urcu.git
12 years agoconfigure.ac: Use AC_LANG_SOURCE for if else macros
Mathieu Desnoyers [Sat, 7 Jan 2012 17:59:41 +0000 (12:59 -0500)] 
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>
12 years agoRefresh autoconf files
Alexandre Montplaisir [Fri, 6 Jan 2012 16:28:35 +0000 (11:28 -0500)] 
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>
12 years agoUpdate gitignore
Alexandre Montplaisir [Fri, 6 Jan 2012 15:36:01 +0000 (10:36 -0500)] 
Update gitignore

Signed-off-by: Alexandre Montplaisir <alexandre.montplaisir@gmail.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoMerge branch 'master' into urcu/ht-shrink
Mathieu Desnoyers [Thu, 29 Dec 2011 14:48:25 +0000 (09:48 -0500)] 
Merge branch 'master' into urcu/ht-shrink

12 years agorculfhash: add comment about hash seed randomness within test program
Mathieu Desnoyers [Thu, 29 Dec 2011 14:46:34 +0000 (09:46 -0500)] 
rculfhash: add comment about hash seed randomness within test program

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoreadme: state correct GCC dependency for ARM
Gerlando Falauto [Wed, 21 Dec 2011 14:50:38 +0000 (09:50 -0500)] 
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>
12 years agorculfhash: remove an invocation of bit_reverse_ulong() when adding
Mathieu Desnoyers [Wed, 21 Dec 2011 14:33:36 +0000 (09:33 -0500)] 
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>
12 years agorculfhash: remove unneeded conversion
Lai Jiangshan [Wed, 21 Dec 2011 14:29:12 +0000 (09:29 -0500)] 
rculfhash: remove unneeded conversion

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: remove unneeded clear_flag()
Lai Jiangshan [Wed, 21 Dec 2011 14:27:47 +0000 (09:27 -0500)] 
rculfhash: remove unneeded clear_flag()

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agocds_lfht_replace: add checks for old/new node hash/value match
Mathieu Desnoyers [Wed, 21 Dec 2011 13:53:48 +0000 (08:53 -0500)] 
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>
12 years agorculfhash: use node instead of iter argument for deletion
Mathieu Desnoyers [Wed, 21 Dec 2011 13:24:25 +0000 (08:24 -0500)] 
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>
12 years agorculfhash: number of logically removed nodes should not appear in API
Mathieu Desnoyers [Wed, 21 Dec 2011 13:16:41 +0000 (08:16 -0500)] 
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>
12 years agoDocument that flags could be represented on 2 bits
Mathieu Desnoyers [Tue, 20 Dec 2011 16:14:01 +0000 (11:14 -0500)] 
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>
12 years agoAdd missing REMOVAL_OWNER_FLAG comment to cds_lfht_node comment
Mathieu Desnoyers [Tue, 20 Dec 2011 16:01:16 +0000 (11:01 -0500)] 
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>
12 years ago_cds_lfht_del is not used for buckets anymore, remove parameter
Mathieu Desnoyers [Tue, 20 Dec 2011 15:44:25 +0000 (10:44 -0500)] 
_cds_lfht_del is not used for buckets anymore, remove parameter

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: Relax atomicity guarantees required by removal operation
Mathieu Desnoyers [Mon, 19 Dec 2011 21:45:51 +0000 (16:45 -0500)] 
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>
12 years agoremove unneeded "return;"
Lai Jiangshan [Tue, 20 Dec 2011 15:34:18 +0000 (10:34 -0500)] 
remove unneeded "return;"

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agosimplify the deletion for bucket node
Lai Jiangshan [Tue, 20 Dec 2011 15:32:48 +0000 (10:32 -0500)] 
simplify the deletion for bucket node

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoRemove unneeded code
Lai Jiangshan [Tue, 20 Dec 2011 15:26:29 +0000 (10:26 -0500)] 
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>
12 years agoCleanup DEFINE_RCU_FLAVOR()
Mathieu Desnoyers [Mon, 19 Dec 2011 19:26:53 +0000 (14:26 -0500)] 
Cleanup DEFINE_RCU_FLAVOR()

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoAdd cds_lfht_ prefix to fls_ulong, get_count_order_ulong, get_count_order_u32
Mathieu Desnoyers [Fri, 16 Dec 2011 21:41:30 +0000 (16:41 -0500)] 
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>
12 years agoMerge branch 'master' into urcu/ht-shrink
Mathieu Desnoyers [Wed, 14 Dec 2011 20:41:18 +0000 (15:41 -0500)] 
Merge branch 'master' into urcu/ht-shrink

