Recursive Mutex: When One Lock Isn't Enough

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

#include <pthread.h>
#include <stdio.h>
 
// ─── Normal Mutex: DEADLOCK SCENARIO ────────────────────
 
pthread_mutex_t normal_lock = PTHREAD_MUTEX_INITIALIZER;
 
void inner_function_normal(void) {
    pthread_mutex_lock(&normal_lock);   // DEADLOCK! Already held by us
    printf("Inner: doing work
");
    pthread_mutex_unlock(&normal_lock);
}
 
void outer_function_normal(void) {
    pthread_mutex_lock(&normal_lock);
    printf("Outer: calling inner
");
    inner_function_normal();            // Never returns...
    pthread_mutex_unlock(&normal_lock);
}
 
// ─── Recursive Mutex: WORKS CORRECTLY ───────────────────
 
pthread_mutex_t recursive_lock;
 
void init_recursive_lock(void) {
    pthread_mutexattr_t attr;
    pthread_mutexattr_init(&attr);
    pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE);
    pthread_mutex_init(&recursive_lock, &attr);
    pthread_mutexattr_destroy(&attr);
}
 
void inner_function_recursive(void) {
    pthread_mutex_lock(&recursive_lock);   // OK! count becomes 2
    printf("Inner: doing work
");
    pthread_mutex_unlock(&recursive_lock); // count becomes 1
}
 
void outer_function_recursive(void) {
    pthread_mutex_lock(&recursive_lock);     // count = 1
    printf("Outer: calling inner
");
    inner_function_recursive();              // Works!
    pthread_mutex_unlock(&recursive_lock);   // count = 0, truly unlocked
}
 
// ─── Demonstration ──────────────────────────────────────
 
int main(void) {
    init_recursive_lock();
    
    // This works with recursive mutex
    outer_function_recursive();
    printf("Success!
");
    
    // This would deadlock with normal mutex (commented out)
    // outer_function_normal();  // Don't run this!
    
    pthread_mutex_destroy(&recursive_lock);
    return 0;
}

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

// RECURSIVE MUTEX IMPLEMENTATION (Conceptual)
 
#include <stdatomic.h>
#include <pthread.h>
 
typedef struct {
    atomic_int state;           // 0 = unlocked, 1 = locked
    pthread_t owner;            // Thread ID of owner
    unsigned int recursion;     // Number of times owner has locked
    // ... wait queue, etc. for blocking ...
} recursive_mutex_t;
 
int recursive_mutex_lock(recursive_mutex_t* m) {
    pthread_t self = pthread_self();
    
    // Case 1: Already own this mutex - just increment counter
    if (m->state && pthread_equal(m->owner, self)) {
        // We already hold the lock
        m->recursion++;
        return 0;  // Success, no blocking needed
    }
    
    // Case 2: Need to acquire the mutex
    // (Using pseudo-code for blocking primitive)
    while (atomic_exchange(&m->state, 1) == 1) {
        // Lock was held, wait for it
        wait_for_unlock(m);
    }
    
    // We acquired the lock
    m->owner = self;
    m->recursion = 1;  // First acquisition
    return 0;
}
 
int recursive_mutex_unlock(recursive_mutex_t* m) {
    pthread_t self = pthread_self();
    
    // Verify we own the mutex
    if (!m->state || !pthread_equal(m->owner, self)) {
        return EPERM;  // Not the owner!
    }
    
    // Decrement recursion count
    m->recursion--;
    
    if (m->recursion == 0) {
        // Last unlock - actually release the mutex
        m->owner = 0;  // Clear owner before releasing
        atomic_store(&m->state, 0);
        wake_one_waiter(m);
    }
    // else: still have outstanding locks, don't release
    
    return 0;
}
 
// KEY INSIGHT: The owner check on every lock attempt
// ─────────────────────────────────────────────────
// A normal mutex just tries to acquire atomically.
// A recursive mutex must FIRST check if we already own it,
// which requires reading the owner field and comparing thread IDs.
// This adds overhead to every lock operation.

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

// ═══════════════════════════════════════════════════════════
// USE CASE 1: Recursive Data Structure
// ═══════════════════════════════════════════════════════════
 
typedef struct tree_node {
    int value;
    struct tree_node *left;
    struct tree_node *right;
} tree_node_t;
 
typedef struct {
    tree_node_t *root;
    pthread_mutex_t lock;  // RECURSIVE
} tree_t;
 
// Recursive traversal - each call needs the lock
int tree_sum(tree_t *tree, tree_node_t *node) {
    pthread_mutex_lock(&tree->lock);  // May already hold it
    
    if (node == NULL) {
        pthread_mutex_unlock(&tree->lock);
        return 0;
    }
    
    int sum = node->value;
    sum += tree_sum(tree, node->left);   // Recursive: locks again
    sum += tree_sum(tree, node->right);  // Recursive: locks again
    
    pthread_mutex_unlock(&tree->lock);
    return sum;
}
 
// ═══════════════════════════════════════════════════════════
// USE CASE 2: Callback That Reenters API
// ═══════════════════════════════════════════════════════════
 
typedef void (*event_callback_t)(void* data);
 
typedef struct {
    pthread_mutex_t lock;  // RECURSIVE
    int value;
    event_callback_t callback;
} observable_t;
 
void observable_set(observable_t *obs, int new_value) {
    pthread_mutex_lock(&obs->lock);
    
    int old_value = obs->value;
    obs->value = new_value;
    
    if (obs->callback) {
        // Callback might call observable_set again!
        obs->callback(obs);  
    }
    
    pthread_mutex_unlock(&obs->lock);
}
 
void my_callback(void* data) {
    observable_t *obs = (observable_t*)data;
    // This needs the lock, but observable_set already holds it
    observable_set(obs, obs->value + 1);  // Works with recursive mutex
}

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

// ═══════════════════════════════════════════════════════════
// PROBLEM: Broken Invariant During Recursive Call
// ═══════════════════════════════════════════════════════════
 
typedef struct {
    pthread_mutex_t lock;  // RECURSIVE
    int count;
    int sum;
    // INVARIANT: sum == sum of all items added (when not modifying)
} accumulator_t;
 
void add_value(accumulator_t *acc, int value);  // Forward declaration
 
void add_and_log(accumulator_t *acc, int value) {
    pthread_mutex_lock(&acc->lock);    // Lock acquired
    
    // Start of modification - invariant temporarily broken
    acc->count++;
    // (sum not yet updated - invariant is broken here!)
    
    // BUG: This callback calls add_value, which tries to read/modify
    // the accumulator while it's in an inconsistent state!
    log_current_average(acc);  // Might call add_value recursively
    
    acc->sum += value;
    // (invariant restored)
    
    pthread_mutex_unlock(&acc->lock);
}
 
void log_current_average(accumulator_t *acc) {
    pthread_mutex_lock(&acc->lock);    // Recursive acquisition (count=2)
    
    // BUG: count was incremented but sum wasn't - wrong average!
    double avg = (double)acc->sum / acc->count;  // WRONG!
    printf("Average: %f
", avg);
    
    pthread_mutex_unlock(&acc->lock);
}
 
// The recursive mutex "hides" this bug by not deadlocking,
// but the data is corrupted. A normal mutex would deadlock,
// which at least makes the problem obvious during testing.

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

// ═══════════════════════════════════════════════════════════
// PATTERN 1: Separate Locked and Unlocked Helper Functions
// ═══════════════════════════════════════════════════════════
// Public functions acquire the lock; internal helpers assume it's held
 
typedef struct {
    pthread_mutex_t lock;  // NORMAL mutex - not recursive
    int value;
} counter_t;
 
// Internal helper: assumes lock is held
static void counter_add_unlocked(counter_t *c, int delta) {
    c->value += delta;
}
 
// Public API: acquires the lock
void counter_add(counter_t *c, int delta) {
    pthread_mutex_lock(&c->lock);
    counter_add_unlocked(c, delta);
    pthread_mutex_unlock(&c->lock);
}
 
// Another public function can safely call the helper
void counter_double(counter_t *c) {
    pthread_mutex_lock(&c->lock);
    int current = c->value;
    counter_add_unlocked(c, current);  // Calls helper, not public API
    pthread_mutex_unlock(&c->lock);
}
 
 
// ═══════════════════════════════════════════════════════════
// PATTERN 2: Explicit Lock State Parameter
// ═══════════════════════════════════════════════════════════
// Pass a flag indicating whether the lock is already held
 
void process_tree_node(tree_t *tree, node_t *node, bool lock_held) {
    if (!lock_held) {
        pthread_mutex_lock(&tree->lock);
    }
    
    // Do work...
    
    // Recursive call indicates lock is held
    process_tree_node(tree, node->left, true);
    process_tree_node(tree, node->right, true);
    
    if (!lock_held) {
        pthread_mutex_unlock(&tree->lock);
    }
}
 
 
// ═══════════════════════════════════════════════════════════
// PATTERN 3: Convert Recursion to Iteration
// ═══════════════════════════════════════════════════════════
// Use an explicit stack instead of call stack recursion
 
int tree_sum_iterative(tree_t *tree) {
    pthread_mutex_lock(&tree->lock);  // Lock once at the start
    
    int sum = 0;
    node_t *stack[1000];  // Explicit stack
    int sp = 0;
    
    stack[sp++] = tree->root;
    
    while (sp > 0) {
        node_t *node = stack[--sp];
        if (node != NULL) {
            sum += node->value;
            stack[sp++] = node->left;
            stack[sp++] = node->right;
        }
    }
    
    pthread_mutex_unlock(&tree->lock);  // Unlock once at the end
    return sum;
}
 
 
// ═══════════════════════════════════════════════════════════
// PATTERN 4: Release Lock Before Callback
// ═══════════════════════════════════════════════════════════
// Copy data, release lock, then invoke callback
 
void with_lock_released_callback(context_t *ctx) {
    pthread_mutex_lock(&ctx->lock);
    
    // Copy everything the callback needs
    callback_t callback = ctx->callback;
    void *callback_data = copy_deep(ctx->data);
    
    pthread_mutex_unlock(&ctx->lock);  // RELEASE before callback
    
    // Callback runs without holding any lock
    callback(callback_data);
    
    free(callback_data);
}

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

// ═══════════════════════════════════════════════════════════
// C++11 std::recursive_mutex
// ═══════════════════════════════════════════════════════════
 
#include <mutex>
#include <iostream>
 
class Counter {
private:
    std::recursive_mutex mutex_;
    int value_ = 0;
 
public:
    void add(int n) {
        std::lock_guard<std::recursive_mutex> lock(mutex_);
        value_ += n;
    }
    
    void double_value() {
        std::lock_guard<std::recursive_mutex> lock(mutex_);
        add(value_);  // Works! Same thread can relock
    }
    
    int get() {
        std::lock_guard<std::recursive_mutex> lock(mutex_);
        return value_;
    }
};
 
// C++17: Also provides std::shared_mutex for reader/writer patterns
 
// ═══════════════════════════════════════════════════════════
// Java: All monitors are recursive by default!
// ═══════════════════════════════════════════════════════════
// In Java, synchronized blocks are inherently reentrant.
// Same thread can enter synchronized(obj) multiple times.
/*
 
class JavaCounter {
    private int value = 0;
    
    public synchronized void add(int n) {
        value += n;
    }
    
    public synchronized void doubleValue() {
        add(value);  // Works! Java monitors are recursive
    }
}
 
// Also: java.util.concurrent.locks.ReentrantLock
 
*/