2022q1 Homework1 (lab0)

contributed by < bochengC >

待辦事項

• q_new: 建立新的「空」佇列;
• q_free: 釋放佇列所佔用的記憶體;
• q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
• q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);
• q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點;
• [x] q_release_element: 釋放特定節點的記憶體空間 已經做好了;
• q_size: 計算目前佇列的節點總量;
• q_delete_mid: 移走佇列中間的節點，詳見 LeetCode 2095. Delete the Middle Node of a Linked List
• q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 LeetCode 82. Remove Duplicates from Sorted List II
• q_swap: 交換佇列中鄰近的節點，詳見 LeetCode 24. Swap Nodes in Pairs
• q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈 結串列節點，換言之，它只能重排已經存在的節點;
• q_sort: 以遞增順序來排序鏈結串列的節點，可參閱 Linked List Sort 得知實作手法;

環境

$uname -a
Linux RTX2070s1 5.11.0-49-generic #55-Ubuntu SMP Wed Jan 12 17:36:34 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux

$gcc --version
gcc (Ubuntu 10.3.0-1ubuntu1) 10.3.0
Copyright (C) 2020 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
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          12
On-line CPU(s) list:             0-11
Thread(s) per core:              2
Core(s) per socket:              6
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           158
Model name:                      Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz
Stepping:                        10
CPU MHz:                         3200.000
CPU max MHz:                     4600.0000
CPU min MHz:                     800.0000
BogoMIPS:                        6399.96
Virtualization:                  VT-x
L1d cache:                       192 KiB
L1i cache:                       192 KiB
L2 cache:                        1.5 MiB
L3 cache:                        12 MiB
NUMA node0 CPU(s):               0-11
Vulnerability Itlb multihit:     KVM: Mitigation: VMX disabled
Vulnerability L1tf:              Mitigation; PTE Inversion; VMX conditional cache flushes, SMT vulnerable
Vulnerability Mds:               Mitigation; Clear CPU buffers; SMT vulnerable
Vulnerability Meltdown:          Mitigation; PTI
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl and seccomp
Vulnerability Spectre v1:        Mitigation; usercopy/swapgs barriers and __user pointer sanitization
Vulnerability Spectre v2:        Mitigation; Full generic retpoline, IBPB conditional, IBRS_FW, STIBP conditional, RSB filling
Vulnerability Srbds:             Mitigation; Microcode
Vulnerability Tsx async abort:   Mitigation; Clear CPU buffers; SMT vulnerable
Flags:                           fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 erms invpcid rtm mpx rdseed adx smap clflushopt intel_pt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp md_clear flush_l1d

q_size

嘗試跟著文件做所有的步驟，在 git commit 之前要先用 clang-format -i queue.c 整理排版，再用 git commit -a ，標題的首字需要大寫

q_new

回傳一個指向 list_head 空間的指標即可

完整程式碼

struct list_head *q_new()
{
    struct list_head *p = malloc(sizeof(struct list_head));
    if (!p)
        return NULL;
    INIT_LIST_HEAD(p);
    return p;
}

q_free

1. 要注意除了list_head 每個 element 都是 element_t 所以要用 list_head 與 container_of / list_entry 回推，原本在 list_for_each_safe 中增加了 if(p) 的判斷式，但這部分會由 macro 處理，不必多此一舉。
2. 原本只有手動 free element_t 本身，會發生 ERROR: Corruption detected in block with address 0x559b9fa683a0 when attempting to free it 的錯誤，很明顯的是一個跟記憶體相關的問題，但是在 free 裡面又沒有其他的問題， 因此檢查 element_t 發現， element_t->value 包含一整個字串，需要將整個字串 free ，也發現有 q_release_element 可以使用。

完整程式碼

void q_free(struct list_head *l)
{
    struct list_head *p, *q;
    if(l->next) {
        list_for_each_safe (p, q, l) {
            list_del(node);
            q_release_element(list_entry(node, element_t, list));
        }
    }
    free(l);
}

q_insert_head

如果在 element_t *p = malloc(sizeof(element_t)); 前面加上 struct 會發生 incomplete type的狀況
1. element 是在 queue.h 裡，所以可以直接call ~
~2. list_head 在 queue.h 的include 所以要用 struct list_head
element_t 有用 typedef 所以能用 element_t 。