12 years agoVersion 0.6.7 v0.6.7
Mathieu Desnoyers [Tue, 13 Dec 2011 02:35:45 +0000 (21:35 -0500)] 
Version 0.6.7

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoAdd compat file for test urcu wfs
Mathieu Desnoyers [Thu, 8 Dec 2011 21:16:46 +0000 (16:16 -0500)] 
Add compat file for test urcu wfs

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoAdd missing compat file for wfq test
Mathieu Desnoyers [Thu, 8 Dec 2011 21:14:21 +0000 (16:14 -0500)] 
Add missing compat file for wfq test

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agourcu-bp: no need for weak attribute
Mathieu Desnoyers [Thu, 8 Dec 2011 13:28:01 +0000 (08:28 -0500)] 
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>
12 years agoMerge branch 'master' into urcu/ht-shrink
Mathieu Desnoyers [Mon, 5 Dec 2011 23:41:49 +0000 (18:41 -0500)] 
Merge branch 'master' into urcu/ht-shrink

12 years agohlist.h: Add missing stddef.h include for NULL
Mathieu Desnoyers [Mon, 5 Dec 2011 23:41:29 +0000 (18:41 -0500)] 
hlist.h: Add missing stddef.h include for NULL

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoMerge branch 'master' into urcu/ht-shrink
Mathieu Desnoyers [Mon, 5 Dec 2011 23:37:50 +0000 (18:37 -0500)] 
Merge branch 'master' into urcu/ht-shrink

Conflicts:
Makefile.am
urcu-bp.c

