2020q1 Homework1 (lab0)

contributed by < KYG-yaya573142 >

H01: lab0

預期目標

C 語言程式設計議題，如不定個數參數的處理, signal, setjmp/longjmp 和記憶體管理
學習 GNU/Linux 開發工具
- Cppcheck: 靜態程式碼分析工具
- Valgrind: 動態程式分析工具
學習使用 Git 與 GitHub
樹立一致且易於協作的程式開發規範
研究自動測試機制
接觸 Linux Programming Interface

作業要求

q_new: 建立新的「空」佇列
q_free: 釋放佇列所佔用的記憶體
q_insert_head: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則)
q_insert_tail: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則)，時間複雜度須為
$O (1)$
q_remove_head: 在佇列開頭 (head) 移除 (remove) 給定的元素
q_size: 計算佇列中的元素數量，時間複雜度須為
$O (1)$
q_reverse: 以反向順序重新排列鏈結串列 (此函式不該配置或釋放任何鏈結串列元素)
q_sort: 以遞增順序來排序鏈結串列的元素 (此函式不該配置或釋放任何鏈結串列元素)

開發流程

queue.h

題目要求 q_insert_tail 和 q_size 的時間複雜度須為

O (1)

，因此先修改 queue.h 中的 struct queue_t，新增 list_ele_t *tail 及 int size

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

`q_size`

直接回傳 q->size 即可






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

`q_new`

先確認是否成功 malloc，再初始化 queue










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

`q_free`

須注意在 q_insert_head 與 q_insert_tail 中，除了配置 elements 的記憶體之外，還會再配置記憶體來儲存字串，因此釋放記憶體的順序應該是

用來儲存字串的空間
linked list elements
queue















void q_free(queue_t *q)
{
    if (!q)  /* ignore NULL queue */
        return;
    /* Free queue structure */
    list_ele_t *tmp = q->head;
    while (tmp) {
        q->head = tmp->next;
        if (tmp->value)  /* free the string if existed */
            free(tmp->value);
        free(tmp);
        tmp = q->head;
    }
    free(q);
}

`q_insert_head` & `q_insert_tail`

這兩個 function 寫起來非常相似，先配置 element 的記憶體空間，再配置 element 中用來儲存字串的空間 (記得確認 malloc 是否成功)，儲存字串至 element 內，最後將 element 插入 queue 的頭/尾並把 q->size 加 1
實作上有幾點需特別注意：

strlen 回傳的長度不包含 null terminator，因此 length 記得要加 1 回去

$ man strlen
...
DESCRIPTION
       The strlen() function calculates the length of the string pointed to by s, excluding the terminating null byte ('\0').
...

若在 malloc 字串所需空間時才失敗，記得要釋放 element 的空間再 return
若為 empty queue 時，需特別處理 q->head 或 q->tail (使兩者皆指向目前新增的唯一 element)



















































bool q_insert_head(queue_t *q, char *s)
{
    if (!q) /* ignore NULL queue */
        return false;
    list_ele_t *newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    /* allocate space for the string and copy it */
    int length = strlen(s) + 1;
    newh->value = malloc(length * sizeof(char));
    if (!newh->value) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, length);
    /* insert element at head of queue */
    if (q->head == NULL) /* queue is empty */
        q->tail = newh;
    newh->next = q->head;
    q->head = newh;
    (q->size)++;
    return true;
}

bool q_insert_tail(queue_t *q, char *s)
{
    if (!q) /* ignore NULL queue */
        return false;
    list_ele_t *newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    /* allocate space for the string and copy it */
    int length = strlen(s) + 1;
    newh->value = malloc(length * sizeof(char));
    if (!newh->value) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, length);
    /* insert element at tail of queue */
    if (q->head == NULL) { /* no element in the queue */
        q->head = newh;
        q->tail = newh;
    } else {
        q->tail->next = newh;
        q->tail = q->tail->next;
    }
    q->tail->next = NULL;
    (q->size)++;
    return true;
}

`q_remove_head`

釋放記憶體的邏輯類似 q_free，釋放 elements 配置的記憶體前，需先處裡並釋放 element 中字串使用的空間
實作上需注意複製字串至 sp 的這個步驟，由於有最大空間為 bufsize 的限制，應該使用 strncpy 而非 strcpy，使用前先查閱說明 man strncpy

The strcpy() function copies the string pointed to by src, including the terminating null byte ('\0'), to the buffer pointed to by dest. The strings may not overlap, and the destination string dest must be large enough to receive the copy. Beware of buffer overruns!
The strncpy() function is similar, except that at most n bytes of src are copied. Warning: If there is no null byte among the first n bytes of src, the string placed in dest will not be null-terminated.
If the length of src is less than n, strncpy() writes additional null bytes to dest to ensure that a total of n bytes are written.

因此當 bufsize 小於字串長度時，將不會複製到 null terminator，要記得手動將其補上

















bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !q->head) /* ignore NULL and empty queue */
        return false;
    list_ele_t *tmp = q->head;
    q->head = q->head->next;
    if (tmp->value) { 
        if (sp != NULL) {
            strncpy(sp, tmp->value, (bufsize - 1));
            sp[bufsize - 1] = '\0';
        }
        free(tmp->value);
    }
    free(tmp);
    (q->size)--;
    return true;
}

`q_reverse`

實作上可以分為以下步驟

建立 new 指標，用來指向已經分類完成的 elements
q->tail 可以先指向 q->head，因為最後順序會反轉
依序將 element 從原先的 queue 取出
總是將取出的 element 放到 new 的頭，來達到反轉順序的目的
最後將 new 指標接回去 q->head 即可




















void q_reverse(queue_t *q)
{
    if (!q || !q->head) /* ignore NULL and empty queue */
        return;
    if (!q->head->next)
        return;
    list_ele_t *tmp;
    list_ele_t *new = NULL;
    q->tail = q->head;
    while (q->head) {
        /* detach element from the head */
        tmp = q->head;
        q->head = q->head->next;
        /* reverse the queue */
        tmp->next = new;
        new = tmp;
    }
    q->head = new;
}

`q_sort`

根據作業說明的共筆中提供的資料，可以使用 bubble sort、insertion sort、selection sort、merge sort 等方式來排序 (將 sort_method 的部分替換成欲使用的演算法名稱即可，例如 merge_sort)











void q_sort(queue_t *q)
{
    if (!q || !q->head) /* ignore NULL and empty queue */
        return;
    if (!q->head->next)
        return;
    q->head = sort_method(q->head);
    while (q->tail->next) { /* update the tail pointer */
        q->tail = q->tail->next;
    }
}

至於題目中所謂的以遞增順序來排序鏈結串列的元素要怎麼做呢? 其實直接觀察 qtest.c 就可以知道答案了，其中 do_sort 這個方程式中很明確的使用 strcasecmp 來檢驗 q_sort 的結果，因此在我們的 q_sort 中一樣使用 strcasecmp 來排序就可以了

merge sort

概念上可以分為拆分 (merge_sort) 及合併 (merge) 兩個部分

拆分 merge_sort:

將原先的 list 從中間分為兩半
將分出來的兩個 list 再各自從中間分為兩半
重複步驟 2 直到整個 list 都被拆成單一 element




















list_ele_t *merge_sort(list_ele_t *head)
{
    /* merge sort */
    if (!head || !head->next)
        return head;
    list_ele_t *slow = head;
    list_ele_t *fast = head->next;
    /* split list */
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow->next;
    slow->next = NULL;
    /* sort each list */
    list_ele_t *l1 = merge_sort(head);
    list_ele_t *l2 = merge_sort(fast);
    /* merge sorted l1 and sorted l2 */
    return merge(l1, l2);
}

