Skip to main content

Crate purrdf_stack

Crate purrdf_stack 

Source
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. Every wasm32 target 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 no unsafe code on wasm32 and cannot name a linker symbol, so a host that can (the PurRDF wasm package, when its instance starts) installs the symbol’s value with replace_floor, which also covers a module linked with the stack elsewhere. Neither __data_end nor __heap_base says 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 with replace_context whenever 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_floor reads pthread_getattr_np, pthread_attr_get_np, pthread_stackseg_np, pthread_get_stackaddr_np / pthread_get_stacksize_np, or GetCurrentThreadStackLimits, 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 with replace_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 — and remaining reports 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 walk scopes.
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§

StackError
Why on_stack did not run its computation.

Constants§

EXHAUSTED
A floor that leaves no stack at all: while it is installed, remaining reports 0 and is_low is true on 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_BYTES of stack are left.
on_stack
Run f on a stack of bytes and return what it returns.
on_stack_scoped
on_stack for a computation that borrows from the caller: f need 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 0 when the frame is already below it or EXHAUSTED is installed.
replace_context
Install context as the running computation’s, returning the context it replaces (which the caller puts back when it switches away again).
replace_floor
Install floor as 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 bytes of stack, beyond MARGIN_BYTES, out of reach of every check on this thread until the returned Reserve is dropped.
reserved
The bytes the running computation’s open reserve scopes keep above its stack’s real floor, widened bytes included: 0 when none is open.
scoped
Whether the running computation has a reserve scope open — whether widen has 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 walk scope, less than MARGIN_BYTES of 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 always false. construct names the walk, for the scope’s error.
widen
Keep bytes more stack out of reach of every check in the running computation, for as long as its outermost open reserve scope 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).