1#include <sch/sched.h>
2#include <stddef.h>
3#include <sync/mutex.h>
4#include <sync/spinlock.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
13static bool try_acquire_simple_mutex(struct mutex_simple *m,
14 struct thread *curr) {
15 enum irql irql = spin_lock(lock: &m->lock);
16 if (m->owner == NULL) {
17 m->owner = curr;
18 spin_unlock(lock: &m->lock, old: irql);
19 return true;
20 }
21 spin_unlock(lock: &m->lock, old: irql);
22 return false;
23}
24
25static bool should_spin_on_mutex(struct mutex_simple *m) {
26 enum irql irql = spin_lock(lock: &m->lock);
27 struct thread *owner = m->owner;
28 bool active = owner && atomic_load(&owner->state) == THREAD_STATE_RUNNING;
29 spin_unlock(lock: &m->lock, old: irql);
30 return active;
31}
32
33static bool spin_wait_simple_mutex(struct mutex_simple *m,
34 struct thread *curr) {
35 for (int i = 0; i < 500; i++)
36 if (try_acquire_simple_mutex(m, curr))
37 return true;
38
39 return false;
40}
41
42static void block_on_simple_mutex(struct mutex_simple *m) {
43 enum irql irql = spin_lock(lock: &m->lock);
44 thread_block_on(q: &m->waiters, type: THREAD_WAIT_UNINTERRUPTIBLE, wake_src: m);
45 spin_unlock(lock: &m->lock, old: irql);
46 scheduler_yield();
47}
48
49void mutex_simple_lock(struct mutex_simple *m) {
50 struct thread *curr = thread_get_current();
51
52 while (true) {
53 if (try_acquire_simple_mutex(m, curr))
54 return;
55
56 if (should_spin_on_mutex(m))
57 if (spin_wait_simple_mutex(m, curr))
58 return;
59
60 block_on_simple_mutex(m);
61 }
62}
63
64void mutex_simple_unlock(struct mutex_simple *m) {
65 struct thread *curr = thread_get_current();
66
67 enum irql irql = spin_lock(lock: &m->lock);
68
69 if (m->owner != curr) {
70 panic("mutex unlock by non-owner thread");
71 }
72
73 m->owner = NULL;
74
75 struct thread *next = thread_queue_pop_front(q: &m->waiters);
76 if (next != NULL)
77 thread_wake(t: next, reason: THREAD_WAKE_REASON_BLOCKING_MANUAL,
78 prio: next->perceived_prio_class, wake_src: m);
79
80 spin_unlock(lock: &m->lock, old: irql);
81}
82
83void mutex_simple_init(struct mutex_simple *m) {
84 spinlock_init(lock: &m->lock);
85 thread_queue_init(q: &m->waiters);
86}
87
88void mutex_init(struct mutex *mtx) {
89 mtx->lock_word = 0;
90}
91
92struct thread *mutex_get_owner(struct mutex *mtx) {
93 return (struct thread *) (MUTEX_READ_LOCK_WORD(mtx) & (~MUTEX_META_BITS));
94}
95
96size_t mutex_lock_get_backoff(size_t current_backoff) {
97 if (!current_backoff)
98 return MUTEX_BACKOFF_DEFAULT;
99
100 if (current_backoff >= (MUTEX_BACKOFF_MAX >> MUTEX_BACKOFF_SHIFT))
101 return MUTEX_BACKOFF_MAX;
102
103 size_t new_backoff = current_backoff << MUTEX_BACKOFF_SHIFT;
104 return new_backoff > MUTEX_BACKOFF_MAX ? MUTEX_BACKOFF_MAX : new_backoff;
105}
106
107static bool mutex_owner_running(struct mutex *mutex) {
108 bool ret = false;
109
110 struct thread *owner = mutex_get_owner(mtx: mutex);
111 if (!owner) /* no owner, can't possibly be running */
112 return false;
113
114 ret = thread_get_state(t: owner) == THREAD_STATE_RUNNING;
115
116 return ret;
117}
118
119static void mutex_sanity_check() {
120 kassert(irq_in_thread_context());
121 kassert(irql_get() < IRQL_HIGH_LEVEL);
122}
123
124/* TODO: would be cool to see mutex spin/sleep stats get recorded! */
125void mutex_lock(struct mutex *mutex) {
126 mutex_sanity_check();
127
128 struct thread *current_thread = thread_get_current();
129
130 /* easy peasy nothing to do */
131 if (mutex_try_lock(mtx: mutex, self: current_thread)) {
132 return;
133 }
134
135 /* failed to spin_try_acquire... now we must do the funny business... */
136 struct thread *last_owner = mutex_get_owner(mtx: mutex);
137 struct thread *current_owner = last_owner;
138
139 /* we set a backoff to say how much we want to spin in between acquisition
140 * attempts. this is done to prevent cache thrashing from atomic RMWs */
141 size_t backoff = MUTEX_BACKOFF_DEFAULT;
142
143 /* how many times we have seen the lock owner change without ever getting
144 * a chance to acquire the lock ourselves. used to reset the backoff so that
145 * we don't wait too long on a lock... */
146 size_t owner_change_count = 0;
147
148 /* let's go gambling! */
149 while (true) {
150 lock_delay(backoff, MUTEX_BACKOFF_JITTER_PCT);
151
152 /* owner is gone, let's try and get the lock */
153 if (!(current_owner = mutex_get_owner(mtx: mutex))) {
154 if (mutex_try_lock(mtx: mutex, self: current_thread))
155 break; /* got it */
156
157 /* increase backoff, better luck next time */
158 backoff = mutex_lock_get_backoff(current_backoff: backoff);
159 owner_change_count++;
160 continue;
161 } else if (last_owner != current_owner) {
162 /* someone swapped out the owner thread */
163 last_owner = current_owner;
164 backoff = mutex_lock_get_backoff(current_backoff: backoff);
165 owner_change_count++;
166 }
167
168 /* reset these values so we can have a better chance
169 * at actually getting the lock, we've been dawdling for
170 * a while if we've reached this branch. */
171 if (owner_change_count >= global.core_count) {
172 backoff = MUTEX_BACKOFF_DEFAULT;
173 owner_change_count = 0;
174 }
175
176 /* keep trying to spin-acquire if the owner is still running */
177 if (mutex_owner_running(mutex))
178 continue;
179
180 /* owner is now no longer running, might be in a ready queue
181 * or something. regardless, this is turnstile time */
182 enum irql ts_lock_irql;
183 struct turnstile *ts = turnstile_lookup(obj: mutex, irql_out: &ts_lock_irql);
184
185 /* just kidding, the owner went back to running, we spin again :^) */
186 if (mutex_owner_running(mutex)) {
187 turnstile_unlock(obj: mutex, irql: ts_lock_irql);
188 continue;
189 }
190
191 /* owner unchanged, waiter bit still the same...
192 * time to do the slow path */
193 if (mutex_get_owner(mtx: mutex) == current_owner) {
194 turnstile_block(ts, TURNSTILE_WRITER_QUEUE, lock_obj: mutex, lock_irql: ts_lock_irql,
195 owner: current_owner);
196
197 /* we do the dance all over again */
198 backoff = MUTEX_BACKOFF_DEFAULT;
199 owner_change_count = 0;
200 } else {
201 /* nevermind, something changed again */
202 turnstile_unlock(obj: mutex, irql: ts_lock_irql);
203 }
204 }
205
206 /* hey ho! we got the mutex! */
207 kassert(mutex_get_owner(mutex) == current_thread);
208}
209
210void mutex_unlock(struct mutex *mutex) {
211 mutex_sanity_check();
212
213 struct thread *current_thread = thread_get_current();
214
215 if (mutex_get_owner(mtx: mutex) != current_thread)
216 panic("non-owner thread tried to unlock mutex. mutex owner is %p, "
217 "current thread is %p",
218 mutex_get_owner(mutex), current_thread);
219
220 enum irql ts_lock_irql;
221 struct turnstile *ts = turnstile_lookup(obj: mutex, irql_out: &ts_lock_irql);
222
223 mutex_lock_word_unlock(mtx: mutex);
224
225 /* no turnstile :) */
226 if (!ts) {
227 turnstile_unlock(obj: mutex, irql: ts_lock_irql);
228 } else {
229 turnstile_wake(ts, TURNSTILE_WRITER_QUEUE,
230 MUTEX_UNLOCK_WAKE_THREAD_COUNT(mutex), lock_irql: ts_lock_irql);
231 }
232}
233
234bool mutex_held(struct mutex *mtx) {
235 return MUTEX_READ_LOCK_WORD(mtx) & MUTEX_HELD_BIT;
236}
237