fibdrv Note

follow 2023 年 Linux 核心設計/實作課程作業 —— fibdrv

參考資料繁多，僅用以紀錄自己瀏覽狀況

預期目標+費氏數列
- 費氏數列相關研讀
  - 介紹短片、fast doubling、Fibonacci Q-martix
  - PRNG
- 你所不知道的C語言：遞迴呼叫篇
- LFG
- Linux 核心的 hash table 實作
Linux 核心模組
- Part 1: Introduction
- Part 2: A Character Device

作業要求

在 GitHub 上 fork fibdrv，目標是修正 Fibonacci 數計算並改善 fibdrv 核心模組的計算效率，過程中需要量化執行時間，可在 Linux 核心模組和使用者空間 (userspace) 中測量
- 原本的程式碼只能列出到
  $F i b o n a c c i (100)$ 而且部分輸出是錯誤的數值，請修改程式碼，列出後方更多數值 (注意: 檢查正確性和數值系統的使用)
- 務必研讀上述 Linux 效能分析的提示的描述，降低效能分析過程中的干擾;
- 在 Linux 核心模組中，可用 ktime 系列的 API;
- 在 userspace 可用 clock_gettime 相關 API;
- 善用統計模型，除去極端數值，過程中應詳述你的手法
- 分別用 gnuplot 製圖，分析 Fibonacci 數列在核心計算和傳遞到 userspace 的時間開銷，單位需要用 us 或 ns (自行斟酌)
- 嘗試解讀上述實驗的時間分佈，特別是隨著 Fibonacci 數列增長後，對於 Linux 核心的影響。可修改 VFS 函式，允許透過寫入 /dev/fibonacci 裝置檔案來變更不同的 Fibonacci 求值的實作程式碼。

用 printk 固然方便，但其執行時間易受各種因素而不穩定，除了透過統計來觀察，也可改用核心的 sysfs 介面，後者可讓我們自行宣告 show 和 store 介面來提供讀寫操作，可參見 Sample kobject implementation (注意: 切換到對應的 Linux 核心版本)。
逐步縮減 Fibonacci 的執行時間，過程中要充分量化
嘗試研讀 sysprog21/bignum 的實作，理解其中的技巧並與你的實作進行效能比較，探討個中值得取鏡之處。
當
$F i b (n)$ 隨著
$n$ 越來越大時，由 Linux 核心傳遞字串形式的十進位就成為效能瓶頸
- 儘量降低由核心傳遞到應用程式的資料量
- 確保應用程式不需要過多的計算量才可重現 Fibonacci 數列
- BONUS: 研讀〈Integer Encoding Algorithm 筆記〉所提及的策略，在 Linux 核心模組先對數值進行編碼和壓縮，再由應用程式予以顯示
  $F i b (n)$ 數值

前期準備

步驟皆 follow 文件

首先檢查 kernel 版本

uname -r

5.19.0-35-generic

uname -a     // full information

Linux aaron-System-Product-Name 5.19.0-35-generic #36~22.04.1-Ubuntu SMP PREEMPT_DYNAMIC Fri Feb 17 15:17:25 UTC 2 x86_64 x86_64 x86_64 GNU/Linux

確認 linux-headers 套件已經正確安裝於開發環境

dpkg -L linux-headers-5.19.0-35-generic | grep "/lib/modules"

預期輸出

/lib/modules
/lib/modules/5.19.0-35-generic
/lib/modules/5.19.0-35-generic/build

檢查目前使用者身份，避免使用 root

whoami

安裝工具

sudo apt install util-linux strace gnuplot-nox

strace(1): 可以追蹤系統呼叫
util-linux (utility linux)

dpkg -l | grep util-linux

dpkg -l 列出以安裝的包

ii  util-linux                                 2.37.2-4ubuntu3                         amd64        miscellaneous system utilities

linux 的系統工具

clone fibdrv 並嘗試編譯測試

make check

 Passed [-]
f(93) fail
input: 7540113804746346429
expected: 12200160415121876738

在 f(93) 的時候 fail 了

編譯時會產生 .ko 檔案，此為 kernel object 檔案，可以使用 modinfo(8) 查看 kernel module 的資訊

modinfo fibdrv.ko

預期輸出

filename:       /home/aaron/linux2023/fibdrv/fibdrv.ko
version:        0.1
description:    Fibonacci engine driver
author:         National Cheng Kung University, Taiwan
license:        Dual MIT/GPL
srcversion:     9A01E3671A116ADA9F2BB0A
depends:        
retpoline:      Y
name:           fibdrv
vermagic:       5.19.0-35-generic SMP preempt mod_unload modversions

延伸閱讀 EXPORT_SYMBOL用法

掛載進去

sudo insmod fibdrv.ko

用 dmesg(1) 可以看到相關資訊

$ sudo dmesg
[ 3585.255612] fibdrv: loading out-of-tree module taints kernel.
[ 3585.255647] fibdrv: module verification failed: signature and/or required key missing - tainting kernel

$ lsmod | grep fib
/* Module              Size   Used by*/
fibdrv                 16384  0

size: 16384
use: 0

$ ls -l /dev/fibonacci
crw------- 1 root root 509, 0  三  11 17:57 /dev/fibonacci

1 是硬連結數
root 為擁有者 (user) 和所屬群組 (group)
509 是文件大小
延伸閱讀 Character device drivers

chatGPT 給的解釋

在 ls -l 命令的輸出中，如果一個文件的大小為 0，那麼第五欄的數字就會是 0。如果文件的大小不為 0，那麼第五欄的數字就代表該文件的大小，表示該文件佔用了多少字節的磁盤空間。

而在 ls -l 命令的輸出中，第一欄的第一個數字是用來表示該文件的類型的，例如普通文件、目錄、符號鏈接、設備文件等。在 Linux 系統中，設備文件是一種特殊的文件，用來表示硬體設備。設備文件的第一個數字通常是 0，表示這是一個設備文件。

因此，如果一個文件的第一個數字是 4，這表示這是一個目錄文件。如果一個文件的第一個數字是 0，這表示這是一個設備文件，其大小可能為 0，也可能不為 0，具體取決於該設備的容量。因此，同時出現 4 和 0 的情況，代表這是一個目錄文件，並且其中一些條目是設備文件。

$ cat /sys/module/fibdrv/refcnt
0

代表 reference counting

在重新 make check 之前要 sudo rmmod fibdrv

什麼是費氏數列

費氏數列分析

舉例來說

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 \dots \dots

下一個數字為前兩個數字相加

Recursive 實作 (Python)

def normal_recursion(n):
    if n < 2:
        return n
    return normal_recursion(n - 1) + normal_recursion(n - 2)

就是執行的效率很差

做了非常多重複的運算

Fast doubling 計算方法

根據 Fast doubling

可得:

\begin{aligned} F & (2 k) = F (k) [2 F (k + 1) - F (k)] \\ F & (2 k + 1) = F (k + 1)^{2} + F (k)^{2} \end{aligned}

且遞迴過程縮減，如下

此時再次利用

F (3)

和遞迴

F (3)

時所得到的

F (2)

來計算

F (4)

，可以再次降低運算的次數

硬體加速
$F (n)$ 的手法

透過 clz/ctz 搭配 fast doubling

省略
$F (0)$ ，直接從
$F (1)$ 開始
clz/ffs
- a = 0b1000, ffs(a)=4
- a = 0b1010, ffs(a)=2
- a = 0b1011, ffs(a)=1

遇到 0 -> fast doubling，求
$F (2 n)$ 和
$F (2 n + 1)$
遇到 1 -> fast doubling，求
$F (2 n)$ 和
$F (2 n + 1)$ ，相加後求
$F (2 n + 2)$

求解

$F (11)$ (11₁₀ = 1011₂)

	1	0	1	1	result
F(n)	F(0*2+1)	F(1*2)	F(2*2+1)	F(5*2+1)	F(11)
a	1	1	5	89	89
b	1	2	8	144

左邊第一欄，遇到 1，計算
$F (2 n) = F (2 * 0) = 0$ 以及
$F (2 n + 1) = F (1) = 1 = a$ 、相加後求得
$b = F (2 * 0 + 2) = F (2) = 1$
左邊第二欄，遇到 0，計算
$F (2 n) = F (2 * 1) = 1 = a$ 以及
$F (2 n + 1) = F (3) = 2 = b$
左邊第三欄，遇到 1，計算
$F (2 n) = F (4) = 3$ 以及
$F (2 n + 1) = 5 = a$ 、相加後求得
$F (2 n + 2) = 8 = b$
左邊第四欄，遇到 1，計算
$F (2 n) = F (10) = F (5) [2 F (5 + 1) - F (5)] = 5 [2 * 8 - 5] = 55$ ，計算
$F (2 n + 1) = F (11) = F (6)^{2} + F (5)^{2} = 64 + 25 = 89 = a$ ，相加得
$F (2 n + 2) = F (12) = 55 + 89 = 144$

Fibonacci 數的應用

Pseudorandom number generator

加速 Fibonacci 運算

範例: 計算

F (6)

根據 fast doubling 計算，但是還是有重複計算的部份，當 target 數值越大，重複的計算效能衝擊越顯著。

Bottom-up Fast Doubling

Top-down vs Bottom-up approach in Dynamic Programming

以 87₁₀ 為例:

                87 =  1010111            (87 >> i+1)
        i = 0 : 43 = (1010111 - 1) >> 1 = 101011
        i = 1 : 21 = ( 101011 - 1) >> 1 = 10101
        i = 2 : 10 = (  10101 - 1) >> 1 = 1010 
        i = 3 :  5 = (   1010 - 0) >> 1 = 101 
        i = 4 :  2 = (    101 - 1) >> 1 = 10 
        i = 5 :  1 = (     10 - 0) >> 1 = 1
        i = 6 :  0 = (      1 - 1) >> 1 = 0
                      	     ^
                         87 的第 i 個位元

移項並反過來看

                   (87 >> i+1)
        i = 6 :  1 =        0 << 1 + 1 = 1
        i = 5 :  2 =        1 << 1 + 0 = 10
        i = 4 :  5 =       10 << 1 + 1 = 101
        i = 3 : 10 =      101 << 1 + 0 = 1010
        i = 2 : 21 =     1010 << 1 + 1 = 10101
        i = 1 : 43 =    10101 << 1 + 1 = 101011
        i = 0 : 87 =   101011 << 1 + 1 = 1010111
                                     ^
                              87 的第 i 個位元

這邊感謝 Eroiko 的筆記幫助很大。

$F (92)$ 以後的數值錯誤原因

測試結果如同作業說明及二補數計算，在返回值為 long long 的情況下

F (93)

會造成 overflow

F(93) = -6246583658587674878

二補數計算

\begin{aligned} i f (A + B) & > & T_{M a x} (o v e r f l o w) \\ r e s u l t & = & A + B - 2^{64} \\ = & F (91) + F (92) - 2^{64} \\ = & - 6246583658587674878 \end{aligned}

初步支援大數運算

引入 bn 結構體，計算 92 項以後的費氏數列

/* number[size - 1] = msb, number[0] = lsb */
typedef struct _bn {
    unsigned int *number;
    unsigned int size;
    int sign;
} bn;

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

由於大數沒辦法直接以數值的形式列出，故改用字串來做呈現，轉換部份利用 ASCII 特性並搭配 fast doubling 的邏輯來組合出 10 進位

Trace 其運作流程

static ssize_t fib_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
    bn *fib = bn_alloc(1);
    bn_fib_fdoubling(fib, *offset);
    // bn_fib(fib, *offset);
    char *p = bn_to_string(fib);
    size_t len = strlen(p) + 1;
    size_t left = copy_to_user(buf, p, len);
    // printk(KERN_DEBUG "fib(%d): %s\n", (int) *offset, p);
    bn_free(fib);
    kfree(p);
    return left;  // return number of bytes that could not be copied
}

首先宣告一指標 fib 指向 bn 結構體，並分配空間

bn_alloc

/*
 * alloc a bn structure with the given size
 * the value is initialized to +0
 */
bn *bn_alloc(size_t size)
{
    bn *new = (bn *) kmalloc(sizeof(bn), GFP_KERNEL);
    new->number = kmalloc(sizeof(int) * size, GFP_KERNEL);
    memset(new->number, 0, sizeof(int) * size);
    new->size = size;
    new->sign = 0;
    return new;
}

bn_alloc 會使用 kmalloc 分配 bn 大小的空間，kmalloc 和 vmalloc 都用以分配核心的記憶體空間，但 kmalloc 會分配連續的虛擬以及實體地址，但 vmalloc 只保證連續的虛擬地址，不保證連續的實體地址， kernel 中常用 kmalloc 因為使用 vamlloc 需要進行映射 (mapping) 會讓效能變差
參考 Memory Management APIs (useful GFP flag combinations):
- GFP_KERNEL is typical for kernel-internal allocations. The caller requires ZONE_NORMAL or a lower zone for direct access but can direct reclaim.
- 其中 Linux 會將 kernel 地址分成三部份 (ZONE_DMA、ZONE_NORMAL 和 ZONE_HIGHMEM)
之後便將其結構體中的元素做初始化

接下來將分配好空間的 bn 結構體 fib 以及要計算的

n^{t h}

費式數透過 bn_fib_fdoubling 計算

bn_fib_fdoubling

/*
 * 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);
}

這裡的實作方法和 iterattion 版本的 fast doubling 一樣，只是在四則運算都分別利用其他函式處理，以 bn_add 為例

bn_add (c = a + b)

/*
 * c = a + b
 * Note: work for c == a or c == b
 */
void bn_add(const bn *a, const bn *b, bn *c)
{
    if (a->sign == b->sign) {  // both positive or negative
        bn_do_add(a, b, c);
        c->sign = a->sign;
    } else {          // different sign
        if (a->sign)  // let a > 0, b < 0
            SWAP(a, b);
        int cmp = bn_cmp(a, b);
        if (cmp > 0) {
            /* |a| > |b| and b < 0, hence c = a - |b| */
            bn_do_sub(a, b, c);
            c->sign = 0;
        } else if (cmp < 0) {
            /* |a| < |b| and b < 0, hence c = -(|b| - |a|) */
            bn_do_sub(b, a, c);
            c->sign = 1;
        } else {
            /* |a| == |b| */
            bn_resize(c, 1);
            c->number[0] = 0;
            c->sign = 0;
        }
    }
}

首先透過結構體中定義的 sign 判斷 a, b 正負號是否相等，如果相等相加過後輸出的正負號會相同，交由 bn_do_add 負責運算，且設定 c 符號相同
如果 a, b 符號不同，則透過比較正負號使 a 大於 b，再來判斷絕對值數值的大小，這會影響相加後結果的正負，例如
- 如果 a = -100, b = 10，做 swap 使得 a = 10, b = -100，透過比較絕對值後進行運算得到結果為負的 |b| - |a|
- 如果 a = 100, b = -10，不會做 swap 且運算的結果為正的 |a| - |b|
- 如果 a, b 不同號，且 |a| = |b| ，則輸出為 0

