Concurrency

The last chapter answered may this code sleep? This one answers the other question you must always be able to answer:

Who else can be touching this data right now?

If your answer is "nothing", you have to be able to prove it. "Nothing else runs here" is a claim about every CPU, every interrupt, and every preemption point in the system, and it is almost always false.

Six concepts in the six-part treatment: the data race, spinlocks and mutexes, atomics and lockless access, RCU, per-CPU data, and lockdep.

Concept 1: The Data Race

1. What problem it solves

Nothing. A data race is the problem. This section exists because the intuition people bring from single-threaded C — "I wrote it, then I read it, so I get what I wrote" — is not merely unreliable in the kernel, it is undefined behavior, and the compiler is entitled to act on that.

Three things can go wrong, and only the first is the one people expect:

  1. INTERLEAVING       Two CPUs read-modify-write the same word.
                        counter++ is load, add, store. Two CPUs, one increment lost.

  2. THE COMPILER       A plain load of a shared variable may be:
                          • fused    (read once, reused across a loop — your poll never ends)
                          • split    ("tearing": one 64-bit store becomes two 32-bit stores)
                          • invented (re-read, so two uses see two different values)
                          • hoisted or sunk across other statements
                        None of this is a bug in the compiler. You did not tell it the
                        variable was shared.

  3. THE CPU            Stores can become visible to other CPUs in a different order
                        than you issued them. On x86 rarely; on arm64 and powerpc,
                        routinely. Your "set the data, then set the ready flag" is
                        observed by another CPU as "ready flag set, data garbage".

2. Where it exists in the kernel

Everywhere two things can reach the same memory: two CPUs, a CPU and an interrupt, a task and a preempting task, or the CPU and a DMA-capable device.

$EDITOR Documentation/memory-barriers.txt          # the canonical reference. Long. Worth it.
$EDITOR Documentation/atomic_t.txt
ls tools/memory-model/                              # the formal model, with runnable litmus tests
$EDITOR tools/memory-model/README

3. Who owns or interacts with it

4. The structures and code paths

The minimum discipline for any variable touched by more than one context:

/* WRONG: a plain access to shared data is a data race. */
while (!thing->ready)               /* the compiler may read this ONCE */
        cpu_relax();
x = thing->value;

/* RIGHT, if you only need "no tearing, no fusing": */
while (!READ_ONCE(thing->ready))
        cpu_relax();
x = READ_ONCE(thing->value);        /* ...but see below: still not ordered */

/* RIGHT, with ordering — the standard "publish" pattern: */
/* writer:  */
WRITE_ONCE(thing->value, 42);
smp_store_release(&thing->ready, true);   /* everything before is visible first */

/* reader:  */
if (smp_load_acquire(&thing->ready))      /* ...to anyone who sees `ready` */
        x = READ_ONCE(thing->value);      /* guaranteed to be 42, not garbage */

Warning: A barrier on one side is always a bug. Ordering is a pairing: a release on the writer means nothing without an acquire on the reader. When you write a barrier, write a comment naming the barrier it pairs with and the file it lives in. Documentation/memory-barriers.txt says this too, and reviewers enforce it.

5. Experiment

CLAIM. An unsynchronized increment loses updates, and the loss scales with CPU count — so a single-CPU test proves nothing.

METHOD. A module with a thread per CPU, each incrementing a shared counter:

static int          plain_counter;
static atomic_t     atomic_counter = ATOMIC_INIT(0);
static DEFINE_SPINLOCK(lock);
static int          locked_counter;

#define ITERS 200000

static int bump(void *unused)
{
        int i;

        for (i = 0; i < ITERS; i++) {
                plain_counter++;                       /* racy on purpose  */
                atomic_inc(&atomic_counter);
                spin_lock(&lock);
                locked_counter++;
                spin_unlock(&lock);
                if (!(i % 4096))
                        cond_resched();
        }
        return 0;
}
/* start one kthread per online CPU, wait for all, then print all three */

PREDICT FIRST, in writing, for -smp 1, -smp 4, and -smp 8:

RESULT. Record the actual numbers. Two things to notice: the plain counter is exactly right at -smp 1 and badly wrong at -smp 8, and the loss is not a small percentage. Then run the same module on a CONFIG_KCSAN kernel and read the report:

BUG: KCSAN: data-race in bump / bump
write to 0xffffffffc0... of 4 bytes by task 219 on cpu 3:
 bump+0x2c/0x120 [race]
