---
tags: linux2022
---
# 2022q1 Homework3 (fibdrv)
contributed by < `bebo1010` >
## 實驗環境
```shell
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04) 9.4.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 43 bits physical, 48 bits virtual
CPU(s): 24
On-line CPU(s) list: 0-23
Thread(s) per core: 2
Core(s) per socket: 12
Socket(s): 1
NUMA node(s): 1
Vendor ID: AuthenticAMD
CPU family: 23
Model: 113
Model name: AMD Ryzen 9 3900X 12-Core Processor
Stepping: 0
Frequency boost: enabled
CPU MHz: 3800.000
CPU max MHz: 4672.0698
CPU min MHz: 2200.0000
BogoMIPS: 7586.05
Virtualization: AMD-V
L1d cache: 384 KiB
L1i cache: 384 KiB
L2 cache: 6 MiB
L3 cache: 64 MiB
NUMA node0 CPU(s): 0-23
```
## 作業要求
### 費式數列計算
原本程式碼如下
實際測試時發現算到第 93 個的時候就會因為 overflow 出錯，因此需要處理 overflow 問題
但我想先嘗試撰寫 [fast doubling](https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling) 的做法
```c
static long long fib_sequence(long long k)
{
/* FIXME: C99 variable-length array (VLA) is not allowed in Linux kernel. */
long long f[k + 2];
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= k; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f[k];
}
```
底下是我根據上面資料的程式碼複製貼上後再稍微進行效能改進的結果
改進點有兩點:
* `if (n % 2)` 改為 `if (n & 1)` 來減少不必要的除法運算
* `k = (n - 1) / 2;` 改為 `k = (n - 1) >> 1;`，和第一點相同的概念
```c
static long long fib(long long n)
{
// base case
if (n == 0)
return 0;
if (n == 1 || n == 2)
return 1;
long long k = 0;
if (n & 1) { // if k is even, use bit-wise to prevent modulo operator
k = (n - 1) >> 1; // use right shift to perform divide by 2
return fib(k) * fib(k) + fib(k + 1) * fib(k + 1);
} else {
k = n >> 1;
return fib(k) * (2 * fib(k + 1) - fib(k));
}
}
static long long fib_sequence(long long k)
{
return fib(k);
}
```
接下來我再針對計算費式數列時會重複計算到的部分先用陣列儲存起來
再遇到重複的部份時才不需要多次呼叫遞迴
* INIT_VALUE 設為 4 是因為費式數列不包含 4 這個數字
```c
#include <linux/slab.h>
...
static const uint64_t INIT_VALUE = 4;
static const uint32_t ARRAY_SIZE = 1000;
static long long fib(long long n, uint64_t *fib_array)
{
if (fib_array[n] != INIT_VALUE)
return fib_array[n];
long long k = n >> 1;
long long a = fib(k, fib_array);
long long b = fib(k + 1, fib_array);
fib_array[n] = (n & 1) ? (a * a + b * b) : a * (2 * b - a);
return fib_array[n];
}
static long long fib_sequence(long long k)
{
// TODO: problem at long long integer overflow
uint64_t *fib_array = kmalloc(sizeof(uint64_t) * ARRAY_SIZE, GFP_KERNEL);
fib_array[0] = 0; // set base case value first
fib_array[1] = 1;
fib_array[2] = 1;
for (int i = 3; i < ARRAY_SIZE; i++) {
fib_array[i] = INIT_VALUE;
}
uint64_t return_value = fib(k, fib_array);
kfree(fib_array);
return return_value;
}
```
::: info
[kmalloc](https://www.kernel.org/doc/htmldocs/kernel-api/API-kmalloc.html) 和 [kfree](https://www.kernel.org/doc/htmldocs/kernel-api/API-kfree.html) 定義於 <linux/slab.h> 底下，是 kernel space 的 malloc 和 free
:::
接著修改原本程式碼，修改成可以進行大數運算的版本
參考 [ChunMinChang](https://github.com/AdrianHuang/fibdrv/tree/big_number) 的程式碼以及[這篇資料](https://www.tutorialspoint.com/multiply-large-numbers-represented-as-strings-in-cplusplus)進行修改
### Fibonacci Generating Function
今天(6月13日)看 [`3blue1brown` 的影片](https://youtu.be/bOXCLR3Wric?t=603)時注意到了費式數列也可寫成 `Generating Function` 的形式，因此我花時間了解如何透過這種表示式讓計算費式數列可以變成一個簡單的式子。
他將費式數列寫成以下多項式的形式(也就是 `generating function`)：
$F(x) = 0 + 1x^1 + 1x^2 + 2x^3 + 3x^4 + 5x^5 + \cdots$
也就是
$F(x) = F_0*x^0 + F_1*x^1 + F_2*x^2 + F_3*x^3 + F_4*x^4 + F_5*x^5 + \cdots$
$F_0$ 代表費式數列中第 $0$ 項，$F_1$ 代表費式數列中第 $1$ 項，依此類推
---
接下來的部分我參考了[這篇文章](https://austinrochford.com/posts/2013-11-01-generating-functions-and-fibonacci-numbers.html)以及[這部影片](https://www.youtube.com/watch?v=1116q780goA)
這兩份資料的內容起點不太相同，但是手法類似。
* 首先將前面的 $F(x)$ 改用 $\sum$ 的形式表示
$F(x) = \sum_{n=0}^{\infty}F_n*x^n$
* 由於$F_0 = 0$，可改寫成以下形式
$F(x) = \sum_{n=1}^{\infty}F_n*x^n$
* 將 $n = 1$ 的項提取出來
$F(x) = F_1*x+ \sum_{n=2}^{\infty}F_n*x^n = x + \sum_{n=2}^{\infty}F_n*x^n$
* 把 $F_n$ 改寫為 $F_n = F_{n-1} + F_{n-2}$ ，並且透過分配律展開
$F(x) = x + \sum_{n=2}^{\infty}(F_{n-1} + F_{n-2})*x^n = x + \sum_{n=2}^{\infty}F_{n-1}*x^n + \sum_{n=2}^{\infty}F_{n-2}*x^n$
* 調整 $\sum_{n=2}^{\infty}F_{n-1}*x^n$ 這項的 index，並且整理成 $F(x)$ 的形式
$\sum_{n=2}^{\infty}F_{n-1}*x^n = x*\sum_{n=2}^{\infty}F_{n-1}*x^{n-1} = x*\sum_{n=1}^{\infty}F_n*x^n$
$x*\sum_{n=1}^{\infty}F_n*x^n = x*(0 + F_0x^0 + \sum_{n=1}^{\infty}F_n*x^n) = x*\sum_{n=0}^{\infty}F_n*x^n =
x * F(x)$
* 同上步驟整理 $\sum_{n=2}^{\infty}F_{n-2}*x^n$
$\sum_{n=2}^{\infty}F_{n-2}*x^n = x^2*\sum_{n=2}^{\infty}F_{n-2}*x^{n-2} = x^2*\sum_{n=0}^{\infty}F_n*x^n =
x^2 * F(x)$
* 因此原式轉成以下式子
$F(x) = x + xF(x) + x^2F(x)$
* 經過移項整理後得到
$(1 - x - x^2)F(x) = x$
* 因此 $F(x) = \frac{x}{1-x-x^2}$
---
* 接著針對 $F(x)$ 的結果做分解，目標是分解成兩個分母為一次式的式子因此先將為二次式的分母分解，將分母以公式解拆開成兩個部分
$F(x) = \frac{x}{-(x-\alpha)(x-\beta)} = \frac{A}{(x-\alpha)} + \frac{B}{(x-\beta)}$
其中的 $\alpha$ 和 $\beta$ 為以下數值
$\alpha = \frac{-1-\sqrt{5}}{2}$ ， $\beta = \frac{-1+\sqrt{5}}{2}$
* 將算式右半部做交叉相乘，並與左邊比較
$\frac{x}{-(x-\alpha)(x-\beta)} = \frac{-[A(x-\beta) + B(x-\alpha)]}{-(x-\alpha)(x-\beta)}$
$x = -(A(x - \beta) + B(x - \alpha))$
* 接著透過代入 $x = \alpha$ 得到 $A = \frac{\alpha}{\beta - \alpha} = \frac{\alpha}{\sqrt{5}}$
* 同樣方法代入 $x = \beta$ 得到 $B = \frac{\beta}{\alpha - \beta} = \frac{\beta}{-\sqrt{5}}$
* 因此得到下式
$F(x) = \frac{1}{\sqrt{5}}(\frac{\alpha}{(x-\alpha)}-\frac{\beta}{(x-\beta)})$
---
* 接著嘗試把 $F(x)$ 表示成等比級數的形式，會使用到以下等比級數的性質
$\sum_{n=0}^{k}a^n = \frac{1(1-a^{k+1})}{1-a}$
當 $|a| < 1$ 且 $k \rightarrow \infty$ 時，$\sum_{n=0}^{k}a^n = \frac{1(1-a^{k+1})}{1-a}$ 可改寫成 $\sum_{n=0}^{\infty}a^n = \frac{1}{1-a}$
* 同時，$\alpha*\beta = -1$
有了以上性質後，開始改寫上部分的 $F(x)$
* 先從 $\frac{\alpha}{(x-\alpha)}$ 開始，分子分母同除 $\alpha$
$\frac{\alpha}{(x-\alpha)} =
\frac{1}{1-\frac{x}{\alpha}} =
\frac{1}{1+\beta{x}} =
\sum_{n=0}^{\infty}{(-\beta{x})}^n =
\sum_{n=0}^{\infty}{(-\beta)^nx^n}$
* 同理，$\frac{\beta}{(x-\beta)}$ 可化為以下形式
$\frac{\beta}{(x-\beta)} = \sum_{n=0}^{\infty}{(-\alpha)^nx^n}$
* 因此原式可改寫成以下形式
$F(x) = \frac{1}{\sqrt{5}}(\frac{\alpha}{(x-\alpha)}-\frac{\beta}{(x-\beta)}) =
\frac{1}{\sqrt{5}}(\sum_{n=0}^{\infty}(-\beta)^n{x^n} - \sum_{n=0}^{\infty}(-\alpha)^n{x^n}) =
\sum_{n=0}^{\infty}\frac{1}{\sqrt{5}}((-\beta)^n - (-\alpha)^n){x^n}$
* 對照最早寫出的算式得出以下結果
$F(x) =
\sum_{n=0}^{\infty}F_n*x^n =
\sum_{n=0}^{\infty}\frac{1}{\sqrt{5}}((-\beta)^n - (-\alpha)^n){x^n}$
$\therefore F_n = \frac{1}{\sqrt{5}}((-\beta)^n - (-\alpha)^n)$
其中 $\alpha = \frac{-1-\sqrt{5}}{2}$ ， $\beta = \frac{-1+\sqrt{5}}{2}$
由此得出費式數列第 $n$ 項的公式
:::danger
以上證明結果已知是錯誤的，從針對 $F(x)$ 的分解開始有錯誤
已知代入算式後結果必為負的，但我能力不足以找出證明錯誤從何處開始發生
:::
---
接著我想到一個問題，使用了這種公式解，在 C 語言內想必只能用 double 儲存。
用 double 儲存的話會遇到一些問題
1. overflow and underflow
$|\alpha| > 1$，$|\alpha^{n}|$ 會越來越大，可能會發生 overflow
相對的，$|\beta| > 1$，$|\beta^{n}|$ 會越來越小，可能會發生 underflow
2. rounding error
浮點數計算時會因為每個步驟計算都具有一定誤差，多次重覆計算後導致數值錯誤
因此我想嘗試找出從第幾個 $F_n$ 會開始出現誤差
:::danger
注意以下程式中輸出有經過絕對值運算，原因如上述
:::
```c
//fibonacci_limit.c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
double fib(const int n);
int main()
{
int n = 0;
for(n = 0; n < 100; n++)
printf("%d. %.0lf\n", n, fib(n));
}
double fib(const int n)
{
double constant = 1.0 / sqrt(5.0);
double alpha = (-1.0 - sqrt(5.0)) / (2.0);
double beta = (-1.0 + sqrt(5.0)) / (2.0);
return fabs(constant * (pow(-1.0 * beta, (double) n) - pow(-1.0 * alpha, (double) n)));
}
```
底下用到的 `fib.txt` 是我預先準備的，裡面紀錄了 $F(0) \sim F(100)$ 的正確費式數列數值
```shell
$ gcc fibonacci_limit.c -o fibonacci_limit -lm
$ ./fibonacci_limit > output.txt
$ diff -y output.txt fib.txt
...
66. 27777890035288 66. 27777890035288
67. 44945570212853 67. 44945570212853
68. 72723460248141 68. 72723460248141
69. 117669030460994 69. 117669030460994
70. 190392490709135 70. 190392490709135
71. 308061521170130 | 71. 308061521170129
72. 498454011879265 | 72. 498454011879264
73. 806515533049395 | 73. 806515533049393
74. 1304969544928660 | 74. 1304969544928657
...
```
由於浮點數運算的 rounding error ，讓這個算法從 $F(71)$ 開始就會出現誤差。
### 排除干擾效能分析的因素
#### 限定 CPU 給特定程式使用
此部分按照[作業要求](https://hackmd.io/@sysprog/linux2022-fibdrv#-Linux-%E6%95%88%E8%83%BD%E5%88%86%E6%9E%90%E7%9A%84%E6%8F%90%E7%A4%BA)中的指示以及 [KYG-yaya573142](https://hackmd.io/@KYWeng/rkGdultSU#%E6%8E%92%E9%99%A4%E5%B9%B2%E6%93%BE%E6%95%88%E8%83%BD%E5%88%86%E6%9E%90%E7%9A%84%E5%9B%A0%E7%B4%A0) 提供的方法去設置
首先修改 `/etc/default/grub` 內的 `GRUB_CMDLINE_LINUX_DEFAULT` ，加入 `isolcpus=12-23` 指定不指派任何任務到編號 12 到 編號 23 的 CPU 核心
```
GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=12-23"`
```
修改完後輸入 `sudo update-grub`更新設定並且重開機
接著透過以下指令測試是否設定成功
看到 `/sys/devices/system/cpu/isolated` 內有 12-23 且 PID 為 1 的 process 沒有占用到 12-23 即設定完成
```shell
$ cd ~
$ cat /sys/devices/system/cpu/isolated
12-23
$ taskset -cp 1
pid 1's current affinity list: 0-11
```
::: info
將 12-23 都獨立出來是考量到當前 CPU 會有邏輯處理器的特性
機器 CPU 實際 12 核，但邏輯處理器有 24
正常情況下應該第 12 個核心對應到邏輯處理器的 22-23
但我無法確定，因此透過這方式確保只有一個實體核心執行程式
:::
#### 讓程式在特定的 CPU 執行
使用以下指令讓 client 程式在編號 23 的 CPU 執行
```shell
sudo taskset -c 23 ./client
```
::: info
任何使用者都可用 taskset 查詢 process 使用的 CPU 編號
但只有 root 可以修改 process 可使用的 CPU
:::
#### 抑制 address space layout randomization (ASLR)
```shell
$ sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
```
::: info
address space layout randomization 是一個將 process 的重要資料隨機打亂的作法
目的是為了避免有心人士刻意跳到不該存取的記憶體位置
:::
#### 設定 scaling_governor 為 performance
準備一份 `performance.sh` 讓 CPU 可以用最高頻率執行程式
```shell
for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
do
echo performance > /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
done
```
#### 關閉 turbo mode
```shell
sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
```
## 課程筆記
### Week 3 C 語言: 函式呼叫
C 語言不允許 nested function，但之前的程式語言可以
C++ template metaprogramming
compile-time polymorphism
constant expression(constexpr)
functional programming
malloc() 會優先拿之前用過的記憶體
* 不需要對配置空間歸零的話優先使用 malloc() ，成功機率較大
calloc() 因為要先歸零，作業系統必須要先準備好要配置的記憶體
* 需要對配置空間清零的話優先使用 calloc() ，執行效率較好
### Week 3 C 語言: 遞迴呼叫
[原文連結](https://hackmd.io/@sysprog/c-recursion?type=view#%E6%A1%88%E4%BE%8B%E5%88%86%E6%9E%90%EF%BC%9A%E6%95%B8%E5%88%97%E8%BC%B8%E5%87%BA)
```c
// p.c
#include <limits.h>
#include <stdio.h>
int p(int i, int N) {
return (i < N && printf("%d\n", i) && !p(i + 1, N)) \
|| printf("%d\n", i);
}
int main() {
return p(0, INT_MAX);
}
```
提到一個延伸問題：`i` 和 `N` 組合的有效上下界為何？
我用我的機器找到的結果為以下
```shell
261631
261632
segmentation fault
```
借用共筆內原本的結果，理論最大值為`262144`
而我想去了解為何實驗結果和理論值有所差異，因此我去嘗試找出實際上差在哪裡
我先嘗試找出這份程式碼編譯後在 memory layout 中各占多少大小
使用這篇[參考資料](https://blog.gtwang.org/programming/memory-layout-of-c-program/)輔助我了解
```shell
$ gcc p.c
$ size a.out
text data bss dec hex filename
1711 600 8 2319 90f a.out
```
| text | data | bss | dec | hex |
| -------- | -------- | -------- | ----- | ---- |
| 1711 bytes | 600 bytes | 8 bytes | 2319 bytes | 90f(in hex) bytes |
| 程式碼 | 已初始化靜態變數 | 未初始化靜態變數 | 前三個數字加起來的總大小(以十進位表示) | 前三個數字加起來的總大小(以十六進位表示)|
找到這裡我才發現找整個 memory layout 不怎麼合理，應該只要討論 stack size 就好了
text, data, heap 都和 stack size 沒有直接關聯
---
首先我先找出這台機器的 stack size ，確實和預設的 8MB 相同
```shell
$ ulimit -s
8192
```
以下引用原文對於每個細節計算
> 複習 你所不知道的C語言：函式呼叫篇，我們知道為了滿足 x86_64 ABI / calling convention，回傳位址佔 8 bytes, (int) i 和 (int) N 這兩個變數合計 8 bytes, 函式的區域變數 (給 printf() 用的 format string 的位置) 8 bytes, p 回傳值 int 佔 4bytes ，總共 32 bytes。
我認為以上敘述有點問題
* `main()` 的回傳值為 int ，因此多占了 4 bytes，以及回傳位址 8 bytes，總計 12 bytes 應該也要算進去
* `printf()` 的呼叫也需要占用 stack，`printf()` 的回傳值是 int ，需要占用 4 bytes；format string 占用 4 bytes，傳入參數 (int)`i` 占用 4 bytes，再加上回傳位址的 8 bytes，因此總共 20 bytes。在 `printf()` 結束後這些記憶體就會被釋放。
* 同樣的，呼叫一次 `p()` 需要占用 20 bytes 記憶體，但這個部分不會被釋放(必須等到程式開始輸出逐漸變小的數字才會開始釋放)
計算方式如下：
```
12 + (261632 * 20) + (20 + 20) = 5232692
第一部分的 12 bytes 表示 main function 和記錄 main function 的 return address
第二部分表示呼叫了 261632 次的 p() 且尚未 segmentation fault
第三部份表示最後一次的 p() 在執行 printf() 時發生 segmentation fault
但不確定為何數值差距這麼大(8MB = 8388608 bytes)
```
---
我把這份程式碼進行編譯但不組譯，在 assembly code 內找到了 `"%d\n"` (也就是 format string)
format string 會 load 進一個字串到 stack 內
```shell
$ gcc p.c -S #生成 p.c 的 assembly code
$ vim p.s #查看 assembly code
...
.LC0:
.string "%d\n"
.text
.globl p
.type p, @function
...
```
---
### Week 3 C 語言: 前置處理器應用篇
[__generic](https://hackmd.io/@sysprog/c-preprocessor?type=view#_Generic-C11)
### Week 3 C 語言: 技巧篇
Compilation Unit
---
```c
enum cities { Taipei, Tainan, Taichung, };
```
多一個逗號是因為可以方便新增更多內容
---
| `strdup()` | `strdupa()` |
| -------- | -------- |
| 透過 `malloc()` 配置記憶體 | 透過 `alloca()` 配置記憶體 |
| 記憶體配置於 heap | 記憶體配置於 stack |
Sign in with Wallet
Connect another wallet