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 mailing list [email protected] http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
