Try   HackMD

2023q1 Homework1 (lab0)

contributed by < lorian0738 >

Reviewed by zeddyuu

  • 開發過程中的編譯器不應該是 Visual Studio Code，應該是整合開發環境
  • 有些函式只有部份程式碼，建議可以貼上整段的程式碼再開始說明會比較完整且可讀
  • 快慢指標用圖片說明很好，但建議可以用 Graphviz
  • 完整說明改善程式碼前後的想法差異，很棒
  • 一些部份尚未完成，像洗牌操作以及論文閱讀等等

開發環境

$ 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):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            9
    CPU max MHz:         4200.0000
    CPU min MHz:         800.0000
    BogoMIPS:            7200.00

開發過程

前置作業

檢查 Linux 版本

原本想用 lsb_release 檢查，但是我裝的版本沒有這個指令
因此改用 cat /etc/*-release
得 VERSION_ID="22.04" 確認符合作業需求

github 設定

參照 Git 教學和 GitHub 設定指引 建立 GitHub 帳號與產生 SSH key
建立完公鑰下指令 clip < ~/.ssh/id_rsa.pub 時沒有這個指令
於是用 sudo apt install geomview 下載
然而還是無法取得公鑰
最後輸入 cat ~/.ssh/id_rsa.pub 再複製

(註：
git commit -a 將所有改過的 push 到 GitHub 上 commit 出去建立一個新的 git 版本
git log 看曾經 push commit 過的情況
也可以用 tig 看更詳細的

最後用 git push -u origin master push 到 Github 上）

檢查 cppcheck 版本

指令：cppcheck --version
確認 Cppcheck 2.7 符合規定

取得程式碼

至 lab0-c fork 到自己的GitHub
再照要求 clone 下來 git clone git@github.com:lorian0738/lab0-c

編譯器

使用 Visual studio Code

q_new

建立新的「空」佇列

先要 list_head 的空間，如果沒有要到就 return NULL
並利用 INIT_LIST_HEAD 建立新的佇列將下一個和前一個都指向自己

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));

    if (!head)
        return NULL;

    INIT_LIST_HEAD(head);

    return head;
}

q_free

釋放佇列所佔用的記憶體

判斷若為 NULL 則直接 return，若為 empty則釋放 list_head 佔用的空間
否則利用 list_for_each_entry_safe 和 q_release_element 逐一釋放每個 node 佔用的空間
最後要記得把 head 的空間也釋放掉

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

    if (list_empty(l)) {
        free(l);
        return;
    }

    element_t *entry = NULL, *safe = NULL;
    list_for_each_entry_safe (entry, safe, l, list)
        q_release_element(entry);

    free(l);
}

q_insert_head

在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)

原本的寫法：

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

    entry->value = s;

    list_add(&entry->list, head);

    return true;
}

但發現忘記應該要先複製要加入的字串，否則原本的資料更動的時候會動到entry中儲存的資料，改寫成：

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *element = (element_t *) malloc(sizeof(element_t));
    char *tmp = (char *) malloc(sizeof(char) * (strlen(s) + 1));

    if (!element || !tmp)
        return false;

    strncpy(tmp, s, strlen(s) + 1);
    element->value = tmp;

    list_add(&element->list, head);

    return true;
}

其中直接用 strncpy 複製可確保複製到 buffer 可容納大小且自動在結尾補上 '\0'

後來發現應該要在一開始檢查 queue 是否為 NULL ，因此在最前面補上

    if (head == NULL)
        return false;

且在 make test 時發現有 malloc 的錯誤，檢查後發現目前的程式有可能在要 element_t 的空間時有要到，但是在要字串的空間時失敗回傳false，前面要的空間應該要被釋放掉，應分開判斷是否有要到空間改為如下：

    if (!element)
        return false;

    if (!tmp) {
        free(element);
        return false;
    }

此步將原本 7 blocks are still allocated 降為 4 ( insert_tail 的部份從 9 降到 4 )，但還是有空間沒有釋放，才想到也有可能是前面 element_t 就沒有要到空間了，但繼續做下去才檢查的話有可能後面的字串有要到空間，這時候就會沒有釋放到字串的空間，因此應該換個順序：

    element_t *element = (element_t *) malloc(sizeof(element_t));
    if (!element)
        return false;

    char *tmp = (char *) malloc(sizeof(char) * (strlen(s) + 1));
    if (!tmp) {
        free(element);
        return false;
    }

才解決這個問題

在 commit 的時候原本想寫 Fix malloc failure on insert_head and insert_tail
但 malloc 不合法，必須寫完整的 memory allocation 才可以
改完後超過上限 50 個 characters
因此最後提交 Fix memory allocation failure on insert

q_insert_tail

在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)

和 q_insert_head 差不多，差別在於最後以 list_add_tail 加到最後

    list_add_tail(&element->list, head);

q_remove_head

在佇列開頭 (head) 移去 (remove) 給定的節點

在 queue.h 的檔案中：

 * @head: header of queue
 * @sp: string would be inserted
 * @bufsize: size of the string
 *
 * If sp is non-NULL and an element is removed, copy the removed string to *sp
 * (up to a maximum of bufsize-1 characters, plus a null terminator.)

第二行有點看不懂 sp 是什麼，註解和前面做 insert 時的 s 一樣，但這裡應該沒有要將字串插入，所以有點困惑
但第五行的意思推測是要將移除的字串複製過去

Return: the pointer to element, %NULL if queue is NULL or empty

首先判斷 queue 是否為 NULL 或空

if (!head || list_empty(head))
        return NULL;

接著用 list_first_entry 取出開頭的 entry，
並用　list_del　移走該點

element_t *element = (element_t *) malloc(sizeof(element_t));
element = list_first_entry(head, element_t, list);

list_del(head->next);

最後判斷 sp 是否不是 NULL 以做複製，再回傳 element

if (sp != NULL) {
    strncpy(sp, element->value, bufsize -1);
    sp[bufsize - 1] = '\0';
}

return element;

但後來發現其實 list_del 不會釋放空間，取出開頭時不需要要一個新的空間，應該直接寫成以下就好

element_t *element = list_first_entry(head, element_t, list);

q_remove_tail

在佇列尾端 (tail) 移去 (remove) 給定的節點

作法和 remove_head 差不多，僅改用 list_last_entry 取出最後一個entry，且刪除節點時刪的是 head->prev 也就是最後一點

q_size

計算目前佇列的節點總量

利用 list_for_each 跑過 list 且每跑一個 node 長度就加一

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

移走佇列中間的節點，詳見 LeetCode 2095. Delete the Middle Node of a Linked List

確定 list 不是 NULL 或 empty 後，用前面寫過的 q_size 取得 list 的長度

    int mid = q_size(head) / 2;

接著以 list_for_each_entry_safe 跑 entry 到中間的時候做 delete 和 release

    element_t *entry = NULL, *safe = NULL;
    list_for_each_entry_safe (entry, safe, head, list) {
        if (mid == 0) {
            list_del(&entry->list);
            q_release_element(entry);
            return true;
        }
        mid = mid - 1;
    }

    return false;

q_delete_dup

在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 LeetCode 82. Remove Duplicates from Sorted List II

首先判斷 list 若為 NULL 則回傳 false
而若 list 為 empty 或只有一點，就直接回傳true

    if (!head)
        return false;

    if (list_empty(head) || list_is_singular(head))
        return true;

接著利用 list_for_each_entry_safe 走訪 list，將下一個 entry 的 value 位址紀錄在 tmp，若現在的值和下一個一樣表示需要 release，且紀錄 delete 為 1，這樣走到有重複的最後一個 entry 時才會記得需要 release

而寫到這裡的時候有點混亂，有許多語法上的錯誤，以下紀錄。

原本的寫法 part 1：

    element_t *entry = NULL, *safe = NULL;
    char *tmp = NULL;
    bool delete = 0;
    list_for_each_entry_safe (entry, safe, head, list) {
        if (&entry->list.next == head)
            return true;

當下一個為 head 就直接 return 了，忽略了最後一個 entry 可能跟前面重疊到所以也需要刪除，應該確認 delete 是否為 0 再 return
修正：

        if (entry->list.next == head) {
            if (delete) {
                list_del(&entry->list);
                q_release_element(entry);
                return true;
            } else {
                return true;
            }
        }

原本的寫法 part 2：

        *tmp = container_of(&entry->list.next, element_t, list)->value;
        
        if (strcmp(&entry->value, tmp) == 0) {
            delete = 1;
            list_del(&entry->list);
            q_release_element(entry);
        } else if (delete) {
            delete = 0;
            list_del(&entry->list);
            q_release_element(entry);
        }
    }

    return true;

value 本身就是一個指向字串的指標了
tmp 也是指標，直接用 = 就好
在做字串比較的時候也不需要再取址
修正：

        tmp = container_of(entry->list.next, element_t, list)->value;

        if (strcmp(entry->value, tmp) == 0) {

q_swap

交換佇列中鄰近的節點，詳見 LeetCode 24. Swap Nodes in Pairs

利用 list_for_each_entry_safe 每跑兩個 node 就將該 node 移到前一個的前面

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    element_t *entry = NULL, *safe = NULL;
    bool even = 0;
    list_for_each_entry_safe (entry, safe, head, list) {
        if (even) {
            list_move(&entry->list, entry->list.prev);
        }
        even = !even;
    }
    return;
}

修正：list_move 是把 node 移到指向 node 的後面，所以這樣什麼都不會改動，應該要用 list_move_tail

q_reverse

以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點

在 queue.h 中：

 * This function should not allocate or free any list elements
 * (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).

但 q_remove_head 也沒有 allocate 或 free 所以覺得有點困惑
但總之是要將 list 整個顛倒過來
因此需要將第一個和最後一個對調、第二個和倒數第二個對調…以此類推。

首先判斷 list 若為 NULL 或 empty 或只有一個節點就直接 return
接著用 left 和 right 的指標分別指向第一點、最後一點，並往右、左跑 list
以while迴圈持續交換 left 和 right 指到的點，直到指到同一個點或是相鄰的點

    while (left != right) {
        
        if (left->next == right) {
            list_move(left,right);
            break;
        }
        tmp = left->prev;
        list_move(left,right);
        list_move(right,tmp);
        
        tmp = left->prev;
        left = right->next;
        right = tmp;

    }

q_reverseK

類似 q_reverse，但指定每 k 個節點為一組，進行反向順序排列，詳見 LeetCode 25. Reverse Nodes in k-Group

若 head 為 NULL 或 empty 或只有一個節點或 k 為一就直接 return
接著跑迴圈並紀錄當跑了 k 個節點就需要做 reverse

struct list_head *node = NULL, *safe = NULL;
    struct list_head *left = head->next;
    struct list_head *right;
    struct list_head *tmp;
    int count = 0;
    list_for_each_safe (node, safe, head) {
        count = count + 1;
        if (count == k) {
            count = 0;
            right = node;

            while (left != right) {
                if (left->next == right) {
                    list_move(left, right);
                    break;
                }
                tmp = left->prev;
                list_move(left, right);
                list_move(right, tmp);

                tmp = left->prev;
                left = right->next;
                right = tmp;
            }

            left = safe;
        }
    }

跑完後有可能最後幾個加起來不到 k 個節點的沒有做 reverse 要再把它做完
更新：重看一次題目發現剩餘的不用做，也就是以下不需要

    if (left != head) {
        right = head->prev;

        while (left != right) {
                if (left->next == right) {
                    list_move(left, right);
                    break;
                }
                tmp = left->prev;
                list_move(left, right);
                list_move(right, tmp);

                tmp = left->prev;
                left = right->next;
                right = tmp;
            }
    }

目前的寫法過於冗長，需要再想想更精簡的作法

q_sort

以遞增順序來排序鏈結串列的節點，可參閱 Linked List Sort 得知實作手法

看過文章後選擇用複雜度為 O(nlogn) 的 merge sort 方法實作

原先的想法（有許多錯誤）：

一樣判斷可以直接 return 的狀況，並呼叫 mergesort_list 做 divide and conquer 中 divide 的部份 mergesort_list

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head)) {
        return;
    }
    head = mergesort_list(head);
}

找出中間點並拆成兩個 list，遞迴下去直到拆不了，再呼叫 mergeTwoLists 將兩兩合併

struct list_head *mergesort_list(struct list_head *head)
{
    if (!head || !head->next)
        return head;
    // let right points to midle
    struct list_head *left = head->next;
    struct list_head *right = head->prev;
    while (left != right) {
        if (left->next == right) {
            break;
        }
        left = left->next;
        right = right->prev;
    }

    // cut the link of list
    left->next = NULL;
    head->prev->next = NULL;

    left = mergesort_list(head), right = mergesort_list(right);

    return mergeTwoLists(left, right);
}

參考 案例探討: LeetCode 21. Merge Two Sorted Lists 使用指標的指標的方法
覺得這樣的寫法很不可思議，需要仔細思考並不搞混每個指標指在哪裡
而其中指標類型 uintptr_t 定義在 stdint.h 之中，因此加了標頭檔 #include <stdint.h>

struct list_head *mergeTwoLists(struct list_head *L1, struct list_head *L2)
{
    struct list_head *head = NULL, **ptr = &head, **node;

    for (node = NULL; L1 && L2; *node = (*node)->next) {
        node = strcmp(list_entry(L1, element_t, list)->value,
                      list_entry(L2, element_t, list)->value) < 0
                   ? &L1
                   : &L2;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
    return head;
}

修正：

觀摩同學的做法後發現想法錯誤的地方

  1. 找中間點的方法錯誤：原本想和前面的做法一樣從尾端和開頭開始往中間找中間點，但是在 merge 的過程中只會將next指向正確的下一個節點，而下一個節點的 prev 不會更新到正確的上一個 node，所以不能用這種方法找中間節點，應該要用快慢指標找

    快慢指標（極度陽春版，若有學會如何製作更精美的版本再更新）：


    struct list_head *slow = head;
    for (struct list_head *fast = head; fast && fast->next; fast = fast->next->next)
        slow = slow->next;
    struct list_head *mid = slow;
  1. 沒有串好 circular linked-list：一樣因為過程的 prev 指標都是錯誤的，所以需要在 q_sort 做完 mergesort_list 後更新正確的 prev 指標
    struct list_head *p = head, *n = head->next;
    for(; n != NULL; n = n->next) {
        n -> prev = p;
        p = n;
    }
    p->next = head;
    head->prev = p;
  1. 為遞迴方便，mergesort_list 傳入的 head 應直接指向第一個 node
    head->next = mergesort_list(head->next);

q_descend

參閱 LeetCode 2487. Remove Nodes From Linked List

首先判斷 NULL 或 empty 直接回傳長度為 0
而若只有一個 node 則直接回傳 1

if (!head || list_empty(head)) {
        return 0;
    } else if (list_is_singular(head)) {
        return 1;
    }

因為直接做不好做，可以將 list 做 reverse，接著紀錄沿途遇到的最大值，若在其後有較小的值則刪除，最後再做一次 reverse 即可

    q_reverse(head);

    char *max = list_first_entry(head, element_t, list)->value;

    element_t *entry = NULL, *safe = NULL;
    list_for_each_entry_safe (entry, safe, head, list) {
        if (strcmp(entry->value, max) < 0) {
            list_del(&entry->list);
        } else {
            max = entry->value;
        }
    }

    q_reverse(head);

    return q_size(head);

但 make test 可以發現有錯，訊息：

ERROR: There is no queue, but 4 blocks are still allocated
ERROR: Freed queue, but 4 blocks are still allocated

看起來是需要釋放空間，雖然題目寫的是 remove，於是做完 list_del 之後加了：

    free(entry);

但這樣還是有沒釋放到的空間，發現 entry->value 沒有釋放到，改成以下：

    q_release_element(entry);

q_merge

合併所有已排序的佇列，並合而為一個新的已排序佇列，詳見 LeetCode 23. Merge k Sorted Lists

在 queue.h 中可見關於 q_merge：

 * @head: header of chain

而 chain 被用在 queue_contex_t 中，被用來將許多 queue 的 head 串在一起

/** 
 * queue_contex_t - The context managing a chain of queues
 * @q: pointer to the head of the queue
 * @chain: used by chaining the heads of queues
 * @size: the length of this queue
 * @id: the unique identification number
 */
