rcuja tests: return errors

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

rcuja: add runja.sh

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

rcuja: cleanup destroy print output

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

rcuja: move debugging info into judy array structure

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

rcuja: use rcu_barrier in destroy

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

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>