0%

Linux并发与同步(四)RCU

原图

RCU概述

RCU的全称Read-Copy-Update,它是Linux内核中一种重要的同步机制。Linux内核中已有了原子操作、自旋锁、读写自旋锁、读写信号量、互斥锁等锁机制,为什么要单独设计一个比它们复杂得多的新机制呢?回忆自旋锁、读写信号量和互斥锁的实现,它们都使用了原子操作指令,即原子地访问内存,多CPU争用共享的变量会让高速缓存一致性变得很糟,使得性能下降。

以读写信号量为例,除了上述缺点外,读写信号量还有一个致命弱点,它允许多个读者同时存在,但是读者和写者不能同时存在。因此RCU机制要实现的目标是,读者线程没有同步开销,或者说同步开销变得很小,甚至可以忽略不计,不需要额外的锁,不需要使用原子操作指令和内存屏障指令,即可畅通无阻地访问;而把需要同步的任务交给写者线程,写者线程等待所有读者线程完成后才会把旧数据销毁。

在RCU中,如果有多个写者同时存在,那么需要额外的保护机制。RCU机制的原理可以概括为RCU记录了所有指向共享数据的指针的使用者,当要修改共享数据时,首先创建一个副本,在副本中修改。所有读者线程离开读者临界区之后,指针指向修改后的副本,并且删除旧数据。

RCU的一个重要的应用场景是链表,链表可以有效地提高遍历读取数据的效率。读取链表成员数据时通常只需要 rcu_read_lock()函数,允许多个线程同时读取该链表,并且允许一个线程同时修改链表。那为什么这个过程能保证链表访问的正确性呢? 在读者遍历链表时,假设另外一个线程删除了一个节点。删除线程会把这个节点从链表中移出,但不会直接销毁它。RCU会等到所有读线程读取完成后,才销毁这个节点。 RCU提供的接口如下。

  • rcu_read_lock()/ rcu_read_unlock():组成一个RCU读者临界区
  • rcu_dereference():用于获取被RCU保护的指针,读者线程要访问RCU保护的共享数据,需要使用该函数创建一个新指针,并且指向被RCU保护的指针
  • rcu_assign_pointer():通常用于写者线程。在写者线程完成新数据的修改后,调用该接口可以让被RCU保护的指针指向新创建的数据,用RCU的术语是发布了更新后的数据
  • synchronize_rcu():同步等待所有现存的读访问完成
  • call_rcu():注册一个回调函数,当所有现存的读访问完成后,调用这个回调函数销毁旧数据

关于RCU的一个简单例子

下面通过关于RCU的一个简单例子来理解上述接口的含义,该例子来源于内核源代码中的 Documents/RCU/whatisrcu.rst,并且省略了一些异常处理情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
《关于RCU的一个简单例子》
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/init.h>
#include <linux/slab.h>
#include <linux/spinlock.h>
#include<linux/rcupdate.h>
#include <linux/kthread.h>
#include <linux/delay.h>
struct foo
{
int a:
struct rcu_head rcu;
};

static struct foo *g_ptr;

static void myrcu_reader_thread(void* data) //读者线程
{
struct foo *p = NULL;
while(1)
{
msleep(200);
rcu_read_lock();
p = rcu_dereference(g_ptr);
if (p) {
printk("%s: read a = %d\n", __func__, p->a);
}
rcu_read_unlock();
}
}

static void myrcu_del(struct rcu_head *rh)
{
struct foo *p = container_of(rh, struct foo, rcu);
printk("%s: read a = %d\n", __func__, p->a);
kfree(p);
}

static void myrcu_writer_thread(void* p) //写者线程
{
struct foo *new;
struct foo *old;
int value = (unsigned int)p;

while(1)
{
msleep(400);
struct foo *new_ptr = kmalloc(sizeof(struct foo), GFP_KERNEL);
old = g_ptr;
printk("%s: read a = %d\n", __func__, value);
*new_ptr = *old;
new_ptr->a = value;
rcu_assign_pointer(g_ptr, new_ptr);
call_rcu(&old_rcu, myrcu_del);
value++;
}
}

static int __init my_test_init(void)
{
struct task_struct *reader_thread;
struct task_struct *writer_thread;
int value = 5;

printk("BEN: my module init\n");

g_ptr = kzalloc(sizeof(struct foo), GFP_KERNEL);

read_thread = kthread_run(myrcu_reader_thread, NULL, "rcu_reader");
writer_thread = kthread_run(myrcu_writer_thread, (void*)(unsigned long)value, "rcu_writer");

return 0;
}

