rculfhash: shrink size of dummy node

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

rculfhash: wait for call_rcu quiescence before destroy

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

rculfhash: add c++ ifdef

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

rculfhash test: add options

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

rculfhash test: use per-cpu call-rcu threads

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

rculfhash: update add_unique api

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

rculfhash: fix add unique

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

rculfhash test: increases random pool size

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

rculfhash: remove hash from nodes

Shrink node size, can get it quickly by reversing the reverse_hash.

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

rculfhash: change order of node fields for locality

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

rculfhash: merge node gc into add loop

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

rculfhash: cleanup

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

rculfhash test: add nr_leaked count

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

rculfhash: garbage collection scheme

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

rculfhash: flip order of removal

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

rculfhash: Remove "value" pointer

Use container_of instead.

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

rculfhash test: add missing free

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

rculfhash: add unique

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

Update resize thresholds

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

rculfhash updates

- Add and remove now completely lock-free (no busy-wait loop).
- Add resize_initiated flag to skip multiple call_rcu calls.
- Identical reverse hashes now only count as one chain entry in the
  chain length accounting. We cannot split identical hashes by growing
  the hash table anyway, so it was leading to large tables uselessly
  when we had a lot of similar hashes.

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

Comment list behavior wrt lock-freedom

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

Fix reverse hash comparison

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

rculfhash: use threshold and target

Accept to target bucket len greater than 1 to diminish the memory
consumption without too much performance impact.

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

rculfhash: implement real hash function

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

rculfhash: fix resize (use log2 of chain length)

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

Merge remote branch 'origin/urcu/ht' into urcu/ht

Conflicts:
urcu-ht.h

rcu lf hash table runtime fixes

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

split-ordered hash table

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

Rename urcu-ht to rculfhash

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

Merge branch 'master' into urcu/ht

Conflicts:
Makefile.inc
tests/Makefile.inc
urcu-defer.h

rculfstack: header implementation should be defined as static inline

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

wfstack: header implementation should be defined as static inline

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

urcu tests: hold mutex across use of custom allocator

A thread preempted for a long period of time could race, when scheduled
again, with another thread that would have been allocating/freeing
entries (thus wrapping-around the available buffer), which would trigger
this race only when overcommitting the number of threads compared to the
number of available CPUs.

Taking the mutex across alloc and free to fix this.

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

urcu-bp: mremap wrapper fix

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

urcu-bp: add mremap wrapper for non-linux systems

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

urcu-bp: don't copy old region upon mremap

mremap keeps the same virtual pages for the old/new mappings. So
explicitly copying from the old mapping is not needed, and probably
buggy, since the old mapping might have been unmapped.

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

api.h: fix type warning

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

non-linux system membarrier fallback update

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

pthread_self should be cast to unsigned long

Used as part of the random seed along with time().

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

Add MAP_ANONYMOUS mapping to MAP_ANON for BSD build

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

tests: only include syscall.h on linux systems

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

urcu-bp, urcu-qsbr: remove unneeded syscall.h include

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

urcu-defer: remove unneeded syscall.h include

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

call_rcu: per_cpu_call_rcu_data should be non-const

On FreeBSD:

In file included from urcu.c:438:
urcu-call-rcu-impl.h: In function 'get_cpu_call_rcu_data_mb':
urcu-call-rcu-impl.h:325: warning: return discards qualifiers from pointer target type

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

Update README info about gcc compability

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

Fix urcu-call-rcu-impl.h missing call_rcu_wait for non-linux systems

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

compat_futex_async: fix missing return

