A debugger barrier
msinilo.pl
msinilo.pl
The bug looks a bit like these two threads running in parallel:
A: x := N
A: y := N
A: done := true
B: if(done) {
B: assert(x == y)
B: } else { retry }
The fix would be to insert appropriate memory barriers to get the threads to see consistent data.
The problem is to try to determine whether the hypothesis was correct. The bug is rare and the proposed fix might make it more rare. It would be bad if the fix just made another bug harder to discover.
The idea was then that to test this, you hit the edge case and test if the memory fence is sufficient to cause the assertion to succeed. But instead of rewriting the code to something like the following, you can just rely on invoking the debugger being sufficiently invasive to have the effect of the fence and then rerun the assertion.
B: if(done) {
B: if(x != y) {
B: fence();
B: assert(x == y);
B: printf("Gotcha!\n");
B: }
B: // Now use x, y as before…
B: } else { retry }
Is that a fair summary or did I miss something?
> it doesn’t really prove that the only cause of x != y issue [...] is caused by the memory barrier problem (eg maybe a rare buffer overflow sets done to true too early).
I mean, you can never prove that, and that goes for pretty much any bug. Hypothetically, a hardware issue could be in the mix. Or a cosmic ray may hit the device (that's a real thing). You can't prove a negative after all.
But while this does not prove that there's no other cause with the same effect, this at least makes it extremely likely that the missing barrier was an issue: Breaking with the debugger suddenly makes it work without any other intervention, and also they've just looked at the machine code in the first place, with the knowledge of how CPUs work.
The likelihood that there's also a rare buffer overflow consistently reproducing the same issue is negligibly small. If there is, that's a problem you can look at once it actually happens again.
And then stare at it in bewildered disbelief.
As an aside, I have not stared at the problem long enough to say this with full confidence, but if the barriers they inserted are full barriers, they might be too strong. acquire/release might have been sufficient.
On common architectures, from one core itself it never looks like the memory accesses were reordered. From other cores, it may look like that. If there weren't any caches of any sort, there would not be any observable "memory reordering", unless the same core would observe it as well, which breaks sequential consistency (the guarantee to observe any memory access in program order).
(And if I'm not missing anything, reordering memory accesses would be pretty useless without caches anyway.)
There are valid weak executions which correspond to no "reordered" memory access pattern at all. This theory can only take you 95% of the way, but that makes it far worse than a theory which only works for 5% of cases.
Setting aside that without a code sample my explanation lacks a punch line: If you "believe" the memory reordering explanation, then this is patent nonsense. If you "believe" the actual acq/rel semantics in the relevant specifications, then it's obvious (albeit unintuitive).
The problem is, this behavior really can happen, and it may not be that uncommon in complex systems where it is very hidden. Reasoning about these systems using the memory reordering theory will yield results which contradict actual executions on actual compiler/CPU combinations.
OP was alluding that caches and hierarchical memory in general are distinct from „memory reordering“. If I understand correctly, you are saying that the situations you have in mind are indeed a result of caches/hierarchical memory, but cannot be modeled as memory access reordering?
Well yes, but actually no. I mean, my point is that they can't be (correctly!) modeled as memory access reordering. But one doesn't have to and shouldn't appeal to caches. Recent ISAs (aarch64, risc-v) and recent languages (C++11, C<whatever it is now>, rust) are both defined based on acquire-release semantics: both hardware and software engineers have decided this is the common set of requirements we want to use. For software programmers to attempt to reason about cache hierarchies is not only unnecessary, it would also potentially be just as wrong as memory reordering if the design of new microarchitectures changes. But as long as those new uarches conform to existing ISAs, and/or are targeted by existing languages, then the acq-rel model will not change out from under you. So it is the only one that should be used. Indeed, the memory reordering theory seems to originate from this same kind of appeal to microarchitecture which are now out of date, i.e. whatever the first multiprocessing x86 cores did.