┌─────────────────────────────────────────────────────────────────────────────┐
│                   KERNEL EXECUTION CONTEXTS                                  │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                              │
│  Context         Can Sleep?    Preemptible?    Lock Types Allowed           │
│  ────────────────────────────────────────────────────────────────────────   │
│                                                                              │
│  Process         Yes           Yes             mutex, semaphore,             │
│  Context         (GFP_KERNEL)  (CONFIG_       spinlock, rwlock              │
│                                 PREEMPT)                                    │
│                                                                              │
│  Softirq/        No            No              spinlock (with               │
│  Tasklet                                       IRQ disabling if             │
│                                                sharing with hardirq)        │
│                                                                              │
│  Hardirq         No            No              spin_lock_irqsave            │
│                  (atomic)                      only                         │
│                                                                              │
│  NMI             No            No              raw_spinlock,                │
│                  (super                        trylock only                 │
│                   atomic)                                                    │
│                                                                              │
└─────────────────────────────────────────────────────────────────────────────┘

#include <linux/atomic.h>

// Basic atomic integer
atomic_t counter = ATOMIC_INIT(0);

// 64-bit atomic
atomic64_t big_counter = ATOMIC64_INIT(0);

// Atomic operations
atomic_read(&counter);           // Read value
atomic_set(&counter, 5);         // Set value
atomic_add(10, &counter);        // Add
atomic_sub(3, &counter);         // Subtract
atomic_inc(&counter);            // Increment
atomic_dec(&counter);            // Decrement

// Atomic read-modify-write
int old = atomic_fetch_add(5, &counter);  // Returns old value
int old = atomic_xchg(&counter, 10);       // Exchange

// Atomic test operations
atomic_dec_and_test(&counter);   // Returns true if result is 0
atomic_add_negative(n, &counter); // Returns true if result is negative

// Compare and swap
atomic_cmpxchg(&counter, old, new);  // If counter==old, set to new
atomic_try_cmpxchg(&counter, &old, new);  // Returns bool

// Good: Simple counter
static atomic_t connection_count = ATOMIC_INIT(0);

void on_connect(void) {
    atomic_inc(&connection_count);
}

void on_disconnect(void) {
    atomic_dec(&connection_count);
}

// Bad: Compound operation (not atomic!)
if (atomic_read(&counter) == 0) {  // RACE!
    atomic_inc(&counter);          // Another CPU could change it
}

// Good: Use atomic primitive
atomic_cmpxchg(&counter, 0, 1);  // Atomic "compare and set if zero"

#include <linux/spinlock.h>

// Static initialization
static DEFINE_SPINLOCK(my_lock);

// Dynamic initialization
spinlock_t my_lock;
spin_lock_init(&my_lock);

// Basic usage
spin_lock(&my_lock);
// ... critical section ...
spin_unlock(&my_lock);

// With trylock (non-blocking)
if (spin_trylock(&my_lock)) {
    // ... critical section ...
    spin_unlock(&my_lock);
} else {
    // Lock not available, handle gracefully
}

// Basic (use in process context when not sharing with interrupts)
spin_lock(&lock);
spin_unlock(&lock);

// Disable softirqs (use when sharing with softirq context)
spin_lock_bh(&lock);      // Disable bottom halves
spin_unlock_bh(&lock);    // Re-enable bottom halves

// Disable all interrupts (use when sharing with hardirq context)
unsigned long flags;
spin_lock_irqsave(&lock, flags);     // Save IRQ state, disable IRQs
// ... critical section ...
spin_unlock_irqrestore(&lock, flags); // Restore IRQ state

// Disable interrupts (unconditionally)
spin_lock_irq(&lock);     // Assumes IRQs were enabled
spin_unlock_irq(&lock);   // Re-enables IRQs

// Warning: Don't nest irq variants wrong!
spin_lock_irq(&lock1);
spin_lock_irq(&lock2);    // WRONG! First unlock will re-enable IRQs
spin_unlock_irq(&lock2);  // IRQs now enabled, but lock1 still held!
spin_unlock_irq(&lock1);

// Correct: Use irqsave for inner locks
spin_lock_irq(&lock1);
spin_lock(&lock2);        // IRQs already disabled
spin_unlock(&lock2);
spin_unlock_irq(&lock1);

