Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-foundation

Source of release 0.6.1

0.6.1 / src / gc / tests_collect.lucb

#==============================================================================================
#
#   tests_collect - collection: roots, precise edges, finalization, deferral, callbacks
#
#   DESCRIPTION:
#       LibGC has no unit tests of its own in the donor (Tests/ has none for LibGC); these pin
#       the C++ behaviour, with the expected counts taken from a local driver over the
#       reference build's liblagom-gc (the scenario of `collect_garbage finalizes the garbage`
#       gives 1000, 0 and 1 finalized cells there as here).
#
#==============================================================================================

# mark: Collection ==============================================================================

test "a new heap has the size-based allocators and no blocks":
    clobber_stack()
    run_new_heap()

noinline func run_new_heap():
    let heap = create_test_heap()
    assert(gc_vector_size(&heap.m_size_based_cell_allocators) == 7)
    assert(cell_allocator_cell_size(heap_allocator_for_size(heap, 1)) == 64)
    assert(cell_allocator_cell_size(heap_allocator_for_size(heap, 64)) == 64)
    assert(cell_allocator_cell_size(heap_allocator_for_size(heap, 65)) == 96)
    assert(cell_allocator_cell_size(heap_allocator_for_size(heap, 257)) == 512)
    assert(cell_allocator_cell_size(heap_allocator_for_size(heap, 3072)) == 3072)
    assert(heap_the() == heap)
    assert(live_cell_count(heap) == 0)
    assert(not heap_is_gc_deferred(heap))
    destroy_test_heap(heap)

test "collect_garbage finalizes the garbage and keeps what is reachable":
    clobber_stack()
    run_finalizes_garbage()

noinline func run_finalizes_garbage():
    let heap = create_test_heap()
    var root = root_create[TestCell](new_test_cell(heap, 1))
    let first = root_cell(&root) else trap("no root cell")
    first.left = new_test_cell(heap, 2)
    let second = first.left else trap("no left")
    second.right = new_test_cell(heap, 3)
    make_garbage(heap, 1000)
    _ = new_test_cell(heap, -5)  # must survive garbage collection

    clobber_stack()
    heap_collect_garbage(heap)
    assert(finalized_count == 1000)
    assert(live_test_cell_count(heap) == 4)

    finalized_count = 0
    clobber_stack()
    heap_collect_garbage(heap)
    assert(finalized_count == 0)

    second.right = none
    finalized_count = 0
    finalized_id_sum = 0
    clobber_stack()
    heap_collect_garbage(heap)
    assert(finalized_count == 1)
    assert(finalized_id_sum == 3)
    assert(live_test_cell_count(heap) == 3)

    root_release(&root)
    destroy_test_heap(heap)

test "a cell reachable only through an unvisited field dies":
    clobber_stack()
    run_unvisited_field_dies()

noinline func run_unvisited_field_dies():
    let heap = create_test_heap()
    var root = root_create[TestCell](new_test_cell(heap, 1))
    let first = root_cell(&root) else trap("no root cell")
    let weak = make_unreferenced_cell(heap, 7)
    first.hidden = weak_ptr(&weak)
    clobber_stack()
    heap_collect_garbage(heap)
    assert(not alive(&weak))
    assert(finalized_id_sum == 7)
    root_release(&root)
    destroy_test_heap(heap)

# mark: Roots ===================================================================================

test "roots: Root handles, the embedder's roots, uprooted cells":
    clobber_stack()
    run_explicit_roots()

