2023q1 Homework1 (lab0)

contributed by < Welly0902 >
本作業參考 zeddyuu 同學及 paul90317 同學

注意書寫規範：中英文間用一個半形空白字元區隔。
:notes: jserv

作業要求

• 完成實作 queue.c 所有功能
• make test 取得 100 分
• 研讀 lib/list_sort.c 並將其加入專案中
• 實作新的命令 shuffle
• 完成 entropy 相關命令 / 選項
• 研讀論文〈Dude, is my code constant time?〉並且解釋 Student’s t-distribution 及程式實作的原理
• 使用 Valgrind 排除 qtest 實作的記憶體錯誤
• 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤

環境設置

使用 WSL2 Ubuntu 22.04

• Perf 在 WSL2上使用:
  Perf 在 WSL2上需另外下載WSL2-Linux-Kernel
  再把 /tools/perf make 起來，過程如下:

$ git clone https://github.com/microsoft/WSL2-Linux-Kernel --depth 1
$ cd WSL2-Linux-Kernel/tools/perf
$ make -j8
$ sudo cp perf /usr/local/bin

• 修改 kernel.perf_event_paranoid 的方式:
  在 /etc/sysctl.conf 中加入 kernel.perf_event_paranoid = -1
  修改完成後 sudo sysctl -p 即修改完成

• Perf 測試使用:

$ perf record ./example
$ perf report

開發環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         46 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  20
  On-line CPU(s) list:   0-19
Vendor ID:               GenuineIntel
  Model name:            12th Gen Intel(R) Core(TM) i7-12700
    CPU family:          6
    Model:               151
    Thread(s) per core:  2
    Core(s) per socket:  10
    Socket(s):           1
    Stepping:            2
    BogoMIPS:            4224.00

開發過程

Q: 如何實際檢驗所寫 function 對 queue 的運行狀況?
A: 修改完程式後執行 make 再運用 ./qtest 去模擬各個 function 的運行狀態

目標: 利用 list.h 中定義好的 API

q_new

/* Create an empty queue */
struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(*head));
    if (head)
        INIT_LIST_HEAD(head);
    return head;
}

q_free

/* Free all storage used by queue */
void q_free(struct list_head *l) {
    if (!l || list_empty(l)) {
        free(l);
        return;
    }

    element_t *entry = NULL, *safe = NULL;
    list_for_each_entry_safe (entry, safe, l, list) {
        list_del(&entry->list);
        q_release_element(entry);
    }
    free(l);
}

q_insert_head

/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
    if(!head)
        return false;
    
    element_t *entry = malloc(sizeof(*entry));
    if (!entry)
        return false;

    size_t len = strlen(s) + 1;
    entry->value = malloc(len * sizeof(char));
    if (!entry->value) {
        free(entry);
        return false;
    }
    
    memcpy(entry->value, s, len);
    INIT_LIST_HEAD(&entry->list);
    list_add(&entry->list, head);
    
    return true;
}

q_insert_tail

/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    if(!head)
        return false;
    element_t *entry = malloc(sizeof(*entry));
    if (!entry)
        return false;
    
    size_t len = strlen(s) + 1;
    entry->value = malloc(len * sizeof(char));
    if (!entry->value) {
        free(entry);
        return false;
    }

    memcpy(entry->value, s, len);
    INIT_LIST_HEAD(&entry->list);
    list_add_tail(&entry->list, head);

    return true;
}

q_remove_head

Q: 為何 romove element 需要 return element_t 型態的 pointer?

/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head)) {
        return NULL;
    }
    element_t *element = list_first_entry(head, element_t, list);
    if (sp && bufsize > 0) {
        strncpy(sp, element->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    list_del(&element->list);
    return element;
}

strncpy: 將 source 的前 num 個字元從 source 複製到 destination。
char * strncpy ( char * destination, const char * source, size_t num );
需注意要預留 null terminator \0 的位置。

q_remove_tail

list_first_entry 換成 list_first_entry 即可找到 tail

/* Remove an element from tail of queue */
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head)) {
        return NULL;
    }
    element_t *element = list_last_entry(head, element_t, list);
    if (sp && bufsize > 0) {
        strncpy(sp, element->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    list_del(&element->list);
    return element;
}

q_size

int q_size(struct list_head *head)
{
    if (!head || list_empty(head)){
        return 0;
    }
    int len = 0;

    struct list_head *node;
    list_for_each (node, head) {
        len++;
    }
    return len;
}

q_delete_mid

list_for_each_entry_safe delete 後需要break

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || list_empty(head)){
        return false;
    }
    int half = q_size(head)/2;

    element_t *node, *t;
    int cnt = 0;
    list_for_each_entry_safe(node, t, head, list){
        if (cnt++ == half){
            list_del(&node->list);
            q_release_element(node);
            break;
        }
    }
    
    return true;
}

q_delete_dup

根據 list.h 註解，list_for_each_entry_safe(entry, safe, head, member) 中的 safe 參數為當前節點的下一個節點，先記錄下一個節點的位置以避免在刪除節點時發生錯誤。

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head)){
        return false;
    }
    element_t *node, *t;
    bool flag = false;

    list_for_each_entry_safe(node, t, head, list){
        // head is the start and end of the linked list
        // strcmp = 0 when strings are equal
        if (node->list.next != head && strcmp(node->value, t->value) == 0) {
            list_del(&node->list);
            q_release_element(node);
            flag = true;
        }
        else if (flag) {
            list_del(&node->list);
            q_release_element(node);
            flag = false;
        }
    }
    return true;
}

運用 flag 去紀錄是否重複，以刪除最後一個重複節點。

q_swap

運用 list_move(node, head) ，可以用 list_move(node, node->next) 來達到交換節點的效果。 list_move 會進行兩個動作: list_del 及 list_add ，以下面是意圖來呈現如何交換:

此處再以graphviz改進

list_del(node):

x
n1 <-> n2 <-> n3         n1     n2 <-> n3
|      |           =>    |      |  
node  node->next        node  node->next

list_add 的部分在 list.h 中為:

static inline void list_add(struct list_head *node, struct list_head *head)
{
    struct list_head *next = head->next; //1

    next->prev = node; //2
    node->next = next; //3
    node->prev = head; //4
    head->next = node; //5
}

因此 list_add(node, node->next) 為:

list_add(node, node->next):
n1     n2 <-> n3
|      | 
node  node->next //head

//1//              
               next
               |
n1     n2 <-> n3
|      | 
node  node->next


//2//            

    node->next    next
    |             |
    n2        n1<-n3
    |         |   ^
    |       node  |
    ---------------

//3//            

    node->next     next
    |               |
    n2        n1<->n3 
    |         |     ^
    |       node    |
    -----------------

//4//            

    node->next     next
    |               |
    n2    <-   n1<->n3 
    |         |     ^
    |       node    |
    -----------------
    
//5//            

    node->next     next
    |               |
    n2   <->   n1<->n3 
               |     
             node    
    

由上過程可見，兩個 node 前後 swap了，程式碼為下:

/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head || list_empty(head)){
        return;
    }
    for (struct list_head *node = head->next; node != head && node->next != head;
        node = node->next) {
        list_move(node, node->next);
    }
}

q_reverse

用 list_for_each_safe 走訪每個節點，走訪該節點時從 list 中刪除再加到 head 下一個即可達到 list reverse 的效果。
考量第一個 iteration 不會對 list 造成任何變動，加一個變數 flag 來跳過第一個 iteration。

/* Reverse elements in queue */
void q_reverse(struct list_head *head) {
    if (!head || list_empty(head)) {
        return;
    }
    struct list_head *node, *t;
    bool flag = true;
    list_for_each_safe (node, t, head) {
        if (flag) {flag = false; continue;}
        list_del(node);
        list_add(node, head);
    }
}

q_reverseK

