tags: `Linux 核心設計 2022`

2022q1 Homework3 (fibdrv)

contributed by < DokiDokiPB >

實驗環境

Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          20
On-line CPU(s) list:             0-19
Thread(s) per core:              1
Core(s) per socket:              14
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           154
Model name:                      12th Gen Intel(R) Core(TM) i7-12700H
Stepping:                        3
CPU MHz:                         612.719
CPU max MHz:                     6000.0000
CPU min MHz:                     400.0000
BogoMIPS:                        5376.00
Virtualization:                  VT-x
L1d cache:                       336 KiB
L1i cache:                       224 KiB
L2 cache:                        8.8 MiB
NUMA node0 CPU(s):               0-19

附註： intel 第 12 代 CPU 可以關閉 E Core

fibonacci 實作

fast doubling method

在 Calculating Fibonacci Numbers by Fast Doubling 網誌中，提及 fast doubling 手法

$F i b (2 k) = F i b (k) [2 F i b (k + 1) - F i b (k)]$
$F i b (2 k + 1) = F i b (k + 1)^{2} + F i b (k)^{2}$

例如

F i b (10)

的計算過程，以 top-down 方法去觀察

F i b (10) \to F i b (5) \to F i b (2) \to F i b (1) \to F i b (0)

使用第一第二計算方法是取決當下

F i b (n)

的 n 是否為偶數

$F i b (10) \to F i b (5)$ ，使用規則一
$F i b (5) \to F i b (2)$ ，使用規則二
$F i b (2) \to F i b (1)$ ，使用規則一
$F i b (1) \to F i b (0)$ ，使用規則二

使用 bottom-up 手法去觀察其對應關係

乘 2 即左移一項 k << 1，因此可以理解為從 F(0) 開始，經過以下 4 個步驟可以得到 F(10)，這也是為何 fast doubling 實作上會根據 bit 來決定計算的步驟
(0000 << 1) + 1 = 0001
(0001 << 1) + 0 = 0010
(0010 << 1) + 1 = 0101
(0101 << 1) + 0 = 1010

引用自 KYG-yaya573142 作者

i	start	4	3	2	1	result
n	-	1010	1010	1010	1010	-
F(m)	F(0)	F(0*2+1)	F(1*2)	F(2*2+1)	F(5*2)	F(10)
a	0	1	1	5	55	55
b	1	1	2	8	89	-

圖表引用自 2022 年 Linux 核心設計/實作課程作業 —— fibdrv - HackMD

引用 Calculating Fibonacci Numbers by Fast Doubling 文章底部的實作

long long fibseq_basic_fast_doubling_branch(unsigned int offset)
{
    unsigned long long h = 0;
    for (int i = offset; i; i >>= 1, h++)
        ;

    unsigned long long a = 0, b = 1;  // fib(0), fib(1)

    for (unsigned long long mask = 1 << (h - 1); mask; mask >>= 1) {
        unsigned long long c = a * (2 * b - a);
        unsigned long long d = a * a + b * b;
        if (mask & offset) {
            a = d;
            b = c + d;
        } else {
            a = c;
            b = d;
        }
    }

    return a;
}

使用 __builtin_clz 的改進實作

long long fibseq_basic_fast_doubling_branch(unsigned int offset)
{
    unsigned long long mask = ULLONG_MAX ^ (ULLONG_MAX >> 1);
    mask >>= __builtin_clz(offset);

    unsigned long long a = 0, b = 1;  // fib(0), fib(1)
    for (; mask; mask >>= 1) {
        unsigned long long c = a * (2 * b - a);
        unsigned long long d = a * a + b * b;

        if (mask & offset) {
            a = d;
            b = c + d;
        } else {
            a = c;
            b = d;
        }
    }

    return a;
}

其中 unsigned long long mask = ULLONG_MAX ^ (ULLONG_MAX >> 1); 為將最高位元設為 1
使用 bitwise 的技巧，再改寫成以下程式碼

