owned this note
owned this note
Published
Linked with GitHub
# Linux 核心設計: 第 5 週課堂互動工作區
## jserv
vfork
## guojiun
* ### 在 kernel space 中執行遞迴
* 實驗環境
```shell
$ uname -r
4.15.0-45-generic
```
* 程式碼
```clike=
/*
* fib(2n) = luc(n) fib(n)
* luc(2n) = 5 fib(n)^2 + 2 (-1)^n
*
* fib(2n + 1) = luc(2n + 1) - 2 luc(n) fib(n)
* luc(2n + 1) = 5 fib(n) (fib(n) + luc(n)) / 2 + (-1)^n
*/
static void fib_luc(long long *fib_result, long long *luc_result, long long n)
{
long tmp;
if (n == 0) {
*fib_result = 0;
*luc_result = 2;
return;
}
fib_luc(fib_result, luc_result, n/2);
if (n & 1) {
tmp = *fib_result * *luc_result;
*luc_result = 5 * *fib_result * (*luc_result + *fib_result) / 2;
((n & 2) == 0) ? (*luc_result += 1) : (*luc_result -= 1);
*fib_result = *luc_result - 2 * tmp;
} else {
tmp = (*fib_result) * (*fib_result);
*fib_result = *fib_result * *luc_result;
*luc_result = 5 * tmp;
((n & 2) == 0) ? (*luc_result += 2) : (*luc_result -= 2);
}
}
static long long fib_sequence(long long k)
{
long long result, luc;
fib_luc(&result, &luc, k/2);
if (k & 1) {
result = 5 * result * (luc + result) / 2 - 2 * luc * result;
return (k & 2) == 0 ? ++result : --result;
} else {
return result * luc;
}
}
```
* 因為上述程式為 **遞迴** 形式，考慮到當 k 值很大時，會有 stackoverflow 的風險存在，進而導致系統 crash 。由於深怕無法復原，所以一直遲遲不敢放到 kernel space 去執行。
* 然而，將上述程式放至 fibdrv.c，實際執行後，結果另我很意外。當 k = 100 時，原以為差不多要 stackoverflow 了，結果沒有。k = 1000 呢？ 也沒有。最終試到 k = 10^7 後，也沒 crash 。
* 那我就好奇，如果使用同樣也是 **遞迴** 形式，但 **未經優化** 的版本，k 值可以多大呢？
```clike=
static long long fib_sequence(long long k)
{
if (k == 0) return 0;
if (k == 1) return 1;
return fib_sequence(k - 1) + fib_sequence (k - 2);
}
```
* 實際執行了兩次試驗，當 crash 發生時，此時對應的 k 都為 47。明顯與優化後的版本有極大的差異。
* ### 為何透過 lsmod 命令，可以得知 kernel 中目前有哪些 drivers ？
```shell
$ strace lsmod
openat(AT_FDCWD, "/sys/module/fibdrv/refcnt", O_RDONLY|O_CLOEXEC) = 3
read(3, "0\n", 31) = 2
read(3, "", 29) = 0
close(3) = 0
openat(AT_FDCWD, "/sys/module/fibdrv", O_RDONLY|O_CLOEXEC) = 3
openat(3, "coresize", O_RDONLY|O_CLOEXEC) = 4
read(4, "16384\n", 31) = 6
read(4, "", 25) = 0
close(4) = 0
close(3) = 0
openat(AT_FDCWD, "/sys/module/fibdrv/holders", O_RDONLY|O_NONBLOCK|O_CLOEXEC|O_DIRECTORY) = 3
fstat(3, {st_mode=S_IFDIR|0755, st_size=0, ...}) = 0
getdents(3, /* 2 entries */, 32768) = 48
getdents(3, /* 0 entries */, 32768) = 0
close(3) = 0
write(1, "fibdrv 16384 0\n", 32fibdrv 16384 0
) = 32
...
```
```shell
$ lsmod
Module Size Used by
fibdrv 16384 0
...
```
* 利用 strace 工具，將 lsmod 命令中，有關於 fibdrv 的系統呼叫給列出來。從上述的資訊可以觀察到 insmod 會去讀取 sys/module。
* 根據 [Talking to the Kernel through Sysfs](https://opensourceforu.com/2015/05/talking-to-the-kernel-through-sysfs/) 摘要相關背景知識：
* Sysfs is a RAM based file system. It is designed to export the kernel data structures and their attributes from the kernel to the user space, which then avoids cluttering the /proc file system.
* Through sysfs, user space programs can get information from the kernel sub-system like device drivers.
* [struct kobject](https://elixir.bootlin.com/linux/v4.15/source/include/linux/kobject.h#L65) (Linux Kernel objects)
* char *name
* Struct kobject *parent
* Struct kref
* 我們知道 fibdrv.ko 被載入到 kernel 時，需要經過"一連串"的步驟，一直到 [/kernel/module.c](https://elixir.bootlin.com/linux/v4.15/source/kernel/module.c#L3447) 才執行透過 module_init() 所註冊的 function，也就是 init_fib_dev()。其中，這"一連串"的步驟中，包含了有關於 sysfs 相關的初始化 [/kernel/module.c](https://elixir.bootlin.com/linux/v4.15/source/kernel/module.c#L3755)
`mod_sysfs_setup(mod, info, mod->kp, mod->num_kp);`
* 上述摘要提到，user space 可透過 sysfs 存取device driver，回想之前一般不是透過 /dev/driver-name 嗎？
```shell
# /dev
$ ls -al fibonacci
crw------- 1 root root 240, 0 3月 20 15:13 fibonacci
```
```shell
# /sys/dev/char
$ ls -al 240:0
240:0 -> ../../devices/virtual/fibonacci/fibonacci
```
* Devfs is an alternative to "real" character and block special devices on your root filesystem. Kernel device drivers can register devices by name rather than major and minor numbers. [/dev](http://tldp.org/LDP/Linux-Filesystem-Hierarchy/html/dev.html)
Sign in with Wallet
