2022q1 Homework1 (lab0)

contributed by < jasperlin1996 >

作業要求

實驗環境

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   46 bits physical, 48 bits virtual
CPU(s):                          64
On-line CPU(s) list:             0-63
Thread(s) per core:              2
Core(s) per socket:              16
Socket(s):                       2
NUMA node(s):                    2
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           85
Model name:                      Intel(R) Xeon(R) Gold 5218 CPU @ 2.30GHz
Stepping:                        7
CPU MHz:                         1000.011
CPU max MHz:                     3900.0000
CPU min MHz:                     1000.0000
BogoMIPS:                        4600.00
Virtualization:                  VT-x
L1d cache:                       1 MiB
L1i cache:                       1 MiB
L2 cache:                        32 MiB
L3 cache:                        44 MiB
NUMA node0 CPU(s):               0-15,32-47
NUMA node1 CPU(s):               16-31,48-63

開發過程

q_new

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

    return head;
}

q_free

原本在實作過程中沒有想清楚 free 該釋放哪些指標的記憶體導致會跳出 0xdeadbeef 或是 Null pointer dereference 之錯誤，經修正後程式碼如下:

void q_free(struct list_head *l)
{
    if (l == NULL)
        return;
    struct list_head *node = l->next;

    while (!list_empty(l)) {
        struct list_head *tmp = node;
        node = node->next;
        list_del(tmp);
        q_release_element(list_entry(tmp, element_t, list));
    }
    free(l);
}

q_insert_head

初版程式如下，但 Cppcheck 靜態分析工具提示會有 Memory Leak 的問題

bool q_insert_head(struct list_head *head, char *s)
{
    /*
     * Consider the following two situation:
     *     (1) head == NULL or head->prev == NULL or head->next == NULL
     *     (2) head != NULL
     * For the (1) situation, just simply return false.
     * For the (2) situation, since the initialized list_head pointer's
     * prev was pointed to the list_head pointer itself, we can finish the
     * insertion via `list_add` API.
     */

    // If the queue is NULL or uninitialized
    if (!head || !(head->prev) || !(head->next))
        return false;

    // Create a node
    element_t *node = (element_t *) malloc(1 * sizeof(element_t));
    if (node == NULL)
        return false;
    // Calculate the length of s then copy it into the node
    size_t len_s = strlen(s) + 1;
    node->value = (char *) malloc(len_s * sizeof(char));
    if (node->value == NULL) {
        free(node);
        return false;
    }
    strncpy(node->value, s, len_s);

    // Linux Kernel style API, create a struct list_head variable
    LIST_HEAD(list);
    node->list = list;
    // Linux Kernel style API, add the node before the head
    list_add(&(node->list), head);
    return true;
}

錯誤訊息如下：

$ cppcheck queue.c
Checking queue.c ...
Checking queue.c: INTERNAL...
queue.c:97:5: error: Memory leak: node [memleak]
    return true;
    ^
Checking queue.c: LIST_POISONING...
Checking queue.c: __GNUC__...

此問題導致在 git commit 前的 pre-commit hook 檢查失敗，根據提示發現問題出在 node 未被釋放，但理論上本實作應在 q_free 函式釋放關於該 linked list 的記憶體。

原本一開始對這個問題的解法並沒有頭緒，後來在觀摩多位去年同學的實作後看到有人將 malloc 函式部分獨立出一個 function，我認為這樣做的原意應該是因為 q_insert_head 與 q_insert_tail 在新增節點 (node) 部分有相似的程式，因此獨立出來，但我同時也很好奇為什麼這樣有辦法通過 Cppcheck 的檢查。因此我也嘗試將 malloc 部分獨立出一個 function：

element_t *create_node(void)
{
    return (element_t *) malloc(sizeof(element_t));
}

之後即通過 Cppcheck 的測試。
後來在 Facebook 社團討論發現有人將 list_add(&(node->list), head); 改成 list_add(&node->list, head); 也能通過測試，此部分我認為的確算是有可能造成 Memory Leak 的問題，但卻能通過不同的方法 Bypass，其實的確算是一種 Bug，預計在近期回報此問題給 Cppcheck。

