Linux文件系统中崩溃一致性错误的系统测试和发现

ACM Transactions on Storage，Vol.号152、第十四条。出版日期：2019年4月CrashMonkey和ACE：系统地测试文件系统崩溃一致性Jayashree Mohan，Ashlie Martinez，SOUJANYA PONNAPALLI，德克萨斯大学奥斯汀分校VIJAY CHIDAMBARAM，德克萨斯大学奥斯汀分校和VMWare Research我们介绍了CRA sH MonkE y和AcE，这是一套系统地查找Linux中崩溃一致性错误的工具文件系统.CRA sH MonkE y是一个记录和重放框架，它通过在执行工作负载时模拟断电崩溃来测试目标文件系统上的给定工作负载，并检查文件系统是否在每次崩溃后恢复到正确的状态。AcE自动生成要在目标文件系统上运行的所有工作负载。我们建立CRA sH MonkE y和AcE基于一种新的方法来测试文件系统崩溃的一致性：有界黑盒崩溃测试（B3）。B3使用文件系统操作的工作负载以黑盒方式测试文件系统。由于可能的工作负载的空间是无限的，B3根据文件系统操作的数量或要包括哪些操作等参数来限制这个空间，并在这个有限的空间内穷尽地生成工作负载。B3建立在我们对过去5年中Linux文件系统中报告的崩溃一致性错误的研究的基础上。我们观察到，大多数报告的错误都可以在新创建的文件系统上使用三个或更少的文件系统操作的小工作负载来重现，并且所有报告的错误都是由fsync（）相关系统调用后的崩溃引起的。CRA sH MonkE y和AcE能够在过去5年中报告的26个崩溃一致性错误中找到24个我们的工具还在广泛使用的成熟Linux文件系统中发现了10个新的崩溃一致性错误，其中7个自2014年以来一直存在于内核中此外，我们的工具在经过验证的文件系统FSCQ中发现了一个崩溃一致性错误。新的错误会导致严重的后果，如破坏重命名原子性，丢失持久化文件和目录，以及数据丢失。CCS概念：·一般和参考→可靠性;·软件及其工程→文件系统管理;·计算机系统组织→可靠性;其他关键词和短语：崩溃一致性，测试，文件系统，错误本材料基于NSF在CNS-1751277下支持的工作以及VMware、Google和Facebook的慷慨捐赠本文是Mohan等[73]. 这里的额外材料包括对文件系统IO路径、缓存和易失性存储设备缓存处IO请求的重新排序的更详细的讨论，对CRA sH MonkE y支持的新子集重放模式的详细讨论，使用LSTM探索崩溃状态的大附录还包含了一个详细的列表，列出了所有复制的bug和CRA sH MonkE y和AcE发现的新bug。作者Jayashree Mohan和Ashlie Martinez也做出了同样的贡献。作者地址：J. Mohan，A. Martinez，S. Ponnapalli和P. Raju，德克萨斯大学奥斯汀分校，110 Inner Campus Drive，Austin，TX 78705;电子邮件：jaya@cs.utexas.eduashmrtn@utexas.edu，{soujanyap 95，pandian 4 mail}@gmail.com;V. Chidambaram，德克萨斯大学奥斯汀分校和VMWare Research，110 Inner Campus Drive，Austin，TX 78705;电子邮件：vijay@cs.utexas.edu。允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上有本声明和完整的引用。必须尊重作者以外的其他人拥有的本作品组件的版权。允许使用学分进行摘要。以其他方式复制、重新发布、在服务器上发布或重新分发到列表中，需要事先获得特定许可和/或付费。从permissions@acm.org请求权限。© 2019版权归所有者/作者所有。授权给ACM的出版权。1553-3077/2019/04-ART14 $15.00https://doi.org/10.1145/332027514ACM Transactions on Storage，Vol.号152、第十四条。出版日期：2019年4月十四日：2J. Mohan等ACM参考格式：Jayashree Mohan，Ashlie Martinez，Soujanya Ponnapalli，Pandian Raju和Vijay Chidambaram。2019年。Crash- Monkey and ACE：Systematically Testing File-System Crash Consistency. ACM Trans. 存储15，2，第14条（2019年4月），34页。https://doi.org/10.1145/33202751介绍如果文件系统在由于断电或内核死机而崩溃后总是恢复到正确的状态，则该文件系统是崩溃一致的如果文件系统的内部数据结构是一致的，并且在崩溃之前持久化的文件没有丢失或损坏，则文件系统状态是正确的当开发人员在2009年将延迟分配添加到ext4文件系统时[65]，他们引入了一个崩溃一致性错误，导致了广泛的数据丢失[36]。考虑到崩溃一致性错误的潜在后果，以及即使是专业管理的崩溃中心偶尔也会遭受断电的事实[67不幸的是，目前几乎没有针对广泛使用的Linux文件系统（如ext4，xfs [84]，btrfs [80]和F2FS [37]）的崩溃一致性测试。Linux文件系统社区目前的做法是不做任何主动的崩溃一致性测试。如果用户报告了一个崩溃一致性错误，文件系统开发人员将响应性地编写一个测试来捕获该错误。Linux文件系统开发人员使用xfstests[23]，一个专门的正确性测试集合，来执行回归测试。xfstests包含总共482个正确性测试，适用于所有POSIX文件系统。在这482项测试中，只有26项（5%）是碰撞一致性测试。因此，文件系统开发人员没有简单的方法来系统地测试他们的文件系统的崩溃一致性。本文介绍了一种新的测试文件系统崩溃一致性的方法：有界黑盒崩溃测试（B3）。B3是一种黑盒测试方法：不修改文件系统代码B3的工作原理是在有限的空间内穷尽地生成工作负载，在工作负载中进行fsync（）等持久化操作后模拟崩溃我们通过构建两个工具来实现B3方法：CRAsH MonkEY和AcE.我们的工具能够在过去5年中报告的26个崩溃一致性错误中找到24个，涉及7个内核版本和3个文件系统。此外，B3的系统性使我们的工具能够发现新的错误：CRA sH MonkE y和AcE在广泛使用的Linux文件系统中发现了10个错误，这些错误导致了严重的后果，例如rename（）不是原子的，文件在fsync（）之后消失，以及FSCQ验证的文件系统中的数据丢失错误[13]。我们已经报告了所有新的错误;开发人员已经提交了五个补丁，并正在努力修复其余的。我们根据对过去5年中ext4、xfs、btrfs和F2FS中报告的所有26个崩溃一致性错误的研究（第3节）来制定B3我们的研究提供了使B3可行的关键见解：大多数报告的错误涉及新文件系统上的少量文件系统操作，在持久化点（调用fsync（）、fdatabloc（）或sync将数据刷新到持久化存储）之后立即崩溃。大多数bug可以通过在一小部分工作负载上进行系统测试来发现或重现，只有在持久化点之后才会崩溃。请注意，如果没有这些限制工作负载空间的见解，B3是不可行的：有无限的工作负载可以在无限的文件系统映像。选择仅在持久化点之后使系统崩溃是使B3易于处理的关键决策之一B3并不关注在文件系统操作过程中由于崩溃而产生的错误，因为在这种情况下文件系统保证是不确定的。此外，如果没有持久化点，B3仅在持久化点之后崩溃限制了测试崩溃一致性所要做的工作，并且还提供了明确的正确性标准：成功持久化CrashMonkey和ACE：系统地测试文件系统崩溃一致性十四日：3ACM Transactions on Storage，Vol.号152、第十四条。出版日期：2019年4月必须在崩溃中幸存下来而不被破坏。虽然我们探索了如何在文件系统操作过程中模拟崩溃（第7节），但并没有发现新的bug。我们认为，在我们能够有效地发现由于文件系统操作过程中的崩溃而导致的错误之前，需要解决几个开放的挑战。B3以其他几种方式限制首先，B3限制了工作负载中文件系统操作的数量，并且只在持久点之后模拟崩溃。其次，B3限制了作为工作负载中文件系统操作的参数的文件和目录。最后，B3将系统的初始状态限制为一个小型的新文件系统。总之，这些界限极大地减少了可能的工作负载的空间，允许CRA sH MonkE y和AcE穷尽地生成和测试工作负载。像B3这样的方法只有在我们可以自动有效地检查任意工作负载的崩溃一致性时才是可行的。我们构建了CRA sH MonkE y，这是一个框架，可以在工作负载执行期间模拟崩溃，并测试恢复的文件系统映像的一致性。CRA sH MonkE y首先分析给定的工作负载，捕获工作负载产生的所有IO。然后，它会重播IO请求，直到一个持久点，以创建一个新的文件系统映像（我们称之为崩溃状态）。在每个持久化点，CRA sH MonkE y还捕获已显式持久化的文件和目录的快照（因此应该在崩溃时幸存）。然后，CRA sH MonkEy在每个崩溃状态下挂载文件系统，允许文件系统恢复，并使用自己的细粒度检查来验证持久化数据和元数据是否可用且正确。因此，CRA sH MonkE y能够自动检查任意工作负载的崩溃一致性，而无需用户进行任何手动这个属性是实现B3方法的关键.我们构建了自动崩溃资源管理器（Automatic Crash Explorer，AcE），以在给定用户约束和文件系统语义的情况下详尽地生成工作负载。AC首先生成一系列文件系统操作;例如，link（）后跟rename（）。接下来，AcE填充每个文件系统操作的参数然后，它会详尽地生成工作负载，其中每个文件系统操作之后都可以有选择地跟随fsync（）、fdatasync（）或全局同步命令。最后，AcE添加操作以满足任何依赖性（例如，文件在被重命名之前必须存在因此，给定一组约束，AcE生成一组详尽的工作负载，每个工作负载都在目标文件系统上使用CRA sH MonkEy进行测试B3在解决文件系统崩溃一致性的技术谱中提供了一个新的点，与已验证的文件系统[12，13，82]和模型检查[94，95]一起。与这些方法不同，B3的目标是用低级语言编写的广泛部署的文件系统，并且不需要标注或修改文件系统代码。然而，B3并不是没有限制的，因为它不能保证找到所有的崩溃一致性错误。目前，AcE虽然CRA sH MonkE y可以测试这样的工作负载，但AcE将无法自动生成工作负载。尽管有这些限制，我们希望我们的工具的黑盒性质和易用性将鼓励它们在文件系统社区中的采用，而不像模型检查和验证的汉阳大学的研究人员正在使用我们的工具来测试他们的研究文件系统BarrierFS的崩溃一致性，这让我们感到鼓舞[93]。本文做出了以下贡献：详细分析了过去5年中在三个广泛使用的文件系统和七个内核版本中报告的崩溃一致性错误（第3节）。- 有界黑箱碰撞测试方法（第4节）。- 介绍了CRA sH MonkE y和AcE. 1（第5节）1https://github.com/utsaslab/crashmonkey。十四日：4J. Mohan等ACM Transactions on Storage，Vol.号152、第十四条。出版日期：2019年4月图1.一、文件系统写入的寿命。 该图显示了存储堆栈正在处理的应用程序写入。为了确保正确性，文件的数据需要在元数据之前持久化 文件系统在向块子系统提交请求时设置FLUSH标志;块子系统在持久化元数据块之前刷新数据块。实验结果表明，我们的工具能够有效地发现广泛使用的Linux文件系统和已验证文件系统中的现有和新错误（第6节）- 推广CRA sH MonkE y来查找由于文件系统操作中崩溃而导致的bug，并演示使用LSTM来解决大状态空间的问题（第7节）2背景我们首先提供一些背景知识，介绍文件系统如何执行读写操作，以及这些操作如何通过存储堆栈进行处理。然后，我们将介绍文件系统崩溃一致性，为什么会出现崩溃一致性错误，以及为什么测试文件系统崩溃一致性很重要。文件系统IO。 文件系统通常以系统调用的形式向用户公开POSIX API。POSIX API包括数据操作（如read（）和write（））以及元数据操作（如creat（）和rename（））。当用户执行写操作时，写操作首先由文件系统处理，然后作为要写的块的列表传递到块IO子系统。块在到达存储设备之前经过几层。诸如IO调度器之类的层可以对发送到存储设备的块重新排序以提高性能（例如，通过逻辑块地址对块进行排序有助于减少硬盘驱动器上的寻道时间）。文件系统写操作所采用的路径如图1所示。在存储设备中缓存。大多数现代存储设备都具有板载RAM缓存，以提高读写性能。当设备收到写请求时，它会将数据写入其缓存并发出请求完成的信号。因此，存储设备完成的IO请求并不意味着它是持久的;如果存储设备在缓存的数据可以持久化之前断电，则数据将丢失。当将缓存的数据写入持久性介质时，存储设备可以自由地以任何顺序写入数据;通常，像硬盘驱动器这样的存储设备将尝试通过按逻辑块地址对数据进行排序来最大化写入性能。有序性和耐久性。文件系统可能需要在各个点上确保有序性和持久性。例如，日志记录协议要求日志事务在CrashMonkey和ACE：系统地测试文件系统崩溃一致性十四日：5ACM Transactions on Storage，Vol.号152、第十四条。出版日期：2019年4月日记承诺类似地，当用户在文件上调用fsync（）时，他们希望在fsync（）返回后，与该文件关联的所有数据都是持久的为了帮助实现有序性和持久性，存储设备公开了两个标志：FLUSH标志和强制单元访问（FUA）标志。如果IO请求标记有FLUSH标志，则存储设备必须刷新其高速缓存，并且之前写入存储设备的所有数据都是永久的。请注意，FLUSH并不强制其请求中的数据是持久性的，只强制以前写入的数据。如果IO请求带有FUA标志，则只有当该请求中的数据被持久化时，IO请求才能返回例如，在ext4文件系统中，日志提交标记有FLUSH标记（确保先前写入的日志事务的持久性）和FUA标志（确保日志提交的持久性崩溃一致性。如果在由于断电或内核恐慌而崩溃后，关于文件系统状态的许多不变量保持不变，则文件系统是崩溃一致的[14，66]。通常，这些不变量包括仅在初始化之后使用资源（例如，路径名指向初始化的元数据（诸如索引节点），在删除之后安全地重用资源（例如，两个文件不应该认为它们都拥有相同的数据块），并且原子地执行某些操作，例如重命名文件。通常，崩溃一致性只涉及内部文件系统的完整性。只要文件系统保持内部一致性，丢失先前持久化数据的错误就不会被认为是崩溃一致性错误。在本文中，我们将定义扩大到包括数据丢失。因此，如果文件系统在崩溃后丢失了持久化数据或文件，我们认为这是一个崩溃一致性错误。Linux文件系统开发人员同意崩溃一致性的这个更广泛的定义[19，86]。然而，重要的是要注意，没有显式持久化的数据或元数据不属于我们的定义;在断电的情况下，允许文件系统丢失这些数据。最后，崩溃一致性bug和文件系统正确性bug之间有一个重要的区别：如果没有崩溃发生，崩溃一致性bug不会导致错误的行为。为什么会出现崩溃一致性bug 崩溃一致性错误的根源在于大多数文件系统操作只修改内存中的状态。例如，当用户创建文件时，新文件仅存在于内存中，直到它通过fsync（）调用或后台线程显式持久化，该后台线程定期写出脏的内存中数据和元数据。现代文件系统非常复杂，并且在内存中保存大量与元数据相关的数据结构。例如，btrfs将其元数据组织为B+树[80]。对这些数据结构的修改累积在内存中，并通过fsync（）或后台线程写入存储。开发人员在持久化这些内存结构时可能会犯两种常见的错误，从而导致崩溃一致性错误。第一个是忽略了更新数据结构的某些字段。例如，btrfs有一个bug，文件inode中决定是否持久化的字段没有更新。结果，文件上的fsync（）变成了无操作，导致崩溃时数据丢失[41]。第二个是在持久化数据和元数据时，数据和元数据的顺序不正确。例如，当ext4中引入延迟分配时，使用重命名来原子地更新文件的应用程序会丢失数据，因为重命名可能会在文件的新数据之前持久化尽管在这两种情况下导致崩溃一致性错误的错误非常不同，但根本问题是正确恢复所需的某些内存状态没有写入磁盘。POSIX和文件系统保证。名义上，Linux文件系统实现了POSIX API，提供了POSIX标准中规定的保证[25]。不幸的是，POSIX非常模糊。例如，在POSIX下，fsync（）不使数据持久是合法的[77]。Mac OSX利用了这种合法性，并要求用户使用fcntl（F_FULLFSYNC）来使数据持久。因此，文件系统通常提供超出十四日：6J. Mohan等ACM Transactions on Storage，Vol.号152、第十四条。出版日期：2019年4月图二、崩溃一致性错误示例。 该图显示了暴露btrfs文件系统中在2月份报告的崩溃一致性错误的工作负载。2018年[57]。该错误导致文件系统无法挂载。POSIX。例如，在ext4上，持久化一个新文件也将持久化它的目录项。不幸的是，这些保证在不同的文件系统中有所不同，因此我们联系了每个文件系统的开发人员，以确保我们正在测试他们试图提供的保证。崩溃一致性错误的示例。图2显示了btrfs中的一个崩溃一致性错误，它导致文件系统在崩溃后变得不可挂载（不可用）。解决这个错误需要使用btrfs-check进行文件系统修复;对于外行用户，这需要开发人员的指导[10]。这个bug发生在btrfs上，因为取消链接会影响两个不同的数据结构，如果发生崩溃，它们就会失去同步。在恢复时，btrfs尝试取消链接bar两次，产生错误。为什么测试崩溃一致性很重要？文件系统研究人员正在开发新的崩溃一致性技术[17，18，75]，并设计新的文件系统，以提高性能[1，7，32，35，79，83，99，100]。同时，Linux文件系统（如btrfs）包括许多影响IO请求顺序的优化，因此，崩溃一致性。然而，崩溃一致性是微妙的，很难得到正确的，一个错误可能会导致无声的数据损坏和数据丢失。因此，应仔细测试影响崩溃一致性的更改。今天的碰撞一致性测试。xfstests[23]是一个用于检查文件系统正确性的回归测试套件，其中包含一小部分（5%）崩溃一致性测试。这些测试的目的是避免随着时间的推移重复出现相同的错误，但不概括识别-这是bug的变种。此外，这些测试用例中的每一个都要求开发人员编写一个检查器，描述崩溃后文件系统的正确行为。考虑到工作负载的无限空间，很难手工制作可能会发现错误的工作负载。这些因素使得xfsts不足以识别新的崩溃一致性错误。3消除碰撞一致性错误我们分析了过去5年中用户在广泛使用的Linux文件系统上报告的26个独特的崩溃一致性错误[88]（第11.1节）。我们通过检查邮件列表消息或查看xfstests回归测试套件中的崩溃一致性测试来发现这些错误。xfstest中的崩溃一致性测试很少与导致编写测试的bug相关联。由于崩溃一致性错误的性质（所有内存中的信息在崩溃时都会丢失），很难将它们与特定的工作负载联系起来。因此，报告的bug数量很低。我们相信有许多崩溃一致性错误在野外没有报告（第11.2节）。CrashMonkey和ACE：系统地测试文件系统崩溃一致性十四日：7ACM Transactions on Storage，Vol.号152、第十四条。出版日期：2019年4月表1.分析崩溃一致性错误版本Consequence # bugs腐败19数据不一致6无法挂载的文件系统3总计28文件系统#bugsext42F2FS2btrfs24总计28需要的操作数#bug1 32 143 9数目总共26这些表格按不同标准列出了过去5年（自2013年以来）报告的26个独特的崩溃一致性错误在两个不同的文件系统上报告了两个错误，导致总共28个错误。表2.崩溃一致性错误示例缺陷编号文件系统后果运营次数涉及（不包括持久化操作）1btrfs目录不可移动2creat（A/x），creat（A/y）2btrfs持久化数据丢失2pwrite（x），link（x，y）3btrfs目录不可移动3link（x，A/x），link（x，A/y），unlink（A/y）4F2FS持久化文件消失3pwrite（x），rename（x，y），pwrite（x）5ext4持久化数据丢失2pwrite（x），direct_write（x）下表显示了过去5年中报告的一些崩溃一致性错误。这些错误会造成严重的后果，从丢失用户数据到使目录不可移动。我们根据后果、内核版本、文件系统以及重现它们所需的文件系统操作的数量来分析错误。有26个独特的bug分布在ext4，F2FS和btrfs中。每个独特的bug都需要一组独特的文件系统操作来重现。两个错误发生在两个文件系统（F2FS和ext4，F2FS和btrfs）上，导致总共28个错误。表1给出了一些关于崩溃一致性bug的统计数据。下表显示了报告错误的内核版本。如果bug报告不包括版本，它会提供B3可以重现bug的最新内核版本（B3无法重现的两个bug这些错误会造成严重后果，从文件系统损坏到文件系统无法挂载。崩溃一致性错误涉及的四个最常见的文件系统操作是write（）、link（）、unlink（）和rename（）。大多数报告的错误都是由于在多个文件系统操作中重用文件名或对重叠文件区域进行写入操作而导致的。大多数报告的错误可以通过三次或更少的文件系统操作重现。例子. 表2展示了一些崩溃一致性错误。Bug #1 [39]涉及到在一个目录中创建两个文件，并且只持久化其中一个。btrfs日志恢复会错误地计算目录大小，从而使该目录在此后不可移动。错误#2 [43]涉及创建一个硬链接到一个已经存在的文件。崩溃导致btrfs恢复大小为0的文件，从而使其数据不可访问。一个类似的bug（#5 [28]）在ext4中的直接写入路径中出现，其中写入成功并分配了块，但文件大小被错误地更新为零，导致数据丢失。复杂性导致bug。ext4文件系统经历了15年的开发，因此只有两个bug。btrfs和F2FS文件系统是更新的：btrfs内核#bug3.1233.1393.1614.1.124.494.1534.16 1总28十四日：8J. Mohan等ACM Transactions on Storage，Vol.号152、第十四条。出版日期：2019年4月F2FS是在2007年推出的，而F2FS是在2012年推出的。特别是，btrfs是一个极其复杂的文件系统，它提供了快照、克隆、带外重复数据删除和压缩等功能。btrfs以各种写时复制B+树的形式维护其元数据（诸如索引节点和位图）。这使得实现崩溃一致性变得棘手，因为更新必须传播到多个树。因此，大多数报告的崩溃一致性错误发生在btrfs中并不奇怪。随着文件系统在未来变得更加复杂，我们预计崩溃一致性错误也会相应增加。崩溃一致性错误很难找到。尽管我们研究的文件系统被广泛使用，但一些错误仍然隐藏在其中多年。例如，btrfs有一个崩溃一致性错误，在它被引入7年后才被发现这个错误是由于错误地处理btrfs数据结构中的一个硬链接引起的当添加硬链接时，目录条目被添加到一个数据结构，而inode被添加到另一个数据结构。当崩溃发生时，只有一个数据结构会被正确恢复，导致包含硬链接的目录变得不可移动[46]。自2008年添加日志树以来就存在此漏洞;然而，该漏洞仅在2015年被发现。需要进行系统测试。一旦btrfs中的硬链接bug被发现，btrfs的开发人员很快就修复了它。然而，他们只修复了一个可能导致bug的代码路径。在另一个代码路径中可能会触发相同的错误，这一事实在原始错误报告后4个月才被发现。虽然最初的bug工作负载需要在原始文件和父目录上创建硬链接并调用fsync（），但这个bug需要在创建硬链接的目录中的兄弟目录上调用fsync（）[47]。对文件系统的系统性测试会揭示该错误可能是通过备用代码路径触发的。小的工作负载可能会暴露空文件系统上的错误。大多数报告的错误不需要特殊的文件系统映像或大量的文件系统操作来重现。在报告的26个错误中，有24个需要三个或更少的核心文件系统操作才能在空文件系统上重现。这个计数很低，因为我们不计算依赖操作：例如，一个文件在被重命名之前必须存在，一个目录在一个文件被创建之前必须存在。2这样的依赖操作可以从核心文件系统操作中推断出来。在剩下的两个bug中，有一个bug需要在工作负载期间运行一个特殊的命令（dropaches）才能表现出来。另一个bug需要一个特定的设置：3,000个硬链接必须已经存在（强制外部重链接）才能显示bug。报告的bug涉及持久化后的崩溃 所有报告的bug都涉及到在持久化点之后的崩溃：调用fsync（）、fdatasync（）或global sync命令。这些命令很重要，因为文件系统操作默认情况下只修改内存中的元数据和数据。只有持久性点才能可靠地更改存储上的文件系统状态。因此，除非文件或目录已被持久化，否则不能期望它在崩溃后仍然存在。虽然从技术上讲，崩溃可能在任何时候发生，但如果没有持久化的文件在崩溃后丢失，用户不能抱怨因此，每个崩溃一致性错误都涉及崩溃后受错误影响的持久化数据或元数据，并且不具有持久化点的工作负载不能导致可再现的崩溃一致性错误。这也指出了一种发现崩溃一致性错误的有效方法：执行一系列文件系统操作，使用fsync（）或类似调用更改存储上的文件系统状态，崩溃，然后检查以前持久化的文件和目录。4B3：有界黑盒碰撞测试基于我们对崩溃一致性错误的研究，我们引入了一种新的方法测试文件系统崩溃一致性：Bounded Black-Box crash testing（B3）。B3是一个黑盒子CrashMonkey和ACE：系统地测试文件系统崩溃一致性十四日：9ACM Transactions on Storage，Vol.号152、第十四条。出版日期：2019年4月测试方法基于这样的见解：通过在新文件系统上系统地测试小序列的文件系统操作，可以发现大多数报告的崩溃一致性错误。B3通过其系统调用API来运行文件系统，并通过读写IO来观察文件系统的行为。因此，B3不需要注释或修改文件系统源代码。4.1概述B3生成文件系统操作序列，称为工作负载。由于可能的工作负载空间是无限的，B3使用研究中的见解来限制在确定的范围内，B3详尽地生成和测试所有可能的工作负载.通过在每个持久性点之后模拟崩溃并检查文件系统是否恢复到正确的状态来测试每个工作负载。B3对恢复的文件系统状态执行细粒度的正确性检查;只检查显式持久化的文件和目录。B3检查文件和目录的数据和元数据（大小、链接数和块数）的一致性。崩溃点。使B3这样的方法可行的研究中的主要见解是崩溃点的选择;崩溃只在工作负载中的每个持久化点之后模拟，而不是在文件系统操作的中间。这种设计选择是由两个因素驱动的。首先，如果在文件系统操作过程中发生崩溃，则文件系统保证是不确定的;只有以前成功持久化的文件和目录才需要在崩溃中幸存下来。文件系统开发人员负担过重，涉及未显式持久化的数据或元数据的错误被赋予较低的优先级（有时不被确认为错误）。其次，如果我们在操作过程中崩溃，文件系统可以恢复到许多正确的状态。如果文件系统操作转换为n个块IO请求，那么如果我们在操作期间的任何地方崩溃，则可能存在2n个不同的磁盘崩溃状态。将崩溃限制在持久化点之后发生，将这个空间线性地限制在构成工作负载的操作数量上。少量的崩溃点和正确的状态使自动化测试更加容易。我们对崩溃点的选择自然会导致持久化数据和元数据损坏或丢失的错误，文件系统开发人员强烈希望修复这些错误。4.2B3使用的边界根据我们对崩溃一致性错误的研究，B3以几种方式限制了可能的工作负载空间(1) 手术次数。B3限制工作负载中文件系统操作的数量（称为序列长度）。seq-X工作负载中有X个核心文件系统操作，不包括相关操作，例如在重命名文件之前创建文件。(2) 目录中的文件和目录我们观察到，在报告的错误中，错误是由于重用一小部分文件进行元数据操作而导致的。因此，B3将工作负载限制为每个目录使用很少的文件，以及较低的目录深度.此限制会自动减少与元数据相关的操作（如rename（））的输入。(3) 数据操作。 该研究还表明，与数据不一致有关的错误主要是由于写入重叠的文件范围而发生。在大多数情况下，错误并不取决于写入中使用的确切偏移量和长度，而是取决于来自写入的重叠区域之间的交互。该研究表明，对写入进行广泛的分类，例如追加到文件末尾，覆盖文件的重叠区域等，足以发现崩溃一致性错误。(4)初始文件系统状态。研究中分析的大多数错误都不需要特殊检查，cific初始文件系统状态（或大型文件系统）。此外，大多数十四日：J. Mohan等ACM Transactions on Storage，Vol.号152、第十四条。出版日期：2019年4月可以从相同的小文件系统映像开始复制已研究的错误。因此，B3可以从相同的初始文件系统状态开始测试所有工作负载。4.3细粒度的正确性检查B3使用细粒度的正确性检查来验证每个崩溃状态下持久化文件和目录的数据和元数据。由于fsck运行起来很耗时，而且可能会漏掉数据丢失/损坏的错误，因此它不适合用于B3。4.4限制B3方法有许多局限性：(1)B3不保证找到所有的崩溃一致性bug。它是健全的，但不完整。然而，由于B3测试是穷尽性的，如果触发bug的工作负载落在受约束的工作负载空间内，B3将找到它。因此，B3的有效性取决于所选择的边界和测试的工作负载的数量。(2)B3专注于一个特定的bug类.它不会模拟文件系统操作过程中的崩溃，也不会重新排序IO请求以创建不同的崩溃状态。隐含的假设是核心的崩溃一致性机制，如日志[78]或写时复制[30，81]，正在正确工作。相反，我们假设是文件系统的其余部分有错误。碰撞一致性错误研究表明这种假设是合理的。我们在第7节中探讨了文件系统操作过程中的崩溃，这并没有导致发现任何新的bug。(3)B3侧重于文件和目录显式持久化的工作负载.如果我们创建了一个文件，等待1小时，然后崩溃，在文件系统恢复后发现文件不见了，这也是一个崩溃一致性错误。然而，B3并没有探索这样的工作负载，因为它们需要大量的时间来运行，并且不容易以确定性的方式重现。(4) 由于其黑盒性质，B3无法精确指出导致所观察到的错误的确切代码行。一旦B3发现了一个错误，找到根本原因需要进一步的调查.但是，B3有助于调查bug的根本原因，因为它提供了一种以确定性方式重现bug的方法。尽管B3有缺点，但我们相信它是测试文件系统崩溃一致性的技术库中的一个有用的补充。B3的真正优势在于它的系统性，以及它不需要对现有系统进行任何更改的事实。因此，它非常适合用低级语言（如C）编写的复杂且广泛使用的文件系统，在这些系统中，无法轻松使用更强大的方法（如验证）。5CRASHMONKEY和ACE我们通过构建两个工具来实现B3方法：CRAsH MonkEY和AcE.如图3所示，CRA sH MonkE y负责在给定工作负载的不同点模拟崩溃，并在每次模拟崩溃后测试文件系统是否正确恢复，而Automatic Crash Explorer（AcE）负责在有限空间中彻底生成工作负载。5.1CrashMonkeyCRA sH MonkE y使用记录和重放技术来模拟工作负载中间的崩溃，并测试文件系统在崩溃后是否恢复到正确的状态为了获得最大的可移植性，CRA sH MonkE y将文件系统视为黑盒，只要求文件系统实现POSIX API。CrashMonkey和ACE：系统地测试文件系统崩溃一致性十四日：ACM Transactions on Storage，Vol.号152、第十四条。出版日期：2019年4月图3.第三章。 系统架构。给定探索的界限，Ac E生成一组工作负载。每个工作负载然后被馈送到CRAsH MonKE y，其生成一组崩溃状态和对应的预言机。Autocompatibility比较每个oracle/crash状态对中的持久化文件;不匹配表示存在bug。图四、做一个很好的手术。 C RA s H Mon KEY y首先记录工作负载转换为的块IO请求，在每个持久化点之后捕获称为oracle的参考映像。然后，C RA s H Mon KE y通过重放记录的IO生成崩溃状态，并根据相应的oracle测试一致性。概况. 如图4所示，CRA s H Monk E y分三个阶段运行。在第一阶段，CRA sH- MonkE y通过收集有关工作负载期间所有文件系统操作和IO请求的信息来分析工作负载。第二阶段重放IO请求，直到持久化点创建崩溃状态。崩溃状态表示系统在持久化操作完成后崩溃时的存储状态然后，CRA sH MonkEy将文件系统挂载到崩溃状态，并允许文件系统执行恢复。在每个持久化点，CRA sH MonkE y还捕获一个引用文件系统映像（称为oracle），方法是安全地卸载它，以便文件系统完成任何挂起的操作或检查点操作。oracle表示崩溃后文件系统的预期状态。我们依赖于umount（）操作的正确性来生成一个神谕图像如果umount（）操作本身没有清除所有脏块，那么我们可能会错过发现bug。然而，在所有以前报告的崩溃一致性错误中，十四日：J. Mohan等ACM Transactions on Storage，Vol.号152、第十四条。出版日期：2019年4月我们探索过，从来没有遇到过这种情况。在没有bug的情况下，持久化文件应该 在恢复后的Oracle和崩溃状态中是相同的。在第三个阶段，CRA sH MonkE yCRA sH MonkE y作为两个内核模块和一组用户空间实用程序实现。内核模块由1，300行C代码组成，可以在运行时编译并插入内核，从而避免了长时间的用户空间实用程序由4，800行C++代码组成。CRA sH MonkE y这使我们能够将CRA sH MonkE y移植到7个内核上，以重现第3节中研究的错误。分析工作负载。CRA sH MonkE y在存储堆栈的两个级别上分析工作负载：它记录块IO请求，并记录系统调用。它使用两个内核模块来记录块IO请求并创建崩溃状态和预言机。第一内核模块使用目标文件系统所挂载的包装器块设备来记录由工作负载生成的所有IO请求。包装器设备记录IO请求的数据和元数据（如扇区号、IO大小和标志）。工作负载中的每个持久化点都会导致一个特殊的检查点请求被插入到记录的IO请求流中。检查点只是一个带有特殊标志的空块IO请求，用于将持久化操作的完成与低级块IO流相关联。包装器设备记录的所有数据都通过ioctl调用传递给用户空间实用程序。CRA sH MonkE y中的第二个内核模块是一个内存中的写时复制块设备，它有助于快照。CRA sH MonkE y在分析阶段开始之前创建文件系统的快照CRA sH MonkE y通过在基本磁盘映像上重放分析期间记录的IO来生成崩溃状态，从而提供快速、可写的快照。快照还保存在工作负载中的每个持久化点以创建Oracle。此外，由于快照是写时复制的，因此将快照重置为基础映像仅意味着删除修改的数据块，从而提高效率。CRA sH MonkE y还记录工作负载中的所有open（）、close（）、fsync（）、fdatasync（）、rename（）、sync（）和msync（）调用，以便当工作负载执行诸如fsync（fd）之类的持久化操作时，CRA sH MonkE y能够将fd与先前打开的文件相这允许CRA sH MonkE y跟踪在工作负载中的任何点显式持久化的文件和目录集