vault

Read-Write Semaphores

18 min read

Read-Write Semaphores

A read-write semaphore (struct rw_semaphore, universally abbreviated rwsem) is the kernel’s reader/writer sleeping lock: it permits many concurrent readers XOR exactly one writer, and a contending task that cannot acquire it blocks (sleeps) rather than spins. It is the read-mostly counterpart to the plain semaphore and the sleeping counterpart to the non-sleeping Reader-Writer Spinlocks. The entire lock state — reader count, writer-held bit, waiters-present bit, and a hand-off bit — is packed into a single atomic_long_t count, manipulated with lock-free atomics on the fast path; only on contention does a task take the internal wait_lock and join wait_list. Writers get optimistic spinning (they spin while the owning writer is running on another CPU, reusing the same MCS queue as the mutex), and a HANDOFF mechanism guarantees that a waiter starved past a deadline is handed the lock directly, defeating reader/writer starvation. The headline kernel user is mmap_lock — the per-mm_struct rwsem (formerly mmap_sem) that serialises a process’s address-space changes.

This note is pinned to Linux 6.12 LTS (released 2024-11-17), reading kernel/locking/rwsem.c and include/linux/rwsem.h directly. It describes the default (non-PREEMPT_RT) implementation; the PREEMPT_RT variant rebuilds rwsem on top of the RT-mutex and is noted at the end.

Mental Model

An rwsem is a turnstile with two modes. In read mode any number of tasks can be inside at once; in write mode exactly one task is inside and everyone else — readers and writers alike — waits outside. The classic justification is read-mostly data: a structure read far more often than it is written can let all the readers proceed in parallel, paying for exclusion only on the rare write.

The clever part is that “how many readers, plus is a writer in, plus is anyone waiting, plus is a hand-off pending” is encoded as a single machine word, so the common uncontended acquire is one atomic instruction on that word. You only fall back to the heavyweight wait-list machinery when the fast atomic fails.

flowchart TD
  subgraph count["atomic_long_t count (64-bit)"]
    direction LR
    RC["bits 8-62:<br/>reader count<br/>(× READER_BIAS)"]
    HF["bit 2:<br/>HANDOFF"]
    WT["bit 1:<br/>WAITERS"]
    WL["bit 0:<br/>WRITER_LOCKED"]
  end
  R["down_read()"] -->|"atomic add<br/>READER_BIAS"| chk1{"any of WRITER /<br/>WAITERS / HANDOFF<br/>set?"}
  chk1 -->|no| ok["read-acquired<br/>(fast path)"]
  chk1 -->|yes| slowR["slowpath:<br/>maybe queue & sleep"]
  W["down_write()"] -->|"cmpxchg 0 →<br/>WRITER_LOCKED"| chk2{"count was<br/>exactly 0?"}
  chk2 -->|yes| okW["write-acquired<br/>(fast path)"]
  chk2 -->|no| slowW["slowpath:<br/>optimistic spin,<br/>then queue & sleep"]

The bit layout of count and the two fast paths. What it shows: readers acquire by adding RWSEM_READER_BIAS (1 << 8) so many readers accumulate in the high bits; a writer acquires only by cmpxchg-ing the whole word from exactly 0 to WRITER_LOCKED. The insight to take: a reader fast-path succeeds only if none of the low “fail” bits (writer-locked, waiters-present, hand-off) are set — the bias add is unconditional but the result is inspected, and a reader that lands on a set fail bit backs its bias out and takes the slow path. A writer can fast-acquire only a completely free lock.

The Structure and the Bit Encoding

The non-PREEMPT_RT definition (rwsem.h v6.12):

struct rw_semaphore {
        atomic_long_t count;       /* reader count + state flag bits */
        atomic_long_t owner;       /* writer task ptr, or last reader + flags */
        struct optimistic_spin_queue osq;  /* MCS spin queue (if SPIN_ON_OWNER) */
        raw_spinlock_t wait_lock;  /* protects wait_list */
        struct list_head wait_list;/* blocked readers and writers, FIFO */
};

Field by field. count is the heart: a single atomic_long_t (a long-sized atomic) holding the entire lock state. owner holds either the writer’s task_struct pointer (when write-locked) or the last reader’s pointer with a flag bit set — used for optimistic spinning and debugging, “take it with a grain of salt” per the source because it may be stale for reader-owned locks. osq is the optimistic spin queue, an MCS lock (the same queue type used by qspinlock and the mutex) on which spinning writers line up. wait_lock is a raw spinlock guarding the wait_list of blocked tasks. The header deliberately places count and owner adjacent so they share a cache line, since both are touched on every acquire.

