4 min read #linux-kernel #Synchronization Mechanisms
On this page

Locking Mechanisms

Coverage: spinlock (qspinlock) → mutex (optimistic spinning) → rw_semaphore (percpu) → seqlock → atomic → memory barriers (acquire/release) Kernel versions: 2.6 ~ 6.x, with emphasis on qspinlock (4.2+) and percpu rwsem (5.x+)

Overview

The core problem of kernel concurrency control: multiple CPUs accessing shared data simultaneously. Solutions range from the lightest atomic operations to heavyweight mutexes, forming a clear "lock selection chain." Choosing the wrong lock can range from unnecessary cache line bouncing to deadlocks.

Key principle: Locks protect data, not code. When designing a locking strategy, first determine "which data is accessed by which contexts," and then select the appropriate lock.

Lock Selection Decision Tree

flowchart TD
    START["Access shared data<br/>Need synchronization?"]

    START --> Q1{"Just a single integer<br/>(add/sub/set bit)?"}
    Q1 -->|"Yes"| ATOMIC["atomic_t / atomic64_t<br/>Lock-free, hardware guarantees atomicity ✅"]

    Q1 -->|"No"| Q2{"Can sleep?"}

    Q2 -->|"Yes"| Q3{"Read-heavy?"}
    Q3 -->|"Yes"| RWSEM["rw_semaphore<br/>Multiple readers can hold the lock simultaneously"]
    Q3 -->|"No"| MUTEX["mutex (preferred)<br/>Optimistic spinning → Sleep"]

    Q2 -->|"No<br/>(interrupt/softirq context)"| Q4{"Write-light + Reads cannot block?"}
    Q4 -->|"Yes"| RCU["RCU / seqlock<br/>Zero-overhead for readers"]

    Q4 -->|"No"| Q5{"Need multiple readers<br/>to hold the lock simultaneously?"}
    Q5 -->|"Yes"| RWLOCK["rwlock_t"]
    Q5 -->|"No"| SPIN["spinlock"]

    SPIN --> Q6{"What to protect against?"}
    Q6 -->|"Only softirq"| SPIN_BH["spin_lock_bh"]
    Q6 -->|"Interrupts + softirq"| SPIN_IRQ["spin_lock_irqsave"]

    classDef start fill:#e3f2fd,stroke:#1565c0
    classDef decision fill:#fff3e0,stroke:#ef6c00
    classDef lock fill:#e8f5e9,stroke:#2e7d32
    classDef api fill:#f3e5f5,stroke:#7b1fa2
    class START start
    class Q1,Q2,Q3,Q4,Q5,Q6 decision
    class ATOMIC,RWSEM,MUTEX,RCU,RWLOCK,SPIN lock
    class SPIN_BH,SPIN_IRQ api

Spinlock: qspinlock (4.2+)

Why qspinlock is needed

Problems with old ticket spinlocks:
  Every CPU spins on the lock word → all CPUs read the same cache line
  → cache line bounces between all CPUs
  > 16 cores: performance disaster

qspinlock (queued spinlock):
  Each CPU spins on its own per-CPU MCS node
  → Each CPU spins on a different cache line!
  → Only unlock requires writing to the next CPU's node → one cache line transfer
  → Effective even with > 128 cores

// kernel/locking/qspinlock.c
// 4-byte atomic word for qspinlock:
//   byte 0: locked (1 bit) + pending (1 bit)
//   byte 1: tail index (points to the tail of the MCS node queue)
//   bytes 2-3: tail CPU

void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) {
    // 1. If lock is free → take it directly (CAS on locked byte)
    // 2. If pending bit is not set → set pending, wait for locked bit to clear
    // 3. Otherwise → join the MCS node queue (spin on own node)
}

// API (include/linux/spinlock.h):
spin_lock(&lock);            // Acquire lock (assumes preemption disabled)
spin_unlock(&lock);          // Release
spin_lock_irq(&lock);        // Disable local interrupts + acquire lock
spin_unlock_irq(&lock);
spin_lock_irqsave(&lock, flags);   // Save IF state + disable interrupts + acquire lock
spin_unlock_irqrestore(&lock, flags);
spin_lock_bh(&lock);         // Disable bottom half (softirq) + acquire lock
spin_unlock_bh(&lock);

Mutex: Optimistic Spinning

// kernel/locking/mutex.c
struct mutex {
    atomic_long_t       owner;          // task_struct * of current holder
    raw_spinlock_t      wait_lock;      // Protects wait_list
    struct list_head    wait_list;      // Wait queue
};

