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>

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>

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>