6.033 - Computer System Engineering Valgrind Assignment

Hands-on 3: valgrind

Complete the following hands-on assignment. Do the activities described, and submit your solutions using the online submission site by 11:59p.

This assignment relates to the Eraser paper, and exposes you to parallel programming with Pthreads, and understanding and fixing concurrency errors. You might find it helpful to skim the Eraser paper, which is assigned for the next section. You also might want to refresh your memory on what race conditions are and the troubles that they can cause by revisiting sections 5.2.2, 5.2.3, and 5.2.4 of the textbook.

This assignment involves a small amount of programming.

I. Warmup

Add the 6.033 and gcc locker:
  no-knife:~> add 6.033; add gcc
Download the program ph.c and store it in a file ph.c. On a linux system, you might do:
  no-knife:~> wget http://web.mit.edu/6.033/www/assignments/ph.c
Then compile and run it with one thread:
$ gcc -g -o ph ph.c -pthread
$ ./ph 1
completion time for put phase = 2.758351
0: 0 keys missing
completion time for get phase = 2.270119

The 1 specifies the number of threads that execute put and get operations on the the hash table. The program inserts NKEYS into a hash table in the put phase and then looks them all up in the get phase.

Let's run with 2 threads. Then each thread does NKEYS/2 puts in the put phase and NKEYS/2 lookups in the get phase. The program is written in C, the default language for low-level systems programming, and uses pthreads for creating several threads that can run in parallel if our machine has several cores (most processors today have at least 2 cores).

If we achieve perfect parallelism, then the two phases complete in half the time. Here is the output:

~/classes/6033-2013.git/wwwdocs/assignments$ ./ph 2
completion time for put phase = 1.688109
0: 27 keys missing
1: 39 keys missing
completion time for get phase = 3.215020

We see that put phase is faster now, so we were able to exploit 2 cores (but it didn't get twice as fast). The get phase, however, is slower with 2 cores, which is disappointing: using more cores, the program ran slower. More on that later, because there is a bigger problem.

You will likely observe that the code is incorrect. The application inserted 27+39 keys in phase 1 that phase 2 couldn't find. In your runs, there may be more or fewer keys missing. There may be even 0 keys missing in some runs. If you run with 1 thread, there will never be any keys missing.

Run the application with 4 threads:

~/classes/6033-2013.git/wwwdocs/assignments$ ./ph 4
completion time for put phase = 1.113811
0: 39 keys missing
2: 31 keys missing
3: 15 keys missing
1: 37 keys missing
completion time for get phase = 3.436008

Three points: 1) the put runs faster with 4 cores than 2 cores, but not 4 times as fast as a single core; 2) the get phase ran even slower; 3) more keys are missing.

II. Using valgrind to find race condition

The ph.c program is simple, and you may be able to spot the mistake immediately, but we will use a tool, helgrind that helps us find such errors automatically. helgrind is similar in spirit to the Eraser system that you are reading about, and is part of a suite of tools collectively called valgrind.

Run helgrind with ph. You will see output as follows:

$ valgrind --tool=helgrind ./ph 2
==8945== Helgrind, a thread error detector
==8945== Copyright (C) 2007-2009, and GNU GPL'd, by OpenWorks LLP et al.
==8945== Using Valgrind-3.6.0.SVN-Debian and LibVEX; rerun with -h for copyright info
==8945== Command: ./ph 2
==8945== Thread #2 was created
==8945==    at 0x513612E: clone (clone.S:77)
==8945==    by 0x4E37172: pthread_create@@GLIBC_2.2.5 (createthread.c:75)
==8945==    by 0x4C2C42C: pthread_create_WRK (hg_intercepts.c:230)
==8945==    by 0x4C2C4CF: pthread_create@* (hg_intercepts.c:257)
==8945==    by 0x4010B8: main (ph.c:148)
==8945== Thread #1 is the program's root thread
==8945== Possible data race during write of size 8 at 0x7ff000440 by thread #2
==8945==    at 0x4C2C54C: mythread_wrapper (hg_intercepts.c:200)
==8945==  This conflicts with a previous read of size 8 by thread #1
==8945==    at 0x4C2C440: pthread_create_WRK (hg_intercepts.c:235)
==8945==    by 0x4C2C4CF: pthread_create@* (hg_intercepts.c:257)
==8945==    by 0x4010B8: main (ph.c:148)
==8945== Thread #3 was created
==8945==    at 0x513612E: clone (clone.S:77)
==8945==    by 0x4E37172: pthread_create@@GLIBC_2.2.5 (createthread.c:75)
==8945==    by 0x4C2C42C: pthread_create_WRK (hg_intercepts.c:230)
==8945==    by 0x4C2C4CF: pthread_create@* (hg_intercepts.c:257)
==8945==    by 0x4010B8: main (ph.c:148)
==8945== Possible data race during read of size 4 at 0x1d47168 by thread #3
==8945==    at 0x400C24: put (ph.c:61)
==8945==    by 0x400EA1: put_thread (ph.c:98)
==8945==    by 0x4C2C558: mythread_wrapper (hg_intercepts.c:202)
==8945==    by 0x4E369C9: start_thread (pthread_create.c:300)
==8945==    by 0x67D46FF: ???
==8945==  This conflicts with a previous write of size 4 by thread #2
==8945==    at 0x400CC6: put (ph.c:64)
==8945==    by 0x400EA1: put_thread (ph.c:98)
==8945==    by 0x4C2C558: mythread_wrapper (hg_intercepts.c:202)
==8945==    by 0x4E369C9: start_thread (pthread_create.c:300)
==8945==    by 0x5FD36FF: ???
==8945== More than 10000000 total errors detected.  I'm not reporting any more.
==8945== Final error counts will be inaccurate.  Go fix your program!
==8945== Rerun with --error-limit=no to disable this cutoff.  Note
==8945== that errors may occur in your program without prior warning from
==8945== Valgrind, because errors are no longer being displayed.

Question 1: Study helgrind's output and the ph.c program. Clearly something is wrong with put() on line 61. Why are there missing keys with 2 or more threads, but not with 1 thread? Identify a sequence of events that can lead to keys missing for 2 threads.

Fixing the error

To avoid this sequence of events, insert lock and unlock statements in put so that the number keys missing is always 0. The relevant pthread calls are (for more see the manual pages, man pthread):

pthread_mutex_t lock;     // declare a lock
pthread_mutex_init(&lock, NULL);   // initialize the lock
pthread_mutex_lock(&lock);  // acquire lock
pthread_mutex_unlock(&lock);  // release lock

The function get() has an example use of locks, and main initializes it.

Modify ph.c to make it correct and recompile with gcc. Test your code first with 1 thread, then test it with 2 threads. Is it correct (i.e. have you eliminated missing keys)? Check the correctness using helgrind. (Note that valgrind slows down ph a lot, so you may want to modify NKEYS to be some small number.)

Question 2: Describe your changes and argue why these changes ensure correctness.

Question 3: Is the two-threaded version faster than the single-threaded version in the put phase? Report the running times for the two-threaded version and the single-threaded version. (Make sure to undo your NKEYS change.)

Question 4: Most likely (depending on your exact changes) ph won't achieve any speedup. Why is that?

Living dangerously

Remove the locks from get() in ph.c, recompile, and rerun the program.

Question 5: You should observe speedup on several cores for the get phase of ph. Why is that?

Question 6: Why does valgrind report no errors for get()?


Question 7: Can you think of a way of modifying ph.c so that you get speedup for both phases and valgrind won't report race conditions? (If you have time, implement that plan and check.)

Go to 6.033 Home Page