# 2022q1 Homework3 (fibdrv)
contributed by < [Herakleos](https://github.com/Herakleos/fibdrv) >
## Reqirements
- [x] 研讀上述 ==Linux 效能分析的提示== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
- [ ] 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
- [x] 複習 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 核心如何追蹤呢？
> 搭配閱讀 [The Linux driver implementer’s API guide » Driver Basics](https://www.kernel.org/doc/html/latest/driver-api/basics.html)
- [ ] 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 [POSIX Thread](https://en.wikipedia.org/wiki/POSIX_Threads) 的程式碼來確認。
## Environment
The same as I mentioned in [lab0-c](https://hackmd.io/@herakleos/linux2022-lab0).
## Prerequisites
### Kernal-modules
Install `linux-headers` package and make sure the package has been installed correctly.
```shell
$ dpkg -L linux-headers-`uname -r` | grep "/lib/modules"
/lib/modules
/lib/modules/5.13.0-35-generic
/lib/modules/5.13.0-35-generic/build
```
After I compiled and test (`make check`) the original program, instead of showing `Passed [-]`, it turns out with several problems.
1. **Skipping BTF generation for ... due to unavailability of vmlinux**
:::info
I am still working on this problem.
:::
```shell
$ readelf -a ./fibdrv.ko | grep BTF
```
2. **insmod: ERROR: could not insert module fibdrv.ko: Operation not permitted**
> [Why do I get “Required key not available” when install 3rd party kernel modules or after a kernel upgrade?](https://askubuntu.com/questions/762254/why-do-i-get-required-key-not-available-when-install-3rd-party-kernel-modules)
As above, something went wrong while installing kernal-modules.
```shell
$ dmesg | tail -1
Lockdown: insmod: unsigned module loading is restricted; see man kernel_lockdown.7
```
```shell
$ sudo mokutil --sb-state
SecureBoot enabled
```
```shell
$ sudo mokutil --disable-validation
$ sudo reboot
```
```shell
$ sudo mokutil --sb-state
SecureBoot enabled
SecureBoot validation is disabled in shim
```
After all these steps, `Passed [-]` will be correctly displayed.
```shell
Passed [-]
f(93) fail
input: 7540113804746346429
expected: 12200160415121876738
```
### Reduce the external interference
* Modify `GRUB_CMDLINE_LINUX_DEFAULT` in `/etc/default/grub`.
```
GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=3"
```
```shell
$ sudo update-grub
$ sudo reboot
```
```shell
$ cat /sys/devices/system/cpu/isolated
3
```
* Address space layout randomization.
```shell
$ sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
```
* Disable turbo mode in Intel structure.
```shell
$ sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
```
```shell
$ sudo taskset -c 3 ./client
```
In order not to do this step repeatly, I put this line in `Makefile`.
### More about `taskset`
:::info
Working on...
:::
### Modify Timer (1)
Replace skipped operation fib_write() to get ktime.
```c
ktime_t kt = ktime_get();
fib_sequence(*offset);
kt = ktime_sub(ktime_get(), kt);
return (ssize_t) ktime_to_ns(kt);
```
This will cause line `diff` return make error, the `script/expected.txt` should therefore be refined.
> [Issue - Make error causes by diff](https://github.com/sysprog21/fibdrv/issues/4)
## Fibonacci
Fix the original fib_sequence(), C99 variable-length array (VLA) is not allowed in Linux kernel.
```c
if (k <= 2)
return !!k;
long long f[3]; // replace variable-length array (VLA)
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= k; i++) {
f[2] = f[0] + f[1];
f[0] = f[1];
f[1] = f[2];
}
return f[2];
```
According to the article, we may calculate fibonacci number by the following formula.
$$
\begin{split}
F(2k) &= F(k)[2F(k+1) - F(k)] \\
F(2k+1) &= F(k+1)^2+F(k)^2
\end{split}
$$
After reading [Calculating Fibonacci Numbers by Fast Doubling](https://gist.github.com/ChunMinChang/f80ef4decca23b88df16f2f7846049b6), I tried to modify `fib_sequence()` as following.
```c
if (k <= 2)
return !!k;
long long f[2];
f[0] = 0; // F(n)
f[1] = 1; // F(n+1)
/* get MSB for the total round of the loop */
for (int i = __builtin_clzll(k) - 1; i >= 0; --i) {
/* F(2n) = F(n) * [ 2 * F(n+1) - F(n) ] */
long long f1 = f[0] * ((f[1] << 1) - f[0]);
/* F(2n+1) = F(n)^2 + F(n+1)^2 */
long long f2 = f[0] * f[0] + f[1] * f[1];
/* k >> i is odd or not */
if ((k >> i) & 1) {
f[0] = f2; // F(2n+1)
f[1] = f1 + f2; // F(2n+2)
} else {
f[0] = f1; // F(2n)
f[1] = f2; // F(2n+1)
}
}
return f[0]; // F(k)
```
By the way, the above [article](https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling) use a for loop to get the MSB.
```c
unsigned int h = 0;
for (unsigned int i = n ; i ; ++h, i >>= 1);
```
### Analysis `__builtin_clz` and other bitwise operation to find MSB
:::info
Working on...
:::
### Modify Timer (2)
Use `escape` (return of `fib_seq_fd_clz`) to avoid the function be removed after optimization.
```c
__attribute__((always_inline)) static inline void escape(void *p) {
__asm__ volatile ("" : : "g"(p) : "memory");
}
```
After add fib_sequence using fast doubling, fib_write should be modified.
```c
ktime_t kt;
long long result = 0;
switch (size) {
case 0:
kt = ktime_get();
fib_sequence(*offset);
kt = ktime_sub(ktime_get(), kt);
break;
case 1:
kt = ktime_get();
result = fib_seq_fd_clz(*offset);
kt = ktime_sub(ktime_get(), kt);
escape(&result);
break;
case 2:
return ktime_to_ns(ktime_get());
default:
return 1;
}
return (ssize_t) ktime_to_ns(kt);
```
:::info
To-do: statistics
:::
## Big Number
> Reading [KYG-yaya573142](https://hackmd.io/@KYWeng/rkGdultSU)
###### tags: `linux2022`
Sign in with Wallet
Connect another wallet