2018-05-09 09:21:21 juS3Ve 阅读数 729

本文简介

本文作者,人称中兴通信内核老中医。本文介绍Linux RCU的用法及其API。这不是一篇单独的文章,这是《谢宝友:深入理解Linux RCU》系列的第4篇,前序文章:

谢宝友: 深入理解Linux RCU之一——从硬件说起

谢宝友:深入理解Linux RCU:从硬件说起之内存屏障

谢宝友:深入理解RCU之三:概念


作者简介

         谢宝友,在编程一线工作已经有20年时间,其中接近10年时间工作于Linux操作系统。在中兴通讯操作系统产品部工作期间,他作为技术总工参与的电信级嵌入式实时操作系统,获得了行业最高奖----中国工业大奖。同时,他也是《深入理解并行编程》一书的译者。

联系方式: mail:scxby@163.com 微信:linux-kernel

640?wx_fmt=jpeg

稿件征集

欢迎您给Linuxer投稿,赢得人民邮电异步社区任意在售技术图书。您随便挑,详情:

Linuxer-"Linux开发者自己的媒体"第四月稿件录取和赠书名单


走过路过,不要错过Linuxer哦,点击二维码关注Linuxer!

640?wx_fmt=png

640?wx_fmt=png

一、

RCU的用法640?wx_fmt=png

RCU最常用的目的是替换已有的机制,如下所示:

  • 读写锁

  • 受限制的引用计数机制

  • 批量引用计数机制

  • 穷人版的垃圾回收器

  • 存在担保

  • 类型安全的内存

  • 等待事物结束

1.1 RCU是读写锁的替代者

Linux内核中,RCU最常见的用途是替换读写锁。在20世纪90年代初期,Paul在实现通用RCU之前,实现了一种轻量级的读写锁。后来,为这个轻量级读写锁原型所设想的每个用途,最终都使用RCU来实现了。

RCU和读写锁最关键的相似之处,在于两者都有可以并行执行读端临界区。事实上,在某些情况下,完全可以用对应的读写锁API来替换RCUAPI,反之亦然。

RCU的优点在于:性能、不会死锁,以及良好的实时延迟。当然RCU也有一点缺点,比如:读者与更新者并发执行,低优先级RCU读者也可以阻塞正等待优雅周期(Grace Period)结束的高优先级线程,优雅周期的延迟可能达到好几毫秒。

640?wx_fmt=png

上图是不是略显奇怪,RCU读端延迟竟然小于一个CPU周期?这不是开玩笑,因为有某些实现中(例如,服务器Linux),RCU读端就完全是一个空操作。当然,在这样的实现中,它可能会包含一个编译屏障,因此也会对性能产生那么一点点影响。

注意,在单个CPU上读写锁比RCU慢一个数量级,在16CPU上读写锁比RCU几乎要慢两个数量级。随着CPU数量的增加,RCU的扩展性优势越来越突出。可以这么说,RCU几乎就是水平扩展,这可以在上图中看出来。

当内核配置了CONFIG_PREEMPT的时候,RCU仍然超过了读写锁一到三个数量级,如下图所示。请注意:读写锁在CPU数目很多时的陡峭曲线。

640?wx_fmt=png

当然,上图中的临界区长度为0,这夸大了读写锁的性能劣势。随着临界区的加大,RCU的性能优势也不再显著。在下图中,有16CPUy轴代表读端原语的总开销,x轴代表临界区长度。

 

640?wx_fmt=png

然而,一般说来,临界区都能在几个毫秒内完成,所以总的来说,在性能方面,测试结果对RCU是有利的。

另外,RCU读端原语基本上是不会死锁的。因为它本身就属于无锁编程的范畴。

这种免于死锁的能力来源于RCU的读端原语不阻塞、不自旋,甚至不存在向后跳转语句,所以RCU读端原语的执行时间是确定的。这使得RCU读端原语不可能形成死锁循环。

RCU读端免于死锁的能力带来了一个有趣的后果:RCU读者可以恣意地升级为RCU更新者。在读写锁中尝试这种升级则会有可能造成死锁。进行RCU读者到更新者升级的代码片段如下所示:

1  rcu_read_lock();

2  list_for_each_entry_rcu(p,  &head,  list_field)  {

3     do_something_with(p);

4     if  (need_update(p))  {

5         spin_lock(my_lock);

6         do_update(p);

7         spin_unlock(&my_lock);

8     }

9  }

10  rcu_read_unlock();

请注意,do_update()是在锁的保护下执行,也是RCU读端的保护下执行。

RCU免于死锁的特性带来的另一个有趣后果是RCU不会受优先级反转问题影响。比如,低优先级的RCU读者无法阻止高优先级的RCU更新者获取更新端锁。类似地,低优先级的更新者也无法阻止高优先级的RCU读者进入RCU读端临界区。

另一方面,因为RCU读端原语既不自旋也不阻塞,所以这些原语有着极佳的实时延迟。而自旋锁或者读写锁都存在不确定的实时延迟。

但是,RCU还是会受到更隐晦的优先级反转问题影响,比如,在等待RCU优雅周期结束而阻塞的高优先级进程,会被-rt内核的低优先级RCU读者阻塞。这可以用RCU优先级提升来解决。

再一方面,因为RCU读者既不自旋也不阻塞,RCU更新者也没有任何类似回滚或者中止的语义,所以RCU读者和更新者可以并发执行。这意味着RCU读者有可能访问旧数据,还有可能发现数据不一致,无论这两个问题中的哪一个,都让读写锁有卷土重来的机会。

不过,令人吃惊的是,在大量情景中,数据不一致和旧数据都不是问题。网络路由表是一个经典例子。因为路由的更新可能要花相当长一段时间才能到达指定系统(几秒甚至几分钟),所以系统可能会在新数据到来后的一段时间内,仍然将报文发到错误的地址去。通常,在几毫秒内将报文发送到错误地址并不算什么问题。

简单地说,读写锁和RCU提供了不同的保证。在读写锁中,任何在写者之后开始的读者都“保证”能看到新值。与之相反,在RCU中,在更新者完成后才开始的读者都“保证”能看见新值,在更新者开始后才完成的读者有可能看见新值,也有可能看见旧值,这取决于具体的时机。

在实时RCUSRCUQRCU中,被抢占的读者将阻止正在进行中的优雅周期的完成,即使有高优先级的任务在等待优雅周期完成时也是如此。实时RCU可以通过用call_rcu()替换synchronize_rcu()来避免此问题,或者采用RCU优先级提升来避免。

除了那些“玩具”RCU实现,RCU优雅周期可能会延续好几个毫秒。这使得RCU更适于使用在读数据占多数的情景。

将读写锁转换成RCU非常简单,如下:

640?wx_fmt=gif

640?wx_fmt=gif

640?wx_fmt=gif


1.2 RCU是一种受限制的引用计数机制

因为优雅周期不能在RCU读端临界区进行时结束,所以RCU读端原语可以像受限的引用计数机制一样使用。比如考虑下面的代码片段:

1  rcu_read_lock();             /*  acquire  reference.  */

2  p  =  rcu_dereference(head);

3  /*  do  something  with  p.  */

4  rcu_read_unlock();            /*  release  reference.  */

rcu_read_lock()原语可以看作是获取对p的引用,因为相应的优雅周期无法在配对的rcu_read_unlock()之前结束。这种引用计数机制是受限制的,因为我们不允许在RCU读端临界区中阻塞,也不允许将一个任务的RCU读端临界区传递给另一个任务。

不管上述的限制,下列代码可以安全地删除p

1  spin_lock(&mylock);

2  p  =  head;

3  rcu_assign_pointer(head,  NULL);

4  spin_unlock(&mylock);

5  /*  Wait  for  all  references  to  be  released.  */

6  synchronize_rcu();

7  kfree(p);

当然,RCU也可以与传统的引用计数结合。但是为什么不直接使用引用计数?部分原因是性能,如下图所示,图中显示了在163GHz CPUIntel x86系统中采集的数据。

640?wx_fmt=png

和读写锁一样,RCU的性能优势主要来源于较短的临界区,如下图所示。

