# linux2023: Eddie-064 - HW1
> [quiz0](https://hackmd.io/@sysprog/linux2023-summer-quiz0)
> [linux2023-summer](https://github.com/Eddie-064/linux2023-summer)
## 測驗 α - 1 : 解釋程式碼運作原理
### S-tree 相關函式
- `st_first` : 以遞迴的方式找到 S-tree 最左邊的節點，而因 S-tree 為一種 BST，因此最左邊的節點也是整個 S-tree 的最小值。
```cpp=
struct st_node *st_first(struct st_node *n)
{
if (!st_left(n))
return n;
return st_first(st_left(n));
}
```
- `st_last` : 以遞迴的方式找到 S-tree 最右邊的節點，也是整個 S-tree 的最大值。
```cpp=
struct st_node *st_last(struct st_node *n)
{
if (!st_right(n))
return n;
return st_last(st_right(n));
}
```
- `st_rotate_left` : 當 AVL tree 左半邊不平衡時，需要做的 rotate 操作。
```cpp=
static inline void st_rotate_left(struct st_node *n)
{
struct st_node *l = st_left(n), *p = st_parent(n);
st_parent(l) = st_parent(n);
st_left(n) = st_right(l);
st_parent(n) = l;
st_right(l) = n;
if (p && st_left(p) == n)
st_left(p) = l;
else if (p)
st_right(p) = l;
if (st_left(n))
st_lparent(n) = n;
}
```
- `st_balance` : 計算 AVL tree 是否平衡，正常值為 -1, 0, 1。
```cpp=
static inline int st_balance(struct st_node *n)
{
int l = 0, r = 0;
if (st_left(n))
l = st_left(n)->hint + 1;
if (st_right(n))
r = st_right(n)->hint + 1;
return l - r;
}
```
- `st_max_hint` : 計算 n 節點的最大高度。
```cpp=
static inline int st_max_hint(struct st_node *n)
{
int l = 0, r = 0;
if (st_left(n))
l = st_left(n)->hint + 1;
if (st_right(n))
r = st_right(n)->hint + 1;
return l > r ? l : r;
}
```
- `st_update` : 判斷以 n 節點為首的子樹是否平衡，如不平衡則做 rotate。最後判斷子樹高度是否有改變，如果改變則執行 `st_update(root, p)` 判斷與 Sibling 是否平衡。
```cpp=
static inline void st_update(struct st_node **root, struct st_node *n)
{
if (!n)
return;
int b = st_balance(n);
int prev_hint = n->hint;
struct st_node *p = st_parent(n);
if (b < -1) {
/* leaning to the right */
if (n == *root)
*root = st_right(n);
st_rotate_right(n);
}
else if (b > 1) {
/* leaning to the left */
if (n == *root)
*root = st_left(n);
st_rotate_left(n);
}
n->hint = st_max_hint(n);
if (n->hint == 0 || n->hint != prev_hint)
st_update(root, p);
}
```
- `st_insert` : 插入 n 節點至指定的 d 位置，確認 s-tree 是否平衡。
```cpp=
void st_insert(struct st_node **root,
struct st_node *p,
struct st_node *n,
enum st_dir d)
{
if (d == LEFT)
st_left(p) = n;
else
st_right(p) = n;
st_parent(n) = p;
st_update(root, n);
}
```
- `st_replace_right` : 在二元搜尋樹中刪除節點時需要選取子樹的一個節點做替換，這個函式是在替換節點為右子樹的情境下，實作以 `r` 節點替換 `n` 節點。
```cpp=
static inline void st_replace_right(struct st_node *n, struct st_node *r)
{
struct st_node *p = st_parent(n), *rp = st_parent(r);
if (st_left(rp) == r) {
st_left(rp) = st_right(r);
if (st_right(r))
st_rparent(r) = rp;
}
if (st_parent(rp) == n)
st_parent(rp) = r;
st_parent(r) = p;
st_left(r) = st_left(n);
if (st_right(n) != r) {
st_right(r) = st_right(n);
st_rparent(n) = r;
}
if (p && st_left(p) == n)
st_left(p) = r;
else if (p)
st_right(p) = r;
if (st_left(n))
st_lparent(n) = r;
}
```
- `st_remove` : 實作 s-tree 移除的函式。
- `AAAA` : 當被移除節點 `del` 存在右節點，尋找右子樹最小值替換以符合 BST 特性，而找到替換節點後還需要處理 node link 細節，因此填空答案應為 **st_replace_right(del, least)**。
- `BBBB` : 因為移除的節點是 `least`，所以應該更新原先 `least` 的 parent 才是最小的 cost，但因為 link 已經被刪去，所以次處應填 **st_update(root, st_right(least))** 或 **st_update(root, st_first(least))**。
- `CCCC` : 找到替換節點後還需要處理 node link 細節，因此填空答案應為 **st_replace_left(del, most)**。
- `DDDD` : 因為移除的節點是 `most`，所以應該更新原先 `most` 的 parent 才是最小的 cost，但因為 link 已經被刪去，所以次處應填 **st_update(root, st_left(most))** 或 **st_update(root, st_last(most))**。
- `EEEE` : n 節點為 leaf node 移除自己後，需要確保 s-tree 為平衡，因此要執行 **st_update(root, parent)**。
```cpp=
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;
AAAA;
BBBB;
return;
}
if (st_left(del)) {
struct st_node *most = st_last(st_left(del));
if (del == *root)
*root = most;
CCCC;
DDDD;
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;
EEEE;
}
```
### Test program
- `__treeint_dump` : 這裡要將 s-tree 中所有節點的大小依升序排列輸出至終端機，而二元樹的 in-order Traversal 正好能夠實現這個功能。因此 `FFFF` 為應先尋訪的 **st_left(n)**，而 `GGGG` 為最後尋訪的 **st_right(n)**。
```cpp=
/* ascending order */
static void __treeint_dump(struct st_node *n, int depth)
{
if (!n)
return;
__treeint_dump(st_left(n), depth + 1); // FFFF
struct treeint *v = treeint_entry(n);
printf("%d\n", v->value);
__treeint_dump(st_right(n), depth + 1); // GGGG
}
```
## 測驗 α - 2
## 測驗 β - 1 : 說明程式碼原理
- 這個函式計算記憶體對齊後應該分配的空間，將對齊大小分為 2 的冪和非 2 的冪，2 的冪可以透過位元運算降低計算的 cost。
- `(alignment & mask) == 0` 判斷當對齊大小為 2 的冪時計算，可以透過 `&` 將餘數清空，但因為計算後不能小於原本使用的 `sz` 大小，所以要先加上 `alignment - 1`，因此 `MMMM` 應該填 **(sz + mask)&(~mask)**。
```cpp=
#include <stdint.h>
static inline uintptr_t align_up(uintptr_t sz, size_t alignment)
{
uintptr_t mask = alignment - 1;
if ((alignment & mask) == 0) { /* power of two? */
return MMMM;
}
return (((sz + mask) / alignment) * alignment);
}
```
## 測驗 γ - 1 : 說明程式碼原理
下方包含 `qsort_mt` 和 `qsort_thread` 函式。
- 下方程式碼的 18 至 32 行為初始化 mutex 及創建 threads，並設置 `qs` 的 status 為 idle。
- `HHHH` : 建立多個 `qsort_thread` 的執行緒後，一開始會在狀態 idle 等待被觸發，因為 `qs->stat` 為多個執行緒共用的資料，因此更動時需要 mutex 機制保護。而如果要控制執行順序則需要透過 condvar 的機制，所以 `HHHH` 應為 **pthread_cond_wait(&qs->cond_st, &qs->mtx_st)** 等待 idle 狀態被修改後觸發 condvar。
- `JJJJ` : 下方程式碼的 116 至 119 行，因為修改了 `qs2` 的狀態因此需要透過 **pthread_cond_signal(&qs2->cond_st)** 通知。
```cpp=
/* The multithreaded qsort public interface */
void qsort_mt(void *a,
size_t n,
size_t es,
cmp_t *cmp,
int maxthreads,
int forkelem)
{
struct qsort *qs;
struct common c;
int i, islot;
bool bailout = true;
if (n < forkelem)
goto f1;
errno = 0;
/* Try to initialize the resources we need. */
if (pthread_mutex_init(&c.mtx_al, NULL) != 0)
goto f1;
if ((c.pool = calloc(maxthreads, sizeof(struct qsort))) == NULL)
goto f2;
for (islot = 0; islot < maxthreads; islot++) {
qs = &c.pool[islot];
if (pthread_mutex_init(&qs->mtx_st, NULL) != 0)
goto f3;
if (pthread_cond_init(&qs->cond_st, NULL) != 0) {
verify(pthread_mutex_destroy(&qs->mtx_st));
goto f3;
}
qs->st = ts_idle;
qs->common = &c;
if (pthread_create(&qs->id, NULL, qsort_thread, qs) != 0) {
verify(pthread_mutex_destroy(&qs->mtx_st));
verify(pthread_cond_destroy(&qs->cond_st));
goto f3;
}
}
/* All systems go. */
bailout = false;
/* Initialize common elements. */
c.swaptype = ((char *) a - (char *) 0) % sizeof(long) || es % sizeof(long)
? 2
: es == sizeof(long) ? 0
: 1;
c.es = es;
c.cmp = cmp;
c.forkelem = forkelem;
c.idlethreads = c.nthreads = maxthreads;
/* Hand out the first work batch. */
qs = &c.pool[0];
verify(pthread_mutex_lock(&qs->mtx_st));
qs->a = a;
qs->n = n;
qs->st = ts_work;
c.idlethreads--;
verify(pthread_cond_signal(&qs->cond_st));
verify(pthread_mutex_unlock(&qs->mtx_st));
/* Wait for all threads to finish, and free acquired resources. */
f3:
for (i = 0; i < islot; i++) {
qs = &c.pool[i];
if (bailout) {
verify(pthread_mutex_lock(&qs->mtx_st));
qs->st = ts_term;
verify(pthread_cond_signal(&qs->cond_st));
verify(pthread_mutex_unlock(&qs->mtx_st));
}
verify(pthread_join(qs->id, NULL));
verify(pthread_mutex_destroy(&qs->mtx_st));
verify(pthread_cond_destroy(&qs->cond_st));
}
free(c.pool);
f2:
verify(pthread_mutex_destroy(&c.mtx_al));
if (bailout) {
fprintf(stderr, "Resource initialization failed; bailing out.\n");
f1:
qsort(a, n, es, cmp);
}
}
/* Thread-callable quicksort. */
static void *qsort_thread(void *p)
{
struct qsort *qs, *qs2;
int i;
struct common *c;
qs = p;
c = qs->common;
again:
/* Wait for work to be allocated. */
verify(pthread_mutex_lock(&qs->mtx_st));
while (qs->st == ts_idle)
verify(HHHH);
verify(pthread_mutex_unlock(&qs->mtx_st));
if (qs->st == ts_term) {
return NULL;
}
assert(qs->st == ts_work);
qsort_algo(qs);
verify(pthread_mutex_lock(&c->mtx_al));
qs->st = ts_idle;
c->idlethreads++;
if (c->idlethreads == c->nthreads) {
for (i = 0; i < c->nthreads; i++) {
qs2 = &c->pool[i];
if (qs2 == qs)
continue;
verify(pthread_mutex_lock(&qs2->mtx_st));
qs2->st = ts_term;
verify(JJJJ);
verify(pthread_mutex_unlock(&qs2->mtx_st));
}
verify(pthread_mutex_unlock(&c->mtx_al));
return NULL;
}
verify(pthread_mutex_unlock(&c->mtx_al));
goto again;
}
```
Sign in with Wallet
Connect another wallet