扩容与回收

主线位置：任务主线里「push 发现满了」的分支。主人分配一块两倍大的新 buffer，把 [front, back) 复制过去，原子地换掉 inner.buffer，旧 buffer 交给 epoch 等所有可能还在读它的窃取者离开后再释放。

sequenceDiagram
  participant W as 主人（push）
  participant I as inner.buffer
  participant S as 窃取者（steal）
  participant E as epoch
  S->>S: pin
  S->>I: load(Acquire) 得到旧 buffer B1
  W->>W: 分配 B2（容量翻倍），复制 [front, back)
  W->>W: pin
  W->>I: swap(B2, Release)，拿到 B1
  W->>E: defer_unchecked(释放 B1)；B2 不小于 1 KiB 时 flush
  S->>S: 从 B1 读槽（B1 仍有效，因为 S 钉着）
  S->>I: 再 load 一次：已是 B2，与 B1 不同
  S->>S: 返回 Retry，unpin
  E->>E: 纪元前进两步后释放 B1

Buffer

struct Buffer<T> {
    /// Pointer to the allocated memory.
    ptr: *mut T,

    /// Capacity of the buffer. Always a power of two.
    cap: usize,
}

（第 48 行）

Buffer 是 Copy 的，只是「指针 + 容量」，drop 它不会释放内存，释放要显式调 dealloc。分配是 (0..cap).map(|_| MaybeUninit::uninit()).collect::<Box<[_]>>()，再取裸指针（第 60 行）；原来是 Vec::with_capacity 加 ManuallyDrop、释放时 Vec::from_raw_parts(ptr, 0, cap)，2024 年 5a15fc28（「More correct buffer allocation」）改成经过 Box<[MaybeUninit<T>]> 分配和释放。

inner.buffer 是 Atomic<Buffer<T>>：存的是指向一个堆上 Buffer 结构体的指针，Buffer 再指向槽数组。所以一个 buffer 有两次分配，换 buffer 时换的是外层那个指针。主人自己另存一份 Buffer 值在 Worker.buffer: Cell<Buffer<T>> 里，读它不需要原子操作。

什么时候换 buffer

容量从 MIN_CAP = 64 起，永远是 2 的幂，缩容不会低于 64。FIFO 的 len 是 pop 之前的长度、比较用 <=，LIFO 的 len 是 back 减一之后的长度、比较用 <，两者算的是同一个条件：pop 之后剩下的不到四分之一。

reserve 原来是「不够就翻倍，直到够」的循环，2026 年 9 月的 #1216（a0e4d292）改成一次 next_power_of_two。

resize

第 309 行：

#[cold]
unsafe fn resize(&self, new_cap: usize) {
    // Load the back index, front index, and buffer.
    let b = self.inner.back.load(Ordering::Relaxed);
    let f = self.inner.front.load(Ordering::Relaxed);
    let buffer = self.buffer.get();

    // Allocate a new buffer and copy data from the old buffer to the new one.
    let new = Buffer::alloc(new_cap);
    let mut i = f;
    while i != b {
        ptr::copy_nonoverlapping(buffer.at(i), new.at(i), 1);
        i = i.wrapping_add(1);
    }

    let guard = &epoch::pin();

    // Replace the old buffer with the new one.
    self.buffer.replace(new);
    let old =
        self.inner
            .buffer
            .swap(Owned::new(new).into_shared(guard), Ordering::Release, guard);

    // Destroy the old buffer later.
    guard.defer_unchecked(move || old.into_owned().into_box().dealloc());

    // If the buffer is very large, then flush the thread-local garbage in order to deallocate
    // it as soon as possible.
    if mem::size_of::<T>() * new_cap >= FLUSH_THRESHOLD_BYTES {
        guard.flush();
    }
}

几处值得注意：

• 按原下标复制。 第 i 个任务在旧 buffer 的 i & (cap - 1)，复制到新 buffer 的 i & (2cap - 1)，front、back 都不用改。窃取者手里的 f 换到新 buffer 上依然有效。
• front 用 Relaxed 读。 复制期间窃取者还在偷，front 随时在涨。多复制几个已经被偷走的任务没关系：它们落在新的 front 之前，永远不会被读到，也不会被 drop（槽是 MaybeUninit）。
• swap 用 Release。 和窃取者 buffer.load(Acquire) 配对：窃取者看到新 buffer 时，复制进去的任务一定已经写好。
• 旧 buffer 交给 epoch。 闭包只捕获一个 Shared（一个字），放得进 Deferred 的内联存储（defer 与回收）。窃取者每次 steal 都 pin 着读 buffer，所以旧 buffer 至少要等它们都离开才会被释放。
• #[cold]：扩容是低频路径，提示编译器把它放到冷路径上。

不小于 1 KiB 就 flush

FLUSH_THRESHOLD_BYTES = 1 << 10（第 42 行）。注意条件用的是新 buffer 的大小 size_of::<T>() * new_cap。

不 flush 的话，旧 buffer 的析构闭包只是进了本线程的袋子，要等袋子攒满 64 个才会进全局队列；而一个 deque 的主人很少 defer 别的东西，袋子可能很久都攒不满。flush 让它立刻进全局队列，之后任何线程的 collect 都能执行它。flush 并不能让它「立刻释放」：仍然要等纪元前进两步，如果有线程长期钉住，照样释放不了（defer 与回收 的 E3 量过这种情况）。

