Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-foundation

Source of release 0.6.1

0.6.1 / src / gc / heap_blobs.lucb

#==============================================================================================
#
#   heap_blobs - managed blobs, atomic blobs and the large-object space
#
#   DESCRIPTION:
#       Additions to LibGC (DESIGN.md §3.1-§3.3). Every allocation AK makes in the port (String
#       and Vector storage, ref-counted objects, lambda captures) is a *blob*: a cell whose
#       vtable says "blob", laid out as a Cell header followed by the payload, in the same size
#       classes as the size-based cells. A blob's visit_edges scans its payload conservatively;
#       an *atomic* blob (string bytes, pixels) is never scanned. The heap is luce-base's
#       `Allocator` (its methods are in types_heap.lucb), so ported code allocates blobs with
#       plain `new` and `alloc` under `with heap`; releasing is a no-op, the sweep reclaims.
#
#       Blobs have size classes of their own, finer than the cells' (blob_size_classes).
#       The *large-object space* holds blobs above the largest size class and cells too large for
#       a heap block: each in its own mapping aligned to BLOCK_SIZE whose header begins with a
#       HeapBlockBase, so Cell::heap() works for a large cell as for any other, kept in an array
#       sorted by address for the pointer lookups of the conservative scans.
#
#==============================================================================================

## The tag new blobs carry in their header's class_id, which a blob does not otherwise use: what
## the thread was doing when it allocated them, so that a census of the heap can tell blobs apart
## (the engine's webview memory census). 0 is untagged. (Addition, for diagnostics.)
pub local var heap_blob_tag: u16 = 0

## The bytes before a blob's payload: its Cell header.
pub let blob_header_size: usize = memory.size_of(Cell)

## The alignment of a blob's payload in a heap block (cells are 16-aligned, the header is 16).
let blob_alignment: usize = 16

## The vtable of a (scanned) blob.
pub let blob_vtable: CellVTable = CellVTable(class_info = &blob_class, class_name = blob_class_name_impl, visit_edges = blob_visit_edges_impl)

## Class information of a blob.
pub let blob_class: ak.ClassInfo = ak.ClassInfo(name = "Blob", first_id = 0, last_id = 0, size = memory.size_of(Cell), vtable = (const void*)&blob_vtable)

## The vtable of an atomic blob: nothing to visit.
pub let atomic_blob_vtable: CellVTable = CellVTable(class_info = &atomic_blob_class, class_name = atomic_blob_class_name_impl)

## Class information of an atomic blob.
pub let atomic_blob_class: ak.ClassInfo = ak.ClassInfo(name = "AtomicBlob", first_id = 0, last_id = 0, size = memory.size_of(Cell), vtable = (const void*)&atomic_blob_vtable)

## A blob's class name.
func blob_class_name_impl(this: Cell*) -> ak.StringView:
    return ak.sv("Blob")

## An atomic blob's class name.
func atomic_blob_class_name_impl(this: Cell*) -> ak.StringView:
    return ak.sv("AtomicBlob")

## A blob's visit_edges: every word of its payload is a possible pointer.
func blob_visit_edges_impl(this: Cell*, visitor: CellVisitor*):
    let heap = cell_heap(this)
    let payload = (u8*)this + blob_header_size
    cell_visitor_visit_possible_values(visitor, u8[](payload, heap_cell_storage_size(heap, this) - blob_header_size))

## Whether `cell` is a blob (scanned or atomic).
pub func cell_is_blob(cell: const Cell*) -> bool:
    return cell.vtable == &blob_vtable or cell.vtable == &atomic_blob_vtable

## The allocator view that allocates atomic blobs in `heap` (DESIGN.md §3.3 rule 5): what ak's
## atomic allocations go through while `heap` is the current allocator.
pub func heap_atomic_allocator(heap: Heap*) -> memory.Allocator:
    return &heap.m_atomic_allocator

# mark: Blob allocation =========================================================================

## The size classes of blobs, header included. They are finer than the cells' (64 to 3072), as
## malloc's are: blobs hold what the donor keeps in malloc (AK's storage), and with the cells'
## classes a blob just above one wasted up to half its cell, or most of a block above 3072 (a
## large object maps at least a 16 KiB block). Each is a multiple of 16 (the payload's
## alignment), and from 2720 on a block's storage (16,320 bytes) holds a whole number of them.
let blob_size_classes: usize[28] = [32, 48, 64, 80, 96, 112, 128, 160, 192, 224, 256, 320, 384, 448, 512, 640, 768, 896, 1024, 1280, 1536, 1792, 2048, 2720, 3264, 4080, 5440, 8160]

## The index of the smallest blob size class of at least `cell_size` bytes (at most the largest).
func blob_size_class_index(cell_size: usize) -> usize:
    var low: usize = 0
    var high = blob_size_classes.length - 1
    while low < high:
        let middle = (low + high) // 2
        if blob_size_classes[middle] >= cell_size:
            high = middle
        else:
            low = middle + 1
    return low

