unit-testing - 一个单元在哪个级别测试无锁代码？

Question

可以 LLVM, QEMU, GDB, Bochs, OpenStack或类似的用于在开源平台上对无锁并发代码进行单元测试？有没有人做到这一点？

如果您通过 recommending software, 回答我不介意，但我提到 LLVM、QEMU 和其他，因为它们在不同的层次上发挥作用。我想了解在单元测试控制下交织线程的实际成功程度。

我知道 SPIN/Promela,顺便。那是很好的软件，但据我所知，不能将 C++、Rust 等编译到 SPIN/Promela 目标上。

如果您知道的话，很高兴收到现有的无锁并发代码的开源单元测试示例。 (如果我知道在哪里看，我会获取源代码并研究它。)

(另见 these questions 和他们的回答。)

示例

据我所知，我的问题不需要一个例子，所以你可以忽略这个。但是，如果可测试的无锁代码示例有助于讨论，这里有一个相对简短的 C++ 玩具示例。我没有单元测试。

#include <atomic>
#include <thread>
#include <cstdlib>
#include <iostream>

const int threshold     =  0x100;
const int large_integer = 0x1000;

// Gradually increase the integer to which q points until it reaches the
// threshold.  Then, release.
void inflate(std::atomic_bool *const p_atom, int *const q)
{
    while (*q < threshold) ++*q;
    p_atom->store(true, std::memory_order_release);
}

int main()
{
    std::atomic_bool atom{false};
    int n{0};

    // Dispatch the inflator, letting it begin gradually, in the background, to
    // inflate the integer n.
    std::thread inflator(inflate, &atom, &n);

    // Waste some time....
    for (int i = large_integer; i; --i) {}

    // Spin until the inflator has released.
    {
        int no_of_tries = 0;
        while (!atom.load(std::memory_order_acquire)) ++no_of_tries;
        std::cout << "tried " << no_of_tries << " times" << std::endl;
    }

    // Verify that the integer n has reached the threshold.
    if (n == threshold) {
        std::cout << "succeeded" << std::endl;
    }
    else {
        std::cout << "failed" << std::endl;
        std::cerr << "error"  << std::endl;
        std::exit(1);
    }

    inflator.join();
    return 0;
}

PETER CORDES 的澄清

@PeterCordes 准确地澄清了我的问题:

There can be cases where some source compiles to safe x86 asm with any reasonable compiler, but unsafe for weakly-ordered ISAs, which are also usually capable of performing an atomic RMW without a full seq-cst memory barrier (for run-time reordering; compile-time is still up to the compiler). So then you have two separate questions: Is the source portable to arbitrary C++11 systems, and is your code actually safe on x86 (if that's all you care about for now).

这两个问题对我来说都很有趣，但我想到了任意的 C++11 系统。

Usually you want to write code that's portably correct, because it usually doesn't cost any more when compiled for x86.

引用:C++17 标准草案，n4659 (6 MB PDF)，很好地解释了 Peter 提到的 C++11 并发模型。见节。 4.7.1.

DIRK HERRMANN 询价

@DirkHerrmann 问了一个相关的问题:

You ask about how to unit-test your code, but I am not sure that what you describe is truly a unit-testing scenario. Which does not mean you could not use any of the so-called unit-testing frameworks (which can in fact be used for all kinds of tests, not just unit-tests). Could you please explain what the goal of your tests would be, that is, which properties of the code you want to check?

你的观点很好。我的测试的目标是在 C++11 并发模型支持的所有可能的时序中可靠地使坏代码不及格。如果我知道代码很糟糕，那么我应该能够编写一个单元测试来不及格它。我的麻烦是这样的:

无线程。 如果代码是非线程的，我通常可以编写一个单元测试来使坏代码不及格。

线程。 为了不及格，线程代码更难，但只要互斥锁协调线程，至少代码在不同的硬件上运行类似。

无锁。 如果不及格，在特定硬件上可能无法实现无锁代码。如果我的糟糕的无锁代码在你的硬件上运行十亿分之一失败并且在我的硬件上永远不会失败怎么办？一个单元如何测试这样的代码？

我不知道我需要什么，真的。就我的 x86 CPU 不提供真正的 C++11 并发模型而言，也许我需要一个不存在的 CPU 的模拟器来提供真正的 C++11 并发模型。我不确定。

如果我确实有一个不存在的 CPU 的模拟器，它提供了真正的 C++11 并发模型，那么我的单元测试将(据我所知)需要在所有可能的合法时间下尝试我的代码。

这不是一个容易的问题。不知道有没有人解决过。

更新:CDSCHECKER 和 RELACY

讨论使我调查了各种来源，包括

CDSChecker, Norris 和 Demsky 的开源软件；和

Relacy Race Detector, Vyukov 的开源软件，之前讨论过 here.

在撰写本文时，我不知道这些是否回答了我的问题，但它们看起来很有希望。我将它们链接到这里以供引用和进一步调查。

为了引用的完整性，我还添加

SPIN/Promela,

上面已经链接了。

Answer 1

有趣的问题!

At which level does one unit test lock-free code?

令人不满意的答案是:您无法真正测试您所说的“无锁并发代码”。

无需等待，您当然可以: 使用一张纸和一支笔进行测试。尝试证明它是正确的。设计级别是测试多线程代码的正确级别。

当然，您可以为您的代码编写单元测试，您确实应该这样做，但实际上没有办法对所有可能的并发执行场景实现 100% 的覆盖。

你可以(并且应该)尝试折磨你的代码，在不同的架构上运行它(例如 x86 非常连贯，它会隐藏许多并发问题。另外在 ARM 上运行它。)。而且您仍然无法找到所有错误。

基本规则是:您不能使用测试来确保多线程代码(无锁或带锁)的任何质量级别。 100%保证正确性的唯一方法是正式证明你的代码的正确性，这通常意味着你有一个非常简单的线程设计，这很明显，每个人在5分钟内就明白了。然后你相​​应地编写代码。

不要误会我的意思:测试很有用。但是它让你无处可去多线程。

为什么是这样？好吧，首先单元测试方法不起作用:互斥体不能组合。

当您组合 100% 正确工作的多线程子系统 A 和 B 时，结果根本不能保证工作。互斥体不构成。条件变量不组成。线程之间的不变量不构成。只有很少且非常有限的原语，例如线程安全队列，它们组成。但是在单元测试中单独测试方面假设事物是组合的，例如函数或类。