rculfhash: implement lock-free replacement

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

rculfhash: support replacement operation

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

rculfhash: API rename: remove -> del

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

rculfhash: spawn only number of threads required for resize

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

rculfhash: parallelize resize

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

rculfhash: document flags

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

rculfhash: comment file inclusion order

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

rculfhash: simplify lfht_new API with inline wrapper

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

rculfhash: add TODO for resize worker threads

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

rculfhash: Remove leftover assertions

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

rculfhash: merge table hash and link stages into populate

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

Merge branch 'urcu/ht-shrink-help' into urcu/ht-shrink

rculfhash: remove helper scheme

There is a trade-off to consider here:
- The helper scheme would require the helpers to allocate the memory for
  dummy nodes themself for correctness (the current implementation is
  buggy because lookups consider an half-linked dummy node to be ready for
  use), which does not work with a cache-efficient per-level array of
  dummy nodes.
- We want cache-efficiency, so we want to keep the per-level array
  allocation.

Therefore, letting insert/removal/lookups help expand is not the way to
go here. This patch removes the helping scheme.

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

call_rcu implementation: add missing static

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

Document QSBR interaction with mutexes

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

rculfhash test: exit upon failure

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

rculfhash: fix add_unique node counting

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

rculfhash test: cast rand_r return value directly

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

rculfhash test: add verbosity

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

rculfhash test: allow different size for lookup, write, init

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

qsbr vs call_rcu : remove exit assertion

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

rculfhash: validate lookups

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

rculfhash test: add pool offsets

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

rculfhash: with resize stop and helpers, min size can now be 1

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

rculfhash: help scheme: fix end node, insertion, and lookups

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

rculfhash: break in-progress resize when target size change (between levels)

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

rculfhash: break in-progress resize when target size change (between levels)

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

rculfhash: make add/removal help expand

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

rculfhash: comment shrink operation

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

rculfhash: remove verified TODOs

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

rculfhash: put thread offline before taking mutex (fix G.P. deadlock)

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

Merge branch 'master' into urcu/ht-shrink-help

Conflicts:
urcu-qsbr.c

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

rculfhash: use single init-time allocation for order table

This simplifies management of hash table resizes. Thanks to Josh
Triplett for suggesting this.

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

urcu-qsbr: use rcu_thread_offline/rcu_thread_online instead of inlining them

* Mathieu Desnoyers wrote:

> Just to let you know that I pushed two updates into urcu: one fixes a
> grace period hang caused by a missing wakeup in the synchronize_rcu
> QSBR code. This appears to hit us due to the more fine-grained wakeup
> code brought by Paolo. The wakeup was really missing from the
> synchronize_rcu code (so Paolo's code just triggered an existing
> problem). I thought it would be good to let you know the effect: grace
> periods are delayed forever. This problem never appeared in a release
> (I caught it before).

Good catch.  Why not use rcu_thread_offline/online in synchronize_rcu,
instead of touching rcu_reader.ctr directly?  I had this in my QEMU
branch but hadn't posted yet because it was meant as a cleanup only.

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

Pair all_cpu call_rcu create with free

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

rculfhash test: add missing call_rcu per-cpu worker threads teardown

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

rculfhash: disable poison and remove debugging code

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

call_rcu: register work threads as rcu readers

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

QSBR: add missing wakeups in synchronize_rcu code

synchronize_rcu go into offline mode during grace period. It duplicates
the rcu_thread_online/offline code, and therefore adding the required
wake_up_gp() is required there too.

Failure to do so leads to grace period hangs.

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

QSBR: add missing wakeups in synchronize_rcu code

synchronize_rcu go into offline mode during grace period. It duplicates
the rcu_thread_online/offline code, and therefore adding the required
wake_up_gp() is required there too.

Failure to do so leads to grace period hangs.

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

rculfhash: hold rcu read-side lock in resize

We need to hold the RCU read-side lock in resize to protect against ABA
caused by re-use of nodes after going through the memory allocator
through a call_rcu performed on another CPU.

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

call_rcu: register work threads as rcu readers

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

rculfhash: add list iteration tracer in gc

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

rculfhash: poison memory before free (for testing)

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

rculfhash: reinstate i - 1 for shrink

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

rculfhash: add assertion in path compression

Detects incorrect usage of path compression.

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

rculfhash: fix fini_table for size 1

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

rculfhash: Fix off-by-one in fini_table

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

rculfhash: add asserts and comments

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

cmm: do not generate code for smp_rmb/smp_wmb on x86_64

We can assume, on x86, that no accesses to write-combining memory occur,
and also that there are no non-temporal load/stores (people would
presumably write those with assembly or intrinsics and put appropriate
lfence/sfence manually). In this case rmb and wmb are no-ops on x86.
according to the updated x86 memory models:

INTEL CORPORATION. Intel 64 Architecture Memory Ordering White Paper,
2007.
http://developer.intel.com/products/processor/manuals/318147.pdf

ADVANCED MICRO DEVICES. AMD x86-64 Architecture Programmer’s Manual
Volume 2: System Programming, 2007.

Paul E. McKenney. Memory Ordering in Modern Microprocessors
www.rdrop.com/users/paulmck/scalability/paper/ordering.2007.09.19a.pdf

x86 does not reorder loads vs loads, and stores vs stores when using
normal memory accesses, with the notable exceptions of Pentium Pro
(reorders reads) and WinChip (reorders writes). Therefore, it is safe
not to emit fence instructions for x86_64 cmm_smp_rmb()/cmm_smp_wmb(),
but we leave the memory fences in place for x86_32 for those two
special-cases.

Define cmm_smp_rmb and cmm_smp_wmb to be the "common" operations that
do not require fence instruction, while leaving cmm_rmb and cmm_wmb in
place for more sophisticated uses.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

cmm: let per-arch files provide cmm_smp_* barriers

x86 instructions lfence and sfence are rarely needed, thus we want
the cmm_smp_rmb/cmm_smp_wmb macros to be simple compiler barriers.
So, let the per-arch files override the default definitions in
arch/generic.h.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

rculfhash test: -A option for auto resize

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

rculfhash: Make auto resize selectable with flag

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

Optimize caa_get_cycles() for PowerPC64

Make caa_get_cycles() read from the Time Base register with only 1
instruction.

[ Edit by Mathieu Desnoyers: coding style update ]

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Signed-off-by: Tulio Magno Quites Machado Filho <tuliom@linux.vnet.ibm.com>

rculfhash: update ascii art

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

rculfhash: set minimum table size, add todo about helping resize

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

rculfhash: fix 0 order lookup (special-case)

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

rculfhash: simplify dummy node removal

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

rculfhash: deal with resize to size 1 corner-case

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

rculfhash: allow shrink

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

test rculfhash: add/remove/random support (with SIGUSR1)

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

rculfhash: set size instead of max for per-cpu count scheme

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

rculfhash: tweak resize thresholds

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

rculfhash: tweak per-cpu counter resize with thresholds

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

rcuhash: lazy per-cpu counters, fix resize target update

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

rculfhash: count nodes (per-cpu) as expand criterion

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

lfq/lfs tests: use call_rcu

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

Revert "Add cds_list_empty"

This reverts commit 4b7cab77f3c1c03f021cb0f7e8d150eed3f948e9.

(did duplicate cds_list_empty)

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

Add cds_list_empty

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

list: Add cds_list_first_entry

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

rculfhash test: Check random pool size

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

rculfhash: Add initial hash population

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

rculfhash: benchmark QSBR flavor

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

rculfhash test: print number of add fail (uniquify matches)

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

rculfhash: power power of two check should allow 0

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

rculfhash: implement cds_lfht_next

Useful for walk traversal of all nodes sharing the same key (lookup +
next until NULL is returned).

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

rculfhash: Update API documentation

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

rculfhash: Check that init size is power of 2

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

Use cds_lfht namespace for lock-free hash table

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

RCU hash table API documentation

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

Merge branch 'master' into urcu/ht

Conflicts:
Makefile.am

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

rculfstack/queue: define _LGPL_SOURCE around static header include

... so the urcu-pointer header takes the LGPL version of rcu_dereference
and friends.

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

Revert "Create per RCU flavor CDS libraries"

This reverts commit d4b99c015229978810319cfd42e1c9763772fad8.

Minor change (not visible to end-users): this commit introduces a
liburcu-common.so to hold wfqueue, wfstack and futex fall-back code.
This .so is used by all URCU flavors, as well as liburcu-cds.so.

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

Revert "CDS API: removal of rcu_read lock/unlock dep, removal of call_rcu argument from init"

This reverts commit 7618919ae496bda84a2efa4f2ad0abe569892a9e.

