Waiting is a primitive_

A semaphore holds no tokens. One thread waits up to ten milliseconds while another releases a token exactly as the deadline expires. If release reports success and the waiter reports a timeout, the token disappears. The next acquire then sleeps even though a token was released.

Our runtime put waiting beneath locks, semaphores, and events. The kernel operation was simple: sleep on this address only while its word still equals an expected value. The library had to turn that conditional sleep and a wake call into correct timeouts on every platform.

The hard part is deciding who owns the token when a release and a timeout happen together.

A word and two calls

The primitive is wait-on-address, usually called a futex. Wait takes a 32-bit word and an expected value. The kernel sleeps only if the word still matches. Notify wakes threads queued on the same address. There is no separate kernel object or handle, and the kernel stays out of the path until a thread sleeps.

The comparison closes a lost-wakeup window. Without it, a consumer can read zero, then miss a producer setting the flag and notifying just before the consumer sleeps. The notification wakes nobody, and the consumer sleeps forever. Wait-on-address compares the word after the thread is committed to the queue. If the producer changed it, the wait returns immediately.

The caller still writes a loop that reads the word and decides. The wait call only keeps the decision and the sleep from coming apart.

One more clause in the contract: a wait may also wake for no reason at all. These spurious wakeups are part of the contract, so every caller loops: wake, re-check the word, wait again if nothing changed.

Platforms expose different versions of these calls. Some can wake an exact count, some offer only wake-one or wake-all, and some have no address-based wait.

A counter that goes negative

A counting semaphore adds blocking to a counter. Acquire takes a token or waits. Release adds tokens and wakes waiters. Keeping tokens and waiter counts separately requires either a lock around the pair or a double-width atomic. The first serializes the common path. The second is unavailable on some platforms.

The futex-based semaphore in the library keeps one number and lets it go negative. Positive means tokens available. Zero means no tokens and no outstanding waiter claims. Negative values count claims that releases must account for. A thread can hold such a claim while entering the kernel, sleeping, waking, or resolving a timeout, so the magnitude is not a moment-by-moment count of sleeping threads.

Start at 2 and let four threads acquire. The first two decrement to 1 and 0 without entering the kernel. The next two decrement to minus 1 and minus 2, then sleep on the counter's address. The result of each atomic decrement tells the caller whether it took a token or must wait.

Release is where the one-word encoding matters. The shape of it, simplified:

void sem_post(int n) {
    int32_t old = counter.fetch_add(n, std::memory_order_release);
    if (old < 0)
        // -(int64_t)old avoids the INT32_MIN negation overflow
        notify(&counter, (int)std::min<int64_t>(n, -(int64_t)old));
}

The common release is one locked add, a sign test, and a return. It calls wake only when the old counter was negative.

; clang-18 -O2 (x86-64), sem_post
    mov       esi, edi
    lock xadd dword ptr [rip + counter], esi  ; bump; esi = old value
    test      esi, esi
    js        .wake                           ; only if old < 0: waiters parked
    ret                                       ; common path: no syscall at all

On the ARM core I also build for, the same release compiles to ldaddl, one atomic add with the release ordering carried in the opcode's trailing letter, followed by the same sign test and the same branch to the wake path. The shape is identical and only the memory model's visibility changes.

Release three tokens into minus 2. The add moves the counter to 1 and returns its old value, which says there were two waiter claims. Release wakes min(3, 2), or two threads. The remaining token stays in the positive counter.

Token count and outstanding waiter claims live in one word, and each counter operation observes both in the atomic step that changes it. The kernel separately tracks which registered threads are actually asleep.

The counter can overflow. The semaphore guarantees a maximum count, and a clamp engages only past twice that maximum to keep the check off the common path. Correct callers stay below the guarantee. Without the clamp, overflow flips the sign and looks like waiters that do not exist.

The release formula leans on two assumptions: the waiting count is accurate, and the kernel can wake an exact number of threads. A waiter that gives up on a timeout threatens the first.

Timing out without losing a wakeup

Timed waits are part of the semaphore's API: take a token, but do not wait past a deadline. Every unit below zero is an outstanding claim that a release must resolve. A waiter whose deadline expires tries to remove its claim with a CAS that raises the counter by one.

Suppose the counter is minus 1 when the deadline and a release arrive together. Release runs first, moves the counter to 0, and wakes the waiter. The waiter's CAS then tries to remove its claim by changing minus 1 to 0. It fails because release already changed the counter.

If the waiter reported a timeout after losing that CAS, the released token would be recorded nowhere. The next acquire would decrement 0 to minus 1 and sleep.

The timed-out waiter has two exits. If its removal CAS succeeds, it restores the count and reports timeout. If removal loses to a release, it loops and returns success because that release already assigned its claim a token. A waiter leaves by removing its own claim or by consuming the token assigned to it, never both.

That takes care of the first assumption, the accurate waiting count. The second does not hold everywhere: not every kernel can wake an exact number of threads.

Exact wakes and fallbacks

Some kernels wake an exact count. Others offer only wake-one or wake-all. Semaphore release wants exactly min(released, waiting), so the second group needs a fallback.

