使用时间戳计数器和 clock_gettime 缓存未命中
Using time stamp counter and clock_gettime for cache miss
作为此 , in order to calculate the memory miss latency, I have wrote the following code using _mm_clflush, __rdtsc and _mm_lfence (which is based on the code from this ) 的后续行动。
正如您在代码中看到的，我首先将数组加载到缓存中。然后我刷新一个元素，因此缓存行被从所有缓存级别中逐出。我放 _mm_lfence 是为了在 -O3.
期间保持顺序
接下来，我使用时间戳计数器来计算延迟或读取 array[0]。如您所见，在两个时间戳之间，存在三个指令：两个 lfence 和一个 read。所以，我必须减去 lfence 开销。代码的最后一部分计算了该开销。
在代码的末尾，打印了开销和未命中延迟。但是，结果无效！
#include <stdio.h>
#include <stdint.h>
#include <x86intrin.h>
int main()
{
int array[ 100 ];
for ( int i = 0; i < 100; i++ )
array[ i ] = i;
uint64_t t1, t2, ov, diff;
_mm_lfence();
_mm_clflush( &array[ 0 ] );
_mm_lfence();
_mm_lfence();
t1 = __rdtsc();
_mm_lfence();
int tmp = array[ 0 ];
_mm_lfence();
t2 = __rdtsc();
_mm_lfence();
diff = t2 - t1;
printf( "diff is %lu\n", diff );
_mm_lfence();
t1 = __rdtsc();
_mm_lfence();
_mm_lfence();
t2 = __rdtsc();
_mm_lfence();
ov = t2 - t1;
printf( "lfence overhead is %lu\n", ov );
printf( "miss cycles is %lu\n", diff-ov );
return 0;
}
但是，输出无效
$ gcc -O3 -o flush1 flush1.c
$ taskset -c 0 ./flush1
diff is 161
lfence overhead is 147
miss cycles is 14
$ taskset -c 0 ./flush1
diff is 161
lfence overhead is 154
miss cycles is 7
$ taskset -c 0 ./flush1
diff is 147
lfence overhead is 154
miss cycles is 18446744073709551609
有什么想法吗？
接下来，我尝试了 clock_gettime 函数来计算未命中延迟，如下所示
_mm_lfence();
_mm_clflush( &array[ 0 ] );
_mm_lfence();
struct timespec start, end;
clock_gettime(CLOCK_MONOTONIC, &start);
_mm_lfence();
int tmp = array[ 0 ];
_mm_lfence();
clock_gettime(CLOCK_MONOTONIC, &end);
diff = 1000000000 * (end.tv_sec - start.tv_sec) + end.tv_nsec - start.tv_nsec;
printf("miss elapsed time = %lu nanoseconds\n", diff);
输出为miss elapsed time = 578 nanoseconds。靠谱吗？
更新 1：
感谢 Peter 和 Hadi，总结了到目前为止的回复，我发现了
1- Unused variables are omitted in the optimization phase and that was the reason on weird values I seen in the output. Thanks to Peter's reply, there are some ways to fix that.
2- clock_gettime is not suitable for such resolution and that function is used for larger delays.
作为解决方法，我尝试将数组放入缓存中，然后刷新所有元素以确保所有元素都从所有缓存级别中逐出。然后我测量了 array[0] 和 array[20] 的延迟。由于每个元素为 4 个字节，因此距离为 80 个字节。我希望得到两次缓存未命中。但是，array[20] 的延迟类似于缓存命中。一个安全的猜测是缓存行不是 80 字节。所以，也许 array[20] 是由硬件预取的。不总是，但我也再次看到一些奇怪的结果
for ( int i = 0; i < 100; i++ ) {
_mm_lfence();
_mm_clflush( &array[ i ] );
_mm_lfence();
}
_mm_lfence();
t1 = __rdtsc();
_mm_lfence();
int tmp = array[ 0 ];
_mm_lfence();
t2 = __rdtsc();
_mm_lfence();
diff1 = t2 - t1;
printf( "tmp is %d\ndiff1 is %lu\n", tmp, diff1 );
_mm_lfence();
t1 = __rdtsc();
tmp = array[ 20 ];
_mm_lfence();
t2 = __rdtsc();
_mm_lfence();
diff2 = t2 - t1;
printf( "tmp is %d\ndiff2 is %lu\n", tmp, diff2 );
_mm_lfence();
t1 = __rdtsc();
_mm_lfence();
_mm_lfence();
t2 = __rdtsc();
_mm_lfence();
ov = t2 - t1;
printf( "lfence overhead is %lu\n", ov );
printf( "TSC1 is %lu\n", diff1-ov );
printf( "TSC2 is %lu\n", diff2-ov );
输出是
$ ./flush1
tmp is 0
diff1 is 371
tmp is 20
diff2 is 280
lfence overhead is 147
TSC1 is 224
TSC2 is 133
$ ./flush1
tmp is 0
diff1 is 399
tmp is 20
diff2 is 280
lfence overhead is 154
TSC1 is 245
TSC2 is 126
$ ./flush1
tmp is 0
diff1 is 392
tmp is 20
diff2 is 840
lfence overhead is 147
TSC1 is 245
TSC2 is 693
$ ./flush1
tmp is 0
diff1 is 364
tmp is 20
diff2 is 140
lfence overhead is 154
TSC1 is 210
TSC2 is 18446744073709551602
“HW prefetcher brings other blocks”的说法大约有 80% 是正确的。这是怎么回事？还有更准确的说法吗？
你在最后删除了对 tmp 的读取，从而破坏了 Hadi 的代码，因此它被 gcc 优化掉了。 你的定时区域没有负载。 C 语句不是 asm 指令。
查看编译器生成的 asm，例如on the Godbolt compiler explorer。当您尝试对像这样的真正低级的东西进行微基准测试时，您应该始终这样做，尤其是当您的计时结果出乎意料时。
lfence
clflush [rcx]
lfence
lfence
rdtsc # start of first timed region
lfence
# nothing because tmp=array[0] optimized away.
lfence
mov rcx, rax
sal rdx, 32
or rcx, rdx
rdtsc # end of first timed region
mov edi, OFFSET FLAT:.LC2
lfence
sal rdx, 32
or rax, rdx
sub rax, rcx
mov rsi, rax
mov rbx, rax
xor eax, eax
call printf
您从 -Wall 收到有关未使用变量的编译器警告，但您可以通过仍然优化的方式将其静音。例如您的 tmp++ 不会使 tmp 可用于函数之外的任何内容，因此它仍然会进行优化。使警告静音是不够的：打印值，return 值，或将其分配给定时区域外的 volatile 变量。 （或者使用内联 asm volatile 来要求编译器在某个时候将它放在寄存器中。Chandler Carruth 的 CppCon2015 talk about using perf 提到了一些技巧：https://www.youtube.com/watch?v=nXaxk27zwlk）
在 GNU C 中（至少使用 gcc 和 clang -O3），你可以强制读取到 (volatile int*)，像这样：
// int tmp = array[0]; // replace this
(void) *(volatile int*)array; // with this
(void) 是为了避免在空上下文中计算表达式时出现警告，例如写 x;.
这种看起来像严格别名 UB，但我的理解是 gcc 定义了这种行为。 Linux 内核在其 ACCESS_ONCE 宏中转换一个指针以添加一个 volatile 限定符，因此它被用于 gcc 绝对关心支持的代码库之一。您总是可以使整个数组 volatile;如果它的初始化不能自动向量化也没关系。
无论如何，这编译为
# gcc8.2 -O3
lfence
rdtsc
lfence
mov rcx, rax
sal rdx, 32
mov eax, DWORD PTR [rsp] # the load which wasn't there before.
lfence
or rcx, rdx
rdtsc
mov edi, OFFSET FLAT:.LC2
lfence
那么您就不必为确保使用 tmp 而烦恼，也不必担心死存储消除、CSE 或持续传播。实际上，_mm_mfence() 或 Hadi 原始答案中的其他内容包含足够的内存屏障，使 gcc 实际上为缓存未命中 + 缓存命中情况重做负载，但它很容易优化掉其中一个重载。
请注意，这可能会导致 asm 加载到寄存器但从不读取它。当前 CPU 确实仍在等待结果（特别是如果有 lfence），但覆盖结果可能会让假设的 CPU 丢弃负载而不是等待它。 （这取决于编译器是否碰巧在下一个 lfence 之前对寄存器做了其他事情，比如那里 rdtsc 结果的 mov 部分。）
这对硬件来说很难/不太可能，因为 CPU 必须为异常做好准备，请参阅 .) RDRAND reportedly does work that way (What is the latency and throughput of the RDRAND instruction on Ivy Bridge?），但这可能是一种特殊情况。
我自己在 Skylake 上进行了测试，方法是在编译器的 asm 输出中添加一个 xor eax,eax，就在 mov eax, DWORD PTR [rsp] 之后，以终止缓存未命中加载的结果。这并不影响时间。
不过，这是丢弃 volatile 加载结果的潜在问题；未来 CPU 的行为可能会有所不同。最好汇总加载结果（在计时区域之外）并在末尾将它们分配给 volatile int sink，以防将来 CPUs 开始丢弃产生未读结果的微指令。但是仍然使用 volatile 来加载以确保它们发生在你想要的地方。
另外不要忘记做一些预热循环以使 CPU 达到最大速度，除非你 想要 以空闲时钟速度测量缓存未命中执行时间。看起来你的空计时区域占用了很多参考周期，所以你的 CPU 可能计时很慢。
So, how exactly cache attacks, e.g. meltdown and spectre, overcome such issue? Basically they have to disable hw prefetcher since they try to measure adjacent addresses in order to find if they are hit or miss.
作为 Meltdown 或 Spectre 攻击一部分的缓存读取侧通道通常使用足够大的步幅，以至于 HW 预取无法检测到访问模式。例如在单独的页面上而不是连续的行上。 meltdown cache read prefetch stride 的第一个 google 命中之一是 https://medium.com/@mattklein123/meltdown-spectre-explained-6bc8634cc0c2，它使用 4096 的步幅。对于 Spectre 来说可能更难，因为你的步幅取决于 "gadgets" 你可以在目标进程中找到。
作为此 _mm_clflush, __rdtsc and _mm_lfence (which is based on the code from this
正如您在代码中看到的，我首先将数组加载到缓存中。然后我刷新一个元素，因此缓存行被从所有缓存级别中逐出。我放 _mm_lfence 是为了在 -O3.
接下来，我使用时间戳计数器来计算延迟或读取 array[0]。如您所见，在两个时间戳之间，存在三个指令：两个 lfence 和一个 read。所以，我必须减去 lfence 开销。代码的最后一部分计算了该开销。
在代码的末尾，打印了开销和未命中延迟。但是，结果无效！
#include <stdio.h>
#include <stdint.h>
#include <x86intrin.h>
int main()
{
int array[ 100 ];
for ( int i = 0; i < 100; i++ )
array[ i ] = i;
uint64_t t1, t2, ov, diff;
_mm_lfence();
_mm_clflush( &array[ 0 ] );
_mm_lfence();
_mm_lfence();
t1 = __rdtsc();
_mm_lfence();
int tmp = array[ 0 ];
_mm_lfence();
t2 = __rdtsc();
_mm_lfence();
diff = t2 - t1;
printf( "diff is %lu\n", diff );
_mm_lfence();
t1 = __rdtsc();
_mm_lfence();
_mm_lfence();
t2 = __rdtsc();
_mm_lfence();
ov = t2 - t1;
printf( "lfence overhead is %lu\n", ov );
printf( "miss cycles is %lu\n", diff-ov );
return 0;
}
但是，输出无效
$ gcc -O3 -o flush1 flush1.c
$ taskset -c 0 ./flush1
diff is 161
lfence overhead is 147
miss cycles is 14
$ taskset -c 0 ./flush1
diff is 161
lfence overhead is 154
miss cycles is 7
$ taskset -c 0 ./flush1
diff is 147
lfence overhead is 154
miss cycles is 18446744073709551609
有什么想法吗？
接下来，我尝试了 clock_gettime 函数来计算未命中延迟，如下所示
_mm_lfence();
_mm_clflush( &array[ 0 ] );
_mm_lfence();
struct timespec start, end;
clock_gettime(CLOCK_MONOTONIC, &start);
_mm_lfence();
int tmp = array[ 0 ];
_mm_lfence();
clock_gettime(CLOCK_MONOTONIC, &end);
diff = 1000000000 * (end.tv_sec - start.tv_sec) + end.tv_nsec - start.tv_nsec;
printf("miss elapsed time = %lu nanoseconds\n", diff);
输出为miss elapsed time = 578 nanoseconds。靠谱吗？
更新 1：
感谢 Peter 和 Hadi，总结了到目前为止的回复，我发现了
1- Unused variables are omitted in the optimization phase and that was the reason on weird values I seen in the output. Thanks to Peter's reply, there are some ways to fix that.
2-
clock_gettimeis not suitable for such resolution and that function is used for larger delays.
作为解决方法，我尝试将数组放入缓存中，然后刷新所有元素以确保所有元素都从所有缓存级别中逐出。然后我测量了 array[0] 和 array[20] 的延迟。由于每个元素为 4 个字节，因此距离为 80 个字节。我希望得到两次缓存未命中。但是，array[20] 的延迟类似于缓存命中。一个安全的猜测是缓存行不是 80 字节。所以，也许 array[20] 是由硬件预取的。不总是，但我也再次看到一些奇怪的结果
for ( int i = 0; i < 100; i++ ) {
_mm_lfence();
_mm_clflush( &array[ i ] );
_mm_lfence();
}
_mm_lfence();
t1 = __rdtsc();
_mm_lfence();
int tmp = array[ 0 ];
_mm_lfence();
t2 = __rdtsc();
_mm_lfence();
diff1 = t2 - t1;
printf( "tmp is %d\ndiff1 is %lu\n", tmp, diff1 );
_mm_lfence();
t1 = __rdtsc();
tmp = array[ 20 ];
_mm_lfence();
t2 = __rdtsc();
_mm_lfence();
diff2 = t2 - t1;
printf( "tmp is %d\ndiff2 is %lu\n", tmp, diff2 );
_mm_lfence();
t1 = __rdtsc();
_mm_lfence();
_mm_lfence();
t2 = __rdtsc();
_mm_lfence();
ov = t2 - t1;
printf( "lfence overhead is %lu\n", ov );
printf( "TSC1 is %lu\n", diff1-ov );
printf( "TSC2 is %lu\n", diff2-ov );
输出是
$ ./flush1
tmp is 0
diff1 is 371
tmp is 20
diff2 is 280
lfence overhead is 147
TSC1 is 224
TSC2 is 133
$ ./flush1
tmp is 0
diff1 is 399
tmp is 20
diff2 is 280
lfence overhead is 154
TSC1 is 245
TSC2 is 126
$ ./flush1
tmp is 0
diff1 is 392
tmp is 20
diff2 is 840
lfence overhead is 147
TSC1 is 245
TSC2 is 693
$ ./flush1
tmp is 0
diff1 is 364
tmp is 20
diff2 is 140
lfence overhead is 154
TSC1 is 210
TSC2 is 18446744073709551602
“HW prefetcher brings other blocks”的说法大约有 80% 是正确的。这是怎么回事？还有更准确的说法吗？
你在最后删除了对 tmp 的读取，从而破坏了 Hadi 的代码，因此它被 gcc 优化掉了。 你的定时区域没有负载。 C 语句不是 asm 指令。
查看编译器生成的 asm，例如on the Godbolt compiler explorer。当您尝试对像这样的真正低级的东西进行微基准测试时，您应该始终这样做，尤其是当您的计时结果出乎意料时。
lfence
clflush [rcx]
lfence
lfence
rdtsc # start of first timed region
lfence
# nothing because tmp=array[0] optimized away.
lfence
mov rcx, rax
sal rdx, 32
or rcx, rdx
rdtsc # end of first timed region
mov edi, OFFSET FLAT:.LC2
lfence
sal rdx, 32
or rax, rdx
sub rax, rcx
mov rsi, rax
mov rbx, rax
xor eax, eax
call printf
您从 -Wall 收到有关未使用变量的编译器警告，但您可以通过仍然优化的方式将其静音。例如您的 tmp++ 不会使 tmp 可用于函数之外的任何内容，因此它仍然会进行优化。使警告静音是不够的：打印值，return 值，或将其分配给定时区域外的 volatile 变量。 （或者使用内联 asm volatile 来要求编译器在某个时候将它放在寄存器中。Chandler Carruth 的 CppCon2015 talk about using perf 提到了一些技巧：https://www.youtube.com/watch?v=nXaxk27zwlk）
在 GNU C 中（至少使用 gcc 和 clang -O3），你可以强制读取到 (volatile int*)，像这样：
// int tmp = array[0]; // replace this
(void) *(volatile int*)array; // with this
(void) 是为了避免在空上下文中计算表达式时出现警告，例如写 x;.
这种看起来像严格别名 UB，但我的理解是 gcc 定义了这种行为。 Linux 内核在其 ACCESS_ONCE 宏中转换一个指针以添加一个 volatile 限定符，因此它被用于 gcc 绝对关心支持的代码库之一。您总是可以使整个数组 volatile;如果它的初始化不能自动向量化也没关系。
无论如何，这编译为
# gcc8.2 -O3
lfence
rdtsc
lfence
mov rcx, rax
sal rdx, 32
mov eax, DWORD PTR [rsp] # the load which wasn't there before.
lfence
or rcx, rdx
rdtsc
mov edi, OFFSET FLAT:.LC2
lfence
那么您就不必为确保使用 tmp 而烦恼，也不必担心死存储消除、CSE 或持续传播。实际上，_mm_mfence() 或 Hadi 原始答案中的其他内容包含足够的内存屏障，使 gcc 实际上为缓存未命中 + 缓存命中情况重做负载，但它很容易优化掉其中一个重载。
请注意，这可能会导致 asm 加载到寄存器但从不读取它。当前 CPU 确实仍在等待结果（特别是如果有 lfence），但覆盖结果可能会让假设的 CPU 丢弃负载而不是等待它。 （这取决于编译器是否碰巧在下一个 lfence 之前对寄存器做了其他事情，比如那里 rdtsc 结果的 mov 部分。）
这对硬件来说很难/不太可能，因为 CPU 必须为异常做好准备，请参阅
我自己在 Skylake 上进行了测试，方法是在编译器的 asm 输出中添加一个 xor eax,eax，就在 mov eax, DWORD PTR [rsp] 之后，以终止缓存未命中加载的结果。这并不影响时间。
不过，这是丢弃 volatile 加载结果的潜在问题；未来 CPU 的行为可能会有所不同。最好汇总加载结果（在计时区域之外）并在末尾将它们分配给 volatile int sink，以防将来 CPUs 开始丢弃产生未读结果的微指令。但是仍然使用 volatile 来加载以确保它们发生在你想要的地方。
另外不要忘记做一些预热循环以使 CPU 达到最大速度，除非你 想要 以空闲时钟速度测量缓存未命中执行时间。看起来你的空计时区域占用了很多参考周期，所以你的 CPU 可能计时很慢。
So, how exactly cache attacks, e.g. meltdown and spectre, overcome such issue? Basically they have to disable hw prefetcher since they try to measure adjacent addresses in order to find if they are hit or miss.
作为 Meltdown 或 Spectre 攻击一部分的缓存读取侧通道通常使用足够大的步幅，以至于 HW 预取无法检测到访问模式。例如在单独的页面上而不是连续的行上。 meltdown cache read prefetch stride 的第一个 google 命中之一是 https://medium.com/@mattklein123/meltdown-spectre-explained-6bc8634cc0c2，它使用 4096 的步幅。对于 Spectre 来说可能更难，因为你的步幅取决于 "gadgets" 你可以在目标进程中找到。