Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.44.0

0.44.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