Linux Implementation

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

# Linux kernel futex source structure (as of Linux 6.x)
 
kernel/futex/
├── core.c          # Core infrastructure: hash table, key computation
├── futex.h         # Internal header: structs, inline functions
├── pi.c            # Priority inheritance futex implementation
├── requeue.c       # FUTEX_REQUEUE and variants
├── waitwake.c      # FUTEX_WAIT and FUTEX_WAKE
├── Makefile        # Build configuration
 
# Key files and their responsibilities:
 
## core.c (~1200 lines)
# - futex_hash_bucket: Wait queue hash table
# - get_futex_key(): Compute futex key from userspace address
# - futex_q: Per-waiter queue entry structure
# - hash_futex(): Map key to bucket
# - futex_cmpxchg_release(): Atomic operations on user memory
 
## waitwake.c (~500 lines)
# - futex_wait(): The FUTEX_WAIT implementation
# - futex_wake(): The FUTEX_WAKE implementation
# - futex_wait_queue_me(): Add to queue and sleep
# - futex_wake_mark(): Mark waiter for waking
 
## requeue.c (~700 lines)
# - futex_requeue(): Move waiters between futexes
# - futex_wake_op(): Compound wake operation
# - requeue_pi(): Priority inheritance requeue
 
## pi.c (~800 lines)
# - futex_lock_pi(): Priority inheritance lock acquire
# - futex_unlock_pi(): Priority inheritance unlock
# - fixup_pi_state_owner(): Handle PI state transfers
# - rt_mutex integration: Uses kernel RT mutexes internally

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
101
102
103
104
105
106
107
108
109

/*
 * System call entry point for futex
 * Source: kernel/futex/syscalls.c
 * 
 * This is called when userspace executes syscall(SYS_futex, ...)
 */
 
SYSCALL_DEFINE6(futex, u32 __user *, uaddr, int, op, u32, val,
                const struct __kernel_timespec __user *, utime,
                u32 __user *, uaddr2, u32, val3)
{
    int ret, cmd = op & FUTEX_CMD_MASK;
    ktime_t t, *tp = NULL;
    struct timespec64 ts;
    
    /*
     * STEP 1: Handle timeout conversion
     * 
     * For wait operations, convert userspace timespec to kernel ktime.
     * Different operations interpret the timeout differently:
     * - FUTEX_WAIT: relative timeout
     * - FUTEX_WAIT_BITSET: absolute timeout
     * - FUTEX_LOCK_PI: absolute timeout
     */
    if (utime && (cmd == FUTEX_WAIT || cmd == FUTEX_LOCK_PI ||
                  cmd == FUTEX_WAIT_BITSET ||
                  cmd == FUTEX_WAIT_REQUEUE_PI)) {
        if (get_timespec64(&ts, utime))
            return -EFAULT;
        if (!timespec64_valid(&ts))
            return -EINVAL;
        
        t = timespec64_to_ktime(ts);
        if (cmd == FUTEX_WAIT)
            t = ktime_add_safe(ktime_get(), t);  // Relative -> absolute
        tp = &t;
    }
    
    /*
     * STEP 2: Dispatch to operation-specific handler
     */
    return do_futex(uaddr, op, val, tp, uaddr2, (unsigned long)utime, val3);
}
 
/*
 * Main futex dispatch function
 */
