Chase-Lev 双端队列

主线位置：任务主线的主体。主人线程 Worker::push 把任务放到 back 一端；别的线程拿着 Stealer，从 front 一端 steal；主人自己 pop 时，LIFO 从 back 取、FIFO 从 front 取。只剩最后一个任务时，主人和窃取者在 front 上用 SeqCst CAS 一决胜负。

flowchart LR
  subgraph buf["buffer：容量 cap（2 的幂），下标对 cap 取模"]
    direction LR
    s0["front：下一个被偷的"] --- s1["……"] --- s2["back - 1：最后放进的"] --- s3["back：下一个空位"]
  end
  st["Stealer::steal：CAS front + 1"] -.-> s0
  fifo["FIFO pop：fetch_add front"] -.-> s0
  lifo["LIFO pop：back - 1"] -.-> s2
  push["push：写 back 槽，back + 1"] -.-> s3

结构

源码注释列了三篇文献（deque.rs 第 119–131 行）：Chase 和 Lev 的《Dynamic circular work-stealing deque》（SPAA 2005），给出可增长环形缓冲的算法；Lê、Pop、Cohen、Nardelli 的《Correct and efficient work-stealing for weak memory models》（PPoPP 2013），给出 C11 原子操作下的正确内存序；Norris 和 Demsky 的 CDSchecker（OOPSLA 2013），用模型检查找出过前者的问题。crossbeam 的实现照的是第二篇。

struct Inner<T> {
    /// The front index.
    front: AtomicWorkerIndex,

    /// The back index.
    back: AtomicWorkerIndex,

    /// The underlying buffer.
    buffer: CachePadded<Atomic<Buffer<T>>>,
}

（第 132 行）

• front、back 只增不减（pop 时临时减一的情况下面讲），读写槽位时才对 cap 取模（Buffer::at，index & (cap - 1)）。back - front 就是长度。
• buffer 是 crossbeam-epoch 的 Atomic<Buffer<T>>：扩容时整个换掉，旧的交给 epoch 回收（扩容与回收）。它单独包了一层 CachePadded，和两个下标隔开。
• 整个 Inner 再包一层 CachePadded，放在 Arc 里，Worker 和所有 Stealer 共享。

下标类型。 0.8.8 起，有 64 位原子的平台上下标是 i64（AtomicI64），否则是 isize（#1321，提交 a30b825e，第 15–34 行）。之前一直是 isize，在 32 位平台上是 32 位。同一个提交也改了 channel 和 queue 的下标。用有符号数是因为算法里长度会暂时变成负数：FIFO 的 pop 先 fetch_add 再检查，LIFO 的 pop 先把 back 减一再检查。

Worker 和 Stealer

pub struct Worker<T> {
    inner: Arc<CachePadded<Inner<T>>>,
    buffer: Cell<Buffer<T>>,
    flavor: Flavor,
    _marker: PhantomData<*mut ()>, // !Send + !Sync
}

unsafe impl<T: Send> Send for Worker<T> {}

pub struct Stealer<T> {
    inner: Arc<CachePadded<Inner<T>>>,
    flavor: Flavor,
}

unsafe impl<T: Send> Send for Stealer<T> {}
unsafe impl<T: Send> Sync for Stealer<T> {}

（Worker 第 215 行、Stealer 第 589 行）

• Worker 是 Send 但不是 Sync：可以交给另一个线程，但同一时刻只有一个线程能调用它的 push / pop。整个算法依赖「back 只有一个写者」，类型系统用 !Sync 保证这一点。
• Worker 自己缓存了一份 buffer（Cell<Buffer<T>>），主人读 buffer 不需要原子操作，也不需要 pin。只有窃取者要从 inner.buffer 原子地读。
• Stealer 可以 Clone、可以跨线程共享，Worker::stealer() 生成。
• flavor 在 new_fifo() / new_lifo() 时定下，之后不变。

两种 flavor 只影响主人从哪头 pop：

LIFO 是工作窃取的经典用法：主人优先处理刚产生的子任务（数据还在缓存里），窃取者拿走最老的那个（通常是更大的一块工作）。rayon 默认就用 LIFO，配置成 breadth-first 时才用 FIFO（rayon-core 的 registry.rs 第 250–261 行）。

push

第 414 行：

