8. DRD: a thread error detector

To model concurrent activities. Assigning one thread to each activity can be a great simplification compared to multiplexing the states of multiple activities in a single thread. This is why most server software and embedded software is multithreaded.

To use multiple CPU cores simultaneously for speeding up computations. This is why many High Performance Computing (HPC) applications are multithreaded.

Locking. Data that is shared over threads is protected from concurrent accesses via locking. E.g. the POSIX threads library, the Qt library and the Boost.Thread library support this paradigm directly.

Message passing. No data is shared between threads, but threads exchange data by passing messages to each other. Examples of implementations of the message passing paradigm are MPI and CORBA.

Automatic parallelization. A compiler converts a sequential program into a multithreaded program. The original program may or may not contain parallelization hints. One example of such parallelization hints is the OpenMP standard. In this standard a set of directives are defined which tell a compiler how to parallelize a C, C++ or Fortran program. OpenMP is well suited for computational intensive applications. As an example, an open source image processing software package is using OpenMP to maximize performance on systems with multiple CPU cores. GCC supports the OpenMP standard from version 4.2.0 on.

Software Transactional Memory (STM). Any data that is shared between threads is updated via transactions. After each transaction it is verified whether there were any conflicting transactions. If there were conflicts, the transaction is aborted, otherwise it is committed. This is a so-called optimistic approach. There is a prototype of the Intel C++ Compiler available that supports STM. Research about the addition of STM support to GCC is ongoing.

A shared address space. All threads running within the same process share the same address space. All data, whether shared or not, is identified by its address.

Regular load and store operations, which allow to read values from or to write values to the memory shared by all threads running in the same process.

Atomic store and load-modify-store operations. While these are not mentioned in the POSIX threads standard, most microprocessors support atomic memory operations.

Threads. Each thread represents a concurrent activity.

Synchronization objects and operations on these synchronization objects. The following types of synchronization objects have been defined in the POSIX threads standard: mutexes, condition variables, semaphores, reader-writer synchronization objects, barriers and spinlocks.

Data races. One or more threads access the same memory location without sufficient locking. Most but not all data races are programming errors and are the cause of subtle and hard-to-find bugs.

Lock contention. One thread blocks the progress of one or more other threads by holding a lock too long.

Improper use of the POSIX threads API. Most implementations of the POSIX threads API have been optimized for runtime speed. Such implementations will not complain on certain errors, e.g. when a mutex is being unlocked by another thread than the thread that obtained a lock on the mutex.

Deadlock. A deadlock occurs when two or more threads wait for each other indefinitely.

False sharing. If threads that run on different processor cores access different variables located in the same cache line frequently, this will slow down the involved threads a lot due to frequent exchange of cache lines.

Every thread is assigned a thread ID by the DRD tool. A thread ID is a number. Thread ID's start at one and are never recycled.

The term segment refers to a consecutive sequence of load, store and synchronization operations, all issued by the same thread. A segment always starts and ends at a synchronization operation. Data race analysis is performed between segments instead of between individual load and store operations because of performance reasons.

There are always at least two memory accesses involved in a data race. Memory accesses involved in a data race are called conflicting memory accesses. DRD prints a report for each memory access that conflicts with a past memory access.

The number in the column on the left is the process ID of the process being analyzed by DRD.

The first line ("Thread 3") tells you the thread ID for the thread in which context the data race has been detected.

The next line tells which kind of operation was performed (load or store) and by which thread. On the same line the start address and the number of bytes involved in the conflicting access are also displayed.

Next, the call stack of the conflicting access is displayed. If your program has been compiled with debug information (-g), this call stack will include file names and line numbers. The two bottommost frames in this call stack (clone and start_thread) show how the NPTL starts a thread. The third frame (vg_thread_wrapper) is added by DRD. The fourth frame (thread_func) is the first interesting line because it shows the thread entry point, that is the function that has been passed as the third argument to pthread_create.