640?wx_fmt=png

1.3 RCU是一种可大规模使用的引用计数机制

如前所述,传统的引用计数通常与某种或者一组数据结构有联系。然而,维护一组数据结构的全局引用计数,通常会导致包含引用计数的缓存行来回“乒乓”。这种缓存行“乒乓”会严重影响系统性能。

相反,RCU的轻量级读端原语允许读端极其频繁地调用,却只带来微不足道的性能影响,这使得RCU可以作为一种几乎没有性能损失的“批量引用计数机制”。当某个任务需要在一大段代码中持有引用时,可以使用可睡眠RCUSRCU)。但是,一个任务不能将引用锁引用传递给另一个任务。例如:在开始一次I/O时获取引用,然后当对应的I/O完成时在中断处理函数里释放该引用。

1.4 RCU是穷人版的垃圾回收器

当人们刚开始学习RCU时,有种比较少见的感叹是“RCU有点像垃圾回收器!”。这种感叹有一部分是对的,不过还是会给学习造成误导。

也许思考RCU与垃圾自动回收器(GC)之间关系的最好办法是,RCU类似自动决定回收时机的GC,但是RCUGC有几点不同:(1)程序员必须手动指示何时可以回收指定数据结构,(2)程序员必须手动标出可以合法持有引用的RCU读端临界区。

尽管存在这些差异,两者的相似程度仍然相当高,至少有一篇理论分析RCU的文献曾经分析过两者的相似度。

1.5 RCU是一种提供存在担保的方法

通过锁来提供存在担保有其不利之处。与锁类似,如果任何受RCU保护的数据元素在RCU读端临界区中被访问,那么数据元素在RCU读端临界区持续期间保证存在。

1  int  delete(int  key)

2  {

3     struct  element  *p;

4     int  b;

5     5

6     b  =  hashfunction(key);

7     rcu_read_lock();

8     p  =  rcu_dereference(hashtable[b]);

9     if  (p  ==  NULL  ||  p->key  !=  key)  {

10         rcu_read_unlock();

11         return  0;

12     }

13     spin_lock(&p->lock);

14     if  (hashtable[b]  ==  p  &&  p->key  ==  key)  {

15         rcu_read_unlock();

16         hashtable[b]  =  NULL;

17         spin_unlock(&p->lock);

18         synchronize_rcu();

19         kfree(p);

20         return  1;

21     }

22     spin_unlock(&p->lock);

23     rcu_read_unlock();

24     return  0;

25  }

上图展示了基于RCU的存在担保如何通过从哈希表删除元素的函数来实现每数据元素锁。第6行计算哈希函数,第7行进入RCU读端临界区。如果第9行发现哈希表对应的哈希项(bucket)为空,或者数据元素不是我们想要删除的那个,那么第10行退出RCU读端临界区,第11行返回错误。

如果第9行判断为false,第13行获取更新端的自旋锁,然后第14行检查元素是否还是我们想要的。如果是,第15行退出RCU读端临界区,第16行从哈希表中删除找到的元素,第17行释放锁,第18行等待所有之前已经存在的RCU读端临界区退出,第19行释放刚被删除的元素,最后第20行返回成功。如果14行的判断发现元素不再是我们想要的,那么第22行释放锁,第23行退出RCU读端临界区,第24行返回错误以删除该关键字。

1.6 RCU是一种提供类型安全内存的方法

很多无锁算法并不需要数据元素在被RCU读端临界区引用时保持完全一致,只要数据元素的类型不变就可以了。换句话说,只要数据结构类型不变,无锁算法可以允许某个数据元素在被其他对象引用时被释放并重新分配,但是决不允许类型上的改变。这种“保证”,在学术文献中被称为“类型安全的内存”,它比前一节提到的存在担保要弱一些,因此处理起来也要困难一些。类型安全的内存算法在Linux内核中的应用是slab缓存,被SLAB_DESTROY_BY_RCU标记专门标出来的缓存通过RCU将已释放的slab返回给系统内存。在任何已有的RCU读端临界区持续期间,使用RCU可以保证所有带有SLAB_DESTROY_BY_RCU标记且正在使用的slab元素仍然在该slab中,类型保持一致。

虽然基于类型安全的无锁算法在特定情景下非常有效,但是最好还是尽量使用存在担保。毕竟简单总是更好的。

1.7 RCU是一种等待事物结束的方式

RCU的一个强大之处,就是允许你在等待上千个不同事物结束的同时,又不用显式地去跟踪其中每一个事物,因此也就无需担心性能下降、扩展限制、复杂的死锁场景、内存泄露等显式跟踪机制本身的问题。

下面展示如何实现与不可屏蔽中断(NMI)处理函数的交互,如果用锁来实现,这将极其困难。步骤如下:

1.做出改变,比如,OS对一个NMI做出反应。在NMI中使用RCU读端原语。

2.等待所有已有的读端临界区完全退出(比如使用synchronize_sched()原语)。

3.扫尾工作,比如,返回表明改变成功完成的状态。

下面是一个Linux内核中的例子。在这个例子中,timer_stop()函数使用synchronize_sched()确保在释放相关资源之前,所有正在处理的NMI处理函数已经完成。

1  struct  profile_buffer  {

2     long  size;

3     atomic_t  entry[0];

4  };

5  static  struct  profile_buffer  *buf  =  NULL;

6

7  void  nmi_profile(unsigned  long  pcvalue)

8  {

9     struct  profile_buffer  *p  = 

                                                                rcu_dereference(buf);

10

11     if  (p  ==  NULL)

12         return;

13     if  (pcvalue  >=  p->size)

14         return;

15     atomic_inc(&p->entry[pcvalue]);

16  }

17

18  void  nmi_stop(void)

19  {

20     struct  profile_buffer  *p  =  buf;

21

22     if  (p  ==  NULL)

23         return;

24     rcu_assign_pointer(buf,  NULL);

25     synchronize_sched();

26     kfree(p);

27  }

14行定义了profile_buffer结构,包含一个大小和一个变长数组的入口。第5行定义了指向profile_buffer的指针,这里假设别处对该指针进行了初始化,指向内存的动态分配区。

716行定义了nmi_profile()函数,供NMI中断处理函数调用。该函数不会被抢占,也不会被普通的中断处理函数打断,但是,该函数还是会受高速缓存未命中、ECC错误以及被同一个核的其他硬件线程抢占时钟周期等因素影响。第9行使用rcu_dereference()原语来获取指向profile_buffer的本地指针,这样做是为了确保在DECAlpha上的内存顺序执行,如果当前没有分配profile_buffer,第11行和12行退出,如果参数pcvalue超出范围,第1314行退出。否则,第15行增加以参数pcvalue为下标的profile_buffer项的值。请注意,profile_buffer结构中的size保证了pcvalue不会超出缓冲区的范围,即使突然将较大的缓冲区替换成了较小的缓冲区也是如此。

1827行定义了nmi_stop()函数,由调用者负责互斥访问(比如持有正确的锁)。第20行获取profile_buffer的指针,如果缓冲区为空,第2223行退出。否则,第24行将profile_buffer的指针置NULL(使用rcu_assign_pointer()原语在弱顺序的机器中保证内存顺序访问),第25行等待RCU Sched的优雅周期结束,尤其是等待所有不可抢占的代码——包括NMI中断处理函数——结束。一旦执行到第26行,我们就可以保证所有获取到指向旧缓冲区指针的nmi_profile()实例都已经返回了。现在可以安全释放缓冲区,这时使用kfree()原语。

简而言之,RCUprofile_buffer动态切换变得更简单,你可以试试原子操作,也可以用锁来折磨下自己。注意考虑到如下一点:在大多数CPU架构中,原子操作和锁都可能存在循环语句,在循环的过程中可能会被NMI中断。

640?wx_fmt=png二、RCU API640?wx_fmt=png


2.1 等待完成的API


640?wx_fmt=gif

