Try   HackMD

2022q1 Homework5 (quiz6)

contributed by < cyrong >

測驗 1

測驗 2

free_later.c

一個 linked list 的實作在最前面
其中包含 list_new, list_add 兩個功能

free_later_t

typedef struct {
void *var;
void (*free)(void *var);
} free_later_t;

這邊的 free_later_t 則是用來儲存之後需要被釋放的資料，而這些資料會先被放在一個 linked list buffer 中

在之後呼叫 free_later_exit 時會將儲存在 buffer 中的資料釋放掉

hashmap.c

hashmap_kv_t

typedef struct hashmap_keyval {
struct hashmap_keyval *next;
const void *key;
void *value;
} hashmap_kv_t;

這個結構用來 link 在每個 bucket 使用的 linked list

hashmap_t

typedef struct {
hashmap_kv_t **buckets;
uint32_t n_buckets;
uint32_t length; /* total count of entries */
/* pointer to the hash and comparison functions */
uint64_t (*hash)(const void *key);
uint8_t (*cmp)(const void *x, const void *y);
/* custom memory management of internal linked lists */
void *opaque;
hashmap_kv_t *(*create_node)(void *opaque, const void *key, void *data);
void (*destroy_node)(void *opaque, hashmap_kv_t *node);
} hashmap_t;

這個結構是主要用的 hashmap，裝有各個 buckets 以及其 linked lists

對 hash map 進行修改的函式有兩個， hashmap_put 和 hashmap_del

hashmap_put 是將一組 key, value 放進 hash map 中，而因為使用 atomic compare and swap，可能會因為其他 thread 導致操作失敗，分為兩種失敗

hashmap_put_replace_fail : 輸入的 key 已經在 hash map 中存在，在進行替換 value 時操作失敗

hashmap_put_head_fail : 輸入的 key 在 hash map 中不存在，而要將此 key 加入到 bucket list 時操作失敗（head 被其他 thread 修改）

hashmap_del 是將輸入的 key 從 hash map 中刪除，一樣可能因為 atomic 指令導致失敗

hashmap_del_fail : key 不是 bucket list head 但存在於 list 中

hashmap_del_fail_new_head : key 為 bucket list head

test-hashmap.c

test_add
重複操作 mt_add_vals 直到 hashmap_put_retries != 0

test_del
重複操作 mt_del_vals 直到 hashmap_del_fail 或是 hashmap_del_fail_new_head != 0

ABA problem

hashmap 中 put 和 del 操作涉及 map 內容的變更，若只是單純使用 CAS 來進行修改資料，可能會發生 ABA 問題，因此在 map 中加入一個新變數 tag

tag 用來指示 map 是否已經被修改，不論是任何修改 tag 都會改變，若是 tag 與原先不同則視為 put 失敗，將重新再執行一次 while loop 中的行為。

bool hashmap_put(hashmap_t *map, const void *key, void *value)
{
    if (!map)
        return NULL;

    /* hash to convert key to a bucket index where value would be stored */
    uint32_t bucket_index = map->hash(key) % map->n_buckets;

    hashmap_kv_t *kv = NULL, *prev = NULL;

    /* known head and next entry to add to the list */
    hashmap_kv_t *head = NULL, *next = NULL;

    while (true) {
        /* copy the head of the list before checking entries for equality */
        head = map->buckets[bucket_index];

        /* find any existing matches to this key */
        prev = NULL;
        if (head) {
            for (kv = head; kv; kv = kv->next) {
                if (map->cmp(key, kv->key) == 0)
                    break;
                prev = kv;
            }
        }

        if (kv) {      /* if the key exists, update and return it */
            if (!next) /* lazy make the next key-value pair to append */
                next = map->create_node(map->opaque, key, value);

            /* ensure the linked list's existing node chain persists */
            next->next = kv->next;

            /* CAS-update the reference in the previous node */
            if (prev) {
                /* replace this link, assuming it has not changed by another
                 * thread
                 */
                uint32_t orig_tag = map->tag;
                uint32_t next_tag = orig_tag + 1;

                if (__atomic_compare_exchange(&map->tag, &orig_tag, &next_tag, 
                                              false,
                                              __ATOMIC_SEQ_CST,
                                              __ATOMIC_SEQ_CST) && 
                    __atomic_compare_exchange(&prev->next, &kv, &next,
                                              false,
                                              __ATOMIC_SEQ_CST,
                                              __ATOMIC_SEQ_CST)) {
                    /* this node, key and value are never again used by this */
                    map->destroy_node(map->opaque, kv);
                    return true;
                }
                hashmap_put_replace_fail += 1;
            } else { /* no previous link, update the head of the list */
                /* set the head of the list to be whatever this node points to
                 * (NULL or other links)
                 */
                uint32_t orig_tag = map->tag;
                uint32_t next_tag = orig_tag + 1;

                if (__atomic_compare_exchange(&map->tag, &orig_tag,
                                              &next_tag, false, __ATOMIC_SEQ_CST,
                                              __ATOMIC_SEQ_CST) && 
                    __atomic_compare_exchange(&map->buckets[bucket_index], &kv,
                                              &next, false, __ATOMIC_SEQ_CST,
                                              __ATOMIC_SEQ_CST)) {
                    map->destroy_node(map->opaque, kv);
                    return true;
                }

                /* failure means at least one new entry was added, retry the
                 * whole match/del process
                 */
                hashmap_put_head_fail += 1;
            }
        } else {       /* if the key does not exist, try adding it */
            if (!next) /* make the next key-value pair to append */
                next = map->create_node(map->opaque, key, value);
            next->next = NULL;

            if (head) /* make sure the reference to existing nodes is kept */
                next->next = head;

            uint32_t orig_tag = map->tag;
            uint32_t next_tag = orig_tag + 1;
            /* prepend the kv-pair or lazy-make the bucket */
            if (__atomic_compare_exchange(&map->tag, &orig_tag,
                                          &next_tag, false, __ATOMIC_SEQ_CST,
                                          __ATOMIC_SEQ_CST) && 
                __atomic_compare_exchange(&map->buckets[bucket_index], &head,
                                          &next, false, __ATOMIC_SEQ_CST,
                                          __ATOMIC_SEQ_CST)) {
                __atomic_fetch_add(&map->length, 1, __ATOMIC_SEQ_CST);
                return false;
            }

            /* failure means another thead updated head before this.
             * track the CAS failure for tests -- non-atomic to minimize
             * thread contention
             */
            hashmap_put_retries += 1;
        }
    }
}

Lock-Free Linked Lists and Skip Lists 論文探討

〈Lock-Free Linked Lists and Skip Lists〉

一般的 linked list 在 concurrent 操作下，delete node 可能會發生問題
使用 compare and swap (C&S) 以實現 deletion 時需確保被刪除的 node 的 next pointer 不會被其他執行緒改變，否則會發生錯誤。

論文中加入兩個 bit 在 next 欄位中

  1. mark : 標記將要被 delete 的 node
  2. flag : 作為一個警告，此 node 的 next 即將要被刪除

mark, flag 不會同時被設定。

並還有在資料結構中加入 backlink 以便 mark, flag 的操作。

每個執行緒偵測到 mark, flag bit 被設定都可以幫忙對應的操作。

Last changed by 
 
吳政宏
0
218
Published on HackMD