For many applications multithreading is a necessity. There are two reasons why the use of threads may be required:

Multithreaded programs can use one or more of the following paradigms. Which paradigm is appropriate a.o. depends on the application type -- modeling concurrent activities versus HPC. Some examples of multithreaded programming paradigms are:

DRD supports any combination of multithreaded programming paradigms as long as the implementation of these paradigms is based on the POSIX threads primitives. DRD however does not support programs that use e.g. Linux' futexes directly. Attempts to analyze such programs with DRD will cause DRD to report many false positives.

POSIX threads, also known as Pthreads, is the most widely available threading library on Unix systems.

The POSIX threads programming model is based on the following abstractions:

Which source code statements generate which memory accesses depends on the memory model of the programming language being used. There is not yet a definitive memory model for the C and C++ languagues. For a draft memory model, see also document WG21/N2338.

For more information about POSIX threads, see also the Single UNIX Specification version 3, also known as IEEE Std 1003.1.

Depending on which multithreading paradigm is being used in a program, one or more of the following problems can occur:

Although the likelihood of the occurrence of data races can be reduced through a disciplined programming style, a tool for automatic detection of data races is a necessity when developing multithreaded software. DRD can detect these, as well as lock contention and improper use of the POSIX threads API.

Synchronization operations impose an order on interthread memory accesses. This order is also known as the happens-before relationship.

A multithreaded program is data-race free if all interthread memory accesses are ordered by synchronization operations.

A well known way to ensure that a multithreaded program is data-race free is to ensure that a locking discipline is followed. It is e.g. possible to associate a mutex with each shared data item, and to hold a lock on the associated mutex while the shared data is accessed.

All programs that follow a locking discipline are data-race free, but not all data-race free programs follow a locking discipline. There exist multithreaded programs where access to shared data is arbitrated via condition variables, semaphores or barriers. As an example, a certain class of HPC applications consists of a sequence of computation steps separated in time by barriers, and where these barriers are the only means of synchronization.

There exist two different algorithms for verifying the correctness of multithreaded programs at runtime. The so-called Eraser algorithm verifies whether all shared memory accesses follow a consistent locking strategy. And the happens-before data race detectors verify directly whether all interthread memory accesses are ordered by synchronization operations. While the happens-before data race detection algorithm is more complex to implement, and while it is more sensitive to OS scheduling, it is a general approach that works for all classes of multithreaded programs. Furthermore, the happens-before data race detection algorithm does not report any false positives.

DRD is based on the happens-before algorithm.

The following command-line options are available for controlling the behavior of the DRD tool itself:

The following options are available for monitoring the behavior of the client program:

DRD prints a message every time it detects a data race. Please keep the following in mind when interpreting DRD's output:

Below you can find an example of a message printed by DRD when it detects a data race:

$ valgrind --tool=drd --var-info=yes drd/tests/rwlock_race
...
==9466== Thread 3:
==9466== Conflicting load by thread 3/3 at 0x006020b8 size 4
==9466==    at 0x400B6C: thread_func (rwlock_race.c:29)
==9466==    by 0x4C291DF: vg_thread_wrapper (drd_pthread_intercepts.c:186)
==9466==    by 0x4E3403F: start_thread (in /lib64/libpthread-2.8.so)
==9466==    by 0x53250CC: clone (in /lib64/libc-2.8.so)
==9466== Location 0x6020b8 is 0 bytes inside local var "s_racy"
==9466== declared at rwlock_race.c:18, in frame #0 of thread 3
==9466== Other segment start (thread 2/2)
==9466==    at 0x4C2847D: pthread_rwlock_rdlock* (drd_pthread_intercepts.c:813)
==9466==    by 0x400B6B: thread_func (rwlock_race.c:28)
==9466==    by 0x4C291DF: vg_thread_wrapper (drd_pthread_intercepts.c:186)
==9466==    by 0x4E3403F: start_thread (in /lib64/libpthread-2.8.so)
==9466==    by 0x53250CC: clone (in /lib64/libc-2.8.so)
==9466== Other segment end (thread 2/2)
==9466==    at 0x4C28B54: pthread_rwlock_unlock* (drd_pthread_intercepts.c:912)
==9466==    by 0x400B84: thread_func (rwlock_race.c:30)
==9466==    by 0x4C291DF: vg_thread_wrapper (drd_pthread_intercepts.c:186)
==9466==    by 0x4E3403F: start_thread (in /lib64/libpthread-2.8.so)
==9466==    by 0x53250CC: clone (in /lib64/libc-2.8.so)
...

The above report has the following meaning:

Threads must be able to make progress without being blocked for too long by other threads. Sometimes a thread has to wait until a mutex or reader-writer lock is unlocked by another thread. This is called lock contention.

Lock contention causes delays. Such delays should be as short as possible. The two command line options --exclusive-threshold=<n> and --shared-threshold=<n> make it possible to detect excessive lock contention by making DRD report any lock that has been held longer than the specified threshold. An example:

$ valgrind --tool=drd --exclusive-threshold=10 drd/tests/hold_lock -i 500
...
==10668== Acquired at:
==10668==    at 0x4C267C8: pthread_mutex_lock (drd_pthread_intercepts.c:395)
==10668==    by 0x400D92: main (hold_lock.c:51)
==10668== Lock on mutex 0x7fefffd50 was held during 503 ms (threshold: 10 ms).
==10668==    at 0x4C26ADA: pthread_mutex_unlock (drd_pthread_intercepts.c:441)
==10668==    by 0x400DB5: main (hold_lock.c:55)
...

The hold_lock test program holds a lock as long as specified by the -i (interval) argument. The DRD output reports that the lock acquired at line 51 in source file hold_lock.c and released at line 55 was held during 503 ms, while a threshold of 10 ms was specified to DRD.

DRD is able to detect and report the following misuses of the POSIX threads API:

Just as for other Valgrind tools it is possible to let a client program interact with the DRD tool.

The interface between client programs and the DRD tool is defined in the header file <valgrind/drd.h>. The available client requests are:

Note: if you compiled Valgrind yourself, the header file <valgrind/drd.h> will have been installed in the directory /usr/include by the command make install. If you obtained Valgrind by installing it as a package however, you will probably have to install another package with a name like valgrind-devel before Valgrind's header files are present.

GNOME applications use the threading primitives provided by the glib and gthread libraries. These libraries are built on top of POSIX threads, and hence are directly supported by DRD. Please keep in mind that you have to call g_thread_init() before creating any threads, or DRD will report several data races on glib functions. See also the GLib Reference Manual for more information about g_thread_init().

One of the many facilities provided by the glib library is a block allocator, called g_slice. You have to disable this block allocator when using DRD by adding the following to the shell environment variables: G_SLICE=always-malloc. See also the GLib Reference Manual for more information.

