RCU(Read-CopyUpdate),是Linux中比较重要的一种同步机制。顾名思义就是“读,拷贝更新”,再直小白点是“随意读,但更新数据的时侯,须要先复制一份副本,在副本上完成更改,再一次性地替换旧数据”。这是Linux内核实现的一种针对“读多写少”的共享数据的同步机制。
不同于其他的同步机制,它允许多个读者同时访问共享数据,但是读者的性能不会受影响(“随意读”),读者与写者之间也不须要同步机制(但须要“复制后再写”),但假如存在多个写者时,在写者把更新后的“副本”覆盖到原数据时,写者与写者之间须要借助其他同步机制保证同步。
RCU的一个典型的应用场景是数组,在Linuxkernel中还专门提供了一个头文件(include/linux/rculist.h),提供了借助RCU机制对数组进行增删查改操作的插口。本文将通过一个反例,借助rculist.h提供的插口对数组进行增删查改的操作,来述说RCU的原理,以及介绍Linuxkernel中相关的API(基于Linuxv3.4.0的源码)。
降低数组项
Linuxkernel中借助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行的显存屏障。哪些是显存屏障(MemoryBarrier)呢?CPU采用流水线技术执行指令时,只保证有显存依赖关系的指令的执行次序,比如p=v;a=*p;,因为第2条指令访问的表针p所指向的显存依赖于第1条指令,因而CPU会保证第1条指令在第2条指令执行前执行完毕。但对于没有显存依赖的指令linux内核原理与分析,诸如上述__list_add_rcu()插口中,如果把第8行写成prev->next=new;,因为这个形参操作并没涉及到对new表针指向的显存的访问,因而觉得不依赖于6,7行对new->next和new->prev的形参,CPU有可能实际运行时会先执行prev->next=new;再执行new->prev=prev;,这都会导致new表针(也就是新加入的数组项)还没完成初始化就被加入了数组中,如果这时正好有一个读者正好遍历访问到了该新的数组项(由于RCU的一个重要特征就是可随便执行读操作),都会访问到一个未完成初始化的数组项!通过设置显存屏障才能解决该问题,它保证了在显存屏障后面的指令一定会先于显存屏障后面的指令被执行。这就保证了被加入到数组中的项linux内核原理与分析,一定是早已完成了初始化的。
最后提醒一下,这儿要注意的是,假如可能存在多个线程同时执行添加数组项的操作,添加数组项的操作须要用其他同步机制(如spin_lock等)进行保护。
Linux内核开发相关学习视频资料,后台私信【内核】获取
访问数组项
Linuxkernel中访问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-sidecriticalsections)。在说读端临界区之前,我们先瞧瞧读取数组项的宏函数list_for_each_entry_rcu。溯源源码linux删除文件夹,获取一个数组项表针主要调用的是一个名为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("%dn", p1->field);
}
rcu_read_unlock();
按照rcu_dereference()的实现,最终疗效就是把一个表针形参给另一个,那假如把上述第2行的rcu_dereference()直接写成p1=p会如何呢?在通常的处理器构架上是一点问题都没有的。但在alpha上,编译器的value-speculation优化选项听说可能会“猜测”p1的值,之后重排指令先取值p1->field~因而Linuxkernel中,smp_read_barrier_depends()的实现是构架相关的,arm、x86等构架上是空实现,alpha上则加了显存屏障,以保证先获得p真正的地址再做解引用。因而上一节“增加数组项”中提及的“__rcu”编译选项强制检测是否使用rcu_dereference()访问受RCU保护的数据,实际上是为了让代码拥有更好的可移植性。
如今回到读端临界区的问题上来。多个读端临界区不互斥,即多个读者可同时处于读端临界区中,但一块显存数据一旦才能在读端临界区内被获取到表针引用,这块显存块数据的释放必须等到读端临界区结束,等待读端临界区结束的LinuxkernelAPI是synchronize_rcu()。读端临界区的检测是全局的,系统中有任何的代码处于读端临界区,synchronize_rcu()就会阻塞,晓得所有读端临界区结束才能返回。为了直观理解这个问题,举以下的代码实例:
/* `p` 指向一块受 RCU 保护的共享数据 */
/* reader */
rcu_read_lock();
p1 = rcu_dereference(p);
if (p1 != NULL) {
printk("%dn", 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()阻塞的这一段时间,有个名子,称作Graceperiod。而Reader4,5,6,无论与Graceperiod的时间关系怎么,因为获取引用的时间在t1以后,都未能获得p表针的引用,因而不会步入p1!=NULL的分支。
删掉数组项
晓得了前面说的Graceperiod,理解数组项的删掉就很容易了。常见的代码模式是:
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()之前步入了读端临界区linux删除命令,synchronize_rcu()都会保证读端临界区结束时才能真正释放数组项的显存,而不会释放读者正在访问的数组项。
更新数组项
前文提及,RCU的更新机制是“CopyUpdate”,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;
}
Linux内核开发相关学习视频资料,后台私信【内核】获取
Linux内核系统学习大纲: