M06: integration

請務必詳閱作業描述 (一), (二), (三) 及 (四)

主講人: jserv / 課程討論區: 2024 年系統軟體課程

返回「Linux 核心設計/實作」課程進度表

預期目標

• 撰寫適用於 Linux 核心層級的程式
  • 學習 ktimer, copy_to_user 一類的核心 API
• 複習 C 語言 數值系統, 浮點數運算, bitwise 操作, List API, alignment, 遞迴呼叫
• 統整前四次作業的成果
• 運算成本分析及其改進策略
• 初探 Linux VFS
• 透過工具進行效能分析
• 初探並行和多執行緒程式設計

撰寫 Linux 核心模組

請自行參閱以下教材:

• 《The Linux Kernel Module Programming Guide》(LKMPG)

  授課教師為本教材的主編，歡迎提交貢獻和協作，本教材也是 Linux 核心文件推薦的線上教材。至少讀到 15.3 節。

• Linux 核心模組運作原理
• Introduction to Linux kernel driver programming
• Part 1: Introduction
• Part 2: A Character Device

ksort: 處理並行排序的 Linux 核心模組

前期準備

1. 開發環境預期和 lab0 相似，如果你剛好重新安裝 Ubuntu Linux，請依據指示將必要的開發套件裝好;
2. 自本次作業，我們就有分析應用程式和 Linux 核心效能的需求，不該在虛擬機器環境 裡頭測試 (但 container 或 Linux KVM 可接受)，否則會有效能偏差的問題
   $\to$ 及早在實體機器上安裝好 GNU/Linux;

• 自從 Linux 核心 4.4 版以來，Ubuntu Linux 預設開啟 EFI_SECURE_BOOT_SIG_ENFORCE，這使得核心模組需要適度的簽章才可掛載進入 Linux 核心，為了後續測試的便利，我們需要將 UEFI Secure Boot 的功能關閉，請見 Why do I get “Required key not available” when install 3rd party kernel modules or after a kernel upgrade?
• 檢查 Linux 核心版本
  ​​​​$ uname -r
  

  預期是大於等於 5.15.0 的版本，例如 5.15.0-66-generic。若在你的開發環境中，核心版本低於 5.15 的話，需要更新 Linux 核心，請自行參照相關文件
• 安裝 linux-headers 套件 (注意寫法裡頭有 s)，以 Ubuntu Linux 22.04 LTS 為例:
  ​​​​$ sudo apt install linux-headers-`uname -r`
  

• 確認 linux-headers 套件已正確安裝於開發環境
  ​​​​$ dpkg -L linux-headers-5.15.0-102-generic | grep "/lib/modules"
  

  預期得到以下輸出:
  ​​​​/lib/modules/5.15.0-102-generic/build
  

• 檢驗目前的使用者身份
  ​​​​$ whoami
  

  預期為「不是 root 的使用者名稱」，例如 jserv (或者你安裝 Ubuntu Linux 指定的登入帳號名稱)。由於測試過程需要用到 sudo，請一併查驗:
  ​​​​$ sudo whoami
  

  預期輸出是 root
  在下列操作中，請避免用 root 帳號輸入命令，而該善用 sudo

  之後的實驗中，我們會重建 root file system，若濫用 root 權限，很可能就把 GNU/Linux 開發環境不小心破壞 (當然，你還是可重新安裝)，現在開始養成好習慣

• 安裝後續會用得到的工具
  ​​​​$ sudo apt install util-linux strace gnuplot-nox
  

• 取得原始程式碼
  ​​​​$ git clone https://github.com/sysprog21/ksort
  ​​​​$ cd ksort
  

• 編譯並測試
  ​​​​$ make check
  

  預期會看到 2 次綠色的 Passed [-] 字樣
• 觀察產生的 sort.ko 核心模組
  ​​​​$ modinfo sort.ko
  

  預期可得以下輸出:
  ​​​​description:    Concurrent sorting driver
  ​​​​author:         National Cheng Kung University, Taiwan
  ​​​​license:        Dual MIT/GPL
  ​​​​name:           sort
  ​​​​vermagic:       5.15.0-102-generic SMP mod_unload 
  

