## Linux 核心專題: 高性能網頁伺服器
> 執行人: fatcatorange
> [專題解說錄影](https://youtu.be/JkzX_Bk2QwY)
### Reviewed by `SimonLee0316`
在解決 keep-alive 問題中，有提到要使用 hash_map 來記錄每個連線，每次檢查 hash_map 所有節點並將過久沒有通訊的連接中斷，在如果有大量連線的情況下，檢查所有連線的效果是否會很差達到 $O(n)$？
> 您好 我最後使用的方法是透過優先權佇列來檢查超時的連接，但確實如果透過此方法，每次檢查的成本為 $O(n)$。
### Reviewed by `jserv`
針對大量連線的追蹤，[2023 年專題: lwan](https://hackmd.io/@sysprog/HJgX4_MH3) 探討維護 timeout 機制從普遍的 $O(n)$ 降到 $O(1)$，其位元運算的策略，可作為後續改進依據。延伸閱讀: [Implement a timing wheel for millions of concurrent tasks](https://dev.to/kevwan/implement-a-timing-wheel-for-millions-of-concurrent-tasks-30oi)
### Reviewed by `Ackerman666`
刪除閒置連線的作法中提到
>傳輸後會將 priority_queue 中的節點修改為已刪除 (不是真的刪除，但該節點會被標記) 然後插入一個新的節點來記錄新的時間。
那這樣考慮同時有多筆連線反覆請求 (如搶五月天的票，一直按F5刷新頁面)。會一直插入新節點至 priority_queue 中，且要花費大量空間紀錄節點資訊，這樣會有效能上的問題。有沒有更好的方式來解這樣的情境 ?
> 如果是這個情況，或許可以將插入節點這個行為改成修改節點內的值，然後再將這個節點下降到適當位置，這樣可以減少優先權佇列內節點的數量。
### Reviewed by `marsh-fish`
如同前面 SimonLee0316 提到的檢查超時的連接所需要的時間為 $O(n)$ ，是否有辦法降低所需要的時間？
>你好，如同前面提到，我後來並不是使用這個方法，而是使用 priority_queue 作為 timer，如果再搭配和同一位同學提到的方法修改 heap，儘管最差可能到 $O(n log n)$，如同時有非常大量的連結同時過期，其他時候都不會有多餘的檢查。
### Reviewed by `w96086123`
在 eBPF 中，你使用作業說明前半部份的方法建立了 10000 執行緒後，提到無法建立這麼多執行續，那原因是為甚麼？
### Reviewed by `yenshipotato`
在報告中提到每秒會有另一個 thread 檢查是否有逾時連結，並在連結逾時後執行 callback 關閉 socket。請問這樣的機制是否會對系統造成負擔？是否有其他更高效的方法來管理和清理逾時連結？
> 你好，在實作之前我是有思考過其他方法，例如在筆記中提到的對個別連結都設定 linux-kernel 中的 timer 等，但結果顯示對系統負荷更大，以目前來說我認為定期透過 priority_queue 檢查超時連結已經是較好的方法，當然之後會再針對 jserv 老師提到的方法進行測試。
## 任務簡介
以[第七次作業](https://hackmd.io/@sysprog/linux2024-ktcp)為基礎，熟悉 Linux 核心模組的開發、網路通訊機制、RCU 使用，和排除相關的技術議題。
應對下方修改，嘗試提交 pull request。
:::danger
等你的 pull request
:::
參考資訊： (適度改寫下方程式碼並驗證)
* Jerejere0808 $\to$ [開發紀錄](https://hackmd.io/@sysprog/HkzcnhOHn)
* Paintako $\to$ [開發紀錄](https://hackmd.io/@sysprog/BkSW8Z2Bn)
* [cppcoffee/khttpd](https://github.com/cppcoffee/khttpd)
## TODO: 自我檢查清單
> https://hackmd.io/@sysprog/linux2024-ktcp-e
回答上述「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼，以第一手材料 (包含自己設計的實驗) 為佳。
### 研讀〈Linux 核心設計: RCU 同步機制〉並測試相關 Linux 核心模組以理解其用法
### Linux 核心設計: RCU 同步機制
以概念來說，RCU 要使用在有大量讀取要求，但只有少量的寫入要求，且不會太在意讀取到舊資料的情況。
最簡單的想法就是當有資料要進行寫入時，先複製一份並修改，在其修改後所有讀取必須讀到新的資料，但如果在寫入前就在讀取資料的話，則那些正在讀取的資料還是會讀到舊資料，等到沒有用戶在讀取舊資料了，再把新資料拿來替代就資料並刪除就資料。
也因此， RCU 非常重要的應用就是在 linked-list。
#### RCU 在核心模組的應用：
在 [rculist](https://github.com/torvalds/linux/blob/master/include/linux/rculist.h) 中，就有提供了大量的 rcu 函式，以 replace 舉例來說：
```c
static inline void list_replace_rcu(struct list_head *old,
struct list_head *new)
{
new->next = old->next;
new->prev = old->prev;
rcu_assign_pointer(list_next_rcu(new->prev), new);
new->next->prev = new;
old->prev = LIST_POISON2;
}
```
先將 new 的內容複製為 old 的內容後，透過 rcu_assign_pointer() 函式進行修改，這邊值得一提的是其使用 list_next_rcu，因為實際上要修改的指標是 old 的前一個的 next 指標，而非 old 指標，以圖例來說明的話：
```graphviz
digraph _graph_name_ {
rankdir=LR;
l1[label = "list1"]
l2[label = "list2"]
l3[label = "l3"]
new[label = "new"]
old[penwidth=0];
l1->l2[color = red]
l2->l3
new->l3
old->l2
}
```
實際上我們要修改的是紅色那個指標指向的位址，而不是 old 指標。
```graphviz
digraph _graph_name_ {
rankdir=LR;
l1[label = "list1"]
l2[label = "list2"]
l3[label = "l3"]
new[label = "new"]
old[penwidth=0];
l1->new[color = red]
l2->l3
new->l3
old->l2
}
```
參考 [rcu_example](https://github.com/jinb-park/rcu_example) ，一個簡單的 driver 展示了 rcu 函式的使用：
先 clone 下來後，因為專案內已經有寫好 Makefile，直接 make 就會產生 .ko 檔，透過 ismod 加入即可。
```c
static int list_rcu_example_init(void)
{
spin_lock_init(&books_lock);
test_example(0);
test_example(1);
return 0;
}
```
因為程式已經把範例內容寫在 init 內， 載入後檢查 dmesg 即可看到執行狀況：
```c
[68873.600792] book1 borrow : 0
[68873.600793] book2 borrow : 0
[68873.600795] borrow success 0, preempt_count : 0
[68873.600797] borrow success 1, preempt_count : 0
[68873.600799] id : 0, name : book1, author : jb, borrow : 1, addr : ffff95660c06c600
[68873.600801] id : 1, name : book2, author : jb, borrow : 1, addr : ffff95660c06d980
```
解釋其行為：
以 add_book 為例，先產生一個 book ，再透過 list_add_rcu 來加入。
:::danger
注意書寫規範：
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
* 注意看[程式碼規範](https://hackmd.io/@sysprog/linux2024-lab0-a)的「clang-format 工具和一致的程式撰寫風格」，筆記列出的程式碼依循指定的風格。
:::
```c
b = kzalloc(sizeof(struct book), GFP_KERNEL);
if(!b)
return;
b->id = id;
strncpy(b->name, name, sizeof(b->name));
strncpy(b->author, author, sizeof(b->author));
b->borrow = 0;
/**
* list_add_rcu
*
* add_node(writer - add) use spin_lock()
*/
spin_lock(&books_lock);
list_add_rcu(&b->node, &books);
spin_unlock(&books_lock);
```
list_add_rcu:
```c
static inline void __list_add_rcu(struct list_head *new,
struct list_head *prev, struct list_head *next)
{
if (!__list_add_valid(new, prev, next))
return;
new->next = next;
new->prev = prev;
rcu_assign_pointer(list_next_rcu(prev), new);
next->prev = new;
}
```
傳入的 new 就是新建立的節點，prev 是前一項，next 是後一項，而這個函式傳入的 prev 是 head， next 是 head->next，因此實際上就是把 new 透過 rcu_assign_pointer 插入到最前面。
如果要借書，就必須修改當前 borrow 為 1
:::danger
注意書寫規範：
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
* 注意看[程式碼規範](https://hackmd.io/@sysprog/linux2024-lab0-a)的「clang-format 工具和一致的程式撰寫風格」，筆記列出的程式碼依循指定的風格。
:::
```c
static int borrow_book(int id, int async) {
struct book *b = NULL;
struct book *new_b = NULL;
struct book *old_b = NULL;
/**
* updater
*
* (updater) require that alloc new node & copy, update new node & reclaim old node
* list_replace_rcu() is used to do that.
*/
rcu_read_lock();
list_for_each_entry(b, &books, node) {
if(b->id == id) {
if(b->borrow) {
rcu_read_unlock();
return -1;
}
old_b = b;
break;
}
}
if(!old_b) {
rcu_read_unlock();
return -1;
}
new_b = kzalloc(sizeof(struct book), GFP_ATOMIC);
if(!new_b) {
rcu_read_unlock();
return -1;
}
memcpy(new_b, old_b, sizeof(struct book));
new_b->borrow = 1;
spin_lock(&books_lock);
list_replace_rcu(&old_b->node, &new_b->node);
spin_unlock(&books_lock);
rcu_read_unlock();
if(async) {
call_rcu(&old_b->rcu, book_reclaim_callback);
}else {
synchronize_rcu();
kfree(old_b);
}
pr_info("borrow success %d, preempt_count : %d\n", id, preempt_count());
return 0;
}
```
這段程式碼中，首先因為要先讀取整個 list，要先尋找要借的書是否存在，並檢查是否已經被借走，因此使用 rcu_read_lock 和 rcu_read_unlock 來設定進入時間，假如找到了，複製一份該 book 並將 borrow 修改為 1 ，並使用 sychronize_rcu 來等之前使用舊資料的用戶都不會再使用後將 old_book 刪除。
:::info
按照 rcu 的規則，這樣似乎會造成兩個人同時借到當時還沒有被界走的書？
:::
### 如何利用 Ftrace 找出 khttpd 核心模組的效能瓶頸，該如何設計相關實驗學習。搭配閱讀《Demystifying the Linux CPU Scheduler》第 6 章
在後續的實作中有使用範例
### 研讀 透過 eBPF 觀察作業系統行為，如何用 eBPF 測量 kthread / CMWQ 關鍵操作的執行成本？
:::danger
清楚標示 GitHub 帳號名稱
:::
參考 <s>[學長寫的教學](https://hackmd.io/@0xff07/r1f4B8aGI#Appendix-C)</s> ，先寫出一個類似的程式進行追蹤：
```c
from bcc import BPF
prog = """
#include <uapi/linux/ptrace.h>
int probe_handler(struct pt_regs *ctx)
{
u64 ts = bpf_ktime_get_ns();
bpf_trace_printk("Enter http_server_worker at %llu\\n", ts);
return 0;
}
"""
b = BPF(text=prog)
b.attach_kprobe(event="http_server_worker", fn_name="probe_handler")
b.trace_print()
```
此處我是以 `http_server_worker`作為目標，這個函式出現在：
```c
worker = kthread_run(http_server_worker, socket, KBUILD_MODNAME);
```
主要功能就是在 accept 後創建執行緒來服務該用戶。
可以發現，當有用戶開始連接時，如果有執行 bcc 程式，就可以攔截到事件並執行一些行為：
client:
```shell
telnet localhost 1999
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
```
我原先希望透過教學檢查 fib_read 的方法來檢測建立執行緒的成本，但產生了一個問題：
在 bpf 中，我應是要加入要檢測的函式，然而執行緒建立的函式如下：
```c
worker = kthread_run(http_server_worker, socket, KBUILD_MODNAME);
```
我一開始選擇監測 http_server_worker ，但會產生一個問題，就是 http_server_worker 只有在斷開連線時才會結束（也就是 client 端關閉連線時），因此這樣透過：
```python
from bcc import BPF
prog = """
#include <uapi/linux/ptrace.h>
BPF_HASH(start, u64, u64);
int probe_handler(struct pt_regs *ctx)
{
u64 ts = bpf_ktime_get_ns();
u64 pid = bpf_get_current_pid_tgid();
start.update(&pid, &ts);
return 0;
}
int ret_handler (struct pt_regs *ctx)
{
u64 ts = bpf_ktime_get_ns();
u64 pid = bpf_get_current_pid_tgid();
u64 *tsp = (start.lookup(&pid));
if (tsp != 0) {
bpf_trace_printk("duration: %llu\\n", ts - *tsp);
start.delete(&pid);
}
return 0;
}
"""
b = BPF(text=prog)
b.attach_kprobe(event="http_server_worker", fn_name="probe_handler")
b.attach_kretprobe(event="http_server_worker", fn_name="ret_handler")
b.trace_print()
```
算出的時間應是連線的持續時間，而非建立執行緒的時間。
而如果改以 kthread_run 為目標，因為 kthread_run 不只出現在這個 module ，因此可能會擷取到一些不相干的東西。
我想到的方法是，在 kthread_run 的前後各加入一個空的函式，例如：
```c
fun1()
worker = kthread_run(http_server_worker, socket, KBUILD_MODNAME);
fun2()
```
然後程式紀錄 fun1 的返回時間和 fun2 的進入時間，儘管會稍微有些誤差，但應可大致估計建立成本和其佔整個建立連線行為的時間比例。
但並沒有按照預期執行:
```
kthread_start_check();
worker = kthread_run(http_server_worker, socket, KBUILD_MODNAME);
kthread_end_check();
```
程式此處只執行了 start_check 的部份。
後來發現，kthread_end_check 不知為何是等到 kthread_run 裡面的函式執行完才會執行？
:::info
後來發現，很多函式雖然可以讀到，但是沒辦法檢測，不知道為什麼？
如果讀取某些函式，會出現如下錯誤：
```shell
cannot attach kprobe, probe entry may not exist
```
但如果讀取一些其他自己寫的函式，不會出現這個錯誤，換句話說，應該是有成功設定斷點，然而實際上經過檢查，除了 `http_server_worker` 這個函式外，其他函式雖然沒有出現錯誤，但 attach_kprobe 也沒有成功擷取(有透過 printk 檢查到函式確實有執行)。
:::
此處發現一個非常神奇的事情，如果使用普通的呼叫，則沒辦法擷取到，但如果透過 kthread_run 來執行該函式，就可以擷取到？
翻閱一些教學文件或教學，應是 system call 才會被擷取到？因此如果要擷取，我決定透過 kthread_run 建立兩個執行緒，第一個用來包裝讓程式執行，第二個用來執行 `kthread_run(http_server_worker, socket, KBUILD_MODNAME);`
並透過：
```python
from bcc import BPF
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;
}
"""
b = BPF(text = code)
b.attach_kprobe(event = 'my_thread_run', fn_name = 'probe_handler')
b.attach_kretprobe(event = 'my_thread_run', fn_name = 'end_function')
while True:
try:
print("listen..")
res = b.trace_fields()
except ValueError:
print(res)
continue
print(res[5].decode("UTF-8"))
```
來檢測執行緒建立成本。
首先先執行程式，並將資料寫入 output.txt:
```
sudo python3 test.py >> output.txt
```
接下來透過作業說明前半部份提到的方法進行測試：
```shell
ab -n 10000 -c -10000 -k http://127.0.0.1:8081/
```
但發現好像不能同時建立這麼多執行緒，同時產生大約只能 5000:
透過 curl 慢慢發送 1000 個訊息：
```bash
#!/bin/bash
for ((i=1; i<=1000; i++))
do
curl -s -o /dev/null http://localhost:8081/
done
```
結果似乎更接近作業說明中的結果。
改為 10000 次：
## TODO: 引入 CMWQ 改寫 kHTTPd
> 分析效能表現和提出改進方案
此處想將原先使用 kthread_run 的部份改以 CMWQ 執行，首先先配置一個 workqueue:
```c
khttpd_wq = alloc_workqueue("khttpd", 0, 0);
```
在 server.c 中，先建立一個 daemon_list 作為這個 workqueue 的開頭。
```c
INIT_LIST_HEAD(&daemon_list.head);
```
接下來，在 server.c 中，參考 [kecho](https://github.com/sysprog21/kecho/blob/master/echo_server.c) ，先使用 create_work 建立工作：
```c
if (unlikely(!(work = create_work(socket)))) {
printk(KERN_ERR ": create work error, connection closed\n");
kernel_sock_shutdown(socket, SHUT_RDWR);
sock_release(socket);
continue;
}
```
在 create_work 中，根據傳入的 socket 建立一個 work。
```c
static struct work_struct *create_work(struct socket *sk)
{
struct http_request *work;
if (!(work = kmalloc(sizeof(struct http_request), GFP_KERNEL)))
return NULL;
work->socket = sk;
INIT_WORK(&work->khttpd_work, http_server_worker);
list_add(&work->node, &daemon_list.head);
return &work->khttpd_work;
}
```
已經透過 list_add 將工作加入 list，此處要注意的是，和使用 kthread_run 運行不同， kthread_run 可以傳入一個 void 型態的指標，因此可以在 kthread_run 時指定要傳入的參數，之後再轉型即可。
但使用 workqueue 時，程式執行時就是傳入一個 `struct work_struct `，也因此可以將一些需要的參數全部寫在一個 struct 內，並讓這個 struct 包含 `struct work_struct `這個成員：
```c
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;
};
```
當傳入時，透過 container_of 即可使用整個 struct ，並使用裡面的參數，舉例來說，原本 `http_server_worker` 是傳入一個 void 指標，這代表的是 socket ，使用 workqueue 時，就可以透過：
```c
struct socket *socket =
container_of(w, struct http_request, khttpd_work)->socket;
```
來取得 socket 的指標。
值得一提的是，在 create_work 中，有一段程式碼：
```c
list_add(&work->node, &daemon_list.head);
```
因為之前作業 6 的 ksort 有使用到 queue_work ，但似乎沒有用到這個部份，因此我嘗試移除這行敘述，執行結果則完全相同。
:::danger
注意用語：instruction 是「指令」，但本處不該用該這樣用，可改說「敘述」(statement)
:::
因為 create_work 應該只是幫這個工作初始化，真正加入應是等到：
```c
queue_work(khttpd_wq, work);
```
下方是有無使用 cmwq 的差距，上方為單純使用 kthread_run:
```
./htstress http://localhost:8081 -t 3 -c 20 -n 200000
0 requests
20000 requests
40000 requests
60000 requests
80000 requests
100000 requests
120000 requests
140000 requests
160000 requests
180000 requests
requests: 200000
good requests: 200000 [100%]
bad requests: 0 [0%]
socket errors: 0 [0%]
seconds: 2.419
requests/sec: 82688.125
```
下方為使用 cmwq ，可以發現request/sec 成長了超過一倍。
```
lhost:8081 -t 3 -c 20 -n 200000
0 requests
20000 requests
40000 requests
60000 requests
80000 requests
100000 requests
120000 requests
140000 requests
160000 requests
180000 requests
requests: 200000
good requests: 200000 [100%]
bad requests: 0 [0%]
socket errors: 0 [0%]
seconds: 1.011
requests/sec: 197856.619
```
此部份的 [commit](https://github.com/fatcatorange/khttpd/commit/2288902a8a13b1aa93df578284062ed486fe3e38)
## TODO: 提供目錄檔案存取功能
要加入這個功能，要修改 `http_server_response` ，原本的 `http_server_response` 只會檢查是不是用 get ，是的話回傳一個 HTTP_RESPONSE_200 (代表成功) ，內容是 hello world。
而這個函式被使用在:
```c
static int http_parser_callback_message_complete(http_parser *parser)
{
struct http_request *request = parser->data;
http_server_response(request, http_should_keep_alive(parser));
request->complete = 1;
return 0;
}
```
而這個函式被綁定在：
:::danger
注意書寫規範：
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
* 注意看[程式碼規範](https://hackmd.io/@sysprog/linux2024-lab0-a)的「clang-format 工具和一致的程式撰寫風格」，筆記列出的程式碼依循指定的風格。
:::
```c
struct http_parser_settings setting = {
.on_message_begin = http_parser_callback_message_begin,
.on_url = http_parser_callback_request_url,
.on_header_field = http_parser_callback_header_field,
.on_header_value = http_parser_callback_header_value,
.on_headers_complete = http_parser_callback_headers_complete,
.on_body = http_parser_callback_body,
.on_message_complete = http_parser_callback_message_complete};
```
當程式執行 http_parser_execute(&parser, &setting, buf, ret); 時，就會根據解析執行對應的函式，以這個例子來說，解析完整個 http 請求時執行 `http_parser_callback_message_complete`
:::danger
依據 [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary) 和 [詞彙對照表](https://hackmd.io/@l10n-tw/glossaries) 的用語，調整開發紀錄。
:::
在顯示目錄部份，參考 [Paintako](https://hackmd.io/@sysprog/BkSW8Z2Bn) ，<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)
{
printk("%s\n", name);
if (strcmp(name, ".") && 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));
printk("%s\n", buf);
}
return 1;
}
```
此處是檢查到每個檔案時該做的事，會向用戶端傳送一個 table 的其中一格，包含該檔案的名字。
接下來將 dir_context.actor 指定為該函式，代表走訪時執行該函式。
```c
static bool handle_directory(struct http_request *request)
{
struct file *fp;
char buf[SEND_BUFFER_SIZE] = {0};
request->dir_context.actor = tracedir;
if (request->method != HTTP_GET) {
snprintf(buf, SEND_BUFFER_SIZE,
"HTTP/1.1 501 Not Implemented\r\n%s%s%s%s",
"Content-Type: text/plain\r\n", "Content-Length: 19\r\n",
"Connection: Close\r\n", "501 Not Implemented\r\n");
http_server_send(request->socket, buf, strlen(buf));
return false;
}
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));
fp = filp_open("/home/jason/linux-2024/khttpd/khttpd", O_RDONLY | O_DIRECTORY, 0);
if (IS_ERR(fp)) {
printk("open file failed");
return false;
}
iterate_dir(fp, &request->dir_context);
snprintf(buf, SEND_BUFFER_SIZE, "</table></body></html>\r\n");
http_server_send(request->socket, buf, strlen(buf));
filp_close(fp, NULL);
return true;
}
```
然後將 http_server_response 改為執行 `handle_dicretory` 即可。
```c
static int http_server_response(struct http_request *request, int keep_alive)
{
// pr_info("requested_url = %s\n", request->request_url);
int ret = handle_directory(request);
if (ret > 0)
return -1;
return 0;
}
```
然而目前遇到一個問題，使用瀏覽器輸入 `127.0.0.1:8081` 後，雖然可以接收到目錄：
但瀏覽器持續在讀取，似乎是還在等待資料
### 指定開啟目錄
一樣透過 `module_param` ，在載入模組時指定路徑即可：
```c
module_param_string(WWWROOT, WWWROOT, PATH_SIZE, 0);
..
daemon_list.dir_path = WWWROOT;
```
將路徑部份替換為 `daemon_list.dir_path`:
```c
fp = filp_open(daemon_list.dir_path,
O_RDONLY | O_DIRECTORY, 0);
```
### 根據路徑開啟檔案
首先，必須先判斷目前路徑是目錄還是檔案，因此可透過：
```c
S_ISDIR(fp->f_inode->i_mode)
```
和
```c
S_ISREG(fp->f_inode->i_mode)
```
來判斷是檔案或目錄。
假如是目錄，則使用跟之前一樣的方法，透過 `iterate_dir`來對目錄進行檢查：
```c
if (S_ISDIR(fp->f_inode->i_mode)) {
char buf[SEND_BUFFER_SIZE] = {0};
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));
}
```
要注意的是，如果是檔案的話，要先取得檔案大小並分配空間：
```c
char *read_data = kmalloc(fp->f_inode->i_size, GFP_KERNEL);
```
然後透過：
```c
kernel_read(fp, buf, fp->f_inode->i_size, 0);
```
來讀取該檔案。
目前當點選目錄時，就可以進入更內層目錄，點選檔案則會顯示內容：
但目前有個問題，當進入深層的目錄時，再點選資料夾或目錄會找不到檔案，這是因為路徑是透過組合成的，假如有個檔案的位置是 ../khttpd/bcc/FAQ.txt ，組合出的路徑會是 ../khttpd/FAQ.txt。
### 修正問題
主要問題是在回傳時設定的 `href` 錯誤：
```c
snprintf(buf, SEND_BUFFER_SIZE,
"<tr><td><a href=\"%s\">%s</a></td></tr>\r\n", name, name);
```
這裡的 name 是這個檔案的名稱，如果直接把拿來當路徑就會發生前面提到的狀況，我們需要把這個名稱和前面的路徑組合：
```c
strcpy(des,request->request_url);
strcat(des, "/");
strcat(des, name);
```
需要注意的是，如果是第一層目錄，原本 `request->request_url` 就是 `/`，因此要排除這個情況，完整程式碼如下：
```c
char *des = kmalloc(strlen(request->request_url) + strlen(name) + 2,GFP_KERNEL);
if(strcmp(request->request_url, "/") != 0) {
strcpy(des,request->request_url);
strcat(des, "/");
strcat(des, name);
}
else {
strcpy(des,name);
}
snprintf(buf, SEND_BUFFER_SIZE,
"<tr><td><a href=\"%s\">%s</a></td></tr>\r\n", des, name);
```
完成後，已經可以順利點擊目錄進入更深層的檔案：
### 回前頁功能
目前想回到上一頁只能透過瀏覽器選擇回上頁完成，這裡嘗試增加一個選項來完成，原本只有在目前名稱不是 `..` 或 `.` 才會執行，稍微進行修改，讓 `..` 可以進入：
```diff=
-if (strcmp(name, ".") && strcmp(name, ".."))
+if (strcmp(name, ".") )
```
但這會出現幾個問題，首先，在第一頁不需要這個按鈕，另外，這個 `..` 在目錄中不一定是在最上面，但顯示給使用者的界面中應該要在最上面：
目前想法是，假如目前路徑不是 `\` ，則直接插入一個 `..` ，並參考學長作法，如果網址最後面試 `\`，則直接去掉該欄：
```c
static int http_parser_callback_request_url(http_parser *parser,
const char *p,
size_t len)
{
struct http_request *request = parser->data;
if(p[len-1] == '/')
len--;
strncat(request->request_url, p, len);
return 0;
}
```
在 iterate_dir 前進行：
```c
if(strcmp(request->request_url, ""))
snprintf(buf, SEND_BUFFER_SIZE,
"<tr><td><a href=\"%s%s\">%s</a></td></tr>\r\n", request->request_url, "/..", "..");
http_server_send(request->socket, buf, strlen(buf));
iterate_dir(fp, &request->dir_context);
```
完成後，`..` 就會出現在目錄最上方：
### 檢測效能
:::danger
注意用語：
* access 是「存取」，而非「訪問」(visit)
:::
因為加入了存取目錄的行為，伺服器回覆速度一定會變慢，使用之前資料比較的話：
目前:
```
requests: 200000
good requests: 200000 [100%]
bad requests: 0 [0%]
socket errors: 0 [0%]
seconds: 14.281
requests/sec: 14004.417
```
之前：
```
requests: 200000
good requests: 200000 [100%]
bad requests: 0 [0%]
socket errors: 0 [0%]
seconds: 1.011
requests/sec: 197856.619
```
嘗試使用 Ftrace 來檢測：
先檢查可以被檢測的函式：
```shell
sudo cat ls /sys/kernel/debug/tracing/available_filter_functions | grep khttpd
```
```shell
parse_url_char [khttpd]
http_message_needs_eof [khttpd]
http_should_keep_alive [khttpd]
http_parser_execute [khttpd]
http_method_str [khttpd]
http_status_str [khttpd]
http_parser_init [khttpd]
..
```
按照[作業說明](https://hackmd.io/@sysprog/linux2024-ktcp/%2F%40sysprog%2Flinux2024-ktcp-c#%E4%BD%BF%E7%94%A8-Ftrace-%E8%A7%80%E5%AF%9F-kHTTPd)，透過一個 shell 檢測是哪部份花了最多時間：
```shell
#!/bin/bash
TRACE_DIR=/sys/kernel/debug/tracing
# clear
echo 0 > $TRACE_DIR/tracing_on
echo > $TRACE_DIR/set_graph_function
echo > $TRACE_DIR/set_ftrace_filter
echo nop > $TRACE_DIR/current_tracer
# setting
echo function_graph > $TRACE_DIR/current_tracer
echo 3 > $TRACE_DIR/max_graph_depth
echo http_server_worker > $TRACE_DIR/set_graph_function
# execute
echo 1 > $TRACE_DIR/tracing_on
./htstress localhost:8081 -n 2000
echo 0 > $TRACE_DIR/tracing_on
```
下方為結果，可以發現在 `http_parser_callback_message_complete` 花費了非常多時間：
```shell
http_parser_execute [khttpd]() {
12) 0.090 us | http_parser_callback_message_begin [khttpd]();
12) 0.105 us | parse_url_char [khttpd]();
12) 0.098 us | http_parser_callback_request_url [khttpd]();
12) 0.072 us | http_parser_callback_header_field [khttpd]();
12) 0.070 us | http_parser_callback_header_value [khttpd]();
12) 0.064 us | http_parser_callback_headers_complete [khttpd]();
12) 0.066 us | http_message_needs_eof [khttpd]();
12) 0.069 us | http_should_keep_alive [khttpd]();
12) ! 345.720 us | http_parser_callback_message_complete [khttpd]();
12) ! 347.870 us |
}
```
這個函式會呼叫 `http_server_response` ，而在叫深層的地方會呼叫 handle_directory，更內部會再呼叫 `tracedir` ，因為推測可能是在訪問目錄產生的成本，嘗試把 `max_graph_depth` 調整的更深，讓他可以檢測到 `tracedir` 的結果。
檢查後，就可以很明顯的發現該處確實是最大的開銷：
```
20) 4.146 us | _printk();
20) 7.140 us | filp_open();
20) + 33.563 us | http_server_send.isra.0 [khttpd]();
20) + 21.726 us | http_server_send.isra.0 [khttpd]();
20) + 21.099 us | http_server_send.isra.0 [khttpd]();
20) ! 545.853 us | iterate_dir();
20) + 13.296 us | http_server_send.isra.0 [khttpd]();
20) + 11.487 us | kernel_sock_shutdown();
20) 2.934 us | filp_close();
20) ! 663.411 us | }
20) ! 663.823 us | }
20) ! 668.401 us | }
```
目前導致這麼差的效能的主因應是每次都要去讀取檔案，如果可以暫存檔案內容，如果有其他用戶呼叫相同內容時可以直接讀取暫存的內容，應該可以減輕一些負擔。
### 引入快取機制
此處使用 linux kernel 的 hashtable 寫出簡易的 hash_insert 和 hash_check：
:::danger
注意書寫規範：
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
* 注意看[程式碼規範](https://hackmd.io/@sysprog/linux2024-lab0-a)的「clang-format 工具和一致的程式撰寫風格」，筆記列出的程式碼依循指定的風格。
:::
```c
DEFINE_READ_MOSTLY_HASHTABLE(ht, 8);
void init_hash_table (void) {
hash_init(ht);
}
void hash_insert (const char *request, char *data) {
char *insert_data = kmalloc(strlen(data) + 1, GFP_KERNEL);
memcpy(insert_data, data, strlen(data) + 1);
u32 key = jhash(request, strlen(request), 0);
struct hash_content *content = kmalloc(sizeof(struct hash_content) , GFP_KERNEL);
content->data = kmalloc(strlen(data) + 1, GFP_KERNEL);
content->request = kmalloc(strlen(request) + 1, GFP_KERNEL);
memcpy(content->data, data, strlen(data) + 1);
memcpy(content->request, request, strlen(data) + 1);
hash_add(ht, &content->node, key);
}
void hash_check (const char *request) {
u32 key = jhash(request, strlen(request), 0);
struct hash_content *now;
rcu_read_lock();
hash_for_each_possible(ht, now, node, key)
{
if (strcmp(request, now->request) == 0) {
printk("now request: %s\n",request);
}
}
rcu_read_unlock();
}
```
`hash_insert` 傳入兩個值，分別是 request 的 url 和要儲存的資料，將 request 透過 jhash 轉為一個 hash 的 key ，並透過這個 key 插入資料。
而在 `hash_check` 則是檢查 request 的 url ， 一樣將其轉為 key 後使用 hash_for_each_possible 來檢查該 key 的 list 是否包含該資料。
考慮到流量大時可能存取到一半切換到其他執行緒，結果目前正在存取的節點被其他執行緒刪除的情況，而寫入又只存在於第一次載入該目錄，將其修改為 hash_for_each_possible_rcu 會比較好？
這是目前的 hash_check ，檢查目前的 request_url 是否有暫存，若有的話會回傳 true ，沒有的話回傳 false ，並執行插入動作：
```c
void hash_insert(const char *request, char *data)
{
u32 original_key = jhash(request, strlen(request), 0);
u8 key = (u8) (original_key % 256);
struct hash_content *content =
kmalloc(sizeof(struct hash_content), GFP_KERNEL);
content->data = kmalloc(strlen(data) + 1, GFP_KERNEL);
content->request = kmalloc(strlen(request) + 1, GFP_KERNEL);
memcpy(content->data, data, strlen(data) + 1);
printk("finished input data");
memcpy(content->request, request, strlen(request) + 1);
printk("finished copy request");
hash_add_rcu(ht, &content->node, key);
printk("finished hash add");
}
bool hash_check(const char *request)
{
u32 original_key = jhash(request, strlen(request), 0);
u8 key = (u8) (original_key % 256);
struct hash_content *now;
rcu_read_lock();
hash_for_each_possible_rcu(ht, now, node, key)
{
if (strcmp(request, now->request) == 0) {
rcu_read_unlock();
printk("find request!: %s %s\n", request,now->data);
return true;
}
}
rcu_read_unlock();
printk("finished hash check");
return false;
}
```
在 `http_server.c` 中：
```c
if(!hash_check(request->request_url))
hash_insert(request->request_url, buf);
```
現在的目標就是把 trace_dir 中產生的各種 `html` 標籤暫存起來，這樣如果有用戶再次存取這個界面，就可以直接給他暫存的資料，而不需要再次透過 `trace_dir` 存取目錄。
目前的問題是，如果將這些標籤全部存在一個字串內，萬一該目錄下的檔案很多，我沒辦法確定要多長的字串才能處理，所以這裡我的想法是，我透過 linked-list 來存放每一筆資料：
在 `http_request` 中加入一個用來紀錄目錄檔案的 tag_list:
```diff
struct http_request {
struct socket *socket;
enum http_method method;
char request_url[128];
int complete;
struct dir_context dir_context;
struct list_head node;
struct work_struct khttpd_work;
+ struct list_head *tag_list;
};
```
:::danger
注意用語：
- access 是「存取」，而非「訪問」(visit)
:::
首先先檢查目前存取的目錄是否有人存取過，若沒有則開始透過 iterate_dir 存取，若有則會將該目錄資料的 list_head 存入 head：
```c
if(!hash_check(request->request_url,&head)) {
head = kmalloc(sizeof(struct list_head), GFP_KERNEL);
INIT_LIST_HEAD(head);
request->tag_list = head;
iterate_dir(fp, &request->dir_context);
hash_insert(request->request_url, head);
}
```
在 `trace_dir` 中，將拼接完成的標籤加入 list 中：
```c
snprintf(buf, SEND_BUFFER_SIZE,
"<tr><td><a href=\"%s\">%s</a></td></tr>\r\n", des, name);
struct tag_content *content = kmalloc(sizeof(struct tag_content), GFP_KERNEL);
INIT_LIST_HEAD(&content->tag_list);
strncpy(content->url, buf, strlen(buf));
list_add_tail(&content->tag_list, request->tag_list);
```
當透過 `trace_dir` 存取完目錄後，request->tag_list 就會有一個完整的 list ，每個節點中內容如下：
```c
struct tag_content {
struct list_head tag_list; //用於連接鏈結串列
char url[SEND_BUFFER_SIZE]; // "<tr><td><a href=\"%s\">%s</a></td></tr>\r\n", des, name);
};
```
接下來將這個 list 的 head 存入 hash 中：
```c
hash_insert(request->request_url, head);
```
假如後續還有用戶再次來訪這個頁面，因為已經有存放在 hash 中了，可以直接透過 hash 內的 head 透過:
```c
list_for_each_entry(now_content, head, tag_list) {
http_server_send(request->socket, now_content->url, strlen(now_content->url));
}
```
來發送訊息，省去了再次存取的時間。
完整的修改連結： [commit 05c3622](https://github.com/fatcatorange/khttpd/commit/dada9ea2862f09f03fc3e0874298526f629f5e21)
最後是刪除 hash 的函式：
```c
void hash_clear(void ) {
struct hash_content *entry = NULL;
struct hlist_node *tmp = NULL;
struct tag_content *now;
struct tag_content *tag_temp;
unsigned int bucket;
hash_for_each_safe(ht, bucket, tmp, entry, node)
{
list_for_each_entry_safe(now, tag_temp, entry->head, tag_list ) {
list_del(&now->tag_list);
kfree(now);
}
hash_del(&entry->node);
kfree(entry);
}
}
```
:::danger
注意用語！
:::
透過 `hash_for_each` 來存取整個 hash table，而因為每個 hash_content 內是存那些 THTML 標籤字串的 head，因此再透過 `list_for_each_safe` 來清除每個節點，這部份不用考慮 race condition ，因為只有在卸載模組會使用。
:::danger
留意 content cache 的效益和測試方法。
:::
### 實驗檢查效能是否提昇：
以下為實驗結果：
```shell
./htstress http://localhost:8081 -t 3 -c 20 -n 200000
0 requests
20000 requests
40000 requests
60000 requests
80000 requests
100000 requests
120000 requests
140000 requests
160000 requests
180000 requests
requests: 200000
good requests: 200000 [100%]
bad requests: 0 [0%]
socket errors: 0 [0%]
seconds: 5.873
requests/sec: 34051.496
```
比對引入 hash 的快取機制前：
```
requests/sec: 14004.417
```
可以發現，速度提昇了超過 1 倍。
需要注意的是，這是建立在所有用戶都存取相同頁面的情況，因此這是最理想的狀態，實際增益應不會這個高。
## 解決 keep-alive 的問題
此處我發現前面回傳資料的部分似乎有一些問題，原先我在回傳資料時，雖有設定為 `keep-alive` ，但我最後不慎多了一行 `kernel_sock_shutdown`:
```c
if (S_ISDIR(fp->f_inode->i_mode)) {
...
} else if (S_ISREG(fp->f_inode->i_mode)) {
../
}
kernel_sock_shutdown(request->socket, SHUT_RDWR);
filp_close(fp, NULL);
return true;
```
這導致每次實際上傳輸完畢後都將連接斷開，實際上行為和把 `connection: close` 相同。
要修改這個問題，首先要把 kernel_sock_shutdown 拿掉，並且在傳輸完成後多傳送一個 `\n\r\n\r` 代表結束。
修改完畢後，可看到可以重複使用同個 socket 進行傳輸:
```shell
telnet localhost 8081
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
GET / HTTP/1.1
HTTP/1.1 200 OK
Connection: Keep-Alive
Content-Type: text/html
Keep-Alive: timeout=5, max=1000
<html><head><style>
..
</table></body></html>
GET / HTTP/1.1
HTTP/1.1 200 OK
Connection: Keep-Alive
Content-Type: text/html
Keep-Alive: timeout=5, max=1000
<html><head><style>
</table></body></html>
```
但還有個問題，目前使用 telnet 是正常的，但使用瀏覽器時會一直在讀取中：
似乎是因為傳輸時沒有告知資料大小，瀏覽器無法知道要不要繼續接收，考慮到這點，參考 [作業說明](https://hackmd.io/@sysprog/linux2024-ktcp/%2F%40sysprog%2Flinux2024-ktcp-c) ，可能必須引入 chunk-encoding。
參考作業說明，只要在傳輸前先傳送資料長度即可(注意這個長度要非常精準，多或少都會導致瀏覽器卡住)，例如:
```c
snprintf(buf, SEND_BUFFER_SIZE,
"%lx\r\n<tr><td><a href=\"%s\">%s</a></td></tr>\r\n",
33 + strlen(des) + strlen(name), des, name);
```
這邊要非常注意的是，當結束傳輸時要傳送 `0\r\n` ，然後再傳`\r\n\r\n` ，這樣用戶端才知道結束，我一開始傳 `0\r\n\r\n` ，結果導致瀏覽器還是在讀取。
完成後，目前已經可以正常運作，瀏覽器也沒有繼續讀取問題。
## TODO: 引入 timer，讓 kHTTPd 主動關閉逾期的連線
此處我的想法是在 `http_server_worker` (用來處理已經建立連線的 socket)中將該 socket 設定為 non-blocking，並設置一個計時器，每次如果有正確接收到資料時，則將計時器重置，當計時器倒數結束，代表已經長時間沒有接收到資料，則主動關閉連線。
首先，為了設置為 non-blocking ，首先透過將 `http_server_recv` 中的 flag 設定為 `MSG_DONTWAIT`。
接收訊息過程中，假如沒有收到資料，會回傳錯誤代碼 -11 ，也因此針對此處做修改：
```c
static int http_server_recv(struct socket *sock, char *buf, size_t size)
{
struct kvec iov = {.iov_base = (void *) buf, .iov_len = size};
struct msghdr msg = {.msg_name = 0,
.msg_namelen = 0,
.msg_control = NULL,
.msg_controllen = 0,
.msg_flags = MSG_DONTWAIT};
return kernel_recvmsg(sock, &msg, &iov, 1, size, msg.msg_flags);
}
```
如果收到的回覆是 -11 ，那就再繼續接收，直到有資料為止：
```c
int ret = http_server_recv(socket, buf, RECV_BUFFER_SIZE - 1);
if (ret <= 0) {
if (ret == -11)
continue;
else
break;
}
```
我嘗試加入 timer 來完成上述實做，但我發現一旦加入 timer 的部份就會導致系統崩潰：
```c
struct timer_content now_timer;
now_timer.socket = socket;
timer_setup(&now_timer.timer, clear_socket, 0);
mod_timer(&now_timer.timer, jiffies + msecs_to_jiffies(10000));
while (!kthread_should_stop()) {
int ret = http_server_recv(socket, buf, RECV_BUFFER_SIZE - 1);
if (ret <= 0) {
if (ret == -11)
continue;
else
break;
}
del_timer_sync(&now_timer.timer);
mod_timer(&now_timer.timer, jiffies + msecs_to_jiffies(10000));
http_parser_execute(&parser, &setting, buf, ret);
if (request.complete && !http_should_keep_alive(&parser))
break;
memset(buf, 0, RECV_BUFFER_SIZE);
}
```
另外，如果將 recv 設定為 non-blocking ，等於對所有的連線都要這麼設置，會對 cpu 有比較大的負擔，系統也會有下面的提示：
```
workqueue: http_server_worker [khttpd] hogged CPU for >10000us 4 times, consider switching to WQ_UNBOUND
```
考量這些因素後，或許改為定期清理超時的連結會是比較好的方法？
目前有考慮以下幾種清理超時連接的方法:
1. 透過優先權佇列，將持續過久的連線中斷，但缺點是如果用戶仍持續在進行通訊，只是連線比較久也會被中斷，而且可能會在資料傳輸中途將其中斷。
2. 透過 hash_map 來記錄每個連線，每次檢查 hash_map 所有節點並將過久沒有通訊的連接中斷。
目前較傾向使用第二種方法。
:::warning
探討 seHTTPd 的作法，先有量化分析，再來討論。
:::
在 seHTTPd 中，使用的是 priority_queue ，在 mainloop 中透過 `handle_expired_timers` 來不斷更新目前時間，並檢查是否有超時連結，假設連結超時， priority_queue 會刪除該節點並執行對應操作，此處就是關閉連結。
需要注意的是，假如用戶有在傳輸資料，每次傳輸後會將 priority_queue 中的節點修改為已刪除 (不是真的刪除，但該節點會被標記) 然後插入一個新的節點來記錄新的時間。
換句話說，假如在清理超時節點時，發現一個節點狀態為未刪除且超時，代表這個連結已經逾時，即可將該節點中斷。
比較特別的是，設定的預設 priority_queue 大小是 10 ，這在連接數較多的情況下這樣可能會不夠，而 seHTTPd 有針對這個情況進行處理，在 insert 前會先檢查目前還有沒有剩餘空間，如果沒有剩餘空間會透過 resize 來重新建立一個兩倍大小的空間存放 priority_queue。
而當要刪除 priority_queue 中的節點時，也會檢查目前節點數和最大容量，假如目前節點數不滿最大容量的 1/4 時，會將容量透過 resize 砍半，但這會導致要重新分配記憶體空間，儘管可以釋放一半的空間，但在時間上是否更有利可能要透過後續實驗檢查。
回到 khttpd ，每個連接被視為一個 work ，考慮到這點，應是要有一個共同的 priority_queue，並且當每個 work 接收到訊息時如前面提到的插入一個節點，並將自身原本的節點設置為 delete，然後由另一個 kthread 或 work 進行定期的清理(也能將 accept 改為 non-blocking 後直接在主迴圈做)。
考慮到 race condition ，在對 priority_queue 操作時應該要有 spinlock 等同步機制。
以下是一些需要的函式和結構。
```c
typedef int (*timer_callback)(struct socket *socket);
typedef struct {
size_t key; // time
bool deleted;
timer_callback callback;
struct socket *socket;
} timer_node;
int pq_timer_init(void);
void handle_expired_timers(void);
timer_node *add_pq_timer(struct socket *socket,
size_t timeout,
timer_callback cb);
void del_pq_timer(timer_node *node);
```
`add_pq_timer` 會新增一個 `timer_node` 到 `priority_queue`，並回傳這個 node 的位址，`worker`會紀錄下這個位址。
當用戶再次送出請求時，會將原本的 node 設定為刪除，並再次使用 `add_pq_timer` 插入一個新節點。
`del_timer` 則很單純，就是前面提到的，將節點標記為 deleted ，也就是後續如果被判定超時不會執行其 callback function。
因此整體程式架構如下:
```c
while (!kthread_should_stop()) {
int ret = http_server_recv(socket, buf, RECV_BUFFER_SIZE - 1);
if (ret <= 0) {
printk("%p disconnected!", socket);
break;
}
del_pq_timer(t_node);
t_node = add_pq_timer(request.socket, TIME_OUT, clear_socket);
http_parser_execute(&parser, &setting, buf, ret);
if (request.complete && !http_should_keep_alive(&parser))
break;
memset(buf, 0, RECV_BUFFER_SIZE);
}
```
每次收到新資料時，使用 `del_min` 把原本的節點標記為刪除，並插入新節點。
以下是圖解，假設建立了一個連接，目前時間是 100 ，timeout 為 20，會先插入一個節點並設定 timeout， 然後開始等待接收資料:
```graphviz
digraph QueueRelationships {
node [shape=record, fontname="Arial"];
// Define the queue context, which manages individual queues
new_connection [label="{ timeout: 120|deleted = false}", style=filled, fillcolor=lightblue];
head->new_connection
}
```
假如在 timeout 前接收到新的資料，例如在 110 時收到資料，則再插入一個節點，並把目前的節點設定為 deleted。
```graphviz
digraph QueueRelationships {
node [shape=record, fontname="Arial"];
// Define the queue context, which manages individual queues
old_connection [label="{ timeout: 120|deleted = true}", style=filled, fillcolor=white];
new_connection [label="{ timeout: 130|deleted = false}", style=filled, fillcolor=lightblue];
head->old_connection->new_connection,unused
}
```
每秒會有另一個 thread 在檢查是否有逾時連結，例如在 121 時，會檢查到原本舊的節點逾時了，這時檢查其 deleted，因為是 false ，代表這個連結後續有再發送請求，所以直接刪除不需要額外操作。
```graphviz
digraph QueueRelationships {
node [shape=record, fontname="Arial"];
// Define the queue context, which manages individual queues
new_connection [label="{ timeout: 130|deleted = false}", style=filled, fillcolor=white];
head->new_connection
}
```
在 131 時，如果程式再次檢查，會再次發現逾時連結，這時檢查 deleted 為 false ，代表這個連接真的已經很久沒有發送請求，判定為逾時連結，因此執行 callback ，這裡就是把 socket 關起來。
完整的修改請見: [Finish timer function](https://github.com/fatcatorange/khttpd/commit/060fc2fe222defee6aab91a772b35547ca0f6962)
目前成果如下，當用戶沒有新的請求超過 10 秒，會被自動中斷連接:
```shell
telnet localhost 8081
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
GET / HTTP/1.1
HTTP/1.1 200 OK
Connection: Keep-Alive
Content-Type: text/html
Transfer-Encoding: chunked
7B
<html><head><style>
body{font-family: monospace; font-size: 15px;}
td {padding: 1.5px 6px;}
</style></head><body><table>
2f
<tr><td><a href="/khttpd">khttpd</a></td></tr>
16
</table></body></html>
0
//10秒後
Connection closed by foreign host.
```
:::danger
依據 [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary) 和 [詞彙對照表](https://hackmd.io/@l10n-tw/glossaries) 的用語，調整開發紀錄。
:::
## TODO: 藉由 RCU 在並行環境中得以釋放系統資源
考量到某些目錄可能非常少被存取到，但現有的機制仍會為其保留快取，會導致占用額外的空間，因此這裡希望透過與前面關閉逾時連結相同的概念，當一個目錄已經非常久無人存取，應該將其佔用的快取空間釋放。
考慮到快取是透過 hash 存取，且寫入次數少(僅在第一次存取該目錄和過久無人存取時)，讀取次數多(只要有用戶存取到存在快取中的目錄，就必須存取快取)，適合使用 RCU 處理，但須注意因為同時有多個修改的可能(同時在插入和刪除)，在刪除和插入時仍須有 `spinlock`。
以下為釋放快取空間的函式，先透過 hlist_del_rcu 刪除 hash 內的節點，再透過 list_for_each_entry_safe 刪除所有標籤的節點。
```c
int hash_delete(void *con)
{
spin_lock(&cache_lock);
struct hash_content * content = con;
hlist_del_rcu(&content->node);
struct tag_content *now;
struct tag_content *tmp;
list_for_each_entry_safe(now, tmp ,content->head, tag_list) {
list_del_rcu(&now->tag_list);
kfree(now);
}
kfree(content);
spin_unlock(&cache_lock);
}
```
接下來稍微修改 `timer_node` 的結構，使其不只可以用來中斷 socket 的連結：
```diff
typedef struct {
size_t key; // time
bool deleted;
timer_callback callback;
- struct socket *socket;
+ void *object;
} timer_node;
```
`timer_callback` 等函式也做相同的修改：
```diff!
+typedef int (*timer_callback)(void *);
-typedef int (*timer_callback)(struct socket * socket);
```
此處要傳入的`timer_callback` 就是 `hash_delete` ，並且稍微修改`hash_insert`和`hash_check`:
```diff
void hash_insert(const char *request, struct list_head *head)
{
spin_lock(&cache_lock);
hash_add_rcu(ht, &content->node, key);
spin_unlock(&cache_lock);
+ content->timer = add_pq_timer(content, CACHE_TIME_OUT, hash_delete);
}
```
```diff
bool hash_check(const char *request, struct list_head **head)
{
```
if (strcmp(request, now->request) == 0) {
*head = now->head;
+ del_pq_timer(now->timer);
+ now->timer = add_pq_timer(now, CACHE_TIME_OUT, hash_delete);
rcu_read_unlock();
return true;
}
```
}
```
第一次存取該目錄時，會插入一個 `timer_node` ，當有用戶再次存取時，會先透過 `hash_check` 檢查是否有快取存在，假設存在的話會刪除原 `timer_node` 並插入一個新節點，整體概念和處理逾時連結非常類似。
目前當短時間內再次有人存取該目錄，可以直接使用快取回傳資料，而當長時間沒有人存取會清除該目錄的快取，下次有人存取必須再檢查一次該目錄下的檔案。
也因此，目前的 `timer` 包含兩個功能，第一是清除逾時連結，第二是清除無人使用的快取，兩邊資料存在同個 priority_queue。
## TODO: 修正 kHTTPd 的執行時期缺失
### kzalloc 失敗處理:
我注意到 `kzalloc` 失敗時的處理機制:
```c
buf = kzalloc(RECV_BUFFER_SIZE, GFP_KERNEL);
if (!buf) {
pr_err("can't allocate memory!\n");
return -1;
}
```
分配失敗時，會直接返回，但此時該 worker 已經被分配了 socket ，這樣會導致 socket 沒有被釋放。
修改非常容易，加入以下兩行即可:
```diff
buf = kzalloc(RECV_BUFFER_SIZE, GFP_KERNEL);
if (!buf) {
pr_err("can't allocate memory!\n");
+ kernel_sock_shutdown(socket, SHUT_RDWR);
+ sock_release(socket);
return -1;
}
```
Sign in with Wallet
Connect another wallet