Overview Kdump 是 Linux 核心的一個特殊功能，可在發生 kernel panic 時建立 Core Dump。當出現異常導致 Kdump 被觸發時，kernel 會匯出一個記憶體的 image，其在 Linux 上通稱為 vmcore。該 image 可用於除錯和確定崩潰的原因。這個 image 會以 ELF 格式匯出，可以在處理核心崩潰時通過 /proc/vmcore 直接存取，或者可以也可將其自動儲存到本地或遠端檔案系統。 Kdump 大致的運作方式是: 在 kernel panic 的情況下，Kdump 會引導另一個 Linux kernel(稱為 dump-capture kernel)，用它來匯出和儲存記憶體狀態。這麼做的目的是讓系統啟動到一個乾淨、可靠的環境，而不是依賴已經崩潰的 kernel，因為後者可能會引發其他問題反而破壞了原本的異常環境。例如，在寫入記憶體轉儲檔案時導致檔案系統損壞。 為了實現這個「雙核心」的環境，Kdump 在核心崩潰後會立即使用 kexec booting 到 dump-capture kernel，使用 kexec 引導「覆蓋」當前執行的核心，這做法同時避免執行 bootloader 和系統韌體(BIOS/UEFI)的硬體初始化行為。 整體的運作即如下附圖所展示: image

:::info 本文主要是以系統軟體開發的角度出發整理相關資料，因此對於硬體特徵不會有過多著墨! 若對硬體細節有興趣可參考 USB Made Simple 和 USB in a NutShell 等材料。 ::: Overview USB(Universal Serial Bus) 是連接電腦與裝置的一種序列匯流排標準，也是用於電子裝置之間通訊的一種協定。 在 USB 被制定以前，外接式裝置的傳輸介面各不相同，如印表機只能接 Parrel Port、數據機只能接 RS232、滑鼠鍵盤只能接 PS/2 等。繁雜的介面系統，加上必須安裝驅動程式並重新開機才能使用的限制，都會造成使用者的困擾。因此，創造出一個統一且支援易插拔的外接式傳輸介面，便成為無可避免的趨勢，USB 應運而生。 image

引言 在 Linux 核心中的 CPU 排程器經歷許多變化。然而 Linux 作為一個可以應用於資料庫、行動裝置、雲端服務等多種平台的作業系統，從 O(1) Scheduler、CFS、到現今的 EEVDF，核心中預設的排程演算法的設計關鍵是必須提供通用(generically)的策略，以符合各式各樣的應用場景。僅有有限的參數被提供以微幅調校排程器，使得應用端得可以更接近理想的效能。 然而，對於某些採用 Linux 的公司來說，他們的平台僅存在特定的工作負載(workload)，此時通用的排程器就不能滿足他們的期待。與之相比，如果可以自訂排程器的行為，可能有機會獲得更多好處。不過若要直接改動核心程式碼實作自定義排程器，這需要一定的技術含量。考慮排程器作為作業系統的關鍵元件，若實作上有錯誤也很容易帶來負面影響。此外，Linux 不太可能允許各廠家把自訂的排程器發佈到上游，這會導致專案充斥冗餘程式碼與混亂。因此綜合來看，該以何種方式開發自訂排程器，以減輕開發的成本和維護的負擔，是至關重要的題目。 在此訴求下，有開發人員開始想在 Linux 中引入「可插入」的排程器機制。這將使得每個人都可以編寫自己定制的排程器，然後以低成本的方式輕鬆的將其植入到核心中使用。然而該用什麼方式來提供能最符合上述的要求呢? 此時 eBPF 就映入開發者的眼簾。eBPF 不但支援動態載入程式碼到 kernel 中執行的功能，也提供檢查器(verifier)來減少載入的程式破壞 kernel 的風險，無疑可以說是最適合發展「可插入」排程器的基礎。 於是在此基礎上，sched_ext 就此誕生了。sched_ext 除了允許客製化排程器，也能做為測試各種排程演算法的試驗台，其包含以下的特點: 開放完整的排程介面，以允許可以在上面實現任何排程演算法

Linux 核心設計: 不只挑選任務的排程器 :::success :video_camera: 此筆記僅補充一些有興趣的議題，詳細請參考課程錄影 ::: Overview 原則上，單個 CPU 總是只能在單個時間點中執行一個任務。即使是多處理器的架構下，要運行的 process 數量往往也都超過 core 的數量。所以我們需要 scheduler，其作用為考量如任務的類型或者重要程度，並決定下一個要運行的任務及其運行時間。 Scheduler 不能毫無根據的隨便挑選下一個任務，有些任務需要及早完成，或者有些任務可以等待讓其他任務先運行，如何妥善分配時間給不同的任務是重要且困難的問題。並且，scheduler 還需要考慮 context switch 的成本，雖然頻繁的切換任務可能可以讓每個任務能儘早的回應，但過於頻繁的切換任務反而會讓 CPU 把大部份心力都花在 context switch 而非任務本身。因此，好的 scheduler 需要適當的去權衡 context switch 的頻率，讓系統可以在任務的回應與效率間取得平衡。

