Try   HackMD

Linux 核心設計/實作 (Spring 2023)

作業要求

2023q1 Homework1 (作業區)
L01: lab0

  • 在 GitHub 上 fork lab0-c
  • 著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 $ make test 自動評分系統的所有項目。
  • 研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
  • 確保 qtest 提供的 web 命令得以搭配上述佇列實作使用，目前一旦網頁伺服器啟動後，原本處理命令列操作的 linenoise 套件就無法使用，請提出改善機制
  • 在 qtest 提供新的命令 shuffle，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作，需要以統計的原理來分析你的實作，探究洗牌的「亂度」
  • 在 qtest 中執行 option entropy 1 並搭配 ih RAND 10 一類的命令，觀察亂數字串的分布，並運用「資訊與熵互補，資訊就是負熵」的觀念，設計一組新的命令或選項，得以在 qtest 切換不同的 PRNG 的實作 (可選定 Xorshift)，搭配統計分析工具，比較亂數產生器 (如 Xorshift vs. 內建) 的品質
  • 研讀論文〈Dude, is my code constant time?〉，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student's t-distribution 及程式實作的原理。
  • 指出現有程式的缺陷或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request

開發環境

$ 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:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  4
  On-line CPU(s) list:   0-3
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-4460  CPU @ 3.20GHz
    CPU family:          6
    Model:               60
    Thread(s) per core:  1
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            3
    CPU max MHz:         3400.0000
    CPU min MHz:         800.0000
    BogoMIPS:            6385.16
Caches (sum of all):
  L1d:                   128 KiB (4 instances)
  L1i:                   128 KiB (4 instances)
  L2:                    1 MiB (4 instances)
  L3:                    6 MiB (1 instance)
NUMA:
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-3

開發進度 (53/100)

  • q_new
  • q_free
  • q_insert_head
  • q_insert_tail
  • q_remove_head
  • q_remove_tail
  • q_size

開發過程

q_new

使用 malloc 函式進行記憶體配置，若配置記憶體空間失敗則回傳 NULL ，使用 queue.h 及連帶的 list.h 中所提供的巨集與函式。以 INIT_LIST_HEAD() 取代將 next 和 prev 都指向自身 (head) 的初始化實作。










struct list_head *q_new()
{
    struct list_head *new = malloc(sizeof(struct list_head));
    if (!new)
        return NULL;

    INIT_LIST_HEAD(new);
    return new;
}

q_free

最初以 list.h 中提供的 list_for_each_safe() 來走訪節點，並以q_release_element() 來釋放走訪到的節點，但在編譯時卻產生出 error: passing argument 1 of ‘q_release_element’ from incompatible pointer type 。經檢查後發現 q_release_element() 中的 expected type 應該要為element_t * ，且 struct element_t 才有包含 char 與 *value 的變數宣告。

改進方案: 改以 element_t * 宣告 entry 和 safe ，並且以list_for_each_entry_safe() 取代 list_for_each_safe() 。












void q_free(struct list_head *l)
{
    if (!l)
        return;

    element_t *cur, *safe;
    list_for_each_entry_safe (cur, safe, l, list) {
        q_release_element(cur);
    }
    free(l);
}

q_insert_head

確認 head 是否為空，以及確認 ele 記憶體配置是否成功後，宣告新增字串的長度 (包含\0) 並串接字串 s 。使用 list.h 中提供的 list_add() 將新增的節點加入至串列的 head 。
















bool q_insert_head(struct list_head *head, char *s)
{
    element_t *ele = malloc(sizeof(element_t));
    if (!head || !ele)
        return false;

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

q_insert_tail

以 q_insert_head() 為基礎，僅將 list.h 中提供的 list_add() 改為 list_add_tail() 。
















bool q_insert_tail(struct list_head *head, char *s)
{
    element_t *ele = malloc(sizeof(element_t));
    if (!head || !ele)
        return false;

    ele->value = malloc((strlen(s) + 1) * sizeof(char));
    if (!ele->value) {
        free(ele);
        return false;
    }
    strncpy(ele->value, s, strlen(s) + 1);
    list_add_tail(&ele->list, head);
    return true;
}

q_remove_head

使用 list_first_entry() 取得 queue 中的第一個節點後，以 list_del_init() 來移除找到的第一個節點，並將移除之節點中所包含的字串存於 sp ，最後再回傳這個被移除的節點。














element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *ele = list_first_entry(head, element_t, list);
    list_del_init(head->next);
    if (ele && bufsize) {
        strncpy(sp, ele->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return ele;
}

q_remove_tail

以 q_remove_head() 為基礎，僅將 list.h 中提供的 list_first_entry() 改為 list_last_entry() ，即為找到並取得 queue 中的最後一個節點。














element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *ele = list_last_entry(head, element_t, list);
    list_del_init(head->next);
    if (ele && bufsize) {
        strncpy(sp, ele->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return ele;
}

q_size

使用 list_for_each() 來走訪所有的節點，並參照 L01: lab0 來實作此介面。













int q_size(struct list_head *head)
{
    if (!head)
        return 0;

    int len = 0;
    struct list_head *li;

    list_for_each (li, head)
        len++;
    return len;
}

q_delete_mid

參考 你所不知道的 C 語言: linked list 和非連續記憶體 ，並以 Leetcode 2095. Delete the Middle Node of a Linked 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 *cur = head->next;
    struct list_head *fast = head->next;
    while (fast != head && fast->next != head) {
        cur = cur->next;
        fast = fast->next->next;
    }

    list_del(cur);
    q_release_element(list_entry(cur, element_t, list));
    return true;
}

q_delete_dup

走訪每個節點，並檢查每個節點往後至尾端的最後一個節點，檢查節點之中是否存在相同的字串。




















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;

    struct list_head *cur = head->next, *del;
    while (cur->next != head) {
        if (strcmp(list_entry(cur, element_t, list)->value,
                   list_entry(cur->next, element_t, list)->value) == 0) {
            del = cur->next;
            list_del(del);
            q_release_element(list_entry(del, element_t, list));
        } else {
            cur = cur->next;
        }
    }
    return true;
}

預期進度

Last changed by 
 
chien1214
0
265
Published on HackMD