list：无界块链表

主线位置：一条消息的另一种走法。unbounded() 的 send 永远不阻塞：抢一个序号、写进当前块的槽；recv 和 array 一样，空了先自旋，再交给 Context 与 Waker 去 park。

flowchart TB
  ss["start_send：读 tail.index 和 tail.block"] --> off{"offset = (tail >> 1) % 32"}
  off -->|"== 31：块尾，下一块还没装好"| sn["snooze，重读"]
  sn --> ss
  off -->|"== 30：最后一个槽"| pre["提前分配下一块"]
  off --> nul{"block 为空？"}
  pre --> nul
  nul -->|"第一条消息"| first["CAS 装第一块，同时写 head.block"]
  nul --> cas["CAS tail.index + 2"]
  first --> cas
  cas -->|"成功且是最后一个槽"| inst["装下一块：tail.block、tail.index 再 +2、block.next"]
  cas -->|成功| w["write：写消息，state |= WRITE，notify"]
  inst --> w
  cas -->|失败| ss

常量与编码

list.rs 开头：

// Bits indicating the state of a slot:
// * If a message has been written into the slot, `WRITE` is set.
// * If a message has been read from the slot, `READ` is set.
// * If the block is being destroyed, `DESTROY` is set.
const WRITE: usize = 1;
const READ: usize = 2;
const DESTROY: usize = 4;

// Each block covers one "lap" of indices.
const LAP: Index = 32;
// The maximum number of messages a block can hold.
const BLOCK_CAP: usize = LAP as usize - 1;
// How many lower bits are reserved for metadata.
const SHIFT: usize = 1;
// Has two different purposes:
// * If set in head, indicates that the block is not the last one.
// * If set in tail, indicates that the channel is disconnected.
const MARK_BIT: Index = 1;

一圈 32 个序号，块里只有 31 个槽：第 32 个序号（offset == BLOCK_CAP）不对应任何槽，它表示「这一块用完了，下一块正在装」。谁拿到第 31 个槽（offset + 1 == BLOCK_CAP），谁负责把下一块挂上去；在它挂好之前，别的发送方算出 offset == 31，就 snooze 等着。这样「换块」不需要额外的锁，用序号本身就把装块的人和等块的人分开了。

索引的最低位是元数据（SHIFT = 1），所以序号每次加 1 << SHIFT = 2。这一位在两个索引上意思不同：

head.index 上的这个优化值得一提：接收方每次要判断空不空，就得 fence(SeqCst) 再读 tail，碰的是发送方那条热缓存行。只要知道后面还有块，就一定不空，可以省掉这一步。start_recv 在 new_head & MARK_BIT == 0 时才去读 tail，读完如果发现 head 和 tail 不在同一块，就把 MARK_BIT 置进新的 head。

数据结构

struct Slot<T> {
    msg: UnsafeCell<MaybeUninit<T>>,
    state: AtomicUsize,
}

struct Block<T> {
    next: AtomicPtr<Block<T>>,
    slots: [Slot<T>; BLOCK_CAP],
}

struct Position<T> {
    index: AtomicIndex,
    block: AtomicPtr<Block<T>>,
}

pub(crate) struct Channel<T> {
    head: CachePadded<Position<T>>,
    tail: CachePadded<Position<T>>,
    receivers: SyncWaker,
    _marker: PhantomData<T>,
}

（Slot、Block、Channel。）

只有一个 SyncWaker：无界 channel 的发送方永远不等。Position 把序号和块指针放在一起，head / tail 各占一条缓存行。usize 在 64 位平台上，一个 Block<usize> 是 8 + 31 × 16 = 504 字节。

第一块懒分配，下一块提前分配

Channel::new 不分配任何块，head.block、tail.block 都是空指针。start_send 发现 block.is_null() 时自己分配一块，CAS 进 tail.block；成功的那个顺手写 head.block，失败的把刚分配的块留到 next_block 里备用，下次装下一块时用。所以一个从没发过消息的 unbounded() 只占 Counter 那一次分配。

