The tool was designed for verification of algorithms like memory management, memory reclamation for lock-free algorithms, multithreaded containers (queues, stacks, maps), mutexes, eventcounts and so on.
My personal subjective feeling to date is that tool is capable of finding extremely subtle algorithmic errors, memory fence placement errors and memory fence type errors within a second. And after error is detected error fixing is relatively trivial, because one has detailed execution history which leads to error.
Main features:
- Relaxed ISO C++0x Memory Model. Relaxed/acquire/release/acq_rel/seq_cst memory operations and fences. The only non-supported feature is memory_order_consume, it's simulated with memory_order_acquire.
- Exhaustive automatic error checking (including ABA detection).
- Full-fledged atomics library (with spurious failures in compare_exchange()).
- Arbitrary number of threads.
- Detailed execution history for failed tests.
- Before/after/invariant functions for test suites.
- No false positives.
Types of detectable errors:
- Race condition (according to ISO C++0x definition)
- Access to uninitialized variable
- Access to freed memory
- Double free
- Memory leak
- Deadlock
- Livelock
- User assert failed
- User invariant failed
You can get some more information (tutorial, examples etc) here:
http://groups.google.com/group/relacy/web
And here is dedicated news group/discussion forum:
http://groups.google.com/group/relacy/topics
If you want to get a copy of the tool, please, contact me via dvyukov@gmail.com.
Any feedback, comments, suggestions are welcome.
Relacy Race Detector is free for open-source, non-commercial development; research with non-patented, published results; educational purposes; home/private usage. Please contact me (dvyukov@gmail.com) about other usages.
--------------------------------------------------------
Here is quick example.
Code of unit-test:
#include
// template parameter '2' is number of threads
struct race_test : rl::test_suite
{
std::atomica;
rl::varx;
// executed in single thread before main thread function
void before()
{
a($) = 0;
x($) = 0;
}
// main thread function
void thread(unsigned thread_index)
{
if (0 == thread_index)
{
// code executed by first thread
x($) = 1;
a($).store(1, rl::memory_order_relaxed);
}
else
{
// code executed by second thread
if (1 == a($).load(rl::memory_order_relaxed))
x($) = 2;
}
}
// executed in single thread after main thread function
void after()
{
}
// executed in single thread after every
// 'visible' action in main threads.
// disallowed to modify any state
void invariant()
{
}
};
int main()
{
// start simulation
rl::simulate();
}
And here is output of the tool:
struct
race_test
DATA
RACE
iteration:
8
execution
history:
[0]
0: <00366538> atomic store, value=0, (prev value=0),
order=seq_cst, in race_test::before, test.cpp(14)
[1]
0: <0036655C> store, value=0, in race_test::before,
test.cpp(15)
[2]
0: <0036655C> store, value=1, in race_test::thread,
test.cpp(23)
[3]
0: <00366538> atomic store, value=1, (prev value=0),
order=relaxed, in race_test::thread, test.cpp(24)
[4]
1: <00366538> atomic load, value=1, order=relaxed, in
race_test::thread, test.cpp(28)
[5]
1: <0036655C> store, value=0, in race_test::thread,
test.cpp(29)
[6]
1: data race detected, in race_test::thread, test.cpp(29)
thread
0:
[0]
0: <00366538> atomic store, value=0, (prev value=0),
order=seq_cst, in race_test::before, test.cpp(14)
[1]
0: <0036655C> store, value=0, in race_test::before,
test.cpp(15)
[2]
0: <0036655C> store, value=1, in race_test::thread,
test.cpp(23)
[3]
0: <00366538> atomic store, value=1, (prev value=0),
order=relaxed, in race_test::thread, test.cpp(24)
thread
1:
[4]
1: <00366538> atomic load, value=1, order=relaxed, in
race_test::thread, test.cpp(28)
[5]
1: <0036655C> store, value=0, in race_test::thread,
test.cpp(29)
[6]
1: data race detected, in race_test::thread, test.cpp(29)
--------------------------------------------------------
Dmitriy V'jukov
Link Copied
Raf_Schietekat:
Sounds cool!
Raf_Schietekat:
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?
Raf_Schietekat:
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?
Raf_Schietekat:
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?
Raf_Schietekat:
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.
>
I want to announce release 1.1 of Relacy Race Detector.
First of all, now you can freely DOWNLOAD latest version of Relacy
Race Detector DIRECTLY FROM WEB:
http://groups.google.com/group/relacy/files
Main change in release 1.1 is support for standard synchronization
primitives:
1. mutex (std::mutex, pthread_mutex_init, InitializeCriticalSection)
2. rw_mutex (pthread_rwlock_init, InitializeSRWLock)
3. condition variable (std::condition_variable,
std::condition_variable_any, pthread_cond_init,
InitializeConditionVariable)
4. semaphore (sem_init, CreateSemaphore)
5. event (CreateEvent)
Now you can test more traditional "mutex-based" algorithms (i.e. no
lock-free), and Relacy still will detect data races, deadlocks,
livelocks, resource leaks, incorrect usage of API etc.
Also you can test mixed lock-based/lock-free algorithms. For example
fast-path is lock-free, and slow-path is mutex-based.
For examples see 'spsc_queue' example in distributive, it uses
std::mutex and std::condition_variable as well as lock-free fast-path.
And following manual implementation of condition_variable via Win
API's CreateEvent and CreateSemaphore:
http://groups.google.com/group/comp.programming.threads/msg/30c2ec41c4d498a2
Also I add RL_DEBUGBREAK_ON_ASSERT and RL_MSVC_OUTPUT options. And
initial_state/final_state parameters. See details here:
http://groups.google.com/group/relacy/web/advanced-moments
Dmitriy V'jukov
For more complete information about compiler optimizations, see our Optimization Notice.