Allow building with GCC >= 13.3 on RISC-V

Building with GCC was marked as broken on RISC-V in
"46980605309e922d14f646c6705d184cb674c0f7". The patches fixing the issue
with atomic operations were included in the GCC 14 branch and backported
to 13.3.0.

Add the appropriate checks to allow building on RISC-V with the fixed
GCC versions.

Tested with GCC 13.3.0 on a VisionFive 2 board.

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

pointer.h: Fix the rcu_cmpxchg_pointer documentation

Fix the description of rcu_cmpxchg_pointer() function that had switched
new and old pointers.

Signed-off-by: Ondřej Surý <ondrej@sury.org>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

rculfhash: make cds_lfht_iter_get_node argument const

cds_lfht_iter_get_node doesn't modify its argument. Hence, it can be
marked as `const`.

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

lfstack: make cds_lfs_empty argument const

cds_lfs_empty doesn't modify its argument. Hence, it can be marked as
`const`.

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

wfcqueue: make cds_wfcq_empty arguments const

cds_wfcq_empty does not modify its arguments. Hence, they can be marked
as `const`.

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

wfstack: make cds_wfs_empty argument const

cds_wfs_empty doesn't modify its argument. Hence, it can be
marked as `const`.

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

cds_list: make cds_list_replace @old argument const

cds_list_replace doesn't modify its @old argument. Hence, it can be
marked as `const`.

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

cds_list: make cds_list_empty const

cds_list_empty doesn't modify its argument. Hence, it can be marked as
`const`.

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

Adjust shell script to allow Bash in other locations

commit da56d5cad05a ("Adjust shell scripts to allow Bash in other locations")
adjusted most of the shell scripts, except one.

Signed-off-by: Brad Smith <brad@comstyle.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Change-Id: I30ee8cb36d874f5eaadf7b17c60cfd362ecfa2f0

futex.h: Indent preprocessor directives

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

futex.h: Use urcu_posix_assert to validate unused values

When building on FreeBSD, uaddr2 and val3 are unused. Add a
urcu_posix_assert() to validate that they are zero and hence allow users
of the API to quickly figure out that those are not effectively used.

When building on OpenBSD, val3 is unused. Add a urcu_posix_assert() to
validate that it is zero.

Those asserts are already present in the compat code. Use the same
mechanism to prevent users from expecting futex arguments to be used
when they are in fact discarded.

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

Use futex on OpenBSD

Tested with "make check", "make regtest".

Signed-off-by: Brad Smith <brad@comstyle.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Change-Id: Icd334cda928f998a2cf455839d428ebbb4460f5e

fix: handle EINTR correctly in get_cpu_mask_from_sysfs

If the read() in get_cpu_mask_from_sysfs() fails with EINTR, the code is
supposed to retry, but the while loop condition has (bytes_read > 0),
which is false when read() fails with EINTR. The result is that the code
exits the loop, having only read part of the string.

Use (bytes_read != 0) in the while loop condition instead, since the
(bytes_read < 0) case is already handled in the loop.

Signed-off-by: Benjamin Marzinski <bmarzins@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Change-Id: I565030d4625ae199cabc4c2ab5eb8ac49ea4dfcb

Relicense src/compat-smp.h to MIT

Relicense the code in src/compat-smp.h from LGPLv2.1 to MIT to match the
copies in the following projects:

- lttng-ust
- libside
- librseq

This code is entirely authored by EfficiOS.

This relicensing initially appeared in the lttng-ust project after
the code was imported into liburcu:

  commit 4159f02937a2740abd7f5b113f376b198a86bc71 (test-struct-tls)
  Author: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
  Date:   Tue Oct 25 12:32:12 2022 -0400

      Relicense common/smp.c common/smp.h to MIT

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

uatomic/x86: Remove redundant memory barriers

When liburcu is configured to _not_ use atomic builtins, the
implementation of atomic operations is done using inline assembler for
each architecture.

Because we control the emitted assembler, we know whether specific
operations (e.g. lock; cmpxchg) already have an implicit memory barrier.
In those cases, emitting an explicit cmm_smp_mb() before/after the
operation is redundant and hurts performance.

Remove those redundant barriers on x86.

Change-Id: Ic1f6cfe9c2afe250946549cf6187f8fa88f5b009
Signed-off-by: Olivier Dion <odion@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

cleanup: move rand_r compat code to tests

This compat code is only used in the tests, move it there as it should
probably not be used in the library.

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

ppc: Document cache line size choice

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

Fix: change order of _cds_lfht_new_with_alloc parameters

The "flavor" parameter should come before the "alloc" parameter
to match the order of cds_lfht_new_with_flavor_alloc() parameters.

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

Add support for custom memory allocators for rculfhash

The current implementation of rculfhash relies on calloc()
to allocate memory for its buckets. This can in some cases
lead to latency spikes when accessing the hash table, which
can be avoided by using an optimized custom memory allocator.
However, there is currently no way of replacing the default
allocator with a custom one.

This commit allows custom allocators to be used during the
table initialization. The default behavior of the hash table
remains unaffected, by using the stdlib calloc() and free(),
if no custom allocator is given.

Signed-off-by: Xenofon Foukas <fon1989@gmail.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Change-Id: Id9a405e5dc42e5564ff8623394c86056a4d1ff48

ppc.h: use mftb on ppc

Older versions of GNU as do not support mftbl. The issue affects Darwin
PowerPC, as well as some older versions of NetBSD and Linux. Since mftb
is equivalent and universally understood, just use that.

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

rcutorture: Check histogram of ages

Ensure that the histogram of ages for all threads are valid after a stress test.

Change-Id: Iadc46f47fe8835ac0e2d8967b6a16a83335a9541
Signed-off-by: Olivier Dion <odion@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

docs: Add links to project resources

