Expand description
purrdf-stack — how much stack the running thread has left.
Exhausting the stack is not an error anywhere: natively the process aborts, and on
wasm32-unknown-unknown the shadow stack runs below its floor and traps with the
instance’s memory in an unknown state. A bound on how deeply a request may nest does
not bound the stack handling it needs — a level of one construct can cost a hundred
times a level of another, and the thread it runs on may be small — so the SPARQL
evaluator (purrdf-sparql-eval) measures the stack actually left at every recursive
entry and refuses, typed, when less than MARGIN_BYTES remain. (The SPARQL parser,
purrdf-sparql-algebra, keeps a request’s nesting on heap-allocated stacks and does
not recurse on it.) This crate is that measurement, in one place: one floor per
thread, one margin, the walk scopes that let a recursion with no error channel refuse
too (walk, walk_is_low), the stack a computation keeps out of reach of its
own checks for walks it knows it will make (reserve, widen), and the functions
hosts call to install the floor of a stack they switch onto (replace_floor) or to
switch whole contexts (replace_context). It also runs a computation on a stack of
a stated size (on_stack), which is how a guard that refuses on a small stack is
exercised on one.
§The floor
“Stack left” is the current stack pointer minus the lowest address the stack may reach — the floor — for the stack the thread is running on. Every target PurRDF ships on has a downward-growing stack.
wasm32: the stack is the shadow stack in linear memory, and its pointer is the address of any address-taken local (stack_pointer). The floor is a thread-local whose default is the low end of the module’s own shadow stack. Everywasm32target rustc ships links with--stack-first, which makes the shadow stack the first region of linear memory, so that low end is address 0 — running below it wraps the pointer and traps. The linker records it as the symbol__stack_low; this crate has nounsafecode onwasm32and cannot name a linker symbol, so a host that can (the PurRDF wasm package, when its instance starts) installs the symbol’s value withreplace_floor, which also covers a module linked with the stack elsewhere. Neither__data_endnor__heap_basesays where the stack ends, and the first pointer observed is the stack’s top, not its floor. A host that runs work on a stack of its own — the wasm package’s asynchronous lane runs each job on a heap-allocated region — installs that stack’s context withreplace_contextwhenever it switches onto it and puts the previous context back whenever it switches away (see Switching contexts).- native: the floor is the current thread’s stack limit, as the operating system
reports it —
platform::stack_floorreadspthread_getattr_np,pthread_attr_get_np,pthread_stackseg_np,pthread_get_stackaddr_np/pthread_get_stacksize_np, orGetCurrentThreadStackLimits, per platform; see that module for which targets read which call, and which read nothing. It is read once per thread and cached in the same thread-local, so a check costs one thread-local load and one comparison. A pointer found below the cached floor means the thread is running on a different stack than the one the floor was read for (a host that switched onto a stack of its own, say), so the floor is read again rather than refusing: a stack switch never turns into a refusal. (A stack a host switched to above the cached floor is measured against the old floor, which overstates what is left: such a host installs its own floor withreplace_floor, as the wasm asynchronous lane does.) On a platform whose limit cannot be read at all the measurement is inactive — there is nothing to measure against — andremainingreports the whole address range below the frame, so nothing refuses.
§The margin
A check refuses when less than MARGIN_BYTES remain, so the margin must hold the
deepest chain of frames any guarded path can push between two checks, plus the
non-recursive work that runs after the last one. See MARGIN_BYTES for the measured
figures.
§Walk scopes
A recursion that has an error channel refuses by returning an error when is_low
says so. One that has none — an infallible analysis, substitution or copy over a tree
whose height nothing but the stack bounds — runs inside a walk scope instead: each
level asks walk_is_low, the first that finds the margin gone latches the refusal in
the scope and installs EXHAUSTED so every later check refuses at once, and the
scope discards whatever the walk built and reports the refusal. Which scope is open,
and what it latched, is per-context state kept beside the floor.
§Switching contexts
The floor and the walk-scope state together are a Context: everything this crate
keeps for the computation running on the thread. A host that runs several
computations on one thread and switches between them before any has returned — the
PurRDF wasm package’s asynchronous lane suspends a job in the middle of an evaluation
and runs the synchronous lane, or another job, until it resumes — swaps the whole
context with replace_context at every switch. Swapping the floor alone is not
enough: a job suspended inside a walk scope would leave that scope open for whatever
ran next, whose own walks would latch their refusals in it — handing a placeholder to a
caller with no scope to discard it, and leaving EXHAUSTED installed on a context
that never refused — and two jobs closing their scopes in the order they happen to be
resumed, rather than the reverse of the order they opened them, would leave each
other’s scope state behind.
Structs§
- Context
- Everything this crate keeps for the computation running on the thread: the floor of
its stack and the state of its
walkscopes. - Reserve
- Stack kept out of reach of every check while it lives; see
reserve. Dropping it gives the bytes back. The guard belongs to the creating thread, whose context it updates when dropped; it cannot move to another thread or be shared across threads.
Enums§
- Stack
Error - Why
on_stackdid not run its computation.
Constants§
- EXHAUSTED
- A floor that leaves no stack at all: while it is installed,
remainingreports0andis_lowistrueon this thread, whatever the stack pointer. - MARGIN_
BYTES - The stack a check requires to be left, in bytes: 128 KiB natively.
Functions§
- is_low
- Whether less than
MARGIN_BYTESof stack are left. - on_
stack - Run
fon a stack ofbytesand return what it returns. - on_
stack_ scoped on_stackfor a computation that borrows from the caller:fneed not be'static, because the stack it runs on is gone before this returns.- remaining
- The bytes of stack left below the calling frame before the floor, or
0when the frame is already below it orEXHAUSTEDis installed. - replace_
context - Install
contextas the running computation’s, returning the context it replaces (which the caller puts back when it switches away again). - replace_
floor - Install
flooras the floor of the stack this thread now runs on, returning the floor it replaces (which the caller puts back when it switches away again). - reserve
- Keep
bytesof stack, beyondMARGIN_BYTES, out of reach of every check on this thread until the returnedReserveis dropped. - reserved
- The bytes the running computation’s open
reservescopes keep above its stack’s real floor,widened bytes included:0when none is open. - scoped
- Whether the running computation has a
reservescope open — whetherwidenhas anywhere to keep its bytes. - stack_
pointer - The current stack pointer, as the address of a local of the calling frame.
- walk
- Run
body— an infallible recursive walk over a tree whose height nothing but the stack bounds (an analysis, a substitution, a copy) — so that it can refuse when the stack runs low. - walk_
is_ low - Whether a level of an infallible walk must stop descending: inside a
walkscope, less thanMARGIN_BYTESof stack are left (the refusal is latched for the scope to report), or a level of the same walk already refused. Outside any scope this is alwaysfalse.constructnames the walk, for the scope’s error. - widen
- Keep
bytesmore stack out of reach of every check in the running computation, for as long as its outermost openreservescope lives — when the computation finds, as it runs, that it needs more than it reserved when it started (the SPARQL evaluator admitting a triple term it built, deeper than any the request wrote).