HackMD
2022q1 Homework5 (quiz6)
contributed by < hankluo6 >
測驗 1
程式原理
/**
* @brief Node in the TCB of the thread
*/
typedef struct __node {
unsigned long int tid, tid_copy;
void *ret_val;
struct __node *next;
funcargs_t *fa;
} node_t;
/**
* @brief Singly-linked list of thread control blocks (TCB)
*/
typedef struct {
node_t *head, *tail;
} list_t;
static list_t tid_list;
執行緒的相關資料以 tld_list 連接，其中每個 node 會存有 tld, 執行緒的回傳值 (ret_val) 以及函式的資料 (fa)。
/**
* @brief Create a One One mapped thread
* @param t Reference to the thread
* @param routine Function associated with the thread
* @param arg Arguments to the routine
*/
int thread_create(thread_t *t, void *routine, void *arg)
{
...
node_t *node = list_insert(&tid_list, 0);
funcargs_t *fa = malloc(sizeof(funcargs_t));
fa->f = routine;
fa->arg = arg;
void *thread_stack = alloc_stack(STACK_SZ, GUARD_SZ);
fa->stack = thread_stack;
thread_t tid = clone(wrap, (char *) thread_stack + STACK_SZ + GUARD_SZ,
CLONE_FLAGS, fa, &(node->tid), NULL, &(node->tld));
node->tid_copy = tid;
node->fa = fa;
*t = tid;
return 0;
}
建立執行緒時，會新增一個新的節點放到 tld_list 中，節點的 tld 會被初始化為 0。透過 clone 建立新的執行緒，並將新建立的執行緒資料放到節點中。
其中 CLONG_FLAGS 為設置 child process 與 parent process 共用資源。
而 CLONE_PARENT_SETTID 表示將 child thread ID 設置到 parent_tid 參數上， CLONE_CHILD_CLEARTID 則表示將當 child process 終止時，child_tid 參數上的內容會被清空，且該位址上的 futex 會被喚醒。
CLONE_PARENT_SETTID
Store the child thread ID at the location pointed to by parent_tid (clone()) or cl_args.parent_tid (clone3()) in the parent’s memory.
CLONE_CHILD_CLEARTID
Clear (zero) the child thread ID at the location pointed to by child_tid (clone()) or cl_args.child_tid (clone3()) in child memory when the child exits, and do a wakeup on the futex at that address.
/**
* @brief Function to wait for a specific thread to terminate
* @param t TID of the thread to wait for
* @param guard Size of guard pag
*/
int thread_join(thread_t t, void **retval)
{
spin_acquire(&global_lock);
void *addr = get_tid_addr(&tid_list, t);
if (!addr) {
spin_release(&global_lock);
return ESRCH;
}
if (*((pid_t *) addr) == 0) {
spin_release(&global_lock);
return EINVAL;
}
int ret = 0;
while (*((pid_t *) addr) == t) {
spin_release(&global_lock);
ret = syscall(SYS_futex, addr, FUTEX_WAIT, t, NULL, NULL, 0);
spin_acquire(&global_lock);
}
syscall(SYS_futex, addr, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
if (retval)
*retval = get_node_from_tid(&tid_list, t)->ret_val;
spin_release(&global_lock);
return ret;
}
futex 可以用來檢查 user space 上的特定情況發生，當參數為 FUTEX_WAIT 時，如果 uaddr 與 val 相同，則會進入睡眠；而當參數為 FUTEX_WAKE 時，會喚醒在 uaddr 上最多 val 數量的 futex。
thread_join 必須等待執行緒執行完畢，當執行緒還在執行時，addr 的內容為執行緒的 tld，當執行緒結束時，根據上方 clone 的 CLONE_CHILD_CLEARTID flag，會將 addr 的內容清空。
故 while 迴圈與內部的 system call 會持續等待到執行緒結束才會跳出，並將回傳值回傳。
FUTEX_WAKE 看起來不需要，沒有其他執行緒使用同個空間 addr 在等待 wake up。
/**
* @brief Function to make a thread terminate itself
* @param ret return value of the thread to be available to thread_join()
* @note Implicit call to thread_exit is made by each thread after completing
* the execution of routine
*/
void thread_exit(void *ret)
{
spin_acquire(&global_lock);
void *addr = get_tid_addr(&tid_list, gettid());
if (!addr) {
spin_release(&global_lock);
return;
}
if (ret) {
node_t *node = get_node_from_tid(&tid_list, gettid());
node->ret_val = ret;
}
syscall(SYS_futex, addr, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
spin_release(&global_lock);
kill(SIGINT, gettid());
}
thread_exit 會在 wrap 函式的最後被呼叫，會設置回傳值並將在 thread_join 等待的 futex 喚醒，最後刪除自己本身的 process。
FUTEX_WAKE 這邊看起來也不需要，因為當 child process 結束時，也會喚醒 futex。
測驗 2
程式原理
hash table
void *hashmap_get(hashmap_t *map, const void *key)
{
/* hash to convert key to a bucket index where value would be stored */
uint32_t index = map->hash(key) % map->n_buckets;
/* walk through the linked list nodes to find any matches */
for (hashmap_kv_t *n = map->buckets[index]; n; n = n->next) {
if (map->cmp(n->key, key) == 0)
return n->value;
}
return NULL; /* no matches found */
}
與一般 hash table 一樣，找到對應的 bucket，再遍歷這個 bucket 上的 linked list 找到對應的 node。
bool hashmap_put(hashmap_t *map, const void *key, void *value)
{
if (!map)
return NULL;
/* hash to convert key to a bucket index where value would be stored */
uint32_t bucket_index = map->hash(key) % map->n_buckets;
hashmap_kv_t *kv = NULL, *prev = NULL;
/* known head and next entry to add to the list */
hashmap_kv_t *head = NULL, *next = NULL;
while (true) {
/* copy the head of the list before checking entries for equality */
head = map->buckets[bucket_index];
/* find any existing matches to this key */
prev = NULL;
if (head) {
for (kv = head; kv; kv = kv->next) {
if (map->cmp(key, kv->key) == 0)
break;
prev = kv;
}
}
if (kv) { /* if the key exists, update and return it */
if (!next) /* lazy make the next key-value pair to append */
next = map->create_node(map->opaque, key, value);
/* ensure the linked list's existing node chain persists */
next->next = kv->next;
/* CAS-update the reference in the previous node */
if (prev) {
/* replace this link, assuming it has not changed by another
* thread
*/
if (__atomic_compare_exchange(&prev->next, &kv, &next, false,
__ATOMIC_SEQ_CST,
__ATOMIC_SEQ_CST)) {
/* this node, key and value are never again used by this */
map->destroy_node(map->opaque, kv);
return true;
}
hashmap_put_replace_fail += 1;
} else { /* no previous link, update the head of the list */
/* set the head of the list to be whatever this node points to
* (NULL or other links)
*/
if (__atomic_compare_exchange(&head->next, &kv,
&next, false, __ATOMIC_SEQ_CST,
__ATOMIC_SEQ_CST)) {
map->destroy_node(map->opaque, kv);
return true;
}
/* failure means at least one new entry was added, retry the
* whole match/del process
*/
hashmap_put_head_fail += 1;
}
} else { /* if the key does not exist, try adding it */
if (!next) /* make the next key-value pair to append */
next = map->create_node(map->opaque, key, value);
next->next = NULL;
if (head) /* make sure the reference to existing nodes is kept */
next->next = head;
/* prepend the kv-pair or lazy-make the bucket */
if (__atomic_compare_exchange(&map->buckets[bucket_index], &head,
&next, false, __ATOMIC_SEQ_CST,
__ATOMIC_SEQ_CST)) {
__atomic_fetch_add(&map->length, 1, __ATOMIC_SEQ_CST);
return false;
}
/* failure means another thead updated head before this.
* track the CAS failure for tests -- non-atomic to minimize
* thread contention
*/
hashmap_put_retries += 1;
}
}
}
hashmap_put 首先尋找 key 使否已經在 hash table 當中，next 為新建立的節點，如果新增失敗，則此次迴圈建立的 next 可以在之後的迴圈中使用，不用再重新建立。可以分成各個部分討論：
-
key 已經在 hash table 當中 (Line 28 ~ Line 64)
kv為要被取代的節點。接著依照kv的位置分成兩種情況：-
key 不在第一個節點 (Line 36 ~ Line 48)
則我們要更新
prev->next將next連接上去，故更新程式為：__atomic_compare_exchange(&prev->next, &kv, &next, false,__ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)
-
key 在第一個節點 (Line 48 ~ Line 63)
此情況表示
head[bucket_idx] = kv，我們要更新head->next將next連接上去，故更新程式為：__atomic_compare_exchange(&head->next, &kv, &next, false,__ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)
而被取代的
kv空間必須被釋放，故透過map->destroy_node呼叫釋放函式。 -
-
key 不在 hash table 當中 (Line 64 ~ Line 85)
直接將
next連接到當成新的head，故將next->next設定為head，並更新：__atomic_compare_exchange(&map->buckets[bucket_index], &kv, &next, false,__ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)
bool hashmap_del(hashmap_t *map, const void *key)
{
if (!map)
return false;
uint32_t bucket_index = map->hash(key) % map->n_buckets;
/* try to find a match, loop in case a delete attempt fails */
while (true) {
hashmap_kv_t *match, *prev = NULL;
for (match = map->buckets[bucket_index]; match; match = match->next) {
if ((*map->cmp)(key, match->key) == 0)
break;
prev = match;
}
/* exit if no match was found */
if (!match)
return false;
/* previous means this not the head but a link in the list */
if (prev) { /* try the delete but fail if another thread did delete */
if (__atomic_compare_exchange(&prev->next, &match, &match->next,
false, __ATOMIC_SEQ_CST,
__ATOMIC_SEQ_CST)) {
__atomic_fetch_sub(&map->length, 1, __ATOMIC_SEQ_CST);
map->destroy_node(map->opaque, match);
return true;
}
hashmap_del_fail += 1;
} else { /* no previous link means this needs to leave empty bucket */
/* copy the next link in the list (may be NULL) to the head */
if (__atomic_compare_exchange(&map->buckets[bucket_index], &match,
&match->next, false, __ATOMIC_SEQ_CST,
__ATOMIC_SEQ_CST)) {
__atomic_fetch_sub(&map->length, 1, __ATOMIC_SEQ_CST);
map->destroy_node(map->opaque, match);
return true;
}
/* failure means whole match/del process needs another attempt */
hashmap_del_fail_new_head += 1;
}
}
return false;
}
hashmap_del 與 hashmap_put 類似，根據要被移除的節點位置，透過 __atomic_compare_exchange 將 linked list 更新。
free list
free list 用來存放要被釋放的空間，每個要釋放的空間先以 free_later_t 包裝，其存放該空間以及要釋放該空間的函式，再以 list_node_t 包裝以便可以放置在 free list buffer 當中。
這樣實作可以對每種型態決定其釋放空間的函式，如 hash 的 key 值存在 stack 中，使用 opaque 防止釋放。
但此程式好像沒有正確釋放所有空間，free_later_run 並不會進到迴圈中。
後續實作: hashmap，請將你的改進以 pull request 提交。
jservImage Not Showing Possible ReasonsLearn More →
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
實作缺失
-
程式有時後會卡住
test_del會呼叫mt_del_vals，其中N_THREADS呼叫add_val增加相同資料到map當中，另外N_THREADS呼叫del_val將資料移除，有第三群N_THREADS會呼叫mt_add_vals插入不同的資料到map當中。當資料從
map移除時 atomic operation 沒有失敗，hashmap_del_fail或hashmap_del_fail_new_head為 0 時，會再重新重複上述步驟。導致程式執行時，會在
while迴圈中重複操作，此情況在搭配 Debugger 或 Valgrind 等工具時更明顯。不確定
hashmap_del_fail的hashmap_del_fail_new_head用途。 -
Memory Leak
程式有多處分配的記憶體沒有釋放。Commit
-
hashmap.c- hashmap 在建立後沒有釋放空間，新增
hashmap_free將 hashmap 釋放，並把剩下的節點放到 free list 中。
void hashmap_free(hashmap_t *map) { for (int bucket = 0; bucket < map->n_buckets; ++bucket) { for (hashmap_kv_t *kv = map->buckets[bucket]; kv; kv = kv->next) { map->destroy_node(map->opaque, kv); } } free(map->buckets); free(map); } - hashmap 在建立後沒有釋放空間，新增
-
free_later.c- 原本
free_later_run在釋放時會讀取到已經釋放的節點，且當 free function 為NULL時，v->free會觸發 segmentation fault，改為釋放前一個節點。
- for (list_node_t *n = buffer_prev->head; n; n = n->next) { + for (list_node_t *n = buffer_prev->head, *prev = NULL; n;) { + prev = n; + n = n->next; - free_later_t *v = n->val; + free_later_t *v = prev->val; + if (v->free) free_later_t *v = n->val; + v->free(v->var); - free(n); + free(prev); }free_later_stage會將buffer的內容給buffer_prev，並新增一個新的buffer，在之後的free_later_run便能將buffer_prev的內容釋放，但原本程式的free_later_stage並不會將內容賦值給buffer_prev。
void free_later_stage(void) { ... - if (!buffer_prev || buffer_prev->length == 0) { + if (buffer_prev) { release_lock(&lock); return; } ... } - 原本
-
