- 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.3 Transfers of Exclusive Ownership Between Threads

As presented, the algorithm is far too strict. It reports many errors in perfectly correct, widely used parallel programming constructions, for example, using child worker threads and worker thread pools.

To avoid these false errors, we must refine the algorithm so that it keeps memory in an Exclusive ownership state in cases where it would otherwise decay into a shared-readonly or shared-modified state. Recall that Exclusive ownership is special in that it grants the owning thread the right to access memory without use of any locks. In order to support worker-thread and worker-thread-pool idioms, we will allow threads to steal exclusive ownership of memory from other threads under certain circumstances.

Here's an example. Imagine a parent thread creates child threads to do units of work. For each unit of work, the parent allocates a work buffer, fills it in, and creates the child thread, handing it a pointer to the buffer. The child reads/writes the buffer and eventually exits, and the waiting parent then extracts the results from the buffer:

typedef ... Buffer;

pthread_t child;
Buffer    buf;

/* ---- Parent ---- */            /* ---- Child ---- */

/* parent writes workload into buf */
pthread_create( &child, child_fn, &buf );

/* parent does not read */        void child_fn (Buffer* buf) {
/* or write buf */                /* read/write buf */

pthread_join ( child );
/* parent reads results from buf */

Although ‘buf’ is accessed by both threads, neither uses locks, yet the program is race-free. The essential observation is that the child's creation and exit create synchronisation events between it and the parent. These force the child's accesses to ‘buf’ to happen after the parent initialises ‘buf’, and before the parent reads the results from ‘buf’.

To model this, Helgrind allows the child to steal, from the parent, exclusive ownership of any memory exclusively owned by the parent before the pthread_create call. Similarly, once the parent's pthread_join call returns, it can steal back ownership of memory exclusively owned by the child. In this way ownership of ‘buf’ is transferred from parent to child and back, so the basic algorithm does not report any races despite the absence of any locking.

Note that the child may only steal memory owned by the parent prior to the pthread_create call. If the child attempts to read or write memory which is also accessed by the parent in between the pthread_create and pthread_join calls, an error is still reported.

This technique was introduced with the name “thread lifetime segments” in “Runtime Checking of Multithreaded Applications with Visual Threads”, (Jerry J. Harrow, Jr, Proceedings of the 7th International SPIN Workshop on Model Checking of Software Stanford, California, USA, August 2000, LNCS 1885, pp331--342). Helgrind implements an extended version of it. Specifically, Helgrind allows transfer of exclusive ownership in the following situations:

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