---
title: 2023q1 Homework3 (quiz3)
tags: Linux核心設計
---
# [2023q1 Homework3 (quiz3)](https://hackmd.io/@sysprog/linux2023-quiz3)
## [測驗一](https://hackmd.io/@sysprog/linux2023-quiz3#%E6%B8%AC%E9%A9%97-1)
### 程式碼原理
在 [include/linux/rbtree_types.h](https://github.com/torvalds/linux/blob/master/include/linux/rbtree_types.h) 中 `tree node` 宣告為
```c
struct rb_node {
unsigned long __rb_parent_color;
struct rb_node *rb_right;
struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
```
而在 [incomplete treesort.c](https://gist.github.com/jserv/920766d1fd893d0efd66ac7fdaf23401) 中 `tree node` 宣告為
```c
typedef struct __node {
uintptr_t color;
struct __node *left, *right;
struct __node *next;
long value;
} node_t __attribute__((aligned(sizeof(long))));
```
在看完 [Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree#Linux-%E6%A0%B8%E5%BF%83%E7%9A%84%E7%B4%85%E9%BB%91%E6%A8%B9%E5%AF%A6%E4%BD%9C) 得知，透過 `__attribute__((aligned(sizeof(long))))` 讓編譯器知道 `struct rb_node` 會對齊 `sizeof(long)`，這樣就會讓指標最低 2 個位元是沒有使用到的，就可以把顏色的資料放進去其中一個位元中。舉例來說，一個節點指標如果指向 `0xF724315C` ，這個位址轉成二進位會變成 `...1100`，最低 2 個位元會是 0，Linux 核心開發者利用這特性，將其中一個沒用到的位元拿來標注紅和黑這二種顏色。
```c
#define rb_parent(r) ((node_t *) (AAAA))
#define rb_color(r) ((color_t) (r)->color & 1)
```
可以看到會將 `color` 的最後一個 bit 當作顏色來使用，而 Linux kernel 會將親代節點跟顏色一起宣告，因為指標會對齊 `sizeof(long)` ，也就是 8 個 bytes ，所以指標的地址會是 8 的倍數，所以指標的最後 3 個 bits 不會使用到，故將指標最後 3 個 bits 設成 0 ，就能得到親代節點的地址，也就是將地址與 `11....11000` 作 and ，而 `11....11000` 只要將 `00...00111` ，也就是 `7` 取反位元運算就能得到，所以 `AAAA` 為 `(r)->color & ~7` 。
```c
typedef enum { CMAP_RED = 0, CMAP_BLACK } color_t;
```
可以看到將節點顏色紅色設成 0，黑色設成 1。
```c
#define rb_set_red(r) \
do { \
BBBB; \
} while (0)
```
要將節點設成紅色的，只須將最後一個 bit 設成 0 即可，也就是將地址與 `11....11110` 作 and，而 `11....11110` 只要將 `00...00001` ，也就是 `1` 取反位元運算就能得到，所以 `BBBB` 為 `(r)->color &= ~1`。
```c
#define rb_set_black(r) \
do { \
CCCC; \
} while (0)
```
將節點設成紅色的，只須將最後一個 bit 設成 1 即可，所以只須 `or 1` 即可，故 `CCCC` 為 `(r)->color |= 1` 。
```c
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_insert` ，主要是用來加入節點到紅黑樹中，變數 `res` 存放的是插入節點與目前走訪節點的比較值，0 表示相等，-1 表示插入節點小於目前走訪節點，1 表示插入節點大於目前走訪節點。
當 `res = 0` 時，則表示紅黑樹中已經有相同的數存在，所以不須插入。當 `res = -1` 時，會有兩種情形，第一種情形是目前走訪節點沒有左子節點，則將要插入節點設成目前走訪節點的左子節點，再調整顏色跟節點關係，第二種情形是目前走訪節點有左子節點，因為尚未得知後續節點的值大小，所以需要繼續往左子節點走訪，故 `DDDD` 為 `cur = cur->left` ，而 `res = -1` 時，也為同理，繼續往右子點走訪，故 `EEEE` 為 `cur = cur->right` 。
```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);
}
```
再來是函式 `tree_sort` ，執行 `tree_sort` 須走訪每一個節點，所以一開始將節點一個個插入紅黑樹中，所以 `FFFF` 應為往下一個節點移動，`list` 為指向節點指標的指標，所以應先取出指標的地址 `*list` ，再找出下一個節點 `(*list)->next` ，再將這個指標的位址給 `list` ，所以 `FFFF` 為 `&(*list)->next` 。
```c
static node_t *cmap_first(cmap_t obj)
{
node_t *n = obj->head;
if (!n)
return NULL;
while (n->left)
n = n->left;
return n;
}
```
函式 `cmap_first` 為找出最小的節點，而 `cmap_next` 會找出比目前節點還大，但是比其他所有節點還小的點，再將他們串接起來，所以 `GGGG` 跟 `FFFF` 一樣為 `&(*list)->next`，最後當所有節點走訪完，將最後一個節點指向 `NULL`，所以 `HHHH` 為 `*list = NULL` 。
### 答案
:::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`
:::
---
## [測驗二](https://hackmd.io/@sysprog/linux2023-quiz3#%E6%B8%AC%E9%A9%97-2)
### 程式碼原理
```c
struct avl_node {
unsigned long parent_balance;
struct avl_node *left, *right;
} AVL_NODE_ALIGNED;
```
```c
#define AVL_NODE_ALIGNED __attribute__((aligned(sizeof(unsigned long))))
```
架構與測驗一紅黑樹類似，指標也是對齊 `sizeof(long)` 。
```c
static inline struct avl_node *avl_parent(struct avl_node *node)
{
return (struct avl_node *) (IIII);
}
```
故要取得親代節點的位址，只須將最後 3 個 bits 設成 0 即可，所以 `IIII` 為 `node->parent_balance & ~7` 。
```c
enum avl_node_balance { AVL_NEUTRAL = 0, AVL_LEFT, AVL_RIGHT, };
```
再來看到 `balance` 的定義，當左右子樹高度相等時為 0 ，當左子樹較右子樹高 1 時為 1 ，當右子樹較左子樹高 1 時為 2 ，所以總共需要 2 個 bits 來表示。
```c
static inline enum avl_node_balance avl_balance(const struct avl_node *node)
{
return (enum avl_node_balance)(JJJJ);
}
```
所以只須取得最右邊 2 個 bits 即可，故 `JJJJ` 為 `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);
}
```
再來要設定新的親代節點時，需要保留 `balance` 的資訊，也就是最右邊 3 個 bits，剩下的 bit 為舊的親代節點位址，故只須與舊位址的最右邊 3 個 bits `or` 即可，故 `KKKK` 為 `node->parent_balance & 3` 。
```c
static void avl_set_balance(struct avl_node *node, enum avl_node_balance balance)
{
node->parent_balance = (LLLL) | balance;
}
```
而要設定新的 `balance` 資訊時，只須留下除了最右邊 3 個 bits 以外的 bits 即可，故 `LLLL` 為 `node->parent_balance & ~7` 。
```c
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;
}
}
```
函式 `avl_insert_balance` 主要是用來平衡 AVL tree，主要會有 4 種情形需要做 rotation，分別是 LL 型、 LR 型、 RR 型、 RL 型，此 `else` 為 L 情形，所以 `case AVL_NEUTRAL:` 為 LL 型，而 `case AVL_RIGHT:` 為 LR 型，故 LL 型須做右旋，所以 `MMMM` 為 `avl_rotate_right` ，而 LR 型須先做左旋，再做右旋，所以 `NNNN` 為 `avl_rotate_leftright` 。
### 答案
:::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`
:::
---
## [測驗三](https://hackmd.io/@sysprog/linux2023-quiz3#%E6%B8%AC%E9%A9%97-3)
### 程式碼原理
```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 _
};
```
`log_table_256` 可以處理的以 2 為底的 x 的對數，可以看到只有 $2^8$ ，所以若要處理 64 bit 的數值，只能將數值拆解成每 8 bit 進行處理。
```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];
}
}
}
...
}
```
函式 `log2_64` 是用來計算以 2 為底的 x 的對數 (logarithm of x to the base b)，且下取整函數 (floor)，因為 `log_table_256` 只能處理 $2^8$ 的數，所以不難看出須以每 8 個 bit 進行處理。`t` 為將輸入右移 56 個 bit 的數，這裡以 $2^{57}$ 為例，`t` 會等於 1，而 $2^{57}$ 取 log 會等於 57 ，所以我們可以知道 output `r` 為 57 ，所以 `AAAA + log_table_256[1]` = 57 ，而 `log_table_256[1]` 查表為 0 ，所以 `AAAA` 為 56 。
```
2^57 >> 56 = 00...001
t = 1
log_table_256[1] = 1
AAAA + log_table_256[1] = 57
AAAA + 1 = 57
AAAA = 56
```
而 `BBBB` 為輸入大於 48 個 bit ，小於 56 個 bit 的情形，所以 `BBBB` 可以推得為 48 ，以此類推，以每 8 bit 為範圍去分。
```c
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 */
}
```
再來看函式 `lfsr` ，[LFSR](https://en.wikipedia.org/wiki/Linear-feedback_shift_register) 的功用為指給定前一狀態，將該輸出的線性函數作為輸入的移位暫存器，這裡用於產生隨機數。
```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.
*/
}
```
先來看函式 `bucket_number` 其作用為在指定區間內，使產生的 LFSR 數值得以均勻分佈，當 `N_BUCKETS` 為 120 時， `mask111` 與 `mask011` 分別為 127 與 63 ，`lep` 用來判定輸入值的最右邊 7 bit 是否會小於等於 `bucket_number` 。
```
N_BUCKETS = 120
N_BITS = log2_64(120) = 6
mask111 = (1 << (N_BITS + 1)) - 1 = (1 << (6 + 1)) - 1 = 127
mask011 = (1 << (N_BITS)) - 1 = (1 << (6)) - 1 = 63
```
因為`lep` 只為 0 或 1 ，所以 `(leq * (x & IIII)) + ((1 - leq) * ((x >> (N_BITS + 1)) & JJJJ));` 會有兩種 case
```
case1: x & IIII
case2: ((x >> (N_BITS + 1)) & JJJJ
```
當`lep = 1`，則表示輸入值的最右邊 7 bit 會小於等於 `bucket_number`，所以輸出 `x & mask111` 即可，故 `IIII` 為 `mask111` ，而若超過 `bucket_number` 時，則用不同組的 bit ，所以會先右移 `N_BITS` (7) ，因為該值可能會超過 `bucket_number` ，所以與 `mask111` `and` 確保不會超過 `bucket_number` 。
### 答案
:::success
* `AAAA = 56`
* `BBBB = 48`
* `CCCC = 40`
* `DDDD = 32`
* `EEEE = 24`
* `FFFF = 16`
* `GGGG = 8`
* `HHHH = 0`
* `IIII = mask111`
* `JJJJ = mask011`
:::
---
## [測驗四](https://hackmd.io/@sysprog/linux2023-quiz3#%E6%B8%AC%E9%A9%97-4)
### 程式碼原理
```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;
}
```
`x` 分別跟四個不同值比較，分別是 $2^{16}-1$, $2^{8}-1$, $2^{4}-1$, $2^{2}-1$，也就是將 x 拆解成四個區間去判斷，並將其對數大小的結果存於變數 `r` 裡面，，當 `x` 大於第一個區間時，會將 16 存在 `r` 中，並將 `x` 右移 16 個 bit ，再去判斷剩下的 bit 在哪個區間裡，而可以看到在 $2^{2}-1$ 時，並無將其對數大小的結果存於變數 `r` 裡，所以最後須作 `r | shift` ，而這些區間加總為 16 + 8 + 4 + 2 = 30 ，所以若 `x` 大於 $2^{30}$ ，則最後的 `x` 會剩 2 個 bit ，於是將其右移1，去判斷其值是否大於 $2^{30}$ 或大於 $2^{31}$ ，所以 `KKKK` 為 `r | shift | x >> 1`，最後加 1 是為了取其對數的上界。
:::success
* `KKKK = r | shift | x >> 1`
:::
Sign in with Wallet
Connect another wallet