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 只給程式用
  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 →
- After: 排除效能分析干擾，限定 CPU 只給程式用
  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 →

費氏數列

費氏數列
$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參數）