2023q1 Homework1 (lab0)

contributed by < linhoward0522 >

不用複製作業要求內容，善用超連結。

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

jserv

開發環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               GenuineIntel
  Model name:            12th Gen Intel(R) Core(TM) i5-12400
    CPU family:          6
    Model:               151
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            2
    CPU max MHz:         5600.0000
    CPU min MHz:         800.0000
    BogoMIPS:            4992.00

queue.[ch]

`q_new`

使用 INIT_LIST_HEAD 來初始化一個空的 list_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`

想法是使用 list_entry 找出對應的 element 並且釋放其內部所指的字串以及自身的空間
在 queue.h 中裡面 q_release_element 可以用來釋放記憶體

void q_free(struct list_head *l)
{
    if (!l)
        return;

    struct list_head *current = l->next;

    while (current != l) {
        current = current->next;
        q_release_element(list_entry(current->prev, element_t, list));
    }

    free(l);
}

後來參考 The Linux Kernel API，由於過程中要將節點移除， list_for_each_entry_safe 會記錄下一個位置，並可以安全刪除當前節點，進一步精簡程式碼

void q_free(struct list_head *l)
{
    if (!l)
        return;

    element_t *pos, *n;

    list_for_each_entry_safe (pos, n, l, list)
        q_release_element(pos);

    free(l);
}

`q_insert_head`

透過 The Linux Kernel API 以及 list.h ，其中的 list_add 將新的 element_t->list 加入原有的 head 裡。
並且需要配置字串所需的記憶體空間，其中 strlen 並不含 '\0'，所以在配置時需要將記憶體空間多加一。

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;

    int len = strlen(s);

    new->value = malloc(sizeof(char) * len + 1);

    if (!new->value) {
        q_release_element(new);
        return false;
    }
    strncpy(new->value, s, len + 1);

    list_add(&new->list, head);

    return true;
}

`q_insert_tail`

同 q_insert_head ，使用 list_add_tail 來實作

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;

    int len = strlen(s);

    new->value = malloc((sizeof(char) * len + 1));

    if (!new->value) {
        q_release_element(new);
        return false;
    }
    strncpy(new->value, s, len + 1);

    list_add_tail(&new->list, head);

    return true;
}

`q_remove_head`

利用 list.h 裡的 list_first_entry ，可以將第一個 element_t 的位址取出
並使用 list_del_init 確保在移除 entry 後前後節點會互相連結
最後要將移除的元素數值複製到 sp ，並且複製字串到 sp 時要加上 null terminator 的空間

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

    element_t *element = list_first_entry(head, element_t, list);

    list_del_init(head->next);
    /*If sp is non-NULL and an element is removed, copy the removed string to
     *sp (up to a maximum of bufsize-1 characters, plus a null terminator.)*/
    if (sp) {
        strncpy(sp, element->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    return element;
}

`q_remove_tail`

同 q_remove_head ，使用 list_last_entry 將最後一個 element_t 的位址取出

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

    element_t *element = list_last_entry(head, element_t, list);

    list_del_init(head->prev);
    /*If sp is non-NULL and an element is removed, copy the removed string to
     *sp (up to a maximum of bufsize-1 characters, plus a null terminator.)*/
    if (sp) {
        strncpy(sp, element->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    return element;
}

`q_size`

利用 list_for_each 走訪每個節點並計算長度。

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

    struct list_head *pos;
    int length = 0;

    list_for_each (pos, head)
        length++;

    return length;
}

`q_delete_mid`

根據你所不知道的 C 語言: linked list 和非連續記憶體，其中老師有提到快慢指標的概念來實作
並使用 list_del_init 確保在移除 entry 後前後節點會互相連結
最後利用 list_entry 找出對應的 element 並使用 q_release_element 釋放記憶體空間。

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

    struct list_head **indirect = &head->next;

    for (struct list_head *fast = head->next;
         fast != head && fast->next != head; fast = fast->next->next)
        indirect = &(*indirect)->next;

    struct list_head *next = *indirect;

    list_del_init(next);
    q_release_element(list_entry(next, element_t, list));

    return true;
}

後來根據考試時的課後講解，改成用以下方式進行實作
透過迴圈來判斷是否相遇

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head *forward = head->next;
    struct list_head *backward = head->prev;

    while (forward != backward && forward->next != backward) {
        forward = forward->next;
        backward = backward->prev;
    }

    list_del_init(backward);
    q_release_element(list_entry(backward, element_t, list));

    return true;
}

`q_delete_dup`

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.
已知為一個排序後的 linked list ，想法是使用 list_for_each_entry_safe 進行迭代，能得到當前的以及下一個 element_t 的位址
使用 strcmp 比對字串是否相同
變數 flag 用來確認如果字串相同，則在下一個迴圈就會刪除另一個重複的元素

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

    element_t *element, *next;
    bool flag = false;

    list_for_each_entry_safe (element, next, head, list) {
        if (&next->list != head && strcmp(element->value, next->value) == 0) {
            list_del_init(&element->list);
            q_release_element(element);
            flag = true;
        } else if (flag) {
            list_del_init(&element->list);
            q_release_element(element);
            flag = false;
        }
    }

    return true;
}

`q_swap`

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)
原本在 The Linux Kernel API 中有找到 list_swap 要來做使用，但在 list.h 並沒有看到相關實作，後來改用 list_move 來實作
由於使用 list_move ，所以兩個指標也互換，所以迭代到下一次時就相當於是 current->next->next ，即完成兩兩交換

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

    for (struct list_head *current = head->next;
         current != head && current->next != head; current = current->next)
        list_move(current, current->next);
}

`q_reverse`

使用 list.h 裡的 list_for_each_safe 進行迭代
原本的想法是運用 prev 和 next 來紀錄前後位置，然後反轉節點
後來發現 list.h 裡的 list_move ，可以將節點移至串列起始點，即完成反轉

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

    struct list_head *pos, *n;

    list_for_each_safe (pos, n, head)
        list_move(pos, head);
}

`q_reverseK`

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.
想法為將每一組的節點逐一往前移至最前面，接著迭代每一組
使用 q_size 紀錄串列長度，用來確保最後剩下不足 k 個節點不會做反向順序排列
透過 current 紀錄 pos->next 的位址
做完 list_move 後，相對地 pos 會向後移一格
所以下一次迭代 *current 就會指向下一個要做反向順序排列的節點
tmp 用來紀錄要將節點移動到的地方

void q_reverseK(struct list_head *head, int k)
{
    if (!head || list_empty(head) || k < 2)
        return;

    int length = q_size(head);
    for (struct list_head *pos = head->next; pos != head && pos->next != head;
         pos = pos->next) {
        struct list_head **current = &pos->next, *tmp = pos->prev;
        for (int i = 1; i < k; i++) {
            if (length >= k)
                list_move(*current, tmp);
        }
        length -= k;
    }
}

`q_sort`

參考你所不知道的 C 語言: linked list 和非連續記憶體 merge sort 的實作

`merge_list`

用兩個指標分別指著兩個串列，比較後將較小的放到新的串列裡，然後將指標移至下一個位置
運用 indirect pointer 的技巧可以避免配置暫時節點的記憶體空間
當迭代完成後，會剩下一個節點尚未加入串列，採 bit-wsie 方法來加速運算

struct list_head *merge_list(struct list_head *left, struct list_head *right)
{
    struct list_head *head = NULL, **ptr = &head;

    for (; left && right; ptr = &(*ptr)->next) {
        if (strcmp(list_entry(left, element_t, list)->value,
                   list_entry(right, element_t, list)->value) < 0) {
            *ptr = left;
            left = left->next;
        } else {
            *ptr = right;
            right = right->next;
        }
    }

    *ptr = (struct list_head *) ((uintptr_t) left | (uintptr_t) right);

    return head;
}

`merge_sort`

先使用快慢指標的方法來尋找中間節點
再呼叫 merge_list 將第一個節點開頭的串列及中間節點開頭的串列，合併成一個有序的串列。
其中 slow->next = NULL; 是必須要將第一個節點開頭的串列尾巴指向NULL

struct list_head *merge_sort(struct list_head *head)
{
    if (!head || !head->next)
        return head;
    struct list_head *fast, *slow = head;

    for (fast = head->next; fast && fast->next; fast = fast->next->next) {
        slow = slow->next;
    }

    struct list_head *left, *right;

    right = slow->next;
    slow->next = NULL;

    left = merge_sort(head);
    right = merge_sort(right);

    return merge_list(left, right);
}

`q_sort`

執行 merge_sort 前要先將 head 斷開，使其變成 singly-linked list 來避免產生無窮迴圈
最後要再迭代一次排序後的串列，因為當前排序過後是 singly-linked list ，所以要將 prev 指標更新，也需將串列尾巴與串列開頭相互連結，讓串列變回 circular doubly-linked list ，以維持 struct list_head 的型態

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 *cur = head, *n = head->next;

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

    cur->next = head;
    head->prev = cur;
}

`q_descend`

Remove every node which has a node with a strictly greater value anywhere to the right side of it.
Return the number of elements in queue after performing operation
想法是透過反向順序逐一走訪節點，若下一個節點小於當前節點則將它刪除

int q_descend(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

    struct list_head *cur = head->prev, *n = cur->prev;

    while (n != head) {
        if (strcmp(list_entry(n, element_t, list)->value,
                   list_entry(cur, element_t, list)->value) < 0) {
            list_del_init(n);
            q_release_element(list_entry(n, element_t, list));
        } else
            cur = n;
        n = cur->prev;
    }
    return q_size(head);
}

`q_merge`

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

從 queue.h 可以了解 queue_contex_t 的結構
- q 用來指向 queue 的 head
- chain 用來將每一個 queue_contex_t 結構串連起來
- size 表示這個 queue 的長度
- id 表示每一個 queue 唯一的編號
接著從 qtest.c 發現有宣告 queue_chain_t 的結構，並從do_new 函式可以發現
- 他是用來當 queue_contex_t 結構的 head
- 並且每次 new 一個新的 queue_contex_t 結構，都會將此結構插入到串列的尾端
同時在 qtest.c 的 do_merge 函式可以發現它傳入的參數是 queue_chain_t 結構的 head
因為 qtest.c 裡面有宣告 q_chain_t 的結構，所以邊界條件不用判斷 !head
- 所以設置 list_empty(head) 與 list_is_singular(head) 為邊界條件即可
想法就是逐一將所有串列合併到第一個串列
與 q_sort 差不多，執行 merge_list 前要先將 head 斷開，使其變成 singly-linked list 來避免產生無窮迴圈
最後要再迭代一次排序後的串列，讓串列變回 circular doubly-linked list
其中必須要加上 INIT_LIST_HEAD(pos->q) 才不會造成 Segmentation fault

int q_merge(struct list_head *head)
{
    if (list_empty(head))
        return 0;
    if (list_is_singular(head))
        return list_entry(head->next, queue_contex_t, chain)->size;

    queue_contex_t *first = list_entry(head->next, queue_contex_t, chain);
    queue_contex_t *pos = NULL;

    struct list_head *tmp = first->q->next;
    first->q->prev->next = NULL;
    list_for_each_entry (pos, head, chain) {
        if (first == pos)
            continue;
        pos->q->prev->next = NULL;
        tmp = merge_list(tmp, pos->q->next);
        INIT_LIST_HEAD(pos->q);
    }
    first->q->next = tmp;
    struct list_head *cur = first->q, *n = cur->next;

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

    cur->next = first->q;
    first->q->prev = cur;

    return q_size(tmp);
}

目前 trace-17-complexity 還是無法通過

研讀 Linux 核心原始程式碼的 `lib/list_sort.c`

閱讀 Linux 核心的鏈結串列排序 , list_sort.c 以及你所不知道的 C 語言: linked list 和非連續記憶體

嘗試引入到 `lab0-c` 專案

參考作業規範中 qtest 命令直譯器的實作
將 list_sort.c 程式碼複製到 qtest.c
其中有使用到__attribute__((nonnull(2,3,4))) 關鍵字
- 為 compiler 指定函式傳入的參數必須為 non-null ，如果傳入 null 則會發出警告
  
  參考資料
在 list_sort.c 有使用到 likely 這個巨集，所以需要增添到 qtest.c ，而他們被定義在 /include/linux/compiler.h 中
```
 # define likely(x)	__builtin_expect(!!(x), 1)
 # define unlikely(x)	__builtin_expect(!!(x), 0)
```
- __built_expect() 是 gcc 的內建 function，用來將 branch 的相關資訊提供給 compiler ，告訴 compiler 設計者期望的比較結果，以便對程式碼改變分支順序來進行優化。
- 而這 likely , unlikely 兩個巨集，可以讓 compiler 在編譯 assembly code 的時候做一些最佳化，可以告訴 compiler 某段 if 敘述為 true 的機率較高或低，讓 compiler 把對應程式碼接在判斷的後面
- 程式碼被放到比較相近的位置，那他們就可能一起被搬到 cache 中，使 cache hit rate 上升，可能可以提升程式的執行效能。
  
  參考資料

將 list_sort.h 中將 list_cmp_func_t 的定義加入到 qtest.c

typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *,
        const struct list_head *, const struct list_head *);

為一個 Function Pointer ，並且因為 __attribute__((nonnull(2,3))) 所以第二以及第三個參數不能為 null

接著根據 list_sort.c 的註解來實作 comparison function

if (a > b) return > 0
if (a < b) return <= 0 或保留其原本排序
list_sort 是 stable sort，所以沒必要區分 a < b 和 a == b 的情況

static int cmp_fun(void *priv,
                   const struct list_head *v1,
                   const struct list_head *v2)
{
    return strcmp(list_entry(v1, element_t, list)->value,
                  list_entry(v2, element_t, list)->value);
}

參考 do_sort 函式，實作 do_linux_sort
- 只要更改這行即可
```
list_sort(NULL, current->q, cmp_fun);
```
並從 qtest.c 的 console_init 中加入新命令 :

ADD_COMMAND(linux_sort, "Sort queue in ascending order by linux kerenl","");

但此時編譯的時候會出現錯誤訊息
- error: unknown type name ‘u8’
- 發現第 56 行宣告一個 count 變數，型態為 u8，被定義在 /tools/include/linux/types 裡
- 去查詢 /include/linux/list_sort.h 後，發現應該是沒有加上 #include <linux/types.h> 才出錯，但加上後仍然出現錯誤訊息
- 最後只好將 #include <linux/types.h> 改成 #include <stdint.h> ，並且將型態 u8 改為 uint8_t 才不會出現錯誤訊息
  
  目前還不知道確切原因

比較你自己實作的 `merge sort` 和 `Linux` 核心程式碼之間效能落差

首先參考 Linux 效能分析工具 : Perf 以及 perf Examples 來做安裝與撰寫

寫了兩個 shell script 分別用來執行 linux_sort 與 sort 的效能測試，並使用 perf report 將輸出存起來

學習怎麼寫 shell scripts

想要檢測的項目有 cache-misses , branches , instructions , context-switches

#!/bin/bash
for i in ./traces/traces_perf_linux_sort/*.cmd
do
    perf stat --repeat 5 -o "${i%.cmd}"_report -e cache-misses,branches,instructions,context-switches ./qtest -v 0 -f "$i"
done

在 lab0-c/traces 新增兩個目錄，分別存放用來測試 linux_sort 與 sort 的命令檔

.
├── traces_perf_linux_sort
│   ├── RAND_1000000.cmd
│   ├── RAND_100000.cmd
│   ├── RAND_10000.cmd
│   └── RAND_1000.cmd
└── traces_perf_sort
    ├── RAND_1000000.cmd
    ├── RAND_100000.cmd
    ├── RAND_10000.cmd
    └── RAND_1000.cmd

其中 RAND_*.cmd 的內容是參考 trace-0*-ops.cmd 來改寫，表示要 sort * 個隨機字串

option fail 0
option malloc 0
new
ih RAND 1000
linux_sort
free

要先啟用 root 權限接著再執行 .sh 檔案
若執行 .sh 檔案顯示 Permission denied
- 輸入 chmod u+x *.sh
perf report 內容

# started on Mon Feb 20 14:01:20 2023
Performance counter stats for './qtest -v 0 -f ./traces/traces_perf_linux_sort/RAND_1000.cmd' (5 runs):

          1289      cpu_core/cache-misses/                                        ( +- 43.74% )
       78,1958      cpu_core/branches/                                            ( +-  0.17% )
      516,3000      cpu_core/instructions/                                        ( +-  0.14% )
             0      context-switches                                            

     0.0008445 +- 0.0000127 seconds time elapsed  ( +-  1.50% )

實驗結果

sort

# node	cache-misses	branches	instructions	context-switches	time
1000	4443	78,9179	514,5106	0	0.0009679
10000	2960	621,6845	4248,6763	0	0.0054019
100000	79,2148	6354,8361	4,2894,2226	0	0.063659
1000000	4692,1584	6,6668,8777	44,2436,0379	152	1.03455

list_sort

# node	cache-misses	branches	instructions	context-switches	time
1000	1289	78,1958	516,3000	0	0.0008445
10000	3118	615,8586	4285,4486	0	0.0058063
100000	37,9827	6297,2125	4,3374,6650	0	0.061114
1000000	3669,3394	6,6033,1233	44,7728,5288	2	0.96378

由實驗結果可以看出上面測試項目基本上 list_sort 都比我自己實作的 sort 還要優秀，尤其在節點數 1000000 時， cache-misses , context-switches 數量相差非常大

在 `qtest` 提供新的命令 `shuffle`

想法是從 Fisher–Yates shuffle 裡面所提供的 pseudocode :

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

首先先實作一個 swap 函式，用來將節點內的數值做交換

void swap(element_t *s1, element_t *s2)
{
    char *tmp = s1->value;
    s1->value = s2->value;
    s2->value = tmp;
}

按照 pseudocode 來實作， tail 指標紀錄目前串列的最後位置
cur 指標用來紀錄隨機挑出節點的位置
接著將 cur 指標所紀錄的位置來做交換跟 tail 指標所紀錄的位置來做交換
tail = tail->prev 會紀錄下一次要交換節點的位置

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

    struct list_head *tail = head->prev;

    for (int i = q_size(head); i > 0; i--) {
        int ran = rand() % i;
        struct list_head *cur = head;
        for (int j = 0; j <= ran; j++) {
            cur = cur->next;
        }
        swap(list_entry(cur, element_t, list),
             list_entry(tail, element_t, list));
        tail = tail->prev;
    }
}

參考 qtest.c 中各個 do_* 函式，加入函式 do_shuffle
此函式在執行 q_shuffle 之前檢查佇列並發出警告訊息，接著再執行 q_shuffle :

static bool do_shuffle(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }

    if (!current || !current->q)
        report(3, "Warning: calling shuffle on null queue");
    error_check();

    if (exception_setup(true))
        q_shuffle(current->q);
    exception_cancel();

    q_show(3);
    return !error_check();
}

從 qtest.c 的 console_init 中加入新命令：

ADD_COMMAND(shuffle, "Shuffle the queue by using Fisher–Yates shuffle", "");

執行結果

cmd> new
l = []
cmd> ih RAND 5
l = [tkjacbs xauofve bjxglmkx sbtgzzd plzss]
cmd> shuffle
l = [xauofve tkjacbs bjxglmkx plzss sbtgzzd]
cmd> shuffle
l = [xauofve bjxglmkx sbtgzzd plzss tkjacbs]
cmd> shuffle
l = [plzss sbtgzzd bjxglmkx tkjacbs xauofve]

以統計的原理來分析你的實作

參考作業說明 : 統計方法驗證 shuffle
將測試程式新增到 scripts/shuffle_test.py
- 第一行要加上 #!/bin/python

1. 先計算 chi-squared test statistic
$X^{2}$

執行 python3 ./scripts/shuffle_test.py
在測試 shuffle 1000000 次後，24種結果各自的頻率如下表：

排列組合	觀察到的頻率	期待的頻率	$\frac{(O_{i} - E_{i})^{2}}{E_{i}}$
[1, 2, 3, 4]	41,566	41,666	0.240003840061441
[1, 2, 4, 3]	41,589	41,666	0.14229827677242837
[1, 3, 2, 4]	41,212	41,666	4.9468631498103965
[1, 3, 4, 2]	41,533	41,666	0.424542792684683
[1, 4, 2, 3]	41,389	41,666	1.8415254644074306
[1, 4, 3, 2]	41,778	41,666	0.3010608169730716
[2, 1, 3, 4]	41,672	41,666	0.0008640138242211876
[2, 1, 4, 3]	41,579	41,666	0.1816589065425047
[2, 3, 1, 4]	41,690	41,666	0.013824221187539001
[2, 3, 4, 1]	41,989	41,666	2.5039360629770075
[2, 4, 1, 3]	41,960	41,666	2.0744971919550714
[2, 4, 3, 1]	41,701	41,666	0.02940047040752652
[3, 1, 2, 4]	41,553	41,666	0.306460903374454
[3, 1, 4, 2]	41,758	41,666	0.1858589737435799
[3, 2, 1, 4]	41,508	41,666	0.5991455863293813
[3, 2, 4, 1]	41,561	41,666	0.26460423366773866
[3, 4, 1, 2]	41,825	41,666	0.6067537080593289
[3, 4, 2, 1]	41,798	41,666	0.41818269092305477
[4, 1, 2, 3]	41,783	41,666	0.3285412566601066
[4, 1, 3, 2]	41,567	41,666	0.2352277636442183
[4, 2, 1, 3]	41,574	41,666	0.20313925022800364
[4, 2, 3, 1]	41,862	41,666	0.9219987519800317
[4, 3, 1, 2]	41,623	41,666	0.04437671002736044
[4, 3, 2, 1]	42,110	41,666	4.731339701435223
Total			21.546104737675805

X^{2}

= 21.546104737675805

2. 決定自由度（degrees of freedom）

對於 N 個隨機樣本而言，自由度為 N - 1
本次實驗有 24 個結果，故自由度為 23

3. 選擇顯著水準

alpha 設定為常見的 0.05
從卡方分布表找合適的 P value，我們的自由度為 23
$X^{2}$ = 21.546104737675805，因為 19.021 < 21.546104737675805 < 22.337，於是 P value 介於 0.7 和 0.5 之間。

4. 統計檢定的結果不拒絕虛無假說

因為 P value（0.5~0.7）> alpha（0.05），統計檢定的結果不拒絕虛無假說（
$H_{0}$ ）
從圖表來看 shuffle 的頻率是大致符合 Uniform distribution 的

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

提出了一個工具 dudcet ，用來量測程式能否在常數時間執行完成

`TIMING LEAKAGE DETECTION`

透過輸入兩種不同的資料，檢查這兩個的執行時間分布在統計分析上是否不同

Step 1 : `Measure execution time`

Classes definition :
- leakage detection test 的類型有很多種，差別是在輸入資料類別的不同
- 最常見的就是 fix-vs-random test
  - 第一類輸入資料是一個固定的常數
  - 第二類數入資料是亂數
  - 其中第一類資料被用來觸發某些特殊的極端狀況( such as low-weight input forarithmetic operations )

Cycle counters :

現今的 CPU 提供 cycle counters 來精準的計算執行時間

在 dudct/cpucycles.h `可找到相關程式碼

