WordLock:停车场自己的锁
主线位置:主线 1、2、3 的每一次
lock_bucket都锁的是它。lock:一次0 → LOCKED的 CAS,失败进lock_slow:能抢就抢,没人排队就自旋,否则把自己的ThreadData推到队列头再睡。unlock:fetch_sub(LOCKED),有人排队且队列锁空着才进unlock_slow:拿队列锁、补全prev指针、摘下队尾、叫醒。
flowchart LR
subgraph word["state: usize"]
q["高位:队列头 ThreadData 指针"]
ql["bit 1:QUEUE_LOCKED"]
l["bit 0:LOCKED"]
end
q --> h["头:最新入队(只有 next)"]
h -->|"next"| m["……"]
m -->|"next"| t["尾:最早入队,下一个被叫醒"]
t -.->|"prev(解锁方补上)"| m
h -.->|"queue_tail:已处理部分的尾"| t
为什么桶锁要自己管队列
停车场的每个桶都要一把锁来保护链表。这把锁不能用停车场实现——停车本身就要先锁桶。用 std 的 Mutex 也不行:parking_lot_core 要支持的平台更多,而且 std 的锁在 macOS 上是堆分配的 pthread mutex,每个桶都带一个就失去了「桶很小」的意义。所以 WordLock 自己管等待队列:一个 usize 状态,等待的线程直接把自己线程局部的 ThreadData 串成链表,链表头的地址就存在状态字里。文件头的注释:「Word-sized lock that is used to implement the parking_lot API. Since this can't use parking_lot, it instead manages its own queue of waiting threads.」(word_lock.rs:74-78)
名字和 WebKit 的同类锁一样,但源码注释和提交说明都没有写出处,本卷不做推断。
状态字
const LOCKED_BIT: usize = 1;
const QUEUE_LOCKED_BIT: usize = 2;
const QUEUE_MASK: usize = !3;
低两位是标志,其余位是指向队列头 ThreadData 的指针。这要求 ThreadData 至少 4 字节对齐,ThreadData::new 里有一句 assert!(mem::align_of::<ThreadData>() > !QUEUE_MASK) 守着(第 39 行)。
| 位 | 含义 |
|---|---|
LOCKED_BIT | 锁被持有 |
QUEUE_LOCKED_BIT | 某个解锁方正在处理队列(补指针、摘线程),别的解锁方不要碰 |
| 其余位 | 队列头;为 0 表示没人在等 |
这是 WordLock 自己的 ThreadData(word_lock.rs:16-34),和停车场的 ThreadData 是两个类型:
struct ThreadData {
parker: ThreadParker,
// Linked list of threads in the queue. The queue is split into two parts:
// the processed part and the unprocessed part. When new nodes are added to
// the list, they only have the next pointer set, and queue_tail is null.
//
// Nodes are processed with the queue lock held, which consists of setting
// the prev pointer for each node and setting the queue_tail pointer on the
// first processed node of the list.
//
// This setup allows nodes to be added to the queue without a lock, while
// still allowing O(1) removal of nodes from the processed part of the list.
// The only cost is the O(n) processing, but this only needs to be done
// once for each node, and therefore isn't too expensive.
queue_tail: Cell<*const ThreadData>,
prev: Cell<*const ThreadData>,
next: Cell<*const ThreadData>,
}
注释把队列分成两段:未处理段(新入队的节点只设了 next,queue_tail 为 null)和已处理段(解锁方补好了 prev,并在已处理段的第一个节点上记了 queue_tail)。入队只需一次 CAS 把自己设成新的头,不用锁;出队要从尾部摘,需要 prev 指针,这些指针由拿着队列锁的解锁方顺手补上,每个节点只补一次。
ThreadData 放哪:IS_CHEAP_TO_CONSTRUCT
fn with_thread_data<T>(f: impl FnOnce(&ThreadData) -> T) -> T {
let mut thread_data_ptr = ptr::null();
// If ThreadData is expensive to construct, then we want to use a cached
// version in thread-local storage if possible.
if !ThreadParker::IS_CHEAP_TO_CONSTRUCT {
thread_local!(static THREAD_DATA: ThreadData = ThreadData::new());
if let Ok(tls_thread_data) = THREAD_DATA.try_with(|x| x as *const ThreadData) {
thread_data_ptr = tls_thread_data;
}
}
// Otherwise just create a ThreadData on the stack
let mut thread_data_storage = None;
if thread_data_ptr.is_null() {
thread_data_ptr = thread_data_storage.get_or_insert_with(ThreadData::new);
}
f(unsafe { &*thread_data_ptr })
}
ThreadParker 的构造代价决定放在哪。Linux 的 futex 版只是一个 AtomicI32,IS_CHEAP_TO_CONSTRUCT = true,每次等锁都在栈上新建一个,不碰线程局部存储;macOS 的 pthread 版要一对 pthread 对象(懒初始化),IS_CHEAP_TO_CONSTRUCT = false,放在线程局部存储里复用(ThreadParker 的各平台实现)。停车场的 ThreadData 则无论哪个平台都放在线程局部存储里,注释说它「总是很贵」——它要计入 NUM_THREADS、可能触发扩表。这个区分来自 8bcfae3「Create ThreadParker::IS_CHEAP_TO_CONSTRUCT」(2018-12)。
栈上的节点能被别的线程访问,是因为它的主人在被叫醒之前一直睡在 lock_slow 那个栈帧里;解锁方叫醒它之后就不再碰它(第 277–280 行的注释:「the thread is guaranteed to be sleeping right now and we are the only one who can wake it up」)。
lock:入队无锁
word_lock.rs:88-175,lock_slow 的结构和 RawMutex::lock_slow 一模一样:
- 锁空着就 CAS 抢,「即使有人在排队」。
- 队列为空时
SpinWait::spin(),最多 10 步。 - 否则把自己推到队列头:
state = with_thread_data(|thread_data| {
// ...
unsafe {
thread_data.parker.prepare_park();
}
// Add our thread to the front of the queue
let queue_head = state.queue_head();
if queue_head.is_null() {
thread_data.queue_tail.set(thread_data);
thread_data.prev.set(ptr::null());
} else {
thread_data.queue_tail.set(ptr::null());
thread_data.prev.set(ptr::null());
thread_data.next.set(queue_head);
}
if let Err(x) = self.state.compare_exchange_weak(
state,
state.with_queue_head(thread_data),
Ordering::AcqRel,
Ordering::Relaxed,
) {
return x;
}
// Sleep until we are woken up by an unlock
// ...
unsafe {
thread_data.parker.park();
}
// Loop back and try locking again
spinwait.reset();
self.state.load(Ordering::Relaxed)
});
队列为空时自己既是头也是尾,queue_tail 指向自己(直接就是「已处理」的);否则只设 next 指向旧头,queue_tail 留空。CAS 用 AcqRel:Release 让解锁方读到这里写的 next / queue_tail,Acquire 让入队者读到之前节点的状态。注意 WordLock 没有 validate:入队的 CAS 期望的是刚读到的 state(含 LOCKED_BIT),锁在这期间被放开,CAS 就失败、回去重抢,不会在空锁上睡着。
被叫醒后不是直接持有锁,而是回到循环开头重新抢,和 RawMutex 拿到 TOKEN_NORMAL 时一样,可能被插队。
unlock:补指针、从队尾叫醒
快路径(第 100–108 行):
pub unsafe fn unlock(&self) {
let state = self.state.fetch_sub(LOCKED_BIT, Ordering::Release);
if state.is_queue_locked() || state.queue_head().is_null() {
return;
}
self.unlock_slow();
}
先无条件放锁,再看要不要叫人:没人排队,或者别的解锁方已经拿着队列锁在处理了,就直接返回。unlock_slow 分三步:
- 拿队列锁:CAS 置
QUEUE_LOCKED_BIT。期间如果发现队列锁已被拿、或队列空了,返回。 - 补
prev指针:从队列头沿next往后走,给每个节点的下一个节点设prev,直到遇到一个queue_tail非空的节点(已处理段的开头),然后把找到的尾记到新的头上。 - 决定叫不叫:
- 锁又被人拿了(
state.is_locked()):叫醒也没用,放开队列锁就返回,「让下一个解锁方去叫」(第 226–243 行)。 - 否则摘下队尾(最早入队的线程):它的
prev为空说明它是唯一的节点,用 CAS 把状态里的队列头和队列锁一起清掉(只保留LOCKED_BIT);否则把头上的queue_tail改成新尾,fetch_and放开队列锁。最后unpark_lock().unpark()叫醒它。
- 锁又被人拿了(
入队在头、出队在尾,所以排队的线程按先来先醒的顺序被叫醒;但被叫醒后要和新来的线程一起抢,整体仍然不保证公平。
两处 CAS 失败后要重新读队列之前,代码调 fence_acquire(第 289–298 行):普通构建是 fence(Acquire),在 TSan 下换成一次丢弃结果的 Acquire 读,因为「TSan 对 fence 只有部分支持」。这一段来自 2021-08 的两个提交:6e3c66e「Fix Ordering on WordLock (tsan detected)」和 4fd88be「Detect and work around TSan's lack of support for fences」。
和 RawMutex 的对照
WordLock | RawMutex | |
|---|---|---|
| 大小 | 1 个字 | 1 字节 |
| 等待队列 | 状态字里的指针 + 侵入式双向链表 | 停车场的桶链表 |
| 入队 | 一次 CAS 推到队头,不加锁 | 锁桶后挂到桶链表尾 |
| 叫醒顺序 | 队尾(最早来的) | 桶链表里第一个同 key 的(最早来的) |
| 公平交接 | 没有,被叫醒者总是回去重抢 | 有,TOKEN_HANDOFF |
| 超时、回调 | 都没有 | park 的全部参数 |
WordLock 是一把「够用就好」的锁:桶锁的临界区只是改几个指针,持有时间极短,绝大多数时候 lock 的第一次 CAS 就成功,不需要公平或超时。
0.13 起不同:#533 中的 fb08e42「Fix WordLock queue unlock retries」重写了 unlock_slow 的重试循环,fbfe854 把状态改成 AtomicPtr(#499),见 07 0.13 的变化。
小结
- 桶锁不能用停车场实现自己,所以
WordLock在一个usize里放LOCKED、QUEUE_LOCKED两位和队列头指针。 - 等待节点是线程的
ThreadData:futex 平台在栈上建(便宜),pthread 平台放线程局部存储(IS_CHEAP_TO_CONSTRUCT)。 - 入队一次 CAS 推到队头、只设
next;解锁方拿队列锁后补prev、从队尾叫醒最早来的线程。 - 锁被别人拿了就不叫醒,留给下一个解锁方;被叫醒者回去重抢,没有交接。