Module sync 

Runtime-independent synchronization primitives: futures and wakers only, usable from any executor. Nuclei’s runtime-independent synchronization primitives: locks, a semaphore, events, a barrier, once-cells and channels that never block a thread.

Every wait in this module is a Future built from futures and wakers only: async code awaits it, and any executor polls it with its own Waker. Every primitive also has try_ forms that never wait. The core of this module makes no system call: no futex, no thread park, no sleep and no clock read. The one exception is inside the lock-free queues the primitives use, which recycle waiter nodes and yield the thread when they meet contention. The other exception is the blocking_* methods, which exist for threads that may block and park the calling thread until their wait is over. Called on a nuclei shard (inside one of its tasks) they run a nested block_on instead, so the shard keeps running its other tasks; called inside another runtime’s task they block the thread that task runs on.

Names and signatures

Mutex, RwLock, Semaphore, Notify, Barrier, OnceCell and SetOnce take the names, signatures, error types and documented behavior of the established async sync API, so code written against that API compiles against these. The guards and errors sit at the same paths under nuclei::sync, and the waits are named futures (Lock, Read, Acquire, and so on) rather than opaque ones. A semaphore holds at most Semaphore::MAX_PERMITS permits, which is usize::MAX >> 7. What this module adds is the Event, the Latch, the Lazy value, the upgradable read of the RwLock, the reentrant locks and OnceCell::get_or_init_racy. The mpsc channels follow the same rule for the established channel API, with their own progress notes. The local module adds single-shard twins of the channels, the semaphore and the mutex, with no atomic instruction on any path, and mesh a full mesh of bounded channels between a fixed number of parties.

What every primitive guarantees

• No runtime. A contended acquire queues a waiter, registers the caller’s Waker and returns Pending. What a wake does belongs to the caller’s executor. Within one poll, a contended acquire of a lock or a semaphore may first spin for a short while (up to the lock’s spin budget, a count of pause instructions it adapts to how long holds last, about 5 microseconds at most on the cores it was tuned on): before it queues, and again after a retry it lost. The spin makes no system call, reads no clock, and ends in the same queueing or the same Pending as before. Locks whose holders keep them across long waits of their own do not spin, and their contended callers queue at once: the once-cell’s initializer turn, for example.
• Fast under contention. The locks and the semaphore let a caller take what is free even while others wait, so a release never waits for a suspended task to run: the thread that released takes the lock straight back.
• Bounded bypass. A release wakes the oldest waiters it could serve to compete again. One that loses MAX_BYPASS times is owed a handoff: nobody gets in ahead of it, and the next release hands it what it waits for directly. Fairness is counted, never timed.
• Cancellation-safe. Dropping a pending future withdraws its waiter. If something was handed to it concurrently, the drop passes it on. No wakeup is lost. (A Barrier wait is the one exception: an arrival that was counted stays counted.)
• Cooperative on a nuclei shard. In a task on a nuclei shard (or in block_on’s own future), a receive of mpsc, oneshot, broadcast or watch that completes spends one operation of the task’s cooperative budget, as IO does (task::coop), and so does an acquire of a semaphore, a lock (the reentrant ones too) or a bounded send that completes at its first attempt. When the budget is spent the call completes nothing, wakes its task and returns Pending, so a loop on a channel or a lock that is always ready yields to the shard’s other tasks. A wait that queued and was granted spends nothing: giving the grant back would cost it its place. The try_ forms never spend, and off a nuclei shard there is no budget. The events, latches, barriers, once-cells and Notify keep no budget.
• Reentrancy by Owner. The reentrant locks are keyed by an owner token rather than a thread, because a task can move between threads and many tasks can share one.
• Every target. State lives in word-sized atomics (in plain cells in local, whose types stay on one thread). On single-threaded wasm the same code runs on one thread, where only interleaved tasks contend. The fast paths allocate nothing; a waiter node comes from a per-primitive free list and reaches the allocator only when that list is empty.

How a wait works

Each primitive keeps one state word, a lock-free stack of arriving waiters and a FIFO of the waiters already sorted. Uncontended calls touch the state word only, one atomic read-modify-write each. Anything that can make a waiter runnable (a release, a new waiter, a cancellation) takes the drain role with one compare-and-swap, or, when another thread holds it, leaves a mark for the holder and returns, so no call ever waits for another. The holder wakes what the state allows (or, while a handoff is owed, grants it in queue order), rechecks until nothing changed while it worked, and calls the wakers after it has given the role up.

