# 2024q1 Homework5 (assessment)
contributed by < [han1018](https://github.com/Han1018) >

## 前 4 週的測驗題選出 3 題改進

## 研讀第 1 到第 6 週「課程教材」
### 數值系統
電腦中僅管 2's complement 加法行成阿貝爾群概念(特性：單位以及反元素唯一)，但僅是整數，浮點數在 IEEE 754 中無法被滿足，因為 INF、NaN 是例外狀況他們沒有對應的反元素。如：NaN + fx = NaN; (3.14 + 1e10) - 1e10 = 0.0 (單精度 fraction 為 2^24 - 1，1e10 - 3.14 差異 > 2^24 - 1 能表達的範圍)。

使用 bitwise 操作可以節省記憶體開銷外還可以加速。
- 大小寫互轉 ('A' | ' ') // 得到 'a'
- Count Leading Zero
- 只要算高位有幾個 0's bits. 再用 31 減掉即可。

    define LOG2(X) ((unsigned) \
       (8 * sizeof (unsigned long long) - \
       __builtin_clzll(X) - 1))

-「__builtin_xxx」 提供數個好用的 built-in function。e.g., __builtin_clz(開頭有幾個 0), __builtin_ffs（從低位元找第一個 1 的位置）

### Bitwise 操作
無號數與有號數不應混用，因為在運算子操作會有意外的結果。如負值會大於正值的情形，因為混用時有號數會被轉換為無號數，e.g, -1 與 0U 比較 -1 會變成 unsigned 然後大於 0。

- Set a bit : `unsigned char a |= (1 << n);`
- Clear a bit : `unsigned char b &= ~(1 << n);`
- Toggle a bit : `unsigned char c ^= (1 << n);`
- Test a bit : `unsigned char e = d & (1 << n); `
- The right/left most byte : `unsigned char right = val & 0xff;`
用 `& 0xff` 取出要的 Byte
- 取出要的 bit : `bool sign = val & 0x8000; // sign bit`

### [開發工具和規格標準](https://hackmd.io/@sysprog/c-standards#%E4%B8%8D%E8%A6%81%E6%80%A5%E8%91%97%E5%8D%B0%E5%87%BA%E4%BD%8D%E5%9D%80%EF%BC%8C%E5%96%84%E7%94%A8-GDB)
> C++ 自稱為物件導向的程式語言，卻不願意對物件在執行時期的表現負責任
:::info
不能理解這一段「執行時期的表現負責任」意思。對照 Linus 撰寫的[「文章」](https://www.realworldtech.com/forum/?threadid=104196&curpostid=104208) ，是指說 C++ 在 GC 複雜度表現不如 C 的機制穩定嗎，或是有其他意思。
:::

- & 不要都念成 and，涉及指標操作的時候，要讀為 "address of"
- object : 指在執行時期，資料儲存的區域，可以明確表示數值的內容
- [GDB 學習](https://www.slideshare.net/owenhsu/introduction-to-gdb-3790833)
- 增加 degub 功能：gcc -g
- 顯示 warning : gcc -Wall
- backtrace / info stack ：觀看此位置的 function call 過程
- [info frame](https://sourceware.org/gdb/current/onlinedocs/gdb.html/Frame-Info.html) : 以副程式為單位分成一個個的區塊 (frame)。可以觀看此 frame 有關的地址(e.g., 變數、上/下一個 frame 的地址)
- the address of the frame
the address of the next frame down (called by this frame)
the address of the next frame up (caller of this frame)
the language in which the source code corresponding to this frame is written
the address of the frame’s arguments
the address of the frame’s local variables
- disassemble [addr] 反組譯指定記憶體位置程組合語言
- 基礎操作：run / break [function / line] / watch [variable] / continue / list / print [val] / next /step
- display [var] 斷點時自動顯示變數

### 記憶體管理、對齊及硬體特性
:::warning
對照閱讀 x86-64 ABI 規格。
:::

編譯器在<s>分配</s> 配置記憶體時，會按照宣告的型態去做 alignment 對齊 4 的倍數，即使使用的大小只有 1 byte，電腦也會給他 4 byte 。避免資料不在 4 的倍數上導致存取速度降低。
- 64-bit 的系統下，malloc 則會以 16 bytes 進行對齊
> In the GNU system, the address is always a multiple of eight on most systems, and a multiple of 16 on 64-bit systems.

> 對應的實驗，malloc 在 Linux x86_64 以 16 bytes 對齊：

for (int i = 0; i < 10000;  ++i) {
    char *z;
    z = malloc(sizeof(char));
}

:::info
這段程式我用 GDB 觀察，z 的地址是以 32B 增加而不是 16B，想請問老師原因。
z = 0x5555555593c0, 0x5555555593e0, 0x555555559400, 0x555555559420, ...
:::

### 未定義行為
- Signed integer overflow：需加上 -fno-strict-overflow 和 -fwrapv 來提醒 Signed integer overflow 。
>overflow of a signed value is undefined behavior

不然會當出現 overflow 又被最佳化掉條件判斷，會有負數 > 正數的情形可能出現。

- Shifting an n-bit integer by n or more bits
- Bitwise 操作時位移數量大於/等於被位移的位元數量。e.g., `int i = 23; i <<= 32;`

### CS:APP 第二章

## 閱讀〈因為自動飲料機而延畢的那一年〉與課程啟發
### 閱讀心得
這篇文章中看到很多個我不足的面向，尤其是當我聽到 Jserv 講的一句話

>你不能現在就放棄，要是現在就放棄的話，你這輩子日後遇到這種等級的困難，就只會想逃避而已 --- Jserv

聽到這句話時腦袋像是被用力錘了一下打醒，打醒遇到困難就想逃避，做作業時想走捷徑，學東西時只想速成卻又要看起來很厲害的自己。當遇到程式寫不出來時現在真的已經養成上網找答案、問 ChatGPT、查關鍵字有沒有人做過，搬運別人的程式的習慣，非常愧對於資訊工程的工程解決能力。從來沒有非常認真、擠出十萬分力氣的把一件事解決或是從頭到尾把一門學科學的徹底，如同 Jserv 所說的以為自己資料結構考到好分數就認為自己學好了資料結構。

下面是整篇文章中我覺得重量最重的一段：
> 人不付出犧牲，就得不到任何回報。如果要得到什麼，就必須付出同等的代價，這就是鍊金術的基本原則，等價交換。當時我們深信著，這就是這世界的真理。------《鋼之鍊金術師》

當我羨慕碩班/大學同學在專題上侃侃而談時，另一面在實驗室裡我是看到他們熬到半夜來弄清楚程式運作原理，他們是付出同等努力才能顯的自信，擠出了全力才能看得輕鬆。我用 cp 值的概念放在學習上，想要用少少的時間得到好的結果，沒有洞見只會永遠追不上別人的腳步、人云亦云。
### 課程心得
到第六週前對 C 的學習一直停留在我會使用指標、結構、巨集。第一次開始看規格書、暸解 Bitwise 以及它怎麼用少少的程式碼完成一樣的功能，知道了 C 語言中有記憶體對齊特性、數值系統、編譯器會優化哪些結構等等。對比之前的程度可以說以前完全不會寫 C。而我付出的努力仍然不夠說到我對於 C 有暸解，很多 C 語言章節只能說淺嚐，無法細嚼裡面的內容加以內化。但六週的課程內容加上 Lab0 的訓練後可以說我能寫出 C 的程式而且真真實實的感覺到自己在變強，學習到了新知識。我撰寫到 Lab0 的亂數部分時發現到時間複雜度原來是用統計方式證明出來的，檢驗虛無假說、選擇自由度、查表顯著水準結果，讓其不拒絕虛無假說。實作到這ㄧ段時候有種身心暢快的感覺，看到了 O(1) 的樣子。

實驗室計劃每週三咪、修課以及其作業就已經佔掉一週一半以上的時間，就算將剩下的三四天完全投入在這門課上依然不夠，我要補的漏洞依然永遠補不完，但依然得補齊。得「誠實面對自己」才能面對龐大的 Linux 核心，翻閱了考研的作業系統筆記重新查看「排程器」、「同步」章節搭配 Linux 核心課程相關章節的歷史典故、背後原理才漸漸明暸搭建真實的世界的同步與排程器是多麽的困難和精巧。尤其在排程器章節中講到 bitarray + priority queue 時做出 O(1) 複雜度時，真的才發現 bitwise 操作的美！空間複雜度小、時間複雜度也小。而在多執行緒程式設計章節中，是讓我疑惑最多的地方，寫一個安全的程式也太難了！只是為了讓更多核心使用到程式。因此也想要駕馭它，了解以及寫出安全且快速的程式。

## 簡述想投入的專案

想要增加軟韌體作品集因此期末專題中選擇投入 kernel driver 有關的專案，有點功利導向。此外雖然多執行緒程式設計還不算熟練但對於那邊有好奇心，想要寫出高速且安全的程式，因此選擇下面有興趣的專案。

目前自身程度還無法提出改善專案或是進一步擴展專案功能的洞見，以及不知道程度是否匹配這幾項專案，或是對於我來說過於困難。需要與老師進一步討論，如果老師覺得有更適合我的專案，我也傾向選擇老師的意見。

#### [kHTTPd](https://github.com/sysprog21/khttpd) 改進
目前還沒開始 [ktcp](https://hackmd.io/@sysprog/linux2023-ktcp/%2F%40sysprog%2Flinux2023-ktcp-d) 作業，不過有觀察到裡面有用到 khttpd 核心模組可以用來熟悉 kernel driver 掛載、寫程式操作等功能，以及作業中也有要實作 Concurrency 的功能，希望可以在作業結束後進一步改進成為一個作品集。而且這個專案有比較完整的資料介紹，可以讓我比較有頭緒的知道專案架構。
> todo:
> - Release resources when HTTP connection is about to be closed.
>- Introduce CMWQ.
>- Improve memory management.
>- Request queue and/or cache

嘗試找尋可改進空間，提升並行的吞吐CMWQ
- 方向：
- 實作 todo list
- 給定的 kHTTPd 和書中的 web 伺服器有哪些流程是一致、又有什麼是別人開發紀錄中 kHTTPd，可改進的部分？
- 找出與 Kecho/ktcp 專案中一致與不一致的地方，嘗試提出 kHTTPd 可改進的部分。
- [2022 開發紀錄](https://hackmd.io/eMLoZzjcRFyd-nSTGuL_4Q?view#%E5%9F%B7%E8%A1%8C-http_server_worker) 這一篇蠻完整的
- 現行 http1.1 與 [HTTP/2.0](https://en.wikipedia.org/wiki/HTTP/2) 的差異，有無可改進/升級的空間？同時向下相容 http1.1。參見 [issue](https://github.com/sysprog21/khttpd/issues/11) 回覆
- 參照 [2022 開發紀錄](https://hackmd.io/eMLoZzjcRFyd-nSTGuL_4Q?view#%E5%9F%B7%E8%A1%8C-http_server_worker) - 使用 MIME 處理不同類型的檔案。延伸，找尋可加速/擴充的空間，e.g., 有沒有可能擴展成像雲端硬碟？

- Resources
- 背景：kecho - [執行在 Linux 核心模式的 TCP 伺服器](https://hackmd.io/@sysprog/linux2023-ktcp/%2F%40sysprog%2Flinux2023-ktcp-a)
- [掛載模組的說明](https://hackmd.io/@Risheng/linux2022-khttpd#%E6%8E%9B%E8%BC%89-khttpd-%E6%A8%A1%E7%B5%84)
- 引入 [CMWQ](https://hackmd.io/@Risheng/linux2022-khttpd#%E5%BC%95%E5%85%A5-CMWQ-%E5%88%B0-khttpd) 的方式是否有可改進空間？
> 使用函式 alloc_workqueue 建立 CMWQ ，而這裡有個需要注意的地方，也就是參數 flag 的值會根據需求而不同，根據 kecho 的註解說明，如果是想要長時間連線，像是使用 telnet 連線，可以把 flag 設成 WQ_UNBOUND ，否則設成 0 即可。自己實際兩個都設定過，的確使用 WQ_UNBOUND 的效率沒有來的非常好，主要原因可能是 work 可能會被 delay 導致，也有發生測試的時候電腦當機的情況

- 提問
- kHTTPd 的開發紀錄似乎沒有送 PR，要 fork 哪一位同學的以及要基於哪一個專案延伸開發？
-
- 觀察
- 掛載初始化程式
使用了一個 kthread 執行 http_server_daemon 接受 client 連線。 假設有多個 CPU 可以初始化多個 kthread 嗎？進而 ...

    static int __init khttpd_init(void)
    {
        int err = open_listen_socket(port, backlog, &listen_socket);
        if (err < 0) {
            pr_err("can't open listen socket\n");
            return err;
        }
        param.listen_socket = listen_socket;
        http_server = kthread_run(http_server_daemon, &param, KBUILD_MODNAME);
    

#### vwifi 虛擬無線網路裝置驅動程式和實驗環境
和 realtek 公司的工作職缺描述接近，如果能完成期末專題救可以有即戰力，有點功利導向。是一個新的領域需要具有 wifi 相關的知識，覺得挑戰過大。

#### 以 eBPF 建構 TCP 伺服器
可以延伸 kHTTPd 的內容，之前有操作過基礎的 socket 傳輸，覺得自己較能勝任。這項專案有較於其他專案還沒有開發的非常完整，可以想撰寫一些新的功能，並熟悉電腦網路在 kernel space 的流程。


TCP 3-way handshake? SYN

ktcp ?
core 核
kernel 核心
worker pool
限制 TCP 伺服器並行處理的因素？

problem statement