L04: fibdrv

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

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

核心模式的時間測量

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.

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

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 是在 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 的文章，並對照 Linux 核心設計: Timer 及其管理機制。

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

static ktime_t kt;

static long long fib_time_proxy(long long k)
{
    kt = ktime_get();
    long long result = fib_sequence(k);
    kt = ktime_sub(ktime_get(), kt);

    return result;
}

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

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

關於 client.c

由 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) 的字串複製到到 fib_read 的 buf 參數後，client 端方可接收到此字串。

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

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 次，對照組為直接平均
  
  

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