2022q1 Homework3 (fibdrv)

contributed by < ganoliz >

實驗環境

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

$ lscpu
架構：                           x86_64
CPU 作業模式：                   32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          8
On-line CPU(s) list:             0-7
每核心執行緒數：                 2
每通訊端核心數：                 4
Socket(s):                       1
NUMA 節點：                      1
供應商識別號：                   GenuineIntel
CPU 家族：                       6
型號：                           158
Model name:                      Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz
製程：                           9
CPU MHz：                        2436.942
CPU max MHz:                     4200.0000
CPU min MHz:                     800.0000
BogoMIPS:                        7200.00
虛擬：                           VT-x
L1d 快取：                       128 KiB
L1i 快取：                       128 KiB
L2 快取：                        1 MiB
L3 快取：                        8 MiB
NUMA node0 CPU(s)：              0-7

作業要求

在 GitHub 上 fork fibdrv，目標是修正 Fibonacci 數計算的正確性 (現有實作存在缺陷，請指出)，隨後改善 fibdrv 計算 Fibinacci 數列的執行效率，過程中需要量化執行時間，可在 Linux 核心模組和使用層級去測量
- 原本的程式碼只能列出到 fib(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 的執行時間，引入費氏數列分析提到的策略，並善用 clz / ffs 一類的指令 (Linux 核心有對應的包裝函式)，過程中都要充分量化
嘗試研讀 bignum (fibdrv 分支) 的實作，理解其中的技巧並與你的實作進行效能比較，探討個中值得取鏡之處。
- 原理和分析可見 KYG-yaya573142 的報告
當 fib(n) 隨著 n越來越大時，由 Linux 核心傳遞字串形式的十進位就成為效能瓶頸，研讀〈Integer Encoding Algorithm 筆記〉所提及的策略，在 Linux 核心模組先對數值進行編碼和壓縮，以二進位方式傳遞到使用者層級後，再由應用程式予以顯示 Fib(n) 數值
- 儘量降低由核心傳遞到應用程式的資料量
- 確保應用程式不需要過多的計算量才可重現 Fibonacci 數列

開發進度

針對 kernel 運算的時間作圖

目前先針對在 kernel 計算 fib(1) ~ fib(100) 分別所需的計算時間，以分佈的方式作圖看看：

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 →

若我們再加上 user time 與 kernel to user 的轉換時間則如圖所示：

Fast Doubling

根據 Fast Doubling 這篇文章所述

F_{2 n + 1} = F_{n + 1}^{2} + F_{n}^{2}

F_{2 n} = F_{n} * (2 * F_{n + 1} - F_{n})

使用這兩個公式，當我們在計算費波那契數列時，就不須用一個一個數列值往後推，只需要知道他的 f(n/2+1) , f(n/2) , f(n/2-1) 的值就好。這說明我們的計算量可以比累加的方法減少至少從　f(n-1) ~ f(n/2+1) 的計算量，時間複雜度為 O(log(n))。

///////////////////////////////////////////////////////////////////////////////
// Fast doubling: O(log(n))
//   Using 2n to the Fibonacci matrix above, we can derive that:
//     F(2n)   = F(n) * [ 2 * F(n+1) – F(n) ]
//     F(2n+1) = F(n+1)^2 + F(n)^2
//     (and F(2n-1) = F(n)^2 + F(n-1)^2)
uint64_t fib(unsigned int n)
{
  if (n == 0) {
    return 0; // F(0) = 0.
  } else if (n <= 2) {
    return 1; // F(1) = F(2) = 0.
  }

  unsigned int k = 0;
  if (n % 2) { // By F(n) = F(2k+1) = F(k+1)^2 + F(k)^2
    k = (n - 1) / 2;
    return fib(k) * fib(k) + fib(k + 1) * fib(k + 1);
  } else { // By F(n) = F(2k) = F(k) * [ 2 * F(k+1) – F(k) ]
    k = n / 2;
    return fib(k) * (2 * fib(k + 1) - fib(k));
  }
}

當然根據文章所述，我們還能更進一步優化程式碼(Top-down)變成如下：

// 4 is not a fibonacci number, so using it as initialized value.
const uint64_t INIT = 4;

uint64_t fib(unsigned int n)
{
  uint64_t f[2] = { INIT, INIT };
  fib_helper(n, f);
  return f[0];
}


// Set f[0], f[1] to F(n), F(n+1).
void fib_helper(unsigned int n, uint64_t f[])
{
  if (!n) {
    f[0] = 0;
    f[1] = 1;
    return;
  }

  fib_helper(n / 2, f);
  // k = floor(n/2), so k = n / 2 if n is even, k = (n - 1) / 2 if n is odd.
  uint64_t a = f[0]; // F(k)
  uint64_t b = f[1]; // F(k+1)

  uint64_t c = a * (2 * b - a); // F(2k) = F(k) * [ 2 * F(k+1) – F(k) ]
  uint64_t d = a * a + b * b;   // F(2k+1) = F(k+1)^2 + F(k)^2

  if (n % 2) {    // k = (n - 1) / 2, so F(2k) = F(n-1), F(2k+1) = F(n).
    f[0] = d;     // F(n) = F(2k+1).
    f[1] = c + d; // F(n+1) = F(n-1) + F(n) = F(2k) + F(2k+1).
  } else {        // k = n / 2, so F(2k) = F(n), F(2k+1) = F(n+1).
    f[0] = c;     // F(n) = F(2k).
    f[1] = d;     // F(n+1) = F(2k).
  }
}

根據 n 是奇數或偶數決定計算 F((n-1)/2) 或是 F(n/2) 。

$k_{i}$	$k_{1}$	$k_{2}$	$k_{3}$	$k_{4}$	$k_{5}$
n(= $k_{i}$ )	10	5	2	1	0
n is odd		v		v
$F_{2 k_{i + 1}}$		$F_{4}$		$F_{0}$
$F_{n}$	$F_{10}$	$F_{5}$	$F_{2}$	$F_{1}$	$F_{0}$
$F_{n + 1}$		$F_{6}$	$F_{3}$	$F_{2}$	$F_{1}$
binary	1010	1010	1010	1010

可以看到 n 為偶數時，我們可以找到

F_{k}

的 k = n/2 ，這樣我們能用

[F_{k}, F_{k + 1}] = [F_{n / 2}, F_{n / 2 + 1}]

來計算

[F_{2 k}, F_{2 k + 1}] = [F_{n}, F_{n + 1}]

反之當 n 為奇數時，我們可以找到

F_{k}

的 k = (n-1)/2 。我們能用

[F_{k}, F_{k + 1}] = [F_{(n - 1) / 2}, F_{(n - 1) / 2 + 1}]

來計算

[F_{2 k}, F_{2 k + 1}] = [F_{n - 1}, F_{n}]

然後我們再多做一個加法

[F_{n}, F_{n - 1} + F_{n}]

因此可以得到

[F_{n}, F_{n + 1}]

由於除2可以看作是進行 binary code 右移，因此我們可以根據老師所述，結合 clz / ctz 的指令搭配 Fast Doubling(先去除數字 MSB 起算的開頭 0 位元，因為真正的數字不包含 leading 0s)。
以下是 bignum 的 fast doubling 實作:

    bn *a1 = fib; /* Use output param fib as a1 */

    bn_t a0, tmp, a;
    bn_init_u32(a0, 0); /*  a0 = 0 */
    bn_set_u32(a1, 1);  /*  a1 = 1 */
    bn_init(tmp);       /* tmp = 0 */
    bn_init(a);

    /* Start at second-highest bit set. */
    for (uint64_t k = ((uint64_t) 1) << (62 - __builtin_clzll(n)); k; k >>= 1) {
        /* Both ways use two squares, two adds, one multipy and one shift. */
        bn_lshift(a0, 1, a); /* a03 = a0 * 2 */
        bn_add(a, a1, a);    /*   ... + a1 */
        bn_sqr(a1, tmp);     /* tmp = a1^2 */
        bn_sqr(a0, a0);      /* a0 = a0 * a0 */
        bn_add(a0, tmp, a0); /*  ... + a1 * a1 */
        bn_mul(a1, a, a1);   /*  a1 = a1 * a */
        if (k & n) {
            bn_swap(a1, a0);    /*  a1 <-> a0 */
            bn_add(a0, a1, a1); /*  a1 += a0 */
        }
    }

使用 bignum 完成 fib(100) 內的操作

首先閱讀完《The Linux Kernel Module Programming Guide》的 character driver 後，可以知道幾件事：

在 kernel print 資訊須使用 printk() 或是 pr_info()
在 kernel space 端傳遞值給 user space 可以採用 copy_to_user()
盡量將變數宣告 static

於是我開始動手修改 fibdrv.c 程式碼:

static struct BigN 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;
    
    struct BigN f[k+2];
    
    f[0].lower = 0;
    f[0].upper = 0;
    f[1].lower = 1; 
    f[1].upper = 0;
    

    for (int i = 2; i <= k; i++) {
        //f[i] = f[i - 1] + f[i - 2];
        addBigN(&f[i],f[i-1],f[i-2]);
    }
    printk(KERN_INFO "count %u %u",k,f[k].lower);

    return f[k];
}

