程序完成时分支预测器条目失效？

Question

我试图理解分支预测器条目何时失效。

以下是我所做的实验：

代码1：

start_measure_branch_mispred()
while(X times):
 if(something something):
  do_useless()
 endif
endwhile
end_measurement()
store_difference()

因此，我正在多次运行此代码。我可以看到，在第一次运行之后，错误预测率会降低。分支预测器学习如何正确预测。但是，如果我一次又一次地运行这个实验（即通过将./experiment写入终端），所有的第一次迭代都是从高错误率开始的。因此，在每次执行时，这些条件分支的分支预测单位都无效。我正在使用无刷，并且我已禁用ASLR。我还在一个孤立的核心上运行这个实验。我已经运行了这个实验几次，以确保这是行为（即不是因为噪音）。

我的问题是:程序停止执行后，CPU会使分支预测单元无效吗？或者这是什么原因造成的？

我做过的第二个实验是：

代码2：

do:
    start_measure_branch_mispred()
    while(X times):
      if(something something):
        do_useless()
      endif
    endwhile
    end_measurement()
    store_difference()
while(cpu core == 1)

在这个实验中，我从两个不同的终端运行不同的进程。第一个被固定在core 1上，这样它就会在core 1上运行，它会进行这个实验，直到我停止它（通过杀死它）。然后，我从另一个终端运行第二个进程，并将进程固定在不同的内核上。由于这个进程在不同的内核中，它只会执行1次do-time循环。如果第二个进程被固定在第一个的兄弟内核（相同的物理内核）上，我看到在第一次迭代中，第二个进程的猜测几乎正确。如果我将第二个进程固定在另一个不是第一个兄弟的核心上，那么第二个进程的第一次迭代会产生更高的误判。这是意料之中的结果，因为同一物理内核上的虚拟内核共享相同的分支预测单元（这是我的假设）。因此，第二个进程有利于训练有素的分支预测单元，因为它们具有相同的虚拟地址并映射到相同的分支预测单元条目。

据我所知，由于CPU没有完成第一个进程（执行繁忙循环的核心1进程），分支预测条目仍然存在，第二个进程可以从中受益。但是，在第一个中，从一个运行到另一个运行，我得到了更高的错误预测。

编辑:由于另一个用户需要代码，这就是。您需要从这里下载性能事件标题代码

编译方法： $（CXX） -标准 =c 11 -O0 主.cpp -lp线程 -o 实验

代码：

#include "linux-perf-events.h"

#include <algorithm>
#include <climits>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <vector>

// some array
int arr8[8] = {1,1,0,0,0,1,0,1};

int pin_thread_to_core(int core_id){            
    int retval;     
    int num_cores = sysconf(_SC_NPROCESSORS_ONLN);      
    if (core_id < 0 || core_id >= num_cores)            
        retval = EINVAL;                                
    cpu_set_t cpuset;                                   
    CPU_ZERO(&cpuset);                                  
    CPU_SET(core_id, &cpuset);                          
    retval = pthread_setaffinity_np(pthread_self(), sizeof(cpu_set_t), &cpuset);
    return retval;
}

void measurement(int cpuid, uint64_t howmany, int* branch_misses){

    int retval = pin_thread_to_core(cpuid);
    if(retval){
        printf("Affinity error: %s\n", strerror(errno));
        return;
    }

    std::vector<int> evts;
    evts.push_back(PERF_COUNT_HW_BRANCH_MISSES); // You might have a different performance event!

    LinuxEvents<PERF_TYPE_HARDWARE> unified(evts, cpuid); // You need to change the constructor in the performance counter so that it will count the events in the given cpuid

    uint64_t *buffer = new uint64_t[howmany + 1];
    uint64_t *buffer_org; // for restoring
    buffer_org = buffer;
    uint64_t howmany_org = howmany; // for restoring

    std::vector<unsigned long long> results;
    results.resize(evts.size());

    do{
        for(size_t trial = 0; trial < 10; trial++) {

            unified.start();
            // the while loop will be executed innerloop times
            int res;
            while(howmany){
                res = arr8[howmany & 0x7]; // do the sequence howmany/8 times
                if(res){
                    *buffer++ = res;
                }       
                howmany--;
            }
            unified.end(results);
            // store misses
            branch_misses[trial] = results[0];
            // restore for next iteration
            buffer = buffer_org;
            howmany = howmany_org;
        }
    }while(cpuid == 5); // the core that does busy loop

    // get rid of optimization
    howmany = (howmany + 1) * buffer[3];
    branch_misses[10] = howmany; // last entry is reserved for this dummy operation

    delete[] buffer;

}
void usage(){
    printf("Run with ./experiment X \t where X is the core number\n");
}
int main(int argc, char *argv[]) {
    // as I have 11th core isolated, set affinity to that
    if(argc == 1){
        usage();
        return 1;
    }

    int exp = 16; // howmany

    int results[11];
    int cpuid = atoi(argv[1]); 

    measurement(cpuid, exp, results);

    printf("%d measurements\n", exp);

    printf("Trial\t\t\tBranchMiss\n");
    for (size_t trial = 0; trial < 10; trial++)
    {
        printf("%zu\t\t\t%d\n", trial, results[trial]);
    }
    return 0;
}

