指令重排与内存屏障

在数据库的实现中，由于经常涉及到多个线程或进程同时访问共享资源的情况，为了保证共享资源的调度和访问的正确性，需要采用互斥量、原子操作等并发控制方式。通过上述手段，共享变量在并发读写的环境下才不会出现非预期的问题。

借助加锁等方式就能保证共享资源在并发环境下的正确调度，这符合我们的普遍的思维逻辑和经验，程序开发人员通常直接使用该方式即可。然而，在引入了指令重排、CPU指令乱序执行等特性后，基于锁的并发控制是否还能保证正确性？问题的答案应该是肯定的，但确实值得进一步探讨：在有指令重排与乱序的环境中，锁等并发控制方式的内部实现是如何确保依然有效的。

指令重排

什么是指令重排

我们通过高级语言编写的程序代码，会先经过编译过程变为指令序列，最后放入CPU中执行。所谓的指令重排就是：在CPU中执行指令的顺序和我们预先在编写代码时指定的顺序不一致。这种不一致可能由两种情况导致：一种是编译器进行的指令重排，一种是CPU级别的指令重排。那么为什么会出现指令重排现象呢？是因为在某些情况下对指令的执行顺序进行重排可以提高指令的执行效率和CPU的利用率，从而最终提升程序运行的效率。首先是编译器重排，我们通过一段简单的C++代码段举个例子：

int x, y = 0, z = 1;
void f()
{
    x = z;
    y = 1688;
}

复制

这段代码的逻辑非常简单，函数f()先将z的值赋给变量x，然后将常量1688赋值到变量y中，但是编译出来的指令执行顺序真的是像我们写代码时所构想的那样么？我们验证一下：

首先不采用编译器优化，直接使用g++ -S test_reorder.cpp
命令将其编译为汇编指令，得到如下输出，关键指令片段如下：

movl    z(%rip), %eax
movl    %eax, x(%rip)
movl    $1688, y(%rip)
nop

# GCC: (GNU) 9.2.1

复制

可以看到，编译器按照我们预期的顺序生成了汇编指令，并未被重排。然而，当我们为编译器开启O2以上的优化时，使用命令g++ -O2 -S test_reorder.cpp
，生成的指令顺序发生了改变，关键指令片段如下：

.cfi_startproc
movl    $1688, y(%rip)
movl    z(%rip), %eax
movl    %eax, x(%rip)
ret
.cfi_endproc

# GCC: (GNU) 9.2.1

复制

显然，movl $1688, y指令先于movl z, %eax和movl %eax, x执行，指令发生了重排。除此之外，现代CPU大都采用了超标量和乱序执行的设计来提升执行性能，根据CPU架构的不同，指令在CPU的真正执行顺序与编译器给出的指令序列也可能会存在着差异。

指令重排导致的问题

通常在单线程环境下，指令重排不会导致任何问题，因为编译器重排和CPU乱序执行是有一个基本的底线，那就是在单线程环境下无论如何优化，程序执行的最终结果始终与未优化时是一致的。如果这个都无法保证，那就把普遍的认知给颠覆了，是编译器和CPU出了问题。例如，下面的函数代码段，在单线程的环境下，无论运行多少次、开启O1O2O3优化、使用不同架构的CPU，最终的结果始终应是一致的。

int a = 0, b = 1;
int f()
{
    a = b;
    if (a)
    {
        return 1688;
    }
    return 0;
}

// O3优化下，IF判断条件虽进行了较大改写，
// 但最终函数返回的值也为1688.

.cfi_startproc
movl b(%rip), %eax
movl $1688, %edx
testl %eax, %eax
movl %eax, a(%rip)
cmovne %edx, %eax
ret
.cfi_endproc

# GCC: (GNU) 9.2.1

复制

但是，在多进程或多线程并发的场景下，指令重排可能会导致并发问题。让我们看这个例子：

int x, y = 0, z = 1;

// thread 0 -- 在CPU0上运行
void f()
{
    x = z;
    y = 1688;
}

// thread 1 -- 在CPU1上运行
void p()
{
  while (y!=1688);
  print(x);
}

复制

