Figure 7 — PP250 Deterministic Garbage Collection
Four-phase Scan-Identify-Clear-Flip cycle with bidirectional G-bit. The G-bit is reset by both mLoad (read gate) and mSave (write gate) during normal operation, so reachable objects self-clear. GC is a safe Turing abstraction: atomic, hidden behind a Church-callable namespace entry, entered via CALL, exited via RETURN.
Four-Phase GC Cycle
1
SCAN — Walk Roots, Set G=1
Set G=1 on every namespace entry (mark all as garbage)
Walk all root GTs (CR8 thread identity, CR15 namespace root)
For each reachable entry: mLoad/mSave automatically clears G←0
Deterministic: bounded by namespace size, no tracing required
2
IDENTIFY — G=1 Means Unreachable
Scan namespace: any entry still G=1 was never accessed
No reachable code path touched it since SCAN set G=1
Therefore it is unreachable → safe to reclaim
Zero false positives: G-bit is cleared by actual access, not heuristics
3
CLEAR — Reclaim Unreachable
For each entry where G=1: invalidate the namespace slot
Bump version counter → all outstanding GTs to this entry become stale
Stale GTs fail mLoad validation (version mismatch) → FAULT
Memory freed atomically; no dangling references possible
4
FLIP — Bump Global Version
Increment the global version counter
All new GTs minted after FLIP carry the new version
Old-version GTs that survived are still valid (version match succeeds)
Cycle complete → return to Phase 1 on next GC invocation
next cycle
Bidirectional G-bit: mLoad + mSave
Both gates reset G←0 on every successful access, ensuring reachable entries self-clear during normal operation
mLoad (Read Gate)
1
Permission check (R/W/X/L/S/E)
2
Bounds → Version → MAC/Seal validation
G
G-bit Reset: entry.G ← 0
"I accessed this entry → it is reachable"
4
CR Write → Thread Shadow
mSave (Write Gate)
1
Version match → Seal validation
2
Target bounds → B-bit → F-bit check
G
G-bit Reset: entry.G ← 0
"I saved to this entry → it is reachable"
4
Seal recompute → Commit
G
GC as a Safe Turing Abstraction
Church Interface
Namespace entry "GC" → callable via CALL with E permission → returns via RETURN
Turing Implementation (hidden)
Atomic: Scan → Identify → Clear → Flip (no interleaving, no preemption)
G-bit Lifecycle
SCAN sets G=1
all entries marked
as "garbage"
Normal Operation
mLoad/mSave clear
G←0 on access
IDENTIFY G=1
still G=1 → never
accessed → garbage
CLEAR + FLIP
reclaim slot
bump version
Phase 2: Identify (G=1 = unreachable)
Phase 4: Flip (bump version)
G-bit reset (bidirectional)