关于rculist_null的一个疑问

nswcfd

关于rculist_null的一个疑问

http://lxr.free-electrons.com/so ... U/rculist_nulls.txt

Documentation/RCU/rculist_nulls.txt介绍了hlist_nulls如何用于SLAB_DESTROY_BY_RCU类型的slab。

它要解决的问题是，在reader遍历list的同时，如果允许writer把当前node移动到其它list，如何保证reader的遍历不受影响？
（如果是list_head型的链表，移到新的list，则永远不会达到原来的表头；如果是NULL结尾的链表，结束的时候无法判断是否还在原来的list）

在介绍hlist_null之前，文章介绍了传统的hlist（以NULL结尾）如何解决这个问题。
这里使用了hlist_for_each_entry_rcu的一个变种。

33 Beware that lockless_lookup(key) cannot use traditional hlist_for_each_entry_rcu()
34 but a version 【with an additional memory barrier (smp_rmb())】
35
36 lockless_lookup(key)
37 {
38    struct hlist_node *node, *next;
39    for (pos = rcu_dereference((head)->first);
40           pos && ({ next = pos->next; smp_rmb(); prefetch(next); 1; }) &&
41           ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; });
42           pos = rcu_dereference(next))
43       if (obj->key == key)
44          return obj;
45    return NULL;

后面引用了一句话：
59 Quoting Corey Minyard :
60
.66  。。。。。。。。。。。。。。。。。。。。。  I think that this can be
67  solved 【by pre-fetching the "next" field (with proper barriers) before
68  checking the key】."

最后，在介绍hlist_null优势的时候，是这么说的
112 With hlist_nulls we can 【avoid extra smp_rmb()】 in lockless_lookup()
113 and 【extra smp_wmb()】in insert function.

------------------------------------------------------------------------

在这里，我不太明白的是，
1) 为什么hlist版本（不是hlist_null）下使用prefetch+mb就可以解决问题？
2）为什么hlist_null版本就不需要mb了？（其实还是因为没有明白问题1的要点）

大家可以讨论一下。

mnipxh

1) prefetch可以无视掉，关键是smp_rmb().
我们需要pos->next  ASAP. 不然可能到pos = rcu_dereference(pos->next))时，pos->next 可能已经被改了。
但是我觉得race还是有的。没人保证pos && ({ next = pos->next; 这两条语句之间，pos->next没有被改。

2) 最后通过solt判断 是不是在同一条链表上。。因为null版本有哨兵吧。

nswcfd

好的，感谢回复。

插入的时候特别强调了新的key必须在新的next之前可见，不知道是不是问题的关键？
73 We need to make sure a reader cannot read the new 'obj->obj_next' value
74 and previous value of 'obj->key'. Or else, an item could be deleted
75 from a chain, and inserted into another chain. If new chain was empty
76 before the move, 'next' pointer is NULL, and lockless reader can
77 not detect it missed following items in original chain.

hlist的版本，插入的时候还是有wmb的，但是遍历的时候就没有了（这意味着，允许读者新的next和旧的key？？）

mnipxh

遍历时的值必须是有效的值（或曾经有效的），这样才能通过compare key， 正确跳出。

writer在填完正确值后才insert（通过wmb保证）。这样保证reader读到的新节点的值是正确有效的。