Indicate that Gerrit (https://review.lttng.org) is the principal place
where patches are submitted and reviewed, rather than the mailing list.

Based on feedback received on the mailing list:
https://lists.lttng.org/pipermail/lttng-dev/2023-November/030670.html

Change-Id: I19f1459045355c57a1f9932a3b540807ba3d4a1c
Signed-off-by: Kienan Stewart <kstewart@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix: allow clang to build liburcu on RISC-V

Clang also defines __GNUC__, so use URCU_GCC_VERSION to detect if built
with gcc.

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

Fix -Walloc-size

GCC 14 introduces a new -Walloc-size included in -Wextra which gives:
```
urcu-call-rcu-impl.h:912:20: warning: allocation of insufficient size '1' for type 'struct call_rcu_completion' with size '16' [-Walloc-size[https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Walloc-size]]
urcu-call-rcu-impl.h:927:22: warning: allocation of insufficient size '1' for type 'struct call_rcu_completion_work' with size '24' [-Walloc-size[https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Walloc-size]]
urcu-call-rcu-impl.h:912:20: warning: allocation of insufficient size '1' for type 'struct call_rcu_completion' with size '16' [-Walloc-size[https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Walloc-size]]
urcu-call-rcu-impl.h:927:22: warning: allocation of insufficient size '1' for type 'struct call_rcu_completion_work' with size '24' [-Walloc-size[https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Walloc-size]]
urcu-call-rcu-impl.h:912:20: warning: allocation of insufficient size '1' for type 'struct call_rcu_completion' with size '16' [-Walloc-size[https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Walloc-size]]
urcu-call-rcu-impl.h:927:22: warning: allocation of insufficient size '1' for type 'struct call_rcu_completion_work' with size '24' [-Walloc-size[https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Walloc-size]]
urcu-call-rcu-impl.h:912:20: warning: allocation of insufficient size '1' for type 'struct call_rcu_completion' with size '16' [-Walloc-size[https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Walloc-size]]
urcu-call-rcu-impl.h:927:22: warning: allocation of insufficient size '1' for type 'struct call_rcu_completion_work' with size '24' [-Walloc-size[https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Walloc-size]]
urcu-call-rcu-impl.h:912:20: warning: allocation of insufficient size '1' for type 'struct call_rcu_completion' with size '16' [-Walloc-size[https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Walloc-size]]
urcu-call-rcu-impl.h:927:22: warning: allocation of insufficient size '1' for type 'struct call_rcu_completion_work' with size '24' [-Walloc-size[https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Walloc-size]]
workqueue.c:401:20: warning: allocation of insufficient size '1' for type 'struct urcu_workqueue_completion' with size '16' [-Walloc-size[https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Walloc-size]]
workqueue.c:432:14: warning: allocation of insufficient size '1' for type 'struct urcu_workqueue_completion_work' with size '24' [-Walloc-size[https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Walloc-size]]
urcu-call-rcu-impl.h:912:20: warning: allocation of insufficient size '1' for type 'struct call_rcu_completion' with size '16' [-Walloc-size[https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Walloc-size]]
urcu-call-rcu-impl.h:927:22: warning: allocation of insufficient size '1' for type 'struct call_rcu_completion_work' with size '24' [-Walloc-size[https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Walloc-size]]
qsbr.c:49:14: warning: allocation of insufficient size ‘1’ for type ‘struct mynode’ with size ‘40’ [-Walloc-size[https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Walloc-size]]
mb.c:50:14: warning: allocation of insufficient size ‘1’ for type ‘struct mynode’ with size ‘40’ [-Walloc-size[https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Walloc-size]]
membarrier.c:50:14: warning: allocation of insufficient size ‘1’ for type ‘struct mynode’ with size ‘40’ [-Walloc-size[https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Walloc-size]]
signal.c:49:14: warning: allocation of insufficient size ‘1’ for type ‘struct mynode’ with size ‘40’ [-Walloc-size[https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Walloc-size]]
bp.c:49:14: warning: allocation of insufficient size ‘1’ for type ‘struct mynode’ with size ‘40’ [-Walloc-size[https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Walloc-size]]
```

The calloc prototype is:
```
void *calloc(size_t nmemb, size_t size);
```

So, just swap the number of members and size arguments to match the prototype, as
we're initialising 1 struct of size `sizeof(struct ...)`. GCC then sees we're not
doing anything wrong.

Signed-off-by: Sam James <sam@gentoo.org>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Change-Id: Id84ce5cf9a1b97bfa942597aa188ef6e27e7c10d

cleanup: use an enum for the error states of nr_cpus_mask

Using an enum with labels for error states instead of literal values
will make the code easier to read and understand.

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

fix: add missing SPDX licensing tags

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

urcu/uatomic/riscv: Mark RISC-V as broken

Implementations of some atomic operations of GCC for RISC-V are
insufficient for sequential consistency. For this reason Userspace RCU
is currently marked as `broken' for RISC-V with GCC. However, it is
still possible to use other toolchains.

See https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104831 for details.

For now, we mark every version of GCC as unsupported. Distribution
package maintainers will have to cherry-pick the relevant patches in GCC
then remove the #error in Userspace RCU if they want to support it.

As for us, we will incrementally add specific versions of GCC that have
fixed the issue whenever new stable releases are made from the GCC
project.

Change-Id: I2cd7c8f12068628b845a096e03f5f8100eacbe43
Signed-off-by: Olivier Dion <odion@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix: urcu-bp: misaligned reader accesses

This is a port from a fix in LTTng-UST's embedded urcu (d1a0fad8). The
original message follows:

    Running the LTTng-tools tests (test_valid_filter, for example) under
    address sanitizer results in the following warning:

      /usr/include/lttng/urcu/static/urcu-ust.h:155:6: runtime error: member access within misaligned address 0x7fc45db3a020 for type 'struct lttng_ust_urcu_reader', which requires 128 byte alignment
      0x7fc45db3a020: note: pointer points here
       c4 7f 00 00  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00
                    ^

    While the node member of lttng_ust_urcu_reader has an "aligned"
    attribute of CAA_CACHE_LINE_SIZE, the compiler can't ensure the
    alignment of members for dynamically allocated instances.

    The `data` pointer is changed from char* to struct
    lttng_ust_urcu_reader*, allowing the compiler to enforce the expected
    alignment constraints.

    Since `data` was addressed in bytes, the code using this field is
    adapted to use element counts. As the chunks are only used to allocate
    reader instances (and not other types), it makes the code a bit easier
    to read.

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

rculfhash: Only pass integral types to atomic builtins

Clang expects the pointers passed to atomic builtins to be integral. Fix
this by casting nodes address to uintptr_t *.

Change-Id: Ifb8833c493df849a542a22f0bb2baeeb85be0297
Signed-off-by: Olivier Dion <odion@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

LoongArch: Document that byte and short atomics are implemented with LL/SC

Based on the LoongArch Reference Manual:

https://loongson.github.io/LoongArch-Documentation/LoongArch-Vol1-EN.html

Section 2.2.7 "Atomic Memory Access Instructions" only lists atomic
operations for 32-bit and 64-bit integers. As detailed in Section
2.2.7.1, LL/SC instructions operating on 32-bit and 64-bit integers are
also available. Those are used by the compiler to support atomics on
byte and short types.

This means atomics on 32-bit and 64-bit types have stronger forward
progress guarantees than those operating on 8-bit and 16-bit types.

Link: https://github.com/urcu/userspace-rcu/pull/11#issuecomment-1706528796
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Change-Id: I01569b718f7300a46d984c34065c0bbfbd2f7cc6

Add LoongArch support

This commit completes LoongArch support.

LoongArch supports byte and short atomic operations,
and defines UATOMIC_HAS_ATOMIC_BYTE and UATOMIC_HAS_ATOMIC_SHORT.

Signed-off-by: Wang Jing <wangjing@loongson.cn>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Change-Id: I335e654939bfc90994275f2a4fad550c95f3eba4

Tests: Add test for byte/short atomics on addresses which are not word-aligned

Add a unit test to catch architectures which do not allow byte and short
atomic operations on addresses which are not word aligned.

If an architecture supports byte and short atomic operations, it should
be valid to issue those operations on variables which are not
word-aligned, otherwise the architecture should not define
UATOMIC_HAS_ATOMIC_BYTE nor UATOMIC_HAS_ATOMIC_SHORT.

This should help identify architectures which mistakenly define
UATOMIC_HAS_ATOMIC_BYTE and UATOMIC_HAS_ATOMIC_SHORT.

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

Complete removal of urcu-signal flavor

This commit completes removal of the urcu-signal flavor.

Users can migrate to liburcu-memb with a kernel implementing the
membarrier(2) system call to have similar read-side performance without
requiring use of a reserved signal, and with improved grace period
performance.

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

doc/examples: Remove urcu-signal example

Remove the urcu-signal example from documentation.

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

tests/common: Remove urcu-signal common test files

In preparation for deprecation of the urcu-signal flavor, remove the
urcu-signal common test files.

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

tests/benchmark: Remove urcu-signal benchmark tests

In preparation for deprecation of the urcu-signal flavor, remove the
urcu-signal benchmark tests.

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

tests/regression: Remove urcu-signal regression tests

In preparation for deprecation of the urcu-signal flavor, remove the
urcu-signal regression tests.

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

tests/unit: Remove urcu-signal unit tests

In preparation for deprecation of the urcu-signal flavor, remove the
urcu-signal unit tests.

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

Fix: Add missing cmm_smp_mb() in deprecated urcu-signal

commit 97d13221f8a1 ("Phase 1 of deprecating liburcu-signal") miss a
cmm_smp_mb() at the beginning of the read-side critical sections, which
causes spurious failures in the CI tests.

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

urcu/uatomic.h: Improve verbosity of static assert error messages

Improve verbosity of static assert error messages for value mismatch.

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

urcu/compiler: Add urcu_static_assert

Static assertion macros copied from LTTng-ust ust-compiler.h for
compatibility with compilers that do not support static assertion.

Change-Id: I5dfa8ba565041b522a1d5c226c7a9369979a3a02
Signed-off-by: Olivier Dion <odion@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Phase 1 of deprecating liburcu-signal

The first phase of liburcu-signal deprecation consists of implementing
it in term of liburcu-mb. In other words, liburcu-signal is identical to
liburcu-mb at the exception of the function symbols and public header
files.

This is done by:

  1) Removing the RCU_SIGNAL specific code in urcu.c

  2) Making the RCU_MB specific code also specific to RCU_SIGNAL in
  urcu.c

  3) Rewriting _urcu_signal_read_unlock_update_and_wakeup to use a
  atomic store with CMM_SEQ_CST instead of a store CMM_RELAXED with
  cmm_barrier() around it. We could keep the explicit barriers, but that
  would require to add some cmm_annotate annotations. Therefore, to be
  less intrusive in a public header file, simply use the CMM_SEQ_CST
  like for the mb flavor.

Change-Id: Ie406f7df2f47da0a9f464df94b968ad9204821f3
Signed-off-by: Olivier Dion <odion@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

uatomic/generic: Fix redundant declaration warning

abort(3) was explicitly declared external to avoid including
<stdlib.h>. However, this emit a redundant declaration warning if it was
already declared before including <urcu/uatomic.h>.

Fix this by including <stdlib.h> and not declaring abort().

Change-Id: If9557814c311e2b531e85fec8c41788462338fe4
Signed-off-by: Olivier Dion <odion@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

tests: Add tests for checking race conditions

These tests do nothing useful except of stress testing a
single-consumer, multiple-producers program on various data structures.

These tests are only meaningful when compiling liburcu with TSAN.

Change-Id: If22b27ed0fb95bf890947fc4e75f923edb5ada8f
Signed-off-by: Olivier Dion <odion@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Add cmm_emit_legacy_smp_mb()

Some public APIs stipulate implicit memory barriers on operations. These
were coherent with the memory model used at that time. However, with the
migration to a memory model closer to the C11 memory model, these memory
barriers are not strictly emitted by the atomic operations in the new
memory model.

Therefore, introducing the `--disable-legacy-mb' configuration
option. By default, liburcu is configured to emit these legacy memory
barriers, thus keeping backward compatibility at the expense of slower
performances. However, users can opt-out by disabling the legacy memory
barriers.

This options is publicly exported in the system configuration header
file and can be overrode manually on a compilation unit basis by
defining `CONFIG_RCU_EMIT_LEGACY_MB' before including any liburcu files.

The usage of this macro requires to re-write atomic operations in term
of the CMM memory model. This is done for the queue and stack APIs.

Change-Id: Ia5ce3b3d8cd1955556ce96fa4408a63aa098a1a6
Signed-off-by: Olivier Dion <odion@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

urcu/annotate: Add CMM annotation

The CMM annotation is highly experimental and not meant to be used by
user for now, even though it is exposed in the public API since some
parts of the liburcu public API require those annotations.

The main primitive is the cmm_annotate_t which denotes a group of memory
operations associated with a memory barrier. A group follows a state
machine, starting from the `CMM_ANNOTATE_VOID' state. The following are
the only valid transitions:

  CMM_ANNOTATE_VOID -> CMM_ANNOTATE_MB (acquire & release MB)
  CMM_ANNOTATE_VOID -> CMM_ANNOTATE_LOAD (acquire memory)
  CMM_ANNOTATE_LOAD -> CMM_ANNOTATE_MB (acquire MB)

The macro `cmm_annotate_define(name)' can be used to create an
annotation object on the stack. The rest of the `cmm_annotate_*' macros
can be used to change the state of the group after validating that the
transition is allowed. Some of these macros also inject TSAN annotations
to help it understand the flow of events in the program since it does
not currently support thread fence.

Sometime, a single memory access does not need to be associated with a
group. In the case, the acquire/release macros variant without the
`group' infix can be used to annotate memory accesses.

Note that TSAN can not be used on the liburcu-signal flavor. This is
because TSAN hijacks calls to sigaction(3) and places its own handler
that will deliver the signal to the application at a synchronization
point.

Thus, the usage of TSAN on the signal flavor is undefined
behavior. However, there's at least one known behavior which is a
deadlock between readers that want to unregister them-self by locking
the `rcu_registry_lock' while a synchronize RCU is made on the writer
side which has already locked that mutex until all the registered
readers execute a memory barrier in a signal handler defined by
liburcu-signal. However, TSAN will not call the registered handler while
waiting on the mutex. Therefore, the writer spin infinitely on
pthread_kill(3p) because the reader simply never complete the handshake.

See the deadlock minimal reproducer below.

Deadlock reproducer:
```
  #include <poll.h>
  #include <signal.h>

  #include <pthread.h>

  #define SIGURCU SIGUSR1

  static pthread_mutex_t rcu_registry_lock = PTHREAD_MUTEX_INITIALIZER;
  static int need_mb = 0;

  static void *reader_side(void *nil)
  {
   (void) nil;

   pthread_mutex_lock(&rcu_registry_lock);
   pthread_mutex_unlock(&rcu_registry_lock);

   return NULL;
  }

  static void writer_side(pthread_t reader)
  {
   __atomic_store_n(&need_mb, 1, __ATOMIC_RELEASE);
   while (__atomic_load_n(&need_mb, __ATOMIC_ACQUIRE)) {
   pthread_kill(reader, SIGURCU);
   (void) poll(NULL, 0, 1);
   }
   pthread_mutex_unlock(&rcu_registry_lock);

   pthread_join(reader, NULL);
  }

  static void sigrcu_handler(int signo, siginfo_t *siginfo, void *context)
  {
   (void) signo;
   (void) siginfo;
   (void) context;

   __atomic_store_n(&need_mb, 0, __ATOMIC_SEQ_CST);
  }

  static void install_signal(void)
  {
   struct sigaction act;

   act.sa_sigaction = sigrcu_handler;
   act.sa_flags     = SA_SIGINFO | SA_RESTART;

   sigemptyset(&act.sa_mask);

   (void) sigaction(SIGURCU, &act, NULL);
  }

  int main(void)
  {
   pthread_t th;

   install_signal();

   pthread_mutex_lock(&rcu_registry_lock);
   pthread_create(&th, NULL, reader_side, NULL);

   writer_side(th);

   return 0;
  }
```

Change-Id: I9c234bb311cc0f82ea9dbefdf4fee07047ab93f9
Co-authored-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Signed-off-by: Olivier Dion <odion@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

tests/unit/test_build: Quiet unused return value

Change-Id: Ie5a18e0ccc4b1b5ee85c5bd140561cc2ff9e2fbc
Co-authored-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Signed-off-by: Olivier Dion <odion@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

benchmark: Use uatomic for accessing global states

Global states accesses were protected via memory barriers. Use the
uatomic API with the CMM memory model so that TSAN can understand the
ordering imposed by the synchronization flags.

Change-Id: I1bf5702c5ac470f308c478effe39e424a3158060
Co-authored-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Signed-off-by: Olivier Dion <odion@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

tests: Use uatomic for accessing global states

Global states accesses were protected via memory barriers. Use the
uatomic API with the CMM memory model so that TSAN does not warn about
non-atomic concurrent accesses.

Also, the thread id map mutex must be unlocked after setting the new
created thread id in the map. Otherwise, the new thread could observe an
unset id.

Change-Id: I1ecdc387b3f510621cbc116ad3b95c676f5d659a
Co-authored-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Signed-off-by: Olivier Dion <odion@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

urcu-wait: Fix wait state load/store

The state of a wait node must be accessed atomically. Also, the action
of busy loading until the teardown state is seen must follow a
CMM_ACQUIRE semantic while storing the teardown must follow a
CMM_RELEASE semantic.

Change-Id: I9cd9cf4cd9ab2081551d7f33c0b1c23c3cf3942f
Co-authored-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Signed-off-by: Olivier Dion <odion@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Add CMM memory model

Introducing the CMM memory model with the following new primitives:

  - uatomic_load(addr, memory_order)

  - uatomic_store(addr, value, memory_order)
  - uatomic_and_mo(addr, mask, memory_order)
  - uatomic_or_mo(addr, mask, memory_order)
  - uatomic_add_mo(addr, value, memory_order)
  - uatomic_sub_mo(addr, value, memory_order)
  - uatomic_inc_mo(addr, memory_order)
  - uatomic_dec_mo(addr, memory_order)

  - uatomic_add_return_mo(addr, value, memory_order)
  - uatomic_sub_return_mo(addr, value, memory_order)

  - uatomic_xchg_mo(addr, value, memory_order)

  - uatomic_cmpxchg_mo(addr, old, new,
                       memory_order_success,
                       memory_order_failure)

The CMM memory model reflects the C11 memory model with an additional
CMM_SEQ_CST_FENCE memory order. The memory order can be selected through
the enum cmm_memorder.

* With Atomic Builtins

If configured with atomic builtins, the correspondence between the CMM
memory model and the C11 memory model is a one to one at the exception
of the CMM_SEQ_CST_FENCE memory order which implies the memory order
CMM_SEQ_CST and a thread fence after the operation.

* Without Atomic Builtins

However, if not configured with atomic builtins, the following stipulate
the memory model.

For load operations with uatomic_load(), the memory orders CMM_RELAXED,
CMM_CONSUME, CMM_ACQUIRE, CMM_SEQ_CST and CMM_SEQ_CST_FENCE are
allowed. A barrier may be inserted before and after the load from memory
depending on the memory order:

  - CMM_RELAXED: No barrier
  - CMM_CONSUME: Memory barrier after read
  - CMM_ACQUIRE: Memory barrier after read
  - CMM_SEQ_CST: Memory barriers before and after read
  - CMM_SEQ_CST_FENCE: Memory barriers before and after read

For store operations with uatomic_store(), the memory orders
CMM_RELAXED, CMM_RELEASE, CMM_SEQ_CST and CMM_SEQ_CST_FENCE are
allowed. A barrier may be inserted before and after the store to memory
depending on the memory order:

  - CMM_RELAXED: No barrier
  - CMM_RELEASE: Memory barrier before operation
  - CMM_SEQ_CST: Memory barriers before and after operation
  - CMM_SEQ_CST_FENCE: Memory barriers before and after operation

For load/store operations with uatomic_and_mo(), uatomic_or_mo(),
uatomic_add_mo(), uatomic_sub_mo(), uatomic_inc_mo(), uatomic_dec_mo(),
uatomic_add_return_mo() and uatomic_sub_return_mo(), all memory orders
are allowed. A barrier may be inserted before and after the operation
depending on the memory order:

  - CMM_RELAXED: No barrier
  - CMM_ACQUIRE: Memory barrier after operation
  - CMM_CONSUME: Memory barrier after operation
  - CMM_RELEASE: Memory barrier before operation
  - CMM_ACQ_REL: Memory barriers before and after operation
  - CMM_SEQ_CST: Memory barriers before and after operation
  - CMM_SEQ_CST_FENCE: Memory barriers before and after operation

For the exchange operation uatomic_xchg_mo(), any memory order is
valid. A barrier may be inserted before and after the exchange to memory
depending on the memory order:

  - CMM_RELAXED: No barrier
  - CMM_ACQUIRE: Memory barrier after operation
  - CMM_CONSUME: Memory barrier after operation
  - CMM_RELEASE: Memory barrier before operation
  - CMM_ACQ_REL: Memory barriers before and after operation
  - CMM_SEQ_CST: Memory barriers before and after operation
  - CMM_SEQ_CST_FENCE: Memory barriers before and after operation

For the compare exchange operation uatomic_cmpxchg_mo(), the success
memory order can be anything while the failure memory order cannot be
CMM_RELEASE nor CMM_ACQ_REL and cannot be stronger than the success
memory order. A barrier may be inserted before and after the store to
memory depending on the memory orders:

 Success memory order:

  - CMM_RELAXED: No barrier
  - CMM_ACQUIRE: Memory barrier after operation
  - CMM_CONSUME: Memory barrier after operation
  - CMM_RELEASE: Memory barrier before operation
  - CMM_ACQ_REL: Memory barriers before and after operation
  - CMM_SEQ_CST: Memory barriers before and after operation
  - CMM_SEQ_CST_FENCE: Memory barriers before and after operation

  Barriers after the operations are only emitted if the compare exchange
  succeed.

 Failure memory order:
  - CMM_RELAXED: No barrier
  - CMM_ACQUIRE: Memory barrier after operation
  - CMM_CONSUME: Memory barrier after operation
  - CMM_SEQ_CST: Memory barriers before and after operation
  - CMM_SEQ_CST_FENCE: Memory barriers before and after operation

  Barriers after the operations are only emitted if the compare exchange
  failed.  Barriers before the operation are never emitted by this
  memory order.

Change-Id: I213ba19c84e82a63083f00143a3142ffbdab1d52
Co-authored-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Signed-off-by: Olivier Dion <odion@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

urcu/arch/generic: Use atomic builtins if configured

If configured to use atomic builtins, implement SMP memory barriers in
term of atomic builtins if the architecture does not implement its own
version.

Change-Id: Iddc4283606e0fce572e104d2d3f03b5c0d9926fb
Co-authored-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Signed-off-by: Olivier Dion <odion@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

urcu/compiler: Use atomic builtins if configured

Use __atomic_signal_fence(__ATOMIC_SEQ_CST) for cmm_barrier() if
configured to use atomic builtins.

Change-Id: Ib168b50f1e97a8da861b92d6882c56db230ebb2c
Co-authored-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Signed-off-by: Olivier Dion <odion@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

configure: Add --enable-compiler-atomic-builtins option

If the toolchain supports atomic builtins and the user ask for atomic
builtins, use them for the uatomic API. This requires that the
toolchains used to compile the library and the user application supports
such builtins.

The advantage of using these builtins is that they are well known
synchronization primitives by several tools such as TSAN.

However, they may introduce redundant memory barriers, mainly on
strongly ordered architectures.

Change-Id: Ia8e97112681f744f17816dbc4cbbec805a483331
Co-authored-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Signed-off-by: Olivier Dion <odion@efficios.com>
Signed-off-by: Michael Jeanson <mjeanson@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix: tests/rcutorture: Put thread offline on busy-wait

Change-Id: Ic12b7df5d70b474f1e87f0710d3a55e5f906c020
Signed-off-by: Olivier Dion <odion@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

tests/regression/rcutorture: Use urcu-wait

pthread_cond_wait(3) can have spurious wakeups on some OS. To detect
such spurious wakeup, a global variable is shared between the waiter and
the waker.

We can use urcu-wait instead.

Change-Id: I6a2d2f3c9104ea23df16a7c8ba3557bb5d58306c
Signed-off-by: Olivier Dion <odion@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

tests/rcutorture: Factor out thread registration

Register the thread once at the begining of the update routine. Put the
thread offline when doing anything that can block.

Change-Id: I345e04ee2ef0b5ba2f065b8a3029dd0e6130037b
Signed-off-by: Olivier Dion <odion@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

tests/regression/rcutorture: Add wait state

pthread_cond_wait(3) can have spurious wakeups. Fix this by polling a
state associated with the the wait.

Change-Id: Iba034cba5f72ad88388d1b90a6093f4ae9f9beb9
Signed-off-by: Olivier Dion <odion@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

urcu-wait: Initialize node in URCU_WAIT_NODE_INIT

C++ emits warnings with the URCU_WAIT_NODE_INIT() macro because the
member node is not initialized.

Fix this by initializing the node to null.

Change-Id: I7ee3b35624ef61cab826e3668f111e2483ca3c05
Signed-off-by: Olivier Dion <odion@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Complete REUSE support

The SPDX identifiers [1] are a legally binding shorthand, which can be
used instead of the full boiler plate text. This is the final step
towards implementing the full REUSE spec [2] to help with copyright and
licensing audits and compliance.

This will reduce a lot a manual work required for the licensing audit
required in Debian on each update.

[1] https://spdx.org/ids-how
[2] https://reuse.software/tutorial/

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

extras/abi: license data files under CC-1.0

The SPDX identifiers [1] are a legally binding shorthand, which can be
used instead of the full boiler plate text. This is another step towards
implementing the full REUSE spec [2] to help with copyright and
licensing audits and compliance.

This will reduce a lot a manual work required for the licensing audit
required in Debian on each update.

These are generated files, use the CC-1.0 license to make their
licensing clear.

[1] https://spdx.org/ids-how
[2] https://reuse.software/tutorial/

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

examples: use SPDX identifiers

The SPDX identifiers [1] are a legally binding shorthand, which can be
used instead of the full boiler plate text. This is another step towards
implementing the full REUSE spec [2] to help with copyright and
licensing audits and compliance.

This will reduce a lot a manual work required for the licensing audit
required in Debian on each update.

Relicense all examples from 'Boehm-GC' to the more well-known and
functionnaly identical 'MIT' license. This is possible since all the
examples were written by Mathieu Desnoyers and only a few trivial fixes
from external contributors were applied over the years.

[1] https://spdx.org/ids-how
[2] https://reuse.software/tutorial/

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

tests: use SPDX identifiers

The SPDX identifiers [1] are a legally binding shorthand, which can be
used instead of the full boiler plate text. This is another step towards
implementing the full REUSE spec [2] to help with copyright and
licensing audits and compliance.

This will reduce a lot a manual work required for the licensing audit
required in Debian on each update.

For files that lacked copyright and licensing information, I used the
following guidelines. Use the author from the git history and the test
scripts license as stated in LICENSE, 'GPL-2.0-only'.

[1] https://spdx.org/ids-how
[2] https://reuse.software/tutorial/

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

src: use SPDX identifiers

The SPDX identifiers [1] are a legally binding shorthand, which can be
used instead of the full boiler plate text. This is another step towards
implementing the full REUSE spec [2] to help with copyright and
licensing audits and compliance.

This will reduce a lot a manual work required for the licensing audit
required in Debian on each update.

[1] https://spdx.org/ids-how
[2] https://reuse.software/tutorial/

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

Public headers: use SPDX identifiers

The SPDX identifiers [1] are a legally binding shorthand, which can be
used instead of the full boiler plate text. This is another step towards
implementing the full REUSE spec [2] to help with copyright and
licensing audits and compliance.

This will reduce a lot a manual work required for the licensing audit
required in Debian on each update.

For files that lacked copyright and licensing information, I used the
following guidelines. Use the author from the git history and the main
project license 'LGPL-2.1-or-later'.

[1] https://spdx.org/ids-how
[2] https://reuse.software/tutorial/

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

Build system: use SPDX identifiers

The SPDX identifiers [1] are a legally binding shorthand, which can be
used instead of the full boiler plate text. This is the first step
towards implementing the full REUSE spec [2] to help with copyright and
licensing audits and compliance.

This will reduce a lot a manual work required for the licensing audit
required in Debian on each update.

For files that lacked copyright and licensing information, I used the
following guidelines. If a clear author could be determined from the git
history use it, otherwise use 'EfficiOS Inc.'. For build system files,
use 'MIT', for documentation 'CC-BY-4.0' and for data files 'CC-1.0'.

[1] https://spdx.org/ids-how
[2] https://reuse.software/tutorial/

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

Fix: urcu-wait: add missing futex.h include

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

doc: update GCC baseline to 4.8

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

doc: update FreeBSD tested version

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

doc: Remove Solaris from tested platforms

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

Revert "compiler.h: Introduce caa_unqual_scalar_typeof"

This reverts commit 67988e204d2c471b24cae61f3f8fedb4f9375034.

_Generic requires C11, but liburcu supports C99.

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

rculfhash: Use caa_container_of_check_null in cds_lfht_entry

Use caa_container_of_check_null in cds_lfht_entry to allow removing
caa_unqual_scalar_typeof, which requires C11.

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

compiler.h: Introduce caa_container_of_check_null

The approach taken by caa_unqual_scalar_typeof requires use of _Generic
which requires full C11 support. Currently liburcu supports C99.
Therefore, this approach is not appropriate for now.

Instead, introduce caa_container_of_check_null which returns NULL if the
ptr is NULL before offsetting by the member offset.

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

compiler.h: Introduce caa_unqual_scalar_typeof

Allow defining variables and cast with a typeof which removes the
volatile and const qualifiers.

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

Avoid calling caa_container_of on NULL pointer in cds_lfht macros

The cds_lfht_for_each_entry and cds_lfht_for_each_entry_duplicate macros
would call caa_container_of() macro on NULL pointer.  This is not a
problem under normal circumstances as the check in the for loop fails
and the loop-statement is not called with invalid (pos) value.

However AddressSanitizer doesn't like that and complains about this:

    runtime error: applying non-zero offset 18446744073709551056 to null pointer

Move the cds_lfht_iter_get_node(iter) != NULL from the cond-expression
of the for loop into both init-clause and iteration-expression as
conditional operator and check for (pos) value in the cond-expression
instead. Introduce the cds_lfht_entry() macro to eliminate code
duplication.

Reported-by: Ondřej Surý <ondrej@sury.org>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Change-Id: I9969c1e0bc0eefc8c90c0d8f17b2927f6a4feb2a

Fix: revise urcu_read_lock_update() comment

Read-side critical section nesting is tracked in lower-order bits
and grace-period phase number use a single high-order bit.

Signed-off-by: Li-Kuan Ou <k777k777tw@gmail.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Change-Id: I4fc185aa12a367e997fa20bf37793cfb2023c96f

Fix: uatomic powerpc comment about lwsync

lwsync allows prior stores to be reordered against following loads.

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

fix: aarch64: allow RHEL7 gcc 4.8.5-11

The patch for GCC upstream bug 63293[1] was backported in RHEL7 gcc
4.8.5-11 package, allow building with this version.

[1] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63293

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

aarch64: Implement caa_cpu_relax as yield instruction

Use the aarch64 "yield" instruction which has the wanted semantic for
caa_cpu_relax.

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

fix: warning 'noreturn' function does return on ppc

On a ppc64 system with gcc 9.5.0 I get the following error when building
with -O0 :

/usr/include/urcu/uatomic/generic.h: In function 'void _uatomic_link_error()':
/usr/include/urcu/uatomic/generic.h:53:1: warning: 'noreturn' function does return
   53 | }
      | ^

