hrtimers - 高精度内核定时器子系统

此补丁引入了一个新的高精度内核定时器子系统。

人们可能会问：我们已经有一个定时器子系统（kernel/timers.c），为什么还需要两个定时器子系统？在多次尝试将高分辨率和高精度功能集成到现有定时器框架中，并实践测试了各种此类高分辨率定时器实现后，我们得出结论，定时器轮代码从根本上不适合这种方法。我们最初不相信这一点（‘一定有办法解决’），并花费了大量精力试图将这些功能集成到定时器轮中，但我们失败了。事后看来，这种集成之所以困难/不可能有几个原因：

  • 强制以相同方式处理低分辨率和高分辨率定时器会导致大量的折衷、宏魔法和 #ifdef 混乱。timers.c 代码围绕 jiffies 和 32 位假设“紧密编码”，多年来为相对狭窄的用例（jiffies 在相对狭窄的 HZ 范围内）进行了磨练和微优化——因此，即使是小的扩展也容易破坏轮的概念，导致更糟糕的折衷。定时器轮代码非常好且紧凑，在当前使用中没有任何问题——但它根本不适合扩展用于高分辨率定时器。

  • 级联的不可预测 [O(N)] 开销导致延迟，这需要更复杂地处理高分辨率定时器，进而降低了鲁棒性。这种设计仍然会导致相当大的计时不准确性。级联是定时器轮概念的基本属性，它无法被“设计”掉，否则将不可避免地以不可接受的方式降低 timers.c 代码的其他部分的性能。

  • 当前基于定时器轮的 posix-timer 子系统实现，已经引入了相当复杂的处理，用于在 settimeofday 或 NTP 时间点对绝对 CLOCK_REALTIME 定时器进行必要的重新调整——这进一步通过示例支持了我们的经验：定时器轮数据结构对于高分辨率定时器来说过于僵化。

  • 定时器轮代码最适用于可识别为“超时”的用例。此类超时通常用于覆盖各种 I/O 路径中的错误情况，例如网络和块 I/O。绝大多数此类定时器从未过期，也很少重新级联，因为预期的正确事件及时到达，因此可以在需要进一步处理它们之前将其从定时器轮中移除。因此，这些超时的用户可以接受定时器轮的粒度和精度权衡，并且很大程度上期望定时器子系统具有接近零的开销。对于它们而言，精确计时不是核心目的——事实上，大多数使用的超时值都是临时性的。对于它们来说，保证实际超时完成的处理最多是一种必要的恶，因此应该尽可能便宜和无侵入性（因为大多数超时在完成之前就被删除了）。

精确定时器的主要用户是利用 nanosleep、posix-timers 和 itimer 接口的用户空间应用程序。此外，内核内部用户，如需要精确计时事件（例如多媒体）的驱动程序和子系统，也可以从单独的高分辨率定时器子系统的可用性中受益。

尽管此子系统尚未提供高分辨率时钟源，但 hrtimer 子系统可以轻松扩展以支持高分辨率时钟功能，并且相关补丁已存在并正在迅速成熟。对实时和多媒体应用程序以及精确定时器其他潜在用户的日益增长的需求，是分离“超时”和“精确定时器”子系统的另一个原因。

另一个潜在好处是，这种分离允许对现有定时器轮进行更多特殊目的优化，以满足低分辨率和低精度用例的需求——一旦精度敏感的 API 从定时器轮中分离并迁移到 hrtimers。例如，我们可以将超时子系统的频率从 250 Hz 降低到 100 HZ（甚至更小）。

hrtimer 子系统实现细节

基本设计考虑因素是

  • 简单性

  • 数据结构不限于 jiffies 或任何其他粒度。所有内核逻辑都以 64 位纳秒分辨率工作——没有折衷。

  • 简化现有与计时相关的内核代码

另一个基本要求是在激活时立即将定时器排队并排序。在考察了基数树和哈希表等几种可能的解决方案后，我们选择了红黑树作为基本数据结构。红黑树作为库在内核中可用，并用于内存管理和文件系统等各种性能关键领域。红黑树仅用于时间排序，而一个单独的列表用于使过期代码快速访问排队的定时器，而无需遍历红黑树。

（这个独立的列表在以后引入高分辨率时钟时也很有用，届时我们需要独立的待处理和已过期队列，同时保持时间顺序不变。）

然而，按时间顺序入队并非纯粹为了高分辨率时钟，它也简化了基于低分辨率 CLOCK_REALTIME 的绝对定时器的处理。现有实现需要维护一个包含所有已设置的绝对 CLOCK_REALTIME 定时器的额外列表，并涉及复杂的锁定。在 settimeofday 和 NTP 的情况下，所有定时器 (!) 都必须出队，时间更改代码必须逐一修复它们，然后将它们全部重新入队。按时间顺序入队以及以绝对时间单位存储过期时间，从 posix-timer 实现中移除了所有这些复杂且扩展性差的代码——时钟可以简单地设置，而无需触及红黑树。这也使 posix-timers 的处理在总体上更简单。

hrtimers 的锁定和每 CPU 行为大部分借鉴了现有的定时器轮代码，因为它成熟且适用。由于数据结构不同，共享代码实际上并没有带来优势。此外，hrtimer 函数现在具有更清晰的行为和名称——例如 hrtimer_try_to_cancel() 和 hrtimer_cancel() [它们大致等同于 timer_delete() 和 timer_delete_sync()]——因此在算法层面它们之间没有直接的一一映射，也就没有真正的代码共享潜力。

基本数据类型：所有时间值，无论是绝对时间还是相对时间，都以特殊的纳秒分辨率 64 位类型表示：ktime_t。（最初，ktime_t 值及其操作的内核内部表示通过宏和内联函数实现，并且可以在“混合联合”类型和纯“标量”64 位纳秒表示之间切换（在编译时）。这在 Y2038 工作中被放弃了。）

hrtimers - 定时器值舍入

hrtimer 代码会将定时器事件舍入到较低分辨率的时钟，因为它必须这样做。否则，它将完全不进行人工舍入。

一个问题是，clock_getres() 接口应该向用户返回什么样的分辨率值。它将返回给定计时器所拥有的实际分辨率——无论是低分辨率、高分辨率还是人为设定的低分辨率。

hrtimers - 测试与验证

我们使用了基于 hrtimers 的高分辨率时钟子系统来验证 hrtimer 的实际实现细节，并且还运行了 posix 定时器测试以确保符合规范。我们还在低分辨率时钟上运行了测试。

hrtimer 补丁将以下内核功能转换为使用 hrtimers

  • nanosleep

  • itimers

  • posix-timers

nanosleep 和 posix-timers 的转换使得 nanosleep 和 clock_nanosleep 的统一成为可能。

代码已成功编译到以下平台

i386, x86_64, ARM, PPC, PPC64, IA64

代码已在以下平台进行了运行测试

i386(UP/SMP), x86_64(UP/SMP), ARM, PPC

hrtimers 也被集成到 -rt 树中，以及基于 hrtimers 的高分辨率时钟实现，因此 hrtimers 代码在实践中得到了大量的良好测试和使用。

Thomas Gleixner, Ingo Molnar