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