2023 年暑期 Linux 核心課程第 1 次測驗/作業檢討

題目

2011eric

static inline void cond_wait(cond_t *cond, mutex_t *mutex)
{
    int seq = load(&cond->seq, relaxed);

    mutex_unlock(mutex);

#define COND_SPINS 128
    for (int i = 0; i < COND_SPINS; ++i) {
        if (load(&cond->seq, relaxed) != seq) {
            mutex_lock(mutex);
            return;
        }
        spin_hint(); /* 避免頻繁使用 atomics */
    }

    futex_wait(&cond->seq, seq);

    mutex_lock(mutex);

    fetch_or(&mutex->state, MUTEX_SLEEPING, relaxed);
}

RinHizakura

linux-summer-2023: hw1

重新定義 S-tree 提供的 public interface。

struct st_tree *st_create(cmp_t *cmp,
                          struct st_node *(*create_node)(void *key),
                          void (*destroy_node)(struct st_node *n));
void st_destroy(struct st_tree *tree);
int st_insert(struct st_tree *tree, void *key);
int st_remove(struct st_tree *tree, void *key);
struct st_node *st_find(struct st_tree *tree, void *key);

可在 st_create 中看到節點之間的 order 比較(cmp)、節點的建立與銷毀(create_node/destroy_node) 被從 S-tree 中獨立出來，以 callback function 的方式讓函式庫的使用者自行實作。其餘包含樹的走訪邏輯、root node 的維護等都直接在內部完成。

順帶一提，原本 treeint_insert 和 treeint_remove 中走訪 S-tree 的邏輯其實很相似。這裡我們實際上也可以重用 st_find 函式來歸納之，避免重寫相同的邏輯，以減少程式碼編譯後產生之二進位檔的大小。

完整的實作改進可以參照 s_tree.c。有了這項調整，未來就可以很輕易地將 S-tree 應用在其他合適的專案之中了!

雖然介面上變得簡單許多，不過其實如果對照 Linux 的 rbtree 實作，會發現其反而避免使用了使用 callback 的方式，作法比較接近本題原始的實作。

原因可參照原作者在 rbtree.h 中的註解說明:

To use rbtrees you'll have to implement your own insert and search cores. This will avoid us to use callbacks and to drop drammatically performances. I know it's not the cleaner way, but in C (not in C++) to get performances and genericity…

探討 S-tree 與 rbtree 效能落差

首先，為利於後續加入其他演算法進行效能評比，對原始程式碼做出以下改動，以建立相關基礎建設:

加入一個 macro benchmark，方便測量一段程式碼完成的時間

主要測量 insert/find/remove 三種操作的時間
撰寫一個簡單的 python script tree-perf.py，方便將測量結果視覺化

為了讓測量結果盡量不受 noise 干擾，且視覺化後的曲線圖可以更平滑，試著用簡單的標準差法排除蒐集到的時間中之 outlier
將 BST 的各項操作也抽象成 callback function pointer

雖然前面提到 callback 的方式可能會對函式呼叫整體造成額外成本，但這裡我們主要的目標是要比較不同 tree 的 throughput，而非注重單一 tree 本身在實際應用上的可能優化
因此取捨傾向先以能夠容易且快速的加入各種 BST 實作的設計方式為主

效能評比程式有了，那麼 rbtree 的函式庫該從何而來呢? 稍微搜尋了一下，一方面似乎沒有比較被大眾廣泛接受的紅黑樹相關 C 函式庫;一方面，S-tree 的實作和 Linux 中的 rbtree 介面上其實存在不少相似之處。因此我們乾脆將 Linux 的紅黑樹實作拉到 userspace 來應用。這裡參照 Linux 6.4 版本中的程式碼，並且只擷取與 insert/find/remove 三項操作相關的函式實作，具體整理出來的程式碼可以參考:

接著我們就可以來測量各個操作間的差異。

