Merge branch 'master' into rbtree2

call_rcu: add back delay in list non-empty case

commit bc94ca9bada25f7403e3e859caa241146ae8e338 changed the !RT behavior
slightly: when the list is not empty, it does not wait for a delay
anymore. Add this delay back, to ensure we don't flood the system with
frequent synchronize_rcu() calls, which would slow down readers.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Merge branch 'master' into rbtree2

call_rcu: handle retry without wait correctly

The wait scheme has an implementation problem: if the list is not empty
when the !RT scheme checks for it, it will restart the loop and
decrement the futex (again) without calling call_rcu_wait() (which would
wait until it is set back to 0). So in this case, we can end up
decrementing "futex" to values well below -1.

Fix this by moving the decrement before the loop, and duplicate it after
return from call_rcu_wait() + poll() delay. Also move the "set futex to
0 upon stopping" outside of the loop: this is the only way the loop can
be stopped anyway.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

urcu: fix dependencies on libwfqueue.la

Without this patch, "make -jN" usually fails for N as low as 4.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

urcu_ref: do error checking on urcu_ref_put

Underflow is what you really want to trap.  When you reach urcu_ref_get,
it is already too late.

[Edit: whitespaces -> tab cleanup]

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

use generic-size macros for common implementation of atomic ops

The definition of _uatomic_cmpxchg is different in x86 and other
architectures.  For x86 it is a 4-argument macro, for other
architectures it is a 3-argument function.  This patch makes it easier
to implement atomic operations incrementally (first as a generic version
and then in machine-specific code), which aids testing and
bisectability.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

call_rcu: drop mutex

The mutex is being used only to protect OR accesses to the flags.
Just use atomic operations for that.

[ Edit: this also fixes busy-looping on flags that were previously read
without volatile access, which could lead to never-ending loop given the
appropriate set of compiler optimisations. ]

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

uatomic: add uatomic_and

Only x86 support is arch-specific for now, the rest uses either cmpxchg
or gcc __sync_ builtins.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

uatomic: add uatomic_or

For now, only the version returning void is used.  Also, I am not
providing PPC versions because I would be unable to test it right
now.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Add missing -lwfqueue to add rcu flavors

Otherwise, linking with the flavor .so leads to:

/usr/local/lib/liburcu-bp.so: undefined reference to `cds_wfq_enqueue'
/usr/local/lib/liburcu-bp.so: undefined reference to `cds_wfq_init'
/usr/local/lib/liburcu-bp.so: undefined reference to `cds_wfq_node_init'

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Add a cds_list_del_init()

Needed by some perfbook example code.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Add comment to flag purpose of the ->qlen field

It is write-only, but is needed for debugging purposes.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Merge branch 'master' into rbtree2

call_rcu: fix futex-based wakeup

The initial decrement was missing from the implementation. It now
behaves exactly like the urcu.c wait/wakeup code.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

atomic: fix typo in x86 compat implementation

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

rcutorture: make goflag volatile

Even cmm_barrier may not be enough as a compiler barrier in the presence
of static variables, and cmm_mb would not be either!  The compiler
assumes that calling a function does not clobber static variables if it
can prove that they do not escape (which also implies the correct phase
of the moon).

Rather than sprinkling the code with compiler barriers, I am taking the
easy way out and declaring the variable volatile.  Without this patch,
rcutorture_qsbr never finishes for me (GCC 4.5.0).

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

urcu-qsbr: fix typo

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

urcu-qsbr: fix typo

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Merge remote branch 'origin/master' into rbtree2

call_rcu: use futex for wakeup scheme

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!).

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

call_rcu: use cpu affinity for per-cpu call_rcu threads

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.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

rbtree: Setup per-cpu RCU worker threads in test

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Merge branch 'master' into rbtree2

Conflicts:
Makefile.am

Edited rbtree API to allow rbtree users to specify which call_rcu should
be used.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Document the new call_rcu() primitives.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Make defer_rcu() usable from library using multiple URCU implementations

[ Edit: minor tab to whitespace cleanup ]

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Allow taking address of rcu_read_lock() and rcu_read_unlock()

Also incorporate README feedback from Mathieu and Josh.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Map symbols to allow multiple RCU flavors to be used in one binary

Probably need similar mapping for rcu_defer().  Definitely need
backwards-compatibility mapping for programs compiled against
old versions of the library.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Provide pthread_atfork-friendly interfaces

Provides call_rcu_before_fork() and call_rcu_after_fork_parent() to
go with the existing call_rcu_after_fork_child().

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

rbtree: Use malloc/free directly in test

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Wrap allocation/free into static function

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Update comment

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

rbtree API change: handle node memory allocation internally

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Enable range search tests

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix search range comparison

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Temporarily disable range tests

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix end range test

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

rbtree: test range lookups with larger ranges

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Comment debug facility

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Add explanation about reader vs writer concurrency behavior

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Use larger number pool in test

Prior range was to stress-test collisions.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Update todo comment about memory allocation error

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Add search begin key test

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Range search works

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Recalculate max end values on rotation

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Use comparison function for end/max_end

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

rbtree: Add end recalculation for transplant

Use a "propagation stop" trick to stop propagation of end update within
the branch we are working on.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Add populate_node_end for insertion

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Remove incorrectly duplicated set_left/set_right

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Rename node fields to begin/end

This states the inclusiveness (begin) and exclusiveness (end) more
explicitely.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

RBtree: Drop initial range support

Will be reimplemented with ranges within nodes.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Add pkg-config files for all urcu libs

Signed-off-by: Yannick Brosseau <yannick.brosseau@gmail.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

RBtree: move wmb after node write

We need to write all the new info into the node before we publish it
(make it visible to readers).

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Cleanup API

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

RBtree: Only execute usleep() in debug mode

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Add range test case, fix range search

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Add search min/max for ranges

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

RCU RBTree: Populate range information (augmented rbtree)

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Add _STORE_SHARED to set_parent

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

RCU rbtree test: handle duplicate random numbers

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

rbtree: disable debug mode

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

RCU RB tree test : add prev/next/max/min test

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix rcu_rbtree_prev

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Cleanup header

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Atomicize parent pointer and position update/read

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

RCU search fix

Fix removal by using the decay scheme for the whole branch from z->right
to y (inclusively) when transplanting y up to z.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Add missing read lock in test, cleanup transplant

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Use decay for rotate and transplant

Handles assumptions about shared nil node more gracefully.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Add RCU read-side test

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix rbtree for nr items > 4, add rcu and non-rcu rotate and transplant

Add non-RCU rotate and transplant for debugging.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

rcu rbtree: make rotation reader-aware

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Implement transplant based on decay scheme

Works with writer test. Concurrent RCU reader not supported yet.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

rbtree: use decay scheme

Rotations implemented. Write-only tested. Not supporting RCU readers
yet.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Reimplement basic non-RCU rbtree

Use as a starting point for RCU rbtree iterative development/test
starting from this non-RCU implementation.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

userspace-rcu tests: zero array before using

It seems like we need the test arrays to start out zeroed.

Without this patch, I get errors like this when running the tests:
test_urcu: test_urcu.c:201: test_array_alloc:
Assertion `test_array[index].a == 0xDEADBEEF || test_array[index].a ==
0' failed.

