向量时钟与同步点

主线位置：主线 2 与主线 3 共用的底座。主线 2 里 Acquire 读「把那次写的 happens_before 并进本线程时钟」，主线 3 里 UnsafeCell 用「上一次写的时钟是否领先」判竞争，说的都是这一页的两个类型：VersionVec 和 Synchronize。

VersionVec：每个线程一个计数

rt/vv.rs:8-12：

pub(crate) struct VersionVec {
    versions: [u16; MAX_THREADS],
}

MAX_THREADS 是 5（rt/mod.rs:61-62），所以一个时钟就是 5 个 u16，按线程编号下标，Copy，10 字节。第 i 个分量的意思是「我已经知道 i 号线程做到了它的第几步」。三个操作：

后面几章用的都是这三个操作：修改顺序用 < 比较（写历史与 coherence），DPOR 用 <= 判断两次访问是否有先后（02 DPOR），检测器用 ahead 找出「没看到的那次访问」（04 检测器）。

分量是 u16，自增是普通的 += 1（vv.rs:31-33）。一个分量在一轮执行里加多少次，取决于这个线程做了多少次下面要讲的「同步操作」，每一轮开始时清零。

每个线程三套时钟

rt/thread.rs:20-27：

    /// Tracks observed causality
    pub causality: VersionVec,

    /// Tracks the view of the lastest release fence
    pub released: VersionVec,

    /// Tracks DPOR relations
    pub dpor_vv: VersionVec,

causality 和 dpor_vv 是两套独立的时钟：一次 Relaxed 读在 causality 上什么也不传递，但 DPOR 仍然把「读」和「之前的写」当作相关访问记进 dpor_vv。两者回答的问题不同：前者是「这个线程在内存模型意义上知道什么」，后者是「调换这两个操作的顺序会不会改变结果」。

另外还有一个全局时钟 Set::seq_cst_causality（thread.rs:54-56），只有 fence(SeqCst) 用它，见 fence 与 SeqCst。

synchronize()：先给自己记一步

rt/mod.rs:137-146：

fn synchronize<F, R>(f: F) -> R
where
    F: FnOnce(&mut Execution) -> R,
{
    execution(|execution| {
        execution.threads.active_causality_inc();
        trace!("synchronize");
        f(execution)
    })
}

本线程自己的分量加一，然后执行操作本身。全仓库只有六处调用它：原子 load、store、rmw（atomic.rs:231、276、309），fence（atomic.rs:168），UnsafeCell 的 start_read / start_write（rt/cell.rs:55-84）。锁、Arc、Notify、channel 只做 sync_store / sync_load，不自增本线程的分量。

自增发生在操作之前，所以「本线程第 k 步」的编号就是做这一步时 causality[self] 的值。Store.first_seen 记的、UnsafeCell 的 write_access 记的，都是这个编号。

synchronize 和 branch 是两回事：branch 是调度点（02 DPOR），synchronize 只推进时钟。原子 load / store / rmw 两样都做；fence 和单元格访问只做 synchronize，不是调度点。

Synchronize：一个可以存时钟的地方

rt/synchronize.rs 全文 63 行，一个字段 happens_before: VersionVec：

    pub fn sync_load(&mut self, threads: &mut thread::Set, order: Ordering) {
        match order {
            Relaxed | Release => {
                // Nothing happens!
            }
            Acquire | AcqRel => {
                self.sync_acq(threads);
            }
            SeqCst => {
                self.sync_acq(threads);
                threads.seq_cst();
            }
            order => unimplemented!("unimplemented ordering {:?}", order),
        }
    }

    pub fn sync_store(&mut self, threads: &mut thread::Set, order: Ordering) {
        self.happens_before.join(&threads.active().released);
        match order {
            Relaxed | Acquire => {
                // Nothing happens!
            }
            Release | AcqRel => {
                self.sync_rel(threads);
            }
            SeqCst => {
                self.sync_rel(threads);
                threads.seq_cst();
            }
            order => unimplemented!("unimplemented ordering {:?}", order),
        }
    }

sync_rel 是「把本线程 causality 并进同步点」，sync_acq 是「把同步点并进本线程 causality」。整个 Release / Acquire 语义就是这两句 join：

• 写：先无条件并入 released（最近一次 release fence 时的快照，没做过 fence 就是全零），这一句让「fence(Release) + Relaxed 写」也能发布数据；序是 Release / AcqRel / SeqCst 时再并入当前 causality。
• 读：序是 Acquire / AcqRel / SeqCst 时，把读到的那次写的同步点并进来。
• SeqCst 多调的 threads.seq_cst() 是空函数，见 fence 与 SeqCst。

flowchart LR
  subgraph w["写者线程"]
    wc["causality"]
    wr["released（最近一次 release fence 的快照）"]
  end
  s["这次写的 Synchronize"]
  subgraph r["读者线程"]
    rc["causality"]
  end
  wr -->|"任何序的写：join"| s
  wc -->|"Release / AcqRel / SeqCst 写：join"| s
  s -->|"Acquire / AcqRel / SeqCst 读：join"| rc

