電子發燒友App
利用定時器，我們可以設定在未來的某一時刻，觸發一個特定的事件。所謂低分辨率定時器，是指這種定時器的計時單位基于jiffies值的計數，也就是說，它的精度只有1/HZ，假如你的內核配置的HZ是1000，那意味著系統中的低分辨率定時器的精度就是1ms。早期的內核版本中，內核并不支持高精度定時器，理所當然只能使用這種低分辨率定時器，我們有時候把這種基于HZ的定時器機制成為時間輪：time wheel。雖然后來出現了高分辨率定時器，但它只是內核的一個可選配置項，所以直到目前最新的內核版本，這種低分辨率定時器依然被大量地使用著。
1. ?定時器的使用方法
在討論定時器的實現原理之前，我們先看看如何使用定時器。要在內核編程中使用定時器，首先我們要定義一個time_list結構，該結構在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 ?字段用于把一組定時器組成一個鏈表，至于內核如何對定時器進行分組，我們會在后面進行解釋。
expires??字段指出了該定時器的到期時刻，也就是期望定時器到期時刻的jiffies計數值。
base??每個cpu擁有一個自己的用于管理定時器的tvec_base結構，該字段指向該定時器所屬的cpu所對應tvec_base結構。
function??字段是一個函數指針，定時器到期時，系統將會調用該回調函數，用于響應該定時器的到期事件。
data??該字段用于上述回調函數的參數。
slack??對有些對到期時間精度不太敏感的定時器，到期時刻允許適當地延遲一小段時間，該字段用于計算每次延遲的HZ數。
要定義一個timer_list，我們可以使用靜態和動態兩種辦法，靜態方法使用DEFINE_TIMER宏：
#define DEFINE_TIMER(_name, _function, _expires, _data)
該宏將得到一個名字為_name，并分別用_function,_expires,_data參數填充timer_list的相關字段。
如果要使用動態的方法，則可以自己聲明一個timer_list結構，然后手動初始化它的各個字段：
[cpp]?view plain?copy
struct?timer_list?timer;??
......??
init_timer(&timer);??
timer.function?=?_function;??
timer.expires?=?_expires;??
timer.data?=?_data;??
要激活一個定時器，我們只要調用add_timer即可：
[cpp]?view plain?copy
add_timer(&timer);??
要修改定時器的到期時間，我們只要調用mod_timer即可：
[cpp]?view plain?copy
mod_timer(&timer,?jiffies+50);??
要移除一個定時器，我們只要調用del_timer即可：
[cpp]?view plain?copy
del_timer(&timer);??
定時器系統還提供了以下這些API供我們使用：
void add_timer_on(struct timer_list *timer, int cpu); ?// 在指定的cpu上添加定時器
int mod_timer_pending(struct timer_list *timer, unsigned long expires); ?// ?只有當timer已經處在激活狀態時，才修改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. ?定時器的軟件架構
低分辨率定時器是基于HZ來實現的，也就是說，每個tick周期，都有可能有定時器到期，關于tick如何產生，請參考：Linux時間子系統之四：定時器的引擎：clock_event_device。系統中有可能有成百上千個定時器，難道在每個tick中斷中遍歷一下所有的定時器，檢查它們是否到期？內核當然不會使用這么笨的辦法，它使用了一個更聰明的辦法：按定時器的到期時間對定時器進行分組。因為目前的多核處理器使用越來越廣泛，連智能手機的處理器動不動就是4核心，內核對多核處理器有較好的支持，低分辨率定時器在實現時也充分地考慮了多核處理器的支持和優化。為了較好地利用cache line，也為了避免cpu之間的互鎖，內核為多核處理器中的每個cpu單獨分配了管理定時器的相關數據結構和資源，每個cpu獨立地管理屬于自己的定時器。
2.1 ?定時器的分組
首先，內核為每個cpu定義了一個tvec_base結構指針：
[cpp]?view plain?copy
static?DEFINE_PER_CPU(struct?tvec_base?*,?tvec_bases)?=?&boot_tvec_bases;??
tvec_base結構的定義如下：
[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結構。
timer_jiffies? 該字段表示當前cpu定時器所經歷過的jiffies數，大多數情況下，該值和jiffies計數值相等，當cpu的idle狀態連續持續了多個jiffies時間時，當退出idle狀態時，jiffies計數值就會大于該字段，在接下來的tick中斷后，定時器系統會讓該字段的值追趕上jiffies值。
next_timer? 該字段指向該cpu下一個即將到期的定時器。
tv1--tv5??這5個字段用于對定時器進行分組，實際上，tv1--tv5都是一個鏈表數組，其中tv1的數組大小為TVR_SIZE， tv2 tv3 tv4 tv5的數組大小為TVN_SIZE，根據CONFIG_BASE_SMALL配置項的不同，它們有不同的大小：
[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，當需要節省內存空間時，也可以使能CONFIG_BASE_SMALL，這時TVR_SIZE的大小是64，TVN_SIZE的大小則是16，以下的討論我都是基于沒有使能CONFIG_BASE_SMALL的情況。當有一個新的定時器要加入時，系統根據定時器到期的jiffies值和timer_jiffies字段的差值來決定該定時器被放入tv1至tv5中的哪一個數組中，最終，系統中所有的定時器的組織結構如下圖所示：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??圖 2.1.1 ?定時器在系統中的組織結構
2.2 ?定時器的添加
要加入一個新的定時器，我們可以通過api函數add_timer或mod_timer來完成，最終的工作會交由internal_add_timer函數來處理。該函數按以下步驟進行處理：
計算定時器到期時間和所屬cpu的tvec_base結構中的timer_jiffies字段的差值，記為idx；
根據idx的值，選擇該定時器應該被放到tv1--tv5中的哪一個鏈表數組中，可以認為tv1-tv5分別占據一個32位數的不同比特位，tv1占據最低的8位，tv2占據緊接著的6位，然后tv3再占位，以此類推，最高的6位分配給tv5。最終的選擇規則如下表所示：
鏈表數組idx范圍tv10-255(2^8)tv2256--16383(2^14)tv316384--1048575(2^20)tv41048576--67108863(2^26)tv567108864--4294967295(2^32)
確定鏈表數組后，接著要確定把該定時器放入數組中的哪一個鏈表中，如果時間差idx小于256，按規則要放入tv1中，因為tv1包含了256個鏈表，所以可以簡單地使用timer_list.expires的低8位作為數組的索引下標，把定時器鏈接到tv1中相應的鏈表中即可。如果時間差idx的值在256--18383之間，則需要把定時器放入tv2中，同樣的，使用timer_list.expires的8--14位作為數組的索引下標，把定時器鏈接到tv2中相應的鏈表中,。定時器要加入tv3 tv4 tv5使用同樣的原理。經過這樣分組后的定時器，在后續的tick事件中，系統可以很方便地定位并取出相應的到期定時器進行處理。以上的討論都體現在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 ?定時器的到期處理
經過2.1節的處理后，系統中的定時器按到期時間有規律地放置在tv1--tv5各個鏈表數組中，其中tv1中放置著在接下來的256個jiffies即將到期的定時器列表，需要注意的是，并不是tv1.vec[0]中放置著馬上到期的定時器列表，tv1.vec[1]中放置著將在jiffies+1到期的定時器列表。因為base.timer_jiffies的值一直在隨著系統的運行而動態地增加，原則上是每個tick事件會加1，base.timer_jiffies代表者該cpu定時器系統當前時刻，定時器也是動態地加入頭256個鏈表tv1中，按2.1節的討論，定時器加入tv1中使用的下標索引是定時器到期時間expires的低8位，所以假設當前的base.timer_jiffies值是0x34567826，則馬上到期的定時器是在tv1.vec[0x26]中，如果這時候系統加入一個在jiffies值0x34567828到期的定時器，他將會加入到tv1.vec[0x28]中，運行兩個tick后，base.timer_jiffies的值會變為0x34567828，很顯然，在每次tick事件中，定時器系統只要以base.timer_jiffies的低8位作為索引，取出tv1中相應的鏈表，里面正好包含了所有在該jiffies值到期的定時器列表。
那什么時候處理tv2--tv5中的定時器？每當base.timer_jiffies的低8位為0值時，這表明base.timer_jiffies的第8-13位有進位發生，這6位正好代表著tv2，這時只要按base.timer_jiffies的第8-13位的值作為下標，移出tv2中對應的定時器鏈表，然后用internal_add_timer把它們從新加入到定時器系統中來，因為這些定時器一定會在接下來的256個tick期間到期，所以它們肯定會被加入到tv1數組中，這樣就完成了tv2往tv1遷移的過程。同樣地，當base.timer_jiffies的第8-13位為0時，這表明base.timer_jiffies的第14-19位有進位發生，這6位正好代表著tv3，按base.timer_jiffies的第14-19位的值作為下標，移出tv3中對應的定時器鏈表，然后用internal_add_timer把它們從新加入到定時器系統中來，顯然它們會被加入到tv2中，從而完成tv3到tv2的遷移，tv4，tv5的處理可以以此作類推。具體遷移的代碼如下，參數index為事先計算好的高一級tv的需要遷移的數組索引：
[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);??
//??重新加入到定時器系統中，實際上將會遷移到下一級的tv數組中??
internal_add_timer(base,?timer);????
}??
return?index;??
}??
每個tick事件到來時，內核會在tick定時中斷處理期間激活定時器軟中斷：TIMER_SOFTIRQ，關于軟件中斷，請參考另一篇博文：Linux中斷（interrupt）子系統之五：軟件中斷（softIRQ。TIMER_SOFTIRQ的執行函數是__run_timers，它實現了本節討論的邏輯，取出tv1中到期的定時器，執行定時器的回調函數，由此可見，低分辨率定時器的回調函數是執行在軟件中斷上下文中的，這點在寫定時器的回調函數時需要注意。__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定時器系統運行時間遞增一個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);??/*??調用定時器的回調函數??*/??
spin_lock_irq(&base->lock);??
}??
}??
base->running_timer?=?NULL;??
spin_unlock_irq(&base->lock);??
}??
通過上面的討論，我們可以發現，內核的低分辨率定時器的實現非常精妙，既實現了大量定時器的管理，又實現了快速的O(1)查找到期定時器的能力，利用巧妙的數組結構，使得只需在間隔256個tick時間才處理一次遷移操作，5個數組就好比是5個齒輪，它們隨著base->timer_jifffies的增長而不停地轉動，每次只需處理第一個齒輪的某一個齒節，低一級的齒輪轉動一圈，高一級的齒輪轉動一個齒，同時自動把即將到期的定時器遷移到上一個齒輪中，所以低分辨率定時器通常又被叫做時間輪：time wheel。事實上，它的實現是一個很好的空間換時間軟件算法。
3. ?定時器軟件中斷
系統初始化時，start_kernel會調用定時器系統的初始化函數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的處理函數，另外，當cpu的每個tick事件到來時，在事件處理中斷中，update_process_times會被調用，該函數會進一步調用run_local_timers，run_local_timers會觸發TIMER_SOFTIRQ軟中斷：
[cpp]?view plain?copy
void?run_local_timers(void)??
{??
hrtimer_run_queues();??
raise_softirq(TIMER_SOFTIRQ);??
}??
TIMER_SOFTIRQ的處理函數是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函數了，2.2節已經介紹過，正是這個函數完成了對到期定時器的處理工作，也完成了時間輪的不停轉動。
?
工商網監
評論