Linux 核心專題: 重建 TUX 網頁伺服器

執行人: zeddyuu
專題講解錄影

提問清單

• ?

任務簡述

〈Linux 核心設計: 發展動態回顧〉提到，Linux 2.4 的時代有 kHTTPd，在 Linux 2.6 時代則有 TUX，二者都是運作於 Linux 核心內部的網頁伺服器，儘管最終都被棄置，但開發 in-kernel web server 仍是探索 Linux 核心關鍵機制的練習，因此我們有 sysprog21/khttpd。本任務回顧 Linux 2.6 時代的 TUX，理解如何設計系統呼叫，提供給應用程式的存取介面、如何客製化和設定，最後將 TUX 風格的存取機制實作於 sysprog21/khttpd 的程式碼基礎之上，並依據 ktcp 的指示，打造出高效且穩定的網頁伺服器。

參考資訊:

• TUX 2.0 Reference Manual
• Effective System Call Aggregation (ESCA): 留意 system call hook
• TUX-patches
• lwan

TODO: 改進 sysprog21/khttpd 的效率

依據 ktcp 的指示，在 sysprog21/khttpd 的基礎之上，打造出高效且穩定的網頁伺服器，需要處理 lock-free 的資源管理議題 (如 RCU)。

未改善前的效率

requests:      100000
good requests: 100000 [100%]
bad requests:  0 [0%]
socket errors: 0 [0%]
seconds:       2.028
requests/sec:  49312.072

引入 CMWQ

與 kecho 相同，首先在 http_server.h 的標頭檔中定義幾個新的結構體

struct http_service {
    bool is_stopped;
    struct list_head worker;
};

struct khttpd {
    struct socket *sock;
    struct list_head list;
    struct work_struct khttpd_work;
};

extern struct workqueue_struct *khttpd_wq;

前兩個結構體 http_service 以及 khttpd 都使用了 lab0 中練習的 Linux 風格的雙向鏈結串列，只要自定義的結構內加入 struct list_head 就可以使用多個 Linux 提供的鏈結串列操作，khttpd 這個結構內是用來存每一個 worker 的 socket 以及 work ，這裡的 work 指的是 work_struct 這個結構，而 workqueue_struct 則如其名像是一個裝 work 的 queue，核心會不斷從此移出 work 來執行。

typedef void (*work_func_t)(struct work_struct *work);

struct work_struct {
	atomic_long_t data;
	struct list_head entry;
	work_func_t func;
#ifdef CONFIG_LOCKDEP
	struct lockdep_map lockdep_map;
#endif
};

從 linux/workqueue.h 中可以找到這個結構，並且會先定義一個函式指標 work_func_t，之後在結構體內宣告此成員變數，代表此 work 所綁定的函式，之後就可以使用 INIT_WORK(_work,_func) 去對一個 work 做初始化的動作。

之後來到 http_server.c 中宣告 daemon 變數，用來判斷服務是否停止以及 worker 的鏈結串列。

struct http_service daemon = {.is_stopped = false};

宣告 create_work 以及 free_work 函式

static struct work_struct *create_work(struct socket *sk)
{
    struct khttpd *work;

    if (!(work = kmalloc(sizeof(struct work_struct), GFP_KERNEL)))
        return NULL;

    work->sock = sk;
    INIT_WORK(&work->khttpd_work, http_server_worker);
    list_add(&work->list, &daemon.worker);
    return &work->khttpd_work;
}

create_work 用來新建一個剛剛定義的 khttpd 結構並且指派成員變數，並且回傳，函式內會將參數的 socket 指派給結構內的 socket，用 INIT_WORK 初始化 work，綁定要執行的函式 http_server_worker，最後將此新建的 work 加入到服務的 worker 鍊結串列中。

其中和 work 綁定的 http_server_worker 也要更改成從 work 中取得 socket。

    struct khttpd *worker = container_of(work, struct khttpd, khttpd_work);
    struct socket *socket = worker->sock;

修改 http_server_daemon，在 server 端 accept 以後使用 create_workqueue 用得到的 socket 去建立一個新的 work，並且使用 queue_work 將 work 加入到 workqueue 中。

        work = create_work(socket);
        if (!work) {
            pr_err("create work error, connection closed\n");
            kernel_sock_shutdown(socket, SHUT_RDWR);
            sock_release(socket);
            continue;
        }
        queue_work(khttpd_wq, work);

到此已將主要服務部份的流程完成。

