2021q1 Homework1 (lab0)

contributed by < robertlin0401 >

tags: `linux2021`

作業說明

github repository

queue 實作

queue 結構

/* Linked list element */
typedef struct ELE {
    char *value;
    struct ELE *next;
} list_ele_t;

/* Queue structure */
typedef struct {
    list_ele_t *head;
    list_ele_t *tail;
    int size;
} queue_t;

list_ele_t 用於表示 queue 中的元素，其中：
- value 存放字元指標，即 C 語言的字串，此為 queue 中元素的內容
- next 為 list_ele_t 的指標，指向 queue 中的下一個元素
queue_t 用於表示 queue 本身，其中：
- head 為指向 queue 中第一個元素的指標
- tail 為指向 queue 中最後一個元素的指標
- size 紀錄 queue 中元素個數
圖示如下：
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →

queue operations

q_new：建立一個空 queue
q_free：釋放 queue 所占用的記憶體空間，包含其元素內容之字串所使用的空間
q_insert_head：將元素加入 queue 的前端
q_insert_tail：將元素加入 queue 的尾端
q_remove_head：將 queue 最前端的元素移除
q_size：取得 queue 中的元素個數
q_reverse：將 queue 中的元素順序反轉
q_sort：將 queue 中的元素以遞增順序進行排序

以下針對部分 operations 之實作進行詳述：

q_insert_tail










































static inline bool ele_new(char *s, list_ele_t **newh, char **value)
{
    *newh = malloc(sizeof(list_ele_t));
    *value = strdup(s); /* Allocate space for the string and copy it */

    /* If either call to malloc returns NULL */
    if (*newh == NULL || *value == NULL) {
        if (*newh)
            free(*newh);
        if (*value)
            free(*value);
        return false;
    }
    return true;
}

/*
 * Attempt to insert element at tail of queue.
 * Return true if successful.
 * Return false if q is NULL or could not allocate space.
 * Argument s points to the string to be stored.
 */
bool q_insert_tail(queue_t *q, char *s)
{
    if (q == NULL)
        return false;
    list_ele_t *newh;
    char *value;
    if (!ele_new(s, &newh, &value))
        return false;

    /* set up the element and insert at the tail of the queue */
    newh->value = value;
    newh->next = NULL;
    if (q->tail != NULL)
        q->tail->next = newh;
    else
        q->head = newh;
    q->tail = newh;
    q->size++;
    return true;
}

第 35-39 行程式碼實作出將元素 newh 加入 queue 尾端的功能

若 queue_t 內未包含 tail 指標，則該段程式碼須改為以下實作，其中的 while 迴圈將達到

O (n)

的時間複雜度

list_ele_t *tail = q->head;
if (tail != NULL) {
    while (tail->next != NULL)
        tail = tail->next;
    tail->next = newh;
} else
    q->head = newh;

因此，我們需要使用 tail 指標增進程式的效能，以達到
$O (1)$ 時間複雜度

q_size











/*
 * Return number of elements in queue.
 * Return 0 if q is NULL or empty
 */
int q_size(queue_t *q)
{
    if (q == NULL || q->head == NULL)
        return 0;
    else
        return q->size;
}

若 queue_t 內未紀錄 size ，則第 10 行程式碼須改為以下實作來計算 size，其中的 while 迴圈將達到

O (n)

的時間複雜度

{
    int size = 0;
    list_ele_t *ptr = q->head;
    while (ptr != NULL) {
        size++;
        ptr = ptr->next;
    }
    return size;
}

因此，我們需要在 queue_t 紀錄 size 以達到
$O (1)$ 時間複雜度

q_sort

版本一：遞迴式 quick sort

參考 2021 年春季 Linux 核心設計課程 quiz1 quicksort 實作

/*
 * Sort elements of linked list in ascending order using recursive quick sort
 * @param head - a pointer to the pointer to head of the list
 * @param tail - a pointer to the pointer to tail of the list
 */
