死锁检测

主线位置：主线 3 和主线 4 的旁支。开了 deadlock_detection 后，主线 1 的每次 lock 之后多一次 acquire_resource(addr)，unlock 之前多一次 release_resource(addr)；用户线程调 check_deadlock() 时，遍历整张哈希表里正在停车的线程建等待图、找环。

flowchart LR
  subgraph g["等待图（只含正在停车、且不带超时的线程）"]
    ra["锁 A"] -->|"被持有"| t1["线程 1"]
    t1 -->|"等待（key）"| rb["锁 B"]
    rb -->|"被持有"| t2["线程 2"]
    t2 -->|"等待（key）"| ra
  end
  chk["check_deadlock()"] --> fast["快速检查：逐桶加锁建图，is_cyclic_directed"]
  fast -->|"有环"| slow["慢速检查：锁住整张表建图，DFS 找出每个环"]
  slow --> mark["环上每个线程：置 deadlocked，unpark"]
  mark --> bt["被叫醒的线程抓自己的 Backtrace 发回来，然后永久停车"]

怎么打开、怎么用

feature deadlock_detection，README 和 core 的文档都标着「Experimental」。它拉进两个依赖：petgraph（建图、找环）和 backtrace（抓栈）。

检测不会自己运行。parking_lot::deadlock 模块的文档示例是自己起一个后台线程，每 10 秒调一次 check_deadlock()（src/deadlock.rs:1-34）：

thread::spawn(move || {
    loop {
        thread::sleep(Duration::from_secs(10));
        let deadlocks = deadlock::check_deadlock();
        if deadlocks.is_empty() {
            continue;
        }

        println!("{} deadlocks detected", deadlocks.len());
        for (i, threads) in deadlocks.iter().enumerate() {
            println!("Deadlock #{}", i);
            for t in threads {
                println!("Thread Id {:#?}", t.thread_id());
                println!("{:#?}", t.backtrace());
            }
        }
    }
});

返回值是「自上次调用以来新发现的环」，每个环是一组 DeadlockedThread，带线程 id 和那个线程自己的调用栈。

记账：每个线程记自己持有什么

ThreadData 在这个 feature 下多一个 DeadlockData（parking_lot.rs:1180-1203）：本线程当前持有的资源 resources: Vec<usize>、deadlocked 标志、报栈用的 mpsc::Sender、线程 id。资源就是锁的地址：

    pub unsafe fn acquire_resource(key: usize) {
        with_thread_data(|thread_data| {
            (*thread_data.deadlock_data.resources.get()).push(key);
        });
    }

    pub unsafe fn release_resource(key: usize) {
        with_thread_data(|thread_data| {
            let resources = &mut (*thread_data.deadlock_data.resources.get());

            // There is only one situation where we can fail to find the
            // resource: we are currently running TLS destructors and our
            // ThreadData has already been freed. There isn't much we can do
            // about it at this point, so just ignore it.
            if let Some(p) = resources.iter().rposition(|x| *x == key) {
                resources.swap_remove(p);
            }
        });
    }

谁调它们：RawMutex 的每条成功加锁路径和两种解锁（raw_mutex.rs 第 74、91、101、122、157、174、327 行），Condvar 拿到 TOKEN_HANDOFF 时替 mutex 记一笔（condvar.rs:354），RawRwLock 的 deadlock_acquire / deadlock_release——一次记两个 key：addr 和 addr + 1（raw_rwlock.rs:1146-1157），因为 RwLock 有两条等待队列，写者等读者退出时睡在 addr + 1 上（状态字与两条队列），两条队列上的等待都要能连到持有者。ReentrantMutex 包的是 RawMutex，只有第一次加锁会经过这里。

两处值得注意：