如果要尝试第一个代码，只需运行＜code＞/实验1两次。它将具有与第一个代码相同的执行。

如果要尝试第二个代码，请打开两个终端，运行＜code＞/在第一个测试中测试X，然后运行/在第二个实验中，实验Y，其中X和Y是cpuid。

请注意，您可能没有相同的性能事件计数器。此外，请注意，您可能需要更改busycle中的cpuid。

Answer 1

TL：DR：省电深度睡眠状态清晰的分支预测器历史。将睡眠水平限制在C3可以保留布罗德韦尔。从广义上讲，包括BTB和RSB在内的所有分支预测状态都保留在C3和较浅中。

为了使分支历史记录在运行中有用，禁用 ASLR（因此虚拟地址相同）也有助于，例如使用非 PIE 可执行文件。

此外，在单个内核上隔离进程，因为分支预测器条目是Intel CPU上物理内核的本地项。然而，核心隔离并非绝对必要。如果您在一个大部分空闲的系统上连续运行该程序多次，您会发现有时它可以工作，但并不总是如此。基本上，任何碰巧在同一个核心上运行的任务，即使是短时间，都会污染分支预测器状态。因此，在独立的内核上运行有助于获得更稳定的结果，特别是在繁忙的系统上。

有几个因素会影响分支预测失误的测量数量，但可以将它们相互隔离，以确定导致这些预测失误的原因。在讨论细节之前，我需要先介绍一些术语和我的实验设置。

我将使用您发布的答案中的代码版本，该版本比问题中显示的版本更通用。以下代码显示了最重要的部分：

void measurement(int cpuid, uint64_t howmany, int* branch_misses) {
    ...
        for(size_t trial = 0; trial < 4; trial++) {

            unified.start();
            int res;
            for(uint64_t tmp = howmany; tmp; tmp--) {
                res = arr8[tmp & 0x7];
                if(res){
                    *buffer++ = res;
                }
            }
            unified.end(results);
            ...
        }
    ...
}

int main(int argc, char *argv[]) {
    ...
    for(int i = 0; i < 3; ++i) {
        measurement(cpuid, exp, results);
        std::this_thread::sleep_for(std::chrono::milliseconds(1));
    }
    ...
}

该程序的单次执行执行多组测量测量函数中while循环的分支错误预测数（事件BR_MISP_RETIRED.ALL_BRANCHES在Intel处理器上）。每组测量之后是调用sleep_for（）Hibernate1ms。同一集合内的测量仅通过调用unified.start（）和unified.end（）分开，它们在内部执行到内核模式和返回用户模式的转换。我已经通过实验确定，一个集合中的测量次数为4，集合的次数为3就足够了，因为分支错误预测的次数不会超过这个数。此外，代码中调用pin_thread_to_core的确切位置似乎并不重要，这表明围绕感兴趣区域的代码没有污染。

在我的所有实验中，我都使用 gcc 7.4.0 -O0 编译了代码，并在启用了 Linux 4.15.0 和禁用超线程的英特尔 Broadwell 处理器的系统上本机运行它。正如我稍后将要讨论的那样，重要的是要查看感兴趣区域中存在哪些类型的分支（即，正在测量分支错误预测数量的代码）。由于已将事件计数限制为仅用户模式事件（通过将 perf_event_attr.exclude_kernel 设置为 1），因此只需考虑用户模式代码。但是使用 -O0 优化级别和 C 会使本机代码有点丑陋。

统一.start（） 函数包含对 ioctl（） 的两次调用，但用户模式事件仅在从第二次调用返回后才进行测量。从 unified.start（） 中的该位置开始，有一堆对 PLT 的调用（仅包含无条件的直接跳转）、一些直接跳转和末尾的 ret。while 循环实现为几个有条件和无条件的直接跳转。然后调用统一.end（），它调用 ioctl 以转换为内核模式并禁用事件计数。在整个感兴趣的区域中，除了单个 ret 之外，没有其他间接分支。任何 ret 或条件跳转指令都可能生成分支错误预测事件。间接跳转和调用如果存在，也可能生成错误预测事件。了解这一点很重要，因为活动的 Spectre v2 缓解措施可以更改用于预测 rets 以外的间接分支（称为 BTB）的缓冲区的状态。根据内核日志，系统上使用以下 Spectre 缓解措施：

