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>

LOAD_SHARED and STORE_SHARED should have CMM_ prefix

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

Fix CAA_CAA -> CAA

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

Fix missing BITS_PER_LONG -> CAA_BITS_PER_LONG rename

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

update version to 0.5.0

Rename all data structure with prefix cds_

This is the third and last patch of the namespace refactoring.

The prefix cds_ stands for Concurrent Data Structure and is
use for queue, list, hlist and stack.

For RCU protected data strucutre, the prefix is also added but
the suffix _rcu is appended. This suffix indicate and RCU protection.

Signed-off-by: David Goulet <david.goulet@polymtl.ca>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Rename all arch primitives with prefix caa_

This is the second patch for reducing namespace pollution.
The caa_ prefix stands for Concurrent Architecture Abstraction.
Again, suggested by Mathieu Desnoyers and Paul E. Mckenney.

Every define, macro and function specific to the architecture
abstraction of liburcu is modified with that prefix

Signed-off-by: David Goulet <david.goulet@polymtl.ca>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Rename all memory primitives with prefix cmm_

In order to not pollute the userspace namespace for application
using liburcu or any lib/apps linked with urcu, this patch if the
first of three major refactor for naming convention.

The cmm_ prefix is a short name for Concurrent Memory Model and was
suggested by Mathieu Desnoyers and Paul E. Mckenney. Every memory
primitives such as mb, wmb, rmb, and so on are renamed.

Signed-off-by: David Goulet <david.goulet@polymtl.ca>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Add missing test binaries to .gitignore

Signed-off-by: David Goulet <david.goulet@polymtl.ca>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Add config.h and stamp-h2 to gitignore

Signed-off-by: David Goulet <david.goulet@polymtl.ca>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Add compiler barriers to read-side for mutex ordering

Ensure that mutex acquisition/release is not reordered wrt rcu read lock/unlock.
No impact in practice because pthreads lock/unlock primitives act as memory
barriers. But we should provide the same guarantees we are expecting from other
locking primitives, hence this modification.

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

Fix missing urcu_ref.h in Makefile.am

The 0.4.7 tarball is missing 'urcu/urcu_ref.h', causing the following
error:

      CC     rculfqueue.lo
    In file included from rculfqueue.c:26:
    urcu/rculfqueue.h:26:22: error: urcu_ref.h: No such file or directory
    In file included from rculfqueue.c:26:
    urcu/rculfqueue.h:45: error: field ‘ref’ has incomplete type
    In file included from rculfqueue.c:27:
    urcu/rculfqueue-static.h:29:27: error: urcu/urcu_ref.h: No such file or directory

Reported-by: Jon Bernard <jbernard@debian.org>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

update version to 0.4.7

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

urcu lfstack: pop needs rcu read lock

The pop side needs to hold the RCU read lock to deal with ABA problem.
The push side does not need to hold the RCU read lock because even if the next
item is changed to the same value initially read, the stack will still be
consistent.

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

lfstack: simplification

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

rculfstack: LGPL-ize

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

rculfqueue: LGPL-ize

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

add missing comment to wfstack.c

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

wfstack: LGPL-ize

Create wrapper symbols for LGPL linking.

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

wfqueue: provide API for caller-locked dequeue

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

LGPL-ize wfqueue

Provide the appropriate wrappers to ensure that non-LGPL applications can use
the half-blocking wait-free queue.

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

WF queue cleanup

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

Wait-free stack: rcu-less implementation

Don't have to hold a rcu read lock anymore. pop side is blocking and holds a
mutex.

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

Wait-free queue: wait-free enqueue, blocking dequeue without RCU dependency

Implementation better suited for supporting call_rcu().

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

RCU lf queue/stack: update comments

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

ifdef C, wait-free stack adaptative pop wait

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

urcu static coding style fix (whitespace)

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

Coding style fix

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

RCU wait-free stack: add _blocking in pop() primitive name

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

RCU lock-free queue comment updates

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

RCU wait-free enqueue/blocking dequeue queue

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

Add ifdef cond around headers

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

RCU lock-free queue: don't hold RCU read lock across retry

Be nicer to grace periods.

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

RCU lock-free stack: don't hold read lock across retry

Be nicer to grace-periods.

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

Wait-free push/Blocking pop stack: Update following Paul's review

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

Add lock-free queue comments from Paul's review

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

Add wait-free push/blocking pop stack

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

Lock-free stack: add comments

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

Add lock-free RCU queue and stack

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

Update version to 0.4.6

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

Update README for ARM support

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