mutex_lock(&lock):
  1. Fast path: No one holds the lock → atomic_long_cmpxchg sets owner = current, returns
  2. Optimistic spinning: Is the owner running on another CPU?
     → Spin waiting (no sleep needed, expecting owner to release soon)
     → Owner is not running (has slept) → Stop spinning, enter sleep
  3. Sleep waiting: Set TASK_UNINTERRUPTIBLE, add to wait_list, schedule()

mutex_unlock(&lock):
  1. Set owner = 0
  2. If wait_list is not empty → wake up the first waiter
      → wake_up_process() → waiter returns to step 2 of mutex_lock

rw_semaphore: Read-Write Semaphore

// kernel/locking/rwsem.c
// percpu rwsem (5.x+ optimization):
//   Read lock: Increment percpu refcount → No global lock needed (local CPU operation)
//   Write lock: Iterate over all CPUs' percpu refcounts → Wait for all to be zero

// Reader starvation protection:
//   rwsem tracks if there are waiting writers
//   If there are waiting writers → new readers are blocked → writers won't starve

down_read(&sem);              // Acquire read lock
up_read(&sem);
down_write(&sem);             // Acquire write lock
up_write(&sem);
down_read_trylock(&sem);      // Non-blocking

Seqlock: Sequence Lock

// include/linux/seqlock.h
// Writers are mutually exclusive (acquire spinlock), readers are lock-free
// Readers detect "is a writer modifying?" via sequence number → retry

struct seqlock {
    seqcount_t seq;       // Sequence number (even = stable, odd = writing)
    spinlock_t lock;      // Protects writers
};

// Reader:
do {
    seq = read_seqbegin(&seqlock);   // Record sequence number
    // ... read data ...
} while (read_seqretry(&seqlock, seq));  // Sequence number changed? Retry

// Writer:
write_seqlock(&seqlock);
seq++;    // Odd → readers see this and retry
// ... modify data ...
seq++;    // Even → readers can read
write_sequnlock(&seqlock);

// Classic use case: timekeeper (lock-free read for gettimeofday, rarely written)

Atomic Operations

// include/linux/atomic/atomic-instrumented.h
// Basic atomic operations guaranteed by all architectures:

// Arithmetic
atomic_inc(&v);  atomic_dec(&v);
atomic_add(n, &v);  atomic_sub(n, &v);

// CAS (Compare-And-Swap)
atomic_cmpxchg(&v, old, new);  // if (v==old) v=new; return old;

// RMW with memory ordering (5.x+)
atomic_add_return(n, &v);       // return v+n (full barrier)
atomic_add_return_acquire(n, &v);  // ACQUIRE semantics
atomic_add_return_release(n, &v);  // RELEASE semantics

// Bit operations
set_bit(nr, addr);  clear_bit(nr, addr);
test_and_set_bit(nr, addr);  // Atomic test + set → used to implement simple locks

Memory Barriers

Compiler barrier:
  barrier(): Prevents compiler reordering (does not affect CPU hardware reordering)

CPU memory barriers:
  smp_mb():  Full barrier (ordering of all memory operations before and after)
  smp_rmb(): Read barrier (loads do not cross)
  smp_wmb(): Write barrier (stores do not cross)

Acquire/Release semantics:
  ACQUIRE: Loads/stores after this operation cannot be reordered before it
  RELEASE: Loads/stores before this operation cannot be reordered after it
  
  spin_lock()   = ACQUIRE (critical section operations do not leak outside the lock)
  spin_unlock() = RELEASE

When is an explicit barrier needed?
  → Lock-free data structures (ring buffers, RCU)
  → Device DMA (ensure DMA buffer writes are completed before starting DMA)

Debugging and Lock Analysis

# lockdep: Lock dependency validation (deadlock detection)
dmesg | grep -i lockdep   # Automatically checks at boot

# lockstat: Lock contention statistics
cat /proc/lock_stat | head -20

# Trigger lock contention tracing
echo 1 > /sys/kernel/debug/tracing/events/lock/lock_acquire/enable
echo 1 > /sys/kernel/debug/tracing/events/lock/lock_release/enable

References

  • Source Code: kernel/locking/ (qspinlock, mutex, rwsem, rtmutex), include/linux/seqlock.h, include/linux/atomic/
  • Kernel Documentation: Documentation/locking/ directory
  • LWN: "Queued spinlocks", "The percpu rwsem", "Memory barriers for kernel hackers"

Keywords: qspinlock, mutex, rw_semaphore, seqlock, atomic, CAS, memory barrier, acquire/release, lockdep

Related pages

© 2026 liz's doc