第10章：内核同步机制

typedef struct {
    int counter;
} atomic_t;

typedef struct {
    long counter;
} atomic64_t;

static inline void atomic_add(int i, atomic_t *v)
{
    asm volatile(LOCK_PREFIX "addl %1,%0"
                 : "+m" (v->counter)
                 : "ir" (i));
}

static inline int atomic_cmpxchg(atomic_t *v, int old, int new)
{
    return cmpxchg(&v->counter, old, new);
}

set_bit(nr, addr)       // 原子设置第nr位
clear_bit(nr, addr)     // 原子清除第nr位
test_bit(nr, addr)      // 测试第nr位
test_and_set_bit(nr, addr)  // 测试并设置

barrier()  // 阻止编译器重排序

mb()    // 全屏障：读写都不能跨越
rmb()   // 读屏障：读操作不能跨越
wmb()   // 写屏障：写操作不能跨越
smp_mb()   // SMP系统的全屏障
smp_rmb()  // SMP系统的读屏障
smp_wmb()  // SMP系统的写屏障

read_barrier_depends()  // Alpha架构特有
smp_read_barrier_depends()

// 生产者-消费者模式
// 生产者：
data = value;
smp_wmb();  // 确保data写入在flag之前
flag = 1;

// 消费者：
while (!flag)
    cpu_relax();
smp_rmb();  // 确保读data在读flag之后
use(data);

typedef struct {
    arch_spinlock_t raw_lock;
} spinlock_t;

spin_lock(&lock);
// 临界区
spin_unlock(&lock);

// 禁用中断的版本
spin_lock_irqsave(&lock, flags);
// 临界区
spin_unlock_irqrestore(&lock, flags);

while (test_and_set(&lock))
    cpu_relax();

typedef struct {
    union {
        u32 head_tail;
        struct {
            u16 head;
            u16 tail;
        };
    };
} arch_spinlock_t;

struct mcs_spinlock {
    struct mcs_spinlock *next;
    int locked;
};

rwlock_t lock;

// 读者
read_lock(&lock);
// 读临界区
read_unlock(&lock);

// 写者
write_lock(&lock);
// 写临界区
write_unlock(&lock);

typedef struct {
    struct seqcount seqcount;
    spinlock_t lock;
} seqlock_t;

// 写者
write_seqlock(&sl);
// 更新数据
write_sequnlock(&sl);

// 读者
unsigned seq;
do {
    seq = read_seqbegin(&sl);
    // 读取数据
} while (read_seqretry(&sl, seq));

struct mutex {
    atomic_long_t owner;
    spinlock_t wait_lock;
    struct list_head wait_list;
};

mutex_lock(&mutex);
// 临界区，可以睡眠
mutex_unlock(&mutex);

// MCS锁风格的等待队列
struct mutex_waiter {
    struct list_head list;
    struct task_struct *task;
};

// 乐观自旋
if (mutex_can_spin_on_owner(lock))
    mutex_optimistic_spin(lock);

struct semaphore {
    raw_spinlock_t lock;
    unsigned int count;
    struct list_head wait_list;
};

// 二值信号量（类似互斥量）
down(&sem);      // P操作，可能睡眠
up(&sem);        // V操作

// 计数信号量
sema_init(&sem, count);  // 初始化为count

struct completion {
    unsigned int done;
    wait_queue_head_t wait;
};

// 等待方
wait_for_completion(&comp);

// 通知方
complete(&comp);
complete_all(&comp);  // 唤醒所有等待者

// 读者
rcu_read_lock();
ptr = rcu_dereference(gptr);
// 使用ptr，不能睡眠
rcu_read_unlock();

// 写者
old_ptr = gptr;
new_ptr = kmalloc(...);
*new_ptr = *old_ptr;
// 修改new_ptr
rcu_assign_pointer(gptr, new_ptr);
synchronize_rcu();  // 等待所有读者完成
kfree(old_ptr);

     CPU0        CPU1        CPU2
      |           |           |
   rcu_read_lock  |           |
      |        rcu_read_lock  |
      |           |      synchronize_rcu()

      |           |      synchronize_rcu()
      |           |           |
   rcu_read_unlock|           |
      |---------- GP ---------|
      |        rcu_read_unlock|
      |           |           |
      |           |      (GP结束)

