# 2020q1 Homework2 (fibdrv)
contributed by < `D4nnyLee` >
## 自我檢查清單
- [ ] 研讀上述 ==Linux 效能分析的提示== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
- [ ] 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
- [ ] 複習 C 語言 [數值系統](https://hackmd.io/@sysprog/c-numerics) 和 [bitwise operation](https://hackmd.io/@sysprog/c-bitwise)，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本;
- [ ] `lsmod` 的輸出結果有一欄名為 `Used by`，這是 "each module's use count and a list of referring modules"，但如何實作出來呢？模組間的相依性和實際使用次數 ([reference counting](https://en.wikipedia.org/wiki/Reference_counting)) 在 Linux 核心如何追蹤呢？
- [ ] 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題
## 設定環境
### 將特定 CPU 從排程中移除
預計將程式限定在第 0 個 CPU 上面執行。
1. 更改 grub 設定檔
開啟 `/etc/default/grub` 後找到 `GRUB_CMDLINE_LINUX_DEFAULT` 並加入 `isolcpus=0`
參考結果:
```
GRUB_CMDLINE_LINUX_DEFAULT="quiet isolcpus=0"
```
2. 重新開機後確認效果
利用 `htop` 工具確認 CPU 的使用情形
從上圖可以看到只有最上面的 CPU 的使用率為 `0%`，因為排程器預設不會排入任務到 `cpu #0`，除非用 `taskset` 一類的工具去指定
3. 抑制 ASLR
```shell
$ sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
```
4. 設定 `scaling_governor` 為 performance
```shell
$ sudo sh -c "echo performance > /sys/devices/system/cpu/cpu0/cpufreq/scaling_governor"
```
5. 針對 intel 處理器，關閉 turbo mode
```shell
$ sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
```
## 新增測量時間功能
首先看到 `fib_read`:
```cpp
static ssize_t fib_read(struct file *file, size_t size, loff_t *offset)
{
return (ssize_t) fib_sequence(*offset);
}
```
可以得知 `fib_read` 的回傳值就是費氏數列的答案，並且利用 `offset` 來指定要第幾個數。
因此可以在 client.c 中看到在呼叫 `read` 之前都會先呼叫 `lseek` 來設定 `offset` 。
為了可以測量 `fib_sequence` 的時間花費，我用 `ktime_get_ns` 紀錄 `fib_sequence` 的開始和結束的時間，而他們的時間差就是 `fib_sequence` 的時間花費。
最後利用 printk 來將測量結果輸出。
修改結果：
```diff
@@ -60,7 +60,16 @@ static ssize_t fib_read(struct file *file,
size_t size,
loff_t *offset)
{
- return (ssize_t) fib_sequence(*offset);
+ ssize_t result;
+ uint64_t start, end;
+
+ start = ktime_get_ns();
+ result = fib_sequence(*offset);
+ end = ktime_get_ns();
+
+ printk(KERN_INFO "%llu", end - start);
+
+ return result;
}
```
## 新增切換計算方法功能
因為之後會測試不同的算法計算費氏數列並紀錄時間花費，所以可以預測我可能需要頻繁的切換 `fib_read` 中的計算函式，因此我需要一個可以快速切換的功能，避免每次要換算法都要去更改 `fib_read` 。
我利用目前還沒用到的 `fib_write` 來實作這個功能。
主要的想法是利用一個變數 `choice` 來決定要使用的算法，然後這個 `choice` 可以利用 `fib_write` 中的 `size` 參數來修改。
在 `fib_read` 裡面，為了寫起來方便，我定義個一個所有算法共通的界面 `fib_compute` ，之後只要根據 `choice` 的值 hook 到對應的函式後就可以用之前的方法計算 `fib_compute` 的時間花費。
具體修改如下:
```diff
@@ -19,20 +19,23 @@ MODULE_VERSION("0.1");
*/
#define MAX_LENGTH 92
+#define IS_VALID(c) (c == 0)
+
+static uint32_t choice;
static dev_t fib_dev = 0;
static struct cdev *fib_cdev;
static struct class *fib_class;
static DEFINE_MUTEX(fib_mutex);
-static long long fib_sequence(long long k)
+static uint64_t fib_sequence(uint64_t k)
{
/* FIXME: use clz/ctz and fast algorithms to speed up */
- long long f[k + 2];
+ uint64_t f[k + 2];
f[0] = 0;
f[1] = 1;
- for (int i = 2; i <= k; i++) {
+ for (uint64_t i = 2; i <= k; i++) {
f[i] = f[i - 1] + f[i - 2];
}
@@ -62,9 +65,15 @@ static ssize_t fib_read(struct file *file,
{
ssize_t result;
uint64_t start, end;
+ uint64_t (*fib_compute)(uint64_t) = NULL;
+
+ if (choice == 0)
+ fib_compute = fib_sequence;
+ else
+ return -1;
start = ktime_get_ns();
- result = fib_sequence(*offset);
+ result = fib_compute(*offset);
end = ktime_get_ns();
printk(KERN_INFO "%llu", end - start);
@@ -78,7 +87,7 @@ static ssize_t fib_write(struct file *file,
size_t size,
loff_t *offset)
{
- return 1;
+ return (choice = IS_VALID(size) ? size : choice);
}
static loff_t fib_device_lseek(struct file *file, loff_t offset, int orig)
@@ -158,6 +167,9 @@ static int __init init_fib_dev(void)
rc = -4;
goto failed_device_create;
}
+
+ choice = 0;
+
return rc;
failed_device_create:
class_destroy(fib_class);
```
可以看到 `fib_write` 的回傳值並不會像之前一樣固定為 1 ，我把他改成回傳目前的 `choice` ，這樣在 client.c 就可以利用回傳值來確認有沒有切換成功。
:::warning
TODO: 可透過 sysfs 介面來指定 method (此例中，不該稱為 choice，語意不同)
:notes: jserv
:::
## Fibonacci 數列
### 原理
基本的定義如下：
$$
F(n) = \begin{cases} n, & n = 0 \text{ or } n = 1 \\ F(n - 1) + F(n - 2), & n \geq 2 \end{cases}
$$
在 [Matrix Difference Equation for Fibonacci Sequence](https://chunminchang.github.io/blog/post/matrix-difference-equation-for-fibonacci-sequence) 中寫到：
$$
\begin{split}
\begin{bmatrix}
F(n + 1) & F(n) \\
F(n) & F(n - 1)
\end{bmatrix} &=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}
\begin{bmatrix}
F(n) & F(n - 1) \\
F(n - 1) & F(n - 2)
\end{bmatrix} \\ &=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^2
\begin{bmatrix}
F(n - 1) & F(n - 2) \\
F(n - 2) & F(n - 3)
\end{bmatrix} \\
\vdots \\ &=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^{n - 1}
\begin{bmatrix}
F(2) & F(1) \\
F(1) & F(0)
\end{bmatrix} \\ &=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n
\end{split}
$$
而 fast doubling 的手法就是利用上面的等式：
$$
\begin{split}
\begin{bmatrix}
F(2n + 1) \\
F(2n)
\end{bmatrix} &=
\begin{bmatrix}
F(2n + 1) & F(2n) \\
F(2n) & F(2n - 1)
\end{bmatrix}
\begin{bmatrix}
1 \\
0
\end{bmatrix} \\ &=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^{2n}
\begin{bmatrix}
1 \\
0
\end{bmatrix} \\ &=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n
\begin{bmatrix}
1 \\
0
\end{bmatrix} \\ &=
\begin{bmatrix}
F(n + 1) & F(n) \\
F(n) & F(n - 1)
\end{bmatrix}
\begin{bmatrix}
F(n + 1) & F(n) \\
F(n) & F(n - 1)
\end{bmatrix}
\begin{bmatrix}
1 \\
0
\end{bmatrix} \\ &=
\begin{bmatrix}
F(n + 1)^2 + F(n)^2 \\
F(n)[F(n + 1) + F(n - 1)]
\end{bmatrix}
\end{split}
$$
最後得到以下遞迴式：
$$
\begin{cases}
F(2n + 1) = F(n + 1)^2 + F(n)^2 \\
F(2n) = F(n)[2F(n + 1) - F(n)] & (\because F(n - 1) = F(n + 1) - F(n))
\end{cases}
$$
### 實作
```cpp
static uint64_t fib_fast_doubling(uint64_t k)
{
/* FIXME: use clz/ctz and fast algorithms to speed up */
uint64_t a, b;
ktime_t kt;
a = 0;
b = 1;
for (uint64_t i = 1llu << 63; i; i >>= 1) {
uint64_t t1 = a * (2 * b - a);
uint64_t t2 = a * a + b * b;
a = t1;
b = t2;
if (k & i) {
t1 = a + b;
a = b;
b = t1;
}
}
return a;
}
```
此作法是參考[作業說明](https://hackmd.io/CTwO5ldOSgKxP-N4YNRVOA?view#-%E8%B2%BB%E6%B0%8F%E6%95%B8%E5%88%97)中給出的虛擬碼。
流程大致如下：
1. 從 MSB 檢查 LSB 的所有 bits
2. 如果此 bit 為
* `0` 則計算 $F(2n), F(2n + 1)$
* `1` 則先計算 $F(2n), F(2n + 1)$ 之後再算出 $F(2n + 2)$ 並將 $F(2n + 1), F(2n + 2)$ 保存起來
### 考慮硬體特性的 $F(n)$ 實作手法
在上述的流程中，如果現在的 $F(n), F(n + 1)$ 為 $F(0), F(1)$ ，則當我們要算 $F(2n), F(2n + 1)$ 的時候會發現 $F(2n), F(2n + 1)$ 還是 $F(0), F(1)$ 。
所以其實迴圈在檢查到第一個 bit 1 之前，所做的運算都是無效的。
為了排除那些無效的運算，我們可以讓迴圈就從第一個 1 開始跑，而這邊就可以借助處理器提供的 [clz](https://en.wikipedia.org/wiki/Find_first_set#CLZ) 指令，讓迴圈的 `i` 可以不要每次都 shift 到 MSB ，而是可以精準的 shift 到第一個 bit 1 。
因此 `i` 的宣告會變為：
```cpp
uint64_t i = k ? 1llu << (63 - __builtin_clzll(k)) : 0;
```
根據 [6.59 Other Built-in Functions Provided by GCC](https://devdocs.io/gcc~9/other-builtins) 所述：
> Built-in Function: int \_\_builtin_clz (unsigned int x)
> Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
當 clz 的輸入為 0 時結果為未定義 ~~(雖然我測的結果都是回傳 32)~~ ，因此在這邊利用三元運算子來確保不會將 0 輸入 clz 函式。
為了確認此作法是否真的可以達到加速的目的，我將結果畫成下面的圖表：
:::warning
"with" 和 "without" 可簡寫為 "w/" 和 "w/o"，用於圖例繪製
:notes: jserv
:::
從圖表中可以看到，使用 clz 之後大約都可以加快 100 ns ，因此證明了此作法是有用的。
因為第 93 項 (含) 以後的計算結果都是錯的，所以在圖表中就沒有畫出來。
Sign in with Wallet
Connect another wallet