 学习笔记：并发 Bug 的地狱——数据竞争、死锁与原子性违反)
写在前面这是本系列的第十七篇。理论上说我们可以用并发编程 API线程、互斥锁、条件变量、信号量实现几乎一切实用的并发程序。然而并发程序“难写”也是出了名的。时至今日我们还没有一种完美、便捷的技术能帮助我们绝对安全地构建多核软件系统。并发 Bug 那种“若隐若现”、“难以复现”的特性导致它们经常逃脱测试人员的掌控。本讲内容我们将直面并发编程中最致命的错误模式——数据竞争、死锁、原子性违反和顺序违反。课前回顾线程库与同步互斥线程库 (人和物理世界):spawn,join互斥 (厕所门):lock(lk),unlock(lk)同步 (等待条件发生):wait(cv, mutex); broadcast(cv)信号量 (袋子和球):P(sem), V(sem)并发编程之所以困难是因为人类天生就是“Sequential Creature”顺序生物。我们习惯了单线程式的思考在写并发代码时大脑极其容易产生“指令是按代码顺序执行”的幻觉。试过 RTS即时战略游戏里的多线微操吗并发编程比那难一万倍。致命的并发 BugsKilled by a Machine如果并发写错了不仅是程序崩溃甚至可能伤人性命。Therac-25 医疗事故 (1985-1987)这是软件工程史上最著名、也是最惨痛的并发 Bug导致至少 6 名患者因过量辐射死亡。Therac-25 是一台放射治疗机它有两种模式Electron (Low): 电子束低剂量模式直接照射。XRay (High): X 射线高剂量模式必须在物理光束前面加上一个金属靶Beam Flattener把高能电子打碎成 X 射线否则会把人直接烧穿。它的核心安全逻辑其实非常简单assert mode in[Electron(Low),XRay(High)]assert beam_flattener in[On,Off]// 绝对不能在没有降能靶的情况下开启高剂量照射assertnot(modeXRay(High)and beam_flattenerOff)悲剧是如何发生的(“软件定义”的代价)操作员一开始选错了选了X-Ray (High)模式。机器收到指令开始缓慢地移动巨大的金属降能靶beam flattener这大约需要 8 秒钟。就在这 8 秒内操作员发现按错了迅速把模式切换到了Electron (Low)。接着操作员凭借单身二十年的手速再次迅速切换回了X-Ray (High)模式并按下了发射键此时由于并发的竞态条件软件里的状态被覆盖错乱了机器以为降能靶已经就位但实际上沉重的物理降能靶根本没来得及移过去触发了Malfunction 54报错。遗憾的是习惯了系统乱报错的操作员下意识地按下了Continue……Root Cause 分析在纯粹的顺序程序中状态的修改是立即生效的。但在真实的物理/并发世界中状态的改变移动降能靶需要时间。操作员手速过快触发了非确定性的状态交织。在更早的产品中这种互锁是由纯物理电路强制保证的绝不可能绕过。但进入了“软件定义”时代如果没有严谨的并发控制底线安全就成了空中楼阁。数据竞争 (Data Race)并发的最底层魔鬼我们如何才能避免两个线程“同时”读写定义不同的线程同时访问同一内存且至少有一个是写操作。发生数据竞争时两个内存访问在“赛跑”谁跑赢了谁就先执行。但这并不是最可怕的最可怕的是在现代 CPU 的Weak Memory Model (弱内存模型)下“跑赢”并没有想象中那么简单。它甚至允许不同核心上的观察者看到完全相反的比赛结果从 C11 标准开始官方明确规定Data Race is Undefined Behavior (数据竞争是未定义行为)。一旦发生编译器怎么优化、CPU 怎么乱序后果自负。那些年我们写过的 Data Race 代码所谓 Ad-hoc synchronization比如用一个while(!flag)死循环当锁本质上都是 Data Race。只有通过标准的锁机制我们才能保证 Serializability可串行化让可能竞争的内存访问要么互斥要么同步强行退回顺序执行。新手最常见的两种数据竞争变种Case 1: 上错了锁voidT_1(){spin_lock(A);sum;spin_unlock(A);}voidT_2(){spin_lock(B);sum;spin_unlock(B);}(注保护同一个共享变量sum却用了两把不同的锁防了个寂寞)Case 2: 忘记上锁voidT_1(){spin_lock(A);sum;spin_unlock(A);}voidT_2(){sum;}为什么不要笑因为在真实系统几百万行代码里这些变量可能藏在堆、栈、框架底层、甚至是你看不见的汇编指令里。要完全消灭并发 Bug必须尽可能减少共享状态的访问。死锁 (Deadlock)维基百科A deadlock is a state in which each member of a group is waiting for another member, including itself, to take action.死锁一组实体中的每一个都在等待另一个实体采取行动导致所有人都被永久卡住。AA-Deadlock (我锁我自己)lock(lk);...// 极度复杂的嵌套后或者在中断处理程序里lock(lk);// 试图再次获取同一把锁当场死锁你觉得自己不会犯这种错在真实的 5~6 层函数调用嵌套、隐藏的控制流里你早就忘了最外层有没有加锁了。ABBA-Deadlock (哲学家就餐)就是我们之前遇到的哲学家吃饭问题voidT_philosopher(){P(avail[lhs]);P(avail[rhs]);...}T1: 拿到 0等 1T2: 拿到 1等 2T3: 拿到 2等 3T4: 拿到 3等 4T5: 拿到 4等 0形成了一个完美的闭环所有人都在等右手边的人放下叉子。死锁产生的四个必要条件 (Coffman Conditions, 1971)把锁看成袋子里的球Mutual-exclusion (互斥):一个口袋一个球得到球才能继续。Wait-for (请求并保持):得到球的人还在贪婪地想要更多的球且不肯放下手里的球。No-preemption (不可剥夺):不能强行抢走别人手里的球。Circular-chain (环路等待):形成 $ A \rightarrow B \rightarrow C \rightarrow A $ 的循环等待关系。只要打破任何一个条件死锁就不会发生在实际系统中如何避免死锁理论上说得好听“合理规划资源分配”但在动辄千万行的内核代码中该怎么做Lock Ordering (全局锁排序):强行给所有的锁编个号强制所有人必须按照从小到大的顺序去获取锁。这样由于永远有一个线程能拿到编号最大的锁环路就被打破了。但这在工程上依然极其痛苦。Linux 内核黑客指南Unreliable Guide to Locking里明确吐槽书本上教你全局排序但实践中根本行不通This approach doesn’t scale。当我新建一把锁时我怎么可能弄清楚它在内核那 5000 把锁的层级里到底该排第几终极最佳实践最好的锁是被完全封装Encapsulated的。绝不暴露在头文件里绝不带着锁去调用其他文件里复杂的函数。只要你在这个文件内部把锁加上、立刻用完解开使用者甚至不需要知道你用了锁死锁自然也就无从谈起。动态检测LockDep为了对抗不靠谱的程序员现代操作系统引入了动态分析工具比如 Linux 内核的 LockDep。它的核心思想是每次acquire/release都在后台打个日志。在运行时动态构建一张“锁依赖图”一旦发现既有 $ A \rightarrow B $ 的申请顺序又有 $ B \rightarrow A $ 的申请顺序立刻警告可能存在死锁哪怕当时还没死锁。原子性违反与顺序违反并不是全加上了一把大锁就能天下太平。并发控制的机制完全是“后果自负”的互斥锁lock/unlock用于保证原子性。忘记上锁 $ \rightarrow $原子性违反 (Atomicity Violation, AV)。条件变量wait/signal用于保证先后顺序。忘记同步 $ \rightarrow $顺序违反 (Order Violation, OV)。顶级实证研究 (ASPLOS’08, Most Influential Paper Award)在收集的 105 个真实系统MySQL, Apache, Mozilla 等并发 Bug 中97% 的非死锁并发 Bug 都是原子性或顺序错误再次印证人类真的是彻头彻尾的 Sequential Creature。原子性违反 (Atomicity Violation, ABA 问题)即便你对每一个单独的操作都上了锁消除了数据竞争依然可能被别人“强势插入”。比如暗黑破坏神Diablo I里利用并发漏洞复制物品。又或者像 Therac-25 那样第一步设置移动靶子 (A)和第三步发射射线 (A)之间被用户的第二步切换低频模式 (B)强势插入了。TOCTTOU 漏洞操作系统的状态也是共享状态(Time-of-check to time-of-use)。这在安全领域臭名昭著。你在检查文件权限Check时是合法的但在你真正打开文件Use的微小间隙黑客并发地把那个文件替换成了系统密码本的软链接。顺序违反 (Order Violation, BA 问题)事件没有按照预定的顺序发生。比如经典的Concurrent Use-after-Free你以为线程 1 会先用完指针线程 2 再去free它。结果线程 2 跑太快了先把指针给free了随后线程 1 再去解引用直接段错误崩溃。真实世界的魔鬼GhostRace (Spicy ️)这是发表在顶会 USENIX Sec’24 的超硬核研究。假设程序员写出了天衣无缝的代码正确的互斥、正确的同步逻辑无懈可击。voidT_A(){lock(obj-lock);free(obj-something);obj-somethingNULL;unlock(obj-lock);}voidT_B(){lock(obj-lock);if(obj-something){// 利用投机执行 (Speculative Execution) 改变缓存状态}unlock(obj-lock);}在严格的理论层面T_B绝不可能在obj-something被free后还能进入if。但是现代 CPU 有投机执行预测执行的功能。CPU 为了快在等锁的时候它“猜”自己能拿到锁于是提前执行了if里的代码并把数据加载到了 CPU 缓存里。哪怕后来 CPU 发现自己猜错了把执行结果撤销了但缓存里的痕迹留下来了Spectre 漏洞的变种。黑客借此实现了完美的侧信道攻击。面对这样深不可测的底层世界除了保持敬畏唯有不断扎实底层的基本功才能在风暴来临时看清魔鬼的真容。
写在前面这是本系列的第十七篇。理论上说我们可以用并发编程 API线程、互斥锁、条件变量、信号量实现几乎一切实用的并发程序。然而并发程序“难写”也是出了名的。时至今日我们还没有一种完美、便捷的技术能帮助我们绝对安全地构建多核软件系统。并发 Bug 那种“若隐若现”、“难以复现”的特性导致它们经常逃脱测试人员的掌控。本讲内容我们将直面并发编程中最致命的错误模式——数据竞争、死锁、原子性违反和顺序违反。课前回顾线程库与同步互斥线程库 (人和物理世界):spawn,join互斥 (厕所门):lock(lk),unlock(lk)同步 (等待条件发生):wait(cv, mutex); broadcast(cv)信号量 (袋子和球):P(sem), V(sem)并发编程之所以困难是因为人类天生就是“Sequential Creature”顺序生物。我们习惯了单线程式的思考在写并发代码时大脑极其容易产生“指令是按代码顺序执行”的幻觉。试过 RTS即时战略游戏里的多线微操吗并发编程比那难一万倍。致命的并发 BugsKilled by a Machine如果并发写错了不仅是程序崩溃甚至可能伤人性命。Therac-25 医疗事故 (1985-1987)这是软件工程史上最著名、也是最惨痛的并发 Bug导致至少 6 名患者因过量辐射死亡。Therac-25 是一台放射治疗机它有两种模式Electron (Low): 电子束低剂量模式直接照射。XRay (High): X 射线高剂量模式必须在物理光束前面加上一个金属靶Beam Flattener把高能电子打碎成 X 射线否则会把人直接烧穿。它的核心安全逻辑其实非常简单assert mode in[Electron(Low),XRay(High)]assert beam_flattener in[On,Off]// 绝对不能在没有降能靶的情况下开启高剂量照射assertnot(modeXRay(High)and beam_flattenerOff)悲剧是如何发生的(“软件定义”的代价)操作员一开始选错了选了X-Ray (High)模式。机器收到指令开始缓慢地移动巨大的金属降能靶beam flattener这大约需要 8 秒钟。就在这 8 秒内操作员发现按错了迅速把模式切换到了Electron (Low)。接着操作员凭借单身二十年的手速再次迅速切换回了X-Ray (High)模式并按下了发射键此时由于并发的竞态条件软件里的状态被覆盖错乱了机器以为降能靶已经就位但实际上沉重的物理降能靶根本没来得及移过去触发了Malfunction 54报错。遗憾的是习惯了系统乱报错的操作员下意识地按下了Continue……Root Cause 分析在纯粹的顺序程序中状态的修改是立即生效的。但在真实的物理/并发世界中状态的改变移动降能靶需要时间。操作员手速过快触发了非确定性的状态交织。在更早的产品中这种互锁是由纯物理电路强制保证的绝不可能绕过。但进入了“软件定义”时代如果没有严谨的并发控制底线安全就成了空中楼阁。数据竞争 (Data Race)并发的最底层魔鬼我们如何才能避免两个线程“同时”读写定义不同的线程同时访问同一内存且至少有一个是写操作。发生数据竞争时两个内存访问在“赛跑”谁跑赢了谁就先执行。但这并不是最可怕的最可怕的是在现代 CPU 的Weak Memory Model (弱内存模型)下“跑赢”并没有想象中那么简单。它甚至允许不同核心上的观察者看到完全相反的比赛结果从 C11 标准开始官方明确规定Data Race is Undefined Behavior (数据竞争是未定义行为)。一旦发生编译器怎么优化、CPU 怎么乱序后果自负。那些年我们写过的 Data Race 代码所谓 Ad-hoc synchronization比如用一个while(!flag)死循环当锁本质上都是 Data Race。只有通过标准的锁机制我们才能保证 Serializability可串行化让可能竞争的内存访问要么互斥要么同步强行退回顺序执行。新手最常见的两种数据竞争变种Case 1: 上错了锁voidT_1(){spin_lock(A);sum;spin_unlock(A);}voidT_2(){spin_lock(B);sum;spin_unlock(B);}(注保护同一个共享变量sum却用了两把不同的锁防了个寂寞)Case 2: 忘记上锁voidT_1(){spin_lock(A);sum;spin_unlock(A);}voidT_2(){sum;}为什么不要笑因为在真实系统几百万行代码里这些变量可能藏在堆、栈、框架底层、甚至是你看不见的汇编指令里。要完全消灭并发 Bug必须尽可能减少共享状态的访问。死锁 (Deadlock)维基百科A deadlock is a state in which each member of a group is waiting for another member, including itself, to take action.死锁一组实体中的每一个都在等待另一个实体采取行动导致所有人都被永久卡住。AA-Deadlock (我锁我自己)lock(lk);...// 极度复杂的嵌套后或者在中断处理程序里lock(lk);// 试图再次获取同一把锁当场死锁你觉得自己不会犯这种错在真实的 5~6 层函数调用嵌套、隐藏的控制流里你早就忘了最外层有没有加锁了。ABBA-Deadlock (哲学家就餐)就是我们之前遇到的哲学家吃饭问题voidT_philosopher(){P(avail[lhs]);P(avail[rhs]);...}T1: 拿到 0等 1T2: 拿到 1等 2T3: 拿到 2等 3T4: 拿到 3等 4T5: 拿到 4等 0形成了一个完美的闭环所有人都在等右手边的人放下叉子。死锁产生的四个必要条件 (Coffman Conditions, 1971)把锁看成袋子里的球Mutual-exclusion (互斥):一个口袋一个球得到球才能继续。Wait-for (请求并保持):得到球的人还在贪婪地想要更多的球且不肯放下手里的球。No-preemption (不可剥夺):不能强行抢走别人手里的球。Circular-chain (环路等待):形成 $ A \rightarrow B \rightarrow C \rightarrow A $ 的循环等待关系。只要打破任何一个条件死锁就不会发生在实际系统中如何避免死锁理论上说得好听“合理规划资源分配”但在动辄千万行的内核代码中该怎么做Lock Ordering (全局锁排序):强行给所有的锁编个号强制所有人必须按照从小到大的顺序去获取锁。这样由于永远有一个线程能拿到编号最大的锁环路就被打破了。但这在工程上依然极其痛苦。Linux 内核黑客指南Unreliable Guide to Locking里明确吐槽书本上教你全局排序但实践中根本行不通This approach doesn’t scale。当我新建一把锁时我怎么可能弄清楚它在内核那 5000 把锁的层级里到底该排第几终极最佳实践最好的锁是被完全封装Encapsulated的。绝不暴露在头文件里绝不带着锁去调用其他文件里复杂的函数。只要你在这个文件内部把锁加上、立刻用完解开使用者甚至不需要知道你用了锁死锁自然也就无从谈起。动态检测LockDep为了对抗不靠谱的程序员现代操作系统引入了动态分析工具比如 Linux 内核的 LockDep。它的核心思想是每次acquire/release都在后台打个日志。在运行时动态构建一张“锁依赖图”一旦发现既有 $ A \rightarrow B $ 的申请顺序又有 $ B \rightarrow A $ 的申请顺序立刻警告可能存在死锁哪怕当时还没死锁。原子性违反与顺序违反并不是全加上了一把大锁就能天下太平。并发控制的机制完全是“后果自负”的互斥锁lock/unlock用于保证原子性。忘记上锁 $ \rightarrow $原子性违反 (Atomicity Violation, AV)。条件变量wait/signal用于保证先后顺序。忘记同步 $ \rightarrow $顺序违反 (Order Violation, OV)。顶级实证研究 (ASPLOS’08, Most Influential Paper Award)在收集的 105 个真实系统MySQL, Apache, Mozilla 等并发 Bug 中97% 的非死锁并发 Bug 都是原子性或顺序错误再次印证人类真的是彻头彻尾的 Sequential Creature。原子性违反 (Atomicity Violation, ABA 问题)即便你对每一个单独的操作都上了锁消除了数据竞争依然可能被别人“强势插入”。比如暗黑破坏神Diablo I里利用并发漏洞复制物品。又或者像 Therac-25 那样第一步设置移动靶子 (A)和第三步发射射线 (A)之间被用户的第二步切换低频模式 (B)强势插入了。TOCTTOU 漏洞操作系统的状态也是共享状态(Time-of-check to time-of-use)。这在安全领域臭名昭著。你在检查文件权限Check时是合法的但在你真正打开文件Use的微小间隙黑客并发地把那个文件替换成了系统密码本的软链接。顺序违反 (Order Violation, BA 问题)事件没有按照预定的顺序发生。比如经典的Concurrent Use-after-Free你以为线程 1 会先用完指针线程 2 再去free它。结果线程 2 跑太快了先把指针给free了随后线程 1 再去解引用直接段错误崩溃。真实世界的魔鬼GhostRace (Spicy ️)这是发表在顶会 USENIX Sec’24 的超硬核研究。假设程序员写出了天衣无缝的代码正确的互斥、正确的同步逻辑无懈可击。voidT_A(){lock(obj-lock);free(obj-something);obj-somethingNULL;unlock(obj-lock);}voidT_B(){lock(obj-lock);if(obj-something){// 利用投机执行 (Speculative Execution) 改变缓存状态}unlock(obj-lock);}在严格的理论层面T_B绝不可能在obj-something被free后还能进入if。但是现代 CPU 有投机执行预测执行的功能。CPU 为了快在等锁的时候它“猜”自己能拿到锁于是提前执行了if里的代码并把数据加载到了 CPU 缓存里。哪怕后来 CPU 发现自己猜错了把执行结果撤销了但缓存里的痕迹留下来了Spectre 漏洞的变种。黑客借此实现了完美的侧信道攻击。面对这样深不可测的底层世界除了保持敬畏唯有不断扎实底层的基本功才能在风暴来临时看清魔鬼的真容。
