RCU(Read-Copy Update)

RCU(Read-Copy Update),对于被RCU保护的共享数据结构，读者不需要获得任何锁就可以访问它，但写者在访问它时首先拷贝一个副本，然后对副本进行修改，最后使用一个回调（callback）机制在适当的时机把指向原来数据的指针重新指向新的被修改的数据。这个时机就是所有引用该数据的CPU都退出对共享数据的操作。

RCU实际上是一种改进的rwlock，读者几乎没有什么同步开销，它不需要锁，不使用原子指令，而且在除alpha的所有架构上也不需要内存栅（Memory Barrier），因此不会导致锁竞争，内存延迟以及流水线停滞。不需要锁也使得使用更容易，因为死锁问题就不需要考虑了。写者的同步开销比较大，它需要延迟数据结构的释放，复制被修改的数据结构，它也必须使用某种锁机制同步并行的其它写者的修改操作。读者必须提供一个信号给写者以便写者能够确定数据可以被安全地释放或修改的时机。有一个专门的垃圾收集器来探测读者的信号，一旦所有的读者都已经发送信号告知它们都不在使用被RCU保护的数据结构，垃圾收集器就调用回调函数完成最后的数据释放或修改操作。 RCU与rwlock的不同之处是：它既允许多个读者同时访问被保护的数据，又允许多个读者和多个写者同时访问被保护的数据（注意：是否可以有多个写者并行访问取决于写者之间使用的同步机制），读者没有任何同步开销，而写者的同步开销则取决于使用的写者间同步机制。但RCU不能替代rwlock，因为如果写比较多时，对读者的性能提高不能弥补写者导致的损失。


读者在访问被RCU保护的共享数据期间不能被阻塞，也就说当读者在引用被RCU保护的共享数据期间，读者所在的CPU不能发生上下文切换，spinlock和rwlock都需要这样的前提。写者在访问被RCU保护的共享数据时不需要和读者竞争任何锁，只有在有多于一个写者的情况下需要获得某种锁以与其他写者同步。写者修改数据前首先拷贝一个被修改元素的副本，然后在副本上进行修改，修改完毕后它向垃圾回收器注册一个回调函数以便在所有读执行单元已经完成对临界区的访问进行修改操作。

RCU的API如下：

#define rcu_read_lock()         preempt_disable()
#define rcu_read_unlock()       preempt_enable()

例子：
struct my_stuff *stuff;
rcu_read_lock();
stuff = find_the_stuff(args...);
do_something_with(stuff);
rcu_read_unlock();

读者在读取由RCU保护的共享数据时使用rcu_read_lock()标记它进入读端临界区。
rcu_read_unlock()与rcu_read_lock配对使用，用以标记读者退出读端临界区。



#define rcu_read_lock_bh()      local_bh_disable()
#define rcu_read_unlock_bh()    local_bh_enable()

rcu_read_lock_bh()只在修改是通过 call_rcu_bh 进行的情况下使用，因为 call_rcu_bh将把 softirq 的执行完毕也认为是一个 quiescent state，因此如果修改是通过 call_rcu_bh 进行的，在进程上下文的读端临界区必须使用rcu_read_lock_bh()。

注：rcu_read_lock和rcu_read_lock_bh实质作用只是禁止内核的抢占调度。


synchronize_rcu()

在linux/kernel/rcupdate.c定义如下：
 618void synchronize_rcu(void)
 619{
 620        struct rcu_synchronize rcu;
 621
 622        init_completion(&rcu.completion);
 623        /* Will wake me after RCU finished */
 624        call_rcu(&rcu.head, wakeme_after_rcu);
 625
 626        /* Wait for it */
 627        wait_for_completion(&rcu.completion);
 628}

该函数由RCU写端调用，它将阻塞写者，直到所有读执行单元完成对临界区的访问后，写者才可以继续下一步操
作。如果有多个RCU写端调用该函数，他们将在所有读执行单元完成对临界区的访问后全部被唤醒。
需要指出的是，函数synchronize_rcu 的实现实际上使用函数call_rcu。


synchronize_sched()

 在linux/include/linux/rcupdate.h定义如下：
 270#define synchronize_sched() synchronize_rcu()

 



void fastcall call_rcu(struct rcu_head *head,
                                void (*func)(struct rcu_head *rcu))
struct rcu_head {
        struct rcu_head *next;
        void (*func)(struct rcu_head *head);
};
其中：fastcall加快访问速度.
函数call_rcu也由RCU写端调用，它不会使写者阻塞，因而可以在中断上下文或softirq使用。该函数将把函数func挂接到RCU回调函数链上，然后立即返回。一旦所有的CPU都已经完成端临界区操作，该函数将被调用来释放删除的将绝不在被应用的数据。参数head用于记录回调函数 func，一般该结构会作为被RCU保护的数据结构的一个字段，以便省去单独为该结构分配内存的操作。



void fastcall call_rcu_bh(struct rcu_head *head,
                                void (*func)(struct rcu_head *rcu))
函数call_ruc_bh功能几乎与call_rcu完全相同，唯一差别就是它把softirq的完成也当作经历一个quiescent state，因此如果写端使用了该函数，在进程上下文的读端必须使用rcu_read_lock_bh。

#define rcu_dereference(p)     ({ \
                                typeof(p) _________p1 = p; \
                                smp_read_barrier_depends(); \
                                (_________p1); \
                                })