通过刚才的介绍，我们了解到y=1688逻辑经过编译器的优化，可能在x=z之前执行，这就导致当f函数和p函数在两个线程中并行运行时，p函数输出的x值可能为0，也可能为1的情况。原因是两线程存在同时读写某一变量的可能，而这种情况在编译器和CPU的视角下是感知不到的，对指令执行顺序进行了重排，最终影响并发场景下的程序执行结果。

这种现象与我们普遍的认知是存在了差异的，作为程序开发者，通常常识性地认为即使不使用互斥锁控制，当y=1688时，x=z逻辑已经被执行完毕，x的值一定是1。但是，由于指令重排的客观存在，会导致在并发环境下我们的代码执行结果与预期不符，出现并发问题。

并发控制

至此我们了解到，不只是对同一共享资源的并发读写访问，指令乱序也可能导致潜在的并发问题，那么我们需要通过合适的手段来对共享资源进行并发控制，保证程序执行的正确性。

基于锁的并发控制

原理简介

happens before

锁是我们进行并发控制的常用手段，各种编程语言和基础软件中，都有着各种形式的实现。锁的原理就是构造"happens before"语义：当一个线程或进程获得锁时，它可以执行对共享资源的操作，而其他线程或进程则需要等待锁的释放。换句话说，当成功获取锁时，它的所有之前的内存操作（加载和存储）都会在之后的内存操作之前完成。这意味着前面的内存操作在其他线程看来是可见的，并且会按照顺序进行。这种"happens before"语义确保了在锁保护的临界区内的操作总体上的有序性和可见性。其他线程或进程在获取锁之前的内存操作都无法看到，从而避免了数据的不一致性。

这么看来，在保证同一时刻仅有获取锁的进程或线程能对共享资源进行访问时，即使存在临界区内操作的代码指令重排序，在未释放锁之前对临界区内共享资源的读写操作对其余任何进程或线程都是不可见的。这里举个例子来说明这一点：

int x, y = 0, z = 1;

Lock(); // 临界区开始
x = z;
y = 1688;
UnLock(); // 临界区结束

复制

在Lock()和UnLock()内部，尽管x = z和y = 1688的顺序执行顺序有可能被编译器优化后反序执行，但根据锁的happends before的语义：在临界区内无论是先执行x=z还是y=1688，在锁未释放之前，其他线程无法访问这两个变量。当锁被释放后，x = z和y = 1688的逻辑均执行完毕，其他线程再次获取锁进入临界区时访问状态正确的共享资源。

缓存一致性

此外，由于现代CPU普遍有多个核心，且每个核心有自身的本地cache。每次对变量的读写操作都会优先在本地cache上进行，这会导致同一个变量在不同的本地cache中存在多份，每个核心对指定变量的副本不是最新的，且有不一致的可能性。那么，是否会存在即使正确使用锁的情况下，对共享数据的访问也因CPU核心间cache不一致而导致其他并发问题呢？

其实是不会的，因为处理器会在硬件层面实现CPU缓存一致性协议，不同的CPU厂商有着不同的协议实现方式，如：MSI、MESI、MOSI、MOESI等，intel x86/64架构的CPU采用的就是MESI缓存一致性协议。缓存一致性协议可让CPU在本地cache的修改以某种形式通知或同步到其他核心的本地cache上，从而保证对变量的读写在其他线程上的可见性。MESI协议在本篇文章中不做展开介绍。

实现方式

看到这里，我们可以回答最开始的问题了：在指令乱序执行的环境中，若用了锁控制并发访问且使用方式正确，是不会导致并发问题的。但是当我们有了指令重排的概念后，是否又突然心头一紧，加锁和解锁的语句，以及与临界区之间的代码块之间，是否会被重排序呢？！举个例子：

lock_t lck;
int a, b, c;

Lock(&lck);    // 1. 加锁
a = xxx;       // 2. 临界区操作
b = xxx;
c = xxx;
UnLock(&lck);  // 3. 解锁

复制

