2019q1 Homework1 (lab0)

contributed by < fateyan >
Problem Source

實作

q_new

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

q_free

在實作的時候 free 掉了 element 卻忘記 free 掉 element 裡面 malloc 出來的記憶體
看到 Code 的第二眼覺得沒有檢查 if (buf != NULL) 才做感覺有點危險
- 但其實所有插入操作 malloc 完之後都會檢查有沒有成功，沒有的話就會直接回溯，所以應該沒問題

void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    if (q == NULL)
        return;

    // we lost next link once we free element, so we need to save it.
    list_ele_t *buf = NULL;
    list_ele_t *el = q->head;
    while (el != NULL) {
        buf = el;
        el = el->next;
        free(buf->value);
        free(buf);
    }
    /* Free queue structure */
    free(q);
}

q_insert_head

其實要求並沒有說 s 是 NULL 的時候該怎麼辦，我就視同 q == NULL 處理了，插尾也一樣

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    if (q == NULL || s == NULL)
        return false;

    newh = malloc(sizeof(list_ele_t));

    if (newh == NULL)
        return false;
    /* Don't forget to allocate space for the string and copy it */
    newh->value = malloc(sizeof(char) * (strlen(s) + 1));
    /* What if either call to malloc returns NULL? */
    if (newh->value == NULL) {
        free(newh);
        return false;
    }

    strcpy(newh->value, s);
    newh->next = q->head;
    q->head = newh;
    if (q_size(q) == 0)
        q->tail = newh;
    ++q->size;
    return true;
}

q_insert_tail