拿到倒数第二个序号（offset + 1 == BLOCK_CAP）的发送方，在 CAS 之前就 Block::new() 分配好下一块，CAS 成功后三步装上：

if offset + 1 == BLOCK_CAP {
    let next_block = Box::into_raw(next_block.unwrap());
    self.tail.block.store(next_block, Ordering::Release);
    self.tail.index.fetch_add(1 << SHIFT, Ordering::Release);
    (*block).next.store(next_block, Ordering::Release);
}

先换 tail.block，再把 tail.index 从块尾的「空序号」推到下一块的 0 号，其他在 offset == 31 上 snooze 的发送方这时才能继续；最后接上 next，接收方读到块尾时要 wait_next 等它。分配提前做，是为了让别人等的这段时间尽量短（注释原话「make the wait for other threads as short as possible」）。

Block::new 直接在堆上建（#1146 / #1147）

0.5.14 之前，Block::new 是 Box::new(unsafe { MaybeUninit::zeroed().assume_init() })：先在栈上造一个全零的 Block，再搬进堆。T 很大时（比如几百 KB 的数组），31 个槽的块在栈上就放不下，线程栈溢出。#1146 改成 alloc_zeroed 直接在堆上分配，#1147 补上分配失败时调 handle_alloc_error（list.rs:98）。源码里还留着一行 // TODO: unsafe { Box::new_zeroed().assume_init() }：Box::new_zeroed 稳定得晚，超出 crossbeam 的 MSRV。std 的移植版直接用了 Box::new_zeroed。同样的改动后来搬到了 deque 的 Injector（见 Injector）和 SegQueue。

谁释放块

没有 epoch，也没有引用计数。规则写在 read 和 Block::destroy 里：

// read：
slot.wait_write();
let msg = slot.msg.get().read().assume_init();

// Destroy the block if we've reached the end, or if another thread wanted to destroy but
// couldn't because we were busy reading from the slot.
if offset + 1 == BLOCK_CAP {
    Block::destroy(block, 0);
} else if slot.state.fetch_or(READ, Ordering::AcqRel) & DESTROY != 0 {
    Block::destroy(block, offset + 1);
}

unsafe fn destroy(this: *mut Block<T>, start: usize) {
    // It is not necessary to set the `DESTROY` bit in the last slot because that slot has
    // begun destruction of the block.
    for i in start..BLOCK_CAP - 1 {
        let slot = (*this).slots.get_unchecked(i);

        // Mark the `DESTROY` bit if a thread is still using the slot.
        if slot.state.load(Ordering::Acquire) & READ == 0
            && slot.state.fetch_or(DESTROY, Ordering::AcqRel) & READ == 0
        {
            // If a thread is still using the slot, it will continue destruction of the block.
            return;
        }
    }

    // No thread is using the block, now it is safe to destroy it.
    drop(Box::from_raw(this));
}

多个接收方可以同时读同一块的不同槽，读完最后一个槽的人不一定是最后一个离开这一块的人。协议是接力：

1. 读到最后一个槽（offset == 30）的接收方发起 destroy(block, 0)，从槽 0 往后检查。
2. 某个槽还没有 READ 位，说明有人还在读它：给它置 DESTROY 位，自己走人。
3. 那个慢读者读完，fetch_or(READ) 看到 DESTROY，接过来，从下一个槽 offset + 1 继续检查。
4. 一路检查到底都已读完，Box::from_raw 释放。

READ 和 DESTROY 都用 fetch_or 设置，两个线程对同一个槽各 fetch_or 一次，必有一方看到另一方的位，所以接力不会断，也不会两个人都去释放。

发送方等写入用 Slot::wait_write：接收方抢到了序号，但发送方可能还没写完（发送方 CAS 了 tail.index，还没执行到 state |= WRITE），接收方就 snooze 等 WRITE 位。这和 array 的「其他」分支是同一个问题：抢序号和写数据是两步。

