userspace-rcu.git
13 years agoRemove dead code in _cds_lfht_gc_bucket()
Lai Jiangshan [Thu, 27 Oct 2011 05:07:56 +0000 (07:07 +0200)] 
Remove dead code in _cds_lfht_gc_bucket()

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoMove replace code out from _cds_lfht_add()
Mathieu Desnoyers [Thu, 27 Oct 2011 04:30:49 +0000 (06:30 +0200)] 
Move replace code out from _cds_lfht_add()

Original patch from Lai Jiangshan, reworked significantly to keep the
iterator semantic, where a "next" node is never re-read after being
looked up within a RCU read-side critical section after it has been
validated.

Although strictly speaking the "replace" code re-checks that the next
node is not logically removed with a cmpxchg, I prefer to ensure that
all lookup paths behave similarly. It will make it easier to track
behavior later on if they all follow the same rules.

Reported-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoRename the parameter name of _cds_lfht_replace()
Lai Jiangshan [Mon, 17 Oct 2011 14:40:06 +0000 (10:40 -0400)] 
Rename the parameter name of _cds_lfht_replace()

Although _cds_lfht_replace() is not a plublic API,
but a proper name will help for reading or maintainance.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoFix dummy node insertion bug
Lai Jiangshan [Mon, 17 Oct 2011 14:34:36 +0000 (10:34 -0400)] 
Fix dummy node insertion bug

dummy node is the first node of the identical-hash-value chain

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agocompare hash value before call compare_fct()
Lai Jiangshan [Mon, 17 Oct 2011 14:26:58 +0000 (10:26 -0400)] 
compare hash value before call compare_fct()

[ Edit by Mathieu Desnoyers:

  This is an optimisation that checks if the reverse hash value is
  equal before calling the comparison function. Given comparing a
  reverse hash is much faster than comparison, this accelarates the
  lookups and add. ]

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: Simplify lookup_bucket()
Lai Jiangshan [Mon, 17 Oct 2011 14:19:10 +0000 (10:19 -0400)] 
rculfhash: Simplify lookup_bucket()

They are the same, but I don't think the compiler can optimize it.

And it also helps for understanding the following code.

[ Edit by Mathieu Desnoyers:
  - Add a comment that describes the equivalence between get_count_order
    and fls for this lookup of index + 1. ]

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: avoid unneed garbage collect
Lai Jiangshan [Mon, 17 Oct 2011 14:10:27 +0000 (10:10 -0400)] 
rculfhash: avoid unneed garbage collect

[ Edit by Mathieu Desnoyers:

If we have a concurrent removal executing while the add is performed,
I just want to ensure we agree that this scenario will be correct:

1) removal succeeds. We have flagged
   a node as "logically removed", but
   it is still in the linked list.

2) garbage collection is initiated.

                                        3) add succeeds. We insert a
                                           node with reverse hash value
                                           higher than the logically
                                           removed node. This means the
                                           add takes care of garbage
                                           collecting the logically
                                           removed node prior to adding
                                           the new node.

4) garbage collection of logically
   removed node fails
   (we ignore the return value of
    (void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next);)
   retry and iterate until we find the reverse
   hash value higher than the logically
   remove node.

So I think this is OK: given that the add path takes care of garbage
collecting any logically removed node located prior to the insert
position, we don't need to perform gargage collection after the
insertion. ]

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: merge duplicated code for bucket lookup
Lai Jiangshan [Mon, 17 Oct 2011 13:46:10 +0000 (09:46 -0400)] 
rculfhash: merge duplicated code for bucket lookup

[ Edit by Mathieu Desnoyers: also remove unnecessary lookups that end up
  returning an already looked up node. Same behavior is guaranteed
  because the hash and size stay invariant across retry. ]

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: make struct rcu_level size power of 2
Lai Jiangshan [Mon, 17 Oct 2011 13:32:00 +0000 (09:32 -0400)] 
rculfhash: make struct rcu_level size power of 2

By adding a small slowpath overhead (added synchronize_rcu call in the
last iteration of the resize), we can reduce the amount of wasted memory
for memory allocators that allocate power of two memory areas. This is
achieved by removing the call_rcu head from struct rcu_level.

