11 Validation

11.1 Introduction

11.1.1 Where Do Bugs Come From?

计算机和人的思维方式的重大差异：

1．计算机缺乏常识性的东西。几十年来，人工智能总是无功而返。

2．计算机通常无法理解人类意图，或者更正式的说，计算机缺少心理理论。

3．计算机通常不能做局部性的计划，与之相反，它需要你将所有细节和每一个可能的场景都一一列出。

小问题11.1：仔细权衡一下，在什么时候，遵从局部性计划显得尤其重要？

答案：有很多这样的情形。但是，最重要的情形可能是，当没有任何人曾经创建过与将要开发的程序类似的任何东西时。在这种情况下，创建一个可信计划的唯一方法就是实现程序、创建计划，并且再次实现它。但是无论是谁首次实现该程序，除了遵循局部性计划外都没有其他选择。因为在无知的情况下创建的任何详细计划，都不能在初次面对真实世界时得以幸存。

也许，这也是如下事实的原因之一，为什么那些疯狂乐观的人，也是那些喜欢遵循局部性计划的人。

11.1.2 Required Mindset

当你在进行任何验证工作时，应当记住以下规则。

1．没有BUG的程序，仅仅是那种微不足道的程序。

2．一个可靠的程序，不存在已知的BUG。

谁不折磨自己的代码，代码将会反过来折磨自己。

11.1.3 When Should Validation Start?

如果你正在从事一个新类型的项目，从某种意义上来说，其需求也是不明确的。在这种情况下，最好的方法可能是快速地原型化一些粗略的方案，尽力将它们搞出来，然后看看哪些方案能最优的运行。

11.1.4 The Open Source Way

只要有足够多的眼球，所有BUG都是浅显的。 开源开发的第二个原则，密集测试。

同Eric在大教堂与集市一书中的表述。

如果你的维护者只有在你已经测试了代码时，才会接受代码，这将形成死锁情形，你的代码需要测试后才能被接受，而只有被接受后才能被测试。

11.2 Tracing

介绍追踪的工具：

• printf/printk
• gdb/kgdb 以上调试手段都存在负载太高的问题。

11.3 Assertions

在并行代码中，可能发生的一个特别糟糕的事情是，某个函数期望在一个特定的锁保护下运行，但是实际上并没有获得该锁。

11.4 Static Analysis

静态分析是一种验证技术，其中一个程序将第二个程序作为输入，它报告第二个程序的错误和漏洞。非常有趣的是，几乎所有的程序都通过它们的编译器和解释器进行静态分析。这些工具远远算不上完美，但是在过去几十年中，它们定位错误的能力得到了极大的改善。部分原因是它们现在拥有超过64K内存进行它们的分析工作。

早期的UNIX lint工具是非常有用的，虽然它的很多功能都被并入C编译器了。目前仍然有类似lint的工具在开发和使用中。

• 介绍了lint的算法及数据结构
• 测试方法

sparse静态分析查找Linux内核中的高级错误，包括：

1．对指向用户态数据结构的指针进行误用。

2．从过长的常量接收赋值。

3．空的switch语句。

4．不匹配的锁申请、释放原语。

5．对每CPU原语的误用。

6．在非RCU指针上使用RCU原语，反之亦然。

虽然编译器极可能会继续提升其静态分析能力，但是sparse静态分析展示了编译器外静态分析的优势，尤其是查找应用特定BUG的优势。

11.5 Code Review

If a man speaks of my virtues, he steals from me; if he speaks of my vices, then he is my teacher.

11.5.1 Inspection

传统意义上来说，正式的代码审查采取面对面会谈的形式，会谈者有正式定义的角色：主持人、开发者及一个或者两个其他参与者。开发者通读整个代码，解释做了什么，以及它为什么这样运行。一个或者两个参与者提出疑问，并抛出问题。而主持人的任务，则是解决冲突并做记录。这个过程对于定位BUG是非常有效的，尤其是当所有参与者都熟悉手头代码时，更加有效。 在审查时，查阅相关的提交记录、错误报告及LWN文档等相关文档是有价值的。

