泰晓科技 -- 聚焦 Linux - 追本溯源,见微知著!
网站地址:https://tinylab.org

儿童Linux系统,可打字编程学数理化
请稍侯

Memory Ordering(内存序):memory-barrier.txt

Chen Jie 创作于 2017/02/14

By Chen Jie of TinyLab.org 2017-02-14 00:25:17

前言:

前篇就内存序问题由来、同步机制中内存序指令的应用,以及 C/C++ 原子操作相关的内存序做了介绍。其中,编译器和硬件优化只关注结果,而多方协同中却需要关注过程细节,这个矛盾,需内存序指令来调和。另一方面,原子操作,为多方协作排了先后顺序,在此基础上,有些内存序指令可进一步确保临界区访问不重叠(在各方看来),比如 Load-acquire/Store-release。

Documentation/memory-barrier.txt 介绍了 Linux 内核中的内存序实现,相较更为复杂。本文试图从一个新视角,试图一目了然。

Again,本文链接的代码如体系架构相关,选 ARMv8 示例。首先交待下背景。

内存序最小假定

Linux 对于 CPU 内存序,做了如下最小假定:

  • 在任何 CPU 中,前后依赖的访存,CPU 按照指令流来发指令。留意这个假定需对 DEC Alpha 作额外步骤,即通过smp_read_barrier_depends()来清空变量旧缓存:

Q = READ_ONCE(P);
smp_read_barrier_depends(); /* 清空 *Q 在 cache 中的缓存,
                             * 防止读到过时数据,Alpha only */;
D = READ_ONCE(*Q);

// CPU 执行指令顺序:Q = LOAD P, D = LOAD *Q
  • 对于某个 CPU,前后两条访存指令,其一读,另一写,且读和写的区域存在重叠,则该 CPU 严格按指令流序来发指令。

a = READ_ONCE(*X); WRITE_ONCE(*X, b);

// CPU 执行指令顺序:LOAD *X, STORE *X = b

WRITE_ONCE(*X, c); d = READ_ONCE(*X);

// CPU 执行指令顺序:STORE *X = c, d = LOAD *X


但,上述假定有如下例外:

  • 对“位域”(bitfields,类似结构体中“int b1:1;int b2:1;”这样的定义)无效,因编译器很可能产生非原子的 RMW(read-modify-write)代码来操作位域。因此,别拿位域来做并行算法中的同步标记。另一方面,请使用同一把锁,保护 全部位域;若手贱用俩锁来保护邻近两组位,则更新其中一组很可能影响另一组。

  • 上述假定中,假定访存目标是 自然对齐的自然尺寸。比如访存目标尺寸为双字节(short、unsigned short),则要求地址也是双字节对齐。

上述最小假定是为了维持因果性,即指令流中先后俩指令,均对后面某结果有贡献,则其顺序不能改变。这个贡献可能是链式传播的,即一环扣一环(“假定 1”);或是均有贡献(“假定 2”)

“假定 1”谈论的是 Data dependencies;与之相对的是 Control dependencies,即指令流中先前指令,决定了指令流路径,从而间接影响指令流路径上的每个结果。

Control dependencies

通过一组例子来看下实践中 Control dependencies 的注意事项:

  • 例1:
    1. READ_ONCE —— 防止编译器合并 a、b 装载;或编译器 “认为 a == 0”,而且剥离掉整个 “if” 语句!
    2. smb_rmb() —— 防止 CPU 在乱序执行时,通过分支预测,使得 读取 b 发生于 读取 a 之前

q = READ_ONCE(a);
if (q) {
	smp_rmb(); /* read barrier */
	p = READ_ONCE(b);
}
  • 例2:用 WRITE_ONCE 而不是直接赋值;若采用直接赋值,编译器可能优化出形如 右边注释块 的代码:

	                        // b = 42;
if (a)                          // if (a)
	WRITE_ONCE(b, a);       //	b = a;
else
	WRITE_ONCE(b, 42);
  • 例3:留意到两个 WRITE_ONCE(b, p) 一摸一样,编译器可能会提取到“if …”语句之前
    • WRITE_ONCE() 像上描述的那样,被编译器上移,CPU 就可以乱序执行之了(而不是在条件分支之后生效)
    • 通过塞入 barrier() 来防止。编译器不能跨 barrier() 来重排指令。

