# linux2023: zoo868e
## 測驗$\alpha-1$
- `st_rotate_left`: 旋轉左子樹變平衡
- `st_rotate_right`: 旋轉右子樹變平衡
- `st_balance`: 左子樹高度-右子樹高度
- `st_max_hint`: 樹的高度
- `st_update`: `st_balance` < -1，代表右子樹太重，所以要`st_rotate_right`，反之，要`st_rotate_left`。在`st_update`的最後會檢查hint是否改變，若是改變，親代的hint就可能改變，因此要向上更新。另外，由於rotate的操作只有在update中會發生，所以也只有在`st_update`中需要更新hint
- `st_insert`: 需要提供`root`, `parent`, `node`和`dir`。`root`是整棵樹的根，`parent`代表`node`的親代，`dir`則代表`node`是在`parent`的左邊還是右邊。實作方法直觀，將`node`附值給`parent`的`dir`，將`parent`設為`node`的親代，`st_update`樹的`parent`這個節點，因為可能需要rotate，這會更新整棵樹。
- `st_replace_[left/right]`: 用`l/r`節點覆寫`n`節點
- `st_remove`: 刪除節點`del`。如果有右子樹會先用右子樹的最小值複寫`del`，若沒有右子樹則會用左子樹的最大值覆寫`del`。若沒有子樹則直接刪除即可。當我們把least/most節點移動到`del`時，我們需要更新他原本的親代的`hint`，同時，如果因為移動導致不平衡，需要旋轉成平衡子樹。
```c
void st_remove(struct st_node **root, struct st_node *del)
{
if (st_right(del)) {
struct st_node *least = st_first(st_right(del));
if (del == *root)
*root = least;
st_replace_right(del, st_first(least));
st_update(root, st_parent(del));
return;
}
if (st_left(del)) {
struct st_node *most = st_last(st_left(del));
if (del == *root)
*root = most;
st_replace_left(del, st_last(most));
st_update(root, st_parent(del));
return;
}
if (del == *root) {
*root = 0;
return;
}
/* empty node */
struct st_node *parent = st_parent(del);
if (st_left(parent) == del)
st_left(parent) = 0;
else
st_right(parent) = 0;
st_update(root, parent);
}
```
- `container_of`: 透過`offsetof`取得類別成員在記憶體中，在pack中的相對位置，再用該成員的記憶體位置減去該相對位置，從而得到該類的記憶體位置
## 測驗$\alpha-2$
在`st_remove`中會先檢查是否有右子樹，若沒有右子樹則會檢查左子樹。由於這是一個平衡樹，且左右子樹高度差不大於1，所以在沒有右子樹的時候，即便有左子樹也只會有一個節點。所以我們不需要再去找左子樹中的最大值，可以省略`st_last`。並且，由於`st_replace_left`之後，`del`不會再有子代，所以直接更新`del`即可。
```c
if (st_left(del)) {
if (del == *root)
*root = st_left(del);
st_replace_left(del, st_left(del));
st_update(root, st_parent(del));
return;
}
```
## 測驗$\alpha-3$
根據[doc/Documentation/rbtree.txt](https://www.kernel.org/doc/Documentation/rbtree.txt)比較`rbtree`與`S-Tree`的效能。使用**Uftrace**比較兩者在Insert以及Remove時，所使用的旋轉次數以及耗費時間。
1. Insert
- 無序
- 有序
2. Search
- 無序
- 有序
4. Remove
- 無序
- 有序
## 測驗$\beta-1$
觀察alignment = 4 = 0100的情況
```
118 = 01110110 --align_up--> 1111000
119 = 01110111 --align_up--> 1111000
120 = 01111000 --align_up--> 1111000
121 = 01111001 --align_up--> 1111100
122 = 01111010 --align_up--> 1111100
```
可以發現`align_up`做的事情就是在第一、二個位元有1的時候，將其清空，並且加上`alignment`。再觀察alignment = 8 = 1000的情況
```
62 = 00111110 --align_up--> 01000000
63 = 00111111 --align_up--> 01000000
64 = 01000000 --align_up--> 01000000
65 = 01000001 --align_up--> 01001000
66 = 01000010 --align_up--> 01001000
```
跟alignment = 4時的狀況相似，只是多了第三的位元。所以我們根據觀察寫出第一個版本的`align_up`。
```clike=
static inline uintptr_t align_up(uintptr_t sz, size_t alignment)
{
uintptr_t mask = alignment - 1;
if ((alignment & mask) == 0) {
uintptr_t ret = sz;
if (sz & mask)
return (sz & ~mask) + mask + 1;
return sz;
}
return (((sz + mask) / alignment) * alignment);
}
```
但是我們希望不要使用`if`來完成`align_up`。再觀察一次`align_up`的步驟
```
sz = 119 = 01110111
alignment = 4 = 00000100
mask = 00000011, ~mask = 11111100
sz & mask = 00000011
sz & ~mask = 01110100
(sz & ~mask) + mask + 1 = 1110100 + 0100
```
再觀察`align_up`之後會是一樣的數，可以發現在需要進行上述步驟的數值都是即便-1之後再做一樣的步驟還是會有一樣的結果。同時，已經對其的數值(116)在-1之後，如果做同樣的步驟，也會得到相同的結果
```
alignment = 4 = 00000100
113 = 01110001 --align_up--> 01111100
114 = 01110010 --align_up--> 01111100
115 = 01110011 --align_up--> 01111100
116 = 01111100 --align_up--> 01111100
```
所以先將`sz`-1，就不需要判斷是否需要對齊
```clike=
static inline uintptr_t align_up(uintptr_t sz, size_t alignment)
{
uintptr_t mask = alignment - 1;
if ((alignment & mask) == 0) {
return ((sz - 1) & ~mask) + mask + 1;
}
return (((sz + mask) / alignment) * alignment);
}
```
由於經過`(sz - 1) & ~mask`之後，`+ mask`等價於`| mask`，所以我們可以改寫成這樣
```c
static inline uintptr_t align_up(uintptr_t sz, size_t alignment)
{
uintptr_t mask = alignment - 1;
if ((alignment & mask) == 0) {
return ((sz - 1) & ~mask | mask) + 1;
}
return (((sz + mask) / alignment) * alignment);
}
```
最後，可以發現先`& ~mask`再`| mask`等價於`| mask`，因此答案應該是這樣
```c
static inline uintptr_t align_up(uintptr_t sz, size_t alignment)
{
uintptr_t mask = alignment - 1;
if ((alignment & mask) == 0) {
return ((sz - 1) | mask) + 1;
}
return (((sz + mask) / alignment) * alignment);
}
```
---
## 測驗$\beta-2$
## 測驗$\gamma-1$
觀察後發現`HHHH`是發生在狀態改變為`ts_idle`的時候，只有在做完`qsort-algo`之後才會改變為`ts_idle`的狀態。所以再來要做的事情應該是等待`ts_term`。查找當狀態改變為`ts_term`時的行為，可以看到在`f3`以及`JJJJ`之前都會改變狀態為`ts_term`，由於`JJJJ`是我們要寫的作業，因此推測這裡的行為跟`f3`是一樣的，都需要發送訊號給`qs->cond_st`。
## 測驗$\gamma-2$
透過**ThreadSanitizer**檢查data race的問題
1. 先用`clang`編譯`qsort-mt.c`
```shell=
clang -fsanitize=thread -O2 qsort-mt.c -o qsort -g
```
2. 執行`qsort`得到ThreadSanitizer的報告，發現有一個data race的問題
```=
==================
WARNING: ThreadSanitizer: data race (pid=49080)
Write of size 4 at 0x7b4000000080 by thread T1 (mutexes: write M0):
#0 allocate_thread /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c:201:21 (qsort+0xd184a) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
#1 qsort_algo /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c:301:14 (qsort+0xd184a)
#2 qsort_thread /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c:338:3 (qsort+0xcc91a) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
Previous read of size 4 at 0x7b4000000080 by thread T2 (mutexes: write M1):
#0 qsort_thread /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c:329:14 (qsort+0xcc8c7) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
Location is heap block of size 256 at 0x7b4000000000 allocated by main thread:
#0 calloc <null> (qsort+0x4be67) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
#1 qsort_mt /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c:124:17 (qsort+0xcc1f6) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
#2 main /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c (qsort+0xcd0f2) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
Mutex M0 (0x7ffc84940bb0) created at:
#0 pthread_mutex_init <null> (qsort+0x4ec1f) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
#1 qsort_mt /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c:122:7 (qsort+0xcc1bd) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
#2 main /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c (qsort+0xcd0f2) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
Mutex M1 (0x7b40000000a8) created at:
#0 pthread_mutex_init <null> (qsort+0x4ec1f) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
#1 qsort_mt /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c:128:9 (qsort+0xcc254) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
#2 main /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c (qsort+0xcd0f2) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
Thread T1 (tid=49088, running) created by main thread at:
#0 pthread_create <null> (qsort+0x4d41d) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
#1 qsort_mt /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c:136:9 (qsort+0xcc2c0) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
#2 main /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c (qsort+0xcd0f2) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
Thread T2 (tid=49089, running) created by main thread at:
#0 pthread_create <null> (qsort+0x4d41d) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
#1 qsort_mt /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c:136:9 (qsort+0xcc2c0) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
#2 main /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c (qsort+0xcd0f2) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
SUMMARY: ThreadSanitizer: data race /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c:201:21 in allocate_thread
==================
ThreadSanitizer: reported 1 warnings
```
## 測驗$\gamma-3$
Sign in with Wallet
Connect another wallet