long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout,
              u32 __user *uaddr2, u32 val2, u32 val3)
{
    int cmd = op & FUTEX_CMD_MASK;
    unsigned int flags = 0;
    
    /*
     * STEP 3: Parse flags
     */
    if (!(op & FUTEX_PRIVATE_FLAG))
        flags |= FLAGS_SHARED;
    
    if (op & FUTEX_CLOCK_REALTIME) {
        flags |= FLAGS_CLOCKRT;
        if (cmd != FUTEX_WAIT_BITSET && cmd != FUTEX_WAIT_REQUEUE_PI &&
            cmd != FUTEX_LOCK_PI)
            return -ENOSYS;
    }
    
    /*
     * STEP 4: Dispatch based on command
     */
    switch (cmd) {
    case FUTEX_WAIT:
        return futex_wait(uaddr, flags, val, timeout, FUTEX_BITSET_MATCH_ANY);
        
    case FUTEX_WAIT_BITSET:
        return futex_wait(uaddr, flags, val, timeout, val3);
        
    case FUTEX_WAKE:
        return futex_wake(uaddr, flags, val, FUTEX_BITSET_MATCH_ANY);
        
    case FUTEX_WAKE_BITSET:
        return futex_wake(uaddr, flags, val, val3);
        
    case FUTEX_REQUEUE:
        return futex_requeue(uaddr, flags, uaddr2, val, val2, NULL, 0);
        
    case FUTEX_CMP_REQUEUE:
        return futex_requeue(uaddr, flags, uaddr2, val, val2, &val3, 0);
        
    case FUTEX_WAKE_OP:
        return futex_wake_op(uaddr, flags, uaddr2, val, val2, val3);
        
    case FUTEX_LOCK_PI:
        return futex_lock_pi(uaddr, flags, timeout, 0);
        
    case FUTEX_UNLOCK_PI:
        return futex_unlock_pi(uaddr, flags);
        
    case FUTEX_TRYLOCK_PI:
        return futex_lock_pi(uaddr, flags, NULL, 1);
        
    case FUTEX_WAIT_REQUEUE_PI:
        return futex_wait_requeue_pi(uaddr, flags, val, timeout, val3,
                                      uaddr2);
    case FUTEX_CMP_REQUEUE_PI:
        return futex_requeue(uaddr, flags, uaddr2, val, val2, &val3, 1);
    }
    
    return -ENOSYS;  // Unknown 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
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

/*
 * Priority Inheritance Futex Implementation
 * Source: kernel/futex/pi.c
 * 
 * PI futexes differ from regular futexes:
 * 1. The futex word contains the TID of the owner (not just 0/1/2)
 * 2. The kernel tracks ownership and adjusts priorities
 * 3. Uses the kernel's RT mutex infrastructure internally
 */
 
/*
 * PI futex word format (32 bits):
 * 
 * Bits 0-29: Owner's TID (thread ID)
 * Bit 30:    FUTEX_WAITERS - there are waiters
 * Bit 31:    FUTEX_OWNER_DIED - owner died while holding
 */
#define FUTEX_TID_MASK      0x3fffffff
#define FUTEX_WAITERS       0x40000000
#define FUTEX_OWNER_DIED    0x80000000
 
/*
 * PI state structure - tracks priority inheritance chain
 */
struct futex_pi_state {
    struct list_head list;          // All PI states for this task
    struct rt_mutex_base pi_mutex;  // The RT mutex for PI tracking
    struct task_struct *owner;      // Current owner
    refcount_t refcount;            // Reference count
    union futex_key key;            // Which futex this is for
};
 
/*
 * Acquiring a PI futex
 * 
 * Much more complex than regular futex due to priority tracking
 */
int futex_lock_pi(u32 __user *uaddr, unsigned int flags,
                   ktime_t *time, int trylock)
{
    struct futex_hash_bucket *hb;
    struct futex_q q = futex_q_init;
    int ret;
    
    /*
     * STEP 1: Get futex key
     */
    ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &q.key);
    if (ret)
        return ret;
    
    /*
     * STEP 2: Fast path - try to acquire uncontended
     * 
     * If futex word is 0, try to set it to our TID
     */
    ret = futex_lock_pi_atomic(uaddr, &q, NULL, current->pid, NULL);
    if (ret == 1) {
        return 0;  // Got it! Fast path success.
    }
    if (ret < 0) {
        return ret;  // Error
    }
    
    /*
     * STEP 3: Slow path - need to wait with PI
     * 
     * ret == 0 means someone else holds it
     */
    hb = hash_futex(&q.key);
    spin_lock(&hb->lock);
    
    /*
     * STEP 4: Set up PI state
     * 
     * Find or create the futex_pi_state for this futex.
     * Attach ourselves to the RT mutex wait chain.
     */
    ret = futex_wait_setup(uaddr, val, flags, &q, &hb);
    if (ret)
        goto out_unlock;
    
    ret = attach_to_pi_state(uaddr, &q, current);
    if (ret)
        goto out_unlock;
    
    /*
     * STEP 5: Now the interesting part - priority inheritance
     * 
     * The RT mutex code will:
     * 1. Add us to the RT mutex wait list
     * 2. Boost owner's priority to ours if we're higher
     * 3. Potentially chain-boost if owner is also blocked
     */
    ret = rt_mutex_wait_proxy_lock(&q.pi_state->pi_mutex, time,
                                    &rt_waiter);
    
    /*
     * STEP 6: Woken up - we now own the lock
     * 
     * The RT mutex code transferred ownership to us.
     * Update the userspace futex word to our TID.
     */
    fixup_owner(uaddr, &q, current);
    
out_unlock:
    spin_unlock(&hb->lock);
    return ret;
}
 
/*
 * Priority inheritance chain example:
 * 
 * Task A (priority 99, highest) wants lock held by B
 * Task B (priority 50) wants lock held by C  
 * Task C (priority 10, lowest) holds both locks
 * 
 * Without PI:
 *   C runs at priority 10, gets preempted by everything
 *   A waits potentially forever
 * 
 * With PI:
 *   C inherits A's priority 99 through the chain
 *   C runs at priority 99, completes quickly
 *   B inherits A's priority 99 (or its own 50, whichever higher)
 *   A finally runs
 */

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

/*
 * Robust Futex Mechanism
 * 
 * The key idea: each thread maintains a list of held robust locks.
 * When the thread exits (normally or via crash), the kernel walks
 * this list and marks each lock as FUTEX_OWNER_DIED.
 */
 
/*
 * Registering the robust list with the kernel
 * 
 * Called early in thread startup (glibc does this automatically
 * for PTHREAD_MUTEX_ROBUST mutexes).
 */
#include <linux/futex.h>
 
struct robust_list_head {
    struct robust_list *list;          // Head of circular list
    long futex_offset;                 // Offset to futex word in struct
    struct robust_list *list_op_pending;  // Currently being acquired/released
};
 
// System call to register the robust list
long set_robust_list(struct robust_list_head *head, size_t len);
 
/*
 * How userspace tracks robust locks
 * 
 * Each mutex structure has a 'list' member that links it into
 * the thread's robust list. When acquiring, add to list.
 * When releasing, remove from list.
 */
 
struct robust_mutex {
    struct robust_list list;    // Link in robust list
    uint32_t futex;             // The actual futex word
    // ... other fields
};
 
void acquire_robust_mutex(struct robust_mutex *m) {
    // Add to pending (in case we crash during acquire)
    __robust_list_head.list_op_pending = &m->list;
    
    // Acquire the lock (PI or regular futex)
    // ... futex operations ...
    
    // Move from pending to held list
    add_to_robust_list(&m->list);
    __robust_list_head.list_op_pending = NULL;
}
 
/*
 * Kernel side: what happens on thread exit
 * Source: kernel/exit.c -> exit_robust_list()
 */
void exit_robust_list(struct task_struct *curr)
{
    struct robust_list_head __user *head;
    struct robust_list __user *entry, *next;
    unsigned int limit = ROBUST_LIST_LIMIT;
    
    // Get the robust list head for this task
    head = curr->robust_list;
    if (!head)
        return;  // No robust list registered
    
    /*
     * Handle pending operation first
     * 
     * If we crashed during acquire/release, handle that entry specially
     */
    if (head->list_op_pending) {
        handle_futex_death((void *)head->list_op_pending + head->futex_offset,
                           curr);
    }
    
    /*
     * Walk the robust list and mark each lock as OWNER_DIED
     */
    entry = head->list;
    while (entry != (struct robust_list __user *)head && --limit) {
        u32 __user *uaddr = (u32 *)((char *)entry + head->futex_offset);
        
        handle_futex_death(uaddr, curr);
        
        // Follow the list
        if (get_user(next, &entry->next))
            break;
        entry = next;
    }
}
 
/*
 * Marking a lock as owner-died
 */
static void handle_futex_death(u32 __user *uaddr, struct task_struct *curr)
{
    u32 uval, nval;
    
    // Read current value
    if (get_user(uval, uaddr))
        return;
    
    // Only if we actually owned it
    if ((uval & FUTEX_TID_MASK) != curr->pid)
        return;
    
    // Atomically set FUTEX_OWNER_DIED, keeping WAITERS bit
    do {
        nval = (uval & FUTEX_WAITERS) | FUTEX_OWNER_DIED;
    } while (cmpxchg_futex_value_locked(uaddr, uval, nval) != uval);
    
    // Wake any waiters so they can recover
    if (uval & FUTEX_WAITERS)
        futex_wake(uaddr, FLAGS_SHARED, 1, FUTEX_BITSET_MATCH_ANY);
}
 
