深入理解 Linux 的 RCU 机制

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(https://lwn.net/Articles/262464/)

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(http://www.cnblogs.com/icanth/archive/2012/06/10/2544300.html)

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

梁康的专栏

1 篇文章1 人订阅

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏hbbliyong

C#在.NET编译执行过程

1..NET语言的编译器接受源代码文件,并生成名为程序集的输出文件。 程序集要么是可执行的,要么是DLL 程序集里的代码并不是本机代码,而是一种名称为CIL的中...

2829
来自专栏张善友的专栏

Contact Manager Web API 示例[2] Web API Routing

联系人管理器web API是一个Asp.net web api示例程序,演示了通过ASP.NET Web API 公开联系信息,并允许您添加和删除联系人,示例地...

1759
来自专栏蘑菇先生的技术笔记

那些年我们一起追过的缓存写法(三)

26010
来自专栏算法修养

后端处理高并发状态的多次重复请求

  相信做Web的,都有可能遇到有多次重复请求发送到后端的情况。而这些重复请求,可能大都是由于在网络较差的情况下,用户多次连续点击。最后导致后端面临处理大量重复...

3618
来自专栏Phoenix的Android之旅

绕过谷歌禁止反射的一种办法

Androi P之后Google可能会禁止使用反射来获取隐藏方法的调用,虽然在preview版本中只会以log的形式提示,但后续的版本可能会在使用反射时直接抛出...

731
来自专栏柠檬先生

Angularjs基础(一)

(一) 模型——视图——控制器     端对端的解决方案,AngularJS 试图成为WEB 应用中的一种段对端的解决方案。AngylarJS 的出众  ...

19010
来自专栏祝威廉

如何使用MLSQL中的帮助指令学习模块的使用

MLSQL 已经实现了文章中描述的功能 如何实现语法的自解释(MLSQL易用性设计有感) 。

744
来自专栏菜鸟计划

angularjs 控制器、作用域、广播详解

一、控制器 首先列出几种我们平常使用控制器时的几种误区: ? 我们知道angualrJs中一个控制器时可以对应不同的视图模板的,但这种实现方式存在的问题是: 如...

3284
来自专栏快乐八哥

JSON入门指南--服务端处理JSON

平时公司使用的ASP.NET MVC3来开发Web项目,其实在ASP.NET中已经原生的支持JSON。所以基本不需要引进Newtonsoft.Json.dll。...

1918
来自专栏猛牛哥的博客

aardio在外部进程执行汇编代码时传入自定义参数的方法

1754

扫码关注云+社区