Linux 核心設計 Homework3 (lab3)

contributed by < r34796Kevin >

簡介

實作Jserv老師的Linux 核心設計 (Linux Kernel Internals)的作業3,並且盡量完成作業的額外要求

研讀上述 Linux 效能分析的提示描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作
$\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 clz / ctz 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
複習 C 語言數值系統和 bitwise operation，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本;
研讀 KYG-yaya573142 的報告，指出針對大數運算，有哪些加速運算和縮減記憶體操作成本的舉措？
lsmod 的輸出結果有一欄名為 Used by，這是 "each module's use count and a list of referring modules"，但如何實作出來呢？模組間的相依性和實際使用次數 (reference counting) 在 Linux 核心如何追蹤呢？
注意到 fibdrv.c 存在著 DEFINE_MUTEX, mutex_trylock, mutex_init, mutex_unlock, mutex_destroy 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 POSIX Thread 的程式碼來確認。
在 GitHub 上 fork fibdrv，目標是修正 Fibonacci 數計算的正確性 (現有實作存在缺陷，請指出)，隨後改善 fibdrv 計算 Fibinacci 數列的執行效率，過程中需要量化執行時間，可在 Linux 核心模組和使用層級去測量
- 原本的程式碼只能列出到 Fibonacci(100) 而且部分輸出是錯誤的數值，請修改程式碼，列出後方更多數值 (注意: 檢查正確性和數值系統的使用)
- 務必研讀上述 Linux 效能分析的提示的描述，降低效能分析過程中的干擾;
- 在 Linux 核心模組中，可用 ktime 系列的 API;
- 在 userspace 可用 clock_gettime 相關 API;
- 善用統計模型，除去極端數值，過程中應詳述你的手法
- 分別用 gnuplot 製圖，分析 Fibonacci 數列在核心計算和傳遞到 userspace 的時間開銷，單位需要用 us 或 ns (自行斟酌)
- 嘗試解讀上述實驗的時間分佈，特別是隨著 Fibonacci 數列增長後，對於 Linux 核心的影響。可修改 VFS 函式，允許透過寫入 /dev/fibonacci 裝置檔案來變更不同的 Fibonacci 求值的實作程式碼。
  Image Not Showing Possible Reasons
  The image file may be corrupted
  The server hosting the image is unavailable
  The image path is incorrect
  The image format is not supported
  Learn More →
逐步最佳化 Fibonacci 的執行時間，引入費氏數列分析提到的策略，並善用 clz / ffs 一類的指令 (Linux 核心有對應的包裝函式)，過程中都要充分量化
嘗試研讀 bignum (fibdrv 分支) 的實作，理解其中的技巧並與你的實作進行效能比較，探討個中值得取鏡之處。
- 原理和分析可見 KYG-yaya573142 的報告

實作

Fibonacci數列定義為

F_{n} = F_{n - 1} + F_{n - 2}, where F_{0} = 0, F_{1} = 1.















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];

    f[0] = 0;
    f[1] = 1;

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

    return f[k];
}

r34796@r34796-PS63-Modern-8RC:~/kevin/linux2021/fibdrv$ git commit
Dangerous function detected in /home/r34796/kevin/linux2021/fibdrv/fibdrv.c
71:    sprintf(tmp, "%lld\n", runtime);

Read 'Common vulnerabilities guide for C programmers' carefully.
    https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml

排除效能分析上干擾因素

考量到Processor affinity，讓行程 (process) 在特定的 CPU 核心中持續執行，不受作業系統排程的干擾。
查看指定行程的處理器親和性，可使用 taskset 加上 -p 參數再加上該行程的 PID（process ID）：
目前PID 1的行程可以被作業系統排程安排在CPU0~7上。

r34796@r34796-PS63-Modern-8RC:/etc/default$ taskset -cp 1
pid 1 目前的近似者清單：0-7

修改 /etc/default/grub 內的 GRUB_CMDLINE_LINUX_DEFAULT，加入 isolcpus=7 來指定編號 7 的核心不被排程器賦予任務，修改完成後需 sudo update-grub 來更新設定，重開機後即生效。
重新使用taskset -cp 1查看，目前PID 1的行程可以被作業系統排程安排在CPU0~6上。

r34796@r34796-PS63-Modern-8RC:~$ taskset -cp 1
pid 1 目前的近似者清單：0-6

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

透過指定處理器親和性 (processor affinity，亦稱 CPU pinning)，可以將程式固定在特定的 CPU 中執行

$ sudo taskset -c 7 ./client

