Linux的定时器使用时间轮算法。数据结构不难理解，核心数据结构与散列表及其相似，甚至可以说，就是散列表。事实上，理解其散列表的本质，有助于对相关操作的理解。
数据结构
这里先列出一些宏，稍后解释：
#define TVN_BITS (CONFIG_BASE_SMALL ? 4 : 6)
#define TVR_BITS (CONFIG_BASE_SMALL ? 6 : 8)
#define TVN_SIZE (1 << TVN_BITS)
#define TVR_SIZE (1 << TVR_BITS)
#define TVN_MASK (TVN_SIZE - 1)
#define TVR_MASK (TVR_SIZE - 1)
最基本的数据结构称为定时器向量，其实就是一个数组，数组类型就是在linux中不厌其烦用到的双向循环链表。代码如下：
struct tvec {
struct list_head vec[TVN_SIZE];
};
struct tvec_root {
struct list_head vec[TVR_SIZE];
};
示意图如图1:
图1 定时器向量
每个双向队列中timer的expires时间都相同。Linux(32位)中延迟时间用unsign int表示，因此最大为0xFFFFFFFF，如果要表示这么多时间，那数组太大了，肯定是不行的。因此，用了五个这样定时器向量来表示所示，分别为tv1~tv5。tv1是tvec_root类型，tv2~tv5是tvec类型，区别就在于数组大小。前者是TVR_SIZE，后者是TVN_SIZE，即256和64。
根据定时器的到期时间间隔interval=expires-jiffies来决定放入哪一个时间向量。
0~0xff放到tv1,
0x100~0x3fff放到tv2,
0x4000~0xfffff放到tv3,
0x100000~0x3ffffff放到tv4,
0x4000000~0xffffff放到tv5。
各个定时器被组织在一个大时间轮里面：
struct tvec_base {
spinlock_t lock;
struct timer_list *running_timer;
unsigned long timer_jiffies;
unsigned long next_timer;
struct tvec_root tv1;
struct tvec tv2;
struct tvec tv3;
struct tvec tv4;
struct tvec tv5;
} ____cacheline_aligned;
定时器添加
代码如下:
static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)
{
unsigned long expires = timer->expires;
unsigned long idx = expires - base->timer_jiffies;
struct list_head *vec; if (idx < TVR_SIZE) {
int i = expires & TVR_MASK;
vec = base->tv1.vec + i;
} else if (idx < << (TVR_BITS + TVN_BITS)) {
int i = (expires >> TVR_BITS) & TVN_MASK;
vec = base->tv2.vec + i;
} else if (idx < << (TVR_BITS + * TVN_BITS)) {
int i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK;
vec = base->tv3.vec + i;
} else if (idx < << (TVR_BITS + * TVN_BITS)) {
int i = (expires >> (TVR_BITS + * TVN_BITS)) & TVN_MASK;
vec = base->tv4.vec + i;
} else if ((signed long) idx < ) {
/*
* Can happen if you add a timer with expires == jiffies,
* or you set a timer to go off in the past
*/
vec = base->tv1.vec + (base->timer_jiffies & TVR_MASK);
} else {
int i;
/* If the timeout is larger than 0xffffffff on 64-bit
* architectures then we use the maximum timeout:
*/
if (idx > 0xffffffffUL) {
idx = 0xffffffffUL;
expires = idx + base->timer_jiffies;
}
i = (expires >> (TVR_BITS + * TVN_BITS)) & TVN_MASK;
vec = base->tv5.vec + i;
}
/*
* Timers are FIFO:
*/
list_add_tail(&timer->entry, vec);
}
当idx < TVR_SIZE时，显然应当放到tv1中。但是具体放到哪个槽呢？按照我的理解，就应该放到第idx个槽中。事实上不是。因为tv1其实是一个时间轮，有一个时间指针在这个轮上走，这个指针就是timer_jiffies%TVR_SIZE。当timer_jiffies%TVR_SIZE==0时，就走完了一圈。因此应该放到这个指针+idx的位置。而且，如果这个指针在靠近数组的末端，比如254，idx值假设为30，那么254+30=284，显然这是一个相对位置。这里用了一个巧妙的方法来计算，即i=expires&TVR_MASK。由于TVR_MASK=TVR_SIZE-1，而TVR_SIZE=1<<TVR_BITS，在这种情况下expires&TVR_MASK=expires%TVR_SIZE，即求余操作。求余操作解决了相对位置的问题，而位运算则比求余运算更高效。
到了求余就好理解前面说的理解为散列表了。hash函数就是求余函数。
其他
其他问题包括删除定时器，调整定时器等，日后有空再分析。但是有了前面的基础，我想会好理解多了。