:::danger WIP ::: 引用: Energy Aware Scheduling 引言 在過往，Linux 應用的場景大多是伺服器或桌面系統，因此系統的效能如吞吐量(throughput)等指標是評斷排程器優劣的重要基準。但現今的 Linux 應用的領域更為多元，也帶出新的問題著眼點。舉例來說，Linux 現在也被大量應用在手機等嵌入式裝置上。在這類平台中，耗電的程度也會是評判的標準，使用者會希望使用最低的功耗來達到理想的工作目標。此外，過度的耗電也可能導致嵌入式裝置的溫度升高，間接影響 CPU 的運作而導致效能降低。因此，如何管理裝置的電源耗損是近代 Linux 的重要課題。 隨此需求，Energy Aware Schedulng（EAS）機制被導入至 Linux 核心中。EAS 使排程器能夠預測對 CPU 功耗的影響。其依靠 CPU 的能源模型 (Energy Model, EM) 為每個任務選擇節能的 CPU，並盡量降低對吞吐量的影響。

甚麼是 MSI? MSI(Message Signaled Interrupt) 是一種特殊的中斷機制，主要在 PCI/PCIe 上支援，能夠提升中斷處理的效能。有些其他類型的硬體也使用 MSI 來實作中斷機制。 傳統上的中斷又別名為 INTx。在此方式下，裝置會有一個中斷用的引腳(pin)，當它想要向 host 發出中斷訊號時，它會 assert 該 pin，以 level-triggered 形式將引腳訊號拉低(active low)。這種 out-band 形式的中斷訊號使用與主資料分開的專用路徑來傳送控制資訊。與之相對，MSI 是以 in-band 訊號藉由主資料路徑的傳遞中斷的訊息。簡單來說，裝置會將描述中斷的資料寫到特殊的記憶體映射位置，然後 chip 再將相應的中斷傳遞給處理器。 MSI 的優勢 與傳統中斷硬體相比，MSI 能減少 pin 的數量，意味著 PCIe Connector 可以更簡化。在性能面上 MSI 也可以帶來一些效益。一方面，因為基於 pin 的中斷會有與 DMA/posted write 競爭的可能性。PCI 裝置傳遞資料給 host 的流程是: PCI 裝置將資料寫入記憶體 PCI 裝置發送中斷以表示 DMA 寫入完成

PCI Express Layering PCIe 是一種序列匯流排(serial bus)。在 PCIe 協議上，所有操作都以封包(packet)的形式完成。舉例來說，假設 CPU 想要將一些資料寫入裝置。它將命令轉送到 PCIe Bridge，然後 PCIe bridge 會建立一個封包、之中寫入位址和資料、然後以序列方式轉送到目標。目標裝置收到封包後，再進行解析並執行之。 image PCI Express® Base Specification Revision 5.0 PCIe 所連接兩端以封包的形式來溝通，以將資訊從傳輸端傳送到接收端。而 PCIe 是一個多層協定，由事務層(Transaction)、資料交換層(Data Link)和實體層(Physical)構成。傳輸時，每當封包經過下一層級後，會將原本的封包加上此層的封包所需的附加資訊。接收時則相反，封包由實體層步步拆解至事務層的封包， image

Overview of PREEMPT_RT Linux 核心設計: PREEMPT_RT 作為邁向硬即時作業系統的機制 在前一章節的 Deadline Scheduling 中，讀者對 Real-time System 的定義應該已經有了基礎的認識。不過，該文主要著眼於與 Soft real-time 相關部分，實際上，Hard real-time 在系統軟體應用中獲得更多注目。 Hard real-time 所受到的關注反映實際的需求。在某些任務中，比起大部分時候都能更快速的完成，在規範的時間限制內完成來得更為關鍵。比如自駕車在偵測到障礙物之後，必須要每次都在規範的時間中停下來。這種即時性的保證在醫療、航空或其他工業領域中至關重要，因為些微偏差也許就意味著可觀的金錢損失、甚至是對生命的傷害。 Linux 最初是以分時多工排程設計的作業系統。在將其修改使得能夠滿足 Hard real-time 的路程上，關鍵點是要減少無法搶佔(preemption)的核心程式碼，這就是 PREEMPT_RT 系列改動的重要目標。比如: 在 PREEMPT_RT 下，softirq 被調整為 kernel thread，意味著每個 interrupt handler 有獨立擁有的 context，可擺脫搶佔的限制; 或者，一般的 spinlock 被改為可以睡眠的 mutex，因此持有鎖的 task 將可以暫時釋放 CPU 資源，已允許其他即時的任務獲得排程。 本文將探討與 PREEMPT_RT 相關的知識點以及工具。

