GitHub
2023 年暑期 Linux 核心課程第 1 次作業

測驗

$\alpha -1$

測驗

$\alpha -2$

1. adjust balance parameter [-1, 1] -> [-2, 2], etc.
   • Need to fix replace_right/replace_left
2. hint start w/1, not 0
3. add struct st_node **pparent to deal w/judgement of left/right child
4. add some members in struct node's padding (for what?)

測驗

$\alpha -3$

測驗

$\beta -1$

第一部份 (1.) align_up() 的定義。第二部份 (2, 3.) 通用式 (即第 9 行) 的原理。第三部分 (4, 5.) 為特殊情況 ( alignment 為二的冪) 下，針對運算進行最佳化。

#include <stdint.h>
/* alignment > 0 */
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);
}

1. align_up() 針對 sz 除以 alignment 所得到的餘數非零時，會有「無條件進位」到 alignment 倍數的動作；而當餘數為零時，則保持 sz 不變，以數學表示如下:

$\text{Given }s\in \mathbb{N}\cup \{0\},a\in \mathbb{N}$

$\text{Then, }\mathrm{\exists }!q_s,r_s\in \mathbb{N}\cup \{0\}\text{ s.t. }s=a{q}_s+r_s\text{, where }0\le r_s<a$

$\text{Case }{r}_s=0\text{: }\text{align\_up(s,a) gives }a\cdot q_s=s=s-r_s$

$\text{Case }{r}_s=1\text{: }\text{align\_up(s,a) gives }a\cdot (q_s+1)=(s-r_s)+a$

$⋮$

$\text{Case }{r}_s=a-1\text{: }\text{align\_up(s,a) gives }a\cdot (q_s+1)=(s-r_s)+a$

2. 電腦整數除法有下取整的效果，以數學表示為
   $\lfloor {\displaystyle \frac{s}{a}}\rfloor =q_s$ (
   $={\displaystyle \frac{s-r_s}{a}}$) ，小數點的部份就消去了。在給定 a 的情況下，
   $\lfloor {\displaystyle \frac{s}{a}}\rfloor \cdot a$ 與 align_up(s,a) 的圖形皆為離散的階梯函數樣子，此時將
   $\lfloor {\displaystyle \frac{s}{a}}\rfloor \cdot a$ 左移即可與 align_up(s,a) 疊合。

