Rust in Everything
基于 loom 0.7.2

内存模型

02 运行时 回答「下一步轮到哪个线程」,这一部分回答另一半:轮到的线程做一次原子读,能读到哪些值,以及读到之后线程之间多了什么因果关系。代码集中在 rt/atomic.rs(931 行)、rt/vv.rs(86 行)和 rt/synchronize.rs(63 行)三个文件,另有 rt/thread.rs 里每个线程的时钟和全局的 seq_cst_causality。

flowchart TB
  op["AtomicUsize::load / store / fetch_add / fence"] --> br["branch:调度点(fence 除外)"]
  br --> sy["synchronize:本线程时钟自增"]
  sy --> st["State:最近 7 次写的环形数组"]
  st --> m["match_load_to_stores / match_rmw_to_stores:列出候选写"]
  m --> path["Path 的 Load 分支:这一轮取第几个候选"]
  path --> ld["State::load / rmw:coherence、first_seen、Synchronize"]
  ld --> vv["线程的 causality 时钟(happens-before)"]
  vv --> chk["04 检测器:UnsafeCell、with_mut 用同一套时钟判竞争"]

五章:

  1. 向量时钟与同步点:VersionVec 的三个操作;每线程 causality、released、dpor_vv 三套时钟;synchronize() 只在原子操作、fence、单元格访问前自增;Synchronize 怎样实现 Release / Acquire;spawn 与 unpark 带来的 happens-before。
  2. 写历史与 coherence:State 与 Store 的字段;修改顺序用向量时钟表示的偏序;四条 coherence 规则各在哪几行;文件头那张 CDSChecker 规则清单里哪些是空的;7 次写的窗口(E6:连写 7 次后初值不再是候选)。
  3. load 的候选:主线 2 的核心。match_load_to_stores 的三条排除规则逐条配实验;yield_now 之后不再给旧值(新实验:同一个模型加一次 yield_now,「对方已写、仍读到 0」这一种结果消失);CoRR 的六种结果(E5);unsync_load 不建分支。
  4. RMW 与释放序列:match_rmw_to_stores 只给修改顺序上最新的写;成功的 RMW 继承所读写的 Synchronize 形成释放序列(实验:RMW 续上、普通写断开);失败的 CAS 也只读最新写;compare_exchange_weak 不会伪失败(E16);与 tokio #1788 的 fetch_add(0)。
  5. fence 与 SeqCst:四种 fence 的实现与 Relaxed fence 的 panic;fence(SeqCst) 是对全局时钟的双向 join;SeqCst 访问的 seq_cst() 是空函数,只剩 load 匹配里的一条规则;SB、RWC、IRIW 三个 litmus 的实测结果;这段实现的历史(#108、#111、#220)。

不重讲的部分

文档与代码的出入

出处的说法代码在哪章
rt/atomic.rs 文件头按 CDSChecker 图 7 / 9 / 10 列出规则「Seq-cst/MO Consistency」「Seq-cst Write-Read Coherence」「RMW Atomicity」以及图 9 的六条 SC fence 规则后面都是空的(atomic.rs:32-55);其中 RMW 原子性实际由 match_rmw_to_stores 实现写历史与 coherence
Mutex 构造时传 seq_cst = true,解锁处注释「Establish sequential consistency between the lock's operations」调用的 threads.seq_cst() 是空函数(thread.rs:336-341)fence 与 SeqCst
assert_ne!(mo_i, mo_j) 旁的注释「TODO: this sometimes fails」断言仍在,同样的断言在 match_rmw_to_stores 里没有这条注释load 的候选
README「SeqCst accesses … are regarded as AcqRel」与代码一致;唯一多出来的是 SeqCst load 在两个 SeqCst 写之间不读旧的那一条(atomic.rs:766-769)fence 与 SeqCst

演进

只列 git log -S 可查的事实;0.5.3、0.5.4 两个版本在 CHANGELOG 里有、仓库里没有对应 tag,版本号以 CHANGELOG 为准。

时间提交版本变化
2018-12-21a2dcce6「Refine atomic history w.r.t yielding」0.1.0is_seen_before_yield:yield 之后不再给已读过的旧值
2019-09-20f8ef5e1「Add initial atomic::fence support」(#57)0.2.6只支持 fence(Acquire),其余序 assert_eq! 失败
2020-02-16fd8680c「Relax how SeqCst is modelled」(#108)0.2.15原先 SeqCst 访问对全局时钟双向 join(全局 happens-before),被改成空函数
2020-03-2388e4225「Overhaul internals to support faster execution」(#111)0.3.0写历史改成 7 格环形数组,修改顺序改用向量时钟,新增 match_load_to_stores / match_rmw_to_stores
2021-09-22ffb2672「Implement Release, AcqRel, and SeqCst fences」(#220)0.5.2线程多一个 released 时钟;seq_cst_fence 把 #108 删掉的双向 join 只用在 fence(SeqCst) 上;README 新增「Unsupported features」

本部分的实验

机器 M2 Max(8P + 4E),macOS,rustc 1.99.1,loom =0.7.2,RUSTFLAGS="--cfg loom" cargo test --release --offline,每个实验目录单独的 CARGO_TARGET_DIR。loom 在一个 OS 线程上跑完所有模型线程,交错数是确定的,重跑结果相同;本部分只报告交错数和结果集合,不报告耗时。

#目录看什么章
E1exp-loom/survey/tests/mp.rs消息传递:Release / Acquire 6 个交错通过,Relaxed 第 3 个交错被抓到向量时钟与同步点
E5exp-loom/survey/tests/litmus.rs、exp-loom/memory-model/tests/fences.rsSB 的四种写法、CoRR;单侧 fence、RWC、IRIW、fence 版消息传递load 的候选、fence 与 SeqCst
E6exp-loom/memory-model/tests/history.rs7 次写的窗口,n = 5 … 9写历史与 coherence
—exp-loom/memory-model/tests/yield_.rsyield_now 前后同一个线程能读到的值load 的候选
E16exp-loom/memory-model/tests/rmw.rsRMW 读最新写、释放序列、失败的 CAS、fetch_add(0) 版 SB、compare_exchange_weakRMW 与释放序列

💬 关联讨论

发起讨论
加载中...