按这个阈值，u64 的 deque 从 64 扩到 128 时（128 × 8 = 1024 字节）就开始每次扩容都 flush；rayon 的任务类型 JobRef 是两个字（一个数据指针加一个函数指针，rayon-core/src/job.rs 第 33 行），16 字节，第一次扩容到 128 就是 2 KiB，也就是说 rayon 的每一次 deque 扩容都会 flush。

扩容和窃取的竞争

窃取者读槽用的是自己 load 到的那个 buffer。扩容可能恰好发生在「窃取者读完 buffer 指针」和「CAS front」之间，于是它是从旧 buffer 里读的任务。steal 在 CAS 之前再 load 一次 inner.buffer，变了就返回 Retry（Chase-Lev 双端队列）。这个检查是 2021 年 #726 修安全问题时加上的。

技术上的 UB：volatile 读写

/// Writes `task` into the specified `index`.
///
/// This method might be concurrently called with another `read` at the same index, which is
/// technically speaking a data race and therefore UB. We should use an atomic store here, but
/// that would be more expensive and difficult to implement generically for all types `T`.
/// Hence, as a hack, we use a volatile write instead.
unsafe fn write(&self, index: WorkerIndex, task: MaybeUninit<T>) {
    ptr::write_volatile(self.at(index).cast::<MaybeUninit<T>>(), task)
}

/// Reads a task from the specified `index`.
///
/// This method might be concurrently called with another `write` at the same index, which is
/// technically speaking a data race and therefore UB. We should use an atomic load here, but
/// that would be more expensive and difficult to implement generically for all types `T`.
/// Hence, as a hack, we use a volatile load instead.
unsafe fn read(&self, index: WorkerIndex) -> MaybeUninit<T> {
    ptr::read_volatile(self.at(index).cast::<MaybeUninit<T>>())
}

（第 90–108 行）

什么时候会并发读写同一个槽。 窃取者读到 front = f，还没 CAS 就被调度走了。这期间别的窃取者把 front 推过了 f，主人继续 push，绕了一圈写到下标 f + cap，和 f 是同一个槽。被调度走的窃取者回来读这个槽，就和主人的写并发了。它读到的东西可能是旧任务、新任务、或者两者混杂的字节，但接下来它的 CAS（期望 front == f）一定失败，读到的 MaybeUninit<T> 直接丢弃，不会被当成 T 使用，也不会被 drop。

为什么还是 UB。 Rust（沿用 C++）的内存模型里，两个线程对同一位置的非原子访问、至少一个是写、没有 happens-before 关系，就是数据竞争，数据竞争是未定义行为，不管读到的值用不用。volatile 只是告诉编译器「这次访问不能省、不能合并」，不改变它是非原子访问这一事实。理想的做法是逐字节的原子读写（任意 T 都能用），但 Rust 没有稳定的这种 API。

这段注释的来历。 2018 年 11 月 20 日 4cbbb7fb（「document technical UB」）第一次加上，那时的措辞是：「Using this concurrently with another read or write is technically speaking UB due to data races. We should be using relaxed accesses, but that would cost too much performance. Hence, as a HACK, we use volatile accesses instead. Experimental evidence shows that this works.」现在的版本把理由从「太慢」改成了「更贵，而且难以对所有 T 通用地实现」，删掉了「实验证据表明可行」这一句。

验证工具怎么对待它：

也就是说，Miri 在允许抢占时能抓到这个竞争，CI 选择关掉抢占让测试通过。这是本库里少有的、维护者明确知道并保留的 UB，设计取舍一章把它和「快、对任意 T 通用」放在一起讨论。

上游仓库里有两条想消除它的分支，都没有合并进 main：一条最后一次提交在 2022 年 2 月，标题是「Use byte-wise atomic memcpy in deque and seqlock」；另一条在 2026 年 2 月，标题是「Use atomic-maybe-uninit's atomic memcpy API」。它们会不会进入发布版，本卷不做推测。

tokio 的本地队列没有这个问题：它的 buffer 固定不换，窃取用两段式认领（先推 real 认领、拷完再推 steal 释放），主人按 steal 算容量，保证不会写进还没拷完的槽（tokio 卷：本地队列）。代价是 tokio 的 steal 要两次 CAS，而且队列不能增长。

小结

• Buffer 是「指针 + 容量」的 Copy 值；inner.buffer 是指向堆上 Buffer 的 Atomic，主人另存一份在 Cell 里。
• 满了翻倍；批量窃取前按需 next_power_of_two；pop 后剩下不到四分之一就减半，但不低于 64。
• resize 按原下标复制 [front, back)，swap(Release) 换上新 buffer，旧的交给 defer_unchecked；新 buffer 不小于 1 KiB 就 flush。rayon 的 JobRef 是 16 字节，它的每次扩容都会 flush。
• 槽位的读写是 volatile 的非原子访问，可能和另一线程的写并发：读到的值在 CAS 失败后被丢弃，但按内存模型仍是数据竞争。源码注释、TSan 抑制文件、Miri 配置（-Zmiri-preemption-rate=0）都明确承认这一点；用原子 memcpy 替换的分支没有合并。