抑制 address space layout randomization (ASLR)

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

針對 Intel 處理器，關閉 turbo mode

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

實作效能分析

在 Linux 核心模組中，可用 ktime 系列的 API;我挪用read function來輸出上一次 fib 的執行時間。


















static ssize_t fib_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
    ktime_t start = ktime_get();
    ssize_t re = fib_sequence(*offset);
    ktime_t end = ktime_get();
    ktime_t runtime = ktime_sub(end, start);

    char tmp[128];
    memset(tmp, 0, 128);
    snprintf(tmp, sizeof(tmp), "%lld\n", runtime);
    //    strncpy(buf,tmp,128);
    copy_to_user(buf, tmp, 128);

    return re;
}

在 userspace 可用 clock_gettime 相關 API;
















for (int i = 0; i <= offset; i++) {
        struct timespec start, end;
        lseek(fd, i, SEEK_SET);
        clock_gettime(CLOCK_REALTIME, &start);
        sz = read(fd, buf, sizeof(buf));
        clock_gettime(CLOCK_REALTIME, &end);
        printf("Reading from " FIB_DEV
               " at offset %d, returned the sequence "
               "%lld.\n",
               i, sz);
        long long ut = (long long) (end.tv_sec * 1e9 + end.tv_nsec) -
                       (start.tv_sec * 1e9 + start.tv_nsec);
        //得到的執行時間寫進time.txt
        fprintf(fp, "%d %lld %lld\n", i, ut, atoll(buf));
    }

在Linux man page中提到

Sufficiently recent versions of GNU libc and the Linux kernel support the following clocks:

CLOCK_REALTIME
    System-wide realtime clock. Setting this clock requires appropriate privileges. 
CLOCK_MONOTONIC
    Clock that cannot be set and represents monotonic time since some unspecified starting point. 
CLOCK_PROCESS_CPUTIME_ID
    High-resolution per-process timer from the CPU. 
CLOCK_THREAD_CPUTIME_ID
    Thread-specific CPU-time clock.

在這邊我使用CLOCK_REALTIME會產生不正確的結果如下：

如果使用CLOCK_MONOTONIC可以修正這個問題：

撰寫script來幫助測量

針對 SMP IRQ affinity 進行設置，盡量避免 CPU 7 去處理 IRQ。
























CPUID=7
ORIG_ASLR=`cat /proc/sys/kernel/randomize_va_space`
ORIG_GOV=`cat /sys/devices/system/cpu/cpu$CPUID/cpufreq/scaling_governor`
ORIG_TURBO=`cat /sys/devices/system/cpu/intel_pstate/no_turbo`

sudo bash -c "echo 0 > /proc/sys/kernel/randomize_va_space"
sudo bash -c "echo performance > /sys/devices/system/cpu/cpu$CPUID/cpufreq/scaling_governor"
sudo bash -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"

#measure the performance of fibdrv
make all
make unload
make load
sudo taskset -c 7 ./client
gnuplot showtime.gp
make unload

# restore the original system settings
sudo bash -c "echo $ORIG_ASLR >  /proc/sys/kernel/randomize_va_space"
sudo bash -c "echo $ORIG_GOV > /sys/devices/system/cpu/cpu$CPUID/cpufreq/scaling_governor"
sudo bash -c "echo $ORIG_TURBO > /sys/devices/system/cpu/intel_pstate/no_turbo"

將userspace得到的時間減去kernelspace得到的時間，可以測量System Call的時間開銷，我測得的時間約為340ns。

到這裡就能正確進行效能分析的實驗，然而儲存Fibonacci數列的資料型態為long long，只能儲存64位元的資料，因此F₉₂之後的數值會產生overflow，於是接下來實作可以儲存任意精度的數值系統（Big Num）

大數運算

由於計算Fibonacci數列只會用到正整數運算，所以接下來的數值系統實作中運算子（加減乘除）都是針對正整數做運算。

資料結構

為了能夠儲存任意精度，定義一個資料結構bigN，unsigned int *d指向配置的記憶體位置，int size紀錄使用了幾個unsigned int來儲存數值。





typedef struct bigN {
    unsigned int *d;
    int size;  // lenths of array d
} bigN;

bigN_to_string

有了資料結構後，要使我們儲存的資料有意義，要可以將儲存的資料轉換為看得懂的數值，實作一個function將bigN轉換成string。
若一個bigN使用了x個位元儲存資料，最多可以換算成

⌜ l o g_{10} (2^{x}) ⌝

位數，
e.g. 若一個bigN使用了8個位元儲存資料，最多可以儲存

