# 2022q1 Homework4 (quiz4)
contributed by < `Kevin-Shih` >
執行環境
:::spoiler lscpu
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i5-7300HQ CPU @ 2.50GHz
Stepping: 9
CPU MHz: 2500.000
CPU max MHz: 3500.0000
CPU min MHz: 800.0000
BogoMIPS: 4999.90
Virtualization: VT-x
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 6 MiB
NUMA node0 CPU(s): 0-3
:::
:::spoiler gcc version
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0
:::
---
## 測驗 1
**題目**
已知輸入必為大於 `0` 的數值 (即 `x > 0`)，以下程式碼可計算
$⌈log2(x)⌉$，也就是 ceil 和 log2 的組合並轉型為整數:
```c=
int ceil_log2(uint32_t x)
{
uint32_t r, shift;
x--;
r = (x > 0xFFFF) << 4;
x >>= r;
shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;
shift = (x > 0xF) << 2;
x >>= shift;
r |= shift;
shift = (x > 0x3) << 1;
x >>= shift;
return (EXP1) + 1; // EXP1 = r | shift | x >> 1
}
```
請補完，使其行為符合預期。
- `EXP1` 為表示式，限制使用 `^`, `&`, `|`, `<<`, `>>` 這幾個運算子，可能會出現常數
#### 運作原理與解題
與第三週測驗 `7` 的原理十分相近，但加上取 `ceil` 的功能，回傳值處的 `+ 1` 就是用來處理 `ceil` 的。 同時因為是向上取整的緣故，當 `x` 正好等於 2 的冪時 `log2` 已是整數不應 `+ 1` 故透過 `x--` 處理，見下方公式。
$$
\begin{split}
⌈log2(x)⌉&=
\begin{cases}
ilog2(x), &\forall n \in \mathbb{N}, x=2^n\\
ilog2(x) + 1, &\forall n \in \mathbb{N}, \forall x \in \mathbb{N^+}, x\ne2^n
\end{cases}
\\ &=\ ilog2(x - 1) + 1,\ \forall x \in \mathbb{N^+}, x\ne1
\end{split}
$$
> 忽略 `x = 1` 此程式碼對於該情形輸出錯誤答案，正解應為 `0`，但輸出恆大於等於 `1` (因 return 時 `+ 1`)
#6 ~ #7 當 `x` 的 first set 在高位的 16 bits 中， `x` 會右移 16 bits 並在剩下的 16 bits 繼續找 first set ， `r` 則設為 16。 若不是的話， `r` 會為 0 不影響後續步驟。 (會變成找低位的 16 bits 中使否有 first set)
#8 ~ #10 則是找在剩下的 16 bits 中 `x` 的 first set 是否在較高的 8 bits 中，若有 `x` 會再右移 8 bits 並在剩下的 8 bits 繼續找 first set ， `r` 則加上 8。
#11 ~ #13, #14 ~ #15 以此類推尋找剩下的 8 bits 及 4 bits。
由於最後 #15 做完的 `shift` 尚未加到 `r` 中，因此 `EXP1` 前半為 `r | shift`，而剩下的 2 bits 尚未尋找故 `EXP1` 還要修改為 `r | shift | x >> 1`，即當 x 的 first set 在 2 bits 中的高位要再加 1 。
#### 改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless
根據 [logarithm](https://en.wikipedia.org/wiki/Logarithm#Definition) 的數學定義 “The logarithm of a positive real number x with respect to base b” ，可以看出 log(x) 的定義域為 `x > 0` ，因此 `x = 0` 屬於未定義的情形。
若根據 [log](https://man7.org/linux/man-pages/man3/log.3.html), [log2](https://man7.org/linux/man-pages/man3/log2.3.html#RETURN_VALUE) 的 manual page，“If x is zero, then a pole error occurs, and the functions return -HUGE_VAL.” ，同樣顯示 `x = 0` 同樣不在該函數的定義域，應無法以 branchless 實做，而是產生對應的錯誤訊息。
#### 在 Linux 核心原始程式碼找出 ceil 和 log2 的組合 (類似的形式)，並解說應用案例 (提示: 在 Linux 核心排程器就有)
在下列的 [kernel/sched/fair.c](https://github.com/torvalds/linux/blob/master/kernel/sched/fair.c#L196) 程式碼片段中有出現類似的形式 `1 + ilog2(cpus)` ，用於一段更新一些 `tunable parameters` 的函數，其中一種 policy 採用與 cpu 數量成對數關係的預測方式。
```c
/*
* Increase the granularity value when there are more CPUs,
* because with more CPUs the 'effective latency' as visible
* to users decreases. But the relationship is not linear,
* so pick a second-best guess by going with the log2 of the
* number of CPUs.
*
* This idea comes from the SD scheduler of Con Kolivas:
*/
static unsigned int get_update_sysctl_factor(void)
{
unsigned int cpus = min_t(unsigned int, num_online_cpus(), 8);
unsigned int factor;
switch (sysctl_sched_tunable_scaling) {
case SCHED_TUNABLESCALING_NONE:
factor = 1;
break;
case SCHED_TUNABLESCALING_LINEAR:
factor = cpus;
break;
case SCHED_TUNABLESCALING_LOG:
default:
factor = 1 + ilog2(cpus);
break;
}
return factor;
}
```
---
## 測驗 2
**題目**
改寫第 3 週測驗題的測驗 `11` 裡頭的 fls 函式 (fls 意謂 “find last set”)，使其得以計算 Find first set:
```c
#define BITS_PER_BYTE 8
#define BITS_PER_LONG (sizeof(unsigned long) * BITS_PER_BYTE)
#include <stddef.h>
static inline size_t ffs(unsigned long x)
{
if (x == 0)
return 0;
size_t o = 1;
unsigned long t = ~0UL;
size_t shift = BITS_PER_LONG;
shift >>= 1;
t >>= shift;
while (shift) {
if ((EXP2) == 0) { // EXP2 = x & t
x >>= shift;
EXP3; // EXP3 = o += shift
}
shift >>= 1;
t >>= shift;
}
return o;
}
```
請補完，使其行為符合預期。
- `EXP2` 和 `EXP3` 限制使用 `^`, `&`, `|`, `<<=`, `>>=`, `+=`, `-=` 這幾個運算子，可能會出現常數
#### 運作原理與解題
後續的程式碼負責處理 x >= 1 的情形，ffs 至少為 1，因此回傳值 `o` 先初始化為 `1`，`shift` 則設為 `BITS_PER_LONG / 2` 並將 `t` 右移 `shift` 得到低位半邊全為 `1` 的 unsigned long，用於後續找尋 ffs 在高位的半邊或低位的半邊。
> 透過 BITS_PER_LONG 可以克服 LP64, LLP64 等 unsigned long 長度不同的問題。
if 的部分，`t` 作為 mask 用於判斷 ffs 是否位於低位的半邊(`f` 在低位半邊全為 `1`，高位半邊全為 `0`)，若是不在低位半邊，則 `x` 向左移 `x` 長度的一半(即 `shift`)並將 `o` 加上 `shift`。 因此 `EXP2` = `x & t`， `EXP3` = `o += shift`。
而不論 if condition 是否成立，`shift` 都會除 2，而 `t` 右移一半的長度，以繼續搜尋 `x` 剩下的半邊直到 `shift` 歸零。
#### 迴避 while, for, goto 等關鍵字以改寫出功能等價的實作
```c
#define BITS_PER_BYTE 8
#define BITS_PER_LONG (sizeof(unsigned long) * BITS_PER_BYTE)
#include <stddef.h>
static inline size_t myffs(unsigned long x)
{
if (x == 0)
return 0;
size_t ret = 1;
unsigned long t = ~0UL;
size_t shift = BITS_PER_LONG >> 1, m;
t >>= shift;
m = ((x & t) == 0) * shift;
x >>= m;
ret += m;
shift >>= 1;
t >>= shift;
m = ((x & t) == 0) * shift;
x >>= m;
ret += m;
shift >>= 1;
t >>= shift;
m = ((x & t) == 0) * shift;
x >>= m;
ret += m;
shift >>= 1;
t >>= shift;
m = ((x & t) == 0) * shift;
x >>= m;
ret += m;
shift >>= 1;
t >>= shift;
m = ((x & t) == 0) * shift;
x >>= m;
ret += m;
shift >>= 1;
/**
* For LP64 shift = 1, check if ffs at higherend
* of last two bits then `ret` += 1.
* for LLP64 shift = 0, ignore this line
*/
ret += ((x & 1) == 0) & shift;
return ret;
}
```
透過將 while loop 展開並針對 LP64, LLP64 的不同改寫了最後一行，當 `BITS_PER_LONG` 為 32 執行到最後一行時 `shift = 0` ，透過與 `shift` 作 `AND` 運算避免勿加多餘的數；而對於 `BITS_PER_LONG` 為 64 者則透過該行檢驗 ffs 在剩餘的 2 bits 中的高位或低位並加上對應的數值 `0` 或 `1`。
另外在中間的部份加入新的變數 `m` 方便拿掉 `if` 進可能減少 branch 次數，實現方式類似測驗 `1` ，但為了同時適用 LP64, LLP64 做了一些修改。
> `m = ((x & t) == 0) * shift` 類似 `r = (x > 0xFFFF) << 4`
**測試 myffs**
加入下方 main function 方便測試是否正確
```c
int main(int argc, char **argv){
printf("ffs = %ld\n", myffs(atol(argv[1])));
return 0;
}
```
編譯後執行結果
```
$ gcc -o q2 q2.c
$ ./q2 2
ffs = 2
$ ./q2 1
ffs = 1
$ ./q2 64
ffs = 7
$ ./q2 258
ffs = 2
// 5120 = 0b1010000000000
$ ./q2 5120
ffs = 11
```
正確！
#### 在 Linux 核心原始程式碼的 [include/asm-generic/bitops](https://github.com/torvalds/linux/tree/master/include/asm-generic/bitops) 目錄找出相關程式碼，並探討應用案例
在 [include/asm-generic/bitops/__ffs.h](https://github.com/torvalds/linux/blob/master/include/asm-generic/bitops/__ffs.h) 中有相近的實做。
相關的應用在很多地方都有出現
- 音效相關
- [sound/soc/codecs/rt1011.c](https://github.com/torvalds/linux/blob/master/sound/soc/codecs/rt1011.c#L1950)
- [sound/soc/codecs/rt1019.c](https://github.com/torvalds/linux/blob/master/sound/soc/codecs/rt1019.c#L444)
- [sound/soc/codecs/tas2562.c](https://github.com/torvalds/linux/blob/master/sound/soc/codecs/tas2562.c#L197)
- 各種型號的 codec 中很多...
- 網路相關
- [drivers/net/wireless/realtek/rtw88/coex.c](https://github.com/torvalds/linux/blob/master/drivers/net/wireless/realtek/rtw88/coex.c#L3688)
- [drivers/net/wireless/realtek/rtw88/tx.c](https://github.com/torvalds/linux/blob/master/drivers/net/wireless/realtek/rtw88/tx.c#L246)
- [drivers/net/ethernet/chelsio/cxgb4/sge.c](https://github.com/torvalds/linux/blob/master/drivers/net/ethernet/chelsio/cxgb4/sge.c#L4292)
- [drivers/net/ethernet/sfc/falcon/falcon.c](https://github.com/torvalds/linux/blob/master/drivers/net/ethernet/sfc/falcon/falcon.c#L1909)
- 各種 有線 / 無線 網路相關 drvier ...
- GPU drm 相關
- [drivers/gpu/drm/nouveau/nvkm/engine/fifo/tu102.c](https://github.com/torvalds/linux/blob/master/drivers/gpu/drm/nouveau/nvkm/engine/fifo/tu102.c#L137)
- [drivers/gpu/drm/nouveau/nvkm/subdev/ltc/gp100.c](https://github.com/torvalds/linux/blob/master/drivers/gpu/drm/nouveau/nvkm/subdev/ltc/gp100.c#L34)
- [drivers/gpu/drm/nouveau/nvkm/subdev/ltc/gm107.c](https://github.com/torvalds/linux/blob/master/drivers/gpu/drm/nouveau/nvkm/subdev/ltc/gm107.c#L97)
- ...
---
## 測驗 3
**題目**
考慮以下改寫自 Linux 核心的程式碼:
```c
struct foo_consumer {
int (*handler)(struct foo_consumer *self, void *);
struct foo_consumer *next;
};
struct foo {
struct foo_consumer *consumers;
unsigned long flags;
};
#include <stdbool.h>
/*
* For foo @foo, delete the consumer @fc.
* Return true if the @fc is deleted sfccessfully
* or return false.
*/
static bool consumer_del(struct foo *foo, struct foo_consumer *fc)
{
struct foo_consumer **con;
bool ret = false;
for (con = &foo->consumers; *con; EXP4) { // EXP4 = `con = &(*con)->next`
if (*con == fc) {
*con = EXP5; // EXP5 = fc->next
ret = true;
break;
}
}
return ret;
}
```
請補完，使 consumer_del 行為符合註解規範。
- `EXP4` 和 `EXP5` 都包含指標操作 (如 `->`)
#### 運作原理與解題
for loop 會依序走訪 foo->consumers 中所有的 foo_consumer，因此作為迴圈變數的 indirect pointer `con` 應該每次都指向 儲存下一個 foo_consumer 指標的位置，因此 `EXP4` = `con = &(*con)->next`。
而 `EXP5` 所在的 if 敘述中是將符合的 foo_consumer 從 linked list 中移除並將 `ret` 設為 `true` 表示正確移除，因此要將 `*con` 也就是前一個 fc 的 next 設為 fc->next 來跳過要刪除的 fc。 因此 `EXP5` = `fc->next`。
:::warning
TODO
- 在 Linux 核心原始程式碼相似技巧的程式碼 (例如 [uprobe](https://docs.kernel.org/trace/uprobetracer.html))，並探討應用案例
:::
#### 區分 foo 和 foo_consumer 的好處
將 `foo` 作為容器， `foo_consumer` 作為內容物，明確區分兩者的功能有助於管理及使用，`foo` 作為容器包含了 `foo_consumer` 這一系列內容物的起始位置及一組 flags 標注內含的所有 `foo_consumer` 的狀態；`foo_consumer` 作為內容物以 linked list 的方式串起一系列的 `foo_consumer` ，當需要走訪節點時就不需要上到 `foo` 的層級，以 `foo_consumer` 作為 entry 走訪即可得到個節點的資料。
---
## 測驗 4
**題目**
以下嘗試用 lab0 提及的 `setjmp` 和 `longjmp`，用以實作〈[你所不知道的 C 語言: goto 和流程控制篇](https://hackmd.io/@sysprog/c-control-flow)〉闡述的 [coroutine](https://en.wikipedia.org/wiki/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
```
> n = 3 似乎應該各印出 3 次 resume 才對
:::spoiler 原始程式碼 (檔名 `jmp.c`)
```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);
EXP6; // EXP6 = 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);
EXP7; // EXP7 = 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);
EXP8; // EXP8 = 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);
EXP9; // EXP9 = 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;
}
```
請補完，使行為符合註解規範。
:::
- `EXP6` 和 `EXP7` 都包含 List API 的使用
- `EXP8` 和 `EXP9` 應有函式呼叫
#### 運作原理與解題
執行這個程式時，`registered_task` 是包含 `task0`, `task1` 兩個 function designator 的陣列，`ntask` 表示 `registered_task` 中包含的 function designator 數量。 接著 `main` 會呼叫 `schedule()`。
> 根據 C99 [ 6.5.3.2-4 ] 所述：
> The unary * operator denotes indirection. If the operand points to a function, the result is a function designator
> 因此 (*registered_task[]) 是 function designator 的陣列
> 又根據 C99 [ 6.3.2.1 ]：
> A function designator is an expression that has function type. Except when it is the operand of the `sizeof` operator) or the unary `&` operator, a function designator with type ‘‘function returning type’’ is converted to an expression that has type ‘‘pointer to function returning type’’.
> `tasks` 是 pointer to pointer to function returning type 而 `registered_task` 也是 pointer to pointer to function returning type 因此可以直接 assign。
**schedule()**
```c
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);
}
```
先設好 jump_buf 以便跳回來，接著while loop 中依序呼叫 `tasks` 中的 function pointer 將 `task0`, `task1` 都初始化後(見下段)，呼叫 `task_join()` 以便執行 `task0`, `task1` 的內容。
**task0(), task1()**
`task0` 的 code 為例：
```c
/* 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);
EXP8; // EXP8 = 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);
}
```
呼叫後會設置 jump_buf 後會將該 task 加入 `task_list` 並以 longjmp 跳回先前的 `schedule()` 紀錄的位置，因此 `EXP8`, `EXP9` = `longjmp(sched, 1)`。 後續跳回來時 `setjmp` 的回傳值會是由 `longjmp` 所指定的值，這次程式碼中均是 1，因不等於 `0` 故會繼續執行後續的 for loop。
> void longjmp(jmp_buf env, int val);
> After longjmp() is completed, program execution continues as if
the corresponding invocation of setjmp() had just returned the
value specified by val. The longjmp() function shall not cause
setjmp() to return 0; if val is 0, setjmp() shall return 1.
> --[longjmp](https://man7.org/linux/man-pages/man3/longjmp.3p.html) manual
for loop 中會執行 `@arg` 所指定的次數，每次都會先 `setjmp` 後將 task 加入 `tasklist` 並呼叫 `task_switch` 切換到下個 task ，跳回來時會印出 resume。 跳出 for loop 後則會印出 complete 並跳回 `schedule()`。
**task_join**
```c
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);
EXP7; // EXP7 = list_del(&t->list)
memcpy(env, t->env, sizeof(jmp_buf));
free(t);
longjmp(env, 1);
}
}
```
簡單來說跳到 `tasklist` 第一個 entry 對應的位置繼續執行，並刪除第一個 entry。 由 `schedule()` 呼叫。
當 `tasklist` 不為空的時候，取出第一個 entry 將其從 linked list 中移除，並將該 entry 所儲存的 jump_buf 複製到 `env` 後，釋放該 entry 所佔的記憶體空間，最後 `longjmp` 跳到 `env` 對應位置。 因此 `EXP7` = `list_del(&t->list)`。
**task_add**
```c
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);
}
```
將 `setjmp` 所設定的 jump_buf 複製到一個新的 entry 中並將該 entry 排入 `tasklist` 中的末端。
**task_switch**
與 `task_join` 所做的事完全相同，但由 `task0(), task1()` 呼叫。 因此 `EXP6` = `list_del(&t->list)`。
:::warning
TODO
- 對比 [concurrent-programs](https://github.com/sysprog21/concurrent-programs) 裡頭的 coroutine 程式碼，如 [tinync](https://github.com/sysprog21/concurrent-programs/tree/master/tinync) 和 [preempt_sched](https://github.com/sysprog21/concurrent-programs/tree/master/preempt_sched)，嘗試引入 UNIX Signal 來做到 preemptive scheduling
- 對比〈[A brief history of the Linux Kernel’s process scheduler: The very first scheduler, v0.01](https://dev.to/satorutakeuchi/a-brief-history-of-the-linux-kernel-s-process-scheduler-the-very-first-scheduler-v0-01-9e4)〉，解說早期 Linux 核心 CPU 排程器的行為，並利用上述程式碼來模擬
:::
#### 上述 [coroutine](https://en.wikipedia.org/wiki/Coroutine) 實作的限制
因為 `setjmp`, `longjmp` 只恢復了包含 stack pointer, program counter 等暫存器的值，而區域變數 `i` 等 stack 內的 automatic variables 則沒有被保存及復原。
> 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.
> --man setjmp
>
> 以及
> 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 unspeci-fied 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()
> - they are not declared as volatile.
> --man setjmp
因此若將題目中的程式實際執行後會出現下列情形 (為方便比較 n 設為 3)
```
$ gcc -g -o q4 q4.c
$ ./q4
Task 0: n = 3
Task 1: n = 3
Task 0: before longjmp i = 0
Task 1: before longjmp i = 0
Task 0: after longjmp i = 0
Task 0: resume
Task 0: before longjmp i = 1
Task 1: after longjmp i = 1
Task 1: resume
Task 1: before longjmp i = 2
Task 0: after longjmp i = 2
Task 0: resume
Task 0: complete
Task 1: after longjmp i = 21881
Task 1: resume
Task 1: complete
```
不難看出兩個 task 間的 `i` 會互相影響，進而導致錯誤的結果。
而將 `i` 改為 static local variable 則會讓 `i` 從原先自動分配在 call stack 上改為分配在程式的 data segment 上，從而避免 call stack 沒有完整復原導致的錯誤。
修改後程式碼如下
```c
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); // EXP8 = longjmp(sched, 1)
}
static int i;
for (i = 0; i < n; i++) {
printf("Task 0: before jmp i = %d\n", i);
if (setjmp(env) == 0) {
task_add(&tasklist, env);
task_switch(&tasklist);
}
printf("Task 0: after jmp i = %d\n", i);
printf("Task 0: resume\n");
}
printf("Task 0: complete\n");
longjmp(sched, 1);
}
```
執行結果
```
$ gcc -g -o q4 q4.c
$ ./q4
Task 0: n = 3
Task 1: n = 3
Task 0: before jmp i = 0
Task 1: before jmp i = 0
Task 0: after jmp i = 0
Task 0: resume //task 0 resume 1
Task 0: before jmp i = 1
Task 1: after jmp i = 0
Task 1: resume //task 1 resume 1
Task 1: before jmp i = 1
Task 0: after jmp i = 1
Task 0: resume //task 0 resume 2
Task 0: before jmp i = 2
Task 1: after jmp i = 1
Task 1: resume //task 1 resume 2
Task 1: before jmp i = 2
Task 0: after jmp i = 2
Task 0: resume //task 0 resume 3
Task 0: complete
Task 1: after jmp i = 2
Task 1: resume //task 1 resume 3
Task 1: complete
```
正確!
先前 `setjmp`, `longjmp` 的 man page 提到會保存及回復 `values of other registers` ，因此測試一下若是以 inline asm 的方式挪用 `ebx` 存放變數 `i` ，是否可以得到相同結果。
> EBX — Pointer to data in the DS segment
> -- [Intel® 64 and IA-32 Architectures Software Developer's Manual Vol. 1 Chapter 3.4.1](https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-vol-1-manual.pdf) (Page 3-12)
```c
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); // EXP8 = longjmp(sched, 1)
}
register int i asm("ebx");
for (i = 0; i < n; i++) {
printf("Task 0: before jmp i = %d\n", i);
if (setjmp(env) == 0) {
task_add(&tasklist, env);
task_switch(&tasklist);
}
printf("Task 0: after jmp i = %d\n", i);
printf("Task 0: resume\n");
}
printf("Task 0: complete\n");
longjmp(sched, 1);
}
```
編譯並執行
```
$ gcc -g -o q4 q4.c
$ ./q4
Task 0: n = 3
Task 1: n = 3
Task 0: before jmp i = 0
Task 1: before jmp i = 0
Task 0: after jmp i = 0
Task 0: resume //task 0 resume 1
Task 0: before jmp i = 1
Task 1: after jmp i = 0
Task 1: resume //task 1 resume 1
Task 1: before jmp i = 1
Task 0: after jmp i = 1
Task 0: resume //task 0 resume 2
Task 0: before jmp i = 2
Task 1: after jmp i = 1
Task 1: resume //task 1 resume 2
Task 1: before jmp i = 2
Task 0: after jmp i = 2
Task 0: resume //task 0 resume 3
Task 0: complete
Task 1: after jmp i = 2
Task 1: resume //task 1 resume 3
Task 1: complete
```
在我的環境中是可以得到相同結果的。
Sign in with Wallet
Connect another wallet