Reader-writer locks: admission, upgrades and wakeup lifetime

Runtime overview · Waits and locks · Mutexes and turnstiles · Ticket and pointer locks

A reader-writer lock protects a resource that permits simultaneous shared readers but only one exclusive writer. In this checkout, understanding an lck_rw_*() call requires first identifying the declared lock type. XNU builds two implementations with different state words, waiting protocols and fairness rules. This chapter follows both, including what remains held after an upgrade fails, why waking a waiter does not transfer ownership, and how the scheduler treats a thread that cannot make progress while using these locks. Build selection, type selection.

1. The default type and the explicit new implementation

XNU_LCK_RW_DEFAULT_TO_NEW is 0 in lock_rw.h. Under XNU_KERNEL_PRIVATE, lck_rw_t therefore names lck_rw_old_t; overloadable declarations route an explicit lck_rw_new_t * to the new implementation. Both source files are compiled. Changing the function name is not how callers choose the backend. Default switch, aliases, old implementation's local alias, new implementation's alias.

The concrete declarations are in vm_object_xnu.h and vm_map_xnu.h. vm_object_lock() and its companions show the dispatch through &object->Lock. The remainder of this chapter labels the variants explicitly.

Neither implementation maintains a production linked list of every shared owner. The exclusive owner is a compact thread ID; debug builds add per-thread lock tracking. A reader count is a count of grants, not a list from which the scheduler can identify and boost each reader. Layouts, debug tracking.

2. Legacy state: intent and ownership are different

The legacy object contains a type, lck_rw_owner, the state word and padding. Its state word has the following fields. Initialization selects writer preference unless LCK_ATTR_RW_SHARED_PRIORITY is supplied and enables sleeping unless LCK_ATTR_RW_NO_SLEEP is supplied. Layout, initialization.

The interlock disables interrupts and uses a bit lock; dropping it restores the prior interrupt state. Atomic fast paths that see interlock must wait for it to clear. The ordinary acquire/release loops use acquire/release atomic operations; the interlock-protected field stores use compiler ordering because the interlock supplies the synchronization. Interlock and state helpers, interrupt handling, interlock spinning.

Mermaid source

flowchart TD
    R["Readers hold shared_count greater than zero"] -->|"writer atomically sets want_excl"| W["Writer intent reserved; readers still own resource"]
    W -->|"new readers denied with writer preference"| Q["Later readers wait on reader event"]
    W -->|"existing readers release; no upgrader remains"| X["Reserved writer sets owner and enters exclusive section"]
    X -->|"release clears owner and intent"| A["Wake eligible waiters; each retries acquisition"]
    A -->|"shared acquisition increments count"| R

The diagram omits an upgrade waiter; that case is expanded below. It also does not promise FIFO ordering among sleeping writers. Legacy release wakes matching writers with thread_wakeup(), and each retries the admission rules. Writer acquisition, release wake decisions.

3. Legacy shared and exclusive acquisition

Shared acquisition increments rwlock_count before a sleepable attempt, then uses an acquire atomic loop. If neither exclusive intent, upgrade intent nor the interlock is set, it adds one to shared_count. The owner field must remain zero. If intent is present, lck_rw_grab() can still admit a reader when shared preference is configured and the reader cohort is already nonempty. Shared entry, admission predicate.

Exclusive acquisition first tries a single test-and-set requiring zero readers, no writer/upgrader intent and no interlock. On failure it separates two waits:

1. Reserve want_excl, waiting for a previous writer's reservation if necessary.
2. Keep that reservation while waiting for both shared_count and want_upgrade to clear.

Only after this drain does it write the current compact thread ID to lck_rw_owner and return exclusive ownership. A snapshot with want_excl=1, nonzero readers and owner=0 is therefore an ordinary contended state. Fast acquisition and owner publication, reserve stage, drain stage.

The legacy try functions do not enqueue a sleeping waiter. They can nevertheless spin on the internal interlock and retry failed atomic exchanges. try_lock_shared() refuses either intent bit even on a reader-biased lock, whereas the blocking shared slow path can join an existing cohort. “Try” therefore means no scheduler blocking on contention, not a single instruction or identical admission to the blocking API. A failed try returns without adding a shared grant or a per-thread RW count. Try-shared, try-exclusive.

