[ltt-dev] [PATCH] urcu-qsbr: avoid useless futex wakeups and burning CPU for long grace periods

[Paolo Bonzini]

On 08/09/2011 11:12 PM, Mathieu Desnoyers wrote:
> The reader will see the index->waiting set to 1, reset it to 0, and
> observe a gp_futex that is not -1 (yet, due to reordering of memory
> accesses), thus return immediately.

You're right.  I set gp_futex before index->waiting exactly for this 
reason, but I was confused by the uatomic name in uatomic_set and didn't 
add the memory barrier.

> Please note that I am extremely careful when doing changes to the wakeup
> code, and I went as far as to create a CPU-level promela model to make
> sure the wakeups would never be missed in any allowed memory
> access/instruction execution orders.
>
> So adding complexity to this code path for the sake of accelerating the
> speed of synchronize_rcu(), which is already considered as a slow path,
> does not appear as an immediate win.

It is not accelerating synchronize_rcu().  It does two things:

1) by using futexes, it avoids burning CPU when a grace period is long. 
  It is actually effective even if the grace period is _not_ so long: 
100 walks through the thread list take less than a millisecond, and you 
do not want to call rcu_quiescent_state() that often;

2) once you're always using futexes, if you have frequent quiescent 
states in one thread and more rare quiescent states in another, the 
former thread will uselessly call FUTEX_WAKE on each quiescent state, 
even though it is already in the next grace period.

> But I might be open to a simpler fix that just changes all the
>
> -                     if (wait_loops == RCU_QS_ACTIVE_ATTEMPTS) {
>
> to
>
> +                     if (wait_loops>= RCU_QS_ACTIVE_ATTEMPTS) {
>
> Because it does not alter the gp_futex and memory barriers semantics.
> You could do that change to both urcu-qsbr.c and urcu.c. I would be
> interested if this alone helps performance ?

That doesn't work.  The first read-side thread that calls FUTEX_WAKE 
will set gp_futex to zero, and you will never get a wakeup from a second 
read-side thread.

> If we choose to also alter the gp_futex behavior, we'll definitely have
> to update the Promela model and make sure than can never lead to missed
> wakeups.

Makes sense.  Where are the models?  I attach a patch with the correct 
memory barrier for completeness.

Paolo
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-urcu-qsbr-avoid-useless-futex-wakeups-and-burning-CP.patch
Type: text/x-patch
Size: 3325 bytes
Desc: not available
URL: <http://lists.casi.polymtl.ca/pipermail/lttng-dev/attachments/20110810/6b2e2bd2/attachment-0003.bin>