## 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 舉例來說：

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 指標，以圖例來說明的話：

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 指標。

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 加入即可。

static int list_rcu_example_init(void)
{
	spin_lock_init(&books_lock);

	test_example(0);
	test_example(1);
	return 0;
}

因為程式已經把範例內容寫在 init 內， 載入後檢查 dmesg 即可看到執行狀況：

[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 工具和一致的程式撰寫風格」，筆記列出的程式碼依循指定的風格。
:::

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:

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 工具和一致的程式撰寫風格」，筆記列出的程式碼依循指定的風格。
:::

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> ，先寫出一個類似的程式進行追蹤：

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`作為目標，這個函式出現在：

worker = kthread_run(http_server_worker, socket, KBUILD_MODNAME);

主要功能就是在 accept 後創建執行緒來服務該用戶。

可以發現，當有用戶開始連接時，如果有執行 bcc 程式，就可以攔截到事件並執行一些行為：

client:

telnet localhost 1999
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.

我原先希望透過教學檢查 fib_read 的方法來檢測建立執行緒的成本，但產生了一個問題：

在 bpf 中，我應是要加入要檢測的函式，然而執行緒建立的函式如下：

worker = kthread_run(http_server_worker, socket, KBUILD_MODNAME);

我一開始選擇監測 http_server_worker ，但會產生一個問題，就是 http_server_worker 只有在斷開連線時才會結束（也就是 client 端關閉連線時），因此這樣透過：

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 的前後各加入一個空的函式，例如：

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
後來發現，很多函式雖然可以讀到，但是沒辦法檢測，不知道為什麼？

如果讀取某些函式，會出現如下錯誤：

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);`
並透過：

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

接下來透過作業說明前半部份提到的方法進行測試：

ab -n 10000 -c -10000 -k http://127.0.0.1:8081/

但發現好像不能同時建立這麼多執行緒，同時產生大約只能 5000:


透過 curl 慢慢發送 1000 個訊息：

#!/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:

khttpd_wq = alloc_workqueue("khttpd", 0, 0);

在 server.c 中，先建立一個 daemon_list 作為這個 workqueue 的開頭。

INIT_LIST_HEAD(&daemon_list.head);

接下來，在 server.c 中，參考 [kecho](https://github.com/sysprog21/kecho/blob/master/echo_server.c) ，先使用 create_work 建立工作：

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。

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 `這個成員：

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 時，就可以透過：

struct socket *socket =
    container_of(w, struct http_request, khttpd_work)->socket;

來取得 socket 的指標。

值得一提的是，在 create_work 中，有一段程式碼：

list_add(&work->node, &daemon_list.head);

因為之前作業 6 的 ksort 有使用到 queue_work ，但似乎沒有用到這個部份，因此我嘗試移除這行敘述，執行結果則完全相同。

:::danger
注意用語：instruction 是「指令」，但本處不該用該這樣用，可改說「敘述」(statement)
:::

因為 create_work 應該只是幫這個工作初始化，真正加入應是等到：

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。

而這個函式被使用在:

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 工具和一致的程式撰寫風格」，筆記列出的程式碼依循指定的風格。
:::

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>，走訪並檢查需要的目錄，具體內容為：

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 指定為該函式，代表走訪時執行該函式。

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` 即可。

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` ，在載入模組時指定路徑即可：

module_param_string(WWWROOT, WWWROOT, PATH_SIZE, 0);
..
daemon_list.dir_path = WWWROOT;

將路徑部份替換為 `daemon_list.dir_path`:

fp = filp_open(daemon_list.dir_path,
                O_RDONLY | O_DIRECTORY, 0);

### 根據路徑開啟檔案

首先，必須先判斷目前路徑是目錄還是檔案，因此可透過：

S_ISDIR(fp->f_inode->i_mode)

和

S_ISREG(fp->f_inode->i_mode)

來判斷是檔案或目錄。

假如是目錄，則使用跟之前一樣的方法，透過 `iterate_dir`來對目錄進行檢查：

 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));

    }

要注意的是，如果是檔案的話，要先取得檔案大小並分配空間：

char *read_data = kmalloc(fp->f_inode->i_size, GFP_KERNEL);

然後透過：

kernel_read(fp, buf, fp->f_inode->i_size, 0);

來讀取該檔案。

目前當點選目錄時，就可以進入更內層目錄，點選檔案則會顯示內容：

但目前有個問題，當進入深層的目錄時，再點選資料夾或目錄會找不到檔案，這是因為路徑是透過組合成的，假如有個檔案的位置是 ../khttpd/bcc/FAQ.txt ，組合出的路徑會是 ../khttpd/FAQ.txt。

### 修正問題

主要問題是在回傳時設定的 `href` 錯誤：

snprintf(buf, SEND_BUFFER_SIZE,
                 "<tr><td><a href=\"%s\">%s</a></td></tr>\r\n", name, name);

這裡的 name 是這個檔案的名稱，如果直接把拿來當路徑就會發生前面提到的狀況，我們需要把這個名稱和前面的路徑組合：

strcpy(des,request->request_url);
strcat(des, "/");
strcat(des, name);

需要注意的是，如果是第一層目錄，原本 `request->request_url` 就是 `/`，因此要排除這個情況，完整程式碼如下：

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);

完成後，已經可以順利點擊目錄進入更深層的檔案：


### 回前頁功能

目前想回到上一頁只能透過瀏覽器選擇回上頁完成，這裡嘗試增加一個選項來完成，原本只有在目前名稱不是 `..` 或 `.` 才會執行，稍微進行修改，讓 `..` 可以進入：

-if (strcmp(name, ".") && strcmp(name, ".."))
+if (strcmp(name, ".") )

但這會出現幾個問題，首先，在第一頁不需要這個按鈕，另外，這個 `..` 在目錄中不一定是在最上面，但顯示給使用者的界面中應該要在最上面：

目前想法是，假如目前路徑不是 `\` ，則直接插入一個 `..` ，並參考學長作法，如果網址最後面試 `\`，則直接去掉該欄：

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 前進行：

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 來檢測：

先檢查可以被檢測的函式：

sudo cat ls /sys/kernel/debug/tracing/available_filter_functions | grep khttpd

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 檢測是哪部份花了最多時間：

#!/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` 花費了非常多時間：

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 工具和一致的程式撰寫風格」，筆記列出的程式碼依循指定的風格。
:::

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 ，並執行插入動作：

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` 中：

if(!hash_check(request->request_url))
    hash_insert(request->request_url, buf);

現在的目標就是把 trace_dir 中產生的各種 `html` 標籤暫存起來，這樣如果有用戶再次存取這個界面，就可以直接給他暫存的資料，而不需要再次透過 `trace_dir` 存取目錄。

目前的問題是，如果將這些標籤全部存在一個字串內，萬一該目錄下的檔案很多，我沒辦法確定要多長的字串才能處理，所以這裡我的想法是，我透過 linked-list 來存放每一筆資料：

在 `http_request` 中加入一個用來紀錄目錄檔案的 tag_list:

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：

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 中：

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 ，每個節點中內容如下：

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 中：

hash_insert(request->request_url, head);

假如後續還有用戶再次來訪這個頁面，因為已經有存放在 hash 中了，可以直接透過 hash 內的 head 透過:

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 的函式：

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 的效益和測試方法。
:::

### 實驗檢查效能是否提昇：

以下為實驗結果：

./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`:

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 進行傳輸:

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。

參考作業說明，只要在傳輸前先傳送資料長度即可(注意這個長度要非常精準，多或少都會導致瀏覽器卡住)，例如:

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 ，也因此針對此處做修改：

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 ，那就再繼續接收，直到有資料為止：

int ret = http_server_recv(socket, buf, RECV_BUFFER_SIZE - 1);
if (ret <= 0) {
    if (ret == -11)
        continue;
    else
        break;
}

我嘗試加入 timer 來完成上述實做，但我發現一旦加入 timer 的部份就會導致系統崩潰：

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 等同步機制。

以下是一些需要的函式和結構。

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。

因此整體程式架構如下:

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， 然後開始等待接收資料:

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。

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 ，代表這個連結後續有再發送請求，所以直接刪除不需要額外操作。

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 秒，會被自動中斷連接:

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 刪除所有標籤的節點。

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 的連結：

typedef struct {
    size_t key;  // time
    bool deleted;
    timer_callback callback;
-   struct socket *socket; 
+   void *object;
} timer_node;

`timer_callback` 等函式也做相同的修改：

+typedef int (*timer_callback)(void *);
-typedef int (*timer_callback)(struct socket * socket);

此處要傳入的`timer_callback` 就是 `hash_delete` ，並且稍微修改`hash_insert`和`hash_check`:

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);
}

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` 失敗時的處理機制:

buf = kzalloc(RECV_BUFFER_SIZE, GFP_KERNEL);
if (!buf) {
    pr_err("can't allocate memory!\n");
    return -1;
}

分配失敗時，會直接返回，但此時該 worker 已經被分配了 socket ，這樣會導致 socket 沒有被釋放。

修改非常容易，加入以下兩行即可:

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;
}