乱序执行 CPU 通常具备猜测执行能力,即依据历史猜条件分支会走哪一条,然后提前执行。猜测执行的指令会作上标记,直到条件被确定 —— “猜对”则让生效(比如写到 architecture registers,或是写到物理内存中;“猜错”则作废)。

另一留意到的是,WRITE_ONCE() 在写原生类型的时候,不带 barrier() 所以不会阻止编译器重排指令,这就是为什么需手动在代码中植入 “barrier()”

q = READ_ONCE(a);
/*
 * Without barrier(), WRITE_ONCE(b, p) may be
 * combined and moved here by compiler
 */
if (q) {
	barrier();
	WRITE_ONCE(b, p);
	do_something();
} else {
	barrier();
	WRITE_ONCE(b, p);
	do_something_else();
}
  • 反面教材1:条件被编译器优化掉,比如下面例中 MAX == 1。这个条件总是成立,编译器会去掉条件判断,将总是成立的分支直接提到外面来:

q = READ_ONCE(a);
if (q % MAX) {
	WRITE_ONCE(b, p);
	do_something();
} else {
	WRITE_ONCE(b, r);
	do_something_else();
}
  • 反面教材2:还是条件被编译器优化掉,不过以另一方式:

q = READ_ONCE(a);
if (q || 1 > 0)
	WRITE_ONCE(b, 1);
  • 反面教材3:条件块之外的 WRITE_ONCE(c, 1),不受分支指令护序,所以会被 CPU 乱序执行:

q = READ_ONCE(a);
if (q) {
	WRITE_ONCE(b, p);
} else {
	WRITE_ONCE(b, r);
}
WRITE_ONCE(c, 1);  /* BUG: No ordering against the read from "a". */

上面三例和前两个反面教材,全是谈论 Control dependencies 中如何防范编译器优化“作祟”。下面顺着再给几例“编译器优化使坏的”、“不易察觉”的情况。

小心编译器优化

反面教材1:

p = 0x76543210; // 请使用 WRITE_ONCE(p, 0x76543210);

给 p 赋值的对象,是一个很大的立即数。这样就无法用一条指令来完成赋值了(因为指令长度,比如 RISC 处理器通常是 32bits,32bits 中只会留一点点,比如 16bits 来编码立即数,这样就需要多条指令了)。编译器可能会用多条立即数“存”指令来,使得期间有多次“存”的动作,其他 CPU 核就可能观察到中间一个“撕裂”的值。

反面教材2:

struct __attribute__((__packed__)) foo {
	short a;
	int b;
	short c;
};
struct foo foo1, foo2;
...

foo2.a = foo1.a;
foo2.b = foo1.b;
foo2.c = foo1.c;

这个是一个 __packed__ 结构体,所以域 int b 之前没有 padding,即起始地址不是 4 字节对齐的。编译器可能用一条 32bit load,来装载“foo1.a”和“foo1.b 的一部分”;再一条 32bits load,来装载“foo1.b 的剩下部分”和“foo1.c”。再两条 32bits store 指令写到 foo2 上。这里,foo1.b 的复制中,也出现了中间的“撕裂”值。所以,还是要请出“WRITE_ONCE” 和 “READ_ONCE”来帮忙:

foo2.a = foo1.a;
WRITE_ONCE(foo2.b, READ_ONCE(foo1.b));
foo2.c = foo1.c;

load/store 地址不对齐的内存变量,有些体系架构下需多条指令,比如 MIPS 要用“lwr + lwl” 来完成一次非对齐 32bits load、“swr + swl” 来完成一次非对齐 32bits store。很显然,其他 CPU 核仍可能观察到中间的“撕裂”值。所以,应避免多线程中去直接使用这样的结构体。

哪些场合需保证内存序?内核有哪些 APIs 可用?

保证内存序,常用 内存屏障 方法。依据各级正确性要求,提供了各种力度的内存屏障。比如通用内存屏障,隔开了(指令流中)其前后的访存指令。而弱一些的读屏障,则隔开(指令流中)其前后的内存读访问;写屏障则隔开(指令流中)其前后的内存写访问。

一个粗略的 “内存序使用场合” 与相应的 “内存序 APIs” 对应如下图:

image

Interprocessor interaction