long long fibseq_basic_fast_doubling_branchless(unsigned int offset)
{
    unsigned long long mask = ULLONG_MAX ^ (ULLONG_MAX >> 1);
    mask >>= __builtin_clz(offset);

    unsigned long long a = 0, b = 1;  // fib(0), fib(1)
    for (; mask; mask >>= 1) {
        unsigned long long c = a * (2 * b - a);
        unsigned long long d = a * a + b * b;

        int aset = !(mask & offset);
        int bset = !!(mask & offset);
        a = d ^ ((c ^ d) & -aset);
        b = d + (c & -bset);
    }

    return a;
}

在 user space 中測試程式碼

考量上述的 fast doubling 手法，分為是否使用 bitwise 技巧的實作。在 user space 測試是否有差異。
新增 fibseq.h, fibseq.c，用於實作上述使用 branch 與 branchless 的程式碼、新增 uclient.c ，實作如下：

#include <stdio.h>
#include <time.h>
#include "fibseq.h"

#define NANOSECOND(x) ((x).tv_sec * 1e9 + (x).tv_nsec)
int main()
{
    for (int i = 0; i < 1000; i++) {
        struct timespec t1, t2, t3;
        clock_gettime(CLOCK_MONOTONIC, &t1);
        long long ret1 = fibseq_basic_fast_doubling_branch(i);

        clock_gettime(CLOCK_MONOTONIC, &t2);
        long long ret2 = fibseq_basic_fast_doubling_branchless(i);
        clock_gettime(CLOCK_MONOTONIC, &t3);

        long long ut = (long long) (NANOSECOND(t2) - NANOSECOND(t1));
        long long ut2 = (long long) (NANOSECOND(t3) - NANOSECOND(t2));
        printf("%d %lld %lld %d\n", i, ut, ut2, ret1 == ret2);
    }
    return 0;
}

在 MakeFile 中新增 make uclient 指令

uclient: uclient.c fibseq.c
	$(CC) -o $@ $^

新增 gnuplot 檔案 scripts/uclient_plot.gp

參考自 KYG-yaya573142/fibdrv/plot.gp

reset
set xlabel 'F(n)'
set ylabel 'time(ns)'
set title 'Fibonacci runtime in userspace'
set term png
set output "uclient_picture.png"
set grid
plot [0:92][0:] \
"uclient_time" using 1:2 with linespoints linewidth 2  pointtype 7 pointsize 0.5 title "fast doubling", \
"" using 1:3 with linespoints linewidth 2 pointtype 7 pointsize 0.5 title "bitwise hack",

將以上流程寫成寫入 MakeFile 中，新增 make ucheck：

ucheck: uclient
	./uclient > ./uclient_time
	gnuplot scripts/uclieng_plot.gp

最終產生以下圖片，可見在 userspace 中使用 bitwise 技巧比原本的實作多耗時

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 →

透過 gcc -S fibseq.c 輸出 x86_64 的組合語言程式碼，可參考線上網站 Godbolt Complier Explorer
fibseq_basic_fast_doubling_branchless

# int aset = !(mask & offset);
movl    -52(%rbp), %eax
        andq    -8(%rbp), %rax
        testq   %rax, %rax
        sete    %al
        movzbl  %al, %eax
        movl    %eax, -44(%rbp)

# int bset = !!(mask & offset);
movl    -52(%rbp), %eax
        andq    -8(%rbp), %rax
        testq   %rax, %rax
        setne   %al
        movzbl  %al, %eax
        movl    %eax, -48(%rbp)

# a = d ^ ((c ^ d) & -aset);
        movq    -32(%rbp), %rax
        xorq    -40(%rbp), %rax
        movq    %rax, %rdx
        movl    -44(%rbp), %eax
        negl    %eax
        cltq
        andq    %rdx, %rax
        xorq    -40(%rbp), %rax
        movq    %rax, -16(%rbp)

