# Concurrent Red-Black Tree

## TODO: concurrent red-black tree
> https://hackmd.io/@sysprog/concurrency 注意 lock-free

## TODO: 將 Linux 核心的 rbtree 搬到 userspace

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

[GitHub repo](https://github.com/MiohitoKiri5474/userspace_rbtree)

## 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

[並行程式設計](https://hackmd.io/@sysprog/concurrency/)
[mfrw/urb](https://github.com/mfrw/urb)
[Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree)
[Lock-Free Red-Black Trees Using CA](https://www.liblfds.org/downloads/white%20papers/%5BRed-Black%20Tree%5D%20-%20%5BKim,%20Cameron,%20Graham%5D%20-%20Lock%20Free%20Red%20Black%20Trees%20Using%20CAS.pdf)