Crate kovan 

Kovan: High-performance wait-free memory reclamation for wait-free data structures. Bounded memory usage, predictable latency.

Kovan implements a asynchronous safe memory reclamation (SMR) algorithm.

Progress Guarantees (precise)

Every core operation completes in a bounded number of its own steps, whatever other threads do, including threads stopped for good at any point of theirs: no step waits for another thread, and no loop retries because another thread got in first more often than the bound below allows. T is the number of thread IDs handed out (at most 65,536); a step is one atomic instruction, as it is on x86_64 and on aarch64 with LSE (an LL/SC read-modify-write is the hardware’s own retry loop; on targets whose 128-bit atomics are emulated with a lock, reclamation is not lock-free at all, see Supported Platforms in README.md).

• Protected loads (Atomic::load, Atom::load): wait-free. The common case is one pointer load plus one epoch compare. If the global epoch keeps advancing, the load re-publishes at most 15 times; then it escalates to an unconditional reservation (the slot becomes eligible for every batch) and completes with one final load.
• pin(): wait-free. A nested pin, or an outermost one that finds the global epoch where its thread’s last transition left it, is a counter update. Otherwise a transition: at most 16 attempts, each one walk of the thread’s own slot list (see below) and one publication, then a slow path whose loop passes once more only for an epoch advance made by a thread that had not yet seen its help request: every advance helps the pending requests first, and a helper completes the request. A thread’s first pin also claims a thread ID: one pass over the released IDs, no lock.
• retire(), retire_reclaimable(): wait-free. O(1) per call; every 64th submits the batch (one pass over the slots, one insert per eligible slot); the first, every 128th after and every one that placed a batch help the pending slow-path requests (O(T) each) and advance the epoch.
• Guard drop: wait-free (a counter store; plus one slot transition when the section escalated to an unconditional reservation).
• flush() and thread exit: wait-free, a fixed sequence of the steps above; batches an exiting thread cannot place are parked on its thread ID and adopted by flush(), both without a lock: one load tells whether any ID holds parked batches, and each call adopts one ID’s chain, on a thread that never pinned too. A thread that never pinned claims a thread ID first, as a first pin does, in flush() while some batch is parked or its own batch holds values it retired, and at exit while its batch holds values.

Every walk of a slot list takes the list with one exchange first, so it is as long as the list was at that instant: one entry per batch submitted while the slot was eligible, since its previous walk. What other threads insert meanwhile starts a new list, and an insert still linking its entry ends the walk there (the inserter walks the rest), so no walk grows while it runs. A thread that stays away from its slot for long owes a walk as long as what was retired meanwhile; flush() before idling avoids that (see Quiescence).

The destructors of retired values run inside these operations (the batches a walk frees); each kovan call a destructor makes is an operation of its own, with the same bounds.

Atom::rcu re-applies its closure on contention, as read-copy-update requires, so it is lock-free: an attempt fails only after another thread’s write. Atom::compare_and_swap makes one attempt. The kovan primitives they compose (load, store, retire) are individually wait-free.

Key Properties

• Near-zero read overhead: the hot read path is a single atomic pointer load plus an epoch check against a thread-local cache.
• Bounded Memory: Retired nodes are reclaimed in batches. Batches that cannot be placed are accumulated or adopted, never dropped. A stalled reader only delays batches containing nodes born before its pinned epoch; younger garbage remains reclaimable. (A reader stalled inside an escalated critical section defers all younger batches until it resumes: escalation windows are bounded by the critical section that triggered them.)
• no_std Compatible: Uses only alloc. No standard library required.

Architecture

• Per-thread epoch slots: Each thread maintains a slot recording its current epoch. Slots are protected by 128-bit DCAS (double compare-and-swap).
• Batch retirement: Retired nodes are accumulated in thread-local batches (at least 64; batches grow under high thread counts so each eligible slot can receive a node) and distributed across active slots via try_retire.
• Wait-free helping: Threads in the slow path publish their state so other threads can help them complete, ensuring system-wide progress.

Quiescence

A thread’s reservation slot stays active after its last Guard drops; it is refreshed/drained on the next pin(), flush(), or thread exit. Long-idle threads that once pinned should call flush before idling to release retained garbage promptly: with no guard live, flush() also leaves the slot holding nothing back until the thread pins again.