#ifndef DUDECT_CPUCYCLES_H
#define DUDECT_CPUCYCLES_H

#include <stdint.h>
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);
 
#elif defined(__aarch64__)
    uint64_t val;
    asm volatile("mrs %0, cntvct_el0" : "=r"(val));
    return val;
#else
#error Unsupported Architecture
#endif
}

#endif

Environmental conditions :
- 為了減少運行環境對結果的影響，每次測量都會對應隨機的類別

Step 2 : `Apply post-processing`

在統計分析之前先做一些後處理
- Cropping
  - 典型的時間分佈為 positive skew ，可能會因為 OS 或外部程式造成測量誤差，透過裁剪超過 threshold 的測量結果
- Higher-order preprocessing :
  - 根據統計測試，可能是更有益於 high-order preprocessing

Step 3 : `Apply statistical test`

利用統計檢驗來反駁虛無假說"兩個時間分佈相同"
t-test : 使用 Welch’s t-test

參考作業說明

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

目前執行完下列指令後並沒有發出如作業規範裡類似的錯誤訊息

make clean
make SANITIZER=1
make test

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

輸入指令 make valgrind

出現很多相同的錯誤訊息，節錄部份

==70766== 32 bytes in 1 blocks are still reachable in loss record 1 of 2
==70766==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==70766==    by 0x10CC82: do_new (qtest.c:154)
==70766==    by 0x10E332: interpret_cmda (console.c:181)
==70766==    by 0x10E8E7: interpret_cmd (console.c:201)
==70766==    by 0x10ECE8: cmd_select (console.c:610)
==70766==    by 0x10F5D4: run_console (console.c:705)
==70766==    by 0x10D724: main (qtest.c:1576)

