- 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.5 A Summary of the Race Detection Algorithm

Helgrind looks for memory locations which are accessed by more than one thread. For each such location, Helgrind records which of the program's locks were held by the accessing thread at the time of each access. The hope is to discover that there is indeed at least one lock which is consistently used by all threads to protect that location. If no such lock can be found, then there is apparently no consistent locking strategy being applied for that location, and so a possible data race might result. Helgrind accordingly reports an error.

In practice this discipline is far too simplistic, and is unusable since it reports many races in some widely used and known-correct programming disciplines. Helgrind's checking therefore incorporates many refinements to this basic idea, and can be summarised as follows:

The following thread events are intercepted and monitored:

Memory allocation and deallocation events are intercepted and monitored:

All memory accesses are intercepted and monitored.

By observing the above events, Helgrind can infer certain aspects of the program's locking discipline. Programs which adhere to the following rules are considered to be acceptable:

Any violation of this discipline will cause an error to be reported. However, two exemptions apply:

The ownership state, accessing thread-set and related lock-set for each memory location are tracked at 8-bit granularity. This means the algorithm is precise even for 16- and 8-bit memory accesses.

Helgrind correctly handles reader-writer locks in this framework. Locations shared between multiple threads can be protected during reads by locks held in either read-mode or write-mode, but can only be protected during writes by locks held in write-mode. Normal POSIX mutexes are treated as if they are reader-writer locks which are only ever held in write-mode.

Helgrind correctly handles POSIX mutexes for which recursive locking is allowed.

Helgrind partially correctly handles x86 and amd64 memory access instructions preceded by a LOCK prefix. Writes are correctly handled, by pretending that the LOCK prefix implies acquisition and release of a magic “bus hardware lock” mutex before and after the instruction. This unfortunately requires subsequent reads from such locations to also use a LOCK prefix, which is not required by the real hardware. Helgrind does not offer any equivalent handling for atomic sequences on PowerPC/POWER platforms created by the use of lwarx/stwcx instructions.

ISBN 0954612051Valgrind 3.3 - Advanced Debugging and Profiling for GNU/Linux applicationsSee the print edition