|Valgrind 3.3 - Advanced Debugging and Profiling for GNU/Linux applications|
by J. Seward, N. Nethercote, J. Weidendorfer and the Valgrind Development Team
Paperback (6"x9"), 164 pages
RRP £12.95 ($19.95)
9.4.2 Helgrind's Memory State Machine
Helgrind tracks the state of every byte of memory used by your program. There are a number of states, but only three are interesting:
- Exclusive: memory in this state is regarded as owned exclusively by one particular thread. That thread may read and write it without a lock. Even in highly threaded programs, the majority of locations never leave the Exclusive state, since most data is thread-private.
- Shared-Readonly: memory in this state is regarded as shared by multiple threads. In this state, any thread may read the memory without a lock, reflecting the fact that readonly data may safely be shared between threads without locking.
- Shared-Modified: memory in this state is regarded as shared by multiple threads, at least one of which has written to it. All participating threads must hold at least one lock in common when accessing the memory. If no such lock exists, Helgrind reports a race error.
Let's review the simple example above with this in mind. When the program starts, ‘var’ is not in any of these states. Either the parent or child thread gets to its ‘var++’ first, and thereby thereby gets Exclusive ownership of the location.
The later-running thread now arrives at its ‘var++’ statement. It first reads the existing value from memory. Because ‘var’ is currently marked as owned exclusively by the other thread, its state is changed to shared-readonly by both threads.
This same thread adds one to the value it has and stores it back in ‘var’. This causes another state change, this time to the shared-modified state. Because Helgrind has also been tracking which threads hold which locks, it can see that ‘var’ is in shared-modified state but no lock has been used to consistently protect it. Hence a race is reported exactly at the transition from shared-readonly to shared-modified.
The essence of the algorithm is this. Helgrind keeps track of each memory location that has been accessed by more than one thread. For each such location it incrementally infers the set of locks which have consistently been used to protect that location. If the location's lockset becomes empty, and at some point one of the threads attempts to write to it, a race is then reported.
This technique is known as “lockset inference” and was introduced in: “Eraser: A Dynamic Data Race Detector for Multithreaded Programs”, (Stefan Savage, Michael Burrows, Greg Nelson, Patrick Sobalvarro and Thomas Anderson, ACM Transactions on Computer Systems, 15(4):391-411, November 1997).
Lockset inference has since been widely implemented, studied and extended. Helgrind incorporates several refinements aimed at avoiding the high false error rate that naive versions of the algorithm suffer from. A summary of the complete algorithm used by Helgrind (see 9.4.5) is presented below. First, however, it is important to understand details of transitions pertaining to the Exclusive-ownership state.
|ISBN 0954612051||Valgrind 3.3 - Advanced Debugging and Profiling for GNU/Linux applications||See the print edition|