從報告中指明有一個 32 bytes 的 block 仍然可以訪問，推測可能是沒有正常釋放記憶體
檢查函式 q_free , do_free 都沒有問題
但是在 qtest.c 中的 q_quit 函式，第一行就是 return ture ，會導致下面的程式無法正常執行，以至於沒有正常釋放記憶體

將第一行的 return ture 拿掉後就沒有出現錯誤訊息了

透過 Massif 視覺化 “simulation” 過程中的記憶體使用量

首先寫要測試用的命令檔

option simulation 1
it
option simulation 0

再來執行

valgrind --tool=massif ./qtest -f traces/trace_it.cmd

如果想要將結果顯示出來，可以先安裝 massif-visualizer 後再來執行

massif-visualizer massif.out.*

simulation it
simulation ih
simulation rt
simulation rh

上述四個的共通點都是記憶體沒有被完全釋放

問題紀錄

GitHub Action 目前都無法正常運作，還沒有找到原因

2023q1 Homework1 (lab0)

開發環境

queue.[ch]

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_remove_tail

q_size

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_reverseK

q_sort

merge_list

merge_sort

q_sort

q_descend

q_merge

研讀 Linux 核心原始程式碼的 lib/list_sort.c

嘗試引入到 lab0-c 專案

比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差

在 qtest 提供新的命令 shuffle

