免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
123下一页
最近访问板块 发新帖
查看: 9936 | 回复: 20

[内核同步] list_for_each_entry_rcu的问题【尚未解决】 [复制链接]

论坛徽章:
1
IT运维版块每日发帖之星
日期:2015-11-17 06:20:00
发表于 2014-04-22 16:17 |显示全部楼层
本帖最后由 jiufei19 于 2014-04-22 20:59 编辑

正在仔细学习RCU的机制,对下面这个宏有点不明白,请各位指点下,谢谢!

  645 #define list_for_each_entry_rcu(pos, head, member) \
  646     for (pos = list_entry((head)->next, typeof(*pos), member); \
  647         prefetch(rcu_dereference(pos)->member.next), \
  648             &pos->member != (head); \
  649         pos = list_entry(pos->member.next, typeof(*pos), member))

我的问题是rcu_dereference为啥不对(head)->next进行处理呢,而只是在prefetch中?

论坛徽章:
0
发表于 2014-04-22 16:33 |显示全部楼层
回复 1# jiufei19


(head)->next是在初始化中访问一次,之后不用,而
rcu_dereference(pos)->member.next则是在遍历过程中下一个要访问的节点,
这里的实现用prefetch宏先预读, 即读入缓存行,能保证缓存的100%命中。

prefetch是架构相关的函数 ,每个架构都可以用自己的预读内存数据到缓存行中的指令实现该宏。

论坛徽章:
1
IT运维版块每日发帖之星
日期:2015-11-17 06:20:00
发表于 2014-04-22 16:37 |显示全部楼层
本帖最后由 jiufei19 于 2014-04-22 16:44 编辑

回复 2# l4rmbr


    谢谢l4rmbr的答复。不过我还是有点不明白,如果在初始化的那个时刻,正好有个线程在更改(head)->next呢,难道这个更改也就是一个updater,不影响reader的行为吗?

  对此,请看看下面一段原文http://www.rdrop.com/users/paulmck/RCU/whatisRCU.html

1. RCU OVERVIEW

The basic idea behind RCU is to split updates into "removal" and "reclamation" phases. The removal phase removes references to data items within a data structure (possibly by replacing them with references to new versions of these data items), and can run concurrently with readers. The reason that it is safe to run the removal phase concurrently with readers is the semantics of modern CPUs guarantee that readers will see either the old or the new version of the data structure rather than a partially updated reference.

上面这段话中红色字体的内容似乎在说明对reader而言,updater可以自由去remove,但是如果这样的话,那么后面的预取咋就必须rcu了呢,我彻底晕了

论坛徽章:
0
发表于 2014-04-22 17:10 |显示全部楼层
本帖最后由 l4rmbr 于 2014-04-22 17:12 编辑
jiufei19 发表于 2014-04-22 16:37
回复 2# l4rmbr


Hi, jiufei19,

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

是这样的,你的疑问是合理的,其实这个遍历宏是必须在rcu_read_lock()和rcu_read_unlock()
包围的临界区里才能正确使用。 举个例子:

  1. rcu_read_lock();
  2. list_for_each_entry_rcu(child, &cgrp->children, sibling) {
  3.            empty = cgroup_is_dead(child);
  4.             if (!empty)
  5.                      break;
  6. }
  7. rcu_read_unlock();
复制代码
可以看出,这个宏是在rcu临界区里的,所以, head->next的访问也是被rcu保护的。

可能是rcu_dereference有个让人疑惑,以为只有它被保护

至于 prefetch(rcu_dereference(pos)->member.next)为什么需要rcu_dereference()
来解引用, 这里面是另外一个问题,即考虑到乱序的问题。

假设 prefetch(pos->member.next), 即没有rcu_dereference。
这一句是预取下一个即将访问的节点,然后在下一个循环,我们就要做判断:
  1. pos = list_entry(pos->member.next, typeof(*pos), member)
  2. pos->member != (head)
复制代码
看是不是遍历一圈了。

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

所以, rcu_dereference在这里有必要。

论坛徽章:
1
IT运维版块每日发帖之星
日期:2015-11-17 06:20:00
发表于 2014-04-22 17:25 |显示全部楼层
本帖最后由 jiufei19 于 2014-04-22 17:38 编辑

回复 4# l4rmbr


  谢谢l4rmbr ,经你这么一解释,至少这点似乎明白了些,即如果没有prefetch操作的话,那么实际上这里并不需要rcu_deference的,对吧?



  好像彻底明白了

As with rcu_assign_pointer(), an important function of rcu_dereference() is to document which pointers are protected by RCU. And, again like rcu_assign_pointer(), rcu_dereference() is typically used indirectly, via the _rcu list-manipulation primitives, such as list_for_each_entry_rcu().

