Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-foundation

Source of release 0.6.1

0.6.1 / src / gc / heap_3.lucb

#==============================================================================================
#
#   heap_3 - Heap: marking, finalization, sweeping, deferral and weak references
#
#   DESCRIPTION:
#       Port of Libraries/LibGC/Heap.cpp (lines 611-842): MarkingVisitor, mark_live_cells,
#       finalize_unmarked_cells, sweep_weak_blocks, sweep_dead_cells, defer_gc and undefer_gc,
#       uproot_cell and create_weak_impl. The additions of DESIGN.md §3.1-§3.2 hook in where
#       marked: a marked cell's own bytes are scanned for blob pointers after its visit_edges
#       (so AK storage a cell owns survives), and the large-object space is finalized and swept
#       beside the heap blocks.
#
#==============================================================================================

# mark: MarkingVisitor ==========================================================================

## Ported from Libraries/LibGC/Heap.cpp:613 GC::MarkingVisitor::MarkingVisitor.
pub func marking_visitor_construct(this: MarkingVisitor*, heap: Heap*, roots: const GcHashMap[HeapRoot]*, all_live_heap_blocks: const GcHashMap[u8]*):
    this.visitor.vtable = (const CellVisitorVTable*)&marking_visitor_vtable
    this.visitor.class_id = marking_visitor_class.first_id
    this.m_heap = heap
    this.m_all_live_heap_blocks = all_live_heap_blocks
    heap_find_min_and_max_block_addresses(this.m_heap, &this.m_min_block_address, &this.m_max_block_address)
    for root in gc_hash_map_keys(roots):
        cell_visitor_visit_cell(&this.visitor, (Cell*?)root)

## Ported from Libraries/LibGC/Heap.cpp:623 GC::MarkingVisitor::visit_impl (override).
pub func marking_visitor_visit_impl_cell_impl(base: CellVisitor*, cell: Cell*):
    let this = (MarkingVisitor*)base
    if cell_is_marked(cell):
        return
    if heap_debug:
        ak.dbgln(f"  ! 0x{(usize)cell:x}")

    cell_set_marked(cell, true)
    gc_vector_append(&this.m_work_queue, cell)

## Ported from Libraries/LibGC/Heap.cpp:633 GC::MarkingVisitor::visit_impl (override).
pub func marking_visitor_visit_impl_span_nan_boxed_value_impl(base: CellVisitor*, values: const NanBoxedValue[]):
    let this = (MarkingVisitor*)base
    gc_vector_ensure_capacity(&this.m_work_queue, gc_vector_size(&this.m_work_queue) + values.length)

    for value in values:
        if not nan_boxed_value_is_cell(&value):
            continue
        let cell = nan_boxed_value_as_cell_const(&value)
        if cell_is_marked(cell):
            continue
        if heap_debug:
            ak.dbgln(f"  ! 0x{(usize)cell:x}")

        cell_set_marked(cell, true)
        gc_vector_append(&this.m_work_queue, cell)

