dymokomi/luce-base
Source of release 0.43.0
0.43.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 at a release of the value language's, explicitly,
# or at the end of a run; never at a release through a native handle (`release_held`). 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 disposals: Object*[]
local var disposal_count: usize = 0
local var collector_running: bool = false
## The candidate count at which a release that may not collect drops the candidates that
## are no longer purple or alive (`purge_roots`), so the buffer grows only with live ones.
local var purge_at: usize = 0
## `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 of a
## release that may collect, so a collection happens at every such 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
## The disposal order lists some of the garbage, so its buffer grows with the garbage's: a
## collection allocates only when the garbage outgrows what came before.
func push_white(o: Object*):
if white_count == whites.length:
whites = grow(whites, white_count, 256)
disposals = grow(disposals, 0, 256)
whites[white_count] = o
white_count += 1
## `o`, released and still held, may be a cycle's root. When the candidates fill, a release
## of the value language's collects (`may_collect`). A release through a native handle never
## does: native code may still hold a traced field whose edge it has just released, as in
## `old.release()` before `self.field = next`, and a collection would take that edge away a
## second time. Its candidates wait for the next release that may collect, or a `collect`.
func possible_root(o: Object*, may_collect: bool):
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:
if may_collect:
collect()
elif root_count >= purge_at:
purge_roots()
purge_at = candidate_limit if root_count * 2 < candidate_limit else root_count * 2
## A point where no native code is midway through replacing a traced field, such as the top
## of an event loop's turn: collects when releases through native handles filled the
## candidates (`possible_root`), which they never collect themselves.
pub func safe_point():
if root_count >= candidate_limit and not collector_running:
collect()
## Drop the candidates that are no longer purple or no longer alive, freeing the storage of
## the dead: it touches no object's fields, so any release may.
func purge_roots():
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
## 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
func push_disposal(o: Object*):
disposals[disposal_count] = o
disposal_count += 1
func visit_order(child: Object*, context: void*):
if skipped(child):
return
order_from(child)
## A depth-first walk of the garbage that lists each disposing object after every one it
## reaches: read backwards, an object is disposed before what it refers to.
func order_from(o: Object*):
if not has(o, collecting) or has(o, ordered):
return
o.flags |= ordered
o.info.trace(o, visit_order, (void*)o)
if o.info.disposes:
push_disposal(o)
## The order the garbage's native objects are disposed in, after every `deinit` has run:
## each before the objects it refers to, as releasing the garbage one reference at a time
## would, so a close that reaches into what it holds finds it open. A cycle has no first
## object, and the walk treats the edge back to an object it is still inside as the one
## released last. It starts at the objects that do not dispose, oldest first, then the
## rest: a native object's references own what they reach, while a cycle is closed by the
## value language's objects and closures, so the walk enters it there.
func order_disposal():
disposal_count = 0
var i: usize = 0
while i < white_count:
if not whites[i].info.disposes:
order_from(whites[i])
i += 1
i = 0
while i < white_count:
order_from(whites[i])
i += 1
func run_finish(o: Object*):
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
## 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 the native objects' disposals, then every object's
## fields, then the storage.
pub func collect():
if collector_running:
return
collector_running = true
purge_at = candidate_limit
# candidates still purple and alive stay; the rest leave the buffer
purge_roots()
var i: usize = 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
# the order is taken before any finish runs, over the garbage as it was found
order_disposal()
i = 0
while i < white_count:
if not whites[i].info.disposes:
run_finish(whites[i])
i += 1
i = disposal_count
while i > 0:
i -= 1
run_finish(disposals[i])
disposal_count = 0
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