# 2022q1 Homework5 (quiz6) contributed by < [cyrong](https://github.com/cyrong) > ## 測驗 `1` ## 測驗 `2` ### `free_later.c` 一個 linked list 的實作在最前面 其中包含 `list_new`, `list_add` 兩個功能 `free_later_t` ```c 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` ```c typedef struct hashmap_keyval { struct hashmap_keyval *next; const void *key; void *value; } hashmap_kv_t; ``` 這個結構用來 link 在每個 bucket 使用的 linked list `hashmap_t` ```c 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 中的行為。 ```c 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](http://www.cse.yorku.ca/~ruppert/papers/lfll.pdf)〉 一般的 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 被設定都可以幫忙對應的操作。