2022q1 Homework3 (fibdrv)

contributed by < Korin777 >

Linux 效能分析

限定 CPU 給特定的程式使用

在 /etc/default/grub 中新增 isolcpus 參數

GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=1"

更新 /boot/grub/grub.cfg
```
$ sudo update-grub
```
重新開機
檢查是否生效
- 查看 /proc/cmdline 裡是否有 isolcpu 參數
  
  korin@korin-VivoBook-15-ASUS-Laptop-X542UF:~$ cat /proc/cmdline
  BOOT_IMAGE=/boot/vmlinuz-5.13.0-30-generic root=UUID=0316da8c-1a94-4511-a7fc-a5133651768b ro quiet splash isolcpus=1 vt.handoff=7

最後用 taskset 查看 process 的 cpu affinity ，可以發現它已經不能在第一個 cpu 執行了

korin@korin-VivoBook-15-ASUS-Laptop-X542UF:~$ taskset -p 1
pid 1's current affinity mask: fd

排除干擾效能分析的因素

抑制 address space layout randomization (ASLR)
- 確保每次程式以及動態函式庫的載入位置都相同
```
$ sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
```
設定 scaling_governor 為 performance
- cpufreq 是一個動態調整 cpu 頻率的模組，系統啟動時生成一個資料夾 /sys/devices/system/cpu/cpu0/cpufreq/，裡面有幾個檔案，scalin_governor 代表 cpu 頻率調整模式，用它來控制 CPU 頻率，設為 performance 表示將 CPU 頻率固定工作在其支援的最高執行頻率上，而不動態調節
```
for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
do
    sudo echo performance > ${i}
done
```
針對 Intel 處理器，關閉 turbo mode
- Intel CPU 有個 Turbo Boost 功能，當應用程式需要較高的運算效能時，可以以高於額定頻率執行，我們要避免上述情況
```
$ sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
```
經過以上處理後，比較計算費式數列對時間的作圖，可以發現執行時間比較沒有突然衝很高的情況，可以看作每次測量執行時間都比較沒有被外在因素影響
- Before: 沒有排除效能分析干擾，沒有限定 CPU 只給程式用
- After: 排除效能分析干擾，限定 CPU 只給程式用

費氏數列

費氏數列
$F (n$ ) 可透過
$F (n / 2)$ 及
$F (n / 2 + 1)$ 求得，而在
$n$ 為奇數及偶數的算法分別如下
- $F (2 k) = F (k) [2 F (k + 1) - F (k)]$
- $F (2 k + 1) = F (k + 1)^{2} + F (k)^{2}$
當我們有
$(a, b) = (F (n / 2), F (n / 2) + 1)$ ，根據上面兩個式子即可算出
$(c, d) = (2 * a * b - a * a, a * a + b * b)$ ，考慮
$n$ 以下情況
- $n$ 為奇數 =>
  $(c, d) = (F (n - 1), F (n))$
- $n$ 為偶數=>
  $(c, d) = (F (n), F (n + 1))$
可以發現當
$n$ 為奇數，我們會得到
$F (n - 1)$ 及
$F (n)$ ，因此若要在算出
$F (2 n)$ ，我們得再算出
$F (n + 1)$ ，而
$n$ 為奇數則變為如下
- $n$ 為奇數 =>
  $(d, c + d) = (F (n), F (n + 1))$
透過上面式子，假設要計算
$F (11)$ ，我們只要透過
$F (5) 、 F (6) => F (2) 、 F (3) => F (1) 、 F (2)$
對照
$F (11)$ ， 11₁₀ = 1011₂

i	start	4	3	2	1	result
n	-	1011	1011	1011	1011	-
F(n)	F(0)	F(0*2+1)	F(1*2)	F(2*2+1)	F(5*2+1)	F(11)
F(n) = a	F(0)=0	1	1	5	89	89
F(n+1) = b	F(1)=1	1	2	8	144
F(2n),F(2n+1)	-	奇數(d,c+d)	偶數(c,d)	奇數(d,c+d)	奇數(d,c+d)