这里明确了在list_for_each_entry_rcu()中indirectly使用了rcu_dereference(),应该就是l4rmbr之前所说的在调用该宏之前,首先使用 rcu_read_lock()来保护,而之所以后面再次显式使用rcu_deference的原因是有那个特殊的prefetch导致的,我好像理解对了也!

再次感谢l4rmbr!

论坛徽章:
0
发表于 2014-04-22 17:43 |显示全部楼层
本帖最后由 l4rmbr 于 2014-04-22 17:49 编辑
jiufei19 发表于 2014-04-22 17:25
回复 4# l4rmbr


Hi, jiufei19,

可以不用。[<-这个是回答OP之前提问的,不过他修改了,他问的是 "如果不用prefetch, 是不是可以不用rcu_dereference()?"]

另,我不清楚你贴的代码是哪个版本的,至少在3年前,该宏实现中就去掉了预取了,是Linus本人提交的,详见:
https://git.kernel.org/cgit/linu ... da62f3b5286c8cc4f9f

个人建议学习不要跟着旧代码来学,follow着Linus的git tree, 研究最新代码, 善用git的历史版本管理功能,学习起来
能知前知后,还能保持知识最新,发现问题还可以给社区提交patch。我个人觉得这样做最好,仅供参考。

论坛徽章:
1
IT运维版块每日发帖之星
日期:2015-11-17 06:20:00
发表于 2014-04-22 18:00 |显示全部楼层
本帖最后由 jiufei19 于 2014-04-22 18:06 编辑

回复 6# l4rmbr


    我一直看的代码是2.6.23,非常感谢你的建议,你文中给出的那个git链接就是你建议的那个东东吗?

   by the way,刚才我的理解是否正确,即那个所谓的indiectly使用的意思就是在该宏调用前,先有rcu_read_lock()的调用?

论坛徽章:
0
发表于 2014-04-22 19:32 |显示全部楼层
jiufei19 发表于 2014-04-22 18:00
回复 6# l4rmbr


引文的意思其实是说rcu_dereference一般被间接的使用在rcu链表中,如你代码所贴的for_each_list_entry_rcu.  
我觉得你理解了。 至于那个链接,那是一次git提交,我的意思是用git clone下来的源码来学习,而不是去官方站点
把整个源码包下下来学习。原因是前者包含着提交历史,可以方便地用git blame,  git show等命令查看提交引入的
原因,以帮助学习理解。

论坛徽章:
1
IT运维版块每日发帖之星
日期:2015-11-17 06:20:00
发表于 2014-04-22 20:58 |显示全部楼层
本帖最后由 jiufei19 于 2014-04-22 23:34 编辑

回复 8# l4rmbr

但是,我还是有点疑问,我喜欢刨根问底哈:wink:

请看如下的代码示例,取自http://www.rdrop.com/users/paulmck/RCU/whatisRCU.html



对于一个updater,

void foo_update_a(int new_a)
{
        struct foo *new_fp;
        struct foo *old_fp;

        new_fp = kmalloc(sizeof(*fp), GFP_KERNEL);
        spin_lock(&foo_mutex);
        old_fp = gbl_foo;
        *new_fp = *old_fp;
        new_fp->a = new_a;
        rcu_assign_pointer(gbl_foo, new_fp);
        spin_unlock(&foo_mutex);
        synchronize_rcu();
        kfree(old_fp);
}



对于一个reader,

int foo_get_a(void)
{
        int retval;
        rcu_read_lock();
        retval = rcu_dereference(gbl_foo)->a;
        rcu_read_unlock();
        return retval;
}

显然,在一个reader中要访问一个会被updater修改的指针时,既要使用rcu_read_lock,同时还要通过rcu_deference来获得可能被并发访问所更新的那个指针。那么为什么在list_for_each_entry_rcu的宏实现中,假设去掉那个prefetch,则就并没有任何rcu_deference的调用了,那么上面的示例代码是什么意思?

进一步,我更加困惑的是,我在搜索linux的内核版本时,发现好像从2.6.30开始,list.h中根本就没有这个rcu_deference了,难道RCU机制没有在内核的后续list.h中保留了吗?但是在搜索比如socket.c文件中,可以看到__sock_create函数中的确还是有rcu_deference的使用,这到底是咋回事呢?

对于这里的疑惑,我们再来看看http://lwn.net/Articles/262464/?format=printable,其中有如下一段话或许有助于理解

Quick Quiz 2: What prevents the list_for_each_entry_rcu() from getting a segfault if it happens to execute at exactly the same time as the list_add_rcu()?

Answer: On all systems running Linux, loads from and stores to pointers are atomic, that is, if a store to a pointer occurs at the same time as a load from that same pointer, the load will return either the initial value or the value stored, never some bitwise mashup of the two. In addition, the list_for_each_entry_rcu() always proceeds forward through the list, never looking back. Therefore, the list_for_each_entry_rcu() will either see the element being added by list_add_rcu(), or it will not, but either way, it will see a valid well-formed list.