Next, the allocation context for the conflicting address is displayed. For dynamically allocated data the allocation call stack is shown. For static variables and stack variables the allocation context is only shown when the option --read-var-info=yes has been specified. Otherwise DRD will print Allocation context: unknown.

A conflicting access involves at least two memory accesses. For one of these accesses an exact call stack is displayed, and for the other accesses an approximate call stack is displayed, namely the start and the end of the segments of the other accesses. This information can be interpreted as follows:

Passing the address of one type of synchronization object (e.g. a mutex) to a POSIX API call that expects a pointer to another type of synchronization object (e.g. a condition variable).

Attempts to unlock a mutex that has not been locked.

Attempts to unlock a mutex that was locked by another thread.

Attempts to lock a mutex of type PTHREAD_MUTEX_NORMAL or a spinlock recursively.

Destruction or deallocation of a locked mutex.

Sending a signal to a condition variable while no lock is held on the mutex associated with the condition variable.

Calling pthread_cond_wait on a mutex that is not locked, that is locked by another thread or that has been locked recursively.

Associating two different mutexes with a condition variable through pthread_cond_wait.

Destruction or deallocation of a condition variable that is being waited upon.

Destruction or deallocation of a locked reader-writer synchronization object.

Attempts to unlock a reader-writer synchronization object that was not locked by the calling thread.

Attempts to recursively lock a reader-writer synchronization object exclusively.

Attempts to pass the address of a user-defined reader-writer synchronization object to a POSIX threads function.

Attempts to pass the address of a POSIX reader-writer synchronization object to one of the annotations for user-defined reader-writer synchronization objects.

Reinitialization of a mutex, condition variable, reader-writer lock, semaphore or barrier.

Destruction or deallocation of a semaphore or barrier that is being waited upon.

Missing synchronization between barrier wait and barrier destruction.

Exiting a thread without first unlocking the spinlocks, mutexes or reader-writer synchronization objects that were locked by that thread.

Passing an invalid thread ID to pthread_join or pthread_cancel.

The macro DRD_GET_VALGRIND_THREADID and the corresponding client request VG_USERREQ__DRD_GET_VALGRIND_THREAD_ID. Query the thread ID that has been assigned by the Valgrind core to the thread executing this client request. Valgrind's thread ID's start at one and are recycled in case a thread stops.

The macro DRD_GET_DRD_THREADID and the corresponding client request VG_USERREQ__DRD_GET_DRD_THREAD_ID. Query the thread ID that has been assigned by DRD to the thread executing this client request. These are the thread ID's reported by DRD in data race reports and in trace messages. DRD's thread ID's start at one and are never recycled.

The macros DRD_IGNORE_VAR(x), ANNOTATE_TRACE_MEMORY(&x) and the corresponding client request VG_USERREQ__DRD_START_SUPPRESSION. Some applications contain intentional races. There exist e.g. applications where the same value is assigned to a shared variable from two different threads. It may be more convenient to suppress such races than to solve these. This client request allows one to suppress such races.

The macro DRD_STOP_IGNORING_VAR(x) and the corresponding client request VG_USERREQ__DRD_FINISH_SUPPRESSION. Tell DRD to no longer ignore data races for the address range that was suppressed either via the macro DRD_IGNORE_VAR(x) or via the client request VG_USERREQ__DRD_START_SUPPRESSION.

The macro DRD_TRACE_VAR(x). Trace all load and store activity for the address range starting at &x and occupying sizeof(x) bytes. When DRD reports a data race on a specified variable, and it's not immediately clear which source code statements triggered the conflicting accesses, it can be very helpful to trace all activity on the offending memory location.

The macro DRD_STOP_TRACING_VAR(x). Stop tracing load and store activity for the address range starting at &x and occupying sizeof(x) bytes.

The macro ANNOTATE_TRACE_MEMORY(&x). Trace all load and store activity that touches at least the single byte at the address &x.

The client request VG_USERREQ__DRD_START_TRACE_ADDR, which allows one to trace all load and store activity for the specified address range.

