2021q3 Homework2 (hp)

contributed by < fwfly >

hp 測試設計

建立 n 個 thread 去對一個 list 做 insert key
然後 n 個 thread 去同一個 list 做 delete key
這樣會同時對一個 list 做新增,刪除跟搜尋(find)而導致 race condition 的問題

最後再用 hp 的方式達到 lock-free 的解法

Elements 的設計

程式用了 2 維 array 去產生 key.
這個 array 可以記錄給個 insert thread 產生的 key
在 delete 的時候， delete thread 也可以根據拿到的 tid 從 array 中找到 key

Bug - delete thread 可能沒有刪到任何的 key

在 main 裡面可以看到 thread 是輪流去產生 delete 跟 insert thread,
所以 delete 跟 insert thread 會有同樣的數目，理想上兩邊剛好可以抵消

        pthread_create(&thr[i], NULL, (i & 1) ? delete_thread : insert_thread,
                       list);

但是問題出在這邊

// 這是 insert thread
(void) list_insert(list, (uintptr_t) &elements[tid()][i]);

// 這是 delete thread 
(void) list_delete(list, (uintptr_t) &elements[tid()][i]);

// 這是 tid 的取得方式, 有新的 thread 就給一個 +1 的 tid
tid_v = atomic_fetch_add(&tid_v_base, 1);

從上面可以知道 key 是 elements 中每一個 cell 的 address
最後產生的 elements 會是下圖

// 這是 elements 
         tid i
insert    0   1,2,3.......max_elements  
delete    1   1,2,3.......max_elements 
insert    2   1,2,3.......max_elements 
delete    3   1,2,3.......max_elements 
insert    4   1,2,3.......max_elements 
 .....

可以看到 delete 跟 insert 是交錯的關係, 所以 delete 永遠不會刪到在 list 中的任何一個 key, 可以簡單地補上 printf 驗證

bool list_delete(list_t *list, list_key_t key)
{
    printf("LST_DEL%d: %ld\n", tid(), 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);
            // 請不要把 printf 加在 list_hp_clear 前面, 不確定是否會影響到 hp 的運作
            printf("LST_DEL%d: %ld ,res: False\n", tid(), key);
            return false;
        }

        printf("LST_DEL%d: %ld ,res: True\n", tid(), key);
        uintptr_t tmp = get_unmarked(next);

然後會發現程式都只會印出 False 直到最後一段把 list 全部清除時才會印到 True
這時候才會做到真正的刪除．
所以如果加上這段 printf, 會發現 True 全部集中在最後一段

LST_DEL1: 94799338001472 ,res: False
...
...
LST_DEL63: 94799338065928 ,res: False
LST_DEL63: 94799338065936 ,res: False
LST_DEL63: 94799338065944 ,res: False
LST_DEL63: 94799338065952 ,res: False
LST_DEL63: 94799338065960 ,res: False
LST_DEL63: 94799338065968 ,res: False
LST_DEL63: 94799338065976 ,res: False
Delete all
LST_DEL64: 94799338000448
LST_DEL64: 94799338000448 ,res: True
LST_DEL64: 94799338001472
LST_DEL64: 94799338001472 ,res: False
LST_DEL64: 94799338002496
LST_DEL64: 94799338002496 ,res: True
LST_DEL64: 94799338003520
LST_DEL64: 94799338003520 ,res: False
LST_DEL64: 94799338004544
LST_DEL64: 94799338004544 ,res: True
LST_DEL64: 94799338005568
LST_DEL64: 94799338005568 ,res: False
LST_DEL64: 94799338006592

patch

用兩個 tid_base 分別計算 insert thread 跟 delete thread
因為 elements 是用 idx 去找 key, 所以並不影響原本的程式．
Patch 的程式碼

經過上面的 patch 後的程式，兩種 thread 確實產生了 race condition, 但是觸發了 ThreadSanitizer: data race 的 error.

