内存屏障 和 内存模型

内存模型定义一系列规范，来保证多线程访问共享变量时的 可见性、有序性 和 原子性。

内核中定义的内存屏障

以x86为例：

#define mb() alternative("lock; addl $0,0(%%esp)", "mfence", X86_FEATURE_XMM2)
#define rmb() alternative("lock; addl $0,0(%%esp)", "lfence", X86_FEATURE_XMM2)

#define smp_mb() mb()
#define smp_rmb() rmb()
#define smp_wmb() wmb()
#define smp_read_barrier_depends() read_barrier_depends()
#define set_mb(var, value)           \
        do                           \
        {                            \
            (void)xchg(&var, value); \
        } while (0)

store buffer

接前文，cache 的基本原理 和 多核心cache的一致性。

CPU设计者都是在极致压榨其性能，cache就是CPU设计者压榨CPU性能的一种体现，但是这样他们觉得还不够。

考虑一种状况，假设当core1执行一次 store 操作，且这个 store 操作的 内存地址 对应的 cacheline 在shared 状态，那么core1 需要向 core2 发送 Invalidate message，并且需要等到 core2 返回 invalidate ack 之后才能继续向下执行，那么在这个期间 core1就处于盲等阶段，那么core1必须要等这么久吗？

image.png

我们发现上面这个操作时同步的动作，基于应用开发的角度，我们往往会用队列将其优化为异步的动作。于是同理 CPU 设计者引入了 store buffer，这个 buffer 处于 CPU 与 cache 之间，但它只负责缓存 CPU的写操作。

image.png

有了 store buffer 之后 core1 如果执行 store 操作就不用立刻向 core2 发送 invalidate message 了，core1只需要将 store值 添加到 store buffer 中即可。但是引入store buffer 会带来问题。

store buffer 带来的问题

考虑下面的例子：
初始情况，假定 a 和 b 都为0，且 a 在CPU1的cache line 中，而 b 在 CPU0 的 cache line 中。

// a, b init to 0.
a = 1;
b = a + 1;
assert(b == 2);

• store forwarding
  为了解决这一问题，增加了 store forwarding ，CPU 在载入数据时，会同时查看 cache 和 store buffer ，这样，即使store buffer 中的数据还未写到cache line，同一CPU自身的后续load 操作依旧可以使用 store buffer 中的数据。

void foo()    // CPU0 执行
{
    a = 1;  // store
    b = 1;  // store
}

void bar()    //  CPU1 执行
{
    while (b == 0)   // load
        continue;
    asset(a == 1);   // load
}

下面假定多CPU执行这段代码。初始情况仍然假定 a 和 b 都为0，且 a 在CPU1的 cache line 中，而 b 在CPU0的 cache line 中，CPU0 执行foo()，CPU1执行bar()。

从上面的流程来看，主要是因为第8行太迟了。
那么如何解决上述分歧呢？我们需要告诉CPU，让它们 有一致的理解。于是轮到了 内存屏障。

void foo()
{
    a = 1;
    smp_mb();
    b = 1;
}

void bar()
{
    while(b == 0) 
        continue;
    assert(a == 1);
}

smp_mb()便是内存屏障，它后面的语句要执行写入cache line 的操作前，必须先把store buffer 的内容处理完成。

invalidate queue

image.png

invalidate queue 带来的问题

TSO 模型

所以我们可以这么理解，CPU0 的 store-load 操作，在别的 CPU 看来乱序执行了，变成了 load-store 次序，这种内存模型，我们称之为完全存储定序(Total Store Order)，简称 TSO。

store 和 load的组合有4种：分别是 store-store，store-load，load-load 和 load-store。TSO模型中，只存在 store-load 存在乱序，另外3种内存操作不存在乱序，x86 就是TSO模型。

CPU屏障

CPU 屏障：

• sfence
  实现Store Barrior 会将store buffer中缓存的修改刷入L1 cache中，使得其他cpu核可以观察到这些修改，而且之后的写操作不会被调度到之前，即sfence之前的写操作一定在sfence完成且全局可见。

• lfence
  实现Load Barrior 会将invalidate queue失效，强制读取入L1 cache中，而且lfence之后的读操作不会被调度到之前，即lfence之前的读操作一定在lfence完成（并未规定全局可见性）。

• mfence
  实现Full Barrior 同时刷新store buffer和invalidate queue，保证了mfence前后的读写操作的顺序，同时要求mfence之后写操作结果全局可见之前，mfence之前写操作结果全局可见。

• lock
  用来修饰当前指令操作的内存只能由当前CPU使用，若指令不操作内存仍然由用，因为这个修饰会让指令操作本身原子化，而且自带Full Barrior效果；还有指令比如IO操作的指令、exch等原子交换的指令，任何带有lock前缀的指令以及CPUID等指令都有内存屏障的作用。

C++ 11 为内存屏障提供了专门的函数``，方便统一移植。

#include <atomic>
std::atomic_thread_fence(std::memory_order_acquire);
std::atomic_thread_fence(std::memory_order_release);

代码实际例子

#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>

// Set either of these to 1 to prevent CPU reordering
#define USE_CPU_FENCE 1

//-------------------------------------
//  Main program, as decribed in the post
//-------------------------------------
sem_t beginSema1;
sem_t beginSema2;
sem_t endSema;

int X, Y;
int r1, r2;

void *thread1Func(void *param)
{
    for (;;)
    {
        sem_wait(&beginSema1); // Wait for signal

        X = 1;
#if USE_CPU_FENCE
        asm volatile("mfence" ::
                         : "memory"); // Prevent CPU reordering
#else
        asm volatile("" ::
                         : "memory"); // Prevent compiler reordering
#endif
        r1 = Y;

        sem_post(&endSema); // Notify transaction complete
    }
    return NULL; // Never returns
};

void *thread2Func(void *param)
{
    for (;;)
    {
        sem_wait(&beginSema2); // Wait for signal

        Y = 1;
#if USE_CPU_FENCE
        asm volatile("mfence" ::
                         : "memory"); // Prevent CPU reordering
#else
        asm volatile("" ::
                         : "memory"); // Prevent compiler reordering
#endif
        r2 = X;

        sem_post(&endSema); // Notify transaction complete
    }
    return NULL; // Never returns
};

int main()
{
    // Initialize the semaphores
    sem_init(&beginSema1, 0, 0);
    sem_init(&beginSema2, 0, 0);
    sem_init(&endSema, 0, 0);

    // Spawn the threads
    pthread_t thread1, thread2;
    pthread_create(&thread1, NULL, thread1Func, NULL);
    pthread_create(&thread2, NULL, thread2Func, NULL);

    // Repeat the experiment ad infinitum
    int detected = 0;
    for (int iterations = 1;; iterations++)
    {
        // Reset X and Y
        X = 0;
        Y = 0;
        r1 = 11;
        r2 = 12;

        // Signal both threads
        sem_post(&beginSema1);
        sem_post(&beginSema2);
        // Wait for both threads
        sem_wait(&endSema);
        sem_wait(&endSema);
        // Check if there was a simultaneous reorder
        if (r1 == 0 && r2 == 0)
        {
            detected++;
            printf("%d reorders detected after %d iterations\n", detected, iterations);
        }
    }

    return 0; // Never returns
}

在不使用 cpu 屏障时，即USE_CPU_FENCE宏为0时，会出现r1 == 0 && r2 == 0 条件成立。