實作判斷可以如下表格所示 (a, b 不同號，且 a > b)

Condition	$\| a \| > \| b \|$	$\| a \| < \| b \|$
Output `c`	$c = + (\| a \| - \| b \|)$	$c = - (\| b \| - \| a \|)$

bn_do_add

/* |c| = |a| + |b| */
static void bn_do_add(const bn *a, const bn *b, bn *c)
{
    // max digits = max(sizeof(a) + sizeof(b)) + 1
    int d = MAX(bn_msb(a), bn_msb(b)) + 1;
    d = DIV_ROUNDUP(d, 32) + !d;
    bn_resize(c, d);  // round up, min size = 1

    unsigned long long int carry = 0;
    for (int i = 0; i < c->size; i++) {
        unsigned int tmp1 = (i < a->size) ? a->number[i] : 0;
        unsigned int tmp2 = (i < b->size) ? b->number[i] : 0;
        carry += (unsigned long long int) tmp1 + tmp2;
        c->number[i] = carry;
        carry >>= 32;
    }

    if (!c->number[c->size - 1] && c->size > 1)
        bn_resize(c, c->size - 1);
}

其中 bn_msb 會回傳傳入的 bn 結構體中所有 array 儲存的資料的 leading zero 有幾個，取較多的那個 + 1 就會是相加後最多有幾個 digits (進位)
bn_resize 會將最終結果 c resize 成 d 的大小，代表著需要幾個 unsigned int *number 去儲存相加後的結果

假設結構體為 uint8_t 為例，若 a = 0b11111111 = 255，b = 0b10000001 = 129 我們想要獲得的答案為 0b 1 10000000 = 384，但只有 8 bit 的話無法表達，所以會輸出會用兩個 uint8_t 數值的陣列表示

bn_do_sub

/*
 * |c| = |a| - |b|
 * Note: |a| > |b| must be true
 */
static void bn_do_sub(const bn *a, const bn *b, bn *c)
{
    // max digits = max(sizeof(a) + sizeof(b))
    int d = MAX(a->size, b->size);
    bn_resize(c, d);

    long long int carry = 0;
    for (int i = 0; i < c->size; i++) {
        unsigned int tmp1 = (i < a->size) ? a->number[i] : 0;
        unsigned int tmp2 = (i < b->size) ? b->number[i] : 0;

        carry = (long long int) tmp1 - tmp2 - carry;
        if (carry < 0) {
            c->number[i] = carry + (1LL << 32);
            carry = 1;
        } else {
            c->number[i] = carry;
            carry = 0;
        }
    }

    d = bn_clz(c) / 32;
    if (d == c->size)
        --d;
    bn_resize(c, c->size - d);
}

同樣的，在 bn_do_sub 中，輸出 c 最大的 digit 數為兩個 digit 數高的那個 (不發生借位)，計算 carry 值，若兩數值相減後 msb 還是 1 的話，代表發生借位，會將 c->number[i] 的值設定為 carry + (1LL << 32) ，這邊的 (1LL << 32) 看起來是要把第 32 bit (含) 以上的都設定為 0 (但實測後不做這件事情可以正確計算)

這裡的判斷是否借位可改寫成

- carry = (long long int) tmp1 - tmp2 - carry;

+ tmp1 - tmp2 - carry < 0 ? carry = 1 : 0;
+ c->number[i] = carry;
- if (carry < 0) {
-     c->number[i] = carry + (1LL << 32);
-     carry = 1;
- } else {
-     c->number[i] = carry;
-     carry = 0;
- }

一樣可以正確計算 Fibonacci number

bn_sub

/*
 * c = a - b
 * Note: work for c == a or c == b
 */
void bn_sub(const bn *a, const bn *b, bn *c)
{
    /* xor the sign bit of b and let bn_add handle it */
    bn tmp = *b;
    tmp.sign ^= 1;  // a - b = a + (-b)
    bn_add(a, &tmp, c);
}

這裡的 bn_sub 可以偷過 bn_add 來實作，因 bn 結構為 unsigned int 的 number 陣列，由另外的 sign 元素決定其正負，若要執行 bn_sub，可以透過反轉 b 的 sign 元素再進行 bn_add 即可

bn_mult

/*
 * c = a x b
 * Note: work for c == a or c == b
 * using the simple quadratic-time algorithm (long multiplication)
 */
void bn_mult(const bn *a, const bn *b, bn *c)
{
    // max digits = sizeof(a) + sizeof(b))
    int d = bn_msb(a) + bn_msb(b);
    d = DIV_ROUNDUP(d, 32) + !d;  // round up, min size = 1
    bn *tmp;
    /* make it work properly when c == a or c == b */
    if (c == a || c == b) {
        tmp = c;  // save c
        c = bn_alloc(d);
    } else {
        tmp = NULL;
        bn_resize(c, d);
    }

    for (int i = 0; i < a->size; i++) {
        for (int j = 0; j < b->size; j++) {
            unsigned long long int carry = 0;
            carry = (unsigned long long int) a->number[i] * b->number[j];
            bn_mult_add(c, i + j, carry);
        }
    }
    c->sign = a->sign ^ b->sign;

    if (tmp) {
        bn_cpy(tmp, c);  // restore c
        bn_free(c);
    }
}

實作一般直式長乘法，用輔助函式 bn_mult_add 負責將每一行的計算結果疊加上去，假設 number 為 4 bit，a=0b0111 0111 (size=2), b=0b0101 0101 (size=2) 計算過程如下

bn_lshift

/* left bit shift on bn (maximun shift 31) */
void bn_lshift(bn *src, size_t shift)
{
    size_t z = bn_clz(src);
    shift %= 32;  // only handle shift within 32 bits atm
    if (!shift)
        return;

    if (shift > z)
        bn_resize(src, src->size + 1);
    /* bit shift */
    for (int i = src->size - 1; i > 0; i--)
        src->number[i] =
            src->number[i] << shift | src->number[i - 1] >> (32 - shift);
    src->number[0] <<= shift;
}

此處實作先僅限於移動 32 bit 以內，函式內用一個 bitwise or | 來處理跨越 number 之間的 bit shift

bn_to_string

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

上述實作中關鍵的程式碼為

