CSE Roadmap

Core tier · about 5 hours · 8 parts

Part 6 of 8 · 3 min read

Fix

In plain words: Page 3 gave the standard cure: a global lock order. The accounts already have numbers, so the order is "lower account number first". Two details need care. A transfer from an account to itself must be handled, or the code would lock the same mutex twice. And the order must apply to every path that takes two account locks.

void transfer(int a, int b) {
    if (a == b) return;                       /* nothing to move; avoids locking one mutex twice */
    int lo = a < b ? a : b, hi = a < b ? b : a;
    pthread_mutex_lock(&acc[lo].m);           /* always the lower number first */
    pthread_mutex_lock(&acc[hi].m);
    acc[a].bal--;  acc[b].bal++;
    pthread_mutex_unlock(&acc[hi].m);
    pthread_mutex_unlock(&acc[lo].m);
}

The proof of page 3 applies: every thread takes locks in rising order, so the lock with the highest number among those held is never wanted by a thread that already holds it, and no cycle can form.

A fix is only believed when it is tested. Three tests were run:

Test Before the fix After the fix
Five stress runs, 4 threads, 3 s All five froze (9 to 703 transfers) None froze; 29.8 to 31.8 million transfers per run
Total money after each run Not reached 4,000 in all five runs
TSan, 2 threads, three runs of 3 s 14, 16 and 16 lock-order reports 0, 0 and 0 lock-order reports

The total of 4,000 is the integrity check: money was not lost or created. The TSan result shows that the order mistake is gone in the code paths that ran. A regression test keeps the bug from coming back: the stress run and the TSan run are added to the test suite, so that a later change that takes two locks in the wrong order makes a test fail. The rank checker of page 3, section 6, makes the failure immediate, even in a run with one thread.

Other cures from page 3 would also work. One big lock was 8.5 to 11.2 million transfers per second with 4 threads, trylock with back-off was 15.6 to 15.9 million, and ordering was 17.5 to 18.1 million. Ordering was chosen because it was the fastest with 4 threads and needs no retry logic.

Regression test

A regression test is an automated test that fails if a bug that was fixed returns, so that the fix is protected against later changes.

Example: a 3 s stress run with a time limit, plus a TSan run that must report no lock-order inversion.

Interview angle

The question "Tell me about a bug you debugged" fits this story. Give the five steps: symptom (0% processor use, threads asleep on locks), reproducer (random transfers, watchdog), diagnosis (thread dump, owners, cycle), fix (lock ordering, with the self-transfer case), and proof (stress run, TSan, regression test). Say what you would do to stop it from coming back.

Check yourself: 1. Why does the fix need the test a == b? 2. Why is the total money a useful check? 3. What would a regression test for this bug contain?