2023q1 Homework3 (fibdrv)

contributed by < Ahsen-lab >

實驗環境

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.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):                          4
On-line CPU(s) list:             0-3
Thread(s) per core:              1
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           165
Model name:                      Intel(R) Core(TM) i5-10400 CPU @ 2.90GHz
Stepping:                        5
CPU MHz:                         2904.002
BogoMIPS:                        5808.00
Hypervisor vendor:               KVM
Virtualization type:             full
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        48 MiB
NUMA node0 CPU(s):               0-3

自我檢查清單

• 研讀上述 Linux 效能分析的提示 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作
  $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
• 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 clz / ctz 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
• 複習 C 語言 數值系統 和 bitwise operation，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本;
• 學習指出針對大數運算的加速運算和縮減記憶體操作成本的舉措，紀錄你的認知和疑惑
• 注意到 fibdrv.c 存在著 DEFINE_MUTEX, mutex_trylock, mutex_init, mutex_unlock, mutex_destroy 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 POSIX Thread 的程式碼來確認。
  $\to$ 搭配閱讀〈並行和多執行緒程式設計〉

作業要求

題目
作業要求

修正 variable-length array (VLA) 警告

若在 Linux module 中使用 variable-length array (VLA) 的機制，編譯過程中會產生警告。因此，為了解決此問題，改用固定大小的陣列來實作求解 Fibonacci 數列的迭代演算法。經修改後，程式碼可以正常編譯和執行。

在新的實作中，迭代演算法從第二項開始進行計算，而不再是從第一項開始。

