RCU机制及内存优化屏障

RCU机制

Read-Copy-Update，读-拷贝-更新。

1，RCU重要的应用场景是链表，有效地提高遍历读取数据的效率，读取链表成员数据时通常只需要rcp_read_lock()，允许多个线程同时读取链表，并且允许一个线程同时修改链表。

RCU就是读-复制-更新。它是根据原理命名的。写者修改对象的流程为：首先复制生成一个副本，然后更新此副本，最后使用新对象替换旧的对象。在写者执行复制更新的时候读者可以读数据信息。（也就是写者拷贝一个备份，在这个备份上写，然后读者就在原来的读，等着都读完了，就将这个备份覆盖掉原来的）。

写者删除对象，必须等待所有访问被删除对象读者访问结束的时候，才能执行销毁操作实现。RCU优势是读者没有任何同步开销；不需要获取任何的锁，不需要执行原子命令，不需要执行内存屏障。但是写者的同步开销比较大，写者需要延迟对象的释放、复制被修改的对象，写者之间必须使用锁互斥操作方法。

RCU经常用于读者性能要求比较高的场景。RCU只能保护动态分配的数据结构，必须是通过指针访问此数据结构；受RCU保护的临界区内不能sleep;读写不对称，对写者的性能没有要求，但是读者性能要求比较高。

缺点： 写着同步开销大，写者之间需要互斥处理操作，我们在应用的时候它比较其他机制更为复杂。

A：读拷贝更新（RCU）模式添加链表项，具体内核源码如下：

/*
 * Insert a new entry between two known consecutive entries.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static inline void __list_add_rcu(struct list_head *new,
        struct list_head *prev, struct list_head *next)
{
    if (!__list_add_valid(new, prev, next))
        return;

    new->next = next;
    new->prev = prev;
    rcu_assign_pointer(list_next_rcu(prev), new);
    next->prev = new;
}

B：读拷贝更新(RCU)模式，删除链表项，具体内核源码如下：

C：读拷贝更新（RCP）模式更新链表项，内核源码如下：

在整个操作过程当中，有时要防止编译器和CPU优化代码执行的顺序。smp_wmb()保证在它之前的两行代码执行完毕之后再执行后面两行代码。

2、RCU层次架构

RCU根据CPU数量的大小按照属性结构来组成其层次结构，称为RCU Hierarchy，具体内核源码分析如下：

/*
 * Define shape of hierarchy based on NR_CPUS, CONFIG_RCU_FANOUT, and
 * CONFIG_RCU_FANOUT_LEAF.
 * In theory, it should be possible to add more levels straightforwardly.
 * In practice, this did work well going from three levels to four.
 * Of course, your mileage may vary.
 */

#ifdef CONFIG_RCU_FANOUT
#define RCU_FANOUT CONFIG_RCU_FANOUT
#else /* #ifdef CONFIG_RCU_FANOUT */
# ifdef CONFIG_64BIT
# define RCU_FANOUT 64
# else
# define RCU_FANOUT 32
# endif
#endif /* #else #ifdef CONFIG_RCU_FANOUT */

#ifdef CONFIG_RCU_FANOUT_LEAF
#define RCU_FANOUT_LEAF CONFIG_RCU_FANOUT_LEAF
#else /* #ifdef CONFIG_RCU_FANOUT_LEAF */
#define RCU_FANOUT_LEAF 16
#endif /* #else #ifdef CONFIG_RCU_FANOUT_LEAF */

#define RCU_FANOUT_1          (RCU_FANOUT_LEAF)
#define RCU_FANOUT_2          (RCU_FANOUT_1 * RCU_FANOUT)
#define RCU_FANOUT_3          (RCU_FANOUT_2 * RCU_FANOUT)
#define RCU_FANOUT_4          (RCU_FANOUT_3 * RCU_FANOUT)

RCU层次结构更具CPU数量决定，内核中有宏帮忙构建RCU层次架构，其中CONFIG_RCU_FANOUT_LEAF表示一个子叶子的CPU数量，CONFIG_RCU_FANOUT表示每个层数最多支持多少个叶子数量。

二、优化内存屏障

在编译时，指令一般不按照源程序顺序执行，原因是为提高程序执行性能，会对它进行优化，主要分为两种：编译器优化和CPU执行优化。

优化屏障避免编译的重新排序优化，保证编译程序时在优化屏障之前的指令不会在优化屏障之后执行。

1、编译器优化：为提高系统性能，编译器在不影响逻辑的情况下会调整指令的执行顺序。

2、CPU执行优化：为提高流水线的性能，CPU的乱序执行可能会让后面的寄存器冲突的汇编指令先于前面指令完成。

内存屏障

内存屏障，是一类同步屏障指令，是编译器或CPU对内存访问操作的时候，严格按照一定顺序来执行，也就是memory barrier之前的指令和memory barrier之后的指令不会由于系统优化等原因而导致乱序。

是一种保证内存访问顺序的方法，解决内存访问乱序问题：

A、编译器编译代码的时候可能重新排序汇编指令，使编译出来的程序在处理器上执行速度更能快，但是有的时候优化的结果不符合软件开发工程师的意图。

B、新式CPU采用超标量体系结构和乱序执行技术，能够在一个时钟周期并行执行多条指令。一句话总结为：顺序取指令，乱序执行，顺序提交执行结果。

C、多处理器系统当中，硬件工程师使用存储缓冲区，使无效队列协助缓存和缓存一致性协议实现高效性能，引入处理器之间的内存访问乱序问题。

假设使用禁止内核抢占方法保护临界区：

preempt_enable()

临界区

preempt_enable()

后面两种是不正确的，但是编译器会使指令乱序，导致出现问题。

临界区

preempt_enable()

preempt_enable()

preempt_enable()

preempt_enable()

临界区

为了能够组织编译器错误重排指令，在禁止内核抢占和开启内核抢占的里面添加编译器优先屏障，具体如下：

GCC编译器定义的宏

关键字为__volatile__告诉编译器：禁止优化代码，不需要改变barrier()前面的代码块、barrier()和后面的代码块这三个代码块的顺序。

处理器内存屏障

处理器内存屏障是解决CPU之间的内存访问乱序问题和处理器访问外围设备的乱序问题。

除数据依赖屏障之外，所有处理器内存屏障隐含编译器优化屏障。