Linux 核心專題: 並行的紅黑樹實作

執行人: MiohitoKiri5474
專題解說影片

任務簡介

延續課程教材，建構並行的紅黑樹實作，確保可達到 lock-free，需驗證其正確性和效率。

TODO: 將 Linux 核心的 rbtree 搬到 userspace

將需要用到的標頭檔複製出來，並另行定義所需要的額外巨集，確保程式碼可在使用者空間運作。

將需要用到的標頭檔複製出來，並且將所需要的額外巨集另外定義。
已撰寫程式確認可運行於使用者空間。

GitHub repo

TODO: 確保 rbtree 能夠在並行的環境運作: lock-based

並行的紅黑樹，lock-based 實作

static function

之前比較少接觸 static function，故遇到一些問題，例如以下程式碼：

static __always_inline struct rb_node *rb_find(
    const void *key,
    const struct rb_root *tree,
    int (*cmp)(const void *key, const struct rb_node *))
{
    struct rb_node *node = tree->rb_node;

    while (node) {
        int c = cmp(key, node);
        ptlock_t *parent_lock = node -> lock;
        LOCK(parent_lock);

        if (c < 0)
            node = node->rb_left;
        else if (c > 0)
            node = node->rb_right;
        else {
            UNLOCK(parent_lock);
            return node;
        }
        UNLOCK(parent_lock);
    }

    return NULL;
}

原先預期是只有在 while 迴圈內會將節點鎖定，等到目前節點處理完畢後便直接解除鎖定，因為 node 指向的記憶體位置會不斷改變，為了正確的將節點解鎖，額外使用變數 parent_lock 紀錄父節點的 lock，但在編譯時期出現以下錯誤：

rbtree.h:276:19: error: unused variable ‘parent_lock’ [-Werror=unused-variable]
  276 |         ptlock_t *parent_lock = node -> lock;
      |                   ^~~~~~~~~~~

後來改成以下形式規避此編譯警告：

    struct rb_node *node = tree->rb_node;
+   ptlock_t *current_lock = NULL;

    while (node) {
        int c = cmp(key, node);
        ptlock_t *parent_lock = node -> lock;

        LOCK(parent_lock);

+       if (current_lock)
+           UNLOCK(current_lock);

        if (c < 0)
            node = node->rb_left;
        else if (c > 0)
            node = node->rb_right;
        else {
            UNLOCK(parent_lock);
            return node;
        }
-       UNLOCK(parent_lock);
+       current_lock = parent_lock;
    }
+   if (current_lock)
+       UNLOCK(current_lock);

Lock 位置

最一開始嘗試很粗暴的在所有操作前加上 LOCK、並在操作結束後 UNLOCK，但在後續的測試中發現程式很常會在一些地方卡住。
後來發現是重複對於同一個節點做 LOCK，導致某些情況下程式會卡住，後來改為 top down 的方式新增 LOCK。

這邊的 top down 是指，先從每個大操作（如 rb_insert, rb_erase）開始時將整顆紅黑樹 LOCK 起來，等到整個操作都處理完畢時再 UNLOCK。
等確認此操作無其他執行上的問題時，再將這些大操作的 LOCK/UNLOCK 下放置下一層的函數中。

但即便如此，還是需要大量的時間確認及驗證 lock 是否正確，以及哪些地方是否需要加上 LOCK/UNLOCK。

insert 和 query 算是比較容易的，query 只要在搜尋時將查詢到的當前子樹 LOCK，等往下轉移節點時再將祖先 UNLOCK；insert 在尋找插入位置時也和 query 類似，找到位置之後我是將整個子樹都鎖定，這樣在 rebalance 的時候即便動到結構也不會影響到其他部分。
但在處理 erase 時則變的很麻煩，erase 操作不像是 insert/query 只會動到原先的位置，而是要連同移除節點的父節點一併鎖定，這使得操作上有些麻煩。

最後選擇和 insert/query 類似的方式，自行使用二分搜找到欲刪除位置，但同時把欲刪除節點位置的父節點一同鎖定，後面再交給 Linux Kernel 的函數處理。

但這樣的作法其實比較算是在 userspace 層面做 LOCK，而且沒有隨著 reblance 進度 UNLOCK，整體效能比較差。

GitHub Commit

TODO: 確保 rbtree 能夠在並行的環境運作: lock-free

並行的紅黑樹，lock-free 實作

TODO: 探討 scalability

比照並行程式設計: Lock-Free Programming，探討 lock-based 和 lock-free 的 scalability，分析二者效能表現並解讀。