linux rcu 深入理解_linux rcu - CSDN
  • 这不是一篇单独的文章,这是《谢宝友:深入理解Linux RCU》系列的第4篇,前序文章: 谢宝友: 深入理解Linux RCU之一——从硬件说起 谢宝友:深入理解Linux RCU:从硬件说起之内存屏障 谢宝友:深入理解RCU之三...

    本文简介

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

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

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

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


    作者简介

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

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

    640?wx_fmt=jpeg&wxfrom=5&wx_lazy=1

    稿件征集

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

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


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

    640?wx_fmt=png

    0?wx_fmt=png

    一、

    RCU的用法0?wx_fmt=png

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

    • 读写锁

    • 受限制的引用计数机制

    • 批量引用计数机制

    • 穷人版的垃圾回收器

    • 存在担保

    • 类型安全的内存

    • 等待事物结束

    1.1 RCU是读写锁的替代者

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

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

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

    0?wx_fmt=png

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

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

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

    0?wx_fmt=png

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

     

    0?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非常简单,如下:

    0?wx_fmt=gif

    0?wx_fmt=gif

    0?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系统中采集的数据。

    0?wx_fmt=png

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

    0?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中断。

    0?wx_fmt=png二、RCU API0?wx_fmt=png


    2.1 等待完成的API


    0?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

    0?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()之前进行的初始化的结果。 

     

    0?wx_fmt=png

    本文未完待续

    敬请关注Linuer期待来下篇!

    0?wx_fmt=png


    苹果用户打赏

    0?wx_fmt=png

    安卓用户打赏


    展开全文
  • 本文将通过一个例子,利用 rculist.h 提供的接口对链表进行增删查改的操作,来讲述 RCU 的原理,以及介绍 Linux kernel 中相关的 API(基于 Linux v3.4.0 的源码)。

    欢迎大家前往腾讯云社区,获取更多腾讯海量技术实践干货哦~

    作者:梁康

    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;
    }

    References

    [1] What is RCU, Fundamentally?
    [2] https://www.kernel.org/doc/Documentation/RCU/checklist.txt
    [3] https://www.kernel.org/doc/Documentation/RCU/whatisRCU.txt
    [4] https://www.kernel.org/doc/Documentation/memory-barriers.txt
    [5] LINUX内核之内存屏障

    相关阅读

    一站式满足电商节云计算需求的秘诀
    谢宝友:深入理解 Linux RCU 从硬件说起之内存屏障
    【ES私房菜】收集 Linux 系统日志


    此文已由作者授权腾讯云技术社区发布,转载请注明文章出处
    原文链接:https://cloud.tencent.com/community/article/369148

    展开全文
  • Linux RCU锁简析

    2016-01-17 14:30:24
    最近遇到一个问题,大压力测试下咬狗了,定位出来跟RCU相关,还是先简单的捋一捋RCU,也好看看后面能否对RCU做些特定场景下的优化。 网上RCU相关的技术博客比较多,先列几个可供参考的: MagicBoy201写的《再谈...

    最近遇到一个问题,大压力测试下咬狗了,定位出来跟RCU相关,还是先简单的捋一捋RCU,也好看看后面能否对RCU做些特定场景下的优化。

    网上RCU相关的技术博客比较多,先列几个可供参考的:

    MagicBoy201写的《再谈Linux内核中的RCU机制 》http://blog.chinaunix.net/uid-23769728-id-3080134.html

    这篇博客写的比较宏观一些。

    《linux内核 RCU机制详解》 http://blog.csdn.net/xabc3000/article/details/15335131

    原文没找到,这篇博文看看前段就好,了就下什么是RCU和宽限期。

    <深入浅出> linux内核 RCU (一)经典RCU》http://blog.csdn.net/chenyu105/article/details/7910269

    <深入浅出> linux内核 RCU (二)分级RCU》http://blog.csdn.net/chenyu105/article/details/23104221

    这两篇博文 经典RCU写的很不错,把经典RCU的逻辑实现都写出来了。

    RCU (Read-Copy Update)是一种同步机制,是对读写锁的优化。

    先简单了解一下读写锁,rwlock可以多个线程同时占用读模式的读写锁,但是只能一个线程占用写模式的读写锁,即

    (1)当有人拿到写锁的时候,任何人都不能再拿到读锁或写锁

    (2)当有人拿到读锁的时候,其他人也可以拿到读锁,但不能有人拿到写锁去修改临界区

    (3)已经加了读锁时,如有人尝试拿写锁,需要尽快得到满足,避免写锁饥饿

    RCU的行为方式

    (1)随时可以拿到读锁,即对临界区的读操作随时都可以得到满足

    (2)某一时刻只能有一个人拿到写锁,多个写锁需要互斥,写的动作包括 拷贝--修改--宽限窗口到期后删除原值

    (3)临界区的原始值为m1,如会有人拿到写锁修改了临界区为m2,则在写锁修改临界区之后拿到的读锁获取的临界区的值为m2,之前获取的为m1,这通过原子操作保证

    对比发现RCU读操作随时都会得到满足,但写锁之后的写操作所耗费的系统资源就相对比较多了,并且只有在宽限期之后删除原资源。

    RCU宽限期:

     图中每行代表一个线程,最下面的一行是删除线程,当它执行完删除操作后,线程进入了宽限期。宽限期的意义是,在一个删除动作发生后,它必须等待所有在宽限期开始前已经开始的读线程结束,才可以进行销毁操作。这样做的原因是这些线程有可能读到了要删除的元素。图中的宽限期必须等待1和2结束;而读线程5在宽限期开始前已经结束,不需要考虑;而3,4,6也不需要考虑,因为在宽限期开始后的线程不可能读到已删除的元素。

    宽限期的描述来源于《linux内核 RCU机制详解》 http://blog.csdn.net/xabc3000/article/details/15335131

    宽限期的定义引来几个问题(后文称RCU问题)

    (1)宽限期的开始即预示着RCU监测的开始,需要监测宽限期开始之前的线程是否结束

    (2)宽限期是否在调用call_rcu之后马上开始?答案是否定的,同一时刻只有一个宽限期,在某个宽限期内新加入的所有call_rcu回调会合并为一个宽限期,在此宽限期到期后

    一起得到调用,即下图中右边所示


    (3)如何判断一个宽限期到期

    经典(classic)RCU读锁就是关内核抢占,读锁释放时再开内核抢占,因此判断运行在某CPU上线程是否有释放读锁的一个间接方式就是观察这个CPU上是否发生了调度(该CPU一直idle状态需额外处理),这种判断方式简单而暴力,在非抢占内核中实时性肯定不是很好,但总体的开销要比释放读锁后再发一个直接的“通知”要小。因此开启一个宽限窗口后,如果监测到所有的CPU在监测点之后都发生过一次调度则就可以认为宽限期到期了,就可以释放原始数据了,太简单暴力了,可能某些CPU上运行的线程跟这个宽限窗口所服务的RCU一点关系都没有,可RCU就是做的这么暴力,这也是一些应用场景需要解决的问题,通过修改RCU的监测机制是能做到不这么暴力的。

    RCU要实现的逻辑是:

    (1)用户注册RCU回调(call_rcu)

    (2)将新注册的RCU回调放到一个缓冲队列(链表)中,或正式队列中为空时直接放到一个正式队列中

    (3)在时钟中断---软中断中判断如没有一个有效的宽限窗口存在,而用户有发起“开窗”请求(上述链表非空),则开启一个宽限窗口,开始监测系统中所有的CPU是否有调度(通过位图、per cpu变量)

    (4)在时钟中断---软中断中监测到宽限期到后(所有CPU都发生了调度),则执行RCU回调/激活RCU软中断

    (5)为解决RCU问题2,CPU过多时操作位图引起的cache line问题、竞争问题,软中断超长等等问题,RCU具体实现的时候应用了一些比较巧妙的方式,来提高RCU的性能

    (6)以上行为(1);(2)(3)(4)周而复始。


    RCU一直在优化,2.6.25 ,2.6.34,3.10,4.1,不同版本的RCU实现已经有比较大的区别了,早起版本理解起来更直观一些,

    有兴趣的话可以上http://lxr.oss.org.cn/快速浏览一下早起的代码。

    后面计划再结合3.10和4.1内核赏析一下RCU的实现,体味一下RCU作者的匠心。



    展开全文
  • 谢宝友: 深入理解Linux RCU之一——从硬件说起 谢宝友:深入理解Linux RCU:从硬件说起之内存屏障 作者简介  谢宝友,在编程一线工作已经有20年时间,其中接近10年时间工作于Linux操作系统

    本文简介

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


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

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


    作者简介

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

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

    640?wx_fmt=jpeg&wxfrom=5&wx_lazy=1

    稿件征集

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

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

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

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

    0?wx_fmt=png

    一、RCU有什么用?

    0?wx_fmt=png

    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节点。

    0?wx_fmt=png

    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的基本原理。

    0?wx_fmt=png

    二、RCU是什么?

    0?wx_fmt=png

    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。前一种如下图所示。

    0?wx_fmt=png

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

    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的发布和订阅原语,另外还有一个删除发布原语。

    0?wx_fmt=png

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

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

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

    0?wx_fmt=png

    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读者此时正持有该元素的引用。请注意,我们为了让图更清楚,忽略了后向指针和从尾指向头的指针。

    0?wx_fmt=png

    等第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都和“删除”例子中一样。

    0?wx_fmt=png

    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

    0?wx_fmt=png

    0?wx_fmt=png

    苹果用户打赏

    0?wx_fmt=png

    0?wx_fmt=jpeg

    0?wx_fmt=png

    安卓用户打赏

    0?wx_fmt=png
    展开全文
  • 本文简介本文介绍Linux 2.6.32-rc7中,分级RCU的基础。这不是一篇单独的文章,这是《谢宝友:深入理解Linux RCU》系列的第6篇。关注Linuxer公众...
        

    本文简介

    本文介绍Linux 2.6.32-rc7中,分级RCU的基础。

    这不是一篇单独的文章,这是《谢宝友:深入理解Linux RCU》系列的第6篇。关注Linuxer公众号看前五篇:

    640?wx_fmt=png

    作者简介

    谢宝友,别名浪子燕青,在编程一线工作已经有20年时间,其中10年时间工作于Linux操作系统。

    同时,他也是《深入理解并行编程》一书的译者。该书作者PaulE.McKeney是IBM Linux中心技术领导者,LinuxRCU Maintainer。《深入理解RCU》系列文章整理了PaulE.McKeney的相关著作,希望能帮助读者更深刻的理解Linux内核中非常难于理解的模块:RCU。

    目前,他编写的Hot-Pot操作系统即使发布第一个版本。这个版本基于ARM 64多核系统,包含了调度、中断、定时器、内存管理、LEXT3文件系统、LWIP网络协议栈、一个精简版本的内核态C库、一些基本的Shell命令等等基本的操作系统功能。虽然目前代码还比较丑陋,仅仅算是Linux的一个小学生,但是也可以自豪的声称:Hot-Pot操作系统拥有了一个Good Start。今年,他将编写一本《Hot-Pot操作系统详解--迈向工业级服务器操作系统的实现》来详细阐述这个操作系统,并以GPL协议公布源代码,热切希望所有有兴趣的好汉一起参与。

        联系方式:

        mail:scxby@163.com

        微信:linux-kernel

    640?wx_fmt=jpeg

    1、准备工作

    本文基于linux 2.6.32-rc7版本的源码, 因此请准备一份linux2.6.32-rc7代码。建议用如下两种方法获取源代码:

    1、直接在linux.org上面下载源码包。

    2、使用git从linux-next拉取最新代码,然后使用git checkout -b linux-2.6.32-rc7 v2.6.32-rc7检出2.6.32-rc7版本的源码。

    2、概述

    虽然Linux更早版本中的经典RCU,其读端原语拥有出色的性能和扩展性,但是写端原语则需要判断预先存在的读端临界区在什么时候完成,它仅仅被设计用于数十个CPU的系统。经典RCU的实现,要求在每个优雅周期内,每个CPU必须获取一个全局锁,这使得它们的扩展性受到了限制。虽然在实际生产系统中,经典RCU可以运行在几百个CPU的系统中,甚至能够比较困难的使用到上千个 CPU的系统中,但是大型多核系统仍然需要更好的扩展性。

    另外,经典RCU有一个不是最优的dynticks 接口,导致经典RCU在每一个优雅周期都要唤醒每一个CPU,即使这些CPU处于idle状态。我们考虑一个16核的系统,它只有四个CPU比较忙,其他CPU的负载都很轻。理想情况下,余下12个CPU可以一直处于深度睡眠模式以节约能源。然而不幸的是,如果四个忙的CPU频繁的执行RCU更新,这12个空闲CPU会被周期性的唤醒,浪费了重要的能源。因此,对于经典RCU的任何优化,都应当让这些睡眠状态的CPU继续处于睡眠状态。

    经典RCU和分级RCU实现都有和经典RCU相同的语义和API。但是,原有的实现被称为“经典RCU”,新实现被称为“分级RCU”。

    2.1.  RCU基础回顾

    从最基本的方面来说,RCU 是一种等待事务完成的方法。当然,要等待事务完成,还存在很多其他方法,包括引用计数、读写锁、事件等等。RCU的一个大的优势是可以同时等待20,000个不同的事件,而不必具体的跟踪其中每一个事件,并且不用担心性能被降低,以及扩展性被限制,也不用担心复杂的死锁情况和内存泄漏的危险。

    在RCU中,被等待的事件被称为“RCU 读端临界区”。RCU读端临界区以rcu_read_lock()原语开始,以相应的rcu_read_unlock() 原语结束。RCU读端临界区可以嵌套,也可以包含相当多的代码,只要这些代码不阻塞或者睡眠(当然,这是针对经典RCU来说的。有一种特殊的名为SRCU的可睡眠RCU,它允许在SRCU读端临界区中进行短期睡眠)。如果您遵从这些约束,您可以使用RCU来等待任何代码片段完成。

    RCU通过间接的确定其他事务何时完成来实现这一点。但是,请注意:在特定的优雅周期之后开始的RCU 读端临界区能够、也必然会延长优雅周期的结束点。

    2.2.  经典RCU实现概要

    经典RCU实现的关键原理是:经典RCU 读端临界区限制其中的内核代码不允许阻塞。这意味着在任意时刻,一个特定的CPU只要看起来处于阻塞状态、IDLE循环、或者离开了内核后,我们就知道所有RCU读端临界区已经完成。这些状态被称为“静止状态”,当每一个CPU已经经历过至少一次静止状态时,RCU优雅周期结束。

    640?wx_fmt=png

    经典RCU最重要的数据结构是rcu_ctrlblk,它包含了->cpumask字段,每一个CPU在该字段中包含一位,如上图所示。当每一个优雅周期开始时,每一个 CPU相应的位被设置为1,每一个CPU经过一次静止状态时,必须清除相应的位。由于多个CPU可能希望同时清除它们的位,这将破坏->cpumask 字段,因此使用了一个->lock自旋锁来保护->cpumask。不幸的是,当超过几千个CPU时,这个自旋锁会遇到严重的竞争状态。更糟糕的是,事实上所有CPU必须清除它们的位,意味着在一个优雅周期内,CPU不允许一直睡眠。这削弱了LINUX节能的能力。

    2.3.  RCU 迫切要解决的问题

    实时RCU迫切要解决的问题列表如下:

    1.   延迟销毁。这样,直到所有已经预先存在的RCU读端临界区已经完成,一个RCU优雅周期才能结束。

    2.   可靠性,这样RCU支持24x7运行。

    3.   可以在IRQ处理函数中调用。

    4.   包含内存标记,这样,如果有很多回调过程,这种机制将加快结束优雅周期。

    5.   独立的内存块,这样RCU能够基于可信的内存分配器进行工作。

    6.   synchronization-free的读端,这样允许通常的非原子指令操作于CPU(或者任务)的本地内存。

    7.   无条件的read-to-write提升,在LINUX内核中,有几个地方需要这样使用。

    8.   兼容的API。

    9.   抢占RCU读端临界区的要求可以被去掉。

    10.  极低的RCU内部锁的竞争,从而带来极大的扩展性。RCU必须支持至少1,024个CPU,最好是至少4,096个CPU。

    11.  节能:RCU必须能够避免唤醒低电压状态的dynticks-idle CPU,但是仍然能够判断当前的优雅周期何时结束。这已经在实时RCU中实现,但是需要大大的简化。

    12.  RCU读端临界区必须允许在NMI处理函数中使用,就如在中断处理函数中一样。

    13.  RCU必须很好的管理不停的CPU热插拨操作。

    14.  必须能够等待所有事先注册的RCU回调完成,虽然这已经以rcu_barrier()的形式提供。

    15.  检测失去响应的CPU是值得的,以帮助诊断RCU和死循环BUG及硬件错误,这能够防止RCU优雅周期不能结束的情况。

    16.  加快RCU优雅周期是值得的,这样RCU优雅周期能够强制在数百微秒内完成。但是,这样的操作预期会带来严重的CPU负载。

    最急迫的首要需求是:可扩展性。因此需要减少RCU的内部锁。

    2.4.  迈向可扩展RCU实现

    640?wx_fmt=png

    减少锁竞争的一个有效方法是创建一个分级结构,如上图所示。在此,四个rcu_node 结构中的每一个都有各自的锁,这样只有 CPU 0 和 1 会获取最左边的 rcu_node的锁, CPU 2 和 3 会获取中间的rcu_node的锁,CPU 4和5会获取右边的rcu_node的锁。在任一个优雅周期期间,仅仅某一个CPU节点会访问rcu_node 结构的上一层的rcu_node。也就是说,在上图中,每一对CPU(它们处于同一个CPU节点)中,最后一个记录静止状态的CPU才会访问上一层的rcu_node。

    这样做的最终结果,是减少了锁的竞争。在经典RCU中,6个CPU在每一个优雅周期内竞争同一个全局锁,在上图中,仅仅是三个节点竞争最上层的rcu_node锁 (降低了50%)。

    640?wx_fmt=png

    rcu_node结构树被嵌入到rcu_state 结构的一个线性数组,树根是结点0,如上图。它是一个8-CPU的、三层分级结构的系统。 每一个箭头将一个rcu_node 结构链接到它的父结点,这对应着rcu_node结构的->parent 字段。每一个rcu_node都标示了它所覆盖的CPU范围,这样根结点覆盖了所有CPU,每一个二级结点覆盖了一半的CPU,每一个叶子结点覆盖了两个 CPU。这个数组在编译时基于NR_CPUS的值静态分配。

    640?wx_fmt=png

    上图显示了如何检测优雅周期。在第一个图中,没有CPU经过静止状态,并用红块标示。假设所有6个CPU试图同时告诉RCU,它们已经经过一个静止状态。那么,在每一对CPU中,仅仅其中某一个CPU能够获得底层rcu_node结构的锁。第二个图中,假设CPU0、3、5比较幸运的获得了底层rcu_node结构的锁,在图中标识为绿色块。一旦这些幸运的CPU结束了,那么其他CPU将获得锁,如图3所示。这三个CPU中,每一个CPU将会发现它们是组内最后一个CPU,因此所有三个CPU尝试移到上层rcu_node。此时,仅仅其中一个能获得上层rcu_node 锁。我们假设CPU1、2、4依次获得了锁,则第4、5、6图显示了相应的状态。最后,第6图显示了所有CPU已经经过一次静止状态,因此优雅周期结束。

    640?wx_fmt=png

    在上面的顺序中,没有超过3个CPU为同一个锁产生竞争,与经典RCU进行对比,我们会高兴的发现,经典RCU中,所有6个CPU都可能冲突。但是,对更多的CPU来说,可以再显著的减少锁之间的冲突。考虑有64个底层结构及64*64=4,096 CPU的分组结构,如图上图。

    在此,每一个底层rcu_node 结构的锁被64个CPU申请,将从经典RCU的4096个CPU竞争一个单一的锁降为64个CPU竞争一个锁。在一个特定的优雅周期期间,仅仅一个底层rcu_node 中的某一个CPU会申请上级rcu_node 的锁。这样,与经典RCU相比,减少了64倍的锁竞争。

    2.5.  迈向不成熟的RCU实现

    正如较早前提示的一样,这些努力的一个重要目的是使一个处于睡眠状态的CPU保持它的睡眠状态,以节约能源。与之相对的是,经典RCU至少会在一个优雅周期内唤醒每一个处于睡眠状态的CPU。当其他大多数CPU都处于空闲状态时,这些个别的CPU进行rcu写操作,会使得这种处理方法不是最优的。这种情形将在周期性的高负载系统中发生,我们需要更好的处理这种情况。

    640?wx_fmt=png

    这是通过要求所有CPU操作位于一个每CPU rcu_dynticks 结构中的计数器来实现的。不是那么准确的说,当相应的CPU处于dynticks idle模式时,计数器的值为偶数,否则是奇数。这样,RCU仅仅需要等待rcu_dynticks 计数值为奇数的CPU经过静止状态,而不必唤醒正在睡眠的CPU。如上图,每一个每CPU rcu_dynticks结构被“rcu”和“rcu_bh”实现所共享。

    2.6.  状态机

    640?wx_fmt=png

    从十分高层的视角来看,Linux内核RCU 实现可以被认为是一个高级状态机,如上图。在一个很繁忙的系统上,通常的路径是最上面的两个循环。在每一个优雅周期(GP)开始时进行初始化,等待静止状态 (QS)。在一个特定的优雅周期中,当每一个CPU都经历过静止状态时,它其实什么都不用做。在这样一个系统中,经历如下事件表明产生一个静止状态:

    1、每一次进程切换

    2、在CPU进入idle状态

    3、或者执行用户态代码时

    CPU热插拨事件将使状态机进入“CPU Offline”流程。而“holdout”CPU(那些由于软件或者硬件原因导致迟迟不能经过一次静止状态的CPU)的出现,使得不能快速经历一次静止状态,这将使状态机进入“send reschedIPIs to Holdout CPUs”(发送重新调度IPI给Holdout CPUS)流程。为了避免不必要的唤醒处于dyntick-idle 状态的CPU,RCU 实现将标记这些CPU处于扩展的静止状态,通过“Y”分支离开“CPUs in dyntick-idle Mode?”(但是请注意,这些处于dyntick-idle模式的CPU将不会被发送重新调度IPI)。最后,如果CONFIG_RCU_CPU_STALL_DETECTOR打开了,过迟的到达静止状态将使状态机进入“Complain About Holdout CPUs”流程。

    640?wx_fmt=png

    上面的状态图中,事件会与不同的数据结构交互。但是,状态图不会被任何RCU实现直接翻译为C代码。相反的,这些实现在内核中被编码为事件驱动的系统。我们通过一些用例来表示这些事件。 

    2.7. 用例

    这些事件驱动的用例包括:

    1. 开始一个新的优雅周期 

    2. 经历一个静止状态

    3. 向RCU通告一个静止状态 

    4. 进入、退出Dynticks Idle 模式 

    5. 从Dynticks Idle 模式进入中断 

    6. 从 Dynticks Idle 模式进入NMI 

    7. 标记一个CPU处于Dynticks Idle 模式 

    8. CPU离线 

    9. CPU上线 

    10. 检测一个太长的优雅周期

    2.7.1. 开始一个新的优雅周期

    rcu_start_gp()函数开始一个新的优雅周期。当一个CPU存在回调,而该回调需要等待优雅周期时,就需要调用此函数。

    rcu_start_gp()函数更新rcu_state和rcu_data结构中的状态,以标识开始一个新的优雅周期,获取->onoff 锁 (并关中断) 以防止任何并发的CPU热插拨操作,在所有的rcu_node结构中设置位,以标识所有CPU (包括当前CPU) 必须经历一次静止状态,最后释放->onoff 锁。

    设置位操作分两个阶段进行。首先,在没有持有任何锁的情况下,非叶子节点rcu_node 的位被设置,然后,在持有->lock的情况下,每一个叶子节点的rcu_node 结构的位被设置。

    2.7.2. 经历一次静止状态

    rcu和rcu_bh有各自的静止状态集合。

    RCU的静止状态是进程切换、IDLE (不管是dynticks 还是IDLE循环)、以及执行用户态程序。

    RCU-bh的静止状态是在开中断状态下,退出软中断。

    需要注意的是,rcu的静止状态也是rcu_bh的静止状态。rcu的静止状态通过调用rcu_qsctr_inc()来记录。而rcu_bh的静止状态通过调用rcu_bh_qsctr_inc()来记录。这两个函数将它们的状态记录到当前CPU的rcu_data 结构中。请注意:在2.6.32版本中,rcu_qsctr_inc和rcu_bh_qsctr_inc函数已经被更名。如何通过git查找它们被更名为什么名称,这个任务就留给作者当做练习了。

    这些函数在调度器、__do_softirq()和rcu_check_callbacks()中被调用。后面这个函数在调度时钟中断中调用,并分析状态以确定中断是否发生在一个静止状态中,以确定是调用rcu_qsctr_inc()或者 rcu_bh_qsctr_inc()。它也触发RCU_SOFTIRQ软中断,并导致当前CPU在随后的软中断上下文中调用rcu_process_callbacks(),rcu_process_callbacks函数处理RCU在每个CPU上的回调函数以释放资源。

    2.7.3. 向RCU宣告一次静止状态

    前述的rcu_process_callbacks() 函数要完成几个事情:

    1. 确定何时结束一个太长的优雅周期(通过force_quiescent_state())。

    2. 当CPU检测到优雅周期结束时,采用适当的动作。(通过 rcu_process_gp_end())。“适当的动作”包括加快本CPU的回调,以及记录新的优雅周期。同一个函数也更新状态以响应其他CPU。 

    3. 向RCU核心机制报告当前CPU的静止状态。(通过 rcu_check_quiescent_state(),它会调用 cpu_quiet())。当然,这个过程也会标记当前的优雅周期结束。

    4. 如果没有处理优雅周期,并且这个CPU有RCU回调等待优雅周期,则开始一个新的优雅周期(通过 cpu_needs_another_gp()和rcu_start_gp())。

    5. 当优雅周期结束时,调用这个CPU的回调 (通过 rcu_do_batch())。

    这些接口都经过精心实现,以避免BUG,如:错误的从上一个优雅周期向当前优雅周期报告静止状态这样的BUG。

    2.7.4. 进入和退出 Dynticks Idle模式

    调度器调用rcu_enter_nohz()进入dynticks-idle 模式,并调用 rcu_exit_nohz()离开此模式。rcu_enter_nohz() 函数递增每CPU dynticks_nesting变量,也递增每CPU dynticks计数器,然后,后者必然拥有一个偶数值。rcu_exit_nohz() 函数递减每CPU dynticks_nesting 变量,并且再一次递增每CPU dynticks计数器,后者将拥有一个奇数值。

    dynticks 计数器可以被其他 CPU采样。如果其值是偶数,那么该CPU处于扩展静止状态。类似的,如果计数器在一个特定的优雅周期内发生了改变,那么CPU必然在优雅周期期间的某个时间点上处于扩展静止状态。但是,还需要采样另外一个dynticks_nmi每CPU变量,随后我们将讨论这个变量。

    2.7.5. 从Dynticks Idle 模式进入中断

    从dynticks idle 模式进入中断由rcu_irq_enter() 和 rcu_irq_exit()处理。rcu_irq_enter() 函数递增每CPU dynticks_nesting 变量,如果此变量为0,也递增dynticks每CPU变量 (它将拥有一个奇数值)。

    rcu_irq_exit()函数递减每CPU dynticks_nesting变量。并且,如果新值是0,也递增dynticks每CPU变量 (它将拥有一个偶数值)。

    注意:进入中断会处理退出dynticks idle模式,反之也一样。进入、退出之间不一致可能导致一些混乱,不用警告你也应该想得到这一点。

    2.7.6. 从Dynticks Idle 模式进入NMI

    从dynticks idle模式进入NMI由rcu_nmi_enter()和rcu_nmi_exit()处理。这些函数同时递增dynticks_nmi计数器,但仅仅是在前述dynticks 计数是偶数时才进行递增。换句话说,如果NMI发生时,处于非dynticks-idle模式或者处于中断状态,那么 NMI将不操作dynticks_nmi计数器。

    这两个函数之间唯一的差异在于错误检查,rcu_nmi_enter()必然使dynticks_nmi计数器为奇数值,rcu_nmi_exit()必然使这个计数器为偶数值。

    2.7.7. 标记CPU处于Dynticks Idle模式

    force_quiescent_state()函数实现一个三阶段的状态机。 第一个阶段 (RCU_INITIALIZING)等待rcu_start_gp()完成对优雅周期的初始化。这个状态不是从force_quiescent_state()退出,就是从rcu_start_gp()退出。

    在第二阶段(RCU_SAVE_DYNTICK),dyntick_save_progress_counter()函数扫描还没有报告静止状态的CPU,记录它们的每CPU dynticks 和dynticks_nmi 计数器。如果这些计数器都是偶数值,那么相应的CPU处于dynticks-idle 状态,因此标记它们为扩展静止状态(通过cpu_quiet_msk()报告)。

    在第三阶段(RCU_FORCE_QS),rcu_implicit_dynticks_qs()函数再一次扫描仍然没有报告静止状态的CPU (既没有明确标示,也没有在RCU_SAVE_DYNTICK阶段隐含的标示),再一次检查每CPU dynticks 和 dynticks_nmi计数器。如果每一个值都变化,或者目前为偶数,那么相应的相应的CPU已经经过一次静止状态或者目前处于dynticks idle模式,也就是前述扩展静止状态。

    如果rcu_implicit_dynticks_qs()发现特定CPU既没有处于dynticks idle模式,也没有报告一个静止状态,它调用rcu_implicit_offline_qs(),这个函数检查CPU是否处于离线状态,如果是,那么也报告一个扩展静止状态。如果CPU在线,那么rcu_implicit_offline_qs()发送一个重新调度IPI,尝试提醒该CPU应当向RCU报告一个静止状态。

    请注意:force_quiescent_state() 既不直接调用dyntick_save_progress_counter(),也不直接调用rcu_implicit_dynticks_qs(),而是将它们传递给rcu_process_dyntick() 函数。这个函数抽象出扫描CPU、报告扩展静止状态的通用代码。

    2.7.8. CPU离线

    CPU离线事件导致rcu_cpu_notify()调用rcu_offline_cpu(),在rcu和rcu_bh上依次调用__rcu_offline_cpu()。这个函数清除离线CPU的位,这样,后面的优雅周期将不再期望这个CPU宣告静止状态,随后调用cpu_quiet(),以宣告离线扩展静止状态。这是在持有全局->onofflock锁的情况下执行的,这是为了防止与优雅周期初始化相冲突。

    2.7.9. CPU上线

    CPU上线事件导致rcu_cpu_notify()调用rcu_online_cpu(),用于初始化CPU的dynticks状态,然后调用rcu_init_percpu_data()初始化CPU的rcu_data 数据结构,也设置这个 CPU的位(同样通过全局->onofflock进行保护),这样后面的优雅周期将等待这个CPU的静止状态。最后,rcu_online_cpu()设置这个CPU的RCU 软中断向量。

    2.7.10. 检测太长的优雅周期

    当配置了CONFIG_RCU_CPU_STALL_DETECTOR内核参数时,record_gp_stall_check_time() 函数记录当前时间,以及3秒以后的时间戳。如果当前优雅周期到期后仍然没有结束,那么check_cpu_stall函数将检测罪魁祸首。并且如果当前CPU是造成延迟的CPU,则调用print_cpu_stall(),如果不是,则调用print_other_cpu_stall()。两个jiffies的时间差有助于确保其他CPU在可能的情况下报告它的状态,利用这个时间差,CPU能够做一些事情,例如跟踪它自己的堆栈。

    2.8. 测试

    RCU是基本的同步代码,因此RCU的错误导致的后果是随机的、难于调试的内存错误。因此,高可靠的RCU是非常重要的。这些可靠性来自于小心的设计,但是最终还是需要依赖于高强度的压力测试。

    幸运的是,虽然有一些关于覆盖性方面的争论,但是仍然可以对软件进行一些压力测试。实际上,进行这些测试是被强烈建议的,因为不对你的软件进行折磨性测试的话,它就会反过来折磨你,这种折磨来自于:它在不合时宜的时候崩溃掉。

    因此,我们使用rcutorture模块来对RCU进行压力测试。

    但是,根据通常情况下的RCU用法来对RCU进行测试,显得还不是很充分。也有必要针对不常用的情况进行压力测试。例如,CPU并发的上线或者离线,CPU并发的进入及退出dynticks idle模式。Paul使用了一个脚本CodeSamples,并向模块rcutorture使用test_no_idle_hz 模块参数对dynticks idle模式进行压力测试。有时作者也比较疑神疑鬼,因此尽量在测试时运行一个kernbench负载测试程序。在128路的机器上运行10个小时的压力测试,看起来是足够测试出几乎所有BUG了。

    实际上这还不算完。Alexey Dobriyan和Nick Piggin早在2008年就证明过,以所有相关内核参数组合对RCU进行压力测试是必要的。相关的内核参数可以使用另外一个脚本CodeSamples进行标识。

    1. CONFIG_CLASSIC_RCU:经典 RCU。

    2. CONFIG_PREEMPT_RCU:可抢占 (实时) RCU。

    3. CONFIG_TREE_RCU:用于大型SMP系统的经典 RCU。

    4. CONFIG_RCU_FANOUT:每一个rcu_node 的子结点数量。

    5. CONFIG_RCU_FANOUT_EXACT:平衡rcu_node 树。

    6. CONFIG_HOTPLUG_CPU:允许 CPU上线、离线。

    7. CONFIG_NO_HZ:打开dyntick-idle 模式。

    8. CONFIG_SMP:打开 multi-CPU选项。

    9. CONFIG_RCU_CPU_STALL_DETECTOR:当CPU进入扩展静止状态时进行RCU检测。

    10. CONFIG_RCU_TRACE:在debugfs中生成 RCU跟踪文件。

    我们忽略CONFIG_DEBUG_LOCK_ALLOC 配置变量,因为我们假设分级RCU不能打断 lockdep。仍然有10个配置变量,如果它们是独立的布尔值,则导致1024种组合。幸运的是,首先,其中前三个是互斥的,这样可以将组合数量减少到384个,但是CONFIG_RCU_FANOUT可以取值2-64,将组合数量增加到12,096。这么大量的组合是不可能都实施的。

    关键的一点是:如果CONFIG_CLASSIC_RCU或者CONFIG_PREEMPT_RCU有效时,预期仅仅CONFIG_NO_HZ 和 CONFIG_PREEMPT 可能会改变其行为。这几乎减少了三分之二的组合。

    而且,并不是这些所有可能的CONFIG_RCU_FANOUT值都会产生显著有效的结果,实际上仅仅一部分情况需要分别测试:

    1. 单结点“tree”。

    2. 两级平衡树。

    3. 三级平衡树。

    4. 自动平衡树,当 CONFIG_RCU_FANOUT 指定一个不平衡树,但是没有配置CONFIG_RCU_FANOUT_EXACT 时,进行自动平衡。 

    5. 非平衡树。

    更进一步说,CONFIG_HOTPLUG_CPU仅仅在指定CONFIG_SMP 时才有用,CONFIG_RCU_CPU_STALL_DETECTOR是独立的,因此仅仅需要测试一次(然而有些人比我还多疑,他们可能决定在有CONFIG_SMP和没有CONFIG_SMP 时,都测试它)。类似的,CONFIG_RCU_TRACE也仅仅需要测试一次。但是象我一样多疑的人,会选择在有CONFIG_NO_HZ 和没有CONFIG_NO_HZ 时,都测试一下它。

    这允许我们在15种测试情形下,得到一个覆盖率较好的RCU测试。所有这些测试情形都指定如下配置参数以运行rcutorture,这样CONFIG_HOTPLUG_CPU=n会产生实际的效果:

    CONFIG_RCU_TORTURE_TEST=m

    CONFIG_MODULE_UNLOAD=y

    CONFIG_SUSPEND=n

    CONFIG_HIBERNATION=n

    15个测试用例如下:

    1. 强制单节点“树”,用于小型系统:

    CONFIG_NR_CPUS=8

    CONFIG_RCU_FANOUT=8

    CONFIG_RCU_FANOUT_EXACT=n

    CONFIG_RCU_TRACE=y

    CONFIG_PREEMPT_RCU=n

    CONFIG_CLASSIC_RCU=n

    CONFIG_TREE_RCU=y

    2. 强制两级节点树用于大型系统:

    CONFIG_NR_CPUS=8

    CONFIG_RCU_FANOUT=4

    CONFIG_RCU_FANOUT_EXACT=n

    CONFIG_RCU_TRACE=n

    CONFIG_PREEMPT_RCU=n

    CONFIG_CLASSIC_RCU=n

    CONFIG_TREE_RCU=y

    3. 强制三级节点树,用于非常大型的系统: 

    CONFIG_NR_CPUS=8

    CONFIG_RCU_FANOUT=2

    CONFIG_RCU_FANOUT_EXACT=n

    CONFIG_RCU_TRACE=y

    CONFIG_PREEMPT_RCU=n

    CONFIG_CLASSIC_RCU=n

    CONFIG_TREE_RCU=y

    4. 测试自动平衡:

    CONFIG_NR_CPUS=8

    CONFIG_RCU_FANOUT=6

    CONFIG_RCU_FANOUT_EXACT=n

    CONFIG_RCU_TRACE=y

    CONFIG_PREEMPT_RCU=n

    CONFIG_CLASSIC_RCU=n

    CONFIG_TREE_RCU=y

    5. 测试不平衡树:

    CONFIG_NR_CPUS=8

    CONFIG_RCU_FANOUT=6

    CONFIG_RCU_FANOUT_EXACT=y

    CONFIG_RCU_CPU_STALL_DETECTOR=y

    CONFIG_RCU_TRACE=y

    CONFIG_PREEMPT_RCU=n

    CONFIG_CLASSIC_RCU=n

    CONFIG_TREE_RCU=y

    6. 禁止CPU延迟检测:

    CONFIG_SMP=y

    CONFIG_NO_HZ=y

    CONFIG_RCU_CPU_STALL_DETECTOR=n

    CONFIG_HOTPLUG_CPU=y

    CONFIG_RCU_TRACE=y

    CONFIG_PREEMPT_RCU=n

    CONFIG_CLASSIC_RCU=n

    CONFIG_TREE_RCU=y

    7. 禁止 CPU延迟检测及dyntick idle 模式:

    CONFIG_SMP=y

    CONFIG_NO_HZ=n

    CONFIG_RCU_CPU_STALL_DETECTOR=n

    CONFIG_HOTPLUG_CPU=y

    CONFIG_RCU_TRACE=y

    CONFIG_PREEMPT_RCU=n

    CONFIG_CLASSIC_RCU=n

    CONFIG_TREE_RCU=y

    8. 禁止 CPU延迟检测及CPU热插拨:

    CONFIG_SMP=y

    CONFIG_NO_HZ=y

    CONFIG_RCU_CPU_STALL_DETECTOR=n

    CONFIG_HOTPLUG_CPU=n

    CONFIG_RCU_TRACE=y

    CONFIG_PREEMPT_RCU=n

    CONFIG_CLASSIC_RCU=n

    CONFIG_TREE_RCU=y

    9. 禁止 CPU延迟检测,dyntick idle 模式,及CPU热插拨:

    CONFIG_SMP=y

    CONFIG_NO_HZ=n

    CONFIG_RCU_CPU_STALL_DETECTOR=n

    CONFIG_HOTPLUG_CPU=n

    CONFIG_RCU_TRACE=y

    CONFIG_PREEMPT_RCU=n

    CONFIG_CLASSIC_RCU=n

    CONFIG_TREE_RCU=y

    10. 禁止SMP、CPU延迟检测、dyntick idle 模式、及CPU热插拨:

    CONFIG_SMP=n

    CONFIG_NO_HZ=n

    CONFIG_RCU_CPU_STALL_DETECTOR=n

    CONFIG_HOTPLUG_CPU=n

    CONFIG_RCU_TRACE=y

    CONFIG_PREEMPT_RCU=n

    CONFIG_CLASSIC_RCU=n

    CONFIG_TREE_RCU=y

    这个组合有一些编译警告。

    11. 禁止SMP、禁止CPU热插拨:

    CONFIG_SMP=n

    CONFIG_NO_HZ=y

    CONFIG_RCU_CPU_STALL_DETECTOR=y

    CONFIG_HOTPLUG_CPU=n

    CONFIG_RCU_TRACE=y

    CONFIG_PREEMPT_RCU=n

    CONFIG_CLASSIC_RCU=n

    CONFIG_TREE_RCU=y

    12. 有dynticks idle 但是没有抢占的情况下,测试经典RCU:

    CONFIG_NO_HZ=y

    CONFIG_PREEMPT=n

    CONFIG_RCU_TRACE=y

    CONFIG_PREEMPT_RCU=n

    CONFIG_CLASSIC_RCU=y

    CONFIG_TREE_RCU=n

    13. 有抢占但是没有dynticks idle时,测试经典RCU:

    CONFIG_NO_HZ=n

    CONFIG_PREEMPT=y

    CONFIG_RCU_TRACE=y

    CONFIG_PREEMPT_RCU=n

    CONFIG_CLASSIC_RCU=y

    CONFIG_TREE_RCU=n

    14. 在dynticks idle情况下,测试可抢占RCU:

    CONFIG_NO_HZ=y

    CONFIG_PREEMPT=y

    CONFIG_RCU_TRACE=y

    CONFIG_PREEMPT_RCU=y

    CONFIG_CLASSIC_RCU=n

    CONFIG_TREE_RCU=n

    15. 在没有 dynticks idle时,测试可抢占RCU:

    CONFIG_NO_HZ=n

    CONFIG_PREEMPT=y

    CONFIG_RCU_TRACE=y

    CONFIG_PREEMPT_RCU=y

    CONFIG_CLASSIC_RCU=n

    CONFIG_TREE_RCU=n

    对于每一次大的影响RCU核心代码的变化,都应当以上面的组合运行rcutorture,并且在CONFIG_HOTPLUG_CPU时,并发的进行CPU热插拨。对小的变化,在每一种情况下运行kernbench就行了。当然,如果变化仅仅限于配置参数的部分子集,就可以减少测试用例的数量。

    作者强烈推荐压力测试软件:Geneva Convention!

    2.9. 结论

    这个分级RCU实现减少了锁竞争,避免了不必要的唤醒dyntick-idle睡眠状态的CPU,因此有助于调试Linux CPU热插拨代码。这个实现被设计用于处理数千个CPU的大型系统,并且在64位系统上,CPU数量限制是250,000,在今后一段时间内,这个限制是没有问题的。

    这个RCU实现当然也有一些局限:

    1. force_quiescent_state()可能在关中断下扫描整个CPU集。这在实时RCU实现中,是一个重大缺陷。因此,如果需要在可抢占RCU中加入分级,则需要其他方法。在4096个CPU的系统中,它可能会产生一些问题,但是需要在实际的系统中进行测试以证明真的有问题。

    在繁忙的系统中,不能指望force_quiescent_state()扫描会发生,CPU将在开始一个静止状态后,在三个jiffies内经历一次静止状态。在半繁忙的系统中,仅仅处于dynticks-idle模式的CPU需要扫描。其他情况下,例如,在一个dynticks-idle CPU扫描过程中,处理一个中断时,后继的扫描是需要的。但是,这样的扫描是分别在相应的CPU上执行的,因此相应的调度延迟仅仅影响该扫描过程所在的CPU负载。

    如果扫描被证明确实有问题,一个好的方法是进行递增扫描。这将稍微增加一点代码复杂性,也增加一点结束优雅周期的时间,但是这也确实算是一个好的方案。

    2. rcu_node分级在编译时创建,因此其长度是最大的CPU数量NR_CPUS。 但是,即使在4,096 CPU的系统中,在64位系统上,rcu_node 分级也仅仅消耗65个缓存行。(即使在32位系统上包含4,096 CPUs也是这样!)。当然,在一个16 CPU的系统中,配置NR_CPUS=4096将使用一个二级树,实际上在这种情况下,单节点树也会运行得很好。虽然这个配置会增加锁的负载,但是实际上不会影响经常执行的读端代码,因此事实上不会有太大的问题。

    3. 这个补丁会稍微增加内核代码及数据尺寸:在NR_CPUS=4的系统中,从经典RCU的1,757字节内核代码、456字节数据,共2213字节的内核尺寸,而分级RCU则增加到4,006字节的内核代码、624字节的内核数据,共计4,630字节尺寸。即使对大多数嵌入式系统来说,这也不是一个问题。这些系统通常有上百兆主内存。但是对特别小的系统来说,这可能就是一个问题了,需要提供两种类型的RCU实现以满足这样的嵌入式系统。不过有一个有趣的问题,在这样的系统中,也许仅仅包含一个CPU,这样的系统完全可以用一个特别简单的RCU实现。

    即使有这些问题,相对于经典RCU来说,在数百个CPU的系统中,这个分级RCU实现仍然是一个巨大的进步。最后需要说明一下,经典RCU设计用于16-32个CPU的系统。

    在某些地方,在可抢占RCU实现中使用分级是有必要的。

    后续章节将继续分析分级RCU的代码,以及Linux中其他一些RCU的实现。也许还会讨论实现RCU这类复杂并行软件的开发方法及其形式化验证。


    近期精彩文章:

    EMC潘国林: 大话存储系列之磁盘娶亲(RAID)

    ARM刘永康: 浅谈Android数字版权管理之视频保护

    宋宝华: 是谁关闭了Linux抢占,而抢占又关闭了谁?

    ...

    展开全文
  • 内核源码中有很多rcu的标志,到底什么是RCU,一直都不清楚。 RCU(Read-Copy Update),是 Linux 中比较重要的一种同步机制。顾名思义就是 “读 , 拷贝更新”,再直白点是“随意读,但更新数据的时候,需要先复制...
  • RCU(Read-Copy Update),是 Linux 中比较重要的一种同步机制。顾名思义就是“读,拷贝更新”,再直白点是“随意读,但更新数据的时候,需要先复制一份副本,在副本上完成修改,再一次性地替换旧数据”。这是 Linux ...
  • 本文简介本文介绍“玩具式”RCU实现。这些实现并不注重性能、实用性,也不能使用于生产环境中,而仅仅是为了清晰的传递RCU的...同时,他也是《深入理解并行编程》一书的译者。该书作者Paul E.McKeney是IBM Linux中心领
  • RCU 是READCOPY UPDATE的简写,设计思想的来源是,对读写锁进行优化,减少写者之间的同步,即如果同时有几个写者进行竞争,那么写者就对资源进行拷贝,从而允许多个写者对资源进行修改,最后由系统决定什么时候更新...
  • 背景Read the fucking source code! --By 鲁迅A picture is worth a thousand words. --By 高尔基说明:Kerne...
  • 经过之前的分析基本清楚了整个RCU的结构体,下面就通过分代码来解读RCU的实现。 void synchronize_rcu(void) { if (!rcu_scheduler_active) return; wait_rcu_gp(call_rcu); } 当rcu_scheduler_active变量将...
  • 深入理解 RCU 实现

    2017-04-18 22:06:03
    深入理解RCU实现 ——基于内核2.6.21 RCU实现(lvyilong316) RCU(Read-Copy Update),顾名思义就是读-拷贝修改,它是基于其原理命名的。对于被RCU保护的共享数据结构,读者不需要获得任何锁就可以访问它,但...
  • Linux RCU

    2017-07-07 09:22:15
    在《深入Linux设备驱动程序内核机制》第4章中,已经非常明确地叙述了RCU背后所遵循的规则,这些规则是从一个比较高的视角来看,因为我觉得过多的代码分析反而容易让读者在细节上迷失方向。最近拿到书后,我又重头...
  • 在《深入Linux设备驱动程序内核机制》第4章中,已经非常明确地叙述了RCU背后所遵循的规则,这些规则是从一个比较高的视角来看,因为我觉得过多的代码分析反而容易让读者在细节上迷失方向。最近拿到书后,我又重头...
  • 深入理解RCU实现

    2018-02-10 15:24:33
    ——基于内核2.6.21 RCU实现(lvyilong316)RCU(Read-Copy Update),顾名思义就是读-拷贝修改,它是基于其原理命名的。对于被RCU保护的共享数据结构,读者不需要获得任何锁就可以访问它,但写者在访问它时首先拷贝一...
1 2 3 4 5 ... 20
收藏数 1,683
精华内容 673
关键字:

linux rcu 深入理解