RCU Classic”一列对应的是RCU的原始实现,rcu_read_lock()rcu_read_unlock()原语标示出RCU读端临界区,可以嵌套使用。对应的同步的更新端原语synchronize_rcu()synchronize_net()都是等待当前正在执行的RCU读端临界区退出。等待时间被称为“优雅周期”。异步的更新端原语call_rcu()在后续的优雅周期结束后调用由参数指定的函数。比如,call_rcu(p, f);在优雅周期结束后执行RCU回调f(p)

想要利用基于RCU的类型安全的内存,要将SLAB_DESTROY_BY_RCU传递给kmem_cache_create()。有一点很重要,SLAB_DESTROY_BY_RCU不会阻止kmem_cache_alloc()立即重新分配刚被kmem_cache_free()释放的内存!事实上,由rcu_dereference返回的受SLAB_DESTROY_ BY_RCU标记保护的数据结构可能会释放——重新分配任意次,甚至在rcu_read_lock()保护下也是如此。但是,SLAB_DESTROY_BY_RCU可以阻止kmem_cache_free()RCU优雅周期结束之前,它所返回数据结构的完全释放给SLAB。一句话,虽然数据元素可能被释放——重新分配N次,但是它的类型是保持不变的。

2.2 订阅和版本维护API

640?wx_fmt=gif

表中的第一类API作用于Linuxstruct list_head循环双链表。list_for_each_ entry_rcu()原语以类型安全的方式遍历受RCU保护的链表。在非Alpha的平台上,该原语相较于list_for_each_entry()原语不产生或者只带来极低的性能惩罚。list_add_rcu()list_add_tail_rcu()list_replace_rcu()原语都是对非RCU版本的模拟,但是在弱顺序的机器上回带来额外的内存屏障开销。list_del_rcu()原语同样是非RCU版本的模拟,但是奇怪的是它要比非RCU版本快一点,这是由于list_del_rcu()只毒化prev指针,而list_del()会同时毒化prevnext指针。最后,list_splice_init_rcu()原语和它的非RCU版本类似,但是会带来一个完整的优雅周期的延迟。

表中的第二类API直接作用于Linuxstruct hlist_head线性哈希表。struct hlist_headstructlist_head高级一点的地方是前者只需要一个单指针的链表头部,这在大型哈希表中将节省大量内存。表中的struct hlist_head原语与非RCU版本的关系同struct list_head原语的类似关系一样。

表中的最后一类API直接作用于指针,这对创建受RCU保护的非链表数据元素非常有用,比如受RCU保护的数组和树。rcu_assign_pointer()原语确保在弱序机器上,任何在给指针赋值之前进行的初始化都将按照顺序执行。同样,rcu_dereferece()原语确保后续指针解引用的代码可以在Alpha CPU上看见对应的rcu_assign_pointer()之前进行的初始化的结果。 

 

640?wx_fmt=png

本文未完待续

敬请关注Linuer期待来下篇!

640?wx_fmt=png


苹果用户打赏

640?wx_fmt=png

安卓用户打赏


2017-11-04 00:00:00 juS3Ve 阅读数 1288

本文简介

本文介绍Linux RCU的基本概念。这不是一篇单独的文章,这是《谢宝友:深入理解Linux RCU》系列的第3篇,前序文章:


谢宝友: 深入理解Linux RCU之一——从硬件说起

谢宝友:深入理解Linux RCU:从硬件说起之内存屏障


作者简介

         谢宝友,在编程一线工作已经有20年时间,其中接近10年时间工作于Linux操作系统。在中兴通讯操作系统产品部工作期间,他作为技术总工参与的电信级嵌入式实时操作系统,获得了行业最高奖----中国工业大奖。同时,他也是《深入理解并行编程》一书的译者。

联系方式: mail:scxby@163.com 微信:linux-kernel

稿件征集

欢迎您给Linuxer投稿,赢得人民邮电异步社区任意在售技术图书。您随便挑,详情:

Linuxer-"Linux开发者自己的媒体"首月稿件录取和赠书名单

Linuxer-"Linux开发者自己的媒体"第二月稿件录取和赠书名单

Linuxer-"Linux开发者自己的媒体"第三月稿件录取和赠书名单

一、RCU有什么用?

RCU主要用于对性能要求苛刻的并行实时计算。例如:天气预报、模拟核爆炸计算、内核同步等等。

假设你正在编写一个并行实时程序,该程序需要访问随时变化的数据。这些数据可能是随着温度、湿度的变化而逐渐变化的大气压。这个程序的实时响应要求是如此严格,需要处理的数据量如此巨大,以至于不允许任何自旋或者阻塞,因此不能使用任何锁。

幸运的是,温度和压力的范围通常变化不大,因此使用默认的数据集也是可行的。当温度、湿度和压力抖动时,有必要使用实时数据。但是温度、湿度和压力是逐渐变化的,我们可以在几分钟内更新数据,但没必要实时更新值。

在这种情况下,可以使用一个全局指针,即gptr,通常为NULL,表示要使用默认值。偶尔也可以将gptr指向假设命名为a、b和c的变量,以反映气压的变化。

传统的软件可以使用自旋锁这样的同步机制,来保护gptr指针的读写。一旦旧的值不被使用,就可以将旧指针指向的数据释放。这种简单的方法有一个最大的问题:它会使软件效率下降数个数量级(注意,不是下降数倍而是下降数个数量级)。

在现代计算系统中,向gptr写入a、b、c这样的值,并发的读者要么看到一个NULL指针要么看到指向新结构gptr的指针,不会看到中间结果。也就是说,对于指针赋值来说,某种意义上这种赋值是原子的。读者不会看到a、b、c之外的其他结果。并且,更好的一点,也是更重要的一点是:读者不需要使用任何代价高昂的同步原语,因此这种方法非常适合于实时使用。

真正的难点在于:在读者获得gptr的引用时,它可能看到a、b、c这三个值中任意一个值,写者何时才能安全的释放a、b、c所指向的内存数据结构?

引用计数的方案很有诱惑力,但正如锁和顺序锁一样,引用计数可能消耗掉数百个CPU指令周期,更致命的是,它会引用缓存行在CPU之间的来回颠簸,破坏各个CPU的缓存,引起系统整体性能的下降。很明显,这种选择不是我们所期望的。

想要理解Linux经典RCU实现的读者,应当认真阅读下面这段话:

一种实现方法是,写者完全不知道有哪些读者存在。这种方法显然让读者的性能最佳,但留给写者的问题是:如何才能确定所有的老读者已经完成。

最简单的实现是:让线程不会被抢占,或者说,读者在读RCU数据期间不能被抢占。在这种不可抢占的环境中,每个线程将一直运行,直到它明确地和自愿地阻塞自己(现实世界确实有这样的操作系统,它由线程自己决定何时释放CPU。例如大名鼎鼎的Solaris操作系统)。这要求一个不能阻塞的无限循环将使该CPU在循环开始后无法用于任何其他目的,还要求还要求线程在持有自旋锁时禁止阻塞。否则会形成死锁。

这种方法的示意图下所示,图中的时间从顶部推移到底部,CPU 1的list_del()操作是RCU写者操作,CPU2、CPU3在读端读取list节点。

Linux经典RCU的概念即是如此。虽然这种方法在生产环境上的实现可能相当复杂,但是玩具实现却非常简单。

1  for_each_online_cpu(cpu)

2  run_on(cpu);

for_each_online_cpu()原语遍历所有CPUrun_on()函数导致当前线程在指定的CPU上执行,这会强制目标CPU执行上下文切换。因此,一旦for_each_online_cpu()完成,每个CPU都执行了一次上下文切换,这又保证了所有之前存在的读线程已经完成。

请注意,这个方法不能用于生产环境。正确处理各种边界条件和对性能优化的强烈要求意味着用于生产环境的代码实现将十分复杂。此外,可抢占环境的RCU实现需要读者实际做点什么事情(也就是在读临界区内,禁止抢占。这是Linux经典RCU读锁的实现)。不过,这种简单的不可抢占的方法在概念上是完整的,有助于我们理解RCU的基本原理。

二、RCU是什么?

