2021q1 Homework1 (lab0)

contributed by < AmyLin0210 >

tags: `2021q1 Linux`

2020q1 lab0 作業解說

基本實做

queue_t

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

為了要達成時間複雜度

O (1)

，加上 *tail 與 size。

需要更多解釋，包含後續的使用和資料更新方式。

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

tail 指向 linked list 的最末端，用途為在尾端插入數值時，可以不用從最前方走訪所有節點，使得時間複雜度降為
$O (1)$ 。它會在 list 的最末端有變動時，例如 q_insert_tail, q_sort, q_reverse 等函式執行時變更他的位置，以確保它正確指向最末端。

size 用於紀錄 linked list 的長度，所以在呼叫 q_size 時，不用遍歷整串 linked list，時間複雜度降為
$O (1)$ 。它會在 linked list 的長度有變化時被改變，例如 q_insert_tail, q_insert_head, q_remove_head。

q_new

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));

    if (!q)
        return NULL;

    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

確認 malloc 的回傳值是否合法，然後將所有參數初始化。

q_free

void q_free(queue_t *q)
{
    list_ele_t *tmp_e = NULL;

    if (q) {
        while (q->head) {
            if (q->head->value)
                free(q->head->value);
            tmp_e = q->head;
            q->head = tmp_e->next;
            free(tmp_e);
        }
        free(q);
    }
}

將所有動態分配 ( malloc ) 的空間給釋放。

q_insert_head, q_insert_tail
























































bool q_insert_head(queue_t *q, char *s)
{
    if (!q)
        return false;

    list_ele_t *newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;

    newh->value = malloc(sizeof(char) * (strlen(s) + 1));

    if (!newh->value) {
        free(newh);
        return false;
    }

    snprintf(newh->value, BUFFER_SIZE, "%s", s);
    newh->next = q->head;
    q->head = newh;
    (q->size)++;

    if (!q->tail)
        q->tail = q->head;

    return true;
}

bool q_insert_tail(queue_t *q, char *s)
{
    if (!q)
        return false;

    list_ele_t *newt = malloc(sizeof(list_ele_t));

    if (!newt)
        return false;

    newt->value = malloc(sizeof(char) * (strlen(s) + 1));

    if (!newt->value) {
        free(newt);
        return false;
    }

    if (!q->head)
        q->head = newt;
    else
        q->tail->next = newt;

    snprintf(newt->value, BUFFER_SIZE, "%s", s);
    newt->next = NULL;
    q->tail = newt;
    (q->size)++;

    return true;
}

這兩個函式實做的部份差不多，在第 13 行與 41 行的部份曾經犯過一個錯誤，記得檢查是否有成功 malloc 給 value，但在發現 malloc 失敗時直接 return false，忘記先清掉前面 malloc 給 list_element_t 的空間。

避免說「採過一個坑」這樣不精準的話，請記住，這份共筆可能是日後代表你程度的作品，務必斟酌用詞。

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_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !(q->head))
        return false;

    list_ele_t *tmp = q->head;
    snprintf(sp, bufsize, "%s", tmp->value);
    q->head = q->head->next;
    (q->size)--;

    free(tmp->value);
    free(tmp);

    if (!q->head)
        q->tail = NULL;

    return true;
}

q_size

int q_size(queue_t *q)
{
    if (!q)
        return 0;
    return q->size;
}

為了實做時間複雜度

O (1)

，故在 queue_t 中新增size，儲存目前 list 的長度。

q_reverse

void q_reverse(queue_t *q)
{
    if (!q || !q->head)
        return;

    list_ele_t *prev = q->head, *next = q->head->next;
    q->tail = q->head;
    q->head->next = NULL;

    while (next) {
        q->head = next;
        next = next->next;
        q->head->next = prev;
        prev = q->head;
    }
}

有想過否要使用遞迴的方式，程式碼會比較直覺簡單，但是空間複雜度會變成

O (n)

，相比較之下，迴圈的空間複雜度為

