On Thu, Nov 13, 2008 at 02:14:18PM +0100, Eric Dumazet wrote:

hlist uses NULL value to finish a chain.

hlist_nulls variant use the low order bit set to 1 to signal an end-of-list 
marker.

This allows to store many different end markers, so that some RCU lockless
algos (used in TCP/UDP stack for example) can save some memory barriers in
fast paths.

Two new files are added :

include/linux/list_nulls.h
 - mimics hlist part of include/linux/list.h, derived to hlist_nulls 
variant

include/linux/rculist_nulls.h
 - mimics hlist part of include/linux/rculist.h, derived to hlist_nulls 
variant

  Only four helpers are declared for the moment :

    hlist_nulls_del_init_rcu(), hlist_nulls_del_rcu(),
    hlist_nulls_add_head_rcu() and hlist_nulls_for_each_entry_rcu()

prefetches() were removed, since an end of list is not anymore NULL value.
prefetches() could trigger useless (and possibly dangerous) memory 
transactions.

Example of use (extracted from __udp4_lib_lookup())

	struct sock *sk, *result;
       struct hlist_nulls_node *node;
       unsigned short hnum = ntohs(dport);
       unsigned int hash = udp_hashfn(net, hnum);
       struct udp_hslot *hslot = &udptable->hash[hash];
       int score, badness;

       rcu_read_lock();
begin:
       result = NULL;
       badness = -1;
       sk_nulls_for_each_rcu(sk, node, &hslot->head) {
               score = compute_score(sk, net, saddr, hnum, sport,
                                     daddr, dport, dif);
               if (score > badness) {
                       result = sk;
                       badness = score;
               }
       }
       /*
        * if the nulls value we got at the end of this lookup is
        * not the expected one, we must restart lookup.
        * We probably met an item that was moved to another chain.
        */
       if (get_nulls_value(node) != hash)
               goto begin;

       if (result) {
               if (unlikely(!atomic_inc_not_zero(&result->sk_refcnt)))
                       result = NULL;
               else if (unlikely(compute_score(result, net, saddr, hnum, 
sport,
                                 daddr, dport, dif) < badness)) {
                       sock_put(result);
                       goto begin;
               }
       }
       rcu_read_unlock();
       return result;

Looks good, but a few questions and suggestions interspersed below.

							Thanx, Paul

Signed-off-by: Eric Dumazet <redacted>
---
include/linux/list_nulls.h    |   94 +++++++++++++++++++++++++++
include/linux/rculist_nulls.h |  110 ++++++++++++++++++++++++++++++++
2 files changed, 204 insertions(+)

And @pos is the starting point, correct?  Suggest something like:

	@pos:	the &struct hlist_node serving as starting point and cursor

The point here is to allow an RCU reader to grab the update-side lock
while holding a reference to an hlist_nulls_node, and then be able to
blindly call hlist_nulls_del_init_rcu() without having to do any complex
check to see if the element has already been deleted?

But this only works if each free operation waits for a grace period.
If using SLAB_DESTROY_BY_RCU, the would-be deleter still needs to
revalidate after grabbing the update-side lock, right?  Hmmm...

+
+/**
+ * hlist_nulls_del_rcu - deletes entry from hash list without re-initialization
+ * @n: the element to delete from the hash list.
+ *
+ * Note: hlist_nulls_unhashed() on entry does not return true after this,
+ * the entry is in an undefined state. It is useful for RCU based
+ * lockfree traversal.
+ *
+ * In particular, it means that we can not poison the forward
+ * pointers that may still be used for walking the hash list.
+ *
+ * The caller must take whatever precautions are necessary
+ * (such as holding appropriate locks) to avoid racing
+ * with another list-mutation primitive, such as hlist_nulls_add_head_rcu()
+ * or hlist_nulls_del_rcu(), running on this same list.
+ * However, it is perfectly legal to run concurrently with
+ * the _rcu list-traversal primitives, such as
+ * hlist_nulls_for_each_entry().
+ */
+static inline void hlist_nulls_del_rcu(struct hlist_nulls_node *n)
+{
+	__hlist_nulls_del(n);
+	n->pprev = LIST_POISON2;
+}
+
+/**
+ * hlist_nulls_add_head_rcu
+ * @n: the element to add to the hash list.
+ * @h: the list to add to.
+ *
+ * Description:
+ * Adds the specified element to the specified hlist_nulls,
+ * while permitting racing traversals.
+ *
+ * The caller must take whatever precautions are necessary
+ * (such as holding appropriate locks) to avoid racing
+ * with another list-mutation primitive, such as hlist_nulls_add_head_rcu()
+ * or hlist_nulls_del_rcu(), running on this same list.
+ * However, it is perfectly legal to run concurrently with
+ * the _rcu list-traversal primitives, such as
+ * hlist_nulls_for_each_entry_rcu(), used to prevent memory-consistency
+ * problems on Alpha CPUs.  Regardless of the type of CPU, the
+ * list-traversal primitive must be guarded by rcu_read_lock().
+ */
+static inline void hlist_nulls_add_head_rcu(struct hlist_nulls_node *n,
+					struct hlist_nulls_head *h)
+{
+	struct hlist_nulls_node *first = h->first;
+
+	n->next = first;
+	n->pprev = &h->first;
+	rcu_assign_pointer(h->first, n);
+	if (!is_a_nulls(first))
+		first->pprev = &n->next;
+}
+/**
+ * hlist_nulls_for_each_entry_rcu - iterate over rcu list of given type
+ * @tpos:	the type * to use as a loop cursor.
+ * @pos:	the &struct hlist_nulls_node to use as a loop cursor.
+ * @head:	the head for your list.
+ * @member:	the name of the hlist_nulls_node within the struct.
+ *
+ */
+#define hlist_nulls_for_each_entry_rcu(tpos, pos, head, member) \
+	for (pos = rcu_dereference((head)->first);			 \
+		(!is_a_nulls(pos)) && 			\
+		({ tpos = hlist_nulls_entry(pos, typeof(*tpos), member); 1; }); \
+		pos = rcu_dereference(pos->next))
+
+#endif
+#endif

Any chance of using a trick like Oleg used to get rid of the "pos"
argument?  http://lkml.org/lkml/2008/3/12/47

The hlist_nulls_node must always be at an even address, correct?
Couldn't this fact be used to allow testing for is_a_nulls() on tpos
rather than on pos?  Or is there a better way to approach this?