2020q1 Homework6 (fiber)

contributed by < haogroot >

tags: linux2020

題目連結

測試環境

Kernel version: 5.3.0-51-generic
OS: Ubuntu 19.10
CPU model: Intel® Core™ i7-8565U CPU @ 1.80GHz

作業要求 1

• 研讀 Paul Turner 的簡報檔案 User-level threads 及相對應的演講錄影，記錄你的認知，並回答以下問題:

  1. M:N model 的優勢在哪？請舉例說明
  • 由於有更多的 kernel contexts 可以利用，可以做到更好的 parallelism 。
  • 由於有更多的 kernel contexts ，大幅減少進入 kernel 來做排程的機會，這個動作是昂貴的。
  2. M:N model 的劣勢為何？舉例說明並談論 Linux NPTL 作為折衷的設計，做了哪些修正？搭配閱讀 The future of M:N threading 討論串
  • 許多現有的技術都是基於 1:1 model 來設計的，修改為 M:N model 會有相容性問題
    • dubugging 和 profiling tool
    • POSIX (如果今天 kernel 準備將 signal 送到 user-space ，他會不知道該送給哪一個 user-level thread )
  3. Google 內部 (至少在 2013 年) 針對執行緒實作做了哪些調整？
  • 以 1:1 Model 來說， context-switch 是一個昂貴的動作，但卻需要頻繁的執行，所以應該採用 M:N model 來減少需要 switch 到 kernel 做排程的機會。但在 Paul Turner 的實驗結果發現 switch 到 kernel 並不如想像中那麼昂貴，大部份 context switch 的花費更多在於 scheduling 上 ，因此透過不同 Syscall API 來製造出 cpu 忙碌的情況，讓同 process 下的 thread 在原本的 CPU 上繼續執行。 維持使用原本的 1:1 Model，也能夠避免 M:N model 的劣勢。

作業要求 2

• 答覆 第 8 週測驗題 第 2 題組的所有延伸問題，需要設計實驗和解讀各式數據

Trampoline

我的理解為他是一個埋在程式碼特定位置裡的 hook ，當執行到該特定位置，就會觸發去執行遠方的一段程式碼，執行完後再跳回來繼續執行原本程式碼。
Gerald 在 stackoverflow 討論串上分享一個有趣的例子： 他應用 trampoline 在遊戲上作弊，當遊戲開始時會去建立檔案，他找到建立檔案函式並修改前面幾個 bytes 來住入他自己的 assembly code ，這些 assembly code 會跳到他的 "trampoline" 函式中，他就可以做任何他想做的事情在他的 "trampoline" 中，然後就會跳回去，繼續執行建立檔案之後的動作。

quiz8 背景知識

Signal handling

sigset_t 用來儲存 POSIX signel 的集合，各個位置代表不同訊號，如果為 1，代表要阻塞該訊號。

sigemptyset() 將所有訊號都清空為 0。
sigfillset() 將所有訊號設為 1，全部都阻塞。

阻塞訊號不代表 "忽略" 該訊號，而是先將該訊號 pending ，之後再去處理該訊號。

int sigprocmask(int how, const sigset_t *set, sigset_t *oldset);

檢查並改變 blocked signals。依據參數 how 內容做不同的動作。

• SIG_BLOCK : set 和 oldset 兩 signal set 裡的訊號若是接收到都阻塞。
• SIG_UNBLOCK ： 設定 set 和 oldset 兩 signal set 的交集為不想阻塞的訊號。
• SIG_SETMASK ： 此 process 對應的 signal set 將被 set 所取代。

sigsuspend : 暫停目前的 task 來等待訊號，等到 signal handler 處理完後，會再繼續當前 task 。

為什麼需要 Block signal ?

可以避免訊號中斷了敏感的操作，例如