compat_futex.c: In function `compat_futex_async':
compat_futex.c:114: warning: control reaches end of non-void function

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

Check for __linux__ before including syscall.h

Reported-by: Jean-François Brousseau <jfb@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Remove unused local variables from compat_futex_async

Reported-by: Jean-François Brousseau <jfb@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Remove unneeded syscall.h include from urcu-call-rcu-impl.h

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

Add ChangeLog file to Makefile.am

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

Add changelog, update version to 0.6.3

uatomic: fix warning about unused variable

Fix:

compat_arch_x86.c: In function '_compat_uatomic_set':
compat_arch_x86.c:104:16: warning: variable 'result' set but not used [-Wunused-but-set-variable]

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

uatomic: fix i386 support

Fix:

* Incorrect prototype for uatomic_and and uatomic_or in i386
  compatibility code.
* Missing $(COMPAT) code inclusion in wfq/lfq tests.
* Silence gcc warnings about compat code (branch volountarily causing a
  linker error, which can never return).

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

Update version to 0.6.2

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

uatomic generic: map uatomic_and/or to correct symbols

Leading underscore was missing.

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

Fix generic atomic ops and/or: add missing return

Fixes build on powerpc:

./urcu/uatomic/generic.h: In function '_uatomic_and':
./urcu/uatomic/generic.h:310:2: warning: 'return' with a value, in
function returning void
./urcu/uatomic/generic.h: In function '_uatomic_or':
./urcu/uatomic/generic.h:374:2: warning: 'return' with a value, in
function returning void

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

Fix test warning

Patch from:
https://build.opensuse.org/package/view_file?file=liburcu0-cleanup.patch&package=liburcu0&project=devel%3Atools%3Alttng&srcmd5=fa3ab9fae0401b4c0f73a9cf474eea16

fixes a warning in the liburcu tests.

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

Add missing headers into tarball, version 0.6.1

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

Update version to 0.6.0

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

Futex: turn "int" into "int32_t" for portability

Even though int is 32-bit on all architectures supported by liburcu so
far, make it future-proof by uint a int32_t, which enforces the same
type width used by the system call in the kernel.

Using int32_t and not uint32_t to make comparison with 0 more
straightforward.

Reported-by: Darren Hart <dvhart@linux.intel.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Add back uatomic_arch.h for slow deprecation process

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

Add back urcu-futex.h and urcu_ref.h for slow deprecation

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

Add ldconfig step to README

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

Add a pkg-config file for the new liburcu-cds

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

Consolidate _LIBADD and _DEPENDENCIES in Makefile.am

Signed-off-by: Alexandre Montplaisir <alexandre.montplaisir@polymtl.ca>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Add urcu/cds.h placeholder for all CDS headers

Using CDS headers becomes as simple as:

 #include <urcu/cds.h>

and link with

 -lurcu-cds

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

Move the version-info to the AM_LDFLAGS variable

Since all the lib builded in this directory use the same version
we can put this command in the global variable

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

Installed headers should only include other headers with < >

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

Rename urcu/urcu-futex.h to urcu/futex.h

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

Rename urcu/urcu_ref.h to urcu/ref.h

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

Headers: move uatomic_*.h to urcu/uatomic/*.h, rename uatomic_arch.h to uatomic.h

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

Headers: move arch_*.h to urcu/arch/*.h

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

Headers: move *-static.h headers to urcu/static/

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

Install urcu/map/*.h into system

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

Headers: move *-map.h headers to urcu/map/

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

Add library version information

Following the guidelines from libtool
(http://www.gnu.org/software/libtool/manual/html_node/Updating-version-info.htm)
this patch add version information to the distributed libraries.
For the next release, the version will be 1:0:0.
It will need to be updated before each release.

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

lfqueue: update comments, cleanup

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

lfqueue: don't use defer_rcu anymore

lfqueue now uses call_rcu instead.

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

Combine stack and queues info liburcu-cds.so

Pretty much all libraries use a single .so for their data types. Do the
same here.

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

cds containers: lfqueue and lfstack: don't depend on a particular rcu flavor

Remove rcu_read lock/unlock from the code, require the caller to ensure
protection. First move towards a single .so for all data containers.

This changes the lfqueue API, which is not very much used yet AFAIK.

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

Add missing pkgconfig files to Makefile.am

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

arm: remove useless declarations

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

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>

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>

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>

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>