/*
 * Userspace recovery
 * 
 * When a waiter wakes and sees FUTEX_OWNER_DIED, it can:
 * 1. Take ownership of the lock
 * 2. Run recovery code (check data consistency)
 * 3. Clear FUTEX_OWNER_DIED and FUTEX_WAITERS
 * 4. Continue with the acquired lock
 * 
 * pthread_mutex_consistent() performs this recovery.
 */

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

/*
 * Futex2 Proposals (as of 2023, not yet merged)
 * 
 * The current futex syscall has limitations that futex2 aims to address:
 */
 
/*
 * LIMITATION 1: Fixed 32-bit futex word
 * 
 * Current: Futex word is always uint32_t
 * Problem: 64-bit atomic operations becoming common
 * 
 * Proposed: Variable-size futexes (8, 16, 32, 64-bit)
 */
struct futex_waitv {
    uint64_t val;           // Expected value (any size)
    uint64_t uaddr;         // Address of futex
    uint32_t flags;         // FUTEX2_SIZE_U8/U16/U32/U64, PRIVATE, etc.
    uint32_t __reserved;
};
 
/*
 * LIMITATION 2: Can only wait on one futex at a time
 * 
 * Current: One FUTEX_WAIT per syscall
 * Problem: Polling multiple futexes requires threads or epoll hacks
 * 
 * Proposed: Wait on multiple futexes simultaneously
 */
long futex_waitv(struct futex_waitv *waiters, unsigned int nr_futexes,
                  unsigned int flags, struct timespec *timeout);
 
/*
 * Usage example: Wait for either of two events
 */
struct futex_waitv events[2] = {
    { .uaddr = &event1, .val = 0, .flags = FUTEX2_SIZE_U32 | FUTEX2_PRIVATE },
    { .uaddr = &event2, .val = 0, .flags = FUTEX2_SIZE_U32 | FUTEX2_PRIVATE },
};
 
ret = futex_waitv(events, 2, 0, &timeout);
// Returns index of futex that woke us, or -1 on timeout
 
/*
 * LIMITATION 3: Timeout handling quirks
 * 
 * Current: Inconsistent timeout semantics across operations
 * Proposed: Unified, explicit timeout handling with newer interfaces
 */
 
/*
 * STATUS: As of 2023, futex_waitv (multi-wait) has been partially
 * accepted for enabling Windows gaming via Wine/Proton (needs waiting
 * on multiple synchronization objects). Full futex2 is still evolving.
 */

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

/*
 * How glibc NPTL uses futex
 * Source: glibc/nptl/*.c
 */
 
/*
 * pthread_mutex_t structure (simplified, glibc 2.34+)
 */
typedef struct {
    int __lock;                    // Futex word
    unsigned int __count;          // Recursive lock count
    int __owner;                   // Owner TID (for error checking)
    unsigned int __nusers;         // Debugging: number of users
    int __kind;                    // Mutex type (normal, recursive, etc.)
    // ... additional fields for robust, PI, etc.
} pthread_mutex_t;
 
/*
 * pthread_mutex_lock implementation (simplified)
 */
int pthread_mutex_lock(pthread_mutex_t *mutex)
{
    int type = mutex->__kind & PTHREAD_MUTEX_KIND_MASK;
    
    switch (type) {
    case PTHREAD_MUTEX_NORMAL:
        return lll_lock(&mutex->__lock);  // Direct futex path
        
    case PTHREAD_MUTEX_RECURSIVE:
        if (mutex->__owner == pthread_self()) {
            mutex->__count++;
            return 0;  // Already hold it, just increment count
        }
        lll_lock(&mutex->__lock);
        mutex->__owner = pthread_self();
        mutex->__count = 1;
        return 0;
        
    case PTHREAD_MUTEX_ERRORCHECK:
        if (mutex->__owner == pthread_self())
            return EDEADLK;  // Error: would deadlock
        lll_lock(&mutex->__lock);
        mutex->__owner = pthread_self();
        return 0;
        
    // ... PI and robust variants
    }
}
 