透過以上公式，可以寫出以下程式來計算費伯納西數 n
可以透過 63 - __builtin_clzll(n) 來代替迴圈求出 n 要除以 2 多少次才等於 0

unsigned long long fib(unsigned long long n) {
    int start = 63 - __builtin_clzll(n);
    unsigned long long int bit = 1ULL << (start), a = 0, b = 1,c,d;
    while(bit) {
        c = 2*a*b - a*a, d = a*a + b*b;
        if(n & bit) {
            a = d, b = c + d;
        }
        else {
            a = c, b = d;
        }
        bit >>= 1;
    }
    return a;
}

減少乘法運算的成本

計算費式數列的過程中，可以發現要求出 c,d 需要大量的乘法運算

c = 2*a*b - a*a, d = a*a + b*b;

運用位移的方式將乘法運算改為加法，可以實作出一個只需要加減及為移的 fib 函式

c = (mul(a,b) << 1ULL) - sqare(a), d = sqare(a) + sqare(b);

unsigned long long mul(unsigned long long a, unsigned long long b) {
    unsigned long long ans = 0ULL;
    for(int i = 0 ; i < 64; ++i) {
        if(b & (1ULL << i))
            ans += a << i; 
    }
    return ans;
}
unsigned long long sqare(unsigned long long x) {
    unsigned long long ans = 0ULL;
    for(int i = 0 ; i < 64; ++i) {
        if(x & (1ULL << i))
            ans += x << i; 
    }
    return ans;
}

大數運算

正確計算
$F (93)$ 以及其後的值

在計算

F (93)

時，因為結果超過 64 位元所能表示的數，得定義新的資料結構來儲存，並改寫 fib_sequence

struct BigN{
    unsigned long long lower, higher;
};
static struct BigN fib_sequence(long long k)
{
    struct BigN f[k + 2];
    f[0].lower = f[0].higher = f[1].higher = 0;
    f[1].lower = 1;
    for (int i = 2; i <= k; i++) {
        f[i].lower = f[i - 1].lower + f[i - 2].lower;
        f[i].higher = f[i - 1].higher + f[i - 2].higher + (f[i].lower < f[i - 1].lower || f[i].lower < f[i - 2].lower);
    }
    return f[k];
}

參考 KYG-yaya573142 的報告，透過字串的方式，將大數以 10 進位的方式印出來
將大數以 2 進位的觀點轉成 10 進位，假設有一 10 進位數 num 初始為 0 ，將大數從高位元到低位元，每次將 num 乘以 2 且若遇到 1 就將 num 加 1 ，最後即可將此數轉為 10 進位
對照 40₁₀ = 101000₂

i	start = 6	5	4	3	2	1	result
n(2進位)	101000	101000	101000	101000	101000	101000	-
n(10進位)	0	1	2	5	10	20	40
下一個數	0*2+1	1*2	2*2+1	5*2	10*2	20*2	-

前兩層 for 迴圈即是將大數從 2 進位轉成 10 進位
最後一層 for 迴圈用來找出 10 進位數的開頭
kmalloc 定義於 linux/slab.h ，用來配置核心的記憶體空間

char* displayBigN(struct BigN b) {
    char *num = kmalloc(41,GFP_KERNEL);
    memset(num,'0',40);
    num[40] = '\0';
    int carry;
    for(unsigned long long i = 1ULL << 63; i; i >>= 1) {
        carry = (b.higher & i) > 0;
        for(int j = 39; j >= 0; j--) {
            num[j] += ((num[j] - '0') + carry);
            if(num[j] > '9') {
                num[j] -= 10;
                carry = 1; 
            }
            else
                carry = 0;                
        }
    }
    for(unsigned long long i = 1ULL << 63; i; i >>= 1) {
        carry = (b.lower & i) > 0;
        for(int j = 39; j >= 0; j--) {
            num[j] += ((num[j] - '0') + carry);
            if(num[j] > '9') {
                num[j] -= 10;
                carry = 1; 
            }
            else
                carry = 0;                
        }
    }
    int i = 0;
    for(;i < 39 && num[i] == '0';++i); 
    return &num[i];
}