將 fib_sequence 改成 big_number 的形式，並回傳指定要的 fibonacci number 編號的 BigN 結構。

static ssize_t fib_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
    struct BigN k_fib=fib_sequence(*offset);
    
    unsigned long temp = copy_to_user(buf,&(k_fib.lower),8);
    unsigned long temp1 = copy_to_user(buf+8,&(k_fib.upper),8);
    printk(KERN_INFO "read: %u ,success number : %u ",k_fib.lower,temp);
    return temp+temp1;
    //return (ssize_t) fib_sequence(*offset);
}

接著我們將 upper 與 lower 複製到 user_space 的 buffer 。 copy_to_user 會回傳未成功複製的位元的值，若所有位元的值都成功複製，預期回傳應為 0 。
接著我們可以使用終端機至 /var/log 開啟 kern.log 或使用命令 tail -200 kern.log 來觀察我們剛剛使用 printk() 輸出的訊息：

Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753098] read: 512559680 ,success number : 0 
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753099] count 47 2971215073
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753100] read: 2971215073 ,success number : 0 
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753101] count 46 1836311903
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753102] read: 1836311903 ,success number : 0 
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753103] count 45 1134903170
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753104] read: 1134903170 ,success number : 0 
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753105] count 44 701408733
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753106] read: 701408733 ,success number : 0 
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753107] count 43 433494437
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753108] read: 433494437 ,success number : 0 
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753109] count 42 267914296
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753110] read: 267914296 ,success number : 0 
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753111] count 41 165580141
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753112] read: 165580141 ,success number : 0 
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753113] count 40 102334155
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753114] read: 102334155 ,success number : 0 
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753115] count 39 63245986
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753116] read: 63245986 ,success number : 0 
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753117] count 38 39088169
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753118] read: 39088169 ,success number : 0 
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753119] count 37 24157817
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753120] read: 24157817 ,success number : 0 
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753121] count 36 14930352
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753122] read: 14930352 ,success number : 0 
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753123] count 35 9227465
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753123] read: 9227465 ,success number : 0 
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753125] count 34 5702887
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753125] read: 5702887 ,success number : 0 
Mar 20 17:52:57 casserly-System-Product-Name kernel: [192857.753127] count 33 3524578

如上所示，這使得要 Debug 稍微方便一點。
接著我們來看看 client.c :

   for (int i = 0; i <= offset; i++) {
        lseek(fd, i, SEEK_SET);
        sz = read(fd, buf, 8);
        /*
        printf("Reading from " FIB_DEV
               " at offset %d, returned the sequence "
               "%lld.\n",
               i, sz);
        */
        unsigned long long temp = transfer1(buf,0);
        unsigned long long temp1 = transfer1(buf,1);
        
        a =((uint128_t) temp1)<<64 + temp; 
        if (temp1 == 0)
        printf("Reading from " FIB_DEV
               " at offset %d, returned the sequence "
               "%llu.\n",
               i, temp);
        else {
                    printf("Reading from " FIB_DEV
               " at offset %d, returned the sequence "
               ,
               i);
               print_u128_u(a);
               printf(".\n");
        }
    }

我目前遇到的問題是如何將 upper 的值與 lower 的值加在一起，百思不得其解。我目前在想轉成 character ，但是那就跟 Small/Short String Optimization 程式碼的方法一致了。一方面我把 character 實做的程式碼看了一下並 clone 下來跑跑看，另一方面試圖在 user space 將 __int128_t 的資料型態定義並能夠使用 print 輸出。

目前依據老師指示參看 bignum範例如何從底層實作大數字運算。由高層次 bignum.c 到底層 bitwise 的實作 apm.c ，處處都藏著能夠加速運算的細節。

首先我們先看看底層的實作:

//==========================================================   apm.h
/* Set u[size] = u[size] + v and return the carry. */
apm_digit apm_daddi(apm_digit *u, apm_size size, apm_digit v);

