# 2021q3 Homework2 (hp)
contributed by < `new-type` >

## 簡介
* **問題描述**：
* 請參閱 [2021 年暑期 Linux 核心 第 2 週測驗題](https://hackmd.io/@sysprog/linux2021-summer-quiz2)
* [原程式](https://github.com/sysprog21/concurrent-programs/tree/master/hp_list)

## 延伸問題 1 - 解釋上述程式碼運作原理
原程式主要是利用 Harzard pointers 來避免正在被其它 threads 使用的物件被刪除。
從原程式 430 行可以看出建立 thread 時會有 3 個 Harzard Pointer

list_hp_t *hp = list_hp_new(3, __list_node_delete);

而在 134 行可以看到 list_hp 中有

struct list_hp {
    int max_hps;
    alignas(128) atomic_uintptr_t *hp[HP_MAX_THREADS];
    alignas(128) retirelist_t *rl[HP_MAX_THREADS * CLPAD];
    list_hp_deletefunc_t *deletefunc;
};

* max_hps：最大的 Harzard pointer 數量 (程式中設定為 3 )
* hp[HP_MAX_THREADS]：正在使用需要防止被刪除的 list
* rl[HP_MAX_THREADS]：已經可以被刪除的 list
* deletefunc：釋放記憶體的函數 (__list_node_delete)

刪除的機制是將準備刪除的物件先拷到 rl 中，處理刪除時再檢查該物件是不是仍然在 hp 中，若是則代表該物件還在使用中，先不刪除；反之則呼叫 deletefunc 刪除。

其中這裏面都是 alignas(128)，應該是為了避免 false sharing 的問題。但是一個 cache line 在 x86_64 上是 64 bytes，這邊使用了 128 bytes 可能是考量到目前最大的 cache line 大小為 128 bytes。

程式在一開始會先建立兩個 node，分別用 head 和 tail 指向它們。而維護 Hazard pointer 機制的主要圍繞在三個函數：
* __find_list
首先在 __find_list 中利用了 CAS 來確保資料狀態是一致的，也就是說要確認 prev, curr 和 curr->next 是不是還是存在之前的 list 中，也就是在確認 curr 的前後 node 是不是還是沒變動，若有變化就代表要重新找。
此外在 node 之中存的都是位置，而且是以遞增的方式，所以可以利用位置的大小判斷新舊的關係。再確認 next 是否有變化。若有變化則代表可能有別的 thread 正在使用，先移到 retire list 之後再刪除。反之若是一致。評估 curr 的 key 若是比輸入的 \*key 小，則可以直接釋放記憶體。反之就可能是大於或是等於的關係，就可以利用是否等於來判斷有沒有找到。

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);
    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));
        /* On a CAS failure, the search function, "__list_find," will simply
         * have to go backwards in the list until an unmarked element is found
         * from which the search in increasing key order can be started.
         */
        if (ATOMIC_LOAD(&get_unmarked_node(curr)->next) != (uintptr_t) next) {
            TRACE(retry);
            goto try_again;
        }
        if (ATOMIC_LOAD(prev) != get_unmarked(curr)) {
            TRACE(retry);
            goto try_again;
        }
        if (get_unmarked_node(next) == next) {
            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 {
            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_insert
在 list_insert 中會先確認 prev 是不是指到 curr ，如果是才會將新的 node 插入到 list；反之會重做一次。

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);
    }
}

* list_delete
在 list_delete 中會確認 curr->next 與 next 是不是同一個，若不是就重做；反之就先把要被刪除 node 的 next 標記並存到 curr->next。然後比較 prev 和 curr 的狀況看是可以需要放到 retire list 中或是可以立刻刪除。

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);

        if (!CAS(&curr->next, &tmp, get_marked(next))) {
            TRACE(del);
            continue;
        }

        tmp = get_unmarked(curr);
        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;
    }
}

## 延伸問題 2 - 指出改進空間並著手實作

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

## 參考
[Lock-Free Data Structures with Hazard Pointers](https://erdani.org/publications/cuj-2004-12.pdf)