• 觀察 sort.ko 核心模組在 Linux 核心掛載後的行為（要先透過 insmod 將模組載入核心後才會有下面的裝置檔案 /dev/sort）
  模組載入核心：
  ​​​​$ sudo insmod sort.ko
  

  ​​​​$ ls -l /dev/sort
  ​​​​$ cat /sys/class/sort/sort/dev
  

  新建立的裝置檔案 /dev/sort，注意到 510 這個數字，在你的電腦也許會有出入。試著對照 sort_mod.c，找尋彼此的關聯。
  ​​​​$ cat /sys/module/sort/version 
  

  預期輸出是 0.1，這和 sort_mod.c 透過 MODULE_VERSION 所指定的版本號碼相同。
  ​​​​$ lsmod | grep sort
  ​​​​$ cat /sys/module/sort/refcnt
  

  這兩道命令的輸出都是 0，意味著目前的 reference counting。

ksort 核心模組內部

觀察使用者層級 (user-level) 的程式如何與 ksort 互動: (user.c)

    int fd = open(KSORT_DEV, O_RDWR);
    if (fd < 0) {
        perror("Failed to open character device");
        goto error;
    }

    size_t n_elements = 1000;
    size_t size = n_elements * sizeof(int);
    int *inbuf = malloc(size);
    if (!inbuf)
        goto error;

    for (size_t i = 0; i < n_elements; i++)
        inbuf[i] = rand() % n_elements;

    ssize_t r_sz = read(fd, inbuf, size);
    if (r_sz != size) {
        perror("Failed to write character device");
        goto error;
    }

ksort 設計為一個 character device，可理解是個能夠循序存取檔案，透過定義相關的函式，可利用存取檔案的系統呼叫以存取 (即 open, read, write, mmap 等等)。因此，使用者層級 (user-level 或 userspace) 的程式可透過 read 系統呼叫來得到輸出。

接著來看如何實作: (sort_mod.c)

static ssize_t sort_read(struct file *file,
                         char *buf,
                         size_t size,
                         loff_t *offset)
{
    unsigned long len;
    size_t es;

    void *sort_buffer = kmalloc(size, GFP_KERNEL);
    if (!sort_buffer)
        return 0;

    len = copy_from_user(sort_buffer, buf, size);
    if (len != 0)
        return 0;

    es = sizeof(int);
    sort_main(sort_buffer, size / es, es, num_compare);

    len = copy_to_user(buf, sort_buffer, size);
    if (len != 0)
        return 0;

    kfree(sort_buffer);
    return size;
}

static const struct file_operations fops = {
    .read = sort_read,
    ...
};

不難發現是透過 fops 中的自行定義的 read 來實作讀取操作，而 sort_read 呼叫 Linux 核心的 copy_from_user 來取得使用這層級準備的連續記憶體空間，接著利用實際排序的操作 (即 sort_main 函式)，最後呼叫 Linux 核心的 copy_to_user 來更新使用者空間的記憶體內容。

Linux Virtual File System 介面

透過 Linux Virtual File System 介面，本核心模組可排序使用者層級指定的資料，並讓 client.c 程式得以存取。

VFS 提供一統各式檔案系統的共用介面，方便使用者操作不同的裝置或檔案時，可用一致的方式存取。Linux 的裝置驅動程式大致分為:

• Character Device Driver;
• Block Device Driver;
• Network Device Driver;
  

在使用裝置前需要對其定義一些 file operation，並將其註冊到 kernel 中。
依據 include/linux/fs.h 中的定義

struct file_operations {
    struct module *owner;
    loff_t (*llseek) (struct file *, loff_t, int);
    ssize_t (*read) (struct file *, char __user *, size_t, loff_t *);
    ssize_t (*write) (struct file *, const char __user *, size_t, loff_t *);
    ...
    int (*open) (struct inode *, struct file *);
    ...
    int (*release) (struct inode *, struct file *);
    int (*fsync) (struct file *, loff_t, loff_t, int datasync);
    int (*fasync) (int, struct file *, int);
    int (*lock) (struct file *, int, struct file_lock *);
    ...
} __randomize_layout;

此手法可參見〈你所不知道的 C 語言：物件導向程式設計篇〉。

