在模塊的編寫過程中，我們經常使用定時器來等待一段時間之後再來執行某一個操作。為方便分析，寫了下列一段測試程序：
#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;
}
定時器部份到這裏就介紹完了.為了管理定時器.內核用了一個很巧妙的數據結構.值得好好的體會.