read to 0xffffffffc0... of 4 bytes by task 218 on cpu 1:
 bump+0x24/0x120 [race]

That report names both sides of the race and the CPU each was on. It is the tool that finds this class of bug without you having to guess where to look.

6. Failure mode

Concept 2: Spinlocks and Mutexes

1. What problem it solves

Mutual exclusion: only one context at a time inside a critical section. There are two families because there are two situations — one where waiting by sleeping is possible, and one where it is not — and the whole of the previous chapter is about telling them apart.

2. Where it exists in the kernel

ls include/linux/spinlock.h include/linux/mutex.h include/linux/rwsem.h include/linux/seqlock.h
ls kernel/locking/
$EDITOR Documentation/locking/locktypes.rst      # the authoritative comparison, incl. PREEMPT_RT

3. Who owns or interacts with it

4. The comparison, and the choice

The choice, as a rule: use a mutex by default. Reach for a spinlock only when the critical section must run in atomic context — because an interrupt handler touches the data, or because it is genuinely a handful of instructions.

The variants, and the rule that makes them necessary. If a lock is ever taken from an interrupt, then every other acquisition must prevent that interrupt from arriving on the same CPU — otherwise the interrupt deadlocks against the holder it just preempted.

   CPU 0:  spin_lock(&L)             ← process context
              │
              ├── interrupt arrives on CPU 0
              │      handler: spin_lock(&L)  ← spins forever, waiting for a
              │                                 holder that cannot run until
              │                                 the handler returns.  DEADLOCK.

Inside the interrupt handler itself, plain spin_lock() is correct — that interrupt is already running, and on that CPU it cannot re-enter.

Tip: spin_lock_irqsave saves and restores the flags rather than unconditionally re-enabling, which is why it is safe to call from anywhere including a context that already had IRQs off. spin_lock_irq unconditionally enables on unlock, and using it in a context that had them off is a subtle, painful bug. Default to irqsave; a reviewer will tell you when irq is provably fine.

The other sleeping locks, briefly:

5. Experiment

CLAIM. Choosing spin_lock() where spin_lock_irqsave() was required produces a deadlock, and lockdep reports it the first time it merely sees the possibility — without ever deadlocking.

METHOD. A module that takes a lock in a timer callback (softirq) and in write() (process context), with the wrong variant:

static DEFINE_SPINLOCK(l);

static void lab_timer_fn(struct timer_list *t)
{
        spin_lock(&l);              /* softirq context */
        shared++;
        spin_unlock(&l);
        mod_timer(&lab_timer, jiffies + 1);
}

static ssize_t lab_write(struct file *f, const char __user *b, size_t n, loff_t *o)
{
        spin_lock(&l);              /* WRONG: should be spin_lock_bh() */
        shared++;
        spin_unlock(&l);
        return n;
}

PREDICT FIRST: with CONFIG_PROVE_LOCKING=y, does the splat appear (a) immediately on load, (b) the first time you write(), (c) only when the timer actually fires during a write(), or (d) only if a real deadlock happens?

RESULT. The answer is (b) — and that is the entire value of lockdep. It records that this lock is taken in softirq context and, the first time it is taken without bottom halves disabled, reports:

WARNING: inconsistent lock state
--------------------------------
inconsistent {SOFTIRQ-ON-W} -> {IN-SOFTIRQ-W} usage.

You never had to hit the timing window. lockdep proves the deadlock is possible from a single observation of each side.

6. Failure mode

Concept 3: Atomics, Reference Counts, and Lockless Access

1. What problem it solves

A lock around a single counter is expensive relative to the work it protects. The hardware provides atomic read-modify-write instructions; the kernel wraps them in a typed API so the compiler cannot undermine them and so the intent — counter vs. reference count vs. bit — is visible in the type.

2. Where it exists in the kernel

ls include/linux/atomic/ include/linux/refcount.h include/linux/kref.h include/linux/bitops.h
$EDITOR Documentation/atomic_t.txt
$EDITOR Documentation/core-api/refcount-vs-atomic.rst

3. The three types, and choosing between them

/* Use refcount_t for reference counts. Not atomic_t. This is a real
 * review comment and there was a tree-wide conversion effort.        */
struct thing {
        refcount_t      ref;
        struct list_head node;
};

