urcu.git
12 years agoMerge branch 'master' into urcu/ht-shrink-help
Mathieu Desnoyers [Tue, 13 Sep 2011 21:34:19 +0000 (17:34 -0400)] 
Merge branch 'master' into urcu/ht-shrink-help

Conflicts:
urcu-qsbr.c

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: use single init-time allocation for order table
Mathieu Desnoyers [Tue, 13 Sep 2011 18:44:25 +0000 (14:44 -0400)] 
rculfhash: use single init-time allocation for order table

This simplifies management of hash table resizes. Thanks to Josh
Triplett for suggesting this.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agourcu-qsbr: use rcu_thread_offline/rcu_thread_online instead of inlining them
Paolo Bonzini [Tue, 13 Sep 2011 17:49:28 +0000 (13:49 -0400)] 
urcu-qsbr: use rcu_thread_offline/rcu_thread_online instead of inlining them

* Mathieu Desnoyers wrote:

> Just to let you know that I pushed two updates into urcu: one fixes a
> grace period hang caused by a missing wakeup in the synchronize_rcu
> QSBR code. This appears to hit us due to the more fine-grained wakeup
> code brought by Paolo. The wakeup was really missing from the
> synchronize_rcu code (so Paolo's code just triggered an existing
> problem). I thought it would be good to let you know the effect: grace
> periods are delayed forever. This problem never appeared in a release
> (I caught it before).

Good catch.  Why not use rcu_thread_offline/online in synchronize_rcu,
instead of touching rcu_reader.ctr directly?  I had this in my QEMU
branch but hadn't posted yet because it was meant as a cleanup only.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoPair all_cpu call_rcu create with free
Mathieu Desnoyers [Sun, 11 Sep 2011 06:45:59 +0000 (23:45 -0700)] 
Pair all_cpu call_rcu create with free

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash test: add missing call_rcu per-cpu worker threads teardown
Mathieu Desnoyers [Sun, 11 Sep 2011 06:39:03 +0000 (23:39 -0700)] 
rculfhash test: add missing call_rcu per-cpu worker threads teardown

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: disable poison and remove debugging code
Mathieu Desnoyers [Sun, 11 Sep 2011 06:29:54 +0000 (23:29 -0700)] 
rculfhash: disable poison and remove debugging code

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agocall_rcu: register work threads as rcu readers
Mathieu Desnoyers [Sun, 11 Sep 2011 05:02:58 +0000 (22:02 -0700)] 
call_rcu: register work threads as rcu readers

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoQSBR: add missing wakeups in synchronize_rcu code
Mathieu Desnoyers [Sun, 11 Sep 2011 06:03:09 +0000 (23:03 -0700)] 
QSBR: add missing wakeups in synchronize_rcu code

synchronize_rcu go into offline mode during grace period. It duplicates
the rcu_thread_online/offline code, and therefore adding the required
wake_up_gp() is required there too.

Failure to do so leads to grace period hangs.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoQSBR: add missing wakeups in synchronize_rcu code
Mathieu Desnoyers [Sun, 11 Sep 2011 06:03:09 +0000 (23:03 -0700)] 
QSBR: add missing wakeups in synchronize_rcu code

synchronize_rcu go into offline mode during grace period. It duplicates
the rcu_thread_online/offline code, and therefore adding the required
wake_up_gp() is required there too.

Failure to do so leads to grace period hangs.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: hold rcu read-side lock in resize
Mathieu Desnoyers [Sun, 11 Sep 2011 05:09:55 +0000 (22:09 -0700)] 
rculfhash: hold rcu read-side lock in resize

We need to hold the RCU read-side lock in resize to protect against ABA
caused by re-use of nodes after going through the memory allocator
through a call_rcu performed on another CPU.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agocall_rcu: register work threads as rcu readers
Mathieu Desnoyers [Sun, 11 Sep 2011 05:02:58 +0000 (22:02 -0700)] 
call_rcu: register work threads as rcu readers

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: add list iteration tracer in gc
Mathieu Desnoyers [Sun, 11 Sep 2011 03:53:30 +0000 (20:53 -0700)] 
rculfhash: add list iteration tracer in gc

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: poison memory before free (for testing)
Mathieu Desnoyers [Sun, 11 Sep 2011 02:58:11 +0000 (19:58 -0700)] 
rculfhash: poison memory before free (for testing)

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: reinstate i - 1 for shrink
Mathieu Desnoyers [Sun, 11 Sep 2011 02:33:56 +0000 (19:33 -0700)] 
rculfhash: reinstate i - 1 for shrink

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: add assertion in path compression
Mathieu Desnoyers [Sun, 11 Sep 2011 01:32:45 +0000 (18:32 -0700)] 
rculfhash: add assertion in path compression

Detects incorrect usage of path compression.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: fix fini_table for size 1
Mathieu Desnoyers [Sun, 11 Sep 2011 01:14:59 +0000 (18:14 -0700)] 
rculfhash: fix fini_table for size 1

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: Fix off-by-one in fini_table
Mathieu Desnoyers [Sun, 11 Sep 2011 01:11:56 +0000 (18:11 -0700)] 
rculfhash: Fix off-by-one in fini_table

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: add asserts and comments
Mathieu Desnoyers [Sat, 10 Sep 2011 23:52:53 +0000 (16:52 -0700)] 
rculfhash: add asserts and comments

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agocmm: do not generate code for smp_rmb/smp_wmb on x86_64
Paolo Bonzini [Sat, 10 Sep 2011 19:29:56 +0000 (12:29 -0700)] 
cmm: do not generate code for smp_rmb/smp_wmb on x86_64

We can assume, on x86, that no accesses to write-combining memory occur,
and also that there are no non-temporal load/stores (people would
presumably write those with assembly or intrinsics and put appropriate
lfence/sfence manually). In this case rmb and wmb are no-ops on x86.
according to the updated x86 memory models:

INTEL CORPORATION. Intel 64 Architecture Memory Ordering White Paper,
2007.
http://developer.intel.com/products/processor/manuals/318147.pdf

ADVANCED MICRO DEVICES. AMD x86-64 Architecture Programmer’s Manual
Volume 2: System Programming, 2007.

Paul E. McKenney. Memory Ordering in Modern Microprocessors
www.rdrop.com/users/paulmck/scalability/paper/ordering.2007.09.19a.pdf

x86 does not reorder loads vs loads, and stores vs stores when using
normal memory accesses, with the notable exceptions of Pentium Pro
(reorders reads) and WinChip (reorders writes). Therefore, it is safe
not to emit fence instructions for x86_64 cmm_smp_rmb()/cmm_smp_wmb(),
but we leave the memory fences in place for x86_32 for those two
special-cases.

Define cmm_smp_rmb and cmm_smp_wmb to be the "common" operations that
do not require fence instruction, while leaving cmm_rmb and cmm_wmb in
place for more sophisticated uses.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agocmm: let per-arch files provide cmm_smp_* barriers
Paolo Bonzini [Sat, 10 Sep 2011 19:26:19 +0000 (12:26 -0700)] 
cmm: let per-arch files provide cmm_smp_* barriers

x86 instructions lfence and sfence are rarely needed, thus we want
the cmm_smp_rmb/cmm_smp_wmb macros to be simple compiler barriers.
So, let the per-arch files override the default definitions in
arch/generic.h.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash test: -A option for auto resize
Mathieu Desnoyers [Fri, 9 Sep 2011 21:43:58 +0000 (17:43 -0400)] 
rculfhash test: -A option for auto resize

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: Make auto resize selectable with flag
Mathieu Desnoyers [Fri, 9 Sep 2011 21:42:01 +0000 (17:42 -0400)] 
rculfhash: Make auto resize selectable with flag

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoOptimize caa_get_cycles() for PowerPC64
Tulio Magno Quites Machado Filho [Fri, 9 Sep 2011 05:37:11 +0000 (22:37 -0700)] 
Optimize caa_get_cycles() for PowerPC64

