# 2025q1 Homework5 (assessment)
contributed by < `rota1001` >

## 因為自動飲料機而延畢的那一年
看完 〈[因為自動飲料機而延畢的那一年](https://www.opasschang.com/docs/the-story-of-auto-beverage-machine-23)〉，我對於願意花一年的時間去解決一個實際的、有難度的問題的學生感到敬佩。我也開始慶幸我是搞軟體的，如果我想看現在工業標準的實作，最大的成本就是翻開 linux 的程式碼，並閱讀它。這不簡單，但是不花錢。看了這篇文章後，我覺得身為一個資工系的學生，在大學期間如果沒有把作業系統和編譯器這些電腦科學的基礎元件寫一遍，那我這四年算是白讀了。這兩件事情其實早就在我 2025 年的目標清單上面了，來修這堂課也是為了這個目標去做的準備。

我對作業系統的認知分為三個階段。一年級時，覺得作業系統離我非常遙遠，也許我一輩子都不會去寫那種東西，也無法想像他是怎麼組成的。聽到同學程式設計（二）的期末專題想要寫一個作業系統，我就想這個怎麼可能是幾個禮拜就寫得出來的東西。在去年暑假，我去寫了 MIT 6.S081 的一些[作業](https://hackmd.io/@rota1001/mit6s081)（那時甚至連中文和英文之間要有空白都還不知道），看了 xv6 這個小的作業系統案例的一部分，發現作業系統可以小到一個我可以想像的大小，這個時候的我以為寫作業系統就比寫一個網頁難一些而已。後來寒假的時候用一些零碎時間跟著 [OS in 1000 line](https://operating-system-in-1000-lines.vercel.app/en/) 去寫了一個可以在使用者空間裡 `printf("Helloworld")` 的作業系統，就覺得自己好棒。接下來就到了這個學期，我選擇修了這門 linux 核心設計。經過前幾週的課程，我發現我根本連作業系統的皮毛都還沒有碰到。光是一個排程器在 linux 核心中就佔了 3 萬行的程式碼，而整個發展的歷程和其中的考量也不是三言兩語就講的完的，要不然老師也不用寫〈Demystifying the Linux CPU Scheduler〉這本書了。而作業系統的難度不只在知道什麼是作業系統和 C 語言怎麼寫上，更多的是在各種元件的目標是什麼？怎麼達成這些目標？怎麼去確定我們達成這些目標了？

## 針對教材的提問
:::success
在閱讀 Demystifying the Linux CPU Scheduler 時，在說明 pid hash 那一段說 `struct pid` 裡面是使用 `pid_chain` 這個東西去把在 pid hash 中碰撞的元素連起來。然而，去閱讀 linux 核心程式碼的時候卻沒有看到有這個變數。
:::
在 [2025-04-22 討論簡記](/i6ZSoExATqOQMf1EvtNFoA#rota1001) 有進行討論，結論是這個 pid hash 實際上的實作是使用 radix tree，也不會有碰撞發生。裡面的 `hlist_head` 與 `task_struct` 中的 `hlist_node` 是用來連接同一個 group 中的任務的（如同一個 thread group 或 process group ...）。
這個部份後來有成功貢獻到這本書中。
:::success
在閱讀 Demystifying the Linux CPU Scheduler 時，在第 35 頁講到 Power Efficiency 的時候，講到排程器在考量這件事的時候有兩件事可以做，一件事是動態調整 CPU 的時脈，另一件事情是將需要比較少能量的任務放到前面。那為什麼將需要能量較少的任務放到前面會比較省電呢？
:::
在下課有去問老師，結論是 CPU 的降頻並不是瞬間的降頻，而是經過一段時間會達到平衡狀態，所以一開始將 CPU 的時脈上升到太高會造成多餘的耗損。這也是為什麼排程器需要去對工作負載進行預測，要對應未來的工作負載來調整 CPU 時脈。

## 前六週學習狀況
前六週教材進度我還算有跟上，所有東西都有看過，現在記得大概 65% 左右的概念。
### 課堂討論
- 第三週：[討論 `str_to_uint32` 的改進](https://hackmd.io/K4C5ofeqQg6LC8OEbdVcwg#rota1001)
- 第五週：[討論 $\displaystyle \lim_ {n\to\infty} (1+\frac{1}{n})^{n}$ 的收斂](https://hackmd.io/EFs_Nfs6TOmIA5ldA_tZsQ#rota1001)
- 第六週：[討論 `fix_sqrt` 與 `fix_log` 的改進](https://hackmd.io/QISdbcjUShy1Be48NHVqaw#rota1001)
### 程式碼貢獻
- [Fix incorrect open count check in release function](https://github.com/sysprog21/simrupt/pull/4)
- [Include <linux/vmalloc.h> explicitly on x86](https://github.com/sysprog21/kxo/pull/5)
- [Enable Control+Q capture by setting input mode](https://github.com/sysprog21/kxo/pull/10)

### 作業重點回顧
- [將 linux 中的 `list_sort` 實作引入 lab0](https://github.com/sysprog21/lab0-c/commit/be13d7b5bbeb812c7ff027afd7a60249e56e45e4)
- [閱讀專題後將 powersort 引入 lab0](https://github.com/sysprog21/lab0-c/commit/7c2224a01909ca61f9d46d96994fe062fc058aa8)
- [閱讀專題時對 xoroshiro128+ 的安全性進行思考](https://hackmd.io/@rota1001/linux2025-ideas#xoroshiro128-%E7%9A%84%E5%AE%89%E5%85%A8%E6%80%A7%E6%80%9D%E8%80%83)
- [實作自己的 custom-memory-allocator](https://github.com/rota1001/custom-memory-allocator)
- [理解並改良 reciprocal implementatijons in Arm assembly](https://hackmd.io/@rota1001/linux2025-homework2#%E6%B5%AE%E9%BB%9E%E6%95%B8%E9%96%8B%E5%B9%B3%E6%96%B9%E6%A0%B9)
- [理解並實作查表的整數平方根](https://hackmd.io/@rota1001/linux2025-homework2#%E8%97%89%E7%94%B1%E6%9F%A5%E8%A1%A8%E7%9A%84%E6%95%B4%E6%95%B8%E5%B9%B3%E6%96%B9%E6%A0%B9)
- [進行《The Art of Computer Programming》對於 Theorem S 的思考，並發現奇怪的地方](https://hackmd.io/@rota1001/linux2025-homework2?stext=33734%3A142%3A0%3A1745655999%3ACleAg5)
- [比照 picolibc 的實作改進 `fix_log`](https://hackmd.io/@rota1001/linux2025-homework3#Fixed-point-log-%E6%94%B9%E9%80%B2)
- [只使用一個 64 位元無號整數紀錄一場遊戲的所有狀態](https://hackmd.io/@rota1001/linux2025-homework3#%E9%A1%AF%E7%A4%BA%E9%81%8E%E5%8E%BB%E6%A3%8B%E7%9B%A4%E7%B4%80%E9%8C%84)

### 課後創作
- [閱讀部份 Linux 核心紅黑樹，並嘗試發 patch](https://hackmd.io/@rota1001/linux-rbtree)
- [對 printf 圖靈完備進行探討](https://hackmd.io/@rota1001/printf-turing)
## 期末專案討論
### [監控和紀錄使用者命令的核心模組](https://hackmd.io/@sysprog/S18kgVDJex?fbclid=IwZXh0bgNhZW0CMTAAYnJpZBExSjJhUWRVOUlSdTNhOGhleQEeBJSG-fUf9asQ2NO_vf9MxoXlNkrskmU5sDNS5AI3tYcBKM3wqklu_r4c7IM_aem_bymnmVaLVr7bPOatNmJqNw#%E7%9B%A3%E6%8E%A7%E5%92%8C%E7%B4%80%E9%8C%84%E4%BD%BF%E7%94%A8%E8%80%85%E5%91%BD%E4%BB%A4%E7%9A%84%E6%A0%B8%E5%BF%83%E6%A8%A1%E7%B5%84)
先前我有使用 Windows API 實作過在使用者層級（Ring 3）的 rookit，做的事情是用 dll injection 去把動態連結庫注入到目標行程中，並且執行程式碼，實作 key logger。另外，也有去 hook 函式。我去監控 chrome 在發出 http 請求的時候使用了什麼 API，並且去 Hook 他攔截封包。另一部份是要去逆向分析 chrome，並且攔截進行 SSL 簽章之前未經加密的明文，這個部份我沒有做出來。後來在資安社的社課後，知道了怎麼找到 `ssl_write` 這個函式（chrome 是使用 boringssl，然後發現他的 debug 巨集中有原始碼的行數，然後這個巨集在展開後的字串是可以在二進制文件中找到的，於是可以用這個東西去找到目標函式的地址）
> [Team T5 2024 木馬實作](https://hackmd.io/@rota1001/team-t5-2024)

並且在這之後有去寫過一個[ㄩㄇ木馬](https://github.com/rota1001/UM_Trojan_Horse)去幫同學的電腦裝有趣的 feature，並且發現如果沒有做硬碟加密的情況下可以用 live usb 在沒有開機的情況下去植入這個木馬：
> [資安讀書會 2024/12：Windows 關機就安全嗎？不用登入也能入侵你的電腦](https://www.canva.com/design/DAGaN1iTQKo/hetMsZ1tSMjWjR4a_BdEWg/edit?utm_content=DAGaN1iTQKo&utm_campaign=designshare&utm_medium=link2&utm_source=sharebutton)

我又看到別人去寫 Windows kernel driver 去做（Ring 0）的 rookit，也有打算之後去研究這件事，然後就發現了這個題目。

其實在看 [LKMPG](https://sysprog21.github.io/lkmpg/#system-calls) 的時候看到 system call 那一段，看到怎麼去找到 syscall table 在哪裡，並且怎麼去 hook 它之後，我對這個專題有些具體的想像了。

### [改進 semu: 實作 VirtIO Crypto Device](https://hackmd.io/@sysprog/S18kgVDJex?fbclid=IwZXh0bgNhZW0CMTAAYnJpZBExSjJhUWRVOUlSdTNhOGhleQEeBJSG-fUf9asQ2NO_vf9MxoXlNkrskmU5sDNS5AI3tYcBKM3wqklu_r4c7IM_aem_bymnmVaLVr7bPOatNmJqNw#%E6%94%B9%E9%80%B2-semu-%E5%AF%A6%E4%BD%9C-VirtIO-Crypto-Device)
我對密碼學和系統軟體都有興趣的，只是還不知道這個題目要做什麼。