refcount_set(&t->ref, 1);               /* NOT refcount_inc from 0 */

if (!refcount_inc_not_zero(&t->ref))    /* the correct "get" for an object
        return NULL;                     * you found via a lookup           */

if (refcount_dec_and_test(&t->ref))     /* true exactly once, at zero       */
        kfree(t);

Warning: atomic_read() and atomic_set() are not barriers and do not order anything. atomic_read(&x) == 0 tells you a value that was true at some instant and may not be by the time you act on it. The atomic operations that do imply ordering are the ones that return a value (atomic_dec_and_test, atomic_add_return, atomic_cmpxchg, xchg). Documentation/atomic_t.txt has the exact table; read it before you write a lockless algorithm, and prefer a lock until you can explain that table.

4. When lockless is the wrong instinct

Lockless code is not "faster locking". It is a different, much harder discipline where the failure mode is a rare corruption instead of a hang, and where the correctness argument must reference the memory model rather than intuition.

The honest hierarchy:

  1. A mutex.                      Boring. Correct. Start here, always.
  2. A spinlock.                   When you must be atomic.
  3. RCU.                          When reads dominate and you can define a grace period.
  4. Per-CPU data.                 When the data is genuinely per-CPU.
  5. Atomics with ordering.        When you can cite Documentation/atomic_t.txt.
  6. A hand-rolled lockless algo.  When you have a litmus test in tools/memory-model/
                                   and a maintainer has agreed.

Most patches that reach for level 6 should have been at level 1 and are rejected. Optimizing a lock you have not measured is the single most common way to introduce a bug that outlives you.

5. Experiment

CLAIM. refcount_t converts a refcount overflow — the shape of many real CVEs — from a use-after-free into a loud, harmless warning.

METHOD.

static refcount_t r;
static atomic_t   a;

static int __init ref_init(void)
{
        refcount_set(&r, 1);
        atomic_set(&a, 1);

        /* Drive both to the top of the type. */
        while (refcount_read(&r) != UINT_MAX && !refcount_read(&r) == 0)
                refcount_inc(&r);       /* observe what happens at the top */

        pr_info("refcount saturated at %u\n", refcount_read(&r));
        refcount_dec(&r);
        pr_info("after dec: %u  (did it come back down?)\n", refcount_read(&r));
        return 0;
}

PREDICT FIRST: at saturation, does refcount_inc (a) wrap to 0, (b) stick at UINT_MAX, (c) WARN and stick, or (d) panic? And after saturation, does refcount_dec bring it back down?

RESULT. Then reason about why the answer matters: with atomic_t, an attacker who can trigger get more times than put wraps the count to zero, the object is freed while still referenced, and that is an exploit. With refcount_t, the count sticks at the top, the object leaks, and a WARN appears in dmesg. A leak is a bug; a use-after-free is a compromise.

6. Failure mode

Concept 4: RCU

1. What problem it solves

Some data is read constantly and modified rarely: a list of network devices, a routing table, a policy table. Taking a lock on every read costs a cache-line bounce between CPUs even when there is no writer at all, and that cost is the dominant one on a large machine.

Read-Copy-Update removes the read-side cost entirely. Readers take no lock, execute no atomic operation, and write to no shared cache line. The cost moves to the writer, which must keep the old version alive until every pre-existing reader has finished with it.

2. Where it exists in the kernel

ls kernel/rcu/ Documentation/RCU/
$EDITOR Documentation/RCU/whatisRCU.rst        # start here
$EDITOR Documentation/RCU/checklist.rst        # read before you write any RCU code
rg -n "rcu_dereference\b|rcu_assign_pointer\b" include/linux/rcupdate.h | head

3. Who owns or interacts with it

4. The mechanism

   WRITER                                READERS
   ──────                                ───────
   old = p                               rcu_read_lock()
   new = copy_of(old)                    q = rcu_dereference(p)     ← may be old OR new
   modify(new)                           ...use q...
   rcu_assign_pointer(p, new) ──────┐    rcu_read_unlock()
                                    │
   synchronize_rcu()  ← BLOCKS until every reader that could still
      (or call_rcu / kfree_rcu,       be holding the OLD pointer has
       which defer instead)           finished its read-side section
                                    │
   free(old)  ◀─────────────────────┘   ← now provably safe

The reader side compiles to almost nothing. The writer pays a grace period, which is long — often milliseconds — and that asymmetry is the entire design.