[ Edit by Mathieu Desnoyers:
  - add comment about need to manually update the allocation size of
    fields are added to struct rcu_level.
  - create a more explanatory title and changelog. ]

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoReinsert missing test_urcu_*.c files (missing in rename)
Mathieu Desnoyers [Sat, 15 Oct 2011 14:08:46 +0000 (09:08 -0500)] 
Reinsert missing test_urcu_*.c files (missing in rename)

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoReinsert missing test_urcu_*.c files (missing in rename)
Mathieu Desnoyers [Sat, 15 Oct 2011 14:08:46 +0000 (09:08 -0500)] 
Reinsert missing test_urcu_*.c files (missing in rename)

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: simplify get_count_order()
Lai Jiangshan [Fri, 14 Oct 2011 14:59:42 +0000 (09:59 -0500)] 
rculfhash: simplify get_count_order()

[ Edit by Mathieu Desnoyers:

- Updated comments.
- Quick benchmark on Intel(R) Atom(TM) CPU Z520   @ 1.33GHz:

get_count_order_ulong, from 0 to 100000000:

previous:  3.840s
new:       3.187s

- Test comparing bit-exactness for ranges near 0:

/*
 * fls: returns the position of the most significant bit.
 * Returns 0 if no bit is set, else returns the position of the most
 * significant bit (from 1 to 32 on 32-bit, from 1 to 64 on 64-bit).
 */
static inline
unsigned int fls_u32(uint32_t x)
{
int r;

asm("bsrl %1,%0\n\t"
    "jnz 1f\n\t"
    "movl $-1,%0\n\t"
    "1:\n\t"
    : "=r" (r) : "rm" (x));
return r + 1;
}

static inline
unsigned int fls_u64(uint64_t x)
{
long r;

asm("bsrq %1,%0\n\t"
    "jnz 1f\n\t"
    "movq $-1,%0\n\t"
    "1:\n\t"
    : "=r" (r) : "rm" (x));
return r + 1;
}

static __attribute__((unused))
unsigned int fls_u64(uint64_t x)
{
unsigned int r = 64;

if (!x)
return 0;

if (!(x & 0xFFFFFFFF00000000ULL)) {
x <<= 32;
r -= 32;
}
if (!(x & 0xFFFF000000000000ULL)) {
x <<= 16;
r -= 16;
}
if (!(x & 0xFF00000000000000ULL)) {
x <<= 8;
r -= 8;
}
if (!(x & 0xF000000000000000ULL)) {
x <<= 4;
r -= 4;
}
if (!(x & 0xC000000000000000ULL)) {
x <<= 2;
r -= 2;
}
if (!(x & 0x8000000000000000ULL)) {
x <<= 1;
r -= 1;
}
return r;
}

static __attribute__((unused))
unsigned int fls_u32(uint32_t x)
{
unsigned int r = 32;

if (!x)
return 0;
if (!(x & 0xFFFF0000U)) {
x <<= 16;
r -= 16;
}
if (!(x & 0xFF000000U)) {
x <<= 8;
r -= 8;
}
if (!(x & 0xF0000000U)) {
x <<= 4;
r -= 4;
}
if (!(x & 0xC0000000U)) {
x <<= 2;
r -= 2;
}
if (!(x & 0x80000000U)) {
x <<= 1;
r -= 1;
}
return r;
}

unsigned int fls_ulong(unsigned long x)
{
return fls_u32(x);
return fls_u64(x);
}

int get_count_order_u32(uint32_t x)
{
int order;

order = fls_u32(x) - 1;
if (x & (x - 1))
order++;
return order;
}

int get_count_order_ulong(unsigned long x)
{
int order;

order = fls_ulong(x) - 1;
if (x & (x - 1))
order++;
return order;
}

int test_get_count_order_u32(uint32_t x)
{
if (!x)
return -1;
return fls_u32(x - 1);
}

/* find the minimum order that x <= (1UL << order) */
int test_get_count_order_ulong(unsigned long x)
{
if (!x)
return -1;
return fls_ulong(x - 1);
}

int main(int argc, char **argv)
{
unsigned long i;

for (i = 0UL; i < 10000; i++) {
if (get_count_order_ulong(i) != test_get_count_order_ulong(i))
printf("Error for %lu\n", i);
}

for (i = 4294967293UL; i != 0; i++) {
if (get_count_order_ulong(i) != test_get_count_order_ulong(i))
printf("Error for %lu\n", i);
}

return 0;
}

]

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: use dbg_printf() for grow/shrink printout
Lai Jiangshan [Fri, 14 Oct 2011 14:14:04 +0000 (09:14 -0500)] 
rculfhash: use dbg_printf() for grow/shrink printout

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: merge thread_id into struct partition_resize_work
Lai Jiangshan [Fri, 14 Oct 2011 13:56:54 +0000 (08:56 -0500)] 
rculfhash: merge thread_id into struct partition_resize_work

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: remove unused rcu_head in partition_resize_work
Lai Jiangshan [Fri, 14 Oct 2011 13:55:16 +0000 (08:55 -0500)] 
rculfhash: remove unused rcu_head in partition_resize_work

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorename test_qsbr to test_urcu_qsbr
Lai Jiangshan [Fri, 14 Oct 2011 13:46:30 +0000 (08:46 -0500)] 
rename test_qsbr to test_urcu_qsbr

