174 lines · plain
1======================================================2hrtimers - subsystem for high-resolution kernel timers3======================================================4 5This patch introduces a new subsystem for high-resolution kernel timers.6 7One might ask the question: we already have a timer subsystem8(kernel/timers.c), why do we need two timer subsystems? After a lot of9back and forth trying to integrate high-resolution and high-precision10features into the existing timer framework, and after testing various11such high-resolution timer implementations in practice, we came to the12conclusion that the timer wheel code is fundamentally not suitable for13such an approach. We initially didn't believe this ('there must be a way14to solve this'), and spent a considerable effort trying to integrate15things into the timer wheel, but we failed. In hindsight, there are16several reasons why such integration is hard/impossible:17 18- the forced handling of low-resolution and high-resolution timers in19 the same way leads to a lot of compromises, macro magic and #ifdef20 mess. The timers.c code is very "tightly coded" around jiffies and21 32-bitness assumptions, and has been honed and micro-optimized for a22 relatively narrow use case (jiffies in a relatively narrow HZ range)23 for many years - and thus even small extensions to it easily break24 the wheel concept, leading to even worse compromises. The timer wheel25 code is very good and tight code, there's zero problems with it in its26 current usage - but it is simply not suitable to be extended for27 high-res timers.28 29- the unpredictable [O(N)] overhead of cascading leads to delays which30 necessitate a more complex handling of high resolution timers, which31 in turn decreases robustness. Such a design still leads to rather large32 timing inaccuracies. Cascading is a fundamental property of the timer33 wheel concept, it cannot be 'designed out' without inevitably34 degrading other portions of the timers.c code in an unacceptable way.35 36- the implementation of the current posix-timer subsystem on top of37 the timer wheel has already introduced a quite complex handling of38 the required readjusting of absolute CLOCK_REALTIME timers at39 settimeofday or NTP time - further underlying our experience by40 example: that the timer wheel data structure is too rigid for high-res41 timers.42 43- the timer wheel code is most optimal for use cases which can be44 identified as "timeouts". Such timeouts are usually set up to cover45 error conditions in various I/O paths, such as networking and block46 I/O. The vast majority of those timers never expire and are rarely47 recascaded because the expected correct event arrives in time so they48 can be removed from the timer wheel before any further processing of49 them becomes necessary. Thus the users of these timeouts can accept50 the granularity and precision tradeoffs of the timer wheel, and51 largely expect the timer subsystem to have near-zero overhead.52 Accurate timing for them is not a core purpose - in fact most of the53 timeout values used are ad-hoc. For them it is at most a necessary54 evil to guarantee the processing of actual timeout completions55 (because most of the timeouts are deleted before completion), which56 should thus be as cheap and unintrusive as possible.57 58The primary users of precision timers are user-space applications that59utilize nanosleep, posix-timers and itimer interfaces. Also, in-kernel60users like drivers and subsystems which require precise timed events61(e.g. multimedia) can benefit from the availability of a separate62high-resolution timer subsystem as well.63 64While this subsystem does not offer high-resolution clock sources just65yet, the hrtimer subsystem can be easily extended with high-resolution66clock capabilities, and patches for that exist and are maturing quickly.67The increasing demand for realtime and multimedia applications along68with other potential users for precise timers gives another reason to69separate the "timeout" and "precise timer" subsystems.70 71Another potential benefit is that such a separation allows even more72special-purpose optimization of the existing timer wheel for the low73resolution and low precision use cases - once the precision-sensitive74APIs are separated from the timer wheel and are migrated over to75hrtimers. E.g. we could decrease the frequency of the timeout subsystem76from 250 Hz to 100 HZ (or even smaller).77 78hrtimer subsystem implementation details79----------------------------------------80 81the basic design considerations were:82 83- simplicity84 85- data structure not bound to jiffies or any other granularity. All the86 kernel logic works at 64-bit nanoseconds resolution - no compromises.87 88- simplification of existing, timing related kernel code89 90another basic requirement was the immediate enqueueing and ordering of91timers at activation time. After looking at several possible solutions92such as radix trees and hashes, we chose the red black tree as the basic93data structure. Rbtrees are available as a library in the kernel and are94used in various performance-critical areas of e.g. memory management and95file systems. The rbtree is solely used for time sorted ordering, while96a separate list is used to give the expiry code fast access to the97queued timers, without having to walk the rbtree.98 99(This separate list is also useful for later when we'll introduce100high-resolution clocks, where we need separate pending and expired101queues while keeping the time-order intact.)102 103Time-ordered enqueueing is not purely for the purposes of104high-resolution clocks though, it also simplifies the handling of105absolute timers based on a low-resolution CLOCK_REALTIME. The existing106implementation needed to keep an extra list of all armed absolute107CLOCK_REALTIME timers along with complex locking. In case of108settimeofday and NTP, all the timers (!) had to be dequeued, the109time-changing code had to fix them up one by one, and all of them had to110be enqueued again. The time-ordered enqueueing and the storage of the111expiry time in absolute time units removes all this complex and poorly112scaling code from the posix-timer implementation - the clock can simply113be set without having to touch the rbtree. This also makes the handling114of posix-timers simpler in general.115 116The locking and per-CPU behavior of hrtimers was mostly taken from the117existing timer wheel code, as it is mature and well suited. Sharing code118was not really a win, due to the different data structures. Also, the119hrtimer functions now have clearer behavior and clearer names - such as120hrtimer_try_to_cancel() and hrtimer_cancel() [which are roughly121equivalent to timer_delete() and timer_delete_sync()] - so there's no direct1221:1 mapping between them on the algorithmic level, and thus no real123potential for code sharing either.124 125Basic data types: every time value, absolute or relative, is in a126special nanosecond-resolution 64bit type: ktime_t.127(Originally, the kernel-internal representation of ktime_t values and128operations was implemented via macros and inline functions, and could be129switched between a "hybrid union" type and a plain "scalar" 64bit130nanoseconds representation (at compile time). This was abandoned in the131context of the Y2038 work.)132 133hrtimers - rounding of timer values134-----------------------------------135 136the hrtimer code will round timer events to lower-resolution clocks137because it has to. Otherwise it will do no artificial rounding at all.138 139one question is, what resolution value should be returned to the user by140the clock_getres() interface. This will return whatever real resolution141a given clock has - be it low-res, high-res, or artificially-low-res.142 143hrtimers - testing and verification144-----------------------------------145 146We used the high-resolution clock subsystem on top of hrtimers to verify147the hrtimer implementation details in praxis, and we also ran the posix148timer tests in order to ensure specification compliance. We also ran149tests on low-resolution clocks.150 151The hrtimer patch converts the following kernel functionality to use152hrtimers:153 154 - nanosleep155 - itimers156 - posix-timers157 158The conversion of nanosleep and posix-timers enabled the unification of159nanosleep and clock_nanosleep.160 161The code was successfully compiled for the following platforms:162 163 i386, x86_64, ARM, PPC, PPC64, IA64164 165The code was run-tested on the following platforms:166 167 i386(UP/SMP), x86_64(UP/SMP), ARM, PPC168 169hrtimers were also integrated into the -rt tree, along with a170hrtimers-based high-resolution clock implementation, so the hrtimers171code got a healthy amount of testing and use in practice.172 173 Thomas Gleixner, Ingo Molnar174