HackMD
2022q1 Homework6 (ktcp)
contributed by < zoanana990 >
自我檢查清單
- kecho
- 給定的
kecho已使用 CMWQ，請陳述其優勢和用法 - 核心文件 Concurrency Managed Workqueue (cmwq) 提到 "The original create_
*workqueue() functions are deprecated and scheduled for removal"，請參閱 Linux 核心的 git log (不要用 Google 搜尋!)，揣摩 Linux 核心開發者的考量 - 解釋
user-echo-server運作原理，特別是 epoll 系統呼叫的使用 - 是否理解
bench原理，能否比較kecho和user-echo-server表現？佐以製圖 - 解釋
drop-tcp-socket核心模組運作原理。TIME-WAITsockets 又是什麼？ - khttpd
- 參照 fibdrv 作業說明 裡頭的「Linux 核心模組掛載機制」一節，解釋
$ sudo insmod khttpd.ko port=1999這命令是如何讓port=1999傳遞到核心，作為核心模組初始化的參數呢？ - 參照 CS:APP 第 11 章，給定的 kHTTPd 和書中的 web 伺服器有哪些流程是一致？又有什麼是你認為 kHTTPd 可改進的部分？
htstress.c用到 epoll 系統呼叫，其作用為何？這樣的 HTTP 效能分析工具原理為何？
作業要求
- 在 GitHub 上 fork kecho，目標是修正
kecho的執行時期的缺失，提升效能和穩健度 (robustness)- 若使用者層級的程式頻繁傳遞過長的字串給
kecho核心模組，會發生什麼事？ - 參照 kecho pull request #1，嘗試比較 kthread 為基礎的實作和 CMWQ，指出兩者效能的落差並解釋
- 如果使用者層級的程式建立與
kecho核心模組的連線後，就長期等待，會導致什麼問題？ - 研讀 Linux Applications Performance: Introduction，嘗試將上述實作列入考量，比較多種 TCP 伺服器實作手法的效能表現
- 若使用者層級的程式頻繁傳遞過長的字串給
- 在 GitHub 上 fork khttpd，目標是提供檔案存取功能和修正
khttpd的執行時期缺失。過程中應一併完成以下:- 指出 kHTTPd 實作的缺失 (特別是安全疑慮) 並予以改正
- 引入 Concurrency Managed Workqueue (cmwq)，改寫 kHTTPd，分析效能表現和提出改進方案，可參考 kecho
- 實作 HTTP 1.1 keep-alive，並提供基本的 directory listing 功能
- 可由 Linux 核心模組的參數指定
WWWROOT，例如 httpd
- 可由 Linux 核心模組的參數指定
文獻回顧
kecho
給定的 kecho 已使用 CMWQ，請陳述其優勢和用法
- 簡介
- 有很多情況需要用到執行非同步行程時而工作佇列 (workqueue) 的 API 就是最常用到這個機制的情況
- 當需要非同步行程，一個工作項目描述該函式執行是放在一個列隊中。一個獨立的執行緒作為非同步執行上下文，稱為 workqueue，而執行緒稱為 worker
- 當工作佇列上面有工作項時，就會依序執行 work item，列隊上沒有東西的時候則會空閒，當一個新的工作項目進入列隊後會再繼續執行。
- 為什麼需要 CMWQ?
- 最初的工作佇列中，多執行緒 (multithread) 的工作佇列是每個 CPU 就有一個工作執行緒，而單執行緒的工作佇列為系統範圍內統一使用一個工作佇列。每個多執行緒的工作佇列需要保持和 CPU 數量相同的 worker。
- 多執行緒的工作佇列使用了許多資源，但是發揮出並行的效果卻不盡人意。 Work Item 必須競爭那些非常有限的上下文，這會引發許多問題，這也對導致用戶必須為了並行和資源之間進行不必要的權橫，這也引發了並行管理工作佇列 (CMWQ) 的開發，主要關注以下幾點目標：
- 和原始的工作佇列保持相容性
- 使用每一個 CPU 統一個工作池 (Worker Pools) 根據不同需求提供彈性的並行級別，減少資源浪費
- 自動調節工作池與並行級別，使 API 用戶不需要擔心這些細節
- CMWQ 的設計
- 為了簡化非同步執行引入了工作項 (work item) 的概念，工作項的結構很簡單，它包含一個指向非同步執行函式的指標。每當子系統或是驅動程式想要非同步執行函式時他必須設置一個指向函式的工作項，並將該工作項排入工作佇列中。
- 工作池由工作執行緒管理，其主要執行工作佇列的功能
- CMWQ 設計區分了子系統與驅動程式的工作項與後端機制
- 兩個工作池，一個用在正常的工作項目，另外一個用在高優先級的工作項目
- 子系統和驅動程式會根據他們合適的工作佇列的 API 函式來創建和排列工作項，他們可以通過不同的 flags 來判斷工作項的執行方式
- 當工作項進入工作佇列後，根據列隊參數和工作佇列屬性工作池，並附加工作池的共享工作佇列中。
- 對於任何工作池的實現， CMWQ 嘗試將並行保持在最低但是足夠的水平，最大限度節省資源
- 當 worker-pool ?，worker-pool 都會收到通知，並跟踪當前可運行的工作人員的數量。通常，工作項不會佔用 CPU 並消耗很多周期，只要 CPU 上有一個或多個可運行的 worker，worker-pool 就不會開始執行新的工作，但是，當最後一個運行的 worker 進入睡眠狀態時，它會立即調度一個新的 worker，以便 CPU 不會當有待處理的工作項時，不要閒著。
- 除了 kthread 的記憶體空間之外，保持空閒的 worker 不會花費其他成本，因此 cmwq 在釋放它們的系統資源之前，會保留空閒的 worker 一段時間。
- 總整 CMWQ 的優勢
- 相較於傳統的工作佇列需要考慮 CPU 調用的問題，CMWQ 使用 worker-pool 全部幫開發者處理好，可以用最少的資源做最多的事
- 相容於原本的程式開發介面
核心文件 Concurrency Managed Workqueue (cmwq) 提到 "The original create_*workqueue() functions are deprecated and scheduled for removal"，請參閱 Linux 核心的 git log (不要用 Google 搜尋!)，揣摩 Linux 核心開發者的考量
- 參考 oscarshiang/kecho
- 題目中提到 "The original create_*workqueue() functions are deprecated and scheduled for removal" 原始的 create_*workqueue() 函式已經棄用，請說明原因，這裡主要先關注幾個
commit - 輸入命令
- 輸出結果示例，下面會以這裡列出的 commit 進行舉例：
- 首先從 oscarshiang 提到這個 commit 寫到將
create改成alloc是因為目前的 workqueue 趨於複雜，若是改寫函式要將整塊相關函式都進行改寫非常不便如 workqueue: introduce create_rt_workqueue 中提到的創造create_rt_workqueue。尷尬的是，在 workqueue: kill RT workqueue 中馬上把create_rt_workqueue刪除，下面可以看到兩個 commit 改寫的程式碼：
引入 workqueue: introduce create_rt_workqueue 時做的改動：
刪除 workqueue: introduce create_rt_workqueue 時做的改動：
可以發現如果要引入一個 create_rt_workqueue，儘管只是多加一個變數，整段程式碼都要重寫，這是一個非常不明制的手法，最後要拿掉 create_rt_workqueue 時，需要把整段刪除，最後甚至改回引入前的程式碼。
上面的現象證實引入新的概念對於程式碼改棟宇維護成本過高，這也就是為什麼要引入 alloc_workqueue() 這個概念，對於函式改寫有許多幫助，以下面的 commit 進行舉例：
新增 high priority workqueue
remove WQ_SINGLE_CPU and use WQ_UNBOUND instead
可以看到引入工作佇列的 flag 之後，對於維護程式碼的成本大幅度的降低，對於新增、修改僅需要改動 workqueue flag 這個 enum 就好，這也是為什麼將 create_*workqueue() 移除的原因
解釋 user-echo-server 運作原理，特別是 epoll 系統呼叫的使用
根據 CS:APP 第十一章中說明伺服器的運作方式：
圖片來源： CS:APP 第十一章
圖中可以看到連線分為 client 與 Server 兩端。
Server 端會利用 socket 創造一個監聽器，經過 bind, listen 兩個函式做好接收連線的準備，若是直接進行 accept 連接客戶端的話，會有效率不夠的問題，因為一次盡能對一個客戶連線。
因此在 CS:APP 第十二章有說明可以使用 select 函式使多個 clent 進行連接，但是由於 select 效率不彰，因此 kecho 使用 epoll 進行實做，使用這種多執行緒的方式就可以達到下圖的效果：
圖片來源： CS:APP 第十二章
下面進行程式碼原理的追蹤說明：
建立一個監聽器，利用 man page 及 CS:APP 可知，socket 是回傳一個檔案描述子 (file descriptor)，如果產生失敗則回傳 -1
由 Linux 核心設計：事件驅動伺服器之原理和實例中提到 non-blocking I/O ，setnonblock 是將監聽器的描述子設定為 non-blocking ，程式碼如下：
宣告 epoll_event ，程式碼如下：
這段程式碼的幾個重點如下，以下資料來源為 Linux Programmer's Manual，這裡順帶介紹其他在這個專案中用到的 epoll 函式：
epoll：epoll是類似於poll的 API，目的在於監視大量的檔案描述子是否可以進行 I/O，epoll API的核心概念是epoll instance，這是 linux 核心內部的資料結構，以 user space 的角度來看，它被視為兩個串列：- interest list：監測檔案描述子的集合
- ready list：為 I/O 準備好的檔案描述子的集合，其為 interest list 的子集合
常見函式：
epoll_create：創建epoll instance，如果不需要用到時，使用close關閉。回傳值為一個檔案描述子 (file descriptor)。過去需要提供epoll instance的大小以利於 linux 核心分配空間，現在都是動態分配，但是為了向前兼容，仍然需要填入一個大於 0 數字。epoll_ctl：對interest_list中的epoll_instacce加入、移除或修改。取決於不同操作 op 對於目標檔案描述子 fd- 函式形式：
EPOLL_CTL_ADD: 將 fd 添加到 interest list ，並根據 event 連接到 fd 的內部文件。EPOLLIN: epoll 讀取模式EPOLLET: epoll 邊緣觸發模式，預設是 level trigger 模式
epoll_wait：- 函式形式
*event：同epoll_ctlmaxevents：事件數量，須大於 0timeout：指定epoll_wait阻塞的豪秒數，時間的量測方法是根據CLOCK_MONOTONIC的方式，直到：- 檔案描述子傳到一個事件
- 時間失效
- 中斷
- 如果
timeout = -1，則無限期的阻塞；如果timeout = -1則立刻回傳
- 回傳值：成功時，epoll_wait() 回傳準備好給 I/O 的檔案描述子的數量，如果超時，回傳 0。發生錯誤時，epoll_wait() 回傳 -1。
接下來就近如連線階段，通常會使用一個 while 迴圈進行訊息間的傳遞：
創造一個 client_addr，用 epoll_wait 找到準備好 I/O 的 epoll_instance 的數量，如果事件的描述符為 listener 則會建立新連線，並且把 client 也設為 nonblocking I/O 。連線完成後，會將客戶端的 epoll_instance 加入 instance_list 中，並把已經連線好的 client 加入 client_list_t 這個鏈結串列中。
如果事件描述符不是連線，則會進入 handle_message_from_client 的函式中。
在 handle_message_from_client 函式中，這裡主要看兩個函式：
recv：讀取client的描述符寫入buf中。回傳 0，代表連線被關閉；回傳 -1，代表錯誤產生；正常來說回傳寫入 buf 的數目send：將buf的資料傳向fd這個描述符，len為 byte 作為單位。 send 回傳實際傳送資料的長度 ，若錯誤則回傳 -1
是否理解 bench 原理，能否比較 kecho 和 user-echo-server 表現？佐以製圖
首先說明 bench.c 的原理，這裡我先觀察 bench 的函式
首先看到 create_worker 函式，在 bench.c 中的註解有提到預設開啟的執行緒是 1000，這裡可以根據註解的提示看到我使用的電腦最多可以開啟的執行緒：
create_worker 的目的是創造 thread_qty 個執行緒。創造方式則是使用 pthread_create
查看 linux programmer's manual 中的 pthread 相關函式
pthread_createpthread_cond_waitpthread_mutex_lock,pthread_mutex_unlockpthread_cond_broadcastpthread_joinpthread_exit
比較 kecho 和 user-echo-server 的效能
-
user-echo-server 的效能
- 用兩個終端機，一個輸入
./user-echo-server，另外一個輸入./bench
- 用兩個終端機，一個輸入
-
kecho 的效能
- 用兩個終端機，一個輸入
sudo insmod kecho.ko，另外一個輸入./bench
- 用兩個終端機，一個輸入
解釋 drop-tcp-socket 核心模組運作原理。TIME-WAIT sockets 又是什麼
## TODO ##
TIME_WAIT
依據 TIME_WAIT and its design implications for protocols and scalable client server systems:
drop-tcp-socket 核心模組運作原理
參考 The Linux Kernel Module Programming Guide Chapter 7
khttpd
參照「Linux 核心模組掛載機制」，解釋 $ sudo insmod khttpd.ko port=1999 這命令是如何讓 port=1999 傳遞到核心，作為核心模組初始化的參數呢？
由 khttpd 原始碼：
由上面的程式碼可知，端口是由 module_param 這個函式進入的，而因為上面的巨集預設為 8081，因此若不特別指定，都是使用 8081 作為輸入端口
這裡需要觀察 module_param 的原始碼，moduleparam.h，這裡我們將 module_param 展開：
可以看到上面的巨集分為三個部份：
param_check_##type(name, &(value))module_param_cb(name, ¶m_ops_##type, &value, perm)__MODULE_PARM_TYPE(name, #type)
複習前置處理器和連結器和執行檔資訊
#: Stringification Operator, e.g.:#abc→"abc"##: Concatenation, e.g.:a##b→ab- 使用
objdump查看記憶體存放的情況- 產出：
- 在
modinfo這個區段中可以看到有模組的名稱、授權條款類型、版本等資訊
param_check_##type(name, &(value))
由 moduleparam.h 的註解說明可以透過 param_check_##type 定義自己所需類型的變數
param_check_##type: for convenience many standard types are provided but you can create your own by defining those variables.
巨集module_param_cb(name, ¶m_ops_##type, &value, perm)
由於巨集中多次使用 __attribute__，因此先對巨集中提到的 __attribute__ 進行基本的了解：
unused- 原文表示，它可能不會被用到，希望 GCC 不要對這個沒有用到的函式跳警告
This attribute, attached to a function, means that the function is meant to be possibly unused. GCC does not produce a warning for this function.
- 原文表示，它可能不會被用到，希望 GCC 不要對這個沒有用到的函式跳警告
__section__- 通常，編譯器將它生成的物件放在 data 和 bss 等部分中。但是，有時我們需要將資料放在其他地方，最好是可以讓我們指定存放地點，這類的巨集在撰寫核心模組時非常容易遇到。
Normally, the compiler places the objects it generates in sections like data and bss. Sometimes, however, you need additional sections, or you need certain particular variables to appear in special sections, for example to map to special hardware. The section attribute specifies that a variable (or function) lives in a particular section.
- 上述的巨集中，
__section__ ("__param")，資料會在連結時期將資料放到指令區段後產生 elf 檔案，也正是如此，可以指定輸入時使用的port，其產生的資料如下：
- 通常，編譯器將它生成的物件放在 data 和 bss 等部分中。但是，有時我們需要將資料放在其他地方，最好是可以讓我們指定存放地點，這類的巨集在撰寫核心模組時非常容易遇到。
aligned: 該屬性規定變數或結構體成員的最小的對齊格式，以位元組為單位。This attribute specifies a minimum alignment for the variable or structure field, measured in bytes.
此時可以看到 __module_param_call 的目的就是為了對 struct kernel_param 進行初始化，並且可以自行命名。由上面的巨集，可以看到 struct kernel_param 扮演著重要的角色，原始碼如下：
將結構與巨集展開如下所示：
將上面的巨集展開得
這裡有一個比較特別的點是 S_IRUGO 這個讀取權限，由官方文件可以知道 S_IRUGO=S_IRUSR | S_IRGRP | S_IROTH ，由 CS:APP 第十章可以得知這三個遮罩的意思：
| Mask | Description |
|---|---|
| S_IRUSR | User (owner) can read this file |
| S_IRGRP | Members of the owner’s group can read this file |
| S_IROTH | Others (anyone) can read this file |
由上表知， S_IRUGO 是唯讀的意思。
繼續展開上面的巨集：
這邊有兩個巨集需要進行展開，這裡先展開 module_param_cb：
將巨集進行展開得：
針對上面的巨集，這裡進行查詢：
__moduleparam_const這裡可以看到如果它不是const就是空白，原始碼如下：MODULE_PARAM_PREFIX，根據原始碼的定義，如果MODULE存在，MODULE_PARAM_PREFIX就是空的
將巨集展開後的結構如下所示：
可以看到這個巨集主要是對 kernel_param 這個結構體進行參數傳遞，僅憑此巨集無法充分回答這個問題，因此下面從另外一個角度進行切入。
由 Linux 核心模組運作原理中提到，可以利用 strace，進行 insmod 的追蹤，這裡進行 insmod 分別有指定 port 值與沒有，結果如下所示：
- 這邊因為卸載核心模組，隨即掛載，因此這邊可以看到其返回值為
-1
上面可以看到，輸出結果都有 finit_module(3, "", 0)。也就是說，有沒有指定值，命行列的 port 都會將值傳給 finit_module 中，這裡我們可以參考 man: finit_module及 module.h 程式碼：
上面是相關系統呼叫 (System Call) 的描述，這裡針對幾個地方進行追蹤：
-
load_info：這個結構真的有夠大，原始碼在這，主要就是將模組的資訊進行讀取 -
may_init_module函式定義如下capable：被定義在 capability.h 中，僅是用來回傳布林值CAP_SYS_MODULE：被定義在 capability.h 中，註解中提示到僅是用來掛載或卸載核心模組，且修改時不能有任何的限制Insert and remove kernel modules - modify kernel without limit
modules_disabled：被定義在 module.c 中，作為模組是否被抑制的布林值EPERM：這是錯誤碼，被定義在 error-base.h 原始程式碼如下： 也就是這個動作沒有權限
-
kernel_read_file_from_fd：根據檔案描述子讀取檔案，原始碼 (kernel_read_file.c) -
module_decompress：原始碼在這，目的是將讀取進來的模組進行解壓縮 -
load_module：定義在 module.c ，這個函式比較複雜，這裡分段進行探討，其宣告如下：info是紀錄模組中二進位的訊息uargs是 user space 傳入的字串
-
嘗試解讀
struct module- 記錄模組的二進位訊息
-
嘗試解讀
module_sig_check- 定義在
kernel/module.c - 這裡主要是檢查模組有沒有簽名，沒有的話會報錯
- 定義在
-
嘗試解讀
elf_validity_check- 定義在
kernel/module.c - 這個函式是針對二進位的檔案、錯誤的 arch 及奇怪的 elf 檔案進行檢查，當然對最基本的區段偏移量、大小及索引都有驗證的作用
sanity checks against invalid binaries, wrong arch, weird elf version. Also do basic validity checks against section offsets and sizes, the section name string table, and the indices used for it (sh_name).
- 定義在
-
嘗試解讀
setup_load_info- 定義在
kernel/module.c - 主要用途：初始化模組，讀取各個 section 將其載入模組中
- 這個函式主要是將不同 section 的資訊讀取到
struct load_info *info中，下面舉幾個例子說明 - 將
section header的起始地址紀錄到info->sechdrs- 這裡可以用
readelf指令進行說明，輸入命令： - 輸出
- 這裡可以關注一行
- 就是這一行被讀進去
- 這裡還有另外一個例子，從 section table 中找到
.modinfo將他的地址紀錄到info->index.info中。- 這裡我使用另外一個指令查看
- 輸出
- 這樣可以找到
.modinfo的區段並且將他的位址與偏移量記錄下來，這可以用另外一個指令
- 這裡可以用
- 嘗試解讀
blacklisted- 定義在
kernel/module.c - 這裡是檢查模組的名稱，在黑名單中的模組不會被讀取
- 定義在
- 嘗試解讀
rewrite_section_headers- 定義在
kernel/module.c - 將所有 section 中
sh_addr和地址載入記憶體中，然而 section 中__version與.modinfo不會載入記憶體，其細節在setup_load_info的函式中
- 定義在
uargs是port傳入引數的地方strndup_user就是將字串從 user_space 複製到 kernel 中，這也是為什麼資料可以傳進來
parse_args，類似於 python 的 parser，可以將命令行的引述傳入parse_args定義於 linux/kernel/params.c中- 其中，
parse_args還有使用到parse_ones的函式 parse_args會取得命令行的所有引數，並將這些引述使用parse_one一個一個進行處理，丟入struct module中，達到傳值得效果- 這裡看到
struct module這個結構，前面只有介紹這個結構是用來紀錄二進位的資訊，這裡會在進行兩點的介紹- 第一個是
enum module_state，這個列舉裡面包含四個型態，註解如下 - 第二個是前面提到的
args，這裡就是終端機傳遞引數的位置
- 第一個是
- 定義在
前面還有一個重點， THIS_MODULE 的使用，其實 THIS_MODULE 就是一個全域變數
此時可以看到 finit_module 在文件中寫到他是一個考慮到檔案描述子 (File Descriptor) 的 init_module
參照 CS:APP 第 11 章，給定的 kHTTPd 和書中的 web 伺服器有哪些流程是一致？又有什麼是你認為 kHTTPd 可改進的部分？
由 CSAPP 第十一章所提到的 web 伺服器流程如下：
圖片來源： CS:APP 第十一章
由上圖可知， CS:APP 第十一章的 server 並沒有使用多執行緒，且是運行在 user-space 的。
接下來看 khttpd 的程式碼。在 The Linux Kernel Module Programming Guide 的第二章提到模組是由 __init 的函式開始，在 __exit 的函式結束。
這裡先從 static int __init khttpd_init(void) 函式開始探究。在 khttpd_init 函式中，分為兩個部份與一個意外處理：
- 函式：
open_listen_socketkthread_run
- 意外處理：
close_listen_socket
open_listen_socket 中進行了幾件事：
socket的創建與設定kernel_bindkernel_listen
kthread_run 是創造一個執行 http_server_daemon 函式的執行緒，其定義如下：
上面可以看到 kthread_run 其實是用來呼叫 kthread_create_on_node 的函式，根據其註解可以得知 kthread_create_on_node 可以創造並命名一個核心執行緒，註解中也有提到停止執行緒需要使用 kthread_stop 或是 kthread_should_stop 。理解完 kthread_run 的作用後，接下來對於 kthread_run 創造的執行緒所需要執行的 http_server_daemon 進行探討：
由上面的原始碼得知， args 會放 socket 型態的引數，這裡有一個比較特別的點：
這裡是允許使用 SIGKILL 與 SIGTERM 這兩種訊號，其中
SIGKILL：無條件停止執行緒，這個訊號無法被忽略也無法被處置(例如：中途停止)，因此這個訊號非常危險SIGTERM：停止執行緒，相較於SIGKILL這個訊號比較「有禮貌」，它可以被中途停止、忽略
參考： CS:APP 第八章
這裡來說明程式碼中的函式：
kthread_should_stop：根據kthread_stop與其本身的註解可以得知，kthread_stop無法停止threadfn，但是透過kthread_should_stop即可實現。總之這是一個查看木閒的執行緒是否需要停止的函式。kernel_accept：類似於 user-space 的accept
其中，http_server_daemon 對於已經成功連接的 socket 會創建新的執行緒進行，這裡我們來探討 http_server_worker 的作用為何
函式的一開始對於 http_parser 進行設定，這裡我們來了解它的設定，然而，這些函式的引數是 http_parser ，這裡需要先對於這個結構進行解析：
由原始碼可以看到， http_parser 這個結構空有一個空型態的指標進行 socket 的儲存，而下面幾個函式也只有應用到這個結構成員，因此我們對其他的結構成員暫時不進行討論。
然而，下面的函式還有用到另外一個結構 http_request，這裡我們來看一下原始碼：
上面有一個列舉空間 enum http_method 這個被定義在 http_parse.h 中，其主要是定義 http 連接的動作。
http_parser_callback_message_begin：初始化 http_request
http_parser_callback_request_url：request 中的 request_url 與 p 進行串連，這裡可能會有安全問題，因為 request_url 僅有 128 位元的空間，若是 len 超過 128 或是 request_url 本身的長度與 len 的和大於 128 會有不可預期的錯誤，這裡要特別注意。
http_parser_callback_message_complete：這裡將 request 傳送到 server 中，傳送後將 request->complete 設定為 1 代表要求以完成，這裡我們發現傳送的過程是由 http_server_response 進行，因此這裡研究一下 http_server_response 這個函式：
上面的程式碼中有看到 HTTP_RESPONSE_200 與 HTTP_RESPONSE_501 ，根據 mozilla 提供給開發者的文件中提到這幾個狀態， HTTP 的回應狀態總共有五大類：
- 資訊回應 (Informational responses, 100–199)
- 成功回應 (Successful responses, 200–299)
- 重定向 (Redirects, 300–399)
- 用戶端錯誤 (Client errors, 400–499)
- 伺服器端錯誤 (Server errors, 500–599)
根據上面的敘述可以看到 HTTP_RESPONSE_200 代表伺服器成功回應…
- 200：請求成功。成功的意義依照 HTTP 方法而定：
- GET：資源成功獲取並於訊息主體中發送。
- HEAD：entity 標頭已於訊息主體中。
- POST：已傳送訊息主體中的 resource describing the result of the action。
- TRACE：伺服器已接收到訊息主體內含的請求訊息。
- 501：無法執行。服務器不支援這種請求格式，以本專案來說，服務器僅支持 HTTP_GET 。
The request method is not supported by the server and cannot be handled. The only methods that servers are required to support (and therefore that must not return this code) are GET and HEAD.
連線成功後使用 http_server_send 函式進行資料的傳送，由於資料傳送是傳送到 linux 核心中，因此 http_server_send 使用 kvec 這個結構進行傳輸，這裡看部份的程式碼：
根據 kvec 其定義如下：
會使用 kvec 結構主要是需要符合 kernel_sendmsg 的定義。在 while 迴圈中，會先將尚未發出的字串放入 kvec ，kernel_sendmsg 會回傳已經傳出去的字串長度，當所有字串都發送出去後，迴圈停止。
到目前為止，我們已經了解了 http_server_worker 的基礎設定，接下來我們繼續探討 http_server_worker 這個函式。
接續前面，這裡開創一個字串空間給接收到的字串，空間大小被定義為 4096，這裡會發生第二個危險，若是字串大於 4096 的話會發生字串無法順利接收的情況。
http_server_recv 接收的方式其實也是使用 kernel_recvmsg 進行接收，而 kernel_recvmsg 則是回傳接收字串的長度，當然接收的結構也是使用 kvec 。
最後任務結束時， socket 及 buf 都會被釋放。
總結 khttpd 的原理，這裡以圖像的方式進行呈現：
## TODO： 作圖與總結 ##
htstress.c 用到 epoll 系統呼叫，其作用為何？這樣的 HTTP 效能分析工具原理為何？
首先從 main 函式開始看起， main 函式中分為兩個部份：
- 訊號處理、解析函式與連線
- epoll 系統呼叫
訊號處理、解析函式與連線
在 main 函式中，常常看到有許多類似下面程式碼：
在 CS:APP 第八章第五節中提到幾種 linux 核心接收到的訊號，如下表所示，由鍵盤引發的中斷給出的訊號為 SIGINT，中止行程的訊號為 SIGTERM，這裡可以看 CS:APP 第八章的表格，表格如下。上面的程式碼則是查看接收到什麼需要做出的應對事件。
接下來說明 khttpd 裡面接收終端機參數的處理：
由你所不知道的 C 語言: 執行階段程式庫 (CRT)中提到執行時期接收到的參數，文章中提到一個連結，文章中提到若是僅有一個引數，則 argc = 1 且 argv[0] = ./...。以 htstress.c 為例，若僅輸入下面的命令：
則 argc = 1 且 argv[0] = ./htstress。此時，正好觸發程式碼中的判斷式，顯示出如何使用 ./htstress 的資訊，如下：
接下來就是解析如何使用這些變數，如 -n, -c 等等。根據 Linux Programmer's Manual 得知 getopt_long 的函式結構與描述：
getopt 和 getopt_long 都可以解析終端機的引數 (arguments) ，差別在於 getopt 僅能解析以 - 形式開頭的參數，例如：-v, -h；相反的，getopt_long 可以解析以 -- 開頭的參數，例如：--help 等等。參數開頭應該使用 - 或是 -- 在下面會進行說明，兩個函數會依序回傳終端機的引數。
這裡先從函式的引數 (Argument) 開始著手，其中：
argc代表傳數的引數個數argv代表傳數的引數字串。舉例來說： 則我們可以得到：argv[0] = ./htstressargv[1] = http://localhost:8081/
optstring
根據 Linux Programmer's Manual 得知，optstring是裝著引數的種類，中間用:分開。longopts在這個結構中，name代表的是引數名稱，例如：help。而has_arg則是查看這個引數是否有附帶參數，0 為沒有，1 為必須有附帶參數，2 為選擇性。*flags則是指定引數回傳結果，若是NULL則是回傳到val
以htstress.c為例，longindex這個參數這裡暫時不討論，通常是使用NULL
在 htstress.c 中，這裡使用 while 迴圈與 switch，將引數一個一個解析。
在終端機引數的最後放入想要連接的網址，然而，如何透過輸入網址進行連線呢？這裡我們繼續追蹤程式碼。
這裡我們先看怎麼進行連線的，這裡是使用 getaddrinfo 進行連線，而函式定義如下：
getaddrinfo 將主機名稱、主機地址與連接埠 (port) 傳換成 struct socket 的形式。若是傳換成功則回傳 0，否則回傳錯誤碼。其中， node 為網域名稱，或是 IP 地址、 service 是連接埠的編號。轉換的結果放入 res 的鍊結串列中。htstress.c 的程式碼如下：
接下來利用兩個例子說明連接時 node 與 port 分別為何：
案例一、連接 http://localhost:8081/ 。此時 node = localhost 而 port = 8081
案例二、連接 http://www.google.com/ 。此時 node = www.google.com 而
port = http
呼叫 getaddrinfo 成功後，會開始走訪 struct addrinfo 鍊結串列，如下圖，嘗試進行 bind 和 connect，若是調用成功，則會建立起連結。
圖片來源： CS:APP 第十一章
程式碼如下：
在這個部份的最後， htstress.c 使用 pthread_create 創造多執行緒，開始進行測試：
在 for 迴圈中創造多執行緒進行測試，而最後的 worker(0) 則是使用主執行緒進行測試，這樣可以避免浪費任何一個運算資源，增加程式效率。
上面的 num_threads 預設值是 1，而 num_threads 可以透過終端機進行修改，終端機參數為 -t。
epoll 系統呼叫
前面提到使用 pthread_create 時，每個執行緒都要執行 worker 這個函式，連主執行緒也不例外，這裡讓我們查看 worker 函式的作用。
一開始先利用 epoll_create 創造 epoll_instance，由 linux 核心 2.6 之後，輸入的值沒有意義， epoll_create 會根據需求動態創建。
接下來是使用 for 迴圈對每個 epoll instance 進行 init_conn，因此這裡進行 init_conn 函式的探究。在 init_conn 函式中，主要執行以下步驟，函式詳情請參照Linux 核心設計：事件驅動伺服器之原理和實例及解釋 user-echo-server 運作原理，特別是 epoll 系統呼叫的使用一節中所提到的函式：
- 將
ec->fd與sss進行連線，並且將ec->fd設定為 Non blocking I/O - 將事件為設定寫入狀態 (EPOLLOUT)
- 利用
epoll_ctl將ec->fd加入到efd中。
接下來進入無窮迴圈 for(;;)：
由解釋 user-echo-server 運作原理，特別是 epoll 系統呼叫的使用一節中可知 epoll_wait 是回傳 ready_list 中的個數，其中 ready_list 是進行 I/O 的鍊結串列。當 epoll_wait 執行結束後會根據四個不同的事件狀態執行對應的程式碼：
- EPOLLERR：發生錯誤
- EPOLLHUP：被中止
- EPOLLOUT：寫入
- EPOLLIN：讀取
其中， 1 和 2 都是錯誤的時候進行的處理，因此這裡我們著重 3 和 4。每個預設的 epoll_event 都是 EPOLLOUT。因此每個事件處理都是先進行訊息發送，當訊息發送結束後會將 epoll_event 改為 EPOLLIN，request + 1。當訊息發送結束後會進行訊息接收，一樣的是，訊息接收成功後也會將 request + 1 ，並且會開始檢查所有 request 是否執行結束，若執行完則呼叫 end_time 函式，結束計時。
開發紀錄
kecho
若使用者層級的程式頻繁傳遞過長的字串給 kecho 核心模組，會發生什麼事？
這裡參考 bench.c 撰寫 test.py 進行大小為 5000 的隨機字串以 1000 個執行緒進行發送，測試其發送的字串與接收的字串是否相同。結果是有時候會有漏字或是缺字的情況，測試程式碼在這。
使用 dmesg 查看 kecho 的訊息可以看到當有漏字的情況時，出現以下的錯誤：
由 linux error number 得知出現這個號碼的主因是連線出現問題
因此這進行 kecho_mod.c, echo_server.c 與 echo_server.h 三個檔案的探討，解讀為什麼是「有時候」會有這種現象，並且進行解決方法的開發。
首先查看 kecho 的運作原理。在 kecho_init_module 已經使用 CMWQ 進行 kecho 的運作。
參照 kecho pull request #1，嘗試比較 kthread 為基礎的實作和 CMWQ，指出兩者效能的落差並解釋
由 kecho pull request #1 提到，kthread 和 CMWQ 的實作效率差了近十倍，但是上面也提到，kecho 已經使用 CMWQ 進行實做，因此這裡可以參考 khttpd 的實做，將 kecho 改為 kthread 的版本。
程式碼改動：commit
效能比較：
- kthread-based kecho
- CMWQ based kecho
khttpd
指出 kHTTPd 實作的缺失 (特別是安全疑慮) 並予以改正
在「參照 CS:APP 第 11 章，給定的 kHTTPd 和書中的 web 伺服器有哪些流程是一致？又有什麼是你認為 kHTTPd 可改進的部分？」一節中提到 khttpd 總共有兩個安全上的問題：
http_parser_callback_request_url在傳入字串時並沒有長度的檢查- 進行
http_server_recv時可能因為buf的大小不足而有資訊接受不完全的危險 (–TODO–)
對於第一種情況，需要在傳入字串之前進行檢查，字串長度是否超過 127 (第 128 位為結束字元)，程式改動部份如 Fix request function security problem ，這裡老師有提起一個問題，將程式碼的 127 改掉，減少維護上的成本，更新的程式碼如 Avoid hard code 127
引入 Concurrency Managed Workqueue (cmwq)，改寫 kHTTPd，分析效能表現和提出改進方案，可參考 kecho
修改前：
修改後：
程式碼已經提交成 commit
Directory Listing 的實做
參考陳日昇同學的作業。
欲進行 Directory Listing 的實做需要考慮幾件事：
- 將資訊傳入網頁的語法
- 讀取目錄、檔案
- 考慮副檔名，根據不同副檔名開啟檔案，須考慮 MIME 的實做
- 加入 WWWROOT
第一個是 HTTP 連線的方式，這裡參考 HTTP_RESPONSE_200_DUMMY 的傳送格式：
在上面這段程式碼內容格式是 text/plain ，而這種內容的傳送會根據後面的撰寫的內容長度傳送。然而 text/plain 對於超連結並不好傳送，因此這裡我使用 text/html 的方式進行。
這裡就需要看到 HTML 的格式規範，
這裡比較特別的是 Content-Type 的格式不同，這裡按照不同的檔案格式，這裡詳細格式如 MIME ，其中 Content-Length 是要發送文字的長度。
第二個是讀取目錄及檔案，參考這篇文章，雖然內容年代有點久遠，但是仍有參考之處：
- 參考
linux/fs.h，查看裡面的結構- 由上面的文章可知，走訪整個目錄的檔案需要用到
struct dir_context,iterate_dir及filp_open等函式
- 由上面的文章可知，走訪整個目錄的檔案需要用到
- 參考 Overview of the Linux Virtual File System 及 Linux 核心設計: 檔案系統概念及實作手法 理解虛擬檔案系統的概念。
Question
在 Linux 核心設計: 檔案系統概念及實作手法 中提到下面這張圖，file object 需要找到對應的 dentry object 再找到 inode，而 inode 才是檔案主體。然而，根據 linux/fs.h 原始碼中的第 925 行 struct file 的宣告，我發現 file object 內並沒有 dentry object，此外 inode 被放在 struct file 中。這是不是代表其實並不需要 dentry_object?
閱讀完上面的文獻並實做後暫時的成果如下
然而目前遇到連線不穩定的問題。
使用命令 dmesg 後發現，錯誤代碼為 104，查詢錯誤代碼後，
會出現連線不穩的錯誤主要是傳輸資料的格式錯誤，傳送字串長度須為 16 進位，非 10 進位，當傳送長度改為 16 進位後即可。
接下來是點開連結後無法進入新的位置的問題，這裡觀察連線到根目錄的網址：
點擊任何一個目錄的網址：
可以發現因為網址的變化導致連線中斷，這裡需要修改連線進入目錄的問題。
將原本的使用的 memset 換成字串串連即可。
目前已經可以走訪每個目錄，現在需要根據副檔名打開各種檔案
加入 MIME 打開副檔名
參考 MIME-TYPE 將檔名打入 mime.h 中
雜湊表結構：
目前雜湊表已經實做完成，輸入附檔名會輸出對應的 HTTP 打開方式
但是時裝到 kernel 時遇到一些問題：
主要程式的改動在 commit 將重複定義的地方刪除，這裡出現另外問題，這主要是路徑上的問題：
TODO
這裡有收到老師的訊息，接下來使用 kernel 的 hashtable API 改寫。
實作 HTTP 1.1 keep-alive
比較 HTTP 1.0 與 HTTP 1.1 的差別：
HTTP 1.0 的主要缺點是，每個 TCP 只能發送一個請求。當資料發送結束，則連線關閉，如果需要請求其他資源，則需要在進行一次連線。
然而， TCP 的新建連線成本很高，需要客戶端 (Client) 與伺服器 (Server) 進行三次握手，這會大幅度的降低資料吞吐量。
為了解決這個問題，HTTP 1.1 中引入了 keep-alive 的連線方式，在一段時間內不要關閉連線，可以讓連線重複使用，如果發現一段時間沒有使用時，則主動關閉連線。不過通常是客戶端在最後一個請求時，可以發送 Connection: close ，這種方式就是持久連線 (Persistent Connection)。
先前與老師討論的過程中，有提到參考 sehttpd 的 HTTP 1.1 實做方法。
這裡簡述了一下 sehttpd 的流程：
mainloop.c 是將
Priority Queue 與 Timer 實做
應說明程式碼改寫的動機，而非急著張貼程式碼。
jserv
這裡主要是將 sehttpd 中的 timer.h 及 timer.c 進行改寫：
