[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