利用定時器，我們可以設定在未來的某一時刻，觸發(fā)一個特定的事件。所謂低分辨率定時器，是指這種定時器的計時單位基于jiffies值的計數(shù)，也就是說，它的精度只有1/HZ，假如你的內(nèi)核配置的HZ是1000，那意味著系統(tǒng)中的低分辨率定時器的精度就是1ms。早期的內(nèi)核版本中，內(nèi)核并不支持高精度定時器，理所當然只能使用這種低分辨率定時器，我們有時候把這種基于HZ的定時器機制成為時間輪：time wheel。雖然后來出現(xiàn)了高分辨率定時器，但它只是內(nèi)核的一個可選配置項，所以直到目前最新的內(nèi)核版本，這種低分辨率定時器依然被大量地使用著。

1. ?定時器的使用方法

在討論定時器的實現(xiàn)原理之前，我們先看看如何使用定時器。要在內(nèi)核編程中使用定時器，首先我們要定義一個time_list結(jié)構(gòu)，該結(jié)構(gòu)在include/linux/timer.h中定義：

[cpp]?view plain?copy

struct?timer_list?{??

/*?

*?All?fields?that?change?during?normal?runtime?grouped?to?the?

*?same?cacheline?

*/??

struct?list_head?entry;??

unsigned?long?expires;??

struct?tvec_base?*base;??

void?(*function)(unsigned?long);??

unsigned?long?data;??

int?slack;??

......??

};??

entry ?字段用于把一組定時器組成一個鏈表，至于內(nèi)核如何對定時器進行分組，我們會在后面進行解釋。

expires??字段指出了該定時器的到期時刻，也就是期望定時器到期時刻的jiffies計數(shù)值。

base??每個cpu擁有一個自己的用于管理定時器的tvec_base結(jié)構(gòu)，該字段指向該定時器所屬的cpu所對應tvec_base結(jié)構(gòu)。

function??字段是一個函數(shù)指針，定時器到期時，系統(tǒng)將會調(diào)用該回調(diào)函數(shù)，用于響應該定時器的到期事件。

data??該字段用于上述回調(diào)函數(shù)的參數(shù)。

slack??對有些對到期時間精度不太敏感的定時器，到期時刻允許適當?shù)匮舆t一小段時間，該字段用于計算每次延遲的HZ數(shù)。

要定義一個timer_list，我們可以使用靜態(tài)和動態(tài)兩種辦法，靜態(tài)方法使用DEFINE_TIMER宏：

#define DEFINE_TIMER(_name, _function, _expires, _data)

該宏將得到一個名字為_name，并分別用_function,_expires,_data參數(shù)填充timer_list的相關(guān)字段。

如果要使用動態(tài)的方法，則可以自己聲明一個timer_list結(jié)構(gòu)，然后手動初始化它的各個字段：

[cpp]?view plain?copy

struct?timer_list?timer;??

......??

init_timer(&timer);??

timer.function?=?_function;??

timer.expires?=?_expires;??

timer.data?=?_data;??

要激活一個定時器，我們只要調(diào)用add_timer即可：

[cpp]?view plain?copy

add_timer(&timer);??

要修改定時器的到期時間，我們只要調(diào)用mod_timer即可：

[cpp]?view plain?copy

mod_timer(&timer,?jiffies+50);??

要移除一個定時器，我們只要調(diào)用del_timer即可：

[cpp]?view plain?copy

del_timer(&timer);??

定時器系統(tǒng)還提供了以下這些API供我們使用：

void add_timer_on(struct timer_list *timer, int cpu); ?// 在指定的cpu上添加定時器

int mod_timer_pending(struct timer_list *timer, unsigned long expires); ?// ?只有當timer已經(jīng)處在激活狀態(tài)時，才修改timer的到期時刻

int mod_timer_pinned(struct timer_list *timer, unsigned long expires); ?// ?當

void set_timer_slack(struct timer_list *time, int slack_hz); ?// ?設定timer允許的到期時刻的最大延遲，用于對精度不敏感的定時器

