2021q3 Homework2 (hp)

contributed by < ccs100203 >

tags: linux2021q3

quiz2

• reference
  Lock-Free Data Structures with Hazard Pointers
  A Pragmatic Implementation of Non-Blocking Linked-Lists
  並行程式設計: Lock-Free Programming
  並行程式設計: Atomics 操作
• source
  hp_list
  concurrent-ll

解釋程式碼運作原理

程式以 lock-free 以及 hazard pointer 的手法，建立相同量的 thread 做 insert / delete 的動作，上圖為 hazard pointer 的結構示意。

Struct

typedef struct {
    int size;
    uintptr_t *list;
} retirelist_t;

Hazard pointer 中使用到的 retire list 的結構

#define CLPAD (128 / sizeof(uintptr_t))
typedef struct list_hp list_hp_t;
typedef void(list_hp_deletefunc_t)(void *);

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;
};

Hazard pointer 的主要結構

• alignas(128) atomic_uintptr_t *hp[HP_MAX_THREADS];
hp 的實作是用一個類似二維陣列去儲存整個 hazard pointer 的內容
  用 HP_MAX_THREADS 去決定 row 有多少，是因為每條 Thread 都要有自己的 hazard pointer，這部份可以從示意圖中看出來，詳細則在 Lock-Free Data Structures with Hazard Pointers 中描述。

• alignas 定義在 C++ 11 中，可在宣告時用來對齊

  the declaration or definition of a class/struct/union or enumeration;
  the declaration of a non-bitfield class data member;
  the declaration of a variable, except that it cannot be applied to the following:
  a function parameter;
  the exception parameter of a catch clause.

  對齊可以避免 false sharing 以及 cacheline coherence 所造成的影響，retirelist 中使用的 CLPAD 就是來協助 cacheline padding 的。
  為何是對齊 128 尚未釐清

• max_hps 決定了每條 thread 中的 hazard pointer 有多少容量 (實作中貌似未檢查)

• alignas(128) retirelist_t *rl[HP_MAX_THREADS * CLPAD];
  每個 Thread 會有 CLPAD 個 retire list

typedef uintptr_t list_key_t;

typedef struct list_node {
    alignas(128) uint32_t magic;
    alignas(128) atomic_uintptr_t next;
    list_key_t key;
} list_node_t;

/* Per list variables */

typedef struct list {
    atomic_uintptr_t head, tail;
    list_hp_t *hp;
} list_t;

此程式的結構都包裝在 list_t 之內，以其為 list 的主體。

• magic 協助驗證正確性，確保該 node 的記憶體範圍並未被其他部份修改到。
• key 是 list 與 hazard pointer 中用來索引的 index，會以 tid 為依據。

Tid

static thread_local int tid_v = TID_UNKNOWN;
static atomic_int_fast32_t tid_v_base = ATOMIC_VAR_INIT(0);
static inline int tid(void)
{
    if (tid_v == TID_UNKNOWN) {
        tid_v = atomic_fetch_add(&tid_v_base, 1);
        assert(tid_v < HP_MAX_THREADS);
    }
    return tid_v;
}

程式利用 tid，以遞增的方式對每條 thread 進行編號，存放在具有 thread_local 性質的 tid_v 中，代表該變數在每個 thread 具有獨立性，並有 thread storage duration。

atomic_int_fast32_t 這個 type 在 std::atomic 及 Fixed width integer types 之中有解釋，在 C++ 11 後有分成 int8_t, int_fast8_t, int_least8_t。

• int8_t 剛好 8 bit 的 int
• int_fast8_t 進行操作最快的 int，但是至少 8 bit
• int_least8_t 該 int 使用最少的 bit，但是至少 8 bit

Find

__list_find 是此程式的核心，這裡會以 lock-free 的手法，並讓 list 維持 ascending，以及讓某些條件下的 node 放入 retire list。回傳 true 代表找到該 key 在 list 內，並藉由 pointer to pointer 的方式回傳給 caller。

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)) {
        TRACE(retry);
        goto try_again;
    }

• prev 的作用像是存放 curr 的複本，用來對照當前的 curr 是否已經被更改，是以 pointer to pointer 的方式。

• try_again: 的作用是當程式發現當前操作的指標有被其他 thread 更動過時，就會重做

• list_hp_protect_ptr 會將操作的節點放入 hazard pointer 中，代表當前的 thread 正在使用，作為避免被刪除的保護