noinline func run_explicit_roots():
    let heap = create_test_heap()
    let weak_rooted = make_unreferenced_cell(heap, 10)
    var root = root_of_weak[TestCell](&weak_rooted)
    let weak_embedder = make_unreferenced_cell(heap, 11)
    embedder_roots[0] = weak_ptr(&weak_embedder)
    let weak_free = make_unreferenced_cell(heap, 12)
    clobber_stack()
    heap_collect_garbage(heap)
    assert(alive(&weak_rooted))
    assert(alive(&weak_embedder))
    assert(not alive(&weak_free))

    # A rooted cell that is uprooted is unmarked after marking, so it dies with the garbage.
    heap_uproot_cell(heap, (weak_ptr(&weak_embedder) else trap("dead")).cell())
    clobber_stack()
    heap_collect_garbage(heap)
    assert(not alive(&weak_embedder))
    embedder_roots[0] = none
    assert(gc_vector_is_empty(&heap.m_uprooted_cells))

    root_release(&root)
    clobber_stack()
    heap_collect_garbage(heap)
    assert(not alive(&weak_rooted))
    assert(list_is_empty(&heap.m_roots))
    destroy_test_heap(heap)

test "must_survive_garbage_collection keeps a cell and what it reaches":
    clobber_stack()
    run_must_survive()

noinline func run_must_survive():
    let heap = create_test_heap()
    let weak_survivor = make_unreferenced_cell(heap, -1)
    let weak_child = make_unreferenced_cell(heap, 20)
    link_left(&weak_survivor, &weak_child)
    clobber_stack()
    heap_collect_garbage(heap)
    assert(alive(&weak_survivor))
    assert(alive(&weak_child))
    assert(finalized_count == 0)
    set_id(&weak_survivor, 1)  # no longer must survive
    clobber_stack()
    heap_collect_garbage(heap)
    assert(not alive(&weak_survivor))
    assert(not alive(&weak_child))
    assert(finalized_count == 2)
    destroy_test_heap(heap)

## A RootVector<TestCell>: a RootVectorBase first, then its cells (on the C heap, which no scan sees).
struct TestRootVector:
    var base: RootVectorBase
    var cells: GcVector[TestCell*]

let test_root_vector_vtable: RootVectorBaseVTable = RootVectorBaseVTable(class_info = &root_vector_base_class, gather_roots = test_root_vector_gather_roots_impl)

func test_root_vector_gather_roots_impl(this: RootVectorBase*, roots: GcHashMap[HeapRoot]*):
    let vector = (TestRootVector*)this
    for cell in gc_vector_span(&vector.cells):
        gc_hash_map_set(roots, (usize)cell, HeapRoot(type_ = HeapRootType.root_vector))

## A RootHashMap<i64, TestCell>: its values are roots.
struct TestRootHashMap:
    var base: RootHashMapBase
    var values: GcHashMap[TestCell*]

let test_root_hash_map_vtable: RootHashMapBaseVTable = RootHashMapBaseVTable(class_info = &root_hash_map_base_class, gather_roots = test_root_hash_map_gather_roots_impl)

func test_root_hash_map_gather_roots_impl(this: RootHashMapBase*, roots: GcHashMap[HeapRoot]*):
    let map = (TestRootHashMap*)this
    for key in gc_hash_map_keys(&map.values):
        let value = *(gc_hash_map_get(&map.values, key) else trap("no value"))
        gc_hash_map_set(roots, (usize)value, HeapRoot(type_ = HeapRootType.root_hash_map))

## A ConservativeVector<FlatPtr>: its words are possible pointers.
struct TestConservativeVector:
    var base: ConservativeVectorBase
    var words: GcVector[u64]

let test_conservative_vector_vtable: ConservativeVectorBaseVTable = ConservativeVectorBaseVTable(class_info = &conservative_vector_base_class, possible_values = test_conservative_vector_possible_values_impl)

func test_conservative_vector_possible_values_impl(this: ConservativeVectorBase*) -> const u64[]:
    let vector = (TestConservativeVector*)this
    return gc_vector_span(&vector.words)

## vector.cells += the cell of `weak`, without leaving its address in the caller's frame.
noinline func append_to_root_vector(vector: TestRootVector*, weak: const Weak[TestCell]*):
    gc_vector_append(&vector.cells, weak_ptr(weak) else trap("dead"))

## map.values[key] = the cell of `weak`, without leaving its address in the caller's frame.
noinline func set_in_root_hash_map(map: TestRootHashMap*, key: usize, weak: const Weak[TestCell]*):
    gc_hash_map_set(&map.values, key, weak_ptr(weak) else trap("dead"))

## conservative.words += an interior pointer to the cell of `weak`, NaN-boxed as LibJS stores
## cells in Values, without leaving the address in the caller's frame.
noinline func append_to_conservative_vector(conservative: TestConservativeVector*, weak: const Weak[TestCell]*):
    let cell_address = (u64)(usize)(weak_ptr(weak) else trap("dead")) + 8
    gc_vector_append(&conservative.words, cell_address | shifted_is_cell_pattern)

test "roots: root vectors, root hash maps, conservative vectors":
    clobber_stack()
    run_root_containers()

noinline func run_root_containers():
    let heap = create_test_heap()
    let vector = (new TestRootVector(base = RootVectorBase(vtable = &test_root_vector_vtable, class_id = 0, m_heap = none, m_list_node = ListNode()), cells = GcVector[TestCell*]()) in memory.heap) else trap("out of memory")
    root_vector_base_construct(&vector.base, heap)
    let map = (new TestRootHashMap(base = RootHashMapBase(vtable = &test_root_hash_map_vtable, class_id = 0, m_heap = none, m_list_node = ListNode()), values = GcHashMap[TestCell*]()) in memory.heap) else trap("out of memory")
    root_hash_map_base_construct(&map.base, heap)
    let conservative = (new TestConservativeVector(base = ConservativeVectorBase(vtable = &test_conservative_vector_vtable, class_id = 0, m_heap = none, m_list_node = ListNode()), words = GcVector[u64]()) in memory.heap) else trap("out of memory")
    conservative_vector_base_construct(&conservative.base, heap)

    let weak_in_vector = make_unreferenced_cell(heap, 30)
    append_to_root_vector(vector, &weak_in_vector)
    let weak_in_map = make_unreferenced_cell(heap, 31)
    set_in_root_hash_map(map, 42, &weak_in_map)
    let weak_in_conservative = make_unreferenced_cell(heap, 32)
    append_to_conservative_vector(conservative, &weak_in_conservative)
    let weak_free = make_unreferenced_cell(heap, 33)

    clobber_stack()
    heap_collect_garbage(heap)
    assert(alive(&weak_in_vector))
    assert(alive(&weak_in_map))
    assert(alive(&weak_in_conservative))
    assert(not alive(&weak_free))

    root_vector_base_destroy(&vector.base)
    root_hash_map_base_destroy(&map.base)
    conservative_vector_base_destroy(&conservative.base)
    clobber_stack()
    heap_collect_garbage(heap)
    assert(not alive(&weak_in_vector))
    assert(not alive(&weak_in_map))
    assert(not alive(&weak_in_conservative))
    gc_vector_clear(&vector.cells)
    gc_hash_map_clear(&map.values)
    gc_vector_clear(&conservative.words)
    free(vector) in memory.heap
    free(map) in memory.heap
    free(conservative) in memory.heap
    destroy_test_heap(heap)

# mark: Deferral, tasks, callbacks, weak containers =============================================

test "DeferGC postpones a collection until the deferral ends":
    clobber_stack()
    run_defer_gc()

noinline func run_defer_gc():
    let heap = create_test_heap()
    make_garbage(heap, 10)
    var defer_gc: DeferGc = DeferGc(m_heap = heap)
    defer_gc_construct(&defer_gc, heap)
    assert(heap_is_gc_deferred(heap))
    clobber_stack()
    heap_collect_garbage(heap)
    assert(finalized_count == 0)
    assert(heap.m_should_gc_when_deferral_ends)
    clobber_stack()
    defer_gc_destroy(&defer_gc)
    assert(finalized_count == 10)
    assert(not heap.m_should_gc_when_deferral_ends)
    destroy_test_heap(heap)

var post_gc_task_runs: i64
var sweep_callback_runs: i64

func count_post_gc_task(context: void*?):
    post_gc_task_runs += 1

func count_sweep_callback(context: void*?):
    sweep_callback_runs += 1