而當我實作到 q_remove_head 與 q_remove_tail 時因為遇到了另一個問題才發現可以手動 suppress cppcheck error，我認為遇到此種狀況時的確應該手動以 Comment Suppression 的方法解決此問題。

我同時也注意到，strlen 在遇到 truncated string 的時候可能會花費大量時間並且回傳一個錯誤的值，因此改用 strnlen 並限制輸入之字串最長只能到 1024 個字元長。

最後實作程式如下：

bool q_insert_head(struct list_head *head, char *s)
{
    /*
     * Consider the following two situation:
     *     (1) head == NULL or head->prev == NULL or head->next == NULL
     *     (2) head != NULL
     * For the (1) situation, just simply return false.
     * For the (2) situation, since the initialized list_head pointer's
     * prev was pointed to the list_head pointer itself, we can finish the
     * insertion via `list_add` API.
     */

    // If the queue is NULL or uninitialized
    if (!head || !(head->prev) || !(head->next))
        return false;

    // Create a node
    // element_t *node = (element_t *) malloc(1 * sizeof(element_t));
    element_t *node = create_node();
    if (node == NULL)
        return false;
    // Calculate the length of s then copy it into the node
    // Maximum length of the string is 1024 (excluding '\0')
    size_t len_s = strnlen(s, 1024) + 1;
    node->value = (char *) malloc(len_s * sizeof(char));
    if (node->value == NULL) {
        free(node);
        return false;
    }
    strncpy(node->value, s, len_s);

    // Linux Kernel style API, create a struct list_head variable
    LIST_HEAD(list);
    node->list = list;
    // Linux Kernel style API, add the node before the head
    list_add(&(node->list), head);
    return true;
}

q_insert_tail

程式碼如下，遇到的問題大致與 q_insert_head 相同，主要差異為將 list_add 改成 list_add_tail。

bool q_insert_tail(struct list_head *head, char *s)
{
    // If the queue is NULL or uninitialized
    if (!head || !(head->prev) || !(head->next))
        return false;

    // Create a node
    // element_t *node = (element_t *) malloc(1 * sizeof(element_t));
    element_t *node = create_node();
    if (node == NULL)
        return false;
    // Calculate the length of s then copy it into the node
    // Maximum length of the string is 1024 (excluding '\0')
    size_t len_s = strnlen(s, 1024) + 1;
    node->value = (char *) malloc(len_s * sizeof(char));
    if (node->value == NULL) {
        free(node);
        return false;
    }
    strncpy(node->value, s, len_s);

    // Linux Kernel style API, create a struct list_head variable
    LIST_HEAD(list);
    node->list = list;
    // Linux Kernel style API, append the node at the tail of the queue
    list_add_tail(&node->list, head);
    return true;
}

q_remove_head

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || head->next == head)
        return NULL;
    element_t *ret_p = list_entry(head->next, element_t, list);

    list_del(head->next);
    if (sp) {
        strncpy(sp, ret_p->value, bufsize);
        // Credit to @laneser's note
        sp[bufsize - 1] = '\0';
    }
    return ret_p;
}

實作過程中，根據註解要求在 sp 不為 NULL 時複製資料過去，但沒想清楚，將判斷式寫成 if (!sp)，且在改成 if (sp != NULL) 時問題就消失了。原以為是 Cppcheck 的問題，後來才想到應該是我自己犯蠢。

後來又發現在 trace-08-robust 測試中會出錯，在 queue 為空時，q_remove_head & q_remove_tail 並不會回傳 NULL，因此增加判斷 head->next 是否與 head 一樣，也就是是否沒有任何 node 在 linked-list 內。

在 trace-07-robust 中，關於 truncated string 的問題我想了蠻久一直無法解決，後來在觀摩 @laneser 的筆記 後發現我的盲點，非常感謝他。

Cppcheck: Null pointer dereference

順利完成其他部分程式後，又遇到靜態檢查問題，錯誤訊息如下：

$ cppcheck queue.c
Checking queue.c ...
Checking queue.c: INTERNAL...
Checking queue.c: LIST_POISONING...
Checking queue.c: __GNUC__...
queue.c:43:27: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
        q_release_element(list_entry(tmp, element_t, list));
                          ^
