LK · source analysis

timer queue와 tick 처리

CPU별 deadline queue의 등록·만료, IRQ callback, periodic·cancel 분기를 읽습니다.

이 글은 LK upstream 고정 commit 1eb9917의 구현을 설명한다. backend와 platform timer 설정은 선택한 project에서 확인한다.

Series
07 / 20
Baseline
upstream 1eb9917
Commit
1eb99171efae
Source
kernel/timer.c:20-108 (발췌 범위)

deadline 등록과 callback 사이에 어떤 분기가 있는가?

timer_set()은 current_time()+delay를 저장해 현재 CPU의 deadline 순 timer queue에 넣는다. dynamic timer 플랫폼에서는 새 timer가 head일 때만 one-shot hardware deadline을 설정한다. 비동적 플랫폼은 timer_init()의 10ms periodic hardware tick을 사용한다 (kernel/timer.c:71, kernel/timer.c:283).

timer_tick()은 interrupt 문맥에서 만료 timer를 queue에서 제거하고 timer_lock을 푼 상태로 callback을 부른다. 그 뒤 periodic 재삽입 여부를 확인하고, callback 결과의 INT_RESCHEDULE을 상위 IRQ 경로에 반환한다. 반환값 자체가 즉시 context switch라는 뜻은 아니다 (kernel/timer.c:196, kernel/timer.c:220).

CPU별 queue와 platform timer 방식

그림 1. timer_t가 CPU queue에 들어가고 hardware tick을 받는 구조
timer_t 객체timer_initialize()로 magic·node 준비
timers[cpu].timer_queuescheduled_time 오름차순; 같은 deadline은 앞선 항목 뒤
head 만료timer_tick이 제거, callback은 lock 밖에서 실행
PLATFORM_HAS_DYNAMIC_TIMER새 head 설정·cancel head 변경·tick 뒤 next head에서 one-shot 재설정
비동적 timertimer_init이 10ms periodic timer 등록; 각 tick 뒤 thread_timer_tick 조건 검사

timers[SMP_MAX_CPUS]는 CPU별 queue이고 timer_lock은 공통이다. queue 삽입 시 arch_curr_cpu_num()의 지역 변수로 대상을 고른다. timer_t에는 소유 CPU 번호를 저장하는 필드가 없다 (kernel/timer.c:36, kernel/timer.c:93).

set→expire→callback→재삽입의 조건

그림 2. one-shot·periodic·cancel의 갈림길
set_oneshot / set_periodic0은 1ms로 보정; now+delay 계산
timer_set이미 queue 연결 중이면 panic; lock 아래 정렬 삽입
timer_tick IRQhead가 만료됐을 때만 dequeue·unlock
one-shotcallback 뒤 queue에서 빠진 상태. callback이 직접 재등록한 경우만 다시 active
periodiccallback이 재등록·cancel하지 않았다면 scheduled_time += period; tick이 받은 now보다 지났다면 now+period
cancelqueue node 제거 후 period=0, callback/arg=NULL; dynamic head 변화면 hardware 갱신
callback은 IRQ 문맥·interrupt disabled이지만 timer_lock 밖에서 호출된다. 반환된 INT_RESCHEDULE은 IRQ 처리 결과에 누적된다.

periodic 여부는 callback 전의 periodic_time > 0로 잡지만, 실제 재삽입은 callback 뒤 node가 아직 빠져 있고 periodic_time이 여전히 양수일 때만 한다 (kernel/timer.c:232, kernel/timer.c:245).

queue·deadline·callback 상태

단계조건상태 변화hardware / 반환
timer_initialize새 timer_tmagic·node 등 초기값queue 없음
timer_setnode가 이미 queue에 없음scheduled_time=now+delay; 현재 CPU queue 정렬 삽입dynamic + 새 head면 one-shot 설정
timer_tickhead deadline ≤ nowqueue에서 제거, timer_lock 해제 뒤 callbackcallback 결과가 INT_RESCHEDULE이면 누적
periodic 재삽입callback 전 periodic, 뒤에도 period>0·미등록다음 scheduled_time 보정 후 삽입dynamic이면 다음 head deadline 설정
timer_cancelqueued 또는 inactivenode 제거 가능, period=0, callback/arg=NULLdynamic이면 head 변화에 따라 stop/reprogram