The client request VG_USERREQ__DRD_STOP_TRACE_ADDR. Do no longer trace load and store activity for the specified address range.

The macro ANNOTATE_HAPPENS_BEFORE(addr) tells DRD to insert a mark. Insert this macro just after an access to the variable at the specified address has been performed.

The macro ANNOTATE_HAPPENS_AFTER(addr) tells DRD that the next access to the variable at the specified address should be considered to have happened after the access just before the latest ANNOTATE_HAPPENS_BEFORE(addr) annotation that references the same variable. The purpose of these two macros is to tell DRD about the order of inter-thread memory accesses implemented via atomic memory operations. See also drd/tests/annotate_smart_pointer.cpp for an example.

The macro ANNOTATE_RWLOCK_CREATE(rwlock) tells DRD that the object at address rwlock is a reader-writer synchronization object that is not a pthread_rwlock_t synchronization object. See also drd/tests/annotate_rwlock.c for an example.

The macro ANNOTATE_RWLOCK_DESTROY(rwlock) tells DRD that the reader-writer synchronization object at address rwlock has been destroyed.

The macro ANNOTATE_WRITERLOCK_ACQUIRED(rwlock) tells DRD that a writer lock has been acquired on the reader-writer synchronization object at address rwlock.

The macro ANNOTATE_READERLOCK_ACQUIRED(rwlock) tells DRD that a reader lock has been acquired on the reader-writer synchronization object at address rwlock.

The macro ANNOTATE_RWLOCK_ACQUIRED(rwlock, is_w) tells DRD that a writer lock (when is_w != 0) or that a reader lock (when is_w == 0) has been acquired on the reader-writer synchronization object at address rwlock.

The macro ANNOTATE_WRITERLOCK_RELEASED(rwlock) tells DRD that a writer lock has been released on the reader-writer synchronization object at address rwlock.

The macro ANNOTATE_READERLOCK_RELEASED(rwlock) tells DRD that a reader lock has been released on the reader-writer synchronization object at address rwlock.

The macro ANNOTATE_RWLOCK_RELEASED(rwlock, is_w) tells DRD that a writer lock (when is_w != 0) or that a reader lock (when is_w == 0) has been released on the reader-writer synchronization object at address rwlock.

The macro ANNOTATE_BARRIER_INIT(barrier, count, reinitialization_allowed) tells DRD that a new barrier object at the address barrier has been initialized, that count threads participate in each barrier and also whether or not barrier reinitialization without intervening destruction should be reported as an error. See also drd/tests/annotate_barrier.c for an example.

The macro ANNOTATE_BARRIER_DESTROY(barrier) tells DRD that a barrier object is about to be destroyed.

The macro ANNOTATE_BARRIER_WAIT_BEFORE(barrier) tells DRD that waiting for a barrier will start.

The macro ANNOTATE_BARRIER_WAIT_AFTER(barrier) tells DRD that waiting for a barrier has finished.

The macro ANNOTATE_BENIGN_RACE_SIZED(addr, size, descr) tells DRD that any races detected on the specified address are benign and hence should not be reported. The descr argument is ignored but can be used to document why data races on addr are benign.

The macro ANNOTATE_BENIGN_RACE_STATIC(var, descr) tells DRD that any races detected on the specified static variable are benign and hence should not be reported. The descr argument is ignored but can be used to document why data races on var are benign. Note: this macro can only be used in C++ programs and not in C programs.

The macro ANNOTATE_IGNORE_READS_BEGIN tells DRD to ignore all memory loads performed by the current thread.

The macro ANNOTATE_IGNORE_READS_END tells DRD to stop ignoring the memory loads performed by the current thread.

The macro ANNOTATE_IGNORE_WRITES_BEGIN tells DRD to ignore all memory stores performed by the current thread.

The macro ANNOTATE_IGNORE_WRITES_END tells DRD to stop ignoring the memory stores performed by the current thread.

