[lttng-dev] [commit] rculfhash: document linearizability guarantees

[lttng-dev] [commit] rculfhash: document linearizability guarantees

[Mathieu Desnoyers]

* Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> On Wed, Apr 18, 2012 at 04:10:17PM -0400, Mathieu Desnoyers wrote:
> > Hi,
> > 
> > FYI, I pushed extra documentation of the RCU lock-free Hash Table found
> > in userspace RCU library master branch regarding the linearizability
> > guarantees it provides. Feedback is welcome,
> 

Hi Paul,

Your reply brings interesting thoughts, see below,

> Interesting!  Please see below for my take on it.
> 
> 							Thanx, Paul
> 
> > Thanks,
> > 
> > Mathieu
> > 
> > commit 0f5543cb1780acef35878646e6cdc966f1406c18
> > Author: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> > Date:   Wed Apr 18 16:05:29 2012 -0400
> > 
> >     rculfhash: document linearizability guarantees
> >     
> >     Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> > 
> > diff --git a/rculfhash.c b/rculfhash.c
> > index 6f470fd..d22b44d 100644
> > --- a/rculfhash.c
> > +++ b/rculfhash.c
> > @@ -98,6 +98,33 @@
> >   *   hash table nodes. These tables are invariant after they are
> >   *   populated into the hash table.
> >   *
> > + * Linearizability Guarantees:
> 
> I suggest calling these ordering guarantees.  Otherwise, people will
> glance at the heading and assume that the hash table is linearizable,
> which from what I can see is not the case.  (And I do -not- recommend
> making it be the case, just to be sure that there is no confusion.)

Ordering guarantees works for me, but I'm curious to know the reasons
that make you think it's not linearizeable. AFAIU, linearizability
requires:

- That there is an atomic step at which each operation takes place,
  located between the start and the end of each method (linearization
  point).
- Progress guarantees for each method.

So looking at linearization points for updates:

- add: takes place atomically at the cmpxchg that links the new node
  into the linked list.

- add_replace: takes place atomically at the uatomic_cmpxchg responsible
  for linking the new node into the linked list, replacing an existing
  node (add_replace) atomically by setting the "removed" flag into the
  replaced node's next pointer at the same time as the new node is
  inserted.

- add_unique: takes place atomically at the cmpxchg that either
  links the new node into the linked list, or otherwise detects
  that the prev node next pointer has changed, triggering a retry.

- del: takes place atomically by setting the "removed" flag into the
  next pointer of the node to remove (atomic "or").

Linearization points for reads: those seem to apply to individual
operations (e.g. lookup, get_first, get_next, get_next_duplicate):

- lookup: atomically reading the next pointer of the node prior to
  either:
  - the node containing the key we are looking for,
  - the node containing the first key above the key we are looking for,
  - the end of the list (next pointer is NULL).

- get_first: atomically reading the head next pointer.

- get_next: atomically reading the next pointer of the current node.

- get_next_duplicate: atomically reading the next pointer of the
  current node.

Progress guarantees:

Updates:

Each retry faced by an update is always caused by another concurrent
operation that itself progresses (lock-freedom type of progress
guarantee).

Reads:

Read operations never loop: the linked lists only go in one direction,
from the head to the tail.

We have to note that for linearizability, I used the basic read
operations (which happen atomically) rather than sequence of such
operations.

One item I'm not convinced could be called entirely linearizable is the
resize operation: it happens lazily at some point in time that is not
usually within the update operations. For that one, I'd be tempted
to say that the hash table is not linearizable. Thoughts ?

> 
> > + *
> > + * To discuss these guarantees, we first define "read" operations as any
> > + * of the following operations surrounded by an RCU read-side lock/unlock
> > + * pair:
> > + *  - cds_lfht_lookup
> > + *  - cds_lfht_lookup followed by iteration with cds_lfht_next_duplicate
> > + *  - cds_lfht_first followed iteration with cds_lfht_next
> > + *
> > + * We define "write" operations as any of cds_lfht_add,
> > + * cds_lfht_add_unique, cds_lfht_add_replace, cds_lfht_del.
> > + *
> > + * The following guarantees are offered by this hash table:
> > + *
> > + * A) "read" after "write" will always return the result of the latest
> > + *    write.
> 
> Hmmm...  "Latest" by what measure?  What is the guarantee really
> saying if there are a large number of writes and reads all involving
> the same hash key?
> 
> My guess is that the guarantee is actually of the following form:
> If there is ordering between a write and a later read, then the
> read is guaranteed to see the write or some later write.

Yes, although I think thinking in terms of "sequence of reads" might be
more appropriate than "basic read operation". By that, I mean thinking
in terms of iteration over the entire hash table, or iteration over a
key and all its duplicates, rather than the basic lookup/get next/get
next duplicate/get first operations.

> As I understand it, this guarantee requires that the read and write
> operate on the same key.

Well, a sequence of "read" operations can be an iteration on the whole
table (get first, then get_next until we reach the end of the table). So
what I'm trying to say here is that if we have a sequence of read
operations for which the first operation is ordered after a write, those
are guaranteed to see this write or some later write.

Of course, if the sequence of read operations is executed across the
write, it may or may not see the write.

And if the sequence of read operations is known to have its last read
ordered before a write, it is ensured that it will not see this write.

> 
> This might be easier given a guarantee that writes involving a given
> key are seen in order.  I believe that the hash table does provide this
> guarantee and that it would be good to state it explicitly.

I'm wondering if the reasoning about a single "key" you are proposing
takes into account that the hash table supports duplicate keys ?

> 
> > + * B) "write" after "read" will never be returned by the read.
> 
> There is a useful guarantee involving a pair of reads: If a pair
> of reads of a given key are ordered (e.g., by a memory barrier),
> then the second read will return the same value as the first
> read or some later value.

Yep, e.g. if we use add_replace to replace a given node with a version
that has an incremented counter, reads that are ordered with memory
barriers are guaranteed to see this counter always incrementing.

> 
> > + * C) It is guaranteed that after a grace period following a "del" and
> > + *    "replace" operation, no reference to the removed items exists in
> > + *    the hash table.
> 
> I would instead say something like: If a grace period separates a "del"
> or "replace" operation and a subsequent read operation, then that reader
> is guaranteed not to see the removed item.

Your statement is true, but the actual idea I want to convey is stronger
than that: after that grace period, we guarantee that no read nor update
operation can see the removed pointer (even just internally).

> 
> > + * D) Uniqueness guarantee: when using add_unique and/or add_replace to
> > + *    insert nodes into the table, if there was previously one node or
> > + *    less with the same key being inserted by one or more concurrent
> > + *    add_unique and/or add_replace, all concurrent "read" performed on
> > + *    the hash table are guaranteed to find one, and only one node with
> > + *    that key.
> 
> How about: Given a hash table that does not contain duplicate items
> for a given key, there will only be one item in the hash table after
> an arbitrary sequence of add_unique and/or add_replace operations.
> Note, however, that a pair of concurrent read operations might well
> access two different items with that key.

