2023q1 Homework3 (quiz3)

--- 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` :::

Read more

2023q1 Homework1 (lab0)

2023q1 Linux核心設計-問題紀錄

2023q1 Homework6 (quiz5)

2023q1 Homework5 (Assessment)