int del_timer_sync(struct timer_list *timer); ?// ?如果該timer正在被處理中，則等待timer處理完成才移除該timer

2. ?定時器的軟件架構(gòu)

低分辨率定時器是基于HZ來實現(xiàn)的，也就是說，每個tick周期，都有可能有定時器到期，關(guān)于tick如何產(chǎn)生，請參考：Linux時間子系統(tǒng)之四：定時器的引擎：clock_event_device。系統(tǒng)中有可能有成百上千個定時器，難道在每個tick中斷中遍歷一下所有的定時器，檢查它們是否到期？內(nèi)核當然不會使用這么笨的辦法，它使用了一個更聰明的辦法：按定時器的到期時間對定時器進行分組。因為目前的多核處理器使用越來越廣泛，連智能手機的處理器動不動就是4核心，內(nèi)核對多核處理器有較好的支持，低分辨率定時器在實現(xiàn)時也充分地考慮了多核處理器的支持和優(yōu)化。為了較好地利用cache line，也為了避免cpu之間的互鎖，內(nèi)核為多核處理器中的每個cpu單獨分配了管理定時器的相關(guān)數(shù)據(jù)結(jié)構(gòu)和資源，每個cpu獨立地管理屬于自己的定時器。

2.1 ?定時器的分組

首先，內(nèi)核為每個cpu定義了一個tvec_base結(jié)構(gòu)指針：

[cpp]?view plain?copy

static?DEFINE_PER_CPU(struct?tvec_base?*,?tvec_bases)?=?&boot_tvec_bases;??

tvec_base結(jié)構(gòu)的定義如下：

[cpp]?view plain?copy

struct?tvec_base?{??

spinlock_t?lock;??

struct?timer_list?*running_timer;??

unsigned?long?timer_jiffies;??

unsigned?long?next_timer;??

struct?tvec_root?tv1;??

struct?tvec?tv2;??

struct?tvec?tv3;??

struct?tvec?tv4;??

struct?tvec?tv5;??

}?____cacheline_aligned;??

running_timer? 該字段指向當前cpu正在處理的定時器所對應的timer_list結(jié)構(gòu)。

timer_jiffies? 該字段表示當前cpu定時器所經(jīng)歷過的jiffies數(shù)，大多數(shù)情況下，該值和jiffies計數(shù)值相等，當cpu的idle狀態(tài)連續(xù)持續(xù)了多個jiffies時間時，當退出idle狀態(tài)時，jiffies計數(shù)值就會大于該字段，在接下來的tick中斷后，定時器系統(tǒng)會讓該字段的值追趕上jiffies值。

next_timer? 該字段指向該cpu下一個即將到期的定時器。

tv1--tv5??這5個字段用于對定時器進行分組，實際上，tv1--tv5都是一個鏈表數(shù)組，其中tv1的數(shù)組大小為TVR_SIZE， tv2 tv3 tv4 tv5的數(shù)組大小為TVN_SIZE，根據(jù)CONFIG_BASE_SMALL配置項的不同，它們有不同的大?。?/p>

[cpp]?view plain?copy

#define?TVN_BITS?(CONFIG_BASE_SMALL???4?:?6)??

#define?TVR_BITS?(CONFIG_BASE_SMALL???6?:?8)??

#define?TVN_SIZE?(1?<

#define?TVR_SIZE?(1?<

#define?TVN_MASK?(TVN_SIZE?-?1)??

#define?TVR_MASK?(TVR_SIZE?-?1)??

struct?tvec?{??

struct?list_head?vec[TVN_SIZE];??

};??

struct?tvec_root?{??

struct?list_head?vec[TVR_SIZE];??

};??

默認情況下，沒有使能CONFIG_BASE_SMALL，TVR_SIZE的大小是256，TVN_SIZE的大小則是64，當需要節(jié)省內(nèi)存空間時，也可以使能CONFIG_BASE_SMALL，這時TVR_SIZE的大小是64，TVN_SIZE的大小則是16，以下的討論我都是基于沒有使能CONFIG_BASE_SMALL的情況。當有一個新的定時器要加入時，系統(tǒng)根據(jù)定時器到期的jiffies值和timer_jiffies字段的差值來決定該定時器被放入tv1至tv5中的哪一個數(shù)組中，最終，系統(tǒng)中所有的定時器的組織結(jié)構(gòu)如下圖所示：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??圖 2.1.1 ?定時器在系統(tǒng)中的組織結(jié)構(gòu)

