Re: [Qemu-devel] [PATCH 04/10] qemu-thread: optimize QemuLockCnt with futexes on Linux

[Paolo Bonzini]

On 12/01/2017 14:34, Fam Zheng wrote:
>> + */
>> +while ((*val & QEMU_LOCKCNT_STATE_MASK) != QEMU_LOCKCNT_STATE_FREE) {
>> +if ((*val & QEMU_LOCKCNT_STATE_MASK) == QEMU_LOCKCNT_STATE_LOCKED) {
>> +int expected = *val;
>> +int new = expected - QEMU_LOCKCNT_STATE_LOCKED + 
>> QEMU_LOCKCNT_STATE_WAITING;
>> +
>> +trace_lockcnt_futex_wait_prepare(lockcnt, expected, new);
> ... the holder thread releases the lock at this point. In this case a second
> call to this function in qemu_lockcnt_dec_and_lock does pass
> QEMU_LOCKCNT_STATE_LOCKED in new_if_free, because 'waited' is left false 
> there.
> The code is okay, but the comment above is too strict.

Right.

>> +bool qemu_lockcnt_dec_and_lock(QemuLockCnt *lockcnt)
>> +{
>> +int val = atomic_read(>count);
>> +int locked_state = QEMU_LOCKCNT_STATE_LOCKED;
>> +bool waited = false;
>> +
>> +for (;;) {
>> +if (val >= 2 * QEMU_LOCKCNT_COUNT_STEP) {
>> +int expected = val;
>> +int new = val - QEMU_LOCKCNT_COUNT_STEP;
>> +val = atomic_cmpxchg(>count, val, new);
>> +if (val == expected) {
>> +break;
>> +}
> If (val != expected && val >= 2 * QEMU_LOCKCNT_COUNT_STEP), should this
> atomic_cmpxchg be retried before trying qemu_lockcnt_cmpxchg_or_wait?
> 

Yeah, the below can be moved entirely in an "else".

Paolo

Re: [Qemu-devel] [PATCH 04/10] qemu-thread: optimize QemuLockCnt with futexes on Linux

[Fam Zheng]

On Wed, 01/04 14:26, Paolo Bonzini wrote:
> diff --git a/include/qemu/futex.h b/include/qemu/futex.h
> new file mode 100644
> index 000..852d612
> --- /dev/null
> +++ b/include/qemu/futex.h
> @@ -0,0 +1,36 @@
> +/*
> + * Wrappers around Linux futex syscall
> + *
> + * Copyright Red Hat, Inc. 2015

2015 - 2017, too?

> + *
> + * Author:
> + *  Paolo Bonzini 
> + *
> + * This work is licensed under the terms of the GNU GPL, version 2 or later.
> + * See the COPYING file in the top-level directory.
> + *
> + */
> +
> +#include 
> +#include 
> +
> +#define qemu_futex(...)  syscall(__NR_futex, __VA_ARGS__)
> +
> +static inline void qemu_futex_wake(void *f, int n)
> +{
> +qemu_futex(f, FUTEX_WAKE, n, NULL, NULL, 0);
> +}
> +
> +static inline void qemu_futex_wait(void *f, unsigned val)
> +{
> +while (qemu_futex(f, FUTEX_WAIT, (int) val, NULL, NULL, 0)) {
> +switch (errno) {
> +case EWOULDBLOCK:
> +return;
> +case EINTR:
> +break; /* get out of switch and retry */
> +default:
> +abort();
> +}
> +}
> +}
> diff --git a/util/lockcnt.c b/util/lockcnt.c
> index 78ed1e4..40cc02a 100644
> --- a/util/lockcnt.c
> +++ b/util/lockcnt.c
> @@ -9,7 +9,288 @@
>  #include "qemu/osdep.h"
>  #include "qemu/thread.h"
>  #include "qemu/atomic.h"
> +#include "trace.h"
>  
> +#ifdef CONFIG_LINUX
> +#include "qemu/futex.h"
> +
> +/* On Linux, bits 0-1 are a futex-based lock, bits 2-31 are the counter.
> + * For the mutex algorithm see Ulrich Drepper's "Futexes Are Tricky" (ok,
> + * this is not the most relaxing citation I could make...).  It is similar
> + * to mutex2 in the paper.
> + */
> +
> +#define QEMU_LOCKCNT_STATE_MASK3
> +#define QEMU_LOCKCNT_STATE_FREE0
> +#define QEMU_LOCKCNT_STATE_LOCKED  1

I find the macro names a bit incomplete in describing the semantics but maybe
you want to limit the length, making it harder to understand the mutex
implementation without reading the paper. How about adding a comment saying
"locked" is "locked but _not waited_" and "waiting" is "_locked_ and waited"?
It's up to you, because this is trivial compared to the real complexity of this
patch. :)

> +#define QEMU_LOCKCNT_STATE_WAITING 2
> +
> +#define QEMU_LOCKCNT_COUNT_STEP4
> +#define QEMU_LOCKCNT_COUNT_SHIFT   2
> +
> +void qemu_lockcnt_init(QemuLockCnt *lockcnt)
> +{
> +lockcnt->count = 0;
> +}
> +
> +void qemu_lockcnt_destroy(QemuLockCnt *lockcnt)
> +{
> +}
> +
> +/* *val is the current value of lockcnt->count.
> + *
> + * If the lock is free, try a cmpxchg from *val to new_if_free; return
> + * true and set *val to the old value found by the cmpxchg in
> + * lockcnt->count.
> + *
> + * If the lock is taken, wait for it to be released and return false
> + * *without trying again to take the lock*.  Again, set *val to the
> + * new value of lockcnt->count.
> + *
> + * new_if_free's bottom two bits must not be QEMU_LOCKCNT_STATE_LOCKED
> + * if calling this function a second time after it has returned
> + * false.

"and waited"? I think it is possible this function return false with the lock
actually being free, when ...

> + */
> +static bool qemu_lockcnt_cmpxchg_or_wait(QemuLockCnt *lockcnt, int *val,
> + int new_if_free, bool *waited)
> +{
> +/* Fast path for when the lock is free.  */
> +if ((*val & QEMU_LOCKCNT_STATE_MASK) == QEMU_LOCKCNT_STATE_FREE) {
> +int expected = *val;
> +
> +trace_lockcnt_fast_path_attempt(lockcnt, expected, new_if_free);
> +*val = atomic_cmpxchg(>count, expected, new_if_free);
> +if (*val == expected) {
> +trace_lockcnt_fast_path_success(lockcnt, expected, new_if_free);
> +*val = new_if_free;
> +return true;
> +}
> +}
> +
> +/* The slow path moves from locked to waiting if necessary, then
> + * does a futex wait.  Both steps can be repeated ad nauseam,
> + * only getting out of the loop if we can have another shot at the
> + * fast path.  Once we can, get out to compute the new destination
> + * value for the fast path.
> + */
> +while ((*val & QEMU_LOCKCNT_STATE_MASK) != QEMU_LOCKCNT_STATE_FREE) {
> +if ((*val & QEMU_LOCKCNT_STATE_MASK) == QEMU_LOCKCNT_STATE_LOCKED) {
> +int expected = *val;
> +int new = expected - QEMU_LOCKCNT_STATE_LOCKED + 
> QEMU_LOCKCNT_STATE_WAITING;
> +
> +trace_lockcnt_futex_wait_prepare(lockcnt, expected, new);

... the holder thread releases the lock at this point. In this case a second
call to this function in qemu_lockcnt_dec_and_lock does pass
QEMU_LOCKCNT_STATE_LOCKED in new_if_free, because 'waited' is left false there.
The code is okay, but the comment above is too strict.

> +*val = atomic_cmpxchg(>count, expected, new);
> +if (*val == expected) {
> +*val = new;
> +}
> +

Re: [Qemu-devel] [PATCH 04/10] qemu-thread: optimize QemuLockCnt with futexes on Linux

[Paolo Bonzini]

On 11/01/2017 17:50, Stefan Hajnoczi wrote:
> On Wed, Jan 04, 2017 at 02:26:19PM +0100, Paolo Bonzini wrote:
>> +unsigned qemu_lockcnt_count(QemuLockCnt *lockcnt)
>> +{
>> +return lockcnt->count >> QEMU_LOCKCNT_COUNT_SHIFT;
> 
> According to docs/atomics.txt at least atomic_read() should be used here
> otherwise sanitizers could flag up this memory access.

Good point.

Paolo



signature.asc
Description: OpenPGP digital signature

Re: [Qemu-devel] [PATCH 04/10] qemu-thread: optimize QemuLockCnt with futexes on Linux

[Stefan Hajnoczi]

On Wed, Jan 04, 2017 at 02:26:19PM +0100, Paolo Bonzini wrote:
> +unsigned qemu_lockcnt_count(QemuLockCnt *lockcnt)
> +{
> +return lockcnt->count >> QEMU_LOCKCNT_COUNT_SHIFT;

According to docs/atomics.txt at least atomic_read() should be used here
otherwise sanitizers could flag up this memory access.


signature.asc
Description: PGP signature

Re: [Qemu-devel] [PATCH 04/10] qemu-thread: optimize QemuLockCnt with futexes on Linux

[Stefan Hajnoczi]

On Tue, Nov 29, 2016 at 12:47:01PM +0100, Paolo Bonzini wrote:
> diff --git a/include/qemu/futex.h b/include/qemu/futex.h
> new file mode 100644
> index 000..c3d1089
> --- /dev/null
> +++ b/include/qemu/futex.h
> @@ -0,0 +1,36 @@
> +/*
> + * Wrappers around Linux futex syscall
> + *
> + * Copyright Red Hat, Inc. 2015
> + *
> + * Author:
> + *  Paolo Bonzini 
> + *
> + * This work is licensed under the terms of the GNU GPL, version 2 or later.
> + * See the COPYING file in the top-level directory.
> + *
> + */
> +
> +#include 
> +#include 
> +
> +#define futex(...)  syscall(__NR_futex, __VA_ARGS__)
> +
> +static inline void futex_wake(void *f, int n)
> +{
> +futex(f, FUTEX_WAKE, n, NULL, NULL, 0);
> +}
> +
> +static inline void futex_wait(void *f, unsigned val)

Now that this is being promoted to an include/ API please use
qemu_futex(), qemu_futex_wake(), and qemu_futex_wait() names.  It's a
bit bold to use futex(), futex_wake(), and futex_wait().  We're relying
on the fact that no system headers will ever use those names.

I haven't reviewed this patch in detail but:
Acked-by: Stefan Hajnoczi 


signature.asc
Description: PGP signature