static long long fib_sequence(long long k)
{
-   /* FIXME: C99 variable-length array (VLA) is not allowed in Linux kernel. */
-   long long f[k + 2];
+   if (k < 1)
+       return 0;

-   f[0] = 0;
-   f[1] = 1;
+   long long f[2] = {1, 1};

-   for (int i = 2; i <= k; i++) {
-       f[i] = f[i - 1] + f[i - 2];
+   for (int i = 2; i < k; i++) {
+       f[1] += f[0];
+       f[0] = f[1] - f[0];
    }

-   return f[k];
+   return f[1];
}

支援大數運算

參考 KYG-yaya573142 / fibdrv

引入大數運算的實作，用來計算

$fib(92)$ 以後的數值。

bn 結構體

完整程式碼

/*
 * bignum data structure
 * number[0] contains least significant bits
 * number[size - 1] contains most significant bits
 * sign = 1 for negative number
 */
typedef struct _bn {
    unsigned int *number;
    unsigned int size;
    int sign;
} bn;

• number - 指向儲存的數值，之後會以 array 的形式來取用
• size - 配置的記憶體大小，單位為 sizeof(unsigned int)
• sign - 0 為正數、1 為負數

bn_to_string

kmalloc(9)

完整程式碼

/*
 * output bn to decimal string
 * Note: the returned string should be freed with the kfree()
 */
char *bn_to_string(const bn *src)
{
    // log10(x) = log2(x) / log2(10) ~= log2(x) / 3.322
    size_t len = (8 * sizeof(int) * src->size) / 3 + 2 + src->sign;
    char *s = kmalloc(len, GFP_KERNEL);
    char *p = s;

    memset(s, '0', len - 1);
    s[len - 1] = '\0';

    /* src.number[0] contains least significant bits */
    for (int i = src->size - 1; i >= 0; i--) {
        /* walk through every bit of bn */
        for (unsigned int d = 1U << 31; d; d >>= 1) {
            /* binary -> decimal string */
            int carry = !!(d & src->number[i]);
            for (int j = len - 2; j >= 0; j--) {
                s[j] += s[j] - '0' + carry;
                carry = (s[j] > '9');
                if (carry)
                    s[j] -= 10;
            }
        }
    }
    // skip leading zero
    while (p[0] == '0' && p[1] != '\0') {
        p++;
    }
    if (src->sign)
        *(--p) = '-';
    memmove(s, p, strlen(p) + 1);
    return s;
}

bn_fib_fdoubling

使用 Fast Doubling 的技巧，在大數運算中計算 Fibonacci 數。

完整程式碼

/*
 * calc n-th Fibonacci number and save into dest
 * using fast doubling algorithm
 */
void bn_fib_fdoubling(bn *dest, unsigned int n)
{
    bn_resize(dest, 1);
    if (n < 2) {  // Fib(0) = 0, Fib(1) = 1
        dest->number[0] = n;
        return;
    }

    bn *f1 = dest;        /* F(k) */
    bn *f2 = bn_alloc(1); /* F(k+1) */
    f1->number[0] = 0;
    f2->number[0] = 1;
    bn *k1 = bn_alloc(1);
    bn *k2 = bn_alloc(1);

    /* walk through the digit of n */
    for (unsigned int i = 1U << 31; i; i >>= 1) {
        /* F(2k) = F(k) * [ 2 * F(k+1) – F(k) ] */
        bn_cpy(k1, f2);
        bn_lshift(k1, 1);
        bn_sub(k1, f1, k1);
        bn_mult(k1, f1, k1);
        /* F(2k+1) = F(k)^2 + F(k+1)^2 */
        bn_mult(f1, f1, f1);
        bn_mult(f2, f2, f2);
        bn_cpy(k2, f1);
        bn_add(k2, f2, k2);
        if (n & i) {
            bn_cpy(f1, k2);
            bn_cpy(f2, k1);
            bn_add(f2, k2, f2);
        } else {
            bn_cpy(f1, k1);
            bn_cpy(f2, k2);
        }
    }
    // return f[0]
    bn_free(f2);
    bn_free(k1);
    bn_free(k2);
}

• dest - 用來儲存
  $fib(n)$
• n - 找出第
  $n$ 個 Fibonacci 數

bn_resize(dest, 1);
if (n < 2) {  // Fib(0) = 0, Fib(1) = 1
    dest->number[0] = n;
    return;
}

bn *f1 = dest;        /* F(k) */
bn *f2 = bn_alloc(1); /* F(k+1) */
f1->number[0] = 0;
f2->number[0] = 1;
bn *k1 = bn_alloc(1);
bn *k2 = bn_alloc(1);

首先確保 dest 的 size 為 1，若 n < 2 則

$fib(n)=n$ 。

初始化 f1 和 f2 為 0 和 1 ，分別對應

$fib(0)$ 和

$fib(1)$ ，再給定兩個變數 k1 和 k2 分別用來儲存

$fib(k)$ 和

$fib(k+1)$ 。

$$\begin{array}{rl}fib(2k)& =fib(k)[2fib(k+1)-fib(k)]\\ fib(2k+1)& =fib(k+1{)}^2+fib(k{)}^2\end{array}$$

根據上述公式並配合 Bottom-up Fast Doubling 的做法，假設要找第

$n$ 個 Fibonacci 數，只需要從左到右依序檢查每個位元，步驟如下：

1. 計算 k1 = fib(2k) 、 k2 = fib(2k+1)
2. 檢查當前位元 i ，若不存在的話跳到第 3 步，否則（假設目前為
   $n=k$）：
   • i = 0 :
     $n=2k$
     • f1 = fib(2k) = k1
     • f2 = fib(2k+1) = k2
   • i = 1 :
     $n=2k+1$
     • f1 = fib(2k+1) = k2
     • f2 = fib(2k+2) = k1 + k2
   • 回到第 2 步
3. 此時
   $n$ 為目標數，回傳 f1 也就是
   $fib(n)$

對應的程式碼：

    /* walk through the digit of n */
    for (unsigned int i = 1U << 31; i; i >>= 1) {
        /* F(2k) = F(k) * [ 2 * F(k+1) – F(k) ] */
        bn_cpy(k1, f2);
        bn_lshift(k1, 1);
        bn_sub(k1, f1, k1);
        bn_mult(k1, f1, k1);
        /* F(2k+1) = F(k)^2 + F(k+1)^2 */
        bn_mult(f1, f1, f1);
        bn_mult(f2, f2, f2);
        bn_cpy(k2, f1);
        bn_add(k2, f2, k2);
        if (n & i) {
            bn_cpy(f1, k2);
            bn_cpy(f2, k1);
            bn_add(f2, k2, f2);
        } else {
            bn_cpy(f1, k1);
            bn_cpy(f2, k2);
        }
    }

量化執行時間

為了分析並改善 Fibonacci 數的計算效率，需要測量並量化執行時間，我們會使用 fib_read() 來計算 Fibonacci 數列，使用者可在 user space 透過指定不同的 offest 作為 Fibonacci 數列的

$n$ 然後透過 read 來輸出

$fib(n)$。

在計算的過程中，傳入 fib_read() 的 size 參數並沒有被使用到，因此我將 size 當作選擇演算法的參數：

• case 0 :
  • 原始迭帶版本的計算方式，因有缺陷，最多只能計算到
    $fib(92)$
• case 1 :
  • 結合了 Fast Doubling 的大數運算函式 bn_fib_fdoubling()

在 case 1 中，首先用 bn_alloc 創建了一個新的大數 fib （用於計算 Fibonacci 數列），然後調用 bn_fib_fdoubling 函式來計算第 *offset 項的 Fibonacci 數。計算完成後，使用 bn_to_string 將結果轉換為字串，並用 copy_to_user 將其複製到 user space 的 buf 中，最後回傳剩餘的未複製成功的字節數。如果一切正常，該函式回傳 0。

static ssize_t fib_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
    bn *fib;
    switch (size) {
    case 0: /* fib_sequence */
        if (*offset > 92)
            *offset = 92;
        return (ssize_t) fib_sequence(*offset);

    case 1: /* bn_fib_fdoubling */
        fib = bn_alloc(1);

        kt = ktime_get();
        bn_fib_fdoubling(fib, *offset);
        kt = ktime_sub(ktime_get(), kt);

        char *p = bn_to_string(fib);
        size_t len = strlen(p) + 1;

        k2u = ktime_get();
        size_t left = copy_to_user(buf, p, len);
        k2u = ktime_sub(ktime_get(), k2u);

        bn_free(fib);
        kfree(p);
        return (ssize_t) left;
    }
    return 0;
}

