Implement rcu_barrier()

Awaits for all in-flight call_rcu handlers to complete execution before
returning.

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

rcuja: tweak pigeon min child for 32-bit

value 89 was causing 2% fallback node with random population. value 83
triggers only 0.01% fallback nodes.

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

rcuja: tweak pigeon min child for 64-bit

value 101 was causing 2% fallback node with random population. value 95
triggers only 0.01% fallback nodes.

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

rcuja testing: add arbitrary wait

For testing purposes, wait for free to be performed.

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

rcuja fix: perform lookup in attach node

Handles case where the existing location is not yet reserved. Therefore,
a pointer check cannot be used to check if it has been concurrently
populated. A full-blown lookup is therefore required.

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

rcuja: implement add unique

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

rcuja: fixes and add redesign of "add"

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

rcuja test: destroy should be done online

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

rcuja: print info about allocated/freed/fallback nodes

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

rcuja fix: fix 2d distance calculation

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

rcuja fix: update 2d distance calculation

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

rcuja: add same can use same fallback as add next

Still need to figure out why this fallback is reached in add same.

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

rcuja: implement 2d distribution

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

rcuja 1d distribution: cleanup

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

rcuja: implement 1 dimension pool distribution

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

Fix rcuja: fallback when adding element to full pool

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

rcuja test: fix -k option

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

rcuja: Add missing header

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

rcuja test: print mul fact

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

rcuja test: add key multiplication factor

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

test rcuja: add ratio parameter

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

rcuja fix: list prev pointer vs recompaction

We should update the list prev pointer (for the first node) when a
recompaction changes the address of the list head. Currently a
work-around.

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

Fix rcuja: concurrency checks

add/delete need to re-check that RCU lookups are still valid after
taking node locks.

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

rcuja test: use poison_free

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

rcuja test: add missing rcu read unlock

No impact for now, since we use QSBR.

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

rcuja fix: handle add/removal/add concurrency

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

rcuja fix: del wrt concurrency

testing with:
test_urcu_ja 0 3 10 -v -M 1 -N 1 -O 1

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

Fix urcu test: incorrect handling of del/free

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

hlist: remove needless "member" parameter

cds_hlist_for_each_rcu and cds_hlist_first_rcu don't need to "member"
parameter at all.

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

Fix rcuja: chain/unchain locking vs retry

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

Fix rcuja: delete last node

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

rcuja fix: get the right node

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

Fix rcuja: handle concurrent updates

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

rcuja: Add debug output

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

rcuja test: add rcu_ prefix to debug_yield_read

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

rcuja: allow non-power of 2 keys

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

rcuja: add multithread test

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

Fix: rcuja: typo

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

rcuja: test duplicate node/key support

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

rcuja: fix duplicate node/key support

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

hlist: implement non-entry API

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

rcuja: fix delete

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

rcuja: free all leaf nodes at destruction

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

hlist: implement cds_hlist_first_entry_rcu

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

rcuja: implement delete function

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

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>