RCUread-copy-update的简称,翻译为中文有点别扭“读-复制-更新”。它是是一种同步机制,有三种角色或者操作:读者、写者和复制操作,我理解其中的复制操作就是不同CPU上的读者复制了不同的数据值,或者说拥有同一个指针的不同拷贝值,也可以理解为:在读者读取值的时候,写者复制并替换其内容(后一种理解来自于RCU作者的解释)。它于200210月引入Linux内核。

RCU允许读操作可以与更新操作并发执行,这一点提升了程序的可扩展性。常规的互斥锁让并发线程互斥执行,并不关心该线程是读者还是写者,而读/写锁在没有写者时允许并发的读者,相比于这些常规锁操作,RCU在维护对象的多个版本时确保读操作保持一致,同时保证只有所有当前读端临界区都执行完毕后才释放对象。RCU定义并使用了高效并且易于扩展的机制,用来发布和读取对象的新版本,还用于延后旧版本对象的垃圾收集工作。这些机制恰当地在读端和更新端并行工作,使得读端特别快速。在某些场合下(比如非抢占式内核里),RCU读端的函数完全是零开销。

Seqlock也可以让读者和写者并发执行,但是二者有什么区别?

首先是二者的目的不一样。Seqlock是为了保证读端在读取值的时候,写者没有对它进行修改,而RCU是为了多核扩展性。

其次是保护的数据结构大小不一样。Seqlock可以保护一组相关联的数据,而RCU只能保护指针这样的unsigned long类型的数据。

最重要的区别还在于效率,Seqlock本质上是与自旋锁同等重量级的原语,其效率与RCU不在同一个数量级上面。

下面从三个基础机制来阐述RCU究竟是什么?

RCU由三种基础机制构成,第一个机制用于插入,第二个用于删除,第三个用于让读者可以不受并发的插入和删除干扰。分别是:

发布/订阅机制,用于插入。

等待已有的RCU读者完成的机制,用于删除。

维护对象多个版本的机制,以允许并发的插入和删除操作。

 

1、发布/订阅机制

RCU的一个关键特性是可以安全的读取数据,即使数据此时正被修改。RCU通过一种发布/订阅机制达成了并发的数据插入。举个例子,假设初始值为NULL的全局指针gp现在被赋值指向一个刚分配并初始化的数据结构。如下所示的代码片段:

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;



“发布”数据结构(不安全)

不幸的是,这块代码无法保证编译器和CPU会按照编程顺序执行最后4条赋值语句。如果对gp的赋值发生在初始化p的各字段之前,那么并发的读者会读到未初始化的值。这里需要内存屏障来保证事情按顺序发生,可是内存屏障又向来以难用而闻名。所以这里我们用一句rcu_assign_ pointer()原语将内存屏障封装起来,让其拥有发布的语义。最后4行代码如下。

1  p->a =  1;

2  p->b =  2;

3  p->c =  3;

4  rcu_assign_pointer(gp,  p);

rcu_assign_pointer()发布”一个新结构,强制让编译器和CPU在为p的各字段赋值再去为gp赋值。

不过,只保证更新者的执行顺序并不够,因为读者也需要保证读取顺序。请看下面这个例子中的代码。

1  p =  gp;

2  if (p  !=  NULL) {

3     do_something_with(p->a,  p->b, p->c);

4  }


块代码看起来好像不会受到乱序执行的影响,可惜事与愿违,在DEC Alpha CPU机器上,还有启用编译器值猜测(value-speculation)优化时,会让p->ap->bp->c的值在p赋值之前被读取。

也许在启动编译器的值猜测优化时比较容易观察到这一情形,此时编译器会先猜测p->ap->bp->c的值,然后再去读取p的实际值来检查编译器的猜测是否正确。这种类型的优化十分激进,甚至有点疯狂,但是这确实发生在剖析驱动(profile-driven)优化的上下文中。

然而读者可能会说,我们一般不会使用编译器猜测优化。那么我们可以考虑DEC Alpha CPU这样的极端弱序的CPU。在这个CPU上面,引起问题的根源在于:在同一个CPU内部,使用了不止一个缓存来缓存CPU数据。这样可能使用pp->a被分布不同一个CPU的不同缓存中,造成缓存一致性方面的问题。

显然,我们必须在编译器和CPU层面阻止这种危险的优化。rcu_dereference()原语用了各种内存屏障指令和编译器指令来达到这一目的。

1  rcu_read_lock();

2  p =  rcu_dereference(gp);

3  if (p  !=  NULL) {

4     do_something_with(p->a,  p->b, p->c);

5  }

6  rcu_read_unlock();

其中rcu_read_ lock()rcu_read_unlock()这对原语定义了RCU读端的临界区。事实上,在没有配置CONFIG_PREEMPT的内核里,这对原语就是空函数。在可抢占内核中,这这对原语就是关闭/打开抢占。

rcu_dereference()原语用一种“订阅”的办法获取指定指针的值。保证后续的解引用操作可以看见在对应的“发布”操作(rcu_assign_pointer())前进行的初始化,即:在看到p的新值之前,能够看到p->ap->bp->c的新值。请注意,rcu_assign_pointer()rcu_dereference()这对原语既不会自旋或者阻塞,也不会阻止list_add_ rcu()的并发执行。

虽然理论上rcu_assign_pointer()rcu_derederence()可以用于构造任何能想象到的受RCU保护的数据结构,但是实践中常常只用于构建更上层的原语。例如,将rcu_assign_pointer()rcu_dereference()原语嵌入在Linux链表的RCU变体中。Linux有两种双链表的变体,循环链表struct list_head和哈希表structhlist_head/struct hlist_node。前一种如下图所示。

对链表采用指针发布的例子如下:

1  struct  foo  {

2    struct  list_head  *list;

3     int  a;

4     int  b;

5     int  c;

6  };

7 LIST_HEAD(head);

8

9  /*  . .  .  */

10

11  p  = kmalloc(sizeof(*p),  GFP_KERNEL);

12 p->a  =  1;

13 p->b  =  2;

14 p->c  =  3;

15 list_add_rcu(&p->list, &head);

RCU发布链表

15行必须用某些同步机制(最常见的是各种锁)来保护,防止多核list_add()实例并发执行。不过,同步并不能阻止list_add()的实例与RCU的读者并发执行。

订阅一个受RCU保护的链表的代码非常直接。

1  rcu_read_lock();

2  list_for_each_entry_rcu(p,  head, list)  {

3     do_something_with(p->a,  p->b, p->c);

4  }

5  rcu_read_unlock();


list_add_rcu()原语向指定的链表发布了一项条目,保证对应的list_for_each_ entry_rcu()可以订阅到同一项条目。

Linux的其他链表、哈希表都是线性链表,这意味着它的头结点只需要一个指针,而不是象循环链表那样需要两个。因此哈希表的使用可以减少哈希表的hash bucket数组一半的内存消耗。

向受RCU保护的哈希表发布新元素和向循环链表的操作十分类似,如下所示。

1  struct  foo  {

2    struct  hlist_node  *list;

3     int  a;

4     int  b;

5     int  c;

6  };

7 HLIST_HEAD(head);

8

9  /*  . .  .  */

10

11  p  = kmalloc(sizeof(*p),  GFP_KERNEL);

12 p->a  =  1;

13 p->b  =  2;

14 p->c  =  3;

15 hlist_add_head_rcu(&p->list, &head);


和之前一样,第15行必须用某种同步机制,比如锁来保护。

订阅受RCU保护的哈希表和订阅循环链表没什么区别。


1 rcu_read_lock();

2 hlist_for_each_entry_rcu(p, q,  head,  list) {

3    do_something_with(p->a, p->b,  p->c);

4  }

5  rcu_read_unlock();

9.2RCU的发布和订阅原语,另外还有一个删除发布原语。

请注意,list_replace_rcu()list_del_rcu()hlist_replace_rcu()hlist_ del_rcu()这些API引入了一点复杂性。何时才能安全地释放刚被替换或者删除的数据元素?我们怎么能知道何时所有读者释放了他们对数据元素的引用?

2、等待已有的RCU读者执行完毕