typedef struct {
    struct list_head *q;
    struct list_head chain;
    int size;
    int id;
} queue_contex_t;

而先前有做過 q_sort，因此先將每個 queue 合在一起，再做 sort 即可

首先若 chain 為 NULL 或 empty 回傳 0
接著原本和上面一樣想著若為 singular 回傳 1，但這裡的 head 指的是 chain 的 head，就算是 singular 也有可能有一串 queue 所以不能這樣寫

    if (!head || list_empty(head)) {
        return 0;
    }

接著以 list_for_each_entry 走訪 chain，將每個 queue 接上第一個 queue
for 迴圈中也是從第一個 entry 開始走，一開始沒有注意到直接做 list_splice_init ，導致重複接了第一個 queue，應該要避免

    queue_contex_t *new_head = list_first_entry(head, queue_contex_t, chain);
    queue_contex_t *entry = NULL;

    list_for_each_entry (entry, head, chain) {
        if (entry == new_head)
            continue;
        list_splice_init(entry->q, new_head->q);
    }

再進行 sort 並回傳大小

    q_sort(new_head->q);

    return q_size(new_head->q);

make test 沒有皮卡丘

目前分數：95/100
constant time 沒有過

以 Valgrind 分析記憶體問題

$ make valgrind

這邊測出
--- TOTAL 100/100