void q_ele_quicksort(list_ele_t **head, list_ele_t **tail)
{
    if (*head == *tail)
        return;

    list_ele_t *pivot, *left = NULL, *right = NULL;
    list_ele_t *target, *left_end = NULL, *right_end = NULL;
    pivot = *head;
    target = pivot->next;
    pivot->next = NULL;
    while (target != NULL) {
        if (strcmp(target->value, pivot->value) <= 0) {
            if (left == NULL)
                left = target;
            else
                left_end->next = target;
            left_end = target;
            target = target->next;
            left_end->next = NULL;
        } else {
            if (right == NULL)
                right = target;
            else
                right_end->next = target;
            right_end = target;
            target = target->next;
            right_end->next = NULL;
        }
    }

    q_ele_quicksort(&left, &left_end);
    q_ele_quicksort(&right, &right_end);

    if (left != NULL) {
        *head = left;
        left_end->next = pivot;
    } else {
        *head = pivot;
    }
    pivot->next = right;
    *tail = (right_end == NULL) ? pivot : right_end;
}

問題描述：在 trace-15 測資發生 TLE（Time Limit Exceeded）錯誤
推測原因
- 觀察 trace-15 測資可發現，欲排序的 queue 中元素為 [a a a … a b b b … b]（a、b 各 1000000 個），對於 quick sort 而言，此為時間複雜度分析上的 worst case
- 在此 quick sort 實作中，此測資的 partition 如下
- 時間複雜度分析
  - 令
    $n$ 為輸入 queue 的元素個數
  - 左 partition 遞迴的時間複雜度為
    $O (\frac{n}{2} - 1) + O (\frac{n}{2} - 2) + . . . + O (1) = O (n^{2})$ ，右 partition 則為
    $O (\frac{n}{2}) + O (\frac{n}{2} - 1) + . . . + O (1) = O (n^{2})$
  - 總時間複雜度
    $T (n) = O (n^{2}) + O (n^{2}) + c n$ ，
    $c$ 為常數，故
    $T (n) = O (n^{2})$ ，確實為 quick sort 之 worst case 的時間複雜度
- 實際遞迴呼叫行為分析
  - 由圖示可推知，左 partition 遞迴呼叫深度為 999999，右 partition 則為 1000000，最大遞迴深度達到
    $\frac{n}{2}$
  - 每次遞迴需要針對其左、右兩 partition 分別呼叫，所以左、右兩 partition（最上層的）總共向下遞迴呼叫了
    $999999 \times 2 + 1000000 \times 2 = 3999998$ 次，加上最初針對左、右兩 partition 的遞迴呼叫，故總遞迴呼叫次數為
    $4000000$ 次，甚至達到了
    $n$ 的兩倍
  - 綜上分析，在此情況下，quick sort 是極度費時且浪費 stack 空間的方法，故不適合應用於此
如何解決問題
- 根據上述分析可知，我們必須選擇其他排序演算法，以避免在遇到 worst case 的情形下，會耗費特別多資源的問題，意即需要選擇 worst case 之時間複雜度與 best case 是相同的演算法，常見的包含 merge sort、heap sort 與 radix sort
- 接著，我們從輸入字串進行分析，來決定使用何種排序法
  - 首先，可以從 qtest.c 觀察到輸入字串僅由小寫的 a-z 組成，共 26 個字母
```
static const char charset[] = "abcdefghijklmnopqrstuvwxyz";
```
  - 字串的排序邏輯為從第一個字元開始比較，若可以比較出大小，則該字串的大小便以此為依據，反之則比較第二個字元，以此類推
  - 結合上述兩點，我們可以使用 radix sort 的觀念來實作排序
    1. 準備 27 個 buckets，分別表示 26 個字母以及終止字元 '\0'
    2. 從第一個字元開始，每回合取一個字元為依據，依此將字串放入所屬 bucket 中
    3. 檢查各 bucket（除 '\0' 以外），若存在多於一個字串則針對該 bucket 內容進行下一回合的 radix sort
    4. 最後，以 '\0' 的 bucket 最優先，接著按照 a-z 的順序，將字串以 FIFO 順序自 buckets 中取出，取出後的結果便會是排序完成的結果
  - 時間分析
    1. 由於 buckets 數量為一常數，故此排序之時間複雜度僅與需比較之最大字串長度（令
      $k$ ）與輸入字串個數（令
      $n$ ）相關
    2. 又因字串之比較，若發現一字元可比較出大小，則無需比較剩餘字元，故僅在
      $k \geq n$ 且前
      $k - 1$ 個字元皆相同的情況下，其時間複雜度會達到
      $O (n^{2})$ 以上，其餘情況下皆為
      $O (n)$ 的時間複雜度
    就實務上而言，時間複雜度達到
    $O (n^{2})$ 以上的情形是會發生的，但要在
    $n$ 為足夠大的數時，才會構成費時過多的問題，然而實際應用中並不會發生，原因如下：
    1. 若字串用作雜湊值，則因為
      $k$ 位數的 26 個字母之排列組合，共有
      $26^{k}$ 種可能性，因此
      $k$ 取值無需過大即足夠，相對地，在發生時間複雜度達到
      $O (n^{2})$ 以上的情形時，
      $n$ 也不會很大
    2. 若字串為有意義之單詞，則其長度本就受到限制，故同理，
      $n$ 也不會很大