2^{8} - 1 = 255

也就是

⌜ l o g_{10} (255) ⌝

= 3位數。






























char *bigN_to_string(bigN *src)
{
    // log10(x) = log2(x) / log2(10) ~= log2(x) / 3.322
    size_t len = (8 * sizeof(int) * src->size) / 3 + 2;
    char *s = (char *) kmalloc(len, GFP_KERNEL);
    char *p = s;

    memset(s, '0', len - 1);
    s[len - 1] = '\0';
    for (int i = src->size - 1; i >= 0; i--) {
        for (unsigned int mask = 1U << 31; mask; mask >>= 1) {
            /* binary -> decimal string */
            int carry = ((mask & src->d[i]) != 0);
            for (int j = len - 2; j >= 0; j--) {
                s[j] += s[j] - '0' + carry;  // double it
                carry = (s[j] > '9');
                if (carry)
                    s[j] -= 10;
            }
        }
    }
    // skip leading zero
    while (p[0] == '0' && p[1] != '\0') {
        p++;
    }
    memmove(s, p, strlen(p) + 1);

    return s;
}

二進位轉十進位的時候，使用一個mask一一取出most sinificant bit，取出下一個bit的時候要將之前的數值乘2才能正確解讀數值，e.g. 二進位數值1101 取出第一個bit 1，此時string儲存1，取出第二個bit 1，此時string應儲存

3 (1 * 2 + 1)

，取出第三個bit 0，此時string應儲存

6 (3 * 2 + 0)

，取出第四個bit 1，此時string應儲存

13 (6 * 2 + 1)

。

bigN初始化

由於bigN是儲存記憶體位置，故需要搭配使用bigNinit函式配置記憶體位置以及數值。








bigN *bigNinit(unsigned int value)
{
    bigN *new = kmalloc(sizeof(bigN), GFP_KERNEL);
    new->d = kmalloc(sizeof(unsigned int), GFP_KERNEL);
    new->size = 1;
    new->d[0] = value;
    return new;
}

value為儲存的數值。

加法與減法

兩個bigN相加時有可能進位，故要先配置一個大小為newsize的記憶體位置來避免overflow。
實作兩個uint32_t相加的時候，可以用一個小技巧，用一個uint64_t來儲存結果，再使用mask跟位元移位來得到正確的32位元數值與它的進位。
































void bigN_add(bigN *a, bigN *b, bigN *res)
{
    int newsize = MAX(a->size, b->size) + 1;  // To avoid overflow
    // printk("new size is %d",newsize);
    uint32_t *result = kmalloc(newsize * sizeof(uint32_t), GFP_KERNEL);

    memset(result, 0, sizeof(*result));

    uint64_t l = 0;
    for (int i = 0; i < newsize; i++) {
        uint32_t A = (a->size) > i ? a->d[i] : 0;
        uint32_t B = (b->size) > i ? b->d[i] : 0;
        l += (uint64_t) A + B;
        result[i] = l & 0xFFFFFFFF;
        l = l >> 32;
    }
    kfree(res->d);
    // Check the actual size and assign to bigN c

    if (result[newsize - 1] == 0) {
        // printf("a\n");
        newsize--;
        res->d = krealloc(result, newsize * sizeof(uint32_t), GFP_KERNEL);
        res->size = newsize;
    } else {
        // printf("b\n");
        res->d = result;
        res->size = newsize;
    }

    return;
}

減法的實作也差不多。
























static void bigN_sub(bigN *a, bigN *b, bigN *c)
{
    bigN_comp(a, b);
    int newsize = MAX(a->size, b->size);
    unsigned int *result = kmalloc(newsize * sizeof(unsigned int), GFP_KERNEL);
    memset(result, 0, sizeof(*result));
    kfree(c->d);
    c->d = result;
    c->size = newsize;
    long long int carry = 0;
    for (int i = 0; i < c->size; i++) {
        unsigned int A = (i < a->size) ? a->d[i] : 0;
        unsigned int B = (i < b->size) ? b->d[i] : 0;
        carry = (long long int) A - B - carry;
        if (carry < 0) {
            c->d[i] = carry + (1LL << 32);
            carry = 1;
        } else {
            c->d[i] = carry;
            carry = 0;
        }
    }
    bigN_resize(c);
}

乘法

目前採用最簡單的 long multiplication，就像手算乘法一樣疊加上去，輔助函式 bigN_mul_add 負責將每一行的計算結果疊加上去。



