┌─────────────────────────────────────────────────────────────────────────────┐
│                   WHICH SPINLOCK VARIANT TO USE?                             │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                              │
│  Q: Is the lock ever acquired in hardirq context?                           │
│  │                                                                           │
│  ├─ YES → Always use spin_lock_irqsave() / spin_unlock_irqrestore()         │
│  │        (Even from process context - must disable IRQs to prevent         │
│  │         deadlock if interrupt tries to acquire same lock)                │
│  │                                                                           │
│  └─ NO ──► Is the lock ever acquired in softirq/tasklet context?            │
│            │                                                                 │
│            ├─ YES → Use spin_lock_bh() / spin_unlock_bh() from process ctx  │
│            │        Use spin_lock() / spin_unlock() from softirq ctx        │
│            │                                                                 │
│            └─ NO ──► Use spin_lock() / spin_unlock()                        │
│                      (But consider if a mutex would be better)              │
│                                                                              │
│  DANGER: Never sleep while holding a spinlock!                               │
│  The CPU spins, so other CPUs waste time waiting.                           │
│                                                                              │
└─────────────────────────────────────────────────────────────────────────────┘

#include <linux/rwlock.h>

static DEFINE_RWLOCK(my_rwlock);

// Reader (shared access)
read_lock(&my_rwlock);
// ... read data ...
read_unlock(&my_rwlock);

// Writer (exclusive access)
write_lock(&my_rwlock);
// ... modify data ...
write_unlock(&my_rwlock);

// IRQ-safe variants
read_lock_irqsave(&my_rwlock, flags);
write_lock_irqsave(&my_rwlock, flags);

#include <linux/seqlock.h>

static DEFINE_SEQLOCK(my_seqlock);

// Writer (takes exclusive lock)
write_seqlock(&my_seqlock);
// ... modify data ...
write_sequnlock(&my_seqlock);

// Reader (lockless, may need to retry)
unsigned int seq;
do {
    seq = read_seqbegin(&my_seqlock);
    // ... read data into local variables ...
} while (read_seqretry(&my_seqlock, seq));

// If read_seqretry returns true, a write occurred during read
// and we must retry

#include <linux/mutex.h>

// Static initialization
static DEFINE_MUTEX(my_mutex);

// Dynamic initialization
struct mutex my_mutex;
mutex_init(&my_mutex);

// Basic usage
mutex_lock(&my_mutex);           // Sleep if locked
// ... critical section (can sleep here!) ...
mutex_unlock(&my_mutex);

// Interruptible (can be interrupted by signals)
if (mutex_lock_interruptible(&my_mutex)) {
    return -ERESTARTSYS;  // Signal received
}
// ... critical section ...
mutex_unlock(&my_mutex);

// Killable (only SIGKILL can interrupt)
if (mutex_lock_killable(&my_mutex)) {
    return -ERESTARTSYS;
}

// Trylock (non-blocking)
if (mutex_trylock(&my_mutex)) {
    // ... got the lock ...
    mutex_unlock(&my_mutex);
} else {
    // Lock not available
}

// WRONG: Recursive locking
mutex_lock(&my_mutex);
foo();  // foo() also calls mutex_lock(&my_mutex) → DEADLOCK!
mutex_unlock(&my_mutex);

// WRONG: Holding mutex in hardirq
irqreturn_t my_irq_handler(int irq, void *dev_id) {
    mutex_lock(&my_mutex);  // BUG: Cannot sleep in IRQ context!
    // ...
}

#include <linux/semaphore.h>

// Initialize with count
static DEFINE_SEMAPHORE(my_sem, 3);  // Allow 3 concurrent accessors

struct semaphore my_sem;
sema_init(&my_sem, 3);

// Acquire (decrement)
down(&my_sem);              // Sleep if count is 0
down_interruptible(&my_sem); // Can be interrupted
down_trylock(&my_sem);      // Non-blocking

// Release (increment)
up(&my_sem);

┌─────────────────────────────────────────────────────────────────────────────┐
│                        RCU MECHANISM                                         │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                              │
│  Traditional Locking:                                                        │
│  ───────────────────                                                        │
│  Reader 1: [====lock====][read][====unlock====]                             │
│  Reader 2:                    [wait...][====lock====][read][unlock]         │
│  Writer:   [wait..................][lock][write][unlock]                    │
│                                                                              │
│  RCU:                                                                        │
│  ─────                                                                       │
│  Reader 1: [rcu_read_lock][read old data][rcu_read_unlock]                  │
│  Reader 2:     [rcu_read_lock][read][rcu_read_unlock]                       │
│  Writer:   [copy][update copy][publish ptr][wait for readers][free old]    │
│            │                  │            │                                 │
│            │                  │            └─ synchronize_rcu()             │
│            │                  └─ rcu_assign_pointer()                       │
│            └─ kmalloc + copy data                                           │
│                                                                              │
│  Key Insight:                                                                │
│  • Readers never wait                                                       │
│  • Writers copy, update pointer atomically, wait, then free old            │
│  • "Grace period" = time for all pre-existing readers to finish            │
│                                                                              │
└─────────────────────────────────────────────────────────────────────────────┘

#include <linux/rcupdate.h>

