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;  

這段代碼的主體是base，base的定義是：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結構體)；上面包含tv1，tv2，tv3，tv4，tv5；內核定時器的巧妙設計就在於此。

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；同樣的，tv2，tv3，tv4和tv5都是長度為64的數組，數組成員是list_head。List_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-tv5這5個結構體中的數組中每個list_head進行初始化。

base->timer_jiffies= jiffies;

base->next_timer= base->timer_jiffies;

將base中的timer_jiffies和next_timer都初始化為jiffies。

初始化完成後，在init_timers函數的第二個重要的步驟是：

open_softirq(TIMER_SOFTIRQ,run_timer_softirq);

這個函數注冊定時器軟中斷，簡單的軟中斷分析見《Linux的軟中斷》 見 http://www.linuxidc.com/Linux/2012-04/57918.htm；

下面來看具體定時器的初始化和添加操作：

初始化的函數：

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. }