1. 若 process 正在修改某個 critical section ，而 signal handler 同樣也修改到 critical section 的話，應該先將該訊號阻塞，直到離開 critical section 後再處理訊號。
2. 避免 signal handler 執行時被其他訊號 interrupt ， signal handler 執行時可以透過設定 struct sigaction 裡的成員 sa_mask 來阻塞特定訊號（ 測驗中 timer_handler() 內就使用這樣方法 ）。
3. 如果你想要檢查訊號是否已經送達，使用一個 flag 來紀錄並不 reliable 。最好的方法是透過檢查訊號是否被 block 。

Blocked signal 何時會被處理？

1. 在上述為什麼需要 Block singal 問題中的第2點狀況中，在 signal handler 執行前先設定其 signal mask ，等到 handler 執行完重回原本位置，mask 也會恢復為執行 handler 前的設定，這時候 pending 中的 signal 在這個恢復過程中由 block 轉為 unblock ，訊號就會被送達。 [reference: 24.7.5 Blocking Signals for a Handler]
2. 使用 sigpending() 可以找出被 pending 的訊號。

[reference]:
24 Signal Handling
24.7 Blocking Signals - GNU C Library Reference Manual

接下來探討測驗中的 lock_irq_save 和 lock_irq_restore 。

static void local_irq_save(sigset_t *sig_set) {
    sigset_t block_set;
    sigfillset(&block_set);
    sigdelset(&block_set, SIGINT);
    sigprocmask(SIG_BLOCK, &block_set, sig_set);
}

透過 local_irq_save ，阻塞除了 SIGINT 以外的所有訊號，可以理解為幫當前 task 攔截除了 SIGINT 以外的訊號。

static void local_irq_restore(sigset_t *sig_set) {
    sigprocmask(SIG_SETMASK, sig_set, NULL);
}

透過 local_irq_restore 則將 task 的 signal set 換成參數 sig_set。

這兩個函式搭配起來使用可以達到怎樣的效果?
以測驗中的 schedule() 為例:

static void schedule(void) {
    sigset_t set;
    /* Initialization shall be executed */
    sigemptyset(&set);
    local_irq_save(&set);
    
    ...
    
    local_irq_restore(&set)
}

以我的理解，local_irq_save() 應該是想先將所有的 signal 都先 block 住，避免被中斷，接著使用 local_irq_store() 能將 signal set 恢復為原本的 (即呼叫 local_irq_save() 之前的 signal set)，回想前面討論 blocked signal 何時會被處理 中提到：如果這時候 pending 中的 signal 在這個恢復過程中由 block 轉為 unblock ，訊號就會被送達，當我們執行 local_irq_store() 就能接收到這段時間被阻塞的訊號了。

程式碼潛在危險

在 24.7.2 Signal Sets 中提到：

You must always initialize the signal set with one of these two functions before using it in any other way.

因此變數 set 應該先透過 sigemptyset() 來初始化比較好。

ucontext_t

在 <ucontext.h> 中定義4個函式 getcontext() , setcontext(), makecontext() 和 swapcontext() 。透過使用這系列函式可以在同個 process 下的 thread 之間做 user-level context switch ( user-level thread 與 kernel-level thread 是不同的，前者是無法被作業系統辨識出來，因此作業系統在 user level 要排程的話，是以 process 為單位。 )

根據 wikipedia 對 context (computing) 的定義：

In computer science, a task context is the minimal set of data used by a task (which may be a process, thread, or fiber) that must be saved to allow a task to be interrupted, and later continued from the same point. The concept of context assumes significance in the case of interruptible tasks, wherein, upon being interrupted, the processor saves the context and proceeds to serve the interrupt service routine. Thus, the smaller the context is, the smaller the latency is.

context 可以理解為該 task 當下的狀態，當今天發生 interrupt 時，透過 context 還能夠回復到 interrupt 發生當下的狀態。有這個背景知識，再來看 <ucontext.h> 中這4個函式就能夠比較了解他們的作用。

ucontext_t type 包含以下欄位：

typedef struct ucontext_t {
    struct ucontext_t *uc_link;
    sigset_t          uc_sigmask;
    stack_t           uc_stack;
    mcontext_t        uc_mcontext;
    ...
} ucontext_t;