The count bit layout, copied verbatim from the rwsem.c comment for 64-bit (rwsem.c v6.12):

 Bit  0    - writer locked bit          (RWSEM_WRITER_LOCKED)
 Bit  1    - waiters present bit         (RWSEM_FLAG_WAITERS)
 Bit  2    - lock handoff bit            (RWSEM_FLAG_HANDOFF)
 Bits 3-7  - reserved
 Bits 8-62 - 55-bit reader count
 Bit  63   - read fail bit               (RWSEM_FLAG_READFAIL)

The corresponding constants:

#define RWSEM_WRITER_LOCKED   (1UL << 0)
#define RWSEM_FLAG_WAITERS    (1UL << 1)
#define RWSEM_FLAG_HANDOFF    (1UL << 2)
#define RWSEM_FLAG_READFAIL   (1UL << (BITS_PER_LONG - 1))
#define RWSEM_READER_SHIFT    8
#define RWSEM_READER_BIAS     (1UL << RWSEM_READER_SHIFT)   /* 0x100 */
#define RWSEM_READ_FAILED_MASK (RWSEM_WRITER_MASK | RWSEM_FLAG_WAITERS | \
                                RWSEM_FLAG_HANDOFF | RWSEM_FLAG_READFAIL)

Reading this carefully is the whole design:

  • Reader count lives in the high bits. Because RWSEM_READER_BIAS is 1 << 8, each reader contributes 0x100 to count. Adding the bias is the reader’s acquire; subtracting it is the release. Putting the count in the high bits means the low bits are free for flags, and an atomic_long_add_return of the bias simultaneously increments the reader count and lets the caller read back all the flag bits in one operation.
  • Bit 0 WRITER_LOCKED marks the word as held by a writer. A writer acquires by cmpxchg-ing the entire word from 0 to RWSEM_WRITER_LOCKED — which can only succeed if there are no readers and no flags, i.e. the lock is completely free.
  • Bit 1 FLAG_WAITERS means the wait_list is non-empty. A fast-path reader that sees this bit set must take the slow path, because granting it immediately could starve a queued writer.
  • Bit 2 FLAG_HANDOFF is the anti-starvation hand-off bit, explained in its own section below.
  • Bit 63 FLAG_READFAIL is a guard against reader-count overflow. With 55 reader bits the count would need ~2^55 concurrent readers to overflow into bit 63; the bit “is still checked anyway in the down_read() fastpath just in case,” per the source. If the bias add ever pushed the count negative (overflow), the read fast path fails safely.

The reader fast path tests count & RWSEM_READ_FAILED_MASK: a reader succeeds only if, after adding its bias, none of {writer-locked, waiters-present, hand-off, read-fail} is set. The presence of FLAG_WAITERS in that mask is what enforces fairness — a reader will not jump ahead of an already-queued writer on the fast path.

Mechanical Walk-through

Reader acquire

down_read() calls __down_read() → rwsem_read_trylock():

static inline bool rwsem_read_trylock(struct rw_semaphore *sem, long *cntp)
{
        *cntp = atomic_long_add_return_acquire(RWSEM_READER_BIAS, &sem->count);
 
        if (WARN_ON_ONCE(*cntp < 0))
                rwsem_set_nonspinnable(sem);
 
        if (!(*cntp & RWSEM_READ_FAILED_MASK)) {
                rwsem_set_reader_owned(sem);
                return true;
        }
        return false;
}

The reader unconditionally adds RWSEM_READER_BIAS with acquire ordering (atomic_long_add_return_acquire) — acquire semantics ensure that reads inside the critical section cannot be hoisted above the lock acquisition. It then inspects the returned value. If none of the fail bits are set, the reader is in: it records itself as a reader-owner and returns. If a fail bit is set — a writer holds the lock, or there are waiters, or a hand-off is pending — the bias is left added for the moment and the caller drops into rwsem_down_read_slowpath(), which will back the bias out (adjustment = -RWSEM_READER_BIAS) and decide whether to queue.

The slow path has a notable optimisation: reader optimistic lock stealing. If the lock is not writer-held and no hand-off is pending, a reader can grab the lock immediately even with the slow path entered, unless the lock is “very likely owned by readers” with more than one reader already present and no writer — in which case it queues, “to prevent a constant stream of readers from starving a sleeping writer.” This is a deliberate fairness compromise: readers normally pile in freely, but once a writer is waiting, new readers stop stealing.

Writer acquire

down_write() → __down_write() → rwsem_write_trylock():

