泰晓科技 -- 聚焦嵌入式 Linux - 追本溯源,见微知著!
网站地址:http://tinylab.org
微信公众号关注我们新浪微博


扫一扫

关注 @泰晓科技
原创服务 | 实验云台 | 共享书籍 | 开放源码
请稍侯

Memory Ordering(内存序)

Chen Jie 创作于 2017/01/29

By Chen Jie of TinyLab.org 2017-01-29 21:11:17

前言:

在本站译文「实用同步原语伸缩技术 」中,来自 SUSE 实验室的 Davidlohr Bueso 总结了 Linux 内核对 大规模并发 的优化实践,即所谓的“老司机如何开得快”。而本文讨论的内存序,属于“老司机如何开得稳”。加起来,才有老司机开车又快又稳。

话归同步原语,多线程协同,若无同步机制保证,就像足球赛中传球射门,有时球传了队友还没跑到位。而所谓同步机制,基本上是在共享的内存区域,读写“通信变量”。例如,下述程序简述“传球射门”中的协同:

shooter_x = 36                  loop:
shooter_y = 25                  shooter_in_position == 0 ? goto loop
shooter_in_position = 1         ball_target_x = shooter_x;
loop:                           ball_target_y = shooter_y;
ball_passing == 0 ? goto loop   ball_passing = 1
/* get ball and shoot */        /* pass ball */

左边是射手 - 将己位置写入变量、知会传球方。随后等球至并射门;右边传球方 - 等射手就位,设好传球目的坐标,知会射手并传球。

其中上述逻辑的正确性,取决于共享内存中变量的访问顺序,比如,shooter_in_position 务必在 shooter_xshooter_y 之后(确切的说,是在传球方看来)。然实际顺序,未必等同 编码顺序,这便是内存序问题。


那么,哪些因素造成内存序问题?主要有:

  1. 编译器进行的指令优化
  2. CPU 硬件进行的、围绕乱序执行的指令优化
  3. 缓存一致性、总线上的缓冲等

第 1 点:编译中,高级语言被译成汇编指令,为求性能优化,会进一步调整汇编指令。这种调整,就像好心整理你房间的保姆,不经意把重要物件收在箱底,甚至丢弃掉。 为免编译器好心办坏事,常用嵌入式汇编来防止,例如内核中的 barrier() ,防止编译器跨 barrier() 重排指令:

#define barrier() __asm__ __volatile__("": : :"memory")

第 2 点:CPU 在执行中,根据内部单元忙闲,来重新安排指令。若执行指令所需内部单元都闲着,这条指令就可能被提前执行。这便是乱序执行(有兴趣的童鞋可参见本站「NVIDIA 黑科技: 丹佛核心杀到!」文中关于乱序的比喻)。

乱序执行是围绕“保持内部单元利用率”的指令调整,基于硬件运行时状态进行;与之相对的、编译器优化基于编译时刻的静态输入。

当然,上述优化带来的内存序问题,并不是编译器或硬件自作聪明,而是从优化者的视角,认为所做优化不影响正确性。这个“从优化者的视角”,正是内存序问题所在。对于乱序执行,当指令退出后,CPU 内部状态,比如各寄存器值与顺序执行一致。在另一种优化手段“猜测执行”中,猜错误写的寄存器可以撤销。然而作为外部资源 —— 内存、或严格地说物理地址空间,就不一定了。因它为多核 CPU、DMA 控制器,甚至是设备(MMIO)所共享。换句话说,优化只看 结果,但考虑内存序,需 注重过程

第 3 点:缓存一致性同样是一个 只看结果 的过程:共享变量被更新,其在每个核的副本,只要之后同步一致即可,不关心具体同步顺序。

第 2、3 点,均与硬件相关,来自 Wiki:Memory ordering 展示了各体系 CPU 可能的内存序调整:

上图: x86 和 x86-64 架构内存序严格,x86 oostore 是 x86 史上一个变种,通过放宽内存序限制,来收获性能。ARMv7、POWER 以及 Alpha 处理器,作为 RISC 体系架构,追求硬件效率,毫无意外放宽内存序限制。其中,曾经号称地球上最快 CPU 的 Alpha,更是做到了极致,例如存在下述可能情形:

                        /*
                         * 共享变量
                         * const int invalid = -1;
                         * int *result = &invalid;
                         * int idx; (uninitialized,
                         *           let's say its value is
                         *           327673313)
                         */
