第六章：位运算与原子操作

涉及内核源码： , ,

一

林小源在黑暗中走了很远。

五种根基已经刻入他的意识深处——指针让他能追踪数据的流向，结构体让他看清了进程的骨架，编译器让他读懂了源码到机器码的翻译，寄存器让他触摸到了 CPU 的脉搏，汇编让他听懂了硬件的低语。

他以为自己已经理解了内核的基本运作方式。

然后他看到了两个影子。

那两个影子几乎完全相同——同样的寄存器，同样的指令流水线，同样的执行单元。它们并排站在黑暗中，各自独立地运转着，像两颗心脏在同一个身体里跳动。

"那是两个 CPU 核心。"一个声音从远处传来，苍老而平稳，像石磨转动时的低吟。林小源循声望去，看到一块巨大的位图悬浮在虚空中——数万个比特整整齐齐地排列着，每一个都在微微发光，有的亮，有的暗。

"我是位图。"那声音说，"页分配器用我追踪哪些物理页已分配，inode 位图用我追踪哪些 inode 已使用。我管理着内核中最基本的资源——每一个比特都是一块领地，置位意味着'已占用'，清零意味着'空闲'。"

林小源走近了。他伸出意识的触角，试探着触碰其中一个比特。

"别乱碰。"位图的声音突然严厉起来，"你看到了那两个核心吗？它们同时在运行。它们同时在修改我。你以为只是'读取、加一、写回'三步操作，但两个核心同时执行这三步——最终的结果可能少计了一次。"

林小源缩回了手。他盯着那两个影子，看到它们各自的执行流几乎在同一瞬间伸向同一个比特，像两只手同时去拿同一枚棋子。

"代码的正确性，"位图缓缓说道，"不仅取决于你写了什么，还取决于别人在同时做什么。这就是并发的世界。"

二

位图带着林小源来到一片更小的世界。

这里没有字节，没有字——只有比特。每一个比特都像一扇门，要么开，要么关，没有中间状态。空气中弥漫着一种精确到极致的气息，仿佛任何偏差都会导致整个世界的崩塌。

"位运算是一切的基础。"位图说，"在一个比特的世界里，置位、清位、测试——每一个操作都必须精确到不可分割。"

林小源看到了三种基本操作的演示：AND 如同两扇门同时开才能通过，OR 如同任意一扇门开就能通过，XOR 如同两扇门状态不同时才能通过。移位操作让比特在位置之间跳跃，像棋子在棋盘上滑行。

"常用技巧，"位图继续说，"设置第 n 位用 flags |= (1U << n)，清除用 flags &= ~(1U << n)，切换用 flags ^= (1U << n)，测试用 flags & (1U << n)。这些是内核位操作的四字真言。"

"那内核里真正的位操作函数呢？"林小源问。

位图沉默了一瞬，然后说："真实的内核位操作函数——、、——在单核上就是普通的位运算。但在多核上，它们必须是原子的。RISC-V 架构会用 AMO（原子内存操作）指令来保证这一点。还有 、、popcount——页分配器用它们在位图中快速找到空闲的物理页。"

林小源看着那些函数的实现，突然明白了：位图不只是数据结构，它是内核管理资源的地图。每一个比特都是一块领地，每一次置位都是一次占领，每一次清零都是一次释放。

三

"但是，"林小源皱起了眉头，"如果两个核心同时对同一个比特执行 ，会发生什么？"

位图没有回答。取而代之的，是一个新的存在从黑暗中浮现——一个通体银白的圆环，表面光滑得像镜子，没有任何缝隙。

"我是 。"圆环发出的声音极其冷静，像金属碰撞时的清响，"不可分割，不可中断。我的每一个操作都在一个时钟周期内完成——、、、——没有任何力量能在我执行的过程中插入干扰。"

林小源绕着圆环走了一圈。他注意到圆环的表面刻着一行小字：。

"你的本质就是一个计数器？"

