nx_mutex.nx source
↩ module page · 162 lines · 5439 B
1// nx_mutex.nx -- futex-based mutex (FUTEX_WAIT / FUTEX_WAKE).
2//
3// Companion to nx_atom (atomic primitives). When SMP arrives,
4// mutual exclusion needs more than a spinlock -- spinning under
5// contention burns CPU and starves the holder. Futex (fast
6// userspace mutex) lets contended waiters sleep in the kernel
7// until the lock is released.
8//
9// State word:
10// 0 = unlocked
11// 1 = locked, no waiters
12// 2 = locked, possibly contended (waiters parked in kernel)
13//
14// Lock fast path: CAS(0, 1).
15// Lock slow path: spin a few times, then transition to 2 + futex_wait.
16// Unlock fast path: store 0; if previous == 2, futex_wake one.
17//
18// Today the sim is single-threaded, so we just track lock/unlock
19// state without actual blocking; the API matches the SMP path so
20// callers don't need to change later.
21//
22// Linux RV64 futex syscall: 98.
23//
24// Pairs with nx_atom for the CAS primitive (which is currently
25// non-atomic since SMP isn't on); will be a no-source-change
26// upgrade once nx_atom emits real LR/SC sequences.
27
28// nx_safety_envelope:
29// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
30// sil_target: SIL1
31// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
32// verdict: NOT_YET_EVALUATED
33
34import "nx_syscalls.nx"
35import "nx_atom.nx"
36
37const NX_SYS_FUTEX: i64 = 98
38
39// FUTEX op codes
40const NX_FUTEX_WAIT: i64 = 0
41const NX_FUTEX_WAKE: i64 = 1
42const NX_FUTEX_PRIVATE_FLAG: i64 = 128
43
44const NX_MUTEX_UNLOCKED: i64 = 0
45const NX_MUTEX_LOCKED: i64 = 1
46const NX_MUTEX_CONTENDED: i64 = 2
47
48const NX_MUTEX_SPIN_TRIES: i64 = 100
49
50struct NxMutex {
51 state: i64,
52}
53
54const NX_MUTEX_BYTES: i64 = 8
55
56func nx_mutex_new() -> *NxMutex {
57 let raw: *u8 = sys_mmap(NX_MUTEX_BYTES)
58 let m: *NxMutex = raw as *NxMutex
59 m.state = NX_MUTEX_UNLOCKED
60 return m
61}
62
63// Real atomic CAS on m.state via the __atomic_cas_i64 builtin.
64// Returns 1 on swap, 0 on miss. ACQUIRE ordering on the swap so any
65// reads inside the critical section observe the prior holder's writes.
66func nx_mutex_cas(m: *NxMutex, expect: i64, new_val: i64) -> i64 {
67 let state_addr: *i64 = (m as i64) as *i64
68 return __atomic_cas_i64(state_addr, expect, new_val, NX_MO_ACQUIRE)
69}
70
71// futex_wait(addr, expected, timeout). Returns 0 on wakeup or
72// -EAGAIN if state already changed. We pass timeout=0 (NULL) for
73// indefinite wait.
74func nx_mutex_futex_wait(m: *NxMutex, expected: i64) -> i64 {
75 let op: i64 = NX_FUTEX_WAIT | NX_FUTEX_PRIVATE_FLAG
76 return __syscall(NX_SYS_FUTEX, m as i64, op, expected, 0, 0, 0)
77}
78
79// futex_wake(addr, n). Wake up to n waiters.
80func nx_mutex_futex_wake(m: *NxMutex, n: i64) -> i64 {
81 let op: i64 = NX_FUTEX_WAKE | NX_FUTEX_PRIVATE_FLAG
82 return __syscall(NX_SYS_FUTEX, m as i64, op, n, 0, 0, 0)
83}
84
85// Lock. Fast path on uncontended, spin then park on contended.
86func nx_mutex_lock(m: *NxMutex) -> i64 {
87 // Fast path: CAS unlocked -> locked.
88 if nx_mutex_cas(m, NX_MUTEX_UNLOCKED, NX_MUTEX_LOCKED) == 1 {
89 return 0
90 }
91
92 // Slow path: spin a few times.
93 var i: i64 = 0
94 while i < NX_MUTEX_SPIN_TRIES {
95 if nx_mutex_cas(m, NX_MUTEX_UNLOCKED, NX_MUTEX_LOCKED) == 1 {
96 return 0
97 }
98 i = i + 1
99 }
100
101 // Park.
102 var done: i64 = 0
103 while done == 0 {
104 // Mark contended so the unlocker knows to wake us.
105 if nx_mutex_cas(m, NX_MUTEX_LOCKED, NX_MUTEX_CONTENDED) == 1 {
106 // We marked it; wait for state to drop from CONTENDED.
107 nx_mutex_futex_wait(m, NX_MUTEX_CONTENDED)
108 }
109 // Try again to grab the lock.
110 if nx_mutex_cas(m, NX_MUTEX_UNLOCKED, NX_MUTEX_CONTENDED) == 1 {
111 done = 1
112 } else {
113 if nx_mutex_cas(m, NX_MUTEX_UNLOCKED, NX_MUTEX_LOCKED) == 1 {
114 done = 1
115 }
116 }
117 }
118 return 0
119}
120
121// Try-lock: non-blocking; returns 1 on success, 0 if already held.
122func nx_mutex_try_lock(m: *NxMutex) -> i64 {
123 return nx_mutex_cas(m, NX_MUTEX_UNLOCKED, NX_MUTEX_LOCKED)
124}
125
126// Unlock. Atomic-store the unlocked value; if previous state was
127// CONTENDED, wake one waiter via futex. RELEASE ordering ensures
128// writes inside the critical section are visible to next holder.
129func nx_mutex_unlock(m: *NxMutex) -> i64 {
130 let state_addr: *i64 = (m as i64) as *i64
131 let prev: i64 = __atomic_load_i64(state_addr, NX_MO_RELAXED)
132 __atomic_store_i64(state_addr, NX_MUTEX_UNLOCKED, NX_MO_RELEASE)
133 if prev == NX_MUTEX_CONTENDED {
134 nx_mutex_futex_wake(m, 1)
135 }
136 return 0
137}
138
139// ---- self-test ---------------------------------------------------
140
141func main() -> i64 {
142 let m: *NxMutex = nx_mutex_new()
143 if m.state != NX_MUTEX_UNLOCKED { return __syscall(93, 1, 0, 0, 0, 0, 0) }
144
145 // Fast-path lock.
146 nx_mutex_lock(m)
147 if m.state != NX_MUTEX_LOCKED { return __syscall(93, 2, 0, 0, 0, 0, 0) }
148
149 // try_lock on already-held should fail.
150 if nx_mutex_try_lock(m) != 0 { return __syscall(93, 3, 0, 0, 0, 0, 0) }
151
152 // Unlock returns to UNLOCKED and (since no waiter) skips wake.
153 nx_mutex_unlock(m)
154 if m.state != NX_MUTEX_UNLOCKED { return __syscall(93, 4, 0, 0, 0, 0, 0) }
155
156 // try_lock + unlock cycle.
157 if nx_mutex_try_lock(m) != 1 { return __syscall(93, 5, 0, 0, 0, 0, 0) }
158 nx_mutex_unlock(m)
159 if m.state != NX_MUTEX_UNLOCKED { return __syscall(93, 6, 0, 0, 0, 0, 0) }
160
161 return 0
162}