1. 要複製字串，沒有先做出連續的記憶體空間
2. 做出連續記憶體空間之後，才能利用 strncpy 複製字串
   原先版本

    char *sc = malloc(strlen(s)); 
    strcpy(sc, s);
    p->value = sc;

這裡在後續處理 q_free() 時發現錯誤， ERROR: Corruption detected in block with address 0x55fb207433a0 when attempting to free it ，必須將 char *sc = malloc(strlen(s)); 改成， char *sc = malloc(strlen(s)+1); ， strlen() 回傳的長度不包含 \0 終止符號，所以事實上終止符號被放置在一個不允許的地方，因此在free的時候會報錯！ 又或者是利用 strdup() 直接複製整個字串包含終止符號，解決這個問題。

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *p = malloc(sizeof(element_t));
    if (!p)
        return false;
    char *sc = malloc(strlen(s)+1); 
    strcpy(sc, s);
    p->value = sc;
    list_add(&(p->list), head);
    return true;
}

後續在 make test 的時候又發現，在測試12、13 test of malloc failure 的時候都沒辦法拿到完整的分數。經過思考發現有可能發生 element_t 正確建立了，但是 char *sc 建立失敗的可能，因此加入新的判斷條件，程式碼改進為。

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *p = malloc(sizeof(element_t));
    if (!p)
        return false;
    char *sc = malloc(strlen(s)+1); 
    if (!sc)
        return false;
    strcpy(sc, s);
    p->value = sc;
    // p->value = strdup(s);
    list_add(&(p->list), head);
    free(p);
    return true;
}

最後的 free(p) 是因為 git commit -a 的時候會有 error: Memory leak: p [memleak] 的問題才加入，但是 free§ 的話，會讓程式出現 segamentation fault

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *p = malloc(sizeof(element_t));
    if (!p)
        return false;
    char *sc = malloc(strlen(s)+1); 
    if (!sc)
        return false;
    strcpy(sc, s);
    p->value = sc;
    // p->value = strdup(s);
    list_add(&(p->list), head);
    free(p);
    return true;
}

q_insert_tail

同上，不多說

完整程式碼

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *p = malloc(sizeof(element_t));
    if (!p)
        return false;
    char *sc = malloc(strlen(s)+1); 
    if (!sc){
        free(p);
        return false;
    }
    strcpy(sc, s);
    p->value = sc;
    // p->value = strdup(s);
    list_add_tail(&p->list, head);
    return true;
}

q_remove_head

完整程式碼

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || head->next == head)
        return NULL;
    element_t *p = container_of(head->next, element_t, list);
    if (bufsize) {
        strncat(sp, p->value, bufsize - 1);
        strncat(sp, "\0", 1);
    }
    list_del(head->next);
    return p;
}

q_delete_mid

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || head->next == head->prev)
        return false;
    struct list_head *p1 = head->next, *p2 = head->next;
    while (p1 != head && p1->next != head) {
        p1 = p1->next->next;
        p2 = p2->next;
    }
    list_del(p2);
    element_t *ptr = list_entry(p2, element_t, list);
    q_release_element(ptr);
    return true;
}

q_delete_dup

這是一個已經被 sort 的 linkedlist

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || head->next == head || head->next == head->prev ||
        head->next->next == head->prev)
        return false;
    struct list_head *p, *q;
    // element_t *p_element, *q_element;
    char *s = malloc(sizeof(char));
    list_for_each_safe (p, q, head) {
        element_t *p_element = container_of(p, element_t, list);
        element_t *q_element = container_of(q, element_t, list);
        if (!strcmp(p_element->value, q_element->value)) {
            strcpy(s, p_element->value);
            list_del(p);
        } else if (!strcmp(s,
                           p_element->value)) {  // strcmp return 0 means equal
            list_del(p);
        }
    }
    return true;
}

在定義某個東西的同時，順便將值給入，是比較好的做法。
上述的程式碼會有 segmentation fault ，理由是在 list_for_each_safe 中，如果 q_element 是 NULL 的時候， q_element->value 會是一個非法的存取，要改成下

        if (!strcmp(s,
                           p_element->value)) {  // strcmp return 0 means equal
            list_del(p);
            q_release_element(p_element);
        } else if (!strcmp(p_element->value, q_element->value)) { // equal  原本把
            s = strdup(p_element->value);
            list_del(&p_element->list);
            q_release_element(p_element);
        }

