Linux 2.6內(nèi)核中的計(jì)時(shí)器和列表

計(jì)時(shí)器是所有操作系統(tǒng)的一個(gè)必要組成部分，您將發(fā)現(xiàn)多個(gè)計(jì)時(shí)器機(jī)制。我們將首先簡要介紹一些 Linux 計(jì)時(shí)器模式，然后深入研究它們的運(yùn)行方式。

（Linux）時(shí)間的起源

在 Linux 內(nèi)核中，時(shí)間由一個(gè)名為?jiffies?的全局變量衡量，該變量標(biāo)識系統(tǒng)啟動以來經(jīng)過的滴答數(shù)。在最低的級別上，計(jì)算滴答數(shù)的方式取決于正在運(yùn)行的特定硬件平臺；但是，滴答計(jì)數(shù)通常在一次中斷期間仍然繼續(xù)進(jìn)行。滴答速率（jiffies?的最不重要的位）可以配置，但在最近針對 x86 的 2.6 內(nèi)核中，一次滴答等于 4ms（250Hz）。jiffies?全局變量在內(nèi)核中廣泛使用，目的有幾個(gè)，其中之一是提供用于計(jì)算一個(gè)計(jì)時(shí)器的超時(shí)值的當(dāng)前絕對時(shí)間（稍后將展示一個(gè)例子）。

回頁首

內(nèi)核計(jì)時(shí)器

最近的 2.6 內(nèi)核中有幾個(gè)不同的計(jì)時(shí)器模式，其中最簡單、最不精確（但適用于大多數(shù)實(shí)例）的模式就是計(jì)時(shí)器 API。這個(gè) API 允許構(gòu)造在?jiffies?域（最低 4ms 超時(shí)）中運(yùn)行的計(jì)時(shí)器。還有一個(gè)高精確度計(jì)時(shí)器 API，它允許構(gòu)造在以納秒定義的時(shí)間中運(yùn)行的計(jì)時(shí)器。根據(jù)您的處理器和處理器運(yùn)行的速度，您的里程（mileage）可能會不同，但這個(gè) API 的確提供了一種方法來在?jiffies?滴答間隔下調(diào)度超時(shí)。

標(biāo)準(zhǔn)計(jì)時(shí)器

標(biāo)準(zhǔn)計(jì)時(shí)器 API 作為 Linux 內(nèi)核的一部分已經(jīng)有很長一段時(shí)間了（自從 Linux 內(nèi)核的早期版本開始）。盡管它提供的精確性比高精確度計(jì)時(shí)器要低，但它對于在處理物理設(shè)備時(shí)提供錯誤覆蓋的傳統(tǒng)驅(qū)動程序超時(shí)來說比較理想。在很多情況下，這些超時(shí)實(shí)際上從不觸發(fā)，而是被啟動，然后被刪除。

簡單內(nèi)核計(jì)時(shí)器使用計(jì)時(shí)器輪（timer wheel）?實(shí)現(xiàn)。這個(gè)主意是由 Finn Arne Gangstad 在 1997 年首次引入的。它不理睬管理大量計(jì)時(shí)器的問題，而是很好地管理數(shù)量合理的計(jì)時(shí)器 — 典型情況。（原始計(jì)時(shí)器實(shí)現(xiàn)只是按照過期順序?qū)⒂?jì)時(shí)器實(shí)現(xiàn)雙重鏈接。盡管在概念上比較簡單，但這種方法是不可伸縮的。）時(shí)間輪是一個(gè) buckets 集合，其中每個(gè) bucker 表示將來計(jì)時(shí)器過期的一個(gè)時(shí)間塊。這些 buckets 使用基于 5 個(gè) bucket 的對數(shù)時(shí)間定義。使用?jiffies?作為時(shí)間粒度，定義了幾個(gè)組，它們表示將來的過期時(shí)段（其中每個(gè)組通過一列計(jì)時(shí)器表示）。計(jì)時(shí)器插入使用具有 O(1) 復(fù)雜度的列表操作發(fā)生，過期發(fā)生在 O(N) 時(shí)間內(nèi)。計(jì)時(shí)器過期以串聯(lián)的形式出現(xiàn)，其中計(jì)時(shí)器被從高粒度 buckets 刪除，然后隨著它們的過期時(shí)間的下降被插入到低粒度 buckets 中?，F(xiàn)在我們查看一下針對這個(gè)計(jì)時(shí)器實(shí)現(xiàn)的 API。

計(jì)時(shí)器 API

Linux 提供了一個(gè)簡單的 API 來構(gòu)造和管理計(jì)時(shí)器。它包含一些函數(shù)（和助手函數(shù)），用于創(chuàng)建、取消和管理計(jì)時(shí)器。

