---
# System prepended metadata

title: 2023q1 Homework1 (lab0)
tags: [Linux核心實作]

---

---
title: 2023q1 Homework1 (lab0)
tags: Linux核心實作
---


# 2023q1 Homework1 (lab0)
contributed by < [`lorian0738`](https://github.com/lorian0738) >


### Reviewed by `zeddyuu`

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


## 開發環境
```bash
$ 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 設定指引](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fgit-with-github#Git-%E6%95%99%E5%AD%B8%E5%92%8C-GitHub-%E8%A8%AD%E5%AE%9A%E6%8C%87%E5%BC%95) 建立 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](https://github.com/sysprog21/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` 建立新的佇列將下一個和前一個都指向自己
```c
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 的空間也釋放掉
```c
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 準則)

原本的寫法：
```c
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中儲存的資料，改寫成：
```c
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 ，因此在最前面補上
```c
    if (head == NULL)
        return false;
```
且在 make test 時發現有 malloc 的錯誤，檢查後發現目前的程式有可能在要 element_t 的空間時有要到，但是在要字串的空間時失敗回傳false，前面要的空間應該要被釋放掉，應分開判斷是否有要到空間改為如下：
```c
    if (!element)
        return false;

    if (!tmp) {
        free(element);
        return false;
    }
```
此步將原本 `7 blocks are still allocated` 降為 4 ( insert_tail 的部份從 9 降到 4 )，但還是有空間沒有釋放，才想到也有可能是前面 element_t 就沒有要到空間了，但繼續做下去才檢查的話有可能後面的字串有要到空間，這時候就會沒有釋放到字串的空間，因此應該換個順序：
```c
    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;
    }
```
才解決這個問題

:::info
在 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` 加到最後
```c
    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 或空
```c
if (!head || list_empty(head))
        return NULL;
```
接著用 `list_first_entry` 取出開頭的 entry，
並用　`list_del`　移走該點
```c
element_t *element = (element_t *) malloc(sizeof(element_t));
element = list_first_entry(head, element_t, list);

list_del(head->next);
```
最後判斷 sp 是否不是 NULL 以做複製，再回傳 element
```c
if (sp != NULL) {
    strncpy(sp, element->value, bufsize -1);
    sp[bufsize - 1] = '\0';
}

return element;
```
但後來發現其實 `list_del` 不會釋放空間，取出開頭時不需要要一個新的空間，應該直接寫成以下就好
```c
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 長度就加一
```c
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](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/)

確定 list 不是 NULL 或 empty 後，用前面寫過的 q_size 取得 list 的長度
```c
    int mid = q_size(head) / 2;
```
接著以 list_for_each_entry_safe 跑 entry 到中間的時候做 delete 和 release 
```c
    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](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)

首先判斷 list 若為 NULL 則回傳 false
而若 list 為 empty 或只有一點，就直接回傳true
```c
    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
修正：
```c
        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 也是指標，直接用 = 就好
在做字串比較的時候也不需要再取址
修正：
```c
        tmp = container_of(entry->list.next, element_t, list)->value;
```
```c
        if (strcmp(entry->value, tmp) == 0) {
```

### q_swap
> 交換佇列中鄰近的節點，詳見 [LeetCode 24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)

利用 list_for_each_entry_safe 每跑兩個 node 就將該 node 移到前一個的前面
```c
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 指到的點，直到指到同一個點或是相鄰的點
```c
    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](https://leetcode.com/problems/reverse-nodes-in-k-group/)

若 head 為 NULL 或 empty 或只有一個節點或 k 為一就直接 return
接著跑迴圈並紀錄當跑了 k 個節點就需要做 reverse　
```c
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 要再把它做完~~
**更新：重看一次題目發現剩餘的不用做，也就是以下不需要**
```c
    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](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法

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

#### 原先的想法（有許多錯誤）：
一樣判斷可以直接 return 的狀況，並呼叫 mergesort_list 做 divide and conquer 中 divide 的部份 `mergesort_list`
```c
void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head)) {
        return;
    }
    head = mergesort_list(head);
}
```
找出中間點並拆成兩個 list，遞迴下去直到拆不了，再呼叫 `mergeTwoLists` 將兩兩合併
```c
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](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists) 使用指標的指標的方法
覺得這樣的寫法很不可思議，需要仔細思考並不搞混每個指標指在哪裡
而其中指標類型 uintptr_t 定義在 stdint.h 之中，因此加了標頭檔 `#include <stdint.h>`
```c
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;
}
```



#### 修正：
> 觀摩[同學的做法](https://hackmd.io/@wanghanchi/linux2023-lab0#q_sort)後發現想法錯誤的地方

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

   快慢指標（極度陽春版，若有學會如何製作更精美的版本再更新）：
   ![](https://i.imgur.com/y85fb0N.jpg)
   ![](https://i.imgur.com/EDDq5pR.jpg)
    
```c
    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;
```

2. 沒有串好 circular linked-list：一樣因為過程的 prev 指標都是錯誤的，所以需要在 q_sort 做完 mergesort_list 後更新正確的 prev 指標
```c
    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;
```
3. 為遞迴方便，mergesort_list 傳入的 head 應直接指向第一個 node
```c
    head->next = mergesort_list(head->next);
```
### q_descend
> 參閱 [LeetCode 2487. Remove Nodes From Linked List](https://leetcode.com/problems/remove-nodes-from-linked-list/)

首先判斷 NULL 或 empty 直接回傳長度為 0
而若只有一個 node 則直接回傳 1
```c
if (!head || list_empty(head)) {
        return 0;
    } else if (list_is_singular(head)) {
        return 1;
    }
```
因為直接做不好做，可以將 list 做 reverse，接著紀錄沿途遇到的最大值，若在其後有較小的值則刪除，最後再做一次 reverse 即可
```c
    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 之後加了：
```c
    free(entry);
```
但這樣還是有沒釋放到的空間，發現 entry->value 沒有釋放到，改成以下：
```c
    q_release_element(entry);
```

### q_merge
> 合併所有已排序的佇列，並合而為一個新的已排序佇列，詳見 [LeetCode 23. Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/)

在 queue.h 中可見關於 q_merge：
```
 * @head: header of chain
```
而 chain 被用在 queue_contex_t 中，被用來將許多 queue 的 head 串在一起
```c
/** 
 * 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 所以不能這樣寫
```c
    if (!head || list_empty(head)) {
        return 0;
    }
```
接著以 list_for_each_entry 走訪 chain，將每個 queue 接上第一個 queue
for 迴圈中也是從第一個 entry 開始走，一開始沒有注意到直接做 `list_splice_init` ，導致重複接了第一個 queue，應該要避免
```c
    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 並回傳大小
```c
    q_sort(new_head->q);

    return q_size(new_head->q);
```
### make test 沒有皮卡丘
目前分數：95/100
constant time 沒有過

## 以 [Valgrind](https://valgrind.org/) 分析記憶體問題

```
$ make valgrind
```
這邊測出
`---     TOTAL           100/100`

最後兩行：
```
Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.6Sd6EX --valgrind -t <tid>
```