/* 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;
}

由高位 (MSB) 開始檢測 binary 中每個 bit
- 若為 1，則輸出乘二加一
- 若為 0，則輸出乘二

計算 F₉₃ (包含) 之後的 Fibonacci 數

參考 AdrianHuang/fibdrv 實作程式碼

bignum

以數字陣列來儲存(同時也可以指定陣列大小)，以 uint8_t 為例，其數值範圍在 0~255，若要表示 300 則以數字陣列 digit 來表示，假設陣列大小為 3，則 300 表示為

\begin{aligned} 300 & : & 00000000 & 00000001 & 00101100 \\ d i g i t & : & d i g i t [2] & d i g i t [1] & d i g i t [0] \\ v a l u e & : & 0 & 1 & 44 \end{aligned}

然後在透過 format.c 格式轉換為十進位

可以透過以下兩種演算法實現大數的乘法

Karatsuba 演算法
Schönhage–Strassen Algorithm

改善大數運算

改善方案 1: 改寫 `bn_fib_fdoubling`

直接引入 Reference 竟然報錯

sudo ./client > out
*** stack smashing detected ***: terminated
Aborted

查看 out 檔案發現計算的值有很大的問題

Reading from /dev/fibonacci at offset 0, returned the sequence 0.
Reading from /dev/fibonacci at offset 1, returned the sequence 1.
Reading from /dev/fibonacci at offset 2, returned the sequence 10.
Reading from /dev/fibonacci at offset 3, returned the sequence 24.
Reading from /dev/fibonacci at offset 4, returned the sequence 392.
Reading from /dev/fibonacci at offset 5, returned the sequence 724.

在尚未優化的版本中， bignum 版本和正常版本的運算可以直接對應

不支援大數的 fast doubling iteration

static long long fib_sequence_fd_iter(long long k)
{
    // Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, ...
    if (k <= 2)
        return !!k;
...
    for (uint64_t i = count, f2k0, f2k1; i-- > 0;) {
        /*  F(2k) = F(k)[2F(k+1) - F(k)]
         *  F(2k+1) = F(k+1)^2 + F(k)^2
         */
        f2k0 = fk0 * ((fk1 << 1) - fk0);
        f2k1 = fk1 * fk1 + fk0 * fk0;

        if (k & (1UL << i)) {
            fk0 = f2k1;
            fk1 = f2k0 + f2k1;
        } else {
            fk0 = f2k0;
            fk1 = f2k1;
        }
    }
    return fk0;
}

支援大數的 fast doubling iteration































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;
    }
...
    /* 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);      // k1 = 2 * F(k+1)
        bn_sub(k1, f1, k1);    // k1 = 2 * F(k+1) - F(k)
        bn_mult(k1, f1, k1);   // k1 = F(k) * (2F(k+1) - F(k))
        /* F(2k+1) = F(k)^2 + F(k+1)^2 */
        bn_mult(f1, f1, f1);   // f1 = F(k)^2
        bn_mult(f2, f2, f2);   // f2 = F(k+1)^2
        bn_cpy(k2, f1);        // k2 = f1 = F(k)^2
        bn_add(k2, f2, k2);    // k2 = F(k+1)^2 + F(k)^2
        if (n & i) {
            bn_cpy(f1, k2);    // f1 = F(k+1)^2 + F(k)^2
            bn_cpy(f2, k1);    // f2 = F(k) * (2F(k+1) - F(k))
            bn_add(f2, k2, f2);
        } else {
            bn_cpy(f1, k1);    // f1 = F(k) * (2F(k+1) - F(k))
            bn_cpy(f2, k2);    // f2 = F(k+1)^2 + F(k)^2
        }
    }
...
}

注意根據函式引數，我們需要的計算結果為 f1 也就是傳入的 dest

void bn_fib_fdoubling_v1(bn *dest, unsigned int n)
{
    ...
    for (unsigned int i = 1U << (31 - __builtin_clz(n)); i; i >>= 1) {
        /* F(2k) = F(k) * [ 2 * F(k+1) – F(k) ] */
        /* F(2k+1) = F(k)^2 + F(k+1)^2 */
        bn_lshift_2(f2, 1, k1);// k1 = 2 * F(k+1)
        bn_sub(k1, f1, k1);  // k1 = 2 * F(k+1) – F(k)
        bn_mult(k1, f1, k2); // k2 = k1 * f1 = F(2k)
        bn_mult(f1, f1, k1); // k1 = F(k)^2
        bn_swap(f1, k2);     // f1 <-> k2, f1 = F(2k) now
        bn_mult(f2, f2, k2); // k2 = F(k+1)^2
        bn_add(k1, k2, f2);  // f2 = f1^2 + f2^2 = F(2k+1) now
        if (n & i) {
            bn_swap(f1, f2);    // f1 = F(2k+1)
            bn_add(f1, f2, f2); // f2 = F(2k+2)
        }
    }
    ...
}

而此改善方案旨在降低使用 malloc 及 memcpy 的次數，首先新的 bn_lshift_2 可以將第一個引數 src 左移第二個引數 shift 後儲存至第三個引數 dest

bn_lshift_2 函式修改

wanghanchi

void bn_lshift_2(const bn *src, size_t shift, bn *dest)
{
    size_t z = bn_clz(src);
    shift %= 32;  // only handle shift within 32 bits atm
    if (!shift)
        return;

    if (shift > z) {
        bn_resize(dest, src->size + 1);
+       dest->number[src->size] = src->number[src->size - 1] >> (32 - shift);
    } else {
        bn_resize(dest, src->size);
    }
    /* bit shift */
    for (int i = src->size - 1; i > 0; i--)
        dest->number[i] =
            src->number[i] << shift | src->number[i - 1] >> (32 - shift);
    dest->number[0] = src->number[0] << shift;
}

結果在測試時還是錯誤

make check FIBMODE=3

檢查過後發現在 bn_mult 中當資料來源與目的沒有重疊時，並沒有將其 number 初始化，以至於產生非預期的取值，之前沒有發現是因為在 bignum 的 fast-doubing 版本中使用 bn_mult 的案例都屬於 (c == a || c == b)

void bn_mult(const bn *a, const bn *b, bn *c)
{
    // max digits = sizeof(a) + sizeof(b))
    int d = bn_msb(a) + bn_msb(b);
    d = DIV_ROUNDUP(d, 32) + !d;  // round up, min size = 1
    bn *tmp;
    /* make it work properly when c == a or c == b */
    if (c == a || c == b) {
        tmp = c;  // save c
        c = bn_alloc(d);
    } else {
        tmp = NULL;
+        for (int i = 0; i < c->size; i++)
+            c->number[i] = 0;
        bn_resize(c, d);
    }

    for (int i = 0; i < a->size; i++) {
        for (int j = 0; j < b->size; j++) {
            unsigned long long int carry = 0;
            carry = (unsigned long long int) a->number[i] * b->number[j];
            bn_mult_add(c, i + j, carry);
        }
    }
    c->sign = a->sign ^ b->sign;

    if (tmp) {
        bn_swap(tmp, c);  // restore c
        bn_free(c);
    }
}

修正完成後此節改善方案可通過測試。

改善方案 2: 運用 Q-Matrix

參考網站所提供的 fast doubling 方法如下

\begin{aligned} [\begin{array}{c} F (2 n + 1) & F (2 n) \\ F (2 n) & F (2 n - 1) \end{array}] & = {[\begin{array}{c} 1 & 1 \\ 1 & 0 \end{array}]}^{2 n} \end{aligned}

左右欄對調

\begin{aligned} [\begin{array}{c} F (2 n) & F (2 n + 1) \\ F (2 n - 1) & F (2 n) \end{array}] & = {[\begin{array}{c} 1 & 1 \\ 0 & 1 \end{array}]}^{2 n} \end{aligned}

可以將第一欄取出為

\begin{aligned} [\begin{array}{c} F (2 n) \\ F (2 n - 1) \end{array}] & = {[\begin{array}{c} 1 & 1 \\ 0 & 1 \end{array}]}^{2 n} [\begin{array}{c} 1 \\ 0 \end{array}] \\ = {[\begin{array}{c} 1 & 1 \\ 0 & 1 \end{array}]}^{2 n} [\begin{array}{c} F (1) \\ F (0) \end{array}] \end{aligned}

列對調

\begin{aligned} [\begin{array}{c} F (2 n - 1) \\ F (2 n) \end{array}] & = {[\begin{array}{c} 0 & 1 \\ 1 & 1 \end{array}]}^{2 n} [\begin{array}{c} 0 \\ 1 \end{array}] \\ = {[\begin{array}{c} 0 & 1 \\ 1 & 1 \end{array}]}^{2 n} [\begin{array}{c} F (0) \\ F (1) \end{array}] \end{aligned}