/* Set w[size] = u[size] + v[size] and return the carry. */
apm_digit apm_add_n(const apm_digit *u,
                    const apm_digit *v,
                    apm_size size,
                    apm_digit *w);
/* Set w[max(usize, vsize)] = u[usize] + v[vsize] and return the carry. */
apm_digit apm_add(const apm_digit *u,
                  apm_size usize,
                  const apm_digit *v,
                  apm_size vsize,
                  apm_digit *w);

/* Set u[size] = u[size] + v[size] and return the carry. */
/* apm_digit	apm_addi_n(apm_digit *u, const apm_digit *v, apm_size size); */
#define apm_addi_n(u, v, size) apm_add_n(u, v, size, u)
/* Set u[usize] = u[usize] + v[vsize], usize >= vsize, and return the carry. */
apm_digit apm_addi(apm_digit *u,
                   apm_size usize,
                   const apm_digit *v,
                   apm_size vsize);

//==========================================================    apm.c
static apm_digit apm_inc(apm_digit *u, apm_size size)
{
    if (size == 0)
        return 1;

    for (; size--; ++u) {
        if (++*u)
            return 0;
    }
    return 1;
}

/* Set u[size] = u[size] - 1, and return the borrow. */
static apm_digit apm_dec(apm_digit *u, apm_size size)
{
    if (size == 0)
        return 1;

    for (;;) {
        if (u[0]--)
            return 0;
        if (--size == 0)
            return 1;
        u++;
    }
    return 1;
}

apm_digit apm_daddi(apm_digit *u, apm_size size, apm_digit v)
{
    if (v == 0 || size == 0)
        return v;
    return ((u[0] += v) < v) ? apm_inc(&u[1], size - 1) : 0;
}

/* Set w[size] = u[size] + v[size] and return the carry. */
apm_digit apm_add_n(const apm_digit *u,
                    const apm_digit *v,
                    apm_size size,
                    apm_digit *w)
{
    ASSERT(u != NULL);
    ASSERT(v != NULL);
    ASSERT(w != NULL);

    apm_digit cy = 0;
    while (size--) {
        apm_digit ud = *u++;
        const apm_digit vd = *v++;
        cy = (ud += cy) < cy;
        cy += (*w = ud + vd) < vd;
        ++w;
    }
    return cy;
}

apm_digit apm_add(const apm_digit *u,
                  apm_size usize,
                  const apm_digit *v,
                  apm_size vsize,
                  apm_digit *w)
{
    ASSERT(u != NULL);
    ASSERT(usize > 0);
    ASSERT(u[usize - 1]);
    ASSERT(v != NULL);
    ASSERT(vsize > 0);
    ASSERT(v[vsize - 1]);

    if (usize < vsize) {
        apm_digit cy = apm_add_n(u, v, usize, w);
        if (v != w)
            apm_copy(v + usize, vsize - usize, w + usize);
        return cy ? apm_inc(w + usize, vsize - usize) : 0;
    } else if (usize > vsize) {
        apm_digit cy = apm_add_n(u, v, vsize, w);
        if (u != w)
            apm_copy(u + vsize, usize - vsize, w + vsize);
        return cy ? apm_inc(w + vsize, usize - vsize) : 0;
    }
    /* usize == vsize */
    return apm_add_n(u, v, usize, w);
}

/* Set u[usize] = u[usize] + v[vsize] and return the carry. */
apm_digit apm_addi(apm_digit *u,
                   apm_size usize,
                   const apm_digit *v,
                   apm_size vsize)
{
    ASSERT(u != NULL);
    ASSERT(v != NULL);
    ASSERT(usize >= vsize);

    apm_digit cy = apm_addi_n(u, v, vsize);
    return cy ? apm_inc(u + vsize, usize - vsize) : 0;
}

/* Set w[size] = u[size] - v[size] and return the borrow. */
apm_digit apm_sub_n(const apm_digit *u,
                    const apm_digit *v,
                    apm_size size,
                    apm_digit *w)
{
    ASSERT(u != NULL);
    ASSERT(v != NULL);
    ASSERT(w != NULL);

    apm_digit cy = 0;
    while (size--) {
        const apm_digit ud = *u++;
        apm_digit vd = *v++;
        cy = (vd += cy) < cy;
        cy += (*w = ud - vd) > ud;
        ++w;
    }
    return cy;
}

底層實作都是以二進位來思考，當加 1 時指標就需要依序從低位元往高位元走。直到我們加 1 之後不等於 0 (沒有進位的時候才停止) 接著回傳進位。接著有一些類似組合語言的 immediate 加法命名方式 addi 是省略一些變數的儲存。最主要的想法我們來看 apm_add() : 藉由兩個變數 u, v 我們需要知道它的 bits size 大小才方便做處理，若 usize > vsize 則我們把高位元直接複製 (usize - vsize) 個 bits 值就好，反之亦然。
若 usize == vsize 則使用 apm_add_n() 來計算。

看完程式碼想要測試看看 bn.h ，結果發現不太曉得如何在 Linux Kernel include "bn.h" ，目前重新回去看 Makefile 怎麼樣能 include 到。

要遞迴呼叫一個 makefile，請使用特殊的 $(MAKE) 而非 make
其他隱藏的規則可以在 variables used in implicit rules 找到
gcc 的參數也可以從這裡參考

另外還有比如 Makefile 裡的這行

all: $(GIT_HOOKS) client
<Tab>$(MAKE) -C $(KDIR) M=$(PWD) modules

意思就是當 make 的目標爲 all 時， -C $(KDIR) 指明切換到 Linux 核心原始程式碼目錄下讀取其中頂端的 Makefile； M=$(PWD) ( M= 的原本意思是 pass 參數讓 Makefile 能看見)。
因此我們看看在 KDIR=/lib/modules/$(shell uname -r)/build 下的 Makefile 可以看到以下註解:

# Use make M=dir or set the environment variable KBUILD_EXTMOD to specify the
# directory of external module to build. Setting M= takes precedence.
#=======================================

PHONY += modules
modules: $(if $(KBUILD_BUILTIN),vmlinux) modules_check modules_prepare

因此敘述表明這一段 make modules 在 KDIR 位置下的 Makefile 並傳遞我們 Character device 的位置給這個 Makefile。

可參見 0xff07/bignum，注意要是 fibdrv 分支，這是移植到 Linux 核心模組的嘗試。
:notes: jserv

Bignum 的時間效能分析如下：

無使用fast doubling 技巧:

使用 fast doubling技巧:

效能差異並不明顯，
但當我們把結果拉到F(1000):

fast doubling:

效能相差就很大了。

研讀 KYG-yaya573142 的報告

排除干擾效能分析的因素

修改 /etc/default/grub 的 GRUB_CMDLINE_LINUX_DEFAULT，在裡面加上 isolcpus=(要獨立的 cpu 編號)
重新開機啟動後，我們可以就能將程式（Process ,Task）固定在這個 CPU 執行。

$ sudo taskset -c cpu編號 ./client(執行的程式)

我們可以透過 /sys/devices/system/cpu/isolated 查看被 isolated 的 CPU 編號。

抑制 address space layout randomization (ASLR)

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

設定 scaling_governor 為 performance 。準備一個 shell script

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

關閉 Intel 處理器的 turbo mode:

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

當我們做把 CPU 編號 7 隔出來只做我們的 ./client.c 就能見到較為下圖平整的效能圖：

但是還是有一些 Timer 的中斷。根據我們查看 cat /proc/interrupts：

casserly@casserly-System-Product-Name:~/LinuxHW2/fibdrv$ cat /proc/interrupts
            CPU0       CPU1       CPU2       CPU3       CPU4       CPU5       CPU6       CPU7       
   0:          8          0          0          0          0          0          0          0   IO-APIC    2-edge      timer
   1:          0          0          0          0          0          0          0          4   IO-APIC    1-edge      i8042
   8:          1          0          0          0          0          0          0          0   IO-APIC    8-edge      rtc0
   9:          0          0          0          0          0          0          0          0   IO-APIC    9-fasteoi   acpi
  12:          0          0          0          0          0          0          6          0   IO-APIC   12-edge      i8042
  16:          0          0          0          7          0          0          0          0   IO-APIC   16-fasteoi   i801_smbus
  17:        335          0          0          0          0          0          0          0   IO-APIC   17-fasteoi   snd_hda_intel:card1
 124:          0         25          0          0          0     659656          0          0   PCI-MSI 520192-edge      enp0s31f6
 125:          0          0       9268          0          0          0      84586          0   PCI-MSI 376832-edge      ahci[0000:00:17.0]
 126:          0       1731       8305       6734      34565          0          0          0   PCI-MSI 327680-edge      xhci_hcd
 127:          0          0          0          0          0         46          0          0   PCI-MSI 360448-edge      mei_me
 128:          0          0          0    1093288          0          0        826          0   PCI-MSI 524288-edge      nvkm
 129:          0        290          0          0          0          0          0        712   PCI-MSI 514048-edge      snd_hda_intel:card0
 NMI:         52         51         50         54         52         53         51          1   Non-maskable interrupts
 LOC:   34294105   33462505   33369919   32449519   33363776   33385164   32648732     469062   Local timer interrupts
 SPU:          0          0          0          0          0          0          0          0   Spurious interrupts
 PMI:         52         51         50         54         52         53         51          1   Performance monitoring interrupts
 IWI:          0          0          0          0          0          0          0          0   IRQ work interrupts
 RTR:          1          0          0          0          0          0          0          0   APIC ICR read retries
 RES:      22335      22699      21681      38878      24019      36512      23749       2905   Rescheduling interrupts
 CAL:     246766     217812     195027     181418     186894     184548     183899       9914   Function call interrupts
 TLB:     123593     126404     118665     125695     119517     124648     123653          0   TLB shootdowns
 TRM:          0          0          0          0          0          0          0          0   Thermal event interrupts
 THR:          0          0          0          0          0          0          0          0   Threshold APIC interrupts
 DFR:          0          0          0          0          0          0          0          0   Deferred Error APIC interrupts
 MCE:          0          0          0          0          0          0          0          0   Machine check exceptions
 MCP:         41         42         42         42         42         42         42         42   Machine check polls
 ERR:          0
 MIS:          0
 PIN:          0          0          0          0          0          0          0          0   Posted-interrupt notification event
 NPI:          0          0          0          0          0          0          0          0   Nested posted-interrupt event
 PIW:          0          0          0          0          0          0          0          0   Posted-interrupt wakeup event

SMP IRQ affinity 設定: 在 /proc/irq 下面做 smp affinity 的設定

sudo bash -c "echo 7f > /proc/irq/default_smp_affinity"

設定完之後再次查看 interupts 次數：

            CPU0       CPU1       CPU2       CPU3       CPU4       CPU5       CPU6       CPU7       
   0:          8          0          0          0          0          0          0          0   IO-APIC    2-edge      timer
   1:          0          0          0          0          0          0          0          4   IO-APIC    1-edge      i8042
   8:          1          0          0          0          0          0          0          0   IO-APIC    8-edge      rtc0
   9:          0          0          0          0          0          0          0          0   IO-APIC    9-fasteoi   acpi
  12:          0          0          0          0          0          0          6          0   IO-APIC   12-edge      i8042
  16:          0          0          0          7          0          0          0          0   IO-APIC   16-fasteoi   i801_smbus
  17:        335          0          0          0          0          0          0          0   IO-APIC   17-fasteoi   snd_hda_intel:card1
 124:          0       9759          0          0          0          0      38460          0   PCI-MSI 376832-edge      ahci[0000:00:17.0]
 125:          0        198         59        852      11246          0          0          0   PCI-MSI 327680-edge      xhci_hcd
 126:          0          0          0          0         87      38483          0          0   PCI-MSI 520192-edge      enp0s31f6
 127:          0          0          0          0          0         46          0          0   PCI-MSI 360448-edge      mei_me
 128:          0          0          0      54476          0          0        861          0   PCI-MSI 524288-edge      nvkm
 129:          0        884          0          0          0          0          0        712   PCI-MSI 514048-edge      snd_hda_intel:card0
 NMI:          6          7          6          6          7          6          6          0   Non-maskable interrupts
 LOC:    3838794    3735323    3683084    3403952    4451933    3816272    3616656      39247   Local timer interrupts
 SPU:          0          0          0          0          0          0          0          0   Spurious interrupts
 PMI:          6          7          6          6          7          6          6          0   Performance monitoring interrupts
 IWI:          0          0          0          0          0          0          0          0   IRQ work interrupts
 RTR:          1          0          0          0          0          0          0          0   APIC ICR read retries
 RES:       3165       3372       3264       5568       3531       4231       3304        316   Rescheduling interrupts
 CAL:      46341      42639      43589      38648      41161      41004      41012       7510   Function call interrupts
 TLB:      30299      29639      31207      30894      29747      29560      29855          0   TLB shootdowns
 TRM:          0          0          0          0          0          0          0          0   Thermal event interrupts
 THR:          0          0          0          0          0          0          0          0   Threshold APIC interrupts
 DFR:          0          0          0          0          0          0          0          0   Deferred Error APIC interrupts
 MCE:          0          0          0          0          0          0          0          0   Machine check exceptions
 MCP:          2          3          3          3          3          3          3          3   Machine check polls
 ERR:          0
 MIS:          0
 PIN:          0          0          0          0          0          0          0          0   Posted-interrupt notification event
 NPI:          0          0          0          0          0          0          0          0   Nested posted-interrupt event
 PIW:          0          0          0          0          0          0          0          0   Posted-interrupt wakeup event