Make caa_get_cycles() read from the Time Base register with only 1
instruction.

[ Edit by Mathieu Desnoyers: coding style update ]

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Signed-off-by: Tulio Magno Quites Machado Filho <tuliom@linux.vnet.ibm.com>
12 years agorculfhash: update ascii art
Mathieu Desnoyers [Thu, 8 Sep 2011 19:04:36 +0000 (12:04 -0700)] 
rculfhash: update ascii art

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: set minimum table size, add todo about helping resize
Mathieu Desnoyers [Thu, 8 Sep 2011 17:44:19 +0000 (13:44 -0400)] 
rculfhash: set minimum table size, add todo about helping resize

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: fix 0 order lookup (special-case)
Mathieu Desnoyers [Thu, 8 Sep 2011 16:16:19 +0000 (09:16 -0700)] 
rculfhash: fix 0 order lookup (special-case)

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: simplify dummy node removal
Mathieu Desnoyers [Thu, 8 Sep 2011 05:16:42 +0000 (22:16 -0700)] 
rculfhash: simplify dummy node removal

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: deal with resize to size 1 corner-case
Mathieu Desnoyers [Thu, 8 Sep 2011 00:15:20 +0000 (17:15 -0700)] 
rculfhash: deal with resize to size 1 corner-case

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: allow shrink
Mathieu Desnoyers [Wed, 7 Sep 2011 22:50:05 +0000 (15:50 -0700)] 
rculfhash: allow shrink

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agotest rculfhash: add/remove/random support (with SIGUSR1)
Mathieu Desnoyers [Wed, 7 Sep 2011 16:44:42 +0000 (09:44 -0700)] 
test rculfhash: add/remove/random support (with SIGUSR1)

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: set size instead of max for per-cpu count scheme
Mathieu Desnoyers [Wed, 7 Sep 2011 16:18:26 +0000 (09:18 -0700)] 
rculfhash: set size instead of max for per-cpu count scheme

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: tweak resize thresholds
Mathieu Desnoyers [Wed, 7 Sep 2011 15:58:33 +0000 (08:58 -0700)] 
rculfhash: tweak resize thresholds

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: tweak per-cpu counter resize with thresholds
Mathieu Desnoyers [Wed, 7 Sep 2011 15:48:29 +0000 (08:48 -0700)] 
rculfhash: tweak per-cpu counter resize with thresholds

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorcuhash: lazy per-cpu counters, fix resize target update
Mathieu Desnoyers [Tue, 6 Sep 2011 19:33:34 +0000 (12:33 -0700)] 
rcuhash: lazy per-cpu counters, fix resize target update

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: count nodes (per-cpu) as expand criterion
Mathieu Desnoyers [Tue, 6 Sep 2011 17:44:30 +0000 (13:44 -0400)] 
rculfhash: count nodes (per-cpu) as expand criterion

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agolfq/lfs tests: use call_rcu
Mathieu Desnoyers [Mon, 5 Sep 2011 01:25:21 +0000 (21:25 -0400)] 
lfq/lfs tests: use call_rcu

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoRevert "Add cds_list_empty"
Mathieu Desnoyers [Mon, 5 Sep 2011 00:11:01 +0000 (20:11 -0400)] 
Revert "Add cds_list_empty"

This reverts commit 4b7cab77f3c1c03f021cb0f7e8d150eed3f948e9.