如果我們要用這個資料結構，運用 fast doubling 的手法計算費伯那西數，我們得另外實做用於此資列結構的 +,-,*,<< 1

先將 lower 相加，在將 higher 相加並加上 lower 的進位

struct BigN* add(struct BigN a, struct BigN b) {
    struct BigN *c = kmalloc(sizeof(struct BigN),GFP_KERNEL);
    c->lower = a.lower + b.lower;
    c->higher = a.higher + b.higher + (c->lower < a.lower || c->lower < b.lower);
    return c;
}

將減數取 2 補數再與被減數相加

struct BigN* sub(struct BigN a, struct BigN b) {
    struct BigN *c;
    b.lower = ~b.lower+1;
    b.higher = ~b.higher + (b.lower == 0);
    c = add(a,b);
    return c;
}

先將 lower 轉型成 unsigned __int128 並相乘，避免 overflow ，結果的較低 64 位元即是新的 lower ，較高 64 位元進位到 higher
分別將一數的 higher 乘以另一數的 lower 並相加，在將上之前的進位，即為新的 higher
higher 乘以 higher 因無法儲存於此資料結構，暫時不處理

struct BigN* mul(struct BigN a, struct BigN b) {
    struct BigN *c = kmalloc(sizeof(struct BigN),GFP_KERNEL);
    unsigned __int128 tmp = (unsigned __int128)a.lower * (unsigned __int128)b.lower;
    c->lower = (unsigned long long)tmp;
    c->higher = a.lower * b.higher + a.higher * b.lower + (unsigned long long)(tmp >> 64);
    return c;
}

<< 1

先將 higher 左移並加上 lower 的最高位元，在將 lower 左移

void lshfit(struct BigN *a) {
    a->higher = (a->higher << 1) + (a->lower >> 63 & 1ULL);
    a->lower = a->lower << 1;
}

修改實作 fast doubling 的 fib

struct BigN fib(unsigned long long n) {
    int start = 63 - __builtin_clzll(n);
    unsigned long long int bit = 1ULL << (start);
    struct BigN a, b;
    struct BigN *v1, *v2, *v3,*c,*d;
    a.lower = a.higher = b.higher = 0;
    b.lower = 1;
    while(bit) {
        v1 = mul(a,b);
        lshfit(v1);
        v2 = mul(a,a);
        v3 = mul(b,b);
        c = sub(*v1,*v2);
        d = add(*v2,*v3);
        kfree(v1);
        kfree(v2);
        kfree(v3);
        if(n & bit) {
            a = *d, b = *add(*c,*d);
        }
        else {
            a = *c, b = *d;
        }
        bit >>= 1;
    }
    return a;
}

透過這個資料結構，我們可以表示
$0$ ~
$2^{128} - 1$ ，就可以正確計算到
$F (186) = 332825110087067562321196029789634457848$

改寫 BigN 來計算更大的費伯納西數

為了計算出更大的費伯納西數，將 BigN 的 higher 及 lower 更改為 *digits ，可以根據我們想儲存的數字大小，動態配置記憶體， size 則用來表示數字真正用到的記憶體大小(幾個 unsigned long long)

struct BigN{
    unsigned long long *digits;
    unsigned long long size;
};

改寫 fib_sequence
- 這裡將 f[k + 2] 改為 f1,f2 及 tmp ， f1,f2 用來保留前兩個費伯那西數， tmp 則用來更換新的 f1,f2

