---
tags: linux kernel
---
# 2022q1 Homework3 (fibdrv)
contributed by < `zoanana990` >
> [fibdrv](), [fib_user]()
## 題目
- [x] 研讀上述 ==Linux 效能分析的提示== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
- [x] 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
- [x] 複習 C 語言 [數值系統](https://hackmd.io/@sysprog/c-numerics) 和 [bitwise operation](https://hackmd.io/@sysprog/c-bitwise)，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本;
- [x] 研讀 [KYG-yaya573142 的報告](https://hackmd.io/@KYWeng/rkGdultSU)，指出針對大數運算，有哪些加速運算和縮減記憶體操作成本的舉措？
- [ ] `lsmod` 的輸出結果有一欄名為 `Used by`，這是 "each module's use count and a list of referring modules"，但如何實作出來呢？模組間的相依性和實際使用次數 ([reference counting](https://en.wikipedia.org/wiki/Reference_counting)) 在 Linux 核心如何追蹤呢？
> 搭配閱讀 [The Linux driver implementer’s API guide » Driver Basics](https://www.kernel.org/doc/html/latest/driver-api/basics.html)
- [ ] 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 [POSIX Thread](https://en.wikipedia.org/wiki/POSIX_Threads) 的程式碼來確認。
- [ ] [一對一談話紀錄](https://docs.google.com/document/d/14G9Fsja1yr7HxeIUbQ9Q83h0KFR2DYWo2biv9_RBQLA/edit)
## 環境建立
電腦配置
```shell
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
Stepping: 9
CPU MHz: 2800.000
CPU max MHz: 3800.0000
CPU min MHz: 800.0000
BogoMIPS: 5599.85
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 6 MiB
```
## 前期準備
```shell
$ uname -r
5.13.0-30-generic
$ whoami
khienh
$ sudo whoami
root
```
嘗試編譯：
```shell
$ make check
make -C /lib/modules/5.13.0-35-generic/build M=/home/khienh/linux_kernel/fibdrv modules
make[1]: Entering directory '/usr/src/linux-headers-5.13.0-35-generic'
make[1]: Leaving directory '/usr/src/linux-headers-5.13.0-35-generic'
make unload
make[1]: Entering directory '/home/khienh/linux_kernel/fibdrv'
sudo rmmod fibdrv || true >/dev/null
make[1]: Leaving directory '/home/khienh/linux_kernel/fibdrv'
make load
make[1]: Entering directory '/home/khienh/linux_kernel/fibdrv'
sudo insmod fibdrv.ko
make[1]: Leaving directory '/home/khienh/linux_kernel/fibdrv'
sudo ./client > out
make unload
make[1]: Entering directory '/home/khienh/linux_kernel/fibdrv'
sudo rmmod fibdrv || true >/dev/null
make[1]: Leaving directory '/home/khienh/linux_kernel/fibdrv'
Passed [-]
f(93) fail
input: 7540113804746346429
expected: 12200160415121876738
```
觀察產生的核心模組：
```shell
$ modinfo fibdrv.ko
filename: /home/khienh/linux_kernel/fibdrv/fibdrv.ko
version: 0.1
description: Fibonacci engine driver
author: National Cheng Kung University, Taiwan
license: Dual MIT/GPL
srcversion: 9A01E3671A116ADA9F2BB0A
depends:
retpoline: Y
name: fibdrv
vermagic: 5.13.0-30-generic SMP mod_unload modversions
```
掛載核心模組:
```shell
$ sudo insmod ./fibdrv.ko
$ ls -l /dev/fibonacci
crw------- 1 root root 505, 0 三 13 22:42 /dev/fibonacci
$ cat /sys/class/fibonacci/fibonacci/dev
505:0
$ cat /sys/module/fibdrv/version
0.1
$ lsmod | grep fibdrv
fibdrv 16384 0
$ cat /sys/module/fibdrv/refcnt
0
```
---
## 為什麼不用虛擬機器
:::info
研讀上述 Linux 效能分析的提示 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作
→ 從中也該理解為何不希望在虛擬機器中進行實驗;
:::
### 閱讀 [Linux 核心設計: 不只挑選任務的排程器](https://hackmd.io/@sysprog/linux-scheduler)
#### 重新認識 scheduling
閱讀文章提示的幾個排程器：
1. [Memory Manager]()：virtual memory 到 physical memory 間的映射
- Source: [Memory Management Concept Overview](https://www.kernel.org/doc/html/latest/admin-guide/mm/concepts.html) ，主要是想看記憶體管理是哪裡用到排程器
- 虛擬記憶體
- 詳細內容在計算機結構中，筆記[請按這裡](https://hackmd.io/apFbMSzYSyijhPt0dZ0IWg)
- 實體記憶體 (Physical Memory) 是十分有限且珍貴的資源，即使程式結束後會將資源釋放實體記憶體的容量仍是硬性限制。因此，虛擬記憶體的出現就是為了解決這個問題。虛擬記憶體是一個從實體記憶體中抽象化的概念，它僅允許行程 (Process) 將必要的資訊除存在實體記憶體中並且提供一個保護的機制確保行程的資料獨立性
- 有了虛擬內存，每個記憶體訪問都惠使用虛擬地址，當 CPU 解碼記憶體指令時，它將虛擬地址轉譯成實體記憶體地址
- 實體記憶體被分成很多頁或頁面 (frame pages, or pages)。頁面的尺寸根據不同架構而定，實體記憶體的頁面可以映射到一個或多個虛擬記憶體的頁面，這些映射關係可以利用頁面表格(Page tables)轉譯，頁面表格進行是階級化的管理
- 較低階級的表格主要是存放軟體使用哪些記憶體頁面；較高階級的表格則是存放較低階級表格的實體記憶體位址，最高級的表格則是放在暫存器(Register)
- 當 CPU 進行地址轉換時，它將利用暫存器取得最高階級的表格。虛擬記憶體中分為幾個部份，有 index, tag, offset...，在 `linux` 中最高位元為虛擬記憶體的 index bits，它將用來進入較低級別的表格。最低的幾個位元組是 offset
- 大型記憶體頁面(Huge Pages)
- 地址翻譯與存取記憶體需要消耗大量的 CPU 時間，為了降低處理器浪費時間在地址翻譯上，會將這個工作放到快取中，叫做 TLB(Translation Lookaside Buffer)。通常 TLB 也是很稀缺的資源，因此運用到大型記憶體的程式可能因為 TLB miss 而有性能損失。
- 很多現代的 CPU 架構允許高階頁面表格(Page Table)直接映射到記憶體頁面(Memory Page)。舉例來說，在 x86 的架構中，可以映射 2M 甚至是 1G 的記憶體頁面到第二階或是第三階的表格中
- Linux 有兩個機制可以映射實體記憶體與大內存頁。第一種是 `hugelbfs` ，是一個偽檔案系統，它使用記憶體作為他的後備除存空間；第二種是 `THP`。 與 `hugelbfs` 不同，`THP` 管理名稱類的映射
- Zones
- 硬體限制可以直接記憶體存取(Directly Memory Access, DMA)的範圍，記憶體空間取決於不同硬體。
- Nodes
- 目前多核心處理器都是採用非統一記憶體存取架構(Non-Uniform Memory Access, NUMA)。在這樣的系統中，記憶體被排列成 "Bank" ，記憶體的訪問時間會根據與處理器的距離。 "Bank" 被稱為節點，每個節點有自己的空間、區域和被使用頁面及不同的統計計數器
- 頁面快取(Page Cache)
- 和記憶體相似的是從文件讀取資料後會將資料放到快取以備之後使用，此外當處理器在寫入文件時，會將 dirty bit 轉為1代表被寫入，確保資料不會和原始資料搞混
- 匿名記憶體(Anonymous Memory)
- 匿名記憶體或是匿名映射代表檔案系統並不支援記憶體。這些映射是程式的堆疊(Stack)與堆積(Heap)產生，通常匿名映射指定議程是允許訪問的虛擬內存區域，讀取導致創建一個頁面表格(Page Table)；寫入時將分配一個頁面表格保存寫入資料
- 回收(Reclaim)
- 在作業系統的生命週期中，實體記憶體頁面可以用在不同類型的資料，例如核心的資料結構、驅動的緩衝區及檔案系統的資料等等
- 根據不同的使用情況，linux的記憶體管理對他的處理方式不同，頁面可以在任何時候釋放不管在哪裡，其中最值得注意的是可回收頁面的類別是匿名記憶體
- 在大多數情況下，保存內部內核數據並用作 DMA 緩衝區的頁面不能被重新利用，並且在被用戶釋放之前它們會保持固定狀態。這樣的頁面被稱為不可回收的。但是，在某些情況下，甚至可以回收內核數據結構佔用的頁面。
- 釋放可回收的物理記憶體頁面並重新利用它們的過程稱為回收(Reclaim)。 Linux 可以異步或同步回收頁面，具體取決於系統的狀態。當系統未加載時，大部分內存是空閒的，分配請求將立即從空閒頁面供應中得到滿足。隨著負載的增加，空閒頁面的數量下降，當達到某個閾值時，分配請求將喚醒 kswapd 守護進程。它將異步掃描記憶體頁面，如果它們包含的數據在其他地方可用，則釋放它們，或者驅逐到後備存儲設備。
- OOM Killer
- 當作業系統沒有足夠的資源運行時會犧牲一個任務的資源讓作業系統繼續運作
2. [Hypervisor](https://en.wikipedia.org/wiki/Hypervisor)：VM 到實體硬體間的映射
- 依照[國家辭典](https://terms.naer.edu.tw/search/?q=hypervisor&field=ti&op=AND&match=&q=&field=ti&op=AND&order=&num=10&show=&page=&group=&heading=#result)查詢可將 `hypervisor` 翻譯成超管理器，Hypervisor 是 Supervisor 的Supervisor
- Hypervisor主要分為兩種
- 第一種，Bare-Metal 直接在硬體上運行
- 第二種，在主作業系統中運行虛擬機
- 但是這兩類只是名詞定義，也有同時符合第一種與第二種的虛擬機
- 示意圖：
- 作業說明要求我們做作業是直接使用系統而不是使用虛擬機主要是因為大部分我們使用的虛擬機屬於第二種類型，在進行效能分析時就有兩層，需要先經過主作業系統再到子作業系統，這樣對效能就不準確且變數很大
---
## 閱讀[Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module)
---
## 研讀費氏數列相關材料與`clz / ctz`
[論文連結](https://ir.library.oregonstate.edu/downloads/t435gg51w)
### 費氏數列論文中的方法
以下數學公式利用 C 語言進行實做，這邊會集中說明三種方法，首先說明費氏數列的定義：
$f(x, y)=\left\{
\begin{array}{c}
0 &if& 0 \leq n \\
1 &if& n = 1\\
f(n-1)+f(n-2) && others
\end{array}
\right.$
在這個作業中不考慮前 $k$ 項的和，也就是論文中所提到的 k-Ordered Fibonacci Numbers
#### 遞迴法 (Recursion)
原始碼如下
```c
int fab(int n){
if(n<=0) return 0;
else if(n==1) return 1;
else return fib(n-1) + fib(n-2);
}
```
這造成大量的重複運算，並不是一個好方法，因此我們接下來介紹疊代法
#### 疊代法 (Iteration)
#### Binet's Formula
#### Matrix Method
將費氏數列的前一項令為 `a`、`a` 的前一項令為 `b`，則可知費氏數列的值可以改寫為
$$
a_{n+1}=a_{n}+b_{n} \\ b_{n+1}=a_{n}
$$
上式可以簡化為矩陣形式，矩陣形式為：
$$
\left[ \begin{array}{l}
a_{n+1} \\ b_{n+1}
\end{array}
\right]=
\left[ \begin{array}{l}
1 & 1 \\ 1 & 0
\end{array}
\right]
\left[ \begin{array}{l}
a_{n} \\ b_{n}
\end{array}
\right]
$$
其中$\left[ \begin{array}{l}
1 & 1 \\ 1 & 0
\end{array}
\right]$為 Q-Matrix，在論文中提到，利用數學歸納法可以得到
$$
Q=\left[ \begin{array}{l}
1 & 1 \\ 1 & 0
\end{array}
\right]=\left[ \begin{array}{l}
f_{2} & f_{1} \\ f_{1} & f_{0}
\end{array}
\right]\\
Q^{n}=\left[ \begin{array}{l}
f_{n+1} & f_{n} \\ f_{n} & f_{n-1}
\end{array}
\right]
$$
這邊有閱讀老師給的資料 [Fast-Doubling](https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling)，但是沒有非常清楚。因此有另外看一個[影片](https://www.youtube.com/watch?v=Mrrgpz2rBjQ&ab_channel=RajanKumarSingh)這個影片詳細解釋了位元組與 Fast Doubling 的關係，其定義如下：
$$
\left[ \begin{array}{l}
f_{2n} \\ f_{2n+1}
\end{array}
\right]=
\left[ \begin{array}{l}
f_{n+1}^2 + f_{n}^2 \\ f_{n}f_{n+1} + f_{n-1}f_{n}
\end{array}
\right]
$$
轉換成聯立方程式：
$$
f_{2n} = f_{n+1}^2 + f_{n}^2 \\
f_{2n+1} = f_{n}f_{n+1} + f_{n-1}f_{n}
$$
下面是我的理解，以 $f_{15}$ 為例，`15` 的二進位為 0...01111，可將計算過程
圖示化如下：
1. 因為 15 = 2n + 1，可求得 n = 7，故欲求 $f_{15}$ 須先求得 $f_{7}$ 和 $f_{8}$ ，可將其圖示化如下：
```graphviz
strict digraph G
{
1[label="F(15)"]
2[label="F(7)", style=filled]
3[label="F(8)", style=filled]
{rank = same; 2;3;}
1 -> {2, 3}
}
```
2. 欲求 $f_{7}$ 和 $f_{8}$ 須先求得 $f_{3}$ 和 $f_{4}$。然而透過 fast doubling 的方法 $f_{3}$ 和 $f_{4}$ 只能求得 $f_{6}$ 和 $f_{7}$ 無法求得 $f_{8}$，此時可以利用定義求得 `f(8) = f(7) + f(6)`，計算方式連同上圖可將其圖示化如下：
```graphviz
strict digraph G
{
1[label="F(15)"]
2[label="F(7)" ]
3[label="F(8)" ]
4[label="F(3)", style=filled]
5[label="F(4)", style=filled]
6[label="F(6)", style=dashed]
{rank = same; 2;3;}
{rank = same; 4;5;6}
1 -> {2, 3}
2 -> {4, 5}
2 -> 3 [style=dashed; arrowhead=vee]
6 -> 3 [style=dashed; arrowhead=vee]
}
```
3. 欲求 $f_{3}$ 和 $f_{2}$ 須先求得 $f_{0}$ 和 $f_{1}$，可將其圖示化如下
```graphviz
strict digraph G
{
1[label="F(15)"]
2[label="F(7)" ]
3[label="F(8)" ]
4[label="F(3)" ]
5[label="F(4)" ]
6[label="F(6)" ]
7[label="F(1)", style=filled]
8[label="F(2)", style=filled]
{rank = same; 2;3;}
{rank = same; 4;5;6}
{rank = same; 7;8;}
1 -> {2, 3}
2 -> {4, 5}
4 -> {7, 8}
2 -> 3 [style=dashed; arrowhead=vee]
6 -> 3 [style=dashed; arrowhead=vee]
4 -> 5 [style=dashed; arrowhead=vee]
8 -> 5 [style=dashed; arrowhead=vee]
}
```
對比老師給的範例 `f(10)`，其二進位為 0...01010，對比我們舉例的 `f(15)`可以以下表呈現：
| $f_{10}$ | bit | $f_{15}$ | bit |
| -------- | --- | -------- | --- |
| $f_{5}, f_{6}$ | 0 | $f_{7}, f_{8}$ | 1 |
| $f_{2}, f_{3}$ | 1 | $f_{3}, f_{4}$ | 1 |
| $f_{1}, f_{2}$ | 0 | $f_{1}, f_{2}$ | 1 |
| $f_{0}, f_{1}$ | 1 | $f_{0}, f_{1}$ | 1 |
上表歸納出若是該位元數為 1，則代表需要使用定義解，0 則代表僅須使用公式解
### 字串疊代法
實做字串疊代法之前，需要先實做字串相加、字串長度、字串複製等函式，主體為字串相加。
#### 字串相加
字串相加概念主要列為以下三點：
1. 判斷字串長度，不能使用 `strlen` ，需要自己實做
2. 判斷是否需要進位，
3. 補上結束字元以避免重複的記憶體空間使用時用到之前的數字，舉例來說，F(7) = 13，此時要求 F(8) 時，F(8) 也是由 F(1) 開始加法，但是此時 F(2) 使用的空間與 F(7) 視同一塊，然而， F(2) = F(0) + F(1) = 0 + 1 = 1，但是因為它與 F(7) 使用相同空間的關係，其空間使用情況如下所示：
```c=
F_7[0] = '1';
F_7[1] = '0';
F_7[2] = '\0';
F_8[0] = '1';
```
此時因為沒有結束字元，若是記憶體分配的空間相同，會用到之前的資料，因此 `F_8 = "13"`。
`
程式碼如下：
```c=
void fib_stradd(char *num1, char *num2, char *res){
unsigned int l1 = fib_strlen(num1), l2 = fib_strlen(num2);
if(fib_strlen(num1) < fib_strlen(num2)){
fib_stradd(num2, num1, res);
return;
}
int carry = 0;
int i = l1 - 1;
for(int j = l2 - 1; i >= 0 && j >= 0; i--, j--){
int sum = num1[i] - '0' + num2[j] - '0' + carry;
res[i] = sum % 10 + '0';
carry = sum / 10;
}
for (; i >= 0; i--) {
int sum = num1[i] - '0' + carry;
res[i] = sum % 10 + '0';
carry = sum / 10;
}
if(carry){
int k = fib_strlen(res) + 1;
res[k] = '\0';
for(int i = k - 1; i > 0; i--)
res[i] = res[i - 1];
res[0] = '1';
}else
res[l1] = '\0';
}
```
#### 字串長度
這邊參考兩種方式，一種是 [linux kernel](https://github.com/torvalds/linux/blob/master/lib/string.c#L479)，另外一種是 [glibc](https://github.com/lattera/glibc/blob/master/string/strlen.c)
[linux kernel](https://github.com/torvalds/linux/blob/master/lib/string.c#L479) 的方式很簡單，就是用 for 迴圈的方式檢測每個字元是不是結束字元
```c=
/* linux kernel strlen */
size_t strlen(const char *s)
{
const char *sc;
for (sc = s; *sc != '\0'; ++sc)
/* nothing */;
return sc - s;
}
```
[glibc](https://github.com/lattera/glibc/blob/master/string/strlen.c) 的方式就聰明且嚴謹許多，這個例子在[你所不知道的C語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics)有被提到，其主要改進方法如下：
1. 判斷一個字元直到資料對齊(Data Alignment)
- 什麼是資料對齊呢？
- 根據[維基百科](https://en.wikipedia.org/wiki/Data_structure_alignment)的定義，可知資料對齊是根據元素的長度進行填充。舉例來說，例如，在 32 位元的機器中，包含 16 位元和 32 位元的資料結構，為了對齊 32 位元的值，填充在 16 位值和 32 位值之間的值。
> - Data alignment is the aligning of elements according to their natural alignment. ==To ensure natural alignment, it may be necessary to insert some padding between structure elements or after the last element of a structure.==
- 也就是說，給定現在的記憶體位址為 0x1001，然而在 0x1008 才是對齊項，就會一個字元一個字元對 '\0' 進行判斷，若是的話就提前結束，不是的話就會在後面使用字 (word) 的判斷
2. 利用 bitwise 操作判斷一個 word，直到找到 `'\0'`，解釋如下所示：
```c
#define DETECT(X) \
(((X) - 0x01010101) & ~(X) & 0x80808080)
```
在數值系統篇當中，可以看到這個巨集是用來偵測 0 的， 0 也是中止符號的 ASCII 碼，若是 `DETECT(0)` 則輸出值不為 0 ，這是就可以判斷是哪個字出現中止符號
3. 這樣的改進對於長的字串有大幅的加速，短的字串速度則與 linux 的方法差不多
```c
size_t fib_strlen(const char *str)
{
const char *char_ptr;
const unsigned long int *longword_ptr;
unsigned long int longword, himagic, lomagic;
/* Handle the first few characters by reading one character at a time.
* Do this until CHAR_PTR is aligned on a longword boundary.
*/
for (char_ptr = str;
((unsigned long int) char_ptr
& (sizeof (longword) - 1)) != 0; ++char_ptr)
if (*char_ptr == '\0')
return char_ptr - str;
/* All these elucidatory comments refer to 4-byte longwords,
* but the theory applies equally well to 8-byte longwords.
*/
longword_ptr = (unsigned long int *) char_ptr;
/* Bits 31, 24, 16, and 8 of this number are zero. Call these bits
the "holes." Note that there is a hole just to the left of
each byte, with an extra at the end:
bits: 01111110 11111110 11111110 11111111
bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
The 1-bits make sure that carries propagate to the next 0-bit.
The 0-bits provide holes for carries to fall into. */
himagic = 0x80808080L;
lomagic = 0x01010101L;
if (sizeof (longword) > 4) {
/* 64-bit version of the magic. */
/* Do the shift in two steps to avoid a warning if long has 32 bits. */
himagic = ((himagic << 16) << 16) | himagic;
lomagic = ((lomagic << 16) << 16) | lomagic;
}
/* Instead of the traditional loop which tests each character,
we will test a longword at a time. The tricky part is testing
if *any of the four* bytes in the longword in question are zero. */
for (;;) {
longword = *longword_ptr++;
if (((longword - lomagic) & ~longword & himagic) != 0) {
/* Which of the bytes was the zero? If none of them were, it was
a misfire; continue the search. */
const char *cp = (const char *) (longword_ptr - 1);
if (cp[0] == 0)
return cp - str;
if (cp[1] == 0)
return cp - str + 1;
if (cp[2] == 0)
return cp - str + 2;
if (cp[3] == 0)
return cp - str + 3;
if (sizeof (longword) > 4) {
if (cp[4] == 0)
return cp - str + 4;
if (cp[5] == 0)
return cp - str + 5;
if (cp[6] == 0)
return cp - str + 6;
if (cp[7] == 0)
return cp - str + 7;
}
}
}
}
```
#### 字串複製
字串複製的想法就是相每個字元複製到指定的字串中，最後在加上結束字元
```c
void fib_strncpy(char *dst, char *src, size_t n)
{
// copy the string
for (int i = 0; i < n; i++)
*(dst + i) = *(src + i);
*(dst + n) = '\0';
}
```
### 印出結果
目前透過字串可以得到第500項的費氏數列，其效能如下圖所示
```shell
fib(499) = 86168291600238450732788312165664788095941068326060883324529903470149056115823592713458328176574447204501
fib(500) = 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125
```
如果以相同的程式碼印到第10000項，其曲線為
### 效能分析
首先對比老師的疊代法與我開發的字串疊代法的效能
:::warning
缺點與改進
- 空間浪費的問題：
- 以 `INT_MAX` (2147483647) 為例，`int` 僅需要 4 bytes 就可以表示，但是 char 卻需要用 10 bytes 表示。此時就會造成空間浪費，若要避免浪費空間，不能以字串相加的形式，也就是 "123456" + "456789" 等，需要以 123 + 456 的方式進行，但是出現新的問題，也就是字元相加溢位的問題
- 字元相加，需要考慮字元溢位的問題
:::
### 改變計算方式
上面提到，這種計算方式過於浪費空間。這邊想到，既然都要做整數運算，不如直接使用大型整數型態進行運算，這邊使用 `unsigned long long` 進行，但是這仍然會產生溢位的問題，因此自定義結構，如下所示：
```c
typedef struct fib_num {
unsigned long long *num;
size_t size;
} fib_t;
```
其中 `*num` 進行大數運算，但是 `*num` 是動態陣列，因此需要 `size` 控制其大小，這邊可以重新實做 `fib_add` 的函式
#### 加法
```c
/* F = prev1 + prev2 */
void fib_add(fib_t *prev1, fib_t *prev2, fib_t *F){
// else is prev1 > prev2
int msb = MAX(fib_msb(prev1), fib_msb(prev2));
unsigned int carry = 0;
for(int i=0; i<F->size; i++){
unsigned long long p1 = (i < prev1->size) ? prev1->num[i] : 0;
unsigned long long p2 = (i < prev2->size) ? prev2->num[i] : 0;
unsigned long long sum = p1 + p2 + carry;
F->num[i] = sum;
carry = DETECT_OVERFLOW(p1, p2);
}
if(carry){
fib_resize(F, F->size + 1);
F->num[F->size - 1] = 1;
}
}
```
這邊主要有一個巨集 `DETECT_OVERFLOW` 是偵測有沒有無號長整數 (unsigned long long) 溢位的，上面的使用方式會有問題，這邊先看原本的巨集，這個巨集的想法是參考 CSAPP 第二章：
```c
#define DETECT_OVERFLOW(x, y) ((x) + (y) < MAX(x, y) ? 1 : 0)
```
這會導致第二次溢位的時候無法成功偵測，舉例來說：
依照原本的方式進行加法預期結果如下
```
idx: INT_MAX INTMAX
+ 1
------------------------------
1 0 0
```
但是實際情況是這樣的
```
idx: INT_MAX INTMAX
+ 1
------------------------------
0 0 0
```
因為 `(x) + (y)` 並不是他的和，和應該是 `(x) + (y) + (carry)`，因此進行對應的修改之後即可
```c
#define DETECT_OVERFLOW(x, y, carry) ((x) + (y) + (carry) < MAX(x, y) ? 1 : 0)
```
:::warning
可改用 gcc 的 [Built-in Functions to Perform Arithmetic with Overflow Checking](https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html)
:notes: jserv
:::
#### 印數字
這邊採用比較直覺的方式，以 `f(96)` 舉例說明：
- `f(96)` 無法裝在一個 `unsigned long long` 中，這邊採用陣列的方式進行，可以知道 `f(96)[1] = 2`, `f(96)[0] = 14787220707439219840`，則 `f(96)` 為 `f(96)[1] * (ULL_MAX + 1) + f(96[0])`而這個加法與乘法採用字串形式
- 字串乘法的實做如下：
```c
char *fib_strmul(char *num1, char *num2){
size_t len1 = fib_strlen(num1), len2 = fib_strlen(num2), len = len1+len2;
short *arr = malloc(sizeof(short) * len);
for(int i=0; i<len; i++)
arr[i] = 0;
for(int i=len1-1; i >= 0; i--)
for(int j=len2-1; j >= 0; j--)
arr[i+j+1] += (num1[i]-'0') * (num2[j]-'0');
for(int i=len-1; i > 0; i--){
arr[i-1] += arr[i]/10;
arr[i] %= 10;
}
char *s = malloc(sizeof(char)*(len+1));
int index = 0, i = 0;
if(arr[i]==0) i++;
while(i < len)
s[index++] = arr[i++]+'0';
s[index] = '\0';
return s;
}
```
- 由於以上原因，這邊需要將整數轉成字串，且不使用標準函式庫，這裡的實做如下：
- 首先是將每個數字取餘數放入 0 ~ 9 中，但是這樣數字的順序是相反的，因此最後做一個字串反轉的函式結尾
```c
char *fib_itos(unsigned long long num){
size_t s = 20;
char *res = malloc(s);
int j = 0;
while(num != 0 && j < s){
res[j] = num % 10 + '0';
num /= 10, j++;
}
res[j] = '\0';
s = fib_strlen(res);
fib_strrev(res, s);
res = realloc(res, s + 1);
res[s] = '\0';
return res;
}
```
```c=
char *fib_print(fib_t *F){
char *temp[F->size];
char *res = malloc(256);
res[0] = '0', res[1] = '\0';
for(int i = 0; i< F->size; i++){
temp[i] = fib_itos(F->num[i]);
for(int j = 0; j < i; j++){
temp[i] = fib_strmul(temp[i], ULL_MAX_STR);
}
res = fib_stradd(temp[i], res);
}
return res;
}
```
#### Fibnum Iteration
```shell
...
fib(98) = 135301852344706746049
fib(99) = 218922995834555169026
fib(100) = 354224848179261915075
...
```
放上 User Space 的效能比較，前 100 項：
#### 計算 `MSB`
計算 `MSB` 在 `Fast-Doubling` 的實做可以有效避免使用過多的分支預測尋找最高位數，因此這裡依照 GCC 的方式進行撰寫
```c
unsigned int gcc_clz(unsigned long long x){
/* Boundary Condition */
if (x == 0) return 64;
int n = 1;
if ((x >> 32) == 0) { n += 32; x <<= 32; }
if ((x >> 48) == 0) { n += 16; x <<= 16; }
if ((x >> 56) == 0) { n += 8; x <<= 8; }
if ((x >> 60) == 0) { n += 4; x <<= 4; }
if ((x >> 62) == 0) { n += 2; x <<= 2; }
n = n - (x >> 63);
return n;
}
unsigned int fib_clz(fib_t *F){
return gcc_clz(F->num[F->size-1]) + 64 * (F->size - 1);
}
unsigned int fib_msb(fib_t *F){
return F->size * 64 - 1 - gcc_clz(F->num[F->size-1]);
}
```
#### 減法
減法使用的方式微小學生的直式減法，以下舉例：
```
A: 1 0 0
B: 1
-------------------------
C:
```
先由最右邊的開始減，如果值不夠就往大的借
```
A: - ULL_MAX ULL_MAX + 1
B: 1
-----------------------------
C: ULL_MAX ULL_MAX
```
這樣就完成了，程式碼如下所示：
```c
/* F = prev1 - prev2 */
void fib_sub(fib_t *Big, fib_t *Small, fib_t *F){
/* if Small > Big, Swap */
if(fib_cmp(Big, Small) == -1){
fib_sub(Small, Big, F);
return;
}
int sub_size = MAX(Big->size, Small->size);
fib_resize(F, sub_size);
long long int carry = 0;
for (int i = 0; i < F->size; i++) {
unsigned int B = (i < Big->size) ? Big->num[i] : 0;
unsigned int S = (i < Small->size) ? Small->num[i] : 0;
if(B < S || B < carry){
/* get carry to do */
F->num[i] = ULL_MAX - S + B - carry + 1;
carry = 1;
}else{
F->num[i] = B - S - carry;
carry = 0;
}
}
/* F resize */
size_t n = fib_msi(F);
fib_resize(F, n);
}
```
#### 左移
左移的想法很簡單，然而實作時需要考慮左移大位數(64以上)，也就是如果要左移 64 位元時的實作，我的作法是，移64位元的時候等同左移一個 `index` ，舉例來說：
```c
unsigned long long *a;
a[0] = 1;
/* a << 64 */
a[0] = 0;
a[1] = 1;
```
會變成上面這樣，而左移 0 ~ 63 位元的值，則是使用一般的左移，因此如果今天是左移 94 位的情況下，會進行 1 個 index 的左移以及 30 位的左移，這樣即可實現大數乘法
```c
/* Shift indexes */
void fib_idxlsh(fib_t *F, const unsigned int idx){
fib_resize(F, F->size + idx);
for(int i = F->size - 1; i >= idx; i--)
F->num[i] = F->num[i-idx];
for(int i = 0; i < idx; i++)
F->num[i] = 0;
}
/* Shift at most 63 bit */
void fib_numlsh(fib_t *F, unsigned int bit){
for(int i = F->size - 1; i > 0; i--)
F->num[i] = F->num[i] << bit | F->num[i - 1] >> (64 - bit);
F->num[0] <<= bit;
}
/* left shift */
void fib_lsh(fib_t *F, unsigned int bit, fib_t *dst){
fib_assign(F, dst);
/**
* @brief If we need to shift 64 bit, 129 bit...
* we can first shift >> 63, then shift 1 bit
*/
int count = 0, i;
size_t msb = fib_msb(F);
if(NEED_SIZE(msb) < NEED_SIZE(msb + bit))
fib_resize(dst, NEED_SIZE(msb + bit));
for(i = bit; i > 63; i >>= 6)
count++;
if(count)
fib_idxlsh(dst, i);
bit = bit - (count << 6);
if(bit)
fib_numlsh(dst, bit);
}
```
#### 乘法
這邊乘法的實作是希望利用位元左移及加法進行，利用上面左移的想法可知，這裡實現大數乘法的方式極其簡單，並沒有用到特別複雜的十進位，然而這裡的缺點是對於每個位元都要進行分支預測，這樣會使程式的速度下降。
```c
/* F = prev1 * prev2 */
void fib_mul(fib_t *prev1, fib_t *prev2, fib_t *F){
/**
* @brief Multiple is left shift and add
* @example, there are 1283 * 4567
* 4567 in binary is
* 0b0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0001_0001_1101_0111
* and the MSB(Most Significant Bit) is 12
* the digit in one is 12, 8, 7, 6, 4, 2, 1, 0 (Here is a function)
* Thus, 1283 * 4567 = (1283 << 12) + (1283 << 8) + (1283 << 7) + (1283 << 6)...
*/
size_t m2 = fib_msb(prev2);
fib_zero(F);
fib_t *temp = fib_init(1);
for(int i = 0; i <= m2; i++){
if(fib_bitisone(prev2, i)){
/* prev1 shift left and add to F */
fib_lsh(prev1, i, temp);
fib_add(F, temp, F);
}
}
fib_free(temp);
}
```
#### Fast Doubling
回顧前面提到的公式，主要為以下兩個：
* $F(2k) = F(k) * (2F(k+1) - F(k))$
* $F(2k + 1) = F(k) * F(k) + F(k+1) * F(k+1)$
其程式碼如下：
```c=
char* fibnum_fast_doubling(unsigned int n){
/**
* @brief Fast Doubling Method
* F(2k) = F(k) * (2F(k+1) - F(k))
* F(2k + 1) = F(k) * F(k) + F(k+1) * F(k+1)
*/
fib_t *f1 = fib_init(1); // F(k)
fib_t *f2 = fib_init(1); // F(k + 1)
f1->num[0] = 1;
f2->num[0] = 1;
fib_t *k1 = fib_init(1); // F(2k)
fib_t *k2 = fib_init(1); // F(2k + 1)
int msb = 63 - gcc_clz(10);
/* Fast Doubling */
for(unsigned long long i = 1UL << msb; i > 0; i>>=1){
fib_t *t1 = fib_init(1), *f11 = fib_init(1), *f22 = fib_init(1);
/* F(2k) = F(k) * [ 2 * F(k+1) – F(k) ] */
fib_assign(f2, k1); // k1 = f2
fib_lsh(k1, 1, k1); // k1 = k1 * 2
fib_sub(k1, f1, k1); // k1 = k1 - f1
fib_mul(k1, f1, t1); // k1 = f1 * k1
fib_assign(t1, k1);
/* F(2k+1) = F(k)^2 + F(k+1)^2 */
fib_mul(f1, f1, f11); // f1 = f1 * f1
fib_mul(f2, f2, f22); // f2 = f2 * f2
fib_add(f11, f22, k2); // k2 = f2 + k2
fib_free(t1), fib_free(f11), fib_free(f22);
if (n & i) {
fib_assign(k2, f1);
fib_assign(k1, f2);
fib_add(f2, k2, f2);
} else {
fib_assign(k1, f1);
fib_assign(k2, f2);
}
}
char *s = fib_print(f1);
fib_free(k1);
fib_free(k2);
fib_free(f1);
fib_free(f2);
return s;
}
```
結果探討：
### 改寫成 kernel 形式
前面自己重新撰寫許多 gcc 內建的函式，主要是避免 kernel module 不支援，照裡參考 [Memory Allocation Guide](https://www.kernel.org/doc/html/latest/core-api/memory-allocation.html) 裡的說明
#### 閱讀 Memory Allocation Guide
如果是想要配少量的記憶體，可以使用 `kmalloc`，若是想要使用大量連續的虛擬記憶體，則可以使用 `vmalloc`
> You can ==allocate small chunks using kmalloc== or kmem_cache_alloc families, ==large virtually contiguous areas using vmalloc and its derivatives==, or you can directly request pages from the page allocator with alloc_pages. It is also possible to use more specialized allocators, for instance cma_alloc or zs_malloc.
然而，kernel 在分配記憶體的時候，會查看 GFP flags
這邊還有另外一個細節，就是 kernel 對於 Memory API 來說有其他更安全的方式進行記憶體分配
### 改寫程式碼
這邊經由老師提示後發現有己的函式可以改用內建函式，如 `clz`, `DETECT_OVERFLOW` 等等，可以使用 `__builtin_clz` 與 `__builtin_add_overflow` 進行替換
在 `fibnum.h` 中，會進行以下改動：
```diff=
- unsigned int gcc_clz(unsigned long long);
```
在 `fibnum.c` 的函式 `fib_add` 中，會進行以下改動：
```diff
- DETECT_OVERFLOW()
+ __builtin_add_overflow()
```
這邊如果無腦將 `malloc` 轉成 `kmalloc` 在執行的時候 kernel 會直接當掉，這邊推測原因是 `kmalloc` 的記憶體分配失敗，導致一直出現 `Segmentation Fault` 。這邊有兩個想法解決這個問題，一個是使用 `vmalloc` 另外一個是對 `kmalloc` 分配失敗時給予對應的解決辦法。
由[第 9 週課程問答簡記](https://hackmd.io/@sysprog/HkuTGofVc)的提示進行巨集定義，對於程式在 `User Mode` 與 `Kernel Model` 時會對應產生不同程式碼：
```c=
#ifdef __KERNEL__
/* KERNEL MODE */
#define MALLOC(x) kmalloc(x, GFP_KERNEL)
#define FREE(x) kfree(x)
#define MALLOC_FAIL printk(KERN_ALERT "Failed to malloc")
#define REALLOC_FAIL printk(KERN_ALERT "Failed to realloc")
#define REALLOC(x, size) krealloc((x), (size), GFP_KERNEL)
#else
/* In User Mode */
#define MALLOC(x) malloc(x)
#define FREE(x) free(x)
#define MALLOC_FAIL printf("Failed to malloc\n")
#define REALLOC_FAIL printf("Failed to realloc")
#define REALLOC(x, size) realloc((x), (size))
#endif
```
除了 `MALLOC` 以外，也對於 `MALLOC` 與 `REALLOC` 失敗時產生警訊，若是配置失敗則可以使用 `dmesg` 產生訊息
#### 嘗試 `kmalloc`
對於 `Iteration` 的順利完成，其結果如下：
進行 Fast Doubling 的移植時發現，模組無法順利產生
```shell
sudo insmod fibdrv.ko
make[1]: Leaving directory '/home/khienh/linux_kernel/fibdrv'
sudo ./client > out
Killed
```
這邊使用 `dmesg` 查看錯誤程式碼：
```shell
[ 367.739928] Failed to realloc
[ 367.739931] BUG: kernel NULL pointer dereference, address: 0000000000000000
[ 367.739935] #PF: supervisor write access in kernel mode
[ 367.739936] #PF: error_code(0x0002) - not-present page
```
這邊可以看到是 `REALLOC` 失敗了，這邊對於 `fib_resize` 函式進行調整。若是 `realloc` 失敗，則將原本的記憶體釋放，重新配置，程式碼如下：
```diff=
void fib_resize(fib_t *F, size_t S){
if(!F || F->size == S) return;
- F->num = realloc(F->num, sizeof(unsigned long long) * S);
+ F->num = REALLOC(F->num, sizeof(unsigned long long) * S);
+ if(F->num == NULL){
+ REALLOC_FAIL;
+ unsigned long long *n = MALLOC(sizeof(unsigned long long) * S);
+ if(n == NULL)
+ MALLOC_FAIL;
+ F->num = n;
+ for(int i = 0; i < F->size; i++)
+ F->num[i] = temp[i];
+ FREE(temp);
+ return;
+ }
/* if S is bigger than size, initialize the realloc zone */
if(F->size < S)
for(int i = F->size; i < S; i++)
F->num[i] = 0;
F->size = S;
}
```
但是仍舊無法成功驅動模組，因此我們研究錯誤碼：
```shell=
[26586.967598] Failed to realloc
[26586.967605] Failed to malloc
```
由上可知，儘管增加了應對記憶體分配失敗的手段，重新分配時仍然會失敗
## 不使用動態記憶體
---
## 參考資料
- [fibdrv](https://hackmd.io/@sysprog/linux2022-fibdrv)
Sign in with Wallet
Connect another wallet