Locks, waiting, completions, and sleeping rules

Before you start#

Read workqueues and kernel threads, interrupts and softirqs, and scheduler core. This chapter describes upstream v6.12 kernel mechanisms; the optional host program is a synthetic POSIX condition-variable example, not kernel code. The source-only lost-wakeup timeline needs no build or guest. Do not use /proc/locks as a list of kernel spinlocks: it reports a different class of file-lock information.

Learning goals#

Choose synchronization based on an invariant, execution context and lifetime; distinguish lock classes and PREEMPT_RT effects; trace waitqueue wakeup and completion state; and explain why a timeout or a lock alone does not prove that an asynchronous object is safe to free.

Start with an invariant and an owner#

A shared-state invariant is a property that must hold whenever other participants are allowed to observe the state. For example, a queue's length must agree with its linked entries, and an entry must not be freed while a consumer can use it. A lock can serialize updates to the queue, but a separate reference or reclamation protocol may be needed after the lock is released. Conversely, a reference can keep an object alive without preventing concurrent writes to its fields. State protection, memory ordering and lifetime are related questions, not interchangeable labels.

List the participants before picking a primitive: a process-context caller, workqueue callback, hard interrupt, softirq, timer or NMI can have different constraints. Identify which operations can sleep, which locks each participant holds, whether a callback can reenter on the same CPU, and who prevents new work during teardown. A lock only protects data when every relevant access follows the same documented protocol. volatile does not make a multi-step operation atomic or provide a general inter-CPU synchronization scheme.

Source walkthrough#

A waitqueue combines a protected queue of waiters with a condition supplied by the caller. The waitqueue lock protects queue bookkeeping; the condition may be protected by another lock or an explicit ordering protocol. In v6.12 kernel/sched/wait.c, __wake_up_common_lock includes this excerpt (SPDX GPL-2.0-only; declarations and return omitted):

spin_lock_irqsave(&wq_head->lock, flags);
remaining = __wake_up_common(wq_head, mode, nr_exclusive, wake_flags,
			key);
spin_unlock_irqrestore(&wq_head->lock, flags);

The lock serializes access to the waitqueue while the helper scans and invokes wake functions; saved interrupt state is restored afterward. mode, exclusive count and key influence which waiters are considered. A wakeup is not the condition itself: after being awakened, a waiter must recheck the condition using its documented synchronization because another consumer can change it, a wakeup can be spurious, or the condition can still be false. The exact internal lock type and semantics depend on configuration, including PREEMPT_RT.

A completion is a kernel synchronization object used to signal that an event or phase has completed. In v6.12 kernel/sched/completion.c, complete_with_flags includes (SPDX GPL-2.0; surrounding declarations and unlock omitted):

if (x->done != UINT_MAX)
	x->done++;
swake_up_locked(&x->wait, wake_flags);

The surrounding function holds x->wait.lock while it updates the completion state and wakes an eligible waiter. A completion can be signaled before the waiter starts waiting; the stored done state prevents that event from being lost in the same way as an unrecorded bare wakeup. complete_all has different persistent semantics and reinitialization requirements. A waiter returning on a timeout or signal does not automatically stop a producer that may later call complete on the object. The completion and its containing storage must remain alive until all possible producers are synchronized. See completion documentation.

Choosing a primitive by context#

A raw spinlock is a low-level lock for code that must not sleep while holding it, including selected scheduler and interrupt paths. On a non-PREEMPT_RT kernel, ordinary spinlocks also provide spinning semantics in their relevant contexts. spin_lock_irqsave saves local interrupt state and prevents a same-CPU interrupt handler that takes the same lock from interrupting the holder and deadlocking it; unlock restores the saved state. spin_lock_bh addresses relevant bottom-half/softirq reentry rather than being a universal replacement for IRQ disabling. Disabling local interrupts alone does not exclude another CPU. The correct variant follows every participant and nesting rule.

PREEMPT_RT changes ordinary spinlock_t and rwlock_t semantics: many are transformed into priority-inheritance-aware sleeping lock mechanisms, while raw_spinlock_t remains a true raw spinning primitive. The exact allowed context and IRQ behavior must be taken from the documented RT lock rules, not from a blanket statement that every object named spinlock always behaves identically. This does not make it safe to sleep under a raw spinlock or to use an ordinary sleeping mutex in hard NMI context. See lock types and PREEMPT_RT.

A mutex provides sleeping mutual exclusion for a suitable task context and has an owner. It is generally inappropriate in hard interrupt context. A non-recursive mutex acquired twice by the same task can deadlock; a lock is not an automatic recursion counter. rw_semaphore supports read/write access with sleeping semantics and different rules from an rwlock. Reader/writer locks can allow concurrent readers, but the data and lifetime still require a consistent protocol. A semaphore counts permits and does not necessarily encode a single owner; a completion is designed to signal an event, not to protect a shared data structure by itself.

