# 2023q1 Homework3 (quiz3)
contributed by < `yanjiew1` >
> [GitHub](https://github.com/yanjiew1/linux23q1-quiz3)
> [題目連結](https://hackmd.io/@sysprog/linux2023-quiz3)
## 實驗環境
```bash
$ 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
CPU(s): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
CPU family: 6
Model: 142
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 10
CPU max MHz: 3400.0000
CPU min MHz: 400.0000
BogoMIPS: 3600.00
```
## 測驗 1
可改進的地方：
- 紅黑樹實作內部使用的函式除了宣告為`static` 外，也可以宣告為 `inline` ，來改進效能，因為函式呼叫有成本。例如： `cmap_rotate_left` 、 `cmap_rotate_right` 、 `cmap_l_l` 、 `cmap_l_r` 、 `cmap_r_l` 、 `cmap_r_r` 等。
:::warning
後來看了一下 Linux coding style ， Linux 不鼓勵為了加速就把函式宣告為 `inline` 。只有大約二到三行的函式再宣告為 `inline` 就好。實際上 GCC 在沒有宣告 `inline` 的情況下，也會為了優化去自動 inline 一些函式。
:::
## 測驗 3
### Linear feedback shift register (LFSR) 的運作原理
在維基百科對 LFSR 有這樣的定義：
```!
In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state.
```
故 LFSR 是一個在狀態改變時，會向右位移的 register ，向右位移時，最左邊的輸入位元，是由目前原本 register 內狀態取一些 bit 出來，並透過線性方式組合。
維基百科有下面這張圖：
下一個狀態是前一個狀態每一個位元向右移，最左邊輸入的 bit ，是由原本狀態中第 11 、 13 、 14 、 16 個 bit 透過 XOR 運算得到的。
最左邊輸入位元怎麼組合沒有明確定義，只要是由原本狀態的線性組合即可。
參考資料：
- [Wikipedia: Linear-feedback shift register](https://en.wikipedia.org/wiki/Linear-feedback_shift_register)
### 程式碼運作原理
程式會建立 120 個初始值為 0 的 bucket ，然後跑 $2^{20}$ 次迴圈，每次迴圈會透過 LFSR 從 0 ~ 119 任選一個隨機數作為 bucket 編號，把對應的 bucket 編號值加一。
一開始程式定義了一個 LFSR 的操作：
```c
/* Implementation of LFSR (linear feedback shift register)
* on uint64_t using irreducible polynomial x^64 + x^61 + x^34 + x^9 + 1
* (On 32 bit we could use x^32 + x^22 + x^2 + x^1 + 1)
*/
static void lfsr(uint64_t *up)
{
uint64_t new_bit =
((*up) ^ ((*up) >> 3) ^ ((*up) >> 30) ^ ((*up) >> 55)) & 1u;
/* don't have to map '+1' in polynomial */
*up = ((*up) >> 1) | (new_bit << 63);
/* shift *up by 1 to RIGHT and insert new_bit at "empty" position */
}
```
`new_bit` 就是在計算要放在最左邊的輸入位元。由程式可知，輸入位元由（由右往左數，最右邊為 0）第 0 、3、30、55 位元進行 XOR 運算組成。
再把 `*up` 向右移一位，把 `new_bit` 放在最左邊空出的一位，就完成了。
下面定義了一個表格 `log_table_256` ，其輸出數值為輸入 index 取 $\log_2$ 的值。為了避免重複填寫同一個數值，這裡還定義了一個巨集 `_` 巨集會把同一個數字複製 16 份，中間用 `,` 隔開。
```c
static const char log_table_256[256] = {
#define _(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
-1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3,
3, 3, 3, 3, 3, _(4), _(5), _(5), _(6), _(6), _(6),
_(6), _(7), _(7), _(7), _(7), _(7), _(7), _(7), _(7),
#undef _
};
#undef _
```
`log2_64` 函式是針對傳入的 64-bit 整數，計算其 $\log_2$ 的值，並取其整數部份。運作原理類似二分搜尋法，找到最高位的位置。
```c
/* ASSUME x >= 1
* returns smallest integer b such that 2^b = 1 << b is >= x
*/
uint64_t log2_64(uint64_t v)
{
unsigned r;
uint64_t t, tt, ttt;
ttt = v >> 32;
if (ttt) {
tt = ttt >> 16;
if (tt) {
t = tt >> 8;
if (t) {
r = 56 + log_table_256[t]; // AAAA
} else {
r = 48 + log_table_256[tt]; // BBBB
}
} else {
t = ttt >> 8;
if (t) {
r = 40 + log_table_256[t]; // CCCC
} else {
r = 32 + log_table_256[ttt]; // DDDD
}
}
} else {
tt = v >> 16;
if (tt) {
t = tt >> 8;
if (t) {
r = 24 + log_table_256[t]; // EEEE
} else {
r = 16 + log_table_256[tt]; // FFFF
}
} else {
t = v >> 8;
if (t) {
r = 8 + log_table_256[t]; // GGGG
} else {
r = 0 + log_table_256[v]; // HHHH
}
}
}
return r;
}
```
若搭配測驗 4 的 bitwise 操作，可簡化為
```c
uint64_t log2_64(uint64_t x)
{
uint64_t r, shift;
r = (x > 0xFFFFFFFFL) << 5;
x >>= r;
shift = (x > 0xFFFF) << 4;
x >>= r;
r |= shift;
shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;
shift = (x > 0xF) << 2;
x >>= shift;
r |= shift;
shift = (x > 0x3) << 1;
x >>= shift;
return (r | shift | x >> 1);
}
```
或是透過 `__builtin_clz64` 來加速：
```c
uint64_t log2_64(uint64_t v)
{
return 63 - __builtin_clz64(v);
}
```
---
`bucket_number` ，會透過傳入的隨機數 `x` 來選取一個 bucket 。
其中 `mask111` ，為二進位有效位數全為 1 且位元數為 bucket 位元數的整數。 `mask011` 則為二進位有效位數全為 1 且位元數為 bucket 位元數少 1 的整數。故可知道 `mask111 >= bucket number > mask011` 。
leq 則判斷對 `x & mask111` 是否小於 bucket 數。針對 `leq` 的結果，有以下產生的方式：
- 若 `x & mask111` 小於 bucket 數 ，則結果為 `x & mask111` ，等價於 `x % N_BUCKETS` 。
- 若 `x & mask111` 大於 bucket 數，則結果為 `(x >> (N_BITS + 1)) & mask011` ，即取 `x` 的較高位數作為隨機數，然後再跟 `mask011` 做 AND 運算，確保取得的數小於 bucket 數值。
```c
/* n == number of totally available buckets, so buckets = \{0, ...,, n-1\}
* ASSUME n < (1 << 32)
*/
unsigned int bucket_number(uint64_t x)
{
uint64_t mask111 = (1 << (N_BITS + 1)) - 1;
uint64_t mask011 = (1 << (N_BITS)) - 1; /* one 1 less */
unsigned char leq = ((x & mask111) < N_BUCKETS);
/* leq (less or equal) is 0 or 1. */
return (leq * (x & mask111)) + // IIII
((1 - leq) * ((x >> (N_BITS + 1)) & mask011)); // JJJJ
/* 'x >> (N_BITS + 1)' : take different set of bits -> better uniformity.
* '... & mask011' guarantees that the result is less or equal N_BUCKETS.
*/
}
```
雖然註解中這樣寫 `'x >> (N_BITS + 1)' : take different set of bits -> better uniformity.` ，若看程式執行的結果，產生的隨機數還是會有偏差。前 64 個 bucket 明顥比較多次被選中。
---
`fill_buckets` 會跑 `1 << 20` 次迴圈（可以從 `main` 函式得知傳入的 `iterations` 值），每一次透過 `bucket_number` 選取一個 bucket ，把選中的 bucket 數值加 1 。之後透過 LFSR ，產生下一組隨機數，再重複進行。
```c
void fill_buckets(unsigned int *buckets, unsigned int iterations)
{
uint64_t x = 0x98765421b16b00b5;
unsigned char lfsr_iter = (N_BITS << 1);
for (uint64_t i = 0; i < iterations; i++) {
unsigned int tmp_bucket = bucket_number(x);
*(buckets + tmp_bucket) = *(buckets + tmp_bucket) + 1;
// 'turn handle' on LFSR lfsr_iteration-times!
unsigned char ell = 0;
while (ell < lfsr_iter) {
lfsr(&x);
ell++;
}
}
}
```
---
## 測驗 4
### 原理解說
原理是類似 binary search 的方式實作。因為要取 $\lceil log_2(x) \rceil$ ，故一開始先對 `x` 減去 1 ，就能直接用 $\lfloor log_2(x - 1) \rfloor$ 二進位的值，算出 $\lceil log_2(x) \rceil$ 的值。
程式中，使用 `r` 作為記錄總共向右移的 bits 數， `shift` 則是暫存要向右移多少 bits 的結果。
這段程式會先判斷 `x` 是否大於 `0xFFFF` ，若大於 `0xFFFF` 則代表其最高位在第 `31 ~ 16` bit 之間，則需向右移 16 bits ，把接下來要檢索的部份放到右邊的 0~15 bits 之間。
在這裡 `r` 記錄向右移動的次數，用來推算最後 $\lceil log_2(x) \rceil$ 的值。
```c
r = (x > 0xFFFF) << 4;
x >>= r;
```
前面已經把檢索範圍縮小到 16-bits 。`x > 0xFF` 成立時，代表最高位在 8 ~15 bits 之間，則要向右移 8 個 bits 。 `shifts` 的值就是要向右移的 bits 數，而 `r` 則記錄著總共向右移的次數， `r |= shift;` 會把先前向右移的次數和這次向右移的次數加起來。這裡用 `|` 是因為 `r` 是 1 的 bits 不會和 `shift` 重疊。
```c
shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;
```
檢索範圍已縮小到 0 - 7 bits 。 `x > 0xF` 成立時，代表最高位在 4 ~ 7 bits 之間，則要再向右移 4 個 bits 。 `shift` 的值是要向右移的 bits 數。 `r` 則把先前已經向右移的 bits 數和現在的 `shift` 加總，為至目前為止向右移的 bits 數。
```c
shift = (x > 0xF) << 2;
x >>= shift;
r |= shift;
```
檢索範圍已縮小到 0 - 3 bits。 `x > 0x3` 成立時，代表最高位在 2 ~ 3 bits 之間，則要向右移 2 個 bits 。 `shift` 的值是要向右移的 bits 數。
```c
shift = (x > 0x3) << 1;
x >>= shift;
```
檢索範圍已縮小到 0 - 1 bits 了。而前面因為 `r` 沒有跟 `shift` 做 bitwise or 運算，把向右移的次數加總，故在 return 時，要先讓 `r` 跟 `shift` 做 bitwise or 運算。而 `x >> 1` 則是當最高位是在第 1 位時，需要再多加上這一位數。最後 `+ 1` 是因為我們要取的是 $\lceil log_2(x) \rceil$ ，即取上界，故還要再多加 1 。
```c
return (r | shift | x >> 1) + 1;
```
### 讓上述程式支援 `x == 0` 的情況
由於 $\log_2 0$ 結果未定義，故我們定義此函式處理 `x` 為 0 時，輸出為 0 。
程式一開始先判斷是否為 0 ，把判斷結果存到 `zero`。
最後回傳結果時，把輸出結果乘上 `!zero` ，即若 `x` 為 0 時，則輸出結果會乘上 0 ，否則乘上 1 ，就可以確保在 `x` 為 0 時，輸出為 0 。
這樣子就可以達到沒有分支，又可以正確處理 `x == 0` 的情況。
```c
int ceil_log2(uint32_t x)
{
uint32_t r, shift;
int zero = (x == 0);
x--;
r = (x > 0xFFFF) << 4;
x >>= r;
shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;
shift = (x > 0xF) << 2;
x >>= shift;
r |= shift;
shift = (x > 0x3) << 1;
x >>= shift;
return ((r | shift | x >> 1) + 1) * !zero;
}
```
### Linux 核心內 ceil 和 log2 的組合，及應用
Sign in with Wallet
Connect another wallet