// Reader-side
rcu_read_lock();
struct my_data *ptr = rcu_dereference(global_ptr);
// ... use ptr (do not dereference after rcu_read_unlock) ...
rcu_read_unlock();

// Writer-side (update)
struct my_data *new = kmalloc(sizeof(*new), GFP_KERNEL);
*new = *old;                    // Copy old data
new->field = new_value;         // Modify
rcu_assign_pointer(global_ptr, new);  // Atomic publish
synchronize_rcu();              // Wait for readers
kfree(old);                     // Safe to free now

// Asynchronous free (don't wait)
call_rcu(&old->rcu_head, my_free_callback);

#include <linux/rculist.h>

struct my_entry {
    int data;
    struct list_head list;
    struct rcu_head rcu;  // For call_rcu
};

static LIST_HEAD(my_list);
static DEFINE_SPINLOCK(list_lock);  // Protects writers

// Reader (lockless)
void read_list(void)
{
    struct my_entry *entry;
    
    rcu_read_lock();
    list_for_each_entry_rcu(entry, &my_list, list) {
        process(entry->data);
    }
    rcu_read_unlock();
}

// Writer (needs lock for mutual exclusion with other writers)
void add_entry(int data)
{
    struct my_entry *new = kmalloc(sizeof(*new), GFP_KERNEL);
    new->data = data;
    
    spin_lock(&list_lock);
    list_add_rcu(&new->list, &my_list);
    spin_unlock(&list_lock);
}

// Delete with RCU
static void entry_free_rcu(struct rcu_head *head)
{
    struct my_entry *entry = container_of(head, struct my_entry, rcu);
    kfree(entry);
}

void remove_entry(struct my_entry *entry)
{
    spin_lock(&list_lock);
    list_del_rcu(&entry->list);
    spin_unlock(&list_lock);
    
    call_rcu(&entry->rcu, entry_free_rcu);  // Free after grace period
}

// Without barriers, this might be reordered!
int ready = 0;
int data = 0;

// CPU 1 (writer)
data = 42;          // Might execute after ready=1!
ready = 1;

// CPU 2 (reader)
while (!ready);     // Might read ready=1 but...
print(data);        // ...data still shows 0!

// With barriers
// CPU 1 (writer)
data = 42;
smp_wmb();          // Write barrier: data visible before ready
ready = 1;

// CPU 2 (reader)
while (!ready);
smp_rmb();          // Read barrier: read data after ready
print(data);        // Now guaranteed to see 42

#include <linux/barrier.h>

// Full memory barrier (both reads and writes)
mb();           // Barrier for all memory types
smp_mb();       // Only needed on SMP systems

// Write barrier (writes before cannot pass writes after)
wmb();
smp_wmb();

// Read barrier (reads before cannot pass reads after)
rmb();
smp_rmb();

// Acquire/Release semantics (lighter than full barriers)
smp_load_acquire(&variable);   // All reads after this see writes before corresponding release
smp_store_release(&variable, value);  // All writes before this visible to loads after acquire

// Compiler-only barrier (doesn't affect CPU)
barrier();      // Prevents compiler reordering
READ_ONCE(x);   // Prevent compiler from caching/reordering read
WRITE_ONCE(x, val);  // Prevent compiler from tearing/reordering write

// Pattern 1: Flag-guarded data
struct {
    int data;
    int ready;  // Flag
} shared;

// Writer
WRITE_ONCE(shared.data, 42);
smp_wmb();                      // Ensure data written before ready
WRITE_ONCE(shared.ready, 1);

// Reader
while (!READ_ONCE(shared.ready))
    cpu_relax();
smp_rmb();                      // Ensure ready read before data
int value = READ_ONCE(shared.data);

// Pattern 2: Ring buffer
// Producer
buffer[head] = item;
smp_wmb();                      // Item visible before head update
WRITE_ONCE(head, next_head);

// Consumer
while (READ_ONCE(head) == tail)
    cpu_relax();
smp_rmb();                      // Head visible before reading item
item = buffer[tail];

#include <linux/percpu.h>

// Static per-CPU variable
static DEFINE_PER_CPU(int, my_counter);

// Dynamic allocation
int __percpu *my_ptr;
my_ptr = alloc_percpu(int);

// Access (must disable preemption!)
void increment_counter(void)
{
    preempt_disable();           // Or get_cpu()
    this_cpu_inc(my_counter);    // Increment this CPU's copy
    preempt_enable();            // Or put_cpu()
}

// Alternative: get_cpu() returns CPU number and disables preemption
void access_percpu(void)
{
    int cpu = get_cpu();
    int *ptr = per_cpu_ptr(&my_counter, cpu);
    (*ptr)++;
    put_cpu();
}

