RCU是什么

在Linux中，RCU代表"Read-Copy-Update"（读-拷贝-更新），是一种用于实现并发性的技术。它主要应用于多核系统中的共享数据结构，以提高读操作的性能，并减少对写操作的影响。

为什么需要RCU？它解决了什么问题

性能提升

当线程在多个cpu上争抢进入临界区的时候，都会操作那个在多个cpu之间共享的数据lock。cpu0操作了lock，为了数据的一致性，cpu0的操作会导致其他cpu的L1中的lock变成无效，在随后的来自其他cpu对lock的访问会导致L1 cache miss（更准确的说是communication cache miss），必须从下一个level的cache中获取，同样的，其他cpu的L1 cache中的lock也被设定为invalid，从而引起下一次其他cpu上的communication cache miss。

RCU的read side不需要访问这样的“共享数据”，从而极大的提升了reader侧的性能。

Pasted image 20231002002640|800

支持writer和readers的并发

spin lock是互斥的，任何时候只有一个thread（reader or writer）进入临界区，rwlock要好一些，允许多个reader并发执行，提高了性能。不过，reader和updater不能并发执行，RCU解除了这些限制，允许一个updater（不能多个updater进入临界区，这可以通过spinlock来保证）和多个reader并发执行。

Pasted image 20231002002921|800

rwlock允许多个reader并发，因此，在上图中，三个rwlock reader可以并行执行。当rwlock writer试图进入的时候（红色虚线），只能spin，直到所有的reader退出临界区。一旦有rwlock writer在临界区，任何的reader都不能进入，直到writer完成数据更新，立刻临界区。绿色的reader thread们又可以并发访问了。

rwlock的一个特点就是确定性，白色的reader一定是读取的是old data，而绿色的reader一定获取的是writer更新之后的new data。

RCU和传统的锁机制不同，当RCU updater进入临界区的时候，即便是有reader在也无所谓，它可以长驱直入，不需要spin。同样的，即便有一个updater正在临界区里面工作，这并不能阻挡RCU reader的步伐。由此可见，RCU的并发性能要好于rwlock，特别如果考虑cpu的数目比较多的情况，那些处于spin状态的cpu在无谓的消耗，多么可惜，随着cpu的数目增加，rwlock性能不断的下降。

RCU reader和updater由于可以并发执行，因此这时候的被保护的数据有两份，一份是旧的，一份是新的，对于白色的RCU reader，其读取的数据可能是旧的，也可能是新的，和数据访问的timing相关，当然，当RCU update完成更新之后，新启动的RCU reader（绿色block）读取的一定是新的数据。

实现原理

Pasted image 20231002003542|800

RCU涉及的数据有两种，一个是指向要保护数据的指针，我们称之RCU protected pointer。另外一个是通过指针访问的共享数据，我们称之RCU protected data，当然，这个数据必须是动态分配的。对共享数据的访问有两种，一种是writer，即对数据要进行更新，另外一种是reader。如果在有reader在临界区内进行数据访问，对于传统的，基于锁的同步机制而言，reader会阻止writer进入（例如spin lock和rw spin lock。seqlock不会这样，因此本质上seqlock也是lock-free的），因为在有reader访问共享数据的情况下，write直接修改data会破坏掉共享数据。怎么办呢？当然是移除了reader对共享数据的访问之后，再让writer进入了（writer稍显悲剧）。对于RCU而言，其原理是类似的，为了能够让writer进入，必须首先移除reader对共享数据的访问，怎么移除呢？创建一个新的copy是一个不错的选择。

因此RCU writer的动作分成了两步：

（1）removal：write分配一个new version的共享数据进行数据更新，更新完毕后将RCU protected pointer指向新版本的数据。一旦把RCU protected pointer指向的新的数据，也就意味着将其推向前台，公布与众（reader都是通过pointer访问数据的）。通过这样的操作，原来read 0、1、2对共享数据的reference被移除了（对于新版本的受RCU保护的数据而言），它们都是在旧版本的RCU protected data上进行数据访问。

（2）reclamation：共享数据不能有两个版本，因此一定要在适当的时机去回收旧版本的数据。当然，不能太着急，不能reader线程还访问着old version的数据的时候就强行回收，这样会让reader crash的。reclamation必须发生在所有的访问旧版本数据的那些reader离开临界区之后再回收，而这段等待的时间被称为grace period。