sigset_t 跟 signal 處理有關係， stack_t 包含現在 context 所使用的 stack ，uc_link 則是現在 context 執行結束後會執行的 context 。

getcontext(ucontext_t *ucp)

• 可以將呼叫他的 task 當下的 context 保留到參數 ucp 中。

setcontext(ucontext_t *ucp)

• 回復到參數 ucp 所指向的 context

makecontext(ucontext_t *ucp, void (*func)(), int argc, ...)

1. 修改 ucp 所指向的 context ， ucp->uc_stack 要由呼叫此函數者先行分配好一塊新的 stack ，ucp->uc_link 也由呼叫此函式者分配好其 Successor context 。
2. makecontext() 產生的 context 接著可以透過 setcontext() 或 swapcontext() 來啟用，參數 func 會被呼叫並且帶有 argc 所指定數量的其餘參數。
3. 函式 func 回傳後， Successor context 再被啟用。 （若 Successor context 為 NULL, thread 存在著）

swapcontext(ucontext_t *oucp, const ucontext_t *ucp)

• 將參數 oucp 的 context 保存下來並回復到參數 ucp 指向的 context 。
• swapcontext(oucp, ucp) 等同於 getcontext(oucp) 再 setcontext(ucp) 。
• 針對 swapcontext 有一點值得紀錄，這個函式第一次被使用的時候並不會回傳。但若之後 oucp 又被 activated ，這次的 swapcontext 就會回傳。

[Reference]

1. GETCONTEXT(3) Linux Programmer's Manual
2. MAKECONTEXT(3) Linux Programmer's Manual
3. SWAPCONTEXT(3) Linux Programmer's Manual

我們來看 main function 會怎麼執行：

int main() {
    timer_init();
    task_init();

    task_add(sort, "1"), task_add(sort, "2"), task_add(sort, "3");

    preempt_disable();
    timer_create(10000); /* 10 ms */

    while (!list_empty(&task_main.list) || !list_empty(&task_reap)) {
        preempt_enable();
        timer_wait();
        preempt_disable();
    }
    preempt_enable();
    timer_cancel();

    return 0;
}

1. timer_init() 註冊訊號 SIGALARM ，接收到該訊號會去執行 timer_handler，在 timer_handler 預設是會 block 所有 SIGNAL 。
2. task_init() 初始化存放 task 的 linked list 。
3. 使用 task_add() 增加3個 task 到 linked list 中，帶有兩個參數，分別為 task_trampoline() 和一整數。透過 makecontext 將參數放到 task 中的 context ，這邊沒有為他們安排任何的 Successor context ，每個 task 都會 block 訊號 SIGALARM 。
4. preempt_disable() 不允許搶佔
5. timer_create() 建立一個每 10 ms 會發出 SIGALARM 的 timer 。
6. main() 接著會一直執行 timer_wait() 直到 linked list 沒有任何 node ，timer_wait() 暫停目前的 task 來等待 SIGALARM，訊號來之後並執行 timer_handler()，結束後會再繼續當前 task 。
7. 在 timer_handler() 中檢查是否允許搶佔，可以的話執行 schedule()。
8. schedule() 會執行 task_switch_to() 來切換 context （也就是在 user-level thread 之間切換），在這個測驗中有4個 context，分別是 main() 以及3個透過 task_add 建立的 task 。 這3個 task 要是執行完，schedule() 會將他們釋放掉。

static void schedule(void) {
    sigset_t set;
    local_irq_save(&set);
    struct task_struct *next_task =
        list_first_entry(&task_current->list, struct task_struct, list);
    if (next_task) {
        if (task_current->reap_self) list_move(&task_current->list, &task_reap);
        task_switch_to(task_current, next_task);
    }

    struct task_struct *task, *tmp;
    list_for_each_entry_safe (task, tmp, &task_reap, list) /* clean reaps */
        task_destroy(task);
    local_irq_restore(&set);
}

