2022q1 Homework5 (quiz5)

contributed by < Risheng1128 >

作業說明
測驗題目

測驗 1

延伸問題:

• 解釋上述程式碼運作原理，指出可改進之處並實作

  是否有必要先將數值轉成字串？用十進位的角度處理運算是否產生額外的計算負擔？

• Linux 核心原始程式碼 lib/math/prime_numbers.c 有類似的程式碼，請解釋其作用、裡頭 RCU 的使用情境，及針對執行時間的改進

測驗 2

延伸問題:

• 解釋上述程式碼運作原理，指出可改進之處並實作
• 上述程式碼開啟多個 reader 時，無法通過 ThreadSanitizer，請指出具體問題並克服
• 比較 RCU 和 hazard pointer (HP)，探討為何 Linux 不採用 HP 而是另外發展 RCU

初始化

首先從實作中兩個重要的結構 domain_t 及 hp_t 開始討論

typedef struct {
    hp_t *pointers; // hazard pointers
    hp_t *retired;  // retire list
    void (*deallocator)(void *);
} domain_t;

typedef struct __hp {
    uintptr_t ptr;
    struct __hp *next;
} hp_t;

從結構定義可以很明顯的看出兩種結構分別的用意

• domain_t 用來建立管理 hazard pointer 和 retire list 的結構，其中 deallocator 是用來釋放記憶體的函式指標
• hp_t 為一般的 linked list 實作，用來儲存共享資料，並加進 hazard pointer 或 retire list ，ptr 則是正在讀取的資料的地址

以上述的結構定義可以得到和題目一樣的架構

接著討論結構的建立以及釋放，實作為函式 init 及 deinit

// 共享資料
typedef struct {
    unsigned int v1, v2, v3;
} config_t;

static config_t *shared_config;
static domain_t *config_dom;

void init()
{
    // 建立共享資料，且初始 (v1,v2,v3) = (0,0,0)
    shared_config = create_config();
    // Create a new domain on the heap
    config_dom = domain_new((void *)delete_config);
    if (!config_dom)
        err(EXIT_FAILURE, "domain_new");
}

void deinit()
{
    delete_config(shared_config);
    domain_free(config_dom);
}

函式 init 的部份，一共做了兩件事

• 建立資料 (型態為 config_t) ，並且由指標 shared_config 指著，以下為函式 create_config 的實作
  ​  config_t *create_config()
  ​  {
  ​​  	config_t *out = calloc(1, sizeof(config_t));
  ​​  	if (!out)
  ​​      	err(EXIT_FAILURE, "calloc");
  ​​  	return out;
  ​  }
  

• 建立 hazard pointer 的整個架構，並且由指標 config_dom 指著，以下為函式 domain_new 的實作
  ​  domain_t *domain_new(void (*deallocator)(void *))
  ​  {
  ​​    	domain_t *dom = calloc(1, sizeof(domain_t));
  ​  	if (!dom)
  ​    		return NULL;
  
  ​  	dom->deallocator = deallocator;
  ​  	return dom;
  ​  }
  

函式 deinit 則是將 shared_config 和 config_dom 分別釋放，以下為函式實作

void delete_config(config_t *conf)
{
    assert(conf);
    free(conf);
}

void domain_free(domain_t *dom)
{
    if (!dom)
        return;

    if (dom->pointers)
        list_free(&dom->pointers); // 釋放 hazard pointer

    if (dom->retired)
        list_free(&dom->retired); // 釋放 retired list

    free(dom);
}

Reader Thread

程式主要執行的部份可以分為 reader thread 及 writer thread ，首先討論 reader thread 的部份

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 最主要的步驟就是先將讀取資料(這邊是 shared_config) 加進 hazard pointer (line 7) ，成功之後進行資料讀取的動作 (line 11) ，最後將該節點從 hazard pointer 移除 (line 12)

接著分析資料加進 hazard pointer 的實作部份，即函式 load

/*
 * 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);
        // 判斷 val 所擁有的資料是否已經在 hazard pointer 裡
        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);
    }
}

首先判斷 val 是否已經存在於 hazard pointer 裡 (line 12) ，接著判斷 hazard pointer 是否加入成功 (line 17) ，如果是就回傳資料的地址 val ，如果否就繼續判斷 val 是否在 retired list 裡，如果是就從 retired list 移除 (line 28)

/* Attempt to find an empty node to store value, otherwise append a new node.
 * Returns the node containing the newly added value.
 */
