util/qemu-coroutine-lock.c

   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 }