將實驗分為循序輸入和亂序輸入的場景。對於循序輸入的部份，我們將從 0 一直到 tree_size - 1 的 key 值插入到樹中，然後再以相同的次序進行搜尋和刪除。過程記錄不同的樹節點數量與完成相應操作所需之累積時間的關係。則實驗的結果如下圖:

循序狀況下，似乎在樹節點數量較少時兩者差異不大，而節點增加時，S-tree 相較於 rbtree 的表現更好?

而亂序輸入的場景下，我們會隨機產生任意的插入/搜尋/移除值，實驗結果如下:

從結果來看，亂序狀況下，S-tree 整體的效能看起來稍優於 rbtree。且在亂序情形下 rbtree 似乎更容易有 worst case (圖中極端值) 的出現。

該怎麼依此給出合理的解釋呢?

需注意到其實無論是插入/搜尋/刪除操作，其實三者都具備搜尋的部份，而插入和刪除只是多了調整節點間關係+旋轉的步驟
- 則如果瓶頸發生在搜尋部份，可以預期三種操作測量出的時間曲線圖將很相似(例如本實驗)?
對於亂序下出現特殊的極端值(圖中的尖峰)，可能是對某個 key 值的搜尋會導致最差情況(worst case)的發生?
- 不認為是硬體(CPU、Cache)干擾的原因在於三種操作在同一節點數量都出現極端值
理論上，在樹的平衡上 S-tree 應具有較為明顯的優勢，如下圖以循序插入 0 - 9 的節點為例，可見在限制樹高度的能力上 S-tree 是更有效的

注意退化的狀況，worst case 的討論

fourcolor

AVL tree 可以確保每個節點的左右子樹高相差不超過 1 ，因此每個節點需要儲存當前高度來計算 balance factor 來決定是否需要 rotate。
red-black tree 則藉由 1) 不能有兩個紅色node相連 2) 所有從該 node 走到其 subtree 下的 leaf 的上之黑色 node 數必定相同的規則來達到平衡。
S-Tree 的平衡機制與 AVL tree 較為相像利用 hint 來評估是否需要做 rotate ，然而 st_node 的 hint 的計算方式為其左右節點 hint 最大值 +1 並且只有在被呼叫到 st_update 時才會被更新。經過實驗觀察，發現 S-Tree 的 worst case 會是 O(n) 並且 worst case 的情形會發生在第一個 a 值極大，接著一串不大於 a 的遞增數列(反之亦然)

int a[] = {1000, 1, 2, 8, 16, 33, 73, 82, 83, 91, 95};
for (int i = 0; i < ARRAY_SIZE(a); i++) {
    treeint_insert(a[i]);
}
treeprint(st_root(tree), 0);

/* 簡單的圖示，無左右節點之分
1
∟———2
     ∟———8
          ∟———16
               ∟———33
                    ∟———73
                         ∟———82
                              ∟———83
                                   ∟———91
                                        ∟———1000
                                             ͱ———95
*/

我們假設目前的 S-Tree 已經有 1000, 1, 2, 8 插入，接著插入 16 來觀察

st_insert 前

st_update 前

對 16 做 st_update: 由於 16 沒有左右節點因此不會做任何動作，但是由於 16 的 hint 為 0 所以會對其親節 8 點做 update。
對 8 做 st_update: 由於 st_balance 為 1 因此不會做任何動作，但由於 8 的 hint 有經過更改 (0 -> 1) 所以會對其親節 1000 點做 update。
對 1000 做 st_update: 做完 rotate 後，由於 1000 的 hint 沒有改變 (1->1) 因此結束。

從上面會發現由於 hint 本身只要沒有改變且不等於 0 就不會往上 update ，代表 S-Tree 只要 update leaf 時發生 AVL 的 LR 或是 RL 就不會再往上 update 了

DrXiao

S-Tree 效仿 Linux 核心的 linked list，而定義了以下的結構體以及操作函式、巨集（此處僅列舉部份函式、巨集）

