dymokomi/luce-browser-foundation
Source of release 0.6.0
0.6.0 / src / gc / tests_blocks.lucb
#==============================================================================================
#
# tests_blocks - heap blocks, weak blocks, NaN-boxed values and the collector's containers
#
# DESCRIPTION:
# The expected values come from a local driver over the reference build's liblagom-gc
# (sizeof(HeapBlock) 64, cell counts per size class, the freelist order after
# deallocating cells 3, 7 and 5, the WeakImpl freelist, extract_pointer_bits on arm64).
#
#==============================================================================================
# mark: Blocks ==================================================================================
test "layout matches LibGC's: header, cell, freelist entry, weak block":
assert(heap_block_storage_offset == 64)
assert(memory.size_of(Cell) == 16)
assert(heap_block_min_possible_cell_size == 24)
assert(memory.size_of(WeakImpl) == 24)
assert(weak_block_impl_count == 681)
assert(memory.size_of(RootImpl) <= 64)
test "cell counts per size class":
let heap = create_test_heap()
let expected: usize[7] = [255, 170, 127, 63, 31, 15, 5]
for (index, cell_size) in cell_size_classes.indexed():
var allocator: CellAllocator
cell_allocator_construct(&allocator, cell_size)
let block = heap_block_create_with_cell_size(heap, &allocator, cell_size, false, false)
assert(heap_block_cell_count(block) == expected[index])
block_allocator_deallocate_block(&allocator.m_block_allocator, block)
block_allocator_destroy(&allocator.m_block_allocator)
destroy_test_heap(heap)
test "a heap block hands out cells in order, then its freelist last-in first-out":
let heap = create_test_heap()
var allocator: CellAllocator
cell_allocator_construct(&allocator, 64)
let block = heap_block_create_with_cell_size(heap, &allocator, 64, false, false)
assert((usize)block % heap_block_base_block_size == 0)
assert(not heap_block_is_full(block))
var cells: (Cell*?)[255]
for i in 0..<heap_block_cell_count(block):
let cell = heap_block_allocate(block) else trap("no cell")
cell.m_state = CellState.live
cell.m_mark = false
cells[i] = cell
assert(heap_block_is_full(block))
assert(heap_block_allocate(block) == none)
let first = cells[0] else trap("no cell")
assert((usize)(cells[1] else trap("no cell")) - (usize)first == 64)
assert((usize)first - (usize)block == 64)
assert(heap_block_from_cell(first) == block)
for i in [3, 7, 5]:
heap_block_deallocate(block, cells[i] else trap("no cell"))
assert(cell_state(cells[i] else trap("no cell")) == CellState.dead)
assert(not heap_block_is_full(block))
var reallocated: usize[3]
for i in 0..<3:
let cell = heap_block_allocate(block) else trap("no cell")
assert(cell_state(cell) == CellState.dead) # a FreelistEntry until constructed
cell.m_state = CellState.live
reallocated[i] = ((usize)cell - (usize)first) // 64
assert(reallocated[0] == 5 and reallocated[1] == 7 and reallocated[2] == 3)
let tenth = cells[10] else trap("no cell")
assert(heap_block_cell_from_possible_pointer(block, (usize)tenth + 13) == tenth)
assert(heap_block_cell_from_possible_pointer(block, (usize)block + 8) == none)
assert(heap_block_is_valid_cell_pointer(block, tenth))
var dead: usize = 0
for _ in heap_block_for_each_cell_in_state(block, CellState.dead):
dead += 1
assert(dead == 0)
block_allocator_deallocate_block(&allocator.m_block_allocator, block)
block_allocator_destroy(&allocator.m_block_allocator)
destroy_test_heap(heap)
test "the block allocator caches freed blocks and hands them out again":
var allocator: BlockAllocator
let a = block_allocator_allocate_block(&allocator, none)
let b = block_allocator_allocate_block(&allocator, none)
assert(a != b)
block_allocator_deallocate_block(&allocator, a)
block_allocator_deallocate_block(&allocator, b)
assert(gc_vector_size(block_allocator_blocks(&allocator)) == 2)
let c = block_allocator_allocate_block(&allocator, none)
assert(c == a or c == b)
assert(gc_vector_size(block_allocator_blocks(&allocator)) == 1)
block_allocator_deallocate_block(&allocator, c)
block_allocator_destroy(&allocator)
assert(gc_vector_is_empty(block_allocator_blocks(&allocator)))
test "a weak block's freelist is last-in first-out":
let block = weak_block_create()
let marker = (Cell*?)(usize)0x10000 else trap("no marker")
let i1 = weak_block_allocate(block, marker) else trap("no impl")
let i2 = weak_block_allocate(block, marker) else trap("no impl")
assert(i1 == &block.m_impls[0])
assert(i2 == &block.m_impls[1])
weak_block_deallocate(block, i1)
let i3 = weak_block_allocate(block, none) else trap("no impl")
assert(i3 == &block.m_impls[0])
assert(weak_impl_state(i3) == WeakImplState.allocated)
assert(weak_block_can_allocate(block))
for _ in 2..<weak_block_impl_count:
_ = weak_block_allocate(block, none)
assert(not weak_block_can_allocate(block))
assert(weak_block_allocate(block, none) == none)
unmap_aligned_block(block, weak_block_block_size)
# mark: NaN-boxed values ========================================================================
test "NaN-boxed values: cells, NaN and the pointer bits":
let samples: u64[5] = [0xfffa000012345678, 0x7ff8000000000000, 0xfff8800000001000, 0x4000000000000000, 0xfff9fffffffffff0]
let expect_cell: bool[5] = [true, false, true, false, true]
let expect_nan: bool[5] = [false, true, false, false, false]
for (i, sample) in samples.indexed():
var value: NanBoxedValue
value.m_value.encoded = sample
assert(nan_boxed_value_is_cell(&value) == expect_cell[i])
assert(nan_boxed_value_is_nan(&value) == expect_nan[i])
if os.arm64:
assert(nan_boxed_value_extract_pointer_bits(0xfffa000012345678) == 0x12345678)
assert(nan_boxed_value_extract_pointer_bits(0xfff8800000001000) == 0x800000001000)
assert(nan_boxed_value_extract_pointer_bits(0xfff9fffffffffff0) == 0xfffffffffff0)
else:
assert(nan_boxed_value_extract_pointer_bits(0xfff8800000001000) == 0xffff800000001000)
assert(canon_nan_bits == 0x7FF8000000000000)
assert(shifted_is_cell_pattern == 0xfff8000000000000)
assert(is_cell_bit == 0xfff8)
# mark: The collector's containers ==============================================================
test "GcVector: append, insert, remove, unstable_take, take_last":
var vector: GcVector[i64]
for i in 0..<100:
gc_vector_append(&vector, i)
assert(gc_vector_size(&vector) == 100)
gc_vector_insert(&vector, 0, -1)
assert(gc_vector_at(&vector, 0) == -1 and gc_vector_at(&vector, 1) == 0)
gc_vector_remove(&vector, 0)
assert(gc_vector_at(&vector, 0) == 0)
assert(gc_vector_unstable_take(&vector, 10) == 10)
assert(gc_vector_at(&vector, 10) == 99)
assert(gc_vector_take_last(&vector) == 98)
assert(gc_vector_size(&vector) == 98)
gc_vector_clear(&vector)
assert(gc_vector_is_empty(&vector) and vector.m_data == none)
test "GcHashMap: set, replace, get, grow, keys":
var map: GcHashMap[i64]
for i: usize in 1..=1000:
gc_hash_map_set(&map, i * 16, (i64)i)
gc_hash_map_set(&map, 16, -1)
assert(gc_hash_map_size(&map) == 1000)
assert(*(gc_hash_map_get(&map, 16) else trap("missing")) == -1)
assert(*(gc_hash_map_get(&map, 16000) else trap("missing")) == 1000)
assert(gc_hash_map_get(&map, 8) == none)
assert(not gc_hash_map_contains(&map, 16016))
var sum: usize = 0
for key in gc_hash_map_keys(&map):
sum += key
assert(sum == 16 * 1000 * 1001 // 2)
gc_hash_map_clear(&map)
assert(gc_hash_map_size(&map) == 0 and gc_hash_map_get(&map, 16) == none)
test "GcHashMap: remove keeps every other key reachable":
var map: GcHashMap[i64]
for i: usize in 1..=1000:
gc_hash_map_set(&map, i * 16, (i64)i)
# Every third key leaves, then the odd ones of those come back with new values.
for i: usize in 1..=1000:
if i % 3 == 0:
assert(gc_hash_map_remove(&map, i * 16))
assert(not gc_hash_map_remove(&map, 48) and not gc_hash_map_remove(&map, 8))
assert(gc_hash_map_size(&map) == 1000 - 333)
for i: usize in 1..=1000:
let value = gc_hash_map_get(&map, i * 16)
if i % 3 == 0:
assert(value == none)
else:
assert(*(value else trap("missing")) == (i64)i)
for i: usize in 1..=1000:
if i % 6 == 3:
gc_hash_map_set(&map, i * 16, -(i64)i)
assert(gc_hash_map_size(&map) == 1000 - 333 + 167)
assert(*(gc_hash_map_get(&map, 48) else trap("missing")) == -3)
var count: usize = 0
for _ in gc_hash_map_keys(&map):
count += 1
assert(count == gc_hash_map_size(&map))
gc_hash_map_clear(&map)
test "intrusive lists: append moves a node between lists":
var a: List
var b: List
var nodes: ListNode[3]
for i in 0..<3:
list_append(&a, &nodes[i])
assert(list_contains(&a, &nodes[1]))
list_append(&b, &nodes[1])
assert(not list_contains(&a, &nodes[1]) and list_contains(&b, &nodes[1]))
var count: usize = 0
for node in list_nodes(&a):
assert(node == &nodes[0] or node == &nodes[2])
count += 1
assert(count == 2)
list_remove(&a, &nodes[0])
assert(list_first(&a) == &nodes[2] and list_last(&a) == &nodes[2])
list_node_remove(&nodes[2])
assert(list_is_empty(&a))
assert(not list_node_is_in_list(&nodes[2]))