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

struct ewma{
    unsigned long internal;
    unsigned long factor;
    unsigned long weight;
}

* `internal` 是紀錄當前時間之計算出的
EWMA
* `factor` 的定義我不清楚作用，按照老師給的註解，是用於對 `internal` 數值的縮放
* `weight` 為 EWMA 中的衰變率，從後面的程式碼回推`weight` 和 公式中 $\alpha$ 的關係為 $\alpha = \frac{1}{weight}$

 /* 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)

uint32_t v = *(uint32_t*) (csrc & 0xfffffffc);

執行時，透過 gdb 觀察：

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

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)

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