多核间协同,保证内存序的基础屏障为 smp_mb / smp_rmb / smp_wmb / smp_read_barrier_depends,即通用内存屏障 / 读屏障 / 写屏障 / “依赖读”屏障。屏障使用需要配对,即沟通双方,一方用 通用内存屏障 或弱化为 写屏障;另一方用通用内存屏障,或弱化为 读屏障(或是可进一步弱化为 “依赖读”屏障)。

基础之上、扩展的屏障如下:

  • smp_store_mb:store 某变量 + 通用内存屏障
  • lockless_dereference:相当于 *ptr,但在装载 “ptr” 的值,与装载 “ptr 的值所示地址处的变量” —— 这两个有依赖的装载之间,插入一个 smp_read_barrier_depends

留意到这些是多核协同用到的内存屏障,在 UP 编译配置下(即关闭内核对多核支持),退化为一个编译屏障(即 barrier())。

另要提一句,通用内存屏障之间,符合全局的“传递性”,A,B,C 三个通用内存屏障,若 A 在 B 前,B 在 C 前,则 A 在 C 前。换言之,任意两个通用内存屏障必有先后。其实就是所谓的 “Sequential Consistency” (参见前篇评论区,或对应论文「WRL_Research_Report_957」)。由于指令流中 通用内存屏障 前的访存指令,生效在屏障前;之后的生效在屏障后 —— 故屏障间的先后,进一步影响屏障附近的访存指令。

ACQUIRE / RELEASE

在 Linux 一系列锁的构造:

  • spin lock
  • R/W spin locks
  • mutexes
  • semaphores
  • R/W semaphores

其 “锁定” 和 “释放” 操作暗含内存屏障,下面这个图来自前篇中 spinlock 内存序介绍

image

图中 “虚实线” 恰如交规中的“虚实线” ,虚线一侧访存可能转入临界区,而临界区内访存无法越过 “实线”,从而不能逃逸出临界区。

如果不想让临界区之前 “内存写” 窜入临界区,可使 smp_mb__before_spinlock,然后再施 ACQUIRE。

一组 ACQUIRE 和 RELEASE 可构成 局部的“传递性”,例如下面例子中,cpu0 - 2 构成了一条局部的先后序链:

  • 留意 cpu0、cpu1 之普通访存操作都被 load-acquire 约束在临界区;cpu2 无普通访存操作
  • 若有 r0 == 0 && r1 == 1 && r2 == 1,则可知其序为 cpu0 > cpu1 > cpu2
  • cpu3 不在局部序链中,故可能存在 “r0 == 0 && r1 == 1 && r2 == 1 && r3 == 0 && r4 == 0”
    • 留意 r3 的写端为 cpu0,读端为 cpu3;r4 写端为 cpu3,读端为 cpu1
    • 若 cpu3 的 smp_mb 在局部的先后序链中,则由 r3、r4 可知 cpu3 > cpu0、cpu1 > cpu3,即 cpu1 > cpu3 > cpu0 与第二点矛盾,故 cpu3 不在(反证法)

int u, v, x, y, z; /* all are initialized to zero */

void cpu0(void)
{
	r0 = smp_load_acquire(&x);
	WRITE_ONCE(u, 1);
	smp_store_release(&y, 1);
}

void cpu1(void)
{
	r1 = smp_load_acquire(&y);
	r4 = READ_ONCE(v);
	r5 = READ_ONCE(u);
	smp_store_release(&z, 1);
}

void cpu2(void)
{
	r2 = smp_load_acquire(&z);
	smp_store_release(&x, 1);
}

void cpu3(void)
{
	WRITE_ONCE(v, 1);
	smp_mb();
	r3 = READ_ONCE(u);
}

Other IMPLICIT kernel barriers