该宏用于在RCU读端临界区获得一个RCU保护的指针，该指针可以在以后安全地引用，内存栅只在alpha架构上才使用。




RCU还增加了链表操作的RCU版本，因为对于RCU，对共享数据的操作必须保证能够被没有使用同步机制的读者看到，所以内存栅是非常必要的。

static inline void list_add_rcu(struct list_head *new, struct list_head *head)
该函数把链表项new插入到RCU保护的链表head的开头。使用内存栅保证了在引用这个新插入的链表项之前，新链表项的链接指针的修改对所有读者是可见的。


static inline void list_add_tail_rcu(struct list_head *new,
                                        struct list_head *head)
该函数类似于list_add_rcu，它将把新的链表项new添加到被RCU保护的链表的末尾。



static inline void list_del_rcu(struct list_head *entry)

在linux/include/linux/list.h定义如下：
 202static inline void list_del_rcu(struct list_head *entry)
 203{
 204        __list_del(entry->prev, entry->next);
 205        entry->prev = LIST_POISON2;
 206}

该函数从RCU保护的链表中移走指定的链表项entry，并且把entry的prev指针设置为LIST_POISON2，但是并没有把entry的next指针设置为LIST_POISON1，因为该指针可能仍然在被读者用于遍历该链表。


static inline void list_replace_rcu(struct list_head *old, struct list_head *new)
该函数是RCU新添加的函数，并不存在非RCU版本。它使用新的链表项new取代旧的链表项old，内存栅保证在引用新的链表项之前，它的链接指针的修正对所有读者可见。


list_for_each_rcu(pos, head)

/**
 * list_for_each_rcu    -       iterate over an rcu-protected list
 * @pos:        the &struct list_head to use as a loop cursor.
 * @head:       the head for your list.
 *
 * This list-traversal primitive may safely run concurrently with
 * the _rcu list-mutation primitives such as list_add_rcu()
 * as long as the traversal is guarded by rcu_read_lock().
 */
#define list_for_each_rcu(, ) \
        for ( = ()->; \
                (rcu_dereference()->),  != (); \
                 = ->)

该宏用于遍历由RCU保护的链表head，只要在读端临界区使用该函数，它就可以安全地和其它_rcu链表操作函数（如list_add_rcu）并发运行。


list_for_each_safe_rcu(pos, n, head)
该宏类似于list_for_each_rcu，但不同之处在于它允许安全地删除当前链表项pos。


list_for_each_entry_rcu(pos, head, member)

在linux/include/linux/list.h定义如下：

/**
 * list_for_each_entry_rcu      -       iterate over rcu list of given type
 * @pos:        the type * to use as a loop cursor.
 * @head:       the head for your list.
 * @member:     the name of the list_struct within the struct.
 *
 * This list-traversal primitive may safely run concurrently with
 * the _rcu list-mutation primitives such as list_add_rcu()
 * as long as the traversal is guarded by rcu_read_lock().
 */
#define list_for_each_entry_rcu(, , ) \
        for ( = (()->, (*), ); \
                (rcu_dereference()->.), \
                        &-> != (); \
                 = (->., (*), ))

其中list_entry((head)->next, typeof(*pos), member);定义为：
425#define list_entry(ptr, type, member) \
 426        container_of(ptr, type, member)

这个 container_of(ptr, type, member)宏说了很多次了，取得type数据结构的首地址。
该宏类似于list_for_each_rcu，不同之处在于它用于遍历指定类型的数据结构链表，当前链表项pos为一包含struct list_head结构的特定的数据结构。可以比较代码发现和list_for_each_rcu(pos, head)的区别。


list_for_each_continue_rcu(pos, head)
该宏用于在退出点之后继续遍历由RCU保护的链表head。


static inline void hlist_del_rcu(struct hlist_node *n)
它从由RCU保护的哈希链表中移走链表项n，并设置n的ppre指针为LIST_POISON2，但并没有设置next为LIST_POISON1,因为该指针可能被读者使用用于遍利链表。


static inline void hlist_add_head_rcu(struct hlist_node *n,
                                        struct hlist_head *h)
该函数用于把链表项n插入到被RCU保护的哈希链表的开头，但同时允许读者对该哈希链表的遍历。内存栅确保在引用新链表项之前，它的指针修正对所有读者可见。


hlist_for_each_rcu(pos, head)
该宏用于遍历由RCU保护的哈希链表head，只要在读端临界区使用该函数，它就可以安全地和其它_rcu哈希链表操作函数（如hlist_add_rcu）并发运行。


hlist_for_each_entry_rcu(tpos, pos, head, member)
类似于hlist_for_each_rcu，不同之处在于它用于遍历指定类型的数据结构哈希链表，当前链表项pos为一包含struct list_head结构的特定的数据结构。


现代产品应用：在绝大部分为读而只有极少部分为写的情况下，它是非常高效的，因此在路由表维护、系统调用审计、SELinux的AVC、dcache和IPC等代码部分中，使用它来取代rwlock来获得更高的性能。但是，它也有缺点，延后的删除或释放将占用一些内存(如：在执行写操作只能等到读操作全部执行完成，才会释放原来的数据的指针指向新的数据)，尤其是对嵌入式系统，这可能是非常昂贵的内存开销。此外，写者的开销比较大，尤其是对于那些无法容忍旧数据的情况以及不只一个写者的情况，写者需要spinlock或其他的锁机制来与其他写者同步。