# 2021q1 Homework2 (quiz2)
contributed by < `tiffany6022` >
###### tags: `linux2021`
> [作業說明](https://hackmd.io/@sysprog/linux2021-quiz2)
- [x] 測驗 1
- [x] 解釋上述程式碼運作原理，指出改進空間並著手實作
- [ ] 研讀 Linux 核心的 lib/list_sort.c 原始程式碼，學習 sysprog21/linux-list 的手法，將 lib/list_sort.c 的實作抽離為可單獨執行 (standalone) 的使用層級應用程式，並設計效能評比的程式碼，說明 Linux 核心的 lib/list_sort.c 最佳化手法
- [ ] 將你在 quiz1 提出的改進實作，和 Linux 核心的 lib/list_sort.c 進行效能比較，需要提出涵蓋足夠廣泛的 benchmark
- [x] 測驗 2
- [x] 解釋上述程式碼運作原理
- [ ] 在 The Linux Kernel API 頁面搜尋 "power of 2"，可見 is_power_of_2，查閱 Linux 核心原始程式碼，舉例說明其作用和考量，特別是 round up/down power of 2
- [ ] 特別留意 __roundup_pow_of_two 和 __rounddown_pow_of_two 的實作機制
- [ ] 研讀 slab allocator，探索 Linux 核心的 slab 實作，找出運用 power-of-2 的程式碼和解讀
- [x] 測驗 3
- [x] 解釋上述程式碼運作原理，並嘗試重寫為同樣功能但效率更高的實作
- [ ] 在 Linux 核心原始程式碼找出逐 bit 進行資料複製的程式碼，並解說相對應的情境
- [ ] 測驗 4
- [ ] 解釋上述程式碼運作原理
- [ ] 上述程式碼使用到 gcc atomics builtins，請透過 POSIX Thread 在 GNU/Linux 驗證多執行緒的環境中，string interning 能否符合預期地運作？若不能，請提出解決方案
- [ ] chriso/intern 是個更好的 string interning 實作，請探討其特性和設計技巧，並透過內建的 benchmark 分析其效能表現
## 測驗 1
> cbea
### `list_head` 結構
- doubly-linked list
- 初始化的空鏈結將 `prev` 和 `next` 都指向自身
```cpp
struct list_head {
struct list_head *prev, *next;
};
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head; head->prev = head;
}
```
### `get_middle` 函式
```cpp
static list_ele_t *get_middle(struct list_head *list)
{
struct list_head *fast = list->next, *slow;
list_for_each (slow, list) {
if (COND1 || COND2)
break;
fast = fast->next->next;
}
return list_entry(TTT, list_ele_t, list);
}
```
其中的 `list_for_each` 代入變成 `for (slow = (list)->next; slow != (list); slow = slow->next)`，也就是 `slow = list->next` 開始遍歷每個 node，直到繞一圈又回來 list。
```cpp
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
```
迴圈中只要符合 `COND1` 或 `COND2` 就 break。而此函式的目的為得到 list 的中間節點，因此這裡使用龜兔賽跑演算法，slow 走一步 fast 走兩步，當 fast 走到底時（這裡是回到 list），slow 所在的位置為中間節點，因此回傳 slow。
```cpp
if (fast->next = list || fast->next->next == list)
break;
...
return list_entry(slow, list_ele_t, list);
```
探討在 list 的 node 數為奇數或偶數時的行為。
```
奇數個 node：
s s
f f
h->n->n->n => h->n->n->n
^________| ^________|
偶數個 node：
s s
f f
h->n->n->n->n => h->n->n->n->n
^___________| ^___________|
```
### `list_merge_sort` 函式
```cpp
void list_merge_sort(queue_t *q)
{
if (list_is_singular(&q->list))
return;
queue_t left;
struct list_head sorted;
INIT_LIST_HEAD(&left.list);
list_cut_position(&left.list, &q->list, MMM);
list_merge_sort(&left);
list_merge_sort(q);
list_merge(&left.list, &q->list, &sorted);
INIT_LIST_HEAD(&q->list);
list_splice_tail(&sorted, &q->list);
}
```
`queue_t` 的結構如下:
```cpp
typedef struct __element {
char *value;
struct __element *next;
struct list_head list;
} list_ele_t;
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
size_t size;
struct list_head list;
} queue_t;
```
`list_is_singular` 是用來判斷 list 是否只有一個 node，若只有一個 node 不用做 sort
```cpp
static inline int list_is_singular(const struct list_head *head)
{
return (!list_empty(head) && head->prev == head->next);
}
static inline int list_empty(const struct list_head *head)
{
return (head->next == head);
}
```
`list_cut_position` 將 `head_from` 的 list 以 `node` 為左右切成兩邊，以 `head_from` 和 `head_to` 存取
```cpp
static inline void list_cut_position(struct list_head *head_to,
struct list_head *head_from,
struct list_head *node)
{
struct list_head *head_from_first = head_from->next;
if (list_empty(head_from))
return;
if (head_from == node) {
INIT_LIST_HEAD(head_to);
return;
}
head_from->next = node->next;
head_from->next->prev = head_from;
head_to->prev = node;
node->next = head_to;
head_to->next = head_from_first;
head_to->next->prev = head_to;
}
```
```graphviz
digraph {
rankdir=LR
node [shape=box]
A[label = "head"]
B[label = "n1"]
C[label = "n2"]
D[label = "n3"]
E[label = "n4"]
F[label = "node", shape=none]
G[label = "head_from", shape=none]
A->B->C->D->E
F->C
G->A
{rank=same F C}
{rank=same G A}
}
```
```graphviz
digraph {
rankdir=LR
subgraph graph1 {
node [shape=box]
D[label = "n3"]
E[label = "n4"]
H[label = "head_from (&q->list)", shape=none]
D->E
H->D
{rank=same H D}
}
subgraph graph2 {
node [shape=box]
B[label = "n1"]
C[label = "n2"]
G[label = "head_to (&left.list)", shape=none]
B->C
G->B
{rank=same G B}
}
C->D[style=invisible, dir=none]
}
```
mergesort 演算法會從中間做 divide and conquer，因此這裡的 node 為 list 的中間點，所以 `MMM` 應該要呼叫 `get_middle` 函式。根據函式的輸入和輸出判定 `MMM` = `&get_middle(&q->list)->list`，即
```cpp
list_cut_position(&left.list, &q->list, &get_middle(&q->list)->list);
```
## 測驗 2
> bdh
考慮函式 func 接受一個 16 位元無號整數 N，並回傳小於或等於 N 的 power-of-2。假定 N = 10101(2) = 21(10)，那麼 func(21) 要得到 16。
```cpp
uint16_t func(uint16_t N) {
/* change all right side bits to 1 */
N |= N >> 1;
N |= N >> 2;
N |= N >> 4;
N |= N >> 8;
return (N + 1) >> 1;
}
```
由回傳值 `(N + 1) >> 1` 可以看出上方的程式碼須將最大位元 1 的右方全部設成 1，最後再加 1 right shift 1 即為答案。若以 1000 0000 0000 0000 為例，要將右方都設成 1 的方法即是，先從 1 個開始設，確定 2 個都為 1 後再設 2 個，再來變 4 個 8 個以此類推。
```
1000 0000 0000 0000 // N
1100 0000 0000 0000 // N |= N >> 1
1111 0000 0000 0000 // N |= N >> 2
1111 1111 0000 0000 // N |= N >> 4
1111 1111 1111 1111 // N |= N >> 8
```
## 測驗 3
### `bitcpy` 函式
考慮到一個 bitcpy 實作，允許開發者對指定的記憶體區域，逐 bit 進行資料複製，這個將指定的位元偏移量及位元數複製到目標位址的函式原型宣告如下:
```cpp=
void bitcpy(void *_dest, /* Address of the buffer to write to */
size_t _write, /* Bit offset to start writing to */
const void *_src, /* Address of the buffer to read from */
size_t _read, /* Bit offset to start reading from */
size_t count)
{
size_t read_lhs = _read & 7;
size_t read_rhs = 8 - read_lhs;
const uint8_t *source = (const uint8_t *) _src + (_read / 8);
size_t write_lhs = _write & 7;
size_t write_rhs = 8 - write_lhs;
uint8_t *dest = (uint8_t *) _dest + (_write / 8);
...
}
```
- 第 7-8 行: 以 byte 對齊，若從 `_read` 個 bit 開始讀取，會在當下的 byte 中哪個位置。以 `lhs`: left hand side 和 `rhs`: right hand side 來做紀錄。
- 第 9 行: 透過 `_read` 讀取位置做計算，得出 `source` 在哪個 byte 中的資料。
- 第 10-11 行: 以 byte 對齊，若從 `_write` 個 bit 開始寫入，會在當下的 byte 中哪個位置。也是以 `lhs` 和 `rhs` 做紀錄。
- 第 12 行: 同 9，透過 `_write` 讀取位置做計算，得出 `dest` 在哪個 byte 中的資料。
```cpp=
while (count > 0) {
uint8_t data = *source++;
size_t bitsize = (count > 8) ? 8 : count;
if (read_lhs > 0) {
data <<= read_lhs; // RRR
if (bitsize > read_rhs)
data |= (*source >> read_rhs);
}
if (bitsize < 8)
data &= read_mask[bitsize];
...
}
```
while 迴圈中每次以一個 byte 的大小做複製，長度超過一個 byte 的會在下個迴圈繼續複製。迴圈中的前半部份在計算要複製的資料 `data`。
- 第 2 行：以 `data` 紀錄 `source` 當下的 byte 資料， `source` 再往前一個 byte。
- 第 3 行：一次最多複製 8 bit (1 byte) 的資料大小，若超過 `bitsize` 則設成 8，剩餘的會在下次迴圈中做複製。
- 第 4-8 行：若要開始讀取的位置不是在 byte 的第一個，也就是沒有對齊的話，進入判斷式
- 第 5 行：將 `data` 對齊，`data` 的第一個位置即為要開始讀取的位置資料。
- 第 6 行：若要複製的資料長度超出當前的 byte，`read_rhs` 為當前的 byte 中扣除開始讀取的位置剩餘能讀取的長度。那麼 `data` 就需要將下個 byte 剩下的幾個 bit 複製過來。
- 第 9-10 行：總共需要複製 `bitsize` 個 bit，將沒有要複製的 bit 做清除，由於已經對齊了，所以是將後面剩餘的部分設成0，只留要複製的部分的資料。
```cpp=
while (count > 0) {
...
uint8_t original = *dest;
uint8_t mask = read_mask[write_lhs];
if (bitsize > write_rhs) {
/* Cross multiple bytes */
*dest++ = (original & mask) | (data >> write_lhs);
original = *dest & write_mask[bitsize - write_rhs];
*dest = original | (data << write_rhs);
} else {
// Since write_lhs + bitsize is never >= 8, no out-of-bound access.
mask |= write_mask[write_lhs + bitsize]; // DDD
*dest++ = (original & mask) | (data >> write_lhs);
}
count -= bitsize;
}
```
迴圈中的後半部份是將前面所得的 `data` 寫入 `dest` 裡。
- 第 5 行：`mask` 將 `write_lhs` 以後的位置全部歸 0
- 第 6-10 行：`bitsize` 大於 `write_rhs` 代表要複製的長度超過了當前開始寫入的 byte 的剩餘位置，因此會橫跨下一個 byte。
- 第 8 行：`(original & mask)` 將要複製的位置歸 0，`data >> write_lhs` 為將 data 對齊開始寫入的位置，將他們做 OR 運算就可以把原始資料與要複製的資料合併在一起。設定完這個 byte 後，`dest` 往前到下一個 byte。
- 第 9 行：重新設定這個 byte 的值。`bitsize - write_rhs` 代表了新的這個 byte 要設定的長度。`write_mask` 將這個 byte 的前面歸 0。也就是將 `original` 設成前面幾個要寫入的位置歸 0，後面保持原本的樣子。
- 第 10 行：將 `data` left shift 到要複製到新的 byte 的位置，與 `original` 做 OR 運算，即為新的 byte 的資料。
- 第 11-14 行：沒有橫跨 byte，直接複製即可
- 第 13 行：也就是 `write_lhs + bitsize` 一定小於 8。`write_mask` 將左邊都歸 0，與 `mask` 做 OR 運算代表保留前面的 `write_lfs` 其餘都歸 0。
- 第 14 行：將原始值該歸 0 的地方歸 0 與要複製的值 shift 到該位置，做 OR 運算後即得到這個 byte 應有的值。
- 第 17 行：計算還有多少 `count` 數量需要進行複製。
Sign in with Wallet
Connect another wallet