Progress

Every operation is lock-free, not wait-free. No call waits for another thread, and some call always completes; but a call may do work on behalf of others, and how much depends on them.

• Uncontended, an acquire and a release are one atomic read-modify-write each.
• A call that can make a waiter runnable (a release with waiters, a new waiter, a cancellation, a notification, a semaphore’s close, a write guard’s downgrade, add_permits) may serve the queue itself. It returns after one pass over the queue, plus at most one more pass for each of these that lands while it works: a waiter that queues, a waiter that withdraws, a waiter that claims the handoff it is owed, and a release that finds a node queued.
• forget_permits wakes nobody: it is a compare-and-swap loop on the state word, which retries only when another call changed the word first. A barrier’s arrival is one fetch_add, followed, for the arrival that completes a group, by the pass that wakes the group.
• A release over an empty queue earns no pass; a release that finds a node queued earns one. So releases alone never keep a thread at work. Waiters that keep queueing or withdrawing can, one pass each: every such pass is another thread’s own operation getting done, which is what lock-free means, and there is no cap on the passes of one call.

Besides the primitives, this module re-exports a lock-free map (HopscotchMap), queues (SegQueue, ArrayQueue) and Atom, so one module holds every synchronization structure.

Modules

broadcast

A multi-producer, multi-consumer broadcast channel: each value sent reaches every receiver that exists when it is sent.

futures

Named future types, at the conventional sync::futures path.

local

Synchronization primitives for the tasks of one shard.

mesh

A full mesh of bounded channels between a fixed number of parties.

mpsc

Multi-producer, single-consumer channels for sending values between tasks.

oneshot

A channel that carries one value from one sender to one receiver.

watch

A multi-producer, multi-consumer channel that retains only the last sent value.

Structs

Acquire

The future Semaphore::acquire and Semaphore::acquire_many return.

AcquireError

Error returned from Semaphore::acquire and the other waits for permits.

AcquireOwned

The future Semaphore::acquire_owned and Semaphore::acquire_many_owned return.

ArrayQueue

A bounded lock-free queue, from the kovan-queue crate: see its docs. A bounded multi-producer multi-consumer queue.

Atom

An atomically swapped value, from the kovan crate: see its docs. 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).

Barrier

A barrier that releases its waiters in groups of n.

BarrierWait

The future Barrier::wait returns.

BarrierWaitResult

What a completed Barrier::wait reports.

CancellationToken

A token which can be used to signal a cancellation request to one or more tasks.

DropGuard

A wrapper for a CancellationToken which cancels it on drop, created by CancellationToken::drop_guard.

DropGuardRef

A wrapper for a borrowed CancellationToken which cancels it on drop, created by CancellationToken::drop_guard_ref.

Event

An event that is set once and stays set.

EventWait

The future Event::wait returns.

HopscotchMap

A concurrent hash map, from the kovan-map crate: see its docs. A concurrent, lock-free hash map based on Hopscotch Hashing.

Latch

A latch that opens when its count reaches zero, and stays open.

LatchWait

The future Latch::wait returns.

Lazy

A value built by F on first access.

Lock

The future Mutex::lock returns.

LockOwned

The future Mutex::lock_owned returns.

MappedMutexGuard

A guard for a component of a Mutex’s value, made by MutexGuard::map; unlocks on drop. The release makes the progress MutexGuard’s does.

Mutex

A mutual-exclusion lock whose wait is a future.

MutexGuard

Exclusive access to a Mutex’s value; unlocks on drop.

Notified

The future Notify::notified returns.

Notify

Wakes tasks waiting for an event that carries no value.

OnceCell

A cell that is written at most once.

OwnedMappedMutexGuard

A guard for a component U of the value of a Mutex<T> held through an Arc, made by OwnedMutexGuard::map; unlocks on drop. The release makes the progress MutexGuard’s does.

OwnedMutexGuard

Exclusive access to a Mutex held through an Arc; unlocks on drop. The release makes the progress MutexGuard’s does.

OwnedNotified

The future Notify::notified_owned returns: Notified that keeps its Notify alive itself.

OwnedRwLockMappedWriteGuard

Exclusive access to a component U of the value of a RwLock<T> held through an Arc, made by OwnedRwLockWriteGuard::map; releases on drop. The release makes the progress RwLockReadGuard’s does.

OwnedRwLockReadGuard

Shared access to a RwLock held through an Arc, to its value or to a component U of it; releases on drop. The release makes the progress RwLockReadGuard’s does.

