251 lines · plain
1=====================================================2High resolution timers and dynamic ticks design notes3=====================================================4 5Further information can be found in the paper of the OLS 2006 talk "hrtimers6and beyond". The paper is part of the OLS 2006 Proceedings Volume 1, which can7be found on the OLS website:8https://www.kernel.org/doc/ols/2006/ols2006v1-pages-333-346.pdf9 10The slides to this talk are available from:11http://www.cs.columbia.edu/~nahum/w6998/papers/ols2006-hrtimers-slides.pdf12 13The slides contain five figures (pages 2, 15, 18, 20, 22), which illustrate the14changes in the time(r) related Linux subsystems. Figure #1 (p. 2) shows the15design of the Linux time(r) system before hrtimers and other building blocks16got merged into mainline.17 18Note: the paper and the slides are talking about "clock event source", while we19switched to the name "clock event devices" in meantime.20 21The design contains the following basic building blocks:22 23- hrtimer base infrastructure24- timeofday and clock source management25- clock event management26- high resolution timer functionality27- dynamic ticks28 29 30hrtimer base infrastructure31---------------------------32 33The hrtimer base infrastructure was merged into the 2.6.16 kernel. Details of34the base implementation are covered in Documentation/timers/hrtimers.rst. See35also figure #2 (OLS slides p. 15)36 37The main differences to the timer wheel, which holds the armed timer_list type38timers are:39 40 - time ordered enqueueing into a rb-tree41 - independent of ticks (the processing is based on nanoseconds)42 43 44timeofday and clock source management45-------------------------------------46 47John Stultz's Generic Time Of Day (GTOD) framework moves a large portion of48code out of the architecture-specific areas into a generic management49framework, as illustrated in figure #3 (OLS slides p. 18). The architecture50specific portion is reduced to the low level hardware details of the clock51sources, which are registered in the framework and selected on a quality based52decision. The low level code provides hardware setup and readout routines and53initializes data structures, which are used by the generic time keeping code to54convert the clock ticks to nanosecond based time values. All other time keeping55related functionality is moved into the generic code. The GTOD base patch got56merged into the 2.6.18 kernel.57 58Further information about the Generic Time Of Day framework is available in the59OLS 2005 Proceedings Volume 1:60 61 http://www.linuxsymposium.org/2005/linuxsymposium_procv1.pdf62 63The paper "We Are Not Getting Any Younger: A New Approach to Time and64Timers" was written by J. Stultz, D.V. Hart, & N. Aravamudan.65 66Figure #3 (OLS slides p.18) illustrates the transformation.67 68 69clock event management70----------------------71 72While clock sources provide read access to the monotonically increasing time73value, clock event devices are used to schedule the next event74interrupt(s). The next event is currently defined to be periodic, with its75period defined at compile time. The setup and selection of the event device76for various event driven functionalities is hardwired into the architecture77dependent code. This results in duplicated code across all architectures and78makes it extremely difficult to change the configuration of the system to use79event interrupt devices other than those already built into the80architecture. Another implication of the current design is that it is necessary81to touch all the architecture-specific implementations in order to provide new82functionality like high resolution timers or dynamic ticks.83 84The clock events subsystem tries to address this problem by providing a generic85solution to manage clock event devices and their usage for the various clock86event driven kernel functionalities. The goal of the clock event subsystem is87to minimize the clock event related architecture dependent code to the pure88hardware related handling and to allow easy addition and utilization of new89clock event devices. It also minimizes the duplicated code across the90architectures as it provides generic functionality down to the interrupt91service handler, which is almost inherently hardware dependent.92 93Clock event devices are registered either by the architecture dependent boot94code or at module insertion time. Each clock event device fills a data95structure with clock-specific property parameters and callback functions. The96clock event management decides, by using the specified property parameters, the97set of system functions a clock event device will be used to support. This98includes the distinction of per-CPU and per-system global event devices.99 100System-level global event devices are used for the Linux periodic tick. Per-CPU101event devices are used to provide local CPU functionality such as process102accounting, profiling, and high resolution timers.103 104The management layer assigns one or more of the following functions to a clock105event device:106 107 - system global periodic tick (jiffies update)108 - cpu local update_process_times109 - cpu local profiling110 - cpu local next event interrupt (non periodic mode)111 112The clock event device delegates the selection of those timer interrupt related113functions completely to the management layer. The clock management layer stores114a function pointer in the device description structure, which has to be called115from the hardware level handler. This removes a lot of duplicated code from the116architecture specific timer interrupt handlers and hands the control over the117clock event devices and the assignment of timer interrupt related functionality118to the core code.119 120The clock event layer API is rather small. Aside from the clock event device121registration interface it provides functions to schedule the next event122interrupt, clock event device notification service and support for suspend and123resume.124 125The framework adds about 700 lines of code which results in a 2KB increase of126the kernel binary size. The conversion of i386 removes about 100 lines of127code. The binary size decrease is in the range of 400 byte. We believe that the128increase of flexibility and the avoidance of duplicated code across129architectures justifies the slight increase of the binary size.130 131The conversion of an architecture has no functional impact, but allows to132utilize the high resolution and dynamic tick functionalities without any change133to the clock event device and timer interrupt code. After the conversion the134enabling of high resolution timers and dynamic ticks is simply provided by135adding the kernel/time/Kconfig file to the architecture specific Kconfig and136adding the dynamic tick specific calls to the idle routine (a total of 3 lines137added to the idle function and the Kconfig file)138 139Figure #4 (OLS slides p.20) illustrates the transformation.140 141 142high resolution timer functionality143-----------------------------------144 145During system boot it is not possible to use the high resolution timer146functionality, while making it possible would be difficult and would serve no147useful function. The initialization of the clock event device framework, the148clock source framework (GTOD) and hrtimers itself has to be done and149appropriate clock sources and clock event devices have to be registered before150the high resolution functionality can work. Up to the point where hrtimers are151initialized, the system works in the usual low resolution periodic mode. The152clock source and the clock event device layers provide notification functions153which inform hrtimers about availability of new hardware. hrtimers validates154the usability of the registered clock sources and clock event devices before155switching to high resolution mode. This ensures also that a kernel which is156configured for high resolution timers can run on a system which lacks the157necessary hardware support.158 159The high resolution timer code does not support SMP machines which have only160global clock event devices. The support of such hardware would involve IPI161calls when an interrupt happens. The overhead would be much larger than the162benefit. This is the reason why we currently disable high resolution and163dynamic ticks on i386 SMP systems which stop the local APIC in C3 power164state. A workaround is available as an idea, but the problem has not been165tackled yet.166 167The time ordered insertion of timers provides all the infrastructure to decide168whether the event device has to be reprogrammed when a timer is added. The169decision is made per timer base and synchronized across per-cpu timer bases in170a support function. The design allows the system to utilize separate per-CPU171clock event devices for the per-CPU timer bases, but currently only one172reprogrammable clock event device per-CPU is utilized.173 174When the timer interrupt happens, the next event interrupt handler is called175from the clock event distribution code and moves expired timers from the176red-black tree to a separate double linked list and invokes the softirq177handler. An additional mode field in the hrtimer structure allows the system to178execute callback functions directly from the next event interrupt handler. This179is restricted to code which can safely be executed in the hard interrupt180context. This applies, for example, to the common case of a wakeup function as181used by nanosleep. The advantage of executing the handler in the interrupt182context is the avoidance of up to two context switches - from the interrupted183context to the softirq and to the task which is woken up by the expired184timer.185 186Once a system has switched to high resolution mode, the periodic tick is187switched off. This disables the per system global periodic clock event device -188e.g. the PIT on i386 SMP systems.189 190The periodic tick functionality is provided by an per-cpu hrtimer. The callback191function is executed in the next event interrupt context and updates jiffies192and calls update_process_times and profiling. The implementation of the hrtimer193based periodic tick is designed to be extended with dynamic tick functionality.194This allows to use a single clock event device to schedule high resolution195timer and periodic events (jiffies tick, profiling, process accounting) on UP196systems. This has been proved to work with the PIT on i386 and the Incrementer197on PPC.198 199The softirq for running the hrtimer queues and executing the callbacks has been200separated from the tick bound timer softirq to allow accurate delivery of high201resolution timer signals which are used by itimer and POSIX interval202timers. The execution of this softirq can still be delayed by other softirqs,203but the overall latencies have been significantly improved by this separation.204 205Figure #5 (OLS slides p.22) illustrates the transformation.206 207 208dynamic ticks209-------------210 211Dynamic ticks are the logical consequence of the hrtimer based periodic tick212replacement (sched_tick). The functionality of the sched_tick hrtimer is213extended by three functions:214 215- hrtimer_stop_sched_tick216- hrtimer_restart_sched_tick217- hrtimer_update_jiffies218 219hrtimer_stop_sched_tick() is called when a CPU goes into idle state. The code220evaluates the next scheduled timer event (from both hrtimers and the timer221wheel) and in case that the next event is further away than the next tick it222reprograms the sched_tick to this future event, to allow longer idle sleeps223without worthless interruption by the periodic tick. The function is also224called when an interrupt happens during the idle period, which does not cause a225reschedule. The call is necessary as the interrupt handler might have armed a226new timer whose expiry time is before the time which was identified as the227nearest event in the previous call to hrtimer_stop_sched_tick.228 229hrtimer_restart_sched_tick() is called when the CPU leaves the idle state before230it calls schedule(). hrtimer_restart_sched_tick() resumes the periodic tick,231which is kept active until the next call to hrtimer_stop_sched_tick().232 233hrtimer_update_jiffies() is called from irq_enter() when an interrupt happens234in the idle period to make sure that jiffies are up to date and the interrupt235handler has not to deal with an eventually stale jiffy value.236 237The dynamic tick feature provides statistical values which are exported to238userspace via /proc/stat and can be made available for enhanced power239management control.240 241The implementation leaves room for further development like full tickless242systems, where the time slice is controlled by the scheduler, variable243frequency profiling, and a complete removal of jiffies in the future.244 245 246Aside the current initial submission of i386 support, the patchset has been247extended to x86_64 and ARM already. Initial (work in progress) support is also248available for MIPS and PowerPC.249 250 Thomas, Ingo251