2022q1 Homework5 (quiz5)

contributed by < Korin777 >

測驗二

程式研讀

程式運作

• reader 會透過 load 函式 來讀 shared_config 並透過 list_insert_or_append 函式 將正在使用的 config 插入 config_dom->pointer(即為 hazard pointer) ， reader 印出 config 後在透過 drop 函式 將 config 從 hazard pointer 移除
• writer 透過 swap 函式 更新 shared_config ， 並將舊的 config 透過 cleanup_ptr 函式 釋放
• 只有一個 writer 時 ， updating config 到 updated config 中間 ， read config 會印出兩種不同的 config ， 一個是舊的一個新的 config ， 等到 updated config 後 read config 所印出的 config 才會一致

load

uintptr_t load(domain_t *dom, const uintptr_t *prot_ptr)
{
    const uintptr_t nullptr = 0;
    while (1) {
        //  reader 讀 shared_config 並將它插入 config_dom->pointers(hazard pointer)
        uintptr_t val = atomic_load(prot_ptr);
        hp_t *node = list_insert_or_append(&dom->pointers, val);

        if (!node)
            return 0;

        /*   如果 prot_ptr != val 表示 writer 已寫入新的 config ,
         * 如果 reader 讀到舊的 val 且尚未插入 hazard pointer , 
         * writer 就去寫入新的 value 並釋放舊的 val 就會發生錯誤 ,
         * 因此要避免上述狀況 
         */  
        if (atomic_load(prot_ptr) == val)
            return val;

        // 重讀 shared_config 前先把剛插入的 hazard pointer 移除
        uintptr_t tmp = val;
        if (!atomic_cas(&node->ptr, &tmp, &nullptr))
            list_remove(&dom->pointers, val);
    }
}

list_remove

bool list_remove(hp_t **head, uintptr_t ptr)
{
    hp_t *node;
    const uintptr_t nullptr = 0;

    LIST_ITER (head, node) {
        uintptr_t expected = atomic_load(&node->ptr);
        if (expected == ptr && atomic_cas(&node->ptr, &expected, &nullptr))
            return true;
    }
    return false;
}

• list_remove 不會將 node 從 link list 移除 ， 而是將該 node 變為空的 node 讓其他人可以使用

drop

void drop(domain_t *dom, uintptr_t safe_val)
{
    if (!list_remove(&dom->pointers, safe_val))
        __builtin_unreachable();
}

• __builtin_unreachable 能讓 compiler 改變 branch 的順序(e.g. if 先往外面執行) 及消除 dead code (e.g. if 內的 ret) ， 這裡的 list_remove 函式 也不該 return false (因為 hazard pointer 的移出不該失敗) ， 若走到 __builtin_unreachable() 也能讓我們得知在 drop 函式 發生錯誤了

swap

void swap(domain_t *dom, uintptr_t *prot_ptr, uintptr_t new_val, int flags)
{
    // 更新新的 shared_config
    const uintptr_t old_obj = atomic_exchange(prot_ptr, new_val);
    cleanup_ptr(dom, old_obj, flags);
}

cleanup_ptr

static void cleanup_ptr(domain_t *dom, uintptr_t ptr, int flags)
{
    if (!list_contains(&dom->pointers, ptr)) { /* deallocate straight away */
        dom->deallocator((void *) ptr);
    } else if (flags & DEFER_DEALLOC) { /* Defer deallocation for later */
        list_insert_or_append(&dom->retired, ptr);
    } else { /* Spin until all readers are done, then deallocate */
        while (list_contains(&dom->pointers, ptr))
            ;
        dom->deallocator((void *) ptr);
    }
}

• 若 flag 為 0 則 writer 一直等到 hazard pointer 沒此 config 在釋放它
• 若 flag 為 1 則 writer 將此 config 插入 config_dom->retired(即 retired list , 之後在透過 cleanup 函式來釋放) ， 因此 writer 不須等待 reader 繼續更新 config

改進

發現