从最基本的角度来说,RCU就是一种等待事物结束的方式。当然,有很多其他的方式可以用来等待事物结束,比如引用计数、读/写锁、事件等等。RCU的最伟大之处在于它可以等待(比如)20,000种不同的事物,而无需显式地去跟踪它们中的每一个,也无需去担心对性能的影响,对扩展性的限制,复杂的死锁场景,还有内存泄漏带来的危害等等使用显式跟踪手段会出现的问题。

RCU的例子中,被等待的事物称为“RCU读端临界区”。RCU读端临界区从rcu_read_lock()原语开始,到对应的rcu_read_unlock()原语结束。RCU读端临界区可以嵌套,也可以包含一大块代码,只要这其中的代码不会阻塞或者睡眠(先不考虑可睡眠RCU)。如果你遵守这些约定,就可以使用RCU去等待任何代码的完成。

RCU通过间接地确定这些事物何时完成,才完成了这样的壮举。

如上图所示,RCU是一种等待已有的RCU读端临界区执行完毕的方法,这里的执行完毕也包括在临界区里执行的内存操作。不过请注意,在某个宽限期开始后才启动的RCU读端临界区会扩展到该宽限期的结尾处。

下列伪代码展示了写者使用RCU等待读者的基本方法。

1.作出改变,比如替换链表中的一个元素。

2.等待所有已有的RCU读端临界区执行完毕(比如使用synchronize_rcu()原语)。这里要注意的是后续的RCU读端临界区无法获取刚刚删除元素的引用。

3.清理,比如释放刚才被替换的元素。

下图所示的代码片段演示了这个过程,其中字段a是搜索关键字。

1  struct  foo  {

2    struct  list_head  *list;

3     int  a;

4     int  b;

5     int  c;

6  };

7 LIST_HEAD(head);

8

9  /*  . .  .  */

10

11  p  = search(head,  key);

12  if  (p ==  NULL)  {

13     /*  Take appropriate  action,  unlock, and

  return. */

14  }

15  q  = kmalloc(sizeof(*p),  GFP_KERNEL);

16  *q  =  *p;

17 q->b  =  2;

18 q->c  =  3;

19 list_replace_rcu(&p->list, &q->list);

20 synchronize_rcu();

21  kfree(p);


标准RCU替换示例

192021行实现了刚才提到的三个步骤。第1619行正如RCU其名(读-复制-更新),在允许并发的同时,第16复制,第1719更新

synchronize_rcu()原语可以相当简单。然而,想要达到产品质量,代码实现必须处理一些困难的边界情况,并且还要进行大量优化,这两者都将导致明显的复杂性。理解RCU的难点,主要在于synchronize_rcu()的实现

3、维护最近被更新对象的多个版本

下面展示RCU如何维护链表的多个版本,供并发的读者访问。通过两个例子来说明在读者还处于RCU读端临界区时,被读者引用的数据元素如何保持完整性。第一个例子展示了链表元素的删除,第二个例子展示了链表元素的替换。

例子1:在删除过程中维护多个版本

1  p =  search(head,  key);

2  if (p  !=  NULL) {

3     list_del_rcu(&p->list);

4     synchronize_rcu();

5     kfree(p);

6  }


如下图,每个元素中的三个数字分别代表字段abc的值。红色的元素表示RCU读者此时正持有该元素的引用。请注意,我们为了让图更清楚,忽略了后向指针和从尾指向头的指针。

等第3行的list_del_rcu()执行完毕后,“567”元素从链表中被删除。因为读者不直接与更新者同步,所以读者可能还在并发地扫描链表。这些并发的读者有可能看见,也有可能看不见刚刚被删除的元素,这取决于扫描的时机。不过,刚好在取出指向被删除元素指针后被延迟的读者(比如,由于中断、ECC内存错误),就有可能在删除后还看见链表元素的旧值。因此,我们此时有两个版本的链表,一个有元素“567”,另一个没有。元素“567”用黄色标注,表明老读者可能还在引用它,但是新读者已经无法获得它的引用。

请注意,读者不允许在退出RCU读端临界区后还维护元素“567”的引用。因此,一旦第4行的synchronize_rcu()执行完毕,所有已有的读者都要保证已经执行完,不能再有读者引用该元素。这样我们又回到了唯一版本的链表。

此时,元素“567”可以安全被释放了。这样我们就完成了元素“567”的删除。

例子2:在替换过程中维护多个版本

1  q =  kmalloc(sizeof(*p),  GFP_KERNEL);

2  *q  =  *p;

3  q->b  =  2;

4  q->c  =  3;

5 list_replace_rcu(&p->list, &q->list);

6 synchronize_rcu();

7  kfree(p);

链表的初始状态包括指针p都和“删除”例子中一样。

RCU从链表中替换元素


和前面一样,每个元素中的三个数字分别代表字段abc。红色的元素表示读者可能正在引用,并且因为读者不直接与更新者同步,所以读者有可能与整个替换过程并发执行。请注意我们为了图表的清晰,再一次忽略了后向指针和从尾指向头的指针。

下面描述了元素“523”如何替换元素“567”的过程,任何特定读者可能看见这两个值其中一个。

1行用kmalloc()分配了要替换的元素。此时,没有读者持有刚分配的元素的引用(用绿色表示),并且该元素是未初始化的(用问号表示)。

2行将旧元素复制给新元素。新元素此时还不能被读者访问,但是已经初始化了。

3行将q->b的值更新为2,第4行将q->c的值更新为3

现在,第5行开始替换,这样新元素终于对读者可见了,因此颜色也变成了红色。此时,链表就有两个版本了。已经存在的老读者可能看到元素“567”(现在颜色是黄色的),而新读者将会看见元素“523”。不过这里可以保证任何读者都能看到一个完好的链表。

随着第6synchronize_rcu()的返回,宽限期结束,所有在list_replace_rcu()之前开始的读者都已经完成。特别是任何可能持有元素“567”引用的读者保证已经退出了它们的RCU读端临界区,不能继续持有引用。因此,不再有任何读者持有旧数据的引用,,如第6排绿色部分所示。这样我们又回到了单一版本的链表,只是用新元素替换了旧元素。

等第7行的kfree()完成后,链表就成了最后一排的样子。

不过尽管RCU是因替换的例子而得名的,但是RCU在内核中的主要用途还是用于简单的删除。


本文未完待续

与其相忘江湖,不如点击“二维码”关注Linuxer

苹果用户打赏

安卓用户打赏

Linux RCU
2017-07-07 09:25:08 tszy208 阅读数 131
RCU的设计思想比较明确,通过新老指针替换的方式来实现免锁方式的共享保护。但是具体到代码的层面,理解起来多少还是会有些困难。在《深入Linux设备驱动程序内核机制》第4章中,已经非常明确地叙述了RCU背后所遵循的规则,这些规则是从一个比较高的视角来看,因为我觉得过多的代码分析反而容易让读者在细节上迷失方向。最近拿到书后,我又重头仔细看了RCU部分的文字,觉得还应该补充一点点内容,因为有些东西不一定适合写在书里。

RCU读取侧进入临界区的标志是调用rcu_read_lock,这个函数的代码是:
 


  1. <include/linux/rcupdate.h>
  2. static inline void rcu_read_lock(void)
  3. {
  4.         __rcu_read_lock();
  5.         __acquire(RCU);
  6.         rcu_read_acquire();
  7. }
该实现里面貌似有三个函数调用,但实质性的工作由第一个函数__rcu_read_lock()来完成,__rcu_read_lock()通过调用 preempt_disable()关闭内核可抢占性。但是中断是允许的,假设读取者正处于rcu临界区中且刚读取了一个共享数据区的指针p(但是还没有访问p中的数据成员),发生了一个中断,而该中断处理例程ISR恰好需要修改p所指向的数据区,按照RCU的设计原则,ISR会新分配一个同样大小的数据区new_p,再把老数据区p中的数据拷贝到新数据区,接着是在new_p的基础上做数据修改的工作(因为是在new_p空间中修改,所以不存在对p的并发访问,因此说RCU是一种免锁机制,原因就在这里),ISR在把数据更新的工作完成后,将new_p赋值给p(p=new_p),最后它会再注册一个回调函数用以在适当的时候释放老指针p。因此,只要对老指针p上的所有引用都结束了,释放p就不会有问题。当中断处理例程做完这些工作返回后,被中断的进程将依然访问到p空间上的数据,也就是老数据,这样的结果是RCU机制所允许的。RCU规则对读取者与写入者之间因指针切换所造成的短暂的资源视图不一致问题是允许的

