Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-foundation

Source of release 0.6.0

0.6.0 / src / gc / heap_1.lucb

#==============================================================================================
#
#   heap_1 - Heap: construction, cell allocation, registration of roots, possible pointers
#
#   DESCRIPTION:
#       Port of Libraries/LibGC/Heap.cpp (lines 1-127: the heap, will_allocate,
#       add_possible_value, find_min_and_max_block_addresses, for_each_cell_among_possible_pointers)
#       and of Heap.h's inline functions (lines 1-254). `Heap::allocate<T>(args...)` is
#       heap_allocate_cell followed by the caller's construction under DeferGC (DESIGN.md §2.3);
#       Base cannot ask T for its allocator, so the caller passes its type-isolating allocator,
#       or none for a size-based one. Cells come back zeroed with a live Cell header.
#
#==============================================================================================

assert(heap_block_min_possible_cell_size <= 32, "Heap Cell tracking uses too much data!")

# mark: The heap ================================================================================

## Ported from Libraries/LibGC/Heap.cpp:43 GC::Heap::the.
pub func heap_the() -> Heap*:
    return s_the else trap("GC::Heap::the: no heap")

## Ported from Libraries/LibGC/Heap.cpp:48 GC::Heap::Heap. The heap belongs to the thread that
## constructs it: its stack is the one gather_conservative_roots scans.
pub func heap_construct(this: Heap*, gather_embedder_roots: ak.Function1[GcHashMap[HeapRoot]*, unit]):
    heap_init_fields(this)
    ak.stack_info_construct(&this.m_stack_info)
    this.m_gather_embedder_roots = gather_embedder_roots
    s_the = this
    for cell_size in cell_size_classes:
        let allocator = (new CellAllocator in memory.heap) else trap("out of memory")
        cell_allocator_construct(allocator, cell_size)
        gc_vector_append(&this.m_size_based_cell_allocators, allocator)
    heap_construct_blob_allocators(this)
    # Addition (DESIGN.md §3.3 rule 5, §4.1.1): AK's atomic storage on this thread comes from
    # this heap's atomic blobs from now on.
    ak.atomic_allocator = heap_atomic_allocator(this)

## The size classes of the size-based cell allocators (and of the blobs).
let cell_size_classes: usize[7] = [64, 96, 128, 256, 512, 1024, 3072]

## Ported from Libraries/LibGC/Heap.cpp:62 GC::Heap::~Heap: collect everything, then what the
## members' destructors do: the size-based allocators give their cached blocks back to the OS.
## Type-isolating allocators outlive the heap, as in C++ (they are static there); they are
## unlinked so that they register with the next heap. Weak blocks are leaked, as in C++.
pub func heap_destroy(this: Heap*):
    heap_collect_garbage(this, HeapCollectionType.collect_everything)
    # Addition: AK's atomic storage goes back to the current allocator.
    ak.atomic_allocator = none

    while let node = list_first(&this.m_all_cell_allocators):
        list_node_remove(node)
    for allocator in gc_vector_span(&this.m_size_based_cell_allocators):
        block_allocator_destroy(&allocator.m_block_allocator)
        free(allocator) in memory.heap
    gc_vector_clear(&this.m_size_based_cell_allocators)
    heap_destroy_blob_allocators(this)
    gc_vector_clear(&this.m_uprooted_cells)
    gc_vector_clear(&this.m_post_gc_tasks)
    gc_vector_clear(&this.m_sweep_callbacks)
    gc_hash_map_clear(&this.m_weak_impls)
    if s_the == this:
        s_the = none

# mark: Heap.h ==================================================================================

## Ported from Libraries/LibGC/Heap.h:64 GC::Heap::should_collect_on_every_allocation.
pub func heap_should_collect_on_every_allocation(this: const Heap*) -> bool:
    return this.m_should_collect_on_every_allocation

## Ported from Libraries/LibGC/Heap.h:65 GC::Heap::set_should_collect_on_every_allocation.
pub func heap_set_should_collect_on_every_allocation(this: Heap*, b: bool):
    this.m_should_collect_on_every_allocation = b

## Ported from Libraries/LibGC/Heap.h:189 GC::Heap::did_create_root.
pub func heap_did_create_root(this: Heap*, impl: RootImpl*):
    assert(not list_contains(&this.m_roots, &impl.m_list_node))
    list_append(&this.m_roots, &impl.m_list_node)