pub fn push(&self, task: T) {
    // Load the back index, front index, and buffer.
    let b = self.inner.back.load(Ordering::Relaxed);
    let f = self.inner.front.load(Ordering::Acquire);
    let mut buffer = self.buffer.get();

    // Calculate the length of the queue.
    let len = b.wrapping_sub(f);

    // Is the queue full?
    if len >= buffer.cap as WorkerIndex {
        // Yes. Grow the underlying buffer.
        unsafe {
            self.resize(2 * buffer.cap);
        }
        buffer = self.buffer.get();
    }

    // Write `task` into the slot.
    unsafe {
        buffer.write(b, MaybeUninit::new(task));
    }

    // ThreadSanitizer does not understand fences, so we omit fence and do store with Release ordering.
    #[cfg(not(crossbeam_sanitize_thread))]
    atomic::fence(Ordering::Release);
    let store_order = if cfg!(crossbeam_sanitize_thread) {
        Ordering::Release
    } else {
        Ordering::Relaxed
    };

    // Increment the back index.
    self.inner.back.store(b.wrapping_add(1), store_order);
}

• back 用 Relaxed 读：只有主人自己写它。
• front 用 Acquire 读：要用它判断槽位能不能复用。窃取者先读槽、再 CAS front（SeqCst，包含 Release）。主人 Acquire 读到推进后的 front，就保证窃取者对那个槽的读已经完成，buffer 绕回来写同一个槽时不会覆盖还没读走的任务。
• 写完槽位，「Release fence + Relaxed 写 back」把任务发布出去，和窃取者 Acquire 读 back 配对。这里原来是直接 store(Release)，注释说 Relaxed 就够、用 Release 只是为了不让 TSan 误报；2026 年 2 月 00e8420b（「deque: Use relaxed store after release fence」，0.8.7 的 CHANGELOG 里对应的应是 #1233「Optimize Worker::push, Stealer::steal_batch*, Injector::steal_batch*」：0.8.6 到 0.8.7 之间 deque 只有这一个改代码的提交，改动范围也正是这几个方法）改成现在这样：正常编译走「fence + Relaxed」，crossbeam_sanitize_thread 下才用 Release 写。

steal

第 656 行：

pub fn steal(&self) -> Steal<T> {
    // Load the front index.
    let f = self.inner.front.load(Ordering::Acquire);

    // A SeqCst fence is needed here.
    //
    // If the current thread is already pinned (reentrantly), we must manually issue the
    // fence. Otherwise, the following pinning will issue the fence anyway, so we don't
    // have to.
    if epoch::is_pinned() {
        atomic::fence(Ordering::SeqCst);
    }

    let guard = &epoch::pin();

    // Load the back index.
    let b = self.inner.back.load(Ordering::Acquire);

    // Is the queue empty?
    if b.wrapping_sub(f) <= 0 {
        return Steal::Empty;
    }

    // Load the buffer and read the task at the front.
    let buffer = self.inner.buffer.load(Ordering::Acquire, guard);
    let task = unsafe { buffer.deref().read(f) };

    // Try incrementing the front index to steal the task.
    // If the buffer has been swapped or the increment fails, we retry.
    if self.inner.buffer.load(Ordering::Acquire, guard) != buffer
        || self
            .inner
            .front
            .compare_exchange(f, f.wrapping_add(1), Ordering::SeqCst, Ordering::Relaxed)
            .is_err()
    {
        // We didn't steal this task, forget it.
        return Steal::Retry;
    }

    // Return the stolen task.
    Steal::Success(unsafe { task.assume_init() })
}

五步：读 front → SeqCst fence → 读 back → 读 buffer 和槽 → 校验 buffer 没换、CAS front。