q_swap

1. 要利用 head 指標確認結尾，所以必須要另外創造三個指標，來指出三個位子

完整程式碼

void q_swap(struct list_head *head)
{
    if (!head || head->next == head || list_is_singular(head))
        return;
    struct list_head *odd = NULL, *even = NULL, *curr = head->next;
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    while (curr != head && curr->next != head) {
        odd = curr;
        even = curr->next;
        list_move(even, curr->prev);
        list_move(odd, even);
        curr = curr->next;
    }
}

q_reverse

初始版本

void q_reverse(struct list_head *head)
{
    if (!head || (head->next == head))
        return;
    struct list_head *p = head->next, *tmp;
    while (p != head) {
        tmp = p->next;
        p->next = p->prev;
        p->prev = tmp;
        p = p->prev;
    }
    tmp = head->next;
    head->next = head->prev;
    head->prev = tmp;
}

API版本

void q_reverse(struct list_head *head)
{
    if (!head || (head->next == head))
        return;
    struct list_head *p = head->next, *tmp;
    while (p != head) {
        tmp = p->next;
        p->next = p->prev;
        p->prev = tmp;
        p = p->prev;
    }
    tmp = head->next;
    head->next = head->prev;
    head->prev = tmp;
}

q_sort

struct list_head *merge(struct list_head *l1, struct list_head *l2)
{
    // printf("enter merge \n");
    struct list_head *head = NULL, **ptr = &head;  //, **node;
    for (; l1 && l2; ptr = &(*ptr)->next) {
        char *l1_ch = list_entry(l1, element_t, list)->value;
        char *l2_ch = list_entry(l2, element_t, list)->value;
        // printf("l1 is %s l2 is %s\n", l1_ch, l2_ch);
        if (strcmp(l1_ch, l2_ch) >= 0) {
            // printf("enter l2 %s\n", l2_ch);
            *ptr = l2;
            l2 = l2->next;
        } else {
            // printf("enter l1 %s\n", l1_ch);
            *ptr = l1;
            l1 = l1->next;
        }
        // *ptr = *node;
        // ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *) ((uintptr_t) l1 | (uintptr_t) l2);
    // printf("out merge \n");
    return head;
}
// 切開 in this part every head have value
struct list_head *mergesort(struct list_head *head)
{
    // printf("enter mergesort \n");
    if (!head || !head->next) {
        // printf("single node out mergesort \n");
        return head;
    }
    struct list_head *fast = head, *slow = head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    // set the left part cut point
    slow->prev->next = NULL;
    struct list_head *left = mergesort(head);
    struct list_head *right = mergesort(slow);
    // printf("out mergesort \n");
    // struct list_head* new_head = merge(left, right);
    // list_for_each(element_t, new_head, list){
    //     printf("%s \n", element_t->value);
    // }
    // return new_head
    return merge(left, right);
}

/*
 * Sort elements of queue in ascending order
 * No effect if q is NULL or empty. In addition, if q has only one
 * element, do nothing.
 */
void q_sort(struct list_head *head)
{
    // printf("enter qsort \n");
    if (!head || head->next == head || list_is_singular(head)) {
        // printf("what \n");
        return;
    }
    // use merge sort I can use 老師的資料
    // set the terminated situatino
    head->prev->next = NULL;
    head->next = mergesort(head->next);
    // printf("back qsort \n");
    struct list_head *node = head->next;
    // element_t* el_t ;
    while (node->next != NULL) {
        // el_t = list_entry(node, element_t, list);
        // printf("node is %s", el_t->value);
        node->next->prev = node;
        node = node->next;
    }
    head->next->prev = head;  整
    head->prev = node;
    node->next = head;
}

:::

每個 function 都要注意的部分

1. if (!head || head->next == head) 要確認 head 不為 NULL 或是 只有單獨 head 節點，但是沒有 element_t 的狀況。
2. 有 malloc 那就要有 free ， 注意 strdup() 背後也使用了 malloc 的行為，所以要記得 free 。
3. strcpy 是有機會發生問題的函數，因此利用 strncpy 處理

make valgrind 檢查

# Test of insert_head and remove_head
==52383== 14 bytes in 1 blocks are still reachable in loss record 1 of 3
==52383==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==52383==    by 0x4A4B3BE: strdup (strdup.c:42)
==52383==    by 0x112415: linenoiseHistoryAdd (linenoise.c:1677)
==52383==    by 0x112FA8: linenoiseHistoryLoad (linenoise.c:1775)
==52383==    by 0x10D810: main (qtest.c:1026)
==52383== 
==52383== 122 bytes in 19 blocks are still reachable in loss record 2 of 3
==52383==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==52383==    by 0x4A4B3BE: strdup (strdup.c:42)
==52383==    by 0x112389: linenoiseHistoryAdd (linenoise.c:1677)
==52383==    by 0x112FA8: linenoiseHistoryLoad (linenoise.c:1775)
==52383==    by 0x10D810: main (qtest.c:1026)
==52383== 
==52383== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==52383==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==52383==    by 0x1123D5: linenoiseHistoryAdd (linenoise.c:1665)
==52383==    by 0x112FA8: linenoiseHistoryLoad (linenoise.c:1775)
==52383==    by 0x10D810: main (qtest.c:1026)
==52383== 

根據圖片上的描述問題出在strdup 裡面，

