---
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)