Real-time System Overview 即時作業系統(Real-time operating system) 是作業系統中的一類。其特性是必須在精確的時間限制內對事件做出反應。因此首要目標不是高的吞吐量(throughput)，而是保證任務的延遲，使得以在特定時間內完成。 image Ref: Deadline Scheduler - From theory to your server 根據對截止時間的要求，即時系統可再分為 soft real-time 和 hard real-time 兩類: Soft real-time: 系統盡可能在時限內完成請求(request)，未在時限內完成的回應(response)可能品質不佳，但不至於被視為是致命的錯誤

Hackbench 簡介 Hackbench 是在 rt-tests 中的效能測試工具之一，其用途在於對 CPU scheduler 進行壓力測試。具體產生的情境是: 創建指定數量的 schedulable entities(thread/process)各自做為 sender 和 receiver，並將各個 sender 和 receiver 劃分組別。對於同組別的 sender 和 receiver，這些 entities 之間會透過 socket 或 pipe 進行特定次數的資料交換。最後，計算完成所有來回收發資料所需的時間。 image 圖片來源: Is Benchmarking a Gimmick or Strength? 為什麼這個時間與 CPU scheduler 的能力有關聯呢? 可以先從 context switch 的發生方式說起。首先，要知道 context swtich 可以分成主動與被動兩種。在主動的部份，對於 receiver 來說，當 read 沒辦法取得資料時，receiver 會被 blocking 並主動讓出 CPU 進入 sleep。反之對於 sender，如果 write 找不到足夠空間寫入資料時，sender 也會被 blocking 且主動讓出 CPU。此外核心也有例如 timer interrupt 的機制來迫使 schedulable entities 讓出 CPU，這是被動 context switch 的部份。

O(1) Scheduler 概述 CFS Scheduler 深入剖析 CFS Scheduler PELT EEVDF Scheduler/1 EEVDF Scheduler/2 CPU 排程器測試工具 sched_ext Energy Aware Scheduling Deadline Scheduling

Linux 核心設計: 淺談同步機制 Linux 核心設計: 多核處理器和 spinlock 從 CPU cache coherence 談 Linux spinlock 可擴展能力議題 搭配 CSAPP: Chapter 12 一起服用風味更佳 Mutex 與 Semaphore Mutex 與 semaphore 是經常被混用的觀念(尤其是 binary semaphore = mutex 這種理解)，做為系統的開發者(雖然我還不是)，勢必需要釐清其中的差異。 對於 mutex 來說，解鎖只能由上鎖的 thread 來完成，經常使用的情境是對於資源的保護 / 互斥。就像是對於一個房間，只存在一把鑰匙，拿到的人就可以進入房間，而其他的人必須排隊等待，直到那個人出來。

什麼是 drgn? 在分析 Linux 上的問題或者學習各個子系統時，相較於只看程式碼而臆測其執行行為，搭配觀察實際運行的狀況才是正確且有效的方式。而如果只是想觀察函式的執行，Linux 內建的 ftrace 已經提供了豐富的支援。但在此之上，如果我們能夠獲取 Linux 核心裡關鍵的變數或資料結構的內容，則可以對當前的系統狀態有更全面的了解。 這個目的可以藉由 drgn 做到。drgn 是一個強大的除錯工具，其目標是讓除錯感覺就像編寫程式碼一樣自然，可以輕鬆的用 Python 編寫腳本來分析運行的 Linux 系統、vmcore 或 userspace 的程式。針對 Linux 系統部分，drgn 可以分析 vmlinux 裡的符號(symbol)和型別(type)，並公開給除錯程式的撰寫者。搭配 KCORE 揭示運行時核心的虛擬 ELF 檔案，就可以存取到核心中的變數與資料結構! 這意味著我們可以了解描述驅動程式的資訊結構、排程器的運行隊列(runqueue)、每一個 GPIO 或 interrupt 的 descriptor，在運行當下的資料結構中的內容為何! 在追蹤系統執行時，這絕對是相當有助益的資訊! 前置準備 安裝 drgn 以 Ubuntu 的系統為例，需要先安裝drgn 的依賴套件。 $ sudo apt install autoconf automake check \