Spectre V1 ： 缓解措施：用户复制/交换屏障和__user指针清理 光谱 V2 ： 缓解措施：完全通用的交换线性
光谱 V2 ： 幽灵 v2 / SpectreRSB 缓解措施：在上下文开关上填充 RSB
幽灵 V2 ： 启用对固件调用的限制推测
Spectre V2 ： 缓解措施： 启用有条件的间接分支预测屏障

上述实验设置是基线设置。下面讨论的一些实验使用了额外的编译选项或内核参数。首先，我使用< code > Intel _ idle . max _ cstate 来限制内核可以使用的最深内核C状态。Broadwell支持以下核心C状态:C0、C1、C1E、C3、C6和C7。我只需要使用两个< code>max_cstate值，即3和6，这样内核就不会分别使用低于C3和C6的核心C状态。一些实验是在使用< code>isolcpus内核参数隔离的内核上运行的。最后，一些实验使用用< code>-no-pie选项编译的代码，该选项禁用pie。所有其他内核参数都有默认值。特别是，CPU漏洞缓解总是处于启用状态。

下图显示了在不同配置中测量的预测失误数量。我遵循了以下实验方法：

• 根据要进行的实验的要求配置系统。然后重新启动系统，使分支预测缓冲区的状态与其他实验使用的状态相同。
• 程序在终端上连续运行十次。如果配置中使用了solcpus，则程序始终在隔离内核上运行。
• 十次运行中的每一次都有三组四个测量值。图中没有显示第一次运行的第一组的四个测量值，因为在所有配置中数字几乎相同。它们基本上是15、6、3和2个错误预测。这些是分支预测器的训练运行，因此预计第一次测量的错误预测次数会很高，并且随着分支预测器的学习，它将在以后的测量中减少。增加同一集合中的测量次数不会进一步减少错误预测的数量。其余的测量值绘制在图中。每种配置的12条对应于单次运行中以相同顺序执行的12次测量。数字在十次运行中取平均值（除了第一次运行的第一组数字不包含在前四个条中的平均值中）。图中的标签sXmY是指集合X的测量Y在十次运行中的平均错误预测次数。

第一种配置基本上等同于默认配置。第一组的第一个测量指示分支预测器是否保留了它在实验的前一次运行中所学到的。其他两组的第一个测量值指示分支预测器是否在同一次运行中保留了在前一组测量值中学习到的内容，尽管调用了＜code＞sleep_forintel_idle。max_cstate被设置为6，这意味着cpuidle子系统可以选择将一个内核放入C6，当它有一个空的运行队列时。这是预期的，因为C6是功率门控状态。

在第五种配置中，< code > Intel _ idle . max _ cstate 设置为3，这意味着内核允许使用的最深C状态是C3，这是一种时钟门控状态。结果表明，分支预测器现在可以在调用< code>sleep_for时保留其信息。使用像< code>strace这样的工具，您可以确认无论< code > Intel _ idle . max _ cstate 如何，< code>sleep_for总是调用< code>nanosleep系统调用。这意味着用户-内核转换不能成为在先前配置中污染分支预测历史的原因，并且C-状态必须是这里的影响因素。

Broadwell 支持 C 状态的自动提升和降级，这意味着硬件本身可以将 C 状态更改为与内核请求的不同。如果不禁用这些html" target="_blank">功能，结果可能会有点不安，但我没有发现这是一个问题。我观察到，在C3或C6中花费的循环数（取决于intel_idle.max_cstate）随着测量集数量的增加而增加。

在第五种配置中，第一个杆与先前的配置一样高。因此，分支预测器仍然无法记住它在第一次运行中学到了什么。第六和第七配置类似。

在第八个配置中，第一个栏明显低于早期的配置，这表明分支预测器现在可以从它在同一程序的前一次运行中学到的东西中受益。这是通过除了将intel_idle.max_cstate设置为3之外使用两个配置选项来实现的：禁用PIE并在隔离的内核上运行。虽然从图中看不清楚，但这两个选项都是必需的。内核可以随机化PIE二进制文件的基地址，这会改变所有分支指令的地址。这使得相同的静态分支指令比前一次运行更有可能映射到不同的分支缓冲区条目。因此，分支预测器在上一次运行中了解到的信息仍然存在于其缓冲区中，但它无法再利用这些信息，因为分支的线性地址已经改变。在隔离内核上运行是必要的这一事实表明内核在空闲内核上运行短任务是很常见的，这会污染分支预测器状态。

