linux 内核定时器timer_list详解

在模块的编写过程中，我们经常使用定时器来等待一段时间之后再来执行某一个操作。为方便分析，写了下列一段测试程序：
#include 

#include 
#include 
#include 
#include 
#include 
 
MODULE_LICENSE("GPL");
void test_timerfuc(unsigned long x)
{
         printk("Eric xiao test ......\n");
}
//声明一个定个器
struct timer_list test_timer = TIMER_INITIALIZER(test_timerfuc, 0, 0);
 
int kernel_test_init()
{
         printk("test_init\n");
         //修改定时器到期时间。为3个HZ。一个HZ产生一个时钟中断
         mod_timer(&test_timer,jiffies+3*HZ);
         //把定时器加入时钟软中断处理链表
         add_timer(&test_timer);
 
}
 
int kernel_test_exit()
{
         printk("test_exit\n");
 
         return 0;
}
module_init(kernel_test_init);
module_exit(kernel_test_exit);
上面的例子程序比较简单，我们从这个例子开始研究linux下的定时器实现。
TIMER_INITIALIZER（）：
1):TIMER_INITIALIZER（）用来声明一个定时器，它的定义如下：
#define TIMER_INITIALIZER(_function, _expires, _data) {             \
                   .function = (_function),                            \
                   .expires = (_expires),                                \
                   .data = (_data),                                \
                   .base = NULL,                                         \
                   .magic = TIMER_MAGIC,                              \
                   .lock = SPIN_LOCK_UNLOCKED,                         \
         }
Struct timer_list定义如下：
struct timer_list {
         //用来形成链表
         struct list_head entry;
         //定始器到达时间
         unsigned long expires;
 
         spinlock_t lock;
         unsigned long magic;
         //定时器时间到达后，所要运行的函数
         void (*function)(unsigned long);
         //定时器函数对应的参数
         unsigned long data;
 
         //挂载这个定时器的tvec_t_base_s.这个结构我们等会会看到，当该次中断顺利执行后，该值也将清空为NULL
  struct tvec_t_base_s *base;  
};
从上面的过程中我们可以看到TIMER_INITIALIZER（）只是根据传入的参数初始化了struct timer_list结构.并把magic 成员初始化成TIMER_MAGIC
2): mod_timer():修改定时器的到时时间
int mod_timer(struct timer_list *timer, unsigned long expires)
{
         //如果该定时器没有定义fuction
         BUG_ON(!timer->function);
         //判断timer的magic是否为TIMER_MAGIC.如果不是,则将其修正为TIMER_MAGIC
         check_timer(timer);
 
         //如果要调整的时间就是定时器的定时时间而且已经被激活,则直接返回
         if (timer->expires == expires && timer_pending(timer))
                   return 1;
         //调用_mod_timer().呆会再给出分析
         return __mod_timer(timer, expires);
}
3): add_timer()用来将定时器挂载到定时软中断队列,激活该定时器
static inline void add_timer(struct timer_list * timer)
{
         __mod_timer(timer, timer->expires);
}
可以看到mod_timer与add_timer 最后都会调用__mod_timer().为了分析这个函数,我们先来了解一下定时系统相关的数据结构.
tvec_bases: per cpu变量,它的定义如下:
static DEFINE_PER_CPU(tvec_base_t, tvec_bases) = { SPIN_LOCK_UNLOCKED };
由此可以看到tves_bases的数型数据为teves_base_t.数据结构的定义如下:
typedef struct tvec_t_base_s tvec_base_t;
struct tvec_t_base_s的定义:
struct tvec_t_base_s {
         spinlock_t lock;
         //上一次运行计时器的jiffies 值这个值很关键，正是这个值保证了不会遗漏定时器中断，timer中断中每次循环查找后，该值加一
         unsigned long timer_jiffies;
         struct timer_list *running_timer;
         //tv1 tv2 tv3 tv4 tv5是五个链表数组
         tvec_root_t tv1;
         tvec_t tv2;
         tvec_t tv3;
         tvec_t tv4;
         tvec_t tv5;
} ____cacheline_aligned_in_smp;
Tves_root_t与tvec_t的定义如下:
#define TVN_BITS 6
#define TVR_BITS 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)
 
typedef struct tvec_s {
         struct list_head vec[TVN_SIZE];
} tvec_t;
 
typedef struct tvec_root_s {
         struct list_head vec[TVR_SIZE];
} tvec_root_t;
系统规定定时器最大超时时间间隔为0xFFFFFFFF.即为一个32位数.即使在64位系统上.如果超过此值也会将其强制设这oxFFFFFFFF(这在后面的代码分析中可以看到).内核最关心的就是间隔在0~255个HZ之间的定时器.次重要的是间隔在255~1<<(8+6)之间的定时器.第三重要的是间隔在1<<(8+6) ~ 1<<(8+6+6)之间的定器.依次往下推.也就是把32位的定时间隔为份了五个部份.1个8位.4个6位.所以内核定义了五个链表数组.第一个链表数组大小为8位大小,也即上面定义的 #define TVR_SIZE (1 << TVR_BITS).其它的四个数组大小为6位大小.即上面定义的#define TVN_SIZE (1 << TVN_BITS)
在加入定时器的时候,按照时间间隔把定时器加入到相应的数组即可.了解这点之后,就可以来看__mod_timer()的代码了:
//修改timer或者新增一个timer都会调用此接口
int __mod_timer(struct timer_list *timer, unsigned long expires)
{
         tvec_base_t *old_base, *new_base;
         unsigned long flags;
         int ret = 0;
 
         //入口参数检测
         BUG_ON(!timer->function);
 
         check_timer(timer);
 
         spin_lock_irqsave(&timer->lock, flags);
         //取得当前CPU对应的tvec_bases
         new_base = &__get_cpu_var(tvec_bases);
repeat:
         //该定时器所在的tvec_bases.对于新增的timer.它的base字段为NULL
         old_base = timer->base;
 
         /*
          * Prevent deadlocks via ordering by old_base < new_base.
          */
 
         //在把timer从当前tvec_bases摘下来之前,要充分考虑好竞争的情况
         if (old_base && (new_base != old_base)) {
                   //按次序获得锁
                   if (old_base < new_base) {
                            spin_lock(&new_base->lock);
                            spin_lock(&old_base->lock);
                   } else {
                            spin_lock(&old_base->lock);
                            spin_lock(&new_base->lock);
                   }
                   /*
                    * The timer base might have been cancelled while we were
                    * trying to take the lock(s):
                    */
                    //如果timer->base != old_base.那就是说在Lock的时候.其它CPU更改它的值
                    //那就解锁.重新判断
                   if (timer->base != old_base) {
                            spin_unlock(&new_base->lock);
                            spin_unlock(&old_base->lock);
                            goto repeat;
                   }
         } else {
                   //old_base == NULl 或者是 new_base==old_base的情况
                   //获得锁
                   spin_lock(&new_base->lock);
                   //同理,在Lock的时候timer会生了改变
                   if (timer->base != old_base) {
                            spin_unlock(&new_base->lock);
                            goto repeat;
                   }
         }
 
         /*
          * Delete the previous timeout (if there was any), and install
          * the new one:
          */
          //将其从其它的tvec_bases上删除.注意运行到这里的话,说话已经被Lock了
         if (old_base) {
                   list_del(&timer->entry);
                   ret = 1;
         }
         //修改它的定时器到达时间
         timer->expires = expires;
         //将其添加到new_base中
         internal_add_timer(new_base, timer);
         //修改base字段
         timer->base = new_base;
 
         //操作完了,解锁
         if (old_base && (new_base != old_base))
                   spin_unlock(&old_base->lock);
         spin_unlock(&new_base->lock);
         spin_unlock_irqrestore(&timer->lock, flags);
 
         return ret;
}
internal_add_timer()的代码如下:
static void internal_add_timer(tvec_base_t *base, struct timer_list *timer)
{
         //定时器到达的时间
         unsigned long expires = timer->expires;
         //计算时间间间隔
         unsigned long idx = expires - base->timer_jiffies;
         struct list_head *vec;
 
         //根据时间间隔,将timer放入相应数组的相应位置
         if (idx < TVR_SIZE) {
                   int i = expires & TVR_MASK;
                   vec = base->tv1.vec + i;
         } else if (idx < 1 << (TVR_BITS + TVN_BITS)) {
                   int i = (expires >> TVR_BITS) & TVN_MASK;
                   vec = base->tv2.vec + i;
         } else if (idx < 1 << (TVR_BITS + 2 * TVN_BITS)) {
                   int i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK;
                   vec = base->tv3.vec + i;
         } else if (idx < 1 << (TVR_BITS + 3 * TVN_BITS)) {
                   int i = (expires >> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK;
                   vec = base->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
                    */
                    //如果间隔小于0
                   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:
                    */
                    //时间间隔超长,将其设为oxFFFFFFFF
                   if (idx > 0xffffffffUL) {
                            idx = 0xffffffffUL;
                            expires = idx + base->timer_jiffies;
                   }
                   i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;
                   vec = base->tv5.vec + i;
         }
         /*
          * Timers are FIFO:
          */
          //加入到链表末尾
         list_add_tail(&timer->entry, vec);
}
计算时间间隔即可知道要加入到哪一个数组.哪又怎么计算加入到该数组的那一项呢?
对于间隔时间在0~255的定时器: 它的计算方式是将定时器到达时间的低八位与低八位为1的数相与而成
对于第1个六位,它是先将到达时间右移8位.然后与低六位全为1的数相与而成
对于第2个六位, 它是先将到达时间右移8+6位.然后与低六位全为1的数相与而成
依次为下推…
在后面结合超时时间到达的情况再来分析相关部份
4):定时器更新
每过一个HZ,就会检查当前是否有定时器的定时器时间到达.如果有,运行它所注册的函数,再将其删除.为了分析这一过程,我们先从定时器系统的初始化看起.
asmlinkage void __init start_kernel(void)
{
         ……
         init_timers();
         ……
}
Init_timers()的定义如下:
void __init init_timers(void)
{
         timer_cpu_notify(&timers_nb, (unsigned long)CPU_UP_PREPARE,
                                     (void *)(long)smp_processor_id());
         register_cpu_notifier(&timers_nb);
         //注册TIMER_SOFTIRQ软中断
         open_softirq(TIMER_SOFTIRQ, run_timer_softirq, NULL);
}
timer_cpu_notify()àinit_timers_cpu():
代码如下:
static void /* __devinit */ init_timers_cpu(int cpu)
{
         int j;
         tvec_base_t *base;
     //初始化各个数组中的链表  
         base = &per_cpu(tvec_bases, cpu);
         spin_lock_init(&base->lock);
         for (j = 0; j < TVN_SIZE; j++) {
                   INIT_LIST_HEAD(base->tv5.vec + j);
                   INIT_LIST_HEAD(base->tv4.vec + j);
                   INIT_LIST_HEAD(base->tv3.vec + j);
                   INIT_LIST_HEAD(base->tv2.vec + j);
         }
         for (j = 0; j < TVR_SIZE; j++)
                   INIT_LIST_HEAD(base->tv1.vec + j);
         //将最近到达时间设为当前jiffies
         base->timer_jiffies = jiffies;
}
我们在前面分析过,每当时钟当断函数到来的时候,就会打开定时器的软中断.运行其软中断函数.run_timer_softirq()
代码如下:
static void run_timer_softirq(struct softirq_action *h)
{
         //取得当于CPU的tvec_base_t结构
         tvec_base_t *base = &__get_cpu_var(tvec_bases);
         //如果jiffies > base->timer_jiffies
         if (time_after_eq(jiffies, base->timer_jiffies))
                   __run_timers(base);
}
__run_timers()代码如下:
static inline void __run_timers(tvec_base_t *base)
{
         struct timer_list *timer;
         unsigned long flags;
 
         spin_lock_irqsave(&base->lock, flags);
         //因为CPU可能关闭中断,引起时钟中断信号丢失.可能jiffies要大base->timer_jiffies 好几个
         //HZ
         while (time_after_eq(jiffies, base->timer_jiffies)) {
                   //定义并初始化一个链表
                   struct list_head work_list = LIST_HEAD_INIT(work_list);
                   struct list_head *head = &work_list;
                  int index = base->timer_jiffies & TVR_MASK;
 
                   /*
                    * Cascade timers:
                    */
                    //当index == 0时,说明已经循环了一个周期
                   //则将tv2填充tv1.如果tv2为空,则用tv3填充tv2.依次类推...... 
                   if (!index &&
                            (!cascade(base, &base->tv2, INDEX(0))) &&
                                     (!cascade(base, &base->tv3, INDEX(1))) &&
                                               !cascade(base, &base->tv4, INDEX(2)))
                            cascade(base, &base->tv5, INDEX(3));
                   //更新base->timer_jiffies
                   ++base->timer_jiffies; 
                   //将base->tv1.vec项移至work_list.并将base->tv1.vec置空
                   list_splice_init(base->tv1.vec + index, &work_list);
repeat:
                   //work_List中的定时器是已经到时的定时器
                   if (!list_empty(head)) {
                            void (*fn)(unsigned long);
                            unsigned long data;
 
                            //遍历链表中的每一项.运行它所对应的函数,并将定时器从链表上脱落
                            timer = list_entry(head->next,struct timer_list,entry);
                           fn = timer->function;
                           data = timer->data;
 
                            list_del(&timer->entry);
                            set_running_timer(base, timer);
                            smp_wmb();
                            timer->base = NULL;
                            spin_unlock_irqrestore(&base->lock, flags);
                            fn(data);
                            spin_lock_irq(&base->lock);
                            goto repeat;
                   }
         }
         set_running_timer(base, NULL);
         spin_unlock_irqrestore(&base->lock, flags);
}
如果base->timer_jiffies低八位为零.说明它向第九位有进位.所以把第九位到十五位对应的定时器搬到前八位对应的数组.如果第九位到十五位为空的话.就到它的上个六位去搬数据.上面的代码也说明.要经过1<<8个HZ才会更新全部数组中的定时器.这样做的效率是很高的.
分析下里面的两个重要的子函数:
static int cascade(tvec_base_t *base, tvec_t *tv, int index)
{
         /* cascade all the timers from tv up one level */
         struct list_head *head, *curr;
 
         //取数组中序号对应的链表
         head = tv->vec + index;
         curr = head->next;
         /*
          * We are removing _all_ timers from the list, so we don't  have to
          * detach them individually, just clear the list afterwards.
          */
          //遍历这个链表,将定时器重新插入到base中
         while (curr != head) {
                   struct timer_list *tmp;
 
                   tmp = list_entry(curr, struct timer_list, entry);
                   BUG_ON(tmp->base != base);
                   curr = curr->next;
                   internal_add_timer(base, tmp);
         }
         //将链表设为初始化状态
         INIT_LIST_HEAD(head);
 
         return index;
}
 
//将list中的数据放入head中,并将list置为空
static inline void list_splice_init(struct list_head *list,
                                         struct list_head *head)
{
         if (!list_empty(list)) {
                   __list_splice(list, head);
                   INIT_LIST_HEAD(list);
         }
}
//将list中的数据放入head
static inline void __list_splice(struct list_head *list,
                                      struct list_head *head)
{
         //list的第一个元素
         struct list_head *first = list->next;
         //list的最后一个元素
         struct list_head *last = list->prev;
         //head的第一个元素
         struct list_head *at = head->next;
 
         将first对应的链表链接至head
         first->prev = head;
         head->next = first;
 
         //将head 原有的数据加入到链表末尾
         last->next = at;
         at->prev = last;
}
5):del_timer()删除定时器
//删除一个timer
int del_timer(struct timer_list *timer)
{
         unsigned long flags;
         tvec_base_t *base;
 
         check_timer(timer);
 
repeat:
        base = timer->base;
         //该定时器没有被激活
         if (!base)
                   return 0;
         //加锁
         spin_lock_irqsave(&base->lock, flags);
         //如果在加锁的过程中,有其它操作改变了timer
         if (base != timer->base) {
                   spin_unlock_irqrestore(&base->lock, flags);
                   goto repeat;
         }
         //将timer从链表中删除
         list_del(&timer->entry);
         timer->base = NULL;
         spin_unlock_irqrestore(&base->lock, flags);
 
         return 1;
}
6): del_timer_sync()有竞争情况下的定时器删除
在SMP系统中,可能要删除的定时器正在某一个CPU上运行.为了防止这种在情况.在删除定时器的时候,应该优先使用del_timer_synsc().它会一直等待所有CPU上的定时器执行完成.
int del_timer_sync(struct timer_list *timer)
{
         tvec_base_t *base;
         int i, ret = 0;
 
         check_timer(timer);
 
del_again:
         //删除些定时器
         ret += del_timer(timer);
         //遍历CPU
         for_each_online_cpu(i) {
                   base = &per_cpu(tvec_bases, i);
                   //如果此CPU正在运行这个timer
                   if (base->running_timer == timer) {
                            //一直等待,直到这个CPU执行完
                            while (base->running_timer == timer) {
                                     cpu_relax();
                                     preempt_check_resched();
                            }
                            break;
                   }
         }
         smp_rmb();
         //如果这个timer又被调用.再删除
         if (timer_pending(timer))
                   goto del_again;
 
         return ret;
}
定时器部份到这里就介绍完了.为了管理定时器.内核用了一个很巧妙的数据结构.值得好好的体会.