hlist: implement cds_hlist_empty

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

rcuja: partial implementation of cds_ja_del

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

rcuja: implement ja_node_clear_nth

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

rcuja: extend tests, more fixes

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

rcuja: fix max depth test

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

rcuja: swap key

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

rcuja: add fallback nodes

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

rcuja: various fixes

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

rcuja: add basic test

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

rcuja: create shadow node for root

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

rcuja: implement add

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

rcuja: implement lookup

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

rcuja: rename cds_ja_node to cds_ja_inode

inode for internal node.

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

rcuja: new and destroy

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

rcuja: rename to cds_ja

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

rcuja: add comment about use of number of nodes

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

rcuja: fix iteration on recompact add

We must iterate on all entries by position, not by value.

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

rcuja: share lock across all nodes with same key

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

rcuja: no need to link with urcu lib anymore

Now that we use the rcu flavor provided as parameter by the application,
there is no need to link with a urcu lib flavor.

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

rcuja: use rcu ja app flavor for shadow hash table

Since we use call_rcu to delay reclaim of the rcu ja node too, we need
to use the same RCU flavor as the application that calls the RCU JA API.

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

rcuja: shadow clear also frees the rcu ja node associated

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

rcuja: implement shadow node hash table

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

rcuja: add shadow nodes hash table

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

rcuja: add data structures for rcu_ja and shadow nodes

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

rcuja: add missing assign in recompact

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

rcuja: implement node add recompaction

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

rcuja: set node update, rcu-ize get node/set node

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

rcuja: cleanup

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

rcuja: implement node set nth

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

rcuja: introduce union to represent nodes

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

rcuja testpop: print extra items in subclass instead of confusing "unbalance"

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

Use statistical approach to approximate the max number of nodes per population

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

rcuja: Update design document, discuss pool distributions

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

rcuja: use pool of linear array instead of bitmap

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

RCU judy array: implement node get functions

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

rcuja: Increase granularity

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

RCU Judy Array Design and initial files

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

Fix: membarrier fallback symbol conflict

* Lai Jiangshan (laijs@cn.fujitsu.com) wrote:
> Hi, Mathieu,
>
> There is a big compatible problem in URCU which should be fix in next round.
>
> LB: liburcu built on the system which has sys_membarrier().
> LU: liburcu built on the system which does NOT have sys_membarrier().
>
> LBM: liburcu-mb ....
> LUM: liburcu-mb ...
>
> AB: application(-lliburcu) built on the system which has sys_membarrier().
> AU: application(-lliburcu) built on the system which does NOT have
> sys_membarrier().
>
> ABM application(-lliburcu-mb) ...
> AUM application(-lliburcu-mb) ...
>
> AB/AU + LB/LU: 4 combinations
> ABM/AUM + LBM/LUM: 4 combinations
>
> I remember some of the 8 combinations can't works due to symbols are
> miss match.  only LU+AB and LB+AU ?
>
> could you check it?
>
> How to fix it: In LU and AU, keep all the symbol name/ABI as LA and
> AB, but only the behaviors falls back to URCU_MB.

Define membarrier() as -ENOSYS when SYS_membarrier is not found in the
system headers. Check dynamically for membarrier availability to ensure
ABI compatibility between applications and librairies.

Reported-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix: Use a filled signal mask to disable all signals

Changelog from David Pelton's original patch:

While using lttng-ust with an application that was calling fork()
with pending signals, I found that all signals were getting unmasked
shortly before the underlying call to fork().  After some
investigation, I found that the rcu_bp_before_fork() function was
unmasking all signals.  Based on the comments for this function, it
should be masking all signals.  Inspection of the rest of the code
in urcu-bp.c revealed the same pattern in two other functions.

This patch changes the code to use a filled signal mask to disable
all signals.  The change to rcu_bp_before_fork() addressed the
problem I was seeing while using lttng-ust.  The changes to the
other two functions appear to fix other instances of the same
problem.

Updates by Mathieu Desnoyers:

- Use SIG_BLOCK instead of SIG_SETMASK when setting a filled mask. This
  has the same behavior in this case (since we're blocking all signals),
  but is semantically neater: if we ever some signals from that mask,
  we'd like to to a union with the signal mask already blocked by the
  application.
- Also fix incorrect signal masking in compat_arch_x86.c.

Reported-by: David Pelton <dpelton@ciena.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

urcu-bp: introduce struct urcu_gp

Make urcu-bp similar to urcu-qsbr and other urcu flavors.

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

Fix: struct urcu_gp broke multiflavor

Add mapping to namespace urcu_gp.

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

Cleanup test usage printout

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

wfstack tests: use pop "last" state info

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

wfstack: return whether pop is popping the last element

Newly introduced "with_state" pop API members return stack state
atomically sampled with the pop operation.

Allow testing behavior of pop with respect to number of push-to-empty
and pop-all-from-non-empty.

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

wfcqueue tests: use dequeue empty state

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

wfcqueue: return whether dequeue is dequeuing last element

Newly introduced "with_state" dequeue API members return queue state
atomically sampled with the dequeue operation.

Allow testing behavior of dequeue with respect to number of
enqueue-to-empty and splice-from-non-empty.

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

urcu: avoid false sharing for rcu_gp_ctr

@rcu_gp_ctr and @registry share the same cache line, it causes
false sharing and slowdown both of the read site and update site.

Fix: Use different cache line for them.

Although rcu_gp_futex is updated less than rcu_gp_ctr, but
they always be accessed at almost the same time, so we also move rcu_gp_futex
to the cacheline of rcu_gp_ctr to reduce the cacheline-usage or cache-missing
of read site.

test: (4X6=24 CPUs)

Before patch:

[root@localhost userspace-rcu]# ./tests/test_urcu_mb 20 1 20
SUMMARY ./tests/test_urcu_mb      testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   1 wdelay      0 nr_reads   2100285330 nr_writes      3390219 nr_ops   2103675549
[root@localhost userspace-rcu]# ./tests/test_urcu_mb 20 1 20
SUMMARY ./tests/test_urcu_mb      testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   1 wdelay      0 nr_reads   1619868562 nr_writes      3529478 nr_ops   1623398040
[root@localhost userspace-rcu]# ./tests/test_urcu_mb 20 1 20
SUMMARY ./tests/test_urcu_mb      testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   1 wdelay      0 nr_reads   1949067038 nr_writes      3469334 nr_ops   1952536372

after patch:

[root@localhost userspace-rcu]# ./tests/test_urcu_mb 20 1 20
SUMMARY ./tests/test_urcu_mb      testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   1 wdelay      0 nr_reads   3380191848 nr_writes      4903248 nr_ops   3385095096
[root@localhost userspace-rcu]# ./tests/test_urcu_mb 20 1 20
SUMMARY ./tests/test_urcu_mb      testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   1 wdelay      0 nr_reads   3397637486 nr_writes      4129809 nr_ops   3401767295

Singed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

urcu: make the code of urcu-qsbr as normal urcu

urcu-qsbr's read site's quiescence is much longer than normal urcu ==>
synchronize_rcu() is much slower ==>
rcu_gp_ctr is updated much less ==>
the whole urcu-qsbr will not be slowed down by false sharing of rcu_gp_ctr.

But this patch makes sense to keep the code of urcu-qsbr like normal urcu,
better readability and maintenance.

Test: (4*6 CPUs)
Before patch:
[root@localhost userspace-rcu]# ./tests/test_urcu_qsbr 20 1 20
SUMMARY ./tests/test_urcu_qsbr    testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   1 wdelay      0 nr_reads  65498297587 nr_writes      2000665 nr_ops  65500298252
[root@localhost userspace-rcu]# ./tests/test_urcu_qsbr 20 1 20
SUMMARY ./tests/test_urcu_qsbr    testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   1 wdelay      0 nr_reads  67218079467 nr_writes      1981593 nr_ops  67220061060

After patch
./tests/test_urcu_qsbr 20 1 20
SUMMARY ./tests/test_urcu_qsbr    testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   1 wdelay      0 nr_reads  67473798999 nr_writes      1999151 nr_ops  67475798150
[root@localhost userspace-rcu]# ./tests/test_urcu_qsbr 20 1 20
SUMMARY ./tests/test_urcu_qsbr    testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   1 wdelay      0 nr_reads  67065521397 nr_writes      1993956 nr_ops  67067515353

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

rculfhash: detect if resize/destroy are called within RCU read-side C.S.

Report errors.

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

Documentation: rculfhash: cds_lfht_resize not within read-side C.S.

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

fix: rculfhash don't change qsbr online state

resize and destroy should not change the QSBR online state. Use the new
rcu_read_ongoing() API for this.

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

Add rcu_read_ongoing() API to each urcu flavor

This will allow checking whether:

- thread is online (QSBR),
- thread is nested within read-side critical section (other flavors),

This is useful for libraries that need to know if QSBR is online in
order to save the original state temporarily so it can be restored
before returning to the caller.

Eventually, this API can be called by a "debugging" implementation of
rcu_dereference() and other urcu-pointer.h API members to check that no
RCU pointer is read outside of RCU read-side critical sections.

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

Add "sparc" host cpu to configure.ac

Some sparc Debian setups advertise a "sparc" host cpu (rather than
sparc64).

In all cases, I think it should be safe to add a "sparc" entry to
userspace RCU configure.ac upstream, e.g.

        [sparc], [ARCHTYPE="sparc64"],

in the event someone would launch the build on an environment not
supporting sparc v9, the build would fail because the 32-bit compiler
would not be able to generate sparc v9 instructions (unless
explicitely instructed to do so by the -m32 -Wa,-Av9a flags).

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

futex: include syscall.h instead of sys/syscall.h

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

Add tab to output in order to allow easy nesting of tables.

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

Remove urcu-api-list.sh from dist tarball

It needs to be run in the git repository.

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

Add urcu-api-list.sh script

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

list: implement cds_list_for_each_safe()

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

Fix: tests/api.h use cpuset.h

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

Fix hurd-i386: move cpuset tests outside of sched_setaffinity conditional

Comment about introduction of cpuset.h within urcu tests:

> Unfortunately it doesn't work, because sched_setaffinity is for now
> just a fail-stub on hurd-i386, and thus configure considers it as
> missing, and thus the CPU_SET test is disabled completely.
>
> I however guess you could just disable defining your own cpu_set_t
> when !HAVE_SCHED_SETAFFINITY, since it is probably used only for using
> sched_setaffinity.

Fix by moving cpu_set_t, CPU_SET and CPU_ZERO tests outside of the
sched_setaffinity conditional.

Reported-by: Samuel Thibault <sthibault@debian.org>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix tests: finer-grained use of CPU_SET, CPU_ZERO and cpu_set_t

Noticed build failure at
https://buildd.debian.org/status/package.php?p=liburcu :

Tail of log for liburcu on hurd-i386:

test_urcu.c:110:0: warning: "CPU_SET" redefined [enabled by default]
In file included from /usr/include/pthread/pthread.h:50:0,
                 from /usr/include/pthread.h:2,
                 from test_urcu.c:26:
/usr/include/sched.h:80:0: note: this is the location of the previous definition
make[3]: *** [test_urcu.o] Error 1
make[2]: *** [all-recursive] Error 1
make[1]: *** [all] Error 2
dh_auto_build: make -j1 returned exit code 2
make: *** [build-arch] Error 2
dpkg-buildpackage: error: debian/rules build-arch gave error exit status 2
make[3]: Entering directory `/build/buildd-liburcu_0.7.6-1-hurd-i386-wGBAtt/liburcu-0.7.6/tests'
  CC     test_urcu.o
make[3]: Leaving directory `/build/buildd-liburcu_0.7.6-1-hurd-i386-wGBAtt/liburcu-0.7.6/tests'
make[2]: Leaving directory `/build/buildd-liburcu_0.7.6-1-hurd-i386-wGBAtt/liburcu-0.7.6'

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

Test for CPU_SET

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

Fix build on architectures with HAVE_SCHED_GETCPU but without HAVE_SYSCONF

Noticed on: https://buildd.debian.org/status/package.php?p=liburcu

Tail of log for liburcu on kfreebsd-amd64:

  CC     urcu.lo
In file included from urcu.c:450:0:
urcu-call-rcu-impl.h:145:12: error: static declaration of 'sched_getcpu' follows non-static declaration
In file included from /usr/include/sched.h:43:0,
                 from /usr/include/pthread.h:20,
                 from urcu.c:30:
/usr/include/x86_64-kfreebsd-gnu/bits/sched.h:65:12: note: previous declaration of 'sched_getcpu' was here
make[3]: *** [urcu.lo] Error 1
make[3]: Leaving directory `/build/buildd-liburcu_0.7.6-1-kfreebsd-amd64-nnkICd/liburcu-0.7.6'
make[2]: *** [all-recursive] Error 1
make[2]: Leaving directory `/build/buildd-liburcu_0.7.6-1-kfreebsd-amd64-nnkICd/liburcu-0.7.6'
make[1]: *** [all] Error 2
make[1]: Leaving directory `/build/buildd-liburcu_0.7.6-1-kfreebsd-amd64-nnkICd/liburcu-0.7.6'
dh_auto_build: make -j1 returned exit code 2
make: *** [build-arch] Error 2

Tail of log for liburcu on kfreebsd-i386:

  CC     urcu.lo
In file included from urcu.c:450:0:
urcu-call-rcu-impl.h:145:12: error: static declaration of 'sched_getcpu' follows non-static declaration
In file included from /usr/include/sched.h:43:0,
                 from /usr/include/pthread.h:20,
                 from urcu.c:30:
/usr/include/i386-kfreebsd-gnu/bits/sched.h:65:12: note: previous declaration of 'sched_getcpu' was here
make[3]: *** [urcu.lo] Error 1
make[3]: Leaving directory `/build/buildd-liburcu_0.7.6-1-kfreebsd-i386-sWzNKU/liburcu-0.7.6'
make[2]: *** [all-recursive] Error 1
make[2]: Leaving directory `/build/buildd-liburcu_0.7.6-1-kfreebsd-i386-sWzNKU/liburcu-0.7.6'
make[1]: *** [all] Error 2
make[1]: Leaving directory `/build/buildd-liburcu_0.7.6-1-kfreebsd-i386-sWzNKU/liburcu-0.7.6'
dh_auto_build: make -j1 returned exit code 2
make: *** [build-arch] Error 2

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

README: document that Clang 3.0 (based on LLVM 3.0) is supported

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

clang: silence "unused expression result" warning

CMM_STORE_SHARED(x, v) is a macro that really acts like an assignment
expression, e.g.:

  x = v;

but internally also has "mc" barriers (useful for cache-incoherent
architectures).

The issue here is that (x = v) can evaluate to "v", but very often we're
not interested to use the assignment expression result. When we have an
explicit assignment, the compiler won't complain that the result of this
expression is unused, but given that the added barrier requires that we
make this macro evaluate explicitly to a value, clang complains.

Fix this by adding "_v = _v" at the last line of the macro, thus
performing what would appear like an effect-less assignment, but
actually tricks clang into thinking we are evaluating to an assignment
expression, thus suppressing the warning.

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

rculfhash: add assertions on node alignment

I've had a report of someone running into issues with the RCU lock-free
hash table by embedding the struct cds_lfht_node into a packed structure
by mistake, thus not respecting alignment requirements stated in
urcu/rculfhash.h. Assertions on "replace" and "add" operations should
catch this, but I notice that we should add assertions on the
REMOVAL_OWNER_FLAG to cover all possible misalignments.

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

Spelling cleanups within comments and documentation

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

Fix configure checks for Tile

The previous method of checking whether the architecture is TileGx or
not was buggy. urcu/arch/tile.h included urcu/arch/gcc.h, which was not
installed on the system, causing a configure error. I am not sure why it
worked when I tested commit 1000f1f4204e5fbb337f4ea911f1e29f67df79aa,
maybe some previous partial install or something.

The check is now done earlier, during the configure step and should not
cause any trouble.

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

uatomic: style fix

- Functions that don't take arguments should be "void" in C, otherwise
  those functions can take a variable number of arguments.

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

doc/cds-api.txt: expand documentation

Expand explanations, reorder items to have all wait-free descriptions
first, so that the rculfqueue API comes last, since it is less
featureful and is the only API of the queues/stacks to actually rely on
RCU.

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

README: document each API file

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

README: reorganize

Move debug build options, and smp support description, to end of README

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

Add compilation support for the TileGX architecture

This patch adds compilation support for the TileGx architecture. Since
the tests were not ran on other architectures of the Tile family
(Tile64, TIlepro), errors are triggered during compilation if the
architecture is another Tile arch.

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

wfstack: add nonblocking to _LGPL_SOURCE API

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

Discourage use of pthread_atfork() for call_rcu handlers

Discourage use of glibc pthread_atfork() for call_rcu handlers due to
its inappropriate assumptions about single-threadedness while pthread
atfork handlers are executing. This results in hangs within the glibc
memory allocator.

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

Fix call_rcu fork handling

Fix call_rcu fork handling by putting all call_rcu threads in a
quiescent state before fork (paused state), and unpausing them when the
parent returns from fork.

On the child, everything will run fine as long as we don't issue fork()
from a call_rcu callback.

Side-note: pthread_atfork is not appropriate when using with multithread
and malloc/free. The glibc malloc implementation sadly expects that all
malloc/free are executed from the context of a single thread while
pthread atfork handlers are running, which leads to interesting hang in
glibc.

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

test: fork handling

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

rculfhash: add cds_lfht_replace to the write operations in the comments

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

urcu: fix comments for cds_list_for_each_prev()

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

documentation: fix rcu-api.txt duplicates

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

test wfcq: remove unneeded urcu.h include

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

test wfs: remove unneeded urcu.h include

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

urcu: declare test_urcu_multiflavor functions

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

urcu: remove the wrong comma

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

wfstack: implement nonblocking pop and next

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

wfcqueue: document first/next return values

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

wfstack: update comments about cds_wfs_empty/first being wait-free

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

wfstack API: rename cds_wfs_first_blocking to cds_wfs_first

cds_wfs_first never needs to block. This operation can be used to check
if the stack returned by pop_all is empty or not, so it is quite
interesting to have a fully non-blocking semantic for all of
enqueue/pop_all/first operations. Only cds_wfs_next may block.

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

wfstack test: test if number of push to empty vs pop_all match

Do same as wfcqueue: we can test if number of push to empty stack match
the number of pop_all that return non-empty stack.

Can be tested with:
./test_urcu_wfs 5 5 10 -w

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

wfstack: document first/next return values

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

test wfstack: enforce external mutex if needed by default

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

test wfcqueue: enforce external mutex if needed by default

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

urcu-mb/signal/membarrier: batch concurrent synchronize_rcu()

Here are benchmarks on batching of synchronize_rcu(), and it leads to
very interesting scalability improvement and speedups, e.g., on a
24-core AMD, with a write-heavy scenario (4 readers threads, 20 updater
threads, each updater using synchronize_rcu()):

* Serialized grace periods:
./test_urcu 4 20 20
SUMMARY ./test_urcu               testdur   20 nr_readers   4
rdur       0 wdur      0 nr_writers  20 wdelay      0
nr_reads    714598368 nr_writes      5032889 nr_ops    719631257

* Batched grace periods:

./test_urcu 4 20 20
SUMMARY ./test_urcu               testdur   20 nr_readers   4
rdur       0 wdur      0 nr_writers  20 wdelay      0
nr_reads    611848168 nr_writes      9877965 nr_ops    621726133

For a 9877965/5032889 = 1.96 speedup for 20 updaters.

Of course, we can see that readers have slowed down, probably due to
increased update traffic, given there is no change to the read-side code
whatsoever.

Now let's see the penality of managing the stack for single-updater.
With 4 readers, single updater:

* Serialized grace periods :

./test_urcu 4 1 20
SUMMARY ./test_urcu               testdur   20 nr_readers   4
rdur       0 wdur      0 nr_writers   1 wdelay      0
nr_reads    241959144 nr_writes     11146189 nr_ops    253105333
SUMMARY ./test_urcu               testdur   20 nr_readers   4
rdur       0 wdur      0 nr_writers   1 wdelay      0
nr_reads    257131080 nr_writes     12310537 nr_ops    269441617
SUMMARY ./test_urcu               testdur   20 nr_readers   4
rdur       0 wdur      0 nr_writers   1 wdelay      0
nr_reads    259973359 nr_writes     12203025 nr_ops    272176384

* Batched grace periods :

SUMMARY ./test_urcu               testdur   20 nr_readers   4
rdur       0 wdur      0 nr_writers   1 wdelay      0
nr_reads    298926555 nr_writes     14018748 nr_ops    312945303
SUMMARY ./test_urcu               testdur   20 nr_readers   4
rdur       0 wdur      0 nr_writers   1 wdelay      0
nr_reads    272411290 nr_writes     12832166 nr_ops    285243456
SUMMARY ./test_urcu               testdur   20 nr_readers   4
rdur       0 wdur      0 nr_writers   1 wdelay      0
nr_reads    267511858 nr_writes     12822026 nr_ops    280333884

Serialized vs batched seems to similar, batched possibly even slightly
faster, but this is probably caused by NUMA affinity.

More benchmark results:

* Serialized synchronize_rcu() -- test_urcu (mb)

./test_urcu 4 1 20
SUMMARY ./test_urcu               testdur   20 nr_readers   4 rdur      0 wdur      0 nr_writers   1 wdelay      0 nr_reads    222512859 nr_writes     10723654 nr_ops    233236513
./test_urcu 4 20 20
SUMMARY ./test_urcu               testdur   20 nr_readers   4 rdur      0 wdur      0 nr_writers  20 wdelay      0 nr_reads    722096653 nr_writes      5012429 nr_ops    727109082
./test_urcu 12 12 20
SUMMARY ./test_urcu               testdur   20 nr_readers  12 rdur      0 wdur      0 nr_writers  12 wdelay      0 nr_reads   1822868768 nr_writes      2300787 nr_ops   1825169555
./test_urcu 16 8 20
SUMMARY ./test_urcu               testdur   20 nr_readers  16 rdur      0 wdur      0 nr_writers   8 wdelay      0 nr_reads   2355908375 nr_writes      1604850 nr_ops   2357513225
./test_urcu 20 4 20
SUMMARY ./test_urcu               testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   4 wdelay      0 nr_reads   3003457459 nr_writes      1074828 nr_ops   3004532287
./test_urcu 20 3 20
SUMMARY ./test_urcu               testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   3 wdelay      0 nr_reads   2956972543 nr_writes      1036556 nr_ops   2958009099
./test_urcu 20 2 20
SUMMARY ./test_urcu               testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   2 wdelay      0 nr_reads   2890178860 nr_writes      1030095 nr_ops   2891208955
./test_urcu 20 1 20
SUMMARY ./test_urcu               testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   1 wdelay      0 nr_reads   3017482290 nr_writes       783420 nr_ops   3018265710

* Batched synchronize_rcu() -- test_urcu (mb)

./test_urcu 4 1 20
SUMMARY ./test_urcu               testdur   20 nr_readers   4 rdur      0 wdur      0 nr_writers   1 wdelay      0 nr_reads    271476751 nr_writes     12858885 nr_ops    284335636
./test_urcu 4 20 20
SUMMARY ./test_urcu               testdur   20 nr_readers   4 rdur      0 wdur      0 nr_writers  20 wdelay      0 nr_reads    608488583 nr_writes     10080610 nr_ops    618569193
./test_urcu 12 12 20
SUMMARY ./test_urcu               testdur   20 nr_readers  12 rdur      0 wdur      0 nr_writers  12 wdelay      0 nr_reads   1260044362 nr_writes      7957711 nr_ops   1268002073
./test_urcu 16 8 20
SUMMARY ./test_urcu               testdur   20 nr_readers  16 rdur      0 wdur      0 nr_writers   8 wdelay      0 nr_reads   2048890674 nr_writes      5440985 nr_ops   2054331659
./test_urcu 20 4 20
SUMMARY ./test_urcu               testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   4 wdelay      0 nr_reads   2819267217 nr_writes      3093008 nr_ops   2822360225
./test_urcu 20 3 20
SUMMARY ./test_urcu               testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   3 wdelay      0 nr_reads   3067795320 nr_writes      2817760 nr_ops   3070613080
./test_urcu 20 2 20
SUMMARY ./test_urcu               testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   2 wdelay      0 nr_reads   3116770603 nr_writes      2404242 nr_ops   3119174845
./test_urcu 20 1 20
SUMMARY ./test_urcu               testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   1 wdelay      0 nr_reads   2238534130 nr_writes      3737588 nr_ops   2242271718

* Serialized synchronize_rcu() -- test_urcu_signal

./test_urcu_signal 4 1 20
SUMMARY ./test_urcu_signal        testdur   20 nr_readers   4 rdur      0 wdur      0 nr_writers   1 wdelay      0 nr_reads  16063309841 nr_writes         9217 nr_ops  16063319058
./test_urcu_signal 4 20 20
SUMMARY ./test_urcu_signal        testdur   20 nr_readers   4 rdur      0 wdur      0 nr_writers  20 wdelay      0 nr_reads  16065183739 nr_writes         9182 nr_ops  16065192921
./test_urcu_signal 12 12 20
SUMMARY ./test_urcu_signal        testdur   20 nr_readers  12 rdur      0 wdur      0 nr_writers  12 wdelay      0 nr_reads  48028512672 nr_writes         8890 nr_ops  48028521562
./test_urcu_signal 16 8 20
SUMMARY ./test_urcu_signal        testdur   20 nr_readers  16 rdur      0 wdur      0 nr_writers   8 wdelay      0 nr_reads  64001589198 nr_writes         8756 nr_ops  64001597954
./test_urcu_signal 20 4 20
SUMMARY ./test_urcu_signal        testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   4 wdelay      0 nr_reads  79907434070 nr_writes         9068 nr_ops  79907443138
./test_urcu_signal 20 3 20
SUMMARY ./test_urcu_signal        testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   3 wdelay      0 nr_reads  79987250839 nr_writes         8589 nr_ops  79987259428
./test_urcu_signal 20 2 20
SUMMARY ./test_urcu_signal        testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   2 wdelay      0 nr_reads  79749947176 nr_writes         8596 nr_ops  79749955772
./test_urcu_signal 20 1 20
SUMMARY ./test_urcu_signal        testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   1 wdelay      0 nr_reads  79751023090 nr_writes         8624 nr_ops  79751031714

* Batched synchronize_rcu() -- test_urcu_signal

./test_urcu_signal 4 1 20
SUMMARY ./test_urcu_signal        testdur   20 nr_readers   4 rdur      0 wdur      0 nr_writers   1 wdelay      0 nr_reads  15739087241 nr_writes         9218 nr_ops  15739096459
./test_urcu_signal 4 20 20
SUMMARY ./test_urcu_signal        testdur   20 nr_readers   4 rdur      0 wdur      0 nr_writers  20 wdelay      0 nr_reads  15662135806 nr_writes        94833 nr_ops  15662230639
./test_urcu_signal 12 12 20
SUMMARY ./test_urcu_signal        testdur   20 nr_readers  12 rdur      0 wdur      0 nr_writers  12 wdelay      0 nr_reads  46634363289 nr_writes        56903 nr_ops  46634420192
./test_urcu_signal 16 8 20
SUMMARY ./test_urcu_signal        testdur   20 nr_readers  16 rdur      0 wdur      0 nr_writers   8 wdelay      0 nr_reads  62263951759 nr_writes        39058 nr_ops  62263990817
./test_urcu_signal 20 4 20
SUMMARY ./test_urcu_signal        testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   4 wdelay      0 nr_reads  77799768623 nr_writes        21065 nr_ops  77799789688
./test_urcu_signal 20 3 20
SUMMARY ./test_urcu_signal        testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   3 wdelay      0 nr_reads  76408008440 nr_writes        17026 nr_ops  76408025466
./test_urcu_signal 20 2 20
SUMMARY ./test_urcu_signal        testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   2 wdelay      0 nr_reads  77868927424 nr_writes        12630 nr_ops  77868940054
./test_urcu_signal 20 1 20
SUMMARY ./test_urcu_signal        testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   1 wdelay      0 nr_reads  77293186844 nr_writes         8680 nr_ops  77293195524

CC: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
CC: Lai Jiangshan <laijs@cn.fujitsu.com>
CC: Alan Stern <stern@rowland.harvard.edu>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

urcu-wait: move queue management code into urcu-wait.h

Note: urcu-wait.h is not yet exposed outside of userspace RCU.

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

urcu-wait: move wait code into separate file

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

urcu-qsbr: batch concurrent synchronize_rcu()

Here are benchmarks on batching of synchronize_rcu(), and it leads to
very interesting scalability improvement and speedups, e.g., on a
24-core AMD, with a write-heavy scenario (4 readers threads, 20 updater
threads, each updater using synchronize_rcu()):

* Serialized grace periods :

./test_urcu_qsbr 4 20 20
SUMMARY ./test_urcu_qsbr          testdur   20 nr_readers   4
rdur      0 wdur      0 nr_writers  20 wdelay      0
nr_reads  20251412728 nr_writes      1826331 nr_ops  20253239059

* Batched grace periods :

./test_urcu_qsbr 4 20 20
SUMMARY ./test_urcu_qsbr          testdur   20 nr_readers   4
rdur      0 wdur      0 nr_writers  20 wdelay      0
nr_reads  15141994746 nr_writes      9382515 nr_ops  15151377261

For a 9382515/1826331 = 5.13 speedup for 20 updaters.

Of course, we can see that readers have slowed down, probably due to
increased update traffic, given there is no change to the read-side code
whatsoever.

Now let's see the penality of managing the stack for single-updater.
With 4 readers, single updater:

* Serialized grace periods :

./test_urcu_qsbr 4 1 20
SUMMARY ./test_urcu_qsbr          testdur   20 nr_readers   4
rdur      0 wdur      0 nr_writers   1 wdelay      0
nr_reads  19240784755 nr_writes      2130839 nr_ops  19242915594

* Batched grace periods :

./test_urcu_qsbr 4 1 20
SUMMARY ./test_urcu_qsbr          testdur   20 nr_readers   4
rdur      0 wdur      0 nr_writers   1 wdelay      0
nr_reads  19160162768 nr_writes      2253068 nr_ops  1916241583

2253068 vs 2137036 -> a couple of runs show that this difference lost in
the noise for single updater.

More benchmark results:

* Serialized synchronize_rcu() -- test_urcu_qsbr

./test_urcu_qsbr 4 1 20
SUMMARY ./test_urcu_qsbr          testdur   20 nr_readers   4 rdur      0 wdur      0 nr_writers   1 wdelay      0 nr_reads  18841016559 nr_writes      1857130 nr_ops  18842873689
./test_urcu_qsbr 4 20 20
SUMMARY ./test_urcu_qsbr          testdur   20 nr_readers   4 rdur      0 wdur      0 nr_writers  20 wdelay      0 nr_reads  20272811733 nr_writes      1837027 nr_ops  20274648760
./test_urcu_qsbr 12 12 20
SUMMARY ./test_urcu_qsbr          testdur   20 nr_readers  12 rdur      0 wdur      0 nr_writers  12 wdelay      0 nr_reads  60343516643 nr_writes      2353685 nr_ops  60345870328
./test_urcu_qsbr 16 8 20
SUMMARY ./test_urcu_qsbr          testdur   20 nr_readers  16 rdur      0 wdur      0 nr_writers   8 wdelay      0 nr_reads  78202711840 nr_writes      2326331 nr_ops  78205038171
./test_urcu_qsbr 20 4 20
SUMMARY ./test_urcu_qsbr          testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   4 wdelay      0 nr_reads  94553396003 nr_writes      2238396 nr_ops  94555634399
./test_urcu_qsbr 20 3 20
SUMMARY ./test_urcu_qsbr          testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   3 wdelay      0 nr_reads  95004708661 nr_writes      2165966 nr_ops  95006874627
./test_urcu_qsbr 20 2 20
SUMMARY ./test_urcu_qsbr          testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   2 wdelay      0 nr_reads  95386506198 nr_writes      2194352 nr_ops  95388700550
./test_urcu_qsbr 20 1 20
SUMMARY ./test_urcu_qsbr          testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   1 wdelay      0 nr_reads  84705972017 nr_writes      2609595 nr_ops  84708581612

* Batched synchronize_rcu() -- test_urcu_qsbr

./test_urcu_qsbr 4 1 20
SUMMARY ./test_urcu_qsbr          testdur   20 nr_readers   4 rdur      0 wdur      0 nr_writers   1 wdelay      0 nr_reads  19154850714 nr_writes      2238834 nr_ops  19157089548
./test_urcu_qsbr 4 20 20
SUMMARY ./test_urcu_qsbr          testdur   20 nr_readers   4 rdur      0 wdur      0 nr_writers  20 wdelay      0 nr_reads  15114131760 nr_writes      9370255 nr_ops  15123502015
./test_urcu_qsbr 12 12 20
SUMMARY ./test_urcu_qsbr          testdur   20 nr_readers  12 rdur      0 wdur      0 nr_writers  12 wdelay      0 nr_reads  45541854970 nr_writes      5786496 nr_ops  45547641466
./test_urcu_qsbr 16 8 20
SUMMARY ./test_urcu_qsbr          testdur   20 nr_readers  16 rdur      0 wdur      0 nr_writers   8 wdelay      0 nr_reads  66217337547 nr_writes      4257427 nr_ops  66221594974
./test_urcu_qsbr 20 4 20
SUMMARY ./test_urcu_qsbr          testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   4 wdelay      0 nr_reads  95048642908 nr_writes      2416266 nr_ops  95051059174
./test_urcu_qsbr 20 3 20
SUMMARY ./test_urcu_qsbr          testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   3 wdelay      0 nr_reads  96679609928 nr_writes      2211168 nr_ops  96681821096
./test_urcu_qsbr 20 2 20
SUMMARY ./test_urcu_qsbr          testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   2 wdelay      0 nr_reads  92166219811 nr_writes      1968725 nr_ops  92168188536
./test_urcu_qsbr 20 1 20
SUMMARY ./test_urcu_qsbr          testdur   20 nr_readers  20 rdur      0 wdur      0 nr_writers   1 wdelay      0 nr_reads  87986181951 nr_writes      3278737 nr_ops  87989460688

CC: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
CC: Lai Jiangshan <laijs@cn.fujitsu.com>
CC: Alan Stern <stern@rowland.harvard.edu>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

tests: use standard malloc/free for synchronize_rcu()

Allows removing mutex from tests, which allow testing scalability of
concurrent synchronize_rcu() executions.

CC: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
CC: Lai Jiangshan <laijs@cn.fujitsu.com>
CC: Alan Stern <stern@rowland.harvard.edu>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

urcu-bp: move quiescent threads to separate list

Accelerate 2-phase grace period by not having to iterate twice on
threads not within RCU read-side critical section.

CC: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
CC: Lai Jiangshan <laijs@cn.fujitsu.com>
CC: Alan Stern <stern@rowland.harvard.edu>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

urcu-mb/signal/membarrier: move quiescent threads to separate list

Accelerate 2-phase grace period by not having to iterate twice on
threads not nested within a RCU read-side lock.

CC: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
CC: Lai Jiangshan <laijs@cn.fujitsu.com>
CC: Alan Stern <stern@rowland.harvard.edu>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

urcu-qsbr: move offline threads to separate list

Accelerate 2-phase grace period by not having to iterate on offline
threads twice.

CC: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
CC: Lai Jiangshan <laijs@cn.fujitsu.com>
CC: Alan Stern <stern@rowland.harvard.edu>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>