[ edit by Mathieu Desnoyers: update runtests*.sh scripts accordingly ]

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash test: handle write return value
Mathieu Desnoyers [Wed, 5 Oct 2011 02:42:29 +0000 (22:42 -0400)] 
rculfhash test: handle write return value

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorcuhash test: fix 32-bit type warning
Mathieu Desnoyers [Wed, 5 Oct 2011 02:34:10 +0000 (22:34 -0400)] 
rcuhash test: fix 32-bit type warning

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoMerge branch 'master' into urcu/ht-shrink
Mathieu Desnoyers [Wed, 5 Oct 2011 02:07:32 +0000 (22:07 -0400)] 
Merge branch 'master' into urcu/ht-shrink

13 years agourcu-pointer: fix rcu_set_pointer unset return value
Mathieu Desnoyers [Wed, 5 Oct 2011 02:01:50 +0000 (22:01 -0400)] 
urcu-pointer: fix rcu_set_pointer unset return value

The problem only affected non-_LGPL_SOURCE configs.

Reported-by: Stephen Hemminger <shemminger@vyatta.com>
Fix-proposed-by: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoMerge branch 'master' into urcu/ht-shrink
Mathieu Desnoyers [Sun, 2 Oct 2011 16:56:36 +0000 (12:56 -0400)] 
Merge branch 'master' into urcu/ht-shrink

Conflicts:
urcu-call-rcu.h

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoEnhance API.txt documentation, add to Makefile as EXTRA_DIST
Mathieu Desnoyers [Sun, 2 Oct 2011 16:53:44 +0000 (12:53 -0400)] 
Enhance API.txt documentation, add to Makefile as EXTRA_DIST

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: do not sample in_progress_destroy in the middle of a level
Mathieu Desnoyers [Fri, 30 Sep 2011 17:37:07 +0000 (13:37 -0400)] 
rculfhash: do not sample in_progress_destroy in the middle of a level

Caused destroy assert/segfaults.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: break resize loop on destroy
Mathieu Desnoyers [Fri, 30 Sep 2011 16:59:33 +0000 (12:59 -0400)] 
rculfhash: break resize loop on destroy

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: decrement resize cnt on destroy
Mathieu Desnoyers [Fri, 30 Sep 2011 16:50:11 +0000 (12:50 -0400)] 
rculfhash: decrement resize cnt on destroy

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoCheck for in progress destroy before calling call_rcu thread
Mathieu Desnoyers [Fri, 30 Sep 2011 16:45:23 +0000 (12:45 -0400)] 
Check for in progress destroy before calling call_rcu thread

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: Test for initiated destroy before performing resize
Mathieu Desnoyers [Fri, 30 Sep 2011 16:23:05 +0000 (12:23 -0400)] 
rculfhash: Test for initiated destroy before performing resize

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoVersion 0.6.5 v0.6.5
Mathieu Desnoyers [Thu, 29 Sep 2011 22:15:42 +0000 (18:15 -0400)] 
Version 0.6.5

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agocall_rcu: Document call_rcu requirements
Mathieu Desnoyers [Thu, 29 Sep 2011 21:40:01 +0000 (17:40 -0400)] 
call_rcu: Document call_rcu requirements

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agocall_rcu: Document call_rcu requirements
Mathieu Desnoyers [Thu, 29 Sep 2011 21:40:01 +0000 (17:40 -0400)] 
call_rcu: Document call_rcu requirements

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoMerge branch 'master' into urcu/ht-shrink
Mathieu Desnoyers [Thu, 29 Sep 2011 21:17:41 +0000 (17:17 -0400)] 
Merge branch 'master' into urcu/ht-shrink

