2022q1 Homework5 (quiz5)

contributed by < 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

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

flags & DEFER_DEALLOC

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