// CPU 0:                                       // CPU 1:
/* idx at cache A */                            idx = 25;
/* result at cache B */                         flush_cache();
                                                result = &idx;
b = *result;
// b = 327673313!!

CPU 1 先写了 idx 值,随后 flush cache 来强制一个更新广播;最后让 result 指向 idx(其更新广播,由缓存一致协议来决定何时进行,此例假设立即进行了)。

CPU 0 这边,先读取 result 指针,内容为 &idx;然后对指针取值(即读取 idx 值),内容却是 327673313。仿佛先读取 idx,然后再读取 result

为啥会这样?下图做了简释:

image

解决第 2、3 点,就需用内存序相关的指令 —— 告诉硬件,在不能重排的地方,别搞事情;同时在关键点或刷新,或监视 共享通信变量的变化。

总结一下,多线程协同需同步机制,而同步机制的实现,得考虑内存序。下面以两个直白的同步机制:spinlockatomic64_add 操作为例,来看下内存序处理。代码摘取当下较火的、armv8 上的实现。

引例:armv8 上的 自旋锁 和 原子加 实现

自旋锁

从锁的基本 API 入手:spin_lock()spin_unlock()。定义于 include/linux/spinlock.h,内容看起来像一个炸鸡块,外面裹了一层“面粉”:用于整合入 kernel 的基础设定框架,例如提供 SMP/UP、inline 编译开关、抢占、死锁检查等等。内在“鸡肉”,对于 armv8 而言,分别是 arch_spin_lock()arch_spin_unlock(),实现了自旋锁的定义,即CPU 循环尝试锁定,直到获得锁。

自旋锁结构体同样是“包了面粉的炸鸡块”,“鸡肉”定义于 arch/arm64/include/asm/spinlock.h

typedef struct {
#ifdef __AARCH64EB__
	u16 next;
	u16 owner;
#else
	u16 owner;
	u16 next;
#endif
} __aligned(4) arch_spinlock_t;	

owner 和 next 是两个计数器,其中对大小尾端的条件编译,表明内存中,owner 靠前(装载到寄存器后,对应数值低位),而 next 要靠后(装载到寄存器后,对应数值高位)。于是,当我们把 arch_spinlock_t 当作 32bits 来运算时,owner++ 意味着 arch_spinlock_t + 1,而 next++ 意味着 arch_spinlock_t + (1 << 16)。也正因为我们要把 arch_spinlock_t 当作 32bits 运算,所以结构体需要 4 字节对齐。

下图展示 lock 和 unlock 在上述结构体的体现:

image

arch_spin_lock()(其访存操作有:ldaxr, stxr,及可能有的 ldaxr):

