x86可以重新排序一个具有更宽负载的窄存储吗？

Question

英特尔®64和IA-32架构软件开发人员手册说:

8.2.3.4负载可以通过早期存储
重新排序到不同位置 Intel-64内存排序模型允许将负载与早期存储重新排序到不同位置.但是,加载不会与商店重新排序到同一位置.

那些与之前的商店部分或完全重叠但是没有相同起始地址的负载呢？(有关具体案例,请参阅本文末尾)

---

假设以下类似C的代码:

// lock - pointer to an aligned int64 variable
// threadNum - integer in the range 0..7
// volatiles here just to show direct r/w of the memory as it was suggested in the comments
int TryLock(volatile INT64* lock, INT64 threadNum)
{
    if (0 != *lock)
        return 0;                           // another thread already had the lock

    ((volatile INT8*)lock)[threadNum] = 1;  // take the lock by setting our byte

    if (1LL << 8*threadNum != *lock)
    {   // another thread set its byte between our 1st and 2nd check.   unset ours
        ((volatile INT8*)lock)[threadNum] = 0;
        return 0;
    }

    return 1;
}

或者它的x64 asm等价物:

; rcx - address of an aligned int64 variable
; rdx - integer in the range 0..7
TryLock PROC
cmp qword ptr [rcx], 0
jne @fail

mov r8, rdx
mov rax, 8
mul rdx

mov byte ptr [rcx+r8], 1

bts rdx, rax
cmp qword ptr [rcx], rdx
jz  @success

mov byte ptr [rcx+r8], 0

@fail:
mov rax, 0
ret

@success:
mov rax, 1
ret

---

然后假设TryLock在两个线程中同时执行:

INT64 lock = 0;

void Thread_1() {  TryLock(&lock, 1);  }
void Thread_5() {  TryLock(&lock, 5);  }

问题:

在((INT8*)lock)[1] = 1;与((INT8*)lock)[5] = 1;门店并不相同位置的64位负载lock.但是,它们都被该负载完全包含,那么"统计"为同一位置？CPU似乎不可能做到这一点.

怎么样((INT8*)lock)[0] = 1？然后,商店的地址与以下加载的地址相同.这些操作是"在同一地点",即使先前的情况不是这样吗？

ps请注意问题不是关于C/Asm代码,而是关于x86 CPU的行为.

Answer 1

x86可以重新排序一个具有更宽负载的窄存储吗？

是的,x86可以重新排序具有完全包含它的更宽负载的窄存储.

这就是你的锁算法被破坏的原因,shared_value不等于800000:

1. GCC 6.1.0 x86_64 - 汇编代码链接:https://godbolt.org/g/ZK9Wql

   • shared_value =662198:http://coliru.stacked-crooked.com/a/157380085ccad40f

2. Clang 3.8.0 x86_64 - 汇编代码链接:https://godbolt.org/g/qn7XuJ

   • shared_value =538246:http://coliru.stacked-crooked.com/a/ecec7f021a2a9782

见下面的正确例子.

问题:

((INT8*)锁定)[1] = 1; 和((INT8*)锁定)[5] = 1; 商店与64位加载锁不在同一个位置.但是,它们都被该负载完全包含,那么"统计"为同一位置？

不,那不是.

英特尔®64和IA-32架构软件开发人员手册说:

8.2.3.4负载可以通过早期存储重新排序到不同位置Intel-64内存排序模型允许将负载与早期存储重新排序到不同位置.但是,加载不会与商店重新排序到同一位置.

对于相同大小的STORE和LOAD,这是一个简化的规则.

但是一般规则是写入内存的时间会延迟一段时间,并且存储(地址+值)排队到存储缓冲区以等待独占状态(E)中的缓存行 - 此缓存行将被无效( I)在其他CPU核心的缓存中.但是您可以使用asm操作MFENCE(或带[LOCK]前缀的任何操作)强制等待直到写入完成,并且只有在清除了存储缓冲区后才能执行任何后续指令,并且所有CPU内核都可以看到STORE.

关于重新排序两行:

((volatile INT8*)lock)[threadNum] = 1;  // STORE
if (1LL << 8*threadNum != *lock)        // LOAD

• 如果STORE和LOAD大小相等,则LOAD CPU-Core执行(存储转发)查找到Store-Buffer并查看所有必需的数据 - 您可以在STORE完成之前立即获取所有实际数据

• 如果STORE和LOAD大小不相等,STORE(1 Byte)和LOAD(8 Byte),那么即使LOAD CPU-Core查找到Store-Buffer,它也只能看到1/8的所需数据 - 你不能在STORE完成之前立即获取所有实际数据.这可能是2个CPU动作的变种:

  1. case-1: CPU-Core从缓存行加载其他数据,这些数据处于共享状态(S),并且与存储缓冲区重叠1个字节,但STORE仍然保留在存储缓冲区中并等待接收独占状态( E)缓存行来修改它 - 即CPU-Core在STORE完成之前读取数据 - 在你的例子中是数据争用(错误).STORE-LOAD在全局可见的情况下重新排序到LOAD-STORE. - 这正是x86_64上发生的事情

  2. case-2:当刷新Store-Buffer时,CPU-Core等待,STORE等待高速缓存行的独占状态(E)并且STORE已经完成,然后CPU-Core从高速缓存行加载所有需要的数据.STORE-LOAD不会在全局可见的情况下重新排序.但这和你使用的一样MFENCE.

结论,MFENCE在任何情况下都必须在STORE之后使用:

1. 它完全解决了案例-1中的问题.
2. 它不会对case-2中的行为和性能产生任何影响.MFENCE空的Store-Buffer 显式将立即结束.

C和x86_64 asm上的正确示例:

我们通过使用强制CPU-Core在case-2中起作用MFENCE,因此没有StoreLoad重新排序

• GCC 6.1.0(用于mfence刷新存储缓冲区):https://godbolt.org/g/dtNMZ7
• Clang 4.0(用于[LOCK] xchgb reg, [addr]刷新Store-Buffer):https://godbolt.org/g/BQY6Ju

注意:xchgb始终具有前缀LOCK,因此通常不用asm编写或用括号表示.

可以在上面的链接上手动选择所有其他编译器:PowerPC,ARM,ARM64,MIPS,MIPS64,AVR.

C代码 - 应该对第一个STORE和下一个LOAD使用顺序一致性:

#ifdef __cplusplus
#include <atomic>
using namespace std;
#else
#include <stdatomic.h>
#endif

// lock - pointer to an aligned int64 variable
// threadNum - integer in the range 0..7
// volatiles here just to show direct r/w of the memory as it was suggested in the comments
int TryLock(volatile uint64_t* lock, uint64_t threadNum)
{
  //if (0 != *lock)
  if (0 != atomic_load_explicit((atomic_uint_least64_t*)lock, memory_order_acquire)) 
    return 0;                           // another thread already had the lock

  //((volatile uint8_t*)lock)[threadNum] = 1;  // take the lock by setting our byte
  uint8_t* current_lock = ((uint8_t*)lock) + threadNum;
  atomic_store_explicit((atomic_uint_least8_t*)current_lock, (uint8_t)1, memory_order_seq_cst);

  //if (1LL << 8*threadNum != *lock)
  // You already know that this flag is set and should not have to check it.
  if ( 0 != ( (~(1LL << 8*threadNum)) & 
    atomic_load_explicit((atomic_uint_least64_t*)lock, memory_order_seq_cst) )) 
  {   // another thread set its byte between our 1st and 2nd check.   unset ours

    //((volatile uint8_t*)lock)[threadNum] = 0;
    atomic_store_explicit((atomic_uint_least8_t*)current_lock, (uint8_t)0, memory_order_release);
    return 0;
  }

  return 1;
}

GCC 6.1.0 - x86_64 asm-code - 应该MFENCE用于第一个STORE:

TryLock(unsigned long volatile*, unsigned long):
        movq    (%rdi), %rdx
        xorl    %eax, %eax
        testq   %rdx, %rdx
        je      .L7
.L1:
        rep ret
.L7:
        leaq    (%rdi,%rsi), %r8
        leaq    0(,%rsi,8), %rcx
        movq    $-2, %rax
        movb    $1, (%r8)
        rolq    %cl, %rax
        mfence
        movq    (%rdi), %rdi
        movq    %rax, %rdx
        movl    $1, %eax
        testq   %rdi, %rdx
        je      .L1
        movb    $0, (%r8)
        xorl    %eax, %eax
        ret

完整示例如何工作:http://coliru.stacked-crooked.com/a/65e3002909d8beae

shared_value = 800000

如果您不使用会发生什么MFENCE- 数据竞赛

有一个StoreLoad重新排序,如上述情况1所述(即如果不使用顺序一致性进行存储) - asm:https://godbolt.org/g/p3j9fR

• GCC 6.1.0 x86_64 - shared_value = 610307:http://coliru.stacked-crooked.com/a/469f087b1ce32977
• Clang 3.8.0 x86_64 - shared_value = 678949:http://coliru.stacked-crooked.com/a/25070868d3cfbbdd

我改变STORE存储器屏障从memory_order_seq_cst到memory_order_release,它删除MFENCE-现在有数据争用- shared_value不等于800000.

Answer 2

可以mov byte [rcx+r8], 1用cmp qword [rcx], rdx它后面的负载重新排序吗？这是lock[threadNum]=1存储和以下加载，以确保没有其他人写了一个字节。

加载必须返回包含存储的数据，因为正在执行的线程总是按照程序顺序观察自己的动作。（即使在弱排序的 ISA 上也是如此）。

事实证明，这种精确锁定的想法之前已经被提出过（针对 Linux 内核），Linus Torvalds 解释说 x86 确实允许这种重新排序

尽管有术语“存储转发失败或停顿”，但这并不意味着数据必须在加载可以读取之前提交到缓存。当缓存行仍处于 S 状态 ( MESI )时，它实际上可以从存储缓冲区中读取。（在有序 Atom 内核上，您甚至根本不会遇到存储转发停顿。）

真正的硬件确实以这种方式工作（正如 Alex 的测试所示）：CPU 会将来自 L1D 的数据与来自存储缓冲区的数据合并，而不会将存储提交给 L1D。

这本身不是重新排序还没有¹（负载看到商店的数据，以及他们在全球秩序相邻），但它敞开了大门重新排序。在加载之后，但在存储提交之前，缓存行可以被另一个内核失效。来自另一个核心的商店可以在我们加载之后但在我们的商店之前变得全局可见。

因此，负载包括来自我们自己存储的数据，但不包括来自另一个 CPU 的其他存储的数据。另一个 CPU 可以看到其负载的相同效果，因此两个线程都进入临界区。

¹ （这是我在对 Alex 的回答发表评论时提出的观点。如果 x86 不允许这种重新排序，CPU 仍然可以在存储变为全局可见之前推测性地进行存储转发，如果另一个 CPU 使缓存无效，则将其击落在商店提交之前行。亚历克斯的那部分答案并不能证明 x86 的工作方式是这样。只有关于锁定算法的实验测试和仔细推理才给了我们这一点。）

如果 x86 确实不允许这种重新排序，那么存储/部分重叠重新加载对将像 MFENCE 一样工作：早期加载不能在加载之前全局可见，早期存储不能在存储之前全局可见。加载必须在任何后续加载或存储之前变得全局可见，这也将阻止存储延迟。

鉴于这种推理，为什么完全重叠的商店也不等同于 MFENCE 并不完全明显。也许它们确实如此，而 x86 只能通过推测执行快速地在堆栈上进行溢出/重新加载或 arg 传递！

锁定方案：

看起来TryLock两个/所有调用者都可能失败：他们最初都看到它为零，他们都写了他们的字节，然后他们每个人都看到至少两个非零字节。与使用locked 指令相比，这对于竞争激烈的锁来说并不理想。有一个硬件仲裁机制来处理冲突的locked insns。（待办事项：找到英特尔工程师发布的英特尔论坛帖子，以回应另一个软件重试循环与locked 指令主题 IIRC。）

窄写/宽读将始终触发现代 x86 硬件上的存储转发停顿。我认为这只是意味着加载结果还没有准备好几个周期，而不是其他指令的执行停止（至少不是在 OOO 设计中）。

在频繁使用的轻度争用锁中，分支将被正确预测为采用无冲突路径。沿着这条路径的推测执行直到加载最终完成并且分支可以退出不应该停止，因为存储转发停止时间不够长，无法填满 ROB。

• SnB：比存储转发工作时长约 12 个周期 (~5c)
• HSW：增加约 10c
• SKL：比存储转发工作时长约 11c（32 位和 64 位操作数为 4c，比以前的 CPU 少 1c）
• AMD K8/K10：Agner Fog 没有给出数字。

• AMD 推土机系列：25-26c（蒸汽压路机）

• Atom：“与大多数其他处理器不同，即使读取操作数大于前面的写入操作数或不同对齐方式，Atom 也可以进行存储转发”，并且只有 1c 延迟。仅在跨越缓存行边界时失败。

• Silvermont：额外约 5c（基础：7c）
• AMD 山猫/捷豹：4-11c 额外（基础：8c/3c）

因此，如果整个锁定方案有效，它可能适用于轻度争用的锁。

我认为您可以通过在每个字节中为读者使用第 1 位，为编写者使用第 2 位，将其变成多读者/单写者锁。TryLock_reader 将忽略其他字节中的读取器位。TryLock_writer 将像原来一样工作，要求其他字节中的所有位都为零。

顺便说一句，对于一般的内存排序，Jeff Preshing 的博客非常好。