接下来关于RCU一个有趣的问题是:何时才能释放老指针。我见过很多书中对此的回答是:当系统中所有处理器上都发生了一次进程切换。这种程式化的回答常常让刚接触RCU机制的读者感到一头雾水,为什么非要等所有处理器上都发生一次进程切换才可以调用回调函数释放老指针呢?这其实是RCU的设计规则决定的:
 所有对老指针的引用只可能发生在rcu_read_lock与rcu_read_unlock所包括的临界区中,而在这个临界区中不可能发生进程切换而一旦出了该临界区就不应该再有任何形式的对老指针p的引用。很明显,这个规则要求读取者在临界区中不能发生进程切换,因为一旦有进程切换,释放老指针的回调函数就有可能被调用,从而导致老指针被释放掉,当被切换掉的进程被重新调度运行时它就有可能引用到一个被释放掉的内存空间。

现在我们看到为什么rcu_read_lock只需要关闭内核可抢占性就可以了,因为它使得即便在临界区中发生了中断,当前进程也不可能被切换除去。
 内核开发者,确切地说,RCU的设计者所能做的只能到这个程度。接下来就是使用者的责任了,如果在rcu的临界区中调用了一个函数,该函数可能睡眠,那么RCU的设计规则就遭到了破坏,系统将进入一种不稳定的状态。

这再次说明,如果想使用一个东西,一定要搞清楚其内在的机制,象上面刚提到的那个例子,即便现在程序不出现问题,但是系统中留下的隐患如同一个定时炸弹, 随时可能被引爆,尤其是过了很长时间问题才突然爆发出来。绝大多数情形下,找到问题所花费的时间可能要远远大于静下心来仔细搞懂RCU的原理要多得多。
 

RCU中的读取者相对rwlock的读取者而言,自由度更高。因为RCU的读取者在访问一个共享资源时,不需要考虑写入者的感受,这不同于rwlock的写入者,rwlock reader在读取共享资源时需要确保没有写入者在操作该资源。两者之间的差异化源自RCU对共享资源在读取者与写入者之间进行了分离,而rwlock的 读取者和写入者则至始至终只使用共享资源的一份拷贝。这也意味着RCU中的写入者要承担更多的责任,而且对同一共享资源进行更新的多个写入者之间必须引入某种互斥机制,所以RCU属于一种"免锁机制"的说法仅限于读取者与写入者之间。所以我们看到:RCU机制应该用在有大量的读取操作,而更新操作相对较少的情形下。此时RCU可以大大提升系统系能,因为RCU的读取操作相对其他一些有锁机制而言,在锁上的开销几乎没有。

实际使用中,共享的资源常常以链表的形式存在
,内核为RCU模式下的链表操作实现了几个接口函数,读取者和使用者应该使用这些内核函数,比如 list_add_tail_rcu, list_add_rcu,hlist_replace_rcu等等,具体的使用可以参考某些内核编程或者设备驱动程序方面的资料。 

在释放老指针方面,Linux内核提供两种方法供使用者使用,一个是调用call_rcu,另一个是调用synchronize_rcu。前者是一种异步 方式,call_rcu会将释放老指针的回调函数放入一个结点中,然后将该结点加入到当前正在运行call_rcu的处理器的本地链表中,在时钟中断的 softirq部分(RCU_SOFTIRQ), rcu软中断处理函数rcu_process_callbacks会检查当前处理器是否经历了一个休眠期(quiescent,此处涉及内核进程调度等方面的内容),rcu的内核代码实现在确定系统中所有的处理器都经历过了一个休眠期之后(意味着所有处理器上都发生了一次进程切换,因此老指针此时可以被安全释放掉了),将调用call_rcu提供的回调函数。
synchronize_rcu的实现则利用了等待队列,在它的实现过程中也会向call_rcu那样向当前处理器的本地链表中加入一个结点,与 call_rcu不同之处在于该结点中的回调函数是wakeme_after_rcu,然后synchronize_rcu将在一个等待队列中睡眠,直到系统中所有处理器都发生了一次进程切换,因而wakeme_after_rcu被rcu_process_callbacks所调用以唤醒睡眠的 synchronize_rcu,被唤醒之后,synchronize_rcu知道它现在可以释放老指针了。

所以我们看到,call_rcu返回后其注册的回调函数可能还没被调用,因而也就意味着老指针还未被释放,而synchronize_rcu返回后老指针肯定被释放了。所以,是调用call_rcu还是synchronize_rcu,要视特定需求与当前上下文而定,比如中断处理的上下文肯定不能使用 synchronize_rcu函数了。
 
2020-02-23 23:02:37 m0_37329910 阅读数 25

深入理解 Linux 的 RCU 机制

转载 https://www.cnblogs.com/qcloud1001/p/7755331.html
欢迎大家前往腾讯云社区,获取更多腾讯海量技术实践干货哦~

作者:梁康

RCU(Read-Copy Update),是 Linux 中比较重要的一种同步机制。顾名思义就是“读,拷贝更新”,再直白点是“随意读,但更新数据的时候,需要先复制一份副本,在副本上完成修改,再一次性地替换旧数据”。这是 Linux 内核实现的一种针对“读多写少”的共享数据的同步机制。

不同于其他的同步机制,它允许多个读者同时访问共享数据,而且读者的性能不会受影响(“随意读”),读者与写者之间也不需要同步机制(但需要“复制后再写”),但如果存在多个写者时,在写者把更新后的“副本”覆盖到原数据时,写者与写者之间需要利用其他同步机制保证同步。

RCU 的一个典型的应用场景是链表,在 Linux kernel 中还专门提供了一个头文件(include/linux/rculist.h),提供了利用 RCU 机制对链表进行增删查改操作的接口。本文将通过一个例子,利用 rculist.h 提供的接口对链表进行增删查改的操作,来讲述 RCU 的原理,以及介绍 Linux kernel 中相关的 API(基于 Linux v3.4.0 的源码)。

增加链表项

Linux kernel 中利用 RCU 往链表增加项的源码如下:

#define list_next_rcu(list)     (*((struct list_head __rcu **)(&(list)->next)))

static inline void __list_add_rcu(struct list_head *new,
                struct list_head *prev, struct list_head *next)
{
        new->next = next;
        new->prev = prev;
        rcu_assign_pointer(list_next_rcu(prev), new);
        next->prev = new;
}

list_next_rcu() 函数中的 rcu 是一个供代码分析工具 Sparse 使用的编译选项,规定有 rcu 标签的指针不能直接使用,而需要使用 rcu_dereference() 返回一个受 RCU 保护的指针才能使用。rcu_dereference() 接口的相关知识会在后文介绍,这一节重点关注 rcu_assign_pointer() 接口。首先看一下 rcu_assign_pointer() 的源码:

#define __rcu_assign_pointer(p, v, space) \
    ({ \
        smp_wmb(); \
        (p) = (typeof(*v) __force space *)(v); \
    })

上述代码的最终效果是把 v 的值赋值给 p,关键点在于第 3 行的内存屏障。什么是内存屏障(Memory Barrier)呢?CPU 采用流水线技术执行指令时,只保证有内存依赖关系的指令的执行顺序,例如 p = v; a = *p;,由于第 2 条指令访问的指针 p 所指向的内存依赖于第 1 条指令,因此 CPU 会保证第 1 条指令在第 2 条指令执行前执行完毕。但对于没有内存依赖的指令,例如上述 __list_add_rcu() 接口中,假如把第 8 行写成 prev->next = new;,由于这个赋值操作并没涉及到对 new 指针指向的内存的访问,因此认为不依赖于 6,7 行对 new->next 和 new->prev 的赋值,CPU 有可能实际运行时会先执行 prev->next = new; 再执行 new->prev = prev;,这就会造成 new 指针(也就是新加入的链表项)还没完成初始化就被加入了链表中,假如这时刚好有一个读者刚好遍历访问到了该新的链表项(因为 RCU 的一个重要特点就是可随意执行读操作),就会访问到一个未完成初始化的链表项!通过设置内存屏障就能解决该问题,它保证了在内存屏障前边的指令一定会先于内存屏障后边的指令被执行。这就保证了被加入到链表中的项,一定是已经完成了初始化的。