"计数器是最简单的原子类型。"atomic_t 的声音没有丝毫波动，"但简单不等于不重要。内核用我管理引用计数——当一个对象的引用计数降到零，它就会被释放。、文件描述符引用、网络包计数——到处都有我的身影。"

"那 呢？"

"减一，然后测试是否为零。如果为零，返回真。这是引用计数的核心操作——'最后一个使用者释放资源'。整个内核的生命周期管理都建立在这个操作之上。"

林小源还想问什么，但 atomic_t 已经转向了另一个方向。

"你需要认识一位更重要的存在。"它说。

四

黑暗中传来一声沉重的金属撞击声。

一个巨大的齿轮从虚空中降下，缓慢而庄严。齿轮的表面刻满了复杂的纹路，每一条纹路都像一道锁链，将齿轮的各个部分紧紧束缚在一起。

"我是自旋锁。"齿轮的声音低沉而威严，像远古的钟声，"我是互斥的基石。当一个执行流进入我的临界区，其他所有执行流都必须在外等待——它们不能睡眠，不能让出 CPU，只能不停地旋转，直到我释放。"

林小源感到了一种压迫感。齿轮的旋转带着一种不可抗拒的力量，仿佛任何试图在它转动时插入的操作都会被碾碎。

"你的规则是什么？"林小源问。

"四条铁律。"齿轮的声音变得严厉起来，"第一，持锁时不能睡眠。一旦你在持有自旋锁时调用了可能睡眠的函数——比如 kmalloc(GFP_KERNEL)——整个系统就可能死锁。这不是理论上的风险，而是每一个内核开发者都会犯的真实错误。"

"第二，持锁时不能调用可能睡眠的函数。这和第一条本质相同，但值得单独强调——因为很多看似无害的函数实际上可能睡眠。"

"第三，中断中必须用 。如果一个中断在你持有锁的时候到来，而中断处理函数又试图获取同一把锁——死锁。"

"第四，临界区要尽可能短。自旋锁的本质是忙等待——其他核心在空转。临界区越长，浪费的 CPU 时间越多。"

林小源默默记住了这四条规则。他看着齿轮缓慢旋转的身躯，突然注意到了一个细节：齿轮的表面有一个小小的凹槽，旁边写着 。

"那是什么？"

"尝试获取锁。"齿轮说，"如果锁空闲，获取成功，返回真；如果锁已被别人持有，立即返回假，不等待。这在某些场景下很有用——比如中断处理函数中，你不想自旋等待，而是想快速判断能否获取锁。"

五

林小源正在消化自旋锁的知识，突然感到脚下的地面在微微震动。

他低头一看，发现自己站在一个巨大的棋盘上。棋盘的每一格都对应一个比特，而棋盘的中央，有两颗棋子正在激烈地交锋——一颗代表 ，另一颗代表 。

"原子位操作。"位图的声音从远处传来，"它们和普通的位操作不同——它们在一个不可分割的操作中同时完成'测试'和'修改'。你先查看某个比特的状态，然后根据结果设置或清除它——整个过程是原子的，没有任何力量能插入其中。"

林小源看着那两颗棋子的动作。 在触碰一个比特的瞬间，先读取它的旧值，然后将它置位——两步合并为一步。 则相反，先读取旧值，然后清零。

"这有什么用？"林小源问。

"信号处理中的 位图。"位图说，"设备中断的状态寄存器。调度器中的进程状态标志。每当你需要'检查并修改'一个比特时，都需要原子位操作——因为检查和修改之间不能被其他核心打断。"

林小源站在棋盘中央，看着那些比特在两个核心的争夺下闪烁不定。他第一次真正理解了并发的可怕——不是技术上的复杂，而是那种'你以为安全的东西其实随时可能崩溃'的不安。

"记住，"atomic_t 的声音从远处传来，冷静而坚定，"在并发的世界里，只有原子操作才是安全的。其他一切都是幻觉。"

/* 打印二进制表示 */
static void print_bin(const char *label, uint32_t val) {
    printf("%s: 0x%08x = ", label, val);
    for (int i = 31; i >= 0; i--) {
        printf("%d", (val >> i) & 1);
        if (i % 8 == 0 && i > 0) printf("_");
    }
    printf("\n");
}

printf("=== 位运算 ===\n\n");

uint32_t a = 0xCA0000F0U;
uint32_t b = 0xAAFF000FU;

print_bin("a", a);
print_bin("b", b);
printf("\n");

print_bin("a & b  (AND)", a & b);
print_bin("a | b  (OR)",  a | b);
print_bin("a ^ b  (XOR)", a ^ b);
print_bin("~a     (NOT)", ~a);
printf("\n");

/* 移位 */
uint32_t val = 1;
print_bin("1 << 0", val << 0);
print_bin("1 << 4", val << 4);
print_bin("1 << 31", val << 31);
printf("\n");

/* 常用技巧 */
printf("常用位运算技巧:\n\n");

/* 设置第 n 位 */
uint32_t flags = 0;
int n = 5;
flags |= (1U << n);
printf("设置第 %d 位: ", n);
print_bin("flags", flags);

/* 清除第 n 位 */
flags &= ~(1U << n);
printf("清除第 %d 位: ", n);
print_bin("flags", flags);

/* 切换第 n 位 */
flags ^= (1U << n);
printf("切换第 %d 位: ", n);
print_bin("flags", flags);

/* 测试第 n 位 */
flags = 0xAAU;
printf("\n测试第 1 位: %s\n", (flags & (1U << 1)) ? "置位" : "未置位");
printf("测试第 2 位: %s\n", (flags & (1U << 2)) ? "置位" : "未置位");

/* 模拟内核的位操作函数。真实内核会按架构展开为 RISC-V AMO 或普通位操作。 */

/* set_bit: 原子地设置第 nr 位 */
static inline void set_bit(int nr, volatile unsigned long *addr) {
    *addr |= (1UL << nr);
}

/* clear_bit: 原子地清除第 nr 位 */
static inline void clear_bit(int nr, volatile unsigned long *addr) {
    *addr &= ~(1UL << nr);
}

/* test_bit: 测试第 nr 位 */
static inline int test_bit(int nr, const volatile unsigned long *addr) {
    return !!(*addr & (1UL << nr));
}

/* find_first_bit: 找到第一个置位的位 */
static int find_first_set(unsigned long val) {
    if (val == 0) return -1;
    return __builtin_ctzl(val);
}

/* find_last_bit: 找到最后一个置位的位 */
static int find_last_set(unsigned long val) {
    if (val == 0) return -1;
    return (int)(8 * sizeof(unsigned long) - 1 - __builtin_clzl(val));
}

/* popcount: 计算置位个数 */
static int popcount(unsigned long val) {
    return __builtin_popcountl(val);
}

printf("=== 内核位操作 ===\n\n");

unsigned long bitmap = 0;

/* 设置一些位 */
set_bit(0, &bitmap);
set_bit(3, &bitmap);
set_bit(7, &bitmap);
set_bit(15, &bitmap);
printf("设置 0,3,7,15: 0x%lx\n", bitmap);

/* 测试位 */
printf("位 3: %s\n", test_bit(3, &bitmap) ? "置位" : "未置位");
printf("位 4: %s\n", test_bit(4, &bitmap) ? "置位" : "未置位");

/* 查找 */
printf("\nfind_first_set: %d\n", find_first_set(bitmap));
printf("find_last_set:  %d\n", find_last_set(bitmap));
printf("popcount:       %d\n", popcount(bitmap));

/* 清除 */
clear_bit(3, &bitmap);
printf("\n清除位 3: 0x%lx\n", bitmap);
printf("位 3: %s\n", test_bit(3, &bitmap) ? "置位" : "未置位");

printf("\n内核中的应用场景:\n");
printf("  - 页分配器: bitmap 追踪哪些页已分配\n");
printf("  - inode 位图: 追踪哪些 inode 已使用\n");
printf("  - 中断描述符: 标志位控制\n");

/*
 * 模拟内核的 atomic_t
 * 真实内核用汇编实现，这里用 C11 atomic 展示概念
 */