合併 merge

排序兩個單一 element 並合併為一個 list
把兩個上述步驟產生的 list 排序並接合為一個 list
重複步驟 2 直到接合所有 list

以下我分別使用不同的方式來實作 merge 的部分

方式 1 - 使用遞迴的方式 merge
這個方式的優點是程式碼很簡潔，但遞迴呼叫的方式導致記憶體使用量更龐大。
最明顯的例子就是當測試 traces-15-perf.cmd 時，因為配置的 elements 數非常龐大 (size = 2,000,000)，會出現 segmentation fault (使用 AddressSanitizer 可以知道問題是 stack overflow)

註：後續會再使用 valgrind 來分析此問題

$ make SANITIZER=1
$ make test
...
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
ASAN:DEADLYSIGNAL
=================================================================
==9205==ERROR: AddressSanitizer: stack-overflow on address 0x7ffcd0a27fd8 (pc 0x7f703599965e bp 0x7ffcd0a28840 sp 0x7ffcd0a27fa0 T0)
...















list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
    if (!l1)
        return l2;
    if (!l2)
        return l1;
    
    if (strcasecmp(l1->value, l2->value) < 0) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l1, l2->next);
        return l2;
    }
}

方式2 - pseudo head
常見的 pseudo head 是先 malloc 一個空間來連接已經排序完成的 element，但在本作業中不允許在 q_sort 內呼叫 malloc，因此我改為使用指標的方式實作，如此一來在 traces-15-perf.cmd 時就不會錯誤




































list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
    if (!l1)
        return l2;
    if (!l2)
        return l1;

    list_ele_t *head = NULL; /* pseudo head */
    list_ele_t *tmp = NULL;
    /* decide the first element and use it as pseudo head */
    if (strcasecmp(l1->value, l2->value) < 0) {
        head = l1;
        l1 = l1->next;
    } else {
        head = l2;
        l2 = l2->next;
    }
    /* merge remaining elements to pseudo head */
    tmp = head;
    while (l1 && l2) {
        if (strcasecmp(l1->value, l2->value) < 0) {
            tmp->next = l1;
            l1 = l1->next;

        } else {
            tmp->next = l2;
            l2 = l2->next;
        }
        tmp = tmp->next;
    }
    if (l1)
        tmp->next = l1;
    if (l2)
        tmp->next = l2;
    return head;
}

變更排序所用的函式為 natural sort

為了使用 natural sort，需先修改 Makefile 來將 strnatcmp.[ch] 加入
(相關的 dependency 會放在 .natsort 內)

...
NAT_DIR := natsort
...
OBJS := qtest.o report.o console.o harness.o queue.o \
        random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
        natsort/strnatcmp.o
...
%.o: %.c
	@mkdir -p .$(DUT_DIR)
	@mkdir -p .$(NAT_DIR)
	$(VECHO) "  CC\t$@\n"
	$(Q)$(CC) -o $@ $(CFLAGS) -c -MMD -MF .$@.d $<
...
clean:
	rm -f $(OBJS) $(deps) *~ qtest /tmp/qtest.*
	rm -rf .$(DUT_DIR)
	rm -rf .$(NAT_DIR)
	rm -rf *.dSYM
	(cd traces; rm -f *~)

接著需要修改 queue.c 中使用的排序方式及 make test 時驗證 q_sort 結果的部分，也就是 queue.c 與 qtest.c 這兩個檔案的部分內容

queue.c:
實際需要修改的地方是 merge sort 使用的 merge，將原先使用的 strcasecmp 修改為 strnatcmp 即可
qtest.c:
字串排序結果是在 do_sort 中驗證的，將原先使用的 strcasecmp 修改為 strnatcmp 即可

至此已將排序函式變更為 natural sort，然而編譯時 Cppcheck 會報錯，如下

natsort/strnatcmp.c:112:14: style: The scope of the variable 'ca' can be reduced. [variableScope]
    nat_char ca, cb;
             ^
natsort/strnatcmp.c:112:18: style: The scope of the variable 'cb' can be reduced. [variableScope]
    nat_char ca, cb;
                 ^
natsort/strnatcmp.c:170:0: style: The function 'strnatcasecmp' is never used. [unusedFunction]

^

Fail to pass static analysis.

直接觀察 strnatcmp.c 相關的部分，區域變數 ca 和 cb 的用途是用來儲存接下來要比較的字元，但由於整個比較的過程都不會 (也不該) 修改到原本的字串，因此其實不用多宣告這兩個區域變數，也就是捨棄原本先宣告 ca = a[ai] 再使用 ca 的作法，改為直接使用 a[ai] 即可，修改完成後就可以正常編譯了

















































static int strnatcmp0(nat_char const *a, nat_char const *b, int fold_case)
{
    int ai = 0;
    int bi = 0;
    int fractional, result;

    while (1) {
        /* skip over leading spaces or zeros */
        while (nat_isspace(a[ai]))
            ++ai;

        while (nat_isspace(b[bi]))
            ++bi;

        /* process run of digits */
        if (nat_isdigit(a[ai]) && nat_isdigit(b[bi])) {
            fractional = (a[ai] == '0' || b[bi] == '0');

            if (fractional) {
                if ((result = compare_left(a + ai, b + bi)) != 0)
                    return result;
            } else {
                if ((result = compare_right(a + ai, b + bi)) != 0)
                    return result;
            }
        }

        if (!a[ai] && !b[bi]) {
            /* The strings compare the same.  Perhaps the caller
                   will want to call strcmp to break the tie. */
            return 0;
        }

        if (fold_case) {
            if (nat_toupper(a[ai]) < nat_toupper(b[bi]))
                return -1;
            if (nat_toupper(a[ai]) > nat_toupper(b[bi]))
                return +1;
        } else {
            if (a[ai] < b[bi])
                return -1;
            if (a[ai] > b[bi])
                return +1;
        }

        ++ai;
        ++bi;
    }
}

最後是驗證的部分，原先在測試 q_sort 正確性的 trace files 中，無論是使用 strcasecmp 或是 strnatcmp 都會給出一樣的結果，因此根據 natural sort 提供的測試排序文件 test-word 來寫一個專門測試 natural sort 是否正確運作的 traces/trace-18-natsort.cmd，實測結果也顯示正確

strcasecmp           strnatcmp
1-02        |        1-02
1-2         |        1-2
1-20        |        1-20
10-20       |        10-20
fred        |        fred
jane        |        jane
pic01       |        pic01
pic02       |        pic02
pic02000    |        pic02a
pic02a      |        pic02000
pic05       |        pic05
pic100      |        pic2
pic100a     |        pic3
pic120      |        pic4
pic121      |        pic100
pic2        |        pic100a
pic3        |        pic120
pic4        |        pic121
tom         |        tom
x2-g8       |        x2-g8
x2-y08      |        x2-y08
x2-y7       |        x2-y7
x8-y8       |        x8-y8

以 Valgrind 分析記憶體問題

先前使用遞迴的方式 merge 時遇到的問題一樣可以用 valgrind 分析，錯誤訊息明確的指出 stack overflow

+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
==27612== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==27612== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==27612== Can't extend stack to 0x1ffe8010a8 during signal delivery for thread 1:
==27612==   no stack segment
==27612== 
==27612== Process terminating with default action of signal 11 (SIGSEGV)

Valgrind - Massif

使用介紹

Massif 可以分析程式執行過程 heap 的使用狀態，使用的方法為

$ valgrind --tool=massif ./qtest

以本作業來說，也可以選擇製作或使用已有的 trace file 來進行分析

$ valgrind --tool=massif ./qtest -f trace