/* Reader. No lock, no atomic op, no shared write. */
rcu_read_lock();
t = rcu_dereference(global_thing);
if (t)
        use(t->field);          /* valid only until rcu_read_unlock() */
rcu_read_unlock();
/* t must NOT escape this section. */

/* Writer. */
new = kmalloc(sizeof(*new), GFP_KERNEL);
*new = *old;
new->field = value;

spin_lock(&writer_lock);        /* writers still exclude each other */
rcu_assign_pointer(global_thing, new);
spin_unlock(&writer_lock);

kfree_rcu(old, rcu);            /* free after a grace period; needs a
                                 * struct rcu_head named `rcu` in the struct */
/* or, if you must wait synchronously (process context only — it sleeps): */
/* synchronize_rcu(); kfree(old); */

5. Experiment

CLAIM. An RCU read-side section costs essentially nothing, and synchronize_rcu() costs a lot — and the ratio is the reason RCU exists.

METHOD. Time both in a module:

u64 t0 = ktime_get_ns();
for (i = 0; i < 1000000; i++) {
        rcu_read_lock();
        v = READ_ONCE(*(volatile int *)&dummy);
        rcu_read_unlock();
}
pr_info("1M read sections: %llu ns\n", ktime_get_ns() - t0);

t0 = ktime_get_ns();
synchronize_rcu();
pr_info("one synchronize_rcu(): %llu ns\n", ktime_get_ns() - t0);

PREDICT FIRST: nanoseconds per read-side section, and nanoseconds for one synchronize_rcu(). Write both numbers down, then compute the ratio you predicted and compare it with reality.

Then deliberately break it and let CONFIG_PROVE_RCU catch you:

t = rcu_dereference(global_thing);       /* with NO rcu_read_lock() */

WARNING: suspicious RCU usage
-----------------------------
lab.c:NN suspicious rcu_dereference_check() usage!
other info that might help us debug this:
rcu_scheduler_active = 2, debug_locks = 1
no locks held by insmod/412.

6. Failure mode

Concept 5: Per-CPU Data

1. What problem it solves

If each CPU only ever touches its own copy of a variable, there is no sharing, no cache-line bouncing, and no lock. Statistics counters, caches, and free-lists are the archetypal uses — the kernel keeps a great many of its counters this way, which is why reading them means summing.

2. Where it exists in the kernel

ls include/linux/percpu.h include/linux/percpu-defs.h
$EDITOR Documentation/core-api/this_cpu_ops.rst
rg -n "DEFINE_PER_CPU\(" kernel/ mm/ | head

3. The API, and the one rule

static DEFINE_PER_CPU(u64, lab_events);

/* Increment this CPU's copy. this_cpu_inc() is atomic WITH RESPECT TO
 * preemption and interrupts on this CPU — it does the disable for you. */
this_cpu_inc(lab_events);

/* If you need a pointer for several operations, you must pin yourself
 * to the CPU for the whole sequence, or you may migrate mid-way and
 * update two different CPUs' copies.                                   */
u64 *p = get_cpu_ptr(&lab_events);      /* preempt_disable() inside */
*p += 1;
*p += weight;
put_cpu_ptr(&lab_events);               /* preempt_enable() */

/* Reading the total: sum across all possible CPUs. Inherently a
 * snapshot — another CPU is incrementing while you sum.                */
u64 total = 0;
int cpu;
for_each_possible_cpu(cpu)
        total += per_cpu(lab_events, cpu);

The one rule: this_cpu_ptr() is only valid with preemption disabled. If you are preempted and migrated between obtaining the pointer and using it, you write to the wrong CPU's data. CONFIG_DEBUG_PREEMPT catches this and prints BUG: using smp_processor_id() in preemptible code.

Note for_each_possible_cpu rather than for_each_online_cpu: an offlined CPU's counters still hold the events it recorded, and dropping them silently loses data.

4. Experiment

CLAIM. Per-CPU counters are dramatically cheaper than a shared atomic under contention, and the gap widens with CPU count.

METHOD. Extend the Concept 1 module with a third counter, this_cpu_inc(percpu_counter), and time all three at -smp 1, -smp 4, and -smp 8.

PREDICT FIRST: the ratio of atomic-increment time to per-CPU-increment time at 1 CPU and at 8. Most people predict the right direction and badly underestimate the magnitude at 8.

