# 2021q1 Homework1 (lab0)
contributed by < `ChenBoSyun` >
###### tags: `linux2021`

## 作業要求

在 `queue.[h/c]` 完成以下要求
* `q_new`: 建立新的「空」佇列;
* `q_free`: 釋放佇列所佔用的記憶體;
* `q_insert_head`: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
* `q_insert_tail`: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
* `q_remove_head`: 在佇列開頭 (head) 移除 (remove) 給定的元素。
* `q_size`: 計算佇列中的元素數量。
* `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
* `q_sort`: 以==遞增順序==來排序鏈結串列的元素

除了實作上述的功能外，還要考慮以下記憶體檢測的議題
1. 先執行 qtest 再於命令提示列輸入 help 命令，會使 開啟 Address Sanitizer 觸發錯誤，應予以排除
2. 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗

## 實作細節

### queue.h
* 新增 `list_ele_t *tail` 與 `unsigned int size` ，為了讓 `q_insert_tail()` 與 `q_size()` 能在O(1) 時間內完成

/* Queue structure */
typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    unsigned int size;
} queue_t;

### queue.c

#### q_new
* 檢查是否有正常的配置記憶體 (`malloc` 回傳值不是 `NULL`)

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (q == NULL) {
        return NULL;
    }
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

:::warning
可調整程式碼風格如下:

queue_t *q = malloc(sizeof(queue_t));
if (!q)
    return NULL

與之相似，`if (q != NULL)` 可簡化為 `if (q)`
:notes: jserv
:::

#### q_free
* 避免目前的 `list_ele_t *curr` 被 `free` 後，無法取得下一個 `list_ele_t`，記得先
將 `curr->next` 指派給 `tmp`

void q_free(queue_t *q)
{
    if (q == NULL) {
        return;
    }
    list_ele_t *curr = q->head;
    list_ele_t *tmp;
    while (curr != NULL) {
        tmp = curr->next;
        free(curr->value);
        free(curr);
        curr = tmp;
    }
    free(q);
    return;
}

:::info
問題： 是否需要指派 `NULL` 給 `queue_t*`，避免 dangling pointer

void q_free(queue_t **q)
{
    if (*q == NULL) {
        return;
    }
    list_ele_t *curr = (*q)->head;
    list_ele_t *tmp;
    while (curr != NULL) {
        tmp = curr->next;
        free(curr->value);
        free(curr);
        curr = tmp;
    }
    free(*q);
    *q = NULL;
    return;
}

> 你可用設計實驗並用 ASan 檢測，看會不會遇到 use-after-free 的警告
> :notes: jserv
:::

#### q_insert_head
* 當配置記憶體失敗時，在 `function return` 之前記得把已經配置過的記憶體 `free` 掉
* 配置記憶體給 string buffer 時，要注意 `strlen()` 在計算字串長度時不會包含空字元(`'\0'`)，記得還要再加一個 byte 存放 `'\0'`
> The strlen() function calculates the length of the string pointed
to by s, excluding the terminating null byte ('\0'). - [man strlen](https://man7.org/linux/man-pages/man3/strlen.3.html)

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    if (q == NULL) {
        return false;
    }

    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL) {
        return false;
    }

    newh->value = malloc(sizeof(char) * (strlen(s) + 1));
    if (newh->value == NULL) {
        free(newh);
        return false;
    }

    memcpy(newh->value, s, strlen(s));
    *(newh->value + strlen(s)) = '\0';
    newh->next = q->head;
    q->head = newh;
    q->size++;
    if (q->size == 1) {
        q->tail = newh;
    }
    return true;
}

#### q_insert_tail
* 為了讓 `q_insert_tail` 在 O(1) 時間內完成，在 `queue_t` 內加上 `tail` 讓它指向佇列的最後一個元素

bool q_insert_tail(queue_t *q, char *s)
{
    if (q == NULL) {
        return false;
    }

    list_ele_t *newt;
    newt = malloc(sizeof(list_ele_t));
    if (newt == NULL) {
        return false;
    }

    newt->value = malloc(sizeof(char) * (strlen(s) + 1));
    if (newt->value == NULL) {
        free(newt);
        return false;
    }

    memcpy(newt->value, s, strlen(s));
    *(newt->value + strlen(s)) = '\0';
    newt->next = NULL;

    q->tail->next = newt;
    q->tail = newt;
    q->size++;
    return true;
}

#### q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL || q->head == NULL) {
        return false;
    }
    char *str = q->head->value;

    if (sp != NULL) {
        if (strlen(str) > bufsize - 1) {
            memcpy(sp, str, bufsize - 1);
            *(sp + bufsize - 1) = '\0';
        } else {
            memcpy(sp, str, strlen(str));
            *(sp + strlen(str)) = '\0';
        }
    }
    free(str);
    list_ele_t *tmp = q->head;
    q->head = q->head->next;
    free(tmp);
    q->size--;
    return true;
}

#### q_size

int q_size(queue_t *q)
{
    if (q == NULL || q->head == NULL) {
        return 0;
    }
    return q->size;
}

#### q_reverse
* 在反轉之前，先將 head 指派給 tail；因為反轉後的 tail 和 head 順序會顛倒
* 迴圈內，將 curr 指向 prev 時；避免找不到 next，要先將 next 保存下來

void q_reverse(queue_t *q)
{
    if (q == NULL || q->head == NULL) {
        return;
    }
    q->tail = q->head;

    list_ele_t *prev = NULL;
    list_ele_t *curr = q->head;
    list_ele_t *next;
    while (curr != NULL) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    q->head = prev;
    return;
}

#### q_sort
* 參考 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/)，使用 O(nlogn) 的 merge sort
* `merge()`: left 跟 right 是已排序狀態，因此只要將 left right 兩個佇列的元素兩兩 (strcmp) 比較再串接即可
::: info
我原先沒搞清楚 `strcmp` 的回傳值代表的意思，從 man strcmp 的 DESCRIPTION 也沒有說明回傳值的細節
> strcmp() returns an integer indicating the result of the
comparison, as follows:
• 0, if the s1 and s2 are equal;
• a negative value if s1 is less than s2;
• a positive value if s1 is greater than s2.

參照 strcmp.c 原始碼，發現strcmp是照順序比較 str1 str2 的字元大小，
若兩個字元一樣，則繼續比較下一組字元。

int
STRCMP (const char *p1, const char *p2)
{
  const unsigned char *s1 = (const unsigned char *) p1;
  const unsigned char *s2 = (const unsigned char *) p2;
  unsigned char c1, c2;

  do
    {
      c1 = (unsigned char) *s1++;
      c2 = (unsigned char) *s2++;
      if (c1 == '\0')
	return c1 - c2;
    }
  while (c1 == c2);

  return c1 - c2;
}

值得注意的是，我在看原始碼時注意到

if (c1 == '\0')
    return c1 - c2;

當下我覺得為何只針對 c1 檢查 `'\0'`，後來推測是避免當 str1 str2 所有字元一樣時，可能造成 buffer overflow 問題 (`*s1++` 超過字串的邊界)，且程式與預期的結果會不符
這邊的檢查換成 `if (c2 == '\0')` 也是可以的

:::

:::info
一開始實作 merge two sorted linked list，使用的是遞迴的作法

list_ele_t *merge(list_ele_t *left, list_ele_t *right)
{
    if (left == NULL) {
        return right;
    }
    if (right == NULL) {
        return left;
    }
    if (strcmp(left->value, right->value) < 0) {
        left->next = merge(left->next, right);
        return left;
    } else {
        right->next = merge(left, right->next);
        return right;
    }
}

執行測資 trace-15-perf.cmd，會出現 segmentation fault。
參考 [RinHizakura](https://hackmd.io/@RinHizakura/ByuY_q6AU#Segmentation-fault) 的筆記，發現有可能是因為頻繁使用遞迴導致 stack overflow
> 我使用 make SANITIZER=1，trace-15-perf.cmd 沒有輸出任何訊息
:::

* `merge_list()`: 實作將 linked list 分成 left 和 right，在 `merge_list()` 的最後會呼叫 `merge()`，因此 `merge_list()` 回傳的佇列是已排序的

    list_ele_t *left = merge_list(head);
    list_ele_t *right = merge_list(fast);

list_ele_t *merge(list_ele_t *left, list_ele_t *right)
{
    list_ele_t dummy;
    dummy.next = NULL;

    list_ele_t *curr = &dummy;
    while (left != NULL && right != NULL) {
        if (strcmp(left->value, right->value) < 0) {
            curr->next = left;
            curr = curr->next;
            left = left->next;
        } else {
            curr->next = right;
            curr = curr->next;
            right = right->next;
        }
    }
    if (left == NULL) {
        curr->next = right;
    }
    if (right == NULL) {
        curr->next = left;
    }
    return dummy.next;
}

list_ele_t *merge_list(list_ele_t *head)
{
    if (head == NULL || head->next == NULL) {
        return head;
    }
    list_ele_t *fast = head->next;
    list_ele_t *slow = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow->next;
    slow->next = NULL;

    list_ele_t *left = merge_list(head);
    list_ele_t *right = merge_list(fast);

    return merge(left, right);
}

/*
 * Sort elements of queue in ascending order
 * No effect if q is NULL or empty. In addition, if q has only one
 * element, do nothing.
 */
void q_sort(queue_t *q)
{
    if (q == NULL || q->head == NULL) {
        return;
    }

    q->head = merge_list(q->head);
    list_ele_t *curr = q->head;
    while (curr && curr->next) {
        curr = curr->next;
    }
    q->tail = curr;
    return;
}

## 透過 Address Sanitizer 修正，呼叫 help 命令時所造成的記憶體錯誤
開啟 Address Sanitizer 後，執行 help 命令會出現以下錯誤訊息

==8599==ERROR: AddressSanitizer: global-buffer-overflow on address 0x560ff3ffa3c0 at pc 0x560ff3fe37bd bp 0x7ffdfe9b4850 sp 0x7ffdfe9b4840
READ of size 4 at 0x560ff3ffa3c0 thread T0
    #0 0x560ff3fe37bc in do_help_cmd /home/old-cat/linux2021/lab0-c/console.c:307
    #1 0x560ff3fe38d0 in interpret_cmda /home/old-cat/linux2021/lab0-c/console.c:221
    #2 0x560ff3fe40b5 in interpret_cmd /home/old-cat/linux2021/lab0-c/console.c:244
    #3 0x560ff3fe57f8 in run_console /home/old-cat/linux2021/lab0-c/console.c:660
    #4 0x560ff3fe23e5 in main /home/old-cat/linux2021/lab0-c/qtest.c:780
    #5 0x7f38d471b0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
    #6 0x560ff3fdfb8d in _start (/home/old-cat/linux2021/lab0-c/qtest+0x8b8d)

0x560ff3ffa3c1 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x560ff3ffa3c0) of size 1

從錯誤訊息中得知該程式出現 global-buffer-overflow
global-buffer-overflow 是因為存取全域變數時，超過系統配置給你的記憶體範圍時，所產生的記憶體錯誤

追蹤程式碼發現，宣告全域變數 echo 是 bool 型態

static bool echo = 0;

呼叫 `add_param` 時會將 `&echo` 轉型成 `(int *)` ，但這裡還不會出現問題，因為並沒有存取記憶體的動作

add_param("echo", (int *) &echo, "Do/don't echo commands", NULL);

在 `do_help_cmd` 會呼叫以下程式，`%d` 這個格式化輸出會讀取一個 int 的大小(4 bytes)
這樣會超過原本配置的(1 bytes)的記憶體空間

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

修正方法： 將 `echo` 宣告成 `int` 型態，同理 `simulation` 也是。