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