bool q_insert_tail(queue_t *q, char *s)
{
    /* You need to write the complete code for this function */
    /* Remember: It should operate in O(1) time */
    if (q == NULL || s == NULL)
        return false;

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

    strcpy(newt->value, s);
    newt->next = NULL;

    if (q_size(q) == 0) {
        q->head = newt;
        q->tail = newt;
    } else {
        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)
{
    /* You need to fix up this code. */
    if (q == NULL || q_size(q) == 0)
        return false;

    if (sp != NULL) {
        strncpy(sp, q->head->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    list_ele_t *buf = q->head;
    q->head = q->head->next;
    free(buf->value);
    free(buf);

    --q->size;
    if (q->size == 0)
        q->tail = NULL;
    return true;
}

q_size

int q_size(queue_t *q)
{
    /* You need to write the code for this function */
    /* Remember: It should operate in O(1) time */
    if (q == NULL)
        return 0;
    return q->size;
}

q_reverse

其實更喜歡做遞迴版本的，而且應該可以寫成尾遞迴，不過老師開的 API 沒那麼適合，不想再開另外一個函數就照做了

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if (q == NULL || q->head == NULL || q->head->next == NULL)
        return;
    list_ele_t *prev = NULL;
    list_ele_t *cur = q->head;
    list_ele_t *next = cur->next;

    q->tail = cur;

    while (cur != NULL) {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }

    q->head = prev;
}

自動測試的原理分析

整個流程的 entry point 在 Makefile，所以從這邊開始 trace，看到了 test 是呼叫 scripts/driver.py 於是繼續追蹤
看到 scripts/driver.py 裡面，進入點是 run，主要都在處理參數，然後功能幾乎都在 Tracer 裡面實現，那接下來簡介 Tracer

Tracer 維護了一些 trace 的 dictionary，還有 Base Directory 之類的環境資訊和參數，還有跑測試的一些 method
- run 是 Tracer 的主要工作進入點，是把跑 trace 需要的資訊準備好，然後把 trace 一個一個丟進 runTrace 跑追蹤
- 然後測試方法或該說測試用的工具有兩種：qtest 和 valgrind，又或者是在 command line interface 上和兩種兼容的測試工具
  - 餵給 command 的參數主要有 qtest, verboseLevel, filename，其中如果 command != valgrind 的話 qtest 就留空

這部份有些讓我不太知道為何這麼實作的點：
- 57 行的測試感覺很冗餘
- trace 用 dictionary 維護也有點奇怪，直覺上在這裡不管是 Hash Table 還是 RBTree 都不太可能比裸的 Array 快，而且這個場景也沒有真的需要用到 Dictionary 優勢的地方
- console.c 裡 L481 為什麼是 RIO_BUFSIZE - 2，不是 - 1，應該就只是留一個 NULL Terminator 吧？

再來回頭看到 Makefile，其中 qtest 的 source file 有 qtest.c report.c console.c harness.c queue.o，那我們就繼續追蹤 qtest

qtest.c

實作那些對 queue 操作的基本函數
用console.c 裡的 add_cmd 來把 CLI 指令和操作 queue 的函數掛進 cmd_list
queue_init
- 因為我 OS 唸爛了，所以來重看一下 Signal
  - 根據 wiki 的說法，它是 IPC 的一種，Signal 會直接中斷程式（除了 Atomic Operation），然後跳進 Handler
  - 所以其實這個 init 只是在註冊 Signal 以及其 Handler

console.c

用 push_file 開啟了一個檔案之後會用 struct RIO_ELE （Buffered I/O 結構）來記錄它的一些東西，例如 FD 或 buffer 之類的。
#L492 沒做 bound check
不懂 select 所以翻了一下資料
- 先講解 fd：雖然不知道怎麼實作的，但被開啟的檔案會被統一整理在 file table 裡面，而 fd 就是 file table 的 entry（講的簡單一點的話可能就像 T file_table[MAX_FDS]）
- select 和 blocking read 的差別在於它不會浪費 CPU cycle
- 不太確定的是第一個參數 nfds 是現在用到的 fd 的最大值 + 1，我在想原因會不會是所有會創造/給出 fd 的函數都會給沒被佔用的最小的那個，那麼就算有新的 fd 出現了，它也會是 nfds，但所有的 fd 都該/會被僅有的一個 select 監視嗎？有沒有可能有 multi-select 而且還 multithreaded
cmd_select 就是 select 的再包裝，主要是迎合 RIO_ELE 實作了 buffered I/O
Buffered IO 其實就是讀資料讀滿 buffer，parse 的時候直接從 buffer 拿，buffer 空了就再從 stdin 拿，好處應該是減少 IO 次數，壞處是一次 IO 就會做到讀至 EOF 或讀滿 buffer，一次會花相對長的時間，但是感覺比起瑣碎的一直呼叫 syscall 來得省時間的多
先總結一下，console.c 整個都在做 console 的 IO, parsing 還有實作基本的 CLI 指令，對外比較重要的 function 大概就 add_cmd 吧

harness.c
一開始看到 harness 這個字愣了很久，後來發現原來是專有名詞，我覺得前面連結的 Wiki 把 harness 解釋的很好就不多解釋了，那比較特別的部分就是會用 Linked List 把 malloc 出來的資料串起來，而且資料的前後都會加 magic header 和 footer，0xdeadbeef 和 0xbeefdead。

環境

Linux fateyan-pc 4.20.11-1-MANJARO #1 SMP PREEMPT Wed Feb 20 23:19:36 UTC 2019 x86_64 GNU/Linux

Architecture:        x86_64
CPU op-mode(s):      32-bit, 64-bit
Byte Order:          Little Endian
Address sizes:       36 bits physical, 48 bits virtual
CPU(s):              4
On-line CPU(s) list: 0-3
Thread(s) per core:  2
Core(s) per socket:  2
Socket(s):           1
NUMA node(s):        1
Vendor ID:           GenuineIntel
CPU family:          6
Model:               58
Model name:          Intel(R) Core(TM) i3-3220 CPU @ 3.30GHz
Stepping:            9
CPU MHz:             1925.908
CPU max MHz:         3300.0000
CPU min MHz:         1600.0000
BogoMIPS:            6603.49
Virtualization:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            3072K
NUMA node0 CPU(s):   0-3
Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr pdcm pcid sse4_1 sse4_2 popcnt tsc_deadline_timer xsave avx f16c lahf_lm cpuid_fault epb pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid fsgsbase smep erms xsaveopt dtherm arat pln pts flush_l1d

參考資料

[0] 直接用 read() 和用 select() 的比較