改進 quiz4 (D)

contributed by < Wallmountain >

不用抄寫題目，直接探討和改進 coro 實作。

jserv

題目

以下嘗試用 lab0 提及的 setjmp 和 longjmp，用以實作〈你所不知道的 C 語言: goto 和流程控制篇〉闡述的 coroutine，參考的程式執行輸出如下:

Task 0: n = 3
Task 1: n = 3
Task 0: resume
Task 1: resume
Task 0: resume
Task 0: complete
Task 1: resume
Task 1: complete

原始程式碼如下: (檔名 jmp.c)

#include <setjmp.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"

struct task {
    jmp_buf env;
    struct list_head list;
};

static LIST_HEAD(tasklist);
static void (**tasks)(void *);
static int ntasks;
static jmp_buf sched;

static void task_add(struct list_head *tasklist, jmp_buf env)
{
    struct task *t = malloc(sizeof(*t));
    memcpy(t->env, env, sizeof(jmp_buf));
    INIT_LIST_HEAD(&t->list);
    list_add_tail(&t->list, tasklist);
}

static void task_switch(struct list_head *tasklist)
{
    jmp_buf env;

    if (!list_empty(tasklist)) {
        struct task *t = list_first_entry(tasklist, struct task, list);
        list_del(&t->list);
        memcpy(env, t->env, sizeof(jmp_buf));
        free(t);
        longjmp(env, 1);
    }
}

static void task_join(struct list_head *tasklist)
{
    jmp_buf env;

    while (!list_empty(tasklist)) {
        struct task *t = list_first_entry(tasklist, struct task, list);
        list_del(&t->list);
        memcpy(env, t->env, sizeof(jmp_buf));
        free(t);
        longjmp(env, 1);
    }
}

void schedule(void)
{
    static int i;

    srand(0xCAFEBABE ^ (uintptr_t) &schedule); /* Thanks to ASLR */

    setjmp(sched);

    while (ntasks-- > 0) {
        int n = rand() % 5;
        tasks[i++](&n);
        printf("Never reached\n");
    }

    task_join(&tasklist);
}

/* A task yields control n times */

void task0(void *arg)
{
    jmp_buf env;
    static int n;
    n = *(int *) arg;

    printf("Task 0: n = %d\n", n);

    if (setjmp(env) == 0) {
        task_add(&tasklist, env);
        longjmp(sched, 1);
    }

    for (int i = 0; i < n; i++) {
        if (setjmp(env) == 0) {
            task_add(&tasklist, env);
            task_switch(&tasklist);
        }
        printf("Task 0: resume\n");
    }

    printf("Task 0: complete\n");
    longjmp(sched, 1);
}

void task1(void *arg)
{
    jmp_buf env;
    static int n;
    n = *(int *) arg;

    printf("Task 1: n = %d\n", n);

    if (setjmp(env) == 0) {
        task_add(&tasklist, env);
        longjmp(sched, 1);;
    }

    for (int i = 0; i < n; i++) {
        if (setjmp(env) == 0) {
            task_add(&tasklist, env);
            task_switch(&tasklist);
        }
        printf("Task 1: resume\n");
    }

    printf("Task 1: complete\n");
    longjmp(sched, 1);
}

#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]))
int main(void)
{
    void (*registered_task[])(void *) = {task0, task1};
    tasks = registered_task;
    ntasks = ARRAY_SIZE(registered_task);

    schedule();

    return 0;
}

首先，先來看 setjmp 和 longjmp 的文件

The setjmp() function saves various information about the calling environment (typically, the stack pointer, the instruction pointer, possibly the values of other registers and the signal mask) in the buffer env for later use by longjmp(). In this case, setjmp() returns 0.

setjmp 可跨越函式，在任意程式碼之間跳躍 (即 non-local goto)，儲存目前位置資訊，之後可以使用 longjmp 跳躍到目前儲存的位置

The longjmp() function uses the information saved in env to transfer control back to the point where setjmp() was called and to restore ("rewind") the stack to its state at the time of the setjmp() call. In addition, and depending on the implementation (see NOTES), the values of some other registers and the process signal mask may be restored to their state at the time of the setjmp() call.

修改原程式碼中的 task 函式，印出變數的數值，去看執行結果是否符合預期

void task0(void *arg)
{
    jmp_buf env;
    static int n;
    n = *(int *) arg;

    printf("Task 0: n = %d\n", n);

    if (setjmp(env) == 0) {
        task_add(&tasklist, env);
        longjmp(sched, 1);
    }

    for (int i = 0; i < n; i++) {
        if (setjmp(env) == 0) {
            task_add(&tasklist, env);
            task_switch(&tasklist);
        }
        printf("Task 0: resume %d\n", i);
    }

    printf("Task 0: complete %d\n", n);
    longjmp(sched, 1);
}

在下面的狀況下，執行結果並不符合預期，在 task 0 中的區域變數 i 在 task 1 完成後，發生了非預期的變化，變數 i 的值和原先尚未 longjmp 前不同。

