2022 年 Linux 核心設計/實作課程期末專題

注意事項

1. 所有專案都該確保在 Linux v5.4+ 運作
2. 所謂的「彙整」，是指能撰寫出完整的技術報告，範例: 位元運算整理 和 基於 C 語言標準研究與系統程式安全議題
3. 專題不僅是課程評分的依據，而且是自己專業的證明，日後可列於個人簡歷
4. 請及早向 授課教師 預約一對一討論，得知專題進行的方式
5. 授課教師將依據學員的投入狀況，指派新的題目 (學員可提案)，或是要求學員重作現有的作業及測驗題
6. 不要自行填入「執行人」，應在與 授課教師 討論後，再行更新
7. 每位學員均獨立進行專題 (除非學員說服授課教師，提供需要二位方可進行的強烈理由)，但一個題目可能有多個執行人

PREEMPT_RT 效能分析和改進

PREEMPT_RT 首先將中斷處理轉化為核心執行緒，保證它不再佔用任意 context，這保證即便中斷被即時行程搶佔，也不會連累無辜地被它佔用核心堆疊的行程，再者，將一般行程使用的 spinlock 改為可以睡眠的 mutex (所謂的 sleeping spinlock)，如此可保證喚醒即時行程後，立即執行該即時行程。PREEMPT_RT 部分的成果已整合進 Linux 核心主幹，不過仍有若干效能議題需要釐清和改進。

• 相關資訊:
  • PREEMPT_RT 作為邁向硬即時作業系統的機制
  • Towards PREEMPT_RT for the Full Task Isolation
• 執行人: OscarShiang
  $\to$ 開發紀錄

Linux 排程器解析和改進

探討 Linux 排程器內部設計，並尋求貢獻程式碼到 Linux 核心的機會

• 相關資訊: Let's Publish a Collaborative e-Book for Linux Kernel
• 執行人: forward-jt
  $\to$ 開發紀錄

Linux 排程器研究

研讀《Demystifying the Linux CPU Scheduler》並改進書中論述和實驗

• 執行人: steven1lung
  $\to$ 開發進度
• 執行人: cantfindagoodname
  $\to$ 開發進度

BMQ 排程器研究

Project C 提供 BMQ (Bit Map Queue)，著重於降低高互動性任務 (例如 Linux 桌面應用程式) 的排程延遲 (scheduling latency)。本專案嘗試量化 BMQ 表現，並探討其內部原理，過程中也會比較 BORE 一類的排程器改進方案。

• 相關資訊
  • BORE (Burst-Oriented Response Enhancer) CPU Scheduler，是 CachyOS 預設的 CPU 排程器
  • Reducing CPU scheduler latency in Linux
  • Reducing latency spikes by tuning the CPU scheduler
• 執行人: SmallHanley
  $\to$ 開發紀錄

vwifi 虛擬無線網路裝置驅動程式和實驗環境

vwifi 是個程式碼約五百行，具體而微的 WiFi 裝置驅動程式，採用 cfg80211 框架。目前 vwifi 支援 scan, connect, disconnect 等 cfg80211 的介面操作，並得以正確處理 Tx/Rx 封包。

• 執行人: rickywu0421
  $\to$ 開發記錄

改進 Linux 核心字串處理函式

Linux 核心儘管已有大量開發者投入，但仍存在改進空間，例如第 8 週隨堂測驗展示 memchr 的實作可藉由 SWAR 技巧予以改進，初步可帶來 4 倍效能提升。這當然是可對 Linux 核心貢獻的機會。

• 執行人: arthurchang09
  $\to$ 開發紀錄

改進 Linux 核心的 lib/sort.c

解釋 Linux 核心的 lib/sort.c 現有的 bottom-up heap sort 實作，並尋求效能改進，例如 hybrid quick sort 的引入

• 相關資訊: Bottom-up Heapsort
• 執行人: Uduru0522

simplefs

為了探索 Linux VFS (virtual file system) 介面及檔案系統實作機制，我們從無到有撰寫一個運作於 Linux 核心模式中的精簡檔案系統，原始程式碼約一千餘行，支援基本的檔案和目錄處理，同時也考慮到權限和並行處理的議題。

• 相關資訊:
  • 開發紀錄 1
  • 開發紀錄 2
  • Issue #20
• 執行人: freshLiver
  $\to$ 開發紀錄