某些 kernel 函数自带 barrier 效果,他们是:

  • 开关中断函数:但仅相当于编译器的屏障(即 barrier()
  • 睡眠和唤醒函数:“wait_*()” 和 complete()、“wake_up*()”
  • 其他:比如 schedule() 系列函数,相当于 mb()

下面展开睡眠和唤醒函数,首先 set_current_state()smp_mb。于是,所有调到它的函数都含通用屏障:

prepare_to_wait()
prepare_to_wait_exclusive()

wait_event()
wait_event_interruptible()
wait_event_interruptible_exclusive()
wait_event_interruptible_timeout()
wait_event_killable()
wait_event_timeout()
wait_on_bit()
wait_on_bit_lock()

其次,执行唤醒的代码,通常形如下例:

event_indicated = 1;
wake_up(&event_wait_queue); // 或 wake_up_process(event_daemon);

而与之对应的睡眠代码,形如下:

for (;;) {
	set_current_state(TASK_UNINTERRUPTIBLE);
	if (event_indicated)
		break;
	schedule();
}

上面代码头几句解构开来看,如下(左边是 sleeper,右边是 waker,留意 waker 带了个“写屏障” (<write barrier>) ):

CPU 1                           CPU 2
=============================== ===============================
set_current_state();            STORE event_indicated
  smp_store_mb();               wake_up();
    STORE current->state          <write barrier>
    <general barrier>             STORE current->state
LOAD event_indicated

注:只有真正执行了唤醒操作,才会有“写屏障”。因为“写屏障”是在唤醒过程中执行

唤醒函数都自带“写屏障”:

complete();
wake_up();
wake_up_all();
wake_up_bit();
wake_up_interruptible();
wake_up_interruptible_all();
wake_up_interruptible_nr();
wake_up_interruptible_poll();
wake_up_interruptible_sync();
wake_up_interruptible_sync_poll();
wake_up_locked();
wake_up_locked_poll();
wake_up_nr();
wake_up_poll();
wake_up_process();


此节最后一个注意事项,来自这个例子:

/* sleeper */          /* waker */
                       my_data = value;
                       event_indicated = 1;
set_current_state(TASK_INTERRUPTIBLE);
if (event_indicated)
        break;
__set_current_state(TASK_RUNNING);
do_something(my_data);
                       wakeup(&event_wait_queue);

sleeper 可能恰好看到 event_indicated 为 1,但尚未收到 my_data 的新值 value。纠正如下:

/* sleeper */          /* waker */
                       my_data = value;
                       smp_wmb(); /* ★_★ */
                       event_indicated = 1;

set_current_state(TASK_INTERRUPTIBLE);
if (event_indicated) {
        smp_rmb(); /* ★_★,参见本文开头
                    * 关于 Control dependencies 讨论*/
        break;
}
__set_current_state(TASK_RUNNING);
do_something(my_data);

                       wakeup(&event_wait_queue);

Atomic Operations

原子操作其实也属于多核间协同,它们被特别提到因为:

  • 除了 “显示锁定操作”,每个返值(无论返旧值或新值)的原子操作,都(效果上)包含一个 smp_mb(回见前篇中 ARMv8 上原子加的介绍):

// 可用来实现 ACQUIRE 以及 RELEASE
xchg();
atomic_xchg();                  atomic_long_xchg();
atomic_inc_return();            atomic_long_inc_return();
atomic_dec_return();            atomic_long_dec_return();
atomic_add_return();            atomic_long_add_return();
atomic_sub_return();            atomic_long_sub_return();
atomic_inc_and_test();          atomic_long_inc_and_test();
atomic_dec_and_test();          atomic_long_dec_and_test();
atomic_sub_and_test();          atomic_long_sub_and_test();
atomic_add_negative();          atomic_long_add_negative();
test_and_set_bit();
test_and_clear_bit();
test_and_change_bit();

/* when succeeds */
cmpxchg();
atomic_cmpxchg();               atomic_long_cmpxchg();
atomic_add_unless();            atomic_long_add_unless();
  • “显示锁定操作”,带有 load ACQUIRE / store RELEASE 内存屏障:

// 实现锁时,应首先考虑用这些原子操作:
test_and_set_bit_lock();
clear_bit_unlock();
__clear_bit_unlock();
  • 不暗含内存屏障:

atomic_add();
atomic_sub();
atomic_inc();
atomic_dec();

// 可用来实现 RELEASE
atomic_set();
set_bit();
clear_bit();
change_bit();

对于不含内存屏障的原子操作,可通过前后加入 smp_mb__before_atomicsmp_mb__after_atomic,来带入内存屏障。比如引用计数的实现中:

obj->dead = 1; /* 指示对象已经消亡 */
smp_mb__before_atomic();
atomic_dec(&obj->ref_count); /* 若缺了上个内存屏障,可能观察到
                              * obj->ref_count == 0,但 obj->dead != 1

Interrupts、Accessing Devices

CPU 和 设备间通信,或通过系统内存(System Memory),或通过 MMIO(Memory Mapped IO)或 IN/OUT 指令。

思考 DMA(Direct Memory Access):CPU 分配一段缓冲区,然后把 缓冲区地址输入数据 丢给设备。设备工作完成后,结果存在缓冲区,并中断 CPU 告之。

在中断中,CPU 从缓冲区取结果,或继续填下一段输入。如前述开关中断的函数仅暗含编译屏障(即 barrier()),故需内存屏障来保证彼此看到正确的数据,这就是 dma_wmbdma_rmb(以及 wmbrmbmb):

  • Documentation/memory-barrier.txt 中关于两者描述,提及了其作用于连续的物理内存。我们知道,常常设备只能 DMA 低(物理)地址的连续区域。
  • 通过 IOMMU 单元,一些设备能够访问虚拟地址,故无需物理内存连续。此时,内存屏障应该是通过 mbwmbrmb
  • dma_wmbdma_rmbwmbrmb 更加轻量,这个说法来自 patchwork:5334001
  • 下面例子展示其用法:

// desc 结构体负责 CPU 与设备 通信
if (desc->status != DEVICE_OWN) {
        // 从下面注释来看,dma_rmb 像是 Control dependencies
        // 防范乱序执行的措施,参见文章开头处讨论
        //
        // 不过,另一方面,访问 desc->data 之前,同样要加 dma_rmb,
        // 因为读和写的内存屏障要配对嘛
        /* do not read data until we own descriptor */
        dma_rmb();

        /* read/modify data */
        read_data = desc->data;
        desc->data = write_data;

        /* flush modifications before status update */
        dma_wmb();

        // 留意下面这个赋值,起到了关门的作用(A Gate Variable!)
        // 即对某一方,如果是“开门状态”,必然”门后已经准备妥当”
        // (“准备妥当”意为,通过 dma_wmb 保证对方能 __完整__ 看到)
        /* assign ownership */
        desc->status = DEVICE_OWN;

        // 这个据说是处理 cache 一致性的
        /* force memory to sync before notifying device via MMIO */
        wmb();

        // 以下这个操作访问设备的 MMIO
        /* notify device of new descriptors */
        writel(DESC_NOTIFY, doorbell);
}