sequenceDiagram
  participant A as 接收方 A（槽 30）
  participant B as 接收方 B（槽 5，慢）
  participant K as Block
  A->>K: 读完槽 30，destroy(block, 0)
  A->>K: 槽 0..4 都有 READ
  A->>K: 槽 5 没有 READ：fetch_or(DESTROY)，返回
  B->>K: 读完槽 5，fetch_or(READ) 看到 DESTROY
  B->>K: destroy(block, 6)：槽 6..29 都有 READ
  B->>K: Box::from_raw 释放

接收端全走：立即丢弃

disconnect_receivers 给 tail.index 置 MARK_BIT，第一次置上的人调 discard_all_messages，把 head 到 tail 之间的消息全部析构、块全部释放。这是 2021 年的 49188f7e「channel: discard messages eagerly」加的：接收端都没了，留着消息没有意义，早点释放内存。E8 的结果（list 在接收端 drop 时就析构了 10 条）见 array。

discard_all_messages 开头先等 tail 不停在块尾：如果某个发送方正好拿到了块尾的空序号、在装下一块，置了 MARK_BIT 以后它的 CAS 会失败，但装块的那一步已经在路上，要等它的 fetch_add 落地，否则新块会泄漏。

一段事故史：0.5.12 到 0.5.14

这个函数附近出过一串问题，CHANGELOG 里能看到 0.5.12、0.5.13、0.5.14 三个版本都被 yank：

0.5.13（select_biased!）和 0.5.14（Select::new_biased、#1146 / #1147、去掉 wait_until 的乐观自旋）的功能都在被 yank 的版本里，0.5.15 只修了这一个 bug，相当于把它们重新放出来。本站锁的就是 0.5.15。

Drop 只析构写过的槽（#1295）

Drop for Channel 遍历 head 到 tail，析构每个槽里的消息。0.5.17 加了一个检查：

let slot = (*block).slots.get_unchecked_mut(offset);
if *slot.state.get_mut() & WRITE != 0 {
    (*slot.msg.get()).assume_init_drop();
}

select! 的发送分支先 start_send 预订一个槽（tail 已经前进了），再把 SelectedOperation 交给调用方去 send。调用方如果 mem::forget 了这个 SelectedOperation，槽被预订了却永远没写，Drop 以前会对一块未初始化内存调析构：UB。mem::forget 是安全函数，所以这是安全代码能触发的 UB。

0.5.17 的提交（2cadbaef，CHANGELOG 记作 #1295）改的就是 list.rs 这四行：Drop 只析构带 WRITE 位的槽。

和 tokio mpsc 的块对照

tokio 的 mpsc 也是块链表（见 tokio 卷 mpsc），同一个思路，细节不同：

fetch_add 能用，是因为 tokio 的序号不需要和块边界协调：块尾的空洞由 ready_slots 的位标记处理。crossbeam 用 CAS 换来了「块尾序号」这个协调点。两边吞吐在本机的对比见 compare。

小结

• list 是 31 槽一块的单链表；每圈 32 个序号，第 32 个是「块尾」，拿到倒数第二个槽的发送方负责提前分配并装上下一块，别人在块尾上 snooze。
• 序号最低位是标志：在 tail 上表示断开，在 head 上表示「后面还有块」，可以跳过读 tail 的空判断。
• 第一块懒分配；Block::new 自 0.5.14 起直接 alloc_zeroed 在堆上建，避免大 T 栈溢出。
• 块的释放靠槽上的 READ / DESTROY 两个位接力：读完最后一个槽的人发起，遇到还在读的槽就把任务交给它。
• 最后一个接收端 drop 时 discard_all_messages 立即析构剩余消息；这个函数在 0.5.12 修泄漏时引入了双重释放，0.5.12–0.5.14 全部 yank，0.5.15（本站锁的版本）修复。
• 0.5.17 的 Drop 只析构带 WRITE 位的槽，修了「泄漏 SelectedOperation 导致析构未初始化内存」的 UB。