dymokomi/luce-browser-foundation
Source of release 0.6.0
0.6.0 / 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.
#
# 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 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 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 cell_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 = cell_size_classes[cell_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
var chosen: CellAllocator*? = none
for allocator in gc_vector_span(allocators):
if cell_allocator_cell_size(allocator) >= blob_header_size + size:
chosen = allocator
break
let allocator = chosen else trap("no blob size class")
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
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)
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