queue.c:155:24: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
    element_t *ret_p = list_entry(head->next, element_t, list);
                       ^
queue.c:176:24: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
    element_t *ret_p = list_entry(head->prev, element_t, list);
                       ^
queue.c:233:23: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
    q_release_element(list_entry(tmp, element_t, list));
                      ^

訊息顯示為有 Null pointer dereference 的情況發生，在詳細 trace code 之後發現，問題如下：

1. 呼叫 list_entry macro
2. list_entry 為 container_of 之包裝
3. container_of 中有段程式碼如下：

__typeof__(((type *)0)->member) ...

而 Cppcheck 在檢查時發現 0 轉型成 type pointer 後為 Null pointer。之後在 Facebook 討論區也有發現有同學遇到同樣的問題，在此引用我自己在討論區的回覆：

這邊是因為 list.h 中 container_of 的實作中，有一行是 __typeof__(((type *) 0)->member) 而 (type *) 0 的確是 null pointer。不過這邊的用法是為了取得 member 的 type，且這個用法是符合 ANSI C 的標準的，詳細的說明可以看這篇：https://stackoverflow.com/questions/13723422/why-this-0-in-type0-member-in-c
以及規格書的第 6.3.2 章關於 pointer 的說明：http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf
jasperlin1996

這邊的問題因為主要發生在 list.h 而我們是無法修改 list.h 的程式碼的，因此也無法在對應的地方加上 comment suppression，後來在與 @jserv 老師討論後建議我可以直接修改 pre-commit.hook 並提交 pull Request #67 到作業專案。這次的 PR 算是我第一次不只是回報 bug 而是參與專案的進展，雖然實際上只改了兩行程式碼，但整個過程比我想像的繁瑣許多，例如：專案開發者可能會要求你對於問題發生的版本提出驗證資料；或是實際上 PR 所包含的程式雖然能解決問題但可能會造成其他困擾。

PR 紀錄

