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>

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>

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>

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>

test api cleanup: remove unused primitives

[ Mathieu: the rationale for this is that we can always add back that
  code if every needed. Removing leftover GPLv2 test code is an
  incentive to create the appropriate library-wide LGPL/MIT-style
  abstractions.]

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

Merge branch 'master' into lfqueue-dev

put thread offline while waiting for the init flag

Otherwise, the call_rcu thread might end up in a synchronize_rcu that
never ends.

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

urcu: move private definitions to .c file

The reader does not and should not know about RCU_QS_ACTIVE_ATTEMPTS
and KICK_READER_LOOPS.  Move the definition to urcu.c.

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

urcu-bp: move private definitions to .c file

The reader does not and should not know about RCU_QS_ACTIVE_ATTEMPTS.
Move the definition to urcu-bp.c.

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

urcu-qsbr: move private definitions to .c file

The reader does not and should not know about RCU_QS_ACTIVE_ATTEMPTS.
Move the definition to urcu-qsbr.c.  Also remove KICK_READER_LOOPS.

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

rcutorture: fix rcutorture-qsbr

rcutorture-qsbr is not marking quiescent states, so it will always
have just one update in the whole test.  Fix it.

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

wfqueue: fix type-incorrect assignment

The "old_tail = q->tail, q->tail = node" assignment in wfqueue
is not type safe; q->tail is a pointer to pointer to node and the
correct value to assign is &node->next.  While the arithmetic is
the same, it is better to be tidy.

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

Fix tests Makefile EXTRA_DIST to use api.h

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

Fix choice of default flavour in urcu/map/urcu.h

Hi, I noticed in the 0.64 release (and git too) that if a flavour is not
specified explicitly then RCU_MB is chosen in urcu/map/urcu.h, while the
docs say and the Makefile expects RCU_MEMBARRIER.  Note that the header
file urcu/static/urcu.h has similar logic but uses RCU_MEMBARRIER for
the default.

Before this patch:

$ nm *.a | grep rcu_init
00000000000003c0 T rcu_init_mb
00000000000003c0 T rcu_init_mb
0000000000000000 T rcu_init_sig

After this patch:

$ nm *.a | grep rcu_init
00000000000003c0 T rcu_init_memb
00000000000003c0 T rcu_init_mb
0000000000000000 T rcu_init_sig

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

api: remove list/hlist

Remove the parts that actually caused compilation to fail.

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

api: remove arch-specific files

No change since they were a subset of api_gcc.h.  api_gcc.h is
renamed to api.h, and configure need not create a symlink anymore.

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

api: make api_gcc.h a superset of the other headers

After this patch the only differences are:

- for_each_tid is now defined in api_x86.h

- HAVE_CPU_SET_T and HAVE_SCHED_SETAFFINITY are now defined in api_ppc.h

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

tests api: remove atomics

The code is #if 0'd already, remove it.

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

put thread offline while waiting for the init flag

Otherwise, the call_rcu thread might end up in a synchronize_rcu that
never ends.

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

urcu: move private definitions to .c file

The reader does not and should not know about RCU_QS_ACTIVE_ATTEMPTS
and KICK_READER_LOOPS.  Move the definition to urcu.c.

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

urcu-bp: move private definitions to .c file

The reader does not and should not know about RCU_QS_ACTIVE_ATTEMPTS.
Move the definition to urcu-bp.c.

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

urcu-qsbr: move private definitions to .c file

The reader does not and should not know about RCU_QS_ACTIVE_ATTEMPTS.
Move the definition to urcu-qsbr.c.  Also remove KICK_READER_LOOPS.

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

rcutorture: fix rcutorture-qsbr

rcutorture-qsbr is not marking quiescent states, so it will always
have just one update in the whole test.  Fix it.

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

wfqueue: fix type-incorrect assignment

The "old_tail = q->tail, q->tail = node" assignment in wfqueue
is not type safe; q->tail is a pointer to pointer to node and the
correct value to assign is &node->next.  While the arithmetic is
the same, it is better to be tidy.

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

Merge branch 'master' into lfqueue-dev

Use caa_ prefix for min() and max()

Defining min/max macros clashes with C++.

Reported-by: Vegard Nossum <vegard.nossum@gmail.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Version 0.6.4, update changelog

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

Merge branch 'master' into lfqueue-dev

Fix ARM uatomic: missing return in uatomic and/or

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

rculfhash: add likely/unlikely annotation

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

rculfhash: document add lock-freedom

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

rculfhash: document node alignment

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

rculfhash: document algorithms

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

rculfhash test: make teardown more verbose and faster

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

rculfhash: print resize length (useful as non-debug for now)

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

rculfhash: tolerate longer chain length

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

rculfhash: diminish index table memory consumption

- introduce log2 rcu table for resize.
- pull the dummy nodes into invariant per-log2-level tables.

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

rculfhash: add missing clear flag in gc

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

rculfhash: document flags

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

rculfhash: merge dummy into next ptr

part 2: rely on the flag for check.

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

rculfhash: merge dummy flag into next pointer

step 1: set flag

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

rculfhash: Add clear flag

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

rculfhash: introduce REMOVED_FLAG and FLAG_MASK

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

rculfhash: shrink size of dummy node

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

rculfhash: wait for call_rcu quiescence before destroy

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

rculfhash: add c++ ifdef

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

rculfhash test: add options

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

rculfhash test: use per-cpu call-rcu threads

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

rculfhash: update add_unique api

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

rculfhash: fix add unique

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

rculfhash test: increases random pool size

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

rculfhash: remove hash from nodes

Shrink node size, can get it quickly by reversing the reverse_hash.

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

rculfhash: change order of node fields for locality

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

rculfhash: merge node gc into add loop

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

rculfhash: cleanup

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

rculfhash test: add nr_leaked count

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