Linux的动态定时器--时间轮

Linux的定时器—有时也称为动态定时器或内核定时器—是管理内核时间的基础。定时器是一种软件功能,即允许在将来的某个时刻,函数在给定的时间间隔用完时被调用。注意的是定时器并不会周期运行,它在超时后就自行销毁,这也是定时器被称为动态定时器的一个原因。动态定时器不断地创建和销毁,而且它的运行次数也不受限制。

定时器在内核代码中属于一个基础组件。要想完全弄清楚linux2.6中内核定时器的实现,得先从初始化开始。

在start_kernel(void)-->init_timers(void)

  1. void __init init_timers(void)  
  2. {  
  3.     int err = timer_cpu_notify(&timers_nb, (unsigned long)CPU_UP_PREPARE,  
  4.                 (void *)(long)smp_processor_id());  
  5.   
  6.     init_timer_stats();  
  7.   
  8.     BUG_ON(err == NOTIFY_BAD);  
  9.     register_cpu_notifier(&timers_nb);  
  10.     open_softirq(TIMER_SOFTIRQ, run_timer_softirq);  
  11. }  

timer_cpu_notify(&timers_nb,(unsigned long)CPU_UP_PREPARE,

(void*)(long)smp_processor_id());

中执行

init_timers_cpu(cpu) //初始化本cpu中的timers

初始化的主要代码是:

  1. spin_lock_init(&base->lock);  
  2.   
  3.     for (j = 0; j < TVN_SIZE; j++) {  
  4.         INIT_LIST_HEAD(base->tv5.vec + j);  
  5.         INIT_LIST_HEAD(base->tv4.vec + j);  
  6.         INIT_LIST_HEAD(base->tv3.vec + j);  
  7.         INIT_LIST_HEAD(base->tv2.vec + j);  
  8.     }  
  9.     for (j = 0; j < TVR_SIZE; j++)  
  10.         INIT_LIST_HEAD(base->tv1.vec + j);  
  11.   
  12.     base->timer_jiffies = jiffies;  
  13.     base->next_timer = base->timer_jiffies;  

这段代码的主体是basebase的定义是:structtvec_base *base;

这个tvec_base是动态定时器的主要数据结构,每个cpu上有一个,它包含相应cpu中处理动态定时器需要的所有数据。为简化分析仅考虑单cpu。给出这个数据机构:

  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;  

其中,timer_list是具体定时器的结构体(后面再具体看timer_list结构体);上面包含tv1tv2tv3tv4tv5;内核定时器的巧妙设计就在于此。

  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)   
  7.   
  8. struct tvec {  
  9.     struct list_head vec[TVN_SIZE];  
  10. };  
  11.   
  12. struct tvec_root {  
  13.     struct list_head vec[TVR_SIZE];  
  14. };  

从这个定义看到,tv1就是长度为256的数组,数组成员是list_head;同样的,tv2tv3tv4tv5都是长度为64的数组,数组成员是list_headList_head就是linux内核代码中广泛使用的双向链表。在阻塞和非阻塞中的等待队列时就看到了list_head的应用。那么,tv1-tv5都是数组+链表的实现,其实hash的有一种简单实现就是数组+链表的组合,那么这几个就有些hash的味道,具体是不是,还要分析道后面才知道。

再回到前面的初始化中,

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);

tv1-tv55个结构体中的数组中每个list_head进行初始化。

base->timer_jiffies= jiffies;

base->next_timer= base->timer_jiffies;

base中的timer_jiffiesnext_timer都初始化为jiffies

初始化完成后,在init_timers函数的第二个重要的步骤是:

open_softirq(TIMER_SOFTIRQ,run_timer_softirq);

下面来看具体定时器的初始化和添加操作:

初始化的函数:

  1. #define init_timer(timer)                       \   
  2.     do {                                \  
  3.         static struct lock_class_key __key;         \  
  4.         init_timer_key((timer), #timer, &__key);        \  
  5.     } while (0)  
  6.   
  7. void init_timer_key(struct timer_list *timer,  
  8.             const char *name,  
  9.             struct lock_class_key *key)  
  10. {  
  11.     debug_init(timer);  
  12.     __init_timer(timer, name, key);  
  13. }  
  14.   
  15. static void __init_timer(struct timer_list *timer,  
  16.              const char *name,  
  17.              struct lock_class_key *key)  
  18. {  
  19.     timer->entry.next = NULL;  
  20.     timer->base = __raw_get_cpu_var(tvec_bases);  
  21. #ifdef CONFIG_TIMER_STATS   
  22.     timer->start_site = NULL;  
  23.     timer->start_pid = -1;  
  24.     memset(timer->start_comm, 0, TASK_COMM_LEN);  
  25. #endif   
  26.     lockdep_init_map(&timer->lockdep_map, name, key, 0);  
  27. }  

初始化的宏定义:

  1. #define TIMER_INITIALIZER(_function, _expires, _data) {      \  
  2.         .entry = { .prev = TIMER_ENTRY_STATIC },    \  
  3.         .function = (_function),            \  
  4.         .expires = (_expires),              \  
  5.         .data = (_data),                \  
  6.         .base = &boot_tvec_bases,           \  
  7.         __TIMER_LOCKDEP_MAP_INITIALIZER(        \  
  8.             __FILE__ ":" __stringify(__LINE__)) \  
  9.     }  

定时器的添加:

  1. void add_timer(struct timer_list *timer)  
  2. {  
  3.     BUG_ON(timer_pending(timer));  
  4.     mod_timer(timer, timer->expires);  
  5. }  

Timer_list结构体的定义:

  1. struct timer_list {  
  2.     struct list_head entry;  
  3.     unsigned long expires;  
  4.   
  5.     void (*function)(unsigned long);  
  6.     unsigned long data;  
  7.   
  8.     struct tvec_base *base;  
  9. #ifdef CONFIG_TIMER_STATS   
  10.     void *start_site;  
  11.     char start_comm[16];  
  12.     int start_pid;  
  13. #endif   
  14. #ifdef CONFIG_LOCKDEP   
  15.     struct lockdep_map lockdep_map;  
  16. #endif   
  17. };  

 

  1. int mod_timer(struct timer_list *timer, unsigned long expires)  
  2. {  
  3.     /* 
  4.      * This is a common optimization triggered by the 
  5.      * networking code - if the timer is re-modified 
  6.      * to be the same thing then just return: 
  7.      */  
  8.     if (timer_pending(timer) && timer->expires == expires)  
  9.         return 1;  
  10.   
  11.     return __mod_timer(timer, expires, false, TIMER_NOT_PINNED);  
  12. }  

相关推荐