以本例來說，宣告一個 file_operations 的資料型態並設定一些對應到 VFS 操作的函式 (sort_read, sort_write 等等)。當在使用者模式程式中呼叫到 read 系統呼叫時，藉由 VFS 將其對應到 sort_read。

static const struct file_operations fops = {
    .read = sort_read,
    .write = sort_write,
    .open = sort_open,
    .release = sort_release,
    .owner = THIS_MODULE,
};

對照〈Linux 核心設計: 檔案系統概念及實作手法〉。

由 read 的手冊描述可知， 若 read 成功，會回傳讀進的 byte 數，而 read 的其中一個輸入參數為 count，即所要讀取的 byte 數，但在 client.c 中，計算出的 Fibonacci 數是 read() 的回傳值。

參考〈Linux Driver Tutorial: How to Write a Simple Linux Device Driver〉的第 7 部分 "Using Memory Allocated in User Mode":

The user allocates a special buffer in the user-mode address space. And the other action that the read function must perform is to copy the information to this buffer. The address to which a pointer from that space points and the address in the kernel address space may have different values. That's why we cannot simply dereference the pointer.

也就是說，在使用者模式 (user-mode) 的位址空間配置一個 buffer 空間時，核心裝置驅動不能直接寫入該地址，相反的，需要透過 copy_to_user，將想傳給使用者模式 (即運作中的 client) 的字串複製到到 sort_read 的 buf 參數後，client 端方可接收到此字串。

依據〈Hierarchical performance measurement and modeling of the Linux file system〉研究指出，從核心模式複製資料到使用者層級的時間成本是，每個位元組達 22ns，因此進行效能分析時，要考慮到 copy_to_user 函式的時間開銷，特別留意到資料大小成長後造成的量測誤差。

核心模式的時間測量

LWN 的〈Reinventing the timer wheel〉描述道：

The kernel maintains two types of timers with two distinct use cases. The high-resolution timer ("hrtimer") mechanism provides accurate timers for work that needs to be done in the near future; hrtimer use is relatively rare, but, when hrtimers are used, they almost always run to completion. "Timeouts," instead, are normally used to alert the kernel to an expected event that has failed to arrive — a missing network packet or I/O completion interrupt, for example. The accuracy requirements for these timers are less stringent (it doesn't matter if an I/O timeout comes a few milliseconds late), and, importantly, these timers are usually canceled before they expire.

跟計時有關的功能主要用在二種情境：

1. timer: 安排「在某個時間點做某件事情」。可想像成火車班次表，這個重要的地方是：若某班火車誤點，會連鎖地影響後面所有班次。因此需要較精準的計時機制;
2. timeout: 用來作為逾時的通知，提醒「有東西遲到」。最簡單的例子是 qtest 裡面的 SIGALRM 的使用。這對於時間的精準度要求不高;

其中一種計時方式是用作業系統從開機以來的計時器中斷發生的次數作為計時的依據，這個計時機制叫作 jiffies，很早就存在於 Linux 核心。較舊的 Linux 核心提供一個建議在 jiffies 上的計時機制，叫作 timer wheel。可以參考 A new approach to kernel timers 一文 (註：標題雖然說是 new approach，但這篇寫作時間是 2005 年)。

以 tv1 為例，這是大小是 256 個陣列，看 jiffies 的最低 8 位元代表的數字是多少，就去 tv1 陣列對應的元素找對應需要處理的事件。而 tv2 是 tv1 的陣列，每經過

$2^8$ 次 jiffy ，index 就加一。 tv3 後面以此類推。

不過，這個計時器受限於計時器中斷觸發和實質能處理的的頻率，而這個頻率有其極限。關於中斷，可參見〈Linux 核心設計: 中斷處理和現代架構考量〉。

一個新的機制是跳脫 jiffies，而將計時機制建立在一個新的資料結構 ktime_t 上面，可參考 LWN 的〈The high-resolution timer API〉一文。

hrtimer 是在 Linux 2.6.16 開始有的新的計時機制，裡面使用 ktime_t 這個新的資料結構來進行計時。這個結構體的定義會隨架構有所不同。所以跟大多數 Linux 中的資料結構使用機制類似，都要使用專門的函數來對這個資料型態進行操作，在 x86-64 中這是個 64 位元整數。相關的使用方式如下：

宣告並初始化 ktime_t 物件:

DEFINE_KTIME(name);

這跟 LIST_HEAD 的功能之於 struct list_head 相仿，宣告一個 ktime_t 並初始化成 0。

對 ktime 數值進行運算:

    ktime_t ktime_add(ktime_t kt1, ktime_t kt2);
    ktime_t ktime_sub(ktime_t kt1, ktime_t kt2);  /* kt1 - kt2 */
    ktime_t ktime_add_ns(ktime_t kt, u64 nanoseconds);

與其他時間相關的轉換：

    ktime_t timespec_to_ktime(struct timespec tspec);
    ktime_t timeval_to_ktime(struct timeval tval);
    struct timespec ktime_to_timespec(ktime_t kt);
    struct timeval ktime_to_timeval(ktime_t kt);
    clock_t ktime_to_clock_t(ktime_t kt);
    u64 ktime_to_ns(ktime_t kt);

詳見 IBM 關於 hrtimer 的文章〈Timers and lists in the 2.6 kernel〉，並對照〈Linux 核心設計: Timer 及其管理機制〉。

ktime 相關的 API 可用來測量時間，我們可發現到 write 在此核心模組暫時沒作用，於是可挪用來輸出上一次 fib 的執行時間。以下是示範的修改:

static ktime_t kt;

static long long sort_time_proxy(long long k)
{
    kt = ktime_get();
    long long result = sort_sequence(k);
    kt = ktime_sub(ktime_get(), kt);

    return result;
}

static ssize_t sort_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
    return (ssize_t) sort_time_proxy(*offset);
}