Introduction PCI Peripheral Component Interconnect(PCI) 是一種連接電腦主機板和外部裝置的匯流排標準。其取代了 ISA 和 VESA，成為現代電腦中常見的標準。 特性上，PCI 是採同步傳輸(Synchronous transaction)。這意味著 PCI bus 只使用一個 clock。預設情況下，時脈運行在 33MHz，但允許更低到甚至 0MHz 以省電。如果硬體支援，則可以運行較高的 66MHz。 PCI 是 32 位元匯流排，採用 BURST 傳輸。所謂 BURST，意指傳輸的方式為: 開始傳輸 第一個 clock cycle 用於指定 32 位元位址

安裝 QEMU 使用 QEMU 的系統模擬器來載入新的 kernel image 在開發和測試上十分便利。我們可以在修改 Linux 的原始碼後，直接重新編譯就能快速地將其執行在 QEMU 上。此外，QEMU 也支援遠端除錯的功能，因此我們可以很容易的透過此工具來觀察 Linux 執行過程的硬體暫存器、記憶體等狀態，甚至是設置斷點來追蹤 Linux 的執行。 想要安裝 QEMU，可以透過 apt 等類似工具直接下載到編譯好的執行檔。不過更建議複製(clone)一份 qemu 原始碼重新編譯，這樣必要時可以自行調整編譯設定甚至是追蹤 QEMU 的執行。 建議切換至 stable branch 進行編譯，以模擬 RISC-V 為例，可以透過以下方式編譯: ./configure --target-list=riscv64-softmmu --enable-virtfs make -j $(nproc) sudo make install

環境建置 :::info 可交叉搭配 Linux 核心設計: 開發、測試與除錯環境。這裡只簡單敘述建置步驟。 ::: Linux 完整安裝方式可以參考 Rust - Quick Start，下面僅針對特定情況做舉例 執行以下可以確認要建構 Rust for Linux 缺少的套件。

RFC Patches 2 前一章所研讀的 patches 最終並未正式合併到 kernel 中。維護者 Peter Zijlstra 針對此做了修正與調整，重新釋出了進階的改動 [RFC][PATCH 00/10] sched/fair: Complete EEVDF。在此系列內容中，除了原本對 time slice/request size 的支援，Peter 還新增 delayed-dequeue 機制以彌補原始論文在 EEVDF 上的缺陷。這些改動將成為補足 EEVDF 的最後一塊拼圖。而本節將針對這一系列內容進行探討。 [RFC][PATCH 01/10] sched/eevdf: Add feature comments 單純是加上註解描述幾個 SCHED_FEAT。 --- a/kernel/sched/features.h +++ b/kernel/sched/features.h @@ -5,7 +5,14 @@ * sleep+wake cycles. EEVDF placement strategy #1, #2 if disabled.

:::success BKK19-TR02 - Linux Kernel Power Management - 101 對 Linux Kernel 的 PM 框架做了 overview，推薦在開始本系列文章前預習一番。投影片可以參考此連結。 ::: 引言 在 Linux 中，大部分程式碼都是屬驅動程式(Device Driver)，而多數 Linux 電源管理(Power Management, PM) 的程式碼也是由驅動程式引導。因此，作為認識電源管理的起點，認識驅動程式使用何種模型和介面連接與系統交互，以完成電源管理的目標，是首要了解的課題。 在 Linux 中使用兩種模型來進行電源管理: System Sleep model 和 Runtime Power Management model。本篇將以第一種模型為主進行探討，而 Runtime Power Management model 會在下一章節進行分析。 Overview

引言 在過去章節中，我們知道 Linux 可以透過各式的機制提供電源管理之功能。然而如果功能實作中有錯誤，加上睡眠狀態可能部分功能將暫停之狀態下，如果發生問題，核心是否還可以產生關鍵除錯訊息?或者可否搭配特定工具來釐清問題? 對於相關功能的核心的開發者，這是至關重要的問題。 除此之外，系統的睡眠和喚醒時間也是調校的重點。對於使用者而言，平台進入低功耗狀態與恢復運作的時間是愈短愈好。則如何分析各個裝置驅動程式的耗時，或者哪個睡眠/恢復階段是時間的瓶頸，同樣是不能忽視的問題。 因此，在本章節中我們將討論如何對 Linux 中的電源管理進行測試、除錯及分析。期待可以彙整不同的工具，以便在問題出現時有效率地找出原因所在! PM on QEMU 由於 Power management 並非是系統的必要功能，讀者手上的硬體可能不支援相關功能(比如某些 Raspberry Pi)。所幸 QEMU 對此有一定程度的支援，可以讓我們很容易的測試。因此在正文開始之前，先簡單說明如何透過 QEMU 來觀察系統的睡眠與喚醒。

:::info 僅記錄最粗淺的概念，詳細的例子請直接參考原書籍或者課程投影片: Concurrency Synchronization-basic Synchronization-advanced Thread-Level Parallelism ::: Concurrency