static inline void arch_spin_lock(arch_spinlock_t *lock)
{
	unsigned int tmp;
	arch_spinlock_t lockval, newval;

	asm volatile(
	/*
	 * 预取指令 prfm
	 * "pstl1strm",跟着字母念:Prefetch for STore to L1 STReaMingly
	 * Streamlingly 代表流式的,即路过不回头(而非徘徊式)的访问。
	 * 类 MADV_SEQUENTIAL 之于 madvise()
	 */
"	prfm	pstl1strm, %3\n"

	/*
	 *    高能预警 ★_★
	 * 以下是 RISC 著名的 LL/SC(Load Link / Store Conditional)指令
	 * 即针对一个变量的事务内存,这个变量就是 %3,即“传入参数 lock”所指向
	 *
	 * "The LL": ldaxr:LoaD Acquire eXclusive Register
	 * "The SC": stxr: STore eXclusive Register(eXclusive 代表对单变量的事务内存)
	 * 作为事务内存,stxr 可能失败,比如 ldaxr-stxr 期间“变量 %3”被其他核改变。失败时 %w2 为 1
	 */
"1:	ldaxr	%w0, %3\n"
"	add	%w1, %w0, %w5\n" /* 即 lock->next + 1 */
"	stxr	%w2, %w1, %3\n"
"	cbnz	%w2, 1b\n" /* 若 %w2 不为 0(为 1),则回到“标签 1”重试 */

	/*
	 * 至此,我们原子地 “lock->next++”。而 %w0 则是 “lock 旧值”
	 * 在 “%w0” 中,w 代表 word,armv8 语境中为 32bits 长度。
	 * “%w0, ror #16” 代表将 %w0 循环右移 16 位,即颠倒了 owner 和 next 位置
	 * 然后与颠倒前进行异或,结果为 0 代表 owner == next,即获得了锁,前进到“标签 3”
	 */
"	eor	%w1, %w0, %w0, ror #16\n"
"	cbz	%w1, 3f\n"

	/*
	 * 锁被别人拿走了,急的团团转!具体是这样转的:
	 */
"	sevl\n" /* set event locally,在当前核上设置一个事件,用于防止一种“死锁可能性”:
	         * 即“当别人释放锁,发 CPU 事件唤醒等待的核来抢”,但这个事件错过了(对
		 * CPU 而言,只有调用过 wfe 才会监听事件)
	         */
"2:	wfe\n"  /* wait for event,等待事件到达,这会让 CPU 进入低功耗模式 */
"	ldaxrh	%w2, %4\n" /* LoaD Acquire eXculsive Register Halword,即读取 lock->owner */
"	eor	%w1, %w2, %w0, lsr #16\n" /* "%w0, lsr #16",逻辑右移 16 位,即“lock 旧值”->next
	                                   * 留意到此处借“异或操作 eor”,实现了“比较相等与否”的功能,
	                                   * 感受到 RISC 精简指令的光环了吗?
	                                   */
"	cbnz	%w1, 2b\n" /* 若还没拿到锁,回“标签 2”再试! */
"3:"
	: "=&r" (lockval) /* %0 */, "=&r" (newval), "=&r" (tmp), "+Q" (*lock)
	: "Q" (lock->owner), "I" (1 << TICKET_SHIFT) /* %5 */
	: "memory");
	/* 形如 "=&r" 被称作“操作数的限定”(Constraints for asm Operands)。比如
	 * "=" 代表写入,"&" 代表输入输出寄存器不能重叠,"r" 代表分配个通用寄存器作中间载体
	 * 参见:https://gcc.gnu.org/onlinedocs/gcc/Constraints.html
	 */
}

spinlock 锁定过程是先取号,再等候叫号。同时,spinlock 也是一种 CPU 多核间的“秒杀游戏”,只不过这个“秒杀”是取号时进行的。

如果比较下我们生活中遇到的秒杀 —— 不断点击重试,或是进入套路式的“下一步”...“下一步”,最后“失败重来” —— spinlock 这种先取号登记,再按取号顺序分配,是不是更省心、更有公平感?

arch_spin_unlock()(其访存操作有:ldrh, stlrh):

static inline void arch_spin_unlock(arch_spinlock_t *lock)
{
	unsigned long tmp;

        asm volatile(
"       ldrh    %w1, %0\n"      /* LoaD Register Halfword,即读取 lock->owner */
"	add     %w1, %w1, #1\n" /* 即 lock->owner + 1 */
"       stlrh   %w1, %0"        /* STore reLease Register Halfword */
        : "=Q" (lock->owner), "=&r" (tmp)
        :
        : "memory");
}

自旋锁中的访存与内存序

在 lock() 过程中有三类访存:

  1. ldaxr、访存特点:Acquire、eXclusive
  2. stxr、访存特点:eXclusive
  3. ldaxrh、访存特点:Acquire、eXclusive

第一、二类中,exclusive 的 load 和 store 配对,构成了 LL/SC。而 Acquire 则是和 unlock 中的 reLease 配对。

第三类访存是可选的(当 spinlock 处于未锁定状态,则被跳过),其中 Acquire 是和 unlock 中的 reLease 配对。但为啥这个里也有 eXclusive 呢?当某个 CPU 核(ARM 术语唤做 PE)进入某地址的“Exclusive Access”,另一个核对该地址的 Store 操作将使之回到“Open Access”,并产生事件,使之从 wfe 中“醒来”(参见「ARM® Architecture Reference Manual ARMv8, for ARMv8-A architecture profile 」,“B2.10.2 Exclusive access instructions and Shareable memory locations”)。


在 unlock() 过程中有两类访存:

  1. ldrh、访存特点:无
  2. stlrh、访存特点:reLease

这个 reLease 就和 lock() 中的 Acquire 构成了所谓的 Load-Acquire 和 Store-Release:

image

指令流中,夹在 Load-Acquire 和 Store-Release 之间的访存,既不能早于 Load-Acquire 生效,也不能晚于 Store-Release 生效。换言之,Load-Acquire 和 Store-Release 隔出一个临界区来,当某线程修改并离开临界区后,其对临界区的 全部修改立即 被下一个进入临界区的线程看到。