timer_cancel()의 dynamic hardware 처리는 취소를 호출한 현재 CPU의 queue를 기준으로 한다. 소유 CPU를 찾아가 재설정하는 코드가 없으므로 다른 CPU에서의 취소가 해당 CPU의 deadline까지 올바르게 갱신한다고 단정하지 않는다. 등록·취소 CPU와 객체 수명은 호출자가 조정해야 한다. 또한 cancel은 이미 dequeue되어 실행 중인 callback의 종료를 기다린다는 구현이 없다. owner의 해제 시점은 queue link만이 아니라 callback 진행 상태까지 고려해야 한다 (kernel/timer.c:150, kernel/timer.c:225).

timer의 queue 상태와 IRQ 문맥

deadline, queue link, callback 실행을 각각 다른 상태로 표시했다. dynamic 모드의 set·cancel은 head 변화 조건을 검사하고, tick 끝에서는 남아 있는 다음 head에 맞춰 hardware timer를 다시 설정한다.

그림 3. deadline 등록부터 IRQ 처리까지

queue 삽입과 hardware programming은 같은 동작이 아니며 platform mode와 head 조건으로 구분한다.

01now + delay
02현재 CPU queue 정렬 삽입
03dynamic + 새 head만 one-shot 설정
04IRQ: deadline 지난 head 제거
05lock 밖 callback
06periodic 조건부 재삽입
07dynamic next head 설정
그림 4. timer node의 세 시점

queue에 없는 timer도 callback이 실행 중일 수 있다.

초기·cancel 후queue link 없음; cancel은 period·callback·arg를 지움
queue 연결 중scheduled_time 기준 정렬; timer_set 재호출은 panic
callback 실행 중node는 이미 제거됨; IRQ 문맥, timer_lock은 풀림
callback이 직접 재등록tick의 자동 periodic 재삽입을 건너뜀
cancel 또는 period=0자동 periodic 재삽입을 건너뜀

원본 코드

아래 코드는 LK upstream 1eb9917의 kernel/timer.c에서 20-108줄을 그대로 가져온 것이다.