• 文档与代码不一致。 release_resource 的公开文档写「Panics if the resource was already released or wasn't acquired in this thread」（parking_lot.rs:1117-1131），实现是找不到就静默忽略，注释解释是为 TLS 析构期间留的。以代码为准。
• 每个加过锁的线程都会创建 ThreadData。 acquire_resource 要经过 with_thread_data，所以开了这个 feature，一个线程只要加过一次锁（哪怕从没停过车）就计入 NUM_THREADS、可能推动哈希表扩容。停车场哈希表 的 E7 实测：扩容点从第 6、11、22、43 个停车线程提前到第 5、10、21、42 个（主线程加锁也算进去了）。

check_deadlock：两遍

parking_lot.rs:1244-1254：先 check_wait_graph_fast()，它说有环再 check_wait_graph_slow()。

快速检查（第 1256–1285 行）逐个桶加锁、遍历链表、放锁，用 petgraph 的 DiGraphMap<usize, ()> 建图，最后 is_cyclic_directed。对每个正在停车的线程加两类边：

• 它持有的每个资源 → 它（「这把锁在等它释放」）；
• 它 → 它正在等的 key（「它在等这把锁」）。

跳过两类线程：parked_with_timeout（带超时的等待）和已经 deadlocked 的。注释说这一遍「不精确」，因为它没有先锁住整张表。

慢速检查（第 1295–1381 行）先拿一把全局的 WordLock（同一时刻只有一个检查在跑），再按下标顺序锁住当前表的全部桶（锁完确认表没换，和 grow_hashtable 的写法相同），在静止的表上用同样的规则重建图，这次节点区分「线程」和「资源」两类，然后放开所有桶锁，DFS 找环（graph_cycles，第 1400–1426 行）：从每个线程节点出发，遇到回到路径上某个线程的回边，就把这一段路径记为一个环，环规范化成从最小节点开始后放进 HashSet 去重。

报告：让环上的线程自己抓栈

找到环之后（第 1360–1376 行），对环上的每个线程：锁它所在的桶，置 deadlocked = true，塞给它一个 Sender，unpark_lock，放桶锁，unpark。然后检查方在 Receiver 上收齐这个环上所有线程发回来的 DeadlockedThread。

被叫醒的线程在 park 返回前调 deadlock::on_unpark（只在不带超时的路径上调，park 与四种 unpark）：

    pub(super) unsafe fn on_unpark(td: &ThreadData) {
        if td.deadlock_data.deadlocked.get() {
            let sender = (*td.deadlock_data.backtrace_sender.get()).take().unwrap();
            sender
                .send(DeadlockedThread {
                    thread_id: td.deadlock_data.thread_id,
                    backtrace: Backtrace::new(),
                })
                .unwrap();
            // make sure to close this sender
            drop(sender);

            // park until the end of the time
            td.parker.prepare_park();
            td.parker.park();
            unreachable!("unparked deadlocked thread!");
        }
    }

栈是死锁线程自己抓的，所以显示的正是它卡住的位置。抓完之后它永久停车：直接睡在自己的 parker 上，不在任何桶的链表里，没有人能再叫醒它。检测只负责报告，不负责恢复；程序拿到报告后通常应该记录下来然后退出。被标记的线程以后建图时被跳过，同一个环只报一次。

看不到的情况

从建图规则可以直接推出盲区：图里只有「正在停车、不带超时、没被标记过」的线程，以及通过 acquire_resource 记过账的锁。

反过来，同一线程对一把不可重入的 Mutex 加两次锁是能检测到的：自己持有 A、自己在等 A，图上是「线程 → A → 线程」，一个只含一个线程的环（下面 E8 的 self 模式）。所以它适合抓「几把 parking_lot 锁的加锁顺序成环」这一类，不适合当作通用的「程序卡住了」诊断工具。

为什么和 send_guard 互斥

src/lib.rs:32-35：

// If deadlock detection is enabled, we cannot allow lock guards to be sent to
// other threads.
#[cfg(all(feature = "send_guard", feature = "deadlock_detection"))]
compile_error!("the `send_guard` and `deadlock_detection` features cannot be used together");