$ ./list 
LST_DEL0: 93989954416704
LST_DEL0: 93989954416704 ,res: True
LST_DEL0: 93989954416712
LST_DEL0: 93989954416712 ,res: True
==================
WARNING: ThreadSanitizer: data race (pid=275662)
  Write of size 8 at 0x7b4000010180 by thread T2:
    #0 free ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:707 (libtsan.so.0+0x35f25)
    #1 list_node_destroy /home/fwfly/project/concurrent-programs/hp_list/main.c:325 (list+0x21af)
    #2 __list_node_delete /home/fwfly/project/concurrent-programs/hp_list/main.c:332 (list+0x2209)
    #3 list_hp_retire /home/fwfly/project/concurrent-programs/hp_list/main.c:274 (list+0x1d39)
    #4 list_delete /home/fwfly/project/concurrent-programs/hp_list/main.c:440 (list+0x269e)
    #5 delete_thread /home/fwfly/project/concurrent-programs/hp_list/main.c:497 (list+0x27df)

  Previous atomic read of size 8 at 0x7b4000010180 by thread T1:
    #0 __tsan_atomic64_load ../../../../src/libsanitizer/tsan/tsan_interface_atomic.cpp:539 (libtsan.so.0+0x7ced7)
    #1 __list_find /home/fwfly/project/concurrent-programs/hp_list/main.c:365 (list+0x1fb4)
    #2 list_insert /home/fwfly/project/concurrent-programs/hp_list/main.c:401 (list+0x22c1)
    #3 insert_thread /home/fwfly/project/concurrent-programs/hp_list/main.c:487 (list+0x243f)

  Thread T2 (tid=275665, running) created by main thread at:
    #0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:962 (libtsan.so.0+0x5ea79)
    #1 main /home/fwfly/project/concurrent-programs/hp_list/main.c:509 (list+0x13e0)

  Thread T1 (tid=275664, running) created by main thread at:
    #0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:962 (libtsan.so.0+0x5ea79)
    #1 main /home/fwfly/project/concurrent-programs/hp_list/main.c:509 (list+0x13e0)

SUMMARY: ThreadSanitizer: data race /home/fwfly/project/concurrent-programs/hp_list/main.c:325 in list_node_destroy

問題會發生在做 retire node 的部分，要先理解 retire 跟整個 hp 的設計，才能知道為什麼這邊會發生

從基本的 list 開始

在 atomic 跟 hp 的幫助下，有點難看出來 atomic 跟 hp 解決了什麼事情,
所以把全部的 atomic 跟 hp 拿掉來實驗看看程式會出現什麼結果．

• prev 用的是 atomic_uintptr_t 去接 node，這是為了要讓 prev 可以做 atomic 操作，但是還不清楚為什麼只有在 prev 上面做這件事情．

使用 atomic 來處理 list 中的值

( To do )

使用 hp 來處理 concurrent 問題

( To do )

並行程式設計中的問題

1. RMW 可能會可能無法完成全部. 可能在做 R 或 M 的途中就會被切到另一個 thread 然讀到舊的值，導致結果產生錯誤 -> atomic operation 可解決
2. 執行順序會被compiler 或 CPU 置換 -> 使用 memory barrier 來確保執行順序正確
3. cache coherence 問題 -> atomic 可以等 cache 同步然後寫入 memory，但是會有效能問題

Atomics

這次作業的 list.c 裡面的 hazard pointer 的機制是用 c11 的 atomic 去進行實作．所以再踏入 hazard pointer 前，要先了解一下 atomic 怎麼使用．
這次的實作有用到以下幾個 atomic 的 function

atomic_store : 把值給寫進去 atomic object
atomic_store_explicit : 跟 atomic_store 但是可以選擇怎麼處理 memory order
atomic_load : 把 atomic 值從 atomic object 中讀出來
atomic_compare_exchange_strong : 比較 atomic object atomic 跟另一個參數，如果比較大就把 desired 值存到 atomic object 中

get_unmarked ?
get_unmarked_node ?

References

• 2021 年暑期 Linux 核心 第 2 週測驗題
• atomic_store, atomic_store_explicit
• memory_order
• POSIX Shared Memory
• Validating Memory Barriers and Atomic Instructions
• 内存屏障实验
• Linux Kernel Scheduler Internals - ch2 Multiprocessing
• Memory Barriers: a Hardware View for Software Hackers
• 每位程式開發者都該知道的記憶體知識
• gcc tsan_interface_atomic.cpp
• ThreadSanitizer – data race detection in practice
• TSan: possible false positive with atomics
• Hazard Pointers: Safe Memory Reclamation for
  Lock-Free Objects
• Lock-Free Data Structures with Hazard Pointers