# 2022q1 Homework3 (fibdrv) contributed by < `Korin777` > ## Linux 效能分析 ### 限定 CPU 給特定的程式使用 1. 在 `/etc/default/grub` 中新增 `isolcpus` 參數 ``` GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=1" ``` 2. 更新 `/boot/grub/grub.cfg` ```shell $ sudo update-grub ``` 3. 重新開機 4. 檢查是否生效 * 查看 `/proc/cmdline` 裡是否有 `isolcpu` 參數 > korin@korin-VivoBook-15-ASUS-Laptop-X542UF:~$ cat /proc/cmdline BOOT_IMAGE=/boot/vmlinuz-5.13.0-30-generic root=UUID=0316da8c-1a94-4511-a7fc-a5133651768b ro quiet splash isolcpus=1 vt.handoff=7 * 最後用 `taskset` 查看 process 的 cpu affinity ， 可以發現它已經不能在第一個 cpu 執行了 > korin@korin-VivoBook-15-ASUS-Laptop-X542UF:~$ taskset -p 1 pid 1's current affinity mask: fd ### 排除干擾效能分析的因素 * 抑制 [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" ``` * 設定 scaling_governor 為 performance * `cpufreq` 是一個動態調整 cpu 頻率的模組，系統啟動時生成一個資料夾 `/sys/devices/system/cpu/cpu0/cpufreq/`，裡面有幾個檔案，`scalin_governor` 代表 cpu 頻率調整模式，用它來控制 CPU 頻率 ， 設為 `performance` 表示將 CPU 頻率固定工作在其支援的最高執行頻率上，而不動態調節 ```shell for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor do sudo echo performance > ${i} done ``` * 針對 Intel 處理器，關閉 turbo mode * Intel CPU 有個 [Turbo Boost](https://zh.wikipedia.org/wiki/%E8%8B%B1%E7%89%B9%E5%B0%94%E7%9D%BF%E9%A2%91%E5%8A%A0%E9%80%9F) 功能，當應用程式需要較高的運算效能時，可以以高於額定頻率執行 ， 我們要避免上述情況 ```shell $ sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo" ``` * 經過以上處理後 ， 比較計算費式數列對時間的作圖 ， 可以發現執行時間比較沒有突然衝很高的情況 ， 可以看作每次測量執行時間都比較沒有被外在因素影響 * Before: 沒有排除效能分析干擾 ， 沒有限定 CPU 只給程式用 ![](https://i.imgur.com/lTu0nYI.png) * After: 排除效能分析干擾 ， 限定 CPU 只給程式用 ![](https://i.imgur.com/tNDOkkb.png) ## 費氏數列 * 費氏數列 $F(n$) 可透過 $F(n/2)$ 及 $F(n/2+1)$ 求得 ， 而在 $n$ 為奇數及偶數的算法分別如下 * $F(2k)=F(k)[2F(k+1)-F(k)]$ * $F(2k+1)=F(k+1)^2+F(k)^2$ * 當我們有$(a,b) = (F(n/2),F(n/2)+1)$ ，根據上面兩個式子即可算出 $(c,d)=(2 * a * b - a * a,a * a + b * b)$ ， 考慮 $n$ 以下情況 * $n$ 為奇數 => $(c,d)=(F(n-1),F(n))$ * $n$ 為偶數=> $(c,d)=(F(n),F(n+1))$ * 可以發現當 $n$ 為奇數 ， 我們會得到 $F(n-1)$ 及 $F(n)$ ， 因此若要在算出 $F(2n)$ ， 我們得再算出 $F(n+1)$ ， 而 $n$ 為奇數則變為如下 * $n$ 為奇數 => $(d,c+d)=(F(n),F(n+1))$ * 透過上面式子 ， 假設要計算 $F(11)$ ， 我們只要透過 $F(5)、F(6) => F(2)、F(3) => F(1)、F(2)$ * 對照 $F(11)$ ， 11~10~ = 1011~2~ | i | start | 4 | 3 |2|1| result | -------- | -------- | -------- | -------- |-------- |-------- |-------- | | n | - | ==1==011 | 1==0==11 | 10==1==1 | 101==1== | - | | F(n)| F(0) | F(0*2+1)| F(1*2) |F(2*2+1)|F(5*2+1) |F(11) | F(n) = a | F(0)=0 |1 |1|5|89|89 | F(n+1) = b | F(1)=1 |1|2|8|144 |F(2n),F(2n+1)|-|奇數(d,c+d)|偶數(c,d)|奇數(d,c+d)|奇數(d,c+d) * 透過以上公式 ， 可以寫出以下程式來計算費伯納西數 `n` * 可以透過 `63 - __builtin_clzll(n)` 來代替迴圈求出 `n` 要除以 2 多少次才等於 0 ```c unsigned long long fib(unsigned long long n) { int start = 63 - __builtin_clzll(n); unsigned long long int bit = 1ULL << (start), a = 0, b = 1,c,d; while(bit) { c = 2*a*b - a*a, d = a*a + b*b; if(n & bit) { a = d, b = c + d; } else { a = c, b = d; } bit >>= 1; } return a; } ``` ## 減少乘法運算的成本 * 計算費式數列的過程中 ， 可以發現要求出 `c,d` 需要大量的乘法運算 ```c c = 2*a*b - a*a, d = a*a + b*b; ``` * 運用位移的方式將乘法運算改為加法 ， 可以實作出一個只需要加減及為移的 `fib` 函式 ```c c = (mul(a,b) << 1ULL) - sqare(a), d = sqare(a) + sqare(b); ``` ```c unsigned long long mul(unsigned long long a, unsigned long long b) { unsigned long long ans = 0ULL; for(int i = 0 ; i < 64; ++i) { if(b & (1ULL << i)) ans += a << i; } return ans; } unsigned long long sqare(unsigned long long x) { unsigned long long ans = 0ULL; for(int i = 0 ; i < 64; ++i) { if(x & (1ULL << i)) ans += x << i; } return ans; } ``` ## 大數運算 ### 正確計算 $F(93)$ 以及其後的值 在計算 $F(93)$ 時 ， 因為結果超過 64 位元所能表示的數 ， 得定義新的資料結構來儲存 ， 並改寫 `fib_sequence` ```c struct BigN{ unsigned long long lower, higher; }; static struct BigN fib_sequence(long long k) { struct BigN f[k + 2]; f[0].lower = f[0].higher = f[1].higher = 0; f[1].lower = 1; for (int i = 2; i <= k; i++) { f[i].lower = f[i - 1].lower + f[i - 2].lower; f[i].higher = f[i - 1].higher + f[i - 2].higher + (f[i].lower < f[i - 1].lower || f[i].lower < f[i - 2].lower); } return f[k]; } ``` * 參考 [KYG-yaya573142 的報告](https://hackmd.io/@KYWeng/rkGdultSU#%E5%A4%A7%E6%95%B8%E9%81%8B%E7%AE%97) ， 透過字串的方式 ， 將大數以 10 進位的方式印出來 * 將大數以 2 進位的觀點轉成 10 進位 ， 假設有一 10 進位數 `num` 初始為 0 ， 將大數從高位元到低位元 ， 每次將 `num` 乘以 2 且若遇到 1 就將 `num` 加 1 ， 最後即可將此數轉為 10 進位 * 對照 40~10~ = 101000~2~ | i | start = 6 | 5 | 4 | 3 | 2 |1|result | -------- | -------- | --------| -------- | -------- | -------- |-------- |-------- | | n(2進位)|==1==01000 | 1==0==1000 | 10==1==000 | 101==0==00 | 1010==0==0 |10100==0== | - | | n(10進位)| 0 | 1 | 2 | 5| 10 | 20 | 40 | 下一個數 | 0*2+1| 1*2|2*2+1|5*2|10*2 |20*2|- * 前兩層 for 迴圈即是將大數從 2 進位轉成 10 進位 * 最後一層 for 迴圈用來找出 10 進位數的開頭 * `kmalloc` 定義於 `linux/slab.h` ， 用來配置核心的記憶體空間 ```c char* displayBigN(struct BigN b) { char *num = kmalloc(41,GFP_KERNEL); memset(num,'0',40); num[40] = '\0'; int carry; for(unsigned long long i = 1ULL << 63; i; i >>= 1) { carry = (b.higher & i) > 0; for(int j = 39; j >= 0; j--) { num[j] += ((num[j] - '0') + carry); if(num[j] > '9') { num[j] -= 10; carry = 1; } else carry = 0; } } for(unsigned long long i = 1ULL << 63; i; i >>= 1) { carry = (b.lower & i) > 0; for(int j = 39; j >= 0; j--) { num[j] += ((num[j] - '0') + carry); if(num[j] > '9') { num[j] -= 10; carry = 1; } else carry = 0; } } int i = 0; for(;i < 39 && num[i] == '0';++i); return &num[i]; } ``` 如果我們要用這個資料結構 ， 運用 fast doubling 的手法計算費伯那西數 ， 我們得另外實做用於此資列結構的 `+`,`-`,`*`,`<< 1` 1. `+` * 先將 `lower` 相加 ， 在將 `higher` 相加並加上 `lower` 的進位 ```c struct BigN* add(struct BigN a, struct BigN b) { struct BigN *c = kmalloc(sizeof(struct BigN),GFP_KERNEL); c->lower = a.lower + b.lower; c->higher = a.higher + b.higher + (c->lower < a.lower || c->lower < b.lower); return c; } ``` 2. `-` * 將減數取 2 補數再與被減數相加 ```c struct BigN* sub(struct BigN a, struct BigN b) { struct BigN *c; b.lower = ~b.lower+1; b.higher = ~b.higher + (b.lower == 0); c = add(a,b); return c; } ``` 3. `*` * 先將 `lower` 轉型成 `unsigned __int128` 並相乘 ， 避免 overflow ， 結果的較低 64 位元即是新的 `lower` ， 較高 64 位元進位到 `higher` * 分別將一數的 `higher` 乘以另一數的 `lower` 並相加 ， 在將上之前的進位 ， 即為新的 `higher` * `higher` 乘以 `higher` 因無法儲存於此資料結構 ， 暫時不處理 ```c struct BigN* mul(struct BigN a, struct BigN b) { struct BigN *c = kmalloc(sizeof(struct BigN),GFP_KERNEL); unsigned __int128 tmp = (unsigned __int128)a.lower * (unsigned __int128)b.lower; c->lower = (unsigned long long)tmp; c->higher = a.lower * b.higher + a.higher * b.lower + (unsigned long long)(tmp >> 64); return c; } ``` 4. `<< 1` * 先將 `higher` 左移並加上 `lower` 的最高位元 ， 在將 `lower` 左移 ```c void lshfit(struct BigN *a) { a->higher = (a->higher << 1) + (a->lower >> 63 & 1ULL); a->lower = a->lower << 1; } ``` * 修改實作 fast doubling 的 `fib` ```c struct BigN fib(unsigned long long n) { int start = 63 - __builtin_clzll(n); unsigned long long int bit = 1ULL << (start); struct BigN a, b; struct BigN *v1, *v2, *v3,*c,*d; a.lower = a.higher = b.higher = 0; b.lower = 1; while(bit) { v1 = mul(a,b); lshfit(v1); v2 = mul(a,a); v3 = mul(b,b); c = sub(*v1,*v2); d = add(*v2,*v3); kfree(v1); kfree(v2); kfree(v3); if(n & bit) { a = *d, b = *add(*c,*d); } else { a = *c, b = *d; } bit >>= 1; } return a; } ``` * 透過這個資料結構 ， 我們可以表示 $0$ ~ $2^{128}-1$ ， 就可以正確計算到 $F(186) = 332825110087067562321196029789634457848$ ### 改寫 BigN 來計算更大的費伯納西數 為了計算出更大的費伯納西數 ， 將 `BigN` 的 `higher` 及 `lower` 更改為 `*digits` ， 可以根據我們想儲存的數字大小 ， 動態配置記憶體 ， `size` 則用來表示數字真正用到的 記憶體大小(幾個 unsigned long long) ```c struct BigN{ unsigned long long *digits; unsigned long long size; }; ``` * 改寫 `fib_sequence` * 這裡將 `f[k + 2]` 改為 `f1`,`f2` 及 `tmp` ， `f1`,`f2` 用來保留前兩個費伯那西數 ， `tmp` 則用來更換新的 `f1`,`f2` ```c static struct BigN* fib_sequence(unsigned long long k) { struct BigN *f1, *f2, *tmp; f1 = malloc(sizeof(struct BigN)); f2 = malloc(sizeof(struct BigN)); f1->digits = malloc(sizeof(unsigned long long)); f2->digits = malloc(sizeof(unsigned long long)); f1->digits[0] = 0; f1->size = f2->size = f2->digits[0] = 1; unsigned long long overflow; for (int i = 2; i <= k; i++) { int carry = 0; for(int j = 0; j < f1->size; j++) { overflow = f1->digits[j]; f1->digits[j] += f2->digits[j] + carry; carry = f1->digits[j] < overflow; } unsigned long long f = 0; int inc = 1; if(f1->size != f2->size) { overflow = f = f2->digits[f2->size-1]; f += carry; carry = f < overflow; ++inc; } if(carry) { f1->digits = realloc(f1->digits,sizeof(unsigned long long) *(f1->size+inc)); f1->size += inc; f1->digits[f1->size-1] = 1; if(f) f1->digits[f1->size-2] = f; } if(!carry && f) { f1->digits = realloc(f1->digits,sizeof(unsigned long long) *(f1->size+1)); f1->size += 1; f1->digits[f1->size-1] = f; } tmp = f2; f2 = f1; f1 = tmp; } if(k==0) { tmp = f2; f2 = f1; f1 = tmp; } free(f1->digits); free(f1); return f2; } ``` * 改寫 `displayBigN` ```c char *displayBigN(struct BigN *b) { char *num = kmalloc(sizeof(char) * (b->size * 20) + 1, GFP_KERNEL); unsigned long long len = sizeof(char) * (b->size * 20) + 1; memset(num, '0', len); num[len - 1] = '\0'; int carry; // convert number from base-2 to base-10 for (int k = b->size - 1; k >= 0; --k) { for (unsigned long long i = 1ULL << 63; i; i >>= 1) { carry = (b->digits[k] & i) > 0; for (int j = len - 2; j >= 0; j--) { // update num num[j] += ((num[j] - '0') + carry); if (num[j] > '9') { num[j] -= 10; carry = 1; } else carry = 0; } } } // skip leading 0 int i = 0; for (; i < len - 2 && num[i] == '0'; ++i) ; char *retnum = kmalloc(sizeof(char) * (len - i), GFP_KERNEL); memcpy(retnum, &num[i], sizeof(char) * (len - i)); kfree(num); return retnum; } ``` 1. `+` ```c struct BigN* add(struct BigN *f1, struct BigN *f2) { struct BigN *c = malloc(sizeof(struct BigN)), *large, *small; int carry = 0, j; if(f1->size > f2->size) large = f1, small = f2; else large = f2, small = f1; c->digits = malloc(sizeof(unsigned long long)*(large->size+1)); for(j = 0; j < small->size; j++) { c->digits[j] = small->digits[j] + large->digits[j] + carry; carry = c->digits[j] < small->digits[j]; } for(; j < large->size; j++) { c->digits[j] = large->digits[j] + carry; carry = c->digits[j] < large->digits[j]; } c->digits[j] = carry; c->size = large->size + carry; return c; } ``` * 透過 `add` 函式改寫 `fib_sequence` ```c static struct BigN* fib_sequence(unsigned long long k) { struct BigN *f1, *f2, *tmp; f1 = malloc(sizeof(struct BigN)), f2 = malloc(sizeof(struct BigN)); f1->digits = malloc(sizeof(unsigned long long)), f2->digits = malloc(sizeof(unsigned long long)); f1->digits[0] = 0, f1->size = f2->size = f2->digits[0] = 1; for(int i = 2; i <= k; i++) { tmp = add(f1,f2); free(f1->digits), free(f1); f1 = f2, f2 = tmp; } if(k == 0) tmp = f2, f2 = f1, f1 = tmp; free(f1->digits), free(f1); return f2; } ``` 2. `-` * 保證 a,b 皆為正數 ```c struct BigN* sub(struct BigN *a, struct BigN *b) { struct BigN *c, *tmp = malloc(sizeof(struct BigN)), *large, *small; if(a->size > b->size) large = a, small = b; else large = b, small = a; tmp->size = large->size, tmp->digits = malloc(sizeof(unsigned long long) * large->size); // change b to its 2's complement tmp->digits[0] = ~b->digits[0] + 1; int i = 1; for(; i < b->size; ++i) tmp->digits[i] = ~b->digits[i] + (tmp->digits[i-1] == 0); for(; i < large->size; ++i) tmp->digits[i] = ~0ULL; c = add(a,tmp); i = large->size - 1; c->size = 1; for(; i > 0; --i) { if(c->digits[i]) { c->size = i+1; break; } } free(tmp->digits); free(tmp); return c; } ``` 3. `*` ```c struct BigN* mul(struct BigN *a, struct BigN *b) { struct BigN *c = malloc(sizeof(struct BigN)); int size = a->size + b->size; c->digits = malloc(sizeof(unsigned long long)*size); memset(c->digits,0,sizeof(unsigned long long)*size); int *carry = malloc(sizeof(int)*size); memset(carry,0,sizeof(int)*size); unsigned long long overflow; for(int i = 0; i < a->size; ++i) { for(int j = 0; j < b->size; ++j) { unsigned __int128 tmp = (unsigned __int128)a->digits[i] * (unsigned __int128)b->digits[j]; int index = i+j; overflow = c->digits[index]; c->digits[index] += (unsigned long long)tmp; carry[index] += c->digits[index] < overflow; overflow = c->digits[index+1]; c->digits[index+1] += (unsigned long long)(tmp >> 64); carry[index+1] += c->digits[index+1] < overflow; } } for(int i = 0; i < size-1; i++) { overflow = c->digits[i+1]; c->digits[i+1] += carry[i]; carry[i+1] += c->digits[i+1] < overflow; } if(c->digits[size-1]) c->size = size; else c->size = size -1; free(carry); return c; } ``` 4. `<<1` ```c void lshfit(struct BigN *a) { int i = a->size - 1; if(a->digits[i] >> 63 & 1ULL) { a->size += 1; a->digits = realloc(a->digits,sizeof(unsigned long long) * (a->size)); a->digits[a->size-1] = 1; } for(; i > 0; --i) a->digits[i] = (a->digits[i] << 1) + (a->digits[i-1] >> 63 & 1ULL); a->digits[0] <<= 1; } ``` * 改寫實作 fast doubling 的 `fib` ```c struct BigN* fib(unsigned long long n) { struct BigN *a = malloc(sizeof(struct BigN)), *b = malloc(sizeof(struct BigN)), *v1, *v2, *v3, *c, *d; a->digits = malloc(sizeof(unsigned long long)) , b->digits = malloc(sizeof(unsigned long long)); a->digits[0] = 0; a->size = b->size = b->digits[0] = 1; if(n == 0) { free(b->digits), free(b); return a; } int start = 63 - __builtin_clzll(n); unsigned long long int bit = 1ULL << start; while(bit) { v1 = mul(a,b); lshfit(v1); v2 = mul(a,a); v3 = mul(b,b); c = sub(v1,v2); d = add(v2,v3); free(v1->digits), free(v1), free(v2->digits), free(v2), free(v3->digits), free(v3), free(a->digits), free(a), free(b->digits), free(b); if(n & bit) a = d, b = add(c,d); else a = c, b = d; bit >>= 1; } free(b->digits), free(b); return a; } ``` * 根據 [Other Built-in Functions Provided by GCC](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) ， `__builtin_clzll` 傳 0 進去為 undefined behavior 所以得特別判斷 `n` 是否為 0 透過這個改寫過的 `BigN` ， `fib_sequence` 及 `fib` 至少能正確計算到 $F(31200)$ ### fast doubling 及 sequence 執行時間 * 在 kernel space 測量時間 * 透過 gnuplot 觀察到 sequence 手法執行時間隨著 n 的增大線性成長 ， 而 fast doubling 手法為非線性緩慢上升 ![](https://i.imgur.com/wbJxQRF.png) ### 與 [bignum](https://github.com/0xff07/bignum/tree/fibdrv) 實做比較 * 在 user space 進行 fast doubling 的時間測量 * 在用 gnuplot 繪圖時 ， 發現還是有許多突然衝高的點 ， 後來透過每個 $F(n)$ 都測量 100 次 ， 並取其中最小值後畫出來的圖比較沒有上述情況了 * `bignum` 的實做比我的實做還要快 3 ～ 4 倍 ![](https://i.imgur.com/YHtWNBs.png) ## 回傳核心計算的值給使用者 在費伯那西數大於 `ssize_t` 的情況下 ， 使用者就無法透過 `read` 的回傳值取得它 ， 因此在進行大數運算時，我們得透過 `copy_to_user` 的方式 ， 將大數傳給使用者 * `unsigned long copy_to_user(void *to, const void *from, unsigned long n)` * `to`:目標地址（使用者空間） * `from`:源地址（核心空間） * `n`:將要拷貝資料的位元組數 ```c static ssize_t fib_read(struct file *file,char *buf,size_t size,loff_t *offset) { int ret = 0; struct BigN *n = fib(*offset); char *num = displayBigN(n); ret = copy_to_user(buf,num,strlen(num)+1); kfree(n), kfree(num); return (ssize_t) ret; } ``` ## 檢查費氏數列正確性 透過 `make check` 我們能檢查我們所求的費氏數列是否正確 ， 並將發生錯誤的地方給印出來 1. 將 MakeFile `@diff -u out scripts/expected.txt && $(call pass)` 註解 ， `expected.txt` 裡的 $fib(93)$ ~ $fib(100)$ 是錯誤的並非我們想要的值 2. 跟據想計算到費伯那西數修改 `fibdrc.c` 的 `MAX_LENG` 、 `client.c` 的 `offset` 及 `verify.py` 的 `range(2, 101)` ``` korin@korin-VivoBook-15-ASUS-Laptop-X542UF:~/Desktop/linux2022/fibdrv$ make check make -C /lib/modules/5.13.0-30-generic/build M=/home/korin/Desktop/linux2022/fibdrv modules make[1]: Entering directory '/usr/src/linux-headers-5.13.0-30-generic' make[1]: Leaving directory '/usr/src/linux-headers-5.13.0-30-generic' make unload make[1]: Entering directory '/home/korin/Desktop/linux2022/fibdrv' sudo rmmod fibdrv || true >/dev/null rmmod: ERROR: Module fibdrv is not currently loaded make[1]: Leaving directory '/home/korin/Desktop/linux2022/fibdrv' make load make[1]: Entering directory '/home/korin/Desktop/linux2022/fibdrv' sudo insmod fibdrv.ko make[1]: Leaving directory '/home/korin/Desktop/linux2022/fibdrv' sudo ./client > out make unload make[1]: Entering directory '/home/korin/Desktop/linux2022/fibdrv' sudo rmmod fibdrv || true >/dev/null make[1]: Leaving directory '/home/korin/Desktop/linux2022/fibdrv' # @diff -u out scripts/expected.txt && env printf "\e[32;01m Passed [-]\e[0m\n" f(187) fail input: 198239973509362327032045173661212819077 expected: 538522340430300790495419781092981030533 ``` #### 參考資料 [CPU 優化建議使用 cpupower 設定 CPU Performance 模式](https://www.gushiciku.cn/pl/2iRh/zh-tw) [isolcpu參數 隔離cpu使其不被自動調度（linux 修改boot參數）](https://www.twblogs.net/a/5d3f74ccbd9eee5174229c27)
Last changed by  
 
Korin777
348

Read more

2023q1 Homework7 (ktcp)

contributed by < Korin777 > 開發環境 $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 39 bits physical, 48 bits virtual Byte Order: Little Endian

5/8/2023
2023q1 Homework5 (quiz5)

contributed by < Korin777 > 測驗題目 測驗一 運作原理 pool_malloc 透過 get_loc_to_place 從 memory pool 的 free block 中配置記憶體給使用者 配置記憶體的大小會根據 32 bits 或 64 bits 進行 round up

4/21/2023
2023q1 Homework4 (quiz4)

contributed by < Korin777 > 測驗題目 測驗三 RB_LOG2_MAX_NODES node_t 的大小為 sizeof(void*) * 4 所以 node 最多有 $$\frac{1 << (sizeof(void ) << 3)} {(sizeof(void) * 4)}$$ 取 log2 可以得到 RB_LOG2_MAX_MEM_BYTES - log2(sizeof(void*)*2) - 1，若 sizeof(void*) == 8 就會是 RB_LOG2_MAX_MEM_BYTES - 4 - 1 tree_insert 這裡透過 path 來記錄插入節點的所有祖先節點，所以節點不須記錄自己的親代節點也能在插入後向上修復紅黑數，遇到黑色節點就可以停下，因為只有紅色節點可能會違反規則

4/8/2023
2023q1 Homework3 (quiz3)

contributed by < Korin777 > 測驗四 int ceil_log2(uint32_t x) { uint32_t r, shift; x--; r = (x > 0xFFFF) << 4; x >>= r;

3/15/2023
Read more from Korin777
Published on HackMD