요약·해설과 원문, 전문 번역을 서로 분리했습니다. API 이름, symbol, source path는 원문 표기를 사용합니다.
1. 요약·해설
원문의 핵심 논리와 kernel programming 관점의 보충 설명입니다. 아래의 전문 번역과는 별도로 작성했습니다.
Clockevent mode와 broadcast
highres.rst:69-141Clockevent는 periodic tick 또는 one-shot next-event mode를 제공합니다. Highres mode에서는 periodic 1/HZ interrupt 대신 다음 hrtimer 또는 scheduler event 시각을 직접 programming합니다.
CPU local event device가 deep idle에서 정지하면 broadcast framework가 계속 동작하는 device에 wakeup deadline을 모읍니다. CPU hotplug에서는 per-CPU device ownership과 next event를 안전하게 이동해야 합니다.
High-resolution mode 전환
highres.rst:142-207Boot 초기에는 clocksource와 clockevent가 완전히 준비되지 않아 low-resolution tick 기반으로 시작할 수 있습니다. Suitable clocksource와 one-shot clockevent가 등록되고 timekeeping 안정성이 확인되면 hrtimer core가 high-resolution mode로 전환합니다.
Callback 실행이 늦어졌다면 현재 시간까지 만료된 timer를 순서대로 처리하고 다음 expiry를 다시 programming합니다. Interrupt latency가 timer resolution보다 크면 hardware precision만 높여도 callback latency 상한은 줄지 않습니다.
Dynamic tick과의 연결
highres.rst:208-251One-shot clockevent가 있으면 idle CPU에 매 jiffy scheduling tick을 보낼 필요가 없습니다. 다음 실제 deadline까지 tick을 멈추고 한 번에 깨우는 것이 dynamic tick의 기반입니다. Hrtimer precision과 NO_HZ energy saving은 같은 clockevent infrastructure를 공유하지만 별도 기능입니다.
2. 영어 원문 전체
번역 기준이 된 Linux v6.18.37 원문입니다. 줄 번호는 이 버전의 파일 좌표입니다.
원문 전체 펼치기
=====================================================
High resolution timers and dynamic ticks design notes
=====================================================
Further information can be found in the paper of the OLS 2006 talk "hrtimers
and beyond". The paper is part of the OLS 2006 Proceedings Volume 1, which can
be 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 the
changes in the time(r) related Linux subsystems. Figure #1 (p. 2) shows the
design of the Linux time(r) system before hrtimers and other building blocks
got merged into mainline.
Note: the paper and the slides are talking about "clock event source", while we
switched 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 of
the base implementation are covered in Documentation/timers/hrtimers.rst. See
also figure #2 (OLS slides p. 15)
The main differences to the timer wheel, which holds the armed timer_list type
timers 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 of
code out of the architecture-specific areas into a generic management
framework, as illustrated in figure #3 (OLS slides p. 18). The architecture
specific portion is reduced to the low level hardware details of the clock
sources, which are registered in the framework and selected on a quality based
decision. The low level code provides hardware setup and readout routines and
initializes data structures, which are used by the generic time keeping code to
convert the clock ticks to nanosecond based time values. All other time keeping
related functionality is moved into the generic code. The GTOD base patch got
merged into the 2.6.18 kernel.
Further information about the Generic Time Of Day framework is available in the
OLS 2005 Proceedings Volume 1:
http://www.linuxsymposium.org/2005/linuxsymposium_procv1.pdf
The paper "We Are Not Getting Any Younger: A New Approach to Time and
Timers" 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 time
value, clock event devices are used to schedule the next event
interrupt(s). The next event is currently defined to be periodic, with its
period defined at compile time. The setup and selection of the event device
for various event driven functionalities is hardwired into the architecture
dependent code. This results in duplicated code across all architectures and
makes it extremely difficult to change the configuration of the system to use
event interrupt devices other than those already built into the
architecture. Another implication of the current design is that it is necessary
to touch all the architecture-specific implementations in order to provide new
functionality like high resolution timers or dynamic ticks.
The clock events subsystem tries to address this problem by providing a generic
solution to manage clock event devices and their usage for the various clock
event driven kernel functionalities. The goal of the clock event subsystem is
to minimize the clock event related architecture dependent code to the pure
hardware related handling and to allow easy addition and utilization of new
clock event devices. It also minimizes the duplicated code across the
architectures as it provides generic functionality down to the interrupt
service handler, which is almost inherently hardware dependent.
Clock event devices are registered either by the architecture dependent boot
code or at module insertion time. Each clock event device fills a data
structure with clock-specific property parameters and callback functions. The
clock event management decides, by using the specified property parameters, the
set of system functions a clock event device will be used to support. This
includes the distinction of per-CPU and per-system global event devices.
System-level global event devices are used for the Linux periodic tick. Per-CPU
event devices are used to provide local CPU functionality such as process
accounting, profiling, and high resolution timers.
The management layer assigns one or more of the following functions to a clock
event 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 related
functions completely to the management layer. The clock management layer stores
a function pointer in the device description structure, which has to be called
from the hardware level handler. This removes a lot of duplicated code from the
architecture specific timer interrupt handlers and hands the control over the
clock event devices and the assignment of timer interrupt related functionality
to the core code.
The clock event layer API is rather small. Aside from the clock event device
registration interface it provides functions to schedule the next event
interrupt, clock event device notification service and support for suspend and
resume.
The framework adds about 700 lines of code which results in a 2KB increase of
the kernel binary size. The conversion of i386 removes about 100 lines of
code. The binary size decrease is in the range of 400 byte. We believe that the
increase of flexibility and the avoidance of duplicated code across
architectures justifies the slight increase of the binary size.
The conversion of an architecture has no functional impact, but allows to
utilize the high resolution and dynamic tick functionalities without any change
to the clock event device and timer interrupt code. After the conversion the
enabling of high resolution timers and dynamic ticks is simply provided by
adding the kernel/time/Kconfig file to the architecture specific Kconfig and
adding the dynamic tick specific calls to the idle routine (a total of 3 lines
added 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 timer
functionality, while making it possible would be difficult and would serve no
useful function. The initialization of the clock event device framework, the
clock source framework (GTOD) and hrtimers itself has to be done and
appropriate clock sources and clock event devices have to be registered before
the high resolution functionality can work. Up to the point where hrtimers are
initialized, the system works in the usual low resolution periodic mode. The
clock source and the clock event device layers provide notification functions
which inform hrtimers about availability of new hardware. hrtimers validates
the usability of the registered clock sources and clock event devices before
switching to high resolution mode. This ensures also that a kernel which is
configured for high resolution timers can run on a system which lacks the
necessary hardware support.
The high resolution timer code does not support SMP machines which have only
global clock event devices. The support of such hardware would involve IPI
calls when an interrupt happens. The overhead would be much larger than the
benefit. This is the reason why we currently disable high resolution and
dynamic ticks on i386 SMP systems which stop the local APIC in C3 power
state. A workaround is available as an idea, but the problem has not been
tackled yet.
The time ordered insertion of timers provides all the infrastructure to decide
whether the event device has to be reprogrammed when a timer is added. The
decision is made per timer base and synchronized across per-cpu timer bases in
a support function. The design allows the system to utilize separate per-CPU
clock event devices for the per-CPU timer bases, but currently only one
reprogrammable clock event device per-CPU is utilized.
When the timer interrupt happens, the next event interrupt handler is called
from the clock event distribution code and moves expired timers from the
red-black tree to a separate double linked list and invokes the softirq
handler. An additional mode field in the hrtimer structure allows the system to
execute callback functions directly from the next event interrupt handler. This
is restricted to code which can safely be executed in the hard interrupt
context. This applies, for example, to the common case of a wakeup function as
used by nanosleep. The advantage of executing the handler in the interrupt
context is the avoidance of up to two context switches - from the interrupted
context to the softirq and to the task which is woken up by the expired
timer.
Once a system has switched to high resolution mode, the periodic tick is
switched 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 callback
function is executed in the next event interrupt context and updates jiffies
and calls update_process_times and profiling. The implementation of the hrtimer
based periodic tick is designed to be extended with dynamic tick functionality.
This allows to use a single clock event device to schedule high resolution
timer and periodic events (jiffies tick, profiling, process accounting) on UP
systems. This has been proved to work with the PIT on i386 and the Incrementer
on PPC.
The softirq for running the hrtimer queues and executing the callbacks has been
separated from the tick bound timer softirq to allow accurate delivery of high
resolution timer signals which are used by itimer and POSIX interval
timers. 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 tick
replacement (sched_tick). The functionality of the sched_tick hrtimer is
extended 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 code
evaluates the next scheduled timer event (from both hrtimers and the timer
wheel) and in case that the next event is further away than the next tick it
reprograms the sched_tick to this future event, to allow longer idle sleeps
without worthless interruption by the periodic tick. The function is also
called when an interrupt happens during the idle period, which does not cause a
reschedule. The call is necessary as the interrupt handler might have armed a
new timer whose expiry time is before the time which was identified as the
nearest event in the previous call to hrtimer_stop_sched_tick.
hrtimer_restart_sched_tick() is called when the CPU leaves the idle state before
it 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 happens
in the idle period to make sure that jiffies are up to date and the interrupt
handler has not to deal with an eventually stale jiffy value.
The dynamic tick feature provides statistical values which are exported to
userspace via /proc/stat and can be made available for enhanced power
management control.
The implementation leaves room for further development like full tickless
systems, where the time slice is controlled by the scheduler, variable
frequency profiling, and a complete removal of jiffies in the future.
Aside the current initial submission of i386 support, the patchset has been
extended to x86_64 and ARM already. Initial (work in progress) support is also
available for MIPS and PowerPC.
Thomas, Ingo
3. 한국어 전문 번역
영어 원문의 문단 순서와 의미를 유지한 전체 번역입니다. 코드, 함수명, symbol과 URL은 원문 표기를 유지합니다.
고해상도 timer와 dynamic tick 설계 개요
1-28추가 정보는 OLS 2006 발표 “hrtimers and beyond” 논문에서 찾을 수 있다. 이 논문은 OLS 2006 Proceedings Volume 1에 수록되어 있다.
- OLS 2006 hrtimers 논문
https://www.kernel.org/doc/ols/2006/ols2006v1-pages-333-346.pdf - OLS 2006 발표 자료
http://www.cs.columbia.edu/~nahum/w6998/papers/ols2006-hrtimers-slides.pdf
발표 자료에는 Linux의 time 및 timer 관련 subsystem이 어떻게 바뀌었는지 보여 주는 그림 다섯 개가 있다(2, 15, 18, 20, 22쪽). 그림 1은 hrtimer와 다른 기반 구성 요소가 mainline에 merge되기 전 Linux time(r) system의 설계를 보여 준다.
논문과 발표 자료에서는 “clock event source”라는 이름을 사용하지만, 이후 명칭은 “clock event devices”로 바뀌었다.
- hrtimer 기반 infrastructure
- timeofday 및 clock source 관리
- clock event 관리
- 고해상도 timer 기능
- dynamic tick
hrtimer 기반 infrastructure
30-42hrtimer 기반 infrastructure는 Linux 2.6.16에 merge되었다. 기반 구현의 자세한 내용은 Documentation/timers/hrtimers.rst와 OLS 발표 자료 15쪽의 그림 2를 참조한다.
활성화된 timer_list timer를 보관하는 timer wheel과 비교하면 핵심 차이는 두 가지다. hrtimer는 시간순으로 red-black tree에 삽입하며, tick에 의존하지 않고 나노초 단위 시간을 기준으로 처리한다.
timeofday와 clock source 관리
44-66John Stultz의 Generic Time Of Day(GTOD) framework는 architecture별 영역에 있던 코드 대부분을 generic 관리 framework로 옮겼다. Architecture별 부분에는 clock source의 저수준 hardware 세부 사항만 남긴다. 각 clock source는 framework에 등록되고 품질을 기준으로 선택된다.
저수준 코드는 hardware setup과 counter read routine을 제공하고 data structure를 초기화한다. Generic timekeeping 코드는 이 data structure를 사용해 hardware clock tick을 나노초 기반 시간 값으로 변환한다. 그 밖의 timekeeping 기능은 모두 generic code로 이동했다. GTOD 기반 patch는 Linux 2.6.18에 merge되었다.
GTOD에 관한 추가 정보는 J. Stultz, D. V. Hart, N. Aravamudan이 작성한 OLS 2005 논문 “We Are Not Getting Any Younger: A New Approach to Time and Timers”와 OLS 발표 자료 18쪽의 그림 3에서 확인할 수 있다.
clock event 관리가 해결하는 문제
69-91Clock source는 단조 증가하는 시간 값을 읽게 해 주고, clock event device는 다음 event interrupt를 예약하는 데 사용된다. 당시의 다음 event는 compile time에 정한 주기를 갖는 periodic event였다. 여러 event-driven 기능에 사용할 device의 setup과 선택이 architecture-dependent code에 고정되어 있었다.
그 결과 architecture마다 코드가 중복되었고, 이미 architecture에 내장된 것과 다른 event interrupt device를 사용하도록 구성을 바꾸기 매우 어려웠다. 고해상도 timer나 dynamic tick 같은 기능을 추가하려면 모든 architecture별 구현을 수정해야 한다는 문제도 있었다.
Clock events subsystem은 clock event device와 여러 kernel 기능에서의 사용을 generic하게 관리해 이 문제를 해결한다. Architecture-dependent code를 순수한 hardware 처리로 줄이고 새 device를 쉽게 추가하고 활용하는 것이 목표다. Generic 기능을 거의 본질적으로 hardware 의존적인 interrupt service handler 직전까지 제공하여 architecture 사이의 중복도 줄인다.
clock event device 등록과 역할 배정
93-123Clock event device는 architecture-dependent boot code 또는 module 삽입 시점에 등록된다. 각 device는 자신의 특성 parameter와 callback function으로 data structure를 채운다. 관리 계층은 이 property parameter를 사용해 device가 지원할 system function 집합을 결정하며, per-CPU device와 system-global device도 이때 구분한다.
System-global event device는 Linux periodic tick에 사용한다. Per-CPU event device는 process accounting, profiling, 고해상도 timer 같은 CPU-local 기능을 제공한다.
- system-global periodic tick: jiffies 갱신
- CPU-local update_process_times
- CPU-local profiling
- CPU-local next-event interrupt: non-periodic mode
Clock event device는 timer interrupt 관련 기능의 선택을 관리 계층에 완전히 위임한다. 관리 계층은 device description structure에 function pointer를 저장하며 hardware-level handler는 이 pointer를 호출해야 한다. 이 구조는 architecture별 timer interrupt handler의 중복 코드를 없애고, device 제어와 timer 기능 배정을 core code로 옮긴다.
Clock event layer API는 작다. Device 등록 interface 외에 다음 event interrupt 예약, clock event device notification service, suspend와 resume 지원을 제공한다.
공통 계층 도입의 비용과 architecture 전환
125-139당시 framework는 약 700줄을 추가하여 kernel binary 크기를 약 2KB 늘렸다. 반면 i386 전환에서는 약 100줄을 제거했고 binary도 약 400byte 줄었다. 문서는 architecture 간 중복 제거와 유연성 향상이 이 작은 크기 증가를 정당화한다고 설명한다.
Architecture를 이 framework로 전환해도 기능 동작 자체는 달라지지 않는다. 그러나 전환 뒤에는 clock event device나 timer interrupt code를 다시 바꾸지 않고도 고해상도 timer와 dynamic tick을 사용할 수 있다. Architecture별 Kconfig에 kernel/time/Kconfig를 포함하고 idle routine에 dynamic tick 관련 호출 세 줄을 추가하면 된다. 이 전환은 OLS 발표 자료 20쪽의 그림 4에 나타나 있다.
부팅 중 고해상도 mode로 전환
142-157System boot 초기에는 고해상도 timer를 사용할 수 없다. 가능하게 만들기 어렵기도 하고 실질적인 이점도 없다. 고해상도 기능이 동작하려면 clock event device framework, clock source framework(GTOD), hrtimer 자체를 먼저 초기화하고 적절한 clock source와 clock event device를 등록해야 한다.
hrtimer 초기화가 끝날 때까지 system은 기존의 저해상도 periodic mode로 동작한다. Clock source와 clock event device layer는 새 hardware를 사용할 수 있음을 hrtimer에 알리는 notification function을 제공한다. hrtimer는 등록된 clock source와 event device가 적합한지 검증한 뒤 고해상도 mode로 전환한다. 따라서 CONFIG_HIGH_RES_TIMERS를 켠 kernel도 필요한 hardware가 없는 system에서 동작할 수 있다.
SMP 제약과 next-event 재설정
159-172고해상도 timer code는 global clock event device만 있는 SMP machine을 지원하지 않는다. 이런 hardware를 지원하려면 interrupt가 발생할 때 IPI를 보내야 하며 overhead가 이점보다 훨씬 크다. 문서 작성 당시 C3 power state에서 local APIC가 멈추는 i386 SMP system에서 고해상도 timer와 dynamic tick을 비활성화한 이유다. 우회 방법의 구상은 있었지만 구현되지는 않았다.
Timer를 시간순으로 삽입하므로 새 timer가 들어왔을 때 event device를 다시 program해야 하는지 판단할 수 있다. 판단은 timer base별로 수행하며 support function이 per-CPU timer base 사이를 동기화한다. 설계상 per-CPU timer base마다 별도의 per-CPU clock event device를 쓸 수 있지만, 당시 구현은 CPU마다 재설정 가능한 device 하나만 사용했다.
timer interrupt와 callback 실행
174-205Timer interrupt가 발생하면 clock event distribution code가 next-event interrupt handler를 호출한다. Handler는 만료된 timer를 red-black tree에서 별도의 이중 연결 list로 옮기고 softirq handler를 호출한다.
hrtimer structure의 추가 mode field를 사용하면 callback을 next-event interrupt handler에서 직접 실행할 수 있다. Hard interrupt context에서 안전하게 실행할 수 있는 코드로 제한되며 nanosleep의 일반적인 wakeup function이 대표적이다. Interrupt context에서 직접 실행하면 interrupted context에서 softirq로, 다시 깨어난 task로 이어지는 최대 두 번의 context switch를 피할 수 있다.
System이 고해상도 mode로 전환하면 기존 periodic tick을 끈다. 이에 따라 i386 SMP의 PIT 같은 system-global periodic clock event device가 비활성화된다.
Periodic tick 기능은 per-CPU hrtimer가 대신한다. Callback은 next-event interrupt context에서 실행되어 jiffies를 갱신하고 update_process_times와 profiling을 호출한다. hrtimer 기반 periodic tick은 dynamic tick으로 확장할 수 있게 설계되었다. UP system에서는 clock event device 하나로 고해상도 timer와 periodic event(jiffies tick, profiling, process accounting)를 모두 예약할 수 있다. 이 방식은 i386의 PIT와 PPC의 Incrementer에서 동작이 입증되었다.
hrtimer queue 실행과 callback 처리를 담당하는 softirq는 tick-bound timer softirq에서 분리했다. itimer와 POSIX interval timer가 사용하는 고해상도 timer signal을 더 정확하게 전달하기 위해서다. 다른 softirq 때문에 이 softirq도 지연될 수 있지만 분리 후 전체 latency는 크게 개선되었다. 이 변화는 OLS 발표 자료 22쪽의 그림 5에 나타나 있다.
Dynamic tick: idle 진입과 다음 event 계산
208-227Dynamic tick은 hrtimer 기반 periodic tick 대체물인 sched_tick에서 자연스럽게 이어진 기능이다. sched_tick hrtimer는 hrtimer_stop_sched_tick, hrtimer_restart_sched_tick, hrtimer_update_jiffies의 세 function으로 확장된다.
hrtimer_stop_sched_tick()
hrtimer_restart_sched_tick()
hrtimer_update_jiffies()CPU가 idle state로 들어갈 때 hrtimer_stop_sched_tick()을 호출한다. 이 function은 hrtimer와 timer wheel 양쪽에서 다음으로 예약된 event를 찾는다. 가장 가까운 event가 다음 tick보다 뒤라면 sched_tick을 그 미래 시점으로 다시 program하여 쓸모없는 periodic tick interrupt 없이 더 오래 idle sleep할 수 있게 한다.
Idle 중 reschedule을 일으키지 않는 interrupt가 발생했을 때도 이 function을 호출한다. Interrupt handler가 이전 hrtimer_stop_sched_tick() 호출에서 찾은 가장 가까운 event보다 먼저 만료되는 새 timer를 등록했을 수 있기 때문이다.
Dynamic tick: idle 이탈과 jiffies 갱신
229-239CPU가 idle state를 벗어나 schedule()을 호출하기 전에 hrtimer_restart_sched_tick()을 호출한다. 이 function은 periodic tick을 재개하며, tick은 다음 hrtimer_stop_sched_tick() 호출까지 활성 상태로 유지된다.
Idle 중 interrupt가 발생하면 irq_enter()에서 hrtimer_update_jiffies()를 호출한다. jiffies를 최신 상태로 맞춰 interrupt handler가 오래된 jiffy 값을 직접 처리하지 않아도 되게 한다.
Dynamic tick 기능은 /proc/stat을 통해 userspace에 통계 값을 노출하며, 이를 향상된 power management 제어에 활용할 수 있다.
향후 확장 방향과 초기 architecture 지원
241-250이 구현은 scheduler가 time slice를 제어하는 완전한 tickless system, 가변 주파수 profiling, 장래의 jiffies 완전 제거 같은 후속 개발을 위한 여지를 남겼다.
초기 제출은 i386을 지원했으며 patchset은 이미 x86_64와 ARM으로 확장되었다. MIPS와 PowerPC에 대한 초기 작업 중 지원도 존재했다.
원문 서명: Thomas, Ingo
시간 계층의 분리
highres.rst:1-68High-resolution timer는 하나의 빠른 hardware timer만으로 생기지 않습니다. Clocksource가 시간을 측정하고, timekeeping이 cycle을 시간 단위로 누적하며, hrtimer가 deadline을 정렬하고, clockevent가 가장 이른 deadline에 interrupt를 발생시켜야 합니다.
Generic layer는 architecture마다 흩어진 time-of-day와 timer interrupt code를 공통 interface로 분리합니다. Hardware driver는 counter와 event programming 능력을 설명하고 core가 one-shot 가능 여부와 rating을 보고 조합합니다.