Linux中斷處理之時鐘中斷（二）

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

定時器部份到這裡就介紹完了.為了管理定時器.內核用了一個很巧妙的數據結構.值得好好的體會.

五:小結

2.6內核在時鐘管理子系統的修改比較大.因為在2.6完全摒棄掉了下半部機制.2.4中下半部處理的大部份都放在了中斷處理程序裡,只有定時器控制被移到了時鐘軟中斷.另外時鐘中斷初始化涉及到了很多硬件的操作.需要查閱相關資料才能完全理解.