On Wed, May 02, 2012 at 12:16:39AM -0400, Mathieu Desnoyers wrote:
* Paul E. McKenney (paul...@linux.vnet.ibm.com) wrote:
On Tue, May 01, 2012 at 05:02:06PM -0400, Mathieu Desnoyers wrote:
* Paul E. McKenney (paul...@linux.vnet.ibm.com) wrote:
On Tue, May 01, 2012 at 01:41:36PM -0400, Mathieu Desnoyers wrote:
* Paul E. McKenney (paul...@linux.vnet.ibm.com) wrote:
On Tue, May 01, 2012 at 11:21:44AM -0400, Mathieu Desnoyers wrote:
* Mathieu Desnoyers (mathieu.desnoy...@efficios.com) wrote:
* Paul E. McKenney (paul...@linux.vnet.ibm.com) wrote:
On Tue, May 01, 2012 at 10:16:09AM -0400, Mathieu Desnoyers
wrote:
Hi!
After 1 year of development, with the last 6-7 months spent
polishing
the API and testing the implementation, I think it is
getting about time
to release the RCU lock-free hash table in a new Userspace
RCU version
(0.7).
I recently described the guarantees provided by the hash
table in more
detail, and created tests for the uniqueness guarantee for
traversals
performed concurrently with add_unique and add_replace
operations. I
also added test modes that create long hash chains, to test
corner-cases
of the hash table.
One small thing I wonder is whether we should document that
the hash
table update operations imply full memory barriers ?
The Linux kernel's rule seems good here -- if a hash-table
operation is
atomic and returns a value, it should imply a full barrier.
So:
cds_lfht_new(): No point in claiming barriers -- publishing
the
pointer to the hash table is where the barriers are
important.
cds_lfht_destroy(): Ditto.
cds_lfht_lookup(): Not an update (let alone an atomic
update), no barriers.
cds_lfht_next_duplicate(): Ditto.
cds_lfht_first(): Ditto.
cds_lfht_next(): Ditto.
cds_lfht_add(): Atomic update, but no return value, so no
barrier
implied.
Yep, makes sense. We use cmpxchg internally to perform the
update, but
it could make sense to eventually use a cmpxchg that has no
memory
barriers to perform this update. So I agree on not providing a
memory
barrier guarantee on the add operation, since it does not
return any
value.
cds_lfht_add_unique(): Atomic update that returns a value, so
should
imply a full memory barrier.
add_unique is a bit special:
- if it returns the node received as parameter, it means the add
succeeded, which imply an update, and thus a memory barrier.
Hrm, thinking further: if we make the add operation not act as a
full memory barrier, then the add_unique success should not act
as a
full mb neither.
Think of it as being similar to the Linux kernel's atomic_inc() and
atomic_add_return() primitives. The latter guarantees memory
barriers
and the former does not.
I think add/add_unique vs atomic_inc/atomic_add_return are
fundamentally
different.
atomic_inc:
- input: increment
- output: none
- effect: increment target address value
atomic_add_return:
- input: increment
- output: incremented value
- effect: increment target address value, atomically reading the
resulting value.
hash table add:
- input: new node to add
- output: none
- effect: atomically add the new node into the table
hash table add_unique (success):
- input: new node to add
- output: (we just return whether the operation has succeeded)
- effect: atomically add the new node into the table
hash table add_unique (failure):
- input: new node to try adding
- output: (we just return whether the operation has succeeded)
- effect: simple lookup (read)
So as we see, the add_unique failure only performs a read. Adding a
memory barrier before this read would require us to add a memory
barrier
also on the success path, which would degrade performance. The success
path does: lookup failure, cmpxchg to add the node, retry if changed.
Adding a memory barrier before the lookup would add an extra memory
barrier in addition to the one located in the cmpxchg, and I don't
think
we want that overhead.
Perhaps a better analogy is cmpxchg() in the Linux kernel. Some
architectures place the memory barrier before
