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$$

乘開後得到

$$\left[\begin{array}{ccccc}{a}_n{a}_n& a_{n-1}{a}_n& a_{n-2}{a}_n& ...& a_0{a}_n\\ a_n{a}_{n-1}& a_{n-1}{a}_{n-1}& a_{n-2}{a}_{n-1}& ...& a_0{a}_{n-1}\\ a_n{a}_{n-2}& a_{n-1}{a}_{n-2}& a_{n-2}{a}_{n-2}& ...& a_0{a}_{n-2}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ a_n{a}_0& a_{n-1}{a}_0& a_{n-2}{a}_0& ...& a_0{a}_0\end{array}\right]$$

分成幾個部分觀察

$$\left[\begin{array}{c}{a}_n{a}_n\end{array}\right]=a_n^2$$

$$\left[\begin{array}{cc}& a_{n-1}{a}_n\\ a_n{a}_{n-1}& a_{n-1}{a}_{n-1}\end{array}\right]=a_{n-1}(2a_n+a_{n-1})$$

$$\left[\begin{array}{ccc}& & a_{n-2}{a}_n\\ & & a_{n-2}{a}_{n-1}\\ a_n{a}_{n-2}& a_{n-1}{a}_{n-2}& a_{n-2}{a}_{n-2}\end{array}\right]=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\le N^2$ 來決定

$a_m$ 是否要加入到

$P_m$，也就是決定

$a_m$ 的值為

$0$ 或是

$2^m$。

$$\{\begin{array}{ll}{P}_m=P_{m+1}+a_m,& \text{if }{P}_m^2\le N^2\\ P_m=P_{m+1},& \text{otherwise}\end{array}$$

因為每輪計算

$N^2-P_m^2$ 的運算成本太高，所以改為紀錄每輪的差值

$X_m$，計算本輪差值的方式為

$X_m=X_{m+1}-Y_m$，

$X_{m+1}$ 為上一輪計算完的差值。

$$\begin{array}{rl}{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{array}$$
再將

$Y_m$ 拆為

$c_m$，

$d_m$

$$\begin{array}{rl}{c}_m& =2P_{m+1}{a}_m=P_{m+1}{2}^{m+1}\\ d_m& =a_m^2=(2^m{)}^2\\ Y_m& =\{\begin{array}{ll}{c}_m+d_m,& \text{if }{a}_m=2^m\\ 0,& \text{if }{a}_m=0\end{array}\end{array}$$
每輪的

$c_m$，

$d_m$ 都會更新，所以試著計算

$m$ 的下一輪，

$m-1$ 輪的結果

$$\begin{array}{rl}{c}_{m-1}& =2P_m{a}_{m-1}=(P_{m+1}+a_m)2^m\\ & =P_{m+1}{2}^m+a_m{2}^m\\ & =\{\begin{array}{ll}{c}_m/2+d_m,& \text{if }{a}_m=2^m\\ c_m/2,& \text{if }{a}_m=0\end{array}\\ \\ d_{m-1}& =a_{m-1}^2=(2^{m-1}{)}^2=d_m/4\end{array}$$
綜合上述方式，要從最大的位元開始測試，即從

$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$。

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$。

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

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;
}

學習 第二週測驗題 使用二分搜尋法找到最靠近 MSB 並且被設為 1 的位置。接下來將 (31 - __builtin_clz(x)) 替換為 (32 - fls(x))。

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 可以找到，從文件開頭可以知道主要是處理 buffered writeback throttling，在 LWN 有找到作者一開始嘗試的情況。大量的 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.

command 是「命令」，而非「指令」(instruction)

一開始作者使用指令 製作檔案，並且嘗試開啟 chrome，發現要等到 writeback 結束 chrome 才會開啟。

$ dd if=/dev/zero of=foo bs=1M count=10k

這段程式碼看最後一行 mod_timer 可以知道是調整計時器的倒數時間。

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$。

(((n >> 3) + (n >> 1) + n) << 3)

接下來再除 128，可以得到

$\frac{13}{128}\approx 0.10$。

q = ((((n >> 3) + (n >> 1) + n) << 3) + d0 + d1 + d2) >> 7;

這邊 d0，d1，d2 是要處理右移後被捨棄的位元。但這裡應該要對 n 做 bitwise AND 而不是對 q，因為被右移的是 n。

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)。

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。先分析 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 進位表示(十進位，八進位 …)

$$amodm=((bmodm)\lfloor \frac{a}{b}\rfloor +(amodb))modm$$
觀察上面式子，想要實作 % 3 可以透過將 a 轉為 4 進位，因為

$(bmodm)$ 為

$(4mod3)$ 即為

$1$。所以整式為

$$\begin{array}{rl}amod3& =((4mod3)\lfloor \frac{a}{4}\rfloor +(amod4))mod3\\ amod3& =(\lfloor \frac{a}{4}\rfloor +(amod4))mod3\end{array}$$
其中可以發現

$(amod4)$ 是取出 a 在四進位中的第一個 digit。而

$\lfloor \frac{a}{4}\rfloor$ 便是 a 將第一個 digit 移去後剩下的值。所以如果重複執行

$(\lfloor \frac{a}{4}\rfloor +(amod4))$ 直到 a 小於 4，其意思就是將 a 轉為四進位後，把所有 digit 相加。

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 總和。可以透過最一開始的式子證明

$$amod3=(\lfloor \frac{a}{2^{16}}\rfloor +(amod{2}^{16}))mod3$$
用同餘的形式表示

$$a\equiv (\lfloor \frac{a}{2^{16}}\rfloor +(amod{2}^{16}))mod3$$
可以再推算

$$(\lfloor \frac{a}{2^{16}}\rfloor +(amod{2}^{16}))\equiv (\lfloor \frac{a}{2^8}\rfloor +(amod{2}^8))mod3$$
所以要撰寫 mod 9 的方式和 mod 3 類似，但因 9 並非

$2^i-1$，所以需要找到某數為

$2^i-1$ 且為 9 的倍數。所以找到以

$63=9\times 7$ 為除數來取餘數。

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，這邊是透過減法撰寫。

TODO: 證明針對 2 的冪 +/- 1 的 modulo 運算可找到對應不依賴除法運算的實作。

第三週測驗三

判斷 ilog2 就是找到二進位最高位的 1 的位置，版本二是透過二分搜尋法來找。版本三是透過 __builtin_clz 得到最靠近 MSB 的第一個 set bit 前有幾個 0，31 - __builtin_clz 就可以得到最靠近 MSB 的 set bit 到 LSB 共有幾個 bits，就是 ilog2 的結果。
在 ksm.c 中有找到 ilog2 的使用。KSM 是 Kernel Samepage Merging 的縮寫，主要用來找到有相同內容的 page，將他們替代為同一份共享的 write-protected page。

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 是指某記憶體區塊若要被 kernel 移除(remove)，則會被標記為 offlined。而 wait_on_bit 是讓此 thread 等待直到 ilog2(KSM_RUN_OFFLINE) 位置的 bit 設為 0，才能繼續下一步。

閱讀〈因為自動飲料機而延畢的那一年〉的啟發

從這篇文章中可以看到作者在製作飲料機的過程中經歷，過程中有許多失敗和挫折，但他還是不放棄的繼續做下去，很值得我學習。製作飲料機和我們學習 Linux 核心的精神很類似，有許多細節和設計都是很重要的卻也很難注意到的。在前幾週的 Linux 核心課程中，我深深體會到自己的不足，學習到軟體開發的態度。以前寫作業都是隨便寫，能跑得出正確答案就好。而現在寫作業需要閱讀大量資料，發現自己連英文閱讀都有點問題，還要注意許多細節，連實驗次數是如何訂定的也要注意，程式語法要直接參考規格書而不是 google 搜尋。

這堂課帶給我的不僅是誠實認知到電腦科學相關知識的不足，也讓我認知到我有許多心態需要改變。老師有說過，真強者是不怕世俗的批評，但我從寫開發紀錄時就發現我不太敢寫出自己的看法，每次寫下一句話就要花很久的時間思考，原因就是怕被批評、害怕別人看法、害怕失敗。老師在第一週就有提到一句話

大部分的人一輩子洞察力不彰，原因之一是怕講錯被笑。想了一點點就不敢繼續也沒記錄或分享，時間都花在讀書查資料看別人怎麼想。看完就真的沒有自己的洞察了

雖然看到這句話想要努力改變，但我在第五週看完老師 code review 後，反而變得更不敢發表自己的意見，因為我發現自己雖然寫了很多作業，但根本沒有掌握細節，許多地方都是似懂非懂。所以後來更害怕自己被批評，讀了論文怕自己哪裡沒讀清楚，怕寫上去後是錯的，所以不敢寫，拖延一段時間後又責怪自己沒有付出夠多的時間寫作業。所以我認為我在這六週表現不好，但看完〈因為自動飲料機而延畢的那一年〉，我了解到自己遇到的挫折和失敗幾乎不值一提，並且增加了許多勇氣，希望能一路堅持到期末。

課程回顧

Linux 核心模組運作原理

Linux 核心模組運作原理 提到在新建立的裝置檔案 /dev/fibonacci 的數字會不同。

$ ls -l /dev/fibonacci
$ cat /sys/class/fibonacci/fibonacci/dev

在 fibdrv.c 中看到註解，於是尋找 register_chrdev 這個函式。先在 fs.h 中找到該函式，接下來在 Linux Kernel API 中看到 major 這個參數，當其為 0 時，會動態配置 device number。

在講解 __MODULE_INFO 的巨集展開時提到

上述巨集的定義根據 MODULE 是否有被定義，MODULE 是在此核心模組被編譯時期所定義，若此模組編譯時已內建於核心則不會被定義。繼續將上述巨集展開

不理解此處，是指 MODULE 在編譯時會自動新增定義嗎？是由誰新增的？

注意看巨集展開，你可嘗試建構 fibdrv 並留意產生的 C 檔案，觀察其內容。

jserv

模組載入時可以直接使用 init_module() 這個函式名稱是因為原始程式碼中使用 module_init 巨集，展開後會透過 GCC extension alias 連結 init_module() 和我們自訂的模組初始化函式。

解釋 fibdrv.ko 是如何植入到 Linux 核心

insmod 會使用系統呼叫 finit_module，再觀察此系統呼叫的程式碼，發現會使用 kernel_read_file 函式透過 file descriptor fd 來讀取檔案。

2024-05-01

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 使用