2022q1 Homework3 (fibdrv)

contributed by < yyyyuwen >

作業說明︰ K04: fibdrv

實驗環境





























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 語言數值系統和 bitwise 操作
數值分析和運算改進策略
初探 Linux VFS
自動測試機制
透過工具進行效能分析

設置環境

Linux kernal 版本

$ 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 套件

$ sudo apt install linux-headers-`uname -r`
linux-headers-5.13.0-28-generic 已是最新版本 (5.13.0-28.31~20.04.1)。

確認 linux-headers 套件已正確安裝

$ 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

檢驗目前的使用者身份

$ whoami
scream
$ sudo whoami
root

安裝後續會用得到的工具

$ sudo apt install util-linux strace gnuplot-nox git cppcheck clang-format aspell

fibdrv.ko 核心模組

$ 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 核心掛載後的行為

$ 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, kmalloc kzalloc vmalloc malloc 和get_free_page()的區別
兩者皆是管理 kernal 的 memory ， kmalloc 返回的是虛擬位址，且他分配的 memory 在實體上是連續的，對於進行 DMA 的設備很重要。
而 vmalloc 只是虛擬地址連續，實體地址不一定連續。不能直接用於 DMA 。
兩者的工作方式相似，不過因為在實體地址上的不連續，使得效率不高。因此只在不得已時才會使用 vmalloc (通常為了要獲得大塊的 memory )。 vmalloc 分配的一般為大塊內存，而 kmalloc 一般分配的為小塊內存，（一般不超過128k);

實體上連續可做 mmap() -> shared page (延伸)

原文網址：https://kknews.cc/code/5o4lqq8.html

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

空間主要被分為兩個部份 : 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) 結束時（卸載）會調用到。
















#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 介面，會先宣告一個 file_operations 的資料型態，如下

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 與 KYG-yaya573142 兩位同學的作法。
首先因為在計算

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 的結果，更詳細的解說在此。
而改進方式在說明有提及，有兩種方式

拆成兩個 long long 的形式：
可以將數字拆成前後兩個 long long 的方式，如此一來會變成兩個16位元的數，而有號數最大範圍到
$2^{127} - 1_{10}$ 。
利用 string 的方式：
將大數
$_{10}$ 以 string 的形式儲存，這樣就可以表示大數。且利用 long long 可以消耗較少的 memory usage。

Iterative 改善方式

原始的程式碼如下，我們可以不需要將所有的值存下來，只需要利用參數來紀錄前一個變數數字就好了。














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];
}

改良如下：
















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 <排除干擾效能分析的因素> 來做修改

將 CPU 獨立給特定程式來做使用


$ cd /etc/default
$ sudo vim grub

修改


GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=1" #core name will be 0~7 if possesses 8 cores

修改之後利用 sudo update-grub 更新再重開機。





$ cd /sys/devices/system/cpu
$ cat isolated
>> 1
$ taskset -cp 1 #check the affinity of PID=1
>> 0,2-7

觀察到 affinity list 不包含該編號的 CPU

將程式固定在特定的 CPU 中執行


$ sudo taskset -c 1 ./client

透過指定處理器親和性 (processor affinity，亦稱 CPU pinning)，可以將程式固定在特定的 CPU 中執行。且client 只有在 fibdrv 掛載時才能被執行, 因此這個指令將會被寫在另外一個專門量測的 bash 檔，命名為 performance.sh 。

抑制 address space layout randomization (ASLR)

原因：為了防範記憶體損壞漏洞被利用的電腦安全技術。ASLR通過隨機放置行程關鍵資料區域的定址空間來防止攻擊者能可靠地跳轉到記憶體的特定位置來利用函式。現代作業系統一般都加設這一機制，以防範惡意程式對已知位址進行Return-to-libc攻擊。參考


$ sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"

設定 scaling_governor 為 performance (即最高級別)

$ cat /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
>> powersave
>> powersave
>> powersave
>> powersave
>> powersave
>> powersave
>> powersave
>> powersave








$ 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




$ cat /sys/devices/system/cpu/intel_pstate/no_turbo 
>> 0

$ sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"

遇到問題

在 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 一次就成功了。