Linux 内核内存模型（LKMM）实用配方指南：用 litmus 测试驾驭消息传递、锁与屏障

Linux 内核内存模型LKMM实用配方指南用 litmus 测试驾驭消息传递、锁与屏障【免费下载链接】linuxLinux kernel source tree项目地址: https://gitcode.com/GitHub_Trending/li/linux导读本文以 tools/memory-model/Documentation/recipes.txt 为骨架结合 Linux 内核源码树中的 LKMMLinux Kernel Memory Consistency Model工具链与配套 litmus 测试系统讲解并发编程中最常遇到的排序ordering场景从单 CPU / 单变量的简单特例、锁同步的基本规则到消息传递MP、载入缓冲LB、释放-获取链Release-Acquire Chain、存储缓冲SB等经典模式最后给出可操作的经验法则。读完本文你将掌握如何读懂一个.litmus测试、如何用herd7/klitmus7验证排序假设、何时该用smp_store_release()/smp_load_acquire()而非裸读写以及为什么某些看起来显然正确的代码实际会出错。说明Documentation/dev-tools/lkmm/docs/recipes.rst是本文档在 Sphinx 文档体系中的壳文件通过kernel-include指令字面量引入 tools/memory-model/Documentation/recipes.txt因此本文以该 txt 全文为绝对主体展开。一、LKMM 与 recipes 的定位Linux 内核内存一致性模型LKMM位于 tools/memory-model 目录用 herd 的 cat 语言写成核心文件包括linux-kernel.bell对相关指令分类包括内存引用、内存屏障、原子读-改-写操作、锁的获取/释放以及 RCU 操作linux-kernel.cat规定哪些重排被禁止即定义模型允许的执行linux-kernel.def把类 C 语法映射到 herd7 内部指令集lock.cat锁获取/释放的前端分析linux-kernel.cfgherd7 常用参数集合。LKMM 通过外部工具herd7穷举探索小型 litmus 测试的状态空间与klitmus7把 litmus 测试转换成内核模块在真实硬件上运行来执行运行与安装要求详见 tools/memory-model/README要求 herdtools7 7.58 及以上版本klitmus7 与目标内核版本有兼容性对照表。本文件recipes.txt提供的就是配方为常见并发场景给出对应的 litmus 测试外加几个看似优雅实则坑人的反例。文中的示例代码多取自 v5.7 的 Linux 内核。全文分三大部分简单特例、摘掉训练轮的进阶示例、经验法则。所有配对的 litmus 测试文件都位于 tools/memory-model/litmus-tests每个文件头部都有Result: Never不可能或Result: Sometimes可能的预期结论可由 scripts/checkalllitmus.sh 等脚本批量核对。二、简单特例2.1 单 CPU 或单内存位置如果只有一个 CPU或者只有一个变量被访问代码会按序执行。但有四点需要小心C 语言的部分行为本身无序例如表达式f(x) g(y)中f与g的调用顺序未定义目标代码可以按任意顺序调用甚至可以交错计算。编译器可用 as-if 规则对普通访问编译器可以生成任意代码只要单线程执行的结果与完全遵守规则时看起来一致。想亲眼看效果可以用高优化级别编译后对生成二进制进行调试。只有一个变量但多 CPU 时该变量必须正确对齐且所有访问必须是全尺寸full sized。跨越 cacheline 或页边界、以及只读写变量一部分的欠尺寸访问都会让你的全排序保证失效。多 CPU 访问共享变量应使用READ_ONCE()/WRITE_ONCE()或更强的原语以阻止 load/store 撕裂tearing、load/store 融合fusing以及凭空发明的读写invented loads and stores。例外包括持有更新侧锁期间某个共享变量不可能被其他 CPU 更新时读它不必用READ_ONCE()早期启动阶段不可能有其他 CPU 读/写该变量时读不必用READ_ONCE()写也不必用WRITE_ONCE()。2.2 锁比临界区互斥更强的保证锁的基本规则非常朴素任何获得了某把锁的 CPU都能看到之前任何 CPU 在释放同一把锁之前所看到或做出的所有修改。注意这句话比持锁的 CPU 能看到持锁期间其他 CPU 做的所有修改要强。看这个经典对对应测试 MPpolocks.litmusvoid CPU0(void) { WRITE_ONCE(x, 1); spin_lock(mylock); WRITE_ONCE(y, 1); spin_unlock(mylock); } void CPU1(void) { spin_lock(mylock); r0 READ_ONCE(y); spin_unlock(mylock); r1 READ_ONCE(x); }如果 CPU0 先于 CPU1 获得mylock则 r0 和 r1 都必须是 1推论是若 r0 最终为 1则 r1 最终也必为 1。这比弱规则持锁期间看到的变化更强——弱规则对 r1 的最终值不做任何承诺。逆命题同样成立对应 MPporevlocks.litmusvoid CPU0(void) { r0 READ_ONCE(y); spin_lock(mylock); r1 READ_ONCE(x); spin_unlock(mylock); } void CPU1(void) { spin_lock(mylock); WRITE_ONCE(x, 1); spin_unlock(mylock); WRITE_ONCE(y, 1); }若 CPU0 先于 CPU1 获得锁则 r0 与 r1 必须都是 0推论是若 r1 最终为 0则 r0 最终也必为 0。这两个测试共同说明锁的获取/释放在形式上可以充当smp_load_acquire()/smp_store_release()两个 .litmus 文件头注释里明确写道 lock acquisitions and releases can stand in for smp_load_acquire() and smp_store_release(), respectively。上面只展示了单对 CPU但锁规则的效力可以跨越同一把锁在多 CPU 上的多次获取。但要注意由锁排序的访问不一定会被未持锁的 CPU 按序看到。看这个三 CPU 例子Z6.0pooncelockpooncelockpombonce.litmusvoid CPU0(void) { spin_lock(mylock); WRITE_ONCE(x, 1); WRITE_ONCE(y, 1); spin_unlock(mylock); } void CPU1(void) { spin_lock(mylock); r0 READ_ONCE(y); WRITE_ONCE(z, 1); spin_unlock(mylock); } void CPU2(void) { WRITE_ONCE(z, 2); smp_mb(); r1 READ_ONCE(x); }尽管违反直觉完全可能出现r0 1、z 2、r1 0的组合。原因在于 CPU2 从未获取过这把锁因此享受不到锁的排序属性该测试预期Result: Sometimes。补救办法是谨慎使用smp_mb__after_spinlock()把排序扩展到未持锁的 CPUZ6.0pooncelockpoonceLockpombonce.litmusvoid CPU1(void) { spin_lock(mylock); smp_mb__after_spinlock(); r0 READ_ONCE(y); WRITE_ONCE(z, 1); spin_unlock(mylock); }加上这行之后上面那个反直觉结果被排除预期Result: Never。从源码看include/linux/spinlock.h 中smp_mb__after_spinlock()被定义为程序序更早的锁获取与更晚的内存访问之间的全内存屏障等价物其注释属性 2明确说明它把锁升级为RCsc 锁并提到__schedule()与try_to_wake_up()中同样使用了该原语。关于无锁访问锁保护的共享变量详见 tools/memory-model/Documentation/locking.txt它是本节的扩展。三、摘掉训练轮进阶示例这一节分析更复杂的模式消息传递MP、载入缓冲LB、释放-获取链Release-Acquire Chains与存储缓冲SB。许多 litmus 测试类有缩写名例如poprogram order程序序、once普通 READ_ONCE/WRITE_ONCE、mbsmp_mb、release/acquire、lock/unlock、ctrl控制依赖、rfreads-from等理解这些命名有助于直接读懂测试名表达的含义。3.1 消息传递MPMP 模式一个 CPU 对一对变量做两次存储另一个 CPU 以相反顺序对同一对变量做两次加载。目标是避免这样的反直觉结果第一次加载看到第二次存储写的值而第二次加载却没看到第一次存储写的值。在没有任何排序时这个目标无法保证——MPpoonceonces.litmus 正是无排序的 MP 可能出问题的演示Result: Sometimes。下面给出三种满足 MP 排序的方案。3.1.1 释放-获取Release and Acquire使用smp_store_release()与smp_load_acquire()MPpooncereleasepoacquireonce.litmusvoid CPU0(void) { WRITE_ONCE(x, 1); smp_store_release(y, 1); } void CPU1(void) { r0 smp_load_acquire(y); r1 READ_ONCE(x); }WRITE_ONCE(x, 1)先于smp_store_release(y, 1)发生而smp_store_release()把该变量之前的所有访问与这次存储排序smp_load_acquire()把这次加载与之后的所有访问排序。因此若 r0 最终为 1则 r1 也必为 1。内核实例lib/stackdepot.c中的init_stack_slab()就以此方式用 release-acquire 安全地初始化一个栈 slabstack slab。从 lib/stackdepot.c 的源码看该文件维护了经过smp_store_release()发布的next_slab指针读取侧则通过smp_load_acquire()获取从而在没有显式锁的情况下安全交接已初始化的 slab。3.1.2 赋值与解引用Assign and DereferenceRCU 变体rcu_assign_pointer()与rcu_dereference()的用法和 release/acquire 很相似区别在于它们操作的是受 RCU 保护的指针MPonceassignderefonce.litmusint z; int *y z; int x; void CPU0(void) { WRITE_ONCE(x, 1); rcu_assign_pointer(y, x); } void CPU1(void) { rcu_read_lock(); r0 rcu_dereference(y); r1 READ_ONCE(*r0); rcu_read_unlock(); }若 r0 最终为x则 r1 必为 1。关键差异在于排序强度rcu_assign_pointer()与smp_store_release()排序性质相同而rcu_dereference()只把加载与依赖该加载值的后续访问排序。依赖分为三种地址依赖address dependency加载值决定后续访问的地址上例即是数据依赖data dependency加载值决定后续存储写入的值控制依赖control dependency加载值决定后续存储是否执行。注意数据依赖有时被口语化地用来同时涵盖地址依赖与数据依赖。内核实例lib/math/prime_numbers.c 中expand_to_next_prime()调用rcu_assign_pointer()见lib/math/prime_numbers.c中rcu_assign_pointer(primes, new)等行next_prime_number()调用rcu_dereference()同文件多处rcu_dereference(primes)二者配合管理一个按需扩展的位向量bit vector在需要更多素数时扩展它。这个组合正是 RCU 指针赋值/解引用模式的真实应用。3.1.3 写屏障与读屏障smp_wmb / smp_rmb通常建议优先用smp_store_release()代替smp_wmb()用smp_load_acquire()代替smp_rmb()但老 API 仍然被广泛使用理解其适用场景很重要MPfencewmbonceoncefencermbonceonce.litmusvoid CPU0(void) { WRITE_ONCE(x, 1); smp_wmb(); WRITE_ONCE(y, 1); } void CPU1(void) { r0 READ_ONCE(y); smp_rmb(); r1 READ_ONCE(x); }smp_wmb()把先前的存储与后续的存储排序smp_rmb()把先前的加载与后续的加载排序。因此若 r0 最终为 1则 r1 必为 1。内核实例一XFSfs/xfs/xfs_log.c 中xlog_state_switch_iclogs()的写侧片段log-l_curr_block - log-l_logBBsize; ASSERT(log-l_curr_block 0); smp_wmb(); log-l_curr_cycle;对应读侧片段在 fs/xfs/xfs_log_priv.h 的xlog_valid_lsn()中cur_cycle READ_ONCE(log-l_curr_cycle); smp_rmb(); cur_block READ_ONCE(log-l_curr_block);写侧先更新l_curr_block再smp_wmb()后更新l_curr_cycle读侧先读l_curr_cycle再smp_rmb()后读l_curr_block从而保证 LSN日志序列号在日志回绕cycle wrap时永远不会以瞬时超前的形态被看到。内核实例二perf ring bufferkernel/events/ring_buffer.c 中perf_output_put_handle()的注释展示了内核与用户空间的配对* kernel user * * if (LOAD -data_tail) { LOAD -data_head * (A) smp_rmb() (C) * STORE $data LOAD $data * smp_wmb() (B) smp_mb() (D) * STORE -data_head STORE -data_tail * }其中B/C 配对就是 MP 模式内核侧写侧用smp_wmb()B分隔两次 STORE用户侧读侧用smp_rmb()C分隔两次 LOAD。注释里说明 B 用 WMB 足够只分隔两个写、C 用 RMB 足够只分隔两个读。当然由于smp_mb()严格强于smp_wmb()/smp_rmb()任何用smp_rmb()/smp_wmb()能工作的片段用smp_mb()替换其中任一或全部弱屏障也必然能工作。3.2 载入缓冲LBLB 模式一个 CPU 先从变量 A 加载、再向变量 B 存储另一个 CPU 先从 B 加载、再向 A 存储。目标是避免每个加载都读到对方存储写入的值的反直觉情况。无排序时这种情况完全可能发生见 LBpoonceonces.litmus。避免该结果的方案之一是控制依赖 全内存屏障LBfencembonceoncectrlonceonce.litmusvoid CPU0(void) { r0 READ_ONCE(x); if (r0) WRITE_ONCE(y, 1); } void CPU1(void) { r1 READ_ONCE(y); smp_mb(); WRITE_ONCE(x, 1); }CPU0 中的控制依赖与 CPU1 中的全屏障配对阻止 r0 和 r1 同时为 1。该测试头注释还补充了一个细节CPU1 的全屏障也可以用另一个控制依赖替换排序依然保持。内核实例仍是 perf ring buffer前面注释中的A/D 配对即 LB 模式——内核侧LOAD -data_tailA与STORE $data之间是控制依赖若-data_tail表明缓冲区没有空间则不存储$data用户侧LOAD $data与STORE -data_tail之间是全内存屏障D注释明确 D 需要是全屏障因为它分隔数据读与 tail 写。二者合力防止内核在用户还没读完数据之前就覆盖了数据的反直觉结果。3.3 释放-获取链Release-Acquire Chains释放-获取链是低开销、灵活、易用的排序手段但也有必须理解的局限。先看一个能正确排序的例子ISA2pooncereleasepoacquirereleasepoacquireonce.litmusvoid CPU0(void) { WRITE_ONCE(x, 1); smp_store_release(y, 1); } void CPU1(void) { r0 smp_load_acquire(y); smp_store_release(z, 1); } void CPU2(void) { r1 smp_load_acquire(z); r2 READ_ONCE(x); }若 r0、r1 最终都为 1则 r2 必为 1。该测试注释给出了链为何够用的内存模型解释除 P2→P0 之外每个进程都读自前一个进程的写即只有一个非 reads-from非 rf链接。这个示例的排序比实际需要的强例如把 CPU1 的smp_load_acquire()换成READ_ONCE()排序依然保持。但一个常见误区是以为 CPU0 对 x 的存储被全局排序在 CPU1 对 z 的存储之前——事实并非如此Z6.0pooncereleasepoacquirereleasefencembonceonce.litmusResult: Sometimesvoid CPU2(void) { WRITE_ONCE(z, 2); smp_mb(); r1 READ_ONCE(x); }你可能希望r0 为 1 且 z 为 2 时r1 必为 1但 r1 真的可能为 0。原因当然是这个版本里CPU2 不在释放-获取链中。该测试注释进一步剖析三个进程里只有 P1 读自 P0 的写因此存在两个非 rf 链接——P1→P2 是写-写链接coherence简称 coP2→P0 是读-写链接from-reads简称 fr。当非 rf 链接达到两个或更多时通常需要为每个非 rf 链接配一个全屏障。尽管有这些局限释放-获取链作为内存排序机制依然是低开销、简单且强大的。3.4 存储缓冲SB存储缓冲可视为倒过来的载入缓冲一个 CPU 先向变量 A 存储、再加载变量 B另一个 CPU 先向 B 存储、再加载 A。要保住顺序非全屏障不可SBfencembonceonces.litmusvoid CPU0(void) { WRITE_ONCE(x, 1); smp_mb(); r0 READ_ONCE(y); } void CPU1(void) { WRITE_ONCE(y, 1); smp_mb(); r1 READ_ONCE(x); }省略任意一个smp_mb()r0 和 r1 就可能同时为 0两个全屏障都在就排除了这个反直觉结果。这个模式最著名的出场是Dekker 互斥算法但在内核中它有个更实用的场景——排序唤醒操作ordering wakeups。include/linux/wait.h 中waitqueue_active()的注释给出了规范模式* CPU0 - waker CPU1 - waiter * * for (;;) { * cond true; prepare_to_wait(wq_head, wait, state); * smp_mb(); // smp_mb() from set_current_state() * if (waitqueue_active(wq_head)) if (cond) * wake_up(wq_head); break; * schedule(); * } * finish_wait(wq_head, wait);CPU0 的存储是cond true加载在waitqueue_active()中CPU1 的prepare_to_wait()既向wq_head存储、又调用含smp_mb()屏障的set_current_state()加载是if (cond)。两个全屏障合力阻止CPU1 把等待任务送入睡眠、CPU0 却没能唤醒它的糟糕结果。注释还特别提醒没有显式smp_mb()时waitqueue_active()的加载可能被提升hoisted越过cond的存储从而观察到空等待队列而等待者可能根本没看到cond。注意使用锁可以极大简化这一模式见 2.2 节的锁规则。四、经验法则Rules of Thumb看起来什么场景该用什么排序原语似乎毫无规律其实不然——规律建立在litmus 测试中连接相邻 CPU 内存访问的关系类型上。有三种链接类型写-读Write-to-read下一个 CPU 读到前一个 CPU 写入的值。LB 模式只含这种关系。形式化内存模型文献中称其为reads-from缩写rf。读-写Read-to-write下一个 CPU 覆盖前一个 CPU 读到的值。SB 测试只含这种关系。文献中常称from-reads有时缩写fr。写-写Write-to-write下一个 CPU 覆盖前一个 CPU 写入的值。Z6.0 模式中CPU1 的最后一个访问与 CPU2 的第一个访问之间就是写-写关系。文献中常称coherence order缩写coC 标准中则叫modification order缩写mo。某个 litmus 测试要避免反直觉结果所需的排序强度取决于目标结果所涉及访问之间的链接类型若所有链接都是写-读rf链接每个 CPU 内部最弱的排序就够。例如 LB 测试中一个控制依赖就能完成任务。若除一个链接外其余都是写-读链接释放-获取链就够。MP 与 ISA2 测试都属于这种情况。若存在不止一个非写-读链接每对连续的非写-读链接之间都需要一个全内存屏障。锁章节与释放-获取章节中的 Z6.0 测试都演示了这种情况。最后一条重要建议如果你发现自己需要拉伸这些经验法则才能适配场景请创建一个 litmus 测试并在模型上运行验证——这正是 tools/memory-model/litmus-tests 目录存在的意义。五、实战如何运行与验证这些配方5.1 用 herd7 穷举验证在源码树的tools/memory-model目录下以本文反复提到的 SB 测试为例命令与输出均引自 tools/memory-model/READMEcd $LINUX_SOURCE_TREE/tools/memory-model herd7 -conf linux-kernel.cfg litmus-tests/SBfencembonceonces.litmus对应输出节选Test SBfencembonceonces Allowed States 3 0:r00; 1:r01; 0:r01; 1:r00; 0:r01; 1:r01; No Witnesses Positive: 0 Negative: 3 Condition exists (0:r00 /\ 1:r00) Observation SBfencembonceonces Never 0 3Positive: 0 Negative: 3与Never 0 3都表明该测试的exists子句0:r00 /\ 1:r00不可能满足与文件头注释的Result: Never一致。其余配方测试同理Result: Sometimes的测试如MPpoonceonces、两个Z6.0...则会得到Sometimes观测结果。5.2 用 klitmus7 在真实硬件上跑klitmus7把 litmus 测试转换成内核模块mkdir mymodules klitmus7 -o mymodules litmus-tests/SBfencembonceonces.litmus cd mymodules; make sudo sh run.sh输出会给出两百万次试验的直方图Histogram例如Positive: 0, Negative: 2000000表示两百万次试验中exists子句描述的状态从未出现与模型结论一致。5.3 用脚本批量回归tools/memory-model/scripts 提供了一组自检脚本均从tools/memory-model目录运行checkalllitmus.sh运行litmus-tests目录下全部测试并与各文件Result:注释中的预期结果比对checktheselitmus.sh检查指定清单的测试initlitmushist.sh / newlitmushist.sh / checklitmushist.sh管理.litmus.out历史结果并比对差异。这些脚本让新增配方 → 模型验证 → 硬件实测形成闭环正是 recipes 文档所倡导的先建模、再上机的工程化做法。六、延伸阅读tools/memory-model/Documentation/litmus-tests.txtlitmus 测试的格式、特性、能力与限制tools/memory-model/Documentation/locking.txt无锁访问锁保护共享变量的细节2.2 节的扩展tools/memory-model/Documentation/control-dependencies.txt控制依赖的深入剖析tools/memory-model/Documentation/ordering.txt各排序原语与屏障的对照tools/memory-model/Documentation/access-marking.txt共享变量访问标注READ_ONCE/WRITE_ONCE规范tools/memory-model/Documentation/simple.txt与本文简单特例章节互为呼应的入门说明模型本身linux-kernel.bell、linux-kernel.cat、linux-kernel.def、lock.cat。本文涉及的全部配方测试均可直接运行验证MPpolocks、MPporevlocks、Z6.0pooncelockpooncelockpombonce、Z6.0pooncelockpoonceLockpombonce、MPpooncereleasepoacquireonce、MPonceassignderefonce、MPfencewmbonceoncefencermbonceonce、LBfencembonceoncectrlonceonce、ISA2pooncereleasepoacquirereleasepoacquireonce、Z6.0pooncereleasepoacquirereleasefencembonceonce、SBfencembonceonces等全部位于 tools/memory-model/litmus-tests 目录。【免费下载链接】linuxLinux kernel source tree项目地址: https://gitcode.com/GitHub_Trending/li/linux创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考