# 2021q3 Homework2 (quiz2)
contribute by <`howard-hsien`>
開發環境:

- Win 10 VMware
- Ubuntu 18.04

### atomic API測試區
---
#### CAS

Bool atomic_compare_exchange_strong( volatile A* obj,C* expected, C desired );

測試程式碼，先想辦法完全搞懂atomic API的用法

#include <stdio.h>
#include <stdlib.h>
#include <stdatomic.h>
#include <stdbool.h>

int main(int argc, char ** argv){
    int* original;
    int* expected;
    int desired = 10;
    int ret = -1;
    original = calloc(1, sizeof(int));
    expected = calloc(1, sizeof(int));
    *original = 5;
    *expected = 5;
    printf("before CAS:\t *orignal = %d, *expected = %d, desired = %d, ret=%d \n", *original, *expected, desired, ret);
    ret = atomic_compare_exchange_strong(original, expected, desired);
    printf("After CAS:\t*orignal = %d, *expected = %d, desired = %d, ret=%d \n", *original, *expected, desired, ret);
    return 0;
}

case 1
before CAS:	 *orignal = 5, *expected = 0, desired = 10, ret=-1 
After CAS:	*orignal = 5, *expected = 5, desired = 10, ret=0 

case 2
before CAS:	 *orignal = 10, *expected = 0, desired = 10, ret=-1 
After CAS:	*orignal = 10, *expected = 10, desired = 10, ret=0 

case 3
before CAS:	 *orignal = 5, *expected = 5, desired = 10, ret=-1 
After CAS:	*orignal = 10, *expected = 5, desired = 10, ret=1 

case 4
before CAS:	 *orignal = 10, *expected = 10, desired = 10, ret=-1 
After CAS:	*orignal = 10, *expected = 10, desired = 10, ret=1 

由實驗結果可確認
1. 如果 *expected 與 *original 相同的話， return 會為 true ，且 *original 會被改成 desired。
2. 如果 *expected 與 *orignal 結果不同時， return 會為 false ，且 *expected 會被改成 *original。

可被翻譯成以下程式碼

if (memcmp(original, expected, sizeof(int)) == 0) {
    memcpy(orginal, &desired, sizeof(int));
    return true;
} else {
    memcpy(expected, original, sizeof(int));
    return false;
}

參考:
cpp reference(https://en.cppreference.com/w/c/atomic/atomic_compare_exchange)

---

### 編譯問題區
**一直出現找不到threads.h的問題**

gcc -Wall -o list list.c -lpthread -g -fsanitize=thread -std=gnu11
list.c:15:10: fatal error: threads.h: No such file or directory
 #include <threads.h>
          ^~~~~~~~~~~
compilation terminated.
Makefile:2: recipe for target 'all' failed

解決辦法:
改成include 有人寫的<c11threads.h> reference from(https://raw.githubusercontent.com/jtsiomb/c11threads/master/c11threads.h)
並增加以下macro

#define thread_local _Thread_local

---
### 學習筆記區

* **uintptr_t 的用法**

`void * ` vs `uintptr_t`
若設為uintptr_t可以做為運算子來操作
example:

#define is_marked(p) (bool) ((uintptr_t)(p) &0x01) 
#define get_marked(p) ((uintptr_t)(p) | (0x01))
#define get_unmarked(p) ((uintptr_t)(p) & (~0x01))

若改為

#define is_marked(p) (bool) ((void *)(p) &0x01) 
#define get_marked(p) ((void *)(p) | (0x01))
#define get_unmarked(p) ((void *)(p) & (~0x01))

則會出現以下編譯錯誤

list.c:177:38: error: invalid operands to binary & (have ‘void *’ and ‘int’)
 #define get_unmarked(p) ((void *)(p) & (~0x01))

參考資料:
https://stackoverflow.com/questions/40941825/understanding-void-against-intptr-t-and-uintptr-t

---
### 延伸問題

1. 解釋上述程式碼運作原理
-- **tid**

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_v為thread_local，有thread storage duration的特性，所以每個thread一開始都是TID_UNKNOWN，thread彼此之前不會相互干擾，這也是C11後才有的macro
> thread storage duration. The storage duration is the entire execution of the thread in which it was created, and the value stored in the object is initialized when the thread is started. Each thread has its own, distinct, object. If the thread that executes the expression that accesses this object is not the thread that executed its initialization, the behavior is implementation-defined. All objects declared _Thread_local have this storage duration.
(since C11)

Reference :https://en.cppreference.com/w/c/language/storage_duration

所以這裡調用tid()可以讓不同的thread確實地得到不同的id，我有試著調用pthread_self()來驗證。

--**__list_find**

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))
        goto try_again;
    while (true) {
        if (!get_unmarked_node(curr)){
			printf("!__list_find get_unmarked_node(curr) => curr=%p\n", curr);
            return false;
        }
        next = (list_node_t *) atomic_load(&get_unmarked_node(curr)->next);
        (void) list_hp_protect_ptr(list->hp, HP_NEXT, get_unmarked(next));
        if (atomic_load(&get_unmarked_node(curr)->next) != (uintptr_t) next)
            break;
        if (get_unmarked(next) == atomic_load((atomic_uintptr_t *) &list->tail))
            break;
        if (atomic_load(prev) != get_unmarked(curr))
            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 FFF;
				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 (!atomic_compare_exchange_strong(prev, &tmp, get_unmarked(next)))
                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));
    }
    *par_curr = curr;
    *par_prev = prev;
    *par_next = next;
	printf("__list_find ==> final return false\n");
    return false;
}

