2022q1 Homework3 (fibdrv)

contributed by < Herakleos >

Reqirements

• 研讀上述 Linux 效能分析的提示 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作
  $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
• 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 clz / ctz 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
• 複習 C 語言 數值系統 和 bitwise operation，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本;
• 研讀 KYG-yaya573142 的報告，指出針對大數運算，有哪些加速運算和縮減記憶體操作成本的舉措？
• lsmod 的輸出結果有一欄名為 Used by，這是 "each module's use count and a list of referring modules"，但如何實作出來呢？模組間的相依性和實際使用次數 (reference counting) 在 Linux 核心如何追蹤呢？

  搭配閱讀 The Linux driver implementer’s API guide » Driver Basics

• 注意到 fibdrv.c 存在著 DEFINE_MUTEX, mutex_trylock, mutex_init, mutex_unlock, mutex_destroy 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 POSIX Thread 的程式碼來確認。

Environment

The same as I mentioned in lab0-c.

Prerequisites

Kernal-modules

Install linux-headers package and make sure the package has been installed correctly.

$ dpkg -L linux-headers-`uname -r` | grep "/lib/modules"
/lib/modules
/lib/modules/5.13.0-35-generic
/lib/modules/5.13.0-35-generic/build

After I compiled and test (make check) the original program, instead of showing Passed [-], it turns out with several problems.

1. Skipping BTF generation for … due to unavailability of vmlinux

I am still working on this problem.

$ readelf -a ./fibdrv.ko | grep BTF

2. insmod: ERROR: could not insert module fibdrv.ko: Operation not permitted

Why do I get “Required key not available” when install 3rd party kernel modules or after a kernel upgrade?

As above, something went wrong while installing kernal-modules.

$ dmesg | tail -1
Lockdown: insmod: unsigned module loading is restricted; see man kernel_lockdown.7

$ sudo mokutil --sb-state
SecureBoot enabled

$ sudo mokutil --disable-validation
$ sudo reboot

$ sudo mokutil --sb-state
SecureBoot enabled
SecureBoot validation is disabled in shim

After all these steps, Passed [-] will be correctly displayed.

 Passed [-]
f(93) fail
input: 7540113804746346429
expected: 12200160415121876738

Reduce the external interference

• Modify GRUB_CMDLINE_LINUX_DEFAULT in /etc/default/grub.

GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=3"

$ sudo update-grub
$ sudo reboot

$ cat /sys/devices/system/cpu/isolated
3

• Address space layout randomization.

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

• Disable turbo mode in Intel structure.

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

$ sudo taskset -c 3 ./client

In order not to do this step repeatly, I put this line in Makefile.

More about taskset

Working on…

Modify Timer (1)

Replace skipped operation fib_write() to get ktime.

    ktime_t kt = ktime_get();
    fib_sequence(*offset);
    kt = ktime_sub(ktime_get(), kt);
    return (ssize_t) ktime_to_ns(kt);

This will cause line diff return make error, the script/expected.txt should therefore be refined.

Issue - Make error causes by diff

Fibonacci

Fix the original fib_sequence(), C99 variable-length array (VLA) is not allowed in Linux kernel.

    if (k <= 2)
        return !!k;
    
    long long f[3];    // replace variable-length array (VLA)

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

    for (int i = 2; i <= k; i++) {
        f[2] = f[0] + f[1];
        f[0] = f[1];
        f[1] = f[2];
    }

    return f[2];

According to the article, we may calculate fibonacci number by the following formula.

$$\begin{array}{rl}F(2k)& =F(k)[2F(k+1)-F(k)]\\ F(2k+1)& =F(k+1{)}^2+F(k{)}^2\end{array}$$

After reading Calculating Fibonacci Numbers by Fast Doubling, I tried to modify fib_sequence() as following.

    if (k <= 2)
        return !!k;
    
    long long f[2];

    f[0] = 0;   // F(n)
    f[1] = 1;   // F(n+1)

    /* get MSB for the total round of the loop */
    for (int i = __builtin_clzll(k) - 1; i >= 0; --i) {
        /* F(2n) = F(n) * [ 2 * F(n+1) - F(n) ] */
        long long f1 = f[0] * ((f[1] << 1) - f[0]);
        /* F(2n+1) = F(n)^2 + F(n+1)^2 */
        long long f2 = f[0] * f[0] + f[1] * f[1];

        /* k >> i is odd or not */
        if ((k >> i) & 1) {
            f[0] = f2;      // F(2n+1)
            f[1] = f1 + f2; // F(2n+2)
        } else {
            f[0] = f1;  // F(2n)
            f[1] = f2;  // F(2n+1)
        }
    }

    return f[0];    // F(k)

By the way, the above article use a for loop to get the MSB.

    unsigned int h = 0;
    for (unsigned int i = n ; i ; ++h, i >>= 1);

Analysis __builtin_clz and other bitwise operation to find MSB

Working on…

Modify Timer (2)

Use escape (return of fib_seq_fd_clz) to avoid the function be removed after optimization.

__attribute__((always_inline)) static inline void escape(void *p) {
    __asm__ volatile ("" : : "g"(p) : "memory");
}

After add fib_sequence using fast doubling, fib_write should be modified.

    ktime_t kt;
    long long result = 0;
    switch (size) {
    case 0:
        kt = ktime_get();
        fib_sequence(*offset);
        kt = ktime_sub(ktime_get(), kt);
        break;
    case 1:
        kt = ktime_get();
        result = fib_seq_fd_clz(*offset);
        kt = ktime_sub(ktime_get(), kt);
        escape(&result);
        break;
    case 2:
        return ktime_to_ns(ktime_get());
    default:
        return 1;
    }
    return (ssize_t) ktime_to_ns(kt);

To-do: statistics

Big Number

Reading KYG-yaya573142

tags: linux2022