hrtimers - 高分辨率内核定时器子系统

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

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

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

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

  • 在定时器轮之上实现的当前 posix 定时器子系统已经引入了对 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-timer 的处理更简单。

hrtimers 的锁定和每个 CPU 的行为主要取自现有的定时器轮代码，因为它已经成熟且非常适用。由于数据结构不同，共享代码实际上没有优势。此外，hrtimer 函数现在具有更清晰的行为和更清晰的名称 - 例如 hrtimer_try_to_cancel() 和 hrtimer_cancel() [它们大致等效于 timer_delete() 和 timer_delete_sync()] - 因此它们在算法级别上没有直接的 1:1 映射，因此也没有真正的代码共享潜力。

基本数据类型：每个时间值，无论是绝对值还是相对值，都使用特殊的纳秒分辨率 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