1#include <sch/sched.h>
2#include <stddef.h>
3#include <sync/mutex.h>
4#include <sync/rcu.h>
5#include <sync/turnstile.h>
6#include <thread/thread.h>
7#include <time/spin_sleep.h>
8
9#include "console/printf.h"
10#include "lock_general_internal.h"
11#include "mutex_internal.h"
12
13#ifdef DEBUG_LOCK_CHK
14
15#include "lock_chk_internal.h"
16
17struct mutex_chk_acquire_state {
18 struct lock_chk_acquire_request request;
19 struct lock_chk_acquire_token token;
20};
21
22struct mutex_chk_release_state {
23 struct lock_chk_release_request request;
24 struct lock_chk_release_token token;
25};
26
27static void mutex_chk_before_lock(struct mutex_chk_acquire_state *state,
28 struct mutex *mutex, uint8_t subclass,
29 const struct lock_chk_site *site) {
30 lock_chk_note_lock_use(&mutex->chk, /*manages_irql=*/false,
31 /*raw_operation=*/false);
32 /* HACK: We should really set .instance at initialization, we just
33 * do it here because I don't want to do all of that work */
34 mutex->chk.instance = mutex;
35 mutex->chk.type = LOCK_CHK_TYPE_MUTEX;
36 state->request = lock_chk_acquire_request_make(
37 &mutex->chk, site, LOCK_CHK_MODE_EXCLUSIVE, LOCK_CHK_WAIT_BLOCKING,
38 subclass, false, false);
39 lock_chk_before_acquire(&state->token, &state->request);
40}
41
42static void mutex_chk_locked(struct mutex_chk_acquire_state *state) {
43 lock_chk_acquired(&state->token);
44}
45
46static void mutex_chk_before_unlock(struct mutex_chk_release_state *state,
47 struct mutex *mutex,
48 const struct lock_chk_site *site) {
49 mutex->chk.instance = mutex;
50 mutex->chk.type = LOCK_CHK_TYPE_MUTEX;
51 state->request = lock_chk_release_request_make(&mutex->chk, site,
52 LOCK_CHK_MODE_EXCLUSIVE);
53 lock_chk_before_release(&state->token, &state->request);
54}
55
56static void mutex_chk_unlocked(struct mutex_chk_release_state *state) {
57 lock_chk_released(&state->token);
58}
59
60static void mutex_chk_state_init(struct mutex *mtx,
61 const struct lock_chk_class *class,
62 enum lock_chk_flags flags) {
63 kassert((flags & ~LOCK_CHKD_FULL) == 0);
64 kassert(flags == LOCK_UNCHKD || class != NULL);
65 mtx->chk.flags = flags;
66 mtx->chk.initialized = true;
67 atomic_store_explicit(&mtx->chk.used, false, memory_order_relaxed);
68 lock_chk_map_runtime_init(&mtx->chk.map, class);
69}
70
71void mutex_set_chk_flags(struct mutex *mtx, enum lock_chk_flags flags) {
72 kassert(mtx->chk.initialized);
73 kassert(!mutex_locked(mtx));
74 kassert(!atomic_load_explicit(&mtx->chk.used, memory_order_relaxed));
75 kassert((flags & ~LOCK_CHKD_FULL) == 0);
76 mtx->chk.flags = flags;
77}
78
79void mutex_reinit_chk(struct mutex *mtx, const struct lock_chk_class *class,
80 enum lock_chk_flags flags) {
81 kassert(mtx->chk.initialized);
82 kassert(!mutex_locked(mtx));
83 mutex_init_chk_internal(mtx, class, flags);
84}
85
86#else /* !defined(DEBUG_LOCK_CHK) */
87
88struct mutex_chk_acquire_state {
89 bool unused;
90};
91
92struct mutex_chk_release_state {
93 bool unused;
94};
95
96static void mutex_chk_before_lock(struct mutex_chk_acquire_state *state,
97 struct mutex *mutex, unsigned int subclass,
98 const struct lock_chk_site *site) {
99 unused(state, mutex, subclass, site);
100}
101
102static void mutex_chk_locked(struct mutex_chk_acquire_state *state) {
103 unused(state);
104}
105
106static void mutex_chk_before_unlock(struct mutex_chk_release_state *state,
107 struct mutex *mutex,
108 const struct lock_chk_site *site) {
109 unused(state, mutex, site);
110}
111
112static void mutex_chk_unlocked(struct mutex_chk_release_state *state) {
113 unused(state);
114}
115
116static void mutex_chk_state_init(struct mutex *mtx,
117 const struct lock_chk_class *class,
118 enum lock_chk_flags flags) {
119 unused(mtx, class, flags);
120}
121
122void mutex_set_chk_flags(struct mutex *mtx, enum lock_chk_flags flags) {
123 unused(mtx, flags);
124}
125
126void mutex_reinit_chk(struct mutex *mtx, const struct lock_chk_class *class,
127 enum lock_chk_flags flags) {
128 mutex_init_chk_internal(mtx, class, flags);
129}
130
131#endif /* DEBUG_LOCK_CHK */
132
133void mutex_init_chk_internal(struct mutex *mtx,
134 const struct lock_chk_class *class,
135 enum lock_chk_flags flags) {
136 atomic_store_explicit(&mtx->lock_word, 0, memory_order_relaxed);
137 mutex_chk_state_init(mtx, class, flags);
138}
139
140struct thread *mutex_get_owner(struct mutex *mtx) {
141 return (struct thread *) (MUTEX_READ_LOCK_WORD(mtx) & (~MUTEX_META_BITS));
142}
143
144static struct thread *mutex_get_owner_ref(struct mutex *mutex) {
145 struct thread *owner;
146
147 rcu_read_lock();
148 owner = mutex_get_owner(mtx: mutex);
149 if (owner && !thread_get_rcu(t: owner))
150 owner = NULL;
151 rcu_read_unlock();
152
153 return owner;
154}
155
156size_t mutex_lock_get_backoff(size_t current_backoff) {
157 if (!current_backoff)
158 return MUTEX_BACKOFF_DEFAULT;
159
160 if (current_backoff >= (MUTEX_BACKOFF_MAX >> MUTEX_BACKOFF_SHIFT))
161 return MUTEX_BACKOFF_MAX;
162
163 size_t new_backoff = current_backoff << MUTEX_BACKOFF_SHIFT;
164 return new_backoff > MUTEX_BACKOFF_MAX ? MUTEX_BACKOFF_MAX : new_backoff;
165}
166
167static bool mutex_owner_running(struct mutex *mutex) {
168 struct thread *owner = mutex_get_owner_ref(mutex);
169 if (!owner) /* no owner, can't possibly be running */
170 return false;
171
172 bool ret = thread_get_state(t: owner) == THREAD_STATE_RUNNING;
173 thread_put(t: owner);
174
175 return ret;
176}
177
178static void mutex_sanity_check() {
179 kassert(irq_not_in_interrupt());
180 kassert(irql_get() <= IRQL_APC_LEVEL);
181}
182
183void mutex_lock_subclass_internal(struct mutex *mutex, uint8_t subclass,
184 const struct lock_chk_site *site) {
185 kassert(subclass < LOCK_CHK_MAX_SUBCLASSES);
186 mutex_sanity_check();
187
188 struct mutex_chk_acquire_state chk_state;
189 mutex_chk_before_lock(state: &chk_state, mutex, subclass, site);
190
191 struct thread *current_thread = thread_get_current();
192
193 /* easy peasy nothing to do */
194 if (mutex_try_lock(mtx: mutex, self: current_thread)) {
195 mutex_chk_locked(state: &chk_state);
196 crash_unwind_enter_mutex(m: mutex);
197 return;
198 }
199
200 /* failed to spin_try_acquire... now we must do the funny business... */
201 struct thread *last_owner = mutex_get_owner(mtx: mutex);
202 struct thread *current_owner = last_owner;
203
204 /* we set a backoff to say how much we want to spin in between acquisition
205 * attempts. this is done to prevent cache thrashing from atomic RMWs */
206 size_t backoff = MUTEX_BACKOFF_DEFAULT;
207
208 /* how many times we have seen the lock owner change without ever getting
209 * a chance to acquire the lock ourselves. used to reset the backoff so that
210 * we don't wait too long on a lock... */
211 size_t owner_change_count = 0;
212
213 /* let's go gambling! */
214 while (true) {
215 lock_delay(backoff, MUTEX_BACKOFF_JITTER_PCT);
216
217 /* owner is gone, let's try and get the lock */
218 if (!(current_owner = mutex_get_owner(mtx: mutex))) {
219 if (mutex_try_lock(mtx: mutex, self: current_thread))
220 break; /* got it */
221
222 /* increase backoff, better luck next time */
223 backoff = mutex_lock_get_backoff(current_backoff: backoff);
224 owner_change_count++;
225 continue;
226 } else if (last_owner != current_owner) {
227 /* someone swapped out the owner thread */
228 last_owner = current_owner;
229 backoff = mutex_lock_get_backoff(current_backoff: backoff);
230 owner_change_count++;
231 }
232
233 /* reset these values so we can have a better chance
234 * at actually getting the lock, we've been dawdling for
235 * a while if we've reached this branch. */
236 if (owner_change_count >= global.core_count) {
237 backoff = MUTEX_BACKOFF_DEFAULT;
238 owner_change_count = 0;
239 }
240
241 /* keep trying to spin-acquire if the owner is still running */
242 if (mutex_owner_running(mutex))
243 continue;
244
245 /* owner is now no longer running, might be in a ready queue
246 * or something. regardless, this is turnstile time */
247 enum irql ts_lock_irql;
248 struct turnstile *ts = turnstile_lookup(obj: mutex, irql_out: &ts_lock_irql);
249
250 /* just kidding, the owner went back to running, we spin again :^) */
251 if (mutex_owner_running(mutex)) {
252 turnstile_unlock(obj: mutex, irql: ts_lock_irql);
253 continue;
254 }
255
256 /* owner unchanged, waiter bit still the same...
257 * time to do the slow path */
258 struct thread *owner = mutex_get_owner_ref(mutex);
259 if (owner == current_owner) {
260 /* Turnstile chain lock stabilizes the lock word until block()
261 * publishes the waiter, so we do not pin for the entire
262 * blocking period, since unlock clears ts->owner
263 * under this same chain before owner exits */
264 thread_put(t: owner);
265 turnstile_block(ts, TURNSTILE_WRITER_QUEUE, lock_obj: mutex, lock_irql: ts_lock_irql,
266 owner);
267
268 /* we do the dance all over again */
269 backoff = MUTEX_BACKOFF_DEFAULT;
270 owner_change_count = 0;
271 } else {
272 if (owner)
273 thread_put(t: owner);
274 /* nevermind, something changed again */
275 turnstile_unlock(obj: mutex, irql: ts_lock_irql);
276 }
277 }
278
279 /* hey ho! we got the mutex! */
280 kassert(mutex_get_owner(mutex) == current_thread);
281 mutex_chk_locked(state: &chk_state);
282 crash_unwind_enter_mutex(m: mutex);
283}
284
285void mutex_lock_internal(struct mutex *mutex,
286 const struct lock_chk_site *site) {
287 mutex_lock_subclass_internal(mutex, subclass: 0, site);
288}
289
290void mutex_unlock_internal(struct mutex *mutex,
291 const struct lock_chk_site *site) {
292 mutex_sanity_check();
293
294 struct thread *current_thread = thread_get_current();
295
296 if (mutex_get_owner(mtx: mutex) != current_thread)
297 panic("non-owner thread tried to unlock mutex. mutex owner is %p, "
298 "current thread is %p",
299 mutex_get_owner(mutex), current_thread);
300
301 enum irql ts_lock_irql;
302 struct turnstile *ts = turnstile_lookup(obj: mutex, irql_out: &ts_lock_irql);
303
304 struct mutex_chk_release_state chk_state;
305 mutex_chk_before_unlock(state: &chk_state, mutex, site);
306 mutex_lock_word_unlock(mtx: mutex);
307 mutex_chk_unlocked(state: &chk_state);
308 crash_unwind_exit_mutex(m: mutex);
309
310 /* no turnstile :) */
311 if (!ts) {
312 turnstile_unlock(obj: mutex, irql: ts_lock_irql);
313 } else {
314 turnstile_wake(ts, TURNSTILE_WRITER_QUEUE, num_threads: ts->waiters, lock_irql: ts_lock_irql);
315 }
316}
317
318bool mutex_locked(struct mutex *mtx) {
319 return MUTEX_READ_LOCK_WORD(mtx) & MUTEX_HELD_BIT;
320}
321
322void mutex_assert_held_internal(struct mutex *mtx,
323 const struct lock_chk_site *site) {
324#ifdef DEBUG_LOCK_CHK
325 mtx->chk.instance = mtx;
326 mtx->chk.type = LOCK_CHK_TYPE_MUTEX;
327 if (mtx->chk.flags != LOCK_UNCHKD && lock_chk_tracking_active() &&
328 lock_chk_assert_held_deep(&mtx->chk, LOCK_CHK_MODE_IGNORED,
329 /*want_held=*/true, site))
330 return;
331#else
332 unused(site);
333#endif
334 kassert(mutex_get_owner(mtx) == thread_get_current(),
335 "mutex not held by current thread");
336}
337
338void mutex_assert_not_held_internal(struct mutex *mtx,
339 const struct lock_chk_site *site) {
340#ifdef DEBUG_LOCK_CHK
341 mtx->chk.instance = mtx;
342 mtx->chk.type = LOCK_CHK_TYPE_MUTEX;
343 if (mtx->chk.flags != LOCK_UNCHKD && lock_chk_tracking_active() &&
344 lock_chk_assert_held_deep(&mtx->chk, LOCK_CHK_MODE_IGNORED,
345 /*want_held=*/false, site))
346 return;
347#else
348 unused(site);
349#endif
350 kassert(mutex_get_owner(mtx) != thread_get_current(),
351 "mutex unexpectedly held by current thread");
352}
353