static void __exit my_test_exit(void)
{
printk("GoodBye\n");
if(g_ptr)
kfree(g_ptr);
}

MODULE_LICENCE("GPL);
module_init(my_test_init);

该例子的目的是通过RCU机制保护 my_test_init()函数分配的共享数据结构g_ptr,并创建一个读者线程和一个写者线程来模拟同步场景。对于 myrcu_reader_thread,注意以下几点。

  • 通过 rcu_read_lock()函数和 rcu_read_unlock()函数来构建一个读者临界区
  • 调用 rcu_dereference()函数获取被保护数据的副本,即指针p,这时p和g_ptr都指向旧的被保护数据
  • 读者线程每隔200ms读取一次被保护数据

对于 myrcu_writer_thread,注意以下几点。

  • 分配新的保护数据,并修改相应数据
  • rcu_assign_pointer()函数让g_ptr指向新数据
  • call_rcu()函数注册一个回调函数,确保所有对旧数据的引用都执行完成之后,才调用回调函数来删除旧数据
  • 写者线程每隔400ms修改被保护数据

上述过程如图所示:

在所有访问结束之后,内核可以释放旧数据,关于何时释放旧数据,内核提供了两个接口函数--synchronize_rcu()和call_rcu()。

经典RCU和 Tree RCU

本节重点介绍经典RCU和 Tree RCU的实现,可睡眠RCU和可抢占RCU留给读者学习。RCU里有两个很重要的概念,分别是宽限期( Grace Period,GP)和静止状态(Quiescent State, QS)。

  • 宽限期:GP有生命周期,有开始和结束之分。从GP开始算起,如果所有处于读者临界区的CPU都离开了临界区,也就是都至少经历了一次QS,那么认为一个GP可以结束了。GP结束后,RCU会调用注册的回调函数,如销毁旧数据等
  • 静止状态:在RCU设计中,如果一个CPU处于RCU读者临界区中,说明它的状态是活跃的:如果在时钟滴答中检测到该CPU处于用户模式或空闲状态,说明该CPU已经离开了读者临界区,那么它是QS。在不支持抢占的RCU实现中,只要检测到CPU有上下文切换,就可以知道离开了读者临界区

RCU在开发 Linux2.5内核时已经被添加到Linux内核中,但是在 Linux2.6.29内核之前的RCU通常称为经典RCU( Classic RCU)。经典RCU在大型系统中遇到了性能问题,后来在 Linux2.6.29内核中IBM的内核专家 Paul E. Mckenney 提出了 Tree RCU的实现, Tree RCU也称为 Hierarchical RCU。

经典RCU的实现在超级大系统中遇到了问题,特别是有些系统的CPU内核超过了1024个,甚至达到4096个。经典RCU在判断是否完成一次GP时采用全局的 cpumask图。如果每位表示一个CPU,那么在1024个CPU内核的系统中, cpumask 位图就有1024位。每个CPU在GP开始时要设置位图中对应的位,GP结束时要清除相应的位。全局的cpumask位图会导致很多CPU竞争使用,因此需要自旋锁来保护位图。这样导致锁争用变得很激烈,激烈程度随着CPU的个数线性递增。以4核CPU为例,经典RCU的实現如图所示。

而 Tree RCU的实现巧妙地解决了cpumask位图竞争锁的问题,以上述4核CPU为例,假设Tree RCU以两个CPU为一个rcu_node,这样4个CPU被分配到两个rcu_node,使用另外一个rcu_node来管理这两个rcu_node。节点1管理pu0和cpu1,节点2管理pu2和cpu3。而节点0是根节点,管理节点1和节点2。每个节点只需要两位的位图就可以管理各自的CPU或者节点,每个节点都通过各自的自旋锁来保护相应的位图。

假设4个CPU都经历过一个QS,那么4个CPU首先在Leve0的节点1和节点2上修改位图。对于节点1或者节点2来说,只有两个CPU竞争锁,这比经典RCU上的锁争用要减少一半。当节点1和节点2上的位图都被清除干浄后,才会清除上一级节点的位图,并且只有最后清除节点的CPU才有机会尝试清除上一级节点的位图。因此对于节点0来说,还是两个CPU争用锁。整个过程中只有两个CPU争用一个锁。这类似于足球比赛,进入四强的4支球队被分成上下半区,每个半区有两支球队,只有半决赛获胜的球队才能进入决赛。

参考文献

《奔跑吧Linux内核》