O (1)

，所以最終是使用迴圈來實做。

q_sort

最初是使用 quick sort，但它的 worst case 可能發生在大多數需要被排序的數的優先序相同，時間複雜度為

O (n^{2})

，而在測試資料中就有對應的項目，故之後會改用時間複雜度為

O (n \log n)

的 merge sort 來實做。

list_ele_t *merge(list_ele_t *front, list_ele_t *back)
{
    if (!front)
        return back;
    if (!back)
        return front;

    list_ele_t *tmp = front;
    list_ele_t **result = &tmp;
    list_ele_t *head =
        (strcasecmp(back->value, front->value) >= 0) ? front : back;

    while (front && back) {
        while (front && strcasecmp(back->value, front->value) >= 0) {
            result = &((*result)->next);
            front = front->next;
        }
        *result = back;
        if (!front) {
            break;
        }
        while (back && strcasecmp(front->value, back->value) >= 0) {
            result = &((*result)->next);
            back = back->next;
        }
        *result = front;
    }

    return head;
}

void mergesort(list_ele_t **list, int list_len)
{
    list_ele_t *tmp = *list;
    list_ele_t *front = *list;
    list_ele_t *back = NULL;

    if (list_len <= 1)
        return;

    for (int i = 0; i < (list_len / 2) - 1; ++i) {
        tmp = tmp->next;
    }

    back = tmp->next;
    tmp->next = NULL;

    mergesort(&front, list_len / 2);
    mergesort(&back, list_len - list_len / 2);

    *list = merge(front, back);
}

分析 Makefile

參考資料：
Makefile 語法和示範
 gcc(1) — Linux manual page

開始看 Makefile 之後又發現自己的一無所知，接下來就是一連串找資料、學習、寫筆記的開始，在此感謝同學 randy870819 與 KYG-yaya573142 的共筆！

CFLAGS = -O1 -g -Wall -Werror -Idudect -I.

在這裡用到了 gcc 的一些參數
- -O1 : 在編譯器裡有 -O0 -O1 -O2 -O3 四個優化程度可以選擇，-O0 為不優化而 -O3 的優化級別最高
- -g : 產生 debugging information
- -Werror : 讓每個 warnings 變成 error
- -Idir : 會在編譯時先在 dir 尋找有沒有符合的 header file，找不到才會依照常規順序繼續尋找

sanitizer

在編譯時加入一些 sanitizer 的參數

# Enable sanitizer(s) or not
ifeq ("$(SANITIZER)","1")
    # https://github.com/google/sanitizers/wiki/AddressSanitizerFlags
    CFLAGS += -fsanitize=address -fno-omit-frame-pointer -fno-common
    LDFLAGS += -fsanitize=address
endif

verbosity

在這裡決定要不要印出詳細的編譯過程

當 VERBOSE 為 1 時會印出詳細編譯過程
- @ 的作用是不顯示執行的指令
- @true可以使該行命令被視作成成功

# Control the build verbosity
ifeq ("$(VERBOSE)","1")
    Q :=
    VECHO = @true
else
    Q := @
    VECHO = @printf
endif

qtest: $(OBJS)
	$(VECHO) "  LD\t$@\n"
	$(Q)$(CC) $(LDFLAGS) -o $@ $^ -lm

objects and dependencies

這邊使用了 Auto-Dependency Generation 來處理 dependency 的問題

第 5 行: 將所有 OBJS 中的 .o 檔代換成 .檔案名稱.o.d
第 10 行: 在建立 object file 的同時也建立 dependency file
第 12 行: include 所有的 dependency file
-MMD the driver uses its argument but with a suffix of .d, and mention only user header files, not system header files
-MF overrides the default dependency output file

當目標 ( target ) 比起自己的相依項目 ( dependency ) 還要建立的更早時，表示其相依項目已經被修改，在此利用 GNU make 中 auto-rebuild 的特徵重新建立目標。












OBJS := qtest.o report.o console.o harness.o queue.o \
        random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
        linenoise.o

