Documentation Index

Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt

Use this file to discover all available pages before exploring further.

​

Advanced Synchronization

​

0. From Data Races to Correct Patterns

​

0.1 Broken Counter: Lost Updates

// BUGGY: Incrementing a shared counter without synchronization
volatile int counter = 0;

void *worker(void *arg) {
    for (int i = 0; i < 1000000; i++) {
        counter++;  // data race
    }
    return NULL;
}

• On a multi-core system, counter++ compiles to load, increment, store.
• Two threads can read the same old value and both write back, losing updates.

int counter = 0;
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;

void *worker(void *arg) {
    for (int i = 0; i < 1000000; i++) {
        pthread_mutex_lock(&m);
        counter++;
        pthread_mutex_unlock(&m);
    }
    return NULL;
}

​

0.2 Reader-Writer Pattern

• Anti-pattern: Using a single mutex around a large data structure that is read-mostly.
• Pattern: Use a reader-writer lock or RCU so that many readers can proceed in parallel while writers serialize.

​

0.3 Producer–Consumer Queue

pthread_mutex_t q_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t q_not_empty = PTHREAD_COND_INITIALIZER;

void enqueue(item *it) {
    pthread_mutex_lock(&q_mutex);
    push_to_queue(it);
    pthread_cond_signal(&q_not_empty);
    pthread_mutex_unlock(&q_mutex);
}

item *dequeue(void) {
    pthread_mutex_lock(&q_mutex);
    while (queue_empty()) {
        pthread_cond_wait(&q_not_empty, &q_mutex);
    }
    item *it = pop_from_queue();
    pthread_mutex_unlock(&q_mutex);
    return it;
}

​

1. RCU (Read-Copy-Update)

​

The RCU Philosophy

1. Readers: Don’t use any locks. They just read the data.
2. Writers: Instead of modifying data in place, they:
   • Create a Copy of the data.
   • Update the copy.
   • Publish the new pointer atomically (using a memory barrier).
   • Defer the deletion of the old data until all current readers are finished.

​

Grace Periods & Quiescent States

• Quiescent State: A point in time where a CPU is guaranteed not to be in an RCU read-side critical section (e.g., a context switch, returning to user space, or entering the idle loop). The key insight is that RCU read-side critical sections cannot span these boundaries.
• Grace Period: The time interval during which every CPU has passed through at least one quiescent state. Once the grace period ends, no reader can possibly still have a reference to the old data. Grace periods are typically milliseconds long, which is why RCU trades memory for latency: the old copy lives a bit longer, but readers are never stalled.

​

RCU vs. Reader-Writer Locks

​

2. Kernel Lock Validation: lockdep

​

How lockdep Works

• Lock Classes: Every lock belongs to a class (e.g., all inode->i_lock instances belong to one class). lockdep does not track individual lock instances — that would be too expensive. Instead, it tracks the acquisition patterns between classes. If any inode->i_lock is ever held before any dentry->d_lock, lockdep records the dependency inode_lock -> dentry_lock for all instances.
• Dependency Tracking: lockdep builds a directed graph of lock acquisition order. If it sees Lock A -> Lock B in one code path and Lock B -> Lock A in another, it triggers a “Possible Deadlock” warning — even if the two code paths have never actually run concurrently. This is powerful: it catches bugs that would otherwise only manifest under rare timing conditions.
• IRQ Context Tracking: It also tracks if a lock is acquired both with and without interrupts enabled. If a thread holds spinlock S with interrupts on, and an interrupt handler also acquires S, the interrupt will spin forever waiting for S to be released — but the release cannot happen because the interrupt preempted the holder. lockdep catches this by tracking in_irq vs not_in_irq context for every lock class.

# Check for lockdep warnings in the kernel log
dmesg | grep -i "possible.*deadlock"
dmesg | grep -i "inconsistent lock state"

# lockdep statistics (how many lock classes it is tracking)
cat /proc/lockdep_stats

​

3. Lock-Free & Wait-Free Progress

• Lock-Free: At least one thread in the system is guaranteed to make progress in a finite number of steps. This prevents system-wide deadlocks but allows individual threads to starve.
• Wait-Free: Every thread is guaranteed to make progress in a finite number of steps. This is the strongest guarantee, common in Hard RTOS.
• Obstruction-Free: A thread makes progress only if it executes in isolation (no other thread interferes).