static void bigN_mul(bigN *a, bigN *b, bigN *c)
{
    int newsize = (a->size) * (b->size) + 1;  // avoid overflow
    unsigned int *result = kmalloc(newsize * sizeof(unsigned int), GFP_KERNEL);
    memset(result, 0, sizeof(*result));
    kfree(c->d);
    c->d = result;
    c->size = newsize;
    uint64_t l;
    for (int i = 0; i < a->size; i++) {
        for (int j = 0; j < b->size; j++) {
            uint32_t A = (a->size) > i ? a->d[i] : 0;
            uint32_t B = (b->size) > j ? b->d[j] : 0;
            l = (uint64_t) A * (uint64_t) B;
            bigN_mul_add(c, i + j, l);
        }
    }
    bigN_resize(c);
}












static void bigN_mul_add(bigN *c, int offset, uint64_t l)
{
    uint64_t carry = 0;
    for (int i = offset; i < c->size; i++) {
        carry += c->d[i] + (l & 0xFFFFFFFF);
        c->d[i] = carry;
        carry >>= 32;
        l >>= 32;
        if (!l && !carry)  // done
            return;
    }
}

big num其他輔助函式

釋放bigN記憶體。






static void bigN_free(bigN *a)
{
    kfree(a->d);
    kfree(a);
    return;
}

交換兩個bigN的數值。







static void bigN_swap(bigN *a, bigN *b)
{
    bigN tmp = *a;
    *a = *b;
    *b = tmp;
    return;
}

比較兩個bigN的數值，並返回A=大的，B=小的。














static void bigN_comp(bigN *a, bigN *b)
{
    if (a->size > b->size) {
        return;
    } else if (a->size < b->size) {
        bigN_swap(a, b);
    } else {  // a->size = b->size
        int i = a->size - 1;
        // compare value
        if (a->d[i] < b->d[i]) {
            bigN_swap(a, b);
        }
    }
}

做加法或乘法時為了避免overflow會多分配記憶體空間，bigN_resize可以調整記憶體空間為剛剛好。









static void bigN_resize(bigN *a)
{
    int i = a->size - 1;
    while (a->d[i] == 0) {
        i--;
    }
    a->d = krealloc(a->d, (i + 1) * sizeof(uint32_t), GFP_KERNEL);
    a->size = i + 1;
}

實作大數版本的Fibonacci數列

有了數值系統之後，就可以實作大數版本的Fibonacci數列，先實作一般的Fibonacci運算。時間複雜度為O(n)。
















static bigN *bigNfib_sequence(long long k)
{
    /* FIXME: use clz/ctz and fast algorithms to speed up */
    bigN *a = bigNinit(0);
    bigN *b = bigNinit(1);
    bigN *c = bigNinit(1);
    for (int i = 2; i <= k; i++) {
        bigN_add(a, b, c);  // a + b = c
        bigN_swap(a, b);
        bigN_swap(b, c);
    }
    // bigN_copy(b,ans);
    bigN_free(a);
    bigN_free(c);
    return b;
}

如此一來便可以正確計算

F_{92}

之後的數值，試著計算第500項得到的數字與The first 1001 Fibonacci Numbers相同。

Reading from /dev/fibonacci at offset 500, returned the sequence 
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125.

實作大數版本的Fibonacci數列 (Fast Doubling)

研讀Calculating Fibonacci Numbers by Fast Doubling 後了解到還有一種方法可以時間複雜度O(logn)來計算Fibonacci數列。
Fibonacci數列定義為

F_{n} = F_{n - 1} + F_{n - 2}, where F_{0} = 0, F_{1} = 1.

接下來實作大數版本的Fast Doubling。








































static bigN *bigN_fib_fdoubling(unsigned int n)
{
    // The position of the highest bit of n.
    // So we need to loop `h` times to get the answer.
    // Example: n = (Dec)50 = (Bin)00110010, then h = 6.
    //                               ^ 6th bit from right side
    unsigned int h = 0;
    for (unsigned int i = n; i; ++h, i >>= 1)
        ;
    bigN *f0 = bigNinit(0);
    bigN *f1 = bigNinit(1);
    bigN *a = bigNinit(1);
    bigN *b = bigNinit(1);
    bigN *f2k = bigNinit(1);
    bigN *f2k1 = bigNinit(1);

    for (unsigned int mask = 1 << (h - 1); mask; mask >>= 1) {
        /* F(2k) = F(k) * [ 2 * F(k+1) – F(k) ] */
        bigN_add(f1, f1, a);   // a = 2f1
        bigN_sub(a, f0, b);    // b = 2f1-f0
        bigN_mul(f0, b, f2k);  // f(2k)
        /* F(2k+1) = F(k)^2 + F(k+1)^2 */
        bigN_mul(f0, f0, a);   // a = f(k)^2
        bigN_mul(f1, f1, b);   // b = f(k+1)^2
        bigN_add(a, b, f2k1);  // f(2k+1)
        if (mask & n) {
            bigN_copy(f2k1, f0);
            bigN_add(f2k, f2k1, f1);
        } else {
            bigN_copy(f2k, f0);
            bigN_copy(f2k1, f1);
        }
    }
    bigN_free(f1);
    bigN_free(a);
    bigN_free(b);
    bigN_free(f2k);
    bigN_free(f2k1);
    return f0;
}

