# 2024q1 Homework5 (assessment)

contributed by < `yinghuaxia` >

### 紀錄閱讀〈[因為自動飲料機而延畢的那一年](https://blog.opasschang.com/the-story-of-auto-beverage-machine-1)〉的啟發

從這個心路歷程的記錄中，我覺得我看到的不僅僅是一個人對於他所做的選擇不放棄的精神，我也在之中獲得了鼓舞。不論是在遇到重重難關所做出的應對，或是經過不斷自我懷疑之後做出延畢的決定，都讓我覺得堅持可以是一個很困難但又很值得的選擇，而跌倒再站起也可以是一個改變人生的信念。從筆者的書寫之中，我也瞥見了從小到大求學歷程問題的冰山一角：

> 紘銘教的這些高頻小套路，瞬間讓大家的焊接技術進步好幾倍，看了除了資工系的學生不會寫程式，機械系的學生不會做機械，現在又多一條電工系的學生不會焊電路，這世界到底怎麼了啊。

這個疑問也曾經出現在大學時期的我的腦海中：我學完這些必修選修的理論課之後，到底會了什麼？修了各個領域的課程，我真的可以說出核心技術的細節嗎？放眼身邊那些能力極佳的同學，他們與我的差異到底是什麼？從現在的角度回頭看，我想某部分得歸咎於我們從來就只是跟著學校規定的上課進度前進，而不是真正了解到實際的需求，再去解決問題；又或者是我們從來就不懂自己喜歡什麼、擅長什麼。

其中，我覺得最受感動的地方在於筆者不斷嘗試學習新的技術、構思遇到問題的解決方式、對自己目標的堅持，即便在最艱難的困境之下也可以果斷地做出決定，熱血的像是動漫的主角，我想，這背後肯定包含了無數的自我否定與自我懷疑，然而他卻能一一克服，並在最後回首時，反思、體認並感謝他所受到的種種幫助，再繼續往人生的下一個階段前進。

> 從來就沒有一件事情是容易的。

自動飲料機的完成是跨過一個個難題才完成的，如果沒有解決問題而是遇到難題就駐足不前，就沒有後面的故事。每一個結果的背後都有著不為人知的汗水與淚水，雖然我們生活的這個世界往往是只看結果的，但是過程卻會在無形之中改變一個人，那就會是一種收穫。「這個世界比任何人都殘酷，也比任何人都公平，犧牲了多少就會得到多少。」以此共勉之。

修 Linux kernel 這門課其實對我而言是個思考良久後做出的決定，考量的原因包含對於韌體一無所知、因應這門課的 loading 所要花費的時間成本、實驗室本身要做的工作、修其他課要寫的作業與要準備的考試等等，都是讓我一開始在決定要不要貿然修課的考量，但後來還是因為這門課據說可以學到很多相關知識所以決定投入這門課。原本在實際參與課程之前秉持的是一個不一定要修完、走一步是一步的態度，但是在實際修課時，往往會被老師的熱忱、同學一起討論作業的努力氛圍所影響，雖然還是只能在有限的時間之內盡量的去閱讀老師的教材和同學們的文件，但是對整個學習的態度有了一點轉變：變得比較願意花時間去做一些沒有人看的見的 dirty work；比起交出作業更想要完全的了解一個議題，而不會去假裝自己有貢獻；比較能夠耐下性子去 trace 一個艱澀但漂亮的 code，這些都是目前修習這門課給我的收穫。能夠認知到自己的不足，並在能力所及的範圍中盡力的吸收知識，是我對自己往後數週繼續修習這門課時的期許。

### 前期作業改進
1. [第四週測驗一](https://hackmd.io/ft3EYSusSS2aLyRicdqTzA?view#%E6%B8%AC%E9%A9%97%E4%B8%801)
:::info
- [x] 為什麼不直接將 n 加 1，而是要使用這種取反再取二補數的方式累加？
> 因為直接將 n 加一會有 overflow 的問題，如果取反再取二補數就可以避免。
- [x] popcount_branchless 為什麼要是 4 個 bit 為單位？
:::
2. [第四週測驗二](https://hackmd.io/ft3EYSusSS2aLyRicdqTzA?view#%E6%B8%AC%E9%A9%97%E4%BA%8C1)
:::info
- [ ] 加上 $23$ 這個數值是否有特別原因？為何需要做 `popcount(n ^ 0x2A) - 3;` 及回傳 `n + ((n >> 31) & 3)`? 是否跟 tic-tac-toe 作業有關連？
> 嘗試將加 23 改成加上一個極大的整數，觀察其結果
:::

3. [作業六](https://hackmd.io/@yinghuaxia/linux2024-homework6)
:::info
- [x] 為什麼要將主設備編號和次設備編號以 20 bit 和 12 bit 的長度進行分配？
> 主設備編號的功能在於唯一識別主要的設備或系統，以確保每個設備在管理系統中都有唯一的標籤，而次設備編號則是用於識別主要設備下的子設備，提供更詳細化的層次管理。也因此主設備的編號必須是唯一的，所以相對於次設備所分配的 bit 數更多。
:::

### 課程教材心得記錄
* #### [Make 語法和示範](https://hackmd.io/@sysprog/SySTMXPvl)
使用 Makefile 和直接使用編譯器進行編譯之間有幾個主要區別：

1. 自動化編譯：Makefile 提供一種自動化編譯的機制，可以根據給定的文件依賴關係來重新編譯必要的文件，進而節省時間並提高效率。如果直接使用編譯器進行編譯，需要手動指定所有的編譯命令，無法自動處理文件依賴關係。

2. 配置管理：Makefile 可以包含各種配置的選項和編譯的參數，讓編譯過程更加靈活和可配置。通過修改 Makefile 中的參數，可以客製化的進行編譯，而直接使用編譯器則需要手動指定所有的編譯參數。

3. 支援跨平台：Makefile 可以根據不同的操作系統和環境配置不同的編譯命令和參數，因此支援跨平台的編譯。與此相比，直接使用編譯器可能會因為不同的操作系統或環境而產生兼容性問題。

4. 依賴管理：Makefile 可以根據文件之間的依賴關係，自動判斷哪些文件需要重新編譯，以確保編譯過程的正確性和一致性。而直接使用編譯器則需要手動處理文件之間的依賴關係。

* #### [Linux: 不只挑選任務的排程器](https://hackmd.io/@sysprog/linux-scheduler)
排程器是一個將任務映射到資源的函數，就是把待辦事項分配給運算單位的系統。舉例來說，Linux (CPU) scheduling 就是把一系列的 process 映射到一個個 CPU core。

有排程器的優點：

- 高效利用資源
- 降低任務和任務在資源之間的耦合度
- Better QoS (Quality of Service)

:::info
- [ ] 不確定耦合度的意思，但我猜這個的意思是一個任務不用一定要等到前一個任務結束之後才能執行，因為他們不一定要使用同一個資源
:::

[Oversubscribed](https://encyclopedia2.thefreedictionary.com/Oversubscribed) 指的是使用少量的資源嘗試完成大量任務的行為，在這種情況下，引入特製的排程器可以支援此種情形。然而排程器本身運算所消耗的資源就是其 tradeoff，測量 reschedule 的時長也是一門學問：其一可以測量的方式是在進入點和出口記錄時間，然後計算數值差距，最後求平均值，但在使用者層級 (userspace) 下很難找到其進入點和出口；其二是將執行時間縮短到無限接近零，讓任務運行的時常約等於 scheduling 花費的時長

* #### [Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree)
紅黑樹是一種[自平衡](https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree)的二叉查找樹，Linux核心中的很多數據結構都使用了紅黑樹。例如，虛擬記憶體系統中的VMA結構，以及擴展性的鎖等等。

> 自平衡樹 : node-based binary search tree that automatically keeps its height small in the face of arbitrary item insertions and deletions.

紅黑樹的每個節點都有一個顏色屬性，可以是紅色或黑色。通過這個顏色屬性，我們可以確保樹的平衡。在插入或者刪除節點時，紅黑樹會通過一系列的旋轉和著色來確保樹的平衡。這樣可以保證對樹進行查找操作的最壞時間複雜度為 $O(\log{n})$。走訪 linked list 的成本過高時，紅黑樹即可勝任。

### 研讀 [CS:APP 3/e 第二章](https://bottomupcs.com/ch02.html)

#### Ch2-1
- 一個 `char` 的大小是一個 byte，基於任何人可能會對 `char` 做自己的定義 (EX: 有人說 1 代表 A，有人說 1 代表 z) ，因此創造一個規定：ASCII(American Standard Code for Information Interchange) 來統一大家對 `char` 與數值映射的意義。ASCII 是一個 7-bit code，因此總共有 $2^7 = 128$ 種可能的組合。
- ASCII code 可以被歸納成兩種: printable (包含大小寫字母、鑄字和標點符號) & non-printable (控制功能為主，像是 [carriage-return](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&cad=rja&uact=8&ved=2ahUKEwihgZTvwr6FAxWMm68BHQpxCVEQmhN6BAhKEAI&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FCarriage_return&usg=AOvVaw12UzFGpnbGCBJVZ5Xe9ZnH&opi=89978449), ring the [terminal bell](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&cad=rja&uact=8&ved=2ahUKEwjn8qSWw76FAxVnbvUHHaQ1CT4QFnoECBAQAw&url=https%3A%2F%2Frosettacode.org%2Fwiki%2FTerminal_control%2FRinging_the_terminal_bell%23%3A~%3Atext%3DIt%2520is%2520usually%2520used%2520to%2Cterminal%2520to%2520ring%2520its%2520bell.&usg=AOvVaw3iv4U4mSBMDryWm7ImCVwE&opi=89978449) or the special `NULL` code)
- ASCII code 轉變為 Unicode (4 bytes) 的動機在於，可以有更多字元被表示 (不只有英文字母)
- 上面提到 ASCII 只是一個 7-bit 的 code，但一個 `char` 卻有 8-bit，剩下的那一個 bit 會被用來實現 [parity](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&cad=rja&uact=8&ved=2ahUKEwjH7tmVxL6FAxUGoK8BHUo2CJMQFnoECA8QAw&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FParity_bit%23%3A~%3Atext%3DParity%2520bit%2520checking%2520is%2520used%2Csimple%25204%252Dbit%2520message%25201001.&usg=AOvVaw2-knDiWT1xuJZgkbd9XE_R&opi=89978449) 。Parity 可以分成 even parity 和 odd parity，以 odd parity 為例，如果在 ASCII code 中，為 1 的 bit 數總和為奇數，則 parity bit 會被設為 1，否則被設為 0。透過這個方式可以避免萬一有一個 bit 在傳送過程中有變導致的錯誤，但如果有偶數個 bit 傳送時有誤一樣沒有辦法被發現。
- 16, 32, and 64 bit computers 的差異在於其內部暫存器的寬度。
- 二進制和十進制的 byte 表示
- 在網路連線中網路或裝置存儲與容量相關的用法中，會使用 bits 而不是 byte 來做表示。
- 電腦幾乎在任何地方使用 boolean 運作子，像是[半加器](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&cad=rja&uact=8&ved=2ahUKEwiNp77AzL6FAxVQlq8BHSBcCEIQFnoECBkQAQ&url=https%3A%2F%2Fzh.wikipedia.org%2Fzh-tw%2F%25E5%258A%25A0%25E6%25B3%2595%25E5%2599%25A8&usg=AOvVaw2g--9DoOwp11cMt53IkoQk&opi=89978449)、電晶體的[邏輯閘](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&cad=rja&uact=8&ved=2ahUKEwj9zvP3zL6FAxX7ja8BHSwHDNIQFnoECBYQAQ&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FLogic_gate&usg=AOvVaw2wjIV_lFq7P5Lwre5yUuQF&opi=89978449)等都會使用到。
- 如果我們想要表示 16 個可能的狀態，我們需要有 4 個 bit，然而我們在 C 語言中一次定義變數的大小最小為 8 bits，我們可以選擇浪費剩餘的 4 個 bits 或是使用 masking 的方式利用那 4 個 bits。想法如下：我們使用這個 8 個 bits 的空間儲存兩個 4 個 bit 的變數，搭配一個 00001111 的 mask 做使用。當我們想要儲存在最低 4 bit 的變數資料十，就拿 mask 對 8 bit 空間做逐個 bit 的 & 運算；若要取得最高 4 bit 的變數時，就將 mask 反轉變成 11110000，一樣做完逐個 bit 的 & 運算之後，將結果右移 4 個位元，讓結果從 abcd0000 變成 abcd 以符合我們的所求。程式碼如下所示：

    char value = 0xA5;
    char lower = value & LOWER_MASK;
    char upper = (value & UPPER_MASK) >> 4;

- Flag 是一種特殊概念的 masking，可以在 state machine 中看到，假設他有 8 個狀態，與其宣告 8 個不同的變數，每個對應一個狀態，不如定義一個 8 bit 的變數，並將每個 bit 分配給特定的狀態。

#### Ch2-2

- ISO/IEC 9899:1999(E)，也被縮寫為 C99，這個標準是用來規範不同系統在使用 C 語言實有不同的編譯。同樣要注意的是 C 標準未定義的內容，因為這個標準需要適用於現在和未來的每種架構。因此標準不對依賴架構(軟體系統中不同元件之間的相互關係，會影響系統的設計、修改和擴展)的區域做定義。 C 標準和底層架構之間的接合是 ABI。
- GNU 編譯器（gcc）幾乎完全實現了 C99 標準。它也實現了一系列的擴充，增加額外的功能。這些擴充功能通常與低階的程式碼相關，常用於 inline assembly code，但代價是犧牲了對另一個編譯器的可移植性。gcc 在執行某些不符合標準的操作時，會發出警告或創建錯誤，有助於我們將程式碼移至另一個編譯器。
- 變數類別的宣告會告訴編譯器我們期望在哪裡儲存這個變數，讓編譯器給定足夠的空間並檢查使用者有沒有違法該類別的規定。
- 64 bit computing 指的是處理器可以處理長度為 64 bits 的位址，同時也代表指標也必須要是 64 bits 才能表示系統中所有的位址。
- 根據以下表格：
我們可以觀察到 `int` 維持 32 bits 而沒有增加到 64 bits 的原因包含：
1. 無法有 32 bit 的變數，除非將 `shorts` 改為 32 bits
2. 很多變數通常不會需要用到 64 bits 來表示
> 我們通常不會需要用到一個 32 bits 的變數來表示迴圈的迭代次數，因此也不會需要用到 64 bits 來作為 int 的大小
3. 整數陣列的大小也會加倍 → 耗費更多系統記憶體與 cache 空間
- [qualifier](https://en.wikipedia.org/wiki/Type_qualifier) 是為了要給編譯器關於變數會如何被使用的資訊，讓編譯器確認你對於變數的使用是否有違反該型別的規定，也同時對根據這些資訊進行優化。
- C99 的 `<stdint.h>` library 中定義了特殊類型的規定，避免各種規則造成的混淆。Library 中採用了 `qtypes_t` 的形式：`q` 是 qualifier、`type` 是基本的形式、`s` 是位元的長度、`_t` 是讓使用者知道他們現在使用 C99 定義類型的擴充。
- 負數的表示方式包含：
- Sign bit：直接在前面加一個 `+` 或 `-`
- 一補數：將正數的所有 bit 取 NOT，優點在於在執行正負數相加時不需要什麼另外的邏輯，除了最高位的進位必須要被加回原數。有一個問題是會有兩個數代表 $0$
- 二補數：將正數的所有 bit 取 NOT 再加一，並且捨棄最高位的進位。優點在於跟 sign bit 表示法相比，不會出現兩個 $0$ 的問題，因此可以表示 $-127$ 到 $128$ 範圍的數字 (sign bit 只能表示 $-127$ 到 $127$)，這也是現在電腦使用的進位方式。
- 當增加一個 signed value 的大小時，必須確保額外的 bit 有進行 sign-extended，也就是複製 MSB 的值。這個動作可以成立的原因如下：假設我們有一個 3 bit 的 binary signed number $A = a_2 \ a_1 \ a_0 = -a_2 \times 2^2 + a_1 \times 2^1 + a_0 \times 2^0$ 要延伸為 4 bit $A^{’} = A = a_3 \ a_2 \ a_1 \ a_0 = -a_3 \times 2^3 + a_2 \times 2^2 + a_1 \times 2^1 + a_0 \times 2^0$，那在延伸之後仍需要符合 $A^{’} = A$ ⇒ $A^{’} - A = 0$ ⇒ $-a_3 \times 2^3 + a_2 \times 2^2 + a_2 \times 2^2 = 0$ ⇒ $-a_3 \times 2^3 + a_2 \times 2^3 = 0$ ⇒ $a_3 = a_2$ 故得證。如果要延伸到更多 bit，則可以根據 $A^{’’’’} = A^{’’’} = A^{’’} = A^{’} = A = ...$ 來推得新延伸的 bit 需要跟 MSB 相同才會讓延伸後的數值與原數值一樣。

Reference： [Signed and Unsigned Numbers](https://chi_gitbook.gitbooks.io/personal-note/content/signed_and_unsigned_numbers.html)
- 在浮點數表示中會對指數進行了一個偏移，使得可以表示負指數。這個偏移值稱為 bias。根據 IEEE 754 標準，通常使用的 bias 為 127。也就是指數欄位為 0 時，則表示的指數為 -127，如果指數欄位為 127，則表示的指數為 0，如果指數欄位為 126，則表示的指數為 -1（實際值為 0）。

### 期末專題

1. 打造 Linux 虛擬攝影機裝置驅動程式：[Link](https://hackmd.io/@sysprog/linux2023-projects#%E6%89%93%E9%80%A0-Linux-%E8%99%9B%E6%93%AC%E6%94%9D%E5%BD%B1%E6%A9%9F%E8%A3%9D%E7%BD%AE%E9%A9%85%E5%8B%95%E7%A8%8B%E5%BC%8F)
在文件的描述中提到，開發一個虛擬的攝影機也可以了解資訊安全的幫助，基於現在大家對資安的重視，讓我也想要透過這個專案嘗試探索資安的領域。

2. 透過 Netfilter 自動過濾廣告：[Link](https://hackmd.io/@sysprog/linux2023-projects#%E9%80%8F%E9%81%8E-Netfilter-%E8%87%AA%E5%8B%95%E9%81%8E%E6%BF%BE%E5%BB%A3%E5%91%8A)
廣告一直都是在瀏覽網頁時惱人的存在，之前有看到有人在使用 Youtube 時選擇安裝[廣告加速器](https://chromewebstore.google.com/detail/ad-speedup-skip-video-ads/pcjlckhhhmlefmobnnoolakplfppdchi)來讓廣告可以以高倍速播放，讓使用者幾乎看不到廣告的同時，也避開 Youtube 偵測廣告攔截器的機制。如果可以直接在核心層級過濾網路的廣告，或許也可以不用使用到廣告加速器，直接從根本解決問題。

3. 完成 ttt project：[Link](https://github.com/jserv/ttt)
由於時間的原因，我並沒有實作 ttt 的作業，但裡面有包含一些對弈演算法的理解與實作、coroutine 的概念、PRNG 原理等是我想要了解的，因此也將 ttt project 納入我的期末專題考量之一。

TODO: vcam
TODO: 看 https://hackmd.io/@Masamaloka/linux2022-vcam 並紀錄問題
TODO: Ubuntu Linux 24.04 (w/ Linux v6.8)