透過 key 製作出排序好的 linked list ，在沒辦法進行 atomic 操作的地方使用 hazard pointer 作保護。
這邊我為了想要了解 hazard pointer 的效果，我做了一個沒有 hazard pointer 保護的 list find

static bool __list_find_no_hp(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);
  
    if (atomic_load(prev) != get_unmarked(curr))
        goto try_again;
    while (true) {
        if (!get_unmarked_node(curr)){
		
            return false;
        }
        next = (list_node_t *) atomic_load(&get_unmarked_node(curr)->next);
        if (atomic_load(&get_unmarked_node(curr)->next) != (uintptr_t) next)
            break;
        if (get_unmarked(next) == atomic_load((atomic_uintptr_t *) &list->tail))
            break;
        if (atomic_load(prev) != get_unmarked(curr))
            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 FFF;
				return get_unmarked_node(curr)->key == *key; //FFF 更新狀態
            }
            prev = &get_unmarked_node(curr)->next;
        
        } else {
            uintptr_t tmp = get_unmarked(curr);
            if (!atomic_compare_exchange_strong(prev, &tmp, get_unmarked(next)))
                goto try_again;

        }
        curr = next;

    }
    *par_curr = curr;
    *par_prev = prev;
    *par_next = next;

    return false;
}

但執行多次執行結果都是一樣的， insert = 4098, delete = 4098。
我認為可能是測試方法導致 insert delete 之間不會互相干擾。
我甚至把 marked 相關的操作給改成

//#define get_marked(p) ((uintptr_t)(p) | (0x01))
//#define get_unmarked(p) ((uintptr_t)(p) & (~0x01))
#define get_marked(p) ((uintptr_t)(p))
#define get_unmarked(p) ((uintptr_t)(p))

執行結果也一樣，結果也相同。

用了問題2提到的 delete thread 的改動後才開始能觀察到 hazard ptr 跟這個 lock free sample 強大的地方。

---

2. 指出改進空間並著手實作

測試方式可以調整，因為目前 main function 的測法會讓thread間critical area的問題沒有被呈現出來，我有試著將 hazard ptr 相關的程式碼去除， marked 相關程式碼也去除，結果卻是一樣的，所以應該需要重新設計測試方式，讓 hazard ptr 這個實做所達到 critical area 的保護效果，以及其解決 ABA 問題的能力可以被顯示出來。

首先我先讓 delete thread 的 tid 跟 insert thread的 tid 是會重複的，這樣可以測試 critical area 被同時 access 時是否會出現異常。

static void *delete_thread(void *arg)
{
    list_t *list = (list_t *) arg;

    for (size_t i = 0; i < N_ELEMENTS; i++){
		printf("delete_thread i=%d, tid=%d\n",(int)i, tid());
        (void) list_delete(list, (uintptr_t) &elements[tid()/2][i]);
    }
    return NULL;
}