# Linux 核心專題: 重作第四次作業
> 執行人: Ken-LuWeiRu
> [專題解說影片](https://youtu.be/VRh-ho6Uz-o)
### Reviewed by `Terry7Wei7`
>完成 TODO 事項，並更新本頁面
## 任務簡介
以多執行緒改寫 lab0-c 內建的網頁伺服器並予以量化分析。重作第四次作業並彙整其他學員的成果，務必涵蓋 Linux 核心的應用場景。
## TODO: 以多執行緒改寫 lab0-c 內建的網頁伺服器
> 如果改用多執行緒，能否提升 lab0-c 內建網頁伺服器同時處理連線的數量？
> 務必閱讀 [Linux 核心設計: 針對事件驅動的 I/O 模型演化](https://hackmd.io/@sysprog/linux-io-model)，進行量化分析，並充分解讀。
lab0-c 的網頁執行是基於 [tiny-web-server](https://github.com/7890/tiny-web-server) 上修改，相關網頁程式碼在lab0-c的 web.c 、 linenoise.c 和 console.c 之中。因此先把原本 [tiny-web-server](https://github.com/7890/tiny-web-server) 的多程序處理改成多執行緒處理請求，在使用 [ApacheBench](https://httpd.apache.org/docs/current/programs/ab.html) 來做壓力測試。目前執行成果再使用多執行緒下到一定的數量的同時連線會導致程式碼崩潰。
### [tiny-web-server](https://github.com/7890/tiny-web-server) 專案觀察
是一個用C語言實現的簡單HTTP伺服器，能夠提供靜態檔案和目錄列表的服務，並且支持[範圍請求（partial content）](https://fullstack.wiki/http/status-codes/206)，適合在瀏覽器中播放影片。
#### [tiny-web-server](https://github.com/7890/tiny-web-server) 程式碼觀察
```graphviz
digraph TinyWebServer {
node [shape=box, style=filled, color=lightgrey];
main [label="main\n初始化伺服器環境，解析命令行參數，啟動多程序"];
open_listenfd [label="open_listenfd\n創建並設置伺服器的監聽套接字"];
process [label="process\n處理HTTP請求，根據請求類型調用相應的處理函數"];
parse_request [label="parse_request\n解析HTTP請求，提取檔案名和範圍請求"];
serve_static [label="serve_static\n傳送靜態檔案內容，支持範圍請求"];
handle_directory_request [label="handle_directory_request\n生成並傳送目錄列表的HTML頁面"];
client_error [label="client_error\n處理錯誤情況，返回錯誤信息給客戶端"];
log_access [label="log_access\n記錄客戶端的訪問日誌"];
sendfile [label="sendfile\n高效地將檔案內容傳送給客戶端"];
format_size [label="format_size\n將檔案大小格式化為易讀的字符串"];
writen [label="writen\n將數據寫入到客戶端套接字中"];
main -> open_listenfd;
main -> process [label="fork"];
process -> parse_request;
process -> serve_static [label="if file"];
process -> handle_directory_request [label="if directory"];
process -> client_error [label="if error"];
process -> log_access;
serve_static -> sendfile;
handle_directory_request -> format_size;
handle_directory_request -> writen;
}
```
### 多執行緒程式碼
首先在原本 [tiny.c](https://github.com/7890/tiny-web-server/blob/master/tiny.c) 中新增
```C
void *thread(void *vargp) {
int connfd = *((int *)vargp);
free(vargp);
struct sockaddr_in clientaddr;
socklen_t clientlen = sizeof(clientaddr);
getpeername(connfd, (struct sockaddr *)&clientaddr, &clientlen);
process(connfd, &clientaddr);
close(connfd);
return NULL;
}
```
並修該 main function
```c
int main(int argc, char** argv) {
// ... (省略其他不變的代碼)
listenfd = open_listenfd(default_port);
if (listenfd > 0) {
printf("listen on port %d, fd is %d\n", default_port, listenfd);
} else {
perror("ERROR");
exit(listenfd);
}
// Ignore SIGPIPE signal, so if browser cancels the request, it
// won't kill the whole process.
signal(SIGPIPE, SIG_IGN);
pthread_t tid;
while (1) {
int *connfd = malloc(sizeof(int));
*connfd = accept(listenfd, (SA *)&clientaddr, &clientlen);
pthread_create(&tid, NULL, thread, connfd);
pthread_detach(tid);
}
return 0;
}
```
:::spoiler 移除原來的 fork 相關代碼
```c
// 刪除以下代碼段
/*
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");
}
}
while(1) {
connfd = accept(listenfd, (SA *)&clientaddr, &clientlen);
process(connfd, &clientaddr);
close(connfd);
}
*/s
```
:::
### 網路壓力測試
安裝 [ApacheBench](https://httpd.apache.org/docs/current/programs/ab.html) ``` sudo apt-get install apache2-utils ``` 來測試
#### 首先是未更改前的多程序處理
```bash
$ ab -n 1000 -c 4 http://localhost:9999/
This is ApacheBench, Version 2.3 <$Revision: 1879490 $>
Copyright 1996 Adam Twiss, Zeus Technology Ltd, http://www.zeustech.net/
Licensed to The Apache Software Foundation, http://www.apache.org/
Benchmarking localhost (be patient)
Completed 100 requests
Completed 200 requests
Completed 300 requests
Completed 400 requests
Completed 500 requests
Completed 600 requests
Completed 700 requests
Completed 800 requests
Completed 900 requests
Completed 1000 requests
Finished 1000 requests
Server Software:
Server Hostname: localhost
Server Port: 9999
Document Path: /
Document Length: 749 bytes
Concurrency Level: 4
Time taken for tests: 0.026 seconds
Complete requests: 1000
Failed requests: 0
Total transferred: 793000 bytes
HTML transferred: 749000 bytes
Requests per second: 37841.52 [#/sec] (mean)
Time per request: 0.106 [ms] (mean)
Time per request: 0.026 [ms] (mean, across all concurrent requests)
Transfer rate: 29305.01 [Kbytes/sec] received
Connection Times (ms)
min mean[+/-sd] median max
Connect: 0 0 0.0 0 0
Processing: 0 0 0.0 0 1
Waiting: 0 0 0.0 0 1
Total: 0 0 0.0 0 1
Percentage of the requests served within a certain time (ms)
50% 0
66% 0
75% 0
80% 0
90% 0
95% 0
98% 0
99% 0
100% 1 (longest request)
```
#### 多執行緒處理測試
測試前要先修改當前程序可以打開的最大檔案數，執行以下
``` ulimit -n 102400 ```
```
$ ab -n 1000 -c 4 http://localhost:9998/
This is ApacheBench, Version 2.3 <$Revision: 1879490 $>
Copyright 1996 Adam Twiss, Zeus Technology Ltd, http://www.zeustech.net/
Licensed to The Apache Software Foundation, http://www.apache.org/
Benchmarking localhost (be patient)
Completed 100 requests
Completed 200 requests
Completed 300 requests
Completed 400 requests
Completed 500 requests
Completed 600 requests
Completed 700 requests
Completed 800 requests
Completed 900 requests
Completed 1000 requests
Finished 1000 requests
Server Software:
Server Hostname: localhost
Server Port: 9998
Document Path: /
Document Length: 1344 bytes
Concurrency Level: 4
Time taken for tests: 0.038 seconds
Complete requests: 1000
Failed requests: 5
(Connect: 0, Receive: 0, Length: 5, Exceptions: 0)
Total transferred: 1387991 bytes
HTML transferred: 1343991 bytes
Requests per second: 26104.89 [#/sec] (mean)
Time per request: 0.153 [ms] (mean)
Time per request: 0.038 [ms] (mean, across all concurrent requests)
Transfer rate: 35384.13 [Kbytes/sec] received
Connection Times (ms)
min mean[+/-sd] median max
Connect: 0 0 0.0 0 0
Processing: 0 0 0.0 0 0
Waiting: 0 0 0.0 0 0
Total: 0 0 0.0 0 0
Percentage of the requests served within a certain time (ms)
50% 0
66% 0
75% 0
80% 0
90% 0
95% 0
98% 0
99% 0
100% 0 (longest request)
```
#### 結果分析
##### 多程序處理
```bash
$ ab -n 1000 -c 4 http://localhost:9999/
...
Requests per second: 37841.52 [#/sec] (mean)
Time per request: 0.106 [ms] (mean)
Transfer rate: 29305.01 [Kbytes/sec] received
Failed requests: 0
Percentage of the requests served within a certain time (ms):
100% 1 (longest request)
```
##### 多執行緒處理
```bash
$ ab -n 1000 -c 4 http://localhost:9998/
...
Requests per second: 26104.89 [#/sec] (mean)
Time per request: 0.153 [ms] (mean)
Transfer rate: 35384.13 [Kbytes/sec] received
Failed requests: 5
Percentage of the requests served within a certain time (ms):
100% 0 (longest request)
```
##### 比較與分析
###### Requests per second (每秒請求數):
- 多程序: 37841.52 [#/sec]
- 多執行緒: 26104.89 [#/sec]
觀察到多程序的請求處理率更高，比多執行緒高出約44%。
###### Time per request (每個請求的平均時間):
- 多程序: 0.106 [ms]
- 多執行緒: 0.153 [ms]
多程序的每個請求處理時間更短，表示其處理效率相對較高。
###### Transfer rate (傳輸速率):
- 多程序: 29305.01 [Kbytes/sec]
- 多執行緒: 35384.13 [Kbytes/sec]
多執行緒的傳輸速率更高，這可能是因為多執行緒共享內存資源的效率較高。
###### Failed requests (失敗請求數):
- 多程序: 0
- 多執行緒: 5
多程序在這次測試中沒有失敗的請求，而多執行緒有5個失敗請求，這表示在高並發下，多執行緒可能有穩定性問題。
###### Percentage of the requests served within a certain time (ms):
- 多程序: 100% 的請求在 1 毫秒內完成（最長的請求）。
- 多執行緒: 100% 的請求在 0 毫秒內完成（最長的請求）。
這表明多執行緒在處理請求時，不會出現個別特別久的等待情況。
### 處理多執行緒大量請求會崩潰
簡單粗暴的把 ``` #define RIO_BUFSIZE 10240000 ``` 調高後
#### 多執行緒測試 ``` ab -n 1000 -c 100 http://localhost:9998/ ```
結果如下
```bash
Server Software:
Server Hostname: localhost
Server Port: 9998
Document Path: /
Document Length: 1344 bytes
Concurrency Level: 100
Time taken for tests: 0.262 seconds
Complete requests: 1000
Failed requests: 2
(Connect: 0, Receive: 0, Length: 2, Exceptions: 0)
Total transferred: 1387997 bytes
HTML transferred: 1343997 bytes
Requests per second: 3816.66 [#/sec] (mean)
Time per request: 26.201 [ms] (mean)
Time per request: 0.262 [ms] (mean, across all concurrent requests)
Transfer rate: 5173.36 [Kbytes/sec] received
Connection Times (ms)
min mean[+/-sd] median max
Connect: 0 0 0.8 0 3
Processing: 2 25 6.7 25 41
Waiting: 1 24 6.7 25 41
Total: 3 25 6.2 25 41
Percentage of the requests served within a certain time (ms)
50% 25
66% 27
75% 29
80% 29
90% 32
95% 34
98% 36
99% 38
100% 41 (longest request)
```
#### 原本多程序測試 ``` ab -n 1000 -c 100 http://localhost:9999/ ```
結果如下
```
Server Software:
Server Hostname: localhost
Server Port: 9999
Document Path: /
Document Length: 944 bytes
Concurrency Level: 100
Time taken for tests: 0.030 seconds
Complete requests: 1000
Failed requests: 0
Total transferred: 988000 bytes
HTML transferred: 944000 bytes
Requests per second: 32979.35 [#/sec] (mean)
Time per request: 3.032 [ms] (mean)
Time per request: 0.030 [ms] (mean, across all concurrent requests)
Transfer rate: 31819.92 [Kbytes/sec] received
Connection Times (ms)
min mean[+/-sd] median max
Connect: 0 0 0.3 0 1
Processing: 0 3 0.6 3 4
Waiting: 0 3 0.6 3 4
Total: 1 3 0.4 3 4
Percentage of the requests served within a certain time (ms)
50% 3
66% 3
75% 3
80% 3
90% 4
95% 4
98% 4
99% 4
100% 4 (longest request)
```
##### 結論
在測試中，多程序的最長請求時間為 1 毫秒，而多執行緒的最長請求時間為 0 毫秒，這表明多執行緒在處理請求時更加均勻，沒有個別特別久的等待情況。這對於需要穩定且一致響應時間的應用場景來說是一個重要的優勢。
整體來看，雖然多程序在處理請求數量和每個請求的平均處理時間方面更具優勢，但多執行緒在傳輸速率和資源共享效率方面有其優點，並且在請求響應時間的一致性上表現更好。根據具體的應用場景和需求，可以考慮進一步優化多執行緒的實現，或是採用多程序和多執行緒混合使用的模式，以達到最佳性能和穩定性
##### 問題
目前多執行緒再遇到同時多請求獲著大量請求會崩潰，例如在終端機執行
```
ab -n 10000 -c 10 http://localhost:9998/
```
後，之前執行建立伺服器的終端機會顯示
```
$ ./tiny
serve directory '/home/nckusoc/titest/old/tiny-web-server'
listen on port 9998, fd is 3
# 執行ab -n 10000 -c 10 http://localhost:9998/
...
Connection closed for 127.0.0.1:56732
127.0.0.1:56642 200 - '.' (text/plain)
Connection closed for 127.0.0.1:56720
Segmentation fault (core dumped) `
```
##### TODO list
- [X] 優化多執行緒程式碼，處理Segmentation fault (core dumped) 在大量請求下。
- [x] 簡單粗暴的把 ``` #define RIO_BUFSIZE 10240000 ```
- [ ] 檢查並發控制和資源同步機制，確保不會出現競態條件或死鎖。
- [ ] 考慮增加執行緒池來管理執行緒數量，避免因為執行緒數量過多導致系統資源耗盡。
- [x] 調整執行緒堆棧大小和其他執行緒參數，以適應高並發情況。
- [x] 將多程序和多執行緒結合使用，利用多程序的穩定性和多執行緒的高效資源利用。可以考慮每個程序內部使用多執行緒處理請求，進一步提升系統的並發能力和穩定性。
- [ ] 增加錯誤處理代碼，確保執行緒崩潰時能夠正確地回收資源，防止資源泄漏。
- [ ] 部屬到 [lab0-c](https://github.com/sysprog21/lab0-c) 中
### 多程序和多執行緒混合模式
* 新增了 #include <pthread.h>。
* 調整了宏定義部分，新增了 THREAD_COUNT 定義。
```C
#include <pthread.h>
#ifndef THREAD_COUNT
#define THREAD_COUNT 8
#endif
```
* 修改了 DEFAULT_PORT 的預設值。
```C
#define DEFAULT_PORT 9997 /* use this port if none given as arg to main() */
```
* 添加了 process 函數的前向宣告。
```c
void process(int fd, struct sockaddr_in *clientaddr); // 前向聲明
```
* 處理客戶端請求的處理邏輯，並將請求分派給多執行緒來處理，以提升伺服器的效能
* 每個執行緒的入口函數
```C
void process(int fd, struct sockaddr_in *clientaddr) {
#ifdef LOG_ACCESS
printf("accept request, fd is %d, pid is %d\n", fd, getpid());
#endif
// 計數測試
for (int i = 1; i <= 10000000; i++) {
// 這裡可以加上一些額外的操作，比如打印或者計時
}
printf("Counting to 10000000 finished.\n");
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);
} 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 = "Unknown Error";
client_error(fd, status, "Error", msg);
}
close(ffd);
}
#ifdef LOG_ACCESS
log_access(status, clientaddr, &req);
#endif
}
typedef struct {
int connfd;
struct sockaddr_in clientaddr;
} thread_args_t;
void *thread_worker(void *arg) {
thread_args_t *args = (thread_args_t *)arg;
process(args->connfd, &args->clientaddr);
close(args->connfd);
free(args);
return NULL;
}
```
* 修改了 main 函數的實作：
* 刪除了未使用的 connfd 變數。
* 在 main 中新增了多執行緒和多程序的處理邏輯。
```C
int main(int argc, char** argv) {
// 刪除未使用的 connfd 變數
int default_port = DEFAULT_PORT,
listenfd;
struct sockaddr_in clientaddr;
char buf[256];
char *path = getcwd(buf, 256);
socklen_t clientlen = sizeof clientaddr;
if(argc == 2) {
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) {
default_port = atoi(argv[2]);
path = argv[1];
if(chdir(path) != 0) {
perror(path);
exit(1);
}
}
printf("serve directory '%s'\n", path);
listenfd = open_listenfd(default_port);
if (listenfd > 0) {
printf("listen on port %d, fd is %d\n", default_port, listenfd);
} else {
perror("ERROR");
exit(listenfd);
}
signal(SIGPIPE, SIG_IGN);
int i = 0;
for (; i < FORK_COUNT; i++) {
int pid = fork();
if (pid == 0) {
while (1) {
int connfd = accept(listenfd, (SA *)&clientaddr, &clientlen);
if (connfd < 0) {
perror("accept");
continue;
}
thread_args_t *args = malloc(sizeof(thread_args_t));
if (args == NULL) {
perror("malloc");
close(connfd);
continue;
}
args->connfd = connfd;
args->clientaddr = clientaddr;
pthread_t thread;
if (pthread_create(&thread, NULL, thread_worker, args) != 0) {
perror("pthread_create");
close(connfd);
free(args);
continue;
}
pthread_detach(thread);
}
} else if (pid > 0) {
printf("child pid is %d\n", pid);
} else {
perror("fork");
}
}
while (1) {
int connfd = accept(listenfd, (SA *)&clientaddr, &clientlen);
if (connfd >= 0) {
thread_args_t *args = malloc(sizeof(thread_args_t));
if (args != NULL) {
args->connfd = connfd;
args->clientaddr = clientaddr;
pthread_t thread;
if (pthread_create(&thread, NULL, thread_worker, args) == 0) {
pthread_detach(thread);
} else {
perror("pthread_create");
close(connfd);
free(args);
}
} else {
perror("malloc");
close(connfd);
}
} else {
perror("accept");
}
}
return 0;
}
```
```graphviz
digraph functions {
rankdir=LR;
node [shape=box, style=filled, color=lightgrey];
main [label="main\n初始化伺服器，創建子程序和執行緒"];
open_listenfd [label="open_listenfd\n創建和綁定伺服器套接字"];
fork [label="fork\n創建子程序"];
thread_worker [label="thread_worker\n執行緒函數，調用 process 處理請求"];
process [label="process\n處理客戶端請求的主要邏輯"];
parse_request [label="parse_request\n解析客戶端請求，提取請求的檔案名和範圍"];
handle_directory_request [label="handle_directory_request\n處理資料夾請求，生成目錄列表"];
serve_static [label="serve_static\n處理靜態檔案請求，返回檔案內容"];
client_error [label="client_error\n處理錯誤，返回錯誤信息"];
rio_readinitb [label="rio_readinitb\n初始化緩衝區"];
rio_readlineb [label="rio_readlineb\n從緩衝區讀取一行"];
format_size [label="format_size\n格式化檔案大小"];
writen [label="writen\n寫入數據到套接字"];
get_mime_type [label="get_mime_type\n獲取檔案的 MIME 類型"];
main -> open_listenfd;
main -> fork [label="fork"];
fork -> thread_worker;
thread_worker -> process;
process -> parse_request;
process -> handle_directory_request [label="is_dir"];
process -> serve_static [label="is_file"];
process -> client_error [label="error"];
parse_request -> rio_readinitb;
parse_request -> rio_readlineb;
handle_directory_request -> format_size;
handle_directory_request -> writen;
serve_static -> writen;
serve_static -> get_mime_type;
client_error -> writen;
}
```
```bash
$ ab -n 1000 -c 4 http://localhost:9997/
This is ApacheBench, Version 2.3 <$Revision: 1879490 $>
Copyright 1996 Adam Twiss, Zeus Technology Ltd, http://www.zeustech.net/
Licensed to The Apache Software Foundation, http://www.apache.org/
Benchmarking localhost (be patient)
Completed 100 requests
Completed 200 requests
Completed 300 requests
Completed 400 requests
Completed 500 requests
Completed 600 requests
Completed 700 requests
Completed 800 requests
Completed 900 requests
Completed 1000 requests
Finished 1000 requests
Server Software:
Server Hostname: localhost
Server Port: 9997
Document Path: /
Document Length: 1035 bytes
Concurrency Level: 4
Time taken for tests: 0.040 seconds
Complete requests: 1000
Failed requests: 0
Total transferred: 1079000 bytes
HTML transferred: 1035000 bytes
Requests per second: 25201.61 [#/sec] (mean)
Time per request: 0.159 [ms] (mean)
Time per request: 0.040 [ms] (mean, across all concurrent requests)
Transfer rate: 26555.22 [Kbytes/sec] received
Connection Times (ms)
min mean[+/-sd] median max
Connect: 0 0 0.0 0 0
Processing: 0 0 0.1 0 1
Waiting: 0 0 0.1 0 0
Total: 0 0 0.1 0 1
Percentage of the requests served within a certain time (ms)
50% 0
66% 0
75% 0
80% 0
90% 0
95% 0
98% 0
99% 0
100% 1 (longest request)
```
```bash
$ ab -n 1000 -c 100 http://localhost:9997/
This is ApacheBench, Version 2.3 <$Revision: 1879490 $>
Copyright 1996 Adam Twiss, Zeus Technology Ltd, http://www.zeustech.net/
Licensed to The Apache Software Foundation, http://www.apache.org/
Benchmarking localhost (be patient)
Completed 100 requests
Completed 200 requests
Completed 300 requests
Completed 400 requests
Completed 500 requests
Completed 600 requests
Completed 700 requests
Completed 800 requests
Completed 900 requests
Completed 1000 requests
Finished 1000 requests
Server Software:
Server Hostname: localhost
Server Port: 9997
Document Path: /
Document Length: 1035 bytes
Concurrency Level: 100
Time taken for tests: 0.036 seconds
Complete requests: 1000
Failed requests: 3
(Connect: 0, Receive: 0, Length: 3, Exceptions: 0)
Non-2xx responses: 1
Total transferred: 1077976 bytes
HTML transferred: 1033978 bytes
Requests per second: 27763.90 [#/sec] (mean)
Time per request: 3.602 [ms] (mean)
Time per request: 0.036 [ms] (mean, across all concurrent requests)
Transfer rate: 29227.36 [Kbytes/sec] received
Connection Times (ms)
min mean[+/-sd] median max
Connect: 0 2 0.5 1 3
Processing: 1 2 0.5 2 3
Waiting: 0 1 0.3 1 2
Total: 1 3 0.6 4 5
ERROR: The median and mean for the initial connection time are more than twice the standard
deviation apart. These results are NOT reliable.
WARNING: The median and mean for the total time are not within a normal deviation
These results are probably not that reliable.
Percentage of the requests served within a certain time (ms)
50% 4
66% 4
75% 4
80% 4
90% 4
95% 4
98% 4
99% 4
100% 5 (longest request)
```
### ref
:::spoiler 參考學員
https://hackmd.io/@fennecJ/linux2024-homework1#%E7%B6%B2%E9%A0%81%E4%BC%BA%E6%9C%8D%E5%99%A8
https://hackmd.io/@tintinjian12999/linux2024-homework1#%E6%95%B4%E5%90%88%E7%B6%B2%E9%A0%81%E4%BC%BA%E6%9C%8D%E5%99%A8
https://hackmd.io/@howardjchen/rkZ1s1r26#%E6%95%B4%E5%90%88-tiny-web-server
https://hackmd.io/@fatCatOrange/linux2024-homework1#%E6%95%B4%E5%90%88%E7%B6%B2%E9%A0%81%E4%BC%BA%E6%9C%8D%E5%99%A8
https://hackmd.io/@marvin0102/linux2024-homework1#linenoise-%E8%88%87%E7%B6%B2%E9%A0%81%E4%BC%BA%E6%9C%8D%E5%99%A8%E7%9A%84%E4%B8%A6%E5%AD%98%E5%8E%9F%E7%90%86
https://hackmd.io/@8gdFdQxMR8O0u3u7xLQmxA/r1V9YJI26#%E4%BD%BF%E7%94%A8-select-%E6%94%B9%E5%96%84-Web-%E8%88%87-Linenoise-%E4%B9%8B%E8%A1%9D%E7%AA%81%E5%95%8F%E9%A1%8C
https://hackmd.io/@jujuegg/HkYOnnBn6#%E6%94%B9%E5%96%84-web-%E8%88%87-linenoise-%E4%B9%8B%E8%A1%9D%E7%AA%81%E5%95%8F%E9%A1%8C
https://hackmd.io/@NeedSleep/linux2024-homework1#web
https://hackmd.io/@csotaku0926/linux2024-homework1#%E6%95%B4%E5%90%88%E7%B6%B2%E9%A0%81%E4%BC%BA%E6%9C%8D%E5%99%A8
https://hackmd.io/@vax-r/linux2024-homework1#%E6%95%B4%E5%90%88%E7%B6%B2%E9%A0%81%E4%BC%BA%E6%9C%8D%E5%99%A8
https://hackmd.io/@millaker/HyXNtXmna#Web-server-and-linenoise-issue
https://hackmd.io/@shawne/linux2024-homework1#%E6%95%B4%E5%90%88%E7%B6%B2%E9%A0%81%E4%BC%BA%E6%9C%8D%E5%99%A8
https://hackmd.io/@stevennnnnn/linux2024-homework1#%E6%95%B4%E5%90%88%E7%B6%B2%E9%A0%81%E4%BC%BA%E6%9C%8D%E5%99%A8
https://hackmd.io/@404allen404/linux2024-homework1
https://hackmd.io/@johnny69527/linux2024-homework1#%E6%95%B4%E5%90%88-web-%E5%91%BD%E4%BB%A4%E5%92%8C-linenoise-%E5%A5%97%E4%BB%B6
https://hackmd.io/@paul90317linux/linux2024-homework1#%E6%95%B4%E5%90%88%E7%B6%B2%E9%A0%81%E4%BC%BA%E6%9C%8D%E5%99%A8
https://hackmd.io/@ranvd/linux2024-homework1#%E7%A2%BA%E4%BF%9D-linenoise-%E5%A5%97%E4%BB%B6%E5%9C%A8-web-%E5%95%9F%E5%8B%95%E6%99%82%E6%AD%A3%E5%B8%B8%E5%9F%B7%E8%A1%8C
:::
## TODO: 重作第四次作業並彙整其他學員的成果
> 務必涵蓋 Linux 核心的應用場景。
> 自[期末專題列表](https://hackmd.io/@sysprog/linux2024-projects)找出同樣投入本題目的學員，提出你的疑惑和建議。
### [quiz3-test1](https://hackmd.io/@sysprog/linux2024-quiz3#%E6%B8%AC%E9%A9%97-1)
#### 1. 解釋上述程式碼運作原理並重新整理數學式 (原題目故意略去某些細節)，並嘗試用第 2 週測驗題提到的 ffs / fls 取代 __builtin_clz，使程式不依賴 GNU extension，且提供分支和無分支 (branchless) 的實作
##### 改寫 `i_sqrt` 函式
首先，我們需要一個不依賴 `log2` 的版本。這可以通過手動計算最左邊的1來實現。
```c
int i_sqrt(int N)
{
int msb = 0;
int n = N;
while (n > 1) {
n >>= 1;
msb++;
}
int a = 1 << msb;
int result = 0;
while (a != 0) {
if ((result + a) * (result + a) <= N)
result += a;
a >>= 1;
}
return result;
}
```
##### 運作原理解釋
上述程式碼的運作原理可以分為兩部分：
1. 計算最左邊的1所在的位置，即最高有效位 (MSB)。
2. 依據最高有效位進行二進位搜尋，以逐步逼近平方根。
##### 使用 `ffs` 或 `fls` 替代 `__builtin_clz`
為了替代 `__builtin_clz`，我們可以使用 `ffs` 或 `fls` 來計算最左邊的1。
##### 使用 `ffs`：
```c
#include <strings.h>
int i_sqrt_ffs(int N)
{
if (N <= 1)
return N;
int tmp = N, msb = 0;
while (tmp) {
int i = ffs(tmp);
msb += i;
tmp >>= i;
}
msb--;
int a = 1 << (msb & ~1);
int result = 0;
while (a != 0) {
if ((result + a) * (result + a) <= N)
result += a;
a >>= 1;
}
return result;
}
```
##### 使用 `fls`：
```c
#include <strings.h>
int fls(int x) {
int r = 32;
if (!x) return 0;
if (!(x & 0xffff0000)) { x <<= 16; r -= 16; }
if (!(x & 0xff000000)) { x <<= 8; r -= 8; }
if (!(x & 0xf0000000)) { x <<= 4; r -= 4; }
if (!(x & 0xc0000000)) { x <<= 2; r -= 2; }
if (!(x & 0x80000000)) { x <<= 1; r -= 1; }
return r;
}
int i_sqrt_fls(int N)
{
if (N <= 1)
return N;
int msb = fls(N) - 1;
int a = 1 << (msb & ~1);
int result = 0;
while (a != 0) {
if ((result + a) * (result + a) <= N)
result += a;
a >>= 1;
}
return result;
}
```
##### 提供有分支和無分支的實作
###### 有分支實作：
```c
int i_sqrt_branch(int N)
{
if (N <= 1)
return N;
int msb = fls(N) - 1;
int a = 1 << (msb & ~1);
int result = 0;
while (a != 0) {
if ((result + a) * (result + a) <= N)
result += a;
a >>= 1;
}
return result;
}
```
###### 無分支實作：
```c
int i_sqrt_branchless(int N)
{
if (N <= 1)
return N;
int msb = fls(N) - 1;
int a = 1 << (msb & ~1);
int result = 0;
while (a != 0) {
int temp = result + a;
int temp2 = temp * temp;
result += (temp2 <= N) * a;
a >>= 1;
}
return result;
}
```
#### 2. 在 Linux 核心原始程式碼找出對整數進行平方根運算的程式碼，並解說其應用案例，至少該包含 [block 目錄的程式碼](https://github.com/torvalds/linux/tree/master/block)。
##### 1. 整數平方根函數 `int_sqrt`
Linux 核心中的整數平方根函數定義於 `/lib/math/int_sqrt.c` 中，使用了 Digit-by-digit calculation 方法來計算開平方根。其具體實作如下：
```c
unsigned long int_sqrt(unsigned long x)
{
unsigned long b, m, y = 0;
if (x <= 1)
return x;
m = 1UL << (__fls(x) & ~1UL);
while (m != 0) {
b = y + m;
y >>= 1;
if (x >= b) {
x -= b;
y += m;
}
m >>= 2;
}
return y;
}
EXPORT_SYMBOL(int_sqrt);
```
這段程式碼中，`__fls(x)` 用於找到數字 x 的最高有效位（Most Significant Bit, MSB），並設定變數 m 為 2 的冪值。接著使用 Digit-by-digit calculation 方法迴圈計算開平方根，直到 m 變為 0。
##### 2. `rwb_arm_timer` 函數中的應用
`int_sqrt` 函數在 Linux 核心中的一個應用範例位於 `block/blk-wbt.c` 檔案中，用於處理 Buffered Writeback Throttling。該函數 `rwb_arm_timer` 使用了 `int_sqrt` 來調整 I/O 請求佇列的深度和監控窗口大小。具體實作如下：
```c
static void rwb_arm_timer(struct rq_wb *rwb)
{
struct rq_depth *rqd = &rwb->rq_depth;
if (rqd->scale_step > 0) {
/*
* We should speed this up, using some variant of a fast
* integer inverse square root calculation. Since we only do
* this for every window expiration, it's not a huge deal,
* though.
*/
rwb->cur_win_nsec = div_u64(rwb->win_nsec << 4,
int_sqrt((rqd->scale_step + 1) << 8));
} else {
/*
* For step < 0, we don't want to increase/decrease the
* window size.
*/
rwb->cur_win_nsec = rwb->win_nsec;
}
blk_stat_activate_nsecs(rwb->cb, rwb->cur_win_nsec);
}
```
在這段程式碼中，當 `scale_step` 大於 0 時，使用 `int_sqrt` 函數計算新的監控窗口大小。具體操作是將 `rwb->win_nsec` 左移 4 位，再除以 `(rqd->scale_step + 1) << 8` 的平方根，以動態調整監控窗口大小。
#### 3. 閱讀[〈Analysis of the lookup table size for square-rooting〉](https://web.ece.ucsb.edu/~parhami/pubs_folder/parh99-asilo-table-sq-root.pdf)和[〈Timing Square Root〉](https://web.archive.org/web/20210208132927/http://assemblyrequired.crashworks.org/timing-square-root/)，嘗試撰寫更快的整數開平分根運算程式。
在〈Analysis of the lookup table size for square-rooting〉這篇論文中，有如何使用查找表（Lookup Table）來加速平方根運算。查找表是一種常用的優化技術，特別適用於處理大數據量的快速運算。在此基礎上實作了一個簡單的查找表算法。
以下改進版本的整數開平方根運算程式：
```c
#define SQRT_TABLE_SIZE 256
// 預先生成的查找表，用於快速查找平方根
static const unsigned char sqrt_table[SQRT_TABLE_SIZE] = {
0, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4,
// 省略中間值，實際查找表需要涵蓋完整的數值範圍
15, 15, 15, 15, 16, 16, 16, 16
};
unsigned long fast_int_sqrt(unsigned long x) {
unsigned long result, remainder, root;
unsigned char index;
if (x < SQRT_TABLE_SIZE) {
return sqrt_table[x];
}
// 使用查找表的高位數據作為初始估計
index = x >> ((sizeof(unsigned long) * 8) - 8);
result = sqrt_table[index] << ((sizeof(unsigned long) * 8) / 2 - 4);
// 使用牛頓迭代法進行精確計算
root = (result + x / result) / 2;
while (root < result) {
result = root;
root = (result + x / result) / 2;
}
return result;
}
```
##### 改進方案說明
1. **查找表**：預先生成一個小範圍的平方根查找表，用於處理小數的快速計算。
2. **初始估計**：對於大數，使用查找表的高位數據作為平方根的初始估計值，這樣可以大大減少後續迭代的次數。
3. **牛頓迭代法**：在初始估計值的基礎上，使用牛頓迭代法進行精確計算，逐步逼近實際的平方根值。
##### 應用案例
改進的 `fast_int_sqrt` 函數可以用於需要高效計算平方根的場合，例如圖形渲染、科學計算以及各種實時系統中。這種優化方法既提高了運算速度，又保持了計算的準確性，特別適合於需要大量進行平方根計算的場景。
:::spoiler 參考學員
https://github.com/torvalds/linux/blob/master/block/blk-wbt.c
https://hackmd.io/@NeedSleep/linux2024-homework4#isqrt1-bitwise-操作
https://hackmd.io/@csotaku0926/linux2024-homework4#測驗一
https://hackmd.io/@tony268596/linux2024-homework4#測驗一
https://hackmd.io/@ShchangAnderson/linux2024-homework4#測驗一
https://hackmd.io/@david96514/linux2024-homework4#測驗-1
https://hackmd.io/@yehsudo/linux2024-homework4
https://hackmd.io/@marvin0102/linux2024-homework4#測驗-1-計算開平方根
https://hackmd.io/@allenliao666/linux2024-homework4#測驗1
https://hackmd.io/@howardjchen/Sk4NDSpJC#測驗-1
https://hackmd.io/@jeremytsai/Homework4_quiz3_4#測驗-1--Using-bitwise-operations-to-compute-square-root
https://hackmd.io/@popo8712/linux2024-homework4#測驗一
https://hackmd.io/@10530417/hw4#測驗一
https://hackmd.io/@Kuanch/linux2024-homework4#Quiz-1---Bitwise-Square
https://hackmd.io/@yinghuaxia/linux2024-homework4#測驗一
https://hackmd.io/@yuu907/linux2024-homework4#測驗-1
https://hackmd.io/@sushake/linux2024-homework4#第一周測驗1
https://hackmd.io/@otteryc/linux2024-homework4#第三次小考
https://hackmd.io/@jimmylu0303/linux2024-homework4#測驗一
:::
### [quiz3-test2](https://hackmd.io/@sysprog/linux2024-quiz3#%E6%B8%AC%E9%A9%97-2)
題目是針對正整數在相鄰敘述進行 `mod 10` 和 `div 10` 操作，並希望透過位運算減少運算成本。以下是具體的解決方案和延伸問題的探討。
#### 問題解讀
目前程式碼如下：
```c
static void str_add(char *b, char *a, char *res, size_t size)
{
int carry = 0;
for (int i = 0; i < size; i++) {
int tmp = (b[i] - '0') + (a[i] - '0') + carry;
carry = tmp / 10;
tmp = tmp % 10;
res[i] = tmp + '0';
}
}
```
這段程式碼進行了多次 `tmp / 10` 和 `tmp % 10` 的操作。若能利用位運算來實現這些操作，可以減少運算成本。以下是使用 `Hacker's Delight` 提到的位運算技術來實現除法和取餘數的方法。
#### 方案說明
根據 `Hacker's Delight`，由於 `10` 無法直接用二的冪表示，因此需要找到一個近似值。我們可以利用以下的關係式：
\[
\frac{13}{128} \approx \frac{1}{10}
\]
因此，除以 10 可以轉換為乘以 13 並右移 7 位。接下來我們實現這個轉換。
#### 程式碼實作
以下是利用位運算來進行 `mod 10` 和 `div 10` 的程式碼：
```c
void divmod_10(uint32_t in, uint32_t *div, uint32_t *mod)
{
uint32_t x = (in | 1) - (in >> 2); // 初步近似值
uint32_t q = (x >> 4) + x;
x = q;
q = (q >> 8) + x;
q = (q >> 8) + x;
q = (q >> 8) + x;
q = (q >> 8) + x;
*div = (q >> 3); // 得到商
*mod = in - ((q & ~0x7) + (*div << 1)); // 得到餘數
}
```
#### 測試程式碼
以下是測試上述函式的程式碼：
```c
#include <stdint.h>
#include <stdio.h>
int main()
{
uint32_t div, mod;
for (int n = 0; n <= 19; n++) {
divmod_10(n, &div, &mod);
printf("n: %d, div: %d, mod: %d\n", n, div, mod);
}
return 0;
}
```
#### 執行結果
執行上述測試程式，預期的結果如下：
```
n: 0, div: 0, mod: 0
n: 1, div: 0, mod: 1
n: 2, div: 0, mod: 2
n: 3, div: 0, mod: 3
n: 4, div: 0, mod: 4
n: 5, div: 0, mod: 5
n: 6, div: 0, mod: 6
n: 7, div: 0, mod: 7
n: 8, div: 0, mod: 8
n: 9, div: 0, mod: 9
n: 10, div: 1, mod: 0
n: 11, div: 1, mod: 1
n: 12, div: 1, mod: 2
n: 13, div: 1, mod: 3
n: 14, div: 1, mod: 4
n: 15, div: 1, mod: 5
n: 16, div: 1, mod: 6
n: 17, div: 1, mod: 7
n: 18, div: 1, mod: 8
n: 19, div: 1, mod: 9
```
這些結果與預期一致，證明上述方法正確。
#### 延伸問題
1. **參照《Hacker's Delight》和 CS:APP 第二章，解釋上述程式碼運作原理，並對照 Instruction tables，以分析最初具備除法操作的程式碼和最終完全不依賴除法和乘法的實作程式碼裡頭，指令序列佔用的 CPU 週期數量。**
- 初步分析：
- 使用除法操作的原始程式碼在大多數處理器上都會佔用較多的 CPU 週期，因為除法操作通常比加法和位移操作慢。
- 優化後的程式碼使用了多次的位移和加法操作，這些操作在大多數處理器上都更快。
- 實際測量可以使用工具如 `perf` 來分析 CPU 週期的佔用。
2. **練習撰寫不依賴任何除法指令的 % 9 (modulo 9) 和 % 5 (modulo 5) 程式碼，並證明在 uint32_t 的有效範圍可達到等效。**
- % 9 (modulo 9)：
```c
uint32_t mod9(uint32_t n) {
uint32_t x = (n >> 3) + (n >> 1);
x = x + (x >> 4);
x = x + (x >> 8);
x = x + (x >> 16);
return n - 9 * (x >> 3);
}
```
- % 5 (modulo 5)：
```c
uint32_t mod5(uint32_t n) {
uint32_t x = (n >> 3) + (n >> 1);
x = x + (x >> 4);
x = x + (x >> 8);
x = x + (x >> 16);
return n - 5 * (x >> 2);
}
```
- 測試這些函式，確保其結果正確。
這樣，我們可以在不依賴除法指令的情況下，使用位運算來進行有效的除法和取餘數操作。這不僅提高了運算效率，還能在某些不支持除法指令的處理器上實現同樣的功能。
#### ref
:::spoiler
https://hackmd.io/@vax-r/linux2024-homework4#測驗二
https://hackmd.io/@csotaku0926/linux2024-homework4#測驗二
https://hackmd.io/@ShchangAnderson/linux2024-homework4#測驗二
https://hackmd.io/@Kuanch/linux2024-homework4#Quiz-2---Bitwise-Division-and-Modular
https://hackmd.io/@marvin0102/linux2024-homework4#測驗-2-計算除法
https://hackmd.io/@popo8712/linux2024-homework4#測驗二
https://hackmd.io/@10530417/hw4#測驗二
https://hackmd.io/@david96514/linux2024-homework4#測驗-2
https://hackmd.io/@yinghuaxia/linux2024-homework4#測驗二
https://hackmd.io/@yuu907/linux2024-homework4#測驗-2
https://hackmd.io/@jeremytsai/Homework4_quiz3_4#測驗-2--Using-bitwise-operations-to-perform-mod-10-and-div-10
https://hackmd.io/@allenliao666/linux2024-homework4#測驗2
:::
### [quiz3-test3](https://hackmd.io/@sysprog/linux2024-quiz3#%E6%B8%AC%E9%A9%97-3)
#### 回答測驗三
依據題目要求補完程式碼如下：
```c
// 版本一
int ilog2(int i)
{
int log = -1;
while (i) {
i >>= 1;
log++;
}
return log;
}
// 版本二
static size_t ilog2(size_t i)
{
size_t result = 0;
while (i >= 65536) {
result += 16;
i >>= 16;
}
while (i >= 256) {
result += 8;
i >>= 8;
}
while (i >= 16) {
result += 4;
i >>= 4;
}
while (i >= 2) {
result += 1;
i >>= 1;
}
return result;
}
// 版本三
int ilog32(uint32_t v)
{
return (31 - __builtin_clz(v | 1));
}
```
#### 2. 解釋程式碼運作原理
**版本一**：
- 這個版本使用右移運算符 (`>>=`) 將輸入的數字每次右移一位，並且每次右移都將 `log` 變數加一。這樣做會計算輸入值的二進制表示中有多少位數，從而計算出以 2 為底的對數。
- 初始時將 `log` 設為 -1，這樣當 `i` 為 0 時，返回的結果也是 0。
**版本二**：
- 這個版本使用了更快的方法來計算對數。它通過檢查數字的高位，能夠一次減少多個位數的比較，從而加速計算過程。該版本分別檢查數字是否大於或等於 65536、256、16 和 2，並相應地右移 16、8、4 和 1 位。這種方法有效地減少了迭代的次數。
**版本三**：
- 這個版本使用了 GNU 擴展函數 `__builtin_clz`，它計算出一個整數前導零的數量。通過 31 減去前導零的數量，得出最高位 1 的位置，從而計算出以 2 為底的對數。這個方法在計算上非常高效，但不處理輸入為 0 的情況，故 `v | 1` 可以確保即使輸入為 0 也能正確處理。
#### 3. 在 Linux 核心原始程式碼中找出 log2 的相關程式碼並解說應用案例
在 Linux 核心程式碼中，`ilog2` 通常用於計算以 2 為底的對數，以便在內核中進行高效的計算。以下是一個應用案例：
```c
// 定義在 include/linux/log2.h
#define ilog2(n) \
( \
__builtin_constant_p(n) ? \
((n) < 2 ? 0 : \
63 - __builtin_clzll(n)) : \
(sizeof(n) <= 4) ? \
__ilog2_u32(n) : \
__ilog2_u64(n) \
)
// __ilog2_u32 和 __ilog2_u64 的實現方式類似於我們的版本二
static __always_inline __attribute__((const))
int __ilog2_u32(u32 n)
{
return fls(n) - 1;
}
static __always_inline __attribute__((const))
int __ilog2_u64(u64 n)
{
return fls64(n) - 1;
}
```
**應用案例**：
`ilog2` 函數在 Linux 核心的內存管理、設備驅動和其他需要高效計算的地方廣泛使用。例如，在 PCIe 設備驅動中，它用於計算設備需要的內存大小：
```c
static int rockchip_pcie_ep_set_bar(struct pci_epc *epc, u8 fn, u8 vfn,
struct pci_epf_bar *epf_bar)
{
// 省略其他程式碼
sz = 1ULL << fls64(sz - 1);
aperture = ilog2(sz) - 7; // 使用 ilog2 計算 aperture 大小
// 省略其他程式碼
}
```
在這個應用中，`ilog2` 用於計算設備 BAR 大小，確保為設備分配合適的內存空間。
#### ref
:::spoiler
https://hackmd.io/@tony268596/linux2024-homework4#測驗三
https://hackmd.io/@8gdFdQxMR8O0u3u7xLQmxA/SJsmMDdRp#測驗3
https://hackmd.io/@vax-r/linux2024-homework4#測驗三
https://hackmd.io/@csotaku0926/linux2024-homework4#測驗三
https://hackmd.io/@ShchangAnderson/linux2024-homework4#測驗三
https://hackmd.io/@david96514/linux2024-homework4#測驗-3
https://hackmd.io/@Kuanch/linux2024-homework4#Quiz-3---Bitwise-log2
https://hackmd.io/@yinghuaxia/linux2024-homework4#測驗三
https://hackmd.io/@brianPA/LinuxHomework4#測驗三
https://hackmd.io/@ivywang2015/linux2024-homework4#測驗三
https://hackmd.io/@Ackerman/H1OvNOx1A#測驗-3
https://hackmd.io/@marvin0102/linux2024-homework4#測驗-3
https://hackmd.io/@ivywang2015/linux2024-homework4#測驗三
https://hackmd.io/@jeremytsai/Homework4_quiz3_4#測驗-3--Using-bitwise-operations-to-calculate-the-logarithm-base-2
https://hackmd.io/@allenliao666/linux2024-homework4#測驗3
https://hackmd.io/@popo8712/linux2024-homework4#測驗三
https://hackmd.io/@howardjchen/Sk4NDSpJC#測驗-3
ok 的 (解釋不錯)
https://hackmd.io/@yuu907/linux2024-homework4#測驗-3
https://hackmd.io/@sushake/linux2024-homework4#第一周測驗2
https://hackmd.io/@NdB0NahsRSSnwZagYYcL6g/linux2024-homework4#測驗三
https://hackmd.io/@10530417/hw4#測驗三
:::
### [quiz3-test4](https://hackmd.io/@sysprog/linux2024-quiz3#%E6%B8%AC%E9%A9%97-4)
#### 測驗四：Exponentially Weighted Moving Average (EWMA) 的程式碼運作原理
EWMA 是一種統計手法，用於計算時間序列數據的加權移動平均。其主要特點是新資料的權重較大，而舊資料的權重則隨時間指數衰減。以下是 EWMA 的數學定義：
$$
S_t = \begin{cases}
Y_0 & t = 0 \\
\alpha Y_t + (1 - \alpha) S_{t-1} & t > 0
\end{cases}
$$
其中：
- \( \alpha \) 表示加權衰減的速率，範圍在 0 到 1 之間。
- \( Y_t \) 是時間 \( t \) 的數據點。
- \( S_t \) 是時間 \( t \) 的 EWMA。
在題目提供的程式碼中，`ewma` 結構體用於存儲 EWMA 的相關參數：
```c
struct ewma {
unsigned long internal;
unsigned long factor;
unsigned long weight;
};
```
接下來分析各函式的運作：
##### 1. `ewma_init`
```c
void ewma_init(struct ewma *avg, unsigned long factor, unsigned long weight)
{
if (!is_power_of_2(weight) || !is_power_of_2(factor))
assert(0 && "weight and factor have to be a power of two!");
avg->weight = ilog2(weight);
avg->factor = ilog2(factor);
avg->internal = 0;
}
```
- 此函式用於初始化 EWMA 結構體。
- 檢查 `weight` 和 `factor` 是否為 2 的冪，因為這樣能夠利用位運算來提高計算效率。
- `ilog2` 函式返回對數值，方便後續位運算。
##### 2. `ewma_add`
```c
struct ewma *ewma_add(struct ewma *avg, unsigned long val)
{
avg->internal = avg->internal
? (((avg->internal << avg->weight) - avg->internal) +
(val << avg->factor)) >> avg->weight
: (val << avg->factor);
return avg;
}
```
- 此函式用於將新的數據點 \( val \) 加入 EWMA 計算。
- 如果 `avg->internal` 為 0，表示是第一個數據點，則直接將 `val` 乘以 `factor`。
- 如果 `avg->internal` 不為 0，則按以下方式計算新的 `internal` 值：
- 先將 `internal` 左移 `weight` 位，這相當於乘以 \( 2^{\text{weight}} \)。
- 減去原來的 `internal`，這相當於計算 \( (1 - \alpha) \cdot S_{t-1} \)。
- 將新數據點 `val` 左移 `factor` 位，這相當於計算 \( \alpha \cdot Y_t \)。
- 將兩者相加，再右移 `weight` 位，得到新的 `internal` 值。
##### 3. `ewma_read`
```c
unsigned long ewma_read(const struct ewma *avg)
{
return avg->internal >> avg->factor;
}
```
- 此函式用於讀取當前的 EWMA 值。
- 將 `internal` 右移 `factor` 位，還原成真實的平均值。
#### 在 Linux 核心原始碼中的 EWMA 應用
##### 範例：無線網路裝置驅動程式
在 Linux 核心中，EWMA 被廣泛應用於無線網路裝置驅動程式中，特別是用於信號強度的測量與優化。例如，在 Atheros AR9000 系列無線網路設備的動態自適應噪聲與通道調整（DYNACK）功能中，使用了 EWMA 來計算和調整 ACK 超時時間。
以下是相關程式碼：
```c
static inline int ath_dynack_ewma(int old, int new)
{
if (old > 0)
return (new * (EWMA_DIV - EWMA_LEVEL) + old * EWMA_LEVEL) / EWMA_DIV;
else
return new;
}
```
- 這段程式碼用於計算 ACK 超時時間的加權移動平均值。
- `EWMA_DIV` 和 `EWMA_LEVEL` 用於控制新舊數據的權重比例。
在這些應用中，EWMA 能夠平滑信號強度的變化，從而提高無線連接的穩定性和性能。
:::spoiler
https://hackmd.io/@8gdFdQxMR8O0u3u7xLQmxA/SJsmMDdRp#測驗4
https://hackmd.io/@vax-r/linux2024-homework4#測驗四
https://hackmd.io/@tony268596/linux2024-homework4#測驗四
https://hackmd.io/@ShchangAnderson/linux2024-homework4#測驗四
https://hackmd.io/@david96514/linux2024-homework4#測驗-4
https://hackmd.io/@Kuanch/linux2024-homework4#Quiz-4---Exponentially-Weighted-Moving-Average
https://hackmd.io/@yinghuaxia/linux2024-homework4#測驗四
https://hackmd.io/@ivywang2015/linux2024-homework4#測驗四
https://hackmd.io/@marvin0102/linux2024-homework4#測驗-４
https://hackmd.io/@ivywang2015/linux2024-homework4#測驗四
https://hackmd.io/@otteryc/linux2024-homework4#測驗四
https://hackmd.io/@popo8712/linux2024-homework4#測驗四
https://hackmd.io/@jeremytsai/Homework4_quiz3_4#測驗-4--Using-bitwise-to-calculate-EWMA
https://hackmd.io/@yuu907/linux2024-homework4#測驗-4
https://hackmd.io/@sushake/linux2024-homework4#第一周測驗4
https://hackmd.io/@allenliao666/linux2024-homework4#測驗4
https://hackmd.io/@howardjchen/Sk4NDSpJC#測驗-4
https://hackmd.io/@10530417/hw4#測驗四
:::
### [quiz3-test5](https://hackmd.io/@sysprog/linux2024-quiz3#%E6%B8%AC%E9%A9%97-5)
#### 程式碼分析
```c
int ceil_ilog2(uint32_t x)
{
uint32_t r, shift;
x--;
r = (x > 0xFFFF) << 4;
x >>= r;
shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;
shift = (x > 0xF) << 2;
x >>= shift;
r |= shift;
shift = (x > 0x3) << 1;
x >>= shift;
return (r | shift | x > 1) + 1;
}
```
這段程式碼實現了一個計算給定的32位元無號整數x的對數值向上取整的函數。具體的實現方式如下：
1. `x--`: 這一步用於確保當x是2的冪時，計算結果不會錯誤。這是因為向下取整的log2對2的冪來說是正確的，但是向上取整則需要特別處理。
2. 後面的幾個條件判斷和位移操作用於逐步找到x的最高有效位的位置：
- `(x > 0xFFFF) << 4`: 如果x大於0xFFFF，則表示x的高16位中有1，`r`被設定為16。
- `(x > 0xFF) << 3`: 如果x大於0xFF，則表示x的高8位中有1，`shift`被設定為8。
- `(x > 0xF) << 2`: 如果x大於0xF，則表示x的高4位中有1，`shift`被設定為4。
- `(x > 0x3) << 1`: 如果x大於0x3，則表示x的高2位中有1，`shift`被設定為2。
3. 每次條件判斷後都會右移x相應的位數，並更新`r`的值。
4. 最後，`r | shift`得到x的最高有效位的位置，加上`x > 1`用於判斷x是否大於1，以決定是否需要進一步加1。最後再加上1，得到最終結果。
#### 改進程式碼以處理 x = 0 的狀況
當`x = 0`時，`x--`會導致x變成0xFFFFFFFF，這不是我們想要的結果。為了解決這個問題，我們可以使用`x -= !!x`來代替`x--`，這樣可以確保只有當x大於0時才會減1，並且保持無分支。
```diff
int ceil_ilog2(uint32_t x)
{
uint32_t r, shift;
+ x -= !!x;
- x--;
r = (x > 0xFFFF) << 4;
x >>= r;
shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;
shift = (x > 0xF) << 2;
x >>= shift;
r |= shift;
shift = (x > 0x3) << 1;
x >>= shift;
return (r | shift | x > 1) + 1;
}
```
#### Linux 核心中的應用
在 Linux 核心中，計算向上取整的對數值 (`ceil(log2)`) 是常見的操作，特別是在記憶體分配、資料結構尺寸計算和排程中，這樣的計算能夠有效地管理和分配系統資源。以下是幾個在 Linux 核心中應用 `ceil(log2)` 的實例：
##### 1. `roundup_pow_of_two` 宏
`roundup_pow_of_two` 是一個將數值向上取整到最近的2的冪次的函數，在許多核心模組中都有應用：
```c
#define roundup_pow_of_two(n) \
( \
__builtin_constant_p(n) ? ( \
(n == 1) ? 1 : \
(1UL << (ilog2((n) - 1) + 1)) \
) : \
__roundup_pow_of_two(n) \
)
```
這段程式碼使用 `ilog2` 函數計算數值的對數，再向上取整到最近的2的冪次。這樣的操作常用於計算記憶體分配大小，確保記憶體的有效使用和對齊。
##### 2. `ilog2` 宏和函數
`ilog2` 是一個用於計算以2為底的對數的函數，它在許多地方都有應用：
```c
static inline int ilog2(unsigned long v)
{
return (sizeof(v) <= 4) ? __ilog2_u32(v) : __ilog2_u64(v);
}
static inline int __ilog2_u32(u32 n)
{
return (n > 0xFFFF) ? \
((n > 0xFFFFFF) ? \
((n > 0xFFFFFFF) ? (28 + (n > 0xFFFFFFF7)) : (24 + (n > 0xFFFFFF07))) : \
((n > 0xFFF) ? (20 + (n > 0xFFF7)) : (16 + (n > 0xF07)))) : \
((n > 0xFF) ? \
((n > 0xFFF) ? (12 + (n > 0xFFF7)) : (8 + (n > 0xF07))) : \
((n > 0xF) ? (4 + (n > 0xF7)) : (n > 0x7)));
}
```
這些函數用於計算整數的對數值，並在需要時向上取整。在排程器、緩衝區管理和其它核心模組中都有廣泛應用。
##### 3. Linux 核心排程器中的應用
在 Linux 核心排程器中，有時需要計算任務的粒度或分配記憶體，`ceil(log2)` 的計算也經常出現。例如，計算任務指標時可能需要確保其大小為2的冪次：
```c
static inline char task_index_to_char(unsigned int state)
{
static const char state_char[] = "RSDTtXZPI";
BUILD_BUG_ON(1 + ilog2(TASK_REPORT_MAX) != sizeof(state_char) - 1);
return state_char[state];
}
```
這段程式碼用於將任務狀態轉換為字符表示，其中 `ilog2` 用於確保任務報告的最大值是2的冪次。
##### 4. 資料結構和記憶體管理中的應用
在資料結構和記憶體管理中，確保結構的大小為2的冪次可以提高效能，減少碎片。以下是一個簡單的應用例子：
```c
unsigned long memsize = roundup_pow_of_two(requested_size);
void *buffer = kmalloc(memsize, GFP_KERNEL);
```
這段程式碼首先將請求的記憶體大小向上取整到最近的2的冪次，然後分配相應大小的記憶體。這樣可以確保記憶體的有效使用和對齊，提高記憶體管理的效能。
#### ref
:::spoiler 參考學員
https://hackmd.io/@ShchangAnderson/linux2024-homework4#測驗五
https://hackmd.io/@david96514/linux2024-homework4#測驗-5
https://hackmd.io/@david96514/linux2024-homework4#測驗-5
https://hackmd.io/@NdB0NahsRSSnwZagYYcL6g/linux2024-homework4#測驗五
https://hackmd.io/@Henry0922/linux2024-homework4#Linux-核心所應用的-ceil_log2
https://hackmd.io/@jimmylu0303/linux2024-homework4#測驗五
https://hackmd.io/@vax-r/linux2024-homework4#測驗五
https://hackmd.io/@tony268596/linux2024-homework4#測驗五
https://hackmd.io/@Kuanch/linux2024-homework4#Quiz-5---Bitwise-Ceiling-log
https://hackmd.io/@Ackerman/H1OvNOx1A#測驗-5
https://hackmd.io/@marvin0102/linux2024-homework4#測驗-5：
https://hackmd.io/@jeremytsai/Homework4_quiz3_4#測驗-5--Test-3-Extension
https://hackmd.io/@popo8712/linux2024-homework4#測驗五
https://hackmd.io/@yinghuaxia/linux2024-homework4#測驗五
https://hackmd.io/@yuu907/linux2024-homework4#測驗-5
https://hackmd.io/@sushake/linux2024-homework4#第一周測驗5
https://hackmd.io/@ivywang2015/linux2024-homework4#測驗五
https://hackmd.io/@ivywang2015/linux2024-homework4#測驗五
https://hackmd.io/@allenliao666/linux2024-homework4#測驗5
https://hackmd.io/@otteryc/linux2024-homework4#測驗五
https://hackmd.io/@howardjchen/Sk4NDSpJC#測驗-5
https://hackmd.io/@10530417/hw4#測驗五
:::
### [第 4 週測驗題 1](https://hackmd.io/@sysprog/linux2024-quiz4#測驗-1)
:::success
延伸問題：
1. 參照[《Hacker's Delight》](https://en.wikipedia.org/wiki/Hacker%27s_Delight)和 [CS:APP 第二章](https://hackmd.io/@sysprog/CSAPP-ch2)，解釋上述程式碼運作原理。
2. 不依賴 popcount，嘗試以上述歸納的規則，針對 [LeetCode 477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/) 撰寫出更高效的程式碼。
:::
#### Population count 程式碼理解
**Population count** (popcount) 或稱 **sideways sum**，是計算數值的二進位表示中，有多少位元是 1 的數量。在許多應用中非常有用，例如計算 0-1 稀疏矩陣或 bit array 中非 0 元素的數量，或計算兩個字串的 Hamming distance。以下提供兩個 C 程式實作範例。
##### 簡單實作
```c
unsigned popcount_naive(unsigned v) {
unsigned n = 0;
while (v) {
v &= (v - 1);
n++;
}
return n;
}
```
此函式利用不斷清除 LSB (least significant bit) 直到輸入的數值 v 為 0。`v &= (v - 1)` 的作用是將 LSB 設為 0 (reset LSB)。例如，假設輸入數值為 20:
```
0001 0100 # 20
0001 0011 # 20 - 1
0001 0000 # 20 & (20 - 1)
```
##### 高效實作
```c
unsigned popcount_branchless(unsigned v) {
unsigned n;
n = (v >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;
v = (v + (v >> 4)) & 0x0F0F0F0F;
v *= 0x01010101;
return v >> 24;
}
```
此實作以常數時間複雜度計算 popcount。程式碼的關鍵在於將每 4 位元 (nibble) 為一個單位計算 1 的個數，並利用位元運算優化計算效率。
#### Hamming Distance 的計算
Hamming Distance 是指兩個數字在二進位表示中的不同位元的數量。例如，數字 3 (0001) 和數字 4 (0100) 的 Hamming distance 為 2。以下提供一個 C 程式實作範例，利用 `__builtin_popcount` 計算兩個數字的 Hamming distance：
```c
int hammingDistance(int x, int y) {
return __builtin_popcount(x ^ y);
}
```
`x ^ y` 會得到一個數字，其二進位表示中 1 的位置就是 x 和 y 不同的位置，然後利用 `__builtin_popcount` 計算這些 1 的數量。
#### 改進的 Total Hamming Distance 程式碼
LeetCode 477 的 Total Hamming Distance 問題需要計算一個數組中所有數字間的總 Hamming 距離。以下提供更高效的解法：
```c
int totalHammingDistance(int* nums, int numsSize) {
int total = 0;
for (int i = 0; i < 32; i++) {
int count = 0;
for (int j = 0; j < numsSize; j++) {
count += (nums[j] >> i) & 1;
}
total += count * (numsSize - count);
}
return total;
}
```
此解法的關鍵在於逐位元計算每個位置上的 1 的數量，並利用這些資訊計算每個位元位置上的 Hamming distance，最後加總所有位元位置的 Hamming distance。這樣的時間複雜度為 $O(n)$，顯著提升效率。
#### ref
:::spoiler 參考學員
https://hackmd.io/@vax-r/linux2024-homework4#測驗一1
https://hackmd.io/@tony268596/linux2024-homework4#測驗一1
https://hackmd.io/@david96514/linux2024-homework4#測驗-11
https://hackmd.io/@Kuanch/linux2024-homework4#Quiz-1---Bitwise-Hamming-Distance
https://hackmd.io/@yinghuaxia/linux2024-homework4#第四週測驗
https://hackmd.io/@Ackerman/H1OvNOx1A#測驗-1
https://hackmd.io/@marvin0102/linux2024-homework4#測驗-1
https://hackmd.io/@jeremytsai/Homework4_quiz3_4#測驗-1--Total-Hamming-Distance
https://hackmd.io/@NdB0NahsRSSnwZagYYcL6g/linux2024-homework4#測驗一
https://hackmd.io/@popo8712/linux2024-homework4#測驗一1
https://hackmd.io/@Henry0922/linux2024-homework4#測驗一
https://hackmd.io/@LindaTing/linux2024-homework4#測驗-11
https://hackmd.io/@jimmylu0303/linux2024-homework4#測驗一1
https://hackmd.io/@yuu907/linux2024-homework4#測驗-11
https://hackmd.io/@Mvkk2ohIQ02-teTNbvLJ9g/rJgkuw3R6#測驗一1
:::
### [第 4 週測驗題 2](https://hackmd.io/@sysprog/linux2024-quiz4#測驗-2)
:::success
延伸問題：
1. 參照[《Hacker's Delight》](https://en.wikipedia.org/wiki/Hacker%27s_Delight)和 [CS:APP 第二章](https://hackmd.io/@sysprog/CSAPP-ch2)，解釋上述程式碼運作原理。
2. 將上述手法應用於[第三次作業中](https://hackmd.io/@sysprog/linux2024-ttt)，追求更有效的賽局判定機制。
:::
#### 1. 解釋上述程式碼運作原理
要計算一個數字除以3的餘數而不使用除法運算，可以利用位元操作來完成。
假設數字 $n$ 的二進位表示為 $b_{n-1}b_{n-2}...b_1b_0$，其中 $b_i$ 為第 $i$ 位的位元值。根據以下性質：
$$
2^k \equiv \begin{cases}
1 \pmod{3}, & \text{if } k \text{ is even} \\
-1 \pmod{3}, & \text{if } k \text{ is odd}
\end{cases}
$$
這表示當 $k$ 為偶數時，$2^k$ 模 3 的結果為 1；當 $k$ 為奇數時，結果為 -1。因此，數字 $n$ 模 3 的結果可以表達為：
$$
n \equiv \sum_{i=0}^{n-1} b_i \cdot (-1)^i \pmod{3}
$$
利用這個性質，我們可以將 $n$ 表示為位元的總和，其中奇數位的位元乘以 -1，偶數位的位元乘以 1。這可以使用 `popcount` 函數來計算：
```c
n = popcount(n & 0x55555555) - popcount(n & 0xAAAAAAAA);
```
其中，`0x55555555` 是 `0b01010101010101010101010101010101`，選取偶數位的位元；`0xAAAAAAAA` 是 `0b10101010101010101010101010101010`，選取奇數位的位元。
再利用以下定理進一步化簡：
$$
popcount(x \& \overline{m}) - popcount(x \& m) = popcount(x \oplus m) - popcount(m)
$$
所以，可以將公式改寫為：
```c
n = popcount(n ^ 0xAAAAAAAA) - 16;
```
這裡減去 16 是因為 `popcount(0xAAAAAAAA)` 為 16。
##### 範例程式碼
```c
int mod3(unsigned n) {
n = popcount(n ^ 0xAAAAAAAA) + 23; // n = popcount(n ^ 0xAAAAAAAA) - 16 + 39;
n = popcount(n ^ 0x2A) - 3;
return n + ((int)n >> 31 & 3); // 避免 n 為負數
}
```
為了避免 n 變為負數，這裡加上了一個足夠大的 3 的倍數，例如加 39。
另一種方法是使用查表法：
```c
int mod3(unsigned n) {
static char table[33] = {2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1};
n = popcount(n ^ 0xAAAAAAAA);
return table[n];
}
```
#### 井字遊戲程式碼解說
在這個井字遊戲中，每個位置的狀態都用 `move_masks` 陣列來表示。每個元素對應於一個位置，表示在該位置下棋後，影響的所有可能的直線、橫線或對角線。
```c
static const uint32_t move_masks[9] = {
0x40040040, 0x20004000, 0x10000404, 0x04020000, 0x02002022,
0x01000200, 0x00410001, 0x00201000, 0x00100110,
};
```
例如，當在左上角（位置 0）下棋時，影響的連線為第一橫線、第一直線和第一對角線，其二進位表示為 `0x40040040`。
判斷是否勝利的條件是玩家的棋盤狀態中某一條連線的值為 `0x7`，即 `0111`。這可以通過以下程式碼來判斷：
```c
static inline uint32_t is_win(uint32_t player_board) {
return (player_board + 0x11111111) & 0x88888888;
}
```
這裡，`0x11111111` 將每 4 位元加 1，如果有一條連線滿足 `0111`，則會產生進位，結果為 `1000`。
##### 範例程式碼
```c
#include <stdint.h>
#include <stdio.h>
#include <time.h>
static const uint32_t move_masks[9] = {
0x40040040, 0x20004000, 0x10000404, 0x04020000, 0x02002022,
0x01000200, 0x00410001, 0x00201000, 0x00100110,
};
static inline uint32_t is_win(uint32_t player_board) {
return (player_board + 0x11111111) & 0x88888888;
}
static inline int mod3(unsigned n) {
static char table[33] = {2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1};
n = __builtin_popcount(n ^ 0xAAAAAAAA);
return table[n];
}
static inline int mod7(uint32_t x) {
x = (x >> 15) + (x & UINT32_C(0x7FFF));
return (int)((x * UINT32_C(0x24924925)) >> 29);
}
static inline uint32_t fastmod(uint32_t x, uint32_t n) {
switch (n) {
case 2:
return x & 1;
case 3:
return mod3(x);
case 4:
return x & 3;
case 5:
return x % 5;
case 6:
return x % 6;
case 7:
return mod7(x);
case 8:
return x & 7;
case 9:
return x % 9;
default:
return 0;
}
}
uint32_t xorshift32() {
static uint32_t x = 0x12345678;
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
return x;
}
uint32_t play_random_game(uint32_t player, uint32_t *moves) {
uint32_t boards[2] = {0, 0};
uint32_t available_moves[9] = {0, 1, 2, 3, 4, 5, 6, 7, 8};
for (uint32_t n_moves = 9; n_moves > 0; n_moves--) {
uint32_t board = boards[player - 1];
uint32_t i = fastmod(xorshift32(), n_moves);
uint32_t move = available_moves[i];
available_moves[i] = available_moves[n_moves - 1];
board |= move_masks[move];
*moves++ = move;
if (is_win(board))
return player;
boards[player - 1] = board;
player = 3 - player;
}
*moves++ = -1;
return 0;
}
int main() {
for (int k = 0; k < 10; k++) {
double start_time = clock() / (double)CLOCKS_PER_SEC;
uint32_t wins[3] = {0, 0, 0};
uint32_t wins_by_move[9] = {0};
int n_games = 1000 * 1000;
for (int i = 0; i < n_games; i++) {
uint32_t player = 1;
uint32_t moves[10] = {0};
uint32_t winner = play_random_game(player, moves);
wins[winner]++;
if (winner == player)
wins_by_move[moves[0]]++;
}
double delta_time = clock() / (double)CLOCKS_PER_SEC - start_time;
printf("Win probability for first move with random agents:\n");
for (int y = 0; y < 3; y++)
{
for (int x = 0; x < 3; x++)
printf("%.3f ", wins_by_move[x + y * 3] * 1.0 / wins[1]);
printf("\n");
}
printf("Player 1 won %u times\n", wins[1]);
printf("Player 2 won %u times\n", wins[2]);
printf("%u ties\n", wins[0]);
printf("%f seconds\n", delta_time);
printf("%f million games/sec\n", n_games * 1e-6 / delta_time);
printf("\n");
}
return 0;
}
```
#### ref
:::spoiler 參考學員
https://hackmd.io/@Henry0922/linux2024-homework4#測驗二1
https://hackmd.io/@Mvkk2ohIQ02-teTNbvLJ9g/rJgkuw3R6#測驗二1
https://hackmd.io/@vax-r/linux2024-homework4#測驗二1
https://hackmd.io/@ShchangAnderson/linux2024-homework4#測驗二1
https://hackmd.io/@Kuanch/linux2024-homework4#Quiz-2---Bitwise-Modular-Arithmetic
https://hackmd.io/@yinghuaxia/linux2024-homework4#測驗二1
https://hackmd.io/@marvin0102/linux2024-homework4#測驗-2
https://hackmd.io/@jeremytsai/Homework4_quiz3_4#測驗2--Remainder-by-Summing-digits
https://hackmd.io/@popo8712/linux2024-homework4#測驗二1
https://hackmd.io/@howardjchen/Sk4NDSpJC#測驗-2
https://hackmd.io/@LindaTing/linux2024-homework4#測驗-21
https://hackmd.io/@david96514/linux2024-homework4#測驗-21
https://hackmd.io/@yuu907/linux2024-homework4#測驗-21
:::
### [第 4 週測驗題 3](https://hackmd.io/@sysprog/linux2024-quiz4#測驗-3)
### 測驗 3 解答
#### 程式碼運作原理
這個程式碼主要是實作一個類似於 AVL 樹和紅黑樹的自平衡二元搜尋樹（BST），稱為 XTree。XTree 結合了 AVL 樹和紅黑樹的一些特性，利用 `hint` 來評估是否需要進行旋轉來保持樹的平衡。
以下是程式碼中的主要操作和其運作原理：
1. **`xt_create`**:
- 初始化一個新的 XTree，並設置比較函式 `cmp` 以及節點的創建和刪除函式。
2. **`xt_destroy`**:
- 遞迴地刪除樹中的每個節點。
3. **`xt_first` 和 `xt_last`**:
- 找到樹中最左邊（最小值）和最右邊（最大值）的節點。
4. **`xt_rotate_left` 和 `xt_rotate_right`**:
- 對樹進行左旋和右旋操作，來保持樹的平衡。
5. **`xt_balance`**:
- 計算節點 `n` 的左右子樹的高度差。
6. **`xt_update`**:
- 更新節點 `n` 的 `hint` 值，並檢查是否需要進行旋轉來保持樹的平衡。
7. **`xt_insert`**:
- 將新節點插入樹中，並更新樹的平衡狀態。
8. **`xt_remove`**:
- 將節點從樹中移除，並更新樹的平衡狀態。
#### 可改進之處
1. **旋轉策略**：
- 目前 XTree 的旋轉策略只有單一方向的旋轉，對於某些情況下的平衡效果不佳。可以引入雙旋轉策略（如 AVL 樹中的 LR 和 RL 旋轉）來改進。
2. **平衡檢查**：
- 平衡檢查可以更嚴格一些，特別是在插入和刪除節點後，應該確保整棵樹的平衡。
3. **性能優化**：
- 可以考慮引入更高效的旋轉和更新策略，來減少不必要的操作，提升整體性能。
#### 改進實作
以下是改進的 XTree 實作，加入了雙旋轉策略：
```c
static inline void xt_rotate_left(struct xt_node *n) {
struct xt_node *l = xt_left(n), *p = xt_parent(n);
xt_parent(l) = xt_parent(n);
xt_left(n) = xt_right(l);
if (xt_left(n))
xt_parent(xt_left(n)) = n;
xt_parent(n) = l;
xt_right(l) = n;
if (p && xt_left(p) == n)
xt_left(p) = l;
else if (p)
xt_right(p) = l;
}
static inline void xt_rotate_right(struct xt_node *n) {
struct xt_node *r = xt_right(n), *p = xt_parent(n);
xt_parent(r) = xt_parent(n);
xt_right(n) = xt_left(r);
if (xt_right(n))
xt_parent(xt_right(n)) = n;
xt_parent(n) = r;
xt_left(r) = n;
if (p && xt_left(p) == n)
xt_left(p) = r;
else if (p)
xt_right(p) = r;
}
static inline void xt_update(struct xt_node **root, struct xt_node *n) {
while (n) {
int b = xt_balance(n);
if (b < -1) {
if (xt_balance(xt_right(n)) > 0)
xt_rotate_left(xt_right(n));
if (n == *root)
*root = xt_right(n);
xt_rotate_right(n);
} else if (b > 1) {
if (xt_balance(xt_left(n)) < 0)
xt_rotate_right(xt_left(n));
if (n == *root)
*root = xt_left(n);
xt_rotate_left(n);
}
int hint = xt_max_hint(n);
if (n->hint == hint)
break;
n->hint = hint;
n = xt_parent(n);
}
}
```
#### ref
:::spoiler 參考學員
https://hackmd.io/@vax-r/linux2024-homework4#測驗三1
https://hackmd.io/@allenliao666/linux2024-homework4#測驗31
https://hackmd.io/@Henry0922/linux2024-homework4#測驗一
https://hackmd.io/@marvin0102/linux2024-homework4#測驗-31
https://hackmd.io/@10530417/hw4#第四週測驗
https://hackmd.io/@yuu907/linux2024-homework4#測驗-31
https://hackmd.io/@jeremytsai/Homework4_quiz3_4#測驗-3--XTree
https://hackmd.io/@popo8712/linux2024-homework4#測驗三1
https://hackmd.io/@Mvkk2ohIQ02-teTNbvLJ9g/rJgkuw3R6#測驗三1
:::
Sign in with Wallet
Connect another wallet