2

Does an open-source technique exist to simulate all possible memory-access-ordering permutations to exhaustively unit test threaded C or C++ code?

REMARKS AND EXAMPLE

One answer is: "Use a memory-safe/functional/very-high-level language. Avoid C and C++." However, that answer answers a different question. Rust, Go, Erlang, Haskell, etc., are great; but my question regards unconstrained C, C++, assembly, or the like.

Another answer is: "Avoid the question by using future, promise, etc." However, my question regards testing methods, not coding methods. I do not seek a code to help me satisfy a paradigm, but a paradigm (or tool) to help me test my code.

The file memory-barriers.txt in the Linux kernel's source documentation affords a suitable example:

[C]onsider the following sequence of events:

    CPU 1           CPU 2
    =============== ===============
    { A == 1; B == 2 }
    A = 3;          x = B;
    B = 4;          y = A;

The set of accesses as seen by the memory system in the middle can be arranged in 24 different combinations:

    STORE A=3,      STORE B=4,      y=LOAD A->3,    x=LOAD B->4
    STORE A=3,      STORE B=4,      x=LOAD B->4,    y=LOAD A->3
    STORE A=3,      y=LOAD A->3,    STORE B=4,      x=LOAD B->4
    STORE A=3,      y=LOAD A->3,    x=LOAD B->2,    STORE B=4
    STORE A=3,      x=LOAD B->2,    STORE B=4,      y=LOAD A->3
    STORE A=3,      x=LOAD B->2,    y=LOAD A->3,    STORE B=4
    STORE B=4,      STORE A=3,      y=LOAD A->3,    x=LOAD B->4
    STORE B=4, ...
    ...

and can thus result in four different combinations of values:

    x == 2, y == 1
    x == 2, y == 3
    x == 4, y == 1
    x == 4, y == 3

Rather than waiting for a Heisenbug to appear, for simple code like the above, one would rather just simulate all 24 cases in advance. Does an open-source technique exist to simulate the 24 cases?

If the technique does not exist, then could it exist? Or would combinatorial explosion render such a technique useless in practice? If the latter, then how do disciplined C++ programmers instead unit test threaded logic when coding for maximum performance?

Various authors have warned how hard it is to think right about concurrency. An open-source technique or tool to systematically expose potential faults in concrete cases would help, if it existed. Does it?

REFERENCES

  • There exists this answer, but it's seven years old and anyway does not much help.
  • There also exist these answers, but they're just as old and do not regard open source.
  • Here is a question that wasn't precise enough.
  • Here is a very interesting question with various partial answers, but it's nine years old. (No one really had an answer back then, apparently.)
  • Here is someone off-site who at least understands the question.
  • There exist various questions and answers on-site for Java, but Java is not what I was asking about.
  • This answer re Objective C is straightforward, illuminating and recent, though not quite on target.
thb
  • 13,796
  • 3
  • 40
  • 68
  • Looks like it belongs on [software recommendations.so](https://softwarerecs.stackexchange.com/). – nwp Sep 05 '17 at 15:39
  • @nwp: Reworded. Thanks. – thb Sep 05 '17 at 15:50
  • Not sure if replacing "tool" with "technique" saves the question. I can tell you my opinion: Testing assumes the tested thing behaves deterministically and reproducibly. That is no longer the case with UB and data races, so testing is basically useless here. I recommend you look into [TSan](https://clang.llvm.org/docs/ThreadSanitizer.html) and the other [TSan](https://clang.llvm.org/docs/ThreadSafetyAnalysis.html). They don't do what you want, but they seem to be the best we have at the moment. Data race prevention by construction seems viable while data race prevention by testing doesn't. – nwp Sep 05 '17 at 16:02
  • You could try [cbmc](http://www.cprover.org/cbmc/), it is pretty good at concurrency. Note however that in general exhaustive testing of software is undecidable. – PaulR Sep 05 '17 at 16:04
  • In my humble opinion, you can NEVER exhaustively test anything in limited time. For example, say x = 1+2 returns 3. You say it passed. How many times do confirm it? What if tomorrow the answer is 4? Only then you will try find the cause. I just get a a little tiny bit irritated when I see statements like this :-). Testing improves confidence level that there are no defects. The more, the better. – Makketronix Sep 05 '17 at 22:33
  • @Makketronix: okay. I would like to test each of the 24 possible orderings once. – thb Sep 06 '17 at 00:36
  • @thb An inefficient trivial way of testing it is to atomically log the operation into a file, and see if all the permutations occurred. I am pretty sure you are seeking a better answer though. – Makketronix Sep 06 '17 at 14:58

0 Answers0