    if(fp)  // 有兩種狀況 1. 有讀取檔案 2. 純粹執行
        freeHistory();  // add here ?

在 linenoiseHistoryLoad 的最後加上這倆行程式碼，會讓一般的 ./qtest 出問題，
這個問題的步驟是

1. ./qtest
2. quit 就會發生 free(): double free detected in tcache 2 的問題
   因此這應該是個錯誤的解決方式，後來在程式碼中，發現錯誤原因應該是在 atexit(linenoiseAtExit); 上

int atexit(void (*func)(void));
The C library function int atexit(void (*func)(void)) causes the specified function func to be called when the program terminates. You can register your termination function anywhere you like, but it will be called at the time of the program termination.
從 linenoise -> linenoiseRaw -> enableRawMode -> atexit(linenoiseAtExit); 讓上述設置在 linenoiseHistoryLoad 的 freeHistory(); 發生重複free的狀況。

因此回頭尋找為何原先手動執行的時候不會發生 history 沒有被 free() 的狀況，發現以下程式碼。

    if (!atexit_registered) {  // add this? check the normal version
        atexit(linenoiseAtExit);
        atexit_registered = 1;
    }

將這段程式碼新加入到 linenoiseHistoryLoad 內，就可以解決問題了。

目前剩下 trace-17-complexity 會發生在 add_cmd add_param 的問題，但是個問題有時候會出現有時候不會出現。

將 lib/list_sort.c 合併入 lab0

要求: 研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
在 list_sort.c 中有長長一段說明，其中提到了，利用這種二的冪合併方式，可以避免 cache thrashing ，只要 cache 可以容納 (2^k)*3 大小的 list。

在聽老師 week4的時候有感受到這部分實作的優勢，因為每次都是往最近對讀取的 sublist/node 排序，所以除非 cache 已經滿了，需要重新從 memory抓資料，才會需要用 cache 的更換
以下舉的例子是在節錄在 list_sort.c 中的程式碼片段執行結果