OwnedRwLockWriteGuard

Exclusive access to a RwLock’s value through an Arc the guard holds; releases on drop. Made by RwLock::write_owned. The release makes the progress RwLockReadGuard’s does.

OwnedSemaphorePermit

Permits taken from a Semaphore held through an Arc. The release makes the progress SemaphorePermit’s does.

Owner

A token that identifies the holder of a reentrant lock.

Read

The future RwLock::read returns.

ReadHeldByOwner

Why a ReentrantRwLock::write failed: its owner reads without writing, so the write would wait for a read only that owner can end. Release the reads first, or take the write before reading.

ReadOwned

The future RwLock::read_owned returns. It keeps its place in the queue, and the bypasses it counted, for as long as it lives; dropping it withdraws the wait and passes on a lock handed to it meanwhile.

ReentrantMutex

A mutex the owner holding it can lock again without waiting.

ReentrantMutexGuard

Shared access to a ReentrantMutex’s value; drops one level of the hold. The drop of the last level releases the lock, which is lock-free, not wait-free: with waiters it returns after one pass over the queue, plus at most one for each operation of another thread that lands on the queue meanwhile (see Progress).

ReentrantMutexLock

The future ReentrantMutex::lock returns.

ReentrantRead

The future ReentrantRwLock::read returns.

ReentrantReadGuard

One read of a ReentrantRwLock; drops one level of the owner’s reads. The drop of the last level releases the read, which is lock-free, not wait-free: with waiters it returns after one pass over the queue, plus at most one for each operation of another thread that lands on the queue meanwhile (see Progress).

ReentrantRwLock

A reader-writer lock its holders may lock again, with the bounded bypass of RwLock.

ReentrantWrite

The future ReentrantRwLock::write returns.

ReentrantWriteGuard

One write of a ReentrantRwLock; drops one level of the owner’s writes. The drop of the last level releases the write, with the progress ReentrantReadGuard’s release makes.

RwLock

A reader-writer lock whose waits are futures.

RwLockMappedWriteGuard

Exclusive access to a component of a RwLock’s value, made by RwLockWriteGuard::map; releases on drop. The release makes the progress RwLockReadGuard’s does.

RwLockReadGuard

Shared access to a RwLock’s value, or to a component of it; releases on drop.

RwLockUpgradableReadGuard

The upgradable read of a RwLock: shared access that can become exclusive without a writer getting in between. Releases on drop, with the progress RwLockReadGuard’s release makes.

RwLockWriteGuard

Exclusive access to a RwLock’s value; releases on drop. The release makes the progress RwLockReadGuard’s does.

SegQueue

An unbounded lock-free queue and its pop error, from the kovan-queue crate: see its docs. An unbounded, lock-free, linearizable FIFO queue for many producers and many consumers.

Semaphore

A counting semaphore whose waits are futures.

SemaphorePermit

Permits taken from a Semaphore, returned when dropped.

SetOnce

A cell that is set once, and that readers can wait on until it is.

SetOnceError

Error returned from SetOnce::set: the cell was set already, or another set is setting it now. The value comes back.

ThreadOwner

The calling thread’s Owner, from Owner::thread.

TryLockError

Error returned from Mutex::try_lock, RwLock::try_read and RwLock::try_write and their _owned forms.

UpgradableRead

The future RwLock::upgradable_read returns.

Upgrade

The future RwLockUpgradableReadGuard::upgrade returns. Dropping it before it completes releases the upgradable read.

WaitForCancellationFuture

A future that resolves once the corresponding CancellationToken is cancelled.

WaitForCancellationFutureOwned

A future that resolves once the corresponding CancellationToken is cancelled, and owns the token.

Write

The future RwLock::write returns.

WriteOwned

The future RwLock::write_owned returns. It keeps its place in the queue, and the bypasses it counted, for as long as it lives; dropping it withdraws the wait and passes on a handoff made to it meanwhile.

Enums

SetError

Errors that can be returned from OnceCell::set.

TryAcquireError

Error returned from Semaphore::try_acquire and the other attempts that never wait.

TryPopError

An unbounded lock-free queue and its pop error, from the kovan-queue crate: see its docs. Why SegQueue::try_pop returned no value.

Constants

MAX_BYPASS

How many times a waiter can be passed over before it is owed a handoff: a woken waiter that loses its retry this many times is handed the next release directly, and nobody barges past it meanwhile.