owned this note   changed 6 years ago  
Linked with GitHub

Linux 核心設計: 第 5 週課堂互動工作區

jserv

vfork

guojiun

  • 在 kernel space 中執行遞迴

    • 實驗環境

      ​​​​​​​​$ uname -r
​​​​​​​4.15.0-45-generic

    • 程式碼

      










































      ​​​​​​​​/*
​​​​​​​​ *  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 值可以多大呢？
      





      ​​​​​​​​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 ？

      ​​​​​​​​$ 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

​​​​​​​​...

      ​​​​​​​​$ lsmod

​​​​​​​​Module                  Size  Used by
​​​​​​​​fibdrv                 16384  0
​​​​​​​​...

      • 利用 strace 工具，將 lsmod 命令中，有關於 fibdrv 的系統呼叫給列出來。從上述的資訊可以觀察到 insmod 會去讀取 sys/module。

      • 根據 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 (Linux Kernel objects)

          • char *name
          • Struct kobject *parent
          • Struct kref

      • 我們知道 fibdrv.ko 被載入到 kernel 時，需要經過"一連串"的步驟，一直到 /kernel/module.c 才執行透過 module_init() 所註冊的 function，也就是 init_fib_dev()。其中，這"一連串"的步驟中，包含了有關於 sysfs 相關的初始化 /kernel/module.c

        mod_sysfs_setup(mod, info, mod->kp, mod->num_kp);

      • 上述摘要提到，user space 可透過 sysfs 存取device driver，回想之前一般不是透過 /dev/driver-name 嗎？

        ​​​​​​​​​​​​# /dev
​​​​​​​​​​​​$ ls -al fibonacci 
​​​​​​​​​​​​crw------- 1 root root 240, 0  3月 20 15:13 fibonacci

        ​​​​​​​​​​​​# /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
Select a repo