# 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; } ``` --- ## 測驗二 ## 測驗三 ## 測驗四
Last changed by  
 
SPFishcool
163

Read more

4/16 一對一問題回復

linux 核心的 list_sort 實作考量 在 linux 核心的 list_sort 使用 buttom-up merge sort 實作排序，buttom-up 與 top-down 的差異在於 buttom-up 少了 partition 這一步驟。 此作法可以省去 recursive 和 stack 的使用（會佔用大量記憶體的寫法，並且會較常去 catch 記憶體更新 cache 內容） 其效能比較根據如下（q_sort 為 lab0-c 實作之排序）： q_sort#nodecache-missesbranchesinstructionscontext-switch1000346977,9884516,04010100003,3403621,93744305,89500100000543,05326326,21194,3295,3471010000007491,55474,6974,191731,6153,305510 list_sort#nodecache-missesbranchesinstructionscontext-switch1000248977,7798519,92400100004,1257614,20284329,38450100000439,19226258,06964,3642,0292310000005824,68914,6028,350731,6579,34489

5/8/2023
2023q1 Homework1 (lab0)

contributed by < SPFishcool > 開發環境 $ neofetch --stdout OS: Ubuntu 22.04.1 LTS x86_64 Host: GL552VW 1.0 Kernel: 5.15.0-60-generic Uptime: 13 hours, 20 mins Packages: 1877 (dpkg), 9 (snap) Shell: bash 5.1.16

4/16/2023
2023q1 Homework3 (fibdrv)

contributed by < SPFishcool > 開發環境 $ neofetch --stdout fico@fico-mac ------------- OS: Arch Linux ARM aarch64 Host: Apple MacBook Air (13-inch, M2, 2022) Kernel: 6.1.0-asahi-2-2-ARCH Uptime: 12 mins

3/20/2023
2023q1 Homework2 (quiz2)

contributed by < SPFishcool > 測驗一 運作原理 程式裡 next_pow2(x) 要找出最接近且大於等於 x 的 2 的冪次方的值。 在改寫程式裡，有著幾行類似下方的程式碼。 x |= x >> 1; 這會讓 x 右移一位並將 1 set 到原本的 x 上，例如： 00100000 變成 00110000、 00100110 變成 00110111。

3/13/2023
Read more from SPFishcool
Published on HackMD