2024q1 Homework6 (integration)

contributed by < Wufangni >

開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 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
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  16
  On-line CPU(s) list:   0-15
Vendor ID:               GenuineIntel
  Model name:            12th Gen Intel(R) Core(TM) i5-12500H
    CPU family:          6
    Model:               154
    Thread(s) per core:  2
    Core(s) per socket:  12
    Socket(s):           1
    Stepping:            3
    CPU max MHz:         4500.0000
    CPU min MHz:         400.0000
    BogoMIPS:            6220.80

自我檢查清單

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

Linux 核心 4.4 版以後 Ubuntu Linux 預設使用 EFI_SECURE_BOOT_SIG_ENFORCE，若核心模組沒有簽章則無法掛載至核心，因此需要預先關閉 UEFI Secure Boot 的功能

• 使用 mokutil --sb-state 查看 Secure Boot 是否停用成功。

$ sudo mokutil --sb-state
SecureBoot enabled
SecureBoot validation is disabled in shim

• 檢查核心版本是否大於 5.15.0。

$ uname -r
6.5.0-28-generic

你現在執行的 Linux 核心版本是什麼？

• 安裝 linux-headers 套件及確認是否正確裝於開發環境。

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

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

練習 hello.c 測試

• 新增 hello 目錄，建立兩個檔案 hello.c 及 Makefile，編譯核心模組產生 hello.ko 。

$ make -C /lib/modules/`uname -r`/build M=`pwd` modules

• 嘗試對核心掛載及卸載兩指令

$ sudo insmod hello.ko
$ sudo rmmod hello

• 使用 dmesg 顯示核心訊息

[88338.431769] Hello, world
[88361.955635] Goodbye, cruel world

fibdrv: 可輸出 Fibonacci 數列的 Linux 核心模組

• 取得 fibdrv 程式碼進行 make check 編譯測試，觀察核心模組 fibdrv.ko 。

$ modinfo fibdrv.ko
filename:       /home/fangni/fibdrv/fibdrv.ko
version:        0.1
description:    Fibonacci engine driver
author:         National Cheng Kung University, Taiwan
license:        Dual MIT/GPL
srcversion:     6DA710BB9C77E697D6DBEEA
depends:        
retpoline:      Y
name:           fibdrv
vermagic:       6.5.0-28-generic SMP preempt mod_unload modversions

檔案 fibdrv.c 裡頭的 MODULE_LICENSE, MODULE_AUTHOR, MODULE_DESCRIPTION, MODULE_VERSION 會在編譯 .ko 檔後提供對應的資訊，在 Linux 核心模組運作原理 中以 MODULE_AUTHOR 為例。

在 fibdrv.c 可看到對巨集的定義:

MODULE_AUTHOR("National Cheng Kung University, Taiwan");

回朔至 include/linux/module.h 找到 MODULE_AUTHOR 使用 MODULE_INFO 結構

#define MODULE_AUTHOR(_author) MODULE_INFO(author, _author)

再從 include/linux/moduleparam.h 觀察， __MODULE_INFO 使用到 __UNIQUE_ID 。

#define __MODULE_INFO(tag, name, info)					  \
static const char __UNIQUE_ID(name)[]					  \
  __used __attribute__((section(".modinfo"), unused, aligned(1)))	  \
  = __stringify(tag) "=" info

從 include/linux/compiler-gcc.h 看到定義過程使用了 __PASTE。

#define __UNIQUE_ID(prefix) __PASTE(__PASTE(__UNIQUE_ID_, prefix), __COUNTER__)

再對 __UNIQUE_ID 繼續做展開:

static const char __PASTE(__PASTE(__UNIQUE_ID_, author), __COUNTER__)[]					  \
  __used __attribute__((section(".modinfo"), unused, aligned(1)))	  \
  = __stringify(author) "=" "National Cheng Kung University, Taiwan"

__UNIQUE_ID 使用傳入的兩參數產生一個不重複的名字，__attribute__ 告訴編譯器文字存放的位置及其餘格式設定，__stringify 會將引數轉換成字串，因此 MODULE_ 系列的巨集最後會轉變成唯一獨立的變數。

藉由 strace 追蹤 Linux 核心的掛載

