# 2023q1 Homework6 (quiz6)
contributed by < `SPFishcool` >
## 開發環境
```bash
$ neofetch --stdout
fico@fico-mac
-------------
OS: Arch Linux ARM aarch64
Host: Apple MacBook Air (13-inch, M2, 2022)
Kernel: 6.2.0-asahi-11-1-edge-ARCH
Uptime: 16 hours, 7 mins
Packages: 1235 (pacman)
Shell: zsh 5.9
Resolution: 2560x1600
DE: Plasma 5.27.4
WM: KWin
Theme: [Plasma], Breeze [GTK2/3]
Icons: [Plasma], breeze [GTK2/3]
Terminal: konsole
Terminal Font: Source Code Pro Semibold 16
CPU: (8) @ 2.424GHz
Memory: 4706MiB / 15649MiB
$ gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/aarch64-unknown-linux-gnu/12.1.0/lto-wrapper
Target: aarch64-unknown-linux-gnu
Configured with: /build/gcc/src/gcc/configure --enable-languages=c,c++,fortran,go,lto,objc,obj-c++ --enable-bootstrap --prefix=/usr --libdir=/usr/lib --libexecdir=/usr/lib --mandir=/usr/share/man --infodir=/usr/share/info --with-bugurl=https://github.com/archlinuxarm/PKGBUILDs/issues --with-linker-hash-style=gnu --with-system-zlib --enable-__cxa_atexit --enable-checking=release --enable-clocale=gnu --enable-default-pie --enable-default-ssp --enable-gnu-indirect-function --enable-gnu-unique-object --enable-linker-build-id --enable-lto --enable-plugin --enable-shared --enable-threads=posix --disable-libssp --disable-libstdcxx-pch --disable-multilib --disable-werror --host=aarch64-unknown-linux-gnu --build=aarch64-unknown-linux-gnu --with-arch=armv8-a --enable-fix-cortex-a53-835769 --enable-fix-cortex-a53-843419
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 12.1.0 (GCC)
```
## 測驗一
### 程式原理分析
struct 結構：
- `struct task`
- `struct arg`
function：
- `task_add`
- `task_switch`
- `schedule`
- `fib_sequence`
- `task0`、`task1`
測驗一的程式碼運用 `setjmp`、`longjmp` 來執行分時多工，根據 man page 的敘述，`setjmp` 會使用 `jmpbuf` 物件設置跳躍 label，當執行 `setjmp(jmpbuf)` 時此函數會返回 `0`，當呼叫 `longjmp(jmpbuf, val)` 時會跳回 `setjmp` 設置的 label 並將此次 `setjmp` 的返回值設為 `val`。
在 `task0`、`task1` 代表要執行的任務，函式內運用下列的敘述來實現 Coroutine 的 await 和 yield
```c
for (; task->i < task->n; task->i++) {
if (setjmp(task->env) == 0) {
printf("%s %d\n", task->task_name, task->i);
task_add(task);
task_switch();
}
task = cur_task;
printf("%s: resume\n", task->task_name);
}
```
在這裡可以看到，當第一次進入迴圈時，會先 `setjmp`，當完成第一次任務便會將 task 加到 `list_head` 的後面，接下來 `task_switch` 再將目前第一個 `task` 取出並用 `longjmp` 跳到下一個 `task` 的迴圈內，而 `longjmp` 會跳到程式碼內 `setjmp` 的位置並回傳 `1`，所以不會進入 `if` 內部，而下一個迴圈會再重新設置一次 `setjmp`。
```c
static void task_switch()
{
if (!list_empty(&tasklist)) {
struct task *t = list_first_entry(&tasklist, struct task, list);
list_del(&t->list);
cur_task = t;
longjmp(t->env, 1);
}
}
```
當我再思考 `setjmp` 與 `longjmp` 使用時記憶體配置的問題時，決定試試 valgrind 測試 memory leak。
```bash
valgrind --tool=memcheck --leak-check=full --show-leak-kinds=all ./coroutine
```
```
==9442== 352 bytes in 1 blocks are still reachable in loss record 1 of 3
==9442== at 0x4865408: malloc (in /usr/lib/valgrind/vgpreload_memcheck-arm64-linux.so)
==9442== by 0x120F83: task1 (coroutine.c:110)
==9442== by 0x120C33: schedule (coroutine.c:54)
==9442== by 0x1211B7: main (coroutine.c:152)
==9442==
==9442== 352 bytes in 1 blocks are indirectly lost in loss record 2 of 3
==9442== at 0x4865408: malloc (in /usr/lib/valgrind/vgpreload_memcheck-arm64-linux.so)
==9442== by 0x120DF7: task0 (coroutine.c:77)
==9442== by 0x120C33: schedule (coroutine.c:54)
==9442== by 0x1211B7: main (coroutine.c:152)
==9442==
==9442== 704 (352 direct, 352 indirect) bytes in 1 blocks are definitely lost in loss record 3 of 3
==9442== at 0x4865408: malloc (in /usr/lib/valgrind/vgpreload_memcheck-arm64-linux.so)
==9442== by 0x120DF7: task0 (coroutine.c:77)
==9442== by 0x120C33: schedule (coroutine.c:54)
==9442== by 0x1211B7: main (coroutine.c:152)
```
偶然發現執行程式有 memory leak 的問題，發現程式碼內部有 `malloc task` 卻沒有 `free`，因此推測這些 memory leak 應該是這個問題，因此當我再 task 結束時 `free` 掉已經結束的 task。
```c
printf("%s: complete\n", task->task_name);
free(task);
longjmp(sched, 1);
}
```
在執行一次 `valgrind`。
```
==9522== All heap blocks were freed -- no leaks are possible
```
之後測試發現這個程式碼有一個限制，就是 task function 不可宣告會變化的區域變數（除了 `const`），因為同一種 task function 的 task 會共享這些變數，以下我將`task0` 迴圈內的 `i` 改成區域變數：
```c
for (int i = 0; i < 10; i++) {
if (setjmp(task->env) == 0) {
printf("%s's i = %d\n", task->task_name, i);
task_add(task);
task_switch();
}
task = cur_task;
printf("%s: resume\n", task->task_name);
}
```
發現輸出變成
```
Task 0's i = 1
Task 1: resume
Task 1's i = 2
Task 2: resume
Task 2 1
Task 0: resume
Task 0's i = 3
Task 1: resume
Task 1's i = 4
Task 2: resume
Task 2 2
Task 0: resume
Task 0's i = 5
Task 1: resume
Task 1's i = 6
Task 2: resume
Task 2 3
Task 0: resume
Task 0's i = 7
Task 1: resume
Task 1's i = 8
Task 2: resume
Task 2 4
Task 0: resume
Task 0's i = 9
Task 1: resume
Task 1: complete
```
而 `struct task` 內部也只有 `n` 和 `i` 兩個整數宣告，代表 task 的架構被變數數量綁死了。
為了增加 task function 變數宣告的彈性，學生覺得可以在 `struct task` 內部加入 `void **var`，`void *` 是一個未宣告任何資料形態的指標，因此可以將 `void **` 視為 pointer to pointer to any 的二維陣列，建立一個 `void **` 存取指向各個不同類型的陣列。
```c
struct task {
jmp_buf env;
struct list_head list;
char task_name[10];
void **var; //variable array
};
struct arg {
void **var; //variable array
char *task_name;
};
```
因為這個變數是有彈性的，因此可以額外寫一個建構 task's arg alloc & free function，以 task0 為例：
```c
void **task0_arg(int i, int n)
{
void **arg = malloc(sizeof(void *) * 2);
arg[0] = malloc(sizeof(int) * 2);
arg[1] = malloc(sizeof(long long) * n);
((int *)arg[0])[0] = i;
((int *)arg[0])[1] = n;
((long long *)arg[1])[0] = 0;
((long long *)arg[1])[1] = 1;
return arg;
}
```
:::warning
程式碼縮排使用 4 個空白字元
:notes: jserv
:::
```c
void task0_free(struct task *task)
{
free(task->var[0]);
free(task->var[1]);
free(task->var);
free(task);
}
```
我將 `task0` 的參數配置改成：
- `arg[0][0]`: i
- `arg[0][1]`: n
- `arg[1]`: fibonacci array
不過使用這種方法，建構 task 時就會需要注意每一組陣列的形態，使用時也需要提供資料形態的資訊。
```c
for (;((int *)task->var[0])[0] < ((int *)task->var[0])[1]; ((int *)task->var[0])[0] += 2) {
if (setjmp(task->env) == 0) {
long long res = fib_sequence(((int *)task->var[0])[0], ((long long *)task->var[1]));
printf("%s fib(%d) = %lld\n", task->task_name, ((int *)task->var[0])[0], res);
task_add(task);
task_switch();
}
task = cur_task;
printf("%s: resume\n", task->task_name);
}
```
編譯執行後達到預期輸出
```
Task 0: n = 0
Task 1: n = 1
Task 2: n = 70
Task 0 fib(0) = 0
Task 1 fib(1) = 1
Task 2 0
Task 0: resume
Task 0 fib(2) = 1
Task 1: resume
Task 1 fib(3) = 2
Task 2: resume
Task 2 1
...
Task 0 fib(68) = 72723460248141
Task 1: resume
Task 1 fib(69) = 117669030460994
Task 2: resume
Task 2 34
Task 0: resume
Task 0: complete
Task 1: resume
Task 1: complete
Task 2: resume
Task 2 35
...
Task 2: resume
Task 2 68
Task 2: resume
Task 2 69
Task 2: resume
Task 2: complete
```
優點：變數宣告較具彈性
缺點：task 建立需要更謹慎，撰寫比較困難
### minicoro 探討與分析
在 [minicoro](https://github.com/edubart/minicoro/blob/main/minicoro.h) 裡面有針對 cpu 種類對其做分類，某些程式碼對於不同 cpu 有不同程式碼，因此我針對我的 cpu 類型 - aarch64 找到其部份程式碼，並發現有幾行 inline assembly 程式碼。
#### a64 architecture register
在理解 inline assembly 時，參考了一下 [Learn the architecture - A64 Instruction Set Architecture](https://developer.arm.com/documentation/102374/0101/Registers-in-AArch64---general-purpose-registers) 認識 aarch64 暫存器的架構
在 aarch64 有 32 顆 一般目的暫存器（Generate Purpose Register），每一顆都可以當作 64-bit (`X0`~`X31`) 和 32-bit (`W0`~`W31`) 暫存器使用，只需要在操作上決定是 x 或 w 即可。
```armasm
ADD X0, X1, X2
```
> 64-bit 加法操作
```armasm
ADD W0, W1, W2
```
> 32-bit 加法操作
另外還有一組 32 顆專門運算浮點數以及向量的暫存器，這一組也可以當作 8-bit ( `B0` )、16-bit( `H0` )、32-bit ( `S0` )、64-bit ( `D0` )、128-bit ( `Q0` ) 浮點數和向量 ( `v0` )
```armasm
FADD S0, S1, S2
```
如果將這些視作向量暫存器（ `v0` ），則可以將 128-bit 當作多個獨立的數值，就可以這樣寫：
```armasm
FADD V0.2D, V1.2D, V2.2D
```
也可以做整數操作
```armasm
ADD V0.2D, V1.2D, V2.2D
```
還有 `sp`(stack pointer)、`xzr`(64-bit zero register)、`wzr`(32-bit zero register)、`LR`(Link Register) 等特殊用途暫存器。
#### minicoro inline assembly
接下來可以看看程式碼
```c
int _mco_switch(_mco_ctxbuf* from, _mco_ctxbuf* to);
__asm__(
".text\n"
#ifdef __APPLE__
".globl __mco_switch\n"
"__mco_switch:\n"
#else
".globl _mco_switch\n"
".type _mco_switch #function\n"
".hidden _mco_switch\n"
"_mco_switch:\n"
#endif
" mov x10, sp\n"
" mov x11, x30\n"
" stp x19, x20, [x0, #(0*16)]\n"
" stp x21, x22, [x0, #(1*16)]\n"
" stp d8, d9, [x0, #(7*16)]\n"
" stp x23, x24, [x0, #(2*16)]\n"
" stp d10, d11, [x0, #(8*16)]\n"
" stp x25, x26, [x0, #(3*16)]\n"
" stp d12, d13, [x0, #(9*16)]\n"
" stp x27, x28, [x0, #(4*16)]\n"
" stp d14, d15, [x0, #(10*16)]\n"
" stp x29, x30, [x0, #(5*16)]\n"
" stp x10, x11, [x0, #(6*16)]\n"
" ldp x19, x20, [x1, #(0*16)]\n"
" ldp x21, x22, [x1, #(1*16)]\n"
" ldp d8, d9, [x1, #(7*16)]\n"
" ldp x23, x24, [x1, #(2*16)]\n"
" ldp d10, d11, [x1, #(8*16)]\n"
" ldp x25, x26, [x1, #(3*16)]\n"
" ldp d12, d13, [x1, #(9*16)]\n"
" ldp x27, x28, [x1, #(4*16)]\n"
" ldp d14, d15, [x1, #(10*16)]\n"
" ldp x29, x30, [x1, #(5*16)]\n"
" ldp x10, x11, [x1, #(6*16)]\n"
" mov sp, x10\n"
" br x11\n"
#ifndef __APPLE__
".size _mco_switch, .-_mco_switch\n"
#endif
);
```
上方程式碼是 `_mco_switch` 的 inline assembly，其中最多使用的指令為 `stp` 和 `ldp`。
- `stp`：可以一次將兩個暫存器資料移到指定記憶體位址，以下方程式為例，`x` 如之前所說是 `64-bit` 暫存器資料，因此這行程式碼會將 `x19` 和 `x20` 裡面存取的資料放到 `x0 + (0 * 16)` 的位置上。
```armasm
stp x19, x20, [x0, #(0 * 16)]
```
- `ldp`：與 `stp` 相反，會將 `x1 + (0 * 16)` 位置的資料存到 `x19` 和 `x20` 兩個暫存器上。
```armasm
ldp x19, x20, [x1, #(0*16)]
```
在 aarch64 架構中，函式的參數會依序放到 `x0` ~ `x3` 裏面，若超過數量則會將剩下的參數存至 stack 中，`_mco_switch` 將兩個 `_mco_ctxbuf` 作為輸入，因此 `x0` 為 `_mco_ctxbuf *from`，`x1` 為 `_mco_ctxbuf *to`。
而 `_mco_ctxbuf` 為以下結構，可以看出來它將暫存器數據都存在裡面
```c
// context information
typedef struct _mco_ctxbuf {
void *x[12]; /* x19-x30 */
void *sp;
void *lr;
void *d[8]; /* d8-d15 */
} _mco_ctxbuf;
```
而這行 inline assembly 做的事就是將暫存器的數據依序放到 `_mco_ctxbuf` 裡面來，並把要切換的 `_mco_ctxbuf` 載入暫存器當中，裡面的資訊包括 `sp` ( stack pointer ) 和 `lr`（ link register, `x30` ），完成 context switch 後使用 `br` 跳至切換後的 link register，因此可以做到 coroutine 與 main function 之間 switch 的功用。
```c
mco_result mco_resume(mco_coro* co) {
if(!co) {
MCO_LOG("attempt to resume an invalid coroutine");
return MCO_INVALID_COROUTINE;
}
if(co->state != MCO_SUSPENDED) { /* Can only resume coroutines that are suspended. */
MCO_LOG("attempt to resume a coroutine that is not suspended");
return MCO_NOT_SUSPENDED;
}
co->state = MCO_RUNNING; /* The coroutine is now running. */
_mco_jumpin(co);
return MCO_SUCCESS;
}
```
要切換進入 ( `resume` ) 到一個 corotine function 時，他會先檢查狀態是否為 `MCO_SUSPENDED`， 並設定成 `MCO_RUNNING`，並呼叫 `_mco_jumpin` 正式跳入 coroutine。
```c
static void _mco_jumpin(mco_coro* co) {
_mco_context* context = (_mco_context*)co->context;
_mco_prepare_jumpin(co);
_mco_switch(&context->back_ctx, &context->ctx); /* Do the context switch. */
}
```
在 `_mco_jumpin` 會使用 `_mco_switch` 將目前的 context 紀錄到 `mco_coro` 裡 `context` 的 `back_ctx` ( `back_ctx` 的作用就是在 `jumpin` 時將跳躍點記下來，好讓 yield 時跳回原來的地方)。
```c
typedef struct _mco_context {
#ifdef MCO_USE_VALGRIND
unsigned int valgrind_stack_id;
#endif
_mco_ctxbuf ctx;
_mco_ctxbuf back_ctx;
} _mco_context;
```
而跳出（ `yield` ）coroutine function 時基本上跟 `resume` 相反，檢查狀態是否為 `MCO_RUNNING` 並設置為 `MCO_SUSPENDED`，然後呼叫 `_mco_jumpout` 跳出。
```c
mco_result mco_yield(mco_coro* co) {
if(!co) {
MCO_LOG("attempt to yield an invalid coroutine");
return MCO_INVALID_COROUTINE;
}
#ifdef MCO_USE_ASYNCIFY
/* Asyncify already checks for stack overflow. */
#else
/* This check happens when the stack overflow already happened, but better later than never. */
volatile size_t dummy;
size_t stack_addr = (size_t)&dummy;
size_t stack_min = (size_t)co->stack_base;
size_t stack_max = stack_min + co->stack_size;
if(co->magic_number != MCO_MAGIC_NUMBER || stack_addr < stack_min || stack_addr > stack_max) { /* Stack overflow. */
MCO_LOG("coroutine stack overflow, try increasing the stack size");
return MCO_STACK_OVERFLOW;
}
```
---
## 測驗二
## 測驗三
## 測驗四
Sign in with Wallet
Connect another wallet