Timer Wheel 분석 — Hashed·Hierarchical·O(1) Tick

1
struct timer { uint32_t expiry; struct timer *next; };
2
struct timer *head;
3

4
void add_timer(struct timer *t, uint32_t ms) {
5
    t->expiry = now() + ms;
6
    insert_sorted(&head, t);   /* O(N) */
7
}
8

9
void tick(void) {
10
    while (head && head->expiry <= now()) {
11
        head->callback();
12
        head = head->next;
13
    }
14
}

1
struct timer heap[N];   /* min-heap by expiry */
2

3
void add(struct timer *t) {
4
    heap_push(heap, t);   /* O(log N) */
5
}
6

7
void tick(void) {
8
    while (heap[0].expiry <= now()) {
9
        heap[0].callback();
10
        heap_pop(heap);
11
    }
12
}

1
#define WHEEL_SIZE 256
2

3
struct slot {
4
    struct timer *head;
5
};
6

7
struct wheel {
8
    struct slot slots[WHEEL_SIZE];
9
    uint32_t current_tick;
10
} g_wheel;
11

12
void add_timer(struct timer *t, uint32_t ms) {
13
    uint32_t expiry = g_wheel.current_tick + ms;
14
    uint32_t slot = expiry % WHEEL_SIZE;
15
    t->expiry = expiry;
16
    t->next = g_wheel.slots[slot].head;
17
    g_wheel.slots[slot].head = t;
18
}
19

20
void tick(void) {
21
    uint32_t slot = g_wheel.current_tick % WHEEL_SIZE;
22
    struct timer *t = g_wheel.slots[slot].head;
23
    g_wheel.slots[slot].head = NULL;
24

25
    while (t) {
26
        struct timer *next = t->next;
27
        if (t->expiry == g_wheel.current_tick) {
28
            t->callback();
29
        } else {
30
            /* Wrapped — re-add */
31
            uint32_t new_slot = t->expiry % WHEEL_SIZE;
32
            t->next = g_wheel.slots[new_slot].head;
33
            g_wheel.slots[new_slot].head = t;
34
        }
35
        t = next;
36
    }
37
    g_wheel.current_tick++;
38
}

1
9 level, 각 64 slot:
2
  level 0: 1ms × 64
3
  level 1: 64ms × 64
4
  level 2: 4s × 64
5
  ...
6

7
Cascade 없음 — 각 level 직접 expiry 처리
8
Tick O(1) + occasional level 0 process

1
struct rte_timer t;
2
rte_timer_init(&t);
3
rte_timer_reset(&t, 1000000 /* hz */, PERIODICAL, lcore_id, callback, arg);

1
/* TIM2 — compare 4 channel */
2
HAL_TIM_OC_Start_IT(&htim2, TIM_CHANNEL_1);
3
TIM2->CCR1 = expiry_ticks;   /* trigger at expiry */
4

5
void HAL_TIM_OC_DelayElapsedCallback(...) {
6
    timer_at_expiry_handler();
7
}

1
esp_timer_handle_t timer;
2
esp_timer_create_args_t args = {
3
    .callback = &my_callback,
4
    .arg = data,
5
    .name = "mytimer",
6
};
7
esp_timer_create(&args, &timer);
8
esp_timer_start_once(timer, 1000000);   /* 1 sec */
9
esp_timer_start_periodic(timer, 500000);   /* 500 ms */

1
#define LVL0_SLOTS 64
2
#define LVL1_SLOTS 64
3
#define LVL_BITS 6   /* log2(64) */
4

5
struct level {
6
    struct list_head slots[64];
7
    uint32_t current;
8
};
9

10
struct hwheel {
11
    struct level levels[4];
12
    uint64_t time;
13
};
14

15
void add(uint64_t expiry) {
16
    uint64_t delta = expiry - hwheel.time;
17
    int level;
18
    if (delta < 64) level = 0;
19
    else if (delta < 64*64) level = 1;
20
    else if (delta < 64*64*64) level = 2;
21
    else level = 3;
22

23
    int slot = (expiry >> (level * LVL_BITS)) & 63;
24
    list_add(&hwheel.levels[level].slots[slot], ...);
25
}
26

27
void tick(void) {
28
    hwheel.time++;
29
    int l0 = hwheel.time & 63;
30
    expire_all(&hwheel.levels[0].slots[l0]);
31
    if (l0 == 0) {
32
        cascade(1);   /* level 1 → 0 */
33
        ...
34
    }
35
}

1
add_timer(t, expiry);   /* O(N) — 1000 timer 시 1 µs+ per add */

1
WHEEL_SIZE = 256
2
add(timer, expiry = current + 1000);   /* ← slot 996 = (current+1000) % 256 = same slot of current+232? */

1
configTICK_RATE_HZ = 10000;   /* 100 µs tick — overhead 큼 */

1
cancel_timer(t);   /* O(N) — list search */