Linux定时器相关源码分析

　　Linux的定时器使用时间轮算法。数据结构不难理解，核心数据结构与散列表及其相似，甚至可以说，就是散列表。事实上，理解其散列表的本质，有助于对相关操作的理解。

　　数据结构　

　　这里先列出一些宏，稍后解释：　

1 #define TVN_BITS (CONFIG_BASE_SMALL ? 4 : 6)
2 #define TVR_BITS (CONFIG_BASE_SMALL ? 6 : 8)
3 #define TVN_SIZE (1 << TVN_BITS)
4 #define TVR_SIZE (1 << TVR_BITS)
5 #define TVN_MASK (TVN_SIZE - 1)
6 #define TVR_MASK (TVR_SIZE - 1)

最基本的数据结构称为定时器向量，其实就是一个数组，数组类型就是在linux中不厌其烦用到的双向循环链表。代码如下：

1 struct tvec {
2     struct list_head vec[TVN_SIZE];
3 };
4 
5 struct tvec_root {
6     struct list_head vec[TVR_SIZE];
7 };

　　示意图如图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。

　　各个定时器被组织在一个大时间轮里面：

 1 struct tvec_base {
 2     spinlock_t lock;
 3     struct timer_list *running_timer;
 4     unsigned long timer_jiffies;
 5     unsigned long next_timer;
 6     struct tvec_root tv1;
 7     struct tvec tv2;
 8     struct tvec tv3;
 9     struct tvec tv4;
10     struct tvec tv5;
11 } ____cacheline_aligned;

　　定时器添加　　

　　代码如下:

 1 static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)
 2 {
 3     unsigned long expires = timer->expires;
 4     unsigned long idx = expires - base->timer_jiffies;
 5     struct list_head *vec;
 6 
 7     if (idx < TVR_SIZE) {
 8         int i = expires & TVR_MASK;
 9         vec = base->tv1.vec + i;
10     } else if (idx < 1 << (TVR_BITS + TVN_BITS)) {
11         int i = (expires >> TVR_BITS) & TVN_MASK;
12         vec = base->tv2.vec + i;
13     } else if (idx < 1 << (TVR_BITS + 2 * TVN_BITS)) {
14         int i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK;
15         vec = base->tv3.vec + i;
16     } else if (idx < 1 << (TVR_BITS + 3 * TVN_BITS)) {
17         int i = (expires >> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK;
18         vec = base->tv4.vec + i;
19     } else if ((signed long) idx < 0) {
20         /*
21          * Can happen if you add a timer with expires == jiffies,
22          * or you set a timer to go off in the past
23          */
24         vec = base->tv1.vec + (base->timer_jiffies & TVR_MASK);
25     } else {
26         int i;
27         /* If the timeout is larger than 0xffffffff on 64-bit
28          * architectures then we use the maximum timeout:
29          */
30         if (idx > 0xffffffffUL) {
31             idx = 0xffffffffUL;
32             expires = idx + base->timer_jiffies;
33         }
34         i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;
35         vec = base->tv5.vec + i;
36     }
37     /*
38      * Timers are FIFO:
39      */
40     list_add_tail(&timer->entry, vec);
41 }

　　当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函数就是求余函数。

　　其他

　　其他问题包括删除定时器，调整定时器等，日后有空再分析。但是有了前面的基础，我想会好理解多了。