Move API.txt to doc/rcu-api.txt, install in system doc/

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

rculfhash: document implied memory barriers

We choose to provide full memory barriers before and after successful
hash table update operations. Eventually, new API with weaker semantic
can be added, but let's make the basic API as fool-proof as possible.

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

rculfhash: Ensure future-proof memory barrier semantic consistency

Use cmm_smp_mb__before_uatomic_or() prior to the uatomic_or() in
_rcu_lfht_del() to ensure correct memory barrier semantic when we relax
(in the future) the barrier implementation of some architectures.

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

API cleanup: use "uatomic_*" in cmm_smp_mb__ API

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

uatomic: add memory barrier API for and/or/add/sub/inc/sub

Implement:
cmm_smp_mb__before_and, cmm_smp_mb__after_and
cmm_smp_mb__before_or, cmm_smp_mb__after_or
cmm_smp_mb__before_add, cmm_smp_mb__after_add
cmm_smp_mb__before_sub, cmm_smp_mb__after_sub
cmm_smp_mb__before_inc, cmm_smp_mb__after_inc
cmm_smp_mb__before_dec, cmm_smp_mb__after_dec

For generic and x86.

These currently translate into simple compiler barriers on all
architectures, but the and/or/add/sub/inc/dec uatomics do not provide
memory ordering guarantees (only uatomic_add_return, uatomic_sub_return,
uatomic_xchg, and uatomic_cmpxchg provides full memory barrier
guarantees before and after the atomic operations).

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

rculfhash: add runhash.sh test script

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

rculfhash tests: add missing check

We need to check if test_ht is NULL.

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

rculfhash: fix: race between replace and del operations

Bug introduced by commit db00ccc36e7fb04ce8044fb1be7964acd1de6ae0

Here is the race:

Initially in hash table:  A

T0                                         T1
replace A by B
                                           del A
  read A->next
  -> check REMOVED flag, not set yet.
                                           read A->next
                                           -> check REMOVED flag, not set yet.
  cmpxchg A->next to set REMOVED flag
  -> cmpxchg succeeds
                                           uatomic_or to set REMOVED flag
                                           uatomic_xchg to atomically set the REMOVAL_OWNER flag
                                           -> first to set the flag.
  Replace returns node -> free(A)          Del success -> free(A)

With this race, we have a double-free.

The problem with the replace code is that it does not set the
"REMOVAL_OWNER" flag.

Test case to reproduce the bug:

test_urcu_hash 0 2 20 -A -s -M 1 -N 1 -O 1

(2 threads, doing replace/del, with a hash table that has only a single
key for all values). After just a couple of seconds, either the program
hangs, or, more often, it does:

*** glibc detected ***
/media/truecrypt1/compudj/doc/userspace-rcu/tests/.libs/test_urcu_hash:
malloc(): memory corruption (fast): 0x00007ffff3a29e25 ***

Program received signal SIGSEGV, Segmentation fault.

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

rculfhash: replace unneeded rcu_dereference by CMM_LOAD_SHARED

The difference between the two is that CMM_LOAD_SHARED() does not imply
a read barrier between the read and following uses of the data pointed
to by the pointer read.

All sites that only use the pointer load for its bits (never
dereference) don't need the read barrier implied by rcu_dereference.

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

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>