---
tags: linux2022
---

# 2022q1 Homework3 (fibdrv)
contributed by < [Build-A-Moat](https://github.com/Build-A-Moat/fibdrv) >

## 實驗環境

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

$ lscpu
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):              8
On-line CPU(s) list: 0-7
Thread(s) per core:  2
Core(s) per socket:  4
Socket(s):           1
NUMA node(s):        1
Vendor ID:           GenuineIntel
CPU family:          6
Model:               60
Model name:          Intel(R) Core(TM) i7-4720HQ CPU @ 2.60GHz
Stepping:            3
CPU MHz:             2320.005
CPU max MHz:         3600.0000
CPU min MHz:         800.0000
BogoMIPS:            5187.67
Virtualization:      VT-x
L1d cache:           128 KiB
L1i cache:           128 KiB
L2 cache:            1 MiB
L3 cache:            6 MiB
NUMA node0 CPU(s):   0-7

## 作業要求
> [fibdrv](https://hackmd.io/@sysprog/linux2022-fibdrv#K04-fibdrv)

## 排除干擾效能分析的因素 [KYG-yaya573142](https://hackmd.io/@KYWeng/rkGdultSU#2020q1-Homework2-fibdrv)
### 限定 CPU 給特定的程式使用
#### 隔離cpu的核
先用 `taskset -cp 1` 取得行程的處理器親和性

pid 1's current affinity list: 0-7

修改 `sudo vi /etc/default/grub`，並用 `sudo update-grub` 更新

~~GRUB_CMDLINE_LINUX_DEFAULT="quiet splash"~~
GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=7"

重開機後，再用 `taskset -cp 1` 取得行程的處理器親和性

pid 1's current affinity list: 0-6

成功將第7核隔離
#### 將行程固定在特定的 CPU 中執行
使用 `sudo taskset -c 7 ./client` 時出現錯誤

Failed to open character device: No such file or directory

需要將 `fibdrv.ko` 掛載到kernel

sudo insmod fibdrv.ko

#### 抑制 [address space layout randomization](https://en.wikipedia.org/wiki/Address_space_layout_randomization) (ASLR)

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

#### 設定 scaling_governor 為 performance

echo performance > /sys/devices/system/cpu/cpu0/cpufreq/scaling_governor
bash: /sys/devices/system/cpu/cpu0/cpufreq/scaling_governor: Permission denied

參考 [Ask ubuntu](https://askubuntu.com/questions/10495/scaling-governor-throws-permission-error-for-su)

sudo sh -c "echo -n performance > /sys/devices/system/cpu/cpu0/cpufreq/scaling_governor"
cat /sys/devices/system/cpu/cpu0/cpufreq/scaling_governor
performance

成功

#### 關閉 turbo mode

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

量測結果


可以看出還是有飄動的情形

#### SMP IRQ affinity
[KYG-yaya573142](https://hackmd.io/BZjwYw1FQ1O0NPY5kIS7VQ?view#SMP-IRQ-affinity)將 smp_affinity 的值與 0x7f 做 `&` 運算
但我認為只接將 `7f` 寫入就可以避免 CPU 7 去處理IRQ，還需要再研究原因。

for file in `find /proc/irq -name "smp_affinity"`
do
    sudo bash -c "echo 7f > ${file}"
done

結束後將值設定為 `ff`

for file in `find /proc/irq -name "smp_affinity"`
do
    sudo bash -c "echo ff > ${file}"
done

發現將值設定為 `ff` 會造成 cpu 使用率很高，猜測是因為所有的 cpu 都在處理 ISR 所造成，
改為設定回原本的值，所以要先將值存下來。

array=()
for file in `find /proc/irq -name "smp_affinity"`
do
    var=`cat ${file}`
    array+=($var)
done

counter=0
for file in `find /proc/irq -name "smp_affinity"`
do
    sudo bash -c "echo ${array[${counter}]} > ${file}"
    let counter++
done

重新開機會將 smp_affinity 重設，但是值會有不同，需再研究 OS 如何設定這些值，依據什麼，才能使電腦在處理 ISR 與其他 process 中取得平衡。

#cat /proc/irq/*/smp_affinity
ff ff ff
ff ff ff
ff ff ff
7f 7f 7f
ff ff ff
ff ff ff
ff ff ff
20 20 20
7f 7f 7f
7f 7f 7f
7f 7f 7f
22 22 22
08 08 08
08 08 08
11 11 11
ff ff ff
44 ff ff
ff 02 44
02 44 02
08 08 08
7f 7f 7f
40 40 40
10 10 10
7f 7f 7f
7f 7f 7f
ff ff ff
ff ff ff
ff ff ff
ff ff ff
ff ff ff
7f 7f 7f
7f 7f 7f


#### 整合為單一 script
[do_measurement.sh](https://github.com/Build-A-Moat/fibdrv/blob/master/do_measurement.sh)

## 實做 Fast Doubling

static long long fib_sequence_fdouble(long long k)
{
    long long a = 0, b = 1;
    unsigned int ndigit = 32 - __builtin_clz(k);
    for (unsigned int mask = 1 << (ndigit - 1); mask; mask >>= 1) {
        long long t1 = a * (2 * b - a), t2 = b * b + a * a;
        a = t1;
        b = t2;
        if (k & mask) {
            t1 = a + b;
            a = b;
            b = t1;
        }
    }
    return a;
}

使用數字字串實做 big number

build-a-moat@buildamoat:~/linux/homework3/fibdrv$ make all
make -C /lib/modules/5.13.0-40-generic/build M=/home/build-a-moat/linux/homework3/fibdrv modules
make[1]: Entering directory '/usr/src/linux-headers-5.13.0-40-generic'
  MODPOST /home/build-a-moat/linux/homework3/fibdrv/Module.symvers
ERROR: modpost: missing MODULE_LICENSE() in /home/build-a-moat/linux/homework3/fibdrv/fibdrv.o
make[2]: *** [scripts/Makefile.modpost:150: /home/build-a-moat/linux/homework3/fibdrv/Module.symvers] Error 1
make[2]: *** Deleting file '/home/build-a-moat/linux/homework3/fibdrv/Module.symvers'
make[1]: *** [Makefile:1794: modules] Error 2
make[1]: Leaving directory '/usr/src/linux-headers-5.13.0-40-generic'
make: *** [Makefile:15: all] Error 2

參考 [回答](https://github.com/volatilityfoundation/volatility/issues/812) 在 `xs.c` 中加入 `MODULE_LICENSE("Dual MIT/GPL");`

make -C /lib/modules/5.13.0-40-generic/build M=/home/build-a-moat/linux/homework3/fibdrv modules
make[1]: Entering directory '/usr/src/linux-headers-5.13.0-40-generic'
make[1]: Leaving directory '/usr/src/linux-headers-5.13.0-40-generic'
make unload
make[1]: Entering directory '/home/build-a-moat/linux/homework3/fibdrv'
sudo rmmod fibdrv || true >/dev/null
make[1]: Leaving directory '/home/build-a-moat/linux/homework3/fibdrv'
make load
make[1]: Entering directory '/home/build-a-moat/linux/homework3/fibdrv'
sudo insmod fibdrv.ko
make[1]: Leaving directory '/home/build-a-moat/linux/homework3/fibdrv'
sudo ./client > out
Failed to open character device: No such file or directory
make: *** [Makefile:49: check] Error 1

因要使用 `xs.h` 與 `xs.c` 所以需要在 makefile 中引用 `$(TARGET_MODULE)-objs := xs.o`，參考 [原始碼](https://github.com/AdrianHuang/fibdrv/blob/big_number/Makefile)

## 量測執行時間
### user space 執行時間

for (int i = 0; i <= offset; i++) {
    long long kt;
    lseek(fd, i, SEEK_SET);
    clock_gettime(CLOCK_MONOTONIC, &t1);
    //
    clock_gettime(CLOCK_MONOTONIC, &t2);
    long long ut = (long long)(t2.tv_sec * 1e9 + t2.tv_nsec)
                - (t1.tv_sec * 1e9 + t1.tv_nsec);
    printf("%d %lld %lld %lld\n", i, kt, ut, ut - kt);
}

### kernel space 執行時間

    static ssize_t fib_write(struct file *file,
                         const char *buf,
                         size_t size,
                         loff_t *offset)
{
    ktime_t kt;
    switch (size) {
    case 0:
        kt = ktime_get();
        fib_sequence(*offset);
        kt = ktime_sub(ktime_get(), kt);
        break;
    case 1:
        kt = ktime_get();
        fib_sequence_fdouble(*offset);
        kt = ktime_sub(ktime_get(), kt);
        break;

    default:
        return 0;
    }
    return (ssize_t) ktime_to_ns(kt);
}

### system call 執行時間

struct timespec t1, t2;
for (int i = 0; i <= offset; i++) {
    long long kt;
    lseek(fd, i, SEEK_SET);
    clock_gettime(CLOCK_MONOTONIC, &t1);
    kt = write(fd, write_buf, 0); /* runtime in kernel space */
    clock_gettime(CLOCK_MONOTONIC, &t2);
    long long ut = (long long)(t2.tv_sec * 1e9 + t2.tv_nsec)
                - (t1.tv_sec * 1e9 + t1.tv_nsec);
    printf("%d %lld %lld %lld\n", i, kt, ut, ut - kt);
}


使用 [mlock](https://man7.org/linux/man-pages/man2/mlock.2.html) 後，可以降低 page fault 所耗費的時間。

struct timespec t1, t2;
if (mlockall(MCL_CURRENT | MCL_FUTURE))
    printf("mlockall failed!\n");

for (int i = 0; i <= offset; i++) {
    long long sz;
    lseek(fd, i, SEEK_SET);
    clock_gettime(CLOCK_MONOTONIC, &t1);
    sz = write(fd, write_buf, 0);
    clock_gettime(CLOCK_MONOTONIC, &t2);
}
for (int i = 0; i <= offset; i++) {
    long long kt;
    lseek(fd, i, SEEK_SET);
    clock_gettime(CLOCK_MONOTONIC, &t1);
    kt = write(fd, write_buf, 0); /* runtime in kernel space */
    clock_gettime(CLOCK_MONOTONIC, &t2);
    long long ut = (long long)(t2.tv_sec * 1e9 + t2.tv_nsec)
                - (t1.tv_sec * 1e9 + t1.tv_nsec);
    printf("%d %lld %lld %lld\n", i, kt, ut, ut - kt);
}


## 實作大數運算，使用 [Small/Short String Optimization](http://wdv4758h.github.io/notes/cpp/string-optimization.html) 參考 [](https://github.com/AdrianHuang/fibdrv/blob/big_number/fibdrv_core.c#L69)
### 減法

#### 讓 a > b 並反轉字串

if (xs_size(a) == xs_size(b)) {
    for (int j = 0; j < size_a; j++) {
        if (data_a[j] < data_b[j]) {
            __swap((void *) &a, (void *) &b, sizeof(void *));
            break;
        }
    }
}
else if (xs_size(a) < xs_size(b))
    __swap((void *) &a, (void *) &b, sizeof(void *));

data_a = xs_data(a);
data_b = xs_data(b);

size_a = xs_size(a);
size_b = xs_size(b);

reverse_str(data_a, size_a);
reverse_str(data_b, size_b);

#### 由低位開始做減法

for (i = 0; i < size_b; i++) {
    sum = (data_a[i] - '0') - (data_b[i] - '0') + carry;
    if (sum < 0) {
        sum += 10;
        carry = -1;
    } else {
        carry = 0;
    }
    buf[i] = sum % 10;
}

#### 將大於 b 長度的 a 計算至 buf

for (i = size_b; i < size_a; i++) {
    sum = (data_a[i] - '0') + carry;
    buf[i] = sum % 10;
    carry = 0;
}

#### 去除為0的開頭，將剩餘的部份加上 '0'

while (buf[i] == 0 && i > 0) {
    i--;
}
while (i >= 0) {
    buf[i--] += '0';
    end++;
}

#### 反轉字串

reverse_str(buf, end);
/* Restore the original string */
reverse_str(data_a, size_a);
reverse_str(data_b, size_b);

### 乘法

#### 讓 a > b 並反轉字串

if (xs_size(a) < xs_size(b))
        __swap((void *) &a, (void *) &b, sizeof(void *));

data_a = xs_data(a);
data_b = xs_data(b);

size_a = xs_size(a);
size_b = xs_size(b);

if (a != b) reverse_str(data_a, size_a);
reverse_str(data_b, size_b);

需要判斷 a != b 是因為在 fast doubling，會有 a = b 的情形，只需反轉一次。

#### 將 buf 設置為 0

for (int k = 0; k < size_a + size_b + 1; k++)
        buf[k] = 0;

#### 由低位開始相乘

for (i = 0; i < size_b; i++) {
    for (j = 0; j < size_a; j++) {
        buf[i + j] += (data_a[j] - '0') * (data_b[i] - '0') + carry;
        carry = buf[i + j] / 10;
        buf[i + j] %= 10;

    }
    if (carry) {
        buf[i + j] = carry;
        carry = 0;
    }
}

#### 判定字串結尾位置，並加上 '0'

int end = buf[size_a + size_b - 1] ? size_a + size_b : size_a + size_b - 1;

for (int k = 0; k < end; k++)
    buf[k] += '0';

#### 反轉字串

reverse_str(buf, end);
/* Restore the original string */
if (a != b) reverse_str(data_a, size_a);
reverse_str(data_b, size_b);

## 驗證 F(93) 後的結果

#python3
import sys
expect = [0, 1]
result = []
result_split = []
dics = []
offset = int(sys.argv[1]) + 1
for i in range(2, offset):
    expect.append(expect[i - 1] + expect[i - 2])
with open('out', 'r') as f:
    tmp = f.readline()
    while (tmp):
        result.append(tmp)
        tmp = f.readline()
    f.close()
for r in result:
    if (r.find('Reading') != -1):
        result_split.append(r.split(' '))
        k = int(result_split[-1][5].split(',')[0])
        f0 = int(result_split[-1][9].split('.')[0])
        dics.append((k, f0))
for i in dics:
    fib = i[1] 
    if (expect[i[0]] != fib):
        print('f(%s) fail' % str(i[0]))
        print('input: %s' %(fib))
        print('expected: %s' %(expect[i[0]]))
        exit()
print('pass')

Reading from /dev/fibonacci at offset 998, returned the sequence 16602747662452097049541800472897701834948051198384828062358553091918573717701170201065510185595898605104094736918879278462233015981029522997836311232618760539199036765399799926731433239718860373345088375054249.
Reading from /dev/fibonacci at offset 999, returned the sequence 26863810024485359386146727202142923967616609318986952340123175997617981700247881689338369654483356564191827856161443356312976673642210350324634850410377680367334151172899169723197082763985615764450078474174626.
Reading from /dev/fibonacci at offset 1000, returned the sequence 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875.