11.5.2 Walkthroughs

典型的走查小组包含一个主持人，一个秘书（记录找到的BUG），一个测试专家（生成测试用例集），以及一个或者两个其他的人。这也是非常有效的，但是也非常耗时。
典型的过程：
1．测试者提供测试用例。

2．主持人使用特定的用例作为输入，在调试器中启动代码。

3．在每一行语句执行前，开发者需要预先指出语句的输出，并解释为什么这样的输出是正确的。

4．如果输出与开发者预先指出的不一致，这将被作为一个潜在BUG的迹象。

5．在并发代码走查中，一个“并发老手”将提出问题，什么样的代码会与当前代码并发运行，为什么这样的并行没有问题？

11.5.3 Self-Inspection

Paul的开发工作流：

1．写出包含需求的设计文档、数据结构图表，以及设计选择的原理。

2．咨询专家，如果有必要就修正设计文档。

3．用笔在纸张上面写下代码，一边写代码一边修正错误。抵制住对已经存在的、几乎相同的代码序列的引用，相反，你应该复制它们。

4．如果有错误，用笔在干净的纸张上面复制代码，一边做这些事情一边修正错误。一直重复，直到最后两份副本完全相同。

5．为那些不是那么显而易见的代码，给出正确性证明。

6．在可能的情况下，自底向上的测试代码片断。

7．当所有代码都集成后，进行全功能测试和压力测试。

8．一旦代码通过了所有测试，写下代码级的文档，也许还会对前面讨论的设计文档进行扩充。

小问题11.5：为什么谁都不喜欢在用笔在纸张上面复制现有代码？这不是增加抄写错误的可能性吗？ 小问题11.6：这个过程是荒谬的过度设计！你怎么能够期望通过这种方式得到合理数量的软件？

1．如果你正在抄写大量代码，那么你可能是没有获得抽象的好处。抄写代码的工作可以为你提供极大的抽象动机。

2．抄写代码的工作，给予你一个机会来思考代码在新的设置环境中是否真的能正常运行。是否有一个不明显的约束，例如需要禁止中断或者持有某些锁？

3．抄写代码的工作，也给你一些时间来考虑是否有更好的途径来完成任务。

事实上，反复的手工抄写代码是费力而且缓慢的。但是，当将重载压力和正确性证明结合起来时，对于那些复杂的，并且其最终性能和可靠性是必要的，而难于调试的并行代码来说，这种方法是极其有效的。Linux内核RCU实现就是一个例子。

Paul的review工作流：

1．使用你喜欢的文档工具（LATEX、HTML、OpenOffice，或者直接用ASCII），描述问题中所述代码的高层设计。使用大量的图来表示数据结构，以及这些如何被修改的。

2．复制一份代码，删除掉所有注释。

3．用文档逐行记录代码是干什么的。

4．修复你所找到的BUG。

虽然后面的过程也是一种真正理解别人代码的好方法，但是在很多情况下，只需要第一步就足够了。

Paul的no-paper工作流：

1．通过扩展使用已有并行库函数，写出一个顺序程序。

2．为并行框架写出顺序执行的插件。例如地图渲染、BIONC或者WEB应用服务器。

3．做如下优秀的并行设计，问题被完整的分割，然后仅仅实现顺序程序，这些顺序程序并发运行而不必相互通信。

4．坚守在某个领域（如线性代数），这些领域中，工具可以自动对问题进行分解及并行化。

5．对并行原语进行极其严格的使用，这样最终代码容易被看出其正确性。但是请注意，它总是诱使你打破“小步前进”这个规则，以获得更好的性能和扩展性。破坏规则常常导致意外。也就是说，除非你小心进行了本节描述的纸面工作，否则就会有意外发生。

11.6 Probability and Heisenbugs

现在的问题是，需要多少测试以确定你真的修复了BUG，而不仅仅是降低故障发生的几率，或者说仅仅修复了几个相关BUG中的某一个BUG，或者是干了一些无效的、不相关的修改。

