一个单元可以在哪个级别上测试无锁代码? [英] At which level does one unit test lock-free code?

问题描述

可以 LLVM， GDB， Bochs， 推荐软件回答，我不介意，但是我提到LLVM，QEMU和其他软件，因为它们在各种情况下都起作用不同级别.我想学习在单元测试控制下的交织线程上找到了哪些实际的成功.

我偶然发现 SPIN/Promela .据我所知，那是一种很好的软件，但不能将C ++，Rust等编译到SPIN/Promela目标上.

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

(另请参见这些

通过彼得·考德斯澄清

@PeterCordes明确阐明了我的问题:

在某些情况下，某些源可以使用任何合理的编译器编译为安全的x86 asm，但对于弱顺序的ISA则不安全，这些ISA通常也能够在没有完整seq-cst内存屏障的情况下执行原子RMW(对于运行-时间重新排序；编译时间仍取决于编译器).因此，您有两个不同的问题:源代码是否可以移植到任意C ++ 11系统，并且您的代码在x86上实际上是安全的(如果您现在只关心它).

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

通常，您要编写可移植的正确代码，因为在为x86编译时，它通常不会花费更多.

参考:C ++ 17标准草案， CDSChecker， Norris和Demsky的开源软件；和

Raceacy Race Detector， Vyukov的开源软件，前面已经讨论过此处.

在撰写本文时，我不知道这些答案是否能回答我的问题，但它们看起来很有希望.我将它们链接在这里，以供参考和进一步研究.

为便于参考，我还添加了

• SPIN/Promela，

已在上方链接.

解决方案

有趣的问题！

一个单元在哪个级别上测试无锁代码?

令人不满意的答案是:您不能像调用它那样真正测试无锁并发代码".

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

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

您可以(并且应该)尝试折磨您的代码，在不同的体系结构上运行它(例如，x86是如此的连贯，它将隐藏许多并发问题.此外，还要在ARM上运行它.).而且您仍然找不到所有错误.

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

不要误会我的意思:测试很有用.但是使用多线程技术无济于事.

这是为什么?好吧，首先，单元测试方法行不通:互斥体不能组成.

当您将100％正确工作的多线程子系统A和B结合在一起时，根本无法保证结果能正常工作.互斥体不组成.条件变量不组成.线程之间的不变性不构成.只有极少数且非常有限的原语(例如线程安全队列)组成.但是在单元测试中孤立地进行测试的各个方面都假设事物是组成的，例如函数或类.

Can LLVM, QEMU, GDB, Bochs, OpenStack or the like be used to unit test lock-free concurrent code on an open-source platform? Has anyone achieved this?

If you answer by recommending software, I don't mind, but I mention LLVM, QEMU and the others because these function at various different levels. I should like to learn at which level practical success has been found at interleaving threads under unit-test control.

I am aware of SPIN/Promela, incidentally. That is fine software but one cannot compile C++, Rust, etc., onto a SPIN/Promela target as far as I know.

Examples of existing, open-source unit tests of lock-free concurrent code would be gladly received, if you know any. (I would fetch the source and study it if I knew where to look.)

(See also these questions and their answers.)

EXAMPLE

My question does not require an example as far as I know, so you can ignore this one. However, in case an example of testable lock-free code were helpful for purpose of discussion, here is a relatively brief toy example in C++. I have no unit test for it.

#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;
}

CLARIFICATION BY PETER CORDES

@PeterCordes precisely clarifies my question:

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).

Both questions are interesting to me, but I had arbitrary C++11 systems in mind.

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

Reference: the draft C++17 standard, n4659 (6 MB PDF), well explains the C++11 concurrency model to which Peter refers. See sect. 4.7.1.

INQUIRY BY DIRK HERRMANN

@DirkHerrmann asks a pertinent question:

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?

Your point is well taken. The goal of my test would be to flunk bad code reliably for all possible timings the C++11 concurrency model supports. If I know that the code is bad, then I should be able to compose a unit test to flunk it. My trouble is this:

• Unthreaded. I can normally compose a unit test to flunk bad code if the code is unthreaded.
• Threaded. To flunk bad, threaded code is harder, but as long as mutexes coordinate the threading, at least the code runs similarly on divergent hardware.
• Lock-free. To flunk bad, lock-free code might be impossible on particular hardware. What if my bad, lock-free code fails once in a billion runs on your hardware and never fails on mine? How can one unit test such code?

I don't know what I need, really. Insofar as my x86 CPU does not provide a true C++11 concurrency model, maybe I need an emulator for a nonexistent CPU that does provide a true C++11 concurrency model. I am not sure.

If I did have an emulator for a nonexistent CPU that provided a true C++11 concurrency model, then my unit test would (as far as I know) need to try my code under all possible, legal timings.

This is not an easy problem. I wonder whether anyone has solved it.

UPDATE: CDSCHECKER AND RELACY

The discussion has led me to investigate various sources, including

• CDSChecker, open-source software by Norris and Demsky; and
• Relacy Race Detector, open-source software by Vyukov, earlier discussed here.

At this writing, I do not know whether these answer my question but they look promising. I link them here for reference and further investigation.

For completeness of reference, I also add

• SPIN/Promela,

already linked above.

解决方案

Interesting question!

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

The unsatisfying answer is: You cannot really test "lock-free concurrent code" as you called it.

No wait, of course you can: Test it by using a single piece of paper and a pen. Try to prove it is correct. The design level is the correct level to test multithreaded code.

Of course you can write unit tests for your code, and you really should do that, but there are virtually no means to achieve 100% coverage for all possible concurrent execution scenarios.

You can (and should) try to torment your code, run it on different architectures (e.g. x86 is so coherent, it will hide many concurrency problems. Run it on ARM in addition.). And you will still fail to find all errors.

The fundamental rule is: You cannot use testing to assure any quality level of multithreaded code (lock-free or also with locks). The only way to 100% assure correctness is to formally prove the correctness of your code, and this usually means you have a very simple thread design, which is so obvious that everybody understands it within 5 minutes. And then you write your code accordingly.

Don't get me wrong: Testing is useful. But it gets you nowhere with multithreading.

Why is this? Well, first of all the unit test approach does not work: Mutexes do not compose.

When you combine 100% correctly working multithreaded subsystems A and B, the result is not guaranteed to work at all. Mutexes do not compose. Condition variables do not compose. Invariants between threads do not compose. There is only very few and very limited primitives, like thread-safe queues, which compose. But testing aspects in isolation in unit tests assumes that things compose, like functions or classes.

这篇关于一个单元可以在哪个级别上测试无锁代码?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！