    do {
		size_t bits;
		struct list_head **tail = &pending;

		/* Find the least-significant clear bit in count */
		for (bits = count; bits & 1; bits >>= 1)
			tail = &(*tail)->prev;
		/* Do the indicated merge */
		if (likely(bits)) {
			struct list_head *a = *tail, *b = a->prev;

			a = merge(priv, cmp, b, a);
			/* Install the merged result in place of the inputs */
			a->prev = b->prev;
			*tail = a;
		}

		/* Move one element from input list to pending */
		list->prev = pending;
		pending = list;
		list = list->next;
		pending->next = NULL;
		count++;
	} while (list);

兩個例子分別是 count = 8 跟 count = 9 的狀況，利用這兩個狀況可以比較快的了解這個演算法是如何 sort的

count = 8 = 1000b 時， 此時在 pending list 內共有8個 nodes ， *tail 指向 h node ， bit = 1000b ，起始狀態圖如下

在進入 if 之前， *tail 指向 h node ，因此進入 if 後， 會是 g,h node進行 merge ，下圖是離開 if 後的結果。

count = 9 = 1001b 時， 此時在 pending list 內共有9個 nodes ， *tail 指向 i node ， bit = 1000b ，起始狀態圖如下

此輪 count = 1001b ，故 bits = 1001b ， tail = &(*tail)->prev ; 會執行一次， 此時， *tail 指向 G node， 接著會進入 if 之內，將 G,E 兩個 sublist 合併，此輪結束的結果如下圖

可以往後推斷， bits = 1010b 時，會是 I,J node 合併， bits = 1011b 時，才會是 A,E 子串列合併。
在文件中的敘述表示利用這種方式可以降低 cache thrashing 的次數。

排序方式比較，實驗設計

以 .cmd 檔，分別對兩種排序方式進行十萬個 node 的排序測試，為了降低字串長度的差別影響實際的結果，將每個節點的字串長度設定為6(在 qtest.c 144)，利用 perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles,l1d_pend_miss.pending,L1D_PEND_MISS.PENDING_CYCLES,L1D.REPLACEMENT ./qtest -v 3 -f traces/trace-Rand.cmd，進行五次測試，並且測量純粹產生十萬個node需要的指令數，扣掉之後再進行分析。

sudo sh -c " echo 0 > /proc/sys/kernel/kptr_restrict"
sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches'
sudo sh -c " echo -1 > /proc/sys/kernel/perf_event_paranoid"
先利用這三個 cmd 准許 perf

about l1D miss

l1d.replacement
[L1D data line replacements]
l1d_pend_miss.pending
[L1D miss outstandings duration in cycles]
l1d_pend_miss.pending_cycles
[Cycles with L1D load Misses outstanding]
這兩個有什麼差別

以下是三種分別的結果

by my sort
       119,000,695      cache-misses              #   53.881 % of all cache refs      ( +-  0.74% )  (57.07%)
       220,859,095      cache-references                                              ( +-  0.43% )  (57.18%)
     2,675,143,084      instructions              #    0.51  insn per cycle           ( +-  0.19% )  (71.46%)
     5,263,504,595      cycles                                                        ( +-  0.22% )  (71.48%)
     4,641,818,427      l1d_pend_miss.pending                                         ( +-  0.50% )  (71.54%)
     3,521,064,443      L1D_PEND_MISS.PENDING_CYCLES                                     ( +-  0.46% )  (71.45%)
        84,211,551      L1D.REPLACEMENT                                               ( +-  0.24% )  (71.28%)

           1.15522 +- 0.00383 seconds time elapsed  ( +-  0.33% )
            
by linux list_sort
        90,458,525      cache-misses              #   56.776 % of all cache refs      ( +-  2.67% )  (56.74%)
       159,324,058      cache-references                                              ( +-  2.03% )  (56.99%)
     2,652,501,582      instructions              #    0.56  insn per cycle           ( +-  0.51% )  (71.44%)
     4,729,713,609      cycles                                                        ( +-  0.36% )  (71.60%)
     4,611,768,094      l1d_pend_miss.pending                                         ( +-  2.87% )  (71.73%)
     3,259,718,213      L1D_PEND_MISS.PENDING_CYCLES                                     ( +-  0.87% )  (71.66%)
        65,302,933      L1D.REPLACEMENT                                               ( +-  1.21% )  (71.27%)

           1.04382 +- 0.00410 seconds time elapsed  ( +-  0.39% )

by rand 
        16,454,796      cache-misses              #   85.709 % of all cache refs      ( +-  0.17% )  (56.00%)
        19,198,404      cache-references                                              ( +-  0.81% )  (56.06%)
     1,743,048,580      instructions              #    1.57  insn per cycle           ( +-  0.29% )  (70.73%)
     1,111,946,653      cycles                                                        ( +-  0.73% )  (71.98%)
       368,212,084      l1d_pend_miss.pending                                         ( +-  0.12% )  (73.23%)
       366,997,770      L1D_PEND_MISS.PENDING_CYCLES                                     ( +-  0.21% )  (72.01%)
         8,174,014      L1D.REPLACEMENT                                               ( +-  0.17% )  (70.71%)

