qemu

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 = qatomic_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 = qatomic_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 = qatomic_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 = qatomic_read(&lockcnt->count);
114
    bool waited = false;
115

116
    for (;;) {
117
        if (val >= QEMU_LOCKCNT_COUNT_STEP) {
118
            int expected = val;
119
            val = qatomic_cmpxchg(&lockcnt->count, val,
120
                                  val + QEMU_LOCKCNT_COUNT_STEP);
121
            if (val == expected) {
122
                break;
123
            }
124
        } else {
125
            /* The fast path is (0, unlocked)->(1, unlocked).  */
126
            if (qemu_lockcnt_cmpxchg_or_wait(lockcnt, &val, QEMU_LOCKCNT_COUNT_STEP,
127
                                             &waited)) {
128
                break;
129
            }
130
        }
131
    }
132

133
    /* If we were woken by another thread, we should also wake one because
134
     * we are effectively releasing the lock that was given to us.  This is
135
     * the case where qemu_lockcnt_lock would leave QEMU_LOCKCNT_STATE_WAITING
136
     * in the low bits, and qemu_lockcnt_inc_and_unlock would find it and
137
     * wake someone.
138
     */
139
    if (waited) {
140
        lockcnt_wake(lockcnt);
141
    }
142
}
143

144
void qemu_lockcnt_dec(QemuLockCnt *lockcnt)
145
{
146
    qatomic_sub(&lockcnt->count, QEMU_LOCKCNT_COUNT_STEP);
147
}
148

149
/* Decrement a counter, and return locked if it is decremented to zero.
150
 * If the function returns true, it is impossible for the counter to
151
 * become nonzero until the next qemu_lockcnt_unlock.
152
 */
153
bool qemu_lockcnt_dec_and_lock(QemuLockCnt *lockcnt)
154
{
155
    int val = qatomic_read(&lockcnt->count);
156
    int locked_state = QEMU_LOCKCNT_STATE_LOCKED;
157
    bool waited = false;
158

159
    for (;;) {
160
        if (val >= 2 * QEMU_LOCKCNT_COUNT_STEP) {
161
            int expected = val;
162
            val = qatomic_cmpxchg(&lockcnt->count, val,
163
                                  val - QEMU_LOCKCNT_COUNT_STEP);
164
            if (val == expected) {
165
                break;
166
            }
167
        } else {
168
            /* If count is going 1->0, take the lock. The fast path is
169
             * (1, unlocked)->(0, locked) or (1, unlocked)->(0, waiting).
170
             */
171
            if (qemu_lockcnt_cmpxchg_or_wait(lockcnt, &val, locked_state, &waited)) {
172
                return true;
173
            }
174

175
            if (waited) {
176
                /* At this point we do not know if there are more waiters.  Assume
177
                 * there are.
178
                 */
179
                locked_state = QEMU_LOCKCNT_STATE_WAITING;
180
            }
181
        }
182
    }
183

184
    /* If we were woken by another thread, but we're returning in unlocked
185
     * state, we should also wake a thread because we are effectively
186
     * releasing the lock that was given to us.  This is the case where
187
     * qemu_lockcnt_lock would leave QEMU_LOCKCNT_STATE_WAITING in the low
188
     * bits, and qemu_lockcnt_unlock would find it and wake someone.
189
     */
190
    if (waited) {
191
        lockcnt_wake(lockcnt);
192
    }
193
    return false;
194
}
195

196
/* If the counter is one, decrement it and return locked.  Otherwise do
197
 * nothing.
198
 *
199
 * If the function returns true, it is impossible for the counter to
200
 * become nonzero until the next qemu_lockcnt_unlock.
201
 */
202
bool qemu_lockcnt_dec_if_lock(QemuLockCnt *lockcnt)
203
{
204
    int val = qatomic_read(&lockcnt->count);
205
    int locked_state = QEMU_LOCKCNT_STATE_LOCKED;
206
    bool waited = false;
207

208
    while (val < 2 * QEMU_LOCKCNT_COUNT_STEP) {
209
        /* If count is going 1->0, take the lock. The fast path is
210
         * (1, unlocked)->(0, locked) or (1, unlocked)->(0, waiting).
211
         */
212
        if (qemu_lockcnt_cmpxchg_or_wait(lockcnt, &val, locked_state, &waited)) {
213
            return true;
214
        }
215

216
        if (waited) {
217
            /* At this point we do not know if there are more waiters.  Assume
218
             * there are.
219
             */
220
            locked_state = QEMU_LOCKCNT_STATE_WAITING;
221
        }
222
    }
223

224
    /* If we were woken by another thread, but we're returning in unlocked
225
     * state, we should also wake a thread because we are effectively
226
     * releasing the lock that was given to us.  This is the case where
227
     * qemu_lockcnt_lock would leave QEMU_LOCKCNT_STATE_WAITING in the low
228
     * bits, and qemu_lockcnt_inc_and_unlock would find it and wake someone.
229
     */
230
    if (waited) {
231
        lockcnt_wake(lockcnt);
232
    }
233
    return false;
234
}
235

236
void qemu_lockcnt_lock(QemuLockCnt *lockcnt)
237
{
238
    int val = qatomic_read(&lockcnt->count);
239
    int step = QEMU_LOCKCNT_STATE_LOCKED;
240
    bool waited = false;
241

242
    /* The third argument is only used if the low bits of val are 0
243
     * (QEMU_LOCKCNT_STATE_FREE), so just blindly mix in the desired
244
     * state.
245
     */
246
    while (!qemu_lockcnt_cmpxchg_or_wait(lockcnt, &val, val + step, &waited)) {
247
        if (waited) {
248
            /* At this point we do not know if there are more waiters.  Assume
249
             * there are.
250
             */
251
            step = QEMU_LOCKCNT_STATE_WAITING;
252
        }
253
    }
254
}
255

