2023q1 Homework3 (fibdrv)

contributed by < slipet >

開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

$lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         48 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               AuthenticAMD
  Model name:            AMD Ryzen 5 5600X 6-Core Processor
    CPU family:          25
    Model:               33
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            0
    Frequency boost:     enabled
    CPU max MHz:         4650.2920
    CPU min MHz:         2200.0000
    BogoMIPS:            7399.35
    Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext fxsr_opt pdpe1gb rdtscp lm constant_ts
                         c rep_good nopl nonstop_tsc cpuid extd_apicid aperfmperf rapl pni pclmulqdq monitor ssse3 fma cx16 sse4_1 sse4_2 movbe popcnt aes xsave avx f16c rdrand lahf_
                         lm cmp_legacy svm extapic cr8_legacy abm sse4a misalignsse 3dnowprefetch osvw ibs skinit wdt tce topoext perfctr_core perfctr_nb bpext perfctr_llc mwaitx cpb
                          cat_l3 cdp_l3 hw_pstate ssbd mba ibrs ibpb stibp vmmcall fsgsbase bmi1 avx2 smep bmi2 erms invpcid cqm rdt_a rdseed adx smap clflushopt clwb sha_ni xsaveopt
                          xsavec xgetbv1 xsaves cqm_llc cqm_occup_llc cqm_mbm_total cqm_mbm_local clzero irperf xsaveerptr rdpru wbnoinvd arat npt lbrv svm_lock nrip_save tsc_scale v
                         mcb_clean flushbyasid decodeassists pausefilter pfthreshold avic v_vmsave_vmload vgif v_spec_ctrl umip pku ospke vaes vpclmulqdq rdpid overflow_recov succor 
                         smca fsrm
Virtualization features: 
  Virtualization:        AMD-V
Caches (sum of all):     
  L1d:                   192 KiB (6 instances)
  L1i:                   192 KiB (6 instances)
  L2:                    3 MiB (6 instances)
  L3:                    32 MiB (1 instance)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-11
Vulnerabilities:         
  Gather data sampling:  Not affected
  Itlb multihit:         Not affected
  L1tf:                  Not affected
  Mds:                   Not affected
  Meltdown:              Not affected
  Mmio stale data:       Not affected
  Retbleed:              Not affected
  Spec rstack overflow:  Mitigation; safe RET, no microcode
  Spec store bypass:     Mitigation; Speculative Store Bypass disabled via prctl
  Spectre v1:            Mitigation; usercopy/swapgs barriers and __user pointer sanitization
  Spectre v2:            Mitigation; Retpolines, IBPB conditional, IBRS_FW, STIBP always-on, RSB filling, PBRSB-eIBRS Not affected
  Srbds:                 Not affected
  Tsx async abort:       Not affected

Checklist

• 研讀上述 Linux 效能分析的提示 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作
  $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
• 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 clz / ctz 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
• 複習 C 語言 數值系統 和 bitwise operation，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本;
• 學習指出針對大數運算的加速運算和縮減記憶體操作成本的舉措，紀錄你的認知和疑惑
• 注意到 fibdrv.c 存在著 DEFINE_MUTEX, mutex_trylock, mutex_init, mutex_unlock, mutex_destroy 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 POSIX Thread 的程式碼來確認。
  $\to$ 搭配閱讀〈並行和多執行緒程式設計〉

Experiment procedure

Modification to calculate Fib(n), when n > 92

In the original design, the Fibonacci sequence is stored in a long long type array, which will overflow after fib(92). In this report, I followed the recommendation from link to implement two methods to deal with this issue:

1. GCC __uint128 type:

Declare the array for recording Fibonacci sequence using __uint128 type. The key difference between the long long and __uint128 types is that printf() cannot directly output the result with __uint128 type. As the result of this, we need to convert the number into a string and pass it to the user process through a buffer.

Details

static size_t fib_sequence(long long k, char *buf)
{
    uint128_t f[k + 2];

    f[0] = 0;
    f[1] = 1;

    for (int i = 2; i <= k; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }
    char *result = uint128_to_string(f[k]);
    size_t len = uint128_len(f[k]);
    __reverse(result, len);
    if (copy_to_user(buf, result, len))
        return -EFAULT;
    kfree(result);
    return len;
}