10. 每個 task 首先會執行 task_trampoline() ，再裏面又透過 callback function 方式去執行 sort() ，執行完後會將 task->reap_self 設為 true ， schedule() 就會自動將他釋放。 在執行 sort() 過程中，會被 timer interrupt ，因而執行 timer_handler 並切換到別的 context 。

---

延伸問題:

1. 解釋上述程式碼運作原理，以及對應到 Linux 核心原始碼的若干機制，如 preempt_disable, preempt_enable, local_irq_save, local_irq_restore 等等

preempt_enable 和 preempt_disable 用來關閉搶佔。 spinlock 的設計中就是不允許搶佔，以下是 spinlock 的原始碼

static inline void __raw_spin_lock(raw_spinlock_t *lock)
{
	preempt_disable();
	spin_acquire(&lock->dep_map, 0, 0, _RET_IP_);
	LOCK_CONTENDED(lock, do_raw_spin_trylock, do_raw_spin_lock);
}

在嘗試持有 spinlock 前會先將搶佔關閉，為什麼 spinlock 不允許搶佔呢？

• 若是允許搶佔，則持有 spinlock 的 process 就會睡眠，這違反 spinlock 持有者必須儘快完成任務並釋放鎖的設計。
• 來搶佔的 process 也有可能想要持有 spinlock ，這樣狀況下變成一個 deadlock 。

而 spinlock 有另一種形式，當你今天是要在 interrupt handler 內想要去獲取 spinlock 時，使用 spin_lock_irqsave() 先保存目前的中斷狀態並且關閉所有中斷，接著再去獲取 spinlock ，不需要 spinlock 後再透過 spin_lock_irqrestore() 來恢復中斷前的狀態，從 spin_lock_irqsave() 原始程式碼 中可以看到裏面有是呼叫 local_irq_save() ，只是是保存中斷當下暫存器等，不同於測驗中是為了保留訊號。

static inline unsigned long __raw_spin_lock_irqsave(raw_spinlock_t *lock)
{
	unsigned long flags;

	local_irq_save(flags);
	preempt_disable();
	spin_acquire(&lock->dep_map, 0, 0, _RET_IP_);
	/*
	 * On lockdep we dont want the hand-coded irq-enable of
	 * do_raw_spin_lock_flags() code, because lockdep assumes
	 * that interrupts are not re-enabled during lock-acquire:
	 */
#ifdef CONFIG_LOCKDEP
	LOCK_CONTENDED(lock, do_raw_spin_trylock, do_raw_spin_lock);
#else
	do_raw_spin_lock_flags(lock, &flags);
#endif
	return flags;
}

2. 探討上述程式碼的 signal 使用機制，指出其正確性或效率疑慮，並著手改進

• 如同前面提到，在 schedule() 應該先對 signal set 先行初始化。

---

作業要求 3

• 解釋上述 threadpool 內建 profiler 運作的機制，特別是 getrusage 和 RUSAGE_THREAD 的使用。可透過 eBPF 觀察及分析;

在我的環境 中，編譯 threadpool 過程中，編譯 tasklet.c 會失敗，錯誤如下：

  CC	src/tasklet.o
src/tasklet.c: In function ‘wait_list_fini’:
src/tasklet.c:9:47: error: ‘uintptr_t’ undeclared (first use in this function)
    9 | #define pointer_set_bits(p, bits) ((void *) ((uintptr_t)(p) | (bits)))
      |                                               ^~~~~~~~~

透過新增 #include <stdint.h> 後才能夠順利編譯。

---

作業要求 4

Fiber