整體來說 local timers interrupts 又變得更少了。

數值編碼壓縮

當我們使用 bignum 大數運算得到的二進制值，會透過 bn_sprintf() 將結果存為十進制的 char * ，接著我們透過 buffer 將結果透過 copy_to_user 傳遞回 user space 。由於每個 char 只存一個 10 位數的 digits ，因此傳遞效率是挺差的。

我們甚至以 BCD 碼來做編碼還比直接使用 char 省了一半的空間( BCD 碼八位元可以放兩個 digits )

這邊先看看在 User Space 才轉換的 BignumBinary 直接 copy_to_user 與原本直接在 Kernel Space 就轉換的 BignumChar copy_to_user 的效能差異：

雖然差距只有個 ns (約 77ns 與 65ns)的差距，但也顯示出 copy_to_user 的傳輸 Bytes 數是有優化空間的。

研讀老師提供的教材Integer Encoding Algorithm 筆記與 invertedtomato/integer-compression 來進行整數壓縮編碼:

Variable Byte

Variable Byte 的方式是企圖採用最少的 Bytes 數來存取，使用最前面的 1 個 bit 當作 flag 來確認資料是否串聯下一個 bytes (若為 0 代表這是 LSB least sinificant bytes) 剩下 7 個 bits 拿來存資料:

數值(unsigned long)	binary(32 bits)	Encode Variant
0	00000000 00000000 00000000 00000000	00000000
127	00000000 00000000 00000000 01111111	01111111
128	00000000 00000000 00000000 10000000	10000001 00000000
4294967295	11111111 11111111 11111111 11111111	10001111 11111111 11111111 11111111 01111111

這個方法採用最少 bytes 去編碼，但因為每 32-bits 使用 4 個 bits 去判斷是否為 LSByte 因此造成當我們要編碼的數值超過

2^{28} - 1

的時候，編碼的 bytes 數反而會比沒編碼的 Bytes 數要多一個。

Run Length encoding (RLE)

根據第一個數字來判定後一個整數的重複次數來做壓縮，比如:

5 5 5 5 8 8 8 2 2 2 2 2

可被壓縮成:

4 5 3 8 5 2

若連續都為不同的數:

1 2 3 4 5 6

則會用一個負數來代表連續不同數的個數:

-6 1 2 3 4 5 6

這種編碼壓縮的方法特性很明顯:就是在數字間熵值 (entropy) 大時 (數字幾乎都不重複) 時，壓縮率很差。做為 fibdrv bignum 計算數值的壓縮來說，不是一個很好的選擇。

Delta of Delta + Variable length coding

Delta 也是一個編碼常用的技巧，比如一個整數陣列為 [ 100, 109, 105, 117, 93] 根據我們的 delta 就可以編碼為 : [100, 9, 5, 17, -7]。再者繼續編成 delta of delta (DoD) : [100, 9, -4, 12, -24]。當我們產生出這種 DoD 格式的編碼之後，我們需要使用 Variable length coding (VLC) 的方法產生出 tag bits 才能在 Decode 階段正確的把 DoD 格式還原成原本的整數數值陣列， VLC 的方法用以下表格舉例:

DoD	tag bits	following bits
0	0	0
[-64,63]	10	7 bits
[-512,511]	110	10 bits
[-4096,4095]	1110	13 bits
[-32768,32767]	11110	16 bits
else	11111	64 bits

使用 DoD 的好處是:由於是目前這個整數數值與上一個整數數值的相差大小，因此即便一開始找的數值很差，對於 DoD 的影響就比單純使用 Difference 方法小。然後因為 tag bits 由左開始連續個 1 ，所以解碼是唯一不會有混淆的情況發生。這裡壓縮的效率與數值的變化是否很大有關。以 fib_drv bignum 而言，每個 apm_digits 的大小為 64-bits (根據我的電腦) 。因此分析最差的情況是 DoD 為需要 69 bits 去儲存下一個數。實際情況則要再分析是否能有效壓縮。

Binary Packing (BP128)

Binary Packing 技巧是判斷整數陣列裡面最大的值需要用幾個 bits 去儲存，其他數值也用相同的 bits 數去儲存即可。

102, 3332, 12, 7,33, 65535

可以看到我們的最大值為 65535 (

2^{16} - 2

)，代表我們每一個整數都用 16 bits 去儲存。這裡也有一個問題就是這個陣列的數值最大值是否與我們原先編碼的 bytes 數有足夠的優化空間(比如我們最大值預期為原先編碼 bytes 數的 1/2 以下)。由於我們可壓縮的 bytes 數與我們的最大值相關，因此我認為 fibdrv bignum 使用這個編碼的壓縮效果會不甚滿意，可能會需要額外的輔助限制條件與規則 ( 文章提到的 Patched coding 方法 )。

根據以上方法，我們決定先以 Variable Byte 的來實作看看。因為這個方法比較簡單，根據我們 fibdrv bignum 效果也比較容易想像。

以下為 encoder 程式碼試作 :