# b = d + (c & -bset);
        movl    -48(%rbp), %eax
        negl    %eax
        cltq
        andq    -32(%rbp), %rax
        movq    %rax, %rdx
        movq    -40(%rbp), %rax
        addq    %rdx, %rax
        movq    %rax, -24(%rbp)

fibseq_basic_fast_doubling_branch

# if (mask & offset){
#        a = d;
#        b = c + d;
#        }
        movl    -52(%rbp), %eax
        andq    -8(%rbp), %rax
        testq   %rax, %rax
        je      .L3
        movq    -40(%rbp), %rax
        movq    %rax, -16(%rbp)
        movq    -32(%rbp), %rdx
        movq    -40(%rbp), %rax
        addq    %rdx, %rax
        movq    %rax, -24(%rbp)
        jmp     .L4

# else {
#        a = c;
#        b = d;
#        }
        movq    -32(%rbp), %rax
        movq    %rax, -16(%rbp)
        movq    -40(%rbp), %rax
        movq    %rax, -24(%rbp)

目前初步推論使用 bitwise 技巧產生較多的組合語言程式碼跟更多的計算，導致效能比單純使用 branch 指令來得費時。

在 user space 實作大數

以下程式碼實作在分支 decnum，為第二個版本。
第一版本 744e95c3a987a3b5822cd887234d9a667c5d9591
第二版本 decnum head 將 malloc 從 decnum_t 函式移除，改進記憶體使用方式
為了測試程式碼，先實作於 user space。

新增的程式碼

新增 `decnum.c decnum.h`

新增兩個檔案，用於實作大數 struct decnum 結構體

新增 `dclient.c`

#define PRINTDECNUM(a)                                            \
    printf("%" PRIu32, (a).digits[((a).size - 1)]);               \
    for (size_t i = 1; i < (a).size; i++) {                       \
        printf(",%09" PRIu32 "", (a).digits[((a).size - i - 1)]); \
    }                                                             \
    printf("\n");

int main()
{
    decnum_t fib = DECNUM_INIT(0, 0);

    for (size_t i = 0; i < 100; i++) {
        decnum_fast_doubling(i, &fib);
        printf("%lu ", i);
        PRINTDECNUM(fib);
        decnum_free(&fib);
    }
    return 0;
}

隨著大數 decnum 相關的加法、減法、乘法實作，在每次 git commit 中，皆有 dclient.c 為對應的程式碼測試。

修改 `Makefile` 內容

+ dclient: dclient.c decnum.c fibseq.c
+	 $(CC) -o $@ $^

新增 dclient 用於測試 decnum 程式碼內容

修改 `fibseq.h fibseq.c`

在 fibseq.h fibseq.c 中新增 void decnum_fast_doubling 函式

`decnum.c decnum.h` 程式碼內容

struct decnum 大數結構體

struct decnum {
    uint32_t size;
    uint32_t cap;
    int32_t *digits;
};
typedef struct decnum decnum_t;
#define DECMAXVALUE 1000000000  // 10^9
#define DECNUM_INIT(a, b)                       \
    {                                           \
        .size = (a), .cap = (b), .digits = NULL \
    }

在原本的作業敘述中，

F_{93}

之後的數字會因為 overflow 導致輸出錯誤，採用 struct decnum 結構體表示一個數字。

size:紀錄大數的最高位有效位數(非零位數)
cap: 實際使用 malloc 的記憶體量
digits: 表示一個數字。使用 int32_t 紀錄數字，使用
$10^{9}$ 進位模式，因此每個位數最大能儲存
$999, 999, 999$ ，最小為
$0$

例如以下程式碼，若以 decnum 要表示

1, 999, 999, 999

，digits[0] 表示最低位數字，而 digits[1] 表示第二位數字

decnum_t b1 = DECNUM_INIT(2, 2);
decnum_new(&b1);
b1.digits[0] = DECMAXVALUE - 1;
b1.digits[1] = 1;

參考 Fast Doubling 方法

F i b (2 k) = F i b (k) [2 F i b (k + 1) - F i b (k)]

F i b (2 k + 1) = F i b (k + 1)^{2} + F i b (k)^{2}

要實作的函式功能為：加法、減法、乘法、平方

以下的實作，程式碼主要分為兩個部份

執行函式要求的運算
計算後的結果的位數，調整 size 與 cap

decnum_add function 兩個大數加法
















































void decnum_add(decnum_t *b1, decnum_t *b2, decnum_t *result)
{
        if (!result || !b1 || !b2) {
        return;
    }

    if (b1->size > result->cap || b2->size > result->cap) {
        return;
    }

    decnum_t a1 = DECNUM_INIT(b1->size, b1->cap);
    a1.digits = b1->digits;
    decnum_t a2 = DECNUM_INIT(b2->size, b2->cap);
    a2.digits = b2->digits;
    if (b2->size > b1->size) {
        decnum_swap(&a1, &a2);
    }

    if (b1 != result && b2 != result) {
        decnum_clean(result);
    }

    int32_t carry = 0;
    for (size_t i = 0; i < a2.size; i++) {
        int32_t digit = a1.digits[i] + a2.digits[i] + carry;
        carry = digit >= DECMAXVALUE;
        result->digits[i] = digit % DECMAXVALUE;
    }

    if (carry) {
        result->size = a2.size;
        for (size_t i = a2.size; (i < a1.size) && carry; i++) {
            int32_t digit = a1.digits[i] + 1;
            result->size += 1;
            carry = digit >= DECMAXVALUE;
            result->digits[i] = digit % DECMAXVALUE;
        }

        if ((result->size < result->cap) && carry) {
            result->digits[result->size] = 1;
            result->size += 1;
        }
    } else {
        result->size = a1.size;
        memcpy(result->digits + a2.size, a1.digits + a2.size,
               sizeof(int32_t) * (a1.size - a2.size));
    }
}

因為加法的特性，可以將運算完成的數字直接指派給原本的變數，例如 decnum_add(a,b,a) 將結果重新指派回 a ，就不需要新的空間指派。
處理兩數加法運算，將重疊的位數相加。再透過變數 carry 處理剩餘的位數

decnum_sub 兩個大數減法







































void decnum_sub(decnum_t *b1, decnum_t *b2, decnum_t *result)
{
    if (!result || !b1 || !b2) {
        return;
    }

    if (b1->size > result->cap || !b1->size || !b2->size) {
        return;
    }

    decnum_t a1 = DECNUM_INIT(b1->size, b1->cap);
    a1.digits = b1->digits;
    decnum_t a2 = DECNUM_INIT(b2->size, b2->cap);
    a2.digits = b2->digits;

    if (b1 != result && b2 != result) {
        decnum_clean(result);
    }

    int32_t carry = 0;
    for (size_t i = 0; i < a2.size; i++) {
        int32_t digit = a1.digits[i] - a2.digits[i] - carry;
        carry = digit < 0;
        result->digits[i] = digit + (DECMAXVALUE & -carry);
    }

    for (size_t i = a2.size; i < a1.size; i++) {
        int32_t digit = a1.digits[i] - carry;
        carry = digit < 0;
        result->digits[i] = digit + (DECMAXVALUE & -carry);
    }

    result->size = a1.size;
    size_t i = a1.size - 1;
    while (i && !result->digits[i]) {
        result->size--;
        i--;
    }
}

在 fast doubling 的計算過程中，

F i b (2 k) = F i b (k) [2 F i b (k + 1) - F i b (k)]

用到減法運算，並且

2 F i b (k + 1) ≧ F i b (k)

，因此實作中只有考慮 decnum_t b1 大於 decnum_t b2 下的減法運算
同樣因為減法的特性，可以將運算完成的數字直接指派給原本的變數，例如 decnum_add(a,b,a) 將結果重新指派回 a ，就不需要新的空間指派。

decnum_mult function 大數乘法



