static inline bool rwsem_write_trylock(struct rw_semaphore *sem)
{
        long tmp = RWSEM_UNLOCKED_VALUE;   /* 0 */
 
        if (atomic_long_try_cmpxchg_acquire(&sem->count, &tmp, RWSEM_WRITER_LOCKED)) {
                rwsem_set_owner(sem);
                return true;
        }
        return false;
}

A writer can only fast-acquire a completely free lock: try_cmpxchg succeeds only if count was exactly 0, swapping it to RWSEM_WRITER_LOCKED. Any reader present, any flag set, and the cmpxchg fails, sending the writer to rwsem_down_write_slowpath(). On success the writer stamps its own task_struct into owner, enabling other contenders to see who holds it and whether that holder is running.

Release

up_read() subtracts the bias with release ordering and, if it was the last reader and waiters are present, wakes them:

static inline void __up_read(struct rw_semaphore *sem)
{
        ...
        tmp = atomic_long_add_return_release(-RWSEM_READER_BIAS, &sem->count);
        if (unlikely((tmp & (RWSEM_LOCK_MASK | RWSEM_FLAG_WAITERS)) ==
                      RWSEM_FLAG_WAITERS)) {
                clear_nonspinnable(sem);
                rwsem_wake(sem);
        }
}

The condition (tmp & (LOCK_MASK | WAITERS)) == WAITERS is precise: it fires only when, after this reader leaves, there are no remaining lock holders (LOCK_MASK covers writer-locked and the reader-count bits) and the waiters bit is set — i.e. “I was the last reader and someone is queued.” Only then is a wake needed. up_write() is the mirror: it subtracts RWSEM_WRITER_LOCKED with release ordering and wakes if FLAG_WAITERS is set. Release ordering on both ensures that writes done inside the critical section are visible to the next acquirer before the lock appears free.

downgrade_write() atomically converts a held write lock into a read lock — subtracting WRITER_LOCKED and adding READER_BIAS in one fetch_add_release — which is safe and starvation-free because no other writer can sneak in during the conversion, and it lets queued readers proceed without the writer having to fully release and re-contend.

Writer Optimistic Spinning

Sleeping is expensive: two context switches plus scheduler work. If the lock is write-held but the owning writer is currently running on another CPU, it will probably release very soon, so a contending writer does better to spin than to sleep. This is the same bet the mutex’s adaptive spinning makes, and rwsem reuses the same machinery — it is gated on CONFIG_RWSEM_SPIN_ON_OWNER and lines spinners up on the osq MCS queue, the identical queue type the mutex uses.

rwsem_down_write_slowpath() opens with:

if (rwsem_can_spin_on_owner(sem) && rwsem_optimistic_spin(sem))
        return sem;   /* got it by spinning, never slept */

rwsem_optimistic_spin() takes the osq lock (so only one optimistic spinner contends per CPU queue position, avoiding a cache-line storm) and then loops calling rwsem_spin_on_owner(), which watches the owner field:

for (;;) {
        new = rwsem_owner_flags(sem, &new_flags);
        if ((new != owner) || (new_flags != flags)) { ...break; }  /* owner changed */
        barrier();
        if (need_resched() || !owner_on_cpu(owner)) {              /* stop spinning */
                state = OWNER_NONSPINNABLE;
                break;
        }
        cpu_relax();
}

The spinner stops the moment the owning writer is no longer running (!owner_on_cpu(owner)) or the spinner itself needs to reschedule (need_resched()) — spinning is only worth it while the holder is actively making progress on another CPU. Each loop it also retries rwsem_try_write_lock_unqueued() to grab the lock if it just became free.

A subtlety: spinning on a reader-owned lock is bounded by a time threshold, not by an owner running flag, because there is no single reader to watch. The heuristic rwsem_rspin_threshold() caps reader-owned spinning at roughly (10 + nr_readers/2) microseconds, maxing out around 25µs for 30+ readers — “the more readers own the rwsem, the longer it will take for them to wind down.” If a writer spins past that threshold on a reader-owned lock, it sets the RWSEM_NONSPINNABLE flag (in the owner field) to disable further futile spinning, and goes to sleep.

Fairness and the HANDOFF Anti-Starvation Mechanism

Optimistic spinning and reader lock-stealing are great for throughput but dangerous for fairness: a steady stream of readers could starve a queued writer forever, or aggressive writer spinning could starve queued readers. The kernel resolves this with the HANDOFF protocol (RWSEM_FLAG_HANDOFF, bit 2).

