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
  • ……

动态程序分析：状态机执行历史的一个函数f(τ)f(τ)

  • 付出程序执行变慢的代价
  • 找到更多 bugs

2.2 运行时 Lock Ordering 检查

一个想法

  • 为每一个 acquire/release 记录 tid 和 lock name
  • Assert: G(V,E)G(V, E) 无成环
    • V: 所有的 lock names
    • E: 每当观测到持有 𝑢 时获取 v 就把 (𝑢,𝑣) 加入 𝐸
1
2
3
4
5
6
T1 ACQ a
T1 ACQ b
T1 REL b
T2 ACQ b
T2 REL b
...

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();

3.1 防御性编程：Buffer Overrun 检查

Canary (金丝雀) 对一氧化碳非常敏感

  • 它们用生命预警矿井下的瓦斯泄露 (since 1911)

Canary: “牺牲” 内存单元，预警 memory error

  • (程序运行时没有动物受到实质的伤害)

3.2 Canary 的例子：Stack Guard

栈溢出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define MAGIC 0x55555555
#define BOTTOM (STK_SZ / sizeof(u32) - 1)
struct stack { char data[STK_SZ]; };

void canary_init(struct stack *s) {
    u32 *ptr = (u32 *)s;
    for (int i = 0; i < CANARY_SZ; i++)
        ptr[BOTTOM - i] = ptr[i] = MAGIC;
}

void canary_check(struct stack *s) {
    u32 *ptr = (u32 *)s;
    for (int i = 0; i < CANARY_SZ; i++) {
        panic_on(ptr[BOTTOM - i] != MAGIC, "underflow");
        panic_on(ptr[i] != MAGIC, "overflow");
    }
}

3.3 另一种 Canary

检测 “缓冲区溢出”

1
2
3
4
5
6
7
8
9
10
11
int foo() {
    // 一段连续内存；位于局部变量和返回地址之前
    u32 canary = SOME_VALUE;

    ... // 实际函数

    canary ^= SOME_VALUE; // 如果程序被攻击或出错
                          // canary 就不会归零了
    assert(canary == 0);
    return ret;
}

MSVC 中 Debug Mode 的 guard/fence/canary

  • 未初始化栈: 0xcccccccc
  • 未初始化堆: 0xcdcdcdcd
  • 对象头尾: 0xfdfdfdfd
  • 已回收内存: 0xdddddddd
    • 手持两把锟斤拷，口中疾呼烫烫烫
    • 脚踏千朵屯屯屯，笑看万物锘锘锘
1
2
for i in [0xcc, 0xcd, 0xdd, 0xfd]:
    print((bytes([i]) * 80).decode('gbk'))

3.4 防御性编程：低配版 Lockdep

高配版 lockdep 太复杂？

  • 统计当前的 spin count
  • 如果超过某个明显不正常的数值 (100, 000, 000) 就报告
    • 你感觉到 “hang” 了
1
2
3
4
5
6
7
int spin_cnt = 0;
while (xchg(&lk, ❌) == ❌) {
    if (spin_cnt++ > SPIN_LIMIT) {
        panic("Spin limit exceeded @ %s:%d\n",
            __FILE__, __LINE__);
    }
}
  • 配合调试器和线程 backtrace 一秒诊断死锁

3.5 防御性编程：低配版 AddressSanitizer

L1 内存分配器的 specification

  • 已分配内存 S=[ℓ0​,r0​)∪[ℓ1​,r1​)∪…S=[ℓ_0​, r_0​)∪[ℓ_1​, r_1​)∪…
  • kalloc(𝑠) 返回的 [ℓ,r)[ℓ, r) 必须满足 [ℓ,r)∩S=∅[ℓ, r)∩S=∅
1
2
3
4
5
6
7
8
9
10
11
// allocation
for (int i = 0; (i + 1) * sizeof(u32) <= size; i++) {
    panic_on(((u32 *)ptr)[i] == MAGIC, "double-allocation");
    arr[i] = MAGIC;
}

// free
for (int i = 0; (i + 1) * sizeof(u32) <= alloc_size(ptr); i++) {
    panic_on(((u32 *)ptr)[i] == 0, "double-free");
    arr[i] = 0;
}

防御性编程：低配版 ThreadSanitizer

回顾：数据竞争的表现

  • 🏃 的结果会影响状态
  • 我们观测状态影响就可以了！
1
2
3
4
5
6
7
8
9
// Suppose x is lock-protected

...
int observe1 = x;
delay();
int observe2 = x;

assert(observe1 == observe2);
...

3.6 防御性编程：SemanticSanitizer

两个看似平常的检查

  • 检查整数是否在某个范围
1
2
3
4
5
#define CHECK_INT(x, cond) \
    ({ panic_on(!((x) cond), \
       "int check fail: " \
       #x " " #cond); \
    })
  • 检查指针是否位于堆区
1
2
#define CHECK_HEAP(ptr) \
    ({ panic_on(!IN_RANGE((ptr), heap)); })

检查内部数据一致性

  • 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 的程序，从而减轻你调试问题的负担。