void decnum_mult(decnum_t *b1, decnum_t *b2, decnum_t *result)
{
    if (!result || !b1 || !b2) {
        return;
    }

    if ((b1->size + b2->size) > result->cap) {
        return;
    }

    decnum_clean(result);
    result->size = b1->size + b2->size;

    const int32_t size = b1->size + b2->size;

    for (size_t i = 0; i < b1->size; i++) {
        for (size_t j = 0; j < b2->size; j++) {
            int64_t carry =
                ((int64_t) b1->digits[i]) * ((int64_t) b2->digits[j]);
            size_t k = i + j;
            do {
                uint64_t vv = carry + result->digits[k];
                result->digits[k] = vv % DECMAXVALUE;
                carry = vv / DECMAXVALUE;
                k++;
            } while ((k < size) && carry);
        }
    }

    size_t i = result->size - 1;
    while (i && !result->digits[i]) {
        result->size--;
        i--;
    }
}

在第 21 ~ 26 行中，因為乘法的特性，會向更高位數傳遞 carry，因此不能重新指派數值給原有的變數。

decnum_multi_by_two function 兩倍乘法






















void decnum_multi_by_two(decnum_t *b1)
{
    if (!b1) {
        return;
    }

    for (size_t i = 0; i < b1->size; i++) {
        b1->digits[i] <<= 1;
    }

    int32_t carry = 0;
    for (size_t i = 0; i < b1->size; i++) {
        int32_t digit = b1->digits[i] + carry;
        b1->digits[i] = digit % DECMAXVALUE;
        carry = digit / DECMAXVALUE;
    }

    if (carry && (b1->size < b1->cap)) {
        b1->digits[b1->size] = carry;
        b1->size++;
    }
}

提供大數一個乘以 2 的實作

使用大數搭配 Fast Doubling

decnum_fast_doubling 函式































































































void decnum_fast_doubling(unsigned int offset, decnum_t *result)
{
    if (!result) {
        return;
    }
    const float factor = 42.25;
    unsigned int sp = (((float) offset) / factor) + 2;

    decnum_t a = DECNUM_INIT(1, sp);
    decnum_new(&a);

    if (!a.digits) {
        goto fa;
    }

    decnum_t b = DECNUM_INIT(1, sp);
    decnum_new(&b);

    if (!b.digits) {
        goto fb;
    }

    decnum_t tmp = DECNUM_INIT(1, sp);
    decnum_new(&tmp);

    if (!tmp.digits) {
        goto ft;
    }

    decnum_t tmp2 = DECNUM_INIT(1, sp);
    decnum_new(&tmp2);

    if (!tmp2.digits) {
        goto ft2;
    }

    decnum_clean(&a);
    decnum_clean(&b);
    decnum_clean(&tmp);
    decnum_clean(&tmp2);

    a.size = 1;
    a.digits[0] = 0;
    b.size = 1;
    b.digits[0] = 1;

    unsigned long long mask = ULLONG_MAX ^ (ULLONG_MAX >> 1);
    mask >>= __builtin_clz(offset);


    for (; mask; mask >>= 1) {
        if (mask & offset) {
            // A = (a + b)^2 - 2ab = a^2 + b^2
            decnum_add(&a, &b, &tmp);
            decnum_mult(&tmp, &tmp, &tmp2);
            decnum_mult(&a, &b, &tmp);
            decnum_multi_by_two(&tmp);
            decnum_sub(&tmp2, &tmp, &tmp);

            // B = (a + b)^2 - a^2
            decnum_mult(&a, &a, &b);
            decnum_sub(&tmp2, &b, &b);

            decnum_assign(&a, &tmp);
        } else {
            // B = a^2 + b^2
            decnum_mult(&a, &a, &tmp);
            decnum_mult(&b, &b, &tmp2);
            decnum_add(&tmp, &tmp2, &tmp2);

            // A = a * (2 * b - a)
            decnum_multi_by_two(&b);
            decnum_sub(&b, &a, &b);
            decnum_mult(&b, &a, &tmp);
            decnum_assign(&b, &tmp2);

            decnum_assign(&a, &tmp);
        }
    }

    decnum_free(&tmp);
    decnum_free(&tmp2);
    decnum_free(&b);
    decnum_swap(result, &a);
    return;

ft2:
    decnum_free(&tmp);
ft:
    decnum_free(&b);
fb:
    decnum_free(&a);
fa:
    return;
}