5. Failure mode

Concept 6: lockdep

1. What problem it solves

Deadlocks are timing-dependent. A lock-order inversion between two code paths may need a specific interleaving that happens once a month on one customer's machine. Testing cannot find these.

lockdep proves them instead. It records, for every lock, the class of lock, every order in which it has ever been acquired relative to others, and every context it has been taken in. Then it reports a possible deadlock the first time it observes each half — without the two halves ever having to race.

2. Where it exists in the kernel

ls kernel/locking/lockdep.c Documentation/locking/lockdep-design.rst
grep -E 'CONFIG_(PROVE_LOCKING|LOCKDEP|DEBUG_LOCK_ALLOC)=' ~/kernel/build/.config
cat /proc/lockdep_stats 2>/dev/null | head

3. The splats, and what each means

Read a splat in this order: the two stack traces at the bottom (which show the two orders), then the Chain exists of: summary (which names the classes), then the "Possible unsafe locking scenario" ASCII diagram lockdep prints for you. It has already done the analysis; your job is to decide which of the two orders is wrong.

The false positive you will actually hit. lockdep derives a lock's class from where it was initialized. An array of per-object locks all initialized in one loop share a class, so locking two different objects looks like recursion:

/* lockdep sees ONE class for all of these, and reports recursive locking. */
for (i = 0; i < n; i++)
        spin_lock_init(&obj[i].lock);

/* Fix, when the order is genuinely well-defined (e.g. by index): */
spin_lock(&a->lock);
spin_lock_nested(&b->lock, SINGLE_DEPTH_NESTING);
/* Or give them distinct classes with lockdep_set_class(). */

Do not suppress the warning until you have proved your ordering is well-defined. lockdep is right far more often than you are.

4. Experiment

CLAIM. lockdep detects an ABBA deadlock without the deadlock ever occurring.

METHOD. Two locks, two functions, opposite orders — and call each once, seconds apart, from process context:

static DEFINE_MUTEX(a);
static DEFINE_MUTEX(b);

static void path1(void) { mutex_lock(&a); mutex_lock(&b); mutex_unlock(&b); mutex_unlock(&a); }
static void path2(void) { mutex_lock(&b); mutex_lock(&a); mutex_unlock(&a); mutex_unlock(&b); }

static int __init dl_init(void)
{
        path1();
        msleep(1000);        /* no possibility of a real race */
        path2();
        return 0;
}

PREDICT FIRST: does the machine hang? Does anything appear in dmesg? If so, after path1, after path2, or neither?

RESULT. No hang — the calls are a second apart and single-threaded. But dmesg contains a full circular-dependency report after path2, because lockdep only needed to see both orders, never to have them collide. Write down what this implies about how much you should trust "I could not reproduce a deadlock."

5. Failure mode

Choosing: The Decision Table

The Deadlock Patterns

Validation / Self-check

1. Name three distinct things that can go wrong with an unsynchronized shared variable. Which two do people forget?
2. What exactly does READ_ONCE guarantee, and what does it not?
3. Why is a barrier on only one side of a publish/subscribe pattern always a bug?
4. Give the rule for choosing between spin_lock, spin_lock_bh, and spin_lock_irqsave.
5. Draw the deadlock that occurs when a lock is taken in process context with plain spin_lock and also in a hardware interrupt handler.
6. Why is spin_lock_irqsave the safer default over spin_lock_irq?
7. Why must a reference count be refcount_t rather than atomic_t? Describe the exploit the type prevents.
8. Do atomic_read and atomic_set imply any ordering? What follows from the answer?
9. Explain RCU's asymmetry in one sentence: what do readers pay, and what do writers pay?
10. Why may a pointer obtained from rcu_dereference not escape the read-side section?
11. When is RCU the wrong choice?
12. Why must this_cpu_ptr be used with preemption disabled, and why do you sum with for_each_possible_cpu?
13. How can lockdep report a deadlock that has never happened? What does it record?
14. You get "possible recursive locking detected" on an array of per-object locks that you are certain you lock in index order. What is the correct fix, and what is the incorrect one?
15. You have a shared counter in a hot path. Rank these by what you should try first: a mutex, a spinlock, atomic_t, per-CPU, a hand-rolled lockless scheme. Justify the ordering.

Next: Memory — which allocator, which GFP flags, and why the memory you just allocated may be unreachable by the device you allocated it for.