(did duplicate cds_list_empty)

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoAdd cds_list_empty
Mathieu Desnoyers [Mon, 5 Sep 2011 00:07:41 +0000 (20:07 -0400)] 
Add cds_list_empty

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agolist: Add cds_list_first_entry
Mathieu Desnoyers [Sun, 4 Sep 2011 23:48:20 +0000 (19:48 -0400)] 
list: Add cds_list_first_entry

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash test: Check random pool size urcu/ht
Mathieu Desnoyers [Sat, 3 Sep 2011 20:23:24 +0000 (16:23 -0400)] 
rculfhash test: Check random pool size

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: Add initial hash population
Mathieu Desnoyers [Sat, 3 Sep 2011 20:05:12 +0000 (16:05 -0400)] 
rculfhash: Add initial hash population

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: benchmark QSBR flavor
Mathieu Desnoyers [Sat, 3 Sep 2011 19:24:25 +0000 (15:24 -0400)] 
rculfhash: benchmark QSBR flavor

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash test: print number of add fail (uniquify matches)
Mathieu Desnoyers [Sat, 3 Sep 2011 19:04:39 +0000 (15:04 -0400)] 
rculfhash test: print number of add fail (uniquify matches)

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: power power of two check should allow 0
Mathieu Desnoyers [Sat, 3 Sep 2011 18:33:06 +0000 (14:33 -0400)] 
rculfhash: power power of two check should allow 0

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: implement cds_lfht_next
Mathieu Desnoyers [Sat, 3 Sep 2011 16:20:31 +0000 (12:20 -0400)] 
rculfhash: implement cds_lfht_next

Useful for walk traversal of all nodes sharing the same key (lookup +
next until NULL is returned).

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: Update API documentation
Mathieu Desnoyers [Sat, 3 Sep 2011 15:42:44 +0000 (11:42 -0400)] 
rculfhash: Update API documentation

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: Check that init size is power of 2
Mathieu Desnoyers [Sat, 3 Sep 2011 15:42:30 +0000 (11:42 -0400)] 
rculfhash: Check that init size is power of 2

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoUse cds_lfht namespace for lock-free hash table
Mathieu Desnoyers [Sat, 3 Sep 2011 15:37:47 +0000 (11:37 -0400)] 
Use cds_lfht namespace for lock-free hash table

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoRCU hash table API documentation
Mathieu Desnoyers [Sat, 3 Sep 2011 15:16:02 +0000 (11:16 -0400)] 
RCU hash table API documentation

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoMerge branch 'master' into urcu/ht
Mathieu Desnoyers [Sat, 3 Sep 2011 14:48:44 +0000 (10:48 -0400)] 
Merge branch 'master' into urcu/ht

Conflicts:
Makefile.am

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfstack/queue: define _LGPL_SOURCE around static header include
Mathieu Desnoyers [Sat, 3 Sep 2011 14:07:41 +0000 (10:07 -0400)] 
rculfstack/queue: define _LGPL_SOURCE around static header include

... so the urcu-pointer header takes the LGPL version of rcu_dereference
and friends.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoRevert "Create per RCU flavor CDS libraries"
Mathieu Desnoyers [Sat, 3 Sep 2011 13:49:07 +0000 (09:49 -0400)] 
Revert "Create per RCU flavor CDS libraries"

This reverts commit d4b99c015229978810319cfd42e1c9763772fad8.

Minor change (not visible to end-users): this commit introduces a
liburcu-common.so to hold wfqueue, wfstack and futex fall-back code.
This .so is used by all URCU flavors, as well as liburcu-cds.so.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoRevert "CDS API: removal of rcu_read lock/unlock dep, removal of call_rcu argument...
Mathieu Desnoyers [Sat, 3 Sep 2011 13:15:14 +0000 (09:15 -0400)] 
Revert "CDS API: removal of rcu_read lock/unlock dep, removal of call_rcu argument from init"

This reverts commit 7618919ae496bda84a2efa4f2ad0abe569892a9e.

Rationale:

I thought about it some more, and had discussions with various people,
and there are a few reasons to go for a scheme where rcu read lock
should be taken by the caller, and to pass call_rcu as a parameter to
the data structure init function:

A) The advantage, as Paul E. McKenney pointed out, is that one single .so
   is enough to support all RCU flavors. Very convenient for external data
   structure containers.

B) It clearly documents where rcu read-side locks are needed, so the user
   keep control and in-depth understanding of their read-side locks.

C) When multiple API functions that require RCU read-side lock to be
   held (sometimes even the same lock) throughout a sequence of API
   calls, we have no choice but to let the caller hold the read-side
   lock.

