2024q1 Homework6 (integration)

contributed by < lintin528 >

自我檢查清單

• 研讀前述 Linux 效能分析 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作

實驗環境

$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:                       x86_64
CPU op-mode(s):                     32-bit, 64-bit
Byte Order:                         Little Endian
Address sizes:                      39 bits physical, 48 bits virtual
CPU(s):                             12
On-line CPU(s) list:                0-11
Thread(s) per core:                 2
Core(s) per socket:                 6
Socket(s):                          1
NUMA node(s):                       1
Vendor ID:                          GenuineIntel
CPU family:                         6
Model:                              151
Model name:                         12th Gen Intel(R) Core(TM) i5-12400
Stepping:                           2
CPU MHz:                            2500.000
CPU max MHz:                        4400.0000
CPU min MHz:                        800.0000
BogoMIPS:                           4992.00
Virtualization:                     VT-x
L1d cache:                          288 KiB
L1i cache:                          192 KiB
L2 cache:                           7.5 MiB
L3 cache:                           18 MiB
NUMA node0 CPU(s):                  0-11

$ uname -r
5.15.0-101-generic

$ dpkg -L linux-headers-5.15.0-101-generic | grep "/lib/modules"
/lib/modules
/lib/modules/5.15.0-101-generic
/lib/modules/5.15.0-101-generic/build

• 閱讀〈Linux 核心模組運作原理〉並對照 Linux 核心原始程式碼 (v6.1+)，解釋 insmod 後，Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)、MODULE_LICENSE 巨集指定的授權條款又對核心有什麼影響 (GPL 與否對於可用的符號列表有關)，以及藉由 strace 追蹤 Linux 核心的掛載，涉及哪些系統呼叫和子系統？

看完這個教材後，剛開始有個粗淺的觀念：核心模組的掛載是為了在不重新編譯 kernel 的情況下加入新的功能。以下寫出各個節點所遇到的問題。

在第一步了解核心模組是如何被編譯的，在當前目錄新增了 hello.c 與 Makefile ，並且透過指令
$ make -C /lib/modules/`uname -r`/build M=`pwd` modules
完成編譯並產出 .ko 檔案，這邊可以看出是透過在 /lib/modules/uname -r/build 目錄下的 Makefile 裡描述編譯操作，但就產出一個疑問，為何我需要建立在當前目錄的 Makefile ?

目前想出的解釋只有需要指定目標模組 obj-m ，以及可以寫一些自定義的規則，所以才需要在當前目錄建立 Makefile。

之後以 fibdrv 為例去探討如何在 linux 核心中掛載模組，在看這部分內容時，其實一開始有點茫然，但看完之後可以大約總結為將每一個 MODULE_XXX 巨集分別透過 __UNIQUE_ID 產生一個獨特的名稱，並且從以下這一段

#define MODULE_INFO(tag, info) __MODULE_INFO(tag, tag, info)
.
.
#define __MODULE_INFO(tag, name, info)					  \
static const char __UNIQUE_ID(name)[]	

可以看出來，產出的名稱其實就是 tag 所對應到的標籤，如 author, license 等等，並且在之後的 __stringify(tag) "=" info ，將其內容轉換為 "操作 = 參數" 的這個形式後，透過
__used __attribute__((section(".modinfo"), unused, aligned(1))) ，在最後所產出的 ELF 格式 object file 中，將先前所生成的字串寫入對應的 .modinfo section。然後去觀察使用 objdump 產出的內容資訊

0000 76657273 696f6e3d 302e3100 64657363  version=0.1.desc
0010 72697074 696f6e3d 4669626f 6e616363  ription=Fibonacc

在 .modinfo section 裡面的其中一小段，第一段 0010 為此段訊息的十六進制 offset ，代表該段數據的偏移量，後面的 76657273 其實是對應到該段文字的 ASCII 碼 ， 76 對應到 v ， 65 對應到 e ，以此類推，至此就是編譯過程中是如何透過 MODULE_XXX 系列的巨集將 module 的資訊寫入此 object 檔案的過程。

下一部分在分析使用 insmod 時，是如何透過系統呼叫將編譯出的 kernel object (.ko) 檔案掛載進 linux 核心中，在最後的總結中可以看出 insmod 實際執行的系統呼叫中主要是透過

openat(AT_FDCWD, "/tmp/fibdrv/fibdrv.ko", O_RDONLY|O_CLOEXEC) = 3
finit_module(3, "", 0)                  = 0

去配置記憶體空間以及加入初始化模組函數的起始位置，而細部觀察 finit_module 系統呼叫的實作，在最後呼叫 load_module ，且實際的記憶體配置就在裡面的 layout_and_allocate ，最後執行 do_init_module ，在其實作中的 ret = fn(); 做實際的模組初始化，另外在讀取 .ko 檔案後事透過 do_init_module 函式實作中的 ret = do_one_initcall(mod->init); 去讀取透過 module_init 將使用者自己寫的 init funciton ，在此情況透過 finit_module 所執行的模組初始化就會更改為使用者自定義的 init_fib_dev 。

• 閱讀《The Linux Kernel Module Programming Guide》(LKMPG) 並解釋 simrupt 程式碼裡頭的 mutex lock 的使用方式，並探討能否改寫為 lock-free;
• 探討 Timsort, Pattern Defeating Quicksort (pdqsort) 及 Linux 核心 lib/sort.c 在排序過程中的平均比較次數，並提供對應的數學證明;
• 研讀 CMWQ (Concurrency Managed Workqueue) 文件，對照 simrupt 專案的執行表現，留意到 worker-pools 類型可指定 "Bound" 來分配及限制特定 worker 執行於指定的 CPU，Linux 核心如何做到？CMWQ 關聯的 worker thread 又如何與 CPU 排程器互動？
• 解釋 xoroshiro128+ 的原理 (對照〈Scrambled Linear Pseudorandom Number Generators〉論文)，並利用 ksort 提供的 xoro 核心模組，比較 Linux 核心內建的 /dev/random 及 /dev/urandom 的速度，說明 xoroshiro128+ 是否有速度的優勢？其弱點又是什麼？
• 解釋 ksort 如何運用 CMWQ 達到並行的排序;