$\text{Find }k\in \mathbb{N}\cup \{0\}\text{ s.t. the every results from align\_up(s+k,a) in 1. don't change.}$

$\text{We have }s+k=(a{q}_s+r_s)+k=a{q}_{s+k}+r_{s+k}\text{, where }0\le r_{s+k}<a$

$\text{Case }{r}_s=0\text{: }s+k=(a{q}_s+0)+k=a{q}_s+k\text{, where }0\le k<a$

$\Rightarrow k\text{ could be }0,1,\dots ,(a-1)$

$\text{Case }{r}_s=1\text{: }s+k=(a{q}_s+1)+k=a(q_s+1)+(k-a+1)\text{, where }0\le (k-a+1)<a$

$\Rightarrow k\text{ could be }(a-1),a,\dots ,(2a-2)$

$⋮$

$\text{Case }{r}_s=a-1\text{: }s+k=(a{q}_s+(a-1))+k=a(q_s+1)+(k-1)\text{, where }0\le (k-1)<a$

$\Rightarrow k\text{ could be }1,2,\dots ,a$

$\text{There's only one }k\text{ matches in every cases}\Rightarrow k\text{ must be }a-1$

3. $\lfloor {\displaystyle \frac{s}{a}}\rfloor \cdot a$ 若要跟 align_up() 疊合，則必須左移
   $a-1$ (即變數 mask ) ，此時 align_up()
   $=\lfloor {\displaystyle \frac{s+m}{a}}\rfloor \cdot a$，得到通用式 (第 9 行)。
4. 從
   $\lfloor {\displaystyle \frac{s+m}{a}}\rfloor \cdot a=a{q}_{s+m}$ 的式子可以看出，就是把原本
   $s+m$ 中對於除數
   $a$ 的餘數
   $r_{s+m}$ 去除。此操作在
   $a$ 為二的冪情況下，跟電腦位元操作結合，有比通用式 (除法和乘法) 更快的運算方式。該方法即為第 7 行 (s + m) & ~m ，原意就是將
   $(s+m)$ 中對於除數
   $a$ 之餘數
   $r_{s+m}$ 去除，前提為
   $a$ 是二的冪。

$\text{(1) Unsigned 64-Bits Integer }(s+m)=\sum _{0\le d<64}{i}_d{2}^d,i_d=0,1$

$\text{(2) Remainders of divisor }{2}^n=\{\sum _{0\le d<n}{i}_d{2}^d|i_d=0,1\}$

$\text{(3) }m=(2^n-1)=(2-1)(2^{n-1}+2^{n-2}+\cdots +2^0)$

5. 由於現在電腦位元是二進位制的，每個整數可以用二的冪組合而成
   $(1)$ ，其係數就是記憶體上對應位置的位元。相同地，對於
   $2^n$ 的餘數也可以用此方式組合而成
   $(2)$ ，出現位置在上圖中黃色範圍內。觀察 m 的位元在記憶體上的樣子，剛好是整個黃色區域填滿 1
   $(3)$ ，此時用 ~ 運算，將 m 的位元反轉，搭配 & 運算，可以將白色區域內的位元保留，黃色區域內的位元歸零，此動作就是我們要的
   $(s+m)-r_{s+m}=a{q}_{s+m}=\lfloor {\displaystyle \frac{s+m}{a}}\rfloor \cdot a$ 。

測驗

$\beta -2$

測驗

$\gamma -1$

測驗

$\gamma -2$

• 使用 TSan(ThreadSanitizer) 編譯，在之後程式執行時可檢查 data race 的發生。

$ gcc -std=gnu11 -Wall -g -fsanitize=thread -o qsort_mt qsort_mt.c -lpthread

• 執行程式 (使用兩個執行緒)， TSan 警告有 data race 發生。

./qsort_mt -tv -f2 -h2 -n100
==================
WARNING: ThreadSanitizer: data race (pid=5885)
  Write of size 4 at 0x7b4000000080 by thread T1 (mutexes: write M0):
    #0 allocate_thread /home/zz4t/test/ttt/sysprog2023/quiz0/qsort_mt.c:211 (qsort_mt+0x31f3) (BuildId: 73768f1e290a7297a057e88a4b073661ed3575c4)
    #1 qsort_algo /home/zz4t/test/ttt/sysprog2023/quiz0/qsort_mt.c:314 (qsort_mt+0x3f0e) (BuildId: 73768f1e290a7297a057e88a4b073661ed3575c4)
    #2 qsort_thread /home/zz4t/test/ttt/sysprog2023/quiz0/qsort_mt.c:352 (qsort_mt+0x4328) (BuildId: 73768f1e290a7297a057e88a4b073661ed3575c4)

  Previous read of size 4 at 0x7b4000000080 by thread T2 (mutexes: write M1):
    #0 qsort_thread /home/zz4t/test/ttt/sysprog2023/quiz0/qsort_mt.c:343 (qsort_mt+0x423e) (BuildId: 73768f1e290a7297a057e88a4b073661ed3575c4)

  Location is heap block of size 256 at 0x7b4000000000 allocated by main thread:
    #0 calloc /usr/src/debug/gcc/gcc/libsanitizer/tsan/tsan_interceptors_posix.cpp:701 (libtsan.so.2+0x43413) (BuildId: 7e8fcb9ed0a63b98f2293e37c92ac955413efd9e)
    #1 qsort_mt /home/zz4t/test/ttt/sysprog2023/quiz0/qsort_mt.c:132 (qsort_mt+0x2677) (BuildId: 73768f1e290a7297a057e88a4b073661ed3575c4)
    #2 main /home/zz4t/test/ttt/sysprog2023/quiz0/qsort_mt.c:505 (qsort_mt+0x4d7d) (BuildId: 73768f1e290a7297a057e88a4b073661ed3575c4)

  Mutex M0 (0x7ffeb8a182d8) created at:
    #0 pthread_mutex_init /usr/src/debug/gcc/gcc/libsanitizer/tsan/tsan_interceptors_posix.cpp:1329 (libtsan.so.2+0x448c6) (BuildId: 7e8fcb9ed0a63b98f2293e37c92ac955413efd9e)
    #1 qsort_mt /home/zz4t/test/ttt/sysprog2023/quiz0/qsort_mt.c:130 (qsort_mt+0x265a) (BuildId: 73768f1e290a7297a057e88a4b073661ed3575c4)
    #2 main /home/zz4t/test/ttt/sysprog2023/quiz0/qsort_mt.c:505 (qsort_mt+0x4d7d) (BuildId: 73768f1e290a7297a057e88a4b073661ed3575c4)

  Mutex M1 (0x7b40000000a8) created at:
    #0 pthread_mutex_init /usr/src/debug/gcc/gcc/libsanitizer/tsan/tsan_interceptors_posix.cpp:1329 (libtsan.so.2+0x448c6) (BuildId: 7e8fcb9ed0a63b98f2293e37c92ac955413efd9e)
    #1 qsort_mt /home/zz4t/test/ttt/sysprog2023/quiz0/qsort_mt.c:136 (qsort_mt+0x26fd) (BuildId: 73768f1e290a7297a057e88a4b073661ed3575c4)
    #2 main /home/zz4t/test/ttt/sysprog2023/quiz0/qsort_mt.c:505 (qsort_mt+0x4d7d) (BuildId: 73768f1e290a7297a057e88a4b073661ed3575c4)

  Thread T1 (tid=5887, running) created by main thread at:
    #0 pthread_create /usr/src/debug/gcc/gcc/libsanitizer/tsan/tsan_interceptors_posix.cpp:1036 (libtsan.so.2+0x44219) (BuildId: 7e8fcb9ed0a63b98f2293e37c92ac955413efd9e)
    #1 qsort_mt /home/zz4t/test/ttt/sysprog2023/quiz0/qsort_mt.c:144 (qsort_mt+0x280c) (BuildId: 73768f1e290a7297a057e88a4b073661ed3575c4)
    #2 main /home/zz4t/test/ttt/sysprog2023/quiz0/qsort_mt.c:505 (qsort_mt+0x4d7d) (BuildId: 73768f1e290a7297a057e88a4b073661ed3575c4)

  Thread T2 (tid=5888, running) created by main thread at:
    #0 pthread_create /usr/src/debug/gcc/gcc/libsanitizer/tsan/tsan_interceptors_posix.cpp:1036 (libtsan.so.2+0x44219) (BuildId: 7e8fcb9ed0a63b98f2293e37c92ac955413efd9e)
    #1 qsort_mt /home/zz4t/test/ttt/sysprog2023/quiz0/qsort_mt.c:144 (qsort_mt+0x280c) (BuildId: 73768f1e290a7297a057e88a4b073661ed3575c4)
    #2 main /home/zz4t/test/ttt/sysprog2023/quiz0/qsort_mt.c:505 (qsort_mt+0x4d7d) (BuildId: 73768f1e290a7297a057e88a4b073661ed3575c4)

SUMMARY: ThreadSanitizer: data race /home/zz4t/test/ttt/sysprog2023/quiz0/qsort_mt.c:211 in allocate_thread
==================
0.0254 0.017 0.0102
ThreadSanitizer: reported 1 warnings

從訊息中可以得到 data race 發生的記憶體位置為 0x7b4000000000 ，在 qsort_mt.c:132 配置的 c.pool 之中。

    if ((c.pool = calloc(maxthreads, sizeof(struct qsort))) == NULL)

c.pool 為 struct qsort 組成之陣列，其中的成員 st 應該要被 mtx_st 所保護。

struct qsort {
    enum thread_state st;   /* For coordinating work. */
    struct common *common;  /* Common shared elements. */
    void *a;                /* Array base. */
    size_t n;               /* Number of elements. */
    pthread_t id;           /* Thread id. */
    pthread_mutex_t mtx_st; /* For signalling state change. */
    pthread_cond_t cond_st; /* For signalling state change. */
};

但在 qsort_mt.c:211 的位置進行 st 的寫入動作前，並未持有 mtx_st ，與 qsort_mt.c:343 位置的讀取動作有 data race 發生的可能。

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;                         /* st write */
            verify(pthread_mutex_lock(&c->pool[i].mtx_st));  /* mtx_st acquire */
            verify(pthread_mutex_unlock(&c->mtx_al));
            return (&c->pool[i]);
        }
    verify(pthread_mutex_unlock(&c->mtx_al));
    return (NULL);
}

    /* Wait for work to be allocated. */
    verify(pthread_mutex_lock(&qs->mtx_st));
    while (qs->st == ts_idle)                                /* st read */
        verify(pthread_cond_wait(&qs->cond_st, &qs->mtx_st));

修正很簡單，就是在 st 執行寫入動作前，先爭取到 mtx_st 即可。

--- a/quiz0/qsort_mt.c
+++ b/quiz0/qsort_mt.c
@@ -208,8 +208,8 @@ static struct qsort *allocate_thread(struct common *c)
     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]);
         }

測驗

$\gamma -3$