并发Bugs

并发Bug

笔记内容来自蒋炎岩老师的OS课程以及slides

死锁

AA-Deadlock

unlock之前出现中断，然后lock()，此时会出现spin

ABBA-Deadlock（最常见）

T->lock(A)->lock(B)

T->lock(B)->lock(A)

当一个线程lock AB后才能执行，但如果T1lock(A),T2lock(B)，此时无法满足条件，死锁

如何避免死锁

  1. Lock ordering
  • 任意时刻系统中的锁都是有限的
  • 给所有锁编号 (Lock Ordering)
    • 严格按照从小到大的顺序获得锁
  1. Proof (sketch)
  • 任意时刻，总有一个线程获得 “编号最大” 的锁
  • 这个线程总是可以继续运行

数据竞争(Data Race)

不同的线程同时访问同一内存，且至少有一个是写

例子：

Case 1: 上错了锁

1
2
3
4
5
6
7
8
9
10
void T_1() { 
    spin_lock(&A); 
    sum++; 
    spin_unlock(&A); 
} 
void T_2() { 
    spin_lock(&B); 
    sum++; 
    spin_unlock(&B); 
}

Case 2: 忘记上锁

1
2
3
4
5
6
7
8
void T_1() { 
    spin_lock(&A); 
    sum++; 
    spin_unlock(&A); 
} 
void T_2() { 
    sum++; 
}

原子性/顺序违反

“ABA”: 代码被别人 “强势插入”

  • 即便分别上锁 (消除数据竞争)，依然是 AV
    • Diablo I 里复制物品的例子
    • Therac-25 中 “移动 Mirror + 设置状态”

“BA”: 事件未按预定的顺序发生

  • 例子：concurrent use-after-free
  • GhostRace (USENIX Sec’24)

应对并发Bugs

死锁

我们可以在运行时检查一切明确的 Specification！

  • 严格按照编号执行
  • 运行时lockorder的检查(lockdep)
  • ThreadSanitizer: 运行时的数据竞争检查

应对死局: 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();

Buffer Overrun检查

  • Canary: “牺牲” 内存单元，预警 memory error
  • 例如：Stack Guard（栈溢出），缓冲区溢出

低配版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 一秒诊断死锁

低配版AddressSanitizer

L1 内存分配器的 specification

  • 已分配内存 S=[ℓ0,r0)∪[ℓ1,r1)∪…S=[ℓ0,r0)∪[ℓ1,r1)∪…
  • kalloc(s) 返回的 [ℓ,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
10
// Suppose x is lock-protected

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

assert(observe1 == observe2);
...

SemanticSanitizer

两个看似平常的检查

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