• 第 14~17 行，確認此時的 prev 與 curr 是否相同，不同就要重做

  2021/08/20
  可以確認 head 是否被 mark

    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));
        /* 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) {
            TRACE(retry);
            goto try_again;
        }
        if (ATOMIC_LOAD(prev) != get_unmarked(curr)) {
            TRACE(retry);
            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); // FFF
            }
            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 (!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);
    }
}

while 會對 list 進行尋訪，並找到適當的插入位置 (由小到大)，在找到 curr->key >= key 或 tail 之前不會讓迴圈結束。而如果中途有找到 marked node，則會將該 node 放入 retire list 內，不作為回傳的結果使用。

• 第 21 行會將 next 也放入 hazard pointer 之中。再來會確認 local 的 next 是否與 list 中的 next 相同，因為有可能已經被插入新的節點了，也確認 prev 是否還等於 curr。

• 第 35 行 get_unmarked_node(next) == next 是利用到 A Pragmatic Implementation of Non-Blocking Linked-Lists 的手法，被標記的 memory 區塊代表他是已經準備被刪除的了，所以就不會將此 next 作為要使用的下一個 node。

  • 已經被 mark 的節點，會在第 45 行的 else，先通過 CAS 確定還是當前的 next，然後用 list_hp_retire 將他放入 retire list裡，並進行處理。
  • 未被 mark 的節點，會先透過 (get_unmarked_node(curr)->key < *key) 確認是否符合條件，要注意第 40 行的判斷，會回傳 true 讓程式不插入相同 key 值的節點。

• 使用 list_hp_protect_release 將需要保護的 node 放入 hazard pointer 之中，利用 release 的 memory order 確保在這之前的 store 都以寫入。

Insert

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 (CAS(prev, &tmp, (uintptr_t) node)) {
            list_hp_clear(list->hp);
            return true;
        }
        TRACE(ins);
    }
}

第 6 行會先利用 list_node_new 根據傳入的 key 創一個新的 node，藉由 __list_find 得到插入的位置，要注意回傳 true 則代表有重複節點，所以把現在新創立的 destroy 並從 hazard pointer 中移除。

再來程式會將新的 node 的 next 先指向 curr

再來先透過 CAS 確保 prev 的位置還未被換過，然後將 node 放入原本 curr 的位置中

list_node_new

list_node_t *list_node_new(list_key_t key)
{
    list_node_t *node = aligned_alloc(128, sizeof(*node));
    assert(node);
    *node = (list_node_t){.magic = LIST_MAGIC, .key = key};
    (void) atomic_fetch_add(&inserts, 1);
    return node;
}

利用 aligned_alloc 確保配置的空間對齊 128。

使用 atomic_fetch_add 操作 inserts，紀錄插入的次數。

Delete

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 (!CAS(&curr->next, &tmp, get_marked(next))) {
            TRACE(del);
            continue;
        }

        tmp = get_unmarked(curr);
        if (CAS(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);
        }
        return true;
    }
}

用 __list_find 查找要刪除的節點是否在 list 中，沒有的話記得先從 hazard pointer 將當前保護的 memory 移掉再返回。

第 13 行的 CAS 不僅確保 next 未被更動，將 next mark 可以確保不會被其他 thread 使用。

第 19 行的 CAS 先是確保 prev 與 curr 尚未被動過，然後將 next unmark 並放入原本 list 內 curr 的位置，藉此將 curr 從 list 中移除。移除後的 curr 就交由 list_hp_retire 去處理。

Retire

在 Lock-Free Data Structures with Hazard Pointers 中有提及 retire list 的原理，當 list 內的東西達到一定量時，在這邊是利用 HP_THRESHOLD_R，會去查找所有 hazard pointer 的內容，確認要刪除的 memory 不在 hazard pointer 的保護中，來判斷 retire list 內的記憶體是否可以釋放掉。

void list_hp_retire(list_hp_t *hp, uintptr_t ptr)
{
    retirelist_t *rl = hp->rl[tid() * CLPAD];
    rl->list[rl->size++] = ptr;
    assert(rl->size < HP_MAX_RETIRED);

    if (rl->size < HP_THRESHOLD_R)
        return;

將傳入的 ptr 放入該 thread 對應的 retire list 中。

再藉由 HP_THRESHOLD_R 去判斷是否要開始進行回收的動作，因為程式的 HP_THRESHOLD_R 設為 0，所以每次有節點放入就會立刻進行查找的動作。(或許可以參照論文的建議將其調大)

    for (size_t iret = 0; iret < rl->size; iret++) {
        uintptr_t obj = rl->list[iret];
        bool can_delete = true;
        for (int itid = 0; itid < HP_MAX_THREADS && can_delete; itid++) {
            for (int ihp = hp->max_hps - 1; ihp >= 0; ihp--) {
                if (atomic_load(&hp->hp[itid][ihp]) == obj) {
                    can_delete = false;
                    break;
                }
            }
        }

        if (can_delete) {
            size_t bytes = (rl->size - iret) * sizeof(rl->list[0]);
            memmove(&rl->list[iret], &rl->list[iret + 1], bytes);
            rl->size--;
            hp->deletefunc((void *) obj); // RRR
        }
    }
}

第 9 行，會以每一個 retire list 內的節點，去 hazard pointer 中進行查找，如果有找到就會將 can_delete 設為 false，代表還不能刪除。

最後如果可以刪除，會利用 memmove 將 iret 之後記憶體空間往前移，覆蓋掉被刪除的位置，藉以達到從 retire list 中移除的效果，同時可以維持該陣列的結構。並將要刪除的節點傳入 deletefunc 刪除。(在程式中是 __list_node_delete)

Delete Function

void list_node_destroy(list_node_t *node)
{
    if (!node)
        return;
    assert(node->magic == LIST_MAGIC);
    free(node);
    (void) atomic_fetch_add(&deletes, 1);
}

static void __list_node_delete(void *arg)
{
    list_node_t *node = (list_node_t *) arg;
    list_node_destroy(node);
}

free 之前，會先對照 LIST_MAGIC 是否相同，藉由比對 magic number 來判斷該記憶體位置沒有被不正確的更改，保證程式的正確性。

同樣利用 atomic_fetch_add 操作 deletes，紀錄刪除的次數。

程式改進空間

1. 128 / 2 改成 128 >> 1
2. find 中，try again 到 while 之間驗證 prev 跟 curr 的必要性
3. max_hps 沒檢查，沒做上限
4. memmove 效率? 雖然 intel 有對其優化
5. 論文中有提及 hash table of hazard pointer, hazard pointer / retire list 用其他更方便搜尋的結構跟使用其他搜尋演算法

對比 rcu_list，解釋同為 lock-free 演算法，跟上述 Hazard pointer 手法有何異同？能否指出 rcu_list 實作缺陷並改進？

TODO