# 2022q1 Homework5 (quiz5)
contributed by < [cyrong](https://github.com/cyrong) >

## 測驗1

## 測驗2

這個程式有兩個主要的結構體

`hp_t` 和 `domain_t`

`hp_t` 也就是 hazard pointer 的本體，用來指向需要被保護的資料

`domain_t` 是在每個 thread 中存放所有 hazard pointer 的結構，其中包含了 hazard pointer(s) 和 retired list

而還有一個結構體 `config_t` 是被共用的資源的結構

typedef struct {
    unsigned int v1, v2, v3;
} config_t;

static config_t *shared_config;

`shared_config` 是被 hazard pointers 共用的資料

typedef struct {
    hp_t *pointers;
    hp_t *retired;
    void (*deallocator)(void *);
} domain_t;

static domain_t *config_dom;

`config_dom` 是每個 thread 中管理 hazard pointer(s) 和 retired list 的結構

static void *reader_thread(void *arg)
{
    (void) arg;

    for (int i = 0; i < N_ITERS; ++i) {
        config_t *safe_config =
            (config_t *) load(config_dom, (uintptr_t *) &shared_config);
        if (!safe_config)
            err(EXIT_FAILURE, "load");

        print_config("read config    ", safe_config);
        drop(config_dom, (uintptr_t) safe_config);
    }

    return NULL;
}

reader thread 執行兩個函式 `load` 和 `drop`

/*
 * Load a safe pointer to a shared object. This pointer must be passed to
 * `drop` once it is no longer needed. Returns 0 (NULL) on error.
 */

uintptr_t load(domain_t *dom, const uintptr_t *prot_ptr)
{
    const uintptr_t nullptr = 0;

    while (1) {
        uintptr_t val = atomic_load(prot_ptr);
        hp_t *node = list_insert_or_append(&dom->pointers, val);
        if (!node)
            return 0;

        /* Hazard pointer inserted successfully */
        if (atomic_load(prot_ptr) == val)
            return val;

        /*
         * This pointer is being retired by another thread - remove this hazard
         * pointer and try again. We first try to remove the hazard pointer we
         * just used. If someone else used it to drop the same pointer, we walk
         * the list.
         */
        uintptr_t tmp = val;
        if (!atomic_cas(&node->ptr, &tmp, &nullptr))
            list_remove(&dom->pointers, val);
    }
}

/*
 * Drop a safe pointer to a shared object. This pointer (`safe_val`) must have
 * come from `load`
 */
void drop(domain_t *dom, uintptr_t safe_val)
{
    if (!list_remove(&dom->pointers, safe_val))
}

`load` 為取值 `prot_ptr` 後將此 `val` 放進 `dom` 中的 hazard pointer list ，首先先找沒有使用的 node 若沒有找到則建立一個新的 node

`drop` 為將已經是 safe 的 `val` 從 hazard pointer list 中設定為 0，在這之後可以給其他需要放進 `dom` 的值使用

而在 reader thread 中是 load `shared_config` 後 `print_config` ，接著 drop 此 val

writer thread

static void *writer_thread(void *arg)
{
    (void) arg;

    for (int i = 0; i < N_ITERS / 2; ++i) {
        config_t *new_config = create_config();
        new_config->v1 = rand();
        new_config->v2 = rand();
        new_config->v3 = rand();
        print_config("updating config", new_config);

        swap(config_dom, (uintptr_t *) &shared_config, (uintptr_t) new_config,
             0);
        print_config("updated config ", new_config);
    }

    return NULL;
}

writer thread 為建立新的 `config_t` `new_config` 後將其與 `shared_config` 進行對調

而在進行對調後函式 `swap` 會呼叫 `cleanup_ptr` ，用以釋放 (呼叫 deallocator) 舊的值，而如果還有 reader 正在使用舊的值，則等待至沒有任何 reader 使用後釋放

`swap` 中根據 `flags` 來分別不同的實作

`flags & DEFER_DEALLOC` $\neq$ 0 : 不進行等待，只在當下沒有任何 reader reference 時進行釋放，否則等待到下次 cleanup 被呼叫

`flags & DEFER_DEALLOC` $=$ 0 : 等待至沒有任何 reader reference 此 pointer 後釋放