Out-of-bounds runtime write from the monotonic SNode id counter under runtime reuse (sibling of #814)

[duburcqa]

Summary

On the LLVM backends (CPU / CUDA / AMDGPU), reusing a long-lived runtime across many workloads without qd.reset() corrupts runtime memory once enough SNodes have been created. SNode::id is a process-global monotonic counter that is only reset when a Program is constructed; it is never recycled when SNode trees are destroyed. The runtime indexes several fixed-size, per-SNode arrays by that id with no bounds check, so once an id reaches quadrants_max_num_snodes (2048) the runtime writes a heap pointer past the array end into adjacent memory. The symptom depends on what gets clobbered: an IR-node type tag (an assertion in the scalarize pass, thrown on a compile-worker thread, aborts the process), a runtime pointer (a later kernel locks a std::mutex on a garbage this and crashes / hangs), or silent numerical corruption.

This is the same class of bug as #814, but a different counter and arrays: #814 was tree ids (recycled, limit 512, roots[]); this is SNode ids (monotonic, never recycled, limit 2048, element_lists[] / node_allocators[] / ambient_elements[]). #814's fix does not cover it.

Minimal reproduction (Quadrants only)

import quadrants as qd

qd.init(arch=qd.cpu)

# Each sparse (pointer) tree creates several SNodes. SNode ids are global, monotonic, and are NOT
# recycled when a tree is destroyed - only qd.reset() rewinds them. After ~2048 SNodes the runtime
# writes element_lists[snode_id] / node_allocators[snode_id] past their fixed [2048] arrays.
for i in range(60):  # ~60 * 53 SNodes crosses 2048
    fb = qd.FieldsBuilder()
    fields = [qd.field(qd.f32) for _ in range(50)]
    block = fb.pointer(qd.i, 4).dense(qd.i, 4)
    for f in fields:
        block.place(f)
    fb.finalize().destroy()  # destroying does NOT rewind the SNode counter
    print(i, flush=True)

On an unpatched build this performs an out-of-bounds write once the SNode ids cross 2048 (around i == 39). Whether it crashes or corrupts silently is heap-layout dependent (see below); either way the write is out of bounds. With the proposed fix it raises a clean RuntimeError at that point.

This is directly expressible as a unit test that fails on the unpatched tree and passes with the fix (verified - see Validation).

Root cause

SNode::id is a process-global monotonic counter:

// quadrants/ir/snode.h
static std::atomic<int> counter;
// quadrants/ir/snode.cpp
id = counter++;

It is reset only in the Program constructor (quadrants/program/program.cpp, SNode::counter = 0;), i.e. on qd.init() / a full reset - not by SNodeTree.destroy().

The LLVM runtime keeps per-SNode state in fixed arrays of quadrants_max_num_snodes (2048) entries indexed by SNode id (quadrants/runtime/llvm/runtime_module/llvm_runtime.h):

ListManager *element_lists[quadrants_max_num_snodes];
NodeManager *node_allocators[quadrants_max_num_snodes];
Ptr          ambient_elements[quadrants_max_num_snodes];

and writes them without any bounds check (quadrants/runtime/llvm/runtime_module/runtime.cpp):

// runtime_initialize_snodes, for non-all-dense trees:
for (int i = root_id; i < root_id + num_snodes; i++)
  runtime->element_lists[i] = runtime->create<ListManager>(...);
// runtime_NodeAllocator_initialize / runtime_allocate_ambient, per gc-able SNode:
runtime->node_allocators[snode_id] = runtime->create<NodeManager>(...);
runtime->ambient_elements[snode_id] = runtime->allocate_aligned(...);

root_id and the per-SNode ids are the global SNode::id (quadrants/runtime/program_impls/llvm/llvm_program.cpp: root_id = tree->root()->id;, snode_cache_data.id = snodes[i]->id;). Under reuse the counter climbs monotonically across workloads (verified: successive tree root ids 1, 303, 605, 907, 1209, ...). Once an id reaches 2048, element_lists[id] / node_allocators[id] write a live heap pointer past the arrays, into the following runtime fields and beyond into adjacent heap.

Why the symptom is flaky and layout-sensitive

The stray value is a valid heap pointer written to a heap-layout-dependent address:

• In a single isolated process the write often lands in a large mapped region and corrupts silently (no crash) - so a single-process run can look clean.
• Under concurrent compilation (num_compile_threads) and with the offline cache on, the allocation layout differs, so the pointer is more likely to land on a live structure that is then used - clobbering an IR node's type tag (assertion in scalarize_store_stmt, quadrants/transforms/scalarize.cpp, thrown on a compile-worker thread) or a runtime pointer (a from-kernel std::mutex::lock() on a garbage object). This matches the observed dependence on reuse + concurrency + offline cache, and the strong sensitivity to process address layout.

Validation (unit test that fails unpatched, passes patched)

@test_utils.test(arch=[qd.cpu, qd.cuda, qd.amdgpu], require=qd.extension.sparse)
def test_snode_id_count_limit_raises_not_corrupts():
    with pytest.raises(RuntimeError, match="maximum supported by the LLVM backend"):
        for _ in range(60):
            fb = qd.FieldsBuilder()
            fields = [qd.field(qd.f32) for _ in range(50)]
            block = fb.pointer(qd.i, 4).dense(qd.i, 4)
            for f in fields:
                block.place(f)
            tree = fb.finalize()
            tree.destroy()

Confirmed: on the current tree (no fix) this fails (DID NOT RAISE - the runtime silently performs the out-of-bounds write); with the fix below it passes. Restricted to LLVM backends (the fixed arrays are LLVM-runtime specific) and to sparse trees (all-dense trees skip every SNode-id-indexed write).

Proposed fix

Reject a materialization whose SNode ids would exceed quadrants_max_num_snodes, before the runtime performs the write. In LlvmRuntimeExecutor::initialize_llvm_runtime_snodes (quadrants/runtime/llvm/llvm_runtime_executor.cpp), after all_dense is computed:

// all_dense trees skip every snode-id-indexed write, so they are unaffected and not checked.
if (!all_dense) {
  int max_snode_id = root_id + (int)snode_metas.size() - 1;
  for (const auto &meta : snode_metas) {
    max_snode_id = std::max(max_snode_id, meta.id);
  }
  QD_ERROR_IF(max_snode_id >= quadrants_max_num_snodes,
              "The total number of SNodes created on this runtime exceeded the maximum supported by "
              "the LLVM backend ({}). SNode ids are not recycled when trees are destroyed; call "
              "qd.reset() to reset the runtime before creating more.",
              quadrants_max_num_snodes);
}

This converts the silent out-of-bounds write into a clear, catchable error. It does not reduce any capability that worked before: staying under 2048 is unaffected, and all-dense trees (which perform no SNode-id-indexed writes) are still allowed past 2048.

Note: this stops the corruption but does not enable long-lived reuse

Because SNode ids are never recycled, a reused runtime still hits the 2048 ceiling and now fails with a clean error instead of corrupting. Actually enabling long-lived reuse would need a follow-up: recycling SNode ids (and freeing their runtime array slots) when trees are destroyed, or making these arrays dynamically sized. That is a larger change (SNode ids thread through codegen and the offline cache) and is out of scope for this correctness fix.

Secondary robustness issue (separate, worth fixing)

When the corruption clobbers an IR node, the resulting QD_ERROR is thrown from a compile-worker thread. ParallelExecutor::worker_loop (quadrants/program/parallel_executor.cpp) calls task() with no surrounding try/catch, so the exception unwinds off the thread's top-level function and aborts the whole process (std::terminate) instead of surfacing catchably. Independent of the bug above, any compile-thread error is currently an unconditional crash; wrapping the task and propagating the exception to the waiting thread would make these surface as normal Python errors.

Relationship to other issues

Sibling of #814 (same "unbounded id indexes a fixed runtime array with no bounds check" defect, different counter/arrays). Related to #813 (both arise under runtime reuse without reset); the free_all_memory API discussed there does not help here, since destroying trees does not recycle SNode ids.

[duburcqa]

Correction on the framing above. Further investigation (dumping the IR at the crash site in a reuse run) showed the actual runtime-reuse crash is NOT this out-of-bounds write - it is a distinct scalarize compiler bug (tracked separately in #816): the scalarize pass asserts on a well-formed StoreStmt whose value is a cast_value<TensorType> of a scalar. The IR at the assert site was intact, not corrupted.

This issue still describes a real latent out-of-bounds write (the code writes element_lists[snode_id] past a fixed [2048] array with no bounds check, and the regression test confirms the bounds-check fix converts it into a clean error). But it was not the cause of the observed reuse crashes, and I have not confirmed it is reachable by any real workload. Treat it as defensive hardening of the same class as #814, not as the reuse-crash fix.