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>

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>

Remove whiteline

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

rculfhash: rename dummy to bucket

[ Edit by Mathieu Desnoyers: rebased. ]

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

rculfhash: Move key out of struct lfht_test_node, move key_len to caller

Make struct lfht_test_node only contains basic field.
Let user take the responsibility to handle the <key>(hash_set)
or <key,value>(hash_map) management and calculation.

[ Edit by Mathieu Desnoyers: rebased on top of commit
  0422d92c2d658f6093b8209f75808efd2109a110 ]

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

rculfhash: Remove leftover hash_seed field

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

rculfhash: extract compare_fct and hash_fct from the hash table

Leave the compare_fct and hash_fct to the caller, which can therefore
become the only one which needs to know the layout of struct
cds_lfht_node (except for the _cds_lfht_node part).

This will enable us to remove the cds_lfht_node structure from the hash
table (moving it entirely to the caller), replacing it by
_cds_lfht_node, which is really the only part the hash table needs to
know about.

Use-cases that can benefit from this extra flexibility:

>> Sometimes the caller don't have the key or the keys which are big
>> are saved separated. Example: file server
>> Or key comparation is too slow.
>> Or caller just need approximate lookup.
>> Or caller want to compare keys with different strategies for
>> performance.

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

Version 0.6.6

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

Merge branch 'master' into urcu/ht-shrink

qsbr vs call_rcu : remove exit assertion

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

rculfhash: Move "struct rcu_head head" out of "struct cds_lfht_node"

It is user's responsibility to free it by call_rcu(),
synchronize_rcu() or defer_rcu().

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

rculfhash, test: wrap struct cds_lfht_node

Use struct lfht_test_node for test instead of struct cds_lfht_node.
We can add test related things in struct lfht_test_node in future.

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

rculfhash: Change lazy shrink strategy

We can aggressively grow a ht,
but we should conservatively shrink a ht.

When we try to shrink the ht after a deletion,
but if a growing is required after it, we should
stop this shrink.

But it is more complicated to implement it, so we use more
conservative strategy to shrink a ht to gain simple code:

We stop to (lazy) shrink when we found growing is
in progress.

[ Edit by Mathieu Desnoyers: Add documentation, cleanup. ]

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

rculfhash: merge duplicated code of cds_lfht_resize_lazy_*()

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

rculfhash: Fix ht lazy grow logic.

"size < target_size" in cds_lfht_resize_lazy() which is always true
confuses me.

I think we should grow the ht only when we success to increase
the resize_target.

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

rculfhash: rename likely/unlikely (add caa_ prefix)

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

Merge branch 'master' into urcu/ht-shrink

Fixed conflicts:
tests/test_urcu_qsbr.c
tests/test_urcu_qsbr_gc.c

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

Rename likely/unlikely to caa_likely/caa_unlikely

This fixes namespace conflicts.

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

Add structure descriptions, remove redundant clear_flag()

Reported-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix CAA_BITS_PER_lONG typo

Should instead be CAA_BITS_PER_LONG.

Signed-off-by: Paul E. McKenney <paul.mckenney@linaro.org>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

rculfhash: add min_alloc_size test parameter

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

rculfhash: Fix min_alloc_size bug

When I change MIN_ALLOC_ORDER macro to parameter,
I forgot set min_alloc_order before used it which causes bug.

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

rculfhash: Fix ht allocation bug

Fix a bug introduced by Lai Jiangshan <laijs@cn.fujitsu.com>:
alloc_split_items_count() use a wrong flags.

ht->flags should be inited earlier.

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

rculfhash: add CDS_LFHT_ACCOUNTING flag

[ Edit by Mathieu Desnoyers: fix null pointer in poison_free. ]

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

rculfhash: use DEFAULT_SPLIT_COUNT_MASK for !HAVE_SYSCONF

Now, item accounting is always available.

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

rculfhash: use hash for index if !HAVE_SCHED_GETCPU

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

rculfhash: rename percpu_count to split_count

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

rculfhash: Cast to struct rcu_level * instead of void * (cleanup)

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

rculfhash: directly lookup bucket in the first order table

[ Edit by Mathieu Desnoyers: add a dbg_printf so the start-of-table
  lookup prints the same dbg messages as normal lookups. ]

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

Avoid alloc small memory pieces

Add min_alloc_size (minimum allocation size) for allocation.

Now we can gain better cache locality by specifying larger minimum
allocation size.

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