12 years agocall_rcu: Add missing call_rcu_before_fork and call_rcu_after_fork_parent declarations
Mathieu Desnoyers [Mon, 5 Dec 2011 20:49:57 +0000 (15:49 -0500)] 
call_rcu: Add missing call_rcu_before_fork and call_rcu_after_fork_parent declarations

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: Simplify default logic
Mathieu Desnoyers [Sun, 4 Dec 2011 16:51:09 +0000 (11:51 -0500)] 
rculfhash: Simplify default logic

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: default mm type
Mathieu Desnoyers [Sun, 4 Dec 2011 15:40:01 +0000 (10:40 -0500)] 
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>
12 years agorculfhash,test: add memory_backend argument
Lai Jiangshan [Fri, 2 Dec 2011 13:16:30 +0000 (08:16 -0500)] 
rculfhash,test: add memory_backend argument

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash,test: add max_hash_buckets_size argument
Lai Jiangshan [Fri, 2 Dec 2011 13:14:08 +0000 (08:14 -0500)] 
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>
12 years agocleanup duplicated code
Lai Jiangshan [Fri, 2 Dec 2011 13:08:14 +0000 (08:08 -0500)] 
cleanup duplicated code

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agocleanup unneed declare
Lai Jiangshan [Fri, 2 Dec 2011 13:06:02 +0000 (08:06 -0500)] 
cleanup unneed declare

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agodisable warning when -DNDEBUG(disable assert())
Lai Jiangshan [Fri, 2 Dec 2011 13:05:08 +0000 (08:05 -0500)] 
disable warning when -DNDEBUG(disable assert())

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoDescribe autotools/libtool/automake version dependency
Mathieu Desnoyers [Thu, 1 Dec 2011 15:40:31 +0000 (10:40 -0500)] 
Describe autotools/libtool/automake version dependency

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoRemove m4_ifdef for AC_PROG_LIBTOOL (deprecated)
Mathieu Desnoyers [Thu, 1 Dec 2011 15:18:12 +0000 (10:18 -0500)] 
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>
12 years agoSupport older autotools
Mathieu Desnoyers [Wed, 30 Nov 2011 14:03:10 +0000 (09:03 -0500)] 
Support older autotools

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoApply autoupdate to configure.ac
Mathieu Desnoyers [Tue, 29 Nov 2011 20:30:26 +0000 (15:30 -0500)] 
Apply autoupdate to configure.ac

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoFix build for amd64 environment (for FreeBSD 8.2)
Mathieu Desnoyers [Mon, 28 Nov 2011 19:28:29 +0000 (14:28 -0500)] 
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>
12 years agoFix cds_lfht field order
Mathieu Desnoyers [Mon, 28 Nov 2011 14:37:21 +0000 (09:37 -0500)] 
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>
12 years agorculfhash mm plugins: cleanup alloc
Mathieu Desnoyers [Mon, 28 Nov 2011 14:07:54 +0000 (09:07 -0500)] 
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>
12 years agorculfhash: document fini_table
Mathieu Desnoyers [Mon, 28 Nov 2011 14:05:36 +0000 (09:05 -0500)] 
rculfhash: document fini_table

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: likely -> caa_likely fix
Mathieu Desnoyers [Mon, 28 Nov 2011 14:02:16 +0000 (09:02 -0500)] 
rculfhash: likely -> caa_likely fix

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: cleanup ht_count_add/ht_count_del
Mathieu Desnoyers [Mon, 28 Nov 2011 14:01:39 +0000 (09:01 -0500)] 
rculfhash: cleanup ht_count_add/ht_count_del

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: reorder cds_lfht for smaller cache footprint in fast-paths
Mathieu Desnoyers [Mon, 28 Nov 2011 13:54:32 +0000 (08:54 -0500)] 
rculfhash: reorder cds_lfht for smaller cache footprint in fast-paths

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoadd rculfhash-mm-mmap.c memory management
Lai Jiangshan [Mon, 28 Nov 2011 13:41:10 +0000 (08:41 -0500)] 
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>
12 years agoadd rculfhash-mm-chunk.c memory management
Lai Jiangshan [Mon, 28 Nov 2011 13:30:55 +0000 (08:30 -0500)] 
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>
12 years agomove memory management code out as rculfhash-mm-order.c
Lai Jiangshan [Mon, 28 Nov 2011 13:26:28 +0000 (08:26 -0500)] 
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>
12 years agoMerge struct rcu_table into struct cds_lfht
Lai Jiangshan [Mon, 28 Nov 2011 13:24:27 +0000 (08:24 -0500)] 
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>
12 years agouse rcu_flavor for rculfhash
Lai Jiangshan [Mon, 28 Nov 2011 13:23:48 +0000 (08:23 -0500)] 
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>
12 years agoAdd rcu_flavor
Lai Jiangshan [Mon, 28 Nov 2011 13:22:36 +0000 (08:22 -0500)] 
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>
12 years agoadd max_nr_buckets argument
Lai Jiangshan [Mon, 28 Nov 2011 13:19:26 +0000 (08:19 -0500)] 
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>
12 years agorename min_alloc_size/min_alloc_order
Lai Jiangshan [Mon, 28 Nov 2011 13:11:38 +0000 (08:11 -0500)] 
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>
12 years agoremove struct rcu_level
Lai Jiangshan [Mon, 28 Nov 2011 13:07:32 +0000 (08:07 -0500)] 
remove struct rcu_level

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoit is not required that ht->t.size >= ht->min_table_size anymore
Lai Jiangshan [Mon, 28 Nov 2011 13:05:09 +0000 (08:05 -0500)] 
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>
12 years agoproper wrapper for bucket table alloc and free
Lai Jiangshan [Mon, 28 Nov 2011 13:01:54 +0000 (08:01 -0500)] 
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>
12 years agointroduce bucket_at() and improve readability
Lai Jiangshan [Mon, 28 Nov 2011 13:00:23 +0000 (08:00 -0500)] 
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>
12 years agoAdd missing rcu_dereference_sym_bp
Mathieu Desnoyers [Sun, 27 Nov 2011 08:58:52 +0000 (08:58 +0000)] 
Add missing rcu_dereference_sym_bp

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agourcu-bp: allow weak linking
Mathieu Desnoyers [Sun, 27 Nov 2011 00:41:09 +0000 (00:41 +0000)] 
urcu-bp: allow weak linking

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoAdd Lai Jiangshan's copyright to rculfhash
Lai Jiangshan [Wed, 23 Nov 2011 05:45:57 +0000 (06:45 +0100)] 
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>
12 years agoUpdate comments of cds_lfht_new()
Lai Jiangshan [Wed, 23 Nov 2011 05:44:35 +0000 (06:44 +0100)] 
Update comments of cds_lfht_new()

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoInstall test scripts in the dist tarball
Alexandre Montplaisir [Tue, 22 Nov 2011 17:02:29 +0000 (18:02 +0100)] 
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>
12 years agorculfhash: constify all key arguments passed to API
Mathieu Desnoyers [Wed, 16 Nov 2011 12:23:19 +0000 (07:23 -0500)] 
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>
12 years agoFix arguments order
Lai Jiangshan [Mon, 14 Nov 2011 12:56:10 +0000 (07:56 -0500)] 
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>
12 years agorculfhash: Add parenthesis around macro arg use in iterator macro
Mathieu Desnoyers [Thu, 10 Nov 2011 18:55:07 +0000 (13:55 -0500)] 
rculfhash: Add parenthesis around macro arg use in iterator macro

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoAdd hash table iterator macros
Mathieu Desnoyers [Wed, 9 Nov 2011 21:18:42 +0000 (16:18 -0500)] 
Add hash table iterator macros

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoRemove whiteline
Mathieu Desnoyers [Wed, 9 Nov 2011 19:50:34 +0000 (14:50 -0500)] 
Remove whiteline

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: rename dummy to bucket
Lai Jiangshan [Sat, 5 Nov 2011 13:52:41 +0000 (09:52 -0400)] 
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>
12 years agorculfhash: Move key out of struct lfht_test_node, move key_len to caller
Lai Jiangshan [Sat, 5 Nov 2011 13:48:18 +0000 (09:48 -0400)] 
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>
12 years agorculfhash: Remove leftover hash_seed field
Mathieu Desnoyers [Sat, 5 Nov 2011 13:10:12 +0000 (09:10 -0400)] 
rculfhash: Remove leftover hash_seed field

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: extract compare_fct and hash_fct from the hash table
Mathieu Desnoyers [Sat, 5 Nov 2011 13:01:09 +0000 (09:01 -0400)] 
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>
13 years agoVersion 0.6.6 v0.6.6
Mathieu Desnoyers [Thu, 3 Nov 2011 16:49:07 +0000 (12:49 -0400)] 
Version 0.6.6

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoMerge branch 'master' into urcu/ht-shrink
Mathieu Desnoyers [Thu, 3 Nov 2011 14:58:54 +0000 (10:58 -0400)] 
Merge branch 'master' into urcu/ht-shrink