Task 0: n = 2
Task 1: n = 0
Task 1: complete 0
Task 0: resume 22052
Task 0: complete 2

而問題在文件中有提到

The compiler may optimize variables into registers, and longjmp()
may restore the values of other registers in addition to the
stack pointer and program counter. Consequently, the values of
automatic variables are unspecified after a call to longjmp() if
they meet all the following criteria:
• they are local to the function that made the corresponding
setjmp() call;
• their values are changed between the calls to setjmp() and
longjmp(); and
• they are not declared as volatile.

在編譯器優化後， longjmp 可能不會恢復 stack 中的變數，於是將變數 i 宣告成靜態變數，變數 i 便不會放在 stack 中了，以此解決這邊因為編譯器造成的問題。

Task 0: n = 4
Task 1: n = 3
Task 0: resume 0
Task 1: resume 0
Task 0: resume 1
Task 1: resume 1
Task 0: resume 2
Task 1: resume 2
Task 1: complete 3
Task 0: resume 3
Task 0: complete 4

在 preempt_sched 有實作 preemptive scheduling，將 task 以鏈結的形式儲存

若在將新工作加入鏈結或刪除鏈結中的工作時被搶占，則有機會發生工作遺失的問題，因此加入靜態變數 preempt_count，當在需要更改工作的鏈結時，將其改成不能被搶占，便能解決 race condition

static int preempt_count = 0;
static void preempt_disable(void)
{
    preempt_count++;
}
static void preempt_enable(void)
{
    preempt_count--;
}

在 preempt.h 中，有用到以下的程式碼，也顯示了在 linux kernel 中各個執行緒擁有其各自的變數 preempt_count，在需要搶佔時，必須去確定當前執行緒是否能夠被搶佔

static __always_inline int preempt_count(void)
{
	return READ_ONCE(current_thread_info()->preempt_count);
}

0-7 bit 為 preempt-disable count 紀錄到目前為止，搶占被禁止的次數
接著三個 count 為分別記錄執行緒被中斷的次數
8-15 bit 為 Software interrupt count
16-19 bit 為 Hardware interrupt count
20-23 bit 為 Non-maskable interrupt count

接著，來研究 signal 使用方式，以下為 sigaction 的結構

struct sigaction {
               void     (*sa_handler)(int);
               void     (*sa_sigaction)(int, siginfo_t *, void *);
               sigset_t   sa_mask;
               int        sa_flags;
               void     (*sa_restorer)(void);
           };

sa_handler 為 function pointer，代表訊號產生時要做的行為
sa_sigaction 只有在當 sa_flags 被賦值為 SA_SIGINFO 時，取代 sa_handler 成為訊號產生時要做的行為

當 sa_flags 被賦值為 SA_SIGINFO 時，handler 會轉變成指向帶有三個參數的函式的指標

void handler(int sig, siginfo_t *info, void *ucontext)
{
    ...
}

sig 為導致觸發信號處理函式的信號編號
info 為指向帶有信號資訊結構的指標
ucontext 為指向結構 ucontext_t 的指標，用來記錄存在 user space stack 中的信號內容

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

uc_link 為指向下一個內容的指標，當前的 context 可用 makecontext 建立

為避免在 printf 此類系統呼叫時被搶占，故將其包夾成一個 crititcal section

#define task_printf(...)     \
    ({                       \
        preempt_disable();   \
        printf(__VA_ARGS__); \
        preempt_enable();    \
    })

設定多久之後要觸發訊號 SIGALRM，而之後會不會繼續每隔一段時間觸發訊號，則是要另外設定間格時間

static void timer_create(unsigned int usecs)
{
    ualarm(usecs, usecs);
}

問題 :
訊號觸發後，程式會跳到後續的處理函式，但由於跳轉前的函式執行位置來不及去用 setjmp 進行記錄，因此便會造成程式執行結果不符合預期
在原程式碼中，在每一次 longjmp 前，都會用 setjmp 儲存當前函式進行的進度

if (setjmp(env) == 0) {
    task_add(&tasklist, env);
    longjmp(sched, 1);
}

ucontext_t 需要儲存所有暫存器的資料，而 jmp_buf 只需要儲存有用到的暫存器即可，因此 ucontext_t 會比 jmp_buf 大不少

對照 cserv 的 coroutine (也叫做 coro) 實作，裡頭的 context 切換成本較低，且考慮到排程。

jserv

在 setjmp 中，有介紹 sigsetjmp 會另外紀錄 signal mask， 之後再用 siglongjmp 回到記錄點

一開始，在程式當中加入每隔一段時間會觸發訊號，而結果發生問題

Task 0: n = 0
Task 0: n = 0
signal
Task 1: n = 3
Task 0: complete 0
Task 0: complete 0
signal
Task 1: resume 0
Task 1: resume 1
Task 1: resume 1
signal
Task 1: resume 2
Task 1: complete 3
Task 1: complete 3
signal