요약·해설과 원문, 전문 번역을 서로 분리했습니다. API 이름, symbol, source path는 원문 표기를 사용합니다.
1. 요약·해설
원문의 핵심 논리와 kernel programming 관점의 보충 설명입니다. 아래의 전문 번역과는 별도로 작성했습니다.
Per-CPU RB-tree와 expiry queue
hrtimers.rst:78-132각 CPU hrtimer base는 active timer를 expiry 기준 RB-tree에 넣습니다. 가장 왼쪽 node가 다음 deadline이고 clockevent를 그 시점으로 programming합니다. Timer start, cancel과 migration은 base lock과 callback state를 함께 다룹니다.
Absolute CLOCK_REALTIME timer는 wall clock 변경의 영향을 받고 monotonic timer는 boot 이후 단조 시간에 기반합니다. Suspend 포함 여부가 필요한 경우 boottime clock을 선택하는 등 clock ID semantics가 callback 정밀도만큼 중요합니다.
Soft expiry와 hard expiry
hrtimers.rst:133-142Hrtimer는 가장 이른 soft expiry와 반드시 넘지 말아야 할 hard expiry range를 가질 수 있습니다. Scheduler가 range 안에서 여러 timer를 합쳐 interrupt 수를 줄이되 hard deadline은 지킵니다.
정밀도와 race 검증
hrtimers.rst:143-174Timer test는 평균 오차뿐 아니라 최대 late expiry, CPU migration, cancel과 callback 동시 실행, clock set과 suspend/resume을 확인해야 합니다. Callback에서 sleep할 수 있는지는 hrtimer execution mode와 후속 work handoff 설계에 따라 결정됩니다.
2. 영어 원문 전체
번역 기준이 된 Linux v6.18.37 원문입니다. 줄 번호는 이 버전의 파일 좌표입니다.
원문 전체 펼치기
======================================================
hrtimers - subsystem for high-resolution kernel timers
======================================================
This patch introduces a new subsystem for high-resolution kernel timers.
One might ask the question: we already have a timer subsystem
(kernel/timers.c), why do we need two timer subsystems? After a lot of
back and forth trying to integrate high-resolution and high-precision
features into the existing timer framework, and after testing various
such high-resolution timer implementations in practice, we came to the
conclusion that the timer wheel code is fundamentally not suitable for
such an approach. We initially didn't believe this ('there must be a way
to solve this'), and spent a considerable effort trying to integrate
things into the timer wheel, but we failed. In hindsight, there are
several reasons why such integration is hard/impossible:
- the forced handling of low-resolution and high-resolution timers in
the same way leads to a lot of compromises, macro magic and #ifdef
mess. The timers.c code is very "tightly coded" around jiffies and
32-bitness assumptions, and has been honed and micro-optimized for a
relatively narrow use case (jiffies in a relatively narrow HZ range)
for many years - and thus even small extensions to it easily break
the wheel concept, leading to even worse compromises. The timer wheel
code is very good and tight code, there's zero problems with it in its
current usage - but it is simply not suitable to be extended for
high-res timers.
- the unpredictable [O(N)] overhead of cascading leads to delays which
necessitate a more complex handling of high resolution timers, which
in turn decreases robustness. Such a design still leads to rather large
timing inaccuracies. Cascading is a fundamental property of the timer
wheel concept, it cannot be 'designed out' without inevitably
degrading other portions of the timers.c code in an unacceptable way.
- the implementation of the current posix-timer subsystem on top of
the timer wheel has already introduced a quite complex handling of
the required readjusting of absolute CLOCK_REALTIME timers at
settimeofday or NTP time - further underlying our experience by
example: that the timer wheel data structure is too rigid for high-res
timers.
- the timer wheel code is most optimal for use cases which can be
identified as "timeouts". Such timeouts are usually set up to cover
error conditions in various I/O paths, such as networking and block
I/O. The vast majority of those timers never expire and are rarely
recascaded because the expected correct event arrives in time so they
can be removed from the timer wheel before any further processing of
them becomes necessary. Thus the users of these timeouts can accept
the granularity and precision tradeoffs of the timer wheel, and
largely expect the timer subsystem to have near-zero overhead.
Accurate timing for them is not a core purpose - in fact most of the
timeout values used are ad-hoc. For them it is at most a necessary
evil to guarantee the processing of actual timeout completions
(because most of the timeouts are deleted before completion), which
should thus be as cheap and unintrusive as possible.
The primary users of precision timers are user-space applications that
utilize nanosleep, posix-timers and itimer interfaces. Also, in-kernel
users like drivers and subsystems which require precise timed events
(e.g. multimedia) can benefit from the availability of a separate
high-resolution timer subsystem as well.
While this subsystem does not offer high-resolution clock sources just
yet, the hrtimer subsystem can be easily extended with high-resolution
clock capabilities, and patches for that exist and are maturing quickly.
The increasing demand for realtime and multimedia applications along
with other potential users for precise timers gives another reason to
separate the "timeout" and "precise timer" subsystems.
Another potential benefit is that such a separation allows even more
special-purpose optimization of the existing timer wheel for the low
resolution and low precision use cases - once the precision-sensitive
APIs are separated from the timer wheel and are migrated over to
hrtimers. E.g. we could decrease the frequency of the timeout subsystem
from 250 Hz to 100 HZ (or even smaller).
hrtimer subsystem implementation details
----------------------------------------
the basic design considerations were:
- simplicity
- data structure not bound to jiffies or any other granularity. All the
kernel logic works at 64-bit nanoseconds resolution - no compromises.
- simplification of existing, timing related kernel code
another basic requirement was the immediate enqueueing and ordering of
timers at activation time. After looking at several possible solutions
such as radix trees and hashes, we chose the red black tree as the basic
data structure. Rbtrees are available as a library in the kernel and are
used in various performance-critical areas of e.g. memory management and
file systems. The rbtree is solely used for time sorted ordering, while
a separate list is used to give the expiry code fast access to the
queued timers, without having to walk the rbtree.
(This separate list is also useful for later when we'll introduce
high-resolution clocks, where we need separate pending and expired
queues while keeping the time-order intact.)
Time-ordered enqueueing is not purely for the purposes of
high-resolution clocks though, it also simplifies the handling of
absolute timers based on a low-resolution CLOCK_REALTIME. The existing
implementation needed to keep an extra list of all armed absolute
CLOCK_REALTIME timers along with complex locking. In case of
settimeofday and NTP, all the timers (!) had to be dequeued, the
time-changing code had to fix them up one by one, and all of them had to
be enqueued again. The time-ordered enqueueing and the storage of the
expiry time in absolute time units removes all this complex and poorly
scaling code from the posix-timer implementation - the clock can simply
be set without having to touch the rbtree. This also makes the handling
of posix-timers simpler in general.
The locking and per-CPU behavior of hrtimers was mostly taken from the
existing timer wheel code, as it is mature and well suited. Sharing code
was not really a win, due to the different data structures. Also, the
hrtimer functions now have clearer behavior and clearer names - such as
hrtimer_try_to_cancel() and hrtimer_cancel() [which are roughly
equivalent to timer_delete() and timer_delete_sync()] - so there's no direct
1:1 mapping between them on the algorithmic level, and thus no real
potential for code sharing either.
Basic data types: every time value, absolute or relative, is in a
special nanosecond-resolution 64bit type: ktime_t.
(Originally, the kernel-internal representation of ktime_t values and
operations was implemented via macros and inline functions, and could be
switched between a "hybrid union" type and a plain "scalar" 64bit
nanoseconds representation (at compile time). This was abandoned in the
context of the Y2038 work.)
hrtimers - rounding of timer values
-----------------------------------
the hrtimer code will round timer events to lower-resolution clocks
because it has to. Otherwise it will do no artificial rounding at all.
one question is, what resolution value should be returned to the user by
the clock_getres() interface. This will return whatever real resolution
a given clock has - be it low-res, high-res, or artificially-low-res.
hrtimers - testing and verification
-----------------------------------
We used the high-resolution clock subsystem on top of hrtimers to verify
the hrtimer implementation details in praxis, and we also ran the posix
timer tests in order to ensure specification compliance. We also ran
tests on low-resolution clocks.
The hrtimer patch converts the following kernel functionality to use
hrtimers:
- nanosleep
- itimers
- posix-timers
The conversion of nanosleep and posix-timers enabled the unification of
nanosleep and clock_nanosleep.
The code was successfully compiled for the following platforms:
i386, x86_64, ARM, PPC, PPC64, IA64
The code was run-tested on the following platforms:
i386(UP/SMP), x86_64(UP/SMP), ARM, PPC
hrtimers were also integrated into the -rt tree, along with a
hrtimers-based high-resolution clock implementation, so the hrtimers
code got a healthy amount of testing and use in practice.
Thomas Gleixner, Ingo Molnar
3. 한국어 전문 번역
영어 원문의 문단 순서와 의미를 유지한 전체 번역입니다. 코드, 함수명, symbol과 URL은 원문 표기를 유지합니다.
Timer wheel과 hrtimer를 분리한 이유
1-16이 문서는 high-resolution kernel timer를 위한 별도 hrtimer subsystem을 도입한 이유를 설명한다. 기존 kernel/timers.c에 high-resolution과 high-precision 기능을 통합하려는 여러 구현을 실제로 시험했지만 timer wheel의 기본 구조가 이 목적에 맞지 않는다는 결론에 도달했다.
처음에는 기존 wheel 안에서 해결할 방법이 있을 것이라 보고 상당한 노력을 들였지만 실패했다. 그 통합이 어렵거나 사실상 불가능한 이유가 이어진다.
Timer wheel의 구조적 한계
18-56- Low-resolution timer와 high-resolution timer를 같은 방식으로 처리하면 타협, macro magic, #ifdef가 크게 늘어난다. timers.c는 jiffies와 32-bit 가정, 좁은 HZ 범위에 맞춘 용도로 오랜 기간 최적화되어 작은 확장도 wheel 개념을 쉽게 훼손한다. 기존 timeout 용도에서는 매우 좋은 code지만 high-resolution timer 확장에는 적합하지 않다.
- Cascading에는 예측하기 어려운 O(N) 비용이 있고 이 지연 때문에 high-resolution timer 처리가 복잡해지며 견고성이 떨어진다. Timer wheel의 본질인 cascading을 제거하면 timers.c의 다른 부분을 받아들일 수 없을 정도로 악화시키게 된다.
- Timer wheel 위에 구현한 기존 POSIX timer는 settimeofday 또는 NTP로 시간이 바뀔 때 absolute CLOCK_REALTIME timer를 다시 조정하는 복잡한 처리를 이미 추가했다. 이는 wheel 자료 구조가 high-resolution timer에 지나치게 경직되어 있다는 실제 사례다.
- Timer wheel은 networking과 block I/O의 error condition을 감시하는 timeout에 가장 적합하다. 이런 timer 대부분은 정상 event가 먼저 도착해 만료 전에 삭제되므로 거의 expire하거나 recascade되지 않는다. 정확한 시간보다 granularity를 받아들이는 대신 overhead가 사실상 0에 가깝기를 기대하며, 실제 timeout 완료를 가능한 한 저렴하게 보장하는 것이 목적이다.
정밀 timer의 사용자와 subsystem 분리 효과
58-76Precision timer의 주된 사용자는 nanosleep, POSIX timer, itimer interface를 쓰는 userspace application이다. 정확한 timed event가 필요한 multimedia driver와 kernel subsystem도 별도 high-resolution timer subsystem의 이점을 얻는다.
문서가 작성된 당시 subsystem 자체가 high-resolution clock source까지 제공하지는 않았지만 그 기능으로 쉽게 확장할 수 있었고 관련 patch도 빠르게 성숙 중이었다. Real-time과 multimedia application의 수요 증가는 timeout과 precise timer subsystem을 분리할 또 다른 이유였다.
Precision-sensitive API를 hrtimer로 옮기면 기존 timer wheel을 low-resolution, low-precision 용도에 더 공격적으로 최적화할 수 있다. 예를 들어 timeout subsystem 주파수를 250 Hz에서 100 Hz 또는 그보다 낮게 줄이는 선택도 가능해진다.
64-bit nanosecond와 rbtree
78-101- 설계는 단순해야 한다.
- 자료 구조를 jiffy나 다른 granularity에 결합하지 않는다. 모든 kernel logic은 타협 없이 64-bit nanosecond resolution으로 동작한다.
- 기존 time 관련 kernel code를 단순화한다.
또 다른 기본 요구는 timer를 activate할 때 즉시 enqueue하고 시간순으로 정렬하는 것이다. Radix tree와 hash 등을 검토한 뒤 기본 자료 구조로 red-black tree를 선택했다. Rbtree는 kernel library로 제공되고 memory management와 file system 같은 성능 핵심 영역에서도 사용된다.
Rbtree는 시간순 정렬에만 사용한다. Expiry code가 tree 전체를 순회하지 않고 queue의 timer에 빠르게 접근하도록 별도의 list를 둔다. 이 list는 나중에 high-resolution clock을 도입해 time order를 유지하면서 pending queue와 expired queue를 분리할 때도 유용하다.
Absolute CLOCK_REALTIME timer 단순화
103-114시간순 enqueue는 high-resolution clock만을 위한 것이 아니다. Low-resolution CLOCK_REALTIME 기반 absolute timer 처리도 단순해진다.
기존 구현은 armed absolute CLOCK_REALTIME timer 전체를 별도 list와 복잡한 lock으로 관리했다. settimeofday나 NTP로 시간이 바뀌면 모든 timer를 dequeue하고 하나씩 보정한 뒤 다시 enqueue해야 했다.
Expiry time을 absolute time unit으로 저장해 rbtree에 시간순 enqueue하면 clock을 바꿀 때 rbtree를 건드릴 필요가 없다. 확장성이 나쁜 복잡한 code가 POSIX timer 구현에서 사라지고 일반적인 POSIX timer 처리도 단순해진다.
Per-CPU locking, API, ktime_t
116-131Hrtimer의 locking과 per-CPU 동작은 성숙하고 용도에 맞는 기존 timer wheel code를 주로 따랐다. 하지만 자료 구조가 달라 code 자체를 공유하는 이점은 없었다.
hrtimer_try_to_cancel()과 hrtimer_cancel()은 대략 timer_delete()와 timer_delete_sync()에 대응하지만 동작과 이름이 더 명확하다. Algorithm 수준에서 직접적인 1:1 mapping이 없으므로 code 공유 가능성도 크지 않다.
Absolute와 relative를 막론하고 모든 time 값은 nanosecond resolution의 특수한 64-bit type인 ktime_t로 표현한다. 과거에는 macro와 inline function을 이용해 hybrid union과 scalar 64-bit nanosecond 표현을 build 시점에 선택할 수 있었지만 Y2038 작업 과정에서 이 방식은 폐기되었다.
Timer value rounding
133-141Hrtimer code는 lower-resolution clock에 맞추기 위해 불가피한 경우에만 timer event를 rounding한다. 그 밖에는 인위적인 rounding을 전혀 하지 않는다.
clock_getres()는 해당 clock이 실제로 제공하는 resolution을 반환한다. 그 값은 low-resolution, high-resolution, 또는 의도적으로 낮춘 resolution일 수 있다.
시험, 변환된 기능, platform
143-173Hrtimer 구현은 그 위에 high-resolution clock subsystem을 올려 실제로 검증했고 POSIX timer specification 준수 test와 low-resolution clock test도 수행했다.
- nanosleep을 hrtimer로 변환했다.
- itimer를 hrtimer로 변환했다.
- POSIX timer를 hrtimer로 변환했다.
- nanosleep과 POSIX timer 변환으로 nanosleep과 clock_nanosleep 구현을 통합할 수 있었다.
Code는 i386, x86_64, ARM, PPC, PPC64, IA64에서 compile되었고 i386 UP/SMP, x86_64 UP/SMP, ARM, PPC에서 runtime test를 통과했다. Hrtimer 기반 high-resolution clock과 함께 -rt tree에도 통합되어 실제 환경에서 충분한 시험과 사용을 거쳤다. 원문 작성자는 Thomas Gleixner와 Ingo Molnar다.
기존 timer wheel과 분리한 이유
hrtimers.rst:1-77기존 timer wheel은 대부분 timeout이 취소되거나 낮은 해상도로 만료되는 workload를 O(1)에 가깝게 처리하도록 설계되었습니다. Absolute time, nanosecond resolution과 clock adjustment를 억지로 넣으면 cascading과 jiffy 기반 구조가 복잡해집니다.
Hrtimer는 만료 순서가 핵심이므로 64-bit ktime_t와 시간 순으로 정렬되는 자료 구조를 별도로 사용합니다. Timeout wheel과 precision event queue의 목표를 분리해 두 subsystem을 각각 단순화합니다.