計(jì)時(shí)器通過?timer_list?結(jié)構(gòu)定義，該結(jié)構(gòu)包括實(shí)現(xiàn)一個(gè)計(jì)時(shí)器所需的所有數(shù)據(jù)（其中包括列表指針和在編譯時(shí)配置的可選計(jì)時(shí)器統(tǒng)計(jì)數(shù)據(jù)）。從用戶角度看，timer_list?包含一個(gè)過期時(shí)間，一個(gè)回調(diào)函數(shù)（當(dāng)/如果計(jì)時(shí)器過期），以及一個(gè)用戶提供的上下文。用戶必須初始化計(jì)時(shí)器，可以采取幾種方法，最簡單的方法是調(diào)用?setup_timer，該函數(shù)初始化計(jì)時(shí)器并設(shè)置用戶提供的回調(diào)函數(shù)和上下文?；蛘撸脩艨梢栽O(shè)置計(jì)時(shí)器中的這些值（函數(shù)和數(shù)據(jù)）并簡單地調(diào)用?init_timer。注意，init_timer?由?setup_timer?內(nèi)部調(diào)用。

voidinit_timer( struct timer_list *timer );voidsetup_timer( struct timer_list *timer, void (*function)(unsigned long), unsigned long data );

擁有一個(gè)經(jīng)過初始化的計(jì)時(shí)器之后，用戶現(xiàn)在需要設(shè)置過期時(shí)間，這通過調(diào)用?mod_timer?來完成。由于用戶通常提供一個(gè)未來的過期時(shí)間，他們通常在這里添加?jiffies?來從當(dāng)前時(shí)間偏移。用戶也可以通過調(diào)用?del_timer?來刪除一個(gè)計(jì)時(shí)器（如果它還沒有過期）：

intmod_timer( struct timer_list *timer, unsigned long expires );voiddel_timer( struct timer_list *timer );

最后，用戶可以通過調(diào)用?timer_pending（如果正在等待，將返回?1）來發(fā)現(xiàn)計(jì)時(shí)器是否正在等待（還沒有發(fā)出）：

inttimer_pending( const struct timer_list *timer );

計(jì)時(shí)器示例

我們來檢查一下這些 API 函數(shù)的實(shí)際運(yùn)行情況。清單 1?提供了一個(gè)簡單的內(nèi)核模塊，用于展示簡單計(jì)時(shí)器 API 的核心特點(diǎn)。在?init_module?中，您使用?setup_timer?初始化了一個(gè)計(jì)時(shí)器，然后調(diào)用?mod_timer?來啟動它。當(dāng)計(jì)時(shí)器過期時(shí)，將調(diào)用回調(diào)函數(shù)?my_timer_callback。最后，當(dāng)您刪除模塊時(shí)，計(jì)時(shí)器刪除（通過?del_timer）發(fā)生。（注意來自?del_timer?的返回檢查，它確定計(jì)時(shí)器是否還在使用。）

清單 1. 探索簡單計(jì)時(shí)器 API

#include #include #include MODULE_LICENSE("GPL");staticstruct timer_listmy_timer;void my_timer_callback( unsigned long data ){ printk( "my_timer_callback called (%ld).\n", jiffies );}int init_module( void ){ int ret; printk("Timer module installing\n"); // my_timer.function, my_timer.datasetup_timer( &my_timer, my_timer_callback, 0 ); printk( "Starting timer to fire in 200ms (%ld)\n", jiffies ); ret =mod_timer( &my_timer, jiffies + msecs_to_jiffies(200) ); if (ret) printk("Error in mod_timer\n"); return 0;}void cleanup_module( void ){ int ret; ret =del_timer( &my_timer ); if (ret) printk("The timer is still in use...\n"); printk("Timer module uninstalling\n"); return;}

您可以在 ./include/linux/timer.h 中進(jìn)一步了解計(jì)時(shí)器 API。盡管簡單計(jì)時(shí)器 API 簡單有效，但它并不能提供實(shí)時(shí)應(yīng)用程序所需的準(zhǔn)確性。為此，我們來看一下 Linux 最近新增的功能，該功能用于支持精確度更高的計(jì)時(shí)器。

高精確度計(jì)時(shí)器

高精確度計(jì)時(shí)器（簡稱?hrtimers）提供一個(gè)高精確度的計(jì)時(shí)器管理框架，這個(gè)框架獨(dú)立于此前討論過的計(jì)時(shí)器框架，原因是合并這兩個(gè)框架太復(fù)雜。盡管計(jì)時(shí)器在?jiffies?粒度上運(yùn)行，hrtimers 在納秒粒度上運(yùn)行。

hrtimer 框架的實(shí)現(xiàn)方式與傳統(tǒng)計(jì)時(shí)器 API 不同。hrtimer 不使用 buckets 和串聯(lián)操作，而是維護(hù)一個(gè)按時(shí)間排序的計(jì)時(shí)器數(shù)據(jù)結(jié)構(gòu)（按時(shí)間順序插入計(jì)時(shí)器，以最小化激活時(shí)的處理）。這個(gè)數(shù)據(jù)結(jié)構(gòu)是一個(gè) “紅-黑” 樹，對于注重性能的應(yīng)用程序很理想（且恰好作為內(nèi)核中的一個(gè)庫普遍可用）。

hrtimer 框架作為內(nèi)核中的一個(gè) API 可用，用戶空間應(yīng)用程序也可以通過?nanosleep、itimers?和 Portable Operating System Interface (POSIX)-timers interface 使用它。hrtimer 框架被主線化（mainlined）到 2.6.21 內(nèi)核中。

高精確度計(jì)時(shí)器 API

hrtimer API 與傳統(tǒng) API 有些相似，但它們之間的一些根本差別是它能夠進(jìn)行額外的時(shí)間控制。應(yīng)該注意的第一點(diǎn)是：時(shí)間不是用?jiffies?表示的，而是以一種名為?ktime?的特殊數(shù)據(jù)類型表示。這種表示方法隱藏了在這個(gè)粒度上有效管理時(shí)間的一些細(xì)節(jié)。hrtimer API 正式確認(rèn)（formalize）了絕對時(shí)間和相對時(shí)間之間的區(qū)別，要求調(diào)用者指定類型。

與傳統(tǒng)的計(jì)時(shí)器 API 類似，高精確度計(jì)時(shí)器通過一個(gè)結(jié)構(gòu)表示 — 這里是?hrtimer。這個(gè)結(jié)構(gòu)從用戶角度定義定時(shí)器（回調(diào)函數(shù)、過期時(shí)間等）并包含了管理信息（其中計(jì)時(shí)器存在于 “紅-黑” 樹、可選統(tǒng)計(jì)數(shù)據(jù)等中）。

定義過程首先通過?hrtimer_init?初始化一個(gè)計(jì)時(shí)器。這個(gè)調(diào)用包含計(jì)時(shí)器、時(shí)鐘定義和計(jì)時(shí)器模式（one-shot 或 restart）。使用的時(shí)鐘在 ./include/linux/time.h 中定義，表示系統(tǒng)支持的各種時(shí)鐘（比如實(shí)時(shí)時(shí)鐘或者單一時(shí)鐘，后者只表示從一個(gè)起點(diǎn)[比如系統(tǒng)啟動]開始的時(shí)間）。計(jì)時(shí)器被初始化之后，就可以通過?hrtimer_start?啟動。這個(gè)調(diào)用包含過期時(shí)間（在?ktime_t中）和時(shí)間值的模式（絕對或相對值）。

voidhrtimer_init( struct hrtimer *time, clockid_t which_clock, enum hrtimer_mode mode );inthrtimer_start(struct hrtimer *timer, ktime_t time, const enum hrtimer_mode mode);

hrtimer 啟動后，可以通過調(diào)用?hrtimer_cancel?或?hrtimer_try_to_cancel?來取消。每個(gè)函數(shù)都包含將被停止的計(jì)時(shí)器的 hrtimer 引用。這兩個(gè)函數(shù)的區(qū)別在于：hrtimer_cancel?函數(shù)試圖取消計(jì)時(shí)器，但如果計(jì)時(shí)器已經(jīng)發(fā)出，那么它將等待回調(diào)函數(shù)結(jié)束；hrtimer_try_to_cancel?函數(shù)也試圖取消計(jì)時(shí)器，但如果計(jì)時(shí)器已經(jīng)發(fā)出，它將返回失敗。

inthrtimer_cancel(struct hrtimer *timer);inthrtimer_try_to_cancel(struct hrtimer *timer);

可以通過調(diào)用?hrtimer_callback_running?來檢查 hrtimer 是否已經(jīng)激活它的回調(diào)函數(shù)。注意，這個(gè)函數(shù)由?hrtimer_try_to_cancel?內(nèi)部調(diào)用，以便在計(jì)時(shí)器的回調(diào)函數(shù)被調(diào)用時(shí)返回一個(gè)錯誤。

inthrtimer_callback_running(struct hrtimer *timer);

ktime API

本文沒有討論 ktime API，它提供一組豐富的函數(shù)來以較高的精確度管理時(shí)間?？梢栽?./linux/include/ktime.h 中查看 ktime API。

一個(gè) hrtimer 示例

hrtimer API 的使用方法非常簡單，如?清單 2?所示。在?init_module?中，首先定義針對超時(shí)的相對時(shí)間（本例中為 200ms）。然后，通過調(diào)用?hrtimer_init?來初始化您的 hrtimer（使用單一時(shí)鐘），并設(shè)置回調(diào)函數(shù)。最后，使用此前創(chuàng)建的?ktime?值啟動計(jì)時(shí)器。當(dāng)計(jì)時(shí)器發(fā)出時(shí)，將調(diào)用?my_hrtimer_callback?函數(shù)，該函數(shù)返回?HRTIMER_NORESTART，以避免計(jì)時(shí)器自動重新啟動。在?cleanup_module?函數(shù)中，通過調(diào)用?hrtimer_cancel?來取消計(jì)時(shí)器。

清單 2. 探索 hrtimer API

#include #include #include #include MODULE_LICENSE("GPL");#define MS_TO_NS(x)(x * 1E6L)staticstruct hrtimerhr_timer;enum hrtimer_restart my_hrtimer_callback( struct hrtimer *timer ){ printk( "my_hrtimer_callback called (%ld).\n", jiffies ); returnHRTIMER_NORESTART;}int init_module( void ){ktime_t ktime; unsigned long delay_in_ms = 200L; printk("HR Timer module installing\n"); ktime =ktime_set( 0, MS_TO_NS(delay_in_ms) );hrtimer_init( &hr_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL );hr_timer.function= &my_hrtimer_callback; printk( "Starting timer to fire in %ldms (%ld)\n", delay_in_ms, jiffies );hrtimer_start( &hr_timer, ktime, HRTIMER_MODE_REL ); return 0;}void cleanup_module( void ){ int ret; ret =hrtimer_cancel( &hr_timer ); if (ret) printk("The timer was still in use...\n"); printk("HR Timer module uninstalling\n"); return;}

關(guān)于 hrtimer API，還有許多內(nèi)容這里沒有涉及到。一個(gè)有趣的方面是它能夠定義回調(diào)函數(shù)的執(zhí)行上下文（比如在 softirq 或 hardiirq 上下文中）。您可以在 ./include/linux/hrtimer.h 文件中進(jìn)一步了解 hrtimer API。

回頁首

內(nèi)核列表

如本文此前所述，列表是有用的結(jié)構(gòu)，內(nèi)核提供了一個(gè)有效的通用使用實(shí)現(xiàn)。另外，您將在我們此前討論過的 APIs 下面發(fā)現(xiàn)列表。理解這個(gè)雙重鏈接的列表 API 有助于使用這個(gè)有效的數(shù)據(jù)結(jié)構(gòu)進(jìn)行開發(fā)，您會發(fā)現(xiàn)，代碼在這個(gè)利用列表的內(nèi)核中是多余的?，F(xiàn)在我們來快速了解一下這個(gè)內(nèi)核列表 API。

這個(gè) API 提供一個(gè)?list_head?結(jié)構(gòu)，用于表示列表頭（錨點(diǎn)）和結(jié)構(gòu)內(nèi)（in-structure）列表指針。我們來檢查一個(gè)包含列表功能的樣例結(jié)構(gòu)（參見?清單 3）。注意，清單 3 添加了?list_head結(jié)構(gòu)，該結(jié)構(gòu)用于對象鏈接（object linkage）。注意，可以在您的結(jié)構(gòu)中的任意位置添加這個(gè)?list_head?結(jié)構(gòu) — 通過一些 GCC（list_entry?和?container_of，在 ./include/kernel/kernel.h 中定義）— 可以取消從列表指針到超對象的引用。

清單 3. 帶有列表引用的樣例結(jié)構(gòu)

struct my_data_structure {int value;struct list_headlist;};

與其他列表實(shí)現(xiàn)一樣，需要一個(gè)列表頭來充當(dāng)列表的錨點(diǎn)。這通常通過?LIST_HEAD?宏來完成，這個(gè)宏提供列表的聲明和初始化。這個(gè)宏創(chuàng)建一個(gè)結(jié)構(gòu)?list_head?對象，可以在該對象上添加其他一些對象。

LIST_HEAD( new_list )

也可以通過使用?LIST_HEAD_INIT?宏手動創(chuàng)建一個(gè)列表頭（例如，您的列表頭位于另一個(gè)結(jié)構(gòu)中）。

主初始化完成后，可以使用?list_add?和?list_del?等函數(shù)來操縱列表。下面，我們將跳到示例代碼，以便更好地解釋這個(gè) API 的使用方法。

列表 API 示例

清單 4?提供一個(gè)簡單的內(nèi)核模塊來探索幾個(gè)列表 AIO 函數(shù)（./include/linux/list.h 中包含更多函數(shù)）。這個(gè)示例創(chuàng)建了兩個(gè)列表，使用?init_module?函數(shù)來填充它們，然后使用?cleanup_module?函數(shù)來操縱這兩個(gè)列表。

一開始，您創(chuàng)建了您的數(shù)據(jù)結(jié)構(gòu)（my_data_struct），該結(jié)構(gòu)包含一些數(shù)據(jù)和兩個(gè)列表頭。這個(gè)示例展示可以將一個(gè)對象同時(shí)插入到多個(gè)列表中。然后，您創(chuàng)建了兩個(gè)列表頭（my_full_list?和?my_odd_list）。

在?init_module?函數(shù)中，您創(chuàng)建了 10 個(gè)數(shù)據(jù)對象，并使用?list_add?函數(shù)將它們加載到列表中（所有對象加載到?my_full_list?中，所有奇值對象加載到?my_odd_list) 中）。這里要注意一點(diǎn)：list_add?接受兩個(gè)參數(shù)，一個(gè)是將用到的對象中的列表引用，另一個(gè)是列表錨點(diǎn)。這個(gè)示例展示了將一個(gè)數(shù)據(jù)對象插入多個(gè)列表的能力，方法是使用內(nèi)核的內(nèi)部機(jī)制來識別包含列表引用的超級對象。

cleanup_module?函數(shù)提供了這個(gè) API 的其他幾個(gè)功能，其中之一是?list_for_each?宏，這個(gè)宏簡化了列表迭代。對于這個(gè)宏，您提供了一個(gè)對當(dāng)前對象（pos）的引用以及將被迭代的列表引用。對于每次迭代，您接收一個(gè)?list_head?引用，list_entry?接收這個(gè)引用以識別容器對象（您的數(shù)據(jù)結(jié)構(gòu)）。指定您的結(jié)構(gòu)和結(jié)構(gòu)之內(nèi)的列表變量，后者用于在內(nèi)部取消引用，返回容器。

為發(fā)出奇值列表（odd list），要使用另一個(gè)名為?list_for_each_entry?的迭代宏。這個(gè)宏更簡單，因?yàn)樗詣犹峁?shù)據(jù)結(jié)構(gòu)，無需再執(zhí)行一個(gè)?list_entry?函數(shù)。

最后，使用?list_for_each_safe?來迭代列表，以便釋放已分配的元素。這個(gè)宏將迭代列表，但阻止刪除列表?xiàng)l目（刪除列表?xiàng)l目是迭代操作的一部分）。您使用?list_entry?來獲取您的數(shù)據(jù)對象（以便將它釋放回內(nèi)核池），然后使用?list_del?來釋放列表中的條目。

清單 4. 探索列表 API

#include #include #include MODULE_LICENSE("GPL");struct my_data_struct { int value; structlist_headfull_list; structlist_headodd_list;};LIST_HEAD( my_full_list );LIST_HEAD( my_odd_list );int init_module( void ){ int count; struct my_data_struct *obj; for (count = 1 ; count < 11 ; count++) { obj = (struct my_data_struct *) kmalloc( sizeof(struct my_data_struct), GFP_KERNEL ); obj->value = count;list_add( &obj->full_list, &my_full_list ); if (obj->value & 0x1) {list_add( &obj->odd_list, &my_odd_list ); } } return 0;}void cleanup_module( void ){ structlist_head*pos, *q; struct my_data_struct *my_obj; printk("Emit full list\n");list_for_each( pos, &my_full_list ) { my_obj =list_entry( pos, struct my_data_struct, full_list ); printk( "%d\n", my_obj->value ); } printk("Emit odd list\n");list_for_each_entry( my_obj, &my_odd_list, odd_list ) { printk( "%d\n", my_obj->value ); } printk("Cleaning up\n");list_for_each_safe( pos, q, &my_full_list ) { struct my_data_struct *tmp; tmp =list_entry( pos, struct my_data_struct, full_list );list_del( pos ); kfree( tmp ); } return;}

還有很多其他函數(shù)，它們的用途包括在列表末尾而不是頭部添加數(shù)據(jù)（list_add_tail）、連接列表（list_splice）、測試列表的內(nèi)容（list_empty）等。請參見?參考資料?詳細(xì)了解內(nèi)核列表函數(shù)。

?