Recycling node memory (the recycle feature)

A structure that publishes nodes allocates each one with alloc_node and lets it go with retire_node, drop_node or free_node (every structure of the kovan crates does). Without the recycle feature, off by default, these are Box allocations, frees and retire. With it, the memory of a node of up to 1 KiB, aligned to at most 16 bytes, goes back to a per-thread magazine cache of its size class when the node is freed, and the next node of that size takes it from there: a thread that frees about as much as it allocates makes no call into the global allocator, and threads that only allocate or only free trade full and empty magazines through a bounded lock-free depot per class. The magazines hold at most 64 blocks per class per thread and 512 per class in the depot. Under them, blocks are carved from 8 KiB chunks taken from the global allocator one at a time, so even a run of allocations the magazines cannot serve costs one allocator call per chunk, and a chunk goes back to the global allocator once all its blocks are free (a chunk with one long-lived node keeps its 8 KiB). A thread’s magazines go back to the depot when it exits, and its chunks are freed by whichever thread gives back each one’s last block.

Whether the cache is faster depends on the global allocator it replaces. Against glibc’s, node churn takes a quarter to a half fewer instructions; against mimalloc, whose fast path is shorter than the cache’s, it takes 3 to 11% more. Measure with the program’s own allocator before turning it on.

Turn it on in the application, never in a library: Cargo enables a feature for every crate of the build at once, so a library that turns it on turns it on for every kovan structure of the programs that depend on it, theirs too.

Example

use kovan::Atom;

// High-level API: safe, zero-overhead reads
let config = Atom::new(vec![1, 2, 3]);
let guard = config.load();
assert_eq!(guard.len(), 3);

Structs

Atom

A single-value container with safe memory reclamation: loads, stores and swaps are wait-free, and rcu() is lock-free (it retries only after another thread’s write).

AtomGuard

RAII guard returned by Atom::load().

AtomMap

A projected view into an Atom<T>, created by Atom::map().

AtomMapGuard

Guard for a mapped/projected load.

AtomOption

Like Atom<T> but allows a null/empty state.

Atomic

A pointer to a heap-allocated value with atomic operations.

CachePadded

Wraps T, padding and aligning it to the target’s effective cache line size so a value never shares a line with an unrelated, independently accessed neighbor (false sharing).

Guard

RAII guard representing an active critical section.

NodeBox

An owned node from alloc_node that is not published yet: it drops its value and frees itself when dropped, like a Box, through the node helpers (so under the recycle feature its memory goes back to the magazine cache).

Removed

A value removed from an Atom or AtomOption.

RetiredNode

Node structure embedded in user’s data structure.

Shared

A pointer to a heap-allocated value protected by a guard.

Enums

Ordering

Atomic memory orderings

Traits

Reclaimable

Trait for types that can be reclaimed by the wait-free memory reclamation system.

Functions

alloc_node

Allocates a node holding value and returns a pointer to it, for Atomic::new or a store or compare-and-swap of an Atomic.

alloc_node_uninit

Allocates the memory of a node of T, its value not yet written, for a node whose fields are written in place.

drop_node^⚠

Drops the value of a node from alloc_node and frees the node now.

flush

Flush all retired nodes on the calling thread.

flush_pending

Submits this thread’s batch of retired nodes to reclamation now, as flush does, when it holds one; with nothing retired on this thread since its batch was last submitted it does nothing. A structure’s drop calls it: what its thread retired goes to reclamation without waiting for the batch to fill, and a drop that retired nothing costs no epoch advance (flush makes one, which sends every other thread’s next pin down its slow path).

free_node^⚠

Frees the memory of a node from alloc_node or alloc_node_uninit without dropping a value: one that was never written, or was moved out.

pin

Enter a critical section.

retire^⚠

Retire a node for later reclamation.

retire_node^⚠

Retires a node from alloc_node that was unlinked from every Atomic: once no guard can reach it, its value is dropped and its memory freed (to the magazine cache under the recycle feature), as retire does for a Box.

retire_reclaimable^⚠

Retire a node whose deallocation is its Reclaimable::dealloc.