---
tags: linux kernel
---
# 2022q1 Homework3 (fibdrv)
contributed by < `jimmy-liu1021` >
## 自我檢查清單
- [x] 研讀上述 ==Linux 效能分析的提示== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
- [x] 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 [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 數快速計算演算法的實作中如何減少乘法運算的成本;
- [ ] 研讀 [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) 的程式碼來確認。
:::danger
說好的開發紀錄呢？
:notes: jserv
:::
:::spoiler 實驗環境
```shell
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0
$ 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: 60
Model name: Intel(R) Core(TM) i7-4770K CPU @ 3.50GHz
Stepping: 3
CPU MHz: 3500.000
CPU max MHz: 3900.0000
CPU min MHz: 800.0000
BogoMIPS: 6999.36
Virtualization: VT-x
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 8 MiB
NUMA node0 CPU(s): 0-7
```
:::
:::spoiler 前期準備
```shell
$ uname -r
5.13.0-39-generic
//確認 linux-headers 套件已正確安裝於開發環境
$ dpkg -L linux-headers-`uname -r` | grep "/lib/modules"
/lib/modules
/lib/modules/5.13.0-39-generic
/lib/modules/5.13.0-39-generic/build
//確認使用者身份不是 root
$ whoami
jimmy
$ sudo whoami
root
//安裝製圖工具
$ sudo apt install util-linux strace gnuplot-nox
//clone `fibdrv` 專案並安裝模組
$ git clone https://github.com/sysprog21/fibdrv
$ cd fibdrv
$ make check
```
此時會發現有報錯
```shell
@diff -u out scripts/expected.txt
```
這道指令是要將 out 與預期的輸出 expected.txt 比對差異，然而實際上去觀察 expected.txt 的內容發現 F(93) 以後的數值亦是錯誤的，因此將此行刪除。
:::
## 排除效能干擾因素
- 查看指定行程的處理器親和性
```shell
$ taskset -cp 1
pid 1's current affinity list: 0-7
```
代表 Process 1 可在第0到第7個 Cpu 中執行
- 若將其中一顆Cpu單獨讓我們使用，量測效能時會更加準確。
```shell
$ cat /etc/default/grub
GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=7"
```
將 `GRUB_CMDLINE_LINUX_DEFAULT` 加上 `isolcpus=7` 以空出第7個Cpu
- 修改完 grub 之後，內有提醒要使用 `update-grub` 指令進行更新
```shell
$ sudo update-grub
```
- 重開機之後再檢查一次，可發現第7個 Cpu 不在列表中
```shell
$ taskset -cp 1
pid 1's current affinity list: 0-6
```
## 測量 Fibonacci sequence 執行時間
### Kernel space
在 kernel space 中，使用 ktime_get 取得時間
```c
static ssize_t fib_write(struct file *file,
const char *buf,
size_t size,
loff_t *offset)
{
ktime_t kt;
switch (size) {
case 0:
kt = ktime_get();
fib_sequence(*offset);
kt = ktime_sub(ktime_get(), kt);
break;
case 1:
kt = ktime_get();
fib_sequence_fdouble(*offset);
kt = ktime_sub(ktime_get(), kt);
break;
default:
return 0;
}
return (ssize_t) ktime_to_ns(kt);
}
```
### User space
在 user space 中，使用 clock_gettime 取得時間
```c
clock_gettime(CLOCK_REALTIME, &t_start);
fz = write(fd, write_buf, 0);
clock_gettime(CLOCK_REALTIME, &t_end);
long long dif = t_end.tv_nsec - t_start.tv_nsec;
```
### System Call
將 kernel space runtime 扣掉 user space runtime 便可估測 system call 所佔用的時間
## 測量 Fast doubling 執行時間
參考 [KYG-yaya573142](https://github.com/KYG-yaya573142/fibdrv/blob/master/fibdrv.c) 中的對於 fast doubling 的實作
```c
static long long fib_sequence_fdouble(long long n)
{
if (n < 2) { /* F(0) = 0, F(1) = 1 */
return n;
}
long long f[2];
unsigned int ndigit = 32 - __builtin_clz(n); /* number of digit in n */
f[0] = 0; /* F(k) */
f[1] = 1; /* F(k+1) */
for (unsigned int i = 1U << (ndigit - 1); i;
i >>= 1) { /* walk through the digit of n */
long long k1 =
f[0] * (f[1] * 2 - f[0]); /* F(2k) = F(k) * [ 2 * F(k+1) – F(k) ] */
long long k2 =
f[0] * f[0] + f[1] * f[1]; /* F(2k+1) = F(k)^2 + F(k+1)^2 */
if (n & i) { /* current binary digit == 1 */
f[0] = k2; /* F(n) = F(2k+1) */
f[1] = k1 + k2; /* F(n+1) = F(2k+2) = F(2k) + F(2k+1) */
} else {
f[0] = k1; /* F(n) = F(2k) */
f[1] = k2; /* F(n+1) = F(2k+1) */
}
}
return f[0];
}
```
### 使用相同的方式測量時間
kernel space 與 user space 近乎 constant time
### 比較 sequential 與 fast doubling 效能差異
## 大數運算
Sign in with Wallet
Connect another wallet