• 离散测试
  离散测试以良好定义的、独立的测试用例为特征。功能测试往往是离散的。

• 连续测试
  rcutorture测试的持续时间，将比启动、停止它的次数更令人关注。所以说，rcutorture是一个持续测试的例子，这类测试包含很多压力测试。

小问题11.7：假如在你的权限范围内，能够支配大量的系统。例如，以目前的云系统价格，你能够以合理的低价购买大量的CPU时间。为什么不使用这种方法，来为所有现实目标获得其足够的确定性？

答案：这个方法可能是你的验证武器库中一个有价值的补充。但是它有一些限制。
1．某些BUG有极其低的发生概率。但是仍然需要修复。例如，假设Linux内核的RCU实现有一个BUG，它在一台机器上平均一个世纪才出现一次。即使在最便宜的云平台上，一个世纪的时间也是十分昂贵的。但是我们可以预期，截止2011年，世界上超过1亿份Linux实例中，这个BUG会导致超过2000次错误。
2．BUG可能在你的测试设置中，发生概率为0，这意味着无论你花费多少机器时间来测试它，都不会看到BUG发生。
当然，如果你的代码足够小，形式验证可能是有用的。正如在第12章所讨论的一样。但是请注意，对于如下错误，你的前提假设、对需求的误解、对所用软件/硬件原语的误解，或者认为不需要进行证明的错误，形式验证将不能发现它们。

11.6.1 Statistics for Discrete Testing

将f＝0.1及Fn＝0.99代入公式11.6，得到结果43.7，这表示我们需要44次连续成功运行测试用例，才能有99％的把握确保对故障的修复真的生效。
从30％的错误比例提升一个数量级，就是3％的错误率。将这些数值代入公式11.6。 30%的错误率对应的测试次数是13次，3%的错误率对应的测试次数是151.2次。 因此，要提升一个数量级，我们大约需要增加约一个数量级的测试。想要完全确认没有问题，这是不可能的。

11.6.2 Abusing Statistics for Discrete Testing

将离散测试统计的方法论用在持续测试统计中，也是一种误差在 10%以内的可用来代替泊松分布的简单办法。

假如你有一个持续测试，它大约每十个小时失败三次，并且你修复了引起故障的BUG。需要在没有故障的情况下，运行多长时间的测试，才能给你99％的把握确认自己已经减小了故障发生的几率？

在不做过多统计的情况下，我们可以简单定义一小时的运行测试为一个离散测试，在这一个小时内，有30％的几率运行失败。从前一节的结果可以得出结论，如果这个测试运行13个小时而没有错误，就有99％的信心认为我们的修复措施已经提升了程序的可靠性。

11.6.3将给出从数学上来说更准确的解法。

11.6.3 Statistics for Continuous Testing

泊松分布:
在测试中，单位时间内预期λ次失败的情况下，m次失败的可能性是
Here Fm is the probability of m failures in the test and λ is the expected failure rate per unit time.
测试成功的概率：F0 = e ^ -λ，为了解决11.6.2中提出的问题，我们令F0 = 0.01,得λ = 4.6，回到λ的定义：单位时间内预期失败的次数。
为了完成这个单位时间对应的失败次数4.6，我们实际需要的测试小时数为λ / 0.3 = 4.6 / 0.3 = 14.3。

一般而言，如果我们在单位时间内，有n次失败，并且我们希望有P％的信心确信，某次修复减小了失败几率，我们可以使用公式

如果一个给定的测试每小时失败一次，但是经过一次BUG修复以后，24小时测试运行仅仅错误两次。假设导致错误的故障是随机发生的，那么第二次运行是由于随机错误引起的，其可能是多大？

泊松累积分布函数解决这个问题：

这里，m是在长时间测试运行过程中的错误次数（在本例中，是2），λ是长时间运行过程中，预期会失败的次数（在本例中，是24）。将m＝2，λ＝24代入表达式，得到两次或者更少次数的可能性是1.2×10^-8。

