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