## Linux 核心專題：kHTTPd 改進
> 執行人: w96086123
> [專題解說錄影](https://youtu.be/Cb4Q2oCgNzE)
### Reviewed by `SimonLee0316`
利用 hashtable 建立cache 的方式儲存每個連線的時間，請問在這個實作中每個連線的重新發送一個請求就會在更新一次 cache 值嗎？
## 任務簡介
改進 kHTTPd 的並行處理能力，予以量化並有效管理連線。
## TODO: 閱讀 CS:APP 第 11 章
> 紀錄對電腦網路的認知
> TCP 3-way handshake 為何要？
> L2 -> L4 的分工和作用
> Ethernet frame 大小？
> ICMP 封包大小？
### TCP 3-way handshake 為何要？
:::danger
注意用語
* data 是「資料」，而非「數據」
* 是電腦「網路」，而非「網絡」
務必使用本課程教材規範的術語！
:::
TCP 使用 3-way handshake 的主要原因有以下幾點：
1. 初始化序列號：
3-way handshake 中的一個關鍵步驟是交換初始序列號。這些序列號對於後續的資料傳輸非常重要：
1-1. 序列號的作用：
初始序列號在交握過程中被交換，並用於標記後續資料包的順序。這樣可以確保資料包能夠按照正確的順序被接收和處理。TCP 使用這些序列號來進行資料包的排序和重傳，以確保資料傳輸的可靠性和完整性。
1-2. 資料包重傳和排序：
如果資料包在傳輸過程中丟失或順序錯亂，TCP 可以根據序列號進行重傳和排序。這確保了即使在不可靠的網路環境中，資料也能夠正確無誤地被傳輸和處理。
1-3. 資料傳輸一致性：
通過使用序列號，TCP 能夠保證資料在網路中傳輸的一致性，避免資料丟失或重複接收。
2. 確保雙方處於可以同步的狀態
2-1. 同步狀態確認：
三次交握過程中，客戶端和服務器互相交換初始序列號，這確保了雙方的資料傳輸是在同一個基準點上開始的。這樣可以避免資料包因網路延遲、丟失或重傳等問題導致的不同步狀況。
2-2. 資料傳輸可靠性：
確保雙方都已經準備好接收和發送資料，這樣可以避免資料包的錯誤傳輸或重傳，從而保證資料傳輸的可靠性。例如，如果雙方未同步，可能會出現資料包無法正確識別的情況，導致資料丟失或重複接收。
2-3. 避免資料包錯誤：
當前客戶端和服務器都處於同步狀態時，可以避免由於網路不同步或其他技術問題（如路由延遲）而導致的資料包錯誤，從而確保資料傳輸的完整性和正確性。
3. 避免舊資料干擾
3-way handshake 也有助於防止舊資料包對新連接的干擾：
3-1. 避免重複和舊資料包：
當前的連接使用了新的序列號，每次建立連接時，TCP 會分配一個新的初始序列號。這確保了即使之前的連接已經關閉並建立了新連接，舊的資料包（帶有舊序列號）也不會干擾新連接。舊資料包會因為序列號不匹配而被丟棄。
3-2. 網路延遲和資料包識別：
在一些情況下，資料包可能因為網路延遲等原因滯留在網路中。通過每次連接使用不同的序列號，TCP 可以識別並丟棄這些過期或重複的資料包，防止其影響新連接。
3-3. 序列號的唯一性：
TCP 序列號具有唯一性，每個連接的序列號範圍是不同的，因此即使同一個 IP 和通訊埠組合重新建立連接，因為序列號的不同，也不會接收到舊資料包的影響。
### L2 -> L4 的分工和作用
每層加入不同的標頭並解析這些標頭，是為了確保數據能夠在複雜的網路環境中正確且高效地傳輸。
* L4 (傳輸層) (Transport Layer)
主要動作：加入傳輸標頭（TH）與解析傳輸層標頭
功能：
* 傳輸層負責提供端到端的通信服務，確保資料能夠可靠且有序地從一個設備傳送到另一個設備。
* 增加傳輸標頭（TH），包含以下關鍵資訊：
* 源通訊埠號：標識資料來源的通訊埠。
* 目的通訊埠號：標識資料目標的通訊埠。
* 序列號：用於封包排序，確保資料按正確順序重組。
* 確認號：確認接收到的封包，確保資料傳輸的可靠性。
* 協定類型：如 TCP 或 UDP 。
解析傳輸標頭：
* 接收方在解析封包時，會查看傳輸標頭以了解資料的源通訊埠、目的通訊埠及其他控制信息，然後將資料傳遞給相應的程式。
* L3 (網路層) (Network Layer)
主要動作：加入網路標頭（NH）與解析網路層標頭
功能：
* 網路層負責封包的路徑選擇和轉發，並加上網路標頭（NH），形成完整的封包。
* 網路標頭包含邏輯位址（IP 位址），標識網路中的設備，確保封包可以在不同的網路節點之間正確轉發。
作用：
* 路由選擇 (Routing)
* 根據網路拓撲和當前網路狀況選擇最佳路徑。
* 使用路由協定（如 OSPF）來更新和維護路由表。
* 邏輯位址分配
* 提供全球唯一的邏輯位址系統（如IP位址），保證資料能夠在不同網路之間正確傳送。
解析網路標頭：
* 接收方會檢查網路標頭中的IP位址，確定封包是否到達最終目的地或需要繼續轉發。
* L2 (資料鏈路層) (Data link Layer)
主要動作：加入資料鏈結串列頭（DLH）和資料鏈結串列尾（DLT）與解析資料鏈路層標頭
功能描述：
* 資料鏈路層負責物理尋址、錯誤檢測和校正，確保資料能夠在同一網段內可靠傳輸。
* 資料鏈路層會將封包加上資料鏈結串列頭（DLH）和資料鏈結串列尾（DLT），形成資訊框（Frame）。
作用：
* 資料鏈結串列頭（DLH）
* 包含實體位址（如MAC位址）和錯誤檢測信息。
* 實體位址用於識別網路中的設備。
* 資料鏈結串列尾（DLT）
* 包含錯誤檢測碼（如FCS），用於檢測和校正數據傳輸過程中的錯誤。
解析資料路層標頭：
* 接收方會檢查資料鏈結串列頭中的實體位址，確認是否是目標設備，並通過資料鏈結串列尾的錯誤檢測碼檢查封包完整性
資料鏈路層可進一步分成兩個子層：
* 邏輯鏈路控制 (LLC) 子層
* 負責流量控制、錯誤檢測和封包的分段和組合。
* 提供統一的接口給上層網路層，隱藏不同物理媒介的差異。
* 媒介存取控制 (MAC) 子層
* 管理對共享媒介的存取控制，確保各設備在網路中不會發生資料碰撞。
* 定義物理位址（MAC 位址）以唯一標識網路中的設備。
:::danger
注意用語：access 是「存取」，而非「訪問」(visit)
參見[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)和[詞彙對照表](https://hackmd.io/@l10n-tw/glossaries)
:::
### Ethernet frame 大小？
在乙太網路 ( Ethernet ) 中，資料的傳輸單位是 Ethernet frame。
每個 Ethernet frame 以 Header 、 Data 、 Trailer 三個部分組成，每個 frame 長度有一定的規範，以下為各部分的規範：
* Header
* 目的位址： 6 Bytes
* 源位址： 6 Bytes
* EtherType： 2 Bytes
* Data
* 最小長度： 46 Bytes
* 最大長度： 1500 Bytes
* Trailer
* FCS ( Frame Check Sequence )： 4 Bytes
由上述可以每個 Ethernet frame 最小為 64 Bytes ， 最大為 1518 Bytes 。
另外在 Ethernet frame 有以下的動作：
* 若資料不足 46 Bytes 時，則會填充至 46 Bytes。
* 當資料過大，大於 1500 Bytes 時，會進行拆分傳輸，並且在接收端進行重組。
* 另外 FCS 則用於錯誤檢測，確保傳輸過程 frame 沒有遺失資料。
### ICMP 封包大小？
參考於[維基百科](https://en.wikipedia.org/wiki/Internet_Control_Message_Protocol)
圖片參考至 [IT邦幫忙](https://ithelp.ithome.com.tw/articles/10301220)
:::danger
注意術語，查閱國家教育研究院的雙語詞彙。
:::
ICMP 封包由兩個主要部分組成： ICMP 頭和 ICMP 資料。這個 ICMP 封包通常嵌入在一個 IP 封包中，由 IP <s>頭</s> 封裝。
* ICMP 頭
* 大小： 8 Bytes
* 內容：
* Type ( 1 Byte ) ：表示 ICMP 類型，譬如：請求、回應等等
* Code ( 1 Byte )：輔助定義 Type 的子類別
* Checksum ( 2 Bytes )： 檢測 ICMP 封包是否有錯誤
* Rest of header ( 4 Bytes)： 根據上述三種類別進行變化
* ICMP 資料
* 大小：可變化，最低可以為 0 ， 之後根據 RFC 791 ， IP 封包大小不能超過 576 Bytes 。且 IP 頭標準大小為 20 Bytes ， ICMP 頭為 8 Bytes ，因此資料最大為 548 Bytes
* 內容：回應主要內容為錯誤訊息
因此 ICMP 封包最小為 8 Bytes 。
## TODO: 改進 kHTTPd
> 以 [ktcp](https://hackmd.io/@sysprog/linux2024-ktcp) 的 kHTTPd 為基礎，提升其並行處理能力，予以量化並有效管理連線
### 引入 CMWQ ，並且分析效能
參考 [ktcp 作業流程](https://hackmd.io/@sysprog/linux2024-ktcp/%2F%40sysprog%2Flinux2024-ktcp-c)，將 CMWQ 引入至 khttp 中
整理過後的整體程式流程為：
1. 建立 CMWQ
2. 連線建立後建立 work，並將此 work 加入至 workqueue 進行管理
3. work 開始執行
4. work 結束時，釋放所有記憶體
:::danger
減少非必要的縮排。
:::
- [ ] main.c
建立 CMWQ
在 `khttp_init` 中建立 workqueue 。
```
// create CMWQ
khttpd_wq = alloc_workqueue(MODULE_NAME, 0, 0);
```
- [ ] http_server.h
使用 `http_service` 管理 workqueue ，`http_request` 管理 request ，workqueue 、 work 都使用 `list_head` 方式進行連接。
```c
// manage workqueue
struct httpd_service {
bool is_stopped;
struct list_head head;
};
// manage work
struct http_request {
struct socket *socket;
enum http_method method;
char request_url[128];
int complete;
struct list_head node;
struct work_struct khttpd_work;
};
```
- [ ] http_server.c
建立 work : `create_work`
為每個連線請求進行 `kernel space` 的動態記憶體配置，並透過 `INIT_WORK` 為此請求進行初始化，再透過 `list_add` 加入至 workqueue 中
:::danger
注意書寫規範：
* 程式碼註解不該出現中文，總是用美式英語書寫
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
:::
```c
static struct work_struct *create_work(struct socket *sk){
struct http_request *work;
// alloc size of http_request
if (!(work = kmalloc(sizeof(struct http_request), GFP_KERNEL)))
return NULL;
work->socket = sk;
// initialization work ，and work http_server_worker
INIT_WORK(&work->khttpd_work, http_server_worker);
list_add(&work->node, &daemon_list.head);
return &work->khttpd_work;
}
```
釋放記憶體： `free_work`
用於釋放為建立連線所分配的記憶體空間，使用 `list_for_each_entry_safe` 巨集走訪每個在 `workqueue` 中所管理的 `work` 。
```c
static void free_work(void){
struct http_request *l, *tar;
/* cppcheck-suppress uninitvar */
list_for_each_entry_safe (tar, l, &daemon_list.head, node) {
kernel_sock_shutdown(tar->socket, SHUT_RDWR);
flush_work(&tar->khttpd_work);
sock_release(tar->socket);
kfree(tar);
}
}
```
在 `http_server_daemon` 中將上述兩個函式加入
主要為修改執行方式與釋放方式，原有的方法是使用 `kthread_run` 建立並執行，因此需要改成使用 `create_work` 建立 work 且使用 `queue_work` 來執行此請求，最終結束時將此 `workqueue` 設定為停止狀態，並且利用 `free_work` 進行記憶體釋放。
:::danger
注意書寫規範：
* 程式碼註解不該出現中文，總是用美式英語書寫
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
:::
``` diff
while (!kthread_should_stop()) {
int err = kernel_accept(param->listen_socket, &socket, 0);
if (err < 0) {
nt http_server_daemon(void *arg)
pr_err("kernel_accept() error: %d\n", err);
continue;
}
- worker = kthread_run(http_server_worker, socket, KBUILD_MODNAME);
+ // Create worker by CMWQ
+ worker = create_work(socket);
if (IS_ERR(worker)) {
pr_err("can't create more worker process\n");
continue;
}
+ // start server workqueue
+ queue_work(khttpd_wq, worker);
}
+ daemon_list.is_stopped = true;
+ free_work();
```
引入 CMWQ 之後，在處理 200000 的請求明顯可以在處理速度上加快了約 1.3 倍。
:::danger
量化解釋改進的幅度，理論依據在哪？
:::
```
origin: CMWQ:
requests: 200000 requests: 200000
good requests: 200000 [100%] good requests: 200000 [100%]
bad requests: 0 [0%] bad requests: 0 [0%]
socket errors: 0 [0%] socket errors: 0 [0%]
seconds: 3.597 seconds: 2.741
requests/sec: 55594.719 requests/sec: 72953.615
```
### 提供目錄檔案存取功能
#### Directory list
主要流程：
1. 進行 method 判斷。由於此功能設定為 GET，因此對於非 GET 方法，回傳 501 狀態。
2. 判斷設定的路徑是否存在，若不存在則回傳 404 狀態。
3. 判斷此路徑是否為資料夾，若是則走訪此資料夾；若是檔案，則讀取檔案內容。
3.1 由於在走訪過程中無法得知整體長度，因此需要在走訪過程中直接發送資料，而非等待全部走訪完成後再統一處理並傳送資料。
- [ ] http_server.c
在 `http_server` 中新增兩個函式 `handle_directory` 與 `tracedir` 。
在 `handle_directory` 主要處理流程中的判斷與讀取檔案內容。
```c
static bool handle_directory(struct http_request *request)
{
struct file *fp;
char pwd[BUFFER_SIZE] = {0};
if (request->method != HTTP_GET) {
send_http_header(request->socket, HTTP_STATUS_NOT_IMPLEMENTED,
http_status_str(HTTP_STATUS_NOT_IMPLEMENTED),
"text/plain", 19, "close");
send_http_content(request->socket, "501 Not Implemented");
return false;
}
catstr(pwd, daemon_list.dir_path, request->request_url);
fp = filp_open(pwd, O_RDONLY, 0);
if (IS_ERR(fp)) {
send_http_header(request->socket, HTTP_STATUS_NOT_FOUND,
http_status_str(HTTP_STATUS_NOT_FOUND), "text/plain",
13, "Close");
send_http_content(request->socket, "404 Not Found");
return false;
}
if (S_ISDIR(fp->f_inode->i_mode)) {
char buf[SEND_BUFFER_SIZE] = {0};
request->dir_context.actor = tracedir;
snprintf(buf, SEND_BUFFER_SIZE, "HTTP/1.1 200 OK\r\n%s%s%s",
"Connection: Keep-Alive\r\n", "Content-Type: text/html\r\n",
"Keep-Alive: timeout=5, max=1000\r\n\r\n");
http_server_send(request->socket, buf, strlen(buf));
snprintf(buf, SEND_BUFFER_SIZE, "%s%s%s%s", "<html><head><style>\r\n",
"body{font-family: monospace; font-size: 15px;}\r\n",
"td {padding: 1.5px 6px;}\r\n",
"</style></head><body><table>\r\n");
http_server_send(request->socket, buf, strlen(buf));
iterate_dir(fp, &request->dir_context);
snprintf(buf, SEND_BUFFER_SIZE, "</table></body></html>\r\n");
http_server_send(request->socket, buf, strlen(buf));
kernel_sock_shutdown(request->socket, SHUT_RDWR);
} else if (S_ISREG(fp->f_inode->i_mode)) {
char *read_data = kmalloc(fp->f_inode->i_size, GFP_KERNEL);
int ret = read_file(fp, read_data);
send_http_header(request->socket, HTTP_STATUS_OK,
http_status_str(HTTP_STATUS_OK), "text/plain", ret,
"Close");
http_server_send(request->socket, read_data, ret);
kfree(read_data);
}
filp_close(fp, NULL);
return true;
}
```
:::danger
directory 是「目錄」，而非「檔案夾」
:::
在 `tracedir` 中，主要處理的為走訪<s>資料夾</s> 中內容，並且在走訪的過程中就會進行傳送。
```c
static bool tracedir(struct dir_context *dir_context,
const char *name,
int namelen,
loff_t offset,
u64 ino,
unsigned int d_type)
{
if (strcmp(name, ".")) {
struct http_request *request =
container_of(dir_context, struct http_request, dir_context);
char buf[SEND_BUFFER_SIZE] = {0};
snprintf(buf, SEND_BUFFER_SIZE,
"<tr><td><a href=\"%s\">%s</a></td></tr>\r\n", name, name);
http_server_send(request->socket, buf, strlen(buf));
}
return true;
}
```
#### Initital Path
流程：
1. 先在 `main.c` 裡面設定初始位置
2. 在 `handle_directory` 中將 `request url` 與初始位置組合
```c
// main.c
if (!*WWWROOT)
WWWROOT[0] = '/';
daemon_list.dir_path = WWWROOT;
```
在 `http_server` 中，新增處理路徑合併的函式 `catstr` ，並且在 `handle_dirctory` 中使用此函式
```c
// http_server.c
static void catstr(char *res, char *first, char *second)
{
int first_size = strlen(first);
int second_size = strlen(second);
memset(res, 0, BUFFER_SIZE);
memcpy(res, first, first_size);
memcpy(res + first_size, second, second_size);
}
```
#### Use Chunk to send data
在不使用 chunk 作為傳輸的時候可能會出現以下問題：
1. 高延遲
如果需要等待整個資料處理完畢後再進行傳輸，會產生較高的延遲，尤其是在資料量較大時，更容易發生此問題
2. 記憶體壓力
由於需要等待資料處理完畢之後才進行送出，因此會占用需多記憶體空間，導致空間不足
3. 錯誤處理困難
當在傳輸的過程中出現錯誤，此時就需要重新處理與傳輸，因此增加了處理的複查度與時間
4. 使用體驗不佳
因為上述所提到的高延遲問題，會產生 client 需要等待全部的資料傳輸完成後，瀏覽器才能開始呈現，因此在使用體驗上會是不佳的狀態
* 那如何使用 chunk 進行傳輸？
只需要在 HTTP header 發送時，新增 `Transfer-Encoding: chunked` ，即可使用 chunk 傳輸，並且在最後傳送資料長度為 0 的資料，表示傳出完成。
之後在傳送資料的時候，需要先標示這次的資料長度為多少，並且以 16 進位表示。
```c
SEND_HTTP_MSG(request->socket, buf, "%s%s%s", "HTTP/1.1 200 OK\r\n",
"Content-Type: text/html\r\n",
"Transfer-Encoding: chunked\r\n\r\n");
// When you use chunk to send Data, you need apply data length at start
SEND_HTTP_MSG(request->socket, buf, "%s",
"16\r\n</table></body></html>\r\n");
```
### 引入 timer ，主動關閉逾期的連線
這次實作的 timer 是使用 `Priority Queue` 與 `Min Heap` 進行管理。
選擇使用 Min Heap 的主要原因為尋找最小值的時間複雜度為常數時間。因為在這種需要頻繁地去尋找最小值的特定狀況下，直接使用 Min Heap 進行管控，是一種最常使用的方法。
timer node 的結構如下：
* `key` 儲存逾期的時間點，作為 Priority 使用
* `pos` 儲存此 node 在 queue 中的位置
```c
typedef struct {
size_t key;
size_t pos; // the position of timer in queue
timer_callback callback;
struct socket *socket;
} timer_node_t;
```
timer 中主要的操作有以下：
* handle_expired_timers
取得目前 timer 中 key 為最小值的 node，並且判斷是否已經逾期，若是則刪除，直到 queue 為空
```c
void handle_expired_timers(void)
{
while (!prio_queue_is_empty(&timer)) {
timer_node_t *node;
current_time_update();
node = prio_queue_min(&timer);
if (node->key > atomic_read(¤t_msec))
return;
prio_queue_delmin(&timer);
}
}
```
* http_timer_update
更新此 node 在 timer 中的 key 值，主要做於此 request 有新的請求時更新 timeout 的時間點
```c
void http_timer_update(timer_node_t *node, size_t timeout)
{
current_time_update();
node->key = atomic_read(¤t_msec) + timeout;
// update new position
node->pos = prio_queue_sink(&timer, node->pos);
}
```
* http_add_timer
將新的 request 加入至 timer
```c
bool http_add_timer(struct http_request *req, size_t timeout, timer_callback cb)
{
timer_node_t *node = kmalloc(sizeof(timer_node_t), GFP_KERNEL);
if (!node)
return false;
current_time_update();
req->timer_item = node;
node->key = atomic_read(¤t_msec) + timeout;
node->pos = atomic_read(&timer.nalloc) + 1;
node->callback = cb;
node->socket = req->socket;
prio_queue_insert(&timer, node);
return true;
}
```
整體的實作流程為：
1. 初始化 timer
2. 當初始化成功建立之後，程式會一直執行 handle_expired_timers
3. 當建立 work 時，會執行 http_add_timer ，建立新的 timer node 並且放入 queue 中
:::danger
如何驗證上述流程的效益？
:::
### 目前的 kHTTPd 初步實作 HTTP 1.1 keep-alive，不過效率不彰，以 ftrace 一類的工具指出問題所在並改進
* 找出問題
以下是請求一次且從 ftrace 輸出中擷取的一部分：
```
9) | http_parser_execute [khttpd]() {
9) 0.464 us | http_parser_callback_headers_complete [khttpd]();
9) 0.250 us | http_message_needs_eof [khttpd]();
9) 0.272 us | http_should_keep_alive [khttpd]();
9) | http_parser_callback_message_complete [khttpd]() {
9) 0.289 us | http_should_keep_alive [khttpd]();
9) | handle_directory [khttpd]() {
9) + 15.485 us | filp_open();
9) + 74.317 us | http_server_send.isra.0 [khttpd]();
9) + 55.432 us | http_server_send.isra.0 [khttpd]();
9) # 1270.662 us | iterate_dir();
9) + 30.469 us | http_server_send.isra.0 [khttpd]();
9) + 40.951 us | http_server_send.isra.0 [khttpd]();
9) 5.280 us | filp_close();
9) # 1498.453 us | }
9) | _printk() {
9) + 13.177 us | vprintk();
9) + 13.739 us | }
9) # 1513.489 us | }
9) # 1517.121 us | }
```
由此可知，在每次的請求中所主要耗費在走訪目錄的過程，其次為傳送資料。
* 解決問題
由於走訪本身無法進行有效的改善，其時間複雜度為 O(n)，因此我使用 cache 的方式進行改善。
我的 cache 是利用 hashtable 的方式建立
結構為:
我主要 url 作為 index 進行尋找，且紀錄原本 response 的資料。
```c
struct cache_item {
char request_url[128];
char response_data[4096];
size_t response_size;
size_t max_size;
struct hlist_node node;
};
```
主要操作如下：
* cahce_lookup
```c
struct cache_item *cache_lookup(const char *url)
{
struct cache_item *item;
u32 key = hash_fn(url);
hash_for_each_possible(cache_table, item, node, key) {
if (strcmp(item->request_url, url) == 0) {
return item;
}
}
return NULL;
}
```
* cache_create_item
```c
struct cache_item *cache_create_item(const char *url)
{
struct cache_item *item = kmalloc(sizeof(struct cache_item), GFP_KERNEL);
if (!item) {
pr_err("Failed to allocate memory for cache_item\n");
return NULL;
}
strncpy(item->request_url, url, sizeof(item->request_url));
memset(item->response_data, 0, sizeof(item->response_data));
item->response_size = 0;
item->max_size = sizeof(item->response_data);
return item;
}
```
* cache_insert
```c
int cache_insert(const char *url, const char *response_data)
{
struct cache_item *item;
u32 key = hash_fn(url);
item = cache_lookup(url);
if (item) {
memset(item->response_data, 0, sizeof(item->response_data));
strncat(item->response_data, response_data, sizeof(item->response_data) - 1);
item->response_size = strlen(item->response_data);
return 0;
}
item = cache_create_item(url);
if (!item) {
return -ENOMEM;
}
strncat(item->response_data, response_data, sizeof(item->response_data) - 1);
item->response_size = strlen(item->response_data);
hash_add(cache_table, &item->node, key);
return 0;
}
```
主要流程為：
1. 先進行初始化
2. 在進入 handle_directory 之前，先尋找在 hashtable 中是否有 request url
2_1. 若有則回傳以記錄的 response data
2_2. 否則進行下一步
3. 執行 handle_directory
4. 在執行傳送資料之前先將資料儲存至 cache 中
* 實作結果
可以看到在重複請求同樣網址時，可以有效提升處理速度
```
原本實做 實作 cache
requests: 20000 requests: 20000
good requests: 20000 [100%] good requests: 20000 [100%]
bad requests: 0 [0%] bad requests: 0 [0%]
socket errors: 0 [0%] socket errors: 0 [0%]
seconds: 5.787 seconds: 0.977
requests/sec: 3455.947 requests/sec: 20471.835
```
### 學習 cserv 的 memcache 並在 kHTTPd 重新實作
在原有的設計上，會因為有大量的記憶體配置請求，每次 kernel 處理記憶體配置時，會需要保證其餘程式的安全，所以需要一定的時間處理該請求，因此會耗費大量的時間，並且當長時間的配置與釋放記憶體空間，會造成記憶體空間破碎化。
因為以上的原因，才使用 memcache 進行統一的記憶體空間管理。由於 memcache 只作為提供空間與數量管理的機制，因此需要將 LRU 加入至 hashtable 。
:::danger
為何引入 LRU 會有幫助？你的理論依據是什麼？建立統計模型來探討。
:::
主要操作如下：
:::danger
減少非必要的縮排。
:::
- [ ] memcache_create
此函式為 memcache 初始化，主要是配置整體大小並且將此空間切分為數份 obj_size 的 element 後將 element 加入至 memcache
```c
struct memcache *memcache_create(size_t obj_size, int max_cache_size)
{
struct memcache *cache;
size_t size;
void *element;
size = sizeof(struct memcache) + max_cache_size * sizeof(void *);
cache = kmalloc(size, GFP_KERNEL);
if (!cache)
return NULL;
cache->elements = (void **)((char *)cache + sizeof(struct memcache));
cache->obj_size = obj_size;
cache->cache_size = max_cache_size;
cache->curr = 0;
INIT_LIST_HEAD(&cache->lru_list);
max_cache_size >>= 2;
while (cache->curr < max_cache_size) {
element = kmalloc(cache->obj_size, GFP_KERNEL);
if (!element) {
free_pool(cache);
return NULL;
}
add_element(cache, element);
}
return cache;
}
```
- [ ] memcache_alloc
主要為若 memcache 還有空間數量可以分配時則回傳開空間大小，否則再次配置
```c
void *memcache_alloc(struct memcache *cache)
{
return (cache->curr) ? remove_element(cache) : kmalloc(cache->obj_size, GFP_KERNEL);
}
```
整體流程為：
1. 在 hashtable 初始化時，建立 memcache
2. 在建立新的 hashtable 節點時，從 memcache 進行配置，並且將此節點放入置 LRU ，若進行配置時存在數量已超過最大值時則刪除最舊的節點
3. 在尋找或插入 hashtable 節點時，會將此節點放入至 LRU 的最前方
## TODO: 探討 eBPF 對於網頁伺服器開發的作用
> 量化 Linux 核心網路的行為
參考 [fatcatorange](https://hackmd.io/@sysprog/HkyVuh0NR#%E7%A0%94%E8%AE%80-%E9%80%8F%E9%81%8E-eBPF-%E8%A7%80%E5%AF%9F%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1%E8%A1%8C%E7%82%BA%EF%BC%8C%E5%A6%82%E4%BD%95%E7%94%A8-eBPF-%E6%B8%AC%E9%87%8F-kthread--CMWQ-%E9%97%9C%E9%8D%B5%E6%93%8D%E4%BD%9C%E7%9A%84%E5%9F%B7%E8%A1%8C%E6%88%90%E6%9C%AC%EF%BC%9F) 與使用 matplotlib 實施可視化分析，撰寫以下程式：
```python
from bcc import BPF
import matplotlib.pyplot as plt
# eBPF 程序
code = """
#include <uapi/linux/ptrace.h>
BPF_HASH(start, u32, u64);
int probe_handler(struct pt_regs *ctx)
{
u64 ts = bpf_ktime_get_ns();
u32 tgid = bpf_get_current_pid_tgid();
start.update(&tgid, &ts);
return 0;
}
int end_function(struct pt_regs *ctx)
{
u64 ts = bpf_ktime_get_ns();
u32 tgid = bpf_get_current_pid_tgid();
u64 *start_ts = start.lookup(&tgid);
if (start_ts) {
bpf_trace_printk("duration: %llu\\n", ts - *start_ts);
start.delete(&tgid);
}
return 0;
}
"""
# 初始化 eBPF
b = BPF(text=code)
b.attach_kprobe(event='handle_directory', fn_name='probe_handler')
b.attach_kretprobe(event='handle_directory', fn_name='end_function')
durations = []
# 捕获数据并保存到 durations 列表中
print("Capturing durations... Press Ctrl+C to stop.")
try:
while True:
(task, pid, cpu, flags, ts, msg) = b.trace_fields()
duration = int(msg.split()[1])
durations.append(duration)
print(f"Captured duration: {duration}")
except KeyboardInterrupt:
print("Stopping capture...")
# 生成折线图
plt.figure(figsize=(10, 5))
plt.plot(durations, marker='*', color='purple', markersize=3)
plt.title('Duration over time')
plt.xlabel('Sample number')
plt.ylabel('Duration (ns)')
plt.grid(True)
plt.savefig('durations_plot.png')
plt.show()
```
:::danger
注意書寫規範：
* 程式碼註解不該出現中文，總是用美式英語書寫
:::
我選擇 `handle_directory` 作為量化目標，選擇此函式的原因是因為每次的請求都會進入此函式，並且根據上方 `ftrace` 的結果，得知此處是整個系統中最耗時的區域。
完成上方的改進 kHTTPd 之後，進行了 1000 、 10000 與 100000 次的連續請求，並完成以下的折線圖，以便後須觀察。
* 1000
* 10000
* 100000
從折線圖中可以看出， `handle_directory` 函式的執行時間在不同的請求次數下表現出相對穩定的趨勢。具體分析如下：
1. 1000 次請求：在 1000 次請求下，handle_directory 函數的執行時間較為穩定，只有少數幾個數據點出現較大的波動。
2. 10000 次請求：在 10000 次請求下，執行時間的波動稍有增加，但整體趨勢仍然較為穩定，顯示出系統在較大負載下的穩定性。
3. 100000 次請求：在 100000 次請求下，執行時間的波動性進一步增加，但總體上系統仍然保持穩定，沒有出現隨著時間推移或其他因素導致的處理成本顯著上升的情況。
:::danger
「執行時間的波動」的成因是什麼？
:::
整體來看，函式在不同請求次數下的表現相對穩定，並未因為時間的推移或其他因素導致處理成本顯著上升。
Sign in with Wallet
Connect another wallet