八个配置的前四个小节显示分支预测器仍在学习感兴趣区域中的一个或两个分支指令。实际上，所有剩余的分支错误预测都不是针对while循环中的分支。为了表明，实验可以在相同的代码上重复，但没有time循环（即，unified.start（）和unified.end（）之间没有任何内容）。这是第九个配置。观察错误预测的数量是如何大致相同的。

第一个柱仍然比其他柱高一点。此外，似乎有些分支预测器很难预测。第十个配置将 -no-pie 向前推进了一步，并完全禁用了 ASLR。这使得第一个条形与其他条形大致相等，但不能消除两个错误的预测。性能记录 -e cpu/分支未命中/uppp -c 1 可用于找出哪些分支被错误预测。它告诉我，感兴趣区域中唯一被错误预测的分支是 ioctl 的 PTL 中的分支指令。我不确定哪两个分支被误解了，为什么。

关于在超线程之间共享分支预测条目，我们知道一些缓冲区是共享的。例如，我们从Spectre攻击中知道，BTB在至少一些Intel处理器上的超线程之间共享。根据英特尔：

如“间接分支预测与英特尔超线程技术（英特尔HT技术）”的描述中所述，共享一个内核的逻辑处理器可能共享间接分支预测器，从而允许一个逻辑处理器控制同一内核的另一逻辑处理器预测的间接分支目标
回想一下，间接分支预测器永远不会在核心之间共享。

您的结果还表明BHT是共享的。我们还知道RSB不是共享的。一般来说，这是一种设计选择。这些结构不必是这样的。

Answer 2

CPU是否在程序停止执行后使分支预测单元失效？

不，CPU不知道程序是否/何时停止执行。

分支预测数据仅对一个虚拟地址空间有意义，因此当您切换到不同的虚拟地址空间时(或者当内核切换到不同的地址空间时，将旧的虚拟地址空间撕开并转换其页表，等等)。放回空闲RAM，然后在您再次启动程序时构建一个全新的虚拟地址空间)，所有旧的分支预测器数据对于新的(完全不同和不相关，即使内容碰巧相同)虚拟地址空间不再有效。

如果第二个进程被固定到第一个进程的兄弟内核（相同的物理内核），我看到在第一次迭代中，第二个过程几乎正确地猜测。

这是预期的结果，因为同一物理内核上的虚拟内核共享相同的分支预测单位（这是我的假设）。

在一个完美的世界里；一个明显的安全漏洞（分支预测器状态，可以用来推断导致它的数据的信息，从一个html" target="_blank">逻辑处理器上的受害者进程泄漏到同一核心中不同逻辑处理器上攻击者的进程）不是我所期望的。

世界有些不完美。更具体地说，在完美的世界中，分支预测器条目将具有“标签”（元数据），其中包含条目有效的虚拟地址空间和完整虚拟地址（以及CPU模式），并且所有这些信息将在使用条目预测分支之前由CPU检查；然而，这比使用信息较少的较小标签、意外使用不合适的分支预测器条目以及最终出现“幽灵般的”安全漏洞更昂贵、更慢。

请注意，这是您使用的操作系统无法缓解的已知漏洞，很可能是因为您禁用了针对此类漏洞的第一道防线（ASLR）。

Answer 3

因此，我进行了更多的实验来减少噪声的影响（从_start到main（）函数，或者来自两个程序执行之间可能发生的系统调用和中断，这些程序执行（系统调用和中断）可能会破坏分支预测器。

以下是修改后的实验的伪代码：

int main(int arg){ // arg is the iteration
   pin_thread_to_isolated_core()
   for i=0 to arg:
     measurement()
     std::this_thread::sleep_for(std::chrono::milliseconds(1)); // I put this as it is
   endfor
   printresults() // print after all measurements are completed
}

void measurement(){
   initialization()
   for i=0 to 10:
      start_measurement()
      while(X times) // for the results below, X is 32
        a = arr8[an element] //sequence of 8,
        if(a is odd)
           do_sth()
        endif
      endwhile
      end_measurement()
      store_difference()
   endfor
}

这些是结果:

例如，我将迭代结果指定为 3

Trial           BranchMiss
RUN:1
    0           16
    1           28
    2           3
    3           1
    ....  continues as 1
RUN:2
    0           16   // CPU forgets the sequence
    1           30
    2           2
    3           1
    ....  continues as 1
RUN:3
    0           16
    1           27
    2           4
    3           1
    ....  continues as 1

因此，即使一毫秒的睡眠也会干扰分支预测单元。为什么会这样呢？如果我不在这些测量之间设置Hibernate，CPU可以正确地猜测，即Run2和Run3将如下所示:

RUN:2
    0           1   
    1           1
    ....  continues as 1
RUN:3
    0           1
    1           1
    ....  continues as 1

我相信我减少了从< code>_start到测量点的分支执行。尽管如此，CPU还是会忘记训练过的东西。