# 2021q3 Homework2 (hp)
contributed by < `KiwiWang` >

## 1. 解釋程式碼運作原理

### Alignment
`struct list_hp` 的實作除了 [Hazard Pointer paper](https://erdani.org/publications/cuj-2004-12.pdf) 描述的內容以外，還多了一些alignment的關鍵字，例如 `CLPAD` , `alignas` 等等。

從功能性上看不出這些 alignment 的必要。更改 alignment 為 8-bytes後程式仍然正常。

因此推測是為了避免 atomic operation 對cache造成太大影響而使用 128-bytes alignment (常見的 cache line size 為32, 64, 128 bytes)

`CLPAD` 應是 CacheLine PAD 的意思。

#define ALIGN_BYTES 128
#define ALLOC(x) aligned_alloc(ALIGN_BYTES, x)
#define ALIGN alignas(ALIGN_BYTES)

struct list_hp {
    int max_hps;
    
    // array of pointers to aligned atomic_uintptr_t?
    // 即 hp[i][j] 皆為 128 的倍數
    ALIGN atomic_uintptr_t *hp[HP_MAX_THREADS];
    
    // 這個比較有趣
    // array of pointers to aligned retirelist_t
    // 然而 rl[0] 和 rl[CLPAD] 相隔 128 bytes
    // 使用上也是以隔CLPAD使用，如rl[i*CLPAD]
    // 考慮到不同 thread 可能執行在不同 CPU core 上
    // 因此以CLPAD讓 thread 間存取 rl[] 時
    // 不會互相干擾 cache line.
    ALIGN retirelist_t *rl[HP_MAX_THREADS * CLPAD];
    list_hp_deletefunc_t *deletefunc;
};

另外，這次實作上每個thread有3個 Hazard Pointer 的位置 ( `max_hps = 3` )

### List

在 `__list_find` 中會進行多次 Hazard Pointer的 Acquire ，只是 paper 中是 `do{}while()` 而 `__list_find` 是 `goto try_again`

因為 Link-List 的操作牽涉的 pointer 最多三個，而且和 paper 描述不同的是，這裡沒有創建全新的 link-list 並 swap，而是只保護 `prev`, `curr`, `next` 三個 node，可以有複數 writer 操作在同一個 link-list 的不同區段。

其中特別值得一提的是 `prev` ，在此次實作中變數名稱為 `prev` 的型態皆為 `atomic_uintptr_t*` ，原因是它並非真正的 `prev_node` ，而是 `&(prev_node->next)` 或 `&curr` 。

與[此連結](https://www.ted.com/talks/linus_torvalds_the_mind_behind_linux)的14:10處概念相似。

另外則是非常讓人困惑的 `mark`, `unmark`

#define is_marked(p) (bool) ((uintptr_t)(p) &0x01)
#define get_marked(p) ((uintptr_t)(p) | (0x01))
#define get_unmarked(p) ((uintptr_t)(p) & (~0x01))

#define get_marked_node(p) ((list_node_t *) get_marked(p))
#define get_unmarked_node(p) ((list_node_t *) get_unmarked(p))

~~目前懷疑目的之一是為了避免 double free~~

研讀 [A Pragmatic Implementation of Non-Blo cking Linked-Lists](https://www.cl.cam.ac.uk/research/srg/netos/papers/2001-caslists.pdf)

以下為該篇論文的節錄。

#### 以CAS實作non-blocking list 的問題

List insert 的時候可以用一個 CAS 順利完成。如下：
##### 1. 創建想 insert 的 node ，假設為 node 20

##### 2. 以 CAS 執行紅色箭頭的置換即可
(即使有許多 thread 同時進行 insert ，也只有一個 CAS 會成功，可保證 List 在任何時刻皆為有效狀態且不會有 node 憑空消失或重複 insert)

然而， Delete node 無法用一個 CAS 便完成。比如：

##### 1. 假設我們想刪除下圖的 node 10 ，以 CAS 執行紅色箭頭

##### 2. 若同時有 node insert 則新的 node 也會被刪除。如下圖 node 20
(insert thread 已紀錄 node 10且將 node 10當成 curr_node ，執行 node 20 insertion)

##### 最終 list 會變成

(從 Head 開始 traverse，只會接著看到 node 30，node 10以及20已經和 list 斷開了)

[論文](https://www.cl.cam.ac.uk/research/srg/netos/papers/2001-caslists.pdf)為此提出以兩個 CAS 來完成 node deletion 的做法。

其步驟為：
1. 第一個 CAS 將 deleted node 的 next 標記
2. 第二個 CAS 將被標記的 node 移除(或稱 unlink)

第一個步驟稱為 logically deleted，第二個步驟則是 physically deleted。

可以將 logically deleted state 想像成預告，讓同時正在 insert 或 delete 的 thread 認知到該 node 已經要被刪除了，不要再使用它或者根據它的值進行運算。如果保存有該 node 的 reference ，則進行 retry。

#### 正確性
論文對於 search function 有以下假設：
1. `left_node.key < search.key <= right_node.key`

2. `right_node` 是 `left_node` 的 immediate successor
3. `left_node` 和 `right_node` 都必須為 unmarked

要注意的是作業二的實作為
[A more Pragmatic Implementation of the Lock-free, Ordered, Linked List](https://arxiv.org/abs/2010.15755)
因此 `__list_find` 和這裡的 search function不盡相同。然而，仍然可以看出 `prev` 為 `left_node` 而 `curr` 為 `right_node`

參考程式碼為[老師的 repo 及同學們的修正](https://github.com/sysprog21/concurrent-programs/blob/master/hp_list/main.c)。下方標記 `// 條件` 為對應上述條件 1, 2, 3 的程式碼。

static bool __list_find(list_t *list,
                        list_key_t *key,
                        atomic_uintptr_t **par_prev,
                        list_node_t **par_curr,
                        list_node_t **par_next)
{
    atomic_uintptr_t *prev = NULL;
    list_node_t *curr = NULL, *next = NULL;

try_again:
    prev = &list->head;
    curr = (list_node_t *) ATOMIC_LOAD(prev);
    (void) list_hp_protect_ptr(list->hp, HP_CURR, (uintptr_t) curr);
    // 條件2, curr 為 prev 的 immediate successor
    // 條件3, prev 為 unmarked
    if (ATOMIC_LOAD(prev) != get_unmarked(curr)) {
        TRACE(retry);
        goto try_again;
    }
    while (true) {
        if (is_marked(curr))
            TRACE(contains);
        next = (list_node_t *) ATOMIC_LOAD(&get_unmarked_node(curr)->next);
        (void) list_hp_protect_ptr(list->hp, HP_NEXT, get_unmarked(next));

        if (ATOMIC_LOAD(&get_unmarked_node(curr)->next) != (uintptr_t) next) {
            TRACE(retry);
            goto try_again;
        }
        
        // 條件2, curr 為 prev 的 immediate successor
        // 條件3, prev 為 unmarked
        if (ATOMIC_LOAD(prev) != get_unmarked(curr)) {
            TRACE(retry);
            goto try_again;
        }
        // 條件3, curr 為 unmarked
        if (get_unmarked_node(next) == next) {
            // 條件1, left_node.key < search.key <= right_node.key
            if (!(get_unmarked_node(curr)->key < *key)) {
                *par_curr = curr;
                *par_prev = prev;
                *par_next = next;
                return (get_unmarked_node(curr)->key == *key);
            }
            prev = &get_unmarked_node(curr)->next;
            (void) list_hp_protect_release(list->hp, HP_PREV,
                                           get_unmarked(curr));
        } else {
            // 移除 marked curr
            uintptr_t tmp = get_unmarked(curr);
            if (!CAS(prev, &tmp, get_unmarked(next))) {
                TRACE(retry);
                goto try_again;
            }
            list_hp_retire(list->hp, get_unmarked(curr));
        }
        curr = next;
        (void) list_hp_protect_release(list->hp, HP_CURR, get_unmarked(next));
        TRACE(traversal);
    }
}

因此，在 `__list_find` return 的瞬間，我們可以假設條件 1, 2, 3 皆成立。

接著再仔細研究 `__list_insert` 和 `__list_delete`，觀察它們如何再次確認條件1, 2, 3：

先看較單純的 `__list_insert` ，它只需確認 `prev` 為 unmarked node。

bool list_insert(list_t *list, list_key_t key)
{
    list_node_t *curr = NULL, *next = NULL;
    atomic_uintptr_t *prev = NULL;

    list_node_t *node = list_node_new(key);

    while (true) {
        if (__list_find(list, &key, &prev, &curr, &next)) {
            list_node_destroy(node);
            list_hp_clear(list->hp);
            return false;
        }
        ATOMIC_STORE_EXPLICIT(&node->next, (uintptr_t) curr,
                              memory_order_relaxed);
        uintptr_t tmp = get_unmarked(curr);
        if (CAS(prev, &tmp, (uintptr_t) node)) {
            list_hp_clear(list->hp);
            return true;
        }
        TRACE(ins);
    }
}

即使 `curr` 在 `__list_find` return 後馬上被 marked 了也不要緊，場景順序大約如下：

##### 1. search結束後，insert 發生時，node 30 已被 mark

##### 2. `__list_insert` 的 CAS 確認到 node 10 的 next 依然為 unmarked 且指向 node 30後，執行 Swap

可以看到上述1及2的 List 皆為有效狀態。我們可以發現在2的CAS執行後的 `__list_find` 相對單純，只是一個普通的 search 搭配移除 marked node 而已。

因此我們考慮另一個較為極限的場景，假設在 `__list_insert` 的 CAS 執行前一瞬間，有某個 thread 的 `__list_find` 已執行到了下方這個 block ，正打算利用 CAS 移除(unlink) node 30

// 條件3, curr 為 unmarked
if (get_unmarked_node(next) == next) {
    // ...
} else {
    // 移除 marked curr
    uintptr_t tmp = get_unmarked(curr);
    // unlink
    if (!CAS(prev, &tmp, get_unmarked(next))) {
        TRACE(retry);
        goto try_again;
    }
    list_hp_retire(list->hp, get_unmarked(curr));
}

此時場景如圖：

可以看到 Thread A 和 Thread B 的 CAS 只有一方會成功，失敗的一方會繼續 retry，因此這個場景安全無虞。

接著考慮複雜的 `__list_delete`，首先可以看到如論文敘述的兩個 CAS：

bool list_delete(list_t *list, list_key_t key)
{
    list_node_t *curr, *next;
    atomic_uintptr_t *prev;
    while (true) {
        if (!__list_find(list, &key, &prev, &curr, &next)) {
            list_hp_clear(list->hp);
            return false;
        }

        uintptr_t tmp = get_unmarked(next);
        // 第一個 CAS 進行 logically deleted
        if (!CAS(&curr->next, &tmp, get_marked(next))) {
            TRACE(del);
            continue;
        }

        tmp = get_unmarked(curr);
        // 第二個 CAS 進行 physically deleted
        if (CAS(prev, &tmp, get_unmarked(next))) {
            list_hp_clear(list->hp);
            list_hp_retire(list->hp, get_unmarked(curr));
        } else {
            list_hp_clear(list->hp);
        }
        return true;
    }
}

我們直接考慮現在的實作是否可以避免如下圖，node 20 為新增的 node，卻因為同時有 Thread 在刪除 node 10而導致 node 20也跟著被刪除。

##### 1. 進入 `__list_delete` 但還未執行第一個 CAS

##### 2.1 若 `__list_delete` 先成功將 node 10標為 Marked，則 `__list_insert` 的 CAS 會失敗
因為 `__list_insert` 的 CAS 確認的是 `get_unmarked(curr)`

##### 2.2 若 `__list_insert` 先成功將 node 10指向 node 20，則 `__list_delete` 的第一個 CAS 失敗。
因為 `__list_delete` 的 CAS 確認的是 `get_unmarked(next)`

由此可知 logically deleted 和 `__list_insert` 的 race 安全無虞。

那麼，`__list_insert` 和 physically deleted 的 race 呢？考慮如下場景：

##### 1. pysically deleted 和 `__list_insert` race

##### 2.1 `__list_delete` 先成功 unlink node 10，變成下圖

`__list_insert` 的 CAS 失敗，因為它確認的是 `get_unmarked(curr)`

##### 2.2 `__list_insert` 的 CAS 不可能成功
因為它確認的是 `get_unmarked(curr)`

由此可知，只要先 logically deleted 了，`__list_insert` 便會偵測到並且 retry。

上述是 `__list_insert` 和 `__list_delete` 間 race 的分析。更複雜的部份是 `__list_find` 當中各個 atomic operation以及 `__list_insert` 、 `__list_delete` 的 CAS 彼此交錯的分析。
分析重點在於 `__list_find` return 或接近return 時，能不能在一個瞬間保持條件1, 2 ,3的成立。

TODO...

## 2. 指出改進空間並著手實作
TODO

## 3. 對比 rcu_list，解釋同為 lock-free 演算法，跟上述 Hazard pointer 手法有何異同？能否指出 rcu_list 實作缺陷並改進？
TODO