hp_t *list_insert_or_append(hp_t **head, uintptr_t ptr)
{
    hp_t *node;
    bool need_alloc = true;

    LIST_ITER (head, node) {
        uintptr_t expected = atomic_load(&node->ptr);
        /* atomic_cas: 判斷 node->ptr 和 expected 是否相等
         * 若相等則回傳 1，反之則回傳 0
         * 如果相同表示該資料已經存在於 hazard pointer 裡，因此不需要創新的空間
         */
        if (expected == 0 && atomic_cas(&node->ptr, &expected, &ptr)) {
            need_alloc = false;
            break;
        }
    }

    if (need_alloc)
        node = list_append(head, ptr);
    return node;
}

/* Allocate a new node with specified value and append to list */
static hp_t *list_append(hp_t **head, uintptr_t ptr)
{
    hp_t *new = calloc(1, sizeof(hp_t));
    if (!new)
        return NULL;

    new->ptr = ptr;
    hp_t *old = atomic_load(head);

    // 將節點加在 linked list 的頭
    do {
        new->next = old;
    } while (!atomic_cas(head, &old, &new));

    return new;
}

函式 list_insert_or_append

• 變數 need_alloc 判斷是否需要建立新的節點
• 對 hazard pointer 的 linked list 進行走訪
• 如果資料已經存在，則不需要新增節點，直接回傳已經存在的節點即可
• 如果不存在則使用函式 list_append 新增節點到 hazard pointer 的 linked list 上-

函式 list_append

• 將新的節點加在 linked list 頭的位置

最後討論函式 drop 的部份

/*
 * 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))
        __builtin_unreachable();
}

函式 drop 主要的功能是將 hazard pointer 裡儲存資料 safe_val 的節點移除

/* Remove a node from the list with the specified value */
bool list_remove(hp_t **head, uintptr_t ptr)
{
    hp_t *node;
    const uintptr_t nullptr = 0;

    LIST_ITER (head, node) {
        uintptr_t expected = atomic_load(&node->ptr);
        // if 如果成立，nullptr 複製到 node->ptr，即移除節點並回傳 true
        if (expected == ptr && atomic_cas(&node->ptr, &expected, &nullptr))
            return true;
    }

    return false;
}

從函式 list_remove 可以得知移除節點的方式是利用巨集函式 atomic_cas ，當 node->ptr 等於 expected 時， nullptr 會複製給 node->ptr

最後總結 reader thread 的執行步驟

1. 取得目標讀取資料的 safe pointer
2. 印出讀取資料
3. 將資料從 hazard pointer 中移除

Writer Thread

以下分析 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 一共執行以下步驟

• 建立新資料的結構
• 將新的資料和舊的資料交換
• 釋放舊的資料

/* Swaps the contents of a shared pointer with a new pointer. The old value will
 * be deallocated by calling the `deallocator` function for the domain, provided
 * when `domain_new` was called. If `flags` is 0, this function will wait
 * until no more references to the old object are held in order to deallocate
 * it. If flags is `DEFER_DEALLOC`, the old object will only be deallocated
 * if there are already no references to it; otherwise the cleanup will be done
 * the next time `cleanup` is called.
 */
void swap(domain_t *dom, uintptr_t *prot_ptr, uintptr_t new_val, int flags)
{
    // new_val 寫進 prot_ptr，並回傳舊的 prot_ptr 給 old_obj
    const uintptr_t old_obj = atomic_exchange(prot_ptr, new_val);
    // 把舊的資料釋放
    cleanup_ptr(dom, old_obj, flags);
}

函式 swap 將新的資料地址 new_val 複製到指標 prot_ptr 所指到的地址，並且釋放原本的資料 old_obj

static void cleanup_ptr(domain_t *dom, uintptr_t ptr, int flags)
{
    if (!list_contains(&dom->pointers, ptr)) { /* deallocate straight away */
        dom->deallocator((void *) ptr);
    } else if (flags & DEFER_DEALLOC) { /* Defer deallocation for later */
        list_insert_or_append(&dom->retired, ptr);
    } else { /* Spin until all readers are done, then deallocate */
        while (list_contains(&dom->pointers, ptr))
            ;
        dom->deallocator((void *) ptr);
    }
}

函式 cleanup_ptr 會根據不同的情況釋放空間

• 直接釋放
• 放進 retired list
• 等待到 reader thread 讀取完畢再釋放

/* Returns 1 if the list currently contains an node with the specified value */
bool list_contains(hp_t **head, uintptr_t ptr)
{
    hp_t *node;
    LIST_ITER (head, node) {
        if (atomic_load(&node->ptr) == ptr)
            return true;
    }
    return false;
}

函式 list_contains 用來判斷 linked list 裡是否包含儲存資料 ptr 的節點

可改進之處