dymokomi/luce-base
Source of release 0.41.0
0.41.0 / src / std / ownership / cycles.lucb
#==============================================================================================
#
# cycles - The cycle collector
#
# DESCRIPTION:
# A synchronous trial-deletion collector for reference cycles on the owning thread,
# run when the candidate set fills or at the end of a run. An object whose type is
# acyclic is never a candidate and never walked into: it cannot be part of a cycle,
# and every visitor skipping it keeps the trial counts balanced.
#
#==============================================================================================
# mark: The cycle collector ====================================================================
pub let candidate_limit: usize = 1024
local var roots: Object*[]
local var root_count: usize = 0
local var whites: Object*[]
local var white_count: usize = 0
local var collector_running: bool = false
## `LUCE_CYCLE_STRESS` in the environment: 0 not read yet, 1 absent, 2 present.
var stress_state: @u8
extern func stress_getenv as "getenv"(name: c.str) -> c.str?
## Whether `LUCE_CYCLE_STRESS` is set: the collector then runs at every new candidate, so a
## collection happens at every release that could leave a cycle, in `clear`, `remove`, a
## `deinit` and a failed `init` too (the stress mode of luce's tools/cycles_fuzz.py). The
## environment is read once; every thread reads the same answer.
func stressed() -> bool:
var state = stress_state.load(.relaxed)
if state == 0:
state = 2 if stress_getenv("LUCE_CYCLE_STRESS") != none else 1
stress_state.store(state, .relaxed)
return state == 2
func push_root(o: Object*):
if root_count == roots.length:
roots = grow(roots, root_count, candidate_limit)
roots[root_count] = o
root_count += 1
func push_white(o: Object*):
if white_count == whites.length:
whites = grow(whites, white_count, 256)
whites[white_count] = o
white_count += 1
func possible_root(o: Object*):
if color_of(o) != purple:
set_color(o, purple)
if not has(o, buffered):
o.flags |= buffered
push_root(o)
if (root_count >= candidate_limit or stressed()) and not collector_running:
collect()
## An object no walk enters: a literal, an acyclic one, or one `abandon` is dropping.
func skipped(child: Object*) -> bool:
return has(child, immortal) or child.info.acyclic or has(child, abandoning)
func visit_mark_gray(child: Object*, context: void*):
if skipped(child):
return
check_thread(child)
child.strong -= 1
mark_gray(child)
func mark_gray(o: Object*):
if color_of(o) != gray:
set_color(o, gray)
o.info.trace(o, visit_mark_gray, (void*)o)
func visit_scan(child: Object*, context: void*):
if skipped(child):
return
check_thread(child)
scan(child)
func visit_scan_black(child: Object*, context: void*):
if skipped(child):
return
check_thread(child)
child.strong += 1
if color_of(child) != black:
scan_black(child)
func scan(o: Object*):
if color_of(o) == gray:
if o.strong > 0:
scan_black(o)
else:
set_color(o, white)
o.info.trace(o, visit_scan, (void*)o)
func scan_black(o: Object*):
set_color(o, black)
o.info.trace(o, visit_scan_black, (void*)o)
func visit_gather(child: Object*, context: void*):
if skipped(child):
return
check_thread(child)
gather(child)
## The white objects, each once, flagged as being collected (`sort_whites` orders them).
func gather(o: Object*):
if color_of(o) == white and not has(o, collecting):
o.flags |= collecting
push_white(o)
o.info.trace(o, visit_gather, (void*)o)
## Undo the trial deletion of one edge out of a garbage object. `mark_gray` took one count
## for every edge it walked; `scan_black` gave back those out of objects found reachable, but
## an edge out of garbage is still missing, whether it points at more garbage or at a live
## object. Restoring every one lets each field release below be an ordinary release: a live
## object loses exactly the reference the garbage held, where it once lost two.
func visit_restore(child: Object*, context: void*):
if skipped(child):
return
check_thread(child)
child.strong += 1
## The garbage in the order its objects were made, oldest first (their generations): what a
## cycle's deinits and the releases of its fields follow, the same in a compiled program and
## Luce's interpreter whatever let go of what when (a heap sort, in place).
func sort_whites():
var start = white_count // 2
while start > 0:
start -= 1
sift_white(start, white_count)
var end = white_count
while end > 1:
end -= 1
let top = whites[0]
whites[0] = whites[end]
whites[end] = top
sift_white(0, end)
func sift_white(first: usize, end: usize):
var root = first
while root * 2 + 1 < end:
var child = root * 2 + 1
if child + 1 < end and whites[child + 1].generation > whites[child].generation:
child += 1
if whites[root].generation >= whites[child].generation:
return
let held = whites[root]
whites[root] = whites[child]
whites[child] = held
root = child
## Free the garbage: deinits first, then every object's fields, then the storage.
pub func collect():
if collector_running:
return
collector_running = true
# candidates still purple and alive stay; the rest leave the buffer
var kept: usize = 0
var i: usize = 0
while i < root_count:
let o = roots[i]
if color_of(o) == purple and o.strong > 0 and not has(o, dead):
roots[kept] = o
kept += 1
else:
o.flags &= ~buffered
release_shell(o)
i += 1
root_count = kept
i = 0
while i < root_count:
mark_gray(roots[i])
i += 1
i = 0
while i < root_count:
scan(roots[i])
i += 1
white_count = 0
i = 0
while i < root_count:
gather(roots[i])
i += 1
i = 0
while i < root_count:
roots[i].flags &= ~buffered
i += 1
root_count = 0
sort_whites()
# the counts the trial deletion took for the garbage's edges are restored, to garbage and
# to live objects alike, so that every field release below is an ordinary one; a release
# of a white object then only lowers its count
i = 0
while i < white_count:
whites[i].info.trace(whites[i], visit_restore, (void*)whites[i])
i += 1
i = 0
while i < white_count:
let o = whites[i]
if let f = o.info.finish:
let before = o.strong
o.strong += 1
f(o)
if o.strong > before + 1:
trap("`deinit` published `self`")
# Native disposal may release edges, including an edge to itself.
# Remove only the temporary finalizer reference, preserving those drops.
o.strong -= 1
i += 1
i = 0
while i < white_count:
whites[i].info.drop(whites[i])
i += 1
i = 0
while i < white_count:
let o = whites[i]
live -= 1
o.strong = 0
o.flags = dead
release_shell(o)
i += 1
white_count = 0
collector_running = false