Fix: memory leak on hash table destroy

There is a missing call to pthread_mutex_destroy(3) to match
pthread_mutex_init(3) in the hash table creation.

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

Fix: urcu-bp: re-initialize list head on library exit

In case an application would try to create threads after the urcu-bp
library destructor has run, make sure the arena chunk list is
re-initialized after the memory mappings are unmapped.

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

Fix: examples make distcheck failure

"make distcheck" marks each source file on the srcdir in the extracted
dist tarball read-only. The examples copy from the srcdir into the
builddir before running the "make" examples, but this keeps the
read-only flag on the builddir directories, which fails the build
because the resulting objects cannot be created.

Fix this by ensuring the copied target directory for each example is
user-writeable.

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

Cleanup: remove unused return value warning from tests

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

Version 0.8.9

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

Fix: handle reference count overflow

The urcu refcounting API features a look and feel similar to the Linux
kernel reference counting API, which has been the subject of
CVE-2016-0728 (use-after-free). Therefore, improve the urcu refcounting
API by dealing with reference counting overflow.

For urcu_ref_get(), handle this by comparing the prior value with
LONG_MAX before updating it with a cmpxchg. When an overflow would
occur, trigger a abort() rather than allowing the overflow (which is a
use-after-free security concern).

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

Fix: compat_futex should work-around futex signal-restart kernel bug

When testing liburcu on a 3.18 Linux kernel, 2-core MIPS (cpu model :
Ingenic JZRISC V4.15  FPU V0.0), we notice that a blocked sys_futex
FUTEX_WAIT returns -1, errno=ENOSYS when interrupted by a SA_RESTART
signal handler. This spurious ENOSYS behavior causes hangs in liburcu
0.9.x. Running a MIPS 3.18 kernel under a QEMU emulator exhibits the
same behavior. This might affect earlier kernels.

This issue appears to be fixed in 3.19 since commit e967ef022 "MIPS: Fix
restart of indirect syscalls", but nevertheless, we should try to handle
this kernel bug more gracefully than a user-space hang due to unexpected
spurious ENOSYS return value.

Therefore, fallback on the "async-safe" version of compat_futex in those
situations where FUTEX_WAIT returns ENOSYS. This async-safe fallback has
the nice property of being OK to use concurrently with other FUTEX_WAKE
and FUTEX_WAIT futex() calls, because it's simply a busy-wait scheme.

The 4.2 kernel on parisc, and likely newer kernels too, are also
affected by a similar issue.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
CC: Michael Jeanson <mjeanson@efficios.com>
CC: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
CC: Ralf Baechle <ralf@linux-mips.org>
CC: linux-mips@linux-mips.org
CC: linux-kernel@vger.kernel.org
CC: "James E.J. Bottomley" <jejb@parisc-linux.org>
CC: Helge Deller <deller@gmx.de>
CC: linux-parisc@vger.kernel.org

Fix: urcu-signal: smp_mb_master() needs registry lock

The signal-based urcu flavor calls smp_mb_master() within the wait_gp()
function. Since commit "Fix: deadlock when thread join is issued in
read-side C.S.", wait_gp() is called without the registry lock held.

Ensure that the registry lock is only released around the wait per se,
not around the call to smp_mb_master(), otherwise we end up iterating on
a non-consistent thread registry in smp_mb_master().

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

Fix: rculfhash only needs to include urcu-pointers.h

rculfhash is not meant to use a specific urcu flavor, but rather receive
the flavor to use as parameter to _cds_lfht_new().

All we need is the API of urcu-pointers.h, so include that instead.

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

Fix: format string signedness

Detected by cppcheck.

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

Use gcc atomics on aarch64/powerpc64le

Currently there are two fairly recent architectures, which at the
moment can only be compiled with "gcc atomics" code path.
The two new architectures are (GNU Types):
* aarch64-linux-gnu (aka ARMv8, ARM64, AARCH64, etc)
* powerpc64le-linux-gnu

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

Fix: compat_futex: uninitialized ret variable

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

Fix: compat_futex_noasync: don't override return value

