# Linux 核心專題: sched_ext 研究
> 執行人: otteryc
> [專題解說影片](https://youtu.be/7yue2xVmuCQ)
## 任務簡介
研究 sched_ext / scx，撰寫簡易的使用者層級 CPU 排程器並予以驗證。
## TODO: sched_ext 的設計考量和實作手法
> 儘量列出第一手材料，包含文件和演講
:::danger
注意用語：
* directory 是「目錄」，而非「檔案夾」
* command 是「命令」，而非「指令」
:::
sched_ext 是基於 BPF 的使用者層級 CPU 排程器，其目的在於簡化排程器的開發及實驗。在過去的 15 年內，排程的重要性發生了戲劇性的改變，現今的處理器不但有異質多核計算的情境，還有 CCX 、 NUMA 等等的架構問題在設計排程器時需要被考慮。
:::danger
Linux v6.10-rc5 已發布，重新統計程式碼行數
:::
> 兩份 release candidate 之間，沒有排程器相關的修改，參見 [Diffstat](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/diff/?id=v6.10-rc5&id2=v6.10-rc3&dt=2)
但是，截止 <s>2024/6 (v6.10-rc3)</s> 2024/6 (v6.10-rc5)，在 `kernel/sched` <s>資料夾</s> 目錄中有 28505 行的程式碼，直接從 Linux 核心的 CFS ( $\lt$ v6.6) 或 EEVDF ( $\geq$ v6.6) 排程器著手進行研究，其所需要的時間成本顯然過高，造成晚近排程器研究門檻上升。此外，即使直接更改 CFS 或 EEVDF 排程器的程式碼，每次更改都需 編譯核心 $\to$ 安裝核心 $\to$ 重啟電腦 的流程始能生效。因為 Linux 屬於 Monolithic kernel ，雖然有 modules 的機制，但是<s>仍然無法媲美 microkernel 中 service 的能力</s> ，僅能作為核心的延伸功能（Demysifying The Linux Kernel Scheduler，第 13 頁）。
:::danger
澄清關於 microkernel 的 server 描述，特別是排程器的設計。
:::
> Microkernel 旨在保障核心的安全性以及可靠性，排程器也是 Hurd 及 Mach 等 microkernel 實作中核心提供的基礎功能；此外， Solaris 作為 Monolithic Kernel ， Scheduling Classes 也可以作為可載入的核心模組，前面關於 microkernel 中 service 的敘述並不準確。
$\to$ [淺談 Microkernel 設計和真實世界中的應用](https://hackmd.io/@sysprog/microkernel-design)
此外， sched_ext 利用 eBPF 強大的連結時期靜態檢查機制，避免排程器的實作使得核心發生錯誤，這個專案更進一步的實作了核心內保護機制，防止被錯誤實作的排程器無限期的排斥單一行程的執行。得益於 eBPF 的 API ， sched_ext 在進行排程決策的程式碼可以執行在使用者層級，這使得執行及終止排程器的方法可以被顯著的簡化，僅需將 sched_ext 行程結束即可。
預計在 Linux v6.11 之後， sched_ext 將被收錄到開發主幹，參見 [Re: [PATCHSET v6] sched: Implement BPF extensible scheduler class](https://lore.kernel.org/bpf/CAHk-=wg8APE61e5Ddq5mwH55Eh0ZLDV4Tr+c6_gFS7g2AxnuHQ@mail.gmail.com/)。
## TODO: 在 sched_ext/scx 的基礎之上開發簡易的 CPU 排程器
> 需要能在 sched_ext 分支運作，針對 Linux v6.9+
### 環境設定
首先，由於 sched_ext 專案已獲 Linus Torvalds 接受， GitHub 上的 [sched-ext/sched_ext](https://github.com/sched-ext/sched_ext) 已於 2024/6/19 起不再維護，我們需要從 kernel.org 獲得最新的 sched_ext 在 kernel 內的 infrastructure
```bash
$ git clone https://git.kernel.org/pub/scm/linux/kernel/git/tj/sched_ext.git linux
$ cd linux
# commit hash: eb4a3b629b4d61e83dc49541185100a297a7e6ba
$ git checkout for_next
```
接著，我們需要進行編譯設定，在這份專題研究中，考量到 `sched_ext` 專案具有核心內保護機制的特性，我們直接在 Ubuntu 24.04 機器上進行，而不透過虛擬環境進行：
```bash
$ cp /boot/config-6.8.0-36-generic .config
$ make LLVM=1 CC=clang-18 nconfig
# required if utilizing ubuntu default config
$ scripts/config --disable SYSTEM_TRUSTED_KEYS
$ scripts/config --disable SYSTEM_REVOCATION_KEYS
```
在進行設定時，請參考 [Linux 核心設計: Scheduler(7): sched_ext](https://hackmd.io/@RinHizakura/r1uSVAWw) 中的敘述，打開 BPF subsystem, **General Setup $\to$ Extensible Scheduling Class**, Kernel hacking $\to$ Compile-time checks and compiler options 的選項，在完成設定後，可以用以下的命令檢查：
```bash
$ rg 'BPF|SCHED|BTF' .config | cut -d ':' -f 3,3
CONFIG_BPF=y
CONFIG_HAVE_EBPF_JIT=y
CONFIG_ARCH_WANT_DEFAULT_BPF_JIT=y
# BPF subsystem
CONFIG_BPF_SYSCALL=y
CONFIG_BPF_JIT=y
CONFIG_BPF_JIT_ALWAYS_ON=y
CONFIG_BPF_JIT_DEFAULT_ON=y
CONFIG_BPF_UNPRIV_DEFAULT_OFF=y
CONFIG_BPF_PRELOAD=y
CONFIG_BPF_PRELOAD_UMD=m
CONFIG_BPF_LSM=y
# end of BPF subsystem
# CONFIG_SCHED_CORE is not set
CONFIG_SCHED_CLASS_EXT=y
CONFIG_HAVE_UNSTABLE_SCHED_CLOCK=y
CONFIG_CGROUP_SCHED=y
CONFIG_FAIR_GROUP_SCHED=y
# CONFIG_RT_GROUP_SCHED is not set
CONFIG_SCHED_MM_CID=y
# CONFIG_CGROUP_BPF is not set
# CONFIG_SCHED_AUTOGROUP is not set
CONFIG_SCHED_OMIT_FRAME_POINTER=y
CONFIG_SCHED_CLUSTER=y
CONFIG_SCHED_SMT=y
CONFIG_SCHED_MC=y
CONFIG_SCHED_MC_PRIO=y
CONFIG_SCHED_HRTICK=y
# CONFIG_CPU_FREQ_DEFAULT_GOV_SCHEDUTIL is not set
CONFIG_CPU_FREQ_GOV_SCHEDUTIL=y
CONFIG_MQ_IOSCHED_DEADLINE=y
CONFIG_MQ_IOSCHED_KYBER=y
# CONFIG_IOSCHED_BFQ is not set
CONFIG_NETFILTER_BPF_LINK=y
CONFIG_NET_SCHED=y
# CONFIG_NET_CLS_BPF is not set
# CONFIG_NET_ACT_BPF is not set
# HID-BPF support
# end of HID-BPF support
CONFIG_USB_EHCI_TT_NEWSCHED=y
CONFIG_DEBUG_INFO_BTF=y
CONFIG_PAHOLE_HAS_SPLIT_BTF=y
CONFIG_PAHOLE_HAS_BTF_TAG=y
CONFIG_DEBUG_INFO_BTF_MODULES=y
# CONFIG_MODULE_ALLOW_BTF_MISMATCH is not set
# CONFIG_SCHED_STACK_END_CHECK is not set
CONFIG_SCHED_DEBUG=y
CONFIG_SCHED_INFO=y
CONFIG_SCHEDSTATS=y
# CONFIG_SCHED_TRACER is not set
CONFIG_PROBE_EVENTS_BTF_ARGS=y
CONFIG_BPF_EVENTS=y
# CONFIG_TEST_BPF is not set
```
設定完之後，我們就可以開始編譯、安裝 Linux 核心並重新開機，就有了可以執行 sched_ext 排程器的環境
```bash
$ make LLVM=1 CC=clang-18 -j`nproc`
$ sudo make install
$ sudo reboot
```
重新開機後，我們可以試著執行 `scx_rustland` 專案：
```bash
$ git clone https://github.com/sched-ext/scx
$ cd scx
$ meson setup build --prefix ~
$ meson compile -C build
$ meson install -C build
$ cd scheds/rust/scx_rustland
$ sudo cargo run --release
```
預期看到以下輸出：
```
$ sudo cargo run --release
Compiling scx_rustland v0.0.7 (/home/otteryc/linux2024/scx/scheds/rust/scx_rustland)
Finished release [optimized] target(s) in 4.24s
Running `target/release/scx_rustland`
05:55:56 [INFO] libbpf: struct_ops rustland: member cgroup_init not found in kernel, skipping it as it's set to zero
05:55:56 [INFO] libbpf: struct_ops rustland: member cgroup_exit not found in kernel, skipping it as it's set to zero
05:55:56 [INFO] libbpf: struct_ops rustland: member cgroup_prep_move not found in kernel, skipping it as it's set to zero
05:55:56 [INFO] libbpf: struct_ops rustland: member cgroup_move not found in kernel, skipping it as it's set to zero
05:55:56 [INFO] libbpf: struct_ops rustland: member cgroup_cancel_move not found in kernel, skipping it as it's set to zero
05:55:56 [INFO] libbpf: struct_ops rustland: member cgroup_set_weight not found in kernel, skipping it as it's set to zero
05:55:57 [INFO] RustLand scheduler attached - 8 CPUs
05:55:58 [INFO] min_vruntime=10000001 max_vruntime=10000001 delta=0us slice=5000us
05:55:58 [INFO] tasks=3
05:55:58 [INFO] nr_user_dispatches=3 nr_kernel_dispatches=210
05:55:58 [INFO] nr_cancel_dispatches=0 nr_bounce_dispatches=0
05:55:58 [INFO] nr_running=1 nr_waiting=0 [nr_queued=0 + nr_scheduled=0]
05:55:58 [INFO] nr_failed_dispatches=0 nr_sched_congested=0 nr_page_faults=0 [OK]
05:55:58 [INFO] Running tasks:
05:55:58 [INFO] core 0 cpu 0 pid=[self]
05:55:58 [INFO] core 0 cpu 4 pid=0
05:55:58 [INFO] core 1 cpu 1 pid=0
05:55:58 [INFO] core 1 cpu 5 pid=0
05:55:58 [INFO] core 2 cpu 2 pid=0
05:55:58 [INFO] core 2 cpu 6 pid=0
05:55:58 [INFO] core 3 cpu 3 pid=0
05:55:58 [INFO] core 3 cpu 7 pid=0
```
### FIFO 排程器的研究
接下來，我們以最簡單的 FIFO 排程策略為例，以 Top-Down 方式扼要說明如何藉助 sched_ext 專案，以 Rust 語言撰寫的使用者層級 CPU 排程器：
在排程器初始化階段， `scx_rlfifo` 會先建立一個 `BpfScheduler`
```rust
let bpf = BpfScheduler::init(
5000, // slice_ns (default task time slice)
topo.nr_cpu_ids() as i32, // nr_cpus (max CPUs available in the system)
false, // partial (include all tasks if disabled)
0, // exit_dump_len (buffer size of exit info)
true, // full_user (schedule all tasks in user-space)
false, // low_power (low power mode)
false, // fifo_sched (enable BPF FIFO scheduling)
false, // debug (debug mode)
)?;
```
在初始化階段完成之後，除非收到 SIGINT 訊號或 BPF 排程器結束， 使用者層級 CPU 排程器將停留在無窮迴圈中。並在排程決定完成之後，讓出 (yield) CPU 資源，等待 BPF Scheduler 喚醒，進行下一個 Scheduling cycle
而作為最簡單的排程策略並得益於 scx 專案提供的高度抽象介面， [scx_rlfifo](https://github.com/sched-ext/scx/blob/main/scheds/rust/scx_rlfifo/src/main.rs) 僅僅使用了約 150 行程式碼就完成了一個能正常運作的使用者層級 CPU 排程器，其排程實作如下：
```rust
// Get queued taks and dispatch them in order (FIFO).
match self.bpf.dequeue_task() {
Ok(Some(task)) => {
// task.cpu < 0 is used to to notify an exiting task, in this
// case we can simply ignore the task.
if task.cpu >= 0 {
let mut dispatched_task = DispatchedTask::new(&task);
// Allow to dispatch on the first CPU available.
dispatched_task.set_flag(RL_CPU_ANY);
let _ = self.bpf.dispatch_task(&dispatched_task);
// Give the task a chance to run and prevent overflowing the dispatch queue.
std::thread::yield_now();
}
}
Ok(None) => {
// Notify the BPF component that all tasks have been scheduled and dispatched.
self.bpf.update_tasks(Some(0), Some(0));
break;
}
Err(_) => {
break;
}
}
```
簡而言之，每當使用者層級 CPU 排程器被喚醒，會從 `queued` (`BPF_MAP_TYPE_RINGBUF`, 資料型態為 `queued_task_ctx`) 中讀取需要被排程的工作，並將之放入 `dispatched` (BPF_MAP_TYPE_USER_RINGBUF, 資料型態為 `dispatched_task_ctx`）之中，供核心讀取。
### 簡易的排程器設計
> [GitHub](https://github.com/otteryc/scx/tree/linux2024/scheds/rust/scx_two_level_queue)
本專題將以一個簡單的 Two-level Queue Scheduling 為例，說明如何在 sched_ext/scx 的助力下，設計一套簡易的排程器
設計概念：
* 當 $NICE \lt 0$ 時，執行 FIFO
* 當 $NICE \geq 0$ 時，執行 Round Robin (Time Quantum = 100 ms)
:::danger
統一術語，使用 timeslice
:::
#### 獲得 NICE Value
由於 `QueuedTask` 結構體中，並不包含 Linux 核心定義的 `task_struct` ，沒有辦法直接得到單一行程的優先程度。
```rust
// Task queued for scheduling from the BPF component (see bpf_intf::queued_task_ctx).
#[derive(Debug, PartialEq, Eq, PartialOrd, Clone)]
pub struct QueuedTask {
pub pid: i32, // pid that uniquely identifies a task
pub cpu: i32, // CPU where the task is running (-1 = exiting)
pub sum_exec_runtime: u64, // Total cpu time
pub nvcsw: u64, // Voluntary context switches
pub weight: u64, // Task static priority
cpumask_cnt: u64, // cpumask generation counter (private)
}
```
不過，作為使用者層級 CPU 排程器，基於 scx 專案所開發的排程器有強大的 crate.io 套件庫支援，可以藉由 pid 從 procfs 獲得 NICE 值。
```bash
$ cargo add procinfo
```
使用的方法也十分容易：
```rust
use procinfo::pid::stat;
let nice = stat(pid).unwrap();
```
#### FIFO/RR 的實作
根據恐龍書中的描述：
> The performance of the RR algorithm depends heavily on the size of the time quantum. At one extreme, if the time quantum is extremely large, the RR policy is the same as the FCFS policy.
這樣會讓實作變得簡單：我們只需要在 FIFO ($NICE \lt 0$) 的情況的 time slice 調整的足夠大，並且在 RR 時允許搶佔即可。
```rust
let _ = dispatched_task.set_flag(RL_CPU_ANY);
let _ = dispatched_task.set_flag(RL_PREEMPT_CPU.into());
let _ = if nice < 0 {
// FIFO
self.served_fifo += 1;
dispatched_task.set_slice_ns(u64::MAX)
} else {
// RR
self.served_rr += 1;
};
```
#### TODO: 驗證演算法正確性
## 撞牆筆記
:::danger
將下方內容整合到對應的環境設定指引中。
:::
### Cargo.toml
在進行 Rust 語言的開發時，如果沒有顯式的在專案中註明使用 2021 edition 的 Rust 語言，會預設使用 2015 edition，造成 use crate 語法的差異，務必留意。
### libbpf 更新
在專題截止前夕，趕進度的臺灣時間凌晨 1:00 ， [libbpf 的 GitHub repo](https://github.com/libbpf/libbpf) fetch 了來自 kernel tree 的 [commit](https://github.com/libbpf/libbpf/commit/be998aa3d41e1f5f83e3e69a71746b785e0a7b8b)，其中包含新增 `bpf_map_skeleton` 的結構體成員 `link`。
```diff
struct bpf_map_skeleton {
const char *name;
struct bpf_map **map;
void **mmaped;
+ struct bpf_link **link;
};
```
這會導致 scx 專案編譯失敗，在經過一夜的惡補 meson 的編譯流程以及除錯之後，在早上終於發現問題，並提交 [Pull Request(#396)](https://github.com/sched-ext/scx/pull/396)，並於是日下午獲得接受。
而後，發現套用 be998aa 雖然能夠成功編譯，卻在其他開發者測試時會造成 Segmentation Fault ， [PR#396](https://github.com/sched-ext/scx/pull/396) 後於當天晚上由 [PR#400](https://github.com/sched-ext/scx/pull/400) revert，並更改 bpftool 版本。
:::danger
本課程的「核心」都指作業系統核心，避免誤用該詞彙到其他場景。下方可說：「其關鍵問題在於」
:::
其<s>核心</s> 原因在於， bpftool 的 GitHub repo 曾經使用 force-push ，造成 meson script 所指向的 commit ID 消失，進而自動使用了最新版本的 bpftool ，以及 meson script 所指定的 libbpf 版本，最終發生了兩者版本上的不一致。把 libbpf commit ID 同步更新到最新之後，雖然能夠成功編譯，但是 scx 專案所寫入 ring buffer 的資料型態仍然是舊的 `bpf_map_skeleton`，致使 segmentation fault 的發生。
### SCHED_CLASS_EXT
如果在 git clone 完最新的 repo 並且 checkout 到正確的 tag 之後，仍然出現以下錯誤，
```
sched_ext_ops.dump() missing, kernel too old?
```
請先別急著懷疑是不是真的是核心版本過於老舊，很有可能是根本沒打開 sched_ext 的核心編譯選項。
Sign in with Wallet
Connect another wallet