版本二：遞迴式 radix sort

/*
 * Sort elements of linked list in ascending order using recursive radix sort
 * @param head - a pointer to the pointer to head of the list
 * @param tail - a pointer to the pointer to tail of the list
 * @param index - the index of character in string now checking
 */
void q_ele_radixsort(list_ele_t **head, list_ele_t **tail, int index)
{
    if (*head == *tail)
        return;

    list_ele_t *bucket_head[27], *bucket_tail[27];
    list_ele_t *target = *head;
    for (int iter = 0; iter < 27; ++iter)
        bucket_head[iter] = bucket_tail[iter] = NULL;
    
    while (target != NULL) {
        int charCode = (int)(target->value[index]);
        charCode = (charCode == 0) ? 0 : charCode - 'a' + 1;
        if (bucket_head[charCode] == NULL)
            bucket_head[charCode] = target;
        else
            bucket_tail[charCode]->next = target;
        bucket_tail[charCode] = target;
        target = target->next;
        bucket_tail[charCode]->next = NULL;
    }

    for (int iter = 1; iter < 27; ++iter) {
        if (bucket_head[iter] != bucket_tail[iter])
            q_ele_radixsort(&bucket_head[iter], &bucket_tail[iter], index + 1);
    }

    bool isHead = true;
    for (int iter = 0; iter < 27; ++iter) {
        if (bucket_head[iter] != NULL) {
            if (isHead) {
                *head = bucket_head[iter];
                isHead = false;
            } else {
                (*tail)->next = bucket_head[iter];
            }
            *tail = bucket_tail[iter];
        }
    }

}

基於上述 radix sort 討論實作出此 function，經測試後可符合此問題之時間效率需求
是否需更改為非遞迴版本？
- 已知遞迴呼叫會花費較多的資源，故在效率議題上可以考慮將其改為非遞迴版本
- 然而，此實作中之遞迴呼叫次數存在限制，以下說明
  - 每回合之遞迴呼叫最多會有 26 次，即針對 a-z 共 26 個 buckets
  - 每次遞迴呼叫之最大深度即為需比較之最大字串長度（令
    $k$ ）少 1，且上述討論已得到
    $k$ 為有限數之結論
  - 故最大遞迴總次數約為
    $26^{k - 1}$ 次，其發生條件為資料個數達到
    $c \cdot 26^{k - 1}$ 個，
    $1 < c \leq 26$ ，且每層遞迴中，各 bucket 內的資料個數需相近
  - 換言之，此情形之排序意義相似於：排序以 26 個字母任意排列的長度 k 之所有可能字串。而實務上此情況發生時，k 並不會是很大的數
- 綜上所述，在一般情形下並不至於發生如 stack overflow 等問題，因此我暫時選擇使用遞迴版本

版本三：非遞迴式 merge sort

參考：bobhsiao0306 同學的開發紀錄

/*
 * Sort elements of linked list in ascending order using non-recursive merge sort
 * @param q - a pointer to the queue
 */
void q_ele_mergesort(queue_t *q)
{
    for (int i = 1; i < q->size; i *= 2) {
        list_ele_t *ptr = q->head;
        list_ele_t *buf = q->head;
        bool init = true;
        while (ptr != NULL) {
            list_ele_t *a = ptr, *a_tail = NULL;
            for (int j = 0; j < i - 1; j++) {
                if (ptr->next == NULL)
                    break;
                ptr = ptr->next;
            }
            a_tail = ptr;
            ptr = ptr->next;
            list_ele_t *b = ptr, *b_tail = NULL;
            if (ptr != NULL) {
                for (int j = 0; j < i - 1; j++) {
                    if (ptr->next == NULL)
                        break;
                    ptr = ptr->next;
                }
                b_tail = ptr;
                ptr = ptr->next;
            }

            int a_count = 0, b_count = 0;
            while (a_count < i && b_count < i && a != NULL && b != NULL) {
                if (strcmp(a->value, b->value) <= 0) {
                    if (init) {
                        q->head = a;
                        init = false;
                    } else {
                        buf->next = a;
                    }
                    buf = a;
                    a = a->next;
                    a_count++;
                } else {
                    if (init) {
                        q->head = b;
                        init = false;
                    } else {
                        buf->next = b;
                    }
                    buf = b;
                    b = b->next;
                    b_count++;
                }
            }

            if (a_count == i) {
                if (b != NULL) {
                    buf->next = b;
                    buf = b_tail;
                    q->tail = b_tail;
                    q->tail->next = NULL;
                }
            } else {
                if (a != NULL) {
                    buf->next = a;
                    buf = a_tail;
                    q->tail = a_tail;
                    q->tail->next = NULL;
                }
            }
        }
    }
}

觀察其他人的開發紀錄可以發現大部分人是使用 merge sort 進行實作，以上取自 bobhsiao0306 同學的非遞迴式實作並進行簡單改良
接著，我們可以從各項議題上與版本二的 radix sort 相比較
- TODO

修正 `qtest` 之錯誤

運用 Address Sanitizer

問題描述：開啟 Address Sanitizer 後，先執行 qtest，再於命令提示列輸入 help 命令，會產生 global buffer overflow
```
$ make SANITIZER=1
$ ./qtest
cmd> help
```
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
何謂 global buffer overflow？
- 針對全域資料的存取超出合法存取範圍之問題，可能導致未定義行為、程式崩潰，甚至有資訊安全之疑慮
參考：global buffer overflow

觀察問題來源

觀察藍字的錯誤訊息可發現，執行過程中自記憶體位址 0x55e5e09a5400 存取了 4 個位元組
觀察綠字的錯誤訊息可知在該記憶體位址的為一全域變數 echo，其定義之大小為 1 個位元組，因此存取記憶體位址 0x55e5e09a5401 以右的位元組之行為為 overflow，並且在 console.c 的第 59 行可以找到該變數的宣告，其宣告為一 bool 型態的變數

接著從其 traceback 去檢查其使用問題所在

traceback #0 顯示在 do_help_cmd 第 307 行存取 param_list 指向的物件 — plist 之成員時發生錯誤

param_ptr plist = param_list;
report(1, "\t%s\t%d\t%s", plist->name, *plist->valp, 
       plist->documentation);

檢查 param_list 與 echo 之關聯：echo 的指標在 init_cmd 中作為參數，強制轉型為整數指標傳入 add_param，並在 add_param 中賦值給 param_list 中物件之成員 valp 使用

void add_cmd()
{
    ...
    add_param("echo", (int *) &echo, "Do/don't echo commands", NULL);
    ...
}

void add_param(char *name, int *valp, ...)
{
    ...
    param_ptr ele = (param_ptr)malloc_or_fail(sizeof(param_ele), "add_param");
    ele->valp = valp;
    ...
}

解決方法
- 既然需要將其作為 4 個位元組的變數使用，則概念上只需將 bool 型態進行位元延伸，使其成為 4 個位元組的整數型態，並且以整數 0 或 1 表示 false 或 true
- 所以實作上將 echo 改成整數宣告，即可解決問題
- 此外，全域變數 simulation 也有同樣問題，同理，也可以用此方法解決
  Image Not Showing Possible Reasons
  The image file may be corrupted
  The server hosting the image is unavailable
  The image path is incorrect
  The image format is not supported
  Learn More →
  simulation 為一 extern 變數，故 header file 之宣告與 source file 之定義皆須做修改

