* 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. > > - if it returns a different node than the one received as parameter, it > failed, and thus means that it only performed a lookup, so there is no > guarantee that a memory barrier has been executed. > > > > > > cds_lfht_add_replace(): Ditto. > > > > cds_lfht_replace(): Ditto. > > > > cds_lfht_del(): Ditto. One more point: "del" is similar to add_unique: if it succeeds, we execute a full memory barrier. If it fails, no memory barrier is guaranteed. But if we want to make the guarantees relax, we might not want to guarantee that a memory barrier is present in any of the "del" cases. In the end, the only primitives for which I think it really makes sense to provide memory barrier semantic is the add_replace and replace : they actually act as an higher-level "cmpxchg" over the hash table nodes. Thoughts ? Thanks, Mathieu > > Yep, makes sense. > > I'll add this documentation in the API. > > Thanks! > > Mathieu > > > > > cds_lfht_is_node_deleted(): Not an update (let alone an atomic update), > > no barriers. > > > > cds_lfht_resize(): Atomic update, but no return value, so no barrier > > implied. > > > > cds_lfht_for_each(): Not an update (let alone an atomic update), > > no barriers. > > > > cds_lfht_for_each_duplicate(): Ditto. > > > > cds_lfht_for_each_entry(): Ditto. > > > > cds_lfht_for_each_entry_duplicate(): Ditto. > > > > Thanx, Paul > > > > > I'm personally getting confident that the hash table API is clean > > > enough, and the implementation well tested, but I'd like to have your > > > thoughts on the readiness of the hash table for production use. > > > > > > Thanks, > > > > > > Mathieu > > > > > > -- > > > Mathieu Desnoyers > > > Operating System Efficiency R&D Consultant > > > EfficiOS Inc. > > > http://www.efficios.com > > > > > > _______________________________________________ > > > rp mailing list > > > r...@svcs.cs.pdx.edu > > > http://svcs.cs.pdx.edu/mailman/listinfo/rp > > > > > > > > > _______________________________________________ > > lttng-dev mailing list > > lttng-dev@lists.lttng.org > > http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev > > -- > Mathieu Desnoyers > Operating System Efficiency R&D Consultant > EfficiOS Inc. > http://www.efficios.com > > _______________________________________________ > lttng-dev mailing list > lttng-dev@lists.lttng.org > http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev -- Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com _______________________________________________ lttng-dev mailing list lttng-dev@lists.lttng.org http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev