urcu.git
12 years agoUpdate version to 0.7.3 v0.7.3
Mathieu Desnoyers [Fri, 1 Jun 2012 17:45:44 +0000 (13:45 -0400)] 
Update version to 0.7.3

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoFix tests: make dist lib dependency
Mathieu Desnoyers [Fri, 1 Jun 2012 17:58:31 +0000 (13:58 -0400)] 
Fix tests: make dist lib dependency

Some test programs were depending in SOURCES on the CDS library. Change
this for a LDADD, which makes "make dist" work after a make clean.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoUpdate README for OS supported, tests dependency
Mathieu Desnoyers [Fri, 1 Jun 2012 17:43:23 +0000 (13:43 -0400)] 
Update README for OS supported, tests dependency

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoAdd CodingStyle to tarball
Mathieu Desnoyers [Wed, 30 May 2012 13:55:39 +0000 (09:55 -0400)] 
Add CodingStyle to tarball

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoAdd coding style document
Mathieu Desnoyers [Wed, 30 May 2012 13:03:45 +0000 (09:03 -0400)] 
Add coding style document

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoTest fix: test_perthreadlock uninitialized mutex
Mathieu Desnoyers [Tue, 29 May 2012 02:10:54 +0000 (22:10 -0400)] 
Test fix: test_perthreadlock uninitialized mutex

- Initialize the per thread mutexes. (fix)
- Remove unused count_reader/count_writer variables. (cleanup)

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agotests: support FreeBSD short "time" args
Hirohisa Yamaguchi [Sun, 27 May 2012 18:16:59 +0000 (14:16 -0400)] 
tests: support FreeBSD short "time" args

time(1) in FreeBSD does not have long argument name: change --append to
-a and --output to -o

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agofreebsd 8.2 fix: define MAP_ANONYMOUS for compatibility
Mathieu Desnoyers [Sat, 26 May 2012 15:00:16 +0000 (11:00 -0400)] 
freebsd 8.2 fix: define MAP_ANONYMOUS for compatibility

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoUpdate version to 0.7.2 v0.7.2
Mathieu Desnoyers [Thu, 24 May 2012 21:24:21 +0000 (17:24 -0400)] 
Update version to 0.7.2

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoFix library compatibility
Mathieu Desnoyers [Thu, 24 May 2012 20:56:08 +0000 (16:56 -0400)] 
Fix library compatibility

Commit 4d0d66bb795d1ed938e11a97a4e5f71326e20c71, implementing
tls-compat.h for pthread TLS compatibility, adds a prefix in front of
each TLS symbol (__tls_*). However, some of these symbols are exported
by the URCU library (e.g. rcu_reader_mb, defined in urcu.c as
"rcu_reader", which is overloaded by the urcu/map/urcu.h) to
applications. Therefore, this breaks binary compatibility with 0.6.x
versions of the library. This is not intended, and therefore is a bug,
so we remove this __tls_* prefix from the variables declared, defined
and referenced to through the tls-compat.h API for compilers supporting
"__thread".

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoUpdate version to 0.7.1 v0.7.1
Mathieu Desnoyers [Thu, 24 May 2012 17:17:30 +0000 (13:17 -0400)] 
Update version to 0.7.1

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agofix: uatomic_set return value compile fix for non-x86 arch.
Mathieu Desnoyers [Thu, 24 May 2012 15:51:03 +0000 (11:51 -0400)] 
fix: uatomic_set return value compile fix for non-x86 arch.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoUpdate version to 0.7.0 v0.7.0
Mathieu Desnoyers [Mon, 21 May 2012 19:09:46 +0000 (15:09 -0400)] 
Update version to 0.7.0

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoCleanup: header comments coding style
Mathieu Desnoyers [Mon, 21 May 2012 22:35:22 +0000 (18:35 -0400)] 
Cleanup: header comments coding style

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoDocument uatomic operations
Mathieu Desnoyers [Fri, 18 May 2012 03:18:35 +0000 (23:18 -0400)] 
Document uatomic operations

Document each atomic operation provided by urcu/uatomic.h, along with
their memory barrier guarantees.

Acked-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoUpdate return value of "set" operations
Mathieu Desnoyers [Fri, 18 May 2012 03:14:26 +0000 (23:14 -0400)] 
Update return value of "set" operations

To follow the way the Linux kernel implements atomic_set(), we change
some API functions so they don't return any value anymore.

This is now the case for:

uatomic_set()
rcu_set_pointer()
rcu_assign_pointer()

This API change is very minor. In all instances of the Linux kernel
using rcu_assign_pointer(), none currently care about its return value.

However, we keep ABI compatibility: rcu_set_pointer_sym() still returns
the "v" value, even though it is not used by its wrapper macro anymore.

Reviewed-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoFix mremap wrapper for NetBSD 5
Mathieu Desnoyers [Wed, 16 May 2012 18:30:09 +0000 (14:30 -0400)] 
Fix mremap wrapper for NetBSD 5

NetBSD 5 implements a mremap with a different semantic. Rename our
wrapper symbol name so it does not clash with the NetBSD 5 symbol.
Eventually, we could envision doing a special-case that uses the NetBSD
5 version instead of the fallback, but let's first get it working before
going into optimization land.

Suggested-by: Marek Vavruša <marek.vavrusa@nic.cz>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoUse urcu/tls-compat.h
Mathieu Desnoyers [Wed, 16 May 2012 13:42:55 +0000 (09:42 -0400)] 
Use urcu/tls-compat.h

Provides compatibility for OpenBSD, NetBSD and Darwin.

Suggested-by: Marek Vavruša <marek.vavrusa@nic.cz>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoImplement urcu/tls-compat.h
Mathieu Desnoyers [Tue, 15 May 2012 20:19:07 +0000 (16:19 -0400)] 
Implement urcu/tls-compat.h

Suggested-by: Marek Vavruša <marek.vavrusa@nic.cz>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoAdd TLS detection m4 macro
Mathieu Desnoyers [Tue, 15 May 2012 18:35:44 +0000 (14:35 -0400)] 
Add TLS detection m4 macro

Will allow urcu to support OSes that require to use pthread TLS (and do
not provide __thread TLS support).

Suggested-by: Marek Vavruša <marek.vavrusa@nic.cz>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agodocument concurrent data structures
Mathieu Desnoyers [Tue, 15 May 2012 11:50:30 +0000 (07:50 -0400)] 
document concurrent data structures

Document the concurrent data structures provided by the userspace RCU
library.

Reviewed-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agodocumentation: refer to rcu-api.txt
Mathieu Desnoyers [Tue, 15 May 2012 03:01:06 +0000 (23:01 -0400)] 
documentation: refer to rcu-api.txt

API.txt moved to userspace-rcu documentation rcu-api.txt.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoMove API.txt to doc/rcu-api.txt, install in system doc/
Mathieu Desnoyers [Tue, 15 May 2012 02:37:26 +0000 (22:37 -0400)] 
Move API.txt to doc/rcu-api.txt, install in system doc/

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: document implied memory barriers
Mathieu Desnoyers [Tue, 8 May 2012 21:12:20 +0000 (17:12 -0400)] 
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>
12 years agorculfhash: Ensure future-proof memory barrier semantic consistency
Mathieu Desnoyers [Tue, 8 May 2012 21:09:46 +0000 (17:09 -0400)] 
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>
12 years agoAPI cleanup: use "uatomic_*" in cmm_smp_mb__ API
Mathieu Desnoyers [Tue, 8 May 2012 21:07:03 +0000 (17:07 -0400)] 
API cleanup: use "uatomic_*" in cmm_smp_mb__ API

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agouatomic: add memory barrier API for and/or/add/sub/inc/sub
Mathieu Desnoyers [Tue, 8 May 2012 20:47:28 +0000 (16:47 -0400)] 
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>
12 years agorculfhash: add runhash.sh test script
Mathieu Desnoyers [Tue, 8 May 2012 04:42:58 +0000 (00:42 -0400)] 
rculfhash: add runhash.sh test script

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash tests: add missing check
Mathieu Desnoyers [Tue, 8 May 2012 04:03:00 +0000 (00:03 -0400)] 
rculfhash tests: add missing check

We need to check if test_ht is NULL.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: fix: race between replace and del operations
Mathieu Desnoyers [Mon, 7 May 2012 23:07:35 +0000 (19:07 -0400)] 
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>
12 years agorculfhash: replace unneeded rcu_dereference by CMM_LOAD_SHARED
Mathieu Desnoyers [Mon, 7 May 2012 15:18:14 +0000 (11:18 -0400)] 
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>
12 years agorculfhash: use do {} while (0) for dbg_printf()
Mathieu Desnoyers [Mon, 7 May 2012 15:10:52 +0000 (11:10 -0400)] 
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>
12 years agorculfhash: cleanup typo
Mathieu Desnoyers [Tue, 1 May 2012 12:09:37 +0000 (08:09 -0400)] 
rculfhash: cleanup typo

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: update API comments
Mathieu Desnoyers [Sun, 29 Apr 2012 23:04:20 +0000 (19:04 -0400)] 
rculfhash: update API comments

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: update comments in implementation
Mathieu Desnoyers [Sun, 29 Apr 2012 22:49:19 +0000 (18:49 -0400)] 
rculfhash: update comments in implementation

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash tests: add long hash chains tests
Mathieu Desnoyers [Sun, 29 Apr 2012 20:49:10 +0000 (16:49 -0400)] 
rculfhash tests: add long hash chains tests

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash tests: add uniqueness test
Mathieu Desnoyers [Sun, 29 Apr 2012 20:19:09 +0000 (16:19 -0400)] 
rculfhash tests: add uniqueness test

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash test: print test name
Mathieu Desnoyers [Sun, 29 Apr 2012 20:18:03 +0000 (16:18 -0400)] 
rculfhash test: print test name

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: stress requirement in documentation
Mathieu Desnoyers [Sun, 29 Apr 2012 19:51:28 +0000 (15:51 -0400)] 
rculfhash: stress requirement in documentation

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: fix typo
Mathieu Desnoyers [Wed, 25 Apr 2012 00:56:43 +0000 (20:56 -0400)] 
rculfhash: fix typo

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash tests: use array of callbacks to modularize
Mathieu Desnoyers [Tue, 24 Apr 2012 14:52:57 +0000 (10:52 -0400)] 
rculfhash tests: use array of callbacks to modularize

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash tests: modularize tests
Mathieu Desnoyers [Tue, 24 Apr 2012 14:30:15 +0000 (10:30 -0400)] 
rculfhash tests: modularize tests

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: document ordering guarantees
Mathieu Desnoyers [Tue, 24 Apr 2012 04:16:43 +0000 (00:16 -0400)] 
rculfhash: document ordering guarantees

What we actually provide are ordering guarantees.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: document linearizability guarantees
Mathieu Desnoyers [Wed, 18 Apr 2012 20:05:29 +0000 (16:05 -0400)] 
rculfhash: document linearizability guarantees

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agorculfhash: update removal comment
Mathieu Desnoyers [Fri, 13 Apr 2012 13:21:33 +0000 (09:21 -0400)] 
rculfhash: update removal comment

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoAdd missing files to .gitignore
Mathieu Desnoyers [Fri, 13 Apr 2012 12:51:37 +0000 (08:51 -0400)] 
Add missing files to .gitignore

Fixes #93

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoFix out-of-tree build
Mathieu Desnoyers [Fri, 13 Apr 2012 12:37:53 +0000 (08:37 -0400)] 
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>
12 years agorculfhash: check malloc NULL pointer
Mathieu Desnoyers [Mon, 2 Apr 2012 18:35:34 +0000 (14:35 -0400)] 
rculfhash: check malloc NULL pointer

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoFix uatomic sign cast
Mathieu Desnoyers [Mon, 26 Mar 2012 15:27:01 +0000 (11:27 -0400)] 
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>
12 years agoRemove unused jhash.h file
Mathieu Desnoyers [Thu, 8 Mar 2012 18:03:08 +0000 (13:03 -0500)] 
Remove unused jhash.h file

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoFix: use known license text, fix incorrect FSF address
Mathieu Desnoyers [Thu, 8 Mar 2012 17:50:11 +0000 (12:50 -0500)] 
Fix: use known license text, fix incorrect FSF address

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoFix: add missing sched.h include in rculfhash.c
Mathieu Desnoyers [Mon, 5 Mar 2012 21:14:19 +0000 (16:14 -0500)] 
Fix: add missing sched.h include in rculfhash.c

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoAllow tests to run on architectures without per-cpu call_rcu support
Mathieu Desnoyers [Sun, 4 Mar 2012 20:50:07 +0000 (15:50 -0500)] 
Allow tests to run on architectures without per-cpu call_rcu support

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoHash table test: FreeBSD compatibility fix
Mathieu Desnoyers [Sun, 4 Mar 2012 20:41:43 +0000 (15:41 -0500)] 
Hash table test: FreeBSD compatibility fix

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agotests: define _GNU_SOURCE instead of __USE_GNU
Mathieu Desnoyers [Sun, 4 Mar 2012 20:26:09 +0000 (15:26 -0500)] 
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>
12 years agoMerge branch 'urcu/ht-shrink'
Mathieu Desnoyers [Sun, 4 Mar 2012 20:20:58 +0000 (15:20 -0500)] 
Merge branch 'urcu/ht-shrink'

12 years agoRCU lock-free hash table: implement cds_lfht_is_node_deleted() urcu/ht-shrink
Mathieu Desnoyers [Wed, 22 Feb 2012 00:06:52 +0000 (19:06 -0500)] 
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>
12 years agoDefine _GNU_SOURCE to access CPU_ZERO() macro in uClibc
Thomas Petazzoni [Wed, 8 Feb 2012 05:49:27 +0000 (00:49 -0500)] 
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>
12 years agoInstall ChangeLog and README into system's doc
Mathieu Desnoyers [Sat, 4 Feb 2012 21:49:01 +0000 (16:49 -0500)] 
Install ChangeLog and README into system's doc

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
12 years agoFix AC_LANG_SOURCE usage: only takes one parameter
Mathieu Desnoyers [Mon, 9 Jan 2012 23:40:24 +0000 (18:40 -0500)] 
Fix AC_LANG_SOURCE usage: only takes one parameter

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

12 years agoFix autoconf futex check
David Goulet [Mon, 9 Jan 2012 23:11:23 +0000 (18:11 -0500)] 
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>
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>
This page took 0.042617 seconds and 4 git commands to generate.