---
tags: linux kernel
---

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

## 開發環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ 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) Xeon(R) CPU E3-1231 v3 @ 3.40GHz
    CPU family:          6
    Model:               60
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            3
    CPU max MHz:         3800.0000
    CPU min MHz:         800.0000
    BogoMIPS:            6784.31

## 開發過程

### q_new

一開始從 `list.h` 中發現了 `LISTHEAD()` 這個巨集，覺得可以透過這一個巨集來定義一個 new list 中的 head ，又因為要能夠回傳，所以寫成 `static LISTHEAD()` ，如下:

struct list_head *q_new()
{   
    static LISTHEAD(head);
    return &head;
}

雖然這樣可以成功的創建一個 new list 的 head ，如下:

$ ./qtest 
cmd> new
l = []

但是仔細思考過後我覺得這個作法的問題是一旦今天需要刪除 head，就會因為 head 是一個 static variable 而不是一個 pointer 導致沒有辦法將其 free 掉，所以我選擇改寫成正常宣告一個 list_head 這個結構的 pointer `head` ，然後透過 `list.h` 中的 `INIT_LIST_HEAD()` 來對 `head` 配置記憶體，如下:

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

### q_free

想法是使用 `list_for_each_entry_safe` 來逐一走訪整個 queue 中的每一個 element，然後透過 `container_of` 來計算每一個 element 的記憶體起始位置，然後將其 free 掉。

void q_free(struct list_head *l)
{   
    element_t *pos, *next;
    list_for_each_entry_safe (pos, next, l, list) {
        free(container_of(&pos->list, element_t, list));
    }
}

但是我忽略了要 free 掉這一個 queue 中的頭 `l` ，所以會導致在做測試的時候會警告

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

而解決方法也很簡單，在上述程式碼的最後補上

free(l);

後來在撰寫其他函式時，用 valgrind 檢查出了

ERROR: Freed queue, but 2 blocks are still allocated
==31258== 42 bytes in 1 blocks are still reachable in loss record 1 of 2
==31258==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==31258==    by 0x10F1FB: test_malloc (harness.c:133)
==31258==    by 0x10F6D2: q_insert_head (queue.c:45)
==31258==    by 0x10CBD2: do_ih (qtest.c:224)
==31258==    by 0x10DEE5: interpret_cmda (console.c:181)
==31258==    by 0x10E49A: interpret_cmd (console.c:201)
==31258==    by 0x10F104: run_console (console.c:691)
==31258==    by 0x10D2D7: main (qtest.c:1227)
==31258== 
==31258== 56 bytes in 1 blocks are still reachable in loss record 2 of 2
==31258==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==31258==    by 0x10F1FB: test_malloc (harness.c:133)
==31258==    by 0x10F5FD: q_new (queue.c:18)
==31258==    by 0x10F6BE: q_insert_head (queue.c:44)
==31258==    by 0x10CBD2: do_ih (qtest.c:224)
==31258==    by 0x10DEE5: interpret_cmda (console.c:181)
==31258==    by 0x10E49A: interpret_cmd (console.c:201)
==31258==    by 0x10F104: run_console (console.c:691)
==31258==    by 0x10D2D7: main (qtest.c:1227)
==31258==

<s>我覺得</s>
:::danger
工程人員說話要精準，你可大膽列出你的推論，隨後證實。避免憑感覺。
:notes: jserv
:::

是因為我在 `q_free` 中只把 `element` 都 `free` 掉，但是沒有把每一個 `element` 中的 member 的記憶體位置也一起 `free` 掉。必須要清乾淨，因為他們也是指標變數或是包含著指標變數的結構體。
仔細看 `queue.h` 中赫然發現有一個已經寫好的 function `q_release_element` 可以直接將整個結構體 `element` 所配置的記憶體空間，包含結構體內的其他結構體和指標變數所指向的記憶體都能一同 free 掉，所以就利用了這個 function 來改寫:

void q_free(struct list_head *l)
{
    if (!l)
        return;
    element_t *pos, *next;
    list_for_each_entry_safe (pos, next, l, list) {
        q_release_element(container_of(&pos->list, element_t, list));
    }
    free(l);
}

### q_insert_head

一開始寫出來的版本忘了配置記憶體空間給要 insert 的 node `n` 的 member `value` ，導致在做測試時會有錯誤跳出來

Need to allocate and copy string for new queue element

解決掉這個失誤的程式碼如下:

bool q_insert_head(struct list_head *head, char *s)
{   
    element_t *n = malloc(1 * sizeof(element_t));
    struct list_head *list = q_new();
    char *value = malloc(1024 * sizeof(char));
    memcpy(value, s, strlen(s) + 1);
    if (head == NULL || s == NULL || n == NULL || list == NULL || value == NULL)
        return false;
    n->list = *list;
    n->value = value;
    list_add(&(n->list), head);
    return true;
}

但又考慮到如果這行敘述成立