神秘的數字 42.25
透過觀察

f i b (x)

在 decnum_t 實作，將輸出的 decnum_t size 除以

x

會得出一組穩定的數字，例如

x

取以下範圍

$0 ∽ 44$ ：需要 1 個 int32_t
$45 ∽ 87$ ：需要 2 個 int32_t
$950 ∽ 992$ ：需要 23 個 int32_t， 950 / 23 = 41.304、992 / 23 = 43.130
$34842 ∽ 34884$ ：需要 810 個 int32_t， 34842 / 810 = 43.066、1035 / 24 = 43.148

選出一個 magic number：

42.25

，將

⌊ x / 42.3 ⌋ + 2

作為每次使用 malloc 的大小

第 52 ~ 77 行中，只能使用 a, b, tmp, tmp2 四個變數去取得計算結果，並且盡量不使用乘法實作。

確認輸出

使用 make dclient 確認輸出

0 0
1 1
2 1
3 2
4 3
5 5
6 8
...
91 4,660046610,375530309
92 7,540113804,746346429
93 12,200160415,121876738
94 19,740274219,868223167
95 31,940434634,990099905
96 51,680708854,858323072
97 83,621143489,848422977
98 135,301852344,706746049
99 218,922995834,555169026

交叉比對後，列出到

F i b (99)

皆為正確的數字。

將大數程式碼移植成 kernel space 版本

以下程式碼實作於 kdecnum 分支

移植的程式碼

新增 `kdecnum.h kdecnum.c` 檔案

原本用於 user space 中的 decnum_t 加上前綴 k，改名成 kdecnum_t
將相關的函式名稱也加入前綴，例如 void decnum_new(decnum_t *ptr) 改成 void kdecnum_new(kdecnum_t *ptr)
malloc 改為 kmalloc, free 改為 kfree, realloc 改為 krealloc

修改 `Makefile` 檔案

- TARGET_MODULE := fibdrv
+ TARGET_MODULE := fibdrv_new

obj-m := $(TARGET_MODULE).o
- $(TARGET_MODULE)-objs := fibdrv.o
+ $(TARGET_MODULE)-objs := fibdrv.o kdecnum.o

...

+ eclient: eclient.c
+	$(CC) -o $@ $^

修改 TARGET_MODULE 名稱，避免使用 make 指令時發生錯誤
使用 eclient.c 測試 fibonacci driver

修改 `fibdrv.c`

原本實作於 fibseq.c 的 decnum_fib_fast_doubling 函式移植到 fibdrv.c 中
修改原本 fibdrv.c 中 ssize_t fib_read，將 b1.digits 大數數值指派給 buf
#define MAX_LENGTH 92 改為 #define MAX_LENGTH 150

#define MAX_LENGTH 150
static ssize_t fib_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
    kdecnum_t b1 = KDECNUM_INIT(0, 0);
    int res = decnum_fib_fast_doubling(*offset, &b1);
    size_t ss = min(size, b1.size * sizeof(int32_t));

    access_ok(buf, ss);
    res = copy_to_user(buf, b1.digits, ss);
    kdecnum_free(&b1);
    return res;
}

參考 K04: fibdrv
核心驅動裝置不能直接寫入該硬體，需透過 copy_to_user 方能將數值內容複製，使得 client 端接收。

剛開始撰寫程式碼時，我使用以下程式碼，導致 Ubuntu 系統螢幕顯示卡頓，即使是只有一行也是卡頓。意外的是系統沒有崩潰。

