分类： C/C++
2010-09-11 20:37:12
大部分软件开发项目依靠结合代码检查、结构测试和功能测试来识别软件缺陷。尽管这些传统技术非常重要，而且能发现大多数软件问题，但它们无法检查出当今复杂系统中的许多共性错误。本文将介绍如何避免那些隐蔽然而常见的错误，并介绍的几个技巧帮助工程师发现软件中隐藏的错误。
结构测试或白盒测试能有效地发现代码中的逻辑、控制流、计算和数据错误。这项测试要求对软件的内部工作能够一览无遗(因此称为"白盒"或"玻璃盒")，以便了解软件结构的详细情况。它检查每个条件表达式、数学操作、输入和输出。由于需要测试的细节众多，结构测试每次检查一个软件单元，通常为一个函数或类。
代码审查也使用与实现缺陷和潜在问题查找同样复杂的技术。与白盒测试一样，审查通常针对软件的各个单元进行，因为一个有效的审查过程要求的是集中而详尽的检查。
与审查和白盒测试不同，功能测试或黑盒测试假设对软件的实现一无所知，它测试由受控输入所驱动的输出。功能测试由测试人员或开发人员所编写的测试过程组成，它们规定了一组特定程序输入对应的预期程序输出。测试运行之后，测试人员将实际输出与预期输出进行比较，查找问题。黑盒测试可以有效地找出未能实现的需求、接口问题、性能问题和程序最常用功能中的错误。
虽然将这些技术结合起来可以找出隐藏在一个特定软件程序中的大部分错误，但它们也有局限。代码审查和白盒测试每次只针对一小部分代码，忽视了系统的其它部分。黑盒测试通常将系统作为一个整体来处理，忽视了实现的细节。一些重要的问题只有在集中考察它们在整个系统内相互作用时的细节才能被发现；传统的方法无法可靠地找出这些问题。必须整体地检查软件系统，查找具体问题的特定原因。由于详尽彻底地分析程序中的每个细节和它与代码中所有其它部分之间的相互作用通常是不大可能的，因此分析应该针对程序中已经知道可能导致问题的特定方面。本文将探讨其中三个潜在的问题领域：
* 堆栈溢出
* 竞争条件
* 死锁
读者可在网上阅读本文的第二部分，它将探讨下列问题：
* 时序问题
* 可重入条件
在采用多任务实时设计技术的系统中，以上所有问题都相当普遍。
堆栈溢出
处理器使用堆栈来存储临时变量、向被调函数传递参数、保存线程“状态”，等等。如果系统不使用虚拟内存(换句话说，它不能将内存页面转移到磁盘上以释放内存空间供其它用途)，堆栈将固定为产品出厂时的大小。如果由于某种原因堆栈越出了编程人员所分配的数量范围，程序将变得不确定。这种不稳定可能导致系统发生严重故障。因此，确保系统在最坏情况下能够分配到足够的堆栈至关重要。
确保永不发生堆栈溢出的唯一途径就是分析代码，确定程序在各种可能情况下的最大堆栈用量，然后检查是否分配了足够的堆栈。测试不大可能触发特定的瞬时输入组合进而导致系统出现最坏情况。
堆栈深度分析的概念比较简单：
1. 为每个独立的线程建立一棵调用树。
2. 确定调用树中每个函数的堆栈用量。
3. 检查每棵调用树，确定从树根到外部“树叶”的哪条调用路径需要使用的堆栈最多。
4. 将每个独立线程调用树的最大堆栈用量相加。
5. 确定每个中断优先级内各中断服务程序(ISR)的最大堆栈用量并计算其总和。但是，如果ISR本身没有堆栈而使用被中断线程的堆栈，则应将ISR使用的最大堆栈数加到各线程堆栈之上。
6. 对于每个优先级，加上中断发生时用来保存处理器状态的堆栈数。
7.如果使用RTOS，则加上RTOS自身内部用途需要的最大堆栈数(与应用代码引发的系统调用不同，后者已包含在步骤2中)。
除此之外，还有两个重要事项需要考虑。首先，仅仅从高级语言源代码建立的调用树很可能并不完善。大部分编译器采用运行时库(run-time library)来优化常用计算任务，如大值整数的乘除、浮点运算等，这些调用只在编译器产生的汇编语言中才可见。运行时库函数本身可能使用大量的堆栈空间，在分析时必须将它们包括进去。如果使用的是C++语言，则以下所有类型的函数(方法)也都必须包含到调用树内：结构器、析构器、重载运算符、复制结构器和转换函数。所有的函数指针也都必须进行解析，并且将它们调用的函数包含进分析之中。
第二，编译器使用一个C库来实现memcpy()、cos()和atof ()等标准函数，而这些例程的源代码可能无法得到。如果能够得到它们的源代码，就有可能确定程序用到的每个库调用在最坏情况下的堆栈使用数量。如果这些库只包含在目标文件中，则编译器厂商必须提供每个库例程使用的堆栈数。如果没有这些信息，就无法通过分析来确定最坏情况下程序使用的最大堆栈数。幸运的是，许多面向嵌入式系统的编译器厂商都提供这些信息。
通常，每次一个函数被调用时，编译器将使用堆栈来保存返回地址并传递函数参数。函数的自动(局部)变量通常也在堆栈当中。不过，由于编译器会尽可能通过将参数或局部变量放入寄存器来优化代码，因此检查汇编语言以精确地确定堆栈用量非常重要。编译器也有可能在代码中的其它地方选择使用堆栈，如用堆栈来保存中间计算结果。
有些与编译器一起打包销售的开发环境包含生成调用树的工具，还有许多第三方的调用树生成工具。但是，除非它们能够对汇编语言进行分析，否则这些工具可能会遗漏运行时库和C库的调用。不过无论在哪种情况下，开发分析汇编语言文件并提取函数名称以及各函数内部调用的脚本都比较简单。分析的结果可写入一个文件，而这个文件能够方便地输入到表格之中。
确定了各个函数的堆栈用量之后，必须计算每个线程所需的最大堆栈数。由于一般程序通常涉及数百个函数，调用跨越多层深度，处理这些信息的一种简便方法就是采用分析表格。如表1所示，表格的各行包含了函数名称、该函数使用的最大堆栈数(包括调用其它函数所需的堆栈数)，以及它调用的所有函数的清单。通过编程控制，这个表格从每个函数的"根"开始迭代循环，计算该函数及其调用的所有函数需要的堆栈。这些信息存放在堆栈路径列中，这样，采用每个线程根函数(如main)的堆栈路径数据就可以方便地计算出需要的最大堆栈数了。这个过程包含了先前介绍的堆栈分析过程中的前四个步骤。
有时候，采用堆栈深度分析过程可能是无法做到，或者是不实际的。如果无法得到运行时库或C库的源代码，而编译器厂商又没有提供任何堆栈使用信息，就不可能进行完整的堆栈分析。在这种情况下，有两种选择：
1. 在测试期间，观察堆栈所能达到的深度，并保证有较大的堆栈空间余量。
2. 检测堆栈溢出，并采取改进措施。
观察堆栈深度的方法很简单:
* 向整个内存堆栈区写入一个特定的数据图案符号，如55AA。
* 在预期使用最大堆栈空间的条件下运行系统。
* 使用仿真器或其它工具检查堆栈存储区，看有多少符号图案由于堆栈的使用而被改写了。
当然，这些步骤并不能保证在一些不同条件下不会需要更多的堆栈，但确实可以表明所需要的最小堆栈数。
使用带内存管理单元(MMU)的处理器时，有可能检测出运行时的堆栈溢出现象。MMU将内存划分为多个区域，用一个受保护的内存段来“警戒”堆栈区域。发生堆栈溢出时，处理器将访问这个受保护段。这个操作将引发一个异常事件(如产生SIGSEGV信号)，可被程序捕获到。创建线程时，与实时POSIX标准兼容的RTOS提供有这种堆栈警戒功能选项，大大简化了编程人员的工作。GNU工具等其它开发环境包含有编译器开关，可在程序中添加实现堆栈警戒功能所需的代码，但它们仍然依靠底层操作系统来有效地处理堆栈溢出。但是，按照这种方式检测溢出还只是问题的一部分。为了使这类设计更为有效，系统必须能够从堆栈溢出中恢复过来并继续正确地工作。
在一个对安全或任务要求严格的应用中，系统运行时在测试或检测堆栈溢出期间监视堆栈的深度可能并不是一项足够的风险控制措施。对于一些应用，必须确保系统绝对不会越出所分配的堆栈范围；只有通过完整的堆栈深度分析才能证明这一点。这意味着，如果整个程序在同一内存空间运行，则必须对所有代码执行这项分析。不过，如果使用MMU，分析常可简化。在设计系统时，可将所有关键代码置于一个或多个独立线程内，而这些线程分别在各自的保护内存段中运行。这样，只要对这些关键线程进行堆栈使用分析就可以了。当然，这项简化设计假定当非关键线程溢出其堆栈并失效时，关键线程仍可正确执行。
由于分析工作所需的堆栈使用数据来自汇编语言清单，因此修改代码时，相应模块的堆栈使用信息必须予以更新。如果使用不同的编译器版本，或者改变了优化设置，也必须复核整个分析过程。在理想情况下，编译器将提供每个函数(如果不是每个线程的话)的堆栈使用数量，因为它拥有计算需要的所有信息。例如，瑞萨公司提供有Call Walker，这是该公司高性能的Embedded Workshop开发环境的一部分。这个工具可以图形化地显示每个函数使用的调用树和堆栈，包括运行时库和C库的函数。Call Walker也能找出使用堆栈数量最大的路径。使用这样的工具可以实现步骤1到步骤3的自动化。
竞争条件
当两个或更多独立线程同时访问同一资源时，就出现了竞争条件。竞争条件的影响多种多样，取决于具体的情况。清单1解释了一个潜在的竞争条件。函数Update_Sensor()通过调用get_raw()来读取传感器的原始数据。在处理过程中，该数据被乘上一个定标因子，并加上一个偏移量。处理是在该数据的一个临时副本上进行的，然后，该临时副本被写入共享变量。
如果在数据写入之前，使用shared_sensor的另一个线程或ISR先占(preempt)了这个线程，它将得到原来的传感器读数。使用临时副本可以防止先占线程读取只经过部分处理的数据。不过，如果这些代码在一个数据总线不足32位的处理器上运行，就会存在竞争条件。
在一个8位或16位的处理器上，向shared_sensor的写入操作并不是一次性完成的。在8位处理器上，写入32位浮点值可能需要四条指令，在16位处理器上可能需要两条指令。如果在对shared_sensor进行连续写入中途Update_Sensor()被先占，则先占线程将从由一部分老数据和一部分新数据组成的shared_sensor读取一个数值。根据应用的具体情况，这有可能造成严重的后果。解决的办法是锁定调度程序，或在更新共享变量期间禁止中断。
消除竞争条件通常很简单，但找出隐藏在代码中的竞争条件则需要仔细的分析。
对于由一个循环程序和不同ISR组成的简单系统，分析竞争条件很简单，只需检查每个ISR并识别它引用的所有共享变量。共享变量通常是这些系统中的全局数据，一旦这些共享变量被找出来之后，就可以检查它们在代码中的各次使用情况。每次访问都必须按需要进行保护，以避免潜在的冲突。在简单设计中，一般通过在关键代码段周围禁止中断来实现保护。遵守下列规则可帮助避免竞争问题：
* 如果一个ISR对共享数据进行写入，则该ISR之外的每次可中断的读操作都必须予以保护。
* 如果一个ISR对共享数据进行写入，则该ISR之外的任何读－修－写操作都必须予以保护。
* 如果一个ISR读取共享数据，则对该数据的可中断写操作必须予以保护。
* 如果一个ISR和其它代码都要检查一个硬件状态标志，以便在使用某资源之前确定其可用性，如：
if (!resource_busy)
{
// Use resource
}
则从检查标志之时开始，到硬件设置标志表示资源不可用为止，必须采取保护措施。
对于使用了优先级不同的多个线程的更为复杂的系统，其分析也非常相似。上述规则仍然适用于ISR使用的所有数据。此外，还必须识别出每个线程使用的共享数据。首先从系统中优先级最高的线程开始，找出它与任何优先级较低的线程共享的所有数据，然后按照上述四条规则进行保护。对于软件使用的其它每个优先级，再重复这一过程。
注意，如果系统采用了一种循环调度算法，则特定优先级内的所有线程可在任意时刻相互先占。这意味着前述四条分析规则在考虑较低优先级的线程之外，还必须考虑同一优先级的所有线程。
多线程系统通常使用某种类型的操作系统，它能够提供多种保护选择。可以使用互斥或信号量，或者锁定调度器。有时也可使用其它进程间通信(IPC)基本技术：通过向消息队列发送消息(而非修改共享变量)来表示数据已经改变。在许多情况下，最好由单一线程来管理共享资源，它负责处理所有的读写请求，并在内部防止访问冲突。
在复杂的代码中辨认潜在的竞争条件可能是一项乏味而又耗时的工作。相应的辅助工具从用来识别全局数据访问的简单脚本到先进的动态分析程序如Polyspace Verifier。虽然比较困难，但详尽的代码分析是识别这类错误的唯一途径。测试不大可能能够建立重复触发竞争条件所需的精确时序序列。
死锁
在共享资源的系统中，防止访问冲突极为重要，但这有可能导致另一个问题：死锁。当通过"锁定"一个资源来防止任何其它线程访问这个资源，以避免竞争条件时，必须对设计进行评估，确保绝对不会发生死锁。死锁测试通常没有什么效果，因为只有某种特定顺序的资源锁定才可能产生死锁，而一般的测试不大可能导致这种顺序。
死锁只不过是多线程环境中一个锁定资源的问题。以下四个条件必须同时具备，才会发生死锁。防止其中任何一个条件出现都可以排除死锁的可能性：
* 相互排除---每次只有一个线程可以使用某个锁定的资源；
* 非先占---其它线程不能强迫另一个线程释放资源；
* 保持并等待---线程在等待需要的其它任何资源时，保持它们已经锁定的资源；
* 循环等待---存在一个线程循环链，其中每个线程保持链中下一个线程所需要的资源。
图1中的资源分配图是死锁问题的一个例子。线程1首先锁定Buf资源，在保持Buf时，指向Bus，然后是Mux。如果线程1一直运行到结束，它最终将释放所有这些资源。线程2运行时，必须指向Bus、Sem，最后是Mux。线程3运行时，需要Sem和Buf。
在这个设计实例中，无法保证任何一个线程能够在另一个线程开始执行之前结束。如果一个线程不能得到需要的某个资源，它将挂起执行(阻塞)，直到该资源有效为止。在系统运行过程中，各线程都将对资源进行锁定或解锁。由于各线程运行和指向其资源的相对时序各不相同，有可能出现由于各个线程正在等待被其它线程保持的资源，导致所有线程都无法运行的情况。例如，如果线程1保持Buf，线程2保持Bus，而线程3已经取得了Sem，则系统将发生死锁。因为按照从Buf到Bus到Sem，再回到Buf的线程分配箭头，循环等待条件得到了满足。
潜在死锁问题识别出来之后，通常很容易进行修复。在图2中，对线程3进行了修改，使其在得到Sem之前首先设法指向Buf。这样，循环等待的条件就被打破了，系统将不会再受到死锁的影响。
一些操作系统过多地使用消息传递来进行线程间通信和同步。在这些类型的系统中，当某线程向另一个线程传递消息时，发送线程将阻塞，直到从接收线程收到响应为止。接收线程通常将一直阻塞到从其它某个线程接收到一个消息为止。这些结构中也会发生死锁。为了给一个基于消息的操作系统建立一张资源分配图，我们利用消息通道来模拟分配的资源。图3是一个例子。线程2建立了通道T2 Ch，当它未因为等待这个通道上的一个消息而阻塞时，线程2就将"锁定"这个通道。当它阻塞并等待一个消息时，另一个线程可在这个通道上向它发送一个消息，并且这个消息将立即被接收到。
现在考虑下面这个系统：线程1指向Mutex并在通道T2 Ch上向线程2发送消息。在线程2中的某个地方，线程2在通道T3 Ch上向线程3发送消息。线程3也在通道T4 Ch上向线程4发送消息。在线程4中的某个地方，它也尝试指向Mutex，如果得不到，它就将阻塞。显然，各资源之间存在一条循环路径，这表明有可能发生死锁。例如，如果某一时刻线程1保持Mutex而线程4尝试指向它，线程4就将在Mutex上阻塞。然后当线程3尝试在通道T4 Ch上向线程4发送一个消息时，线程3将阻塞，等待来自线程4的应答(因为线程4是由于等待Mutex而阻塞，不是为了等待这个消息)。类似地，当线程2尝试向线程3发送一个消息时，将被阻塞；线程1尝试向线程2发送一个消息时也将阻塞，由于它仍然保持着Mutex，所以系统将发生死锁。
对付死锁的最容易的办法是通过设计进行避免。采用以下任何一条设计约束都可排除死锁出现的可能性：
* 任意时刻线程锁定的资源不超过一个。
* 线程开始执行前就完全分配它所需的全部资源。
* 指向多个资源的线程必须按照一种系统范围的预设顺序来锁定(并释放)这些资源。
如果无法通过设计来避免死锁，则应该建立资源分配图。检查资源分配图可以识别潜在的死锁。通过仔细跟踪系统中的所有线程和它们锁定的共享资源，可以维护资源分配图并周期性地进行检查，及时发现循环等待的特征。
建立资源分配图需要识别每个受保护的共享资源，以及指向其中某一资源的所有线程。如果使用一个操作系统，可以采用下面的过程步骤：
1. 识别所有可能阻塞的系统调用，如Mutex_Lock()，每个受保护的共享资源总是有一些与访问它有关的阻塞调用。
2. 识别出获取共享资源的阻塞调用之后，在源代码中查找它们的各次调用情况。
3. 对于每次调用，记录下指向资源的线程名称和该资源的名称。通常调用本身将受保护的资源作为一个参数来传递，调用在源代码中所处的位置表明了哪个线程需要该资源。通过这种方式，可以识别出所有受保护的资源以及分配资源的线程。
4. 建立资源分配图，并检查是否有任何资源存在循环路径。当线程和共享资源较少时，画出资源分配图比较简单。在较为复杂的系统中，最好将这些信息输入分析表格，并编写一个宏来检查线程和资源分配结构，以识别潜在的死锁。编写好宏之后，就可以快速地对资源分配变化进行重新评估。编写宏时，可以忽略不会导致死锁的资源之间的循环。在表2所示的例子中，各种资源之间有许多循环，但只有线程6和线程7之间可能存在死锁。
在一些类型的系统中，预先确定每一个共享资源并建立分配图是不实际或不可能的。此时可以增加一些额外的代码，以便在系统运行时检测出潜在的死锁。许多不同的算法都致力于优化这个检测过程，但本质上它们几乎都动态地建立某种资源分配图。只要有线程请求、分配或释放资源，分配图就会被修改和检测，以确定是否存在表明潜在死锁的循环路径。
检测到某个死锁之后，唯一的克服方法是强迫线程释放关键的资源。通常，这意味着中断正保持着所需资源的线程。对于某些应用，这种方法可能是无法接受的。另一个有趣的解决方案是在运行时收集资源分配情况并进行事后分析处理，以确定在程序运行过程中是否有死锁情况发生。尽管这种方法并不能防止在运行时发生死锁，但它确实有助于在死锁出现后发现问题并进行修复。
还有一些工具也可以用来帮助发现代码中的死锁。例如，Solaris程序设计员可以采用Sun公司的LockLint工具来对代码进行统计分析。它可以发现对锁定技术的不一致用法，识别引起竞争条件和死锁的许多原因。
