2023 Homework1

> [題目](https://hackmd.io/@sysprog/linux2023-summer-quiz0) ## 測驗 α − 1 S-Tree 是不完整的 AVL tree。以 insertion 為例，AVL tree 有 LL, RR, RL, LR 四個不平衡 case; 其中 LL, RR 需要 1 個 rotate 做 rebalance; RL, LR 需要 2 rotate 做 rebalance。 ![](https://hackmd.io/_uploads/HkkiZGmn2.png) > 林軒田教授公開的 [DSA 課程](https://www.csie.ntu.edu.tw/~htlin/course/dsa20spring/)筆記 S-Tree 只分左傾 (對應 AVL 的 LL, LR) 和右傾 (對應 AVL 的 LL, LR) 兩個不平衡 case, 都只用一個 rotate 處理 rebalance。所以 S-Tree 並不能處理 LR 和 RL 不平衡。以 LR 不平衡為例, S-Tree 經過 st_rotate_left 後, 只會轉為 RL 不平衡。 ``` st_rotate_left(<3>): 3 1 / \ 1 => 3 \ / 2 2 ``` 不過, S-Tree 還是有自平衡能力, 如再插入 2.5 為例, 產生新的 LR 不平衡, 經 st_rotate_left 後轉為 RL 不平衡; 然後再向上 update, 新的不平衡把之前的 RL 不平衡轉為 RR 不平衡, RR 不平衡可以由一個 rotate 轉為平衡。 ``` st_rotate_left(<3>) st_rotate_right(<1>) 1 1 2 \ \ / \ 3　　　=> 2 => 1 3 / \ / 2 3 2.5 \ / 2.5 2.5 ``` S-Tree 的自平衡能力用一次操作不太能看得出來。 ## 測驗 α − 2 在 remove 操作中, 當將要 remove 的 `del` 節點不是 leaf node 時, 需要進行 replace, 但是 `st_update` 不是從 leaf node 開始進行, 會使 st_right(least) 或 st_left(most) 子樹裡節點的 hint 不準確, 而影響後續操作的 rebalance。在 `st_remove` 中, 先紀錄 leaf node 的親代節點, 由此親代節點開始進行 `st_update`。 ```clike 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; struct st_node *p_least = st_parent(least); st_replace_right(del, least); //AAAA; st_update(root, p_least == del ? st_right(least) : p_least); //BBBB; return; } if (st_left(del)) { struct st_node *most = st_last(st_left(del)); if (del == *root) *root = most; struct st_node *p_most = st_parent(most); st_replace_left(del, most); //CCCC; st_update(root, p_most == del ? st_left(most) : p_most); //DDDD; return; } ``` ## 測驗 β − 1 當 `sz` 已經對齊時, `sz + mask` 會 set `sz` 後面的位元; `& ~mask` 會 clear 剛才被 set 的位元。當 `sz` 不對齊時, `sz + mask` 會使不對齊的地址進位, `& ~mask` 會 clear 進位的位元後面位元使其對齊。 ## 測驗 β − 2 在 bootlin 網站[搜尋 align_up](https://elixir.bootlin.com/linux/latest/A/ident/align_up), 找到其實作及用法: 實作 (kvm/include/test_util.h) ```c /* Aligns x up to the next multiple of size. Size must be a power of 2. */ static inline uint64_t align_up(uint64_t x, uint64_t size) { uint64_t mask = size - 1; TEST_ASSERT(size != 0 && !(size & (size - 1)), "size not a power of 2: %lu", size); return ((x + mask) & ~mask); } static inline uint64_t align_down(uint64_t x, uint64_t size) { uint64_t x_aligned_up = align_up(x, size); if (x == x_aligned_up) return x; else return x_aligned_up - size; } ``` ## 測驗 γ − 1 Quick sort 是一個 divide and conquer 的演算法, 可以采用 multithreading 方法做出平行運算的實作。實作中有一個 thread pool: ```clike=107 struct qsort *pool; /* Fixed pool of threads. ``` idle 的 thread 在等待工作: ```clike=341 /* Wait for work to be allocated. */ verify(pthread_mutex_lock(&qs->mtx_st)); while (qs->st == ts_idle) verify(pthread_cond_wait(&qs->cond_st, &qs->mtx_st)); verify(pthread_mutex_unlock(&qs->mtx_st)); ``` Quick sort 的 first run 會 signal 第一個 thread 進行第一次 divide and conquer: ```clike=164 /* 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)); ``` Quick sort 每一個 run 會 divide 出兩個集合, 當兩個集合的元素同時足夠多時, 會找一個 idle thread 排序左集合 (line 313), 右集合由原來的 thread 排序 (line 324) : ```clike=312 /* Now try to launch subthreads. */ if (nl > c->forkelem && nr > c->forkelem && (qs2 = allocate_thread(c)) != NULL) { qs2->a = a; qs2->n = nl; verify(pthread_cond_signal(&qs2->cond_st)); verify(pthread_mutex_unlock(&qs2->mtx_st)); } else if (nl > 0) { qs->a = a; qs->n = nl; qsort_algo(qs); } if (nr > 0) { a = pn - nr * es; n = nr; goto top; } ``` 當所有 thread 都 terminated 和 join 時, 即代表沒有需要排序的集合了, 完成排序。 ## 測驗 γ − 2 加入編譯參數如下 ```shell gcc -Wall -o qsort qsort-mt.c -lpthread -fsanitize=thread -g ``` 執行程式, 得得以下 WARNING: ```shall ================== WARNING: ThreadSanitizer: data race (pid=899) Write of size 4 at 0x7b4000000080 by thread T1 (mutexes: write M0): #0 allocate_thread /home/kachun/linux2023/qsort-mt/qsort-mt.c:211 (qsort+0x3448) #1 qsort_algo /home/kachun/linux2023/qsort-mt/qsort-mt.c:314 (qsort+0x415b) #2 qsort_thread /home/kachun/linux2023/qsort-mt/qsort-mt.c:351 (qsort+0x4565) #3 <null> <null> (libtsan.so.0+0x2d1af) Previous read of size 4 at 0x7b4000000080 by thread T2 (mutexes: write M2): #0 qsort_thread /home/kachun/linux2023/qsort-mt/qsort-mt.c:343 (qsort+0x4487) #1 <null> <null> (libtsan.so.0+0x2d1af) Location is heap block of size 256 at 0x7b4000000000 allocated by main thread: #0 calloc <null> (libtsan.so.0+0x305ca) #1 qsort_mt /home/kachun/linux2023/qsort-mt/qsort-mt.c:132 (qsort+0x28fb) #2 main /home/kachun/linux2023/qsort-mt/qsort-mt.c:503 (qsort+0x4f7f) Mutex M0 (0x7ffc43b47368) created at: #0 pthread_mutex_init <null> (libtsan.so.0+0x4a636) #1 qsort_mt /home/kachun/linux2023/qsort-mt/qsort-mt.c:130 (qsort+0x28de) #2 main /home/kachun/linux2023/qsort-mt/qsort-mt.c:503 (qsort+0x4f7f) Mutex M2 (0x7b40000000a8) created at: #0 pthread_mutex_init <null> (libtsan.so.0+0x4a636) #1 qsort_mt /home/kachun/linux2023/qsort-mt/qsort-mt.c:136 (qsort+0x2981) #2 main /home/kachun/linux2023/qsort-mt/qsort-mt.c:503 (qsort+0x4f7f) Thread T1 (tid=901, running) created by main thread at: #0 pthread_create <null> (libtsan.so.0+0x5ea99) #1 qsort_mt /home/kachun/linux2023/qsort-mt/qsort-mt.c:144 (qsort+0x2a86) #2 main /home/kachun/linux2023/qsort-mt/qsort-mt.c:503 (qsort+0x4f7f) Thread T2 (tid=902, running) created by main thread at: #0 pthread_create <null> (libtsan.so.0+0x5ea99) #1 qsort_mt /home/kachun/linux2023/qsort-mt/qsort-mt.c:144 (qsort+0x2a86) #2 main /home/kachun/linux2023/qsort-mt/qsort-mt.c:503 (qsort+0x4f7f) SUMMARY: ThreadSanitizer: data race /home/kachun/linux2023/qsort-mt/qsort-mt.c:211 in allocate_thread ================== ThreadSanitizer: reported 1 warnings ``` 由 ThreadSanitizer 檢測出來第 211 行程式碼產生 data race, 修正如下: ```c=205 static struct qsort *allocate_thread(struct common *c) { verify(pthread_mutex_lock(&c->mtx_al)); for (int i = 0; i < c->nthreads; i++) if (c->pool[i].st == ts_idle) { c->idlethreads--; /* c->pool[i].st = ts_work; */ verify(pthread_mutex_lock(&c->pool[i].mtx_st)); c->pool[i].st = ts_work; verify(pthread_mutex_unlock(&c->mtx_al)); return (&c->pool[i]); } verify(pthread_mutex_unlock(&c->mtx_al)); return (NULL); } ```