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