# 2021q3 Homework2 (hp) contributed by < [`RoyWFHuang`](https://github.com/RoyWFHuang) > ###### tags: `linux_class` `kernel` > [2021 年暑期 第 2 週隨堂測驗題目](https://hackmd.io/@sysprog/linux2021-summer-quiz2) > [2021 年暑期 Linux 核心 Homework2](https://hackmd.io/@sysprog/linux2021-summer-homework2) 開發環境為: OS: ubuntu 20.04 kernel ver: 5.4.0-77-generic CPU arch: x86_64 使用 multipass 開發 ```shell $ multipass info dev Name: dev State: Running IPv4: 10.195.227.125 Release: Ubuntu 20.04.2 LTS Image hash: 1d3f69a8984a (Ubuntu 20.04 LTS) Load: 0.00 0.00 0.00 Disk usage: 1.9G out of 4.7G Memory usage: 136.6M out of 981.2M Mounts: /home/roy/src-code => /home/roy/src-code UID map: 1000:default GID map: 1000:default In multipass shell $ uname -a Linux dev 5.4.0-80-generic #90-Ubuntu ``` --- ## 解釋上述程式碼運作原理 首先先看 ```c= #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)) ``` 這邊最是把 address 最後一個 bit 當作 mark 使用, e.g. 0x40004000 -> 表示此address的資料沒被標注 0x40004001 ->則表示被標注 另外再來看 ```c = list_node_t *node = aligned_alloc(128, sizeof(*node)); ``` 除了是要作 cache line作用之外, 最主要是因為要拿, 最後一個 bit 當作 mark 使用的關係, 所以要確保每一個 allocate address 最後一個bit 必須為 0,在考慮到對齊特性(Intel 架構下 128 bit 對齊,詳細請參見 [linD026](https://hackmd.io/@linD026/harzard-pointer#Harzard-Pointer-%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B)有詳細說明), 所以只要保持最後一個 byte 當作 mask使用 ## 指出改進空間並著手實作 1. 首先修正 delete thread do nothing problem ```c= static void *delete_thread(void *arg) { list_t *list = (list_t *) arg; // pthread_barrier_wait(&barr); for (size_t i = 0; i < N_ELEMENTS; i++) (void) list_delete(list, (uintptr_t) &elements[tid()-1][i]); return NULL; } ``` 這樣正常來說 tid()在 create 產生的資料, 全部都可以在 tid()-1 的 thread中刪除, 所以可以將後面的 ```c= for (size_t i = 0; i < N_ELEMENTS; i++) { for (size_t j = 0; j < tid_v_base; j++) list_delete(list, (uintptr_t) &elements[j][i]); } ``` 將之移除, 但移除後出現了, 程式執行完畢後, 仍有未刪除之節點存在list中 ``` curr = 7b4000020400 curr = 7b4000020500 curr = 7b4000020600 curr = 7b4000020700 .... curr = 7b40000b7b00 curr = 7b40000b7c00 curr = 7b40000b7d00 curr = 7b40000b7e00 curr = 7b40000b7f00 curr = 7b4000000000 cnt = 693 ``` 表示delete的方法因為這樣修改出現問題 2. 修正list_delete 在此 function 中,==if (!__list_find(list, &key, &prev, &curr, &next))== 在未發現 node 的狀態下, 會直接回傳 false, 但在這個程式中, create 產生的 node 只會由某一個 delete 固定去刪除, 所以調整如下: ```c= if (!__list_find(list, &key, &prev, &curr, &next)) { list_hp_clear(list->hp); continue; // return false; } ``` 將之改為找不到節點則重新找尋 ``` output : curr = 7b4000000000 cnt = 0 inserts = 4098, deletes = 4032 ``` 3. 修正 所有 create thread 和 delete thread 不是同時開始的問題 使用 barrier 方式解決此問題, 在 create and delete thread 中加入 barrier, 促使所有的 thread 都產生後才開始執行 ```c= pthread_barrier_t barr; static void *insert_thread(void *arg) { list_t *list = (list_t *) arg; pthread_barrier_wait(&barr); //add barrier for (size_t i = 0; i < N_ELEMENTS; i++) // 128 * 32(64/2) (void) list_insert(list, (uintptr_t) &elements[tid()][i]); return NULL; } static void *delete_thread(void *arg) { list_t *list = (list_t *) arg; pthread_barrier_wait(&barr); //add barrier for (size_t i = 0; i < N_ELEMENTS; i++) (void) list_delete(list, (uintptr_t) &elements[tid()-1][i]); return NULL; } ``` 4. create and delete 數量不一致問題 在 list_delete 中 ```c= if (atomic_compare_exchange_strong(prev, &tmp, get_unmarked(next))) { list_hp_clear(list->hp); list_hp_retire(list->hp, get_unmarked(curr)); //DDD; } else { list_hp_clear(list->hp); } ``` 因為同時刪除的關係, 有可能因為在刪除此 node 時, 其他人剛好在刪除其前面的節點, 造成此節點無法刪除, 因此就無法從 retire list 刪除 因此程式最後結束時, 還必須做回收 //TODO.... 6. ## 對比 rcu_list，解釋同為 lock-free 演算法，跟上述 Hazard pointer 手法有何異同？能否指出 rcu_list 實作缺陷並改進？