使用 RDTSC 精确测量最大循环计数
Precise measurements of maximum cycle count with RDTSC
我正在开发 low level routines for binary search in C 和 x64 程序集，并尝试测量搜索未缓存数组（RAM 中的数据）的确切执行时间。根据 "lucky" 分支预测的方式，为不同的目标搜索相同的数组所花费的时间差异很大。我可以准确地测量最小和中值执行时间，但我发现很难测量最大执行时间。
问题是分支预测的最坏情况在时间上与平均情况加上处理器中断相当。最坏情况和中断都很少见，但我还没有想出一个好方法来区分一个罕见事件和另一个。标准方法是简单地过滤掉所有 "anomalously" 高测量值，但这只有在两者之间有明确界限的情况下才有效。
所以问题就变成了，“我如何区分被中断的测量和比其他测量花费更长的时间的测量？”
或者更一般地说，“如何在不预先假设硬最大值的情况下测量执行时间的完整分布？”
内核是否存储了任何我可以查询的有关是否发生中断的信息？我可以在测量前后查询的东西会告诉我测量是否中断？理想情况下，它会告诉我中断花费了多长时间的周期，但仅仅知道测量受到影响将是一个很好的开始。
也许除了（或代替）RDTSC，我可以使用 RDPMC 读取一个计数器，该计数器测量在 Ring 0（内核）而不是 Ring 3（用户）中花费的周期数？是否已经设置了一个计数器来执行此操作，还是我需要设置自己的？我需要创建自己的内核模块来执行此操作，还是可以使用现有的 ioctl？
一些背景：
我主要 运行 运行 Ubuntu 14.03 Linux 4.2.0 在 Intel Skylake i7-6700 上，但我也在 Intel Sandy Bridge 和哈斯韦尔。我已经尽力减少系统上的抖动。我用 CONFIG_NOHZ_FULL 重新编译了一个 tickless 内核，没有强制抢占，透明大页面支持关闭，定时器频率为 100 Hz。
我已经停止了大部分不必要的进程，并删除了大部分不必要的内核模块。我正在使用 cpuset / cset shield 为单个进程保留一个 NoHZ 内核，并使用 kernel/debug/tracing 来验证我得到的中断很少。但我仍然得到足够的精确测量是困难的。也许更重要的是，我可以设想未来的长尾情况（很少需要调整大小的哈希 table），在这种情况下，能够区分有效和无效测量将非常有帮助
我正在使用 Intel suggests in their whitepaper 的技术测量 RDTSC/RDTSCP 的执行时间，并且总体上获得了我期望的准确性。我的测试涉及搜索 16 位值，并且我对长度可变的随机数组的 65536 次可能搜索中的每一次重复和单独计时。为了防止处理器学习正确的分支预测，每次都以不同的顺序重复搜索。每次使用 "CLFLUSH".
搜索后，搜索到的数组将从缓存中删除
这是一个研究项目，我的目标是了解这些问题。因此，我愿意采用在其他情况下可能被认为愚蠢和极端的方法。自定义内核模块、保护模式 x64 程序集、未经测试的内核修改和处理器特定功能都是公平的游戏。如果有办法摆脱剩余的少数中断，使所有测量结果为 "real"，那也可能是一个可行的解决方案。感谢您的建议！
我假设您已经在一定程度上屏蔽了基准测试线程
可能：
- 它可以独占访问其 CPU 核心（不仅是 HyperThread），参见 here
关于如何轻松管理它。
- 中断相关性已从该核心移开，请参阅 here
- 如果可能，运行 一个
nohz 内核以最小化计时器滴答声。
此外，你不应该从你的内部跳入内核 space
基准代码路径：在 return 后，您的线程可能会被调度
离开一段时间。
但是，您根本无法消除 CPU 内核上的所有中断：on
Linux，本地APIC定时器中断，处理器间中断
(IPI) 和其他用于内部目的，你根本不能
摆脱他们！例如，定时器中断用于确保，
线程最终得到调度。同样，IPI 用于
触发其他核心的动作，例如 TLB 击落。
现在，由于 Linux 跟踪基础设施，可以从用户space 判断一个
hardirq在某段时间发生了。
一个小问题是 Linux 处理两个 类 中断
在追踪方面有所不同：
- 首先是"real"个外部硬件中断被占用
网络适配器、声卡等真实设备。
- 有Linux内部使用的中断。
从处理器异步的意义上说，两者都是硬中断
将控制转移到中断服务例程 (ISR)，由
中断描述符 table (IDT).
通常，在 Linux 中，ISR 只是一个用汇编语言编写的存根，它
将控制转移到用 C 编写的高级处理程序。
有关详细信息，请参阅 Linux 内核源代码中的 arch/x86/entry_entry_64.S。
对于 Linux-internal 中断，每个都定义了一个跟踪存根
而对于外部中断，tracing留给高层
中断处理程序。
这是每个内部中断都有一个跟踪事件的方式：
# sudo perf list | grep irq_vectors:
irq_vectors:call_function_entry [Tracepoint event]
irq_vectors:call_function_exit [Tracepoint event]
irq_vectors:call_function_single_entry [Tracepoint event]
irq_vectors:call_function_single_exit [Tracepoint event]
irq_vectors:deferred_error_apic_entry [Tracepoint event]
irq_vectors:deferred_error_apic_exit [Tracepoint event]
irq_vectors:error_apic_entry [Tracepoint event]
irq_vectors:error_apic_exit [Tracepoint event]
irq_vectors:irq_work_entry [Tracepoint event]
irq_vectors:irq_work_exit [Tracepoint event]
irq_vectors:local_timer_entry [Tracepoint event]
irq_vectors:local_timer_exit [Tracepoint event]
irq_vectors:reschedule_entry [Tracepoint event]
irq_vectors:reschedule_exit [Tracepoint event]
irq_vectors:spurious_apic_entry [Tracepoint event]
irq_vectors:spurious_apic_exit [Tracepoint event]
irq_vectors:thermal_apic_entry [Tracepoint event]
irq_vectors:thermal_apic_exit [Tracepoint event]
irq_vectors:threshold_apic_entry [Tracepoint event]
irq_vectors:threshold_apic_exit [Tracepoint event]
irq_vectors:x86_platform_ipi_entry [Tracepoint event]
irq_vectors:x86_platform_ipi_exit [Tracepoint event]
而外部中断只有一个通用跟踪事件：
# sudo perf list | grep irq:
irq:irq_handler_entry [Tracepoint event]
irq:irq_handler_exit [Tracepoint event]
irq:softirq_entry [Tracepoint event]
irq:softirq_exit [Tracepoint event]
irq:softirq_raise [Tracepoint event]
因此，在基准测试期间跟踪所有这些 IRQ *_entries
代码路径，你就知道你的基准测试样本是否中毒了
是否通过 IRQ。
注意x86上还有第三种硬件中断方式：
例外。至少，我也会检查页面错误。
对于上面遗漏的 NMI（通过 nmi:nmi_handler）。
为了方便起见，我整理了一个 little piece of code
在基准测试代码路径中跟踪 IRQ。请参阅随附的 example.c
用法。请注意，需要访问 /sys/kernel/debug 才能
确定跟踪点 ID。
我知道有两种 "fast" 在 x86 上观察中断的方法，第一种是我自己使用的。
您可以使用用户空间 rdpmc 直接读取 hw_interrupts.received 事件，在您测试的部分之前和之后，以确定是否有任何中断发生。为了首先对计数器进行编程并处理读取，我列出了一些库 。如果我现在要开始一个新项目，我可能会使用 pmu-tools，或者直接使用 perf_event_open，因为它并不是那么难以实现。
在您的计时区域之前将 %fs 或 %gs 设置为非零值，然后检查该值在之后是否不变。如果它已被设置回零，则会发生中断，因为 iret 指令会重置这些寄存器。在 x86-64 上，您最好使用 %gs，因为 %fs 用于线程本地存储。完整的细节 in this blog post，这是我了解到它的地方。
我正在开发 low level routines for binary search in C 和 x64 程序集，并尝试测量搜索未缓存数组（RAM 中的数据）的确切执行时间。根据 "lucky" 分支预测的方式，为不同的目标搜索相同的数组所花费的时间差异很大。我可以准确地测量最小和中值执行时间，但我发现很难测量最大执行时间。
问题是分支预测的最坏情况在时间上与平均情况加上处理器中断相当。最坏情况和中断都很少见，但我还没有想出一个好方法来区分一个罕见事件和另一个。标准方法是简单地过滤掉所有 "anomalously" 高测量值，但这只有在两者之间有明确界限的情况下才有效。
所以问题就变成了，“我如何区分被中断的测量和比其他测量花费更长的时间的测量？”
或者更一般地说，“如何在不预先假设硬最大值的情况下测量执行时间的完整分布？”
内核是否存储了任何我可以查询的有关是否发生中断的信息？我可以在测量前后查询的东西会告诉我测量是否中断？理想情况下，它会告诉我中断花费了多长时间的周期，但仅仅知道测量受到影响将是一个很好的开始。
也许除了（或代替）RDTSC，我可以使用 RDPMC 读取一个计数器，该计数器测量在 Ring 0（内核）而不是 Ring 3（用户）中花费的周期数？是否已经设置了一个计数器来执行此操作，还是我需要设置自己的？我需要创建自己的内核模块来执行此操作，还是可以使用现有的 ioctl？
一些背景：
我主要 运行 运行 Ubuntu 14.03 Linux 4.2.0 在 Intel Skylake i7-6700 上，但我也在 Intel Sandy Bridge 和哈斯韦尔。我已经尽力减少系统上的抖动。我用 CONFIG_NOHZ_FULL 重新编译了一个 tickless 内核，没有强制抢占，透明大页面支持关闭，定时器频率为 100 Hz。
我已经停止了大部分不必要的进程，并删除了大部分不必要的内核模块。我正在使用 cpuset / cset shield 为单个进程保留一个 NoHZ 内核，并使用 kernel/debug/tracing 来验证我得到的中断很少。但我仍然得到足够的精确测量是困难的。也许更重要的是，我可以设想未来的长尾情况（很少需要调整大小的哈希 table），在这种情况下，能够区分有效和无效测量将非常有帮助
我正在使用 Intel suggests in their whitepaper 的技术测量 RDTSC/RDTSCP 的执行时间，并且总体上获得了我期望的准确性。我的测试涉及搜索 16 位值，并且我对长度可变的随机数组的 65536 次可能搜索中的每一次重复和单独计时。为了防止处理器学习正确的分支预测，每次都以不同的顺序重复搜索。每次使用 "CLFLUSH".
搜索后，搜索到的数组将从缓存中删除这是一个研究项目，我的目标是了解这些问题。因此，我愿意采用在其他情况下可能被认为愚蠢和极端的方法。自定义内核模块、保护模式 x64 程序集、未经测试的内核修改和处理器特定功能都是公平的游戏。如果有办法摆脱剩余的少数中断，使所有测量结果为 "real"，那也可能是一个可行的解决方案。感谢您的建议！
我假设您已经在一定程度上屏蔽了基准测试线程 可能：
- 它可以独占访问其 CPU 核心（不仅是 HyperThread），参见 here 关于如何轻松管理它。
- 中断相关性已从该核心移开，请参阅 here
- 如果可能，运行 一个
nohz内核以最小化计时器滴答声。
此外，你不应该从你的内部跳入内核 space 基准代码路径：在 return 后，您的线程可能会被调度 离开一段时间。
但是，您根本无法消除 CPU 内核上的所有中断：on Linux，本地APIC定时器中断，处理器间中断 (IPI) 和其他用于内部目的，你根本不能 摆脱他们！例如，定时器中断用于确保， 线程最终得到调度。同样，IPI 用于 触发其他核心的动作，例如 TLB 击落。
现在，由于 Linux 跟踪基础设施，可以从用户space 判断一个 hardirq在某段时间发生了。
一个小问题是 Linux 处理两个 类 中断 在追踪方面有所不同：
- 首先是"real"个外部硬件中断被占用 网络适配器、声卡等真实设备。
- 有Linux内部使用的中断。
从处理器异步的意义上说，两者都是硬中断 将控制转移到中断服务例程 (ISR)，由 中断描述符 table (IDT).
通常，在 Linux 中，ISR 只是一个用汇编语言编写的存根，它 将控制转移到用 C 编写的高级处理程序。
有关详细信息，请参阅 Linux 内核源代码中的 arch/x86/entry_entry_64.S。
对于 Linux-internal 中断，每个都定义了一个跟踪存根
而对于外部中断，tracing留给高层
中断处理程序。
这是每个内部中断都有一个跟踪事件的方式：
# sudo perf list | grep irq_vectors:
irq_vectors:call_function_entry [Tracepoint event]
irq_vectors:call_function_exit [Tracepoint event]
irq_vectors:call_function_single_entry [Tracepoint event]
irq_vectors:call_function_single_exit [Tracepoint event]
irq_vectors:deferred_error_apic_entry [Tracepoint event]
irq_vectors:deferred_error_apic_exit [Tracepoint event]
irq_vectors:error_apic_entry [Tracepoint event]
irq_vectors:error_apic_exit [Tracepoint event]
irq_vectors:irq_work_entry [Tracepoint event]
irq_vectors:irq_work_exit [Tracepoint event]
irq_vectors:local_timer_entry [Tracepoint event]
irq_vectors:local_timer_exit [Tracepoint event]
irq_vectors:reschedule_entry [Tracepoint event]
irq_vectors:reschedule_exit [Tracepoint event]
irq_vectors:spurious_apic_entry [Tracepoint event]
irq_vectors:spurious_apic_exit [Tracepoint event]
irq_vectors:thermal_apic_entry [Tracepoint event]
irq_vectors:thermal_apic_exit [Tracepoint event]
irq_vectors:threshold_apic_entry [Tracepoint event]
irq_vectors:threshold_apic_exit [Tracepoint event]
irq_vectors:x86_platform_ipi_entry [Tracepoint event]
irq_vectors:x86_platform_ipi_exit [Tracepoint event]
而外部中断只有一个通用跟踪事件：
# sudo perf list | grep irq:
irq:irq_handler_entry [Tracepoint event]
irq:irq_handler_exit [Tracepoint event]
irq:softirq_entry [Tracepoint event]
irq:softirq_exit [Tracepoint event]
irq:softirq_raise [Tracepoint event]
因此，在基准测试期间跟踪所有这些 IRQ *_entries
代码路径，你就知道你的基准测试样本是否中毒了
是否通过 IRQ。
注意x86上还有第三种硬件中断方式：
例外。至少，我也会检查页面错误。
对于上面遗漏的 NMI（通过 nmi:nmi_handler）。
为了方便起见，我整理了一个 little piece of code
在基准测试代码路径中跟踪 IRQ。请参阅随附的 example.c
用法。请注意，需要访问 /sys/kernel/debug 才能
确定跟踪点 ID。
我知道有两种 "fast" 在 x86 上观察中断的方法，第一种是我自己使用的。
您可以使用用户空间
rdpmc直接读取hw_interrupts.received事件，在您测试的部分之前和之后，以确定是否有任何中断发生。为了首先对计数器进行编程并处理读取，我列出了一些库pmu-tools，或者直接使用perf_event_open，因为它并不是那么难以实现。在您的计时区域之前将
%fs或%gs设置为非零值，然后检查该值在之后是否不变。如果它已被设置回零，则会发生中断，因为iret指令会重置这些寄存器。在 x86-64 上，您最好使用%gs，因为%fs用于线程本地存储。完整的细节 in this blog post，这是我了解到它的地方。