# 2021q1 Homework1 (lab0)
contributed by < `grb72t3yde` >
###### tags: `sysprog2020`
---
# :penguin: 作業要求
> [lab0 題目連結](https://hackmd.io/@sysprog/linux2021-homework1)
* [x] 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
* [x] 參閱 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/git-with-github) ^附教學影片^
* [x] ==詳細閱讀 [C Programming Lab](https://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/labs/cprogramminglab.pdf)== ，依據指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 `q_sort` 函式。
* [x] 在提交程式變更前，務必詳閱 [如何寫好 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)
* [ ] 在 tiny-web-server 上實作 coroutine，並整合進 qtest
## 實驗環境
* Ubuntu 20.04 LTS
* Linux 核心版本 : 5.4.0-58-generic
## queue.[ch] 之實作日誌
### queue.h
* 於定義的結構`queue_t`中加入下列屬性, 其用以實現具有O(1)時間複雜度的`q_size()`和`q_insert_tail()`函式
```cpp
typedef struct {
...
list_ele_t *tail;
int size;
...
} queue_t;
```
### queue.c
* `queue_t *q_new()`
* **功能 : 建立一條新的 queue 且進行內部結構的初始化, 並回傳其指標**
* 根據註解提示, 我先檢查 `malloc()` 的回傳值確認是否成功, 否則回傳 NULL
* 做初始化時, 除了 head 與 tail 指標指向 NULL, 新加的 size 也要 assigned 0
* `void q_free(queue_t *q)`
* **功能 : 刪除一條 queue 並釋放其所有使用的記憶體空間**
* 使用 while loop 逐一將 list node 使用 free() 釋放
* 其中用以儲存 value 所額外 malloc 的空間也要記得釋放
* `bool q_insert_head(queue_t *q, char *s)`
* **功能: 從 list 頭部插入新的 list node, 並將參數 s 所指向的資料複製入此 list node 的 value, 最後回傳 true/false 以告知是否成功**
* 此 function 我呼叫了兩次 malloc(), 分別為了 list node 的空間以及 value 的空間; 因此, 需注意第二次的 malloc()若 return error 時, 需將第一次成功分配的空間釋放
* 使用 strlen()取得 s 之長度時, 不包括其原本 string terminator (i.e. '\0') 的長度, 因此替 list node 分配存儲字串的空間時需要+1
* `bool q_insert_tail(queue_t *q, char *s)`
* **功能: 從 list 尾部插入新的 list node, 並將參數 s 所指向的資料複製入此 list node 的 value, 最後回傳 true/false 以告知是否成功**
* 注意事項與 q_insert_head 十分類似
* `bool q_remove_head(queue_t *q, char *sp, size_t bufsize)`
* **功能: 從 list 頭部移除一個 list node, 並將 node 內的資料複製入指定位址sp, 最後回傳true/false以告知是否成功; 同時, 我們只允許bufsize(含'\0')長度的資料被存入sp**
* 要看清題目所述, bufsize-1 是不含 terminator 的, 因此做 clear 和 copy 時需注意長度
* 需要注意 NULL 檢查的順序, 若考慮以下順序, 會造成的不合法的 dereference 存取
```cpp
if (!q->head || !q) {
...
}
```
* `int q_size(queue_t q)`
* **功能: 回傳 queue q 內的元素個數, 若 q==NULL 則也回傳0**
* 因為有了 size 屬性, 我們直接回傳即可達到 O(1) 的複雜度
* `void q_reverse(queue_t *q)`
* **功能: 將 queue q 的元素順序倒轉**
* 使用常見的三個指標之方法非遞迴方法
```cpp
void q_reverse(queue_t *q)
{
if (!q || !q->head) {
return;
}
if (q->size == 1) {
return;
}
list_ele_t *prev, *cur, *foward;
prev = q->head;
cur = prev->next;
foward = cur->next;
while (foward) {
cur->next = prev;
prev = cur;
cur = foward;
foward = foward->next;
}
cur->next = prev;
q->tail = q->head;
q->head->next = NULL;
q->head = cur;
}
```
* `void q_sort(queue_t *q)`
* 參考 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 提供之 merge sort 手法
* 參考 [Merge two sorted linked list](https://www.geeksforgeeks.org/merge-two-sorted-linked-lists/) 後採用其 `Using Local References method`
* 參考 [你所不知道的 C 語言：函式呼叫篇](https://hackmd.io/@sysprog/c-function), 將所有用以操作 `free()` 且不再使用的指標在呼叫 `free()` 後指向 `NULL`
## 其他實驗以及分析
### 在 `qtest` 實作 coroutine，嘗試整合 tiny web server 進 qtest
* [tiny-web-server](https://github.com/7890/tiny-web-server) 為一個 concurrent echo server based on processes 的實作 (==可搭配 CS:APP 第十二章節閱讀==)。其可於一個目錄下服務，接收來自多個 clients 的檔案請求 (長度，格式，內容)。
* 程式碼追蹤
1. 進入 main function 後，先進行 arguments 的拆解
```cpp
int main(int argc, char** argv) {
if(argc > 1 && (!strcmp(argv[1], "-h") || !strcmp(argv[1], "--help")))
{
print_help();
return 0;
}
struct sockaddr_in clientaddr;
int default_port = DEFAULT_PORT,
listenfd,
connfd;
char buf[256];
char *path = getcwd(buf, 256);
socklen_t clientlen = sizeof clientaddr;
if(argc == 2) { // port number is argv1
if(argv[1][0] >= '0' && argv[1][0] <= '9') {
default_port = atoi(argv[1]);
} else {
path = argv[1];
if(chdir(path) != 0) {
perror(path);
exit(1);
}
}
} else if (argc == 3) { // port number is argv2
default_port = atoi(argv[2]);
path = argv[1];
if(chdir(path) != 0) {
perror(path);
exit(1);
}
}
...
```
2. 接著呼叫 `open_listenfd`，包含 server 端創建 socket descripter，bind，listen 等呼叫。bind 請求 kernel 將 listenfd 和 serveraddr 連結; listen 則將 listenfd 從 active socket 轉換成 listen socket ，一個可從 client 接收請求狀態。
```cpp
int open_listenfd(int port) {
int listenfd, optval=1;
struct sockaddr_in serveraddr;
/* Create a socket descriptor */
if ((listenfd = socket(AF_INET, SOCK_STREAM, 0)) < 0) {
return -1;
}
/* Eliminates "Address already in use" error from bind. */
if (setsockopt(listenfd, SOL_SOCKET, SO_REUSEADDR,
(const void *)&optval , sizeof(int)) < 0) {
return -1;
}
// 6 is TCP's protocol number
// enable this, much faster : 4000 req/s -> 17000 req/s
if (setsockopt(listenfd, 6, TCP_CORK,
(const void *)&optval , sizeof(int)) < 0) {
return -1;
}
/* Listenfd will be an endpoint for all requests to port
on any IP address for this host */
memset(&serveraddr, 0, sizeof(serveraddr));
serveraddr.sin_family = AF_INET;
serveraddr.sin_addr.s_addr = htonl(INADDR_ANY);
serveraddr.sin_port = htons((unsigned short)port);
if (bind(listenfd, (SA *)&serveraddr, sizeof(serveraddr)) < 0) {
return -1;
}
/* Make it a listening socket ready to accept connection requests */
if (listen(listenfd, LISTENQ) < 0) {
return -1;
}
return listenfd;
}
```
3. 以下為一個 concurrent server 的實作。需要注意到 listening 以及 connecting descirpter 的不同，有助於理解以下使用 fork 的實作 concurrent server 技巧。(請參考 CS:APP p.973)
```cpp
...
int i=0;
for(; i < FORK_COUNT; i++) {
int pid = fork();
if (pid == 0) { // child
while(1) {
connfd = accept(listenfd, (SA *)&clientaddr, &clientlen);
process(connfd, &clientaddr);
close(connfd);
}
} else if (pid > 0) { // parent
printf("child pid is %d\n", pid);
} else {
perror("fork");
}
}
...
```
4. `process` 等待一個並隨後拆解 request 的檔案名稱並使用 `rio_readlineb` 讀取檔案。
```diff
void process(int fd, struct sockaddr_in *clientaddr) {
#ifdef LOG_ACCESS
printf("accept request, fd is %d, pid is %d\n", fd, getpid());
#endif
http_request req;
parse_request(fd, &req);
struct stat sbuf;
int status = 200, ffd = open(req.filename, O_RDONLY, 0);
if(ffd <= 0) {
status = 404;
char *msg = "File not found";
- client_error(fd, status, "Not found", msg);
+ client_error(fd, status, "Not found\n", msg);
} else {
fstat(ffd, &sbuf);
if(S_ISREG(sbuf.st_mode)) {
if (req.end == 0) {
req.end = sbuf.st_size;
}
if (req.offset > 0) {
status = 206;
}
serve_static(fd, ffd, &req, sbuf.st_size);
} else if(S_ISDIR(sbuf.st_mode)) {
status = 200;
handle_directory_request(fd, ffd, req.filename);
} else {
status = 400;
char *msg = "Unknow Error";
client_error(fd, status, "Error", msg);
}
close(ffd);
}
#ifdef LOG_ACCESS
log_access(status, clientaddr, &req);
#endif
}
```
如下圖輸出結果，目前的程式碼預設會建立==四個子程序==，加上原本的程序(2450689)共有五個程序可同時服務 clients，若有後續連線請求將暫時得不到回應。
```shell
serve dicrectory '/home/bear/Documents/Github/linux2020/tiny-web-server'
listen on port 9999, fd is 3
child pid is 2450690
child pid is 2450691
child pid is 2450692
child pid is 2450693
accept request, fd is 6, pid is 2450690
accept request, fd is 6, pid is 2450691
accept request, fd is 6, pid is 2450692
accept request, fd is 6, pid is 2450689
accept request, fd is 6, pid is 2450693
...
```
:::danger
文字導向的訊息不要用圖片顯示，否則不利於日後資料檢索，更對視覺障礙者不友善。
:notes: jserv
:::
> 已修正
---
* 作業目標 : 將 `FORK_COUNT` 改成 `0`，以 [coroutine.h](https://www.chiark.greenend.org.uk/~sgtatham/coroutine.h) 實作 coroutine。
* 參考: [Coroutines in C](https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html) 以及 [coroutines and sockets](https://wiki.tcl-lang.org/page/coroutines+and+sockets)
* 想法 : 只使用單一程序，其在等待 client 連線 (accept) 或是 client 資料時 (read) 不使用 blocking 方法，而是將執行權 yield 出去，讓其他 routine 繼續執行工作。
1. 首先將 `FORK_CPUNT` 改為 `0`，則目前只能同時服務一個 client。
```diff=
- #define FORK_COUNT 4
+ #define FORK_COUNT 0
```
2. 設計一個 coroutine `acceptor` 負責接收來自 client 的連線領求，以及一個 scheduler 負責建立 coroutines 來處理已經建立連線的 socket 資料讀取。
```diff
while(1) {
+ acceptor(listenfd, &clientaddr, &clientlen, &pool);
+ scehduler(&pool, &clientaddr, &clientlen);
- connfd = accept(listenfd, (SA *)&clientaddr, &clientlen);
- process(connfd, &clientaddr);
- close(connfd);
}
```
首先我將先前創建的 listenfd 改為 non-blocking，則程序在 accept 時並不會 block。
```cpp
int fileflags = 0;
if (fileflags = fcntl(listenfd, F_GETFL) == -1) {
perror("fcntl F_GETFL");
exit(1);
}
if (fcntl(listenfd, F_SETFL, fileflags | O_NONBLOCK) == -1){
perror("fcntl");
exit(1);
}
```
`acceptor` 的程式碼如下 :
```cpp
void acceptor(int listenfd, struct sockaddr_in *clientaddr, socklen_t *len, pool *p)
{
int connfd = 1;
scrBegin;
while (1) {
connfd = accept(listenfd, (SA*)clientaddr, len);
if (connfd < 0)
{
scrReturnV;
}
else
{
#ifdef LOG_ACCESS
printf("accept request, fd is %d, pid is %d\n", listenfd, getpid());
#endif
add_client(connfd, p);
/* code */
}
}
scrFinishV;
}
```
其會在 accept 到連線的時候將 client 加進 client pool (關於 client pool 的實作請參考 CS:APP 第十二章節)，其餘時候，會 yield 出執行權。
3. 接下來就是設計一個 scheduler 不斷輪流服務每個已經連線的 client (沒有使用 `select` 等 event-driven 的設計)。
```cpp
void scehduler(pool *p, struct sockaddr_in* addr, socklen_t *len)
{
int i, connfd;
rio_t rio;
for (i = 0; i <= p->maxi; i++) {
connfd = p->clientfd[i];
rio = p->clientrio[i];
/* If the descriptor is ready, echo a text line from it */
if ((connfd > 0) /* && (FD_ISSET(connfd, &p->ready_set)) */) {
process(connfd, addr, &p->context[i], &rio);
}
}
}
```
scheduler 為每個已經連線的 client 建立一個 coroutine，以協調處理不同 client 之間的 socketfd 讀寫操作。coroutine 的特性為每次重新進入時可以從上次的返回點之下一行繼續執行。
4. 最後為 process 內部的實作，我盡量維持此 function 的功用 (處理對 socket fd 的讀寫操作)，但是改為一個 client 若是未讀到資料時，就返回以讓 scehduler 服務下個 client 的讀寫操作。
```cpp
```
Sign in with Wallet
Connect another wallet