D) Due to support of multiple nesting of rcu read-side lock, any
   "improvement" we could get by releasing the read-side lock in
   retry loops would vanish in the cases where we are called within
   nested C.S..

E) If a library uses synchronize_rcu, this should be clearly documented,
   and even frowned upon, because this involves important limitations on
   the design of the caller, and important performance hit. There are
   usually ways to reach the same result through use of call_rcu, which
   should really be used thoroughout these libraries.

F) It clearly documents when a data structure needs to use call_rcu
   internally.

G) Some very early benchmark results show that there is indeed not
   much performance gain to achieve by inlining call_rcu, even if it is
   a version with a cache for the "call_rcu structure" lookup
   (per-cpu/per-thread/global). So passing it as a parameter to
   the data structure init function should be fine, even in cases
   where it is called very often.

H) For use-cases where applications would like to use more than one
   RCU flavor concurrently (which is now supported), leaving management
   of RCU read-side C.S. to the reader allows the application to take
   more than one RCU read-side lock across API calls. It also lets the
   application specify its own call_rcu function that could handle more
   than one RCU flavor.

So for all these reasons, I reverting back to the API we have in our
last release (0.6.4).

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoAdd __rcu annotation (unimplemented)
Mathieu Desnoyers [Sat, 3 Sep 2011 12:37:22 +0000 (08:37 -0400)] 
Add __rcu annotation (unimplemented)

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoFix incorrect fsf address in header files
Mathieu Desnoyers [Thu, 1 Sep 2011 20:11:14 +0000 (16:11 -0400)] 
Fix incorrect fsf address in header files

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agowfstack: push returns prior stack emptiness state
Mathieu Desnoyers [Thu, 1 Sep 2011 13:31:55 +0000 (09:31 -0400)] 
wfstack: push returns prior stack emptiness state

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoMake lf stack push return if the stack was empty
Mathieu Desnoyers [Thu, 1 Sep 2011 13:28:30 +0000 (09:28 -0400)] 
Make lf stack push return if the stack was empty

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoDocument caa_container_of
Mathieu Desnoyers [Tue, 23 Aug 2011 21:22:00 +0000 (17:22 -0400)] 
Document caa_container_of

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agourcu-bp: do not call munmap for NULL registry at exit
Mathieu Desnoyers [Sat, 20 Aug 2011 17:50:08 +0000 (13:50 -0400)] 
urcu-bp: do not call munmap for NULL registry at exit

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agourcu libraries can directly use the _LGPL_SOURCE wfqueue
Mathieu Desnoyers [Thu, 18 Aug 2011 17:41:11 +0000 (13:41 -0400)] 
urcu libraries can directly use the _LGPL_SOURCE wfqueue

No need to link dynamically with the data structure object.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfstack: document "push"
Mathieu Desnoyers [Thu, 18 Aug 2011 16:13:44 +0000 (12:13 -0400)] 
rculfstack: document "push"

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoAdd runall.sh to tarball
Mathieu Desnoyers [Wed, 17 Aug 2011 21:58:30 +0000 (17:58 -0400)] 
Add runall.sh to tarball

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoFix build order of liburcu-cds-common
Mathieu Desnoyers [Wed, 17 Aug 2011 21:57:19 +0000 (17:57 -0400)] 
Fix build order of liburcu-cds-common

Caused make install to fail.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoCDS API: removal of rcu_read lock/unlock dep, removal of call_rcu argument from init
Mathieu Desnoyers [Wed, 17 Aug 2011 21:54:33 +0000 (17:54 -0400)] 
CDS API: removal of rcu_read lock/unlock dep, removal of call_rcu argument from init

* API change * for all liburcu-cds* flavors.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoFix missing check for SYS_membarrier in map header
Mathieu Desnoyers [Wed, 17 Aug 2011 21:54:07 +0000 (17:54 -0400)] 
Fix missing check for SYS_membarrier in map header

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoCreate per RCU flavor CDS libraries
Mathieu Desnoyers [Wed, 17 Aug 2011 20:42:20 +0000 (16:42 -0400)] 
Create per RCU flavor CDS libraries

Introduce per-flavor concurrent data structure libraries for data
structures depending on RCU:

liburcu-cds: memb flavor (default), matches -lurcu
liburcu-cds-qsbr: qsbr flavor, matches -lurcu-qsbr
liburcu-cds-mb: mb flavor, matches -lurcu-mb
liburcu-cds-signal, matches -lurcu-signal
liburcu-cds-bp, matches -lurcu-bp

liburcu-cds-common: Data structures not depending on RCU for
synchronization.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoMerge branch 'master' into lfqueue-dev lfqueue-dev
Mathieu Desnoyers [Wed, 17 Aug 2011 10:07:35 +0000 (06:07 -0400)] 
Merge branch 'master' into lfqueue-dev

12 years agourcu-qsbr: avoid useless futex wakeups and burning CPU for long grace periods
Paolo Bonzini [Wed, 17 Aug 2011 09:42:51 +0000 (05:42 -0400)] 
urcu-qsbr: avoid useless futex wakeups and burning CPU for long grace periods

I noticed that urcu makes exactly _one_ attempt at using futexes
to avoid busy looping on synchronize_rcu.  The attached patch instead
switches from busy waiting to futexes after RCU_QS_ACTIVE_ATTEMPTS.
To limit the amount of system calls, reading threads remember whether
they already had a quiescent state in this grace period; if so they were
already removed from the list, and can avoid signaling the futex.

Performance measured with rcutorture (nreaders: 10, nupdaters: 1,
duration: 10, median of nine runs):

     RCU_QS_ACTIVE_ATTEMPTS == 100, no patch         n_updates = 292
     RCU_QS_ACTIVE_ATTEMPTS == 1, no patch           n_updates = 290
     RCU_QS_ACTIVE_ATTEMPTS == 100, with patch       n_updates = 408
     RCU_QS_ACTIVE_ATTEMPTS == 1, with patch         n_updates = 404

(the first two cases are obviously the same; the only change is
when the futex is used, but over many calls there is no difference).

This patch matches the update to the Promela model.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoapi: reimplement BUILD_BUG_ON in compiler.h
Paolo Bonzini [Wed, 17 Aug 2011 09:33:58 +0000 (05:33 -0400)] 
api: reimplement BUILD_BUG_ON in compiler.h

Even though it's just two lines of code, I'm reimplementing it
cleanly out of paranoia.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agotest api cleanup: remove unused primitives
Paolo Bonzini [Wed, 17 Aug 2011 09:31:21 +0000 (05:31 -0400)] 
test api cleanup: remove unused primitives

[ Mathieu: the rationale for this is that we can always add back that
  code if every needed. Removing leftover GPLv2 test code is an
  incentive to create the appropriate library-wide LGPL/MIT-style
  abstractions.]

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoMerge branch 'master' into lfqueue-dev
Mathieu Desnoyers [Wed, 17 Aug 2011 09:28:33 +0000 (05:28 -0400)] 
Merge branch 'master' into lfqueue-dev

12 years agoput thread offline while waiting for the init flag
Paolo Bonzini [Tue, 9 Aug 2011 20:49:27 +0000 (16:49 -0400)] 
put thread offline while waiting for the init flag

Otherwise, the call_rcu thread might end up in a synchronize_rcu that
never ends.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agourcu: move private definitions to .c file
Paolo Bonzini [Tue, 9 Aug 2011 20:44:20 +0000 (16:44 -0400)] 
urcu: move private definitions to .c file

The reader does not and should not know about RCU_QS_ACTIVE_ATTEMPTS
and KICK_READER_LOOPS.  Move the definition to urcu.c.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agourcu-bp: move private definitions to .c file
Paolo Bonzini [Tue, 9 Aug 2011 20:43:21 +0000 (16:43 -0400)] 
urcu-bp: move private definitions to .c file

