2021q1 Homework2 (quiz2)

# 2021q1 Homework2 (quiz2) contributed by < `cyrong` > ## Q1: Linux 核心 [list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 與 mergesort ### 解釋上述程式碼運作原理，指出改進空間並著手實作 #### `container_of` ```cpp /** * container_of() - Calculate address of object that contains address ptr * @ptr: pointer to member variable * @type: type of the structure containing ptr * @member: name of the member variable in struct @type * * Return: @type pointer of object containing ptr */ #ifndef container_of #define container_of(ptr, type, member) \ __extension__({ \ const __typeof__(((type *) 0)->member) *__pmember = (ptr); \ (type *) ((char *) __pmember - offsetof(type, member)); \ }) #endif ``` `__extension__` 代表程式要使用 GNU extension ，加上 `__extension__` 後可以去除 compile warning [參考資料](https://gcc.gnu.org/onlinedocs/gcc/Alternate-Keywords.html#index-_005f_005fextension_005f_005f) `__typeof__()` 會回傳傳入值的型態，並使用此型態宣告 `__pmember` 最後一步 ```c (type *) ((char *) __pmember - offsetof(type, member)); ``` 先是使用 `(char *)` 取得 `__pmember` 的絕對位址之後再減去 `offsetof(type, member)` 就可以得到這個 type 的開頭位址最後用 `(type *)` 把開頭位址轉型成 pointer to `type` 在這裡有幾個點可以探討 1. `((type *) 0)->member` 被傳進了 `__typeof__` 先看一下 `__typeof__` 的 argument 要輸入什麼參考 gcc onlinedoc 中的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html#Typeof) `typeof` 要輸入的 argument 是 expression or type 看起來 `((type *) 0)->member` 是一個 expression 再進一步分析 `(type *) 0` = 0 is cast to a pointer to struct type，也就是說這段是一個指標 `((type *) 0)->member` 把 0 做 member offset 的位移後取值此時的型態就會是 member 的型態，因為已經將 0 轉型為 type 再放入 `typeof` 中就可以得到 struct 中 member 的型態 2. `({})` 的使用，其實就是在括號中作運算，詳情可見 [gcc statement and declaration in expression](https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html) #### `INIT_LIST_HEAD` ```cpp /** * INIT_LIST_HEAD() - Initialize empty list head * @head: pointer to list head */ static inline void INIT_LIST_HEAD(struct list_head *head) { head->next = head; head->prev = head; } ``` 對 list head 作初始化，一開始的 head 中 next 和 prev 都是自己 #### `list_add_tail()` ```cpp /** * list_add_tail() - Add a list node to the end of the list * @node: pointer to the new node * @head: pointer to the head of the list */ static inline void list_add_tail(struct list_head *node, struct list_head *head) { struct list_head *prev = head->prev; prev->next = node; node->next = head; node->prev = prev; head->prev = node; } ``` 先做一個 `*prev` 為 `head->prev` 也就是 tail 接下來對這個 tail 跟 head 作配合操作就可以 add tail 了 #### `list_del()` ```cpp /** * list_del() - Remove a list node from the list * @node: pointer to the node */ static inline void list_del(struct list_head *node) { struct list_head *next = node->next, *prev = node->prev; next->prev = prev; prev->next = next; } ``` 用傳入的 `*node` 得到這個 node 的前後兩個 node 並接在一起，便成功作到 del node 的效果 #### `list_empty()` ```cpp /** * list_empty() - Check if list head has no nodes attached * @head: pointer to the head of the list */ static inline int list_empty(const struct list_head *head) { return (head->next == head); } ``` 回傳 `head->next` 是否為 `head` 代表如果只有 `head` 此 list 就是 empty #### `list_is_singular()` ```cpp /** * list_is_singular() - Check if list head has exactly one node attached * @head: pointer to the head of the list */ static inline int list_is_singular(const struct list_head *head) { return (!list_empty(head) && head->prev == head->next); } ``` 回傳 list 是否只有一個 node 若 `head->next` 和 `head->prev` 相同代表只有一個 node #### `list_splice_tail` ```cpp /** * list_splice_tail() - Add list nodes from a list to end of another list * @list: pointer to the head of the list with the node entries * @head: pointer to the head of the list */ static inline void list_splice_tail(struct list_head *list, struct list_head *head) { struct list_head *head_last = head->prev; struct list_head *list_first = list->next, *list_last = list->prev; if (list_empty(list)) return; head->prev = list_last; list_last->next = head; list_first->prev = head_last; head_last->next = list_first; } ``` 把 `list` 中所有的 node 接到 `head` 的尾端不需要重新鏈接，只需要有 node 們的 first 和 last 把 first 接到 `head` 尾，再將 last 接到 `head->prev` 就完成了 #### `list_cut_position()` ```cpp /** * list_cut_position() - Move beginning of a list to another list * @head_to: pointer to the head of the list which receives nodes * @head_from: pointer to the head of the list * @node: pointer to the node in which defines the cutting point */ 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; } ``` 將 `head_from` 中的 `node` 以前的所有 nodes 都搬到 `head_to` 後 #### `list_entry()` ```cpp /** * list_entry() - Calculate address of entry that contains list node * @node: pointer to list node * @type: type of the entry containing the list node * @member: name of the list_head member variable in struct @type */ #define list_entry(node, type, member) container_of(node, type, member) ``` 利用 `container_of` 找到輸入 node 之初始位址 #### `list_first_entry()` ```cpp /** * list_first_entry() - get first entry of the list * @head: pointer to the head of the list * @type: type of the entry containing the list node * @member: name of the list_head member variable in struct @type */ #define list_first_entry(head, type, member) \ list_entry((head)->next, type, member) ``` 使用 `list_entry()` 但是輸入的 node 為 `(head)->next` 因此得到的會是 list 中的第一個 node #### `list_for_each()` ```cpp /** * list_for_each - iterate over list nodes * @node: list_head pointer used as iterator * @head: pointer to the head of the list */ #define list_for_each(node, head) \ for (node = (head)->next; node != (head); node = node->next) ``` 利用 for 迴圈走訪 list 所有節點 #### 搭配使用的 merge sort ```c= #include <string.h> 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; 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); } static void list_merge(struct list_head *lhs, struct list_head *rhs, struct list_head *head) { INIT_LIST_HEAD(head); if (list_empty(lhs)) { list_splice_tail(lhs, head); return; } if (list_empty(rhs)) { list_splice_tail(rhs, head); return; } while (!list_empty(lhs) && !list_empty(rhs)) { char *lv = list_entry(lhs->next, list_ele_t, list)->value; char *rv = list_entry(rhs->next, list_ele_t, list)->value; struct list_head *tmp = strcmp(lv, rv) <= 0 ? lhs->next : rhs->next; list_del(tmp); list_add_tail(tmp, head); } list_splice_tail(list_empty(lhs) ? rhs : lhs, head); } 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); } ``` #### `get_middle()` 這段程式碼用的手法是 `slow` 每動一格 `fast` 就會動兩格而等到 `fast` 到達 list 尾端時走過的 node 數是 list 的大小 `n` 這時 `slow` 正好走過 `n/2` 也就是 list 的中間了 #### `list_merge()` 這裡是在作 mergesort 的合併 `lhs` 代表 left hand side， `rhs` 代表 right hand side 從兩邊 list 的頭開始走完兩個 list 的所有 node 合併進 `head` #### quiz 題目 20 行的 `COND1` 和 `COND2` 是為了判斷 `slow` 是否已經到達了 list 的中間而分成 `COND1` 和 `COND2` 的原因是 `n` 可能是奇數或偶數 `COND1` 對應的是偶數的情況 `fast->next == list` `COND2` 對應的是奇數的情況 `fast->next->next == list` 24 行是已經找到 middle 了並且要得到其位址 middle 也就是 `slow` 因此 `TTT` 傳入 `slow` 59 行的目的是把 `list` 切成兩半，分別再作 mergesort `MMM` 是要找的 middle node ，所以應該要用 `get_middle()` 要注意的是 `get_middle()` 回傳的 type 是 `list_ele_t` 但是 `list_cut_position()` 要輸入的參數是 `list_head *` 因此要對找到的 `list_ele_t` 的 `list` 作取值，並且傳入他的位址，參數型態才會對參數型態的問題在 `get_middle()` 也要注意，要傳入的是 `list_head *` 所以 `MMM` 答案應是 `&(get_middle(&q->list)->list)` --- ## Q2: power-of-2 ### 解釋程式碼 ```c= uint16_t func(uint16_t N) { /* change all right side bits to 1 */ N |= N >> 1; N |= N >> X; N |= N >> Y; N |= N >> Z; return (N + 1) >> 1; } ``` 假定 N = 10101~2~ = 21~10~，那麼 func(21) 要得到 16，請補完程式碼，使其運作符合預期。 16~10~ = 10000~2~ 而 `return (N + 1) >> 1` = 10000~2~ 可以回推 `N` 是 11111~2~ 再從程式碼第3行看 ```c=3 N |= N >> 1; ``` `N` = `10101 | (10101 >> 1)` = `10101 | 1010` = `11111` 雖然這樣看起來就是答案了不過程式需要的功能是 change all right side bits to 1 在這個 `uint16_t` 的 type 下，最大的值就是 16 個 bits 都是 1 會是 1 的最高位也就是 16 要做到可以把最高位 1 的 right side 都變成 1 假設現在要操作的值是 `1000 0000 0000 0000` 作第三行的操作後是 `1100 0000 0000 0000` 用 4 步去把 1 個 1 用 `>>` 複製成 16 個最好的方法就是每次都可以把 1 的數量加倍 `1100 0000 0000 0000` => `1111 0000 0000 0000` => `1111 1111 0000 0000` => `1111 1111 1111 1111` 之後要位移的量就分別是 2, 4, 8 因此 `X = 2` `Y = 4` `Z = 8` ## Q3: bitcpy 考慮到一個 `bitcpy` 實作，允許開發者對指定的記憶體區域，逐 bit 進行資料複製。 ### 解釋程式碼 ```c= #include <stdint.h> 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); static const uint8_t read_mask[] = { 0x00, /* == 0 00000000b */ 0x80, /* == 1 10000000b */ 0xC0, /* == 2 11000000b */ 0xE0, /* == 3 11100000b */ 0xF0, /* == 4 11110000b */ 0xF8, /* == 5 11111000b */ 0xFC, /* == 6 11111100b */ 0xFE, /* == 7 11111110b */ 0xFF /* == 8 11111111b */ }; static const uint8_t write_mask[] = { 0xFF, /* == 0 11111111b */ 0x7F, /* == 1 01111111b */ 0x3F, /* == 2 00111111b */ 0x1F, /* == 3 00011111b */ 0x0F, /* == 4 00001111b */ 0x07, /* == 5 00000111b */ 0x03, /* == 6 00000011b */ 0x01, /* == 7 00000001b */ 0x00 /* == 8 00000000b */ }; while (count > 0) { uint8_t data = *source++; size_t bitsize = (count > 8) ? 8 : count; if (read_lhs > 0) { RRR; if (bitsize > read_rhs) data |= (*source >> read_rhs); } if (bitsize < 8) data &= read_mask[bitsize]; 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. DDD; *dest++ = (original & mask) | (data >> write_lhs); } count -= bitsize; } } ``` 輸入的參數有 dest, src, write offset, read offset, count 一開始會有一些變數設定有 `read_lhs / rhs`, `write_lhs / rhs` 以及作過處理的 `source` 跟 `dest` ```c=9 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); ``` `read_lhs` = `_read` & `7` = `_read` % `8` `read_rhs` = `8` - `read_lhs` `read_lhs` 目的是留下 read offset 的 0 ~ 2 bit 的值因為程式是以一個 byte 作處理所以配合 `read_rhs` left 處理開頭，right 處理收尾而 `source` 的處理 ```c const uint8_t *source = (const uint8_t *) _src + (_read / 8); ``` 讓 `source` 是 `_src` 移動 `(_read / 8)` 個單位，也就是 `(_read / 8)` bytes `source` 就是開始讀取的地方 `write_lhs` 和 `write_rhs` 的作法和 read 一樣 `dest` 則是和 `source` 一樣接著是兩個 mask 是為了方便等一下的 `bitcpy` 方便使用 ```c=16 static const uint8_t read_mask[] = { 0x00, /* == 0 00000000b */ 0x80, /* == 1 10000000b */ 0xC0, /* == 2 11000000b */ 0xE0, /* == 3 11100000b */ 0xF0, /* == 4 11110000b */ 0xF8, /* == 5 11111000b */ 0xFC, /* == 6 11111100b */ 0xFE, /* == 7 11111110b */ 0xFF /* == 8 11111111b */ }; static const uint8_t write_mask[] = { 0xFF, /* == 0 11111111b */ 0x7F, /* == 1 01111111b */ 0x3F, /* == 2 00111111b */ 0x1F, /* == 3 00011111b */ 0x0F, /* == 4 00001111b */ 0x07, /* == 5 00000111b */ 0x03, /* == 6 00000011b */ 0x01, /* == 7 00000001b */ 0x00 /* == 8 00000000b */ }; ``` 最下面的 while 迴圈就是在作 bit copy ```c=40 while (count > 0) { uint8_t data = *source++; size_t bitsize = (count > 8) ? 8 : count; if (read_lhs > 0) { RRR; if (bitsize > read_rhs) data |= (*source >> read_rhs); } if (bitsize < 8) data &= read_mask[bitsize]; 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. DDD; *dest++ = (original & mask) | (data >> write_lhs); } count -= bitsize; } ``` 41~42 創一個 `uint8_t` data 是當前的 `source`，之後 `source`++， `source` 進到下個 byte `bitsize` 最大到 8 為了方便使用 mask 43~47 `if (read_lhs > 0)` 這裡判斷有沒有需要對 `data` 作調整要讓 `data` 是要讀的第一個 byte 的第 `read_lhs` 到第 7 個 bit ( bit 是 0~7 ) 然後再接上下一個 byte 從 0 開始的 `read_rhs` 個 bits `RRR` 要作的是把 `data` 往左 shift `read_lhs` 次 `RRR` = `data <<= read_lhs` 下一個判斷是要複製的 `bitsize` 有沒有超過 `read_rhs` 也就是有沒有要跨 byte 如果有就把下個 byte 從 0 開始的 `read_rhs` 個 bits 複製到 data 前 `read_rhs` 個 bits 49~50 如果 `bitsize` 不到 8 就把用不到的 bits 清掉手法是利用 `read_mask` 54~58 要複製的 `bitsize` 會超出當前 byte 因此要作兩次複製目前的 byte 利用 `mask` 操作，最後留下的資料是: 前 `write_lhs` bits 保持原狀，後面的 bits 換成 `data >> write_lhs` 下一個 byte 操作前，先置換 `original` 把 `original` 換成下一個 byte 的 original 而`write_mask` 把不會操作到的 bits 保持原狀進到下一個 byte 操作把剛剛做好的 `original` & `data << write_rhs` 59~63 `else` 指 `bitsize` 個 bit 操作不會超出 byte bound 因此只需要改 `bitsize` 個 bit ，其他 bits 都要保持原狀因此 `mask` 要改成除了前 `write_lhs` 個 bit 保持外還要保持 `write_lhs` + `bitsize` 後的 bits 因此 `DDD` |= `write_mask[write_lhs + bitsize]` `write_mask[write_lhs + bitsize]` 就是剛才提到 `write_lhs` + `bitsize` 後的 bits `mask` 做好後用 `original` 與 `mask` 調整好再複製 `data >> write_lhs`

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.