xref: /openbmc/qemu/util/qemu-coroutine-lock.c (revision 80adf54e)
1 /*
2  * coroutine queues and locks
3  *
4  * Copyright (c) 2011 Kevin Wolf <kwolf@redhat.com>
5  *
6  * Permission is hereby granted, free of charge, to any person obtaining a copy
7  * of this software and associated documentation files (the "Software"), to deal
8  * in the Software without restriction, including without limitation the rights
9  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10  * copies of the Software, and to permit persons to whom the Software is
11  * furnished to do so, subject to the following conditions:
12  *
13  * The above copyright notice and this permission notice shall be included in
14  * all copies or substantial portions of the Software.
15  *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
22  * THE SOFTWARE.
23  *
24  * The lock-free mutex implementation is based on OSv
25  * (core/lfmutex.cc, include/lockfree/mutex.hh).
26  * Copyright (C) 2013 Cloudius Systems, Ltd.
27  */
28 
29 #include "qemu/osdep.h"
30 #include "qemu-common.h"
31 #include "qemu/coroutine.h"
32 #include "qemu/coroutine_int.h"
33 #include "qemu/processor.h"
34 #include "qemu/queue.h"
35 #include "block/aio.h"
36 #include "trace.h"
37 
38 void qemu_co_queue_init(CoQueue *queue)
39 {
40     QSIMPLEQ_INIT(&queue->entries);
41 }
42 
43 void coroutine_fn qemu_co_queue_wait(CoQueue *queue, CoMutex *mutex)
44 {
45     Coroutine *self = qemu_coroutine_self();
46     QSIMPLEQ_INSERT_TAIL(&queue->entries, self, co_queue_next);
47 
48     if (mutex) {
49         qemu_co_mutex_unlock(mutex);
50     }
51 
52     /* There is no race condition here.  Other threads will call
53      * aio_co_schedule on our AioContext, which can reenter this
54      * coroutine but only after this yield and after the main loop
55      * has gone through the next iteration.
56      */
57     qemu_coroutine_yield();
58     assert(qemu_in_coroutine());
59 
60     /* TODO: OSv implements wait morphing here, where the wakeup
61      * primitive automatically places the woken coroutine on the
62      * mutex's queue.  This avoids the thundering herd effect.
63      */
64     if (mutex) {
65         qemu_co_mutex_lock(mutex);
66     }
67 }
68 
69 /**
70  * qemu_co_queue_run_restart:
71  *
72  * Enter each coroutine that was previously marked for restart by
73  * qemu_co_queue_next() or qemu_co_queue_restart_all().  This function is
74  * invoked by the core coroutine code when the current coroutine yields or
75  * terminates.
76  */
77 void qemu_co_queue_run_restart(Coroutine *co)
78 {
79     Coroutine *next;
80     QSIMPLEQ_HEAD(, Coroutine) tmp_queue_wakeup =
81         QSIMPLEQ_HEAD_INITIALIZER(tmp_queue_wakeup);
82 
83     trace_qemu_co_queue_run_restart(co);
84 
85     /* Because "co" has yielded, any coroutine that we wakeup can resume it.
86      * If this happens and "co" terminates, co->co_queue_wakeup becomes
87      * invalid memory.  Therefore, use a temporary queue and do not touch
88      * the "co" coroutine as soon as you enter another one.
89      *
90      * In its turn resumed "co" can pupulate "co_queue_wakeup" queue with
91      * new coroutines to be woken up.  The caller, who has resumed "co",
92      * will be responsible for traversing the same queue, which may cause
93      * a different wakeup order but not any missing wakeups.
94      */
95     QSIMPLEQ_CONCAT(&tmp_queue_wakeup, &co->co_queue_wakeup);
96 
97     while ((next = QSIMPLEQ_FIRST(&tmp_queue_wakeup))) {
98         QSIMPLEQ_REMOVE_HEAD(&tmp_queue_wakeup, co_queue_next);
99         qemu_coroutine_enter(next);
100     }
101 }
102 
103 static bool qemu_co_queue_do_restart(CoQueue *queue, bool single)
104 {
105     Coroutine *next;
106 
107     if (QSIMPLEQ_EMPTY(&queue->entries)) {
108         return false;
109     }
110 
111     while ((next = QSIMPLEQ_FIRST(&queue->entries)) != NULL) {
112         QSIMPLEQ_REMOVE_HEAD(&queue->entries, co_queue_next);
113         aio_co_wake(next);
114         if (single) {
115             break;
116         }
117     }
118     return true;
119 }
120 
121 bool coroutine_fn qemu_co_queue_next(CoQueue *queue)
122 {
123     assert(qemu_in_coroutine());
124     return qemu_co_queue_do_restart(queue, true);
125 }
126 
127 void coroutine_fn qemu_co_queue_restart_all(CoQueue *queue)
128 {
129     assert(qemu_in_coroutine());
130     qemu_co_queue_do_restart(queue, false);
131 }
132 
133 bool qemu_co_enter_next(CoQueue *queue)
134 {
135     Coroutine *next;
136 
137     next = QSIMPLEQ_FIRST(&queue->entries);
138     if (!next) {
139         return false;
140     }
141 
142     QSIMPLEQ_REMOVE_HEAD(&queue->entries, co_queue_next);
143     qemu_coroutine_enter(next);
144     return true;
145 }
146 
147 bool qemu_co_queue_empty(CoQueue *queue)
148 {
149     return QSIMPLEQ_FIRST(&queue->entries) == NULL;
150 }
151 
152 /* The wait records are handled with a multiple-producer, single-consumer
153  * lock-free queue.  There cannot be two concurrent pop_waiter() calls
154  * because pop_waiter() can only be called while mutex->handoff is zero.
155  * This can happen in three cases:
156  * - in qemu_co_mutex_unlock, before the hand-off protocol has started.
157  *   In this case, qemu_co_mutex_lock will see mutex->handoff == 0 and
158  *   not take part in the handoff.
159  * - in qemu_co_mutex_lock, if it steals the hand-off responsibility from
160  *   qemu_co_mutex_unlock.  In this case, qemu_co_mutex_unlock will fail
161  *   the cmpxchg (it will see either 0 or the next sequence value) and
162  *   exit.  The next hand-off cannot begin until qemu_co_mutex_lock has
163  *   woken up someone.
164  * - in qemu_co_mutex_unlock, if it takes the hand-off token itself.
165  *   In this case another iteration starts with mutex->handoff == 0;
166  *   a concurrent qemu_co_mutex_lock will fail the cmpxchg, and
167  *   qemu_co_mutex_unlock will go back to case (1).
168  *
169  * The following functions manage this queue.
170  */
171 typedef struct CoWaitRecord {
172     Coroutine *co;
173     QSLIST_ENTRY(CoWaitRecord) next;
174 } CoWaitRecord;
175 
176 static void push_waiter(CoMutex *mutex, CoWaitRecord *w)
177 {
178     w->co = qemu_coroutine_self();
179     QSLIST_INSERT_HEAD_ATOMIC(&mutex->from_push, w, next);
180 }
181 
182 static void move_waiters(CoMutex *mutex)
183 {
184     QSLIST_HEAD(, CoWaitRecord) reversed;
185     QSLIST_MOVE_ATOMIC(&reversed, &mutex->from_push);
186     while (!QSLIST_EMPTY(&reversed)) {
187         CoWaitRecord *w = QSLIST_FIRST(&reversed);
188         QSLIST_REMOVE_HEAD(&reversed, next);
189         QSLIST_INSERT_HEAD(&mutex->to_pop, w, next);
190     }
191 }
192 
193 static CoWaitRecord *pop_waiter(CoMutex *mutex)
194 {
195     CoWaitRecord *w;
196 
197     if (QSLIST_EMPTY(&mutex->to_pop)) {
198         move_waiters(mutex);
199         if (QSLIST_EMPTY(&mutex->to_pop)) {
200             return NULL;
201         }
202     }
203     w = QSLIST_FIRST(&mutex->to_pop);
204     QSLIST_REMOVE_HEAD(&mutex->to_pop, next);
205     return w;
206 }
207 
208 static bool has_waiters(CoMutex *mutex)
209 {
210     return QSLIST_EMPTY(&mutex->to_pop) || QSLIST_EMPTY(&mutex->from_push);
211 }
212 
213 void qemu_co_mutex_init(CoMutex *mutex)
214 {
215     memset(mutex, 0, sizeof(*mutex));
216 }
217 
218 static void coroutine_fn qemu_co_mutex_wake(CoMutex *mutex, Coroutine *co)
219 {
220     /* Read co before co->ctx; pairs with smp_wmb() in
221      * qemu_coroutine_enter().
222      */
223     smp_read_barrier_depends();
224     mutex->ctx = co->ctx;
225     aio_co_wake(co);
226 }
227 
228 static void coroutine_fn qemu_co_mutex_lock_slowpath(AioContext *ctx,
229                                                      CoMutex *mutex)
230 {
231     Coroutine *self = qemu_coroutine_self();
232     CoWaitRecord w;
233     unsigned old_handoff;
234 
235     trace_qemu_co_mutex_lock_entry(mutex, self);
236     w.co = self;
237     push_waiter(mutex, &w);
238 
239     /* This is the "Responsibility Hand-Off" protocol; a lock() picks from
240      * a concurrent unlock() the responsibility of waking somebody up.
241      */
242     old_handoff = atomic_mb_read(&mutex->handoff);
243     if (old_handoff &&
244         has_waiters(mutex) &&
245         atomic_cmpxchg(&mutex->handoff, old_handoff, 0) == old_handoff) {
246         /* There can be no concurrent pops, because there can be only
247          * one active handoff at a time.
248          */
249         CoWaitRecord *to_wake = pop_waiter(mutex);
250         Coroutine *co = to_wake->co;
251         if (co == self) {
252             /* We got the lock ourselves!  */
253             assert(to_wake == &w);
254             mutex->ctx = ctx;
255             return;
256         }
257 
258         qemu_co_mutex_wake(mutex, co);
259     }
260 
261     qemu_coroutine_yield();
262     trace_qemu_co_mutex_lock_return(mutex, self);
263 }
264 
265 void coroutine_fn qemu_co_mutex_lock(CoMutex *mutex)
266 {
267     AioContext *ctx = qemu_get_current_aio_context();
268     Coroutine *self = qemu_coroutine_self();
269     int waiters, i;
270 
271     /* Running a very small critical section on pthread_mutex_t and CoMutex
272      * shows that pthread_mutex_t is much faster because it doesn't actually
273      * go to sleep.  What happens is that the critical section is shorter
274      * than the latency of entering the kernel and thus FUTEX_WAIT always
275      * fails.  With CoMutex there is no such latency but you still want to
276      * avoid wait and wakeup.  So introduce it artificially.
277      */
278     i = 0;
279 retry_fast_path:
280     waiters = atomic_cmpxchg(&mutex->locked, 0, 1);
281     if (waiters != 0) {
282         while (waiters == 1 && ++i < 1000) {
283             if (atomic_read(&mutex->ctx) == ctx) {
284                 break;
285             }
286             if (atomic_read(&mutex->locked) == 0) {
287                 goto retry_fast_path;
288             }
289             cpu_relax();
290         }
291         waiters = atomic_fetch_inc(&mutex->locked);
292     }
293 
294     if (waiters == 0) {
295         /* Uncontended.  */
296         trace_qemu_co_mutex_lock_uncontended(mutex, self);
297         mutex->ctx = ctx;
298     } else {
299         qemu_co_mutex_lock_slowpath(ctx, mutex);
300     }
301     mutex->holder = self;
302     self->locks_held++;
303 }
304 
305 void coroutine_fn qemu_co_mutex_unlock(CoMutex *mutex)
306 {
307     Coroutine *self = qemu_coroutine_self();
308 
309     trace_qemu_co_mutex_unlock_entry(mutex, self);
310 
311     assert(mutex->locked);
312     assert(mutex->holder == self);
313     assert(qemu_in_coroutine());
314 
315     mutex->ctx = NULL;
316     mutex->holder = NULL;
317     self->locks_held--;
318     if (atomic_fetch_dec(&mutex->locked) == 1) {
319         /* No waiting qemu_co_mutex_lock().  Pfew, that was easy!  */
320         return;
321     }
322 
323     for (;;) {
324         CoWaitRecord *to_wake = pop_waiter(mutex);
325         unsigned our_handoff;
326 
327         if (to_wake) {
328             qemu_co_mutex_wake(mutex, to_wake->co);
329             break;
330         }
331 
332         /* Some concurrent lock() is in progress (we know this because
333          * mutex->locked was >1) but it hasn't yet put itself on the wait
334          * queue.  Pick a sequence number for the handoff protocol (not 0).
335          */
336         if (++mutex->sequence == 0) {
337             mutex->sequence = 1;
338         }
339 
340         our_handoff = mutex->sequence;
341         atomic_mb_set(&mutex->handoff, our_handoff);
342         if (!has_waiters(mutex)) {
343             /* The concurrent lock has not added itself yet, so it
344              * will be able to pick our handoff.
345              */
346             break;
347         }
348 
349         /* Try to do the handoff protocol ourselves; if somebody else has
350          * already taken it, however, we're done and they're responsible.
351          */
352         if (atomic_cmpxchg(&mutex->handoff, our_handoff, 0) != our_handoff) {
353             break;
354         }
355     }
356 
357     trace_qemu_co_mutex_unlock_return(mutex, self);
358 }
359 
360 void qemu_co_rwlock_init(CoRwlock *lock)
361 {
362     memset(lock, 0, sizeof(*lock));
363     qemu_co_queue_init(&lock->queue);
364     qemu_co_mutex_init(&lock->mutex);
365 }
366 
367 void qemu_co_rwlock_rdlock(CoRwlock *lock)
368 {
369     Coroutine *self = qemu_coroutine_self();
370 
371     qemu_co_mutex_lock(&lock->mutex);
372     /* For fairness, wait if a writer is in line.  */
373     while (lock->pending_writer) {
374         qemu_co_queue_wait(&lock->queue, &lock->mutex);
375     }
376     lock->reader++;
377     qemu_co_mutex_unlock(&lock->mutex);
378 
379     /* The rest of the read-side critical section is run without the mutex.  */
380     self->locks_held++;
381 }
382 
383 void qemu_co_rwlock_unlock(CoRwlock *lock)
384 {
385     Coroutine *self = qemu_coroutine_self();
386 
387     assert(qemu_in_coroutine());
388     if (!lock->reader) {
389         /* The critical section started in qemu_co_rwlock_wrlock.  */
390         qemu_co_queue_restart_all(&lock->queue);
391     } else {
392         self->locks_held--;
393 
394         qemu_co_mutex_lock(&lock->mutex);
395         lock->reader--;
396         assert(lock->reader >= 0);
397         /* Wakeup only one waiting writer */
398         if (!lock->reader) {
399             qemu_co_queue_next(&lock->queue);
400         }
401     }
402     qemu_co_mutex_unlock(&lock->mutex);
403 }
404 
405 void qemu_co_rwlock_downgrade(CoRwlock *lock)
406 {
407     Coroutine *self = qemu_coroutine_self();
408 
409     /* lock->mutex critical section started in qemu_co_rwlock_wrlock or
410      * qemu_co_rwlock_upgrade.
411      */
412     assert(lock->reader == 0);
413     lock->reader++;
414     qemu_co_mutex_unlock(&lock->mutex);
415 
416     /* The rest of the read-side critical section is run without the mutex.  */
417     self->locks_held++;
418 }
419 
420 void qemu_co_rwlock_wrlock(CoRwlock *lock)
421 {
422     qemu_co_mutex_lock(&lock->mutex);
423     lock->pending_writer++;
424     while (lock->reader) {
425         qemu_co_queue_wait(&lock->queue, &lock->mutex);
426     }
427     lock->pending_writer--;
428 
429     /* The rest of the write-side critical section is run with
430      * the mutex taken, so that lock->reader remains zero.
431      * There is no need to update self->locks_held.
432      */
433 }
434 
435 void qemu_co_rwlock_upgrade(CoRwlock *lock)
436 {
437     Coroutine *self = qemu_coroutine_self();
438 
439     qemu_co_mutex_lock(&lock->mutex);
440     assert(lock->reader > 0);
441     lock->reader--;
442     lock->pending_writer++;
443     while (lock->reader) {
444         qemu_co_queue_wait(&lock->queue, &lock->mutex);
445     }
446     lock->pending_writer--;
447 
448     /* The rest of the write-side critical section is run with
449      * the mutex taken, similar to qemu_co_rwlock_wrlock.  Do
450      * not account for the lock twice in self->locks_held.
451      */
452     self->locks_held--;
453 }
454