# 2021q3 Homework2 (quiz2)
contributed by < [`WayneLin1992`](https://github.com/WayneLin1992) >
###### tags: `linux2021`
## 延伸問題
- [ ] 解釋程式碼運作原理
- [ ] 指出改進空間並著手實作
- [ ] 對比 rcu_list，解釋同為 lock-free 演算法，跟上述 Hazard pointer 手法有何異同？能否指出 rcu_list 實作缺陷並改進？
## 解釋運作原理
`list_new`
```cpp
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`
```cpp
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`
```cpp
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`
```cpp
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`
```cpp
typedef struct {
int size;
uintptr_t *list;
} retirelist_t;
```
回到 `list_new` 並將 list 中的 head、tail、head->next 設定好，並回傳。
```cpp
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。
```cpp
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`
```cpp
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](https://erdani.org/publications/cuj-2004-12.pdf) 論文
才能實際了解到需要改進的地方
Sign in with Wallet
Connect another wallet