vm: releasing a long persistent node chain recurses per node and overflows the stack

orion commented

2026-10-08 15:17:18 +00:00

Collaborator

Finding

Found by the loop worker for #199 (PR #203): dropping a BankersQueue with about 50,000 items segfaults in the VM, because release recurses once per node. The same shape applies to any persistent linked structure (ConsStack, #198). The limitation is documented on the type; benchmark and conformance sizes stay below it.

Goal

Release of long single-owner node chains runs iteratively (or with bounded stack), in the VM and the native backend.

## Finding Found by the loop worker for #199 (PR https://git.torb.dev/torbscript/language/pulls/203): dropping a `BankersQueue` with about 50,000 items segfaults in the VM, because release recurses once per node. The same shape applies to any persistent linked structure (`ConsStack`, #198). The limitation is documented on the type; benchmark and conformance sizes stay below it. ## Goal Release of long single-owner node chains runs iteratively (or with bounded stack), in the VM and the native backend. ## Next Refine: reproduce on main in VM and native, check whether the native backend has the same recursion, pick the mechanism, write acceptance criteria. Seed impact unknown until refined.

orion added the

loop

label

2026-10-08 15:17:18 +00:00

orion commented

2026-10-08 16:39:08 +00:00

Author

Collaborator

[loop:torbscript] intake: in scope (finding from the loop worker of PR #203, author orion, label loop), no duplicate among the open issues, no collision with a design record seen at triage; a VM and native release defect on long node chains, seed impact unknown until refined, next: refine (queued behind the ready buffer, waiting until the buffer drops below 4 ready issues)

[loop:torbscript] intake: in scope (finding from the loop worker of PR #203, author orion, label `loop`), no duplicate among the open issues, no collision with a design record seen at triage; a VM and native release defect on long node chains, seed impact unknown until refined, next: refine (queued behind the ready buffer, waiting until the buffer drops below 4 `ready` issues)

orion commented

2026-10-08 16:48:14 +00:00

Author

Collaborator

[loop:torbscript] refine: held back, the ready buffer is above its target of 4 ready issues, next: waiting (ready buffer full)

[loop:torbscript] refine: held back, the ready buffer is above its target of 4 `ready` issues, next: waiting (ready buffer full)

orion commented

2026-10-12 11:05:55 +00:00

Author

Collaborator

[loop:torbscript] claim refine by session:loop-torbscript-20261012 until 2026-10-12T13:05Z

orion commented

2026-10-12 11:06:49 +00:00

Author

Collaborator

[loop:torbscript] decided by the loop: mechanism and scope.

Finding (read from source; no local build per the contract, CI will confirm). Release is recursive in two places that share one shape: the C runtime's torb_release (runtime/memory.c) calls the type's drop function, which releases its child via torb_release again (emitted by emitDropHelper, compiler/src/backend/c/body.trb), and the VM kernel's torb_machine_release_block -> torb_machine_release_value -> torb_machine_release_word -> torb_machine_release_block (runtime/machine.c). So VM and native are both affected, at one node per few C frames. ConsStack and BankersQueue nodes (std/collections/src/queue.trb) are the known cases.

Decision: a bounded-depth release with a per-thread deferred list, in the runtime only. A thread-local release depth counter is kept by torb_release and by torb_machine_release_block. Below a fixed bound (256 nested releases) behaviour is unchanged, including the depth-first order of close() calls (docs/design/VM.md section 7, docs/design/DESTRUCTORS.md section 2a). At the bound, a block whose last count was just dropped is pushed with its drop function onto a per-thread pending vector instead of being dropped inline; the outermost release drains the vector (LIFO) until empty, so stack use is O(bound) however long the chain. Alternatives rejected: rewriting the nodes' drop in TorbScript (needs per-type code, cannot cover user-defined chains or the VM mirror), pointer reversal (needs spare words in every shape), a global free-list (breaks per-thread heaps and shared blocks).
Consequences, accepted: only chains deeper than the bound change the relative order of nested drops, and nothing but a close() could observe it, which in a node chain of 256+ nested levels is not a contract anyone can rely on; shared (TORB_SHARED_COUNT) blocks keep the atomic path and are deferred on the thread that took the last count.

Seed impact: none. runtime/ and the VM kernel change only; no syntax, no new native name the compiler looks up, no driver flag, no std name looked up by string. No two-commit rule needed.

Design link: docs/design/VM.md section 7 (releases and destructors, depth-first order), docs/design/DESTRUCTORS.md section 2a, docs/design/COLLECTIONS.md (ConsStack/BankersQueue, C7/C8); ROADMAP row "collections" (milestone 10). The doc limitation on BankersQueue (queue.trb, "Releasing a queue releases its nodes one inside the next ...") is removed by this issue.

Acceptance criteria

torb run (VM) and torb run --native release a BankersQueue<Int> of 1,000,000 items, and a ConsStack<Int> of 1,000,000 items, without a stack overflow or segfault, with the same output both ways.
New conformance test tests/conformance/release-long-chain.trb (+ .expected, .allocations) builds both chains, drops them (scope end and reassignment), and prints counts; it runs in tier B in both VM and native, and the live-block leak gate shows zero blocks left.
A short-chain test keeps today's order: an existing destructor-order conformance test stays green unchanged (chains under the bound are not deferred).
A chain with a shared tail (two queues sharing nodes) frees each node exactly once (conformance covers: drop one version, the other stays intact, then drop it).
The limitation paragraph on BankersQueue (and any equivalent on ConsStack) is removed from std/collections/src/queue.trb and the docs; torb docs skill docs skills regenerated and committed.
sh tools/gates.sh a and b green in forge CI (touches runtime/, so tier B applies).

Size: one PR, two Conventional Commits: fix(runtime): release deep node chains iteratively (runtime + VM kernel + test) and docs(collections): drop the deep-release limitation (docs/skills). Implementer: opus/high (runtime).

[loop:torbscript] decided by the loop: mechanism and scope. **Finding (read from source; no local build per the contract, CI will confirm).** Release is recursive in two places that share one shape: the C runtime's `torb_release` (`runtime/memory.c`) calls the type's drop function, which releases its child via `torb_release` again (emitted by `emitDropHelper`, `compiler/src/backend/c/body.trb`), and the VM kernel's `torb_machine_release_block` -> `torb_machine_release_value` -> `torb_machine_release_word` -> `torb_machine_release_block` (`runtime/machine.c`). So VM and native are both affected, at one node per few C frames. `ConsStack` and `BankersQueue` nodes (`std/collections/src/queue.trb`) are the known cases. **Decision: a bounded-depth release with a per-thread deferred list, in the runtime only.** A thread-local release depth counter is kept by `torb_release` and by `torb_machine_release_block`. Below a fixed bound (256 nested releases) behaviour is unchanged, including the depth-first order of `close()` calls (`docs/design/VM.md` section 7, `docs/design/DESTRUCTORS.md` section 2a). At the bound, a block whose last count was just dropped is pushed with its drop function onto a per-thread pending vector instead of being dropped inline; the outermost release drains the vector (LIFO) until empty, so stack use is O(bound) however long the chain. Alternatives rejected: rewriting the nodes' drop in TorbScript (needs per-type code, cannot cover user-defined chains or the VM mirror), pointer reversal (needs spare words in every shape), a global free-list (breaks per-thread heaps and shared blocks). Consequences, accepted: only chains deeper than the bound change the relative order of nested drops, and nothing but a `close()` could observe it, which in a node chain of 256+ nested levels is not a contract anyone can rely on; shared (`TORB_SHARED_COUNT`) blocks keep the atomic path and are deferred on the thread that took the last count. **Seed impact: none.** `runtime/` and the VM kernel change only; no syntax, no new native name the compiler looks up, no driver flag, no std name looked up by string. No two-commit rule needed. **Design link:** `docs/design/VM.md` section 7 (releases and destructors, depth-first order), `docs/design/DESTRUCTORS.md` section 2a, `docs/design/COLLECTIONS.md` (ConsStack/BankersQueue, C7/C8); ROADMAP row "collections" (milestone 10). The doc limitation on `BankersQueue` (`queue.trb`, "Releasing a queue releases its nodes one inside the next ...") is removed by this issue. **Acceptance criteria** 1. `torb run` (VM) and `torb run --native` release a `BankersQueue<Int>` of 1,000,000 items, and a `ConsStack<Int>` of 1,000,000 items, without a stack overflow or segfault, with the same output both ways. 2. New conformance test `tests/conformance/release-long-chain.trb` (+ `.expected`, `.allocations`) builds both chains, drops them (scope end and reassignment), and prints counts; it runs in tier B in both VM and native, and the live-block leak gate shows zero blocks left. 3. A short-chain test keeps today's order: an existing destructor-order conformance test stays green unchanged (chains under the bound are not deferred). 4. A chain with a shared tail (two queues sharing nodes) frees each node exactly once (conformance covers: drop one version, the other stays intact, then drop it). 5. The limitation paragraph on `BankersQueue` (and any equivalent on `ConsStack`) is removed from `std/collections/src/queue.trb` and the docs; `torb docs skill docs skills` regenerated and committed. 6. `sh tools/gates.sh a` and `b` green in forge CI (touches `runtime/`, so tier B applies). **Size:** one PR, two Conventional Commits: `fix(runtime): release deep node chains iteratively` (runtime + VM kernel + test) and `docs(collections): drop the deep-release limitation` (docs/skills). Implementer: opus/high (runtime).

orion added the

ready

label

2026-10-12 11:06:52 +00:00

orion commented

2026-10-12 11:06:52 +00:00

Author

Collaborator

[loop:torbscript] refine: ready (goal, 6 testable acceptance criteria incl. regression conformance test, design links, seed impact none, one PR with two commits), next: implement. Worker usage: about 60k tokens (sonnet).

orion commented

2026-10-12 11:07:44 +00:00

Author

Collaborator

[loop:torbscript] claim implement by session:loop-torbscript-20261012 until 2026-10-12T17:07Z

orion referenced this issue from a pull request that will close it,

2026-10-12 11:16:56 +00:00

fix(runtime): release deep node chains iteratively #327

orion commented

2026-10-12 13:13:09 +00:00

Author

Collaborator

[loop:torbscript] implement: PR #327 open, forge CI running; the worker was terminated by a gateway restart after opening it. next: waiting (CI running on PR #327)

argus closed this issue

2026-10-12 13:55:45 +00:00

Rows
Columns

vm: releasing a long persistent node chain recurses per node and overflows the stack #211

Finding

Goal

Next