13. 应对 (并发) Bugs
1 应对死锁
1.1 死锁:一类 “简单” 的并发 Bug
具有明确的 Specification
- 任何线程在 “基本合理” 的调度下,不能失去进展
甚至有明确的必要条件
- Mutual-exclusion - 一个口袋一个球,得到球才能继续
- Wait-for - 得到球的人想要更多的球
- No-preemption - 不能抢别人的持有的球
- Circular-chain - 形成循环等待球的关系
Lock ordering: 避免循环等待
- 严格按照编号顺序获得所有锁
1.2 死锁:死局
一面是复杂的系统,另一面是不可靠的人
- 希望
- 标记 “做一件事” 不被打断
- 实际
- “做一件事” 需要拆解成多个步骤
- 每个步骤需要上正确 (而且尽可能少) 的锁
LockDoc (EuroSys’19)
- “Only 53 percent of the variables with a documented locking rule are actually consistently accessed with the required locks held.”
2 应对死局:绝处逢生
2.1 应对 “死局”:程序员的自救
我们可以在运行时检查一切明确的 Specification!
- AA/ABBA 型死锁
- 数据竞争
- 带符号整数溢出 (undefined behavior)
- Use after free
- ……
动态程序分析:状态机执行历史的一个函数
- 付出程序执行变慢的代价
- 找到更多 bugs
2.2 运行时 Lock Ordering 检查
一个想法
- 为每一个 acquire/release 记录 tid 和 lock name
- Assert: 无成环
- V: 所有的 lock names
- E: 每当观测到持有 𝑢 时获取 v 就把 (𝑢,𝑣) 加入 𝐸
1 | T1 ACQ a |
2.3 Linux Kernel Lockdep
解决锁的 “命名” 问题
- 可以是锁的地址
- 也可以是锁的初始化位置 (更严格;开销更小)
- The kernel lock validator
- Since Linux Kernel 2.6.17, also in OpenHarmony v1
我们有一个山寨实现!
2.4 应对死局:Sanitizers
现代复杂软件系统必备的支撑工具
- AddressSanitizer (asan); (paper): 非法内存访问
- Buffer (heap/stack/global) overflow, use-after-free, use-after-return, double-free, …;
- 没有 KASAN, Linux Kernel 的质量/安全性直接崩盘
- ThreadSanitizer (tsan): 数据竞争
- KCSAN: Concurrency bugs should fear the big bad
- data-race detector
- MemorySanitizer (msan), UBSanitizer (ubsan), …
- SpecSanitizer: 基于 AI/LLM 的 “specification 检查”
没错,在 “有 specification” 的情况下,开发者一定会想到合适的方法检查它们,以提高软件的质量。很显然,C 语言只提供 “底层机制” 的设计,在管理大型复杂项目时捉襟见肘。Linux Kernel 如果没有 ASAN 和 TSAN 机制,将会变得千疮百孔。
3 应对死线 (Deadline):防御性编程
理论很美好,现实很残酷
- 我们的框架直接运行在虚拟机上
- 根本没法带这些 sanitizers
- 试图移植 = 失败
- 我们根本不可能 “观测每一次共享内存访问”
Full Sanitizer 很难实现
- 不如换一种思路
- 我们可以 “编程”!
Best-effort is better than no-effort!
- 不实现 “完整” 的检查 (允许存在误报/漏报)
- 但实现简单、非常有用——而且有惊喜
- 我们不是一直都在写 assertions 吗?
- Peterson 算法:
assert(nest == 1);
- 链表:
assert(u->prev->next == u);
- spinlock:
if (holding(&lk)) panic();
- Peterson 算法:
- 我们不是一直都在写 assertions 吗?
3.1 防御性编程:Buffer Overrun 检查
Canary (金丝雀) 对一氧化碳非常敏感
- 它们用生命预警矿井下的瓦斯泄露 (since 1911)
Canary: “牺牲” 内存单元,预警 memory error
- (程序运行时没有动物受到实质的伤害)
3.2 Canary 的例子:Stack Guard
栈溢出
1 |
|
3.3 另一种 Canary
检测 “缓冲区溢出”
1 | int foo() { |
MSVC 中 Debug Mode 的 guard/fence/canary
- 未初始化栈: 0xcccccccc
- 未初始化堆: 0xcdcdcdcd
- 对象头尾: 0xfdfdfdfd
- 已回收内存: 0xdddddddd
- 手持两把锟斤拷,口中疾呼烫烫烫
- 脚踏千朵屯屯屯,笑看万物锘锘锘
1 | for i in [0xcc, 0xcd, 0xdd, 0xfd]: |
3.4 防御性编程:低配版 Lockdep
高配版 lockdep 太复杂?
- 统计当前的 spin count
- 如果超过某个明显不正常的数值 (100, 000, 000) 就报告
- 你感觉到 “hang” 了
1 | int spin_cnt = 0; |
- 配合调试器和线程 backtrace 一秒诊断死锁
3.5 防御性编程:低配版 AddressSanitizer
L1 内存分配器的 specification
- 已分配内存
- kalloc(𝑠) 返回的 必须满足
1 | // allocation |
防御性编程:低配版 ThreadSanitizer
回顾:数据竞争的表现
- 🏃 的结果会影响状态
- 我们观测状态影响就可以了!
1 | // Suppose x is lock-protected |
3.6 防御性编程:SemanticSanitizer
两个看似平常的检查
- 检查整数是否在某个范围
1 |
- 检查指针是否位于堆区
1 |
检查内部数据一致性
CHECK_INT(waitlist->count, >= 0);
CHECK_INT(pid, < MAX_PROCS);
CHECK_HEAP(ctx->rip); CHECK_HEAP(ctx->cr3);
代入 “变量语义”
-
CHECK_INT(count, >= 0);
-
CHECK_INT(count, <= 10000);
-
预防多种错误,甚至部分承担了 AddressSanitizer 的功能
- Overflow, use-after-free 都可能导致 memory corruption
短短几行代码,我们实现了
- Stack guard
- Lockdep (simple)
- AddressSanitizer (simple)
- ThreadSanitizer (simple)
- SemanticSanitizer
它们是一个种子
- 指向 “engineering” 里无限的空间
- 也指引我们反思编程语言的机制设计
Bugs (包括并发 bugs) 一直以来困扰着所有软件工程的实践者。我们不仅要应对 specification crisis (定义到底什么是对的),甚至即便知道 specification,也难以应对现代软件的复杂性。为了部分应对这一点从而实现 “更正确” 的软件,我们把对程序的预期表达在程序中 (race-free, lock ordering, …),而不是让程序在自然状态下悄悄进入有问题的状态,就是我们目前解决程序调试问题的折中办法。“山寨” sanitizer 给我们带来的启发则是:如果我们能清楚地追溯到问题产生的本源,我们就总是能找到好的应对方法——山寨的 sanitizers 在暗中帮助你实现 fail-fast 的程序,从而减轻你调试问题的负担。