測驗 α − 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 的 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);
}