thread-pool Design #

Overview #

thread-pool is a fixed-capacity, shared-infrastructure thread-pool with three concrete scheduler variants behind one public API:

• global_queue
• work_stealing
• lane_extension

The public API stays stable while scheduler selection, queue topology, and instrumentation remain internal. Algorithm-level diagrams (submit pipeline, worker loop, descriptor state, DescCache, wake coalescing, lane routing, shutdown) are consolidated in ALGORITHMS.md; this document covers rationale, contracts, and memory / shutdown model.

Public Surface #

flowchart LR
    INIT[ThreadPool.init allocator, config]
    DEINIT[ThreadPool.deinit]
    SUB[submit / trySubmit / submitBatch]
    REG[registerSubmitter / releaseSubmitter]
    WAIT[wait / waitGroup]
    SHUT[shutdown mode, timeout_ns]
    STAT[statsSnapshot / purgeWorkerCaches]
    INIT --> SUB
    SUB --> REG
    SUB --> WAIT
    INIT --> SHUT
    INIT --> STAT
    SHUT --> DEINIT

ThreadPool.purgeWorkerCaches() is quiescent-only. It returns error.PoolBusy unless active_tasks == 0 && queued_tasks == 0.

Scheduler Variants #

global_queue #

• One bounded FIFO inject queue (BoundedRing MPMC).
• Fixed worker set.
• Workers pop directly from the shared queue.
• Included as the simplest correctness-first baseline and fallback.
• Submit-path bypasses LIFO slot and local queues entirely (comptime elided when -Dscheduler-variant=global_queue).

work_stealing #

• One bounded central inject queue for external submitters.
• One owner-local LIFO slot (atomic u64 with LIFO_SLOT_EMPTY sentinel) plus one bounded local queue per worker.
• Local submissions from worker threads prefer the LIFO slot, then the local queue.
• Idle workers refill from the inject queue, then attempt steals from peer local queues using the workers_nonempty u64 bitmap to skip empty victims.
• Optional per-submitter SPMC queues via registerSubmitter() — cross-thread steal from submitter-owned push queues without paying MPMC inject contention.
• Worker wake: scanAndWake performs a linear scan from a rotating hint (submitted % scan_len), wakes the first parked worker it finds, and exits. The scan is issued at most once per wake_coalesce_batch (default 32) submissions so the futex cost is amortised across bursts.

lane_extension #

• work_stealing plus a dedicated blocking inject queue (blocking_inject) and a reserved worker range.
• Workers [0, blocking_workers) drain blocking_inject; workers [blocking_workers, max_threads) drain the default lane.
• Slice L3 cross-lane rebalance: a blocking worker always helps the default lane when its own lane is empty; a default worker helps the blocking lane only when Config.cpu_helps_blocking is set.
• Slice L4 watchdog: spawns up to Config.max_overflow_workers when a default-lane task runs longer than blocking_promotion_timeout_ns. Overflow workers retire themselves after sustained idleness.

Queue Design #

flowchart TB
    subgraph MPMC
        IQ[BoundedRing<br/>Vyukov per-slot sequence<br/>MPMC lock-free]
    end
    subgraph SPMC
        LQ[RingQueue - default owner local<br/>single producer, multi-consumer stealers<br/>stealHalf batched take]
    end
    subgraph SPMCopt[SPMC opt-in - for testing]
        CD[WorkDeque Chase-Lev<br/>queue_kind = .chase_lev]
    end
    subgraph SPSC
        DC[DescCache LIFO 32<br/>zero-atomic push/pop<br/>drainAll on release]
    end
    IQ ---|inject_queue + blocking_inject| Pool
    LQ ---|local_queues i + submitter_queues i| Pool
    CD ---|opt-in local_queues i| Pool
    DC ---|workers i .desc_cache + desc_caches i| Pool

Inject Queue #

• Bounded ring buffer — BoundedRing.
• Vyukov-style per-slot sequence word encodes producer/consumer turn.
• Backpressure explicit: error.QueueFull, block with timeout, or block indefinitely.
• popMany fast path: one strong head CAS reserves up to inject_batch_size (default 32) entries, slot reads bounded by per-slot sequence spin.

Local Worker Queue #

• Bounded owner-local queue with pluggable implementation via Config.queue_kind.
• queue_kind = .ring — default SPMC modelled on Tokio/Go runq.
• queue_kind = .chase_lev — classic Chase-Lev deque.
• Owner pushes and pops from bottom/tail; stealers take from head/top.

DescCache #

• 32-entry SPSC LIFO per submitter slot (desc_caches[i]) and per worker (workers[i].desc_cache).
• Refill: acquireDescriptorBatch takes up to 32 indices from the global freelist with one acquire pointer exchange; cache holds tail, returns head to caller.
• Drain-on-release: releaseDescriptor pushes into the owning slot's cache; on overflow, bounded spin-retry onto the inject queue's freelist sibling.
• Drain-on-deinit: every cache is drained into the freelist before deinit frees the array; preserves task_desc_live == 0 invariant.

Memory Model #

• Task descriptors are preallocated from a bounded descriptor array.
• Descriptor reuse happens only after task completion and, for waitable tasks, after wait.
• Worker scratch allocates one bounded buffer per worker lazily on first use.
• On the normal owning-worker path, scratch begin/alloc/finish are lock-free.
• Scratch buffers can be purged explicitly or after configured idle periods.
• Explicit purge is only legal while the pool is quiescent.
• All pool-owned allocations are counted in total_alloc_bytes, total_free_bytes, live_bytes, peak_live_bytes.

Task Lifecycle #

sequenceDiagram
    participant App
    participant Pool
    participant Desc as TaskDescriptor
    participant W as Worker
    App->>Pool: submit(task_fn, ctx, opts)
    Pool->>Desc: acquire (DescCache or freelist)
    Desc->>Desc: state := reserved
    Pool->>Desc: write task_fn, ctx, options, submit_ns, generation
    Desc->>Desc: state.store(.queued, .release)
    Pool->>Pool: push entry {gen, idx} to lifo_slot / local / submitter / inject
    Pool->>W: notifySubmits + scanAndWake
    W->>Desc: pop entry, filter by gen
    W->>Desc: CAS state .queued -> .running
    W->>App: invoke task_fn(ctx)
    App-->>W: return
    W->>Desc: finalizeTask: state.store(.completed or .cancelled, .release)
    alt non-waitable
        W->>Desc: releaseDescriptor -> DescCache.push or freelist
    else waitable
        Note over W,Desc: wait() returns then triggers release
    end

1. Submission validates pool state and acquires a descriptor from the DescCache / bounded freelist.
2. The descriptor is enqueued either to the caller worker's LIFO slot, the caller worker's local deque, a submitter queue, or the central inject queue.
3. A worker dequeues, steals, or refills and transitions the descriptor to running via CAS.
4. The task executes exactly once.
5. The descriptor transitions to completed or cancelled.
6. Detached descriptors return to the DescCache / freelist immediately; waitable descriptors return after wait.

Task panic behaviour (REV-001) #

task_fn must not panic. Zig panics are non-catchable by design — an integer overflow, OOB access, @panic, or unreachable in user code aborts the entire process. This is the correct outcome for a production pool: a panicked task leaves counters.active_tasks incremented, descriptor.claimed_by set, and the matching WaitGroup.pending undecremented. Core.runTask cannot recover because the control flow never returns.

Callers that install a process-wide custom panic handler (e.g. a debugger hook or a crash reporter) must not resume execution into the pool after catching a panic. If they do, the pool cannot self-heal; the only observable signal is Stats.accounting_skew_detected = true across multiple consecutive snapshots. See docs/security/REV-001.md for the ADR and src/pool.zig::runTask for the contract comment.

Descriptor reuse and idempotent wait() (SEC-018) #

releaseDescriptor is CAS-guarded on descriptor.state so concurrent wait() callers on the same handle cannot double-push the slot onto the freelist. Exactly one caller performs the release; others observe the state already .free (with a matching generation) and return success. A late wait() on a reused slot returns error.InvalidHandle via the generation-tag mismatch.

Gen-tagged queue entries #

Queue entries carry {u32 gen, u32 idx} packed into a u64. On every release, the descriptor's generation increments. runTask rejects any entry whose embedded gen does not match the descriptor's current gen — closes the recycled-slot double-dispatch race.

