rculfhash: use do {} while (0) for dbg_printf()

found by clang(make CC=clang).

avoid empty statement.
-------------------------
if (condition)
        dbg_printf()  /* forget ";", but compiler say nothing if dbg_printf() is empty */
statement;
-------------------------

also add printf format check.
(we can use gcc extention "__printf(1, 2)" to declare a dummy inline function
to do the check, but I use "printf()" directly here)

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

rculfhash: cleanup typo

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

rculfhash: update API comments

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

rculfhash: update comments in implementation

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

rculfhash tests: add long hash chains tests

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

rculfhash tests: add uniqueness test

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

rculfhash test: print test name

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

rculfhash: stress requirement in documentation

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

rculfhash: fix typo

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

rculfhash tests: use array of callbacks to modularize

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

rculfhash tests: modularize tests

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

rculfhash: document ordering guarantees

What we actually provide are ordering guarantees.

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

rculfhash: document linearizability guarantees

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

rculfhash: update removal comment

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

Add missing files to .gitignore

Fixes #93

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

Fix out-of-tree build

Wildcards in automake seems to require that we prepent $(top_srcdir) to
get out-of-tree build to work.

Other non-wildcards work fine without the $(top_srcdir) prefix, so
leaving as-is.

Fixes #94

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

rculfhash: check malloc NULL pointer

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

Fix uatomic sign cast

Passing an unsigned int to uatomic_sub does not honor sign extend to
long, as we should be allowed by assume.

Fix this by introducing caa_cast_long_keep_sign(), which casts either to
long or unsigned long depending on the signedness of the argument
received. It is used in uatomic_sub before applying the "-" operator,
since this operator needs to operate on the "long" type size (since sign
extension might not be performed if the argument received is unsigned).

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

Remove unused jhash.h file

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

Fix: use known license text, fix incorrect FSF address

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

Fix: add missing sched.h include in rculfhash.c

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

Allow tests to run on architectures without per-cpu call_rcu support

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

Hash table test: FreeBSD compatibility fix

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

tests: define _GNU_SOURCE instead of __USE_GNU

Fixes the following warning:

In file included from urcutorture.c:9:0:
api.h:67:0: warning: "__USE_GNU" redefined [enabled by default]
/usr/include/features.h:304:0: note: this is the location of the previous definition

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

Merge branch 'urcu/ht-shrink'

RCU lock-free hash table: implement cds_lfht_is_node_deleted()

Some thoughts on how to use the RCU lock-free hash table brought me to
figure out that using the lock-free hash table along with a per-node
mutex is a quite interesting way to deal with lookup vs teardown
coherency.

A per-node lock can be used to protect concurrent modifications of an
entry from one another, as well as concurrent read vs modification. In
addition, if we ensure that each reader/updater of the node checks if
the node has been removed right after taking the mutex, and if we
perform the node removal from the hash table with the per-node mutex
held, we can ensure that readers/updaters will never access unlinked
data.

struct mynode {
pthread_mutex_t mutex;
struct cds_lfht node;
}

CPU A (lookup destroy and free)           CPU B (lookup and read/modify)

                                          rcu_read_lock()
                                          mynode = caa_container_of(
                                                cds_lfht_lookup(...), ...);
                                          mutex_lock(&mynode->mutex);
                                          if (cds_lfht_is_node_deleted(
&mynode->node))
                                               goto unlock;

                                          read/modify structure....

                                        unlock:
                                          mutex_unlock(&mynode->mutex);
                                          rcu_read_unlock()

rcu_read_lock()
mynode = caa_container_of(
        cds_lfht_lookup(...), ...);

mutex_lock(&mynode->mutex);

cds_lfht_del(ht, &mynode->node);

- perform extra teardown operations
  with side-effects, for which call_rcu
  delay is not appropriate

mutex_unlock(&mynode->mutex);
rcu_read_unlock()
call_rcu(free, mynode);

To perform this efficiently, we need an API function to return whether
the node previously looked-up has been deleted since then.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Acked-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
CC: Lai Jiangshan <laijs@cn.fujitsu.com>
CC: Stephen Hemminger <shemminger@vyatta.com>

Define _GNU_SOURCE to access CPU_ZERO() macro in uClibc

Signed-off-by: Thomas Petazzoni <thomas.petazzoni@free-electrons.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Install ChangeLog and README into system's doc

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

Fix AC_LANG_SOURCE usage: only takes one parameter

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

