util/lockcnt.c

   1 /*
   2  * QemuLockCnt implementation
   3  *
   4  * Copyright Red Hat, Inc. 2017
   5  *
   6  * Author:
   7  *   Paolo Bonzini <pbonzini@redhat.com>
   8  */
   9 #include "qemu/osdep.h"
  10 #include "qemu/thread.h"
  11 #include "qemu/atomic.h"
  12 #include "trace.h"
  13
  14 #ifdef CONFIG_LINUX
  15 #include "qemu/futex.h"
  16
  17 /* On Linux, bits 0-1 are a futex-based lock, bits 2-31 are the counter.
  18  * For the mutex algorithm see Ulrich Drepper's "Futexes Are Tricky" (ok,
  19  * this is not the most relaxing citation I could make...).  It is similar
  20  * to mutex2 in the paper.
  21  */
  22
  23 #define QEMU_LOCKCNT_STATE_MASK    3
  24 #define QEMU_LOCKCNT_STATE_FREE    0   /* free, uncontended */
  25 #define QEMU_LOCKCNT_STATE_LOCKED  1   /* locked, uncontended */
  26 #define QEMU_LOCKCNT_STATE_WAITING 2   /* locked, contended */
  27
  28 #define QEMU_LOCKCNT_COUNT_STEP    4
  29 #define QEMU_LOCKCNT_COUNT_SHIFT   2
  30
  31 void qemu_lockcnt_init(QemuLockCnt *lockcnt)
  32 {
  33     lockcnt->count = 0;
  34 }
  35
  36 void qemu_lockcnt_destroy(QemuLockCnt *lockcnt)
  37 {
  38 }
  39
  40 /* *val is the current value of lockcnt->count.
  41  *
  42  * If the lock is free, try a cmpxchg from *val to new_if_free; return
  43  * true and set *val to the old value found by the cmpxchg in
  44  * lockcnt->count.
  45  *
  46  * If the lock is taken, wait for it to be released and return false
  47  * *without trying again to take the lock*.  Again, set *val to the
  48  * new value of lockcnt->count.
  49  *
  50  * If *waited is true on return, new_if_free's bottom two bits must not
  51  * be QEMU_LOCKCNT_STATE_LOCKED on subsequent calls, because the caller
  52  * does not know if there are other waiters.  Furthermore, after *waited
  53  * is set the caller has effectively acquired the lock.  If it returns
  54  * with the lock not taken, it must wake another futex waiter.
  55  */
  56 static bool qemu_lockcnt_cmpxchg_or_wait(QemuLockCnt *lockcnt, int *val,
  57                                          int new_if_free, bool *waited)
  58 {
  59     /* Fast path for when the lock is free.  */
  60     if ((*val & QEMU_LOCKCNT_STATE_MASK) == QEMU_LOCKCNT_STATE_FREE) {
  61         int expected = *val;
  62
  63         trace_lockcnt_fast_path_attempt(lockcnt, expected, new_if_free);
  64         *val = atomic_cmpxchg(&lockcnt->count, expected, new_if_free);
  65         if (*val == expected) {
  66             trace_lockcnt_fast_path_success(lockcnt, expected, new_if_free);
  67             *val = new_if_free;
  68             return true;
  69         }
  70     }
  71
  72     /* The slow path moves from locked to waiting if necessary, then
  73      * does a futex wait.  Both steps can be repeated ad nauseam,
  74      * only getting out of the loop if we can have another shot at the
  75      * fast path.  Once we can, get out to compute the new destination
  76      * value for the fast path.
  77      */
  78     while ((*val & QEMU_LOCKCNT_STATE_MASK) != QEMU_LOCKCNT_STATE_FREE) {
  79         if ((*val & QEMU_LOCKCNT_STATE_MASK) == QEMU_LOCKCNT_STATE_LOCKED) {
  80             int expected = *val;
  81             int new = expected - QEMU_LOCKCNT_STATE_LOCKED + QEMU_LOCKCNT_STATE_WAITING;
  82
  83             trace_lockcnt_futex_wait_prepare(lockcnt, expected, new);
  84             *val = atomic_cmpxchg(&lockcnt->count, expected, new);
  85             if (*val == expected) {
  86                 *val = new;
  87             }
  88             continue;
  89         }
  90
  91         if ((*val & QEMU_LOCKCNT_STATE_MASK) == QEMU_LOCKCNT_STATE_WAITING) {
  92             *waited = true;
  93             trace_lockcnt_futex_wait(lockcnt, *val);
  94             qemu_futex_wait(&lockcnt->count, *val);
  95             *val = atomic_read(&lockcnt->count);
  96             trace_lockcnt_futex_wait_resume(lockcnt, *val);
  97             continue;
  98         }
  99
 100         abort();
 101     }
 102     return false;
 103 }
 104
 105 static void lockcnt_wake(QemuLockCnt *lockcnt)
 106 {
 107     trace_lockcnt_futex_wake(lockcnt);
 108     qemu_futex_wake(&lockcnt->count, 1);
 109 }
 110
 111 void qemu_lockcnt_inc(QemuLockCnt *lockcnt)
 112 {
 113     int val = atomic_read(&lockcnt->count);
 114     bool waited = false;
 115
 116     for (;;) {
 117         if (val >= QEMU_LOCKCNT_COUNT_STEP) {
 118             int expected = val;
 119             val = atomic_cmpxchg(&lockcnt->count, val, val + QEMU_LOCKCNT_COUNT_STEP);
 120             if (val == expected) {
 121                 break;
 122             }
 123         } else {
 124             /* The fast path is (0, unlocked)->(1, unlocked).  */
 125             if (qemu_lockcnt_cmpxchg_or_wait(lockcnt, &val, QEMU_LOCKCNT_COUNT_STEP,
 126                                              &waited)) {
 127                 break;
 128             }
 129         }
 130     }
 131
 132     /* If we were woken by another thread, we should also wake one because
 133      * we are effectively releasing the lock that was given to us.  This is
 134      * the case where qemu_lockcnt_lock would leave QEMU_LOCKCNT_STATE_WAITING
 135      * in the low bits, and qemu_lockcnt_inc_and_unlock would find it and
 136      * wake someone.
 137      */
 138     if (waited) {
 139         lockcnt_wake(lockcnt);
 140     }
 141 }
 142
 143 void qemu_lockcnt_dec(QemuLockCnt *lockcnt)
 144 {
 145     atomic_sub(&lockcnt->count, QEMU_LOCKCNT_COUNT_STEP);
 146 }
 147
 148 /* Decrement a counter, and return locked if it is decremented to zero.
 149  * If the function returns true, it is impossible for the counter to
 150  * become nonzero until the next qemu_lockcnt_unlock.
 151  */
 152 bool qemu_lockcnt_dec_and_lock(QemuLockCnt *lockcnt)
 153 {
 154     int val = atomic_read(&lockcnt->count);
 155     int locked_state = QEMU_LOCKCNT_STATE_LOCKED;
 156     bool waited = false;
 157
 158     for (;;) {
 159         if (val >= 2 * QEMU_LOCKCNT_COUNT_STEP) {
 160             int expected = val;
 161             val = atomic_cmpxchg(&lockcnt->count, val, val - QEMU_LOCKCNT_COUNT_STEP);
 162             if (val == expected) {
 163                 break;
 164             }
 165         } else {
 166             /* If count is going 1->0, take the lock. The fast path is
 167              * (1, unlocked)->(0, locked) or (1, unlocked)->(0, waiting).
 168              */
 169             if (qemu_lockcnt_cmpxchg_or_wait(lockcnt, &val, locked_state, &waited)) {
 170                 return true;
 171             }
 172
 173             if (waited) {
 174                 /* At this point we do not know if there are more waiters.  Assume
 175                  * there are.
 176                  */
 177                 locked_state = QEMU_LOCKCNT_STATE_WAITING;
 178             }
 179         }
 180     }
 181
 182     /* If we were woken by another thread, but we're returning in unlocked
 183      * state, we should also wake a thread because we are effectively
 184      * releasing the lock that was given to us.  This is the case where
 185      * qemu_lockcnt_lock would leave QEMU_LOCKCNT_STATE_WAITING in the low
 186      * bits, and qemu_lockcnt_unlock would find it and wake someone.
 187      */
 188     if (waited) {
 189         lockcnt_wake(lockcnt);
 190     }
 191     return false;
 192 }
 193
 194 /* If the counter is one, decrement it and return locked.  Otherwise do
 195  * nothing.
 196  *
 197  * If the function returns true, it is impossible for the counter to
 198  * become nonzero until the next qemu_lockcnt_unlock.
 199  */
 200 bool qemu_lockcnt_dec_if_lock(QemuLockCnt *lockcnt)
 201 {
 202     int val = atomic_read(&lockcnt->count);
 203     int locked_state = QEMU_LOCKCNT_STATE_LOCKED;
 204     bool waited = false;
 205
 206     while (val < 2 * QEMU_LOCKCNT_COUNT_STEP) {
 207         /* If count is going 1->0, take the lock. The fast path is
 208          * (1, unlocked)->(0, locked) or (1, unlocked)->(0, waiting).
 209          */
 210         if (qemu_lockcnt_cmpxchg_or_wait(lockcnt, &val, locked_state, &waited)) {
 211             return true;
 212         }
 213
 214         if (waited) {
 215             /* At this point we do not know if there are more waiters.  Assume
 216              * there are.
 217              */
 218             locked_state = QEMU_LOCKCNT_STATE_WAITING;
 219         }
 220     }
 221
 222     /* If we were woken by another thread, but we're returning in unlocked
 223      * state, we should also wake a thread because we are effectively
 224      * releasing the lock that was given to us.  This is the case where
 225      * qemu_lockcnt_lock would leave QEMU_LOCKCNT_STATE_WAITING in the low
 226      * bits, and qemu_lockcnt_inc_and_unlock would find it and wake someone.
 227      */
 228     if (waited) {
 229         lockcnt_wake(lockcnt);
 230     }
 231     return false;
 232 }
 233
 234 void qemu_lockcnt_lock(QemuLockCnt *lockcnt)
 235 {
 236     int val = atomic_read(&lockcnt->count);
 237     int step = QEMU_LOCKCNT_STATE_LOCKED;
 238     bool waited = false;
 239
 240     /* The third argument is only used if the low bits of val are 0
 241      * (QEMU_LOCKCNT_STATE_FREE), so just blindly mix in the desired
 242      * state.
 243      */
 244     while (!qemu_lockcnt_cmpxchg_or_wait(lockcnt, &val, val + step, &waited)) {
 245         if (waited) {
 246             /* At this point we do not know if there are more waiters.  Assume
 247              * there are.
 248              */
 249             step = QEMU_LOCKCNT_STATE_WAITING;
 250         }
 251     }
 252 }
 253
 254 void qemu_lockcnt_inc_and_unlock(QemuLockCnt *lockcnt)
 255 {
 256     int expected, new, val;
 257
 258     val = atomic_read(&lockcnt->count);
 259     do {
 260         expected = val;
 261         new = (val + QEMU_LOCKCNT_COUNT_STEP) & ~QEMU_LOCKCNT_STATE_MASK;
 262         trace_lockcnt_unlock_attempt(lockcnt, val, new);
 263         val = atomic_cmpxchg(&lockcnt->count, val, new);
 264     } while (val != expected);
 265
 266     trace_lockcnt_unlock_success(lockcnt, val, new);
 267     if (val & QEMU_LOCKCNT_STATE_WAITING) {
 268         lockcnt_wake(lockcnt);
 269     }
 270 }
 271
 272 void qemu_lockcnt_unlock(QemuLockCnt *lockcnt)
 273 {
 274     int expected, new, val;
 275
 276     val = atomic_read(&lockcnt->count);
 277     do {
 278         expected = val;
 279         new = val & ~QEMU_LOCKCNT_STATE_MASK;
 280         trace_lockcnt_unlock_attempt(lockcnt, val, new);
 281         val = atomic_cmpxchg(&lockcnt->count, val, new);
 282     } while (val != expected);
 283
 284     trace_lockcnt_unlock_success(lockcnt, val, new);
 285     if (val & QEMU_LOCKCNT_STATE_WAITING) {
 286         lockcnt_wake(lockcnt);
 287     }
 288 }
 289
 290 unsigned qemu_lockcnt_count(QemuLockCnt *lockcnt)
 291 {
 292     return atomic_read(&lockcnt->count) >> QEMU_LOCKCNT_COUNT_SHIFT;
 293 }
 294 #else
 295 void qemu_lockcnt_init(QemuLockCnt *lockcnt)
 296 {
 297     qemu_mutex_init(&lockcnt->mutex);
 298     lockcnt->count = 0;
 299 }
 300
 301 void qemu_lockcnt_destroy(QemuLockCnt *lockcnt)
 302 {
 303     qemu_mutex_destroy(&lockcnt->mutex);
 304 }
 305
 306 void qemu_lockcnt_inc(QemuLockCnt *lockcnt)
 307 {
 308     int old;
 309     for (;;) {
 310         old = atomic_read(&lockcnt->count);
 311         if (old == 0) {
 312             qemu_lockcnt_lock(lockcnt);
 313             qemu_lockcnt_inc_and_unlock(lockcnt);
 314             return;
 315         } else {
 316             if (atomic_cmpxchg(&lockcnt->count, old, old + 1) == old) {
 317                 return;
 318             }
 319         }
 320     }
 321 }
 322
 323 void qemu_lockcnt_dec(QemuLockCnt *lockcnt)
 324 {
 325     atomic_dec(&lockcnt->count);
 326 }
 327
 328 /* Decrement a counter, and return locked if it is decremented to zero.
 329  * It is impossible for the counter to become nonzero while the mutex
 330  * is taken.
 331  */
 332 bool qemu_lockcnt_dec_and_lock(QemuLockCnt *lockcnt)
 333 {
 334     int val = atomic_read(&lockcnt->count);
 335     while (val > 1) {
 336         int old = atomic_cmpxchg(&lockcnt->count, val, val - 1);
 337         if (old != val) {
 338             val = old;
 339             continue;
 340         }
 341
 342         return false;
 343     }
 344
 345     qemu_lockcnt_lock(lockcnt);
 346     if (atomic_fetch_dec(&lockcnt->count) == 1) {
 347         return true;
 348     }
 349
 350     qemu_lockcnt_unlock(lockcnt);
 351     return false;
 352 }
 353
 354 /* Decrement a counter and return locked if it is decremented to zero.
 355  * Otherwise do nothing.
 356  *
 357  * It is impossible for the counter to become nonzero while the mutex
 358  * is taken.
 359  */
 360 bool qemu_lockcnt_dec_if_lock(QemuLockCnt *lockcnt)
 361 {
 362     /* No need for acquire semantics if we return false.  */
 363     int val = atomic_read(&lockcnt->count);
 364     if (val > 1) {
 365         return false;
 366     }
 367
 368     qemu_lockcnt_lock(lockcnt);
 369     if (atomic_fetch_dec(&lockcnt->count) == 1) {
 370         return true;
 371     }
 372
 373     qemu_lockcnt_inc_and_unlock(lockcnt);
 374     return false;
 375 }
 376
 377 void qemu_lockcnt_lock(QemuLockCnt *lockcnt)
 378 {
 379     qemu_mutex_lock(&lockcnt->mutex);
 380 }
 381
 382 void qemu_lockcnt_inc_and_unlock(QemuLockCnt *lockcnt)
 383 {
 384     atomic_inc(&lockcnt->count);
 385     qemu_mutex_unlock(&lockcnt->mutex);
 386 }
 387
 388 void qemu_lockcnt_unlock(QemuLockCnt *lockcnt)
 389 {
 390     qemu_mutex_unlock(&lockcnt->mutex);
 391 }
 392
 393 unsigned qemu_lockcnt_count(QemuLockCnt *lockcnt)
 394 {
 395     return atomic_read(&lockcnt->count);
 396 }
 397 #endif