The Qt library is the GUI library used by the KDE project. Currently there are two versions of the Qt library in use: Qt3 by KDE 3 and Qt4 by KDE 4. If possible, use Qt4 instead of Qt3. Qt3 is no longer supported, and there are known problems with multithreading support in Qt3. As an example, using QString objects in more than one thread will trigger race reports (this has been confirmed by Trolltech -- see also Trolltech task #206152).

Qt4 applications are supported by DRD, but only if the libqt4-debuginfo package has been installed. Some of the synchronization and threading primitives in Qt4 bypass the POSIX threads library, and DRD can only intercept these if symbol information for the Qt4 library is available. DRD won't tell you if it has not been able to load the Qt4 debug information, but a huge number of data races will be reported on data protected via QMutex objects.

The Boost.Thread library is the threading library included with the cross-platform Boost Libraries. This threading library is an early implementation of the upcoming C++0x threading library.

Applications that use the Boost.Thread library should run fine under DRD.

More information about Boost.Thread can be found here:

OpenMP stands for Open Multi-Processing. The OpenMP standard consists of a set of compiler directives for C, C++ and Fortran programs that allows a compiler to transform a sequential program into a parallel program. OpenMP is well suited for HPC applications and allows to work at a higher level compared to direct use of the POSIX threads API. While OpenMP ensures that the POSIX API is used correctly, OpenMP programs can still contain data races. So it makes sense to verify OpenMP programs with a thread checking tool.

DRD supports OpenMP shared-memory programs generated by gcc. The gcc compiler supports OpenMP since version 4.2.0. Gcc's runtime support for OpenMP programs is provided by a library called libgomp. The synchronization primites implemented in this library use Linux' futex system call directly, unless the library has been configured with the --disable-linux-futex flag. DRD only supports libgomp libraries that have been configured with this flag and in which symbol information is present. For most Linux distributions this means that you will have to recompile gcc. See also the script drd/scripts/download-and-build-gcc in the Valgrind source tree for an example of how to compile gcc. You will also have to make sure that the newly compiled libgomp.so library is loaded when OpenMP programs are started. This is possible by adding a line similar to the following to your shell startup script:

export LD_LIBRARY_PATH=~/gcc-4.3.2/lib64:~/gcc-4.3.2/lib:

As an example, the test OpenMP test program drd/tests/omp_matinv triggers a data race when the option -r has been specified on the command line. The data race is triggered by the following code:

#pragma omp parallel for private(j)
for (j = 0; j < rows; j++)
{
  if (i != j)
  {
    const elem_t factor = a[j * cols + i];
    for (k = 0; k < cols; k++)
    {
      a[j * cols + k] -= a[i * cols + k] * factor;
    }
  }
}

The above code is racy because the variable k has not been declared private. DRD will print the following error message for the above code:

$ valgrind --check-stack-var=yes --var-info=yes --tool=drd drd/tests/omp_matinv 3 -t 2 -r
...
Conflicting store by thread 1/1 at 0x7fefffbc4 size 4
   at 0x4014A0: gj.omp_fn.0 (omp_matinv.c:203)
   by 0x401211: gj (omp_matinv.c:159)
   by 0x40166A: invert_matrix (omp_matinv.c:238)
   by 0x4019B4: main (omp_matinv.c:316)
Allocation context: unknown.
...

In the above output the function name gj.omp_fn.0 has been generated by gcc from the function name gj. Unfortunately the variable name k is not shown as the allocation context -- it is not clear to me whether this is caused by Valgrind or whether this is caused by gcc. The most usable information in the above output is the source file name and the line number where the data race has been detected (omp_matinv.c:203).

Note: DRD reports errors on the libgomp library included with gcc 4.2.0 up to and including 4.3.2. This might indicate a race condition in the POSIX version of libgomp.

For more information about OpenMP, see also openmp.org.

DRD tracks all memory allocation events that happen via either the standard memory allocation and deallocation functions (malloc, free, new and delete) or via entry and exit of stack frames. DRD uses memory allocation and deallocation information for two purposes:

It is essential for correct operation of DRD that the tool knows about memory allocation and deallocation events. DRD does not yet support custom memory allocators, so you will have to make sure that any program which runs under DRD uses the standard memory allocation functions. As an example, the GNU libstdc++ library can be configured to use standard memory allocation functions instead of memory pools by setting the environment variable GLIBCXX_FORCE_NEW. For more information, see also the libstdc++ manual.

It is essential for correct operation of DRD that there are no memory errors such as dangling pointers in the client program. Which means that it is a good idea to make sure that your program is memcheck-clean before you analyze it with DRD. It is possible however that some of the memcheck reports are caused by data races. In this case it makes sense to run DRD before memcheck.

So which tool should be run first ? In case both DRD and memcheck complain about a program, a possible approach is to run both tools alternatingly and to fix as many errors as possible after each run of each tool until none of the two tools prints any more error messages.

The requirements of DRD with regard to heap and stack memory and the effect on the execution time of client programs are as follows:

The following information may be helpful when using DRD:

The Single UNIX Specification version two defines the following four mutex types (see also the documentation of pthread_mutexattr_settype()):

In complex applications it is not always clear from beforehand which mutex will be locked recursively and which mutex will not be locked recursively. Attempts lock a non-recursive mutex recursively will result in race conditions that are very hard to find without a thread checking tool. So either use the error checking mutex type and consistently check the return value of Pthread API mutex calls, or use the recursive mutex type.

A condition variable allows one thread to wake up one or more other threads. Condition variables are often used to notify one or more threads about state changes of shared data. Unfortunately it is very easy to introduce race conditions by using condition variables as the only means of state information propagation. A better approach is to let threads poll for changes of a state variable that is protected by a mutex, and to use condition variables only as a thread wakeup mechanism. See also the source file drd/tests/monitor_example.cpp for an example of how to implement this concept in C++. The monitor concept used in this example is a well known and very useful concept -- see also Wikipedia for more information about the monitor concept.

Historically the function pthread_cond_timedwait() only allowed the specification of an absolute timeout, that is a timeout independent of the time when this function was called. However, almost every call to this function expresses a relative timeout. This typically happens by passing the sum of clock_gettime(CLOCK_REALTIME) and a relative timeout as the third argument. This approach is incorrect since forward or backward clock adjustments by e.g. ntpd will affect the timeout. A more reliable approach is as follows:

See also drd/tests/monitor_example.cpp for an example.

Many applications log information about changes in internal or external state to a file. When analyzing log files of a multithreaded application it can be very convenient to know which thread logged which information. One possible approach is to identify threads in logging output by including the result of pthread_self() in every log line. However, this approach has two disadvantages: there is no direct relationship between these values and the source code and these values can be different in each run. A better approach is to assign a brief name to each thread and to include the assigned thread name in each log line. One possible approach for managing thread names is as follows: