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

[Mathieu Desnoyers]

* Mathieu Desnoyers (mathieu.desnoyers at efficios.com) wrote:
[...]
> Now, I'm thinking slightly further about the success cases of add,
> add_unique and del.
> 
> Typically, when giving a node to add or add_unique for population into
> the hash table, we have to order the writes that initialize the node
> before its insertion into the hash table. So I think it would make sense
> to guarantee that we provide a memory barrier prior to add and
> add_unique (success) operations.
> 
> For the "del" case, it's the other way around: if a deletion succeeds,
> we want to have a memory barrier between the removal flag write and the
> following "free()" of the element. So we need to ensure that there is a
> memory barrier after a successful deletion.
> 
> If we think about it, the "add_replace" acts both as an "add" and "del":
> in all cases, we need to have a memory barrier before the add_replace,
> because we need to order the node initialization before the atomic
> insertion into the hash table, and we also need a memory barrier after,
> but only really in the case where add_replace replaced an old node, thus
> acting as a delete of that old node.
> 
> Considering all this, the barrier semantic I'm proposing is:
> 

One small modification I'm thinking about: changing every "full memory
barrier" below for a "write memory barrier".

All we really need to order are writes cs writes, right ?

I'm concerned that if we publish an API providing memory ordering
semantics guarantees stricter than required, we will never be able to
optimize further if we ever need to relax the barriers in the
implementation, because users will assume that the full barriers are in
place.

Thoughts ?

Thanks,

Mathieu

> add:
> - full memory barrier before the insertion.
> 
> add_unique:
> - success: full memory barrier before the insertion.
> - failure: no memory barrier.
> 
> replace:
> - success: full memory barrier before the insertion, and after the
>   removal of the old node.
> - failure: no memory barrier.
> 
> add_replace:
> - returns an old node (replace): full memory barrier before the
>   insertion, and after the removal of the old node.
> - returns NULL (add): full memory barrier before the insertion.
> 
> del:
> - success: full memory barrier after the removal.
> - failure: no memory barrier.
> 
> I think those are the minimal barriers we need to provide to ensure that
> users will not have to add barriers of their own to use the API.
> 
> Thoughts ?
> 
> Thanks,
> 
> Mathieu
> 
> 
> > 
> > 							Thanx, Paul
> > 
> > > Thanks,
> > > 
> > > Mathieu
> > > 
> > > 
> > > > 
> > > > 							Thanx, Paul
> > > > 
> > > > > 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
> > > > > > > > rp at svcs.cs.pdx.edu
> > > > > > > > http://svcs.cs.pdx.edu/mailman/listinfo/rp
> > > > > > > > 
> > > > > > > 
> > > > > > > 
> > > > > > > _______________________________________________
> > > > > > > lttng-dev mailing list
> > > > > > > lttng-dev at 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 at 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
> > > > > 
> > > > > _______________________________________________
> > > > > rp mailing list
> > > > > rp at svcs.cs.pdx.edu
> > > > > http://svcs.cs.pdx.edu/mailman/listinfo/rp
> > > > > 
> > > > 
> > > 
> > > -- 
> > > 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
> > > 
> > 
> > 
> > _______________________________________________
> > lttng-dev mailing list
> > lttng-dev at 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

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com