Cleanup: tests: Branch condition evaluates to a garbage value

scan-build reported this:

Logic error Branch condition evaluates to a garbage value tests
/benchmark /test_urcu_hash_rw.c 170
Logic error Branch condition evaluates to a garbage value tests
/benchmark /test_urcu_hash_rw.c 274

It should never happen based on code review, but silence this warning by
initializing to NULL.

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

Fix: test: unchecked return value

Fix Coverity issues:

CID 1021635 (#1 of 2): Unchecked return value (CHECKED_RETURN)7.
check_return: Calling pthread_mutex_unlock without checking return value
(as is done elsewhere 29 out of 33 times).

CID 1021634 (#2 of 2): Unchecked return value (CHECKED_RETURN)12.
check_return: Calling pthread_mutex_unlock without checking return value
(as is done elsewhere 29 out of 33 times).

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

Fix: test: side-effect in assertion

Coverity detected:

CID 1021642 (#1 of 2): 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>

x86: allocate membarrier system call number

Now that the membarrier system call is allocated on x86 32/64, allocate
its number in our architecture header if the system headers don't
allocate it. This allows using the membarrier system call as soon as
implemented in the kernel, even if the distribution has old kernel
headers.

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

urcu-bp: use sys_membarrier when available

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

Cleanup: urcu: remove unused membarrier "group" parameter

Was planned in the 2010 implementation, but has never been used, and is
not needed with the current kernel membarrier implementation.

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

urcu/ref.h: implement urcu_ref_get_unless_zero()

Allows getting a reference atomically if the reference count is not
zero. Returns true if the reference is taken, false otherwise. This
needs to be used in conjunction with another synchronization technique
(e.g.  RCU or mutex) to ensure existence of the reference count.

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: 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>

Detect RCU read-side overflows

Use the urcu_assert() macro (enabled on DEBUG_RCU) to check for
unmatched rcu_read_lock() that eventually leads to nesting counter
overflow in urcu.h and urcu-bp.h. This won't necessarily point the the
exact rcu_read_lock() that is unmatched, but will at least detect the
overflow condition.

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

Detect RCU read-side underflows

Use the urcu_assert() macro (enabled on DEBUG_RCU) to check for
unmatched rcu_read_unlock() that leads to nesting counter underflow in
urcu.h and urcu-bp.h.

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

Introduce urcu_assert and registration check

Add a "registered" flag to urcu.c and urcu-qsbr.c, set/cleared when a
thread is registered and unregistered. Add corresponding asserts in
those functions checking if a thread is registered or unregistered more
than once (which would be a bug in the way the application uses urcu).

Move the checks enabled on RCU_DEBUG to a single header: urcu/debug.h.
Add checks for the registered flag in RCU read-side lock functions (new
urcu_assert() checks, which are only built-in if RCU_DEBUG is defined at
compile-time).

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>

Update following changes to sys_membarrier ABI

sys_membarrier underwent changes between its original implementation and
its upcoming inclusion into the Linux kernel. Update its use to follow
those changes.

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>

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>

Cleanup: remove unused return value warning from tests

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>

Cleanup: cast poll delay return value to void

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

tests: Convert unit tests to TAP

Signed-off-by: Michael Jeanson <mjeanson@efficios.com>
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>

Cleanup: cast poll delay return value to void

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

Cleanup: cast poll delay return value to void

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

Cleanup: cast poll delay return value to void

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

Cleanup: cast poll delay return value to void

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

Cleanup: cast poll() return value to void for delays

Explicitly state that we don't care about poll return value in those
cases.

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>

urcu: add cds_list_for_each_entry_safe_from macro

Same as cds_list_for_each_entry_safe, but starts at an arbitrary point
within the list instead of at the head.

Signed-off-by: Jeff Layton <jeff.layton@primarydata.com>
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>

Cleanup some c99 pedantic warnings

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>

tests: Use stderr redirection for time output

Allows using Mac OS X time command in tests.

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

Fix: use space after rpath for OS X ld

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

Fix: move transparent union attribute after union declaration for clang

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

Configure: add check for used type

Signed-off-by: Jonathan Rajotte <jonathan.rajotte-julien@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Configure: add missing check of headers

Signed-off-by: Jonathan Rajotte <jonathan.rajotte-julien@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Configure: add missing check for funcs: memset, strerror

Signed-off-by: Jonathan Rajotte <jonathan.rajotte-julien@efficios.com>
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>

urcu-bp/urcu-qsbr: remove unneeded DEBUG_YIELD code

They were moved to debug-yield.c

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
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>

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>

wfstack: add missing union parameters

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>

wfstack: implement mutex-free wfstack with transparent union

This allows users more freedom to use alternative synchronization
mechanisms.

Changes since v1:
- Fix typos in cds_wfs_stack_ptr_t documentation.
  Thanks to Mathieu for spotting.

Signed-off-by: Eric Wong <normalperson@yhbt.net>
Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Cc: Lai Jiangshan <laijs@cn.fujitsu.com>
Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

wfcqueue: Implement mutex-free wfcqueue head with transparent union

Tested-by: Eric Wong <normalperson@yhbt.net>
CC: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
CC: "Lai Jiangshan" <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

lfstack: Implement mutex-free stack head with transparent union (v2)

Changes since v1:
- implement __cds_lfs_init().

Tested-by: Eric Wong <normalperson@yhbt.net>
CC: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
CC: "Lai Jiangshan" <laijs@cn.fujitsu.com>
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>

Cleanup: tests: cast console write return value as void

Fixes #791

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

Modernize doc using Markdown

Signed-off-by: Philippe Proulx <eeppeliteloop@gmail.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix: update automake following README to README.md change

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

Modernize README using Markdown

Signed-off-by: Philippe Proulx <eeppeliteloop@gmail.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix: incorrect parenthesis in cds_hlist_for_each_entry_safe_2

commit db903109f0031c831e8fdc95cb7197996e53f46d introduced a regression
in cds_hlist_for_each_entry_safe_2(): incorrect parenthesis assign "e"
to 1, rather than assign "e" to the next pointer, and evaluating the
expression to 1 (comma expression).

Reported-by: Daniel Thibault <Daniel.Thibault@drdc-rddc.gc.ca>
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>

test_urcu_fork: test many fork, with 3 children deep

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

Update list of supported architectures in README

Add ARM 64, Tilera, and hppa/PA-RISC.

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

Add support for hppa/PA-RISC architecture

Add the missing architecture specific functions to provide support for
the hppa/PA-RISC architecture:
- the processor internal time stamp counter (Control Register CR16) is
  used to get high-performance/low-latency cycle counts
- gcc provides the necessary built-in atomic functions on hppa (which in
  turn uses the light-weigth atomic locking syscall-interface of the
  Linux kernel)

Signed-off-by: Helge Deller <deller@gmx.de>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Use autoconf AM_MAINTAINER_MODE

Give distribution maintainers the option to skip rebuilding
autoconf and automake generated files. The default behaviour
is still to have the rebuild rules enabled.

Signed-off-by: Lars Persson <larper@axis.com>
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: 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>

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>

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>

x86 barrier for Xeon Phi: use rsp on x86-64

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

Set RCU_HAVE_FENCE to false on Intel Xeon Phi

It currently fails to compile, because the Phi does not have fence
instructions.

It will use lock prefixed instructions for all memory barriers, which
is overkill for this platform, but at least it will work.

Signed-off-by: Simon Marchi <simon.marchi@polymtl.ca>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix undefined NULL pointer arithmetic in hlist

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.

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

Cleanup: Check for pthread in Libc

Some libc like Googles's Bionic for Android include pThread. Instead of
checking for Android as in commit
58a052effb2305655ff1b7233c78ab24fc25257e this patch checks for pthread
in libc as proposed by Thomas Petazzoni.

Reported-by: Thomas Petazzoni <thomas.petazzoni@free-electrons.com>
Signed-off-by: Charles Briere <charlesbriere.flatzo@gmail.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Cleanup: Android: Do not redefine gettid

When compiling with Android Toolchain, gettid is already defined in
<unistd.h> and therefore doesn't need to be reimplemented. This patch
checks for gettid instead of looking for Android in case other
environements behave the same way.

Signed-off-by: Charles Briere <charlesbriere.flatzo@gmail.com>
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>

Android: implement rand_r()

stdlib.h doesn't implement rand_r() on Android.

Signed-off-by: Charles Briere <charlesbriere.flatzo@gmail.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Android: do not redefine gettid on Android

Bionic already defines gettid through <unistd.h>.

Signed-off-by: Charles Briere <charlesbriere.flatzo@gmail.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Android: add a compat layer for 'syscall.h'

Path to include syscall.h is different on Android.

Signed-off-by: Charles Briere <charlesbriere.flatzo@gmail.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Android: do not link pthread on Android

On Android, pthread is already part of libc called Bionic and doesn't
have an external library to link with.

Signed-off-by: Charles Briere <charlesbriere.flatzo@gmail.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Android: configure.ac Android check

Set TARGET_IS_ANDROID to true if target is Android.

Signed-off-by: Charles Briere <charlesbriere.flatzo@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>