1. fence 借用 pin 的。 epoch::pin() 在第一次钉住时本来就要执行一道 SeqCst fence（pin 与 Guard），steal 正好需要「读 front 和读 back 之间」有一道，所以把 pin 放在两次读之间。如果线程已经钉住（比如在 epoch 的临界区里调用 steal），重入的 pin 只加计数、不执行 fence，于是要手动补一道。这就是 is_pinned() 那个分支。
2. 为什么要 pin。 读到的 buffer 可能下一刻就被主人换掉；pin 住保证旧 buffer 在本次 steal 结束前不会被释放。
3. 先读后认领。 任务是在 CAS 之前读出来的，读到的是一份按位拷贝（MaybeUninit<T>）。CAS 失败就当没读过（直接丢掉 MaybeUninit，不会 drop 里面的 T），返回 Retry。这一步的读和主人的写可能并发，源码注释承认这「技术上是 UB」，扩容与回收细讲。
4. 校验 buffer 没换。 CAS 之前再读一次 inner.buffer，和刚才用来读槽的不是同一个就 Retry。这是 2021 年 #726（「Fix deque steal race condition」，提交 38c07fcf）加上的；修复随 0.8.1 和 0.7.4 发布，之前的 0.7.1–0.7.3 和 0.8.0 被 yank，CHANGELOG 指向安全公告 GHSA-pqqp-xmhj-wgcw。
5. CAS 失败返回 Retry，不是 Empty。 队列里有东西，只是这一次和别人撞了。调用方必须重试，Steal、Retry 与批量窃取用实验说明把它当 Empty 会怎样。

#726 给六处「读槽之后的 CAS」中的五处加了 buffer 校验。steal_batch_with_limit_and_pop 在源队列是 LIFO 时的第一个 CAS（第 1098 行）当时没有加，0.8.8 里也没有；它后面循环里的 CAS 有。这处差异是否构成问题，本卷没有做进一步论证，只记下这个事实。

pop

第 465 行。先用两次 Relaxed 读算长度，空了直接返回 None；然后按 flavor 分两条路。

LIFO：和窃取者抢最后一个

// Decrement the back index.
let b = b.wrapping_sub(1);
self.inner.back.store(b, Ordering::Relaxed);

atomic::fence(Ordering::SeqCst);

// Load the front index.
let f = self.inner.front.load(Ordering::Relaxed);

// Compute the length after the back index was decremented.
let len = b.wrapping_sub(f);

if len < 0 {
    // The queue is empty. Restore the back index to the original task.
    self.inner.back.store(b.wrapping_add(1), Ordering::Relaxed);
    None
} else {
    // Read the task to be popped.
    let buffer = self.buffer.get();
    let mut task = unsafe { Some(buffer.read(b)) };

    // Are we popping the last task from the queue?
    if len == 0 {
        // Try incrementing the front index.
        if self
            .inner
            .front
            .compare_exchange(
                f,
                f.wrapping_add(1),
                Ordering::SeqCst,
                Ordering::Relaxed,
            )
            .is_err()
        {
            // Failed. We didn't pop anything. Reset to `None`.
            task.take();
        }

        // Restore the back index to the original task.
        self.inner.back.store(b.wrapping_add(1), Ordering::Relaxed);
    } else {
        // Shrink the buffer if `len` is less than one fourth of the capacity.
        if buffer.cap > MIN_CAP && len < buffer.cap as WorkerIndex / 4 {
            unsafe {
                self.resize(buffer.cap / 2);
            }
        }
    }

    task.map(|t| unsafe { t.assume_init() })
}

（第 505–558 行）

这是 Chase-Lev 最精巧的一段。主人先把 back 减一，宣布「这个任务我要了」，再看 front：

• len > 0：减完以后还剩任务，窃取者够不着 b 这个位置（它们只取 front，而 front < b），直接拿走，不需要 CAS。
• len == 0：这是最后一个，窃取者可能也盯着它。双方都在 front 上做 CAS（f → f + 1），只有一方成功。主人不管输赢都把 back 恢复成 b + 1：赢了，front 和 back 都等于 b + 1，队列为空；输了，任务归窃取者，同样为空。
• len < 0：减之前队列就被偷空了，恢复 back。

「back 减一」和「读 front」之间那道 SeqCst fence 是整个算法的关键，它和 steal 里「读 front」和「读 back」之间的 fence 配对，防的是经典的 store-buffer 重排：

没有这两道 fence，可能出现「主人读到旧的 front，窃取者读到旧的 back」：主人以为 len > 0，不做 CAS 就拿走 b；窃取者以为 b 还在队列里，CAS front 成功也拿走 b。同一个任务被取了两次。两道 SeqCst fence 在全局顺序里有先后，后执行 fence 的一方一定能看到对方 fence 之前的写，于是两边至少有一方看到「只剩一个」，走到 CAS 上去裁决。实验 E5 用 loom 把这个交错找了出来。

len > 0 时可能顺便缩容：长度不到容量四分之一、容量大于 MIN_CAP = 64 时减半。

FIFO：和窃取者在同一端