## Ported from Libraries/LibGC/Heap.h:195 GC::Heap::did_destroy_root.
pub func heap_did_destroy_root(this: Heap*, impl: RootImpl*):
    assert(list_contains(&this.m_roots, &impl.m_list_node))
    list_remove(&this.m_roots, &impl.m_list_node)

## Ported from Libraries/LibGC/Heap.h:201 GC::Heap::did_create_root_vector.
pub func heap_did_create_root_vector(this: Heap*, vector: RootVectorBase*):
    assert(not list_contains(&this.m_root_vectors, &vector.m_list_node))
    list_append(&this.m_root_vectors, &vector.m_list_node)

## Ported from Libraries/LibGC/Heap.h:207 GC::Heap::did_destroy_root_vector.
pub func heap_did_destroy_root_vector(this: Heap*, vector: RootVectorBase*):
    assert(list_contains(&this.m_root_vectors, &vector.m_list_node))
    list_remove(&this.m_root_vectors, &vector.m_list_node)

## Ported from Libraries/LibGC/Heap.h:213 GC::Heap::did_create_root_hash_map.
pub func heap_did_create_root_hash_map(this: Heap*, hash_map: RootHashMapBase*):
    assert(not list_contains(&this.m_root_hash_maps, &hash_map.m_list_node))
    list_append(&this.m_root_hash_maps, &hash_map.m_list_node)

## Ported from Libraries/LibGC/Heap.h:219 GC::Heap::did_destroy_root_hash_map.
pub func heap_did_destroy_root_hash_map(this: Heap*, hash_map: RootHashMapBase*):
    assert(list_contains(&this.m_root_hash_maps, &hash_map.m_list_node))
    list_remove(&this.m_root_hash_maps, &hash_map.m_list_node)

## Ported from Libraries/LibGC/Heap.h:225 GC::Heap::did_create_conservative_vector.
pub func heap_did_create_conservative_vector(this: Heap*, vector: ConservativeVectorBase*):
    assert(not list_contains(&this.m_conservative_vectors, &vector.m_list_node))
    list_append(&this.m_conservative_vectors, &vector.m_list_node)

## Ported from Libraries/LibGC/Heap.h:231 GC::Heap::did_destroy_conservative_vector.
pub func heap_did_destroy_conservative_vector(this: Heap*, vector: ConservativeVectorBase*):
    assert(list_contains(&this.m_conservative_vectors, &vector.m_list_node))
    list_remove(&this.m_conservative_vectors, &vector.m_list_node)

## Ported from Libraries/LibGC/Heap.h:237 GC::Heap::did_create_weak_container.
pub func heap_did_create_weak_container(this: Heap*, set: WeakContainer*):
    assert(not list_contains(&this.m_weak_containers, &set.m_list_node))
    list_append(&this.m_weak_containers, &set.m_list_node)

## Ported from Libraries/LibGC/Heap.h:243 GC::Heap::did_destroy_weak_container.
pub func heap_did_destroy_weak_container(this: Heap*, set: WeakContainer*):
    assert(list_contains(&this.m_weak_containers, &set.m_list_node))
    list_remove(&this.m_weak_containers, &set.m_list_node)

## Ported from Libraries/LibGC/Heap.h:249 GC::Heap::register_cell_allocator.
pub func heap_register_cell_allocator(this: Heap*, allocator: CellAllocator*):
    list_append(&this.m_all_cell_allocators, &allocator.m_list_node)

## Ported from Libraries/LibGC/Heap.h:88 GC::Heap::is_gc_deferred.
pub func heap_is_gc_deferred(this: const Heap*) -> bool:
    return this.m_gc_deferrals > 0

## Ported from Libraries/LibGC/Heap.h:113 GC::Heap::allocate_cell: a zeroed live cell of
## `sizeof(T)` from `allocator` (T's GC_DECLARE_ALLOCATOR), or from the size-based allocator of
## its size when `allocator` is none (GC_DECLARE_SIZE_BASED_ALLOCATOR). The compile-time check
## has_own_gc_allocator_marker<T>() has no counterpart: the allocator is an argument.
pub func heap_allocate_cell[T](this: Heap*, allocator: CellAllocator*?) -> Cell*:
    return heap_allocate_cell_of_size(this, memory.size_of(T), allocator)

