Try   HackMD

2023q1 Homework1 (lab0)

contributed by < visitorckw >

開發環境

$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          12
On-line CPU(s) list:             0-11
Thread(s) per core:              2
Core(s) per socket:              6
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           165
Model name:                      Intel(R) Core(TM) i5-10500 CPU @ 3.10GHz
Stepping:                        3
CPU MHz:                         3100.000
CPU max MHz:                     4500.0000
CPU min MHz:                     800.0000
BogoMIPS:                        6199.99
Virtualization:                  VT-x
L1d cache:                       192 KiB
L1i cache:                       192 KiB
L2 cache:                        1.5 MiB
L3 cache:                        12 MiB
NUMA node0 CPU(s):               0-11

開發過程

Current score: 83/100

q_new

一開始的實作如下:

struct list_head *q_new()
{
    struct list_head *head =
        (struct list_head *) malloc(sizeof(struct list_head));
    if (!head)
        return NULL;
    INIT_LIST_HEAD(head);
    return head;
}

後來想到可以寫得更精簡，當 malloc 配置記憶體成功後，才使用 INIT_LIST_HEAD 巨集。

struct list_head *q_new()
{
    struct list_head *head =
        (struct list_head *) malloc(sizeof(struct list_head));
    if (head)
        INIT_LIST_HEAD(head);
    return head;
}

q_free

使用 list_for_each_entry_safe 巨集逐一釋放每個單元占用的空間。

void q_free(struct list_head *l)
{
    if (!l)
        return;
    element_t *entry;
    element_t *safe;
    list_for_each_entry_safe (entry, safe, l, list) {
        free(entry->value);
        free(entry);
    }
    free(l);
}

q_insert_head

使用 malloc 函式去配置記憶體，若失敗就先用 free 函式釋放記憶體後 return false ，否則利用 list_add macro 來將新的節點加入到 list 之中。

原先採用 strcpy 函式進行字串的複製，但在 git commit 時會遇到以下錯誤:

Dangerous function detected in /home/student1/linux2023/lab0-c/queue.c
90:    strcpy(sp, delNode->value);

因此定義了 strlcpy 巨集，在複製時需指定長度，透過改成 sprintf 函式來實作:

#ifndef strlcpy
#define strlcpy(dst, src, sz) snprintf((dst), (sz), "%s", (src))
#endif

最後完整的 q_insert_head 函式如下:

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *newNode = (element_t *) malloc(sizeof(element_t));
    if (!newNode)
        return false;
    newNode->value = (char *) malloc(sizeof(char) * (strlen(s) + 1));
    if (!newNode->value) {
        free(newNode);
        return false;
    }
    strlcpy(newNode->value, s, strlen(s) + 1);
    list_add(&newNode->list, head);
    return true;
}

q_insert_tail

邏輯與 q_insert_head 函式相同。唯一的不同之處是原先使用 list_add 巨集來完成，這裡是要從尾端加入新節點，因此要改用 list_add_tail 巨集。

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *newNode = (element_t *) malloc(sizeof(element_t));
    if (!newNode)
        return false;
    newNode->value = (char *) malloc(sizeof(char) * (strlen(s) + 1));
    if (!newNode->value) {
        free(newNode);
        return false;
    }
    strlcpy(newNode->value, s, strlen(s) + 1);
    list_add_tail(&newNode->list, head);
    return true;
}

q_remove_head

先用 list_entry macro 抓出將要 remove 的節點，將節點的 value 字串的內容複製給 sp 之後，再用 list_del macro 刪除。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *delNode = list_entry(head->next, element_t, list);
    size_t length = bufsize < strlen(delNode->value) + 1
                        ? bufsize
                        : strlen(delNode->value) + 1;
    strlcpy(sp, delNode->value, length);
    list_del(head->next);
    return delNode;
}

後來發現須要先檢查 sp 的值是否是 NULL，若是 NULL則不應該將字串複製給它。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *delNode = list_entry(head->next, element_t, list);
    size_t length = bufsize < strlen(delNode->value) + 1
                        ? bufsize
                        : strlen(delNode->value) + 1;
    if (sp && bufsize)
        strlcpy(sp, delNode->value, length);
    list_del(head->next);
    return delNode;
}

q_remove_tail

跟 q_remove_head 的邏輯相同，差在要抓的節點是 head->prev。

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *delNode = list_entry(head->prev, element_t, list);
    size_t length = bufsize < strlen(delNode->value) + 1
                        ? bufsize
                        : strlen(delNode->value) + 1;
    strlcpy(sp, delNode->value, length);
    list_del(head->prev);
    return delNode;
}

和 q_remove_head 一樣，後來加入了 sp 是否為 NULL 的檢查機制。

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *delNode = list_entry(head->prev, element_t, list);
    size_t length = bufsize < strlen(delNode->value) + 1
                        ? bufsize
                        : strlen(delNode->value) + 1;
    if (sp && bufsize)
        strlcpy(sp, delNode->value, length);
    list_del(head->prev);
    return delNode;
}

q_size

使用 list_for_each 巨集走訪整個 list 計算節點的數量。











int q_size(struct list_head *head)
{
    if (!head)
        return 0;
    int ctr = 0;
    struct list_head *node;
    list_for_each (node, head)
        ++ctr;
    return ctr;
}

q_delete_mid

慢指標一次移動一格，快指標一次移動兩格。
因此當快指標走完整個 list 時，慢指標的位置會剛好只走了快指標的一半。

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;
    struct list_head *slow = head;
    struct list_head *fast = head;
    while (1) {
        slow = slow->next;
        if (fast->next == head || fast->next->next == head)
            break;
        fast = fast->next->next;
    }
    element_t *delNode = list_entry(slow, element_t, list);
    list_del(slow);
    free(delNode->value);
    free(delNode);
    return true;
}

q_delete_dup

使用 list_for_each 巨集走訪整個鏈結串列。
額外用一個字串 str 來記錄當前節點的 value 字串內容。
並且再另外用一個 while 迴圈來找字串內容相同的元素，並使用 list_del 巨集對節點做 remove 。

  • 待解決的問題: 在執行完 q_delete_dup 過後接著執行 q_free 會產生以下錯誤:
ERROR: There is no queue, but 3 blocks are still allocated

目前猜測是由於刪除時有發生 memory leak 的情形，需用 valgrind 等工具檢查錯誤產生的原因。

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head))
        return true;
    struct list_head *cur;
    list_for_each (cur, head) {
        if (cur->next == head)
            break;
        element_t *L = list_entry(cur, element_t, list);
        element_t *R = list_entry(cur->next, element_t, list);
        if (strcmp(L->value, R->value))
            continue;
        char *str = (char *) malloc(sizeof(char) * (strlen(L->value) + 1));
        strlcpy(str, L->value, strlen(L->value) + 1);
        struct list_head *prev = cur->prev;
        while (prev->next != head) {
            element_t *node = list_entry(prev->next, element_t, list);
            if (strcmp(str, node->value))
                break;
            list_del(prev->next);
            free(node->value);
            free(node);
        }
        cur = prev;
    }
    return true;
}

q_swap

迴圈每次將指標移動兩格，將自身與下一個節點的 value 交換。
交換採用三次 bitwise xor 的技巧。

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    for (struct list_head *cur = head->next; (long int) cur ^ (long int) head;
         cur = cur->next->next) {
        if (cur->next == head)
            return;
        element_t *L = list_entry(cur, element_t, list);
        element_t *R = list_entry(cur->next, element_t, list);
        L->value = (char *) ((long int) L->value ^ (long int) R->value);
        R->value = (char *) ((long int) L->value ^ (long int) R->value);
        L->value = (char *) ((long int) L->value ^ (long int) R->value);
    }
}

撰寫更精簡的程式碼。
:notes: jserv

修正後的程式碼如下，使用 flag 變數來記錄是否跟前一個節點交換 value 。

void q_swap(struct list_head *head)
{
    int flag = 0;
    struct list_head *cur, *safe;
    list_for_each_safe (cur, safe, head) {
        if (flag & 1) {
            element_t *L = list_entry(cur, element_t, list);
            element_t *R = list_entry(cur->prev, element_t, list);
            R->value = (char *) ((long int) L->value ^ (long int) R->value);
            L->value = (char *) ((long int) L->value ^ (long int) R->value);
        }
        flag ^= 1;
    }
}

q_reverse

將所有節點的 next 和 prev 的值交換 ( 須包含 head )。
交換採用 3 次 bitwise xor 的技巧。

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *cur = head;
    do {
        cur->prev =
            (struct list_head *) ((long int) cur->prev ^ (long int) cur->next);
        cur->next =
            (struct list_head *) ((long int) cur->prev ^ (long int) cur->next);
        cur->prev =
            (struct list_head *) ((long int) cur->prev ^ (long int) cur->next);
        cur = cur->prev;
    } while ((long int) cur ^ (long int) head);
}

q_reverseK

將每 k 個拆成一段獨立出來的 list 。
呼叫前面所實作好的 q_reverse 函式之後，再拼接回原本的鏈結串列中。

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    struct list_head *ptr = head;
    struct list_head *cur = head;
    while (1) {
        for (int i = 0; i < k; i++) {
            cur = cur->next;
            if (cur == head)
                break;
        }
        if (cur == head)
            break;
        struct list_head *next = cur->next;
        element_t ele;
        struct list_head *dummy = &(ele.list);
        dummy->next = ptr->next;
        dummy->prev = cur;
        ptr->next->prev = dummy;
        cur->next = dummy;
        q_reverse(dummy);
        ptr->next = dummy->next;
        dummy->next->prev = ptr;
        dummy->prev->next = next;
        next->prev = dummy->prev;
        ptr = cur = dummy->prev;
    }
}

mergeTwoLists

由於實作 q_sort 以及 q_merge 兩個函式時都需要用到合併已排序連結串列的操作。因此額外實作本函式以利後續開發與維護。
合併兩個已經由小到大排序好的 list 合併。
採用 indirect pointer 技巧使程式碼更簡潔易讀。

struct list_head *mergeTwoLists(struct list_head *L1, struct list_head *L2)
{
    struct list_head **ptr = &L1;
    struct list_head *ptr1 = L1->next;
    struct list_head *ptr2 = L2->next;
    while (ptr1 != L1 && ptr2 != L2) {
        element_t *node1 = list_entry(ptr1, element_t, list);
        element_t *node2 = list_entry(ptr2, element_t, list);
        if (strcmp(node1->value, node2->value) < 0) {
            (*ptr)->next = ptr1;
            ptr1->prev = *ptr;
            ptr1 = ptr1->next;
        } else {
            (*ptr)->next = ptr2;
            ptr2->prev = *ptr;
            ptr2 = ptr2->next;
        }
        ptr = &(*ptr)->next;
    }
    while (ptr1 != L1) {
        (*ptr)->next = ptr1;
        ptr1->prev = *ptr;
        ptr1 = ptr1->next;
        ptr = &(*ptr)->next;
    }
    while (ptr2 != L2) {
        (*ptr)->next = ptr2;
        ptr2->prev = *ptr;
        ptr2 = ptr2->next;
        ptr = &(*ptr)->next;
    }
    (*ptr)->next = L1;
    L1->prev = *ptr;
    return L1;
}

q_sort

先利用和前面實作 q_delete_mid 所用到的快慢指針技巧找到將 list 拆分成兩半的位置。然後加入 dummy node 形成兩個獨立的 list。分別 sort 兩個list 之後，再將兩個排序好的 list 利用前面實作的 mergeTwoLists 函式合併。

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *slow = head->next;
    struct list_head *fast = head->next;
    while (fast->next != head && fast->next->next != head) {
        slow = slow->next;
        fast = fast->next->next;
    }
    element_t ele;
    struct list_head *dummy = &(ele.list);
    struct list_head *mid = slow->next;
    struct list_head *last = head->prev;

    mid->prev->next = head;
    head->prev = mid->prev;
    dummy->next = mid;
    dummy->prev = last;
    last->next = dummy;
    mid->prev = dummy;

    q_sort(head);
    q_sort(dummy);
    mergeTwoLists(head, dummy);
}

q_descend

類似於 monotonic stack 的概念，反向迭代整個 list ，並同時記錄當前所遇到最大的 value 。若當前的 value 比過去最大的 value 還要小則利用 list_del 函式來進行 remove 的動作。

int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    char str[50000] = "";  // unsafe for possible larger length
    struct list_head *next;
    for (struct list_head *cur = head->prev; cur != head; cur = next) {
        next = cur->prev;
        element_t *node = list_entry(cur, element_t, list);
        if (strcmp(node->value, str) < 0) {
            list_del(cur);
            free(node->value);
            free(node);
        } else
            strlcpy(str, node->value, 50000);
    }
    return q_size(head);
}

q_merge

採用頭尾兩兩合併的方式，不斷重複直到剩下一個 list 為止。

  • 待解決的問題: 在執行 make test 指令時發現，由於 merge 過後會造成當前指向的 queue 被設為 null 進而導致後續的一串指令都失效。
int q_merge(struct list_head *head)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    if (!head || list_empty(head))
        return 0;
    if (list_is_singular(head))
        return list_entry(head->next, queue_contex_t, chain)->size;
    int queueSize = q_size(head);
    while (queueSize > 1) {
        struct list_head *node;
        list_for_each (node, head) {
            queue_contex_t *que1 = list_entry(node, queue_contex_t, chain);
            queue_contex_t *que2 =
                list_entry(head->prev, queue_contex_t, chain);
            if (que1 == que2)
                break;
            que1->q = mergeTwoLists(que1->q, que2->q);
            que2->q = NULL;
            que2->size = 0;
            list_del(head->prev);
        }
        queueSize = (queueSize + 1) / 2;
    }

    list_entry(head->next, queue_contex_t, chain)->size =
        q_size(list_entry(head->next, queue_contex_t, chain)->q);
    return list_entry(head->next, queue_contex_t, chain)->size;
}