2.2 ?定時器的添加

要加入一個新的定時器，我們可以通過api函數(shù)add_timer或mod_timer來完成，最終的工作會交由internal_add_timer函數(shù)來處理。該函數(shù)按以下步驟進行處理：

計算定時器到期時間和所屬cpu的tvec_base結(jié)構(gòu)中的timer_jiffies字段的差值，記為idx；

根據(jù)idx的值，選擇該定時器應該被放到tv1--tv5中的哪一個鏈表數(shù)組中，可以認為tv1-tv5分別占據(jù)一個32位數(shù)的不同比特位，tv1占據(jù)最低的8位，tv2占據(jù)緊接著的6位，然后tv3再占位，以此類推，最高的6位分配給tv5。最終的選擇規(guī)則如下表所示：

鏈表數(shù)組idx范圍tv10-255(2^8)tv2256--16383(2^14)tv316384--1048575(2^20)tv41048576--67108863(2^26)tv567108864--4294967295(2^32)

確定鏈表數(shù)組后，接著要確定把該定時器放入數(shù)組中的哪一個鏈表中，如果時間差idx小于256，按規(guī)則要放入tv1中，因為tv1包含了256個鏈表，所以可以簡單地使用timer_list.expires的低8位作為數(shù)組的索引下標，把定時器鏈接到tv1中相應的鏈表中即可。如果時間差idx的值在256--18383之間，則需要把定時器放入tv2中，同樣的，使用timer_list.expires的8--14位作為數(shù)組的索引下標，把定時器鏈接到tv2中相應的鏈表中,。定時器要加入tv3 tv4 tv5使用同樣的原理。經(jīng)過這樣分組后的定時器，在后續(xù)的tick事件中，系統(tǒng)可以很方便地定位并取出相應的到期定時器進行處理。以上的討論都體現(xiàn)在internal_add_timer的代碼中：

[cpp]?view plain?copy

static?void?internal_add_timer(struct?tvec_base?*base,?struct?timer_list?*timer)??

{??

unsigned?long?expires?=?timer->expires;??

unsigned?long?idx?=?expires?-?base->timer_jiffies;??

struct?list_head?*vec;??

if?(idx?

int?i?=?expires?&?TVR_MASK;??

vec?=?base->tv1.vec?+?i;??

}?else?if?(idx?

int?i?=?(expires?>>?TVR_BITS)?&?TVN_MASK;??

vec?=?base->tv2.vec?+?i;??

}?else?if?(idx?

int?i?=?(expires?>>?(TVR_BITS?+?TVN_BITS))?&?TVN_MASK;??

vec?=?base->tv3.vec?+?i;??

}?else?if?(idx?

int?i?=?(expires?>>?(TVR_BITS?+?2?*?TVN_BITS))?&?TVN_MASK;??

vec?=?base->tv4.vec?+?i;??

}?else?if?((signed?long)?idx?

......??

}?else?{??

......??

i?=?(expires?>>?(TVR_BITS?+?3?*?TVN_BITS))?&?TVN_MASK;??

vec?=?base->tv5.vec?+?i;??

}??

list_add_tail(&timer->entry,?vec);??

}??

2.2 ?定時器的到期處理