## The blob allocators of `heap`, scanned and atomic, one per size class.
func heap_construct_blob_allocators(this: Heap*):
    this.m_atomic_allocator = HeapAtomicAllocator(m_heap = this)
    for cell_size in blob_size_classes:
        let allocator = (new CellAllocator in memory.heap) else trap("out of memory")
        cell_allocator_construct(allocator, cell_size, ak.sv("Blob"))
        gc_vector_append(&this.m_blob_allocators, allocator)
        let atomic_allocator = (new CellAllocator in memory.heap) else trap("out of memory")
        cell_allocator_construct(atomic_allocator, cell_size, ak.sv("AtomicBlob"))
        gc_vector_append(&this.m_atomic_blob_allocators, atomic_allocator)

## Give the blob allocators and the large-object space back (after collect everything).
func heap_destroy_blob_allocators(this: Heap*):
    for allocator in gc_vector_span(&this.m_blob_allocators):
        block_allocator_destroy(&allocator.m_block_allocator)
        free(allocator) in memory.heap
    for allocator in gc_vector_span(&this.m_atomic_blob_allocators):
        block_allocator_destroy(&allocator.m_block_allocator)
        free(allocator) in memory.heap
    gc_vector_clear(&this.m_blob_allocators)
    gc_vector_clear(&this.m_atomic_blob_allocators)
    for object in gc_vector_span(&this.m_large_objects):
        unmap_aligned_block(object, object.m_mapping_size)
    gc_vector_clear(&this.m_large_objects)

## A blob of `size` bytes at `alignment` (at most BLOCK_SIZE), zeroed, scanned unless `atomic`.
## The empty blob is a dangling, aligned, empty span, as luce-base's allocators answer.
pub func heap_allocate_blob(this: Heap*, size: usize, alignment: usize, atomic: bool) -> u8[]?:
    if size == 0:
        return u8[]((u8*)blob_alignment, 0)
    if alignment > heap_block_base_block_size:
        return none
    let largest = blob_size_classes[blob_size_classes.length - 1]
    var cell: Cell* = ---
    if alignment > blob_alignment or size > largest - blob_header_size:
        cell = heap_allocate_large_object(this, blob_header_size + size, alignment, false, false)
    else:
        heap_will_allocate(this, blob_header_size + size)
        let allocators = &this.m_atomic_blob_allocators if atomic else &this.m_blob_allocators
        let allocator = gc_vector_at(allocators, blob_size_class_index(blob_header_size + size))
        cell = cell_allocator_allocate_cell(allocator, this)
        cell_initialize_header(cell, cell_allocator_cell_size(allocator))
    cell.vtable = &atomic_blob_vtable if atomic else &blob_vtable
    cell.class_id = heap_blob_tag
    return u8[]((u8*)cell + blob_header_size, size)

## Whether the blob `block` has room for `size` bytes where it is.
pub func heap_resize_blob(this: Heap*, block: u8[], size: usize) -> bool:
    if block.length == 0:
        return size == 0
    let cell = (Cell*)((u8*)block.data - blob_header_size)
    return size <= heap_cell_storage_size(this, cell) - blob_header_size

## Releasing a blob does nothing: ported code never frees (DESIGN.md §3.3 rule 3), and a buffer
## that luce-base code releases may still be shared by a copied struct; the sweep reclaims it.
pub func heap_release_blob(this: Heap*, block: u8[]):
    return

## The bytes of `cell`, header included: its heap block's cell size, or its large object's.
func heap_cell_storage_size(this: Heap*, cell: Cell*) -> usize:
    if let object = heap_large_object_containing(this, (usize)cell):
        return object.m_cell_size
    return heap_block_cell_size(heap_block_from_cell(cell))

# mark: The large-object space ==================================================================

## A large object: the header of its own BLOCK_SIZE-aligned mapping. It begins with a
## HeapBlockBase, so HeapBlockBase::from_cell(cell) finds the heap of a large cell.
pub struct LargeObject:
    pub var heap_block_base: HeapBlockBase
    pub var m_mapping_size: usize
    pub var m_cell_offset: usize  # where the cell header begins, from the mapping's start
    pub var m_cell_size: usize  # the cell's bytes, header included
    pub var m_overrides_must_survive_garbage_collection: bool
    pub var m_overrides_finalize: bool

## The cell of a large object.
func large_object_cell(object: LargeObject*) -> Cell*:
    return (Cell*)((u8*)object + object.m_cell_offset)

## A cell too large for a heap block, from `allocator`'s class (its flags) or size-based.
func heap_allocate_large_cell(this: Heap*, cell_size: usize, allocator: CellAllocator*?) -> Cell*:
    var overrides_must_survive_garbage_collection = false
    var overrides_finalize = false
    if let type_allocator = allocator:
        overrides_must_survive_garbage_collection = type_allocator.m_overrides_must_survive_garbage_collection
        overrides_finalize = type_allocator.m_overrides_finalize
    return heap_allocate_large_object(this, cell_size, blob_alignment, overrides_must_survive_garbage_collection, overrides_finalize)