13 years agocall_rcu: fix error handling of malloc error
Mathieu Desnoyers [Thu, 29 Sep 2011 21:17:05 +0000 (17:17 -0400)] 
call_rcu: fix error handling of malloc error

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

13 years agourcu call_rcu: Use RCU read-side protection for per-cpu call_rcu data
Mathieu Desnoyers [Thu, 29 Sep 2011 21:13:48 +0000 (17:13 -0400)] 
urcu call_rcu: Use RCU read-side protection for per-cpu call_rcu data

A concurrent get_cpu_call_rcu_data(), called by get_call_rcu_data(),
could dereference this pointer without holding any mutex. So this
situation would happen if we have a concurrent call_rcu() executing
while we do the create_all_cpu_call_rcu_data().

I think we would need to put a rcu_dereference() around
per_cpu_call_rcu_data read within get_cpu_call_rcu_data() too.
per_cpu_call_rcu_data should be done with rcu_set_pointer.

Also, a rcu read-side critical section would be required around any
usage of per_cpu_call_rcu_data, and the action of tearing down the
per-cpu data would require to wait for a quiescent state. So we would
basically require that the call_rcu users need to be registered as
RCU reader threads.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agourcu,call_rcu: Cleanup call_rcu_data pointers before use in child
Lai Jiangshan [Thu, 29 Sep 2011 19:56:43 +0000 (15:56 -0400)] 
urcu,call_rcu: Cleanup call_rcu_data pointers before use in child

[ Edit by Mathieu Desnoyers: create maxcpus_reset to handle cases where
  maxcpus is 0 and -1, depending on the configuration. ]

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agourcu,call_rcu: avoid create call_rcu_data for child when unneed
Lai Jiangshan [Thu, 29 Sep 2011 17:55:11 +0000 (13:55 -0400)] 
urcu,call_rcu: avoid create call_rcu_data for child when unneed

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Reviewed-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agourcu,defer_rcu: Make defer_rcu encoding more compact for marker
Lai Jiangshan [Thu, 29 Sep 2011 17:47:13 +0000 (13:47 -0400)] 
urcu,defer_rcu: Make defer_rcu encoding more compact for marker

When the function changes (and the function is aligned), and only the
data is the marker, we can get away with using only 2 pointers rather
than 3.

[ Edit by Mathieu Desnoyers: patch cleanup, changelog updates ]

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agourcu_defer: Use cancellation flag instead of pthread_cancel()
Mathieu Desnoyers [Thu, 29 Sep 2011 17:28:04 +0000 (13:28 -0400)] 
urcu_defer: Use cancellation flag instead of pthread_cancel()

- Provides better control over cancellation point location.
- Set the futex to 0 before exiting the defer thread.

This patch combines and enhances patches from Lai Jiangshan:
  urcu,defer_rcu: fix missing respond to a cancellation request
  urcu,defer_rcu: Avoid thread exit unexpected

Reported-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agourcu,call_rcu: protects call_rcu_data_list when remove node
Lai Jiangshan [Thu, 29 Sep 2011 17:04:12 +0000 (13:04 -0400)] 
urcu,call_rcu: protects call_rcu_data_list when remove node

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoMerge branch 'master' into urcu/ht-shrink
Mathieu Desnoyers [Wed, 28 Sep 2011 20:03:40 +0000 (16:03 -0400)] 
Merge branch 'master' into urcu/ht-shrink

