# Linux定时器实现

## Linux时间轮的实现

#### 定义五个等级的数组

#define TVN_BITS 6
#define TVR_BITS 8
#define TVN_SIZE (1 << TVN_BITS)  // 64
#define TVR_SIZE (1 << TVR_BITS)  // 256

struct timer_vec {
int index;
};

struct timer_vec_root {
int index;
};

static struct timer_vec tv5;
static struct timer_vec tv4;
static struct timer_vec tv3;
static struct timer_vec tv2;
static struct timer_vec_root tv1;

void init_timervecs (void)
{
int i;

for (i = 0; i < TVN_SIZE; i++) {
}
for (i = 0; i < TVR_SIZE; i++)
}

#### 插入定时器

static inline void internal_add_timer(struct timer_list *timer)
{
/*
* must be cli-ed when calling this
*/
unsigned long expires = timer->expires;
unsigned long idx = expires - timer_jiffies;

if (idx < TVR_SIZE) { // 0 ~ 255
int i = expires & TVR_MASK;
vec = tv1.vec + i;
} else if (idx < 1 <> TVR_BITS) & TVN_MASK;
vec = tv2.vec + i;
} else if (idx < 1 <> (TVR_BITS + TVN_BITS)) & TVN_MASK;
vec =  tv3.vec + i;
} else if (idx < 1 <> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK;
vec = tv4.vec + i;
} else if ((signed long) idx < 0) {
/* can happen if you add a timer with expires == jiffies,
* or you set a timer to go off in the past
*/
vec = tv1.vec + tv1.index;
} else if (idx > (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;
vec = tv5.vec + i;
} else {
/* Can only get here on architectures with 64-bit jiffies */
return;
}
/*
* 添加到链表中
*/
}

internal_add_timer() 函数的主要工作是计算定时器到期时间所属的等级范围，然后把定时器添加到链表中。

#### 执行到期的定时器

static inline void cascade_timers(struct timer_vec *tv)
{
/* cascade all the timers from tv up one level */

/*
* We are removing _all_ timers from the list, so we don't  have to
* detach them individually, just clear the list afterwards.
*/
struct timer_list *tmp;

tmp = list_entry(curr, struct timer_list, list);
next = curr->next;
list_del(curr);
curr = next;
}
tv->index = (tv->index + 1) & TVN_MASK;
}

static inline void run_timer_list(void)
{
spin_lock_irq(&timerlist_lock);
while ((long)(jiffies - timer_jiffies) >= 0) {
if (!tv1.index) { // 完成了一个轮回, 移动下一个单位的定时器
int n = 1;
do {
} while (tvecs[n]->index == 1 && ++n next;
struct timer_list *timer;
void (*fn)(unsigned long);
unsigned long data;

timer = list_entry(curr, struct timer_list, list);
fn = timer->function;
data= timer->data;

detach_timer(timer);
timer->list.next = timer->list.prev = NULL;
timer_enter(timer);
spin_unlock_irq(&timerlist_lock);
fn(data);
spin_lock_irq(&timerlist_lock);
timer_exit();
goto repeat;
}
++timer_jiffies;
tv1.index = (tv1.index + 1) & TVR_MASK;
}
spin_unlock_irq(&timerlist_lock);
}