Linux 時(shí)鐘管理

Linux 中的定時(shí)器

在 Linux 內(nèi)核中主要有兩種類型的定時(shí)器。一類稱為 timeout 類型，另一類稱為 timer 類型。timeout 類型的定時(shí)器通常用于檢測各種錯誤條件，例如用于檢測網(wǎng)卡收發(fā)數(shù)據(jù)包是否會超時(shí)的定時(shí)器，IO 設(shè)備的讀寫是否會超時(shí)的定時(shí)器等等。通常情況下這些錯誤很少發(fā)生，因此，使用 timeout 類型的定時(shí)器一般在超時(shí)之前就會被移除，從而很少產(chǎn)生真正的函數(shù)調(diào)用和系統(tǒng)開銷?？偟膩碚f，使用 timeout 類型的定時(shí)器產(chǎn)生的系統(tǒng)開銷很小，它是下文提及的 timer wheel 通常使用的環(huán)境。此外，在使用 timeout 類型定時(shí)器的地方往往并不關(guān)心超時(shí)處理，因此超時(shí)精確與否，早 0.01 秒或者晚 0.01 秒并不十分重要，這在下文論述 deferrable timers 時(shí)會進(jìn)一步介紹。timer 類型的定時(shí)器與 timeout 類型的定時(shí)器正相反，使用 timer 類型的定時(shí)器往往要求在精確的時(shí)鐘條件下完成特定的事件，通常是周期性的并且依賴超時(shí)機(jī)制進(jìn)行處理。例如設(shè)備驅(qū)動通常會定時(shí)讀寫設(shè)備來進(jìn)行數(shù)據(jù)交互。如何高效的管理 timer 類型的定時(shí)器對提高系統(tǒng)的處理效率十分重要，下文在介紹 hrtimer 時(shí)會有更加詳細(xì)的論述。

內(nèi)核需要進(jìn)行時(shí)鐘管理，離不開底層的硬件支持。在早期是通過 8253 芯片提供的 PIT（Programmable Interval Timer）來提供時(shí)鐘，但是 PIT 的頻率很低，只能提供最高 1ms 的時(shí)鐘精度，由于 PIT 觸發(fā)的中斷速度太慢，會導(dǎo)致很大的時(shí)延，對于像音視頻這類對時(shí)間精度要求更高的應(yīng)用并不足夠，會極大的影響用戶體驗(yàn)。隨著硬件平臺的不斷發(fā)展變化，陸續(xù)出現(xiàn)了 TSC（Time Stamp Counter），HPET（High Precision Event Timer），ACPI PM Timer（ACPI Power Management Timer），CPU Local APIC Timer 等精度更高的時(shí)鐘。這些時(shí)鐘陸續(xù)被 Linux 的時(shí)鐘子系統(tǒng)所采納，從而不斷的提高 Linux 時(shí)鐘子系統(tǒng)的性能和靈活性。這些不同的時(shí)鐘會在下文不同的章節(jié)中分別進(jìn)行介紹。

Timer wheel

在 Linux 2.6.16 之前，內(nèi)核一直使用一種稱為 timer wheel 的機(jī)制來管理時(shí)鐘。這就是熟知的 kernel 一直采用的基于 HZ 的 timer 機(jī)制。Timer wheel 的核心數(shù)據(jù)結(jié)構(gòu)如清單 1 所示：

清單 1. Timer wheel 的核心數(shù)據(jù)結(jié)構(gòu)

#define TVN_BITS (CONFIG_BASE_SMALL ? 4 : 6) #define TVR_BITS (CONFIG_BASE_SMALL ? 6 : 8) #define TVN_SIZE (1  TVN_BITS) #define TVR_SIZE (1  TVR_BITS) #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]; }; 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; 

以 CONFIG_BASE_SMALL 定義為 0 為例，TVR_SIZE ＝ 256，TVN_SIZE ＝ 64，這樣

可以得到如圖 1 所示的 timer wheel 的結(jié)構(gòu)。

圖 1. Timer wheel 的邏輯結(jié)構(gòu)

清單 2. timer wheel 的核心處理函數(shù)

static inline void __run_timers(struct tvec_base *base) { struct timer_list *timer; spin_lock_irq(base->lock); while (time_after_eq(jiffies, base->timer_jiffies)) { struct list_head work_list; struct list_head *head = work_list; int index = base->timer_jiffies  TVR_MASK; /* * Cascade timers: */ 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)) { void (*fn)(unsigned long); unsigned long data; timer = list_first_entry(head, struct timer_list,entry); fn = timer->function; data = timer->data; . . . . fn(data); . . . . } 

hrtimer (High-resolution Timer)

hrtimer 首先要實(shí)現(xiàn)的功能就是要克服 timer wheel 的缺點(diǎn)：低精度以及與內(nèi)核其他模塊的高耦合性。在正式介紹 hrtimer 之前，有必要先介紹幾個常用的基本概念：

時(shí)鐘源設(shè)備（clock-source device）

系統(tǒng)中可以提供一定精度的計(jì)時(shí)設(shè)備都可以作為時(shí)鐘源設(shè)備。如 TSC，HPET，ACPI PM-Timer，PIT 等。但是不同的時(shí)鐘源提供的時(shí)鐘精度是不一樣的。像 TSC，HPET 等時(shí)鐘源既支持高精度模式（high-resolution mode）也支持低精度模式（low-resolution mode），而 PIT 只能支持低精度模式。此外，時(shí)鐘源的計(jì)時(shí)都是單調(diào)遞增的（monotonically），如果時(shí)鐘源的計(jì)時(shí)出現(xiàn)翻轉(zhuǎn)（即返回到 0 值），很容易造成計(jì)時(shí)錯誤， 內(nèi)核的一個 patch（commit id: ff69f2）就是處理這類問題的一個很好示例。時(shí)鐘源作為系統(tǒng)時(shí)鐘的提供者，在可靠并且可用的前提下精度越高越好。在 Linux 中不同的時(shí)鐘源有不同的 rating，具有更高 rating 的時(shí)鐘源會優(yōu)先被系統(tǒng)使用。如圖 2 所示：

表 1. 時(shí)鐘源中 rating 的定義

時(shí)鐘事件設(shè)備（clock-event device）

系統(tǒng)中可以觸發(fā) one-shot（單次）或者周期性中斷的設(shè)備都可以作為時(shí)鐘事件設(shè)備。如 HPET，CPU Local APIC Timer 等。HPET 比較特別，它既可以做時(shí)鐘源設(shè)備也可以做時(shí)鐘事件設(shè)備。時(shí)鐘事件設(shè)備的類型分為全局和 per-CPU 兩種類型。全局的時(shí)鐘事件設(shè)備雖然附屬于某一個特定的 CPU 上，但是完成的是系統(tǒng)相關(guān)的工作，例如完成系統(tǒng)的 tick 更新；per-CPU 的時(shí)鐘事件設(shè)備主要完成 Local CPU 上的一些功能，例如對在當(dāng)前 CPU 上運(yùn)行進(jìn)程的時(shí)間統(tǒng)計(jì)，profile，設(shè)置 Local CPU 上的下一次事件中斷等。和時(shí)鐘源設(shè)備的實(shí)現(xiàn)類似，時(shí)鐘事件設(shè)備也通過 rating 來區(qū)分優(yōu)先級關(guān)系。

tick device

Tick device 用來處理周期性的 tick event。Tick device 其實(shí)是時(shí)鐘事件設(shè)備的一個 wrapper，因此 tick device 也有 one-shot 和周期性這兩種中斷觸發(fā)模式。每注冊一個時(shí)鐘事件設(shè)備，這個設(shè)備會自動被注冊為一個 tick device。全局的 tick device 用來更新諸如 jiffies 這樣的全局信息，per-CPU 的 tick device 則用來更新每個 CPU 相關(guān)的特定信息。

broadcast

Timekeeping GTOD (Generic Time-of-Day)

Timekeeping（可以理解為時(shí)間測量或者計(jì)時(shí)）是內(nèi)核時(shí)間管理的一個核心組成部分。沒有 Timekeeping，就無法更新系統(tǒng)時(shí)間，維持系統(tǒng)“心跳”。GTOD 是一個通用的框架，用來實(shí)現(xiàn)諸如設(shè)置系統(tǒng)時(shí)間 gettimeofday 或者修改系統(tǒng)時(shí)間 settimeofday 等工作。為了實(shí)現(xiàn)以上功能，Linux 實(shí)現(xiàn)了多種與時(shí)間相關(guān)但用于不同目的的數(shù)據(jù)結(jié)構(gòu)。

struct timespec { __kernel_time_t    tv_sec;               /* seconds */ long                tv_nsec;               /* nanoseconds */ }; 

timespec 精度是納秒。它用來保存從 00:00:00 GMT, 1 January 1970 開始經(jīng)過的時(shí)間。內(nèi)核使用全局變量 xtime 來記錄這一信息，這就是通常所說的“Wall Time”或者“Real Time”。與此對應(yīng)的是“System Time”。System Time 是一個單調(diào)遞增的時(shí)間，每次系統(tǒng)啟動時(shí)從 0 開始計(jì)時(shí)。

struct timeval { __kernel_time_t          tv_sec;          /* seconds */ __kernel_suseconds_t    tv_usec;         /* microseconds */ }; 

timeval 精度是微秒。timeval 主要用來指定一段時(shí)間間隔。

union ktime { s64     tv64; #if BITS_PER_LONG != 64  !defined(CONFIG_KTIME_SCALAR) struct { # ifdef __BIG_ENDIAN s32     sec, nsec; # else s32     nsec, sec; # endif } tv; #endif }; 

ktime_t 是 hrtimer 主要使用的時(shí)間結(jié)構(gòu)。無論使用哪種體系結(jié)構(gòu)，ktime_t 始終保持 64bit 的精度，并且考慮了大小端的影響。

typedef u64 cycle_t; 

cycle_t 是從時(shí)鐘源設(shè)備中讀取的時(shí)鐘類型。

為了管理這些不同的時(shí)間結(jié)構(gòu)，Linux 實(shí)現(xiàn)了一系列輔助函數(shù)來完成相互間的轉(zhuǎn)換。

ktime_to_timespec，ktime_to_timeval，ktime_to_ns/ktime_to_us，反過來有諸如 ns_to_ktime 等類似的函數(shù)。

timeval_to_ns，timespec_to_ns，反過來有諸如 ns_to_timeval 等類似的函數(shù)。

timeval_to_jiffies，timespec_to_jiffies，msecs_to_jiffies, usecs_to_jiffies, clock_t_to_jiffies 反過來有諸如 ns_to_timeval 等類似的函數(shù)。

clocksource_cyc2ns / cyclecounter_cyc2ns

有了以上的介紹，通過圖 3 可以更加清晰的看到這幾者之間的關(guān)聯(lián)。

圖 2. 內(nèi)核時(shí)鐘子系統(tǒng)的結(jié)構(gòu)關(guān)系

時(shí)鐘源設(shè)備和時(shí)鐘事件設(shè)備的引入，將原本放在各個體系結(jié)構(gòu)中重復(fù)實(shí)現(xiàn)的冗余代碼封裝到各自的抽象層中，這樣做不但消除了原來 timer wheel 與內(nèi)核其他模塊的緊耦合性，更重要的是系統(tǒng)可以在運(yùn)行狀態(tài)動態(tài)更換時(shí)鐘源設(shè)備和時(shí)鐘事件設(shè)備而不影響系統(tǒng)正常使用，譬如當(dāng) CPU 由于睡眠要關(guān)閉當(dāng)前使用的時(shí)鐘源設(shè)備或者時(shí)鐘事件設(shè)備時(shí)系統(tǒng)可以平滑的切換到其他仍處于工作狀態(tài)的設(shè)備上。Timekeeping/GTOD 在使用時(shí)鐘源設(shè)備的基礎(chǔ)上也采用類似的封裝實(shí)現(xiàn)了體系結(jié)構(gòu)的無關(guān)性和通用性。hrtimer 則可以通過 timekeeping 提供的接口完成定時(shí)器的更新，通過時(shí)鐘事件設(shè)備提供的事件機(jī)制，完成對 timer 的管理。在圖 3 中還有一個重要的模塊就是 tick device 的抽象，尤其是 dynamic tick。Dynamic tick 的出現(xiàn)是為了能在系統(tǒng)空閑時(shí)通過停止 tick 的運(yùn)行以達(dá)到降低 CPU 功耗的目的。使用 dynamic tick 的系統(tǒng)，只有在有實(shí)際工作時(shí)才會產(chǎn)生 tick，否則 tick 是處于停止?fàn)顟B(tài)。下文會有專門的章節(jié)進(jìn)行論述。

