Further information can be found in the paper of the OLS 2006 talk “hrtimersand beyond”. The paper is part of the OLS 2006 Proceedings Volume 1, which canbe found on the OLS website:https://www.kernel.org/doc/ols/2006/ols2006v1-pages-333-346.pdf
The slides to this talk are available from:http://www.cs.columbia.edu/~nahum/w6998/papers/ols2006-hrtimers-slides.pdf
The slides contain five figures (pages 2, 15, 18, 20, 22), which illustrate thechanges in the time(r) related Linux subsystems. Figure #1 (p. 2) shows thedesign of the Linux time(r) system before hrtimers and other building blocksgot merged into mainline.
Note: the paper and the slides are talking about “clock event source”, while weswitched to the name “clock event devices” in meantime.
The design contains the following basic building blocks:
hrtimer base infrastructure
timeofday and clock source management
clock event management
high resolution timer functionality
dynamic ticks
hrtimer base infrastructure¶
The hrtimer base infrastructure was merged into the 2.6.16 kernel. Details ofthe base implementation are covered in hrtimers - subsystem for high-resolution kernel timers. Seealso figure #2 (OLS slides p. 15)
The main differences to the timer wheel, which holds the armed timer_list typetimers are:
time ordered enqueueing into a rb-tree
independent of ticks (the processing is based on nanoseconds)
timeofday and clock source management¶
John Stultz’s Generic Time Of Day (GTOD) framework moves a large portion ofcode out of the architecture-specific areas into a generic managementframework, as illustrated in figure #3 (OLS slides p. 18). The architecturespecific portion is reduced to the low level hardware details of the clocksources, which are registered in the framework and selected on a quality baseddecision. The low level code provides hardware setup and readout routines andinitializes data structures, which are used by the generic time keeping code toconvert the clock ticks to nanosecond based time values. All other time keepingrelated functionality is moved into the generic code. The GTOD base patch gotmerged into the 2.6.18 kernel.
Further information about the Generic Time Of Day framework is available in theOLS 2005 Proceedings Volume 1:
The paper “We Are Not Getting Any Younger: A New Approach to Time andTimers” was written by J. Stultz, D.V. Hart, & N. Aravamudan.
Figure #3 (OLS slides p.18) illustrates the transformation.
clock event management¶
While clock sources provide read access to the monotonically increasing timevalue, clock event devices are used to schedule the next eventinterrupt(s). The next event is currently defined to be periodic, with itsperiod defined at compile time. The setup and selection of the event devicefor various event driven functionalities is hardwired into the architecturedependent code. This results in duplicated code across all architectures andmakes it extremely difficult to change the configuration of the system to useevent interrupt devices other than those already built into thearchitecture. Another implication of the current design is that it is necessaryto touch all the architecture-specific implementations in order to provide newfunctionality like high resolution timers or dynamic ticks.
The clock events subsystem tries to address this problem by providing a genericsolution to manage clock event devices and their usage for the various clockevent driven kernel functionalities. The goal of the clock event subsystem isto minimize the clock event related architecture dependent code to the purehardware related handling and to allow easy addition and utilization of newclock event devices. It also minimizes the duplicated code across thearchitectures as it provides generic functionality down to the interruptservice handler, which is almost inherently hardware dependent.
Clock event devices are registered either by the architecture dependent bootcode or at module insertion time. Each clock event device fills a datastructure with clock-specific property parameters and callback functions. Theclock event management decides, by using the specified property parameters, theset of system functions a clock event device will be used to support. Thisincludes the distinction of per-CPU and per-system global event devices.
System-level global event devices are used for the Linux periodic tick. Per-CPUevent devices are used to provide local CPU functionality such as processaccounting, profiling, and high resolution timers.
The management layer assigns one or more of the following functions to a clockevent device:
system global periodic tick (jiffies update)
cpu local update_process_times
cpu local profiling
cpu local next event interrupt (non periodic mode)
The clock event device delegates the selection of those timer interrupt relatedfunctions completely to the management layer. The clock management layer storesa function pointer in the device description structure, which has to be calledfrom the hardware level handler. This removes a lot of duplicated code from thearchitecture specific timer interrupt handlers and hands the control over theclock event devices and the assignment of timer interrupt related functionalityto the core code.
The clock event layer API is rather small. Aside from the clock event deviceregistration interface it provides functions to schedule the next eventinterrupt, clock event device notification service and support for suspend andresume.
The framework adds about 700 lines of code which results in a 2KB increase ofthe kernel binary size. The conversion of i386 removes about 100 lines ofcode. The binary size decrease is in the range of 400 byte. We believe that theincrease of flexibility and the avoidance of duplicated code acrossarchitectures justifies the slight increase of the binary size.
The conversion of an architecture has no functional impact, but allows toutilize the high resolution and dynamic tick functionalities without any changeto the clock event device and timer interrupt code. After the conversion theenabling of high resolution timers and dynamic ticks is simply provided byadding the kernel/time/Kconfig file to the architecture specific Kconfig andadding the dynamic tick specific calls to the idle routine (a total of 3 linesadded to the idle function and the Kconfig file)
Figure #4 (OLS slides p.20) illustrates the transformation.
high resolution timer functionality¶
During system boot it is not possible to use the high resolution timerfunctionality, while making it possible would be difficult and would serve nouseful function. The initialization of the clock event device framework, theclock source framework (GTOD) and hrtimers itself has to be done andappropriate clock sources and clock event devices have to be registered beforethe high resolution functionality can work. Up to the point where hrtimers areinitialized, the system works in the usual low resolution periodic mode. Theclock source and the clock event device layers provide notification functionswhich inform hrtimers about availability of new hardware. hrtimers validatesthe usability of the registered clock sources and clock event devices beforeswitching to high resolution mode. This ensures also that a kernel which isconfigured for high resolution timers can run on a system which lacks thenecessary hardware support.
The high resolution timer code does not support SMP machines which have onlyglobal clock event devices. The support of such hardware would involve IPIcalls when an interrupt happens. The overhead would be much larger than thebenefit. This is the reason why we currently disable high resolution anddynamic ticks on i386 SMP systems which stop the local APIC in C3 powerstate. A workaround is available as an idea, but the problem has not beentackled yet.
The time ordered insertion of timers provides all the infrastructure to decidewhether the event device has to be reprogrammed when a timer is added. Thedecision is made per timer base and synchronized across per-cpu timer bases ina support function. The design allows the system to utilize separate per-CPUclock event devices for the per-CPU timer bases, but currently only onereprogrammable clock event device per-CPU is utilized.
When the timer interrupt happens, the next event interrupt handler is calledfrom the clock event distribution code and moves expired timers from thered-black tree to a separate double linked list and invokes the softirqhandler. An additional mode field in the hrtimer structure allows the system toexecute callback functions directly from the next event interrupt handler. Thisis restricted to code which can safely be executed in the hard interruptcontext. This applies, for example, to the common case of a wakeup function asused by nanosleep. The advantage of executing the handler in the interruptcontext is the avoidance of up to two context switches - from the interruptedcontext to the softirq and to the task which is woken up by the expiredtimer.
Once a system has switched to high resolution mode, the periodic tick isswitched off. This disables the per system global periodic clock event device -e.g. the PIT on i386 SMP systems.
The periodic tick functionality is provided by an per-cpu hrtimer. The callbackfunction is executed in the next event interrupt context and updates jiffiesand calls update_process_times and profiling. The implementation of the hrtimerbased periodic tick is designed to be extended with dynamic tick functionality.This allows to use a single clock event device to schedule high resolutiontimer and periodic events (jiffies tick, profiling, process accounting) on UPsystems. This has been proved to work with the PIT on i386 and the Incrementeron PPC.
The softirq for running the hrtimer queues and executing the callbacks has beenseparated from the tick bound timer softirq to allow accurate delivery of highresolution timer signals which are used by itimer and POSIX intervaltimers. The execution of this softirq can still be delayed by other softirqs,but the overall latencies have been significantly improved by this separation.
Figure #5 (OLS slides p.22) illustrates the transformation.
dynamic ticks¶
Dynamic ticks are the logical consequence of the hrtimer based periodic tickreplacement (sched_tick). The functionality of the sched_tick hrtimer isextended by three functions:
hrtimer_stop_sched_tick
hrtimer_restart_sched_tick
hrtimer_update_jiffies
hrtimer_stop_sched_tick() is called when a CPU goes into idle state. The codeevaluates the next scheduled timer event (from both hrtimers and the timerwheel) and in case that the next event is further away than the next tick itreprograms the sched_tick to this future event, to allow longer idle sleepswithout worthless interruption by the periodic tick. The function is alsocalled when an interrupt happens during the idle period, which does not cause areschedule. The call is necessary as the interrupt handler might have armed anew timer whose expiry time is before the time which was identified as thenearest event in the previous call to hrtimer_stop_sched_tick.
hrtimer_restart_sched_tick() is called when the CPU leaves the idle state beforeit calls schedule(). hrtimer_restart_sched_tick() resumes the periodic tick,which is kept active until the next call to hrtimer_stop_sched_tick().
hrtimer_update_jiffies() is called from irq_enter() when an interrupt happensin the idle period to make sure that jiffies are up to date and the interrupthandler has not to deal with an eventually stale jiffy value.
The dynamic tick feature provides statistical values which are exported touserspace via /proc/stat and can be made available for enhanced powermanagement control.
The implementation leaves room for further development like full ticklesssystems, where the time slice is controlled by the scheduler, variablefrequency profiling, and a complete removal of jiffies in the future.
Aside the current initial submission of i386 support, the patchset has beenextended to x86_64 and ARM already. Initial (work in progress) support is alsoavailable for MIPS and PowerPC.
Thomas, Ingo
