]>
Commit | Line | Data |
---|---|---|
04454e1e FG |
1 | use crate::sync::atomic::{ |
2 | AtomicU32, | |
3 | Ordering::{Acquire, Relaxed, Release}, | |
4 | }; | |
5 | use crate::sys::futex::{futex_wait, futex_wake, futex_wake_all}; | |
6 | use crate::time::Duration; | |
7 | ||
8 | pub type MovableMutex = Mutex; | |
9 | pub type MovableCondvar = Condvar; | |
10 | ||
11 | pub struct Mutex { | |
12 | /// 0: unlocked | |
13 | /// 1: locked, no other threads waiting | |
14 | /// 2: locked, and other threads waiting (contended) | |
15 | futex: AtomicU32, | |
16 | } | |
17 | ||
18 | impl Mutex { | |
19 | #[inline] | |
20 | pub const fn new() -> Self { | |
21 | Self { futex: AtomicU32::new(0) } | |
22 | } | |
23 | ||
24 | #[inline] | |
25 | pub unsafe fn init(&mut self) {} | |
26 | ||
04454e1e FG |
27 | #[inline] |
28 | pub unsafe fn try_lock(&self) -> bool { | |
29 | self.futex.compare_exchange(0, 1, Acquire, Relaxed).is_ok() | |
30 | } | |
31 | ||
32 | #[inline] | |
33 | pub unsafe fn lock(&self) { | |
34 | if self.futex.compare_exchange(0, 1, Acquire, Relaxed).is_err() { | |
35 | self.lock_contended(); | |
36 | } | |
37 | } | |
38 | ||
39 | #[cold] | |
40 | fn lock_contended(&self) { | |
41 | // Spin first to speed things up if the lock is released quickly. | |
42 | let mut state = self.spin(); | |
43 | ||
44 | // If it's unlocked now, attempt to take the lock | |
45 | // without marking it as contended. | |
46 | if state == 0 { | |
47 | match self.futex.compare_exchange(0, 1, Acquire, Relaxed) { | |
48 | Ok(_) => return, // Locked! | |
49 | Err(s) => state = s, | |
50 | } | |
51 | } | |
52 | ||
53 | loop { | |
54 | // Put the lock in contended state. | |
55 | // We avoid an unnecessary write if it as already set to 2, | |
56 | // to be friendlier for the caches. | |
57 | if state != 2 && self.futex.swap(2, Acquire) == 0 { | |
58 | // We changed it from 0 to 2, so we just succesfully locked it. | |
59 | return; | |
60 | } | |
61 | ||
62 | // Wait for the futex to change state, assuming it is still 2. | |
63 | futex_wait(&self.futex, 2, None); | |
64 | ||
65 | // Spin again after waking up. | |
66 | state = self.spin(); | |
67 | } | |
68 | } | |
69 | ||
70 | fn spin(&self) -> u32 { | |
71 | let mut spin = 100; | |
72 | loop { | |
73 | // We only use `load` (and not `swap` or `compare_exchange`) | |
74 | // while spinning, to be easier on the caches. | |
75 | let state = self.futex.load(Relaxed); | |
76 | ||
77 | // We stop spinning when the mutex is unlocked (0), | |
78 | // but also when it's contended (2). | |
79 | if state != 1 || spin == 0 { | |
80 | return state; | |
81 | } | |
82 | ||
83 | crate::hint::spin_loop(); | |
84 | spin -= 1; | |
85 | } | |
86 | } | |
87 | ||
88 | #[inline] | |
89 | pub unsafe fn unlock(&self) { | |
90 | if self.futex.swap(0, Release) == 2 { | |
91 | // We only wake up one thread. When that thread locks the mutex, it | |
92 | // will mark the mutex as contended (2) (see lock_contended above), | |
93 | // which makes sure that any other waiting threads will also be | |
94 | // woken up eventually. | |
95 | self.wake(); | |
96 | } | |
97 | } | |
98 | ||
99 | #[cold] | |
100 | fn wake(&self) { | |
101 | futex_wake(&self.futex); | |
102 | } | |
103 | } | |
104 | ||
105 | pub struct Condvar { | |
106 | // The value of this atomic is simply incremented on every notification. | |
107 | // This is used by `.wait()` to not miss any notifications after | |
108 | // unlocking the mutex and before waiting for notifications. | |
109 | futex: AtomicU32, | |
110 | } | |
111 | ||
112 | impl Condvar { | |
113 | #[inline] | |
114 | pub const fn new() -> Self { | |
115 | Self { futex: AtomicU32::new(0) } | |
116 | } | |
117 | ||
04454e1e FG |
118 | // All the memory orderings here are `Relaxed`, |
119 | // because synchronization is done by unlocking and locking the mutex. | |
120 | ||
121 | pub unsafe fn notify_one(&self) { | |
122 | self.futex.fetch_add(1, Relaxed); | |
123 | futex_wake(&self.futex); | |
124 | } | |
125 | ||
126 | pub unsafe fn notify_all(&self) { | |
127 | self.futex.fetch_add(1, Relaxed); | |
128 | futex_wake_all(&self.futex); | |
129 | } | |
130 | ||
131 | pub unsafe fn wait(&self, mutex: &Mutex) { | |
132 | self.wait_optional_timeout(mutex, None); | |
133 | } | |
134 | ||
135 | pub unsafe fn wait_timeout(&self, mutex: &Mutex, timeout: Duration) -> bool { | |
136 | self.wait_optional_timeout(mutex, Some(timeout)) | |
137 | } | |
138 | ||
139 | unsafe fn wait_optional_timeout(&self, mutex: &Mutex, timeout: Option<Duration>) -> bool { | |
140 | // Examine the notification counter _before_ we unlock the mutex. | |
141 | let futex_value = self.futex.load(Relaxed); | |
142 | ||
143 | // Unlock the mutex before going to sleep. | |
144 | mutex.unlock(); | |
145 | ||
146 | // Wait, but only if there hasn't been any | |
147 | // notification since we unlocked the mutex. | |
148 | let r = futex_wait(&self.futex, futex_value, timeout); | |
149 | ||
150 | // Lock the mutex again. | |
151 | mutex.lock(); | |
152 | ||
153 | r | |
154 | } | |
155 | } |