[lttng-dev] [rp] [RFC] Readiness for URCU release with RCU lock-free hash table

[Paul E. McKenney]

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.

cds_lfht_add_unique(): Atomic update that returns a value, so should
	imply a full memory barrier.

cds_lfht_add_replace(): Ditto.

cds_lfht_replace(): Ditto.

cds_lfht_del(): Ditto.

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
> rp at svcs.cs.pdx.edu
> http://svcs.cs.pdx.edu/mailman/listinfo/rp
>