vault

Runtime Semaphore

13 min read

Runtime Semaphore

The runtime semaphore is the single low-level sleep/wakeup primitive that sits underneath every sync package type — Mutex, RWMutex, WaitGroup, and (via a sibling notifyList) Cond. It is implemented in src/runtime/sema.go and exposed to the sync package through a handful of //go:linkname-bridged functions named semacquire/semrelease. Despite the name, the runtime comment is emphatic: “don’t think of these as semaphores — think of them as a way to implement sleep and wakeup such that every sleep is paired with a single wakeup, even if, due to races, the wakeup happens before the sleep” (sema.go). The design is lifted directly from Mullender and Cox’s Semaphores in Plan 9 (swtch.com/semaphore.pdf).

Mental Model

A runtime semaphore is not one object. It is a convention: any *uint32 in memory can be used as a semaphore address. Its integer value is the count of available “permits”; goroutines that find the count at zero park themselves on a global side-table keyed by that address, and a release walks the side-table to wake exactly one waiter.

The crucial inversion to internalize: the sync.Mutex does not contain a wait queue. The mutex contains a tiny sema uint32 field whose address is the lookup key. The actual queue of blocked goroutines lives in a global structure called semtable, completely separate from the mutex itself. This is why a sync.Mutex is only two words wide regardless of how many goroutines are contending on it — the contention state is externalized.

graph TD
    subgraph "User memory"
      M1["sync.Mutex A<br/>sema uint32 @ 0x1000"]
      M2["sync.Mutex B<br/>sema uint32 @ 0x2080"]
    end
    subgraph "Global semtable [251 semaRoots]"
      R0["semaRoot[hash(0x1000)]<br/>lock + treap + nwait"]
      R1["semaRoot[hash(0x2080)]<br/>lock + treap + nwait"]
    end
    M1 -.->|"rootFor(addr)"| R0
    M2 -.->|"rootFor(addr)"| R1
    R0 --> T0["treap of sudog<br/>keyed by distinct addr"]
    T0 --> L0["addr 0x1000 → sudog → sudog → sudog<br/>(O(1) inner wait list)"]

    caption["semtable is a fixed 251-bucket hash table of semaRoots.<br/>Each semaRoot holds a treap of sudogs keyed by *distinct address*;<br/>multiple goroutines blocked on the SAME address chain in an inner O(1) list."]

Diagram: the runtime semaphore is a global side-table, not a field of the mutex. The insight: a sync.Mutex stays two words wide because all blocked-goroutine bookkeeping is offloaded to semtable, indexed by the mutex’s address.

Mechanical Walk-through

The data structures

The global semtable is [251]struct{ root semaRoot; pad [...]byte } — a fixed-size hash table. 251 is prime “to not correlate with any user patterns” (sema.go). The pad field rounds each entry up to a cache-line boundary so that two unrelated semaRoots never land on the same cache line and cause false sharing.

rootFor picks the bucket: &t[(uintptr(addr)>>3) % 251].root. The >>3 discards the low three bits because addresses of uint32 semaphores are at least 4-byte aligned and the shift improves bucket spread.

A semaRoot is:

type semaRoot struct {
    lock  mutex          // a runtime-internal spinlock, NOT a sync.Mutex
    treap *sudog         // root of balanced tree of unique waiter addresses
    nwait atomic.Uint32  // number of waiters, readable WITHOUT the lock
}

The treap is a treap — a binary search tree ordered by semaphore address, kept balanced on average by simultaneously maintaining a min-heap on a random ticket priority assigned to each node (Wikipedia: Treap, Aragon & Seidel 1989). Scanning the treap to find a waiter address is O(log n) in the number of distinct addresses hashing to that bucket.

The two-level structure matters. Each treap node is a sudog (“sleeping g union dog” — the runtime’s per-blocked-goroutine descriptor) for one distinct address. If many goroutines block on the same address (highly contended mutex), they do not each become a treap node — they chain off the head node through s.waitlink into an inner list with O(1) push/pop. This second level was added in response to issue #17953, where a program contending many goroutines on one address degraded the treap into a pathological shape.

Acquire — semacquire1

The fast path of semacquire1(addr, ...) calls cansemacquire(addr): atomically load the count, and if non-zero, compare-and-swap it down by one. If that succeeds, the goroutine got a permit without ever touching the table or a lock — this is the uncontended case and costs one successful CAS.

The slow path is a loop carefully ordered to be race-free against a concurrent release:

  1. Acquire root.lock (a runtime spinlock).
  2. root.nwait.Add(1) — increment the waiter count first. This is the linchpin: it disables the “easy case” fast-exit inside semrelease before this goroutine commits to sleeping.
  3. Call cansemacquire(addr) again. A release may have bumped the count between the fast-path check and now; if so, undo the nwait increment, unlock, and return.
  4. Otherwise call root.queue(addr, s, lifo) to insert the sudog into the treap, then goparkunlock — which atomically releases root.lock and parks the goroutine (transitions it to _Gwaiting and yields the M to the scheduler).
  5. When woken, re-check s.ticket != 0 || cansemacquire(addr); loop if neither holds (spurious wakeup defense).

The ordering of steps 2 and 3 is the entire correctness argument. A semrelease that runs after the nwait.Add(1) is guaranteed to see nwait != 0 and therefore take its slow path and look for a waiter. A semrelease that runs before it has already incremented the count, so the re-check in step 3 sees it. There is no window for a missed wakeup.

Release — semrelease1

semrelease1(addr, handoff, ...) does:

  1. atomic.Xadd(addr, 1) — bump the count. This happens before the nwait read, mirroring the acquire ordering.
  2. Easy case: if root.nwait.Load() == 0, there are no waiters — return immediately, no lock taken. This lock-free fast path is why an uncontended Unlock() is cheap.
  3. Slow case: acquire root.lock, re-check nwait (another releaser may have consumed it), then root.dequeue(addr) to find and remove the first waiter blocked on addr.
  4. Unlock, then readyWithTime(s, ...) makes the woken goroutine [[Goroutine Lifecycle and States|_Grunnable]] and places it on a run queue.

Direct handoff and the starvation regime

semrelease takes a handoff bool. When true and the count can immediately be re-acquired, the releaser sets s.ticket = 1 and, if it is safe to enter the scheduler (m.locks == 0, not on g0), calls goyield() — putting itself on the local run queue and letting the just-woken waiter run immediately on the same P, inheriting the releaser’s time slice. This is the runtime-semaphore half of [[sync.Mutex Internals|sync.Mutex’s starvation mode]]: under heavy contention the mutex flips to FIFO direct handoff so a highly contended lock cannot “hog the P indefinitely” and starve a queued waiter (issue #33747).

The lifo bool parameter to semacquire1 controls insertion order. sync.Mutex passes lifo=true for a newly-woken-but-failed waiter so it goes to the front — this preserves fairness ordering within the starvation regime by keeping the longest-waiting goroutine at the head.

notifyList — the sibling primitive for sync.Cond

sema.go also defines notifyList, a ticket-based notification list used exclusively by [[sync.Cond Internals|sync.Cond]]. It is distinct from the treap semaphore because Cond needs broadcast (NotifyAll) and signal (NotifyOne) semantics, not counting. notifyListAdd hands out a monotonically increasing wait ticket; notifyListWait parks the goroutine on a simple FIFO list; notifyListNotifyOne scans for the goroutine holding the next ticket. The less(a,b) helper compares tickets modulo 2^32 so ticket wraparound is handled correctly.

The ticket scheme exists to close a specific race in sync.Cond. The documented Cond.Wait contract requires the caller to hold the associated lock, and Wait atomically unlocks it and suspends — but there is a window between notifyListAdd (taking a ticket) and notifyListWait (actually parking) during which a concurrent Signal/Broadcast could run. The ticket makes this safe: notifyListAdd reserves a ticket before the lock is dropped, and notifyListWait first checks less(t, l.notify) — “has a notification already advanced past my ticket?” If so it returns without parking. A Signal that fires in the window advances l.notify, so the late-arriving waiter sees it has already been notified and does not sleep. This is the same lost-wakeup defense as the nwait-before-recheck ordering in the treap semaphore, expressed with monotonic tickets instead of a counter. The two fast paths in notifyListNotifyOne/NotifyAll — comparing l.wait against l.notify without taking the lock — make an uncontended Signal on a Cond with no waiters nearly free.

Why a treap, and not a simpler structure

The choice of a treap for the per-semaRoot tree deserves justification, since a plain linked list or a balanced BST were both options. A linked list gives O(1) insert but O(n) search to find a specific address’s waiters — unacceptable when many distinct mutexes hash to one bucket. A strict balanced tree (red-black, AVL) gives O(log n) search but needs rebalancing bookkeeping (color bits, height fields) and more complex rotation logic. A treap gets O(log n) expected search, insert, and delete with almost no bookkeeping: each node carries one random ticket priority (cheaprand() | 1), the tree is a BST on address and a min-heap on ticket, and that dual invariant keeps it balanced on average through nothing but rotations. The | 1 ensures the ticket is never zero, because zero is used as a sentinel elsewhere. It is the minimal structure that hits the needed complexity — exactly the kind of trade-off the runtime favors: probabilistic balance, tiny per-node cost, simple code.

Code Examples

How sync.Mutex reaches the runtime semaphore

// internal/sync/mutex.go (simplified) — the contended-lock path
func (m *Mutex) lockSlow() {
    // ... spin / CAS attempts elided ...
    runtime_SemacquireMutex(&m.sema, queueLifo, 1)   // (1)
    // ... woken: retry the CAS on m.state ...
}
 
func (m *Mutex) unlockSlow(new int32) {
    // ... decide whether a waiter exists ...
    runtime_Semrelease(&m.sema, starving /*handoff*/, 1)  // (2)
}
  1. runtime_SemacquireMutex is //go:linkname-bound to internal_sync_runtime_SemacquireMutex in sema.go, which calls semacquire1(&m.sema, lifo, semaBlockProfile|semaMutexProfile, skipframes, waitReasonSyncMutexLock). The &m.sema address is the only thing passed — that address is the semaphore identity.
  2. runtime_Semrelease carries the handoff boolean straight from the mutex’s starving flag, wiring starvation mode into the direct-handoff path described above.

The linkname bridge — why these names cannot change

//go:linkname internal_sync_runtime_SemacquireMutex internal/sync.runtime_SemacquireMutex
func internal_sync_runtime_SemacquireMutex(addr *uint32, lifo bool, skipframes int) {
    semacquire1(addr, lifo, semaBlockProfile|semaMutexProfile, skipframes, waitReasonSyncMutexLock)
}

//go:linkname makes a private runtime symbol callable from another package by name — the runtime and sync are compiled separately and cannot share unexported identifiers normally. The comments in sema.go keep a “hall of shame” of third-party packages (gvisor.dev/gvisor) that reach into sync_runtime_Semacquire via linkname; per issue #67401 the Go team froze these signatures rather than break those ecosystems. The waitReason* argument is what makes a blocked goroutine show up as semacquire versus sync.Mutex.Lock in a goroutine dump.

Profiling hooks woven into acquire

if profile&semaBlockProfile != 0 && blockprofilerate > 0 {
    t0 = cputicks(); s.releasetime = -1          // arm block-profile timing
}
if profile&semaMutexProfile != 0 && mutexprofilerate > 0 {
    s.acquiretime = t0                            // arm mutex-contention timing
}

The semaBlockProfile / semaMutexProfile flags are why go tool pprof can attribute blocking time and mutex contention to source lines: the semaphore records cputicks() at park and at wake, and semrelease1 charges the delay via mutexevent. The amortized contention accounting (avg(head-wait, tail-wait) * N) is an O(1) approximation so that a release does not pay O(N) to bill every queued waiter.

Failure Modes and Common Misunderstandings

  • “A mutex owns its waiters.” No. The mutex owns a uint32; the waiters live in the global semtable. Copying a sync.Mutex after it has been used copies the count but the copy has a different address, so it indexes a different (likely empty) treap slot — one reason copying a used mutex is a go vet error.
  • Treating it as a counting semaphore. The runtime comment warns explicitly against this. A cansemacquire decrement that finds zero does not block at the value level — it is the caller (sync.Mutex) that decides what zero means. The primitive only guarantees one-sleep-paired-with-one-wakeup.
  • Missed wakeup if you reorder. If semrelease’s Xadd were placed after the nwait check, a waiter that incremented nwait and then parked could be missed. The Xadd-before-nwait-read on release and the nwait-increment-before-cansemacquire-recheck on acquire form a matched pair; breaking either reintroduces lost wakeups. This is the single most subtle invariant in the file.
  • Hash collisions degrading to O(n). Before issue #17953, many goroutines on the same address all became treap nodes; the fix (inner waitlink list) makes same-address operations O(1) and keeps the treap sized to distinct addresses only.
  • Spurious wakeups are real. semacquire1 loops and re-checks cansemacquire after waking precisely because goparkunlock can, in edge cases, return without the count being available — callers must never assume a wakeup means a permit.

Alternatives and When They Apply

The runtime does not use one mechanism for everything. The treap semaphore is for goroutine-level blocking inside user code. For M-level (OS-thread) blocking — parking a thread that has no work — the runtime uses the lower-level note primitive built on a futex or an OS semaphore. The distinction: semacquire parks a goroutine and frees the M to run other goroutines; the note/futex path parks the whole OS thread. A sync.Mutex contended by goroutines uses the former; the scheduler idling an M uses the latter.

For lock-free coordination that never needs to block at all, [[Atomic Operations in Go|sync/atomic]] is the alternative — but the moment a goroutine must wait, it ends up here. Channels are a third path: a channel has its own recvq/sendq of sudogs and parks goroutines directly via gopark, not through the treap semaphore — channels and the semaphore are parallel users of the same sudog and gopark machinery.

Production Notes

The semaphore is invisible in profiles by name but central to two diagnostics. The block profile (runtime.SetBlockProfileRate) and mutex profile (runtime.SetMutexProfileFraction) both get their data from the semaBlockProfile/semaMutexProfile timing arms shown above — when pprof tells you a sync.Mutex.Lock is hot, the numbers came from sema.go’s blockevent/mutexevent calls.

The Go 1.26 experimental goroutine-leak profiler depends on a small but deliberate detail here: root.queue sets s.g.waiting = s and s.elem to the semaphore address — the comment says “Storing this pointer so that we can trace the semaphore address from the blocked goroutine when checking for goroutine leaks.” This lets the leak detector, walking from a blocked goroutine, find which primitive it is blocked on and ask the GC whether that primitive is still reachable. The semaphore was retrofitted to be introspectable by the leak profiler.

Cache-line padding the semtable entries is a measurable win on many-core machines: without it, two busy mutexes whose addresses hash to adjacent buckets would ping-pong a shared cache line between cores on every nwait update.

See Also

Graph View

Backlinks