• 自 GitHub fiber 進行 fork，目標是修正現有 fiber 實作的缺失並發展視覺化效能分析工具，過程中應滿足以下:
  1. 解釋 Fiber 運作機制，和指出原有測試項目無法通過的原因並修正;
  2. 以 $ grep -r FIXME 找出程式碼標注的改進事項，特別是記憶體管理相關，若能引入高效能的 memory pool 實作，會有助益;
  3. 學習 第 8 週測驗題 的實作手法，對 Fiber 程式予以重構 (refactor)，讓實作更清晰並易於維護;
  4. 針對 Fiber，撰寫更多的測試案例，如 Producer–consumer problem，過程中你可能會新增若干 API，儘可能維持和 POSIX Thread 的對應;
  5. 將前述的視覺化效能分析工具整合在 Fiber 並設計對應的實驗;
  6. 提出改進 Fiber 效能的機制並予以落實;
  7. ThreadKit 提出的 tasklet 定位是 "thread without stack"，思考其效益，也對照 Protothread 這樣 "Threads without stacks" 的設計 (即不用依賴 ucontext) 的效能表現，和探討其限制;

Fiber 運作機制

1. M:N model 意謂著有 M 個 user-level threads 交由 N 個 kernel-level threads 來執行。
2. 利用 clone 用來建立 kernel-level threads 。 除了第一個 main thread 以外的 thread 都要為他們分配好 stack 。
3. 透過 fiber_create() 建立 user-level threads 。
4. 透過 timer 和 signal hadler 來完成 user-level thread 的 preemptive scheduling ，有一點值得注意的是 timer 的時間是以實際執行時間來倒數，並不是系統時間 （ reference ITIMER_PROF ）； user-level threads 可以透過 fiber_yield() 主動讓出 CPU 來達到 cooperative scheduling 。

malloc() 失敗時的 error handling

在 fiber_create() 中，若是 allocate memory 失敗應該直接回傳。

    /* create a TCB for the new thread */
    _tcb *thread = malloc(sizeof(_tcb) + 1 + _THREAD_STACK);
    if (!thread) {
        perror("Failed to allocate space for TCB!");
        return -1;
    }

• 待確認
  由於 clang-format 關係，fiber.c 的 header 順序會自動被更動， fiber.h 將會被移到 header 的第一個順序。這樣子會造成 compile 錯誤。錯誤訊息如下：

  CC	src/fiber.o
In file included from src/fiber.c:5:
./include/fiber.h:6:9: error: unknown type name ‘uint’
    6 | typedef uint fiber_t;
      |         ^~~~
./include/fiber.h:31:5: error: unknown type name ‘uint’
   31 |     uint lock;
      |     ^~~~

我必須在 fiber.h 上增加 stdlib.h 才能順利編譯並可以移除掉 stdint.h，。

test-content()

兩個 user context 不斷做 swap 來輪流執行，他們的任務都可能機率性的結束，結束之後回到 main thread ，我們透過 vlagrind 來對他進行記憶體檢測，

• 在編譯加上 -g
• 透過執行 $ valgrind --leak-check=full ./tests/test-context

結果如下：

==9725== LEAK SUMMARY:
==9725==    definitely lost: 0 bytes in 0 blocks
==9725==    indirectly lost: 0 bytes in 0 blocks
==9725==      possibly lost: 0 bytes in 0 blocks
==9725==    still reachable: 16,384 bytes in 2 blocks
==9725==         suppressed: 0 bytes in 0 blocks

仍然有 16384 bytes 記憶體沒有被正確釋放，而程式中為兩個 user context 透過 malloc() 各分配了 SIGSTKSZ 大小的記憶體，根據查詢 linux kernel 原始碼後， 他所代表大小為 8192 ，因此可以確認即為這兩塊為 user context 分配的記憶體未被正確釋放。

因此我們在 main thread 準備結束前將他釋放即可以通過 valgrind 的檢查。

    free(ping_ctx.uc_stack.ss_sp);
    free(pong_ctx.uc_stack.ss_sp);
    printf("main: exiting\n");

test-yield()

• 兩種切換 user-level switch 方式：
  1. 透過 fiber_yield() 主動讓出 CPU
  2. timer 固定時間發出 SIGPROF ， 引發 timer handler schedule() 執行，將目前執行的 user-level thread 放到 user-level thread queue 的尾端，並透過 swapcontext() 執行 kernel-level thread 。

