urt-rs / docs /research /LEAF_METADATA.md

Recover leaf metadata loops and query output contracts

f8c1da5 30 days ago

7.29 kB

# Leaf areas, cluster accumulation and query output contracts

Static/bounded pass, 2026-10-11. Reproduce with `python3 scripts/analyze_leaf_metadata.py`; check with `python3 scripts/test_leaf_metadata.py`. [Generated evidence](leaf-metadata.json) verifies both Linux ELF64 originals/disassemblies and retains five graphs per engine. It records **208 metadata compositions, sixty guarded accessor probes and 72 leaf-store probes**. This extends [bound/query-return evidence](LINK_BOUNDS.md).

Every CM_LeafArea/CM_LeafCluster return is supplied, and diagnostic blocks are skipped with explicit post-call continuation. No original process, BSP traversal or native callee executes. Metadata slices stop before placement/cleanup. Accessor probes explicitly replace their RBX PUSH/POP with NOPs, retaining original instruction addresses; stack traffic and frame unwinding are excluded, and error calls/returns are stopped. Actual maps, ABI clobbers/lifetimes and runtime/platform conformance remain open.

## META-001: two area slots and diagnostic gating

The area loop visits all supplied leaves before starting cluster accumulation. It ignores returned area -1. A qualifying area writes server record +0x128 when that slot is -1 or already equal to the new area. Other areas write +0x12c. Thus the first qualifying area stays in the first slot, while a later distinct area can replace the second slot; this is not a set of every touched area.

When the second slot is neither -1 nor the incoming area, the native global word at the base of `sv` is compared with **one**. Equality requests Com_DPrintf before the second slot is replaced; other sampled global values skip the diagnostic. The report preserves the original diagnostic text. That raw state-word predicate does not establish a complete named server-state contract, rendered output or permission policy.
Each engine has 104 compositions: leaf counts 0–8, 15, 16, 17 and 128, four supplied return patterns (all absent, repeated IDs, mixed -1/repeated/distinct IDs, and unique IDs), and state word 0/1. Original unrolled instructions are followed between each stopped service/diagnostic boundary. All eight observed area-call lanes are exercised. Call requests retain leaf identity, supplied return and native address; traces through count three are retained in full, larger traces have deterministic hashes/instruction counts.
Independent fixtures verify slot replacement, repeated first/second values, diagnostic counts, complete area visitation and paired engine outputs. Actual leaf enumeration order, area connectivity and metadata consumers remain open.
## META-002: cluster append, duplicates and capacity fallback
The cluster phase skips only return -1 in the tested sequences. Other IDs are appended at record +0xe4 +4*old_count, and count at +0xe0 increments. Duplicates remain: sixteen repeated sevens produce sixteen entries, not a single unique cluster.

After storing/incrementing, **new count ==16** requests CM_LeafCluster for the extra output word from the bound query; its supplied return is stored at +0x124 before placement. The sixteen stored entries remain intact and count stays sixteen. This occurs even when the sixteenth qualifying entry is also the final leaf. Remaining cluster calls are skipped, while the preceding area phase has already visited every supplied leaf. Fewer qualifying clusters keep the initialized fallback word zero.
All observed normal cluster-call lanes and the fallback call are exercised. Fixtures verify source visitation order, -1 filtering, duplicate preservation, sixteen-entry canaries/unwritten markers, exact fallback timing and all-area-before-cluster ordering. Here the extra word is supplied as leaf 1000 and fallback return as 777, not produced by actual geometry. The earlier signed-negative-count path remains a separate supplied-return slice; normal leaf-query count ownership is addressed below.
## META-003: guarded leaf access and actual store callback
CM_LeafArea and CM_LeafCluster each reject signed-negative index or index >= native leaf count by requesting Com_Error with code one and respectively `CM_LeafArea: bad number` / `CM_LeafCluster: bad number`. The probes stop before that error call; they do not infer recovery or nonreturn behavior.

Valid accesses share the same native leaf-array pointer/count globals and use a **24-byte native leaf stride**. Cluster reads record +0, area reads +4. This is the shipped native representation, not automatically the BSP on-disk record stride. Fifteen cases per accessor/engine combine native counts 0/1/3 with indices -1/0/1/2/3 and distinct synthetic field values. PUSH/POP omission is recorded explicitly in the report; error arguments and indexed reads are still evaluated from original instructions.

