parlib: Add synchronization objects
[akaros.git] / user / parlib / mutex.c
1 /* Copyright (c) 2016-2017 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 struct uth_default_mtx {
14         struct spin_pdr_lock            lock;
15         uth_sync_t                                      sync_obj;
16         bool                                            locked;
17 };
18
19 struct uth_default_cv {
20         struct spin_pdr_lock            lock;
21         uth_sync_t                                      sync_obj;
22 };
23
24
25 /************** Default Mutex Implementation **************/
26
27
28 static struct uth_default_mtx *uth_default_mtx_alloc(void)
29 {
30         struct uth_default_mtx *mtx;
31
32         mtx = malloc(sizeof(struct uth_default_mtx));
33         assert(mtx);
34         spin_pdr_init(&mtx->lock);
35         mtx->sync_obj = __uth_sync_alloc();
36         mtx->locked = FALSE;
37         return mtx;
38 }
39
40 static void uth_default_mtx_free(struct uth_default_mtx *mtx)
41 {
42         __uth_sync_free(mtx->sync_obj);
43         free(mtx);
44 }
45
46 static void __mutex_cb(struct uthread *uth, void *arg)
47 {
48         struct uth_default_mtx *mtx = (struct uth_default_mtx*)arg;
49
50         /* We need to tell the 2LS that its thread blocked.  We need to do this
51          * before unlocking the mtx, since as soon as we unlock, the mtx could be
52          * released and our thread restarted.
53          *
54          * Also note the lock-ordering rule.  The mtx lock is grabbed before any
55          * locks the 2LS might grab. */
56         uthread_has_blocked(uth, mtx->sync_obj, UTH_EXT_BLK_MUTEX);
57         spin_pdr_unlock(&mtx->lock);
58 }
59
60 static void uth_default_mtx_lock(struct uth_default_mtx *mtx)
61 {
62         spin_pdr_lock(&mtx->lock);
63         if (!mtx->locked) {
64                 mtx->locked = TRUE;
65                 spin_pdr_unlock(&mtx->lock);
66                 return;
67         }
68         /* the unlock and sync enqueuing is done in the yield callback.  as always,
69          * we need to do this part in vcore context, since as soon as we unlock the
70          * uthread could restart.  (atomically yield and unlock). */
71         uthread_yield(TRUE, __mutex_cb, mtx);
72 }
73
74 static bool uth_default_mtx_trylock(struct uth_default_mtx *mtx)
75 {
76         bool ret = FALSE;
77
78         spin_pdr_lock(&mtx->lock);
79         if (!mtx->locked) {
80                 mtx->locked = TRUE;
81                 ret = TRUE;
82         }
83         spin_pdr_unlock(&mtx->lock);
84         return ret;
85 }
86
87 static void uth_default_mtx_unlock(struct uth_default_mtx *mtx)
88 {
89         struct uthread *uth;
90
91         spin_pdr_lock(&mtx->lock);
92         uth = __uth_sync_get_next(mtx->sync_obj);
93         if (!uth)
94                 mtx->locked = FALSE;
95         spin_pdr_unlock(&mtx->lock);
96         if (uth)
97                 uthread_runnable(uth);
98 }
99
100
101 /************** Wrappers for the uthread mutex interface **************/
102
103
104 uth_mutex_t uth_mutex_alloc(void)
105 {
106         if (sched_ops->mutex_alloc)
107                 return sched_ops->mutex_alloc();
108         return (uth_mutex_t)uth_default_mtx_alloc();
109 }
110
111 void uth_mutex_free(uth_mutex_t m)
112 {
113         if (sched_ops->mutex_free) {
114                 sched_ops->mutex_free(m);
115                 return;
116         }
117         uth_default_mtx_free((struct uth_default_mtx*)m);
118 }
119
120 void uth_mutex_lock(uth_mutex_t m)
121 {
122         if (sched_ops->mutex_lock) {
123                 sched_ops->mutex_lock(m);
124                 return;
125         }
126         uth_default_mtx_lock((struct uth_default_mtx*)m);
127 }
128
129 bool uth_mutex_trylock(uth_mutex_t m)
130 {
131         if (sched_ops->mutex_trylock)
132                 return sched_ops->mutex_trylock(m);
133         return uth_default_mtx_trylock((struct uth_default_mtx*)m);
134 }
135
136 void uth_mutex_unlock(uth_mutex_t m)
137 {
138         if (sched_ops->mutex_unlock) {
139                 sched_ops->mutex_unlock(m);
140                 return;
141         }
142         uth_default_mtx_unlock((struct uth_default_mtx*)m);
143 }
144
145
146 /************** Recursive mutexes **************/
147
148 /* Note the interface type uth_recurse_mtx_t is a pointer to this struct. */
149 struct uth_recurse_mtx {
150         uth_mutex_t                                     mtx;
151         struct uthread                          *lockholder;
152         unsigned int                            count;
153 };
154
155 uth_recurse_mutex_t uth_recurse_mutex_alloc(void)
156 {
157         struct uth_recurse_mtx *r_mtx = malloc(sizeof(struct uth_recurse_mtx));
158
159         assert(r_mtx);
160         r_mtx->mtx = uth_mutex_alloc();
161         r_mtx->lockholder = NULL;
162         r_mtx->count = 0;
163         return (uth_recurse_mutex_t)r_mtx;
164 }
165
166 void uth_recurse_mutex_free(uth_recurse_mutex_t r_m)
167 {
168         struct uth_recurse_mtx *r_mtx = (struct uth_recurse_mtx*)r_m;
169
170         uth_mutex_free(r_mtx->mtx);
171         free(r_mtx);
172 }
173
174 void uth_recurse_mutex_lock(uth_recurse_mutex_t r_m)
175 {
176         struct uth_recurse_mtx *r_mtx = (struct uth_recurse_mtx*)r_m;
177
178         assert(!in_vcore_context());
179         assert(current_uthread);
180         /* We don't have to worry about races on current_uthread or count.  They are
181          * only written by the initial lockholder, and this check will only be true
182          * for the initial lockholder, which cannot concurrently call this function
183          * twice (a thread is single-threaded).
184          *
185          * A signal handler running for a thread should not attempt to grab a
186          * recursive mutex (that's probably a bug).  If we need to support that,
187          * we'll have to disable notifs temporarily. */
188         if (r_mtx->lockholder == current_uthread) {
189                 r_mtx->count++;
190                 return;
191         }
192         uth_mutex_lock(r_mtx->mtx);
193         r_mtx->lockholder = current_uthread;
194         r_mtx->count = 1;
195 }
196
197 bool uth_recurse_mutex_trylock(uth_recurse_mutex_t r_m)
198 {
199         struct uth_recurse_mtx *r_mtx = (struct uth_recurse_mtx*)r_m;
200         bool ret;
201
202         assert(!in_vcore_context());
203         assert(current_uthread);
204         if (r_mtx->lockholder == current_uthread) {
205                 r_mtx->count++;
206                 return TRUE;
207         }
208         ret = uth_mutex_trylock(r_mtx->mtx);
209         if (ret) {
210                 r_mtx->lockholder = current_uthread;
211                 r_mtx->count = 1;
212         }
213         return ret;
214 }
215
216 void uth_recurse_mutex_unlock(uth_recurse_mutex_t r_m)
217 {
218         struct uth_recurse_mtx *r_mtx = (struct uth_recurse_mtx*)r_m;
219
220         r_mtx->count--;
221         if (!r_mtx->count) {
222                 r_mtx->lockholder = NULL;
223                 uth_mutex_unlock(r_mtx->mtx);
224         }
225 }
226
227
228 /************** Default Condition Variable Implementation **************/
229
230
231 static struct uth_default_cv *uth_default_cv_alloc(void)
232 {
233         struct uth_default_cv *cv;
234
235         cv = malloc(sizeof(struct uth_default_cv));
236         assert(cv);
237         spin_pdr_init(&cv->lock);
238         cv->sync_obj = __uth_sync_alloc();
239         return cv;
240 }
241
242 static void uth_default_cv_free(struct uth_default_cv *cv)
243 {
244         __uth_sync_free(cv->sync_obj);
245         free(cv);
246 }
247
248 struct uth_cv_link {
249         struct uth_default_cv           *cv;
250         struct uth_default_mtx          *mtx;
251 };
252
253 static void __cv_wait_cb(struct uthread *uth, void *arg)
254 {
255         struct uth_cv_link *link = (struct uth_cv_link*)arg;
256         struct uth_default_cv *cv = link->cv;
257         struct uth_default_mtx *mtx = link->mtx;
258
259         /* We need to tell the 2LS that its thread blocked.  We need to do this
260          * before unlocking the cv, since as soon as we unlock, the cv could be
261          * signalled and our thread restarted.
262          *
263          * Also note the lock-ordering rule.  The cv lock is grabbed before any
264          * locks the 2LS might grab. */
265         uthread_has_blocked(uth, cv->sync_obj, UTH_EXT_BLK_MUTEX);
266         spin_pdr_unlock(&cv->lock);
267         /* This looks dangerous, since both the CV and MTX could use the
268          * uth->sync_next TAILQ_ENTRY (or whatever the 2LS uses), but the uthread
269          * never sleeps on both at the same time.  We *hold* the mtx - we aren't
270          * *sleeping* on it.  Sleeping uses the sync_next.  Holding it doesn't.
271          *
272          * Next, consider what happens as soon as we unlock the CV.  Our thread
273          * could get woken up, and then immediately try to grab the mtx and go to
274          * sleep! (see below).  If that happens, the uthread is no longer sleeping
275          * on the CV, and the sync_next is free.  The invariant is that a uthread
276          * can only sleep on one sync_object at a time. */
277         uth_mutex_unlock((uth_mutex_t)mtx);
278 }
279
280 /* Caller holds mtx.  We will 'atomically' release it and wait.  On return,
281  * caller holds mtx again.  Once our uth is on the CV's list, we can release the
282  * mtx without fear of missing a signal.
283  *
284  * POSIX refers to atomicity in this context as "atomically with respect to
285  * access by another thread to the mutex and then the condition variable"
286  *
287  * The idea is that we hold the mutex to protect some invariant; we check it,
288  * and decide to sleep.  Now we get on the list before releasing so that any
289  * changes to that invariant (e.g. a flag is now TRUE) happen after we're on the
290  * list, and so that we don't miss the signal.  To be more clear, the invariant
291  * in a basic wake-up flag scenario is: "whenever a flag is set from FALSE to
292  * TRUE, all waiters that saw FALSE are on the CV's waitqueue."  The mutex is
293  * required for this invariant.
294  *
295  * Note that signal/broadcasters do not *need* to hold the mutex, in general,
296  * but they do in the basic wake-up flag scenario.  If not, the race is this:
297  *
298  * Sleeper:                                                             Waker:
299  * -----------------------------------------------------------------
300  * Hold mutex
301  *   See flag is False
302  *   Decide to sleep
303  *                                                                              Set flag True
304  * PAUSE!                                                               Grab CV lock
305  *                                                                              See list is empty, unlock
306  *
307  *   Grab CV lock
308  *     Get put on list
309  *   Unlock CV lock
310  * Unlock mutex
311  * (Never wake up; we missed the signal)
312  *
313  * For those familiar with the kernel's CVs, we don't couple mutexes with CVs.
314  * cv_lock() actually grabs the spinlock inside the CV and uses *that* to
315  * protect the invariant.  The signallers always grab that lock, so the sleeper
316  * is not in danger of missing the signal.  The tradeoff is that the kernel CVs
317  * use a spinlock instead of a mutex for protecting its invariant; there might
318  * be some case that preferred blocking sync.
319  *
320  * The uthread CVs take a mutex, unlike the kernel CVs, to map more cleanly to
321  * POSIX CVs.  Maybe one approach or the other is a bad idea; we'll see.
322  *
323  * As far as lock ordering goes, once the sleeper holds the mutex and is on the
324  * CV's list, it can unlock in any order it wants.  However, unlocking a mutex
325  * actually requires grabbing its spinlock.  So as to not have a lock ordering
326  * between *spinlocks*, we let go of the CV's spinlock before unlocking the
327  * mutex.  There is an ordering between the mutex and the CV spinlock (mutex->cv
328  * spin), but there is no ordering between the mutex spin and cv spin.  And of
329  * course, we need to unlock the CV spinlock in the yield callback.
330  *
331  * Also note that we use the external API for the mutex operations.  A 2LS could
332  * have their own mutex ops but still use the generic cv ops. */
333 static void uth_default_cv_wait(struct uth_default_cv *cv,
334                                 struct uth_default_mtx *mtx)
335 {
336         struct uth_cv_link link;
337
338         link.cv = cv;
339         link.mtx = mtx;
340         spin_pdr_lock(&cv->lock);
341         uthread_yield(TRUE, __cv_wait_cb, &link);
342         uth_mutex_lock((uth_mutex_t)mtx);
343 }
344
345 static void uth_default_cv_signal(struct uth_default_cv *cv)
346 {
347         struct uthread *uth;
348
349         spin_pdr_lock(&cv->lock);
350         uth = __uth_sync_get_next(cv->sync_obj);
351         spin_pdr_unlock(&cv->lock);
352         if (uth)
353                 uthread_runnable(uth);
354 }
355
356 static void uth_default_cv_broadcast(struct uth_default_cv *cv)
357 {
358         struct uth_tailq restartees = TAILQ_HEAD_INITIALIZER(restartees);
359         struct uthread *i, *safe;
360
361         spin_pdr_lock(&cv->lock);
362         /* If this turns out to be slow or painful for 2LSs, we can implement a
363          * get_all or something (default used to use TAILQ_SWAP). */
364         while ((i = __uth_sync_get_next(cv->sync_obj))) {
365                 /* Once the uth is out of the sync obj, we can reuse sync_next. */
366                 TAILQ_INSERT_TAIL(&restartees, i, sync_next);
367         }
368         spin_pdr_unlock(&cv->lock);
369         /* Need the SAFE, since we can't touch the linkage once the uth could run */
370         TAILQ_FOREACH_SAFE(i, &restartees, sync_next, safe)
371                 uthread_runnable(i);
372 }
373
374
375 /************** Wrappers for the uthread CV interface **************/
376
377
378 uth_cond_var_t uth_cond_var_alloc(void)
379 {
380         if (sched_ops->cond_var_alloc)
381                 return sched_ops->cond_var_alloc();
382         return (uth_cond_var_t)uth_default_cv_alloc();
383 }
384
385 void uth_cond_var_free(uth_cond_var_t cv)
386 {
387         if (sched_ops->cond_var_free) {
388                 sched_ops->cond_var_free(cv);
389                 return;
390         }
391         uth_default_cv_free((struct uth_default_cv*)cv);
392 }
393
394 void uth_cond_var_wait(uth_cond_var_t cv, uth_mutex_t m)
395 {
396         if (sched_ops->cond_var_wait) {
397                 sched_ops->cond_var_wait(cv, m);
398                 return;
399         }
400         uth_default_cv_wait((struct uth_default_cv*)cv, (struct uth_default_mtx*)m);
401 }
402
403 void uth_cond_var_signal(uth_cond_var_t cv)
404 {
405         if (sched_ops->cond_var_signal) {
406                 sched_ops->cond_var_signal(cv);
407                 return;
408         }
409         uth_default_cv_signal((struct uth_default_cv*)cv);
410 }
411
412 void uth_cond_var_broadcast(uth_cond_var_t cv)
413 {
414         if (sched_ops->cond_var_broadcast) {
415                 sched_ops->cond_var_broadcast(cv);
416                 return;
417         }
418         uth_default_cv_broadcast((struct uth_default_cv*)cv);
419 }
420
421
422 /************** Default Sync Obj Implementation **************/
423
424 static uth_sync_t uth_default_sync_alloc(void)
425 {
426         struct uth_tailq *tq;
427
428         tq = malloc(sizeof(struct uth_tailq));
429         assert(tq);
430         TAILQ_INIT(tq);
431         return (uth_sync_t)tq;
432 }
433
434 static void uth_default_sync_free(uth_sync_t sync)
435 {
436         struct uth_tailq *tq = (struct uth_tailq*)sync;
437
438         assert(TAILQ_EMPTY(tq));
439         free(tq);
440 }
441
442 static struct uthread *uth_default_sync_get_next(uth_sync_t sync)
443 {
444         struct uth_tailq *tq = (struct uth_tailq*)sync;
445         struct uthread *first;
446
447         first = TAILQ_FIRST(tq);
448         if (first)
449                 TAILQ_REMOVE(tq, first, sync_next);
450         return first;
451 }
452
453 static bool uth_default_sync_get_uth(uth_sync_t sync, struct uthread *uth)
454 {
455         struct uth_tailq *tq = (struct uth_tailq*)sync;
456         struct uthread *i;
457
458         TAILQ_FOREACH(i, tq, sync_next) {
459                 if (i == uth) {
460                         TAILQ_REMOVE(tq, i, sync_next);
461                         return TRUE;
462                 }
463         }
464         return FALSE;
465 }
466
467 /************** External uthread sync interface **************/
468
469 /* Called by the 2LS->has_blocked op, if they are using the default sync.*/
470 void __uth_default_sync_enqueue(struct uthread *uth, uth_sync_t sync)
471 {
472         struct uth_tailq *tq = (struct uth_tailq*)sync;
473
474         TAILQ_INSERT_TAIL(tq, uth, sync_next);
475 }
476
477 /* Called by 2LS-independent sync code when a sync object is created. */
478 uth_sync_t __uth_sync_alloc(void)
479 {
480         if (sched_ops->sync_alloc)
481                 return sched_ops->sync_alloc();
482         return uth_default_sync_alloc();
483 }
484
485 /* Called by 2LS-independent sync code when a sync object is destroyed. */
486 void __uth_sync_free(uth_sync_t sync)
487 {
488         if (sched_ops->sync_free) {
489                 sched_ops->sync_free(sync);
490                 return;
491         }
492         uth_default_sync_free(sync);
493 }
494
495 /* Called by 2LS-independent sync code when a thread needs to be woken. */
496 struct uthread *__uth_sync_get_next(uth_sync_t sync)
497 {
498         if (sched_ops->sync_get_next)
499                 return sched_ops->sync_get_next(sync);
500         return uth_default_sync_get_next(sync);
501 }
502
503 /* Called by 2LS-independent sync code when a specific thread needs to be woken.
504  * Returns TRUE if the uthread was blocked on the object, FALSE o/w. */
505 bool __uth_sync_get_uth(uth_sync_t sync, struct uthread *uth)
506 {
507         if (sched_ops->sync_get_uth)
508                 return sched_ops->sync_get_uth(sync, uth);
509         return uth_default_sync_get_uth(sync, uth);
510 }