struct st_node {
    short hint;
    struct st_node *parent;
    struct st_node *left, *right;
};

struct st_root {
    struct st_node *root;
};

void st_insert(struct st_node **root, 
               struct st_node *p,
               struct st_node *n,
               enum st_dir d);
void st_remote(struct st_node **root,
               struct st_node *del);

可見 st_node 中，先撇除 hint 物件（會在後續說明用意），剩下的物件也都是指標，分別是指向父節點、左側子節點以及右側的子節點。參考 Linux 核心的 linked list 設計理念，不難推論 S-Tree 想達成以下示意圖的效果:

同樣參照 Linux 核心原始程式碼巨集: container_of ，可發現與 linked list 的效果有異曲同工之妙。S-Tree 同樣提供一內含數個指標的結構以及相關的操作函式，讓開發者引用 st_node、st_root 來自行定義二元搜尋樹所需的 struct，而涉及二元樹的插入新節點、刪除指定節點的操作，可利用 st_insert()、st_remove() 兩個函式，來完成增減節點的操作函式，而程式碼便不用再撰寫指標操作相關的部份，因為一切交由 st_insert() 和 st_remove() 來處理，讓每一節點中的 parent、left、right 物件，都可以指向應指向的節點。如此，開發者即可建立適當的 S-Tree。

StevenChen8759

align_up(120, 4) = 120
align_up(121, 4) = 124
align_up(122, 4) = 124
align_up(123, 4) = 124

推導為何 align 的計算
- 首先，我們令
  $s z = A * n + r$ ，其中
  $A \in Z^{+}, n \in N, r \in {0, 1, 2, . . ., A - 1}$
- 上列公式中，
  $A$ 為 alignment count，
  $n$ 與
  $r$ 為變動值，使 sz 可為任意 Size (包含 0)。
- 令 Function
  $a l i g n_u p (s z, A)$ 為求 alignment 的公式，並以上述的範例輸出觀察
  $a l i g n_{u} p$ 公式須具備的特性：
  - 120 恰可被 4 整除，此時
    $A = 4, n = 30, r = 0$ ，結果
    $120 = 4 * 30$
  - 121 除以 4 餘數 1，此時
    $A = 4, n = 30, r = 1$ ，結果
    $124 = 4 * 31$
  - 122 除以 4 餘數 2，此時
    $A = 4, n = 30, r = 2$ ，結果
    $124 = 4 * 31$
  - 123 除以 4 餘數 3，此時
    $A = 4, n = 30, r = 3$ ，結果
    $124 = 4 * 31$
  - 124 除以 4 餘數 0，此時
    $A = 4, n = 31, r = 0$ ，結果
    $124 = 4 * 31$
  - 125 除以 4 餘數 1，此時
    $A = 4, n = 31, r = 1$ ，結果
    $128 = 4 * 32$
- 綜上整理可觀察到當
  $r \in {1, 2, 3}$ 時，我們最後的輸出會變成
  $31 = 30 + 1$ ，考量上列特性，可得下列公式：
  - $a l i g n_u p (s z, A) = {\begin{cases} A * n, if r = 0 \\ A * (n + 1), if r \in {1, 2, . . ., A - 1} \end{cases}$
- 因上述公式適用除法原理，我們在此運用 ceiling function 取得 align up 的 size，可將上述公式改寫如下：
  - $a l i g n_u p (s z, A) = ⌈ s z / A ⌉ * A = ⌈ n + \frac{r}{A} ⌉ * A = (n + ⌈ \frac{r}{A} ⌉) * A$
- 考量除法運算的特性，以及後續 bitwise operation 的最佳化，我們改寫上述公式為取 floor function 的實作，此時須在
  $⌈ \frac{r}{A} ⌉$ 項的分子加上一常數
  $c$ ，改寫後如下所示：
  - $a l i g n_u p (s z, A) = (⌊ \frac{A * n + r + c}{A} ⌋) * A = (n + ⌊ \frac{r + c}{A} ⌋) * A$
- 接下來我們求常數
  $c$ 之值，還原至最初的
  $a l i g n_u p$ function 搭配兩式不同的條件，可得到下列聯立方程式 (推導過程省略)：
  - ${\begin{cases} ⌊ \frac{c}{A} ⌋ = 0, if r = 0 \\ ⌊ \frac{r + c}{A} ⌋ = 1, if r \in {1, 2, . . ., A - 1} \end{cases}$
- 根據 floor function 的特性，我們可得到下列聯立不等式：
  - ${\begin{cases} c \leq A - 1, if r = 0 \\ A \leq (r + c) \leq (2 * A - 1), if r \in {1, 2, . . ., A - 1} \end{cases}$
- 上列第二式的條件
  $r \in {1, 2, . . ., A - 1}$ 可再寫成不等式
  $1 \leq r \leq A - 1$ ，並拓展為
  $(1 + c) \leq (r + c) \leq (A - 1 + c)$ ，我們拆解這些條件，並考量上述 floor function 的特性重組成下列兩組聯立不等式：
  - ${\begin{cases} (r + c) \leq (A - 1 + c) \\ (r + c) \leq 2 * A - 1 \end{cases}$ ，相減得到
    $c \leq A$
  - ${\begin{cases} (r + c) \geq (1 + c) \\ (r + c) \geq A \end{cases}$ ，相減得到
    $c \geq A - 1$
- 總結所有常數
  $c$ 的不等式，聯立如下：最終
  $c = A - 1$
  - ${\begin{cases} c \leq A - 1 \\ c \leq A \\ c \geq A - 1 \end{cases}$ ，求得
    $c = A - 1$
- 我們現在求得最終的
  $a l i g n_u p (s z, A) = (⌊ \frac{s z + (A - 1)}{A} ⌋) * A$ ，對應至程式碼之實作即為 (((sz + mask) / alignment) * alignment)，其中 mask = alignment - 1。
當 alignment
$A$ 為 2 的冪時，我們令
$A = 2^{k}$ ，其中
$k$ 為正整數，此時公式變成
$a l i g n_u p (s z, 2^{k}) = (⌊ \frac{s z + (2^{k} - 1)}{2^{k}} ⌋) * 2^{k}$ ，因此我們可利用右移與左移實現乘以與除以
$2^{k}$ ，可得 (((sz + mask) >> alignment) << alignment)，其中 mask = alignment - 1，考量 pattern 中不可出現 alignment，可改寫成 (((sz + mask) >> (mask + 1)) << (mask + 1))。
但顯然上述的 pattern 看起來有些臃腫，我們再深入觀察二進位數值系統的特性，當我們對 size 除以 2^k 時，假設
$(s z + (2^{k} - 1)) = 2^{k} * n + r$ ，則其餘數
$r \in {0, 1, 2, . . ., 2^{k} - 1}$ ，因此餘數部分恰好可用 k bit 表示之，這部分恰為
$(s z + (2^{k} - 1))$ 的 last k bit，因此直接取 k + 1 以上的 bit 並右移 k bit 即為
$(⌊ \frac{(s z + (2^{k} - 1))}{2^{k}} ⌋)$ 的結果，但因最後還要再乘上
$2^{k}$ ，相當於再左移 k bit，恰好與前述的右移 k bit 互消，但考量 last k bit 必定為 0，因此需使用 bit mask 將 last k bit 設置為 0。
- 以 4 Byte alignment 為例，我們須設定 last 2 bit 為 0，因 mask 為 0x03，以 ~mask 做 and 操作即可完成設定，並保留 bit 3 以上的原始值。
- 最後的實作為 ((sz + mask) & ~mask)，其中 mask = alignment - 1

NOVBobLee

使用 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]);
         }