# Linux 核心專題: 並行的紅黑樹實作
> 執行人: MiohitoKiri5474
> [專題解說影片](?)

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

## TODO: 將 Linux 核心的 rbtree 搬到 userspace
> 將需要用到的標頭檔複製出來，並另行定義所需要的額外巨集，確保程式碼可在使用者空間運作。

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

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

## 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](https://github.com/MiohitoKiri5474/userspace_rbtree/commit/ad37b1b3fe8c30c71db3048a86015a434c5596b1#diff-a14ad0b49b120e1729b2c5af9bd19704af07cdb3b79aeca11cdc33e70fd04400)

## TODO: 確保 rbtree 能夠在並行的環境運作: lock-free
> 並行的紅黑樹，lock-free 實作

## TODO: 探討 scalability
> 比照[並行程式設計: Lock-Free Programming](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-lockfree)，探討 lock-based 和 lock-free 的 scalability，分析二者效能表現並解讀。