<kernel v5.4>
Lowres(Low Resolution) Timer
커널에서 사용하는 jifffies 기반의 타이머 tick을 소프트웨어 기법으로 구현한 타이머이다. 커널이 타이머를 요청할 때 만료 시간을 기재하는데 lowres 타이머는 정확하게 그 만료시점에 깨어나는 것을 보장하지 못하고 요청한 만료 시간의 최대 1/8(12.5%)의 지연된 오차를 가진다. 그 외 특징으로 lowres 타이머는 특정 아키텍처와 무관한 구조이다.
새로운 non-cascading wheel 구조 (v4.8~)
lowres 타이머는 커널 v4.8-rc1 에서 새로운 변화를 보여주면서 lowres 타이머에 대한 전반적인 설계가 변경되어 non-cascading wheel 모델이 소개되었다.
- 타이머 휠에 등록된 타이머들은 cascading 하는 작업이 없어졌으므로 이로 인한 오버헤드가 줄었다.
- fast lookup: 만료 타이머를 찾기 위한 lookup이 빨라졌다.
- slack 관련한 동작과 API들도 더 이상 필요없게되어 삭제되었다.
- 직전 implementation한 로직과 유사하게 요청한 만료 시각에 오차가 발생하는데, 최대 약 1/8(12.5%) 지연된 오차를 가진다.
- 예) 40시간 후에 타이머를 동작시키게 하였지만 4.6시간 더 오래 걸려 타이머가 동작한다.
- 참고:
- timers: Switch to a non-cascading wheel (2016, v4.8-rc1)
- Reinventing the timer wheel | LWN.net
타이머 리스트
admin 권한으로 타이머 리스트를 보려면 다음과 같이 한다. (커널 v4.8~)
$ cat /proc/timer_list Timer List Version: v0.8 HRTIMER_MAX_CLOCK_BASES: 8 now at 79245435304 nsecs cpu: 0 clock 0: .base: (____ptrval____) .index: 0 .resolution: 1 nsecs .get_time: ktime_get .offset: 0 nsecs active timers: #0: <(____ptrval____)>, tick_sched_timer, S:01 # expires at 79260000000-79260000000 nsecs [in 14564696 to 14564696 nsecs] #1: <(____ptrval____)>, it_real_fn, S:01 # expires at 79374561805-79374561805 nsecs [in 129126501 to 129126501 nsecs] #2: <(____ptrval____)>, hrtimer_wakeup, S:01 # expires at 77374835623-79874835623 nsecs [in -1870599681 to 629400319 nsecs] ...
타이머 및 벡터 관리 구조
두 개의 타이머 베이스
다음 그림과 같이 nohz에서 사용하는 타이머 베이스까지 두 개로 나뉘어 관리된다. 스케줄틱이 발생할 때마다 두 개의 타이머 베이스의 만료된 타이머들을 깨워 콜백함수를 호출한다.
다음 그림은 타이머들이 해시 벡터리스트로 구현되어 처리되는 모습을 보여준다. 100hz 시스템의 경우 최대 8 단계, 그 외의 시스템은 최대 9 단계 레벨로 구성된다.
- 각 단계의 단위 틱은 2^(lvl*3) 이다. 즉 레벨 0는 1틱, 레벨 1은 8틱, 레벨 2는 64틱이다.
- 스케줄 틱마다 base->clk의 값도 증가된다. 이 값으로 각 레벨의 해시 인덱스를 산출하고 이 인덱스 값에 따른 타이머들을 깨워 호출한다.
timer_list 구조체
include/linux/timer.h
struct timer_list {
/*
* All fields that change during normal runtime grouped to the
* same cacheline
*/
struct hlist_node entry;
unsigned long expires;
void (*function)(struct timer_list *);
u32 flags;
#ifdef CONFIG_LOCKDEP
struct lockdep_map lockdep_map;
#endif
};
타이머마다 만료 시각과 호출될 콜백 함수 정보가 담겨있다.
- entry
- 동적 타이머들을 타이머 벡터 리스트로 연결 시 사용한다.
- expires
- 타이머가 만료될 미래의 jiffies 시점을 지정한다.
- function
- 타이머 만료 시 실행할 함수의 주소를 저장한다.
- flags
- TIMER_CPUMASK
- 타이머 휠 인덱스 값으로 10비트를 사용하여 저장된다.
- TIMER_MIGRATING
- migration 진행중인 타이머 여부 (타이머 cpu 이동중)
- TIMER_DEFERRABLE
- 지연 타이머 여부
- deferrable 전용 타이머 베이스를 사용한다.
- TIMER_PINNED
- cpu 고정(pinned) 타이머 여부
- TIMER_IRQSAFE
- 타이머가 인터럽트 핸들러에서 사용되지 않음을 나타낸다.
- 인터럽트 latency 성능을 위해 추가되는 플래그로 내부에서 spinlock 시 인터럽트를 disable 하지 않는다.
- TIMER_CPUMASK
timer_base 구조체
tvec_base 구조체명이 timer_base 구조체명으로 변경되었다.
- 참고: timers: Give a few structs and members proper names (2016, v4.8-rc1)
kernel/time/timer.c
struct timer_base {
raw_spinlock_t lock;
struct timer_list *running_timer;
#ifdef CONFIG_PREEMPT_RT
spinlock_t expiry_lock;
atomic_t timer_waiters;
#endif
unsigned long clk;
unsigned long next_expiry;
unsigned int cpu;
bool is_idle;
bool must_forward_clk;
DECLARE_BITMAP(pending_map, WHEEL_SIZE);
struct hlist_head vectors[WHEEL_SIZE];
} ____cacheline_aligned;
타이머들이 관리되는 타이머 베이스는 per-cpu로 관리되며, 타이머 리스트는 해시 벡터 휠로 관리된다.
- lock
- 타이머 벡터 리스트 조작시 사용할 lock
- running_timer
- 타이머가 만료되어 현재 함수를 실행중인 타이머를 가리킨다.
- clk
- 처리할 시각(틱)이다. nohz 상태에 따라 동작이 상이하다.
- nohz가 동작하지 않는 경우 이 시각은 현재 시각(jiffies)과 동일한 값이 되도록 매 스케줄 틱마다 증가된다.
- nohz가 동작하는 경우에는 jiffies 보다 지연될 수 있다. cpu가 nohz에서 탈출할 때 지연된 시간만큼 처리한다.
- 지연된 시간만큼 루프를 반복하며 틱을 처리하면 성능이 떨어지므로 nohz optimization 기법을 사용하여 처리하지 않아도 되는 틱은 생략하게 한다.
- 처리할 시각(틱)이다. nohz 상태에 따라 동작이 상이하다.
- next_expiry
- 다음 만료될 타이머의 시각(틱)
- cpu
- 현재 타이머 벡터 관리가 동작하는 cpu id
- is_idle
- 타이머 베이스의 idle 상태
- must_forward_clk
- nohz에서 타이머 베이스의 clk를 forward 한다. (nohz optimization)
- pending_map
- 펜딩 비트맵으로 타이머 휠 인덱스마다 1비트를 사용한다.
- 타이머 휠의 인덱스 비트가 1로 설정되면 타이머가 1 개 이상이 대기중임을 의미한다.
- vectors[]
- 타이머들이 대기하는 타이머 휠 리스트이며, 해시 벡터로 구현되었다.
timer_bases[]
kernel/time/timer.c
static DEFINE_PER_CPU(struct timer_base, timer_bases[NR_BASES]);
timer_base는 성능향상을 위해 per-cpu를 사용하여 관리한다. nohz를 사용하지 않으면 하나의 타이머 베이스에 관리된다. 그러나 nohz를 사용하는 경우 다음과 같이 두 개의 타이머 휠로 나누어 관리된다.
- BASE_STD
- 기본(standard) 타이머를 위해 사용된다.
- BASE_DEF
- defferable 타이머를 위해 사용된다.
jiffies & 초기값
jiffies 값은 스케줄 틱이 발생할 때 마다 1씩 증가한다. 스케줄 틱은 CONFIG_HZ에 정한 시간에 한 번씩 발생한다.
- 예) 100hz 시스템인 경우 1초에 100번의 스케줄 틱이 발생한다. 따라서 10ms 주기마다 1 tick이 발생하고 jiffies 값도 1씩 증가된다.
INITIAL_JIFFIES
include/linux/jiffies.h
/* * Have the 32 bit jiffies value wrap 5 minutes after boot * so jiffies wrap bugs show up earlier. */
#define INITIAL_JIFFIES ((unsigned long)(unsigned int) (-300*HZ))
jiffies 초기값은 32bit 시스템에서 부트 후 약 5분이내에 overflow 될 수 있는 값을 주었다. 64비트 시스템에서는 overflow되려면 어마 어마한 시간이 흘러야 하므로 overflow될 걱정이 없다.
- 초기값
- 32bit 예) HZ=250
- 0xfffe_db08 (-75000)
- 64bit 예) HZ=250
- 0x0000_0000_fffe_db08
- 32bit 예) HZ=250
APIs
주요 API
컴파일 타임에 정적으로 타이머 생성 및 초기화
- DEFINE_TIMER()
런타임에 동적으로 타이머 생성 및 초기화
- timer_setup()
- timer_setup_on_stack()
타이머 베이스에 타이머 추가/변경/삭제
- add_timer()
- mod_timer()
- del_timer()
시간 비교 API
jiffies 값을 읽어 시간을 직접 비교하는 경우 jiffies overflow 되는 시점에서 시간 비교가 의도치 않는 반대의 결과를 얻을 수 있다. 따라서 다음 함수들을 사용하여야 정확한 결과를 나타내게 할 수 있으므로 절대 jiffies 시간을 직접 비교 사용하는 일이 없도록 해야 한다.
- 2개 시간 비교 함수
- time_before(a,b)
- a가 b 보다 먼저 시간값이면 true
- time_after(a,b)
- a가 b 보다 나중 시간값이면 true
- time_before_eq(a,b)
- a 가 b보다 먼저이거나 같은 시간이면 true
- time_after_eq(a,b)
- a 가 b 보다 나중이거나 같은 시간이면 true
- time_before(a,b)
- jiffies와 시간 비교 함수
- time_is_before_jiffies(a)
- a가 jiffies 보다 먼저 시간값이면 true
- time_is_after_jiffies(a)
- a가 jiffies 보다 나중 시간값이면 true
- time_is_before_eq_jiffies(a)
- a 가 jiffies 보다 먼저이거나 같은 시간이면 true
- time_is_after_eq_jiffies(a)
- a 가 jiffies 보다 나중이거나 같은 시간이면 true
- time_is_before_jiffies(a)
관련 API
- msleep()
- msleep_interruptible()
- schedule_timeout_interruptible()
- schedule_timeout_killable()
- schedule_timeout_uninterruptible()
- schedule_timeout_idle()
- schedule_timeout()
타이머 추가/삭제
타이머 추가
add_timer()
kernel/time/timer.c
/** * add_timer - start a timer * @timer: the timer to be added * * The kernel will do a ->function(->data) callback from the * timer interrupt at the ->expires point in the future. The * current time is 'jiffies'. * * The timer's ->expires, ->function (and if the handler uses it, ->data) * fields must be set prior calling this function. * * Timers with an ->expires field in the past will be executed in the next * timer tick. */
void add_timer(struct timer_list *timer)
{
BUG_ON(timer_pending(timer));
mod_timer(timer, timer->expires);
}
EXPORT_SYMBOL(add_timer);
동적 타이머를 요청한다.
- mod_timer()를 호출하여 만료 시간을 변경한다.
타이머 삭제
del_timer()
kernel/time/timer.c
/** * del_timer - deactive a timer. * @timer: the timer to be deactivated * * del_timer() deactivates a timer - this works on both active and inactive * timers. * * The function returns whether it has deactivated a pending timer or not. * (ie. del_timer() of an inactive timer returns 0, del_timer() of an * active timer returns 1.) */
int del_timer(struct timer_list *timer)
{
struct tvec_base *base;
unsigned long flags;
int ret = 0;
debug_assert_init(timer);
if (timer_pending(timer)) {
base = lock_timer_base(timer, &flags);
ret = detach_if_pending(timer, base, true);
spin_unlock_irqrestore(&base->lock, flags);
}
return ret;
}
EXPORT_SYMBOL(del_timer);
타이머를 타이머 베이스에서 제거하여 비활성화한다.
- 코드 라인 7에서 타이머에서 사용자 트래킹 정보를 클리어한다.
- 코드 라인 9~13에서 타이머 벡터 리스트에 등록되어 대기중인 타이머인 경우 그 리스트에서 제거한다.
- 코드 라인 15에서 타이머가 활성화 상태였었으면 1을 반환하고, 그렇지 않은 경우 0을 반환한다.
펜딩 타이머 제거
detach_if_pending()
kernel/time/timer.c
static int detach_if_pending(struct timer_list *timer, struct timer_base *base,
bool clear_pending)
{
unsigned idx = timer_get_idx(timer);
if (!timer_pending(timer))
return 0;
if (hlist_is_singular_node(&timer->entry, base->vectors + idx))
__clear_bit(idx, base->pending_map);
detach_timer(timer, clear_pending);
return 1;
}
펜딩된 타이머인 경우 리스트에서 제거한다. 활동(pending) 중인 타이머를 제거한 경우 1을 반환한다.
- 코드 라인 6~7에서 타이머 벡터 리스트에 등록되어 대기하고 있는 타이머가 아닌 경우 이미 deactivate된 경우이므로 0을 반환한다.
- 코드 라인 9~10에서 타이머의 인덱스에 해당하는 타이머 벡터 리스트에 자신 1건만 등록된 경우라면 해당 인덱스의 펜딩맵을 클리어한다.
- 코드 라인 12~13에서 타이머를 타이머 베이스 휠에서 제거하고 1을 반환한다.
타이머 제거
detach_timer()
kernel/time/timer.c
static inline void detach_timer(struct timer_list *timer, bool clear_pending)
{
struct list_head *entry = &timer->entry;
debug_deactivate(timer);
__hlist_del(entry);
if (clear_pending)
entry->pprev = NULL;
entry->next = LIST_POISON2;
}
타이머 리스트에서 요청 타이머를 제거한다. 만일 clear pending 요청이 있는 경우 타이머 엔트리가 다음 타이머와 연결되지 않도록 분리한다.
타이머 변경
mod_timer()
kernel/time/timer.c
/** * mod_timer - modify a timer's timeout * @timer: the timer to be modified * @expires: new timeout in jiffies * * mod_timer() is a more efficient way to update the expire field of an * active timer (if the timer is inactive it will be activated) * * mod_timer(timer, expires) is equivalent to: * * del_timer(timer); timer->expires = expires; add_timer(timer); * * Note that if there are multiple unserialized concurrent users of the * same timer, then mod_timer() is the only safe way to modify the timeout, * since add_timer() cannot modify an already running timer. * * The function returns whether it has modified a pending timer or not. * (ie. mod_timer() of an inactive timer returns 0, mod_timer() of an * active timer returns 1.) */
int mod_timer(struct timer_list *timer, unsigned long expires)
{
return __mod_timer(timer, expires, 0);
}
EXPORT_SYMBOL(mod_timer);
요청한 타이머를 제거하고 인수로 받은 만료 시점(timerout을 적용한 새 jiffies 시점)으로 조절하고 설정한다. inactive된 타이머도 active 시킨다.
__mod_timer()
kernel/time/timer.c
static inline int
__mod_timer(struct timer_list *timer, unsigned long expires, unsigned int options)
{
struct timer_base *base, *new_base;
unsigned int idx = UINT_MAX;
unsigned long clk = 0, flags;
int ret = 0;
BUG_ON(!timer->function);
/*
* This is a common optimization triggered by the networking code - if
* the timer is re-modified to have the same timeout or ends up in the
* same array bucket then just return:
*/
if (timer_pending(timer)) {
/*
* The downside of this optimization is that it can result in
* larger granularity than you would get from adding a new
* timer with this expiry.
*/
long diff = timer->expires - expires;
if (!diff)
return 1;
if (options & MOD_TIMER_REDUCE && diff <= 0)
return 1;
/*
* We lock timer base and calculate the bucket index right
* here. If the timer ends up in the same bucket, then we
* just update the expiry time and avoid the whole
* dequeue/enqueue dance.
*/
base = lock_timer_base(timer, &flags);
forward_timer_base(base);
if (timer_pending(timer) && (options & MOD_TIMER_REDUCE) &&
time_before_eq(timer->expires, expires)) {
ret = 1;
goto out_unlock;
}
clk = base->clk;
idx = calc_wheel_index(expires, clk);
/*
* Retrieve and compare the array index of the pending
* timer. If it matches set the expiry to the new value so a
* subsequent call will exit in the expires check above.
*/
if (idx == timer_get_idx(timer)) {
if (!(options & MOD_TIMER_REDUCE))
timer->expires = expires;
else if (time_after(timer->expires, expires))
timer->expires = expires;
ret = 1;
goto out_unlock;
}
} else {
base = lock_timer_base(timer, &flags);
forward_timer_base(base);
}
요청한 타이머를 제거하고 최종 결정된 만료 시점으로 타이머를 설정한 후 다시 추가 하고 active 시킨다. 타이머가 active된 상태이면 1로 반환된다.
- 코드 라인 16에서 타이머가 expire 되지 않고 아직 타이머 휠에서 기다리고 있는 중이다.
- 코드 라인 22~27에서 새로운 만료 시각(@expires)으로 변경을 하려할 때 차이가 없으면 1을 결과로 함수를 빠져나간다.
- 만일 만료 시각이 앞당겨졌는데 만료 시각을 앞으로 당기지 못하게 한 MOD_TIMER_REDUCE 옵션을 사용한 경우도 결과를 1로 함수를 빠져나간다.
- 코드 라인 35~45에서 타이머가 등록된 타이머 베이스에서 산출한 타이머 휠 인덱스를 알아온다.
- lock을 획득 한 후 타이머 베이스의 시각(clk)을 forward 하도록 갱신하고, 다시 한번 체크한다. 만료 시각이 앞당겨졌는데 만료 시각을 앞으로 당기지 못하게 한 MOD_TIMER_REDUCE 옵션을 사용한 경우도 결과를 1로 함수를 빠져나간다.
- 코드 라인 52~59에서 타이머가 등록된 타이머 베이스에서 해당 타이머 휠 인덱스와 위에서 산출한 휠 인덱스가 동일하면 만료 시각을 갱신하고 결과를 1로 변경하고 함수를 빠져나간다.
- 코드 라인 60~63에서 요청한 타이머가 타이머 휠에 없는 경우 타이머를 위한 타이머 베이스를 준비하고, 타이머 베이스의 시각(clk)을 forward 하도록 갱신한다.
ret = detach_if_pending(timer, base, false);
if (!ret && (options & MOD_TIMER_PENDING_ONLY))
goto out_unlock;
new_base = get_target_base(base, timer->flags);
if (base != new_base) {
/*
* We are trying to schedule the timer on the new base.
* However we can't change timer's base while it is running,
* otherwise del_timer_sync() can't detect that the timer's
* handler yet has not finished. This also guarantees that the
* timer is serialized wrt itself.
*/
if (likely(base->running_timer != timer)) {
/* See the comment in lock_timer_base() */
timer->flags |= TIMER_MIGRATING;
raw_spin_unlock(&base->lock);
base = new_base;
raw_spin_lock(&base->lock);
WRITE_ONCE(timer->flags,
(timer->flags & ~TIMER_BASEMASK) | base->cpu);
forward_timer_base(base);
}
}
debug_timer_activate(timer);
timer->expires = expires;
/*
* If 'idx' was calculated above and the base time did not advance
* between calculating 'idx' and possibly switching the base, only
* enqueue_timer() and trigger_dyntick_cpu() is required. Otherwise
* we need to (re)calculate the wheel index via
* internal_add_timer().
*/
if (idx != UINT_MAX && clk == base->clk) {
enqueue_timer(base, timer, idx);
trigger_dyntick_cpu(base, timer);
} else {
internal_add_timer(base, timer);
}
out_unlock:
raw_spin_unlock_irqrestore(&base->lock, flags);
return ret;
}
- 코드 라인 1~3에서 pending된 타이머인 경우에 한해 해당 타이머 벡터 리스트에서 제거한다. 실패 시 pending only인 경우 처리를 중단하고 빠져나간다.
- 코드 라인 5~26에서 타이머의 cpu 변경이 필요한 경우 migrating을 한다.
- 코드 라인 30~43에서 타이머의 만료 시점을 갱신하고 적절한 타이머 벡터 리스트에 새로 추가한다.
다음 그림은 타이머를 추가 또는 변경 시 호출되는 __mod_timer() 함수를 통해 타이머 베이스의 벡터 리스트에 타이머가 추가되는 모습을 보여준다.
- 레벨이 올라갈수록 만료 시각에 대한 정확도는 레벨 당 8배 단위로 커지는 Granularity 값만큼 비례하여 떨어진다. 레벨 0의 오차가 8틱 이하였지만, 그 다음 레벨 1은 8배 커진 64틱 이하인것을 확인할 수 있다.
타이머 추가(internal)
internal_add_timer()
kernel/time/timer.c
static void
internal_add_timer(struct timer_base *base, struct timer_list *timer)
{
__internal_add_timer(base, timer);
trigger_dyntick_cpu(base, timer);
}
요청 타이머 베이스에 타이머를 추가한다.
__internal_add_timer()
kernel/time/timer.c
static void
__internal_add_timer(struct timer_base *base, struct timer_list *timer)
{
unsigned int idx;
idx = calc_wheel_index(timer->expires, base->clk);
enqueue_timer(base, timer, idx);
}
요청 타이머 베이스에 타이머를 추가한다.
- 코드 라인 5에서 타이머 베이스에서 사용할 타이머 휠의 인덱스 값을 알아온다.
- 코드 라인 6에서 산출한 인덱스의 테이머 벡터 리스트에 타이머를 추가한다.
- vectors[idx] 리스트 <— 타이머 추가
enqueue_timer()
kernel/time/timer.c
/* * Enqueue the timer into the hash bucket, mark it pending in * the bitmap and store the index in the timer flags. */
static void enqueue_timer(struct timer_base *base, struct timer_list *timer,
unsigned int idx)
{
hlist_add_head(&timer->entry, base->vectors + idx);
__set_bit(idx, base->pending_map);
timer_set_idx(timer, idx);
trace_timer_start(timer, timer->expires, timer->flags);
}
요청 타이머 베이스에서 인덱스에 해당하는 타이머 벡터 리스트에 타이머를 추가한다.
- 코드 라인 4에서 요청 인덱스에 해당하는 타이머 벡터 리스트에 타이머를 추가한다.
- 코드 라인 5에서 펜딩 맵의 인덱스에 해당하는 비트를 설정한다.
- 코드 라인 6에서 타이머의 플래그 중 10비트 공간을 사용하여 인덱스를 기록한다.
timer_set_idx()
kernel/time/timer.c
static inline void timer_set_idx(struct timer_list *timer, unsigned int idx)
{
timer->flags = (timer->flags & ~TIMER_ARRAYMASK) |
idx << TIMER_ARRAYSHIFT;
}
타이머의 플래그 bits[31..22]에 인덱스를 기록한다. (10 비트)
timer_pending()
include/linux/timer.h
/** * timer_pending - is a timer pending? * @timer: the timer in question * * timer_pending will tell whether a given timer is currently pending, * or not. Callers must ensure serialization wrt. other operations done * to this timer, eg. interrupt contexts, or other CPUs on SMP. * * return value: 1 if the timer is pending, 0 if not. */
static inline int timer_pending(const struct timer_list * timer)
{
return timer->entry.pprev != NULL;
}
타이머 벡터 리스트에서 대기중인 타이머인지 여부를 반환한다.
- 타이머 벡터 리스트는 환형 더블리스트이므로 타이머가 혼자 등록되어 있어도 head와 연결되는 구조이다. 따라서 null이 들어가 있는 경우는 환형 더블리스트에서 제거된 경우밖에 없다. 즉 리스트에 존재하면 항상 true이다.
no-hz용 타이머 베이스 시각 forward
forward_timer_base()
kernel/time/timer.c
static inline void forward_timer_base(struct timer_base *base)
{
#ifdef CONFIG_NO_HZ_COMMON
unsigned long jnow;
/*
* We only forward the base when we are idle or have just come out of
* idle (must_forward_clk logic), and have a delta between base clock
* and jiffies. In the common case, run_timers will take care of it.
*/
if (likely(!base->must_forward_clk))
return;
jnow = READ_ONCE(jiffies);
base->must_forward_clk = base->is_idle;
if ((long)(jnow - base->clk) < 2)
return;
/*
* If the next expiry value is > jiffies, then we fast forward to
* jiffies otherwise we forward to the next expiry value.
*/
if (time_after(base->next_expiry, jnow))
base->clk = jnow;
else
base->clk = base->next_expiry;
#endif
}
nohz를 위해 현재 요청한 타이머 베이스의 시각을 forward 한다.
- 코드 라인 11~12에서 nohz를 위해 타이머 베이스가 idle 상태인 경우 타이머 베이스를 forward할 수 있게 하였다. 그 경우가 아니면 함수를 빠져나간다. 다음 함수들에서 must_forward_clk 플래그를 1로 만든다.
- timers_prepare_cpu()
- get_next_timer_interrupt()
- 코드 라인 14~17에서 must_forward_clk 값을 idle 상태에서만 사용할 수 있게 지정한다. 타이머 베이스가 현재 틱과 비교하여 2틱 미만인 경우 함수를 빠져나간다.
- 코드 라인 23~26에서 만료 시각이 아직 남아 있는 경우 타이머 베이스의 시각에 현재 시각을 대입한다. 만일 만료 시각이 지났으면 다음 만료 시각으로 갱신한다.
휠 인덱스 산출
calc_wheel_index()
kernel/time/timer.c
static int calc_wheel_index(unsigned long expires, unsigned long clk)
{
unsigned long delta = expires - clk;
unsigned int idx;
if (delta < LVL_START(1)) {
idx = calc_index(expires, 0);
} else if (delta < LVL_START(2)) {
idx = calc_index(expires, 1);
} else if (delta < LVL_START(3)) {
idx = calc_index(expires, 2);
} else if (delta < LVL_START(4)) {
idx = calc_index(expires, 3);
} else if (delta < LVL_START(5)) {
idx = calc_index(expires, 4);
} else if (delta < LVL_START(6)) {
idx = calc_index(expires, 5);
} else if (delta < LVL_START(7)) {
idx = calc_index(expires, 6);
} else if (LVL_DEPTH > 8 && delta < LVL_START(8)) {
idx = calc_index(expires, 7);
} else if ((long) delta < 0) {
idx = clk & LVL_MASK;
} else {
/*
* Force expire obscene large timeouts to expire at the
* capacity limit of the wheel.
*/
if (expires >= WHEEL_TIMEOUT_CUTOFF)
expires = WHEEL_TIMEOUT_MAX;
idx = calc_index(expires, LVL_DEPTH - 1);
}
return idx;
}
만료 시각과 클럭 베이스의 시각의 차이로 타이머 휠 인덱스 값을 산출한다.
- 코드 라인 3에서 만료 시각과 클럭 베이스의 시각의 차이 틱을 구해 delta에 대입한다.
- 코드 라인 6~7에서 delta 값이 1 레벨 시작 틱 값보다 작은 경우 0 레벨 기준으로 휠 인덱스를 산출한다.
- 코드 라인 8~21에서 delta 값을 사용하여 1~7레벨까지를 기준으로 휠 인덱스를 산출한다.
- 코드 라인 22~23에서 0보다 작은 delta 값에 해당하는 휠 인덱스를 산출한다.
- 코드 라인 24~33에서 범위를 초과하는 delta 값인 경우 최대 값으로 휠 인덱스를 산출한다.
- 코드 라인 34에서 산출한 휠 인덱스를 반환한다.
calc_index()
kernel/time/timer.c
/* * Helper function to calculate the array index for a given expiry * time. */
static inline unsigned calc_index(unsigned expires, unsigned lvl)
{
expires = (expires + LVL_GRAN(lvl)) >> LVL_SHIFT(lvl);
return LVL_OFFS(lvl) + (expires & LVL_MASK);
}
만료 시각과 레벨로 타이머 휠 인덱스를 알아온다.
- 예) expires=0x43c0, lvl=2
- new expires = (0x43c0 + 0x40) >> 6 = 0x110
- return 0x80 + 0x10 = 0x90 (144)
매크로 함수들
kernel/time/timer.c
/* * The timer wheel has LVL_DEPTH array levels. Each level provides an array of * LVL_SIZE buckets. Each level is driven by its own clock and therefor each * level has a different granularity. * * The level granularity is: LVL_CLK_DIV ^ lvl * The level clock frequency is: HZ / (LVL_CLK_DIV ^ level) * * The array level of a newly armed timer depends on the relative expiry * time. The farther the expiry time is away the higher the array level and * therefor the granularity becomes. * * Contrary to the original timer wheel implementation, which aims for 'exact' * expiry of the timers, this implementation removes the need for recascading * the timers into the lower array levels. The previous 'classic' timer wheel * implementation of the kernel already violated the 'exact' expiry by adding * slack to the expiry time to provide batched expiration. The granularity * levels provide implicit batching. * * This is an optimization of the original timer wheel implementation for the * majority of the timer wheel use cases: timeouts. The vast majority of * timeout timers (networking, disk I/O ...) are canceled before expiry. If * the timeout expires it indicates that normal operation is disturbed, so it * does not matter much whether the timeout comes with a slight delay. * * The only exception to this are networking timers with a small expiry * time. They rely on the granularity. Those fit into the first wheel level, * which has HZ granularity. * * We don't have cascading anymore. timers with a expiry time above the * capacity of the last wheel level are force expired at the maximum timeout * value of the last wheel level. From data sampling we know that the maximum * value observed is 5 days (network connection tracking), so this should not * be an issue. * * The currently chosen array constants values are a good compromise between * array size and granularity. * * This results in the following granularity and range levels: * * HZ 1000 steps * Level Offset Granularity Range * 0 0 1 ms 0 ms - 63 ms * 1 64 8 ms 64 ms - 511 ms * 2 128 64 ms 512 ms - 4095 ms (512ms - ~4s) * 3 192 512 ms 4096 ms - 32767 ms (~4s - ~32s) * 4 256 4096 ms (~4s) 32768 ms - 262143 ms (~32s - ~4m) * 5 320 32768 ms (~32s) 262144 ms - 2097151 ms (~4m - ~34m) * 6 384 262144 ms (~4m) 2097152 ms - 16777215 ms (~34m - ~4h) * 7 448 2097152 ms (~34m) 16777216 ms - 134217727 ms (~4h - ~1d) * 8 512 16777216 ms (~4h) 134217728 ms - 1073741822 ms (~1d - ~12d) * * HZ 300 * Level Offset Granularity Range * 0 0 3 ms 0 ms - 210 ms * 1 64 26 ms 213 ms - 1703 ms (213ms - ~1s) * 2 128 213 ms 1706 ms - 13650 ms (~1s - ~13s) * 3 192 1706 ms (~1s) 13653 ms - 109223 ms (~13s - ~1m) * 4 256 13653 ms (~13s) 109226 ms - 873810 ms (~1m - ~14m) * 5 320 109226 ms (~1m) 873813 ms - 6990503 ms (~14m - ~1h) * 6 384 873813 ms (~14m) 6990506 ms - 55924050 ms (~1h - ~15h) * 7 448 6990506 ms (~1h) 55924053 ms - 447392423 ms (~15h - ~5d) * 8 512 55924053 ms (~15h) 447392426 ms - 3579139406 ms (~5d - ~41d) * * HZ 250 * Level Offset Granularity Range * 0 0 4 ms 0 ms - 255 ms * 1 64 32 ms 256 ms - 2047 ms (256ms - ~2s) * 2 128 256 ms 2048 ms - 16383 ms (~2s - ~16s) * 3 192 2048 ms (~2s) 16384 ms - 131071 ms (~16s - ~2m) * 4 256 16384 ms (~16s) 131072 ms - 1048575 ms (~2m - ~17m) * 5 320 131072 ms (~2m) 1048576 ms - 8388607 ms (~17m - ~2h) * 6 384 1048576 ms (~17m) 8388608 ms - 67108863 ms (~2h - ~18h) * 7 448 8388608 ms (~2h) 67108864 ms - 536870911 ms (~18h - ~6d) * 8 512 67108864 ms (~18h) 536870912 ms - 4294967288 ms (~6d - ~49d) * * HZ 100 * Level Offset Granularity Range * 0 0 10 ms 0 ms - 630 ms * 1 64 80 ms 640 ms - 5110 ms (640ms - ~5s) * 2 128 640 ms 5120 ms - 40950 ms (~5s - ~40s) * 3 192 5120 ms (~5s) 40960 ms - 327670 ms (~40s - ~5m) * 4 256 40960 ms (~40s) 327680 ms - 2621430 ms (~5m - ~43m) * 5 320 327680 ms (~5m) 2621440 ms - 20971510 ms (~43m - ~5h) * 6 384 2621440 ms (~43m) 20971520 ms - 167772150 ms (~5h - ~1d) * 7 448 20971520 ms (~5h) 167772160 ms - 1342177270 ms (~1d - ~15d) */
LVL_SHIFT() & LVL_GRAN()
kernel/time/timer.c
/* Clock divisor for the next level */ #define LVL_CLK_SHIFT 3 #define LVL_CLK_DIV (1UL << LVL_CLK_SHIFT) #define LVL_CLK_MASK (LVL_CLK_DIV - 1) #define LVL_SHIFT(n) ((n) * LVL_CLK_SHIFT) #define LVL_GRAN(n) (1UL << LVL_SHIFT(n))
- LVL_SHIFT(n)
- 레벨별 비트 수
- =n * 3
- 레벨별 비트 수
- LVL_GRAN(n)
- 레벨별 틱 단위
- =2^(n*3) 틱
- 예) 0 레벨 = 2^0 = 1 틱
- 예) 1 레벨 = 2^3 = 8 틱
- 예) 2 레벨 = 2^6 = 64 틱
- 예) 3 레벨 = 2^6 = 512 틱
- 예) 4 레벨 = 2^6 = 4096 틱
- 예) 5 레벨 = 2^6 = 32768 틱
- 예) 6 레벨 = 2^6 = 262144 틱
- 예) 7 레벨 = 2^21=2097152 틱
- 예) 8 레벨 = 2^24=16777216 틱
- 레벨별 틱 단위
LVL_OFFS()
kernel/time/timer.c
/* Size of each clock level */ #define LVL_BITS 6 #define LVL_SIZE (1UL << LVL_BITS) #define LVL_MASK (LVL_SIZE - 1) #define LVL_OFFS(n) ((n) * LVL_SIZE)
- LVL_OFFS(n)
- 레벨별 벡터 offset
- = n * 64
- 예) 0 레벨 = 0 * 64 = 0
- 예) 1 레벨 = 1 * 64 = 64
- 예) 2 레벨 = 2 * 64 = 128
- 예) 3 레벨 = 3 * 64 = 192
- 예) 4 레벨 = 4 * 64 = 256
- 예) 5 레벨 = 5 * 64 = 320
- 예) 6 레벨 = 6 * 64 = 384
- 예) 7 레벨 = 7 * 64 = 448
- 예) 8 레벨 = 8 * 64 = 512
- 레벨별 벡터 offset
LVL_START()
kernel/time/timer.c
/* * The time start value for each level to select the bucket at enqueue * time. */
#define LVL_START(n) ((LVL_SIZE - 1) << (((n) - 1) * LVL_CLK_SHIFT))
- 레벨별 시작 틱 값
- = 63 << (n-1) * 3
- 예) 레벨 0 = 63 << (0-1) * 3 = 0 틱
- 예) 레벨 1 = 63 << (1-1) * 3 = 63 틱
- 예) 레벨 2 = 63 << (2-1) * 3 = 504 틱
- 예) 레벨 3 = 63 << (3-1) * 3 =4032 틱
- 예) 레벨 4 = 63 << (4-1) * 3 =32256 틱
- 예) 레벨 5 = 63 << (5-1) * 3 = 258048 틱
- 예) 레벨 6 = 63 << (6-1) * 3 = 2064384 틱
- 예) 레벨 7 = 63 << (7-1) * 3 = 16515072 틱
- 예) 레벨 8 = 63 << (8-1) * 3 = 132120576 틱
- = 63 << (n-1) * 3
타이머 베이스
타이머 베이스 락 획득
lock_timer_base()
kernel/time/timer.c
/* * We are using hashed locking: Holding per_cpu(timer_bases[x]).lock means * that all timers which are tied to this base are locked, and the base itself * is locked too. * * So __run_timers/migrate_timers can safely modify all timers which could * be found in the base->vectors array. * * When a timer is migrating then the TIMER_MIGRATING flag is set and we need * to wait until the migration is done. */
static struct timer_base *lock_timer_base(struct timer_list *timer,
unsigned long *flags)
__acquires(timer->base->lock)
{
for (;;) {
struct timer_base *base;
u32 tf;
/*
* We need to use READ_ONCE() here, otherwise the compiler
* might re-read @tf between the check for TIMER_MIGRATING
* and spin_lock().
*/
tf = READ_ONCE(timer->flags);
if (!(tf & TIMER_MIGRATING)) {
base = get_timer_base(tf);
raw_spin_lock_irqsave(&base->lock, *flags);
if (timer->flags == tf)
return base;
raw_spin_unlock_irqrestore(&base->lock, *flags);
}
cpu_relax();
}
}
타이머가 사용할 현재 cpu의 타이머 베이스 락을 획득한다.
- 만일 타이머가 migration 중이면 TIMER_MIGRATING 플래그를 사용하는데 이 플래그가 없어질 때까지 루프를 반복하며 lock을 잡을 때까지 기다린다.
- 또한 lock을 잡은 후에 플래그가 변경된 경우 루프를 반복한다.
타이머 베이스 알아오기
get_timer_base()
kernel/time/timer.c
static inline struct timer_base *get_timer_base(u32 tflags)
{
return get_timer_cpu_base(tflags, tflags & TIMER_CPUMASK);
}
현재 cpu에 대한 타이머 베이스를 반환한다.
get_target_base()
kernel/time/timer.c
static inline struct timer_base *
get_target_base(struct timer_base *base, unsigned tflags)
{
#if defined(CONFIG_SMP) && defined(CONFIG_NO_HZ_COMMON)
if (static_branch_likely(&timers_migration_enabled) &&
!(tflags & TIMER_PINNED))
return get_timer_cpu_base(tflags, get_nohz_timer_target());
#endif
return get_timer_this_cpu_base(tflags);
}
동작할 cpu의 타이머 베이스를 반환한다.
- 코드 라인 5~7에서 nohz 시스템에서 이주 가능한 타이머인 경우 현재 cpu가 idle 상태일 때 절전을 위해 타이머가 동작될 인접한 busy cpu를 찾아 해당 cpu의 타이머 베이스를 반환한다.
- 코드 라인 9에서 현재 cpu의 타이머 베이스를 반환한다.
get_timer_cpu_base()
kernel/time/timer.c
static inline struct timer_base *get_timer_cpu_base(u32 tflags, u32 cpu)
{
struct timer_base *base = per_cpu_ptr(&timer_bases[BASE_STD], cpu);
/*
* If the timer is deferrable and NO_HZ_COMMON is set then we need
* to use the deferrable base.
*/
if (IS_ENABLED(CONFIG_NO_HZ_COMMON) && (tflags & TIMER_DEFERRABLE))
base = per_cpu_ptr(&timer_bases[BASE_DEF], cpu);
return base;
}
요청 cpu에 대한 타이머 베이스를 반환한다.
- per-cpu로 관리되는 타이머 베이스는 nohz를 사용하는 경우 두 개로 나뉘어 관리되며 지연 가능한 타이머는 별도의 타이머 베이스를 사용한다.
get_timer_this_cpu_base()
kernel/time/timer.c
static inline struct timer_base *get_timer_this_cpu_base(u32 tflags)
{
struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
/*
* If the timer is deferrable and NO_HZ_COMMON is set then we need
* to use the deferrable base.
*/
if (IS_ENABLED(CONFIG_NO_HZ_COMMON) && (tflags & TIMER_DEFERRABLE))
base = this_cpu_ptr(&timer_bases[BASE_DEF]);
return base;
}
현재 cpu에 대한 타이머 베이스를 반환한다.
- per-cpu로 관리되는 타이머 베이스는 nohz를 사용하는 경우 두 개로 나뉘어 관리되며 지연 가능한 타이머는 별도의 타이머 베이스를 사용한다.
nohz 타이머용 cpu
get_nohz_timer_target()
kernel/sched/core.c
/* * In the semi idle case, use the nearest busy CPU for migrating timers * from an idle CPU. This is good for power-savings. * * We don't do similar optimization for completely idle system, as * selecting an idle CPU will add more delays to the timers than intended * (as that CPU's timer base may not be uptodate wrt jiffies etc). */
int get_nohz_timer_target(void)
{
int i, cpu = smp_processor_id();
struct sched_domain *sd;
if (!idle_cpu(cpu) && housekeeping_cpu(cpu, HK_FLAG_TIMER))
return cpu;
rcu_read_lock();
for_each_domain(cpu, sd) {
for_each_cpu(i, sched_domain_span(sd)) {
if (cpu == i)
continue;
if (!idle_cpu(i) && housekeeping_cpu(i, HK_FLAG_TIMER)) {
cpu = i;
goto unlock;
}
}
}
if (!housekeeping_cpu(cpu, HK_FLAG_TIMER))
cpu = housekeeping_any_cpu(HK_FLAG_TIMER);
unlock:
rcu_read_unlock();
return cpu;
}
절전을 위해 nohz 타이머를 위한 타겟 cpu를 알아온다.
- 코드 라인 6~7에서 로컬 cpu가 busy 상태이면서 타이머에 대한 housekeeping이 가능하면 로컬 cpu를 반환한다.
- 코드 라인 10~20에서 cpu가 속한 스케쥴 domain 수 만큼 순회하고 내부에서 순회중인 스케줄 도메인만큼 cpu를 순회하며 busy 상태이면서 타이머에 대한 housekeeping이 가능한 해당 cpu를 반환한다.
- 코드 라인 22~23에서 찾지 못한 경우이다. cpu가 타이머에 대한 housekeeping이 불가능하면 housekeeping이 가능한 어떠한 cpu라도 찾아낸다.
- 코드 라인 26에서 nohz 타이머로 사용할 cpu를 반환한다.
SOFTIRQ – TIMER 수행
lowres 타이머의 bottom-half로 동작하는 softirq 핸들러를 알아본다.
run_timer_softirq()
kernel/time/timer.c
/* * This function runs timers and the timer-tq in bottom half context. */
static __latent_entropy void run_timer_softirq(struct softirq_action *h)
{
struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
__run_timers(base);
if (IS_ENABLED(CONFIG_NO_HZ_COMMON))
__run_timers(this_cpu_ptr(&timer_bases[BASE_DEF]));
}
로컬 cpu에 타이머 tick이 인입될 때 마다 호출되는 timer softirq에 등록한 함수이다. 만료된 타이머들의 해당 타이머 함수를 호출한다.
- 코드 라인 5에서 스탠다드 타이머 베이스에서 만료된 타이머들의 해당 타이머 함수를 호출한다.
- 코드 라인 6~7에서 deferrable 타이머 베이스에서 만료된 타이머들의 해당 타이머 함수를 호출한다.
__run_timers()
kernel/time/timer.c
/** * __run_timers - run all expired timers (if any) on this CPU. * @base: the timer vector to be processed. */
static inline void __run_timers(struct timer_base *base)
{
struct hlist_head heads[LVL_DEPTH];
int levels;
if (!time_after_eq(jiffies, base->clk))
return;
timer_base_lock_expiry(base);
raw_spin_lock_irq(&base->lock);
/*
* timer_base::must_forward_clk must be cleared before running
* timers so that any timer functions that call mod_timer() will
* not try to forward the base. Idle tracking / clock forwarding
* logic is only used with BASE_STD timers.
*
* The must_forward_clk flag is cleared unconditionally also for
* the deferrable base. The deferrable base is not affected by idle
* tracking and never forwarded, so clearing the flag is a NOOP.
*
* The fact that the deferrable base is never forwarded can cause
* large variations in granularity for deferrable timers, but they
* can be deferred for long periods due to idle anyway.
*/
base->must_forward_clk = false;
while (time_after_eq(jiffies, base->clk)) {
levels = collect_expired_timers(base, heads);
base->clk++;
while (levels--)
expire_timers(base, heads + levels);
}
raw_spin_unlock_irq(&base->lock);
timer_base_unlock_expiry(base);
}
요청 타이머 베이스에서 만료된 타이머들의 함수를 실행한다.
- 코드 라인 6~7에서 jiffies < base->clk 이다. 가장 가까운 타이머 시각이 아직 처리할 시각이 안되었으므로 함수를 빠져나간다.
- 코드 라인 9~10에서 타이머 함수 호출 루틴이 동시에 호출되는 것을 막기 위해 lock을 획득한다. 또한 타이머 베이스를 조작하기 위한 lock도 획득한다.
- 코드 라인 26에서 타이머 베이스에서 forward 처리를 하지 못하도록 막는다.
- 코드 라인 28~35에서 타이머 베이스의 clk가 만료된 경우 다음과 같이 처리한다.
- 만료된 타이머들을 heads 리스트에 모아온다. levels에는 최고 레벨이 저장된다.
- 다음 루프 처리를 위해 타이머 베이스의 clk을 미리 증가시킨다.
- 레벨별로 만료된 타이머에 해당하는 콜백 함수들을 호출한다.
- 코드 라인 36~37에서 걸었던 lock들을 해제한다.
만료된 타이머들 수집
collect_expired_timers()
kernel/time/timer.c
static int collect_expired_timers(struct timer_base *base,
struct hlist_head *heads)
{
unsigned long now = READ_ONCE(jiffies);
/*
* NOHZ optimization. After a long idle sleep we need to forward the
* base to current jiffies. Avoid a loop by searching the bitfield for
* the next expiring timer.
*/
if ((long)(now - base->clk) > 2) {
unsigned long next = __next_timer_interrupt(base);
/*
* If the next timer is ahead of time forward to current
* jiffies, otherwise forward to the next expiry time:
*/
if (time_after(next, now)) {
/*
* The call site will increment base->clk and then
* terminate the expiry loop immediately.
*/
base->clk = now;
return 0;
}
base->clk = next;
}
return __collect_expired_timers(base, heads);
}
요청 타이머 베이스에서 만료된 타이머들을 @heads 리스트에 추가한다. levels에는 수집한 최고 레벨 + 1이 저장된다.
- 코드 라인 11~27에서 nohz를 사용하면 타이머 베이스를 매 틱마다 처리하지 못할 수 있다. 이 때 3틱 이상 밀려 있는 상태면 매 틱마다 처리하지 않고 nohz optimization을 수행한다. 이 때 다음 타이머의 만료 시각이 현재 시각을 초과했는지 여부에 따라 다음과 같이 처리한다.
- 아직 만료 시각이 남은 경우 지연된 base->clk을 현재 시각으로 갱신하고, 결과 값 0으로 함수를 빠져나간다.
- 만료 시각이 지난 경우 base->clk에 다음 타이머 만료 시각을 대입하고, 다음 루틴을 계속 처리한다.
- 코드 라인 28에서 만료된 타이머 함수들을 @heds 리스트로 수집한다.
__collect_expired_timers()
kernel/time/timer.c
static int __collect_expired_timers(struct timer_base *base,
struct hlist_head *heads)
{
unsigned long clk = base->clk;
struct hlist_head *vec;
int i, levels = 0;
unsigned int idx;
for (i = 0; i < LVL_DEPTH; i++) {
idx = (clk & LVL_MASK) + i * LVL_SIZE;
if (__test_and_clear_bit(idx, base->pending_map)) {
vec = base->vectors + idx;
hlist_move_list(vec, heads++);
levels++;
}
/* Is it time to look at the next level? */
if (clk & LVL_CLK_MASK)
break;
/* Shift clock for the next level granularity */
clk >>= LVL_CLK_SHIFT;
}
return levels;
}
요청 타이머 베이스에서 만료된 타이머들을 @heads 리스트로 수집한다.
- 코드 라인 9~17에서 0~마지막 레벨(100hz 이하에서 8, 초과 시 9)까지 순회하며 타이머 휠 인덱스 값에 해당하는 펜딩 맵에 비트가 설정된 경우 이를 클리어하고, 이에 해당하는 인덱스의 타이머 휠 벡터 리스트를 heads 리스트에 옮기고, 반환할 levels를 1 증가시킨다.
- 코드 라인 19~23에서 다음 레벨을 처리할 필요가 없는 경우 루프를 벗어난다. 그렇지 않고 남은 경우 다음 레벨을 처리하기 위해 clk을 3 비트 쉬프트한다.
- clk 값의 해당 레벨의 6비트 중 하위 3비트 값이 0인 경우 다음 레벨로 넘어간다.
- 코드 라인 24에서 수집한 최고 레벨 + 1 값을 반환한다.
다음 그림은 base->clk 값에 의해 호출되는 레벨별 타이머 벡터 리스트들을 보여준다.
- 레벨별로 쉬프트된 6bit clk 값의 하위 3비트가 0인 경우 다음 레벨도 처리하기 위해 이동한다.
- clk 값이 0x4400 값인 경우 lvl 0 ~ lvl 3까지 이동하며 각 레벨의 6bit clk값 + lvl * 64로 idx를 산출한다. 그런 후 idx에 해당하는 펜딩맵이 설정된 벡터 리스트의 타이머들이 선택된다.
만료된 타이머들의 콜백 함수 호출
expire_timers()
kernel/time/timer.c
static void expire_timers(struct timer_base *base, struct hlist_head *head)
{
/*
* This value is required only for tracing. base->clk was
* incremented directly before expire_timers was called. But expiry
* is related to the old base->clk value.
*/
unsigned long baseclk = base->clk - 1;
while (!hlist_empty(head)) {
struct timer_list *timer;
void (*fn)(struct timer_list *);
timer = hlist_entry(head->first, struct timer_list, entry);
base->running_timer = timer;
detach_timer(timer, true);
fn = timer->function;
if (timer->flags & TIMER_IRQSAFE) {
raw_spin_unlock(&base->lock);
call_timer_fn(timer, fn, baseclk);
base->running_timer = NULL;
raw_spin_lock(&base->lock);
} else {
raw_spin_unlock_irq(&base->lock);
call_timer_fn(timer, fn, baseclk);
base->running_timer = NULL;
timer_sync_wait_running(base);
raw_spin_lock_irq(&base->lock);
}
}
}
@head 리스트의 만료된 타이머들의 콜백 함수들을 호출한다.
- 호출하는 동안 base->running_timer에 타이머가 기록되고, 호출이 완료되면 null이 대입된다.
- TIMER_IRQSAFE 플래그를 사용하면 인터럽트를 disable하지 않은 상태에서 spinlock을 사용한다.
타이머 콜백 함수 호출
call_timer_fn()
kernel/time/timer.c
static void call_timer_fn(struct timer_list *timer,
void (*fn)(struct timer_list *),
unsigned long baseclk)
{
int count = preempt_count();
#ifdef CONFIG_LOCKDEP
/*
* It is permissible to free the timer from inside the
* function that is called from it, this we need to take into
* account for lockdep too. To avoid bogus "held lock freed"
* warnings as well as problems when looking into
* timer->lockdep_map, make a copy and use that here.
*/
struct lockdep_map lockdep_map;
lockdep_copy_map(&lockdep_map, &timer->lockdep_map);
#endif
/*
* Couple the lock chain with the lock chain at
* del_timer_sync() by acquiring the lock_map around the fn()
* call here and in del_timer_sync().
*/
lock_map_acquire(&lockdep_map);
trace_timer_expire_entry(timer, baseclk);
fn(timer);
trace_timer_expire_exit(timer);
lock_map_release(&lockdep_map);
if (count != preempt_count()) {
WARN_ONCE(1, "timer: %pS preempt leak: %08x -> %08x\n",
fn, count, preempt_count());
/*
* Restore the preempt count. That gives us a decent
* chance to survive and extract information. If the
* callback kept a lock held, bad luck, but not worse
* than the BUG() we had.
*/
preempt_count_set(count);
}
}
인수로 받은 fn은 타이머에 설정된 함수이다. 디버그를 위해 trace 출력등이 사용되었다.
타이머 설정
컴파일 타임에 정적 타이머 생성 및 초기화
include/linux/timer.h
DEFINE_TIMER()
#define DEFINE_TIMER(_name, _function) \
struct timer_list _name = \
__TIMER_INITIALIZER(_function, 0)
컴파일 타임에 타이머를 초기화한다. 인자로 타이머 이름과 콜백 함수를 지정한다.
- 플래그는 사용하지 않고 0을 전달한다.
__TIMER_INITIALIZER()
include/linux/timer.h
#define __TIMER_INITIALIZER(_function, _flags) { \
.entry = { .next = TIMER_ENTRY_STATIC }, \
.function = (_function), \
.flags = (_flags), \
__TIMER_LOCKDEP_MAP_INITIALIZER( \
__FILE__ ":" __stringify(__LINE__)) \
}
런타임에 동적 타이머 생성 및 초기화
timer_setup()
include/linux/timer.h
/** * timer_setup - prepare a timer for first use * @timer: the timer in question * @callback: the function to call when timer expires * @flags: any TIMER_* flags * * Regular timer initialization should use either DEFINE_TIMER() above, * or timer_setup(). For timers on the stack, timer_setup_on_stack() must * be used and must be balanced with a call to destroy_timer_on_stack(). */
#define timer_setup(timer, callback, flags) \
__init_timer((timer), (callback), (flags))
타이머를 사용하기 위해 준비한다. 인자로는 타이머와 콜백 함수 및 플래그를 지정한다.
__init_timer()
include/linux/timer.h
#define __init_timer(_timer, _fn, _flags) \
init_timer_key((_timer), (_fn), (_flags), NULL, NULL)
timer_setup_on_stack()
include/linux/timer.h
#define setup_timer_on_stack(timer, callback, flags) \
__init_timer_on_stack((timer), (callback), (flags))
타이머를 전달 받은 인자들로 초기화한다.
__init_timer_on_stack()
include/linux/timer.h
#define __init_timer_on_stack(_timer, _fn, _flags) \
init_timer_on_stack_key((_timer), (_fn), (_flags), NULL, NULL)
init_timer_on_stack_key()
include/linux/timer.h
static inline void init_timer_on_stack_key(struct timer_list *timer,
void (*func)(struct timer_list *),
unsigned int flags,
const char *name,
struct lock_class_key *key)
{
init_timer_key(timer, func, flags, name, key);
}
init_timer_key()
kernel/time/timer.c
/** * init_timer_key - initialize a timer * @timer: the timer to be initialized * @func: timer callback function * @flags: timer flags * @name: name of the timer * @key: lockdep class key of the fake lock used for tracking timer * sync lock dependencies * * init_timer_key() must be done to a timer prior calling *any* of the * other timer functions. */
void init_timer_key(struct timer_list *timer,
void (*func)(struct timer_list *), unsigned int flags,
const char *name, struct lock_class_key *key)
{
debug_init(timer);
do_init_timer(timer, func, flags, name, key);
}
EXPORT_SYMBOL(init_timer_key);
타이머를 전달 받은 인자들로 초기화한다.
do_init_timer()
kernel/time/timer.c
static void do_init_timer(struct timer_list *timer,
void (*func)(struct timer_list *),
unsigned int flags,
const char *name, struct lock_class_key *key)
{
timer->entry.pprev = NULL;
timer->function = func;
timer->flags = flags | raw_smp_processor_id();
lockdep_init_map(&timer->lockdep_map, name, key, 0);
}
타이머를 전달 받은 인자들로 초기화한다.
초기화
init_timers()
kernel/time/timer.c
void __init init_timers(void)
{
init_timer_cpus();
open_softirq(TIMER_SOFTIRQ, run_timer_softirq);
}
타이머를 사용할 수 있도록 초기화한다.
- 코드 라인 3에서 cpu별로 타이머를 사용할 수 있도록 초기화한다.
- 코드 라인 4에서 타이머 softirq를 열고 run_timer_softirq() 함수가 호출되도록 준비한다.
init_timer_cpus()
kernel/time/timer.c
static void __init init_timer_cpus(void)
{
int cpu;
for_each_possible_cpu(cpu)
init_timer_cpu(cpu);
}
모든 possible cpu에 대해 타이머를 사용할 수 있도록 초기화한다.
init_timer_cpu()
kernel/time/timer.c
static void __init init_timer_cpu(int cpu)
{
struct timer_base *base;
int i;
for (i = 0; i < NR_BASES; i++) {
base = per_cpu_ptr(&timer_bases[i], cpu);
base->cpu = cpu;
raw_spin_lock_init(&base->lock);
base->clk = jiffies;
timer_base_init_expiry_lock(base);
}
}
요청 cpu에 대해 타이머를 사용할 수 있도록 초기화한다.
기존 커널 관련 (~ 커널 v4.7)
기존 cascading wheel 구조
요청된 타이머의 관리를 위해 cpu 마다 타이머휠이 사용된다. 타이머 휠마다 tv1 ~ tv5까지의 5개 벡터로 나누어 관리하며, 각 벡터는 각각 256, 64, 64, 64, 64개의 리스트로 이루어진다.
- CONFIG_BASE_SMALL 사용 시 커널 사이즈를 최소화하기 위해 리스트들은 각각 64, 16, 16, 16, 16개로 1/4로 줄어든다.
다음 그림은 타이머 벡터 간의 cascade 조건을 보여준다.
예) base->timer_jiffies 값이 0x400_0000인 경우 tv2 -> tv1, tv3 -> tv2, tv4 -> tv3, tv5 -> tv4의 순서로 full cascade 처리된다.
다음 그림은 만료시각이 다른 각종 타이머들을 추가했을 때 타이머휠에 등록된 타이머 상태들을 보여준다.
- expires – base->timer_jiffies 하여 산출된 tick 값에 따라 512(256+64+64+64+64)개의 리스트 중 하나가 선택된다.
- 예) timer_jiffies=100, hz=100, 7초 후에 timer가 호출되게 하려할 때 expires 값과 추가될 타이머 벡터 리스트는?
- 7초면 700 tick이 필요하므로 expires=100+700이 대입되고 tv2.vec[32]에 추가된다.
- 예) timer_jiffies=100, hz=100, 7초 후에 timer가 호출되게 하려할 때 expires 값과 추가될 타이머 벡터 리스트는?
다음 그림은 jiffies값이 35인 시점에 cpu#1에 tick이 발생하고 그 동안 tick이 발생하지 못해 처리 못했던 jiffies 들에 대한 처리를 한꺼번에 처리하도록 한다.
- jiffies=35인 시점에 26~35까지 처리 못했던 만료된 타이머들의 함수들을 처리한다.
다음 그림은 tv2에 있는 두 개의 타이머가 tv1으로 cascade되는 모습을 보여준다.
Slack으로 만료 시간 조정
만료 시간을 조정하여 유사한 만료 시간들끼리 모아 한꺼번에 처리하도록 slack 정렬한다. 타이머 인터럽트가 조금이라도 덜 발생하도록하여 절전과 처리 성능에 도움을 준다.
- 참고: Timer slack | LWN.net
아래 그림은 100hz 시스템에서 slack으로 9 tick을 준 경우와 timeout으로 2311 tick을 준 경우에 대해 만료 값이 어떻게 변화하는지를 보여준다.
커널 v4.7까지에서는 타이머 리스트가 disable 된 상태에 있기 때문에 아래와 같이 inactive 출력된다.
$ cat /proc/timer_stats Timer Stats Version: v0.3 Sample period: 0.000 s Collection: inactive 0 total events
다음과 같이 enable 시킨다.
# echo "1" > /proc/timer_stats
그런 후 출력이 가능하다. (lowres 타이머와 hrtimer가 섞여 있다)
# cat /proc/timer_stats
Timer Stats Version: v0.3
Sample period: 4.530 s
Collection: active
453, 0 swapper/2 hrtimer_start_range_ns (tick_sched_timer)
38, 0 swapper/0 hrtimer_start_range_ns (tick_sched_timer)
50, 7 rcu_preempt rcu_gp_kthread (process_timeout)
5, 1632 ifplugd hrtimer_start_range_ns (hrtimer_wakeup)
16, 0 swapper/1 hrtimer_start (tick_sched_timer)
36, 0 swapper/0 hrtimer_start (tick_sched_timer)
4, 3992 sshd sk_reset_timer (tcp_write_timer)
17, 0 swapper/1 usb_hcd_poll_rh_status (rh_timer_func)
4, 1582 ifplugd hrtimer_start_range_ns (hrtimer_wakeup)
4, 2230 ntpd hrtimer_start_range_ns (posix_timer_fn)
4, 3467 kworker/u8:2 queue_delayed_work_on (delayed_work_timer_fn)
10, 0 swapper/0 sk_reset_timer (tcp_delack_timer)
3, 26686 kworker/2:1 queue_delayed_work_on (delayed_work_timer_fn)
3, 44 kworker/0:1 queue_delayed_work_on (delayed_work_timer_fn)
1, 2058 thd hrtimer_start_range_ns (hrtimer_wakeup)
25, 0 swapper/1 hrtimer_start_range_ns (tick_sched_timer)
673 total events, 148.565 events/sec
참고
- Timer -1- (Lowres Timer) | 문c – 현재 글
- Timer -2- (HRTimer) | 문c
- Timer -3- (Clock Sources Subsystem) | 문c
- Timer -4- (Clock Sources Watchdog) | 문c
- Timer -5- (Clock Events Subsystem) | 문c
- Timer -6- (Clock Source & Timer Driver) | 문c
- Timer -7- (Sched Clock & Delay Timers) | 문c
- Timer -8- (Timecounter) | 문c
- Timer -9- (Tick Device) | 문c
- Timer -10- (Timekeeping) | 문c
- Timer -11- (Posix Clock & Timers) | 문c
- time_init() | 문c
- sched_clock_postinit() | 문c
- tick_init() | 문c
- timekeeping_init() | 문c
- calibrate_delay() | 문c
안녕하세요! iamroot16차 이파란입니다.
타이머 스터디하다가 발견해서 문의드립니다. 항상 감사드립니다~
add_timer-2c.png
다음 그림은 만료시각이 다른 각종 타이머들을 추가했을 때 타이머휠에 등록된 타이머 상태들을 보여준다.
그림에서 구조체 멤버 함수가 finction 으로 되어있습니다!
add 한 B 컬백 함수가 우하단에 동적 타이머에 C 로 나와있습니다.
감사합니다!
p.s.
E 컬백을 가진 동적 타이머가 1100 으로 expires 가 등록되어있는데, 1000 으로 add 되어있습니다.
감사합니다!
안녕하세요?
요청하신 항목들이 잘못 표시되었군요. 모두 수정하였습니다.
감사합니다.