Split the inline function in 2 variants and apply the noreturn attribute
only on the builtin_trap one.

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

Fix: use __noreturn__ for C11-compatibility

The noreturn convenience macro provided by stdnoreturn.h might get
included before urcu headers, use __noreturn__ for better compatibility
with code using <stdnoreturn.h> header.

Signed-off-by: Ondřej Surý <ondrej@sury.org>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Adjust shell scripts to allow Bash in other locations

Linux-based OS for the most part provide Bash and being located in /bin,
but on other OS's the shell would be in another location. Utilize env(1)
and allow it to be located elsewhere.

Signed-off-by: Brad Smith <brad@comstyle.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Change-Id: I9d4d4a3feaf993754c64b740ea91e42b336ba2b4

Add support for OpenBSD

- Add OpenBSD to syscall compatibility header as appropriate.
- Add function for retrieving the thread id in urcu_get_thread_id().
- Rely on pthread cond variables for futex compatibility.

It builds on all of our archs and fully run time tested on amd64.

Signed-off-by: Brad Smith <brad@comstyle.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Change-Id: I5cca5962ba3dc3113c9bd12e544b6e6f77dfdb61

Bump version to 0.15.0-pre

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

Version 0.14.0

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

Fix: urcu-bp: only teardown call-rcu worker in destructor