The macro ANNOTATE_IGNORE_READS_AND_WRITES_BEGIN tells DRD to ignore all memory accesses performed by the current thread.

The macro ANNOTATE_IGNORE_READS_AND_WRITES_END tells DRD to stop ignoring the memory accesses performed by the current thread.

The macro ANNOTATE_NEW_MEMORY(addr, size) tells DRD that the specified memory range has been allocated by a custom memory allocator in the client program and that the client program will start using this memory range.

The macro ANNOTATE_THREAD_NAME(name) tells DRD to associate the specified name with the current thread and to include this name in the error messages printed by DRD.

The macros VALGRIND_MALLOCLIKE_BLOCK and VALGRIND_FREELIKE_BLOCK from the Valgrind core are implemented; they are described in The Client Request mechanism.

Add the following code at the start of a common header or at the start of each source file, before any C++ header files are included:

#include <valgrind/drd.h>
#define _GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(addr) ANNOTATE_HAPPENS_BEFORE(addr)
#define _GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(addr)  ANNOTATE_HAPPENS_AFTER(addr)

Download the gcc source code and from source file libstdc++-v3/src/c++11/thread.cc copy the implementation of the execute_native_thread_routine() and std::thread::_M_start_thread() functions into a source file that is linked with your application. Make sure that also in this source file the _GLIBCXX_SYNCHRONIZATION_HAPPENS_*() macros are defined properly.

Anthony Williams, Boost.Thread Library Documentation, Boost website, 2007.

Anthony Williams, What's New in Boost Threads?, Recent changes to the Boost Thread library, Dr. Dobbs Magazine, October 2008.

To know where the scope ends of POSIX objects that have not been destroyed explicitly. It is e.g. not required by the POSIX threads standard to call pthread_mutex_destroy before freeing the memory in which a mutex object resides.

To know where the scope of variables ends. If e.g. heap memory has been used by one thread, that thread frees that memory, and another thread allocates and starts using that memory, no data races must be reported for that memory.

When running a program under DRD with default DRD options, between 1.1 and 3.6 times more memory will be needed compared to a native run of the client program. More memory will be needed if loading debug information has been enabled (--read-var-info=yes).

DRD allocates some of its temporary data structures on the stack of the client program threads. This amount of data is limited to 1 - 2 KB. Make sure that thread stacks are sufficiently large.

Most applications will run between 20 and 50 times slower under DRD than a native single-threaded run. The slowdown will be most noticeable for applications which perform frequent mutex lock / unlock operations.

Make sure that debug information is present in the executable being analyzed, such that DRD can print function name and line number information in stack traces. Most compilers can be told to include debug information via compiler option -g.

Compile with option -O1 instead of -O0. This will reduce the amount of generated code, may reduce the amount of debug info and will speed up DRD's processing of the client program. For more information, see also Getting started.

If DRD reports any errors on libraries that are part of your Linux distribution like e.g. libc.so or libstdc++.so, installing the debug packages for these libraries will make the output of DRD a lot more detailed.

When using C++, do not send output from more than one thread to std::cout. Doing so would not only generate multiple data race reports, it could also result in output from several threads getting mixed up. Either use printf or do the following:

normal, which means that no error checking is performed, and that the mutex is non-recursive.

error checking, which means that the mutex is non-recursive and that error checking is performed.

recursive, which means that a mutex may be locked recursively.

default, which means that error checking behavior is undefined, and that the behavior for recursive locking is also undefined. Or: portable code must neither trigger error conditions through the Pthreads API nor attempt to lock a mutex of default type recursively.

When initializing a condition variable through pthread_cond_init, specify that the timeout of pthread_cond_timedwait will use the clock CLOCK_MONOTONIC instead of CLOCK_REALTIME. You can do this via pthread_condattr_setclock(..., CLOCK_MONOTONIC).

When calling pthread_cond_timedwait, pass the sum of clock_gettime(CLOCK_MONOTONIC) and a relative timeout as the third argument.