buf[0] = b1.digits[0] & 0xFF;

修改 `eclient.c`

#define BUFSIZE 8
int main()
{
    long long sz;
    int32_t buf[BUFSIZE];
    memset(buf, 0, sizeof(int32_t) * BUFSIZE);

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

    lseek(fd, 99, SEEK_SET);
    sz = read(fd, buf, BUFSIZE * sizeof(int32_t));
    
    decnum_t fib = DECNUM_INIT(BUFSIZE, BUFSIZE);
    fib.digits = buf;
    PRINTDECNUM(fib);

    close(fd);
    return 0;
}

在實作上幾乎與原本的 client.c 相同

時間成本計算

以下實作於 timemeasure 分支

修改的程式碼

以下實作的版本為 timemeasure 60268ca7215f84a3f0a973d05f7fda03bab3f2f5

將 fibdrv.c 的程式碼的回傳改為計算 decnum_fib_fast_doubling 需要的時間，單位為 nano second

static ssize_t fib_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
    kdecnum_t b1 = KDECNUM_INIT(0, 0);
 
+    ktime_t kk = ktime_get();
    int res = decnum_fib_fast_doubling(*offset, &b1);
+    kk = ktime_sub(ktime_get(), kk);
+    ssize_t dd = ktime_to_ns(kk);
    
    size_t ss = min(size, b1.size * sizeof(int32_t));
    access_ok(buf, ss);
    res = copy_to_user(buf, b1.digits, ss);
    kdecnum_free(&b1);
-    return res;
+    return dd;
}

在尚未移除影響效能的因素下，多次使用指令 make eclient 計算

F i b (99)

，可得到以下輸出

移除影響效能分析的因素

使用 taskset 指定 CPU 核心上執行程式(指定 19)

cpu19 為 Intel effective core，用途為省電，使用 Performance core 在執行時間上較短
以下實作為 timemeasure 719aa1ef02dc949dbd4c65979a2698ae726acdc9

在 Makefile 中新增測試流程






eall: all eclient
 	$(MAKE) unload
 	$(MAKE) load
- 	sudo ./eclient > ./eclient_time
+	sudo taskset -c 1 ./eclient > ./eclient_time
	gnuplot scripts/eclient_plot.gp

在多次執行 make eall 後，無論是否使用第四行或是第五行程式碼所繪製的圖片，皆有週期性的跳動

或是遠高於平均、低於平均的數值

設定 intel turbo mode、抑制 ASLR、區隔指定的 CPU

參考 2022 年 Linux 核心設計/實作課程作業 fibdrv Linux 效能分析的提示，保留特定的 CPU
參考 grub2 - How do I add a kernel boot parameter? - Ask Ubuntu
參考 What is the difference between GRUB_CMDLINE_LINUX and GRUB_CMDLINE_LINUX_DEFAULT in /etc/default/grub

在 /etc/default/grub 檔案中加入 GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=19"，並且 sudo update-grub

並修改 Makefile

performance:
#	cat /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
	sudo sh scripts/performance.sh

powersave:
#	cat /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
	sudo sh scripts/powersave.sh

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

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

irqaffinity:
	sudo sh scripts/changeIRQAffinity.sh

eall: all eclient noturbo noaslr performance irqaffinity
	$(MAKE) unload
	$(MAKE) load
	sudo taskset -c 19 ./eclient > ./eclient_time
	gnuplot scripts/eclient_plot.gp

使用 make eall 後，產生以下圖片

好像什麼沒變化

檢查實驗因素

在這次作業中，我使用 @KYWeng 的筆記作為對照組去檢驗我的實作。忽略第 0 ~ 5 次的

F i b (99)

計算，並顯示於以下圖片，此實驗獲得平穩的結果，表示確實移除影響效能分析的因素。

ftrace and trace-cmd

