# 2025q1 Homework3 (kxo)
contributed by < `leonnig` >

## 教材閱讀紀錄

[linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module)

**`__attribute__`** 是 GNU C 提供的一種語法，用來對**函式/變數/型別加上一些額外的屬性**，像是 `noreturn` 、`pure`、`malloc` 等等，而 `alias` 就是其中一種。

// alias ("target")
//The alias attribute causes the declaration to be emitted as an alias for another symbol, which must be specified. For instance,

void __f () { /* Do something. */; }
void f () __attribute__ ((alias ("__f")));

`f()` 是 `__f()` 的別名，不會真的生成 code，而是會轉向 `__f()`。

當 device driver 掛載進入後，使用 `read` 去讀取 kernel space 的資訊，`write` 可以將資料傳送給 kernel space

[<Linux Kernel Module Programming Guide> 閱讀紀錄](https://hackmd.io/@Cool-55/B1rJP9nxgx)

## 將棋盤的畫面呈現移動至使用者層級

參考: [rota1001](https://github.com/sysprog21/kxo/commit/b73de5f1a1bf6914c4c7cba97e1a6e7fab46807e)

我的理解是，在原本的實作中，draw_buffer 會透過 `kfifo_in` 寫到 kfifo 中，它的功用是儲存即將要傳送到 user space 的 data，也就是棋盤的資料。

在原本的 `draw_board` 函式中，先觀察一下程式碼

int i = 0, k = 0;
draw_buffer[i++] = '\n';
smp_wmb();
draw_buffer[i++] = '\n';
smp_wmb();

while (i < DRAWBUFFER_SIZE) {
    for (int j = 0; j < (BOARD_SIZE << 1) - 1 && k < N_GRIDS; j++) {
        draw_buffer[i++] = j & 1 ? '|' : table[k++];
        smp_wmb();
    }
    draw_buffer[i++] = '\n';
    smp_wmb();
    for (int j = 0; j < (BOARD_SIZE << 1) - 1; j++) {
        draw_buffer[i++] = '-';
        smp_wmb();
    }
    draw_buffer[i++] = '\n';
    smp_wmb();
}

可以看到每當進行了 `draw_buffer` 資料的寫入，後面就會接上 `smp_wmb` ，這邊我認為是為了確保當兩邊的 CPU 上的演算法再進行對弈時，要嚴格保證資料的寫入順序。

這段程式碼其實就是在繪製整個棋盤，總共有 4 列，每列包括了 4 個格子以及 3個 `|` 再加上一個換行字符，所以每列總共8個字元，而每列下面也都會有一個分隔線，也是 8 個字元，總計 8*8 加上開頭兩個換行字符共 66 個字元。

每次都會繪製 66 個字元，並且再經由 `produce_board` insert 到 kfifo buffer 中，在傳給 user space，但因為像是棋盤中除了作答的部分在 kernel space 完成以外，其實其他的棋盤部分繪製的任務可以在 user space 完成，便可以節省傳輸的成本。

將原本 `draw_board` 的部分修改成只傳輸對弈過程寫入 `table` 的資料，也就是 16 個答案格，而剩下 66 - 16 個字元則移動到 user space

static int draw_board(char *table)
{
    int i = 0;
      while (i < N_GRIDS){
        draw_buffer[i++] = table[i++];     
        smp_wmb();
    }
    
    return 0;
}

Commit [e904be0](https://github.com/leonnig/kxo/commit/e904be0af6acb2ce37683f867489e706768c83e6#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ec)

## 在對弈過程中顯示當下時間

使用 C 標準函式庫的 [<time.h>](https://pubs.opengroup.org/onlinepubs/7908799/xsh/time.h.html)，我讓時間顯示在使用者層級，所以在 `xo.user.c` 中新增以下

+time_t now;
+struct tm *time_info;
+char t_str[20];

/* Draw the board in user space */
static int draw_board(const char *table)
{
    int i = 0, k = 0;
    printf("\n");
    printf("\n");

    while (i < 4) {
        for (int j = 0; j < (BOARD_SIZE << 1) - 1 && k < N_GRIDS; j++) {
            printf("%c", j & 1 ? '|' : table[k++]);
        }
        printf("\n");
        for (int j = 0; j < (BOARD_SIZE << 1) - 1; j++) {
            printf("%c", '-');
        }
        printf("\n");
        i++;     
    }
    
+   time(&now);
+   time_info = localtime(&now);
+   strftime(t_str, 20, "%Y-%m-%d %H:%M-%S", time_info);
+   printf("\n%s \n", t_str);

    return 0;
}
    

使用 `strftime` 可以客製化的呈現時間的表示方式。

## coroutine

待閱讀教材: [〈並行程式設計：排程器原理〉](https://hackmd.io/@sysprog/concurrency-sched)

## corotine

簡而言之，就是快速的在工作間切換以達到像是同時處理多個工作的感覺


這邊來觀摩 [coro](https://github.com/sysprog21/concurrent-programs/tree/master/coro) 來學習協同式多工

這邊在看程式碼前，先來了解一下 `setjmp` 跟 `longjmp`

### setjmp

int setjmp(jmp_buf env);

此函式能夠在指定位置設定一個目標，而後透過 `longjmp` 轉移到此目標位置。
而 `setjmp()` 會儲存當前執行環境的相關資訊，包括堆疊指標，program counter，可能還包含其他暫存器的值，當呼叫 `setjmp()` 時，會回傳 0。

### longjmp

void longjmp(jmp_buf env, int val);

此函式會利用 `env` 中提供的資訊，把程式控制流程跳回到當初呼叫 `setjmp()` 的位置。
在成功跳回去後，堆疊會恢復成當初呼叫 `setjmp()` 時的狀態，而當 `longjmp` 成功執行後，程式會像是 `setjmp()` 呼叫 `return` 一樣繼續執行。

在 `setjmp()` 第一次被呼叫的時候會回傳 0，再來 `longjmp()` 跳回來的時候，會讓 `setjmp()` 回傳 `longjmp()` 提供的 `val` 參數值。

這邊做個小實驗來體驗一下這兩個函式的使用方式

我們利用 `setjmp()`、`longjmp()` 來實現 c 語言中沒有的 `exception` 功能

#include <stdio.h>
#include <stdlib.h>
#include <setjmp.h>

jmp_buf env;

double compute_avg(double *values, size_t length)
{
    if(length <= 0){
        longjmp(env, 1);
    }

    double sum = 0;
    for (int i=0; i < length; ++i){
        sum += values[i];
    }

    return sum / (double)length;
}

int main(int argc, char **argv){
    int arrlength = argc-1;
    double *darr = malloc(sizeof(double) * arrlength);
    for (int i=1; i < argc; ++i){
        darr[i-1] = atof(argv[i]);
    }

    if (setjmp(env) == 0){
        double avg = compute_avg(darr, arrlength);
        printf("Average = %f\n", avg);
    } else {
        printf("ERROR! Invalid inputs. \n");
    }

    return 0;
}

該程式利用 `setjmp()` 去判斷 `lonngjmp()` 的回傳值，若輸入值 $\leq 0$ 時，會呼叫 `longjmp()` 轉移到 `setjmp()` 的位置，並輸出錯誤訊息。

以下為
> [coro](https://github.com/sysprog21/concurrent-programs/blob/master/coro/coro.c): 使用 setjmp/longjmp

首先定義了結構體 `task` ，其中有兩個成員，分別為用於 `setjmp()` 的 `jmp_buf` `env` 以及用於排程的 `list`。 在 `main` 函式中，`registered_task` 是函式指標陣列，存放本實驗中的的 3 個任務函式指標。

在 `schedule` 中，會先呼叫 `setjmp()`，每當新的任務加進排程，會呼叫 `
longjmp(sched, 1)`， 讓 `schedule()` 可以繼續將新任務增加到排程，`tasks[i++](&arg)` 則是取出當前的任務，並且 `i++` 輪到下一個排程中的任務，接著 `arg` 這個區域變數的指標傳給 coroutine，這樣 coroutine 可以知道自己是哪個任務的參數，最後 `task_switch()` 去執行下一個 coroutine。

可以發現 `while (ntasks-- > 0)`，其實 `schedule` 只有把一開始的 3 個任務加入到循環中就沒他的事了，後續真正的 corotine 是交由 `task_switch` 來執行。

void schedule(void)
{
    static int i;

    setjmp(sched);

    while (ntasks-- > 0) {
        struct arg arg = args[i];
        tasks[i++](&arg);
        printf("Never reached\n");
    }

    task_switch();
}

`task0` 和 `task1` 的結構都一樣，前半段都會先到 `schedule` 執行完 ``` printf("%s: n = %d\n", task->task_name, task->n);``` 後，再用 `task_add()` 加入到 `tasklist` 中，並再次呼叫 `longjmp` 跳回到 `schedule`，直到 `schedule` 的 `ntasks` 都執行完畢，再藉由 `task_switch` 的 ` longjmp(t->env, 1);` 跳回 `task` 執行主要的操作。