Signed-off-by: Colin McCabe <cmccabe@alumni.cmu.edu>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

arm: put CONFIG_RCU_ARM_HAVE_DMB in the global config.h

Change CONFIG_ARM_HAVE_DMB to CONFIG_RCU_ARM_HAVE_DMB while at the
same time making it seen as a global setting in urch/config.h.

The initial ARM < v7 work missed this setting, which allowed the URCU
to package to build correctly, but exposed the memorry barriers
defines incorrectly for other applications using the URCU headers.

Signed-off-by: Jason Wessel <jason.wessel@windriver.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Cleanup: remove unused value warning

return value of cmpxchg is purposefully unused in
_cds_lfq_enqueue_rcu(). Cast it to (void) to remove the compiler
warning.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Provide cleanup interfaces for per-CPU and per-thread call_rcu threads

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Maintain list of struct call_rcu_data to keep valgrind happy.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Add call_rcu() interface

Adds call_rcu(), with RCU threads to invoke the callbacks.  By default,
there will be one such RCU thread per process, created the first time
that call_rcu() is invoked.  On systems supporting sched_getcpu(), it
is possible to create one RCU thread per CPU by calling
create_all_cpu_call_rcu_data().

This version includes feedback from Mathieu Desnoyers.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix ppc asm syntax error.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

update version to 0.5.4

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

urcu-bp: Update fork() handling

Introduce

extern void rcu_bp_before_fork(void);
extern void rcu_bp_after_fork_parent(void);
extern void rcu_bp_after_fork_child(void);

to handle fork gracefully. These disable signals and hold the registry mutex
across forks.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Version 0.5.3

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Update README for urcu-bp fork handling

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

README: describe fork() interaction

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

urcu-bp: no "need_mb" in distrust signal config

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Update the README to change armv7l to arm

ARM v5 and ARM v6 are known to work using compiler barriers.

[ edit: add a missing comma while we are there ]

Signed-off-by: Jason Wessel <jason.wessel@windriver.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

ARM: use dmb for rmb and wmb in addition to mb

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Add a test for the dmb instruction on ARM

The dmb instruction is used to implement a memory barrier on modern
ARM hardware.  The older generations of processors which are included
in single processor systems can get by on the generic implementation
of the cmm_mb().  This will allow the user space rcu to work on many
other ARM systems.

Signed-off-by: Jason Wessel <jason.wessel@windriver.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

hange the arm headers to remove all the references to v7

Signed-off-by: Jason Wessel <jason.wessel@windriver.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Make armv7l headers generic for the arm architecture

This commit simply moves the files named *armv7l* to *arm*

Signed-off-by: Jason Wessel <jason.wessel@windriver.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

URCU list: remove leftover namespace clash (list_t type removed)

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

urcu_defer: update test programs (build fix)

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

rcu_defer test: handle error value

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

urcu-defer: handle malloc error value

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Version 0.5.2

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix get_cycles -> caa_get_cycles

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Version 0.5.1

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

ACCESS_ONCE should also have CMM_ prefix

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>