typedef struct { atomic_int counter; } atomic_t;

static inline void atomic_set(atomic_t *v, int i) {
    atomic_store(&v->counter, i);
}

static inline int atomic_read(const atomic_t *v) {
    return atomic_load(&v->counter);
}

static inline void atomic_add(atomic_t *v, int i) {
    atomic_fetch_add(&v->counter, i);
}

static inline void atomic_sub(atomic_t *v, int i) {
    atomic_fetch_sub(&v->counter, i);
}

static inline void atomic_inc(atomic_t *v) {
    atomic_fetch_add(&v->counter, 1);
}

static inline void atomic_dec(atomic_t *v) {
    atomic_fetch_sub(&v->counter, 1);
}

static inline int atomic_sub_and_test(atomic_t *v, int i) {
    return atomic_fetch_sub(&v->counter, i) == i;
}

static inline int atomic_inc_and_test(atomic_t *v) {
    return atomic_fetch_add(&v->counter, 1) == -1;
}

static inline int atomic_dec_and_test(atomic_t *v) {
    return atomic_fetch_sub(&v->counter, 1) == 1;
}

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

printf("=== atomic_t 原子类型 ===\n\n");

atomic_t refcnt;

/* 模拟引用计数 */
atomic_set(&refcnt, 1);
printf("初始引用计数: %d\n", atomic_read(&refcnt));

atomic_inc(&refcnt);
atomic_inc(&refcnt);
printf("增加两次: %d\n", atomic_read(&refcnt));

atomic_dec(&refcnt);
printf("减少一次: %d\n", atomic_read(&refcnt));

/* dec_and_test: 减到 0 时返回真 */
atomic_dec(&refcnt);
printf("再减一次: %d\n", atomic_read(&refcnt));
int is_zero = atomic_dec_and_test(&refcnt);
printf("dec_and_test: %s (计数: %d)\n",
       is_zero ? "到达零" : "未到零", atomic_read(&refcnt));

printf("\n内核中的应用场景:\n");
printf("  - 引用计数: kref, 文件描述符引用\n");
printf("  - 统计计数: 网络包计数、页错误计数\n");
printf("  - 状态标志: 原子地设置/清除标志\n");

/*
 * 模拟内核自旋锁
 * 真实内核用 ticket spinlock 或 qspinlock
 */

typedef atomic_int spinlock_t;

#define SPIN_LOCK_UNLOCKED 0
#define DEFINE_SPINLOCK(name) spinlock_t name = SPIN_LOCK_UNLOCKED

static inline void cpu_relax(void) {
#if defined(__riscv)
    asm volatile("fence rw, rw" ::: "memory");
#else
    __sync_synchronize();
#endif
}

static inline void spin_lock(spinlock_t *lock) {
    while (atomic_exchange(lock, 1) != 0) {
        /* 自旋等待 */
        cpu_relax();
    }
}

static inline void spin_unlock(spinlock_t *lock) {
    atomic_store(lock, 0);
}

static inline int spin_trylock(spinlock_t *lock) {
    int old = 0;
    return atomic_compare_exchange_strong(lock, &old, 1);
}

static inline int spin_is_locked(spinlock_t *lock) {
    return atomic_load(lock);
}

/* 模拟临界区操作 */
static int shared_counter = 0;

static void unsafe_increment(int times) {
    for (int i = 0; i < times; i++) {
        shared_counter++;  /* 非原子! */
    }
}

static void safe_increment(spinlock_t *lock, int times) {
    for (int i = 0; i < times; i++) {
        spin_lock(lock);
        shared_counter++;
        spin_unlock(lock);
    }
}

printf("=== 自旋锁 ===\n\n");

/* 不加锁的问题 */
shared_counter = 0;
unsafe_increment(1000000);
printf("不加锁: counter = %d (单线程正确，多线程会丢失)\n\n",
       shared_counter);

/* 加锁 */
DEFINE_SPINLOCK(my_lock);
shared_counter = 0;
safe_increment(&my_lock, 1000000);
printf("加锁:   counter = %d\n\n", shared_counter);

