HackMD
2022q1 Homework3 (fibdrv)
contributed by < Herakleos >
Reqirements
- 研讀上述 Linux 效能分析的提示 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作
- 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 clz / ctz 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
- 複習 C 語言 數值系統 和 bitwise operation，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本;
- 研讀 KYG-yaya573142 的報告，指出針對大數運算，有哪些加速運算和縮減記憶體操作成本的舉措？
lsmod的輸出結果有一欄名為Used by，這是 "each module's use count and a list of referring modules"，但如何實作出來呢？模組間的相依性和實際使用次數 (reference counting) 在 Linux 核心如何追蹤呢？搭配閱讀 The Linux driver implementer’s API guide » Driver Basics
- 注意到
fibdrv.c存在著DEFINE_MUTEX,mutex_trylock,mutex_init,mutex_unlock,mutex_destroy等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 POSIX Thread 的程式碼來確認。
Environment
The same as I mentioned in lab0-c.
Prerequisites
Kernal-modules
Install linux-headers package and make sure the package has been installed correctly.
$ 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.
- Skipping BTF generation for … due to unavailability of vmlinux
I am still working on this problem.
$ readelf -a ./fibdrv.ko | grep BTF
- insmod: ERROR: could not insert module fibdrv.ko: Operation not permitted
As above, something went wrong while installing kernal-modules.
$ dmesg | tail -1
Lockdown: insmod: unsigned module loading is restricted; see man kernel_lockdown.7
$ sudo mokutil --sb-state
SecureBoot enabled
$ sudo mokutil --disable-validation
$ sudo reboot
$ sudo mokutil --sb-state
SecureBoot enabled
SecureBoot validation is disabled in shim
After all these steps, Passed [-] will be correctly displayed.
Passed [-]
f(93) fail
input: 7540113804746346429
expected: 12200160415121876738
Reduce the external interference
- Modify
GRUB_CMDLINE_LINUX_DEFAULTin/etc/default/grub.
GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=3"
$ sudo update-grub
$ sudo reboot
$ cat /sys/devices/system/cpu/isolated
3
- Address space layout randomization.
$ sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
- Disable turbo mode in Intel structure.
$ sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
$ sudo taskset -c 3 ./client
In order not to do this step repeatly, I put this line in Makefile.
More about taskset
Working on…
Modify Timer (1)
Replace skipped operation fib_write() to get ktime.
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.
Fibonacci
Fix the original fib_sequence(), C99 variable-length array (VLA) is not allowed in Linux kernel.
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.
After reading Calculating Fibonacci Numbers by Fast Doubling, I tried to modify fib_sequence() as following.
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 use a for loop to get the MSB.
unsigned int h = 0;
for (unsigned int i = n ; i ; ++h, i >>= 1);
Analysis __builtin_clz and other bitwise operation to find MSB
Working on…
Modify Timer (2)
Use escape (return of fib_seq_fd_clz) to avoid the function be removed after optimization.
__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.
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);
To-do: statistics
Big Number
Reading KYG-yaya573142