註：最初使用時會報錯 Unknown option: --show-leak-kinds=all，將 .valgrindrc 裡面 --show-leak-kinds=all 刪掉即可 (.valgrindrc 裡面紀錄的是預設使用的參數)

分析結果預設存於同目錄下的 massif.out.<pid> 檔案中 (可以使用參數 --massif-out-file 指定不同的檔案)，得到分析結果後，可以進一步將其圖像化

$ ms_print massif.out.<pid>

圖像中的 : 代表一般記錄點、@ 代表詳細記錄點、# 代表峰值位置，y 軸為 heap 使用量，x 軸預設為 instruction 的執行數量，可使用參數 --time-unit=<i|ms|B> 更改

--time-unit=<i|ms|B> [default: i]
The time unit used for the profiling.
There are three possibilities:
1. instructions executed (i), which is good for most cases;
2. real (wallclock) time (ms, i.e. milliseconds), which is sometimes useful;
3. bytes allocated/deallocated on the heap and/or stack (B), which is useful for very short-run programs, and for testing purposes, because it is the most reproducible across different machines.

Massif 可配合不同的參數調整分析的方式，詳見 Manual

實測 heap 使用量

接下來分別以 --time-unit=i(預設) 與 --time-unit=B 兩種參數來分析以下自訂指令

new
ih head 100000
it tail 100000
reverse
sort
size
quit

觀察 --time-unit=i 的分析結果，可以看到程式的過程一共約執行了 429.1 Mi，然而峰值在位置 83.6 Mi 時就出現了，這是因為我們執行的指令實際上只有 ih head 100000 和 it tail 100000 會大量增加 heap 的使用量，其餘的 reverse sort quit 主要改變的是 stack 而不是 heap，這也是為何到達峰值後，heap 的使用量幾乎都維持一致直到程式結束

$ ms_print massif.out.32595
--------------------------------------------------------------------------------
Command:            ./qtest
Massif arguments:   (none)
ms_print arguments: massif.out.32595
--------------------------------------------------------------------------------


    MB
24.42^             #                                                          
     |            :#:::::::::::::::::::::::::::::::::::::::::::::::::::::     
     |           ::#:                                                  ::     
     |           ::#:                                                  :::    
     |          :::#:                                                  :::    
     |         @:::#:                                                  :::    
     |         @:::#:                                                  :::    
     |        :@:::#:                                                  ::::   
     |        :@:::#:                                                  ::::   
     |       ::@:::#:                                                  :::::  
     |      @::@:::#:                                                  :::::  
     |     :@::@:::#:                                                  :::::  
     |     :@::@:::#:                                                  :::::  
     |    ::@::@:::#:                                                  :::::  
     |   :::@::@:::#:                                                  :::::: 
     |   @::@::@:::#:                                                  :::::: 
     |  :@::@::@:::#:                                                  :::::: 
     |  :@::@::@:::#:                                                  :::::::
     | ::@::@::@:::#:                                                  :::::::
     |:::@::@::@:::#:                                                  :::::::
   0 +----------------------------------------------------------------------->Mi
     0                                                                   429.1

Number of snapshots: 53
 Detailed snapshots: [8, 9, 17, 26, 34 (peak)]

觀察 --time-unit=B 的分析結果，可以發現 heap 先線性成長到峰值，接著再線性下降直到程式結束，這是因為 ih head 100000 和 it tail 100000 實質上就是重複 100000 次相同指令，所以是線性成長，接著 quit 時會使用 q_free 將記憶體逐一釋放，所以是線性下降
另外，原先 --time-unit=i 的分析結果在峰值後會出現一段 heap 用量幾乎沒有變動的區域，這個區域在改用 --time-unit=B 分析後會直接消失，這是因為此時 x 座標是 heap 的使用/釋放量，既然 heap 用量沒有改變，x 座標就不會移動

$ ms_print massif.out.32584
--------------------------------------------------------------------------------
Command:            ./qtest
Massif arguments:   --time-unit=B
ms_print arguments: massif.out.32584
--------------------------------------------------------------------------------


    MB
24.42^                                    #                                   
     |                                  ::#::                                 
     |                                 :::#: :                                
     |                               :::::#: :::                              
     |                             :@: :::#: :: :                             
     |                           :::@: :::#: :: ::::                          
     |                          :: :@: :::#: :: ::::::                        
     |                        :::: :@: :::#: :: :::::@:                       
     |                       ::::: :@: :::#: :: :::::@:::                     
     |                    :::::::: :@: :::#: :: :::::@:::::                   
     |                  :::: ::::: :@: :::#: :: :::::@::::::                  
     |                 :: :: ::::: :@: :::#: :: :::::@:::::::::               
     |              ::::: :: ::::: :@: :::#: :: :::::@:::::::::::             
     |             :: ::: :: ::::: :@: :::#: :: :::::@::::::::::::            
     |           :::: ::: :: ::::: :@: :::#: :: :::::@:::::::::::::@          
     |          :: :: ::: :: ::::: :@: :::#: :: :::::@:::::::::::::@:         
     |       ::::: :: ::: :: ::::: :@: :::#: :: :::::@:::::::::::::@::::      
     |     :::: :: :: ::: :: ::::: :@: :::#: :: :::::@:::::::::::::@::::::    
     |    :: :: :: :: ::: :: ::::: :@: :::#: :: :::::@:::::::::::::@::::::@   
     |  :::: :: :: :: ::: :: ::::: :@: :::#: :: :::::@:::::::::::::@::::::@:: 
   0 +----------------------------------------------------------------------->MB
     0                                                                   48.47

Number of snapshots: 71
 Detailed snapshots: [1, 23, 28 (peak), 38, 55, 65]

Massif 的結果會顯示峰值所在的 snapshot，分別是兩種分析結果的 34 及 28 這兩筆，挑選出來後直接比對，可以發現 heap 的使用量確實是一模一樣的，差別僅在 x 軸的不同

--time-unit=i
--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 34     83,560,433       25,610,648       20,210,167     5,400,481            0
 
--time-unit=B
--------------------------------------------------------------------------------
  n        time(B)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 28     25,611,112       25,610,648       20,210,167     5,400,481            0

