memory model litmus 测试

由内核模块 m/concurrent/memory_model.c 和 m/concurrent/mm_ll.c 转换而来的用户态测试, 并补充了经典的 SB / MP / LB litmus 测试。使用 pthread + C11 stdatomic, Linux (gcc) 和 macOS / Asahi Linux (clang / gcc) 都可以直接编译。

构建和运行

// 参考: https://github.com/smcdef/memory-reordering

make            # 每个测试生成 xx-nofence.out 和 xx-fence.out 两个版本
./run-all.sh    # 每个测试跑 5 秒, 依次输出结果
./sb-nofence.out 10   # 也可以单独跑, 参数是秒数, 默认 10

测试变量一律是 volatile + compiler_barrier(), 禁止编译器重排, 因此观察到的都是 CPU 层面的乱序。 另外测试变量按 256B 对齐放到不同 cache line 上: 若共享一条 cache line, 两个 store 会随同一个 line 一起可见, mp / lb 几乎不可能触发。 (dekker 相反, 故意让两个 flag 共享一条 line 来加剧 ownership 争抢, 否则 Apple Silicon 上几乎测不到, 见 dekker.c 注释。)

测试列表

测试 litmus 检测的乱序结果 x86 (TSO) ARM
sb x=1; r1=y ∥ y=1; r2=x r1=0 且 r2=0 允许 允许
dekker flag[i]=1; if (!flag[j]) 进临界区 双方同时在临界区 允许 允许
mp x=i; y=i 递增 ∥ r1=y; r2=x r1 > r2 禁止 允许
lb r1=x; y=1 ∥ r2=y; x=1 r1=1 且 r2=1 禁止 允许
ll x=1; y=1 ∥ r1=x; r2=y r1=1 且 r2=0 (假象, 见下) 不适用 不适用
wr x=1; y=1; y=0; x=0 循环 看到 y=1 且 x=0 禁止 允许
ss a=t; b=t ∥ d=b; c=a d > c 禁止 允许
xor v ^= bit0 ∥ v ^= bit1 最终值非 0 (lost update) 发生 发生

sb / lb / ll 用 watcher 每轮重置变量并 rendezvous 两个 actor (等价于内核版本里的 sem_x / sem_y / sem_end 信号量), mp / wr / ss 自由跑 (mp 用单调递增避免重置, wr / ss 和内核版本一致)。

实测结果

x86_64 (本机, Intel/AMD)

[sb-nofence] arch=x86: reorder(r1=0,r2=0) detected 4185618 / 18320364 iterations
[sb-fence]   arch=x86: reorder(r1=0,r2=0) detected 0 / 18426997 iterations
[mp-nofence] arch=x86: reorder(flag>data) detected 0 / 97452152 checks
[mp-fence]   arch=x86: reorder(flag>data) detected 0 / 170042961 checks
[lb-nofence] arch=x86: reorder(r1=1,r2=1) detected 0 / 15262854 iterations
[lb-fence]   arch=x86: reorder(r1=1,r2=1) detected 0 / 17369335 iterations
[ll-nofence] arch=x86: racy-timing(r1=1,r2=0) detected 124676 / 19134872 iterations (NOT a reorder proof)
[ll-fence]   arch=x86: racy-timing(r1=1,r2=0) detected 702165 / 17651800 iterations (NOT a reorder proof)
[wr-nofence] arch=x86: hits(y=1,x=0) 0 / 100433190 checks (fence 版本不归零说明是时间窗口假象)
[wr-fence]   arch=x86: hits(y=1,x=0) 8515 / 272122218 checks (fence 版本不归零说明是时间窗口假象)
[ss-nofence] arch=x86: reorder(d>c) detected 0 / 113936849 checks
[ss-fence]   arch=x86: reorder(d>c) detected 0 / 117962080 checks
[dekker-nofence] arch=x86: mutual-exclusion broken 74737578 / 74739837 enters
[dekker-fence]   arch=x86: mutual-exclusion broken 0 / 46449249 enters
[xor-plain]  arch=x86: lost-update in 16 / 30 trials (each thread 500000 flips)
[xor-atomic] arch=x86: lost-update in 0 / 30 trials (each thread 500000 flips)

aarch64 (Asahi Linux @ Apple Silicon, 100.113.183.51)