使用 trace-cmd 追蹤我的實作：使用 sudo trace-cmd record --max-graph-depth 1 -e all taskset -c 19 ./eclient > ./eclient_time，並將結果輸出為下圖。執行時間驚人的增加 7 倍。

使用 trace-cmd report 輸出的報告如下

eclient-9916  [019]  1781.863070: kmalloc:              (kdecnum_new+0x23) call_site=kdecnum_new ptr=0xffff8fe002e101a0 bytes_req=4 bytes_alloc=8 gfp_flags=GFP_KERNEL
eclient-9916  [019]  1781.863070: kfree:                (kdecnum_free+0x17) call_site=kdecnum_free ptr=0xffff8fe002e10118
eclient-9916  [019]  1781.863070: kfree:                (kdecnum_free+0x17) call_site=kdecnum_free ptr=0xffff8fe002e10b10
...

然而同樣的使用 ftrace 追蹤 @KYWeng 的實作，卻是沒有變化(下圖)

在觀察 trace-cmd report 輸出的報告後，我注意到我的實作在每次加法、減法、乘法、都會使用 kmalloc 並且很快就 kfree，因 ftrace 追蹤行為導致在執行時間大幅增加。
對比於 @KYWeng 的實作輸出的報告，出現 kmalloc, kfree 的頻率不多，參照其程式碼的實作中，使用 krealloc 而不是多次使用 kmalloc

減少大數運算的時間成本

第一次改進

這一次的修改包含

修改大數系統的加法、減法、乘法函式，可參考 master b3960dd6260b28872978d53720d1c66c4139b01f
修改記憶體使用方式，使用 magic number 42.25 配置指定大小的記憶體。在 Linux driver 版本中，不能使用浮點數，因此採用 42 作為計算數值。

改進之後產生的輸出圖片如下：

成為穩定執行時間成本的線段 38000 ns 下降至 11500 ns

第二次改進(使用 perf)

參考 @KYWeng perf 說明

sudo perf record -g --call-graph dwarf ./eclient
sudo perf report --stdio -g graph,0.5,caller

取得以下結果(省略部份輸出)，可以得出實作中乘法與 memset_erms 指令絕大多數執行時間

59.11%     0.00%  eclient  eclient            [.] main
            |
            ---main
               __GI___read (inlined)
               entry_SYSCALL_64_after_hwframe
               do_syscall_64
               __x64_sys_read
               ksys_read
               vfs_read
               fib_read
               |          
               |--29.81%--kdecnum_mult
               |          
                --29.30%--memset_erms

使用 sudo perf stat -r 10 -e cycles,instructions,cache-misses,cache-references,branch-instructions,branch-misses ./eclient 取得以下輸出， cpu_core/cache-misses/ 佔去 59.19%

Performance counter stats for './eclient' (10 runs):

          205,8354      cpu_core/cycles/                                              ( +-  1.36% )
     <not counted>      cpu_atom/cycles/                                              (0.00%)
          426,1798      cpu_core/instructions/                                        ( +-  0.11% )
     <not counted>      cpu_atom/instructions/                                        (0.00%)
              2274      cpu_core/cache-misses/                                        ( +- 52.19% )
     <not counted>      cpu_atom/cache-misses/                                        (0.00%)
            1,9000      cpu_core/cache-references/                                     ( +-  7.76% )
     <not counted>      cpu_atom/cache-references/                                     (0.00%)
           81,7867      cpu_core/branch-instructions/                                     ( +-  0.12% )
     <not counted>      cpu_atom/branch-instructions/                                     (0.00%)
              6047      cpu_core/branch-misses/                                       ( +-  7.44% )
     <not counted>      cpu_atom/branch-misses/                                       (0.00%)

         0.0011872 +- 0.0000302 seconds time elapsed  ( +-  2.54% )

Some events weren't counted. Try disabling the NMI watchdog:
	echo 0 > /proc/sys/kernel/nmi_watchdog
	perf stat ...
	echo 1 > /proc/sys/kernel/nmi_watchdog

tags: Linux 核心設計 2022