A sequence counter lets readers retry if a writer changed data during a read, as seen in the timekeeping chapter. A seqlock combines sequencing with writer-side locking. Readers cannot safely follow arbitrary pointers that a writer may free unless another lifetime mechanism makes those references valid. Atomic operations can update individual values and provide specified ordering, but an atomic counter does not make a multi-field invariant atomic. RCU provides a different read-side and deferred-reclamation protocol; its correctness still depends on publication, grace periods and references. Later chapters develop atomics and RCU in detail.

The lost-wakeup timeline#

Suppose a consumer checks ready == false, then intends to sleep until a producer sets it. In an incorrect design, the consumer checks without the required synchronization and is interrupted before it joins the waitqueue. The producer sets ready = true, sends a wakeup while no waiter is registered and returns. The consumer then registers and sleeps without checking again. The condition is true, but the only wakeup was missed; the consumer can remain asleep indefinitely. Adding a faster CPU or a different scheduler class does not repair this ordering bug.

A correct wait-event pattern establishes the queue state and task sleep state under the API's protocol, checks the condition with the required lock or memory ordering, sleeps only while it remains false, and rechecks after wakeup. The producer publishes the condition under the matching protocol and wakes the appropriate waiters. Exact lock and barrier choices depend on the data and API: blindly adding wake_up after an unsynchronized write is not a proof. Waitqueue macros such as wait_event encode important prepare, check and finish behavior; inspect v6.12 include/linux/wait.h and the caller's condition access.