Do not invoke urcu_call_rcu_exit() every time a reader thread
unregisters from urcu-bp. This causes pthread join hangs observed on
Cygwin.

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

Fix: rculfhash: urcu_die() takes positive error value

Found by Coverity:

** CID 1504537:  Error handling issues  (NEGATIVE_RETURNS)
/src/rculfhash.c: 1934 in do_auto_resize_destroy_cb()

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

Fix: call_rcu: teardown default call_rcu worker on application exit

Teardown the default call_rcu worker thread if there are no queued
callbacks on process exit. This prevents leaking memory.

Here is how an application can ensure graceful teardown of this
worker thread:

- An application queuing call_rcu callbacks should invoke
  rcu_barrier() before it exits.
- When chaining call_rcu callbacks, the number of calls to
  rcu_barrier() on application exit must match at least the maximum
  number of chained callbacks.
- If an application chains callbacks endlessly, it would have to be
  modified to stop chaining callbacks when it detects an application
  exit (e.g. with a flag), and wait for quiescence with rcu_barrier()
  after setting that flag.
- The statements above apply to a library which queues call_rcu
  callbacks, only it needs to invoke rcu_barrier in its library
  destructor.

Fixes: #1317
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Change-Id: I40556bc872d3df58a22fb88a0dbb528ce5c9b4af

