CSE Roadmap

Core tier · about 5 hours · 8 parts

Part 5 of 8 · 2 min read

Tools

In plain words: The thread dump shows a deadlock after it happened. Two tools find the mistake while the program still runs, because they watch the order of the locks, as a person would read the code. They can warn even when no deadlock occurs.

ThreadSanitizer (TSan). Build with gcc -g -fsanitize=thread. For the transfer program with 2 threads and plain pthread_mutex_lock calls, three runs of 3 s each gave 14, 16 and 16 reports of this kind, and the exit code 66:

WARNING: ThreadSanitizer: lock-order-inversion (potential deadlock)
  Cycle in lock order graph: M0 => M1 => M0
  Mutex M1 acquired here while holding mutex M0 in thread T1: ... transfer ...
  Mutex M0 acquired here while holding mutex M1 in thread T1: ... transfer ...

Some reports showed longer cycles with three mutexes, such as M0 => M1 => M2 => M0. The report names the exact line of the second lock. The same kind of report appeared for a small two-lock test program in which the two threads ran one after the other and finished normally. TSan records the order in which locks are taken, and warns when the records contradict each other. In a version of the transfer program that used pthread_mutex_timedlock for the second lock, TSan gave no such report in three runs, so a tool may not follow every kind of lock call.

Helgrind (valgrind --tool=helgrind). In a 3 s run, it printed two messages in the form lock order "A before B" violated, naming the two threads and the order each used. After that, the run was so slow, and the program so stuck, that it did not finish within 100 s, so the run was stopped.

Both tools report noise as well. The monitoring loop in the test program read the transfer counters without a lock, and TSan reported those reads as data races. Read each report, and look at the lock-order ones first.

Lock-order inversion

A lock-order inversion is a pair of code paths that take the same two locks in opposite orders; it is a possible deadlock even in a run in which no deadlock occurs.

Example: one transfer takes the lock of account 1 and then account 3, and another takes 3 and then 1.

Common mistake

A clean report from a tool does not prove that a program is free of deadlocks. A tool sees only the code paths that ran. Run it on tests that exercise every path, and treat a report as a bug even when the program has never frozen.

Check yourself: 1. What does TSan record that lets it warn when no deadlock has happened? 2. Why should a report from TSan not be ignored because the program "works"? 3. What was one case in which TSan gave no lock-order report for the same mistake?