Load-Acquire 和 Store-Release 为实现锁所需的内存序指令。

64 位原子加

64 原子加的系列操作,由“arch/arm64/include/asm/atomic_ll_sc.h”中的宏 ATOMIC64_OPS(add, add) 所展开。其中根据原子加操作返回值,分成了三类:

  1. 不返回:atomic64_add
  2. 返回加以后的值:atomic64_add_return*
  3. 返回加之前的值:atomic64_return_add*

上表中,展开了 atomic64_add_return 实现,可以看到 RISC 没有原子操作指令,again,通过著名的 LL/SC(ld?xr/st?xr)对单变量的事务内存来实现。另外,上述展开包含了俩内存序指令:

  • stlxr:store-release,使得本操作可以和 atomic64_add_return_acquire 配对,构成对某个临界区的协商访问。
  • dmb ish:跟着字母念 - Data Memory Barrier for Inner SHareable domain - 是一个共享内存中的内存屏障。既然是共享内存,与谁共享呢?通常是多核系统中的其它 CPU 核,所以这条指令也是 smp_mb()在 arm 上的实现。另一个需留意的 —— 不仅需要写者执行“内存屏障”,来把更新立即通知到总线;读者也需执行之,来清空本地旧相应缓冲,及时得到最新版本。就好像一方喊“天王盖地虎”,另一方应“宝塔镇河妖”,这个协商才能玩得转。

顺便说一下后缀 _relaxed,意味着本操作,是一个放松内存序限制的版本,比如atomic64_add_return_relaxed,相比 atomic64_add 除了有返回值外,主体实现是一致的。

C/C++ 规范中的内存序

C/C++ 在原子操作函数中,包含一个内存序参数,用于定制的多线程协商访问。其中 C++ 规范中的阐述更详细,以下择之来详细展开。

#include <atomic>

std::atomic<int> cnt = {0};

void f()
{
    for (int n = 0; n < 1000; ++n) {
        cnt.fetch_add(1, std::memory_order_relaxed);
    }
}

std::memory_order_relaxed 是一个内存序参数,意思是内存序无限制,胡来吧🙃。除此之外,还有如下内存序可指定:

  • std::memory_order_consume:用在 std::atomic::load 中,依赖 load 进来值的操作(仔细想想,什么叫“依赖”呢?即指令流中排在 load 之后,并以 load 结果为输入的那些指令),不能在 load 之前生效。除了 Alpha 之外的平台,基本上就是一个编译器级别的屏障,参见前言中关于 Alpha 的图例。
  • std::memory_order_acquirememory_order_release:load-acquire 与 store-release。
  • std::memory_order_acq_rel:read-modify-write(RMW)操作,原子操作包含“acquire”和“release”:当前线程中 访存操作“生效顺序的重排”,不能跨越“本 RMW 中的 store”;store 之后,其结果能被其它线程的 acquire 操作所看到。
  • std::memory_order_seq_cst:Sequentially-consistent ordering —— 除了包含“acquire”和“release”,所有“memory_order_seq_cst”的原子操作,构成一个全局的序列(a single total modification order)。
    • 每个“memory_order_seq_cst”原子操作,在序列中拥有一个序号。
    • 换言之,A、B 和 C 仨“memory_order_seq_cst”原子操作,若 A 在 B 前(A appears before B),B 在 C 前(B appears before C),则 A 在 C 前(A appears before C)。这就是所谓的 传递性(Transitivity)。
    • 下例中,若 CPU 1 fence 晚于 CPU 0(in the single total modification order),则 CPU 1 能成功读到 CPU 0 写的 M:

// CPU 0                      // CPU 1
write M;
std::atomic_thread_fence(
  std::memory_order_seq_cst); /*
         ^                     * the fence in CPU 1 is __after__
          \                    * the fence in CPU 0 in
        appears after          * the single total modification order
            \                  */
             `--------------- std::atomic_thread_fence(
                                std::memory_order_seq_cst);
                              read M; /* perceive the modification
                                         from CPU 0 successfully */

memory-barrier.txt

Documentation/memory-barrier.txt 介绍了 Linux 内核实现的、更复杂的内存序问题解决方案。限于篇幅,拟在新开篇作翻译和学习笔记。

小伙伴们新年快乐,鸡年大吉!


Read More: