# 2020q1 Homework4 (khttpd)
contributed by < `colinyoyo26` >
> [H08: khttpd](https://hackmd.io/@sysprog/linux2020-khttpd)
## HTTP (Hypertext Transfer Protocol) transaction
### 1. Connect
Client open connection to server
### 2. Request
Client request information from server
- Consist of one ==request line== and some ==request header==
- The form of request line is `method URI version`
> HTTP support lots of methods, e.g. POST, GET, OPTIONS...
- Each line ends with `\r\n`
- e.g.
```
GET / HTTP/1.1
Host: localhost:1999
User-Agent: Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:74.0) Gecko/20100101 Firefox/74.0
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,*/*;q=0.8
Accept-Language: en-US,en;q=0.5
Accept-Encoding: gzip, deflate
Connection: keep-alive
Upgrade-Insecure-Requests: 1
Cache-Control: max-age=0
```
### 3. Response
Server response to client
- Consist of one ==response line==, some ==response header== and follow by a ==blank line== and a ==response body==
- The form of response line is `version status-code status-message`
- e.g.
```
HTTP/1.1 200 OK
Server: khttpd
Content-Type: text/plain
Content-Length: 12
Connection: Keep-Alive
Hello World!
```
### 4. Close
Close the transaction
## HTTP Parser
The [parser](https://raw.githubusercontent.com/nodejs/http-parser/master/http_parser.c), which implement in `http_parser.c`, behave like a [mealy machine](https://en.wikipedia.org/wiki/Mealy_machine)
and parse the client request character by character.
(not complete)
## Integrate fib into khttpd
Rewrite the macro to process different request
- Use `snprintf` to deal with formatting string
- Separate response body from response line and response header
```cpp
#define HTTP_RESPONSE_200_KEEPALIVE \
"" \
"HTTP/1.1 200 OK" CRLF "Server: " KBUILD_MODNAME CRLF \
"Content-Type: text/plain" CRLF "Content-Length: %lu" CRLF \
"Connection: Keep-Alive" CRLF CRLF
```
Wget [bigmun.h](https://raw.githubusercontent.com/colinyoyo26/fibdrv/master/bignum.h) from my github and use it to implement `fib_sequence` in [fib.c](https://github.com/colinyoyo26/khttpd/blob/master/fib.c)
> Trying to improve the performance. Detail in [2020q1 Homework2 (fibdrv)](https://hackmd.io/YaY5iYlOSfOeM-ROG5OYIg#%E6%8E%A2%E8%A8%8E-bignum-%E5%AF%A6%E4%BD%9C%E6%95%88%E8%83%BD%E5%B7%AE%E7%95%B0)
```
bignum.h:
wget -q https://raw.githubusercontent.com/colinyoyo26/fibdrv/master/bignum.h
```
Modify the following function to check the format of URI and give corresponding response
- If not in the format `/fib/N`, response `Hello World!`
- If `N` is not a integer, response `Not Implemented` with status-code 501
- Otherwise, response Nth fibonacci number (in hex)
> the URL in following function is URI precisely, which is the suffix of URL
```diff
static int http_server_response(struct http_request *request, int keep_alive)
{
- char *response;
+ char *response, *be_free = NULL;
+ char buf[128];
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;
+ else {
+ char *url = request->request_url;
+ if (!strncmp(url, "/fib/", 5)) {
+ long long k;
+ if (kstrtoll(url + 5, 10, &k)) {
+ response = keep_alive ? HTTP_RESPONSE_501_KEEPALIVE
+ : HTTP_RESPONSE_501;
+ goto out;
+ }
+ response = fib_sequence(k);
+ if (keep_alive)
+ snprintf(buf, 128, HTTP_RESPONSE_200_KEEPALIVE,
+ strlen(response));
+ else
+ snprintf(buf, 128, HTTP_RESPONSE_200, strlen(response));
+ int buf_len = strlen(buf);
+ strncat(response, CRLF, strlen(CRLF));
+ memmove(response + buf_len, response, strlen(response));
+ memcpy(response, buf, buf_len);
+ be_free = response;
+ } else {
+ if (keep_alive)
+ snprintf(buf, 128, HTTP_RESPONSE_200_KEEPALIVE HELLOW, 12lu);
+ else
+ snprintf(buf, 128, HTTP_RESPONSE_200 HELLOW, 12lu);
+ response = buf;
+ }
+ }
+out:
http_server_send(request->socket, response, strlen(response));
+ kfree(be_free);
return 0;
}
```
## Verified script
Modify the python script from [kickasson](https://gist.github.com/wilson6405/c8b86f71ce680efee26850298c9c237c?fbclid=IwAR1M1X8w87FljubK96u4kQJGQ2GJF3QRaaW3pEa5zhw42e7lm7UTTzoil2E) and add `verify` target in Makefile
- The script fetch the correct result and my result from this [website](http://www.protocol5.com/Fibonacci) and `localhost:$(PORT)` repectively to tell if my result is correct
> [c4b9dfe](https://github.com/colinyoyo26/khttpd/commit/c4b9dfe22c65fe82acd4bb305c176ee674859a3b)
```cmake
verify: all
$(MAKE) unload
$(MAKE) load
@python3 scripts/verify.py $(PORT) 1 -b base16
@python3 scripts/verify.py $(PORT) 100 -b base16
@python3 scripts/verify.py $(PORT) 1000 -b base16
@python3 scripts/verify.py $(PORT) 10000 -b base16
@python3 scripts/verify.py $(PORT) 100000 -b base16
@python3 scripts/verify.py $(PORT) 1000000 -b base16
$(MAKE) unload
```
Reference result
```shell
$ make verify
Calculate 1th fib number takes 0.0047147274017333984 seconds
Pass
Calculate 100th fib number takes 0.003022432327270508 seconds
Pass
Calculate 1000th fib number takes 0.002961874008178711 seconds
Pass
Calculate 10000th fib number takes 0.0054323673248291016 seconds
Pass
Calculate 100000th fib number takes 0.20912790298461914 seconds
Pass
Calculate 1000000th fib number takes 19.9953453540802 seconds
Pass
```
:::warning
Sometime my computer crash when calculating 1000000th fib number.
The problem is in [bignum.h](https://github.com/colinyoyo26/fibdrv/blob/master/bignum.h), I will fix it.
:::
## CMWQ
> Reference from [Concurrency Managed Workqueue](https://www.kernel.org/doc/html/v4.15/core-api/workqueue.html)
### Workqueue (wq) API
Which is the most commonly used mechanism for asynchronous process execution context.
### Original wq implementation
> before linux kernel 2.6.36
MT wq had one worker thread per CPU, ST wq had one worker thread system-wide.
> MT wq need to keep the same number of worker threads as #CPU cores
- Wasted a lot of resource.
An MT wq could provide only one execution context per CPU core.
- proneness to deadlock
Corresponding APIs
- `create_workqueue()`
- `create_singlethread_workqueue()`
> deprecated to use
### CMWQ is reimplementation of wq
Which has following feature
- Maintain compatibility with the original wq API.
- Separate worker pool with wq.
- Use per-CPU unified worker pools shared by all wq.
- Automatically regulate worker pool and level of concurrency.
> user face the wq but don't don't need to worry about woker pool and level of concurrency
Corresponding API
- `alloc_workqueue()`
### Work
A work item is a simple struct that holds a pointer to the function that is to be executed asynchronously.
### Worker thread
The thread execute the functions off of the wq.
### Worker pool
Manage worker threads.
There are two major worker-pools
- one for normal work items
- the other for high priority ones
- some extra worker-pools to serve work items queued on unbound workqueues
> a work item of a bound workqueue will be queued on the worklist of either normal or high priority worker pool that is associated to ==the CPU the issuer is running on==.
e.g.
- `[kworker/u9:2-rb]` means
- unbound pool id = 9 (`u` imply unbound pool)
- 2th worker in this worker pool
- `[kworker/0:0-eve]` means
- this worker pool is on CPU 0
- 0th worker in this worker pool
- `[kworker/2:0H-kb]` means
- this worker pool is on CPU 2 (`H` imply high priority worker pool)
- 0th worker in this worker pool
```
$ ps aux | grep kworker
root 451 0.0 0.0 0 0 ? I< 四 06 0:00 [kworker/u9:2-rb]
root 6156 0.0 0.0 0 0 ? I 01:15 0:00 [kworker/0:0-eve]
root 7548 0.0 0.0 0 0 ? I< 01:21 0:00 [kworker/2:0H-kb]
```
:::info
Still don't know what the suffix `rb` `eve` `kb` means
:::
## Rewrite kHTTPd with CMWQ
> [639e247](https://github.com/colinyoyo26/khttpd/commit/639e24745b11e91c468d55884d2253bc343f2785)
Implement CMWQ in branch [cmwq](https://github.com/colinyoyo26/khttpd/tree/cmwq).
The members of following structure
- `sock` is the arument for the function to be execute.
- `list` is used to link the sturcture together, so we can release all the`sock`and `khttp_work` after the daemon stop.
- `khttpd_work` please see the description of Work above.
```cpp
struct khttp_worker {
struct socket *sock;
struct list_head list;
struct work_struct khttp_work;
};
```
### Program flow of daemon
#### kthread_should_stop
Check if the kernel thread, which execute the daemon, should stop.
#### create_work
Allocate a space for `struct khttp_worker`, initilize it, and return `&worker->khttp_work`.
Use `container_of` macro to get `struct khttp_worker` when we need it.
```cpp
static struct work_struct *create_work(struct socket *sock)
{
struct khttp_worker *worker;
if (!(worker = kmalloc(sizeof(struct khttp_worker), GFP_KERNEL)))
return NULL;
worker->sock = sock;
INIT_WORK(&worker->khttp_work, http_server_worker);
list_add(&worker->list, &daemon.worker);
return &worker->khttp_work;
}
```
#### queue_work
Queue work on a workqueue, which had been create when `ismod`.
```cpp
khttp_wq = alloc_workqueue(KBUILD_MODNAME, 0, 0);
```
> but I use `system_wq` instead of a dedicated workqueue now. [d6751e0](https://github.com/colinyoyo26/khttpd/commit/d6751e02e77efdbcda2df42b24551f1eef8f7a24)
```cpp
queue_work(khttp_wq, work);
```
#### exit
Set `daemon.is_stopped` to be `true` to notify all the work.
Call `free_work` to release the resources.
```cpp
static void free_work(void)
{
struct khttp_worker *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->khttp_work);
sock_release(tar->sock);
kfree(tar);
}
}
```
> ##### bool flush_work(struct work_struct * work)
>- wait for a `work` to finish executing the last queueing instance
```mermaid
graph TB
init
stop{kthread_should_stop}
accept[kernel_accept]
create_work[create_work]
queue_work[queue_work]
exit
init --> stop
stop -- true --> exit
stop -- false --> accept
accept --> create_work
create_work --> queue_work
queue_work --> stop
```
### Performance
Use `htstress` to quantify the performance of each method.
- paramater `./htstress -n 100000 -c 1 -t 4 http://localhost:8081/`
- `-c`, number of concurrent connections ==per user thread==
- `-t`, number of threads (set this to the number of "
"CPU cores)
`CMWQ` method cost less than half of the time naive method used.
- Naive
> Call kthread_run to create a kernel thread for every connection
```
requests: 100000
good requests: 100000 [100%]
bad requests: 0 [0%]
socker errors: 1 [0%]
seconds: 6.313
requests/sec: 15839.323
```
- CMWQ
```
requests: 100000
good requests: 100000 [100%]
bad requests: 0 [0%]
socker errors: 0 [0%]
seconds: 3.060
requests/sec: 32675.531
```
## Release the work resource dynamically
The problem in [639e247](https://github.com/colinyoyo26/khttpd/commit/639e24745b11e91c468d55884d2253bc343f2785) is that we release the resource only when daemon stop, so I fix the problem in [0eb2268](https://github.com/colinyoyo26/khttpd/commit/0eb226878e24dd533c9cbcf205ecd120d69fa6d2)
What I do is release the resource when a work leave.
```cpp
static void free_work(struct khttp_worker *worker)
{
kernel_sock_shutdown(worker->sock, SHUT_RDWR);
sock_release(worker->sock);
spin_lock(&daemon.lock);
list_del(&worker->list);
spin_unlock(&daemon.lock);
kfree(worker);
}
```
```diff
static void http_server_worker(struct work_struct *work)
{
...
- kernel_sock_shutdown(socket, SHUT_RDWR);
+ free_work(worker);
}
```
Flush the workqueue when daemon stop
> I'd already rename the fuction to `flush_wq` in new commit. [7bf242e](https://github.com/colinyoyo26/khttpd/commit/7bf242eb14e679e1aa018af59ee39ecb395362b8)
- `kernel_sock_shutdown` can force the work not be blocked in `kernel_recvmsg`
```diff
static void flush_works(void)
{
- struct khttp_worker *l, *tar;
+ struct khttp_worker *l = NULL, *tar = NULL;
list_for_each_entry_safe (tar, l, &daemon.worker, list) {
kernel_sock_shutdown(tar->sock, SHUT_RDWR);
flush_work(&tar->khttp_work);
- sock_release(tar->sock);
- kfree(tar);
}
}
```
```diff
int http_server_daemon(void *arg)
{
...
- free_work();
+ flush_works();
return 0;
}
```
## `epoll`
I compare three APIs `epoll`, `poll`, `select`
- They all belong to ==I/O multiplexing==
- `select()` can monitor only file descriptors numbers that are less than `FD_SETSIZE`
- `poll` and `select` are level-triggered, while `epoll` supports both level-triggered and edge-triggered
- when used as a level-triggered interface (the default,
when `EPOLLET` is not specified), ==`epoll` is simply a faster `poll`==
> We use level-triggered in `htstress.c`
- Time comlexity of `poll` and `select` are $O(n)$, while `epoll` is $O(1)$
## Reference
- [Linux 核心設計: 不僅是個執行單元的 Process](https://hackmd.io/@sysprog/linux-process)
- [CS:APP 第 11 章](https://hackmd.io/@sysprog/CSAPP-ch11?type=view)
Sign in with Wallet
Connect another wallet