觀察 sysprog21/bignum 中費氏數列的實作函式 fibonacci，會發現雖看似採用 fast doubling，但實際是 Q-matrix 這樣的變形，推導如下:

\begin{aligned} [\begin{array}{c} F (2 n - 1) \\ F (2 n) \end{array}] & = {[\begin{array}{c} 0 & 1 \\ 1 & 1 \end{array}]}^{2 n} [\begin{array}{c} F (0) \\ F (1) \end{array}] \\ = [\begin{array}{c} F (n - 1) & F (n) \\ F (n) & F (n + 1) \end{array}] [\begin{array}{c} F (n - 1) & F (n) \\ F (n) & F (n + 1) \end{array}] [\begin{array}{c} 1 \\ 0 \end{array}] \\ = [\begin{array}{c} F (n)^{2} + F (n - 1)^{2} \\ F (n) F (n) + 2 F (n) F (n - 1) \end{array}] \end{aligned}

整理後可得

\begin{aligned} F (2 k - 1) & = F (k)^{2} + F (k - 1)^{2} \\ F (2 k) & = F (k) [2 F (k - 1) + F (k)] \end{aligned}

使用上述公式改寫 bn_fib_fdoubling，搭配使用 clz ，後者可讓 n 值越小的時候，減少越多次迴圈運算，從而達成加速。

改善方案 3: 引入 memory pool

原本在實作中在計算前會使用 bn_resize 來確保有足夠的空間儲存計算結果 (number 的數量)，而現在引入 capacity 的方式來管理 bn 的可用大小，減少 bn_resize 呼叫 realloc 的次數。

static int bn_resize(bn *src, size_t size)
{
    if (!src)
        return -1;
    if (size == src->size)
        return 0;
    if (size == 0)  // prevent krealloc(0) = kfree, which will cause problem
        return bn_free(src);
    if (size > src->capacity) { /* need to allocate larger capacity */
        src->capacity = (size + (ALLOC_CHUNK_SIZE - 1)) & ~(ALLOC_CHUNK_SIZE - 1); // ceil to 4*n
        src->number = krealloc(src->number, sizeof(int) * src->capacity, GFP_KERNEL);
    }
    if (!src->number) {  // realloc fails
        return -1;
    }
    if (size > src->size) { /* memset(src, 0, size) */
        for (int i = src->size; i < size; i++)
            src->number[i] = 0;
    }
    src->size = size;
    return 0;
}

只有當 size 超過 capacity 時才會 realloc，並以 4 為單位
計算仍以 size 作為範圍，不必計算多餘的空間
trim 時只要縮小 size 就好，不需要實際 realloc 來縮小空間

Part 1: Introduction 閱讀筆記

This article is focused on the system configuration, tools and code required to build and deploy a “Hello World!” kernel module.

什麼是 Kernel Module?

Loadable kernel module (LKM) 是一個在 Linux kernel run time 下新增、移除程式的機制。這樣使得 kernel 無須知道硬體是如何運作的便可以使 kernel 和硬體進行通訊 (ideal for device drivers!)

LKM 的替代方案就是將每個驅動都直接灌到 Linux Kernel 中

如果沒有這個東西的話， Linux kernel 將會非常的龐大，且要更新 hardware driver 的話每次都要重新建構 kernel。 LKM 的缺點就是每個 device 的 driver 都需要被 maintain

LKMs 是在 runtime 被加載的，但並不是在 user space 運行。

Kernel modules 在 kernel space 運行，Application 在 user space 運行

kernel space 和 user space 都有自己唯一且不重疊的記憶體位置，確保應用程式不管在任何硬體平台上在 user space 都有 consistent view。

為什麼要寫 kernel module?

在嵌入式 Linux 中利用 sysfs 以及低階 (low-level) 檔案操作來與電子電路進行互動，這樣的方法非常沒有效率。但是，這樣的方法在各種應用程式上已經足夠 (原文提供證明)。

而替代方案就是使用支援中斷 (interrupt) 的 kernel module，但 kernel code 是非常編寫和除錯的。

在寫測試 LKMs 時是非常容易 crash system 的，是有可能損壞檔案系統的，若有需要就要備份

The Module Code

一般典型的電腦程式在 runtime life cycle 非常直觀。 loader 分配記憶體給程式，然後載入任何需要的 libraries。指令執行的起始點通常東在 main()，然後接著執行、回報錯誤、例外狀況，分配動態記憶體，然後最終運行完成。在程式離開時，作業系統會將 memroy leaks 以及沒有 free 乾淨的 memory 丟到 pool 中。

但 kernel module 沒有這些東西，且沒有 main() function!

以下是一些主要區別:

不會按照順序執行: kernel module 是用自己的 initialization function 來註冊自己 handle request，該函數可以運行然後中止。它可以 handle 的類型會在 module code 中定義。這和 GUI 中的 event-driven programming model 非常類似。
沒有自動清理 (automatic cleanup): 分配給 module 的任何資源 (resources) 都必須在卸載 (unloaded) module 的時候釋放掉 (released) ，否則在重開機之前這些資源不可用
沒有 printf() 函式: kernel code 無法訪問 (access) user space 的 libraries。kernel module 在 kernel space 生成及執行，有自己的 memory address space， kernel space 和 user space 的界面 (interface) 被明確定義，但確實有一個 printk() 函數可以輸出 information，且可以在 user space 查看
可以被中斷 (interrupt): kernel module 可以同時被多個不同的程式 (programs) 或行程 (process) 使用，須仔細的建構以確保在被中斷時具有一致且有效的行為。就算是單核心的 processor ，也還是要考慮到多行程的問題。
具有更高級別的權限: 一般來說，分配給 kernel module 的 cpu cycle 會比 user space 的 program 來的多，但是就必須要注意 kernel module 不要對整體效能產生不利的影響。
不支援浮點數: kernel code 使用 traps 將系統從整數模式轉換為浮點數模式，但是在 kernel space 下難以執行這些 traps，替代方案是手動保存和恢復浮點數運算，但是最好還是留給 user space code 來處理。
- Reference Linux 核心的浮點數運算

Part 2: A Character Device 閱讀筆記

Character Device Drivers

ChatGPT 給的解釋

Character Device 是指一種在 Unix/Linux 系統中的設備類型，該設備對外提供了一個字符（Character）流的接口，用於與其他軟件或硬件進行通信。一些例子包括終端設備（如 tty）、滑鼠、鍵盤、語音輸入、音訊裝置等。

Character Device 與另一種設備類型 Block Device 不同。Block Device 是指提供塊（Block）訪問方式的設備，例如硬碟驅動器，其將數據劃分為固定大小的塊（通常為512位元組或4KB），用於高效地存儲和讀取數據。

在 Linux 系統中，Character Device 和 Block Device 均被視為一種特殊的檔案，可以使用文件描述符（File Descriptor）對其進行讀寫操作。Character Device 提供了一種簡單的、無緩衝的 I/O 模型，允許使用者以字節為單位進行讀寫操作。相較之下，Block Device 的 I/O 模型則更複雜，需要進行塊緩存、讀寫計劃等操作，以達到更高的性能。

Character decive 一般在 user application 收送資料，就像是 pipes 或 serial ports，立即讀寫 character-by-character stream 中的位元組資料。為典型的驅動軟體提供框架，連接 serial communcations、video capture、audio devices，其主要的替代品是 block device， block device 的行為和常規的文件相似，允許透過讀取、寫入、查找等等操作來查看或操作 buffered array of cached data

