# Linux 核心設計 Homework3 (lab3)
contributed by < r34796Kevin >
## 簡介
實作Jserv老師的[Linux 核心設計 (Linux Kernel Internals)](http://wiki.csie.ncku.edu.tw/linux/schedule)的[作業3](https://hackmd.io/@sysprog/linux2021-fibdrv#J06-fibdrv),並且盡量完成作業的額外要求
- [x] 研讀上述 ==Linux 效能分析的提示== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
- [x] 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
- [x] 複習 C 語言 [數值系統](https://hackmd.io/@sysprog/c-numerics) 和 [bitwise operation](https://hackmd.io/@sysprog/c-bitwise)，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本;
- [x] 研讀 [KYG-yaya573142 的報告](https://hackmd.io/@KYWeng/rkGdultSU)，指出針對大數運算，有哪些加速運算和縮減記憶體操作成本的舉措？
- [ ] `lsmod` 的輸出結果有一欄名為 `Used by`，這是 "each module's use count and a list of referring modules"，但如何實作出來呢？模組間的相依性和實際使用次數 ([reference counting](https://en.wikipedia.org/wiki/Reference_counting)) 在 Linux 核心如何追蹤呢？
- [ ] 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 [POSIX Thread](https://en.wikipedia.org/wiki/POSIX_Threads) 的程式碼來確認。
- [x] 在 GitHub 上 fork [fibdrv](https://github.com/sysprog21/fibdrv)，目標是修正 Fibonacci 數計算的正確性 (現有實作存在缺陷，請指出)，隨後改善 `fibdrv` 計算 Fibinacci 數列的執行效率，過程中需要量化執行時間，可在 Linux 核心模組和使用層級去測量
* 原本的程式碼只能列出到 Fibonacci(100) 而且==部分輸出是錯誤的數值==，請修改程式碼，列出後方更多數值 (注意: 檢查正確性和數值系統的使用)
* 務必研讀上述 ==Linux 效能分析的提示== 的描述，降低效能分析過程中的干擾;
* 在 Linux 核心模組中，可用 ktime 系列的 API;
* 在 userspace 可用 [clock_gettime](https://linux.die.net/man/2/clock_gettime) 相關 API;
* 善用統計模型，除去極端數值，過程中應詳述你的手法
* 分別[用 gnuplot 製圖](https://hackmd.io/@sysprog/Skwp-alOg)，分析 Fibonacci 數列在核心計算和傳遞到 userspace 的時間開銷，單位需要用 us 或 ns (自行斟酌)
* 嘗試解讀上述實驗的時間分佈，特別是隨著 Fibonacci 數列增長後，對於 Linux 核心的影響。可修改 VFS 函式，允許透過寫入 `/dev/fibonacci` 裝置檔案來變更不同的 Fibonacci 求值的實作程式碼。
- [x] 逐步最佳化 Fibonacci 的執行時間，引入[費氏數列分析](https://hackmd.io/@sysprog/fibonacci-number) 提到的策略，並善用 [clz / ffs](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令 (Linux 核心有對應的包裝函式)，過程中都要充分量化
- [x] 嘗試研讀 [bignum](https://github.com/0xff07/bignum/tree/fibdrv) (`fibdrv` 分支) 的實作，理解其中的技巧並與你的實作進行效能比較，探討個中值得取鏡之處。
* 原理和分析可見 [KYG-yaya573142 的報告](https://hackmd.io/@KYWeng/rkGdultSU)
## 實作
Fibonacci數列定義為
$$
F_{n}=F_{n-1}+F_{n-2}, \text{ where } F_{0}=0, F_{1}=1.
$$
```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];
}
```
```
r34796@r34796-PS63-Modern-8RC:~/kevin/linux2021/fibdrv$ git commit
Dangerous function detected in /home/r34796/kevin/linux2021/fibdrv/fibdrv.c
71: sprintf(tmp, "%lld\n", runtime);
Read 'Common vulnerabilities guide for C programmers' carefully.
https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml
```
### 排除效能分析上干擾因素
考量到[Processor affinity](https://en.wikipedia.org/wiki/Processor_affinity)，讓行程 (process) 在特定的 CPU 核心中持續執行，不受作業系統排程的干擾。
查看指定行程的處理器親和性，可使用 `taskset` 加上 `-p `參數再加上該行程的 `PID`（process ID）：
目前PID 1的行程可以被作業系統排程安排在CPU0~7上。
```
r34796@r34796-PS63-Modern-8RC:/etc/default$ taskset -cp 1
pid 1 目前的近似者清單：0-7
```
修改 `/etc/default/grub` 內的 `GRUB_CMDLINE_LINUX_DEFAULT`，加入 `isolcpus=7` 來指定編號 7 的核心不被排程器賦予任務，修改完成後需 `sudo update-grub` 來更新設定，重開機後即生效。
重新使用`taskset -cp 1`查看，目前PID 1的行程可以被作業系統排程安排在CPU0~6上。
```
r34796@r34796-PS63-Modern-8RC:~$ taskset -cp 1
pid 1 目前的近似者清單：0-6
```
#### 將程式固定在特定的 CPU 中執行
透過指定處理器親和性 (processor affinity，亦稱 CPU pinning)，可以將程式固定在特定的 CPU 中執行
```shell
$ sudo taskset -c 7 ./client
```
#### 抑制 [address space layout randomization](https://en.wikipedia.org/wiki/Address_space_layout_randomization) (ASLR)
```shell
$ sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
```
#### 針對 Intel 處理器，關閉 turbo mode
```shell
$ sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
```
### 實作效能分析
在 Linux 核心模組中，可用 ktime 系列的 API;我挪用`read function`來輸出上一次 fib 的執行時間。
```c=
static ssize_t fib_read(struct file *file,
char *buf,
size_t size,
loff_t *offset)
{
ktime_t start = ktime_get();
ssize_t re = fib_sequence(*offset);
ktime_t end = ktime_get();
ktime_t runtime = ktime_sub(end, start);
char tmp[128];
memset(tmp, 0, 128);
snprintf(tmp, sizeof(tmp), "%lld\n", runtime);
// strncpy(buf,tmp,128);
copy_to_user(buf, tmp, 128);
return re;
}
```
在 userspace 可用 clock_gettime 相關 API;
```c=
for (int i = 0; i <= offset; i++) {
struct timespec start, end;
lseek(fd, i, SEEK_SET);
clock_gettime(CLOCK_REALTIME, &start);
sz = read(fd, buf, sizeof(buf));
clock_gettime(CLOCK_REALTIME, &end);
printf("Reading from " FIB_DEV
" at offset %d, returned the sequence "
"%lld.\n",
i, sz);
long long ut = (long long) (end.tv_sec * 1e9 + end.tv_nsec) -
(start.tv_sec * 1e9 + start.tv_nsec);
//得到的執行時間寫進time.txt
fprintf(fp, "%d %lld %lld\n", i, ut, atoll(buf));
}
```
在[Linux man page](https://linux.die.net/man/3/clock_gettime)中提到
```
Sufficiently recent versions of GNU libc and the Linux kernel support the following clocks:
CLOCK_REALTIME
System-wide realtime clock. Setting this clock requires appropriate privileges.
CLOCK_MONOTONIC
Clock that cannot be set and represents monotonic time since some unspecified starting point.
CLOCK_PROCESS_CPUTIME_ID
High-resolution per-process timer from the CPU.
CLOCK_THREAD_CPUTIME_ID
Thread-specific CPU-time clock.
```
在這邊我使用`CLOCK_REALTIME`會產生不正確的結果如下：
如果使用`CLOCK_MONOTONIC`可以修正這個問題：
### 撰寫script來幫助測量
針對 SMP IRQ affinity 進行設置，盡量避免 CPU 7 去處理 IRQ。
```scala=
CPUID=7
ORIG_ASLR=`cat /proc/sys/kernel/randomize_va_space`
ORIG_GOV=`cat /sys/devices/system/cpu/cpu$CPUID/cpufreq/scaling_governor`
ORIG_TURBO=`cat /sys/devices/system/cpu/intel_pstate/no_turbo`
sudo bash -c "echo 0 > /proc/sys/kernel/randomize_va_space"
sudo bash -c "echo performance > /sys/devices/system/cpu/cpu$CPUID/cpufreq/scaling_governor"
sudo bash -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
#measure the performance of fibdrv
make all
make unload
make load
sudo taskset -c 7 ./client
gnuplot showtime.gp
make unload
# restore the original system settings
sudo bash -c "echo $ORIG_ASLR > /proc/sys/kernel/randomize_va_space"
sudo bash -c "echo $ORIG_GOV > /sys/devices/system/cpu/cpu$CPUID/cpufreq/scaling_governor"
sudo bash -c "echo $ORIG_TURBO > /sys/devices/system/cpu/intel_pstate/no_turbo"
```
將`userspace`得到的時間減去`kernelspace`得到的時間，可以測量`System Call`的時間開銷，我測得的時間約為340ns。
到這裡就能正確進行效能分析的實驗，然而儲存Fibonacci數列的資料型態為`long long`，只能儲存64位元的資料，因此F~92~之後的數值會產生overflow，於是接下來實作可以儲存任意精度的數值系統（Big Num）
## 大數運算
由於計算Fibonacci數列只會用到正整數運算，所以接下來的數值系統實作中運算子（加減乘除）都是針對正整數做運算。
### 資料結構
為了能夠儲存任意精度，定義一個資料結構`bigN`，`unsigned int *d`指向配置的記憶體位置，`int size`紀錄使用了幾個`unsigned int`來儲存數值。
```c=
typedef struct bigN {
unsigned int *d;
int size; // lenths of array d
} bigN;
```
### bigN_to_string
有了資料結構後，要使我們儲存的資料有意義，要可以將儲存的資料轉換為看得懂的數值，實作一個function將`bigN`轉換成`string`。
若一個`bigN`使用了x個位元儲存資料，最多可以換算成$\ulcorner log_{10}(2^{x})\urcorner$位數，
e.g. 若一個`bigN`使用了8個位元儲存資料，最多可以儲存$2^{8}-1=255$也就是$\ulcorner log_{10}(255)\urcorner$ = 3位數。
```c=
char *bigN_to_string(bigN *src)
{
// log10(x) = log2(x) / log2(10) ~= log2(x) / 3.322
size_t len = (8 * sizeof(int) * src->size) / 3 + 2;
char *s = (char *) kmalloc(len, GFP_KERNEL);
char *p = s;
memset(s, '0', len - 1);
s[len - 1] = '\0';
for (int i = src->size - 1; i >= 0; i--) {
for (unsigned int mask = 1U << 31; mask; mask >>= 1) {
/* binary -> decimal string */
int carry = ((mask & src->d[i]) != 0);
for (int j = len - 2; j >= 0; j--) {
s[j] += s[j] - '0' + carry; // double it
carry = (s[j] > '9');
if (carry)
s[j] -= 10;
}
}
}
// skip leading zero
while (p[0] == '0' && p[1] != '\0') {
p++;
}
memmove(s, p, strlen(p) + 1);
return s;
}
```
二進位轉十進位的時候，使用一個`mask`一一取出most sinificant bit，取出下一個bit的時候要將之前的數值乘2才能正確解讀數值，e.g. 二進位數值1101 取出第一個bit 1，此時string儲存1，取出第二個bit 1，此時string應儲存$3 (1*2+1)$，取出第三個bit 0，此時string應儲存$6(3*2+0)$，取出第四個bit 1，此時string應儲存$13(6*2+1)$。
### bigN初始化
由於`bigN`是儲存記憶體位置，故需要搭配使用`bigNinit`函式配置記憶體位置以及數值。
```c=
bigN *bigNinit(unsigned int value)
{
bigN *new = kmalloc(sizeof(bigN), GFP_KERNEL);
new->d = kmalloc(sizeof(unsigned int), GFP_KERNEL);
new->size = 1;
new->d[0] = value;
return new;
}
```
`value`為儲存的數值。
### 加法與減法
兩個`bigN`相加時有可能進位，故要先配置一個大小為`newsize`的記憶體位置來避免overflow。
實作兩個`uint32_t`相加的時候，可以用一個小技巧，用一個`uint64_t`來儲存結果，再使用mask跟位元移位來得到正確的32位元數值與它的進位。
```c=
void bigN_add(bigN *a, bigN *b, bigN *res)
{
int newsize = MAX(a->size, b->size) + 1; // To avoid overflow
// printk("new size is %d",newsize);
uint32_t *result = kmalloc(newsize * sizeof(uint32_t), GFP_KERNEL);
memset(result, 0, sizeof(*result));
uint64_t l = 0;
for (int i = 0; i < newsize; i++) {
uint32_t A = (a->size) > i ? a->d[i] : 0;
uint32_t B = (b->size) > i ? b->d[i] : 0;
l += (uint64_t) A + B;
result[i] = l & 0xFFFFFFFF;
l = l >> 32;
}
kfree(res->d);
// Check the actual size and assign to bigN c
if (result[newsize - 1] == 0) {
// printf("a\n");
newsize--;
res->d = krealloc(result, newsize * sizeof(uint32_t), GFP_KERNEL);
res->size = newsize;
} else {
// printf("b\n");
res->d = result;
res->size = newsize;
}
return;
}
```
減法的實作也差不多。
```c=
static void bigN_sub(bigN *a, bigN *b, bigN *c)
{
bigN_comp(a, b);
int newsize = MAX(a->size, b->size);
unsigned int *result = kmalloc(newsize * sizeof(unsigned int), GFP_KERNEL);
memset(result, 0, sizeof(*result));
kfree(c->d);
c->d = result;
c->size = newsize;
long long int carry = 0;
for (int i = 0; i < c->size; i++) {
unsigned int A = (i < a->size) ? a->d[i] : 0;
unsigned int B = (i < b->size) ? b->d[i] : 0;
carry = (long long int) A - B - carry;
if (carry < 0) {
c->d[i] = carry + (1LL << 32);
carry = 1;
} else {
c->d[i] = carry;
carry = 0;
}
}
bigN_resize(c);
}
```
### 乘法
目前採用最簡單的 long multiplication，就像手算乘法一樣疊加上去，輔助函式 `bigN_mul_add `負責將每一行的計算結果疊加上去。
```c=
static void bigN_mul(bigN *a, bigN *b, bigN *c)
{
int newsize = (a->size) * (b->size) + 1; // avoid overflow
unsigned int *result = kmalloc(newsize * sizeof(unsigned int), GFP_KERNEL);
memset(result, 0, sizeof(*result));
kfree(c->d);
c->d = result;
c->size = newsize;
uint64_t l;
for (int i = 0; i < a->size; i++) {
for (int j = 0; j < b->size; j++) {
uint32_t A = (a->size) > i ? a->d[i] : 0;
uint32_t B = (b->size) > j ? b->d[j] : 0;
l = (uint64_t) A * (uint64_t) B;
bigN_mul_add(c, i + j, l);
}
}
bigN_resize(c);
}
```
```c=
static void bigN_mul_add(bigN *c, int offset, uint64_t l)
{
uint64_t carry = 0;
for (int i = offset; i < c->size; i++) {
carry += c->d[i] + (l & 0xFFFFFFFF);
c->d[i] = carry;
carry >>= 32;
l >>= 32;
if (!l && !carry) // done
return;
}
}
```
### big num其他輔助函式
釋放bigN記憶體。
```c=
static void bigN_free(bigN *a)
{
kfree(a->d);
kfree(a);
return;
}
```
交換兩個bigN的數值。
```c=
static void bigN_swap(bigN *a, bigN *b)
{
bigN tmp = *a;
*a = *b;
*b = tmp;
return;
}
```
比較兩個bigN的數值，並返回A=大的，B=小的。
```c=
static void bigN_comp(bigN *a, bigN *b)
{
if (a->size > b->size) {
return;
} else if (a->size < b->size) {
bigN_swap(a, b);
} else { // a->size = b->size
int i = a->size - 1;
// compare value
if (a->d[i] < b->d[i]) {
bigN_swap(a, b);
}
}
}
```
做加法或乘法時為了避免overflow會多分配記憶體空間，`bigN_resize`可以調整記憶體空間為剛剛好。
```c=
static void bigN_resize(bigN *a)
{
int i = a->size - 1;
while (a->d[i] == 0) {
i--;
}
a->d = krealloc(a->d, (i + 1) * sizeof(uint32_t), GFP_KERNEL);
a->size = i + 1;
}
```
### 實作大數版本的Fibonacci數列
有了數值系統之後，就可以實作大數版本的Fibonacci數列，先實作一般的Fibonacci運算。時間複雜度為O(n)。
```c=
static bigN *bigNfib_sequence(long long k)
{
/* FIXME: use clz/ctz and fast algorithms to speed up */
bigN *a = bigNinit(0);
bigN *b = bigNinit(1);
bigN *c = bigNinit(1);
for (int i = 2; i <= k; i++) {
bigN_add(a, b, c); // a + b = c
bigN_swap(a, b);
bigN_swap(b, c);
}
// bigN_copy(b,ans);
bigN_free(a);
bigN_free(c);
return b;
}
```
如此一來便可以正確計算$F_{92}$之後的數值，試著計算第500項得到的數字與[The first 1001 Fibonacci Numbers](http://www.fullbooks.com/The-first-1001-Fibonacci-Numbers.html)相同。
```
Reading from /dev/fibonacci at offset 500, returned the sequence
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125.
```
### 實作大數版本的Fibonacci數列 (Fast Doubling)
研讀[Calculating Fibonacci Numbers by Fast Doubling ](https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling)後了解到還有一種方法可以時間複雜度O(logn)來計算Fibonacci數列。
Fibonacci數列定義為
$$
F_{n}=F_{n-1}+F_{n-2}, \text{ where } F_{0}=0, F_{1}=1.
$$
<!--
將上述推導寫成矩陣的形式就會變成
$$
\begin{pmatrix}
F_{n+1} \\ F_{n}
\end{pmatrix}
=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
F_{n} \\ F_{n-1}
\end{pmatrix}
$$
則 $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ 就是所謂的 ==Q-matrix==，可進一步改寫為:
$$
\begin{pmatrix}
F_{n+1} & F_{n} \\
F_{n} & F_{n-1}
\end{pmatrix} =
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
F_{n} & F_{n-1} \\
F_{n-1} & F_{n-2}
\end{pmatrix}\\
=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}^{2}
\begin{pmatrix}
F_{n-1} & F_{n-2} \\
F_{n-2} & F_{n-3}
\end{pmatrix}\\
=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}^{n-1}
\begin{pmatrix}
F_{2} & F_{1} \\
F_{1} & F_{0}
\end{pmatrix}\\
=\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}^{n} =Q^{n}
$$
繼續整理:
$$
\begin{split}
\begin{bmatrix}
F_{2n+1} \\
F_{2n}
\end{bmatrix} &=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^{2n}
\begin{bmatrix}
1 \\
0
\end{bmatrix}\\ \\ &=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n
\begin{bmatrix}
1 \\
0
\end{bmatrix}\\ \\ &=
\begin{bmatrix}
F_{n+1} & F_{n} \\
F_{n} & F_{n-1}
\end{bmatrix}
\begin{bmatrix}
F_{n+1} & F_{n} \\
F_{n} & F_{n-1}
\end{bmatrix}
\begin{bmatrix}
1 \\
0
\end{bmatrix}\\ \\ &=
\begin{bmatrix}
F_{n+1}^2 + F_{n}^2\\
F_{n}F_{n+1} + F_{n-1}F_{n}
\end{bmatrix}
\end{split}
$$
因此可得:
$$
\begin{split}
F(2k) &= F(k)[2F(k+1) - F(k)] \\
F(2k+1) &= F(k+1)^2+F(k)^2
\end{split}
$$
-->
接下來實作大數版本的Fast Doubling。
```c=
static bigN *bigN_fib_fdoubling(unsigned int n)
{
// The position of the highest bit of n.
// So we need to loop `h` times to get the answer.
// Example: n = (Dec)50 = (Bin)00110010, then h = 6.
// ^ 6th bit from right side
unsigned int h = 0;
for (unsigned int i = n; i; ++h, i >>= 1)
;
bigN *f0 = bigNinit(0);
bigN *f1 = bigNinit(1);
bigN *a = bigNinit(1);
bigN *b = bigNinit(1);
bigN *f2k = bigNinit(1);
bigN *f2k1 = bigNinit(1);
for (unsigned int mask = 1 << (h - 1); mask; mask >>= 1) {
/* F(2k) = F(k) * [ 2 * F(k+1) – F(k) ] */
bigN_add(f1, f1, a); // a = 2f1
bigN_sub(a, f0, b); // b = 2f1-f0
bigN_mul(f0, b, f2k); // f(2k)
/* F(2k+1) = F(k)^2 + F(k+1)^2 */
bigN_mul(f0, f0, a); // a = f(k)^2
bigN_mul(f1, f1, b); // b = f(k+1)^2
bigN_add(a, b, f2k1); // f(2k+1)
if (mask & n) {
bigN_copy(f2k1, f0);
bigN_add(f2k, f2k1, f1);
} else {
bigN_copy(f2k, f0);
bigN_copy(f2k1, f1);
}
}
bigN_free(f1);
bigN_free(a);
bigN_free(b);
bigN_free(f2k);
bigN_free(f2k1);
return f0;
}
```
重新測量可以看到運行時間大幅減少，Iterative方法時間複雜度為O(n)，Fast Doubling方法時間複雜度為O(logn)。
這邊已經大幅降低計算Fibonacci數列的時間，接下來在Fast Doubling方法下繼續做最佳化。
### 考慮到硬體加速的手法
許多現代處理器提供 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令，可搭配上述 [Fast Doubling](https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling) 手法運用:
```c=
//unsigned int h = 0;
//for (unsigned int i = n; i; ++h, i >>= 1);
unsigned int h=32-__builtin_clz(n);
```
這樣可以更求出leading 1 bit在右邊數來第幾個bit。
因為這個運算在整個大數版本的Fast Doubling演算法中佔比很小，所以得到的加速很小。
### 使用左移運算取代加法
Fast Doubling運算中需要求出2f1的運算可以使用左移運算取代。
```c=
//bigN_add_op(f1, f1, a);
bigN_ls(f1,a);
```
```c=
void bigN_ls(bigN* a, bigN* b)
{
uint32_t mask =1<<31;
int size = a->size;
int overflow = 0;
overflow = ((a->d[size - 1]) & mask) != 0 ;
if(b->size < size ){
if (overflow){
size++;
}
b->size = size;
uint32_t *result = kmalloc(size * sizeof(uint32_t), GFP_KERNEL);
uint64_t l = 0;
for (int i = 0; i < size; i++) {
uint32_t A = (a->size) > i ? a->d[i] : 0;
l = ((uint64_t)A << 1) + l;
result[i] = l & 0xFFFFFFFF;
l >>= 32;
}
kfree(b->d);
b->d = result;
}
else if((b->size == size) && overflow){
if (overflow){
size++;
}
b->size = size;
uint32_t *result = kmalloc(size * sizeof(uint32_t), GFP_KERNEL);
uint64_t l = 0;
for (int i = 0; i < size; i++) {
uint32_t A = (a->size) > i ? a->d[i] : 0;
l = ((uint64_t)A << 1) + l;
result[i] = l & 0xFFFFFFFF;
l >>= 32;
}
kfree(b->d);
b->d = result;
}
else
{
uint64_t l = 0;
for (int i = 0; i < b->size; i++) {
uint32_t A = (a->size) > i ? a->d[i] : 0;
l = ((uint64_t)A << 1) + l;
b->d[i] = l & 0xFFFFFFFF;
l >>= 32;
}
}
}
```
紫色的線段使用上了左移運算以及硬體支援的clz運算，得到了更進一步的加速。
### 引入memory pool
原本的運算上都直接分配一個新的記憶體空間，將舊的記憶體空間釋放，頻繁的這樣操作導致效能下降。例如：
```c=
unsigned int *result = kmalloc(newsize * sizeof(unsigned int), GFP_KERNEL);
memset(result, 0, sizeof(*result));
kfree(c->d);
c->d = result;
```
所以我重新寫過所有的運算，如果非必要(例如值會溢位)，否則都寫入原本分配的記憶體空間。
並且使用新的資料結構加入memory pool的概念
```c=
typedef struct bigN_op {
unsigned int *d;
int capacity;
int size; // lenths of array d
} bigN_op;
```
一開始就分配比較大的陣列給資料，減少值會溢位的情況。capacity紀錄總共可以使用的陣列，size紀錄目前的資料需要幾個unsigned int來儲存。
在計算比較小的(200)Fibonacci數列計算效率可以有 **50%** 的提昇。
在計算比較大的(1000)Fibonacci數列計算效率也有 **20%** 的提昇。
(因為Fast Doubling方法時間複雜度為O(logn)，數列越大提昇越有限)。
在Iterative方法中也是50%的提昇。
Sign in with Wallet
Connect another wallet