Fake it with wake-one and you get serialized wakeups: one kernel call per thread, where each call is its own round trip and the last waiter stays asleep until the last call reaches it. Fake it with wake-all and you get the thundering herd: every waiter stands up, the two with tokens proceed, and the rest re-check the word, find nothing for them, and file back to sleep. Each of those threads did a full wake and sleep for nothing, and all of them hit the same cache line on the way through.

The caller knows which fallback fits. Releasing one token into many waiters favors wake-one. At a phase boundary, every waiter must run, so wake-all avoids one kernel round trip per thread.

The notify API therefore takes a fallback strategy from the call site. On kernels with exact-count wakes, the argument changes nothing.

Both fallbacks remain correct. A thread woken without a token checks the word and sleeps again. A serialized wake arrives later. The strategy changes only the cost.

The platforms with nothing underneath

Some supported platforms had no wait-on-address facility. New ports still needed a correct implementation before any tuning could begin.

What exists nearly everywhere is the older pair, a mutex and a condition variable. A condition variable lets a thread unlock a mutex and go to sleep as one atomic step, and lets another thread wake the waiters. A woken thread returns holding the mutex and re-checks whatever fact it was waiting on. It closes the same lost-wakeup window the futex's expected value closes, with the mutex playing the role of the check.

The portable fallback uses one global mutex and condition variable for every address. Broadcast is correct but wakes unrelated threads. Repeated notify_one is not correct because a notification for A may wake B while A remains asleep.

The fallback refuses to compile on platforms with a native facility. The native implementation refuses to compile where none exists. Each port declares which one it uses, so an accidental switch fails the build.

A lock made of one token

Those fallback platforms also need a mutual-exclusion lock. Writing another lock state machine would add concurrency code on the ports with the youngest toolchains and weakest debugging support.

The fallback lock is the capped counting semaphore with capacity one, pre-loaded with one token. Release uses a compare-exchange loop to clamp the count to the cap. If the count is already one, a second release returns zero and leaves it unchanged. This prevents an over-release from creating a second permit. Other lock misuse is unaffected.

An uncontended acquire decrements 1 to 0 and enters without the kernel. A contended acquire decrements 0 to minus 1 and sleeps. The counter's magnitude is the number of queued threads. Unlock releases one token, and the returned old value says whether anyone needs waking. The lock inherits the semaphore's negative counter, timeout race, and wake strategy with its capacity fixed at one.

Testing the timeout

A single 1 millisecond sample is meaningless on a coarse scheduler and may even measure as zero without indicating a bug.

The suite executes a 1 ms timed wait one thousand times and requires at least 500 ms in total. That catches large conversion mistakes and sentinel collisions. A smaller early-return error could still pass, so this is a coarse conversion regression test rather than a per-wait accuracy measurement.

The floor is one-sided because only early firing breaks the caller: a caller that asked to wait a millisecond is entitled to assume the millisecond has passed when the call returns empty-handed.

A notification with no waiter

A semaphore remembers unused tokens in its counter. The wait primitive must not remember notifications. A notify with nobody waiting has to disappear, or the kernel would hold a second token count that can disagree with the semaphore.

The test notifies with nobody waiting, then waits on an unchanged word. The wait must still block.

The fast path that never shipped

One supported desktop OS had undocumented private wait calls. A version built on them was faster than the supported route. It stayed compiled and tested in every build.

It stayed switched off because an OS update could change the private interface without notice. Keeping it in the build prevented compiler and API changes from silently breaking the option.

The private call takes its timeout in microseconds, and zero microseconds means wait forever. A caller passing a zero-millisecond timeout means something close to the opposite, the shortest wait expressible. A straight unit conversion turns zero milliseconds into zero microseconds, which the kernel reads as forever. So the conversion clamps zero milliseconds to one microsecond, the smallest value the field can carry that still means finite.

Larger requests clamp to the field's one-hour maximum. The caller wakes, checks the word, and waits again. That behavior is already legal under the spurious-wakeup contract.

Another OS accepts milliseconds and treats all ones as infinite. As a finite duration, that value is about fifty days. The conversion subtracts one millisecond so a numeric timeout can never become the infinite sentinel.

// clamp zero up to the 1us minimum, saturate anything past the 32-bit field
uint32_t to_timeout_us(int64_t us) {
    if (us <= 0)             return 1;            // never a zero-length wait
    if (us > 0xFFFFFFFFll)   return 0xFFFFFFFFu;  // saturate the field
    return (uint32_t)us;
}

; clang-18 -O2 (x86-64), to_timeout_us: two clamps, no branches
    mov       ecx, 4294967295
    cmp       rdi, rcx
    cmovb     rcx, rdi        ; rcx = min(us, 0xFFFFFFFF)
    test      rdi, rdi
    mov       eax, 1
    cmovg     eax, ecx        ; us > 0 ? the clamped value : 1
    ret

The tests preserve each kernel rule: the meaning of zero, the all-ones sentinel, and the limit of a 32-bit field.

The implementation remained tested and switched off. As far as I know, it never shipped.