---
tags: linux2022
---
# 2022q1 Homework3 (fibdrv)
contributed by < `yyyyuwen` >
> 作業說明︰ [K04: fibdrv](https://hackmd.io/@sysprog/linux2022-fibdrv)
### 實驗環境
```shell=
gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04) 9.4.0
lscpu
架構： x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 12
On-line CPU(s) list: 0-11
每核心執行緒數： 2
每通訊端核心數： 6
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 158
Model name: Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
製程： 10
CPU MHz： 2200.000
CPU max MHz: 4100.0000
CPU min MHz: 800.0000
BogoMIPS: 4399.99
虛擬： VT-x
L1d 快取： 192 KiB
L1i 快取： 192 KiB
L2 快取： 1.5 MiB
L3 快取： 9 MiB
NUMA node0 CPU(s)： 0-11
```
### 預期目標
* 撰寫適用於 Linux 核心層級的程式
* 學習 ktimer, copy_to_user 一類的核心 API
* 複習 C 語言 [數值系統](https://hackmd.io/@sysprog/c-numerics) 和 [bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)
* 數值分析和運算改進策略
* 初探 Linux VFS
* 自動測試機制
* 透過工具進行效能分析
### 設置環境
* Linux kernal 版本
```shell
$ uname -a
Linux scream 5.13.0-28-generic #31~20.04.1-Ubuntu SMP Wed Jan 19 14:08:10 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux
```
* 安裝 `linux-headers` 套件
```shell
$ sudo apt install linux-headers-`uname -r`
linux-headers-5.13.0-28-generic 已是最新版本 (5.13.0-28.31~20.04.1)。
```
* 確認 `linux-headers` 套件已正確安裝
```shell
$ dpkg -L linux-headers-5.13.0-28-generic | grep "/lib/modules"
/lib/modules
/lib/modules/5.13.0-28-generic
/lib/modules/5.13.0-28-generic/build
```
* 檢驗目前的使用者身份
```shell
$ whoami
scream
$ sudo whoami
root
```
* 安裝後續會用得到的工具
```shell
$ sudo apt install util-linux strace gnuplot-nox git cppcheck clang-format aspell
```
* `fibdrv.ko` 核心模組
```shell
$ modinfo fibdrv.ko
filename: /home/scream/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-28-generic SMP mod_unload modversions
```
* `fibdrv.ko` 核心模組在 Linux 核心掛載後的行為
```shell
$ sudo insmod fibdrv.ko
$ ls -l /dev/fibonacci
crw------- 1 root root 511, 0 3月 16 18:28 /dev/fibonacci
cat /sys/class/fibonacci/fibonacci/dev
511:0
cat /sys/module/fibdrv/version
0.1
$ lsmod | grep fibdrv
fibdrv 16384 0
$ cat /sys/module/fibdrv/refcnt
0
```
### 開發過程
#### kmalloc & vmalloc
ref : [Linux Memory Management](https://learnlinuxconcepts.blogspot.com/2014/02/linux-memory-management.html]), [kmalloc kzalloc vmalloc malloc 和get_free_page()的區別](https://www.cnblogs.com/alantu2018/p/9000778.html)
兩者皆是管理 kernal 的 memory ， kmalloc 返回的是虛擬位址，且他分配的 memory 在實體上是連續的，對於進行 DMA 的設備很重要。
而 vmalloc 只是虛擬地址連續，實體地址不一定連續。不能直接用於 DMA 。
兩者的工作方式相似，不過因為在實體地址上的不連續，使得效率不高。因此只在不得已時才會使用 vmalloc (通常為了要獲得大塊的 memory )。 vmalloc 分配的一般為大塊內存，而 kmalloc 一般分配的為小塊內存，（一般不超過128k);
實體上連續可做 mmap() -> shared page (延伸)
原文網址：https://kknews.cc/code/5o4lqq8.html
空間主要被分為兩個部份 : user space and kernal space.
user space ： 0～3GB (PAGE_OFFSET, equal to 0xC000000 in 0x86)
kernal space : 3GB～4GB
在這一次的實驗中，我們將會使用 kmalloc ，來實現 big number arithmetic.
### Device Driver 整理
Linux 的 Device Driver 主要分為兩個類型 **Block Device Driver** 與 **Character Device Driver** 。
差別：
* Block Device Driver 是以固定大小長度來傳送轉移資料，且大多是可以隨機存取 (Random Access)，例如硬碟機或光碟。
* Character Device Driver 是以不定長度的字元來傳送資料，且是依循先後順序存取資料，例如印表機、終端機等皆是。他們可以被當作 a stream of butes 來被存取就像 file 一樣。因此 Character dirver要負責至少 open, close, read, and write 的system call。
#### 幾個重要功能
* `module_init(sys_init)` module 被 Kernel 加載時會使用到
* `module_exit(sys_exit)` 結束時（卸載）會調用到。
```c=
#include <linux / init.h>
#include <linux / module.h>
MODULE_LICENSE(“Dual BSD / GPL”);
static int hello_init(void)
{
printk(KERN_ALERT “Hellow, world\ n”);
return 0;
}
static void hello_exit(void)
{
printk(KERN_ALERT “Goodbye, cruel world\ n”);
}
module_init(hello_init);
module_exit(hello_exit);
```
可以利用 `insmod` 和 `rmmod` 來加載與卸載 module （要在）super user 的模式下。
#### kernel 與 client 的互動
根據[Linux Virtual File System 介面](https://www.win.tue.nl/~aeb/linux/lk/lk-8.html)，會先宣告一個 file_operations 的資料型態 ，如下
```c
const struct file_operations fib_fops = {
.owner = THIS_MODULE,
.read = fib_read,
.write = fib_write,
.open = fib_open,
.release = fib_release,
.llseek = fib_device_lseek,
};
```
接下來會設定一些對應到 VFS system call 的函式。當在使用者模式程式（`client.c`）中呼叫到 system call（`read()`,` write()`...）時，藉由 VFS 將其對應到在 file_operations 裡設定的函式（`fib_read()`, `fib_write()`...）。
### Big Number
參考比對 [kdnvt](https://hackmd.io/@kdnvt/fibdrv#2022q1-Homework3-fibdrv) 與 [KYG-yaya573142](https://hackmd.io/@KYWeng/rkGdultSU#2020q1-Homework2-fibdrv) 兩位同學的作法。
首先因為在計算 $F_{93}$ 之後的數字沒辦法以數值的方式列出，$F_{93}$ 得到的預期輸出為
$F_{92}$ + $F_{91}$
= $4,660,046,610,375,530,309$ + $7,540,113,804,746,346,429$
= $12,200,160,415,121,876,738$
但由於在 64 位元系統中， TMAX = $9,223,372,036,854,775,807$ ，會導致 overflow 的結果，更詳細的解說[在此](https://hackmd.io/@KYWeng/rkGdultSU#F92-%E4%BB%A5%E5%BE%8C%E7%9A%84%E6%95%B8%E5%80%BC%E9%8C%AF%E8%AA%A4%E7%9A%84%E5%8E%9F%E5%9B%A0)。
而改進方式在說明有提及，有兩種方式
1. 拆成兩個 `long long` 的形式：
可以將數字拆成前後兩個 `long long` 的方式，如此一來會變成兩個16位元的數，而有號數最大範圍到$2^{127} - 1_{10}$。
2. 利用 `string` 的方式：
將大數$_{10}$ 以 string 的形式儲存，這樣就可以表示大數。且利用 `long long` 可以消耗較少的 memory usage。
### Iterative 改善方式
原始的程式碼如下，我們可以不需要將所有的值存下來，只需要利用參數來紀錄前一個變數數字就好了。
```c=
static long long fib_sequence(long long k)
{
/* FIXME: C99 variable-length array (VLA) is not allowed in Linux kernel. */
long long f[k + 2];
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= k; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f[k];
}
```
改良如下：
```c=
static long long fib_sequence(long long k)
{
if(k < 2) {
return k;
}
long long k1 = 0, k2 = 1, sum = 0;
for(int i = 2; i <= k; i++) {
sum = k1 + k2;
k1 = k2;
k2 = sum;
}
return k2;
}
```
## 效能分析
參考作業說明跟 [KYG-yaya573142](https://hackmd.io/@KYWeng/rkGdultSU#%E6%8E%92%E9%99%A4%E5%B9%B2%E6%93%BE%E6%95%88%E8%83%BD%E5%88%86%E6%9E%90%E7%9A%84%E5%9B%A0%E7%B4%A0) <排除干擾效能分析的因素> 來做修改
將 CPU 獨立給特定程式來做使用
```shell=
$ cd /etc/default
$ sudo vim grub
```
修改
```shell=
GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=1" #core name will be 0~7 if possesses 8 cores
```
修改之後利用 `sudo update-grub` 更新再重開機。
```shell=
$ cd /sys/devices/system/cpu
$ cat isolated
>> 1
$ taskset -cp 1 #check the affinity of PID=1
>> 0,2-7
```
觀察到 affinity list 不包含該編號的 CPU
#### 將程式固定在特定的 CPU 中執行
```shell=
$ sudo taskset -c 1 ./client
```
透過指定處理器親和性 (processor affinity，亦稱 CPU pinning)，可以將程式固定在特定的 CPU 中執行。且client 只有在 fibdrv 掛載時才能被執行, 因此這個指令將會被寫在另外一個專門量測的 bash 檔，命名為 `performance.sh` 。
#### 抑制 address space layout randomization (ASLR)
原因 ： 為了防範記憶體損壞漏洞被利用的電腦安全技術。ASLR通過隨機放置行程關鍵資料區域的定址空間來防止攻擊者能可靠地跳轉到記憶體的特定位置來利用函式。現代作業系統一般都加設這一機制，以防範惡意程式對已知位址進行Return-to-libc攻擊。 [參考](https://zh.wikipedia.org/zh-tw/%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)
```shell=
$ sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
```
#### 設定 scaling_governor 為 performance (即最高級別)
```shell
$ cat /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
>> powersave
>> powersave
>> powersave
>> powersave
>> powersave
>> powersave
>> powersave
>> powersave
```
```shell=
$ cat performance.sh
for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
do
echo performance > /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
done
$ sudo sh performance.sh
```
#### 針對 Intel 處理器，關閉 turbo boost
```shell=
$ cat /sys/devices/system/cpu/intel_pstate/no_turbo
>> 0
$ sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
```
### 遇到問題
1. 在 `make checck` 時遇到一個錯誤：
```
rmmod: ERROR: Module fibdrv is not currently loaded
make[1]: 離開目錄「/home/scream/fibdrv」
make load
make[1]: 進入目錄「/home/scream/fibdrv」
sudo insmod fibdrv.ko
insmod: ERROR: could not insert module fibdrv.ko: Invalid module format
make[1]: *** [Makefile:25：load] 錯誤 1
make[1]: 離開目錄「/home/scream/fibdrv」
make: *** [Makefile:39：check] 錯誤 2
```
利用 `dmesg` 查看可能出錯的地方
```
disagrees about version of symbol module_layout
```
發現可能是版本有問題，因此重新掛載一次，先 `make clean` 再 `make` 一次就成功了。
Sign in with Wallet
Connect another wallet