Massif 在特定的 snapshot 會做詳細的紀錄 (同時也是圖像上的 @ 與 # 所在的位置)，其中 heap 的總量可再被分為兩種

useful-heap
程式執行時向系統請求的 heap 量
extra-heap
heap 用來記錄管理資訊的空間 (header 與 footer)、以及為了alignment 而增加的空間，這兩個也就是所謂的 internal fragmentation

挑選峰值的紀錄觀察，可以發現只有 78.91% 的 heap 使用量是 useful-heap，這代表 internal fragmentation 相對明顯
接著看下方的樹狀圖，先觀察前兩階的數據，可以發現 q_insert_head 與 q_insert_tail 都使用了 21.87% 與 17.57% 的用量，而它們的用量加起來幾乎就是 useful-heap 的總量，這符合前面觀察到的結果，因為整個測試過程中只有 ih 和 it 會新增 elements

--------------------------------------------------------------------------------
  n        time(B)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 26     24,457,704       24,457,240       19,300,056     5,157,184            0
 27     24,951,528       24,951,064       19,689,714     5,261,350            0
 28     25,611,112       25,610,648       20,210,167     5,400,481            0
78.91% (20,210,167B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->78.87% (20,200,064B) 0x10C6E9: test_malloc (harness.c:137)
| ->21.87% (5,600,000B) 0x10CC56: q_insert_head (queue.c:58)
| | ->21.87% (5,600,000B) 0x10A77F: do_insert_head (qtest.c:213)
| |   ->21.87% (5,600,000B) 0x10B8E8: interpret_cmda (console.c:220)
| |     ->21.87% (5,600,000B) 0x10BE5C: interpret_cmd (console.c:243)
| |       ->21.87% (5,600,000B) 0x10C5CB: cmd_select (console.c:609)
| |         ->21.87% (5,600,000B) 0x10C672: run_console (console.c:630)
| |           ->21.87% (5,600,000B) 0x10AD97: main (qtest.c:771)
| |             
| ->21.87% (5,600,000B) 0x10CCF5: q_insert_tail (queue.c:89)
| | ->21.87% (5,600,000B) 0x10A4F8: do_insert_tail (qtest.c:298)
| |   ->21.87% (5,600,000B) 0x10B8E8: interpret_cmda (console.c:220)
| |     ->21.87% (5,600,000B) 0x10BE5C: interpret_cmd (console.c:243)
| |       ->21.87% (5,600,000B) 0x10C5CB: cmd_select (console.c:609)
| |         ->21.87% (5,600,000B) 0x10C672: run_console (console.c:630)
| |           ->21.87% (5,600,000B) 0x10AD97: main (qtest.c:771)
| |             
| ->17.57% (4,500,000B) 0x10CC7C: q_insert_head (queue.c:63)
| | ->17.57% (4,500,000B) 0x10A77F: do_insert_head (qtest.c:213)
| |   ->17.57% (4,500,000B) 0x10B8E8: interpret_cmda (console.c:220)
| |     ->17.57% (4,500,000B) 0x10BE5C: interpret_cmd (console.c:243)
| |       ->17.57% (4,500,000B) 0x10C5CB: cmd_select (console.c:609)
| |         ->17.57% (4,500,000B) 0x10C672: run_console (console.c:630)
| |           ->17.57% (4,500,000B) 0x10AD97: main (qtest.c:771)
| |             
| ->17.57% (4,500,000B) 0x10CD1B: q_insert_tail (queue.c:94)
| | ->17.57% (4,500,000B) 0x10A4F8: do_insert_tail (qtest.c:298)
| |   ->17.57% (4,500,000B) 0x10B8E8: interpret_cmda (console.c:220)
| |     ->17.57% (4,500,000B) 0x10BE5C: interpret_cmd (console.c:243)
| |       ->17.57% (4,500,000B) 0x10C5CB: cmd_select (console.c:609)
| |         ->17.57% (4,500,000B) 0x10C672: run_console (console.c:630)
| |           ->17.57% (4,500,000B) 0x10AD97: main (qtest.c:771)
| |             
| ->00.00% (64B) in 1+ places, all below ms_print's threshold (01.00%)
| 
->00.04% (10,103B) in 1+ places, all below ms_print's threshold (01.00%)

記憶體對齊

從你所不知道的 C 語言：記憶體管理、對齊及硬體特性可以知道在 64-bit 的系統下，malloc 會以 16 bytes 進行對齊，而原先 heap block 用來記錄管理資訊的空間 header 與 footer 會共佔 8 bytes，也就是說如果 elements 中儲存的字串低於 8 個字 (含 null terminator)，一律會因為 alignment 要求而實際 malloc 8 bytes，同理當字串長度為 9~24 個字時皆會 malloc 24 bytes

這個現象也可以用 massif 觀察，使用以下的指令進行實驗，主要目的是驗證使用字串為 "h" 與 "t" 時的 heap 使用量其實與字串為 "head" 與 "tail" 時一樣

new
ih h 100000
it t 100000
free
new
ih head 100000
it tail 100000
quit

從結果可以看到 heap 總使用量根本一樣，而字串為 "head" 與 "tail" 時，因為程式實際索取的記憶體大小較大，產生的 useful-heap 也確實比較高

string: "h", "t"
--------------------------------------------------------------------------------
  n        time(B)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 18     25,611,112       25,610,648       19,610,164     6,000,484            0
76.57% (19,610,164B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.

string: "head", "tail"
--------------------------------------------------------------------------------
  n        time(B)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 28     25,611,112       25,610,648       20,210,167     5,400,481            0
78.91% (20,210,167B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.

最後再追加一個比較，目的是呈現當字串長度為 9~24 個字時會 malloc 24 bytes
註：massif 沒辦法同時抓取複數峰值，因此只呈現圖像結果

new
ih h 100000
it t 100000
free
new
ih head 100000
it tail 100000
free
new
ih headhead 100000
it tailtail 100000
quit

結果很明顯，字串長度 8 以內 heap 的使用量都一樣，字串長度一到 9 bytes 就能觀察到 heap 使用量提升



    MB
27.48^                                                           #            
     |                                                           #            
     |                                                          :#            
     |           @                      ::                     ::#:           
     |          :@:                    ::                      ::#::          
     |          :@:                    :: :                   :::#::          
     |         @:@:::                  :: :                  @:::#:::         
     |         @:@::                 :::: ::                 @:::#::::        
     |        :@:@:: @               : :: :::               :@:::#::::        
     |        :@:@:: @              :: :: :::              ::@:::#:::::       
     |      :::@:@:: @:             :: :: ::::             ::@:::#::::::      
     |      : :@:@:: @::           ::: :: :::::           :::@:::#:::::@      
     |     :: :@:@:: @::           ::: :: :::::@         ::::@:::#:::::@:     
     |     :: :@:@:: @:::         :::: :: :::::@        :::::@:::#:::::@::    
     |    ::: :@:@:: @:::        ::::: :: :::::@:       :::::@:::#:::::@::    
     |   :::: :@:@:: @:::::     :::::: :: :::::@       @:::::@:::#:::::@:::   
     |   :::: :@:@:: @::::     ::::::: :: :::::@ :     @:::::@:::#:::::@::::  
     |   :::: :@:@:: @::::     ::::::: :: :::::@ :     @:::::@:::#:::::@::::  
     | :::::: :@:@:: @:::: :  :::::::: :: :::::@ ::   :@:::::@:::#:::::@::::: 
     |:: :::: :@:@:: @:::: :: @::::::: :: :::::@ ::@ ::@:::::@:::#:::::@::::::
   0 +----------------------------------------------------------------------->MB
     0                                                                   152.0

分析 Makefile

閱覽 Makefile 有助於了解整個程式的架構，然而點開 Makefile 後發現~~根本看不懂~~需要花點時間來理解內容，以下會分段逐步理解 Makefile 的內容，許多用法在 Makefile 語法和示範中已經有詳細示範，將不再重複說明
完整的 Makefile 請參照 Github

首次執行 make 會自動安裝 git hook:
直接 make 預設會執行第一個 target，也就是 all 這個項目，所以除了編譯 qtest 之外，還會執行安裝 git hook 的腳本

all: $(GIT_HOOKS) qtest

$(GIT_HOOKS):
	@scripts/install-git-hooks
	@echo

make VERBOSE=1 可以顯示詳細編譯訊息
- @ 的作用是該行的指令不會被顯示
- @true 則追加該行指令直接被視為成功的作用
- 因此 " LD\t$@\n" 這行如果前面從 @printf 改為 @ 會出錯，需要追加 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

Dependency 的部分相當有趣，查資料後發現本作業中使用類似 Auto-Dependency Generation 的方法來處理 dependency 的問題
- deps := $(OBJS:%.o=.%.o.d) 使用自動變數替換，也就是每個 dependency 檔案名稱都是物件檔結尾加上 .d
- -MMD 代表僅考慮 user header files 不包含 system head files，-MF 是指定輸出 dependency 檔案的名稱
- -include $(deps) 須放置在檔案的最後，告訴 make 需要 dependency 檔案的名稱，前置的 - 代表就算執行失敗也不強制結束 make 的執行

OBJS := qtest.o report.o console.o harness.o queue.o \
        random.o dudect/constant.o dudect/fixture.o dudect/ttest.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)

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

valgrind 的支援
- 2>&1 指的是將 stderr 的輸出重新導向到 stdout
- /dev/null 概念類似黑洞，進去的東西都會消失
- || 代表若左邊執行出錯，就執行右邊的內容
- 因此 valgrind_existence 執行的意思就是 "檢查 valgrind 版本 (但無論成功失敗都不列出結果)，如果檢查失敗就顯示右邊的錯誤訊息"
- $(MAKE) 代表將這行當作 make 來執行，詳見 Manual
- $(eval expression) 會先將 expression 展開，接著再將 expression 的內容視為 Makefile 的一部分並執行，與直接將 expression 寫在 Makefile 的差別為，後面的 shell 指令 mktemp 只有在 make valgrind 時才會執行並取得檔案名稱，詳見 Manual
- sed -i "s/alarm/isnan/g" $(patched_file)，其中 s/alarm/isnan/g 不是路徑，是 sed 用來替換內容的表示法，這裡的意思是 "將 $(patched_file) 中的所有的 alarm 替換成 iasnan"，詳見 Manual
  - 由於 valgrind 會大幅度的增加程式的執行時間，將 alarm 去除可以避免在 qtest 中設置 timer，去除原先對執行時間的限制
  - 相關的語法可以參閱 sed - stream editor 以及 the s command (感謝 Randy870819 提供)

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
	@echo
	@echo "Test with specific case by running command:" 
	@echo "scripts/driver.py -p $(patched_file) --valgrind -t <tid>"

dudect

dudect 以兩種不同類別的資料來測試程式的執行時間，再以統計的方式分析兩者的執行時間的平均值是否有差異，若無法證明平均值有差異，則程式的執行時間可能為常數 (constant time)
dudect 的優點是不需要執行平台的硬體資訊 (這也是本題可以使用虛擬機跑的原因之一)。執行的過程可以分為三個步驟

量測執行時間
使用的資料分為固定資料及隨機資料兩種 (fix-vs-random test)，同時為了降低環境因素的影響，每次量測選定的資料種類也是隨機的，執行時間則是根據 CPU cycle 來計算
後處理
每次量測時間後，可以在統計分析前先進行後處理，例如去除一定數值以外的資料 (cropping)，來避免因程式執行過程中被系統插斷造成的正偏差。另外，可以根據後面想執行的統計分析，先在此步驟先進行資料處理
統計分析
dudect 使用 Welch's t-test 來分析兩種資料的結果，如果檢定結果無法否定 "兩種資料具有相同的平均數" 這個零假設 (null hypothesis)，就代表兩種資料很有可能具有一樣的平均數，也就是程式執行時間很可能是常數

t-test

t-test 是一種假說檢定 (statistical hypothesis test)，指零假設 (null hypothesis) 成立時的任一檢定統計會具有 Student’s t-distribution
Student's t-test 和 Welch's t-test 皆為雙樣本的 t-test 應用，Student's t-test 同時假設兩個母體 (population) 具有相同的變異數，Welch's t-test 則無此假設
本作業中使用的是 Welch's t-test，因為我們沒辦法得知母體的變異數

Student’s t-distribution

用於根據小樣本來估計 "呈常態分布且變異數未知的總體" 的平均值
自由度
$ν$ 越大，t-distribution 越接近常態分佈
也簡稱為 t-distribution

分析本作業中如何實作 dudect

從 qtest.c 裡面可以看到使用 is_insert_tail_const 與 is_size_const 來判斷，其函數的定義在 dudect/fixture.c 內，由於整個程式的架構非常複雜，現階段先釐清整體實作的架構，許多輔助函數的實作之後再探討

`is_size_const`



















bool is_size_const(void)
{
    bool result = false;
    t = malloc(sizeof(t_ctx));
    for (int cnt = 0; cnt < test_tries; ++cnt) {
        printf("Testing size...(%d/%d)\n\n", cnt, test_tries);
        init_once();
        for (int i = 0;
             i <
             enough_measurements / (number_measurements - drop_size * 2) + 1;
             ++i)
            result = doit(1);
        printf("\033[A\033[2K\033[A\033[2K");
        if (result == true)
            break;
    }
    free(t);
    return result;
}

t_ctx 是一個儲存統計用資料的資料結構，相關的意義可以在後續的 t-push 中得知
- mean 是平均值
- m2 是離均差之合 (aggregates of squared distance from the mean)
- n 是資料數量

typedef struct {
    double mean[2];
    double m2[2];
    double n[2];
} t_ctx;

第一個迴圈 for (int cnt = 0; cnt < test_tries; ++cnt) 代表最多會進行 10 次測試，如果結果為真，會直接跳離迴圈 (也就是結果顯示為 constant time)
init_once 會將 t 的所有資料成員初始化為 0.0，q 初始化為 NULL
實際的計算與量測在 doit 中實施
doit 一次會進行 (number_measurements - drop_size * 2) 次的測試，而統計需求共需 enough_measurements = 10000 次測試數據

`doit`





























static bool doit(int mode)
{
    int64_t *before_ticks = calloc(number_measurements + 1, sizeof(int64_t));
    int64_t *after_ticks = calloc(number_measurements + 1, sizeof(int64_t));
    int64_t *exec_times = calloc(number_measurements, sizeof(int64_t));
    uint8_t *classes = calloc(number_measurements, sizeof(uint8_t));
    uint8_t *input_data =
        calloc(number_measurements * chunk_size, sizeof(uint8_t));

    if (!before_ticks || !after_ticks || !exec_times || !classes ||
        !input_data) {
        die();
    }

    prepare_inputs(input_data, classes);

    measure(before_ticks, after_ticks, input_data, mode);
    differentiate(exec_times, before_ticks, after_ticks);
    update_statistics(exec_times, classes);
    bool ret = report();

    free(before_ticks);
    free(after_ticks);
    free(exec_times);
    free(classes);
    free(input_data);

    return ret;
}

prepare_inputs(input_data, classes)
- 總共準備 number_measurements = 150 個資料
- classes 的內容只會是 0 和 1 ，用來區分兩種資料類別
- input_data 的每個成員大小為 chunk_size * sizeof(uint8_t)，也就是 16 bytes
- class 0 的 input_data 的前兩個 bytes 會被設置為 0
- 在此函數內會一同隨機設置用來測試的字串 static char random_string[100][8]
- 產生隨機數值的方法應該是從這裡偷過來的
measure
- assert 是一個保護函數 (man assert)
- 根據 mode 的數值來判斷是要分析 q_size 還是 q_insert_tail ，另外這裡有用到 anonymous enum 的技巧 enum { test_insert_tail, test_size }
- 從 for (size_t i = drop_size; i < number_measurements - drop_size; i++) 可以看出實際使用的資料會從頭尾再扣除 drop_size = 20，查閱原始 Github 專案並比對內容，這麼做的目的就是 dudect 步驟二的 cropping，只是本作業中有對 cropping 的時間點稍作修改
  - 原始 Github 專案共使用 first order uncropped、cropped、second order uncropped 三種方式來計算最大 t 值，本作業中大幅度省略至只使用單一閥值來 cropping
- 為了避免和主測試函數的內容混淆，同時維持測試環境的一致性，這邊會先使用 dut_new 與 dut_insert_head 做出測試用的 linked-list
- 實際測試時間的函數被包在 before_ticks[i] = cpucycles() 與 after_ticks[i] = cpucycles() 之間，執行時間以 CPU clock cycles 當基準計算
- 由 *(uint16_t *) (input_data + i * chunk_size) % 10000) 可以看出字串插入的隨機數量是根據 input_data 的前兩個 bytes 決定，而且最多不超過 10000。同時由此可以看出 class 0 的數據實際上根本不會插入字串
differentiate
- 計算執行時間 exec_times[i] = after_ticks[i] - before_ticks[i]
update_statistics
- 選定納入使用的數據，並呼叫 t-push 對其進行前處理
- CPU cycle counter overflowed 的資料與 drop_size 涵蓋的資料會在此被過濾掉
t-push
- 使用 Welford's online algorithm 計算實行 Welch's t-test 所需的資料，計算結果儲存於 t 指向的資料結構中
report
- 使用 t_compute 計算出 t 值，判斷是否在閥值範圍內並回傳判斷結果

`cpucycles`










static inline int64_t cpucycles(void)
{
#if defined(__i386__) || defined(__x86_64__)
    unsigned int hi, lo;
    __asm__ volatile("rdtsc\n\t" : "=a"(lo), "=d"(hi));
    return ((int64_t) lo) | (((int64_t) hi) << 32);
#else
#error Unsupported Architecture
#endif
}

執行時間以 CPU clock cycles 當基準計算
詳細方法可參閱 Code Execution Times: IA-32/IA-64 Instruction Set Architecture (現階段我還看不太懂 asm 的用法)

`t_compute`










double t_compute(t_ctx *ctx)
{
    double var[2] = {0.0, 0.0};
    var[0] = ctx->m2[0] / (ctx->n[0] - 1);
    var[1] = ctx->m2[1] / (ctx->n[1] - 1);
    double num = (ctx->mean[0] - ctx->mean[1]);
    double den = sqrt(var[0] / ctx->n[0] + var[1] / ctx->n[1]);
    double t_value = num / den;
    return t_value;
}

實際計算 Welch’s t-test 的函式
計算檢定量
$t = \frac{{\overset{―}{X}}_{1} - {\overset{―}{X}}_{2}}{\sqrt{\frac{s_{1}^{2}}{N_{1}} + \frac{s_{2}^{2}}{N_{2}}}}$
- $\bar{X}$ 為平均值，也就是 ctx->mean
- $s^{2}$ 為標準差平方，也就是 ctx->m2
- $N$ 為資料數量，也就是 ctx->n
本作業直接以固定的 t 值 t_threshold_moderate = 10 進行雙尾檢定 (two-tail test)，也就是判斷 t 的絕對值是否在接受範圍內，來判斷是否為 constant time
閥值越大，I 型錯誤 (執行時間被誤認為非常數) 的機率會降低，但 II 型錯誤 (執行時間被誤認為常數) 的機率會增加
原先的 Welch’s t-test 需再算出自由度
$ν$ 來獲得對應的 t-distribution，根據設定的信賴區間及 t-distribution 決定 t 的閥值，再進行雙尾檢定

$ν \approx \frac{{(\frac{s_{1}^{2}}{N_{1}} + \frac{s_{2}^{2}}{N_{2}})}^{2}}{\frac{s_{1}^{4}}{N_{1}^{2} ν_{1}} + \frac{s_{2}^{4}}{N_{2}^{2} ν_{2}}}, ν_{1} = N_{1} - 1, ν_{2} = N_{2} - 1$

RIO 套件 (Robust I/O)

RIO 套件是 CS:APP 中提供的一種 system I/O wrapper 套件，其內容建立於原本的 read 與 write 之上，原始內容可詳見 csapp.c 與 csapp.h
RIO 套件具有以下特點

被 signal handler 中斷後 (會導致 EINTR 錯誤)，會自動嘗試重新執行，直到遇到 EOF 或是達到指定的讀取大小
具有 application-level buffer，可大幅降低實際呼叫 system call 的次數，進而提升效能
可以方便的用於 socket
thread-safe (之後研讀 CS:APP 第 12 章會再探討並補充進來)

RIO 套件的精隨在於 rio_read 以及對應的 rio 結構體 rio_t

#define RIO_BUFSIZE 8192
typedef struct {
    int rio_fd;                /* Descriptor for this internal buf */
    int rio_cnt;               /* Unread bytes in internal buf */
    char *rio_bufptr;          /* Next unread byte in internal buf */
    char rio_buf[RIO_BUFSIZE]; /* Internal buffer */
} rio_t;

/* 
 * rio_read - This is a wrapper for the Unix read() function that
 *    transfers min(n, rio_cnt) bytes from an internal buffer to a user
 *    buffer, where n is the number of bytes requested by the user and
 *    rio_cnt is the number of unread bytes in the internal buffer. On
 *    entry, rio_read() refills the internal buffer via a call to
 *    read() if the internal buffer is empty.
 */
static ssize_t rio_read(rio_t *rp, char *usrbuf, size_t n)
{
    int cnt;

    while (rp->rio_cnt <= 0) {  /* Refill if buf is empty */
	rp->rio_cnt = read(rp->rio_fd, rp->rio_buf, 
			   sizeof(rp->rio_buf));
	if (rp->rio_cnt < 0) {
	    if (errno != EINTR) /* Interrupted by sig handler return */
		return -1;
	}
	else if (rp->rio_cnt == 0)  /* EOF */
	    return 0;
	else 
	    rp->rio_bufptr = rp->rio_buf; /* Reset buffer ptr */
    }

    /* Copy min(n, rp->rio_cnt) bytes from internal buf to user buf */
    cnt = n;          
    if (rp->rio_cnt < n)   
	cnt = rp->rio_cnt;
    memcpy(usrbuf, rp->rio_bufptr, cnt);
    rp->rio_bufptr += cnt;
    rp->rio_cnt -= cnt;
    return cnt;
}

在使用 RIO 套件前，會先建立並初始化一個 rio_t 物件
rio_read 在被呼叫後，會先檢查 rio_t 物件中的 buffer 是否還有內容可以被使用
- 若有 - 直接讀取 rio_buf
- 若無 - 呼叫 read 讀取最多至 8192 bytes 的內容至 rio_buf
也就是說使用者呼叫 rio_read 取得的內容總是會從 rio_buf 取得，rio_read 同時會負責更新 rio_buf 的內容

`qtest` 使用 RIO 套件的考量點

qtest 使用 RIO 套件的優勢會體現於 trace files 的讀取，若使用無緩衝的 read 來讀取指令，需要重複以 read 讀取單個字元直到遇到 \n 為止，如此一來會因為頻繁的 system call 造成效能低落
改用 RIO 套件的方法後，會將整個 trace file 的內容存入 rio_buf，接著 readline 會從 rio_buf 內讀出指令來執行，只有當 rio_buf 內容都使用完畢 (也就是跑完整個 trace file 的內容)，才會再次將下一個 trace file 的內容完整存入 rio_buf

`qtest` 實際使用 RIO 套件的方式

觀察 qtest.c 及 console.c 可歸納出整體的呼叫順序，qtest 首先會在 run_console 初始化 rio_t 物件的空間，接著 cmd_select 會負責從 rio_buf 取得輸入的字串並交給後續的 interpret_cmd 執行指令，cmd_select 中的 readline 則是實際讀取與更新 buffer 的函數 (等同於 RIO 套件的 rio_read)

main → run_console → cmd_select → interpret_cmd → parse_args

`run_console`

bool run_console(char *infile_name)
{
    if (!push_file(infile_name)) {
        report(1, "ERROR: Could not open source file '%s'", infile_name);
        return false;
    }

    while (!cmd_done())
        cmd_select(0, NULL, NULL, NULL, NULL);
    return err_cnt == 0;
}

static bool push_file(char *fname)
{
    int fd = fname ? open(fname, O_RDONLY) : STDIN_FILENO;
    if (fd < 0)
        return false;

    if (fd > fd_max)
        fd_max = fd;

    rio_ptr rnew = malloc_or_fail(sizeof(rio_t), "push_file");
    rnew->fd = fd;
    rnew->cnt = 0;
    rnew->bufptr = rnew->buf;
    rnew->prev = buf_stack;
    buf_stack = rnew;

    return true;
}

rio_t 物件在 push_file 內產生，但此時 rio_buf 還沒有內容
最後將產生的物件以 linked list 的方式插入 buf_stack 所指向 list
觀察 console.c 中定義的 rio_t 資料結構以及 buf_stack 指標的使用方式，可以發現 console 將每個 rio_t 物件以 stack 的邏輯在管理，這也是為何新增及刪除 rio_t 物件的函式名稱分別叫做 push_file 及 pop_file

#define RIO_BUFSIZE 8192
typedef struct RIO_ELE rio_t, *rio_ptr;

struct RIO_ELE {
    int fd;                /* File descriptor */
    int cnt;               /* Unread bytes in internal buffer */
    char *bufptr;          /* Next unread byte in internal buffer */
    char buf[RIO_BUFSIZE]; /* Internal buffer */
    rio_ptr prev;          /* Next element in stack */
};

static rio_ptr buf_stack;

`cmd_select`

流程略為複雜，直接以 flowchart 呈現其運作邏輯，select 的部分可參閱下個章節的討論

interpret_cmd 會呼叫 parse_args 來將 readline 回傳的內容解析為指令及參數，最後根據指令及參數呼叫 interpret_cmda 來執行該指令內容
執行命令的部分，作業導讀的部分已經說明得很清楚了

`readline`

邏輯類似 RIO 套件的 rio_read
與 RIO 套件不同的地方是，被 signal 中斷而未讀取任何資料時 (EINTR)，不會自動重新執行 read，而會被判斷成 EOF

解釋 `select` 系統呼叫在本程式的使用方式

int select(int nfds,
           fd_set *readfds, fd_set *writefds, fd_set *exceptfds,
           struct timeval *timeout);

fd_set 是一種儲存 file descriptor (以下簡稱為 fd) 編號的集合，例如 fd 集合為 {0, 2, 7} 的 fd_set 以 binary 顯示會是 10000101。fd_set 須配合下面幾種 macro 來管理

FD_ZERO(fd_set *set) - 清空 set 內容
FD_SET(int fd, fd_set *set) - 新增 fd 至 set
FD_CLR(int fd, fd_set *set) - 將 fd 從 set 移除
FD_ISSET(int fd, fd_set *set) - 確認 fd 是否可用 (在 select 返回後使用)

select 會暫停程式並監測 fd_set 清單中紀錄的 fd，直到其中至少有一個 fd 變成可使用的狀態，返回 "可用 fd 的數量"，並將相對應的 fd_set 清單內容修改為 "可用 fd 清單" (因此每次呼叫 select 前都須 FD_ZERO 初始化清單)

監測至最大編號為 nfds 的 fd
監測 readfds 中紀錄的 fd 是否可讀
監測 writefds 中紀錄的 fd 是否可寫
監測 exceptfds 中紀錄的 fd 是否有特殊狀態
timeout 可以設定 select 要等待多久 (詳見 man select)

本作業中 select 使用在 cmd_select 內，當 read_ready 確認 rio_buf 無內容可用後，select 會暫停程式直到以下兩種情況發生

使用者輸入指令 (具體來說是按下的 ENTER 鍵)
trace file 可被讀取 (想不到哪種情況會產生這個情況)

最後 readline 才會根據 select 的結果決定是否能從 fd 讀取資料

`select` 於本作業中的必要性

以下列程式碼進行實驗

int main(int argc, char *argv[])
{
    int fds = STDIN_FILENO;
    int nfds = fds + 1;
    int result = 0;
    fd_set readfds;
    char line[10];
    memset(line, 0x0, 10);

    while (1) {
        FD_ZERO(&readfds);
        FD_SET(fds, &readfds);
        select(nfds, &readfds, NULL, NULL, NULL);
        if (FD_ISSET(fds, &readfds)) {
            result = read(fds, line, 10);
            line[result] = '\0';
            printf("input: %s", line);
        }
    }
}

執行結果如下

test
input: test
hello
input: hello

但其實如果把 select 的部份去掉，輸出結果是一樣的，差別是

使用 select 時，程式會在 select 等待輸入，輸入後 read 會直接讀取剛剛輸入的數值
單獨使用 read 時，程式會在 read 等待，直到鍵入 ENTER 才會結束

同時我還進行了另一個實驗，目的是想要知道如果 fork 後 parent 和 child 都使用 read 來讀取輸入，會不會造成 race condition。測試的方式是執行程式後，等待一秒以上再輸入文字 (因為 parent 會先 sleep(1))，此時 parent 與 child 皆執行到 read 的位置，且 child 比 parent 先執行 read

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/select.h>
#include <sys/types.h>
#include <unistd.h>

int main(int argc, char *argv[])
{
    int fds = STDIN_FILENO;
    int nfds = fds + 1;
    int result = 0;
    pid_t pid;
    fd_set readfds;
    char line[10];
    memset(line, 0x0, 10);

     if ((pid = fork()) == 0) {  /* child runs the job */
        FD_ZERO(&readfds);
        FD_SET(fds, &readfds);
        result = read(fds, line, 10);
        line[result] = '\0';
        printf("child input: %s", line);
     } else { /* parent */
     sleep(1);
        FD_ZERO(&readfds);
        FD_SET(fds, &readfds);
        result = read(fds, line, 10);
        line[result] = '\0';
        printf("parent input: %s", line);
    }
}

執行結果如下

child
child input: child
parent
parent input: parent

因此就算同時有兩個程式對同個 file descriptor 進行 read，不使用 select 仍不會產生混淆的狀態

根據上面的結果，我認為 qtest 中無需使用 select，單獨使用 read 也能達到一樣的結果

移除 qtest 中的 `select`

直接修改 console.c:598 將 select 的部分移除，測試結果發現無論是 make test 的分數，或是手動輸入指令測試，程式執行結果都找不到差別













    int result = 1; /* remove the usage of select() */
    if (result <= 0)
        return result;

    infd = buf_stack->fd;
    if (1) {
        /* Commandline input available */
        result--;
        cmdline = readline();
        if (cmdline)
            interpret_cmd(cmdline);
    }
    return result;

使用 `select` 的情境

在 GNU - Waiting for Input or Output 中有提到 select 可以使用的情境，這同時可以說明為何 qtest 中不須使用 select，因為輸入端只有一個鍵盤，如果有額外的輸入端才必須使用 select

Sometimes a program needs to accept input on multiple input channels whenever input arrives. For example, some workstations may have devices such as a digitizing tablet, function button box, or dial box that are connected via normal asynchronous serial interfaces.
You cannot normally use read for this purpose, because this blocks the program until input is available on one particular file descriptor; input on other channels won’t wake it up. You could set nonblocking mode and poll each file descriptor in turn, but this is very inefficient.
A better solution is to use the select function. This blocks the program until input or output is ready on a specified set of file descriptors, or until a timer expires, whichever comes first.

使用 antirez/linenoise 強化 `qtest` 命令列功能

linenoise 使用說明

linenoise 的 API 非常簡單，閱覽 Github 的範例就可以非常快上手

主要的 API，會將 prompt 的內容列出在 terminal，並把處理過後的輸入以字串的型態回傳
回傳的字串使用過後需 free

char *linenoise(const char *prompt);

多行編輯功能
- linenoiseSetMultiLine(0) 為單行編輯
- linenoiseSetMultiLine(1) 為多行編輯

linenoiseSetMultiLine(1);

歷史紀錄功能，讓使用者可以用上下鍵使用曾經輸入過的內容
- linenoiseHistoryAdd 將字串紀錄到歷史紀錄中
- linenoiseHistorySetMaxLen 可以設置歷史紀錄最大的長度
- linenoiseHistoryLoad 開啟儲存歷史紀錄的檔案，儲存歷史紀錄於檔案前須先開啟該檔案
- linenoiseHistorySave 儲存歷史紀錄於檔案

int linenoiseHistoryAdd(const char *line);
int linenoiseHistorySetMaxLen(int len);
int linenoiseHistoryLoad(const char *filename);
int linenoiseHistorySave(const char *filename);

命令自動補完，使用者可以按下 <TAB> 鍵來根據已輸入的部分自動補完命令
- 在使用前需先以 linenoiseSetCompletionCallback(completion) 註冊 callback funtion
- 被註冊為 callback 的函式有規定的格式，同時內容包含自動補完的判斷依據，如下

void completion(const char *buf, linenoiseCompletions *lc) {
    if (buf[0] == 'h') {
        linenoiseAddCompletion(lc,"hello");
        linenoiseAddCompletion(lc,"hello there");
    }
}

整合並應用 linenoise

將 linenoise.[ch] 納入lab0

會特別提到這點是因為 git hook 的所有設定也會套用到 linenoise，也就是說執行 git commit 前會先對 linenoise.[ch] 做 clang-format 和 cppcheck，前者沒什麼問題，直接 clang-format -i linenoise.[ch] 就可以解決，後者則會需要對原始碼進行修改，為了節省時間我選擇直接修改腳本讓 cppcheck 忽略 linenoise.[ch]，scripts/pre-commit.hook 的修改內容如下

...
CPPCHECK_IGNORE="-ilinenoise/"
...
# static analysis
$CPPCHECK $CPPCHECK_IGNORE $CPPCHECK_OPTS >/dev/null
if [ $? -ne 0 ]; then
...

在 qtest 中使用 linenoise

原本的 cmd_select 會先 select 確認 fd 是否可用，然後才使用 readline 讀取指令。如果直接改成使用 select + linenoise 會導致指令需要輸入兩次 (準確來說是第一次的輸入會被 linenoise 捨棄)，因此若要維持 select 的作用並同時使用 linenoise，勢必要修改 linenoise 的原始碼。根據前面的討論結果，我決定當 fd 為 stdin 時，不使用 select 並直接 linenoise 來讀取輸入的指令 (雖然這樣就失去 cmd_select 本來名稱所代表的用途)

實作時有幾點注意事項

需將 linenoise 回傳的字串結尾改成 \n\0 (因為原本的 lab0 會根據 \n 來判斷是否為完整的輸入，而 linenose 預設結尾不含 \n)
linenoise 回傳的字串是使用 strdup 產生的，記得 free
也可以不使用 linenoiseHistorySave，只是這樣每次執行 qtest 時不會有上次的歷史紀錄

int cmd_select(int nfds,
               fd_set *readfds,
               fd_set *writefds,
               fd_set *exceptfds,
               struct timeval *timeout)
{
...
    /* need to read command from fd */
    infd = buf_stack->fd;
    if (infd != STDIN_FILENO) { /* use trace files */
        /* prepare necessary data for select */
        if (!readfds)
            readfds = &local_readset;
        FD_SET(infd, readfds);
        if (infd >= nfds)
            nfds = infd + 1;
        if (nfds == 0)
            return 0;

        int result = select(nfds, readfds, writefds, exceptfds, timeout);
        if (result <= 0)
            return result;
        if (readfds && FD_ISSET(infd, readfds)) {
            /* Commandline input available */
            FD_CLR(infd, readfds);
            result--;
            cmdline = readline();
            if (cmdline)
                interpret_cmd(cmdline);
        }
        return result;
    } else { /* use linenoise (stdin) */
        cmdline = linenoise(prompt);
        linenoiseHistoryAdd(cmdline); /* Add to the history. */
        linenoiseHistorySave(
            "linenoise/history.txt"); /* Save the history on disk. */
        int len = strlen(cmdline);
        if (len >= (RIO_BUFSIZE - 2)) /* prevent overflow */
            len = RIO_BUFSIZE - 2;
        memcpy(linebuf, cmdline, len + 1); /* copy content to inter buffer */
        /* the original string got from linenoise is ended with \0,
         * change it to \n\0. */
        linebuf[len] = '\n';
        linebuf[len + 1] = '\0';
        free(cmdline); /* free the memory allocated by linenoise */
        cmdline = len ? linebuf : NULL;
        if (cmdline)
            interpret_cmd(cmdline);
    }
    return 0;
}

自動補完與歷史紀錄的功能需在使用前先設定好 callback，這個部分寫在 qtest.c 中，於 run_console 前執行

void completion(const char *buf, linenoiseCompletions *lc)
{
    if (buf[0] == 'f') {
        linenoiseAddCompletion(lc, "free");
    }
    if (buf[0] == 'h') {
        linenoiseAddCompletion(lc, "help");
    }
...
    if (buf[0] == 't') {
        linenoiseAddCompletion(lc, "time");
    }
}

static void linenoise_init()
{
    /* Set the completion callback. This will be called every time the
     * user uses the <tab> key. */
    linenoiseSetCompletionCallback(completion);
    /* Load history from file. The history file is just a plain text file
     * where entries are separated by newlines. */
    linenoiseHistoryLoad(
        "linenoise/history.txt"); /* Load the history at startup */
}

int main(int argc, char *argv[])
{
...
    queue_init();
    init_cmd();
    console_init();
    linenoise_init();
...
    ok = ok && run_console(infile_name);
...
}

現有程式的缺陷

在繪製 readline 的流程圖的時候，我發現 readline 不像 RIO 套件有考慮到被 signal 中斷的狀況 (可參考 RIO 套件中的 rio_read)，這會造成一個邏輯問題

被 signal 中斷而未讀取任何資料時 (EINTR)，不會自動重新執行 read，而會被判斷成 EOF

實作小型終端機命令解譯器 (待補)

我認為可以將此次作業的經驗用於改善以前寫的 CS:APP shell lab，但短時間內沒辦法完成
TODO list:

改善 git commit 的使用方式 (也應該考量如何加入 git-good-commit)
改善 signal handler 的使用方式 (例如考量使用 siglongjmp)，我覺得我原先寫的 signal handler 肯定爛透了，整體的流程也該重新考慮
應該更詳細理解 Asynchronous Signal Safety 如何達成
重新編輯筆記，使之具有更高的可讀性

參考資料 (待整理)

flowchart.js

2020q1 Homework1 (lab0)

預期目標

作業要求

開發流程

queue.h

q_size

q_new

q_free

q_insert_head & q_insert_tail

q_remove_head

q_reverse

q_sort

merge sort

變更排序所用的函式為 natural sort

以 Valgrind 分析記憶體問題

Valgrind - Massif

使用介紹

實測 heap 使用量

記憶體對齊

分析 Makefile

dudect

t-test

Student’s t-distribution

分析本作業中如何實作 dudect

is_size_const

doit

cpucycles

t_compute

RIO 套件 (Robust I/O)

qtest 使用 RIO 套件的考量點

qtest 實際使用 RIO 套件的方式

run_console

cmd_select

readline

解釋 select 系統呼叫在本程式的使用方式

select 於本作業中的必要性

移除 qtest 中的 select

使用 select 的情境

使用 antirez/linenoise 強化 qtest 命令列功能