Spinning becomes a protected wait registration

For a sleepable legacy lock, lck_rw_deadline_for_spin() returns an immediate deadline if there are already reader/writer waiters or the reader count exceeds machine_info.max_cpus; otherwise it uses mach_absolute_time() + MutexSpin. Those checks avoid spending a normal spin interval when the existing population already suggests poor on-core progress. ARM pauses use WFE after an exclusive load; this is still spinning in the current kernel execution context, not a scheduler sleep. Deadline, ARM pause and drain.

When spinning expires, the waiter disables interrupts, takes the bit interlock and rereads the state. If the condition became available, it claims the relevant state under that interlock. Otherwise it sets r_waiting or w_waiting, publishes an uninterruptible assert_wait() on (lock + 2) or (lock + 1), releases the interlock and calls thread_block() only if registration returned THREAD_WAITING. It loops after wakeup. The condition check and wait registration are protected together; wakeup before the eventual thread_block() is handled by the scheduler's wait protocol. Event definitions, reader registration, writer registration, generic wait transitions.

Legacy NO_SLEEP is a caller obligation: acquisition requires preemption already disabled and never takes the sleepable interlock path. Its deadline helper uses a very large interval and the outer loops continue; expiry there is not a user-visible timeout. The _b() variants let a caller-supplied block stop a non-sleepable attempt. If a writer already reserved want_excl before that early return, lck_rw_drop() clears it. Context check and entry, callback contract, drop and cleanup, post-drain early return.

4. Legacy upgrades, downgrades and the lost-read-lock case

A shared-to-exclusive upgrade is not equivalent to taking a second lock. The legacy implementation requires writer preference, atomically sheds the caller's shared count and tries to reserve want_upgrade. If another upgrader already reserved it, the caller still sheds its shared count, may wake the successful upgrader when it was the last reader, removes debug/count ownership and returns false with no lock held. Otherwise it waits for remaining readers to drain and becomes exclusive owner. Upgrade body, failure cleanup, successful drain.

The two branches both subtract the old shared grant:

osfmk/kern/lock_rw_old.c, lines 1306–1326.

		if (data & LCK_RW_WANT_UPGRADE) {
			data -= LCK_RW_SHARED_READER;
			if ((data & LCK_RW_SHARED_MASK) == 0) {         /* we were the last reader */
				data &= ~(LCK_RW_W_WAITING);            /* so clear the wait indicator */
			}
			if (atomic_exchange_complete32(&lock->lck_rw_data, prev, data, memory_order_acquire_smp)) {
				return lck_rw_lock_shared_to_exclusive_failure(lock, prev);
			}
		} else {
			data |= LCK_RW_WANT_UPGRADE;            /* ask for WANT_UPGRADE */
			data -= LCK_RW_SHARED_READER;           /* and shed our read count */
			if (atomic_exchange_complete32(&lock->lck_rw_data, prev, data, memory_order_acquire_smp)) {
				break;
			}
		}
		cpu_pause();
	}
	/* we now own the WANT_UPGRADE */
	if (data & LCK_RW_SHARED_MASK) {        /* check to see if all of the readers are drained */
		lck_rw_lock_shared_to_exclusive_success(lock);  /* if not, we need to go wait */
	}

A worked interleaving with writer preference illustrates why callers must revalidate after failure:

These are chosen successful atomic orderings, not a claim that all schedules produce this sequence. The crucial invariant is that only one upgrader waits while the others release their shared grants; retaining all readers while multiple upgraders waited would prevent progress. Upgrade atomic loop, writer drain mask, release clears upgrade before writer intent.

Downgrade performs one release atomic transition that adds a shared count and removes the caller's upgrade or exclusive intent after clearing the owner field. It never exposes an intermediate fully unlocked critical section. Waiting readers are woken unless writer preference and sleeping writers suppress that wake; writers are not woken merely by downgrade because one reader remains. In contrast, explicit yield helpers release, pause and reacquire: protected state can change during that gap. Downgrade, legacy yield helpers.

5. Legacy release and destruction

lck_rw_done() releases the mode inferred from the state. A shared release decrements the reader count; only the last reader reaches waiter processing. An exclusive release clears the owner and removes want_upgrade if present, otherwise want_excl. It updates waiter flags in the same release atomic exchange and passes the prior state to lck_rw_done_gen() for wake selection. The checked shared/exclusive wrappers verify mode/owner expectations before and after this common operation. Release state machine, checked wrappers.