不合法的序不报错。 load(Release)、store(_, Acquire)、失败序为 Release 的 CAS，在 std 里运行时 panic（比如「there is no such thing as a release load」），loom 落到「Nothing happens!」分支照常执行。实测（exp-loom/memory-model/tests/bad_order.rs）：三种写法在 loom 下各 1 个交错通过，同样的 load(Release) 用 std 原子直接 panic。字面量写错序时编译器的 invalid_atomic_ordering lint 只认 std 的原子类型，所以这类错误要靠非 loom 构建的普通测试发现。

每个原子写都带一个自己的 Synchronize（Store.sync），锁、Arc、Notify、lazy_static 各有一个，channel 每条消息一个。它们怎么用这两个函数，见 05 同步原语的模型。

Store 上的两个时钟不是一回事

原子写记录两个看起来相似的东西（atomic.rs:141-161）：

• Store.happens_before：写的那一刻写者的 causality，无论什么序都记。只用于 coherence 规则（「这次写是否发生在本线程之前」），不传递给读者。
• Store.sync.happens_before：读者 acquire 时能拿到的时钟。Relaxed 写且之前没有 release fence 时它是全零，读者什么也拿不到。

Relaxed 写也会让读者「不能再读更早的值」（coherence），但不会让读者「看到写者之前的普通内存写」（happens-before）。前者靠第一个时钟，后者靠第二个。

一次消息传递里的时钟

E1 的单元格版本（exp-loom/survey/tests/mp.rs）：子线程 data.with_mut(写 42) 再 flag.store(true, Release)；主线程 flag.load(Acquire) 读到 true 就 data.with(读)。下表是「子线程先跑完、主线程再读」那一轮，按代码逐步推算的 causality（只写前两个分量，[主线程, 子线程]）：

把 Acquire 换成 Relaxed，主线程读完是 [2, 0]，with 时是 [3, 0]，write_access 的第 1 个分量 2 领先，ahead 返回 1，报「Causality violation: Concurrent read and write accesses.」。E1 实测：Release / Acquire 6 个交错通过；Relaxed / Relaxed 和 Release / Relaxed 都在第 3 个交错报这句话；数据也换成原子、flag 用 Relaxed 时，第 3 个交错读到旧值 0（断言失败）；SeqCst / SeqCst 6 个交错通过。

线程之间的另外两条边

spawn。 execution.rs:77-92：

    pub(crate) fn new_thread(&mut self) -> thread::Id {
        let thread_id = self.threads.new_thread();
        let active_id = self.threads.active_id();

        let (active, new) = self.threads.active2_mut(thread_id);

        new.causality.join(&active.causality);
        new.dpor_vv.join(&active.dpor_vv);

        // Bump causality in order to ensure CausalCell accurately detects
        // incorrect access when first action.
        new.causality[thread_id] += 1;
        active.causality[active_id] += 1;

        thread_id
    }

子线程知道父线程在 spawn 之前做过的一切；父线程 spawn 之后做的事，子线程不知道。实测（exp-loom/checkers/tests/cell.rs）：父线程在 spawn 之前写单元格、子线程读，1 个交错通过；把父线程的写挪到 spawn 之后，第 1 个交错报「Causality violation: Concurrent read and write accesses.」，开 LOOM_LOCATION 时打印出读在 1 号线程、写在 0 号线程。注释里的 CausalCell 是 UnsafeCell 在 0.3.0 之前的名字。

反方向的边由 join 提供：JoinHandle::join 等的是一个 Notify，子线程结束时 notify 做 release、join 返回前做 acquire（05 线程、线程局部与 lazy_static）。

unpark。 thread.rs:153-156：被唤醒的线程直接并入唤醒者的整个 causality。线程唤醒自己时跳过 join（thread.rs:305-317）。Condvar、Notify 都建立在 park / unpark 之上，详见 05 Condvar、Notify 与 park。

小结

• VersionVec 是 5 个 u16；join 传递因果，ahead 找出「没看到的那一步」，partial_cmp 给出偏序。
• 每线程三套时钟：causality 管内存模型与竞争检测，released 存最近一次 release fence 的快照，dpor_vv 只给 DPOR 用。
• synchronize() 只在原子 load / store / RMW、fence、单元格访问前自增本线程分量；fence 与单元格访问不是调度点。
• Synchronize 用两句 join 实现 Release / Acquire；写总会带上 released，所以 release fence 后的 Relaxed 写也能发布；不合法的序不报错。
• 原子写的 happens_before 只用于 coherence，sync 才传给读者。
• spawn 时子线程继承父线程时钟、双方各加一；unpark 时被唤醒者并入唤醒者的时钟。