int ByteModify(unsigned long  *x ,unsigned char *buffer){
	
	 if(*x == 0UL){		
		*buffer = 0x00;
		return 1;
	 }
	 int leading_zero = __builtin_clzl(*x);
	 printf("leading zero is: %d",leading_zero);
	 int bit_length=32-leading_zero;
	 
	 unsigned char *tmp1 = (unsigned char *)(void *)(x);
	 unsigned char *tmp2 = (unsigned char *)(void *)(x)+1;
	 unsigned char *tmp3 = (unsigned char *)(void *)(x)+2;
	 unsigned char *tmp4 = (unsigned char *)(void *)(x)+3;
	 
	 unsigned char c0 = *tmp1 & 0x7f; 
	 
	 unsigned char c0_c = (*tmp1 >> 7) & 0x01 ;
	 
	 unsigned char c1 = ((*tmp2 & 0x3f)<<1) | 0x80 | c0_c ;
	 unsigned char c1_c = (*tmp2 >> 6) & 0x03;
	 unsigned char c2 = ((*tmp3 & 0x1f)<<2) | 0x80 | c1_c ;
	 unsigned char c2_c = (*tmp3 >>5) & 0x07;
	 unsigned char c3 = ((*tmp4 & 0x0f)<<3) | 0x80 | c2_c ;
	 unsigned char c4 = ((*tmp4 >>4) & 0x0f) | 0x80 ;
	 
	 int size = -1;
	 
	 if(bit_length <=7){
	 	
	 	*buffer = c0; 
	 	size =1;
	 }
	 else if(bit_length <=14){
	 	
	 	*buffer++ = c1;
		*buffer++ = c0; 
		 size = 2;
	 }
	 else if(bit_length <=21){
	 	*buffer++ = c2;
	 	*buffer++ = c1;
	 	*buffer++ =c0;
	 	size=3;
	 }
	 else if(bit_length <=28){
	 	*buffer++ = c3;
	 	*buffer++ = c2;
	 	*buffer++ = c1;
	 	*buffer++ = c0;
	 	size =4;
	 }
	 else if(bit_length <=32){
	 	*buffer++ = c4;
	 	*buffer++ = c3;
		 *buffer++ = c2;
		 *buffer++ = c1;
		 *buffer++ = c0; 
		 size =5;
	 } 
	 
	 return size;
	 
}

int encoder(unsigned long  *x ,unsigned char *result, int size){
		
	int total_size=0;
	 
	size=size*2;
	x=x+size-1;
	
	do{
		unsigned char *buffer = malloc(sizeof(unsigned char)*5);
		
		int bytes_size = ByteModify((void *)x,buffer);
		
		memcpy((void *)result,buffer,bytes_size);
		int i;

		result=result+bytes_size;
		total_size+=bytes_size;
		
		x--;
		free(buffer);	
	} while (--size >0);

	return total_size;
}

以及我的 Decoder :

int Decoder(char *x,unsigned long long *buffer,int size){

	//size = number of *x in x 
	int fib_size=0;	
	unsigned long temp=0;
	unsigned long temp_msb=0;
	int mergelong=0;
	
	do{
		temp = temp << 7;
		temp  = temp | (*x & 0x7f);	
		if(!(*x & 0x80)){ // x is  the last byte.
		    mergelong++;
		    if(mergelong == 2){
			
		 	*buffer++ = (((unsigned long long)(temp_msb)) << 32) | (unsigned long long)temp;
		 	fib_size++;
			mergelong = 0;
		 	temp=0;
		 	temp_msb = 0;
		    }
		else{
			 
	 		temp_msb = temp;
			temp=0;	
	    	    }
		}
		
		*x++;
	}while(--size>0);

	return fib_size;	
}

目前把 encoder 套用到 fibdrv.c 上出現了錯誤，已修改型別使的以每個 32-bits digits 來做 BytesModify 處理，但我觀察核心 log 還是出現記憶體存取的錯誤如下(1~6行)：