The reader does not and should not know about RCU_QS_ACTIVE_ATTEMPTS.
Move the definition to urcu-bp.c.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agourcu-qsbr: move private definitions to .c file
Paolo Bonzini [Tue, 9 Aug 2011 20:42:53 +0000 (16:42 -0400)] 
urcu-qsbr: move private definitions to .c file

The reader does not and should not know about RCU_QS_ACTIVE_ATTEMPTS.
Move the definition to urcu-qsbr.c.  Also remove KICK_READER_LOOPS.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorcutorture: fix rcutorture-qsbr
Paolo Bonzini [Tue, 9 Aug 2011 20:40:29 +0000 (16:40 -0400)] 
rcutorture: fix rcutorture-qsbr

rcutorture-qsbr is not marking quiescent states, so it will always
have just one update in the whole test.  Fix it.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agowfqueue: fix type-incorrect assignment
Paolo Bonzini [Tue, 9 Aug 2011 12:37:14 +0000 (08:37 -0400)] 
wfqueue: fix type-incorrect assignment

The "old_tail = q->tail, q->tail = node" assignment in wfqueue
is not type safe; q->tail is a pointer to pointer to node and the
correct value to assign is &node->next.  While the arithmetic is
the same, it is better to be tidy.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoFix tests Makefile EXTRA_DIST to use api.h
Mathieu Desnoyers [Tue, 16 Aug 2011 11:11:16 +0000 (07:11 -0400)] 
Fix tests Makefile EXTRA_DIST to use api.h

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoFix choice of default flavour in urcu/map/urcu.h
Duncan Sands [Tue, 16 Aug 2011 11:10:01 +0000 (07:10 -0400)] 
Fix choice of default flavour in urcu/map/urcu.h

Hi, I noticed in the 0.64 release (and git too) that if a flavour is not
specified explicitly then RCU_MB is chosen in urcu/map/urcu.h, while the
docs say and the Makefile expects RCU_MEMBARRIER.  Note that the header
file urcu/static/urcu.h has similar logic but uses RCU_MEMBARRIER for
the default.

Before this patch:

$ nm *.a | grep rcu_init
00000000000003c0 T rcu_init_mb
00000000000003c0 T rcu_init_mb
0000000000000000 T rcu_init_sig

After this patch:

$ nm *.a | grep rcu_init
00000000000003c0 T rcu_init_memb
00000000000003c0 T rcu_init_mb
0000000000000000 T rcu_init_sig

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoapi: remove list/hlist
Paolo Bonzini [Tue, 16 Aug 2011 10:52:54 +0000 (06:52 -0400)] 
api: remove list/hlist

Remove the parts that actually caused compilation to fail.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoapi: remove arch-specific files
Paolo Bonzini [Tue, 16 Aug 2011 10:51:55 +0000 (06:51 -0400)] 
api: remove arch-specific files

No change since they were a subset of api_gcc.h.  api_gcc.h is
renamed to api.h, and configure need not create a symlink anymore.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoapi: make api_gcc.h a superset of the other headers
Paolo Bonzini [Tue, 16 Aug 2011 10:41:06 +0000 (06:41 -0400)] 
api: make api_gcc.h a superset of the other headers

After this patch the only differences are:

- for_each_tid is now defined in api_x86.h

- HAVE_CPU_SET_T and HAVE_SCHED_SETAFFINITY are now defined in api_ppc.h

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agotests api: remove atomics
Paolo Bonzini [Fri, 12 Aug 2011 22:23:59 +0000 (18:23 -0400)] 
tests api: remove atomics

The code is #if 0'd already, remove it.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoput thread offline while waiting for the init flag
Paolo Bonzini [Tue, 9 Aug 2011 20:49:27 +0000 (16:49 -0400)] 
put thread offline while waiting for the init flag

Otherwise, the call_rcu thread might end up in a synchronize_rcu that
never ends.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agourcu: move private definitions to .c file
Paolo Bonzini [Tue, 9 Aug 2011 20:44:20 +0000 (16:44 -0400)] 
urcu: move private definitions to .c file

