# 2024q1 Homework5 (assessment)
contributed by < `nosba0957` >
## 改進測驗題
### 第三週測驗一
計算平方根的原理為
$$
N^2 = (a_n+a_{n-1}+a_{n-2}+...+a_0)^2,\ a_m=2^m \ or \ a_m=0
$$
乘開後得到
$$
\begin{bmatrix}
a_na_n & a_{n-1}a_n & a_{n-2}a_n & ... & a_0a_n\\
a_na_{n-1} & a_{n-1}a_{n-1} & a_{n-2}a_{n-1} & ... & a_0a_{n-1}\\
a_na_{n-2} & a_{n-1}a_{n-2} & a_{n-2}a_{n-2} & ... & a_0a_{n-2}\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
a_na_0 & a_{n-1}a_0 & a_{n-2}a_0 & ... & a_0a_0\\
\end{bmatrix}
$$
分成幾個部分觀察
$$
\begin{bmatrix}
a_na_n
\end{bmatrix} = a_n^2
$$
$$
\begin{bmatrix}
\ & a_{n-1}a_n \\
a_na_{n-1} & a_{n-1}a_{n-1}
\end{bmatrix} = a_{n-1}(2a_n+a_{n-1})
$$
$$
\begin{bmatrix}
\ & \ & a_{n-2}a_n \\
\ & \ & a_{n-2}a_{n-1} \\
a_na_{n-2} & a_{n-1}a_{n-2} &a_{n-2}a_{n-2}
\end{bmatrix} = a_{n-2}(2(a_{n-1}+a_n)+a_{n-2})
$$
所以可以將 $N^2$ 表示為
$$
N^2=a_n^2+a_{n-1}(2a_n+a_{n-1})+a_{n-2}(2(a_n+a_{n-1})+a_{n-2})+...+a_0(\sum_{i=1}^{n}a_i+a_0)
$$
將 $\sum_{i=m}^{n}a_i$ 定義為 $P_m$，而 $P_0=a_n+a_{n-1}+a_{n-2}+...+a_0$ 就是我們要求的平方根 $N$。所以接下來要找出所有組成平方根 $N$ 的所有 $a_m$。我們可以得知
$$
P_m = P_{m+1} + a_m
$$
其中 $a_m = 2^m \ or \ a_m=0$。找到平方根的方式就是讓 $P_m=N$，所以透過每一輪比較 $P_m^2 \leq N^2$ 來決定 $a_m$ 是否要加入到 $P_m$，也就是決定 $a_m$ 的值為 $0$ 或是 $2^m$。
$$
\begin{cases}
P_m = P_{m+1} + a_m, & \text{if } P_m^2 \leq N^2 \\
P_m = P_{m+1}, & \text{otherwise}
\end{cases}
$$
因為每輪計算 $N^2-P_m^2$ 的運算成本太高，所以改為紀錄每輪的差值 $X_m$，計算本輪差值的方式為 $X_m = X_{m+1} - Y_m$，$X_{m+1}$ 為上一輪計算完的差值。
$$
\begin{aligned}
X_m &= N^2-P_m^2 = X_{m+1} - Y_m \\
Y_m &= P_m^2-P_{m+1}^2 = 2P_{m+1}a_m+a_m^2
\end{aligned}
$$
再將 $Y_m$ 拆為 $c_m$，$d_m$
$$
\begin{aligned}
c_m&=2P_{m+1}a_m = P_{m+1}2^{m+1} \\
d_m&=a_m^2=(2^m)^2 \\
Y_m &= \begin{cases}
c_m+d_m, &\text{if }a_m=2^m\\
0, &\text{if }a_m=0
\end{cases}
\end{aligned}
$$
每輪的 $c_m$，$d_m$ 都會更新，所以試著計算 $m$ 的下一輪，$m-1$ 輪的結果
$$
\begin{aligned}
c_{m-1}&=2P_ma_{m-1} = (P_{m+1}+a_m)2^m\\
&=P_{m+1}2^m+a_m2^m \\
&=\begin{cases}
c_m/2+d_m, & \text{if }a_m=2^m \\
c_m/2, & \text{if } a_m=0 \\
\end{cases}\\ \\
d_{m-1}&=a_{m-1}^2 = (2^{m-1})^2 = d_m/4
\end{aligned}
$$
綜合上述方式，要從最大的位元開始測試，即從 $a_n$ 開始試到 $a_0$，初始情況為
+ $X_{n+1}=N^2$
+ $c_n=0$
+ $P_{n+1}=0$
在程式碼中 `z` 是 $c_m$，`m` 是 $d_m$，`x` 為 $X_m$，`b` 是 $Y_m$。
```c
for (int m = 1UL << ((31 - __builtin_clz(x)) & ~1UL); m; m >>= 2)
```
for 迴圈的初始情況先將 $d_m$ 也就是 `m`。首先 `(31 - __builtin_clz(x))` 可以找到最高位的 1 距離 lsb 的長度。接下來 `& ~1UL` 讓 `(31 - __builtin_clz(x))` 算出來的長度調整為偶數，如此一來 `1UL` 經過位移後，`m` 必為2的冪且有整數平方根。接下來每次迴圈都會執行 `m >>= 2`，對應到上面敘述的 $d_{m-1}=d_m/4$。
```c
int b = z + m;
z >>= 1;
if (x >= b)
x -= b, z += m;
```
迴圈內，`z >>= 1` 對應到先前敘述的 $c_{m-1}$ 的計算，先計算 $c_m/2$，是否要將 $d_m$ 加入則是由 $a_m$ 的值決定，也就是判斷 `x >= b`，成立後才執行 `z += m`，即為 $c_{m-1}=c_m/2+d_m$ 這段敘述。
#### 使用 fls 取代 `__builtin_clz`
```c
int fls(int x)
{
int result = 0;
if (x & 0xFFFF0000) {
result += 16;
x >>= 16;
}
if (x & 0xFF00) {
result += 8;
x >>= 8;
}
if (x & 0xF0) {
result += 4;
x >>= 4;
}
if (x & 0xC) {
result += 2;
x >>= 2;
}
if (x & 0x2) {
result += 1;
x >>= 1;
}
if (x & 0x1)
result += 1;
return result;
}
```
學習 [第二週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2) 使用二分搜尋法找到最靠近 MSB 並且被設為 1 的位置。接下來將 `(31 - __builtin_clz(x))` 替換為 `(32 - fls(x))`。
```c
int branchless_fls(int x)
{
int result = 0;
int move = 0;
move = 16 & (~(!!(x & 0xFFFF0000)) + 1);
result += move;
x >>= move;
move = 8 & (~(!!(x & 0xFF00)) + 1);
result += move;
x >>= move;
move = 4 & (~(!!(x & 0xF0)) + 1);
result += move;
x >>= move;
move = 2 & (~(!!(x & 0xC)) + 1);
result += move;
x >>= move;
move = 1 & (~(!!(x & 0x2)) + 1);
result += move;
x >>= move;
move = 1 & (~(!!(x & 0x1)) + 1);
result += move;
x >>= move;
return result;
}
```
無分支的實作會需要另一個變數 `move` 協助運算。以第一行計算為例，透過 `!!` 將 `x & 0xFFFF0000` 的值轉為 0 或 1。
+ 若為 0，經過 bitwise NOT 運算後會得到 `0xFFFFFFFF`，再加 1 會得到 0。
+ 若為 1，經過 bitwise NOT 運算後會得到 `0xFFFFFFFE`，再加 1 得到 `0XFFFFFFFF`。
而 `0xFFFFFFFF` 就可以作為 mask 和 16 進行 bitwise AND 運算。
#### Linux 核心原始程式碼使用 int_sqrt
在 [block/blk-wbt.c](https://github.com/torvalds/linux/blob/e34cbd307477ae07c5d8a8d0bd15e65a9ddaba5c/block/blk-wbt.c#L402) 可以找到，從文件開頭可以知道主要是處理 buffered writeback throttling，在 [LWN](https://lwn.net/Articles/704739/) 有找到作者一開始嘗試的情況。大量的 background buffered writeback 會導致 foreground 活動也受影響(下面例子是用開啟 chrome)。
>When we do background buffered writeback, it should have little impact
on foreground activity. That's the definition of background activity...
But for as long as I can remember, heavy buffered writers have not
behaved like that.
:::danger
command 是「命令」，而非「指令」(instruction)
:::
一開始作者使用<s>指令</s> 製作檔案，並且嘗試開啟 chrome，發現要等到 writeback 結束 chrome 才會開啟。
```bash
$ dd if=/dev/zero of=foo bs=1M count=10k
```
這段程式碼看最後一行 `mod_timer` 可以知道是調整計時器的倒數時間。
```c
static void rwb_arm_timer(struct rq_wb *rwb)
{
unsigned long expires;
if (rwb->scale_step > 0) {
/*
* We should speed this up, using some variant of a fast
* integer inverse square root calculation. Since we only do
* this for every window expiration, it's not a huge deal,
* though.
*/
rwb->cur_win_nsec = div_u64(rwb->win_nsec << 4,
int_sqrt((rwb->scale_step + 1) << 8));
} else {
/*
* For step < 0, we don't want to increase/decrease the
* window size.
*/
rwb->cur_win_nsec = rwb->win_nsec;
}
expires = jiffies + nsecs_to_jiffies(rwb->cur_win_nsec);
mod_timer(&rwb->window_timer, expires);
}
```
### 第三週測驗二
因為 10 不能表示為二的冪，所以透過精確度的計算找到可以使用 $\frac{128}{13} \approx 9.84$ 來估算除以 10。這邊使用的方式是透過找到 $\frac{n}{8}+\frac{n}{2}+n=\frac{13}{8}n$ 後再乘上 8 即可找到 $13n$。
```c
(((n >> 3) + (n >> 1) + n) << 3)
```
接下來再除 128，可以得到 $\frac{13}{128} \approx 0.10$。
```c
q = ((((n >> 3) + (n >> 1) + n) << 3) + d0 + d1 + d2) >> 7;
```
這邊 `d0`，`d1`，`d2` 是要處理右移後被捨棄的位元。但這裡應該要對 `n` 做 bitwise AND 而不是對 `q`，因為被右移的是 `n`。
```c
d0 = q & 0b1;
d1 = q & 0b11;
d2 = q & 0b111;
```
下面是另一種表示方式，和上面方式不太一樣。首先計算 `x` 為 $\frac{3}{4}in$，但這裡不清楚為何需要 `(in | 1)`。再計算 `q` 為 $(\frac{3}{64} + \frac{3}{4})in$，而其中 $(\frac{3}{64} + \frac{3}{4}) \approx 0.80$。接下來四次執行 `q = (q >> 8) + x;` 是為了讓 `q` 逼近 $0.8in$，最後再透過 `q >> 3` 就可以得到 $0.1in$。而最後 `mod` 計算，`(q & ~0x7)` 相當於 `div << 3`，所以最後一行程式碼可以看成 `in - (8 * div + 2 * div)`。
```c
void divmod_10(uint32_t in, uint32_t *div, uint32_t *mod)
{
uint32_t x = (in | 1) - (in >> 2); /* div = in/10 ==> div = 0.75*in/8 */
uint32_t q = (x >> 4) + x;
x = q;
q = (q >> 8) + x;
q = (q >> 8) + x;
q = (q >> 8) + x;
q = (q >> 8) + x;
*div = (q >> 3);
*mod = in - ((q & ~0x7) + (*div << 1));
}
```
#### 分析佔用的 CPU 週期數
透過使用 `objdump -S` 產生組合語言，查看 intel ice lake and tiger lake 的表。以下是使用 `/` 和 `%`。
```
0000000000001149 <divmod_10>:
1149: f3 0f 1e fa endbr64
114d: 55 push %rbp
114e: 48 89 e5 mov %rsp,%rbp
1151: 89 7d fc mov %edi,-0x4(%rbp)
1154: 48 89 75 f0 mov %rsi,-0x10(%rbp)
1158: 48 89 55 e8 mov %rdx,-0x18(%rbp)
115c: 8b 45 fc mov -0x4(%rbp),%eax
115f: 48 63 d0 movslq %eax,%rdx
1162: 48 69 d2 67 66 66 66 imul $0x66666667,%rdx,%rdx
1169: 48 c1 ea 20 shr $0x20,%rdx
116d: c1 fa 02 sar $0x2,%edx
1170: c1 f8 1f sar $0x1f,%eax
1173: 29 c2 sub %eax,%edx
1175: 48 8b 45 f0 mov -0x10(%rbp),%rax
1179: 89 10 mov %edx,(%rax)
117b: 8b 4d fc mov -0x4(%rbp),%ecx
117e: 48 63 c1 movslq %ecx,%rax
1181: 48 69 c0 67 66 66 66 imul $0x66666667,%rax,%rax
1188: 48 c1 e8 20 shr $0x20,%rax
118c: 89 c2 mov %eax,%edx
118e: c1 fa 02 sar $0x2,%edx
1191: 89 c8 mov %ecx,%eax
1193: c1 f8 1f sar $0x1f,%eax
1196: 29 c2 sub %eax,%edx
1198: 89 d0 mov %edx,%eax
119a: c1 e0 02 shl $0x2,%eax
119d: 01 d0 add %edx,%eax
119f: 01 c0 add %eax,%eax
11a1: 29 c1 sub %eax,%ecx
11a3: 89 ca mov %ecx,%edx
11a5: 48 8b 45 e8 mov -0x18(%rbp),%rax
11a9: 89 10 mov %edx,(%rax)
11ab: 90 nop
11ac: 5d pop %rbp
11ad: c3 retq
```
1 個 `push` 花費 3 clock cycles。5 個 `mov`(r,r) 共花費 5 clock cycles。4 個 `mov`(r,m) 共花費 8 clock cycles。5 個 `mov`(m,r) 共花費 15 clock cycles。2 個 `movslq`(r,r) 花費 2 clock cycles。2 個 `imul` 共花費 6 clock cycles。2 個 `shr` 花費 2 clock cycles。4 個 `sar` 花費 4 clock cycles。3 個 `sub`(r,r) 花費 3 clock cycles。2 個 `add`(r,r) 花費 2 clock cycles。1 個 `pop` 花費 3 clock cycles。
總共 53 個 clock cycles。
以下是改為使用 shift/add 方式的組合語言。
```
0000000000000000 <divmod_10>:
0: f3 0f 1e fa endbr64
4: 55 push %rbp
5: 48 89 e5 mov %rsp,%rbp
8: 89 7d ec mov %edi,-0x14(%rbp)
b: 48 89 75 e0 mov %rsi,-0x20(%rbp)
f: 48 89 55 d8 mov %rdx,-0x28(%rbp)
13: 8b 45 ec mov -0x14(%rbp),%eax
16: 83 c8 01 or $0x1,%eax
19: 89 c2 mov %eax,%edx
1b: 8b 45 ec mov -0x14(%rbp),%eax
1e: c1 e8 02 shr $0x2,%eax
21: 29 c2 sub %eax,%edx
23: 89 d0 mov %edx,%eax
25: 89 45 f8 mov %eax,-0x8(%rbp)
28: 8b 45 f8 mov -0x8(%rbp),%eax
2b: c1 e8 04 shr $0x4,%eax
2e: 89 c2 mov %eax,%edx
30: 8b 45 f8 mov -0x8(%rbp),%eax
33: 01 d0 add %edx,%eax
35: 89 45 fc mov %eax,-0x4(%rbp)
38: 8b 45 fc mov -0x4(%rbp),%eax
3b: 89 45 f8 mov %eax,-0x8(%rbp)
3e: 8b 45 fc mov -0x4(%rbp),%eax
41: c1 e8 08 shr $0x8,%eax
44: 89 c2 mov %eax,%edx
46: 8b 45 f8 mov -0x8(%rbp),%eax
49: 01 d0 add %edx,%eax
4b: 89 45 fc mov %eax,-0x4(%rbp)
4e: 8b 45 fc mov -0x4(%rbp),%eax
51: c1 e8 08 shr $0x8,%eax
54: 89 c2 mov %eax,%edx
56: 8b 45 f8 mov -0x8(%rbp),%eax
59: 01 d0 add %edx,%eax
5b: 89 45 fc mov %eax,-0x4(%rbp)
54: 89 c2 mov %eax,%edx
56: 8b 45 f8 mov -0x8(%rbp),%eax
59: 01 d0 add %edx,%eax
5b: 89 45 fc mov %eax,-0x4(%rbp)
5e: 8b 45 fc mov -0x4(%rbp),%eax
61: c1 e8 08 shr $0x8,%eax
64: 89 c2 mov %eax,%edx
66: 8b 45 f8 mov -0x8(%rbp),%eax
69: 01 d0 add %edx,%eax
6b: 89 45 fc mov %eax,-0x4(%rbp)
6e: 8b 45 fc mov -0x4(%rbp),%eax
71: c1 e8 08 shr $0x8,%eax
74: 89 c2 mov %eax,%edx
76: 8b 45 f8 mov -0x8(%rbp),%eax
79: 01 d0 add %edx,%eax
7b: 89 45 fc mov %eax,-0x4(%rbp)
7e: 8b 45 fc mov -0x4(%rbp),%eax
81: c1 e8 03 shr $0x3,%eax
84: 89 c2 mov %eax,%edx
86: 48 8b 45 e0 mov -0x20(%rbp),%rax
8a: 89 10 mov %edx,(%rax)
8c: 8b 45 fc mov -0x4(%rbp),%eax
8f: 83 e0 f8 and $0xfffffff8,%eax
92: 89 c2 mov %eax,%edx
94: 48 8b 45 e0 mov -0x20(%rbp),%rax
98: 8b 00 mov (%rax),%eax
9a: 01 c0 add %eax,%eax
9c: 01 c2 add %eax,%edx
9e: 8b 45 ec mov -0x14(%rbp),%eax
a1: 29 d0 sub %edx,%eax
a3: 89 c2 mov %eax,%edx
a5: 48 8b 45 d8 mov -0x28(%rbp),%rax
a9: 89 10 mov %edx,(%rax)
ab: 90 nop
ac: 5d pop %rbp
ad: c3 retq
```
1 個 `push` 花費 3 clock cycles。12 個 `mov`(r,r) 花費 12 clock cycles。13 個 `mov`(m,r) 花費 26 clock cycles。21 個 `mov`(r,m) 花費 63 clock cycles。1 個 `or` 花費 1 clock cycles。7 個 `shr` 花費 7 clock cycles。8 個 `add` 花費 8 clock cycles。2 個 `sub` 花費 2 clock cycles。1 個 `and` 花費 1 clock cycles。1 個 `pop` 花費 3 clock cycles。
總共 126 clock cycles。
#### 不依賴除法指令 modulo 9
參考延伸閱讀 [Modulus without Division, a tutorial](https://homepage.cs.uiowa.edu/~dwjones/bcd/mod.shtml)。先分析 `mod 3` 的情況。
首先
> All of the above rules are actually special cases of a single general rule. Given that
a is represented in number base b
a mod m = ( (b mod m)⌊a/b⌋ + (a mod b) ) mod m
可以得知若要將 `a` 改為用 `b` 進位表示(十進位，八進位 ...)
$$
a\ mod\ m = ((b\ mod\ m)\lfloor \frac{a}{b}\rfloor + (a\ mod\ b))\ mod\ m
$$
觀察上面式子，想要實作 `% 3` 可以透過將 `a` 轉為 4 進位，因為 $(b\ mod\ m)$ 為 $(4\ mod\ 3)$ 即為 $1$。所以整式為
$$
\begin{aligned}
a\ mod\ 3 &= ((4\ mod\ 3)\lfloor \frac{a}{4} \rfloor + (a\ mod\ 4))\ mod\ 3 \\
a\ mod\ 3&=(\lfloor \frac{a}{4} \rfloor + (a\ mod\ 4))\ mod\ 3
\end{aligned}
$$
其中可以發現 $(a\ mod\ 4)$ 是取出 `a` 在四進位中的第一個 digit。而 $\lfloor \frac{a}{4} \rfloor$ 便是 `a` 將第一個 digit 移去後剩下的值。所以如果重複執行 $(\lfloor \frac{a}{4} \rfloor + (a\ mod\ 4))$ 直到 `a` 小於 4，其意思就是將 `a` 轉為四進位後，把所有 digit 相加。
```c
uint32_t mod3( uint32_t a ) {
a = (a >> 16) + (a & 0xFFFF);
a = (a >> 8) + (a & 0xFF);
a = (a >> 4) + (a & 0xF);
a = (a >> 2) + (a & 0x3);
a = (a >> 2) + (a & 0x3);
a = (a >> 2) + (a & 0x3);
if (a > 2) a = a - 3;
return a;
}
```
這個程式碼是基於上面所述以四進位來計算 `mod 3`，但計算方式不同。本來的原理是透過計算四進位的所有 digit 總和，而這個方式改為依序計算 $2^{16}=4^8$ 進位(內文為 base-$4^8$)的 digit。接下來再計算 base-$2^8(=4^4)$ 的 digit 總和，再依序算到四進位的 digit 總和。可以透過最一開始的式子證明
$$
a\ mod\ 3 = (\lfloor \frac{a}{2^{16}} \rfloor + (a\ mod\ 2^{16}))\ mod\ 3
$$
用同餘的形式表示
$$
a \equiv (\lfloor \frac{a}{2^{16}} \rfloor + (a\ mod\ 2^{16}))\ mod\ 3
$$
可以再推算
$$
(\lfloor \frac{a}{2^{16}} \rfloor + (a\ mod\ 2^{16})) \equiv (\lfloor \frac{a}{2^8} \rfloor + (a\ mod\ 2^8))\ mod\ 3
$$
所以要撰寫 `mod 9` 的方式和 `mod 3` 類似，但因 9 並非 $2^i-1$，所以需要找到某數為 $2^i-1$ 且為 9 的倍數。所以找到以 $63=9\times 7$ 為除數來取餘數。
```c
uint32_t mod9(uint32_t a) {
a = (a >> 24) + (a & 0xFFFFFF);
a = (a >> 18) + (a & 0x3FFFF);
a = (a >> 12) + (a & 0xFFF);
a = (a >> 6) + (a & 0x3F);
if (a > 62) a -= 63;
while (a > 8) {
a -= 9;
}
return a;
}
```
首先找到 63 的餘數，和尋找 3 的餘數方式相同，找 3 的餘數要先計算四進位(base-4)的所有 digit 和，而找 63 的餘數就要先找 base-64 的所有 digit 和，即為 `a = (a >> 6) + (a & 0x3F);`。接下來因為 63 的餘數範圍為 0~62，所以再對此餘數 `mod 9`，這邊是透過減法撰寫。
:::warning
TODO: 證明針對 2 的冪 +/- 1 的 modulo 運算可找到對應不依賴除法運算的實作。
:::
### 第三週測驗三
判斷 ilog2 就是找到二進位最高位的 1 的位置，版本二是透過二分搜尋法來找。版本三是透過 `__builtin_clz` 得到最靠近 MSB 的第一個 set bit 前有幾個 0，`31 - __builtin_clz` 就可以得到最靠近 MSB 的 set bit 到 LSB 共有幾個 bits，就是 ilog2 的結果。
在 [ksm.c](https://github.com/torvalds/linux/blob/7efd0a74039fb6b584be2cb91c1d0ef0bd796ee1/mm/ksm.c#L3246) 中有找到 `ilog2` 的使用。KSM 是 [Kernel Samepage Merging](https://docs.kernel.org/admin-guide/mm/ksm.html) 的縮寫，主要用來找到有相同內容的 page，將他們替代為同一份共享的 write-protected page。
```c
static void wait_while_offlining(void)
{
while (ksm_run & KSM_RUN_OFFLINE) {
mutex_unlock(&ksm_thread_mutex);
wait_on_bit(&ksm_run, ilog2(KSM_RUN_OFFLINE),
TASK_UNINTERRUPTIBLE);
mutex_lock(&ksm_thread_mutex);
}
}
```
這邊的 `ilog2` 是用來取得 `KSM_RUN_OFFLINE` 的 set bit 位置。`KSM_RUN_OFFLINE` 的值為 4，所以 `ilog2` 會得到 2。[offline](https://docs.kernel.org/admin-guide/mm/memory-hotplug.html#onlining-and-offlining-memory-blocks) 是指某記憶體區塊若要被 kernel 移除(remove)，則會被標記為 `offlined`。而 `wait_on_bit` 是讓此 thread 等待直到 `ilog2(KSM_RUN_OFFLINE)` 位置的 bit 設為 0，才能繼續下一步。
## 閱讀〈因為自動飲料機而延畢的那一年〉的啟發
從這篇文章中可以看到作者在製作飲料機的過程中經歷，過程中有許多失敗和挫折，但他還是不放棄的繼續做下去，很值得我學習。製作飲料機和我們學習 Linux 核心的精神很類似，有許多細節和設計都是很重要的卻也很難注意到的。在前幾週的 Linux 核心課程中，我深深體會到自己的不足，學習到軟體開發的態度。以前寫作業都是隨便寫，能跑得出正確答案就好。而現在寫作業需要閱讀大量資料，發現自己連英文閱讀都有點問題，還要注意許多細節，連實驗次數是如何訂定的也要注意，程式語法要直接參考規格書而不是 google 搜尋。
這堂課帶給我的不僅是誠實認知到電腦科學相關知識的不足，也讓我認知到我有許多心態需要改變。老師有說過，真強者是不怕世俗的批評，但我從寫開發紀錄時就發現我不太敢寫出自己的看法，每次寫下一句話就要花很久的時間思考，原因就是怕被批評、害怕別人看法、害怕失敗。老師在第一週就有提到一句話
> 大部分的人一輩子洞察力不彰，原因之一是怕講錯被笑。想了一點點就不敢繼續也沒記錄或分享，時間都花在讀書查資料看別人怎麼想。看完就真的沒有自己的洞察了
雖然看到這句話想要努力改變，但我在第五週看完老師 code review 後，反而變得更不敢發表自己的意見，因為我發現自己雖然寫了很多作業，但根本沒有掌握細節，許多地方都是似懂非懂。所以後來更害怕自己被批評，讀了論文怕自己哪裡沒讀清楚，怕寫上去後是錯的，所以不敢寫，拖延一段時間後又責怪自己沒有付出夠多的時間寫作業。所以我認為我在這六週表現不好，但看完〈因為自動飲料機而延畢的那一年〉，我了解到自己遇到的挫折和失敗幾乎不值一提，並且增加了許多勇氣，希望能一路堅持到期末。
## 課程回顧
### Linux 核心模組運作原理
[Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module) 提到在新建立的裝置檔案 `/dev/fibonacci` 的數字會不同。
```bash
$ ls -l /dev/fibonacci
$ cat /sys/class/fibonacci/fibonacci/dev
```
在 [fibdrv.c](https://github.com/sysprog21/fibdrv/blob/master/fibdrv.c#L114) 中看到註解，於是尋找 `register_chrdev` 這個函式。先在 [fs.h](https://elixir.bootlin.com/linux/latest/source/include/linux/fs.h#L2685) 中找到該函式，接下來在 [Linux Kernel API](https://docs.kernel.org/core-api/kernel-api.html?highlight=register_chrdev#c.__register_chrdev) 中看到 `major` 這個參數，當其為 0 時，會動態配置 device number。
在講解 `__MODULE_INFO` 的巨集展開時提到
> 上述巨集的定義根據 MODULE 是否有被定義，MODULE 是在此核心模組被編譯時期所定義，若此模組編譯時已內建於核心則不會被定義。繼續將上述巨集展開
:::info
不理解此處，是指 `MODULE` 在編譯時會自動新增定義嗎？是由誰新增的？
> 注意看巨集展開，你可嘗試建構 [fibdrv](https://github.com/sysprog21/fibdrv) 並留意產生的 C 檔案，觀察其內容。 :notes: jserv
:::
模組載入時可以直接使用 `init_module()` 這個函式名稱是因為原始程式碼中使用 `module_init` 巨集，展開後會透過 [GCC extension](https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#index-alias-function-attribute) alias 連結 `init_module()` 和我們自訂的模組初始化函式。
#### 解釋 `fibdrv.ko` 是如何植入到 Linux 核心
`insmod` 會使用系統呼叫 `finit_module`，再觀察此系統呼叫的程式碼，發現會使用 [kernel_read_file](https://elixir.bootlin.com/linux/v6.9-rc1/source/kernel/module/main.c#L3149) 函式透過 file descriptor `fd` 來讀取檔案。
## 2024-05-01
[shecc](https://github.com/sysprog21/shecc)
RISC-V auipc, jalr
TODO:
1. 在 Linux 環境中，執行 shecc，並設定 Arm 和 RISC-V backend，觀察 bootstrap
2. 看報告，紀錄問題
3. https://github.com/sysprog21/shecc/blob/master/lib/c.c 產生的執行檔會用到 Linux 系統呼叫
4. Engineering a compiler 的 SSA 描述 => SSA 要解決什麼問題？什麼樣的 optimizer 可用 SSA 表達？SSA 的限制？
Known issues
* shecc 無法搭配 perf 使用
Sign in with Wallet
Connect another wallet