线程验证在Linux内核代码中的应用

理论计算机科学电子笔记174（2007）49-61www.elsevier.com/locate/entcs线程验证-经验报告Robert P. Cook罗伯特·库克1，2佐治亚南方大学计算机科学系Statesboro，GA 30460 U.S.A摘要本文详细介绍了作者在Linux内核代码、RedHatLinuxPOSIX线程库、作者开发的可移植PThread库等四个应用程序中的线程验证经验和一个轻便型原型机。 根据作者保留字：验证、模型检查、重用库、POSIX线程、Linux1引言本文的主题是，存在一个频谱的分析技术之间的那些用于编码的并发算法和那些用于验证并发算法。软件工程师忽视验证技术，因为他们套用柏拉图的话，“未经检验的并发算法不值得使用.”3.问题是本文详细介绍了作者每一个例子都说明了仅仅依靠传统测试作为验证技术是徒劳的。应用一系列验证方法的原则，即使没有一种方法完全成功，也可以暴露出仅通过测试难以发现的1 电子邮件地址：bobcook@GeorgiaSouthern.edu2鸣谢：陆军研究办公室（DAAD 19 -01-1-0473）和NASA对本研究的支持。3 苏格拉底，柏拉图，对话，道歉1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2007.04.00650R.P. Cook/Electronic Notes in Theoretical Computer Science 174（2007）492Linux ID分配Linux是验证示例的一个很好的来源，因为代码被发布在网上，并且IBM和其他公司已经有了一个协调的项目（Linux测试项目[4]），通过测试来提高Linux代码库的可靠性。不幸的是，没有根据核查分析进行类似的项目。考虑生成唯一id号的常见问题。操作系统需要在许多上下文中生成唯一的id。id可能需要在本地唯一或在时间和空间上唯一。例如，Microsoft在这个例子中，我们考虑从固定范围的正整数生成进程id（pids）的问题要求是1）给定的pid来自固定范围内，2）它不被分配一次以上而不被释放，3）在返回错误之前分配范围内的所有整数，4)释放的ID必须处于分配状态，5）ID不能被释放一次以上，6）如果当前没有PID可用，则返回0，以及7）任何解决方案都是线程安全的。前几百个id是为守护进程保留下面的解决方案（图1）[1]来自Linux操作系统的内核。cv2.4.28.使用存储器存储数据和数据，以处理所有类型的问题。该解决方案具有不需要辅助数据结构的优点。该算法仅在进程ID尚未被其他进程使用时才分配该进程ID第一个验证步骤是在Promela中重新编码算法，以输入到SPIN [5]模型检查器。图2列出了一个Promela代码片段。Promela支持多线程编程，具有用于线程间通信的保护（先决条件）语句和通道（消息队列）有趣的是，通道和它们的前身UNIX管道都没有被然而，在新的Sony/IBM Cell Broadband Engine [9]中，信道和邮箱是第一类硬件原语，因此这些抽象在编程语言语法中的出现可能即将到来。结果模型的执行发现了两个bug;不幸的是，这两个bug都在SPIN中。一个是固定的，一个不是。不幸的是，后一个bug（称为第二个验证步骤是应用我们称之为“细粒度并发测试”的技术作者开发的StarLite[6]编程环境运行时有一个不寻常的特性，即时钟周期与指令执行有关（每N个指令产生一个时钟中断）。因此，时钟节拍可以与每个指令提取周期一样频繁地被调度。通过基于时钟节拍调度线程，可以实现细粒度的多路复用，这在物理机器上是不可能的StarLite测试算法的唯一变更是将“最后保留pid”从300减少一种算法-R.P. Cook/Electronic Notes in Theoretical Computer Science 174（2007）4951intlast =LAST r;自旋锁定试验 lastpid lock = SPIN_UNLOCKED;public voidrun（）{intmax= int MAX;structtask struct task;intpid，int pid;spin lock（lastpid lock）;if（（++last pid）0x int n）{last pid = LAST R PID;gotoinside;}if（last pid> = next）{inside：next safe = PID MAX; read lock（tasklist lock）;repeat：对于每个任务（p）{if（pid== last pid）{if（++last pid> = next safe）{if（last pid 0x）{last pid = LAST R PID;}next safe = PID MAX;}if（last pid == pid）{return 0;read unlock（tasklist lock）;spin unlock（lastpidlock）;return 0;}goto重复;}// ifpid==if（p−>pid> last pid next safe>p−> pid）{next safe =p−> pid;}}//对于每个read unlock（tasklist）;}// if last pid>=next safepid = last;spin unlock（lastpid lock）;returnpid;}Fig. 1. Linux分配进程ID（获取pid）52R.P. Cook/Electronic Notes in Theoretical Computer Science 174（2007）491 #define MAX 42 proctype A（chan in，/文件ex.2/3 {byte mt;/消息数据/4bit vr;5 S1：mt =（mt+1）%MAX;6滚出去！mt，1;7gotoS2;8 S2：在？vr;9如果10：：（vr == 1）−>gotoS1十一： (vr== 0）−>goto S312：：printf（13五;14 S3：出局！mt，1;15gotoS2;16 S4：in？vr;17如果18：：转到S119：： printf（20五;21 S5：出局！mt，0;22转到S4 23}图二. Promela代码示例N= 15（或更小）的Rithm可以归纳地证明对于较大的N值是有效的。一个有趣的线程验证问题是决定什么时候可以进行归纳证明，以及什么时候问题已经被最佳地缩小在第一次运行StarLite时，暴露了两个问题。 两者都是“显而易见的”，但提交人却没有事先想到。 首先，算法“读取”任务列表的状态，然后释放锁。 在这一点上，不变的“新pid不“名单”就成问题了。如果在任务列表中存储了旧分配之前的最后一个pid周期，则可以多次分配相同的id。第二个错误发生在最后一个PID计数超过PID M AX之后。 分配的是“最后保留的pid”，而不是该值加1。第三个问题，也是最后一个问题，是根据作者的经验发现的，但也可以通过机械的方式发现。一旦最后一个pid被在Linux v2.4.28之后，pid管理算法升级为使用位图作为id分配数据结构来动态分配页面下面的两个代码片段（图3）说明了经典的由于页面分配是耗时的，第一个种族（地图→页面）可能会被暴露和补偿，尽管是以非最佳的方式。第二个竞争条件（map→nr free）只覆盖了三个或四个指令，R.P. Cook/Electronic Notes in Theoretical Computer Science 174（2007）4953如果（不太可能）！map−>page））{longpage = get zero page（GFP KERNEL）;/如果有人和我们一起比赛，请释放页面/spin lock（pidmap lock）;if（map->page）free page（page）;其他map−>page =（voidname）page;spin unlock（pidmap lock）;如果（不太可能）！map−>page））破碎;}if（probably（atomicread（map−> nr free）{执行{如果（！ test and set bit（o = set，map−> page））{atomic dec（map−>nr free）;return pid;returnpid;}pid = pid（map）; pid = pid（map）;}}图3.第三章。cfth159 Code Snippets所以它的暴露概率很低。当多个线程发现nr free等于1时会发生错误。只有一个调用者获得空闲ID，而其余线程搜索完整的位图。3个红帽POSIX线程2004年，作者获得了NASA肯尼迪航天中心的夏季奖学金，以修改Red Hat NPTL库，以支持POSIX Threads实时特性。这项任务需要对Linux内核futex的实现进行调查[7]，这可能是现代操作系统历史上研究最少的同步原语。futex是一个快速的用户空间互斥体。它是快速的，因为“忙”测试是用非特权指令执行的。操作系统内核只在排队和延迟时被调用。不幸的是，NPTL库与Linux内部和futex实现紧密绑定。事实证明，修改库和54R.P. Cook/Electronic Notes in Theoretical Computer Science 174（2007）49Linux内核在允许的时间内。然后，作者在那个夏天花了一部分时间分析NPTL代码中选定模块的正确性NPTL于2002年首次发布，带有广泛的测试套件。在作者发现错误之前，代码已经发布并使用了近两年。图4列出了用于读/写锁的“get-read-lock”方法的实现（带有错误）即使在rwlock的SPIN模型完成之前，很明显，实现中存在问题。仅仅是执行验证审查的行为就可以具有指导意义！在rdlock的情况下，如果写入器排队，则读取器必须等待（写入器优先）。此时，读取器排队计数递增。但是，它永远不会减少！！Red Hat承认了这个bug，并在下一个版本中修复了它。第二个问题是通过模型检查发现的，因为释放数据锁以在写入器上执行futex等待，然后重新获取锁。这导致重新进入数据锁队列时，futex队列中的所有读取器都被打乱，从而导致可能的无限超越或饥饿问题。4便携式原型如前所述，事实证明修改红帽POSIX线程实现以支持POSIX实时特性是不可行的;因此，设计了一个新的库。除了实时要求外，还认为新图书馆应尽可能便于携带。例如，它至少可以作为一个“参考”实现。库的源代码和测试结果发布在Web上 [3]与作者实现的库一致，决定开发一个原型HandyVerification应用程序。有几个目标。首先，检查器必须使用C/C++语法。其次，原型必须支持C/C++代码的自动或半自动注释，以使任何程序都能被检查。第三，原型必须为发现的错误提供线索。第四，状态空间搜索必须以足够简单的方式封装Handyx的实现基于两个映射。首先，程序的变量被重命名为结构元素。其次，将代码划分为代码“条”。每个条带包含一个涉及全局变量的干扰点（读写或读写）或一个表示控制流程决策的点。代码条具有良好的逐段组合特性，只要组件已被验证。因此，可以通过级别来检查模块层次结构。图5列出了可移植PThreads库中屏障实现的代码带（转换前）。请注意，访问/测试步骤，如在B中，被分解为两个条目“b，IF. . ”在当前的HandyCable原型中，只实现了检查。地带R.P. Cook/Electronic Notes in Theoretical Computer Science 174（2007）4955publicint findDuplicate（int findDuplicate）{return 0;互斥锁 （rwlock−> 数据lock）;而（1）{/如果没有writer，则获取rwlock.//你... 如果没有作家在等，或者我们更喜欢读者。/如果（rwlock−> 数据 作者== 0&&（啊！rwlock−> 数据 已排队的|| rwlock−> data. （== 0））{/n递增读取器计数器。 避免过度疲劳。 /if（unlikely（++rwlock−> data.nr readers ==0））{/阅读器数量超过1000。/−−rwlock−>data。nr读取器;结果=EAGAIN;}破碎;}/if rwlock −> data.作者//n确保我们没有将rwlock作为writer持有。 /if（unlikely（rwlock−> 数据作家== THREAD GETMEM（THREAD SELF，tid）{return EDEADLK;破碎;}请记住，我们是一个读者。 /if（unlikely（++rwlock−> data.nr readers queued == 0））{/n排队的读取器数量超过1000。 /−−rwlock−>data。nr个读取器排队;结果=EAGAIN;破碎;}intwaitval = rwlock−>data. 读者觉醒;/解锁。/lll互斥体解锁（rwlock−> 数据lock）;等待作者完成。/我会futex等待 （&rwlock−> 数据 readers wakeup，waitval）;把锁打开。/互斥锁 （rwlock−> 数据lock）;}/while1/我们完成了，解锁。/lll互斥体解锁（rwlock−> 数据lock）;返回结果;}见图4。 Linux glibc MPTL rwlock56R.P. Cook/Electronic Notes in Theoretical Computer Science 174（2007）49public intfindDuplicate（int findDuplicate）{隆一， j;断言 （ 障碍！=NULL）;/NULLj =势垒−>循环;i = InterlockedDecrement（barrier−> queued）;如果（i> 0）{Lock（barrier−>q[j]）;BlockSelf（barrier−> q[j]）;/B/返回0;}断言 （i = 0）;i =屏障−>计数;/C/returni;barrier−>cycle = 1;/D/assert（LookHead（barrier−>q[barrier−>cycle]）== NULL）;对于（i−−; i！= 0;i−−）{/E/int p;p = RemoveHead（barrier−>q[j]）;assert（p！=空值）;return（p）;}断言 （ return（0）;assert（LookHead（barrier−>q[j]）== NULL）;returnPTHREAD BARRIER SERIAL THREAD;}图五. HandyCode Strips（转换前）识别和变量转换是手动执行的此外，没有实现并行搜索。所有状态变量都被收集到一个结构中，该结构包含一个控制信息结构、一个全局变量结构和一个用于每个过程的结构（包含局部变量）。当前不支持递归。下面是一个例子。R.P. Cook/Electronic Notes in Theoretical Computer Science 174（2007）4957类型定义结构{p线程屏障t线程屏障;隆一， j;int函数返回值;}prWait;类型定义结构{控制控制;/检查器数据结构/全局全局变量;/n指向全局变量的指针/nprWait wait;/n局部变量n/}State;见图6。 国家结构每一条都被编码为一个类型为“void *"的参数的函数。预处理器#define宏用于将变量引用转换为等效的State结构引用。只有具有复制构造函数的C++类才能被检查，因为状态必须在每个决策点复制。此外，任何挂起（排队）线程的原语都被简单地标记为“排队”。检查器在每一步都查找这些标记，以将这些线程从“就绪”列表中删除。这种转换是必要的，因为检查器是一个单线程;在嵌套过程中阻塞将阻塞检查。如果使用单独的线程来评估每个“状态”，则可以解除此然而，这一备选办法没有得到探讨。图7列出了转换后的屏障代码。当前原型的实现假设一个线程一次只能在一个队列中。在每个状态结构的控制信息中，为每个状态分配编号。图中的条代码阵列包含检查器关于每个条执行的“结果”的信息。IF选择器后面有三个参数，它们是要执行的条带和IF TRUE（暂停/退出）和IF TRUE（CDE）的数组索引。. ）案件。图8和图9列出了HandyData在屏障示例中的示例输出有两个线程（0和1）。 请注意，对于“串行”线程， 以“击败”试图阻塞的较早线程。结果是一个程序错误，而不应该存在。图1列出了错误状态的解释HandyData只是一个原型，它在“概念证明”的道路上迈出了一步。还有许多工作要做。例如，可以通过添加语义提示来改进实现，以减少搜索路径的数量。5挑战• 虽然Linux内核具有高效的算法和出色的架构组织，但它在面向对象设计方面失败了。面向对象的实现将有助于部分验证，如果不是全部的• 如果有一个Linux验证项目来比较，58R.P. Cook/Electronic Notes in Theoretical Computer Science 174（2007）49public intfindDuplicate（intfindDuplicate）{L（x）−>wait.j =L（x）−>wait.barrier−> cycle;返回下一步;}public intfindDuplicate（intfindDuplicate）{L（x）−>wait.i =InterlockedDecrement（L（x）−>wait.barrier−> queued）;如果（i> 0）{assert（CONTROL（x）−>queue ==EMPTY）CONTROL（x）−>toQueue = L（x）−>wait.j; L（x）−>wait.functionreturn value = 0;returnIF TRUE;}returnif;}public intfindDuplicate（intfindDuplicate）{return（L（x）->wait. i）;L（x）−>wait.i = L（x）−>wait.barrier−>count; L（x）−>wait.barrier−>queued = i;返回下一步;}intD（void boundaryx）{L（x）−>wait.barrier−>cycleboundary = 1;returnNEXTSTEP;}public intfindDuplicate（intfindDuplicate）{for（L（x）−> wait.i −−; L（x）−>wait.i！= 0; L（x）−>wait.i−−）{Wakeup（L（x）−> wait.j）;}assert（L（x）−>wait.i ==0）;assert（isEmpty（L（x）−>wait.j））;L（x）−>wait.函数返回值= PTHREADBARRIER SERIAL THREAD;返回下一步;}条码阵列R.P. Cook/Electronic Notes in Theoretical Computer Science 174（2007）49590，A，IF，B，8，6，SUSPEND，EXIT，C，D，E，RESUME，EXIT[0 1 2 3 4 5iftrue 7 8 9 10 11 12]见图7。HandyCode Strips（转换后）60R.P. Cook/Electronic Notes in Theoretical Computer Science 174（2007）49、0A、1A、1IF、0IF、1挂起、0C、0D、0E、0恢复、1退出、0退出、正常、0A、1A、1IF、0IF、0C、1暂停、0D、0E、0恢复、1退出、0退出、正常、0A、1A、1IF、0IF、0C、0D、1暂停、0E、0恢复、1退出、0退出、正常、0A、1A、1IF、0IF、0C、0D、0E、1暂停、0恢复、0退出、1退出、正常、0A、1A、1IF、0IF、0C、0D、0E、0恢复、ERR、0A、1A、1IF、0IF、0C、0D、0E、1暂停、0恢复、1退出、0退出、正常、0A、1A、1IF、0IF、0C、0D、1暂停、0E、0恢复、1退出、0退出、正常、0A、1A、1IF、0IF、0C、1暂停、0D、0E、0恢复、1退出、0退出、正常、0A、1A、1IF、1暂停、0IF、0C、0D、0E、0恢复、1退出、0退出、正常、0A、1A、1IF、0IF、1挂起、0C、0D、0E、0恢复、1退出、0退出、正常、0A、1A、1IF、0IF、0C、1暂停、0D、0E、0恢复、1退出、0退出、正常、0A、1A、1IF、0IF、0C、0D、1暂停、0E、0恢复、1退出、0退出、正常、0A、1A、1IF、0IF、0C、0D、0E、1暂停、0恢复、0退出、1退出、正常、0A、1A、1IF、0IF、0C、0D、0E、0恢复、ERR、0A、1A、1IF、0IF、0C、0D、0E、1暂停、0恢复、1退出、0退出、正常、0A、1A、1IF、0IF、0C、0D、1暂停、0E、0恢复、1退出、0退出、正常、0A、1A、1IF、0IF、0C、1暂停、0D、0E、0恢复、1退出、0退出、正常、0A、1A、1IF、0IF、1挂起、0C、0D、0E、0恢复、1退出、0退出、正常、0A、1A、0IF、1IF、0暂停、1C、1D、1E、1恢复、0退出、1退出、OK、0A、1A、0IF、1IF、1C、0暂停、1D、1E、1恢复、0退出、1退出、OK、0A、1A、0IF、1IF、1C、1D、0挂起、1E、1恢复、0退出、1退出、OK、0A、1A、0IF、1IF、1C、1D、1E、0暂停、1恢复、0退出、1退出、正常、0A、1A、0IF、1IF、1C、1D、1E、1恢复、ERR、0A、1A、0IF、1IF、1C、1D、0挂起、1E、1恢复、0退出、1退出、OK、0A、1A、0IF、1IF、1C、0暂停、1D、1E、1恢复、0退出、1退出、OK、0A、1A、0IF、1IF、0暂停、1C、1D、1E、1恢复、0退出、1退出、OK、0A、1A、0IF、0暂停、1IF、1C、1D、1E、1恢复、0退出、1退出、OK、0A、1A、0IF、1IF、1C、0暂停、1D、1E、1恢复、0退出、1退出、OK、0A、1A、0IF、1IF、1C、1D、0挂起、1E、1恢复、0退出、1退出、OK、0A、1A、0IF、1IF、1C、1D、1E、0暂停、1恢复、0退出、1退出、正常、0A、1A、0IF、1IF、1C、1D、1E、1恢复、ERR、0A、1A、1IF、0IF、0C、0D、0E、1暂停、0恢复、1退出、0退出、正常、0A、1A、1IF、0IF、0C、0D、1暂停、0E、0恢复、1退出、0退出、正常、0A、1A、1IF、0IF、0C、1暂停、0D、0E、0恢复、1退出、0退出、正常、0A、1A、1IF、0IF、1挂起、0C、0D、0E、0恢复、1退出、0退出、正常、0A、1A、0IF、1IF、0暂停、1C、1D、1E、1恢复、0退出、1退出、OK、0A、1A、0IF、1IF、1C、0暂停、1D、1E、1恢复、0退出、1退出、OK、0A、1A、0IF、1IF、1C、1D、0挂起、1E、1恢复、0退出、1退出、OK、0A、1A、0IF、1IF、1C、1D、1E、0暂停、1恢复、0退出、1退出、正常、0A、1A、0IF、1IF、1C、1D、1E、1恢复、ERRR.P. Cook/Electronic Notes in Theoretical Computer Science 174（2007）4961见图8。 手动代码输出（线程0 1）60R.P. Cook/Electronic Notes in Theoretical Computer Science 174（2007）49、0A、1A、0IF、1IF、1C、1D、0挂起、1E、1恢复、0退出、1退出、OK、0A、1A、0IF、1IF、1C、0暂停、1D、1E、1恢复、0退出、1退出、OK、0A、1A、0IF、1IF、0暂停、1C、1D、1E、1恢复、0退出、1退出、OK、0A、1A、0IF、0暂停、1IF、1C、1D、1E、1恢复、0退出、1退出、OK、0A、1A、0IF、1IF、1C、0暂停、1D、1E、1恢复、0退出、1退出、OK、0A、1A、0IF、1IF、1C、1D、0挂起、1E、1恢复、0退出、1退出、OK、0A、1A、0IF、1IF、1C、1D、1E、0暂停、1恢复、0退出、1退出、正常、0A、1A、0IF、1IF、1C、1D、1E、1恢复、ERR、0A、1A、0IF、1IF、1C、1D、0挂起、1E、1恢复、0退出、1退出、OK、0A、1A、0IF、1IF、1C、0暂停、1D、1E、1恢复、0退出、1退出、OK见图9。 手动代码输出（线程0 1）续0A 1A 0IF 1IF 1C 1D 1E 1恢复错误线程0线程10Aj =势垒→循环;j ==01Aj =势垒→循环;j ==00如果i = InterlockedDecrement（barrier→queued）;i == 11如果i = InterlockedDecrement（barrier→queued）;i == 01Ci =屏障→计数;屏障→=计数;i == 21D势垒→循环数n = 1;IEfor（i−−; i！= 0; i−−）{int p;p = RemoveHead;线程1遇到了违反不变量的情况，即N-1个线程排队。线程0更改了全局状态，以指示它被阻塞，而实际上它没有被阻塞。表1屏障错误解释现在已经是一个成熟的LTP引擎。• POSIX Threads需要有一个参考实现，并且需要作为一个生活标准来• 每个POSIX Threads的实现都应该经过验证和测试。• 根据Enea TekSci的说法，如果它是商业性的，它必须获得DO-178 B认证然而，在这方面，R.P. Cook/Electronic Notes in Theoretical Computer Science 174（2007）4961它的软件处理要求是如此耗时和复杂，以致程序员的生产率可能平均低于100行/月。程序中的每一个入口和出口都必须在测试中至少被调用一次，程序中的每一个决策都必须至少采取所有可能的结果一次，并且决策中的每一个条件都必须被证明独立地影响决策的结果。DO-178 B测试是否能保证发现顺序程序中的任何错误？多线程程序？研究界对当前DO-178 B软件验证计划的看法是什么• 当前的模型检查器与模型语言联系得太紧密。应该构建一个• 模型检查基准测试的现状如何？性能和质量标准是什么？• OpenMP标准利用“杂注“来注释代码。每个• Sony/IBM Cell Broadband Engine对程序员、程序验证员和优化员提出了复杂的挑战• 有没有可能标准化XML中间表示，以作为模型检查器的输入？• Java和Ada用第一类语法符号来支持并发编程。下一步是什么？• 是时候抛弃二维编程符号，转而使用多维XML注释来记录程序从需求到目标机器语言的细化了吗引用[1] http://lxr.linux.no/source/kernel/fork.c[2] http://sourceware.org/cgi-bin/cvsweb.cgi/libc/nptl/? cvsroot=glibc[3] http://bcook.cs.georgiasouthern.edu/pthreads/[4] http://ltp.sourceforge.net/[5] Holzmann，Gerard J.，The SPIN Model，Addison-weseley（2003）[6] 库克，罗伯特P，StarLite操作系统，在：关键任务计算操作系统编辑K。Gordon，P. Hwang，A. Agrawala，IOS Press，（1992）2-10.[7] Franke，Hubertus，Rusty Russell，Matthew Kirkwood，Fuss，Futexes和Furwocks：Linux中的快速用户级锁定。Ottawa Linux Symposium，（2002）。[8] Hilderman ， Vance ， Certifying an RTOS to DO178B ： Tips Tales ， The Open Group Real-Time andEmbedded Systems Forum，Amsterdam，Netherlands（2001年10月）。[9] http://www-128.ibm.com/developerworks/power/cell/