Fix: join worker thread in call_rcu_data_free

When freeing the call rcu descriptor, join its associated thread as well
to ensure complete teardown.

Fixes: #1317
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Change-Id: Ic522e0466f56deca8bde519e082f3d7f99ec2e7f

Docs: clarify grace period polling API

Reword the existing grace period polling API documentation. The
changes are:

  - Replace "should" by "must" to express obligations,
  - Attempt to clarify "which" grace period the API allows checking for.

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

Document grace period polling in rcu-api.md

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

Implement poll rcu stress test in rcutorture

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

urcu-memb,mb,signal: Implement grace period polling

Implement a grace period polling mechanism for each urcu flavor. Its use
is documented in README.md.

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

Fix: auto-resize hash table destroy deadlock

Fix a deadlock for auto-resize hash tables when cds_lfht_destroy
is called with RCU read-side lock held.

Example stack track of a hang:

  Thread 2 (Thread 0x7f21ba876700 (LWP 26114)):
  #0  syscall () at ../sysdeps/unix/sysv/linux/x86_64/syscall.S:38
  #1  0x00007f21beba7aa0 in futex (val3=0, uaddr2=0x0, timeout=0x0, val=-1, op=0, uaddr=0x7f21bedac308 <urcu_memb_gp+8>) at ../include/urcu/futex.h:81
  #2  futex_noasync (timeout=0x0, uaddr2=0x0, val3=0, val=-1, op=0, uaddr=0x7f21bedac308 <urcu_memb_gp+8>) at ../include/urcu/futex.h:90
  #3  wait_gp () at urcu.c:265
  #4  wait_for_readers (input_readers=input_readers@entry=0x7f21ba8751b0, cur_snap_readers=cur_snap_readers@entry=0x0,
      qsreaders=qsreaders@entry=0x7f21ba8751c0) at urcu.c:357
  #5  0x00007f21beba8339 in urcu_memb_synchronize_rcu () at urcu.c:498
  #6  0x00007f21be99f93f in fini_table (last_order=<optimized out>, first_order=13, ht=0x5651cec75400) at rculfhash.c:1489
  #7  _do_cds_lfht_shrink (new_size=<optimized out>, old_size=<optimized out>, ht=0x5651cec75400) at rculfhash.c:2001
  #8  _do_cds_lfht_resize (ht=ht@entry=0x5651cec75400) at rculfhash.c:2023
  #9  0x00007f21be99fa26 in do_resize_cb (work=0x5651e20621a0) at rculfhash.c:2063
  #10 0x00007f21be99dbfd in workqueue_thread (arg=0x5651cec74a00) at workqueue.c:234
  #11 0x00007f21bd7c06db in start_thread (arg=0x7f21ba876700) at pthread_create.c:463
  #12 0x00007f21bd4e961f in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:95

  Thread 1 (Thread 0x7f21bf285300 (LWP 26098)):
  #0  syscall () at ../sysdeps/unix/sysv/linux/x86_64/syscall.S:38
  #1  0x00007f21be99d8b7 in futex (val3=0, uaddr2=0x0, timeout=0x0, val=-1, op=0, uaddr=0x5651d8b38584) at ../include/urcu/futex.h:81
  #2  futex_async (timeout=0x0, uaddr2=0x0, val3=0, val=-1, op=0, uaddr=0x5651d8b38584) at ../include/urcu/futex.h:113
  #3  futex_wait (futex=futex@entry=0x5651d8b38584) at workqueue.c:135
  #4  0x00007f21be99e2c8 in urcu_workqueue_wait_completion (completion=completion@entry=0x5651d8b38580) at workqueue.c:423
  #5  0x00007f21be99e3f9 in urcu_workqueue_flush_queued_work (workqueue=0x5651cec74a00) at workqueue.c:452
  #6  0x00007f21be9a0c83 in cds_lfht_destroy (ht=0x5651d8b2fcf0, attr=attr@entry=0x0) at rculfhash.c:1906