• PR Link: https://github.com/sysprog21/lab0-c/pull/67
• 本次 PR 主要想解決的問題是：Cppcheck 因 list.h 而跳出的 Null pointer dereference 誤報。
• 主要解決方法：詳見 PR 之 file changes (https://github.com/sysprog21/lab0-c/pull/67/files)

為了測試此問題發生之 Cppcheck 版本，我從 Cppcheck 的 GitHub 抓了一份 source code 下來，直接 compile 並測試。因為怕弄壞現有環境，且本次實驗不需考慮效能，因此我以 Docker 製作測試用環境。
以下是測試用之 Dockerfile：

FROM ubuntu:20.04

MAINTAINER jasperlin1996

ENV TZ=Asia/Taipei

RUN ln -snf "/usr/share/zoneinfo/$TZ" /etc/localtime
RUN echo "$TZ" > /etc/timezone

RUN apt update && apt install -y \
    vim     \
    g++     \
    make    \
    cmake   \
    git

RUN git clone https://github.com/danmar/cppcheck.git
RUN git clone https://github.com/sysprog21/lab0-c.git

測試用的程式片段：

#include "lab0-c/queue.h"

int main() {
    struct list_head *head = {&head, &head};
    element_t node = {"Testing\n", head};
    list_entry(head, element_t, list);
    return 0;
}

因為將每個要求的版本（from v1.9 to v2.7）逐一編譯並記錄問題是個有點累的事情，因此我寫了一點 shell script 輔助我完成這件事（或許看起來有點醜，如果有更好的寫法請多指教ＸＤ）。其中 cmake -j32 是因為剛好有足夠的 CPU core 加速 compile，不然真的會等到天荒地老，如果要用本段程式的話記得改成符合你的硬體的參數：

#!/bin/bash
TEST_FILE=/test.c
LOG_PATH=/verify.log

rm $LOG_PATH

cd cppcheck
VERSIONS_STRING=$(git tag -l | tr '\n' ',')
readarray -td, ALL_VERSION <<< "$VERSIONS_STRING,"
unset 'ALL_VERSION[-1]'
unset 'ALL_VERSION[-1]'
declare -p ALL_VERSION

VERSIONS=()
for i in ${!ALL_VERSION[@]}; do
    if [ "${ALL_VERSION[$i]}" == "1.90" ]; then
        START_VERSION=$i
    fi
    if [ "${ALL_VERSION[$i]}" == "2.7" ]; then
        END_VERSION=$i
    fi
done

for i in ${!ALL_VERSION[@]}; do
    if [ $i -eq $START_VERSION ] || [ $i -gt $START_VERSION ]; then
        VERSIONS+=(${ALL_VERSION[$i]})
    fi
done

function build_cppcheck() {
    git checkout $1
    rm -rf build
    mkdir build
    pushd build
    TMP=$(cmake ..)
    if [[ "$TMP" == *"written"* ]]; then
        echo "- CMAKE SETUP SUCCESS"
        echo "- CMAKE BUILDING..."
        cmake --build . -j32 > /dev/null 2>&1
        if [ ! -f "./bin/cfg" ]; then
            cp -r ../cfg/ bin/cfg
        fi
        RESULT=$(./bin/cppcheck $TEST_FILE 2>&1)
        if [[ "$RESULT" == *"error"* ]]; then
            echo "** Cppcheck v$1 failed to pass the test**" >> $LOG_PATH
            echo $RESULT >> $LOG_PATH
        else
            echo "** Cppcheck v$1 passes the test **" >> $LOG_PATH
        fi
    else
           echo "** Cppcheck v$1 failed to compile **" >> $LOG_PATH
    fi
    popd
}

for i in ${VERSIONS[@]}; do
    build_cppcheck $i;
done

實驗後發現，在 Cppcheck v2.1 ~ v2.7 皆會產生此問題（v2.0 無法順利 compile），回報之後再修正 unmatchedSuppression，即完成本次貢獻。

這裡我也提供 Cppcheck 的 Compilation Guide，其實基本上跟 Cppcheck 的 GitHub 上之說明差不多。不過如果你對於從原始碼編譯專案並將執行檔加入你在用的系統的執行目錄這件事不太熟悉的話，可以參考一下，或許會對你有點幫助。

Facebook Infer

Facebook Infer 是由 Facebook（現在可能要叫做 meta）推出的靜態程式碼檢查工具，支援 C/C++/Objective-C 與 Java，在我遇到第一個 Cppcheck issue 時， @jserv 老師有提到可以嘗試使用本工具代替 Cppcheck。

經過了一點小實驗後我稍微有了一點心得，但礙於時間關係，教學待補，我可能得先寫畢業論文QQ。

q_delete_mid

這裡參考 你所不知道的 C 語言: linked list 和非連續記憶體 中所提到的快慢指標技巧，並稍做修改以符合 doublly-linked-list 的需求（應用 Linux Kernel style API）並適當刪除節點，處理不需要的記憶體空間。

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 **indirect = &(head->next);
    for (struct list_head *fast = head->next;
         fast != head && fast->next != head; fast = fast->next->next) {
        indirect = &(*indirect)->next;
    }
    struct list_head *tmp = *indirect;
    list_del(tmp);
    q_release_element(list_entry(tmp, element_t, list));

    return true;
}

q_reverse

我的基本想法是，將 linked-list 中的每個 node 所指向的 prev & next 對調的話，那就等於是做了 reverse 這個操作了。實作的程式碼如下：

void q_reverse(struct list_head *head)
{
    if (!head || head->next == head)
        return;
    struct list_head *node = head;
    // Swap all node's next and prev pointer
    do {
        struct list_head *tmp = node->next;
        node->next = node->prev;
        node->prev = tmp;

        node = node->prev;
    } while (node != head);
}

q_swap

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head)
        return;
    struct list_head *node;
    for (node = head->next; node != head && node->next != head;
         node = node->next) {
        struct list_head *tmp = node->next;
        list_move(node, tmp);
    }
}

本函式之概念不難，重點是要想清楚 pointer 之間要如何連接。思考過後我用純 pointer 實作了一次，之後發現 swap 可以用以下程式即可將 node 移動到 position 後：

list_del(node);
list_add(node, position);

之後又發現，有個 list_move 已經是這兩個 API 的包裝了，因此可以直接使用它。

q_sort