​

CAS (Compare-And-Swap) Internals

// Pseudo-code for Atomic Compare and Swap.
// The entire if-then-write happens atomically in hardware --
// no other CPU can interleave between the comparison and the store.
bool CAS(int *addr, int expected, int new_val) {
    if (*addr == expected) {
        *addr = new_val;
        return true;   // Success: we were the one to update it
    }
    return false;       // Failure: someone else changed it first
}

​

Lock-Free Stack Example

// A lock-free stack node
struct node {
    int value;
    struct node *next;
};

// Global stack top pointer (shared between all threads)
struct node *top = NULL;

void push(int value) {
    struct node *new_node = malloc(sizeof(*new_node));
    new_node->value = value;

    do {
        // Snapshot the current top
        new_node->next = top;
        // Attempt to swing the top pointer to our new node.
        // If another thread pushed between our snapshot and this CAS,
        // CAS fails (top != new_node->next), and we retry with
        // the updated snapshot.
    } while (!CAS(&top, new_node->next, new_node));
}

​

4. The ABA Problem

1. Thread 1 reads value A from a pointer and prepares a CAS to update it.
2. Thread 2 changes the pointer to B (maybe freeing A), does some work, allocates new memory that happens to land at the same address as old A, and writes A back.
3. Thread 1 performs CAS, sees A, and thinks nothing has changed — but the underlying data at address A is completely different. Thread 1 has been tricked into accepting a stale, recycled object.

• Solution: Hazard Pointers (each thread publishes which pointers it is currently examining, preventing reclamation), Epoch-based Reclamation (like RCU — defer freeing until all threads have moved to a new epoch), or Tagged Pointers (pack a monotonically increasing counter into the pointer so CAS detects the version change even if the address is reused).

​

5. Memory Barriers in Sync

• Acquire Barrier: Applied on lock(). Ensures subsequent loads/stores stay after the lock is acquired. No memory operation after the lock can “leak” above it.
• Release Barrier: Applied on unlock(). Ensures preceding loads/stores stay before the lock is released. No memory operation before the unlock can “leak” below it.
• Full Barrier (mfence): Prevents any reordering across the barrier in either direction. Used in __sync_synchronize() and atomic_thread_fence(memory_order_seq_cst).

// Without barriers, this publish/consume pattern is broken on
// weakly-ordered architectures (ARM, POWER):

// Thread A (publisher)
data = 42;
smp_wmb();          // Write memory barrier: ensures data=42 is visible
                    // before ready=true becomes visible to other CPUs
ready = true;

// Thread B (consumer)
while (!ready) ;    // Spin until ready
smp_rmb();          // Read memory barrier: ensures we see the data
                    // that was written before ready was set
assert(data == 42); // Safe after the barrier

​

6. Interview Deep Dive

​

Summary for Senior Engineers

• Use RCU for read-mostly data structures (like routing tables or file descriptor tables). It is the single most important synchronization primitive in the Linux kernel.
• Understand that lockdep is your best friend during kernel development. It catches deadlocks that would otherwise only manifest under rare timing conditions in production.
• Avoid custom lock-free structures unless you are prepared to handle the ABA problem and memory ordering nuances. In most cases, a well-tuned mutex or RCU is both safer and fast enough.
• Memory Barriers are what actually make synchronization work across multiple CPU cores. If you write lock-free code without understanding barriers, it will work on x86 and break on ARM.
• Know the hierarchy: mutex (simple, correct) -> rwlock (read parallelism) -> RCU (zero-cost reads) -> lock-free CAS (maximum control, maximum risk). Move down this list only when profiling proves you need to.

​

Interview Deep-Dive

struct padded_counter {
    long value;
    char padding[56];
} __attribute__((aligned(64)));
struct padded_counter per_cpu[MAX_CPUS];

void increment() { per_cpu[sched_getcpu()].value++; }
long read_total() {
    long sum = 0;
    for (int i = 0; i < num_cpus; i++) sum += per_cpu[i].value;
    return sum;
}