dymokomi/luce-browser-foundation
Source of release 0.6.0
0.6.0 / src / gc / tests_stress.lucb
#==============================================================================================
#
# tests_stress - a mutating graph of cells and blobs under many collections
#
# DESCRIPTION:
# A root vector of slots holds cells; each cell owns a blob of bytes derived from its id
# and links to other cells. Random steps allocate, relink and drop cells, and every cell
# reachable from the slots is checked after each collection (live state, id, the bytes of
# its blob, its edges). The collect-on-every-allocation mode (DESIGN.md ยง3.4) runs the
# same steps with a collection before every allocation, cell and blob alike.
#
#==============================================================================================
# mark: The stress graph ========================================================================
## The slots of the stress graph: a RootVector on the C heap.
struct StressRoots:
var base: RootVectorBase
var slots: GcVector[TestCell*?]
let stress_roots_vtable: RootVectorBaseVTable = RootVectorBaseVTable(class_info = &root_vector_base_class, gather_roots = stress_roots_gather_roots_impl)
func stress_roots_gather_roots_impl(this: RootVectorBase*, roots: GcHashMap[HeapRoot]*):
let stress_roots = (StressRoots*)this
for slot in gc_vector_span(&stress_roots.slots):
if let cell = slot:
gc_hash_map_set(roots, (usize)cell, HeapRoot(type_ = HeapRootType.root_vector))
## The next value of a xorshift generator.
func next_random(state: u64*) -> u64:
var x = *state
x = x ^ (x << 13)
x = x ^ (x >> 7)
x = x ^ (x << 17)
*state = x
return x
## A cell with id `id` owning a blob of `size` bytes, byte i being (id + i) mod 256.
func new_stress_cell(heap: Heap*, id: i64, size: usize, atomic: bool) -> TestCell*:
let cell = new_test_cell(heap, id)
let blob = heap_allocate_blob(heap, size, 16, atomic) else trap("no blob")
for i in 0..<size:
blob[i] = (u8)((u64)id +% (u64)i)
cell.buffer = blob
return cell
## Check every cell reachable from the slots; answers how many there are.
noinline func check_stress_graph(roots: StressRoots*) -> usize:
var seen: GcHashMap[u8]
defer gc_hash_map_clear(&seen)
var work: GcVector[TestCell*]
defer gc_vector_clear(&work)
for slot in gc_vector_span(&roots.slots):
if let cell = slot:
gc_vector_append(&work, cell)
while not gc_vector_is_empty(&work):
let cell = gc_vector_take_last(&work)
if gc_hash_map_contains(&seen, (usize)cell):
continue
gc_hash_map_set(&seen, (usize)cell, 1)
assert(cell_state(cell.cell()) == CellState.live)
assert(cell.cell_base.vtable == &test_cell_vtable)
assert(cell.id > 0)
for i in 0..<cell.buffer.length:
assert(cell.buffer[i] == (u8)((u64)cell.id +% (u64)i))
if let left = cell.left:
gc_vector_append(&work, left)
if let right = cell.right:
gc_vector_append(&work, right)
return gc_hash_map_size(&seen)
## `steps` random steps over `slot_count` slots, collecting every `collect_every` steps. (The
## reference run: 60000 steps from seed 0x9E3779B97F4A7C15 make 35720 cells, 405 reachable at the
## end and the other 35315 finalized.)
noinline func run_stress(heap: Heap*, seed: u64, steps: usize, slot_count: usize, collect_every: usize):
let roots = (new StressRoots(base = RootVectorBase(vtable = &stress_roots_vtable, class_id = 0, m_heap = none, m_list_node = ListNode()), slots = GcVector[TestCell*?]()) in memory.heap) else trap("out of memory")
root_vector_base_construct(&roots.base, heap)
for _ in 0..<slot_count:
gc_vector_append(&roots.slots, none)
var state = seed
var next_id: i64 = 1
for step in 0..<steps:
let r = next_random(&state)
let slot = (usize)(r % (u64)slot_count)
let other = (usize)((r >> 20) % (u64)slot_count)
let slots = gc_vector_span(&roots.slots)
match (r >> 40) % 8:
0, 1, 2:
# a new cell in a slot, its blob small, medium or large
let size = (usize)(16 + (r >> 44) % 200) if (r >> 50) % 16 != 0 else (usize)(4000 + (r >> 44) % 30000)
let cell = new_stress_cell(heap, next_id, size, (r >> 55) % 2 == 0)
next_id += 1
cell.left = slots[other]
slots[slot] = cell
3:
# a new cell hung under an existing one
if let parent = slots[slot]:
let child = new_stress_cell(heap, next_id, (usize)(8 + (r >> 44) % 64), false)
next_id += 1
child.right = parent.right
parent.right = child
4:
# relink
if let cell = slots[slot]:
cell.left = slots[other]
5:
# drop a slot
slots[slot] = none
6:
# drop an edge
if let cell = slots[slot]:
cell.right = none
_:
# garbage: cells and blobs nothing keeps
_ = new_stress_cell(heap, next_id, (usize)(r >> 44) % 3000, true)
next_id += 1
if collect_every != 0 and step % collect_every == collect_every - 1:
heap_collect_garbage(heap)
_ = check_stress_graph(roots)
heap_collect_garbage(heap)
let reachable = check_stress_graph(roots)
# everything unreachable was collected, but for the odd stale word the stack may still hold
let made = (usize)(next_id - 1)
assert(finalized_count <= made - reachable)
assert(finalized_count + 8 >= made - reachable)
root_vector_base_destroy(&roots.base)
gc_vector_clear(&roots.slots)
free(roots) in memory.heap
# mark: Stress tests ============================================================================
test "stress: a mutating graph of cells and blobs survives many collections":
let heap = create_test_heap()
run_stress(heap, 0x9E3779B97F4A7C15, 60000, 256, 997)
destroy_test_heap(heap)
test "stress: collect on every allocation":
let heap = create_test_heap()
heap_set_should_collect_on_every_allocation(heap, true)
run_stress(heap, 12345, 1500, 32, 0)
heap_set_should_collect_on_every_allocation(heap, false)
destroy_test_heap(heap)
## A list of `count` Pairs made with `new` under `with heap`, collecting on every allocation;
## answers its head.
noinline func build_pair_list(heap: Heap*, count: i64) -> Pair*?:
var head: Pair*? = none
let view: memory.Allocator = heap
with view:
for i in 0..<count:
head = new Pair(first = i, second = head) else trap("no pair")
if i % 10 == 0:
var bytes = new u8[8] else trap("no bytes")
let sizes: usize[4] = [16, 100, 1000, 5000]
for size in sizes:
bytes = memory.grow(bytes, size) else trap("no growth")
bytes[size - 1] = (u8)(size % 256)
assert(bytes[4999] == (u8)(5000 % 256))
return head
test "stress: AK-style storage made with new and memory.grow under collections":
clobber_stack()
let heap = create_test_heap()
heap_set_should_collect_on_every_allocation(heap, true)
let head = build_pair_list(heap, 400)
heap_set_should_collect_on_every_allocation(heap, false)
heap_collect_garbage(heap)
var expected: i64 = 399
var node = head
while let pair = node:
assert(pair.first == expected)
expected -= 1
node = pair.second
assert(expected == -1)
destroy_test_heap(heap)