mirror of
https://github.com/fluffos/fluffos
synced 2026-08-12 18:26:06 -04:00
86d13cdb83
A complete treatment of reference loops (cyclic data structures) in LPC:
the reference-counting VM has no cycle collector, so a value that reaches
itself leaks permanently -- and silently -- once the last outside
reference is dropped, and it cannot be saved, deep-copied, or fully
printed in the meantime. This change documents the problem, fixes a
driver memory-safety bug it exposes, and adds runtime tooling to detect,
locate, break, and (on debug builds) collect such loops.
Driver fixes:
- copy() on a cyclic structure always hits the MAX_SAVE_SVALUE_DEPTH
error(), and that unwind path leaked every partially-built container --
allocated with the _empty_ (uninitialized-svalue) allocators and holding
a borrowed, un-ref-counted pointer to the ORIGINAL value, which the
Debug memory checker then read after free (heap-use-after-free abort
under ASan, reproducible with just catch(copy(a)) on a[0] = a).
deep_copy_* now allocate zero-filled, hold the destination in a
unique_ptr whose deleter is the tag-symmetric free_*, and only write the
destination slot after the child copy fully succeeded (ffi.cc precedent,
AGENTS.md section 4).
- save_object/save_variable and copy()'s 'nested too deep' errors -- the
classic symptom of a loop -- now say so (the has_cycle() pointer is
gated on PACKAGE_CONTRIB so core never recommends an efun the build
lacks).
New efuns (contrib package, src/packages/contrib/cycles.cc):
- has_cycle(mixed): 1 if the value's reference graph contains a loop.
- find_cycles(mixed): one index-path string per loop-closing slot
("[3][\"peer\"].1" style).
- break_cycles(mixed): clears every loop in place and returns the number
of edges broken. Exactly the DFS back-edges are touched (a digraph is
acyclic iff its DFS has no back-edges): item/value slots are zeroed, a
loop closed in mapping-KEY position has its node deleted (hashed keys
cannot be overwritten), and a loop closing on the funptr->args edge
itself -- possible because bind() SHARES the args array between the old
and new funptr -- detaches the bound funptr's args list and replaces it
with a zero-filled one of the same size. DAG sharing is never touched;
one cut un-loops a whole ring; afterwards the value saves, copies,
prints, and frees normally.
All three share one ITERATIVE walk (explicit heap stack, white/grey/
black coloring): no C-stack recursion, no depth cap -- arbitrarily deep
acyclic values scan cleanly where save_variable() errors. Edges:
array/class items, mapping keys AND values, fp->hdr.args; objects are
deliberately leaves (loops through object variables are the
destruct()-managed kind: destruct2() zeroes the variable block).
break_cycles() records fixes during a mutation-free walk and applies
them in a post-pass that holds a reference on every touched container,
zeroes slots before deleting nodes (only node deletion can cascade
frees), and releases the holds last -- order-independent and safe
against shared/overlapping fixes.
Orphaned-loop collector (develop package, Debug/DEBUGMALLOC_EXTENSIONS):
- find_orphaned_cycles(int collect): finds -- and with any nonzero
argument reclaims -- data blocks that are unreachable because only a
reference loop keeps them alive: the case nothing LPC-level can reach
anymore. Detection is trial deletion (CPython-gc-style), implemented in
md_scan_orphaned_cycles (checkmemory.cc): count each array/class/
mapping/funptr's references held by OTHER data blocks; a block whose
real ref count exceeds that is externally held (object variables, VM
stack, call_out, any C++-side holder) and seeds liveness, which
propagates along data edges; the remainder is loop garbage. No root
enumeration to get wrong -- every legitimate holder shows up as an
external ref. Collection: hold a ref on every dead block, sever all
their child slots (releasing strings/objects/buffers/live values
normally), then release the holds -- each dead block deallocates with
nothing left to cascade into.
- check_all_blocks() runs the same scan (skippable via new flag bit 2,
value 4) and reports 'unreachable data block(s) kept alive only by
reference loop(s)', so the testsuite's per-file check_memory() gate
turns a dropped cycle into a hard, attributed failure. That immediately
caught a real pre-existing leak: tests/std/json.lpc's
test_encode_circular_references() dropped all four of its
deliberately-cyclic fixtures on every suite run since it was written.
Tests (testsuite/single/tests/):
- operators/reference_loop.lpc pins the driver contract around loops and
crashes the unfixed Debug/ASan driver (the copy() unwind UAF).
- efuns/has_cycle.lpc, find_cycles.lpc, break_cycles.lpc cover self/
mutual/ring loops across arrays, mappings (value and key position),
classes, funptr args (including the bind()-shared-args case, which was
unbreakable in an earlier revision of this change), DAG-sharing
preservation, save/copy working again after a break, idempotency, and a
5000-deep acyclic walk.
- efuns/find_orphaned_cycles.lpc pins baseline-relative detection of 6
orphans across three dropped loop shapes, idempotent detection, that
reachable loops are never classified as garbage, and that collection
reclaims everything while reachable data survives.
- Every cycle-building test has UNCONDITIONAL teardown (body in catch(),
find_orphaned_cycles(1) regardless, error re-raised) so a mid-test
regression stays one [ FAILED ] entry instead of cascading the
harness's LEAK gate into a suite-wide abort (AGENTS.md section 7).
Docs (Docusaurus, sidebar regenerated; full two-locale build verified):
- new concepts page docs/concepts/general/reference_loops.md: why loops
leak, what each recursive consumer does, the destruct() exception,
prevention patterns, the runtime tools, and the debug-build collector;
- efun pages for all four new efuns; check_memory.md documents the new
scan and flag bit.
Validated on Debug+ASan/UBSan (full LPC suite, randomized order, multiple
runs) and RelWithDebInfo (full suite), 313 GTest unit tests, plus an
8-angle adversarially-verified self-review.
Round-2 self-review (4 fresh angles, adversarially verified) additionally:
- break_cycles() post-pass releases its held container references via an
RAII guard: allocate_array() there can error() (set_config() can shrink
__MAX_ARRAY_SIZE__ at runtime below a shared args array's size), and the
old trailing release loop would have leaked every held ref on that
unwind (AGENTS.md section 4).
- documented the pre-existing map_delete()-class caveat: deleting a
key-closed loop's node while an outer unlocked foreach-ref variable is
aimed at it dangles that variable (not specific to this efun; noted in
code and doc).
- extended orphan-collector coverage from 6 to 10 blocks: class rings
(TAG_CLASS candidate/sever/free_class paths), mapping pairs closed in
KEY position (the collector's in-place key-zeroing sever path), and a
buffer payload riding an orphaned ring (sever must release it or the
Debug ref gate trips); added a destructed-object-in-walked-value test
(render_key + leaf handling).
- docs: refs.md and copy.md now link back to the cycle tooling; zh-CN
sidebar translation keys rescaffolded; AGENTS.md section 7 documents the
new hard gate and the catch + find_orphaned_cycles(1) teardown pattern.
- re-entrancy audit (foreach/MAP_LOCKED/locked_map_nodes/merge_arg_lists)
and LPC-test-semantics audit returned no code defects.
Claude-Session: https://claude.ai/code/session_01VaksxbPjc3hjzghoQPUHRo
Co-authored-by: Claude <noreply@anthropic.com>
|
||
|---|---|---|
| .. | ||
| general | ||