# 2024 年開放原始碼專案協作
> [講解錄影](https://youtu.be/AzlgZMd_Pqs)

## 緣起

* 2005 年 Debian Taiwan 社群有項名為「[夢幻軟體計畫](https://web.archive.org/web/20120814062536/http://wiki.debian.org.tw/WishList2005)」，嘗試將現有的概念化為更具體的提案，徵求更多人的參與，從而讓投身實作的人得以互相溝通與合作。
* 2015 年決定「[封麥](https://blog.coscup.org/2015/07/2015-coscup.html)」
+ 連續在 COSCUP 演講 10 年、合計 18 場演講，擔任訪談人、議程委員、贊助商等不同角色
+ 把發表的機會留給學生
* 2014 到 2017 年，[jserv](https://wiki.csie.ncku.edu.tw/User/jserv) 在交大資工所開設「[自由開源軟體與專案協作](https://sites.google.com/site/fossapc/about-the-class)」課程，嘗試引導大學生貢獻於開放原始碼專案。
* 莊偉赳博士發起的[源來適你](https://www.facebook.com/opensource4you/)，引導有心人投入 Apache Software Foundation 的眾多專案
+ COSCUP 2021 年演講: [帶台灣學生打世界盃—以開源社群成立頂級實習場域](https://coscup.org/2021/zh-TW/session/EY8XKK)
+ [podcast](https://podcasts.apple.com/tw/podcast/id1674730463)
* 2019 年起，[jserv](https://wiki.csie.ncku.edu.tw/User/jserv) 在成大資訊系/所開設「Linux 核心」系列課程，至今已有超過 17 位學生的程式碼貢獻獲得 Linux 核心收錄

## 近期國際研討會發表狀況
> 請考慮 **[資助學生旅費](https://ocf.tw/p/sysprogram/)**

- [ ] 2022 年
* 鄭育丞: FOSSASIA - 講題: The Evolution of Linux I/O Models: A Path towards IO_uring
* 向景亘: FOSSASIA - 講題: Empower Embedded Computing with VexRiscv and FreeRTOS
* 馮會鈞: FOSSASIA - 講題: Brief History of Linux CPU Scheduler
* 向景亘: Open Source Summit - 講題: [Towards PREEMPT_RT for the Full Task Isolation](https://ossna2022.sched.com/event/11NtQ)
* 林志恩: Open Source Summit - 講題: [Lower Response Time of Fork by Extending Copy-on-write to the Page Table](https://ossna2022.sched.com/event/11NnW)
* 洪邵澤: Open Source Summit - 講題: [Revisit Multi-Reader Synchronizations for Scalable Applications](https://osslatam22.sched.com/event/15BsE)
* 吳恩緯: [Google Summer of Code for FreeBSD Foundation](https://summerofcode.withgoogle.com/archive/2022/organizations/the-freebsd-project) - 主題: Wi-Fi Simulator: wtap

- [ ] 2023 年
* 吳恩緯: Open Source Summit - 講題: [Lightweight and Fast WiFi Access in Virtual Machines](https://osseu2023.sched.com/event/1OGgh)
* 陳彥甫: Open Source Summit - 講題: [RISC-V-Based Sandboxing for Secure and Efficient Software Execution](https://sched.co/1Typ4)

## 開發策略和模式
* 選定若干有潛力、有特色的主題，建構對應的開放原始碼專案
* 擬定切入貢獻大型開放原始碼專案 (如 Linux 核心) 的策略，以「投石問路」的手段逐步推進
* 聯繫對學生友好的開放原始碼專案主持人，建議程式碼貢獻的方案
* 不再是 [side project](https://en.wikipedia.org/wiki/Side_project)，直接成為課程作業/畢業專題/研究論文主體

## 2024 年聚焦的開放原始碼專案

### 虛擬機器/編譯器
* [rv32emu](https://github.com/sysprog21/rv32emu) / [semu](https://github.com/sysprog21/semu): A compact and efficient RISC-V RV32I[MACF] emulator
* [slides](https://docs.google.com/presentation/d/1hSYMrdrZX0pp9bp5HKXlEs2SB-Z08lhvTXfLwv3QsO4/edit?usp=sharing)
* 進行中: [tiered JIT compilation](https://github.com/sysprog21/rv32emu/issues/322), [CFI](https://github.com/sysprog21/rv32emu/issues/311), [deterministic memory pool](https://github.com/sysprog21/rv32emu/issues/94), [WebAssembly port](https://github.com/sysprog21/rv32emu/issues/75)
* 進行中: [VirtIO GPU](https://github.com/sysprog21/semu/issues/32), [Caching for MMU](https://github.com/sysprog21/semu/issues/26)
* [2023 年開發紀錄](https://hackmd.io/@sysprog/Skuw3dJB3)
* [shecc](https://github.com/sysprog21/shecc): A self-hosting and educational C optimizing compiler
* [HN](https://news.ycombinator.com/item?id=38905182)
* 進行中: [C front-end refinement](https://github.com/sysprog21/shecc/issues/84), [basic optimizations](https://github.com/sysprog21/shecc/issues/88)
* [sse2neon](https://github.com/DLTcollab/sse2neon): A C/C++ header file that converts Intel SSE intrinsics to Arm/Aarch64 NEON intrinsics
* [slides](https://docs.google.com/presentation/d/1xmb_mvsHISWp6naP1rHOyrxzMzNQkVoKK69lGRRXV9M/edit#slide=id.g207f77d4362_0_502)
* 進行中: [CRC intrinsics](https://github.com/DLTcollab/sse2neon/issues/624), [older GCC compatibility](https://github.com/DLTcollab/sse2neon/issues/622), [AVX/AVX2 coverage](https://github.com/DLTcollab/sse2neon/issues/82)

### RISC-V 處理器實作
* [single-cycle RISC-V core](https://github.com/sysprog21/ca2023-lab3)
* [解說](https://hackmd.io/@sysprog/r1mlr3I7p)
* [SoomRV](https://github.com/mathis-s/SoomRV): A simple superscalar out-of-order RISC-V core. It can execute up to 4 instructions per cycle and is able to boot Linux.

### Linux 核心模組
* [vcam](https://github.com/sysprog21/vcam): 針對 Linux 核心開發的虛擬攝影機裝置，全部程式碼僅 1 千 5 百行，從而可理解 V4L2 (video for Linux APIs, version 2) 的使用和 Linux 多媒體架構。
* [2020 年開發紀錄](https://hackmd.io/@eecheng/B16rQ3GjU)
* [2021 年開發紀錄](https://hackmd.io/@WayneLin1992/HkDBmLUDO)
* [2022 年開發紀錄](https://hackmd.io/@Masamaloka/linux2022-vcam)
* [vwifi](https://github.com/sysprog21/vwifi) 是個具體而微的 WiFi 裝置驅動程式，採用 cfg80211 框架。目前 vwifi 支援 scan, connect, disconnect 等 cfg80211 的介面操作，並得以正確處理 Tx/Rx 封包。
* [2022 年開發記錄](https://hackmd.io/@rickywu0421/FinalProject)
* [2023 年開發紀錄](https://hackmd.io/@sysprog/rJD2joOSh)
* [kHTTPd](https://github.com/sysprog21/khttpd): 核心模式的網頁伺服器，參見 [ktcp](https://hackmd.io/@sysprog/linux2023-ktcp)
* 改進: [提升吞吐量](https://hackmd.io/@Risheng/linux2022-khttpd)
* 改進: [以 content cache 改進伺服器處理效率](https://hackmd.io/@sysprog/HkzcnhOHn)
* 改進: [提供存取網頁伺服器的系統呼叫](https://hackmd.io/@sysprog/BknrvhuHn)
* 改進: [workqueue](https://hackmd.io/@sysprog/BkSW8Z2Bn)
* [simplefs](https://github.com/sysprog21/simplefs): 為了探索 Linux VFS (virtual file system) 介面及檔案系統實作機制，我們從無到有撰寫一個運作於 Linux 核心模式中的精簡檔案系統
* [開發紀錄-1](https://hackmd.io/@Nahemah1022/rJo1sAtid)
* [開發紀錄-2](https://hackmd.io/@fwfly/simplefs)
* [開發紀錄-3](https://hackmd.io/@freshLiver/linux-vfs-main/)
* [開發紀錄-4](https://hackmd.io/@sysprog/BymZ7EeH3)
* 透過 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)
* [2023 年開發紀錄](https://hackmd.io/@sysprog/BJb0NRYH3)

### eBPF/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)
* [開發紀錄](https://hackmd.io/@sysprog/ryvKMFgr2)
* 嘗試以 [eBPF](https://hackmd.io/@sysprog/linux-ebpf) 來建構 TCP 伺服器。
* [開發紀錄](https://hackmd.io/@sysprog/ryBw0adH2)

### Linux 核心的 `lib/` 目錄
* 解釋 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)
* [lib/list_sort.c 改進](https://hackmd.io/@sysprog/Hy5hmaKBh)
* [lib/sort.c 改進](https://hackmd.io/@sysprog/B146OVeHn)
* Linux 核心的 [include/asm-generic/bitops](https://github.com/torvalds/linux/tree/master/include/asm-generic/bitops) 存在若干實作不一致的狀況，本任務嘗試追蹤 git log 和 LKML，以理解發展脈絡，並嘗試用精簡有效的方式改寫，最後嘗試貢獻程式碼到 Linux 核心。
* [2023 年開發紀錄](https://hackmd.io/@sysprog/ByS9w_lHh)
* [針對 min_heap 的效率改進](https://lore.kernel.org/linux-perf-users/[e-mail]/)
* 第一個 patch 將 array 建立成 heap 的時候我們可以從 n / 2 - 1 (根節點位於 index 0 的位置) 開始做 heapify 而不是從 n / 2 開始，減少了一次不必要的 heapify。
* 教科書版本的 heapify 操作是從根節點開始向下進行，每個 level 與兩個子節點比較，除非當前節點已經是最小的，否則就與兩個子節點中的最小者進行交換。一般情況下，像是 `min_heap_pop` 在移除根節點元素後，會將最後一個元素放到根節點再進行 heapify。這樣的比較與交換過程通常會一直進行到接近葉節點的位置，因此總共需要大約 $2 \times \log_2(n)$ 次的比較操作。為了減少比較次數，第二個 patch 改成每個 level 只比較兩個子節點中的最小者，直到遇到葉節點為止。在遇到葉節點後，我們再從葉節點向上尋找根節點應該被交換至的正確位置。由於這個位置會很接近葉節點，所以只需大約 $\log_2(n)$ 次的比較操作。
* 這樣一來，我們可以節省大約 50% 的比較次數，同時保持相同的交換次數。

### 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/)
* [sched_ext](https://hackmd.io/@RinHizakura/r1uSVAWwp)
* [開發進度-1](https://hackmd.io/@steven1lung/scheduler_notes)
* [開發紀錄-2](https://hackmd.io/@SmallHanley/linux2022-projects)
* [開發紀錄-3](https://hackmd.io/@sysprog/BJh9FdlS2)
* [開發紀錄-4](https://hackmd.io/@sysprog/By-Q7reB3)

### 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)
* [2023 年開發紀錄](https://hackmd.io/@sysprog/rkro_FeSh)

### 全向量視窗系統
[mado](https://github.com/sysprog21/mado) 是個向量圖形 (vector graphics) 視窗系統，不僅展現相關 rect clipping 相關演算法及 fixed point 的操作，還能利用 Linux framebuffer 和 input 子系統來展現整個視窗系統。打造類似 [Cairo API](https://www.cairographics.org/manual/) 風格的向量繪圖函式庫。
> mado 是達悟 (雅美) 族語「窗」的意思。

### 電子書編輯
* Linux Kernel Module Programming Guilde (LKMPG) 校訂和改進
[LKMPG](https://sysprog21.github.io/lkmpg/) 是 [Linux 核心內建文件](https://www.kernel.org/doc/Documentation/process/kernel-docs.rst)所推薦的電子書，儘管品質不算好，但仍是世上極少數自由流通的 Linux 核心專書。投入這項專案，就意味著可獲得大量的關注，也是對自身專業的極好肯定。
* [2023 年開發紀錄](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)〉並針對現行電腦運算環境予以更新
* [Concurrency Primer](https://github.com/sysprog21/concurrency-primer)

### 作業系統核心

* [Mazu](https://github.com/MazuNIX): 亦即 Mazu's Not UNIX，公開釋出的版本會支援 RISC-V 處理器架構。Mazu 的實作參考 MINIX 的許多設計理念，又提供部分 Linux 核心系統呼叫的相容，連同工具程式在內大約僅一萬行，其中微核心的部分則在三千行的規模，很適合作為探索作業系統的教具，一旦熟悉 Mazu 後，再去學習 Linux 核心的內部，掌握度就會很高。設計理念:
* 媽祖是海上守護神，Mazu 則是應用程式的守護神 (daemon)
* 媽祖也稱默娘，Mazu 默默守護著電腦硬體，分配硬體資源給特定的應用程式
* 從命名來說，MazuNIX 顯然是向 UNIX 作業系統致敬，但全部的程式碼針對現代硬體特性重寫，又保有經典系統呼叫
* 媽祖可以鼓勵企業家勇於參選總統，那媽祖更可鼓勵廣大的學子去挑戰高難度的題目，例如開發作業系統核心
> [小故事](https://www.facebook.com/groups/system.software2024/posts/1533465440764682/)

### 針對無人飛行器和機器人系統的軟體基礎建設
* [UAV-Mission-Server](https://github.com/shengwen-tw/uav-mission-server)

### 頂級研討會
* OSDI'23 | [RON: One-Way Circular Shortest Routing to Achieve Efficient and Bounded-waiting Spinlocks](https://www.usenix.org/conference/osdi23/presentation/lo)