經(jīng)過2.1節(jié)的處理后，系統(tǒng)中的定時器按到期時間有規(guī)律地放置在tv1--tv5各個鏈表數(shù)組中，其中tv1中放置著在接下來的256個jiffies即將到期的定時器列表，需要注意的是，并不是tv1.vec[0]中放置著馬上到期的定時器列表，tv1.vec[1]中放置著將在jiffies+1到期的定時器列表。因為base.timer_jiffies的值一直在隨著系統(tǒng)的運行而動態(tài)地增加，原則上是每個tick事件會加1，base.timer_jiffies代表者該cpu定時器系統(tǒng)當前時刻，定時器也是動態(tài)地加入頭256個鏈表tv1中，按2.1節(jié)的討論，定時器加入tv1中使用的下標索引是定時器到期時間expires的低8位，所以假設當前的base.timer_jiffies值是0x34567826，則馬上到期的定時器是在tv1.vec[0x26]中，如果這時候系統(tǒng)加入一個在jiffies值0x34567828到期的定時器，他將會加入到tv1.vec[0x28]中，運行兩個tick后，base.timer_jiffies的值會變?yōu)?x34567828，很顯然，在每次tick事件中，定時器系統(tǒng)只要以base.timer_jiffies的低8位作為索引，取出tv1中相應的鏈表，里面正好包含了所有在該jiffies值到期的定時器列表。

那什么時候處理tv2--tv5中的定時器？每當base.timer_jiffies的低8位為0值時，這表明base.timer_jiffies的第8-13位有進位發(fā)生，這6位正好代表著tv2，這時只要按base.timer_jiffies的第8-13位的值作為下標，移出tv2中對應的定時器鏈表，然后用internal_add_timer把它們從新加入到定時器系統(tǒng)中來，因為這些定時器一定會在接下來的256個tick期間到期，所以它們肯定會被加入到tv1數(shù)組中，這樣就完成了tv2往tv1遷移的過程。同樣地，當base.timer_jiffies的第8-13位為0時，這表明base.timer_jiffies的第14-19位有進位發(fā)生，這6位正好代表著tv3，按base.timer_jiffies的第14-19位的值作為下標，移出tv3中對應的定時器鏈表，然后用internal_add_timer把它們從新加入到定時器系統(tǒng)中來，顯然它們會被加入到tv2中，從而完成tv3到tv2的遷移，tv4，tv5的處理可以以此作類推。具體遷移的代碼如下，參數(shù)index為事先計算好的高一級tv的需要遷移的數(shù)組索引：

[cpp]?view plain?copy

static?int?cascade(struct?tvec_base?*base,?struct?tvec?*tv,?int?index)??

{??

/*?cascade?all?the?timers?from?tv?up?one?level?*/??

struct?timer_list?*timer,?*tmp;??

struct?list_head?tv_list;??

list_replace_init(tv->vec?+?index,?&tv_list);??//??移除需要遷移的鏈表??

/*?

*?We?are?removing?_all_?timers?from?the?list,?so?we?

*?don't?have?to?detach?them?individually.?

*/??

list_for_each_entry_safe(timer,?tmp,?&tv_list,?entry)?{??

BUG_ON(tbase_get_base(timer->base)?!=?base);??

//??重新加入到定時器系統(tǒng)中，實際上將會遷移到下一級的tv數(shù)組中??

internal_add_timer(base,?timer);????

}??

return?index;??

}??

每個tick事件到來時，內(nèi)核會在tick定時中斷處理期間激活定時器軟中斷：TIMER_SOFTIRQ，關(guān)于軟件中斷，請參考另一篇博文：Linux中斷（interrupt）子系統(tǒng)之五：軟件中斷（softIRQ。TIMER_SOFTIRQ的執(zhí)行函數(shù)是__run_timers，它實現(xiàn)了本節(jié)討論的邏輯，取出tv1中到期的定時器，執(zhí)行定時器的回調(diào)函數(shù)，由此可見，低分辨率定時器的回調(diào)函數(shù)是執(zhí)行在軟件中斷上下文中的，這點在寫定時器的回調(diào)函數(shù)時需要注意。__run_timers的代碼如下：

[cpp]?view plain?copy

static?inline?void?__run_timers(struct?tvec_base?*base)??

