2021q3 Homework2 (quiz2)

contributed by < WayneLin1992 >

tags: linux2021

延伸問題

• 解釋程式碼運作原理
• 指出改進空間並著手實作
• 對比 rcu_list，解釋同為 lock-free 演算法，跟上述 Hazard pointer 手法有何異同？能否指出 rcu_list 實作缺陷並改進？

解釋運作原理

list_new

list_t *list_new(void)
{
    list_t *list = calloc(1, sizeof(*list));
    assert(list);
    list_node_t *head = list_node_new(0), *tail = list_node_new(UINTPTR_MAX);
    assert(head), assert(tail);
    list_hp_t *hp = list_hp_new(3, __list_node_delete);

    atomic_init(&head->next, (uintptr_t) tail);
    *list = (list_t){.hp = hp};
    atomic_init(&list->head, (uintptr_t) head);
    atomic_init(&list->tail, (uintptr_t) tail);

    return list;
}

calloc(size_t number, size_t size) 配置一個空間，初始值為 0
typedef struct list list_t

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

list_node_new 就會配置一個 list_node_t *node 空間並且 aligned 128 ，*node = (list_node_t){.magic = LIST_MAGIC, .key = key};，後 atomic_add 使 insert + 1 insert 為全域變數，所以要注意是否有保持一致
typedef struct list_node list_node_t

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

創立一個 tail 和 head
list_hp_new 配置一個 list_hp_t *hp 空間並且 aligned 128 ， *hp = (list_hp_t){.max_hps = max_hps, .deletefunc = deletefunc}; 並創 hp[128] 個別要 CLPAD * 2 為 32 bytes * sizeof(atomic_uintptr_t ) 的空間，hp->rl[128 * 32] 個別要 sizeof(retirelist_t) 的空間， hp->rl[i * CLPAD]->list = calloc(HP_MAX_RETIRED, sizeof(uintptr_t));
typedef struct list_hp list_hp_t

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

retirelist_t

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

回到 list_new 並將 list 中的 head、tail、head->next 設定好，並回傳。

pthread_t thr[N_THREADS];
for (size_t i = 0; i < N_THREADS; i++)
    pthread_create(&thr[i], NULL, (i & 1) ? delete_thread : insert_thread,
                   list);

會檢查目前 i 為偶數就會 insert_thread 奇數就會 delete_thread 參數為 list。

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_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 (!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));//DDD
        } else {
            list_hp_clear(list->hp);
        }
        return true;
    }
}

__list_find
__list_find(list, &key, &prev, &curr, &next) 會透過 curr = list->head next = curr->next prev = &list->head
atomic_load(&get_unmarked_node(curr)->next) != (uintptr_t) next 確保 next 沒被 mark
get_unmarked(next) == atomic_load((atomic_uintptr_t *) &list->tail) 確保 next 不是 &list->tail
atomic_load(prev) != get_unmarked(curr) 確保 curr 沒被 mark 與且 和 prev 和 curr 相等
get_unmarked_node(next) == next 確保 next 沒被 mark ，
return get_unmarked_node(curr)->key == *key 回傳 curr->key == *key
回到 list_delete
atomic_compare_exchange_strong(&curr->next, &tmp, get_marked(next)) 把 next mark 起來並存進 list 當中， mark 起來代表有人要處裡
atomic_compare_exchange_strong(prev, &tmp, get_unmarked(next)) 把 head = next 並取消 next 的 mark
list_hp_clear 將 &hp->hp[tid()][i] 存入 0
把原本的 curr 存入 retire list rl->list[rl->size++] = ptr
list_destroy
會循環透過 list_node_destroy 刪除 node 之後並全域函數 deletes + 1

最後顯示出 deletes inserts 數值

指出改進空間並著手實作

閱讀 Lock-Free Data Structures with Hazard Pointers 論文
才能實際了解到需要改進的地方