注释只说了结论。从上面的记账方式可以推出原因（推测，提交说明里没有展开）：资源记在加锁线程的 Vec 里；守卫被发到另一个线程后在那里解锁，release_resource 在那个线程的 Vec 里找不到这个 key，静默忽略，原线程的 Vec 里则一直留着一个已经不持有的锁。等待图因此会出现不存在的「持有」边。这一条的完整讨论在 GuardSend 与 send_guard。

实验 E8：能抓到什么、开销多大

断言：AB-BA 和三线程环能被检测到，各报一次；带超时的等待、std 锁、没有环的等待链检测不到；这个 feature 让每次加解锁变慢。

方法（exp-parking_lot/deadlock-detect）：检测部分用 --features dd（打开 parking_lot/deadlock_detection）构建，后台每 50 ms 调一次 check_deadlock()，2 秒内看是否报告，报告后立刻再调一次看是否重复报告。七种模式：

• 检测时间约 65 ms：第一次检查在 50 ms 时发生，其余十几毫秒主要是被标记的线程抓栈（Backtrace::new() 要解析符号）。
• ring3 报告的环恰好包含 3 个线程，DFS 找环的规则对长度大于 2 的环同样有效。
• 第二次调用都返回 0：被报告过的线程已经永久停车、被标记，不会再进图。
• chain3 是反向验证：等待链 A→B→C 存在、但没有闭合，图上无环，不报告；none 也一样。timed 和 std 两行就是上一节的前两个盲区。

开销：同一个程序的 bench 模式，T 个线程共享一把 Mutex<u64>，循环「加锁、加一、解锁」，锁外没有工作，1 秒，ns/op = 墙钟 / 总次数。分别用不开（dd=false）和开（dd=true）这个 feature 的两份二进制跑；再加一个对照 pad：不开 feature，但在临界区里手工做一次和 acquire_resource / release_resource 同样的线程局部 Vec push / 查找 / swap_remove。2026-11-01 22:28，开始时负载 1 分钟 2.12、5 分钟 2.96：

同一天 22:23 的另一组（负载 2.59 / 2.92）：T=1 时 5.20、5.25、5.25 对 7.09、7.07、7.08；T=12 时 26.98、25.87、26.79 对 18.19、18.40、18.33。

• 单线程：每对加解锁多约 1.8 ns，约慢 35%。pad 只多 1.4 ns，剩下的差别来自 with_thread_data 那次线程局部访问和函数调用。这是这个 feature 的直接开销。
• 12 线程、锁外没有工作：打开 feature 反而更快（约 19 ns 对 24–27 ns）。pad 对照也同样变快（约 20 ns），说明原因不在死锁检测本身，而在临界区里多出来的那一两纳秒工作。为什么临界区变长、吞吐反而变高，本卷没有拆开（推测：锁外完全没有工作时，持锁线程解锁后几乎立刻重新加锁，临界区稍长改变了线程之间抢锁和停车的节奏；要验证需要统计每次加锁走快路径、自旋还是停车）。T=4 时三组的波动和差别同量级，看不出方向。
• 结论：这个 feature 改变被测对象，单线程时可以按 1.8 ns / 次理解它的成本，高竞争的微基准则不能把它当成「多出来的开销」去减。这也是本卷所有计时实验都不开它的原因；规划阶段在开着它的 crate 里测得的高竞争吞吐数字，需要在不开它的 crate 里重测。

小结

• deadlock_detection 是实验性 feature：每次加锁把锁地址推进本线程 ThreadData 的 Vec，解锁时删掉；RwLock 记 addr 和 addr + 1 两个 key。
• check_deadlock() 要用户自己轮询；先逐桶建图粗查，有环再锁住整张表精查，DFS 找出每个环。
• 环上的线程被叫醒后自己抓栈发回，然后永久停车；同一个环只报一次。
• 盲区：带超时的等待、std 锁、自旋中的线程、Condvar 等待。
• 实测两线程环、三线程环约 65 ms 被报告；单线程每对加解锁多约 1.8 ns，高竞争微基准的吞吐反而变高，原因是临界区变长而不是检测本身。
• release_resource 的文档说会 panic，代码是静默忽略；和 send_guard 互斥。