# 2020q1 Homework2 (fibdrv)
contributed by < `haogroot` >
###### tags: `linux2020`
> Kernel version: 5.3.0-40-generic
> OS: Ubuntu 19.10
> CPU model: Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz
## 自我檢查清單
- [ ] 研讀上述 ==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，到底會發生什麼問題
## 初步效能量測
在 kernel module 中透過 `ktime_get()` 來量測計算所需時間，在 user space 透過 `clock_gettime()`來測量。
由於 read 預設是回傳 `ssize_t`，只有 8 bytes，我們無法回傳 `fib_sequence()` 執行時間與大數計算的結果，改為將結果寫入 `fib_read()` 的參數 `char *buf`，在 kernel space 宣告一個陣列 kbuffer 來儲存，將 ktime 所計算的時間寫到前八個 bytes，大數計算的結果寫到接下來的位置，最後透過 `copy_to_user()`將 kernel space 的資料傳到 user space。
```cpp
char kbuffer[168];
static ssize_t fib_read(char *buf)
{
// Write Fibonacci result to kbuffer...
ssize_t retval = fib_sequence(*offset, kbuffer);
/* Write execution time to kbuffer... */
// Copy data from kernel to user space.
copy_to_user(buf, kbuffer, retval + 9);
}
```
:::danger
用字要精準，到底是 $n \ge 93$ 還是 $n \gt 93$，另外 overflow 的空間範圍要說清楚
:notes: jserv
:::
當 fib(n) 中的 n ≥ 93 會發生 overflow ( fib(93)=12,200,160,415,121,876,738,但 unsigned long long 可表達最大為 18,446,744,073,709,551,615)，先限制測試到 92。測時結果如下圖所示，隨著測試數字愈大，在 kernel space 耗費時間也跟著增加，從 user space 跟 kernel space 之間的差距為 200 ms，可推估在 kernel 計算完傳輸到 user space 耗費約 200 ms。
## 費式數列實作演算法
在[你所不知道的C語言：遞迴呼運算叫篇](https://hackmd.io/@sysprog/c-recursion?type=view#Fibonacci-sequence) 探討過 Fibonacci sequence 不同實作演算法的複雜度，如下表所示：
| 方法 | 複雜度 |
| -------- | -------- |
| Recursive | $O(2^n)$ |
| Iterative | $O(n)$ |
| Tail Recursion | $O(n)$ |
| Q-Matrix | $O(log{n})$ |
| Fast Doubling | $O(log{n})$ |
## 大數運算 - Iterative
當 fib(n) 中的 n 大於 93 會發生 overflow，透過大數運算來解決這個問題。
參考 [tiny-bignum-c](https://github.com/kokke/tiny-bignum-c) 來實作大數運算，透過 `struct bn` 來存放大數運算的結果，每一個 element 大小為 32 bits，最多可以用來代表 (`0xFFFFFFFF`)。
```cpp
#define DTYPE unsigned int
struct bn {
DTYPE array[10]
}
```
### 排除干擾效能分析的因素
1. 限定 CPU 給特定程式使用
增加 BootOptions `isolcpus=1`，reboot 後透過 `cat /proc/cmdline` 來驗證。
2. 關掉 CPU Turbo mode
`$ sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"`
3. 關掉 [ASLR](https://zh.wikipedia.org/wiki/%E4%BD%8D%E5%9D%80%E7%A9%BA%E9%96%93%E9%85%8D%E7%BD%AE%E9%9A%A8%E6%A9%9F%E8%BC%89%E5%85%A5)
`$ sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"`
4. 設定 scaling_governor 為 performance。
`$ sudo sh -c "echo performance > /sys/devices/system/cpu/cpu1/cpufreq/scaling_governor"`
### 測量結果
```shell
$ make load
$ sudo taskset 0x2 ./client
$ make unload
$ make plot
```
透過大數算法來解決 overflow 問題，並採取 iterative 方式，結果如下圖。 Fib(0) 和 Fib(1) 會直接回傳結果，所以執行時間較短，其他測試隨著 n 的增加運算所需時間都有顯著的提升，符合 $O(n)$ 的線性趨勢，不過雖然我們已經排除干擾效能分析的因素，但結果仍舊有顯著的抖動。
:::warning
TODO:
1. 檢查 taskset 設定;
2. 另一個命令 [chrt](http://man7.org/linux/man-pages/man1/chrt.1.html) 可搭配使用，見 [Chapter 6. Affinity
](https://access.redhat.com/documentation/en-US/Red_Hat_Enterprise_MRG/1.3/html/Realtime_Reference_Guide/chap-Realtime_Reference_Guide-Affinity.html)
3. 透過統計學手法，取 95% 信賴區間
:notes: jserv
:::
## 大數運算 - fast doubling
fast doubling 需要實作大數運算的減法與乘法，乘法實作上較複雜，透過二層迴圈來走訪每個位數，將各位數做相乘，再將相乘結果向左位移到所屬的位數，依序計算並相加所有結果。
```cpp
void bignum_mul(struct bn *a, struct bn *b, struct bn *output)
{
struct bn row;
struct bn tmp;
for (i = 0; i < ARR_SIZE; i++) {
for (j = 0; j < ARR_SIZE; j++) {
if (i + j < ARR_SIZE) {
BIGGER_DTYPE mul_result = (BIGGER_DTYPE) a->array[i] *
(BIGGER_DTYPE) b->array[j];
bignum_from_int(&tmp, mul_result);
_lshift_word(&tmp, i + j);
bignum_add(&tmp, &row, &row);
}
}
bignum_add(output, &row, output);
}
}
```
### 測量結果
如下圖，fast doubling 的運算明顯比 Iterative 法更加耗時許多，並沒有如所預期的可以達到 $O(log{n})$ 的時間複雜度。
嘗試優化程式碼，可以觀察在做乘法時，<s>雙重</s>二層迴圈內顯然有很多次都是不必要的執行，如果執行乘法時其中一方為 `0`，就不必執行乘法運算。
:::danger
注意用語：「雙重」和「二層」意義不同，前者是隱含有對稱的兩件人事物，後者則著重在階層 (hierarchy)，本例中，應採後者。
:notes: jserv
:::
```cpp
void bignum_mul(struct bn *a, struct bn *b, struct bn *output)
{
struct bn row;
struct bn tmp;
for (i = 0; i < ARR_SIZE; i++) {
if (a->array[i] != 0) {
for (j = 0; j < ARR_SIZE; j++) {
if (i+j < ARR_SIZE && b->array[b] !=0) {
/* multiplication... */
}
}
}
}
}
```
用來存放運算結果的 array 減小到只包含3個 element，這樣的大小就足夠存放。
```cpp
#define DTYPE unsigned int
struct bn {
DTYPE array[3]
}
```
再次測量結果可以發現執行時間大幅減小。
### 優化
#### 方法 1: 根據 [你所不知道的C語言：遞迴呼運算叫篇](https://hackmd.io/@sysprog/c-recursion?type=view#Fibonacci-sequence) 的 Fast doubling 演算法 psuedo code 來實作。
```cpp
int fib(int n) {
if (n == 0) return 0;
int t0 = 1; // F(n)
int t1 = 1; // F(n + 1)
int t3 = 1; // F(2n)
int t4; // F(2n+1)
int i = 1;
while (i < n) {
if ((i << 1) <= n) {
t4 = t1 * t1 + t0 * t0;
t3 = t0 * (2 * t1 - t0);
t0 = t3;
t1 = t4;
i = i << 1;
} else {
t0 = t3;
t3 = t4;
t4 = t0 + t4;
i++;
}
}
return t3;
}
```
#### 方法 2: 參考來自 [Calculating Fibonacci Numbers by Fast Doubling](https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling) 中的手法實作，如同以下的 pseudo code：
```cpp
uint64_t fib(unsigned int n)
{
// The position of the highest bit of n.
// So we need to loop `h` times to get the answer.
// Example: n = (Dec)50 = (Bin)00110010, then h = 6.
// ^ 6th bit from right side
unsigned int h = 0;
for (unsigned int i = n ; i ; ++h, i >>= 1);
uint64_t a = 0; // F(0) = 0
uint64_t b = 1; // F(1) = 1
for (int j = h - 1 ; j >= 0 ; --j) {
// n_j = floor(n / 2^j) = n >> j, k = floor(n_j / 2), (n_j = n when j = 0)
// then a = F(k), b = F(k+1) now.
uint64_t c = a * (2 * b - a); // F(2k) = F(k) * [ 2 * F(k+1) – F(k) ]
uint64_t d = a * a + b * b; // F(2k+1) = F(k)^2 + F(k+1)^2
if ((n >> j) & 1) { // n_j is odd: k = (n_j-1)/2 => n_j = 2k + 1
a = d; // F(n_j) = F(2k+1)
b = c + d; // F(n_j + 1) = F(2k + 2) = F(2k) + F(2k+1)
} else { // n_j is even: k = n_j/2 => n_j = 2k
a = c; // F(n_j) = F(2k)
b = d; // F(n_j + 1) = F(2k + 1)
}
}
return a;
}
```
:::danger
使用一致的程式碼縮排方式: 4 個空白
:notes: jserv
:::
分析兩組 pseudo code，執行 Fast Doubling 的次數雖然相同，但方法二在執行大數加法運算的次數則減少許多。
以 Fib(100) 為例，
方法一執行 6 次 fast doubling 的運算 (變數 i 從 1 到 64 以 2 的倍數增加共執行 6 次)，接著執行 35 次的大數加法（變數 i 從 64 到 99）。
方法二同樣執行 6 次 fast doubling 的運算，但僅執行 3 次的大數加法 （`(n >> j) & 1`為 true 時會執行）。
#### 方法 3: 將方法2搭配 `clz`
方法 2 中其實我們就已經利用 for 迴圈來計算從 MSB 算起有多少開頭 0 位元，但透過 gcc 提供的 built-in function `clz` 試圖加速。
```cpp
unsigned int h = 32 - __builtin_clz(k);
```
測量結果如下圖，不過發現測試多次後，抖動相當明顯，
### 處理測量結果抖動
根據老師的建議，方向為
1. 檢查 taskset 設定
2. 搭配命令 chrt 使用
3. 透過統計學方法取 95% 信賴區間
#### 檢查 taskset 設定
在上方排除效能干擾的因素段落中確實執行，且結果均有成功寫入，透過 Ubuntu 內建的 System Monitor 觀察，CPU1 確實被保留住。
#### 使用命令 chrt
命令 chrt 可以設定 process 的 real-time scheduling attributes，有以下 attributes 可以設定
1. `SCHED_OTHER` : 這是一般 Linux 預設的排程方法，並不會對 process 做任何特殊處理。
2. `SCHED_FIFO` :使用 First-in-first-out scheduling algorithm。
3. `SCHED_RR` : 使用 round-robin scheduling algorithm。
4. `SCHED_BATCH` :這是 Linux 獨有的（since linux 2.6.23），只有在沒有任何 process 想要使用 CPU 時，他才能夠執行，被設定成 SCHED_BATCH 的 process 比 SCHED_OTHER 還低。
5. `SCHED_IDLE` : 通常使用在低優先級且在背景執行的 process。
:::warning
在此案例中，我們可將 scheduling policy 設定為 FIFO，任務的即時排程優先權改為 `90` (不能設定為 `99`，否則系統很可能無法正確運作)，並且加大測試次數，這樣就可確保測試時間，被打斷的機會大幅降低，從而排除干擾。當然，還是需要將 [outlier](https://en.wikipedia.org/wiki/Outlier) 去除，利用統計方法。
:notes: jserv
:::
這裡我們使用 `SCHED_FIFO` ，根據老師建議給予優先權 `90`。
```
$ sudo taskset -c 1 chrt -f 90 ./client
```
> 這邊我有一個疑惑，其實從量測效能圖中，可以看到從 kernel space 所測得的時間就已經有明顯抖動，代表是否 kernel module 執行過程中發生被打斷的現象，但是我們使用 taskset 指令都是在確保 user space 的 process 不要被搶佔，這樣的動作是否對排除量測干擾並沒有幫助？是否能夠對 kernel module 設定較高的優先權來解決？ 或是對 kernel module 設定 Processor affinity 來排除干擾？[name=Yu-Hao(Howard) Hsu]
:::warning
因為你使用 ktime 測量時間，在 Linux 核心尚有其他方法。設計實驗需要逐步排除問題，不用急著一次套用一堆方法。
注意共筆書寫，中英文間用一個半形空白字元區隔
:notes: jserv
:::
#### Outlier 離群值處理
若是我們測量出來的數據近似於常態分佈的機率分佈，將會有 95% 的數值分佈在距離平均值 2 個標準差以內的範圍。透過執行 50 次的 user space program，將結果以不同標準差來去除離群值。
在 Makefile 裡重複執行測試程式50次並將結果存成不同的檔案。預期希望透過do while loop 來控制測試執行次數。
寫 Makefile 過程中，學習到以下 3 點，紀錄下來供未來參考：
1. 在 [GNU Make 文件 5.3 Recipe Execution](https://www.gnu.org/software/make/manual/html_node/Execution.html#Execution) 中提到
> When it is time to execute recipes to update a target, they are executed by invoking a new sub-shell for each line of the recipe, ... Please note: this implies that setting shell variables and invoking shell commands such as cd that set a context local to each process will not affect the following lines in the recipe.
因此我們必須將整個 do while loop 寫成單行指令，以便達到預期成效，我們以分號（;）與換行符行 （\）來將所有指令串起。在 [GNU Make 5.3.1](https://www.gnu.org/software/make/manual/html_node/One-Shell.html#One-Shell) 文件中也有提到你可以透過 .ONESHELL 來達成一樣的效果。
2. 在 [GNU Make 文件 5.3.2 Choosing the shell](https://www.gnu.org/software/make/manual/html_node/Choosing-the-Shell.html#Choosing-the-Shell) 中提到
> The program used as the shell is taken from the variable SHELL. If this variable is not set in your makefile, the program /bin/sh is used as the shell.
若是你沒有特別設定 variable `SHELL`，預設都是以 `/bin/sh` 來執行。而不會是 bash ，不能使用 bash 語法混雜其中。
3. 在 [GNU Make 文件 5.1.2 Using Variables in Recipes](https://www.gnu.org/software/make/manual/html_node/Variables-in-Recipes.html) 中提到
> Variable and function references in recipes have identical syntax and semantics to references elsewhere in the makefile. They also have the same quoting rules: if you want a dollar sign to appear in your recipe, you must double it (‘`$$`’). For shells like the default shell, that use dollar signs to introduce variables, it’s important to keep clear in your mind whether the variable you want to reference is a make variable (use a single dollar sign) or a shell variable (use two dollar signs).
在 Recipe 中，如果使用的是 make variable，必須使用單一個 `$`，若是使用 shell variable，須使用兩個 `$$`。以下例子就是正確的使用變數的方式。
```shell
LIST = one two three
all:
for i in $(LIST); do \
echo $$i; \
done
```
以下是在 makefile 中撰寫名為 profile 的 target，會執行程式 client 共 50 次並將依序存為檔案。
```shell
profile: all
-rm -rf result/
mkdir -p result
number=1 ; while [ $$number -le 50 ] ; do \
$(MAKE) unload ; \
$(MAKE) load ; \
REPORT="result/test_$$number.txt" ; \
sudo taskset -c 1 chrt -f 90 ./client $$REPORT >/dev/null 2>&1 ; \
$(MAKE) unload ; \
number=`expr $$number + 1` ; \
done
```
針對 kernel space 的執行時間進行觀察，以 python script 來分別以 68-95-99.7 法則來去除離群值，並將標準差範圍內的資料取平均，畫出以下圖表。
原始全部資料與以 68 法則去除離群值後的資料來對比
原始全部資料與以 95 法則去除離群值後的資料來對比
原始全部資料與以 99.7 法則去除離群值後的資料來對比
我的解讀是是 99.7 法則來去除離群值能夠將大部份 Fib(n) 的測量結果降低，會是比較符合我們預期的模型。但這部份該如何正確分析，還請老師給予指導。
:::warning
至此，你不難發現，面對 GNU/Linux 和現代的電腦硬體，即便程式碼都是你自己撰寫，其行為卻無法充分掌握，你總是只能用較為迂迴的方式來分析，這也是我們為何要學習 perf, gdb, valgrind 等工具。在上述統計的實驗中，僅能適度剔除 outlier，不過資料本身的特性更為關鍵。
我們還需要排除更多干擾因素，諸如:
1. cache 的影響: 為何程式在 n 很小的時候，執行時間偏長？見討論 [What does it mean by cold cache and warm cache concept?](https://stackoverflow.com/questions/22756092/what-does-it-mean-by-cold-cache-and-warm-cache-concept)
* 後續尚有 [從 CPU cache coherence 談 Linux spinlock 可擴展能力議題](https://hackmd.io/@sysprog/linux-spinlock-scalability) 這類討論;
2. 電腦硬體實際上是 SMP，但我們做實驗的過程並未充分考量 [SMP IRQ affinity](https://www.kernel.org/doc/Documentation/IRQ-affinity.txt) 和 [NUMA](http://man7.org/linux/man-pages/man7/numa.7.html) 一類的影響 (顯然我沒辦法全部提過後，才要求學員寫簡單的程式，於是改為「做中學」的手段);
3. 以前學演算法，通常只看時間複雜度，但並未深究經由編譯器產生的機械碼，個別指令的 latency，更是從為探討過 microarchitecture 的影響 —— 上述的數據展現讓我們不得不誠實面對自己的認知，這也是本作業要引導學員理解的事：你的電腦不是你 (想像中) 的電腦;
* 針對 Intel 處理器，關閉 turbo mode，對於上述實驗影響就很顯著
:notes: jserv
:::
## Warm cache v.s. Cold Cache
Cold cache: Cache is empty or has irrelvant data, so it needs to read data from main memory for your program.
Warm cache: Cache has relvant data that your program needs so it only access the cache without access main memory.
## SMP IRQ affinity
可以參考 ldotrg 同學的[共筆](https://hackmd.io/@ldotrg/rydJZ_zBL#%E6%95%88%E8%83%BD%E5%88%86%E6%9E%90%E4%B8%89%E9%83%A8%E6%9B%B2)來設定
Sign in with Wallet
Connect another wallet