另外,既然涉及系统内存,必关系 cache 一致性问题(其中,上述内存屏障应已包含类似工作,但有时,也许还需要显式操作 cache):

  • 问题1:各个 CPU 写给设备的东东 还在 cache,尚未抵达内存。解法是各 CPU flush(或有需要,invalidate)相应 cacheline。
  • 问题2:设备 DMA 回来的内存数据,1) 却被某个 CPU 覆写了一部分(该 CPU cache 中的脏行正在回写内存);2) 或 CPU 自己的 cache 未觉察到相应内存区域的更新,使 CPU 从 cache 中读到了旧数据。解法是各 CPU invalidate 相应 cacheline。


MMIO 空间,通常由物理地址窗口来定义,比如 MIPS 32bits 下的 kseg1,intel 的 MTRR 或 PATs。这些物理地址窗口,通常没有 cache 罩着(但可以再细分出窗口,应用写合并优化 (Write Combine,或用龙芯术语,Uncache Accelerate) )。

对 MMIO 空间访问,通过 “readX” 和 “writeX”:

上述两类访问方式,保证 同一物理地址窗口中,它们之间 是全序的,且不会作合并优化。

  • 但不排除总线上存在缓冲,从而最终抵达设备时顺序不保证,可以采用 先写再读同一地址 来进一步保证顺序(但这样做可能让某些设备罢工)。
  • 对于可预取的 IO memory,也许需要 mmiowb 来保证“写”操作。

最后,上述两类访问,存在对应的 “_relaxed” 版本:

  • 访问同一外围设备 时,relaxed 操作间是全序的
  • 其他情况下,比如与普通访存不保证顺序;不能被约束在 LOCK / UNLOCK 所包含的临界区(要约束,请考虑 mmiowb

MMIO 内存序呈现更加的硬件多变性,进一步信息参见「LWN: Semantics of MMIO mapping attributes across architectures」。



Read Related:

Read Latest: