## Linux 核心專題: 位元操作的應用
> 執行人: Lccgth
[專題解說錄影](https://youtu.be/EG72PgfBu4E)
### Reviewed by `Daniel-0224`
在閱讀回顧 bitops 並改進的問題 2 中，能否表明實驗使用的分析程式，是使用 perf ?
### Reviewed by `mesohandsome`
說明 C 語言中 `float` 轉型成 `int` 時舉了兩個例子，但僅說明了其中一個。
### Reviewed by `56han`
測驗 2 中，`uint32_t x = (in | 1) - (in >> 2);` 和 `uint32_t x = (in) - (in >> 2);` 都是 $\frac{3}{4} in$ ，為甚麼需要做 `(in | 1)`。
### Reviewed by `lintin528`
在 `bitops` 問題三中，之所以將輸入參數設定為 `unsigned long` ，我的想法是在 64 位元系統中 `unsigned long` 可以包含大部分的整數型態，就算輸入 `int, char` 也將會被正確的隱式轉換，我會想到的是既然 `ffs` 的回傳值在 `0-63` 這個範圍之間，或許可以縮減回傳值的型態所佔的記憶體大小。
### Reviewed by `youjiaw`
我想請問測驗一的實驗結果，Result 1 至 4 在實驗的設計上有什麼不同？
## 任務簡介
研究 Linux 核心的 bitops (位元操作) 並探討相關的應用
## TODO: 閱讀[回顧 bitops 並改進](https://hackmd.io/@sysprog/ByS9w_lHh)
> 含錄影並紀錄你的疑惑
> 評估能否用於新的 Linux 核心
### 問題 1
在閱讀 [`__ffs`](https://github.com/torvalds/linux/blob/master/include/asm-generic/bitops/__ffs.h) 程式碼時，不懂為什麼 `num` 要宣告成 int，此函式的回傳型態為 unsigned long，在回傳時需要進行一次轉型，若一開始就將 `num` 宣告成 unsigned long，是否可省略此轉型成本?
```c
static __always_inline unsigned long __ffs(unsigned long word)
{
int num = 0;
// 計算 ffs 過程
return num;
}
```
:::success
此問題在 [commit 3eb3c33](https://github.com/torvalds/linux/commit/3eb3c33c1d87029a3832e205eebd59cfb56ba3a4) 被修正了，而此 commit 中關於 bitops 還有另一項貢獻：
> bitops: Change function return types from long to int
:::
原本 bitops 相關的程式碼回傳型態包含 unsigned long 和 unsigned int，存在不一致的問題，在這次的 commit 中將回傳型態統一為 unsigned int，雖然這兩種資料型態在不同處理器架構下位元數量可能會不同，例如在 64 位元的系統中，unsigned int 為 32 位元，而 unsigned long 為 64 位元，但是這些更動的函式回傳值已經被限定在 0 ～ 63 之間，所以可以統一將回傳型態更改為 unsigned int。
### 問題 2
`__gen_ffs` 的參數中有一項為 `sizeof(in_type) * 8`，而這也是和 `gen_ffs` 唯一的參數不同之處，但這裡的計算是仰賴於其中一個參數 `in_type`， 若是在 `__gen_ffs` 的巨集展開函式中宣告 `bit_len`，是否就能省略此參數，提高 `__gen_ffs` 和 `gen__ffs` 的一致性?
原本程式碼
```c
#define __gen_ffs(in_type, out_type, start_from, fn_name, bit_len) \
static __always_inline out_type fn_name(in_type x) \
{ \
\
shift = bit_len >> 1; \
mask = (in_type) ~(_ONES << (bit_len >> 1)); \
\
return bits; \
}
#define gen_fls(in_type, out_type, start_from, fn_name) \
__gen_fls(in_type, out_type, start_from, fn_name, (sizeof(in_type) * 8))
```
嘗試改進
```c
#define __gen_ffs(in_type, out_type, start_from, fn_name) \
static __always_inline out_type fn_name(in_type x) \
{ \
const int bit_len = sizeof(in_type) * 8; \
shift = bit_len >> 1; \
mask = (in_type) ~(_ONES << (bit_len >> 1)); \
\
return bits; \
}
#define gen_fls(in_type, out_type, start_from, fn_name) \
__gen_fls(in_type, out_type, start_from, fn_name)
```
作者在提問清單中回答了相似問題，他說明他的設計想法主要有兩個優點:
>1. 呼叫者不需要輸入 bit_len 參數，因為這可以從輸入型別直接推得。
>2. bit_len 這項輸入在 __gen_fls 中用上兩次。
嘗試改進的程式碼保留以上兩點，且讓呼叫時更加簡潔，接著需做實驗驗證是否會有效能上的改變。
原本程式碼
| | cache-misses | cache-references | instructions | cycles |
| --- | ------------ | ---------------- | ------------ | ------ |
| 10k | 1,4224 | 6,2514 | 1391,9494 | 1165,3715 |
| 20k | 2,4392 | 6,4771 | 2679,5783 | 2230,2978 |
| 30k | 2,0021 | 7,6756 | 3972,1235 | 3295,0284 |
| 40k | 2,1108 | 6,7162 | 5259,1896 | 4355,7414 |
| 50k | 2,0070 | 6,8844 | 6548,1820 | 5395,5590 |
嘗試改進後
| | cache-misses | cache-references | instructions | cycles |
| --- | ------------ | ---------------- | ------------ | ------ |
| 10k | 1,4291 | 6,2514 | 1421,1424 | 1150,7252 |
| 20k | 2,1252 | 7,4009 | 2743,9896 | 2205,4977 |
| 30k | 1,9854 | 7,0670 | 4061,2386 | 3243,0903 |
| 40k | 1,5812 | 6,7534 | 5377,3521 | 4285,8376 |
| 50k | 1,9591 | 7,1855 | 6698,0794 | 5336,1987 |
根據實驗結果，雖然效能上沒有顯著的提昇，但改進的程式碼能在不影響效能的情況下讓呼叫時能更加的方便與簡潔。
### 問題 3
`__ffs` 程式碼的功能為尋找傳入值的第一個位元，在此情形下有固定的回傳值範圍，而這裡的回傳型態為 unsigned long，如果使用 unsigned char 等占用較小記憶體空間的型態，是否可以節省記憶體空間?
```c
// __ffs.h
/**
* __ffs - find first bit in word.
* @word: The word to search
*
*/
static __always_inline unsigned long __ffs(unsigned long word)
```
目前想法為是否是因為普遍做 4 byte alignment，所以就算其真正使用的大小只有 1 byte，電腦也會給他 4 byte 的空間?
:::danger
不是，翻閱 x86-64 ABI 規範。
:::
## TODO: 重做第 3 週測驗題
> 彙整其他學員的成果、探討延伸問題、著重 Linux 核心的應用案例
### 測驗 1
#### 解釋測驗程式碼
設所求的平方根答案為 N，透過 [digit-by-digit calculation](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Digit-by-digit_calculation) 將 `N` 拆成 2 的冪相加。
$$
N^2 = (000b_0b_1...b_{n-1}b_n)^2
$$
其中 $b_0$ 為最高位的 1，可再將 N 表示為
$$
N^2 = (a_n+a_{n-1}+...a_0)^2
$$
其中 $a_i$ 為 2 的冪或 0，再依照 $(x+y)^2=x^2+2xy+y^2$ 的公式逐層拆解。
$\begin{split}
N^2& = (\displaystyle\sum_{i=0}^{n}a_i)^2 \\
&= a_n^2 + [2a_n+a_{n-1}]a_{n-1} +...[2\displaystyle\sum_{i=1}^{n}a_i+a_0]a_0 \\
&= a_n^2 + [2P_n+a_{n-1}]a_{n-1} +...+ [2P_1+a_0]a_0 \\
P_m &= a_n + a_{n-1}+...+a_0 \\
&= P_{m+1} + a_m \\
P_m^2 &= P_{m+1}^2 + 2a_mP_{m+1} + a_m^2
\end{split}$
接著設 $Y_m=P_m^2-P_{m+1}^2$，則 $P_m^2=P_{m+1}^2+Y_m$，而 $X_m = N^2-P_m^2=X_{m+1}-Y_m$，再把 $Y_m$ 拆解為 $c_m+d_m$。
$$
c_m = 2P_{m+1}2^m，d_m = (2^m)^2
$$
$$
c_{m-1} = P_m2^m = (P_{m+1} + a_m)2^m = P_{m+1}2^m + a_m2^m = \dfrac{c_m} 2 + d_m
$$
而 $c_{-1} = P_02^0 = N$ 就是所求的 N。
```c
for (int m = 1UL << ((31 - __builtin_clz(x)) & ~1UL); m; m >>= 2) {
int b = z + m;
z >>= 1;
if (x >= b)
x -= b, z += m;
}
```
此函式中的 `b` 對應到數學式的 $Y_m$，`z` 對應到 $c_m$，而 `m` 對應到 $d_m$。
#### 使用 ffs / fls 取代 `__builtin_clz`
fls 的功能為從 lsb 開始往高位尋找最後一個為 1 的位元的位置，而在版本三中的 `31 - __builtin_clz(x)` 等價於 `fls(x) - 1`，所以可使用 fls 替換掉 `__builtin_clz` 使程式不依賴 GNU extension。
```diff
- for (int m = 1UL << ((31 - __builtin_clz(x)) & ~1UL); m; m >>= 2) {
+ for (int m = 1UL << ((fls(x) - 1) & ~1UL); m; m >>= 2) {
int b = z + m;
z >>= BBBB;
if (x >= b)
x -= b, z += m;
}
```
#### 在 Linux 核心原始程式碼找出對整數進行平方根運算的程式碼
在 [block/blk-wbt.c](https://github.com/torvalds/linux/blob/master/block/blk-wbt.c) 中的 `rwb_arm_timer` 函式中使用到了 `int_sqrt` 來計算整數的平方根，註解說明此函式為根據 [CoDel](https://en.wikipedia.org/wiki/CoDel) 的 bufferd writeback throttling 機制的一部分，會根據 `rqd->scale_step` 的值來調整當前的 window 大小。
如果 `rqd->scale_step` 的值大於 0，註解說明應該要基於 [fast inverse square root](https://en.wikipedia.org/wiki/Fast_inverse_square_root) 來縮小 window，但因為執行次數不高，所以沒有做，對這部分感到疑惑。
```c
if (rqd->scale_step > 0) {
/*
* We should speed this up, using some variant of a fast
* integer inverse square root calculation. Since we only do
* this for every window expiration, it's not a huge deal,
* though.
*/
rwb->cur_win_nsec = div_u64(rwb->win_nsec << 4,
int_sqrt((rqd->scale_step + 1) << 8));
} else {
/*
* For step < 0, we don't want to increase/decrease the
* window size.
*/
rwb->cur_win_nsec = rwb->win_nsec;
}
```
其中 `rwb->win_nsec` 為預設的 window 大小。
```c
RWB_WINDOW_NSEC = 100 * 1000 * 1000ULL;
rwb->win_nsec = RWB_WINDOW_NSEC;
```
##### CoDel 是甚麼
:::danger
注意用語，改進你的漢語表達。
:::
在網路路由中，<s>通過</s> 設置緩衝區來克服硬體中的緩衝膨脹，當封包從較快速的網路要傳輸到較慢速的網路時，設計了一個緩衝區讓快速網路能將封包先儲存在其中，而慢速網路就能以自己的速度讀取封包，當兩者速度差距太大時，緩衝區內的封包會越來越多，導致延遲增加。
CoDel 會持續測量緩衝區中的封包延遲時間，若高於設定的延遲時間 (5 毫秒)，則認定發生了緩衝膨脹，開始丟棄封包讓延遲能低於設定的延遲時間。
##### fast inverse square root 是甚麼
是一種快速計算 $x$ 的 $\frac{1}{\sqrt{x}}$ 的演算法，參考〈[從 √2 的存在談開平方根的快速運算](https://hackmd.io/@sysprog/sqrt)〉和 [Fast Inverse Square Root — A Quake III Algorithm](https://www.youtube.com/watch?v=p8u_k2LIZyo&ab_channel=Nemean) 嘗試理解其原理。
```c
float InvSqrt(float x)
{
float xhalf = 0.5f * x;
int i = *(int *) &x;
i = 0x5f3759df - (i >> 1);
x = *(float *) &i;
x = x * (1.5f - xhalf * x * x);
return x;
}
```
因為除法操作非常耗時，所以採用近似值來計算。
###### 解析程式碼
一開始先將 0.5 倍的 `x` 的值存在 `xhalf` 變數中供後續的計算使用。
```c
float xhalf = 0.5f * x;
```
接著將 `x` 的型態從 float 轉型為 int，如此以來才方便使用位元操作來減少計算成本，但這裡特別的是一般在轉型時的寫法為 `i = (int) x`，這兩者的不同之處在於:
```c
float x = 3.33; // x = 0 10000000 10101010001111010111000
int i1 = (int) x; // i1 = 00000000 00000000 00000000 00000011
int i2 = *(int *) &x; // i2 = 01000000 01010101 00011110 10111000
```
第二種轉型首先會從 `&x` 中取得 float `x` 的記憶體位址，接著通過 `(int *)` 會將 `x` 的記憶體位址從 float 型態改為 int 型態，雖然記憶體位址本身並沒有更改，但對 C 而言此記憶體位址中的值已經變成 int，於是在最後對此記憶體位址取值時就會直接將裡面的 32 位元讀成 int。
這時會注意到程式碼中出現了一個 magic number(`0x5f3759df`)，接下來會一步步推導此數值出現的原因。在 IEEE 754 單精度的表示法中 32 個位元被分成了三個部分，以浮點數 3.33 為例:
```
| 0 | 10000000 | 10101010001111010111000 |
| sign | exponent | fraction |
```
此值在十進位的表示中，為
$$
(1 + \frac{frac}{2^{23}}) \times 2^{exp - 127}
$$
此時將此值取 $log$
$$
log_2((1 + \frac{frac}{2^{23}}) \times 2^{exp - 127})
= log_2(1 + \frac{frac}{2^{23}}) + exp - 127
$$
因為 $\frac{frac}{2^{23}}$ 的值介於 0 到 1 之間，因此
$$
log_2(1 + \frac{frac}{2^{23}}) \approx \frac{frac}{2^{23}} + \mu
\quad (\mu \approx 0.0450466)
$$
把此結果帶回上述算式
$$
\begin{align*}
\frac{frac}{2^{23}} + \mu + exp - 127 &= \frac{frac}{2^{23}} + exp + \mu - 127 \\
&= \frac{frac}{2^{23}} + \frac{2^{23} \times exp}{2^{23}} + \mu - 127 \\
&= \frac{frac + 2^{23} \times exp}{2^{23}} + \mu - 127 \\
\end{align*}
$$
有趣的是 $frac + 2^{23} \times exp$ 轉成二進位表示時:
```
frac = 0 00000000 frac(23 bits)
2^{23} * exp = 0 exp(8 bits) 0000....0
------------------------------------------
sum = 0 exp(8 bits) frac(23 bits)
```
所以如果要對浮點數取 $log$，只需將其除以 $2^{23}$ 後再加上常數 $\mu - 127$ 即可。
此時設所求的解為 $\Gamma$ :
$$
\begin{align*}
\Gamma &= \frac{1}{\sqrt{x}} \\
log(\Gamma) &= log(\frac{1}{\sqrt{x}}) = -\frac{1}{2}log(x) \\
\frac{1}{2^{23}}(frac_\Gamma + 2^{23} \times exp_\Gamma) + \mu - 127 &= -\frac{1}{2}(\frac{1}{2^{23}}(frac_x + 2^{23} \times exp_x)) + \mu - 127) \\
frac_\Gamma + 2^{23} \times exp_\Gamma &= -2^{22}(\frac{1}{2^{23}}(frac_x + 2^{23} \times exp_x)) - 2^{22}(\mu - 127) - 2^{23}(\mu - 127) \\
&= 2^{22}(127 - \mu) + 2 \times2^{22}(127 - \mu) - \frac{1}{2}(frac_x + 2^{23} \times exp_x)\\
&= 3 \times 2^{22}(127 - \mu) - \frac{1}{2}(frac_x + 2^{23} \times exp_x) \\
&= 0x5f3759df - (x >> 1)
\end{align*}
$$
此行程式碼就是依照以上推導而得出的，用於計算 $i$ 的 $\frac{1}{\sqrt{i}}$。
```c
i = 0x5f3759df - (i >> 1);
```
計算完畢後再將型態轉回 float。
```c
x = *(float *) &i;
```
接著再利用 Newton's method 來改進近似值，Newton's method 的基本公式為:
$$
x_{n+1} = x_n - \frac{f(x_n)}{f^{\prime}(x_n)}
$$
這裡所要求的是 $\frac{1}{\sqrt{x}}$，設:
$$
y = \frac{1}{\sqrt{x}}
$$
希望能找到 y 的值令
$$
f(y) = \frac{1}{y^2} - x = 0
$$
其導數為
$$
f^{\prime}(y) = -\frac{2}{y^3}
$$
將兩者帶入到 Newtons's method 中
$$
\begin{align*}
y_{n+1} &= y_n - \frac{f(y_n)}{f^{\prime}(y_n)} \\
&= y_n - \frac{\frac{1}{y^2_n} - x}{-\frac{2}{y^3_n}} \\
&= y_n - \frac{1 - xy^2_n}{y^2_n} \times (-\frac{y^3_n}{2}) \\
&= y_n + \frac{y_n - xy^3_n}{2} \\
&= y_n + \frac{y_n}{2} - \frac{xy^3_n}{2} \\
&= \frac{3y_n}{2} - \frac{xy^3_n}{2} \\
&= y_n(\frac{3}{2} - \frac{xy^2_n}{2})
\end{align*}
$$
對應到程式碼中的
```c
x = x * (1.5f - xhalf * x * x);
```
###### 利用 fast inverse square root 改進 linux kernel
使用 fast inverse square root 讓程式碼中不依賴開根號與除法，預期將 `div_u64` 移除。
```c
rwb->cur_win_nsec = div_u64(rwb->win_nsec << 4,
int_sqrt((rqd->scale_step + 1) << 8));
```
首先要小幅修改上述介紹的 fast inverse square root，因為上述程式碼推導的是基於 32 位元，而此處使用到的是基於 64 位元，推導過程與上述相同，只須將 IEEE 754 單精度換成雙精度，這裡就不贅述，直接展示修改好的程式碼。
```c
double InvSqrt64(double x)
{
double xhalf = 0.5 * x;
int64_t i = *(int64_t *)&x;
i = 0x5fe6eb50c7b537a9 - (i >> 1);
x = *(double *)&i;
x = x * (1.5 - xhalf * x * x);
return x;
}
```
接著利用此函式對原本的程式碼進行修改。
```c
rwb->cur_win_nsec = rwb->win_nsec << 4;
double scale_factor = InvSqrt64((double)((rqd->scale_step + 1) << 8));
rwb->cur_win_nsec = (u64)(rwb->cur_win_nsec * scale_factor);
```
:::danger
誤差的分析呢？
:::
###### 做實驗測試效能差別
測試用命令
```shell
$ sudo perf stat --repeat 100 -e cache-misses,cache-references,instructions,cycles
```
原本程式碼
| | Result 1 | Result 2 | Result 3 | Result 4 |
| ---------------- | -------- | -------- | -------- | -------- |
| cache-misses | 1826 | 1597 | 2064 | 5973 |
| cache-references | 6,1509 | 6,2647 | 6,1889 | 6,1523 |
| instrcuciotns | 99,2204 | 99,1723 | 99,1330 | 99,3471 |
| cycles | 89,4694 | 87,9199 | 88,3323 | 99,6138 |
| time (sec) | 0.0014 | 0.0014 | 0.0014 | 0.0016 |
使用 fast inverse square root 改寫
| | Result 1 | Result 2 | Result 3 | Result 4 |
| ---------------- | -------- | -------- | -------- | -------- |
| cache-misses | 1441 | 1913 | 2637 | 4867 |
| cache-references | 6,1086 | 6,1883 | 6,1737 | 6,1851 |
| instrcuciotns | 99,5354 | 99,4980 | 99,4249 | 99,4466 |
| cycles | 90,0680 | 88,5366 | 89,7526 | 99,0297 |
| time (sec) | 0.0013 | 0.0011 | 0.0010 | 0.0012 |
從實驗結果可以得知，修改後的程式碼執行速度比原本快了 0.0001 ~ 0.0004 秒，相當於提升了 7% ~ 28%。
### 測驗 2
#### 解釋測驗程式碼
為了減少運算成本，題目中想利用位元運算來代替 `/` 和 `%` 兩種運算元，因為除以 10 相等於乘 $\dfrac{1}{10}$，所以利用 2 的冪的倒數和來逼近。
$$
\dfrac{1}{128} + \dfrac{1}{32} + \dfrac{1}{16} = \dfrac{13}{128}\approx \dfrac{1}{10}
$$
而 $13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0$，因此用位元運算可得到 $\dfrac{13}{8}n$。
```c
q = ((((n >> 3) + (n >> 1) + n) << 3) // q = 13n
```
接著將做位元運算時捨棄的值加回後再右移 7 (除以 128)。
```c
d0 = n & 0b1;
d1 = n & 0b11;
d2 = n & 0b111;
q = ((((n >> 3) + (n >> 1) + n) << 3) + d0 + d1 + d2) >> 7; // q = 13n / 128
```
而 $(4q + q) \times 2 = 10q$。
```c
r = n - (((q << 2) + q) << 1);
```
而另一種算法先將 `q` 逼近到 0.8 in。
```c
uint32_t x = (in | 1) - (in >> 2); /* div = in/10 ==> div = 0.75*in/8 */
uint32_t q = (x >> 4) + x;
```
$$
x = \dfrac{3}{4}in
$$
$$
q= \dfrac{3}{64}in + \dfrac{3}{4}in = \dfrac{51}{64}in\approx0.8in
$$
將 0.8 右移 3 位可得到 0.1 ( `div` )。
```c
*div = (q >> 3);
```
再計算 `mod = in - div * 10`。
```c
*mod = in - ((q & ~0x7) + (*div << 1));
```
#### 改進測驗程式碼
在計算 $q = 13n$ 時是先計算出 $\frac{13n}{8}$ 後再乘 8。
```c
q = ((((n >> 3) + (n >> 1) + n) << 3
```
可以修改為直接使用位元操作計算出 $13n = 8n + 4n +n$。
```c
q = (n << 3) + (n << 2) + n
```
而原本程式碼會記錄位元運算時捨棄的值(d0、d1、d2)，但再加完這些值後會做一次右移 7，導致這些位元會再次被捨去，於是這個操作可以被省略。
```diff
- unsigned d2, d1, d0, q, r;
+ unsigned q,r;
- d0 = n & 0b1;
- d1 = n & 0b11;
- d2 = n & 0b111;
- q = ((((n >> 3) + (n >> 1) + n) << 3) + d0 + d1 + d2) >> 7;
+ q = ((n << 3) + (n << 2) + n) >> 7;
r = n - (((q << 2) + q) << 1);
```
測試結果:
```
q: 0 r: 0
q: 0 r: 1
q: 0 r: 2
q: 0 r: 3
q: 0 r: 4
q: 0 r: 5
q: 0 r: 6
q: 0 r: 7
q: 0 r: 8
q: 0 r: 9
q: 1 r: 0
q: 1 r: 1
q: 1 r: 2
q: 1 r: 3
q: 1 r: 4
q: 1 r: 5
q: 1 r: 6
q: 1 r: 7
q: 1 r: 8
q: 1 r: 9
```
結果和原本的程式碼一致。
#### 撰寫不依賴除法指令的 `%5` 和 `%9`
##### `%5`
2 的冪 mod 5 有以下的特性
$$
\begin{split}
2^1 \quad mod \quad 5 = 2 \\
2^2 \quad mod \quad 5 = 4 \\
2^3 \quad mod \quad 5 = 3 \\
2^4 \quad mod \quad 5 = 1 \\
2^5 \quad mod \quad 5 = 2 \\
...
\end{split}
$$
可觀察到會以四個為一組循環(2、4、3、1)，接著因為 $2^{16}、2^8、2^4$ mod 5 都等於 1，所以對於任意整數 a
$$
a \times 2^{16} (mod \quad 5) = a \times 1 (mod \quad 5) = a (mod \quad 5)
$$
於是我們可以將 32 位元的整數 (`x`) 拆解為兩個部分，分別是前 16 位元 (`a`) 和後 16 位元 (`b`)
$$
x = a \times 2^{16} + b
$$
根據取模的分配律
$$
\begin{align*}
x (mod \quad 5) &= a * 2^{16}(mod \quad 5) + b(mod \quad 5) \\
&= a(mod \quad 5) + b(mod \quad 5)
\end{align*}
$$
可根據位元運算來逐步壓縮 `x` 的數值。
```c
x = (x >> 16) + (x & 0xFFFF);
x = (x >> 8) + (x & 0xFF);
x = (x >> 4) + (x & 0xF);
```
壓縮完的數值會介在 `0 ~ 63` 之間，可以直接建一個表紀錄每個值 mod 5 的結果即可。
```c
int table[63] = {0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0,
1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1,
2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2,
3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1};
return table[x];
```
##### `%9`
2 的冪 mod 9 有以下的特性
$$
\begin{split}
2^1 \quad mod \quad 9 = 2 \\
2^2 \quad mod \quad 9 = 4 \\
2^3 \quad mod \quad 9 = 8 \\
2^4 \quad mod \quad 9 = 7 \\
2^5 \quad mod \quad 9 = 5 \\
2^6 \quad mod \quad 9 = 1 \\
2^7 \quad mod \quad 9 = 2 \\
...
\end{split}
$$
觀察到 $2^{18}、2^{12}、2^6$ mod 9 都等於 1，於是修改壓縮數值的程式碼。
```c
x = (x >> 18) + (x & 0x3FFFF);
x = (x >> 12) + (x & 0xFFF);
x = (x >> 6) + (x & 0x3F);
```
接著依照和 `%5` 相同的方式建表，將壓縮完的值進行查表即可。
### 測驗 3
#### 解釋測驗程式碼
版本二函式依序判斷目前的 `i` 是否大於或等於 65536 ( $2^{16}$ )、256 ( $2^{8}$ )、16 ( $2^{4}$ )、2 ( $2^{1}$ )，如果成立的話就將 `i` 進行右移並且增加 `result`，如此一來可找到最大的 `result` 使得 $2^{result} <= i$。
```c
while (i >= 65536) {
result += 16;
i >>= 16;
}
while (i >= 256) {
result += 8;
i >>= 8;
}
while (i >= 16) {
result += 4;
i >>= 4;
}
while (i >= 2) {
result += 1;
i >>= 1;
}
return result;
```
版本三函式使用 GCC 內建的函式 `__builtin_clz` 計算傳入的無號整數從最高位開始連續 0 的數量，再使用 31 減 `__builtin_clz` 的結果，為了處理輸入為 0 的情況，會將 `__builtin_clz` 的輸入參數和 1 做 or。
```c
int ilog32(uint32_t v)
{
return (31 - __builtin_clz(v | 1));
}
```
參考 [linux/log2.h](https://github.com/torvalds/linux/blob/master/include/linux/log2.h) 其中 `31 - __builtin_clz(v)` 等價於 `fls(v) - 1`，`fls` 會回傳從最低位往最高位找到的最後一個 1。
```c
static __always_inline __attribute__((const))
int __ilog2_u32(u32 n)
{
return fls(n) - 1;
}
```
#### Linux 核心中 log2 相關程式碼
在 [linux/include/linux/log2.h](https://github.com/torvalds/linux/blob/master/include/linux/log2.h) 中存在與 log2 相關的函式與巨集，接下來會逐一說明各自的功能。
##### `__ilog2_u32(u32 n)` 和 `__ilog2_u64(u64 n)`
對於輸入的 32 或 64 位元無號整數 `n`，找出其以 2 為底的對數，使用 `fls()` 和 `fls64()` 找出最高位的 1 的位置後減 1 並返回。
##### `is_power_of_2(unsigned long n)`
檢查輸入的 `n` 是否為 2 的冪，判斷 `n & (n - 1)` 的結果，如果結果為 0，代表 `n` 是 2 的冪。
在 2 進位表示中，如果 `n` 是 2 的冪，則只有 1 個位元會是 1，而 `n - 1` 會將原本最高位的 1 變成 0，最高位前的 0 變為 1，以 `n = 64` 為例:
```
n = 100 0000 (64)
n - 1 = 011 1111 (63)
n & (n - 1) = 000 0000 (0)
```
##### `__roundup_pow_of_two(unsigned long n)`
將輸入的 `n` 向上取到最接近的 2 的冪。
##### `__rounddown_pow_of_two(unsigned long n)`
將輸入的 `n` 向下取到最接近的 2 的冪。
##### `const_ilog2(n)`
此巨集會先判斷 `n` 編譯時是否為常數，再來從最高位依序往最低位檢查每個位元是否為 1，若找到第一個位元為 1 的位置時就回傳該位置。
##### `ilog2(n)`
此巨集會根據 `n` 的大小來決定要使用 `__ilog2_u32(u32 n)` 或 `__ilog2_u64(u64 n)` 來取得 `n` 的以 2 為底的對數。
##### `roundup_pow_of_two(n)`
此巨集會先判斷 `n` 編譯時是否為常數，並根據結果決定要使用 `ilog2(n)` 或 `__roundup_pow_of_two(unsigned long n)` 將 `n` 向上取到最接近的 2 的冪。
##### `rounddown_pow_of_two(n)`
此巨集會先判斷 `n` 編譯時是否為常數，並根據結果決定要使用 `ilog2(n)` 或 `__rounddown_pow_of_two(unsigned long n)` 將 `n` 向下取到最接近的 2 的冪。
##### `__order_base_2(unsigned long n)`
回傳 `n` 向上取到 2 的冪後為 2 的幾次方。
```
ob2(0) = 0 // 0 -> 1
ob2(1) = 0 // 1 -> 1
ob2(2) = 1 // 2 -> 2
ob2(3) = 2 // 3 -> 4
ob2(4) = 2 // 4 -> 4
ob2(5) = 3 // 5 -> 8
```
##### `order_base_2(n)`
此巨集會先判斷 `n` 編譯時是否為常數，並根據結果決定要使用 `ilog2(n)` 或 `__order_base_2(unsigned long n)` 回傳 `n` 向上取到 2 的冪後為 2 的幾次方。
##### `__bits_per(unsigned long n)`
回傳 `n` 需要用幾個位元來表示。
```
ob2(0) = 1 // 0
ob2(1) = 1 // 1
ob2(2) = 2 // 10
ob2(3) = 2 // 11
ob2(4) = 3 // 100
ob2(5) = 3 // 101
```
##### `bits_per(n)`
此巨集會先判斷 `n` 編譯時是否為常數，並根據結果決定要使用 `ilog2(n)` 或 `__bits_per(unsigned long n)` 回傳 `n` 需要用幾個位元來表示。
### 測驗 4
[EWMA](https://en.wikipedia.org/wiki/Moving_average#Exponential_moving_average) 是一種用於平滑時間序列數據的統計手法，讓越久以前的資料所佔的權重越低。
#### 解釋測驗程式碼
##### `ewma_init`
初始化 EWMA 結構，設定 `factor` 和 `weight`，為了使用位元運算而讓這兩個參數的值為 2 的冪，`factor` 用於在有限的數值範圍內維持盡可能高的精確度，當 `factor` 越大時可以提高精確度，但同時也會降低 EWMA 能表示的最大值，而 `weight` 用於控制舊值對於新值的影響程度，當 `weight` 越大時會使平均值對於新值的影響越小。
```c
avg->weight = ilog2(weight);
avg->factor = ilog2(factor);
avg->internal = 0;
```
##### `ewma_add`
向 EWMA 中添加一個新值，如果 `internal` 不為 0，則按照已有的累計平均值計算新的加權平均值，如果 `internal` 為 0，則直接根據 `factor` 調整新值。
```c
avg->internal = avg->internal
? (((avg->internal << avg->weight) - avg->internal) +
(val << avg->factor)) >> avg->weight
: (val << avg->factor);
```
##### `ewma_read`
返回 EWMA 當前的加權平均值，通過對 `internal` 依 `factor` 反向縮放得到。
```c
return avg->internal >> avg->factor;
```
#### 在 Linux 核心原始程式碼找出 EWMA 的相關程式碼
在 [linux/drivers/net/virtio_net.c](https://github.com/torvalds/linux/blob/master/drivers/net/virtio_net.c) 中 EWMA 被用來計算封包的平均大小，根據對最近的數據賦予更大的權重能更好的反應當前的網路狀態，接著使用計算出的平均來決定重新填滿 RX ring 時所需的緩衝區大小，而對於短期、瞬間的封包大小變化不敏感。
> RX packet size EWMA. The average packet size is used to determine the packet buffer size when refilling RX rings. As the entire RX ring may be refilled at once, the weight is chosen so that the EWMA will be insensitive to short-term, transient changes in packet size.
RX ring 是一種用於管理網路封包接收過程的資料結構，是一種循環緩衝區，用來暫存從網卡 (NIC) 接收到的封包。
### 測驗 5
#### 解釋測驗程式碼
設定 `r` 和 `shift` 紀錄各步驟的位移量和最終的對數結果，接著將傳入的 `x` 值減 1，這是為了處理當 `x` 為 2 的冪時的情況，因為此函式回傳的是 $\lceil\log_2(x)\rceil$，如果不先減 1，會導致回傳的結果比預期要多 1。
再檢查 `x` 是否大於 `0xFFFF`，如果為真說明 `x` 的對數最小為 16，將此資訊紀錄在 `r` 中，並將 `x` 右移 16 位。
```c
r = (x > 0xFFFF) << 4;
x >>= r;
```
再檢查當前 `x` 是否大於 `0xFF`，如果為真說明當前 `x` 的對數最小為 8，將此資訊紀錄在 `shift` 中，並將 `x` 右移 8 位，並將 `shift` 的值合併到 `r` 中，累計目前為止的對數結果。
```c
shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;
```
根據相同的邏輯依序判斷當前 `x` 是否大於 `0xF` 和 `0x3`，設定 `shift` 和通過 `r` 累計結果，最後將判斷 `x` 是否大於 `0x1` 的步驟合併在最後一行中，並統計以上步驟中的對數結果，再將一開始減的 1 補上。
```c
return (r | shift | x > 1) + 1;
```
#### 改進程式碼使其得以處理 `x = 0` 的狀況，並仍是 branchless
新增判斷傳入的 `x` 值是否為 0，若 `x` 為 0 則不會讓 `x -= 1`，使 `x` 不會產生 underflow。
```diff
uint32_t r, shift;
- x--;
+ x -= !!x
return (r | shift | (x > 1)) + 1;
```
#### 在 Linux 核心原始程式碼找出 ceil 和 log2 的組合
在 [linux/kernel/sched/fair.c](https://github.com/torvalds/linux/blob/master/kernel/sched/fair.c#L205) 中 的 `get_update_sysctl_factor` 函式中使用到了類似的組合，程式碼如下:
```c
static unsigned int get_update_sysctl_factor(void)
{
unsigned int cpus = min_t(unsigned int, num_online_cpus(), 8);
unsigned int factor;
switch (sysctl_sched_tunable_scaling) {
case SCHED_TUNABLESCALING_NONE:
factor = 1;
break;
case SCHED_TUNABLESCALING_LINEAR:
factor = cpus;
break;
case SCHED_TUNABLESCALING_LOG:
default:
factor = 1 + ilog2(cpus);
break;
}
return factor;
}
```
:::danger
為了避免「舉燭」，實際執行並觀察程式碼的運作。
:::
此函式首先會先計算當前的 CPU 數量，但最多不超過 8，接著根據 `sysctl_sched_tunable_scaling` 參數控制縮放行為，`SCHED_TUNABLESCALING_NONE` 為不縮放，`factor` 始終為 1，代表不管 CPU 數量為何都不會改變，適用於不需要根據 CPU 數量動態調整時，`SCHED_TUNABLESCALING_LINEAR` 為線性縮放，會依照 CPU 數量線性增加 `factor` 的值，適用於需要與 CPU 數量呈正比的性能調整時，`SCHED_TUNABLESCALING_LOG` 為對數縮放，`ilog2(cpus)` 計算 CPU 數量的對數整數部分，因此 `1 + ilog2(cpus)` 相當於 `ceil(log2(cpus))`，適用於在<s>多核心</s> 多核處理器系統中達到更均衡的性能分配。
:::danger
注意用語：
* (OS) kernel 是「核心」
* (processor) core 是「核」
務必使用本課程教材規範的術語。
> 已修正
:::
Sign in with Wallet
Connect another wallet