uint128_to_string and uint128_len are the functions associated with uint128_t type. Below are the details of the implementation:

Details

static size_t uint128_len(uint128_t x)
{
    size_t size = 0;
    while (x) {
        size++;
        x /= 10;
    }
    size += (size == 0);  // digit len can not less than 1
    return size;
}

static char *uint128_to_string(uint128_t x)
{
    char *str = (char *) kmalloc(uint128_len(x) + 1, GFP_KERNEL);
    char *p = str;
    *p = '0';  // initilize the string to zero;
    while (x) {
        *p++ = x % 10 + '0';
        x /= 10;
    }

    return str;
}

So far, we are able to accurately calculate the Fibonacci sequence up to n = 100; however, we still encounter overflow after n = 187.

##Modify verify.py to calculate fibonacci sequence til fib(200)
f(187) fail
input: 198239973509362327032045173661212819077
expected: 538522340430300790495419781092981030533

2. myBigN

There is an alternative for the large number representation mentioned in link, which is a customized data structure. I reference the implementations from AdrianHuang and SSO-23 to design myBigN for large number representation.

Structure details

typedef struct {
    char *ptr;
    size_t size : MY_BIGNUM_MAX_LEN, capcity : 6, is_ptr : 1, reserved : 3;
} myLong;

typedef struct {
    char data[15];
    uint8_t free_space : 4, reserved : 4;
} myShort;

typedef union {
    myLong long_num;
    myShort short_num;
} myBigN;

Numbers up to 15 digits are represented using the myShort structure. Whenever a number exceeds 15 digits, we dynamically allocate memory space to a pointer in myLong for storing large numbers. Both structures include a reserved byte to record information about free space, size, and a control flag. The following is the implementation associated with myBigN.

fib_sequence

static ssize_t fib_sequence(long long k, char *buf)
{
    myBigN f[k + 2];

    f[0] = *MY_BIGNUM_TMP("0");
    f[1] = *MY_BIGNUM_TMP("1");

    for (int i = 2; i <= k; i++) {
        myBigN_Add(&f[i], &f[i - 1], &f[i - 2]);
    }
    ssize_t len = myBigN_size(&f[k]);
    if (copy_to_user(buf, myBigN_data(&f[k]), len))
        return -EFAULT;
    for (int i = 0; i <= k; i++)
        myBigN_free(&f[i]);
    return len;
}

The strategy for myBigN variables addition is implemented character by character. Below are the details of this method.

myBigN_Add

void myBigN_Add(myBigN *out, const myBigN *x, const myBigN *y)
{
    size_t sizeX = myBigN_size(x), sizeY = myBigN_size(y);
    char *dataX = myBigN_data(x), *dataY = myBigN_data(y);
    size_t i = 0;
    if (sizeX < sizeY) {
        __SWAP(dataX, dataY, char);
        __SWAP(&sizeX, &sizeY, size_t);
    }
    __reverse(dataX, sizeX);
    __reverse(dataY, sizeY);

    uint8_t carry = 0;
    char result[sizeX + 2];
    for (; i < sizeX || carry; i++) {
        uint8_t sum = ((i < sizeX) ? (dataX[i] - '0') : 0) +
                      ((i < sizeY) ? (dataY[i] - '0') : 0) + carry;
        result[i] = '0' + sum % 10;
        carry = sum / 10;
    }
    result[i] = 0;

    __reverse(result, i);
    __reverse(dataX, sizeX);
    __reverse(dataY, sizeY);
    if (out)
        *out = *MY_BIGNUM_TMP(result);
}

The macros MY_BIGNUM_TMP and INIT_STRING_LITERALS, referenced from AdrianHuang, leverage the designated initializer to make the initialization of variables more elegant and readable.

MY_BIGNUM_TMP and INIT_STRING_LITERALS

#define INIT_STRING_LITERALS()           \
    (myBigN)                             \
    {                                    \
        .short_num = {.free_space = 15 } \
    }

#define MY_BIGNUM_TMP(x) myBigN_init(&INIT_STRING_LITERALS(), x)

