|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.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:
thread creation and exiting
lock acquisition and release
inter-thread event notifications
Memory allocation and deallocation events are intercepted and monitored:
- malloc/new/free/delete and variants
- stack allocation and deallocation
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:
- A thread may allocate memory, and write initial values into it, without locking. That thread is regarded as owning the memory exclusively.
- A thread may read and write memory which it owns exclusively, without locking.
- Memory which is owned exclusively by one thread may be read by that thread and others without locking. However, in this situation no thread may do unlocked writes to the memory (except for the owner thread's initializing write).
- Memory which is shared between multiple threads, one or more of which writes to it, must be protected by a lock which is correctly acquired and released by all threads accessing the memory.
Any violation of this discipline will cause an error to be reported. However, two exemptions apply:
A thread Y can acquire exclusive ownership of memory
previously owned exclusively by a different thread X providing
X's last access and Y's first access are separated by one of the
following synchronization events:
- X creates thread Y
- X joins back to Y
- X uses a condition-variable to signal at Y, and Y is waiting for that event
- Y completes a semaphore wait as a result of X signalling on that same semaphore
- Similarly, if thread Y joins back to thread X, memory exclusively owned by Y becomes exclusively owned by X instead. Also, memory that has been shared only by X and Y becomes exclusively owned by X. More generally, memory that has been shared by X, Y and some arbitrary other set S of threads is re-marked as shared by X and S. Hence, under the right circumstances, memory shared amongst multiple threads, all of which join into just one, can revert to the exclusive ownership state. In effect, each memory location may make arbitrarily many transitions between exclusive and shared ownership. Furthermore, a different lock may protect the location during each period of shared ownership. This significantly enhances the flexibility of the algorithm.
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 0954612051||Valgrind 3.3 - Advanced Debugging and Profiling for GNU/Linux applications||See the print edition|