Mathieu Desnoyers [Sat, 3 Sep 2011 15:37:47 +0000 (11:37 -0400)] 
Use cds_lfht namespace for lock-free hash table
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Sat, 3 Sep 2011 15:16:02 +0000 (11:16 -0400)]
RCU hash table API documentation
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Sat, 3 Sep 2011 14:48:44 +0000 (10:48 -0400)]
Merge branch 'master' into urcu/ht
Conflicts:
Makefile.am
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Sat, 3 Sep 2011 14:07:41 +0000 (10:07 -0400)]
rculfstack/queue: define _LGPL_SOURCE around static header include
... so the urcu-pointer header takes the LGPL version of rcu_dereference
and friends.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Sat, 3 Sep 2011 13:49:07 +0000 (09:49 -0400)]
Revert "Create per RCU flavor CDS libraries"
This reverts commit
d4b99c015229978810319cfd42e1c9763772fad8.
Minor change (not visible to end-users): this commit introduces a
liburcu-common.so to hold wfqueue, wfstack and futex fall-back code.
This .so is used by all URCU flavors, as well as liburcu-cds.so.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Sat, 3 Sep 2011 13:15:14 +0000 (09:15 -0400)]
Revert "CDS API: removal of rcu_read lock/unlock dep, removal of call_rcu argument from init"
This reverts commit
7618919ae496bda84a2efa4f2ad0abe569892a9e.
Rationale:
I thought about it some more, and had discussions with various people,
and there are a few reasons to go for a scheme where rcu read lock
should be taken by the caller, and to pass call_rcu as a parameter to
the data structure init function:
A) The advantage, as Paul E. McKenney pointed out, is that one single .so
is enough to support all RCU flavors. Very convenient for external data
structure containers.
B) It clearly documents where rcu read-side locks are needed, so the user
keep control and in-depth understanding of their read-side locks.
C) When multiple API functions that require RCU read-side lock to be
held (sometimes even the same lock) throughout a sequence of API
calls, we have no choice but to let the caller hold the read-side
lock.
D) Due to support of multiple nesting of rcu read-side lock, any
"improvement" we could get by releasing the read-side lock in
retry loops would vanish in the cases where we are called within
nested C.S..
E) If a library uses synchronize_rcu, this should be clearly documented,
and even frowned upon, because this involves important limitations on
the design of the caller, and important performance hit. There are
usually ways to reach the same result through use of call_rcu, which
should really be used thoroughout these libraries.
F) It clearly documents when a data structure needs to use call_rcu
internally.
G) Some very early benchmark results show that there is indeed not
much performance gain to achieve by inlining call_rcu, even if it is
a version with a cache for the "call_rcu structure" lookup
(per-cpu/per-thread/global). So passing it as a parameter to
the data structure init function should be fine, even in cases
where it is called very often.
H) For use-cases where applications would like to use more than one
RCU flavor concurrently (which is now supported), leaving management
of RCU read-side C.S. to the reader allows the application to take
more than one RCU read-side lock across API calls. It also lets the
application specify its own call_rcu function that could handle more
than one RCU flavor.
So for all these reasons, I reverting back to the API we have in our
last release (0.6.4).
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Sat, 3 Sep 2011 12:37:22 +0000 (08:37 -0400)]
Add __rcu annotation (unimplemented)
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Thu, 1 Sep 2011 20:11:14 +0000 (16:11 -0400)]
Fix incorrect fsf address in header files
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Thu, 1 Sep 2011 13:31:55 +0000 (09:31 -0400)]
wfstack: push returns prior stack emptiness state
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Thu, 1 Sep 2011 13:28:30 +0000 (09:28 -0400)]
Make lf stack push return if the stack was empty
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Tue, 23 Aug 2011 21:22:00 +0000 (17:22 -0400)]
Document caa_container_of
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Sat, 20 Aug 2011 17:50:08 +0000 (13:50 -0400)]
urcu-bp: do not call munmap for NULL registry at exit
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Thu, 18 Aug 2011 17:41:11 +0000 (13:41 -0400)]
urcu libraries can directly use the _LGPL_SOURCE wfqueue
No need to link dynamically with the data structure object.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Thu, 18 Aug 2011 16:13:44 +0000 (12:13 -0400)]
rculfstack: document "push"
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Wed, 17 Aug 2011 21:58:30 +0000 (17:58 -0400)]
Add runall.sh to tarball
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Wed, 17 Aug 2011 21:57:19 +0000 (17:57 -0400)]
Fix build order of liburcu-cds-common
Caused make install to fail.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Wed, 17 Aug 2011 21:54:33 +0000 (17:54 -0400)]
CDS API: removal of rcu_read lock/unlock dep, removal of call_rcu argument from init
* API change * for all liburcu-cds* flavors.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Wed, 17 Aug 2011 21:54:07 +0000 (17:54 -0400)]
Fix missing check for SYS_membarrier in map header
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Wed, 17 Aug 2011 20:42:20 +0000 (16:42 -0400)]
Create per RCU flavor CDS libraries
Introduce per-flavor concurrent data structure libraries for data
structures depending on RCU:
liburcu-cds: memb flavor (default), matches -lurcu
liburcu-cds-qsbr: qsbr flavor, matches -lurcu-qsbr
liburcu-cds-mb: mb flavor, matches -lurcu-mb
liburcu-cds-signal, matches -lurcu-signal
liburcu-cds-bp, matches -lurcu-bp
liburcu-cds-common: Data structures not depending on RCU for
synchronization.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Wed, 17 Aug 2011 10:07:35 +0000 (06:07 -0400)]
Merge branch 'master' into lfqueue-dev
Paolo Bonzini [Wed, 17 Aug 2011 09:42:51 +0000 (05:42 -0400)] 
urcu-qsbr: avoid useless futex wakeups and burning CPU for long grace periods
I noticed that urcu makes exactly _one_ attempt at using futexes
to avoid busy looping on synchronize_rcu. The attached patch instead
switches from busy waiting to futexes after RCU_QS_ACTIVE_ATTEMPTS.
To limit the amount of system calls, reading threads remember whether
they already had a quiescent state in this grace period; if so they were
already removed from the list, and can avoid signaling the futex.
Performance measured with rcutorture (nreaders: 10, nupdaters: 1,
duration: 10, median of nine runs):
RCU_QS_ACTIVE_ATTEMPTS == 100, no patch n_updates = 292
RCU_QS_ACTIVE_ATTEMPTS == 1, no patch n_updates = 290
RCU_QS_ACTIVE_ATTEMPTS == 100, with patch n_updates = 408
RCU_QS_ACTIVE_ATTEMPTS == 1, with patch n_updates = 404
(the first two cases are obviously the same; the only change is
when the futex is used, but over many calls there is no difference).
This patch matches the update to the Promela model.
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Paolo Bonzini [Wed, 17 Aug 2011 09:33:58 +0000 (05:33 -0400)]
api: reimplement BUILD_BUG_ON in compiler.h
Even though it's just two lines of code, I'm reimplementing it
cleanly out of paranoia.
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Paolo Bonzini [Wed, 17 Aug 2011 09:31:21 +0000 (05:31 -0400)]
test api cleanup: remove unused primitives
[ Mathieu: the rationale for this is that we can always add back that
code if every needed. Removing leftover GPLv2 test code is an
incentive to create the appropriate library-wide LGPL/MIT-style
abstractions.]
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Wed, 17 Aug 2011 09:28:33 +0000 (05:28 -0400)]
Merge branch 'master' into lfqueue-dev
Paolo Bonzini [Tue, 9 Aug 2011 20:49:27 +0000 (16:49 -0400)]
put thread offline while waiting for the init flag
Otherwise, the call_rcu thread might end up in a synchronize_rcu that
never ends.
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Paolo Bonzini [Tue, 9 Aug 2011 20:44:20 +0000 (16:44 -0400)]
urcu: move private definitions to .c file
The reader does not and should not know about RCU_QS_ACTIVE_ATTEMPTS
and KICK_READER_LOOPS. Move the definition to urcu.c.
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Paolo Bonzini [Tue, 9 Aug 2011 20:43:21 +0000 (16:43 -0400)]
urcu-bp: move private definitions to .c file
The reader does not and should not know about RCU_QS_ACTIVE_ATTEMPTS.
Move the definition to urcu-bp.c.
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Paolo Bonzini [Tue, 9 Aug 2011 20:42:53 +0000 (16:42 -0400)]
urcu-qsbr: move private definitions to .c file
The reader does not and should not know about RCU_QS_ACTIVE_ATTEMPTS.
Move the definition to urcu-qsbr.c. Also remove KICK_READER_LOOPS.
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Paolo Bonzini [Tue, 9 Aug 2011 20:40:29 +0000 (16:40 -0400)]
rcutorture: fix rcutorture-qsbr
rcutorture-qsbr is not marking quiescent states, so it will always
have just one update in the whole test. Fix it.
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Paolo Bonzini [Tue, 9 Aug 2011 12:37:14 +0000 (08:37 -0400)]
wfqueue: fix type-incorrect assignment
The "old_tail = q->tail, q->tail = node" assignment in wfqueue
is not type safe; q->tail is a pointer to pointer to node and the
correct value to assign is &node->next. While the arithmetic is
the same, it is better to be tidy.
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Tue, 16 Aug 2011 11:11:16 +0000 (07:11 -0400)]
Fix tests Makefile EXTRA_DIST to use api.h
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Duncan Sands [Tue, 16 Aug 2011 11:10:01 +0000 (07:10 -0400)] 
Fix choice of default flavour in urcu/map/urcu.h
Hi, I noticed in the 0.64 release (and git too) that if a flavour is not
specified explicitly then RCU_MB is chosen in urcu/map/urcu.h, while the
docs say and the Makefile expects RCU_MEMBARRIER. Note that the header
file urcu/static/urcu.h has similar logic but uses RCU_MEMBARRIER for
the default.
Before this patch:
$ nm *.a | grep rcu_init
00000000000003c0 T rcu_init_mb
00000000000003c0 T rcu_init_mb
0000000000000000 T rcu_init_sig
After this patch:
$ nm *.a | grep rcu_init
00000000000003c0 T rcu_init_memb
00000000000003c0 T rcu_init_mb
0000000000000000 T rcu_init_sig
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Paolo Bonzini [Tue, 16 Aug 2011 10:52:54 +0000 (06:52 -0400)]
api: remove list/hlist
Remove the parts that actually caused compilation to fail.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Paolo Bonzini [Tue, 16 Aug 2011 10:51:55 +0000 (06:51 -0400)]
api: remove arch-specific files
No change since they were a subset of api_gcc.h. api_gcc.h is
renamed to api.h, and configure need not create a symlink anymore.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Paolo Bonzini [Tue, 16 Aug 2011 10:41:06 +0000 (06:41 -0400)]
api: make api_gcc.h a superset of the other headers
After this patch the only differences are:
- for_each_tid is now defined in api_x86.h
- HAVE_CPU_SET_T and HAVE_SCHED_SETAFFINITY are now defined in api_ppc.h
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Paolo Bonzini [Fri, 12 Aug 2011 22:23:59 +0000 (18:23 -0400)]
tests api: remove atomics
The code is #if 0'd already, remove it.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Paolo Bonzini [Tue, 9 Aug 2011 20:49:27 +0000 (16:49 -0400)]
put thread offline while waiting for the init flag
Otherwise, the call_rcu thread might end up in a synchronize_rcu that
never ends.
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Paolo Bonzini [Tue, 9 Aug 2011 20:44:20 +0000 (16:44 -0400)]
urcu: move private definitions to .c file
The reader does not and should not know about RCU_QS_ACTIVE_ATTEMPTS
and KICK_READER_LOOPS. Move the definition to urcu.c.
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Paolo Bonzini [Tue, 9 Aug 2011 20:43:21 +0000 (16:43 -0400)]
urcu-bp: move private definitions to .c file
The reader does not and should not know about RCU_QS_ACTIVE_ATTEMPTS.
Move the definition to urcu-bp.c.
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Paolo Bonzini [Tue, 9 Aug 2011 20:42:53 +0000 (16:42 -0400)]
urcu-qsbr: move private definitions to .c file
The reader does not and should not know about RCU_QS_ACTIVE_ATTEMPTS.
Move the definition to urcu-qsbr.c. Also remove KICK_READER_LOOPS.
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Paolo Bonzini [Tue, 9 Aug 2011 20:40:29 +0000 (16:40 -0400)]
rcutorture: fix rcutorture-qsbr
rcutorture-qsbr is not marking quiescent states, so it will always
have just one update in the whole test. Fix it.
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Paolo Bonzini [Tue, 9 Aug 2011 12:37:14 +0000 (08:37 -0400)]
wfqueue: fix type-incorrect assignment
The "old_tail = q->tail, q->tail = node" assignment in wfqueue
is not type safe; q->tail is a pointer to pointer to node and the
correct value to assign is &node->next. While the arithmetic is
the same, it is better to be tidy.
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Mon, 8 Aug 2011 15:15:03 +0000 (11:15 -0400)]
Merge branch 'master' into lfqueue-dev
Mathieu Desnoyers [Tue, 2 Aug 2011 17:22:38 +0000 (13:22 -0400)]
Use caa_ prefix for min() and max()
Defining min/max macros clashes with C++.
Reported-by: Vegard Nossum <vegard.nossum@gmail.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Thu, 21 Jul 2011 21:25:43 +0000 (17:25 -0400)]
Version 0.6.4, update changelog
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Thu, 21 Jul 2011 21:17:47 +0000 (17:17 -0400)]
Merge branch 'master' into lfqueue-dev
Mathieu Desnoyers [Thu, 21 Jul 2011 20:50:42 +0000 (16:50 -0400)]
Fix ARM uatomic: missing return in uatomic and/or
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Tue, 12 Jul 2011 19:59:00 +0000 (15:59 -0400)]
rculfhash: add likely/unlikely annotation
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Tue, 12 Jul 2011 16:15:06 +0000 (12:15 -0400)]
rculfhash: document add lock-freedom
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Tue, 12 Jul 2011 15:59:00 +0000 (11:59 -0400)]
rculfhash: document node alignment
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Tue, 12 Jul 2011 15:19:35 +0000 (11:19 -0400)]
rculfhash: document algorithms
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Mon, 11 Jul 2011 21:56:21 +0000 (17:56 -0400)]
rculfhash test: make teardown more verbose and faster
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Mon, 11 Jul 2011 21:34:05 +0000 (17:34 -0400)]
rculfhash: print resize length (useful as non-debug for now)
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Mon, 11 Jul 2011 21:32:55 +0000 (17:32 -0400)]
rculfhash: tolerate longer chain length
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Mon, 11 Jul 2011 21:14:08 +0000 (17:14 -0400)]
rculfhash: diminish index table memory consumption
- introduce log2 rcu table for resize.
- pull the dummy nodes into invariant per-log2-level tables.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Sat, 9 Jul 2011 20:43:26 +0000 (16:43 -0400)]
rculfhash: add missing clear flag in gc
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Sat, 9 Jul 2011 20:34:29 +0000 (16:34 -0400)]
rculfhash: document flags
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Sat, 9 Jul 2011 20:22:32 +0000 (16:22 -0400)]
rculfhash: merge dummy into next ptr
part 2: rely on the flag for check.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Sat, 9 Jul 2011 19:28:38 +0000 (15:28 -0400)]
rculfhash: merge dummy flag into next pointer
step 1: set flag
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Sat, 9 Jul 2011 19:12:28 +0000 (15:12 -0400)]
rculfhash: Add clear flag
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Sat, 9 Jul 2011 19:04:40 +0000 (15:04 -0400)]
rculfhash: introduce REMOVED_FLAG and FLAG_MASK
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Sat, 9 Jul 2011 19:02:26 +0000 (15:02 -0400)]
rculfhash: shrink size of dummy node
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Sat, 9 Jul 2011 17:28:01 +0000 (13:28 -0400)]
rculfhash: wait for call_rcu quiescence before destroy
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Thu, 7 Jul 2011 16:27:19 +0000 (12:27 -0400)]
rculfhash: add c++ ifdef
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Thu, 7 Jul 2011 16:19:14 +0000 (12:19 -0400)]
rculfhash test: add options
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Thu, 7 Jul 2011 15:49:09 +0000 (11:49 -0400)]
rculfhash test: use per-cpu call-rcu threads
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Thu, 7 Jul 2011 15:48:34 +0000 (11:48 -0400)]
rculfhash: update add_unique api
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Thu, 7 Jul 2011 15:13:06 +0000 (11:13 -0400)]
rculfhash: fix add unique
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Thu, 7 Jul 2011 14:43:51 +0000 (10:43 -0400)]
rculfhash test: increases random pool size
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Thu, 7 Jul 2011 14:36:39 +0000 (10:36 -0400)]
rculfhash: remove hash from nodes
Shrink node size, can get it quickly by reversing the reverse_hash.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Thu, 7 Jul 2011 14:24:00 +0000 (10:24 -0400)]
rculfhash: change order of node fields for locality
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Thu, 7 Jul 2011 13:48:44 +0000 (09:48 -0400)]
rculfhash: merge node gc into add loop
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Thu, 7 Jul 2011 13:43:50 +0000 (09:43 -0400)]
rculfhash: cleanup
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Thu, 7 Jul 2011 13:20:39 +0000 (09:20 -0400)]
rculfhash test: add nr_leaked count
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Thu, 7 Jul 2011 13:09:04 +0000 (09:09 -0400)]
rculfhash: garbage collection scheme
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Wed, 6 Jul 2011 20:05:48 +0000 (16:05 -0400)]
rculfhash: flip order of removal
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Wed, 6 Jul 2011 19:00:14 +0000 (15:00 -0400)]
rculfhash: Remove "value" pointer
Use container_of instead.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Wed, 6 Jul 2011 17:37:19 +0000 (13:37 -0400)]
rculfhash test: add missing free
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Wed, 6 Jul 2011 15:19:08 +0000 (11:19 -0400)]
rculfhash: add unique
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Wed, 6 Jul 2011 14:50:09 +0000 (10:50 -0400)]
Update resize thresholds
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Wed, 6 Jul 2011 14:45:04 +0000 (10:45 -0400)]
rculfhash updates
- Add and remove now completely lock-free (no busy-wait loop).
- Add resize_initiated flag to skip multiple call_rcu calls.
- Identical reverse hashes now only count as one chain entry in the
chain length accounting. We cannot split identical hashes by growing
the hash table anyway, so it was leading to large tables uselessly
when we had a lot of similar hashes.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Wed, 6 Jul 2011 05:07:33 +0000 (01:07 -0400)]
Comment list behavior wrt lock-freedom
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Wed, 6 Jul 2011 04:52:07 +0000 (00:52 -0400)]
Fix reverse hash comparison
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Wed, 6 Jul 2011 04:44:43 +0000 (00:44 -0400)]
rculfhash: use threshold and target
Accept to target bucket len greater than 1 to diminish the memory
consumption without too much performance impact.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Wed, 6 Jul 2011 03:47:32 +0000 (23:47 -0400)]
rculfhash: implement real hash function
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Wed, 6 Jul 2011 02:43:17 +0000 (22:43 -0400)]
rculfhash: fix resize (use log2 of chain length)
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Wed, 6 Jul 2011 01:02:11 +0000 (21:02 -0400)]
Merge remote branch 'origin/urcu/ht' into urcu/ht
Conflicts:
urcu-ht.h
Mathieu Desnoyers [Wed, 6 Jul 2011 01:00:42 +0000 (21:00 -0400)]
rcu lf hash table runtime fixes
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Tue, 5 Jul 2011 23:35:08 +0000 (19:35 -0400)]
split-ordered hash table
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Sat, 2 Jul 2011 15:31:09 +0000 (11:31 -0400)]
Rename urcu-ht to rculfhash
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Sat, 2 Jul 2011 15:24:18 +0000 (11:24 -0400)]
Merge branch 'master' into urcu/ht
Conflicts:
Makefile.inc
tests/Makefile.inc
urcu-defer.h
Mathieu Desnoyers [Fri, 1 Jul 2011 23:51:48 +0000 (19:51 -0400)]
rculfqueue: provide locklessness by allowing multiple dummy nodes
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Fri, 1 Jul 2011 22:50:15 +0000 (18:50 -0400)]
rcu lfqueue: make dequeue lockless by helping out other dequeuers
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Fri, 1 Jul 2011 21:42:48 +0000 (17:42 -0400)]
rculfqueue: Document dummy pointer value access
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Fri, 1 Jul 2011 21:35:07 +0000 (17:35 -0400)]
rculfqueue: Keep a reference to the current dummy node rather than using low bit
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Fri, 1 Jul 2011 21:24:24 +0000 (17:24 -0400)]
rculfqueue: only one dummy node is needed
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Fri, 1 Jul 2011 21:23:39 +0000 (17:23 -0400)]
rculfstack: update comment
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Fri, 1 Jul 2011 21:06:16 +0000 (17:06 -0400)]
RCU lf queue: Add assert for memory allocation
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Fri, 1 Jul 2011 20:17:55 +0000 (16:17 -0400)]
rculfstack: header implementation should be defined as static inline
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Mathieu Desnoyers [Fri, 1 Jul 2011 20:17:14 +0000 (16:17 -0400)]
wfstack: header implementation should be defined as static inline
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
This page took 0.040751 seconds and 4 git commands to generate.
projects / urcu.git / log