Fibonacci 數列計算的時間

在 Linux 核心模組中，使用 ktime 系列的 API 來測量 Fibonacci 數列計算的時間，參考 核心模式的時間測量 的做法

kt = ktime_get();
bn_fib_fdoubling(fib, *offset);
kt = ktime_sub(ktime_get(), kt);

kt 為在核心模式下執行 bn_fib_fdoubling(fib, *offset) 的時間，首先，在計算之前先用 ktime_get() 取得當前時間，在計算完成後，再次呼叫 ktime_get() ，用計算後的時間減去計算前的時間，即可得到在核心模式中 Fibonacci 數列計算的時間。

從 kernel 傳遞到 user space 的時間

Fibonacci 數列計算的結果會儲存在 buf 裡面，需要透過 copy_to_user 函式來傳回 user space ， k2u 會儲存資料從 kernel 傳遞到 user space 的時間。

k2u = ktime_get();
size_t left = copy_to_user(buf, p, len);
k2u = ktime_sub(ktime_get(), k2u);

這段程式碼的目的是將 Fibonacci 數列計算的結果傳回給 user space，並測量從 kernel 傳遞到 user space 所需的時間。

copy_to_user 函式用於將計算結果從 kernel 的記憶體區域 p 複製到 user space 的緩衝區 buf 中。在這之前，使用 ktime_get() 函式獲取當前時間，在傳遞結束之後，再次呼叫 ktime_get() 函式，獲取傳遞後時間點，並使用 ktime_sub() 函式計算兩者之差，即為從 kernel 傳遞到 user space 所需的時間，儲存在 k2u 變數中。

read() 在 user space 的執行時間

fibdrv 是一個 character device ，使用者可透過定義相關的函式並使用存取檔案的系統呼叫 (如 read()) 來與裝置互動，也就是說使用者空間 ( userspace ) 的程式可透過 read() 系統呼叫來得到 fibdrv 裝置的輸出。

clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
long long sz = read(fd, buf, 1);
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);

在 user space 中，我使用 clock_gettime(3) 函式來計算 read() 系統呼叫的執行時間。

#include <time.h>
int clock_gettime(clockid_t clk_id, struct timespec *tp);

clk_id 參數可用來指定不同的計時器

• CLOCK_PROCESS_CPUTIME_ID ： 當前進程在 CPU 上執行的時間。

這個計時器不會包括行程被阻塞的時間，因此可以更好地測量行程的實際執行時間。

具體而言，首先獲取當前時間點，稱為 start ，接著執行 read() 系統呼叫，獲取讀取的字元數 sz，最後再次使用 clock_gettime() 函式獲取當前時間點，稱為 end 時間點。使用 end 減去 start 可得到 read() 系統呼叫在使用者空間中的執行時間。