// Read all CPUs (for statistics)
int total = 0;
int cpu;
for_each_possible_cpu(cpu) {
    total += per_cpu(my_counter, cpu);
}

// Atomic per-CPU operations (no preemption disable needed)
this_cpu_add(my_counter, 5);
this_cpu_read(my_counter);
this_cpu_write(my_counter, 0);

┌─────────────────────────────────────────────────────────────────────────────┐
│                       DEADLOCK PREVENTION                                    │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                              │
│  Classic Deadlock:                                                           │
│  ─────────────────                                                          │
│  CPU 0:                      CPU 1:                                         │
│  lock(A)                     lock(B)                                        │
│  lock(B)  ← waits for B      lock(A)  ← waits for A                        │
│  ...                         ...                                            │
│  unlock(B)                   unlock(A)                                      │
│  unlock(A)                   unlock(B)                                      │
│                                                                              │
│  Both CPUs wait forever!                                                     │
│                                                                              │
│  Prevention: Consistent Lock Ordering                                        │
│  ─────────────────────────────────────                                      │
│  Rule: Always acquire locks in the same order                               │
│                                                                              │
│  CPU 0:                      CPU 1:                                         │
│  lock(A)                     lock(A)  ← waits for A                        │
│  lock(B)                     ...      ← eventually gets A                   │
│  ...                         lock(B)                                        │
│  unlock(B)                   ...                                            │
│  unlock(A)                   unlock(B)                                      │
│                              unlock(A)                                      │
│                                                                              │
│  Document your lock ordering!                                                │
│  Example: i_mutex → dentry->d_lock → dcache_lock                           │
│                                                                              │
└─────────────────────────────────────────────────────────────────────────────┘

# Enable in kernel config
CONFIG_PROVE_LOCKING=y
CONFIG_DEBUG_LOCK_ALLOC=y
CONFIG_LOCK_STAT=y

# Check lockdep warnings in dmesg
dmesg | grep -i "lockdep\|deadlock\|held lock"

=============================================
WARNING: possible recursive locking detected
---------------------------------------------
kworker/0:1/1234 is trying to acquire lock:
 (&my_lock){+.+.}, at: my_function+0x20/0x100

but task is already holding lock:
 (&my_lock){+.+.}, at: my_function+0x10/0x100

other info that might help us debug this:
 Possible unsafe locking scenario:

       CPU0
       ----
  lock(&my_lock);
  lock(&my_lock);   <-- Recursive!

 *** DEADLOCK ***

// Annotate lock ordering for lockdep
static DEFINE_MUTEX(outer_lock);
static DEFINE_MUTEX(inner_lock);

void my_function(void)
{
    mutex_lock(&outer_lock);
    mutex_lock_nested(&inner_lock, SINGLE_DEPTH_NESTING);  // Tell lockdep this is intentional
    // ...
    mutex_unlock(&inner_lock);
    mutex_unlock(&outer_lock);
}

// Lock class annotation (for locks that seem same but aren't)
static struct lock_class_key my_lock_key;
__mutex_init(&my_lock, "my_lock", &my_lock_key);

# Enable lock statistics
echo 1 > /proc/sys/kernel/lock_stat

# View lock contention
cat /proc/lock_stat

# Sample output:
# class name                 con-bounces    contentions   waittime-min   ...
# &mm->mmap_lock-W:            123456         12345          0.50
# &inode->i_lock:               98765          9876          0.10

#include <linux/spinlock.h>
#include <linux/rcupdate.h>
#include <linux/slab.h>

struct my_data {
    int value;
    struct rcu_head rcu;
};

struct my_container {
    struct my_data __rcu *current;  // RCU-protected pointer
    spinlock_t update_lock;          // Writer mutual exclusion
};

// Initialize
void my_container_init(struct my_container *c)
{
    struct my_data *data = kzalloc(sizeof(*data), GFP_KERNEL);
    spin_lock_init(&c->update_lock);
    rcu_assign_pointer(c->current, data);
}

// Read (lockless, can be called from any context including IRQ)
int my_container_read(struct my_container *c)
{
    int value;
    
    rcu_read_lock();
    struct my_data *data = rcu_dereference(c->current);
    value = data->value;
    rcu_read_unlock();
    
    return value;
}

// Update (process context only, might sleep)
void my_container_update(struct my_container *c, int new_value)
{
    struct my_data *old, *new;
    
    new = kmalloc(sizeof(*new), GFP_KERNEL);
    if (!new)
        return;
    
    spin_lock(&c->update_lock);
    
    old = rcu_dereference_protected(c->current, 
                                    lockdep_is_held(&c->update_lock));
    new->value = new_value;
    rcu_assign_pointer(c->current, new);
    
    spin_unlock(&c->update_lock);
    
    synchronize_rcu();  // Wait for readers
    kfree(old);
}