This deadlock is easy to reproduce when rapidly adding a large number of
entries in the cds_lfht, removing them, and calling cds_lfht_destroy().

The deadlock will occur if the call to cds_lfht_destroy() takes place
while a resize of the hash table is ongoing.

Fix this by moving the teardown of the lfht worker thread to libcds
library destructor, so it does not have to wait on synchronize_rcu from
a resize callback from within a read-side critical section. As a
consequence, the atfork callbacks are left registered within each urcu
flavor for which a resizeable hash table is created until the end of the
executable lifetime.

The other part of the fix is to move the hash table destruction to the
worker thread for auto-resize hash tables. This prevents having to wait
for resize callbacks from RCU read-side critical section. This is
guaranteed by the fact that the worker thread serializes previously
queued resize callbacks before the destroy callback.

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

Fix building on MSYS2

Update cygwin libtool config in `configure.ac` to match MSYS2 build
environments as well. MSYS2 is also a Windows build environment that
produces DLLs.

Signed-off-by: Christopher Ng <facboy@gmail.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Change-Id: I48ca648123fd40b8003c72c0447c70a8b4bde6d6

rculfhash: Include rculfhash-internal.h from local directory

Use double quotes rather than angle brackets to include this local
header file. This fixes build scenarios where the liburcu build is used
from cmake.

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

Remove "Darwin" from "should also work on list"

MacOS is already covered in the "tested on" list, and standalone Darwin
is relatively niche (http://www.puredarwin.org/).

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

Merge branch 'adah1972-improve-md'

Change-Id: I7904f3cee368428a21fdd84d07c395e232f5cfdb

Add semicolons at the end of function prototypes

This pleases the syntax highlighter for multi-line code. Also, other
files already have semicolons.

Signed-off-by: Wu Yongwei <wuyongwei@gmail.com>

Wrap a file name in backticks

For consistency.

Signed-off-by: Wu Yongwei <wuyongwei@gmail.com>