# 2023q1 Homework3 (fibdrv)
contributed by < `sherrygottalent` >

## materials
[L04: fibdrv](https://hackmd.io/@sysprog/linux2023-fibdrv-a)
[Linux Device Drivers: Tutorial for Linux Driver Development](https://www.apriorit.com/dev-blog/195-simple-driver-for-linux-os)

> The Linux kernel is written in the C and Assembler programming languages. C implements the main part of the kernel, while Assembler implements architecture-dependent parts.
> ..
> If a developer makes a mistake when implementing a user-level application, it will not cause problems outside the user application in most cases. But mistakes in the implementation of a kernel module will lead to system-level issues.
>..
> The kernel and its modules represent a single program module and use a single global namespace.

## 開發環境

$ uname -r
5.15.0-67-generic

$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 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):                          8
On-line CPU(s) list:             0-7
每核心執行緒數：                 2
每通訊端核心數：                 4
Socket(s):                       1
NUMA 節點：                      1
供應商識別號：                   GenuineIntel
CPU 家族：                       6
型號：                           142
Model name:                      Intel(R) Core(TM) i7-8550U CPU @ 1.80GHz
製程：                           10
CPU MHz：                        2000.000
CPU max MHz:                     4000.0000
CPU min MHz:                     400.0000
BogoMIPS:                        3999.93
虛擬：                           VT-x
L1d 快取：                       128 KiB
L1i 快取：                       128 KiB
L2 快取：                        1 MiB
L3 快取：                        8 MiB
NUMA node0 CPU(s)：              0-7

## 自我檢查清單

- [ ] 研讀上述 ==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 數快速計算演算法的實作中如何減少乘法運算的成本;
- [ ] 研讀 [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 核心如何追蹤呢？
- [ ] 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 [POSIX Thread](https://en.wikipedia.org/wiki/POSIX_Threads) 的程式碼來確認。

## :penguin: 作業要求

* 回答上述==自我檢查清單==的所有問題，需要附上對應的參考資料和必要的程式碼，以第一手材料 (包含自己設計的實驗) 為佳
* 在 GitHub 上 fork [fibdrv](https://github.com/sysprog21/fibdrv)，目標是修正 Fibonacci 數計算的正確性 (現有實作存在缺陷，請指出)，隨後改善 `fibdrv` 計算 Fibinacci 數列的執行效率，過程中需要量化執行時間，可在 Linux 核心模組和使用層級去測量
* 原本的程式碼只能列出到 Fibonacci(100) 而且==部分輸出是錯誤的數值==，請修改程式碼，列出後方更多數值 (注意: 檢查正確性和數值系統的使用)
* 務必研讀上述 ==Linux 效能分析的提示== 的描述，降低效能分析過程中的干擾;
* 在 Linux 核心模組中，可用 ktime 系列的 API;
* 在 userspace 可用 [clock_gettime](https://linux.die.net/man/2/clock_gettime) 相關 API;
* 善用統計模型，除去極端數值，過程中應詳述你的手法
* 分別[用 gnuplot 製圖](https://hackmd.io/@sysprog/Skwp-alOg)，分析 Fibonacci 數列在核心計算和傳遞到 userspace 的時間開銷，單位需要用 us 或 ns (自行斟酌)
* 嘗試解讀上述實驗的時間分佈，特別是隨著 Fibonacci 數列增長後，對於 Linux 核心的影響。可修改 VFS 函式，允許透過寫入 `/dev/fibonacci` 裝置檔案來變更不同的 Fibonacci 求值的實作程式碼。
* 用 printk 固然方便，但其執行時間易受各種因素而不穩定，除了透過統計來觀察，也可改用核心的 sysfs 介面，後者可讓我們自行宣告 show 和 store 介面來提供讀寫操作，可參見 [Sample kobject implementation](https://elixir.bootlin.com/linux/latest/source/samples/kobject/kobject-example.c) (注意: 切換到對應的 Linux 核心版本)。
* 逐步最佳化 Fibonacci 的執行時間，引入[費氏數列分析](https://hackmd.io/@sysprog/fibonacci-number) 提到的策略，並善用 [clz / ffs](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令 (Linux 核心有對應的包裝函式)，過程中都要充分量化
* 嘗試研讀 [bignum](https://github.com/0xff07/bignum/tree/fibdrv) (`fibdrv` 分支) 的實作，理解其中的技巧並與你的實作進行效能比較，探討個中值得取鏡之處。
* 原理和分析可見 [KYG-yaya573142 的報告](https://hackmd.io/@KYWeng/rkGdultSU)

:::spoiler linux command
- `insmod`
- `lsmod`
- `modprobe`

- `mknod`
- `krealloc` - reallocate memory. The contents will remain unchanged.
:::

### 模組間的相依性和實際使用次數
> However, there is a counter which keeps track of how many processes are using your module. You can see what its value is by looking at the 3rd field with the command cat /proc/modules or sudo lsmod . __《[The Linux Kernel Module Programming Guide](https://sysprog21.github.io/lkmpg/#what-is-a-kernel-module)》

- `teskset` 限定使用指定 CPU 執行
- `isolcpu` isolate 指定 CPU，讓他們只執行某些程式
- 重現

### test
[The Linux Kernel Module Programming](https://sysprog21.github.io/lkmpg/)

---
:::spoiler ...
## 開發環境 trial 2
M1 with AsahiLinux
[Asahi Linux](https://asahilinux.org/)

$ uname -r
6.1.0-rc6-asahi-4-1-ARCH

$gcc --version
gcc (GCC) 12.1.0
Copyright (C) 2022 Free Software Foundation, Inc.

$ lscpu
架構：                  aarch64
  CPU 作業模式：        64-bit
  Byte Order:           Little Endian
CPU(s):                 8
  On-line CPU(s) list:  0-7
供應商識別號：          Apple
  Model name:           Icestorm
    型號：              1
    每核心執行緒數：    1
    每通訊端核心數：    4
    Socket(s):          1
    製程：              0x1
    CPU(s) scaling MHz: 100%
    CPU max MHz:        2064.0000
    CPU min MHz:        600.0000
    BogoMIPS:           48.00
    Flags:              fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 asimddp sha512 asimdfhm dit uscat ilrcpc flagm ssbs sb paca pacg dcpodp flagm2
                         frint
  Model name:           Firestorm
    型號：              1
    每核心執行緒數：    1
    每通訊端核心數：    4
    Socket(s):          1
    製程：              0x1
    CPU(s) scaling MHz: 65%
    CPU max MHz:        2988.0000
    CPU min MHz:        600.0000
    BogoMIPS:           48.00
    Flags:              fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 asimddp sha512 asimdfhm dit uscat ilrcpc flagm ssbs sb paca pacg dcpodp flagm2
                         frint
Vulnerabilities:        
  Itlb multihit:        Not affected
  L1tf:                 Not affected
  Mds:                  Not affected
  Meltdown:             Not affected
  Mmio stale data:      Not affected
  Retbleed:             Not affected
  Spec store bypass:    Mitigation; Speculative Store Bypass disabled via prctl
  Spectre v1:           Mitigation; __user pointer sanitization
  Spectre v2:           Not affected
  Srbds:                Not affected
  Tsx async abort:      Not affected

$ cat /etc/*-release   
NAME="Arch Linux ARM"
PRETTY_NAME="Arch Linux ARM"
ID=archarm
ID_LIKE=arch
BUILD_ID=rolling
ANSI_COLOR="38;2;23;147;209"
HOME_URL="https://archlinuxarm.org/"
DOCUMENTATION_URL="https://archlinuxarm.org/wiki"
SUPPORT_URL="https://archlinuxarm.org/forum"
BUG_REPORT_URL="https://github.com/archlinuxarm/PKGBUILDs/issues"
LOGO=archlinux-logo

.
.
.
Asahi Linux 的指令只有 `wget`， `rpm` `dpkg` 都不支援，安裝 `git` 都會碰到問題，最後還是決定要買一台 windows 電腦作業。
:::

:::spoiler ...

## 開發環境 trial 1
M1 with container

$ uname -r
5.15.49-linuxkit

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

$ lscpu
Architecture:          aarch64
  CPU op-mode(s):      64-bit
  Byte Order:          Little Endian
CPU(s):                8
  On-line CPU(s) list: 0-7
Vendor ID:             0x00
  Model:               0
  Thread(s) per core:  1
  Core(s) per cluster: 8
  Socket(s):           -
  Cluster(s):          1
  Stepping:            0x0
  BogoMIPS:            48.00
  Flags:               fp asimd evtstrm aes pmul
                       l sha1 sha2 crc32 atomics
                        fphp asimdhp cpuid asimd
                       rdm jscvt fcma lrcpc dcpo
                       p sha3 asimddp sha512 asi
                       mdfhm dit uscat ilrcpc fl
                       agm ssbs sb paca pacg dcp
                       odp flagm2 frint
Vulnerabilities:       
  Itlb multihit:       Not affected
  L1tf:                Not affected
  Mds:                 Not affected
  Meltdown:            Not affected
  Mmio stale data:     Not affected
  Spec store bypass:   Vulnerable
  Spectre v1:          Mitigation; __user pointe
                       r sanitization
  Spectre v2:          Not affected
  Srbds:               Not affected
  Tsx async abort:     Not affected

## materials
[Run Linux GUI Apps on macOS using Docker](https://www.youtube.com/watch?v=cNDR6Z24KLM)
[docker CLI cheat sheet](https://docs.docker.com/get-started/docker_cheatsheet.pdf)

## 環境建置
- 安裝 linux-headers 套件 (注意寫法裡頭有 s)

    $ sudo apt install linux-headers-`uname -r`
    Reading package lists... Done
    Building dependency tree       
    Reading state information... Done
    E: Unable to locate package linux-headers-5.15.49-linuxkit
    E: Couldn't find any package by glob 'linux-headers-5.15.49-linuxkit'

[解決方式] 先使用 `apt-cache search linux-headers-` 查詢可用套件，再安裝對應套件
e.g.`linux-headers-5.15.0-48-generic-64k`

    $ dpkg -L linux-headers-5.15.0-48-generic-64k | grep "/lib/modules"
    /lib/modules
    /lib/modules/5.15.0-48-generic-64k
    /lib/modules/5.15.0-48-generic-64k/build

- 檢驗目前的使用者身份

    $ whoami
    libsemigroups

    $ sudo whoami
    root

* 編譯並測試

    $ make check

預期會看到綠色的 ` Passed [-]` 字樣，隨後是

    f(93) fail
    input: 7540113804746346429
    expected: 12200160415121876738

這符合預期，因為給定的 `fibdrv`
Error 1.

    $ make check
    make -C /lib/modules/5.15.49-linuxkit/build M=/home/libsemigroups/linux2023/L04_fibdrv/sysprog/
    make[1]: *** /lib/modules/5.15.49-linuxkit/build: No such file or directory.  Stop.
    make: *** [Makefile:14: all] Error 2

[解決方式] 修改 Makefile argument，寫死 `KDIR := /lib/modules/5.15.0-48-generic-64k/build`
Error 2.

    $ make check
    make -C /lib/modules/5.15.0-48-generic-64k/build M=/home/libsemigroups/linux2023/L04_fibdrv/sysprog/fibdrv modules
    make[1]: Entering directory '/usr/src/linux-headers-5.15.0-48-generic-64k'
    make[1]: Leaving directory '/usr/src/linux-headers-5.15.0-48-generic-64k'
    make unload
    make[1]: Entering directory '/home/libsemigroups/linux2023/L04_fibdrv/sysprog/fibdrv'
    sudo rmmod fibdrv || true >/dev/null
    sudo: rmmod: command not found
    make[1]: Leaving directory '/home/libsemigroups/linux2023/L04_fibdrv/sysprog/fibdrv'
    make load
    make[1]: Entering directory '/home/libsemigroups/linux2023/L04_fibdrv/sysprog/fibdrv'
    sudo insmod fibdrv.ko
    sudo: insmod: command not found
    make[1]: *** [Makefile:24: load] Error 1
    make[1]: Leaving directory '/home/libsemigroups/linux2023/L04_fibdrv/sysprog/fibdrv'
    make: *** [Makefile:38: check] Error 2

[解決方式] `sudo apt-get install insmod `
["Unable to locate package" while trying to install packages with APT](https://askubuntu.com/questions/378558/unable-to-locate-package-while-trying-to-install-packages-with-apt)
.
.
.
更改環境， switch from M1 with container to M1 with Asahi Linux
:::