# 2023q1 Homework3 (fibdrv)

contributed by < [seasonwang0905](https://github.com/seasonwang0905/fibdrv) >

## 實驗環境

$ uname -r
5.19.0-35-generic

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0

$ lscpu
Architecture                x86_64
PU op-mode(s):              32-bit, 64-bit
Address sizes:              39 bits physical, 48 bits virtual
Byte Order:                 Little Endian
CPU(s):                     6
On-line CPU(s) list:        0-5
Vendor ID:                  GenuineIntel
Model name:                 Intel(R) Core(TM) i5-9500 CPU @ 3.00GHz
CPU family:                 6
Model:                      158
Thread(s) per core:         1
Core(s) per socket:         6
Socket(s):                  1
Stepping:                   10
CPU max MHz:                4400.0000
CPU min MHz:                800.0000
BogoMIPS:                   6000.00
L1d cache:                  192 KiB (6 instances)
L1i cache:                  192 KiB (6 instances)
L2 cache:                   1.5 MiB (6 instances)
L3 cahce:                   9 MiB (1 instance)
NUMA node(s):               1
NUMA node0 CPU(s):          0-5

> [作業要求](https://hackmd.io/@sysprog/linux2023-fibdrv/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Flinux2023-fibdrv-g)

:::info
- [x] 研讀上述 ==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 數快速計算演算法的實作中如何減少乘法運算的成本;
- [ ] 學習指出針對大數運算的加速運算和縮減記憶體操作成本的舉措，紀錄你的認知和疑惑
- [ ] 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 [POSIX Thread](https://en.wikipedia.org/wiki/POSIX_Threads) 的程式碼來確認。 $\to$ 搭配閱讀〈[並行和多執行緒程式設計](https://hackmd.io/@sysprog/concurrency)〉
:::

---

## 研讀 Linux 效能分析的提示與描述

根據[時間測量和效能分析](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-c)的敘述，我們可透過命令使 CPU 獨立使用，也可指定行程 (Process) 於特定 CPU 中執行。實作的方式參考 [CPU Isolation & CPU Affinity In Linux](https://www.linkedin.com/pulse/cpu-isolation-affinity-linux-vinit-tirnagarwar) ，文中提到兩種方法:
1. 從開機時的 GNU Grub 目錄中操作，在開機後可使特定的 CPU 不被排程，直到下次重新開機為止
2. 開啟 /etc/default/grub 檔案，並新增以下內容。這種方法會永久更改 CPU 使用方式，直到使用者更動為止。

GRUB_CMDLINE_LINUX="isolcpus=2"

此行將會使 2 號 CPU 在開機後獨立出來，號碼可根據個人需求做更改。接下來，輸入下列命令以更新 Grub

$ sudo update-grub

會看到下列輸出

Sourcing file `/etc/default/grub'
Sourcing file `/etc/default/grub.d/init-select.cfg'
Generating grub configuration file ...
Found linux image: /boot/vmlinuz-5.19.0-35-generic
Found initrd image: /boot/initrd.img-5.19.0-35-generic
Found linux image: /boot/vmlinuz-5.19.0-32-generic
Found initrd image: /boot/initrd.img-5.19.0-32-generic
Memtest86+ needs a 16-bit boot, that is not available on EFI, exiting
Warning: os-prober will be executed to detect other bootable partitions.
Its output will be used to detect bootable binaries on them and create new boot entries.
Found Windows Boot Manager on /dev/nvme1n1p1@/EFI/Microsoft/Boot/bootmgfw.efi
Adding boot menu entry for UEFI Firmware Settings ...
done

在終端機中輸入 `reboot` 重新開機後，再輸入命令 `taskset -p 1` 查詢編號 1 的行程使用的 CPU 編號

由結果得知， 2 號 CUP 已被保留下來了。

除了限定 CPU 給特定的程式使用之外，還需要排除會影響效能分析的因素，根據提示輸入下列命令
* 抑制 [ASLR](https://en.wikipedia.org/wiki/Address_space_layout_randomization)

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

* 設定 scaling_governor 為 performance。在下列路徑中新增 `perfomance.sh` 檔案並寫入

for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
do
    echo performance > ${i}
done

之後再用 `$ sudo sh performance.sh` 執行

* 針對 Intel 處理器，關閉 turbo mode

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

* 關閉 [SMT](https://en.wikipedia.org/wiki/Simultaneous_multithreading)

$ sudo sh -c "echo off > /sys/devices/system/cpu/smt/control"

### 為何不用虛擬機 (Virtual Machine) 進行實驗