static void free_work(void)
{
    struct khttpd *l, *tar;
    /* cppcheck-suppress uninitvar */

    list_for_each_entry_safe (tar, l, &daemon.worker, list) {
        kernel_sock_shutdown(tar->sock, SHUT_RDWR);
        flush_work(&tar->khttpd_work);
        sock_release(tar->sock);
        kfree(tar);
    }
}

最後在服務停止時，使用 list_for_each_entry_safe 將每一個 socket 以及 work 釋放。
CMWQ 已經加入到 khttpd 中，接著測試效能是否改進。

requests:      100000
good requests: 100000 [100%]
bad requests:  0 [0%]
socket errors: 0 [0%]
seconds:       1.310
requests/sec:  76362.109

改善幅度蠻小，繼續找其他改進方向。

換一台效能較好的電腦跑了一次，throughput 從 49312 到 76362，其實提升蠻多的。

列出硬體規格，作為比較。

jserv

提供目錄檔案存取功能，提供基本的 directory listing 功能

參考教材給予的方向加入 directory listing 的功能。

在 http_request 的結構中新增成員變數 dir_context

struct http_request {
    struct socket *socket;
    enum http_method method;
    char request_url[128];
    int complete;
    struct dir_context dir_context;
    struct list_head list;
    struct work_struct khttpd_work;
};

而 dir_context 這個結構是定義在 fs.h 這個標頭檔中，使得 kernel 可以將目錄讀入 kernel space 中。

struct dir_context;
typedef int (*filldir_t)(struct dir_context *, const char *, int, loff_t, u64,
			 unsigned);

struct dir_context {
	const filldir_t actor;
	loff_t pos;
};

新增讀取目錄名稱的處理函式 handle_directory

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/zhenyu/final/khttpd/", O_RDONLY | O_DIRECTORY, 0);
    if (IS_ERR(fp)) {
        pr_info("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;
}

此函式主要執行讀取目錄名稱從第 28 行開始，在之前 fibdrv 的作業中有在 mutex 的實驗中使用到 kernel space 開檔的函式，在這邊一樣是使用 filp_open 來完成開檔，並且用 iterate_dir 去走訪指定目錄，並且在第 6 行有設定 iterator_dir.actor = tracedir，也就是實際執行過程中會去呼叫 tracedir 這個自訂的函式，其實就是 callback function 的用法，可參見 callback function。一開始很疑惑直接使用函式名稱，原來在 C 語言當中函式名稱就代表函式指標，以下為 tracedir 的實作，走訪目錄底下的資料並且執行一次就會透過 http_server_send 傳送給 client。

static int tracedir(struct dir_context *dir_context,
                    const char *name,
                    int namelen,
                    loff_t offset,
                    u64 ino,
                    unsigned int d_type)
{
    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));
    }
    return 0;
}

傳送的內容 "<tr><td><a href=\"%s\">%s</a></td></tr>\r\n" 則對應到了網頁中的 HTML 去顯示超連結

如此一來，以上程式碼可完成 directory listing 的功能

讀取檔案資料

在泛 Unix 作業系統中，檔案系統的檔案屬性由 inode 結構管理，如果要存取檔案資料就必須透過 inode，而要存取 i_node 的方式很簡單，可以直接用 file 結構指標去做存取，其中我們感興趣的是檔案的類型和大小，分別是 inode 成員中的 i_mode 以及 i_size。

判斷檔案的類型可以使用巨集來完成，定義在 include/uapi/linux/stat.h 當中

#define S_ISLNK(m)	(((m) & S_IFMT) == S_IFLNK)
#define S_ISREG(m)	(((m) & S_IFMT) == S_IFREG)
#define S_ISDIR(m)	(((m) & S_IFMT) == S_IFDIR)
#define S_ISCHR(m)	(((m) & S_IFMT) == S_IFCHR)
#define S_ISBLK(m)	(((m) & S_IFMT) == S_IFBLK)
#define S_ISFIFO(m)	(((m) & S_IFMT) == S_IFIFO)
#define S_ISSOCK(m)	(((m) & S_IFMT) == S_IFSOCK)

其中 S_ISDIR 和 S_ISREG 為判斷是否為目錄以及檔案。

修改 http_server.c 中的 handle_directory

若判斷為目錄，就將整個目錄中的所有檔案名稱傳送給 client
若判斷為檔案，則直接讀取檔案資料送給 client

    if (S_ISDIR(fp->f_inode->i_mode)) {
        SEND_HTTP_MSG(request->socket, buf, "%s%s%s", "HTTP/1.1 200 OK\r\n",
                      "Content-Type: text/html\r\n",
                      "Transfer-Encoding: chunked\r\n\r\n");
        SEND_HTTP_MSG(
            request->socket, buf, "7B\r\n%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");

        iterate_dir(fp, &request->dir_context);


        SEND_HTTP_MSG(request->socket, buf, "%s",
                      "16\r\n</table></body></html>\r\n");
        SEND_HTTP_MSG(request->socket, buf, "%s", "0\r\n\r\n");

    } else if (S_ISREG(fp->f_inode->i_mode)) {
        char *read_data = kmalloc(fp->f_inode->i_size, GFP_KERNEL);
        int ret = read_file(fp, read_data);

        SEND_HTTP_MSG(
            request->socket, buf, "%s%s%s%s%d%s", "HTTP/1.1 200 OK\r\n",
            "Content-Type: ", get_mime_str(request->request_url),
            "\r\nContent-Length: ", ret, "\r\nConnection: Close\r\n\r\n");
        http_server_send(request->socket, read_data, ret);
        kfree(read_data);
    }

其中 SEND_HTTP_MSG 是將取代了原本程式碼中很多重複的 snprintf 以及http_server_send，用巨集的方式更精簡化，省略重複的程式碼

#define SEND_HTTP_MSG(socket, buf, format, ...)           \
    snprintf(buf, SEND_BUFFER_SIZE, format, __VA_ARGS__); \
    http_server_send(socket, buf, strlen(buf))

到此可以正確顯示出檔案資料以及資料夾

TODO: 研讀 TUX 2.0 Reference Manual 並總結存取介面

回顧 Linux 2.6 時代的 TUX，理解如何設計系統呼叫，提供給應用程式的存取介面、如何客製化和設定。本任務著重 HTTP (若有 HTTPS 更好)，過程中應當閱讀 Effective System Call Aggregation (ESCA)，以得知 system call hook 的處理方式。

TUX 簡介

TUX 是個以 GPL 授權條款發布、運作於 Linux 核心模式的網頁伺服器，其特色是可達到典型執行於使用者模式的網頁伺服器所無法達到的功能，但也意味著 TUX 無法提供動態的網頁服務，目前專案的狀態是被棄置不再維護，原因是因為現代的 kernels 以及 web server 都可以提供等同於 TUX 的效能優勢，而沒有 in-kernel 的缺點，例如 Nginx。

TUX 目前只能提供靜態的網頁服務(沒有後端的網頁服務，不會跟後端資料庫進行互動)，和 kernel-space modules、user-space modules 以及提供動態網頁內容的 user-space web server 後台進行協調合作，且一般的 user-space web server 不需要為了 TUX 去做任何改變，然而 user-space 的程式碼必須使用基於 tux(2) 系統呼叫的 interface。

提供給 user-space 應用程式的存取介面

tux (unsigned int action, user_req_t *req) 這個系統呼叫用於幫助目前執行的 user-space TUX module 呼叫 kernel 執行相對應的 action，而 action 可以使用第一個參數來表示，第二個參數 req 則是表示 TUX subsystem 回應的使用者請求，是一個結構體的指標並含有使用者 HTTP 請求的資訊，像是一些 GET、POST 等等，隨著 TUX 版本不同結構體的成員變數都會有所不同。

幾個常用的 action 有 TUX_ACTION_STARTUP 代表啟動 tux subsystem、TUX_ACTION_SHUTDOWN 代表停止 tux subsystem 等等，還有一些常見的請求可以透過 action 參數來表示，用來回應 TUX events，像是 TUX_ACTION_EVENTLOOP 會 invoke TUX event loop，TUX subsystem 會回傳一個新的 request 或是等待新的 request 到達，TUX_ACTION_SEND_OBJECT 會傳送目前的 URL 物件給 client、TUX_ACTION_GET_OBJECT 代表發出一個 request 給名子存在 req->objectname 的物件，若此物件目前無法馬上取用，目前的 request 會被暫停，還有許多 action 在此就不多提。

第二個參數 user_req_t req 是代表 TUX subsystem 回應給 client 的請求，成員變數會隨著版本不同而有所不同，這裡拿第二版當範例。

typedef struct user_req_s {
        int version_major;
        int version_minor;
        int version_patch;

       int http_version;
        int http_method;

       int sock;
        int event;
        int thread_nr;
        void *id;
        void *priv;

       int http_status;
        int bytes_sent;
        char *object_addr;
        int module_index;
        char modulename[MAX_MODULENAME_LEN];

       unsigned int client_host;
        unsigned int objectlen;
        char query[MAX_URI_LEN];
        char objectname[MAX_URI_LEN];

       unsigned int cookies_len;
        char cookies[MAX_COOKIE_LEN];

       char content_type[MAX_FIELD_LEN];
        char user_agent[MAX_FIELD_LEN];
        char accept[MAX_FIELD_LEN];
        char accept_charset[MAX_FIELD_LEN];
        char accept_encoding[MAX_FIELD_LEN];
        char accept_language[MAX_FIELD_LEN];
        char cache_control[MAX_FIELD_LEN];
        char if_modified_since[MAX_FIELD_LEN];
        char negotiate[MAX_FIELD_LEN];
        char pragma[MAX_FIELD_LEN];
        char referer[MAX_FIELD_LEN];

       char *post_data;
        char new_date[DATE_LEN];
        int keep_alive;
} user_req_t;

雖然不同版本會有不同的成員變數，但主要一定會出現比較重要的像是 http_version 代表 HTTP 的版本，可以是 HTTP_1_0 或是 HTTP_1_1，還有像是 http_method 代表 HTTP 方法，可以是 METHOD_GET 或是 METHOD_POST 等等，這些都是在 HTTP 中常見的請求。

tux() 這個系統呼叫會回傳以下的值。

enum tux_reactions {
        TUX_RETURN_USERSPACE_REQUEST = 0,
        TUX_RETURN_EXIT = 1,
        TUX_RETURN_SIGNAL = 2,
};

TUX_RETURN_USERSPACE_REQUEST 代表 kernel 放了新的 request 在 req 中，也代表　request 一定是 TUX_ACTION_GET_OBJECT、TUX_ACTION_SEND_OBJECT、TUX_ACTION_READ_OBJECT、TUX_ACTION_FINISH_REQ 其中一個。

TUX_RETURN_EXIT 代表 TUX 已經停止運作。

TUX_RETURN_SIGNAL 代表 signal 發生，沒有新的 request 被安排。

TUX 2.0 特色

TUX 2.0 是 TUX 1.0 的升級版，並與 user-space module 保持 source-code level 的相容性。
主要新增和增強的部分為

• Zero-copy 硬碟讀取
  • TUX 1.0 會將檔案複製到一個暫存的緩衝區，而 TUX 2.0 整合了 page cache，因此使用了 zero-copy block I/O。
• Zero-copy 網路寫入
  • TUX 2.0 使用通用 zero-copy TCP 框架。
• Zero-copy parsing
  • 當可能的時候，TUX 可以直接 parse 輸入的封包，就算在記憶體受限的狀態下，TUX 也可以執行完整、back-to-back 的 zero-copy I/O。

Effective System Call Aggregation (ESCA) 閱讀

Effective System Call Aggregation (ESCA) 是用來減少整體系統呼叫的執行成本，為此 ESCA 運用 system call batching 的手法。

System call batching 意即將系統呼叫批次化執行，一段 code 被 batch_start() 以及 batch_stop() 包住稱之為 batching segment，在一個應用中此 segment 可以出現多次，跟一般的系統呼叫相比，ESCA 可以消除 kernel mode 和 user mode 之間的切換，在 segment 中的 system call 會去紀錄他們的系統呼叫 ID 以及參數到一個 shared table 中，而不是一觸發系統呼叫就切換 mode 去執行相對應的 service routine，當 batch_flush() 被呼叫時就會切換到 kernel mode 執行全部 batch 的系統呼叫，再切換回 user mode，這可以省去 mode 切換的時間，提升效率，是一個簡單且有效的方法。

System call hooking 簡單來說就是用自己寫的程式碼取代 system call table entry，要達到上述的效果就需要 system call hooking。

有兩個 system call 是 ESCA 必須攔截改寫的

• sys_batch : 走訪所有 shared table 並且執行所有紀錄的 system call，並且切回 user mode。
• sys_register : 將 user space 的 shared table 映射到 kernel space memory 並且初始化。

直接來看 esca.c 程式碼中一些重要的部分。

static int __init mod_init(void)
{
    int rc;
    scTab = (void **) (smSCTab + ((char *) &system_wq - smSysWQ));
    allow_writes();

    /* backup */
    sys_oldcall0 = scTab[__NR_batch_flush];
    sys_oldcall1 = scTab[__NR_register];

    /* hooking */
    scTab[__NR_batch_flush] = sys_batch;
    scTab[__NR_register] = sys_register;

    disallow_writes();

    pr_info("installed as %d\n", __NR_batch_flush);
    return 0;
}

此段程式碼流程即為先找出 system call table，但因為 system call table 的內容是唯讀不能進行寫入，所以要修改 CR0 這個暫存器就可以進行寫入，CR0 暫存器有 32 個 bit，有多個 control flag，其中第 16 個位元代表 Write protection，當它是 set 時(為1的時候) 代表無法對 read-only 的 page 進行寫入，所以只要把它 clear 成 0 就可以進行寫入。