這兩種 device types 都可以被 attached 到 file system tree 的 device file 來 access

本文提供了一個運行在 linux kernel space 下，且可以讓 Linux user-space program 和 loadable kernel module (LKM) 之間 pass information 的 character driver，本例中， C user-space application 發送一段 string 給 LKM，然後 LKM 會回傳其收到的字節數。接著解釋為何要解決同步的問題 (本文透過 mutex lock 解決)

Major and Minor Numbers

Device drivers 有一個 major 和 minor 號碼， major number 是 kernel 在當這個 device 被 accessed 時用來識別正確的 device driver，而 minor number 取決於 device，並在驅動程式內部處理

:/dev$ ls -l |grep i2c
crw-------   1 root  root     89,     0  三  17 19:19 i2c-0

如果是 character deviceds ，首欄字母為 c，如果是 block device，首欄字母為 b，接下來就是常見的 access permission, owner, grops.

可以手動建立 block 或 character device，例如 sudo mknod /dev/test c 92 1，但是這個方法必須確認 92 這個數字沒有被使用

The File Operation Data Structure

file_operations 的 data structure 定義於 /linux/fs.h，內部結構包含 function pointer 並允許設計人員定義以下操作。

struct file_operations {
   struct module *owner;                             // Pointer to the LKM that owns the structure
   loff_t (*llseek) (struct file *, loff_t, int);    // Change current read/write position in a file
   ssize_t (*read) (struct file *, char __user *, size_t, loff_t *);    // Used to retrieve data from the device
   ssize_t (*write) (struct file *, const char __user *, size_t, loff_t *);   // Used to send data to the device
   ssize_t (*aio_read) (struct kiocb *, const struct iovec *, unsigned long, loff_t);  // Asynchronous read
   ssize_t (*aio_write) (struct kiocb *, const struct iovec *, unsigned long, loff_t); // Asynchronous write
   ssize_t (*read_iter) (struct kiocb *, struct iov_iter *);            // possibly asynchronous read
   ssize_t (*write_iter) (struct kiocb *, struct iov_iter *);           // possibly asynchronous write
   int (*iterate) (struct file *, struct dir_context *);                // called when VFS needs to read the directory contents
   unsigned int (*poll) (struct file *, struct poll_table_struct *);    // Does a read or write block?
   long (*unlocked_ioctl) (struct file *, unsigned int, unsigned long); // Called by the ioctl system call
   long (*compat_ioctl) (struct file *, unsigned int, unsigned long);   // Called by the ioctl system call
   int (*mmap) (struct file *, struct vm_area_struct *);                // Called by mmap system call
   int (*mremap)(struct file *, struct vm_area_struct *);               // Called by memory remap system call 
   int (*open) (struct inode *, struct file *);             // first operation performed on a device file
   int (*flush) (struct file *, fl_owner_t id);             // called when a process closes its copy of the descriptor
   int (*release) (struct inode *, struct file *);          // called when a file structure is being released
   int (*fsync) (struct file *, loff_t, loff_t, int datasync);  // notify device of change in its FASYNC flag
   int (*aio_fsync) (struct kiocb *, int datasync);         // synchronous notify device of change in its FASYNC flag
   int (*fasync) (int, struct file *, int);                 // asynchronous notify device of change in its FASYNC flag
   int (*lock) (struct file *, int, struct file_lock *);    // used to implement file locking
   …
} __randomize_layout;

結尾的 __randomize_layout 標示可參考 Linux Kernel之randomized layout，其目的在於增強 kernel 的安全性

這個 driver 提供了 read, write, open, release 等 system call file operation，如果沒有實作的話，那麼這些 function pointer 會指向 NULL

The Device Driver Source Code

本節原文以 BeagleBone 做為舉例，但其架構可從 fibdrv 找到相對應的 init()、 exit()，以及 file_operations 等等實作，其中

dev_open(): Called each time the device is opened from user space.
dev_read(): Called when data is sent from the device to user space.
dev_write(): Called when data is sent from user space to the device.
dev_release(): Called when the device is closed in user space.
llseak(): Change current read/write position in a file
- 在 userr-level 的 entry point 為lseek(int __fd, off_t __offset, int __whence) ，控制檔案的讀寫位置，引數 __offset 根據引數 __whence 來移動讀寫位置的位移數， __whence 可以是以下其中一種:
  - SEEK_SET: 引數 __offset 即為新的讀寫位置
  - SEEK_CUR: 以目前的讀寫位置往後增加 __offset 個位移量
  - SEEK_END: 將讀寫位置指向檔案未端後在增加 __offset 個位移量
- 在 fibdrv.c 中的 fib_device_lseek 有對應的實作

在 user space 呼叫 read() 函式時，是無法直接指定文件 offset 的，文件的偏移量是和 file descriptor 的屬性，只能透過呼叫 lseek() 函式或其他類似的 system call 來修改，故若要指定文件偏移量，需在讀取文件之前使用 lseek() 設定偏移量，然後在呼叫 read() 函式進行讀取，例如 client.c 中的作法

for (int i = 0; i <= offset; i++) {
    lseek(fd, i, SEEK_SET);
    // cppcheck-suppress unreadVariable
    sz = read(fd, buf, 1);
    printf("Reading from " FIB_DEV
           " at offset %d, returned the sequence "
           "%s.\n",
           i, buf);
}

在原文的留言處有提到

devnull: You should add “.owner = THIS_MODULE,” in struct file_operations fops or you will get nasty kernel oopses when unloading or rebooting. Took me 2 weeks to find out.

在 fibdrv 中有做

fibdrv 核心模組內部

可以發現有些東西是在 user-level 運作的

查看 client.c

#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <unistd.h>

#define FIB_DEV "/dev/fibonacci"

int main()
{
    long long sz;

    char buf[1];
    char write_buf[] = "testing writing";
    int offset = 100; /* TODO: try test something bigger than the limit */

    int fd = open(FIB_DEV, O_RDWR);
    if (fd < 0) {
        perror("Failed to open character device");
        exit(1);
    }

    for (int i = 0; i <= offset; i++) {
        sz = write(fd, write_buf, strlen(write_buf));
        printf("Writing to " FIB_DEV ", returned the sequence %lld\n", sz);
    }

    for (int i = 0; i <= offset; i++) {
        lseek(fd, i, SEEK_SET);
        sz = read(fd, buf, 1);
        printf("Reading from " FIB_DEV
               " at offset %d, returned the sequence "
               "%lld.\n",
               i, sz);
    }

    for (int i = offset; i >= 0; i--) {
        lseek(fd, i, SEEK_SET);
        sz = read(fd, buf, 1);
        printf("Reading from " FIB_DEV
               " at offset %d, returned the sequence "
               "%lld.\n",
               i, sz);
    }

    close(fd);
    return 0;
}

上述這段 code 會用系統呼叫 open 打開 device file /dev/fibonacci，其中也使用了 open、write、lseek、read 等系統呼叫來對 fibonacci 進行操作，操作之後就可以從 kernel 讀取出之前運算出來的 fibonacci 數值，然後就可以在 user space 中進行輸出

client.c

fd = open(FIB_DEV, O_RDWR);

if (fd < 0) {
    perror("Failed to open character device");
    exit(1);
}

for (i = 0; i <= offset; i++) {
    sz = write(fd, write_buf, strlen(write_buf));
    printf("Writing to " FIB_DEV ", returned the sequence %lld\n", sz);
}

