cons: Support epolling /dev/null
[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 void uth_default_mtx_unlock(struct uth_default_mtx *mtx)
99 {
100         struct uth_mtx_link *first;
101
102         spin_pdr_lock(&mtx->lock);
103         first = TAILQ_FIRST(&mtx->waiters);
104         if (first)
105                 TAILQ_REMOVE(&mtx->waiters, first, next);
106         else
107                 mtx->locked = FALSE;
108         spin_pdr_unlock(&mtx->lock);
109         if (first)
110                 uthread_runnable(first->uth);
111 }
112
113
114 /************** Wrappers for the uthread mutex interface **************/
115
116
117 uth_mutex_t uth_mutex_alloc(void)
118 {
119         if (sched_ops->mutex_alloc)
120                 return sched_ops->mutex_alloc();
121         return (uth_mutex_t)uth_default_mtx_alloc();
122 }
123
124 void uth_mutex_free(uth_mutex_t m)
125 {
126         if (sched_ops->mutex_free) {
127                 sched_ops->mutex_free(m);
128                 return;
129         }
130         uth_default_mtx_free((struct uth_default_mtx*)m);
131 }
132
133 void uth_mutex_lock(uth_mutex_t m)
134 {
135         if (sched_ops->mutex_lock) {
136                 sched_ops->mutex_lock(m);
137                 return;
138         }
139         uth_default_mtx_lock((struct uth_default_mtx*)m);
140 }
141
142 void uth_mutex_unlock(uth_mutex_t m)
143 {
144         if (sched_ops->mutex_unlock) {
145                 sched_ops->mutex_unlock(m);
146                 return;
147         }
148         uth_default_mtx_unlock((struct uth_default_mtx*)m);
149 }
150
151
152 /************** Default Condition Variable Implementation **************/
153
154
155 static struct uth_default_cv *uth_default_cv_alloc(void)
156 {
157         struct uth_default_cv *cv;
158
159         cv = malloc(sizeof(struct uth_default_cv));
160         assert(cv);
161         spin_pdr_init(&cv->lock);
162         TAILQ_INIT(&cv->waiters);
163         return cv;
164 }
165
166 static void uth_default_cv_free(struct uth_default_cv *cv)
167 {
168         assert(TAILQ_EMPTY(&cv->waiters));
169         free(cv);
170 }
171
172 static void __cv_wait_cb(struct uthread *uth, void *arg)
173 {
174         struct uth_cv_link *link = (struct uth_cv_link*)arg;
175         struct uth_default_cv *cv = link->cv;
176         struct uth_default_mtx *mtx = link->mtx;
177
178         /* We need to tell the 2LS that its thread blocked.  We need to do this
179          * before unlocking the cv, since as soon as we unlock, the cv could be
180          * signalled and our thread restarted.
181          *
182          * Also note the lock-ordering rule.  The cv lock is grabbed before any
183          * locks the 2LS might grab. */
184         uthread_has_blocked(uth, UTH_EXT_BLK_MUTEX);
185         spin_pdr_unlock(&cv->lock);
186         uth_mutex_unlock((uth_mutex_t)mtx);
187 }
188
189 /* Caller holds mtx.  We will 'atomically' release it and wait.  On return,
190  * caller holds mtx again.  Once our uth is on the CV's list, we can release the
191  * mtx without fear of missing a signal.
192  *
193  * POSIX refers to atomicity in this context as "atomically with respect to
194  * access by another thread to the mutex and then the condition variable"
195  *
196  * The idea is that we hold the mutex to protect some invariant; we check it,
197  * and decide to sleep.  Now we get on the list before releasing so that any
198  * changes to that invariant (e.g. a flag is now TRUE) happen after we're on the
199  * list, and so that we don't miss the signal.  To be more clear, the invariant
200  * in a basic wake-up flag scenario is: "whenever a flag is set from FALSE to
201  * TRUE, all waiters that saw FALSE are on the CV's waitqueue."  The mutex is
202  * required for this invariant.
203  *
204  * Note that signal/broadcasters do not *need* to hold the mutex, in general,
205  * but they do in the basic wake-up flag scenario.  If not, the race is this:
206  *
207  * Sleeper:                                                             Waker:
208  * -----------------------------------------------------------------
209  * Hold mutex
210  *   See flag is False
211  *   Decide to sleep
212  *                                                                              Set flag True
213  * PAUSE!                                                               Grab CV lock
214  *                                                                              See list is empty, unlock
215  *
216  *   Grab CV lock
217  *     Get put on list
218  *   Unlock CV lock
219  * Unlock mutex
220  * (Never wake up; we missed the signal)
221  *
222  * For those familiar with the kernel's CVs, we don't couple mutexes with CVs.
223  * cv_lock() actually grabs the spinlock inside the CV and uses *that* to
224  * protect the invariant.  The signallers always grab that lock, so the sleeper
225  * is not in danger of missing the signal.  The tradeoff is that the kernel CVs
226  * use a spinlock instead of a mutex for protecting its invariant; there might
227  * be some case that preferred blocking sync.
228  *
229  * The uthread CVs take a mutex, unlike the kernel CVs, to map more cleanly to
230  * POSIX CVs.  Maybe one approach or the other is a bad idea; we'll see.
231  *
232  * As far as lock ordering goes, once the sleeper holds the mutex and is on the
233  * CV's list, it can unlock in any order it wants.  However, unlocking a mutex
234  * actually requires grabbing its spinlock.  So as to not have a lock ordering
235  * between *spinlocks*, we let go of the CV's spinlock before unlocking the
236  * mutex.  There is an ordering between the mutex and the CV spinlock (mutex->cv
237  * spin), but there is no ordering between the mutex spin and cv spin.  And of
238  * course, we need to unlock the CV spinlock in the yield callback.
239  *
240  * Also note that we use the external API for the mutex operations.  A 2LS could
241  * have their own mutex ops but still use the generic cv ops. */
242 static void uth_default_cv_wait(struct uth_default_cv *cv,
243                                 struct uth_default_mtx *mtx)
244 {
245         struct uth_cv_link link;
246
247         link.cv = cv;
248         link.mtx = mtx;
249         link.uth = current_uthread;
250         spin_pdr_lock(&cv->lock);
251         TAILQ_INSERT_TAIL(&cv->waiters, &link, next);
252         uthread_yield(TRUE, __cv_wait_cb, &link);
253         uth_mutex_lock((uth_mutex_t)mtx);
254 }
255
256 static void uth_default_cv_signal(struct uth_default_cv *cv)
257 {
258         struct uth_cv_link *first;
259
260         spin_pdr_lock(&cv->lock);
261         first = TAILQ_FIRST(&cv->waiters);
262         if (first)
263                 TAILQ_REMOVE(&cv->waiters, first, next);
264         spin_pdr_unlock(&cv->lock);
265         if (first)
266                 uthread_runnable(first->uth);
267 }
268
269 static void uth_default_cv_broadcast(struct uth_default_cv *cv)
270 {
271         struct cv_link_tq restartees = TAILQ_HEAD_INITIALIZER(restartees);
272         struct uth_cv_link *i, *safe;
273
274         spin_pdr_lock(&cv->lock);
275         TAILQ_SWAP(&cv->waiters, &restartees, uth_cv_link, next);
276         spin_pdr_unlock(&cv->lock);
277         /* Need the SAFE, since we can't touch the linkage once the uth could run */
278         TAILQ_FOREACH_SAFE(i, &restartees, next, safe)
279                 uthread_runnable(i->uth);
280 }
281
282
283 /************** Wrappers for the uthread CV interface **************/
284
285
286 uth_cond_var_t uth_cond_var_alloc(void)
287 {
288         if (sched_ops->cond_var_alloc)
289                 return sched_ops->cond_var_alloc();
290         return (uth_cond_var_t)uth_default_cv_alloc();
291 }
292
293 void uth_cond_var_free(uth_cond_var_t cv)
294 {
295         if (sched_ops->cond_var_free) {
296                 sched_ops->cond_var_free(cv);
297                 return;
298         }
299         uth_default_cv_free((struct uth_default_cv*)cv);
300 }
301
302 void uth_cond_var_wait(uth_cond_var_t cv, uth_mutex_t m)
303 {
304         if (sched_ops->cond_var_wait) {
305                 sched_ops->cond_var_wait(cv, m);
306                 return;
307         }
308         uth_default_cv_wait((struct uth_default_cv*)cv, (struct uth_default_mtx*)m);
309 }
310
311 void uth_cond_var_signal(uth_cond_var_t cv)
312 {
313         if (sched_ops->cond_var_signal) {
314                 sched_ops->cond_var_signal(cv);
315                 return;
316         }
317         uth_default_cv_signal((struct uth_default_cv*)cv);
318 }
319
320 void uth_cond_var_broadcast(uth_cond_var_t cv)
321 {
322         if (sched_ops->cond_var_broadcast) {
323                 sched_ops->cond_var_broadcast(cv);
324                 return;
325         }
326         uth_default_cv_broadcast((struct uth_default_cv*)cv);
327 }