Paul E. McKenney [Fri, 7 Sep 2012 01:15:53 +0000 (21:15 -0400)]
Ensure that read-side functions meet 10-line LGPL criterion
This commit ensures that all read-side functions meet the 10-line LGPL
criterion that permits them to be expanded directly into non-LGPL code,
without function-call instructions. It also documents this as the
intent.
[ paulmck: Spelling fixes called out by Josh Triplett and name
change called out by Mathieu Desnoyers (_rcu_read_lock_help() ->
_rcu_read_lock_update(). ]
[ Mathieu Desnoyers: _rcu_read_unlock_help renamed to
_rcu_read_unlock_update_and_wakeup, and spelling fix for
preced -> precede. ]
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Thu, 6 Sep 2012 23:09:28 +0000 (19:09 -0400)]
tls-compat.h: document sigaltstack(2) limitation
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Lai Jiangshan [Thu, 6 Sep 2012 23:07:19 +0000 (19:07 -0400)]
urcu: add notice to URCU_TLS() for it is not strictly async-signal-safe
Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Thu, 6 Sep 2012 13:58:36 +0000 (09:58 -0400)]
Document sigaltstack(2) limitation
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Mon, 3 Sep 2012 17:51:43 +0000 (13:51 -0400)]
Documentation: update LICENSE file
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Mon, 27 Aug 2012 12:09:26 +0000 (08:09 -0400)]
Update version to 0.7.4
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Tue, 21 Aug 2012 22:45:37 +0000 (18:45 -0400)]
rculfhash API documentation: document destroy RCU read-lock constraint
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Tue, 21 Aug 2012 15:01:50 +0000 (11:01 -0400)]
Fix: rculfhash should be offline while waiting for resize to complete
Causes hang on destroy with urcu QSBR if destroy is called within a rcu
registered thread.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Wed, 15 Aug 2012 15:36:05 +0000 (11:36 -0400)]
Add missing entry to gitignore
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Lai Jiangshan [Thu, 9 Aug 2012 14:24:38 +0000 (10:24 -0400)]
urcu: move busy-wait code and name it ___cds_wfq_node_sync_next()
This code which waits for a node's next pointer until it appears, will
be used many times, move it to a help function and name it
___cds_wfq_node_sync_next().
Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Lai Jiangshan [Thu, 9 Aug 2012 14:19:14 +0000 (10:19 -0400)]
urcu: fix compat_futex_noasync()
This patch fix two critical problems in the compatibility fallback of
compact_futex_noasync():
1) compat_futex_cond is not bound to any @uaddr, it services all @uaddr,
if you wakeup only one thread(pthread_cond_signal), the @uaddr of
this waking thread and the @uaddr of the woken-up thread may be different.
The woken-up thread will very probably go to sleep again
because his own condition is not true.
*And* this waking thread(FUTEX_WAKE) wake up NOTHING.
2) If the caller want to wake up all waiting threads, he will use INT_MAX
for @val, and:
for (i = 0; i < INT_MAX; i++)
pthread_cond_signal(&compat_futex_cond);
becomes almost infinity loop.
Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Lai Jiangshan [Thu, 9 Aug 2012 14:10:08 +0000 (10:10 -0400)]
urcu: add hint to DEFINE_URCU_TLS() for compound types
Just a hint.
Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Mon, 30 Jul 2012 03:45:40 +0000 (23:45 -0400)]
Fix: CAA_BUILD_BUG_ON should refer to CAA_BUILD_BUG_ON_ZERO
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Ralf Baechle [Tue, 10 Jul 2012 15:03:08 +0000 (11:03 -0400)]
Add MIPS support
[ Edit by Mathieu Desnoyers: add explanations about supported
MIPS architectures, extracted from conversation with Ralf Baechle:
* Supported architectures
Ralf Baechle (edited by Mathieu Desnoyers):
This code works on all MIPS architecture variants. The memory barrier
instruction, SYNC, was introduced for MIPS II. The original MIPS I
instruction set doesn't have SYNC nor SMP support in the processor
architecture itself so SMP required horrible kludges in the system
hardware. I think it's safe to say that Linux/MIPS will never support
any of these MIPS I SMP systems. In the unlikely case this happens
anyway, we have a (Linux) kernel emulation of the SYNC instruction.
Voila - full binary compatibility across all MIPS processors and the
oldest hardware pays the performance penalty.
* Choice of barrier for cmm_mb()/cmm_rmb()/cmm_wmb()
Ralf Baechle:
"RMI (aka Netlogic and now Broadcom) XLR processor cores can be
configured to permit LD-LD, LD-ST, ST-LD and ST-ST reordering; default
is only ST-ST reordering. To allow Linux to eventually enable full
reordering cmm_mb(), cmm_rmb() and cmm_wmb() all should perform SYNC
and a compiler barrier."
* No-op choice for cmm_read_barrier_depends():
Ralf Baechle:
"Technically there is nothing in the MIPS architecture spec that would
keep a MIPS implementation from reordering as freely as an Alpha or
even more liberally. In practice most do strong ordering. However
there is no MIPS implementation that makes full use of all the rope
provided. So in theory a paranoid implementation of
cmm_read_barrier_depends() for MIPS should perform a SYNC. In reality
it's not necessary and no sane MIPS core designer would implement
something that would design a core that need a non-empty
cmm_read_barrier_depends(). The reason why my patch had an empty one
is that I was using the Alpha code as a template."
Mathieu Desnoyers:
Moreover, the Linux kernel chooses a no-op for MIPS
read_barrier_depends() implementation, so any MIPS architecture that
would be as weak as Alpha would break the Linux kernel before breaking
the userspace RCU library.
* No need to put ".set noreorder" in cmm_mb() inline assembly:
Ralf Baechle:
"Certain instructions such as SYNC won't get reordered." ]
Signed-off-by: Ralf Baechle <ralf@linux-mips.org>
CC: Paul McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Mon, 9 Jul 2012 13:44:52 +0000 (09:44 -0400)]
Compatibility: remove bash-ismsm from test scripts
+= is not supported by all shells.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Fri, 22 Jun 2012 16:48:14 +0000 (12:48 -0400)]
Fix inappropriate lib behavior: don't call exit()
Use abort() (implemented through the new urcu_die()) instead of exit(-1)
for unrecoverable errors.
Fixes #152
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Thu, 14 Jun 2012 04:56:40 +0000 (00:56 -0400)]
Fix: re-enable compatibility with autoconf < 2.64
> I tried to build the latest urcu (git master e51500) on a Centos 6.2 box, and got:
>
> jscott@dxi0-62:~/src/userspace-rcu$ make -j4
> CDPATH="${ZSH_VERSION+.}:" && cd . && /bin/sh /users/jscott/src/userspace-rcu/config/missing --run aclocal-1.11 -I
> +config
> CDPATH="${ZSH_VERSION+.}:" && cd . && /bin/sh /users/jscott/src/userspace-rcu/config/missing --run autoconf
> cd . && /bin/sh /users/jscott/src/userspace-rcu/config/missing --run automake-1.11 --foreign
> configure:4010: error: possibly undefined macro: m4_ifnblank
> If this token and others are legitimate, please use m4_pattern_allow.
> See the Autoconf documentation.
> make: *** [configure] Error 1
> make: *** Waiting for unfinished jobs....
>
> Some digging showed that the macro m4_ifnblank requires autoconf 2.64. Centos 6.2 has autoconf 2.63. :(
>
> I just worked around it by reverting commit a767fd locally, then I can build fine.
Reported-by: John Steele Scott <toojays@toojays.net>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Tue, 12 Jun 2012 15:24:31 +0000 (11:24 -0400)]
Fix c99 compatibility: use __asm__ and __volatile__ in public headers
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Mon, 11 Jun 2012 14:16:35 +0000 (10:16 -0400)]
Fix c99 compatibility: use __typeof__ instead of typeof in public headers
Reported-by: John Steele Scott <toojays@toojays.net>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Fri, 1 Jun 2012 21:12:43 +0000 (17:12 -0400)]
warning fix: tests urcutorture for NetBSD 5
> CC rcutorture_urcu-urcutorture.o
> In file included from urcutorture.c:9:
> api.h: In function '__smp_thread_id':
> api.h:160: warning: cast from pointer to integer of different size
> api.h:160: warning: cast from pointer to integer of different size
> api.h: In function 'wait_thread':
> api.h:210: warning: cast from pointer to integer of different size
> api.h:210: warning: cast from pointer to integer of different size
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
Mathieu Desnoyers [Sun, 4 Mar 2012 20:20:58 +0000 (15:20 -0500)]
Merge branch '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>
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>
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>
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>
Mathieu Desnoyers [Mon, 9 Jan 2012 23:12:13 +0000 (18:12 -0500)]
Merge branch 'master' into urcu/ht-shrink
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>
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>
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>
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>
Mathieu Desnoyers [Thu, 29 Dec 2011 14:48:25 +0000 (09:48 -0500)]
Merge branch 'master' into urcu/ht-shrink
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
This page took 0.042033 seconds and 4 git commands to generate.