In MY_BIGNUM_TMP(x), we can initialize a myBigN pointer with NIT_STRING_LITERALS() and a string literal. Declaring the INIT_STRING_LITERALS() macro is equivalent to declaring a myBigN object. myBigN_init receives the address of the object and a string literal to complete the subsequent allocation. Numbers with a digit length of up to 15 are stored in a character array. When the length exceeds 15, we allocate heap space to x->long_num.ptr for storing the larger number.

myBigN_init

myBigN *myBigN_init(myBigN *x, const char *strNum)
{
    *x = INIT_STRING_LITERALS();
    //+ 1 for '\0'
    ssize_t len = strlen(strNum) + 1;
    if (len > 16) {
        x->long_num.size = len - 1;
        x->long_num.is_ptr = true;
        x->long_num.ptr = kmalloc(myBigN_size(x), GFP_KERNEL);
        memcpy(myBigN_data(x), strNum, len);
    } else {
        memcpy(x->short_num.data, strNum, len);
        x->short_num.free_space = 15 - len + 1;
    }

    return x;
}   

Up until now, everything seemed set up to calculate Fibonacci sequence to fib(500). However, every time I execute $make check command, a failure message appears, followed by my Ubuntu system freezing, requiring a restart to resolve. The failure message is looks like this:

##Modify verify.py to calculate fibonacci sequence til fib(500)
f(312) fail
input: 1719558092601766452430641106302905217344934236440122960529002115744
expected: 71558092601766452430641106302905217344934236440122960529002115744

Furthermore, the terminated numbers of the Fibonacci sequence are not the same and appear to occur randomly.

At first, I intserted printk into the function and checked the information about myBigN variables. I used $sudo dmesg | grep "xxxxx" to filter the kernel messages. With the help of the print messages, I found that there is a condition uncovered in myBigN_init. The error was that the large number should be assigned to x->long_num.ptr rather than x->short_num.data when len = 16. The revised code is as follows:

myBigN_init (revised)

myBigN *myBigN_init(myBigN *x, const char *strNum)
{
    *x = INIT_STRING_LITERALS();
    //+ 1 for '\0'
    ssize_t len = strlen(strNum) + 1;
-    if (len > 16) {
+    if (len >= 16) {
        x->long_num.size = len - 1;
        x->long_num.is_ptr = true;
        x->long_num.ptr = kmalloc(myBigN_size(x), GFP_KERNEL);
        memcpy(myBigN_data(x), strNum, len);
    } else {
        memcpy(x->short_num.data, strNum, len);
        x->short_num.free_space = 15 - len + 1;
    }

    return x;
}   

However, the failure message persists despite the modification. This leads me to suspect other parts of my implementation. Subsequently, I spent two days addressing this issue. Ultimately, I discovered that the problem lies in memcpy(myBigN_data(x), strNum, len);. It copies the entire string including \0 into myBigN_data(x), but the allocated size for x->long_num.ptr is only len - 1. Thus, an extra byte is copied into myBigN_data(x), overwriting the area designated for storing the size. Below is the modification:

myBigN_init (final)

myBigN *myBigN_init(myBigN *x, const char *strNum)
{
    *x = INIT_STRING_LITERALS();
    //+ 1 for '\0'
    ssize_t len = strlen(strNum) + 1;
    if (len >= 16) {
        x->long_num.size = len - 1;
        x->long_num.is_ptr = true;
        x->long_num.ptr = kmalloc(myBigN_size(x), GFP_KERNEL);
-       memcpy(myBigN_data(x), strNum, len);
+       memcpy(myBigN_data(x), strNum, myBigN_size(x));    
    } else {
        memcpy(x->short_num.data, strNum, len);
        x->short_num.free_space = 15 - len + 1;
    }

    return x;
}   

Now, we are able to calculate Fibonacci sequence up to fib(500). The following is the result of fib(500) in the out file, which is same as link

/fibonacci at offset 500, returned the sequence 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125.    

TODO: I should learn using other debugging tools to help me debug kernel modules.

sysprog21/bignum

From the description of sysprog21/bignum 程式碼分析, we can found that

Reference

AdrianHuang

Linux 核心專題: 重做 fibdrv