Fix error reported by Coverity:
** CID 1324336:  Code maintainability issues  (UNUSED_VALUE)
/compat_futex.c: 99 in compat_futex_noasync()

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

Fix: stable-0.8 branch does not have syscall-compat.h

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

Fix: dynamic fallback to compat futex on sys_futex ENOSYS

Some MIPS processors (e.g. Cavium Octeon II) dynamically check if the
CPU supports ll/sc within sys_futex, and return a ENOSYS errno if they
don't, even though the architecture implements sys_futex.

Handle this situation by always building the sys_futex compatibility
layer, and fall-back on it if sys_futex return a ENOSYS errno. This is
a tiny compat layer which adds very little space overhead.

This adds an unlikely branch on return from sys_futex, which should
not be an issue performance-wise (we've already taken a system call).

Since this is a fall-back mode, don't try to be clever, and don't cache
the result, so that the common cases (architectures with a properly
working sys_futex) don't get two conditional branches, just one.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Acked-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
CC: Michael Jeanson <mjeanson@efficios.com>
CC: Jon Bernard <jbernard@debian.org>

Version 0.8.8

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

Disable sys_membarrier

sys_membarrier underwent changes between its original implementation and
its upcoming inclusion into the Linux kernel. Disable it to ensure we
do not use the ABI incorrectly.

Should the prior user-space code be built against a kernel header that
defines SYS_membarrier, and executed against that kernel, the following
scenarios may happen:

- -1 will be returned with EINVAL errno if the 2nd argument (flags) is
  non-zero (the previous ABI expected a single argument),
- (MEMBARRIER_EXPEDITED | MEMBARRIER_QUERY) defined as
  (1 << 0) | (1 << 16) will return -1 with EINVAL errno, because valid
  commands are now one-hot.

Therefore, should an incompatible user-space code try to use
sys_membarrier, it will simply think that the system does not have
membarrier support due to the negative return value upon query.

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

Fix: volatile in assert()

From Coverity:
CID 1021642 (#1 of 3): Side effect in assertion
(ASSERT_SIDE_EFFECT)assert_side_effect: Argument test_array of assert()
has a side effect because the variable is volatile. The containing
function might work differently in a non-debug build.

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

uatomic: Specify complete types for atomic function calls

This was unearthed by clang compiler where it complained about parameter
mismatch, gcc doesnt notice this

urcu/uatomic/generic.h:190:10: error: address argument to atomic builtin
must be a pointer to integer or pointer ('void *' invalid)
                return __sync_add_and_fetch_4(addr, val);

Fixed all instances thusly.

[ Edit by Mathieu: use stdint.h types. ]

Signed-off-by: Khem Raj <raj.khem@gmail.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix: handle sys_futex() FUTEX_WAIT interrupted by signal

We need to handle EINTR returned by sys_futex() FUTEX_WAIT, otherwise a
signal interrupting this system call could make sys_futex return too
early, and therefore cause a synchronization issue.

Ensure that the futex compatibility layer returns meaningful errors and
errno when using poll() or pthread cond variables.

Reported-by: Gerd Gerats <geg@ngncc.de>
CC: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
CC: Lai Jiangshan <laijs@cn.fujitsu.com>
CC: Stephen Hemminger <shemminger@vyatta.com>
CC: Alan Stern <stern@rowland.harvard.edu>
CC: lttng-dev@lists.lttng.org
CC: rp@svcs.cs.pdx.edu
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix: compat_futex.c: *uaddr should be read as volatile

Ensure that a volatile read is used when reading *uaddr in the
compatibility implementation for sys_futex FUTEX_WAIT.

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

Fix: make benchmark test run in oot build

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

Fix: call_rcu_thread() affinity failure

Make call_rcu_thread() affine itself more persistently

Currently, URCU simply fails if a call_rcu_thread() fails to affine
itself. This is problematic when execution is constrained by cgroup
and hotunplugged CPUs. This commit therefore makes call_rcu_thread()
retry setting its affinity every 256 grace periods, but only if it
detects that it migrated to a different CPU. Since sched_getcpu() is
cheap on many architectures, this check is less costly than going
through a system call.

Reported-by: Michael Jeanson <mjeanson@efficios.com>
Suggested-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Acked-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

urcu: fix deprecation warning with new glibc

This patch fixes the following warning:

/usr/include/features.h:148:3: warning: #warning "_BSD_SOURCE and _SVID_SOURCE are deprecated, use _DEFAULT_SOURCE" [-Wcpp]
 # warning "_BSD_SOURCE and _SVID_SOURCE are deprecated, use _DEFAULT_SOURCE"

From http://man7.org/linux/man-pages/man7/feature_test_macros.7.html:

_BSD_SOURCE (deprecated since glibc 2.20)
[...]
Since glibc 2.20, this macro is deprecated.  It now has the same effect
as defining _DEFAULT_SOURCE, but generates a compile-time warning
(unless _DEFAULT_SOURCE is also defined).  Use _DEFAULT_SOURCE instead.
To allow code that requires _BSD_SOURCE in glibc 2.19 and earlier and
_DEFAULT_SOURCE in glibc 2.20 and later to compile without warnings,
define both _BSD_SOURCE and _DEFAULT_SOURCE.

Signed-off-by: Marc Kleine-Budde <mkl@pengutronix.de>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Version 0.8.7

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

Fix: deadlock when thread join is issued in read-side C.S.

The transitive dependency between:

RCU read-side C.S. -> synchronize_rcu -> rcu_gp_lock -> rcu_register_thread

and the dependency:

pthread_join -> awaiting for thread completion

Can block a thread on join, and thus have the side-effect of deadlocking
a thread doing a pthread_join while within a RCU read-side critical
section. This join would be awaiting for completion of register_thread or
rcu_unregister_thread, which may never complete because the rcu_gp_lock
is held by synchronize_rcu executed from another thread.

One solution to fix this is to add a new lock, rcu_registry_lock. This
lock now protects the thread registry. It is released between iterations
on the registry by synchronize_rcu, thus allowing thread
registration/unregistration to complete even though synchronize_rcu is
awaiting for RCU read-side critical sections to complete.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Reviewed-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
CC: Eugene Ivanov <Eugene.Ivanov@orc-group.com>
CC: Lai Jiangshan <laijs@cn.fujitsu.com>
CC: Stephen Hemminger <stephen@networkplumber.org>

Fix: rename RCU_DEBUG to DEBUG_RCU in urcu-qsbr.h

Keep a mapping allowing to define RCU_DEBUG within urcu-qsbr.h for
compatibility purposes.

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

Mark braced-groups within expressions with __extension__

Braced-groups within expressions are not valid ISO C, so
if a macro uses them and it's included in a project built
with -pedantic, the build will fail. GCC and CLANG do
support them as extension, so marking them as such allows
the build to complete even with -pedantic.

Signed-off-by: Luca Boccassi <lboccass@brocade.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix: compat_futex_noasync race condition

The Userspace RCU compatibility layer around sys_futex has a race
condition which makes pretty much all "benchmark" tests hang pretty
quickly on non-Linux systems (tested on Mac OS X).

I narrowed it down to a bug in compat_futex_noasync: this compat layer
uses a single pthread mutex and condition variable for all callers,
independently of their uaddr. The FUTEX_WAKE performs a pthread cond
broadcast to all waiters. FUTEX_WAIT must then compare *uaddr with val
to see which thread has been awakened.

Unfortunately, the check was not done again after each return from
pthread_cond_wait(), thus causing the race.

This race affects threads using the futex_noasync() compatibility layer
concurrently, thus it affects only on non-Linux systems.

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

Fix: documentation: urcu-pointer.h: s/rcu_dereference_pointer/rcu_dereference/

Signed-off-by: Emilio G. Cota <cota@braap.org>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix: call rcu should call internal RCU API

Because call rcu implementation is included within RCU flavors, calling
the RCU API goes through the API for non-LGPL code (this is a special
case for the RCU flavor implementation c file). Since this is clearly
LGPL code, we can use the inline versions.

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

Version 0.8.6

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

Fix: silence gcc -Wextra warning

It appears that just casting to "unsigned long" already has the semantic
we are looking for (checked by reading C99 standard and
experimentation): it sign-extends smaller signed integers, and does not
sign-extend unsigned integers.

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

compiler: use __GNUC__ instead of the undefined __GNUC_MAJOR__

gcc defines the major number with __GNUC__, not __GNUC_MAJOR__:
  https://gcc.gnu.org/onlinedocs/cpp/Common-Predefined-Macros.html

Signed-off-by: Emilio G. Cota <cota@braap.org>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix: lfstack reversed empty/non-empty return value

The return value of lfstack push operation is logically reversed
compared to the documentation, and compared to wfstack and wfcqueue.

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

lfstack: fix: add missing __cds_lfs_init

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

Version 0.8.5

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

Fix: preserve example files' timestamps when copying

This fixes an issue where examples were always being rebuilt
when performing an out of tree build since the examples were
being copied to the build directory with a timestamp more
recent than the already-built example objects.

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

rculfhash: remove duplicated code

Signed-off-by: Eric Wong <normalperson@yhbt.net>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

rculfhash: handle pthread_create failures

Like calloc, pthread_create may fail with EAGAIN due to a lack
of resources.  Account for that and gracefully continue.

Signed-off-by: Eric Wong <normalperson@yhbt.net>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

rculfhash: fall back to single-threaded resize on calloc failure

Having a calloc fail on my server should not be fatal.

Signed-off-by: Eric Wong <normalperson@yhbt.net>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

x86: drop extra semi-colon in caa_cpu_relax

This fixes compilation in braceless if/else constructs:

if (expr)
caa_cpu_relax();
else
...

Signed-off-by: Eric Wong <normalperson@yhbt.net>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix: Use after free in rcu_barrier()

Do not free the rcu_barrier() completion struct until all threads are
done with it.

It cannot reside on the waiter's stack as rcu_barrier() may return
before the call_rcu handlers have finished checking whether it needs a
futex wakeup. Instead we dynamically allocate the structure and
determine its lifetime with a reference count.

Signed-off-by: Keir Fraser <keir@cohodata.com>
[ Edit by Mathieu Desnoyers: use urcu/ref.h. Cleanup: use
  uatomic_sub_return() rather than uatomic_add_return() with negative
  value. ]
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix: rcu_barrier(): uninitialized futex field

This uninitialized futex field can lead to rcu_barrier() hang. This
issue has been found with Valgrind.

Fixes #787

Reported-by: Keir Fraser <keir@cohodata.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

call_rcu threads should clear their PAUSED flag when they unpause

And call_rcu_after_fork_parent should spin-wait on this.

Otherwise a second fork in the parent will see the PAUSED flags
already set and call_rcu_before_fork will not correctly wait for the
call_rcu threads to quiesce on this second occasion.

Fixes #786

Signed-off-by: Keir Fraser <keir@cohodata.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix: bring back dummy rcu_bp_exit symbol

Needed to keep so compatibility within stable branch.

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

Version 0.8.4

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

Fix: move wait loop increment before first conditional block

The fix "Fix: high cpu usage in synchronize_rcu with long RCU read-side
C.S." has an imperfection in urcu.c and urcu-qsbr.c: when incrementing
the wait loop counter for the last time, the first conditional branch is
not taken, but the following conditionals are, and they assume the first
conditional has been taken.

Within urcu.c (urcu-mb, urcu-membarrier and urcu-signal), and
urcu-qsbr.c, this will simply skip the first wait_gp() call, without any
noticeable ill side-effect.

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

Version 0.8.3

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

Fix: high cpu usage in synchronize_rcu with long RCU read-side C.S.

We noticed that with this kind of scenario:
- application using urcu-mb, urcu-membarrier, urcu-signal, or urcu-bp,
- long RCU read-side critical sections, caused by e.g. long network I/O
  system calls,
- other short lived RCU critical sections running in other threads,
- very frequent invocation of call_rcu to enqueue callbacks,
lead to abnormally high CPU usage within synchronize_rcu() in the
call_rcu worker threads.

Inspection of the code gives us the answer: in urcu.c, we expect that if
we need to wait on a futex (wait_gp()), we expect to be able to end the
grace period within the next loop, having been notified by a
rcu_read_unlock(). However, this is not always the case: we can very
well be awakened by a rcu_read_unlock() executed on a thread running
short-lived RCU read-side critical sections, while the long-running RCU
read-side C.S. is still active. We end up in a situation where we
busy-wait for a very long time, because the counter is !=
RCU_QS_ACTIVE_ATTEMPTS until a 32-bit overflow happens (or more likely,
until we complete the grace period). We need to change the wait_loops ==
RCU_QS_ACTIVE_ATTEMPTS check into an inequality to use wait_gp() for
every attempts beyond RCU_QS_ACTIVE_ATTEMPTS loops.

urcu-bp.c also has this issue. Moreover, it uses usleep() rather than
poll() when dealing with long-running RCU read-side critical sections.
Turn the usleep 1000us (1ms) into a poll of 10ms. One of the advantage
of using poll() rather than usleep() is that it does not interact with
SIGALRM.

urcu-qsbr.c already checks for wait_loops >= RCU_QS_ACTIVE_ATTEMPTS, so
it is not affected by this issue.

Looking into these loops, however, shows that overflow of the loop
counter, although unlikely, would bring us back to a situation of high
cpu usage (a negative value well below RCU_QS_ACTIVE_ATTEMPTS).
Therefore, change the counter behavior so it stops incrementing when it
reaches RCU_QS_ACTIVE_ATTEMPTS, to eliminate overflow.

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

Version 0.8.2

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

Fix: out of tree build: doc/examples

Fixes #704

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

Fix: out of tree build tests/common

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

tests/unit: use lib rather than source

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

automake: Rename INCLUDES to AM_CPPFLAGS (new name)

Fixes this warning:

Makefile.am:3: warning: 'INCLUDES' is the old name for 'AM_CPPFLAGS' (or '*_CPPFLAGS')

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

tests regressions: use lib rather than recompile from source

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

tests: use common lib rather than recompile compat sources

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

urcu tests: use lib rather than compile from source

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

urcu mb tests: use lib rather than recompile from source

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

urcu signal tests: use library rather than recompile source

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

tests: move yield debug to common test library

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

tests urcu bp: use lib rather than recompile source

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

test_urcu_defer: link on urcu lib rather than recompile source

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

tests/benchmark: use urcu qsbr lib rather than recompile from source

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

Pass the CC variable to the example Makefiles

Cross-compilation fails when using the --host configure option
since the cross-compiler is not invoked by the hand-made Makefiles
in doc/examples.

The CC variable must be passed explicitly to ensure the host's
default compiler is not invoked.

Signed-off-by: Jérémie Galarneau <jeremie.galarneau@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix: urcu-bp interaction with threads vs constructors/destructors

Add a reference counter for threads using urcu-bp, thus ensuring that
even if the urcu destructor is executed before each thread using RCU
read-side critical sections exit, those threads will not see a corrupted
thread list.

Also, don't use URCU_TLS() within urcu_bp_thread_exit_notifier(). It
appears that this is racy (although this was probably due to the issue
fixed by reference counting). Anyway, play safe, and pass the rcu_key
received as parameter instead.

Those issues only reproduce when threads are still active when the
urcu-bp destructor is called.

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

Fix undefined NULL pointer arithmetic

Clang 3.3 with -O2 optimisations is especially picky about arithmetic
on NULL pointers. This undefined behavior is turned into optimized out
NULL checks by clang 3.3. Fix the undefined behavior by checking against
the pointer directly, without going back and forth around NULL with
pointer arithmetic.

Reported-by: Zifei Tong <soariez@gmail.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Blacklist ARM gcc 4.8.0, 4.8.1, 4.8.2

It produces clobbered frame accesses, which can lead to stack corruption
when racing with signal handlers nested on stack.

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

rculfhash: document max_nr_buckets = 0

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

Version 0.8.1

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

tls-compat: fix comment typo

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

Keep ABI compatible with already compiled LGPL applications

Applications with _LGPL_SOURCE defined that were compiled against bogus
tls-compat.h header *and* which are using multiple urcu flavors
concurrently need to be told that they need to be recompiled against a
fixed tls-compat.h header. Detect these usage, and abort() with a
message error on stderr.

This is needed for stable-0.7 and stable-0.8 branches of userspace RCU
only. The upcoming 0.9 will bump the soname version, and therefore does
not have to care about this aspect of ABI compatibility.

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

Fix: tls-compat multi-lib conflict

When configured with the TLS pthread key fallback either:

- explicitly with ./configure --disable-compiler-tls,
- or if compiler TLS is not usable,

(this can be confirmed by looking at the configure output:
Thread Local Storage (TLS): pthread_getspecific().)

There is an issue when using multiple flavors of RCU within the same
program. Unit tests concerned:

tests/unit/test_urcu_multiflavor
tests/unit/test_urcu_multiflavor_dynlink

Vladimir Nikulichev noticed crashes when using this setup. The problem
can be pinpointed to a missing macro expansion in urcu/tls-compat.h:

looking at the output of

nm tests/unit/.libs/test_urcu_multiflavor :

                 U __tls_access_rcu_reader

this seems to be the issue. We're missing macro expansion in
tls-compat.h. With this commit, it becomes:

                 U __tls_access_rcu_reader_bp
                 U __tls_access_rcu_reader_mb
                 U __tls_access_rcu_reader_memb
                 U __tls_access_rcu_reader_sig

Please note that this affects an unusual configuration of userspace RCU
(with TLS pthread key fallback), needed for some BSD that don't support
compiler TLS. Strictly speaking, this requires bumping the URCU library
soname version major number, because it breaks the ABI presented to
applications on those unusual configurations.

A following commit will handle the ABI migration: for stable releases
(stable-0.7 and stable-0.8 branches), the ABI is kept compatible, and
bogus usage are detected. For the upcoming stable-0.9, the soname will
simply be bumped.

Reported-by: Vladimir Nikulichev <nvs@tbricks.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Use cross compiler for doc examples

Signed-off-by: Cristiana Voicu <cristiana.voicu@intel.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

gcc warning fixes: -Wsign-compare and -Wextra

When compiling code using the rcu_xchg_pointer() family of functions,
with the following define:

 #define URCU_INLINE_SMALL_FUNCTIONS

prior to including urcu headers, when compiling with gcc with
-Wsign-compare and -Wextra, gcc warns about:

urcu-xchg.c: In function ‘reload’:
urcu-xchg.c:19:1: warning: ordered comparison of pointer with integer zero [-Wextra]
urcu-xchg.c:19:1: warning: signed and unsigned type in conditional expression [-Wsign-compare]

For the "ordered comparison of pointer with integer zero" warning, fix
this by comparing (type) -1 against (type) 0 instead of just 0, so if
"type" is a pointer type, this pointer type will be applied to the right
operand too, thus fixing the warning.

For the "signed and unsigned type in conditional expression" warning, we
need caa_cast_long_keep_sign() to always evaluate to the same type
signedness. In order to do so, when we need to sign-extend the value,
cast it to unsigned long after first casting it to long.

Reported-by: Stephen Hemminger <stephen@networkplumber.org>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix: urcu-qsbr: reversed logic on RCU_DEBUG

* Dmitri Shubin <sbn@tbricks.com> wrote:
> Shouldn't the condition in line 94 actually be
>
>      94  #if (!defined(BUILD_QSBR_LIB) && !defined(RCU_DEBUG))
>
> So when RCU_DEBUG is _not_ defined we get static inlines for
> rcu_read_{,un}lock() ?

Indeed!

Reported-by: Dmitri Shubin <sbn@tbricks.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix: urcu-bp segfault in glibc pthread_kill()

This fixes an issue that appears after this recent urcu-bp fix is
applied:

  Fix: urcu-bp: Bulletproof RCU arena resize bug

Prior to this fix, on Linux at least, the behavior was to allocate
(and leak) one memory map region per reader thread. It worked, except
for the unfortunate leak. The fact that it worked, even though not the
way we had intended it to, is is why testing did not raise any red flag.
That state of affairs has prevailed for a long time, but it was
side-tracking some issues. After fixing the underlying bug that was
causing the memory map leak, another issue appears.

The garbage collection scheme reclaiming the thread tracking structures
in urcu-bp fails in stress tests to due a bug in glibc (tested against
glibc 2.13 and 2.17). Under this workload, on a 2-core/hyperthreaded i7:

./test_urcu_bp 40 4 10

we can easily trigger a segmentation fault in the pthread_kill() code.

Program terminated with signal 11, Segmentation fault.

Backtrace:

 #0  __pthread_kill (threadid=140723681437440, signo=0) at ../nptl/sysdeps/unix/sysv/linux/pthread_kill.c:42
 42 ../nptl/sysdeps/unix/sysv/linux/pthread_kill.c: No such file or directory.
 (gdb) bt full
 #0  __pthread_kill (threadid=140723681437440, signo=0) at ../nptl/sysdeps/unix/sysv/linux/pthread_kill.c:42
         __x = <optimized out>
         pd = 0x7ffcc90b2700
         tid = <optimized out>
         val = <optimized out>
 #1  0x0000000000403009 in rcu_gc_registry () at ../../urcu-bp.c:437
         tid = 140723681437440
         ret = 0
         chunk = 0x7ffcca0b8000
         rcu_reader_reg = 0x7ffcca0b8120
         __PRETTY_FUNCTION__ = "rcu_gc_registry"
 #2  0x0000000000402b9c in synchronize_rcu_bp () at ../../urcu-bp.c:230
         cur_snap_readers = {next = 0x7ffcb4888cc0, prev = 0x7ffcb4888cc0}
         qsreaders = {next = 0x7ffcb4888cd0, prev = 0x7ffcb4888cd0}
         newmask = {__val = {18446744067267100671, 18446744073709551615 <repeats 15 times>}}
         oldmask = {__val = {0, 140723337334144, 0, 0, 0, 140723690351643, 0, 140723127058464, 4, 0, 140723698253920, 140723693868864, 4096, 140723690370432,
             140723698253920, 140723059951840}}
         ret = 0
         __PRETTY_FUNCTION__ = "synchronize_rcu_bp"
 #3  0x0000000000401803 in thr_writer (_count=0x76b2f0) at test_urcu_bp.c:223
         count = 0x76b2f0
         new = 0x7ffca80008c0
         old = 0x7ffca40008c0
 #4  0x00007ffcc9c83f8e in start_thread (arg=0x7ffcb4889700) at pthread_create.c:311
         __res = <optimized out>
         pd = 0x7ffcb4889700
         now = <optimized out>
         unwind_buf = {cancel_jmp_buf = {{jmp_buf = {140723337336576, 6546223316613858487, 0, 140723698253920, 140723693868864, 4096, -6547756131873848137,
                 -6547872135220034377}, mask_was_saved = 0}}, priv = {pad = {0x0, 0x0, 0x0, 0x0}, data = {prev = 0x0, cleanup = 0x0, canceltype = 0}}}
         not_first_call = 0
         pagesize_m1 = <optimized out>
         sp = <optimized out>
         freesize = <optimized out>
         __PRETTY_FUNCTION__ = "start_thread"
 #5  0x00007ffcc99ade1d in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:113

It appears that the memory backing the thread information can be
relinquished by NPTL concurrently with execution of pthread_kill()
targeting an already joined thread and cause this segfault. We were
using pthread_kill(tid, 0) to discover if the target thread was alive or
not, as documented in pthread_kill(3):

       If  sig  is 0, then no signal is sent, but error checking is still per‐
       formed; this can be used to check for the existence of a thread ID.

but it appears that the glibc implementation is racy.

Instead of using the racy pthread_kill implementation, implement cleanup
using a pthread_key destroy notifier for a dummy key. This notifier is
called for each thread exit and destroy.

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

Fix urcu-bp: don't move registry

It is not correct to move the registry address range, since there are
external references from reader threads. This will trigger on workloads
with many threads.

Typically, on Linux, mremap can expand the existing range, which is OK.
However, if there is not enough space around the existing range, it may
try to map it at a different address, which is incorrect.

It is more likely that this bug will be observed on operating systems
where urcu uses the mmap/munmap fallback instead of mremap.

Moreover, prior to commit:

  "Fix: urcu-bp: Bulletproof RCU arena resize bug"

this issue was hidden by the fact that each thread ended up with their
own memory mapping (leaked), on Linux at least.

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

Fix: compat futex duplicated lock and completion

compat_futex.c has one instance included in each urcu shared object, as
well as within some of the test applications. However, it is expected
that an entire program interact with the same lock and completion
variables. Therefore, define them as globally visible, but weak, so the
entire program agree on which object should be used.

Reported-by: Vladimir Nikulichev <nvs@tbricks.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix: i386 compat code duplicated mutex instances

compat_arch_x86.c is linked into many .so and even into test programs.
The basic problem with this is that it contains a statically defined
mutex, which will fail to protect concurrent use of this compat code by
different shared objects.

Fix this by defining both the mutex (now called __urcu_x86_compat_mutex)
and __rcu_cas_avail as weak symbols. Therefore, the first symbol that
gets loaded in a program will by used by everyone.

Reported-by: Vladimir Nikulichev <nvs@tbricks.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix: urcu-bp: Bulletproof RCU arena resize bug

> From: "Milosz Tanski" <milosz@adfin.com>

> While trying to use the BP flavor of RCU I ran into random crashes. I
> tracked it down to issues with resizing of the BP RCU memory pool.
>
> The problem is in the urcu-bp.c file in the resize_arena() function.
> On successful allocation / remapping the len member of the
> registry_arena struct is never set anywhere function. On the second
> resize of the arena the code in resize_arena() still thinks the
> previous size is equal to the original mapping size. I've fixed this
> issue locally by just adding the following code at the bottom of
> resize_arena().

Good catch !!

However, I think your fix misses one case: if we happen to re-use the
same region, we want to update the length too.

Reported-by: Milosz Tanski <milosz@adfin.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix: test_mutex.c uninitialized mutex

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

Version 0.8.0

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

Fix: hash table growth (for small tables) should be limited

Buckets with many entries encountered in a hash table could cause it to
grow to a large size, beyond the scope for which this mechanism is
expected to play a role when node accounting is available. Indeed, when
the hash table grows to larger size, split-counter node accounting is
expected to deal with resize/shrink rather than relying on an heuristic
based on the largest bucket size.

This is fixing an issue where we see hash tables sometimes reaching 65k
entries index (65536*8 = 524288 bytes) for a workload limited to adding
1000 entries and then removing all of them, done in a loop (random
keys).

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

Fix: doc/examples cross-build

We need to pass automake's CPPFLAGS and LDFLAGS to examples. Add CFLAGS
too for completeness.

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

Introduce URCU_INLINE_SMALL_FUNCTIONS

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

Add missing tests/common/Makefile.am

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

README: document make check/regtest/bench

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

tests: split in check, regtest and bench targets

Allow make check to run without requiring build machines to use hours of
CPU time.

make check: short unit tests
make regtest: long regression tests
make bench: long benchmarks

Fixes #611

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

Cleanup: doc/examples makefile

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

Fix: doc/examples VPATH build

Fixes #568

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

doc/examples: Move the LIBS after the OBJECTS in the Makefile

Fixes #569.

Signed-off-by: Alexandre Montplaisir <alexmonthy@voxpopuli.im>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Document build work-around on MacOS X

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

Fix tests: use of uninitialized variables

Were working fine by luck, since they were allocated at the start of
newly spawned test programs. Identified by Coverity.

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

test_urcu_hash*: initialize TLS seeds

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

doc/examples: cds_lfht_for_each_entry_duplicate

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

doc/examples: cds_lfht_lookup

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

doc/examples: cds_lfht_destroy

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

doc/examples: cds_lfht_add_replace

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

doc/examples: cds_lfht_add_unique

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