[ltt-dev] [URCU RFC patch 0/3] call_rcu() performance improvements

[ltt-dev] [URCU RFC patch 0/3] call_rcu() performance improvements

[Mathieu Desnoyers]

Hi,

I did some benchmarking on the rbtree2 branch (on my rcu red black tree
implementation) and figured out some very important slowdown that were
due to the current call_rcu implementation. This patch series digs
through the problems I noticed and explains the solution. The three main
problems were:

- Lack of per-cpu affinity for per-cpu call_rcu threads.
- Use of pthread_cond, which requires a mutex, at each call_rcu
  execution to signal the call_rcu thread (heavy mutex contention).
- More delay than necessary between executions of the call_rcu thread in
  the wakeup-based scenario increased the cache footprint.

I'm proposing these patches as RFC. If you think they are acceptable,
I'll pull them into the liburcu mainline.

Comments are welcome,

Thanks,

Mathieu

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] [URCU RFC patch 1/3] call_rcu: use cpu affinity for per-cpu call_rcu threads

[Mathieu Desnoyers]

An embedded and charset-unspecified text was scrubbed...
Name: cpu_affinity_for_call_rcu.patch
URL: <http://lists.casi.polymtl.ca/pipermail/ltt-dev/attachments/20110606/c4b2512f/attachment.txt>

[ltt-dev] [URCU RFC patch 1/3] call_rcu: use cpu affinity for per-cpu call_rcu threads

[Mathieu Desnoyers]

An embedded and charset-unspecified text was scrubbed...
Name: cpu_affinity_for_call_rcu.patch
URL: <http://lists.casi.polymtl.ca/pipermail/lttng-dev/attachments/20110606/c4b2512f/attachment-0001.asc>

[ltt-dev] [URCU RFC patch 1/3] call_rcu: use cpu affinity for per-cpu call_rcu threads

[Mathieu Desnoyers]

An embedded and charset-unspecified text was scrubbed...
Name: cpu_affinity_for_call_rcu.patch
URL: <http://lists.casi.polymtl.ca/pipermail/lttng-dev/attachments/20110606/c4b2512f/attachment.asc>

[ltt-dev] [URCU RFC patch 2/3] call_rcu: use futex for wakeup scheme

[Mathieu Desnoyers]

An embedded and charset-unspecified text was scrubbed...
Name: call-rcu-use-futex.patch
URL: <http://lists.casi.polymtl.ca/pipermail/ltt-dev/attachments/20110606/f3ad99c7/attachment.asc>

[ltt-dev] [URCU RFC patch 2/3] call_rcu: use futex for wakeup scheme

[Mathieu Desnoyers]

An embedded and charset-unspecified text was scrubbed...
Name: call-rcu-use-futex.patch
URL: <http://lists.casi.polymtl.ca/pipermail/lttng-dev/attachments/20110606/f3ad99c7/attachment-0001.txt>

[ltt-dev] [URCU RFC patch 2/3] call_rcu: use futex for wakeup scheme

[Mathieu Desnoyers]

An embedded and charset-unspecified text was scrubbed...
Name: call-rcu-use-futex.patch
URL: <http://lists.casi.polymtl.ca/pipermail/lttng-dev/attachments/20110606/f3ad99c7/attachment.txt>

[ltt-dev] [URCU RFC patch 3/3] call_rcu: remove delay for wakeup scheme

[Mathieu Desnoyers]

An embedded and charset-unspecified text was scrubbed...
Name: call-rcu-remove-delay.patch
URL: <http://lists.casi.polymtl.ca/pipermail/lttng-dev/attachments/20110606/ed7605cb/attachment.txt>

[ltt-dev] [URCU RFC patch 3/3] call_rcu: remove delay for wakeup scheme

[Mathieu Desnoyers]

An embedded and charset-unspecified text was scrubbed...
Name: call-rcu-remove-delay.patch
URL: <http://lists.casi.polymtl.ca/pipermail/lttng-dev/attachments/20110606/ed7605cb/attachment-0001.txt>

[ltt-dev] [URCU RFC patch 3/3] call_rcu: remove delay for wakeup scheme

[Mathieu Desnoyers]

An embedded and charset-unspecified text was scrubbed...
Name: call-rcu-remove-delay.patch
URL: <http://lists.casi.polymtl.ca/pipermail/ltt-dev/attachments/20110606/ed7605cb/attachment.asc>

[ltt-dev] [URCU RFC patch 3/3] call_rcu: remove delay for wakeup scheme

[Mathieu Desnoyers]

* Mathieu Desnoyers (mathieu.desnoyers at efficios.com) wrote:
> I notice that the "poll(NULL, 0, 10);" delay is executed both for the RT
> and non-RT code.  So given that my goal is to get the call_rcu thread to
> GC memory as quickly as possible to diminish the overhead of cache
> misses, I decided to try removing this delay for !RT: the call_rcu
> thread then wakes up ASAP when the thread invoking call_rcu wakes it. My
> updates jump to 76349/s (getting there!) ;).
> 
> This improvement can be explained by a lower delay between call_rcu and
> execution of its callback, which decrease the amount of cache used, and
> therefore provides better cache locality.

I just wonder if it's worth it: removing this delay from the !RT
call_rcu thread can cause high-rate of synchronize_rcu() calls. So
although there might be an advantage in terms of update rate, it will
likely cause extra cache-line bounces between the call_rcu threads and
the reader threads.

test_urcu_rbtree 7 1 20 -g 1000000

With the delay in the call_rcu thread:
search:  1842857 items/reader thread/s (7 reader threads)
updates:   21066 items/s (1 update thread)
ratio: 87 search/update

Without the delay in the call_rcu thread:
search:  3064285 items/reader thread/s (7 reader threads)
updates:   45096 items/s (1 update thread)
ratio: 68 search/update

So basically, adding the delay doubles the update performance, at the
cost of being 33% slower for reads. My first thought is that if an
application has very frequent updates, then maybe it wants to have fast
updates because the update throughput is then important. If the
application has infrequent updates, then the reads will be fast anyway,
because rare call_rcu invocation will trigger less cache-line bounce
between readers and writers. Any other thoughts on this trade-off and
how to deal with it ?

Thanks,

Mathieu


> 
> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> ---
>  urcu-call-rcu-impl.h |    3 ++-
>  1 file changed, 2 insertions(+), 1 deletion(-)
> 
> Index: userspace-rcu/urcu-call-rcu-impl.h
> ===================================================================
> --- userspace-rcu.orig/urcu-call-rcu-impl.h
> +++ userspace-rcu/urcu-call-rcu-impl.h
> @@ -242,7 +242,8 @@ static void *call_rcu_thread(void *arg)
>  		else {
>  			if (&crdp->cbs.head == _CMM_LOAD_SHARED(crdp->cbs.tail))
>  				call_rcu_wait(crdp);
> -			poll(NULL, 0, 10);
> +			else
> +				poll(NULL, 0, 10);
>  		}
>  	}
>  	call_rcu_lock(&crdp->mtx);
> 

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] [URCU RFC patch 3/3] call_rcu: remove delay for wakeup scheme

[Paul E. McKenney]

On Mon, Jun 06, 2011 at 03:21:07PM -0400, Mathieu Desnoyers wrote:
> * Mathieu Desnoyers (mathieu.desnoyers at efficios.com) wrote:
> > I notice that the "poll(NULL, 0, 10);" delay is executed both for the RT
> > and non-RT code.  So given that my goal is to get the call_rcu thread to
> > GC memory as quickly as possible to diminish the overhead of cache
> > misses, I decided to try removing this delay for !RT: the call_rcu
> > thread then wakes up ASAP when the thread invoking call_rcu wakes it. My
> > updates jump to 76349/s (getting there!) ;).
> > 
> > This improvement can be explained by a lower delay between call_rcu and
> > execution of its callback, which decrease the amount of cache used, and
> > therefore provides better cache locality.
> 
> I just wonder if it's worth it: removing this delay from the !RT
> call_rcu thread can cause high-rate of synchronize_rcu() calls. So
> although there might be an advantage in terms of update rate, it will
> likely cause extra cache-line bounces between the call_rcu threads and
> the reader threads.
> 
> test_urcu_rbtree 7 1 20 -g 1000000
> 
> With the delay in the call_rcu thread:
> search:  1842857 items/reader thread/s (7 reader threads)
> updates:   21066 items/s (1 update thread)
> ratio: 87 search/update
> 
> Without the delay in the call_rcu thread:
> search:  3064285 items/reader thread/s (7 reader threads)
> updates:   45096 items/s (1 update thread)
> ratio: 68 search/update
> 
> So basically, adding the delay doubles the update performance, at the
> cost of being 33% slower for reads. My first thought is that if an
> application has very frequent updates, then maybe it wants to have fast
> updates because the update throughput is then important. If the
> application has infrequent updates, then the reads will be fast anyway,
> because rare call_rcu invocation will trigger less cache-line bounce
> between readers and writers. Any other thoughts on this trade-off and
> how to deal with it ?

One approach would be to let the user handle it using real-time
priority adjustment.  Another approach would be to let the user
specify the wait time in milliseconds, and skip the poll() system
call if the specified wait time is zero.

The latter seems more sane to me.  It also allows the user to
specify (say) 10000 milliseconds for cases where there is a
lot of memory and where amortizing synchronize_rcu() overhead
across a large number of updates is important.

Other thoughts?

						Thanx, Paul

> Thanks,
> 
> Mathieu
> 
> 
> > 
> > Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> > ---
> >  urcu-call-rcu-impl.h |    3 ++-
> >  1 file changed, 2 insertions(+), 1 deletion(-)
> > 
> > Index: userspace-rcu/urcu-call-rcu-impl.h
> > ===================================================================
> > --- userspace-rcu.orig/urcu-call-rcu-impl.h
> > +++ userspace-rcu/urcu-call-rcu-impl.h
> > @@ -242,7 +242,8 @@ static void *call_rcu_thread(void *arg)
> >  		else {
> >  			if (&crdp->cbs.head == _CMM_LOAD_SHARED(crdp->cbs.tail))
> >  				call_rcu_wait(crdp);
> > -			poll(NULL, 0, 10);
> > +			else
> > +				poll(NULL, 0, 10);
> >  		}
> >  	}
> >  	call_rcu_lock(&crdp->mtx);
> > 
> 
> -- 
> Mathieu Desnoyers
> Operating System Efficiency R&D Consultant
> EfficiOS Inc.
> http://www.efficios.com

[ltt-dev] [URCU RFC patch 1/3] call_rcu: use cpu affinity for per-cpu call_rcu threads

[Paul E. McKenney]

On Mon, Jun 06, 2011 at 01:45:59PM -0400, Mathieu Desnoyers wrote:
> I played a bit with the call_rcu() implementation alongside with my
> rbtree tests, and noticed the following:
> 
> If I use per-cpu call_rcu threads with URCU_CALL_RCU_RT flag, with one
> updater thread only for my rbtree (no reader), I get 38365 updates/s.
> If I add cpu affinity to these per-cpu call_rcu threads (I have prepared
> a patch that does this), it jumps to 54219 updates/s.  So it looks like
> keeping per-cpu affinity for the call_rcu thread is a good thing.

Makes sense to me!

Main comment is that API.h should also be updated.

							Thanx, Paul

> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> ---
>  API.txt              |    7 +++++--
>  tests/rcutorture.h   |    4 ++--
>  urcu-call-rcu-impl.h |   51 ++++++++++++++++++++++++++++++++++++++++++++-------
>  urcu-call-rcu.h      |    3 ++-
>  urcu-qsbr.c          |    1 +
>  urcu.c               |    1 +
>  6 files changed, 55 insertions(+), 12 deletions(-)
> 
> Index: userspace-rcu/API.txt
> ===================================================================
> --- userspace-rcu.orig/API.txt
> +++ userspace-rcu/API.txt
> @@ -59,12 +59,15 @@ void call_rcu(struct rcu_head *head,
> 
>  		call_rcu(&p->rcu, func);
> 
> -struct call_rcu_data *create_call_rcu_data(unsigned long flags);
> +struct call_rcu_data *create_call_rcu_data(unsigned long flags,
> +					   int cpu_affinity);
> 
>  	Returns a handle that can be passed to the following
>  	primitives.  The "flags" argument can be zero, or can be
>  	URCU_CALL_RCU_RT if the worker threads associated with the
> -	new helper thread are to get real-time response.
> +	new helper thread are to get real-time response. The argument
> +	"cpu_affinity" specifies a cpu on which the call_rcu thread should
> +	be affined to. It is ignored if negative.
> 
>  struct call_rcu_data *get_default_call_rcu_data(void);
> 
> Index: userspace-rcu/tests/rcutorture.h
> ===================================================================
> --- userspace-rcu.orig/tests/rcutorture.h
> +++ userspace-rcu/tests/rcutorture.h
> @@ -156,7 +156,7 @@ void *rcu_update_perf_test(void *arg)
>  	if ((random() & 0xf00) == 0) {
>  		struct call_rcu_data *crdp;
> 
> -		crdp = create_call_rcu_data(0);
> +		crdp = create_call_rcu_data(0, -1);
>  		if (crdp != NULL) {
>  			fprintf(stderr,
>  				"Using per-thread call_rcu() worker.\n");
> @@ -385,7 +385,7 @@ void *rcu_fake_update_stress_test(void *
>  	if ((random() & 0xf00) == 0) {
>  		struct call_rcu_data *crdp;
> 
> -		crdp = create_call_rcu_data(0);
> +		crdp = create_call_rcu_data(0, -1);
>  		if (crdp != NULL) {
>  			fprintf(stderr,
>  				"Using per-thread call_rcu() worker.\n");
> Index: userspace-rcu/urcu-call-rcu-impl.h
> ===================================================================
> --- userspace-rcu.orig/urcu-call-rcu-impl.h
> +++ userspace-rcu/urcu-call-rcu-impl.h
> @@ -20,6 +20,7 @@
>   * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
>   */
> 
> +#define _GNU_SOURCE
>  #include <stdio.h>
>  #include <pthread.h>
>  #include <signal.h>
> @@ -31,6 +32,7 @@
>  #include <sys/time.h>
>  #include <syscall.h>
>  #include <unistd.h>
> +#include <sched.h>
> 
>  #include "config.h"
>  #include "urcu/wfqueue.h"
> @@ -47,6 +49,7 @@ struct call_rcu_data {
>  	pthread_cond_t cond;
>  	unsigned long qlen;
>  	pthread_t tid;
> +	int cpu_affinity;
>  	struct cds_list_head list;
>  } __attribute__((aligned(CAA_CACHE_LINE_SIZE)));
> 
> @@ -146,6 +149,31 @@ static void call_rcu_unlock(pthread_mute
>  	}
>  }
> 
> +#if HAVE_SCHED_SETAFFINITY
> +static
> +int set_thread_cpu_affinity(struct call_rcu_data *crdp)
> +{
> +	cpu_set_t mask;
> +
> +	if (crdp->cpu_affinity < 0)
> +		return 0;
> +
> +	CPU_ZERO(&mask);
> +	CPU_SET(crdp->cpu_affinity, &mask);
> +#if SCHED_SETAFFINITY_ARGS == 2
> +	return sched_setaffinity(0, &mask);
> +#else
> +	return sched_setaffinity(0, sizeof(mask), &mask);
> +#endif
> +}
> +#else
> +static
> +int set_thread_cpu_affinity(struct call_rcu_data *crdp)
> +{
> +	return 0;
> +}
> +#endif
> +
>  /* This is the code run by each call_rcu thread. */
> 
>  static void *call_rcu_thread(void *arg)
> @@ -156,6 +184,11 @@ static void *call_rcu_thread(void *arg)
>  	struct call_rcu_data *crdp = (struct call_rcu_data *)arg;
>  	struct rcu_head *rhp;
> 
> +	if (set_thread_cpu_affinity(crdp) != 0) {
> +		perror("pthread_setaffinity_np");
> +		exit(-1);
> +	}
> +
>  	thread_call_rcu_data = crdp;
>  	for (;;) {
>  		if (&crdp->cbs.head != _CMM_LOAD_SHARED(crdp->cbs.tail)) {
> @@ -214,7 +247,8 @@ static void *call_rcu_thread(void *arg)
>   */
> 
>  static void call_rcu_data_init(struct call_rcu_data **crdpp,
> -			       unsigned long flags)
> +			       unsigned long flags,
> +			       int cpu_affinity)
>  {
>  	struct call_rcu_data *crdp;
> 
> @@ -236,6 +270,7 @@ static void call_rcu_data_init(struct ca
>  	}
>  	crdp->flags = flags | URCU_CALL_RCU_RUNNING;
>  	cds_list_add(&crdp->list, &call_rcu_data_list);
> +	crdp->cpu_affinity = cpu_affinity;
>  	cmm_smp_mb();  /* Structure initialized before pointer is planted. */
>  	*crdpp = crdp;
>  	if (pthread_create(&crdp->tid, NULL, call_rcu_thread, crdp) != 0) {
> @@ -280,20 +315,22 @@ pthread_t get_call_rcu_thread(struct cal
>   * Create a call_rcu_data structure (with thread) and return a pointer.
>   */
> 
> -static struct call_rcu_data *__create_call_rcu_data(unsigned long flags)
> +static struct call_rcu_data *__create_call_rcu_data(unsigned long flags,
> +						    int cpu_affinity)
>  {
>  	struct call_rcu_data *crdp;
> 
> -	call_rcu_data_init(&crdp, flags);
> +	call_rcu_data_init(&crdp, flags, cpu_affinity);
>  	return crdp;
>  }
> 
> -struct call_rcu_data *create_call_rcu_data(unsigned long flags)
> +struct call_rcu_data *create_call_rcu_data(unsigned long flags,
> +					   int cpu_affinity)
>  {
>  	struct call_rcu_data *crdp;
> 
>  	call_rcu_lock(&call_rcu_mutex);
> -	crdp = __create_call_rcu_data(flags);
> +	crdp = __create_call_rcu_data(flags, cpu_affinity);
>  	call_rcu_unlock(&call_rcu_mutex);
>  	return crdp;
>  }
> @@ -346,7 +383,7 @@ struct call_rcu_data *get_default_call_r
>  		call_rcu_unlock(&call_rcu_mutex);
>  		return default_call_rcu_data;
>  	}
> -	call_rcu_data_init(&default_call_rcu_data, 0);
> +	call_rcu_data_init(&default_call_rcu_data, 0, -1);
>  	call_rcu_unlock(&call_rcu_mutex);
>  	return default_call_rcu_data;
>  }
> @@ -434,7 +471,7 @@ int create_all_cpu_call_rcu_data(unsigne
>  			call_rcu_unlock(&call_rcu_mutex);
>  			continue;
>  		}
> -		crdp = __create_call_rcu_data(flags);
> +		crdp = __create_call_rcu_data(flags, i);
>  		if (crdp == NULL) {
>  			call_rcu_unlock(&call_rcu_mutex);
>  			errno = ENOMEM;
> Index: userspace-rcu/urcu-call-rcu.h
> ===================================================================
> --- userspace-rcu.orig/urcu-call-rcu.h
> +++ userspace-rcu/urcu-call-rcu.h
> @@ -64,7 +64,8 @@ struct rcu_head {
>   */
>  struct call_rcu_data *get_cpu_call_rcu_data(int cpu);
>  pthread_t get_call_rcu_thread(struct call_rcu_data *crdp);
> -struct call_rcu_data *create_call_rcu_data(unsigned long flags);
> +struct call_rcu_data *create_call_rcu_data(unsigned long flags,
> +					   int cpu_affinity);
>  int set_cpu_call_rcu_data(int cpu, struct call_rcu_data *crdp);
>  struct call_rcu_data *get_default_call_rcu_data(void);
>  struct call_rcu_data *get_call_rcu_data(void);
> Index: userspace-rcu/urcu-qsbr.c
> ===================================================================
> --- userspace-rcu.orig/urcu-qsbr.c
> +++ userspace-rcu/urcu-qsbr.c
> @@ -23,6 +23,7 @@
>   * IBM's contributions to this file may be relicensed under LGPLv2 or later.
>   */
> 
> +#define _GNU_SOURCE
>  #include <stdio.h>
>  #include <pthread.h>
>  #include <signal.h>
> Index: userspace-rcu/urcu.c
> ===================================================================
> --- userspace-rcu.orig/urcu.c
> +++ userspace-rcu/urcu.c
> @@ -24,6 +24,7 @@
>   */
> 
>  #define _BSD_SOURCE
> +#define _GNU_SOURCE
>  #include <stdio.h>
>  #include <pthread.h>
>  #include <signal.h>
> 

[ltt-dev] [rp] [URCU RFC patch 2/3] call_rcu: use futex for wakeup scheme

[Paul E. McKenney]

On Mon, Jun 06, 2011 at 01:46:00PM -0400, Mathieu Desnoyers wrote:
> If I remove the URCU_CALL_RCU_RT flag from the rbtree single writer
> test, thus using the pthread_cond_signal mechanism, there is a huge
> slowdown: without cpu affinity for the worker threads, it crawls to 129
> updates/s (looks like mutex contention between the thread calling
> call_rcu and the call_rcu thread). Adding CPU affinity to the per-cpu
> call_rcu threads, I get 546 updates/s, which is slightly better (better
> cache locality, and maybe the mutex contention is not as bad thanks to
> the two threads sharing the same CPU).
> 
> So I decided to try replacing pthread_cond_wait/signal with my
> futex-based implementation I use for the rest of the urcu lib: it has
> the advantage of removing the mutex from the call_rcu() execution
> entirely, sampling the "futex" variable without any mutex whatsoever for
> the case where no wakeup is needed.
> 
> Disabling URCU_CALL_RCU_RT flag, with per-cpu affined call_rcu threads,
> with my futex-based wakeup implementation, I get 55754 updates/s (even
> better than with URCU_CALL_RCU_RT flag!).

Assuming that compat_futex.c handles the non-Linux case, works for me!

							Thanx, Paul

> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> ---
>  urcu-call-rcu-impl.h |   56 +++++++++++++++++++++++++--------------------------
>  1 file changed, 28 insertions(+), 28 deletions(-)
> 
> Index: userspace-rcu/urcu-call-rcu-impl.h
> ===================================================================
> --- userspace-rcu.orig/urcu-call-rcu-impl.h
> +++ userspace-rcu/urcu-call-rcu-impl.h
> @@ -39,6 +39,7 @@
>  #include "urcu-call-rcu.h"
>  #include "urcu-pointer.h"
>  #include "urcu/list.h"
> +#include "urcu/urcu-futex.h"
> 
>  /* Data structure that identifies a call_rcu thread. */
> 
> @@ -46,7 +47,7 @@ struct call_rcu_data {
>  	struct cds_wfq_queue cbs;
>  	unsigned long flags;
>  	pthread_mutex_t mtx;
> -	pthread_cond_t cond;
> +	int futex;
>  	unsigned long qlen;
>  	pthread_t tid;
>  	int cpu_affinity;
> @@ -88,6 +89,26 @@ static struct call_rcu_data *default_cal
>  static struct call_rcu_data **per_cpu_call_rcu_data;
>  static long maxcpus;
> 
> +static void call_rcu_wait(struct call_rcu_data *crdp)
> +{
> +	/* Read call_rcu list before read futex */
> +	cmm_smp_mb();
> +	if (uatomic_read(&crdp->futex) == -1)
> +		futex_async(&crdp->futex, FUTEX_WAIT, -1,
> +		      NULL, NULL, 0);
> +}
> +
> +static void call_rcu_wake_up(struct call_rcu_data *crdp)
> +{
> +	/* Write to call_rcu list before reading/writing futex */
> +	cmm_smp_mb();
> +	if (unlikely(uatomic_read(&crdp->futex) == -1)) {
> +		uatomic_set(&crdp->futex, 0);
> +		futex_async(&crdp->futex, FUTEX_WAKE, 1,
> +		      NULL, NULL, 0);
> +	}
> +}
> +
>  /* Allocate the array if it has not already been allocated. */
> 
>  static void alloc_cpu_call_rcu_data(void)
> @@ -219,19 +240,9 @@ static void *call_rcu_thread(void *arg)
>  		if (crdp->flags & URCU_CALL_RCU_RT)
>  			poll(NULL, 0, 10);
>  		else {
> -			call_rcu_lock(&crdp->mtx);
> -			_CMM_STORE_SHARED(crdp->flags,
> -				     crdp->flags & ~URCU_CALL_RCU_RUNNING);
> -			if (&crdp->cbs.head ==
> -			    _CMM_LOAD_SHARED(crdp->cbs.tail) &&
> -			    pthread_cond_wait(&crdp->cond, &crdp->mtx) != 0) {
> -				perror("pthread_cond_wait");
> -				exit(-1);
> -			}
> -			_CMM_STORE_SHARED(crdp->flags,
> -				     crdp->flags | URCU_CALL_RCU_RUNNING);
> +			if (&crdp->cbs.head == _CMM_LOAD_SHARED(crdp->cbs.tail))
> +				call_rcu_wait(crdp);
>  			poll(NULL, 0, 10);
> -			call_rcu_unlock(&crdp->mtx);
>  		}
>  	}
>  	call_rcu_lock(&crdp->mtx);
> @@ -264,11 +275,8 @@ static void call_rcu_data_init(struct ca
>  		perror("pthread_mutex_init");
>  		exit(-1);
>  	}
> -	if (pthread_cond_init(&crdp->cond, NULL) != 0) {
> -		perror("pthread_cond_init");
> -		exit(-1);
> -	}
> -	crdp->flags = flags | URCU_CALL_RCU_RUNNING;
> +	crdp->futex = 0;
> +	crdp->flags = flags;
>  	cds_list_add(&crdp->list, &call_rcu_data_list);
>  	crdp->cpu_affinity = cpu_affinity;
>  	cmm_smp_mb();  /* Structure initialized before pointer is planted. */
> @@ -492,16 +500,8 @@ int create_all_cpu_call_rcu_data(unsigne
>   */
>  static void wake_call_rcu_thread(struct call_rcu_data *crdp)
>  {
> -	if (!(_CMM_LOAD_SHARED(crdp->flags) & URCU_CALL_RCU_RT)) {
> -		call_rcu_lock(&crdp->mtx);
> -		if (!(_CMM_LOAD_SHARED(crdp->flags) & URCU_CALL_RCU_RUNNING)) {
> -			if (pthread_cond_signal(&crdp->cond) != 0) {
> -				perror("pthread_cond_signal");
> -				exit(-1);
> -			}
> -		}
> -		call_rcu_unlock(&crdp->mtx);
> -	}
> +	if (!(_CMM_LOAD_SHARED(crdp->flags) & URCU_CALL_RCU_RT))
> +		call_rcu_wake_up(crdp);
>  }
> 
>  /*
> 
> 
> _______________________________________________
> rp mailing list
> rp at svcs.cs.pdx.edu
> http://svcs.cs.pdx.edu/mailman/listinfo/rp

[ltt-dev] [URCU RFC patch 1/3] call_rcu: use cpu affinity for per-cpu call_rcu threads

[Mathieu Desnoyers]

* Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> On Mon, Jun 06, 2011 at 01:45:59PM -0400, Mathieu Desnoyers wrote:
> > I played a bit with the call_rcu() implementation alongside with my
> > rbtree tests, and noticed the following:
> > 
> > If I use per-cpu call_rcu threads with URCU_CALL_RCU_RT flag, with one
> > updater thread only for my rbtree (no reader), I get 38365 updates/s.
> > If I add cpu affinity to these per-cpu call_rcu threads (I have prepared
> > a patch that does this), it jumps to 54219 updates/s.  So it looks like
> > keeping per-cpu affinity for the call_rcu thread is a good thing.
> 
> Makes sense to me!
> 
> Main comment is that API.h should also be updated.

I updated API.txt. What is API.h ?

Mathieu

> 
> 							Thanx, Paul
> 
> > Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> > ---
> >  API.txt              |    7 +++++--
> >  tests/rcutorture.h   |    4 ++--
> >  urcu-call-rcu-impl.h |   51 ++++++++++++++++++++++++++++++++++++++++++++-------
> >  urcu-call-rcu.h      |    3 ++-
> >  urcu-qsbr.c          |    1 +
> >  urcu.c               |    1 +
> >  6 files changed, 55 insertions(+), 12 deletions(-)
> > 
> > Index: userspace-rcu/API.txt
> > ===================================================================
> > --- userspace-rcu.orig/API.txt
> > +++ userspace-rcu/API.txt
> > @@ -59,12 +59,15 @@ void call_rcu(struct rcu_head *head,
> > 
> >  		call_rcu(&p->rcu, func);
> > 
> > -struct call_rcu_data *create_call_rcu_data(unsigned long flags);
> > +struct call_rcu_data *create_call_rcu_data(unsigned long flags,
> > +					   int cpu_affinity);
> > 
> >  	Returns a handle that can be passed to the following
> >  	primitives.  The "flags" argument can be zero, or can be
> >  	URCU_CALL_RCU_RT if the worker threads associated with the
> > -	new helper thread are to get real-time response.
> > +	new helper thread are to get real-time response. The argument
> > +	"cpu_affinity" specifies a cpu on which the call_rcu thread should
> > +	be affined to. It is ignored if negative.
> > 
> >  struct call_rcu_data *get_default_call_rcu_data(void);
> > 
> > Index: userspace-rcu/tests/rcutorture.h
> > ===================================================================
> > --- userspace-rcu.orig/tests/rcutorture.h
> > +++ userspace-rcu/tests/rcutorture.h
> > @@ -156,7 +156,7 @@ void *rcu_update_perf_test(void *arg)
> >  	if ((random() & 0xf00) == 0) {
> >  		struct call_rcu_data *crdp;
> > 
> > -		crdp = create_call_rcu_data(0);
> > +		crdp = create_call_rcu_data(0, -1);
> >  		if (crdp != NULL) {
> >  			fprintf(stderr,
> >  				"Using per-thread call_rcu() worker.\n");
> > @@ -385,7 +385,7 @@ void *rcu_fake_update_stress_test(void *
> >  	if ((random() & 0xf00) == 0) {
> >  		struct call_rcu_data *crdp;
> > 
> > -		crdp = create_call_rcu_data(0);
> > +		crdp = create_call_rcu_data(0, -1);
> >  		if (crdp != NULL) {
> >  			fprintf(stderr,
> >  				"Using per-thread call_rcu() worker.\n");
> > Index: userspace-rcu/urcu-call-rcu-impl.h
> > ===================================================================
> > --- userspace-rcu.orig/urcu-call-rcu-impl.h
> > +++ userspace-rcu/urcu-call-rcu-impl.h
> > @@ -20,6 +20,7 @@
> >   * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> >   */
> > 
> > +#define _GNU_SOURCE
> >  #include <stdio.h>
> >  #include <pthread.h>
> >  #include <signal.h>
> > @@ -31,6 +32,7 @@
> >  #include <sys/time.h>
> >  #include <syscall.h>
> >  #include <unistd.h>
> > +#include <sched.h>
> > 
> >  #include "config.h"
> >  #include "urcu/wfqueue.h"
> > @@ -47,6 +49,7 @@ struct call_rcu_data {
> >  	pthread_cond_t cond;
> >  	unsigned long qlen;
> >  	pthread_t tid;
> > +	int cpu_affinity;
> >  	struct cds_list_head list;
> >  } __attribute__((aligned(CAA_CACHE_LINE_SIZE)));
> > 
> > @@ -146,6 +149,31 @@ static void call_rcu_unlock(pthread_mute
> >  	}
> >  }
> > 
> > +#if HAVE_SCHED_SETAFFINITY
> > +static
> > +int set_thread_cpu_affinity(struct call_rcu_data *crdp)
> > +{
> > +	cpu_set_t mask;
> > +
> > +	if (crdp->cpu_affinity < 0)
> > +		return 0;
> > +
> > +	CPU_ZERO(&mask);
> > +	CPU_SET(crdp->cpu_affinity, &mask);
> > +#if SCHED_SETAFFINITY_ARGS == 2
> > +	return sched_setaffinity(0, &mask);
> > +#else
> > +	return sched_setaffinity(0, sizeof(mask), &mask);
> > +#endif
> > +}
> > +#else
> > +static
> > +int set_thread_cpu_affinity(struct call_rcu_data *crdp)
> > +{
> > +	return 0;
> > +}
> > +#endif
> > +
> >  /* This is the code run by each call_rcu thread. */
> > 
> >  static void *call_rcu_thread(void *arg)
> > @@ -156,6 +184,11 @@ static void *call_rcu_thread(void *arg)
> >  	struct call_rcu_data *crdp = (struct call_rcu_data *)arg;
> >  	struct rcu_head *rhp;
> > 
> > +	if (set_thread_cpu_affinity(crdp) != 0) {
> > +		perror("pthread_setaffinity_np");
> > +		exit(-1);
> > +	}
> > +
> >  	thread_call_rcu_data = crdp;
> >  	for (;;) {
> >  		if (&crdp->cbs.head != _CMM_LOAD_SHARED(crdp->cbs.tail)) {
> > @@ -214,7 +247,8 @@ static void *call_rcu_thread(void *arg)
> >   */
> > 
> >  static void call_rcu_data_init(struct call_rcu_data **crdpp,
> > -			       unsigned long flags)
> > +			       unsigned long flags,
> > +			       int cpu_affinity)
> >  {
> >  	struct call_rcu_data *crdp;
> > 
> > @@ -236,6 +270,7 @@ static void call_rcu_data_init(struct ca
> >  	}
> >  	crdp->flags = flags | URCU_CALL_RCU_RUNNING;
> >  	cds_list_add(&crdp->list, &call_rcu_data_list);
> > +	crdp->cpu_affinity = cpu_affinity;
> >  	cmm_smp_mb();  /* Structure initialized before pointer is planted. */
> >  	*crdpp = crdp;
> >  	if (pthread_create(&crdp->tid, NULL, call_rcu_thread, crdp) != 0) {
> > @@ -280,20 +315,22 @@ pthread_t get_call_rcu_thread(struct cal
> >   * Create a call_rcu_data structure (with thread) and return a pointer.
> >   */
> > 
> > -static struct call_rcu_data *__create_call_rcu_data(unsigned long flags)
> > +static struct call_rcu_data *__create_call_rcu_data(unsigned long flags,
> > +						    int cpu_affinity)
> >  {
> >  	struct call_rcu_data *crdp;
> > 
> > -	call_rcu_data_init(&crdp, flags);
> > +	call_rcu_data_init(&crdp, flags, cpu_affinity);
> >  	return crdp;
> >  }
> > 
> > -struct call_rcu_data *create_call_rcu_data(unsigned long flags)
> > +struct call_rcu_data *create_call_rcu_data(unsigned long flags,
> > +					   int cpu_affinity)
> >  {
> >  	struct call_rcu_data *crdp;
> > 
> >  	call_rcu_lock(&call_rcu_mutex);
> > -	crdp = __create_call_rcu_data(flags);
> > +	crdp = __create_call_rcu_data(flags, cpu_affinity);
> >  	call_rcu_unlock(&call_rcu_mutex);
> >  	return crdp;
> >  }
> > @@ -346,7 +383,7 @@ struct call_rcu_data *get_default_call_r
> >  		call_rcu_unlock(&call_rcu_mutex);
> >  		return default_call_rcu_data;
> >  	}
> > -	call_rcu_data_init(&default_call_rcu_data, 0);
> > +	call_rcu_data_init(&default_call_rcu_data, 0, -1);
> >  	call_rcu_unlock(&call_rcu_mutex);
> >  	return default_call_rcu_data;
> >  }
> > @@ -434,7 +471,7 @@ int create_all_cpu_call_rcu_data(unsigne
> >  			call_rcu_unlock(&call_rcu_mutex);
> >  			continue;
> >  		}
> > -		crdp = __create_call_rcu_data(flags);
> > +		crdp = __create_call_rcu_data(flags, i);
> >  		if (crdp == NULL) {
> >  			call_rcu_unlock(&call_rcu_mutex);
> >  			errno = ENOMEM;
> > Index: userspace-rcu/urcu-call-rcu.h
> > ===================================================================
> > --- userspace-rcu.orig/urcu-call-rcu.h
> > +++ userspace-rcu/urcu-call-rcu.h
> > @@ -64,7 +64,8 @@ struct rcu_head {
> >   */
> >  struct call_rcu_data *get_cpu_call_rcu_data(int cpu);
> >  pthread_t get_call_rcu_thread(struct call_rcu_data *crdp);
> > -struct call_rcu_data *create_call_rcu_data(unsigned long flags);
> > +struct call_rcu_data *create_call_rcu_data(unsigned long flags,
> > +					   int cpu_affinity);
> >  int set_cpu_call_rcu_data(int cpu, struct call_rcu_data *crdp);
> >  struct call_rcu_data *get_default_call_rcu_data(void);
> >  struct call_rcu_data *get_call_rcu_data(void);
> > Index: userspace-rcu/urcu-qsbr.c
> > ===================================================================
> > --- userspace-rcu.orig/urcu-qsbr.c
> > +++ userspace-rcu/urcu-qsbr.c
> > @@ -23,6 +23,7 @@
> >   * IBM's contributions to this file may be relicensed under LGPLv2 or later.
> >   */
> > 
> > +#define _GNU_SOURCE
> >  #include <stdio.h>
> >  #include <pthread.h>
> >  #include <signal.h>
> > Index: userspace-rcu/urcu.c
> > ===================================================================
> > --- userspace-rcu.orig/urcu.c
> > +++ userspace-rcu/urcu.c
> > @@ -24,6 +24,7 @@
> >   */
> > 
> >  #define _BSD_SOURCE
> > +#define _GNU_SOURCE
> >  #include <stdio.h>
> >  #include <pthread.h>
> >  #include <signal.h>
> > 

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] [URCU RFC patch 1/3] call_rcu: use cpu affinity for per-cpu call_rcu threads

[Paul E. McKenney]

On Mon, Jun 06, 2011 at 04:47:48PM -0400, Mathieu Desnoyers wrote:
> * Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> > On Mon, Jun 06, 2011 at 01:45:59PM -0400, Mathieu Desnoyers wrote:
> > > I played a bit with the call_rcu() implementation alongside with my
> > > rbtree tests, and noticed the following:
> > > 
> > > If I use per-cpu call_rcu threads with URCU_CALL_RCU_RT flag, with one
> > > updater thread only for my rbtree (no reader), I get 38365 updates/s.
> > > If I add cpu affinity to these per-cpu call_rcu threads (I have prepared
> > > a patch that does this), it jumps to 54219 updates/s.  So it looks like
> > > keeping per-cpu affinity for the call_rcu thread is a good thing.
> > 
> > Makes sense to me!
> > 
> > Main comment is that API.h should also be updated.
> 
> I updated API.txt. What is API.h ?

API.h is a typo on my part, thank you for your correct interpretation!

							Thanx, Paul

> Mathieu
> 
> > 
> > 							Thanx, Paul
> > 
> > > Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> > > ---
> > >  API.txt              |    7 +++++--
> > >  tests/rcutorture.h   |    4 ++--
> > >  urcu-call-rcu-impl.h |   51 ++++++++++++++++++++++++++++++++++++++++++++-------
> > >  urcu-call-rcu.h      |    3 ++-
> > >  urcu-qsbr.c          |    1 +
> > >  urcu.c               |    1 +
> > >  6 files changed, 55 insertions(+), 12 deletions(-)
> > > 
> > > Index: userspace-rcu/API.txt
> > > ===================================================================
> > > --- userspace-rcu.orig/API.txt
> > > +++ userspace-rcu/API.txt
> > > @@ -59,12 +59,15 @@ void call_rcu(struct rcu_head *head,
> > > 
> > >  		call_rcu(&p->rcu, func);
> > > 
> > > -struct call_rcu_data *create_call_rcu_data(unsigned long flags);
> > > +struct call_rcu_data *create_call_rcu_data(unsigned long flags,
> > > +					   int cpu_affinity);
> > > 
> > >  	Returns a handle that can be passed to the following
> > >  	primitives.  The "flags" argument can be zero, or can be
> > >  	URCU_CALL_RCU_RT if the worker threads associated with the
> > > -	new helper thread are to get real-time response.
> > > +	new helper thread are to get real-time response. The argument
> > > +	"cpu_affinity" specifies a cpu on which the call_rcu thread should
> > > +	be affined to. It is ignored if negative.
> > > 
> > >  struct call_rcu_data *get_default_call_rcu_data(void);
> > > 
> > > Index: userspace-rcu/tests/rcutorture.h
> > > ===================================================================
> > > --- userspace-rcu.orig/tests/rcutorture.h
> > > +++ userspace-rcu/tests/rcutorture.h
> > > @@ -156,7 +156,7 @@ void *rcu_update_perf_test(void *arg)
> > >  	if ((random() & 0xf00) == 0) {
> > >  		struct call_rcu_data *crdp;
> > > 
> > > -		crdp = create_call_rcu_data(0);
> > > +		crdp = create_call_rcu_data(0, -1);
> > >  		if (crdp != NULL) {
> > >  			fprintf(stderr,
> > >  				"Using per-thread call_rcu() worker.\n");
> > > @@ -385,7 +385,7 @@ void *rcu_fake_update_stress_test(void *
> > >  	if ((random() & 0xf00) == 0) {
> > >  		struct call_rcu_data *crdp;
> > > 
> > > -		crdp = create_call_rcu_data(0);
> > > +		crdp = create_call_rcu_data(0, -1);
> > >  		if (crdp != NULL) {
> > >  			fprintf(stderr,
> > >  				"Using per-thread call_rcu() worker.\n");
> > > Index: userspace-rcu/urcu-call-rcu-impl.h
> > > ===================================================================
> > > --- userspace-rcu.orig/urcu-call-rcu-impl.h
> > > +++ userspace-rcu/urcu-call-rcu-impl.h
> > > @@ -20,6 +20,7 @@
> > >   * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> > >   */
> > > 
> > > +#define _GNU_SOURCE
> > >  #include <stdio.h>
> > >  #include <pthread.h>
> > >  #include <signal.h>
> > > @@ -31,6 +32,7 @@
> > >  #include <sys/time.h>
> > >  #include <syscall.h>
> > >  #include <unistd.h>
> > > +#include <sched.h>
> > > 
> > >  #include "config.h"
> > >  #include "urcu/wfqueue.h"
> > > @@ -47,6 +49,7 @@ struct call_rcu_data {
> > >  	pthread_cond_t cond;
> > >  	unsigned long qlen;
> > >  	pthread_t tid;
> > > +	int cpu_affinity;
> > >  	struct cds_list_head list;
> > >  } __attribute__((aligned(CAA_CACHE_LINE_SIZE)));
> > > 
> > > @@ -146,6 +149,31 @@ static void call_rcu_unlock(pthread_mute
> > >  	}
> > >  }
> > > 
> > > +#if HAVE_SCHED_SETAFFINITY
> > > +static
> > > +int set_thread_cpu_affinity(struct call_rcu_data *crdp)
> > > +{
> > > +	cpu_set_t mask;
> > > +
> > > +	if (crdp->cpu_affinity < 0)
> > > +		return 0;
> > > +
> > > +	CPU_ZERO(&mask);
> > > +	CPU_SET(crdp->cpu_affinity, &mask);
> > > +#if SCHED_SETAFFINITY_ARGS == 2
> > > +	return sched_setaffinity(0, &mask);
> > > +#else
> > > +	return sched_setaffinity(0, sizeof(mask), &mask);
> > > +#endif
> > > +}
> > > +#else
> > > +static
> > > +int set_thread_cpu_affinity(struct call_rcu_data *crdp)
> > > +{
> > > +	return 0;
> > > +}
> > > +#endif
> > > +
> > >  /* This is the code run by each call_rcu thread. */
> > > 
> > >  static void *call_rcu_thread(void *arg)
> > > @@ -156,6 +184,11 @@ static void *call_rcu_thread(void *arg)
> > >  	struct call_rcu_data *crdp = (struct call_rcu_data *)arg;
> > >  	struct rcu_head *rhp;
> > > 
> > > +	if (set_thread_cpu_affinity(crdp) != 0) {
> > > +		perror("pthread_setaffinity_np");
> > > +		exit(-1);
> > > +	}
> > > +
> > >  	thread_call_rcu_data = crdp;
> > >  	for (;;) {
> > >  		if (&crdp->cbs.head != _CMM_LOAD_SHARED(crdp->cbs.tail)) {
> > > @@ -214,7 +247,8 @@ static void *call_rcu_thread(void *arg)
> > >   */
> > > 
> > >  static void call_rcu_data_init(struct call_rcu_data **crdpp,
> > > -			       unsigned long flags)
> > > +			       unsigned long flags,
> > > +			       int cpu_affinity)
> > >  {
> > >  	struct call_rcu_data *crdp;
> > > 
> > > @@ -236,6 +270,7 @@ static void call_rcu_data_init(struct ca
> > >  	}
> > >  	crdp->flags = flags | URCU_CALL_RCU_RUNNING;
> > >  	cds_list_add(&crdp->list, &call_rcu_data_list);
> > > +	crdp->cpu_affinity = cpu_affinity;
> > >  	cmm_smp_mb();  /* Structure initialized before pointer is planted. */
> > >  	*crdpp = crdp;
> > >  	if (pthread_create(&crdp->tid, NULL, call_rcu_thread, crdp) != 0) {
> > > @@ -280,20 +315,22 @@ pthread_t get_call_rcu_thread(struct cal
> > >   * Create a call_rcu_data structure (with thread) and return a pointer.
> > >   */
> > > 
> > > -static struct call_rcu_data *__create_call_rcu_data(unsigned long flags)
> > > +static struct call_rcu_data *__create_call_rcu_data(unsigned long flags,
> > > +						    int cpu_affinity)
> > >  {
> > >  	struct call_rcu_data *crdp;
> > > 
> > > -	call_rcu_data_init(&crdp, flags);
> > > +	call_rcu_data_init(&crdp, flags, cpu_affinity);
> > >  	return crdp;
> > >  }
> > > 
> > > -struct call_rcu_data *create_call_rcu_data(unsigned long flags)
> > > +struct call_rcu_data *create_call_rcu_data(unsigned long flags,
> > > +					   int cpu_affinity)
> > >  {
> > >  	struct call_rcu_data *crdp;
> > > 
> > >  	call_rcu_lock(&call_rcu_mutex);
> > > -	crdp = __create_call_rcu_data(flags);
> > > +	crdp = __create_call_rcu_data(flags, cpu_affinity);
> > >  	call_rcu_unlock(&call_rcu_mutex);
> > >  	return crdp;
> > >  }
> > > @@ -346,7 +383,7 @@ struct call_rcu_data *get_default_call_r
> > >  		call_rcu_unlock(&call_rcu_mutex);
> > >  		return default_call_rcu_data;
> > >  	}
> > > -	call_rcu_data_init(&default_call_rcu_data, 0);
> > > +	call_rcu_data_init(&default_call_rcu_data, 0, -1);
> > >  	call_rcu_unlock(&call_rcu_mutex);
> > >  	return default_call_rcu_data;
> > >  }
> > > @@ -434,7 +471,7 @@ int create_all_cpu_call_rcu_data(unsigne
> > >  			call_rcu_unlock(&call_rcu_mutex);
> > >  			continue;
> > >  		}
> > > -		crdp = __create_call_rcu_data(flags);
> > > +		crdp = __create_call_rcu_data(flags, i);
> > >  		if (crdp == NULL) {
> > >  			call_rcu_unlock(&call_rcu_mutex);
> > >  			errno = ENOMEM;
> > > Index: userspace-rcu/urcu-call-rcu.h
> > > ===================================================================
> > > --- userspace-rcu.orig/urcu-call-rcu.h
> > > +++ userspace-rcu/urcu-call-rcu.h
> > > @@ -64,7 +64,8 @@ struct rcu_head {
> > >   */
> > >  struct call_rcu_data *get_cpu_call_rcu_data(int cpu);
> > >  pthread_t get_call_rcu_thread(struct call_rcu_data *crdp);
> > > -struct call_rcu_data *create_call_rcu_data(unsigned long flags);
> > > +struct call_rcu_data *create_call_rcu_data(unsigned long flags,
> > > +					   int cpu_affinity);
> > >  int set_cpu_call_rcu_data(int cpu, struct call_rcu_data *crdp);
> > >  struct call_rcu_data *get_default_call_rcu_data(void);
> > >  struct call_rcu_data *get_call_rcu_data(void);
> > > Index: userspace-rcu/urcu-qsbr.c
> > > ===================================================================
> > > --- userspace-rcu.orig/urcu-qsbr.c
> > > +++ userspace-rcu/urcu-qsbr.c
> > > @@ -23,6 +23,7 @@
> > >   * IBM's contributions to this file may be relicensed under LGPLv2 or later.
> > >   */
> > > 
> > > +#define _GNU_SOURCE
> > >  #include <stdio.h>
> > >  #include <pthread.h>
> > >  #include <signal.h>
> > > Index: userspace-rcu/urcu.c
> > > ===================================================================
> > > --- userspace-rcu.orig/urcu.c
> > > +++ userspace-rcu/urcu.c
> > > @@ -24,6 +24,7 @@
> > >   */
> > > 
> > >  #define _BSD_SOURCE
> > > +#define _GNU_SOURCE
> > >  #include <stdio.h>
> > >  #include <pthread.h>
> > >  #include <signal.h>
> > > 
> 
> -- 
> Mathieu Desnoyers
> Operating System Efficiency R&D Consultant
> EfficiOS Inc.
> http://www.efficios.com

[ltt-dev] [URCU RFC patch 1/3] call_rcu: use cpu affinity for per-cpu call_rcu threads

[Mathieu Desnoyers]

* Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> On Mon, Jun 06, 2011 at 04:47:48PM -0400, Mathieu Desnoyers wrote:
> > * Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> > > On Mon, Jun 06, 2011 at 01:45:59PM -0400, Mathieu Desnoyers wrote:
> > > > I played a bit with the call_rcu() implementation alongside with my
> > > > rbtree tests, and noticed the following:
> > > > 
> > > > If I use per-cpu call_rcu threads with URCU_CALL_RCU_RT flag, with one
> > > > updater thread only for my rbtree (no reader), I get 38365 updates/s.
> > > > If I add cpu affinity to these per-cpu call_rcu threads (I have prepared
> > > > a patch that does this), it jumps to 54219 updates/s.  So it looks like
> > > > keeping per-cpu affinity for the call_rcu thread is a good thing.
> > > 
> > > Makes sense to me!
> > > 
> > > Main comment is that API.h should also be updated.
> > 
> > I updated API.txt. What is API.h ?
> 
> API.h is a typo on my part, thank you for your correct interpretation!

OK, patch merged as-is.

Thanks,

Mathieu

> 
> 							Thanx, Paul
> 
> > Mathieu
> > 
> > > 
> > > 							Thanx, Paul
> > > 
> > > > Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> > > > ---
> > > >  API.txt              |    7 +++++--
> > > >  tests/rcutorture.h   |    4 ++--
> > > >  urcu-call-rcu-impl.h |   51 ++++++++++++++++++++++++++++++++++++++++++++-------
> > > >  urcu-call-rcu.h      |    3 ++-
> > > >  urcu-qsbr.c          |    1 +
> > > >  urcu.c               |    1 +
> > > >  6 files changed, 55 insertions(+), 12 deletions(-)
> > > > 
> > > > Index: userspace-rcu/API.txt
> > > > ===================================================================
> > > > --- userspace-rcu.orig/API.txt
> > > > +++ userspace-rcu/API.txt
> > > > @@ -59,12 +59,15 @@ void call_rcu(struct rcu_head *head,
> > > > 
> > > >  		call_rcu(&p->rcu, func);
> > > > 
> > > > -struct call_rcu_data *create_call_rcu_data(unsigned long flags);
> > > > +struct call_rcu_data *create_call_rcu_data(unsigned long flags,
> > > > +					   int cpu_affinity);
> > > > 
> > > >  	Returns a handle that can be passed to the following
> > > >  	primitives.  The "flags" argument can be zero, or can be
> > > >  	URCU_CALL_RCU_RT if the worker threads associated with the
> > > > -	new helper thread are to get real-time response.
> > > > +	new helper thread are to get real-time response. The argument
> > > > +	"cpu_affinity" specifies a cpu on which the call_rcu thread should
> > > > +	be affined to. It is ignored if negative.
> > > > 
> > > >  struct call_rcu_data *get_default_call_rcu_data(void);
> > > > 
> > > > Index: userspace-rcu/tests/rcutorture.h
> > > > ===================================================================
> > > > --- userspace-rcu.orig/tests/rcutorture.h
> > > > +++ userspace-rcu/tests/rcutorture.h
> > > > @@ -156,7 +156,7 @@ void *rcu_update_perf_test(void *arg)
> > > >  	if ((random() & 0xf00) == 0) {
> > > >  		struct call_rcu_data *crdp;
> > > > 
> > > > -		crdp = create_call_rcu_data(0);
> > > > +		crdp = create_call_rcu_data(0, -1);
> > > >  		if (crdp != NULL) {
> > > >  			fprintf(stderr,
> > > >  				"Using per-thread call_rcu() worker.\n");
> > > > @@ -385,7 +385,7 @@ void *rcu_fake_update_stress_test(void *
> > > >  	if ((random() & 0xf00) == 0) {
> > > >  		struct call_rcu_data *crdp;
> > > > 
> > > > -		crdp = create_call_rcu_data(0);
> > > > +		crdp = create_call_rcu_data(0, -1);
> > > >  		if (crdp != NULL) {
> > > >  			fprintf(stderr,
> > > >  				"Using per-thread call_rcu() worker.\n");
> > > > Index: userspace-rcu/urcu-call-rcu-impl.h
> > > > ===================================================================
> > > > --- userspace-rcu.orig/urcu-call-rcu-impl.h
> > > > +++ userspace-rcu/urcu-call-rcu-impl.h
> > > > @@ -20,6 +20,7 @@
> > > >   * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> > > >   */
> > > > 
> > > > +#define _GNU_SOURCE
> > > >  #include <stdio.h>
> > > >  #include <pthread.h>
> > > >  #include <signal.h>
> > > > @@ -31,6 +32,7 @@
> > > >  #include <sys/time.h>
> > > >  #include <syscall.h>
> > > >  #include <unistd.h>
> > > > +#include <sched.h>
> > > > 
> > > >  #include "config.h"
> > > >  #include "urcu/wfqueue.h"
> > > > @@ -47,6 +49,7 @@ struct call_rcu_data {
> > > >  	pthread_cond_t cond;
> > > >  	unsigned long qlen;
> > > >  	pthread_t tid;
> > > > +	int cpu_affinity;
> > > >  	struct cds_list_head list;
> > > >  } __attribute__((aligned(CAA_CACHE_LINE_SIZE)));
> > > > 
> > > > @@ -146,6 +149,31 @@ static void call_rcu_unlock(pthread_mute
> > > >  	}
> > > >  }
> > > > 
> > > > +#if HAVE_SCHED_SETAFFINITY
> > > > +static
> > > > +int set_thread_cpu_affinity(struct call_rcu_data *crdp)
> > > > +{
> > > > +	cpu_set_t mask;
> > > > +
> > > > +	if (crdp->cpu_affinity < 0)
> > > > +		return 0;
> > > > +
> > > > +	CPU_ZERO(&mask);
> > > > +	CPU_SET(crdp->cpu_affinity, &mask);
> > > > +#if SCHED_SETAFFINITY_ARGS == 2
> > > > +	return sched_setaffinity(0, &mask);
> > > > +#else
> > > > +	return sched_setaffinity(0, sizeof(mask), &mask);
> > > > +#endif
> > > > +}
> > > > +#else
> > > > +static
> > > > +int set_thread_cpu_affinity(struct call_rcu_data *crdp)
> > > > +{
> > > > +	return 0;
> > > > +}
> > > > +#endif
> > > > +
> > > >  /* This is the code run by each call_rcu thread. */
> > > > 
> > > >  static void *call_rcu_thread(void *arg)
> > > > @@ -156,6 +184,11 @@ static void *call_rcu_thread(void *arg)
> > > >  	struct call_rcu_data *crdp = (struct call_rcu_data *)arg;
> > > >  	struct rcu_head *rhp;
> > > > 
> > > > +	if (set_thread_cpu_affinity(crdp) != 0) {
> > > > +		perror("pthread_setaffinity_np");
> > > > +		exit(-1);
> > > > +	}
> > > > +
> > > >  	thread_call_rcu_data = crdp;
> > > >  	for (;;) {
> > > >  		if (&crdp->cbs.head != _CMM_LOAD_SHARED(crdp->cbs.tail)) {
> > > > @@ -214,7 +247,8 @@ static void *call_rcu_thread(void *arg)
> > > >   */
> > > > 
> > > >  static void call_rcu_data_init(struct call_rcu_data **crdpp,
> > > > -			       unsigned long flags)
> > > > +			       unsigned long flags,
> > > > +			       int cpu_affinity)
> > > >  {
> > > >  	struct call_rcu_data *crdp;
> > > > 
> > > > @@ -236,6 +270,7 @@ static void call_rcu_data_init(struct ca
> > > >  	}
> > > >  	crdp->flags = flags | URCU_CALL_RCU_RUNNING;
> > > >  	cds_list_add(&crdp->list, &call_rcu_data_list);
> > > > +	crdp->cpu_affinity = cpu_affinity;
> > > >  	cmm_smp_mb();  /* Structure initialized before pointer is planted. */
> > > >  	*crdpp = crdp;
> > > >  	if (pthread_create(&crdp->tid, NULL, call_rcu_thread, crdp) != 0) {
> > > > @@ -280,20 +315,22 @@ pthread_t get_call_rcu_thread(struct cal
> > > >   * Create a call_rcu_data structure (with thread) and return a pointer.
> > > >   */
> > > > 
> > > > -static struct call_rcu_data *__create_call_rcu_data(unsigned long flags)
> > > > +static struct call_rcu_data *__create_call_rcu_data(unsigned long flags,
> > > > +						    int cpu_affinity)
> > > >  {
> > > >  	struct call_rcu_data *crdp;
> > > > 
> > > > -	call_rcu_data_init(&crdp, flags);
> > > > +	call_rcu_data_init(&crdp, flags, cpu_affinity);
> > > >  	return crdp;
> > > >  }
> > > > 
> > > > -struct call_rcu_data *create_call_rcu_data(unsigned long flags)
> > > > +struct call_rcu_data *create_call_rcu_data(unsigned long flags,
> > > > +					   int cpu_affinity)
> > > >  {
> > > >  	struct call_rcu_data *crdp;
> > > > 
> > > >  	call_rcu_lock(&call_rcu_mutex);
> > > > -	crdp = __create_call_rcu_data(flags);
> > > > +	crdp = __create_call_rcu_data(flags, cpu_affinity);
> > > >  	call_rcu_unlock(&call_rcu_mutex);
> > > >  	return crdp;
> > > >  }
> > > > @@ -346,7 +383,7 @@ struct call_rcu_data *get_default_call_r
> > > >  		call_rcu_unlock(&call_rcu_mutex);
> > > >  		return default_call_rcu_data;
> > > >  	}
> > > > -	call_rcu_data_init(&default_call_rcu_data, 0);
> > > > +	call_rcu_data_init(&default_call_rcu_data, 0, -1);
> > > >  	call_rcu_unlock(&call_rcu_mutex);
> > > >  	return default_call_rcu_data;
> > > >  }
> > > > @@ -434,7 +471,7 @@ int create_all_cpu_call_rcu_data(unsigne
> > > >  			call_rcu_unlock(&call_rcu_mutex);
> > > >  			continue;
> > > >  		}
> > > > -		crdp = __create_call_rcu_data(flags);
> > > > +		crdp = __create_call_rcu_data(flags, i);
> > > >  		if (crdp == NULL) {
> > > >  			call_rcu_unlock(&call_rcu_mutex);
> > > >  			errno = ENOMEM;
> > > > Index: userspace-rcu/urcu-call-rcu.h
> > > > ===================================================================
> > > > --- userspace-rcu.orig/urcu-call-rcu.h
> > > > +++ userspace-rcu/urcu-call-rcu.h
> > > > @@ -64,7 +64,8 @@ struct rcu_head {
> > > >   */
> > > >  struct call_rcu_data *get_cpu_call_rcu_data(int cpu);
> > > >  pthread_t get_call_rcu_thread(struct call_rcu_data *crdp);
> > > > -struct call_rcu_data *create_call_rcu_data(unsigned long flags);
> > > > +struct call_rcu_data *create_call_rcu_data(unsigned long flags,
> > > > +					   int cpu_affinity);
> > > >  int set_cpu_call_rcu_data(int cpu, struct call_rcu_data *crdp);
> > > >  struct call_rcu_data *get_default_call_rcu_data(void);
> > > >  struct call_rcu_data *get_call_rcu_data(void);
> > > > Index: userspace-rcu/urcu-qsbr.c
> > > > ===================================================================
> > > > --- userspace-rcu.orig/urcu-qsbr.c
> > > > +++ userspace-rcu/urcu-qsbr.c
> > > > @@ -23,6 +23,7 @@
> > > >   * IBM's contributions to this file may be relicensed under LGPLv2 or later.
> > > >   */
> > > > 
> > > > +#define _GNU_SOURCE
> > > >  #include <stdio.h>
> > > >  #include <pthread.h>
> > > >  #include <signal.h>
> > > > Index: userspace-rcu/urcu.c
> > > > ===================================================================
> > > > --- userspace-rcu.orig/urcu.c
> > > > +++ userspace-rcu/urcu.c
> > > > @@ -24,6 +24,7 @@
> > > >   */
> > > > 
> > > >  #define _BSD_SOURCE
> > > > +#define _GNU_SOURCE
> > > >  #include <stdio.h>
> > > >  #include <pthread.h>
> > > >  #include <signal.h>
> > > > 
> > 
> > -- 
> > Mathieu Desnoyers
> > Operating System Efficiency R&D Consultant
> > EfficiOS Inc.
> > http://www.efficios.com

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] [rp] [URCU RFC patch 3/3] call_rcu: remove delay for wakeup scheme

[Phil Howard]

On Mon, Jun 6, 2011 at 12:21 PM, Mathieu Desnoyers
<mathieu.desnoyers at efficios.com> wrote:
> * Mathieu Desnoyers (mathieu.desnoyers at efficios.com) wrote:
>> I notice that the "poll(NULL, 0, 10);" delay is executed both for the RT
>> and non-RT code. ?So given that my goal is to get the call_rcu thread to
>> GC memory as quickly as possible to diminish the overhead of cache
>> misses, I decided to try removing this delay for !RT: the call_rcu
>> thread then wakes up ASAP when the thread invoking call_rcu wakes it. My
>> updates jump to 76349/s (getting there!) ;).
>>
>> This improvement can be explained by a lower delay between call_rcu and
>> execution of its callback, which decrease the amount of cache used, and
>> therefore provides better cache locality.
>
> I just wonder if it's worth it: removing this delay from the !RT
> call_rcu thread can cause high-rate of synchronize_rcu() calls. So
> although there might be an advantage in terms of update rate, it will
> likely cause extra cache-line bounces between the call_rcu threads and
> the reader threads.
>
> test_urcu_rbtree 7 1 20 -g 1000000
>
> With the delay in the call_rcu thread:
> search: ?1842857 items/reader thread/s (7 reader threads)
> updates: ? 21066 items/s (1 update thread)
> ratio: 87 search/update
>
> Without the delay in the call_rcu thread:
> search: ?3064285 items/reader thread/s (7 reader threads)
> updates: ? 45096 items/s (1 update thread)
> ratio: 68 search/update
>
> So basically, adding the delay doubles the update performance, at the
> cost of being 33% slower for reads. My first thought is that if an
> application has very frequent updates, then maybe it wants to have fast
> updates because the update throughput is then important. If the
> application has infrequent updates, then the reads will be fast anyway,
> because rare call_rcu invocation will trigger less cache-line bounce
> between readers and writers. Any other thoughts on this trade-off and
> how to deal with it ?
>

Did I miss something here? It looks like you more than doubled the
update rate and almost doubled the lookup rate. The search/update
ration is less, but if both the raw rates improved so much, how is
this a bad thing?

-phil

> Thanks,
>
> Mathieu
>
>
>>
>> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
>> ---
>> ?urcu-call-rcu-impl.h | ? ?3 ++-
>> ?1 file changed, 2 insertions(+), 1 deletion(-)
>>
>> Index: userspace-rcu/urcu-call-rcu-impl.h
>> ===================================================================
>> --- userspace-rcu.orig/urcu-call-rcu-impl.h
>> +++ userspace-rcu/urcu-call-rcu-impl.h
>> @@ -242,7 +242,8 @@ static void *call_rcu_thread(void *arg)
>> ? ? ? ? ? ? ? else {
>> ? ? ? ? ? ? ? ? ? ? ? if (&crdp->cbs.head == _CMM_LOAD_SHARED(crdp->cbs.tail))
>> ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? call_rcu_wait(crdp);
>> - ? ? ? ? ? ? ? ? ? ? poll(NULL, 0, 10);
>> + ? ? ? ? ? ? ? ? ? ? else
>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? poll(NULL, 0, 10);
>> ? ? ? ? ? ? ? }
>> ? ? ? }
>> ? ? ? call_rcu_lock(&crdp->mtx);
>>
>
> --
> Mathieu Desnoyers
> Operating System Efficiency R&D Consultant
> EfficiOS Inc.
> http://www.efficios.com
>
> _______________________________________________
> rp mailing list
> rp at svcs.cs.pdx.edu
> http://svcs.cs.pdx.edu/mailman/listinfo/rp
>

[ltt-dev] [rp] [URCU RFC patch 3/3] call_rcu: remove delay for wakeup scheme

[Phil Howard]

On Mon, Jun 6, 2011 at 12:41 PM, Paul E. McKenney
<paulmck at linux.vnet.ibm.com> wrote:
> On Mon, Jun 06, 2011 at 03:21:07PM -0400, Mathieu Desnoyers wrote:
>> * Mathieu Desnoyers (mathieu.desnoyers at efficios.com) wrote:
>> > I notice that the "poll(NULL, 0, 10);" delay is executed both for the RT
>> > and non-RT code. ?So given that my goal is to get the call_rcu thread to
>> > GC memory as quickly as possible to diminish the overhead of cache
>> > misses, I decided to try removing this delay for !RT: the call_rcu
>> > thread then wakes up ASAP when the thread invoking call_rcu wakes it. My
>> > updates jump to 76349/s (getting there!) ;).
>> >
>> > This improvement can be explained by a lower delay between call_rcu and
>> > execution of its callback, which decrease the amount of cache used, and
>> > therefore provides better cache locality.
>>
>> I just wonder if it's worth it: removing this delay from the !RT
>> call_rcu thread can cause high-rate of synchronize_rcu() calls. So
>> although there might be an advantage in terms of update rate, it will
>> likely cause extra cache-line bounces between the call_rcu threads and
>> the reader threads.
>>
>> test_urcu_rbtree 7 1 20 -g 1000000
>>
>> With the delay in the call_rcu thread:
>> search: ?1842857 items/reader thread/s (7 reader threads)
>> updates: ? 21066 items/s (1 update thread)
>> ratio: 87 search/update
>>
>> Without the delay in the call_rcu thread:
>> search: ?3064285 items/reader thread/s (7 reader threads)
>> updates: ? 45096 items/s (1 update thread)
>> ratio: 68 search/update
>>
>> So basically, adding the delay doubles the update performance, at the
>> cost of being 33% slower for reads. My first thought is that if an
>> application has very frequent updates, then maybe it wants to have fast
>> updates because the update throughput is then important. If the
>> application has infrequent updates, then the reads will be fast anyway,
>> because rare call_rcu invocation will trigger less cache-line bounce
>> between readers and writers. Any other thoughts on this trade-off and
>> how to deal with it ?
>
> One approach would be to let the user handle it using real-time
> priority adjustment. ?Another approach would be to let the user
> specify the wait time in milliseconds, and skip the poll() system
> call if the specified wait time is zero.
>
> The latter seems more sane to me. ?It also allows the user to
> specify (say) 10000 milliseconds for cases where there is a
> lot of memory and where amortizing synchronize_rcu() overhead
> across a large number of updates is important.
>
> Other thoughts?
>
> ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?Thanx, Paul

If synchronize_rcu is used to time memory reclamation, then trading
memory for overhead is a valid way to think of this timing. But if
synchronize_rcu is required inside an update for other purposes (e.g.
my RBTree algorithm or Josh's hash table resize), then the trade-off
needs to include synchronize_rcu overhead vs. update throughput.

-phil

>
>> Thanks,
>>
>> Mathieu
>>
>>
>> >
>> > Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
>> > ---
>> > ?urcu-call-rcu-impl.h | ? ?3 ++-
>> > ?1 file changed, 2 insertions(+), 1 deletion(-)
>> >
>> > Index: userspace-rcu/urcu-call-rcu-impl.h
>> > ===================================================================
>> > --- userspace-rcu.orig/urcu-call-rcu-impl.h
>> > +++ userspace-rcu/urcu-call-rcu-impl.h
>> > @@ -242,7 +242,8 @@ static void *call_rcu_thread(void *arg)
>> > ? ? ? ? ? ? else {
>> > ? ? ? ? ? ? ? ? ? ? if (&crdp->cbs.head == _CMM_LOAD_SHARED(crdp->cbs.tail))
>> > ? ? ? ? ? ? ? ? ? ? ? ? ? ? call_rcu_wait(crdp);
>> > - ? ? ? ? ? ? ? ? ? poll(NULL, 0, 10);
>> > + ? ? ? ? ? ? ? ? ? else
>> > + ? ? ? ? ? ? ? ? ? ? ? ? ? poll(NULL, 0, 10);
>> > ? ? ? ? ? ? }
>> > ? ? }
>> > ? ? call_rcu_lock(&crdp->mtx);
>> >
>>
>> --
>> Mathieu Desnoyers
>> Operating System Efficiency R&D Consultant
>> EfficiOS Inc.
>> http://www.efficios.com
>
> _______________________________________________
> rp mailing list
> rp at svcs.cs.pdx.edu
> http://svcs.cs.pdx.edu/mailman/listinfo/rp
>

[ltt-dev] [rp] [URCU RFC patch 3/3] call_rcu: remove delay for wakeup scheme

[Paul E. McKenney]

On Mon, Jun 06, 2011 at 02:29:01PM -0700, Phil Howard wrote:
> On Mon, Jun 6, 2011 at 12:41 PM, Paul E. McKenney
> <paulmck at linux.vnet.ibm.com> wrote:
> > On Mon, Jun 06, 2011 at 03:21:07PM -0400, Mathieu Desnoyers wrote:
> >> * Mathieu Desnoyers (mathieu.desnoyers at efficios.com) wrote:
> >> > I notice that the "poll(NULL, 0, 10);" delay is executed both for the RT
> >> > and non-RT code. ?So given that my goal is to get the call_rcu thread to
> >> > GC memory as quickly as possible to diminish the overhead of cache
> >> > misses, I decided to try removing this delay for !RT: the call_rcu
> >> > thread then wakes up ASAP when the thread invoking call_rcu wakes it. My
> >> > updates jump to 76349/s (getting there!) ;).
> >> >
> >> > This improvement can be explained by a lower delay between call_rcu and
> >> > execution of its callback, which decrease the amount of cache used, and
> >> > therefore provides better cache locality.
> >>
> >> I just wonder if it's worth it: removing this delay from the !RT
> >> call_rcu thread can cause high-rate of synchronize_rcu() calls. So
> >> although there might be an advantage in terms of update rate, it will
> >> likely cause extra cache-line bounces between the call_rcu threads and
> >> the reader threads.
> >>
> >> test_urcu_rbtree 7 1 20 -g 1000000
> >>
> >> With the delay in the call_rcu thread:
> >> search: ?1842857 items/reader thread/s (7 reader threads)
> >> updates: ? 21066 items/s (1 update thread)
> >> ratio: 87 search/update
> >>
> >> Without the delay in the call_rcu thread:
> >> search: ?3064285 items/reader thread/s (7 reader threads)
> >> updates: ? 45096 items/s (1 update thread)
> >> ratio: 68 search/update
> >>
> >> So basically, adding the delay doubles the update performance, at the
> >> cost of being 33% slower for reads. My first thought is that if an
> >> application has very frequent updates, then maybe it wants to have fast
> >> updates because the update throughput is then important. If the
> >> application has infrequent updates, then the reads will be fast anyway,
> >> because rare call_rcu invocation will trigger less cache-line bounce
> >> between readers and writers. Any other thoughts on this trade-off and
> >> how to deal with it ?
> >
> > One approach would be to let the user handle it using real-time
> > priority adjustment. ?Another approach would be to let the user
> > specify the wait time in milliseconds, and skip the poll() system
> > call if the specified wait time is zero.
> >
> > The latter seems more sane to me. ?It also allows the user to
> > specify (say) 10000 milliseconds for cases where there is a
> > lot of memory and where amortizing synchronize_rcu() overhead
> > across a large number of updates is important.
> >
> > Other thoughts?
> >
> > ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?Thanx, Paul
> 
> If synchronize_rcu is used to time memory reclamation, then trading
> memory for overhead is a valid way to think of this timing. But if
> synchronize_rcu is required inside an update for other purposes (e.g.
> my RBTree algorithm or Josh's hash table resize), then the trade-off
> needs to include synchronize_rcu overhead vs. update throughput.

But this patch does not affect synchronize_rcu(), just call_rcu().

That said, your point on raw results vs. ratio in your other email
are well-taken.

						Thanx, Paul

> -phil
> 
> >
> >> Thanks,
> >>
> >> Mathieu
> >>
> >>
> >> >
> >> > Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> >> > ---
> >> > ?urcu-call-rcu-impl.h | ? ?3 ++-
> >> > ?1 file changed, 2 insertions(+), 1 deletion(-)
> >> >
> >> > Index: userspace-rcu/urcu-call-rcu-impl.h
> >> > ===================================================================
> >> > --- userspace-rcu.orig/urcu-call-rcu-impl.h
> >> > +++ userspace-rcu/urcu-call-rcu-impl.h
> >> > @@ -242,7 +242,8 @@ static void *call_rcu_thread(void *arg)
> >> > ? ? ? ? ? ? else {
> >> > ? ? ? ? ? ? ? ? ? ? if (&crdp->cbs.head == _CMM_LOAD_SHARED(crdp->cbs.tail))
> >> > ? ? ? ? ? ? ? ? ? ? ? ? ? ? call_rcu_wait(crdp);
> >> > - ? ? ? ? ? ? ? ? ? poll(NULL, 0, 10);
> >> > + ? ? ? ? ? ? ? ? ? else
> >> > + ? ? ? ? ? ? ? ? ? ? ? ? ? poll(NULL, 0, 10);
> >> > ? ? ? ? ? ? }
> >> > ? ? }
> >> > ? ? call_rcu_lock(&crdp->mtx);
> >> >
> >>
> >> --
> >> Mathieu Desnoyers
> >> Operating System Efficiency R&D Consultant
> >> EfficiOS Inc.
> >> http://www.efficios.com
> >
> > _______________________________________________
> > rp mailing list
> > rp at svcs.cs.pdx.edu
> > http://svcs.cs.pdx.edu/mailman/listinfo/rp
> >

[ltt-dev] [rp] [URCU RFC patch 3/3] call_rcu: remove delay for wakeup scheme

[Mathieu Desnoyers]

* Phil Howard (pwh at cecs.pdx.edu) wrote:
> On Mon, Jun 6, 2011 at 12:21 PM, Mathieu Desnoyers
> <mathieu.desnoyers at efficios.com> wrote:
> > * Mathieu Desnoyers (mathieu.desnoyers at efficios.com) wrote:
> >> I notice that the "poll(NULL, 0, 10);" delay is executed both for the RT
> >> and non-RT code. ?So given that my goal is to get the call_rcu thread to
> >> GC memory as quickly as possible to diminish the overhead of cache
> >> misses, I decided to try removing this delay for !RT: the call_rcu
> >> thread then wakes up ASAP when the thread invoking call_rcu wakes it. My
> >> updates jump to 76349/s (getting there!) ;).
> >>
> >> This improvement can be explained by a lower delay between call_rcu and
> >> execution of its callback, which decrease the amount of cache used, and
> >> therefore provides better cache locality.
> >
> > I just wonder if it's worth it: removing this delay from the !RT
> > call_rcu thread can cause high-rate of synchronize_rcu() calls. So
> > although there might be an advantage in terms of update rate, it will
> > likely cause extra cache-line bounces between the call_rcu threads and
> > the reader threads.
> >
> > test_urcu_rbtree 7 1 20 -g 1000000
> >
> > With the delay in the call_rcu thread:
> > search: ?1842857 items/reader thread/s (7 reader threads)
> > updates: ? 21066 items/s (1 update thread)
> > ratio: 87 search/update
> >
> > Without the delay in the call_rcu thread:
> > search: ?3064285 items/reader thread/s (7 reader threads)
> > updates: ? 45096 items/s (1 update thread)
> > ratio: 68 search/update
> >
> > So basically, adding the delay doubles the update performance, at the
> > cost of being 33% slower for reads. My first thought is that if an
> > application has very frequent updates, then maybe it wants to have fast
> > updates because the update throughput is then important. If the
> > application has infrequent updates, then the reads will be fast anyway,
> > because rare call_rcu invocation will trigger less cache-line bounce
> > between readers and writers. Any other thoughts on this trade-off and
> > how to deal with it ?
> >
> 
> Did I miss something here? It looks like you more than doubled the
> update rate and almost doubled the lookup rate. The search/update
> ration is less, but if both the raw rates improved so much, how is
> this a bad thing?

Actually, my discussion of the results was good, but the I mis-entered
the raw results. Here is the re-run of the tests, with the results well
entered this time. I notice that on repeated runs, the update rates
seems to be much closer between delay vs no-delay than the original
difference I noticed.

test_urcu_rbtree 7 1 20 -g 1000000

With the delay in the call_rcu thread:
search: ?3064285 items/reader thread/s (7 reader threads)
updates: ? 43051 items/s (1 update thread)
ratio:        71 search/update

Without the delay in the call_rcu thread:
search: ?1550000 items/reader thread/s (7 reader threads)
updates:   47221 items/s (1 update thread)
ratio:       33 search/update

So removing the delay seems to hurt read performance quite a lot, and
does not benefit updates as much as I initially thought (it's only
9.6%). I would be tempted to just leave the delay in place for !RT case
then.

Thanks,

Mathieu


-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] [rp] [URCU RFC patch 3/3] call_rcu: remove delay for wakeup scheme

[Mathieu Desnoyers]

* Phil Howard (pwh at cecs.pdx.edu) wrote:
> On Mon, Jun 6, 2011 at 12:41 PM, Paul E. McKenney
> <paulmck at linux.vnet.ibm.com> wrote:
> > On Mon, Jun 06, 2011 at 03:21:07PM -0400, Mathieu Desnoyers wrote:
> >> * Mathieu Desnoyers (mathieu.desnoyers at efficios.com) wrote:
> >> > I notice that the "poll(NULL, 0, 10);" delay is executed both for the RT
> >> > and non-RT code. ?So given that my goal is to get the call_rcu thread to
> >> > GC memory as quickly as possible to diminish the overhead of cache
> >> > misses, I decided to try removing this delay for !RT: the call_rcu
> >> > thread then wakes up ASAP when the thread invoking call_rcu wakes it. My
> >> > updates jump to 76349/s (getting there!) ;).
> >> >
> >> > This improvement can be explained by a lower delay between call_rcu and
> >> > execution of its callback, which decrease the amount of cache used, and
> >> > therefore provides better cache locality.
> >>
> >> I just wonder if it's worth it: removing this delay from the !RT
> >> call_rcu thread can cause high-rate of synchronize_rcu() calls. So
> >> although there might be an advantage in terms of update rate, it will
> >> likely cause extra cache-line bounces between the call_rcu threads and
> >> the reader threads.
> >>
> >> test_urcu_rbtree 7 1 20 -g 1000000
> >>
> >> With the delay in the call_rcu thread:
> >> search: ?1842857 items/reader thread/s (7 reader threads)
> >> updates: ? 21066 items/s (1 update thread)
> >> ratio: 87 search/update
> >>
> >> Without the delay in the call_rcu thread:
> >> search: ?3064285 items/reader thread/s (7 reader threads)
> >> updates: ? 45096 items/s (1 update thread)
> >> ratio: 68 search/update
> >>
> >> So basically, adding the delay doubles the update performance, at the
> >> cost of being 33% slower for reads. My first thought is that if an
> >> application has very frequent updates, then maybe it wants to have fast
> >> updates because the update throughput is then important. If the
> >> application has infrequent updates, then the reads will be fast anyway,
> >> because rare call_rcu invocation will trigger less cache-line bounce
> >> between readers and writers. Any other thoughts on this trade-off and
> >> how to deal with it ?
> >
> > One approach would be to let the user handle it using real-time
> > priority adjustment. ?Another approach would be to let the user
> > specify the wait time in milliseconds, and skip the poll() system
> > call if the specified wait time is zero.
> >
> > The latter seems more sane to me. ?It also allows the user to
> > specify (say) 10000 milliseconds for cases where there is a
> > lot of memory and where amortizing synchronize_rcu() overhead
> > across a large number of updates is important.
> >
> > Other thoughts?
> >
> > ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?Thanx, Paul
> 
> If synchronize_rcu is used to time memory reclamation, then trading
> memory for overhead is a valid way to think of this timing. But if
> synchronize_rcu is required inside an update for other purposes (e.g.
> my RBTree algorithm or Josh's hash table resize), then the trade-off
> needs to include synchronize_rcu overhead vs. update throughput.

I've got some thoughts about use of synchronize_rcu() within the
algorithms, which can be summed up by "let's try not to do that". ;)
We'll see how far I can get in terms of update performance without
relying on synchronize_rcu() within my rbtree updates.

As far as hash tables are concerned, I might find time to tackle this
problem later on with a similar mindset.

Thanks !

Mathieu

> 
> -phil
> 
> >
> >> Thanks,
> >>
> >> Mathieu
> >>
> >>
> >> >
> >> > Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> >> > ---
> >> > ?urcu-call-rcu-impl.h | ? ?3 ++-
> >> > ?1 file changed, 2 insertions(+), 1 deletion(-)
> >> >
> >> > Index: userspace-rcu/urcu-call-rcu-impl.h
> >> > ===================================================================
> >> > --- userspace-rcu.orig/urcu-call-rcu-impl.h
> >> > +++ userspace-rcu/urcu-call-rcu-impl.h
> >> > @@ -242,7 +242,8 @@ static void *call_rcu_thread(void *arg)
> >> > ? ? ? ? ? ? else {
> >> > ? ? ? ? ? ? ? ? ? ? if (&crdp->cbs.head == _CMM_LOAD_SHARED(crdp->cbs.tail))
> >> > ? ? ? ? ? ? ? ? ? ? ? ? ? ? call_rcu_wait(crdp);
> >> > - ? ? ? ? ? ? ? ? ? poll(NULL, 0, 10);
> >> > + ? ? ? ? ? ? ? ? ? else
> >> > + ? ? ? ? ? ? ? ? ? ? ? ? ? poll(NULL, 0, 10);
> >> > ? ? ? ? ? ? }
> >> > ? ? }
> >> > ? ? call_rcu_lock(&crdp->mtx);
> >> >
> >>
> >> --
> >> Mathieu Desnoyers
> >> Operating System Efficiency R&D Consultant
> >> EfficiOS Inc.
> >> http://www.efficios.com
> >
> > _______________________________________________
> > rp mailing list
> > rp at svcs.cs.pdx.edu
> > http://svcs.cs.pdx.edu/mailman/listinfo/rp
> >

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] [rp] [URCU RFC patch 2/3] call_rcu: use futex for wakeup scheme

[Mathieu Desnoyers]

* Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> On Mon, Jun 06, 2011 at 01:46:00PM -0400, Mathieu Desnoyers wrote:
> > If I remove the URCU_CALL_RCU_RT flag from the rbtree single writer
> > test, thus using the pthread_cond_signal mechanism, there is a huge
> > slowdown: without cpu affinity for the worker threads, it crawls to 129
> > updates/s (looks like mutex contention between the thread calling
> > call_rcu and the call_rcu thread). Adding CPU affinity to the per-cpu
> > call_rcu threads, I get 546 updates/s, which is slightly better (better
> > cache locality, and maybe the mutex contention is not as bad thanks to
> > the two threads sharing the same CPU).
> > 
> > So I decided to try replacing pthread_cond_wait/signal with my
> > futex-based implementation I use for the rest of the urcu lib: it has
> > the advantage of removing the mutex from the call_rcu() execution
> > entirely, sampling the "futex" variable without any mutex whatsoever for
> > the case where no wakeup is needed.
> > 
> > Disabling URCU_CALL_RCU_RT flag, with per-cpu affined call_rcu threads,
> > with my futex-based wakeup implementation, I get 55754 updates/s (even
> > better than with URCU_CALL_RCU_RT flag!).
> 
> Assuming that compat_futex.c handles the non-Linux case, works for me!

OK, patch merged. Thanks!

Mathieu

> 
> 							Thanx, Paul
> 
> > Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> > ---
> >  urcu-call-rcu-impl.h |   56 +++++++++++++++++++++++++--------------------------
> >  1 file changed, 28 insertions(+), 28 deletions(-)
> > 
> > Index: userspace-rcu/urcu-call-rcu-impl.h
> > ===================================================================
> > --- userspace-rcu.orig/urcu-call-rcu-impl.h
> > +++ userspace-rcu/urcu-call-rcu-impl.h
> > @@ -39,6 +39,7 @@
> >  #include "urcu-call-rcu.h"
> >  #include "urcu-pointer.h"
> >  #include "urcu/list.h"
> > +#include "urcu/urcu-futex.h"
> > 
> >  /* Data structure that identifies a call_rcu thread. */
> > 
> > @@ -46,7 +47,7 @@ struct call_rcu_data {
> >  	struct cds_wfq_queue cbs;
> >  	unsigned long flags;
> >  	pthread_mutex_t mtx;
> > -	pthread_cond_t cond;
> > +	int futex;
> >  	unsigned long qlen;
> >  	pthread_t tid;
> >  	int cpu_affinity;
> > @@ -88,6 +89,26 @@ static struct call_rcu_data *default_cal
> >  static struct call_rcu_data **per_cpu_call_rcu_data;
> >  static long maxcpus;
> > 
> > +static void call_rcu_wait(struct call_rcu_data *crdp)
> > +{
> > +	/* Read call_rcu list before read futex */
> > +	cmm_smp_mb();
> > +	if (uatomic_read(&crdp->futex) == -1)
> > +		futex_async(&crdp->futex, FUTEX_WAIT, -1,
> > +		      NULL, NULL, 0);
> > +}
> > +
> > +static void call_rcu_wake_up(struct call_rcu_data *crdp)
> > +{
> > +	/* Write to call_rcu list before reading/writing futex */
> > +	cmm_smp_mb();
> > +	if (unlikely(uatomic_read(&crdp->futex) == -1)) {
> > +		uatomic_set(&crdp->futex, 0);
> > +		futex_async(&crdp->futex, FUTEX_WAKE, 1,
> > +		      NULL, NULL, 0);
> > +	}
> > +}
> > +
> >  /* Allocate the array if it has not already been allocated. */
> > 
> >  static void alloc_cpu_call_rcu_data(void)
> > @@ -219,19 +240,9 @@ static void *call_rcu_thread(void *arg)
> >  		if (crdp->flags & URCU_CALL_RCU_RT)
> >  			poll(NULL, 0, 10);
> >  		else {
> > -			call_rcu_lock(&crdp->mtx);
> > -			_CMM_STORE_SHARED(crdp->flags,
> > -				     crdp->flags & ~URCU_CALL_RCU_RUNNING);
> > -			if (&crdp->cbs.head ==
> > -			    _CMM_LOAD_SHARED(crdp->cbs.tail) &&
> > -			    pthread_cond_wait(&crdp->cond, &crdp->mtx) != 0) {
> > -				perror("pthread_cond_wait");
> > -				exit(-1);
> > -			}
> > -			_CMM_STORE_SHARED(crdp->flags,
> > -				     crdp->flags | URCU_CALL_RCU_RUNNING);
> > +			if (&crdp->cbs.head == _CMM_LOAD_SHARED(crdp->cbs.tail))
> > +				call_rcu_wait(crdp);
> >  			poll(NULL, 0, 10);
> > -			call_rcu_unlock(&crdp->mtx);
> >  		}
> >  	}
> >  	call_rcu_lock(&crdp->mtx);
> > @@ -264,11 +275,8 @@ static void call_rcu_data_init(struct ca
> >  		perror("pthread_mutex_init");
> >  		exit(-1);
> >  	}
> > -	if (pthread_cond_init(&crdp->cond, NULL) != 0) {
> > -		perror("pthread_cond_init");
> > -		exit(-1);
> > -	}
> > -	crdp->flags = flags | URCU_CALL_RCU_RUNNING;
> > +	crdp->futex = 0;
> > +	crdp->flags = flags;
> >  	cds_list_add(&crdp->list, &call_rcu_data_list);
> >  	crdp->cpu_affinity = cpu_affinity;
> >  	cmm_smp_mb();  /* Structure initialized before pointer is planted. */
> > @@ -492,16 +500,8 @@ int create_all_cpu_call_rcu_data(unsigne
> >   */
> >  static void wake_call_rcu_thread(struct call_rcu_data *crdp)
> >  {
> > -	if (!(_CMM_LOAD_SHARED(crdp->flags) & URCU_CALL_RCU_RT)) {
> > -		call_rcu_lock(&crdp->mtx);
> > -		if (!(_CMM_LOAD_SHARED(crdp->flags) & URCU_CALL_RCU_RUNNING)) {
> > -			if (pthread_cond_signal(&crdp->cond) != 0) {
> > -				perror("pthread_cond_signal");
> > -				exit(-1);
> > -			}
> > -		}
> > -		call_rcu_unlock(&crdp->mtx);
> > -	}
> > +	if (!(_CMM_LOAD_SHARED(crdp->flags) & URCU_CALL_RCU_RT))
> > +		call_rcu_wake_up(crdp);
> >  }
> > 
> >  /*
> > 
> > 
> > _______________________________________________
> > rp mailing list
> > rp at svcs.cs.pdx.edu
> > http://svcs.cs.pdx.edu/mailman/listinfo/rp

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] [URCU RFC patch 2/3] call_rcu: use futex for wakeup scheme

[Paolo Bonzini]

On 06/06/2011 07:46 PM, Mathieu Desnoyers wrote:
> +static void call_rcu_wait(struct call_rcu_data *crdp)
> +{
> +	/* Read call_rcu list before read futex */
> +	cmm_smp_mb();
> +	if (uatomic_read(&crdp->futex) == -1)
> +		futex_async(&crdp->futex, FUTEX_WAIT, -1,
> +		      NULL, NULL, 0);
> +}
> +
> +static void call_rcu_wake_up(struct call_rcu_data *crdp)
> +{
> +	/* Write to call_rcu list before reading/writing futex */
> +	cmm_smp_mb();
> +	if (unlikely(uatomic_read(&crdp->futex) == -1)) {
> +		uatomic_set(&crdp->futex, 0);
> +		futex_async(&crdp->futex, FUTEX_WAKE, 1,
> +		      NULL, NULL, 0);
> +	}
> +}

I don't see crdp->futex ever set to -1, am I missing something obvious?

Paolo

[ltt-dev] [URCU RFC patch 2/3] call_rcu: use futex for wakeup scheme

[Mathieu Desnoyers]

* Paolo Bonzini (pbonzini at redhat.com) wrote:
> On 06/06/2011 07:46 PM, Mathieu Desnoyers wrote:
>> +static void call_rcu_wait(struct call_rcu_data *crdp)
>> +{
>> +	/* Read call_rcu list before read futex */
>> +	cmm_smp_mb();
>> +	if (uatomic_read(&crdp->futex) == -1)
>> +		futex_async(&crdp->futex, FUTEX_WAIT, -1,
>> +		      NULL, NULL, 0);
>> +}
>> +
>> +static void call_rcu_wake_up(struct call_rcu_data *crdp)
>> +{
>> +	/* Write to call_rcu list before reading/writing futex */
>> +	cmm_smp_mb();
>> +	if (unlikely(uatomic_read(&crdp->futex) == -1)) {
>> +		uatomic_set(&crdp->futex, 0);
>> +		futex_async(&crdp->futex, FUTEX_WAKE, 1,
>> +		      NULL, NULL, 0);
>> +	}
>> +}
>
> I don't see crdp->futex ever set to -1, am I missing something obvious?


Good catch! I missed those parts from the urcu.c wait/wakeup scheme
(decrement initially, and also set to 0 explicitely when breaking the
loop without waiting). I just added them with commit
c768e45ed336970a42e58e679804f0f455422cd8

Thanks!

Mathieu

>
> Paolo
>
>
> _______________________________________________
> ltt-dev mailing list
> ltt-dev at lists.casi.polymtl.ca
> http://lists.casi.polymtl.ca/cgi-bin/mailman/listinfo/ltt-dev
>

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] [URCU RFC patch 2/3] call_rcu: use futex for wakeup scheme

[Paolo Bonzini]

On 06/09/2011 12:31 AM, Mathieu Desnoyers wrote:
> Good catch! I missed those parts from the urcu.c wait/wakeup scheme
> (decrement initially, and also set to 0 explicitely when breaking the
> loop without waiting). I just added them with commit
> c768e45ed336970a42e58e679804f0f455422cd8

Yes, looks good.

Paolo