RCU基础

什么是RCU?

什么是RCU?是Read,Copy-Update的缩写,意指读-复制更新。是一种同步机制。

典型的RCU更新时序如下:

  • a. 删除指向数据结构的指针,以便后续读者无法获得对它的引用;
  • b. 等待,所有以前的读者完成RCU读端操作;
  • c. 回收,当没有任何持有此数据结构引用的读者时,安全地回收数据结构(例如,kfree () d)。

关键思想:延迟销毁。等待所有读者完成,允许RCU的读者使用轻量级的同步,在某些情况下甚至没有任何同步机制。
相比之下,在更传统基于锁的方案中,读者必须使用重量同步机制,才能防止更新程序正在引用的数据结构。
这是因为基于锁的更新者通常更新数据项,因此必须排除读者。相反,基于rcu的更新者利用写入单一对齐指针在现代cpu中是原子操作,允许原子插入、删除、以及在不中断读者的情况下替换链接结构中的数据项
并发的RCU读者可以继续访问旧版本,并可以免除在SMP计算机系统中昂贵的操作,如锁,原子操作,内存障碍,通信缓存丢失等。

在上面显示的三步过程中,更新者执行移除和回收步骤,但通常会使用完全不同的一个线程来做回收
实际上,在Linux内核的目录条目缓存(directory-entry cache, dcache)中采用这种方法。
即使同一线程执行更新(步骤(a))和回收(步骤(c))操作,分开考虑通常也是有帮助的。例如,RCU读取者和更新者根本不需要通信,但是RCU读者与回收者之间提供了隐式的低开销通信,即上文的步骤(b)。

RCU特性总结如下:
1. RCU使用在读者多而写者少的情况。RCU和读写锁相似.但RCU的读者占锁没有任何的系统开销。写者与写者之间必须要保持同步,且写者必须要等它之前的读者全部都退出之后才能释放之前的资源。
2. RCU保护的是指针.这一点尤其重要.因为指针赋值是一条单指令.也就是说是一个原子操作.因它更改指针指向没必要考虑它的同步.只需要考虑cache的影响.
3. 读者是可以嵌套的.也就是说rcu_read_lock()可以嵌套调用.
4. 读者在持有rcu_read_lock()的时候,不能发生进程上下文切换.否则,因为写者需要要等待读者完成,写者进程也会一直被阻塞.

那么,如果读者没有执行任何类型的同步操作,reclaimer怎么能知道读取者什么时候完成呢?

RCU核心API

核心的RCU API非常的少,如下:

rcu_read_lock()
rcu_read_unlock()
synchronize_rcu()/call_rcu()
rcu_assign_pointer()
rcu_dereference()

RCU API还有许多其他成员,但是其余的可以用这五种来表示。

rcu_read_lock()

原型:void rcu_read_lock(void);

读取者使用,用于通知回收者读取者进入了RCU的读端临界区。
虽然使用CONFIG_PREEMPT_RCU构建的内核可以抢占RCU读侧临界区,但是在RCU读侧临界区阻塞是非法的
在RCU读端临界区访问的任何受RCU保护的数据结构都会保证在临界区期间保持未回收状态。
另外,引用计数可以与RCU一起使用,以维护对数据结构的长期引用。

在Linux普通的TREE RCU实现中,rcu_read_lock和rcu_read_unlock的实现非常简单,分别是关闭抢占和打开抢占:

static inline void __rcu_read_lock(void)
{
    preempt_disable();
}

static inline void __rcu_read_unlock(void)
{
    preempt_enable();
}

rcu_read_unlock()

原型:void rcu_read_unlock(void);

读取者使用,用于通知回收者其退出了读端临界区。
注意:RCU的读端临界区可能被嵌套或重叠。

synchronize_rcu()

原型:void synchronize_rcu(void);

此函数的关键思想:等待。

使用synchronize_rcu()确保读者完成对旧结构体的操作后释放旧结构体。

用于标志“更新者代码的结束”和“回收者代码的开始”。
它通过阻塞来做到这一点,直到所有cpu上所有预先存在的RCU读端临界区都完成。

注意:synchronize_rcu()不一定要等待任何后续的RCU读端临界区完成。例如,考虑以下事件序列:

         CPU 0                     CPU 1                  CPU 2
         ----------------- ------------------------- ---------------
     1.  rcu_read_lock()
     2.                    enters synchronize_rcu()
     3.                                               rcu_read_lock()
     4.  rcu_read_unlock()
     5.                    exits synchronize_rcu()
     6.                                              rcu_read_unlock()

需要重申的是,synchronize_rcu()只需要等待调用它之前的读端临界区完成,不需要等待调用它之后开始的读取者完成。

当然,synchronize_rcu()不需要立刻返回,

当然,synchronize_rcu()不一定在最后一个预先存在的RCU读端临界区完成之后立即返回。
首先,具体实现中可能会有延时调度。另外,为了提高效率,许多RCU实现批量处理请求,这可能会进一步延迟synchronize_rcu()。

因为synchronize_rcu() API必须发现读取者完成的时间,因此其是RCU实现的关键。
另外,要使RCU在除了最需要读的情况之外的所有情况下都有用,synchronize_rcu()的开销也必须非常小。

call_rcu() API是syncnize_rcu()的回调形式,在后面的部分中有更详细的描述。
它注册而不是阻塞,而是注册一个函数和自变量,这些函数和自变量在所有正在进行的RCU读取侧关键部分均已完成之后被调用。
在禁止非法访问或更新端性能要求比较高时,此回调变体特别有用。

但是,不应轻易使用call_rcu() API,因为对syncnize_rcu() API的使用通常会使代码更简单。
此外,synchronize_rcu() API具有不错的属性,可以在宽限期被延迟时自动限制更新速率。
面对拒绝服务攻击,此属性导致系统具有弹性。 使用call_rcu()的代码应限制更新速率,以获得相同的弹性。 有关限制更新速率的一些方法,请参见checklist.txt。

如何判断所有读者都退出调用synchronize_rcu之前的读临界区?

以Linux中的tree rcu实现为例,其rcu_read_lock()会关闭抢占,rcu_read_unlock()打开抢占,
synchronize_rcu是否度过宽限期的判断就比较简单:每个CPU都经过一次抢占。因为发生抢占,就说明不在rcu_read_lock和rcu_read_unlock之间,必然已经完成访问或者还未开始访问。

每个CPU度过quiescnet state

接下来我们看每个CPU上报完成抢占的过程。kernel把这个完成抢占的状态称为quiescent state。每个CPU在时钟中断的处理函数中,都会判断当前CPU是否度过quiescent state。

void update_process_times(int user_tick)
{
...
    rcu_check_callbacks(cpu, user_tick);
...
}

void rcu_check_callbacks(int cpu, int user)
{
...
    if (user || rcu_is_cpu_rrupt_from_idle()) {
        /*在用户态上下文,或者idle上下文,说明已经发生过抢占*/
        rcu_sched_qs(cpu);
        rcu_bh_qs(cpu);
    } else if (!in_softirq()) {
        /*仅仅针对使用rcu_read_lock_bh类型的rcu,不在softirq,
         *说明已经不在read_lock关键区域*/
        rcu_bh_qs(cpu);
    }
    rcu_preempt_check_callbacks(cpu);
    if (rcu_pending(cpu))
        invoke_rcu_core();
...
}

每个CPU度过quiescent state之后,需要向上汇报直至所有CPU完成quiescent state,从而标识宽限期的完成,这个汇报过程在软中断RCU_SOFTIRQ中完成。汇报过程是树状的,也就是“Tree RCU”这个名字得来的缘由。

所有宽限期的发起和完成都是由同一个内核线程rcu_gp_kthread来完成。

  • 通过判断rsp->gp_flags & RCU_GP_FLAG_INIT来决定是否发起一个gp;
  • 通过判断! (rnp->qsmask) && !rcu_preempt_blocked_readers_cgp(rnp))来决定是否结束一个gp。

发起一个GP时,rsp->gpnum++;结束一个GP时,rsp->completed = rsp->gpnum。

rcu_assign_pointer()

原型: void rcu_assign_pointer(p, typeof(p) v);

rcu_assign_pointer()通过宏实现。将新指针赋给RCU结构体,赋值前的读者看到的还是旧的指针。

更新者使用这个函数为受rcu保护的指针分配一个新值,以便安全地将更新的值更改传递给读者。
此宏不计算rvalue,但它执行某CPU体系结构所需的内存屏障指令。保证内存屏障前的指令一定会先于内存屏障后的指令被执行。

它用于记录(1)哪些指针受RCU保护以及(2)给定结构可供其他CPU访问的点。
rcu_assign_pointer()最常通过_rcu列表操作原语(例如list_add_rcu())间接使用。

rcu_dereference()

原型: typeof(p) rcu_dereference(p);

rcu_assign_pointer()类似,rcu_dereference()也必须通过宏实现

读者通过rcu_dereference()获取受保护的RCU指针,该指针返回一个可以安全解除引用的值
请注意,rcu_dereference()实际上并未取消对指针的引用,相反,它保护指针供以后取消引用
它还针对给定的CPU体系结构执行任何所需的内存屏障指令。 当前,只有Alpha CPU架构才需要rcu_dereference()中的内存屏障-在其他CPU上,它编译为无内容,甚至编译器指令也没有。

常见的编码实践是使用rcu_dereference() 将一个受rcu保护的指针复制到一个局部变量,然后解引用这个局部变量,例如:

    p = rcu_dereference(head.next);
    return p->data;

然而,上述情况可以整合成如下一句:

    return rcu_dereference(head.next)->data;

如果您要从受rcu保护的结构中获取多个字段,那么使用局部变量当然是首选的。重复的rcu_dereference()调用看起来很糟糕,不能保证在关键部分发生更新时返回相同的指针,并且会在Alpha cpu上产生不必要的开销。

注意rcu_dereference()返回的值仅在封闭的RCU读端临界区[1]内有效
例如,以下内容是不合法的:

    rcu_read_lock();
    p = rcu_dereference(head.next);
    rcu_read_unlock();
    x = p->address;  /* BUG!!! */
    rcu_read_lock();
    y = p->data;  /* BUG!!! */
    rcu_read_unlock();

将一个RCU读临界区获得的引用保留到另一个是非法的;同事,将一个锁定的临界区的引用放在另一个中使用也是非法的。

rcu_assign_pointer()一样,rcu_dereference()的重要功能是记录哪些指针受RCU保护,尤其是标记一个随时可能更改的指针,包括紧随rcu_dereference()之后。
通常通过_rcu列表操作基元(例如list_for_each_entry_rcu())间接使用rcu_dereference()

变量rcu_dereference_protected()可以在RCU读取临界区外使用,只要使用情况受到更新者代码获取的锁的保护即可。

下图展示了不同角色之间的通信。

        rcu_assign_pointer()
                                +--------+
        +---------------------->| 读者   |---------+
        |                       +--------+         |
        |                           |              |
        |                           |              | Protect:
        |                           |              | rcu_read_lock()
        |                           |              | rcu_read_unlock()
        |        rcu_dereference()  |              |
        +---------+                 |              |
        | 更新者  |<----------------+              |
        +---------+                                V
        |                                    +-----------+
        +----------------------------------->| 回收者    |
                                             +-----------+
          推迟、等待:
          synchronize_rcu() & call_rcu()

RCU基础结构会观察rcu_read_lock(),rcu_read_unlock(),synchronize_rcu() 和call_rcu() 调用的时间顺序,以确定何时(1)syncnize_rcu()调用何时可以返回,以及(2)call_rcu() 回调可以被调用。
RCU基础结构的有效实现大量使用批处理,以便在相应API的许多使用上分摊其开销。

在Linux内核中至少有三种RCU用法。上图显示了最常见的一种。在更新端,rcu_assign_pointer()、sychronize_rcu()和call_rcu()这三种基本类型使用的原语是相同的。但是为了保护(在读端),使用的原语根据不同的口味而有所不同:

a.
rcu_read_lock() / rcu_read_unlock() 
rcu_dereference()

b.
rcu_read_lock_bh() / rcu_read_unlock_bh() 
local_bh_disable() / local_bh_enable() 
rcu_dereference_bh()

c.
rcu_read_lock_sched() / rcu_read_unlock_sched() 
preempt_disable() / preempt_enable() 
local_irq_save() / local_irq_restore()
hardirq enter / hardirq exit 
NMI enter / NMI exit 
rcu_dereference_sched()

上述三种类型的使用方法如下:

  • a. RCU应用于普通的数据结构。
  • b. RCU应用于可能遭受远程拒绝服务攻击的网络数据结构。
  • c. RCU应用于调度器和中断/ nmi处理器任务。

同样,大多数用途是(a)。 (b)和(c)情况对于专门用途很重要,但相对较少见。

核心API使用示例

本节展示如何简单使用核心RCU API来保护指向动态分配结构的全局指针。
更多的典型用法在 listRCU.txt , arrayRCU.txt , NMI-RCU.txt中被使用。

struct foo {
    int a;
    char b;
    long c;
};

DEFINE_SPINLOCK(foo_mutex); // 定义spin锁

struct foo __rcu *gbl_foo;  // 声明一个受保护的指针

/*
 * Create a new struct foo that is the same as the one currently 
 * pointed to by gbl_foo, except that field "a" is replaced 
 * with "new_a". Points gbl_foo to the new structure, and 
 * frees up the old structure after a grace period. 
 * 
 * Uses rcu_assign_pointer() to ensure that concurrent readers 
 * see the initialized version of the new structure. 
 * 
 * Uses synchronize_rcu() to ensure that any readers that might
 * have references to the old structure complete before freeing 
 * the old structure. 
 */
void foo_update_a(int new_a) 
{
    struct foo *new_fp; 
    struct foo *old_fp;
    new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
    spin_lock(&foo_mutex);  // 更新操作上锁
    old_fp = rcu_dereference_protected(gbl_foo, lockdep_is_held(&foo_mutex)); 
    *new_fp = *old_fp; 
    new_fp->a = new_a;
    rcu_assign_pointer(gbl_foo, new_fp);  // 确保并行的读者看到新结构的旧版本
    spin_unlock(&foo_mutex); 
    synchronize_rcu();  // 确保所有引用旧的数据结构的读者在释放旧数据结构之前都已经完成操作,退出了临界区
    kfree(old_fp);
} 

/*
 * Return the value of field "a" of the current gbl_foo 
 * structure. Use rcu_read_lock() and rcu_read_unlock() 
 * to ensure that the structure does not get deleted out 
 * from under us, and use rcu_dereference() to ensure that 
 * we see the initialized version of the structure (important 
 * for DEC Alpha and for people reading the code).
 */
int foo_get_a(void) {
    int retval; 
    rcu_read_lock();
    retval = rcu_dereference(gbl_foo)->a; 
    rcu_read_unlock(); 
    return retval;
}

总结如下:

  • 使用 rcu_read_lock()rcu_read_unlock() 保证其处于读端临界区;
  • 在读端临界区内,使用 rcu_dereference() 解引用受RCU保护的指针
  • 使用一些可靠的方案保证并行更新操作不会互相干扰,如锁或者向量
  • 使用rcu_assign_pointer()更新受rcu保护的指针。这个原语保护并发读不受更新操作(而不是并发更新)的影响!但是,仍然需要使用锁(或类似的东西)来防止并发rcu_assign_pointer()原语相互干扰。
  • 使用synchronize_rcu() 在从受RCU保护的数据结构中删除一个数据元素之后,但是在回收/释放数据元素之前,为了等待所有可能正在引用那个数据项的RCU读端临界区完成。