commit1eb99171efae98867d4be4a5bd6479ea03f43ac9anchor · L44static enum handler_return timer_tick(void *arg
20 * @{
21 */
22#include <kernel/timer.h>
23
24#include <assert.h>
25#include <kernel/debug.h>
26#include <kernel/spinlock.h>
27#include <kernel/thread.h>
28#include <lk/debug.h>
29#include <lk/list.h>
30#include <lk/trace.h>
31#include <platform.h>
32#include <platform/timer.h>
33
34#define LOCAL_TRACE 0
35
36spin_lock_t timer_lock;
37
38struct timer_state {
39    struct list_node timer_queue;
40} __CPU_ALIGN;
41
42static struct timer_state timers[SMP_MAX_CPUS];
43
44static enum handler_return timer_tick(void *arg, lk_time_t now);
45
46/**
47 * @brief  Initialize a timer object
48 */
49void timer_initialize(timer_t *timer) {
50    *timer = (timer_t)TIMER_INITIAL_VALUE(*timer);
51}
52
53static void insert_timer_in_queue(uint cpu, timer_t *timer) {
54    timer_t *entry;
55
56    DEBUG_ASSERT(arch_ints_disabled());
57
58    LTRACEF("timer %p, cpu %u, scheduled %u, periodic %u\n", timer, cpu, timer->scheduled_time, timer->periodic_time);
59
60    list_for_every_entry(&timers[cpu].timer_queue, entry, timer_t, node) {
61        if (TIME_GT(entry->scheduled_time, timer->scheduled_time)) {
62            list_add_before(&entry->node, &timer->node);
63            return;
64        }
65    }
66
67    /* walked off the end of the list */
68    list_add_tail(&timers[cpu].timer_queue, &timer->node);
69}
70
71static void timer_set(timer_t *timer, lk_time_t delay, lk_time_t period, timer_callback callback, void *arg) {
72    lk_time_t now;
73
74    LTRACEF("timer %p, delay %u, period %u, callback %p, arg %p\n", timer, delay, period, callback, arg);
75
76    DEBUG_ASSERT(timer->magic == TIMER_MAGIC);
77
78    if (list_in_list(&timer->node)) {
79        panic("timer %p already in list\n", timer);
80    }
81
82    now = current_time();
83    timer->scheduled_time = now + delay;
84    timer->periodic_time = period;
85    timer->callback = callback;
86    timer->arg = arg;
87
88    LTRACEF("scheduled time %u\n", timer->scheduled_time);
89
90    spin_lock_saved_state_t state;
91    spin_lock_irqsave(&timer_lock, state);
92
93    uint cpu = arch_curr_cpu_num();
94    insert_timer_in_queue(cpu, timer);
95
96#if PLATFORM_HAS_DYNAMIC_TIMER
97    if (list_peek_head_type(&timers[cpu].timer_queue, timer_t, node) == timer) {
98        /* we just modified the head of the timer queue */
99        LTRACEF("setting new timer for %u msecs\n", delay);
100        platform_set_oneshot_timer(timer_tick, NULL, delay);
101    }
102#endif
103
104    spin_unlock_irqrestore(&timer_lock, state);
105}
106
107/**
108 * @brief  Set up a timer that executes once

원본 발췌와 만료 처리 구현

기존 주 원본 kernel/timer.c 20–108행과 보충 61–133행은 고정 원문과 일치해 보존했다. L44는 timer_tick 선언이다. 실제 IRQ callback 구현은 L196부터 시작하므로 아래 분기를 함께 읽는다.

dequeue·callback·periodic 재삽입

kernel/timer.c L220–252

 220          /* process it */
 221          LTRACEF("timer %p\n", timer);
 222          DEBUG_ASSERT(timer && timer->magic == TIMER_MAGIC);
 223          list_delete(&timer->node);
 224
 225          /* we pulled it off the list, release the list lock to handle it */
 226          spin_unlock(&timer_lock);
 227
 228          LTRACEF("dequeued timer %p, scheduled %u periodic %u\n", timer, timer->scheduled_time, timer->periodic_time);
 229
 230          THREAD_STATS_INC(timers);
 231
 232          bool periodic = timer->periodic_time > 0;
 233
 234          LTRACEF("timer %p firing callback %p, arg %p\n", timer, timer->callback, timer->arg);
 235          KEVLOG_TIMER_CALL(timer->callback, timer->arg);
 236          if (timer->callback(timer, now, timer->arg) == INT_RESCHEDULE)
 237              ret = INT_RESCHEDULE;
 238
 239          /* it may have been requeued or periodic, grab the lock so we can safely inspect it */
 240          spin_lock(&timer_lock);
 241
 242          /* if it was a periodic timer and it hasn't been requeued
 243           * by the callback put it back in the list
 244           */
 245          if (periodic && !list_in_list(&timer->node) && timer->periodic_time > 0) {
 246              LTRACEF("periodic timer, period %u\n", timer->periodic_time);
 247              timer->scheduled_time += timer->periodic_time;
 248              if (unlikely(TIME_LT(timer->scheduled_time, now))) {
 249                  timer->scheduled_time = now + timer->periodic_time;
 250              }
 251              insert_timer_in_queue(cpu, timer);
 252          }

dynamic next deadline / periodic tick 분기

kernel/timer.c L255–280

 255  #if PLATFORM_HAS_DYNAMIC_TIMER
 256      /* reset the timer to the next event */
 257      timer = list_peek_head_type(&timers[cpu].timer_queue, timer_t, node);
 258      if (timer) {
 259          /* has to be the case or it would have fired already */
 260          DEBUG_ASSERT(TIME_GT(timer->scheduled_time, now));
 261
 262          lk_time_t delay = timer->scheduled_time - now;
 263
 264          LTRACEF("setting new timer for %u msecs for event %p\n", (uint)delay, timer);
 265          platform_set_oneshot_timer(timer_tick, NULL, delay);
 266      }
 267
 268      /* we're done manipulating the timer queue */
 269      spin_unlock(&timer_lock);
 270  #else
 271      /* release the timer lock before calling the tick handler */
 272      spin_unlock(&timer_lock);
 273
 274      /* let the scheduler have a shot to do quantum expiration, etc */
 275      /* in case of dynamic timer, the scheduler will set up a periodic timer */
 276      if (thread_timer_tick(NULL, now, NULL) == INT_RESCHEDULE)
 277          ret = INT_RESCHEDULE;
 278  #endif
 279
 280      return ret;

cancel에서 period·callback을 지우고 dynamic head를 다시 설정하는 부분은 kernel/timer.c:150–190행이다.

함께 읽어야 하는 원본 코드

첫 코드 조각만으로 동작이 완성되지 않는 경우 호출 매크로, 객체 정의와 실제 실행 목록을 같은 페이지에 묶었다. 각 조각은 같은 기준 commit에서 가져왔다.

01. timer의 만료 시각과 callback을 queue에 등록

kernel/timer.c 61-133줄이다.

filekernel/timer.canchor · L71static void timer_set(timer_t *timer
61        if (TIME_GT(entry->scheduled_time, timer->scheduled_time)) {
62            list_add_before(&entry->node, &timer->node);
63            return;
64        }
65    }
66
67    /* walked off the end of the list */
68    list_add_tail(&timers[cpu].timer_queue, &timer->node);
69}
70
71static void timer_set(timer_t *timer, lk_time_t delay, lk_time_t period, timer_callback callback, void *arg) {
72    lk_time_t now;
73
74    LTRACEF("timer %p, delay %u, period %u, callback %p, arg %p\n", timer, delay, period, callback, arg);
75
76    DEBUG_ASSERT(timer->magic == TIMER_MAGIC);
77
78    if (list_in_list(&timer->node)) {
79        panic("timer %p already in list\n", timer);
80    }
81
82    now = current_time();
83    timer->scheduled_time = now + delay;
84    timer->periodic_time = period;
85    timer->callback = callback;
86    timer->arg = arg;
87
88    LTRACEF("scheduled time %u\n", timer->scheduled_time);
89
90    spin_lock_saved_state_t state;
91    spin_lock_irqsave(&timer_lock, state);
92
93    uint cpu = arch_curr_cpu_num();
94    insert_timer_in_queue(cpu, timer);
95
96#if PLATFORM_HAS_DYNAMIC_TIMER
97    if (list_peek_head_type(&timers[cpu].timer_queue, timer_t, node) == timer) {
98        /* we just modified the head of the timer queue */
99        LTRACEF("setting new timer for %u msecs\n", delay);
100        platform_set_oneshot_timer(timer_tick, NULL, delay);
101    }
102#endif
103
104    spin_unlock_irqrestore(&timer_lock, state);
105}
106
107/**
108 * @brief  Set up a timer that executes once
109 *
110 * This function specifies a callback function to be called after a specified
111 * delay.  The function will be called one time.
112 *
113 * @param  timer The timer to use
114 * @param  delay The delay, in ms, before the timer is executed
115 * @param  callback  The function to call when the timer expires
116 * @param  arg  The argument to pass to the callback
117 *
118 * The timer function is declared as:
119 *   enum handler_return callback(struct timer *, lk_time_t now, void *arg) { ... }
120 */
121void timer_set_oneshot(timer_t *timer, lk_time_t delay, timer_callback callback, void *arg) {
122    if (delay == 0)
123        delay = 1;
124    timer_set(timer, delay, 0, callback, arg);
125}
126
127/**
128 * @brief  Set up a timer that executes repeatedly
129 *
130 * This function specifies a callback function to be called after a specified
131 * delay.  The function will be called repeatedly.
132 *
133 * @param  timer The timer to use

등록·만료·취소의 정확한 순서

01

timer_t는 caller가 초기화한다

timer_initialize()가 TIMER_INITIAL_VALUE를 대입한다. timer_set은 magic을 검사하고 이미 queue에 있는 node면 panic한다. 이 API가 timer 객체 메모리를 할당하지는 않는다 (kernel/timer.c:49, kernel/timer.c:76).

02

상대 delay를 현재 CPU의 절대 deadline으로

one-shot과 periodic의 0 입력은 1ms로 보정된다. timer_set은 now + delay를 저장하고 현재 CPU queue에 TIME_GT 비교로 정렬 삽입한다 (kernel/timer.c:53, kernel/timer.c:71, kernel/timer.c:121).

03

callback은 lock 밖의 IRQ 작업

timer_tick은 interrupt disabled를 assert하고 timer_lock으로 head를 본다. deadline이 지나면 node를 제거하고 lock을 풀어 callback을 호출한다. callback 자체가 sleep할 수 있는 thread 문맥으로 이동한 것은 아니다 (kernel/timer.c:196, kernel/timer.c:220).

04

periodic 자동 재삽입의 세 조건

tick은 callback 전 periodic 여부를 보관한다. callback 후 lock을 다시 잡아 node가 재등록되지 않았고 periodic_time이 양수일 때만 다음 deadline을 계산한다. 이전 deadline이 이미 지난 경우 now+period로 건너뛴다 (kernel/timer.c:232, kernel/timer.c:239).

05

하드웨어 timer는 platform mode가 결정

dynamic 모드는 새 head, cancel의 head 변화, tick 뒤 next head에서 one-shot을 설정하거나 멈춘다. 비동적 모드는 timer_init의 10ms periodic tick을 사용하고 thread_timer_tick의 결과도 반환값에 합친다 (kernel/timer.c:96, kernel/timer.c:172, kernel/timer.c:255).

수명과 시간 비교의 세 조건

01

deadline 비교는 TIME_LT/TIME_GT

정렬과 만료 판정은 unsigned 숫자의 단순 대소 비교가 아니라 TIME_GT/TIME_LT 매크로를 사용한다. wrap 조건의 정확한 허용 범위는 lk_time_t와 macro 정의로 확인한다 (kernel/timer.c:60, kernel/timer.c:217).

02

callback의 INT_RESCHEDULE은 요청 결과

하나 이상의 callback이 INT_RESCHEDULE을 반환하면 timer_tick은 값을 누적한다. 비동적 timer에서는 thread_timer_tick 결과도 합친다. 실제 preempt·switch 여부는 호출한 IRQ 경로와 scheduler 상태에 달려 있다 (kernel/timer.c:236, kernel/timer.c:274).

03

cancel은 callback 완료 barrier가 아니다

cancel은 list에 있으면 node를 제거하고 period·callback·arg를 지운다. timer_tick은 callback 전에 이미 list에서 node를 꺼내 lock을 풀기 때문에, node가 없다는 관찰만으로 callback이 끝났다고 판단할 수 없다 (kernel/timer.c:150, kernel/timer.c:223).

timer 객체와 queue 소유권

대상만드는 주체유효 상태주의
timer_tcaller가 보유·timer_initializequeue 연결, callback 진행, 취소 후에도 객체 수명은 caller 책임stack timer는 callback 완료까지 살아야 함
timers[cpu].timer_queuetimer_init현재 CPU에 set한 timer의 deadline 순 listCPU별 queue, 공통 timer_lock
callback/argtimer_set이 timer_t에 보관tick이 호출; cancel이 NULL로 지움IRQ 실행과 owner 해제 경합 점검
hardware deadlinedynamic head 또는 비동적 periodic 설정platform mode별 별도 경로모든 insert가 one-shot 설정은 아님

증상별 먼저 볼 조건

관찰확인할 분기근거
등록 직후 panictimer node가 이미 list에 있는지kernel/timer.c:78
deadline 앞 timer가 늦음TIME_LT 만료 판단과 긴 IRQ callback 실행 시간kernel/timer.c:217
periodic 재호출 안 됨callback이 재등록했는지·cancel로 period=0이 됐는지kernel/timer.c:245
dynamic timer가 재설정 안 됨새 timer가 head인지, cancel로 head가 바뀌었는지kernel/timer.c:96
cancel 뒤 callback 수명 문제dequeue 뒤 lock 밖 callback과 owner 해제 순서kernel/timer.c:223

callback이 timer를 재등록하는 것은 코드가 고려한 경로다. 재등록 자체를 list corruption 원인으로 단정하지 않는다.

선택한 platform에서 확인하기

ELF는 선택한 project의 symbol이 남아 있는 산출물로 바꾼다. static 함수는 최적화·strip 설정에 따라 보이지 않을 수 있다.

목적명령 또는 계측판정
timer modePLATFORM_HAS_DYNAMIC_TIMER 빌드 값 확인one-shot head 경로 / 10ms periodic 경로
timer symbolnm -an <ELF> | grep -E '[[:space:]](timer_init|timer_set_oneshot|timer_cancel)$'C 선언문이 아닌 symbol 이름
queue 상태CPU 번호·head deadline·node link 기록현재 CPU queue의 정렬과 head 변화
callback 문맥IRQ active·interrupt state·timer_lock 보유 여부 기록IRQ 문맥, callback에서 timer_lock 해제
reschedule 결과callback 반환, timer_tick 반환, 실제 preempt 시간 기록요청과 switch 시각 분리

세 가지 timer 실험

  1. 01
    head와 비-head 삽입 비교

    dynamic platform에서 새 head일 때와 아닌 때의 platform_set_oneshot_timer 호출 수를 기록한다.

  2. 02
    periodic callback 분기 비교

    callback이 그대로 반환, 직접 재등록, cancel 세 경우에 다음 scheduled_time과 queue link를 비교한다.

  3. 03
    cancel과 callback 진행 구분

    cancel 호출 시 node가 이미 dequeue된 경우를 계측하고 callback 종료와 owner free 시각을 따로 기록한다.

원문과 다음 글