static struct BigN* fib_sequence(unsigned long long k)
{
    struct BigN *f1, *f2, *tmp;
    f1 = malloc(sizeof(struct BigN));
    f2 = malloc(sizeof(struct BigN));
    f1->digits = malloc(sizeof(unsigned long long));
    f2->digits = malloc(sizeof(unsigned long long));
    f1->digits[0] = 0;
    f1->size = f2->size = f2->digits[0] = 1;
    unsigned long long overflow;
    for (int i = 2; i <= k; i++) {
        int carry = 0;
        for(int j = 0; j < f1->size; j++) {
            overflow = f1->digits[j];
            f1->digits[j] += f2->digits[j] + carry;
            carry = f1->digits[j] < overflow;
        }
        unsigned long long f = 0;
        int inc = 1;
        if(f1->size != f2->size) {
            overflow = f = f2->digits[f2->size-1];
            f += carry;
            carry = f < overflow;
            ++inc;
        }
        if(carry) {
            f1->digits = realloc(f1->digits,sizeof(unsigned long long) *(f1->size+inc));
            f1->size += inc;
            f1->digits[f1->size-1] = 1;
            if(f)
                f1->digits[f1->size-2] = f;
        }
        if(!carry && f) {
            f1->digits = realloc(f1->digits,sizeof(unsigned long long) *(f1->size+1));
            f1->size += 1;
            f1->digits[f1->size-1] = f;
        }
        tmp = f2;
        f2 = f1;
        f1 = tmp;
    }
    if(k==0) {
        tmp = f2;
        f2 = f1;
        f1 = tmp;
    }
    free(f1->digits);
    free(f1);
    return f2;
}

改寫 displayBigN

char *displayBigN(struct BigN *b)
{
    char *num = kmalloc(sizeof(char) * (b->size * 20) + 1, GFP_KERNEL);
    unsigned long long len = sizeof(char) * (b->size * 20) + 1;
    memset(num, '0', len);
    num[len - 1] = '\0';
    int carry;
    // convert number from base-2 to base-10
    for (int k = b->size - 1; k >= 0; --k) {
        for (unsigned long long i = 1ULL << 63; i; i >>= 1) {
            carry = (b->digits[k] & i) > 0;
            for (int j = len - 2; j >= 0; j--) {  // update num
                num[j] += ((num[j] - '0') + carry);
                if (num[j] > '9') {
                    num[j] -= 10;
                    carry = 1;
                } else
                    carry = 0;
            }
        }
    }
    // skip leading 0
    int i = 0;
    for (; i < len - 2 && num[i] == '0'; ++i)
        ;
    char *retnum = kmalloc(sizeof(char) * (len - i), GFP_KERNEL);
    memcpy(retnum, &num[i], sizeof(char) * (len - i));
    kfree(num);
    return retnum;
}

struct BigN* add(struct BigN *f1, struct BigN *f2) {
    struct BigN *c = malloc(sizeof(struct BigN)), *large, *small;
    int carry = 0, j;
    if(f1->size > f2->size) 
        large = f1, small = f2;
    else 
        large = f2, small = f1;
    c->digits = malloc(sizeof(unsigned long long)*(large->size+1));

    for(j = 0; j < small->size; j++) {
        c->digits[j] = small->digits[j] + large->digits[j] + carry;
        carry = c->digits[j] < small->digits[j];
    }
    for(; j < large->size; j++) {
        c->digits[j] = large->digits[j] + carry;
        carry = c->digits[j] < large->digits[j];
    }
    c->digits[j] = carry;
    c->size = large->size + carry;

    return c;
}

透過 add 函式改寫 fib_sequence

static struct BigN* fib_sequence(unsigned long long k)
{
    struct BigN *f1, *f2, *tmp;
    f1 = malloc(sizeof(struct BigN)), f2 = malloc(sizeof(struct BigN));
    f1->digits = malloc(sizeof(unsigned long long)), f2->digits = malloc(sizeof(unsigned long long));
    f1->digits[0] = 0, f1->size = f2->size = f2->digits[0] = 1;
    for(int i = 2; i <= k; i++) {
        tmp = add(f1,f2);
        free(f1->digits), free(f1);
        f1 = f2, f2 = tmp;
    }
    if(k == 0)
        tmp = f2, f2 = f1, f1 = tmp;
    free(f1->digits), free(f1);
    return f2;
}

保證 a,b 皆為正數

struct BigN* sub(struct BigN *a, struct BigN *b) {
    struct BigN *c, *tmp = malloc(sizeof(struct BigN)), *large, *small;
    if(a->size > b->size)
        large = a, small = b;
    else
        large = b, small = a;
    tmp->size = large->size, tmp->digits = malloc(sizeof(unsigned long long) * large->size);
    // change b to its 2's complement
    tmp->digits[0] = ~b->digits[0] + 1;
    int i = 1;
    for(; i < b->size; ++i)
        tmp->digits[i] = ~b->digits[i] + (tmp->digits[i-1] == 0);
    for(; i < large->size; ++i)
        tmp->digits[i] = ~0ULL;
    c = add(a,tmp);
    i = large->size - 1;
    c->size = 1;
    for(; i > 0; --i) {
        if(c->digits[i]) {
            c->size = i+1;
            break;
        }
    }
    free(tmp->digits);
    free(tmp);
    return c;
}

struct BigN* mul(struct BigN *a, struct BigN *b) {
    struct BigN *c = malloc(sizeof(struct BigN));
    int size = a->size + b->size;
    c->digits = malloc(sizeof(unsigned long long)*size);
    memset(c->digits,0,sizeof(unsigned long long)*size);
    int *carry = malloc(sizeof(int)*size);
    memset(carry,0,sizeof(int)*size);
    unsigned long long overflow;
    for(int i = 0; i < a->size; ++i) {
        for(int j = 0; j < b->size; ++j) {
            unsigned __int128 tmp = (unsigned __int128)a->digits[i] * (unsigned __int128)b->digits[j];
            int index = i+j;
            overflow = c->digits[index];
            c->digits[index] += (unsigned long long)tmp;
            carry[index] += c->digits[index] < overflow;
            overflow = c->digits[index+1];
            c->digits[index+1] += (unsigned long long)(tmp >> 64);
            carry[index+1] += c->digits[index+1] < overflow;
        }
    }
    for(int i = 0; i < size-1; i++) {
        overflow = c->digits[i+1];
        c->digits[i+1] += carry[i];
        carry[i+1] += c->digits[i+1] < overflow;
    }
    if(c->digits[size-1])
        c->size = size;
    else
        c->size = size -1;
    free(carry);
    return c;
}

<<1

void lshfit(struct BigN *a) {
    int i = a->size - 1;
    if(a->digits[i] >> 63 & 1ULL) {
        a->size += 1;
        a->digits = realloc(a->digits,sizeof(unsigned long long) * (a->size));
        a->digits[a->size-1] = 1; 
    }
    for(; i > 0; --i)
        a->digits[i] = (a->digits[i] << 1) + (a->digits[i-1] >> 63 & 1ULL);
    a->digits[0] <<= 1;
}

改寫實作 fast doubling 的 fib

struct BigN* fib(unsigned long long n) {
    struct BigN *a = malloc(sizeof(struct BigN)), *b = malloc(sizeof(struct BigN)), *v1, *v2, *v3, *c, *d;
    a->digits = malloc(sizeof(unsigned long long)) , b->digits = malloc(sizeof(unsigned long long));
    a->digits[0] = 0;
    a->size = b->size = b->digits[0] = 1;
    if(n == 0) {
        free(b->digits), free(b);
        return a;
    }
    int start = 63 - __builtin_clzll(n);
    unsigned long long int bit = 1ULL << start;
    while(bit) {
        v1 = mul(a,b);
        lshfit(v1);
        v2 = mul(a,a);
        v3 = mul(b,b);
        c = sub(v1,v2);
        d = add(v2,v3);
        free(v1->digits), free(v1), free(v2->digits), free(v2), free(v3->digits), free(v3), 
        free(a->digits), free(a), free(b->digits), free(b);
        if(n & bit)
            a = d, b = add(c,d);
        else
            a = c, b = d;
        bit >>= 1;
    }
    free(b->digits), free(b);
    return a;
}

根據 Other Built-in Functions Provided by GCC ， __builtin_clzll 傳 0 進去為 undefined behavior 所以得特別判斷 n 是否為 0

透過這個改寫過的 BigN ， fib_sequence 及 fib 至少能正確計算到

F (31200)

fast doubling 及 sequence 執行時間

在 kernel space 測量時間
透過 gnuplot 觀察到 sequence 手法執行時間隨著 n 的增大線性成長，而 fast doubling 手法為非線性緩慢上升

與 bignum 實做比較

在 user space 進行 fast doubling 的時間測量
在用 gnuplot 繪圖時，發現還是有許多突然衝高的點，後來透過每個
$F (n)$ 都測量 100 次，並取其中最小值後畫出來的圖比較沒有上述情況了
bignum 的實做比我的實做還要快 3 ～ 4 倍

回傳核心計算的值給使用者

在費伯那西數大於 ssize_t 的情況下，使用者就無法透過 read 的回傳值取得它，因此在進行大數運算時，我們得透過 copy_to_user 的方式，將大數傳給使用者

unsigned long copy_to_user(void *to, const void *from, unsigned long n)
- to:目標地址（使用者空間）
- from:源地址（核心空間）
- n:將要拷貝資料的位元組數

static ssize_t fib_read(struct file *file,char *buf,size_t size,loff_t *offset)
{
    int ret = 0;
    struct BigN *n = fib(*offset);
    char *num = displayBigN(n);
    ret = copy_to_user(buf,num,strlen(num)+1);
    kfree(n), kfree(num);
    return (ssize_t) ret;
}

檢查費氏數列正確性

透過 make check 我們能檢查我們所求的費氏數列是否正確，並將發生錯誤的地方給印出來

將 MakeFile @diff -u out scripts/expected.txt && $(call pass) 註解， expected.txt 裡的
$f i b (93)$ ~
$f i b (100)$ 是錯誤的並非我們想要的值
跟據想計算到費伯那西數修改 fibdrc.c 的 MAX_LENG 、 client.c 的 offset 及 verify.py 的 range(2, 101)

korin@korin-VivoBook-15-ASUS-Laptop-X542UF:~/Desktop/linux2022/fibdrv$ make check 
make -C /lib/modules/5.13.0-30-generic/build M=/home/korin/Desktop/linux2022/fibdrv modules
make[1]: Entering directory '/usr/src/linux-headers-5.13.0-30-generic'
make[1]: Leaving directory '/usr/src/linux-headers-5.13.0-30-generic'
make unload
make[1]: Entering directory '/home/korin/Desktop/linux2022/fibdrv'
sudo rmmod fibdrv || true >/dev/null
rmmod: ERROR: Module fibdrv is not currently loaded
make[1]: Leaving directory '/home/korin/Desktop/linux2022/fibdrv'
make load
make[1]: Entering directory '/home/korin/Desktop/linux2022/fibdrv'
sudo insmod fibdrv.ko
make[1]: Leaving directory '/home/korin/Desktop/linux2022/fibdrv'
sudo ./client > out
make unload
make[1]: Entering directory '/home/korin/Desktop/linux2022/fibdrv'
sudo rmmod fibdrv || true >/dev/null
make[1]: Leaving directory '/home/korin/Desktop/linux2022/fibdrv'
# @diff -u out scripts/expected.txt && env printf "\e[32;01m Passed [-]\e[0m\n"
f(187) fail
input: 198239973509362327032045173661212819077
expected: 538522340430300790495419781092981030533

參考資料

CPU 優化建議使用 cpupower 設定 CPU Performance 模式
 isolcpu參數隔離cpu使其不被自動調度（linux 修改boot參數）