---
tags: LINUX KERNEL, LKI
---

# [Linux 核心設計](https://beta.hackfoldr.org/linux/): 發展動態回顧

Copyright (**慣C**) 2020, 2022 [宅色夫](http://wiki.csie.ncku.edu.tw/User/jserv)
==[直播錄影](https://youtu.be/nUXxdgszJAQ)==

## 點題

本講座將以 Thorsten Leemhuis 在 FOSDEM 2020 開場演說 "[Linux kernel – Solving big problems in small steps for more than 20 years](https://youtu.be/WsktXXMOg1k)" ([slides](https://archive.fosdem.org/2020/schedule/event/linux_kernel/attachments/slides/3890/export/events/attachments/linux_kernel/slides/3890/Fosdem_Leemhuis_Kernel_Steps.pdf)) 為主軸，嘗試歸納自 21 世紀第一年開始的 Linux 核心 2.4 版到如今的 5.x 版，中間核心開發者如何克服 SMP (Symmetric multiprocessing), scalability, 及各式硬體架構和周邊裝置支援等難題，過程中提出全面移除 BKL (Big kernel lock)、實作虛擬化技術 (如 Xen 和 KVM)、提出 namespace 和 cgroups 從而確立容器化 (container) 的能力，再來是核心發展的明星技術 eBPF 會在既有的基礎之上，帶來 XDP 和哪些令人驚豔的機制呢？又，Linux 核心終於正式納入發展十餘年的 PREEMPT_RT，使得 Linux 核心得以成為硬即時的作業系統，對內部設計有哪些衝擊？AIO 後繼的 io_uring 讓 Linux 有更優雅且高效的非同步 I/O 存取，我們該如何看待？
> 前導議程: [Linux 核心設計: 作業系統術語及概念](https://hackmd.io/@sysprog/linux-concepts)

## FOSDEM

Free and Open source Software Developers' European Meeting (簡稱 FOSDEM）是個專為自由軟體及開源軟體開發者而設的週年會議，通常都一連兩日，包括有講座、導修工作室、攤位等。會議由比利時的布魯塞爾自由大學及一般志願人士籌備，被視為全歐洲、甚至全世界最優秀的自由軟體及開源軟體活動。所有會議的活動都可免費參加。

這個會議在 2001 年開始時，本來稱為 Open source Software Developers' European Meeting，2003 年加入 Free Software 開發者的參與，而改用今日的名稱。
> Louie Lu 的 [FOSDEM 紀錄](https://blog.louie.lu/tag/fosdem/)
> [OCF: 系統軟體走向國際](https://ocf.tw/p/sysprogram/): 您的善心捐款即是熱血學子在國際舞台發光發熱的盤纏

## Linux 2.4

Linux 核心 [v2.4.0](https://mirrors.edge.kernel.org/pub/linux/kernel/v2.4/) 在 2001 年 1 月 4 日釋出
:::spoiler
原始程式碼壓縮檔案比較 (gzip)
* [linux-2.4.0](https://mirrors.edge.kernel.org/pub/linux/kernel/v2.4/) 佔 23 MB
* [linux-5.6.14](https://cdn.kernel.org/pub/linux/kernel/v5.x/) 佔 166 MB

[Linux 核心原始程式碼和 Torvalds 家族成員的關聯](https://hackmd.io/@sysprog/revolution-os-note#Linus-Torvalds-%E5%AE%B6%E5%BA%AD%E6%88%90%E5%93%A1%E8%88%87-Linux-%E6%A0%B8%E5%BF%83%E7%A8%8B%E5%BC%8F%E7%A2%BC)
:::

[Version 2.4 of the LINUX KERNEL--Why Should a System Administrator Upgrade?](https://www.informit.com/articles/article.aspx?p=20667)

1996 年 6 月 9 日釋出的 Linux `v2.0`，後續變更包含:
* 1999 年 1 月 25 日 Linux `v2.2.0`（1,800,847 行程式碼）
* 1999 年 12 月 18 日針對 Linux `v2.2.13` 的 IBM 大型電腦修補程式釋出，允許 Linux 核心用於企業級機器
* 2001 年 1 月 4 日 Linux `v2.4.0`（3,377,902 行程式碼）
* 2003 年 12 月 17 日 Linux `v2.6.0`（5,929,913 行程式碼）
* 自 2004 年開始，釋出過程發生變化，新核心每隔 2-3 個月定期釋出，編號為 `2.6.0`, `2.6.1`，直到 `2.6.39`
* 2011 年 7 月 21 日 Torvalds 宣布釋出 Linux `v3.0`，自此「奇數版本號碼表示開發中、偶數核心版本表示穩定版本」的規則就此打破

Linux 核心差一點就走進如同 Microsoft Windows 的「為需求而升級」的發展道路從而偏離原先 Linux 核心「只提供機制不提供策略」的道路。
* Linux 2.4 時代，核心提供一個名為 `khttpd` 的核心內部的 web 伺服器 (in-kernel httpd)。當時 Linux 的效能不夠好，且無法有效利用 SMP 的優勢、thread 的實作仍很很拙劣 (不是 NPTL)，很多方面沒有達到 POSIX 的高效指標，因此當時的開發者就鑽進解決效能瓶頸的牛角尖上
* 有鑑於 Apache 伺服器多半在 Linux 上運作，且 web 伺服器是如此普遍也重要，因此效能瓶頸往往是 Apache 本身，因此面對這個如此「特化」又不得不理會的需求，開發者們只好就事論事地將 web 伺服器單獨加速，也就是在核心內部中實做一個 web 加速器
- 如果按照這條路走下去，Linux 還會把圖形處理搬到核心內部，一如 Windows NT 所為
- 不過 Linux `v2.6` 以來，核心發展重新找到自己的方向，沒必要透過特化需求去克服局部的效能瓶頸
* Linux-2.6 核心的發展策略是基於整體思維，像是新的排程演算法 (`O(1)` scheduler 和後續的 CFS)，又像是 linux-2.6.17 中的 splice 和 tee 系統呼叫，都讓 `khttpd` 沒有存在的必要

## SMP 支援

Linux `v2.0` 有項重要變革是開始支援 SMP (儘管效率不佳)

1997 年，為電腦《鐵達尼號》(Titanic) 製作電腦特技效果的 [Digital Domain](http://digitaldomain.com/) 公司，在製作過程中部署 105 台執行 Red Hat Linux 的 Alpha 電腦 (另有二百多台 SGI 及 55 台 Windows NT)。

Linux 在 1995 年，即可在 i386 以外的平台運作，包含 Alpha
* [Porting Linux to the DEC Alpha: Infrastructure](http://www.linuxjournal.com/article/1044)
* Alpha 處理器的命名規則是 21x64: `21` 表示 21 世紀、`64` 表示完整 64 位元的設計，例如 1995 年推出的 [Alpha 21164](https://en.wikipedia.org/wiki/Alpha_21164) 是

1997 年 12 月 19 日電影《鐵達尼號》(Titanic) 在全球各地上映，獲得空前成功。該片是第一部達到 10 億美元票房大關的電影，全球票房收入達 18 億，並保持電影票房收入排行第一位，是隨後 12 年來最賣座的電影。直至 2010 年 1 月《阿凡達》的上映，導演 James Cameron 才打破自己在《鐵達尼號》的紀錄。

[Digital Domain](http://digitaldomain.com/) 公司製作不少賣座電影，像是《阿波羅 13 號》、《天崩地裂》、《第五元素》等等。當導演 James Cameron 把《鐵達尼號》的視覺特效交給 [Digital Domain](http://digitaldomain.com/) 公司時，工程團隊面臨前所未有的挑戰：《鐵達尼號》的動畫特效伴隨著一個體型相當龐大且複雜的物件模型，換言之，需要快速且穩定的電腦系統，才可負荷如此複雜且大量的視覺特效運算。
* 為了以最少的成本換取最高的計算能力，Digital Domain 公司向當時執工作站牛耳的 DEC 公司買下 160 部 Alpha 工作站電腦
* 儘管多數的 DEC Alpha 使用者偏好採用 Digital UNIX 或 Microsoft Windows NT 作業系統，但 [Digital Domain](http://digitaldomain.com/) 公司卻選擇在其中的 105 部新機器上安裝 Red Hat Linux 作業系統，事後證實是相當划算的投資
* 許多動畫特效公司紛紛採用 Linux 搭配價格低廉且高效的硬體

延伸閱讀:
* [Linux Helps Bring Titanic to Life](https://www.linuxjournal.com/article/2494)
* [Digital Domain: TITANIC](https://www.digitaldomain.com/work/titanic/)
* [Red Hat Sinks Titanic](https://www.redhat.com/en/about/press-releases/press-titanic)
* [Industrial Light and Magic](https://www.linuxjournal.com/article/6011)
* [MaterialX Joins the Academy Software Foundation as a Hosted Project](https://www.aswf.io/blog/materialx-joins-the-academy-software-foundation-as-a-hosted-project/)

Linux 2.4 在 SMP 的效率問題在哪？
* [Big Kernel Lock](https://kernelnewbies.org/BigKernelLock): 鎖定整個 Linux 核心的機制，透過 `lock_kernel()` 與 `unlock_kernel()` 函式。這是為了支援多處理器，暫時引進的鎖定機制，已在 `v2.6.39` (2011 年，在 Linux SMP 支援引入的 15 年後!) 徹底清除。
* `v2.6.6` still had about 500 lock_kernel() calls
* [commit](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=4ba8216cd90560bc402f52076f64d8546e8aefcb)
* [Killing the Big Kernel Lock](https://lwn.net/Articles/380174/)
* BKL 用於保護整個核心，而 spinlock 用於保護非常特定的某一共享資源。行程 (process) 持有 BKL 時允許發生排程。實作機制：在執行`schedule` 時，`schedule` 將檢查行程是否擁有 BKL，若有，它將被釋放，以致於其它的行程能夠獲得該 lock，而當輪到該行程執行之際，再讓它重新獲得 BKL。注意：在持有 spinlock 期間不會發生排程。
* 整個核心僅有一個 BKL

延伸閱讀:
* [並行和多執行緒程式設計系列講座](https://hackmd.io/@sysprog/concurrency)
* [Linux 核心設計: 淺談同步機制](https://hackmd.io/@sysprog/linux-sync)
* [Linux 核心設計: 多核處理器和 spinlock](https://hackmd.io/@sysprog/multicore-locks)

[Big Kernel Lock](https://kernelnewbies.org/BigKernelLock) 是個顯著的問題，但 scalability 並非單一議題，需要顧及各種議題。

延伸閱讀:
* [Linux 核心設計: Scalability 議題](https://hackmd.io/@sysprog/linux-scalability)
* [從 CPU cache coherence 談 Linux spinlock 可擴展能力議題](https://hackmd.io/@sysprog/linux-spinlock-scalability)

[Linux 5.5's Scheduler Sees A Load Balancing Rework For Better Perf But Risks Regressions](https://www.phoronix.com/scan.php?page=news_item&px=Linux-5.5-Scheduler)
> When testing on a dual quad-core ARM64 system they found the performance ranged from less than 1% to upwards of 10% for the Hackbench scheduler test. With a 224-core ARM64 server, the performance ranged from less than 1% improvements to 12% better performance with Hackbench and up to 33% better performance with Dbench.

## 虛擬化

[Embedded Virtualization applied in Mobile Devices](https://www.slideshare.net/jserv/mobile-virtualization)

> 出處: [Xen Directions](http://www-archive.xenproject.org/files/xensummit_germany09/IanPratt.pdf), 2009

> 出處: [Overview of Xen for ARM Servers](https://www.slideshare.net/linaroorg/lcu14-308-xen-project-for-arm-servers)

:::warning
Xen problem:
support for running as Host (Dom0) or Guest (DomU) was out-of-tree
:::

2017 年第四季，AWS 支援 KVM 作為虛擬化架構，自此 KVM 可說是席捲 Linux 虛擬化技術生態。在 AWS 啟動的 2006 年，Xen 是當時最成熟、開放原始碼的 Linux 虛擬化引擎技術。因此，AWS 在早期採用 Xen，成為其 [EC2](https://aws.amazon.com/ec2/) 的底層基礎。

KVM 全名是 Kernel-based Virtual Machine，最早是以色列新創公司 [Qumranet](https://en.wikipedia.org/wiki/Qumranet) (創立於 2005 年) 發表的開放原始碼專案，在 2006 年下半收錄於 Linux 核心，自此大幅強化 KVM 的影響力。

2008 年，Red Hat 以 1 億 7 百萬美金收購 KVM 背後的 Qumranet 公司，藉此擴展 Red Hat 對於虛擬技術的支援。得益於 KVM 的活躍發展，2011 年啟動的 Google Cloud 從一開始就採用 KVM 引擎。Qumranet 核心人物 Avi Kivity 在公司成功賣給 Red Hat 後，沒閒著，後來開創新一代的分散式資料庫技術公司 [ScyllaDB](https://www.scylladb.com/)。

世界上最大的科技公司不約而同選擇在以色列設立研發中心，且成果卓著，例如，Intel x86 家族中比較重要的兩代 CPU: Sandy Bridge 和 Ivy Bridge 都是由 Intel 以色列的研發中心研發的，藍色巨人 IBM 也早在 1970 年代就在以色列設立龐大的研發中心，且成果斐然。

虛擬化技術歷史悠久，早在 1967 年，第一代的硬體虛擬化技術就由 IBM 提出。在大型主機中實作以 CP/CMS 為代表的虛擬化技術，直到 2006 年，Intel 和 AMD 才分別在各自的處理器中加入「有限」的硬體虛擬化特性，分別稱為，Intel VT-x 和 AMD-V。與大型機所採用的專為虛擬化設計的處理器不同，從 PC 起家者以 Intel 為代表的 x86 家族的處理器生來就不是為虛擬化設計。要在 x86 家族處理器上完全向後相容的同時加入硬體虛擬化特性，無疑成為一個挑戰，硬體層面實作較為困難，導致軟體層面的實作複雜度也隨之水漲船高。

Linux 核心中，虛擬化相關程式碼，x86 架構部分的程式碼數量是 S390 架構的 7 倍、PPC 架構的 8 倍、Arm 架構的 4 倍，其複雜度之高從中可見一斑。

Avi Kivity 提出的方案非常清晰且巧妙：聚焦於 Linux 核心，至於User space 部分交給穩定可靠的 Qemu，採用後者作為其使用者層級的入口，而且 KVM 僅僅實現 HVM 功能。以 Avi Kivity 為主的工程師僅僅花了不到一年時間就讓 Linux 社群接受 KVM 的設計方案並通過程式碼審查，最終於 2006 年 10 月合併進入 Linux `v2.6.20`。

:::warning
why did KVM succeed?
1. KVM had a better, more flexible, and future-proof design built into Linux, not underneath it
2. reuse things already there that suited Linux more and left it in control which obviously is in the interest of Linux developers
:::
> 註: underneath 語意與 under 相近，但更強烈

[Cloud-Hypervisor](https://github.com/cloud-hypervisor/cloud-hypervisor) 是 Intel 以 KVM 為基礎，開發出來的嶄新 Virtual Machine Monitor (VMM)，這項虛擬化建設著眼於資源配置侷限但又廣泛部署的雲端運算環境，採用 Rust 程式語言打造。Cloud-Hypervisor 由於自身定位，不考慮舊有通行的硬體支援，相反地，主要支援 VirtIO 為基礎的 para-virtualized device。

## DPDK (Data Plane Development Kit)

一言以敝之: "Kernel-bypass networking"

kernel bypassing 是達成 low latency 網路的常見手法，特別在高速科學運算、[低延遲資本市場交易](https://en.wikipedia.org/wiki/Low_latency_(capital_markets))，和雲端運算基礎建設中用到。

為何需要 kernel bypassing？

一般 app-to-wire-to-app 時，Linux 核心的 TCP 或 UDP 可達到 6us。cache-to-wire-to-cache 可達到 0.8 us (在 Intel Ivy Bridge, Exablaze 10G） —— 這些延遲已經很低，多數網路延遲其實發生於應用軟體層面。要降低應用軟體層級的延遲，有個激進的手段是繞過作業系統的管理，從而避免延遲：直接使應用程式能夠操作、寫入網路介面緩衝區裡的資料，甚至接管網路介面控制器。

NIC 是 network interface controller 的簡稱，通俗的說法是「網路卡」。low latency 網路卡的製造商有 Mellanox（Mellanox Messaging Accelerator, VMA; 2020 年 4 月 NVIDIA 正式完成 Mellanox 收購以強化資料中心業務）, Solarflare ([OpenOnload](https://www.openonload.org/)), Exablaze(exasock), Chelsio (WireDirect), Myricom (DBL) 等等，括號裡的是Transparent kernel-bypass TCP/IP stack。

Transparent kernel-bypass TCP/IP 的實作手法:
1. 以 LD_PRELOAD 攔截 libc 呼叫，確定被傳遞的 file descriptor 是個需要被加速的 socket。若需要被加速，直接把這個呼叫轉包到使用者層級的網路堆疊 (userspace TCP/IP stack）
2. 網路卡被直接映射到使用者模式，以處理封包的傳遞和接收。這是最簡潔且安全的解決方案，倘若硬體支援虛擬網路介面，那就直接發送到 virtual interfaces。

延伸閱讀:
* [Kernel-bypass networking for fun and profit](https://youtu.be/noqSZorzooc), Matthew Chapman
* [Kernel bypass](https://blog.cloudflare.com/kernel-bypass/), CloudFlare
* [Understanding DPDK](https://www.slideshare.net/garyachy/dpdk-44585840)

## XDP: eXpress Data Path

> 如果封包發現錯誤，則在 protocol stack 前，就會判斷是否要繼續處理或丟棄
延伸閱讀: [Linux 核心設計: 透過 eBPF 觀察作業系統行為](https://hackmd.io/@sysprog/linux-ebpf)

> * Fill ring (to kernel) / Rx ring (from kernel)
> * Tx ring (to kernel) / Completion ring (from kernel)
> * Copy mode (DMA to/from kernel allocated frames, copy data to user)
> * Zero-copy mode (DMA to/from user allocated frames)

[The Path to DPDK Speeds for AF XDP](https://linuxplumbersconf.org/event/2/contributions/99/attachments/98/116/lpc18_pres_af_xdp_perf-v3.pdf) / [錄影](https://youtu.be/JmGfJok32Kw)

AF 表示 [address_families](http://man7.org/linux/man-pages/man7/address_families.7.html)

## AIO

Synchronous / Asynchronous I/O：在從/向核心空間讀取/寫入資料 (i.e. **實際進行 I/O 操作**) 的過程，使用者層級的行程是否會被 **blocked**。
- Synchronous I/O：從/向核心空間讀取/寫入資料 的過程，使用者層級的行程會被 blocked
- 例如 [read](http://man7.org/linux/man-pages/man2/read.2.html), [recvfrom](http://man7.org/linux/man-pages/man2/recv.2.html)
- Asynchronous I/O：從/向核心空間讀取/寫入的過程交由核心內部處理。核心複製完資料後，再通知使用者層級的行程。這中間使用者層級的行程不會被 blocked。
- 例如 `aio_read()`, `aio_write()`

> 1. 應用程式通知核心執行給定的操作 (Operation)，但應用程式不用等待核心回覆，程式繼續執行
> 2. 核心完成整個操作，包含取得資料、複製到緩衝區後，通知應用程式 (deliver signal specified in `aio_read`)

延伸閱讀:
* [針對事件驅動的 I/O 模型演化](https://hackmd.io/@sysprog/linux-io-model/)
* [Effective System Call Aggregation](https://eecheng87.github.io/ESCA/)

:::info
* UNIX 哲學: Everything is a file.
* Linux 不成文規範: Everything is a file descriptor.
:::

[Faster IO through io_uring](https://www.slideshare.net/ennael/kernel-recipes-2019-faster-io-through-iouring) / [錄影](https://youtu.be/-5T4Cjw46ys)

自 Linux `v5.1` 起引入的 `io_uring` 存在大量以現有 aio 為基礎的程式碼，例如可透過 [eventfd](http://man7.org/linux/man-pages/man2/eventfd.2.html) 或 SIGIO 通知 I/O 事件的完成。

Linux 原本的 AIO 存在以下限制:
1. 最大的限制無疑是只支援 direct AIO。而 `O_DIRECT` 要求 bypass cache 和 size alignemt 等，直接影響很多場景的使用。而對 buffered IO，其表現為同步
2. 即使滿足所有非同步 IO 的規範，有時仍會 blocking，例如，等待 metadata I/O，或儲存裝置的 request slot 正在使用等等
3. 存在額外的開銷：每個 IO request 需要複製 64 + 8 位元組，每個 IO 完成需要複製 32 位元組，這在某些場景下影響很可觀。在使用完成 event 時需要非常小心，否則容易丟失事件。IO 總需要至少 2 個系統呼叫（submit + wait-for-completion)，在 spectre/meltdown 啟用後，效能衝擊很大

延伸閱讀:
* [AIO 的新歸宿：io_uring](https://zhuanlan.zhihu.com/p/62682475)
* [Efficient IO with io_uring](https://kernel.dk/io_uring.pdf)
* [io_uring 共筆](https://hackmd.io/@sysprog/iouring)

## Container

建構在以下 Linux 核心基礎建設:
* namespace
* cgroups
* capabilities
* seccomp

[Containers: cgroups, Linux kernel namespaces, ufs, Docker, and intro to Kubernetes pods](https://youtu.be/el7768BNUPw)

## BPF/cBPF/eBPF

:::warning
run small programs in kernel mode
20 years ago, this idea would likely have been shot down immediately
:::

增加 [bpf](https://man7.org/linux/man-pages/man2/bpf.2.html) 系統呼叫後:

給予核心開發者新的想像:

[Thomas Graf](https://www.infoq.com/presentations/facebook-google-bpf-linux-kernel/) 評論道:
> With BPF, we're starting to implement a microkernel model where we can now dynamically load programs, we can dynamically replace logic in a safe way, we can make logic composable. We're going away from the requirement that every single Linux kernel change requires full consensus across the entire industry or across the entire development community and instead, you can define your own logic, you can define your own modules and load them safely and with the necessary efficiency.


延伸閱讀:
* [Extended BPF: A New Type of Software](https://www.slideshare.net/brendangregg/um2019-bpf-a-new-type-of-software) / [video](https://youtu.be/7pmXdG8-7WU)
* [Linux 核心設計: 透過 eBPF 觀察作業系統行為](https://hackmd.io/@sysprog/linux-ebpf)

## BPF Performance Tools

book: [BPF Performance Tools](http://www.brendangregg.com/bpf-performance-tools-book.html)

## Real-Time

延伸閱讀: [Linux 核心設計: PREEMPT_RT 作為邁向硬即時作業系統的機制](https://hackmd.io/@sysprog/preempt-rt)

[Linux 5.3 已整合 PREEMPT_RT 部分修改](https://lwn.net/ml/linux-kernel/[e-mail]/)

> [source](https://twitter.com/fleming_matt/status/1249453804350734337)

## 不能小看的 `printk`

[Why printk() is so complicated (and how to fix it)](https://lwn.net/Articles/800946/)
> The difficulties with printk() over the years, come down to the tension between non-interference and reliability. Trying to achieve both goals in the same place has been shown not to work, so a better approach would be to split them apart. Non-interference can be addressed by making printk() fully preemptable, making the ring buffer safe in all contexts, and moving console handling to dedicated kernel threads. Reliability, instead, can be achieved by providing a synchronous channel for important messages, an "atomic consoles" concept, and the notion of "emergency messages".

## ZFS, BtrFS, RAID

[ZFS vs. RAID](https://arstechnica.com/gadgets/2020/05/zfs-versus-raid-eight-ironwolf-disks-two-filesystems-one-winner/)

## 核心開發模式

* a new kernel version every 9 or 10 weeks
* each with ~13,500 commits these days
* bringing round about `+650,000` insertions and `-350,000` deletions
- growth: ~1.5 million lines per year

## 導入 Rust 程式語言
[Linux 核心採納 Rust 的狀況](https://hackmd.io/@linD026/rust-in-linux-organize)

## 待整理
* [Fifty years of Unix and Linux advances](https://youtu.be/lYWpZHhaqmk) (FOSDEM 2019)
* [Forgetting the history of Unix is coding us into a corner](https://www.theregister.com/2024/02/16/what_is_unix/) / [Drowning in code: The ever-growing problem of ever-growing codebases](https://www.theregister.com/2024/02/12/drowning_in_code/) (FOSDEM 2024)