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());
6. init_timer_stats();
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);
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);
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)
8. struct tvec {
9. struct list_head vec[TVN_SIZE];
10. };
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)
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. }
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;
5. void (*function)(unsigned long);
6. unsigned long data;
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;
11. return __mod_timer(timer, expires, false, TIMER_NOT_PINNED);
12. }