target-microblaze: Introduce a use-pcmp-instr property
[qemu/ar7.git] / util / qemu-coroutine-lock.c
blobb44b5d55ebad8b8b6c4b8d7e41030ae527308c45
1 /*
2 * coroutine queues and locks
4 * Copyright (c) 2011 Kevin Wolf <kwolf@redhat.com>
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:
13 * The above copyright notice and this permission notice shall be included in
14 * all copies or substantial portions of the Software.
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.
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.
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"
38 void qemu_co_queue_init(CoQueue *queue)
40 QSIMPLEQ_INIT(&queue->entries);
43 void coroutine_fn qemu_co_queue_wait(CoQueue *queue, CoMutex *mutex)
45 Coroutine *self = qemu_coroutine_self();
46 QSIMPLEQ_INSERT_TAIL(&queue->entries, self, co_queue_next);
48 if (mutex) {
49 qemu_co_mutex_unlock(mutex);
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.
57 qemu_coroutine_yield();
58 assert(qemu_in_coroutine());
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.
64 if (mutex) {
65 qemu_co_mutex_lock(mutex);
69 /**
70 * qemu_co_queue_run_restart:
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.
77 void qemu_co_queue_run_restart(Coroutine *co)
79 Coroutine *next;
80 QSIMPLEQ_HEAD(, Coroutine) tmp_queue_wakeup =
81 QSIMPLEQ_HEAD_INITIALIZER(tmp_queue_wakeup);
83 trace_qemu_co_queue_run_restart(co);
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.
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.
95 QSIMPLEQ_CONCAT(&tmp_queue_wakeup, &co->co_queue_wakeup);
97 while ((next = QSIMPLEQ_FIRST(&tmp_queue_wakeup))) {
98 QSIMPLEQ_REMOVE_HEAD(&tmp_queue_wakeup, co_queue_next);
99 qemu_coroutine_enter(next);
103 static bool qemu_co_queue_do_restart(CoQueue *queue, bool single)
105 Coroutine *next;
107 if (QSIMPLEQ_EMPTY(&queue->entries)) {
108 return false;
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;
118 return true;
121 bool coroutine_fn qemu_co_queue_next(CoQueue *queue)
123 assert(qemu_in_coroutine());
124 return qemu_co_queue_do_restart(queue, true);
127 void coroutine_fn qemu_co_queue_restart_all(CoQueue *queue)
129 assert(qemu_in_coroutine());
130 qemu_co_queue_do_restart(queue, false);
133 bool qemu_co_enter_next(CoQueue *queue)
135 Coroutine *next;
137 next = QSIMPLEQ_FIRST(&queue->entries);
138 if (!next) {
139 return false;
142 QSIMPLEQ_REMOVE_HEAD(&queue->entries, co_queue_next);
143 qemu_coroutine_enter(next);
144 return true;
147 bool qemu_co_queue_empty(CoQueue *queue)
149 return QSIMPLEQ_FIRST(&queue->entries) == NULL;
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).
169 * The following functions manage this queue.
171 typedef struct CoWaitRecord {
172 Coroutine *co;
173 QSLIST_ENTRY(CoWaitRecord) next;
174 } CoWaitRecord;
176 static void push_waiter(CoMutex *mutex, CoWaitRecord *w)
178 w->co = qemu_coroutine_self();
179 QSLIST_INSERT_HEAD_ATOMIC(&mutex->from_push, w, next);
182 static void move_waiters(CoMutex *mutex)
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);
193 static CoWaitRecord *pop_waiter(CoMutex *mutex)
195 CoWaitRecord *w;
197 if (QSLIST_EMPTY(&mutex->to_pop)) {
198 move_waiters(mutex);
199 if (QSLIST_EMPTY(&mutex->to_pop)) {
200 return NULL;
203 w = QSLIST_FIRST(&mutex->to_pop);
204 QSLIST_REMOVE_HEAD(&mutex->to_pop, next);
205 return w;
208 static bool has_waiters(CoMutex *mutex)
210 return QSLIST_EMPTY(&mutex->to_pop) || QSLIST_EMPTY(&mutex->from_push);
213 void qemu_co_mutex_init(CoMutex *mutex)
215 memset(mutex, 0, sizeof(*mutex));
218 static void coroutine_fn qemu_co_mutex_wake(CoMutex *mutex, Coroutine *co)
220 /* Read co before co->ctx; pairs with smp_wmb() in
221 * qemu_coroutine_enter().
223 smp_read_barrier_depends();
224 mutex->ctx = co->ctx;
225 aio_co_wake(co);
228 static void coroutine_fn qemu_co_mutex_lock_slowpath(AioContext *ctx,
229 CoMutex *mutex)
231 Coroutine *self = qemu_coroutine_self();
232 CoWaitRecord w;
233 unsigned old_handoff;
235 trace_qemu_co_mutex_lock_entry(mutex, self);
236 w.co = self;
237 push_waiter(mutex, &w);
239 /* This is the "Responsibility Hand-Off" protocol; a lock() picks from
240 * a concurrent unlock() the responsibility of waking somebody up.
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.
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;
258 qemu_co_mutex_wake(mutex, co);
261 qemu_coroutine_yield();
262 trace_qemu_co_mutex_lock_return(mutex, self);
265 void coroutine_fn qemu_co_mutex_lock(CoMutex *mutex)
267 AioContext *ctx = qemu_get_current_aio_context();
268 Coroutine *self = qemu_coroutine_self();
269 int waiters, i;
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.
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;
286 if (atomic_read(&mutex->locked) == 0) {
287 goto retry_fast_path;
289 cpu_relax();
291 waiters = atomic_fetch_inc(&mutex->locked);
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);
301 mutex->holder = self;
302 self->locks_held++;
305 void coroutine_fn qemu_co_mutex_unlock(CoMutex *mutex)
307 Coroutine *self = qemu_coroutine_self();
309 trace_qemu_co_mutex_unlock_entry(mutex, self);
311 assert(mutex->locked);
312 assert(mutex->holder == self);
313 assert(qemu_in_coroutine());
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;
323 for (;;) {
324 CoWaitRecord *to_wake = pop_waiter(mutex);
325 unsigned our_handoff;
327 if (to_wake) {
328 qemu_co_mutex_wake(mutex, to_wake->co);
329 break;
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).
336 if (++mutex->sequence == 0) {
337 mutex->sequence = 1;
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.
346 break;
349 /* Try to do the handoff protocol ourselves; if somebody else has
350 * already taken it, however, we're done and they're responsible.
352 if (atomic_cmpxchg(&mutex->handoff, our_handoff, 0) != our_handoff) {
353 break;
357 trace_qemu_co_mutex_unlock_return(mutex, self);
360 void qemu_co_rwlock_init(CoRwlock *lock)
362 memset(lock, 0, sizeof(*lock));
363 qemu_co_queue_init(&lock->queue);
364 qemu_co_mutex_init(&lock->mutex);
367 void qemu_co_rwlock_rdlock(CoRwlock *lock)
369 Coroutine *self = qemu_coroutine_self();
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);
376 lock->reader++;
377 qemu_co_mutex_unlock(&lock->mutex);
379 /* The rest of the read-side critical section is run without the mutex. */
380 self->locks_held++;
383 void qemu_co_rwlock_unlock(CoRwlock *lock)
385 Coroutine *self = qemu_coroutine_self();
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--;
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);
402 qemu_co_mutex_unlock(&lock->mutex);
405 void qemu_co_rwlock_wrlock(CoRwlock *lock)
407 qemu_co_mutex_lock(&lock->mutex);
408 lock->pending_writer++;
409 while (lock->reader) {
410 qemu_co_queue_wait(&lock->queue, &lock->mutex);
412 lock->pending_writer--;
414 /* The rest of the write-side critical section is run with
415 * the mutex taken, so that lock->reader remains zero.
416 * There is no need to update self->locks_held.