在 Linux 操作系統中,很多活動都和時間有關,例如:進程調度和網絡處理 等等。所以說,了解 Linux 操作系統中的時鐘處理機制有助於更好地了解 Linux 操作系統的運作方式。本文分析了 Linux 2.6.25 內核的時鐘處理機制, 首先介紹了在計算機系統中的一些硬件計時器,然後重點介紹了 Linux 操作系 統中的硬件時鐘和軟件時鐘的處理過程以及軟件時鐘的應用。最後對全文進行了 總結。
1 計算機系統中的計時器
在計算機系統中存在著許多硬件計時器,例如 Real Timer Clock ( RTC ) 、Time Stamp Counter ( TSC ) 和 Programmable Interval Timer ( PIT ) 等等。
這部分內容不是本文的中點,這裡僅僅簡單介紹幾種,更多內容參見參考文 獻:
Real Timer Clock ( RTC ):
獨立於整個計算機系統(例如: CPU 和其他 chip )
內核利用其獲取系統當前時間和日期
Time Stamp Counter ( TSC ):
從 Pentium 起,提供一個寄存器 TSC,用來累計每一次外部振蕩器產生的時 鐘信號
通過指令 rdtsc 訪問這個寄存器
比起 PIT,TSC 可以提供更精確的時間測量
Programmable Interval Timer ( PIT ):
時間測量設備
內核使用的產生時鐘中斷的設備,產生的時鐘中斷依賴於硬件的體系結構, 慢的為 10 ms 一次,快的為 1 ms 一次
High Precision Event Timer ( HPET ):
PIT 和 RTC 的替代者,和之前的計時器相比,HPET 提供了更高的時鐘頻率 (至少10 MHz )以及更寬的計數器寬度(64位)
一個 HPET 包括了一個固定頻率的數值增加的計數器以及3到32個獨立的計時 器,這每一個計時器有包涵了一個比較器和一個寄存器(保存一個數值,表示觸 發中斷的時機)。每一個比較器都比較計數器中的數值和寄存器中的數值,當這 兩個數值相等時,將產生一個中斷
2 硬件時鐘處理
這裡所說的硬件時鐘處理特指的是硬件計時器時鐘中斷的處理過程。
2.1 數據結構
和硬件計時器(本文又稱作硬件時鐘,區別於軟件時鐘)相關的數據結構主 要有兩個:
struct clocksource :對硬件設備的抽象,描述時鐘源信息
struct clock_event_device :時鐘的事件信息,包括當硬件時鐘中斷發生 時要執行那些操作(實際上保存了相應函數的指針)。本文將該結構稱作為 “時鐘事件設備”。
上述兩個結構內核源代碼中有較詳細的注解,分別位於文件 clocksource.h 和 clockchips.h 中。需要特別注意的是結構 clock_event_device 的成員 event_handler ,它指定了當硬件時鐘中斷發生時,內核應該執行那些操作,也 就是真正的時鐘中斷處理函數。 在2.3節“時鐘初始化”部分會介紹 它真正指向哪個函數。
Linux 內核維護了兩個鏈表,分別存儲了系統中所有時鐘源的信息和時鐘事 件設備的信息。這兩個鏈表的表頭在內核中分別是 clocksource_list 和 clockevent_devices 。圖2-1顯示了這兩個鏈表。
圖2-1 時鐘源鏈表和時鐘事件鏈表
2.2 通知鏈技術( notification chain )
在時鐘處理這部分中,內核用到了所謂的“通知鏈( notification chain )”技術。所以在介紹時鐘處理過程之前先來了解下“通知鏈 ”技術。
在 Linux 內核中,各個子系統之間有很強的相互關系,一些被一個子系統生 成或者被探測到的事件,很可能是另一個或者多個子系統感興趣的,也就是說這 個事件的獲取者必須能夠通知所有對該事件感興趣的子系統,並且還需要這種通 知機制具有一定的通用性。基於這些, Linux 內核引入了“通知鏈 ”技術。
2.2.1 數據結構:
通知鏈有四種類型,
原子通知鏈( Atomic notifier chains ):通知鏈元素的回調函數(當事 件發生時要執行的函數)只能在中斷上下文中運行,不允許阻塞
可阻塞通知鏈( Blocking notifier chains ):通知鏈元素的回調函數在 進程上下文中運行,允許阻塞
原始通知鏈( Raw notifier chains ):對通知鏈元素的回調函數沒有任何 限制,所有鎖和保護機制都由調用者維護
SRCU 通知鏈( SRCU notifier chains ):可阻塞通知鏈的一種變體
所以對應了四種通知鏈頭結構:
struct atomic_notifier_head :原子通知鏈的鏈頭
struct blocking_notifier_head :可阻塞通知鏈的鏈頭
struct raw_notifier_head :原始通知鏈的鏈頭
struct srcu_notifier_head : SRCU 通知鏈的鏈頭
通知鏈元素的類型:
struct notifier_block :通知鏈中的元素,記錄了當發出通知時,應該執 行的操作(即回調函數)
鏈頭中保存著指向元素鏈表的指針。通知鏈元素結構則保存著回調函數的類 型以及優先級,參見 notifier.h 文件。
2.2.2 運作機制
通知鏈的運作機制包括兩個角色:
被通知者:對某一事件感興趣一方。定義了當事件發生時,相應的處理函數 ,即回調函數。但需要事先將其注冊到通知鏈中(被通知者注冊的動作就是在通 知鏈中增加一項)。
通知者:事件的通知者。當檢測到某事件,或者本身產生事件時,通知所有 對該事件感興趣的一方事件發生。他定義了一個通知鏈,其中保存了每一個被通 知者對事件的處理函數(回調函數)。通知這個過程實際上就是遍歷通知鏈中的 每一項,然後調用相應的事件處理函數。
包括以下過程:
通知者定義通知鏈
被通知者向通知鏈中注冊回調函數
當事件發生時,通知者發出通知(執行通知鏈中所有元素的回調函數)
整個過程可以看作是“發布——訂閱”模型(參見參 考資料)
被通知者調用 notifier_chain_register 函數注冊回調函數,該函數按照優 先級將回調函數加入到通知鏈中 。注銷回調函數則使用 notifier_chain_unregister 函數,即將回調函數從通知鏈中刪除。2.2.1節講 述的4種通知鏈各有相應的注冊和注銷函數,但是他們最終都是調用上述兩個函 數完成注冊和注銷功能的。有興趣的讀者可以自行查閱內核代碼。
通知者調用 notifier_call_chain 函數通知事件的到達,這個函數會遍歷通 知鏈中所有的元素,然後依次調用每一個的回調函數(即完成通知動作)。 2.2.1節講述的4種通知鏈也都有其對應的通知函數,這些函數也都是最終調用 notifier_call_chain 函數完成事件的通知。
更多關於通知鏈的內容,參見參考文獻。
由以上的敘述,“通知鏈”技術可以概括為:事件的被通知者將 事件發生時應該執行的操作通過函數指針方式保存在鏈表(通知鏈)中,然後當 事件發生時通知者依次執行鏈表中每一個元素的回調函數完成通知。
2.3 時鐘初始化
內核初始化部分( start_kernel 函數)和時鐘相關的過程主要有以下幾個 :
tick_init()
init_timers()
hrtimers_init()
time_init()
其中函數 hrtimers_init() 和高精度時鐘相關(本文暫不介紹這部分內容) 。下面將詳細介紹剩下三個函數。
2.3.1 tick_init 函數
函數 tick_init() 很簡單,調用 clockevents_register_notifier 函數向 clockevents_chain 通知鏈注冊元素: tick_notifier。這個元素的回調函數指 明了當時鐘事件設備信息發生變化(例如新加入一個時鐘事件設備等等)時,應 該執行的操作,該回調函數為 tick_notify (參見2.4節)。
2.3.2 init_timers 函數
函數 init_timers() 的實現如清單2-1(省略了部分和
主要功能無關的內容,以後代碼同樣方式處理)
清單2-1 init_timers 函數
void __init init_timers(void)
{
int err = timer_cpu_notify(&timers_nb, (unsigned long) CPU_UP_PREPARE,
(void *)(long) smp_processor_id());
……
register_cpu_notifier(&timers_nb);
open_softirq(TIMER_SOFTIRQ,run_timer_softirq, NULL);
}
代碼解釋:
初始化本 CPU 上的軟件時鐘相關的數據結構,參見3.2節
向 cpu_chain 通知鏈注冊元素 timers_nb ,該元素的回調函數用於初始化 指定 CPU 上的軟件時鐘相關的數據結構
初始化時鐘的軟中斷處理函數
2.3.3 time_init 函數
函數 time_init 的實現如清單2-2
清單2-2 time_init 函數
void __init time_init(void)
{
……
init_tsc_clocksource();
late_time_init = choose_time_init();
}
函數 init_tsc_clocksource 初始化 tsc 時鐘源。choose_time_init 實際 是函數 hpet_time_init ,其代碼清單2-3
清單2-3 hpet_time_init 函數
void __init hpet_time_init(void)
{
if (!hpet_enable())
setup_pit_timer();
setup_irq(0, &irq0);
}
函數 hpet_enable 檢測系統是否可以使用 hpet 時鐘,如果可以則初始化 hpet 時鐘。否則初始化 pit 時鐘。最後設置硬件時鐘發生時的處理函數(參見 2.4節)。
初始化硬件時鐘這個過程主要包括以下兩個過程(參見 hpet_enable 的實現 ):
初始化時鐘源信息( struct clocksource 類型的變量),並將其添加到時 鐘源鏈表中,即 clocksource_list 鏈表(參見圖2-1)。
初始化時鐘事件設備信息( struct clock_event_device 類型的變量),並 向通知鏈 clockevents_chain 發布通知:一個時鐘事件設備要被添加到系統中 。在通知(執行回調函數)結束後,該時鐘事件設備被添加到時鐘事件設備鏈表 中,即 clockevent_devices 鏈表(參見圖2-1)。有關通知鏈的內容參見2.2節 。
需要注意的是在初始化時鐘事件設備時,全局變量 global_clock_event 被 賦予了相應的值。該變量保存著系統中當前正在使用的時鐘事件設備(保存了系 統當前使用的硬件時鐘中斷發生時,要執行的中斷處理函數的指針)。
2.4 硬件時鐘處理過程
由2.3.3可知硬件時鐘中斷的處理函數保存在靜態變量 irq0 中,其定義如清 單2-4
清單2-4 變量irq0定義
static struct irqaction irq0 = {
.handler = timer_event_interrupt,
.flags = IRQF_DISABLED | IRQF_IRQPOLL | IRQF_NOBALANCING,
.mask = CPU_MASK_NONE,
.name = "timer"
};
由定義可知:函數 timer_event_interrupt 為時鐘中斷處理函數,其定義如 清單2-5
清單2-5 timer_event_interrupt 函數
static irqreturn_t timer_event_interrupt(int irq, void *dev_id)
{
add_pda(irq0_irqs, 1);
global_clock_event->event_handler(global_clock_event);
return IRQ_HANDLED;
}
從代碼中可以看出:函數 timer_event_interrupt 實際上調用的是 global_clock_event 變量的 event_handler 成員。那 event_handler 成員指 向哪裡呢?
為了說明這個問題,不妨假設系統中使用的是 hpet 時鐘。由2.3.3節可知 global_clock_event 指向 hpet 時鐘事件設備( hpet_clockevent )。查看 hpet_enable 函數的代碼並沒有發現有對 event_handler 成員的賦值。所以繼 續查看時鐘事件設備加入事件的處理函數 tick_notify ,該函數記錄了當時鐘 事件設備發生變化(例如,新時鐘事件設備的加入)時,執行那些操作(參見 2.3.1節),代碼如清單2-6
清單2-6 tick_notify 函數
static int tick_notify(struct notifier_block *nb, unsigned long reason, void *dev)
{
switch (reason) {
case CLOCK_EVT_NOTIFY_ADD:
return tick_check_new_device(dev);
……
return NOTIFY_OK;
}
由代碼可知:對於新加入時鐘事件設備這個事件,將會調用函數 tick_check_new_device 。順著該函數的調用序列向下查找。 tick_set_periodic_handler 函數將時鐘事件設備的 event_handler 成員賦值 為 tick_handle_periodic 函數的地址。由此可知,函數 tick_handle_periodic 為硬件時鐘中斷發生時,真正的運行函數。
函數 tick_handle_periodic 的處理過程分成了以下兩個部分:
全局處理:整個系統中的信息處理
局部處理:局部於本地 CPU 的處理
總結一下,一次時鐘中斷發生後, OS 主要執行的操作( tick_handle_periodic ):
全局處理(僅在一個 CPU 上運行):
更新 jiffies_64
更新 xtimer 和當前時鐘源信息等
根據 tick 計算 avenrun 負載
局部處理(每個 CPU 都要運行):
根據當前在用戶態還是核心態,統計當前進程的時間:用戶態時間還是核心 態時間
喚醒 TIMER_SOFTIRQ 軟中斷
喚醒 RCU 軟中斷
調用 scheduler_tick (更新進程時間片等等操作,更多內容參見參考文獻 )
profile_tick 函數調用
以上就介紹完了硬件時鐘的處理過程,下面來看軟件時鐘。
3 軟件時鐘處理
這裡所說“軟件時鐘”指的是軟件定時器( Software Timers ) ,是一個軟件上的概念,是建立在硬件時鐘基礎之上的。它記錄了未來某一時刻 要執行的操作(函數),並使得當這一時刻真正到來時,這些操作(函數)能夠 被按時執行。舉個例子說明:它就像生活中的鬧鈴,給鬧鈴設定振鈴時間(未來 的某一時間)後,當時間(相當於硬件時鐘)更新到這個振鈴時間後,鬧鈴就會 振鈴。這個振鈴時間好比軟件時鐘的到期時間,振鈴這個動作好比軟件時鐘到期 後要執行的函數,而鬧鈴時間更新好比硬件時鐘的更新。
實現軟件時鐘原理也比較簡單:每一次硬件時鐘中斷到達時,內核更新的 jiffies ,然後將其和軟件時鐘的到期時間進行比較。如果 jiffies 等於或者 大於軟件時鐘的到期時間,內核就執行軟件時鐘指定的函數。
接下來的幾節會詳細介紹 Linux2.6.25 是怎麼實現軟件時鐘的。
3.1 相關數據結構
struct timer_list :軟件時鐘,記錄了軟件時鐘的到期時間以及到期後要 執行的操作。具體的成員以及含義見表3-1。
struct tvec_base :用於組織、管理軟件時鐘的結構。在 SMP 系統中,每 個 CPU 有一個。具體的成員以及含義參見表3-2。
表3-1 struct timer_list 主要成員
域名 類型 描述 entry struct list_head 所在的鏈表 expires unsigned long 到期時間,以 tick 為單位 function void (*)(unsigned long) 回調函數,到期後執行的操作 data unsigned long 回調函數的參數 base struct tvec_base * 記錄該軟件時鐘所在的 struct tvec_base 變量
表3-2 struct tvec_base 類型的成員
域名 類型 描述 lock spinlock_t 用於同步操作 running_timer struct timer_list * 正在處理的軟件時鐘 timer_jiffies unsigned long 當前正在處理的軟件時鐘到期時間 tv1 struct tvec_root 保存了到期時間從 timer_jiffies 到 timer_jiffies + 之間 (包括邊緣值)的所有軟件時鐘 tv2 struct tvec 保存了到期時間從 timer_jiffies + 到 timer_jiffies +之間 (包括邊緣值)的 所有軟件時鐘 tv3 struct tvec 保存了到期時間從 timer_jiffies +到 timer_jiffies +之間 (包括邊緣值)的所有軟件時鐘 tv4 struct tvec 保存了到期時間從 timer_jiffies +到 timer_jiffies +之間 (包括邊緣值)的所有軟件時鐘 tv5 struct tvec 保存了到期時間從 timer_jiffies +到 timer_jiffies +之間 (包括邊緣值)的所有軟件時鐘其中 tv1 的類型為 struct tvec_root ,tv 2~ tv 5的類型為 struct tvec ,清單3-1顯示它們的定義
清單3-1 struct tvec_root 和 struct tvec 的定義
struct tvec {
struct list_head vec[TVN_SIZE];
};
struct tvec_root {
struct list_head vec[TVR_SIZE];
};
可見它們實際上就是類型為 struct list_head 的數組,其中 TVN_SIZE 和 TVR_SIZE 在系統沒有配置宏 CONFIG_BASE_SMALL 時分別被定義為64和256。
3.2 數據結構之間的關系
圖3-1顯示了以上數據結構之間的關系:
從圖中可以清楚地看出:軟件時鐘( struct timer_list ,在圖中由 timer 表示)以雙向鏈表( struct list_head )的形式,按照它們的到期時間保存相 應的桶( tv1~tv5 )中。tv1 中保存了相對於 timer_jiffies 下256個 tick 時間內到期的所有軟件時鐘; tv2 中保存了相對於 timer_jiffies 下256*64個 tick 時間內到期的所有軟件時鐘; tv3 中保存了相對於 timer_jiffies 下 256*64*64個 tick 時間內到期的所有軟件時鐘; tv4 中保存了相對於 timer_jiffies 下256*64*64*64個 tick 時間內到期的所有軟件時鐘; tv5 中 保存了相對於 timer_jiffies 下256*64*64*64*64個 tick 時間內到期的所有軟 件時鐘。具體的說,從靜態的角度看,假設 timer_jiffies 為0,那麼 tv1[0] 保存著當前到期(到期時間等於 timer_jiffies )的軟件時鐘(需要馬上被處 理), tv1[1] 保存著下一個 tick 到達時,到期的所有軟件時鐘, tv1[n] ( 0<= n <=255)保存著下 n 個 tick 到達時,到期的所有軟件時鐘。而 tv2[0] 則保存著下256到511個 tick 之間到期所有軟件時鐘, tv2[1] 保存著 下512到767個 tick 之間到期的所有軟件時鐘, tv2[n] (0<= n <=63) 保存著下256*(n+1)到256*(n+2)-1個 tick 之間到達的所有軟件時鐘。 tv3~tv5 依次類推。
從上面的說明中可以看出:軟件時鐘是按照其到期時間相對於當前正在處理 的軟件時鐘的到期時間( timer_jiffies 的數值)保存在 struct tvec_base 變量中的。而且這個到期時間的最大相對值(到期時間 - timer_jiffies )為 0xffffffffUL ( tv5 最後一個元素能夠表示的相對到期時間的最大值)。
還需要注意的是軟件時鐘的處理是局部於 CPU 的,所以在 SMP 系統中每一 個 CPU 都保存一個類型為 struct tvec_base 的變量,用來組織、管理本 CPU 的軟件時鐘。從圖中也可以看出 struct tvec_base 變量是 per-CPU 的(關於 per-CPU 的變量原理和使用參見參考資料)。
由於以後的講解經常要提到每個 CPU 相關的 struct tvec_base 變量,所以 為了方便,稱保存軟件時鐘的 struct tvec_base 變量為該軟件時鐘的 base , 或稱 CPU 的 base 。
3.3 添加或刪除軟件時鐘
在了解了軟件時鐘的數據組織關系之後,現在來看一下如何添加以及刪除一 個軟件時鐘。
3.3.1 添加軟件時鐘
在 Linux 內核中要添加一個軟件時鐘,首先必須分配 struct timer_list 類型的變量,然後調用函數 add_timer() 將該軟件時鐘添加到相應調用 add_timer 函數的 CPU 的 base 中。 Add_timer 是對函數 __mod_timer() 的 一層包裝。函數 __mod_timer() 的代碼如清單3-2:
清單3-2 __mod_timer 函數
int __mod_timer(struct timer_list *timer, unsigned long expires)
{
struct tvec_base *base, *new_base;
unsigned long flags;
int ret = 0;
……
base = lock_timer_base(timer, &flags);
if (timer_pending(timer)) {
detach_timer(timer, 0);
ret = 1;
}
new_base = __get_cpu_var(tvec_bases);
if (base != new_base) {
if (likely(base->running_timer != timer)) {
/* See the comment in lock_timer_base() */
timer_set_base(timer, NULL);
spin_unlock(&base->lock);
base = new_base;
spin_lock(&base->lock);
timer_set_base(timer, base);
}
}
timer->expires = expires;
internal_add_timer(base, timer);
spin_unlock_irqrestore(&base->lock, flags);
return ret;
}
代碼解釋:
取得軟件時鐘所在 base 上的同步鎖( struct tvec_base 變量中的自旋鎖 ),並返回該軟件時鐘的 base ,保存在 base 變量中
如果該軟件時鐘處在 pending 狀態(在 base 中,准備執行),則卸載該軟 件時鐘
取得本 CPU 上的 base 指針(類型為 struct tvec_base* ),保存在 new_base 中
如果 base 和 new_base 不一樣,也就是說軟件時鐘發生了遷移(從一個 CPU 中移到了另一個 CPU 上),那麼如果該軟件時鐘的處理函數當前沒有在遷 移之前的那個 CPU 上運行,則先將軟件時鐘的 base 設置為 NULL ,然後再將 該軟件時鐘的 base 設置為 new_base 。否則,跳到5。
設置軟件時鐘的到期時間
調用 internal_add_timer 函數將軟件時鐘添加到軟件時鐘的 base 中(本 CPU 的 base )
釋放鎖
這裡有必要詳細說明一下軟件時鐘如何被添加到軟件時鐘的 base 中的(添 加到本 CPU base 的 tv1~tv5 裡面),因為這是軟件時鐘處理的基礎。來看函 數 internal_add_timer 函數的實現,如清單3-3
清單3-3 internal_add_timer 函數
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 < 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) {
vec = base->tv1.vec + (base->timer_jiffies & TVR_MASK);
} else {
int i;
if (idx > 0xffffffffUL) {
idx = 0xffffffffUL;
expires = idx + base->timer_jiffies;
}
i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;
vec = base->tv5.vec + i;
}
list_add_tail(&timer->entry, vec);
}
代碼解釋:
計算該軟件時鐘的到期時間和 timer_jiffies (當前正在處理的軟件時鐘的 到期時間)的差值,作為索引保存到 idx 變量中。
判斷 idx 所在的區間,在
[0, ]或 者( , 0) (該軟件時鐘已經到期),則將要添加到 tv1 中
[, ],則將要添加到 tv2 中
[, ],則將要添加到 tv3 中
[, ],則將要添加到 tv4 中
[, ),則將要添加到 tv5 中,但實際上最大值為 0xffffffffUL
計算所要加入的具體位置(哪個鏈表中,即 tv1~tv5 的哪個子鏈表,參考圖 3-1)
最後將其添加到相應的鏈表中
從這個函數可以得知,內核中是按照軟件時鐘到期時間的相對值(相對於 timer_jiffies 的值)將軟件時鐘添加到軟件時鐘所在的 base 中的。
3.3.2 刪除軟件時鐘
內核可調用 del_timer 函數刪除軟件時鐘, del_timer 的代碼如清單3- 4
清單3-4 del_timer 函數
int del_timer(struct timer_list *timer)
{
struct tvec_base *base;
unsigned long flags;
int ret = 0;
……
if (timer_pending(timer)) {
base = lock_timer_base(timer, &flags);
if (timer_pending(timer)) {
detach_timer(timer, 1);
ret = 1;
}
spin_unlock_irqrestore(&base->lock, flags);
}
return ret;
}
代碼解釋:
檢測該軟件時鐘是否處在 pending 狀態(在 base 中,准備運行),如果不 是則直接函數返回
如果處於 pending 狀態,則獲得鎖
再次檢測軟件時鐘是否處於 pending 狀態(該軟件時鐘可能被卸載了),不 是則釋放鎖然後函數返回
如果還是 pending 狀態,則將其卸載,之後釋放鎖,函數返回
如果在 SMP 系統中,則需使用 del_timer_sync 函數來刪除軟件時鐘。在講 解 del_timer_sync 函數之前,先來看下 try_to_del_timer_sync 函數的實現 (該函數被 del_timer_sync 函數使用),其代碼如清單3-5
清單3-5 try_to_del_timer_sync 函數
int try_to_del_timer_sync(struct timer_list *timer)
{
struct tvec_base *base;
unsigned long flags;
int ret = -1;
base = lock_timer_base(timer, &flags);
if (base->running_timer == timer)
goto out;
ret = 0;
if (timer_pending(timer)) {
detach_timer(timer, 1);
ret = 1;
}
out:
spin_unlock_irqrestore(&base->lock, flags);
return ret;
}
該函數檢測當前運行的軟件時鐘是不是該軟件時鐘,如果是,則函數返回-1 ,表明目前不能刪除該軟件時鐘;如果不是檢測該軟件時鐘是否處於 pending 狀態,如果不是,則函數返回0,表明軟件時鐘已經被卸載,如果處於 pending 狀態再把軟件時鐘卸載,函數返回1,表明成功卸載該軟件時鐘。
接下來,再來看看函數 del_timer_sync 定義,如清單3-6
清單3-6 del_timer_sync 函數
int del_timer_sync(struct timer_list *timer)
{
for (;;) {
int ret = try_to_del_timer_sync(timer);
if (ret >= 0)
return ret;
cpu_relax();
}
}
del_timer_sync 函數無限循環試圖卸載該軟件時鐘,直到該軟件時鐘能夠被 成功卸載。從其實現中可以看出:如果一個軟件時鐘的處理函數正在執行時,對 其的卸載操作將會失敗。一直等到軟件時鐘的處理函數運行結束後,卸載操作才 會成功。這樣避免了在 SMP 系統中一個 CPU 正在執行軟件時鐘的處理函數,而 另一個 CPU 則要將該軟件時鐘卸載所引發的問題。
3.3 時鐘的軟中斷處理
軟件時鐘的處理是在時鐘的軟中斷中進行的。
3.3.1 軟中斷初始化
軟中斷的一個重要的處理時機是在每個硬件中斷處理完成後(參見 irq_exit 函數),且由2.4節的內容可知:在硬件時鐘中斷處理中,會喚醒時鐘的軟中斷 ,所以每次硬件時鐘中斷處理函數執行完成後都要進行時鐘的軟中斷處理。和時 鐘相關的軟中斷是 TIMER_SOFTIRQ ,其處理函數為 run_timer_softirq ,該函 數用來處理所有的軟件時鐘。這部分初始化代碼在函數 init_timers 中進行, 如清單3-7
清單3-7 init_timers 函數
void __init init_timers(void)
{
……
open_softirq(TIMER_SOFTIRQ, run_timer_softirq, NULL);
}
3.3.2 處理過程
函數 run_timer_softirq 所作的工作就是找出所有到期的軟件時鐘,然後依 次執行其處理函數。其代碼如清單3-8
清單3-8 run_timer_softirq函數
static void run_timer_softirq(struct softirq_action *h)
{
struct tvec_base *base = __get_cpu_var(tvec_bases);
hrtimer_run_pending();
if (time_after_eq(jiffies, base->timer_jiffies))
__run_timers(base);
}
函數首先獲得到本地 CPU 的 base 。然後檢測如果 jiffies
大於等於 timer_jiffies ,說明可能已經有軟件時鐘到期了,此
時就要進行軟件時鐘的處理,調用函數 __run_timers 進行處
理。如果 jiffies 小於 timer_jiffies ,表明沒有軟件時鐘到期,
則不用對軟件時鐘進行處理。函數返回。
接下來看一下函數 __run_timers 都作了些什麼,如清單3-9
清單3-9 __run_timers函數
static inline void __run_timers(struct tvec_base *base)
{
……
spin_lock_irq(&base->lock);
while (time_after_eq(jiffies, base->timer_jiffies)) {
……
int index = base->timer_jiffies & TVR_MASK;
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;
list_replace_init(base->tv1.vec + index, &work_list);
while (!list_empty(head)) {
……
timer = list_first_entry(head, struct timer_list,entry);
fn = timer->function;
data = timer->data;
……
set_running_timer(base, timer);
detach_timer(timer, 1);
spin_unlock_irq(&base->lock);
{
int preempt_count = preempt_count();
fn(data);
……
}
spin_lock_irq(&base->lock);
}
}
set_running_timer(base, NULL);
spin_unlock_irq(&base->lock);
}
代碼解釋:
獲得 base 的同步鎖
如果 jiffies 大於等於 timer_jiffies (當前正要處理的軟件時鐘的到期 時間,說明可能有軟件時鐘到期了),就一直運行3~7,否則跳轉至8
計算得到 tv1 的索引,該索引指明當前到期的軟件時鐘所在 tv1 中的鏈表 (結構參見3.2節),代碼:
int index = base->timer_jiffies & TVR_MASK;
調用 cascade 函數對軟件時鐘進行必要的調整(稍後會介紹調整的過程)
使得 timer_jiffies 的數值增加1
取出相應的軟件時鐘鏈表
遍歷該鏈表,對每個元素進行如下操作
設置當前軟件時鐘為 base 中正在運行的軟件時鐘(即保存當前軟件時鐘到 base-> running_timer 成員中)
將當前軟件時鐘從鏈表中刪除,即卸載該軟件時鐘
釋放鎖,執行軟件時鐘處理程序
再次獲得鎖
設置當前 base 中不存在正在運行的軟件時鐘
釋放鎖
3.3.3 軟件時鐘調整過程
函數 cascade 用於調整軟件時鐘(這個調整過程是指:將馬上就要到期的軟 件時鐘從其所在的鏈表中刪除,重新計算到期時間的相對值(到期時間 - timer_jiffies ),然後根據該值重新插入到 base 中)。注意到在軟件時鐘處 理過程中,每次都是從 tv1 中取出一個鏈表進行處理,而不是從 tv2~tv5 中取 ,所以對軟件時鐘就要進行必要的調整。
在講解 cascade 函數之前,再從直觀上理解下為什麼需要進行調整。所有軟 件時鐘都是按照其到期時間的相對值(相對於 timer_jiffies )被調加到 base 中的。但是 timer_jiffies 的數值都會在處理中增加1(如3.3.2節所示),也 就是說這個相對值會隨著處理發生變化,當這個相對值小於等於256時,就要將 軟件時鐘從 tv2~tv5 中轉移到 tv1 中( tv1 中保存著下256個 tick 內到期的 所有軟件時鐘)。
函數 cascade 的實現如清單3-10
清單3-10 cascade 函數
static int cascade(struct tvec_base *base, struct tvec *tv, int index)
{
struct timer_list *timer, *tmp;
struct list_head tv_list;
list_replace_init(tv->vec + index, &tv_list);
list_for_each_entry_safe(timer, tmp, &tv_list, entry) {
……
internal_add_timer(base, timer);
}
return index;
}
該函數根據索引,取出相應的 tv ( tv2~tv5 )中的鏈表,然後遍歷鏈表每 一個元素。按照其到期時間重新將軟件時鐘加入到軟件時鐘的 base 中。該函數 返回 tv 中被調整的鏈表索引值(參見圖3-1)。
清單3-9中調整軟件時鐘的代碼如下:
int index = base->timer_jiffies & TVR_MASK;
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));
這部分代碼表明:如果 index 有0再到0時( index 是對 timer_jiffies 取 模),說明時間已經過了256個 tick ,這時要把 tv2 中軟件時鐘轉移到 tv1 中。如果 index 和第一個 cascade 函數的返回值都從0再到到0時,說明時間已 經過了256*64個 tick ,這時要把 tv3 中軟件時鐘轉移到 tv1 或者 tv2 中。 之後的調整過程依次類推。
3.4 自我激活
軟件時鐘可分為兩種類型:
僅僅激活一次
激活多次或者周期性激活
多次激活的實現機制就是要在軟件時鐘處理函數中重新設置軟件時鐘的到期 時間為將來的一個時間,這個過程通過調用 mod_timer 函數來實現。該函數的 實現如清單3-11
清單3-11 mod_timer 函數
int mod_timer(struct timer_list *timer, unsigned long expires)
{
……
if (timer->expires == expires && timer_pending(timer))
return 1;
return __mod_timer(timer, expires);
}
從代碼中可以看出,該函數實際上調用 __mod_timer 函數(參見3.3.1節) 來調整軟件時鐘的到期時間。
3.5 軟件時鐘的應用
軟件時鐘的處理是在處理軟中斷時觸發的,而軟中斷的處理又會緊接著硬件 中斷處理結束而進行,並且系統會周期地產生時鐘中斷(硬件中斷),這樣,軟 件時鐘的處理至少會在系統每一次時鐘中斷處理完成後觸發(如果軟件時鐘的到 期時間大於系統當前的 jiffies ,表明時間未到期,則不會調用保存在軟件時 鐘中的函數,但此時的確提供了處理軟件時鐘的時機)。從這點上看,軟件時鐘 會有較快的相應——一旦時間到期,保存在軟件時鐘中的函數會將快 地被調用(在時鐘軟中斷中被調用,參見3.3.2節)。所以內核中凡是需要隔一 段時間間隔後作指定操作的過程都通過軟件時鐘完成。例如大部分設備驅動程序 使用軟件時鐘探測異常條件、軟盤驅動程序利用軟件時鐘關閉有一段時間沒有被 訪問軟盤的設備馬達、進程的定時睡眠( schedule_timeout 函數)和網絡超時 重傳等等。
本節主要通過介紹進程的定時睡眠( schedule_timeout 函數)和網絡超時 重傳來說明軟件時鐘的應用。
3.5.1 進程的定時睡眠
函數 schedule_timeout 的代碼如清單3-12
清單3-12 函數 schedule_timeout
signed long __sched schedule_timeout(signed long timeout)
{
struct timer_list timer;
unsigned long expire;
……
expire = timeout + jiffies;
setup_timer(&timer, process_timeout, (unsigned long) current);
__mod_timer(&timer, expire);
schedule();
del_singleshot_timer_sync(&timer);
timeout = expire - jiffies;
out:
return timeout < 0 ? 0 : timeout;
}
函數 schedule_timeout 定義了一個軟件時鐘變量 timer ,在計算到期時間 後初始化這個軟件時鐘:設置軟件時鐘當時間到期時的處理函數為 process_timeout ,參數為當前進程描述符,設置軟件時鐘的到期時間為 expire 。之後調用 schedule() 函數。此時當前進程睡眠,交出執行權,內核 調用其它進程運行。但內核在每一個時鐘中斷處理結束後都要檢測這個軟件時鐘 是否到期。如果到期,將調用 process_timeout 函數,參數為睡眠的那個進程 描述符。 process_timeout 函數的代碼如清單3-13。
清單3-13 函數 process_timeout
static void process_timeout(unsigned long __data)
{
wake_up_process((struct task_struct *)__data);
}
函數 process_timeout 直接調用 wake_up_process 將進程喚醒。當內核重 新調用該進程執行時,該進程繼續執行 schedule_timeout 函數,執行流則從 schedule 函數中返回,之後調用 del_singleshot_timer_sync 函數將軟件時鐘 卸載,然後函數 schedule_timeout 結束。函數 del_singleshot_timer_sync 是實際上就是函數 del_timer_sync (參見3.3.2節),如清單3-14
清單3-14 函數del_singleshot_timer_sync
#define del_singleshot_timer_sync(t) del_timer_sync(t)
以上就是進程定時睡眠的實現過程。接下來介紹的是軟件時鐘在網絡超時重 傳上的應用。
3.5.2 網路超時重傳
對於 TCP 協議而言,如果某次發送完數據包後,並超過一定的時間間隔還沒 有收到這次發送數據包的 ACK 時, TCP 協議規定要重新發送這個數據包。
在 Linux2.6.25 的內核中,這種數據的重新發送使用軟件時鐘來完成。這個 軟件時鐘保存在面向連接的套接字(對應內核中 inet_connection_sock 結構) 中。對這個域的初始在函數 tcp_init_xmit_timers 中,如清單3-15
清單3-15 函數 tcp_init_xmit_timers 、函數 inet_csk_init_xmit_timers 和函數 setup_timer
void tcp_init_xmit_timers(struct sock *sk)
{
inet_csk_init_xmit_timers(sk,
&tcp_write_timer, &tcp_delack_timer,
&tcp_keepalive_timer);
}
void inet_csk_init_xmit_timers(struct sock *sk,
void (*retransmit_handler)(unsigned long),
void (*delack_handler)(unsigned long),
void (*keepalive_handler)(unsigned long))
{
struct inet_connection_sock *icsk = inet_csk(sk);
setup_timer(&icsk->icsk_retransmit_timer, retransmit_handler,
(unsigned long)sk);
……
}
static inline void setup_timer(struct timer_list * timer,
void (*function)(unsigned long),
unsigned long data)
{
timer->function = function;
timer->data = data;
init_timer(timer);
}
在函數 inet_csk_init_xmit_timers 中,變量 icsk 就是前面提到的面向連 接的套接字,其成員 icsk_retransmit_timer 則為實現超時重傳的軟件時鐘。 該函數調用 setup_timer 函數將函數 tcp_write_timer (參考函數 tcp_init_xmit_timers )設置為軟件時鐘 icsk->icsk_retransmit_timer 當時間到期後的處理函數。初始化的時候並沒有設置該軟件時鐘的到期時間。
在 TCP 協議具體的一次數據包發送中,函數 tcp_write_xmit 用來將數據包 從 TCP 層發送到網絡層,如清單3-16。
清單3-16 tcp_write_xmit 函數
static int tcp_write_xmit(struct sock *sk, unsigned int mss_now, int nonagle)
{
struct tcp_sock *tp = tcp_sk(sk);
struct sk_buff *skb;
……
if (unlikely(tcp_transmit_skb(sk, skb, 1, GFP_ATOMIC)))
break;
tcp_event_new_data_sent(sk, skb);
……
return !tp->packets_out && tcp_send_head(sk);
}
注意該函數中加粗的函數,其中 tcp_transmit_skb 函數是真正將數據包由 TCP 層發送到網絡層中的函數。數據發送後,將調用函數 tcp_event_new_data_sent ,而後者又會調用函數 inet_csk_reset_xmit_timer 來設置超時軟件時鐘的到期時間。
當函數 tcp_event_new_data_sent 結束之後,處理超時的軟件時鐘已經設置 好了。內核會在每一次時鐘中斷處理完成後檢測該軟件時鐘是否到期。如果網絡 真的超時,沒有 ACK 返回,那麼當該軟件時鐘到期後內核就會執行函數 tcp_write_timer 。函數 tcp_write_timer 將進行數據包的重新發送,並重新 設置超時重傳軟件時鐘的到期時間。
4 總結
本文介紹了 Linux 內核的時鐘處理機制。首先簡單介紹了系統的硬件計時器 ,然後重點介紹了硬件時鐘的處理過程和軟件時鐘的處理過程以及軟件時鐘的應 用。