purrdf_stack/lib.rs
1// SPDX-FileCopyrightText: 2026 Blackcat Informatics® Inc. <paudley@blackcatinformatics.ca>
2// SPDX-License-Identifier: MIT OR Apache-2.0 OR MulanPSL-2.0
3
4//! `purrdf-stack` — how much stack the running thread has left.
5//!
6//! Exhausting the stack is not an error anywhere: natively the process aborts, and on
7//! `wasm32-unknown-unknown` the shadow stack runs below its floor and traps with the
8//! instance's memory in an unknown state. A bound on how deeply a request may nest does
9//! not bound the stack handling it needs — a level of one construct can cost a hundred
10//! times a level of another, and the thread it runs on may be small — so the SPARQL
11//! evaluator (`purrdf-sparql-eval`) measures the stack actually left at every recursive
12//! entry and refuses, typed, when less than [`MARGIN_BYTES`] remain. (The SPARQL parser,
13//! `purrdf-sparql-algebra`, keeps a request's nesting on heap-allocated stacks and does
14//! not recurse on it.) This crate is that measurement, in one place: one floor per
15//! thread, one margin, the walk scopes that let a recursion with no error channel refuse
16//! too ([`walk`], [`walk_is_low`]), the stack a computation keeps out of reach of its
17//! own checks for walks it knows it will make ([`reserve`], [`widen`]), and the functions
18//! hosts call to install the floor of a stack they switch onto ([`replace_floor`]) or to
19//! switch whole contexts ([`replace_context`]). It also runs a computation on a stack of
20//! a stated size ([`on_stack`]), which is how a guard that refuses on a small stack is
21//! exercised on one.
22//!
23//! # The floor
24//!
25//! "Stack left" is the current stack pointer minus the lowest address the stack may
26//! reach — the *floor* — for the stack the thread is running on. Every target PurRDF
27//! ships on has a downward-growing stack.
28//!
29//! * **`wasm32`**: the stack is the shadow stack in linear memory, and its pointer is the
30//! address of any address-taken local ([`stack_pointer`]). The floor is a thread-local
31//! whose default is the low end of the module's own shadow stack. Every `wasm32` target
32//! rustc ships links with `--stack-first`, which makes the shadow stack the first region
33//! of linear memory, so that low end is address 0 — running below it wraps the pointer
34//! and traps. The linker records it as the symbol `__stack_low`; this crate has no
35//! `unsafe` code on `wasm32` and cannot name a linker symbol, so a host that can (the
36//! PurRDF wasm package, when its instance starts) installs the symbol's value with
37//! [`replace_floor`], which also covers a module linked with the stack elsewhere.
38//! Neither `__data_end` nor `__heap_base` says where the stack *ends*, and the first
39//! pointer observed is the stack's top, not its floor. A host that runs work on a
40//! stack of its own — the wasm package's asynchronous lane runs each job on a
41//! heap-allocated region — installs that stack's context with [`replace_context`]
42//! whenever it switches onto it and puts the previous context back whenever it switches
43//! away (see [Switching contexts](#switching-contexts)).
44//! * **native**: the floor is the current thread's stack limit, as the operating system
45//! reports it — `platform::stack_floor` reads `pthread_getattr_np`,
46//! `pthread_attr_get_np`, `pthread_stackseg_np`, `pthread_get_stackaddr_np` /
47//! `pthread_get_stacksize_np`, or `GetCurrentThreadStackLimits`, per platform; see that
48//! module for which targets read which call, and which read nothing. It is read once per
49//! thread and cached in the same thread-local, so a check costs one thread-local load
50//! and one comparison. A pointer found *below* the cached floor means the thread is
51//! running on a different stack than the one the floor was read for (a host that switched
52//! onto a stack of its own, say), so the floor is read again rather than refusing: a
53//! stack switch never turns into a refusal. (A stack a host switched to *above* the
54//! cached floor is measured against the old floor, which overstates what is left: such a
55//! host installs its own floor with [`replace_floor`], as the wasm asynchronous lane
56//! does.) On a platform whose limit cannot be read at all the measurement is inactive —
57//! there is nothing to measure against — and [`remaining`] reports the whole address
58//! range below the frame, so nothing refuses.
59//!
60//! # The margin
61//!
62//! A check refuses when less than [`MARGIN_BYTES`] remain, so the margin must hold the
63//! deepest chain of frames any guarded path can push *between two checks*, plus the
64//! non-recursive work that runs after the last one. See [`MARGIN_BYTES`] for the measured
65//! figures.
66//!
67//! # Walk scopes
68//!
69//! A recursion that has an error channel refuses by returning an error when [`is_low`]
70//! says so. One that has none — an infallible analysis, substitution or copy over a tree
71//! whose height nothing but the stack bounds — runs inside a [`walk`] scope instead: each
72//! level asks [`walk_is_low`], the first that finds the margin gone latches the refusal in
73//! the scope and installs [`EXHAUSTED`] so every later check refuses at once, and the
74//! scope discards whatever the walk built and reports the refusal. Which scope is open,
75//! and what it latched, is per-context state kept beside the floor.
76//!
77//! # Switching contexts
78//!
79//! The floor and the walk-scope state together are a [`Context`]: everything this crate
80//! keeps for the computation running on the thread. A host that runs several
81//! computations on one thread and switches between them *before any has returned* — the
82//! PurRDF wasm package's asynchronous lane suspends a job in the middle of an evaluation
83//! and runs the synchronous lane, or another job, until it resumes — swaps the whole
84//! context with [`replace_context`] at every switch. Swapping the floor alone is not
85//! enough: a job suspended inside a walk scope would leave that scope open for whatever
86//! ran next, whose own walks would latch their refusals in it — handing a placeholder to a
87//! caller with no scope to discard it, and leaving [`EXHAUSTED`] installed on a context
88//! that never refused — and two jobs closing their scopes in the order they happen to be
89//! resumed, rather than the reverse of the order they opened them, would leave each
90//! other's scope state behind.
91
92#![deny(unsafe_code)]
93
94use core::cell::Cell;
95use core::marker::PhantomData;
96use std::rc::Rc;
97
98#[cfg(not(target_arch = "wasm32"))]
99#[allow(
100 unsafe_code,
101 reason = "reading the current thread's stack bounds from the operating system; each \
102 block carries its own safety argument, and none of it compiles on wasm32, \
103 where the crate stays unsafe-free"
104)]
105mod platform;
106
107/// The stack a check requires to be left, in bytes: 128 KiB natively.
108///
109/// # Derivation
110///
111/// The margin has to hold the deepest chain of frames any guarded path pushes between
112/// two checks, together with the work that runs past the last check before a leaf
113/// returns.
114///
115/// **The evaluator** checks at every recursive entry, so what is left between two checks
116/// is one level of one recursion plus the leaf under it. It was measured by lowering the
117/// margin and sweeping the size of the thread a request runs on (x86_64, the workspace's
118/// opt-level-3 profile), over 26 request shapes that include every nesting and sibling
119/// form the parser admits at its limits:
120///
121/// * with a 4 or 8 KiB margin (threads of 96 to 704 KiB in 4 KiB steps) some thread
122/// sizes abort — the widest interval is a basic graph pattern's first use of a lazily
123/// built index, whose sort needs between 8 and 16 KiB;
124/// * with a 16 KiB margin (threads of 32 to 736 KiB in 8 KiB steps, 2 314 runs) every
125/// request answers or is the refusal, except on a 32 KiB thread, too small for the
126/// walks that run once before a plan's first operator. The same sweep over whole
127/// requests, governed ones, updates and in-process `SERVICE` calls found no other abort
128/// in the evaluator.
129///
130/// 128 KiB is eight times the evaluator's widest interval. The rest is room for what the sweeps cannot see: host code a leaf calls (a registered
131/// function, relation or aggregate, a `SERVICE` transport), and the derived copy and
132/// comparison of terms up to 128 triple-term levels deep (a computation walking deeper
133/// ones keeps what they take out of reach with [`reserve`]). It
134/// costs a thread little it could have used: a default 2 MiB thread keeps 94% of its
135/// stack, and a request refused here needed nearly all of it anyway.
136#[cfg(not(target_arch = "wasm32"))]
137pub const MARGIN_BYTES: usize = 128 * 1024;
138
139/// The stack a check requires to be left, in bytes: 64 KiB on `wasm32`.
140///
141/// # Derivation
142///
143/// As for the native margin. **The evaluator's** was measured with the margin lowered to
144/// 16 KiB, on the shipped npm artifact's synchronous lane with its shadow stack painted:
145/// 565 requests mixing two nesting forms at a time (`NOT EXISTS`, `EXISTS`, `OPTIONAL`,
146/// `LATERAL`, `MINUS`, sub-`SELECT`) over four innermost shapes (a triple, a 200-operator
147/// chain, a 121-step path, a nested `EXISTS` over a 100-term conjunction), so the refusal
148/// falls at every phase of every level. None trapped; the deepest frame any of them
149/// reached was 11 064 bytes above the floor — 5 320 bytes past the point the check
150/// refuses at. Only address-taken locals live on the shadow stack, so its levels are
151/// smaller than their native twins, and host code (a JavaScript function or resolver)
152/// runs on the engine's own stack, not on this one.
153///
154/// 64 KiB is twelve times the measured interval. It leaves the synchronous lane 960 KiB
155/// of its 1 MiB — 63 nested `FILTER EXISTS`, which reached 96% of the stack before the
156/// evaluator's guard existed, is refused, where 63 nested `FILTER NOT EXISTS` used to
157/// trap and corrupt the instance — and an asynchronous job, which runs on a heap region
158/// exactly as large as that shadow stack with the region's base installed as its floor,
159/// is refused here with the same typed error; compiler frame sizes can make the two
160/// lanes reach that refusal at different depths. The host engine's own
161/// call stack, which this crate cannot read, the SPARQL evaluator bounds with a budget of
162/// its own.
163#[cfg(target_arch = "wasm32")]
164pub const MARGIN_BYTES: usize = 64 * 1024;
165
166/// A floor that leaves no stack at all: while it is installed, [`remaining`] reports `0`
167/// and [`is_low`] is `true` on this thread, whatever the stack pointer.
168///
169/// For a guard that must stop every further check on the thread at once — a [`walk`]
170/// scope latches a refusal this way so the rest of the walk unwinds without computing
171/// over the placeholder it left — installed with [`replace_floor`], and replaced by the
172/// floor [`replace_floor`] returned once the refusal has been reported.
173pub const EXHAUSTED: usize = usize::MAX - 1;
174
175/// The floor's value before anything has been read or installed on this thread.
176const UNKNOWN: usize = usize::MAX;
177
178/// Where the running context stands with respect to [`walk`] scopes.
179#[derive(Clone, Copy, Debug, PartialEq, Eq)]
180enum WalkState {
181 /// No scope is open: a walk that runs low has nobody to hand a refusal to, so it
182 /// carries on exactly as it would with no guard at all.
183 Unscoped,
184 /// A scope is open and nothing has refused yet.
185 Scoped,
186 /// A walk inside the open scope refused at `construct`; the floor it replaced with
187 /// [`EXHAUSTED`] is `floor`.
188 Refused {
189 /// What refused.
190 construct: &'static str,
191 /// The floor to put back when the scope closes.
192 floor: usize,
193 },
194}
195
196thread_local! {
197 /// The floor of the stack this thread is running on; [`UNKNOWN`] until the first
198 /// measurement reads it (or a host installs one with [`replace_floor`]).
199 static FLOOR: Cell<usize> = const { Cell::new(UNKNOWN) };
200 /// The running context's [`WalkState`].
201 static WALK: Cell<WalkState> = const { Cell::new(WalkState::Unscoped) };
202 /// The bytes the open [`reserve`] scopes keep above the stack's real floor: `FLOOR`
203 /// is the real floor raised by this much, and a floor read again is raised by it too.
204 /// [`WIDENED`] is part of it.
205 static RESERVED: Cell<usize> = const { Cell::new(0) };
206 /// How many [`reserve`] scopes are open in the running context.
207 static SCOPES: Cell<usize> = const { Cell::new(0) };
208 /// The bytes [`widen`] added to the open scopes, given back when the outermost of
209 /// them closes.
210 static WIDENED: Cell<usize> = const { Cell::new(0) };
211}
212
213/// The current stack pointer, as the address of a local of the calling frame.
214///
215/// On `wasm32` an address-taken local lives on the shadow stack, so this is the shadow
216/// stack's depth, not the (inaccessible) value stack's; natively it is within one frame
217/// of the machine stack pointer. `black_box` keeps the local a real, addressed slot.
218/// Whether or not the call is inlined, the address is within this function's own small
219/// frame of the caller's, which the margin absorbs.
220#[inline]
221#[must_use]
222pub fn stack_pointer() -> usize {
223 let marker = 0u8;
224 core::hint::black_box(&raw const marker) as usize
225}
226
227/// The bytes of stack left below the calling frame before the floor, or `0` when the
228/// frame is already below it or [`EXHAUSTED`] is installed.
229#[must_use]
230pub fn remaining() -> usize {
231 let sp = stack_pointer();
232 match FLOOR.with(Cell::get) {
233 EXHAUSTED => 0,
234 floor => sp.checked_sub(floor).unwrap_or_else(|| refresh(sp)),
235 }
236}
237
238/// Install `floor` as the floor of the stack this thread now runs on, returning the
239/// floor it replaces (which the caller puts back when it switches away again).
240///
241/// Only a host that switches the stack pointer onto a stack of its own needs this, or a
242/// guard latching a refusal with [`EXHAUSTED`]; see the [crate documentation](crate).
243/// The value returned may be the "not yet read" marker, which is a valid value to put
244/// back: the next measurement reads the floor again.
245pub fn replace_floor(floor: usize) -> usize {
246 FLOOR.with(|cell| cell.replace(floor))
247}
248
249/// Everything this crate keeps for the computation running on the thread: the floor of
250/// its stack and the state of its [`walk`] scopes.
251///
252/// A host that switches between computations before they return swaps the whole of it
253/// with [`replace_context`]; see [Switching contexts](crate#switching-contexts). The
254/// value is opaque: a host only ever puts back what [`replace_context`] handed it, or
255/// installs a fresh one with [`Context::on_floor`].
256#[derive(Clone, Copy, Debug, PartialEq, Eq)]
257pub struct Context {
258 /// The floor [`replace_floor`] would install.
259 floor: usize,
260 /// The walk-scope state.
261 walk: WalkState,
262 /// The bytes the context's open [`reserve`] scopes keep above its real floor.
263 reserved: usize,
264 /// How many [`reserve`] scopes the context has open.
265 scopes: usize,
266 /// The bytes [`widen`] added to the context's open scopes.
267 widened: usize,
268}
269
270impl Context {
271 /// The context of a stack whose floor is `floor`, with no walk scope open — what a
272 /// host installs when it switches onto a stack of its own for a computation that has
273 /// not started yet.
274 #[must_use]
275 pub const fn on_floor(floor: usize) -> Self {
276 Self {
277 floor,
278 walk: WalkState::Unscoped,
279 reserved: 0,
280 scopes: 0,
281 widened: 0,
282 }
283 }
284}
285
286/// Install `context` as the running computation's, returning the context it replaces
287/// (which the caller puts back when it switches away again).
288///
289/// The floor, the walk-scope state and the open [`reserve`] scopes are swapped together,
290/// so a walk scope a suspended computation left open — and a refusal it latched there,
291/// with [`EXHAUSTED`] installed — stays with that computation, as does the stack it
292/// reserved, and whatever runs while it waits sees only its own. See
293/// [Switching contexts](crate#switching-contexts).
294pub fn replace_context(context: Context) -> Context {
295 Context {
296 floor: replace_floor(context.floor),
297 walk: WALK.with(|state| state.replace(context.walk)),
298 reserved: RESERVED.with(|reserved| reserved.replace(context.reserved)),
299 scopes: SCOPES.with(|scopes| scopes.replace(context.scopes)),
300 widened: WIDENED.with(|widened| widened.replace(context.widened)),
301 }
302}
303
304/// Keep `bytes` of stack, beyond [`MARGIN_BYTES`], out of reach of every check on this
305/// thread until the returned [`Reserve`] is dropped.
306///
307/// For a computation whose leaves run a recursion of known depth with no check of its
308/// own — the SPARQL evaluator copies, compares and matches the triple terms a request
309/// writes wherever its evaluation stands, and a term nested `n` deep takes those walks
310/// `n` levels down — reserving what that recursion needs up front makes every check the
311/// computation passes leave room for it: [`is_low`], [`remaining`] and [`walk_is_low`]
312/// all measure against the floor raised by `bytes`, so a frame that passed a check has
313/// the margin *and* the reserve below it. It is the floor that moves, so a check costs
314/// what it always did.
315///
316/// Reserves nest, and add up. A floor read again while one is open (a native thread
317/// that finds its frame below the cached floor) is raised by what is reserved, and a
318/// host's [`replace_context`] carries the reserve with the computation that made it. On
319/// a platform whose stack bound cannot be read, where every guard of this crate is
320/// inactive, nothing is reserved either.
321///
322/// A reserve is also a *scope* — even one of zero bytes — that [`widen`] can add to while
323/// the computation runs: whatever it adds is given back when the outermost open scope
324/// closes, not the innermost, because what the computation built with it may reach every
325/// frame up to where the computation started.
326pub fn reserve(bytes: usize) -> Reserve {
327 // Read the floor first, so what is raised is a real floor rather than the "not yet
328 // read" marker.
329 let _ = remaining();
330 let floor = FLOOR.with(Cell::get);
331 if floor == EXHAUSTED || inactive(floor) {
332 return Reserve {
333 bytes: 0,
334 scoped: false,
335 thread_bound: PhantomData,
336 };
337 }
338 FLOOR.with(|cell| cell.set(floor.saturating_add(bytes)));
339 RESERVED.with(|reserved| reserved.set(reserved.get() + bytes));
340 SCOPES.with(|scopes| scopes.set(scopes.get() + 1));
341 Reserve {
342 bytes,
343 scoped: true,
344 thread_bound: PhantomData,
345 }
346}
347
348/// Whether `floor` is the "no readable bound" floor of a native platform, where every
349/// guard of this crate is inactive.
350const fn inactive(floor: usize) -> bool {
351 cfg!(not(target_arch = "wasm32")) && floor == 0
352}
353
354/// Keep `bytes` more stack out of reach of every check in the running computation, for
355/// as long as its outermost open [`reserve`] scope lives — when the computation finds, as
356/// it runs, that it needs more than it reserved when it started (the SPARQL evaluator
357/// admitting a triple term it built, deeper than any the request wrote).
358///
359/// Returns whether the bytes are kept. They are not, and nothing changes, when no scope
360/// is open (nothing would give them back), when a refusal is latched ([`EXHAUSTED`] is
361/// installed), or when the calling frame would be left with less than [`MARGIN_BYTES`]
362/// above the raised floor — the caller refuses then, typed. On a platform whose stack
363/// bound cannot be read nothing is measured, so nothing is kept and `true` is returned.
364///
365/// The bytes are given back when the outermost scope closes rather than the innermost,
366/// because what the computation built with them may be walked in any frame up to the
367/// one that opened the outermost scope: that frame is above the one that widened, so it
368/// has at least the margin and every widened byte above the real floor.
369#[must_use]
370pub fn widen(bytes: usize) -> bool {
371 let _ = remaining();
372 let floor = FLOOR.with(Cell::get);
373 if inactive(floor) || bytes == 0 {
374 return true;
375 }
376 if floor == EXHAUSTED || SCOPES.with(Cell::get) == 0 {
377 return false;
378 }
379 let raised = floor.saturating_add(bytes);
380 let sp = stack_pointer();
381 if sp
382 .checked_sub(raised)
383 .is_none_or(|left| left < MARGIN_BYTES)
384 {
385 return false;
386 }
387 FLOOR.with(|cell| cell.set(raised));
388 RESERVED.with(|reserved| reserved.set(reserved.get() + bytes));
389 WIDENED.with(|widened| widened.set(widened.get() + bytes));
390 true
391}
392
393/// The bytes the running computation's open [`reserve`] scopes keep above its stack's
394/// real floor, [`widen`]ed bytes included: `0` when none is open.
395#[must_use]
396pub fn reserved() -> usize {
397 RESERVED.with(Cell::get)
398}
399
400/// Whether the running computation has a [`reserve`] scope open — whether [`widen`] has
401/// anywhere to keep its bytes.
402#[must_use]
403pub fn scoped() -> bool {
404 SCOPES.with(Cell::get) > 0
405}
406
407/// Stack kept out of reach of every check while it lives; see [`reserve`]. Dropping it
408/// gives the bytes back. The guard belongs to the creating thread, whose context it
409/// updates when dropped; it cannot move to another thread or be shared across threads.
410///
411/// ```compile_fail,E0277
412/// let guard = purrdf_stack::reserve(4096);
413/// std::thread::spawn(move || drop(guard));
414/// ```
415///
416/// ```compile_fail,E0277
417/// fn requires_sync<T: Sync>() {}
418/// requires_sync::<purrdf_stack::Reserve>();
419/// ```
420#[derive(Debug)]
421#[must_use = "the stack is reserved only while the `Reserve` lives"]
422pub struct Reserve {
423 /// What this reserve raised the floor by.
424 bytes: usize,
425 /// Whether it opened a scope (see [`reserve`]).
426 scoped: bool,
427 /// Dropping a reservation updates the creating thread's state.
428 thread_bound: PhantomData<Rc<()>>,
429}
430
431impl Reserve {
432 /// The bytes this reserve keeps: what was asked for, or `0` where nothing could be
433 /// reserved (no readable stack bound, or a refusal already latched).
434 #[must_use]
435 pub const fn bytes(&self) -> usize {
436 self.bytes
437 }
438}
439
440impl Drop for Reserve {
441 fn drop(&mut self) {
442 if !self.scoped {
443 return;
444 }
445 // The outermost scope gives back what `widen` added while any scope was open.
446 let outermost = SCOPES.with(|scopes| {
447 let open = scopes.get().saturating_sub(1);
448 scopes.set(open);
449 open == 0
450 });
451 let bytes = if outermost {
452 self.bytes + WIDENED.with(|widened| widened.replace(0))
453 } else {
454 self.bytes
455 };
456 if bytes == 0 {
457 return;
458 }
459 RESERVED.with(|reserved| reserved.set(reserved.get().saturating_sub(bytes)));
460 match FLOOR.with(Cell::get) {
461 // A walk scope inside this reserve refused and has not closed: it put
462 // EXHAUSTED in place of the raised floor and puts that floor back when it
463 // closes, so that is the floor to lower.
464 EXHAUSTED => WALK.with(|state| {
465 if let WalkState::Refused { construct, floor } = state.get() {
466 state.set(WalkState::Refused {
467 construct,
468 floor: floor.saturating_sub(bytes),
469 });
470 }
471 }),
472 UNKNOWN => {}
473 floor => FLOOR.with(|cell| cell.set(floor.saturating_sub(bytes))),
474 }
475 }
476}
477
478/// Run `body` — an infallible recursive walk over a tree whose height nothing but the
479/// stack bounds (an analysis, a substitution, a copy) — so that it can refuse when the stack
480/// runs low.
481///
482/// Such a walk has no error channel, so a level of it that finds less than
483/// [`MARGIN_BYTES`] left calls [`walk_is_low`], which latches the refusal in this scope
484/// and tells the walk to stop descending and return a placeholder. The scope then
485/// discards whatever `body` produced and returns `Err` with the construct that refused:
486/// a placeholder never escapes, because the only way to reach `body`'s value is through
487/// the `Ok` this returns only when nothing refused. Anything the walk wrote through a
488/// reference must be discarded with it, which is why a caller hands its walk state it owns
489/// (a fresh table, a fresh map) and drops it on the error.
490///
491/// Once a level has refused, the rest of the walk must not go on computing over the
492/// placeholder it left — a later level could trip an internal consistency assertion on a
493/// tree it half-built — so the refusal also replaces the running context's floor with
494/// [`EXHAUSTED`]: every check in that context, in every walk, then refuses at once, and the walk unwinds to this scope level by level
495/// without doing any more work. The real floor is put back when the scope closes.
496///
497/// Scopes nest: the enclosing scope's state (and, after a refusal, the floor) is put back
498/// when this one closes, even when `body` unwinds. They nest *per context*: a host that
499/// suspends a computation inside a scope swaps its [`Context`] out with
500/// [`replace_context`], so the scope is closed in the context that opened it.
501///
502/// # Errors
503///
504/// The `construct` a level of the walk named when it refused.
505pub fn walk<T>(body: impl FnOnce() -> T) -> Result<T, &'static str> {
506 /// Closes the scope when the walk returns or unwinds: puts the real floor back if a
507 /// level refused, then the enclosing scope's state.
508 struct Close(WalkState);
509 impl Drop for Close {
510 fn drop(&mut self) {
511 let inner = WALK.with(|state| state.replace(self.0));
512 if let WalkState::Refused { floor, .. } = inner {
513 replace_floor(floor);
514 }
515 }
516 }
517 let close = Close(WALK.with(|state| state.replace(WalkState::Scoped)));
518 let value = body();
519 let outcome = WALK.with(Cell::get);
520 drop(close);
521 match outcome {
522 WalkState::Refused { construct, .. } => Err(construct),
523 WalkState::Unscoped | WalkState::Scoped => Ok(value),
524 }
525}
526
527/// Whether a level of an infallible walk must stop descending: inside a [`walk`] scope,
528/// less than [`MARGIN_BYTES`] of stack are left (the refusal is latched for the scope to
529/// report), or a level of the same walk already refused. Outside any scope this is always
530/// `false`. `construct` names the walk, for the scope's error.
531///
532/// The hot path is [`is_low`]'s; the scope is consulted only once the margin is gone.
533#[inline]
534#[must_use]
535pub fn walk_is_low(construct: &'static str) -> bool {
536 if !is_low() {
537 return false;
538 }
539 walk_refuse(construct)
540}
541
542/// The cold half of [`walk_is_low`]: latch the refusal in the open scope, if any.
543#[cold]
544#[inline(never)]
545fn walk_refuse(construct: &'static str) -> bool {
546 WALK.with(|state| match state.get() {
547 WalkState::Unscoped => false,
548 WalkState::Scoped => {
549 let floor = replace_floor(EXHAUSTED);
550 state.set(WalkState::Refused { construct, floor });
551 true
552 }
553 WalkState::Refused { .. } => true,
554 })
555}
556
557/// Whether less than [`MARGIN_BYTES`] of stack are left.
558///
559/// The hot path is one thread-local load, one subtraction and one comparison; the floor
560/// is read (or re-read) only on the cold path.
561#[inline]
562#[must_use]
563pub fn is_low() -> bool {
564 let sp = stack_pointer();
565 sp.checked_sub(FLOOR.with(Cell::get))
566 .is_none_or(|left| left < MARGIN_BYTES)
567 && is_low_cold(sp)
568}
569
570/// The cold half of [`is_low`]: the floor was never read on this thread, the frame is
571/// below it, [`EXHAUSTED`] is installed, or the margin really is gone.
572#[cold]
573#[inline(never)]
574fn is_low_cold(sp: usize) -> bool {
575 let left = match FLOOR.with(Cell::get) {
576 EXHAUSTED => return true,
577 floor => sp.checked_sub(floor).unwrap_or_else(|| refresh(sp)),
578 };
579 left < MARGIN_BYTES
580}
581
582/// Read the floor of the stack `sp` is on, cache it, and return the bytes left above it.
583#[cfg(not(target_arch = "wasm32"))]
584fn refresh(sp: usize) -> usize {
585 // `platform::stack_floor` reads the thread's bounds directly from the operating
586 // system rather than from any particular frame, so — unlike a floor derived from a
587 // "bytes left" figure measured a few frames down — this is the thread's exact floor,
588 // not an approximation of it.
589 let floor = match platform::stack_floor() {
590 // What the open reserves keep is above the real floor.
591 Some(floor) => floor.saturating_add(RESERVED.with(Cell::get)),
592 None => 0,
593 };
594 FLOOR.with(|cell| cell.set(floor));
595 sp.saturating_sub(floor)
596}
597
598/// The floor of the synchronous shadow stack when no host has installed one: address 0.
599///
600/// Every `wasm32` target rustc ships links with `wasm-ld --stack-first`, which places the
601/// shadow stack as the first region of linear memory: `[0, stack size)`, the stack
602/// pointer starting at its top (1 MiB by default) and growing down toward address 0,
603/// with static data and the heap above it. The linker records that low end as the symbol
604/// `__stack_low`; this crate forbids `unsafe` code, so it cannot name a linker symbol
605/// itself, and takes the value the layout fixes instead. A host that links otherwise
606/// (`--no-stack-first` puts the stack above the static data) or that can read the
607/// symbol installs the real floor with [`replace_floor`] — the PurRDF wasm package does
608/// exactly that, from `__stack_low`, when its instance starts.
609#[cfg(target_arch = "wasm32")]
610const DEFAULT_FLOOR: usize = 0;
611
612/// Read the floor of the stack `sp` is on, cache it, and return the bytes left above it.
613///
614/// Only the first measurement on an instance with no installed floor reads anything: it
615/// takes [`DEFAULT_FLOOR`]. A frame below an installed floor has already run past the
616/// stack that floor belongs to, so nothing is left — the one case a native thread
617/// re-reads (a host that switched stacks under it) cannot arise here, where every stack
618/// switch installs its floor.
619#[cfg(target_arch = "wasm32")]
620fn refresh(sp: usize) -> usize {
621 if FLOOR.with(Cell::get) == UNKNOWN {
622 let floor = DEFAULT_FLOOR + RESERVED.with(Cell::get);
623 FLOOR.with(|cell| cell.set(floor));
624 return sp.saturating_sub(floor);
625 }
626 0
627}
628
629/// Why [`on_stack`] did not run its computation.
630#[derive(Debug)]
631#[non_exhaustive]
632pub enum StackError {
633 /// The computation asked for more stack than is left above the running stack's floor.
634 ///
635 /// `wasm32` has one shadow stack per instance and no second thread to give a
636 /// computation a stack of its own, so [`on_stack`] runs it inline on what is left of
637 /// the running stack: a request larger than that cannot be honoured, and is refused
638 /// here rather than trapping below the floor part-way through the computation.
639 ExceedsFloor {
640 /// The bytes asked for.
641 requested: usize,
642 /// The bytes left above the floor when the request was made.
643 available: usize,
644 },
645 /// The operating system would not start a thread with the requested stack.
646 Spawn(purrdf_hash::error::IoFailure),
647}
648
649impl purrdf_hash::error::StructuredError for StackError {
650 purrdf_hash::error_visit! {
651 ExceedsFloor { requested, available } => "stack-exceeds-floor" {
652 "requested" => ByteCount(*requested as u128),
653 "available" => ByteCount(*available as u128)
654 },
655 Spawn(cause) => "stack-spawn" { "cause" => Cause(cause) },
656 }
657}
658
659impl core::fmt::Display for StackError {
660 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
661 match self {
662 Self::ExceedsFloor {
663 requested,
664 available,
665 } => write!(
666 f,
667 "a {requested}-byte stack was requested, but only {available} bytes are left \
668 above the running stack's floor"
669 ),
670 Self::Spawn(error) => write!(f, "could not start a thread for the stack: {error}"),
671 }
672 }
673}
674
675impl std::error::Error for StackError {
676 fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
677 match self {
678 Self::ExceedsFloor { .. } => None,
679 Self::Spawn(error) => Some(error),
680 }
681 }
682}
683
684/// Run `f` on a stack of `bytes` and return what it returns.
685///
686/// A guard that refuses before the stack runs out is only shown to work by running it on
687/// a stack small enough to run out, so every such test needs "this computation, on a
688/// stack this big". This is the one implementation of that, because what a stack of a
689/// given size *is* differs by target and only this crate knows both:
690///
691/// * **native**: a fresh thread whose stack is `bytes` (the operating system may round
692/// it up to its minimum or its page size, never down). A fresh thread starts with a
693/// fresh [`Context`] — its own floor, no walk scope, no reserve — so `f` is measured
694/// against exactly the stack it was given. A panic in `f` resumes on the calling thread
695/// with its original payload, so an assertion inside `f` fails the caller with its own
696/// message.
697/// * **`wasm32`**: there is no second thread, so `f` runs inline, under a fresh
698/// [`Context`] whose floor is `bytes` below the calling frame: every check `f` makes
699/// sees a stack of `bytes`, as it would on a native thread of that size, and the
700/// caller's context is put back when `f` returns. The request is checked against the
701/// stack actually left above the running floor first, and one larger than that is
702/// refused with [`StackError::ExceedsFloor`] instead of running `f` into a trap.
703///
704/// # Errors
705///
706/// [`StackError::ExceedsFloor`] on `wasm32` when `bytes` exceeds what is left above the
707/// floor; [`StackError::Spawn`] natively when the thread cannot be started.
708pub fn on_stack<R: Send + 'static>(
709 bytes: usize,
710 f: impl FnOnce() -> R + Send + 'static,
711) -> Result<R, StackError> {
712 on_stack_scoped(bytes, f)
713}
714
715/// [`on_stack`] for a computation that borrows from the caller: `f` need not be
716/// `'static`, because the stack it runs on is gone before this returns.
717///
718/// Natively `f` runs on a scoped thread of `bytes` that is joined before the
719/// scope closes, so its borrows of the caller's locals are sound; on `wasm32` it
720/// runs inline under the same fresh [`Context`] as [`on_stack`], and a request
721/// over the floor is refused in the same way. Every other property — the fresh
722/// context, a panic resuming on the caller with its payload — is [`on_stack`]'s,
723/// which is this function with a `'static` computation.
724///
725/// # Errors
726///
727/// [`StackError::ExceedsFloor`] on `wasm32` when `bytes` exceeds what is left above the
728/// floor; [`StackError::Spawn`] natively when the thread cannot be started.
729pub fn on_stack_scoped<'env, R: Send + 'env>(
730 bytes: usize,
731 f: impl FnOnce() -> R + Send + 'env,
732) -> Result<R, StackError> {
733 #[cfg(not(target_arch = "wasm32"))]
734 {
735 on_thread(bytes, f)
736 }
737 #[cfg(target_arch = "wasm32")]
738 {
739 on_current_stack(bytes, f)
740 }
741}
742
743/// [`on_stack_scoped`] natively: `f` on a scoped thread of `bytes`, joined before
744/// the scope closes.
745#[cfg(not(target_arch = "wasm32"))]
746fn on_thread<'env, R: Send + 'env>(
747 bytes: usize,
748 f: impl FnOnce() -> R + Send + 'env,
749) -> Result<R, StackError> {
750 std::thread::scope(|scope| {
751 let handle = std::thread::Builder::new()
752 .stack_size(bytes)
753 .spawn_scoped(scope, f)
754 .map_err(|cause| StackError::Spawn(cause.into()))?;
755 match handle.join() {
756 Ok(value) => Ok(value),
757 Err(payload) => std::panic::resume_unwind(payload),
758 }
759 })
760}
761
762/// [`on_stack`] on `wasm32`: `f` inline, under a fresh [`Context`] whose floor is `bytes`
763/// below the calling frame, after checking that much stack is left above the running
764/// floor. Compiled natively too, so its refusal and its accepted neighbour are tested on
765/// every target.
766#[cfg_attr(
767 not(any(target_arch = "wasm32", test)),
768 expect(
769 dead_code,
770 reason = "the inline path is `on_stack_scoped` on wasm32 only"
771 )
772)]
773fn on_current_stack<R>(bytes: usize, f: impl FnOnce() -> R) -> Result<R, StackError> {
774 /// Puts the caller's context back when `f` returns or unwinds.
775 struct Restore(Context);
776 impl Drop for Restore {
777 fn drop(&mut self) {
778 replace_context(self.0);
779 }
780 }
781 let available = remaining();
782 if bytes > available {
783 return Err(StackError::ExceedsFloor {
784 requested: bytes,
785 available,
786 });
787 }
788 // `remaining` measured from a frame at or below this one, so the frame here has at
789 // least `bytes` above the running floor and the new floor does not pass under it.
790 let floor = stack_pointer().saturating_sub(bytes);
791 let restore = Restore(replace_context(Context::on_floor(floor)));
792 let value = f();
793 drop(restore);
794 Ok(value)
795}
796
797#[cfg(test)]
798mod tests {
799 use super::*;
800
801 /// `levels` frames of 4 KiB below the caller, then `at_bottom`.
802 fn deeper<T>(levels: usize, at_bottom: &dyn Fn() -> T) -> T {
803 if levels == 0 {
804 return at_bottom();
805 }
806 let frame = core::hint::black_box([0u8; 4096]);
807 let value = deeper(levels - 1, at_bottom);
808 core::hint::black_box(&frame);
809 value
810 }
811
812 /// The first measurement on a thread reads its floor, and what it reports is that
813 /// thread's own stack, and tracks the stack pointer: sixteen 4 KiB frames deeper, it
814 /// reports at least 64 KiB less.
815 #[test]
816 fn remaining_measures_the_thread_s_own_stack() {
817 const BYTES: usize = 4 * 1024 * 1024;
818 let (top, below) =
819 on_stack(BYTES, || (remaining(), deeper(16, &remaining))).expect("spawn");
820 // At least what was asked for, less the frames already live. (The C library may
821 // hand a thread more than it asked for, never less.)
822 assert!(
823 top > BYTES - 64 * 1024,
824 "{top} bytes left of at least {BYTES}"
825 );
826 let used = top - below;
827 assert!(
828 (16 * 4096..16 * 4096 + 32 * 1024).contains(&used),
829 "sixteen 4 KiB frames used {used} bytes"
830 );
831 }
832
833 /// On a small thread, `remaining` falls as frames are pushed, `is_low` turns true
834 /// once the margin is eaten into — and not before — and both recover as the frames
835 /// unwind.
836 #[test]
837 fn a_small_thread_runs_low_as_its_stack_is_consumed() {
838 let (top, low_at_top, reports) = on_stack(512 * 1024, || {
839 let top = remaining();
840 let low_at_top = is_low();
841 let mut reports = Vec::new();
842 let mut levels = 0;
843 loop {
844 let (left, low) = deeper(levels, &|| (remaining(), is_low()));
845 reports.push((left, low));
846 if low {
847 break;
848 }
849 levels += 4;
850 }
851 (top, low_at_top, reports)
852 })
853 .expect("spawn");
854 assert!(
855 !low_at_top,
856 "{top} bytes left at the top of a 512 KiB thread"
857 );
858 assert!(
859 reports.windows(2).all(|pair| pair[1].0 < pair[0].0),
860 "remaining falls with every four frames: {reports:?}"
861 );
862 // `remaining` and `is_low` read the stack pointer in two different frames, a few
863 // hundred bytes apart at most; the kilobyte of slack below is that, not the step.
864 const FRAME_SLACK: usize = 1024;
865 let (last_left, last_low) = *reports.last().expect("at least one report");
866 assert!(
867 last_low && last_left < MARGIN_BYTES + FRAME_SLACK,
868 "{reports:?}"
869 );
870 assert!(
871 reports[..reports.len() - 1]
872 .iter()
873 .all(|&(left, low)| !low && left + FRAME_SLACK > MARGIN_BYTES),
874 "nothing is low while the margin is whole: {reports:?}"
875 );
876 assert!(
877 reports.len() > 2,
878 "the thread had room for several steps before the margin: {reports:?}"
879 );
880 assert!(
881 on_stack(512 * 1024, || !is_low()).expect("spawn"),
882 "a fresh thread is not low"
883 );
884 }
885
886 /// A floor installed above the running frame (a host that switched away without
887 /// putting the previous floor back) is read again rather than reporting nothing left.
888 #[test]
889 fn a_floor_above_the_frame_is_read_again() {
890 let (low, left) = on_stack(1024 * 1024, || {
891 let previous = replace_floor(stack_pointer() + 4096);
892 let low = is_low();
893 let left = remaining();
894 replace_floor(previous);
895 (low, left)
896 })
897 .expect("spawn");
898 assert!(!low);
899 assert!(left > MARGIN_BYTES, "{left} bytes left");
900 }
901
902 /// `replace_floor` hands back what it replaced, so a host can nest switches, and an
903 /// installed floor is the one measured against.
904 #[test]
905 fn replace_floor_sets_and_returns_the_floor() {
906 on_stack(256 * 1024, || {
907 let original = replace_floor(1);
908 assert_eq!(replace_floor(2), 1);
909 let sp = stack_pointer();
910 replace_floor(sp - 8192);
911 let left = remaining();
912 assert!(
913 (8192 - 1024..8192 + 1024).contains(&left),
914 "{left} bytes left above a floor 8 KiB down"
915 );
916 assert!(is_low(), "8 KiB is inside the margin");
917 assert_eq!(replace_floor(original), sp - 8192);
918 assert!(!is_low(), "the thread's own floor is back");
919 })
920 .expect("spawn");
921 }
922
923 /// While [`EXHAUSTED`] is installed nothing is left, whatever the stack pointer, and
924 /// putting the previous floor back restores the measurement.
925 #[test]
926 fn the_exhausted_floor_leaves_nothing() {
927 on_stack(1024 * 1024, || {
928 assert!(!is_low());
929 let previous = replace_floor(EXHAUSTED);
930 assert_eq!(remaining(), 0);
931 assert!(is_low());
932 assert_eq!(replace_floor(previous), EXHAUSTED);
933 assert!(!is_low());
934 assert!(remaining() > MARGIN_BYTES);
935 })
936 .expect("spawn");
937 }
938
939 /// A floor 1 KiB below the calling frame: inside the margin, so [`is_low`] is `true`.
940 fn low_floor() -> usize {
941 stack_pointer() - 1024
942 }
943
944 /// A walk that runs low inside a scope is refused with the construct it named, the
945 /// rest of the walk sees [`EXHAUSTED`], and closing the scope puts the real floor back.
946 /// Outside any scope the same low stack is not a refusal, and nothing is latched.
947 #[test]
948 fn a_scope_latches_a_low_walk_and_an_unscoped_walk_carries_on() {
949 on_stack(1024 * 1024, || {
950 assert!(!is_low(), "the thread's own floor, read");
951 let real = FLOOR.with(Cell::get);
952 let low = low_floor();
953 replace_floor(low);
954 assert!(!walk_is_low("unscoped walk"), "no scope, no refusal");
955 assert_eq!(replace_floor(real), low, "nothing latched");
956
957 let mut observed = None;
958 let refused = walk(|| {
959 replace_floor(low_floor());
960 let first = walk_is_low("scoped walk");
961 // The low floor is swapped for EXHAUSTED, so every later level stops too.
962 let latched = FLOOR.with(Cell::get);
963 observed = Some((first, latched, walk_is_low("a later level")));
964 });
965 assert_eq!(observed, Some((true, EXHAUSTED, true)));
966 assert_eq!(refused, Err("scoped walk"), "the first refusal is reported");
967 // The scope put back the floor it replaced — the low one this test installed.
968 assert!(is_low());
969 replace_floor(real);
970 assert!(!is_low(), "the thread's own floor is back");
971 assert_eq!(walk(|| walk_is_low("roomy walk")), Ok(false));
972 })
973 .expect("spawn");
974 }
975
976 /// A computation suspended inside a scope takes the scope with it: the context that
977 /// runs while it waits has none, so a walk there that runs low carries on and latches
978 /// nothing, and the suspended scope is still open — and still able to refuse — when
979 /// the computation resumes. The neighbouring control swaps the floor alone, as a host
980 /// that knew nothing of walk scopes would: the waiting context's walk then latches its
981 /// refusal in the suspended scope, leaves [`EXHAUSTED`] as the waiting context's floor,
982 /// and the suspended computation is refused for a walk it never ran.
983 #[test]
984 fn a_suspended_scope_stays_with_its_context() {
985 on_stack(1024 * 1024, || {
986 assert!(!is_low(), "the thread's own floor, read");
987 let real = FLOOR.with(Cell::get);
988 let mut observed = None;
989 let suspended = walk(|| {
990 // Suspend: the waiting context runs on its own, nearly exhausted, stack.
991 let waiting_floor = low_floor();
992 let job = replace_context(Context::on_floor(waiting_floor));
993 let waiting_low = walk_is_low("waiting walk");
994 let waiting = replace_context(job);
995 // Resume: the job's scope is open, and refuses a walk that runs low.
996 replace_floor(low_floor());
997 let job_low = walk_is_low("resumed walk");
998 observed = Some((
999 waiting_low,
1000 waiting == Context::on_floor(waiting_floor),
1001 job_low,
1002 ));
1003 });
1004 assert_eq!(observed, Some((false, true, true)));
1005 assert_eq!(
1006 suspended,
1007 Err("resumed walk"),
1008 "the job's own refusal, no other"
1009 );
1010 // Closing the refusing scope put back the floor the job's walk replaced.
1011 assert!(is_low());
1012 replace_floor(real);
1013
1014 let waiting = walk(|| {
1015 let waiting_floor = low_floor();
1016 let job = replace_context(Context::on_floor(waiting_floor));
1017 let low = walk_is_low("waiting walk");
1018 let after = replace_context(job);
1019 (low, after == Context::on_floor(waiting_floor))
1020 });
1021 assert_eq!(
1022 waiting,
1023 Ok((false, true)),
1024 "the waiting walk had no scope and latched nothing; the job was not refused"
1025 );
1026 assert!(!is_low());
1027
1028 let mut observed = None;
1029 let floor_only = walk(|| {
1030 let job_floor = replace_floor(low_floor());
1031 let low = walk_is_low("waiting walk");
1032 observed = Some((low, replace_floor(job_floor)));
1033 });
1034 assert_eq!(
1035 observed,
1036 Some((true, EXHAUSTED)),
1037 "swapping the floor alone latches the waiting walk in the job's scope, and \
1038 leaves the waiting context exhausted"
1039 );
1040 assert_eq!(
1041 floor_only,
1042 Err("waiting walk"),
1043 "and refuses the job for the waiting context's walk"
1044 );
1045 replace_floor(real);
1046 })
1047 .expect("spawn");
1048 }
1049
1050 /// A reserve takes its bytes off what every check sees, and gives them back when it
1051 /// is dropped; reserves add up. The neighbouring control: a reserve that leaves more
1052 /// than the margin is not low, one that eats into the margin is.
1053 #[test]
1054 fn a_reserve_is_kept_out_of_reach_until_dropped() {
1055 on_stack(4 * 1024 * 1024, || {
1056 let before = remaining();
1057 let outer = reserve(512 * 1024);
1058 assert_eq!(outer.bytes(), 512 * 1024);
1059 let within = remaining();
1060 assert!(
1061 (before - 512 * 1024 - 1024..before - 512 * 1024 + 1024).contains(&within),
1062 "{before} bytes before a 512 KiB reserve, {within} within it"
1063 );
1064 assert!(
1065 !is_low(),
1066 "a reserve that leaves more than the margin is not low"
1067 );
1068 let inner = reserve(within - MARGIN_BYTES / 2);
1069 assert!(is_low(), "a reserve that eats into the margin is low");
1070 drop(inner);
1071 assert!(!is_low());
1072 drop(outer);
1073 let after = remaining();
1074 assert!(
1075 (before - 1024..before + 1024).contains(&after),
1076 "{before} bytes before, {after} after the reserve is dropped"
1077 );
1078 })
1079 .expect("spawn");
1080 }
1081
1082 /// A floor read again inside a reserve — a native thread whose frame is found below
1083 /// the cached floor — is raised by what is reserved, so the reserve survives it.
1084 #[test]
1085 fn a_floor_read_again_keeps_the_reserve() {
1086 on_stack(4 * 1024 * 1024, || {
1087 let before = remaining();
1088 let kept = reserve(1024 * 1024);
1089 let raised = FLOOR.with(Cell::get);
1090 // As if the thread had switched stacks: the cached floor is above the frame.
1091 replace_floor(stack_pointer() + 4096);
1092 let within = remaining();
1093 assert_eq!(
1094 FLOOR.with(Cell::get),
1095 raised,
1096 "the floor read again is raised"
1097 );
1098 assert!(
1099 within + 1024 * 1024 <= before + 1024,
1100 "{within} bytes left inside a 1 MiB reserve of {before}"
1101 );
1102 drop(kept);
1103 assert!(remaining() + 1024 > before);
1104 })
1105 .expect("spawn");
1106 }
1107
1108 /// A reserve travels with its context: the computation that runs while it waits sees
1109 /// its own stack whole, and the reserve is still in force when it resumes.
1110 #[test]
1111 fn a_reserve_stays_with_its_context() {
1112 on_stack(4 * 1024 * 1024, || {
1113 let before = remaining();
1114 let kept = reserve(1024 * 1024);
1115 let real = FLOOR.with(Cell::get) - 1024 * 1024;
1116 let job = replace_context(Context::on_floor(real));
1117 let waiting = remaining();
1118 let back = replace_context(job);
1119 assert_eq!(
1120 back,
1121 Context::on_floor(real),
1122 "the waiting context reserved nothing"
1123 );
1124 assert!(
1125 waiting + 1024 > before,
1126 "{waiting} of {before} bytes for the waiting context"
1127 );
1128 assert!(
1129 remaining() + 1024 * 1024 <= before + 1024,
1130 "the reserve is back in force"
1131 );
1132 drop(kept);
1133 assert!(remaining() + 1024 > before);
1134 })
1135 .expect("spawn");
1136 }
1137
1138 /// Widening needs an open scope, keeps its bytes until the OUTERMOST scope closes
1139 /// (an inner scope closing gives back only its own), and refuses — changing nothing —
1140 /// a widening that would leave the calling frame less than the margin, while the
1141 /// neighbouring widening that leaves more is kept.
1142 #[test]
1143 fn a_widening_lasts_until_the_outermost_scope_closes() {
1144 on_stack(4 * 1024 * 1024, || {
1145 let before = remaining();
1146 assert!(!scoped());
1147 assert!(!widen(4096), "no scope: nothing would give the bytes back");
1148 assert_eq!(reserved(), 0);
1149 let outer = reserve(0);
1150 assert!(scoped());
1151 assert_eq!(outer.bytes(), 0);
1152 let inner = reserve(64 * 1024);
1153 assert!(
1154 widen(256 * 1024),
1155 "a widening that leaves the margin is kept"
1156 );
1157 assert_eq!(reserved(), 320 * 1024);
1158 let left = remaining();
1159 assert!(
1160 !widen(left - MARGIN_BYTES / 2),
1161 "a widening into the margin is refused"
1162 );
1163 assert_eq!(reserved(), 320 * 1024, "and changes nothing");
1164 assert!(widen(left - MARGIN_BYTES - 8192), "its neighbour is kept");
1165 let widened = 256 * 1024 + (left - MARGIN_BYTES - 8192);
1166 drop(inner);
1167 assert_eq!(
1168 reserved(),
1169 widened,
1170 "the inner scope gives back its own only"
1171 );
1172 assert!(scoped());
1173 drop(outer);
1174 assert_eq!(
1175 reserved(),
1176 0,
1177 "the outermost scope gives back every widening"
1178 );
1179 assert!(!scoped());
1180 let after = remaining();
1181 assert!(
1182 (before - 1024..before + 1024).contains(&after),
1183 "{before} bytes before, {after} after"
1184 );
1185 })
1186 .expect("spawn");
1187 }
1188
1189 /// A widening travels with its context, like the scope it belongs to.
1190 #[test]
1191 fn a_widening_stays_with_its_context() {
1192 on_stack(4 * 1024 * 1024, || {
1193 let before = remaining();
1194 let scope = reserve(0);
1195 assert!(widen(1024 * 1024));
1196 let real = FLOOR.with(Cell::get) - 1024 * 1024;
1197 let job = replace_context(Context::on_floor(real));
1198 assert!(!scoped(), "the waiting context has no scope");
1199 assert!(!widen(4096));
1200 assert!(remaining() + 1024 > before);
1201 let back = replace_context(job);
1202 assert_eq!(back, Context::on_floor(real));
1203 assert!(scoped());
1204 assert!(remaining() + 1024 * 1024 <= before + 1024);
1205 drop(scope);
1206 assert!(remaining() + 1024 > before);
1207 assert_eq!(reserved(), 0);
1208 })
1209 .expect("spawn");
1210 }
1211
1212 /// A walk scope that refuses inside a reserve and closes after the reserve is dropped
1213 /// puts back the real floor, not the raised one.
1214 #[test]
1215 fn a_refusal_latched_inside_a_reserve_restores_the_real_floor() {
1216 on_stack(4 * 1024 * 1024, || {
1217 let _ = remaining();
1218 let real = FLOOR.with(Cell::get);
1219 let refused = walk(|| {
1220 let kept = reserve(remaining() - MARGIN_BYTES / 2);
1221 assert!(
1222 walk_is_low("reserved walk"),
1223 "the reserve eats into the margin"
1224 );
1225 assert_eq!(FLOOR.with(Cell::get), EXHAUSTED);
1226 drop(kept);
1227 assert_eq!(
1228 FLOOR.with(Cell::get),
1229 EXHAUSTED,
1230 "the refusal stays latched"
1231 );
1232 });
1233 assert_eq!(refused, Err("reserved walk"));
1234 assert_eq!(FLOOR.with(Cell::get), real, "the real floor is back");
1235 assert!(!is_low());
1236 })
1237 .expect("spawn");
1238 }
1239
1240 /// `on_stack` runs its computation on a stack of its own, at least the size asked
1241 /// for: what the computation measures is that stack, not the caller's, and its value
1242 /// comes back.
1243 #[test]
1244 fn on_stack_runs_the_computation_on_a_stack_of_the_requested_size() {
1245 const BYTES: usize = 512 * 1024;
1246 let caller_sp = stack_pointer();
1247 let caller_floor = caller_sp - remaining();
1248 let (sp, left) =
1249 on_stack(BYTES, || (stack_pointer(), remaining())).expect("a 512 KiB thread starts");
1250 // The operating system may round a thread's stack up to a page or its minimum, and
1251 // the C library may hand a thread a cached stack several times the request, never
1252 // less; 64 KiB covers the frames already live.
1253 assert!(
1254 left >= BYTES - 64 * 1024,
1255 "{left} bytes left on a {BYTES}-byte stack"
1256 );
1257 assert!(
1258 !(caller_floor..=caller_sp).contains(&sp),
1259 "the computation ran on the caller's stack ({sp:#x} in {caller_floor:#x}..={caller_sp:#x})"
1260 );
1261 assert_eq!(on_stack(BYTES, || 7_u8).expect("runs"), 7);
1262 }
1263
1264 /// A panic inside `on_stack`'s computation resumes on the caller with the original
1265 /// payload, so an assertion inside it fails the caller with its own message.
1266 #[test]
1267 fn on_stack_resumes_a_panic_with_its_own_payload() {
1268 let caught = std::panic::catch_unwind(|| {
1269 on_stack(256 * 1024, || -> () {
1270 panic!("the inner assertion's message")
1271 })
1272 })
1273 .expect_err("the panic reaches the caller");
1274 let message = caught
1275 .downcast_ref::<&str>()
1276 .copied()
1277 .expect("a string payload");
1278 assert_eq!(message, "the inner assertion's message");
1279 }
1280
1281 /// The inline path refuses a request larger than the stack left above the running
1282 /// floor, typed, and runs its neighbour just inside it — the boundary drawn from a
1283 /// floor installed a known distance below the frame.
1284 #[test]
1285 fn an_over_floor_request_is_refused_and_an_in_floor_request_runs() {
1286 on_stack(2 * 1024 * 1024, || {
1287 let previous = replace_floor(stack_pointer() - 512 * 1024);
1288 let available = remaining();
1289
1290 let over = on_current_stack(available + 4096, || unreachable!("not run"));
1291 match over {
1292 Err(StackError::ExceedsFloor {
1293 requested,
1294 available: reported,
1295 }) => {
1296 assert_eq!(requested, available + 4096);
1297 assert!(reported <= available, "{reported} of {available}");
1298 }
1299 other => panic!("an over-floor request is refused, got {other:?}"),
1300 }
1301 assert!(
1302 matches!(
1303 on_current_stack(usize::MAX, || ()),
1304 Err(StackError::ExceedsFloor { .. })
1305 ),
1306 "the largest request is refused"
1307 );
1308
1309 let inside = on_current_stack(available - 4096, remaining)
1310 .expect("a request inside the floor runs");
1311 assert!(inside <= available - 4096, "{inside} of {available}");
1312
1313 replace_floor(previous);
1314 })
1315 .expect("spawn");
1316 }
1317
1318 /// The inline path gives its computation a fresh context of the requested size — a
1319 /// small request is inside the margin, a large one is not, no reserve scope of the
1320 /// caller's is visible — and puts the caller's context back afterwards.
1321 #[test]
1322 fn the_inline_path_runs_under_a_fresh_context_and_restores_the_caller_s() {
1323 on_stack(4 * 1024 * 1024, || {
1324 let _ = remaining();
1325 let kept = reserve(0);
1326 let floor = FLOOR.with(Cell::get);
1327 assert!(scoped());
1328
1329 let (low, inner_scoped) =
1330 on_current_stack(MARGIN_BYTES / 2, || (is_low(), scoped())).expect("runs");
1331 assert!(low, "half the margin is inside it");
1332 assert!(
1333 !inner_scoped,
1334 "the caller's reserve scope stays with the caller"
1335 );
1336 assert!(
1337 !on_current_stack(4 * MARGIN_BYTES, is_low).expect("runs"),
1338 "four margins are not low"
1339 );
1340
1341 assert!(scoped(), "the caller's scope is back");
1342 assert_eq!(FLOOR.with(Cell::get), floor, "the caller's floor is back");
1343 drop(kept);
1344 })
1345 .expect("spawn");
1346 }
1347
1348 /// The typed refusal says what was asked for and what was left.
1349 #[test]
1350 fn the_refusal_names_the_request_and_what_was_left() {
1351 let error = StackError::ExceedsFloor {
1352 requested: 2048,
1353 available: 1024,
1354 };
1355 assert_eq!(
1356 error.to_string(),
1357 "a 2048-byte stack was requested, but only 1024 bytes are left above the \
1358 running stack's floor"
1359 );
1360 assert!(std::error::Error::source(&error).is_none());
1361 }
1362}