[sb-nofence] arch=arm: reorder(r1=0,r2=0) detected 95 / 29092460 iterations
[sb-fence]   arch=arm: reorder(r1=0,r2=0) detected 0 / 24077549 iterations
[mp-nofence] arch=arm: reorder(flag>data) detected 136589057 / 342861784 checks
[mp-fence]   arch=arm: reorder(flag>data) detected 0 / 183557732 checks
[lb-nofence] arch=arm: reorder(r1=1,r2=1) detected 0 / 33399335 iterations
[lb-fence]   arch=arm: reorder(r1=1,r2=1) detected 0 / 24703486 iterations
[ll-nofence] arch=arm: racy-timing(r1=1,r2=0) detected 4 / 33475849 iterations (NOT a reorder proof)
[ll-fence]   arch=arm: racy-timing(r1=1,r2=0) detected 174 / 26362565 iterations (NOT a reorder proof)
[wr-nofence] arch=arm: hits(y=1,x=0) 285199 / 3117154268 checks (fence 版本不归零说明是时间窗口假象)
[wr-fence]   arch=arm: hits(y=1,x=0) 2 / 3429056110 checks (fence 版本不归零说明是时间窗口假象)
[ss-nofence] arch=arm: reorder(d>c) detected 23585059 / 1462506076 checks
[ss-fence]   arch=arm: reorder(d>c) detected 0 / 193916441 checks
[dekker-nofence] arch=arm: mutual-exclusion broken 261679600 / 310918434 enters
[dekker-fence]   arch=arm: mutual-exclusion broken 0 / 207811091 enters
[xor-plain]  arch=arm: lost-update in 21 / 30 trials (each thread 500000 flips)
[xor-atomic] arch=arm: lost-update in 0 / 30 trials (each thread 500000 flips)

结果解读

整理一下这个笔记 https://research.swtch.com/mm

用 sb.c 中的内容来测试的:

// Thread 1           // Thread 2
x = 1;                while(done == 0) { /* loop */ }
done = 1;             print(x);

It depends. It depends on the hardware, and it depends on the compiler. A direct line-for-line translation to assembly run on an x86 multiprocessor will always print 1. But a direct line-for-line translation to assembly run on an ARM or POWER multiprocessor can print 0.

drawing

https://research.swtch.com/hwmm

drawing

https://research.swtch.com/hwmm

Litmus Test: Write Queue (also called Store Buffer) Can this program see r1 = 0, r2 = 0?

// Thread 1           // Thread 2
x = 1                 y = 1
r1 = y                r2 = x

This example may seem artificial, but using two synchronization variables does happen in well-known synchronization algorithms, such as Dekker's algorithm or Peterson's algorithm, as well as ad hoc schemes. They break if one thread isn’t seeing all the writes from another.

kimi 的回忆

完成。新增 dekker.c —— 不加屏障的 Dekker 互斥锁，StoreLoad 乱序直接导致双方同时进入临界区：

┌─────────┬─────────────────────────────────┬─────────────────────────┐ │ 版本 │ x86 │ ARM │ ├─────────┼─────────────────────────────────┼─────────────────────────┤ │ nofence │ 7474 万/7474 万进入失效（~100%) │ 2.6 亿/3.1 亿失效（84%) │ ├─────────┼─────────────────────────────────┼─────────────────────────┤ │ fence │ 0/4645 万 │ 0/2.1 亿 │ └─────────┴─────────────────────────────────┴─────────────────────────┘

你听到的没错：StoreLoad 是 x86 TSO 唯一允许的乱序，前面的 sb.c 测的就是它；dekker 展示的是它的软件后果——互斥锁失效，效果更直观。

调试这个测试时踩了两个坑，都写进了 dekker.c 注释和 README:

• 检测代码自身也怕乱序：最初用 in_cs 计数判断双方同时在临界区，ARM fence 版本误报率 80%——退出方 in_cs=0 的 store 被排到 flag=0 之后可见，互斥 明明成立也会误报。记账代码两侧必须用无条件 dmb（不能跟着 FENCE() 宏走）。这本身就是”ARM 上共享变量通信都要考虑序”的活教材 • Apple Silicon 上真实乱序率太低：flag 分 cache line 时 ARM nofence 一次都测不到（和 sb 分线后只有 95/2909 万一致）；让两个 flag 共享一条 line 加剧 ownership 争抢后才到 84%。这也解释了为什么这类 bug 在 ARM 上难复现但不代表不存在

README 的测试表格、两个架构的实测结果和解读都已更新，ARM 机器上的 ~/memory-model-tests/ 也同步了。

这个也可以整理了

https://zhuanlan.zhihu.com/p/41872203

TODO

我总是感觉这里的例子有点奇怪，每次启动一个 thread，真的就可以运气那么好，然后卡到一起吗?

本站所有文章转发 CSDN 将按侵权追究法律责任，其它情况随意。