当我们使用锁的方式保护临界区中的资源时，需要保证CPU中执行指令时也必须按照：1. 加锁（Lock），2. 临界区操作，3. 释放锁（UnLock） 的顺序严格执行的。任何的乱序均会导致锁无效，例如顺序改为132、213、321等任意一种情况都是存在问题的。所以，在锁的实现中必须保证编译器和CPU不会将这几个步骤的指令进行任何形式的重排，该方式的具体实现将在内存屏障小节中进行展开介绍。

内存屏障

什么是内存屏障

通过上文介绍，我们得知指令重排现象是客观存在的，如果要防止指令重排，需要引入一种额外的机制，这种机制被称为内存屏障(Memory Barrier)。

内存屏障也称为内存栅栏，是一种用于控制内存访问顺序和可见性的指令或操作。在多核或多线程系统中，由于处理器和编译器的优化策略，对内存的读写操作可能会发生重排序、缓存不一致或乱序执行等问题，导致程序的运行出现意料之外的结果。内存屏障的作用就是通过插入特定的指令或操作来保证内存访问的有序性和可见性，以避免这些问题。

我们可以通俗的理解为：内存屏障就像一道栅栏，在栅栏之前的指令全部执行完成之后，才允许执行栅栏之后的某些类别指令，从而保证代码在运行时的有序性。一般的，针对对内存中的读写操作不同（load, store），可以将内存屏障分为多种类型，包括读屏障（Read Barrier）、写屏障（Write Barrier）和全屏障（Full Barrier）等。

内存屏障的实现原理

参考Intel开发手册，我们以Intel 的x86/64系统架构为例，它提供了三种内存屏障指令：(1) sfence; (2) lfence; (3) mfence。

The SFENCE, LFENCE, and MFENCE instructions provide a performance-efficient way of ensuring load and store memory ordering between routines that produce weakly-ordered results and routines that consume that data. The functions of these instructions are as follows: • SFENCE — Serializes all store (write) operations that occurred prior to the SFENCE instruction in the program instruction stream, but does not affect load operations. • LFENCE — Serializes all load (read) operations that occurred prior to the LFENCE instruction in the program instruction stream, but does not affect store operations. • MFENCE — Serializes all store and load operations that occurred prior to the MFENCE instruction in the program instruction stream. Note that the SFENCE, LFENCE, and MFENCE instructions provide a more efficient method of controlling memory ordering than the CPUID instruction.

我们来解读一下这三种内存屏障的含义：

• sfence写屏障：所有在sfence前的写入(store/release)等操作是序列化执行的，也就是说，所有出现在屏障之前的写操作，都将先于所有出现在屏障之后的写操作被系统中的其他组件所感知，但是读操作(load)不做保证。

• lfence读屏障：所有在lfence前的读取(load)操作是序列化执行的，也就是说，所有出现在屏障之前读操作，都将先于所有出现在屏障之后的读取操作被系统中的其他组件所感知。

• mfence全屏障：所有在mfence前的读写操作(store/release/load)都是序列化执行的，也就是说，它既确保写操作能够按照屏障前后的指令序写入，也确保读者能够按照指令序完成数据读取。mfence同时具有sfence和lfence的特性，保证所有出现在屏障之前的store/release/load操作都将先于所有出现在屏障之后的store/release/load操作被系统中的其他组件所感知。

这三种屏障可以有以下汇编代码进行实现：

// CPU 写内存屏障
__asm__ __volatile__("sfence":::"memory");

// CPU 读内存屏障
__asm__ __volatile__("lfence":::"memory");

// CPU 全内存屏障
__asm__ __volatile__("mfence":::"memory");

复制

PostgreSQL中的内存屏障实现

到现在，我们已经了解了内存屏障的具体实现方式。下面我们以PostgreSQL内核对内存屏障的封装实现为例，对其进行更全面的介绍，PG将内存屏障分为；pg_read_barrier()：读屏障；pg_write_barrier()：写屏障；pg_memory_barrier()：内存屏障

编译器屏障 (pg_compiler_barrier)

/*
 * pg_compiler_barrier - prevent the compiler from moving code across
 *
 * A compiler barrier need not (and preferably should not) emit any actual
 * machine code, but must act as an optimization fence: the compiler must not
 * reorder loads or stores to main memory around the barrier.  However, the
 * CPU may still reorder loads or stores at runtime, if the architecture's
 * memory model permits this.
 */
