關(guān)于rculist_null的一個(gè)疑問

nswcfd

關(guān)于rculist_null的一個(gè)疑問

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

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

它要解決的問題是，在reader遍歷list的同時(shí)，如果允許writer把當(dāng)前node移動(dòng)到其它list，如何保證reader的遍歷不受影響？
（如果是list_head型的鏈表，移到新的list，則永遠(yuǎn)不會(huì)達(dá)到原來的表頭；如果是NULL結(jié)尾的鏈表，結(jié)束的時(shí)候無法判斷是否還在原來的list）

在介紹hlist_null之前，文章介紹了傳統(tǒng)的hlist（以NULL結(jié)尾）如何解決這個(gè)問題。
這里使用了hlist_for_each_entry_rcu的一個(gè)變種。

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優(yōu)勢(shì)的時(shí)候，是這么說的
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了？（其實(shí)還是因?yàn)闆]有明白問題1的要點(diǎn)）

大家可以討論一下。

mnipxh

1) prefetch可以無視掉，關(guān)鍵是smp_rmb().
我們需要pos->next  ASAP. 不然可能到pos = rcu_dereference(pos->next))時(shí)，pos->next 可能已經(jīng)被改了。
但是我覺得race還是有的。沒人保證pos && ({ next = pos->next; 這兩條語句之間，pos->next沒有被改。

2) 最后通過solt判斷 是不是在同一條鏈表上。。因?yàn)閚ull版本有哨兵吧。

nswcfd

好的，感謝回復(fù)。

插入的時(shí)候特別強(qiáng)調(diào)了新的key必須在新的next之前可見，不知道是不是問題的關(guān)鍵？
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的版本，插入的時(shí)候還是有wmb的，但是遍歷的時(shí)候就沒有了（這意味著，允許讀者新的next和舊的key？？）

mnipxh

遍歷時(shí)的值必須是有效的值（或曾經(jīng)有效的），這樣才能通過compare key， 正確跳出。

writer在填完正確值后才insert（通過wmb保證）。這樣保證reader讀到的新節(jié)點(diǎn)的值是正確有效的。