13 years agoCreate default call rcu data upon per-cpu call-rcu teardown
Mathieu Desnoyers [Wed, 28 Sep 2011 20:03:13 +0000 (16:03 -0400)] 
Create default call rcu data upon per-cpu call-rcu teardown

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash test: fix 32-bit hash
Mathieu Desnoyers [Wed, 28 Sep 2011 17:46:23 +0000 (13:46 -0400)] 
rculfhash test: fix 32-bit hash

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash test: Use get first/get next to delete all entries
Mathieu Desnoyers [Wed, 28 Sep 2011 03:27:17 +0000 (23:27 -0400)] 
rculfhash test: Use get first/get next to delete all entries

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: fix get first / get next iterator
Mathieu Desnoyers [Wed, 28 Sep 2011 03:27:02 +0000 (23:27 -0400)] 
rculfhash: fix get first / get next iterator

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoFix handling of systems without sysconf nr possible cpu support
Mathieu Desnoyers [Wed, 28 Sep 2011 00:01:51 +0000 (20:01 -0400)] 
Fix handling of systems without sysconf nr possible cpu support

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash needs local config.h
Mathieu Desnoyers [Tue, 27 Sep 2011 23:54:08 +0000 (19:54 -0400)] 
rculfhash needs local config.h

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: update header documentation
Mathieu Desnoyers [Tue, 27 Sep 2011 21:47:35 +0000 (17:47 -0400)] 
rculfhash: update header documentation

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash test: move init node outside of rcu read-side c.s. (unneeded protection)
Mathieu Desnoyers [Tue, 27 Sep 2011 21:39:30 +0000 (17:39 -0400)] 
rculfhash test: move init node outside of rcu read-side c.s. (unneeded protection)

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoAdd cds_lfht_first/cds_lfht_next for hash table iteration
Mathieu Desnoyers [Tue, 27 Sep 2011 21:24:55 +0000 (17:24 -0400)] 
Add cds_lfht_first/cds_lfht_next for hash table iteration

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: rename _next into _next_duplicate
Mathieu Desnoyers [Tue, 27 Sep 2011 18:45:41 +0000 (14:45 -0400)] 
rculfhash: rename _next into _next_duplicate

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: document use of caa_container_of()
Mathieu Desnoyers [Tue, 27 Sep 2011 15:19:21 +0000 (11:19 -0400)] 
rculfhash: document use of caa_container_of()

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: cleanup includes
Mathieu Desnoyers [Mon, 26 Sep 2011 18:48:30 +0000 (14:48 -0400)] 
rculfhash: cleanup includes

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoMerge branch 'master' into urcu/ht-shrink
Mathieu Desnoyers [Thu, 22 Sep 2011 15:01:54 +0000 (11:01 -0400)] 
Merge branch 'master' into urcu/ht-shrink

13 years agopowerpc: use __NO_LWSYNC__ check to use appropriate lwsync/sync opcode
Mathieu Desnoyers [Thu, 22 Sep 2011 15:00:14 +0000 (11:00 -0400)] 
powerpc: use __NO_LWSYNC__ check to use appropriate lwsync/sync opcode

We already used it in uatomic code, move it to arch ppc.

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

13 years agocmm: provide lightweight smp_rmb/smp_wmb on PPC
Paolo Bonzini [Thu, 22 Sep 2011 09:12:44 +0000 (05:12 -0400)] 
cmm: provide lightweight smp_rmb/smp_wmb on PPC

lwsync orders loads in cacheable memory with respect to other loads,
and stores in cacheable memory with respect to other stores.  Use it
to implement smp_rmb/smp_wmb.

The heavy-weight sync is still used for the "full" rmb/wmb operations,
as well as for smp_mb.

[ Edit by Mathieu Desnoyers: rephrased the comments around the memory
  barriers. ]

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: factor out add_replace and replace
Mathieu Desnoyers [Thu, 22 Sep 2011 09:03:36 +0000 (05:03 -0400)] 
rculfhash: factor out add_replace and replace

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoatomic: provide seq_cst semantics on powerpc
Mathieu Desnoyers [Thu, 22 Sep 2011 00:25:20 +0000 (20:25 -0400)] 
atomic: provide seq_cst semantics on powerpc

We provide sequential consistency semantic over all architectures for
cmpxchg and add_return family of primitives, but the powerpc
implementation does not match that.

