1 ==============================================
2 High resolution timers and dynamic ticks desig
3 ==============================================
4
5 Further information can be found in the paper
6 and beyond". The paper is part of the OLS 2006
7 be found on the OLS website:
8 https://www.kernel.org/doc/ols/2006/ols2006v1-
9
10 The slides to this talk are available from:
11 http://www.cs.columbia.edu/~nahum/w6998/papers
12
13 The slides contain five figures (pages 2, 15,
14 changes in the time(r) related Linux subsystem
15 design of the Linux time(r) system before hrti
16 got merged into mainline.
17
18 Note: the paper and the slides are talking abo
19 switched to the name "clock event devices" in
20
21 The design contains the following basic buildi
22
23 - hrtimer base infrastructure
24 - timeofday and clock source management
25 - clock event management
26 - high resolution timer functionality
27 - dynamic ticks
28
29
30 hrtimer base infrastructure
31 ---------------------------
32
33 The hrtimer base infrastructure was merged int
34 the base implementation are covered in Documen
35 also figure #2 (OLS slides p. 15)
36
37 The main differences to the timer wheel, which
38 timers are:
39
40 - time ordered enqueueing into a rb-tre
41 - independent of ticks (the processing
42
43
44 timeofday and clock source management
45 -------------------------------------
46
47 John Stultz's Generic Time Of Day (GTOD) frame
48 code out of the architecture-specific areas in
49 framework, as illustrated in figure #3 (OLS sl
50 specific portion is reduced to the low level h
51 sources, which are registered in the framework
52 decision. The low level code provides hardware
53 initializes data structures, which are used by
54 convert the clock ticks to nanosecond based ti
55 related functionality is moved into the generi
56 merged into the 2.6.18 kernel.
57
58 Further information about the Generic Time Of
59 OLS 2005 Proceedings Volume 1:
60
61 http://www.linuxsymposium.org/2005/lin
62
63 The paper "We Are Not Getting Any Younger: A N
64 Timers" was written by J. Stultz, D.V. Hart, &
65
66 Figure #3 (OLS slides p.18) illustrates the tr
67
68
69 clock event management
70 ----------------------
71
72 While clock sources provide read access to the
73 value, clock event devices are used to schedul
74 interrupt(s). The next event is currently defi
75 period defined at compile time. The setup and
76 for various event driven functionalities is ha
77 dependent code. This results in duplicated cod
78 makes it extremely difficult to change the con
79 event interrupt devices other than those alrea
80 architecture. Another implication of the curre
81 to touch all the architecture-specific impleme
82 functionality like high resolution timers or d
83
84 The clock events subsystem tries to address th
85 solution to manage clock event devices and the
86 event driven kernel functionalities. The goal
87 to minimize the clock event related architectu
88 hardware related handling and to allow easy ad
89 clock event devices. It also minimizes the dup
90 architectures as it provides generic functiona
91 service handler, which is almost inherently ha
92
93 Clock event devices are registered either by t
94 code or at module insertion time. Each clock e
95 structure with clock-specific property paramet
96 clock event management decides, by using the s
97 set of system functions a clock event device w
98 includes the distinction of per-CPU and per-sy
99
100 System-level global event devices are used for
101 event devices are used to provide local CPU fu
102 accounting, profiling, and high resolution tim
103
104 The management layer assigns one or more of th
105 event device:
106
107 - system global periodic tick (jiffies u
108 - cpu local update_process_times
109 - cpu local profiling
110 - cpu local next event interrupt (non pe
111
112 The clock event device delegates the selection
113 functions completely to the management layer.
114 a function pointer in the device description s
115 from the hardware level handler. This removes
116 architecture specific timer interrupt handlers
117 clock event devices and the assignment of time
118 to the core code.
119
120 The clock event layer API is rather small. Asi
121 registration interface it provides functions t
122 interrupt, clock event device notification ser
123 resume.
124
125 The framework adds about 700 lines of code whi
126 the kernel binary size. The conversion of i386
127 code. The binary size decrease is in the range
128 increase of flexibility and the avoidance of d
129 architectures justifies the slight increase of
130
131 The conversion of an architecture has no funct
132 utilize the high resolution and dynamic tick f
133 to the clock event device and timer interrupt
134 enabling of high resolution timers and dynamic
135 adding the kernel/time/Kconfig file to the arc
136 adding the dynamic tick specific calls to the
137 added to the idle function and the Kconfig fil
138
139 Figure #4 (OLS slides p.20) illustrates the tr
140
141
142 high resolution timer functionality
143 -----------------------------------
144
145 During system boot it is not possible to use t
146 functionality, while making it possible would
147 useful function. The initialization of the clo
148 clock source framework (GTOD) and hrtimers its
149 appropriate clock sources and clock event devi
150 the high resolution functionality can work. Up
151 initialized, the system works in the usual low
152 clock source and the clock event device layers
153 which inform hrtimers about availability of ne
154 the usability of the registered clock sources
155 switching to high resolution mode. This ensure
156 configured for high resolution timers can run
157 necessary hardware support.
158
159 The high resolution timer code does not suppor
160 global clock event devices. The support of suc
161 calls when an interrupt happens. The overhead
162 benefit. This is the reason why we currently d
163 dynamic ticks on i386 SMP systems which stop t
164 state. A workaround is available as an idea, b
165 tackled yet.
166
167 The time ordered insertion of timers provides
168 whether the event device has to be reprogramme
169 decision is made per timer base and synchroniz
170 a support function. The design allows the syst
171 clock event devices for the per-CPU timer base
172 reprogrammable clock event device per-CPU is u
173
174 When the timer interrupt happens, the next eve
175 from the clock event distribution code and mov
176 red-black tree to a separate double linked lis
177 handler. An additional mode field in the hrtim
178 execute callback functions directly from the n
179 is restricted to code which can safely be exec
180 context. This applies, for example, to the com
181 used by nanosleep. The advantage of executing
182 context is the avoidance of up to two context
183 context to the softirq and to the task which i
184 timer.
185
186 Once a system has switched to high resolution
187 switched off. This disables the per system glo
188 e.g. the PIT on i386 SMP systems.
189
190 The periodic tick functionality is provided by
191 function is executed in the next event interru
192 and calls update_process_times and profiling.
193 based periodic tick is designed to be extended
194 This allows to use a single clock event device
195 timer and periodic events (jiffies tick, profi
196 systems. This has been proved to work with the
197 on PPC.
198
199 The softirq for running the hrtimer queues and
200 separated from the tick bound timer softirq to
201 resolution timer signals which are used by iti
202 timers. The execution of this softirq can stil
203 but the overall latencies have been significan
204
205 Figure #5 (OLS slides p.22) illustrates the tr
206
207
208 dynamic ticks
209 -------------
210
211 Dynamic ticks are the logical consequence of t
212 replacement (sched_tick). The functionality of
213 extended by three functions:
214
215 - hrtimer_stop_sched_tick
216 - hrtimer_restart_sched_tick
217 - hrtimer_update_jiffies
218
219 hrtimer_stop_sched_tick() is called when a CPU
220 evaluates the next scheduled timer event (from
221 wheel) and in case that the next event is furt
222 reprograms the sched_tick to this future event
223 without worthless interruption by the periodic
224 called when an interrupt happens during the id
225 reschedule. The call is necessary as the inter
226 new timer whose expiry time is before the time
227 nearest event in the previous call to hrtimer_
228
229 hrtimer_restart_sched_tick() is called when th
230 it calls schedule(). hrtimer_restart_sched_tic
231 which is kept active until the next call to hr
232
233 hrtimer_update_jiffies() is called from irq_en
234 in the idle period to make sure that jiffies a
235 handler has not to deal with an eventually sta
236
237 The dynamic tick feature provides statistical
238 userspace via /proc/stat and can be made avail
239 management control.
240
241 The implementation leaves room for further dev
242 systems, where the time slice is controlled by
243 frequency profiling, and a complete removal of
244
245
246 Aside the current initial submission of i386 s
247 extended to x86_64 and ARM already. Initial (w
248 available for MIPS and PowerPC.
249
250 Thomas, Ingo
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.