The idea: every waiter records a deadline when it joins the queue — waiter.timeout = jiffies + RWSEM_WAIT_TIMEOUT, where RWSEM_WAIT_TIMEOUT is “at least 4ms or 1 jiffy.” If the first waiter has been queued past its deadline, it sets FLAG_HANDOFF, and from that point lock-stealing and optimistic acquisition are forbidden — the lock must be handed directly to that first waiter when it is released.

In rwsem_try_write_lock() (the queued writer’s acquire attempt):

if (count & RWSEM_LOCK_MASK) {
        if (has_handoff || (!rt_or_dl_task(waiter->task) &&
                            !time_after(jiffies, waiter->timeout)))
                return false;
        new |= RWSEM_FLAG_HANDOFF;   /* set the bit, force the issue */
}

A waiting writer that has timed out (or is a realtime/deadline task, which gets it immediately) sets FLAG_HANDOFF. Once set, the comment in rwsem.c guarantees ordering: “A writer must also be the first one in the wait_list to be eligible for setting the handoff bit. So concurrent setting/clearing of handoff bit is not possible” — the wait_lock is held for every set/clear, and only the head waiter may set it. With HANDOFF set, rwsem_try_write_lock() for any non-first waiter returns false (“Honor handoff bit and yield only when the first waiter is the one that set it”), so the queued head waiter is guaranteed the next grant.

On the reader side, rwsem_mark_wake() similarly checks time_after(jiffies, waiter->timeout) and requests a hand-off when waking readers has been blocked too long by writers. The hand-off bit is cleared once the lock is granted to the intended waiter (in rwsem_del_waiter(), rwsem_try_write_lock(), or when readers are woken). The net effect: throughput-friendly stealing and spinning are allowed up to a bounded latency, after which fairness is enforced by fiat. The source describes the reader-wakeup policy as “an adaptation of the phase-fair R/W locks where at the reader phase… all readers are eligible to acquire the lock at the same time.”

The Headline User: mmap_lock

The single most important rwsem in the kernel is mmap_lock, the per-mm_struct lock that protects a process’s virtual address space — its tree of Virtual Memory Areas (VMAs). Every mmap(), munmap(), mprotect(), brk(), and page-fault-driven VMA modification serialises through it. The kernel docs state it plainly: “Each MM has a read/write semaphore mmap_lock which locks at a process address space granularity which can be acquired via mmap_read_lock(), mmap_write_lock() and variants” (process_addrs). Readers (e.g. page-fault handlers that only look up a VMA) take it for read; mutators (mmap/munmap) take it for write. “The first thing any of these locks achieve is to stabilise the VMA within the MM tree” — i.e. guarantee the VMA will not be freed or modified underneath you.

It was historically named mmap_sem. Michel Lespinasse’s work to wrap all direct mmap_sem accesses behind an mmap_*_lock() API (merged for v5.8) renamed the field to mmap_lock; the wrapping was the necessary prerequisite for later scalability work, because mmap_sem was, in the words of the LWN coverage, “a known scalability problem for years” that “protects multiple unrelated data structures simultaneously” — covering “many sins” beyond VMA protection (LWN 787629).

Uncertain

Verify: that the mmap_sem → mmap_lock rename landed specifically in v5.8 via Michel Lespinasse’s API-wrapping series. Reason: the process_addrs doc I fetched describes the current mmap_lock but “does not explicitly mention a rename from mmap_sem,” and the v5.8 attribution is from memory plus LWN context, not a directly-fetched commit. To resolve: git log --oneline --follow mm/mmap.c | grep -i mmap_lock or the v5.8 merge changelog.

The contention pressure on mmap_lock drove the per-VMA locking work: page-fault handlers can now take a lightweight per-VMA read lock under RCU (lock_vma_under_rcu()) instead of the whole-address-space mmap_lock, so faults to different VMAs run concurrently. The docs confirm “VMA read locking is entirely optimistic — if the lock is contended or a competing write has started, then we do not obtain a read lock,” and that a VMA read lock “can be obtained without any other lock,” with the maple-tree VMA lookup being “RCU safe.” A VMA write lock still requires the mmap_lock write lock to be held. This is the classic rwsem story: a single coarse rwsem becomes a scalability bottleneck, and the fix is to push toward finer-grained or RCU-based reader paths rather than to make the rwsem itself faster.

Configuration and Usage Examples

/* Static declaration */
DECLARE_RWSEM(my_rwsem);
 
/* Dynamic initialisation */
struct rw_semaphore lock;
init_rwsem(&lock);
 
/* Reader critical section */
down_read(&lock);
... /* read shared data; many readers run here at once */
up_read(&lock);
 