无阻塞更新call_rcu()

在上面的例子中,foo_update_a()阻塞直到一个宽限期结束。这很简单,但在某些情况下,人们不能等这么久——可能还有其他高优先级的工作要做。
在这种情况下,使用call_rcu()而不是synchronize_rcu()call_rcu() API如下:

void call_rcu(struct rcu_head * head, void (*func)(struct rcu_head *head));

此函数在宽限期过后调用func(heda)。此调用可能发生在softirq或进程上下文中,因此不允许阻止该函数。foo结构需要添加一个rcu-head结构,可能如下所示:

struct foo {
    int a;
    char b; 
    long c;
    struct rcu_head rcu; 
 };

foo_update_a()函数示例如下:

/*
* Create a new struct foo that is the same as the one currently
* * pointed to by gbl_foo, except that field "a" is replaced 
* * with "new_a". Points gbl_foo to the new structure, and 
* * frees up the old structure after a grace period. *
* Uses rcu_assign_pointer() to ensure that concurrent readers 
* * see the initialized version of the new structure.
* * Uses call_rcu() to ensure that any readers that might have
* * references to the old structure complete before freeing the * old structure.
* */
void foo_update_a(int new_a) {
    struct foo *new_fp; 
    struct foo *old_fp;
    new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL); 
    spin_lock(&foo_mutex);
    old_fp = rcu_dereference_protected(gbl_foo, lockdep_is_held(&foo_mutex)); 
    *new_fp = *old_fp; 
    new_fp->a = new_a;
    rcu_assign_pointer(gbl_foo, new_fp); 
    spin_unlock(&foo_mutex);
    call_rcu(&old_fp->rcu, foo_reclaim); 
} 

// The foo_reclaim() function might appear as follows:
void foo_reclaim(struct rcu_head *rp) {
    struct foo *fp = container_of(rp, struct foo, rcu); 
    foo_cleanup(fp->a); 
    kfree(fp);
}

container_of() 原语是一个宏,给定指向结构的指针,结构的类型以及结构内的指向字段,该宏将返回指向结构开头的指针。

使用 call_rcu() 可使 foo_update_a() 的调用方立即重新获得控制权,而不必担心新近更新的元素的旧版本。 它还清楚地显示了更新程序 foo_update_a()和回收程序 foo_reclai() 之间的RCU区别。

总结:

  • 在从受RCU保护的数据结构中删除数据元素之后,请使用call_rcu()-以注册一个回调函数,该函数将在所有可能引用该数据项的RCU读取侧完成后调用。
  • 如果call_rcu()的回调除了在结构上调用kfree()之外没有做其他事情,则可以使用kfree_rcu()代替call_rcu()来避免编写自己的回调:kfree_rcu(old_fp,rcu)

RCU简单实现

RCU的优点之一是它具有极其简单的“Toy(玩具)”实现,这是理解Linux内核中生产质量实现的良好第一步。
本节介绍两种这样的RCU“玩具”实现,一种是按照熟悉的锁(locking)原语实现的,另一种更类似于“经典” RCU。 两者对于现实世界的使用都太简单了,缺乏功能和性能。 但是,它们对于了解RCU的工作方式很有用。

有关生产质量的实现,请参见kernel / rcu / update.c,

基于锁的Toy实现

本节介绍基于熟悉的锁定原语的“玩具” RCU实现。 它的开销使其无法用于现实生活,缺乏可伸缩性。
它也不适合实时使用,因为它允许调度等待时间以从一个读取临界区“泄漏”到另一个。 它还假定递归读写器锁:如果使用非递归锁尝试此操作,并且允许嵌套的rcu_read_lock()调用,则可能会死锁。

static DEFINE_RWLOCK(rcu_gp_mutex);

void rcu_read_lock(void) {
    read_lock(&rcu_gp_mutex); 
}


void rcu_read_unlock(void) {
     read_unlock(&rcu_gp_mutex);
}