test "post-GC tasks run once after a collection, sweep callbacks every sweep":
    clobber_stack()
    run_post_gc_tasks()

noinline func run_post_gc_tasks():
    let heap = create_test_heap()
    post_gc_task_runs = 0
    sweep_callback_runs = 0
    heap_enqueue_post_gc_task(heap, ak.Function0[unit](call = count_post_gc_task, context = none))
    heap_register_sweep_callback(heap, ak.Function0[unit](call = count_sweep_callback, context = none))
    clobber_stack()
    heap_collect_garbage(heap)
    clobber_stack()
    heap_collect_garbage(heap)
    assert(post_gc_task_runs == 1)
    assert(sweep_callback_runs == 2)
    destroy_test_heap(heap)

## A WeakContainer: a list of TestCells that drops the dead ones when told.
struct TestWeakContainer:
    var base: WeakContainer
    var cells: GcVector[TestCell*]
    var calls: i64

let test_weak_container_vtable: WeakContainerVTable = WeakContainerVTable(class_info = &weak_container_class, remove_dead_cells = test_weak_container_remove_dead_cells_impl)

func test_weak_container_remove_dead_cells_impl(this: WeakContainer*):
    let container = (TestWeakContainer*)this
    container.calls += 1
    var i: usize = 0
    while i < gc_vector_size(&container.cells):
        if cell_state(gc_vector_at(&container.cells, i).cell()) != CellState.live:
            _ = gc_vector_unstable_take(&container.cells, i)
        else:
            i += 1

test "weak containers remove their dead cells after each sweep":
    clobber_stack()
    run_weak_containers()

noinline func run_weak_containers():
    let heap = create_test_heap()
    let container = (new TestWeakContainer(base = WeakContainer(vtable = &test_weak_container_vtable, class_id = 0, m_registered = false, m_heap = heap, m_list_node = ListNode()), cells = GcVector[TestCell*](), calls = 0) in memory.heap) else trap("out of memory")
    weak_container_construct(&container.base, heap)
    var root = root_create[TestCell](new_test_cell(heap, 1))
    gc_vector_append(&container.cells, root_cell(&root) else trap("no cell"))
    let weak = make_unreferenced_cell(heap, 2)
    gc_vector_append(&container.cells, weak_ptr(&weak) else trap("dead"))
    clobber_stack()
    heap_collect_garbage(heap)
    assert(container.calls == 1)
    assert(gc_vector_size(&container.cells) == 1)
    weak_container_destroy(&container.base)
    clobber_stack()
    heap_collect_garbage(heap)
    assert(container.calls == 1)
    root_release(&root)
    gc_vector_clear(&container.cells)
    free(container) in memory.heap
    destroy_test_heap(heap)

# mark: Thresholds and heap destruction =========================================================

test "the threshold follows the live bytes and collects on allocation":
    clobber_stack()
    run_threshold()

noinline func run_threshold():
    let heap = create_test_heap()
    assert(heap.m_gc_bytes_threshold == heap_gc_min_bytes_threshold)
    # 4 MiB of garbage: the allocations past the threshold collect by themselves
    make_garbage(heap, (i64)(heap_gc_min_bytes_threshold // memory.size_of(TestCell)) + 100)
    assert(finalized_count > 0)
    assert(heap.m_allocated_bytes_since_last_gc < heap_gc_min_bytes_threshold)
    destroy_test_heap(heap)

test "heap destruction collects everything":
    clobber_stack()
    run_collect_everything()

noinline func run_collect_everything():
    let heap = create_test_heap()
    var root = root_create[TestCell](new_test_cell(heap, 1))
    make_garbage(heap, 50)
    heap_collect_garbage(heap, HeapCollectionType.collect_everything)
    assert(finalized_count == 51)
    assert(live_test_cell_count(heap) == 0)
    # the rooted cell is gone with everything else; its RootImpl is unlinked and given back by hand
    let impl = root.m_impl else trap("no impl")
    list_node_remove(&impl.m_list_node)
    free(impl) in memory.heap
    destroy_test_heap(heap)