11.6.4 Hunting Heisenbugs

“海森堡BUG”这个名字，来源于量子力学的海森堡不确定性原理，该原理指出，在任何特定时间点，不可能同时精确计量某个粒子的位置和速度[Hei27]。任何试图更精确计量粒子位置的手段，都将会增加速度的不确定性。
为什么不构造反-爱森堡 BUG 的东西来消灭爱森堡BUG呢？
针对海森堡BUG构造反-海森堡BUG，这更像是一项艺术，而不是科学。
本节描述一些手段来实现这一点：

为竞争区域增加延迟

这依赖于如何首先找到竞争条件。这有点像暗黑艺术，但是也存在一些找到它们的方法——通过有条理的添加并移除延迟（例如，二分法查找），会更进一步了解到竞争条件是如何运行的。

但是我在进行二分法查找时，最终发现有一个太大的提交。我该怎么办呢？

这就是你的答案：将提交分拆成大小适合的块，并对块进行二分查找。根据我的经验，将提交进行拆分的动作，足以使得BUG变得明显。

增加负载强度

1．增加更多的CPU。

2．如果程序用到了网络，增加更多网络适配卡，以及更多、更快的远程系统。

3．如果在问题出现的时候，程序正在做重载I/O，要么是：（1）增加更多存储设备，（2）使用更快的存储设备，例如将磁盘换为SSD，或者是（3）为大容量存储而使用基于RAM的文件系统，以替代主存储设备。

4．改变其尺寸，例如，如果在进行并行矩阵运算，改变矩阵的大小。更大的问题域可能引入更多复杂性，而更小的问题域通常会增加竞争水平。如果你不确信是否应该加大尺寸，还是减小尺寸，就两者都尝试一下。

独立的测试可疑子系统

实际上，当创建并行程序时，明智的做法是分别对组件进行压力测试。创建这样的组件级别的压力测试，看起来是浪费时间，但是少量的组件级测试可以节省大量系统级的调试。

模拟不常见的事件

例如，不直接调用malloc()，而是调用一个封装函数，该函数使用一个随机数，以确定是否无条件返回NULL，或者真正调用malloc()并返回结果指针。包含伪失败事件是一种在顺序程序及并行程序中实现鲁棒性的好方法。

对near-miss事件进行计数

通常的方法是，将对不频繁发生的错误计数替换为对更常见的near-miss事件进行计数，可以确信，这些near-miss事件与错误相关。
例如：如果有两个操作，应当使用同一把锁，进行不同的获取操作以保护两个操作，在这两个操作之间的延迟过短。这是第一个near-miss事件

11.7 Performance Estimation

11.7.1 Benchmarking

模拟实际应用场景，来测试不同实现的应用对应的性能结果。
其目标如下：

1．对不同的竞争性实现进行比较，提供公正的框架。
2．将竞争力聚集于实现用户关心的部分。
3．将基准实现作为示范使用。
4．作为营销手段，突出软件与竞争对手相比的强项。

11.7.2 Profiling

一个老套但是十分有效的跟踪性能及扩展性BUG的方法，是在调试器下面运行程序，然后定期中断它，并记录下每次中断时所有线程的堆栈。其原理是，如果某些地方使程序变慢，它就必然在线程执行过程中可见。

11.7.4 Microbenchmarking

微基准的一个常用方法是测量其时间，在测试状态下运行一定次数的代码迭代，然后再次测量其时间。两次时间之间的差异除以迭代次数。同glibc中的测试方式。

不幸的是，这种测量方法会有任意数量的误差，包括：

1．测量过程包含一些测量时间的开销。这个误差源可以通过增加迭代次数来将其减小到任意小的值。

2．最初几次测试迭代可能有缓存缺失或者（更为糟糕）缺页错误，这将影响测量值。这个误差源也可以通过增加迭代次数来减小。通常也可以在开始测量前，预先运行几次迭代来将误差源完全消除。