運用 Valgrind

問題描述：使用 valgrind 進行執行時期的記憶體檢測可以發現有部分配置的記憶體空間未被釋放，以下為 trace-01 之執行的錯誤訊息
```
$ make
$ valgrind ./qtest -v 1 -f traces/trace-01-ops.cmd
```
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
為了更有彈性的進行測試，我嘗試手動輸入測資，卻發現此方法不會觸發錯誤，故能夠推斷此錯誤產生的原因與讀檔進行輸入相關，此資訊應該會在後續分析有所幫助
觀察錯誤訊息可以發現，未被釋放的記憶體是在 linenoiseHistoryAdd 函式中（分別在 linenoise.c:1224 與 linenoise.c:1236）被配置的，其用途為記錄命令列的輸入歷史
- 配置字元指標的空間，用於指向各條歷史紀錄
```
history = malloc(sizeof(char *) * history_max_len);
```
- 使用 strdup 複製字串，即各條命令本身內容
```
linecopy = strdup(line);
```
- 後續將複製的字串存入歷史紀錄中（交由前面配置的指標所指）
```
history[history_len] = linecopy;
```

接著，由於前面已經發現僅在讀檔進行輸入時未將此記憶體空間釋放，故必存在用於釋放歷史紀錄的記憶體空間的程式片段，找到它並進行追蹤

記憶體空間會在 freeHistory 函式中進行釋放










static void freeHistory(void)
{
    if (history) {
        int j;

        for (j = 0; j < history_len; j++)
            free(history[j]);
        free(history);
    }
}

freeHistory 僅在 linenoiseAtExit 函式中被呼叫





static void linenoiseAtExit(void)
{
    disableRawMode(STDIN_FILENO);
    freeHistory();
}

linenoiseAtExit 僅在首次呼叫 enableRawMode 函式時會被 atexit 註冊，若被註冊則當程序正常終止時便會執行該函式。enableRawMode 函式之目的為開啟 raw mode，以改變特定按鍵輸入的行為，例如：改變 tab 鍵的行為以此實作命令自動補齊的功能，關於 raw mode 在此段落不進行深入討論，詳見 linenoise 運作原理段落












static int enableRawMode(int fd)
{
    struct termios raw;

    if (!isatty(STDIN_FILENO))
        goto fatal;
    if (!atexit_registered) {
        atexit(linenoiseAtExit);
        atexit_registered = 1;
    }
    ...
}

參考 atexit man page

由於讀檔進行輸入不需要切換成 raw mode（因為輸入來自檔案，故不需要改變按鍵輸入的行為），故不會呼叫到 enableRawMode 函式，因此歷史紀錄的記憶體空間不會被釋放

解決方法

找到判別檔案輸入或命令列輸入的分支處，其位於 console.c 的 run_console 函式中，處理檔案輸入的部分為 else block 中的程式碼












if (!has_infile) {
    char *cmdline;
    while ((cmdline = linenoise(prompt)) != NULL) {
        interpret_cmd(cmdline);
        linenoiseHistoryAdd(cmdline);       /* Add to the history. */
        linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
        linenoiseFree(cmdline);
    }
} else {
    while (!cmd_done())
        cmd_select(0, NULL, NULL, NULL, NULL);
}

向下追蹤 cmd_done 與 cmd_select 的內容卻發現其中並無操作歷史紀錄的程式碼，故回頭檢查檔案輸入前後的歷史紀錄，發現檔案輸入的內容確實沒有被記錄，未被釋放的空間所存放的歷史紀錄是在執行 run_console 以前就載入完成的過往執行的紀錄
又因為檔案輸入的內容並不會記錄，故當使用檔案輸入時其實不需要載入過往的紀錄，因此找到載入歷史紀錄的函式呼叫，並加入讀檔與否的判斷式即可修正此問題，該段程式碼位於 qtest.c 的 main 函式中
```
- linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
+ if (!infile_name)
+     linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
```

linenoise 運作原理

TODO

2021q1 Homework1 (lab0)

tags: linux2021