Jun 13 00:15:58 casserly-System-Product-Name kernel: [116287.439301] sizeof 4 8 8  
Jun 13 00:15:58 casserly-System-Product-Name kernel: [116287.439305] before ByteModify  
Jun 13 00:15:58 casserly-System-Product-Name kernel: [116287.439306] Before Leading_zero 
Jun 13 00:15:58 casserly-System-Product-Name kernel: [116287.439311] BUG: unable to handle page fault for address: fffffffffffffffc
Jun 13 00:15:58 casserly-System-Product-Name kernel: [116287.439312] #PF: supervisor read access in kernel mode
Jun 13 00:15:58 casserly-System-Product-Name kernel: [116287.439313] #PF: error_code(0x0000) - not-present page
Jun 13 00:15:58 casserly-System-Product-Name kernel: [116287.439314] PGD 747c15067 P4D 747c15067 PUD 747c17067 PMD 0 
Jun 13 00:15:58 casserly-System-Product-Name kernel: [116287.439317] Oops: 0000 [#31] SMP PTI
Jun 13 00:15:58 casserly-System-Product-Name kernel: [116287.439319] CPU: 7 PID: 68800 Comm: client Tainted: G      D    OE     5.13.0-44-generic #49~20.04.1-Ubuntu
Jun 13 00:15:58 casserly-System-Product-Name kernel: [116287.439322] Hardware name: System manufacturer System Product Name/PRIME Z270M-PLUS, BIOS 0607 03/23/2017
Jun 13 00:15:58 casserly-System-Product-Name kernel: [116287.439323] RIP: 0010:fib_read+0x1ba/0x262 [fibdrv]
Jun 13 00:15:58 casserly-System-Product-Name kernel: [116287.439327] Code: 85 c0 75 0c 48 c7 c7 00 b9 b2 c0 e8 ec 9f 27 db 31 f6 48 c7 c7 1a b9 b2 c0 e8 de 9f 27 db 48 c7 c7 31 b9 b2 c0 e8 d2 9f 27 db <41> 8b 37 85 f6 75 12 48 c7 c7 49 b9 b2 c0 e8 bf 9f 27 db 41 c6 06
Jun 13 00:15:58 casserly-System-Product-Name kernel: [116287.439329] RSP: 0018:ffffafabc2a2fdd0 EFLAGS: 00010246

已解決，在 fib_size = 0 的情況下還是要 kmalloc 一個 char * 來存放數值 0x00

解決問題後透過 encoder 將資料複製到 buffer 裡傳送到 user space 做 decode ，但是經過分析 Bytes 數後發現白忙一場，因為需要複製的 Bytes 數在費波那契數列值大的時候甚至比一開始未　encode 的 Bignum_64bits 還多，如下圖所示 :sweat_smile: ：

performance 則是如下圖：

看起來這個編碼並沒有發揮他的優勢，大部分的情況一個 32 bits 的 digits 數值都會超過

2^{28} - 1

，這樣的情況下 4 個 Bytes 的資料就需要用 5 個 Bytes 去做儲存。在數列約為fib(800)之後需要使用的 Bytes 數就越差越大。看起來不太適合費波那契數列數值壓縮，要再試試其他數值壓縮方法。
加入 BCD 編碼出來的 Bytes 數來看，使用 BCD 來表示既簡單而且壓縮率(為CharBytes 的

1 / 2

) 發現與 VariableBytes 相仿重疊：

Fib(n)	BignumBinary	BCDcode	VariableBytes
n=10	8	1	2
n=50	8	5	6
n=100	16	10	12
n=200	24	21	23
n=300	32	31	34
n=400	40	42	44

目前暫時想不到如何更有效的壓縮 BignumBinary ，因為目前直接將 BignumBinary 傳送到 UserSpace 之後再做十進位解碼即可。至於有觀摩 scottxxxabc 使用 clz 來計算 bignum[max_idx] 來減少 copy_to_user 的 bytes 數，這樣的確會減少 bytes 數，但是依照遞增差不多就是減少 ( 0 ~ 7個 Bytes ; uint_64t ) 效益並不是很大。

嘗試使用 POSIX Thread 達到多執行緒存取

由於目前的 Bignum 都是以 fast doubling 計算並透過 copy_to_user 回傳至 buffer 陣列，所以各執行緒之間並沒有共享變數。
以下透過 pthread 來建立五個執行緒：

#include <pthread.h>
//...

#define NUM_THREADS 5

typedef struct  thread_ID thid;
struct thread_ID{
        int PID;
        int count;
    };

void *Fib_count(void * threadnum){


    thid *b ;
    b = (thid *)threadnum;
    
    int fd = open(FIB_DEV, O_RDWR);
    int offset = b->count;
    int id = b->PID;
    long long sz;

    for (int i = 0; i <= offset; i++) {
            char buf[4096];       
            sz = read(fd, buf, i);
            printf("Reading from pid : %d " FIB_DEV
                " at offset %d, returned the sequence "
                "%s.\n",
                id,i,buf);
    }
}


int main()
{
    
    // ....
    
    struct thread_ID threadlist[NUM_THREADS];

    for(int i = 0; i< NUM_THREADS;i++){
        //struct thread_ID a;
        threadlist[i].count = offset;
        threadlist[i].PID = i;
            
        pthread_create(&threads[i],NULL,Fib_count,(void *)&threadlist[i]);
    }

    
}

所以結果跟我們想的一樣，值得一提的是假如我們將程式 taskset 固定在單個 CPU 上則每個 Thread 就會按照列隊順序執行 fib_count ：

Reading from pid : 0 /dev/fibonacci at offset 0, returned the sequence 0.
Reading from pid : 0 /dev/fibonacci at offset 1, returned the sequence 1.
Reading from pid : 0 /dev/fibonacci at offset 2, returned the sequence 1.
Reading from pid : 0 /dev/fibonacci at offset 3, returned the sequence 2.
Reading from pid : 0 /dev/fibonacci at offset 4, returned the sequence 3.
Reading from pid : 0 /dev/fibonacci at offset 5, returned the sequence 5.
Reading from pid : 0 /dev/fibonacci at offset 6, returned the sequence 8.
Reading from pid : 1 /dev/fibonacci at offset 0, returned the sequence 0.
Reading from pid : 0 /dev/fibonacci at offset 7, returned the sequence 13.
Reading from pid : 1 /dev/fibonacci at offset 1, returned the sequence 1.
Reading from pid : 1 /dev/fibonacci at offset 2, returned the sequence 1.
Reading from pid : 0 /dev/fibonacci at offset 8, returned the sequence 21.
Reading from pid : 0 /dev/fibonacci at offset 9, returned the sequence 34.
Reading from pid : 1 /dev/fibonacci at offset 3, returned the sequence 2.
Reading from pid : 0 /dev/fibonacci at offset 10, returned the sequence 55.
Reading from pid : 1 /dev/fibonacci at offset 4, returned the sequence 3.
Reading from pid : 1 /dev/fibonacci at offset 5, returned the sequence 5.
Reading from pid : 1 /dev/fibonacci at offset 6, returned the sequence 8.
Reading from pid : 1 /dev/fibonacci at offset 7, returned the sequence 13.
Reading from pid : 1 /dev/fibonacci at offset 8, returned the sequence 21.
Reading from pid : 1 /dev/fibonacci at offset 9, returned the sequence 34.
Reading from pid : 1 /dev/fibonacci at offset 10, returned the sequence 55.
Reading from pid : 3 /dev/fibonacci at offset 0, returned the sequence 0.
Reading from pid : 3 /dev/fibonacci at offset 1, returned the sequence 1.
Reading from pid : 3 /dev/fibonacci at offset 2, returned the sequence 1.
Reading from pid : 3 /dev/fibonacci at offset 3, returned the sequence 2.
Reading from pid : 4 /dev/fibonacci at offset 0, returned the sequence 0.
Reading from pid : 3 /dev/fibonacci at offset 4, returned the sequence 3.
Reading from pid : 4 /dev/fibonacci at offset 1, returned the sequence 1.
Reading from pid : 3 /dev/fibonacci at offset 5, returned the sequence 5.
Reading from pid : 4 /dev/fibonacci at offset 2, returned the sequence 1.
Reading from pid : 3 /dev/fibonacci at offset 6, returned the sequence 8.
Reading from pid : 4 /dev/fibonacci at offset 3, returned the sequence 2.
Reading from pid : 3 /dev/fibonacci at offset 7, returned the sequence 13.
Reading from pid : 4 /dev/fibonacci at offset 4, returned the sequence 3.
Reading from pid : 3 /dev/fibonacci at offset 8, returned the sequence 21.
Reading from pid : 4 /dev/fibonacci at offset 5, returned the sequence 5.
Reading from pid : 4 /dev/fibonacci at offset 6, returned the sequence 8.
Reading from pid : 3 /dev/fibonacci at offset 9, returned the sequence 34.
Reading from pid : 4 /dev/fibonacci at offset 7, returned the sequence 13.
Reading from pid : 3 /dev/fibonacci at offset 10, returned the sequence 55.
Reading from pid : 4 /dev/fibonacci at offset 8, returned the sequence 21.
Reading from pid : 4 /dev/fibonacci at offset 9, returned the sequence 34.
Reading from pid : 4 /dev/fibonacci at offset 10, returned the sequence 55.
Reading from pid : 2 /dev/fibonacci at offset 0, returned the sequence 0.
Reading from pid : 2 /dev/fibonacci at offset 1, returned the sequence 1.
Reading from pid : 2 /dev/fibonacci at offset 2, returned the sequence 1.
Reading from pid : 2 /dev/fibonacci at offset 3, returned the sequence 2.
Reading from pid : 2 /dev/fibonacci at offset 4, returned the sequence 3.
Reading from pid : 2 /dev/fibonacci at offset 5, returned the sequence 5.
Reading from pid : 2 /dev/fibonacci at offset 6, returned the sequence 8.
Reading from pid : 2 /dev/fibonacci at offset 7, returned the sequence 13.
Reading from pid : 2 /dev/fibonacci at offset 8, returned the sequence 21.
Reading from pid : 2 /dev/fibonacci at offset 9, returned the sequence 34.
Reading from pid : 2 /dev/fibonacci at offset 10, returned the sequence 55.

一旦可有效處理多執行緒的 client 端要求，接著就能在 fibdrv 實作 LRU，將之前的計算結果保存下來，並利用 fast doubling 的特性 (用第 N 項快速計算第 2N 項)，從而省去大量的計算。不過，使用 LRU 的話，就要解決同步處理議題。
:notes: jserv

使用 LRU 快取策略來加速 fib_drv 的執行

LRU(Least Recently Used Cache)，是一種快取策略，將最近用到的資料放在串列前面，最近越沒用到的放在快取串列後面，當快取串列滿的時候就會將最後一個資料移除，接著把新的資料存在串列第一個。 LeetCode 參考
由於 double linked list 的搜尋存取效率為

O (n)

效率不好，因此常常會透過一個 hash maps 來達到好的存取效率。
因此，我們可以從第一周練習題的 hlist_node 的想法來建構一個 hash map ，再透過 list_head 建立雙向鏈結串列實作。

//hashmap.h ================================================================

#ifndef _HASH_H_
#define _HASH_H_
#include <linux/kernel.h>
#include "bn.h"
#include <linux/types.h>
#endif

typedef struct hlist_node hlist_node;
typedef struct hlist_head hlist_head;
typedef struct list_head list_head;


typedef struct {
    int map_size;
    hlist_head *head;
}hmap;

typedef struct{
    int key;
    bn *fib;
    hlist_node *hnode;
    list_head *lnode;
}hash_key;



int map_init(hmap *map,int size);
int hash(int key, int size);
hash_key *key_find(hmap *map,int key);
hash_key *search_and_update(hmap *map, int key, list_head *head);
void hlist_node_add(hmap *map, int key,list_head *lhead, bn *result,int list_size);

int list_count(list_head *head);
bool list_isfull(list_head *head, int list_size);
void hash_key_del(hash_key *node);
void map_deinit(hmap *map);

// hashmap.c ===============================================================

#include "hashmap.h"
#include <linux/list.h>
#include <linux/slab.h>

int map_init(hmap *map,int size){

    //hmap *map = kmalloc(sizeof(struct hmap) , GFP_KERNEL);
    if (!map){
        printk(KERN_INFO " map_init error \n");
        return 0;
    }

    struct hlist_head *head = kmalloc(sizeof(struct hlist_head)*size,GFP_KERNEL);
    if (!head){
        printk(KERN_INFO " map_init error \n");
        return 0;
    }
    int temp;
    hlist_head *ptr = head;
    for(temp=0;temp<size;ptr++){
        INIT_HLIST_HEAD(ptr);
    }
    map->map_size = size;
    map->head = head;

    return 1;
}

int hash(int key,int size){

    int result = key % size ;
    return result;
}


hash_key *key_find(hmap *map,int key){

        
        int hash_v = hash(key,map->map_size);

        struct hlist_head *target = (map->head)+hash_v;
        hlist_node *temp = target->first;
        while(temp != NULL){
            hash_key *hash_val = container_of(&temp,typeof(hash_key),hnode);
            if(hash_val->key == key)
                return hash_val;
            temp = temp->next;
        }
        return NULL;
}
hash_key *search_and_update(hmap *map, int key, list_head *head){

    hash_key *result = key_find(map, key);
    if(!result){
        printk(KERN_ALERT "not in cache");
        //node_add(map->head, key, head , unknown );//add new struct hash_key 
        return NULL;
    }
    list_move(result->lnode,head); //delete node and add to head;
    return result;
}



void hlist_node_add(hmap *map,int key,list_head *Lhead,bn *result,int list_size){ //new hash_key {hlist_node list_head,data bn}

    int hash_idx = hash(key, map->map_size);
    hlist_head *Hhead = map->head + hash_idx;
    hlist_node *temp = Hhead->first;
    
    hash_key *hash_val =kmalloc(sizeof(hash_key),GFP_KERNEL);
    
    if(list_isfull(Lhead,list_size)){
        
        
        hash_key *temp_del = container_of(&Lhead->prev, typeof(hash_key), lnode);
        //list_del(lhead->prev);
        //hlist_node_release(temp_del->hnode);
        //hlist_del(temp_del->hnode);
        hash_key_del(temp_del);
    }


    hlist_node *node = kmalloc(sizeof(hlist_node),GFP_KERNEL);
    list_head *list_temp = kmalloc(sizeof(list_head),GFP_KERNEL);
    
    hash_val->key = key;
    hash_val->hnode = node;
    hash_val->lnode = list_temp;
    hash_val->fib = result;

    hlist_add_head(node, Hhead);
    list_add(hash_val->lnode,Lhead);
        //head->first = node;
        //node->next = NULL;
        //node->pprev = NULL;



    return;

}
int list_count(list_head *head){
    list_head *temp;
    int count =0;
    list_for_each(temp,head)
        count++;
    
    return count;
}

bool list_isfull(list_head *head, int list_size){

    int count = list_count(head);
    if(count>=list_size)
        return true;
    
    return false;
}

void hash_key_del(hash_key *node){


    list_del_init(node->lnode);          //release list_head pointer
    //hlist_node_release(node->hnode);//release hlist_node pointer
    hlist_del_init(node->hnode);
    bn *bn_temp = node->fib;
    node->fib =NULL;
    kfree(bn_temp);
    kfree(node);
    return;
}


void map_deinit(hmap *map){

    if(!map)
        return;
    int i;
    hlist_head *htemp = map->head;
    for(i=0;i<map->map_size;htemp++){

        hlist_node *node = htemp->first;
        while(node!=NULL){
             hash_key *key_node = container_of(&node, hash_key, hnode);
             //list_release(key_node->lnode);
             //list_del(key_node->lnode);
             //hlist_del(key_node->hnode);
             hash_key_del(key_node);
             //list_head_free
        }
    
    }
    kfree(map->head);
    kfree(map);
}

然後目前我在思考我的 cache 大小要設多大比較好，目前設為 50 個 fib 數值。

debug 的時候遇到問題，就是掛載上 kernel 之後導致系統 crash ，我猜是記憶體釋放或是存取到其他不該存取的位置，但這邊不曉得要怎摸 debug 比較好 :sweat_smile: