測驗α

α−1 運作原理

根據註解表示：
在刪除節點時，如果要刪除的節點有右子節點，則刪除過程涉及將要刪除的節點替換為右子樹中遇到的第一個節點(249 ~ 254行)。在這個替換之後，會對新插入節點的右子節點進行更新操作(255行)。

同樣地，如果要刪除的節點沒有右子節點，替換過程涉及利用左子樹中找到的第一個節點。隨後，會對替換節點的左子節點進行更新操作。

在要刪除的節點既沒有左子節點也沒有右子節點的情況下，可以直接從樹中刪除該節點，並對被刪除節點的父節點進行更新操作(282行)。

248 void st_remove(struct st_node **root, struct st_node *del) {
249   if (st_right(del)) {
250     struct st_node *least = st_first(st_right(del));
251     if (del == *root)
252       *root = least;
253 
254     st_replace_right(del, least);       // AAAA
255     st_update(root, st_right(least));   // BBBB
256     return;
257   }
258 
259   if (st_left(del)) {
260     struct st_node *most = st_last(st_left(del));
261     if (del == *root)
262       *root = most;
263 
264     st_replace_left(del, most);         // CCCC;
265     st_update(root, st_left(most));     // DDDD;
266     return;
267   }
268 
269   if (del == *root) {
270     *root = 0;
271     return;
272   }
273 
274   /* empty node */
275   struct st_node *parent = st_parent(del);
276 
277   if (st_left(parent) == del)
278     st_left(parent) = 0;
279   else
280     st_right(parent) = 0;
281 
282   st_update(root, parent);              // EEEE;
283 }

α−2 改進之處

特別跟 AVL tree 和 red-black tree 相比
實作:

α−3

設計效能評比程式，探討上述程式碼和 red-black tree 效能落差

---

測驗β

β-1 運作原理

#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 (sz + mask) & ~mask;       
    }
    return (((sz + mask) / alignment) * alignment);
}

第6行先判斷變數 alignment 是不是2的冪，判斷方式是透過將 alignment 與 mask = alignment - 1 做 bitwise and 運算，如果 alignment 是2的冪寫成二進制表達式時只會有一個 bit 是1 (假設第i個 bit 為1)剩餘的 bits 都是0，並且 mask 會變成0 ~ i-1 bits 都是1其餘的 bits 是0的狀況，所以兩者做 bitwise and 就會變成0如此就可以判斷是不是2的幂。

第7行透過剛剛計算出的 ~mask 代表0 ~ i-1 bits 都是0其餘的 bits 是1，所以當 sz + mask 與 ~mask 做 bitwise and 相當於把0 ~ i-1 bits 清成0，這就可以達到對齊的效果了。另外 sz + mask 的原因在於輸出要求大於等於 alignment 的記憶體對齊地址，如果要求變成小於等於的話則不需要另外加 mask。

之所以要分 alignment 是不是2的冪是因為除法跟乘法需要的時間遠遠大於 bitwise 操作所需的時間，所以為了讓 align_up 更有效率才會分開來計算，並且在 kernel 中大部分 alignment 都是2的冪所以這個方法可以有效加速。

β-2 Linux核心原始程式碼及用法:

巨集:
__ALIGN_KERNEL_MASK(x, mask)
舉例說明:
在linux/mm/cma.c#L278中，kernel 需要計算出使用者要保留CMA的 base address 以及 size，並且這兩個值都必需是 alignment，就使用巨集ALIGN(x, a)來達成此目的。

---

測驗γ

γ-1 運作原理

333 /* Thread-callable quicksort. */
334 static void *qsort_thread(void *p)
335 {
336     struct qsort *qs, *qs2;
337     int i;
338     struct common *c;
339 
340     qs = p;
341     c = qs->common;
342 again:
343     /* Wait for work to be allocated. */
344     verify(pthread_mutex_lock(&qs->mtx_st));
345     while (qs->st == ts_idle)
346         verify(pthread_cond_wait(&qs->cond_st, &qs->mtx_st));               // HHHH
347     verify(pthread_mutex_unlock(&qs->mtx_st));
348     if (qs->st == ts_term) {
349         return NULL;
350     }
351     assert(qs->st == ts_work);
352 
353     qsort_algo(qs);
354 
355     verify(pthread_mutex_lock(&c->mtx_al));
356     qs->st = ts_idle;
357     c->idlethreads++;
358     if (c->idlethreads == c->nthreads) {
359         for (i = 0; i < c->nthreads; i++) {
360             qs2 = &c->pool[i];
361             if (qs2 == qs)
362                 continue;
363             verify(pthread_mutex_lock(&qs2->mtx_st));
364             qs2->st = ts_term;
365             verify(pthread_cond_signal(&qs2->cond_st));           // JJJJ
366             verify(pthread_mutex_unlock(&qs2->mtx_st));
367         }
368         verify(pthread_mutex_unlock(&c->mtx_al));
369         return NULL;
370     }
371     verify(pthread_mutex_unlock(&c->mtx_al));
372     goto again;
373 }

γ-2 找出data race並著手修正

在編譯參數中加入-fsanitize=thread 即可開啟 Thread Sanitizer，編譯後執行會出現以下警告：

從上圖 Write of size 那行可以看出 data race 出現在213行，並且從圖中 Previous read 那行指出345行正在讀取共同變數。這樣看來問題就很明顯了那主要是 pool 中用來表示 thread 狀態的 st 變數有 data race。

要解決這個問題只需要將213行跟214行對調即可，透過先 lock mtx_st 確保原本213行在改變狀態時345行無法去讀取(344行有lock)。

207 static struct qsort *allocate_thread(struct common *c)
208 {
209     verify(pthread_mutex_lock(&c->mtx_al));
210     for (int i = 0; i < c->nthreads; i++)
211         if (c->pool[i].st == ts_idle) {
212             c->idlethreads--;
213             c->pool[i].st = ts_work;
214             verify(pthread_mutex_lock(&c->pool[i].mtx_st));
215             verify(pthread_mutex_unlock(&c->mtx_al));
216             return (&c->pool[i]);
217         }
218     verify(pthread_mutex_unlock(&c->mtx_al));
219     return (NULL);
220 }
...
342 again:
343     /* Wait for work to be allocated. */
344     verify(pthread_mutex_lock(&qs->mtx_st));
345     while (qs->st == ts_idle)
346         verify(pthread_cond_wait(&qs->cond_st, &qs->mtx_st));// HHHH
347     verify(pthread_mutex_unlock(&qs->mtx_st));
...

γ-3 改進與實作