Valgrind 自動檢測

執行 make valgrind 過後，發現多數結果都如下:

==616700== 2,049 bytes in 1 blocks are still reachable in loss record 46 of 47
==616700==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==616700==    by 0x10C0C9: do_remove (qtest.c:373)
==616700==    by 0x10C4B7: do_rh (qtest.c:463)
==616700==    by 0x10E053: interpret_cmda (console.c:181)
==616700==    by 0x10E623: interpret_cmd (console.c:201)
==616700==    by 0x10EA60: cmd_select (console.c:610)
==616700==    by 0x10F36B: run_console (console.c:705)
==616700==    by 0x10D3E0: main (qtest.c:1276)
==616700==

代表檢測到程式結束時，仍然有著還沒被釋放的記憶體，但有指標依然指向它。可能是由於 globla 變數所導致的現象。

q_shuffle

首先在 qtest.c 裡面增加 shuffle 命令:

ADD_COMMAND(shuffle, "Shuffle the queue with Fisher–Yates shuffle algorithm", "");

然後參考其他 do_ 開頭的函式實作 do_shuffle

static bool do_shuffle(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }

    if (!current || !current->q)
        report(3, "Warning: Calling sort on null queue");

    error_check();
    set_noallocate_mode(true);
    if (exception_setup(true))
        q_shuffle(current->q);
    exception_cancel();

    set_noallocate_mode(false);
    q_show(3);
    return !error_check();
}

另外由於 commit hook 不允許更動 queue.h 之中的程式碼，因此另外用一個標頭檔 shuffle.h 並在裡面增加 q_shuffle 函式的宣告





#ifndef SHUFFLE_H
#define SHUFFLE_H
void q_shuffle(struct list_head *head);
#endif

並在 qtest.c 之中引入此標頭檔。

lib/list_sort.c

由於 list_sort.c 程式碼中所引入的標頭檔都是 linux 核心之中的標頭檔，因此需要自己做對應的修改才能順利的執行。

改進漢語描述，注意作業書寫規範。
:notes: jserv

  1. 將 u8 改為 uint8_t
  2. likely 以及 unlikely 巨集是定義在 linux/compiler.h 之中的巨集，因此需要在 list_sort.h 之中自己加入以下程式碼:
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
  1. 需要自己實作比較函式，如下:
int cmp(void *_, const struct list_head *a, const struct list_head *b)
{
    char *strA = list_entry(a, element_t, list)->value;
    char *strB = list_entry(b, element_t, list)->value;
    return strcmp(strA, strB);
}

論文閱讀 - Dude, is my code constant time?

  • 本論文介紹了 dutect 工具，用於評估代碼在特定平台上是否以恆定時間運行，並且不需要對硬體有特別的要求。

  • 方法步驟

    1. Measure execution time
      • 進行測量時，首先需要定義兩種不同的數據類別，一種是固定的數據類別，而另一種是隨機的數據類別。
      • 現代 CPU 提供週期計數器（例如 x86 系列中的 TSC 寄存器，或 ARM 可用的 systick 外設），可用於準確地獲取執行時間測量。
      • 為了最小化環境變化對結果的影響，在進行測量時，每次測量對應一個隨機選擇的輸入數據類別。類別分配和輸入準備任務在測量階段之前執行。
    2. Apply post-processing
      • 在進行統計分析前，應對每個單獨的測量進行一些處理。
      • 典型的時序分佈對較長的執行時間呈正偏斜。這可能是由於測量數據本身的問題，或者是主進程被操作系統或其他外部因素干擾所致。因此可以捨棄大於固定閾值的測量值。
      • 根據應用的統計檢驗方法，可以進行一些高階前處理。
    3. Apply statistical test
      • T 檢定: 可以使用 Welch’s t-test。需要注意的是，當 t 檢定與裁剪預處理結合使用時，不僅測試平均值是否相等，還測試更高階的統計矩，因為裁剪是一種非線性變換。
      • 非參數檢定

  • percentile 處理
    percentile 是論文中步驟二所提及的 cropping 處理，目的是為了去除極值。

Last changed by 
 
visitorckw
0
433
Published on HackMD