重新測量可以看到運行時間大幅減少，Iterative方法時間複雜度為O(n)，Fast Doubling方法時間複雜度為O(logn)。

這邊已經大幅降低計算Fibonacci數列的時間，接下來在Fast Doubling方法下繼續做最佳化。

考慮到硬體加速的手法

許多現代處理器提供 clz / ctz 一類的指令，可搭配上述 Fast Doubling 手法運用:



    //unsigned int h = 0;
    //for (unsigned int i = n; i; ++h, i >>= 1);
    unsigned int h=32-__builtin_clz(n);

這樣可以更求出leading 1 bit在右邊數來第幾個bit。

因為這個運算在整個大數版本的Fast Doubling演算法中佔比很小，所以得到的加速很小。

使用左移運算取代加法

Fast Doubling運算中需要求出2f1的運算可以使用左移運算取代。


//bigN_add_op(f1, f1, a);
bigN_ls(f1,a);

















































void bigN_ls(bigN* a, bigN* b)
{
    uint32_t mask =1<<31;
    int size = a->size;
    int overflow = 0;
    overflow = ((a->d[size - 1]) & mask) != 0 ;
    if(b->size < size ){
        if (overflow){
            size++;
        }
        b->size = size;
        uint32_t *result = kmalloc(size * sizeof(uint32_t), GFP_KERNEL);
        uint64_t l = 0;
        for (int i = 0; i < size; i++) {
            uint32_t A = (a->size) > i ? a->d[i] : 0;
            l =  ((uint64_t)A << 1) + l;
            result[i] = l & 0xFFFFFFFF;
            l >>= 32; 
        }
        kfree(b->d);
        b->d = result;
    }
    else if((b->size == size) && overflow){
        if (overflow){
            size++;
        }
        b->size = size;
        uint32_t *result = kmalloc(size * sizeof(uint32_t), GFP_KERNEL);
        uint64_t l = 0;
        for (int i = 0; i < size; i++) {
            uint32_t A = (a->size) > i ? a->d[i] : 0;
            l =  ((uint64_t)A << 1) + l;
            result[i] = l & 0xFFFFFFFF;
            l >>= 32; 
        }
        kfree(b->d);
        b->d = result;
    }
    else
    {
        uint64_t l = 0;
        for (int i = 0; i < b->size; i++) {
            uint32_t A = (a->size) > i ? a->d[i] : 0;
            l =  ((uint64_t)A << 1) + l;
            b->d[i] = l & 0xFFFFFFFF;
            l >>= 32; 
        }
    }
}

紫色的線段使用上了左移運算以及硬體支援的clz運算，得到了更進一步的加速。

引入memory pool

原本的運算上都直接分配一個新的記憶體空間，將舊的記憶體空間釋放，頻繁的這樣操作導致效能下降。例如：




unsigned int *result = kmalloc(newsize * sizeof(unsigned int), GFP_KERNEL);
memset(result, 0, sizeof(*result));
kfree(c->d);
c->d = result;

所以我重新寫過所有的運算，如果非必要(例如值會溢位)，否則都寫入原本分配的記憶體空間。
並且使用新的資料結構加入memory pool的概念





typedef struct bigN_op {
    unsigned int *d;
    int capacity;
    int size;  // lenths of array d
} bigN_op;

一開始就分配比較大的陣列給資料，減少值會溢位的情況。capacity紀錄總共可以使用的陣列，size紀錄目前的資料需要幾個unsigned int來儲存。

在計算比較小的(200)Fibonacci數列計算效率可以有 50% 的提昇。

在計算比較大的(1000)Fibonacci數列計算效率也有 20% 的提昇。
(因為Fast Doubling方法時間複雜度為O(logn)，數列越大提昇越有限)。
在Iterative方法中也是50%的提昇。