{??

struct?timer_list?*timer;??

spin_lock_irq(&base->lock);??

/*?同步jiffies，在NO_HZ情況下，base->timer_jiffies可能落后不止一個tick??*/??

while?(time_after_eq(jiffies,?base->timer_jiffies))?{????

struct?list_head?work_list;??

struct?list_head?*head?=?&work_list;??

/*??計算到期定時器鏈表在tv1中的索引??*/??

int?index?=?base->timer_jiffies?&?TVR_MASK;????

/*?

*?/*??tv2--tv5定時器列表遷移處理??*/??

*/??

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

/*??該cpu定時器系統(tǒng)運行時間遞增一個tick??*/???????????????????

++base->timer_jiffies;????

/*??取出到期的定時器鏈表??*/?????????????????????????????????????????

list_replace_init(base->tv1.vec?+?index,?&work_list);??

/*??遍歷所有的到期定時器??*/????????????

while?(!list_empty(head))?{??????????????????????????????????????

void?(*fn)(unsigned?long);??

unsigned?long?data;??

timer?=?list_first_entry(head,?struct?timer_list,entry);??

fn?=?timer->function;??

data?=?timer->data;??

timer_stats_account_timer(timer);??

base->running_timer?=?timer;????/*??標記正在處理的定時器??*/??

detach_timer(timer,?1);??

spin_unlock_irq(&base->lock);??

call_timer_fn(timer,?fn,?data);??/*??調(diào)用定時器的回調(diào)函數(shù)??*/??

spin_lock_irq(&base->lock);??

}??

}??

base->running_timer?=?NULL;??

spin_unlock_irq(&base->lock);??

}??

通過上面的討論，我們可以發(fā)現(xiàn)，內(nèi)核的低分辨率定時器的實現(xiàn)非常精妙，既實現(xiàn)了大量定時器的管理，又實現(xiàn)了快速的O(1)查找到期定時器的能力，利用巧妙的數(shù)組結(jié)構(gòu)，使得只需在間隔256個tick時間才處理一次遷移操作，5個數(shù)組就好比是5個齒輪，它們隨著base->timer_jifffies的增長而不停地轉(zhuǎn)動，每次只需處理第一個齒輪的某一個齒節(jié)，低一級的齒輪轉(zhuǎn)動一圈，高一級的齒輪轉(zhuǎn)動一個齒，同時自動把即將到期的定時器遷移到上一個齒輪中，所以低分辨率定時器通常又被叫做時間輪：time wheel。事實上，它的實現(xiàn)是一個很好的空間換時間軟件算法。

3. ?定時器軟件中斷

系統(tǒng)初始化時，start_kernel會調(diào)用定時器系統(tǒng)的初始化函數(shù)init_timers：

[cpp]?view plain?copy

void?__init?init_timers(void)??

{????????

int?err?=?timer_cpu_notify(&timers_nb,?(unsigned?long)CPU_UP_PREPARE,???

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

init_timer_stats();??

BUG_ON(err?!=?NOTIFY_OK);??

register_cpu_notifier(&timers_nb);??/*?注冊cpu?notify，以便在hotplug時在cpu之間進行定時器的遷移?*/??

open_softirq(TIMER_SOFTIRQ,?run_timer_softirq);??

}??

可見，open_softirq把run_timer_softirq注冊為TIMER_SOFTIRQ的處理函數(shù)，另外，當cpu的每個tick事件到來時，在事件處理中斷中，update_process_times會被調(diào)用，該函數(shù)會進一步調(diào)用run_local_timers，run_local_timers會觸發(fā)TIMER_SOFTIRQ軟中斷：

[cpp]?view plain?copy

void?run_local_timers(void)??

{??

hrtimer_run_queues();??

raise_softirq(TIMER_SOFTIRQ);??

}??

TIMER_SOFTIRQ的處理函數(shù)是run_timer_softirq：

[cpp]?view plain?copy

static?void?run_timer_softirq(struct?softirq_action?*h)??

{??

struct?tvec_base?*base?=?__this_cpu_read(tvec_bases);??

hrtimer_run_pending();??

if?(time_after_eq(jiffies,?base->timer_jiffies))??

__run_timers(base);??

}??

好啦，終于看到__run_timers函數(shù)了，2.2節(jié)已經(jīng)介紹過，正是這個函數(shù)完成了對到期定時器的處理工作，也完成了時間輪的不停轉(zhuǎn)動。

?