LWN：更好地选择CPU来处理到期timer！
关注了就能看到更多这么棒的文章哦～
Better CPU selection for timer expiration
By Jonathan Corbet
November 7, 2022
DeepL assisted translation
https://lwn.net/Articles/913568/
从表面上看，内核内部的 timer 机制在很长一段时间内似乎没有什么变动。最核心的那些 API 看起来与 1.0 版本中的 API 很相似。其实在这个 API 里面，这些年已经增加了不少复杂的实现细节。如果 Anna-Maria Behnsen 的这个 patch set 进入 mainline 的话，那么这个 API 的实现就会变得更加复杂，但速度可以更快。
Premature optimization
先介绍一下背景，需要注意，内核实际上有两组 core API 用于管理内部 timer。其中高分辨率计时器（hrtimers，high-resolution timers）的功能正如其名称所说，用在对精度要求很高的近期会发生的 event 上；它们的开销相对比较大，只在必要时使用。对于其他一切情况，都在使用另一个子系统，也就是 "kernel timer"（或有时称为 "timer-wheel timers"），主要是 add_timer()等函数。Behnsen 的 patch set 改变了这些普通的 kernel timer 的工作方式。
可以说，大多数使用 kernel timer 的情况，都是用来在某个预期应该发生的 event 没有出现时确保 kernel 仍会给出正确响应的情况下。某个驱动程序可能会在设备上触发一个 I/O 操作，虽然它知道设备会在操作完成后上报一个中断，不过仍然会设置一个 timer，这样，如果硬件设备走神了，这个操作也不会无限期地 hang 在那里。内核的其他一些部分，例如 networking 子系统，也在以类似的方式使用 timer。
这种使用模式产生了一些有趣的影响。其中之一是，这些 timer 并不需要在其规定的到期时刻到期；如果内核等了一小段时间之后才来处理这个到期的 timer，也不是什么大问题。这就使得内核可以批量处理这些到期的 timer 了，就能通过推迟处理来避免唤醒原本闲置的 CPU。不过这里有一个隐含的信息，kernel timer 很少会过期。毕竟一切都运行正常时，预期的 event 会正常触发，于是 timer 就会被取消或 reset 到未来的某个时刻。因此，timer 子系统应该针对 timer event 的创建和取消动作来进行优化。事实上，这方面的优化已经做了很多了，从 LWN 的 2004 年的报道中都可以看出有一个持续到了 2015 年的对 timer 的重大重构。
不过，Behnsen 发现了一个可以进一步优化的地方。当在当前内核中设置一个 timer 时，timer 子系统会花费一些 CPU 时间来判断哪个 CPU 应该被用来处理该定时器的到期事件。这个动作是为了能将这项工作安排在已经有事情在做的 CPU 上，而不是白白唤醒一个空闲的 CPU 来处理这个 timer 事件。因此，timer 子系统会在系统中扫描，寻找合适的 CPU，从而将 timer 添加到对应的队列中。
不过，这种算法有几个问题。其中之一是，现在很忙的 CPU 在 timer 过期时可能就不再繁忙了。因此，如果在设置定时器时选择一个 CPU 来处理 timer 过期事件，实际上纯粹是基于猜测的。更糟糕的是，这项工作是在错误的时间进行的，因为大多数 timer 都不会到期，所以这些提前来选择处理相应事件的 CPU 的努力，都可能被浪费掉，哪怕猜测对了。最好的办法就是在设置 timer 时不做任何额外工作，而让一个在 timer 实际上到期时在繁忙的 CPU 来处理这个事件，这样就只有在比较少见的情况下（timer 过期）来付出代价了。
第一部分（在设置 timer 时不选择到时候处理此事件的 CPU）很容易实现；timer 直接放入当前设置它的 CPU 的队列中就好。不过，要选择一个合适的 CPU 来实际处理过期事件是比较困难的。如果不加思考，可能就直接创建一个普通的 timer 队列，正在干活的 CPU 会偶尔过检查一下这个队列，来处理到期事件。这会产生大量的 lock contention 以及 cache-line 的来回切换，这样会导致哪怕没有 timer 需要处理，也会付出不必要的开销。所以需要更复杂的实现。
Choosing the expiration CPU
这里所选择的方案是将系统的 CPU 组织成一个类似于硬件拓扑结构的层级结构，但又不完全一样。在最下面一级，CPU 按最多 8 个的标准来组合成一些 group，要求他们所有都必须是属于同一个 NUMA 节点中的。这些 group 本身也被合并成 group；这个过程一直持续到系统中的所有 CPU 都被排列成一个树状结构。
[CPU 组的组织]
例如，假设一个简单情况，也就是 4 CPU 的一个系统，按照两个 NUMA 节点来分布，如上图所示。前两个 CPU 被放到第 1 组；另外两个，因为它们在另一个 NUMA 节点中，所以就放到了另一组。这两组又被放在一起，成为第 3 组。如果系统更大、更复杂的话，组合完毕之后可能会有更多 group，但就比较难画成一个简化示意图了。
timer API 可以把 timer 指定在特定的 CPU 上；这在重新实现的版本中没有改变。每个 CPU 都必须处理固定在这里的 timer 的到期事件，哪怕这意味着自己需要被从 idle 状态唤醒。不过，大多数 timer 都可以在系统中的任何一个 CPU 上执行，并没有指定 CPU；对这些 "全局"性质的 timer 的处理会跟以前不一样。忙碌的 CPU 将继续处理它的队列中的全局 timer，但是，如果该 CPU 进入了 idle 状态，就会把它的即将到期的全局 timer 添加到它所属的 group 的队列中。
通常来说，每个 CPU group 都会指定一个成员来作为 "migrator，迁移者"。该 CPU 应该不是 idle CPU，它会需要时不时地检查与其 group 相关的队列中即将到期的全局 timer；如果某个 timer 队列对应的 CPU 仍然是 idle，那么这个 migrator CPU 会把这个 timer 取过来，代替该 CPU 处理到期的 timer，那个 CPU 就可以继续保持 idle 了。因此，举例来说，如果上图中的 CPU 1 是 idle 的，它就会把即将到期的全局 timer 排在 Group 1 上；如果 CPU 2 在运行状态（因此它就是 migrator），它就会在该 timer 到期时完成处理。
如果 migrator 闲置了，那么该 group 中的另一个 CPU 就必须接过这个职责，成为新的 migrator；这只需要在该 group 中找到下一个正在忙碌的 CPU 就好。如果其他的 CPU 也都 idle 了，那么这个 group 最终就没有 migrator 了。在这种情况下，这个 group 的会在更高一级的 group 中标记为 idle 状态，其第一个到期的 timer 也会在更高一级的 group 中排队了。所以，如果 CPU 2 也空闲下来，它就会把 Group 1 中最早到期的 event，放到 Group 3 的队列中。
migrator 角色的分配也会在更高一级的 group 中进行。如果一个 group 包含了其他 group，那么就会从中挑选一个作为这一层的 migrator。按我们这里描述的场景来说，Group 2 将是 Group 3 的 migrator。 因此，在 Group 2 中作为 migrator 来运行的 CPU（CPU 3 或 CPU 4）也必须处理 Group 3 的 timer event。如果这个系统中有很多 idle CPU，那么这个 migrator 角色可以一直传递到这个层级结构的最顶端，这时就会由一个 CPU 来负责处理系统中所有即将到期的 timer。
如果这个 CPU 也 idle 了下来，那么系统就会完全没有任何可用的 migrator CPU 了。此时，最后一个 CPU 会按照最早会到期的 timer 的时间来设置一个硬件 timer 唤醒自己。这就保证了即使在没有正在工作的 CPU 来处理 timer 事件时，也不会完全没有人处理。
在 timer 子系统中实现这一机制的 patch，在 core kernel 子系统中增加了近 2000 行代码。这项工作带来的好处据说是增加和删除一个 timer 所需的时间减少了大约 25%。由于在一些对性能要求很高的代码中也可能会要设置 timer 或者改变 timer，所以这个改动的好处应该值得付出这些复杂性增加的代价。
这项工作的另一个好处是，应该可以删除掉 deferrable timer（可推后处理的 timer） 机制了。deferrable timer 是指那些可以延后处理而没有任何不良影响的 timer；某个正在 idle 状态的 CPU 不会仅仅为了处理一个 deferrable timer 事件而被唤醒。将 deferrable timer 变成全局 timer 将产生同样的效果，都不会再导致 sleep 状态的 CPU 被专门唤醒，因此不再需要对 deferrable timer 进行特殊处理了。据 Behnsen 称，deferrable timer 移除工作也在进行中，这就可以部分抵消当前这个 patch 所增加的复杂性。
全文完
LWN 文章遵循 CC BY-SA 4.0 许可协议。
长按下面二维码关注，关注 LWN 深度文章以及开源社区的各种新近言论～