13 years agoqsbr vs call_rcu : remove exit assertion
Mathieu Desnoyers [Wed, 14 Sep 2011 17:36:12 +0000 (13:36 -0400)] 
qsbr vs call_rcu : remove exit assertion

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: Move "struct rcu_head head" out of "struct cds_lfht_node"
Lai Jiangshan [Wed, 2 Nov 2011 17:22:30 +0000 (13:22 -0400)] 
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>
13 years agorculfhash, test: wrap struct cds_lfht_node
Lai Jiangshan [Wed, 2 Nov 2011 17:20:57 +0000 (13:20 -0400)] 
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>
13 years agorculfhash: Change lazy shrink strategy
Lai Jiangshan [Wed, 2 Nov 2011 15:31:14 +0000 (11:31 -0400)] 
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>
13 years agorculfhash: merge duplicated code of cds_lfht_resize_lazy_*()
Lai Jiangshan [Wed, 2 Nov 2011 15:21:35 +0000 (11:21 -0400)] 
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>
13 years agorculfhash: Fix ht lazy grow logic.
Lai Jiangshan [Wed, 2 Nov 2011 15:20:11 +0000 (11:20 -0400)] 
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>
13 years agorculfhash: rename likely/unlikely (add caa_ prefix)
Mathieu Desnoyers [Wed, 2 Nov 2011 00:17:16 +0000 (20:17 -0400)] 
rculfhash: rename likely/unlikely (add caa_ prefix)

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoMerge branch 'master' into urcu/ht-shrink
Mathieu Desnoyers [Wed, 2 Nov 2011 00:15:55 +0000 (20:15 -0400)] 
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>
13 years agoRename likely/unlikely to caa_likely/caa_unlikely
Mathieu Desnoyers [Tue, 1 Nov 2011 23:58:52 +0000 (19:58 -0400)] 
Rename likely/unlikely to caa_likely/caa_unlikely

This fixes namespace conflicts.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoAdd structure descriptions, remove redundant clear_flag()
Mathieu Desnoyers [Tue, 1 Nov 2011 19:45:01 +0000 (15:45 -0400)] 
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>
13 years agoFix CAA_BITS_PER_lONG typo
Paul E. McKenney [Tue, 1 Nov 2011 18:48:31 +0000 (14:48 -0400)] 
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>
13 years agorculfhash: add min_alloc_size test parameter
Lai Jiangshan [Tue, 1 Nov 2011 17:09:13 +0000 (13:09 -0400)] 
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>
13 years agorculfhash: Fix min_alloc_size bug
Lai Jiangshan [Tue, 1 Nov 2011 17:08:13 +0000 (13:08 -0400)] 
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>
13 years agorculfhash: Fix ht allocation bug
Lai Jiangshan [Tue, 1 Nov 2011 16:54:04 +0000 (12:54 -0400)] 
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>
13 years agorculfhash: add CDS_LFHT_ACCOUNTING flag
Lai Jiangshan [Fri, 28 Oct 2011 08:16:34 +0000 (10:16 +0200)] 
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>
13 years agorculfhash: use DEFAULT_SPLIT_COUNT_MASK for !HAVE_SYSCONF
Lai Jiangshan [Fri, 28 Oct 2011 07:31:51 +0000 (09:31 +0200)] 
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>
13 years agorculfhash: use hash for index if !HAVE_SCHED_GETCPU
Lai Jiangshan [Fri, 28 Oct 2011 07:29:47 +0000 (09:29 +0200)] 
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>
13 years agorculfhash: rename percpu_count to split_count
Lai Jiangshan [Fri, 28 Oct 2011 07:28:14 +0000 (09:28 +0200)] 
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>
13 years agorculfhash: Cast to struct rcu_level * instead of void * (cleanup)
Mathieu Desnoyers [Fri, 28 Oct 2011 06:18:30 +0000 (08:18 +0200)] 
rculfhash: Cast to struct rcu_level * instead of void * (cleanup)

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: directly lookup bucket in the first order table
Lai Jiangshan [Fri, 28 Oct 2011 06:14:07 +0000 (08:14 +0200)] 
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>
13 years agoAvoid alloc small memory pieces
Lai Jiangshan [Fri, 28 Oct 2011 06:09:40 +0000 (08:09 +0200)] 
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>
13 years agorculfhash: Remove unneed branches
Lai Jiangshan [Fri, 28 Oct 2011 06:02:12 +0000 (08:02 +0200)] 
rculfhash: Remove unneed branches

By the effect of previous patch, some unneed branches can be removed.
One of them is in the fast path.

These branches are mostly special-cases for the node "0", which is
always populated after hash table new.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: create dummy nodes directly when create lfht
Lai Jiangshan [Fri, 28 Oct 2011 05:57:44 +0000 (07:57 +0200)] 
rculfhash: create dummy nodes directly when create lfht

make cds_lfht_new() can be called earlier(before rcu is initialized
..etc) If caller want to *parallelly* init the dummy nodes with large
init_size, he can use cds_lfht_new()+cds_lfht_resize() combination.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: fix uniquely add vs cds_lfht_next observation semantic
Lai Jiangshan [Fri, 28 Oct 2011 04:23:40 +0000 (06:23 +0200)] 
rculfhash: fix uniquely add vs cds_lfht_next observation semantic

Is it a bug?

It depends.

Current code(a combination of add_replace and add_unique)
does never generate duplicated keys, but it only
guarantees snapshot semantic: If we take a snapshot of the
hash table, we can observe that there are no duplicated keys
in the snapshot.

But this definition don't work in practice, we don't take snapshot
before observe, we actually observe them one by one.
Example:

cds_lfht_lookup(&iter);
while (should_end(&iter)) {
do_something_with(&iter);
cds_lfht_next(&iter);
}

In the old code, we may do_something_with/observe 2 duplicate nodes
in this practice!

Here is an identical-hash-value node chain with no duplicated keys
-->[p1]-->[p2]-->[p3]-->[p4]-->

Now thread 1 is the observing thread, it is travelling and do
something with the nodes. thread 2 deletes [p1], thread 3
add_unique [p1'] with the same key as [p1]

thread 1 thread 2 thread 3
---------------------------------------------------
do something with [p1]
do something with [p2]
delete [p1]
uniquely add [p1']
(-->[p2]-->[p3]-->[p4]-->[p1']-->)
do something with [p3]
do something with [p4]
do something with [p1']
---------------------------------------------------

Now, thread 1 unexpectly handles the same key twice.
It is BUG!

If we just provide snapshot semantic, it is not useful.

So we need to provide more strict add_replace/add_unique semantic.
1) no duplicated keys should ever be observable in the table(snapshot semantic)
2) no duplicated keys should ever be observed by forward iteration in the table.

The fix:
To provide forward-iteration-observation semantic, I ensure the new inserted
node(add_unique/add_replace) is inserted as the first node of
the identical-hash-value node chain.

A little another behavior is changed in this patch, we will no do gc in
cds_lfht_next_duplicate(), because it does need.

[ Note by Mathieu Desnoyers:

I agree that your semantic fix is needed for ensuring that cds_lfht_next
is semantically correct with add_unique semantic.

Just a note: the most important lookup/get next API semantic in my view
is the lookup + cds_lfht_next_duplicate, which is the typical use case
for looking up and node and getting all the duplicate keys.

Ideally, we want both get_next and get_next_duplicate to provide the
correct semantic.

I think the reason your fix here seems to work and not break the
behavior of cds_lfht_next_duplicate is because you only put nodes added
with add_unique at the beginning of the same-hash-value-chain. It's a
good thing that you don't try doing this for other add mode (allowing
duplicates), because cds_lfht_next_duplicate requires duplicate nodes to
be next one to another. And you patch keeps this behavior.

]

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
This page took 0.047955 seconds and 4 git commands to generate.