## A large object holding a zeroed live cell of `cell_size` bytes whose payload (after the
## header) is aligned to `alignment`.
func heap_allocate_large_object(this: Heap*, cell_size: usize, alignment: usize, overrides_must_survive_garbage_collection: bool, overrides_finalize: bool) -> Cell*:
    heap_will_allocate(this, cell_size)
    let payload_alignment = alignment if alignment > blob_alignment else blob_alignment
    let cell_offset = (memory.size_of(LargeObject) + blob_header_size + payload_alignment - 1) // payload_alignment * payload_alignment - blob_header_size
    let mapping_size = (cell_offset + cell_size + heap_block_base_block_size - 1) // heap_block_base_block_size * heap_block_base_block_size
    let object = (LargeObject*)map_aligned_block(mapping_size)
    object.heap_block_base.m_heap = this
    object.m_mapping_size = mapping_size
    object.m_cell_offset = cell_offset
    object.m_cell_size = cell_size
    object.m_overrides_must_survive_garbage_collection = overrides_must_survive_garbage_collection
    object.m_overrides_finalize = overrides_finalize

    var index = gc_vector_size(&this.m_large_objects)
    while index > 0 and (usize)gc_vector_at(&this.m_large_objects, index - 1) > (usize)object:
        index -= 1
    gc_vector_insert(&this.m_large_objects, index, object)

    let cell = large_object_cell(object)
    if map_aligned_block_is_zeroed:
        cell_initialize_zeroed_header(cell)
    else:
        cell_initialize_header(cell, cell_size)
    return cell

## The large object whose mapping contains `address`, or none (a binary search by address).
func heap_large_object_containing(this: Heap*, address: usize) -> LargeObject*?:
    let objects = gc_vector_span(&this.m_large_objects)
    var low: usize = 0
    var high = objects.length
    while low < high:
        let middle = low + (high - low) // 2
        if (usize)objects[middle] <= address:
            low = middle + 1
        else:
            high = middle
    if low == 0:
        return none
    let object = objects[low - 1]
    if address >= (usize)object + object.m_mapping_size:
        return none
    return object

## The large cell `pointer` points into (its header or payload), or none.
func heap_large_cell_from_possible_pointer(this: Heap*, pointer: usize) -> Cell*?:
    let object = heap_large_object_containing(this, pointer) else return none
    let cell = large_object_cell(object)
    if pointer < (usize)cell or pointer >= (usize)cell + object.m_cell_size:
        return none
    return cell

## find_min_and_max_block_addresses's range, widened to cover the large objects.
func heap_extend_block_address_range_with_large_objects(this: Heap*, min_address: usize*, max_address: usize*):
    let objects = gc_vector_span(&this.m_large_objects)
    if objects.length == 0:
        return
    let first = (usize)objects[0]
    let last = objects[objects.length - 1]
    if first < *min_address:
        *min_address = first
    if (usize)last + last.m_mapping_size > *max_address:
        *max_address = (usize)last + last.m_mapping_size

## gather_roots for the large objects: the live cells that must survive.
func heap_gather_large_object_must_survive_roots(this: Heap*, roots: GcHashMap[HeapRoot]*):
    for object in gc_vector_span(&this.m_large_objects):
        if not object.m_overrides_must_survive_garbage_collection:
            continue
        let cell = large_object_cell(object)
        if cell_state(cell) == CellState.live and cell_must_survive_garbage_collection(cell):
            gc_hash_map_set(roots, (usize)cell, HeapRoot(type_ = HeapRootType.must_survive_gc))

## finalize_unmarked_cells for the large objects.
func heap_finalize_unmarked_large_cells(this: Heap*):
    for object in gc_vector_span(&this.m_large_objects):
        if not object.m_overrides_finalize:
            continue
        let cell = large_object_cell(object)
        if cell_state(cell) == CellState.live and not cell_is_marked(cell):
            cell_finalize(cell)

## sweep_dead_cells for the large objects: unmarked cells die (their mappings are released by
## heap_release_dead_large_objects), marked ones are unmarked. Answers the collected and live
## counts and bytes.
func heap_sweep_dead_large_cells(this: Heap*) -> (usize, usize, usize, usize):
    var collected: usize = 0
    var collected_bytes: usize = 0
    var live: usize = 0
    var live_bytes: usize = 0
    for object in gc_vector_span(&this.m_large_objects):
        let cell = large_object_cell(object)
        if cell_state(cell) != CellState.live:
            continue
        if not cell_is_marked(cell):
            cell_set_state(cell, CellState.dead)
            collected += 1
            collected_bytes += object.m_cell_size
        else:
            cell_set_marked(cell, false)
            live += 1
            live_bytes += object.m_cell_size
    return (collected, collected_bytes, live, live_bytes)

## Give the mappings of the dead large objects back; answers how many.
func heap_release_dead_large_objects(this: Heap*) -> usize:
    var released: usize = 0
    var index = gc_vector_size(&this.m_large_objects)
    while index > 0:
        index -= 1
        let object = gc_vector_at(&this.m_large_objects, index)
        if cell_state(large_object_cell(object)) == CellState.dead:
            gc_vector_remove(&this.m_large_objects, index)
            unmap_aligned_block(object, object.m_mapping_size)
            released += 1
    return released