Change the isync after the atomic primitives to sync, and explain the
scheme.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash tests: make node count RCU aware
Mathieu Desnoyers [Wed, 21 Sep 2011 17:59:31 +0000 (13:59 -0400)] 
rculfhash tests: make node count RCU aware

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: set next to NULL when node is NULL
Mathieu Desnoyers [Wed, 21 Sep 2011 17:59:09 +0000 (13:59 -0400)] 
rculfhash: set next to NULL when node is NULL

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: approximation can be negative
Mathieu Desnoyers [Wed, 21 Sep 2011 14:50:58 +0000 (10:50 -0400)] 
rculfhash: approximation can be negative

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: min size only needed on shrink, take nr cpus into account
Mathieu Desnoyers [Wed, 21 Sep 2011 14:33:28 +0000 (10:33 -0400)] 
rculfhash: min size only needed on shrink, take nr cpus into account

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: type the ht count approx as long
Mathieu Desnoyers [Wed, 21 Sep 2011 14:22:39 +0000 (10:22 -0400)] 
rculfhash: type the ht count approx as long

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: handle small and negative table size approximation
Mathieu Desnoyers [Wed, 21 Sep 2011 14:21:21 +0000 (10:21 -0400)] 
rculfhash: handle small and negative table size approximation

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: fix node approx counting
Mathieu Desnoyers [Wed, 21 Sep 2011 13:48:05 +0000 (09:48 -0400)] 
rculfhash: fix node approx counting

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: output approximation of number of nodes in counting
Mathieu Desnoyers [Wed, 21 Sep 2011 13:24:17 +0000 (09:24 -0400)] 
rculfhash: output approximation of number of nodes in counting

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash cleanup: count percpu deletes in the positive range
Mathieu Desnoyers [Wed, 21 Sep 2011 12:44:49 +0000 (08:44 -0400)] 
rculfhash cleanup: count percpu deletes in the positive range

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: node alignment is back to 4 bytes
Mathieu Desnoyers [Wed, 21 Sep 2011 05:11:05 +0000 (01:11 -0400)] 
rculfhash: node alignment is back to 4 bytes

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: remove now unneeded gc flag (combine with removed)
Mathieu Desnoyers [Wed, 21 Sep 2011 04:45:11 +0000 (00:45 -0400)] 
rculfhash: remove now unneeded gc flag (combine with removed)

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: implement lock-free replacement
Mathieu Desnoyers [Wed, 21 Sep 2011 04:40:38 +0000 (00:40 -0400)] 
rculfhash: implement lock-free replacement

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: support replacement operation
Mathieu Desnoyers [Wed, 21 Sep 2011 03:05:08 +0000 (23:05 -0400)] 
rculfhash: support replacement operation

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: API rename: remove -> del
Mathieu Desnoyers [Tue, 20 Sep 2011 23:34:49 +0000 (19:34 -0400)] 
rculfhash: API rename: remove -> del

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: spawn only number of threads required for resize
Mathieu Desnoyers [Tue, 20 Sep 2011 21:50:58 +0000 (17:50 -0400)] 
rculfhash: spawn only number of threads required for resize

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: parallelize resize
Mathieu Desnoyers [Tue, 20 Sep 2011 20:46:22 +0000 (16:46 -0400)] 
rculfhash: parallelize resize

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: document flags
Mathieu Desnoyers [Mon, 19 Sep 2011 20:22:49 +0000 (16:22 -0400)] 
rculfhash: document flags

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: comment file inclusion order
Mathieu Desnoyers [Mon, 19 Sep 2011 20:12:43 +0000 (16:12 -0400)] 
rculfhash: comment file inclusion order

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: simplify lfht_new API with inline wrapper
Mathieu Desnoyers [Mon, 19 Sep 2011 20:07:18 +0000 (16:07 -0400)] 
rculfhash: simplify lfht_new API with inline wrapper

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: add TODO for resize worker threads urcu/ht-shrink-help
Mathieu Desnoyers [Mon, 19 Sep 2011 17:27:08 +0000 (13:27 -0400)] 
rculfhash: add TODO for resize worker threads

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: Remove leftover assertions
Mathieu Desnoyers [Mon, 19 Sep 2011 16:57:12 +0000 (12:57 -0400)] 
rculfhash: Remove leftover assertions

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: merge table hash and link stages into populate
Mathieu Desnoyers [Mon, 19 Sep 2011 16:56:04 +0000 (12:56 -0400)] 
rculfhash: merge table hash and link stages into populate

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoMerge branch 'urcu/ht-shrink-help' into urcu/ht-shrink
Mathieu Desnoyers [Mon, 19 Sep 2011 16:49:23 +0000 (12:49 -0400)] 
Merge branch 'urcu/ht-shrink-help' into urcu/ht-shrink

13 years agorculfhash: remove helper scheme
Mathieu Desnoyers [Mon, 19 Sep 2011 16:45:26 +0000 (12:45 -0400)] 
rculfhash: remove helper scheme

There is a trade-off to consider here:
- The helper scheme would require the helpers to allocate the memory for
  dummy nodes themself for correctness (the current implementation is
  buggy because lookups consider an half-linked dummy node to be ready for
  use), which does not work with a cache-efficient per-level array of
  dummy nodes.
- We want cache-efficiency, so we want to keep the per-level array
  allocation.

Therefore, letting insert/removal/lookups help expand is not the way to
go here. This patch removes the helping scheme.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoavoid leaking crdp for failed path
Lai Jiangshan [Thu, 15 Sep 2011 15:24:03 +0000 (11:24 -0400)] 
avoid leaking crdp for failed path

