# 2022q1 Homework5 (quiz6)
contributed by < `Kevin-Shih` >
> [測驗題目 quiz6](https://hackmd.io/@sysprog/linux2022-quiz6)
> [final project github](https://github.com/Kevin-Shih/Linux2022q1-final-project)
## 問題描述
〈[UNIX 作業系統 fork/exec 系統呼叫的前世今生](https://hackmd.io/@sysprog/unix-fork-exec)〉提到 [clone](https://man7.org/linux/man-pages/man2/clone.2.html) 系統呼叫，搭配閱讀〈[Implementing a Thread Library on Linux](https://www.evanjones.ca/software/threading.html)〉，嘗試撰寫一套使用者層級的執行緒函式庫，程式碼可見: [readers.c](https://gist.github.com/jserv/f1c55b97ae6cb0ae8f4945203c2b12c9)
### 運作原理與解題
:::danger
逐行解釋程式碼運作前，應當描述 Linux NPTL 和相關系統呼叫的原理。
:notes: jserv
:::
**儲存執行緒資料的節點及 TCB**
```c
typedef struct __node {
unsigned long int tid, tid_copy;
void *ret_val;
struct __node *next;
funcargs_t *fa;
} node_t;
typedef struct {
node_t *head, *tail;
} list_t;
```
`node_t` 用來存該執行緒的 tid，回傳值 (`ret_val` ) 及所執行的函式 (`fa`)，`fa` 包含函式的輸入參數。 TCB 則以單向的鏈結串列建構。
**鎖定指定的 spinlock object**
```c
static inline int spin_acquire(spin_t *l)
{
int out;
volatile int *lck = &(l->lock);
asm("whileloop:"
"xchg %%al, (%1);" // exchange src and dest val
/* bitwise AND between src and dest.
* If they're both zero, the zero flag is set
*/
"test %%al,%%al;"
"jne whileloop;" // exit when zero flag is set
: "=r"(out) // output
: "r"(lck)); // input
return 0;
}
```
- `%%al` : 相當於 `rax` 的 lowest 8 bits
- `%1` : input, 相當於 `rax` (見底下組合語言指令列表)
對應的組合語言: (AT&T 語法)
```c
movq -8(%rbp), %rax //input, move 64bits from `lck` to rax
whileloop:
xchg %al, (%rax); //rax is addr to l->lock so swap l-lock val and al val
test %al,%al;
jne whileloop;
movl %eax, -12(%rbp) //output, move 32bits from eax to `out`
```
最後的結果 `xchg` 相當於 `l->lock = &(l->lock) << (64-8) >> (64-8)` 因為 `%al` 是 input lck 的低位 8 bits，如果 `l->lock` 是 0 (未被 lock 的狀態)換完一次就會跳出迴圈。 而 spin_release 則對應釋放 lock，將 `l->lock`, `l->locker` 設為 0。 `spin lock` 用來保護後續 thread create, join, exit 等 critical section，確保對 node 中的資料操作時不會被中斷。
`mutex_t` 類別的 init, acquire, release 大致與 `spin_t` 相同，但在 acquire, release 多了一道 `SYS_futex` 系統呼叫。
```c
// mutex_acquire function readers.c L109
syscall(SYS_futex, m, FUTEX_WAIT, 1, NULL, NULL, 0);
// mutex_release function readers.c L125
syscall(SYS_futex, m, FUTEX_WAKE, 1, NULL, NULL, 0);
```
根據 man page `FUTEX_WAIT` 對應的行為會檢驗 uaddr (即 `m`) 指向的 futex word 值是否與 val (即 `1`) 相同則進入 sleep 並等待相同 futex word 上的 `FUTEX_WAKE` 指令，當值不同則 system call fails immediately 並產生錯誤訊號 `EAGAIN` 。 `FUTEX_WAKE` 會喚醒 uaddr (即 `m`) 所指向的 futex word，val (即 `1`) 可以指定喚醒的 waiter 數量 (`1` 或 `INT_MAX`)，需要注意的是喚醒單個 waiter 時並不保證喚醒的順序。 更詳細的 `FUTEX_WAIT`, `FUTEX_WAKE` 行為可以查閱下方引文中的 man page 連結。
> `SYS_futex`:
> ```c
> long syscall(SYS_futex, uint32_t *uaddr, int futex_op, uint32_t val,
> const struct timespec *timeout, /* or: uint32_t val2 */
> uint32_t *uaddr2, uint32_t val3);
> ```
> futex - fast user-space locking. The futex() system call provides a method for waiting until a
> certain condition becomes true.
> --man [futex](https://man7.org/linux/man-pages/man2/futex.2.html)
**clone one-to-one 所用的 flags**
```c
#define CLONE_FLAGS \
(CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND | CLONE_THREAD | \
CLONE_SYSVSEM | CLONE_PARENT_SETTID | CLONE_CHILD_CLEARTID)
```
- 當 `CLONE_VM` 被設定時，呼叫端行程及子行程會共用記憶體空間，使得它們的記憶體存取對二者均為可見。
> If the CLONE_VM flag is specified and the CLONE_VFORK flag is not specified, then any alternate signal stack that was established by sigaltstack(2) is cleared in the child process.
- 當 `CLONE_FS` 被設定時，呼叫端行程及子行程會共用檔案系統。
> This includes the root of the filesystem, the current working directory, and the umask.
- 當 `CLONE_FILES` 被設定時，呼叫端行程及子行程會共用 fd 表格，當其中一者關閉 fd 時另一者也會受影響。
- 當 `CLONE_SIGHAND` 被設定時，呼叫端行程及子行程會共用 signal handler，兩者會共用對某個 signal 的 action，但 signal mask 及 signal 本身仍是獨立的。
- 當 `CLONE_THREAD` 被設定時，呼叫端行程及子行程放在同一個 thread group (所以有相同的 TGID)，但也擁有獨立的 TID，以供區別。
- 當 `CLONE_SYSVSEM` 被設定時，呼叫端行程及子行程會共用 semadj list。
> A semaphore adjustment (semadj) value is a per-process, per-semaphore integer that is the negated sum of all operations performed on a semaphore specifying the SEM_UNDO flag. When a process specified the SEM_UNDO flag terminates, each of its per-semaphore semadj values is added to the corresponding semaphore, thus undoing the effect of that process's operations on the semaphore.
- 當 `CLONE_PARENT_SETTID` 被設定時，child TID 會存入由 parent_tid 參數指向的位置
> Stored in the parent's memory. The store operation completes before the clone call returns control to user space.
- 當 `CLONE_CHILD_CLEARTID` 被設定時，當子行程一旦執行 exit，則清除由 child_tid 參數指向的 child TID (in child memory)，並接著喚醒該 address 對應的 futex。
更詳細的說明可見 [clone(2)](https://man7.org/linux/man-pages/man2/clone.2.html)
**建立新的 thread**
```c
/**
* @brief Create a One One mapped thread
* @param t Reference to the thread
* @param routine Function associated with the thread
* @param arg Arguments to the routine
*/
int thread_create(thread_t *t, void *routine, void *arg)
{
// lock it till thread created or failed to create
spin_acquire(&global_lock);
...
// insert the node to the TCB
node_t *node = list_insert(&tid_list, 0);
if (!node) {...}
// arg for wrap
funcargs_t *fa = malloc(sizeof(funcargs_t));
if(!fa) {...}
fa->f = routine;
fa->arg = arg;
// stack for child
void *thread_stack = alloc_stack(STACK_SZ, GUARD_SZ);
if (!thread_stack) {
perror("thread create");
spin_release(&global_lock);
free(fa);
return errno;
}
fa->stack = thread_stack;
thread_t tid = clone(wrap, (char *) thread_stack + STACK_SZ + GUARD_SZ,
CLONE_FLAGS, fa, &(node->tid), NULL, &(node->tid));
node->tid_copy = tid;
node->fa = fa;
// clone failed
if (tid == -1) {...}
*t = tid; // set *t to child tid
spin_release(&global_lock);
return 0;
}
```
該函式會將對應的 kernel level thread 的 tid 存入 thread_t，而該 kernel thread 負責執行傳入的 routine founction，routine 及其 arg 會先包入 `funcargs_t` 類別(即變數 fa) 後作為參數交由 clone 時的 wrap founction 執行。 這邊的 wrap 函式協助包裝 routine 並為該 thread 設定所需的 signal handler 並在 routine return 後結束該 thread (呼叫 `thread_exit`) 等功能。
`thread_stack + STACK_SZ + GUARD_SZ` 是指向分配給 child stack 的最上方的記憶體位置。 因為設定 `CLONE_VM` 使兩者共用 memory space 故 parent_tid 與 child_tid 均指向 `&(node->tid)` ，當 child 建立時會將其 tid 存入，結束時則會清除 (歸零)，並喚醒對應的 futex。 (因為 `CLONE_PARENT_SETTID` 及 `CLONE_CHILD_CLEARTID` 的 flags)。
**thread join**
```c
/**
* @brief Function to wait for a specific thread to terminate
* @param t TID of the thread to wait for
*/
int thread_join(thread_t t, void **retval)
{
spin_acquire(&global_lock);
void *addr = get_tid_addr(&tid_list, t);
if (!addr) {
spin_release(&global_lock);
return ESRCH;
}
if (*((pid_t *) addr) == 0) {
spin_release(&global_lock);
return EINVAL;
}
int ret = 0;
while (*((pid_t *) addr) == t) {
spin_release(&global_lock);
ret = syscall(SYS_futex, addr, FUTEX_WAIT, t, NULL, NULL, 0);
spin_acquire(&global_lock);
}
syscall(SYS_futex, addr, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
if (retval)
*retval = get_node_from_tid(&tid_list, t)->ret_val;
spin_release(&global_lock);
return ret;
}
```
`while` 迴圈內的 FUTEX_WAIT 會在 addr 與 t 相等時進入睡眠，即該等待被 join 的 thread 仍在執行時 `thread_join` 就會睡眠直到該 thread 結束，`CLONE_CHILD_CLEARTID` flag 觸發清空 addr 及 FUTEX_WAKE，`thread_join` 才會繼續接收 return value 並結束。
**thread exit**
```c
void thread_exit(void *ret)
{
spin_acquire(&global_lock);
void *addr = get_tid_addr(&tid_list, gettid());
if (!addr) {...}
if (ret) {
node_t *node = get_node_from_tid(&tid_list, gettid());
node->ret_val = ret;
}
/**
* after child thread killed, `CLONE_CHILD_CLEARTID` flag will
* call another FUTEX_WAKE, won't it?
*/
syscall(SYS_futex, addr, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
spin_release(&global_lock);
kill(SIGINT, gettid());
}
```
在 child thread 執行 wrap function 到最後時會呼叫 `thread_exit`，將回傳值放到 `thread_join` 可以存取的地方，並終止該 thread。
---
# final project: 改進 quiz6(A)
## 作業環境
**硬體**
- CPU: Intel® Core™ i5-7300HQ CPU @ 2.50GHz × 4
:::spoiler lscpu
```shell
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i5-7300HQ CPU @ 2.50GHz
Stepping: 9
CPU MHz: 2500.000
CPU max MHz: 3500.0000
CPU min MHz: 800.0000
BogoMIPS: 4999.90
Virtualization: VT-x
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 6 MiB
NUMA node0 CPU(s): 0-3
```
:::
- RAM: 4GiB DDR4 @ 2133MHz x 2 (Dual channel)
:::spoiler dmidecode -t memory
```shell
$ sudo dmidecode -t memory
# dmidecode 3.2
Handle 0x003F, DMI type 17, 40 bytes
Memory Device
Array Handle: 0x003E
Error Information Handle: Not Provided
Total Width: 64 bits
Data Width: 64 bits
Size: 4096 MB
Form Factor: SODIMM
Set: None
Locator: ChannelA-DIMM0
Bank Locator: BANK 0
Type: DDR4
Type Detail: Synchronous
Speed: 2133 MT/s
Manufacturer: 859B
Part Number: CT4G4SFS8213.C8FBR2
Rank: 1
Configured Memory Speed: 2133 MT/s
Handle 0x0040, DMI type 17, 40 bytes
Memory Device
Array Handle: 0x003E
Error Information Handle: Not Provided
Total Width: 64 bits
Data Width: 64 bits
Size: 4096 MB
Form Factor: SODIMM
Set: None
Locator: ChannelB-DIMM0
Bank Locator: BANK 2
Type: DDR4
Type Detail: Synchronous
Speed: 2133 MT/s
Manufacturer: SK Hynix
Part Number: HMA451S6AFR8N-TF
Rank: 1
Configured Memory Speed: 2133 MT/s
```
:::
**作業系統**
- OS: Ubuntu 20.04.4 LTS (Focal Fossa)
- Linux kernel: 5.13.0-44-generic
```shell
$ uname -a
Linux Shih-MSI 5.13.0-44-generic #49~20.04.1-Ubuntu SMP Wed May 18 18:44:28 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux
```
**編譯器**
- gcc 9.4
- g++ 9.4 (目前因重現實驗時遭遇的問題改為 g++ 7.5)
- GO 1.13.8
- nodejs v10.19.0
---
## 重現 [uThreads](https://github.com/samanbarghi/uThreads) 的實驗 (throughput)
首先使用 [wrk](https://github.com/wg/wrk) 嘗試，過程中使用的命令依照 [httpbenchmarks](https://github.com/samanbarghi/httpbenchmarks)。 然而對於 uThreads webserver 卻產生了異常的結果，wrk 回報的 Requests/sec 為 0。
```shell
// first terminal
$ sudo taskset -c 2,3 ./bin/webserver 2
// second terminal
$ sudo taskset -c 0,1 ./wrk -d 15s -t 2 -c 200 https://127.0.0.1:8800
Running 15s test @ https://127.0.0.1:8800
2 threads and 200 connections
Thread Stats Avg Stdev Max +/- Stdev
Latency 0.00us 0.00us 0.00us -nan%
Req/Sec 0.00 0.00 0.00 -nan%
0 requests in 15.03s, 0.00B read
Requests/sec: 0.00
Transfer/sec: 0.00B
```
與老師聯繫後嘗試改用 khttpd 中附的 [htstress](https://github.com/arut/htstress) 嘗試，仍然無法正常得到結果。
```shell
// first terminal
$ sudo taskset -c 2,3 ./bin/webserver 2
// second terminal
$ ./htstress -n 1000 -c 100 -t 1 http://localhost:8800
// over 1 minute no responce, so I press `Ctrl + C`
^Cepoll_wait: Interrupted system call
```
而在試著使用 htstress 中的 debug 時，我注意到儘管 `uThreads webserver` 仍在運行，但從未得到 server 的回應。
```shell
./htstress -d http://localhost:8800
[Press Ctrl-C to finish]
GET / HTTP/1.0
Host: localhost
```
除了嘗試對 `uThreads webserver` benchmark 外，也嘗試對`fasthttp`, `cppsp` 測試，意外發現 `cppsp` 也無法正常得到測試結果，僅有 `fasthttp` 可以在 htstress 上正確的測試。
(但當用 `./htstress -d` 對 `cppsp` 測試時是有回應 `Hello Wrold!` 的，但只有一次)
:::danger
htstress 無法正常測試 `uThreads webserver`, `cppsp`，僅能以 `Ctrl + C` 終止。
(目前改變 g++ 版本至 7.5 後測試正常)
:::
**嘗試 gdb 以了解發生問題的環節在哪**
first try： 第 226 行後，先 `./htstress -d` 再執行 227 行，可以 accept (`*cconn` 有被指派 `pd`, `fd`)，但未收到回應()。
```
(gdb) r 2
Starting program: /home/user/Senior/linux2022/project/uThreads/bin/webserver 2
...
Thread 1 "webserver" hit Breakpoint 1, main (argc=<optimized out>, argv=<optimized out>) at test/webserver.cpp:226
226 Connection* cconn = sconn->accept((struct sockaddr*)nullptr, nullptr);
(gdb) display *sconn
1: *sconn = {pd = 0x5555555744b0, fd = 4}
(gdb) display *cconn
2: *cconn = <error: value has been optimized out>
// 這邊先執行 `./htstress -d http://localhost:8800` 可以 accept 到，但最後仍沒有收到回應
(gdb) n
227 uThread::create()->start(defaultCluster, (void*)handle_connection, (void*)cconn);
1: *sconn = {pd = 0x5555555744b0, fd = 4}
2: *cconn = {pd = 0x5555555744e0, fd = 5}
(gdb) n
Thread 1 "webserver" hit Breakpoint 1, main (argc=<optimized out>, argv=<optimized out>) at test/webserver.cpp:226
226 Connection* cconn = sconn->accept((struct sockaddr*)nullptr, nullptr);
1: *sconn = {pd = 0x5555555744b0, fd = 4}
2: *cconn = <error: value has been optimized out>
// 已經進到下一次的迴圈了，但 htstress 仍沒有收到回應
```
second try： 第 226 行後，先執行 227 行再嘗試 `./htstress -d`，無法正常 accept，也未收到回應。
```
(gdb) r 2
Starting program: /home/user/Senior/linux2022/project/uThreads/bin/webserver 2
...
Thread 1 "webserver" hit Breakpoint 1, main (argc=<optimized out>, argv=<optimized out>) at test/webserver.cpp:226
226 Connection* cconn = sconn->accept((struct sockaddr*)nullptr, nullptr);
(gdb) display *sconn
1: *sconn = {pd = 0x5555555744b0, fd = 4}
(gdb) display *cconn
2: *cconn = <error: value has been optimized out>
// 若這邊先不執行 `./htstress -d http://localhost:8800` 則會卡在 `n`
(gdb) n
// 此時執行 `./htstress -d http://localhost:8800` 但不會正確進到下一步
^C
Thread 1 "webserver" received signal SIGINT, Interrupt.
0x00007ffff7fa73d0 in kThread::postSwitchFunc (nextuThread=0x555555573e80, args=0x5555555744b0) at src/runtime/kThread.cpp:198
198 nextuThread->state = uThread::State::RUNNING;
1: *sconn = {pd = 0x5555555744b0, fd = 4}
(gdb) n
197 ck->currentUT = nextuThread;
1: *sconn = {pd = 0x5555555744b0, fd = 4}
```
也改用在其他同學共筆中見過的 ab 進行測試，測試結果同樣異常。
```shell
$ ab -n 100 -c 10 -k http://localhost:8800/
...
Benchmarking localhost (be patient)...apr_pollset_poll: The timeout specified has expired (70007)
```
同樣是等到 timeout 仍無回應。
### 改變 g++ 版本
經過在 ubuntu 18.04 以 g++ 7.5.0 編譯成功過得經驗，懷疑可能是 compiler 版本導致不能正常運行，嘗試降至 g++ 7.5.0 編譯。
```shell
$ sudo update-alternatives --install /usr/bin/g++ g++ /usr/bin/g++-7 100
$ g++ --version
g++ (Ubuntu 7.5.0-6ubuntu2) 7.5.0
```
編譯完後的執行結果：
```shell
$ wrk -d 15s -t 1 -c 200 http://localhost:8800
Running 15s test @ http://localhost:8800
1 threads and 200 connections
Thread Stats Avg Stdev Max +/- Stdev
Latency 849.23us 418.16us 9.88ms 90.49%
Req/Sec 129.34k 8.38k 136.25k 88.67%
1929955 requests in 15.00s, 242.95MB read
Requests/sec: 128626.03
Transfer/sec: 16.19MB
```
看來確實是 g++ 版本導致的問題，但實際的原因仍待查證。
### 抑制編譯器最佳化
修改 Makefile 抑制編譯器的最佳化，測試再此情況下以 g++ 9.4.0 編譯是否可以正確執行。
原先的 Makefile 有三處帶有 `-O` 選項，分別對應 uThreads、測試用 sample code 及 linker。 其中 linker 維持 `-O1` 不變，但將其他兩個改為 `-O0` 以抑制編譯器最佳化。
```diff
// uThreads 主體
@@ -18 +18 @@
-CXXFLAGS := -O3 -g -m64 -fpermissive -mtls-direct-seg-refs -fno-extern-tls-init -pthread -DNDEBUG -DNPOLLNONBLOCKING
+CXXFLAGS := -O0 -g -m64 -fpermissive -mtls-direct-seg-refs -fno-extern-tls-init -pthread -DNDEBUG -DNPOLLNONBLOCKING
// test (sample code)
@@ -67 +67 @@
- $(CXX) -O3 -g -o $@ $(HTTP) $< -luThreads
+ $(CXX) -O0 -g -o $@ $(HTTP) $< -luThreads
```
以這種設定編譯 uThreads webserver 是可以正常測試的，方法 `2` 的測試結果會與改用 g++ 7.5 的實驗結果並呈。
另外有嘗試將 uThreads、sample code 提至 `-O1`，若兩者均採 `-O1` 或 uThreads 採 `-O1`、sample code 採 `-O0`，則與修改前相同，均無法正常收到回應。 若 uThreads 採 `-O0`、sample code 採 `-O1` 則當 htstress 嘗試連入後便會產生以下錯誤：
```shell
$ taskset -c 0-1 ./bin/webserver 2
Error reading from socket: No such file or directory
fd 962199568
Segmentation fault (core dumped)
```
### 盡可能排除干擾因素
根據 man [cpupower](http://manpages.ubuntu.com/manpages/focal/en/man1/cpupower-set.1.html)，將其設為最大程度偏好效能。
> The range of valid numbers is 0-15, where 0 is maximum performance and 15 is maximum energy efficiency.
> This policy hint does not supersede Processor Performance states (P-states) or CPU Idle power states (C-states), but allows software to have influence where it would otherwise be unable to express a preference.
```shell
$ sudo cpupower -c 0-3 set -b 0
$ sudo cpupower -c all info -b
analyzing CPU 0:
perf-bias: 0
analyzing CPU 1:
perf-bias: 0
analyzing CPU 2:
perf-bias: 0
analyzing CPU 3:
perf-bias: 0
```
接著由於該設定不會取代 P-states, C-states，故接下來試著調整 C-states 最大可能避免 CPU idle。 透過 cpupower idle-set 命令 disable 所有 idle states:
```shell
$ sudo cpupower idle-set -D 0
Idlestate 0 disabled on CPU 0
Idlestate 1 disabled on CPU 0
Idlestate 2 disabled on CPU 0
Idlestate 3 disabled on CPU 0
Idlestate 4 disabled on CPU 0
Idlestate 5 disabled on CPU 0
Idlestate 6 disabled on CPU 0
Idlestate 7 disabled on CPU 0
Idlestate 8 disabled on CPU 0
Idlestate 0 disabled on CPU 1
...
```
P-states 的部份則將 governor 設為 performance，來讓表現更穩定，此外也進一步修改 fibdrv 作業中為消除干擾因素所寫的 shell script，將先前調整 perf-bias 及 C-states 整合進來，讓設定變方便。
```shell
$ sudo bash perf_test_mode.sh
cat /proc/sys/kernel/randomize_va_space
0
cat /sys/devices/system/cpu/intel_pstate/no_turbo
1
cat /sys/devices/system/cpu/cpu0/power/energy_perf_bias
0
cat /sys/devices/system/cpu/cpu0/cpufreq/scaling_governor
performance
sudo cpupower idle-info | grep "Available\|DISABLED"
Available idle states: POLL C1 C1E C3 C6 C7s C8 C9 C10
POLL (DISABLED) :
C1 (DISABLED) :
C1E (DISABLED) :
C3 (DISABLED) :
C6 (DISABLED) :
C7s (DISABLED) :
C8 (DISABLED) :
C9 (DISABLED) :
C10 (DISABLED) :
cat /sys/devices/system/cpu/isolated
0-1
```
### 實驗方法 `1` 及其結果
:::warning
**注意：**
目前 wrk 的測試結果仍存在問題，詳見本段末尾，在此列出重現問題的步驟。
下段有改用方法 `2` 取得的正確(合理)實驗結果，後續分析均採用方法 `2`。
:::
- webserver
使用 taskset 將其綁定到已經隔離出來的 cpu 0,1。 實際執行的命令如下：
```shell
// uThreads
$ taskset -c 0-1 ./bin/webserver $T
// nodejs (only for single thread)
$ taskset -c 0-1 node server.js
// fasthttp
$ GOMAXPROCS=$T taskset -c 0-1 ./server
// cppsp
$ taskset -c 0-1 ./run_example -t $T
```
`$T`： 執行緒數量
根據 uThreads 原作者所述，uThreads webserver 總是使用 `$T - 1` 個執行緒。
> Note, that the number of threads here always mean number of worker threads + 1, which means if you pass 4, the number of worker threads will be 3 and there will be 1 poller thread. --[httpbenchmarks](https://github.com/samanbarghi/httpbenchmarks)
- 測試工具: [wrk](https://github.com/wg/wrk)
為了方便彙整 wrk 測得的資訊及方便後續製圖，自行撰寫了基於 python 的測試程式來包裝 wrk 命令。 gist: [benchmark.py](https://gist.github.com/Kevin-Shih/7344e6227a9914ad813e96fa4d22f63c)
會在測試執行時以 htop 確保 wrk 所使用的核不會比 webserver 使用的核先達到滿負載，以確保測得 webserver 的完整效能。
- 測試 uThreads webserver 時遇到錯誤訊息
```shell
$ taskset -c 0-1 ./bin/webserver 2
Error: system:24 - Too many open files
$ errno 24
EMFILE 24 Too many open files
```
`EMFILE` 根據 [errno(3)](https://man7.org/linux/man-pages/man3/errno.3.html) 及 [getrlimit(2)](https://man7.org/linux/man-pages/man2/getrlimit.2.html) 所述，是由於嘗試開啟超過 `RLIMIT_NOFILE` 所限制的最大 fd 數量所導致。
透過 `ulimit` 將該終端機的 Soft limit 由 1024 提升至 8192 (超過 connection 數)
```shell
$ ulimit -Sn 8192
```
- 測試結果
**1 thread**
**2 threads (有問題的)**
:::warning
可以注意到使用 wrk 的測試，2 threads (以及沒放上來的 3 threads) 在並行程度低的時候，特別是在設為 `10` 時有特別顯著的效能降低，顯示使用 wrk 的測試方法在當前的環境下，其測試結果很可能有問題。 在下面會改用 `htsress` 測試。
:::
### 實驗方法 `2` 及其結果
除了改變測試工具及 session soft limit 外其餘部份與方法 `1` 維持相同。
- 測試工具: [htstress](https://github.com/arut/htstress)
為了方便彙整 htstress 測得的資訊及方便後續製圖，同樣撰寫了基於 python 的測試程式來包裝 htstress 命令。 gist: [benchmark_htstress.py](https://gist.github.com/Kevin-Shih/0f8cd0867001f44bace21335c569afc2)
同樣會遇到 `EMFILE`，透過 `ulimit` 將該終端機的 Soft limit 由 1024(default) 直接提升至 999999
```shell
$ ulimit -Sn 999999
```
另外，由於測試環境限制達不到真正的 8k 並行度，致使測試結果失準，因此圖表中不會顯示 8k 的結果。
- 測試結果
**1 thread**
**2 threads**
**3 threads**
:::info
後續測試將改為使用 [jserv/uThreads](https://github.com/jserv/uThreads)。
(此版本指定使用 g++ 7 編譯、不須安裝只須 `make all && make test`)
後續文中若無特別說明 `uThreads` 即代表此版本。
:::
下方將會列出使用此版本以方法 `2` 測試的結果，作為後續進一步修改的參考基準。
**1 thread**
**2 threads**
**3 threads**
## 找出並驗證 uThreads 勝過 cppsp 的原因
### M:N mapping
在 uThreads 中提及對 M:N mapping 的支援，是透過將 N 個 kThreads 以 `Cluster` 的方式聚合在一起來服務 M 個 uThreads，在目前實驗的情境中就是每個連入的客戶端 (M connections)，並具有非搶佔式的排程器。
根據以下程式碼可以確認 uThreads 中的 websever 確實是為每個連接的客戶端建立一個新的 user thread。
```cpp
sconn->listen(65535);
while(true){
Connection* cconn = sconn->accept((struct sockaddr*)nullptr, nullptr);
uThread::create()->start(defaultCluster, (void*)handle_connection, (void*)cconn);
}
sconn->close();
```
在本節希望透過限制 M:N mapping 的能力，回到 1:1 mapping 以檢驗 cluster 改進網頁伺服器效能的有效性。 故在試驗時將 server 設定為 1 個 kthread 並且同時只有一個 connection 以確保只有一個 uthread 來達到 1:1 mapping。
:::warning
TODO
- Facebook's folly::fiber, folly
- 若 uthreads 中的改進有效 試著移植到 quiz6
- 最前段補上 NPTL (Native POSIX Thread Library) 的介紹
- uThreads scheduler (#2)
- [hackernew](https://news.ycombinator.com/item?id=6726357)
- [google](https://www.theregister.com/2020/08/10/google_scheduling_code_reaches_linux/) 回去看 2013 的演講
:::
## 將 uThreads 中的啟發移植到 quiz6 中
這個部份將會分為 2 個階段進行：
- 建立一個 non-blocking socket, single thread 的伺服器
- 將 uThreads 中 M:N mapping 的 cluster, scheduler 等機制整合進來
### 建立基於 non-blocking socket, single thread 的伺服器
過去以 c 語言寫的伺服器都是簡單的 single thread, blocking socket 的伺服器，在這個部份希望能先建立一個基於 non-blocking socket, single thread 的伺服器並確認其執行的正確性及效能。 完整程式碼請見：[GitHub master/singleT_nonblock](https://github.com/Kevin-Shih/Linux2022q1-final-project/tree/master/singleT_nonblock)
Server 基本上是依據 uThreads 中的 webserver.cpp 並修改為 c 的版本
- 測試結果
### 建立 M:N mapping 的伺服器
先嘗試建立一個只有單個 Cluster 的伺服器，此時分配 user thread 的方式是指派給 local run queue 最短的 kernel thread。 完整程式碼請見：[GitHub master/m2n](https://github.com/Kevin-Shih/Linux2022q1-final-project/tree/master/m2n)
uthread node:
```c
typedef struct uthread_node_t{
thread_t current_kthread;
funcargs_t *fa; // handle connections
struct uthread_node_t *next;
}uthread_node_t;
typedef struct uthread_list_t{
unsigned long uthread_count;
uthread_node_t *head, *tail;
}uthread_list_t;
```
kthread node:
```c
typedef struct __node {
unsigned long int tid, tid_copy;
uthread_list_t runqueue; // kthread local runqueue
void *ret_val;
struct __node *next;
funcargs_t *fa;
} node_t;
```
kthread 的 routine 改為持續試著由 local runqueue 取得等待的 uthread，當 local runqueue 長度不為 0 時 pop 出 head 並執行該 uthread 中的 function。
```c=
static void kthread_try_run(void *arg){
spin_acquire(&global_lock);
uthread_list_t *runqueue = (uthread_list_t *)arg;
spin_release(&global_lock);
while(1){
if(__atomic_load_n(&runqueue->uthread_count, __ATOMIC_RELAXED) != 0){
// pop and run
spin_acquire(&global_lock);
uthread_node_t *ut = runqueue->head;
runqueue->head = runqueue->head->next;
runqueue->uthread_count--;
spin_release(&global_lock);
(ut->fa->f)(ut->fa->arg);
}
}
}
```
- 測試結果
**1 thread**
**2 threads**
**3 threads**
:::warning
TODO
目前的 accept 並沒有加入 epoll_wait 來等待，後續應加入避免持續佔用 cpu 資源
試著在 accept_conn() 加入 epoll 後程式在 kthread_try_run() L10 出現 segmentation fault 但在 gdb 測試，有時會出現如下錯誤，原因正在查證
```
Thread 1 "server" received signal SIGSEGV, Segmentation fault.
tcache_get (tc_idx=<optimized out>) at malloc.c:2939
2939 malloc.c: No such file or directory.
```
註： 當 request 數量較少(< 10000)時不一定會發生，但當數量增大則會發生(無法完成 benchmark)
把實用的 scheduler 搞定
:::
Sign in with Wallet
Connect another wallet