Yes, that works,

Thanks for the feedback!

Mathieu

> 
> >   * Bucket node tables:
> >   *
> >   * hash table	hash table	the last	all bucket node tables
> > 
> > -- 
> > 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

[lttng-dev] [rp] [commit] rculfhash: document linearizability guarantees

[Paul E. McKenney]

On Thu, Apr 19, 2012 at 08:02:57PM -0400, Mathieu Desnoyers wrote:
> * Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> > On Wed, Apr 18, 2012 at 04:10:17PM -0400, Mathieu Desnoyers wrote:
> > > Hi,
> > > 
> > > FYI, I pushed extra documentation of the RCU lock-free Hash Table found
> > > in userspace RCU library master branch regarding the linearizability
> > > guarantees it provides. Feedback is welcome,
> > 
> 
> Hi Paul,
> 
> Your reply brings interesting thoughts, see below,
> 
> > Interesting!  Please see below for my take on it.
> > 
> > 							Thanx, Paul
> > 
> > > Thanks,
> > > 
> > > Mathieu
> > > 
> > > commit 0f5543cb1780acef35878646e6cdc966f1406c18
> > > Author: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> > > Date:   Wed Apr 18 16:05:29 2012 -0400
> > > 
> > >     rculfhash: document linearizability guarantees
> > >     
> > >     Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> > > 
> > > diff --git a/rculfhash.c b/rculfhash.c
> > > index 6f470fd..d22b44d 100644
> > > --- a/rculfhash.c
> > > +++ b/rculfhash.c
> > > @@ -98,6 +98,33 @@
> > >   *   hash table nodes. These tables are invariant after they are
> > >   *   populated into the hash table.
> > >   *
> > > + * Linearizability Guarantees:
> > 
> > I suggest calling these ordering guarantees.  Otherwise, people will
> > glance at the heading and assume that the hash table is linearizable,
> > which from what I can see is not the case.  (And I do -not- recommend
> > making it be the case, just to be sure that there is no confusion.)
> 
> Ordering guarantees works for me, but I'm curious to know the reasons
> that make you think it's not linearizeable. AFAIU, linearizability
> requires:
> 
> - That there is an atomic step at which each operation takes place,
>   located between the start and the end of each method (linearization
>   point).

The above can fail due to reordering of readers by either the CPU
or the compiler.

> - Progress guarantees for each method.
> 
> So looking at linearization points for updates:
> 
> - add: takes place atomically at the cmpxchg that links the new node
>   into the linked list.

Yep.

> - add_replace: takes place atomically at the uatomic_cmpxchg responsible
>   for linking the new node into the linked list, replacing an existing
>   node (add_replace) atomically by setting the "removed" flag into the
>   replaced node's next pointer at the same time as the new node is
>   inserted.

Yep.

> - add_unique: takes place atomically at the cmpxchg that either
>   links the new node into the linked list, or otherwise detects
>   that the prev node next pointer has changed, triggering a retry.

Yep.

> - del: takes place atomically by setting the "removed" flag into the
>   next pointer of the node to remove (atomic "or").

Yep.

> Linearization points for reads: those seem to apply to individual
> operations (e.g. lookup, get_first, get_next, get_next_duplicate):
> 
> - lookup: atomically reading the next pointer of the node prior to
>   either:
>   - the node containing the key we are looking for,
>   - the node containing the first key above the key we are looking for,
>   - the end of the list (next pointer is NULL).

Nope.  This could be reordered by either compiler or CPU with another
read operation.

> - get_first: atomically reading the head next pointer.

Ditto.

> - get_next: atomically reading the next pointer of the current node.

Ordered with respect to the corresponding get_first() due to dependency
ordering, also with respect to another get_next() or get_next_duplicate()
in the same traversal, but not ordered with respect to lookup().

> - get_next_duplicate: atomically reading the next pointer of the
>   current node.

Ditto.

> Progress guarantees:
> 
> Updates:
> 
> Each retry faced by an update is always caused by another concurrent
> operation that itself progresses (lock-freedom type of progress
> guarantee).
> 
> Reads:
> 
> Read operations never loop: the linked lists only go in one direction,
> from the head to the tail.

I agree with both of these.  Updates are lock-free (assuming use of
call_rcu() and sufficient memory) and readers are wait-free.

> We have to note that for linearizability, I used the basic read
> operations (which happen atomically) rather than sequence of such
> operations.
> 
> One item I'm not convinced could be called entirely linearizable is the
> resize operation: it happens lazily at some point in time that is not
> usually within the update operations. For that one, I'd be tempted
> to say that the hash table is not linearizable. Thoughts ?

The possibility of reordering of read operations means that it is not
linearizable even in the absence of resize operations.

> > > + *
> > > + * To discuss these guarantees, we first define "read" operations as any
> > > + * of the following operations surrounded by an RCU read-side lock/unlock
> > > + * pair:
> > > + *  - cds_lfht_lookup
> > > + *  - cds_lfht_lookup followed by iteration with cds_lfht_next_duplicate
> > > + *  - cds_lfht_first followed iteration with cds_lfht_next
> > > + *
> > > + * We define "write" operations as any of cds_lfht_add,
> > > + * cds_lfht_add_unique, cds_lfht_add_replace, cds_lfht_del.
> > > + *
> > > + * The following guarantees are offered by this hash table:
> > > + *
> > > + * A) "read" after "write" will always return the result of the latest
> > > + *    write.
> > 
> > Hmmm...  "Latest" by what measure?  What is the guarantee really
> > saying if there are a large number of writes and reads all involving
> > the same hash key?
> > 
> > My guess is that the guarantee is actually of the following form:
> > If there is ordering between a write and a later read, then the
> > read is guaranteed to see the write or some later write.
> 
> Yes, although I think thinking in terms of "sequence of reads" might be
> more appropriate than "basic read operation". By that, I mean thinking
> in terms of iteration over the entire hash table, or iteration over a
> key and all its duplicates, rather than the basic lookup/get next/get
> next duplicate/get first operations.

Only if you have something explicitly ordering the reads, like an
explicit memory barrier or some such.  The reads in a given traversal
are ordered by dependency ordering, but only with respect to other
reads in that same traversal.

> > As I understand it, this guarantee requires that the read and write
> > operate on the same key.
> 
> Well, a sequence of "read" operations can be an iteration on the whole
> table (get first, then get_next until we reach the end of the table). So
> what I'm trying to say here is that if we have a sequence of read
> operations for which the first operation is ordered after a write, those
> are guaranteed to see this write or some later write.

Yes, but only for the reads in that same traversal or a later traversal
by this same thread.  No guarantees for an independent lookup() operation,
for example.

> Of course, if the sequence of read operations is executed across the
> write, it may or may not see the write.
> 
> And if the sequence of read operations is known to have its last read
> ordered before a write, it is ensured that it will not see this write.

Agreed.

> > This might be easier given a guarantee that writes involving a given
> > key are seen in order.  I believe that the hash table does provide this
> > guarantee and that it would be good to state it explicitly.
> 
> I'm wondering if the reasoning about a single "key" you are proposing
> takes into account that the hash table supports duplicate keys ?

If I understand correctly, the duplicate keys get hidden and uncovered
in order.  But I have not analyzed this case carefully.

> > > + * B) "write" after "read" will never be returned by the read.
> > 
> > There is a useful guarantee involving a pair of reads: If a pair
> > of reads of a given key are ordered (e.g., by a memory barrier),
> > then the second read will return the same value as the first
> > read or some later value.
> 
> Yep, e.g. if we use add_replace to replace a given node with a version
> that has an incremented counter, reads that are ordered with memory
> barriers are guaranteed to see this counter always incrementing.

Agreed.  Cross-thread ordering might be supplied by communication
with some other variable combined with appropriate memory barriers.

> > > + * C) It is guaranteed that after a grace period following a "del" and
> > > + *    "replace" operation, no reference to the removed items exists in
> > > + *    the hash table.
> > 
> > I would instead say something like: If a grace period separates a "del"
> > or "replace" operation and a subsequent read operation, then that reader
> > is guaranteed not to see the removed item.
> 
> Your statement is true, but the actual idea I want to convey is stronger
> than that: after that grace period, we guarantee that no read nor update
> operation can see the removed pointer (even just internally).

OK, then how about this?

	If a grace period separates a "del" or "replace" operation
	and a subsequent operation, then that subsequent operation is
	guaranteed not to see the removed item.

							Thanx, Paul

> > > + * D) Uniqueness guarantee: when using add_unique and/or add_replace to
> > > + *    insert nodes into the table, if there was previously one node or
> > > + *    less with the same key being inserted by one or more concurrent
> > > + *    add_unique and/or add_replace, all concurrent "read" performed on
> > > + *    the hash table are guaranteed to find one, and only one node with
> > > + *    that key.
> > 
> > How about: Given a hash table that does not contain duplicate items
> > for a given key, there will only be one item in the hash table after
> > an arbitrary sequence of add_unique and/or add_replace operations.
> > Note, however, that a pair of concurrent read operations might well
> > access two different items with that key.
> 
> Yes, that works,
> 
> Thanks for the feedback!
> 
> Mathieu
> 
> > 
> > >   * Bucket node tables:
> > >   *
> > >   * hash table	hash table	the last	all bucket node tables
> > > 
> > > -- 
> > > 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
> 
> _______________________________________________
> rp mailing list
> rp at svcs.cs.pdx.edu
> http://svcs.cs.pdx.edu/mailman/listinfo/rp
> 

[lttng-dev] [rp] [commit] rculfhash: document linearizability guarantees

[Mathieu Desnoyers]

Hi Paul,

* Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> On Thu, Apr 19, 2012 at 08:02:57PM -0400, Mathieu Desnoyers wrote:
> > * Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> > > On Wed, Apr 18, 2012 at 04:10:17PM -0400, Mathieu Desnoyers wrote:
[...]

> > > This might be easier given a guarantee that writes involving a given
> > > key are seen in order.  I believe that the hash table does provide this
> > > guarantee and that it would be good to state it explicitly.
> > 
> > I'm wondering if the reasoning about a single "key" you are proposing
> > takes into account that the hash table supports duplicate keys ?
> 
> If I understand correctly, the duplicate keys get hidden and uncovered
> in order.  But I have not analyzed this case carefully.

When dealing with a table that may contain duplicate keys, it is
necessary to use "lookup + iteration with get_next_duplicate" to get all
the nodes that have duplicate keys. If one chooses to use lookup without
get next duplicate on a table with duplicated keys, I don't think we
should guarantee which keys are hidden and which are not (this would be
a constraint on the table I'm not sure we want to put upon us without a
good reason).

> 
> > > > + * B) "write" after "read" will never be returned by the read.
> > > 
> > > There is a useful guarantee involving a pair of reads: If a pair
> > > of reads of a given key are ordered (e.g., by a memory barrier),
> > > then the second read will return the same value as the first
> > > read or some later value.
> > 
> > Yep, e.g. if we use add_replace to replace a given node with a version
> > that has an incremented counter, reads that are ordered with memory
> > barriers are guaranteed to see this counter always incrementing.
> 
> Agreed.  Cross-thread ordering might be supplied by communication
> with some other variable combined with appropriate memory barriers.

So the read after read ordering guarantee seems to only makes sense if
we have a table that has no duplicate of a given key (and where
add_replace is used to update the key's content).

If we want to address tables with duplicate keys, then we should discuss
iteration over duplicate keys. And in this case, we should talk about an
iteration over duplicate keys that starts after the end of a previous
iteration (if they overlap, we cannot say anything).

Thoughts ?

Thanks,

Mathieu



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

[lttng-dev] rculfhash ordering guarantees

[Mathieu Desnoyers]

Hi Paul,

Here is the updated text I plan for the next update. Comments are
welcome, thanks !

Mathieu

 * Ordering Guarantees:
 *
 * To discuss these guarantees, we first define "read" operation as any
 * of the the basic cds_lfht_lookup, cds_lfht_next_duplicate,
 * cds_lfht_first, cds_lfht_next operation.
 *
 * We define "read traversal" operation as any of the following
 * group of operations
 *  - cds_lfht_lookup followed by iteration with cds_lfht_next_duplicate
 *  - cds_lfht_first followed iteration with cds_lfht_next
 *
 * We define "write" operations as any of cds_lfht_add,
 * cds_lfht_add_unique, cds_lfht_add_replace, cds_lfht_del.
 *
 * We define "prior" and "later" node as nodes observable by reads and
 * read traversals respectively before and after a write or sequence of
 * write operations.
 *
 * It is implicit from the requirement of the read, read traversal, and
 * write operations that RCU read-side locks need to be held across
 * traversals, and between a read or read traversal and invocation of a
 * write that receives a node as argument.
 *
 * The following ordering guarantees are offered by this hash table:
 *
 * A.1) "read" after "write": if there is ordering between a write and a
 *      later read, then the read is guaranteed to see the write or some
 *      later write.
 * A.2) "read traversal" after "write": given that there is dependency
 *      ordering between reads in a "read traversal", if there is
 *      ordering between a write and the first read of the traversal,
 *      then the "read traversal" is guaranteed to see the write or
 *      some later write.
 * B.1) "write" after "read": if there is ordering between a read and a
 *      later write, then the read will never see the write.
 * B.2) "write" after "read traversal": given that there is dependency
 *      ordering between reads in a "read traversal", if there is
 *      ordering between the last read of the traversal and a later
 *      write, then the "read traversal" will never see the write.
 * C)   "write" while "read traversal": if a write occurs during a "read
 *      traversal", the traversal may, or may not, see the write.
 * D)   "write" vs "write": writes occur atomically between their
 *      invocation and the moment they return. There is a full memory
 *      barrier before and after the atomic "commit" point of each
 *      write.
 * E)   If a grace period separates a "del" or "replace" operation
 *      and a subsequent operation, then that subsequent operation is
 *      guaranteed not to see the removed item.
 * F)   Uniqueness guarantee: given a hash table that does not contain
 *      duplicate items for a given key, there will only be one item in
 *      the hash table after an arbitrary sequence of add_unique and/or
 *      add_replace operations.  Note, however, that a pair of
 *      concurrent read operations might well access two different items
 *      with that key.
 * G.1) Given a hash table that does not contain duplicate items for a
 *      given key, if a pair of lookups for a given key are ordered
 *      (e.g. by a memory barrier), then the second lookup will return
 *      the same node as the previous lookup, or some later node.
 * G.2) A "read traversal" that starts after the end of a prior "read
 *      traversal" (ordered by memory barriers) is guaranteed to see the
 *      same nodes as the previous traversal, or some later nodes.
 *
 * Progress guarantees:
 *
 * * Reads are wait-free. These operations always move forward in the
 *   hash table linked list, and this list has no loop.
 * * Writes are lock-free. Any retry loop performed by a write operation
 *   is triggered by progress made within another update operation.

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