void synchronize_rcu(void) {
     write_lock(&rcu_gp_mutex); 
     smp_mb__after_spinlock();
     write_unlock(&rcu_gp_mutex);
}

rcu_read_lock()和rcu_read_unlock()原语读取并获取并释放全局读写器锁。 syncnize_rcu()原语写获取该相同的锁,然后释放它。这意味着一旦syncnize_rcu()退出,就可以保证在调用syncnize_rcu()之前进行中的所有RCU读取侧关键部分都已完成-无法通过syncnize_rcu()进行写获取。否则锁定。 smp_mb__after_spinlock()提升了syncnize_rcu()到完整的内存屏障,符合以下所列的“内存屏障保证”:
Documentation / RCU / Design / Requirements / Requirements.html。
可以嵌套rcu_read_lock(),因为可以递归获取读写器锁。还要注意,rcu_read_lock()不受死锁(RCU的重要属性)的影响。这样做的原因是,唯一可以阻止rcu_read_lock()的东西是syncnize_rcu()。但是syncnize_rcu()在持有rcu_gp_mutex时不会获取任何锁,因此不会有死锁周期。
快速测验1:为什么这种说法幼稚?在实际的Linux内核中使用此算法时,怎么会发生死锁?如何避免这种僵局?

linux内核 rcu机制

#define __rcu_assign_pointer(p, v, space) \
    ({ \
        smp_wmb(); \
        (p) = (typeof(*v) __force space *)(v); \
    })

内存屏障前边的指令一定会先于内存屏障后边的指令被执行。这就保证了被加入到链表中的项,一定是已经完成了初始化的。

RCU(Read-Copy Update),是 Linux 中比较重要的一种同步机制。顾名思义就是“读,拷贝更新”,再直白点是“随意读,但更新数据的时候,需要先复制一份副本,在副本上完成修改,再一次性地替换旧数据”。这是 Linux 内核实现的一种针对“读多写少”的共享数据的同步机制。

在kernel中,rcu有tiny rcu和tree rcu两种实现,tiny rcu更加简洁,通常用在小型嵌入式系统中,tree rcu则被广泛使用在了server, desktop以及android系统中。

add操作

#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 等)进行保护。

遍历与lookup操作

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

delete操作

知道了前边说的 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() 就会保证读端临界区结束时才会真正释放链表项的内存,而不会释放读者正在访问的链表项。

update 操作

RCU 的更新机制是 :拷贝更新,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() 用新节点替换掉旧节点,最后释放旧节点内存。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;
}

FAQs

rcu_dereference() vs rcu_dereference_protected()?

简而言之:

  • rcu_dereference()应该在阅读方使用,受rcu_read_lock()保护。
  • rcu_dereference_protected()应该由单个写者在在写入侧(更新侧)使用,或者由锁定保护,这会阻止多个写入器同时修改解除引用的指针.在这种情况下,指针不能在当前线程之外进行修改,因此既不需要编译器也不需要cpu-barrier.

使用rcu_dereference总是安全的,并且其性能损失(与之相比rcu_dereference_protected)很低.

精确描述了rcu_dereference_protected在内核4.6:

/**
 * rcu_dereference_protected() - fetch RCU pointer when updates prevented
 * @p: The pointer to read, prior to dereferencing
 * @c: The conditions under which the dereference will take place
 *
 * Return the value of the specified RCU-protected pointer, but omit
 * both the smp_read_barrier_depends() and the READ_ONCE().  This
 * is useful in cases where update-side locks prevent the value of the
 * pointer from changing.  Please note that this primitive does -not-
 * prevent the compiler from repeating this reference or combining it
 * with other references, so it should not be used without protection
 * of appropriate locks.
 *
 * This function is only for update-side use.  Using this function
 * when protected only by rcu_read_lock() will result in infrequent
 * but very ugly failures.
 */

原文链接

参考

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.
永久连接: http://www.nfvschool.cn/?p=767
标签:

发表评论