RCU
RCU (ready-copy-update) 是读-拷贝-更新,是linux内核中重要的同步机制,Linux内核已有原子操作,读写信号量等锁机制
- RCU 重要的应用场景是链表,有效地提高遍历读取数据的效率,读取链表成员时候,通常只需要rcu_read_lock(),允许多个线程同时读取链表,并且允许一个线程同时修改链表。
- RCU 的意思是读复制更新,它是根据原理命名,写者修改对象的流程为:首先复制生成一个副本,然后更新此副本,最后使用新对象替换旧的对象。
- 在写者执行复制更新的时候,读者可以读数据信息
写者删除对象,必须等待所有访问被删除对象读者访问结束的时候,才能够执行销毁操作实现。 优势在于 任何同步开销:不需要获取任何的所,不需要执行原子指令,不需要执行内存屏障, 写者同步开销比较大,写者需要延迟对象的释放,复制被修改的对象,写者之间必须使用锁互斥操作方法。 有时候称为互斥锁的替代,目标最大程度减小读写开销,经常用于读者性能要求比较高的场景。只能保护动态分配的数据结构,必须是通过指针访问此数据结构 写者之间需要互斥处理操作,我们在应用的时候比较其他机制更为复杂, 受到RCU保护的临界区不能sleep,读写不对称,对写者的性能没有要求,但是读者性能要求比较高。
RCU 机制
在RCU机制所有指向共享数据的指针的使用者,当要修改该共享数据时,首先创建一个副本,正在副本中修改, 所有读访问线程都离开读临界区之后,指针指向新的修改后副本的指针,并且删除旧数据。
链表操作
- RCU 能保护的不仅是一般的指针,linux 内核提供标准函数,使得能通过RCU机制保护双链表,这是RCU机制在linux内核内部最重要的应用。
- 有关通过RCU保护的链表,优点是仍然可以使用标准的链表元素,只有在遍历链表,修改和删除链表元素时候,必须调用标准函数的RCU变体。
读拷贝跟新( RCU) 模式添加链表项,具体内核源码分析如下:
static inline void list_add_rcu(struct list_head *new, struct list_head *head)
{
__list_add_rcu(new,head,head->next);
}
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;
}
读拷贝更新(RCU) 模式删除链表项,具体内核源码分析如下:
static inline void list_del_rcu(struct list_head *entry)
{
__list_del_entry(entry);
entry->prev = LIST_POSION2;
}
static inline void __list_del_entry(struct list_head *entry)
{
if(!__list_del_entry_valid(entry))
return;
__list_del(entry->prev,entry->next);
}
static inline void list_del(struct list_head *entry)
{
__list_del_entry(entry);
entry->next = LIST_POISON1;
entry->prev = LIST_POISION2;
}
读拷贝更新(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;
}
在整个操作过程中,有时要防止编译器和CPU 优化代码执行的顺序,smp_wmb()保证在它之前的两行代码执行完毕之后再执行后两行。
RCU 层次架构
rcu 根据CPU数量的大小按照树形结构来组成层次结构,称为RCU Hierarchy,具体内核源码如下:
#ifdef CONFIG_RCU_FANOUT
#define RCU_FANOUT_CONFIG_RCU_FANOUT
#else
#ifdef CONFIG_64BIT
#define RCU_FANOUT 64
#else
#define RCU_FANOUT 32
#endif
#endif
#ifdef CONFIG_RCU_FANOUT_LEAF
#define RCU_FANOUT_LEAF CONFIG_RCU_FANOUT_LEAF
#else
#define RCU_FANOUT_LEAF 16
#endif
#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 执行优化。优化屏障避免编译的重新排序优化操作,保证编译程序时在优化屏障之前的指令不会在优化屏障之后执行。 linux 使用宏barrier 实现优化屏障,如GCC 编译器的优化屏障宏定义,具体查询linux内核源码如下
#define barrier() __asm__ __volatile__("": : :"memory");
- 编译器优化:为提高系统性能,编译器在不影响逻辑的情况下会调整指令的执行顺序。
- CPU 执行优化:为提高流水线的性能,CPU的乱序执行可能会让后面的寄存器冲突的汇率指令先于前面指令完成。
内存屏障
内存屏障,也称内存栅障或屏障指令等,是一类同步屏障指令,是编译器或cpu对内存访问操作的时候,严格按照一定顺序来执行,也 就是memory barrier 之前的指令和memory barrier 之后的指令不会由于系统优化等原因而导致乱序。
Linux 内核支持3种内存屏障:编译器屏障,处理器内存屏障,【内存映射I/O写屏障(Memory Mapping I/O,MMIO。此屏障已经废弃新驱动不应该使】
保证内存访问顺序的方法,解决内存访问乱序问题: 编译器编译代码时候可能重新排序汇编指令,使编译出来的程序在处理器上执行速度更快,但是有时候优化结果可能不符合软件开发工程师意图。 新式处理器采用超标量体系结构和乱序执行技术,能够在一个时钟周期并行执行多条指令。一句话总结:顺序取指令,乱序执行,顺序提交执行结果。 多处理系统当中,硬件工程师使用存储缓冲区,使用无锁队列缓写存和缓存一致性协议实现高效性能,引入处理器之间的内存访问乱序问题。
假设使用机制内核抢占方法保护临界区:
preempt_disable();
临界区:
preempt_enable();
临界区
preempt_disable();
preempt_enable();
preempt_disbale();
preempt_enable();
临界区
后面两种是错误的,只有第一个是对的。为了阻止编译器错误重排指令,在禁止内核抢占和开启内核抢占的里面添加编译器优先屏障
#define preempt_disable() \
do {\
preempt_count_inc();\
barrier();\
} while(0)
#ifdef CONFIG_PREEMPTION
#define preempt_enable() \
do {\
barrier(); \
if (unlikely(preempt_count_dec_and_test())) \
__preempt_schedule();
} while(0)
GCC编译器定义的宏
#define barrier() __asm__ __volatile__("": : :"memory");
关键字为__volatile__告诉编译器禁止优化代码块,不需要改变barrier()前面的代码块,barrier()和后面的代码块这3个代码块的顺序。
处理器内存屏障
处理器内存屏障解决cpu之间的内存访问乱序问题和处理器访问外围设备的乱序问题。linux 中有8种处理器屏障。
- 内存屏障类型: 通用内存屏障 写内存屏障 读内存屏障 数据依赖屏障
- 强制性内存屏障: mb() vmb() rmb() read_barrier_depends()
- SMP内存屏障: smp_mb() smp_vmb() smp_rmb() smp_read_barrier_depends()
除了数据依赖屏障之外,所有处理器内存屏障隐含编译器优化屏障。