The reader does not and should not know about RCU_QS_ACTIVE_ATTEMPTS
and KICK_READER_LOOPS.  Move the definition to urcu.c.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agourcu-bp: move private definitions to .c file
Paolo Bonzini [Tue, 9 Aug 2011 20:43:21 +0000 (16:43 -0400)] 
urcu-bp: move private definitions to .c file

The reader does not and should not know about RCU_QS_ACTIVE_ATTEMPTS.
Move the definition to urcu-bp.c.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agourcu-qsbr: move private definitions to .c file
Paolo Bonzini [Tue, 9 Aug 2011 20:42:53 +0000 (16:42 -0400)] 
urcu-qsbr: move private definitions to .c file

The reader does not and should not know about RCU_QS_ACTIVE_ATTEMPTS.
Move the definition to urcu-qsbr.c.  Also remove KICK_READER_LOOPS.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorcutorture: fix rcutorture-qsbr
Paolo Bonzini [Tue, 9 Aug 2011 20:40:29 +0000 (16:40 -0400)] 
rcutorture: fix rcutorture-qsbr

rcutorture-qsbr is not marking quiescent states, so it will always
have just one update in the whole test.  Fix it.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agowfqueue: fix type-incorrect assignment
Paolo Bonzini [Tue, 9 Aug 2011 12:37:14 +0000 (08:37 -0400)] 
wfqueue: fix type-incorrect assignment

The "old_tail = q->tail, q->tail = node" assignment in wfqueue
is not type safe; q->tail is a pointer to pointer to node and the
correct value to assign is &node->next.  While the arithmetic is
the same, it is better to be tidy.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoMerge branch 'master' into lfqueue-dev
Mathieu Desnoyers [Mon, 8 Aug 2011 15:15:03 +0000 (11:15 -0400)] 
Merge branch 'master' into lfqueue-dev

12 years agoUse caa_ prefix for min() and max()
Mathieu Desnoyers [Tue, 2 Aug 2011 17:22:38 +0000 (13:22 -0400)] 
Use caa_ prefix for min() and max()

Defining min/max macros clashes with C++.

Reported-by: Vegard Nossum <vegard.nossum@gmail.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoVersion 0.6.4, update changelog v0.6.4
Mathieu Desnoyers [Thu, 21 Jul 2011 21:25:43 +0000 (17:25 -0400)] 
Version 0.6.4, update changelog

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoMerge branch 'master' into lfqueue-dev
Mathieu Desnoyers [Thu, 21 Jul 2011 21:17:47 +0000 (17:17 -0400)] 
Merge branch 'master' into lfqueue-dev

12 years agoFix ARM uatomic: missing return in uatomic and/or
Mathieu Desnoyers [Thu, 21 Jul 2011 20:50:42 +0000 (16:50 -0400)] 
Fix ARM uatomic: missing return in uatomic and/or

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: add likely/unlikely annotation
Mathieu Desnoyers [Tue, 12 Jul 2011 19:59:00 +0000 (15:59 -0400)] 
rculfhash: add likely/unlikely annotation

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: document add lock-freedom
Mathieu Desnoyers [Tue, 12 Jul 2011 16:15:06 +0000 (12:15 -0400)] 
rculfhash: document add lock-freedom

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: document node alignment
Mathieu Desnoyers [Tue, 12 Jul 2011 15:59:00 +0000 (11:59 -0400)] 
rculfhash: document node alignment

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: document algorithms
Mathieu Desnoyers [Tue, 12 Jul 2011 15:19:35 +0000 (11:19 -0400)] 
rculfhash: document algorithms

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash test: make teardown more verbose and faster
Mathieu Desnoyers [Mon, 11 Jul 2011 21:56:21 +0000 (17:56 -0400)] 
rculfhash test: make teardown more verbose and faster

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: print resize length (useful as non-debug for now)
Mathieu Desnoyers [Mon, 11 Jul 2011 21:34:05 +0000 (17:34 -0400)] 
rculfhash: print resize length (useful as non-debug for now)

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
This page took 0.040565 seconds and 4 git commands to generate.