# 2024q1 Homework5 (assessment)
contributed by < `MiohitoKiri5474` >

## 測驗題改進與提問
> 從前 4 週的測驗題選出 3 題改進 (含延伸問題，要有對應的 Linux 核心原始程式碼案例探討)，觀摩其他學員並參照授課教師進行的作業檢討和回顧，若有不能理解的部分，請標註出來。善用 HackMD 的語法 :::info 和 ::: 標註你的提問，在原有的筆記頁面更新即可。

## 閱讀〈因為自動飲料機而延畢的那一年〉
> 紀錄閱讀〈因為自動飲料機而延畢的那一年〉的啟發，特別在學習本課程 5 週之後的感想，應具體描述你在課堂、課後創作，和觀摩其他學員的成果時，理解到系統軟體的開發態度、對細節的重視，以及理論和實務的融會貫通。

## 研讀第 1 到第 6 週「課程教材」和 CS:APP 3/e
> 研讀第 1 到第 6 週「課程教材」和 CS:APP 3/e (至少到第二章)，紀錄心得和提問。針對自訂題目，例如貢獻程式碼到 Linux 核心，也將自己的構想和規劃記錄下來，隨後與授課教師一對一討論時可運用。

## 簡述想投入的專案
> 參照 [2023 年期末專題](https://hackmd.io/@sysprog/linux2023-projects)，簡述你想投入的專案 (亦可建立新專案)，至少選出 (或訂出) 二個。

1. 高效網頁伺服器
2. 紅黑樹實作改進

---

int max(int x, int y)
{
    // no branch; no ? operator
    long long mask = ((y - x) >> 31) & 1;
    return (((mask << 32) - mask) & y) +
           ((((1 - mask) << 32) - (1 - mask)) & x);
}

:::warning
TODO:
* 避免使用乘法運算子
* 探討實作的限制，即 x 和 y 的有效條件
:::

max ( 3, -5 )
mask = 3 - ( -5 ) = 8
mask = $0000000000000000000000000000100_{2}$
mask >> 31 = 0

TODO: 如何處理 max(INT_MIN, INT_MAX) ?

int count_bits(unsigned x)
{
    // population count
    int cnt = 0;
    while (x) {
        if (x & 1)
            cnt++;
        x >>= 1;
    }
    return cnt;
}

TODO: branchless 的 popcount

int count_bits(unsigned x)
{
    // population count
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = (x + (x >> 8)) & 0x00FF00FF;
    x = (x + (x >> 16)) & 0x0000FFFF;
    return x;
}

> 0x55 => 0101 0101
> 0x33 => 0011 0011
> 0x0F => 0000 1111

# 專題

專題連結 [https://hackmd.io/@MiohitoKiri5474/Hy52_dWIA]

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

但即便如此，還是需要大量的時間確認及驗證 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: 評估 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)