[lttng-dev] [rp] rculfhash ordering guarantees

[Paul E. McKenney]

On Mon, Apr 23, 2012 at 03:45:32PM -0400, Mathieu Desnoyers wrote:
> Hi Paul,
> 
> Here is the updated text I plan for the next update. Comments are
> welcome, thanks !

Looks much improved!  The inevitable questions and comments interspersed.

							Thanx, Paul

> Mathieu
> 
>  * Ordering Guarantees:
>  *
>  * To discuss these guarantees, we first define "read" operation as any
>  * of the the basic cds_lfht_lookup, cds_lfht_next_duplicate,
>  * cds_lfht_first, cds_lfht_next operation.
>  *
>  * We define "read traversal" operation as any of the following
>  * group of operations
>  *  - cds_lfht_lookup followed by iteration with cds_lfht_next_duplicate
>  *  - cds_lfht_first followed iteration with cds_lfht_next

Can't cds_lfht_next() and cds_lfht_next_duplicate() be intermixed?
Something like the following:

	rcu_read_lock();
	p = cds_lfht_lookup(...);
	while (p != NULL) {
		do_something(p);
		if (p->dups_of_interest)
			p = cds_lfht_next_duplicate(...);
		else
			p = cds_lfht_next(...);
	}
	rcu_read_unlock();

>  *
>  * We define "write" operations as any of cds_lfht_add,
>  * cds_lfht_add_unique, cds_lfht_add_replace, cds_lfht_del.
>  *
>  * We define "prior" and "later" node as nodes observable by reads and
>  * read traversals respectively before and after a write or sequence of
>  * write operations.
>  *
>  * It is implicit from the requirement of the read, read traversal, and
>  * write operations that RCU read-side locks need to be held across
>  * traversals, and between a read or read traversal and invocation of a
>  * write that receives a node as argument.

This paragraph is implying a lot...  How about the following?

	Hash-table operations are often chained, for example, the
	pointer returned by a cds_lfht_lookup() might be passed to a
	cds_lfht_next(), whose return value might in turn be passed to
	another hash-table operation.  This entire chain of operations
	must be enclosed by a pair of matching rcu_read_lock() and
	rcu_read_unlock() operations.

>  *
>  * The following ordering guarantees are offered by this hash table:
>  *
>  * A.1) "read" after "write": if there is ordering between a write and a
>  *      later read, then the read is guaranteed to see the write or some
>  *      later write.
>  * A.2) "read traversal" after "write": given that there is dependency
>  *      ordering between reads in a "read traversal", if there is
>  *      ordering between a write and the first read of the traversal,
>  *      then the "read traversal" is guaranteed to see the write or
>  *      some later write.
>  * B.1) "write" after "read": if there is ordering between a read and a
>  *      later write, then the read will never see the write.
>  * B.2) "write" after "read traversal": given that there is dependency
>  *      ordering between reads in a "read traversal", if there is
>  *      ordering between the last read of the traversal and a later
>  *      write, then the "read traversal" will never see the write.
>  * C)   "write" while "read traversal": if a write occurs during a "read
>  *      traversal", the traversal may, or may not, see the write.
>  * D)   "write" vs "write": writes occur atomically between their
>  *      invocation and the moment they return. There is a full memory
>  *      barrier before and after the atomic "commit" point of each
>  *      write.

This is a description of the implementation, while the others are guarantees.
Of course, that begs the question of what the guarantee is...  Maybe the
following?

D.1	"write" after "write": if there is ordering between a write and
	a later write, then the later write is guaranteed to see the
	effects of the first write.
D.2	Concurrent "write" pairs: The system will assign an arbitrary order
	to any pair of concurrent conflicting writes.  Non-conflicting
	writes (for example, to different keys) are unordered.

>  * E)   If a grace period separates a "del" or "replace" operation
>  *      and a subsequent operation, then that subsequent operation is
>  *      guaranteed not to see the removed item.
>  * F)   Uniqueness guarantee: given a hash table that does not contain
>  *      duplicate items for a given key, there will only be one item in
>  *      the hash table after an arbitrary sequence of add_unique and/or
>  *      add_replace operations.  Note, however, that a pair of
>  *      concurrent read operations might well access two different items
>  *      with that key.
>  * G.1) Given a hash table that does not contain duplicate items for a
>  *      given key, if a pair of lookups for a given key are ordered
>  *      (e.g. by a memory barrier), then the second lookup will return
>  *      the same node as the previous lookup, or some later node.
>  * G.2) A "read traversal" that starts after the end of a prior "read
>  *      traversal" (ordered by memory barriers) is guaranteed to see the
>  *      same nodes as the previous traversal, or some later nodes.
>  *
>  * Progress guarantees:
>  *
>  * * Reads are wait-free. These operations always move forward in the
>  *   hash table linked list, and this list has no loop.
>  * * Writes are lock-free. Any retry loop performed by a write operation
>  *   is triggered by progress made within another update operation.
> 
> -- 
> 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] [rp] rculfhash ordering guarantees