if (head == NULL || s == NULL || n == NULL || list == NULL || value == NULL)

應該要將指到 `NULL` 的指標變數 `free` 掉，所以改寫成個別判斷

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

後來使用 valgrind 測試的時候發現也有 memory leak 的問題，仔細觀察後發現我額外宣告並配置了一個 list_head `list`，這是沒有必要的，因為在宣告並配置 element_t `n` 時其 memeber 就包含了一個結構體 list_head ，改寫後就解決了 memory leak 的問題。
同時我也精簡了程式碼，因為不需要去 free 那些指向 NULL 的指標變數。

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

:::warning
列出程式碼變更之處 (善用 `diff`)，不用張貼完整程式碼。
:notes: jserv
:::
:::danger
上述程式碼在 `element_t *n` 成功配置，但 `char *value` 配置失敗時，會導致配置成功的 `element_t *n` 之記憶體沒有被釋放。
應改為:

element_t *n = malloc(1 * sizeof(element_t));
if (!n)
    return false;
char *value = malloc((strlen(s) + 1) * sizeof(char));
if (!value)
    free(n);
    return false;

:notes: qwe661234
:::
## q_insert_tail

函式運作的邏輯和 `q_insert_head` 幾乎一樣，唯一的差別是將原先的

list_add(&n->list, head);

改成

list_add_tail(&n->list, head);

但是這樣會發現這兩個函式的程式碼幾乎相同，所以可以將相同的部份提出來成為一個新的函式提供給 `q_insert_head` 和 `q_insert_tail` 使用，或是使用巨集來展開，這會是我在完成這份作業後可以<s>優化</s> -- 的地方。
:::warning
這裡不是 optimize 的意思，僅為 improve，請查閱英英字典，理解二個詞彙的落差。
:notes: jserv

- [Optimize](https://dictionary.cambridge.org/dictionary/english/optimize)
> to make something as good as possible.
- [Improve](https://dictionary.cambridge.org/dictionary/english/improve)
> to (cause something to) get better.

我想老師的意思是要慎用 **優化** 這個單詞，在這裡使用 **改善** 才能表達正確的意思。
:::

## q_remove_head

`strncpy`, `snprintf` 和 `strlcpy` 的差異。因為 `strcpy` 會存在潛在的 buffer overflow 的問題，所以應該用 `strncpy` 來限制寫入的位元組的大小。但是 `strncpy` 也並非是安全的，因為有可能會發生 `dest` 字串的結尾並沒有 null terminator 的問題，所以有了更安全的 `strlcpy` 能選擇。`strlcpy` 如果遇到寫入的位元組大小比 `src` 的位元組大小還要小的時候，會在欲寫入的位元組大小的最後一個位元填入 null terminator 。但是因為這需要安裝額外的 package 才能 include `bsd/string.h`，所以我選擇使用 `snprintf` 來達到一樣的效果。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *tmp = list_first_entry(head, element_t, list);
    list_del_init(&tmp->list);
    if (sp)
        snprintf(sp, bufsize, "%s", tmp->value);
    return tmp;
}

## q_remove_tail

函式運作的邏輯和 `q_remove_head` 幾乎一樣，唯一的差別是將原先的

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

改成

element_t *tmp = list_last_entry(head, element_t, list);

同樣可以發現兩個函式的程式碼幾乎相同，<s>所以改善程式碼的部份會列入我的 TODO List 中。</s>
:::warning
闡述接下來要怎麼修改程式碼，細節！
:notes: jserv
:::

## q_delete_mid

想法是透過一個型別為 `list_head` 的指標變數 `tmp` 和一個 <s>會在 true 和 false 反覆震盪的</s> 布林變數 `flag`，在逐一走訪 `queue` 中的每一個 entry 時，每當 `flag` 為 true 時將 `tmp` 指向其下一個 entry 的 list。這樣當走訪完整個 `queue` 後 `tmp` 就會指向 `queue` 的第 $⌊n / 2⌋$ 個 entry，然後再將其刪除。
:::warning
查閱教育部辭典「[震盪](https://dict.revised.moe.edu.tw/dictView.jsp?ID=116768)」:震動擺盪，不安定

作為 `bool` 型態的變數，只能在 0 和 1 之間變化，而非「震盪」，注意用語。
:notes: jserv
:::

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;
    bool flag = true;
    element_t *pos;
    struct list_head *tmp = head;
    list_for_each_entry (pos, head, list) {
        if (flag)
            tmp = tmp->next;
        flag = !flag;
    }
    element_t *mid = list_entry(tmp, element_t, list);
    list_del_init(&mid->list);
    q_release_element(mid);
    return true;
}

但是這一段程式碼還有改善的空間。能改善的點在於

if (flag)
    tmp = tmp->next;

因為這一行敘述被翻譯成組合語言時會產生一次分支指令。而能避免產生分支指令的做法是透過一組快慢指標來達成相同的功能，這會列入我的 TODO List 中。