# 2020q1 Homework4 (khttpd)
contributed by < `StevenChen8759` >
###### tags: `linux2020`
> [作業說明 - khttpd](https://hackmd.io/@sysprog/linux2020-khttpd)
> [作業繳交區](https://hackmd.io/@sysprog/linux2020-homework4)
> [Github](https://github.com/StevenChen8759/khttpd)
> [color=lightgreen]
# :computer: 功能開發記錄
## :camera: `khttpd` 運作分析與 `HTTP Response` 訊息修改
* 首先，我們觀察 `khttpd` 回覆要求的執行流程。
* 在模組安裝到核心時，我們透過自訂的 [Make Target](https://github.com/StevenChen8759/khttpd/blob/master/Makefile) 查看模組與網路的狀態
```shell
$ make
...
$ make load
sudo insmod khttpd.ko port=8081
$ make stat
------------------------------------------------------------------------
lsmod | grep khttpd
khttpd 40960 0
------------------------------------------------------------------------
sudo netstat -antp
Active Internet connections (servers and established)
Proto Recv-Q Send-Q Local Address Foreign Address State PID/Program name
tcp 0 0 0.0.0.0:8081 0.0.0.0:* LISTEN -
tcp 0 0 127.0.1.1:53 0.0.0.0:* LISTEN 1054/dnsmasq
tcp 0 0 127.0.0.1:631 0.0.0.0:* LISTEN 2356/cupsd
tcp6 0 0 ::1:631 :::* LISTEN 2356/cupsd
```
* 觀察以上輸出訊息，可發現在插入模組的初始化 Callback 時已開啟 Socket ，[對應的程式碼](https://github.com/StevenChen8759/khttpd/blob/master/main.c)如下：
```cpp=93
static int __init khttpd_init(void)
{
int err = open_listen_socket(port, backlog, &listen_socket);
if (err < 0) {
pr_err("can't open listen socket\n");
return err;
}
param.listen_socket = listen_socket;
http_server = kthread_run(http_server_daemon, ¶m, KBUILD_MODNAME);
if (IS_ERR(http_server)) {
pr_err("can't start http server daemon\n");
close_listen_socket(listen_socket);
return PTR_ERR(http_server);
}
return 0;
}
```
* 觀察上述程式，除了開啟對應的 Socket 以外，初始化 Callback 亦同時創建了一個 Kernel Thread，其 callback 為 `http_server_daemon` ，負責 `Socket Accept` 的處理，[對應的程式碼](https://github.com/StevenChen8759/khttpd/blob/master/http_server.c)如下：
```cpp=188
int http_server_daemon(void *arg)
{
struct socket *socket;
struct task_struct *worker;
struct http_server_param *param = (struct http_server_param *) arg;
allow_signal(SIGKILL);
allow_signal(SIGTERM);
while (!kthread_should_stop()) {
int err = kernel_accept(param->listen_socket, &socket, 0);
if (err < 0) {
if (signal_pending(current))
break;
pr_err("kernel_accept() error: %d\n", err);
continue;
}
worker = kthread_run(http_server_worker, socket, KBUILD_MODNAME);
if (IS_ERR(worker)) {
pr_err("can't create more worker process\n");
continue;
}
}
return 0;
}
```
* 觀察上述 `kernel_accept` 的呼叫，在每一次的裝置連結時， `http_server_daemon` 將會再創建一個 Kernel Thread，其 Callback 為 `http_server_worker` ，以處理連結裝置的 Request， 並將相應的 Response 回傳給 Client，[對應程式碼](https://github.com/StevenChen8759/khttpd/blob/master/http_server.c)如下：
```cpp=144
static int http_server_worker(void *arg)
{
char *buf;
struct http_parser parser;
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};
struct http_request request;
struct socket *socket = (struct socket *) arg;
allow_signal(SIGKILL);
allow_signal(SIGTERM);
buf = kmalloc(RECV_BUFFER_SIZE, GFP_KERNEL);
if (!buf) {
pr_err("can't allocate memory!\n");
return -1;
}
request.socket = socket;
http_parser_init(&parser, HTTP_REQUEST);
parser.data = &request;
while (!kthread_should_stop()) {
int ret = http_server_recv(socket, buf, RECV_BUFFER_SIZE - 1);
if (ret <= 0) {
if (ret)
pr_err("recv error: %d\n", ret);
break;
}
http_parser_execute(&parser, &setting, buf, ret);
if (request.complete && !http_should_keep_alive(&parser))
break;
}
kernel_sock_shutdown(socket, SHUT_RDWR);
sock_release(socket);
kfree(buf);
return 0;
}
```
* 觀察此 Callback 中的 `setting` 變數，此變數是用於控制模組 `http_parser` 在 Request 解析過程中所呼叫的本地 Callback，在 [http_server.c](https://github.com/StevenChen8759/khttpd/blob/master/http_server.c) 中可找到對應各執行階段的 callback。
* 因為我們欲從輸入的網址 (URL) 找出欲回傳的費氏數，故我們觀察以下在 [http_server.c](https://github.com/StevenChen8759/khttpd/blob/master/http_server.c) 中的 callback 函式：
```cpp=99
static int http_parser_callback_request_url(http_parser *parser,
const char *p,
size_t len)
{
struct http_request *request = parser->data;
strncat(request->request_url, p, len);
return 0;
}
```
```cpp=136
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;
}
```
* `http_parser` 會自動替我們取得 Request 的 URL，並在訊息接收完成後呼叫對應的 Response 函式，如下所示：
```cpp=76
static int http_server_response(struct http_request *request, int keep_alive)
{
char *response;
pr_info("requested_url = %s\n", request->request_url);
if (request->method != HTTP_GET)
response = keep_alive ? HTTP_RESPONSE_501_KEEPALIVE : HTTP_RESPONSE_501;
else
response = keep_alive ? HTTP_RESPONSE_200_KEEPALIVE_DUMMY
: HTTP_RESPONSE_200_DUMMY;
http_server_send(request->socket, response, strlen(response));
return 0;
}
```
* `http_server_response` 會根據 HTTP 的 Request 方法 (e.g. GET, POST...等) 回應對應的訊息，四種訊息對應的 Marco 如下所示：
```cpp=12
#define HTTP_RESPONSE_200_DUMMY \
"" \
"HTTP/1.1 200 OK" CRLF "Server: " KBUILD_MODNAME CRLF \
"Content-Type: text/plain" CRLF "Content-Length: 12" CRLF \
"Connection: Close" CRLF CRLF "Hello World!" CRLF
#define HTTP_RESPONSE_200_KEEPALIVE_DUMMY \
"" \
"HTTP/1.1 200 OK" CRLF "Server: " KBUILD_MODNAME CRLF \
"Content-Type: text/plain" CRLF "Content-Length: 12" CRLF \
"Connection: Keep-Alive" CRLF CRLF "Hello World!" CRLF
#define HTTP_RESPONSE_501 \
"" \
"HTTP/1.1 501 Not Implemented" CRLF "Server: " KBUILD_MODNAME CRLF \
"Content-Type: text/plain" CRLF "Content-Length: 21" CRLF \
"Connection: Close" CRLF CRLF "501 Not Implemented" CRLF
#define HTTP_RESPONSE_501_KEEPALIVE \
"" \
"HTTP/1.1 501 Not Implemented" CRLF "Server: " KBUILD_MODNAME CRLF \
"Content-Type: text/plain" CRLF "Content-Length: 21" CRLF \
"Connection: KeepAlive" CRLF CRLF "501 Not Implemented" CRLF
```
* 參考 `HTTP_RESPONSE_200_DUMMY` 與 `HTTP_RESPONSE_200_KEEPALIVE_DUMMY` 兩個 Marco，可見到我們透過 `wget` 連接 `127.0.0.1:2020` 回應的 `Hello World!` 字串，如下所示 (搭配自訂的 [Make Target](https://github.com/StevenChen8759/khttpd/blob/master/Makefile))：
```shell
$ make request PORT=2020
wget 127.0.0.1:2020/
--2020-04-03 01:01:47-- http://127.0.0.1:2020/
Connecting to 127.0.0.1:2020... connected.
HTTP request sent, awaiting response... 200 OK
Length: 32 [text/plain]
Saving to: ‘index.html.2’
index.html.2 100%[================================================================>] 32 --.-KB/s in 0s
2020-04-03 01:01:47 (3.64 MB/s) - ‘index.html.2’ saved [32/32]
```
```shell
$ cat index.html.2
Hello World! Fibonacci Number.
```
:::warning
可用 `$ wget -O - http://foo > file` 搭配 redirection 來驗證 Fibonacci 數的計算是否符合預期
:notes: jserv
:::
* 在上述的測試中，我們針對回應的字串做出修改，並調整原始 Response 中的字串長度以符合新字串的長度 (12 -> 32)。
* 因此，我們只要==針對字串與字串長度進行動態地修改==，即可正確地以文字的方式回傳 Request 中所指定的 Fibonacci Number。
## :camera: 整合自訂的大數運算型別 (char-based)
* 在先前[自訂的 `bignum` 實現](https://github.com/StevenChen8759/fibdrv/tree/master/bignum)中，我們使用了字元運算搭配鏈結串列，藉以正確地儲存位數極大的費氏數。
> 在此版本的大數型別實作中，測試回傳 F[10000] 時的執行時間不甚理想，甚至在測試 F[30000] 時直接造成系統崩潰，仍有很大的改善空間。(原有實現改以 `Fast Doubling` 方法實作 or 整合 [jserv 老師的 `bignum` 實作](https://github.com/sysprog21/bignum)、記憶體配置改善......等 )
> [name=Steven HH Chen][time=Sat, Apr 5, 2020 3:30 PM][color=red]
* 但是先前的實現並未成功地整合到 `fibdrv` 中，其主因在於 <font color=red>程式的系統呼叫函式庫是從 User Space 呼叫 Kernel Space</font>，無法適用在 Kernel Space 的程式呼叫！
* 因此，我們必須將==舊有的一些系統呼叫置換成適用於 Kernel Space 的系統呼叫==，如下列的置換對應：
| 適用於 User Space 的系統呼叫 | 對應適用於 Kernel Space 的呼叫 |
| ---------------------------- | ------------------------------ |
| printf() | printk() 或 pr_info() ...等 |
| malloc() | kmalloc() |
| calloc() | kcalloc() |
| free() | kfree() |
> 可透過 `條件式編譯` 的技巧，選擇程式在編譯時是使用 `User Space` 或 `Kernel Space` 的系統呼叫，並輸出適合 `User Space` 或 `Kernel Space` 的 Object。
> [color=green]
* 除此之外，為方便處理 Response 字串的串接，故在 `bignum` 中新增函式 `bn_tostring_and_free` ，此函式會將大數轉換成字串(字元陣列)回傳，並同時釋放大數所占用的空間。實作如下：
```cpp=206
char *bn_tostring_and_free(bignum_t **bnum)
{
int i;
char *str;
bnlist_t *ptr;
if (*bnum == NULL)
return NULL;
str = (char *) kcalloc((*bnum)->cnt_d + 1, sizeof(char), GFP_KERNEL);
ptr = (*bnum)->msd;
for (i = 0; i < (*bnum)->cnt_d; i++) {
str[i] = ptr->value + 0x30;
ptr = ptr->next;
}
bn_free(*bnum);
*bnum = NULL;
return str;
}
```
* 在 [main.c](https://github.com/StevenChen8759/khttpd/blob/master/main.c) 中整合 `bignum`，並呼叫函式測試其功能，實作如下：
```cpp=9
#include "bignum.h"
```
```cpp=94
static int __init khttpd_init(void)
{
bignum_t *fibn = bn_fibonacci(60);
pr_info("fibnum is : %s", bn_tostring_and_free(&fibn));
// bn_free(fibn);
int err = open_listen_socket(port, backlog, &listen_socket);
if (err < 0) {
pr_err("can't open listen socket\n");
return err;
}
param.listen_socket = listen_socket;
http_server = kthread_run(http_server_daemon, ¶m, KBUILD_MODNAME);
if (IS_ERR(http_server)) {
pr_err("can't start http server daemon\n");
close_listen_socket(listen_socket);
return PTR_ERR(http_server);
}
return 0;
}
```
* 修改 `Makefile` 中編譯核心模組相關的變數，並執行編譯，實作如下：
```diff
$ git diff 54194e b8bfe3
diff --git a/Makefile b/Makefile
index c478aa4..41e4792 100644
--- a/Makefile
+++ b/Makefile
@@ -5,13 +5,14 @@ LDFLAGS_user = -lpthread
obj-m += khttpd.o
khttpd-objs := \
+ bignum.o \
http_parser.o \
http_server.o \
main.o
GIT_HOOKS := .git/hooks/applied
-all: $(GIT_HOOKS) http_parser.c htstress
+all: $(GIT_HOOKS) bignum.c http_parser.c htstress
make -C $(KDIR) M=$(PWD) modules
$(GIT_HOOKS):
```
```shell
$ make
cc -std=gnu99 -Wall -Wextra -Werror -o htstress htstress.c -lpthread
make -C /lib/modules/4.15.0-91-generic/build M=/home/stch/linux2020/khttpd modules
make[1]: Entering directory '/usr/src/linux-headers-4.15.0-91-generic'
CC [M] /home/stch/linux2020/khttpd/bignum.o
CC [M] /home/stch/linux2020/khttpd/http_parser.o
CC [M] /home/stch/linux2020/khttpd/http_server.o
CC [M] /home/stch/linux2020/khttpd/main.o
LD [M] /home/stch/linux2020/khttpd/khttpd.o
Building modules, stage 2.
MODPOST 1 modules
CC /home/stch/linux2020/khttpd/khttpd.mod.o
LD [M] /home/stch/linux2020/khttpd/khttpd.ko
make[1]: Leaving directory '/usr/src/linux-headers-4.15.0-91-generic'
```
* 成功編譯後，將[模組掛載](https://github.com/StevenChen8759/khttpd/blob/master/Makefile)至核心，並觀察 `dmesg` 輸出費氏數列的第 60 項：
```shell
$ make load
...
$ dmesg
...
[66587.574298] khttpd: fibnum is : 1548008755920
...
```
## :camera: 建立任意輸入費氏數的 Response (Via URL 輸入)
* 首先，我們先統整常用的數值與字串處理函式在 `Kernel Space` 執行的替代：
| 適用於 User Space 的系統呼叫 | 對應適用於 Kernel Space 的呼叫 |
| ---------------------------- | ------------------------------ |
| itoa() | snprintf() |
| atoll() | kstrtoll () |
| strtok() | strsep() |
| strncpy() | 無須替換，或可採用 snprintf() |
* 參考 [基於 `strsep()` 之 URL 傳遞參數分割法](https://blog.wu-boy.com/2010/04/cc-c%E8%AA%9E%E8%A8%80%E5%88%87%E5%89%B2%E5%AD%97%E4%B8%B2%E5%87%BD%E5%BC%8F-strsep%EF%BC%8C%E5%88%86%E6%9E%90-url-get-%E5%8F%83%E6%95%B8/) ，在 `http_response` 函式內實作 URL 分割，輸出結果如下：
```shell
$ make reload
...
$ make request RFILE=fib/10
...
$ dmesg
[82143.401840] khttpd: requested_url = /fib/10, len = 7
[82143.401844] khttpd: sep / -> url afetr: 10, ptr return: fib
```
* 透過檢查字串是否符合我們的輸入後，計算指定輸入的費氏數列，並將其打印在 dmesg 上，結果如下：
```shell
[82143.401840] khttpd: requested_url = /fib/10, len = 7
[82143.401844] khttpd: sep / -> url afetr: 10, ptr return: fib
[82143.401849] khttpd: F[10] = 55
[82143.401849] khttpd: free fib!
[82160.456446] khttpd: requested_url = /fib/10000, len = 10
[82160.456451] khttpd: sep / -> url afetr: 10000, ptr return: fib
[82185.911054] khttpd: F[10000] = 3364476487643178326662161200510754331030214846068006390656476997468008144216666236815559551363373402558206533268083615937373479048386526826304089246305643188735454436955982749160660209988418393386465273130008883026923567361313511757929743785441375213052050434770160226475831890652789085515436615958298727968298751063120057542878345321551510387081829896979161312785626503319548714021428753269818796204693609787990035096230229102636813149319527563022783762844154036058440257211433496118002309120828704608892396232883546150577658327125254609359112820392528539343462090424524892940390170623388899108584106518317336043747073790855263176432573399371287193758774689747992630583706574283016163740896917842637862421283525811282051637029808933209990570792006436742620238978311147005407499845925036063356093388383192338678305613643535189213327973290813373264265263398976392272340788292817795358057099369104917547080893184105614632233821746563732124822638309210329770164805472624384
```
* 在建立費氏數計算的機制後，我們著手修改定義的 Macro，並以 `snprintf()` 函式整合計算的費氏數以及 HTTP Response 文字格式，並==嚴格管制回傳字串的記憶體空間配置==，實作如下：
```cpp=11
#define CRLF "\r\n"
#define HTTP_RESPONSE_200_DUMMY \
"" \
"HTTP/1.1 200 OK" CRLF "Server: " KBUILD_MODNAME CRLF \
"Content-Type: text/plain" CRLF "Content-Length: %zu" CRLF \
"Connection: Close" CRLF CRLF "%s" CRLF
#define HTTP_RESPONSE_200_KEEPALIVE_DUMMY \
"" \
"HTTP/1.1 200 OK" CRLF "Server: " KBUILD_MODNAME CRLF \
"Content-Type: text/plain" CRLF "Content-Length: %zu" CRLF \
"Connection: Keep-Alive" CRLF CRLF "%s" CRLF
```
```cpp=79
char *respmsg_edition(char *msg, int keep_alive)
{
char *rpmsg = NULL;
int msgl;
size_t rpmsglen;
// Calculate space needed for response message return
// KEEPALIVE_DUMMY vs DUMMY, excluding 5 characters "%zu" and "%s"
rpmsglen = keep_alive ? strlen(HTTP_RESPONSE_200_KEEPALIVE_DUMMY) - 5
: strlen(HTTP_RESPONSE_200_DUMMY) - 5;
// Add msg length into needed space
rpmsglen += strlen(msg);
// Probing the length of strlen(msg) and add into needed space
rpmsg = (char *) kcalloc(strlen(msg) + 1, sizeof(char), GFP_KERNEL);
if (rpmsg == NULL) {
pr_err("Allocate space for response message fail...");
return NULL;
}
msgl = snprintf(rpmsg, strlen(msg), "%zu", strlen(msg));
if (msgl > 0) {
rpmsglen += msgl;
}
kfree(rpmsg);
/* Formal allocation for response needed */
rpmsg = (char *) kcalloc(rpmsglen, sizeof(char), GFP_KERNEL);
/* Compose formal HTTP response */
msgl = keep_alive
? snprintf(rpmsg, rpmsglen, HTTP_RESPONSE_200_KEEPALIVE_DUMMY,
strlen(msg), msg)
: snprintf(rpmsg, rpmsglen, HTTP_RESPONSE_200_DUMMY, strlen(msg),
msg);
pr_info("HTTP response snprintf result: %d", msgl);
return rpmsg;
}
```
* 整合輸入判斷、費氏數計算與 HTTP Response 文字組合的 `http_response()` 函式之實現如下：
```cpp=122
static int http_server_response(struct http_request *request, int keep_alive)
{
char *response, *url = NULL, *ptr_n, *ptr_i, fib_s, *rpmsg = NULL;
long long fib_input;
int kres;
bignum_t *bn_res;
/* Allocate string space for url copying */
url = (char *) kcalloc(strlen(request->request_url), sizeof(char),
GFP_KERNEL);
/* Prevent allocation fail case*/
if (url == NULL) {
pr_err("Allocate url space fail!");
goto rsp; // Response allocation error directly
}
/* Copying URL */
strncpy(url, request->request_url + 1, strlen(request->request_url));
ptr_n = url;
pr_info("requested_url = %s, len = %zu\n", request->request_url,
strlen(request->request_url));
/* Seperate instruction pattern and requested number pattern */
/* Note: ptr_i for instruction pattern, ptr_n for number pattern */
ptr_i = strsep(&ptr_n, "/");
pr_info("sep / -> number: %s, instruction: %s\n", ptr_n, ptr_i);
/* Check if the instruction pattern is matched... */
if (strncmp(ptr_i, "fib", 4) == 0) {
/* Transfer input number to type long long (fit bn_fibonacci(long long))
*/
kres = kstrtoll(ptr_n, 10, &fib_input);
/* Calculate fibonacci number while return success */
if (kres == 0) {
/* CPU bound task, disable preemption for better performance */
preempt_disable();
/* Calculate fibonacci number */
bn_res = bn_fibonacci(fib_input);
/* Enable preemption */
preempt_enable();
} else {
pr_err("Input to long long fail, fail code: %d", kres);
}
} else {
pr_err("Pattern fib is NOT matched!");
}
//----------------------------------------Allo----------------------------------------
// Integrate response message to formal HTTP response!
rsp:
if (url == NULL) {
rpmsg = (char *) kcalloc(sizeof("Allocate url space fail!\n"),
sizeof(char), GFP_KERNEL);
strncat(rpmsg, "Allocate url space fail!\n",
sizeof("Allocate url space fail!\n"));
} else {
// rpmsg = (char *) kcalloc(sizeof("Calculate fibonacci number!"),
// sizeof(char), GFP_KERNEL);
// strncat(rpmsg, "Calculate fibonacci number!\n", sizeof("Calculate
// fibonacci number!\n"));
rpmsg = bn_tostring_and_free(&bn_res);
}
// pr_info("%s, %zu", rpmsg, strlen(rpmsg));
if (request->method != HTTP_GET)
response = keep_alive ? HTTP_RESPONSE_501_KEEPALIVE : HTTP_RESPONSE_501;
else {
response = respmsg_edition(rpmsg, keep_alive);
/*if (response != NULL) kfree(response);
response = keep_alive ? HTTP_RESPONSE_200_KEEPALIVE_DUMMY
: HTTP_RESPONSE_200_DUMMY;*/
}
```
:::danger
`if (strncmp(ptr_i, "fib", 3) == 0 && strlen(ptr_i) == 3) {` 這樣的敘述，會造成可能存取 `ptr_i` 開頭的記憶體空間兩次，是很沒效率的做法，請你思考改進方案。我們可做到無論如何，只要存取記憶體內容一次。
:notes: jserv
:::
>解決方案：將 `strncmp(ptr_i, "fib", 3) == 0 && strlen(ptr_i) == 3` 表達式，改以 `strncmp(ptr_i, "fib", 4) == 0 ` 實作，因 ASCII 字串編碼是以 `\0` 作為結尾，因此將 `strncmp()` 的比較字元長度改為 4 ，即可免除判斷 `ptr_i` 之長度，且因常數字串 `fib` 在記憶體實際占用的空間為 4 Byte (包含 `\0`)，因此不會有 `緩衝區溢位 (Buffer overflow)` 的問題產生，一兼兩顧。
>[name=Steven HH Chen][time=Thu, Apr 9, 2020 4:04 PM][color=Yellow]
:::warning
Good. 多想兩分鐘，你可以寫出精簡正確又安全的程式碼
:notes: jserv
:::
* 透過 wget 進行實測：
```shell
$ make request RFILE=fib/55
...
$ cat 55
139583862445
$ make request RFILE=fibo/
...
$ cat index.html
Instruction pattern is NOT matched!
$ make request RFILE=fib/xxx
...
$ cat xxx
Input to long long fail, fail code: -22
```
# :triangular_ruler: 模組改善與效能評測
## :wrench: 檢測 `khttpd` 造成系統停擺之原因
* 首先，我們觀察基於 `Dynamic Programming` 方法計算費氏數的函式 `bn_fibonacci()` 在 Runtime 的記憶體配置行為：
```cpp=38
bignum_t *bn_fibonacci(long long n)
{
/* Declare dynamic array for big number */
bignum_t **bn_fib;
bignum_t *ptr_retn;
long long i;
/* Return NULL while input is not non-negative value */
if (n == 0)
return NULL;
/* Allocate n bignum_t* pointer spaces for fibonacci number storage */
bn_fib = kcalloc(n + 1, sizeof(bignum_t *),
GFP_KERNEL); // Allocate pointer spaces...
/* Return NULL while failed allocation */
if (bn_fib == NULL)
return NULL;
/* Allocate bignum_t spaces for initial value F[0] and F[1] */
bn_fib[0] = bn_create(); // Allocate F[0]
bn_fib[1] = bn_create(); // Allocate F[1]
/* Return NULL while failed allocation*/
if (bn_fib[0] == NULL || bn_fib[1] == NULL) {
if (bn_fib[0] != NULL)
bn_free(bn_fib[0]);
if (bn_fib[1] != NULL)
bn_free(bn_fib[1]);
kfree(bn_fib);
return NULL;
}
/* Fibonacci number initial value assignment */
((bn_fib[0])->lsd)->value = 0; // F[0] = 0
((bn_fib[1])->lsd)->value = 1; // F[1] = 1
/* Calculate Fibonacci Number (Start from 2) */
for (i = 2; i <= n; i++) {
bn_fib[i] = bn_add_with_malloc(bn_fib[i - 1], bn_fib[i - 2]);
if (i == n)
ptr_retn = bn_fib[i]; // Return nth sequence
}
// free bignum storage space
for (i = n - 1;; i--) {
bn_free(bn_fib[i]);
if (i == 0)
break;
}
// free pointer to pointer space for bignum
kfree(bn_fib);
return ptr_retn;
}
```
:::danger
避免說「造成 Kernel 可用的記憶體空間枯竭」這樣不精準的話語，因為:
1. 「核心可用的記憶體空間」是對應於虛擬記憶體的配置，你不能單就 [kmalloc](https://www.kernel.org/doc/htmldocs/kernel-api/API-kmalloc.html) 失敗就說「沒有可用的記憶體空間」，相反地，你需要解讀問題的根源;
2. 需要量化分析
:notes: jserv
:::
* 在 Client 要求的費氏數在數萬項等級 (e.g. 30000) 時， `Dynamic Programming` 的方法會配置 Kernel Space 的記憶體空間，<s>造成 Kernel 可用的記憶體空間枯竭</s>，致使系統崩潰。
* 但觀察費氏數列的計算過程，F[2] 計算完成後，F[0] 項即永遠不再使用，此使我們即應釋放該空間，如此一來記憶體的耗用即可大幅減少，配置如下：
```diff
diff --git a/bignum.c b/bignum.c
index 926bdd8..992f40d 100644
--- a/bignum.c
+++ b/bignum.c
@@ -86,15 +86,13 @@ bignum_t *bn_fibonacci(long long n)
for (i = 2; i <= n; i++) {
bn_fib[i] = bn_add_with_malloc(bn_fib[i - 1], bn_fib[i - 2]);
+ bn_free(bn_fib[i - 2]);
+
if (i == n)
ptr_retn = bn_fib[i]; // Return nth sequence
}
- for (i = n - 1;; i--) {
- bn_free(bn_fib[i]);
- if (i == 0)
- break;
- }
+ bn_free(bn_fib[n - 1]);
kfree(bn_fib);
```
## :straight_ruler: `khttpd` 之效能評測機制與設計
* 首先，我們將已完成的程式碼透過 Git 操作移植至雙系統 ubuntu 上進行測試，並參考 `fibdrv` 中的[排除測試干擾因素](https://hackmd.io/@sysprog/linux2020-fibdrv#%E6%8E%92%E9%99%A4%E5%B9%B2%E6%93%BE%E6%95%88%E8%83%BD%E5%88%86%E6%9E%90%E7%9A%84%E5%9B%A0%E7%B4%A0)排除測試干擾因素。
## :hammer: 改善 `bignum` 之計算效能與比較
* 將原有的 `Dynamic Programming` 方法修改成 `Fast Doubling`。 實作敬請參閱最新的 [bignum.c](https://github.com/StevenChen8759/khttpd/blob/master/bignum.c) 與 [bignum.h](https://github.com/StevenChen8759/khttpd/blob/master/bignum.h)。
:::danger
上述的 `bignum` 仍然基於字元操作進行數值計算，仍有很大的效能改進空間。
:arrow_forward: Steven HH Chen
:::
## :wrench: 驗證回應費氏數的正確性
* 我們自 [Facebook 的討論區]()引入[費氏數驗證的 Python Script](https://gist.github.com/wilson6405/c8b86f71ce680efee26850298c9c237c)並加以修改，利用套件的網路爬蟲功能產生正確的費氏數比較檔案 `fib_crawler.txt`。
* 在此同時，我們撰寫 Shell Script 操作網路通訊套件 `wget`，並將 `khttpd` 模組回應的費氏數列數值儲存在 `fibnum.txt` 檔案內，同時利用 `diff` 加以驗證。結果如下：
```shell
$ diff -s fibnum.txt scripts/fibnum_crawler.txt
Files fibnum.txt and scripts/fibnum_crawler.txt are identical
```
> 目前共驗證 10000 項，實際查詢[提供費氏數列值的網站](http://www.protocol5.com/Fibonacci)，可發現在要求超過數百萬項的值時，該網站並無建立對應的資料，因此我們可針對要求的費氏數項次做出一些限制，儘管我們的大數計算效能能夠持續改善，但在計算時間與空間隨著要求的費氏數項次的上升而暴增時 (其增長率約為 $O(2^n)$ )，我們也必須做出一些要求輸入值上的限制，才能在 Request 處理能力上取得平衡。
> [name=Steven HH Chen][time=Sat, Apr 11, 2020 6:03 PM][color=yellow]
## :hammer: Socket 通訊處理機制之改善與探討
* 瀏覽器與 wget 之通訊行為上的不同...
## :wrench: khttpd 安全性探討與改善
# :bulb: 問題與討論
## :arrow_forward: `khttpd` 之初始化參數傳遞方法
* 參考 [`The Linux Kernel Module Programming Guide`](http://tldp.org/LDP/lkmpg/2.4/html/x354.htm) 之說明，核心模組的參數會先透過程式內部的 `MODULE_PARAM()` 宣告參數的名稱與參數型別，參考我們的 `khttpd` 實現如下：(in `main.c`)
```cpp=14
static ushort port = DEFAULT_PORT;
module_param(port, ushort, S_IRUGO);
static ushort backlog = DEFAULT_BACKLOG;
module_param(backlog, ushort, S_IRUGO);
```
* 因此，我們在載入模組時，輸入以下命令，即可決定模組所開啟的 socket port，參閱 [Makefile](https://github.com/StevenChen8759/khttpd/blob/master/Makefile) 內的 Target `load` ：
```=32
PORT := 8081
load: all
sudo insmod khttpd.ko port=$(PORT)
$(MAKE) stat
```
```make=42
stat:
@echo "------------------------------------------------------------------------"
-lsmod | grep khttpd
@echo "------------------------------------------------------------------------"
sudo netstat -antp
```
* 實際執行結果如下：
```shell
$make load PORT=2020
make -C /lib/modules/4.15.0-96-generic/build M=/home/stch/linux2020/khttpd modules
make[1]: Entering directory '/usr/src/linux-headers-4.15.0-96-generic'
Building modules, stage 2.
MODPOST 1 modules
make[1]: Leaving directory '/usr/src/linux-headers-4.15.0-96-generic'
sudo insmod khttpd.ko port=2020
make stat
make[1]: Entering directory '/home/stch/linux2020/khttpd'
------------------------------------------------------------------------
lsmod | grep khttpd
khttpd 45056 0
------------------------------------------------------------------------
sudo netstat -antp
Active Internet connections (servers and established)
Proto Recv-Q Send-Q Local Address Foreign Address State PID/Program name
tcp 0 0 0.0.0.0:2020 0.0.0.0:* LISTEN -
tcp 0 0 127.0.1.1:53 0.0.0.0:* LISTEN 1090/dnsmasq
tcp 0 0 127.0.0.1:631 0.0.0.0:* LISTEN 926/cupsd
tcp 1 0 127.0.0.1:8081 127.0.0.1:50676 CLOSE_WAIT -
tcp6 0 0 ::1:631 :::* LISTEN 926/cupsd
make[1]: Leaving directory '/home/stch/linux2020/khttpd'
```
* Ref: https://lwn.net/Articles/22197/
## :arrow_forward: `epoll()` 系統呼叫分析
*
Sign in with Wallet
Connect another wallet