// Try incrementing the front index to pop the task.
let f = self.inner.front.fetch_add(1, Ordering::SeqCst);
let new_f = f.wrapping_add(1);

if b.wrapping_sub(new_f) < 0 {
    self.inner.front.store(f, Ordering::Relaxed);
    return None;
}

（第 480–501 行）

FIFO 的主人和窃取者都从 front 取。主人不用 CAS，直接 fetch_add：fetch_add 不会失败，加完一看越界了（被偷空），再把 front 写回去。写回只发生在队列已经空了的时候（back <= f）：这时窃取者要么读到 back - front <= 0 返回 Empty，要么拿着更早读到的 front 去 CAS，因为 front 已经变过而失败。

每个 Ordering 在和谁配对

整个文件里有 11 处 fence(SeqCst)：LIFO pop 一处，Stealer 的 is_empty / len 各一处，三个窃取方法里「已钉住时补 fence」各一处，两个从 LIFO 源批量窃取的循环里各一处，Injector 的三个窃取方法各一处。本库里的内存序把它们和 epoch 的那几道归在同一类。

is_empty 和 len

Worker::is_empty / len 读 back（Relaxed，自己写的）和 front（SeqCst）；Stealer 的版本是「front Acquire → fence(SeqCst) → back Acquire」，和 steal 的前半段一样。两者都只是一个瞬间的快照，并发时随时可能过期；len 对负数取 max(0)。Stealer::len 是 0.8.1 加的（#708）。

实验 E5：用 loom 检查那两道 fence

断言：LIFO pop 和 steal 各自的 SeqCst fence 缺一不可；完整的协议下，任何交错都不会把同一个任务取两次，也不会丢任务。

方法（exp-crossbeam/loom-chase-lev/tests/chase_lev.rs）：crossbeam-deque 不能在 loom 下编译，所以用 loom 的原子类型照 0.8.8 的 LIFO pop 和 steal 抄一个容量固定为 4 的版本（不扩容、不用 epoch；槽位用 Relaxed 的原子读写，只模拟 front / back 的协议）。场景：主人先 push 1、2，然后一个窃取者线程连续 steal 两次，同时主人 pop 一次；join 之后主人把剩下的 pop 干净。断言所有取出的值排序后正好是 [1, 2]。三个变体，loom 不限抢占次数：

两个失败都是同一个任务 2 被取了两次。loom 只报告断言失败，没有打印交错；能产生这个结果的交错就是上面那张表说的（按结果推出）：窃取者先偷走 1（front 变成 1），再读到旧的 back = 2，以为 2 还在，CAS front 1 → 2 成功；主人把 back 写成 1 后读到旧的 front = 0，算出 len = 1 > 0，不做 CAS 直接拿走 2。

反向验证：完整版本 65 个交错全部通过，两个去掉 fence 的版本都失败，说明这个模型足以区分有无 fence，也说明 loom 0.7.2 确实模拟了 SeqCst fence 的语义（否则完整版本也会失败）。规划阶段的 exp-crossbeam/survey/tests/loom_mp.rs 是一个更小的消息传递模板（Release / Acquire 通过、Relaxed / Relaxed 被抓到），可以当作 loom 本身的对照。

这个模型没有覆盖扩容、FIFO flavor、批量窃取，也没有覆盖 volatile 槽访问；它只说明 front / back 上的那套协议需要这两道 fence。

小结

• Inner 是 front、back 两个只增的有符号下标（0.8.8 起在有 64 位原子的平台上是 i64）加一个可以整体替换的 Atomic<Buffer>。Worker 单主人（!Sync），自己缓存 buffer；Stealer 可克隆、可共享。
• push 写槽、Release fence、Relaxed 写 back；front 用 Acquire 读，保证复用槽位前窃取者已经读完。
• steal：读 front → SeqCst fence（借 pin 的）→ 读 back → 读槽 → 校验 buffer 没换并 CAS front；失败返回 Retry。buffer 校验是 #726 修安全问题时加的。
• LIFO pop 先把 back 减一、SeqCst fence、再读 front，只有最后一个任务才和窃取者在 front 上 CAS 裁决；FIFO pop 直接 fetch_add front。
• loom 实验：完整协议 65 个交错全部通过，去掉 pop 或 steal 任一侧的 SeqCst fence，第一个交错就取出了 [1, 2, 2]。