这里似乎明确说明了在list_for_each_entry_rcu中,可以对(head)->next不使用rcu_deference的理由,即无论此时list_add_rcu如何并发,反正(head)->next都会明确指向要么是之前的链表头部,要么是添加新节点后的链表头部,都是稳定的值。

但是,如果这个解释是正确的话,那么我们来看看__sock_create()中的一段代码该做何解释?

static int __sock_create(int family, int type, int protocol,                                                                                                         
                                           struct socket **res, int kern)
{
      ...
      sock->type = type;
      rcu_read_lock();  
      // get the corresponding struct net_proto_family in the array
      // of net_families for this @family
      pf = rcu_dereference(net_families[family]);
      err = -EAFNOSUPPORT;
      if (!pf)
          goto out_release;
  
      // We will call the ->create function, that possibly is in a
      // loadable module, so we have to bump that loadable
      // module refcnt first.
      if (!try_module_get(pf->owner))
          goto out_release;
      /* Now protected by module ref count */
      rcu_read_unlock();
      ...
}

这里,红色字体语句就是上文中说的loads from,那么此时为啥需要使用rcu_deference来获得pf呢,根据上文的解释理由,要么这里能得到对应此family的pf,要么不能得到,有什么必要必须rcu_deference呢?

关于这个RCU的问题,我现在依然困惑无比,烦请l4rmbr解惑,谢谢!
   

论坛徽章:
0
发表于 2014-04-23 00:33 |显示全部楼层
本帖最后由 l4rmbr 于 2014-04-23 00:53 编辑
jiufei19 发表于 2014-04-22 20:58
回复 8# l4rmbr

但是,我还是有点疑问,我喜欢刨根问底哈


Hi, jiufei19,

rcu_dereference()其实跟rcu机制没关系,这个名字其实起了文档的作用,表示它要在rcu保护的临界区内使用。

至于它本身的真正作用,如前面答案所提,它其实起到防止乱序的作用。
细究其代码,最终真正生效的是这两行:
  1. r = rcu_dereference(p)
  2. 等价于
  3. r = ACCESS_ONCE(p);
  4. smp_read_barrier_depends();
复制代码
它的作用是防止编译器和处理器两个层次的乱序。

为什么要防止。看例子:
  1. 读者端:
  2.   1 p = gp;
  3.   2 if (p != NULL) {
  4.   3   do_something_with(p->a, p->b, p->c);
  5.   4 }
复制代码
  1. 写者端:
  2. p->a = 1;
  3. p->b = 2;
  4. p->c = 3;
  5. gp = p;
复制代码
这里大家会有个假设:
读者端:先读p = gp, 然后再依次访问p->a, p->b, p->c,
写者端:先依次写p->a, p->b, p->c, 然后再赋值给gp.

这是很合理的,也直观的假设,逻辑正确,很多处理器都保持这样的基本的假定。
但是DEC Alpha架构的处理器+指令预测的编译器,可以观察到如此激进的优化:
  1. 它先猜测p的值,然后预取p->a, p->b, p->b;然后再取p, 来判断p是否猜测正确。
复制代码
那么,就会出现这种情况:
读者端先预测到p会被加载进gp的地址, 所以它高兴地先预读进来(p = gp),然后读了p->a, p->b, p->c的值。
注意,此时写端的赋值可能还没发生,所以读端预读到的可能是原来旧的值,假设依次为9, 8, 7
然后,等下p真的被加载进gp的地址了,处理器检查一下,发现:呀,我真聪明,预取对了,所以它就理所当然地
认为p-a, p->b, p->c是它之前预取的值。

但是, 这中间,写端可能已经写了新值,即p->a=1, p->b=2, p->c=3

这样就出了大问题了, 读者端自作聪明的预读,结果读到了旧值,它还以为是正确的。

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

比如
  1. 读者端:
  2.   1 p = gp;
  3.     ###  smp_read_barrier_depends ###
  4.   2 if (p != NULL) {
  5.   3   do_something_with(p->a, p->b, p->c);
  6.   4 }
复制代码
  1. 写者端:
  2. p->a = 1;
  3. p->b = 2;
  4. p->c = 3;
  5. ### smp_mb  ###  
  6. gp = p;
复制代码
加上这两个屏障后,就可以保证,只要在读者端看到p是gp, 那么p->a, p->b ,p->c一定是最新的;因为,写者端也有一个屏障,它保证了先更新p->a, p->b, p->c后再更新gp = p

因此, rcu_dereference() 不过就是加载指针 , 再加一个屏障的封装
而rcu_assign_pointer()不过就是一个屏障,再加赋值指针的封装


可以注意到,屏障指令在读写两端都需要的,而且使用的顺序相反。只有读,写两端配合,才能保证想要的顺序。

关于这个内存屏障,可以参考我之前写过的文章:Linux内核中的内存屏障(1)
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP