hrtimers - 高精度核心定時器子系統

此補丁引入了一個新的高精度核心定時器子系統。

人們可能會問：我們已經有一個定時器子系統（kernel/timers.c），為什麼還需要兩個定時器子系統？在多次嘗試將高解析度和高精度功能整合到現有定時器框架中，並實踐測試了各種此類高解析度定時器實現後，我們得出結論，定時器輪程式碼從根本上不適合這種方法。我們最初不相信這一點（‘一定有辦法解決’），並花費了大量精力試圖將這些功能整合到定時器輪中，但我們失敗了。事後看來，這種整合之所以困難/不可能有幾個原因：

  • 強制以相同方式處理低解析度和高解析度定時器會導致大量的折衷、宏魔法和 #ifdef 混亂。timers.c 程式碼圍繞 jiffies 和 32 位假設“緊密編碼”，多年來為相對狹窄的用例（jiffies 在相對狹窄的 HZ 範圍內）進行了磨練和微最佳化——因此，即使是小的擴充套件也容易破壞輪的概念，導致更糟糕的折衷。定時器輪程式碼非常好且緊湊，在當前使用中沒有任何問題——但它根本不適合擴充套件用於高解析度定時器。

  • 級聯的不可預測 [O(N)] 開銷導致延遲，這需要更復雜地處理高解析度定時器，進而降低了魯棒性。這種設計仍然會導致相當大的計時不準確性。級聯是定時器輪概念的基本屬性，它無法被“設計”掉，否則將不可避免地以不可接受的方式降低 timers.c 程式碼的其他部分的效能。

  • 當前基於定時器輪的 posix-timer 子系統實現，已經引入了相當複雜的處理，用於在 settimeofday 或 NTP 時間點對絕對 CLOCK_REALTIME 定時器進行必要的重新調整——這進一步透過示例支援了我們的經驗：定時器輪資料結構對於高解析度定時器來說過於僵化。

  • 定時器輪程式碼最適用於可識別為“超時”的用例。此類超時通常用於覆蓋各種 I/O 路徑中的錯誤情況，例如網路和塊 I/O。絕大多數此類定時器從未過期，也很少重新級聯，因為預期的正確事件及時到達，因此可以在需要進一步處理它們之前將其從定時器輪中移除。因此，這些超時的使用者可以接受定時器輪的粒度和精度權衡，並且很大程度上期望定時器子系統具有接近零的開銷。對於它們而言，精確計時不是核心目的——事實上，大多數使用的超時值都是臨時性的。對於它們來說，保證實際超時完成的處理最多是一種必要的惡，因此應該儘可能便宜和無侵入性（因為大多數超時在完成之前就被刪除了）。

精確定時器的主要使用者是利用 nanosleep、posix-timers 和 itimer 介面的使用者空間應用程式。此外，核心內部使用者，如需要精確計時事件（例如多媒體）的驅動程式和子系統，也可以從單獨的高解析度定時器子系統的可用性中受益。

儘管此子系統尚未提供高解析度時鐘源，但 hrtimer 子系統可以輕鬆擴充套件以支援高解析度時鐘功能，並且相關補丁已存在並正在迅速成熟。對即時和多媒體應用程式以及精確定時器其他潛在使用者的日益增長的需求，是分離“超時”和“精確定時器”子系統的另一個原因。

另一個潛在好處是，這種分離允許對現有定時器輪進行更多特殊目的最佳化，以滿足低解析度和低精度用例的需求——一旦精度敏感的 API 從定時器輪中分離並遷移到 hrtimers。例如，我們可以將超時子系統的頻率從 250 Hz 降低到 100 HZ（甚至更小）。

hrtimer 子系統實現細節

基本設計考慮因素是

  • 簡單性

  • 資料結構不限於 jiffies 或任何其他粒度。所有核心邏輯都以 64 位納秒解析度工作——沒有折衷。

  • 簡化現有與計時相關的核心程式碼

另一個基本要求是在啟用時立即將定時器排隊並排序。在考察了基數樹和雜湊表等幾種可能的解決方案後，我們選擇了紅黑樹作為基本資料結構。紅黑樹作為庫在核心中可用，並用於記憶體管理和檔案系統等各種效能關鍵領域。紅黑樹僅用於時間排序，而一個單獨的列表用於使過期程式碼快速訪問排隊的定時器，而無需遍歷紅黑樹。

（這個獨立的列表在以後引入高解析度時鐘時也很有用，屆時我們需要獨立的待處理和已過期佇列，同時保持時間順序不變。）

然而，按時間順序入隊並非純粹為了高解析度時鐘，它也簡化了基於低解析度 CLOCK_REALTIME 的絕對定時器的處理。現有實現需要維護一個包含所有已設定的絕對 CLOCK_REALTIME 定時器的額外列表，並涉及複雜的鎖定。在 settimeofday 和 NTP 的情況下，所有定時器 (!) 都必須出隊，時間更改程式碼必須逐一修復它們，然後將它們全部重新入隊。按時間順序入隊以及以絕對時間單位儲存過期時間，從 posix-timer 實現中移除了所有這些複雜且擴充套件性差的程式碼——時鐘可以簡單地設定，而無需觸及紅黑樹。這也使 posix-timers 的處理在總體上更簡單。

hrtimers 的鎖定和每 CPU 行為大部分借鑑了現有的定時器輪程式碼，因為它成熟且適用。由於資料結構不同，共享程式碼實際上並沒有帶來優勢。此外，hrtimer 函式現在具有更清晰的行為和名稱——例如 hrtimer_try_to_cancel() 和 hrtimer_cancel() [它們大致等同於 timer_delete() 和 timer_delete_sync()]——因此在演算法層面它們之間沒有直接的一一對映，也就沒有真正的程式碼共享潛力。

基本資料型別：所有時間值，無論是絕對時間還是相對時間，都以特殊的納秒解析度 64 位型別表示：ktime_t。（最初，ktime_t 值及其操作的核心內部表示透過宏和行內函數實現，並且可以在“混合聯合”型別和純“標量”64 位納秒錶示之間切換（在編譯時）。這在 Y2038 工作中被放棄了。）

hrtimers - 定時器值舍入

hrtimer 程式碼會將定時器事件舍入到較低解析度的時鐘，因為它必須這樣做。否則，它將完全不進行人工舍入。

一個問題是，clock_getres() 介面應該向使用者返回什麼樣的解析度值。它將返回給定計時器所擁有的實際解析度——無論是低解析度、高解析度還是人為設定的低解析度。

hrtimers - 測試與驗證

我們使用了基於 hrtimers 的高解析度時鐘子系統來驗證 hrtimer 的實際實現細節，並且還運行了 posix 定時器測試以確保符合規範。我們還在低解析度時鐘上運行了測試。

hrtimer 補丁將以下核心功能轉換為使用 hrtimers

  • nanosleep

  • itimers

  • posix-timers

nanosleep 和 posix-timers 的轉換使得 nanosleep 和 clock_nanosleep 的統一成為可能。

程式碼已成功編譯到以下平臺

i386, x86_64, ARM, PPC, PPC64, IA64

程式碼已在以下平臺進行了執行測試

i386(UP/SMP), x86_64(UP/SMP), ARM, PPC

hrtimers 也被整合到 -rt 樹中，以及基於 hrtimers 的高解析度時鐘實現，因此 hrtimers 程式碼在實踐中得到了大量的良好測試和使用。

Thomas Gleixner, Ingo Molnar