locks held, ordered, or forgotten

Threading & Mutexes

Mutexes serialize access — until one is acquired out of order (deadlock) or retried in lockstep (livelock). Both achieve nothing.

The lock that protects you from a race is the lock that deadlocks you.

01in the wild

In the wild

Deadlock: Acquire in One Order

Two locks taken in opposite orders freeze forever, each thread waiting on the other.

example.py

# DEADLOCK: two locks taken in opposite orders
# thread 1: lock(a) ; lock(b)
# thread 2: lock(b) ; lock(a)   <- each waits on the other

# RIGHT: impose a global lock ordering
def transfer(src, dst, amount):
    first, second = sorted((src, dst), key=id)
    with first.lock, second.lock:        # always same order
        src.balance -= amount
        dst.balance += amount

Deadlock needs a cycle in the wait graph. Acquire locks in one consistent order and the cycle can't form.

// observed

unordered: threads freeze, NOTHING ACHIEVED
ordered:   no cycle, transfers complete

example.java

// SMELL: lock order depends on argument order -> deadlock
void transfer(Account a, Account b, long amt) {
    synchronized (a) { synchronized (b) { /* ... */ } }
}

// RIGHT: order locks by a stable key (e.g. account id)
void transfer(Account a, Account b, long amt) {
    Account first = a.id < b.id ? a : b, second = a.id < b.id ? b : a;
    synchronized (first) { synchronized (second) { /* ... */ } }
}

transfer(x, y) and transfer(y, x) grab the locks in opposite orders. Sorting by a stable key gives every thread the same order.

// observed

by-arg order: two transfers deadlock
by-id order:  no cycle possible

Livelock: Back Off With Jitter

Both threads politely release and retry in lockstep, busy forever, achieving nothing.

example.java

// LIVELOCK: both threads politely back off forever
while (!acquireBoth()) {
    releaseAll();
    Thread.sleep(0);     // both retry in lockstep, get nowhere
}

// RIGHT: randomized backoff breaks the symmetry
while (!acquireBoth()) {
    releaseAll();
    Thread.sleep(random.nextInt(50));   // jitter
}

Livelock is deadlock's busy cousin: lots of activity, zero progress. Random jitter desynchronizes the retries.

// observed

lockstep: SO MUCH IS HAPPENING, nothing done
jitter:   one thread wins, work proceeds

example.go

// SMELL: spin-retry with no backoff -> two goroutines livelock
for !tryAcquire() {
    release()
    // immediately retry, in perfect step with the other
}

// RIGHT: exponential backoff with jitter
for attempt := 0; !tryAcquire(); attempt++ {
    release()
    d := time.Duration(1<<attempt)*time.Millisecond + jitter()
    time.Sleep(d)
}

Tight retry loops keep two actors in sync so neither makes progress. Growing, jittered sleeps break the symmetry.

// observed

no backoff: 100% CPU, no progress
backoff:    one acquires, the other follows

02cross-pollination

Where this compounds

Nondeterminism

Lost Update (Read-Modify-Write Race) × ++ / -- & Integer Overflow
Concurrent Modification During Iteration × for-Loop Control Flow
Lazy-Init Visibility Race (Double-Checked Locking) × Improper Initialization

Data Corruption

NaN Poisons a Shared Aggregate × Divide by Zero
Lossy Coercion Poisons a Shared Ledger × Type Errors in Dynamic Languages

03weakness catalog

Mapped weaknesses (CWE)

On its own, this defect is catalogued by MITRE as one or more of these weaknesses. The exploitable vulnerability usually appears only when it chains or combines with another.