for (i = 0; i <= offset; i++) {
    lseek(fd, i, SEEK_SET);
    sz = read(fd, buf, 1);
    printf("Reading from " FIB_DEV
           " at offset %d, returned the sequence "
           "%lld.\n",
           i, sz);
}

此處透過 read 系統呼叫來得到輸出

查看 fibdrv.c (參考物件導向程式設計篇 (designated initializers)、file_operations Struct Reference)

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

const struct file_operations fib_fops = {
    .owner = THIS_MODULE,
    .read = fib_read,
    .write = fib_write,
    .open = fib_open,
    .release = fib_release,
    .llseek = fib_device_lseek,
};

上述 fib_read 宣告為 static (表示其能見度只有在該檔案)，但在 fib_fops 被初始化成 read function pointer，所以之後只要操作該 function pointer，就會像是在操作 fib_read，且可以避免命名衝突

這裡實作了 fib_read 函數內將 fib_sequence 的值回傳，透過使用者給定不同的 offset 作為 Fibonacci 數列的

x

回傳

f i b (x)

Linux Virtual File System (VFS)

在傳統 UNIX 系統中，檔案系統是固定的，但是在 Linux 中，為了結合各個檔案系統，因而加上了一層虛擬檔案系統 (VFS)， VFS 是一組檔案操作的抽象界面，可以將任何真實的檔案系統透過 VFS 掛載到 Linux 中。

VFS 並不直接處理檔案格式，而是規定這些處理請求的介面及操作語意，然後交由真實的檔案系統 (像是 EXT2) 去處理。

而透過 VFS， fibdrv 核心模組可以將計算出來 Fibonacci 數讓 client.c 程式得以存取

Linux 的裝置驅動程式大致分為:

Character Device Driver
Block Device Driver
Network Device Driver

參照 Linux 核心設計: 檔案系統概念及實作手法

Makefile

在 Makefile 中，make check 會去加載編譯好的 fibdrv kernel module，並將 client 輸出儲存至 out，透過以下指令

diff -u out scripts/expected.txt && $(call pass)

來檢驗輸出和預期是否一樣，在第一版本的 fibdrv 中僅能輸出正確的

F i b (92)

Reading from /dev/fibonacci at offset 92, returned the sequence 7540113804746346429.
Reading from /dev/fibonacci at offset 93, returned the sequence 7540113804746346429.
Reading from /dev/fibonacci at offset 94, returned the sequence 7540113804746346429.

在和目標檔案 expected.txt 比對時會給 pass ，因為 expected.txt 本來就給定這樣的預期輸出，若要檢測後續的 Fibonacci number 是否正確則連同 expected.txt 也要一起改

`copy_[to/from]_user`

user-space 無法直接存取 kernel-space 的記憶體
Linux device driver 與 user-space 間的 I/O 會與 fops->read、fops->write、fops->ioctl 這三個 system call 有關

不論是從 user-space 讀取資料至 kernel-space，或是將 kernel-space 的資料寫至 user-space, 必須透過 kernel 提供的兩個 API 來進行

long copy_tp_user(void *to, const void * from, long n)
long copy_from_user(void *to, const void* from, long n)

copy_to_user

to: 資料的目的位置 (指向 user-space 記憶體的指標)
from: 資料的來源位址 (指向 kernel-space 記憶體的指標)

copy_from_user

to: 資料的目的位置 (指向 kernel-spcae 記憶體的指標)
from: 資料的來源位置 (指向 user-space 記憶體的指標)

Kernel 裡面有 copy_to_user，可以把資料從 kernel space copy 到 user space

注意到 copy_to_user 其實是有成本的

核心模式的時間測量

參照核心模式的時間測量、Linux 核心設計: Timer 及其管理機制

如果只在 user space 做測量，那就只能測量進出 kernel 內部的時間，測量不到 kernel 內部，進出 kernel 其實有其他的成本開銷 (例如 mode switch)

這時候就需要用到 hrtimer (high-resolution timer)，在 linux 上的通常可以達到 1 micro second 的精準度

jiffies 是一種計時機制，計算自開機以來計時器中斷發生的次數，較舊的 Linux 核心有提到 timer wheel，而一個新的機制是將計時機制建立在新資料結構 ktime_t 上

參照 The high-resolution timer API、ktime 相關 API

關於 `client.c`

根據作業說明描述，在 user-mode 的位置配置一個 buffer 空間時， kernel driver 不能直接寫入該地址，而是要透過 copy-to-user，將想傳給 user-mode (運作中的 client) 的字串複製到 fib_read 的 buf 參數後， client 方可接收此字串

而 Hierarchical performance measurement and modeling of the Linux file system 研究指出，從 kernel-level 複製資料到 user-level 的時間成本是每位元組 22ns，故在進行效能分析時，必須要考慮到 copy_to_user 函式的時間開銷，特別留意資料大小成長後造成的量測誤差

Linux 效能分析的提示

傳統多核心的系統使用 SMP 進行設計，各個 CPU 共享相同的記憶體，每個 CPU 都可以訪問記憶體中的任何地址，所需要的時間都是相同的
由於 SMP 在擴展上的限制，非統一記憶體存取架構 (NUMA)因而誕生，可以把更多數量的 CPU 組合起來， CPU 可以同時訪問不同的記憶體，大幅提高並行性， NUMA 模式下，處理器被劃分為多個節點，每個節點有自己的 local memory，同樣的每個 CPU 都可以訪問所有的記憶體位址，但離自己越遠則需要花費比較多的時間。

參考Linux 效能分析的提示、KYG-yaya573142，使用 processor affinity / CPU pinning 讓行程在特定的 CPU 中執行不受排程的干擾

$ cat /proc/cpuinfo | grep "^processor" | wc -l
8

也可以使用 perf record 來取樣並紀錄目標的執行狀態

sudo perf record -g --call-graph dwarf ./measure

-g 回同時紀錄取樣點的 stack trace
--call-graph 指定走訪 stack trace 的方法 follow The DWARF Debugging Standard
記得要先 make load 載入 module

限定 CPU 給特定的程式使用

修改 /etc/default/grub 內的 GRUP_CMDLINE_LINUX_DEFAULT ，加入 isolcpus=7 來指定編號 7 的核心 不被排程器賦予任務，修改完成後 sudo update-grub 來更新設定

quiet: 啟動系統的過程中，如果沒有 quiet， kernel 就會輸出很多訊息，包括啟動過程中運行了哪些程式，如果系統可以正常啟動，通常就不會需要這些訊息，故會設定成 quiet
splash: 與可視化界面有關
GRUB_CMDLINE_LINUX: 一直生效
GRUB_CMDLINE_LINUX_DEFAULT: 恢復模式 (recovery mode) 下不會運作

排除干擾效能的因素

抑制 address space layout randomization (ASLR)

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

設定 scaling_governor 為 performance。

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

以我的電腦來說，會將 performance 分別寫入

/sys/devices/system/cpu/cpu0/cpufreq/scaling_governor
/sys/devices/system/cpu/cpu1/cpufreq/scaling_governor
/sys/devices/system/cpu/cpu2/cpufreq/scaling_governor
/sys/devices/system/cpu/cpu3/cpufreq/scaling_governor
/sys/devices/system/cpu/cpu4/cpufreq/scaling_governor
/sys/devices/system/cpu/cpu5/cpufreq/scaling_governor
/sys/devices/system/cpu/cpu6/cpufreq/scaling_governor
/sys/devices/system/cpu/cpu7/cpufreq/scaling_governor