最後兩行：

Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.6Sd6EX --valgrind -t <tid>
Last changed by 
 
lorian0738
0
385

Read more

2023q1 Homework5 (assessment)

2023q1 Homework5 (assessment) contributed by &lt; lorian0738 &gt; 2. 〈因為自動飲料機而延畢的那一年〉的啟發 學期進行到了一半，開始出現了彈性疲乏，在前面的課程與作業積欠累積越來越多的情況下，開始不知道從何補起，有別的事情的時候就會先去做別的事，回神過來已經怠惰逃避很久了，而這次作業其中一項是看這篇文章，看完後有種被激勵到的感覺。 作者為了自己想做的事情選擇延畢，十分熱血，然而創業卻不是一件去做就會成功的事，現在大學已經有許多創業車庫等創業基地鼓勵創業，看過身邊一些朋友投入，但大部分都不了了之，就連獲得了創業資金、企業顧問協助都無法順利運作下去，這其中涉及到了許多團隊管理、技術支援、資金運轉等問題，而作者在做這件時還沒這麼盛行，他們甚至需要自己找資源人脈和資金，印象很深的是資金（連房租）甚至都是其中一名成員打工賺來的。 花費了如此多的時間精力，只看結果或許不是世間認為的「成功」，但是作者那一年多來，對製作自動飲料機的熱忱非常打動人心，遇到問題就去解決，解決不了的問題就尋求專業幫助，不只龜縮在電腦前查資料，更身體力行地到處找朋友、店家、師長了解實際狀況。現實世界不能紙上談兵，許多理論上可行的在實作過後都會出現意想不到的問題，想到大學時期一堂課中也曾經和兩個組員做過肥料定量施放器，人類手做切割出的板子終究會有誤差，最後也沒有到非常精確，看到作者四處去找更良好的工具製作真的很佩服，作者不放棄地實作、修正、再實作、再修正...，正是我需要學習的。

Apr 11, 2023
2023q1 Homework4 (quiz4)

2023q1 Homework4 (quiz4) contributed by &lt; lorian0738 &gt; 紅黑樹 疑問 紅黑樹的移除有許多 Case，但看不懂，或許會有完整程式碼？ 紅黑樹節點為何 struct rb_node 對齊 sizeof(long) 後，指標最低 2 個位元就會沒有使用到？ 小筆記 container_of or rb_entry

Apr 11, 2023
2023q1 Homework3 (fibdrv)

2023q1 Homework3 (fibdrv) contributed by &lt; lorian0738 &gt; 自我檢查清單 [ ] 研讀上述 ==Linux 效能分析的提示== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗; [ ] 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 clz / ctz 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說 [ ] 複習 C 語言 數值系統 和 bitwise operation，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本; [ ] 學習指出針對大數運算的加速運算和縮減記憶體操作成本的舉措，紀錄你的認知和疑惑 [ ] 注意到 fibdrv.c 存在著 DEFINE_MUTEX, mutex_trylock, mutex_init, mutex_unlock, mutex_destroy 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 POSIX Thread 的程式碼來確認。 $\to$ 搭配閱讀〈並行和多執行緒程式設計〉

Mar 21, 2023
2023q1 Homework3 (quiz3)

2023q1 Homework3 (quiz3) contributed by &lt; lorian0738 &gt; 測驗 1 測驗 2 測驗 3 Linear feedback shift register (LFSR) 是指給定前一狀態，將該輸出的線性函數作為輸入的移位暫存器，其應用包括產生 PRNG。考慮一個運用 LFSR 來產生隨機數，並使其均勻分佈於 64 位元無號整數的有效空間 (distribution of uniformly arbitrarily large uint64_t)。 程式碼可參見 bucket_uniform.c (部分程式碼遮蔽): log2_64 : 計算以 2 為底的 x 的對數 (logarithm of x to the base b)，且下取整函數 (floor)

Mar 21, 2023
Read more from lorian0738
Published on HackMD