# 2024q1 Homework5 (assessment)
contributed by < [YiChiChao](https://github.com/YiChiChao) >
## Quiz 1
### 測驗 `1`
[利用 Linux Kernel API 改寫](https://hackmd.io/0hIrCST8QGea8-_3w5rCfg#%E5%88%A9%E7%94%A8-Linux-Kernel-API-%E6%94%B9%E5%AF%AB)
### 測驗 `2`
## Quiz 2
### 測驗 `2`
[實作測試之相關程式](https://github.com/YiChiChao/LinuxKernelLecture-Lab/commit/d3324bc8c286d632f178c57c9933918af27577f5)
#### 觀察實作
在當前的程式中，hhead[] 的大小和快取的最大存量等大。我修改 `lRUCacheCreate` 的參數，將 `hhead` 的大小和 `capacity` 作區隔，去測試觀察看縮減 hash table 的大小對搜尋時間的影響。
單就 cache capacity = 1000 的情形來觀察，hlist 的大小在500之後趨於平緩，可認 hlist 的大小設定宜做調整。
參考 [Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable) 將 hash function 改以 Multiplication Method 計算，從搜尋時間來看並無太大的差異。
## Quiz 3
### 測驗 `4`
$$S_t=\begin{cases}
\begin{flalign*}
&Y_0 \qquad &t = 0 \\
&\alpha Y_t+(1-\alpha )\cdot S_{t-1} \qquad &t > 0
\end{flalign*}
\end{cases} $$
```c
struct ewma{
unsigned long internal;
unsigned long factor;
unsigned long weight;
}
```
* `internal` 是紀錄當前時間之計算出的
EWMA
* `factor` 的定義我不清楚作用，按照老師給的註解，是用於對 `internal` 數值的縮放
* `weight` 為 EWMA 中的衰變率，從後面的程式碼回推`weight` 和 公式中 $\alpha$ 的關係為 $\alpha = \frac{1}{weight}$
```c
/* Add a sample to the average.*/
struct ewma *ewma_add(struct ewma *avg, unsigned long val)
{
avg->internal = avg->internal
? (((avg->internal << EEEE) - avg->internal) +
(val << FFFF)) >> avg->weight
: (val << avg->factor);
return avg;
}
```
將函式拆解會變成這樣
$$\tiny avg\rightarrow internal=\begin{cases}
\begin{flalign*}
&(avg\rightarrow val) \cdot 2^{avg\rightarrow factor } \qquad &avg\rightarrow internal = 0 \\
&\frac{1}{weight} \cdot (avg\rightarrow val) \cdot 2^{avg\rightarrow factor }+(1-\frac{1}{weight} )\cdot avg\rightarrow internal \qquad &avg\rightarrow internal \not = 0
\end{flalign*}
\end{cases}
$$
為了在程式碼中用shift來實現除法運算，程式碼加了對 `factor` 以及 `weight` 必須是2的冪的限制。將 $1$ 用 $\frac{weight}{weight}$ 替代。
$$\tiny avg\rightarrow internal=\begin{cases}
\begin{flalign*}
&(avg\rightarrow val) \cdot 2^{avg\rightarrow factor } \qquad &avg\rightarrow internal = 0 \\
&\frac{1}{{\color{red}{weight}}} \cdot (avg\rightarrow val) \cdot 2^{avg\rightarrow factor }+(\frac{weight}{{\color{red}{weight}}}-\frac{1}{{\color{red}{weight}}} )\cdot avg\rightarrow internal \qquad &avg\rightarrow internal \not = 0
\end{flalign*}
\end{cases}
$$
再將 $\frac{1}{weight}$ 提出，以 `>> weight` 表示。
$$\tiny avg\rightarrow internal=\begin{cases}
\begin{flalign*}
&(avg\rightarrow val) \cdot 2^{avg\rightarrow factor } \qquad &avg\rightarrow internal = 0 \\
&\frac{1}{{\color{red}{weight}}} \cdot [(avg\rightarrow val) \cdot 2^{avg\rightarrow factor }+(weight-1 )\cdot avg\rightarrow internal]
\qquad&avg\rightarrow internal \not = 0
\end{flalign*}
\end{cases}
$$
#### 觀察實作
在 [drivers/net/virtio_net.c](https://elixir.bootlin.com/linux/latest/source/drivers/net/virtio_net.c) 透過 `DECLARE_EWMA(pkt_len, 0, 64)` 來定義一個結構體 `struct ewma_pkt_len` 來利用 EWMA 調整 mergeable receive buffer 的封包大小。
## 閱讀學習資料問題
[Data Alignment](https://hackmd.io/@sysprog/c-memory#%E9%87%8D%E6%96%B0%E7%9C%8B-Heap)
```c
uint32_t v = *(uint32_t*) (csrc & 0xfffffffc);
```
執行時，透過 gdb 觀察：
```c
Program received signal SIGSEGV, Segmentation fault.
unaligned_get8 (src=0x7fffffffd600) at unaligned_get32.c:9
uint32_t v = *(uint32_t*) (csrc & 0xfffffffc);
```
> POSIX.1-2017, "References to unmapped addresses shall result in a SIGSEGV signal."
:::danger
不要參照中文 Wikipedia，其資訊通常過時，參照 IEEE / Open Group 的 POSIX 規範文件。
> 了解[name=YiChi Chao]
:::
當在使用遮罩取最後兩位以外的位元後，由於取得的指標未初始化，在此情況下對指標取值 （`*(uint32_t*)`)，為無效的記憶體<s>訪問</s> 。
:::danger
注意用語，參見[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)及[詞彙對照表](https://hackmd.io/@l10n-tw/glossaries)
:::
即使此強置轉型沒有 `SIGSEGV` 報錯，這個取值在此程式中也不合理。
改進方式是直接將 `csrc & 0xfffffffc` 強置轉型為 `(uint32_t)`
:::danger
**中文和英文字元之間要有空白字元** (對排版和文字搜尋有利)
:::
---
#### x86-64 ABI
IEEE 754, Assume float is 32-bit
```c
float float_div2(float x)
{
if(x == 0)return 0;
// using bitwise operations. No mul, div
__uint32_t calculate = *(__uint32_t*) &x;
__uint32_t exponent = calculate & 0x7F800000;
calculate &= 0x807FFFFF;
exponent -= 0x800000;
exponent &= 0x7F800000;
calculate |= exponent;
return *(float*) &calculate;
}
```
> TODO: 實作程式碼並解釋
實作程式碼：[445afd8](https://github.com/YiChiChao/LinuxKernelLecture-Lab/commit/445afd88fec6f38afedc1cdb238de1936004bc6b)
```graphviz
digraph G {
// Set graph attributes
graph [rankdir=LR, splines=line, nodesep=0.5]
// Define node shapes and styles
node [shape=plaintext, fontsize=15]
// Combined box with three compartments
combined_box [label=<<table border="0" cellborder="1" cellspacing="0">
<tr><td>sign</td><td><font color="blue"><b>exponent </b></font></td><td>mantissa</td></tr>
<tr><td>0</td><td><font color="blue"><b>1110 0001</b></font> </td><td>1000 0000 0000 0000 0000 000 </td></tr>
</table>>, width=0, height=0]
}
```
按照 IEEE-754 對浮點數的表示方法：
$$ (-1)^{sign} \times 1.mantissa\times2^{exponent-bias}$$
在不使用除法和乘法的前提下，透過位元操作將 `exponent` 的數值減一便能完成浮點數除以二的運算。
首先透過位元遮罩將 `exponent` 的部份單獨取出，
$$ \begin{array}{ccc}
&01110000110000000000000000000000\\
\And&01111111100000000000000000000000\\
\hline
=&0\color{blue}{11100001}00000000000000000000000
\end{array}$$
並且將 `calculate` 中的 exponent 部份先清零：
$$ \begin{array}{ccc}
&01110000110000000000000000000000\\
\And&10000000011111111111111111111111\\
\hline
=&0\color{blue}{00000000}10000000000000000000000
\end{array}$$
再來將 `exponent` 部份減一，也就是對此浮點數表示方式減 `0x800000` ：
$$ \begin{array}{ccc}
&0\color{blue}{11100001}00000000000000000000000\\
-&00000000\color{red}100000000000000000000000\\
\hline
=&0\color{blue}{11100000}00000000000000000000000
\end{array}$$
最後將 `calculate` 和計算好之 `exponent` OR 在一起。
值得注意的部份，在 IEEE-754 對特定數值有特例的表示方法，像是 `INF` 的表示為 `exponent` 全為一，`mantissa` 全為 0 。在測試我寫的函式是否正確時，發現當輸入值為 0 時，運算出的結果為 `INF` 。
```
x = 0.000000
float_div2(x) = inf
x/2 = 0.000000
```
所以在函式中單獨對 0 作判斷。
參考資料：[IEEE-754 與浮點數運算](https://hackmd.io/@czPKboGUQZi6-txq9HcDqw/BkzftBYAv)
TODO: quiz3+quiz4
Sign in with Wallet
Connect another wallet