parlib: Add recursive uthread mutexes
[akaros.git] / user / parlib / mutex.c
1 /* Copyright (c) 2016 Google, Inc.
2  * Barret Rhoden <brho@cs.berkeley.edu>
3  * See LICENSE for details. */
4
5 /* Generic Uthread Mutexes and CVs.  2LSs implement their own methods, but we
6  * need a 2LS-independent interface and default implementation. */
7
8 #include <parlib/uthread.h>
9 #include <sys/queue.h>
10 #include <parlib/spinlock.h>
11 #include <malloc.h>
12
13 /* The linkage structs are for the yield callbacks */
14 struct uth_default_mtx;
15 struct uth_mtx_link {
16         TAILQ_ENTRY(uth_mtx_link)       next;
17         struct uth_default_mtx          *mtx;
18         struct uthread                          *uth;
19 };
20 TAILQ_HEAD(mtx_link_tq, uth_mtx_link);
21
22 struct uth_default_mtx {
23         struct spin_pdr_lock            lock;
24         struct mtx_link_tq                      waiters;
25         bool                                            locked;
26 };
27
28 struct uth_default_cv;
29 struct uth_cv_link {
30         TAILQ_ENTRY(uth_cv_link)        next;
31         struct uth_default_cv           *cv;
32         struct uth_default_mtx          *mtx;
33         struct uthread                          *uth;
34 };
35 TAILQ_HEAD(cv_link_tq, uth_cv_link);
36
37 struct uth_default_cv {
38         struct spin_pdr_lock            lock;
39         struct cv_link_tq                       waiters;
40 };
41
42
43 /************** Default Mutex Implementation **************/
44
45
46 static struct uth_default_mtx *uth_default_mtx_alloc(void)
47 {
48         struct uth_default_mtx *mtx;
49
50         mtx = malloc(sizeof(struct uth_default_mtx));
51         assert(mtx);
52         spin_pdr_init(&mtx->lock);
53         TAILQ_INIT(&mtx->waiters);
54         mtx->locked = FALSE;
55         return mtx;
56 }
57
58 static void uth_default_mtx_free(struct uth_default_mtx *mtx)
59 {
60         assert(TAILQ_EMPTY(&mtx->waiters));
61         free(mtx);
62 }
63
64 static void __mutex_cb(struct uthread *uth, void *arg)
65 {
66         struct uth_mtx_link *link = (struct uth_mtx_link*)arg;
67         struct uth_default_mtx *mtx = link->mtx;
68
69         /* We need to tell the 2LS that its thread blocked.  We need to do this
70          * before unlocking the mtx, since as soon as we unlock, the mtx could be
71          * released and our thread restarted.
72          *
73          * Also note the lock-ordering rule.  The mtx lock is grabbed before any
74          * locks the 2LS might grab. */
75         uthread_has_blocked(uth, UTH_EXT_BLK_MUTEX);
76         spin_pdr_unlock(&mtx->lock);
77 }
78
79 static void uth_default_mtx_lock(struct uth_default_mtx *mtx)
80 {
81         struct uth_mtx_link link;
82
83         spin_pdr_lock(&mtx->lock);
84         if (!mtx->locked) {
85                 mtx->locked = TRUE;
86                 spin_pdr_unlock(&mtx->lock);
87                 return;
88         }
89         link.mtx = mtx;
90         link.uth = current_uthread;
91         TAILQ_INSERT_TAIL(&mtx->waiters, &link, next);
92         /* the unlock is done in the yield callback.  as always, we need to do this
93          * part in vcore context, since as soon as we unlock the uthread could
94          * restart.  (atomically yield and unlock). */
95         uthread_yield(TRUE, __mutex_cb, &link);
96 }
97
98 static bool uth_default_mtx_trylock(struct uth_default_mtx *mtx)
99 {
100         bool ret = FALSE;
101
102         spin_pdr_lock(&mtx->lock);
103         if (!mtx->locked) {
104                 mtx->locked = TRUE;
105                 ret = TRUE;
106         }
107         spin_pdr_unlock(&mtx->lock);
108         return ret;
109 }
110
111 static void uth_default_mtx_unlock(struct uth_default_mtx *mtx)
112 {
113         struct uth_mtx_link *first;
114
115         spin_pdr_lock(&mtx->lock);
116         first = TAILQ_FIRST(&mtx->waiters);
117         if (first)
118                 TAILQ_REMOVE(&mtx->waiters, first, next);
119         else
120                 mtx->locked = FALSE;
121         spin_pdr_unlock(&mtx->lock);
122         if (first)
123                 uthread_runnable(first->uth);
124 }
125
126
127 /************** Wrappers for the uthread mutex interface **************/
128
129
130 uth_mutex_t uth_mutex_alloc(void)
131 {
132         if (sched_ops->mutex_alloc)
133                 return sched_ops->mutex_alloc();
134         return (uth_mutex_t)uth_default_mtx_alloc();
135 }
136
137 void uth_mutex_free(uth_mutex_t m)
138 {
139         if (sched_ops->mutex_free) {
140                 sched_ops->mutex_free(m);
141                 return;
142         }
143         uth_default_mtx_free((struct uth_default_mtx*)m);
144 }
145
146 void uth_mutex_lock(uth_mutex_t m)
147 {
148         if (sched_ops->mutex_lock) {
149                 sched_ops->mutex_lock(m);
150                 return;
151         }
152         uth_default_mtx_lock((struct uth_default_mtx*)m);
153 }
154
155 bool uth_mutex_trylock(uth_mutex_t m)
156 {
157         if (sched_ops->mutex_trylock)
158                 return sched_ops->mutex_trylock(m);
159         return uth_default_mtx_trylock((struct uth_default_mtx*)m);
160 }
161
162 void uth_mutex_unlock(uth_mutex_t m)
163 {
164         if (sched_ops->mutex_unlock) {
165                 sched_ops->mutex_unlock(m);
166                 return;
167         }
168         uth_default_mtx_unlock((struct uth_default_mtx*)m);
169 }
170
171
172 /************** Recursive mutexes **************/
173
174 /* Note the interface type uth_recurse_mtx_t is a pointer to this struct. */
175 struct uth_recurse_mtx {
176         uth_mutex_t                                     mtx;
177         struct uthread                          *lockholder;
178         unsigned int                            count;
179 };
180
181 uth_recurse_mutex_t uth_recurse_mutex_alloc(void)
182 {
183         struct uth_recurse_mtx *r_mtx = malloc(sizeof(struct uth_recurse_mtx));
184
185         assert(r_mtx);
186         r_mtx->mtx = uth_mutex_alloc();
187         r_mtx->lockholder = NULL;
188         r_mtx->count = 0;
189         return (uth_recurse_mutex_t)r_mtx;
190 }
191
192 void uth_recurse_mutex_free(uth_recurse_mutex_t r_m)
193 {
194         struct uth_recurse_mtx *r_mtx = (struct uth_recurse_mtx*)r_m;
195
196         uth_mutex_free(r_mtx->mtx);
197         free(r_mtx);
198 }
199
200 void uth_recurse_mutex_lock(uth_recurse_mutex_t r_m)
201 {
202         struct uth_recurse_mtx *r_mtx = (struct uth_recurse_mtx*)r_m;
203
204         assert(!in_vcore_context());
205         assert(current_uthread);
206         /* We don't have to worry about races on current_uthread or count.  They are
207          * only written by the initial lockholder, and this check will only be true
208          * for the initial lockholder, which cannot concurrently call this function
209          * twice (a thread is single-threaded).
210          *
211          * A signal handler running for a thread should not attempt to grab a
212          * recursive mutex (that's probably a bug).  If we need to support that,
213          * we'll have to disable notifs temporarily. */
214         if (r_mtx->lockholder == current_uthread) {
215                 r_mtx->count++;
216                 return;
217         }
218         uth_mutex_lock(r_mtx->mtx);
219         r_mtx->lockholder = current_uthread;
220         r_mtx->count = 1;
221 }
222
223 bool uth_recurse_mutex_trylock(uth_recurse_mutex_t r_m)
224 {
225         struct uth_recurse_mtx *r_mtx = (struct uth_recurse_mtx*)r_m;
226         bool ret;
227
228         assert(!in_vcore_context());
229         assert(current_uthread);
230         if (r_mtx->lockholder == current_uthread) {
231                 r_mtx->count++;
232                 return TRUE;
233         }
234         ret = uth_mutex_trylock(r_mtx->mtx);
235         if (ret) {
236                 r_mtx->lockholder = current_uthread;
237                 r_mtx->count = 1;
238         }
239         return ret;
240 }
241
242 void uth_recurse_mutex_unlock(uth_recurse_mutex_t r_m)
243 {
244         struct uth_recurse_mtx *r_mtx = (struct uth_recurse_mtx*)r_m;
245
246         r_mtx->count--;
247         if (!r_mtx->count) {
248                 r_mtx->lockholder = NULL;
249                 uth_mutex_unlock(r_mtx->mtx);
250         }
251 }
252
253
254 /************** Default Condition Variable Implementation **************/
255
256
257 static struct uth_default_cv *uth_default_cv_alloc(void)
258 {
259         struct uth_default_cv *cv;
260
261         cv = malloc(sizeof(struct uth_default_cv));
262         assert(cv);
263         spin_pdr_init(&cv->lock);
264         TAILQ_INIT(&cv->waiters);
265         return cv;
266 }
267
268 static void uth_default_cv_free(struct uth_default_cv *cv)
269 {
270         assert(TAILQ_EMPTY(&cv->waiters));
271         free(cv);
272 }
273
274 static void __cv_wait_cb(struct uthread *uth, void *arg)
275 {
276         struct uth_cv_link *link = (struct uth_cv_link*)arg;
277         struct uth_default_cv *cv = link->cv;
278         struct uth_default_mtx *mtx = link->mtx;
279
280         /* We need to tell the 2LS that its thread blocked.  We need to do this
281          * before unlocking the cv, since as soon as we unlock, the cv could be
282          * signalled and our thread restarted.
283          *
284          * Also note the lock-ordering rule.  The cv lock is grabbed before any
285          * locks the 2LS might grab. */
286         uthread_has_blocked(uth, UTH_EXT_BLK_MUTEX);
287         spin_pdr_unlock(&cv->lock);
288         uth_mutex_unlock((uth_mutex_t)mtx);
289 }
290
291 /* Caller holds mtx.  We will 'atomically' release it and wait.  On return,
292  * caller holds mtx again.  Once our uth is on the CV's list, we can release the
293  * mtx without fear of missing a signal.
294  *
295  * POSIX refers to atomicity in this context as "atomically with respect to
296  * access by another thread to the mutex and then the condition variable"
297  *
298  * The idea is that we hold the mutex to protect some invariant; we check it,
299  * and decide to sleep.  Now we get on the list before releasing so that any
300  * changes to that invariant (e.g. a flag is now TRUE) happen after we're on the
301  * list, and so that we don't miss the signal.  To be more clear, the invariant
302  * in a basic wake-up flag scenario is: "whenever a flag is set from FALSE to
303  * TRUE, all waiters that saw FALSE are on the CV's waitqueue."  The mutex is
304  * required for this invariant.
305  *
306  * Note that signal/broadcasters do not *need* to hold the mutex, in general,
307  * but they do in the basic wake-up flag scenario.  If not, the race is this:
308  *
309  * Sleeper:                                                             Waker:
310  * -----------------------------------------------------------------
311  * Hold mutex
312  *   See flag is False
313  *   Decide to sleep
314  *                                                                              Set flag True
315  * PAUSE!                                                               Grab CV lock
316  *                                                                              See list is empty, unlock
317  *
318  *   Grab CV lock
319  *     Get put on list
320  *   Unlock CV lock
321  * Unlock mutex
322  * (Never wake up; we missed the signal)
323  *
324  * For those familiar with the kernel's CVs, we don't couple mutexes with CVs.
325  * cv_lock() actually grabs the spinlock inside the CV and uses *that* to
326  * protect the invariant.  The signallers always grab that lock, so the sleeper
327  * is not in danger of missing the signal.  The tradeoff is that the kernel CVs
328  * use a spinlock instead of a mutex for protecting its invariant; there might
329  * be some case that preferred blocking sync.
330  *
331  * The uthread CVs take a mutex, unlike the kernel CVs, to map more cleanly to
332  * POSIX CVs.  Maybe one approach or the other is a bad idea; we'll see.
333  *
334  * As far as lock ordering goes, once the sleeper holds the mutex and is on the
335  * CV's list, it can unlock in any order it wants.  However, unlocking a mutex
336  * actually requires grabbing its spinlock.  So as to not have a lock ordering
337  * between *spinlocks*, we let go of the CV's spinlock before unlocking the
338  * mutex.  There is an ordering between the mutex and the CV spinlock (mutex->cv
339  * spin), but there is no ordering between the mutex spin and cv spin.  And of
340  * course, we need to unlock the CV spinlock in the yield callback.
341  *
342  * Also note that we use the external API for the mutex operations.  A 2LS could
343  * have their own mutex ops but still use the generic cv ops. */
344 static void uth_default_cv_wait(struct uth_default_cv *cv,
345                                 struct uth_default_mtx *mtx)
346 {
347         struct uth_cv_link link;
348
349         link.cv = cv;
350         link.mtx = mtx;
351         link.uth = current_uthread;
352         spin_pdr_lock(&cv->lock);
353         TAILQ_INSERT_TAIL(&cv->waiters, &link, next);
354         uthread_yield(TRUE, __cv_wait_cb, &link);
355         uth_mutex_lock((uth_mutex_t)mtx);
356 }
357
358 static void uth_default_cv_signal(struct uth_default_cv *cv)
359 {
360         struct uth_cv_link *first;
361
362         spin_pdr_lock(&cv->lock);
363         first = TAILQ_FIRST(&cv->waiters);
364         if (first)
365                 TAILQ_REMOVE(&cv->waiters, first, next);
366         spin_pdr_unlock(&cv->lock);
367         if (first)
368                 uthread_runnable(first->uth);
369 }
370
371 static void uth_default_cv_broadcast(struct uth_default_cv *cv)
372 {
373         struct cv_link_tq restartees = TAILQ_HEAD_INITIALIZER(restartees);
374         struct uth_cv_link *i, *safe;
375
376         spin_pdr_lock(&cv->lock);
377         TAILQ_SWAP(&cv->waiters, &restartees, uth_cv_link, next);
378         spin_pdr_unlock(&cv->lock);
379         /* Need the SAFE, since we can't touch the linkage once the uth could run */
380         TAILQ_FOREACH_SAFE(i, &restartees, next, safe)
381                 uthread_runnable(i->uth);
382 }
383
384
385 /************** Wrappers for the uthread CV interface **************/
386
387
388 uth_cond_var_t uth_cond_var_alloc(void)
389 {
390         if (sched_ops->cond_var_alloc)
391                 return sched_ops->cond_var_alloc();
392         return (uth_cond_var_t)uth_default_cv_alloc();
393 }
394
395 void uth_cond_var_free(uth_cond_var_t cv)
396 {
397         if (sched_ops->cond_var_free) {
398                 sched_ops->cond_var_free(cv);
399                 return;
400         }
401         uth_default_cv_free((struct uth_default_cv*)cv);
402 }
403
404 void uth_cond_var_wait(uth_cond_var_t cv, uth_mutex_t m)
405 {
406         if (sched_ops->cond_var_wait) {
407                 sched_ops->cond_var_wait(cv, m);
408                 return;
409         }
410         uth_default_cv_wait((struct uth_default_cv*)cv, (struct uth_default_mtx*)m);
411 }
412
413 void uth_cond_var_signal(uth_cond_var_t cv)
414 {
415         if (sched_ops->cond_var_signal) {
416                 sched_ops->cond_var_signal(cv);
417                 return;
418         }
419         uth_default_cv_signal((struct uth_default_cv*)cv);
420 }
421
422 void uth_cond_var_broadcast(uth_cond_var_t cv)
423 {
424         if (sched_ops->cond_var_broadcast) {
425                 sched_ops->cond_var_broadcast(cv);
426                 return;
427         }
428         uth_default_cv_broadcast((struct uth_default_cv*)cv);
429 }