struct rcu_head {
    struct rcu_head *next;
    void (*func)(struct rcu_head *head);
};

call_rcu(&obj->rcu_head, free_func);

struct rcu_data {
    struct rcu_head *nxtlist;     // 新回调
    struct rcu_head *curlist;     // 当前批次
    struct rcu_head *donelist;    // 完成批次
};

CONFIG_RCU_TRACE         // RCU跟踪
CONFIG_RCU_CPU_STALL_DETECTOR  // 停滞检测
CONFIG_PROVE_RCU         // 运行时验证

// 调试接口
rcu_dereference_check()  // 带检查的解引用
rcu_access_pointer()     // 只访问指针值

struct lockdep_map {
    struct lock_class_key *key;
    struct lock_class *class_cache;
    const char *name;
};

// 锁类定义
static struct lock_class_key key;
spin_lock_init_key(&lock, &key);

     A -----> B
     ^         |
     |         v
     D <----- C

// 检测到循环：死锁！

// 自旋锁检查
CONFIG_DEBUG_SPINLOCK

- 检测未初始化的锁
- 检测重复解锁
- 检测错误的CPU

// 互斥量检查
CONFIG_DEBUG_MUTEXES

- 检测API误用
- 检测优先级反转

// 原子睡眠检查
CONFIG_DEBUG_ATOMIC_SLEEP

- 检测原子上下文中的睡眠

struct foo {
    spinlock_t lock;
    struct list_head list;
    int counter;
};

void process_foo(struct foo *f)
{
    spin_lock(&f->lock);
    if (f->counter > 0) {
        spin_unlock(&f->lock);
        schedule();  // 让出CPU
        spin_lock(&f->lock);
        f->counter--;
        // 处理list
    }
    spin_unlock(&f->lock);
}

struct foo {
    struct rcu_head rcu;
    int data;
};

void reader(void)
{
    struct foo *p;
    int val;

    rcu_read_lock();
    p = rcu_dereference(global_foo);
    val = p->data;
    rcu_read_unlock();

    if (val > 100) {
        rcu_read_lock();
        p = rcu_dereference(global_foo);
        p->data = val + 1;  // 问题行
        rcu_read_unlock();
    }
}

// CPU 0              // CPU 1
spin_lock(&A);        spin_lock(&B);
spin_lock(&B);        spin_lock(&A);  // 死锁！

spin_lock(&lock);
// 中断发生
  -> interrupt_handler()
     spin_lock(&lock);  // 死锁！

低优先级任务持有锁 -> 高优先级任务等待 -> 中优先级任务抢占低优先级

rcu_read_lock();
p = rcu_dereference(gp);
rcu_read_unlock();
use(p);  // 错误！p可能已被释放

rcu_read_lock();
p = rcu_dereference(gp);
atomic_inc(&p->refcount);  // 危险！p可能正在释放
rcu_read_unlock();

rcu_read_lock();
kmalloc(GFP_KERNEL);  // 错误！可能睡眠
rcu_read_unlock();

while (!flag);  // 编译器可能优化为 if(!flag) while(1);
data = shared;

p = READ_ONCE(gp);
if (p)
    val = p->data;  // ARM/Alpha可能乱序

for (i = 0; i < 1000; i++) {
    spin_lock(&lock);
    do_something_tiny();
    spin_unlock(&lock);
}

read_lock(&rwlock);
lengthy_computation();  // 阻塞所有写者
read_unlock(&rwlock);

struct percpu_counter {
    int cpu0_count;  // 同一缓存行
    int cpu1_count;  // 造成乒乓
} __attribute__((packed));

struct optimized {
    spinlock_t lock ____cacheline_aligned;
    int shared_data;
} ____cacheline_aligned;