[Mathieu Desnoyers]

* Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> On Mon, Apr 23, 2012 at 03:45:32PM -0400, Mathieu Desnoyers wrote:
> > Hi Paul,
> > 
> > Here is the updated text I plan for the next update. Comments are
> > welcome, thanks !
> 
> Looks much improved!  The inevitable questions and comments interspersed.
> 
> 							Thanx, Paul
> 
> > Mathieu
> > 
> >  * Ordering Guarantees:
> >  *
> >  * To discuss these guarantees, we first define "read" operation as any
> >  * of the the basic cds_lfht_lookup, cds_lfht_next_duplicate,
> >  * cds_lfht_first, cds_lfht_next operation.
> >  *
> >  * We define "read traversal" operation as any of the following
> >  * group of operations
> >  *  - cds_lfht_lookup followed by iteration with cds_lfht_next_duplicate
> >  *  - cds_lfht_first followed iteration with cds_lfht_next
> 
> Can't cds_lfht_next() and cds_lfht_next_duplicate() be intermixed?
> Something like the following:
> 
> 	rcu_read_lock();
> 	p = cds_lfht_lookup(...);
> 	while (p != NULL) {
> 		do_something(p);
> 		if (p->dups_of_interest)
> 			p = cds_lfht_next_duplicate(...);
> 		else
> 			p = cds_lfht_next(...);
> 	}
> 	rcu_read_unlock();

Yes, they can technically be intermixed, but I doubt that the
"cds_lfht_next" after a lookup will be of any interest: it will get the
nodes with keys following the current node's key (in split-ordered
order).

A use-case that would make more sense would be:

- cds_lfht_first

- iterate on the table with cds_lfht_next(), until we find an
  interesting key.

- Then, iterate on all the duplicate of this key.

So I will document that both can be intermixed.

> 
> >  *
> >  * We define "write" operations as any of cds_lfht_add,
> >  * cds_lfht_add_unique, cds_lfht_add_replace, cds_lfht_del.
> >  *
> >  * We define "prior" and "later" node as nodes observable by reads and
> >  * read traversals respectively before and after a write or sequence of
> >  * write operations.
> >  *
> >  * It is implicit from the requirement of the read, read traversal, and
> >  * write operations that RCU read-side locks need to be held across
> >  * traversals, and between a read or read traversal and invocation of a
> >  * write that receives a node as argument.
> 
> This paragraph is implying a lot...  How about the following?
> 
> 	Hash-table operations are often chained, for example, the
> 	pointer returned by a cds_lfht_lookup() might be passed to a
> 	cds_lfht_next(), whose return value might in turn be passed to
> 	another hash-table operation.  This entire chain of operations
> 	must be enclosed by a pair of matching rcu_read_lock() and
> 	rcu_read_unlock() operations.

looks good, will update.

> 
> >  *
> >  * The following ordering guarantees are offered by this hash table:
> >  *
> >  * A.1) "read" after "write": if there is ordering between a write and a
> >  *      later read, then the read is guaranteed to see the write or some
> >  *      later write.
> >  * A.2) "read traversal" after "write": given that there is dependency
> >  *      ordering between reads in a "read traversal", if there is
> >  *      ordering between a write and the first read of the traversal,
> >  *      then the "read traversal" is guaranteed to see the write or
> >  *      some later write.
> >  * B.1) "write" after "read": if there is ordering between a read and a
> >  *      later write, then the read will never see the write.
> >  * B.2) "write" after "read traversal": given that there is dependency
> >  *      ordering between reads in a "read traversal", if there is
> >  *      ordering between the last read of the traversal and a later
> >  *      write, then the "read traversal" will never see the write.
> >  * C)   "write" while "read traversal": if a write occurs during a "read
> >  *      traversal", the traversal may, or may not, see the write.
> >  * D)   "write" vs "write": writes occur atomically between their
> >  *      invocation and the moment they return. There is a full memory
> >  *      barrier before and after the atomic "commit" point of each
> >  *      write.
> 
> This is a description of the implementation, while the others are guarantees.
> Of course, that begs the question of what the guarantee is...  Maybe the
> following?
> 
> D.1	"write" after "write": if there is ordering between a write and
> 	a later write, then the later write is guaranteed to see the
> 	effects of the first write.
> D.2	Concurrent "write" pairs: The system will assign an arbitrary order
> 	to any pair of concurrent conflicting writes.  Non-conflicting
> 	writes (for example, to different keys) are unordered.

yep, looks good.

I also documented more thoroughly the "cds_lfht_add_unique", which acts
as a write (if it returns success) or read (if it returns failure).

Here is the updated version:

 * Ordering Guarantees:
 *
 * To discuss these guarantees, we first define "read" operation as any
 * of the the basic cds_lfht_lookup, cds_lfht_next_duplicate,
 * cds_lfht_first, cds_lfht_next operation, as well as
 * cds_lfht_add_unique (failure). 
 *
 * We define "read traversal" operation as any of the following
 * group of operations
 *  - cds_lfht_lookup followed by iteration with cds_lfht_next_duplicate
 *    (and/or cds_lfht_next, although less common).
 *  - cds_lfht_add_unique (failure) followed by iteration with
 *    cds_lfht_next_duplicate (and/or cds_lfht_next, although less
 *    common).
 *  - cds_lfht_first followed iteration with cds_lfht_next (and/or
 *    cds_lfht_next_duplicate, although less common).
 *
 * We define "write" operations as any of cds_lfht_add,
 * cds_lfht_add_unique (success), cds_lfht_add_replace, cds_lfht_del.
 *
 * When cds_lfht_add_unique succeeds (returns the node passed as
 * parameter), it acts as a "write" operation. When cds_lfht_add_unique
 * fails (returns a node different from the one passed as parameter), it
 * acts as a "read" operation. A cds_lfht_add_unique failure is a
 * cds_lfht_lookup "read" operation, therefore, any ordering guarantee
 * referring to "lookup" imply any of "lookup" or cds_lfht_add_unique
 * (failure).
 *
 * We define "prior" and "later" node as nodes observable by reads and
 * read traversals respectively before and after a write or sequence of
 * write operations.
 *
 * Hash-table operations are often chained, for example, the pointer
 * returned by a cds_lfht_lookup() might be passed to a cds_lfht_next(),
 * whose return value might in turn be passed to another hash-table
 * operation. This entire chain of operations must be enclosed by a
 * pair of matching rcu_read_lock() and rcu_read_unlock() operations.
 *
 * The following ordering guarantees are offered by this hash table:
 *
 * A.1) "read" after "write": if there is ordering between a write and a
 *      later read, then the read is guaranteed to see the write or some
 *      later write.
 * A.2) "read traversal" after "write": given that there is dependency
 *      ordering between reads in a "read traversal", if there is
 *      ordering between a write and the first read of the traversal,
 *      then the "read traversal" is guaranteed to see the write or
 *      some later write.
 * B.1) "write" after "read": if there is ordering between a read and a
 *      later write, then the read will never see the write.
 * B.2) "write" after "read traversal": given that there is dependency
 *      ordering between reads in a "read traversal", if there is
 *      ordering between the last read of the traversal and a later
 *      write, then the "read traversal" will never see the write.
 * C)   "write" while "read traversal": if a write occurs during a "read
 *      traversal", the traversal may, or may not, see the write.
 * D.1) "write" after "write": if there is ordering between a write and
 *      a later write, then the later write is guaranteed to see the
 *      effects of the first write.
 * D.2) Concurrent "write" pairs: The system will assign an arbitrary
 *      order to any pair of concurrent conflicting writes.
 *      Non-conflicting writes (for example, to different keys) are
 *      unordered.
 * E)   If a grace period separates a "del" or "replace" operation
 *      and a subsequent operation, then that subsequent operation is
 *      guaranteed not to see the removed item.
 * F)   Uniqueness guarantee: given a hash table that does not contain
 *      duplicate items for a given key, there will only be one item in
 *      the hash table after an arbitrary sequence of add_unique and/or
 *      add_replace operations. Note, however, that a pair of
 *      concurrent read operations might well access two different items
 *      with that key.
 * G.1) If a pair of lookups for a given key are ordered (e.g. by a
 *      memory barrier), then the second lookup will return the same
 *      node as the previous lookup, or some later node.
 * G.2) A "read traversal" that starts after the end of a prior "read
 *      traversal" (ordered by memory barriers) is guaranteed to see the
 *      same nodes as the previous traversal, or some later nodes.
 *
 * Progress guarantees:
 *
 * * Reads are wait-free. These operations always move forward in the
 *   hash table linked list, and this list has no loop.
 * * Writes are lock-free. Any retry loop performed by a write operation
 *   is triggered by progress made within another update operation.
 *

Thanks,

Mathieu

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

[lttng-dev] [rp] rculfhash ordering guarantees

[Paul E. McKenney]

On Mon, Apr 23, 2012 at 10:54:54PM -0400, Mathieu Desnoyers wrote:
> * Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> > On Mon, Apr 23, 2012 at 03:45:32PM -0400, Mathieu Desnoyers wrote:
> > > Hi Paul,
> > > 
> > > Here is the updated text I plan for the next update. Comments are
> > > welcome, thanks !
> > 
> > Looks much improved!  The inevitable questions and comments interspersed.
> > 
> > 							Thanx, Paul
> > 
> > > Mathieu
> > > 
> > >  * Ordering Guarantees:
> > >  *
> > >  * To discuss these guarantees, we first define "read" operation as any
> > >  * of the the basic cds_lfht_lookup, cds_lfht_next_duplicate,
> > >  * cds_lfht_first, cds_lfht_next operation.
> > >  *
> > >  * We define "read traversal" operation as any of the following
> > >  * group of operations
> > >  *  - cds_lfht_lookup followed by iteration with cds_lfht_next_duplicate
> > >  *  - cds_lfht_first followed iteration with cds_lfht_next
> > 
> > Can't cds_lfht_next() and cds_lfht_next_duplicate() be intermixed?
> > Something like the following:
> > 
> > 	rcu_read_lock();
> > 	p = cds_lfht_lookup(...);
> > 	while (p != NULL) {
> > 		do_something(p);
> > 		if (p->dups_of_interest)
> > 			p = cds_lfht_next_duplicate(...);
> > 		else
> > 			p = cds_lfht_next(...);
> > 	}
> > 	rcu_read_unlock();
> 
> Yes, they can technically be intermixed, but I doubt that the
> "cds_lfht_next" after a lookup will be of any interest: it will get the
> nodes with keys following the current node's key (in split-ordered
> order).

I missed a 50% chance of doing something useful.  Good thing I didn't buy
a lottery ticket.  ;-)

> A use-case that would make more sense would be:
> 
> - cds_lfht_first
> 
> - iterate on the table with cds_lfht_next(), until we find an
>   interesting key.
> 
> - Then, iterate on all the duplicate of this key.
> 
> So I will document that both can be intermixed.

Sounds good!

> > >  *
> > >  * We define "write" operations as any of cds_lfht_add,
> > >  * cds_lfht_add_unique, cds_lfht_add_replace, cds_lfht_del.
> > >  *
> > >  * We define "prior" and "later" node as nodes observable by reads and
> > >  * read traversals respectively before and after a write or sequence of
> > >  * write operations.
> > >  *
> > >  * It is implicit from the requirement of the read, read traversal, and
> > >  * write operations that RCU read-side locks need to be held across
> > >  * traversals, and between a read or read traversal and invocation of a
> > >  * write that receives a node as argument.
> > 
> > This paragraph is implying a lot...  How about the following?
> > 
> > 	Hash-table operations are often chained, for example, the
> > 	pointer returned by a cds_lfht_lookup() might be passed to a
> > 	cds_lfht_next(), whose return value might in turn be passed to
> > 	another hash-table operation.  This entire chain of operations
> > 	must be enclosed by a pair of matching rcu_read_lock() and
> > 	rcu_read_unlock() operations.
> 
> looks good, will update.
> 
> > 
> > >  *
> > >  * The following ordering guarantees are offered by this hash table:
> > >  *
> > >  * A.1) "read" after "write": if there is ordering between a write and a
> > >  *      later read, then the read is guaranteed to see the write or some
> > >  *      later write.
> > >  * A.2) "read traversal" after "write": given that there is dependency
> > >  *      ordering between reads in a "read traversal", if there is
> > >  *      ordering between a write and the first read of the traversal,
> > >  *      then the "read traversal" is guaranteed to see the write or
> > >  *      some later write.
> > >  * B.1) "write" after "read": if there is ordering between a read and a
> > >  *      later write, then the read will never see the write.
> > >  * B.2) "write" after "read traversal": given that there is dependency
> > >  *      ordering between reads in a "read traversal", if there is
> > >  *      ordering between the last read of the traversal and a later
> > >  *      write, then the "read traversal" will never see the write.
> > >  * C)   "write" while "read traversal": if a write occurs during a "read
> > >  *      traversal", the traversal may, or may not, see the write.
> > >  * D)   "write" vs "write": writes occur atomically between their
> > >  *      invocation and the moment they return. There is a full memory
> > >  *      barrier before and after the atomic "commit" point of each
> > >  *      write.
> > 
> > This is a description of the implementation, while the others are guarantees.
> > Of course, that begs the question of what the guarantee is...  Maybe the
> > following?
> > 
> > D.1	"write" after "write": if there is ordering between a write and
> > 	a later write, then the later write is guaranteed to see the
> > 	effects of the first write.
> > D.2	Concurrent "write" pairs: The system will assign an arbitrary order
> > 	to any pair of concurrent conflicting writes.  Non-conflicting
> > 	writes (for example, to different keys) are unordered.
> 
> yep, looks good.
> 
> I also documented more thoroughly the "cds_lfht_add_unique", which acts
> as a write (if it returns success) or read (if it returns failure).
> 
> Here is the updated version:

Much better!  Just a couple of remaining nits, one of them my fault rather
than yours.

							Thanx, Paul

>  * Ordering Guarantees:
>  *
>  * To discuss these guarantees, we first define "read" operation as any
>  * of the the basic cds_lfht_lookup, cds_lfht_next_duplicate,
>  * cds_lfht_first, cds_lfht_next operation, as well as
>  * cds_lfht_add_unique (failure). 
>  *
>  * We define "read traversal" operation as any of the following
>  * group of operations
>  *  - cds_lfht_lookup followed by iteration with cds_lfht_next_duplicate
>  *    (and/or cds_lfht_next, although less common).
>  *  - cds_lfht_add_unique (failure) followed by iteration with
>  *    cds_lfht_next_duplicate (and/or cds_lfht_next, although less
>  *    common).
>  *  - cds_lfht_first followed iteration with cds_lfht_next (and/or
>  *    cds_lfht_next_duplicate, although less common).
>  *
>  * We define "write" operations as any of cds_lfht_add,
>  * cds_lfht_add_unique (success), cds_lfht_add_replace, cds_lfht_del.
>  *
>  * When cds_lfht_add_unique succeeds (returns the node passed as
>  * parameter), it acts as a "write" operation. When cds_lfht_add_unique
>  * fails (returns a node different from the one passed as parameter), it
>  * acts as a "read" operation. A cds_lfht_add_unique failure is a
>  * cds_lfht_lookup "read" operation, therefore, any ordering guarantee
>  * referring to "lookup" imply any of "lookup" or cds_lfht_add_unique
>  * (failure).
>  *
>  * We define "prior" and "later" node as nodes observable by reads and
>  * read traversals respectively before and after a write or sequence of
>  * write operations.
>  *
>  * Hash-table operations are often chained, for example, the pointer
>  * returned by a cds_lfht_lookup() might be passed to a cds_lfht_next(),
>  * whose return value might in turn be passed to another hash-table
>  * operation. This entire chain of operations must be enclosed by a
>  * pair of matching rcu_read_lock() and rcu_read_unlock() operations.

Sigh.  I obviously wasn't thinking very clearly when I wrote this.
Someone is going to confuse chained operations with hash chains.  One way
to resolve this potential source of confusion is to replace "chain" with
"cascade" as follows:

	Hash-table operations are often cascaded, for example, the
	pointer returned by a cds_lfht_lookup() might be passed to a
	cds_lfht_next(), whose return value might in turn be passed to
	another hash-table operation. This entire cascaded series of
	operations must be enclosed by a pair of matching rcu_read_lock()
	and rcu_read_unlock() operations.

>  *
>  * The following ordering guarantees are offered by this hash table:
>  *
>  * A.1) "read" after "write": if there is ordering between a write and a
>  *      later read, then the read is guaranteed to see the write or some
>  *      later write.
>  * A.2) "read traversal" after "write": given that there is dependency
>  *      ordering between reads in a "read traversal", if there is
>  *      ordering between a write and the first read of the traversal,
>  *      then the "read traversal" is guaranteed to see the write or
>  *      some later write.
>  * B.1) "write" after "read": if there is ordering between a read and a
>  *      later write, then the read will never see the write.
>  * B.2) "write" after "read traversal": given that there is dependency
>  *      ordering between reads in a "read traversal", if there is
>  *      ordering between the last read of the traversal and a later
>  *      write, then the "read traversal" will never see the write.
>  * C)   "write" while "read traversal": if a write occurs during a "read
>  *      traversal", the traversal may, or may not, see the write.
>  * D.1) "write" after "write": if there is ordering between a write and
>  *      a later write, then the later write is guaranteed to see the
>  *      effects of the first write.
>  * D.2) Concurrent "write" pairs: The system will assign an arbitrary
>  *      order to any pair of concurrent conflicting writes.
>  *      Non-conflicting writes (for example, to different keys) are
>  *      unordered.
>  * E)   If a grace period separates a "del" or "replace" operation
>  *      and a subsequent operation, then that subsequent operation is
>  *      guaranteed not to see the removed item.
>  * F)   Uniqueness guarantee: given a hash table that does not contain
>  *      duplicate items for a given key, there will only be one item in
>  *      the hash table after an arbitrary sequence of add_unique and/or
>  *      add_replace operations. Note, however, that a pair of
>  *      concurrent read operations might well access two different items
>  *      with that key.
>  * G.1) If a pair of lookups for a given key are ordered (e.g. by a
>  *      memory barrier), then the second lookup will return the same
>  *      node as the previous lookup, or some later node.
>  * G.2) A "read traversal" that starts after the end of a prior "read
>  *      traversal" (ordered by memory barriers) is guaranteed to see the
>  *      same nodes as the previous traversal, or some later nodes.

And we should explicitly state that concurrent reads are unordered.
For example, if a pair of reads to the same key run concurrently with
an insertion of that same key, the reads remain unordered regardless
of their return values.  In other words, you cannot rely on the values
returns by the reads to deduce ordering.

>  *
>  * Progress guarantees:
>  *
>  * * Reads are wait-free. These operations always move forward in the
>  *   hash table linked list, and this list has no loop.
>  * * Writes are lock-free. Any retry loop performed by a write operation
>  *   is triggered by progress made within another update operation.
>  *
> 
> Thanks,
> 
> Mathieu
> 
> -- 
> Mathieu Desnoyers
> Operating System Efficiency R&D Consultant
> EfficiOS Inc.
> http://www.efficios.com
> 

[lttng-dev] [rp] rculfhash ordering guarantees

[Mathieu Desnoyers]

* Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> On Mon, Apr 23, 2012 at 10:54:54PM -0400, Mathieu Desnoyers wrote:
[...]
> > yep, looks good.
> > 
> > I also documented more thoroughly the "cds_lfht_add_unique", which acts
> > as a write (if it returns success) or read (if it returns failure).
> > 
> > Here is the updated version:
> 
> Much better!  Just a couple of remaining nits, one of them my fault rather
> than yours.

No problem, all updated taking into account your comments. I committed
the changes:

commit 7f94921512c992dde5c3abf5990436531b6230af
Author: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
Date:   Tue Apr 24 00:16:43 2012 -0400

    rculfhash: document ordering guarantees
    
    What we actually provide are ordering guarantees.
    
    Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>


Thanks!