雖然程式有實做 retire list ， 但 writer_thread 傳入 cleanup_ptr 函式 的 flags 為 0 ， 因此不會將要移除的 config 插入 retire list 而會用 busy waiting 的方式來釋放舊的 config

實做

static void *writer_thread(void *arg)
{
    (void) arg;

    hp_t *local_retired = NULL, *tmp;

    for (int i = 0; i < N_ITERS / 2; ++i) {
        cleanup(config_dom,1, (uintptr_t) &local_retired);
        config_t *new_config = create_config();
        new_config->v1 = rand();
        new_config->v2 = rand();
        new_config->v3 = rand();
        // 將 new_config 插入 hazard pointer
        list_insert_or_append(&config_dom->pointers, (uintptr_t) new_config);
        print_config("updating config", new_config);

        swap(config_dom, (uintptr_t *) &shared_config, (uintptr_t) new_config,
             1, (uintptr_t) &local_retired);
        print_config("updated config ", new_config);
        // 將 new_config 移出 hazard pointer 
        drop(config_dom, (uintptr_t) new_config);
    }
    while(local_retired)
        cleanup(config_dom,1, (uintptr_t) &local_retired);
    return NULL;
}

• 原本的 retired list 是 global 的 ， 所有 writer 都能存取到 ， 但這裡我將 retired list 改為 local 的 。 每個 writer 需要將自己替換掉的 shared_config 加入自己的 local_retired 並負責釋放此 config
• writer 結束前必須確保自己負責的 config 都已經釋放了
• retired list 改為 local 的好處有讓對 retired list 操作不再需要用 atomic operation ; 而每個 config 被唯一一個 writer 保存 ， 因此 traverse retired list 的路徑也可以減少

void swap(domain_t *dom, uintptr_t *prot_ptr, uintptr_t new_val, int flags, uintptr_t local_retire)
{
    // 更新新的 shared_config
    const uintptr_t old_obj = atomic_exchange(prot_ptr, new_val);
    cleanup_ptr(dom, old_obj, flags, local_retire);
}
static void cleanup_ptr(domain_t *dom, uintptr_t ptr, int flags, uintptr_t local_retire)
{
    if (!list_contains(&dom->pointers, ptr)) { /* deallocate straight away */
        dom->deallocator((void *) ptr);
    } else if (flags & DEFER_DEALLOC) { /* Defer deallocation for later */
        independent_list_append(local_retire, ptr);
    } else { /* Spin until all readers are done, then deallocate */
        while (list_contains(&dom->pointers, ptr))
            ;
        dom->deallocator((void *) ptr);
    }
}
void cleanup(domain_t *dom, int flags, uintptr_t local_retired)
{
    hp_t *node;
    for(node = *(hp_t **)local_retired; node;) {
        uintptr_t ptr = node->ptr;
        hp_t *retire_node, *tmp;
        tmp = node;
        node = node->next;
        if (!ptr)
            continue;
        if (!list_contains(&dom->pointers, ptr))
            if(independent_list_remove(local_retired, ptr))
                dom->deallocator((void *) ptr);
    }
}

• 傳入 writer 的 local retired list 及更換操作 retired list 的函式 independent_list_remove、independent_list_append

#define INDEPENDNET_LIST_ITER(head, node) \
    for (node = *head; node; node = node->next)
static hp_t *independent_list_append(hp_t **head, uintptr_t ptr)
{
    hp_t *new = calloc(1, sizeof(hp_t));
    if (!new)
        return NULL;
    new->ptr = ptr;
    new->next = *head;
    *head = new; 
    return new;
}
bool independent_list_remove(hp_t **head, uintptr_t ptr)
{
    hp_t *node, *prev = NULL;
    const uintptr_t nullptr = 0;

    INDEPENDNET_LIST_ITER (head, node) {
        if (node->ptr == ptr) {
            if(prev)
                prev->next = node->next;
            else
                *head = node->next;
            free(node);
            return true;
        }
        prev = node;
    }
    return false;
}

• 因為 retired list 改為 local 的 ， 在插入及移除可以不用 atomic operation

比較 retired list 與 busy waiting

N_ITERS 固定為 10000

writer 固定為 4 個 ， 增加 reader 數量

• 使用 busy wating 和 retired list 的執行時間差異不大

reader 固定為 4 個 ， 增加 writer 數量

• 當 writer 為 8 個時 busy waiting 的時間大幅增加 (註：有時當 writer 為 8 個時 busy waiting 的時間還是可以跟 retired list 差不多)
• 執行程式並透過 perf 來觀察程式熱點
  • 使用 retired list 時 ， 在各函式所佔的百分比大致相差不多 ， 佔比較多的有 list_insert_or_append、list_remove、syscall_exit_to_user_mode、__random ， 其中 random 函式似乎會使用到 futex
  • 使用 busy waiting 時 ， 可以發現在 list_contains 佔了 90% 以上 ， 而 cleanup_ptr 則佔了 5％ 左右 。 會卡在這裡的原因就是要等 reader 及其他 writer drop 掉插入 hardzrad pointer 的 config ， 因此 writer 一直透過 list_contains 來查看 hardzrad pointer
• retired list 和 busy wating 還有一個不同的地方是 ， retired list 的 print config 和 updating/updated config 的交錯會比較頻繁 ， 因為 writer 不用等 reader

開啟多個 writer 無法通過 ThreadSanitizer

static void *writer_thread(void *arg)
{
    (void) arg;
    for (int i = 0; i < N_ITERS / 2; ++i) {
        config_t *new_config = create_config();
        new_config->v1 = rand();
        new_config->v2 = rand();
        new_config->v3 = rand();
        // 將 new_config 插入 hazard pointer
        list_insert_or_append(&config_dom->pointers, (uintptr_t) new_config);
        print_config("updating config", new_config);
        swap(config_dom, (uintptr_t *) &shared_config, (uintptr_t) new_config,
             0);
        print_config("updated config ", new_config);
        // 將 new_config 移出 hazard pointer 
        drop(config_dom, (uintptr_t) new_config);
    }
    return NULL;
}

問題

• 原本只有一個 writer ， new_config 並不會被動到 ， 而當開啟多個 writer new_config 就有可能受到其他 writer 的操作
• e.g.
  1. writer1 在 print_config("updated config ", new_config) 前停下換 writer2 執行
  2. writer2 經過 swap 函式 換掉 shared_config 並取得 old_obj(即 writer1 的 new_config) 在透過 cleanup_ptr 函式 查看是否能釋放它 ， 這時要是剛好沒有 reader 在使用它 ， writer2 就能將它釋放 ， writer2 停下換 writer1 執行
  3. writer1 此時要印出 new_config 就會發生問題

解決方法

• 在進入 swap 函式 前 ， 先將 new_config 插入 hazard pointer 讓其他 writer 必須等待而無法將它釋放 ， 等 writer 不用使用到 new_config 後在透過 drop 函式 將它從 hazard pointer 移除 ， 這時其他 writer 便能將它釋放

比較 RCU 和 hazard pointer (HP)

RCU

• reader
  • 透過 rcu_read_lock、rcu_read_unlock 所建立的 critical section 來保護資料
    • rcu_read_lock : 通知 reclaimer 自己進入 crtical section
    • rcu_read_unlock : 通知 reclaimer 自己離開 crtical section
• updater
  • removal
    • 透過 spinlock 確保同時只有一個 writer 在更新資料
    • writer 先複製一份舊的資料並更新它 ， 接著用此替換掉舊的資料
  • reclamation
    • 透過 synchronize_rcu、call_rcu 來釋放資料
      • synchronize_rcu : block updater 直到 pre-existing RCU
        read-side critical sections 都完成
      • call_rcu : updater 不會被 block ， pre-existing RCU
        read-side 都完成才會執行註冊的 callback function

RCU 和 HP 的差異