Before gen tags, the double-dequeue race fuzz gate hit 9/20; post-gen tags it's 20/20.

Shutdown Semantics #

flowchart LR
    Start[shutdown mode, timeout] --> Flag[state := shutting_down]
    Flag --> M{mode?}
    M -- drain --> Wait[Wait queued_tasks + active_tasks == 0]
    M -- cancel_pending --> Cancel[cancelQueuedTasks]
    Cancel --> Wait
    Wait --> WD[watchdog_stop := true]
    WD --> Broadcast[Broadcast park_cond all workers]
    Broadcast --> Join[Join worker threads]
    Join --> DrainCaches[Drain DescCaches to freelist]
    DrainCaches --> DrainSubs[Drain submitter_queues + desc_caches]
    DrainSubs --> Verify[Assert task_desc_live == 0]
    Verify --> Free[Free owned allocations]

drain #

• Reject new submissions.
• Let queued and running work finish.
• Join workers.
• Purge worker scratch.
• Release owned memory.

cancel_pending #

• Reject new submissions.
• Cancel tasks still in queues (state.cmpxchgStrong(.queued, .cancelled)).
• Running tasks continue to completion.
• Join workers and release resources.

Fairness and Tradeoffs #

• global_queue is simpler and sometimes slightly smaller in RSS because it lacks per-worker queue state.
• work_stealing reduces multi-producer contention and improves local handoff, but it is not currently lock-free (it is lock-free on the fast paths but not on the wake scan).
• Recursive submission is safe because worker-originated tasks preferentially target the caller's local LIFO slot.
• Blocking tasks are supported through lane metadata and lane_extension's dedicated workers + overflow spawn.

Performance-Relevant Design Choices #

Choice	Rationale	Where
64-worker cap	workers_nonempty is a single u64	Core.workers
64-submitter cap	submitter_free_mask is a single u64	registerSubmitter
Power-of-two queue sizes	mask instead of modulo	BoundedRing, RingQueue, WorkDeque
LIFO slot sentinel 0xFFFF_FFFF_FFFF_FFFF	Gen-tagged entries never collide	LIFO_SLOT_EMPTY
wake_coalesce_batch = 32 default	Amortises scan + futex cost	notifySubmits
inject_batch_size (32 default)	popMany amortises head-CAS	tryDrainLaneForWorker
steal_batch_size (8 default)	stealHalf copies rounded-up half	nextTask
End-of-struct Worker.desc_cache	Iter-11 showed layout-shift costs	src/pool.zig::Worker

Observability #

statsSnapshot() reports:

• task lifecycle counters
• queue depth current and peak (per lane)
• steal and steal-failure counts
• wakeups and parks (aggregate + per worker)
• per-worker busy / idle / scratch / local-queue metrics
• wait and execution latency summaries (when timestamp_mode = .full)
• wake-latency histogram per worker
• watchdog stall counter + overflow spawn/retire counters
• Linux / macOS / Windows process memory metrics

Comptime Elision Hooks #

Three -D flags allow specialisation that drops branches at compile time:

• -Dsingle-pool=true — elide per-pool TLS identity check (UNSAFE with >1 pool per process).
• -Dtimestamp-mode=<m> — pin Config.timestamp_mode to disabled/full; drops histogram writes.
• -Dscheduler-variant=<v> — pin Config.scheduler_variant; drops alternative scheduler's branches from the hot path.

See ALGORITHMS.md § Comptime Elision Hooks for the full map and measured gains.

Known Gaps #

• Adaptive grow/shrink is intentionally not implemented in phase 1. The L4b max_overflow_workers elastic spawn is watchdog-driven, not hysteresis-based.
• Per-task allocator-count metrics are not yet separate from byte accounting.
• Non-x86 platforms have not been benchmarked end-to-end; the queue primitives use std.atomic.Value so correctness is portable but tuning constants are empirical for x86_64.

Further Reading #

• ALGORITHMS.md — mermaid diagrams for every pipeline
• architecture.md — component + ownership map
• BENCHMARKS.md — measurement protocol + current numbers
• PERFORMANCE_TRACKING.md — phase-by-phase deltas
• SCHEDULER_DECISION.md — variant-picking rubric