hrtimer 的實(shí)現(xiàn)機(jī)制

hrtimer 是建立在 per-CPU 時(shí)鐘事件設(shè)備上的，對于一個 SMP 系統(tǒng)，如果只有全局的時(shí)鐘事件設(shè)備，hrtimer 無法工作。因?yàn)槿绻麤]有 per-CPU 時(shí)鐘事件設(shè)備，時(shí)鐘中斷發(fā)生時(shí)系統(tǒng)必須產(chǎn)生必要的 IPI 中斷來通知其他 CPU 完成相應(yīng)的工作，而過多的 IPI 中斷會帶來很大的系統(tǒng)開銷，這樣會令使用 hrtimer 的代價(jià)太大，不如不用。為了支持 hrtimer，內(nèi)核需要配置 CONFIG_HIGH_RES_TIMERS=y。hrtimer 有兩種工作模式：低精度模式（low-resolution mode）與高精度模式（high-resolution mode）。雖然 hrtimer 子系統(tǒng)是為高精度的 timer 準(zhǔn)備的，但是系統(tǒng)可能在運(yùn)行過程中動態(tài)切換到不同精度的時(shí)鐘源設(shè)備，因此，hrtimer 必須能夠在低精度模式與高精度模式下自由切換。由于低精度模式是建立在高精度模式之上的，因此即便系統(tǒng)只支持低精度模式，部分支持高精度模式的代碼仍然會編譯到內(nèi)核當(dāng)中。

在低精度模式下，hrtimer 的核心處理函數(shù)是 hrtimer_run_queues，每一次 tick 中斷都要執(zhí)行一次。如清單 3 所示。這個函數(shù)的調(diào)用流程為：

update_process_times run_local_timers hrtimer_run_queuesraise_softirq(TIMER_SOFTIRQ) 

void hrtimer_run_queues(void) { struct rb_node *node; struct hrtimer_cpu_base *cpu_base = __get_cpu_var(hrtimer_bases); struct hrtimer_clock_base *base; int index, gettime = 1; if (hrtimer_hres_active()) return; for (index = 0; index  HRTIMER_MAX_CLOCK_BASES; index++) { base = cpu_base->clock_base[index]; if (!base->first) continue; if (gettime) { hrtimer_get_softirq_time(cpu_base); gettime = 0; } raw_spin_lock(cpu_base->lock); while ((node = base->first)) { struct hrtimer *timer; timer = rb_entry(node, struct hrtimer, node); if (base->softirq_time.tv64 = hrtimer_get_expires_tv64(timer)) break; __run_hrtimer(timer, base->softirq_time); } raw_spin_unlock(cpu_base->lock); } } 

hrtimer_bases 是實(shí)現(xiàn) hrtimer 的核心數(shù)據(jù)結(jié)構(gòu)，通過 hrtimer_bases，hrtimer 可以管理掛在每一個 CPU 上的所有 timer。每個 CPU 上的 timer list 不再使用 timer wheel 中多級鏈表的實(shí)現(xiàn)方式，而是采用了紅黑樹（Red-Black Tree）來進(jìn)行管理。hrtimer_bases 的定義如清單 4 所示：

清單 4. hrtimer_bases 的定義

DEFINE_PER_CPU(struct hrtimer_cpu_base, hrtimer_bases) = { .clock_base = { { .index = CLOCK_REALTIME, .get_time = ktime_get_real, .resolution = KTIME_LOW_RES, }, { .index = CLOCK_MONOTONIC, .get_time = ktime_get, .resolution = KTIME_LOW_RES, }, } }; 

圖 4 展示了 hrtimer 如何通過 hrtimer_bases 來管理 timer。

圖 3. hrtimer 的時(shí)鐘管理

每個 hrtimer_bases 都包含兩個 clock_base，一個是 CLOCK_REALTIME 類型的，另一個是 CLOCK_MONOTONIC 類型的。hrtimer 可以選擇其中之一來設(shè)置 timer 的 expire time, 可以是實(shí)際的時(shí)間 , 也可以是相對系統(tǒng)運(yùn)行的時(shí)間。

在 hrtimer_run_queues 的處理中，首先要通過 hrtimer_bases 找到正在執(zhí)行當(dāng)前中斷的 CPU 相關(guān)聯(lián)的 clock_base，然后逐個檢查每個 clock_base 上掛的 timer 是否超時(shí)。由于 timer 在添加到 clock_base 上時(shí)使用了紅黑樹，最早超時(shí)的 timer 被放到樹的最左側(cè)，因此尋找超時(shí) timer 的過程非常迅速，找到的所有超時(shí) timer 會被逐一處理。超時(shí)的 timer 根據(jù)其類型分為 softIRQ / per-CPU / unlocked 幾種。如果一個 timer 是 softIRQ 類型的，這個超時(shí)的 timer 需要被轉(zhuǎn)移到 hrtimer_bases 的 cb_pending 的 list 上，待 IRQ0 的軟中斷被激活后，通過 run_hrtimer_pending 執(zhí)行，另外兩類則必須在 hardIRQ 中通過 __run_hrtimer 直接執(zhí)行。不過在較新的 kernel（> 2.6.29）中，cb_pending 被取消，這樣所有的超時(shí) timers 都必須在 hardIRQ 的 context 中執(zhí)行。這樣修改的目的，一是為了簡化代碼邏輯，二是為了減少 2 次 context 的切換：一次從 hardIRQ 到 softIRQ，另一次從 softIRQ 到被超時(shí) timer 喚醒的進(jìn)程。

在 update_process_times 中，除了處理處于低精度模式的 hrtimer 外，還要喚醒 IRQ0 的 softIRQ（TIMER_SOFTIRQ（run_timer_softirq））以便執(zhí)行 timer wheel 的代碼。由于 hrtimer 子系統(tǒng)的加入，在 IRQ0 的 softIRQ 中，還需要通過 hrtimer_run_pending 檢查是否可以將 hrtimer 切換到高精度模式，如清單 5 所示：

清單 5. hrtimer 進(jìn)行精度切換的處理函數(shù)

void hrtimer_run_pending(void) { if (hrtimer_hres_active()) return; /* * This _is_ ugly: We have to check in the softirq context, * whether we can switch to highres and / or nohz mode. The * clocksource switch happens in the timer interrupt with * xtime_lock held. Notification from there only sets the * check bit in the tick_oneshot code, otherwise we might * deadlock vs. xtime_lock. */ if (tick_check_oneshot_change(!hrtimer_is_hres_enabled())) hrtimer_switch_to_hres(); } 

正如這段代碼的作者注釋中所提到的，每一次觸發(fā) IRQ0 的 softIRQ 都需要檢查一次是否可以將 hrtimer 切換到高精度，顯然是十分低效的，希望將來有更好的方法不用每次都進(jìn)行檢查。

如果可以將 hrtimer 切換到高精度模式，則調(diào)用 hrtimer_switch_to_hres 函數(shù)進(jìn)行切換。如清單 6 所示：

清單 6. hrtimer 切換到高精度模式的核心函數(shù)

/* * Switch to high resolution mode */ static int hrtimer_switch_to_hres(void) { int cpu = smp_processor_id(); struct hrtimer_cpu_base *base = per_cpu(hrtimer_bases, cpu); unsigned long flags; if (base->hres_active) return 1; local_irq_save(flags); if (tick_init_highres()) { local_irq_restore(flags); printk(KERN_WARNING Could not switch to high resolution mode on CPU %dn, cpu); return 0; } base->hres_active = 1; base->clock_base[CLOCK_REALTIME].resolution = KTIME_HIGH_RES; base->clock_base[CLOCK_MONOTONIC].resolution = KTIME_HIGH_RES; tick_setup_sched_timer(); /* Retrigger the interrupt to get things going */ retrigger_next_event(NULL); local_irq_restore(flags); return 1; } 

在這個函數(shù)中，首先使用 tick_init_highres 更新與原來的 tick device 綁定的時(shí)鐘事件設(shè)備的 event handler，例如將在低精度模式下的工作函數(shù) tick_handle_periodic / tick_handle_periodic_broadcast 換成 hrtimer_interrupt（它是 hrtimer 在高精度模式下的 timer 中斷處理函數(shù)），同時(shí)將 tick device 的觸發(fā)模式變?yōu)?one-shot，即單次觸發(fā)模式，這是使用 dynamic tick 或者 hrtimer 時(shí) tick device 的工作模式。由于 dynamic tick 可以隨時(shí)停止和開始，以不規(guī)律的速度產(chǎn)生 tick，因此支持 one-shot 模式的時(shí)鐘事件設(shè)備是必須的；對于 hrtimer，由于 hrtimer 采用事件機(jī)制驅(qū)動 timer 前進(jìn)，因此使用 one-shot 的觸發(fā)模式也是順理成章的。不過這樣一來，原本 tick device 每次執(zhí)行中斷時(shí)需要完成的周期性任務(wù)如更新 jiffies / wall time (do_timer) 以及更新 process 的使用時(shí)間（update_process_times）等工作在切換到高精度模式之后就沒有了，因此在執(zhí)行完 tick_init_highres 之后緊接著會調(diào)用 tick_setup_sched_timer 函數(shù)來完成這部分設(shè)置工作，如清單 7 所示：

清單 7. hrtimer 高精度模式下模擬周期運(yùn)行的 tick device 的簡化實(shí)現(xiàn)

void tick_setup_sched_timer(void) { struct tick_sched *ts = __get_cpu_var(tick_cpu_sched); ktime_t now = ktime_get(); u64 offset; /* * Emulate tick processing via per-CPU hrtimers: */ hrtimer_init(ts->sched_timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS); ts->sched_timer.function = tick_sched_timer; . . . . for (;;) { hrtimer_forward(ts->sched_timer, now, tick_period); hrtimer_start_expires(ts->sched_timer, HRTIMER_MODE_ABS_PINNED); /* Check, if the timer was already in the past */ if (hrtimer_active(ts->sched_timer)) break; now = ktime_get(); } . . . . } 

這個函數(shù)使用 tick_cpu_sched 這個 per-CPU 變量來模擬原來 tick device 的功能。tick_cpu_sched 本身綁定了一個 hrtimer，這個 hrtimer 的超時(shí)值為下一個 tick，回調(diào)函數(shù)為 tick_sched_timer。因此，每過一個 tick，tick_sched_timer 就會被調(diào)用一次，在這個回調(diào)函數(shù)中首先完成原來 tick device 的工作，然后設(shè)置下一次的超時(shí)值為再下一個 tick，從而達(dá)到了模擬周期運(yùn)行的 tick device 的功能。如果所有的 CPU 在同一時(shí)間點(diǎn)被喚醒，并發(fā)執(zhí)行 tick 時(shí)可能會出現(xiàn) lock 競爭以及 cache-line 沖突，為此 Linux 內(nèi)核做了特別處理：如果假設(shè) CPU 的個數(shù)為 N，則所有的 CPU 都在 tick_period 前 1/2 的時(shí)間內(nèi)執(zhí)行 tick 工作，并且每個 CPU 的執(zhí)行間隔是 tick_period / (2N)，見清單 8 所示：

清單 8. hrtimer 在高精度模式下 tick 執(zhí)行周期的設(shè)置

void tick_setup_sched_timer(void) { . . . . /* Get the next period (per cpu) */ hrtimer_set_expires(ts->sched_timer, tick_init_jiffy_update()); offset = ktime_to_ns(tick_period) >> 1; do_div(offset, num_possible_cpus()); offset *= smp_processor_id(); hrtimer_add_expires_ns(ts->sched_timer, offset); . . . . } 

回到 hrtimer_switch_to_hres 函數(shù)中，在一切準(zhǔn)備就緒后，調(diào)用 retrigger_next_event 激活下一次的 timer 就可以開始正常的運(yùn)作了。

隨著 hrtimer 子系統(tǒng)的發(fā)展，一些問題也逐漸暴露了出來。一個比較典型的問題就是 CPU 的功耗問題。現(xiàn)代 CPU 都實(shí)現(xiàn)了節(jié)能的特性，在沒有工作時(shí) CPU 會主動降低頻率，關(guān)閉 CPU 內(nèi)部一些非關(guān)鍵模塊以達(dá)到節(jié)能的目的。由于 hrtimer 的精度很高，觸發(fā)中斷的頻率也會很高，頻繁的中斷會極大的影響 CPU 的節(jié)能。在這方面 hrtimer 一直在不斷的進(jìn)行調(diào)整。以下幾個例子都是針對這一問題所做的改進(jìn)。

schedule_hrtimeout 函數(shù)

/** * schedule_hrtimeout - sleep until timeout * @expires:    timeout value (ktime_t) * @mode:       timer mode, HRTIMER_MODE_ABS or HRTIMER_MODE_REL */ int __sched schedule_hrtimeout(ktime_t *expires, const enum hrtimer_mode mode) 

schedule_hrtimeout 用來產(chǎn)生一個高精度的調(diào)度超時(shí)，以 ns 為單位。這樣可以更加細(xì)粒度的使用內(nèi)核的調(diào)度器。在 Arjan van de Ven 的最初實(shí)現(xiàn)中，這個函數(shù)有一個很大的問題：由于其粒度很細(xì)，所以可能會更加頻繁的喚醒內(nèi)核，導(dǎo)致消耗更多的能源。為了實(shí)現(xiàn)既能節(jié)省能源，又能確保精確的調(diào)度超時(shí)，Arjan van de Ven 的辦法是將一個超時(shí)點(diǎn)變成一個超時(shí)范圍。設(shè)置 hrtimer A 的超時(shí)值有一個上限，稱為 hard expire，在 hard expire 這個時(shí)間點(diǎn)上設(shè)置 hrtimer A 的超時(shí)中斷；同時(shí)設(shè)置 hrtimer A 的超時(shí)值有一個下限，稱為 soft expire。在 soft expire 到 hard expire 之間如果有一個 hrtimer B 的中斷被觸發(fā)，在 hrtimer B 的中斷處理函數(shù)中，內(nèi)核會檢查是否有其他 hrtimer 的 soft expire 超時(shí)了，譬如 hrtimer A 的 soft expire 超時(shí)了，即使 hrtimer A 的 hard expire 沒有到，也可以順帶被處理。換言之，將原來必須在 hard expire 超時(shí)才能執(zhí)行的一個點(diǎn)變成一個范圍后，可以盡量把 hrtimer 中斷放在一起處理，這樣 CPU 被重復(fù)喚醒的幾率會變小，從而達(dá)到節(jié)能的效果，同時(shí)這個 hrtimer 也可以保證其執(zhí)行精度。

Deferrable timers round jiffies

在內(nèi)核中使用的某些 legacy timer 對于精確的超時(shí)值并不敏感，早一點(diǎn)或者晚一點(diǎn)執(zhí)行并不會產(chǎn)生多大的影響，因此，如果可以把這些對時(shí)間不敏感同時(shí)超時(shí)時(shí)間又比較接近的 timer 收集在一起執(zhí)行，可以進(jìn)一步減少 CPU 被喚醒的次數(shù)，從而達(dá)到節(jié)能的目地。這正是引入 Deferrable timers 的目地。如果一個 timer 可以被短暫延時(shí)，那么可以通過調(diào)用 init_timer_deferrable 設(shè)置 defer 標(biāo)記，從而在執(zhí)行時(shí)靈活選擇處理方式。不過，如果這些 timers 都被延時(shí)到同一個時(shí)間點(diǎn)上也不是最優(yōu)的選擇，這樣同樣會產(chǎn)生 lock 競爭以及 cache-line 的問題。因此，即便將 defer timers 收集到一起，彼此之間也必須稍稍錯開一些以防止上述問題。這正是引入 round_jiffies 函數(shù)的原因。雖然這樣做會使得 CPU 被喚醒的次數(shù)稍多一些，但是由于間隔短，CPU 并不會進(jìn)入很深的睡眠，這個代價(jià)還是可以接受的。由于 round_jiffies 需要在每次更新 timer 的超時(shí)值（mod_timer）時(shí)被調(diào)用，顯得有些繁瑣，因此又出現(xiàn)了更為便捷的 round jiffies 機(jī)制，稱為 timer slack。Timer slack 修改了 timer_list 的結(jié)構(gòu)定義，將需要偏移的 jiffies 值保存在 timer_list 內(nèi)部，通過 apply_slack 在每次更新 timer 的過程中自動更新超時(shí)值。apply_slack 的實(shí)現(xiàn)如清單 9 所示：

清單 9. apply_slack 的實(shí)現(xiàn)

/* * Decide where to put the timer while taking the slack into account * * Algorithm: *  1) calculate the maximum (absolute) time *  2) calculate the highest bit where the expires and new max are different *  3) use this bit to make a mask *  4) use the bitmask to round down the maximum time, so that all last *   bits are zeros */ static inline unsigned long apply_slack(struct timer_list *timer, unsigned long expires) { unsigned long expires_limit, mask; int bit; expires_limit = expires; if (timer->slack >= 0) { expires_limit = expires + timer->slack; } else { unsigned long now = jiffies; /* avoid reading jiffies twice */ /* if already expired, no slack; otherwise slack 0.4% */ if (time_after(expires, now)) expires_limit = expires + (expires - now)/256; } mask = expires ^ expires_limit; if (mask == 0) return expires; bit = find_last_bit(mask, BITS_PER_LONG); mask = (1  bit) - 1; expires_limit = expires_limit  ~(mask); return expires_limit; } 

隨著現(xiàn)代計(jì)算機(jī)系統(tǒng)的發(fā)展，對節(jié)能的需求越來越高，尤其是在使用筆記本，手持設(shè)備等移動環(huán)境是對節(jié)能要求更高。Linux 當(dāng)然也會更加關(guān)注這方面的需求。hrtimer 子系統(tǒng)的優(yōu)化盡量確保在使用高精度的時(shí)鐘的同時(shí)節(jié)約能源，如果系統(tǒng)在空閑時(shí)也可以盡量的節(jié)能，則 Linux 系統(tǒng)的節(jié)能優(yōu)勢可以進(jìn)一步放大。這也是引入 dynamic tick 的根本原因。

Dynamic tick tickless

在 dynamic tick 引入之前，內(nèi)核一直使用周期性的基于 HZ 的 tick。傳統(tǒng)的 tick 機(jī)制在系統(tǒng)進(jìn)入空閑狀態(tài)時(shí)仍然會產(chǎn)生周期性的中斷，這種頻繁的中斷迫使 CPU 無法進(jìn)入更深的睡眠。如果放開這個限制，在系統(tǒng)進(jìn)入空閑時(shí)停止 tick，有工作時(shí)恢復(fù) tick，實(shí)現(xiàn)完全自由的，根據(jù)需要產(chǎn)生 tick 的機(jī)制，可以使 CPU 獲得更多的睡眠機(jī)會以及更深的睡眠，從而進(jìn)一步節(jié)能。dynamic tick 的出現(xiàn)，就是為徹底替換掉周期性的 tick 機(jī)制而產(chǎn)生的。周期性運(yùn)行的 tick 機(jī)制需要完成諸如進(jìn)程時(shí)間片的計(jì)算，更新 profile，協(xié)助 CPU 進(jìn)行負(fù)載均衡等諸多工作，這些工作 dynamic tick 都提供了相應(yīng)的模擬機(jī)制來完成。由于 dynamic tick 的實(shí)現(xiàn)需要內(nèi)核的很多模塊的配合，包括了很多實(shí)現(xiàn)細(xì)節(jié)，這里只介紹 dynamic tick 的核心工作機(jī)制，以及如何啟動和停止 dynamic tick。

Dynamic tick 的核心處理流程

從上文中可知內(nèi)核時(shí)鐘子系統(tǒng)支持低精度和高精度兩種模式，因此 dynamic tick 也必須有兩套對應(yīng)的處理機(jī)制。從清單 5 中可以得知，如果系統(tǒng)支持 hrtimer 的高精度模式，hrtimer 可以在此從低精度模式切換到高精度模式。其實(shí)清單 5 還有另外一個重要功能：它也是低精度模式下從周期性 tick 到 dynamic tick 的切換點(diǎn)。如果當(dāng)前系統(tǒng)不支持高精度模式，系統(tǒng)會嘗試切換到 NOHZ 模式，也就是使用 dynamic tick 的模式，當(dāng)然前提是內(nèi)核使能了 NOHZ 模式。其核心處理函數(shù)如清單 10 所示。這個函數(shù)的調(diào)用流程如下：

tick_check_oneshot_change tick_nohz_switch_to_nohz tick_switch_to_oneshot(tick_nohz_handler) 

static void tick_nohz_handler(struct clock_event_device *dev) { struct tick_sched *ts = __get_cpu_var(tick_cpu_sched); struct pt_regs *regs = get_irq_regs(); int cpu = smp_processor_id(); ktime_t now = ktime_get(); dev->next_event.tv64 = KTIME_MAX; if (unlikely(tick_do_timer_cpu == TICK_DO_TIMER_NONE)) tick_do_timer_cpu = cpu; /* Check, if the jiffies need an update */ if (tick_do_timer_cpu == cpu) tick_do_update_jiffies64(now); /* * When we are idle and the tick is stopped, we have to touch * the watchdog as we might not schedule for a really long * time. This happens on complete idle SMP systems while * waiting on the login prompt. We also increment the start * of idle jiffy stamp so the idle accounting adjustment we * do when we go busy again does not account too much ticks. */ if (ts->tick_stopped) { touch_softlockup_watchdog(); ts->idle_jiffies++; } update_process_times(user_mode(regs)); profile_tick(CPU_PROFILING); while (tick_nohz_reprogram(ts, now)) { now = ktime_get(); tick_do_update_jiffies64(now); } } 

在這個函數(shù)中，首先模擬周期性 tick device 完成類似的工作：如果當(dāng)前 CPU 負(fù)責(zé)全局 tick device 的工作，則更新 jiffies，同時(shí)完成對本地 CPU 的進(jìn)程時(shí)間統(tǒng)計(jì)等工作。如果當(dāng)前 tick device 在此之前已經(jīng)處于停止?fàn)顟B(tài)，為了防止 tick 停止時(shí)間過長造成 watchdog 超時(shí)，從而引發(fā) soft-lockdep 的錯誤，需要通過調(diào)用 touch_softlockup_watchdog 復(fù)位軟件看門狗防止其溢出。正如代碼中注釋所描述的，這種情況有可能出現(xiàn)在啟動完畢，完全空閑等待登錄的 SMP 系統(tǒng)上。最后需要設(shè)置下一次 tick 的超時(shí)時(shí)間。如果 tick_nohz_reprogram 執(zhí)行時(shí)間超過了一個 jiffy，會導(dǎo)致設(shè)置的下一次超時(shí)時(shí)間已經(jīng)過期，因此需要重新設(shè)置，相應(yīng)的也需要再次更新 jiffies。這里雖然設(shè)置了下一次的超時(shí)事件，但是由于系統(tǒng)空閑時(shí)會停止 tick，因此下一次的超時(shí)事件可能發(fā)生，也可能不發(fā)生。這也正是 dynamic tick 根本特性。

從清單 7 中可以看到，在高精度模式下 tick_sched_timer 用來模擬周期性 tick device 的功能。dynamic tick 的實(shí)現(xiàn)也使用了這個函數(shù)。這是因?yàn)?hrtimer 在高精度模式時(shí)必須使用 one-shot 模式的 tick device，這也同時(shí)符合 dynamic tick 的要求。雖然使用同樣的函數(shù)，表面上都會觸發(fā)周期性的 tick 中斷，但是使用 dynamic tick 的系統(tǒng)在空閑時(shí)會停止 tick 工作，因此 tick 中斷不會是周期產(chǎn)生的。

Dynamic tick 的開始和停止

當(dāng) CPU 進(jìn)入空閑時(shí)是最好的時(shí)機(jī)。此時(shí)可以啟動 dynamic tick 機(jī)制，停止 tick；反之在 CPU 從空閑中恢復(fù)到工作狀態(tài)時(shí)，則可以停止 dynamic tick。見清單 11 所示：

清單 11. CPU 在 idle 時(shí) dynamic tick 的啟動 / 停止設(shè)置

void cpu_idle(void) { . . . . while (1) { tick_nohz_stop_sched_tick(1); while (!need_resched()) { . . . . } tick_nohz_restart_sched_tick(); } . . . . } 

timer 子系統(tǒng)的初始化過程

在分別了解了內(nèi)核時(shí)鐘子系統(tǒng)各個模塊后，現(xiàn)在可以系統(tǒng)的介紹內(nèi)核時(shí)鐘子系統(tǒng)的初始化過程。系統(tǒng)剛上電時(shí)，需要注冊 IRQ0 時(shí)鐘中斷，完成時(shí)鐘源設(shè)備，時(shí)鐘事件設(shè)備，tick device 等初始化操作并選擇合適的工作模式。由于剛啟動時(shí)沒有特別重要的任務(wù)要做，因此默認(rèn)是進(jìn)入低精度 + 周期 tick 的工作模式，之后會根據(jù)硬件的配置（如硬件上是否支持 HPET 等高精度 timer）和軟件的配置（如是否通過命令行參數(shù)或者內(nèi)核配置使能了高精度 timer 等特性）進(jìn)行切換。在一個支持 hrtimer 高精度模式并使能了 dynamic tick 的系統(tǒng)中，第一次發(fā)生 IRQ0 的軟中斷時(shí) hrtimer 就會進(jìn)行從低精度到高精度的切換，然后再進(jìn)一步切換到 NOHZ 模式。IRQ0 為系統(tǒng)的時(shí)鐘中斷，使用全局的時(shí)鐘事件設(shè)備（global_clock_event）來處理的，其定義如下：

static struct irqaction irq0  = { .handler = timer_interrupt, .flags = IRQF_DISABLED | IRQF_NOBALANCING | IRQF_IRQPOLL | IRQF_TIMER, .name = timer}; 

它的中斷處理函數(shù) timer_interrupt 的簡化實(shí)現(xiàn)如清單 12 所示：

清單 12. IRQ0 中斷處理函數(shù)的簡化實(shí)現(xiàn)

static irqreturn_t timer_interrupt(int irq, void *dev_id) { . . . . global_clock_event->event_handler(global_clock_event);. . . . return IRQ_HANDLED; } 

在 global_clock_event->event_handler 的處理中，除了更新 local CPU 上運(yùn)行進(jìn)程時(shí)間的統(tǒng)計(jì)，profile 等工作，更重要的是要完成更新 jiffies 等全局操作。這個全局的時(shí)鐘事件設(shè)備的 event_handler 根據(jù)使用環(huán)境的不同，在低精度模式下可能是 tick_handle_periodic / tick_handle_periodic_broadcast，在高精度模式下是 hrtimer_interrupt。目前只有 HPET 或者 PIT 可以作為 global_clock_event 使用。其初始化流程清單 13 所示：

清單 13. timer 子系統(tǒng)的初始化流程

void __init time_init(void) { late_time_init = x86_late_time_init; } static __init void x86_late_time_init(void) { x86_init.timers.timer_init(); tsc_init(); } /* x86_init.timers.timer_init 是指向 hpet_time_init 的回調(diào)指針 */ void __init hpet_time_init(void) { if (!hpet_enable()) setup_pit_timer(); setup_default_timer_irq(); } 

由清單 13 可以看到，系統(tǒng)優(yōu)先使用 HPET 作為 global_clock_event，只有在 HPET 沒有使能時(shí)，PIT 才有機(jī)會成為 global_clock_event。在使能 HPET 的過程中，HPET 會同時(shí)被注冊為時(shí)鐘源設(shè)備和時(shí)鐘事件設(shè)備。

hpet_enable hpet_clocksource_register hpet_legacy_clockevent_register clockevents_register_device(hpet_clockevent); 

clockevent_register_device 會觸發(fā) CLOCK_EVT_NOTIFY_ADD 事件，即創(chuàng)建對應(yīng)的 tick device。然后在 tick_notify 這個事件處理函數(shù)中會添加新的 tick device。

clockevent_register_device trigger event CLOCK_EVT_NOTIFY_ADD tick_notify receives event CLOCK_EVT_NOTIFY_ADD tick_check_new_device tick_setup_device 

在 tick device 的設(shè)置過程中，會根據(jù)新加入的時(shí)鐘事件設(shè)備是否使用 broadcast 來分別設(shè)置 event_handler。對于 tick device 的處理函數(shù)，可見圖 5 所示：

表 2. tick device 在不同模式下的處理函數(shù)

另外，在系統(tǒng)運(yùn)行的過程中，可以通過查看 /proc/timer_list 來顯示系統(tǒng)當(dāng)前配置的所有時(shí)鐘的詳細(xì)情況，譬如當(dāng)前系統(tǒng)活動的時(shí)鐘源設(shè)備，時(shí)鐘事件設(shè)備，tick device 等。也可以通過查看 /proc/timer_stats 來查看當(dāng)前系統(tǒng)中所有正在使用的 timer 的統(tǒng)計(jì)信息。包括所有正在使用 timer 的進(jìn)程，啟動 / 停止 timer 的函數(shù)，timer 使用的頻率等信息。內(nèi)核需要配置 CONFIG_TIMER_STATS=y，而且在系統(tǒng)啟動時(shí)這個功能是關(guān)閉的，需要通過如下命令激活echo 1 >/proc/timer_stats。/proc/timer_stats 的顯示格式如下所示：

count>, pid> command> start_func> (expire_func>)

總結(jié)

隨著應(yīng)用環(huán)境的改變，使用需求的多樣化，Linux 的時(shí)鐘子系統(tǒng)也在不斷的衍變。為了更好的支持音視頻等對時(shí)間精度高的應(yīng)用，Linux 提出了 hrtimer 這一高精度的時(shí)鐘子系統(tǒng)，為了節(jié)約能源，Linux 改變了長久以來一直使用的基于 HZ 的 tick 機(jī)制，采用了 tickless 系統(tǒng)。即使是在對硬件平臺的支持上，也是在不斷改進(jìn)。舉例來說，由于 TSC 精度高，是首選的時(shí)鐘源設(shè)備。但是現(xiàn)代 CPU 會在系統(tǒng)空閑時(shí)降低頻率以節(jié)約能源，從而導(dǎo)致 TSC 的頻率也會跟隨發(fā)生改變。這樣會導(dǎo)致 TSC 無法作為穩(wěn)定的時(shí)鐘源設(shè)備使用。隨著新的 CPU 的出現(xiàn)，即使 CPU 的頻率發(fā)生變化，TSC 也可以一直維持在固定頻率上，從而確保其穩(wěn)定性。在 Intel 的 Westmere 之前的 CPU 中，TSC 和 Local APIC Timer 類似，都會在 C3+ 狀態(tài)時(shí)進(jìn)入睡眠，從而導(dǎo)致系統(tǒng)需要切換到其他較低精度的時(shí)鐘源設(shè)備上，但是在 Intel Westmere 之后的 CPU 中，TSC 可以一直保持運(yùn)行狀態(tài)，即使 CPU 進(jìn)入了 C3+ 的睡眠狀態(tài)，從而避免了時(shí)鐘源設(shè)備的切換。在 SMP 的環(huán)境下，尤其是 16-COREs，32-COREs 這樣的多 CPU 系統(tǒng)中，每個 CPU 之間的 TSC 很難保持同步，很容易出現(xiàn)“Out-of-Sync”。如果在這種環(huán)境下使用 TSC，會造成 CPU 之間的計(jì)時(shí)誤差，然而在 Intel 最新的 Nehalem-EX CPU 中，已經(jīng)可以確保 TSC 在多個 CPU 之間保持同步，從而可以使用 TSC 作為首選的時(shí)鐘源設(shè)備。由此可見，無論是現(xiàn)在還是將來，只要有需要，內(nèi)核的時(shí)鐘子系統(tǒng)就會一直向前發(fā)展。