mirror of
https://github.com/brazilofmux/tinymux
synced 2026-08-13 00:23:11 -04:00
3a9ecd068f
Terminating a runaway self-recursive ufun on the compiled route cost time
exponential in function_recursion_limit. Measured here, before:
function_recursion_limit eval_attempts seconds
8 97 0.02
12 1,537 0.01
16 24,577 0.14
20 393,217 0.57
24 6,291,457 7.76
eval_attempts is exactly 3*2^(d-3)+1 at every depth -- a full binary tree
with 2^(d-3) leaves and 2^(d-3)-1 internal nodes. The AST route is 0.00s
at every depth, so the blowup is specific to the compiled route.
Root cause. shared_heap_t holds one dbt_state_t: one guest register
context, one stack pointer, one heap arena. jit_eval's s_jit_depth > 1
arm runs through it, and that program ECALLs into u(), whose body
evaluates another bracket, which re-enters shared_heap_t::eval. The
nested run sets ctx.x[2] = STACK_TOP, resets s_heap_next and calls
tier2_reset_writable -- all underneath the suspended outer run. The outer
run resumes at a program counter that is not its own, the backend refuses
to translate there (XLATE_REFUSE), dbt_resume returns -1, and
shared_heap_t::eval returns false with host ECALLs already run. jit_eval
propagates that, and mux_exec redoes the whole bracket through the AST.
That bracket contains the next recursion level, so each level is evaluated
twice.
The type declares the hazard away in a comment -- "independent of the
outer expression's DBT, so this is safe to call from within an ECALL
handler" -- which is true of the outer expression's DBT and false of its
own. #1309 identified the same hazard for the Lua path and guarded it
with s_run_cached_depth; the softcode path re-enters unguarded.
Instrumented over the runaway, the correlation is total: of 511 runs that
had a nested run inside them, 511 failed and 0 succeeded; of 512 runs with
no nested run, 512 succeeded and 0 failed. Every re-entrant outer run
fails, so the nested run's result is always discarded by the parent's AST
re-run -- declining it up front forfeits no retained work.
After: eval_attempts is exactly limit+1 at every depth, and depth 100 --
which the issue reports as not finishing in any practical time -- answers
instantly.
function_recursion_limit eval_attempts seconds
8 9 0.00
24 25 0.00
100 101 0.00
Not a behaviour change for recursion that should complete: sum(1..n) via a
self-recursive ufun returns n(n+1)/2 on both routes at n = 3..50, checked
against the arithmetic rather than against the other route.
One difference is visible at the boundary. When the limit is low enough
that the recursion cannot complete, the two routes reach it at different
points inside the expression, because the JIT flattens nesting and this
changes how many func_nest_lev levels one softcode level costs. For
[switch(gt(%0,0),1,[u(me/CD,sub(%0,1))],done)] the limit can land in the
condition instead of the arm, and switch() then returns its default --
so the compiled route may answer "done" where the AST answers the limit
error. Enforcement itself is unaffected: func_nest_lev peaked at exactly
limit-2 in every configuration measured, never above. This is the same
class as the INVOCATION-vs-RECURSION difference already noted on #1994.
The counter is exposed as jitstats() bail_shared_busy so the decline is
visible rather than silent.
Adds testcases/tools/jit_recursion/oracle.sh (make test-jit-recursion),
which asserts eval_attempts stays linear. It has to assert a counter
rather than a result: the answer is correct either way -- the AST re-run
recomputes the same string -- which is exactly why this went unnoticed,
and a result-equality check cannot see it. Confirmed by breaking the
guard and re-running: the cost assertion fails at 393,217 while every
result assertion still passes.
A census over the full smoke suite recorded zero re-entrant shared-heap
runs (outer_ok=0 outer_fail=0, flat_ok=113), so smoke never exercised this
path at all -- which is why the regression test is a new oracle rather
than a smoke case.
make test 34/34 with jit=yes stubslave=yes nls=yes realitylvls=yes
wodrealms=yes.
Co-Authored-By: Claude Opus 5 <noreply@anthropic.com>
|
||
|---|---|---|
| .. | ||
| oracle.sh | ||