Mathieu

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

[lttng-dev] [rp] [commit] rculfhash: document linearizability guarantees

[Paul E. McKenney]

On Mon, Apr 23, 2012 at 03:17:45PM -0400, Mathieu Desnoyers wrote:
> Hi Paul,
> 
> * Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> > On Thu, Apr 19, 2012 at 08:02:57PM -0400, Mathieu Desnoyers wrote:
> > > * Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> > > > On Wed, Apr 18, 2012 at 04:10:17PM -0400, Mathieu Desnoyers wrote:
> [...]
> 
> > > > This might be easier given a guarantee that writes involving a given
> > > > key are seen in order.  I believe that the hash table does provide this
> > > > guarantee and that it would be good to state it explicitly.
> > > 
> > > I'm wondering if the reasoning about a single "key" you are proposing
> > > takes into account that the hash table supports duplicate keys ?
> > 
> > If I understand correctly, the duplicate keys get hidden and uncovered
> > in order.  But I have not analyzed this case carefully.
> 
> When dealing with a table that may contain duplicate keys, it is
> necessary to use "lookup + iteration with get_next_duplicate" to get all
> the nodes that have duplicate keys. If one chooses to use lookup without
> get next duplicate on a table with duplicated keys, I don't think we
> should guarantee which keys are hidden and which are not (this would be
> a constraint on the table I'm not sure we want to put upon us without a
> good reason).

Ah, I was assuming ordering of the hash chains, with the old duplicates
following the new ones.  If there is no ordering on the chains, then
there can indeed be no ordering of the reads and writes.

> > > > > + * B) "write" after "read" will never be returned by the read.
> > > > 
> > > > There is a useful guarantee involving a pair of reads: If a pair
> > > > of reads of a given key are ordered (e.g., by a memory barrier),
> > > > then the second read will return the same value as the first
> > > > read or some later value.
> > > 
> > > Yep, e.g. if we use add_replace to replace a given node with a version
> > > that has an incremented counter, reads that are ordered with memory
> > > barriers are guaranteed to see this counter always incrementing.
> > 
> > Agreed.  Cross-thread ordering might be supplied by communication
> > with some other variable combined with appropriate memory barriers.
> 
> So the read after read ordering guarantee seems to only makes sense if
> we have a table that has no duplicate of a given key (and where
> add_replace is used to update the key's content).

As long as we are choosing not to constrain the ordering of the
duplicate keys in the hash chains, agreed.

> If we want to address tables with duplicate keys, then we should discuss
> iteration over duplicate keys. And in this case, we should talk about an
> iteration over duplicate keys that starts after the end of a previous
> iteration (if they overlap, we cannot say anything).

I believe that overlaps in time are OK, at least for lookup operations.
Traversals are another issue entirely, unless we are willing to model
a traversal as a series of lookup operations.

> Thoughts ?

You know me.  I never have been much for over-engineering ordering
guarantees.  So let's not guarantee any more than makes sense.

							Thanx, Paul

[lttng-dev] [rp] [commit] rculfhash: document linearizability guarantees

[Mathieu Desnoyers]

* Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> On Mon, Apr 23, 2012 at 03:17:45PM -0400, Mathieu Desnoyers wrote:
> > Hi Paul,
> > 
> > * Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> > > On Thu, Apr 19, 2012 at 08:02:57PM -0400, Mathieu Desnoyers wrote:
> > > > * Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> > > > > On Wed, Apr 18, 2012 at 04:10:17PM -0400, Mathieu Desnoyers wrote:
> > [...]
> > 
> > > > > This might be easier given a guarantee that writes involving a given
> > > > > key are seen in order.  I believe that the hash table does provide this
> > > > > guarantee and that it would be good to state it explicitly.
> > > > 
> > > > I'm wondering if the reasoning about a single "key" you are proposing
> > > > takes into account that the hash table supports duplicate keys ?
> > > 
> > > If I understand correctly, the duplicate keys get hidden and uncovered
> > > in order.  But I have not analyzed this case carefully.
> > 
> > When dealing with a table that may contain duplicate keys, it is
> > necessary to use "lookup + iteration with get_next_duplicate" to get all
> > the nodes that have duplicate keys. If one chooses to use lookup without
> > get next duplicate on a table with duplicated keys, I don't think we
> > should guarantee which keys are hidden and which are not (this would be
> > a constraint on the table I'm not sure we want to put upon us without a
> > good reason).
> 
> Ah, I was assuming ordering of the hash chains, with the old duplicates
> following the new ones.  If there is no ordering on the chains, then
> there can indeed be no ordering of the reads and writes.

Looking back at the history, commit
238cc06e5728e3a642d4d22bd4fc199cfd265110 from Lai explains why we need
to require that the new nodes are inserted at the beginning of the
duplicate chains. This is needed by add_replace/add_unique "uniqueness"
guarantee wrt traversals: the traversal goes forward in the table, so we
need to insert the replacement nodes before (not after) current
iteration position.

> 
> > > > > > + * B) "write" after "read" will never be returned by the read.
> > > > > 
> > > > > There is a useful guarantee involving a pair of reads: If a pair
> > > > > of reads of a given key are ordered (e.g., by a memory barrier),
> > > > > then the second read will return the same value as the first
> > > > > read or some later value.
> > > > 
> > > > Yep, e.g. if we use add_replace to replace a given node with a version
> > > > that has an incremented counter, reads that are ordered with memory
> > > > barriers are guaranteed to see this counter always incrementing.
> > > 
> > > Agreed.  Cross-thread ordering might be supplied by communication
> > > with some other variable combined with appropriate memory barriers.
> > 
> > So the read after read ordering guarantee seems to only makes sense if
> > we have a table that has no duplicate of a given key (and where
> > add_replace is used to update the key's content).
> 
> As long as we are choosing not to constrain the ordering of the
> duplicate keys in the hash chains, agreed.

It looks like we need to guarantee that newer nodes are placed at the
beginning of the hash chains, so we might as well guarantee that read
after read will see either the last write, or a later node, in all cases
(replace, unique, normal add with duplicates).

> 
> > If we want to address tables with duplicate keys, then we should discuss
> > iteration over duplicate keys. And in this case, we should talk about an
> > iteration over duplicate keys that starts after the end of a previous
> > iteration (if they overlap, we cannot say anything).
> 
> I believe that overlaps in time are OK, at least for lookup operations.
> Traversals are another issue entirely, unless we are willing to model
> a traversal as a series of lookup operations.
> 
> > Thoughts ?
> 
> You know me.  I never have been much for over-engineering ordering
> guarantees.  So let's not guarantee any more than makes sense.

Given the review I just made of the add duplicate chain placement, I
finally think it makes sense to add that guarantee.

Thanks,

Mathieu

> 
> 							Thanx, Paul
> 

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