打造 Linux 虛擬攝影機裝置驅動程式

vcam 是個針對 Linux 核心開發的虛擬攝影機裝置，全部程式碼僅 1 千 5 百行，從而可理解 V4L2 (video fro Linux APIs, version 2) 的使用和 Linux 多媒體架構。開發一個虛擬的攝影機裝置除了理解 Linux 核心設計外，也有資訊安全的幫助，例如你可以安插相關程式碼，紀錄有哪些應用程式偷偷啟動攝影機，但過程中又不會揭露真正的隱私。

• 相關資訊:
  • 2020 年開發紀錄
  • 2021 年開發紀錄
• 執行人: kevinshieh0225
  $\to$ 開發紀錄

/dev/mem 研究

編撰 Linux 核心的 /dev/mem 裝置，強化 eBPF, crash 等工具的運用，目標是「成為電腦的主人」 —— 想改哪段記憶體就動手變更

• 相關資訊: 開發紀錄
• 執行人: vacantron
  $\to$ 開發紀錄

改進 mimalloc

mimalloc 是 Microsoft Research 主導的開放原始碼專案，旨在提出更輕量且更有效率的記憶體管理器 (即 malloc/free 等函式) 的實作。

• 相關資訊:
  • Brief History of Free List Sharding
  • IsoAlloc Performance
  • 2021 年開發紀錄
• 執行人: oucs638
  $\to$ 開發紀錄
• 執行人: hankluo6
  $\to$ 開發紀錄

高效網頁伺服器

探討從無到有打造 Linux 平台的高效能網頁伺服器，涵蓋是否該將伺服器實作於 Linux 核心內部、並行處理、I/O 模型、epoll、Reactor pattern，和 Web 伺服器在事件驅動架構的考量。

• 相關資訊:
  • sysprog21/timeout: Tickless Hierarchical Timing Wheel
  • 2020 年開發紀錄 / GitHub
  • 2021 年開發紀錄
• 執行人: blueskyson
  $\to$ 開發紀錄
• 執行人: tommy2234
  $\to$ 開發紀錄

cserv 高效網頁伺服器的分析和改進

cserv 展現 event-driven, non-blocking I/O Multiplexing (主要是 epoll), shared memory, processor affinity, coroutine, context switch, UNIX signal, dynamic linking, circular buffer, hash table, red-black tree, atomic operations 等議題的實際應用

• 相關資訊: lwan / note
• 執行人: Xx-oX
  $\to$ 開發紀錄

seHTTPd 改進

• 執行人: jim12312321
  $\to$ 開發紀錄
• 執行人: haoyu0970624763
  $\to$ 開發紀錄

kecho 改進

• 執行人: eric88525
  $\to$ 開發紀錄

kHTTPd 改進

擴充 kHTTPd，使其具備現代網頁伺服器的經典特色，並運用 Linux 核心的機制，例如使用 RCU 管理 HTTP 連線

• 相關資訊:
  • Tempesta FW: 在現有的 Linux TCP/IP 堆疊上建構 Web 加速器
  • http-server-rcu: 以 RCU 管理連線
  • kws: 參照其待辦事項
• 執行人: Risheng1128
  $\to$ 開發紀錄
• 執行人: YiChianLin
  $\to$ 開發紀錄
• 執行人: zoanana990
  $\to$ 開發紀錄

ESCA: 針對事件驅動伺服器提出的系統呼叫加速方案

• 相關資訊
  • Effective System Call Aggregation (ESCA)
• 執行人: yaohwang99
  $\to$ 開發紀錄

NVIDIA 開放原始碼 GPU 核心模組的研究和改進

NVIDIA 以 GPL/MIT 授權發布針對 Linux 核心的 GPU 模組原始程式碼: open-gpu-kernel-modules

• 執行人: ccs100203
  $\to$ 開發紀錄

simrupt 研究和改進

simrupt 專案名稱由 simulate 和 interrupt 二個單字組合而來

• 作用是模擬 IRQ 事件，並展示以下 Linux 核心機制的運用:
  • irq
  • softirq
  • tasklet
  • workqueue
  • kernel thread
  • kfifo
  • memory barrier
• 相關資訊:
  • 2021q3 Homework (simrupt)
• 執行人: Build-A-Moat
  $\to$ 開發紀錄
• 執行人: jimmy-liu1021

使用 eBPF 實作 Transparent Proxy