Merge branch 'master' into urcu/ht-shrink

Fix autoconf futex check

The check was always returning true.

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

configure.ac: Use AC_LANG_SOURCE for if else macros

Ref. http://www.flameeyes.eu/autotools-mythbuster/forwardporting/autoconf.html
"Noteworthy changes in autoconf version 2.66 through 2.68"

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

Refresh autoconf files

Use portable shell macros wherever possible.
All functionality should remain the same.

Signed-off-by: Alexandre Montplaisir <alexandre.montplaisir@gmail.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Update gitignore

Signed-off-by: Alexandre Montplaisir <alexandre.montplaisir@gmail.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Merge branch 'master' into urcu/ht-shrink

rculfhash: add comment about hash seed randomness within test program

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

readme: state correct GCC dependency for ARM

If you are trying to compile liburcu for ARM and get errors like:

/usr/local/include/urcu/uatomic/generic.h:180: undefined reference to
`__sync_add_and_fetch_4'
usr/local/lib/liburcu-common.so: undefined reference to
`__sync_lock_test_and_set_4'
/usr/local/lib/liburcu.so: undefined reference to
`__sync_or_and_fetch_4'

please upgrade your GCC to 4.4.

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

rculfhash: remove an invocation of bit_reverse_ulong() when adding

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

rculfhash: remove unneeded conversion

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

rculfhash: remove unneeded clear_flag()

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

cds_lfht_replace: add checks for old/new node hash/value match

Also initialize reverse hash in replace.

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

rculfhash: use node instead of iter argument for deletion

Using a node instead of an iterator as argument for deletion allows
passing a node pointer (that would have been looked up from another data
structure, thus not using the iterator) as argument for deletion.

Deletion still returns -ENOENT if asked to delete the NULL node. This
simplifies the caller usage.

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

rculfhash: number of logically removed nodes should not appear in API

This is an implementation artefact that should not appear in the API. So
only count the non-removed nodes. Print a debug message showing the
number of logically removed nodes instead within the count nodes
function.

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

Document that flags could be represented on 2 bits

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

Add missing REMOVAL_OWNER_FLAG comment to cds_lfht_node comment

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

_cds_lfht_del is not used for buckets anymore, remove parameter

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

rculfhash: Relax atomicity guarantees required by removal operation

The atomicity guarantees for the removal operation do not need to be as
strict as a cmpxchg. Use a uatomic_set followed by a xchg on a newly
introduced "REMOVAL_OWNER_FLAG" to perform removal.

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

remove unneeded "return;"

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

simplify the deletion for bucket node

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

Remove unneeded code

this unneeded code is wrongly introduced by laijs.

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

Cleanup DEFINE_RCU_FLAVOR()

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

Add cds_lfht_ prefix to fls_ulong, get_count_order_ulong, get_count_order_u32

As those are not static anymore (used in plugins).

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

Merge branch 'master' into urcu/ht-shrink

Version 0.6.7

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

Add compat file for test urcu wfs

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

Add missing compat file for wfq test

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

urcu-bp: no need for weak attribute

We should do this within the user (e.g. liblttng-ust), not within the
urcu-bp library.

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

Merge branch 'master' into urcu/ht-shrink

hlist.h: Add missing stddef.h include for NULL

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

Merge branch 'master' into urcu/ht-shrink

Conflicts:
Makefile.am
urcu-bp.c

call_rcu: Add missing call_rcu_before_fork and call_rcu_after_fork_parent declarations

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

rculfhash: Simplify default logic

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

rculfhash: default mm type

In the original patch from Lai Jiangshan <laijs@cn.fujitsu.com>:

When I test backend with the following commands.
(my box is x86_64 with 4 cores/logic cpus)
**(test with Load factor = 100% only)**

./tests/test_urcu_hash 4 0 10 -B mmap -h $((1<<19)) -p $((1<<19))
./tests/test_urcu_hash 4 0 10 -B mmap -h $((1<<18)) -p $((1<<18))
./tests/test_urcu_hash 4 0 10 -B mmap -h $((1<<17)) -p $((1<<17))
./tests/test_urcu_hash 4 0 10 -B mmap -h $((1<<16)) -p $((1<<16))
                    4readers/no writer

It shows that mmap backend is about 6% better over order backend.
(It also shows that chunk backend is (worse than)/(the same as) order
backend for small/large min_nr_alloc_buckets. (use -m when test)).

Note:
"6%" and the google-perftools told us the bucket_at() is not the
critical bottleneck.

new strategy:
* infinite buckets size                  --> order mm
* otherwise if 64bits,
   with number of buckets <= (1 << 32)   --> mmap mm
* otherwise                              --> order mm

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

rculfhash,test: add memory_backend argument

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

rculfhash,test: add max_hash_buckets_size argument

[ Edit by Mathieu Desnoyers: clarify the test program printouts. ]

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

cleanup duplicated code

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

cleanup unneed declare

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

disable warning when -DNDEBUG(disable assert())

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

Describe autotools/libtool/automake version dependency

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

Remove m4_ifdef for AC_PROG_LIBTOOL (deprecated)

This trick does not seem to work anyway.

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

Support older autotools

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

Apply autoupdate to configure.ac

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

Fix build for amd64 environment (for FreeBSD 8.2)

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

Fix cds_lfht field order

* Lai Jiangshan (laijs@cn.fujitsu.com) wrote:
> 3fd3f554f6eb18ae5ec526b82025a53a554f775d are wrong,
>
> 1) dynamic len tbl_chunk must at the end of cds_lfht, (so I put all the mm field at the end of cds_lfht).

My bad, will fix.

>
> 2) lists of hot access fields:
> size
> tbl_order/chunk/mmap
> bucket_at
> flags (testing for counting)
> split_count
> min_alloc_buckets_order (bucket_at() for chunk mm)
> min_nr_alloc_buckets (buket_at() for order mm and chunk mm)

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

rculfhash mm plugins: cleanup alloc

- Ensure the order of fields set match the cds_lfht field order.
- 80 cols cleanup.

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

rculfhash: document fini_table

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

rculfhash: likely -> caa_likely fix

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

rculfhash: cleanup ht_count_add/ht_count_del

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

rculfhash: reorder cds_lfht for smaller cache footprint in fast-paths

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

add rculfhash-mm-mmap.c memory management

[ Edit by Mathieu Desnoyers:
  - change "buckets" for "mmap" to better show the mapping between the
    union member and the mm plugin.
  - 80 col coding style fixups. ]

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

add rculfhash-mm-chunk.c memory management

[ Edit by Mathieu Desnoyers: Update comment above
  struct cds_lfht_node *tbl_chunk. ]

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

move memory management code out as rculfhash-mm-order.c

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

Merge struct rcu_table into struct cds_lfht

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

use rcu_flavor for rculfhash

Make the sizeof(struct cds_lfht) smaller

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

Add rcu_flavor

Not all related functions are added.
Left functions will be added when needed.

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

add max_nr_buckets argument

[ Edit by Mathieu Desnoyers: clarify cds_lfht_new() description. ]

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

rename min_alloc_size/min_alloc_order

[ Mathieu Desnoyers:

  This clarifies that the amount of buckets allocated can differ from
  the number of buckets chained together, especially for small hash
  tables, where we don't free under min_nr_alloc_buckets. ]

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

remove struct rcu_level

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

it is not required that ht->t.size >= ht->min_table_size anymore

Original code always ensure ht->t.size >= ht->min_table_size.
This can be improved: ht->min_table_size should be used for allocation,
not for the bucket size in use.

Why does the original code need to always ensure this ?

  Original code don't do special alloc/free when

    ht->t.size < ht->min_table_size

  in init_table()/fini_table(), so we have to force

    ht->t.size >= ht->min_table_size.

Why does new code become flexible ?

  New code use the wrappers, they handle the special cases.

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

proper wrapper for bucket table alloc and free

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

introduce bucket_at() and improve readability

Fast path is not changed.
It will slow down very little for slow path.

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

Add missing rcu_dereference_sym_bp

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

urcu-bp: allow weak linking

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

Add Lai Jiangshan's copyright to rculfhash

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

Update comments of cds_lfht_new()

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

Install test scripts in the dist tarball

Fix for http://lttng.org/issue/250
Allows running `make check' when installing from the tarball

Signed-off-by: Alexandre Montplaisir <alexandre.montplaisir@gmail.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

rculfhash: constify all key arguments passed to API

The hash table never needs to modify the key, it is only ever used for
"match", so it should always be received as a const argument.

Reported-by: Stephen Hemminger <shemminger@vyatta.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix arguments order

use: hash, match, key

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

rculfhash: Add parenthesis around macro arg use in iterator macro

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

Add hash table iterator macros

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