# 2023q1 Homework3 (quiz3)
contributed by < [cin-cout](https://github.com/cin-cout) >
[題目](https://hackmd.io/@sysprog/linux2023-quiz3)
## 測驗一
### 延伸問題:
1. 指出 treesort.c 程式碼的缺失並改進
2. 利用 Linux 核心的 list.h 標頭檔改寫並整合進第一次作業的實驗程式碼中，探討 Tree sort 的效率
3. 研讀 Linux 核心的 Red–black tree 程式碼，比較給定的 treesort.c 實作手法，指出後者的改進空間並予以實作
### Question
考慮一個 Tree sort 的實作，搭配 Red–black tree 作為排序所需的自我平衡樹，原始程式碼可見 [treesort.c](https://gist.github.com/jserv/920766d1fd893d0efd66ac7fdaf23401)。部分程式碼已遮蔽，請補完程式碼，使其運作符合預期。
先簡單介紹一下 [treesort.c](https://gist.github.com/jserv/920766d1fd893d0efd66ac7fdaf23401) 的內容，主要是利用紅黑樹去實作map。
資料結構如下：
tree node 的方面， `color` 紀錄其顏色、`left` `right` 則記錄其左右子節點 `next` 是用來記錄在原本 array 中其下一個位置在 RB tree 中 node 的位置、`value` 則是記錄其值。
```c
typedef struct __node {
uintptr_t color;
struct __node *left, *right;
struct __node *next;
long value;
} node_t __attribute__((aligned(sizeof(long))));
```
map 的資料結構則會記錄 RB tree 的 root，以及其他 map 之中的一些特質(ex size)。
```c
struct cmap_internal {
node_t *head;
/* Properties */
size_t key_size, element_size, size;
cmap_iter_t it_end, it_most, it_least;
int (*comparator)(void *, void *);
};
```
#### AAAA
這邊用了一個特殊的方法來儲存顏色。因為現在電腦多數都是 64 bits (8 bytes)，所以其位置二進位最後三位必為 0。所以這邊就用了 node 的 parent 的位址的第一個 bit 來儲存 node 之顏色，如此一來找 parent 只需要對其顏色做 bit wise 的處理，不須額外花費記憶體空間，紅色為 0 黑色為 1。
由上述邏輯可知要找 node 的 parent 只需把 node 的 color 前三個(或第一個) bits 設為 0 ，故 AAAA = `((r)->color & ~7)`。
```c
typedef enum { CMAP_RED = 0, CMAP_BLACK } color_t;
#define rb_parent(r) ((node_t *) (AAAA))
#define rb_color(r) ((color_t) (r)->color & 1)
```
#### BBBB CCCC
同 AAAA 提到的原理，透過更改其 parent 的 last bit 來記錄顏色，在 set color 時，紅色為 0 ，黑色為 1。
故 BBBB 為 `(r)->color &= ~1`。
故 CCCC 為 `(r)->color |= 1`。
```c
#define rb_set_red(r) \
do { \
BBBB; \
} while (0)
#define rb_set_black(r) \
do { \
CCCC; \
} while (0)
```
#### DDDD EEEE
rb tree insert node 的程式碼如下，DDDD、EEEE 前的部分是在處理 create root 的狀況，為解答出 DDDD、EEEE，我們著重於 for 迴圈的部分。
for 迴圈處的邏輯跟 binary tree insert 的方式類似，即若小於此處的 node 則往左走，反之大於則往右走，直到走到 null 的位置即為要插入的位置。
故 DDDD 為 cur = cur->left。
故 EEEE 為 cur = cur->right。
另外，插入時會需要先 set parent，而 `cmap_fix_colors` 則會對於 ll lr rl rr 的情況去平衡紅黑數。
```c
static bool cmap_insert(cmap_t obj, node_t *node, void *value)
{
cmap_create_node(node);
obj->size++;
if (!obj->head) {
/* Just insert the node in as the new head. */
obj->head = node;
rb_set_black(obj->head);
/* Calibrate the tree to properly assign pointers. */
cmap_calibrate(obj);
return true;
}
/* Traverse the tree until we hit the end or find a side that is NULL */
for (node_t *cur = obj->head;;) {
int res = obj->comparator(&node->value, &cur->value);
if (!res) /* If the key matches something else, don't insert */
assert(0 && "not support repetitive value");
if (res < 0) {
if (!cur->left) {
cur->left = node;
rb_set_parent(node, cur);
cmap_fix_colors(obj, node);
break;
}
DDDD;
} else {
if (!cur->right) {
cur->right = node;
rb_set_parent(node, cur);
cmap_fix_colors(obj, node);
break;
}
EEEE;
}
}
cmap_calibrate(obj);
return true;
}
```
#### FFFF GGGG HHHH
最後則是實際使用 map 的情況，輸入會是一個 list 而 map 則會使用紅黑樹將其排序。
FFFF 是為將 list 內的值一一傳入 map 做 insert，故在每次 while 時都必須將 *list 改下一個值的位置。
故 FFFF = &(*list)->next
for 迴圈的部分是將排序完成後的結果放回 list。每次迴圈都會更新到下一個 node ，GGGG 則是在耕莘 list 的位置。
故 GGGG 同為 &(*list)->next。
將 list 更新完畢以後，必須確保最後一個值的 next 為 null， list 在 for 結束後會落在，tail->next 的位置。
故 HHHH 為 *list = NULL。
```c
void tree_sort(node_t **list)
{
node_t **record = list;
cmap_t map = cmap_new(sizeof(long), sizeof(NULL), cmap_cmp_int);
while (*list) {
cmap_insert(map, *list, NULL);
list = FFFF;
}
node_t *node = cmap_first(map), *first = node;
for (; node; node = cmap_next(node)) {
*list = node;
list = GGGG;
}
HHHH;
*record = first;
free(map);
}
```
### Answer
:::success
AAAA = `((r)->color & ~7)`
BBBB = `(r)->color &= ~1`
CCCC = `(r)->color |= 1`
DDDD = `cur = cur->left`
EEEE = `cur = cur->right`
FFFF = `&(*list)->next`
GGGG = `&(*list)->next`
HHHH = `*list = NULL`
:::
## 測驗二
### 延伸問題:
1. 解釋上述程式碼運作原理，並比較用紅黑樹實作的 priority queue，應提供完整的測試程式和效能分析
2. Linux 核心也有 AVL tree 的身影，但陸續被紅黑樹替代，請揣摩 Linux 核心開發者的考慮因素，並搭配 git log 來解讀
見 commit b145425
3. 研讀 Linux 核心原始程式碼，指出曾經/現在使用 AVL tree 的部分，對照 Linux 核心的 rbtree.h，探究是否可用後者替換，從而爭取到貢獻程式碼到 Linux 核心的機會
### Question
考慮一個使用 AVL tree 實作的 priority queue。
其中 `avltree.h` 的程式碼可見 [avltree.h](https://gist.github.com/jserv/d03098d57fec03c89fdb2a449d7f6be2)。部分程式碼已遮蔽，請補完程式碼，使其運作符合預期。
AVL tree 是嚴格的平衡樹，每一個節點的左子樹高度跟右子樹的高度不差超過 1 。
先講解 AVL tree node 的資料結構：
`left` `right` 是紀錄其左右子節點的位址，`parent_balance` 跟上一題 rb tree node 用了類似的手法，原因以及好處可見上題。後三位 bits 用來儲存此節點 balance 的狀況，高位元用來儲存父節點的位址。
```c
struct avl_node {
unsigned long parent_balance;
struct avl_node *left, *right;
} AVL_NODE_ALIGNED;
```
balance 的狀況有三種，分別為：
`AVL_NEUTRAL (0)` 左右子樹高度相等。
`AVL_LEFT (1)` 左子樹高 1 。
`AVL_RIGHT (2)` 右子樹高 1 。
```c
enum avl_node_balance { AVL_NEUTRAL = 0, AVL_LEFT, AVL_RIGHT, };
```
#### IIII
如同上述的解釋，在找 parent 時，即抓取 parent_balance 的高位元。
故 IIII 為 (node)->parent_balance & ~7。
```c
static inline struct avl_node *avl_parent(struct avl_node *node)
{
return (struct avl_node *) (IIII);
}****
```
#### JJJJ
找 balance 也一樣，即抓取 parent_balance 的最低三位元，因為 balance 只有 0 1 2，所以只會用到最低二位，可以只取最低兩位，放 & 7 也可以。
故 JJJJ 為 (node)->parent_balance & 3。
```c
static inline enum avl_node_balance avl_balance(const struct avl_node *node)
{
return (enum avl_node_balance)(JJJJ);
}
```
#### KKKK
更新 parent 必須要考慮到 parent 跟 balance ， set parent 只要更新父節點的位置，balance 保持一樣。函式中已經有更新 parent 的實作，缺少保留 balance 的實作部分。
故 KKKK 為 (node)->parent_balance & 3。
```c
static void avl_set_parent(struct avl_node *node, struct avl_node *parent)
{
node->parent_balance =
(unsigned long) parent | (KKKK);
}
```
#### LLLL
反之，在更新 balance 時，也必須保持原 parent 的狀況。
故 LLLL 為 (node)->parent_balance & ~7。
```c
static void avl_set_balance(struct avl_node *node,
enum avl_node_balance balance)
{
node->parent_balance = (LLLL) | balance;
}
```
#### MMMM NNNN
最後則是在插入新的節點後平衡的處理。
簡單講解 AVL 樹的平衡方式，首先檢查它是其父節點的左子節點還是右子節點。對於右子節點，它根據父節點的 balance 做出不同的處理。
如果父節點的 balance 是 AVL_LEFT，意味著它的左子樹比右子樹高，這樣 node 插入右側就沒什麼問題。
若是 AVL_RIGHT，意味著它的右子樹比左子樹高，這樣 node 插入右側就則需要做旋轉的處理，處理方式則是依照 node 本身的 balance來決定，來保持 AVL 樹的平衡性。
若是 AVL_NEUTRAL，則需要繼續往上檢查到上面的節點需不需要旋轉。
對於左子節點，它的處理方式類似，只是 balance 的方向相反。
故 MMMM 為 avl_rotate_right。
故 NNNN 為 avl_rotate_leftright。
```c
void avl_insert_balance(struct avl_node *node, struct avl_root *root)
{
struct avl_node *parent;
/* go tree upwards and fix the nodes on the way */
while ((parent = avl_parent(node))) {
if (avl_is_right_child(node)) {
switch (avl_balance(parent)) {
default:
case AVL_RIGHT:
/* compensate double right balance by rotation
* and stop afterwards
*/
switch (avl_balance(node)) {
default:
case AVL_RIGHT:
case AVL_NEUTRAL:
avl_rotate_left(node, parent, root);
break;
case AVL_LEFT:
avl_rotate_rightleft(node, parent, root);
break;
}
parent = NULL;
break;
case AVL_NEUTRAL:
/* mark balance as right and continue upwards */
avl_set_balance(parent, AVL_RIGHT);
break;
case AVL_LEFT:
/* new right child + left leaning == balanced
* nothing to propagate upwards after that
*/
avl_set_balance(parent, AVL_NEUTRAL);
parent = NULL;
break;
}
} else {
switch (avl_balance(parent)) {
default:
case AVL_RIGHT:
/* new left child + right leaning == balanced
* nothing to propagate upwards after that
*/
avl_set_balance(parent, AVL_NEUTRAL);
parent = NULL;
break;
case AVL_NEUTRAL:
/* mark balance as left and continue upwards */
avl_set_balance(parent, AVL_LEFT);
break;
case AVL_LEFT:
/* compensate double left balance by rotation
* and stop afterwards
*/
switch (avl_balance(node)) {
default:
case AVL_LEFT:
case AVL_NEUTRAL:
MMMM(node, parent, root);
break;
case AVL_RIGHT:
NNNN(node, parent, root);
break;
}
parent = NULL;
break;
}
}
if (!parent)
break;
node = parent;
}
}
```
### Answer
:::success
IIII = `(node)->parent_balance & ~7`
JJJJ = `(node)->parent_balance & 3`
KKKK = `(node)->parent_balance & 3`
LLLL = `(node)->parent_balance & ~7`
MMMM = `avl_rotate_right`
NNNN = `avl_rotate_leftright`
:::
## 測驗三
### 延伸問題:
1. 解釋 Linear feedback shift register (LFSR) 的運作原理，搭配在 Linux 核心原始程式碼中，用 git log 和 grep 找出 LFSR 的應用案例
2. 解釋上述程式碼運作的原理
3. 在 Linux 核心原始程式碼中找到 log2(x) 的實作 (整數)，要涵蓋不同的整數型態寬度，以及是否能運用微處理器提供的指令來加速。也從 Linux 核心找出整數 log2(x) 的應用案例並解說。
4. lab0-c 提供類似的實作 log2_lshift16.h，解釋其原理並嘗試改進其效能
### Question
考慮一個運用 LFSR 來產生隨機數，並使其均勻分佈於 64 位元無號整數的有效空間 (distribution of uniformly arbitrarily large uint64_t)。完成 [bucket_uniform.c](https://gist.github.com/jserv/15c6ef4383d5d010326cdc4382ffdd1d) (部分程式碼遮蔽)。
#### AAAA ~ HHHH
先看 log2_64 這個函式，此函式的目的是找到 64 bits 數的 log2 floor int。在測驗中，這個函式的目的是找到一個 64 bits 的 FSB (第一個 1 的) 位置。
使用的方法為，使用不斷的 shift 的方式，找到 64 bits FSB 在哪一個 bytes，使用這個 bytes 去查表找到其 log2 值，最後要加上前面 shift 的數量。
```
舉例：
0x0100000000000000
在例子中 shift 了 48 次。
使用 1 這個 bytes 去查表時，得到的結果為 1 。
所以最後 r 為 49。
```
其意義為，因為找 log2 floor 意及找 FSB 的位置，在這個例子中，我們用查表得到了 1 的 log2 (意及其在這 8 bytes 中 FSB 的位置)，但前面 shift 掉了 1 後面的 48 個 bits，所以最終 FSB 的位置必須加上 48。
故 AAAA 為 56 。
故 BBBB 為 48 。
故 CCCC 為 40 。
故 DDDD 為 32 。
故 EEEE 為 24 。
故 FFFF 為 16 。
故 GGGG 為 8 。
故 HHHH 為 0 。
```c
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 = AAAA + log_table_256[t];
} else {
r = BBBB + log_table_256[tt];
}
} else {
t = ttt >> 8;
if (t) {
r = CCCC + log_table_256[t];
} else {
r = DDDD + log_table_256[ttt];
}
}
} else {
tt = v >> 16;
if (tt) {
t = tt >> 8;
if (t) {
r = EEEE + log_table_256[t];
} else {
r = FFFF + log_table_256[tt];
}
} else {
t = v >> 8;
if (t) {
r = GGGG + log_table_256[t];
} else {
r = HHHH + log_table_256[v];
}
}
}
return r;
}
```
#### IIII JJJJ
IIII JJJJ 在 `bucket_number` 這個函式中，但是在理解怎麼做此函式前，必須知道其用處。
所以我們先解釋，`fill_buckets` 這個函式：
步驟為：
1. while 迴圈會利用多次的 lfsr 找到一個 64 bits 的隨機數 x。
2. 利用這個隨機數，放入 `bucket_number` 得到一個小於設定的 N_BUCKETS 的數，所以得出來的 tmp_bucket 也可以視為 1 隨機數。
以一套這樣的方法，就可以產生固定範圍的隨機數了！
而 for 迴圈只是重複做多次上數的步驟，用來統計產生出來的隨機數。
(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++;
}
}
}
```
如此一來就可以來探討 `bucket_number` 這個函式了，這個函式的目的即為將傳入的 64 bits 整數轉換為一規定範圍內的數字。
首先，有兩種 mask，配合上面 log2_64 的意義，找到一個 64 bits 的 FSB (第一個 1 的) 位置，不難理解其意義：
mask111：包含 FSB 之下的 bits 全為 1。
mask011：不包含 FSB 之下的 bits 全為 1。
之後 leq 的意義為判斷 64 bits 的 x 是否有大於我們設定的 N_BUCKET。
最後的 return 則分為兩種狀況：
1. 若傳入的 x 就已經比 N_BUCKET 小了，直接回傳 x。
2. 若傳入的 x 大於等於 N_BUCKET ，取 x 的高位元段回傳。
第一個很好理解是直接對 mask111 做 and，而第二個因為確保高位元段的值一定比 N_BUCKET 小，所以是跟 mask011 做 and 。
故 IIII 為 mask111。
故 JJJJ 為 mask011。
```c
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 & IIII)) +
((1 - leq) * ((x >> (N_BITS + 1)) & JJJJ));
/* 'x >> (N_BITS + 1)' : take different set of bits -> better uniformity.
* '... & mask011' guarantees that the result is less or equal N_BUCKETS.
*/
}
```
### Answer
:::success
AAAA = `56`
BBBB = `48`
CCCC = `40`
DDDD = `32`
EEEE = `24`
FFFF = `16`
GGGG = `8`
HHHH = `0`
IIII = `mask111`
JJJJ = `mask011`
:::
## 測驗四
### 延伸問題:
1. 解釋上述程式碼運作原理
2. 改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless
3. 在 Linux 核心原始程式碼找出 ceil 和 log2 的組合 (類似的形式)，並解說應用案例，例如在 Linux 核心排程器就有。善用 lxr 和 git log
### Question
已知輸入必為大於 0 的數值 (即 x > 0)，以下程式碼可計算
⌈log2(x)⌉，也就是 ceil 和 log2 的組合並轉型為整數:
```c
int ceil_log2(uint32_t x)
{
uint32_t r, shift;
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 (KKKK) + 1;
}
```
#### KKKK
邏輯跟上一題的 log2 floor 類似，只是不是用 control flow 的方式找到 FSB 所在的位置，而是無論是哪一種情況都能成功計算 FSB 的位置。
接著解釋程式碼：
```c
int ceil_log2(uint32_t x)
{
uint32_t r, shift;
/*
因為是求 ceil ，最後結果都會加 1 ，
但是對於本來就是 2 冪次的數反而會多加 1 ，
所以一開始先減掉 1 避免此問題。
*/
x--;
/*
如果 x 前 16 bits 有值，r = 16 反之 r = 0
r 的意義跟上題類似是用來記錄目前統計到 FSB 後的值。
*/
r = (x > 0xFFFF) << 4;
/*
x shift r 次，即後面 16 位已討論完，繼續討論前 16 位。
若 shift 0 次，即前 16 位沒值，直接討論後 16 位。
*/
x >>= r;
/*
同理，只是改為處理 x 前 16 bits 或後 16 bits，而非 32 bits。
*/
shift = (x > 0xFF) << 3;
/*
因為 r 是代表累計的 shift 數量所以，改為用 shift 紀錄。
*/
x >>= shift;
/*
因為 shift 是從 16 -> 8 -> 4 -> 2 討論。
所以可以利用 r |= shift 代替 r += shift。
*/
r |= shift;
/*
同理。
*/
shift = (x > 0xF) << 2;
x >>= shift;
r |= shift;
shift = (x > 0x3) << 1;
x >>= shift;
/*
最後因為要直接 return 了，所以將 r |= shift ，
直接留在 KKKK 做，而此時 x 還剩下 2 位，所以最後
累計的 shift 還要在 + x>>1 (例如 x = 0b10)。
故 KKKK 為 r | shift | x >> 1。
最後的 + 1 是因為是求 ceil。
*/
return (KKKK) + 1;
}
```
### Answer
:::success
KKKK = `r | shift | x >> 1`
:::
Sign in with Wallet
Connect another wallet