最后提醒一下,这里要注意的是,如果可能存在多个线程同时执行添加链表项的操作,添加链表项的操作需要用其他同步机制(如 spin_lock 等)进行保护。

访问链表项

Linux kernel 中访问 RCU 链表项常见的代码模式是:

rcu_read_lock();
list_for_each_entry_rcu(pos, head, member) {
    // do something with `pos`
}
rcu_read_unlock();

这里要讲到的 rcu_read_lock() 和 rcu_read_unlock(),是 RCU “随意读” 的关键,它们的效果是声明了一个读端的临界区(read-side critical sections)。在说读端临界区之前,我们先看看读取链表项的宏函数 list_for_each_entry_rcu。追溯源码,获取一个链表项指针主要调用的是一个名为 rcu_dereference() 的宏函数,而这个宏函数的主要实现如下:

#define __rcu_dereference_check(p, c, space) \
    ({ \
        typeof(*p) *_________p1 = (typeof(*p)*__force )ACCESS_ONCE(p); \
        rcu_lockdep_assert(c, "suspicious rcu_dereference_check()" \
                      " usage"); \
        rcu_dereference_sparse(p, space); \
        smp_read_barrier_depends(); \
        ((typeof(*p) __force __kernel *)(_________p1)); \
    })

第 3 行:声明指针 _p1 = p;
第 7 行:smp_read_barrier_depends();
第 8 行:返回 _p1;

上述两块代码,实际上可以看作这样一种模式:

rcu_read_lock();
p1 = rcu_dereference(p);
if (p1 != NULL) {
    // do something with p1, such as:
    printk("%d\n", p1->field);
}
rcu_read_unlock();

根据 rcu_dereference() 的实现,最终效果就是把一个指针赋值给另一个,那如果把上述第 2 行的 rcu_dereference() 直接写成 p1 = p 会怎样呢?在一般的处理器架构上是一点问题都没有的。但在 alpha 上,编译器的 value-speculation 优化选项据说可能会“猜测” p1 的值,然后重排指令先取值 p1->field~ 因此 Linux kernel 中,smp_read_barrier_depends() 的实现是架构相关的,arm、x86 等架构上是空实现,alpha 上则加了内存屏障,以保证先获得 p 真正的地址再做解引用。因此上一节 “增加链表项” 中提到的 “__rcu” 编译选项强制检查是否使用 rcu_dereference() 访问受 RCU 保护的数据,实际上是为了让代码拥有更好的可移植性。

现在回到读端临界区的问题上来。多个读端临界区不互斥,即多个读者可同时处于读端临界区中,但一块内存数据一旦能够在读端临界区内被获取到指针引用,这块内存块数据的释放必须等到读端临界区结束,等待读端临界区结束的 Linux kernel API 是synchronize_rcu()。读端临界区的检查是全局的,系统中有任何的代码处于读端临界区,synchronize_rcu() 都会阻塞,知道所有读端临界区结束才会返回。为了直观理解这个问题,举以下的代码实例:

/* `p` 指向一块受 RCU 保护的共享数据 */

/* reader */
rcu_read_lock();
p1 = rcu_dereference(p);
if (p1 != NULL) {
    printk("%d\n", p1->field);
}
rcu_read_unlock();

/* free the memory */
p2 = p;
if (p2 != NULL) {
    p = NULL;
    synchronize_rcu();
    kfree(p2);
}

用以下图示来表示多个读者与内存释放线程的时序关系:

在这里插入图片描述

上图中,每个读者的方块表示获得 p 的引用(第5行代码)到读端临界区结束的时间周期;t1 表示 p = NULL 的时间;t2 表示 synchronize_rcu() 调用开始的时间;t3 表示 synchronize_rcu() 返回的时间。我们先看 Reader1,2,3,虽然这 3 个读者的结束时间不一样,但都在 t1 前获得了 p 地址的引用。t2 时调用 synchronize_rcu(),这时 Reader1 的读端临界区已结束,但 Reader2,3 还处于读端临界区,因此必须等到 Reader2,3 的读端临界区都结束,也就是 t3,t3 之后,就可以执行 kfree(p2) 释放内存。synchronize_rcu() 阻塞的这一段时间,有个名字,叫做 Grace period。而 Reader4,5,6,无论与 Grace period 的时间关系如何,由于获取引用的时间在 t1 之后,都无法获得 p 指针的引用,因此不会进入 p1 != NULL 的分支。

删除链表项

知道了前边说的 Grace period,理解链表项的删除就很容易了。常见的代码模式是:

p = seach_the_entry_to_delete();
list_del_rcu(p->list);
synchronize_rcu();
kfree(p);

其中 list_del_rcu() 的源码如下,把某一项移出链表:

/* list.h */
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
    next->prev = prev;
    prev->next = next;
}

/* rculist.h */
static inline void list_del_rcu(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    entry->prev = LIST_POISON2;
}

根据上一节“访问链表项”的实例,假如一个读者能够从链表中获得我们正打算删除的链表项,则肯定在 synchronize_rcu() 之前进入了读端临界区,synchronize_rcu() 就会保证读端临界区结束时才会真正释放链表项的内存,而不会释放读者正在访问的链表项。

更新链表项

前文提到,RCU 的更新机制是 “Copy Update”,RCU 链表项的更新也是这种机制,典型代码模式是:

p = search_the_entry_to_update();
q = kmalloc(sizeof(*p), GFP_KERNEL);
*q = *p;
q->field = new_value;
list_replace_rcu(&p->list, &q->list);
synchronize_rcu();
kfree(p);

其中第 3,4 行就是复制一份副本,并在副本上完成更新,然后调用 list_replace_rcu() 用新节点替换掉旧节点。源码如下:
其中第 3,4 行就是复制一份副本,并在副本上完成更新,然后调用 list_replace_rcu() 用新节点替换掉旧节点,最后释放旧节点内存。list_replace_rcu() 源码如下:

static inline void list_replace_rcu(struct list_head *old,
                struct list_head *new)
{
    new->next = old->next;
    new->prev = old->prev;
    rcu_assign_pointer(list_next_rcu(new->prev), new);
    new->next->prev = new;
    old->prev = LIST_POISON2;
}
2019-06-06 11:35:59 qq_22613757 阅读数 118

内核源码中有很多rcu的标志,到底什么是RCU,一直都不清楚。

  • RCU(Read-Copy Update),是 Linux 中比较重要的一种同步机制。顾名思义就是 “读 , 拷贝更新”,再直白点是“随意读,但更新数据的时候,需要先复制一份副本,在副本上完成修改,再一次性地替换旧数据”。这是linux内核实现的一种针对“读多写少”的共享数据的同步机制。

  • 不同于其他的同步机制,它允许多个读者同时访问共享数据,而且读者的性能不会受影响(随意读),读者与写者之间也不需要同步机制(但需要“复制后再写”),但如果存在多个写者时,在写者把更新后的“副本”覆盖到原数据时,写者与写者之间需要利用其他同步机制保证同步。

  • RCU的一个典型的应用场景是链表,在linux kernel 中还专门提供了一个头文件(linux/linux/rculist.h), 提供里利用RCU机制对链表进行增删改查改操作的接口。本文将通过一个例子,利用rculist.h提供的接口对链表进行增删改查的操作,来讲述RCU的原理,以及介绍Linux kernel中相关的API(基于 Linux v4.4.4 源码)

增加链表项

Linux kernel 中利用RCU往链表增加项的源码如下:

#define list_next_rcu(list)     (*((struct list_head __rcu **)(&(list)->next)))