static ssize_t sort_write(struct file *file,
                         const char *buf,
                         size_t size,
                         loff_t *offset)
{
    return ktime_to_ns(kt);
}

Linux 效能分析

無論是伺服器或個人電腦裡頭的 CPU 幾乎都是多核架構，通常在多核心的作業系統中常使用處理器的親和性 (processor affinity，亦稱 CPU pinning) 讓行程 (process) 在特定的 CPU 核中持續執行，不受作業系統排程的干擾。

將行程綁定在特定的 CPU 核上有許多優點，例如一個 cache bound 的程式跟其他比較耗費 CPU 計算的程式一起執行時，將程式綁定在特定的 CPU 核可減少 cache miss 的狀況。另外在兩個行程頻繁的藉由共享記憶體進行資料交換時，將二行程都綁定在同一個 NUMA 節點中也可增進執行效率。

在 Linux 系統中若要將特定的處理器核指定給一個程式或行程使用，可以使用 taskset 命令來設定或取得行程的處理器親和性。

延伸閱讀:

• Linux 核心設計: 不只挑選任務的排程器

查看行程的 CPU affinity

若要查看指定行程的處理器親和性，可使用 taskset 加上 -p 參數再加上該行程的 PID（process ID）：

$ taskset -p PID

其中 PID 就是行程的 ID，例如：

$ taskset -p 1

參考輸出為: (顯然每台主機搭配 Linux 會有多樣結果)

pid 1's current affinity mask: ffffffffffffffff

輸出的 affinity mask 是一個十六進位的 bitmask，將其轉換為二進位格式之後，若位元值為 1 則代表該行程可在這個位元對應的 CPU 核中執行，若位元值為 0 則代表該行程不允許在這個位元對應的 CPU 核中執行。

在上面這個例子中十六進位的 ff 轉成二進位的格式會是 11111111，這 8 個 1 分別代表該行程可以在第 0 到第 7 個 CPU 核中執行，最低（LSB; 最右邊）的位元代表第 0 個 CPU 核，次低的代表第 1 個，以次類推。

如果 affinity mask 是一個 0x11，則代表可在第 0 個與第 4 個 CPU 核執行。若對 bitmask 表示法不易掌握，可加上 -c 參數，讓 taskset 直接輸出 CPU 核的列表：

$ taskset -cp 1

參考輸出為:

pid 1's current affinity list: 0-63

將行程固定在特定的 CPU 中執行

taskset 亦可設定行程的 core mask，將指定的行程固定在特定的 CPU 核中執行：

$ taskset -p COREMASK PID

其中 COREMASK 就是指定的十六進位 core mask，PID 則為行程的 ID。除此之外，亦可使用 -c 參數以 CPU 的核心列表來指定：

$ taskset -cp CORELIST PID

其中 CORELIST 為 CPU 核列表，以逗點分隔各個核的編號或是使用連字號指定連續的區間，例如: 0,2,5,7-10。

例如若要將一個行程固定在第 0 個與第 4 個 CPU 核，則使用：

$ taskset -p 0x11 9030

輸出為：

pid 9030's current affinity mask: ff
pid 9030's new affinity mask: 11

亦可使用 CPU 核列表的方式：

taskset -cp 0,4 9030

兩種方式效果一致。

在 Linux 中的使用者必須有開啟 CAP_SYS_NICE 這個權限，才能更動行程的處理器親和性，而若只是要查看處理器親和性的設定，則沒有限制（任何使用者皆可查詢）。

以特定的 CPU 執行程式

除了更改現有行程的處理器親和性，使用者也可使用 taskset 指定 CPU 核來執行一個新的程式：

$ taskset COREMASK EXECUTABLE

其中 EXECUTABLE 是要執行的程式。
例如若要以第 0 個 CPU 核執行 vlc 則使用：

$ taskset 0x1 vlc

限定 CPU 給特定的程式使用

taskset 可指定行程所使用的 CPU 核，但不代表其他的行程不會使用這些被指定的 CPU 核，如果你不想讓其他的行程干擾你要執行的程式，讓指定的核心只能被自己設定的行程使用，可以使用 isolcpus 這個 Linux 核心起始參數，這個參數可以讓特定的 CPU 核在開機時就被保留下來。

設定的方式有兩種，一個是在開機時使用 boot loader 所提供的自訂開機參數功能，手動加入 isolcpus=cpu_id 參數，或是直接加在 GRUB 的設定檔中，這樣 Linux 的排程器在預設的狀況下就不會將任何一般行程放在這個被保留的 CPU 核中執行，只有那些被 taskset 特別指定的行程可使用這些 CPU 核。

舉例來說，如果想讓第 0 個與第 1 個 CPU 核都被保留下來，則在開機時加入:

isolcpus=0,1

這個 Linux 起始核心參數，然後再使用 taskset 命令將這兩個 CPU 核指定給要執行的程式使用即可。

排除干擾效能分析的因素

• 抑制 address space layout randomization (ASLR)

  ​​​​$ sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
  

• 設定 scaling_governor 為 performance。準備以下 shell script，檔名為 performance.sh:

  ​​​​for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
  ​​​​do
  ​​​​    echo performance > ${i}
  ​​​​done
  

  之後再用 $ sudo sh performance.sh 執行

• 針對 Intel 處理器，關閉 turbo mode

  ​​​​$ sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
  

• 關閉 SMT (Intel 稱它為 Hyper-Threading)

  ​​​​$ sudo sh -c "echo off > /sys/devices/system/cpu/smt/control"
  

用統計手法去除極端值

假設數據分佈接近常態分佈的情況下，一個標準差到三個標準差之內的資料量約佔 68%, 95%, 99.7%

圖片來源: wikipedia

• Python script 實作以及結果

4ce43c4

datas 的資料為計算某個 fibonacci number 的時間，並用此手法去除 95% 區間之外的值

• 其中 z 代表某個 sample 距離 mean 幾個標準差

def outlier_filter(datas, threshold = 2):
    datas = np.array(datas)
    z = np.abs((datas - datas.mean()) / datas.std())
    return datas[z < threshold]

處理計算每個 Fibonacci number 的時間，最後返回處理好資料 (去除 outlier 再取平均)

def data_processing(data_set, n):
    catgories = data_set[0].shape[0]
    samples = data_set[0].shape[1]
    final = np.zeros((catgories, samples))

    for c in range(catgories):        
        for s in range(samples):
            final[c][s] =                                                    \
                outlier_filter([data_set[i][c][s] for i in range(n)]).mean()
    return final

以下是分別是計算

$100th$ 和

$1000th$ Fibonacci number 的結果，單獨一張圖看起來可能還是波動很大，但對照組放下去就能看出差異

• 每個數據取樣 50 次，對照組為直接平均
  
  
  
  

從處理過數據的圖中可以更明顯的看出執行時間有週期性波動的趨勢。