# 2023q1 Homework3 (fibdrv)
contributed by < `25077667` >
## 實驗環境
```shell
$ neofetch
scc@scc-Taipei
--------------
OS: Arch Linux x86_64
Host: Z370M DS3H
Kernel: 6.2.6-arch1-1
Uptime: 35 secs
Packages: 1352 (pacman)
Shell: zsh 5.9
DE: sway
Terminal: /dev/pts/0
CPU: Intel i5-9400F (6) @ 4.100GHz
GPU: NVIDIA GeForce GTX 750 Ti
Memory: 648MiB / 32028MiB
$ gcc -v
gcc version 12.2.1 20230201 (GCC)
$ ldd --version
ldd (GNU libc) 2.37
```
### Linux 版本更新迅速
還正要開始寫作業，一如往常下了 `paru` 滾系統：
令人震驚的 package 出現在眼前：
```
Packages (3) broadcom-wl-6.30.223.271-459 linux-6.2.7.arch1-1 linux-headers-6.2.7.arch1-1
```
阿怎麼兩天前剛滾上 6.2.6，昨天躺在床上沒做實驗，今天起床就 6.2.7 了。
## 自我檢查清單
- [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)〉
:::success
不確定此作業在 Arm Linux 的支援度如何
> 本學期所有作業都在 x86-64 和 Arm64 處理器架構測試過 -- :notes: jserv
考慮會使用 Arm-based machine 進行此作業
> 可能會是 [ALARM - pi4](https://archlinuxarm.org/platforms/armv8/broadcom/raspberry-pi-4)
需要先請問 @jserv 這是否可行?
> 經查詢 [Wikipedia](https://en.wikipedia.org/wiki/Find_first_set) Armv8-A 便有支援 clz，同時 [Arm A-profile A64 Instruction Set Architecture](https://developer.arm.com/documentation/ddi0602/2022-12/Base-Instructions/CLZ--Count-Leading-Zeros-) 也有提到 clz
> 至於 mulq 使用 `__int128` 的 register，在 Arm 中有 [UMULH](https://developer.arm.com/documentation/ddi0596/2020-12/Base-Instructions/UMULH--Unsigned-Multiply-High-) 可以實作 64 位元之乘運算
:::
:::info
結果被各種事情拖了兩個禮拜，火燒屁股該來寫作業了QQ
後來還是會使用 x86-64 平台
並且會盡可能參考同學的開發紀錄，指出開發的優缺點，並且探討具體實現方案
同時能夠以具體實驗進行探討
:::
## 費氏數列在[作業](https://github.com/25077667/fibdrv)中的實作
> 預計會探討 clz/ctz/ffs ... 等等指令在作業中的實作以及效能提昇
>> 至於這點，我想在其他同學也有提出，這裡我就不贅述（當然也是可以 reproduce 實驗結果）
>> 但是我想把自己放在更有價值的地方 （2023-03-18）
>>> 這樣同時也有自己沒有練習到 bitwise operation 的缺點，可能會造成後續對 Linux kernel 的理解過慢，變成曲解註解而舉燭。
### 使用 vscode 進行開發
參考 @Shiritai 的 [作法](https://hackmd.io/@Eroiko/fibdrv-impl) 並且使用他的工具進行自動生成
但是遇到一個問題是他的作法沒有相當完美跨發行版，我是使用 Archlinux，這對應到的 related path 與 Ubuntu 不同。
剛剛有想要 fork 來改成比較 general 的版本。
但是想到還要 associate to package manager 就懶惰了，這作業剩下兩天時間，應該沒有這時間，反正老師也是建議同學使用 Ubuntu，那我也就先不對這提出貢獻。
> 除了 package manager 來取的 linux-headers 安裝在哪裡之外，還要檢查 `uname -m` 的 architecture，有點不幸的是還要建表去對應
>> 比如說 x86_64 -> x84
>> 比如說 aarch64 -> arm
>> 比如說 x86 -> x84
>> 等等
不過很感謝這位同學提供堪用的 toolchain 快速解決問題。
### 查閱 `kamlloc` 的 GFP flags
根據[原始資料](https://www.kernel.org/doc/html/next/core-api/memory-allocation.html)有提到各個 GFP flag 的介紹。
而我根據經驗，以及觀察同學的作業發現：**大多數人都使用** `GFP_KERNEL`，同時該文件也這樣提到：
> Most of the time `GFP_KERNEL` is what you need. Memory for the kernel data structures, DMAable memory, inode cache, all these and many other allocations types can use `GFP_KERNEL`. Note, that using `GFP_KERNEL` implies `GFP_RECLAIM`, which means that direct reclaim may be triggered under memory pressure; the calling context must be allowed to sleep.
但是有一個算是比較特殊的情況，我觀察到 [qwe661234 分析](https://hackmd.io/@qwe661234/linux2022q1-homework3#%E6%AF%94%E8%BC%83%E5%B0%87-bigNum_to_dec-%E5%BE%9E-kernel-space-%E7%A7%BB%E8%87%B3-user-space-%E6%95%88%E8%83%BD%E5%B7%AE%E7%95%B0) `copy_to_user` 執行成本問題。
如此一來，我們何不一開始就分配一段記憶體空間與 user 共用？
原始文件提到：
> Userspace allocations should use either of the `GFP_USER`, `GFP_HIGHUSER` or `GFP_HIGHUSER_MOVABLE` flags. The longer the flag name the less restrictive it is.
而後提到：
> `GFP_USER` is for userspace allocations that also need to be directly accessibly by the kernel or hardware. It is typically used by hardware for buffers that are mapped to userspace (e.g. graphics) that hardware still must DMA to. cpuset limits are enforced for these allocations.
於是我想就此試試看，可否直接使用如此方式，達成 zero-copy。
另外，也希望使用 `GFP_ATOMIC` 以抑制 interrupt 在我們處理記憶體分配時，因中斷而造成的測量誤差；還有 `GFP_USER` 中的 `__GFP_HARDWALL` 更善加利用 cpu isolation 的特性。
### 對 zero-copy 的初步構想
除了上面想要對 GFP flags 進行調整，也有另外一個比較新的 zero-copy 非同步機制： [io_uring](https://man.archlinux.org/man/io_uring.7.en)
## 指出針對大數運算的加速運算 和 縮減記憶體操作成本的舉措
根據 Jserv 老師在課程中提到 Linux kernel 風格的 rbtree 巧妙的使用 memory alignment 的特性，使用指標的 LSB 2 or 3 bit 用來標示親代節點的顏色。
對於這點，我有**不一樣**想法：
:::info
對於軟體工程而言，可讀性、SRP等等比起效能，更應該優先考量。
確實 Kernel 的每一個小小舉措，不論是對效能對記憶體使用，都有至關重要的影響，甚至影響深遠（可參考 system call overhead）。
我們 21 世紀的軟體工程師而言，能夠快速協助隊友一同向前進，寫出更乾淨的程式碼，會比在這著墨幾個 bit 還更有「價格」。
但是反過來從如果從硬體角度，觀察這樣的設計並無不妥。以硬體角度，每根針腳彼此是獨立的，就是定義這個 protocal 的 LSB 是標示親代節點的顏色，不會違反 SRP 原則。
也就是說，這仍然是合理的工程解決方案。
> 只不過我是軟體工程師，既可以寫軟韌，也可以寫 Web backend, Infra, Endpoint product ... 同時還有資安背景的軟體工程師。
> 看待這舉措的角度會比較「軟體」，甚至有點學究。
> 所以就是寫寫想法而已。
:::
> 可讀性當然是軟體開發的關鍵考量，但要看開發者是什麼程度，Linux 核心假設開發者都是持續成長，且樂於分享的人，因此可積極引入各式新技術和多樣策略，包含上面的 rbtree 改進。
> :notes: jserv
Sign in with Wallet
Connect another wallet