/*
 * The low-level lock (lll) functions in NPTL
 * These directly use futex operations
 */
 
// Lock acquire (fast path inline)
static inline void lll_lock(int *futex)
{
    if (__glibc_likely(atomic_compare_exchange_weak(futex, 0, 1)))
        return;  // Fast path: acquired
    
    lll_lock_wait(futex);  // Slow path
}
 
// Slow path: futex wait loop
void lll_lock_wait(int *futex)
{
    // Set to contended state
    if (atomic_exchange(futex, 2) == 2)
        goto do_futex;  // Someone else was already waiting
    
    // Try once more after setting contended
    while (atomic_exchange(futex, 2) != 0) {
    do_futex:
        // Actually sleep via futex
        syscall(SYS_futex, futex, 
                FUTEX_WAIT | FUTEX_PRIVATE_FLAG, 2, NULL);
    }
}
 
/*
 * pthread_cond_t and condition variable implementation
 * Uses FUTEX_CMP_REQUEUE for efficient signaling
 */
 
int pthread_cond_signal(pthread_cond_t *cond)
{
    atomic_fetch_add(&cond->__wrefs, 8);  // Increment sequence
    
    // Requeue: wake 1, requeue rest to mutex
    syscall(SYS_futex, &cond->__wseq, FUTEX_CMP_REQUEUE | PRIVATE,
            1,                    // Wake 1 thread
            INT_MAX,              // Requeue all others
            &cond->__mutex->__lock,  // To the mutex
            cond->__wseq);        // Expected sequence
    
    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
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

#!/bin/bash
# Debugging futex issues
 
# ============================================
# TECHNIQUE 1: Find threads blocked on futex
# ============================================
 
# List all threads in your process
ps -eLf | grep my_application
 
# Check what each thread is doing
cat /proc/<pid>/task/<tid>/syscall
# Output like: 202 0x7f1234 0x80 0x2 ...
# 202 = SYS_futex, following are arguments
 
# More readable with strace
strace -f -e futex -p <pid>
# Shows all futex calls in real-time
 
# ============================================
# TECHNIQUE 2: GDB for lock state inspection
# ============================================
 
# Attach to running process
gdb -p <pid>
 
# Find mutex state
(gdb) print *my_mutex
# Shows __lock field value:
# 0 = unlocked
# 1 = locked, no waiters
# 2 = locked, has waiters
 
# Find who holds a PI mutex
(gdb) print my_pi_mutex.__owner
# Shows TID of owner
 
# Get backtrace of all threads
(gdb) thread apply all bt
 
# Find threads in futex_wait
(gdb) thread apply all bt | grep futex_wait
 
# ============================================
# TECHNIQUE 3: bpftrace for futex timing
# ============================================
 
# Find long futex waits
sudo bpftrace -e '
tracepoint:syscalls:sys_enter_futex /args->op & 0x7f == 0/ {
    @start[tid] = nsecs;
}
tracepoint:syscalls:sys_exit_futex /@start[tid] && 
                                    nsecs - @start[tid] > 1000000000/ {
    printf("Thread %d waited %d ms in futex
", 
           tid, (nsecs - @start[tid]) / 1000000);
    @[ustack] = count();
    delete(@start[tid]);
}'
 
# ============================================
# TECHNIQUE 4: lockdep for deadlock detection
# ============================================
 
# Enable CONFIG_LOCKDEP in kernel (debug builds)
# Kernel will detect lock order violations
 
# Runtime check for circular dependencies
echo 1 > /proc/sys/kernel/softlockup_panic
 
# View lock statistics (if enabled)
cat /proc/lockdep_stats
 
# ============================================
# TECHNIQUE 5: Valgrind helgrind/drd
# ============================================
 
# Detect data races and lock misuse
valgrind --tool=helgrind ./my_application
 
# DRD is similar but different detection strategy
valgrind --tool=drd ./my_application
 
# Common issues detected:
# - Lock order inconsistency (potential deadlock)
# - Unlocking unheld lock
# - Data race: concurrent access without synchronization