call/1 metacall recursion grows the native C stack and SIGSEGVs below the step limit #23

New issue

Closed

opened 2026-06-20 04:25:34 +00:00 by navicore · 1 comment

navicore commented

2026-06-20 04:25:34 +00:00

Owner

Summary

A predicate that recurses through call/1 (or any goal routed through the
runtime metacall path) grows the native C stack one frame per level and
SIGSEGVs, instead of running in constant stack like direct recursion. The
crash is reachable under default settings — it happens below the default
10,000 step limit — so the bounded-execution guarantee (the step limit) is
bypassed by an uncatchable stack overflow with silent, empty output.

This contradicts docs/ARCHITECTURE.md: "All transfers are tail calls and
continuation frames are heap-allocated, so Prolog recursion depth never grows
the C stack." That holds for direct predicate recursion; it does not hold
for call/1.

Reproduction

% callbug.pl
count(0).
count(N) :- N > 0, N1 is N - 1, call(count(N1)).   % via call/1
go(N) :- count(N).

$ plgc build callbug.pl -o callbug

# default step limit (10k), no PLG_MAX_STEPS:
$ ./callbug --query "go(1000)"  ; echo $?      #  true.   exit 1   (ok)
$ ./callbug --query "go(5000)"  ; echo $?      #  (empty) exit 139 (SIGSEGV)

Crossover is ~5–6k deep. With the identical predicate using direct
recursion (count(N1) instead of call(count(N1))), go(5000000) succeeds in
constant stack — so the growth is specifically the metacall re-entry, not the
>/is arithmetic body.

form	`go(4000)`	`go(6000)`	`go(5000000)`
`call(count(N1))`	ok (exit 1)	SIGSEGV (139)	SIGSEGV
`count(N1)` (direct)	ok	ok	ok (exit 1)

Why this is a bug (not just a missing optimization)

Even setting aside whether call/1 should get last-call optimization, the
uncatchable SIGSEGV below the step limit is the defect: the step limit
exists to bound runaway execution and fail gracefully, and this path overflows
the native stack (~5k frames) before the limit (10k steps) is ever reached. The
process dies with exit 139 and no diagnostic.

Root cause

crates/runtime/src/solve.rs, dispatch() re-enters compiled code with a plain
Rust call:

unsafe { f(m as *mut Machine, 0) }   // f = compiled predicate entry

This is not a tail call (Rust has no guaranteed TCO). The callee f runs
its full sub-search — including, for call/1 recursion, another trip through
call_goal → dispatch → f for the next level — before returning. So each
metacall level leaves a dispatch/call_goal Rust frame on the C stack.
Direct compiled goal calls are emitted as musttail in generated IR and are
exempt, which is why direct recursion stays constant.

This is the same class of issue as the fact-table delivery rule (delivery to the
continuation must be a musttail in generated IR, not a Rust call to k).

Anything that re-enters compiled code via call_goal/dispatch shares the
path and should be checked:

call/N metacall (this report)
findall/3 goal re-entry
catch/3 recovery-goal dispatch (unwind_to_catch calls call_goal)

Suggested direction

Route metacall dispatch into compiled code via a generated-IR musttail
trampoline (deliver the target function pointer back to IR that tail-calls it),
mirroring the fact-table delivery fix, rather than dispatch() calling f
directly in Rust. At minimum, the step limit must bound this path so it fails
gracefully instead of SIGSEGV-ing below the limit.

Environment

Found on aarch64-apple-darwin during the WASM Checkpoint-0 spike. The native
binary is the artifact that crashes; the wasm path traps the same way (it's a
native-architecture issue, independent of target).

## Summary A predicate that recurses through `call/1` (or any goal routed through the runtime metacall path) grows the **native C stack** one frame per level and **SIGSEGVs**, instead of running in constant stack like direct recursion. The crash is reachable under **default settings** — it happens *below* the default 10,000 step limit — so the bounded-execution guarantee (the step limit) is bypassed by an uncatchable stack overflow with silent, empty output. This contradicts `docs/ARCHITECTURE.md`: *"All transfers are tail calls and continuation frames are heap-allocated, so Prolog recursion depth never grows the C stack."* That holds for direct predicate recursion; it does **not** hold for `call/1`. ## Reproduction ```prolog % callbug.pl count(0). count(N) :- N > 0, N1 is N - 1, call(count(N1)). % via call/1 go(N) :- count(N). ``` ``` $ plgc build callbug.pl -o callbug # default step limit (10k), no PLG_MAX_STEPS: $ ./callbug --query "go(1000)" ; echo $? # true. exit 1 (ok) $ ./callbug --query "go(5000)" ; echo $? # (empty) exit 139 (SIGSEGV) ``` Crossover is ~5–6k deep. With the identical predicate using **direct** recursion (`count(N1)` instead of `call(count(N1))`), `go(5000000)` succeeds in constant stack — so the growth is specifically the metacall re-entry, not the `>`/`is` arithmetic body. | form | `go(4000)` | `go(6000)` | `go(5000000)` | |---|---|---|---| | `call(count(N1))` | ok (exit 1) | **SIGSEGV (139)** | SIGSEGV | | `count(N1)` (direct) | ok | ok | ok (exit 1) | ## Why this is a bug (not just a missing optimization) Even setting aside whether `call/1` *should* get last-call optimization, the **uncatchable SIGSEGV below the step limit** is the defect: the step limit exists to bound runaway execution and fail gracefully, and this path overflows the native stack (~5k frames) before the limit (10k steps) is ever reached. The process dies with exit 139 and no diagnostic. ## Root cause `crates/runtime/src/solve.rs`, `dispatch()` re-enters compiled code with a plain Rust call: ```rust unsafe { f(m as *mut Machine, 0) } // f = compiled predicate entry ``` This is **not** a tail call (Rust has no guaranteed TCO). The callee `f` runs its full sub-search — including, for `call/1` recursion, another trip through `call_goal → dispatch → f` for the next level — before returning. So each metacall level leaves a `dispatch`/`call_goal` Rust frame on the C stack. Direct compiled goal calls are emitted as `musttail` in generated IR and are exempt, which is why direct recursion stays constant. This is the same class of issue as the fact-table delivery rule (delivery to the continuation must be a `musttail` in generated IR, not a Rust call to `k`). ## Scope / related paths Anything that re-enters compiled code via `call_goal`/`dispatch` shares the path and should be checked: - `call/N` metacall (this report) - `findall/3` goal re-entry - `catch/3` recovery-goal dispatch (`unwind_to_catch` calls `call_goal`) ## Suggested direction Route metacall dispatch into compiled code via a generated-IR `musttail` trampoline (deliver the target function pointer back to IR that tail-calls it), mirroring the fact-table delivery fix, rather than `dispatch()` calling `f` directly in Rust. At minimum, the step limit must bound this path so it fails gracefully instead of SIGSEGV-ing below the limit. ## Environment Found on aarch64-apple-darwin during the WASM Checkpoint-0 spike. The native binary is the artifact that crashes; the wasm path traps the same way (it's a native-architecture issue, independent of target).

navicore referenced this issue from a commit

2026-06-20 06:01:49 +00:00

⏺ Confirmed clean: the only @plg_rt_metacall emission left is

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

2026-06-20 06:02:16 +00:00

⏺ Confirmed clean: the only @plg_rt_metacall emission left is #24

navicore commented

2026-06-20 06:02:32 +00:00

Author

Owner

#24

https://git.navicore.tech/navicore/patch-prolog/pulls/24