Merge branch 'master' into urcu/ht-shrink

Conflicts:
urcu-call-rcu.h

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

Enhance API.txt documentation, add to Makefile as EXTRA_DIST

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

rculfhash: do not sample in_progress_destroy in the middle of a level

Caused destroy assert/segfaults.

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

rculfhash: break resize loop on destroy

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

rculfhash: decrement resize cnt on destroy

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

Check for in progress destroy before calling call_rcu thread

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

rculfhash: Test for initiated destroy before performing resize

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

Version 0.6.5

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

call_rcu: Document call_rcu requirements

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

call_rcu: Document call_rcu requirements

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

Merge branch 'master' into urcu/ht-shrink

call_rcu: fix error handling of malloc error

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

Merge branch 'master' into urcu/ht-shrink

urcu call_rcu: Use RCU read-side protection for per-cpu call_rcu data

A concurrent get_cpu_call_rcu_data(), called by get_call_rcu_data(),
could dereference this pointer without holding any mutex. So this
situation would happen if we have a concurrent call_rcu() executing
while we do the create_all_cpu_call_rcu_data().

I think we would need to put a rcu_dereference() around
per_cpu_call_rcu_data read within get_cpu_call_rcu_data() too.
per_cpu_call_rcu_data should be done with rcu_set_pointer.

Also, a rcu read-side critical section would be required around any
usage of per_cpu_call_rcu_data, and the action of tearing down the
per-cpu data would require to wait for a quiescent state. So we would
basically require that the call_rcu users need to be registered as
RCU reader threads.

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

urcu,call_rcu: Cleanup call_rcu_data pointers before use in child

[ Edit by Mathieu Desnoyers: create maxcpus_reset to handle cases where
  maxcpus is 0 and -1, depending on the configuration. ]

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

urcu,call_rcu: avoid create call_rcu_data for child when unneed

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

urcu,defer_rcu: Make defer_rcu encoding more compact for marker

When the function changes (and the function is aligned), and only the
data is the marker, we can get away with using only 2 pointers rather
than 3.

[ Edit by Mathieu Desnoyers: patch cleanup, changelog updates ]

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

urcu_defer: Use cancellation flag instead of pthread_cancel()

- Provides better control over cancellation point location.
- Set the futex to 0 before exiting the defer thread.

This patch combines and enhances patches from Lai Jiangshan:
  urcu,defer_rcu: fix missing respond to a cancellation request
  urcu,defer_rcu: Avoid thread exit unexpected

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

urcu,call_rcu: protects call_rcu_data_list when remove node

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

Merge branch 'master' into urcu/ht-shrink

Create default call rcu data upon per-cpu call-rcu teardown

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

rculfhash test: fix 32-bit hash

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

rculfhash test: Use get first/get next to delete all entries

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

rculfhash: fix get first / get next iterator

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

Fix handling of systems without sysconf nr possible cpu support

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

rculfhash needs local config.h

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

rculfhash: update header documentation

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

rculfhash test: move init node outside of rcu read-side c.s. (unneeded protection)

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

Add cds_lfht_first/cds_lfht_next for hash table iteration

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

rculfhash: rename _next into _next_duplicate

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

rculfhash: document use of caa_container_of()

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

rculfhash: cleanup includes

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

Merge branch 'master' into urcu/ht-shrink

powerpc: use __NO_LWSYNC__ check to use appropriate lwsync/sync opcode

We already used it in uatomic code, move it to arch ppc.

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

Merge branch 'master' into urcu/ht-shrink

cmm: provide lightweight smp_rmb/smp_wmb on PPC

lwsync orders loads in cacheable memory with respect to other loads,
and stores in cacheable memory with respect to other stores.  Use it
to implement smp_rmb/smp_wmb.

The heavy-weight sync is still used for the "full" rmb/wmb operations,
as well as for smp_mb.

[ Edit by Mathieu Desnoyers: rephrased the comments around the memory
  barriers. ]

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

rculfhash: factor out add_replace and replace

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

atomic: provide seq_cst semantics on powerpc

We provide sequential consistency semantic over all architectures for
cmpxchg and add_return family of primitives, but the powerpc
implementation does not match that.

Change the isync after the atomic primitives to sync, and explain the
scheme.

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

rculfhash tests: make node count RCU aware

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

rculfhash: set next to NULL when node is NULL

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

rculfhash: approximation can be negative

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

rculfhash: min size only needed on shrink, take nr cpus into account

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

rculfhash: type the ht count approx as long

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

rculfhash: handle small and negative table size approximation

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

rculfhash: fix node approx counting

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

rculfhash: output approximation of number of nodes in counting

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

rculfhash cleanup: count percpu deletes in the positive range

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

rculfhash: node alignment is back to 4 bytes

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

rculfhash: remove now unneeded gc flag (combine with removed)

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

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>

avoid leaking crdp for failed path

[ Comment: now that set_cpu_call_rcu_data() is not racy and detects
  overwrites, we can effectively trust its return value and free the
  crdp if already set. ]

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

Return -EEXIST when the old cpu call_rcu_data has not been removed

To make it matches the comments.

It is the caller's responsibility to use
set_cpu_call_rcu_data(cpu, NULL) to remove the CPU's
call_rcu_data structure and dispose it.

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

protect writing to per_cpu_call_rcu_data[*]

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

wake up default call_rcu thread after we move the leftover callbacks

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

avoid memory leak in call_rcu_data_free()

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

urcu call_rcu: fix use after free()

call_rcu_after_fork_child() needs to use cds_list_for_each_entry_safe to
safely iterate on the list as its item is being freed.

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

use get_cpu_call_rcu_data() for get_call_rcu_data()

[ Impact: refactor duplicated code ]

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

init maxcpus before use

[ Edit:
  Covers the per-cpu call_rcu data setup (not all_cpus helper, which is
  why we did not trigger it in our tests. ]

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
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>

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>

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>

urcu-pointer: implement URCU_FORCE_CAST for C++ compatibility of urcu-pointer.h

We need to be careful with those, so we do not break aliasing. Our
use-case is to cast back and forth between the same type and a void *
(or void **) type when we pass pointers to C functions. As we cast back
to the same type when the pointer is returned from the function,
aliasing should still work.

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>