本文作者：杜雨阳滴滴|高级专家工程师-Linux内核指南：死锁是多线程和分布式程序中普遍存在的严重问题。死锁是破坏性的。一旦发生，系统很难或几乎不可能恢复；死锁是随机的，只有在满足某些条件时才会发生。如果条件复杂，虽然发生的概率很低，但一旦发生，就很难了。重现和调试。使用锁的死锁是一种常见的死锁情况。Linux内核使用Lockdep工具来检测并特别预测锁的死锁情况。但是Lockdep目前只支持互斥锁，不支持更复杂的读写锁，尤其是递归读锁。因此，Lockdep会遭受由读写锁引起的误报和漏报预测。本工作首先对Lockdep工具进行解密，然后提出了一种通用的锁死锁预测算法的设计与实现（互斥锁可以看作是只使用读写锁中的写锁），并证明了该算法是正确而全面。计划。今年年初，我们先后解决了三个严重影响滴滴基础平台大规模服务器集群的内核故障。我们在解决这些问题的时候，花了很多时间和精力去找出造成死锁的原因。排错时间耽误了，想知道有没有什么通用的方法可以帮助我们处理死锁问题。但由于时间关系，我们只能针对这些具体问题进行有针对性的探讨和处理。终于成功修复了这些内核故障后，我终于有时间静下心来，深入思考死锁产生的原因，以及如何检测和预测死锁。随着对这个问题的深入研究，我先后在内核死锁预测方面做了一些算法优化和算法设计工作，有的已经被Linux内核接受，有的还在审查阶段。在这里给大家分享一个比较重要的工作：读写锁的通用死锁预测算法。这项工作提出了一种通用的锁死锁预测算法，支持所有Linux内核读写锁，并证明该算法是一个正确且全面的解决方案。这个算法解决的核心问题已经存在了10多年（目前还在社区审核阶段）。在介绍这项工作之前，先简单介绍一下死锁问题和Linux内核死锁工具Lockdep。1.死锁（Deadlock）死锁在日常生活中并不少见。生活在大城市的人或多或少都经历过下图所示的场景。这种发生在环岛或十字路口的情况就是死锁。也许有些车坏了，但绝大多数车都能用。但是因为每辆车都要等前面的车动完才能动，所以所有的车都动不了，或者更通俗地说就是不能前进（MakeForwardProgress）。造成这种情况的原因是车辆的等待构成了一个循环，其中每辆车的状态都在等待前面的车辆，所以所有的车辆都不能等待自己正在等待的东西。这种车辆僵持状态将继续恶化，产生严重后果：一是会造成路口交通拥堵，如果拥堵进一步扩大，将导致大范围的交通瘫痪。车辆死锁难以自愈，自行脱离死锁状态难度很大或需要很长时间。一般只能靠人工（如交警）干预才能解决。图1：环岛路上堵车（图片来自网络）在多线程或分布式系统程序中，也会出现死锁。其本质与上述路口堵车是一样的。就是因为参与者形成了循环等待，使得所有的参与者都等不到想要的结果，所以就会永远等待，无法取得进步。当然，死锁也发生在Linux内核中。如果调度器、内存管理等核心部分（Core）或文件系统等子系统出现死锁，则整个系统将不可用。死锁是随机发生的。如上图环形交叉路口的情况，环形交叉路口就在那里，死锁并不总是发生。但是环岛本身就是死锁的隐患，尤其是在车流压力比较大的路口，环岛会更容易出现死锁。而且这个路口如果设计成交通信号灯会好很多，如果设计成立交桥会好很多。在程序中，我们将可能导致死锁的场景称为潜在死锁场景（PotentialDeadlockScenario），即将发生或正在发生的死锁称为死锁实例（ConcreteDeadlock）。如何处理死锁一直是学术界和应用领域积极研究和解决的问题。我们大致可以将解决死锁的方法分为：死锁检测（Detection）、死锁避免（Prevention）和死锁预测（Prediction）。死锁发现是指在程序运行过程中发现死锁实例；死锁避免是当发现即将产生死锁实例时，进一步阻止该实例；而死锁预测就是通过静态或动态的方法找出程序中潜在的问题。死锁，提前从根本上消除死锁隐患。2.锁死锁和Lockdep在死锁中，锁（Lock）使用不当造成的死锁是死锁的一个重要来源。锁是同步的主要手段，使用锁是必然的。对于复杂的同步关系，锁的使用会比较复杂。如果使用不当，很容易造成锁的死锁。从等待的角度来看，锁的死锁是由于参与线程等待锁的释放，而这个等待构成了一个等待循环，比如ABBA死锁：图2：双线程ABBA死锁其中，线程中的黑色箭头表示线程当前正在执行语句，红色箭头表示线程语句之间的等待关系。如您所见，红色箭头形成一个圆圈（或循环）。再回顾一下潜在的死锁和死锁实例，如果这两个线程的执行时间稍有变化，那么很有可能不会发生死锁实例，比如Thread1在Thread2开始执行之前执行了这段代码。但这样的加锁行为（LockingBehavior）无疑是一种潜在的死锁。进一步可以看出，如果我们能够跟踪和分析程序的锁使用行为，就可以预测死锁或发现潜在的死锁，而不是等待死锁来检测死锁实例。Linux内核的Lockdep工具就是描述内核的锁行为，进而预测和报告潜在的死锁。Lockdep可以描述一类锁（LockClass）的行为，主要是记录一类锁中所有锁实例的加锁顺序（LockingOrder），即如果一个线程持有锁A，它会先获取它释放它。锁B，然后锁A，锁B，锁顺序为A->B。在Lockdep中，这种锁顺序叫做：锁依赖（LockDependency）。同样，对于ABBA类型的死锁，我们不需要Thread1和Thread2恰好产生一个死锁实例，只要有一个线程产生A->B锁序列行为，另一个线程产生B->A锁序列行为。锁序列行为，那么这就构成了潜在的死锁，如下图所示：图3：线程ABBA锁序列由此泛化而来，我们可以记录并保存所有的锁序列（即锁依赖），形成一个锁定序列图（Graph）。其中，如果有一个锁依赖A->B和另一个锁依赖B->C，那么由于锁依赖（Relation）是传递性的（Transitive），我们也可以得到锁依赖A->C。A->B和B->C称为直接依赖（DirectDependency），而A->C称为间接依赖（IndirectDependency）。对于每个新的直接锁依赖，我们检查这个依赖是否与图中现有的锁依赖形成一个循环。如果是这样，那么我们可以预测潜在的僵局。3.读写锁（Read-writeLock）刚才我们说的锁都是排他锁（ExclusiveLock）。读写锁是一种更复杂的锁，或者说是通用锁（GeneralLock）。我们可以把互斥体看成是只使用写锁的读写锁。只要不存在写锁和写锁争用，读锁是允许读者（Reader）同时持有的。Linux内核中的读写锁有很多种，主要有：rwsem、rwlock和qrwlock等，问题是读写锁会使死锁预测变得极其复杂，Lockdep无法支持这几种读写锁，所以Lockdep在使用过程中会产生一些相关的错误。假阴性死锁预测。这个问题已经存在了10多年。我们提出了一种通用的锁死锁预测算法，并证明该算法解决了读写锁的死锁预测问题。4.锁的通用死锁预测在描述该算法的过程中，我们通过提出几个引理（Lemma）来解释或证明我们提出的死锁预测的有效性。▍引理1：引入读写锁后，锁的加锁顺序循环是潜在死锁的必要条件，但不是充分条件。此外，潜在的死锁可以而且只能在最后一个锁序列（或锁依赖）即将产生死锁循环时被预测到。基于引理1，解决死锁预测问题就是在最后一个获取锁的顺序（即锁依赖）形成等待环（circle）时，通过一定的方法计算等待环是否构成潜在死锁，而我们的任务是找到这个方法（算法）。▍引理2：两个虚拟线程T1和T2可以用来表示所有的死锁场景。对于任意一个死锁实例，假设有n个线程参与了这个死锁实例，这n个线程表示为：T1,T2,...,Tn考虑n的情况：如果n=1：这个死锁即线程等待自己，在Lockdep中称为RecursionDeadlock。由于检查这种死锁的简单性，下面的算法忽略了这种特殊情况。如果n>1：这种死锁在Lockdep中称为InversionDeadlock。对于这种情况，我们将n个线程分成两组，即T1，T2，...，Tn-1和Tn，然后合并上一组中所有的锁依赖，并假设所有这些依赖都存在于一个虚拟中线程，得到两个虚拟线程T1和T2。这就是引理2中陈述的两个虚拟线程。基于引理2，我们提出了一个用于死锁检查的双线程模型（Two-ThreadModel）来表示内核的加锁行为：T1:Alllockdependenciesbeforethecurrentcheck锁依赖，这些依赖构成了一个锁依赖图。T2：当前要检查的直接锁依赖。根据引理2和死锁检查双线程模型，我们可以得到如下引理：▍引理3：任何死锁都可以转化为ABBA类型。基于以上3个引理，我们可以将死锁预测问题进一步描述为，当我们得到一个新的直接锁依赖B->A时，我们将这个新的依赖想象为T2，而之前所有的锁依赖都存在基于一个锁依赖图由一个假想的T1产生，死锁预测是检查T1中是否存在A->B的锁依赖，如果存在死锁，否则不存在死锁，将T2合并到T1中。如下图所示：图4：T1的锁依赖关系图和T2的直接锁依赖关系。引入读写锁后，锁的依赖性也取决于锁的类型，即读或写。根据Linux内核中互斥锁和读写锁的设计特点，我们引入一个锁互斥表来表示锁之间的互斥关系：表1：读写锁互斥关系表其中，递归读锁（Recursive-readLock）是一种特殊的读锁，可以被同一个线程递归持有。下面我们先提出一个简单的算法（SimpleAlgorithm）。基于双线程模型，给定T1和T2，以及ABBA锁：图5：基于双线程模型的简单算法简单算法的步骤如下：若X1.A和X1.B互斥X2.A和X2。B互斥，则T1和T2构成潜在死锁。否则，T1和T2不构成潜在死锁。从简单的算法可以看出，锁的类型决定了锁之间的互斥关系，互斥关系是检查死锁的关键信息。对于读写锁，锁类型在程序执行过程中可能会发生变化，那么如何记录所有的锁类型呢？基于锁类型互斥，即锁类型互斥从低到高：递归读锁<读锁<写锁（互斥锁），提出锁类型提升（LockTypePromotion）.在程序执行过程中，如果遇到高互斥锁类型，那么我们将锁依赖中的锁类型升级为高互斥锁依赖。锁类型升级如图：图6：锁类型升级其中RRn表示递归读锁n（Recursive-readLockn），Rn表示读锁n（ReadLockn），Wn表示写锁或互斥锁n（写锁n）。下面的xn代表任意锁n（即recursiveread,readorwritelock）。然而，上述简单的算法并不能处理所有的死锁预测情况。例如，下面的情况会逃脱简单算法，但实际上它是一个潜在的死锁：图7：简单算法失败的情况在这种情况下，X1和X3是互斥的，所以这种情况构成了潜在的死锁。但是当简单算法检查RR2->X1（即T2是RR2->X1）时，根据简单算法可以发现T1中有X1->RR2，但是因为RR和RR互不存在exclusive，误判定本例不为死锁。分析这个案例为什么会得出错误的结论是因为真正的死锁X1X3X3X1中的X3->X1是一个间接锁依赖，简单算法漏掉了这个间接依赖。这个问题更深层次的原因是互斥锁之间只有互斥，所以只要有ABBA就是潜在的死锁，不需要检查T2的间接锁依赖。在读锁的情况下，这个条件已经不存在了，所以必须考虑T2中的间接锁依赖。▍引理4：对于由直接锁依赖引入的间接锁依赖，如果间接锁依赖构成死锁，那么直接锁依赖仍然是critical。引理4是引理1的扩展。根据引理1，这个直接的锁依赖一定是形成锁循环的最后一个锁依赖，引理4表明通过这个锁依赖，一定可以判断是否是锁循环这是一个潜在的僵局。也就是说，通过修改和加强之前提出的简单算法，新算法一定能够解决这个问题。但问题在于，T2中原有的直接锁依赖可能会进一步产生大量的间接锁依赖。我们如何找到最终导致潜在死锁的间接锁依赖？更进一步，我们首先需要重新定义T2，然后在这个T2中找到所有的间接锁依赖，那么T2的边界是什么？如果将T2扩展到整个锁依赖图，算法的复杂度会增加很多，甚至可能超过Lockdep的处理能力，导致Lockdep实际上无法使用。▍引理5：T2只需要扩展到当前线程的LockStack即可。根据引理5，我们首先将之前提出的双线程模型修改为：T1：检查当前直接锁依赖之前的所有锁依赖，这些依赖形成一个图。T2：待查线程的当前锁栈。根据引理5和新的双线程模型，我们在简单算法的基础上提出如下最终算法（FinalAlgorithm）：继续搜索锁依赖图，即T1寻找新的锁依赖循环。在这个新的循环中，如果T2中还有其他锁，那么这个锁和T2中的直接锁依赖构成间接锁依赖，检查这个间接锁依赖是否构成潜在死锁。如果发现潜在的死锁，则算法结束，如果没有，则算法转到1，直到搜索完整个锁依赖图。这个最终的算法能否解决之前存在漏洞的案例？答案是肯定的，具体检查过程如图：图8：简单算法的失败案例解决过程然而，对于所有其他情况，引理5是否正确？为什么最终算法有效？我们通过以下两个引理证明最终算法中的间接锁依赖是充分必要的。▍引理6：需要检查T2中的间接锁依赖，否则简单的算法就解决了所有问题。引理6表明，由于读写锁的存在，我们不能只检查直接的锁依赖。▍引理7：T2的边界是当前线程的锁栈，足够了。根据引理2和引理3，任何死锁都可以转化为双线程ABBA死锁，T1只能贡献AB，T2必须贡献BA。这里T2不仅是一个虚拟线程，还是一个实际的物理线程，所以T2需要也只需要检查当前线程。到目前为止，已经描述了一种通用的读写锁死锁预测算法，但还没有得到正式证明。该算法已在Lockdep中实现并提交给Linux内存社区审核（最新版本见https://lkml.org/lkml/2019/8/...）。由于相关性和篇幅有限，这里没有展示算法的一些关键细节。有兴趣的读者可以到上面的链接去了解一下，欢迎提出意见和建议。从最初处理滴滴基础平台大集群爆发的几次严重系统故障，到学习和研究内核死锁预测工具，再到设计实现一种新的通用读写锁死锁预测算法。它充满了不确定性，甚至是戏剧性，但整个过程和最终的结果对我来说都是非常值得的。我觉得这种体验就像电影里阿甘的奔跑《阿甘正传》：到达一个目的地后，我想多跑一点，当我到达下一个目的地时，我设定了一个新的更远的目标。我也认为普通作品和世界一流作品的区别不在于起点，而在于终点。就看几个更远的目标有没有实现。同时也欢迎大家关注滴滴科技公众号，我们会及时发布最新的开源信息和技术资料！
