list_for_each_entry_rcu的问题【尚未解决】

jiufei19

回复 10# l4rmbr


    非常感谢l4rmbr的说明！

    我终于明白了，的确rcu_deference其实和rcu机制本身并没有直接关系，只是为了解决某些cpu的自作聪明的预取机制而设的，目前也仅Alpha有这个特点，对应i386，这个宏其实什么都没有做。那么是否可以这样说，由于没有预取的自作聪明，在i386机器上实际根本不需要这个宏的。但是如果是这样理解，为啥在__sock_create中保留了rcu_deference，而在list.h中却去掉了这个rcu_deference呢？

asuka2001

回复 10# l4rmbr

所以， 必要的次序要保证，这里其实有一个数据依赖的关系， 即p的值应该先读，再读p->a, p->b, p->c,
因此，要加一个屏障，也就是可以严格限定存取顺序的指令。

这里是否描述的稍微有点问题，由于数据依赖，读的顺序保证先读 p，再读 p->a等。

问题在于对于读者，读p读到的是 p的新值；随后读到的 p->a等读到的旧值罢了！

data dependency barrier这里并不是保证读顺序（数据依赖必然保证），而是保证 p为新，则 p->a也应该为新值而已（需要写者 write barrier配合）。

data dependency barrier具体实现我猜想应该是 DEC alpha会感知对p引用的地址的写入，最后废弃预读的p->a等值。

对此只是基于概念上的推测，l4rmbr对 DEC alpha看来比较熟悉，请确认下物理实现是这样的吗？

asuka2001

回复 10# l4rmbr

额，好像有点不对，这不是因为预读的原因吧？

writer:

p_new->a = new_a;

wmb()

p = new_p

当 writer保证了写入顺序的情况下: 对于reader，如果 reader_p == new_p，reader_p->a != new_a 的原因不应该是由于预读造成的吧？而是 cache的更新顺序造成的吧！

如果 writer不做上述写入顺序保证，那么预读与否都没关系了。正常读一样会有这个问题！




   

l4rmbr

回复 13# asuka2001


   Hi, asuka2001,

回上上一个回复， 我的描述是有点问题，你更正是对的。

回上一个回复， 我再重新整理下我的表述：

分两部分说，

1）对于读者端，

读p->a要先知道&(p->a),  而这进而要先得到&p， 这里就存在数据依赖（&p->a依赖&p),  这种最基本的保证
在几乎所有的处理器中都有，也就是不加显式的屏障指令都会得到处理器的保证。这里说的保证的意思是，处理器在访问p->a
时一定会强制更新缓存，重新加载p->a, 这样保证p->a的值是最新的。

但是Alpha是个奇葩， 它不提供这种保证，如之前的回帖所举例子。

所以，可以看到在针对这种数据依赖的情况下，读者端只需要一个读依赖屏障： read_barrier_depends()就可以了，
这个宏在大部分处理器中是空操作， 原因是刚才说的，处理器提供这种保证。唯独在Alpha中，这个宏才有实际的指令。

当然，这里可以用更严格的读屏障： rmb(), 但对于其它有提供这种数据依赖保证的处理器来说，就浪费了。


2）对于写者端，

p_new->a = new_a;

p = new_p;

这里的关系是： 获得一个对象的地址(p=new_p)与对该对象写入值（p_new->a=new_a)之间的关系。
这种关系不是数据依赖关系，于是，任何处理器，都可能对该序列乱序(可能因为缓存或预取的原因)：

p = new_p;

p_new->a = new_a;

所以，这里一个显式的写屏障，就是必须的，即：
p_new->a = new_a;
wmb();
p = new_p;


这里面，读，写两端的屏障指令要配对使用才能保证。即，单独的读者端屏障或单独的写者端屏障都不能
保证实际的发生顺序如预期。因为单独的写屏障，仅表示对于外界，发布写指令的次序是这样的，但不保证
读的人会按指定次序读（缓存或其他的原因）;  单独的读屏障， 仅表示自己是按照指定的次序读，但不
保证写的人是按指定次序。

jiufei19

回复 14# l4rmbr


    在请l4rmbr帮我解答下我的这个问题：

    为啥在__sock_create中保留了rcu_deference，而在list.h中却完全去掉了这个rcu_deference呢？

    我再次仔细阅读了http://lwn.net/Articles/262464/?format=printable这篇文章中所举的如下例子，发现一个该例子所依赖的上下文的问题，或许是可以解释我的疑问。

  1 struct foo {
  2   int a;
  3   int b;
  4   int c;
  5 };
  6 struct foo *gp = NULL;
  7
  8 /* . . . */
  9