256
void qemu_lockcnt_inc_and_unlock(QemuLockCnt *lockcnt)
257
{
258
    int expected, new, val;
259

260
    val = qatomic_read(&lockcnt->count);
261
    do {
262
        expected = val;
263
        new = (val + QEMU_LOCKCNT_COUNT_STEP) & ~QEMU_LOCKCNT_STATE_MASK;
264
        trace_lockcnt_unlock_attempt(lockcnt, val, new);
265
        val = qatomic_cmpxchg(&lockcnt->count, val, new);
266
    } while (val != expected);
267

268
    trace_lockcnt_unlock_success(lockcnt, val, new);
269
    if (val & QEMU_LOCKCNT_STATE_WAITING) {
270
        lockcnt_wake(lockcnt);
271
    }
272
}
273

274
void qemu_lockcnt_unlock(QemuLockCnt *lockcnt)
275
{
276
    int expected, new, val;
277

278
    val = qatomic_read(&lockcnt->count);
279
    do {
280
        expected = val;
281
        new = val & ~QEMU_LOCKCNT_STATE_MASK;
282
        trace_lockcnt_unlock_attempt(lockcnt, val, new);
283
        val = qatomic_cmpxchg(&lockcnt->count, val, new);
284
    } while (val != expected);
285

286
    trace_lockcnt_unlock_success(lockcnt, val, new);
287
    if (val & QEMU_LOCKCNT_STATE_WAITING) {
288
        lockcnt_wake(lockcnt);
289
    }
290
}
291

292
unsigned qemu_lockcnt_count(QemuLockCnt *lockcnt)
293
{
294
    return qatomic_read(&lockcnt->count) >> QEMU_LOCKCNT_COUNT_SHIFT;
295
}
296
#else
297
void qemu_lockcnt_init(QemuLockCnt *lockcnt)
298
{
299
    qemu_mutex_init(&lockcnt->mutex);
300
    lockcnt->count = 0;
301
}
302

303
void qemu_lockcnt_destroy(QemuLockCnt *lockcnt)
304
{
305
    qemu_mutex_destroy(&lockcnt->mutex);
306
}
307

308
void qemu_lockcnt_inc(QemuLockCnt *lockcnt)
309
{
310
    int old;
311
    for (;;) {
312
        old = qatomic_read(&lockcnt->count);
313
        if (old == 0) {
314
            qemu_lockcnt_lock(lockcnt);
315
            qemu_lockcnt_inc_and_unlock(lockcnt);
316
            return;
317
        } else {
318
            if (qatomic_cmpxchg(&lockcnt->count, old, old + 1) == old) {
319
                return;
320
            }
321
        }
322
    }
323
}
324

325
void qemu_lockcnt_dec(QemuLockCnt *lockcnt)
326
{
327
    qatomic_dec(&lockcnt->count);
328
}
329

330
/* Decrement a counter, and return locked if it is decremented to zero.
331
 * It is impossible for the counter to become nonzero while the mutex
332
 * is taken.
333
 */
334
bool qemu_lockcnt_dec_and_lock(QemuLockCnt *lockcnt)
335
{
336
    int val = qatomic_read(&lockcnt->count);
337
    while (val > 1) {
338
        int old = qatomic_cmpxchg(&lockcnt->count, val, val - 1);
339
        if (old != val) {
340
            val = old;
341
            continue;
342
        }
343

344
        return false;
345
    }
346

347
    qemu_lockcnt_lock(lockcnt);
348
    if (qatomic_fetch_dec(&lockcnt->count) == 1) {
349
        return true;
350
    }
351

352
    qemu_lockcnt_unlock(lockcnt);
353
    return false;
354
}
355

356
/* Decrement a counter and return locked if it is decremented to zero.
357
 * Otherwise do nothing.
358
 *
359
 * It is impossible for the counter to become nonzero while the mutex
360
 * is taken.
361
 */
362
bool qemu_lockcnt_dec_if_lock(QemuLockCnt *lockcnt)
363
{
364
    /* No need for acquire semantics if we return false.  */
365
    int val = qatomic_read(&lockcnt->count);
366
    if (val > 1) {
367
        return false;
368
    }
369

370
    qemu_lockcnt_lock(lockcnt);
371
    if (qatomic_fetch_dec(&lockcnt->count) == 1) {
372
        return true;
373
    }
374

375
    qemu_lockcnt_inc_and_unlock(lockcnt);
376
    return false;
377
}
378

379
void qemu_lockcnt_lock(QemuLockCnt *lockcnt)
380
{
381
    qemu_mutex_lock(&lockcnt->mutex);
382
}
383

384
void qemu_lockcnt_inc_and_unlock(QemuLockCnt *lockcnt)
385
{
386
    qatomic_inc(&lockcnt->count);
387
    qemu_mutex_unlock(&lockcnt->mutex);
388
}
389

390
void qemu_lockcnt_unlock(QemuLockCnt *lockcnt)
391
{
392
    qemu_mutex_unlock(&lockcnt->mutex);
393
}
394

395
unsigned qemu_lockcnt_count(QemuLockCnt *lockcnt)
396
{
397
    return qatomic_read(&lockcnt->count);
398
}
399
#endif
400