以 socket-acceleration-with-ebpf 為基礎，實作 Transparent Proxy

• 執行人: shawn5141
  $\to$ 開發紀錄

kvm-host 的改進

KVM 可將 Linux 核心轉為 type-2 hypervisor，結合硬體的虛擬化支援，使得 host machine 上可以執行多個獨立的虛擬環境，稱為 guest 或者 virtual machine。由於 KVM 直接提供 CPU 和記憶體的虛擬化，guest os 的 CPU 指令不需要額外經過軟體的 decode，而是直接交給硬體進行處理，因此可以有效的提高運行速度。而結合軟體 (例如 KVM 搭配 QEMU) 模擬 CPU 和記憶體以外的裝置後，guest OS 便可以被完整地支援在 host OS 上載入並執行。kvm-host 則是建構在 KVM 基礎上的虛擬機器實作，可載入 Linux 核心和相關應用程式。

• 相關資訊:
  • KVM
• 執行人: ray90514
  $\to$ 開發紀錄

〈每位程式開發者都該有的記憶體知識〉翻譯和校訂

本文翻譯自 Ulrich Drepper 於 2007 年撰寫的論文《What Every Programmer Should Know About Memory》(版次: 1.0)

• 相關資訊
  • 現代處理器設計: Cache 原理和實際影響
  • CPU Cache 原理探討
  • prefetch 背景知識簡略整理
  • Random and sequential
• 執行人: 2020leon
  $\to$ 開發紀錄
• 執行人: happyjack91630
  $\to$ 開發紀錄

〈Concurrency Primer〉校訂和範例撰寫

檢視〈Concurrency Primer〉草稿並記錄閱讀過程中的疑惑，嘗試用 C11 Atomics 改寫原有程式碼，並確保在 QEMU/Arm 正確運作。

• 執行人: huang-me
  $\to$ 開發記錄

研讀 Memory Ordering 材料並實驗

研讀 Linux-Kernel Memory Ordering: Help Arrives At Last! (錄影要看完！對應的投影片) 和 Memory barriers in C，提供對應的解說，並重現實驗 (例如使用 diy7)

• 相關資訊:
  • I/O ordering 學習紀錄
  • Experiments on Concurrency - Happens-before
• 執行人: yyyyuwen
  $\to$ 開發紀錄
• 執行人: ibat10clw
  $\to$ 開發紀錄

rhashtable 研究

Linux 核心提供一套 Resizable, Scalable, Concurrent Hash Table，名為 rhashtable (見 include/linux/rhashtable.h 及 lib/rhashtable.c)，描述於論文〈Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming〉。摘譯 LWN 文章，並佐以原論文，描述 rhashtable 何以落實高效的並行雜湊表，搭配撰寫 Linux 核心模組作為試驗

• 相關資訊
  • Relativistic hash tables, part 1: Algorithms
  • Relativistic hash tables, part 2: Implementation
• 執行人: linjohnss
  $\to$ 開發紀錄

針對 rv32emu 實作 JIT 編譯器

rv32emu 是針對 RISC-V 32 位元指令集開發的精簡高效模擬器，本任務是引入 JIT 編譯器，以加速 RV32 指令的執行。

• 執行人: LambertWSJ
  $\to$ 開發紀錄

重做 Fibonacci Device Driver

完成 fibdrv 指定要求和進行附加事項 (在一對一討論時約定)

• 執行人: ganoliz
  $\to$ 開發紀錄
• 執行人: bebo1010
  $\to$ 開發紀錄
• 執行人: Nomad1230
  $\to$ 開發紀錄
• 執行人: Destiny0504
  $\to$ 開發紀錄
• 執行人: scottxxxabc
  $\to$ 開發紀錄
• 執行人: linchi1997yeh
  $\to$ 開發紀錄

sysprog21/bignum 的研究和改進

對比 sysprog21/bignum 和自己撰寫的大數運算，同樣在求 Fibonacci 數，分析運算速度、記憶體開銷，和潛在的錯誤，並解釋何以有這些落差。研讀 sysprog21/bignum，落實原始程式碼中標注的待做事項。

• 執行人: curlyw819
  $\to$ 開發紀錄

實作 Thread package

以第 10 週測驗題給定的程式碼為基礎，實作類似 POSIX Thread 的套件

• 執行人: qwe661234
  $\to$ 開發紀錄

Concurrent Linked List with Memory Reclamation

實作有效的並行鏈結串列，並整合 Hazard Pointer 和 RCU 作為資源釋放機制

• 執行人: kdnvt
  $\to$ 開發紀錄

Lock-Free Linked List with Lockless Memory Allocation

以第 11 週測驗題第二題的程式碼為基礎，實作有效的並行鏈結串列，並搭配第 13 週測驗題第一題的記憶體管理 (以 mmap 系統呼叫實作) 程式，儘量降低 lock contention。

• 執行人: Korin777
  $\to$ 開發紀錄

Lock-free Multiple Producer-Consumer 實作

以第 9 週測驗題第二題和第 11 週測驗題給定的程式碼為基礎，探討 lock-based vs. lock-free Multiple Producer-Consumer 的設計和實作議題

• 執行人: idoleat
  $\to$ 開發紀錄

Lock-free Ringbuffer 實作

理解 lfring 並改進該實作

• 執行人: Eddielin0926
  $\to$ 開發紀錄

Lockless Multithreaded Logger 實作

探討 threaded-logger 的實作，分析其中 reader-writer 議題，包含 atomics 和 fute 的使用，思索後續的改進

• 執行人: AmyLin0210
  $\to$ 開發紀錄

改進 quiz1

改進 第 1 週測驗題 並彙整其他學員的成果

• 執行人: ShawnLu31
  $\to$ 開發紀錄

改進 quiz2

改進 第 2 週測驗題 並彙整其他學員的成果

• 執行人: KJay221
  $\to$ 開發紀錄

改進 quiz3

改進 第 3 週測驗題 並彙整其他學員的成果

• 執行人: KatherineHuangg
  $\to$ 開發紀錄

改進 quiz4 (D)

改進 第 4 週測驗題第四題、彙整其他學員的成果，並且擴充為通用的 coroutine

• 執行人: Wallmountain
  $\to$ 開發紀錄

改進 quiz5 (B)

完成 第 5 週測驗題第二題的延伸題目，著重於 Hazard Pointer 和 RCU 的比較 (在同一程式碼基礎上，個別實作二者來量化比較效率/特性)

• 相關資訊: concurrent-programs
• 執行人: sternacht
  $\to$ 開發紀錄
• 執行人: ShienF
  $\to$ 開發紀錄

改進 quiz6 (A)

改進 第 6 週測驗題第一題 (user-level threads)，搭配第 10 週測驗題的實作，打造一套高效率的使用者層級的執行緒函式庫，比照 uThreads (及其後繼專案 libfibre) 進行網頁伺服器情境的效能評估

• 執行人: Kevin-Shih
  $\to$ 開發紀錄

改進 quiz6 (B)

改進 第 6 週測驗題第二題 (lock-free hashtable)、彙整其他學員的成果，和進行附加事項 (在一對一討論時約定)

• 執行人: linjohn
  $\to$ 開發紀錄
• 執行人: cyrong
  $\to$ 開發紀錄

改進 quiz8 (C)

進行 第 8 週測驗題第三題的延伸問題

• 執行人: cwl0429
  $\to$ 開發紀錄

改進 quiz9 (A)

進行 第 9 週測驗題第一題的延伸問題

• 執行人: yijui
  $\to$ 開發紀錄

改進 quiz12 (B)

進行 第 12 週測驗題第二題的延伸問題。過程中參照第 13 週測驗題第一/二題，嘗試開發出高效的 ring buffer。

• 相關資訊:
  • ringbuffer 報告
  • Super Fast Circular Ring Buffer Using Virtual Memory trick
  • Using black magic to make a fast circular buffer
  • linear_ringbuffer/include/bev/linear_ringbuffer.hpp
  • wuffs/script/mmap-ring-buffer.c
• 執行人: StevenChou499
  $\to$ 開發紀錄

改進 quiz14 (B)

延展 第 14 週測驗題第二題的封包捕捉程式 (使用 Packet MMAP)，使其具備類似 Packet Sniffer 的功能

• 執行人: a12345645
  $\to$ 開發紀錄

重作 lab0

改進並彙整其他學員的成果

• 執行人: Eric-liau
  $\to$ 開發紀錄
• 執行人: HScallop
  $\to$ 開發紀錄
• 執行人: jj97181818
  $\to$ 開發紀錄
• 執行人: kaiweike
  $\to$ 開發紀錄
• 執行人: raysun0729