## heap_allocate_cell for a size known at run time (a ClassInfo's size): the allocation seam of
## the engine's creation helpers (DESIGN.md §2.3). A cell too large for a heap block goes to the
## large-object space (addition, heap_blobs.lucb).
pub func heap_allocate_cell_of_size(this: Heap*, cell_size: usize, allocator: CellAllocator*?) -> Cell*:
    if cell_size > heap_block_base_block_size - heap_block_storage_offset:
        return heap_allocate_large_cell(this, cell_size, allocator)
    heap_will_allocate(this, cell_size)
    var cell: Cell* = ---
    if let type_allocator = allocator:
        assert(type_allocator.m_cell_size >= cell_size)
        cell = cell_allocator_allocate_cell(type_allocator, this)
    else:
        cell = cell_allocator_allocate_cell(heap_allocator_for_size(this, cell_size), this)
    let block = heap_block_from_cell(cell)
    cell_initialize_header(cell, heap_block_cell_size(block))
    return cell

## A freshly allocated cell's memory: zeroed (DESIGN.md §2.3: constructors assume zeroed memory)
## and a live, unmarked header whose vtable is Cell's own until the constructor sets its class's.
func cell_initialize_header(cell: Cell*, cell_size: usize):
    memory.set(u8[]((u8*)cell, cell_size), 0)
    cell.vtable = &cell_vtable
    cell.class_id = 0
    cell.m_mark = false
    cell.m_state = CellState.live

## Ported from Libraries/LibGC/Heap.h:138 GC::Heap::allocator_for_size.
pub func heap_allocator_for_size(this: Heap*, cell_size: usize) -> CellAllocator*:
    # FIXME: Use binary search?
    for allocator in gc_vector_span(&this.m_size_based_cell_allocators):
        if cell_allocator_cell_size(allocator) >= cell_size:
            return allocator
    ak.dbgln(f"Cannot get CellAllocator for cell size {cell_size}, largest available is {cell_allocator_cell_size(gc_vector_at(&this.m_size_based_cell_allocators, gc_vector_size(&this.m_size_based_cell_allocators) - 1))}!")
    trap("VERIFY_NOT_REACHED")

## Ported from Libraries/LibGC/Heap.h:150 GC::Heap::for_each_block: every block of every
## registered allocator (`for block in heap_for_each_block(heap)`; Break is `break`).
pub func heap_for_each_block(this: Heap*) -> HeapBlocks:
    return HeapBlocks(heap = this)

## The blocks of a heap: for_each_block as a loop.
pub struct HeapBlocks: luce.Iterable[HeapBlock*, HeapBlockIterator]:
    pub var heap: Heap*

    func iterator() -> HeapBlockIterator:
        return HeapBlockIterator(next_allocator = self.heap.m_all_cell_allocators.m_first, blocks = none)

## The iterator of HeapBlocks: the blocks of one allocator, then of the next.
pub struct HeapBlockIterator: luce.Iterator[HeapBlock*]:
    pub var next_allocator: ListNode*?
    pub var blocks: CellAllocatorBlockIterator?

    func next() -> HeapBlock*?:
        while true:
            if let current = self.blocks:
                var iterator = current
                let block = iterator.next()
                self.blocks = iterator
                if let found = block:
                    return found
            let node = self.next_allocator else return none
            self.next_allocator = node.m_next
            let allocator = cell_allocator_from_list_node(node)
            self.blocks = cell_allocator_for_each_block(allocator).iterator()

## The CellAllocator whose m_list_node is `node` (IntrusiveList's container_of).
func cell_allocator_from_list_node(node: ListNode*) -> CellAllocator*:
    return (CellAllocator*)((u8*)node - memory.offset_of(CellAllocator, m_list_node))

# mark: Heap.cpp ================================================================================

## Ported from Libraries/LibGC/Heap.cpp:67 GC::Heap::will_allocate.
pub func heap_will_allocate(this: Heap*, size: usize):
    if heap_should_collect_on_every_allocation(this):
        this.m_allocated_bytes_since_last_gc = 0
        heap_collect_garbage(this)
    elif this.m_allocated_bytes_since_last_gc + size > this.m_gc_bytes_threshold:
        this.m_allocated_bytes_since_last_gc = 0
        heap_collect_garbage(this)

    this.m_allocated_bytes_since_last_gc += size

