# Linux 核心專題: 並行程式設計
> 執行人: WeiHongWi

:::success
:question: 提問清單
* ?
:::

## 任務簡述

回顧〈[並行和多執行緒程式設計](https://hackmd.io/@sysprog/concurrency)〉教材，以課程測驗題給定的並行程式碼為基礎，著手改進，並確保以 C11 Atomics 撰寫出正確且有效的程式碼，所有程式碼應當通過 [Thread Sanitizer](https://github.com/google/sanitizers/wiki/ThreadSanitizerCppManual) 的執行時期檢測。

## TODO: Concurrent Hashtable

重做[第 12 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz12)，包含延伸問題。

### 用 C11 atomics 改寫

### 解讀 bsd_queue.c
裡頭包含 4 個資料結構 , 有 singly-linked list 和 tail singly-linked list , queue , tail queue,在 hashtable 裡用到的是 `double linked tail queue` , 這裡就介紹 function

#### TAILQ_ENTRY 和 TAILQ_HEAD

#### TAILQ_FOREACH_SAFE

#### TAILQ_REMOVE

### 解讀 hashtable.c
第一個資料結構為 `ht_item_t` , 其中包含 key 和 value 以及長度 , 且這些 item 用一個 double linked tail queue 去做連接.如以下程式碼:

typedef struct _ht_item {
    uint32_t hash;
    char kbuf[32];
    void *key;
    size_t klen;
    void *data;
    size_t dlen;
    TAILQ_ENTRY(_ht_item) next;
} ht_item_t;

第二個資料結構為 `ht_items_list_t` , 其中包含了 spinlock 和 `ht_item_t` 的 double linked tail queue , 另外也用 double linked tail queue 來連接其他的 `ht_item_list`. 如以下程式碼:

typedef struct _ht_item_list {
    TAILQ_HEAD(, _ht_item) head;
    pthread_spinlock_t lock;
    size_t index;
    TAILQ_ENTRY(_ht_item_list) iterator_next;
} ht_items_list_t;

第三個資料結構則為 `hashtable_t` , 其中也用 **mutex** 去避免競爭 hash table 的問題,加上前面提到屬於 `struct ht_item_list` 的 **spinlock** ,關於如何使用這兩個 lock 來達到並行, 我用 `ht_clear()` 這個函式做範例:

void ht_clear(hashtable_t *table)
{
    ...
    MUTEX_LOCK(table->iterator_lock);
    ...
    TAILQ_FOREACH_SAFE(list, &table->iterator_list->head, iterator_next,
                       tmplist)
    {
        SPIN_LOCK(list->lock);

        ht_item_t *item = NULL;
        ht_item_t *tmp;

        TAILQ_FOREACH_SAFE(item, &list->head, next, tmp)
        {
            ...
        }

        ...
        SPIN_UNLOCK(list->lock);
        SPIN_DESTROY(list->lock);
        free(list);
    }
    MUTEX_UNLOCK(table->iterator_lock);

    ATOMIC_CAS(table->status, HT_STATUS_CLEAR, HT_STATUS_IDLE);
}

在第 6 和第 14 行的 `TAILQ_FOREACH_SAFE()` 用來走訪整個 double linked tail queue

第一個搜尋屬於 `struct ht_iterator_list` 的 TAILQ ,在搜尋前用 `MUTEX_LOCK()`讓其他 thread 的競爭者無法使用

第二個搜尋屬於 `struct ht_items_list` 的 TAILQ , 在搜尋前用 `SPIN_LOCK()`讓其他 thread 的競爭者無法使用.

#### ht_init 和 PRNG 改寫

#### ht_grow_table() 和 internal preallocated bufferpool 改寫

## TODO: MPMC

重做[第 9 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz12)的測驗一，包含延伸問題。