On the last shared release or an exclusive release, the helper wakes writers if the old w_waiting was set. It wakes readers only when old r_waiting was set and the combination of writer preference plus waiting writers does not suppress them. Each woken thread competes again. Clearing a waiting bit means the unlocker has taken responsibility for the corresponding wake, not that every thread has already run. It then decrements the releasing thread's RW count and removes debug ownership. Wake and count cleanup.

Destruction asserts an unheld state, marks the type invalid, installs LCK_RW_TAG_DESTROYED and releases the lock-group reference. It does not implement a general waiter cancellation/drain protocol. The containing object's lifetime discipline must exclude new attempts and ensure no outstanding user can touch the lock. Legacy destroy.

6. New RW state and why a failed read increment is not rolled back

The new object retains a compact exclusive owner but uses a 64-bit lck_rw_word_t split into the fields below. lock32 covers only u_wanted, x_locked and r_count; the other fields carry configuration and contention. Complete layout, constant masks.

A shared fast attempt first checks valid, no upgrade/exclusive state, and—when writer-biased—an empty writer-spinner tail. It deliberately ignores sleeping x_waiters: an on-core arrival can acquire ahead of sleepers. The pretest is racy. The subsequent atomic add increments r_count and succeeds if the returned state is not exclusively locked. If a writer won between the pretest and add, the increment remains in the word but represents no shared owner. The exclusive unlock resets the entire acquisition word, removing these failed speculative increments. Admission rules, shared attempt, exclusive release.

For __arm64__ && __ARM_ARCH_8_3__, the body separates a relaxed add from an acquire load; the source explains the acquire-PC optimization for read-only critical sections. Other builds use an acquire add. This is a selected code-generation path, not a claim that every ARM64 target emits one fixed instruction sequence. The new reader does not decrement after a failed attempt:

osfmk/kern/lock_rw.c, lines 315–325.

		word.lock64 = os_atomic_add(&lck->lck_rw.lock64,
		    LCK_RW_R_COUNT_INC.lock64, relaxed);
		os_atomic_load(&lck->lck_rw.lock64, acquire);
#else
		word.lock64 = os_atomic_add(&lck->lck_rw.lock64,
		    LCK_RW_R_COUNT_INC.lock64, acquire);
#endif
		success = !word.x_locked;
	}

	return success;

For example, R passes the pretest, W CASes lock32 from zero to x_locked, and R's add sees x_locked=1. R enters contention without owning a read grant; W continues to be the only owner and clears the acquisition word on release. Conversely, if R increments before W's CAS, the nonzero count makes that CAS fail. An exact formal memory-model proof is outside this source trace. Exclusive CAS, algorithm rationale.

7. New contention: queued writer spinners and three typed waits

Reader contention adaptively spins and retries admission. Writer contention first enters an MCS queue using per-CPU node storage; a thread behind the leader waits on its own node status, while the leader tests the RW word. The writer queue mode is LCK_MCS_SLEEPABLE | LCK_MCS_ABORTABLE: an urgent AST can request removal from this queue before the RW acquisition loop eventually blocks or backs off. Leaving the MCS queue does not release an acquired RW lock; these are separate states. Reader step, writer step and dequeue, MCS abort path, MCS representation.

Spinning expiry, or an existing upgrader waiter in selected paths, leads to lck_rw_assert_wait(). Unlike legacy RW, there is no RW-word bit interlock. The helper derives one of three typed events—read, write or upgrade—locks its global event queue, rereads admission, and either declines to sleep or atomically publishes the appropriate waiter bits. It calls waitq_assert_wait64_locked() only when those bits are already present or its full-word CAS succeeds. A CAS collision returns to acquisition rather than enqueuing based on stale state. Event encoding, wait registration.

The key publication and registration branch is:

