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

--- title: 2023 年 Linux 核心設計/實作課程期末專題 description: 「Linux 核心設計/實作」課程期末專題清單 tags: linux2023 --- # 2023 年 [Linux 核心設計/實作](https://wiki.csie.ncku.edu.tw/linux/schedule)課程期末專題 :::info :information_source: 注意事項 * 敬請瀏覽學員的成果，亦歡迎在下方「開發紀錄」中，留言提出您的疑惑和改進建議，學員會適度回覆，您的寶貴意見是我們成長的動力 $\to$ 請留言在每份開發紀錄的「提問清單」 * 下方主題對應的開發紀錄、原始程式碼、實驗資訊，和解說影片皆允許公眾存取，若您遇到存取上的困難，請發訊息給 **[授課教師](https://www.facebook.com/JservFans)** ::: ## Linux 核心同步機制研究探討 Linux 核心的同步機制，並運用 Hazard Pointer 和 RCU 作為資源釋放機制 * 相關資訊 * [concurrent linked list](https://hackmd.io/@kdnvt/concurrent-ll-2022) * [Revisit Multi-Reader Synchronizations for Scalable Applications](https://osslatam22.sched.com/event/15BsE): Open Source Summit Latin America 2022 * [OSSLA Records](https://hackmd.io/@cccccs100203/OSSLA2022-records) * [So What Has RCU Done Lately?](https://hackmd.io/@cccccs100203/So-What-Has-RCU-Done-Lately) * 執行人: Korin777 $\to$ [開發紀錄](https://hackmd.io/@sysprog/ry_6RHgS3) ## Linux 排程器研究探討 Linux 排程器內部設計，改進《Demystifying the Linux CPU Scheduler》，並尋求貢獻程式碼到 Linux 核心的機會 * 相關資訊 * [Let's Publish a Collaborative e-Book for Linux Kernel](https://hackmd.io/LXD339QGRbaEBvESooItTg) * [git commits](https://lore.kernel.org/all/?q=%22Jui-Tse+Huang%22) * [BORE (Burst-Oriented Response Enhancer) CPU Scheduler](https://hackmd.io/@foxhoundsk/bore-sched)，是 [CachyOS](https://cachyos.org/) 預設的 CPU 排程器 * [Reducing CPU scheduler latency in Linux](https://www.diva-portal.org/smash/get/diva2:1630380/FULLTEXT01.pdf) * [Reducing latency spikes by tuning the CPU scheduler](https://www.scylladb.com/2016/06/10/read-latency-and-scylla-jmx-process/) * [開發進度-1](https://hackmd.io/@steven1lung/scheduler_notes) * [開發紀錄-2](https://hackmd.io/@SmallHanley/linux2022-projects) * 執行人: linhoward0522 $\to$ [開發紀錄](https://hackmd.io/@sysprog/BJh9FdlS2) * 執行人: chun61205 $\to$ [開發紀錄](https://hackmd.io/@sysprog/By-Q7reB3) * 執行人: irenesu2000 $\to$ [開發紀錄](https://hackmd.io/@sysprog/rklkuZ2rh) ## vwifi 虛擬無線網路裝置驅動程式和實驗環境 [vwifi](https://github.com/sysprog21/vwifi) 是個程式碼約五百行，具體而微的 WiFi 裝置驅動程式，採用 cfg80211 框架。目前 vwifi 支援 scan, connect, disconnect 等 cfg80211 的介面操作，並得以正確處理 Tx/Rx 封包。 * 相關資訊 * [2022 年開發記錄](https://hackmd.io/@rickywu0421/FinalProject) * 執行人: willwillhi1 $\to$ [開發紀錄](https://hackmd.io/@sysprog/rJD2joOSh) ## 打造 Linux 虛擬攝影機裝置驅動程式 [vcam](https://github.com/sysprog21/vcam) 是個針對 Linux 核心開發的虛擬攝影機裝置，全部程式碼僅 1 千 5 百行，從而可理解 V4L2 (video fro Linux APIs, version 2) 的使用和 Linux 多媒體架構。開發一個虛擬的攝影機裝置除了理解 Linux 核心設計外，也有資訊安全的幫助，例如你可以安插相關程式碼，紀錄有哪些應用程式偷偷啟動攝影機，但過程中又不會揭露真正的隱私。 * 相關資訊: * [2020 年開發紀錄](https://hackmd.io/@eecheng/B16rQ3GjU) * [2021 年開發紀錄](https://hackmd.io/@WayneLin1992/HkDBmLUDO) * [2022 年開發紀錄](https://hackmd.io/@Masamaloka/linux2022-vcam) * [2023 年開發紀錄](https://hackmd.io/@sysprog/rJEhcgoSn) ## Linux 系統虛擬機器開發和改進 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](https://github.com/sysprog21/kvm-host) 則是建構在 KVM 基礎上的虛擬機器實作，可載入 Linux 核心和相關應用程式。 * 相關資訊: * [KVM](https://hackmd.io/@RinHizakura/SJpFJ0mfF) * [2022 年開發紀錄](https://hackmd.io/@ray90514/HyefaHiwc) * [KVM-host 筆記](https://github.com/magnate3/linux-riscv-dev/blob/main/exercises2/kvm/kvm.md) * [Gunyah Hypervisor from QUIC](https://www.phoronix.com/news/Qualcomm-Gunyah-Linux-v12) * 執行人: yanjiew1 $\to$ [開發紀錄](https://hackmd.io/@sysprog/rkro_FeSh) ## simplefs 為了探索 Linux VFS (virtual file system) 介面及檔案系統實作機制，我們從無到有撰寫一個運作於 Linux 核心模式中的精簡檔案系統，原始程式碼約一千餘行，支援基本的檔案和目錄處理，同時也考慮到權限和並行處理的議題。本任務也規劃移植 Arm 公司發展的 [littlefs](https://github.com/littlefs-project/littlefs) 成為 Linux 核心原生檔案系統 (不透過 [FUSE](https://en.wikipedia.org/wiki/Filesystem_in_Userspace)) * 相關資訊: * [開發紀錄-1](https://hackmd.io/@Nahemah1022/rJo1sAtid) * [開發紀錄-2](https://hackmd.io/@fwfly/simplefs) * [開發紀錄-3](https://hackmd.io/@freshLiver/linux-vfs-main/) * 執行人: fewletter $\to$ [開發紀錄](https://hackmd.io/@sysprog/BymZ7EeH3) ## 實作高效記憶體配置器 [第 5 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz5)、[第 6 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz6)、[第 11 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz11)提及逐步建構記憶體配置器 (memory allocator)，本任務針對 Linux 核心的機制，設計現代的高效記憶體配置器 * 相關資訊 * [rpmalloc](https://github.com/mjansson/rpmalloc) * [Deterministic Memory Allocation for Mission-Critical Linux](https://ossna2017.sched.com/event/BCsR) * 執行人: WangHanChi $\to$ [開發紀錄](https://hackmd.io/@sysprog/HkNR4RVrn) * 執行人: a1091150 $\to$ [開發紀錄](https://hackmd.io/@sysprog/Hy5kBl5Hh) * 執行人: cin-cout $\to$ [開發紀錄](https://hackmd.io/@sysprog/Sys6U7nB2) ## 高效網頁伺服器探討從無到有打造 Linux 平台的高效能網頁伺服器，涵蓋是否該將伺服器實作於 Linux 核心內部、並行處理、I/O 模型、epoll、Reactor pattern，和 Web 伺服器在事件驅動架構的考量。 * 相關資訊: * [sysprog21/timeout](https://github.com/sysprog21/timeout): Tickless Hierarchical Timing Wheel * [2020 年開發紀錄](https://hackmd.io/@jwang0306/final-project) / [GitHub](https://hackmd.io/@jwang0306/sehttpd) * [2021 年開發紀錄](https://hackmd.io/@XDEv11/sehttpd-project) * [2022 年開發紀錄](https://hackmd.io/@tommy2234/HJgbwqvvc) * [開發紀錄-4](https://hackmd.io/@jim12312321/linux2022-sehttpd) * 執行人: SPFishcool $\to$ [開發紀錄](https://hackmd.io/@sysprog/HJgX4_MH3) * 執行人: JoshuaLee0321 $\to$ [開發紀錄](https://hackmd.io/@sysprog/SJyZrfnSh) ## kHTTPd 改進擴充 [kHTTPd](https://github.com/sysprog21/khttpd)，使其具備現代網頁伺服器的經典特色，並運用 Linux 核心的機制，例如使用 RCU 管理 HTTP 連線，參見 [ktcp](https://hackmd.io/@sysprog/linux2023-ktcp) * 相關資訊: * [Tempesta FW](https://github.com/tempesta-tech/tempesta): 在現有的 Linux TCP/IP 堆疊上建構 Web 加速器 * [http-server-rcu](https://github.com/frextrite/http-server-rcu): 以 RCU 管理連線 * [kws](https://github.com/kaiyuanl/kws): 參照其待辦事項 * [2022 年開發紀錄](https://hackmd.io/@Risheng/linux2022-khttpd) * [開發紀錄-2](https://hackmd.io/@eric88525/linux2022-ktcp) * 執行人: Jerejere0808 $\to$ [開發紀錄](https://hackmd.io/@sysprog/HkzcnhOHn) * 執行人: zeddyuu $\to$ [開發紀錄](https://hackmd.io/@sysprog/BknrvhuHn) * 執行人: Paintako $\to$ [開發紀錄](https://hackmd.io/@sysprog/BkSW8Z2Bn) * 執行人: terry23304 $\to$ [開發紀錄](https://hackmd.io/@sysprog/r1vb6bhH2) ## 以 eBPF 建構 TCP 伺服器嘗試以 [eBPF](https://hackmd.io/@sysprog/linux-ebpf) 來建構 TCP 伺服器。 * 執行人: YSRossi $\to$ [開發紀錄](https://hackmd.io/@sysprog/ryBw0adH2) ## 透過 Netfilter 自動過濾廣告儘管我們可在網頁瀏覽器中透過像是 [AdBlock](https://getadblock.com/) 這類的 extension 來過濾廣告，但需要額外的設定和佔用更多系統資源，倘若我們能透過 [netfilter](https://www.netfilter.org/)，直接在核心層級過濾網路廣告，那所有應用程式都有機會受益。 * 參考資訊: * [How to drop 10 million packets per second](https://blog.cloudflare.com/how-to-drop-10-million-packets/) * [Use the iptables firewall to block ads on your Linux machine](https://securitronlinux.com/debian-testing/use-the-iptables-firewall-to-block-ads-on-your-linux-machine/) * [nBlock](https://github.com/notracking/nBlock) * [2020 年開發紀錄](https://hackmd.io/@ZhuMon/2020q1_final_project) * 執行人: ItisCaleb $\to$ [開發紀錄](https://hackmd.io/@sysprog/BJb0NRYH3) ## 以 Linux XDP 為基礎的防火牆 XDP (eXpress Data Path) 自 Linux 核心 4.8 版本起作為以 eBPF 為基礎的高效資料處理路徑，一旦網路中斷觸發後，XDP 允許將特定的操作提前在 TCP/IP 堆疊之前就處理，不僅反應更快而且省下寶貴的記憶體分配的成本。本議程以 XDP 作為切入，探討如何在這之上發展高效網路負載平衡器，並針對典型的 High Availability (HA) 叢集和非典型的情境去調整。 * 參考資訊: * [XDP Use-case: Load Balancer](https://prototype-kernel.readthedocs.io/en/latest/networking/XDP/use-cases/xdp_use_case_load_balancer.html) * [COSCUP 2020](https://coscup.org/2020/zh-TW/agenda/FFF8UM) * [XDP Firewall](https://github.com/gamemann/XDP-Firewall) * 執行人: jhin1228, D4nnyLee $\to$ [開發紀錄](https://hackmd.io/@sysprog/ryvKMFgr2) ## 改進 Linux 核心的 `lib/{list_}sort.c` 解釋 Linux 核心的 `lib/{list_}sort.c` 現有的 bottom-up merge/heap sort 實作，並尋求效能改進，例如 hybrid sort 的引入 * 參考資訊 * [Bottom-up Heapsort](https://hackmd.io/@Uduru0522/bottomup-heapsort-analyze) * [Timsort 研究與對 Linux 核心貢獻嘗試](https://hackmd.io/@yanjiew/linux2023q1-timsort) * 執行人: visitorckw $\to$ [開發紀錄](https://hackmd.io/@sysprog/Hy5hmaKBh) * 執行人: kart81604 $\to$ [開發紀錄](https://hackmd.io/@sysprog/B146OVeHn) ## `simrupt` 研究和應用 [simrupt](https://github.com/sysprog21/simrupt) 專案名稱由 simulate 和 interrupt 二個單字組合而來 * 作用是模擬 [IRQ 事件](https://www.kernel.org/doc/html/latest/core-api/genericirq.html)，並展示以下 Linux 核心機制的運用: - irq - softirq - tasklet - workqueue - kernel thread - [kfifo](https://www.kernel.org/doc/htmldocs/kernel-api/kfifo.html) - [memory barrier](https://www.kernel.org/doc/Documentation/memory-barriers.txt) * 相關資訊: * [2021 年開發紀錄](https://hackmd.io/@linD026/simrupt-vwifi) * [2022 年開發紀錄](https://hackmd.io/@Build-A-Moat/BJasWQhOc) * 執行人: brianlin314 $\to$ [開發紀錄](https://hackmd.io/@sysprog/HJXlHtlB2) ## Linux Kernel Module Programming Guilde (LKMPG) 校訂和改進 [LKMPG](https://sysprog21.github.io/lkmpg/) 是 [Linux 核心內建文件](https://www.kernel.org/doc/Documentation/process/kernel-docs.rst)所推薦的電子書，儘管品質不算好，但仍是世上極少數自由流通的 Linux 核心專書。投入這項專案，就意味著可獲得大量的關注，也是對自身專業的極好肯定。 * 執行人: fourcolor $\to$ [開發紀錄](https://hackmd.io/@sysprog/Sk8IMQ9S2) ## 〈[每位程式開發者都該有的記憶體知識](https://sysprog21.github.io/cpumemory-zhtw/)〉翻譯和校訂本文翻譯自 Ulrich Drepper 於 2007 年撰寫的論文〈[What Every Programmer Should Know About Memory](https://www.akkadia.org/drepper/cpumemory.pdf)〉(版次: 1.0) * 相關資訊 * [現代處理器設計: Cache 原理和實際影響](https://hackmd.io/@sysprog/HkW3Dr1Rb) * [CPU Cache 原理探討](https://hackmd.io/@drwQtdGASN2n-vt_4poKnw/H1U6NgK3Z) * [prefetch 背景知識簡略整理](https://hackmd.io/@Rance/Hy3KRm1CG) * [Random and sequential](https://hackmd.io/@dange/B1J3omXfV) * [2022 年開發紀錄](https://hackmd.io/@6649/linux2022-cpumemory) * 執行人: lorian0738 $\to$ [開發紀錄](https://hackmd.io/@sysprog/Sk6wB3FS2) ## 《Concurrency Primer》校訂和範例撰寫檢視〈Concurrency Primer〉草稿並記錄閱讀過程中的疑惑，嘗試用 C11 Atomics 改寫原有程式碼，並確保在 QEMU/Arm 正確運作。 * 相關資訊 * [2022 年開發記錄](https://hackmd.io/@huang-me/2022linux_atomic_primer) * 執行人: PlusThousand0107 $\to$ [開發紀錄](https://hackmd.io/@sysprog/HySGuWXL3) * 執行人: GaberPlaysGame $\to$ [開發紀錄](https://hackmd.io/@sysprog/S1kFNL6L3) ## 並行程式設計回顧〈[並行和多執行緒程式設計](https://hackmd.io/@sysprog/concurrency)〉教材和相關測驗題，強化對延伸問題的掌握 * 執行人: csm1735 $\to$ [開發紀錄](https://hackmd.io/@sysprog/SkzPgZnB2) * 執行人: WeiHongWi $\to$ [開發紀錄](https://hackmd.io/@sysprog/H1L_mbhrh) ## [rhashtable](https://elixir.bootlin.com/linux/latest/source/include/linux/rhashtable.h) 及 Linux 核心記憶體管理研究 Linux 核心提供一套 Resizable, Scalable, Concurrent Hash Table，名為 `rhashtable` (見 [include/linux/rhashtable.h](https://elixir.bootlin.com/linux/latest/source/include/linux/rhashtable.h) 及 [lib/rhashtable.c](https://elixir.bootlin.com/linux/latest/source/lib/rhashtable.c))，描述於論文〈[Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming](https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf)〉。摘譯 LWN 文章，並佐以原論文，描述 rhashtable 何以落實高效的並行雜湊表，搭配撰寫 Linux 核心模組作為試驗 * 相關資訊 * [Relativistic hash tables, part 1: Algorithms](https://lwn.net/Articles/612021/) * [Relativistic hash tables, part 2: Implementation](https://lwn.net/Articles/612100/) * [2022 年開發紀錄](https://hackmd.io/@linjohn/rhashtable) * 執行人: chiangkd, POCHUN-CHEN $\to$ [開發紀錄](https://hackmd.io/@sysprog/HkKKE5eB3) ## 針對 rv32emu 實作 JIT 編譯器 [rv32emu](https://github.com/sysprog21/rv32emu) 是針對 RISC-V 32 位元指令集開發的精簡高效模擬器，本任務是引入 JIT 編譯器，以加速 RV32 指令的執行。 * 相關資訊 * [2022 年開發紀錄](https://hackmd.io/@lambert-wu/rv32emu) * [設計精簡又快速的 RISC-V 指令集模擬器](https://hackmd.io/@coscup/ByiRHCyTc) * 執行人: qwe661234 $\to$ [開發紀錄](https://hackmd.io/@sysprog/Syh834lH3) ## RISC-V System Emulator + Linux [semu](https://github.com/jserv/semu) 是個能夠執行 Linux 核心的精簡 RISC-V 系統模擬器。 * 執行人: JiggerChuang $\to$ [開發紀錄](https://hackmd.io/@sysprog/Skuw3dJB3) ## 在 RISC-V 處理器運作 Linux 核心 (FPGA/虛擬機器) * 相關資訊 * [從零開始的 RISC-V SoC 架構設計與 Linux 核心運行](https://hackmd.io/@w4K9apQGS8-NFtsnFXutfg/B1Re5uGa5) * [semu](https://github.com/jserv/semu): RISC-V 系統模擬器，可執行 Linux 核心 * 執行人: Chiwawachiwawa $\to$ [開發紀錄](https://hackmd.io/@sysprog/B1Jl_HlBn) * 執行人: fennecJ $\to$ [開發紀錄](https://hackmd.io/@sysprog/S1jNiYgr2) ## 紅黑樹實作改進重做[第 3 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz3) 的測驗一及[第 4 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz4)的測驗一，彙整其他學員的成果，連同延伸問題 * 執行人: koty6069 $\to$ [開發紀錄](https://hackmd.io/@sysprog/ryDD1HgS3) * 執行人: LiChiiiii $\to$ [開發紀錄](https://hackmd.io/@sysprog/rJbMiW3S3) * 執行人: EdwardCKC $\to$ [開發紀錄](https://hackmd.io/@sysprog/Sy7jXmnrh) ## 運用 Skip List 於 Linux 核心 * 相關資訊 * [第 8 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz8) * [2019 年開發紀錄](https://hackmd.io/@Vy_ZuZdnSo-Wv4jSWgNmLw/B1OZFDL1H) * 執行人: Tonr01 $\to$ [開發紀錄](https://hackmd.io/@sysprog/SJ6drDgB2) ## 回顧 Linux 核心的 bitops 並尋求貢獻程式碼的機會 Linux 核心的 [include/asm-generic/bitops](https://github.com/torvalds/linux/tree/master/include/asm-generic/bitops) 存在若干實作不一致的狀況，本任務嘗試追蹤 git log 和 LKML，以理解發展脈絡，並嘗試用精簡有效的方式改寫，最後嘗試貢獻程式碼到 Linux 核心。 * 執行人: Shiritai $\to$ [開發紀錄](https://hackmd.io/@sysprog/ByS9w_lHh) ## Linux 亂數產生器研究 [第 3 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz3)第三題介紹到 Linear feedback shift register (LFSR)，這也是 Linux 核心亂數產生器 (RNG) 的基礎之一。本任務探討 [Linux RNG](https://www.amossys.fr/fr/ressources/blog-technique/linux-csprng-architecture/) 的原理、實作機制，以及應用場景。 * 執行人: ShamrockLee $\to$ [開發紀錄](https://hackmd.io/@sysprog/r18z86NHh) ## 位元操作 [第 2 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz2)嘗試檢驗學員對[位元操作](https://hackmd.io/@sysprog/c-bitwise)的認知，本任務強化相關練習。 * 執行人: tab08222 $\to$ [開發紀錄](https://hackmd.io/@sysprog/BJBQgOZI2) ## Trusted Firmware-A 及 Linux 啟動流程分析 [Trusted Firmware](https://www.trustedfirmware.org/) 是 Arm 公司針對 TrustZone 和 [Platform Security Architecture](https://www.arm.com/architecture/security-features/platform-security) 開發的基礎建設，本任務理解 Trusted Firmware-A (TF-A) 及探討 Linux 在 TF-A 的系統啟動流程分析。 * 執行人: chien1214 $\to$ [開發紀錄](https://hackmd.io/@sysprog/rkxaDOWI3) ## Kernel PWN 藉由回顧經典的 PWN 手法，理解 Linux 核心機制。 * 執行人: Welly0902 $\to$ [開發紀錄](https://hackmd.io/@sysprog/H1c8jONIh) ## 重做 fibdrv 並彙整學員成果改進並彙整其他學員的成果 * 執行人: ericlai1021 $\to$ [開發紀錄](https://hackmd.io/@sysprog/HyyMNz7S3) * 執行人: p96114175 $\to$ [開發紀錄](https://hackmd.io/@sysprog/SJzDwvQS2) * 執行人: bonianlee $\to$ [開發紀錄](https://hackmd.io/@sysprog/H1DuThFHn) * 執行人: seasonwang0905 $\to$ [開發紀錄](https://hackmd.io/@sysprog/rJxjTe5B2) * 執行人: paulpeng-popo $\to$ [開發紀錄](https://hackmd.io/@sysprog/Hk2NJG3H2) * 執行人: tintinjian12999 $\to$ [開發紀錄](https://hackmd.io/@sysprog/B1lbIu73Sh) * 執行人: ctfish7063 $\to$ [開發紀錄](https://hackmd.io/@sysprog/ByWO973r3) ## 重做 lab0 並彙整學員成果改進並彙整其他學員的成果 * 執行人: oEric0929o $\to$ [開發紀錄](https://hackmd.io/@sysprog/SJ8ZkFxSh) * 執行人: andy155224 $\to$ [開發紀錄](https://hackmd.io/@sysprog/HJmB5x5Hn) * 執行人: yihsuan1011 $\to$ [開發紀錄](https://hackmd.io/@sysprog/B1itMCUI3)