使用 WITCH 来观察系统的无效处理

最近看了一篇 Paper - Watching for Software Inefficiencies with Witch，觉得作者排查性能问题的思路很不错，这里记录一下。

什么是无效处理

对于性能调优来说，我们会关注很多指标，这里，WITCH 主要关注的是系统的 infficiencies，也就是无效的处理。通常的无效处理可能包括：

• 计算了一个不会被使用的结果
• 重复计算了某一个结果
• 无效的数据移动
• 过分的同步

大家都知道，无效处理会对系统性能造成影响，我们需要尽量避免。虽然现在编译器在很多时候都能对代码做很多优化，但仅仅靠编译器是不够的，我们还需要其他的方法来检查发现系统无效处理的地方。

WITCH 的设计与实现

要排查系统性能问题，对我来说，最先想到的就是使用 perf 这类型的工具，但无论是 perf 还是 vtune，它们都是基于采样的，是一种 Coarse-grained profiler，虽然对系统影响较小，但并不精确，在一些情况下面其实并不能很好的发现无效处理。

另一种就是 Fine-grained profiler，譬如 DeadSpy，它们会详细的分析动态指令，从而发现无效处理，但也会给系统造成非常大的负担，是的系统性能下降。

而对于 WITCH 来说，它融合了 Coarse-grained 和 Find-grained，核心想法就是先用 PUMs 对系统进行采样，然后使用 hardware debug registers 来给采样的地址加上断点，当后续系统访问到这些地址的时候，触发对应的判断程序，看是否是无效处理。

WITCH 的原理非常简单，但要做好，其实还需要处理很多问题。在继续开始之前，我们可以先简单介绍一下系统调优里面一些背景知识。

常用术语

• Hardware Performance Monitoring Units

  也就是通常说的 PMU。现代的 CPU 都会提供很多硬件事件的计数器，譬如 loads，stores，CPU cycles 等。当计数器的值超过了一个阈值之后，PMU 就会触发一个溢出中断，这个中断就会被 profiler（譬如 perf）给捕捉到并且处理。

• Hardware Debug Registers

  Hardware debug registers 其实就可以认为是我们在用 gdb 调试的时候设置的断点。当程序的 Program counter (PC) 运行到某一个地址或者是一条指令访问到了一个特定的地址，hardware debug registers 就会捕获 CPU 的执行。在现代的 x86 架构中，通常有 4 个 debug registers。

• Linux Perf events_

  Linux 提供了一套标准的接口用来对 PMU 进行采用和编程，主要使用的是 perf_event_open 和相关的 ioctl 调用。当 PMU 的事件溢出之后，Linux 内核会给相关的线程发送信号，并且将取样的 PMU 数据追加到一个循环 buffer 里面。

• Call Path Profiling

  当对应事件触发的时候，我们能通过 Call path profiling 拿到当前的 calling context，也就是整个事件的调用链。一个 calling context 从入口函数（譬如 main 或者线程开始函数）的 instruction pointer (IP) 开始，然后到触发这个事件的指令这里结束。

• Watchpoint

  Watchpoint 就是类似于 gdb 里面的断点设置。我们可以设置 write W_TRAP 以及 read-or-write RW_TRAP。

例子

这里我们用 WITCH 的 DeadCraft 来说明下 WITCH 是如何工作的，DeadCraft 主要是用来检查 dead store。所谓 dead store，就是当我们给一个地址设置了一个值，然后马上又用一个新的值在同样的地址设置了，那么这个就是 dead store。如果我们设置了一个值，但后面马上就 load 读取了，这个就不是 dead store。

上面是 WITCH 用来检查 dead store 的流程：

1. PMU store event 的计数器溢出，触发中断
2. WITCH 捕获到了信号，得到 calling context C-watch 以及地址 M，跟 AccessType 合成一个 tuple <C-watch, M, AccessType> 发送给 DeadCraft
3. DeadCraft 让 WITCH 去监控后续对地址 M 的 load 或者 store
4. WITCH 给设置一个 RW_TRAP 的 watchpoint
5. 后续程序访问到 M，watchpoint 捕获
6. WITCH 处理，得到 calling context C-trap，并且将 <C-trap, M, AccessType> 给 DeadCraft
7. 如果 AccessType 是 store，那么 DeadCraft 就认为这个是一个 dead store，并且将这次 dead store 设置为 <C-watch, C-trap>

实现

上面说到了 WITCH 一个简单的例子，这里说下 WITCH 是如何实现的， WITCH 主要是基于 HPCToolkit，主要有：

• PMU Sampling : 在 Intel CPU 上，主要设置 MEM_UOPS_RETIRED:ALL_STORES 和 MEM_UOPS_RETIRED:ALL_LOADS Registration
• Watchpoint : WITCH 会自动确定机器上面的 hardware debug registers，使用 Linux perf_event 接口去注册一个 watchpoint 事件 HW_BREAKPOINT。WITCH 会注册一个 signal handler 去捕获 watchpoint 抛出的异常。WITCH 也会把采样周期设置为 1 ，用来保证只要访问到了监控的内存就会跑出异常，被 WITCH 捕获。
• Precise PC : 当 watchpoint 触发的时候，其实在 signal handler 里面得到的 PC（Context PC） 并不是当前触发中断的 PC （Precise PC），而是在 Precise PC 之前的一条指令。WITCH 使用 Last Branch Record （LBR）来得到 precise PC。
• Fast Watchpoint Replacement : WITCH 需要经常的关闭 watchpoint，并且关掉所有跟这些 watchpoint 相关的内核资源，WITCH 给 perf_event ioctl 接口加了个 PERF_EVENT_IOC_MODIFY_ATTRIBUTES。
• Stack Addresses : WITCH 会用 sigaltstack 机制来用一个额外的 signal stack 处理 PMU 以及 watchpoint 的 signal。

挑战

上面整个流程看起来是很简单，但实际还是有很多困难需要克服的，最大的困难就是采样其实并不是精确的。譬如如下的例子：

1: for (int i = 1; i <= 100K; i++) {
2:  arrya[i] = 0;
3: }
4: for (int j = 1; j <= 100K; j++) {
5:  arrya[j] = j;
6: }

假设采样周期是 10K，我们就只有一个 hardware debug register，那么 WITCH 会在第一个 array[10K] 的时候设置一个 watchpoint，然后在 array[20K] 会有第二次采样，但这时候已经没有空间设置 watchpoint 了。

如果采用最通常的做法，后面的替换掉最老的，这个是不能工作的。譬如当我们在第一个循环最后 array[100K] 设置了 watchpoint 之后，下一个在第二个循环 array[10K] 会覆盖掉之前的，但这时候其实是没法发现 dead store 的。为了解决这个问题，WITCH 引入概率机制来决定对于某一次采样，是否需要设置 watchpoint。

假设系统有 N 个 debug register，对于第 k 次采样，k > N，按照 N / k 的概率替换掉 N 里面的一个 watchpoint。也就是说，任何采样都有 N / k 的概率来被监控到。只要 watchpoint 被处罚，概率就被重置为 1。具体的推导可以详细参考 paper。当然，paper 里面还说了其他很多的困难，这里就不一一说明了。

小结

总的来说，WITCH 的思路还是挺不错的，Paper 作者也通过它来找到了一些软件中的无效处理。我也在 Github 上面找到了 WITCH ，本来想试试，看能不能找找 TiKV 中的无效处理，但一看安装说明，需要装一个定制版本的 Linux，就只好先打消了这个念头，后面在尝试吧。如果你对这块很感兴趣，想在 TiKV 里面试试，欢迎联系我 tl@pingcap.com。