2023q1 Homework1 (lab0)

contributed by < 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==

我覺得

工程人員說話要精準，你可大膽列出你的推論，隨後證實。避免憑感覺。

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;
}

列出程式碼變更之處 (善用 diff)，不用張貼完整程式碼。

jserv

上述程式碼在 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;

qwe661234

q_insert_tail

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

list_add(&n->list, head);

改成

list_add_tail(&n->list, head);

但是這樣會發現這兩個函式的程式碼幾乎相同，所以可以將相同的部份提出來成為一個新的函式提供給 q_insert_head 和 q_insert_tail 使用，或是使用巨集來展開，這會是我在完成這份作業後可以優化 – 的地方。

這裡不是 optimize 的意思，僅為 improve，請查閱英英字典，理解二個詞彙的落差。

jserv

• Optimize

  to make something as good as possible.

• 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);

同樣可以發現兩個函式的程式碼幾乎相同，所以改善程式碼的部份會列入我的 TODO List 中。

闡述接下來要怎麼修改程式碼，細節！

jserv

q_delete_mid

想法是透過一個型別為 list_head 的指標變數 tmp 和一個 會在 true 和 false 反覆震盪的 布林變數 flag，在逐一走訪 queue 中的每一個 entry 時，每當 flag 為 true 時將 tmp 指向其下一個 entry 的 list。這樣當走訪完整個 queue 後 tmp 就會指向 queue 的第

$\lfloor n/2\rfloor$ 個 entry，然後再將其刪除。

查閱教育部辭典「震盪」:震動擺盪，不安定

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

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 中。