           0.24576 +- 0.00230 seconds time elapsed  ( +-  0.93% )


將兩個排序扣掉製作 nodes 的時間與步驟
my sort
         102545899      cache-misses            
         201660691      cache-references                                             
         932094504      instructions              
        4151557942      cycles                                                        
        4273606343      l1d_pend_miss.pending                                         
        3154066673      L1D_PEND_MISS.PENDING_CYCLES                                     
          76037537      L1D.REPLACEMENT   
          0.90946 seconds
          
linux list_sort
          74003729      cache-misses            
         140125654      cache-references                                             
         909453002      instructions              
        3617766956      cycles                                                        
        4243556010      l1d_pend_miss.pending                                         
        2892720443      L1D_PEND_MISS.PENDING_CYCLES                                     
          57128919      L1D.REPLACEMENT
          0.79806 seconds

由上方的分析可以發現，在兩種不同的 sort的方式下， list_sort.c 的演算法是一個 cache-friendly 的演算法，增加了比較的次數，但是可以降低 cache-miss的次數，我自己實現的 q_sort 是基於 merge_sort 的方式建立，理論上可以達到最佳的 O(nlogn) 的時間複雜度，但是在實際的實驗中可以發現在 L1Dcache-miss 上有約莫三千萬次的差距，因為大量的 cache-miss 讓理論上最快的 O(nlogn) 的演算法反而比 cache-friendly 的演算法慢了一成，十分值得引以為戒。

增加 shuffle cmd

在 qtest 提供新的命令 shuffle，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作

這個演算法簡單來說就是在還沒有亂序過的子序列中挑出一個，放到後面的序列中。

void q_shuffle(struct list_head* head){
    if (!head || head->next == head || list_is_singular(head))
        return ;
    int cnt = 0 ;
    struct list_head* ptr=head->next;
    while(ptr != head){
        cnt++;
        ptr = ptr->next;
    } 
    int rand_num = 0 ;
    while( cnt !=1){
        ptr = head->next ; // if rand_num = 0 means remove the first node 
        rand_num = rand();
        rand_num = rand_num % cnt ;
        while(rand_num){
            ptr = ptr->next;
            rand_num--;
        }
        list_move_tail(ptr, head);
        cnt--;
    }
}

加入 tiny-web-server

在 qtest 提供新的命令 web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令

• 可依據前述說明，嘗試整合 tiny-web-server

整份 tiny-web-server 的code直接抄過來會有滿滿的問題，審慎使用

整套功能簡單來說就是開啟一個web server 之後，會持續接受資訊，如果有人給出指令，會執行指令

上述想法， 先做出list_sortk的 cmd 然後再看原本的cmd的呼叫方式依樣葫蘆做出一樣的呼叫方式，最後再研究shuffle 與 web 有 time 可以使用 可以簡單比較效能

1. 先把整份 tiny-web 的code 全部放到 linenoise去
2. 依照提示修改 process
3. 在 http_request 中加入 char* function_name 成員
4. 修改 run_console
5. 在 linenoiseEdit 加入 non-blocking 的程式碼 在 linenoise.h 加上 extern int listenfd ， 因為這個變數在 console.c 跟 linenoise.c 裡面都會用到

Q : non-blocking 的修改要放在哪裡? 一開始放在 linenoiseEdit， 後來改到 do_web 函數。

int flags = fcntl(listenfd, F_GETFL);
fcntl(listenfd, F_SETFL, flags | O_NONBLOCK);

static bool do_web(int argc, char *argv[])
{
   listenfd = open_listenfd(9999);
   noise = false;
   // add for non-blocking
   int flags = fcntl(listenfd, F_GETFL);
   fcntl(listenfd, F_SETFL, flags | O_NONBLOCK);
   return true;
}

6. 把 socket_init 換成 open_listenfd(9999 )
7. 原本在 handle_request 的部分 直接把 parse_request 拿來用，但是會發生 seg fault ，研究了一下發現應該是 read 會有個讀取的指標往後移動， 因為是同樣的 fd 所以再次 read 的時候會出現問題 ，所以最後決定在 parse_request 函式把 req->function_name 建立好
8. 加入以下程式碼，讓 LOG可以出現

#ifndef NO_LOG_ACCESS
#define LOG_ACCESS 
#endif

9. log_access 的 req->filename 改成 req->function_name
10. 解決問題: style: Redundant condition: If 'EXPR', the comparison 'EXPR != '\0'' is always true. [redundantCondition] while (*p && (*p) != '\0') { // 整理 function name

linenoise.c:1215:15: style: Redundant condition: If 'EXPR', the comparison 'EXPR != '\0'' is always true. [redundantCondition]
    while (*p && (*p) != '\0') {  // 整理 function name
              ^
linenoise.c:1163:13: portability: %lu in format string (no. 2) requires 'unsigned long *' but the argument type is 'size_t * {aka unsigned long *}'. [invalidScanfArgType_int]
            sscanf(buf, "Range: bytes=%lu-%lu", &req->offset, &req->end);
            ^
linenoise.c:1158:5: warning: sscanf() without field width limits can crash with huge input data. [invalidscanf]
    sscanf(buf, "%s %s", method, uri); /* version is not cared */
    ^
改成 這裡為什麼不是 1024 ?
sscanf(buf, "%1023s %1023s", method, uri); /* version is not cared */

其他問題

建好 web server 之後，會遇到另外兩個個問題
問題1，./qtest 輸出狀態會變成以下的模式，會有嚴重的echo 影響，必須手動利用 option echo 0 關閉。

cmd> new
cmd> new
l = []
cmd> ih a
cmd> ih a
l = [a]

這個部分的問題是明明都是執行 ./qtest 但是在還沒有加入 web-server 之前都不用手動關閉 echo ，但是加入 web-server 之後，就必須要手動關閉 echo 了，關鍵在 lab0 的修改中改掉了 if (has_infile) 的部分

    if (readfds && FD_ISSET(infd, readfds)) {
        /* Commandline input available */
        FD_CLR(infd, readfds);
        result--;
-       if (has_infile) {
        char *cmdline;
        cmdline = readline();
        if (cmdline)
            interpret_cmd(cmdline);
-       }

在 readline() 中，有以下的程式碼片段會多輸出一次 >cmd 必須使用 options echo 0 手動關閉功能。

    if (echo) {
        report_noreturn(1, prompt);     // because echo > 0 ? so print?
        report_noreturn(1, linebuf);
    }

問題二: tab 鍵 自動完成的效果會消失，這部分功能的實現在 linenoiseEdit 中， linenoise()->linenoiseRaw()->linenoiseEdit()

        if (c == 9 && completionCallback != NULL) {
            c = completeLine(&l);
            /* Return on errors */
            if (c < 0)
                return l.len;
            /* Read next character when 0 */
            if (c == 0)
                continue;
        }

在下列的問題與解決，讓沒有開 web server的狀態，能夠正常的補齊。但是如何在 web_server 的狀態下，讓自動補齊可以使用？

問題: 為何會直接卡在 accept request, fd is -1, pid is 7673?
問題分析：

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

在上述的程式碼中，如果 noise 為1的狀況下，會依序進入 linenoise() linenoiseRaw() linenoiseEdit function，根據 web-server 的修改步驟，此時 linenoiseEdit 中已經有以下的程式碼

while (1) {
    char c;
    int nread;
    char seq[3];

    fd_set set;
    
    FD_ZERO(&set);
    FD_SET(listenfd, &set);
    FD_SET(stdin_fd, &set);
    int rv = select(listenfd + 1, &set, NULL, NULL, NULL);
    struct sockaddr_in clientaddr;
    socklen_t clientlen = sizeof clientaddr;
    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;
    }
}

在第八跟第九行的 FD_SET() macro 將 stdin_fd 與 listenfd 加入 set 之中，代表在沒有任何錯誤的狀態下，在 switch 中，必然會進入 23行的 default，則必然會進入第一個 if 但此時 web 還沒有被開啟，也不會有 request 進入該程式，因此會在 process() 內的 parse_request() 內的 while 迴圈持續執行，而不會跳出

while (buf[0] != '\n' && buf[1] != '\n') { /* \n || \r\n */
    rio_readlineb(&rio, buf, MAXLINE);
    if (buf[0] == 'R' && buf[1] == 'a' && buf[2] == 'n') {
        sscanf(buf, "Range: bytes=%lu-%lu", &req->offset,
               (unsigned long *) (&req->end));
        // Range: [start, end]
        if (req->end != 0) {
            req->end++;
        }
    }
}

如果以 24行的作法的話會讓程式卡在 cmd> accept request, fd is -1, pid is 5973 無法進行近一步的處理。
解決： 將一開始在 linenoiseEdit 的修改取消就可以了！

未完成

• 除了修改程式，也要編輯「作業區」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:

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

    • 先執行 qtest 再於命令提示列輸入 help 命令，會使 開啟 Address Sanitizer 觸發錯誤，應予以排除 ???

• 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
  Massif 是 valgrind 其中一個東西
  massif的使用參考

massif-visualizer 不知道怎麼處理遇到的問題，先擱置

解釋 select

解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點。可對照參考 CS:APP 第 10 章重點提示
int select(int nfds, fd_set *restrict readfds, fd_set *restrict writefds, fd_set *restrict exceptfds, struct timeval *restrict timeout);
cmd_select ,linenoiseEdit 都有 select

與select 主要相關的行為有以下幾個

FD_ZERO(): This macro clears (removes all file descriptors from) set. It should be employed as the first step in initializing a file descriptor set.
FD_SET(): This macro adds the file descriptor fd to set. Adding a file descriptor that is already present in the set is a no-op, and does not produce an error.
FD_CLR(): This macro removes the file descriptor fd from set. Removing a file descriptor that is not present in the set is a no-op, and does not produce an error.
FD_ISSET(): select() modifies the contents of the sets according to the rules described below. After calling select(), the FD_ISSET() macro can be used to test if a file descriptor is still present in a set. FD_ISSET() returns nonzero if the file descriptor fd is present in set, and zero if itis not.

簡而言之， FD_ZERO() 清空整個 fd set 會用在初始化， FD_SET() 將 fd 加入到 fd set 中， FD_CLR() 移除某個 fd ， FD_ISSET() 確認某個 fd 是否在 fd set 中。

• 研讀論文〈Dude, is my code constant time?〉，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student's t-distribution 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
• 指出現有程式的缺陷 (提示: 和 RIO 套件 有關) 或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request

WARNING: select() can monitor only file descriptors numbers that are less than FD_SETSIZE (1024)—an unreasonably low limit for many modern applications—and this limitation will not change. All modern applications should instead use poll(2) or epoll(7), which do not suffer this limitation.

提供的內建函數

INIT_LIST_HEAD
list_add
list_add_tail
list_del
list_del_init
list_empty
list_is_singular
list_splice - 把 Alist 加到 Blist 的前面
list_splice_tail
list_splice_init
list_cut_position
list_move - move a list node to the beginning of the list
list_move_tail() - Move a list node to the end of the list
list_entry() - Calculate address of entry that contains list node
list_first/last_entry() - get first/last entry of the list
list_for_each - iterate over list nodes
用make check檢查 make test 評分

後記

在用 make test 的時候看到可以顯示目前運行多少，就去查了一下 qtest 的原始碼看到神奇的一行
printf("\033[A\033[2K");
便去查了一下到底這行在幹嘛
By this可以知道他是ansi的控制碼，可以操控游標的行為。
再從這個網站拿到方塊格子的輸入方式 這個網站 ，拼湊出一個進度條

#include <iostream>
#include <unistd.h>
using namespace std;

int main()
{
    cout<<"Hello World" << endl;
    int j , cnt = 0;
    bool status = true; 
    for(int i = 1 ; i < 100000000000 ; i++){
        //printf("\033[A\033[2K");
        cnt =0;
        if(status){
            j = i%20;
        }else{
            j = 20 - i%20;
        }
        printf("progress:[");
        while( cnt  < j){
            //usleep(20);
            cnt++;
            //printf("*");
            printf("▉");
            printf("\033[32m");
            //printf(" \033[34m");
        }
        int spare_cnt = 20-j ;
        while( spare_cnt > 0 ){
            printf(" ");
            spare_cnt--;
        }
        printf("] %d / %d ％", j*5 , 100);
        printf("\n");
        if( i%40  == 39){
            status = true;
        }else if( i%20  ==19){
            status = false;
        }
        printf("\033[A\033[2K");
        usleep(200000);
        //printf("meas: %7.2lf M \n ", (i / 1e6));
    }
    
    
    return 0;
}

char *bar = (char *)malloc(sizeof(char) * (len + 1));
printf("progress:[%s]%d%%\r", bar+len-i, i+1);  

[%s] 可以直接輸出某段string

gcc -o list_sort -g list_sort.c -I/usr/src/linux-headers-5.4.0-99-generic/include -I 是加入including path

// note : e右 s下 w左 n上
a:next:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
b:prev:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
b:next:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="next"];
c:prev:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, label="prev"];
c:next:c -> d