2022q1 Homework1 (lab0)

contributed by < Eric-liau >

實驗環境

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          8
On-line CPU(s) list:             0-7
Thread(s) per core:              2
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           94
Model name:                      Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz
Stepping:                        3
CPU MHz:                         900.002
CPU max MHz:                     3500.0000
CPU min MHz:                     800.0000
BogoMIPS:                        5199.98
Virtualization:                  VT-x
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        6 MiB
NUMA node0 CPU(s):               0-7

作業要求

依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 q_sort 函式。

• 在 GitHub 上 fork lab0-c
• 依據上述指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 ``$ make test` 自動評分系統的所有項目。
• 研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
• 在 qtest 提供新的命令 shuffle，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
• 在 qtest 提供新的命令 web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令
• 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
  • 先執行 qtest 再於命令提示列輸入 help 命令，會使開啟 Address Sanitizer 觸發錯誤，應予以排除
• 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
• 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點。可對照參考 CS:APP 第 10 章重點提示
• 研讀論文〈Dude, is my code constant time?〉，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
• 指出現有程式的缺陷 (提示: 和 RIO 套件 有關) 或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request

針對 2022 年作業要求，更新上述列表
:notes: jserv

已更新

queue.c

q_new

​​​​- `INIT_LIST_HEAD(head)`: 將 head 的 *\*prev* 和 *\*next* 分別指向 head。

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));

    if (!head)
        return NULL;

    INIT_LIST_HEAD(head);
    return head;
}

q_free

想法：從 head node 開始，依序把每個node free 掉。

• temp : 因為 container 會被 free 掉，而 current 包含在 container 中，所以需要一個 struct list_head 來暫存 current 的值。
• free(l): list_for_each 不會經過 head ，所以在迴圈結束後需要把 head free 掉。
• 在寫 q_insert_head 時提示 memory leak ，檢查後發現 container->value 並未 free 掉，故加入 free(container->value)。

void q_free(struct list_head *l) 
{
    struct list_head *current, temp;
    element_t *container;
    list_for_each(current, l){
        container = list_entry(current, element_t, list);
        temp = *current;
        free(container->value);
        free(container);
        current = &temp;
    }
    free(l);
}

q_insert_head

1. 檢查 head 是否為 null
2. 分配空間給 new 並檢查是否成功分配
3. 分配空間給 new->value 並檢查是否成功分配
4. 複製 s 到 new->value
5. 將 new insert 到 queue 中

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;


    new->value = malloc(strlen(s) + 1);
    if (!new->value) {
        free(new);
        return false;
    }
    strncpy(new->value, s, strlen(s) + 1);


    list_add(&new->list, head);

    return true;
}

q_insert_tail

1. 檢查 head 是否為 null
2. 分配空間給 new 並檢查是否成功分配
3. 分配空間給 new->value 並檢查是否成功分配
4. 複製 s 到 new->value
5. 將 new insert 到 queue 中

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;


    new->value = malloc(strlen(s) + 1);
    if (!new->value) {
        free(new);
        return false;
    }
    strncpy(new->value, s, strlen(s) + 1);


    list_add_tail(&new->list, head);

    return true;
}

q_remove_head

1. 檢查 head 是否為 NULL 或 empty
2. 檢查 sp 是否為 NULL
3. 比較 strlen(node->value) + 1 和 bufsize 大小
   • 若後者較大則把 node->value 完整複製到 sp 中
   • 反之則只把 node->value 的前 bufsize - 1 個字元複製到 sp，並在 sp 的第 bufsize 個字元填上 `'\0'
4. 將 head->next 移除

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head)
        return NULL;
    if (list_empty(head))
        return NULL;


    element_t *node = list_entry(head->next, element_t, list);

    if (!sp) {
        list_del_init(head->next);
        return node;
    }
    char *str = node->value;
    int len = strlen(str) + 1;
    if (len <= bufsize)
        strncpy(sp, str, len);
    else {
        strncpy(sp, str, bufsize - 1);
        *(sp + bufsize - 1) = '\0';
    }

    list_del_init(head->next);
    return node;
}

q_remove_tail