1. 在 reader 方面 RCU 不會用到 lock 及 atomic operation ; HP 則需要在使用到 shared data 及 hazard pointer 時使用 atomic operation ， 若拿到的 shared data 為舊的就要重新讀取。
2. 在 writer 方面 ， RCU 透過 spinlock 來確保同時只有一個 writer 在更新 shared data ; HP 則是透過 atomic operation
3. RCU 透過 crical section 來保護 reader 正在使用的 shared data ; HP 則透過 hazard pointer 來保護

題目連結

對照研讀 hp_list 程式碼，這是測驗題後續改進的實作

jserv

研讀 hp_list

程式運作

• thread 間共享一個 key 值遞增且唯一的 link list
• 每個 thread 有自己的 hazard pointer 及 retired list
• insert thread 負責新增節點 ; delete thread 負責移除節點(logically delete) 並嘗試將它 physically delete 。 兩者皆會透過 __list_find 函式 嘗試將經過的 logically delete 節點 physically delete
  • logically delete: 將欲移除 node 的 next 所指向的地址的最後一個 bit 改為 1 (因記憶體對齊的緣故 , 原本記憶體位置的最後一個 bit 為 0)
  • physically delete: 將 node 從 link list 上移除(尚未釋放) 並加到 retired list
  • 並行程式設計: Lock-Free Programming 提到 concurrent linked list 會發生的問題
    ​​​​​​​​// 先 insert 且做到一半:
    ​​​​​​​​node_10_next = atomic_load(&(node_10->next))
    ​​​​​​​​node_20->next = node_10_next
    ​​​​​​​​// 換 delete:
    ​​​​​​​​head_next = atomic_load(&(H->next))
    ​​​​​​​​CAS(&(H->next), head_next,  head->next->next) 
    ​​​​​​​​// 回到 insert:
    ​​​​​​​​CAS(&(node_10->next), node_10_next, node_20) // error
    

    
    原本的 delete 過程中並不會更動到 node_10->next , 所以 insert 如期執行而產生錯誤的結果 ; 而 logically delete 就是透過改變 node_10->next 來避免上述問題

__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)
{
    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);
    // 確保沒有其他人新增 node 在curr 前或插入 hp 前 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));

        // 確保沒有其他人新增 node 在 next 前或插入 hp 前 next 被其他人釋放
        if (ATOMIC_LOAD(&get_unmarked_node(curr)->next) != (uintptr_t) next) {
            TRACE(retry);
            goto try_again;
        }
        // 確保沒有其他人新增 node 在 curr 正前面
        if (ATOMIC_LOAD(prev) != get_unmarked(curr)) {
            TRACE(retry);
            goto try_again;
        }
        // curr 沒被 logically delete
        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 { // 查看是否能 physically delete , 將 curr 加到 retired list
            uintptr_t tmp = get_unmarked(curr);
            // 確保沒人新增 node 在 curr 正前面及 curr 還沒被 physically delete
            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);
    }
}

• par_curr: 持有的 key 大於等於所要尋找的 key 的 node
• par_prev: node->next 為 par_curr 的 pointer 地址
• par_next: par_curr->next 的值
• return value: 若 key 存在回傳 true , 反之回傳 false
• 會將 par_curr 及其前後一個 node 插入 hp , 這 3 個 node 就是 thread 正在使用的 data , 用完後透過 list_hp_clear 從 hazard pointer 移除

list_insert

bool list_insert(list_t *list, list_key_t key)
{
    // curr 為新增 node 的 next , *prev 為
    list_node_t *curr = NULL, *next = NULL;
    atomic_uintptr_t *prev = NULL;

    list_node_t *node = list_node_new(key);

    while (true) {
        // key 已經存在了
        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);
        /*    *prev 應該與 get_unmarked(curr) 相等 , 不是的話就 
         *   表示有其他 thread 新增 node 在 curr 正前方或前一個 
         *   node 已經 physically delete , 則必須重來
         */
        if (CAS(prev, &tmp, (uintptr_t) node)) {
            list_hp_clear(list->hp);
            return true;
        }
        TRACE(ins);
    }
}

list_delete

bool list_delete(list_t *list, list_key_t key)
{
    list_node_t *curr, *next;
    atomic_uintptr_t *prev;
    while (true) {
        // key 不存在
        if (!__list_find(list, &key, &prev, &curr, &next)) {
            list_hp_clear(list->hp);
            return false;
        }

        uintptr_t tmp = get_unmarked(next);
        /*     將 curr logically delete , curr->next 應該與 get_unmarked(next) 
         *   相等 , 不是的話就表示有其他 thread 新增 node 在 curr 正後方或 curr 已經被 logically delete , 則必須重來
         */
        if (!CAS(&curr->next, &tmp, get_marked(next))) {
            TRACE(del);
            continue;
        }

        // 若沒人新增 node 在 curr 正前面且 curr 還沒被 physically delete , 將 curr physically delete
        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;
    }
}

TODO: 討論上述實作是否能避免 ABA Problem?

jserv

討論 ABA 問題

• 根據 ABA Problem 所舉的例子
• 假設 link list 一開始為 (head,0) -> (0x4,1) -> (0x8,2) -> (0xc,3) -> (tail,UINTPTR_MAX)
• (address,data)

thread1 先執行

// list_delete 1
prev = &head->next;
curr = 0x4;
next = 0x8;
tmp = 0x8;

thrad1 在執行 CAS(&curr->next, &tmp, get_marked(next)) 前被 thread2 中斷

// list_delete 1
{
    prev = &head->next;
    curr = 0x4;
    next = 0x8;
    tmp = 0x8;
    // logically delete , marked 0x4->next
    CAS(&curr->next, &tmp, get_marked(next))
    // physically delete , head -> 0x8 -> 0xc -> tail
    CAS(prev, &tmp, get_unmarked(next)) 
}
// list_delete 2
{
    prev = &head->next;
    curr = 0x8;
    next = 0xc;
    tmp = 0xc;
    // logically delete , marked 0x8->next
    CAS(&curr->next, &tmp, get_marked(next))
    // physically delete , head -> 0xc -> tail
    CAS(prev, &tmp, get_unmarked(next)) 
}
// list_insert 1 , 假設 new_node 地址剛好為 0x4
{
    prev = &head->next;
    curr = 0xc;
    ATOMIC_STORE_EXPLICIT // new_node->next = 0xc
    //  head->next = 0x4 , head -> 0x4 -> 0xc -> tail
    CAS(prev, &tmp, (uintptr_t) new_node)  
}

回到 thread1 執行

/* prev = &head->next;
 * curr = 0x4;
 * next = 0x8;
 * tmp = 0x8;
 * head -> 0x4 -> 0xc -> tail
 */ 
CAS(&curr->next, &tmp, get_marked(next))
tmp = curr;
// 可能會產生 ABA 問題
CAS(prev, &tmp, get_unmarked(next))

• 此時的 curr 為 thread2 插入的 , curr->next 為 0xc , 所以第一個 CAS 不會將 curr logically delete , 在這個狀況下會重新執行 list_delete
• 如果 thread2 不只新增了 0x4 還新增了 0x8 , 則 link list 為 head -> 0x4 -> 0x8 -> 0xc -> tail , 這時第一個 CAS 就可以將 curr logically delete 並執行第二個 CAS , 而第二個 CAS 也可以將 curr physically delete , 就會產生先執行的 delete 去移除後面 insert 近來的 node 的情況 。 不過實際上 thread1 會將 head,0x4,0x8 插入 harzard pointer 來延緩 physically delete , 因為記憶體還沒被釋放 , 所以 thread2 所新增的節點記憶體位置應該不會在 0x4 及 0x8 , 因此上述的情況應該也不會發生。
• 就上述情況 , 此實做能避免 wekipedia 所舉出的 ABA 問題

參考資料 ：
What optimizations does __builtin_unreachable facilitate?
What is RCU? – "Read, Copy, Update"