此 function 以 merge sort 的 recursive 版本實作 linked-list 排序功能。
首先以快慢指標找到 linked-list 的中間點，並以該點為分界(不包含)，建立一個新的 linked-list。得到左右兩邊後以 recursive call 方式將兩邊各自排序好，再透過 merge_two_list 合併兩個 list。

void q_sort(struct list_head *head)
{
    if (!head || head->next == head || list_is_singular(head))
        return;
    struct list_head *slow = head->next, *fast = head->next->next;
    while (fast != head && fast->next != head) {
        slow = slow->next;
        fast = fast->next->next;
    }
    // Now the slow pointer is at the middle
    LIST_HEAD(right);

    // Split the list from the next node of slow pointer
    right.next = slow->next;
    right.next->prev = &right;
    right.prev = head->prev;
    right.prev->next = &right;

    slow->next = head;
    head->prev = slow;

    q_sort(&right);
    q_sort(head);

    merge_two_list(head, &right);
}

在 merge_two_list function 中，我用 list_for_each_safe 將右邊的 list 中的 node 去和左邊 list 中的當前 node value 進行比較，如果發現右邊的 value 大於或等於左邊的 value 則將左邊當前節點往 next 移動並繼續比較。
如果發現右邊的 value 小於左邊的 value 或是左邊已經是最後一個 node 了，則看最後 value 比較結果將右邊的 node 移動到左邊當前 node 的前面或是後面。

在寫 q_sort 的時候我花了比較久的時間，再加上其他事務繁重，最後趕在截止日期前幾個小時才寫完。歸根究柢發現原因其實是熬夜導致邏輯思考能力下降。今天在寫的時候實際上我只花了一小時不到就找到卡了幾天的問題，比起學到了 merge sort 的實作方法，我想更多的是我更了解自己的身體狀況了。

/*
 * Merge two sorted list to a sorted one
 * Must ensure the left list isn't empty
 */
void merge_two_list(struct list_head *left_head, struct list_head *right_head)
{
    struct list_head *safe, *right, *left = left_head->next;
    // if the left list is empty but the right isn't
    if (left == left_head && right_head->next != right_head) {
        // left_head = right_head;
        list_splice(right_head, left_head);
        return;
    }
    // Put right list's node to left
    list_for_each_safe (right, safe, right_head) {
        element_t *l_node = list_entry(left, element_t, list);
        element_t *r_node = list_entry(right, element_t, list);

        int cmp_result = strcmp(l_node->value, r_node->value);
        // if left value <= right value, move the left pointer to it's next
        while (left->next != left_head && cmp_result <= 0) {
            left = left->next;
            l_node = list_entry(left, element_t, list);
            cmp_result = strcmp(l_node->value, r_node->value);
        }
        list_del(right);
        if (cmp_result > 0)
            list_add_tail(right, left);
        else
            list_add(right, left);
    }
}

q_delete_dup

這邊我的作法是用 q_new 新增一個專門存放 duplicate strings 的 linked-list，在發現字串重複之後就將該 node 從原本的 linked-list 移動到 dup_strs。此方法不僅以一個較直觀的方式處理問題，且因此 function 要求要將 node 刪除，因此最後可以直接使用 q_free 將整個記憶體一次清空。只要 q_free 的實做是完善的，即可確保這個 function 在處理記憶體的問題上不會有問題。

另，原本我想要使用 list_for_each_safe 來替代主要的迴圈，但因為我先用 val 變數去儲存第一個元素的 value，因此我希望這個 for loop 從第二個元素開始執行。可惜 list_for_each_safe 雖然直觀，但若我將開始點從 head 改成 head->next 則也同時會改變結束條件，因此還是決定自己仿照 list_for_each_safe 寫一個允許刪除 node 的迴圈。

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    /* This implementation will gather all duplicate strings then
     * delete them together.
     */
    if (!head || head->next == head)
        return NULL;
    struct list_head *dup_strs = q_new();
    struct list_head *node, *safe;
    char *val = list_entry(head->next, element_t, list)->value;
    for (node = head->next->next, safe = node->next; node != head;
         node = safe, safe = node->next) {
        char *tmp = list_entry(head->next, element_t, list)->value;
        if (strcmp(val, tmp) == 0)
            list_move(node, dup_strs);
        else
            val = tmp;
    }
    q_free(dup_strs);
    return true;
}