參考 CPU frequency scaling，會讓 CPU 在最高頻率下運轉

針對 Intel 處理器，關閉 turbo mode

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

關閉 SMT (Hyper-threading)

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

gnuplot

set title "Performance with setting affinity"
set xlabel "n^{th} fibonacci number"
set ylabel "Time(ns)"
set terminal png font "Times_New_Roman, 12"
set output "tt.png"
set key left

FILES = system("ls -1 *.txt")

plot for [data in FILES]\
data using 3 with linespoints linewidth 2 title data\

觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題

並行和多執行緒設計

POSIX Threads

POSIX Threads 是一套符合 POSIX 標準的 API，方便開發者設計出 User-level 的多執行緒程式。

在 linux/unistd.h 中提供了 POSIX 作業系統 API 的存取功能標頭檔名稱。通常為大量的 system call。

在可移植性方面，符合 POSIX 標準的 API 其函數名稱、返回值、參數類型等等都按照標準定義，而 POSIX 相容也就指定這些接口 (interface) 函式相容，但是並不管 API 具體如何實現

利用 strace 簡單測試一個 printf 到底呼叫了哪些 system call

int main()
{
    printf("Hello!\n");
    return 0;
}








































execve("./strace", ["./strace"], 0x7ffe4f88a900 /* 54 vars */) = 0
brk(NULL)                               = 0x55b334ae3000
arch_prctl(0x3001 /* ARCH_??? */, 0x7fff9841a5c0) = -1 EINVAL (Invalid argument)
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fc18d976000
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=70567, ...}, AT_EMPTY_PATH) = 0
mmap(NULL, 70567, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7fc18d964000
close(3)                                = 0
openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libc.so.6", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1\1\3\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0P\237\2\0\0\0\0\0"..., 832) = 832
pread64(3, "\6\0\0\0\4\0\0\0@\0\0\0\0\0\0\0@\0\0\0\0\0\0\0@\0\0\0\0\0\0\0"..., 784, 64) = 784
pread64(3, "\4\0\0\0 \0\0\0\5\0\0\0GNU\0\2\0\0\300\4\0\0\0\3\0\0\0\0\0\0\0"..., 48, 848) = 48
pread64(3, "\4\0\0\0\24\0\0\0\3\0\0\0GNU\0i8\235HZ\227\223\333\350s\360\352,\223\340."..., 68, 896) = 68
newfstatat(3, "", {st_mode=S_IFREG|0644, st_size=2216304, ...}, AT_EMPTY_PATH) = 0
pread64(3, "\6\0\0\0\4\0\0\0@\0\0\0\0\0\0\0@\0\0\0\0\0\0\0@\0\0\0\0\0\0\0"..., 784, 64) = 784
mmap(NULL, 2260560, PROT_READ, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x7fc18d600000
mmap(0x7fc18d628000, 1658880, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x28000) = 0x7fc18d628000
mmap(0x7fc18d7bd000, 360448, PROT_READ, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x1bd000) = 0x7fc18d7bd000
mmap(0x7fc18d815000, 24576, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x214000) = 0x7fc18d815000
mmap(0x7fc18d81b000, 52816, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x7fc18d81b000
close(3)                                = 0
mmap(NULL, 12288, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fc18d961000
arch_prctl(ARCH_SET_FS, 0x7fc18d961740) = 0
set_tid_address(0x7fc18d961a10)         = 21183
set_robust_list(0x7fc18d961a20, 24)     = 0
rseq(0x7fc18d9620e0, 0x20, 0, 0x53053053) = 0
mprotect(0x7fc18d815000, 16384, PROT_READ) = 0
mprotect(0x55b333cc8000, 4096, PROT_READ) = 0
mprotect(0x7fc18d9b0000, 8192, PROT_READ) = 0
prlimit64(0, RLIMIT_STACK, NULL, {rlim_cur=8192*1024, rlim_max=RLIM64_INFINITY}) = 0
munmap(0x7fc18d964000, 70567)           = 0
newfstatat(1, "", {st_mode=S_IFCHR|0620, st_rdev=makedev(0x88, 0x1), ...}, AT_EMPTY_PATH) = 0
getrandom("\xaf\xb4\x13\x5c\x53\x7c\x1c\x55", 8, GRND_NONBLOCK) = 8
brk(NULL)                               = 0x55b334ae3000
brk(0x55b334b04000)                     = 0x55b334b04000
write(1, "Hello!\n", 7Hello!
)                 = 7
exit_group(0)                           = ?
+++ exited with 0 +++

在 line 37 中 write system call 把字符串 Hello! 傳給 file descriptor 1 的設備

$ ls /dev/std* -l
lrwxrwxrwx 1 root root 15  四  10 19:55 /dev/stderr -> /proc/self/fd/2
lrwxrwxrwx 1 root root 15  四  10 19:55 /dev/stdin -> /proc/self/fd/0
lrwxrwxrwx 1 root root 15  四  10 19:55 /dev/stdout -> /proc/self/fd/1

對應到的為 stdout

建立執行緒

pthread API

首先程式運行時第一個 tread 負責運行 main()，建立一個以上的執行緒則使用 pthread_create ，而執行緒完成工作後很多種結束的方法

The new thread terminates in one of the following ways:

It calls pthread_exit(3), specifying an exit status value that is available to another thread in the same process that calls pthread_join(3).

It returns from start_routine(). This is equivalent to calling pthread_exit(3) with the value supplied in the return statement.

It is canceled (see pthread_cancel(3)).

Any of the threads in the process calls exit(3), or the main thread performs a return from main(). This causes the termination of all threads in the process.

如果不使用 pthread_join ，該執行緒會繼續佔用資源直到 process 結束。

pthread_create

int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
                          void *(*start_routine) (void *), void *arg);

thread: 指向 pthread_t 結構體的指標
attr: 設定 thread 的 attribute，如果設定 attr 為 NULL ，則這個 thread 使用 default attributes
start_routine: 這個 thread 會 invoke start_routine()
arg 會作為 start_routine 的引數

嘗試建立 hash table

hlist_add_head(&dnode->list, &htable[key]); // add to hash table

[ 7850.213620] BUG: kernel NULL pointer dereference, address: 0000000000000008
[ 7850.213621] #PF: supervisor write access in kernel mode
[ 7850.213622] #PF: error_code(0x0002) - not-present page

#PF 代表 page fault，當 page fault 發生時，CPU 會將相關的錯誤訊息除存在 error code 的特殊暫存器中 (32bit value)
supervisor write access in kernel mode: 可能發生的原因包含
1. 程式碼對 kernel 空間的指標操作，但是這些指標操作沒有經過適當得初始化。
2. 對該資源進行寫操作，但是該資源已經被鎖定 or 被其他程式使用。
3. 使用了已經被取消或是被棄用的函式或 API，這些函式可能會對 kernel 的 memory 進行寫操作而沒有足夠的權限

Memroy management

在多執行緒的預期流程，insmode -> 多執行緒進行 hash table 的查表、填表 -> 結束運算，走訪 hash table 並釋放空間 -> rmmod

lkmpg 4.3 The __init and __exit Macros
The __exit macro causes the omission of the function when the module is built into the kernel, and like __init , has no effect for loadable modules. Again, if you consider when the cleanup function runs, this makes complete sense; built-in drivers do not need a cleanup function, while loadable modules do.

quick note

function declaration isn't a prototype
- 引數加上 void