接著將 system call table entry 進行備份後替換成自己寫的，恢復 Write protection，即完成 system call hooking。

其中注意到替換的 function 宣告時有我不知道的修飾字 asmlinkage，代表 system call routine 要透過 stack 來取得 system call handler 傳遞的參數，而不是透過暫存器。

TODO: 將 TUX 風格的存取方式引入 sysprog21/khttpd

可指定網頁伺服器的 webroot、調整核心執行緒組態、MIME type 等等，並確保在 sysprog21/khttpd 實作。過程中應當確保兼顧效率和讓應用程式指定網頁伺服器的組態。

指定網頁伺服器的 webroot

實作 directory listing 功能可以顯示 handle_directory 中第 28 行透過 filp_open 函式開啟的目錄，但參數給定的 webroot 路徑是固定的，每次更換 webroot 都需要去改動程式碼，所以透過參數指定 webroot 啟動 webserver 是 TUX 的方式，(雖然我沒有找到 TUX 相關的程式碼，但看文件所表示應該是如此)。

在 http_server.h 中的 http_service 結構體去新增 dir_path 字串變數，並且新增一個 extern 變數 daemon_list 給所有程式碼共用。

struct http_service {
    bool is_stopped;
    char *dir_path;
    struct list_head worker;
};

extern struct http_service daemon_list;

並且在 main.c 中新增模組參數 WEBROOT，之後可以在命令列給予目錄路徑給此字元陣列

#define DOCPATH_SIZE 100
static char WEBROOT[DOCPATH_SIZE] = {0};
module_param_string(WEBROOT, WEBROOT, DOCPATH_SIZE, 0);

接著修改 khttpd_init，將得到的參數 WEBROOT 指定給 daemon_list 中的 dir_path

if (!*WEBROOT)
    WEBROOT[0] = '/';
daemon_list.dir_path = WEBROOT;

最後在 http_server.c 中修改 filp_open 的第一個參數，開啟指定目錄，即可完成

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

以下展示 sudo insmod khttpd.ko，得到的是/的目錄

以下展示 sudo insmod khttpd.ko WEBROOT='"/home/zhenyu/final/khttpd/"，得到的是 work directory 的目錄

MIME type

MIME 是一個網際網路標準，始其能夠支援非文字多媒體檔案，像是音效或圖片。
只要在網頁伺服器回應的 HTTP header 中的 Content-type 提供類型就可以使用，一般以以下形式呈現。

Content-Type: [type]/[subtype]; parameter

不同的副檔名有不同要回應的 type，像是 .img 要回應 image 等等，故只要修改程式碼去找到對應的副檔名要回應怎樣的 type 即可，這裡我的想法是使用 hashtable 實作，但 linux kernel 中的 hashtable 似乎不支援以整數以外的型態做為 key，故先使用陣列版本。

新增標頭檔 mime_type.h，使用結構陣列當成 key-value 對應，並且宣告 get_mime_type 去得到當前 request 的副檔名所對應到的 MIME type。

#ifndef _MIME_TYPE_H_
#define _MIME_TYPE_H_

typedef struct {
    const char *type;
    const char *string;
} mime_map;

mime_map mime_types[] = {
    {".aac", "audio/aac"},
    {".abw", "application/x-abiword"},
    ...
    {".7z", "application/x-7z-compressed"},
    {NULL, NULL},
};

// return mime type string
const char *get_mime_str(char *request_url)
{
    char *request_type = strchr(request_url, '.');
    int index = 0;
    if (!request_type)
        return "text/plain";

    while (mime_types[index].type) {
        if (!strcmp(mime_types[index].type, request_type))
            return mime_types[index].string;
        index++;
    }
    return "text/plain";
}

#endif

但每次都需要逐一比對副檔名取出 MIME type，時間複雜度為

$O(n)$ ，故可以考慮使用 hash table 加快搜尋的時間，但目前找到的資訊是 linux kernel 的 hash table 只支援整數的 key，還在尋找有沒有其他方法。

此陳述不正確，Linux 核心的 hash table 可用於多種型態，請對照 Linux 核心原始程式碼。

jserv

收到，我是看這篇討論 How to use the kernel hashtable API? 的，好像要使用到 xxhash，晚點研究看看。

接著在 Content-type 項中使用取出的 MIME type，即可完成

可以看到能正常顯示出除文字以外的類型，Content-type 也是使用 image/jpeg

調整核心執行緒組態