HackMD
測驗α
α−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));
...
