2022q1 Homework5 (quiz6)

contributed by < Kevin-Shih >

測驗題目 quiz6
final project github

問題描述

〈UNIX 作業系統 fork/exec 系統呼叫的前世今生〉提到 clone 系統呼叫，搭配閱讀〈Implementing a Thread Library on Linux〉，嘗試撰寫一套使用者層級的執行緒函式庫，程式碼可見: readers.c

運作原理與解題

逐行解釋程式碼運作前，應當描述 Linux NPTL 和相關系統呼叫的原理。
:notes: jserv

儲存執行緒資料的節點及 TCB

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

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 語法)

        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 系統呼叫。

// 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:

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

clone one-to-one 所用的 flags

#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)

建立新的 thread

/**
 * @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

/**
 * @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

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
  lscpu

  ​​​​$ 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)
  dmidecode -t memory

  ​​​​$ 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

$ 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 的實驗 (throughput)

首先使用 wrk 嘗試，過程中使用的命令依照 httpbenchmarks。 然而對於 uThreads webserver 卻產生了異常的結果，wrk 回報的 Requests/sec 為 0。

// 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 嘗試，仍然無法正常得到結果。

// 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 的回應。

./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! 的，但只有一次)

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 進行測試，測試結果同樣異常。

$ 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 編譯。

$ sudo update-alternatives --install /usr/bin/g++ g++ /usr/bin/g++-7  100
$ g++ --version
g++ (Ubuntu 7.5.0-6ubuntu2) 7.5.0

編譯完後的執行結果：

$ 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 以抑制編譯器最佳化。

// 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 嘗試連入後便會產生以下錯誤：

$ taskset -c 0-1 ./bin/webserver 2
Error reading from socket: No such file or directory
fd 962199568
Segmentation fault (core dumped)

盡可能排除干擾因素

根據 man cpupower，將其設為最大程度偏好效能。

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.

$ 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:

$ 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 整合進來，讓設定變方便。

$ 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 及其結果

注意：
目前 wrk 的測試結果仍存在問題，詳見本段末尾，在此列出重現問題的步驟。
下段有改用方法 2 取得的正確(合理)實驗結果，後續分析均採用方法 2。

• webserver
  使用 taskset 將其綁定到已經隔離出來的 cpu 0,1。 實際執行的命令如下：

  ​​​​// 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

• 測試工具: wrk
  為了方便彙整 wrk 測得的資訊及方便後續製圖，自行撰寫了基於 python 的測試程式來包裝 wrk 命令。 gist: benchmark.py

  會在測試執行時以 htop 確保 wrk 所使用的核不會比 webserver 使用的核先達到滿負載，以確保測得 webserver 的完整效能。

• 測試 uThreads webserver 時遇到錯誤訊息

$ 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) 及 getrlimit(2) 所述，是由於嘗試開啟超過 RLIMIT_NOFILE 所限制的最大 fd 數量所導致。

透過 ulimit 將該終端機的 Soft limit 由 1024 提升至 8192 (超過 connection 數)

$ ulimit -Sn 8192

• 測試結果
  1 thread
  
  2 threads (有問題的)
  

可以注意到使用 wrk 的測試，2 threads (以及沒放上來的 3 threads) 在並行程度低的時候，特別是在設為 10 時有特別顯著的效能降低，顯示使用 wrk 的測試方法在當前的環境下，其測試結果很可能有問題。 在下面會改用 htsress 測試。

實驗方法 2 及其結果

除了改變測試工具及 session soft limit 外其餘部份與方法 1 維持相同。

• 測試工具: htstress
  為了方便彙整 htstress 測得的資訊及方便後續製圖，同樣撰寫了基於 python 的測試程式來包裝 htstress 命令。 gist: benchmark_htstress.py

同樣會遇到 EMFILE，透過 ulimit 將該終端機的 Soft limit 由 1024(default) 直接提升至 999999

$ ulimit -Sn 999999

另外，由於測試環境限制達不到真正的 8k 並行度，致使測試結果失準，因此圖表中不會顯示 8k 的結果。

• 測試結果
  1 thread
  
  2 threads
  
  3 threads
  

後續測試將改為使用 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。

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。

TODO

• Facebook's folly::fiber, folly
• 若 uthreads 中的改進有效 試著移植到 quiz6
• 最前段補上 NPTL (Native POSIX Thread Library) 的介紹
• uThreads scheduler (#2)
• hackernew
• google 回去看 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

Server 基本上是依據 uThreads 中的 webserver.cpp 並修改為 c 的版本

• 測試結果
  
  

建立 M:N mapping 的伺服器

先嘗試建立一個只有單個 Cluster 的伺服器，此時分配 user thread 的方式是指派給 local run queue 最短的 kernel thread。 完整程式碼請見：GitHub master/m2n

uthread node:

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:

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。

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
  

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 搞定