## 測驗 α − 1

## 測驗 β - 1

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);
}

當 `aligment` 為 2 的 n 次方時 `if ((alignment & mask) == 0)` 會成立，`sz + mask` 會得到大於 `alignment` 的數值，再將 `sz + mask` 跟 `~mask` 做 `&` 後即可將最低的 n - 1 bit 清零，達到 align_up 的效果

## 測驗 β - 2
[`linux/arch/s390/boot/startup.c`](https://github.com/torvalds/linux/blob/52a93d39b17dc7eb98b6aa3edb93943248e03b2f/arch/s390/boot/startup.c#L183) 的 `setup_kernel_memory_layout` 函式中使用相同的技巧來將 `pages` 向上對齊到 `PAGES_PER_SECTION`

#define SECTION_ALIGN_UP(pfn)	
    (((pfn) + PAGES_PER_SECTION - 1) & PAGE_SECTION_MASK)

pages = ident_map_size / PAGE_SIZE;
	/* vmemmap contains a multiple of PAGES_PER_SECTION struct pages */
	vmemmap_size = SECTION_ALIGN_UP(pages) * sizeof(struct page);

## 測驗 γ-1

### `qsort_mt`
初始化並建立執行緒來執行 `qsort_thread`

struct qsort *qs;
struct common c;

/* Try to initialize the resources we need. */
if (pthread_mutex_init(&c.mtx_al, NULL) != 0)
    goto f1;
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;
    }
}

### `qsort_thread`
若 `qs` 的狀態為 `ts_idle` 代表沒有任務需要處理，呼叫 `pthread_cond_wait` 等待，直到其他執行緒呼叫 `pthread_cond_signal`，被喚醒後解鎖防止 spurious wakeup 的 mutex，並執行 qsort

again:
/* 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));
if (qs->st == ts_term) {
    return NULL;
}
assert(qs->st == ts_work);

qsort_algo(qs);

在所有執行緒都為 idle 時，將所有的 thread 設為 terminate，並回傳，若沒有則繼續回到 `again` 等待新的工作

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(pthread_cond_signal(&qs2->cond_st));
        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;

## γ-2

執行 `$ clang qsort_mt.c -fsanitize=thread -fPIE -pie -g`

> SUMMARY: ThreadSanitizer: data race qsort_mt.c:211:27 in allocate_thread

原本實作為 `allocate_thread` 中第七行，將 `c->pool[i]` 的狀態改為 `ts_work` 再 lock 該執行緒的鎖

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));
            verify(pthread_mutex_unlock(&c->mtx_al));
            return (&c->pool[i]);
        }
    verify(pthread_mutex_unlock(&c->mtx_al));
    return (NULL);
}

但在更改 `c->pool[i]` 的狀態時，`qsort_thread` 中的 while loop 判斷中讀取到的狀態資訊可能會有 data race

static void *qsort_thread(void *p)
{
    ...
again:
    /* 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));
    ...
}

修改成取得鎖之後再修改執行緒的狀態

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--;
            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);
}