---
tags: linux2023
---
# [2023q1](http://wiki.csie.ncku.edu.tw/linux/schedule) 第 3 週測驗題
:::info
目的: 檢驗學員對 bitwise, alignment, C 語言程式設計的認知
:::
==[作答表單: 測驗 1-2](https://docs.google.com/forms/d/e/1FAIpQLSeBT6aUILfntZvv4I73IU3qw-rbpdu7GuosBz1gnw7Er5lkuw/viewform)== (針對 Linux 核心「設計」課程)
==[作答表單: 測驗 3-4](https://docs.google.com/forms/d/e/1FAIpQLSeSwhdbw3Rh7fghROajaiuFlN55SsMHYt-yazpqjWZiSPN8QQ/viewform)== (針對 Linux 核心「實作」課程)
### 測驗 `1`
考慮一個 [Tree sort](https://en.wikipedia.org/wiki/Tree_sort) 的實作，搭配 [Red–black tree](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree) 作為排序所需的自我平衡樹，原始程式碼可見 [treesort.c](https://gist.github.com/jserv/920766d1fd893d0efd66ac7fdaf23401)。部分程式碼已遮蔽，請補完程式碼，使其運作符合預期。
作答規範:
* `AAAA` : 利用〈[你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)〉提到利用 ABI 特性來「標示不用的節點」手段，以 bitwise 操作，對給定的引數 `(r)` 計算合法的記憶體地址 (記得要考慮 alignment)。
* `BBBB` 和 `CCCC` : 運用〈[你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics)〉和〈[你所不知道的 C 語言: bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)〉，以 bitwise 操作分別設定紅黑數節點的顏色。
* `DDDD`, `EEEE`, `HHHH` 是 C 語言敘述
* `FFFF` 和 `GGGG` 則運用〈[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)〉，是合法的 C 語言敘述
* 當使用 bitwise 操作時，應該將變數/引數名稱放在左側，常數 (儘量用最精簡的形式！) 放在右側，例如 `r | 1`
* 上述皆不包含 `;`，並該依循 [CONTRIBUTING.md](https://github.com/sysprog21/lab0-c) 程式碼風格規範 (注意空白！)，用最精簡的程式碼書寫
:::success
延伸問題:
1. 指出 `treesort.c` 程式碼的缺失並改進
2. 利用 Linux 核心的 [list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 標頭檔改寫並整合進第一次作業的實驗程式碼中，探討 [Tree sort](https://en.wikipedia.org/wiki/Tree_sort) 的效率
3. 研讀 Linux 核心的 [Red–black tree](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree) 程式碼，比較給定的 `treesort.c` 實作手法，指出後者的改進空間並予以實作
:::
---
### 測驗 `2`
考慮一個使用 [AVL tree](https://en.wikipedia.org/wiki/AVL_tree) 實作的 [priority queue](https://en.wikipedia.org/wiki/Priority_queue)，部分程式碼如下:
```c
#include "avltree.h"
struct avl_prio_queue {
struct avl_root root;
struct avl_node *min_node;
};
static inline void avl_prio_queue_init(struct avl_prio_queue *queue)
{
INIT_AVL_ROOT(&queue->root);
queue->min_node = NULL;
}
static inline void avl_prio_queue_insert_unbalanced(
struct avl_prio_queue *queue,
struct avlitem *new_entry)
{
struct avl_node *parent = NULL;
struct avl_node **cur_nodep = &queue->root.node;
struct avlitem *cur_entry;
int isminimal = 1;
while (*cur_nodep) {
cur_entry = avl_entry(*cur_nodep, struct avlitem, avl);
parent = *cur_nodep;
if (cmpint(&new_entry->i, &cur_entry->i) <= 0) {
cur_nodep = &((*cur_nodep)->left);
} else {
cur_nodep = &((*cur_nodep)->right);
isminimal = 0;
}
}
if (isminimal)
queue->min_node = &new_entry->avl;
avl_link_node(&new_entry->avl, parent, cur_nodep);
}
static inline struct avlitem *avl_prio_queue_pop_unbalanced(
struct avl_prio_queue *queue)
{
struct avlitem *item;
bool removed_right;
if (!queue->min_node)
return NULL;
item = avl_entry(queue->min_node, struct avlitem, avl);
queue->min_node = avl_next(queue->min_node);
avl_erase_node(&item->avl, &queue->root, &removed_right);
return item;
}
tatic inline void avl_prio_queue_insert_balanced(
struct avl_prio_queue *queue,
struct avlitem *new_entry)
{
struct avl_node *parent = NULL;
struct avl_node **cur_nodep = &queue->root.node;
struct avlitem *cur_entry;
int isminimal = 1;
while (*cur_nodep) {
cur_entry = avl_entry(*cur_nodep, struct avlitem, avl);
parent = *cur_nodep;
if (cmpint(&new_entry->i, &cur_entry->i) <= 0) {
cur_nodep = &((*cur_nodep)->left);
} else {
cur_nodep = &((*cur_nodep)->right);
isminimal = 0;
}
}
if (isminimal)
queue->min_node = &new_entry->avl;
avl_insert(&new_entry->avl, parent, cur_nodep, &queue->root);
}
static inline struct avlitem *avl_prio_queue_pop_balanced(
struct avl_prio_queue *queue)
{
struct avlitem *item;
if (!queue->min_node)
return NULL;
item = avl_entry(queue->min_node, struct avlitem, avl);
queue->min_node = avl_next(queue->min_node);
avl_erase(&item->avl, &queue->root);
return item;
}
```
其中 `avltree.h` 的程式碼可見 [avltree.h](https://gist.github.com/jserv/d03098d57fec03c89fdb2a449d7f6be2)。部分程式碼已遮蔽，請補完程式碼，使其運作符合預期。
作答規範:
* `IIII`, `JJJJ`, `KKKK`, `LLLL` 利用〈[你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)〉提到利用 ABI 特性來「標示不用的節點」手段，以 bitwise 操作，計算合法的記憶體地址 (記得要考慮 alignment)。
* `MMMM` 和 `NNNN` 為函式名稱
* 當使用 bitwise 操作時，應該將變數/引數名稱放在左側，常數 (儘量用最精簡的形式！) 放在右側，例如 `r | 1`
* 上述皆不包含 `;`，並該依循 [CONTRIBUTING.md](https://github.com/sysprog21/lab0-c) 程式碼風格規範 (注意空白！)，用最精簡的程式碼書寫
:::success
延伸問題
1. 解釋上述程式碼運作原理，並比較用紅黑樹實作的 [priority queue](https://en.wikipedia.org/wiki/Priority_queue)，應提供完整的測試程式和效能分析
2. Linux 核心也有 AVL tree 的身影，但陸續被紅黑樹替代，請揣摩 Linux 核心開發者的考慮因素，並搭配 git log 來解讀
> 見 commit [b145425](https://github.com/torvalds/linux/commit/b145425f269a17ed344d737f746b844dfac60c82)
3. 研讀 Linux 核心原始程式碼，指出曾經/現在使用 AVL tree 的部分，對照 Linux 核心的 `rbtree.h`，探究是否可用後者替換，從而爭取到貢獻程式碼到 Linux 核心的機會
:::
---
### 測驗 `3`
[Linear feedback shift register](https://en.wikipedia.org/wiki/Linear-feedback_shift_register) (LFSR) 是指給定前一狀態，將該輸出的線性函數作為輸入的移位暫存器，其應用包括 [PRNG](https://en.wikipedia.org/wiki/Pseudorandom_number_generator) 場景。
LFSR 範例:
1. 初始狀態 $s = [s_2, s_1, s_0] = [1, 0, 0]$
2. 反饋 $p = [p_2, p_1, p_0] = [0, 1, 1]$
3. 線性運算 `s[n+1] = s[n]*p[2] ^ s[n-1]*p[1] ^ s[n-2]*p[0]`
考慮一個運用 LFSR 來產生隨機數，並使其均勻分佈於 64 位元無號整數的有效空間 (distribution of uniformly arbitrarily large `uint64_t`)。參考執行輸出如下:
```
0:91263 | 1:93093 | 2:92113 | 3:92503 | 4:92253 |
5:91833 | 6:93023 | 7:92283 | 8:93473 | 9:92983 |
10:90433 | 11:92373 | 12:91733 | 13:93733 | 14:92193 |
...
105:81623 | 106:82253 | 107:82573 | 108:82393 | 109:82483 |
110:82643 | 111:81483 | 112:82473 | 113:80623 | 114:82833 |
115:81703 | 116:82213 | 117:80603 | 118:81143 | 119:81253 |
```
程式碼可參見 [bucket_uniform.c](https://gist.github.com/jserv/15c6ef4383d5d010326cdc4382ffdd1d) (部分程式碼遮蔽):
* `log2_64` : 計算以 2 為底的 x 的對數 (logarithm of x to the base b)，且下取整函數 (floor)
* `bucket_number` : 在指定區間內，使產生的 LFSR 數值得以均勻分佈
請補上程式碼，使程式碼的執行結果符合參考輸出。作答規範:
* `AAAA`, `BBBB`, `CCCC`, `DDDD`, `EEEE`, `FFFF`, `GGGG`, `HHHH` 皆為大於或等於 `0` 的整數
* `IIII` 和 `JJJJ` 是 `mask111` 或 `mask011`
:::success
延伸問題:
1. 解釋 [Linear feedback shift register](https://en.wikipedia.org/wiki/Linear-feedback_shift_register) (LFSR) 的運作原理，搭配在 [Linux 核心原始程式碼](https://github.com/torvalds/linux)中，用 `git log` 和 `grep` 找出 LFSR 的應用案例
2. 解釋上述程式碼運作的原理
3. 在 Linux 核心原始程式碼中找到 $\log_2(x)$ 的實作 (整數)，要涵蓋不同的整數型態寬度，以及是否能運用微處理器提供的指令來加速。也從 Linux 核心找出整數 $\log_2(x)$ 的應用案例並解說。
4. `lab0-c` 提供類似的實作 [log2_lshift16.h](https://github.com/sysprog21/lab0-c/blob/master/log2_lshift16.h)，解釋其原理並嘗試改進其效能
:::
---
### 測驗 `4`
已知輸入必為大於 `0` 的數值 (即 `x > 0`)，以下程式碼可計算 $\lceil log_2(x) \rceil$ ，也就是 [ceil](https://man7.org/linux/man-pages/man3/ceil.3.html) 和 [log2](https://man7.org/linux/man-pages/man3/log2.3.html) 的組合並轉型為整數:
```cpp
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` 應以最簡潔的形式撰寫，且符合[作業一](https://hackmd.io/@sysprog/linux2023-lab0)排版規範 (近似 Linux 核心程式碼排版風格)
* `KKKK` 為表示式，限制使用 `^`, `&`, `|`, `<<`, `>`> 這幾個運算子，可能會出現常數
* `KKKK` 不該包含小括號 (即 `(` 和 `)`)
* 為了自動批改的便利，變數出現的順序 (可從缺) 從左到右為 `r`, `shift`, `x`
* `KKKK` 不可包含 `,` 和 `;` 這樣的分隔符號 (separator)
:::success
延伸問題:
1. 解釋上述程式碼運作原理
2. 改進程式碼，使其得以處理 `x = 0` 的狀況，並仍是 branchless
3. 在 Linux 核心原始程式碼找出 ceil 和 log2 的組合 (類似的形式)，並解說應用案例，例如在 Linux 核心排程器就有
> 善用 [lxr](https://elixir.bootlin.com/linux/latest/source) 和 `git log`
:::
---
Sign in with Wallet
Connect another wallet