page-stack

A 4 KB page-aligned concurrent LIFO stack for Zig 0.16.0 — freestanding library, host-verified.

Push and pop operations that miss each other exchange payloads directly through a cache-line-isolated elimination array; the rest flow through an engine-global staging buffer (flat-combining leader election) into page-chained main storage, reclaimed safely by Hyaline epoch-based reclamation. No garbage collector, no OS mutexes, no heap allocator in the library.

Status

0.1.0-alpha — all milestones implemented and gated: wire protocol, page allocation, elimination rendezvous, epoch reclamation, stack engine with global staging, benchmarks with a recorded baseline. See CHANGELOG.md and benchmarks/baseline.json.

Features

• Page-chained main store — exact 4096 B / 4096-aligned nodes from OS virtual memory (VirtualAlloc on Windows, mmap on Linux), natural-alignment packing.
• Three-level push pipeline — elimination rendezvous → global staging with leader flush → main store with overflow chaining.
• Hybrid API — unified comptime-dispatched push/pop plus explicit pushScalar/popScalar/pushBytes/popBytes (copy-out; no popSlice).
• Hyaline EBR — 128-thread registry, hazard-free node retirement, no leaks.
• Deterministic errors — 8-variant sentinel set, zero-panic policy, non-destructive TypeSizeMismatch / BufferTooSmall.
• Verified — 40 tests (unit, multiset concurrency gates, churn stresses), full traceability PRD → TDD → code → tests, freestanding compile check.

Layout

• src/ — freestanding library: root, common (wire protocol, errors), node (4 KB pages), elimination (rendezvous), ebr (reclamation), stage (global staging buffer), stack (engine), os + os/windows + os/linux. No std.testing, no page_allocator, no OS mutex.
• tests/ — host-only verification (test_stack.zig).
• tools/ — host-only trace_check.zig (traceability gate) and bench_check.zig (≤10 % regression gate vs baseline).
• benchmarks/ — host-only bench_stack.zig runner plus baseline.json snapshot.
• docs/ — PRD.md, TDD.md (kept 1:1), CODING_STANDARDS.md (merged Zig + CODET).

Usage

const stack = @import("page_stack").stack;

var s = try stack.PageStack.init();
defer s.deinit();

const tok = try s.registerThread();

// Scalars (1, 2, 4, 8 bytes), LIFO ordered.
try s.pushScalar(u64, 0x1234, &tok);
const v = try s.popScalar(u64, &tok); // 0x1234

// Unified comptime dispatch.
try s.push(u64, 0xCAFE, &tok);
try s.push([]const u8, "data", &tok);

// Byte streams (chunked past 63 bytes, reassembled on pop).
try s.pushBytes("hello-world", &tok);
var buf: [64]u8 = undefined;
const n = try s.popBytes(&buf, &tok); // n == 11

Each thread registers once (registerThread, max 128) and passes its token to every operation. Popping an empty stack returns error.StackEmpty; an undersized popBytes buffer returns error.BufferTooSmall without consuming.

Commands

zig build docs --summary all               # Autodoc
zig build freestanding --summary all       # true freestanding compile check
zig build test --summary all               # host tests (40)
zig build test -Doptimize=ReleaseFast --summary all
zig build bench -Doptimize=ReleaseFast --summary all  # benchmarks + benchmarks/last.json
zig run tools/trace_check.zig              # traceability gate (exit 1 on gaps)
zig run tools/bench_check.zig              # <= 10% regression gate vs baseline (exit 1)
zig build -Doptimize=ReleaseFast --summary all        # production static lib

With Task: task ci runs trace → lint → freestanding → test → bench → build. Run benchmarks on an unloaded machine; re-run on failure before concluding regression (see benchmarks/baseline.json notes).

Performance snapshot

Measured on x86_64 Windows (Zig 0.16.0, ReleaseFast, median of 5, warmup discarded) — see benchmarks/baseline.json for method and machine notes:

Benchmark	Result	Target
Scalar push/pop pairs (u64)	2.74M ops/s	≥ 1M ops/s
Elimination miss probe	20.7 ns/op	info
Elimination paired mean	429.8 ns	≤ 50 ns in-window handoff
Concurrent 4P+4C, 100k ops wall	0.141 s	baseline
Concurrent avg / p50 / p99 per op	707 / 2300 / 20700 ns	baseline

The ≤ 50 ns target refers to the in-window atomic handoff (claim plus publish), consistent with the ~21 ns probe round trip. End-to-end paired means include waiter-handoff scheduling; QPC granularity (~100 ns) quantises fast medians to zero. Per-pop latencies include empty-spin waiting while producers are still working.

Design notes

• Staging is engine-global (1 KB in PageStack, not per-node), so head switches can never strand staged data. The leader drains until clean and resets only via exact-match CAS; drained headers are zeroed so post-reset scans see honest zeros.
• Main store is combiner-guarded by a test-and-test-and-set spinlock of pure atomics (no OS mutex): commit, claim, and unlink are mutually exclusive, which excludes speculative main bytes from racing pop walks by construction. Elimination, staging reservation, and EBR stay fully lock-free.
• Empty payloads bypass staging (header 0x00 is indistinguishable from an unpublished slot) and commit straight to main.
• A pop observing a busy elimination slot waits a generous bounded window for the provably mid-publish partner before missing.
• Pops flush staged (newer) data before taking main-top, so LIFO observes commit order.

Standards

Code documentation follows docs/CODING_STANDARDS.md. Every requirement in docs/PRD.md maps 1:1 to docs/TDD.md and into tested code — enforced by tools/trace_check.zig as a hard gate.

Limitations

• Windows and Linux page backends only; other targets return AllocationFailed.
• In-memory and volatile; no persistence or disk serialisation.
• Maximum 128 concurrently registered threads.
• Benchmark baselines are machine-specific; re-baseline deliberately on new hardware.

License

Copyright (c) 2026 Dzulkifli Anwar dzulkiflianwar2@gmail.com

This project is dual-licensed at your option:

• MIT License — see LICENSE-MIT.
• Apache License, Version 2.0 — see LICENSE-APACHE.

You may use, modify, and distribute it commercially under either license, provided the copyright and license notices above are preserved in all copies.