kk Blog —— 通用基础

date [-d @int|str] [+%s|"+%F %T"]

Linux kernel 内存屏障在RCU上的应用

http://blog.csdn.net/jianchaolv/article/details/7527647

内存屏障主要解决的问题是编译器的优化和CPU的乱序执行。

编译器在优化的时候,生成的汇编指令可能和c语言程序的执行顺序不一样,在需要程序严格按照c语言顺序执行时,需要显式的告诉编译不需要优化,这在linux下是通过barrier()宏完成的,它依靠volidate关键字和memory关键字,前者告诉编译barrier()周围的指令不要被优化,后者作用是告诉编译器汇编代码会使内存里面的值更改,编译器应使用内存里的新值而非寄存器里保存的老值。

同样,CPU执行会通过乱序以提高性能。汇编里的指令不一定是按照我们看到的顺序执行的。linux中通过mb()系列宏来保证执行的顺序。简单的说,如果在程序某处插入了mb()/rmb()/wmb()宏,则宏之前的程序保证比宏之后的程序先执行,从而实现串行化。

即使是编译器生成的汇编码有序,处理器也不一定能保证有序。就算编译器生成了有序的汇编码,到了处理器那里也拿不准是不 是会按照代码顺序执行。所以就算编译器保证有序了,程序员也还是要往代码里面加内存屏障才能保证绝对访存有序,这倒不如编译器干脆不管算了,因为内存屏障 本身就是一个sequence point,加入后已经能够保证编译器也有序。

处理器虽然乱序执行,但最终会得出正确的结果,所以逻辑上讲程序员本不需要关心处理器乱序的问题。但是在SMP并发执行的情况下,处理器无法知道并发程序之间的逻辑,比如,在不同core上的读者和写者之间的逻辑。简单讲,处理器只保证在单个core上按照code中的顺序给出最终结果。这就要求程序员通过mb()/rmb()/wmb()/read_barrier_depends来告知处理器,从而得到正确的并发结果。内存屏障、数据依赖屏障都是为了处理SMP环境下的数据同步问题,UP根本不存在这个问题。

下面分析下内存屏障在RCU上的应用:

1
2
3
4
5
6
7
8
9
10
#define rcu_assign_pointer(p, v) ({ \
	smp_wmb();                      \
	(p)= (v);                       \
})

#define rcu_dereference(p) ({     \
	typeof(p)_________p1 = p;     \
	smp_read_barrier_depends();   \
	(_________p1);                \
}) 

rcu_assign_pointer()通常用于写者的发布,rcu_dereference()通常用于读者的订阅。

写者:

1
2
3
4
5
6
7
p->a = 1;
p->b = 2;
p->c = 3;
rcu_assign_pointer(gp, p);

// 如果gp的原值马上会被改变/释放,则需要synchronize_rcu()/synchronize_net(),
// 如: 模块的卸载, 原gp指向函数被释放

读者:

1
2
3
4
5
6
rcu_read_lock();
p = rcu_dereference(gp);
if (p != NULL) {
	do_something_with(p->a, p->b, p->c);
}
rcu_read_unlock();

rcu_assign_pointer()是说,先把那块内存写好,再把指针指过去。这里使用的内存写屏障是为了保证并发的读者读到数据一致性。在这条语句之前的读者读到旧的指针和旧的内存,这条语句之后的读者读到新的指针和新的内存。如果没有这条语句,很有可能出现读者读到新的指针和旧的内存。也就是说,这里通过内存屏障刷新了p所指向的内存的值,至于gp本身的值有没有更新还不确定。实际上,gp本身值的真正更新要等到并发的读者来促发。

rcu_dereference() 原语用的是数据依赖屏障,smp_read_barrier_dependence,它要求后面的读操作如果依赖前面的读操作,则前面的读操作需要首先完成。根据数据之间的依赖,要读p->a, p->b, p->c, 就必须先读p,要先读p,就必须先读p1,要先读p1,就必须先读gp。也就是说读者所在的core在进行后续的操作之前,gp必须是同步过的当前时刻的最新值。如果没有这个数据依赖屏障,有可能读者所在的core很长一段时间内一直用的是旧的gp值。所以,这里使用数据依赖屏障是为了督促写者将gp值准备好,是为了呼应写者,这个呼应的诉求是通过数据之间的依赖关系来促发的,也就是说到了非呼应不可的地步了。

下面看看kernel中常用的链表操作是如何使用这样的发布、订阅机制的:

写者:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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)
{
	new->next = next;
	new->prev = prev;
	smp_wmb();
	next->prev = new;
	prev->next = new;
}

读者:

1
2
3
4
5
#define list_for_each_entry_rcu(pos, head, member)                \
	for(pos = list_entry((head)->next, typeof(*pos), member);     \
			prefetch(rcu_dereference(pos)->member.next),          \
			&pos->member!= (head);                                \
		pos= list_entry(pos->member.next, typeof(*pos), member))

写者通过调用list_add_rcu来发布新的节点,其实是发布next->prev, prev->next这两个指针。读者通过list_for_each_entry_rcu来订阅这连个指针,我们将list_for_each_entry_rcu订阅部分简化如下:

1
2
pos = prev->next;
prefetch(rcu_dereference(pos)->next);

读者通过rcu_dereference订阅的是pos,而由于数据依赖关系,又间接订阅了prev->next指针,或者说是促发prev->next的更新。

下面介绍下其他相关链表操作的函数:

safe版本的iterate的函数?为什么就safe了?

1
2
3
4
5
6
7
#define list_for_each_safe(pos,n, head)                    \
	for(pos = (head)->next, n = pos->next; pos != (head);  \
			pos= n, n = pos->next)

#define list_for_each(pos, head)                                \
	for(pos = (head)->next; prefetch(pos->next), pos != (head); \
			pos= pos->next)

当在iterate的过程中执行删除操作的时候,比如:

1
2
list_for_each(pos,head)
	list_del(pos)

这样会断链,为了避免这种断链,增加了safe版本的iterate函数。另外,由于preftech的缘故,有可能引用一个无效的指针LIST_POISON1。这里的safe是指,为避免有些cpu的preftech的影响,干脆在iterate的过程中去掉preftech。

还有一个既有rcu+safe版本的iterative函数:

1
2
3
4
#define list_for_each_safe_rcu(pos, n, head)              \
	for(pos = (head)->next;                               \
			n= rcu_dereference(pos)->next, pos != (head); \
			pos= n)

只要用这个版本的iterate函数,就可以和多个_rcu版本的写操作(如:list_add_rcu())并发执行。