#define pg_compiler_barrier() pg_compiler_barrier_impl()
#define pg_compiler_barrier_impl() __asm__ __volatile__("" ::: "memory")

复制

• pg_compiler_barrier函数的目的是防止编译器将代码移动到屏障之后。编译器屏障不会生成实际的机器代码，但它必须作为一种优化屏障，确保编译器不会在屏障周围重新排序对主内存的加载或存储操作。需要注意的是，根据体系结构的内存模型，CPU仍然可以在运行时重新排序加载或存储操作，进行乱序执行。因此，编译器屏障只能防止编译器级别的优化，而无法完全控制CPU运行时的内存重排序，是几种屏障里最弱的保证。

写|读屏障 (pg_write_barrier | pg_read_barrier)

/*
 * pg_(read|write)_barrier - prevent the CPU from reordering memory access
 *
 * A read barrier must act as a compiler barrier, and in addition must
 * guarantee that any loads issued prior to the barrier are completed before
 * any loads issued after the barrier.  Similarly, a write barrier acts
 * as a compiler barrier, and also orders stores.  Read and write barriers
 * are thus weaker than a full memory barrier, but stronger than a compiler
 * barrier.  In practice, on machines with strong memory ordering, read and
 * write barriers may require nothing more than a compiler barrier.
 */
#define pg_read_barrier() pg_read_barrier_impl()
#define pg_write_barrier() pg_write_barrier_impl()

/*
 * Both 32 and 64 bit x86 do not allow loads to be reordered with other loads,
 * or stores to be reordered with other stores, but a load can be performed
 * before a subsequent store.
 *
 * Technically, some x86-ish chips support uncached memory access and/or
 * special instructions that are weakly ordered.  In those cases we'd need
 * the read and write barriers to be lfence and sfence.  But since we don't
 * do those things, a compiler barrier should be enough.
 *
 * "lock; addl" has worked for longer than "mfence". It's also rumored to be
 * faster in many scenarios.
 */
#define pg_read_barrier_impl()  pg_compiler_barrier_impl()
#define pg_write_barrier_impl()  pg_compiler_barrier_impl()

复制

• 这里我们可以看到，在x86架构的pg读屏障和写屏障的实现中，依旧仅采用了编译器屏障。这是因为无论是32位还是64位的x86架构，都不允许加载指令（load）与其他加载指令进行重排序，也不允许存储指令（store）与其他存储指令进行重排序。这意味着CPU不会对load-load操作和store-store操作进行指令重排而导致乱序执行，在该架构的CPU上仅编译器屏障即可。

• 在Intel开发手册中也对该特性进行了描述，参见引用的原文和下图：

The Intel-64 memory-ordering model allows neither loads nor stores to be reordered with the same kind of operation. That is, it ensures that loads are seen in program order and that stores are seen in program order.

图中的示例可以用如下的代码段进行解释：

int x, y, r1, r2 = 0;

// Processor 0
_x = 1;
_y = 1;

// Processor 1
r1 = _y;
r2 = _x;

复制

使用处理器0和处理器1在不加任何互斥锁的情况下分别执行上述代码，根据x86 CPU的特性，在满足编译器屏障的前提下，可以保证不出现程序最终执行结果为r1 = 1且r2 = 0的情况。

只有当处理器0的两个存储操作被重新排序（在它们之间发生了两个加载操作）或者处理器1的两个加载操作被重新排序（在它们之间发生了两个存储操作）时，才会出现r1 = 1且r2 = 0。如果r1 = 1，那么对y的存储操作会在对y的加载操作之前发生。由于Intel-64内存顺序模型不允许对存储操作进行重新排序，因此先前对x的存储操作会在对y的加载操作之前发生。由于Intel-64内存顺序模型不允许对加载操作进行重新排序，因此对x的存储操作也会在后续对x的加载操作之前发生。这样r2 = 1。

综上，在x86的cpu架构中，编译器屏障已能够满足读屏障和写屏障的特性。

全屏障 (pg_memory_barrier)

/*
 * pg_memory_barrier - prevent the CPU from reordering memory access
 *
 * A memory barrier must act as a compiler barrier, and in addition must
 * guarantee that all loads and stores issued prior to the barrier are
 * completed before any loads or stores issued after the barrier.  Unless
 * loads and stores are totally ordered (which is not the case on most
 * architectures) this requires issuing some sort of memory fencing
 * instruction.
 */
#define pg_memory_barrier() pg_memory_barrier_impl()

/*
 * Both 32 and 64 bit x86 do not allow loads to be reordered with other loads,
 * or stores to be reordered with other stores, but a load can be performed
 * before a subsequent store.
 *
 * Technically, some x86-ish chips support uncached memory access and/or
 * special instructions that are weakly ordered.  In those cases we'd need
 * the read and write barriers to be lfence and sfence.  But since we don't
 * do those things, a compiler barrier should be enough.
 *
 * "lock; addl" has worked for longer than "mfence". It's also rumored to be
 * faster in many scenarios.
 */
#define pg_memory_barrier_impl()  \
 __asm__ __volatile__ ("lock; addl $0,0(%%rsp)" : : : "memory", "cc")


复制

在汇编中使用lock前缀和memory约束都与内存屏障相关。

1. lock前缀：lock前缀用于对共享变量进行原子操作。它会告知处理器要执行原子操作，并且在执行期间禁止其他处理器对同一变量的访问，从而确保操作的原子性。同时，lock前缀也会生成一个全屏障，保证在lock前缀指令之前和之后的所有内存访问有序性。

2. memory约束：memory约束用于告知编译器在内联汇编中的内存操作需要考虑内存屏障。这意味着编译器会在该约束所在的内联汇编代码之前和之后插入内存屏障指令，以确保内存操作的顺序性和可见性。

其中，在源码注释中提到：

"lock; addl" has worked for longer than "mfence". It's also rumored to be faster in many scenarios.

这表明 "lock; addl" 命令与mfence相比具有相似的功能，且可能在大多数场景下执行的更高效。

spinlock加解锁过程中的内存屏障

回到在介绍锁并发控制小节最后留下的问题，我们此前推论在锁实现中一定会隐式或显式的加入了内存屏障的来保证加锁、临界区操作、解锁的过程不会被编译器和CPU指令重排序。下面我们通过PostgreSQL中的spinlock加锁实现过程的源码来佐证这一点：

// spinlock 加锁API
#define SpinLockAcquire(lock) S_LOCK(lock)

// S_LOCK实现
#define S_LOCK(lock) \
 (TAS(lock) ? s_lock((lock), __FILE__, __LINE__, PG_FUNCNAME_MACRO) : 0)

// s_lock实现
int
s_lock(volatile slock_t *lock, const char *file, int line, const char *func)
{
 SpinDelayStatus delayStatus;

 init_spin_delay(&delayStatus, file, line, func);

while (TAS_SPIN(lock))
 {
  perform_spin_delay(&delayStatus);
 }

 finish_spin_delay(&delayStatus);

return delayStatus.delays;
}

// TAS_SPIN原语
#define TAS_SPIN(lock)    (*(lock) ? 1 : TAS(lock))

// TAS
static __inline__ int
tas(volatile slock_t *lock)
{
registerslock_t _res = 1;

 __asm__ __volatile__(
" lock   \n"
" xchgb %0,%1 \n"
:  "+q"(_res), "+m"(*lock)
:  /* no inputs */
:  "memory", "cc");
return (int) _res;
}

复制

通过源码我们可以看到，获取锁的操作本质上是由TAS操作来实现的，在intel x86/64架构中有tas的硬件实现， 本质上是通过带"lock"前缀和"memory"约束的xchgb指令来实现的，"lock"和"memory"表明其具有全屏障的特性。至此，锁如何保证加锁解锁，以及临界区访问的逻辑不被指令重排的原因就已经破案了。

总结

本文对指令重排现象进行了分析，并讨论了指令重排对并发读写环境可能造成的影响，此后从锁的实现原理出发，引出了内存屏障的概念并对其进行了介绍。在实际代码开发中，锁已可满足绝大多数的应用场景，在可不使用锁但却对共享内存操作顺序敏感的场景中，可采用添加内存屏障的方式进行控制。