[ Comment: now that set_cpu_call_rcu_data() is not racy and detects
  overwrites, we can effectively trust its return value and free the
  crdp if already set. ]

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoReturn -EEXIST when the old cpu call_rcu_data has not been removed
Lai Jiangshan [Thu, 15 Sep 2011 15:22:03 +0000 (11:22 -0400)] 
Return -EEXIST when the old cpu call_rcu_data has not been removed

To make it matches the comments.

It is the caller's responsibility to use
set_cpu_call_rcu_data(cpu, NULL) to remove the CPU's
call_rcu_data structure and dispose it.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoprotect writing to per_cpu_call_rcu_data[*]
Lai Jiangshan [Thu, 15 Sep 2011 15:20:29 +0000 (11:20 -0400)] 
protect writing to per_cpu_call_rcu_data[*]

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agowake up default call_rcu thread after we move the leftover callbacks
Lai Jiangshan [Thu, 15 Sep 2011 15:19:12 +0000 (11:19 -0400)] 
wake up default call_rcu thread after we move the leftover callbacks

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoavoid memory leak in call_rcu_data_free()
Lai Jiangshan [Thu, 15 Sep 2011 15:17:41 +0000 (11:17 -0400)] 
avoid memory leak in call_rcu_data_free()

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agourcu call_rcu: fix use after free()
Lai Jiangshan [Thu, 15 Sep 2011 15:14:43 +0000 (11:14 -0400)] 
urcu call_rcu: fix use after free()

call_rcu_after_fork_child() needs to use cds_list_for_each_entry_safe to
safely iterate on the list as its item is being freed.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agouse get_cpu_call_rcu_data() for get_call_rcu_data()
Lai Jiangshan [Thu, 15 Sep 2011 15:10:31 +0000 (11:10 -0400)] 
use get_cpu_call_rcu_data() for get_call_rcu_data()

[ Impact: refactor duplicated code ]

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoinit maxcpus before use
Lai Jiangshan [Thu, 15 Sep 2011 15:01:38 +0000 (11:01 -0400)] 
init maxcpus before use

[ Edit:
  Covers the per-cpu call_rcu data setup (not all_cpus helper, which is
  why we did not trigger it in our tests. ]

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agocall_rcu implementation: add missing static
Lai Jiangshan [Thu, 15 Sep 2011 14:56:56 +0000 (10:56 -0400)] 
call_rcu implementation: add missing static

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agocall_rcu implementation: add missing static
Lai Jiangshan [Thu, 15 Sep 2011 14:56:56 +0000 (10:56 -0400)] 
call_rcu implementation: add missing static

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoDocument QSBR interaction with mutexes
Mathieu Desnoyers [Thu, 15 Sep 2011 14:04:30 +0000 (10:04 -0400)] 
Document QSBR interaction with mutexes

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoDocument QSBR interaction with mutexes
Mathieu Desnoyers [Thu, 15 Sep 2011 14:04:30 +0000 (10:04 -0400)] 
Document QSBR interaction with mutexes

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash test: exit upon failure
Mathieu Desnoyers [Thu, 15 Sep 2011 10:41:46 +0000 (06:41 -0400)] 
rculfhash test: exit upon failure

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash: fix add_unique node counting
Mathieu Desnoyers [Thu, 15 Sep 2011 10:29:31 +0000 (06:29 -0400)] 
rculfhash: fix add_unique node counting

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash test: cast rand_r return value directly
Mathieu Desnoyers [Wed, 14 Sep 2011 21:24:00 +0000 (17:24 -0400)] 
rculfhash test: cast rand_r return value directly

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash test: add verbosity
Mathieu Desnoyers [Wed, 14 Sep 2011 21:19:07 +0000 (17:19 -0400)] 
rculfhash test: add verbosity

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agorculfhash test: allow different size for lookup, write, init
Mathieu Desnoyers [Wed, 14 Sep 2011 18:27:48 +0000 (14:27 -0400)] 
rculfhash test: allow different size for lookup, write, init

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
13 years agoqsbr vs call_rcu : remove exit assertion
Mathieu Desnoyers [Wed, 14 Sep 2011 17:36:12 +0000 (13:36 -0400)] 
qsbr vs call_rcu : remove exit assertion

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
This page took 0.049232 seconds and 4 git commands to generate.