在 main thread 中透過 fiber_join() 等待所有的 user-level thread 結束。最後執行 fiber_destroy() ，此函數是用來收尾的，應該將該釋放的記憶體都釋放乾淨，在此專案中，會替 user-level thread 與 kernel-level thread 的 thread control block 分配記憶體，前者的釋放由 k_thread_exec_func() 負責，後者的釋放卻沒有實作。

• kernel-level thread 的釋放

test-mutex()

執行過程會發生 Core dumped. 一開始使用 Valgrind 想來找記憶體不當使用問題，但 Valgrind 並不支援 clone ，因此無法分析。

透過 gdb 來追 core dumped 問題，以下紀錄過程：

1. 啟用 core dump

$ ulimit -c unlimited
$ ulimit -c 240000

2. 透過 gdb

• 編譯時加上 -g
• 執行 $ gdb -c core ./test-mutex
• 在 gdb 內執行直到 segmentation fault ，當下錯誤將紀錄在 core 這個檔案中。
• 在 termeinal 執行 gdb test-mutex core 進到 gdb 內
• 透過 where 或 bt full 可以知道執行到哪裡時發生記憶體問題

[Current thread is 1 (LWP 22780)]
(gdb) bt
#0  _int_free (av=0x7ffff7f89b80 <main_arena>, p=0x55555556b6a0, have_lock=<optimized out>) at malloc.c:4341
#1  0x0000555555555f60 in k_thread_exec_func (arg=0x0) at src/fiber.c:350
#2  0x00007ffff7ec1323 in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:95

而 fiber.c 第 350 行則是釋放當下執行執行緒所佔有的記憶體。

        if (TERMINATED == run_tcb->status || FINISHED == run_tcb->status) {
            /* do V() in thread semaphore implies that current user-level
             * thread is done.
             */
            sem_post(&(sigsem_thread[run_tcb->tid].semaphore));
            free(run_tcb);
            user_thread_num--;
            continue;
        }

[Reference]

1. AIdrifter CS 浮生筆錄 : Debug Hacks Ch2 : Debug前該知道的事
2. How do I analyze a program's core dump file with GDB when it has command-line parameters?

實作 fiber_destroy

在釋放 kernel-level thread 前，首先確認他是否已經沒有任務要執行，而他的主要任務就是執行 user-level thread ，所以若是 user-level thread 都結束了，kernel-level thread 自然可以被釋放，可以透過檢查變數 user_thread_num 是否為 0 來確認是否所有 user-level thread 都結束。

在建立 kernel-level thread 時候，為其分配好記憶體，並透過 clone() 的參數來給定這塊 stack ，值得注意的是，在 clone man page 中提到 stack 是往下長的，所以這也是為什麼 clone 所帶的參數會是分配的 stack 記憶體位置加上其大小。

這邊我感到疑惑，我們分配好記憶體交由 child thread ，那這塊記憶體是否會隨著 child thread 回傳而直接被釋放呢或是該由 child thread 自己釋放呢？ 但是記憶體又是由 parent thread 所分配的，會不會還是該由 parent thread 來釋放？

• pthread_create() 一樣最終透過 clone() 來建立 thread ，我參考 pthread_create() 和 pthread_join() 來尋找方向，在後者程式碼當中，可以看到他有針對 tcb 做釋放記憶體的動作。
• clone 參數中帶有 CLONE_VM ，意味著記憶體是由 parent 跟 child thread 共享的，最安全的作法應該是確認兩者都不會再 access 記憶體後再將其釋放。

另外一點覺得奇怪的是建立 kernel-level thread 放到 fiber_create() 才做有點奇怪，最好方法應該是在 fiber_init() 來建立並在 fiber_destroy() 來釋放。

• 這邊我們為 kernel-level thread 分配了 stack ，但 stack 要是一直無止盡長大，有機會超過我們為其分配的 stack 上限，這是一個安全上的疑慮。