## Ported from Libraries/LibGC/Heap.cpp:80 GC::add_possible_value.
func add_possible_value(possible_pointers: GcHashMap[HeapRoot]*, data: usize, origin: HeapRoot, min_block_address: usize, max_block_address: usize):
    # sizeof(FlatPtr*) == sizeof(NanBoxedValue) on every target of the port.
    # Because NanBoxedValue stores pointers in non-canonical form we have to check if the top bytes
    # match any pointer-backed tag, in that case we have to extract the pointer to its
    # canonical form and add that as a possible pointer.
    var possible_pointer: usize = 0
    if ((u64)data & shifted_is_cell_pattern) == shifted_is_cell_pattern:
        possible_pointer = nan_boxed_value_extract_pointer_bits((u64)data)
    else:
        possible_pointer = data
    if possible_pointer < min_block_address or possible_pointer > max_block_address:
        return
    gc_hash_map_set(possible_pointers, possible_pointer, origin)

## Ported from Libraries/LibGC/Heap.cpp:104 GC::Heap::find_min_and_max_block_addresses. The
## range also covers the large-object space (addition), so that pointers into large objects pass
## add_possible_value's filter.
pub func heap_find_min_and_max_block_addresses(this: Heap*, min_address: usize*, max_address: usize*):
    *min_address = ~(usize)0  # explode_byte(0xff)
    *max_address = 0
    for node in list_nodes(&this.m_all_cell_allocators):
        let allocator = cell_allocator_from_list_node(node)
        let allocator_min = cell_allocator_min_block_address(allocator)
        let allocator_max = cell_allocator_max_block_address(allocator) +% heap_block_base_block_size
        if allocator_min < *min_address:
            *min_address = allocator_min
        if allocator_max > *max_address:
            *max_address = allocator_max
    heap_extend_block_address_range_with_large_objects(this, min_address, max_address)

## Ported from Libraries/LibGC/Heap.cpp:115 GC::for_each_cell_among_possible_pointers: the cells
## the possible pointers point into, each with the pointer that found it (`for found in ...`, a
## (cell, pointer) pair). The heap is passed to look up large objects too (addition).
func for_each_cell_among_possible_pointers(heap: Heap*, all_live_heap_blocks: const GcHashMap[u8]*, possible_pointers: const GcHashMap[HeapRoot]*) -> PossibleCells:
    return PossibleCells(heap = heap, all_live_heap_blocks = all_live_heap_blocks, possible_pointers = possible_pointers)

## The cells among a set of possible pointers.
struct PossibleCells: luce.Iterable[(Cell*, usize), PossibleCellIterator]:
    var heap: Heap*
    var all_live_heap_blocks: const GcHashMap[u8]*
    var possible_pointers: const GcHashMap[HeapRoot]*

    func iterator() -> PossibleCellIterator:
        return PossibleCellIterator(heap = self.heap, all_live_heap_blocks = self.all_live_heap_blocks, keys = gc_hash_map_keys(self.possible_pointers).iterator())

## The iterator of PossibleCells.
struct PossibleCellIterator: luce.Iterator[(Cell*, usize)]:
    var heap: Heap*
    var all_live_heap_blocks: const GcHashMap[u8]*
    var keys: GcHashMapKeyIterator[HeapRoot]

    func next() -> (Cell*, usize)?:
        while let possible_pointer = self.keys.next():
            if possible_pointer == 0:
                continue
            if let cell = heap_cell_from_possible_pointer(self.heap, self.all_live_heap_blocks, possible_pointer):
                return (cell, possible_pointer)
        return none

## The body of for_each_cell_among_possible_pointers's loop for one pointer: the live heap block
## it points into and the cell there, or else (addition) the large object it points into.
func heap_cell_from_possible_pointer(heap: Heap*, all_live_heap_blocks: const GcHashMap[u8]*, possible_pointer: usize) -> Cell*?:
    if let possible_heap_block = heap_block_from_cell_address(possible_pointer):
        if gc_hash_map_contains(all_live_heap_blocks, (usize)possible_heap_block):
            return heap_block_cell_from_possible_pointer(possible_heap_block, possible_pointer)
    return heap_large_cell_from_possible_pointer(heap, possible_pointer)