1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

/* 
 * Real kernel deadlock pattern (simplified from actual Linux bug)
 * CVE-like scenario in filesystem/memory management interaction
 */
 
/* Path 1: write() syscall */
ssize_t my_write(struct file *file, const char __user *buf, size_t count) {
    struct inode *inode = file->f_inode;
    
    mutex_lock(&inode->i_mutex);     // Acquire inode lock
    
    // Allocate memory for write buffers
    void *buffer = kmalloc(count, GFP_KERNEL);  
    // GFP_KERNEL means: may block, may reclaim memory
    
    // If memory is tight, kmalloc() triggers memory reclaim...
    // which calls into the memory manager...
    
    mutex_unlock(&inode->i_mutex);
    return count;
}
 
/* Path 2: Memory reclaim path (triggered by memory pressure) */
static int my_writeback(struct address_space *mapping) {
    struct inode *inode = mapping->host;
    
    // Memory reclaim needs to flush dirty pages
    // This requires various MM locks
    
    spin_lock(&zone->lru_lock);      // Already held from reclaim
    
    // Now need to write dirty pages back to disk
    // This requires the inode lock!
    
    mutex_lock(&inode->i_mutex);     // DEADLOCK!
    // Path 1 holds i_mutex, waiting for memory (lru_lock)
    // Path 2 holds lru_lock, waiting for i_mutex
    
    spin_unlock(&zone->lru_lock);
}
 
/*
 * WHY THIS IS TRICKY:
 * 
 * 1. The deadlock involves two completely different subsystems
 *    (filesystem and memory management)
 * 
 * 2. The interaction is implicit: write() doesn't directly call
 *    the memory reclaim path—it calls kmalloc() which *might*
 *    trigger reclaim depending on memory pressure
 * 
 * 3. The bug only manifests under memory pressure (hard to test)
 * 
 * 4. Lock ordering is violated across subsystem boundaries
 * 
 * SOLUTION: Linux uses GFP_NOFS flag when called from filesystem
 *           context, telling kmalloc() not to re-enter filesystem
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

-- TRANSACTION T1: Alice transfers $100 to Bob
START TRANSACTION;
 
-- Lock Alice's account (for debit)
UPDATE accounts SET balance = balance - 100 WHERE name = 'Alice';
-- Alice's row is now locked by T1
 
-- Simulate some delay (processing, validation, etc.)
-- During this time, T2 starts...
 
-- Now try to credit Bob
UPDATE accounts SET balance = balance + 100 WHERE name = 'Bob';
-- BLOCKED! T2 holds lock on Bob's row
 
-- TRANSACTION T2: Bob transfers $50 to Alice (runs concurrently)
START TRANSACTION;
 
-- Lock Bob's account (for debit)
UPDATE accounts SET balance = balance - 50 WHERE name = 'Bob';
-- Bob's row is now locked by T2
 
-- Now try to credit Alice
UPDATE accounts SET balance = balance + 50 WHERE name = 'Alice';
-- BLOCKED! T1 holds lock on Alice's row
 
-- ═══════════════════════════════════════════════════════════
-- DEADLOCK DETECTED!
-- ═══════════════════════════════════════════════════════════
--
-- T1 holds: Alice, waiting for: Bob
-- T2 holds: Bob, waiting for: Alice
--
-- Database response (typically within seconds):
-- ERROR 1213 (40001): Deadlock found when trying to get lock; 
-- try restarting transaction
--
-- One transaction (the "victim") is rolled back automatically.
-- The other transaction proceeds.
-- Application must retry the failed transaction.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

"""
Distributed Deadlock Scenario
Three microservices, two transactions, network-distributed locks
"""
 
# Service A: Order Processing
class OrderService:
    def process_order(self, order_id, inventory_client, payment_client):
        with self.lock(f"order:{order_id}"):  # Hold lock on order
            # Check inventory
            inventory_client.reserve(order_id)  # Calls Service B
            # Process payment  
            payment_client.charge(order_id)     # Calls Service C
            # If Service B or C is waiting on us, deadlock!
 
# Service B: Inventory Management  
class InventoryService:
    def update_stock(self, product_id, order_client):
        with self.lock(f"product:{product_id}"):  # Hold lock on product
            # Verify order is valid
            order_client.validate(product_id)  # Calls Service A
            # If Service A is waiting on us, deadlock!
 
# Service C: Payment Processing
class PaymentService:
    def reverse_charge(self, payment_id, inventory_client):
        with self.lock(f"payment:{payment_id}"):  # Hold lock on payment
            # Restore inventory
            inventory_client.release(payment_id)  # Calls Service B
            # If Service B is waiting on us, deadlock!
 
"""
DEADLOCK SCENARIO:
 
Timeline:
T=0: Transaction 1 starts at OrderService, locks Order-123
T=1: Transaction 2 starts at InventoryService, locks Product-456
T=2: Transaction 1 calls InventoryService.reserve, waits for Product-456
T=3: Transaction 2 calls OrderService.validate, waits for Order-123
 
Result: Distributed deadlock!
- Transaction 1 (Node A) holds Order-123, waits for Product-456 (Node B)
- Transaction 2 (Node B) holds Product-456, waits for Order-123 (Node A)
 
CHALLENGES:
1. No single node knows the full wait-for graph
2. Network latency makes detection slow
3. Node failures complicate recovery
4. Global state is hard to snapshot consistently
 
SOLUTIONS:
1. Timeouts: Give up after N seconds (most common)
2. Distributed deadlock detection: Chandy-Misra-Haas algorithm
3. Pessimistic locking: Lock everything upfront
4. Saga pattern: Compensating transactions instead of locks
"""

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

// CLASSIC OBSERVER PATTERN DEADLOCK
 
class Observable {
    private final Object lock = new Object();
    private List<Observer> observers = new ArrayList<>();
    private int value;
    
    public void addObserver(Observer o) {
        synchronized (lock) {
            observers.add(o);
        }
    }
    
    public void setValue(int v) {
        synchronized (lock) {            // Acquire Observable's lock
            this.value = v;
            for (Observer o : observers) {
                o.onValueChanged(v);     // Callback while holding lock!
            }
        }
    }
}
 
class DataProcessor implements Observer {
    private final Object myLock = new Object();
    private Observable data;
    
    public void onValueChanged(int value) {
        synchronized (myLock) {           // Acquire our lock
            // Process the value
            processValue(value);
        }
    }
    
    public void readData() {
        synchronized (myLock) {           // Acquire our lock
            int v = data.getValue();      // Needs Observable's lock
            // ...
        }
    }
}
 
/*
 * DEADLOCK SCENARIO:
 * 
 * Thread 1: Calls observable.setValue(42)
 *   - Acquires Observable.lock
 *   - Iterates observers, calls processor.onValueChanged(42)
 *   - onValueChanged tries to acquire DataProcessor.myLock
 *   - BLOCKED if Thread 2 holds myLock
 * 
 * Thread 2: Calls processor.readData()
 *   - Acquires DataProcessor.myLock
 *   - Calls observable.getValue()
 *   - getValue() tries to acquire Observable.lock
 *   - BLOCKED because Thread 1 holds Observable.lock
 * 
 * Result: Thread 1 holds Observable.lock, waits for myLock
 *         Thread 2 holds myLock, waits for Observable.lock
 *         DEADLOCK!
 * 
 * SOLUTIONS:
 * 1. Copy observer list, release lock before callbacks
 * 2. Use concurrent collections that don't need external sync
 * 3. Post callbacks to an event queue (async notification)
 * 4. Document lock ordering: Observable.lock < DataProcessor.myLock
 */
 
// CORRECT: Release lock before callbacks
public void setValueSafe(int v) {
    List<Observer> snapshot;
    synchronized (lock) {
        this.value = v;
        snapshot = new ArrayList<>(observers);  // Copy
    }  // Lock released!
    
    for (Observer o : snapshot) {
        o.onValueChanged(v);  // Callback without holding lock
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

/*
 * Simplified USB subsystem deadlock (based on real Linux bugs)
 * 
 * This scenario involves:
 * 1. User reading sysfs attribute (cat /sys/bus/usb/devices/1-1/...)
 * 2. Device being unplugged simultaneously
 */
 
/* Path 1: User reads device attribute via sysfs */
static ssize_t show_attribute(struct device *dev, ...) {
    struct usb_device *udev = to_usb_device(dev);
    
    // Sysfs takes device lock
    device_lock(dev);                    // Lock A
    
    // Need to access USB core data
    usb_lock_device(udev);               // Lock B - BLOCKS!
    
    // ...read attribute...
    
    usb_unlock_device(udev);
    device_unlock(dev);
}
 
/* Path 2: USB device being disconnected */
static void usb_disconnect(struct usb_interface *intf) {
    struct usb_device *udev = interface_to_usbdev(intf);
    
    // USB core takes USB device lock
    usb_lock_device(udev);               // Lock B
    
    // Need to remove from sysfs
    device_del(&intf->dev);              // Needs Lock A - BLOCKS!
    
    // device_del() eventually needs device_lock()
    // But Path 1 already holds device_lock!
    
    usb_unlock_device(udev);
}
 
/*
 * DEADLOCK STATE:
 * 
 * Path 1: Holds device_lock (A), waiting for usb_lock (B)
 * Path 2: Holds usb_lock (B), waiting for device_lock (A)
 * 
 * Result: sysfs read hangs, USB disconnect hangs
 *         Computer may appear frozen to user
 * 
 * ACTUAL FIX IN LINUX:
 * - Introduced reference counting for USB devices
 * - Changed locking order to be consistent
 * - Used trylock with retry to avoid blocking
 * 
 * This bug class is so common in drivers that lockdep has
 * special annotations for device subsystems.
 */