Implementing a Multi-Level Timing Wheel in C for Efficient Timer Management

Overview of the Multi‑Level Timing Wheel

The multi‑level timing wheel is a hierarchical timer mechanism similar to a clock: the lowest wheel advances on each tick, and when it completes a full rotation it increments the next higher wheel. Tasks are moved down the hierarchy until they reach the work wheel, where their callbacks are executed. The implementation uses five wheels, giving a timer range of 0 ~ 2³² ms (approximately 49 days).

Core Data Structures

Each wheel is represented by a struct. The first wheel ( tvec_root) has 256 slots; the remaining four wheels ( tvec) have 64 slots each.

Each slot contains a doubly linked list of timer objects, implemented with the generic struct list_head used in the Linux kernel.

The timer object ( struct timer_list) stores a list node, the absolute expiration time, a callback function pointer, a callback argument, and a back‑reference to its owning tvec_base.

struct tvec_base {
    unsigned long current_index;   /* current time in ms */
    pthread_t thincrejiffies;    /* thread that increments time */
    pthread_t threadID;          /* worker thread */
    struct tvec_root tv1;        /* first wheel (256 slots) */
    struct tvec tv2;            /* second wheel (64 slots) */
    struct tvec tv3;            /* third wheel (64 slots) */
    struct tvec tv4;            /* fourth wheel (64 slots) */
    struct tvec tv5;            /* fifth wheel (64 slots) */
};

Bitwise Slot Calculation Constants

#define TVN_BITS   6               /* 64 slots per higher wheel */
#define TVR_BITS   8               /* 256 slots for the first wheel */
#define TVN_SIZE   (1U << TVN_BITS)
#define TVR_SIZE   (1U << TVR_BITS)
#define TVN_MASK   (TVN_SIZE - 1)
#define TVR_MASK   (TVR_SIZE - 1)

These constants are used to select the appropriate wheel and slot by shifting the expiration offset and applying the masks.

Timer Insertion Logic

The function internal_add_timer computes the distance idx between the timer's expiration and the current index, chooses the correct wheel, and inserts the timer at the tail of the selected slot.

static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)
{
    unsigned long expires = timer->expires;
    unsigned long idx = expires - base->current_index;
    struct list_head *vec;

    if ((signed long)idx < 0) {
        /* Expiration already passed – place in current slot of first wheel */
        vec = base->tv1.vec + (base->current_index & TVR_MASK);
    } else if (idx < TVR_SIZE) {
        int i = expires & TVR_MASK;
        vec = base->tv1.vec + i;
    } else if (idx < 1U << (TVR_BITS + TVN_BITS)) {
        int i = (expires >> TVR_BITS) & TVN_MASK;
        vec = base->tv2.vec + i;
    } else if (idx < 1U << (TVR_BITS + 2*TVN_BITS)) {
        int i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK;
        vec = base->tv3.vec + i;
    } else if (idx < 1U << (TVR_BITS + 3*TVN_BITS)) {
        int i = (expires >> (TVR_BITS + 2*TVN_BITS)) & TVN_MASK;
        vec = base->tv4.vec + i;
    } else {
        int i;
        if (idx > 0xffffffffUL) {
            idx = 0xffffffffUL;
            expires = idx + base->current_index;
        }
        i = (expires >> (TVR_BITS + 3*TVN_BITS)) & TVN_MASK;
        vec = base->tv5.vec + i;
    }
    list_add_tail(&timer->entry, vec);
}

Timer Modification and Deletion API

The public function mod_timer updates a timer's expiration and re‑inserts it if necessary. Adding a timer is performed by ti_add_timer, which allocates a struct timer_list, fills its fields and calls the internal add routine. Deleting a timer is done with ti_del_timer, which removes the timer from its list and frees the memory.

int mod_timer(void *ptimer, unsigned long expires);
void *ti_add_timer(void *ptimewheel, unsigned long expires,
                  void (*handle)(unsigned long), unsigned long arg);
void ti_del_timer(void *timer);

Cascade Processing

When the lowest wheel wraps around (slot index 0), higher‑level wheels are cascaded: all timers in the current slot of the higher wheel are moved down to the appropriate lower‑level slots. The cascade function extracts the list from a slot, re‑adds each timer with internal_add_timer, and clears the original slot.

static int cascade(struct tvec_base *base, struct tvec *tv, int index)
{
    struct list_head *pos, *tmp, tv_list;
    list_replace_init(tv->vec + index, &tv_list);
    list_for_each_safe(pos, tmp, &tv_list) {
        struct timer_list *timer = list_entry(pos, struct timer_list, entry);
        internal_add_timer(base, timer);
    }
    return index;
}

Worker Thread

A dedicated thread runs deal_function_timeout. It repeatedly obtains the current wall‑clock time, advances current_index while processing the work list of the first wheel, executes each timer's callback, and performs cascading when the first wheel reaches slot 0.

static void *deal_function_timeout(void *arg)
{
    struct tvec_base *ba = (struct tvec_base *)arg;
    struct timeval tv;
    for (;;) {
        gettimeofday(&tv, NULL);
        while (ba->current_index <= (tv.tv_sec*1000 + tv.tv_usec/1000)) {
            int index = ba->current_index & TVR_MASK;
            if (!index &&
                !cascade(ba, &ba->tv2, INDEX(0)) &&
                !cascade(ba, &ba->tv3, INDEX(1)) &&
                !cascade(ba, &ba->tv4, INDEX(2)))
                cascade(ba, &ba->tv5, INDEX(3));
            ba->current_index++;
            struct list_head work_list;
            list_replace_init(ba->tv1.vec + index, &work_list);
            while (!list_empty(&work_list)) {
                struct timer_list *timer = list_first_entry(&work_list,
                                            struct timer_list, entry);
                void (*fn)(unsigned long) = timer->function;
                unsigned long data = timer->data;
                detach_timer(timer);
                fn(data);
            }
        }
    }
    return NULL;
}

Demo Program

The demo creates a timing wheel, registers a timer that prints a value every 3 seconds, and then loops indefinitely. The output shows repeated debug messages. If a timer callback blocks for a long time, subsequent timers are delayed because the worker thread processes callbacks sequentially.

#include "list.h"
#include "log.h"
/* ... (the full source code from the article) ... */

int main(int argc, char *argv[])
{
    void *pwheel = ti_timewheel_create();
    struct request_para *para = malloc(sizeof(*para));
    para->val = 100;
    para->timer = ti_add_timer(pwheel, 3000, mytimer, (unsigned long)para);
    while (1) sleep(2);
    ti_timewheel_release(pwheel);
    return 0;
}

Compilation and Execution

gcc mutiTimeWheel.c -lpthread -o timer_demo
./timer_demo

Typical output (debug messages) looks like:

[#DEBUG: Toeny Sun: mytimer:370]: 100

Visualization

The following image illustrates the five‑wheel cascade layout, where the central wheel is the work wheel and the outer wheels cascade tasks down to it.