osfmk/kern/lock_rw.c, lines 1331–1354.

	if (hint == kThreadWaitKernelRWLockRead &&
	    lck_rw_lock_s_allowed(word, false)) {
		waiting = false;
	} else if (hint == kThreadWaitKernelRWLockWrite &&
	    lck_rw_lock_x_allowed(word, false)) {
		waiting = false;
	} else if (hint == kThreadWaitKernelRWLockUpgrade &&
	    lck_rw_lock_u2x_allowed(word)) {
		waiting = false;
	} else if ((word.lock64 & mask.lock64) == mask.lock64) {
		waiting = true;
	} else {
		waiting = os_atomic_cmpxchg(&lck->lck_rw.lock64, word.lock64,
		    word.lock64 | mask.lock64, relaxed);
	}

	if (waiting) {
		thread_set_pending_block_hint(self, hint);
		waitq_assert_wait64_locked(waitq, event,
		    THREAD_UNINT | THREAD_WAIT_NOREPORT_USER,
		    TIMEOUT_URGENCY_SYS_NORMAL, TIMEOUT_WAIT_FOREVER,
		    TIMEOUT_NO_LEEWAY, self);
	}

Mermaid source

sequenceDiagram
    participant T as Contending thread
    participant Q as Typed event queue
    participant L as RW state
    participant U as Unlocker
    T->>Q: Lock queue
    T->>L: Recheck admission and CAS waiter bit
    alt Still blocked and bit published
        T->>Q: Register uninterruptible wait
        T->>Q: Unlock queue
        U->>L: Atomic release
        U->>Q: Lock queue and identify a waiter
        U->>L: Update waiter bits while identified thread remains retained
        U->>Q: Resume identified thread
        T->>L: Retry acquisition after wake
    else Admission changed or CAS lost
        T->>Q: Unlock queue without enqueue
        T->>L: Retry acquisition
    end

The diagram compresses spinning and scheduler dispatch. An identified thread is not automatically installed as the owner; all wake paths return to acquisition. Extremely unlucky interference after expiry can select exponential mutex_pause() backoff even when wait registration repeatedly loses its race. Reader backoff, blocking helper.

Writer admission also distinguishes sleeping waiter urgency. A non-realtime writer above MINPRI_FLOOR without TH_OPT_VMPRIV publishes x_urgent as well as x_waiters. This does not donate that writer's priority to all readers. It requests a broader wake so the scheduler can choose among writers rather than leaving a higher-priority thread behind multiple low-priority sleepers. Urgent-writer predicate and rationale.

8. New wakeup and storage lifetime after unlocking

New shared release uses a release subtraction and requests wake processing when the resulting reader count reaches zero with writer/upgrader waiters. Exclusive release clears the owner and atomically clears the entire lock32 portion with release ordering. The wake functions run after this publication, so the current unlocker cannot assume the containing object still exists merely because it once held the lock. Shared release, exclusive release.

The solution uses the typed wait event and a waiting thread's separate right to access the object. Under the event-queue lock, a wake helper first identifies and removes a matching thread. Only if it found one may it modify the lock's waiter bits; that thread is not resumed until the update is finished. If no thread remains, another wake may have won or the old instance may already be gone, so the helper does not dereference the lock to clear stale bits. The event type prevents interpreting a completely different primitive at the same address; it does not prove the RW instance is the identical allocation, and spurious wakes of a replacement RW instance are tolerated. Lifetime rationale, identify/resume helpers, wakeup contract.

Wake selection is explicit:

The writer helper uses WAITQ_CHECK_HAS_MORE on its second identified thread to keep or clear waiter bits. Readers are woken as a group after one identified reader gives the helper safe access to the RW word; the upgrader is singular. All of these decisions can race with other awakeners and on-core acquisitions. Selection, writers, readers and upgrader.

New destruction is correspondingly strict: after validating type and valid, it removes configuration bits from a snapshot and requires the remainder to be zero. Outstanding owner/count, queue tail or waiter bits are an invariant violation. It checks the group, drops its reference and zeroes the object. This is validation of an externally quiesced object, not a destructor that wakes and cancels users. Destroy.

9. New conversion and spin-mode contracts

New upgrade first CASes the sole-reader acquisition word directly to x_locked. On failure it atomically sets u_wanted. An already-set bit means another upgrader won: the caller invokes shared unlock and returns false. The successful reserving upgrader records its owner ID, subtracts its own reader count, and waits until the acquisition word contains only u_wanted; it then converts that word to exclusive. The owner field can therefore identify an upgrading thread before x_locked becomes true. Upgrade entry, prepare and drain.

Downgrade clears the owner and performs a release RMW that replaces lock32 with exactly one shared grant, retaining the queue/configuration half. Eligible readers can then wake. As with legacy upgrade, false means the read lock is gone. VM callers must retry or otherwise reconstruct their lookup under a new grant. The fault path is one real consumer of this contract. Downgrade, VM wrapper, fault upgrade callers.

The suffix _spin on the new RW API specifies the held-mode preemption/accounting contract; it does not by itself guarantee that acquisition never sleeps:

Held-mode accounting, spin-to-block transition, shared mode dispatch, exclusive no-sleep loop, mode conversion.

Context validation in assertion builds distinguishes interrupt context, expected preemption depth, no-sleep configuration and exceptional early-boot/hibernation/panic circumstances. Those branches are not blanket permission to acquire a sleepable lock from arbitrary interrupt-disabled code. New context checks.

10. RW counts, scheduler promotion and explicit condition sleeps

Both variants use the common per-thread rwlock_count helpers for their sleepable held/attempting state. The counter increments before an ordinary acquisition can publish ownership, remains nonzero across its internal wait, and decrements on release or failed upgrade. It is consequently broader than the field comment “number of locks held”: an acquisition in progress can contribute. Legacy increment before attempt, new mode helper, counter implementation, thread field.

When a thread goes off-core with a positive count, thread_dispatch() marks active sleepable-SMR trackers stalled and later, with the thread locked, calls lck_rw_set_promotion_locked(). Unless LCK_OPTION_DISABLE_RW_PRIO disables this mechanism, it adds TH_SFLAG_RW_PROMOTED; priority computation applies at least MINPRI_RWLOCK together with other independent promotion reasons. The final count decrement clears this reason if present. This is a thread-scoped scheduling floor, not the mutex turnstile's directed waiter-to-owner priority inheritance. There is no per-RW chain enumerating all reader owners. Off-core integration, set/clear promotion, priority calculation, design limits.

Mermaid source

flowchart TD
    A["Sleepable acquire starts"] -->|"increment before possible acquisition or wait"| C["thread.rwlock_count is positive"]
    C -->|"thread goes off-core"| S["Scheduler adds RW promotion reason"]
    S -->|"priority recomputed"| F["RW scheduling floor plus other independent reasons"]
    C -->|"release or losing upgrade"| D["Decrement count"]
    F -->|"release or losing upgrade"| D
    D -->|"last count and promotion active"| R["Remove only RW promotion reason"]

lck_rw_sleep() and _deadline() serve a different need from internal lock contention: wait for a caller's condition while releasing an already-held RW lock. They register the event while the lock is still held, release through lck_rw_done(), block, and reacquire the old or explicitly requested mode unless LCK_SLEEP_UNLOCK says to remain unlocked. If registration did not produce a wait, they normally retain the lock; LCK_SLEEP_UNLOCK still releases it. LCK_SLEEP_PROMOTED_PRI keeps an explicit priority-floor token across the release/wait/reacquire interval. A wake, abort or deadline result describes the condition wait; it does not validate the caller's protected condition after reacquisition. Legacy sleep implementation, new implementation.

11. Evidence, tests and remaining limits

This trace covers both representations, shared/exclusive/try admission, legacy interrupt interlocking, adaptive/new MCS contention, wait publication, upgrade failure, downgrade, post-unlock wake lifetime, scheduler count/promotion, condition sleep and destruction. The ticket and pointer-lock companion expands the shared MCS infrastructure and non-sleeping primitives. It does not establish fairness bounds under every schedule or prove the ARM memory model.

The tree includes a TLA+ RW model with explicit read/write/upgrade event sets and an exclusion invariant. Its own comments intentionally omit detailed owner/readers tracking to reduce state transitions. That model is additional design evidence, not proof that this checkout's compiled implementation and all configuration branches have been verified. Model state and invariants.

The lock benchmark supplies separate new and legacy RW operation tables, including upgrade/downgrade, and a user test exposes the corresponding selections. The VM wrappers provide real new-RW clients. These bodies were inspected; no kernel benchmark, test kernel, TLA+ execution or hardware timing measurement was run for this documentation. Benchmark adapters, test command options, VM object wrappers.