# 2021q1 Homework2 (quiz2)
contributed by < `gyes00205` >
###### tags: `linux2021`
> [作業要求](https://hackmd.io/@sysprog/ByHRgtofu)
## 測驗一
### 仿效 Linux 核心 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 的精簡實作
#### 結構定義
一個環狀雙向 linked list 其結構定義為:
```cpp
struct list_head {
struct list_head *prev, *next;
};
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_add_tail
將節點加到 list 尾端
```cpp
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;
}
```
I. `*prev = head->prev;`
```graphviz
digraph linkedlist {
layout="circo"
node [shape=box];
"prev(f)" [style="filled", fillcolor=lightblue]
"head(a)" [style="filled", fillcolor="red"]
rankdir=LR
{
rankdir=LR
"head(a)"->b [label="next"] b->c->d->e->"prev(f)"->"head(a)"
"head(a)"->"prev(f)" [label="prev"] "prev(f)"->e->d->c->b->"head(a)"
}
}
```
II.
```cpp
prev->next = node;
node->next = head;
node->prev = prev;
head->prev = node;
```
```graphviz
digraph linkedlist {
layout="circo"
node [shape=box];
"prev(f)" [style="filled", fillcolor=lightblue]
"head(a)" [style="filled", fillcolor="red"]
"node" [style="filled", fillcolor=green]
rankdir=LR
{
rankdir=LR
"head(a)"->b [label="next"] b->c->d->e->"prev(f)"->"node"->"head(a)"
"head(a)"->"node" [label="prev"] "node"->"prev(f)"->e->d->c->b->"head(a)"
}
}
```
#### list_del
並沒有真的釋放節點的記憶體空間，而是把它從原本的串列移除而已。
```cpp
static inline void list_del(struct list_head *node)
{
struct list_head *next = node->next, *prev = node->prev;
next->prev = prev; prev->next = next;
}
```
I. `*next = node->next, *prev = node->prev;`
```graphviz
digraph linkedlist {
layout="circo"
node [shape=box];
"prev(a)" [style="filled", fillcolor=lightblue]
"next(b)" [style="filled", fillcolor="red"]
"node" [style="filled", fillcolor=green]
rankdir=LR
{
rankdir=LR
"node"->"next(b)"[label="next"] "next(b)"->c->d->e->f->"prev(a)"->"node"
"prev(a)"->f->e->d->c->"next(b)"->"node" "node"->"prev(a)" [label="prev"]
}
}
```
II. `next->prev = prev; prev->next = next;`
```graphviz
digraph linkedlist {
layout="circo"
node [shape=box];
"prev(a)" [style="filled", fillcolor=lightblue]
"next(b)" [style="filled", fillcolor="red"]
rankdir=LR
{
rankdir=LR
"next(b)"->c->d->e->f->"prev(a)"->"next(b)"
"prev(a)"->f->e->d->c->"next(b)"->"prev(a)"
}
}
```
#### list_is_singular
判斷是否只有一個節點，如果只有一個節點，就不需要排序
```cpp
static inline int list_is_singular(const struct list_head *head)
{
return (!list_empty(head) && head->prev == head->next);
}
```
#### INIT_LIST_HEAD
初始化空的 list ，next 和 prev 皆指向 head 本身
```cpp
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head; head->prev = head;
}
```
```graphviz
digraph linkedlist {
node [shape=box];
rankdir=LR
{
rankdir=LR
head->head [dir=both]
}
}
```
### 解釋 doubly-linked list 的 merge sort
#### 1. 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 (fast->next || fast->next->next)
break;
fast = fast->next->next;
}
return list_entry(slow, list_ele_t, list);
}
```
其中 `list_for_each` 的定義如下
```cpp
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
```
這與上個作業 [lab0](https://hackmd.io/ftRycx6nQWqzuYl4f14cVA?view#q_sort) 相似，就是透過 fast 和 slow 的前進速度不同，當 fast 指向 list 尾端，slow 則會指向大約中間的位置。
* 第一次 for 迴圈
```graphviz
digraph linkedlist {
layout="circo"
node [shape=box];
"list" [style=filled, fillcolor=green]
"slow:b" [fontcolor=red];
"fast:d" [fontcolor=blue];
rankdir=LR
{
rankdir=LR
list->"slow:b"->c->"fast:d"->e->f->list
}
}
```
* 第二次 for 迴圈
```graphviz
digraph linkedlist {
layout="circo"
node [shape=box];
"list" [style=filled, fillcolor=green]
"slow:c" [fontcolor=red];
"fast:f" [fontcolor=blue];
rankdir=LR
{
rankdir=LR
list->b->"slow:c"->d->e->"fast:f"->list
}
}
```
* 第三次 for 迴圈，此時因為 `fast->next == list`，所以離開迴圈，這時候 slow 指向 d
```graphviz
digraph linkedlist {
layout="circo"
node [shape=box];
"list" [style=filled, fillcolor=green]
"slow:d" [fontcolor=red];
"fast:f" [fontcolor=blue];
rankdir=LR
{
rankdir=LR
list->b->c->"slow:d"->e->"fast:f"->list
}
}
```
```cpp
typedef struct __element {
char *value;
struct __element *next;
struct list_head list;
} list_ele_t;
```
得到 slow 的位置後，再透過 `list_entry(slow, list_ele_t, list)` 得到 `struct list_ele_t` 的位址。
:::info
這裡的 list 是 `struct list_ele_t` 中的 member 名稱
:::
#### 2. list_merge
一開始先判斷 `lhs` 和 `rhs` 是否為空，如果為空則不需要排序，直接回傳就好。
```cpp
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);
}
```
這裡的 `list_splice_tail(lhs, head);` 和 `list_splice_tail(lhs, head);` 有多此一舉的效果，因為在 `list_splice_tail` 中會再判斷一次 `lhs` 和 `rhs` 是否為空，所以可以直接移除。
```diff
if (list_empty(lhs)) {
- list_splice_tail(lhs, head);
return;
}
if (list_empty(rhs)) {
- list_splice_tail(rhs, head);
return;
}
```
:::warning
可簡化為 `if (list_empty(lhs) || list_empty(rhs)) return;`
:notes: jserv
:::
I. 初始狀態
```graphviz
digraph linkedlist {
node [shape=box];
"lhs" [style="filled", fillcolor=green]
"rhs" [style="filled", fillcolor=green]
"head" [style="filled", fillcolor=lightblue]
rankdir=LR
{
rankdir=LR
"lhs"->a [label="next"]
a->d->"lhs"
}
{
rankdir=LR
"rhs"->b [label=next]
b->c->"rhs"
}
{
head->head [dir=both]
}
}
```
II. 第一次 while 迴圈
```graphviz
digraph linkedlist {
node [shape=box];
"lhs" [style="filled", fillcolor=green]
"rhs" [style="filled", fillcolor=green]
"head" [style="filled", fillcolor=lightblue]
rankdir=LR
{
rankdir=LR
"lhs"->d [label="next"]
d->"lhs"
}
{
rankdir=LR
"rhs"->b [label=next]
b->c->"rhs"
}
{
head->a [label=next]
a->head
}
}
```
III. 第二次 while 迴圈
```graphviz
digraph linkedlist {
node [shape=box];
"lhs" [style="filled", fillcolor=green]
"rhs" [style="filled", fillcolor=green]
"head" [style="filled", fillcolor=lightblue]
rankdir=LR
{
rankdir=LR
"lhs"->d [label="next"]
d->"lhs"
}
{
rankdir=LR
"rhs"->c [label=next]
c->"rhs"
}
{
head->a [label=next]
a->b->head
}
}
```
IIII. 第三次 while 迴圈
```graphviz
digraph linkedlist {
node [shape=box];
"lhs" [style="filled", fillcolor=green]
"rhs" [style="filled", fillcolor=green]
"head" [style="filled", fillcolor=lightblue]
rankdir=LR
{
rankdir=LR
"lhs"->d [label="next"]
d->"lhs"
}
{
rankdir=LR
"rhs"->"rhs" [dir=both]
}
{
head->a [label=next]
a->b->c->head
}
}
```
V. 因為 `rhs` 為空，所以離開 while 迴圈，並將 `lhs` 接在 `head` 尾端。
```graphviz
digraph linkedlist {
node [shape=box];
"head" [style="filled", fillcolor=lightblue]
rankdir=LR
{
head->a [label=next]
a->b->c->d->head
}
}
```
#### 3. list_merge_sort
`q->list` 是要做 merge sort 的串列，而 `left.list` 剛做完初始化所以還是空的串列。
```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, &get_middle(&q->list)->list);
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);
}
```
* `list_cut_position(&left.list, &q->list, &get_middle(&q->list)->list);` 將 `q` 分成兩半，一邊是 `left` 一邊是 `q`
```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;
}
```
I. 起始狀態
```graphviz
digraph linkedlist {
node [shape=box];
rankdir=LR
{
rankdir=LR
head_to->head_to [dir=both]
}
{
rankdir=LR
head_from->1->2->3->head_from
}
{
rank=same
"node"->2
}
{
rank=same
"head_from_first"->1
}
"node" [shape=plaintext, fontcolor=blue]
"head_from_first" [shape=plaintext, fontcolor=blue]
}
```
II. 做完 `list_cut_position` 後
```graphviz
digraph linkedlist {
node [shape=box];
rankdir=LR
{
rankdir=LR
head_to->1->2->head_to
}
{
rankdir=LR
head_from->3->head_from
}
{
rank=same
"node"->2
}
{
rank=same
"head_from_first"->1
}
"node" [shape=plaintext, fontcolor=blue]
"head_from_first" [shape=plaintext, fontcolor=blue]
}
```
```cpp
list_merge_sort(&left);
list_merge_sort(q);
list_merge(&left.list, &q->list, &sorted);
```
透過遞迴將 `left` 和 `q` 繼續分成兩半，直到剩下一個節點或串列為空。接著將排序好的串列合併。
```cpp
INIT_LIST_HEAD(&q->list);
list_splice_tail(&sorted, &q->list);
```
`sorted` 是排序好的串列，不過他的資料結構為 `struct list_head` ，所以重新初始化 `queue_t q` ，並將 `sorted` 接在 `queue_t q` 上
---
## 測驗二
考慮函式 `func` 接受一個 16 位元無號整數 $N$ ，並回傳小於或等於 $N$ 的 power-of-2
```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;
}
```
首先將遇到的第一個值為 1 的 bit 的右邊所有 bit 都設為 1，最後 +1 並往右移一個 bit
以 N = $32768_{10}$ = $1000000000000000_2$ 為例
* `N |= N >> 1;`
$N$ = $1100000000000000_2$
* `N |= N >> 2;`
$N$ = $1111000000000000_2$
* `N |= N >> 4;`
$N$ = $1111111100000000_2$
* `N |= N >> 8;`
$N$ = $1111111111111111_2$
* `(N + 1) >> 1;`
$N$ = $1000000000000000_2$
:::warning
N + 1 已經 overflow 了，那為甚麼 (N + 1) >> 1 不會出錯呢?
改進方法: 參考[你所不知道的 C 語言：數值系統](/@sysprog/c-numerics)
>* 比方說 `(x + y) / 2` 這樣的運算，有個致命問題在於 (x + y) 可能會導致 overflow (考慮到 x 和 y 都接近 [UINT32_MAX](https://msdn.microsoft.com/en-us/library/mt764276.aspx)，亦即 32-bit 表示範圍的上限之際)
* [Binary search 的演算法提出之後十年才被驗證](https://www.comp.nus.edu.sg/~sma5503/recitations/01-crct.pdf)
* 於是我們可以改寫為以下:
```
(x & y) + ((x ^ y) >> 1)
```
>* 用加法器來思考: x & y 是進位, x ^ y 是位元和, / 2 是向右移一位
>* 位元相加不進位的總和: x ^ y; 位元相加產生的進位值: (x & y) << 1
>* x + y = x ^ y + ( x & y ) << 1
>* 所以 (x + y) / 2
= (x + y) >> 1
= (x ^ y + (x & y) << 1) >> 1
= (x & y) + ((x ^ y) >> 1)
```diff=
- (N + 1) >> 1
+ (N & 1) + ((N ^ 1) >> 1)
```
:::
---
## 測驗三
### bitcpy
#### 初始化變數
`read_lhs` 為位元組中，不需要複製的部分，真正需要複製的地方為 `read_rhs` ；同理 `write_lhs` 為不需要寫入的部分， `write_rhs` 才是需要寫入的部分。 `source` 為開始複製的位元組， `dest` 為開始寫入的位元組。
:::info
`source` 和 `dest` 的單位為 bytes 的位址 。 `read_lhs` , `read_rhs` , `read_lhs` , `read_rhs` 的單位是 bits
:::
第 3 行 `(_read / 8);` 可以改寫為 `(_read >> 3);` 平移花的成本較除法低；同理 `(_write / 8)` 也可以改寫為 `(_write >> 3)`。
```diff=
size_t read_lhs = _read & 7;
size_t read_rhs = 8 - read_lhs;
- const uint8_t *source = (const uint8_t *) _src + (_read / 8);
+ const uint8_t *source = (const uint8_t *) _src + (_read >> 3);
size_t write_lhs = _write & 7;
size_t write_rhs = 8 - write_lhs;
- uint8_t *dest = (uint8_t *) _dest + (_write / 8);
+ uint8_t *dest = (uint8_t *) _dest + (_write >> 3);
```
```cpp=
while (count > 0) {
uint8_t data = *source++;
size_t bitsize = (count > 8) ? 8 : count;
if (read_lhs > 0) {
data <<= read_lhs;
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.
mask |= write_mask[write_lhs + bitsize];
*dest++ = (original & mask) | (data >> write_lhs);
}
count -= bitsize;
}
```
* 複製資料
`data` 複製 `source` 所指向的位元組內容。 `bitsize` 為複製的 bits 數，每次最多複製 8-bit 。第 4 行判斷複製的 bit 有沒有對齊 MSB ，沒有的話就將 data 左移。第 6 行判斷有沒有跨位元組，有的話就將 `source` 右移(此時的 `source` 已經是下一個位元組了)，並和 `data` 做 bitwise or operation，也就是將資料複製到 `data` 的 right hand side 。第 10 行把超過 `bitsize` 的部分改為 0 避免寫入。
* 寫入資料
第 15 行 `if (bitsize > write_rhs)` 判斷是否需要跨位元組。
如果需要的話，`*dest++ = (original & mask) | (data >> write_lhs);` 先將 `data` 的一部分寫入 `dest` 右半邊。 `original = *dest & write_mask[bitsize - write_rhs];` 保留 `dest` 的右半部(此時的 `dest` 已經到下一個位元組)，`*dest = original | (data << write_rhs);` 將 `data` 剩下的部分複製到 `dest`。
如果不需要的話，代表 `bitsize + write_lhs <= 8` ， `*dest++ = (original & mask) | (data >> write_lhs);` 將 `data` 寫入 `dest`。
第 4~11 行可以簡化如下，省去判斷的成本。
```diff
- if (read_lhs > 0) {
- data <<= read_lhs;
- if (bitsize > read_rhs)
- data |= (*source >> read_rhs);
- }
- if (bitsize < 8)
- data &= read_mask[bitsize];
+ data <<= read_lhs;
+ data |= (*source >> read_rhs);
+ data &= read_mask[bitsize];
```
---
## 測驗四
#### `cstr.h`
```cpp
enum {
CSTR_PERMANENT = 1,
CSTR_INTERNING = 2,
CSTR_ONSTACK = 4,
};
```
* `CSTR_PERMANENT` : TODO
* `CSTR_INTERNING` : 常數字串
* `CSTR_ONSTACK` : 字串變數
```cpp
typedef struct __cstr_data {
char *cstr;
uint32_t hash_size;
uint16_t type;
uint16_t ref;
} * cstring;
```
* cstr : 字串內容
* hash_size : 字串長度
* type : 字串類型(`CSTR_PERMANENT`, `CSTR_INTERNING`, `CSTR_ONSTACK`)
* ref : 和多少字串共用記憶體空間
```cpp
typedef struct __cstr_buffer {
cstring str;
} cstr_buffer[1];
```
```cpp
#define CSTR_BUFFER(var) \
char var##_cstring[CSTR_STACK_SIZE] = {0}; \
struct __cstr_data var##_cstr_data = {var##_cstring, 0, CSTR_ONSTACK, 0}; \
cstr_buffer var; \
var->str = &var##_cstr_data;
```
初始化變數類型的 `var` 以及相關變數， [the ## operator](https://www.ibm.com/docs/en/zos/2.3.0?topic=mdd-operator) 可以用來連接變數名稱。宣告一個 char array ， size 為 `CSTR_STACK_SIZE (128)` 並且初始化為 0 並且 assign 給 `__cstr_data` 的 `cstr` 。最後 assign 給 `cstr_buffer` 的 `str` 。
```cpp
#define CSTR_LITERAL(var, cstr) \
static cstring var = NULL; \
if (!var) { \
cstring tmp = cstr_clone("" cstr, (sizeof(cstr) / sizeof(char)) - 1); \
if (tmp->type == 0) { \
tmp->type = CSTR_PERMANENT; \
tmp->ref = 0; \
} \
if (!__sync_bool_compare_and_swap(&var, NULL, tmp)) { \
if (tmp->type == CSTR_PERMANENT) \
free(tmp); \
} \
}
```
初始化常數類型的字串
### cstr_cat
```cpp=
cstring cstr_cat(cstr_buffer sb, const char *str)
{
cstring s = sb->str;
if (s->type == CSTR_ONSTACK) {
int i = s->hash_size;
while (i < CSTR_STACK_SIZE - 1) {
s->cstr[i] = *str;
if (*str == 0)
return s;
++s->hash_size;
++str;
++i;
}
s->cstr[i] = 0;
}
cstring tmp = s;
sb->str = cstr_cat2(tmp->cstr, str);
cstr_release(tmp);
return sb->str;
}
```
第 4~15 行
* 必須是 `CSTR_ONSTACK`
* str 已經全部接在 s 後面，且 s 的長度小於 `CSTR_STACK_SIZE - 1` 則直接回傳 s 。
* 如果 s 的長度大於等於 `CSTR_STACK_SIZE - 1` 則要透過 `cstr_cat2` 連接字串。
### cstr_cat2
```cpp=
static cstring cstr_cat2(const char *a, const char *b)
{
size_t sa = strlen(a), sb = strlen(b);
if (sa + sb < CSTR_INTERNING_SIZE) {
char tmp[CSTR_INTERNING_SIZE];
memcpy(tmp, a, sa);
memcpy(tmp + sa, b, sb);
tmp[sa + sb] = 0;
return cstr_interning(tmp, sa + sb, hash_blob(tmp, sa + sb));
}
cstring p = xalloc(sizeof(struct __cstr_data) + sa + sb + 1);
if (!p)
return NULL;
char *ptr = (char *) (p + 1);
p->cstr = ptr;
p->type = 0;
p->ref = 1;
memcpy(ptr, a, sa);
memcpy(ptr + sa, b, sb);
ptr[sa + sb] = 0;
p->hash_size = 0;
return p;
}
```
第 4~10 行，如果長度小於 `CSTR_INTERNING_SIZE(32)` 會進入 `cstr_interning` ，利用 `hash_blob` 產生 hash value 。
第 11 行，如果長度大於等於 `CSTR_INTERNING_SIZE(32)` ，則分配記憶體空間給 `p` ， 其中 `ptr` 的記憶體位置在 `p` 的尾端。
:::warning
因為 `CSTR_INTERNING_SIZE(32)` `CSTR_STACK_SIZE(128)` ，所以第 4 行的 if 永遠進不去
:::
### cstring_interning
```cpp=
static cstring cstr_interning(const char *cstr, size_t sz, uint32_t hash)
{
cstring ret;
CSTR_LOCK();
ret = interning(&__cstr_ctx, cstr, sz, hash);
if (!ret) {
expand(&__cstr_ctx);
ret = interning(&__cstr_ctx, cstr, sz, hash);
}
++__cstr_ctx.total;
CSTR_UNLOCK();
return ret;
}
```
Sign in with Wallet
Connect another wallet