CM_BoxLeafnums installs **CM_StoreLeafs** as its leaf callback; the collector verifies that immediate function pointer against the decoded callback entry. CM_StoreLeafs complements the supplied negative child encoding to obtain leaf index. It reads that leaf's cluster through the same 24-byte representation, then:

- If cluster !=-1, it writes leaf index to list record +48 **before** testing capacity.
- If signed count < capacity, it appends the leaf index to output +4*count and increments count. Leaves with cluster -1 are still appended.
- Otherwise it sets overflow word +8 to one, leaves count unchanged and performs no output write. The latest leaf with cluster != -1 can still update +48 when capacity is full.
The callback reads its leaf directly, without using the guarded accessors; index provenance and tree bounds remain open. Thirty-six callback probes per engine cover three indices, cluster -1/7 and capacity boundaries 0/1/2/128. The wrapper initializes count/overflow/+48 to zero, and its retained return path reads count into EAX and writes +48 through the extra pointer. It does not return the overflow word as a negative count. Consequently the extra output is a retained leaf index, not a tree-node pointer. Under supplied valid initial count/capacity and these callback rules, count stays nonnegative and bounded; complete traversal/mutation ownership still needs verification. The previous negative EAX fixtures tested a caller branch, not an observed normal query return.
## Reproduction and remaining work
The evaluator adds signed JL/JS with separately modeled comparison/sign predicates, NOTL preserving flags, and NOPL/NOPW handling. Signed branches after unmodeled arithmetic fail closed; tests cover comparison overflow cases and unknown calls/registers. Accessor stack omission and diagnostic/callee-return injection remain explicit limitations.
Eight tests check independent area/cluster/guard/store oracles, all unrolled service-site coverage, paired outputs and failure domains. For Rust, specify stable leaf ordering, area-slot replacement rather than set accumulation, cluster duplicates/overflow timing, and the distinct count/overflow/last-leaf outputs. RE-316 tracks full BSP traversal/plane predicates, leaf-array loading/layout/ownership, actual output bounds and diagnostics/state lifecycle, metadata/PVS/snapshot consumers, complete query/collision fixtures and original-runtime/all-platform conformance. Broad collision and port tasks remain open.

	# Leaf areas, cluster accumulation and query output contracts

	Static/bounded pass, 2026-10-11. Reproduce with `python3 scripts/analyze_leaf_metadata.py`; check with `python3 scripts/test_leaf_metadata.py`. [Generated evidence](leaf-metadata.json) verifies both Linux ELF64 originals/disassemblies and retains five graphs per engine. It records 208 metadata compositions, sixty guarded accessor probes and 72 leaf-store probes. This extends [bound/query-return evidence](LINK_BOUNDS.md).

	Every CM_LeafArea/CM_LeafCluster return is supplied, and diagnostic blocks are skipped with explicit post-call continuation. No original process, BSP traversal or native callee executes. Metadata slices stop before placement/cleanup. Accessor probes explicitly replace their RBX PUSH/POP with NOPs, retaining original instruction addresses; stack traffic and frame unwinding are excluded, and error calls/returns are stopped. Actual maps, ABI clobbers/lifetimes and runtime/platform conformance remain open.

	## META-001: two area slots and diagnostic gating

	The area loop visits all supplied leaves before starting cluster accumulation. It ignores returned area -1. A qualifying area writes server record +0x128 when that slot is -1 or already equal to the new area. Other areas write +0x12c. Thus the first qualifying area stays in the first slot, while a later distinct area can replace the second slot; this is not a set of every touched area.

	When the second slot is neither -1 nor the incoming area, the native global word at the base of `sv` is compared with one. Equality requests Com_DPrintf before the second slot is replaced; other sampled global values skip the diagnostic. The report preserves the original diagnostic text. That raw state-word predicate does not establish a complete named server-state contract, rendered output or permission policy.

	Each engine has 104 compositions: leaf counts 0–8, 15, 16, 17 and 128, four supplied return patterns (all absent, repeated IDs, mixed -1/repeated/distinct IDs, and unique IDs), and state word 0/1. Original unrolled instructions are followed between each stopped service/diagnostic boundary. All eight observed area-call lanes are exercised. Call requests retain leaf identity, supplied return and native address; traces through count three are retained in full, larger traces have deterministic hashes/instruction counts.

	Independent fixtures verify slot replacement, repeated first/second values, diagnostic counts, complete area visitation and paired engine outputs. Actual leaf enumeration order, area connectivity and metadata consumers remain open.

	## META-002: cluster append, duplicates and capacity fallback

	The cluster phase skips only return -1 in the tested sequences. Other IDs are appended at record +0xe4 +4*old_count, and count at +0xe0 increments. Duplicates remain: sixteen repeated sevens produce sixteen entries, not a single unique cluster.

	After storing/incrementing, new count ==16 requests CM_LeafCluster for the extra output word from the bound query; its supplied return is stored at +0x124 before placement. The sixteen stored entries remain intact and count stays sixteen. This occurs even when the sixteenth qualifying entry is also the final leaf. Remaining cluster calls are skipped, while the preceding area phase has already visited every supplied leaf. Fewer qualifying clusters keep the initialized fallback word zero.

	All observed normal cluster-call lanes and the fallback call are exercised. Fixtures verify source visitation order, -1 filtering, duplicate preservation, sixteen-entry canaries/unwritten markers, exact fallback timing and all-area-before-cluster ordering. Here the extra word is supplied as leaf 1000 and fallback return as 777, not produced by actual geometry. The earlier signed-negative-count path remains a separate supplied-return slice; normal leaf-query count ownership is addressed below.

	## META-003: guarded leaf access and actual store callback

	CM_LeafArea and CM_LeafCluster each reject signed-negative index or index >= native leaf count by requesting Com_Error with code one and respectively `CM_LeafArea: bad number` / `CM_LeafCluster: bad number`. The probes stop before that error call; they do not infer recovery or nonreturn behavior.

	Valid accesses share the same native leaf-array pointer/count globals and use a 24-byte native leaf stride. Cluster reads record +0, area reads +4. This is the shipped native representation, not automatically the BSP on-disk record stride. Fifteen cases per accessor/engine combine native counts 0/1/3 with indices -1/0/1/2/3 and distinct synthetic field values. PUSH/POP omission is recorded explicitly in the report; error arguments and indexed reads are still evaluated from original instructions.

	CM_BoxLeafnums installs CM_StoreLeafs as its leaf callback; the collector verifies that immediate function pointer against the decoded callback entry. CM_StoreLeafs complements the supplied negative child encoding to obtain leaf index. It reads that leaf's cluster through the same 24-byte representation, then:

	- If cluster !=-1, it writes leaf index to list record +48 before testing capacity.
	- If signed count < capacity, it appends the leaf index to output +4*count and increments count. Leaves with cluster -1 are still appended.
	- Otherwise it sets overflow word +8 to one, leaves count unchanged and performs no output write. The latest leaf with cluster != -1 can still update +48 when capacity is full.

	The callback reads its leaf directly, without using the guarded accessors; index provenance and tree bounds remain open. Thirty-six callback probes per engine cover three indices, cluster -1/7 and capacity boundaries 0/1/2/128. The wrapper initializes count/overflow/+48 to zero, and its retained return path reads count into EAX and writes +48 through the extra pointer. It does not return the overflow word as a negative count. Consequently the extra output is a retained leaf index, not a tree-node pointer. Under supplied valid initial count/capacity and these callback rules, count stays nonnegative and bounded; complete traversal/mutation ownership still needs verification. The previous negative EAX fixtures tested a caller branch, not an observed normal query return.

	## Reproduction and remaining work

	The evaluator adds signed JL/JS with separately modeled comparison/sign predicates, NOTL preserving flags, and NOPL/NOPW handling. Signed branches after unmodeled arithmetic fail closed; tests cover comparison overflow cases and unknown calls/registers. Accessor stack omission and diagnostic/callee-return injection remain explicit limitations.

	Eight tests check independent area/cluster/guard/store oracles, all unrolled service-site coverage, paired outputs and failure domains. For Rust, specify stable leaf ordering, area-slot replacement rather than set accumulation, cluster duplicates/overflow timing, and the distinct count/overflow/last-leaf outputs. RE-316 tracks full BSP traversal/plane predicates, leaf-array loading/layout/ownership, actual output bounds and diagnostics/state lifecycle, metadata/PVS/snapshot consumers, complete query/collision fixtures and original-runtime/all-platform conformance. Broad collision and port tasks remain open.