deps := $(OBJS:%.o=.%.o.d)

%.o: %.c
	@mkdir -p .$(DUT_DIR)
	$(VECHO) "  CC\t$@\n"
	$(Q)$(CC) -o $@ $(CFLAGS) -c -MMD -MF .$@.d $<
    
-include $(deps)

valgrind

tid := 0

# Control test case option of valgrind
ifeq ("$(tid)","0")
    TCASE :=
else
    TCASE := -t $(tid)
endif

valgrind_existence:
	@which valgrind 2>&1 > /dev/null || (echo "FATAL: valgrind not found"; exit 1)

valgrind: valgrind_existence
	# Explicitly disable sanitizer(s)
	$(MAKE) clean SANITIZER=0 qtest
	$(eval patched_file := $(shell mktemp /tmp/qtest.XXXXXX))
	cp qtest $(patched_file)
	chmod u+x $(patched_file)
	sed -i "s/alarm/isnan/g" $(patched_file)
	scripts/driver.py -p $(patched_file) --valgrind $(TCASE)
	@echo
	@echo "Test with specific case by running command:" 
	@echo "scripts/driver.py -p $(patched_file) --valgrind -t <tid>"

// 施工研究中

開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤

先執行 qtest 再於命令提示列輸入 help 命令，會使開啟 Address Sanitizer 觸發錯誤

$ make clean
$ make SANITIZER=1//    開啟 Address Sanitizer
$ ./qtest

以下是錯誤訊息的節錄












==22083==ERROR: AddressSanitizer: global-buffer-overflow on address 0x555ca3a7b400 at pc 0x555ca3a647bd bp 0x7fff08f34f00 sp 0x7fff08f34ef0
READ of size 4 at 0x555ca3a7b400 thread T0
    #0 0x555ca3a647bc in do_help_cmd /home/amy/Desktop/NCKU/School-Work/Linux/lab0-c/console.c:307
    #1 0x555ca3a648d0 in interpret_cmda /home/amy/Desktop/NCKU/School-Work/Linux/lab0-c/console.c:221
    #2 0x555ca3a650b5 in interpret_cmd /home/amy/Desktop/NCKU/School-Work/Linux/lab0-c/console.c:244
    #3 0x555ca3a667f8 in run_console /home/amy/Desktop/NCKU/School-Work/Linux/lab0-c/console.c:660
    #4 0x555ca3a633e5 in main /home/amy/Desktop/NCKU/School-Work/Linux/lab0-c/qtest.c:780
    #5 0x7f6b23bfa0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
    #6 0x555ca3a60b8d in _start (/home/amy/Desktop/NCKU/School-Work/Linux/lab0-c/qtest+0x8b8d)

0x555ca3a7b401 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x555ca3a7b400) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /home/amy/Desktop/NCKU/School-Work/Linux/lab0-c/console.c:307 in do_help_cmd

從第 11 行來看，我們要從 console.c 去尋求進一步的線索。

在 console.c 的第 59 行，有一個變數宣告

static bool echo = 0;

往下搜尋還有其他哪些地方有用到這個 echo 變數，發現以下程式碼的第 21 行對 echo 進行了強制轉型，但是原 echo 的型態為 bool ，它卻將指向 bool 位置的指標改成指向 int 位置的指標。


























void init_cmd()
{
    cmd_list = NULL;
    param_list = NULL;
    err_cnt = 0;
    quit_flag = false;

    add_cmd("help", do_help_cmd, "                | Show documentation");
    add_cmd("option", do_option_cmd,
            " [name val]     | Display or set options");
    add_cmd("quit", do_quit_cmd, "                | Exit program");
    add_cmd("source", do_source_cmd,
            " file           | Read commands from source file");
    add_cmd("log", do_log_cmd, " file           | Copy output to file");
    add_cmd("time", do_time_cmd, " cmd arg ...    | Time command execution");
    add_cmd("#", do_comment_cmd, " ...            | Display comment");
    add_param("simulation", (int *) &simulation, "Start/Stop simulation mode",
              NULL);
    add_param("verbose", &verblevel, "Verbosity level", NULL);
    add_param("error", &err_limit, "Number of errors until exit", NULL);
    add_param("echo", (int *) &echo, "Do/don't echo commands", NULL);

    init_in();
    init_time(&last_time);
    first_time = last_time;
}