/* Writer critical section */
down_write(&lock);
... /* mutate shared data; exclusive */
up_write(&lock);

Variants from the header (rwsem.h v6.12):

  • down_read_interruptible() / down_read_killable() — sleep interruptibly / killably, returning -EINTR if signalled.
  • down_write_killable() — killable write acquire. (Note: there is no down_write_interruptible().)
  • down_read_trylock() / down_write_trylock() — non-blocking; return 1 on success, 0 on contention (the opposite convention from [[Kernel Semaphores|down_trylock()]], which returns 0 on success — a classic confusion).
  • downgrade_write() — atomically convert a held write lock to a read lock.
  • The DEFINE_GUARD(rwsem_read, ...) / DEFINE_GUARD(rwsem_write, ...) macros provide scope-based auto-release (guard(rwsem_read)(&lock);) via the cleanup.h infrastructure.

Failure Modes and Common Misunderstandings

  • down_read_trylock() vs down_trylock() return inversion. rwsem trylocks return 1 on success (like spin_trylock/mutex_trylock), but the plain semaphore’s down_trylock() returns 0 on success. Mixing the conventions silently inverts the success test.
  • Reader recursion deadlock. rwsems are not recursive. A task that holds the read lock and then a writer queues behind it must not try to take the read lock again — if a writer is waiting, the second down_read() will block behind that writer (fairness forbids jumping the queue), and since the task is also the one holding the first read lock, it deadlocks against itself. The header explicitly warns “rwsems are not allowed to recurse.”
  • Writer starvation under reader floods (mitigated, not eliminated). Before HANDOFF, a steady reader stream could starve a writer indefinitely. HANDOFF bounds the starvation to ~4ms+ of waiting, but a latency-sensitive writer can still see multi-millisecond stalls under heavy reader load — mmap_lock write contention is a real source of tail latency in memory-heavy workloads.
  • Holding it too long. Because it sleeps, an rwsem may only be taken in process context that can block — never in atomic/interrupt context (use Reader-Writer Spinlocks there) and never while holding a spinlock. might_sleep() in the acquire paths will warn if violated.
  • Stale owner for reader locks. The owner field for a reader-held lock points at some past reader and may be wrong — it is for spinning heuristics and debugging only, never for correctness. The source warns: “it may not be the real owner… when that field is examined.”

Alternatives and When to Choose Them

  • Plain mutex — if reads and writes are roughly balanced, the reader/writer bookkeeping of an rwsem (the atomic add/sub, the spinning thresholds) often costs more than it saves; a simple mutex wins. Reach for rwsem only when reads genuinely dominate.
  • Reader-Writer Spinlocks — the non-sleeping reader/writer lock for atomic/interrupt context or very short critical sections. Cannot sleep inside.
  • RCU (Read-Copy-Update Fundamentals) — when readers must be truly free (no atomic on the fast path, no cache-line bouncing) and the data structure can be updated copy-then-publish. RCU readers never block writers at all, which an rwsem cannot match — but RCU constrains how you mutate the data. This is the direction mmap_lock evolution took with RCU-based per-VMA lookup.
  • Per-CPU Variables — if the state can be made per-CPU, share nothing and avoid the lock entirely.

The reviewer’s rule of thumb: rwsem is for read-mostly state in sleepable context where you cannot restructure for RCU. If reads are not clearly dominant, a mutex is simpler and usually faster.

PREEMPT_RT and Production Notes

On a PREEMPT_RT kernel, struct rw_semaphore is not the count-and-atomics implementation above. It is rebuilt on the PI-aware RT-mutex (rwbase_rt), so that a writer can priority-boost the readers blocking it. The locktypes documentation flags the key behavioural change: on PREEMPT_RT “a writer cannot distribute its priority to multiple readers simultaneously,” and “low-priority preempted readers retain locks, starving high-priority writers” is a tolerated trade-off, while “readers can grant priority to writers, preventing writer starvation through priority boosting” (locktypes). The reader-count semantics also tighten under RT to make PI tractable.

In a production 6.12 kernel the most-watched rwsem by far is mmap_lock; perf lock and the lock_event_counts (the rwsem_* lockevents the source increments, like rwsem_rlock_steal, rwsem_wlock_handoff, rwsem_opt_lock) are the tools for diagnosing rwsem contention. Heavy mmap_lock write contention shows up as time spent in rwsem_down_write_slowpath; the modern remedy is rarely “tune the rwsem” and usually “stop taking mmap_lock for write so often” — hence the years of per-VMA-lock and maple-tree work in the memory-management subsystem.

See Also

Graph View

Backlinks