Reinsert missing test_urcu_*.c files (missing in rename)

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

rculfhash: simplify get_count_order()

[ Edit by Mathieu Desnoyers:

- Updated comments.
- Quick benchmark on Intel(R) Atom(TM) CPU Z520   @ 1.33GHz:

get_count_order_ulong, from 0 to 100000000:

previous:  3.840s
new:       3.187s

- Test comparing bit-exactness for ranges near 0:

/*
 * fls: returns the position of the most significant bit.
 * Returns 0 if no bit is set, else returns the position of the most
 * significant bit (from 1 to 32 on 32-bit, from 1 to 64 on 64-bit).
 */
static inline
unsigned int fls_u32(uint32_t x)
{
int r;

asm("bsrl %1,%0\n\t"
    "jnz 1f\n\t"
    "movl $-1,%0\n\t"
    "1:\n\t"
    : "=r" (r) : "rm" (x));
return r + 1;
}

static inline
unsigned int fls_u64(uint64_t x)
{
long r;

asm("bsrq %1,%0\n\t"
    "jnz 1f\n\t"
    "movq $-1,%0\n\t"
    "1:\n\t"
    : "=r" (r) : "rm" (x));
return r + 1;
}

static __attribute__((unused))
unsigned int fls_u64(uint64_t x)
{
unsigned int r = 64;

if (!x)
return 0;

if (!(x & 0xFFFFFFFF00000000ULL)) {
x <<= 32;
r -= 32;
}
if (!(x & 0xFFFF000000000000ULL)) {
x <<= 16;
r -= 16;
}
if (!(x & 0xFF00000000000000ULL)) {
x <<= 8;
r -= 8;
}
if (!(x & 0xF000000000000000ULL)) {
x <<= 4;
r -= 4;
}
if (!(x & 0xC000000000000000ULL)) {
x <<= 2;
r -= 2;
}
if (!(x & 0x8000000000000000ULL)) {
x <<= 1;
r -= 1;
}
return r;
}

static __attribute__((unused))
unsigned int fls_u32(uint32_t x)
{
unsigned int r = 32;

if (!x)
return 0;
if (!(x & 0xFFFF0000U)) {
x <<= 16;
r -= 16;
}
if (!(x & 0xFF000000U)) {
x <<= 8;
r -= 8;
}
if (!(x & 0xF0000000U)) {
x <<= 4;
r -= 4;
}
if (!(x & 0xC0000000U)) {
x <<= 2;
r -= 2;
}
if (!(x & 0x80000000U)) {
x <<= 1;
r -= 1;
}
return r;
}

unsigned int fls_ulong(unsigned long x)
{
return fls_u32(x);
return fls_u64(x);
}

int get_count_order_u32(uint32_t x)
{
int order;

order = fls_u32(x) - 1;
if (x & (x - 1))
order++;
return order;
}

int get_count_order_ulong(unsigned long x)
{
int order;

order = fls_ulong(x) - 1;
if (x & (x - 1))
order++;
return order;
}

int test_get_count_order_u32(uint32_t x)
{
if (!x)
return -1;
return fls_u32(x - 1);
}

/* find the minimum order that x <= (1UL << order) */
int test_get_count_order_ulong(unsigned long x)
{
if (!x)
return -1;
return fls_ulong(x - 1);
}

int main(int argc, char **argv)
{
unsigned long i;

for (i = 0UL; i < 10000; i++) {
if (get_count_order_ulong(i) != test_get_count_order_ulong(i))
printf("Error for %lu\n", i);
}

for (i = 4294967293UL; i != 0; i++) {
if (get_count_order_ulong(i) != test_get_count_order_ulong(i))
printf("Error for %lu\n", i);
}

return 0;
}

]

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

rculfhash: use dbg_printf() for grow/shrink printout

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

rculfhash: merge thread_id into struct partition_resize_work

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

rculfhash: remove unused rcu_head in partition_resize_work

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

rculfhash test: handle write return value

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

rcuhash test: fix 32-bit type warning

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

Merge branch 'master' into urcu/ht-shrink

urcu-pointer: fix rcu_set_pointer unset return value

The problem only affected non-_LGPL_SOURCE configs.

Reported-by: Stephen Hemminger <shemminger@vyatta.com>
Fix-proposed-by: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

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>