此為每 k 個元素做一次 reverse。可利用上一個 q_reverse 每走過k個元素用 list_cut_position 拆分成剩餘 list 中前方 k 個要 reverse 的，以及後方剩餘還沒做的。再將切出來的前 k 個 cut 用 q_reverse 做 reverse。最後再以 list_splice_init 接到目前 tmp_head 的前方。達成 reverse 的效果。

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || list_empty(head)) {
        return;
    }
    struct list_head *node, *t, *tmp_head = head;
    struct list_head cut;
    INIT_LIST_HEAD(&cut);
    int counter = 0;
    list_for_each_safe (node, t, head) {
        counter++;
        // every k element do reverse
        if (counter == k) {
            list_cut_position(&cut, tmp_head, node);
            q_reverse(&cut);
            list_splice_init(&cut, tmp_head);
            // reset count
            counter = 0;
            // record the start of the list to be dealed with
            tmp_head = t->prev;
        }
    }
    return;
}

q_sort

merge 的部分取兩 list 的節點出來比大小:

static inline void merge(struct list_head *head, struct list_head *l1, struct list_head *l2)
{
    while (!list_empty(l1) && !list_empty(l2)) {
        if (strcmp(list_entry(l1->next, element_t, list)->value, list_entry(l2->next, element_t, list)->value) < 0) {
            list_move_tail(l1->next, head);
        } else {
            list_move_tail(l2->next, head);
        }
    }

    if (!list_empty(l1)) {
        list_splice_tail_init(l1, head);
    } else {
        list_splice_tail_init(l2, head);
    }
}

再來將 input linked list 切分為二後，用前面寫好的 q_sort 排好，再進行 merge:

/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head) {
    if (!head || q_size(head) < 2) {
        return;
    } 
    // split the target linked list to two list for merging
    struct list_head *fast = head, *slow = head;
    do {
        slow = slow->next;
        fast = fast->next->next;
    } while (fast != head && fast->next != head);

    LIST_HEAD(left);
    LIST_HEAD(right);
    list_splice_init(head, &right);
    // get left and right list
    list_cut_position(&left, &right, slow);
    //sort left and right list and ready for merging
    q_sort(&left);
    q_sort(&right);
    // merge
    merge(head, &left, &right);
}

Q: merge function 中初始為何是l1->next，而不是l1?

q_descend

此實作若節點右側有值比他大，則當下點刪除。思路可利用 doubly linked list 雙向的特性，從又往左走訪各節點。以一個變數記錄當下最大，小於即刪除來達到相同效果。

/* Remove every node which has a node with a strictly greater value anywhere to
 * the right side of it */
    
int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head)) {
        return 0;
    }

    element_t *entry = list_entry(head->prev, element_t, list);
    element_t *np = list_entry(entry->list.prev, element_t, list);
    char *curr_max = entry->value;
    while (&entry->list != head) {
        if (strcmp(entry->value, curr_max) < 0) {
            list_del(&entry->list);
            q_release_element(entry);
        } else {
            curr_max = entry->value;
        }
        
        // move the pointer backward
        entry = np;
        np = list_entry(entry->list.prev, element_t, list);
    }

    return q_size(head);
}

q_merge

此實作的 input 為一個 linked list，每個節點連著一個 queue。故透過 while 迴圈每次合成 floor((q_count + 1) / 2) 個 queue。

/* Merge all the queues into one sorted queue, which is in ascending order */
int q_merge(struct list_head *head)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    if (!head || list_empty(head)) {
        return 0;
    }
    int q_count = q_size(head);
    while (q_count > 1) {
        // fast pointer for merging
        struct list_head *fast = head->next; 
        // slow pointer for recording the position for the final result queue list
        struct list_head *slow = head->next;
        for (int i = 0; i < q_count / 2; i++) {
            // create a head for the temp merging list
            LIST_HEAD(temp_head);
            merge(&temp_head, container_of(fast, queue_contex_t, chain)->q, container_of(fast->next, queue_contex_t, chain)->q);

            list_splice_tail(&temp_head, container_of(slow, queue_contex_t, chain)->q);

            fast = fast->next->next;
            slow = slow->next;
        }
        if (q_count & 1)
            list_splice_tail_init(container_of(fast, queue_contex_t, chain)->q, container_of(slow, queue_contex_t, chain)->q);

        q_count = (q_count + 1) / 2;
    }

    return q_size(container_of(head->next, queue_contex_t, chain)->q);
}