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: 以遞增順序來排序鏈結串列的元素

除了實作上述的功能外，還要考慮以下記憶體檢測的議題

先執行 qtest 再於命令提示列輸入 help 命令，會使開啟 Address Sanitizer 觸發錯誤，應予以排除
運用 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;
}

可調整程式碼風格如下:

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

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

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 →

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

問題：是否需要指派 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 的警告

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 →

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

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，使用 O(nlogn) 的 merge sort
merge(): left 跟 right 是已排序狀態，因此只要將 left right 兩個佇列的元素兩兩 (strcmp) 比較再串接即可

我原先沒搞清楚 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') 也是可以的

一開始實作 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 的筆記，發現有可能是因為頻繁使用遞迴導致 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 也是。