Rationale:

I thought about it some more, and had discussions with various people,
and there are a few reasons to go for a scheme where rcu read lock
should be taken by the caller, and to pass call_rcu as a parameter to
the data structure init function:

A) The advantage, as Paul E. McKenney pointed out, is that one single .so
   is enough to support all RCU flavors. Very convenient for external data
   structure containers.

B) It clearly documents where rcu read-side locks are needed, so the user
   keep control and in-depth understanding of their read-side locks.

C) When multiple API functions that require RCU read-side lock to be
   held (sometimes even the same lock) throughout a sequence of API
   calls, we have no choice but to let the caller hold the read-side
   lock.

D) Due to support of multiple nesting of rcu read-side lock, any
   "improvement" we could get by releasing the read-side lock in
   retry loops would vanish in the cases where we are called within
   nested C.S..

E) If a library uses synchronize_rcu, this should be clearly documented,
   and even frowned upon, because this involves important limitations on
   the design of the caller, and important performance hit. There are
   usually ways to reach the same result through use of call_rcu, which
   should really be used thoroughout these libraries.

F) It clearly documents when a data structure needs to use call_rcu
   internally.

G) Some very early benchmark results show that there is indeed not
   much performance gain to achieve by inlining call_rcu, even if it is
   a version with a cache for the "call_rcu structure" lookup
   (per-cpu/per-thread/global). So passing it as a parameter to
   the data structure init function should be fine, even in cases
   where it is called very often.

H) For use-cases where applications would like to use more than one
   RCU flavor concurrently (which is now supported), leaving management
   of RCU read-side C.S. to the reader allows the application to take
   more than one RCU read-side lock across API calls. It also lets the
   application specify its own call_rcu function that could handle more
   than one RCU flavor.

So for all these reasons, I reverting back to the API we have in our
last release (0.6.4).

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

Add __rcu annotation (unimplemented)

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

Fix incorrect fsf address in header files

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

wfstack: push returns prior stack emptiness state

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

Make lf stack push return if the stack was empty

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

Document caa_container_of

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

urcu-bp: do not call munmap for NULL registry at exit

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

urcu libraries can directly use the _LGPL_SOURCE wfqueue

No need to link dynamically with the data structure object.

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

rculfstack: document "push"

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

Add runall.sh to tarball

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

Fix build order of liburcu-cds-common

Caused make install to fail.

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

CDS API: removal of rcu_read lock/unlock dep, removal of call_rcu argument from init

* API change * for all liburcu-cds* flavors.

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

Fix missing check for SYS_membarrier in map header

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

Create per RCU flavor CDS libraries

Introduce per-flavor concurrent data structure libraries for data
structures depending on RCU:

liburcu-cds: memb flavor (default), matches -lurcu
liburcu-cds-qsbr: qsbr flavor, matches -lurcu-qsbr
liburcu-cds-mb: mb flavor, matches -lurcu-mb
liburcu-cds-signal, matches -lurcu-signal
liburcu-cds-bp, matches -lurcu-bp

liburcu-cds-common: Data structures not depending on RCU for
synchronization.

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

Merge branch 'master' into lfqueue-dev

urcu-qsbr: avoid useless futex wakeups and burning CPU for long grace periods

I noticed that urcu makes exactly _one_ attempt at using futexes
to avoid busy looping on synchronize_rcu.  The attached patch instead
switches from busy waiting to futexes after RCU_QS_ACTIVE_ATTEMPTS.
To limit the amount of system calls, reading threads remember whether
they already had a quiescent state in this grace period; if so they were
already removed from the list, and can avoid signaling the futex.

Performance measured with rcutorture (nreaders: 10, nupdaters: 1,
duration: 10, median of nine runs):

     RCU_QS_ACTIVE_ATTEMPTS == 100, no patch         n_updates = 292
     RCU_QS_ACTIVE_ATTEMPTS == 1, no patch           n_updates = 290
     RCU_QS_ACTIVE_ATTEMPTS == 100, with patch       n_updates = 408
     RCU_QS_ACTIVE_ATTEMPTS == 1, with patch         n_updates = 404

(the first two cases are obviously the same; the only change is
when the futex is used, but over many calls there is no difference).

This patch matches the update to the Promela model.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

api: reimplement BUILD_BUG_ON in compiler.h

Even though it's just two lines of code, I'm reimplementing it
cleanly out of paranoia.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>