Link Copied
Raf_Schietekat:
Sounds cool!
Thank you ;)
I think that it would take a bit more to model Java volatiles, because they're also mutually sequentially consistent (right?), which on typical hardware probably means that they have to be sequentially consistent with everything (are there any exceptions?). So would you be able to test the memory model as defined and not as mapped to the hardware running the test?
Completely! Memory model is modelled entirely programmatically.
I'm running the tests on x86 hardware, but I'm able to test program against relaxed C++0x memory model, i.e. not total store order, relaxed interlocked operations and so on.
Btw, what you mean by "mutually sequentially consistent"?
As I understand Java's volatiles:
- volatile load is acquire
- volatile store is release
- and between every volatile store and volatile load must be #StoreLoad memory fence.
This basically means that "Peterson's mutex works w/o any additional memory fences". But there are no requirements for total store order to different locations.
So I can map following Java program:
volatile int x;
x = 1;
int y = x;
to C++0x this way:
std::atomic
x.store(1, std::memory_order_release);
std::atomic_thread_fence(std::memory_order_seq_cst);
int y = x.load(std::memory_order_acquire);
Right?
Dmitriy V'jukov
I don't see how unit testing can go beyond the constraints of the hardware on which it is running? Unless you replaced the basic building blocks with a mockup that opens up the cracks, so to say, and you are testing code that sits between your own building blocks replacement and the testing framework, at the cost of considerably reduced performance?
Yes. I replace 'basic building blocks'. My std::atomic<> is special object which tracks 'happens-before' relations. And this is why one have to use rl::var<> instead of plain variables. And actually execution of unit test is single-threaded, so underlying hardware memory model plays no role at all. I manually switch between different "user threads".
As to performance. Yes, it's reduced. As compared to "unchecked run". But I don't see any value in high speed of execution of unit-test, when unit-test doesn't actually test anything.
Execution speed is about 100'000 fully checked executions per second (very depends on unit-test). Most errors are found on iterations 1-10. Very subtle errors are found on iterations 1-10'000. So basically after 1 second of execution one has some confidence.
If you want to check *every possible* "interleaving" (it's possible with 'full search scheduler'), then, yes, execution speed plays significant role, because test can run 1 munute, 1 hour, 1 day...
What would be the relative merits between this approach and something that tries to find flaws in a more systematic way, by reasoning about what can go wrong and/or trying to provide formalproveproof that the algorithm is correct?
I've considered formal model verification too, and have concluded that it's not suitable to test real life C/C++ code, it's more for "scientists", so to say :)
And I'm an engineer, interested in testing real-life synchronization algorithms written in C/C++, including bit manipulation, pointer compression, access violations as part of the algorithm etc.
Also with my tool one don't have to rewrite his algorithm in some "scientific form", and can you his IDE/debugger of choice.
Dmitriy V'jukov
For Java, I'm thinking of the following from <>: "5.2.1 Operations on Volatiles are sequentially consistent." To achieve that, you would need those heavy #StoreLoad barriers, although a compiler can do a lot to soften the impact on performance by eliminating redundant barriers and/or relocating them, even though they're still scheduled statically. A less sophisticated compiler, or a library of volatiles/atomics, may have to apply barriers directly around the volatiles that effectively, if not intentionally, make volatiles sequentially consistent with everything, so the interlocks are costlier than intended. Luckily C++ atomics don't have the mutual sequential consistency to consider.
From my still limited understanding of the matter the mapping seems strict enough (maybe a little too strict?), but in a slightly more complex example it would probably be difficult to model the exact constraints defined in the Java Language Specification, which probably cannot be specified in a linear way even within a control block, and probably require a graph instead, which can be flattened in more than one way.
Yes, I agree, that it's difficult to manually model Java's volatiles. It's possible to place #StoreLoad after every volatile store, for example. But this is not very good approximation. It's possible to try to make some manual "optimization" wrt #StoreLoad placement...
But note that C#/CLI doesn't have such problems, because C#'s volatiles are not sequentially consistent.
Now I am working on incorporating support for Java/C#. Wrt Java's volatiles I going to use *dynamic* scheduling of #StoreLoad barriers. Something like this:
struct thread
{
bool store_load_pending;
void volatile_store()
{
store_load_pending = true;
...
}
void store_load_fence()
{
// if user manually execute full fence between volatile store and volatile load,
// then run-time will not emit additional fence
store_load_pending = false;
...
}
void volatile_load()
{
if (store_load_pending)
store_load_fence();
...
}
};
So I will try to execute #StoreLoad as late as possible. I think that this is "the worst possible conforming implementation". And "worst" in context of unit-testing is good, because it can reveal more errors.
Dmitriy V'jukov