In v6.12 include/linux/wait.h, SPDX GPL-2.0, the loop in ___wait_event reads as follows (the macro's setup and return lines omitted):

	for (;;) {								\
		long __int = prepare_to_wait_event(&wq_head, &__wq_entry, state);\
										\
		if (condition)							\
			break;							\
										\
		if (___wait_is_interruptible(state) && __int) {			\
			__ret = __int;						\
			goto __out;						\
		}								\
										\
		cmd;								\
	}									\
	finish_wait(&wq_head, &__wq_entry);					\

The condition is tested after prepare_to_wait_event has registered the entry and set the task state, which is the ordering the lost-wakeup timeline depends on. schedule() runs only while the condition is still false, and the loop tests again after each wakeup. The excerpt does not show the lock or barrier that makes the condition itself visible, and the cmd argument is supplied by each caller.

Consider two consumers waiting for one item. A producer sets the condition and wakes them. Consumer A gets the item first and changes the condition before B runs. B can wake yet find the condition false and must wait again. This is why a wakeup is an invitation to re-evaluate, not a transfer of ownership of an item. Exclusive waiters and wake counts influence how many tasks are awakened; they do not remove the need to define who consumes the resource.

Completions, timeouts and teardown#

A completion's done field represents completion events under its API. complete can wake one waiter and records completion state; complete_all makes the completion available to all relevant waiters until it is reinitialized according to its rules. Reusing a completion without coordinating all previous waiters and producers can mix generations of an operation. reinit_completion changes state; it does not cancel an outstanding producer or make a stale pointer safe.

The timeout variant has a documented return convention: wait_for_completion_timeout returns zero on timeout and a positive value on completion, representing at least one or remaining jiffies as documented. Interruptible variants have distinct error returns. A timeout means the waiter stopped waiting under that call; it does not mean a device, timer or work item has stopped. If a completion is embedded in a stack object and an asynchronous producer calls complete after the function returns, the producer can access invalid stack storage. Allocate or retain the object for the whole operation and synchronize or cancel every producer before freeing it.

In v6.12 kernel/sched/completion.c, SPDX GPL-2.0, __wait_for_common is shown whole, including its lockdep annotations:

static inline long __sched
__wait_for_common(struct completion *x,
		  long (*action)(long), long timeout, int state)
{
	might_sleep();

	complete_acquire(x);

	raw_spin_lock_irq(&x->wait.lock);
	timeout = do_wait_for_common(x, action, timeout, state);
	raw_spin_unlock_irq(&x->wait.lock);

	complete_release(x);

	return timeout;
}

The waiter holds x->wait.lock for the done check and queue bookkeeping in do_wait_for_common, and drops it around each sleep. A done recorded before the wait is therefore seen by the check rather than lost. The excerpt does not show the timeout return value or the signal path, and it does not say when a producer may stop touching the completion.

For a worked example, a driver submits a device request and waits with a bounded timeout. At time 0 the request owns a reference to context C; at time 1 the waiter times out; at time 2 the device completion arrives. If the waiter freed C at time 1, the later callback can use freed memory. A correct design marks the request canceled or timed out, coordinates the hardware and callback, waits for or otherwise accounts for the final producer reference, and only then frees C. The precise API sequence is subsystem-specific. A lock around the timeout flag alone does not extend C's lifetime.

Ordering and deadlock#

A lock acquisition/release provides ordering under the Linux locking contract, but the ordering guarantee is tied to the actual participants and primitive. It does not make unrelated unlocked accesses safe or order an MMIO device transaction without the relevant I/O accessor and device protocol. A sequence counter reader may retry indefinitely under continuous writers; a completion waiter can block forever if no producer signals it; an ordered workqueue callback can deadlock if it synchronously waits for work that cannot run until the callback returns. Every wait needs a progress argument as well as a data-race argument.

Lock ordering is a partial order over acquisitions: if one path takes A then B, another path taking B then A can deadlock when they run concurrently. Interrupt reentry adds another dimension: a task can hold a lock and be interrupted on the same CPU by a handler attempting the same lock. irqsave is one possible tool when the lock's contract requires excluding that local interrupt, but it is not a universal fix for every ordering or lifetime bug. Lockdep can detect many observed locking-order problems in a suitably configured disposable guest, but absence of a warning in one run does not prove all paths safe. Do not enable host debugging knobs or deliberately deadlock the host for this exercise.

Practice#

Source-only route: draw the incorrect lost-wakeup ordering above, then draw a corrected protocol with condition publication, waiter preparation, a protected recheck and wakeup. Add the timed-out completion example and identify which actor holds each reference to C. Your deliverable must state the condition lock or ordering assumption, not merely say “use a lock.” The timeline is a model, not a recorded execution.

Own-process host route: this POSIX program models a predicate and condition variable in one ordinary userspace process. It does not exercise Linux waitqueue or completion internals directly. One worker sets ready while holding the mutex and signals; the main thread waits in a loop, then joins the worker. The program creates no additional processes and does not access shared host state.

lab_dir=$(mktemp -d) || exit 1
cd "$lab_dir" || exit 1
cat > cond.c <<'C'
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t changed = PTHREAD_COND_INITIALIZER;
static int ready;
static void check(int e) { if (e) { fprintf(stderr, "pthread error %d\n", e); exit(1); } }
static void *produce(void *unused) {
    (void)unused;
    check(pthread_mutex_lock(&lock));
    ready = 1;
    check(pthread_cond_signal(&changed));
    check(pthread_mutex_unlock(&lock));
    return NULL;
}
int main(void) {
    pthread_t t;
    check(pthread_create(&t, NULL, produce, NULL));
    check(pthread_mutex_lock(&lock));
    while (!ready) check(pthread_cond_wait(&changed, &lock));
    printf("predicate observed: %d\n", ready);
    check(pthread_mutex_unlock(&lock));
    check(pthread_join(t, NULL));
    check(pthread_cond_destroy(&changed));
    check(pthread_mutex_destroy(&lock));
    return 0;
}
C
cc -std=c11 -Wall -Wextra -Werror -pthread -o cond cond.c || exit 1
./cond

Expect predicate observed: 1. The loop is necessary even if the signal occurs before the main thread enters pthread_cond_wait: the predicate remains true under the mutex. A wakeup with the predicate still false would cause another wait. POSIX condition-variable semantics and Linux kernel waitqueue internals are not identical; the example illustrates a shared idea, not an implementation proof. If compilation or a pthread call fails, preserve the diagnostic and do not report the expected result. A hung program can be terminated as your own process from the same terminal; do not signal unrelated tasks.

For the counterexample, use the source-only timeline rather than deliberately removing the loop or creating an indefinite hang. Record the output, the two timelines and one limitation of this userspace model. Remove only the created files:

rm cond cond.c
cd /tmp
rmdir "$lab_dir"

Knowledge check#

1. Why does a lock protecting a list not automatically keep an item alive after the lock is released?
2. How can a condition become true while an incorrectly written waiter still sleeps forever?
3. What does the shown completion done update provide that an unrecorded bare wakeup does not?
4. Why can a timed-out waiter not immediately free an object that an asynchronous producer may still complete?
5. How does PREEMPT_RT change the interpretation of ordinary spinlock_t compared with raw_spinlock_t?

Answers#

1. Another participant may remove and free the item after unlock. A reference, RCU or another documented lifetime protocol must cover use beyond the protected section.
2. The producer can publish and wake after the consumer's check but before it registers to sleep. A correct prepare/check/sleep protocol and condition synchronization prevent that missed transition.
3. It records completion state while holding the completion's wait lock, so a later waiter can observe a prior signal. Correct reuse and object lifetime still need coordination.
4. Timeout only ends that wait. A callback can still run and access the object, so the producer must be canceled or synchronized and references accounted for before free.
5. PREEMPT_RT transforms many ordinary spinlocks into RT-aware sleeping lock mechanisms, while raw spinlocks retain raw spinning semantics. Actual context rules remain specific to each primitive and path.

Checkpoint#

Deliver the lost-wakeup and completion-timeout timelines, plus the labeled userspace program output if run. Pass when you state the condition's synchronization, distinguish serialization from lifetime, explain one lock-order deadlock and identify the PREEMPT_RT caveat. If uncertain, trace __wake_up_common_lock and complete_with_flags, then revise the model. This is not certification.

Sources#

• v6.12 waitqueue implementation and wait interfaces.
• v6.12 completion implementation and completion interfaces.
• Lock types.
• Completions.