Update version to 0.4.5

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

Update email address from @polymtl.ca to @efficios.com

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

Force build failure on unknown architectures

Create urcu/arch_unknown.h and urcu/uatomic_arch_unknown.h, which
contain only #error statements and explanatory comments.  This forces
build failures on unrecognized architectures in preference to trying
to guess at what operations might be safe on such architectures.

One other semi-feasible alternative is to use hashed arrays of locks
that are acquired with signals disabled.  However, this seems a bit
too ornate, especially for architectures for which the gcc __sync_
primitives work correctly.

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

Add native ARM port for armv7l

Add native support for armv7l.  Other variants of ARM will likely require
separate ports.  The gcc __sync_ approach works back to at least 2.6.15
kernels.

As suggested by Paolo Bonzini, defer the definition of CACHE_LINE_SIZE
to arch_generic.h.

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

Add ia64 architecture based on gcc primitives

This of course assumes that ia64 gcc correctly implements the various
__sync_ primitives.  ;-)

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

Add header files supporting gcc __sync_ primitives

Add a urcu/arch_gcc.h and urcu/uatomic_arch_gcc.h whose primitives are
based on the gcc __sync_ primitives.  This should be usable for all
systems that have correctly implemented __sync_ primitives, which sadly
does not include all combinations of systems and compilers.  In addition,
specific systems may gain higher performance with hand-coded primitives.
Nevertheless, this is nice for getting a new architecture up and running
quickly.

As suggested by Paolo Bonzini, defer the definition of mb() to the common
arch_generic.h file, and also defer the uatomic*() primitives to
uatomic_generic.h.

[Mathieu : fixed arch_gcc.h header which contained incorrect arch_unknown.h in
           header.]

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

Add test cycles per loop

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

Add uatomic test to make check

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

Remove unused sync_core() definitions

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

Update version to 0.4.4

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

Fix powerpc uatomic 4-byte cmpxchg (cmpd -> cmpw)

Necessary to make it work on 32-bit only powerpc architectures. Was using the
64-bit comparison rather than the 32-bit comparison for 4-byte cmpxchg.

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

urcu-qsbr: use same ongoing helper for 32 and 64 bits

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

"make check" runs the test suite

a trivial patch to enable the Makefile "check" rule.

Signed-off-by: Giuseppe Scrivano <gscrivano@gnu.org>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Simplify qsbr online condition

Alan Stern wrote:

>       return v && (v - rcu_gp_ctr > ULONG_MAX / 2);
>
> Wouldn't it be better to write:
>
>       return v != 0 && v != rcu_gp_ctr;
>
> or something equivalent?  The point is, it's foolish to return 0 when
> rcu_gp_ctr has wrapped around to below v.  This can happen only when
> rcu_thread_online() is delayed (as by preemption), in which case we
> know that there's a good chance the algorithm will fail.  My version of
> the test eliminates the possibility of this failure, although it
> doesn't eliminate the possibility that rcu_gp_ctr has wrapped around so
> far that it is equal to v.

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

Cleanup: head -> node field name

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

Update urcu and urcu-qsbr, make compiler barriers explicit

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

urcu: Add extra "engineering safety factor" memory barrier in update_counter_and_wait()

Even though the memory barriers within update_counter_and_wait() are proven not
to be needed in urcu-mb/signal/qsbr implementations, we leave them in place as
an engineering safety factor. Basically, we've proven they are not required
(formally for urcu-mb and urcu-signal by model checking, less formally for
urcu-qsbr by looking at the execution order of concurrent synchronize_rcu() and
RCU read-sides with out-of-order load/stores). However, given that on the
overall performance impact of synchronize_rcu(), these memory barriers do not
add a significant overhead, let's leave them in place with a comment stating
that they are not required.

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

urcu-qsbr: document compiler barrier

This compiler barrier is, at the implementation level, already provided by the
volatile accesses for STORE/LOAD_SHARED. However, given that these primitives
does not provide this guarantee at the high-level (and might use lighter gcc
primitives eventually), we need to add an explicit barrier().

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

update version to 0.4.3

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

Fix typo in urcu/uatomic_generic.h

Signed-off-by: Jon Bernard <jbernard@debian.org>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Update version to 0.4.2

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

Update README

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

urcu-bp: reset ctr to 0 upon garbage collection

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

compiler.h: add () in ACCESS_ONCE()

Protect x in ACCESS_ONCE macro.

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

urcu-defer: remove "ratelimit" leftover

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

Update readme: ia64 and alpha support

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

Install missing arch_generic.h

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