## Ported from Libraries/LibGC/Heap.cpp:650 GC::MarkingVisitor::visit_possible_values (override).
pub func marking_visitor_visit_possible_values_impl(base: CellVisitor*, bytes: const u8[]):
    let this = (MarkingVisitor*)base
    var possible_pointers: GcHashMap[HeapRoot]
    defer gc_hash_map_clear(&possible_pointers)

    let raw_pointer_sized_values = (const usize*)bytes.data
    for i in 0..<(bytes.length // memory.size_of(usize)):
        add_possible_value(&possible_pointers, raw_pointer_sized_values[i], HeapRoot(type_ = HeapRootType.heap_function_captured_pointer), this.m_min_block_address, this.m_max_block_address)

    for found in for_each_cell_among_possible_pointers(this.m_heap, this.m_all_live_heap_blocks, &possible_pointers):
        let cell = found.0
        if cell_is_marked(cell):
            continue
        if cell_state(cell) != CellState.live:
            continue
        cell_set_marked(cell, true)
        gc_vector_append(&this.m_work_queue, cell)

## Ported from Libraries/LibGC/Heap.cpp:668 GC::MarkingVisitor::mark_all_live_cells.
pub func marking_visitor_mark_all_live_cells(this: MarkingVisitor*):
    while not gc_vector_is_empty(&this.m_work_queue):
        let cell = gc_vector_take_last(&this.m_work_queue)
        cell_visit_edges(cell, &this.visitor)
        # Addition (DESIGN.md §3.1): the AK storage a cell owns (Strings, Vectors, captures) is
        # found by scanning the cell's own bytes for blob pointers, never for cell pointers.
        if not cell_is_blob(cell):
            marking_visitor_visit_blob_pointers(this, cell)

## Addition: mark the blobs the words of `cell` point into (a blob is marked and queued, so its
## words are scanned in turn; cells the words point to are left to the precise visit_edges).
func marking_visitor_visit_blob_pointers(this: MarkingVisitor*, cell: Cell*):
    let words = (const usize*)cell
    for i in 0..<(heap_cell_storage_size(this.m_heap, cell) // memory.size_of(usize)):
        let word = words[i]
        if word < this.m_min_block_address or word > this.m_max_block_address:
            continue
        let target = heap_cell_from_possible_pointer(this.m_heap, this.m_all_live_heap_blocks, word) else continue
        if not cell_is_blob(target) or cell_is_marked(target) or cell_state(target) != CellState.live:
            continue
        cell_set_marked(target, true)
        gc_vector_append(&this.m_work_queue, target)

## Ported from Libraries/LibGC/Heap.cpp:683 GC::Heap::mark_live_cells.
pub func heap_mark_live_cells(this: Heap*, roots: const GcHashMap[HeapRoot]*, all_live_heap_blocks: const GcHashMap[u8]*):
    if heap_debug:
        ak.dbgln("mark_live_cells:")

    var visitor: MarkingVisitor = ---
    memory.set(u8[]((u8*)&visitor, memory.size_of(MarkingVisitor)), 0)
    marking_visitor_construct(&visitor, this, roots, all_live_heap_blocks)
    marking_visitor_mark_all_live_cells(&visitor)
    gc_vector_clear(&visitor.m_work_queue)

    for inverse_root in gc_vector_span(&this.m_uprooted_cells):
        cell_set_marked(inverse_root else trap("uprooted a null cell"), false)

    gc_vector_clear(&this.m_uprooted_cells)

# mark: Finalization and sweeping ===============================================================

## Ported from Libraries/LibGC/Heap.cpp:696 GC::Heap::finalize_unmarked_cells.
pub func heap_finalize_unmarked_cells(this: Heap*):
    for block in heap_for_each_block(this):
        if not heap_block_overrides_finalize(block):
            continue
        for cell in heap_block_for_each_cell_in_state(block, CellState.live):
            if not cell_is_marked(cell):
                cell_finalize(cell)
    heap_finalize_unmarked_large_cells(this)

## Ported from Libraries/LibGC/Heap.cpp:709 GC::Heap::sweep_weak_blocks.
pub func heap_sweep_weak_blocks(this: Heap*):
    for node in list_nodes(&this.m_usable_weak_blocks):
        weak_block_sweep(weak_block_from_list_node(node), &this.m_weak_impls)
    var now_usable_weak_blocks: GcVector[WeakBlock*]
    defer gc_vector_clear(&now_usable_weak_blocks)
    for node in list_nodes(&this.m_full_weak_blocks):
        let weak_block = weak_block_from_list_node(node)
        weak_block_sweep(weak_block, &this.m_weak_impls)
        if weak_block_can_allocate(weak_block):
            gc_vector_append(&now_usable_weak_blocks, weak_block)
    for weak_block in gc_vector_span(&now_usable_weak_blocks):
        list_append(&this.m_usable_weak_blocks, &weak_block.m_list_node)

## Ported from Libraries/LibGC/Heap.cpp:725 GC::Heap::sweep_dead_cells. `measurement_start` is
## the time.now() the collection began at (Core::ElapsedTimer).
pub func heap_sweep_dead_cells(this: Heap*, print_report: bool, measurement_start: u64):
    if heap_debug:
        ak.dbgln("sweep_dead_cells:")
    var empty_blocks: GcVector[HeapBlock*]
    defer gc_vector_clear(&empty_blocks)
    var full_blocks_that_became_usable: GcVector[HeapBlock*]
    defer gc_vector_clear(&full_blocks_that_became_usable)

    var collected_cells: usize = 0
    var live_cells: usize = 0
    var collected_cell_bytes: usize = 0
    var live_cell_bytes: usize = 0

    for block in heap_for_each_block(this):
        var block_has_live_cells = false
        let block_was_full = heap_block_is_full(block)
        for cell in heap_block_for_each_cell_in_state(block, CellState.live):
            if not cell_is_marked(cell):
                if heap_debug:
                    ak.dbgln(f"  ~ 0x{(usize)cell:x}")
                heap_block_deallocate(block, cell)
                collected_cells += 1
                collected_cell_bytes += heap_block_cell_size(block)
            else:
                cell_set_marked(cell, false)
                block_has_live_cells = true
                live_cells += 1
                live_cell_bytes += heap_block_cell_size(block)
        if not block_has_live_cells:
            gc_vector_append(&empty_blocks, block)
        elif block_was_full != heap_block_is_full(block):
            gc_vector_append(&full_blocks_that_became_usable, block)

    # Addition: the large objects die here too; their mappings go back after the weak containers
    # and sweep callbacks have looked at them, as empty blocks do.
    let (large_collected, large_collected_bytes, large_live, large_live_bytes) = heap_sweep_dead_large_cells(this)
    collected_cells += large_collected
    collected_cell_bytes += large_collected_bytes
    live_cells += large_live
    live_cell_bytes += large_live_bytes

    for node in list_nodes(&this.m_weak_containers):
        weak_container_remove_dead_cells(weak_container_from_list_node(node))

    for callback in gc_vector_span(&this.m_sweep_callbacks):
        ak.function0_call(&callback)

    for block in gc_vector_span(&empty_blocks):
        if heap_debug:
            ak.dbgln(f" - HeapBlock empty @ 0x{(usize)block:x}: cell_size={heap_block_cell_size(block)}")
        cell_allocator_block_did_become_empty(heap_block_cell_allocator(block), block)

    for block in gc_vector_span(&full_blocks_that_became_usable):
        if heap_debug:
            ak.dbgln(f" - HeapBlock usable again @ 0x{(usize)block:x}: cell_size={heap_block_cell_size(block)}")
        cell_allocator_block_did_become_usable(heap_block_cell_allocator(block), block)

    let freed_large_objects = heap_release_dead_large_objects(this)

    if heap_debug:
        for block in heap_for_each_block(this):
            ak.dbgln(f" > Live HeapBlock @ 0x{(usize)block:x}: cell_size={heap_block_cell_size(block)}")

    this.m_gc_bytes_threshold = live_cell_bytes if live_cell_bytes > heap_gc_min_bytes_threshold else heap_gc_min_bytes_threshold

    if print_report:
        let time_spent = time.since(measurement_start)
        var live_block_count: usize = 0
        for _ in heap_for_each_block(this):
            live_block_count += 1

        ak.dbgln("Garbage collection report")
        ak.dbgln("=============================================")
        ak.dbgln(f"     Time spent: {time_spent // 1000000} ms")
        ak.dbgln(f"     Live cells: {live_cells} ({live_cell_bytes} bytes)")
        ak.dbgln(f"Collected cells: {collected_cells} ({collected_cell_bytes} bytes)")
        ak.dbgln(f"    Live blocks: {live_block_count} ({live_block_count * heap_block_base_block_size} bytes)")
        ak.dbgln(f"   Freed blocks: {gc_vector_size(&empty_blocks)} ({gc_vector_size(&empty_blocks) * heap_block_base_block_size} bytes)")
        ak.dbgln(f"  Freed objects: {freed_large_objects} (large-object space)")
        ak.dbgln("=============================================")

# mark: Deferral, uprooting, weak references ====================================================

## Ported from Libraries/LibGC/Heap.cpp:803 GC::Heap::defer_gc.
pub func heap_defer_gc(this: Heap*):
    this.m_gc_deferrals += 1

## Ported from Libraries/LibGC/Heap.cpp:808 GC::Heap::undefer_gc.
pub func heap_undefer_gc(this: Heap*):
    assert(this.m_gc_deferrals > 0)
    this.m_gc_deferrals -= 1

    if this.m_gc_deferrals == 0:
        if this.m_should_gc_when_deferral_ends:
            heap_collect_garbage(this)
        this.m_should_gc_when_deferral_ends = false

## Ported from Libraries/LibGC/Heap.cpp:820 GC::Heap::uproot_cell.
pub func heap_uproot_cell(this: Heap*, cell: Cell*?):
    gc_vector_append(&this.m_uprooted_cells, cell)

## Ported from Libraries/LibGC/Heap.cpp:825 GC::Heap::create_weak_impl. The port gives a cell one
## impl, which all its Weaks share (weak.lucb): while the cell lives, the impl made for it first
## is answered again.
pub func heap_create_weak_impl(this: Heap*, ptr: void*?) -> WeakImpl*:
    if let cell = ptr:
        if let existing = gc_hash_map_get(&this.m_weak_impls, (usize)cell):
            return *existing

    if list_is_empty(&this.m_usable_weak_blocks):
        # NOTE: These are leaked on Heap destruction, but that's fine since Heap is tied to process lifetime.
        let weak_block = weak_block_create()
        list_append(&this.m_usable_weak_blocks, &weak_block.m_list_node)

    let weak_block = weak_block_from_list_node(list_first(&this.m_usable_weak_blocks) else trap("no usable weak block"))
    let new_weak_impl = weak_block_allocate(weak_block, (Cell*?)ptr) else trap("VERIFY: a usable weak block allocates")
    if not weak_block_can_allocate(weak_block):
        list_append(&this.m_full_weak_blocks, &weak_block.m_list_node)

    if let cell = ptr:
        gc_hash_map_set(&this.m_weak_impls, (usize)cell, new_weak_impl)
    return new_weak_impl