/* trylock */
DEFINE_SPINLOCK(try_lock);
int got = spin_trylock(&try_lock);
printf("trylock 第一次: %s\n", got ? "成功" : "失败");
got = spin_trylock(&try_lock);
printf("trylock 第二次: %s (锁已被持有)\n", got ? "成功" : "失败");
spin_unlock(&try_lock);
got = spin_trylock(&try_lock);
printf("trylock 第三次: %s (锁已释放)\n", got ? "成功" : "失败");

printf("\n内核自旋锁规则:\n");
printf("  1. 持锁时不能睡眠!\n");
printf("  2. 持锁时不能调用可能睡眠的函数\n");
printf("  3. 中断中必须用 spin_lock_irqsave()\n");
printf("  4. 临界区要尽可能短\n");

是自旋锁的关键优化点。不同架构会把它展开成合适的等待提示或轻量屏障；在 RISC-V 上可以使用 扩展提示，也可以用 维持等待循环中的顺序约束。

/* 原子 test_and_clear_bit: 测试并清除第 n 位 */
static inline int test_and_clear_bit(int nr, atomic_ulong *addr) {
    unsigned long mask = 1UL << nr;
    unsigned long old = atomic_fetch_and(addr, ~mask);
    return !!(old & mask);
}

/* 原子 test_and_set_bit: 测试并设置第 n 位 */
static inline int test_and_set_bit(int nr, atomic_ulong *addr) {
    unsigned long mask = 1UL << nr;
    unsigned long old = atomic_fetch_or(addr, mask);
    return !!(old & mask);
}

printf("=== 原子位测试操作 ===\n\n");

atomic_ulong flags = ATOMIC_VAR_INIT(0xFFUL);  /* 低 8 位置位 */

printf("初始: 0x%lx\n", atomic_load(&flags));

/* 测试并清除位 3 */
int was_set = test_and_clear_bit(3, &flags);
printf("test_and_clear_bit(3): 之前 %s, 现在 0x%lx\n",
       was_set ? "置位" : "未置位", atomic_load(&flags));

/* 再次清除位 3 */
was_set = test_and_clear_bit(3, &flags);
printf("test_and_clear_bit(3): 之前 %s, 现在 0x%lx\n",
       was_set ? "置位" : "未置位", atomic_load(&flags));

/* 测试并设置位 3 */
was_set = test_and_set_bit(3, &flags);
printf("test_and_set_bit(3):   之前 %s, 现在 0x%lx\n",
       was_set ? "置位" : "未置位", atomic_load(&flags));

printf("\n应用场景:\n");
printf("  - 信号处理: sigpending 位图\n");
printf("  - 设备中断: 中断状态寄存器\n");
printf("  - 调度器: 进程状态标志\n");

---

道藏笔记

内核启示

原子操作是并发安全的基石。 用于简单的计数器，自旋锁用于保护临界区，位操作用于管理位图。

在内核中选择同步原语的准则是：

• 只需要原子计数 →
• 临界区很短且不会睡眠 →
• 临界区可能睡眠 →
• 读多写少 → 或 RCU

自旋锁的那条铁律——"持锁时不能睡眠"——是内核开发者最常违反、也最致命的规则。一旦在持有自旋锁时调用了可能睡眠的函数（比如 kmalloc(GFP_KERNEL)），整个系统就可能死锁。这不是理论上的风险，而是每一个内核开发者都会犯的真实错误。

而位操作在内核中的应用远比你想象的广泛。页分配器用位图追踪哪些物理页已分配，inode 位图追踪哪些 inode 已使用，中断描述符表用标志位控制每个中断的行为。甚至进程的状态标志——、——也是用位来表示的。

当你在内核中看到 、、 时，你就知道：有人在管理一块位图。而那块位图，往往控制着系统中最关键的资源。

---

破关试炼

原子操作试炼

临界区很短且持锁时不能睡眠时，内核通常使用哪类锁？

答对后才能继续滑动和进入下一章。

← 上一回下一回 →