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