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