Rust in Everything
基于 parking_lot_core 0.9.12

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 的同类锁一样,但源码注释和提交说明都没有写出处,本卷不做推断。

状态字

word_lock.rs:70-72:

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

word_lock.rs:49-68:

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 一模一样:

  1. 锁空着就 CAS 抢,「即使有人在排队」。
  2. 队列为空时 SpinWait::spin(),最多 10 步。
  3. 否则把自己推到队列头:
            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 分三步:

  1. 拿队列锁:CAS 置 QUEUE_LOCKED_BIT。期间如果发现队列锁已被拿、或队列空了,返回。
  2. 补 prev 指针:从队列头沿 next 往后走,给每个节点的下一个节点设 prev,直到遇到一个 queue_tail 非空的节点(已处理段的开头),然后把找到的尾记到新的头上。
  3. 决定叫不叫:
    • 锁又被人拿了(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 的对照

WordLockRawMutex
大小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、从队尾叫醒最早来的线程。
  • 锁被别人拿了就不叫醒,留给下一个解锁方;被叫醒者回去重抢,没有交接。

💬 关联讨论

发起讨论
加载中...