以統計的原理來分析你的實作

1. 先計算 chi-squared test statistic X2

2. 決定自由度（degrees of freedom）

3. 選擇顯著水準

4. 統計檢定的結果不拒絕虛無假說

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

TIMING LEAKAGE DETECTION

Step 1 : Measure execution time

Step 2 : Apply post-processing

Step 3 : Apply statistical test

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

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

透過 Massif 視覺化 “simulation” 過程中的記憶體使用量

問題紀錄

Read more

Demystifying the Linux CPU Scheduler 閱讀筆記

關於 BORE 及 schedgraph 的描述

2023q1 Homework7 (ktcp)

2023q1 Homework3 (fibdrv)

`q_new`

`q_free`

`q_insert_head`

`q_insert_tail`

`q_remove_head`

`q_remove_tail`

`q_size`

`q_delete_mid`

`q_delete_dup`

`q_swap`

`q_reverse`

`q_reverseK`

`q_sort`

`merge_list`

`merge_sort`

`q_sort`

`q_descend`

`q_merge`

研讀 Linux 核心原始程式碼的 `lib/list_sort.c`

嘗試引入到 `lab0-c` 專案

比較你自己實作的 `merge sort` 和 `Linux` 核心程式碼之間效能落差

在 `qtest` 提供新的命令 `shuffle`

1. 先計算 chi-squared test statistic
$X^{2}$

`TIMING LEAKAGE DETECTION`

Step 1 : `Measure execution time`

Step 2 : `Apply post-processing`

Step 3 : `Apply statistical test`

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

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