10 p = kmalloc(sizeof(*p), GFP_KERNEL);
11 p->a = 1;
12 p->b = 2;
13 p->c = 3;
14 gp = p;

这里gp是一个全局变量，所以存在其他的reader可以并发读取该变量的可能性，然后从10-14行可以看作是updater的行为。这里的一个上下文就是该例子中申请了一个内存区域，并用了另外一个指针变量p来指向该区域，所以也才有后文所描述的语句的执行顺序问题，因此也才有了rcu_assign_pointer和rcu_deference出现的解决方案，来避免由于读写顺序的不同所导致的错误问题。

而在诸如hlist_for_each_entry_rcu这种宏当中，可以看到：
  972 #define hlist_for_each_entry_rcu(tpos, pos, head, member)        \
  973     for (pos = (head)->first;                    \
  974          rcu_dereference(pos) && ({ prefetch(pos->next); 1;}) &&     \
  975         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
  976          pos = pos->next)

这里的pos实际是本地的局部指针变量，所以，似乎这里的rcu_deference根本就没有必要出现了，因为和刚才所举的那个gp的例子的上下文完全不一样，即此时pos是当前正在执行此宏的reader的临时对象，它要么指向尚未被更新的head，要么指向已经更新后的head，这两种情况都是正常的。

我这样的理解是否正确？然而即使正确，则仍然无法解释__sock_create中使用rcu_deference的原因

asuka2001

回复 14# l4rmbr

1）恩，我是确认 DEC alpha同样保证有数据依赖的内存读取的顺序性。即不论预读与否，总是先 LOAD p；然后再 LOAD p->a。

     至于 DEC alpha需要 data dependency barrier的原因 Documentation/memory-barrier.txt里写的很清楚：

[!] Note that this extremely counterintuitive situation arises most easily on
machines with split caches, so that, for example, one cache bank processes
even-numbered cache lines and the other bank processes odd-numbered cache
lines.  The pointer P might be stored in an odd-numbered cache line, and the
variable B might be stored in an even-numbered cache line.  Then, if the
even-numbered bank of the reading CPU's cache is extremely busy while the
odd-numbered bank is idle, one can see the new value of the pointer P (&B),
but the old value of the variable B (2).

2) 我想说明的是需要 data dependency barrier的原因不在于预读！而是 split cache的更新顺序与写者的实际 store顺序不一致！

jiufei19

回复 16# asuka2001


    也请asuka2001帮我看看我的那个问题，谢谢

asuka2001

回复 17# jiufei19

sigh，你可以看看最新的代码么？

/**
* hlist_for_each_entry_rcu - iterate over rcu list of given type
* @pos:        the type * to use as a loop cursor.
* @head:       the head for your list.
* @member:     the name of the hlist_node within the struct.
*
* This list-traversal primitive may safely run concurrently with
* the _rcu list-mutation primitives such as hlist_add_head_rcu()
* as long as the traversal is guarded by rcu_read_lock().
*/
#define hlist_for_each_entry_rcu(pos, head, member)                     \
        for (pos = hlist_entry_safe (rcu_dereference_raw(hlist_first_rcu(head)),\
                        typeof(*(pos)), member);                        \
                pos;                                                    \
                pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
                        &(pos)->member)), typeof(*(pos)), member))

我想l4rmbr其实已经授之以渔了，你觉得呢：）

jiufei19

l4rmbr 发表于 2014-04-22 17:10
Hi, jiufei19,

抱歉，一开始没仔细阅读你的问题，没回答你真正问的

今天仔细阅读了下l4rmbr之前对我的问题的如下说明：
------------------------------------------------------------
这里可能出现的乱序是在pos取值 与 访问pos->member之间， 激进优化的处理器（如文中所提到
的DEC Alpha) 就会做这种事。 本来应该先读pos, 再来读pos->member, 这是合理也直观的次序，
但这种处理器可能会先预读pos->member, 等读了pos, 再来判断之前使用的pos是不是对的。对的
还好；不对就麻烦了，重读。 但我们之前已经用prefetch预读了，这样做相当于浪费了。
------------------------------------------------------------

但是经过仔细阅读http://lwn.net/Articles/262464/?format=printable后，我认为pos和pos->member之间是不会有乱序现象发生的，因为pos是局部变量，并不符合http://lwn.net/Articles/262464/?format=printable一文中所举示例的说明。不知l4rmbr认为是否正确？

asuka2001

回复 19# jiufei19

如果对内存一致性问题感兴趣，你可以去读 Document/memory-barrier.txt

这里 pos与 pos->member是存在乱序的。可以参见我16楼引用文字中的红色部分！