Concurrent Red-Black Tree

TODO: concurrent red-black tree

https://hackmd.io/@sysprog/concurrency 注意 lock-free

TODO: 將 Linux 核心的 rbtree 搬到 userspace

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

GitHub repo

TODO: 確保 rbtree 能夠在並行的環境運作 (locked vs. lock-free)

locked

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 下放置下一層的函數中。

insert

TODO: 評估 scalability

Reference

並行程式設計
mfrw/urb
Linux 核心的紅黑樹
Lock-Free Red-Black Trees Using CA