parlib: Add trylock to 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 /************** Default Condition Variable Implementation **************/
173
174
175 static struct uth_default_cv *uth_default_cv_alloc(void)
176 {
177         struct uth_default_cv *cv;
178
179         cv = malloc(sizeof(struct uth_default_cv));
180         assert(cv);
181         spin_pdr_init(&cv->lock);
182         TAILQ_INIT(&cv->waiters);
183         return cv;
184 }
185
186 static void uth_default_cv_free(struct uth_default_cv *cv)
187 {
188         assert(TAILQ_EMPTY(&cv->waiters));
189         free(cv);
190 }
191
192 static void __cv_wait_cb(struct uthread *uth, void *arg)
193 {
194         struct uth_cv_link *link = (struct uth_cv_link*)arg;
195         struct uth_default_cv *cv = link->cv;
196         struct uth_default_mtx *mtx = link->mtx;
197
198         /* We need to tell the 2LS that its thread blocked.  We need to do this
199          * before unlocking the cv, since as soon as we unlock, the cv could be
200          * signalled and our thread restarted.
201          *
202          * Also note the lock-ordering rule.  The cv lock is grabbed before any
203          * locks the 2LS might grab. */
204         uthread_has_blocked(uth, UTH_EXT_BLK_MUTEX);
205         spin_pdr_unlock(&cv->lock);
206         uth_mutex_unlock((uth_mutex_t)mtx);
207 }
208
209 /* Caller holds mtx.  We will 'atomically' release it and wait.  On return,
210  * caller holds mtx again.  Once our uth is on the CV's list, we can release the
211  * mtx without fear of missing a signal.
212  *
213  * POSIX refers to atomicity in this context as "atomically with respect to
214  * access by another thread to the mutex and then the condition variable"
215  *
216  * The idea is that we hold the mutex to protect some invariant; we check it,
217  * and decide to sleep.  Now we get on the list before releasing so that any
218  * changes to that invariant (e.g. a flag is now TRUE) happen after we're on the
219  * list, and so that we don't miss the signal.  To be more clear, the invariant
220  * in a basic wake-up flag scenario is: "whenever a flag is set from FALSE to
221  * TRUE, all waiters that saw FALSE are on the CV's waitqueue."  The mutex is
222  * required for this invariant.
223  *
224  * Note that signal/broadcasters do not *need* to hold the mutex, in general,
225  * but they do in the basic wake-up flag scenario.  If not, the race is this:
226  *
227  * Sleeper:                                                             Waker:
228  * -----------------------------------------------------------------
229  * Hold mutex
230  *   See flag is False
231  *   Decide to sleep
232  *                                                                              Set flag True
233  * PAUSE!                                                               Grab CV lock
234  *                                                                              See list is empty, unlock
235  *
236  *   Grab CV lock
237  *     Get put on list
238  *   Unlock CV lock
239  * Unlock mutex
240  * (Never wake up; we missed the signal)
241  *
242  * For those familiar with the kernel's CVs, we don't couple mutexes with CVs.
243  * cv_lock() actually grabs the spinlock inside the CV and uses *that* to
244  * protect the invariant.  The signallers always grab that lock, so the sleeper
245  * is not in danger of missing the signal.  The tradeoff is that the kernel CVs
246  * use a spinlock instead of a mutex for protecting its invariant; there might
247  * be some case that preferred blocking sync.
248  *
249  * The uthread CVs take a mutex, unlike the kernel CVs, to map more cleanly to
250  * POSIX CVs.  Maybe one approach or the other is a bad idea; we'll see.
251  *
252  * As far as lock ordering goes, once the sleeper holds the mutex and is on the
253  * CV's list, it can unlock in any order it wants.  However, unlocking a mutex
254  * actually requires grabbing its spinlock.  So as to not have a lock ordering
255  * between *spinlocks*, we let go of the CV's spinlock before unlocking the
256  * mutex.  There is an ordering between the mutex and the CV spinlock (mutex->cv
257  * spin), but there is no ordering between the mutex spin and cv spin.  And of
258  * course, we need to unlock the CV spinlock in the yield callback.
259  *
260  * Also note that we use the external API for the mutex operations.  A 2LS could
261  * have their own mutex ops but still use the generic cv ops. */
262 static void uth_default_cv_wait(struct uth_default_cv *cv,
263                                 struct uth_default_mtx *mtx)
264 {
265         struct uth_cv_link link;
266
267         link.cv = cv;
268         link.mtx = mtx;
269         link.uth = current_uthread;
270         spin_pdr_lock(&cv->lock);
271         TAILQ_INSERT_TAIL(&cv->waiters, &link, next);
272         uthread_yield(TRUE, __cv_wait_cb, &link);
273         uth_mutex_lock((uth_mutex_t)mtx);
274 }
275
276 static void uth_default_cv_signal(struct uth_default_cv *cv)
277 {
278         struct uth_cv_link *first;
279
280         spin_pdr_lock(&cv->lock);
281         first = TAILQ_FIRST(&cv->waiters);
282         if (first)
283                 TAILQ_REMOVE(&cv->waiters, first, next);
284         spin_pdr_unlock(&cv->lock);
285         if (first)
286                 uthread_runnable(first->uth);
287 }
288
289 static void uth_default_cv_broadcast(struct uth_default_cv *cv)
290 {
291         struct cv_link_tq restartees = TAILQ_HEAD_INITIALIZER(restartees);
292         struct uth_cv_link *i, *safe;
293
294         spin_pdr_lock(&cv->lock);
295         TAILQ_SWAP(&cv->waiters, &restartees, uth_cv_link, next);
296         spin_pdr_unlock(&cv->lock);
297         /* Need the SAFE, since we can't touch the linkage once the uth could run */
298         TAILQ_FOREACH_SAFE(i, &restartees, next, safe)
299                 uthread_runnable(i->uth);
300 }
301
302
303 /************** Wrappers for the uthread CV interface **************/
304
305
306 uth_cond_var_t uth_cond_var_alloc(void)
307 {
308         if (sched_ops->cond_var_alloc)
309                 return sched_ops->cond_var_alloc();
310         return (uth_cond_var_t)uth_default_cv_alloc();
311 }
312
313 void uth_cond_var_free(uth_cond_var_t cv)
314 {
315         if (sched_ops->cond_var_free) {
316                 sched_ops->cond_var_free(cv);
317                 return;
318         }
319         uth_default_cv_free((struct uth_default_cv*)cv);
320 }
321
322 void uth_cond_var_wait(uth_cond_var_t cv, uth_mutex_t m)
323 {
324         if (sched_ops->cond_var_wait) {
325                 sched_ops->cond_var_wait(cv, m);
326                 return;
327         }
328         uth_default_cv_wait((struct uth_default_cv*)cv, (struct uth_default_mtx*)m);
329 }
330
331 void uth_cond_var_signal(uth_cond_var_t cv)
332 {
333         if (sched_ops->cond_var_signal) {
334                 sched_ops->cond_var_signal(cv);
335                 return;
336         }
337         uth_default_cv_signal((struct uth_default_cv*)cv);
338 }
339
340 void uth_cond_var_broadcast(uth_cond_var_t cv)
341 {
342         if (sched_ops->cond_var_broadcast) {
343                 sched_ops->cond_var_broadcast(cv);
344                 return;
345         }
346         uth_default_cv_broadcast((struct uth_default_cv*)cv);
347 }