3．某些类型的干扰，例如随机内存错误，这是罕见的，并且可以通过运行一定数量的测试集合来处理。如果干扰级别有显著的统计特征，则明显不合理的性能数据可以被剔除。

4．任意某次测试迭代可能被系统中的其他活动所干扰。干扰可能包括其他应用、系统实用程序及守护程序、设备中断、固件中断（包括系统管理中断、SMI）、虚拟化、内存错误，以及其他一些活动。如果这些干扰是随机发生的，其影响可能通过减少迭代次数来将其最小化。

小问题11.18：其他误差源呢？例如，由于缓存及内存布局之间的相互影响？

内存布局确实会导致执行时间的减少。例如，如果一个特定的应用几乎总是超过L0缓存关联大小，但是通过正确的内存布局，它完全与缓存匹配。如果这确实是一个要顾虑的问题，可以考虑使用巨页（在内核或者裸机上）来运行你的微基准，以完全的控制你的内存布局。

11.7.5 Isolation

CPU调度的干扰

将一组CPU与外界干扰进行隔离的方法：

• taskset
• POSIX sched_setaffinity()系统调用 以上方法对每CPU内核线程没有什么作用。

对每CPU内核线程，则需要以高优先级实时任务的方式来运行你的测试。例如，使用POSIX sched_setscheduler()系统调用。

中断的干扰

通过中断绑核来屏蔽。

11.7.6 Detecting Interference

11.7.6.1 Detecting Interference Via Measurement

在基于Linux的系统中，这个上下文切换将出现在/proc/<PID>/sched的nr_switches字段中。
对于一个特定线程来说，可以使用getrusage()系统调用以得到上下文切换次数，如下实例所示：
如果在测试过程中发生了上下文切换，就舍弃这次测试。

#include <sys/time.h>
#include <sys/resource.h>
/* Return 0 if test results should be rejected. */
int runtest(void)
{
    struct rusage ru1;
    struct rusage ru2;
    if (getrusage(RUSAGE_SELF, &ru1) != 0) {
        perror("getrusage");
        abort();
    }
    /* run test here. */
    if (getrusage(RUSAGE_SELF, &ru2 != 0) {
        perror("getrusage");
        abort();
    }
    return (ru1.ru_nvcsw == ru2.ru_nvcsw &&
    ru1.runivcsw == ru2.runivcsw);
}

11.7.6.2 Detecting Interference Via Statistics

核心：对于良好数据来说，其测量结果的误差程度是已知的。这个事实允许我们在误差范围内接受测量结果。如果干扰的影响大于误差，表示它是受影响的数据，可以简单的剔除它。

作者写了个脚本来实现上述的功能：

divisor=3
relerr=0.01
trendbreak=10
while test $# -gt 0
do
    case "$1" in
    --divisor)
        shift
        divisor=$1
        ;;
    --relerr)
        shift
        relerr=$1
        ;;
    --trendbreak)
        shift
        trendbreak=$1
        ;;
    esac
    shift
done

awk -v divisor=$divisor -v relerr=$relerr \
    -v trendbreak=$trendbreak ’{
    for (i = 2; i <= NF; i++)
        d[i - 1] = $i;
    asort(d);
    i = int((NF + divisor - 1) / divisor);
    delta = d[i] - d[1];
    maxdelta = delta * divisor;
    maxdelta1 = delta + d[i] * relerr;
    if (maxdelta1 > maxdelta)
        maxdelta = maxdelta1;
    for (j = i + 1; j < NF; j++) {
        if (j <= 2)
            maxdiff = d[NF - 1] - d[1];
        else
            maxdiff = trendbreak * \
            (d[j - 1] - d[1]) / (j - 2);
        if (d[j] - d[1] > maxdelta && \
            d[j] - d[j - 1] > maxdiff)
            break;
    }
    n = sum = 0;
    for (k = 1; k < j; k++) {
        sum += d[k];
        n++;
    }
    min = d[1];
    max = d[j - 1];
    avg = sum / n;
    print $1, avg, min, max, n, NF - 1;
}’