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/coroutine.h"
  31 #include "qemu/coroutine_int.h"
  32 #include "qemu/processor.h"
  33 #include "qemu/queue.h"
  34 #include "block/aio.h"
  35 #include "trace.h"
  36
  37 void qemu_co_queue_init(CoQueue *queue)
  38 {
  39     QSIMPLEQ_INIT(&queue->entries);
  40 }
  41
  42 void coroutine_fn qemu_co_queue_wait_impl(CoQueue *queue, QemuLockable *lock)
  43 {
  44     Coroutine *self = qemu_coroutine_self();
  45     QSIMPLEQ_INSERT_TAIL(&queue->entries, self, co_queue_next);
  46
  47     if (lock) {
  48         qemu_lockable_unlock(lock);
  49     }
  50
  51     /* There is no race condition here.  Other threads will call
  52      * aio_co_schedule on our AioContext, which can reenter this
  53      * coroutine but only after this yield and after the main loop
  54      * has gone through the next iteration.
  55      */
  56     qemu_coroutine_yield();
  57     assert(qemu_in_coroutine());
  58
  59     /* TODO: OSv implements wait morphing here, where the wakeup
  60      * primitive automatically places the woken coroutine on the
  61      * mutex's queue.  This avoids the thundering herd effect.
  62      * This could be implemented for CoMutexes, but not really for
  63      * other cases of QemuLockable.
  64      */
  65     if (lock) {
  66         qemu_lockable_lock(lock);
  67     }
  68 }
  69
  70 void qemu_co_queue_restart_all(CoQueue *queue)
  71 {
  72     Coroutine *next;
  73
  74     if (QSIMPLEQ_EMPTY(&queue->entries)) {
  75         return false;
  76     }
  77
  78     while ((next = QSIMPLEQ_FIRST(&queue->entries)) != NULL) {
  79         QSIMPLEQ_REMOVE_HEAD(&queue->entries, co_queue_next);
  80         aio_co_wake(next);
  81     }
  82     return true;
  83 }
  84
  85 bool qemu_co_enter_next_impl(CoQueue *queue, QemuLockable *lock)
  86 {
  87     Coroutine *next;
  88
  89     next = QSIMPLEQ_FIRST(&queue->entries);
  90     if (!next) {
  91         return false;
  92     }
  93
  94     QSIMPLEQ_REMOVE_HEAD(&queue->entries, co_queue_next);
  95     if (lock) {
  96         qemu_lockable_unlock(lock);
  97     }
  98     aio_co_wake(next);
  99     if (lock) {
 100         qemu_lockable_lock(lock);
 101     }
 102     return true;
 103 }
 104
 105 bool coroutine_fn qemu_co_queue_next(CoQueue *queue)
 106 {
 107     /* No unlock/lock needed in coroutine context.  */
 108     return qemu_co_enter_next_impl(queue, NULL);
 109 }
 110
 111 bool qemu_co_queue_empty(CoQueue *queue)
 112 {
 113     return QSIMPLEQ_FIRST(&queue->entries) == NULL;
 114 }
 115
 116 /* The wait records are handled with a multiple-producer, single-consumer
 117  * lock-free queue.  There cannot be two concurrent pop_waiter() calls
 118  * because pop_waiter() can only be called while mutex->handoff is zero.
 119  * This can happen in three cases:
 120  * - in qemu_co_mutex_unlock, before the hand-off protocol has started.
 121  *   In this case, qemu_co_mutex_lock will see mutex->handoff == 0 and
 122  *   not take part in the handoff.
 123  * - in qemu_co_mutex_lock, if it steals the hand-off responsibility from
 124  *   qemu_co_mutex_unlock.  In this case, qemu_co_mutex_unlock will fail
 125  *   the cmpxchg (it will see either 0 or the next sequence value) and
 126  *   exit.  The next hand-off cannot begin until qemu_co_mutex_lock has
 127  *   woken up someone.
 128  * - in qemu_co_mutex_unlock, if it takes the hand-off token itself.
 129  *   In this case another iteration starts with mutex->handoff == 0;
 130  *   a concurrent qemu_co_mutex_lock will fail the cmpxchg, and
 131  *   qemu_co_mutex_unlock will go back to case (1).
 132  *
 133  * The following functions manage this queue.
 134  */
 135 typedef struct CoWaitRecord {
 136     Coroutine *co;
 137     QSLIST_ENTRY(CoWaitRecord) next;
 138 } CoWaitRecord;
 139
 140 static void push_waiter(CoMutex *mutex, CoWaitRecord *w)
 141 {
 142     w->co = qemu_coroutine_self();
 143     QSLIST_INSERT_HEAD_ATOMIC(&mutex->from_push, w, next);
 144 }
 145
 146 static void move_waiters(CoMutex *mutex)
 147 {
 148     QSLIST_HEAD(, CoWaitRecord) reversed;
 149     QSLIST_MOVE_ATOMIC(&reversed, &mutex->from_push);
 150     while (!QSLIST_EMPTY(&reversed)) {
 151         CoWaitRecord *w = QSLIST_FIRST(&reversed);
 152         QSLIST_REMOVE_HEAD(&reversed, next);
 153         QSLIST_INSERT_HEAD(&mutex->to_pop, w, next);
 154     }
 155 }
 156
 157 static CoWaitRecord *pop_waiter(CoMutex *mutex)
 158 {
 159     CoWaitRecord *w;
 160
 161     if (QSLIST_EMPTY(&mutex->to_pop)) {
 162         move_waiters(mutex);
 163         if (QSLIST_EMPTY(&mutex->to_pop)) {
 164             return NULL;
 165         }
 166     }
 167     w = QSLIST_FIRST(&mutex->to_pop);
 168     QSLIST_REMOVE_HEAD(&mutex->to_pop, next);
 169     return w;
 170 }
 171
 172 static bool has_waiters(CoMutex *mutex)
 173 {
 174     return QSLIST_EMPTY(&mutex->to_pop) || QSLIST_EMPTY(&mutex->from_push);
 175 }
 176
 177 void qemu_co_mutex_init(CoMutex *mutex)
 178 {
 179     memset(mutex, 0, sizeof(*mutex));
 180 }
 181
 182 static void coroutine_fn qemu_co_mutex_wake(CoMutex *mutex, Coroutine *co)
 183 {
 184     /* Read co before co->ctx; pairs with smp_wmb() in
 185      * qemu_coroutine_enter().
 186      */
 187     smp_read_barrier_depends();
 188     mutex->ctx = co->ctx;
 189     aio_co_wake(co);
 190 }
 191
 192 static void coroutine_fn qemu_co_mutex_lock_slowpath(AioContext *ctx,
 193                                                      CoMutex *mutex)
 194 {
 195     Coroutine *self = qemu_coroutine_self();
 196     CoWaitRecord w;
 197     unsigned old_handoff;
 198
 199     trace_qemu_co_mutex_lock_entry(mutex, self);
 200     push_waiter(mutex, &w);
 201
 202     /* This is the "Responsibility Hand-Off" protocol; a lock() picks from
 203      * a concurrent unlock() the responsibility of waking somebody up.
 204      */
 205     old_handoff = qatomic_mb_read(&mutex->handoff);
 206     if (old_handoff &&
 207         has_waiters(mutex) &&
 208         qatomic_cmpxchg(&mutex->handoff, old_handoff, 0) == old_handoff) {
 209         /* There can be no concurrent pops, because there can be only
 210          * one active handoff at a time.
 211          */
 212         CoWaitRecord *to_wake = pop_waiter(mutex);
 213         Coroutine *co = to_wake->co;
 214         if (co == self) {
 215             /* We got the lock ourselves!  */
 216             assert(to_wake == &w);
 217             mutex->ctx = ctx;
 218             return;
 219         }
 220
 221         qemu_co_mutex_wake(mutex, co);
 222     }
 223
 224     qemu_coroutine_yield();
 225     trace_qemu_co_mutex_lock_return(mutex, self);
 226 }
 227
 228 void coroutine_fn qemu_co_mutex_lock(CoMutex *mutex)
 229 {
 230     AioContext *ctx = qemu_get_current_aio_context();
 231     Coroutine *self = qemu_coroutine_self();
 232     int waiters, i;
 233
 234     /* Running a very small critical section on pthread_mutex_t and CoMutex
 235      * shows that pthread_mutex_t is much faster because it doesn't actually
 236      * go to sleep.  What happens is that the critical section is shorter
 237      * than the latency of entering the kernel and thus FUTEX_WAIT always
 238      * fails.  With CoMutex there is no such latency but you still want to
 239      * avoid wait and wakeup.  So introduce it artificially.
 240      */
 241     i = 0;
 242 retry_fast_path:
 243     waiters = qatomic_cmpxchg(&mutex->locked, 0, 1);
 244     if (waiters != 0) {
 245         while (waiters == 1 && ++i < 1000) {
 246             if (qatomic_read(&mutex->ctx) == ctx) {
 247                 break;
 248             }
 249             if (qatomic_read(&mutex->locked) == 0) {
 250                 goto retry_fast_path;
 251             }
 252             cpu_relax();
 253         }
 254         waiters = qatomic_fetch_inc(&mutex->locked);
 255     }
 256
 257     if (waiters == 0) {
 258         /* Uncontended.  */
 259         trace_qemu_co_mutex_lock_uncontended(mutex, self);
 260         mutex->ctx = ctx;
 261     } else {
 262         qemu_co_mutex_lock_slowpath(ctx, mutex);
 263     }
 264     mutex->holder = self;
 265     self->locks_held++;
 266 }
 267
 268 void coroutine_fn qemu_co_mutex_unlock(CoMutex *mutex)
 269 {
 270     Coroutine *self = qemu_coroutine_self();
 271
 272     trace_qemu_co_mutex_unlock_entry(mutex, self);
 273
 274     assert(mutex->locked);
 275     assert(mutex->holder == self);
 276     assert(qemu_in_coroutine());
 277
 278     mutex->ctx = NULL;
 279     mutex->holder = NULL;
 280     self->locks_held--;
 281     if (qatomic_fetch_dec(&mutex->locked) == 1) {
 282         /* No waiting qemu_co_mutex_lock().  Pfew, that was easy!  */
 283         return;
 284     }
 285
 286     for (;;) {
 287         CoWaitRecord *to_wake = pop_waiter(mutex);
 288         unsigned our_handoff;
 289
 290         if (to_wake) {
 291             qemu_co_mutex_wake(mutex, to_wake->co);
 292             break;
 293         }
 294
 295         /* Some concurrent lock() is in progress (we know this because
 296          * mutex->locked was >1) but it hasn't yet put itself on the wait
 297          * queue.  Pick a sequence number for the handoff protocol (not 0).
 298          */
 299         if (++mutex->sequence == 0) {
 300             mutex->sequence = 1;
 301         }
 302
 303         our_handoff = mutex->sequence;
 304         qatomic_mb_set(&mutex->handoff, our_handoff);
 305         if (!has_waiters(mutex)) {
 306             /* The concurrent lock has not added itself yet, so it
 307              * will be able to pick our handoff.
 308              */
 309             break;
 310         }
 311
 312         /* Try to do the handoff protocol ourselves; if somebody else has
 313          * already taken it, however, we're done and they're responsible.
 314          */
 315         if (qatomic_cmpxchg(&mutex->handoff, our_handoff, 0) != our_handoff) {
 316             break;
 317         }
 318     }
 319
 320     trace_qemu_co_mutex_unlock_return(mutex, self);
 321 }
 322
 323 struct CoRwTicket {
 324     bool read;
 325     Coroutine *co;
 326     QSIMPLEQ_ENTRY(CoRwTicket) next;
 327 };
 328
 329 void qemu_co_rwlock_init(CoRwlock *lock)
 330 {
 331     qemu_co_mutex_init(&lock->mutex);
 332     lock->owners = 0;
 333     QSIMPLEQ_INIT(&lock->tickets);
 334 }
 335
 336 /* Releases the internal CoMutex.  */
 337 static void qemu_co_rwlock_maybe_wake_one(CoRwlock *lock)
 338 {
 339     CoRwTicket *tkt = QSIMPLEQ_FIRST(&lock->tickets);
 340     Coroutine *co = NULL;
 341
 342     /*
 343      * Setting lock->owners here prevents rdlock and wrlock from
 344      * sneaking in between unlock and wake.
 345      */
 346
 347     if (tkt) {
 348         if (tkt->read) {
 349             if (lock->owners >= 0) {
 350                 lock->owners++;
 351                 co = tkt->co;
 352             }
 353         } else {
 354             if (lock->owners == 0) {
 355                 lock->owners = -1;
 356                 co = tkt->co;
 357             }
 358         }
 359     }
 360
 361     if (co) {
 362         QSIMPLEQ_REMOVE_HEAD(&lock->tickets, next);
 363         qemu_co_mutex_unlock(&lock->mutex);
 364         aio_co_wake(co);
 365     } else {
 366         qemu_co_mutex_unlock(&lock->mutex);
 367     }
 368 }
 369
 370 void qemu_co_rwlock_rdlock(CoRwlock *lock)
 371 {
 372     Coroutine *self = qemu_coroutine_self();
 373
 374     qemu_co_mutex_lock(&lock->mutex);
 375     /* For fairness, wait if a writer is in line.  */
 376     if (lock->owners == 0 || (lock->owners > 0 && QSIMPLEQ_EMPTY(&lock->tickets))) {
 377         lock->owners++;
 378         qemu_co_mutex_unlock(&lock->mutex);
 379     } else {
 380         CoRwTicket my_ticket = { true, self };
 381
 382         QSIMPLEQ_INSERT_TAIL(&lock->tickets, &my_ticket, next);
 383         qemu_co_mutex_unlock(&lock->mutex);
 384         qemu_coroutine_yield();
 385         assert(lock->owners >= 1);
 386
 387         /* Possibly wake another reader, which will wake the next in line.  */
 388         qemu_co_mutex_lock(&lock->mutex);
 389         qemu_co_rwlock_maybe_wake_one(lock);
 390     }
 391
 392     self->locks_held++;
 393 }
 394
 395 void qemu_co_rwlock_unlock(CoRwlock *lock)
 396 {
 397     Coroutine *self = qemu_coroutine_self();
 398
 399     assert(qemu_in_coroutine());
 400     self->locks_held--;
 401
 402     qemu_co_mutex_lock(&lock->mutex);
 403     if (lock->owners > 0) {
 404         lock->owners--;
 405     } else {
 406         assert(lock->owners == -1);
 407         lock->owners = 0;
 408     }
 409
 410     qemu_co_rwlock_maybe_wake_one(lock);
 411 }
 412
 413 void qemu_co_rwlock_downgrade(CoRwlock *lock)
 414 {
 415     qemu_co_mutex_lock(&lock->mutex);
 416     assert(lock->owners == -1);
 417     lock->owners = 1;
 418
 419     /* Possibly wake another reader, which will wake the next in line.  */
 420     qemu_co_rwlock_maybe_wake_one(lock);
 421 }
 422
 423 void qemu_co_rwlock_wrlock(CoRwlock *lock)
 424 {
 425     Coroutine *self = qemu_coroutine_self();
 426
 427     qemu_co_mutex_lock(&lock->mutex);
 428     if (lock->owners == 0) {
 429         lock->owners = -1;
 430         qemu_co_mutex_unlock(&lock->mutex);
 431     } else {
 432         CoRwTicket my_ticket = { false, qemu_coroutine_self() };
 433
 434         QSIMPLEQ_INSERT_TAIL(&lock->tickets, &my_ticket, next);
 435         qemu_co_mutex_unlock(&lock->mutex);
 436         qemu_coroutine_yield();
 437         assert(lock->owners == -1);
 438     }
 439
 440     self->locks_held++;
 441 }
 442
 443 void qemu_co_rwlock_upgrade(CoRwlock *lock)
 444 {
 445     qemu_co_mutex_lock(&lock->mutex);
 446     assert(lock->owners > 0);
 447     /* For fairness, wait if a writer is in line.  */
 448     if (lock->owners == 1 && QSIMPLEQ_EMPTY(&lock->tickets)) {
 449         lock->owners = -1;
 450         qemu_co_mutex_unlock(&lock->mutex);
 451     } else {
 452         CoRwTicket my_ticket = { false, qemu_coroutine_self() };
 453
 454         lock->owners--;
 455         QSIMPLEQ_INSERT_TAIL(&lock->tickets, &my_ticket, next);
 456         qemu_co_rwlock_maybe_wake_one(lock);
 457         qemu_coroutine_yield();
 458         assert(lock->owners == -1);
 459     }
 460 }