- publishing free software manuals
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
ISBN 0954612051
RRP £12.95 ($19.95)

Get a printed copy>>>

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:

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 0954612051Valgrind 3.3 - Advanced Debugging and Profiling for GNU/Linux applicationsSee the print edition