1High resolution timers and dynamic ticks design notes
   4Further information can be found in the paper of the OLS 2006 talk "hrtimers
   5and beyond". The paper is part of the OLS 2006 Proceedings Volume 1, which can
   6be found on the OLS website:
   9The slides to this talk are available from:
  12The slides contain five figures (pages 2, 15, 18, 20, 22), which illustrate the
  13changes in the time(r) related Linux subsystems. Figure #1 (p. 2) shows the
  14design of the Linux time(r) system before hrtimers and other building blocks
  15got merged into mainline.
  17Note: the paper and the slides are talking about "clock event source", while we
  18switched to the name "clock event devices" in meantime.
  20The design contains the following basic building blocks:
  22- hrtimer base infrastructure
  23- timeofday and clock source management
  24- clock event management
  25- high resolution timer functionality
  26- dynamic ticks
  29hrtimer base infrastructure
  32The hrtimer base infrastructure was merged into the 2.6.16 kernel. Details of
  33the base implementation are covered in Documentation/hrtimers/hrtimer.txt. See
  34also figure #2 (OLS slides p. 15)
  36The main differences to the timer wheel, which holds the armed timer_list type
  37timers are:
  38       - time ordered enqueueing into a rb-tree
  39       - independent of ticks (the processing is based on nanoseconds)
  42timeofday and clock source management
  45John Stultz's Generic Time Of Day (GTOD) framework moves a large portion of
  46code out of the architecture-specific areas into a generic management
  47framework, as illustrated in figure #3 (OLS slides p. 18). The architecture
  48specific portion is reduced to the low level hardware details of the clock
  49sources, which are registered in the framework and selected on a quality based
  50decision. The low level code provides hardware setup and readout routines and
  51initializes data structures, which are used by the generic time keeping code to
  52convert the clock ticks to nanosecond based time values. All other time keeping
  53related functionality is moved into the generic code. The GTOD base patch got
  54merged into the 2.6.18 kernel.
  56Further information about the Generic Time Of Day framework is available in the
  57OLS 2005 Proceedings Volume 1:
  60The paper "We Are Not Getting Any Younger: A New Approach to Time and
  61Timers" was written by J. Stultz, D.V. Hart, & N. Aravamudan.
  63Figure #3 (OLS slides p.18) illustrates the transformation.
  66clock event management
  69While clock sources provide read access to the monotonically increasing time
  70value, clock event devices are used to schedule the next event
  71interrupt(s). The next event is currently defined to be periodic, with its
  72period defined at compile time. The setup and selection of the event device
  73for various event driven functionalities is hardwired into the architecture
  74dependent code. This results in duplicated code across all architectures and
  75makes it extremely difficult to change the configuration of the system to use
  76event interrupt devices other than those already built into the
  77architecture. Another implication of the current design is that it is necessary
  78to touch all the architecture-specific implementations in order to provide new
  79functionality like high resolution timers or dynamic ticks.
  81The clock events subsystem tries to address this problem by providing a generic
  82solution to manage clock event devices and their usage for the various clock
  83event driven kernel functionalities. The goal of the clock event subsystem is
  84to minimize the clock event related architecture dependent code to the pure
  85hardware related handling and to allow easy addition and utilization of new
  86clock event devices. It also minimizes the duplicated code across the
  87architectures as it provides generic functionality down to the interrupt
  88service handler, which is almost inherently hardware dependent.
  90Clock event devices are registered either by the architecture dependent boot
  91code or at module insertion time. Each clock event device fills a data
  92structure with clock-specific property parameters and callback functions. The
  93clock event management decides, by using the specified property parameters, the
  94set of system functions a clock event device will be used to support. This
  95includes the distinction of per-CPU and per-system global event devices.
  97System-level global event devices are used for the Linux periodic tick. Per-CPU
  98event devices are used to provide local CPU functionality such as process
  99accounting, profiling, and high resolution timers.
 101The management layer assigns one or more of the following functions to a clock
 102event device:
 103      - system global periodic tick (jiffies update)
 104      - cpu local update_process_times
 105      - cpu local profiling
 106      - cpu local next event interrupt (non periodic mode)
 108The clock event device delegates the selection of those timer interrupt related
 109functions completely to the management layer. The clock management layer stores
 110a function pointer in the device description structure, which has to be called
 111from the hardware level handler. This removes a lot of duplicated code from the
 112architecture specific timer interrupt handlers and hands the control over the
 113clock event devices and the assignment of timer interrupt related functionality
 114to the core code.
 116The clock event layer API is rather small. Aside from the clock event device
 117registration interface it provides functions to schedule the next event
 118interrupt, clock event device notification service and support for suspend and
 121The framework adds about 700 lines of code which results in a 2KB increase of
 122the kernel binary size. The conversion of i386 removes about 100 lines of
 123code. The binary size decrease is in the range of 400 byte. We believe that the
 124increase of flexibility and the avoidance of duplicated code across
 125architectures justifies the slight increase of the binary size.
 127The conversion of an architecture has no functional impact, but allows to
 128utilize the high resolution and dynamic tick functionalities without any change
 129to the clock event device and timer interrupt code. After the conversion the
 130enabling of high resolution timers and dynamic ticks is simply provided by
 131adding the kernel/time/Kconfig file to the architecture specific Kconfig and
 132adding the dynamic tick specific calls to the idle routine (a total of 3 lines
 133added to the idle function and the Kconfig file)
 135Figure #4 (OLS slides p.20) illustrates the transformation.
 138high resolution timer functionality
 141During system boot it is not possible to use the high resolution timer
 142functionality, while making it possible would be difficult and would serve no
 143useful function. The initialization of the clock event device framework, the
 144clock source framework (GTOD) and hrtimers itself has to be done and
 145appropriate clock sources and clock event devices have to be registered before
 146the high resolution functionality can work. Up to the point where hrtimers are
 147initialized, the system works in the usual low resolution periodic mode. The
 148clock source and the clock event device layers provide notification functions
 149which inform hrtimers about availability of new hardware. hrtimers validates
 150the usability of the registered clock sources and clock event devices before
 151switching to high resolution mode. This ensures also that a kernel which is
 152configured for high resolution timers can run on a system which lacks the
 153necessary hardware support.
 155The high resolution timer code does not support SMP machines which have only
 156global clock event devices. The support of such hardware would involve IPI
 157calls when an interrupt happens. The overhead would be much larger than the
 158benefit. This is the reason why we currently disable high resolution and
 159dynamic ticks on i386 SMP systems which stop the local APIC in C3 power
 160state. A workaround is available as an idea, but the problem has not been
 161tackled yet.
 163The time ordered insertion of timers provides all the infrastructure to decide
 164whether the event device has to be reprogrammed when a timer is added. The
 165decision is made per timer base and synchronized across per-cpu timer bases in
 166a support function. The design allows the system to utilize separate per-CPU
 167clock event devices for the per-CPU timer bases, but currently only one
 168reprogrammable clock event device per-CPU is utilized.
 170When the timer interrupt happens, the next event interrupt handler is called
 171from the clock event distribution code and moves expired timers from the
 172red-black tree to a separate double linked list and invokes the softirq
 173handler. An additional mode field in the hrtimer structure allows the system to
 174execute callback functions directly from the next event interrupt handler. This
 175is restricted to code which can safely be executed in the hard interrupt
 176context. This applies, for example, to the common case of a wakeup function as
 177used by nanosleep. The advantage of executing the handler in the interrupt
 178context is the avoidance of up to two context switches - from the interrupted
 179context to the softirq and to the task which is woken up by the expired
 182Once a system has switched to high resolution mode, the periodic tick is
 183switched off. This disables the per system global periodic clock event device -
 184e.g. the PIT on i386 SMP systems.
 186The periodic tick functionality is provided by an per-cpu hrtimer. The callback
 187function is executed in the next event interrupt context and updates jiffies
 188and calls update_process_times and profiling. The implementation of the hrtimer
 189based periodic tick is designed to be extended with dynamic tick functionality.
 190This allows to use a single clock event device to schedule high resolution
 191timer and periodic events (jiffies tick, profiling, process accounting) on UP
 192systems. This has been proved to work with the PIT on i386 and the Incrementer
 193on PPC.
 195The softirq for running the hrtimer queues and executing the callbacks has been
 196separated from the tick bound timer softirq to allow accurate delivery of high
 197resolution timer signals which are used by itimer and POSIX interval
 198timers. The execution of this softirq can still be delayed by other softirqs,
 199but the overall latencies have been significantly improved by this separation.
 201Figure #5 (OLS slides p.22) illustrates the transformation.
 204dynamic ticks
 207Dynamic ticks are the logical consequence of the hrtimer based periodic tick
 208replacement (sched_tick). The functionality of the sched_tick hrtimer is
 209extended by three functions:
 211- hrtimer_stop_sched_tick
 212- hrtimer_restart_sched_tick
 213- hrtimer_update_jiffies
 215hrtimer_stop_sched_tick() is called when a CPU goes into idle state. The code
 216evaluates the next scheduled timer event (from both hrtimers and the timer
 217wheel) and in case that the next event is further away than the next tick it
 218reprograms the sched_tick to this future event, to allow longer idle sleeps
 219without worthless interruption by the periodic tick. The function is also
 220called when an interrupt happens during the idle period, which does not cause a
 221reschedule. The call is necessary as the interrupt handler might have armed a
 222new timer whose expiry time is before the time which was identified as the
 223nearest event in the previous call to hrtimer_stop_sched_tick.
 225hrtimer_restart_sched_tick() is called when the CPU leaves the idle state before
 226it calls schedule(). hrtimer_restart_sched_tick() resumes the periodic tick,
 227which is kept active until the next call to hrtimer_stop_sched_tick().
 229hrtimer_update_jiffies() is called from irq_enter() when an interrupt happens
 230in the idle period to make sure that jiffies are up to date and the interrupt
 231handler has not to deal with an eventually stale jiffy value.
 233The dynamic tick feature provides statistical values which are exported to
 234userspace via /proc/stats and can be made available for enhanced power
 235management control.
 237The implementation leaves room for further development like full tickless
 238systems, where the time slice is controlled by the scheduler, variable
 239frequency profiling, and a complete removal of jiffies in the future.
 242Aside the current initial submission of i386 support, the patchset has been
 243extended to x86_64 and ARM already. Initial (work in progress) support is also
 244available for MIPS and PowerPC.
 246          Thomas, Ingo