$ sudo strace insmod fibdrv.ko
execve("/usr/sbin/insmod", ["insmod", "fibdrv.ko"], 0x7fff78d52d88 /* 26 vars */) = 0
brk(NULL)                               = 0x55ad5cf7b000
arch_prctl(0x3001 /* ARCH_??? */, 0x7ffd4d65fde0) = -1 EINVAL (Invalid argument)
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7b99da089000
access("/etc/ld.so.preload", R_OK)      = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
newfstatat(3, "", {st_mode=S_IFREG|0644, st_size=58227, ...}, AT_EMPTY_PATH) = 0
mmap(NULL, 58227, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7b99da07a000
close(3)                                = 0
...
close(3)                                = 0
getcwd("/home/fangni/fibdrv", 4096)     = 20
newfstatat(AT_FDCWD, "/home/fangni/fibdrv/fibdrv.ko", {st_mode=S_IFREG|0664, st_size=274752, ...}, 0) = 0
openat(AT_FDCWD, "/home/fangni/fibdrv/fibdrv.ko", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1", 6)               = 6
lseek(3, 0, SEEK_SET)                   = 0
newfstatat(3, "", {st_mode=S_IFREG|0664, st_size=274752, ...}, AT_EMPTY_PATH) = 0
mmap(NULL, 274752, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7b99d9f3a000
finit_module(3, "", 0)                  = 0
munmap(0x7b99d9f3a000, 274752)          = 0
close(3)                                = 0
exit_group(0)                           = ?
+++ exited with 0 +++

追蹤過程中可看到 finit_module 被系統執行，此函數用於動態加載 linux 核心模組，擴展系統功能性及添加新的驅動程序。

• 當我們透過 insmod 去載入一個核心模組時，為何 module_init 所設定的函式得以執行呢？Linux 核心做了什麼事呢?

從 include/linux/module.h 觀察 module_init 的定義方式:

/* Each module must use one module_init(). */
#define module_init(initfn)					\
	static inline initcall_t __maybe_unused __inittest(void)		\
	{ return initfn; }					\
	int init_module(void) __attribute__((alias(#initfn)));

• static inline initcall_t __maybe_unused __inittest(void) 標記函數為未使用並傳回名為 initfn 的初始化函數指針。
• 查閱 GCC 手冊 __attribute__((alias("target"))) 用於給予函數或變量設置別名，讓其指向另一個函數，在這裡 init_module 被給予另一個別名 initfn ，使得加載模組時不會直接使用到 init_module ，而是調用 module_init 函數。
• 從註解中提到每個模組在加載過程中必須使用到 module_init() 進行初始化函數。

系統在執行 finit_module 後會執行 load_module ，從 kernel/module.c 觀察 load_module 定義:

static int load_module(struct load_info *info, const char __user *uargs,
		       int flags)
{
	struct module *mod;
	
        //...

	/* Figure out module layout, and allocate all the memory. */
	mod = layout_and_allocate(info, flags);
	if (IS_ERR(mod)) {
		err = PTR_ERR(mod);
		goto free_copy;
	}

        // ...
	
	return do_init_module(mod);
        // ...
}

使用 layout_and_allocate 對模組進行記憶體配置，接著以 do_init_module 對模組進行初始化。

static noinline int do_init_module(struct module *mod)
{
        // ...
    
	/* Start the module */
	if (mod->init != NULL)
		ret = do_one_initcall(mod->init);
        
        // ...
}

再從 init/main.c 中追述 do_one_initcall 的定義，可看到ret = fn() 實際上針對函數 fn 進行初始化工作。

int __init_or_module do_one_initcall(initcall_t fn)
{
	// ...
	
	do_trace_initcall_start(fn);
	ret = fn();
	do_trace_initcall_finish(fn, ret);

        // ...
}

• 試著執行 $ readelf -a fibdrv.ko, 觀察裡頭的資訊和原始程式碼及 modinfo 的關聯，搭配上述提問，解釋像 fibdrv.ko 這樣的 ELF 執行檔案是如何「植入」到 Linux 核心

Executable and Linking Format(ELF) 可以表示成一種二進制文件格式，用於儲存 Executable File、Shared Library 和 Object File，可分成 ELF header、Section(s)、Section Header(s)三部份。

$ readelf -a fibdrv.ko
ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00 
  Class:                             ELF64
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              REL (Relocatable file)
  Machine:                           Advanced Micro Devices X86-64
  Version:                           0x1
  Entry point address:               0x0
  Start of program headers:          0 (bytes into file)
  Start of section headers:          271424 (bytes into file)
  Flags:                             0x0
  Size of this header:               64 (bytes)
  Size of program headers:           0 (bytes)
  Number of program headers:         0
  Size of section headers:           64 (bytes)
  Number of section headers:         52
  Section header string table index: 51

從 ELF header 中可觀察到 fibdrv.ko 沒有 program headers 等訊息，因此 fibdrv.ko 不是能在 shell 呼叫的可執行檔，需要透過可執行檔 insmod 來將其植入核心，所需使用到 system call 將核心模組的資料複製到 kernel space。

• 閱讀《The Linux Kernel Module Programming Guide》(LKMPG) 並解釋 simrupt 程式碼裡頭的 mutex lock 的使用方式，並探討能否改寫為 lock-free;

simrupt_work_func 使用到 kfifo buffer 與 circular buffer 兩種儲存 data 的方式作為例子，先從 kfifo 觀察，為一種 First-In-First-Out (FIFO) 的結構體，在此定義一個 rx_fifo 的 kfifo 資料結構儲存傳遞到 userspace 的 data。

/* Data are stored into a kfifo buffer before passing them to the userspace */
static struct kfifo rx_fifo;

kfifo 生產資料使用到 kfifo_in 函數，此函數會先確認 buffer 剩餘空間大小是否裝的下生產的資料總長度，若不夠大則以剩餘空間長度為主複製資料到 buffer 中，足夠大則全部複製過去，最後更新 buffer 中插入資料的 index 並回傳插入資料的長度。

/* Insert a value into the kfifo buffer */
static void produce_data(unsigned char val)
{
    /* Implement a kind of circular FIFO here (skip oldest element if kfifo
     * buffer is full).
     */
    unsigned int len = kfifo_in(&rx_fifo, &val, sizeof(val));
    if (unlikely(len < sizeof(val)) && printk_ratelimit())
        pr_warn("%s: %zu bytes dropped\n", __func__, sizeof(val) - len);

    pr_debug("simrupt: %s: in %u/%u bytes\n", __func__, len,
             kfifo_len(&rx_fifo));
}

Circular Buffer 為一種固定大小的環狀記憶體緩衝區，head index 用於指向可插入資料的剩餘空間索引，tail index 則指向消費者即將取出資料的索引位置。

在 include/linux/circ_buf.h 可看到結構體的定義:

struct circ_buf {
    char *buf;
    int head;
    int tail;
};

/* Return count in buffer.  */
#define CIRC_CNT(head,tail,size) (((head) - (tail)) & ((size)-1))

/* Return space available, 0..size-1.  We always leave one free char
 * as a completely full buffer has head == tail, which is the same as
 * empty.
 */
#define CIRC_SPACE(head,tail,size) CIRC_CNT((tail),((head)+1),(size))

CIRC_CNT 被消費者所使用到，用於計算 buffer 內含有的物體數量; CIRC_SPACE 則被生產者所使用，用於計算剩餘空間數量。

static int fast_buf_get(void)
{
    struct circ_buf *ring = &fast_buf;

    /* prevent the compiler from merging or refetching accesses for tail */
    unsigned long head = READ_ONCE(ring->head), tail = ring->tail;
    int ret;

    if (unlikely(!CIRC_CNT(head, tail, PAGE_SIZE)))
        return -ENOENT;

    /* read index before reading contents at that index */
    smp_rmb();

    /* extract item from the buffer */
    ret = ring->buf[tail];

    /* finish reading descriptor before incrementing tail */
    smp_mb();

    /* increment the tail pointer */
    ring->tail = (tail + 1) & (PAGE_SIZE - 1);

    return ret;
}

fast_buf_get 函數代表消費者，分別取得 buffer 的 head 及 tail 後先使用 smp_rmb() 作為記憶體緩衝區保護取出資料的過程，ret = ring->buf[tail] 取出該筆資料後執行 smp_mb() ，並對 tail 做更新，最後回傳取出的資料內容。

接著從 linux/include/linux/workqueue.h 看到兩個 mutex lock 的定義:

/* Mutex to serialize kfifo writers within the workqueue handler */
static DEFINE_MUTEX(producer_lock);

/* Mutex to serialize fast_buf consumers: we can use a mutex because consumers
 * run in workqueue handler (kernel thread context).
 */
static DEFINE_MUTEX(consumer_lock);

producer_lock 作為生產者執行程式時的保護鎖，以 mutex_lock 及 mutex_unlock 方式防止其餘 thread 干擾包在其中的程式，而 consumer_lock 作為消費者的保護鎖，功能與 producer_lock 相似。

while (1) {
        /* Consume data from the circular buffer */
        mutex_lock(&consumer_lock);
        val = fast_buf_get();
        mutex_unlock(&consumer_lock);

        if (val < 0)
            break;

        /* Store data to the kfifo buffer */
        mutex_lock(&producer_lock);
        produce_data(val);
        mutex_unlock(&producer_lock);
    }

在 simrupt_work_func 函式中以 val = fast_buf_get() 執行消費者從 circular buffer 中取出資料，而 produce_data(val) 則是將剛才取出的資料放至 kfifo buffer 中，兩個過程分別都由 mutex_lock 及 mutex_unlock 保護，確保只有一個 thread 可對 buffer 進行存取。

在 simrupt 中單純使用 lock 作為共同資料存取的保護手段，但在多執行緒環境下此方法容易有阻塞問題，也就是說當其中一個 thread 再對共同記憶體進行存取過程時因為 lock 的性質，導致其餘欲使用到此空間的 thread 執行停滯，而若此時原進行存取的執行緒被系統做搶先或直接被 kill 則會造成所有 thread 都被迫暫停工作的情形，因此為了提昇多執行緒的效能達成並行成效，可使用 lock-free 方法做改進。

lock-free 為一種實現並行操作的方法，避免使用 lock 減少執行緒間的競爭關系，它使得執行緒間不須等待其他人釋放 lock 就可以自由操作，主要依賴於 Compare and Swap (CAS) 實現對共用資源的並行存取操作。

int CAS(int *a, int old_val, int new_val) {
    if (*a == old_val) {
        *a = new_val;
        return old_val;
    }
    return *a;
}

CAS 有三種須代入的參數，分別為用來比較的指標變數 *a、指標原先的舊數值 old_val 以及要做替換的新數值 new_val。

int old, new;

do {
    old = *p;
    new = NEW_VALUE;
} while(CAS(*p, old, new) != new);

使用 CAS 包覆的迴圈作為 Critical Section，其空間為共用記憶體做存取，若執行到該空間的內容則 CAS 會去檢查 p 的值是否與原先 old 的值相同，一樣代表此空間沒有被其他執行緒使用過可以將 p 的值替換為 new，而若不相同則重新跑一次迴圈。

• 研讀 CMWQ (Concurrency Managed Workqueue) 文件，對照 simrupt 專案的執行表現，留意到 worker-pools 類型可指定 "Bound" 來分配及限制特定 worker 執行於指定的 CPU，Linux 核心如何做到？CMWQ 關聯的 worker thread 又如何與 CPU 排程器互動？

workqueue 作為 linux 核心對非同步的執行手段，其中 work item 代表欲執行的一種工作項目，創建時會先將其加入到等待佇列( workqueue )中，等待 linux 核心找到適合的 work thread 執行，以往 workqueue 的作法分成兩種方式:

1. single threaded (ST) workqueue
   只依靠單一個 work thread 來處理系統上所有的 work item，因此若前面正執行的 work item 非常龐大，其餘所有的 work 都須等待該work thread 執行結束，雖然有可節省資源的優勢在(只需要少數的 work thread )，但會造成系統執行效率低落的問題。
2. multi threaded (MT) workqueue
   每個 CPU 上會有一個 work thread，對於每個 workqueue 會有自己的一個 thread pool 且數目固定，對於分配到該 CPU 的 work item 有嚴格的綁定關係，不能隨意移到別的 work thread 上執行，需要多個 work thread 配合故十分消耗資源，雖然可緩解執行效率低落的現象，但在並行的效果有限，且不可避免的還是會有死結情況產生。

因此 CMWQ（Concurrent Multi-Queue Workqueue）方法被提出用於解決 ST 及 MT 效能和耗能上的問題，它打破一般對於 workqueue 與特定的 thread pool 之間的關聯性，建立若干個 worker pool (其等於 thread pool 的概念) 可共享給所有的 workqueue ，且可以根據 CPU 的負載情況動態調整 worker pool 大小釋放 work thread ，更好的實現並行，其主要實現的目標有:

• 維持與原始 workqueue 的兼容性
  在與原本 workqueue 相容的情況下原始程式碼可以更容易的移植到 CMWQ，不需要進行過大的改動。
• 共享 per-CPU worker pools
  CMWQ使得每個 workqueue 都可共用 per-CPU worker pools，也就是說不同的 workqueue 可共同使用一個 work pool, 減少資源浪費。
• 黑盒子式調整
  worker pool 和並行等級共同封裝在系統內部，使用者只須使用系統提供的 API 進行提交和管理。

在 CMWQ 設計理念中分為兩種 work pool 類型，屬於Bound 類型的 work pool 會被限制與特定的 CPU 綁定，且每個 CPU 會有兩個 work pool，一個提供給普通的 work，一個則給予高等級的 work，藉由 workqueue 上的 flag 決定由哪一個來執行;屬於 Unbound 類型的 work pool 未與 CPU 做綁定，可動態釋放 work thread 減少資源消耗。

透過 workqueue API 生成的 work item 會根據 workqueue 參數和本身的屬性決定該交由哪個種類的 work pool 處理，而只要 CPU 上存在一個或個正在執行的 worker thread， work pool 就會停止執行新的 work 直到最後一個 worker thread 執行結束，確保不會有尚有 work item 但 worker thread 卻閒置的問題，且不會過度產生 worker thread。

• 探討 Timsort, Pattern Defeating Quicksort (pdqsort) 及 Linux 核心 lib/sort.c 在排序過程中的平均比較次數，並提供對應的數學證明;
• 解釋 xoroshiro128+ 的原理 (對照〈Scrambled Linear Pseudorandom Number Generators〉論文)，並利用 ksort 提供的 xoro 核心模組，比較 Linux 核心內建的 /dev/random 及 /dev/urandom 的速度，說明 xoroshiro128+ 是否有速度的優勢？其弱點又是什麼？