# 2021q3 Homework2 (hp) contributed by < zzzoie > ## 1. 解釋上述程式碼運作原理 ### Hazard Pointer資料結構 ``` 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; }; ``` 1. max_hps: 一個thread最多可以儲存的正在使用的節點個數 2. hp: 儲存每個thread正在使用的節點( `prev`, `curr`, `next`) 3. rl: 處存每個thread準備要釋放的節點 4. deletefunc: 用來釋放放在rl裡節點的函式 ### 插入節點 list_insert ``` bool list_insert(list_t *list, list_key_t key); ``` 1. 透過 `__list_find` 尋找是否已經有帶有 `key` 內容的節點存在: - 若 `__list_find` 回傳 `true` : 代表已存在該節點，所以將新建的節點銷毀，並清除目前在執行的thread 的 hazard pointer狀態。 - 若 `__list_find` 回傳 `false` : 代表沒有存在重複的節點，透過 `__list_find` 得到插入節點的位置( `curr` 的前面) 2. 透過 CAS 比較 `prev`的內容是否還是 `curr`，沒被其他 thread 更改: - 如果CAS成功，`prev` 的內容改成新的節點 `node` ，插入節點成功 - 如果CAS失敗，全部重頭開始 ### 刪除節點 list_delete ``` bool list_delete(list_t *list, list_key_t key); ``` 1. 透過 `__list_find` 尋找是否已經有帶有 `key` 內容的節點存在: - 若 `__list_find` 回傳 `false` : 代表沒有存在該節點，清除目前thread 的 hazard pointer狀態。 - 若 `__list_find` 回傳 `true` : 代表有存在的節點，透過 `__list_find` 得到該節點的位置( `curr` ) 2. 透過CAS確認 `next` 沒有被更動過: - CAS成功，將原本的next取代成有 `mark` 的值，透過 `get_marked` MACRO 做 bitwise 運算 - CAS失敗，全部重頭開始 3. 透過CAS確認 `prev`位置的內容還是 `curr`: - CAS成功，`prev` 位置的內容換成`unmark` 的 `next`，並且將 `curr` 交給 `list_hp_retire` 處理 - CAS失敗，直接清除thread 的 hazard pointer狀態 ### 尋找節點 __list_find ``` 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); ``` - 此函式透過 `while` 迴圈對 `list` 做遍歷，直到找到對應的 `curr` 節點 - list的順序是用key的大小來排列，由小排到大 - 將用到的節點存到hazard pointer後，會檢查前後節點是否有被其他 thread 更改，如果被更改，則重頭開始 - 當 `next` 節點是帶有`mark`標記的，代表`curr` 是準備被刪除的節點。透過CAS檢查 `prev` 的位置內容是否還是`curr`，若內容沒被更改，就將`prev`的內容指向`next`, 然後把 `curr` 交給 `list_hp_retire` 處理 ### 釋放節點記憶體　list_hp_retire ``` void list_hp_retire(list_hp_t *hp, uintptr_t ptr); ``` - 檢查所有放在 retirelist 的節點，看是否有其他 thread 正在使用(儲存在hp裡) - 如果沒有其他 thread 在使用該節點，透過deletefunc釋放該節點記憶體