1. 檢查 head 是否為 NULL 或 empty
2. 檢查 sp 是否為 NULL
3. 比較 strlen(node->value) + 1 和 bufsize 大小
   • 若後者較大則把 node->value 完整複製到 sp 中
   • 反之則只把 node->value 的前 bufsize - 1 個字元複製到 sp，並在 sp 的第 bufsize 個字元填上 `'\0'
4. 將 head->prev 移除

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head)
        return NULL;
    if (list_empty(head))
        return NULL;


    element_t *node = list_entry(head->prev, element_t, list);

    if (!sp) {
        list_del_init(head->prev);
        return node;
    }
    char *str = node->value;
    int len = strlen(str) + 1;
    if (len <= bufsize)
        strncpy(sp, str, len);
    else {
        strncpy(sp, str, bufsize - 1);
        *(sp + bufsize - 1) = '\0';
    }

    list_del_init(head->prev);
    return node;
}

q_release_element

未做更動

void q_release_element(element_t *e)
{
    free(e->value);
    free(e);
}

q_size

整個 list 走過一遍即可算出 size

int q_size(struct list_head *head)
{
    if (!head)
        return 0;

    int len = 0;
    struct list_head *li;
    list_for_each (li, head)
        len++;

    return len;
}

q_delete_mid

利用快慢指標找到中間的 node

struct list_head *find_mid(struct list_head *head)
{
    struct list_head *slow = head->next;
    for (struct list_head *fast = head->next;
         fast != head && fast->next != head; fast = fast->next->next) {
        slow = slow->next;
    }
    return slow;
}


bool q_delete_mid(struct list_head *head)
{
    if (!head)
        return false;
    if (list_empty(head))
        return false;

    struct list_head *mid = find_mid(head);

    mid->prev->next = mid->next;
    mid->next->prev = mid->prev;
    element_t *node = list_entry(mid, element_t, list);
    free(node->value);
    free(node);


    return true;
}

q_delete_dup

若 current node 的值等於 first 的值就把 last 指標移到 current node ，若不等於就檢查 first 和 last 是否為同一個 node ，若不是就把 first 和 last 之間的 node 全部刪除。

bool q_delete_dup(struct list_head *head)
{
    if (!head)
        return false;
    if (list_empty(head))
        return true;

    element_t *current, *first = list_entry(head->next, element_t, list),
                        *last = first;
    list_for_each_entry (current, head, list) {
        if (!strcmp(current->value, first->value))
            last = current;
        else {
            if (first != last) {
                first->list.prev->next = last->list.next;
                last->list.next->prev = first->list.prev;
                while (first != current) {
                    element_t *temp =
                        list_entry(first->list.next, element_t, list);
                    q_release_element(first);
                    first = temp;
                }
            }
            first = current;
            last = current;
        }
    }
    if (first != last) {
        first->list.prev->next = last->list.next;
        last->list.next->prev = first->list.prev;
        while (first != current) {
            element_t *temp = list_entry(first->list.next, element_t, list);
            q_release_element(first);
            first = temp;
        }
    }
    return true;
}

q_swap

把 list 的 node 每兩個依序前後交換

void q_swap(struct list_head *head)
{
    if (!head)
        return;

    for (struct list_head *first = head->next, *second = head->next->next;
         first != head && second != head;
         first = first->next, second = first->next) {
        struct list_head *prev = first->prev;
        struct list_head *next = second->next;
        prev->next = second;
        second->prev = prev;
        second->next = first;
        first->prev = second;
        next->prev = first;
        first->next = next;
    }
}

q_reverse

把每個 node 的 next 和 prev 進行交換

void q_reverse(struct list_head *head)
{
    if (!head)
        return;

    struct list_head *current, *safe;
    list_for_each_safe (current, safe, head) {
        struct list_head *prev = current->prev;
        struct list_head *next = current->next;
        current->next = prev;
        current->prev = next;
    }
    struct list_head *prev = head->prev;
    struct list_head *next = head->next;
    head->next = prev;
    head->prev = next;
}

q_sort

遞迴版本

使用遞迴的 merge sort ，因為傳入的 list 有一個不存資料的 head ，所以宣告一個 new_head 作為切下來另一半 list 的 head node。在自己電腦的效能測試過了，但 github 上的仍無法通過。

struct list_head *merge(struct list_head *left, struct list_head *right)
{
    struct list_head head, **temp, *l = left->next, *r = right->next;
    INIT_LIST_HEAD(&head);
    while (l != left && r != right) {
        if (strcmp(list_entry(l, element_t, list)->value,
                   list_entry(r, element_t, list)->value) < 0)
            temp = &l;
        else
            temp = &r;
        *temp = (*temp)->next;
        list_move_tail((*temp)->prev, &head);
    }
    (l == left) ? list_splice_tail_init(right, &head)
                : list_splice_tail(left, &head);

    list_splice_tail(&head, right);

    return right;
}

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *mid = find_mid(head);
    struct list_head new_head;
    INIT_LIST_HEAD(&new_head);

    list_cut_position(&new_head, head, mid->prev);
    q_sort(&new_head);
    q_sort(head);

    merge(&new_head, head);

    return;
}

• 參考這篇筆記懷疑是 stackoverflow 導致效能測試無法通過
• 思考為什麼會發生 stackoverflow ，猜測是因為每次遞迴都會宣告一次 new_head 所導致的
• 改寫 mergesort ，讓 merge 的時候不考慮 head node ，如此就不需要每次遞迴都宣告一個 new_head 。
• 再次上傳後成功通過效能測試

struct list_head *merge(struct list_head *left, struct list_head *right)
{
    struct list_head *head = NULL, **temp = &head;

    while (left && right) {
        if (strcmp(list_entry(left, element_t, list)->value,
                   list_entry(right, element_t, list)->value) <= 0) {
            *temp = left;
            left = left->next;
        } else {
            *temp = right;
            right = right->next;
        }
        temp = &(*temp)->next;
    }
    *temp = left ? left : right;


    return head;
}



struct list_head *merge_sort(struct list_head *head)
{
    if (!head)
        return head;
    if (!head->next)
        return head;

    struct list_head *fast = head, *slow = head;
    while (1) {
        if (!fast)
            break;
        if (!fast->next)
            break;

        slow = slow->next;
        fast = fast->next->next;
    }
    slow->prev->next = NULL;

    head = merge_sort(head);
    slow = merge_sort(slow);

    return merge(head, slow);
}

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    head->prev->next = NULL;

    head->next = merge_sort(head->next);

    struct list_head *current, *prev;
    for (current = head->next, prev = head; current;
         current = current->next, prev = prev->next)
        current->prev = prev;
    prev->next = head;
    head->prev = prev;


    return;
}

非遞迴版本

依序將 list 裡的 node 存進 space 陣列中，當第 space[i] 與 space[i-1] 擁有同樣的 node 數（lsit 的長度一樣）時，將兩者進行 merge 並存到 space[i-1] 。

void merge_sort_iter(struct list_head *head)
{
    int num = q_size(head);
    num = log2(num) + 1;
    int stack[num];
    struct list_head *space[num];
    head->prev->next = NULL;
    head->prev = NULL;
    struct list_head *node = head->next;

    int i = 0;
    while (node) {
        space[i] = node;
        stack[i] = 0;
        struct list_head *tmp = node;
        node = node->next;
        tmp->next = NULL;
        int j = i - 1;
        while (j >= 0) {
            if (stack[j] == stack[j + 1]) {
                space[j] = merge(space[j], space[j + 1]);
                stack[j]++;
                j--;
                i--;
            } else
                break;
        }
        i++;
    }
    i--;
    while (i) {
        space[i - 1] = merge(space[i - 1], space[i]);
        i--;
    }
    head->next = space[0];
    struct list_head *current, *prev;
    for (current = head->next, prev = head; current;
         current = current->next, prev = prev->next)
        current->prev = prev;
    prev->next = head;
    head->prev = prev;

    return;
}

研讀 linux/list_sort.c

• 需要傳入 list_sort() 的三個參數

  1. priv : 傳輸 cmp 所需參數的 pointer
  2. head : 要排序的 list
  3. cmp : 比較自定義大小的 function pointer，當 a 須置於 b 之後時會回傳大於 0 的值
     • 以升序排列為例，當 a > b 時便會回傳大於 0 的值
     • list_sort 為 stable sort ，故不必區分小於或等於 0 的分別

• list_sort 跟一般的 bottom-up mergesort 不同，後者每當出現 2 個 $2^k$ 大小的 list 時就會進行合併，前者則是當第 3 個 $2^k$ 大小的 list 出現時才進行合併。這樣做的好處是避免了 worst case 的出現，當要排序的 list 大小只比 $2^k$ 大一點點時，bottom-up mergesort 的最後一次合併就會出現極端的情況。舉個例子，當 list 大小為 9 時， bottom-up mergesort最後一次合併的 2 個 list 大小分別會是 8 和 1；而 list_sort 則會是 4 和 5 ，後者很明顯地會優於前者。事實上，不論要排序的 list 大小為何， list_sort 的合併都不會出現比 2 : 1 還糟糕的情況。

• 從 list_sort 的程式碼中，我發現了幾個自己實作的 merge sort 可以改進的地方

  • sort 過的 list 可以用 struct list_head() 的 prev 指標來串聯，如此就不須宣告新的空間去存放
  • 試著只用一個 integer count 去控制 list 的合併
    • 上述兩點可以使 sort 少走訪一次整個 list (不必在一開始計算 list 的 node 數)
  • 在最後一次的合併就把整個 list 的 prev 連接回去
    • 可以使 sort 少走訪一次 list

• 修改後的程式碼

void final_merge(struct list_head *left,
                 struct list_head *right,
                 struct list_head *head)
{
    struct list_head **temp = &head;

    while (left && right) {
        if (strcmp(list_entry(left, element_t, list)->value,
                   list_entry(right, element_t, list)->value) <= 0) {
            left->prev = *temp;
            (*temp)->next = left;
            left = left->next;
        } else {
            right->prev = *temp;
            (*temp)->next = right;
            right = right->next;
        }
        temp = &(*temp)->next;
    }
    (*temp)->next = left ? left : right;
    while ((*temp)->next) {
        (*temp)->next->prev = *temp;
        temp = &(*temp)->next;
    }
    (*temp)->next = head;
    head->prev = *temp;

    return;
}

void merge_sort_iter(struct list_head *head)
{
    struct list_head *pending = NULL;
    struct list_head *list = head->next;
    head->prev->next = NULL;
    head->prev = NULL;
    int count = 0;

    while (list) {
        list->prev = pending;
        pending = list;
        list = list->next;
        pending->next = NULL;
        struct list_head **tail = &pending;
        for (int bits = count;; bits >>= 1) {
            if (bits & 1) {
                struct list_head *a = *tail, *b = a->prev;
                a = merge(b, a);
                a->prev = b->prev;
                *tail = a;
            } else
                break;
        }
        count++;
    }

    list = pending;
    pending = pending->prev;
    while (pending) {
        struct list_head *next = pending->prev;
        if (!next)
            break;
        list = merge(pending, list);
        pending = next;
    }
    final_merge(pending, list, head);


    return;
}

• 測試兩者間效能差異
  • 測試用的命令檔（由於第一次 sort 測出來的時間會跟之後的有明顯落差，故皆不採記第一次的結果）
  ​​​​option echo 0
  ​​​​option verbose 1
  
  ​​​​# fault
  ​​​​new
  ​​​​it RAND 300000
  ​​​​time sort
  
  ​​​​# 1
  ​​​​new
  ​​​​it RAND 300000
  ​​​​time sort
  
  ​​​​# 2
  ​​​​new
  ​​​​it RAND 300000
  ​​​​time sort
  
  ​​​​# 3
  ​​​​new
  ​​​​it RAND 300000
  ​​​​time sort
  
  ​​​​# 4
  ​​​​new
  ​​​​it RAND 300000
  ​​​​time sort
  
  ​​​​# 5
  ​​​​new
  ​​​​it RAND 300000
  ​​​​time sort
  

  • 測試結果
    • 原始版本
    ​​​​​​​​ericliau@ericliau-GL502VML:~/linux2022/lab0-c$ ./qtest -f traces/test1.cmd
    ​​​​​​​​cmd> option echo 0
    ​​​​​​​​# fault
    ​​​​​​​​Delta time = 0.242
    ​​​​​​​​# 1
    ​​​​​​​​Delta time = 0.381
    ​​​​​​​​# 2
    ​​​​​​​​Delta time = 0.396
    ​​​​​​​​# 3
    ​​​​​​​​Delta time = 0.391
    ​​​​​​​​# 4
    ​​​​​​​​Delta time = 0.386
    ​​​​​​​​# 5
    ​​​​​​​​Delta time = 0.383
    

    • 修改後
    ​​​​​​​​ericliau@ericliau-GL502VML:~/linux2022/lab0-c$ ./qtest -f traces/test1.cmd
    ​​​​​​​​cmd> option echo 0
    ​​​​​​​​# fault
    ​​​​​​​​Delta time = 0.207
    ​​​​​​​​# 1
    ​​​​​​​​Delta time = 0.325
    ​​​​​​​​# 2
    ​​​​​​​​Delta time = 0.327
    ​​​​​​​​# 3
    ​​​​​​​​Delta time = 0.333
    ​​​​​​​​# 4
    ​​​​​​​​Delta time = 0.333
    ​​​​​​​​# 5
    ​​​​​​​​Delta time = 0.330
    

    • 把修改後的 5 次測試時間加起來除以原始版本的 5 次測試時間，得出來的值約為 0.85 ，效能提昇了 15％ 左右

引入 linux/list_sort.c

引入方法參考自 2020leon

1. 將 list_sort.c 和 list_sort.h 複製到 lab0-c 專案中。

   • list_sort.c 直接從 linux/list_sort.c 複製。
   • list_sort.h 從 linux 核心中的 include/linux/list_sort.h 複製。

2. 將型別 u8 更改為 uint8_t。

   • 必須引入標頭檔 stdint.h。

3. 在 list_sort.h 加入 likely(x) 及 unlikely(x) 巨集定義。

   ​​​​# define likely(x)	__builtin_expect(!!(x), 1)           
   ​​​​# define unlikely(x)	__builtin_expect(!!(x), 0)
   

4. 在 list_sort.c 中新增 listcmp() 函式。

   ​​​​int listcmp(void *priv, const struct list_head *a, const struct list_head *b)
   ​​​​{
   ​​​​    return strcmp(list_entry(a, element_t, list)->value,
   ​​​​              list_entry(b, element_t, list)->value);
   ​​​​}
   

5. 使 cppcheck 忽略 list_sort.c 中 merge 函式產生的 head 未賦值錯誤

   • 加入 // cppcheck-suppress unassignedVariable
   ​​​​// cppcheck-suppress unassignedVariable
   ​​​​struct list_head *head, **tail = &head;
   

   • 於終端機輸入 $ cppcheck --inline-suppr list_sort.c

6. 修改 qtest.c ，新增一個 option 以便於在 list_sort 及自己實作的排序法間做切換。

   • 加入 option
     ​​​​​​​​...
     ​​​​​​​​static int listsort = 0;
     ​​​​​​​​...
     ​​​​​​​​static void console_init()
     ​​​​​​​​{
     ​​​​​​​​...
     ​​​​​​​​    add_param("listsort", &listsort, "Use list_sort or not", NULL);
     ​​​​​​​​}
     

   • 修改 do_sort() 函式
     ​​​​​​​​bool do_sort(int argc, char *argv[])
     ​​​​​​​​{
     ​​​​​​​​...
     ​​​​​​​​if (exception_setup(true)){
     ​​​​​​​​    if(!listsort)
     ​​​​​​​​        q_sort(l_meta.l);
     ​​​​​​​​    else
     ​​​​​​​​        list_sort(NULL, l_meta.l, cmp);
     ​​​​​​​​...
     ​​​​​​​​}
     

測試 list sort 和自己的排序法效能落差，測出來自己的排序法慢了大概 10％

ericliau@ericliau-GL502VML:~/linux2022/lab0-c$ ./qtest -f traces/test.cmd
cmd> option echo 0
# fault
Delta time = 0.273
# user version
Delta time = 0.376
Delta time = 0.408
Delta time = 0.390
Delta time = 0.377
Delta time = 0.374
# list sort
Delta time = 0.358
Delta time = 0.342
Delta time = 0.340
Delta time = 0.342
Delta time = 0.344

而如果是用參考 list sort 後所修改的版本則大約快了 5％

ericliau@ericliau-GL502VML:~/linux2022/lab0-c$ ./qtest -f traces/test.cmd
cmd> option echo 0
# fault
Delta time = 0.207
# user version
Delta time = 0.323
Delta time = 0.321
Delta time = 0.327
Delta time = 0.336
Delta time = 0.333
# list sort
Delta time = 0.344
Delta time = 0.348
Delta time = 0.344
Delta time = 0.343
Delta time = 0.343

我還蠻意外會比 list sort 快的，具體比較快的原因待驗證

qtest.c

實作 shuffle 演算法

使用 Fisher–Yates shuffle 演算法，該演算法之 pseudocode 如下：

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

實作之程式碼如下：

static void shuffle(struct list_head *head)
{
    int num = q_size(head);

    struct list_head *tmp, *current;
    for(tmp = head->prev; num > 0; num--){
        current = head;
        for(int i = rand() % num; i >= 0; i--)
            current = current->next;
        char *value = list_entry(current, element_t, list)->value;
        list_entry(current, element_t, list)->value = list_entry(tmp, element_t, list)->value;
        list_entry(tmp, element_t, list)->value = value;
    }
}
static bool do_shuffle(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }
    if(!l_meta.l){
        report(1, "list is null");
        return false;
    }
    else if (list_empty(l_meta.l))
    {
        report(1, "list is empty");
        return false;
    }
    else if (list_is_singular(l_meta.l))
    {
        report(1, "no need to shuffle");
        return false;
    }
    
    shuffle(l_meta.l);
    show_queue(3);
    return true;
}

最後在 console_init() 添加指令：

ADD_COMMAND(shuffle, "                | Shuffle the list");

提供 web 命令

因為要整合 tiny-web-server ，所以先試著引入 tiny.c ，並分一個 tiny.h 出來存放其他檔案會用到的部份。

• 其中的 process() 需要進行修改，這部份稍後再提

#ifndef __TINY_H
#define __TINY_H

#include <arpa/inet.h> /* inet_ntoa */
#include <dirent.h>
#include <errno.h>
#include <fcntl.h>
#include <netinet/in.h>
#include <netinet/tcp.h>
#include <signal.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/sendfile.h>
#include <sys/socket.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <time.h>
#include <unistd.h>


typedef struct {
    char filename[512];
    off_t offset; /* for support Range */
    size_t end;
} http_request;

/* Simplifies calls to bind(), connect(), and accept() */
typedef struct sockaddr SA;

int open_listenfd(int port);
char *process(int fd, struct sockaddr_in *clientaddr);
void parse_request(int fd, http_request *req);

#endif /* __TINY_H */

然後把 tiny.c 和 tiny.h 加到 Makefile 裡，在 OBJS := 後面加入 tiny.o

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

接著基本上就照著作業說明完成

首先在 linenoise.h 中加入變數 noise 和 listenfd

bool noise;
int listenfd;

修改 linenoiseEdit() ，在 while(1) 裡加入以下程式碼

if (listenfd) {
            fd_set set;
            FD_ZERO(&set);
            FD_SET(listenfd, &set);
            FD_SET(stdin_fd, &set);
            struct sockaddr_in clientaddr;
            socklen_t clientlen = sizeof(clientaddr);
            int rv = select(listenfd + 1, &set, NULL, NULL, NULL);
            int connfd;
            switch (rv) {
            case -1:
                perror("select"); /* an error occurred */
                continue;
            case 0:
                printf("timeout occurred\n"); /* a timeout occurred */
                continue;
            default:
                if (FD_ISSET(listenfd, &set)) {
                    connfd = accept(listenfd, (SA *) &clientaddr, &clientlen);
                    char *p = process(connfd, &clientaddr);
                    strncpy(buf, p, strlen(p) + 1);
                    close(connfd);
                    free(p);
                    return strlen(p);
                } else if (FD_ISSET(stdin_fd, &set)) {
                    nread = read(l.ifd, &c, 1);
                    if (nread <= 0)
                        return l.len;
                }
                break;
            }
        } else {
            nread = read(l.ifd, &c, 1);
            if (nread <= 0)
                return l.len;
        }

修改 run_console() ，讓其依照 linenoise 開啟與否決定要用 linenoise 還是 cmd_select

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

    if (!has_infile) {
        char *cmdline;
        while (noise && (cmdline = linenoise(prompt)) != NULL) {
            interpret_cmd(cmdline);
            linenoiseHistoryAdd(cmdline);       /* Add to the history. */
            linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
            linenoiseFree(cmdline);
        }
        if (!noise) {
            while (!cmd_done()) {
                cmd_select(0, NULL, NULL, NULL, NULL);
            }
        }
    } else {
        while (!cmd_done()) {
            cmd_select(0, NULL, NULL, NULL, NULL);
        }
    }

    return err_cnt == 0;
}

修改 cmd_select() ，新增對於 web 端輸入的處理

int cmd_select(int nfds,
               fd_set *readfds,
               fd_set *writefds,
               fd_set *exceptfds,
               struct timeval *timeout)
{
    int infd;
    fd_set local_readset;

    if (cmd_done())
        return 0;

    if (!block_flag) {
        /* Process any commands in input buffer */
        if (!readfds)
            readfds = &local_readset;

        /* Add input fd to readset for select */
        infd = buf_stack->fd;
        FD_ZERO(readfds);
        FD_SET(infd, readfds);

        /* If web not ready listen */
        if (listenfd != -1)
            FD_SET(listenfd, readfds);

        if (infd == STDIN_FILENO && prompt_flag) {
            printf("%s", prompt);
            fflush(stdout);
            prompt_flag = true;
        }

        if (infd >= nfds)
            nfds = infd + 1;

        if (listenfd >= nfds)
            nfds = listenfd + 1;
    }
    if (nfds == 0)
        return 0;

    int result = select(nfds, readfds, writefds, exceptfds, timeout);
    if (result <= 0)
        return result;

    infd = buf_stack->fd;
    if (readfds && FD_ISSET(infd, readfds)) {
        /* Commandline input available */
        FD_CLR(infd, readfds);
        result--;

        char *cmdline;
        cmdline = readline();
        if (cmdline)
            interpret_cmd(cmdline);
    } else if (readfds && FD_ISSET(listenfd, readfds)) {
        FD_CLR(listenfd, readfds);
        result--;
        int connfd;
        struct sockaddr_in clientaddr;
        socklen_t clientlen = sizeof(clientaddr);
        connfd = accept(listenfd, (SA *) &clientaddr, &clientlen);

        char *p = process(connfd, &clientaddr);
        if (p)
            interpret_cmd(p);
        free(p);
        close(connfd);
    }
    return result;
}

修改 tiny.c 中的 process() ， process() 會處理 http 請求，將其轉換成符合 cmd 的命令格式

char *process(int fd, struct sockaddr_in *clientaddr)
{
#ifdef LOG_ACCESS
    printf("accept request, fd is %d, pid is %d\n", fd, getpid());
#endif
    http_request req;
    parse_request(fd, &req);
    int status = 200;

    char *p = req.filename;
    /* Change '/' to ' ' */
    while (*p && (*p) != '\0') {
        ++p;
        if (*p == '/') {
            *p = ' ';
        }
    }
#ifdef LOG_ACCESS
    log_access(status, clientaddr, &req);
#endif
    char *ret = malloc(strlen(req.filename) + 1);
    strncpy(ret, req.filename, strlen(req.filename) + 1);

    return ret;
}

最後在 qtest.c 中新增 do_web() 函式和 web 指令

• 加入 set_echo(false); 是為了避免在 web 開啟後從使用者端輸入指令會重複印出的情形

static bool do_web(int argc, char *argv[])
{
    noise = false;
    set_echo(false);
    listenfd = open_listenfd(9999);
    printf("listen on port 9999, fd is %d\n", listenfd);

    return true;
}

ADD_COMMAND(web, "                | Open web server");

執行結果

ericliau@ericliau-GL502VML:~/linux2022/lab0-c$ ./qtest
cmd> web
listen on port 9999, fd is 3
cmd> accept request, fd is 4, pid is 53178
127.0.0.1:58584 200 - 'new' (text/plain)
l = []
cmd> accept request, fd is 4, pid is 53178
127.0.0.1:58586 200 - 'ih a' (text/plain)
l = [a]
cmd> accept request, fd is 4, pid is 53178
127.0.0.1:58588 200 - 'ih b' (text/plain)
l = [b a]
cmd> accept request, fd is 4, pid is 53178
127.0.0.1:58590 200 - 'ih c' (text/plain)
l = [c b a]
cmd> ih d
l = [d c b a]
cmd> ih e
l = [e d c b a]
cmd> accept request, fd is 4, pid is 53178
127.0.0.1:58592 200 - 'sort' (text/plain)
l = [a b c d e]

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

qtest 執行後並未發生錯誤，尚在尋找原因

select 系統呼叫

select 的功用是同時監測多個 file descriptor ，直到其中一個準備好要進行 I/O 。而 lab0 使用 select 的地方在函式 cmd_select() 中，透過實作 web 指令，可以得知其主要用來偵測是由使用者端還是從 web 端輸入指令。

分析 console.c

先說結論 : 使用 RIO 套件可以在讀 cmd 檔的時候減少呼叫系統指令 read 的次數。

因為 RIO 套件支援 buffered I/O ，在讀行時只需要呼叫 1 次 read 系統指令將一個 buffer 大小的資料存進 buffer ，再從 buffer 中一個字一個字的尋找換行符即可。如果不使用 buffer ，因為需要尋找換行符的緣故，每次呼叫 read 只能讀一個字元，導致需要頻繁的呼叫 read 指令，使得 OS 必須不斷地在 kernel-mode 和 user-mode 間做切換。

研讀論文〈Dude, is my code constant time?〉

這篇論文使用 dudect 這個程式來測量某個程式執行時間是否為 constant time 。其中使用的 Student’s t-distribution 為一種估計期望值的統計學方法，用於樣本量不大且不知道標準差的情況。

該論文使用 leakage detection test ，因為是透過統計模型來推斷是否為 constant time，使得此方法並不局限於特定的 CPU 硬體，方法步驟如下:

1. 分別用固定和隨機的輸入資料進行多次測試
2. 去掉極端值然後進行 high-order preprocessing
3. 用統計方法判定是否符合常態時間，本專案使用 Welch's t-test

lab0 實作

lab0 檢查是否 constant time 的函式主要位於 dudect/ 中，其呼叫路徑為 is_XXX_const() -> TEST_CONST() -> doit() ，測試步驟基本在 doit() 中完成。

static bool doit(int mode)
{
    int64_t *before_ticks = calloc(n_measure + 1, sizeof(int64_t));
    int64_t *after_ticks = calloc(n_measure + 1, sizeof(int64_t));
    int64_t *exec_times = calloc(n_measure, sizeof(int64_t));
    uint8_t *classes = calloc(n_measure, sizeof(uint8_t));
    uint8_t *input_data = calloc(n_measure * 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() 產生多個長度為 7 bytes 的隨機字串 (加上 \0 為 8 bytes)，並將資料分成兩個 class。

measure() 將 prepare_inputs() 產生的字串根據不同操作進行測量，測量方式為分別記錄執行該操作前後當下的 cycle 數。

differentiate() 計算兩者 cycle 數的差值，即該操作執行所花費的 cycle 數。

update_statistics() 再用得到的執行 cycle 數分別算出兩個 class 的平均數和變異數。

report() 將所求出的值用 Welch’s t-test 算出 t 值，並判斷對應操作是否為 constant time 。