# 2021q3 Homework2 (hp) contributed by < [`9m77fans`](https://github.com/9m77fans/kernel-lab) > ###### tags: `linux2021` > [2021 年暑期 第 2 週隨堂測驗題目](https://hackmd.io/@sysprog/linux2021-summer-quiz2) --- ## 1.解釋程式碼運作原理 在講解程式碼前可以先講講這個link list到底在幹麻,這個link list剛開始看的時候很不直覺, 因為他不是將使用者資料存入,他是保存使用者資料的地址,還有它沒有get操作意思是使用者插入資料後只能刪除,概念上不太像一個container. 所以我加了一些單純測試link list的程式碼, list_travel_debug/list_find_debug是我加入用來理解這個link list的API ```cpp= printf("test insert\n"); (void) list_insert(list, (uintptr_t) &elements[tid()][0]); (void) list_insert(list, (uintptr_t) &elements[tid()][0]); (void) list_insert(list, (uintptr_t) &elements[tid()][0]); list_travel_debug(list); printf("test find\n"); if(list_find_debug(list, (uintptr_t) &elements[tid()][0])) { printf("found element\n"); }else{ printf("not found element\n"); } printf("test delete\n"); (void) list_delete(list, (uintptr_t) &elements[tid()][0]); (void) list_delete(list, (uintptr_t) &elements[tid()][0]); (void) list_delete(list, (uintptr_t) &elements[tid()][0]); list_travel_debug(list); ``` 我們可以看到list的dump確認list的行為,插入的"key"是使用者資料的"地址",重複插入只會有一個保存,重複刪除也不至於爆炸. * 這個list指少會有兩個node(head/tail). * head的key是0x0 ,tail的key是0xffffffffffffffff * 插入的key(地址)一定是介於0x0-0xffffffffffffffff,以此來比大小. ```cpp= test insert dump = 0x0,addr = 0x7b4000000088 dump = 0x558d1d630060,addr = 0x7b4000000288 dump = 0xffffffffffffffff,addr = 0x7b4000000188 test find found element test delete dump = 0x0,addr = 0x7b4000000088 dump = 0xffffffffffffffff,addr = 0x7b4000000188 ``` ### link list API * list_new ： 創造一個lock free 的link list * list_destroy ： 刪除一個lock free 的link list * list_insert ： 將使用者資料的"地址"存入node,thread-safe * list_delete ： 根據使用者資料的"地址",刪除存在list上對應的node,thread-safe 我自己加了2個API方便debug * list_travel_debug : 將link list內的所有key顯示出來 * list_find_debug ：用key搜尋link list是否存在這個key值 先來理解這個list內部結構,有兩個指標指向head/tail node以及一個Hazard pointers(hp)指標 ```cpp= typedef struct list { atomic_uintptr_t head, tail; list_hp_t *hp; } list_t; ``` 1. 初始化(list_new)時會創造兩個node(head/tail),head node的next是指向tail的並將list內的head/tail指標指向這兩個node ```graphviz digraph structs { node[shape=record] rankdir="LR" s1 [label="<l0> list_t|<l1> head|<l2> tail"]; s2 [label="<ln0> list_node_t|<ln1> key\ \ (0)\ |<ln2> next"]; s3 [label="<ln0> list_node_t|<ln1> key\ (UINTPTR_MAX)|<ln2> next(NULL)"]; s1:l1 -> s2; s1:l2 -> s3; s2:ln2 -> s3; } ``` 還有這邊的hp有個特別的地方是128byte的對齊,對齊2個cache line(2*64byte)大小當然是為了解決false sharing問題,只是一般我們解決false sharing都是將資料對齊一個cache line就夠了,這邊卻是對齊兩個,目前我是只有看到[`folly`](https://github.com/facebook/folly)這套facebook的函式庫有這樣做,它註解中寫到這是他們實驗的結果,兩個cache line對齊再跟atomic變數操作時效能比較好！可是我看過其他知名的函式庫都還只是一個cache line對齊,這其實讓我蠻疑惑的... ```cpp= 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; }; ``` 2. 插入key(list_insert)它首先會為key值創造一個node將其存入,接著用__list_find去現有的list搜尋適合插入此node的位置，之前說過這個list內存的都是使用者資料的地址所以他是比地址大小找個一個把它大的地址即為cur然後下一個node為next,prev指標存的是cur地址也求是前一個node的node地址,這是一個[`有品味`](https://medium.com/fcamels-notes/%E5%BE%9E%E5%88%AA%E9%99%A4-linked-list-node-%E7%9C%8B%E7%A8%8B%E5%BC%8F%E8%A8%AD%E8%A8%88%E7%9A%84%E5%93%81%E5%91%B3-b597cc5af785)的link list(),接下來就比較單純,調整link list的指標,只是注意的是這個lock free link list所以需要用atomic store操做先調整node->next在用compare_exchange來確認整個node的調整中間是否被另一個thread插隊.完成的話就返回true. ```cpp= 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 (atomic_compare_exchange_strong(prev, &tmp, (uintptr_t) node)) { list_hp_clear(list->hp); return true; } } } ``` __list_find需要比較注意的是它也是一系列的atomic操作,需要特別注意的是hp 這邊的hp就是將這個thread用到的node都保護起來以防被其他人釋放,所以我們可以看到重點12(13)行我們選定了 curr就要將它放入hp內保護還有17(18),34(34),43(44)都是我們要用node所以需要放入hp內 反之41行當我們知道此node不會在被用到了就可以丟入retire list ```cpp= 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)) goto try_again; while (true) { 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) goto try_again; if (atomic_load(prev) != get_unmarked(curr)) 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 (!atomic_compare_exchange_strong(prev, &tmp, get_unmarked(next))) 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)); } } ``` 3. 刪除node (list_delete)的想法跟insert也是類似的,用__list_find去現有的list搜尋資料地址(key)跟傳入的key相同的話就回傳true,接著根據pre/curr/next刪除及調整link list ```cpp= 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 (!atomic_compare_exchange_strong(&curr->next, &tmp, get_marked(next))) continue; tmp = get_unmarked(curr); if (atomic_compare_exchange_strong(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個commit一個修正一些初始化list的小問題,另一個增加測試list功能的程式碼與debug API,最後我自己的理解這個程式memory order還有調整空間. * Keep code more readable [`3da6435fd7`](https://github.com/9m77fans/kernel-lab/commit/3da6435fd7b3555b1d4cb6e5791006b6eaf4dd13) * Add debug API and test code[`e439d0e281`](https://github.com/9m77fans/kernel-lab/commit/e439d0e281095a81030198ae2eadfdeacad50ff4) * Relaxe some atomic load[`0852e51ad2`](https://github.com/9m77fans/kernel-lab/commit/0852e51ad23154a4a266f1332368425de173839f)