當 add_param 以為該指標指向 integer 但實際上是指向 bool 時，就有可能會發生 buffer overflow 的問題。

在我的電腦中執行以下程式碼， int 和 bool 的大小不同增強了我對那段程式碼的懷疑。

#include <stdbool.h>
#include <stdio.h>

int main() {
    printf("bool size: %ld\n", sizeof(bool));
    printf("int size: %ld\n", sizeof(int));
    return 0;
}

bool size: 1
int size: 4

在 console.c 中有一段程式碼

















static bool do_help_cmd(int argc, char *argv[])
{
    cmd_ptr clist = cmd_list;
    report(1, "Commands:", argv[0]);
    while (clist) {
        report(1, "\t%s\t%s", clist->name, clist->documentation);
        clist = clist->next;
    }
    param_ptr plist = param_list;
    report(1, "Options:");
    while (plist) {
        report(1, "\t%s\t%d\t%s", plist->name, *plist->valp,
               plist->documentation);
        plist = plist->next;
    }
    return true;
}

在第 12 行中的 *plist->valp 存取到的就是上述所提的 echo 變數，但它卻是用 %d 來讀取一個 1 byte 的數值，因此 buffer overflow。

目前我想到的改善方式是改變該程式碼中 echo 與有相同問題的 simulation ，將他們由 bool 改為 int ，但改變資料型態後可能會造成其餘相關程式碼出現問題，所以還在思考有沒有更優雅的改法。

運用 Valgrind 排除 qtest 實作的記憶體錯誤

以下擷取自 make valgrind 後得到的訊息

==46210== 10 bytes in 1 blocks are still reachable in loss record 1 of 3
==46210==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==46210==    by 0x4A5250E: strdup (strdup.c:42)
==46210==    by 0x1100B6: linenoiseHistoryAdd (linenoise.c:1236)
==46210==    by 0x110C49: linenoiseHistoryLoad (linenoise.c:1325)
==46210==    by 0x10C22C: main (qtest.c:769)
==46210== 
==46210== 160 bytes in 1 blocks are still reachable in loss record 2 of 3
==46210==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==46210==    by 0x110076: linenoiseHistoryAdd (linenoise.c:1224)
==46210==    by 0x110C49: linenoiseHistoryLoad (linenoise.c:1325)
==46210==    by 0x10C22C: main (qtest.c:769)
==46210== 
==46210== 170 bytes in 19 blocks are still reachable in loss record 3 of 3
==46210==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==46210==    by 0x4A5250E: strdup (strdup.c:42)
==46210==    by 0x11002A: linenoiseHistoryAdd (linenoise.c:1236)
==46210==    by 0x110C49: linenoiseHistoryLoad (linenoise.c:1325)
==46210==    by 0x10C22C: main (qtest.c:769)

首先我們看到 valgrind 的錯誤訊息，still reachable 表示程式結束時有未釋放的記憶體，不過卻還有指標指著。

接下來我們找到 qtest.c 的第 769 行。

linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */

接下來看看 linenoise.c 的 1325 行，可以發現又呼叫了另一個函式。

linenoiseHistoryAdd(buf);

在這份程式碼中，有使用一個名為 history 的參數，型態為 char** ，當中做的事情是儲存字串，而 linenoiseHistoryAdd 做的就是將這些字串加入 history。
因此我猜測由於 history 所指向的記憶體空間在程式結束前沒有被成功的清掉，所以才會出現 still reachable 這項錯誤。
最後我在程式結束前將 history 指向的空間清掉，就不會再跳出錯誤訊息了。