static inline void __list_add_rcu(struct list_head *new,
                struct list_head *prev, struct list_head *next)
{
        new->next = next;
        new->prev = prev;
        rcu_assign_pointer(list_next_rcu(prev), new);
        next->prev = new;
}

list_next_rcu()函数中的rcu是一个供代码分析工具Sparse使用的编译选项,规定有rcu标签的指针不能直接使用,而需要使用rcu_dereference()返回一个受RCU保护的指针才能使用。rcu_dereference()接口的相关知识会在后文介绍,这一节重点关注rcu_assign_pointer()接口。先看一个rcu_assign_pointer()的源码:

#define smp_store_release(p, v)						\
do {									\
	compiletime_assert_atomic_type(*p);				\
	barrier();							\
	WRITE_ONCE(*p, v);						\
} while (0)

上述代码的最终效果是把v的值赋值给p,关键点在于第4行的内存屏障(Memory Barrier)。什么是内存屏障? CPU采用流水线技术执行指令时,只保证有内存依赖关系的指令的执行顺序,例如p = v ; a = *p ; 由于第2条指令访问的指针p所指向的内存依赖于第1条指令,因此CPU会保证第一条指令在第二条指令执行前执行完毕。但对于没有内存依赖的指令,例如上述__list_add_rcu()接口中,如果把第8行写成pre->next = new; 由于这个赋值操作并没有涉及到对new 指针指向的内存的访问,因此认为不依赖于6,7行对new->next和new->prev的赋值,CPU有可能实际运行时会先执行pre->next = new;再执行new->prev = prev; 这就会造成new指针(也就是新加入的链表项)还没完成初始化就被加入了链表中,假如这时刚好有一个读者刚好遍历访问到了该新的链表项(RCU的重要特性就是可随意执行读操作),就会访问到一个未完成初始化的链表项!通过设置内存屏障就能解决该问题,它保证了在内存屏障前边的指令一定会先于内存屏障后边的指令被执行,这就保证了被加入到链表中的项,一定是已经完成了初始化。

如果可能存在多个线程同时执行添加链表项的操作,添加链表项的操作需要其他同步机制(如 spin_lock 等)进行保护。

访问链表项

Linux kernel中访问RCU链表项常见的代码模式是:

rcu_read_lock();
list_for_each_entry_rcu(pos, head, member) {
    // do something with `pos`
}
rcu_read_unlock();

这里要讲到的 rcu_read_lock() 和 rcu_read_unlock(),是 RCU “随意读” 的关键,它们的效果是声明了一个读端的临界区(read-side critical sections)。在说读端临界区之前,我们先看看读取链表项的宏函数 list_for_each_entry_rcu。追溯源码,获取一个链表项指针主要调用的是一个名为 lockless_dereference() 的宏函数,而这个宏函数的主要实现如下:

/**
 * lockless_dereference() - safely load a pointer for later dereference
 * @p: The pointer to load
 *
 * Similar to rcu_dereference(), but for situations where the pointed-to
 * object's lifetime is managed by something other than RCU.  That
 * "something other" might be reference counting or simple immortality.
 */
#define lockless_dereference(p) \
({ \
	typeof(p) _________p1 = READ_ONCE(p); \
	smp_read_barrier_depends(); /* Dependency order vs. p above. */ \
	(_________p1); \
})

上述两块代码,实际上可以看作这样一种模式:

rcu_read_lock();
p1 = rcu_dereference(p);
if (p1 != NULL) {
    // do something with p1, such as:
    printk("%d\n", p1->field);
}
rcu_read_unlock();

根据 rcu_dereference() 的实现,最终效果就是把一个指针赋值给另一个,那如果把上述第 2 行的 rcu_dereference() 直接写成 p1 = p 会怎样呢?在一般的处理器架构上是一点问题都没有的。但在 alpha 上,编译器的 value-speculation 优化选项据说可能会“猜测” p1 的值,然后重排指令先取值 p1->field~ 因此 Linux kernel 中,smp_read_barrier_depends() 的实现是架构相关的,arm、x86 等架构上是空实现,alpha 上则加了内存屏障,以保证先获得 p 真正的地址再做解引用。因此上一节 “增加链表项” 中提到的 “__rcu” 编译选项强制检查是否使用 rcu_dereference() 访问受 RCU 保护的数据,实际上是为了让代码拥有更好的可移植性。

  • 现在回到读端临界区的问题上来。多个读端临界区不互斥,即多个读者可同时处于读端临界区中,但一块内存数据一旦能够在读端临界区内被获取到指针引用,这块内存块数据的释放必须等到读端临界区结束,等待读端临界区结束的 Linux kernel API 是synchronize_rcu()。读端临界区的检查是全局的,系统中有任何的代码处于读端临界区,synchronize_rcu() 都会阻塞,知道所有读端临界区结束才会返回。为了直观理解这个问题,举以下的代码实例:
/* `p` 指向一块受 RCU 保护的共享数据 */

/* reader */
rcu_read_lock();
p1 = rcu_dereference(p);
if (p1 != NULL) {
    printk("%d\n", p1->field);
}
rcu_read_unlock();

/* free the memory */
p2 = p;
if (p2 != NULL) {
    p = NULL;
    synchronize_rcu();
    kfree(p2);
}

用以下图示来表示多个读者与内存释放线程的时序关系:

在这里插入图片描述


上图中,每个读者的方块表示获得 p 的引用(第5行代码)到读端临界区结束的时间周期;t1 表示 p = NULL 的时间;t2 表示 synchronize_rcu() 调用开始的时间;t3 表示 synchronize_rcu() 返回的时间。我们先看 Reader1,2,3,虽然这 3 个读者的结束时间不一样,但都在 t1 前获得了 p 地址的引用。t2 时调用 synchronize_rcu(),这时 Reader1 的读端临界区已结束,但 Reader2,3 还处于读端临界区,因此必须等到 Reader2,3 的读端临界区都结束,也就是 t3,t3 之后,就可以执行 kfree(p2) 释放内存。synchronize_rcu() 阻塞的这一段时间,有个名字,叫做 Grace period。而 Reader4,5,6,无论与 Grace period 的时间关系如何,由于获取引用的时间在 t1 之后,都无法获得 p 指针的引用,因此不会进入 p1 != NULL 的分支。

删除链表项

知道了前面的Grace period,理解链表项的删除就很容易了。常见的代码模式是:

p = seach_the_entry_to_delete();
list_del_rcu(p->list);
synchronize_rcu();
kfree(p);
其中 list_del_rcu() 的源码如下,把某一项移出链表:

/* list.h */
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
    next->prev = prev;
    prev->next = next;
}

/* rculist.h */
static inline void list_del_rcu(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    entry->prev = LIST_POISON2;
}

根据上一节“访问链表项”的实例,假如一个读者能够从链表中获得我们正打算删除的链表项,则肯定在 synchronize_rcu() 之前进入了读端临界区,synchronize_rcu() 就会保证读端临界区结束时才会真正释放链表项的内存,而不会释放读者正在访问的链表项。

更新链表项

前文提到,RCU 的更新机制是 “Copy Update”,RCU 链表项的更新也是这种机制,典型代码模式是:

p = search_the_entry_to_update();
q = kmalloc(sizeof(*p), GFP_KERNEL);
*q = *p;
q->field = new_value;
list_replace_rcu(&p->list, &q->list);
synchronize_rcu();
kfree(p);

其中第 3,4 行就是复制一份副本,并在副本上完成更新,然后调用 list_replace_rcu() 用新节点替换掉旧节点,最后释放旧节点内存。list_replace_rcu() 源码如下:

static inline void list_replace_rcu(struct list_head *old,
                struct list_head *new)
{
    new->next = old->next;
    new->prev = old->prev;
    rcu_assign_pointer(list_next_rcu(new->prev), new);
    new->next->prev = new;
    old->prev = LIST_POISON2;
}

参考: Linux内核内存屏障 https://www.cnblogs.com/icanth/archive/2012/06/10/2544300.html

引用: 深入理解Linux内核RCU机制

没有更多推荐了,返回首页