顺便说明一下，reclamation并不需要等待read3和4，因为write端的为RCU protected pointer赋值的语句是原子的，乱入的reader线程要么看到的是旧的数据，要么是新的数据。对于read3和4，它们访问的是新的共享数据，因此不会reference旧的数据，因此reclamation不需要等待read3和4离开临界区。

接口

Pasted image 20231002160900|800

Reader接口

（1）rcu_read_lock：用来标识RCU read side临界区的开始。

（2）rcu_dereference：该接口用来获取RCU protected pointer。reader要访问RCU保护的共享数据，当然要获取RCU protected pointer，然后通过该指针进行dereference的操作。

（3）rcu_read_unlock：用来标识reader离开RCU read side临界区

Writer接口

（1）rcu_assign_pointer：该接口被writer用来进行removal的操作，在witer完成新版本数据分配和更新之后，调用这个接口可以让RCU protected pointer指向RCU protected data。即publish后进入grace period 。

（2）synchronize_rcu：writer端的操作可以是同步的，也就是说，完成更新操作之后，可以调用该接口函数等待所有在旧版本数据上的reader线程离开临界区，一旦从该函数返回，说明旧的共享数据没有任何引用了，可以直接进行reclaimation的操作。

（3）call_rcu：当然，某些情况下（例如在softirq context中），writer无法阻塞，这时候可以调用call_rcu接口函数，该函数仅仅是注册了callback就直接返回了，在适当的时机会调用callback函数，完成reclaimation的操作。这样的场景其实是分开removal和reclaimation的操作在两个不同的线程中：updater和reclaimer。

一个使用的案例 - 链表节点的删除

案例来自术道经纬的一篇博文

 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


//查找
int search(long key , int *result)
{
	struct list_head *lp;
	struct el *p; 
	rcu_read_lock();//关闭CPU的可抢占性能
	list_for_each_entry_rcu(p,head,lp)
	{
		if(p->key == key)
		{
			*result = p->data ; 
			rcu_read_unlock();//打开CPU的可抢占性能
			return 1 ;
		}
	}
	rcu_read_unlock();//打开CPU的可抢占性能
	return 0 ;
}
//删除
int delete(long key)
{
	struct el *p;
	spin_lock(&listmutex);
	list_for_each_entry(p,head,lp)
	{
		if(p->key==key)
		{
			list_del_rcu(&p->list);
			spin_unlock(&listmutex);
			synchronize_rcu();
			kfree(p);
			return 1 ; 
		}
	}
	spin_unlock(&listmutex);
	return 0 ;
}

synchronize_rcu() 是关键的一步，代表writer两个阶段的转换（removal->reclamation），该调用给在synchronize之前的reader一段退出临界区的时间，被称为Grace Period（简称GP），以grace period为界，整个更新操作被划分为了"removal"和"reclamation"两个阶段，writer的角色也被对应地划分为了updater和reclaimer。removal阶段将一个节点从链表中移除，而等待所有reader解除对该节点的引用后，就进入回收/释放这个节点所占内存reclamation阶段。

Pasted image 20231002105151|800

GP 的生命周期

何时开始

前文的例子中提到，synchronize_rcu()（或者call_rcu）是GP开始，writer的操作被分为两个阶段removal和reclamation，分别作为updater和reclaimer两种角色，负责新数据的更新，和旧数据的移除。

何时结束

writer如何判断所有的reader已经退出临界区，从而移除旧数据呢？

QS

什么是QS，QS是每一个reader从退出临界区，到可以判定已经退出临界区的这段时间，被称为 Quiescent State。只有所有的reader都进入QS，writer才可以结束GP 具体的做法是：分配一个 bitmap（在 CPU 这里一般叫做cpumask），开始一个 GP 后，将 bitmap 中所有的 bits 置 1，当一个 CPU 进入 QS 后，就将自己对应的 bit 清零。所有 bits 都被置 0 后，就可以判断 GP 的结束了。

Tree RCU

因为众多reader访问bitmap，所以需要使用一个spinlock来保护，但是如果spinlock的竞争过于激烈对性能的影响不言而喻，所以采用层级化管理，某些reader被标记为leader，只有该leader的下属reader全部报告QS复位并且自己同样进入QS后，才会向自己的上级报告。这样一种树形结构，减少了锁竞争带来的性能问题。被称为Tree RCU（Linux中采用array形式组织）

Pasted image 20231002163425|800