2024q1 Homework1 (lab0)

contributed by < ShawnXuanc >

Reviewed by `SimonLee0316`

你的洞見呢？

Reviewed by `SHChang-Anderson`

new_element 實作中提到可以使程式碼更加簡潔，請提出改進的規劃。
檢視 commit 連結是否貼錯，q_swap, q_ascend, q_descend commit 連結點入皆為 q_merge 的實作。
嘗試使用 List API 如 : list_move_tail 或 list_move 透過不同順序移動節點達成 q_swap 實作。

收到非常感謝會將內容進行修正並改進
已搭配 list_move 來修正 q_swap
shawn

Reviewed by `Shiang1212`

在如何寫一個 Git Commit Message 有提到：內文每行最多 72 字。

Git 不會把任何文字自動換行。當你在撰寫 commit message 內文的時候，你需要注意左邊的 margin，並且手動將超過 margin 的文字換到下一行。

如 089c5e5 和 909cd79 皆沒有滿足要求。雖然只是簡單的換行，但能有效提高 commit message 的可讀性。

已修改 commit 進行換行非常感謝
修改後的 commit 為 b14916f 以及 8d3be5a
shawn

開發環境

$ gcc --version
(Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

$ 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):                        4
On-line CPU(s) list:           0-3
Vendor ID:                     GenuineIntel
Model name:                    Intel(R) Core(TM) i5-7267U CPU @3.10GHz
CPU family:                    6
Model:                         142
Thread(s) per core:            2
Core(s) per socket:            2
Socket(s):                     1
Stepping:                      9
CPU max MHz:                   3500.0000
CPU min MHz:                   400.0000
BogoMIPS:                      6199.99

由於使用的是 macbook ，當初在燒錄 ubuntu 時遇到了一些問題，在使用 balenaEtcher 時無法正確燒錄，在經過查詢之後發現使用下方指令命令開啟燒錄軟體才能正常燒錄，若有遇到相同問題可以嘗試使用下方命令開啟

$ sudo /Applications/balenaEtcher.app/Contents/MacOS/balenaEtcher

在進行程式碼測試時可以善加利用 qtest 以及 Valgrind 來評估程式的正確性以及處理記憶體洩漏問題，這樣的方式有助於更深入理解問題發生得原因，幫助我們更加精確的理解問題的所在

通過使用 qtest 可以執行所撰寫的測試案例，確保程式行為符合預期，搭配使用 Valgrind 可以知道記憶體出現問題的地方，並搭配所提供的資料，找到出現問題的原因

在進行 git commit 時務必仔細閱讀 How to write a git commit message 並遵守其中的七個步驟，如果不慎傳遞了錯誤的 commit 內容或是想修改先前的提交，可以使用 git rebase <commit Id> -i 來修改正確的內容，最後記得使用 git push -f 將修改過後的內容上傳

指定佇列的操作

`q_size`

第一次接觸 list_for_each 這類型的巨集使用所以還不太習慣，但藉由通過範例的練習，更加了解使用方式，並慢慢熟悉 linux 核心風格鏈結串列操作

不該將 through 稱作「通過」，否則你如何區隔 pass (通過) 呢？

了解，會對用詞更加注意
shawn

`q_free`

函式功能為釋放一個佇列，在釋放每個 element_t 時，需要先釋放結構中的字串，然後釋放結構本身，最後將作為 head 節點的記憶體空間釋放

`q_insert_head` and `q_inset_tail`

commit e956281

留意以下程式碼的縮排

避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。

謝謝老師幫忙修正錯字
shawn
會更加注意在中英文詞彙上的使用謝謝老師shawn

函式功能為將新增的元素加到佇列時，要注意在複製字串內容~~創建字串~~ 時要使用 malloc 來配置記憶體，為避免程式碼重複出現，使用一個新的函式 new_element 來省去重複的程式碼

如果是使用 strcpy 會有記憶體問題，因為 strcpy 不會事先檢查字串長度，所以改成使用 strncpy

本處並非「創建字串」，充其量只是配置必要的記憶體空間並複製給定的字串內容。改進你的漢語表達。

了解謝謝老師shawn

`new_element`

commit e956281

不符合作業規範，請用 git rebase -i 重新撰寫 git commit message，務必詳閱作業說明提及的規範。

對此部份會再修改謝謝老師 shawn

bool new_element(element_t **element, char *s) 
{
        if (!s)
        return true;
        int len = strlen(s) + 1;
        (*node) = malloc(sizeof(element_t));
        char *tmp_s = malloc(len);
        if (!*node || !tmp_s) {
            free(*node);
            free(tmp_s);
            return true;
        }
        strncpy(tmp_s, s, len);
        (*node)->value = tmp_s;

        INIT_LIST_HEAD(&(*node)->list);
        return false;
}

在這段程式碼中，通過使用指標的指標，可以讓函式不用返回節點內容，而只返回條件的判斷結果，使得程式碼的實現更加容易

Todo: 可以更加簡潔

`q_remove_head` and `q_remove_tail`

commit 1238597

HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」

收到會將不必要的程式碼移除只列出關鍵程式碼shawn

再移除節點的過程中，兩個函式的功能分別為對 head 的前一個節點與後一個節點進行節點的移除

為了防止記憶體問題，同樣使用更加安全的 strncpy ，在過程中將要傳回的字串的最後一個位置設定為 \0 ，以避免錯誤的結果

兩段程式碼不同之處僅在於要移除指標所指向的位置，為了減少重複的程式碼新增 q_remove_list，來重複利用相同的程式碼

commit b0375b1

`q_delete_dup`

一開始的想法是利用 pre 指標來紀錄重複的節點，同時使用 dup 指標來掃過所有重複節點，在過程中用 tmp 來釋放重複的節點，釋放完重複的節點後，釋放 pre 指向的節點並調整 pre 指標的位置

在處理過程中，若重複的節點是位在 head->next 時，在進行 pre 指標的移動結束後要將 pre 指標與 dup 指標指回正確的位置也就是 head->next 以及 head->next->next

可以發現上面這樣的想法會導致需要額外的特例處理，以及有太多重複的程式碼出現

經過修改之後使用 list.h 所提供的巨集，在走訪節點的過程中使用 tmp 來儲存重複的節點，當重複的節點為當前的最後一個時會需要藉由這樣的方式來將其刪除，

當走訪到最後時 safe 指標會指到 head 的位置，因為 list_entry 會發生錯誤在導致 strcmp 會判斷出記憶體洩漏的問題，需要特別處理這個例外的情況

發現記憶體洩漏問題是使用 Valgrind 進行偵測，可以看到在 queue.c 中 155 行時出現問題，除此之外也可以搭配 qtest 裡面的程式碼來進一步了解問題所在

==15908== Invalid read of size 1
==15908==    at 0x484FBD7: strcmp (in/usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==15908==    by 0x10FBBD: q_delete_dup (queue.c:154)
==15908==    by 0x10C15E: do_dedup (qtest.c:464)
==15908==    by 0x10E0F9: interpret_cmda (console.c:181)
==15908==    by 0x10E6AE: interpret_cmd (console.c:201)
==15908==    by 0x10F318: run_console (console.c:691)
==15908==    by 0x10D4EB: main (qtest.c:1280)
==15908==  Address 0xdeadbeef is not stack'd, malloc'd or (recently) free'd
==15908== 
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer==15908== 2 bytes in 1 blocks are still reachable in loss record 1 of 53

`q_swap`

commit b9536b1

+      n2->next->prev = n1;
       n1->next = n2->next;
       n2->next = n1;
       n2->prev = n1->prev;
       n1->prev = n2;
+       pre->next = n2;
+       pre = n1;

交換節點的方式是通過使用兩個指標來指向要交換位置的節點，並將這兩個節點進行位置交換

在一開始撰寫時只考慮到將兩個節點進行交換的，疏忽了指向交換節點的另外兩個節點，導致錯誤的結果

最後在交換的過程中，需要將原先與兩節點相連的節點，即 n1->prev 以及 n2->next 指向交換完的節點

commit 39bd60c

for (struct list_head *n1 = head->next->next, *pre = head;
         n1 != head && n1->prev != head; n1 = pre->next->next) {
        list_move(n1, pre);
        pre = n1->next;
    }

在經過 SHChang-Anderson 同學的 review 後收到建議，並使用 list_move 的方式來進行修改，這邊的想法是藉由讓 n1 往前移動到 pre 的下一個節點來更換位置，移動完後在更新 n1 以及 pre 的指標，藉由這樣的方式來交換兩個節點的位置，每次讓 n1 藉由 pre 來找到正確的位置

這邊要有一個比較特別的地方在於最後得判斷要判斷是否 n1->prev 為 head ，如果照著之前判斷 n1->next != head 則會導致當節點數量大於等於 6 時最後兩個節點會沒辦法交換，因為這時候 n1->next 即為 head 還未交換就離開迴圈了

`q_reverseK`

想法是基於之前反轉串列的概念，使用將節點移動到環狀鏈結串列的 head 來進行反轉，不同之處在於要根據給定的 k值來更新反轉的起始位置

新的起始位置是 head 的下一個節點位置，但在經過翻轉之後會改變節點的位置，因此需要在最開始時先紀錄下來，這樣的話在經過反轉過後就不會獲得錯誤的位置

`q_ascend` and `q_descend`

commit b9536b1

   for (safe = move->prev; move != head; move = safe, safe = move->prev) {
       element_t *cur_ele = list_entry(cur, element_t, list);
       element_t *move_ele = list_entry(move, element_t, list);
       if (strcmp(cur_ele->value, move_ele->value) > 0) {
           list_del(move);
           q_release_element(move_ele);
       } else {
           cur = move;
           count += 1;
       }
   }

對於 q_descend，使用原本的巨集 list_for_each 是往 next
的方向移動，而在這個問題上藉由往反方向移動的方式可以減少問題的困難度

通過這樣的方式讓問題簡化，只需要在遇到比當前節點更小的節點時將其刪除，而在遇到比當前節點更大的節點時再更新當前節點這樣，重複這個步驟，每次進行當前節點更新時，同時計算剩餘節點數量

相反的，對於q_ascend 遇到比當前節點大的節點時，將其刪除遇到比當前節點小時，更新位置，並計算剩餘節點數量

減少非必要的項目縮排 (即 * )，使用清晰、明確，且流暢的漢語書寫。

`q_sort`

commit f4aad84

減少非必要的項目縮排 (即 * )，使用清晰、明確，且流暢的漢語書寫。

選擇使用 Merge_sort 而不是 Quick sort 的原因在特定的條件下如果選擇 pivot 不當 (選到集合裡面的最大最小值)，可能會導致整個排序的時間複雜度變成 O(N²)，所以選擇使用 Merge sort

參考了 list_sort 的方式，先將環狀鏈結串列的環狀狀態解除變成單向的，再將 head->next 作為參數傳遞給 mergeSort 來進行排序

struct list_head *slow = head, *fast = head->next, *right;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

減少非必要的項目縮排 (即 * )，使用清晰、明確，且流暢的漢語書寫。

在這裡一開始先判斷 head 跟 head->next 的原因是因為已經將整個環狀鏈結串列變成單向的，在進行切割切時，最後會剩下單一節點，通過判斷節點是否還有相鄰連接，可以確認是否完成

使用快慢指標來切割整個鏈結串列時，在初始指標設定時將 fast 設定在 head->next －藉由這樣的方式 slow 指標才可以取得原先會到達位置的前一個節點，從而正確的去做切割

你如何確保目前的測試已涵蓋排序演算法的最差狀況？

`merge`

commit f4aad84

不符合作業規範，請用 git rebase -i 重新撰寫 git commit message，務必詳閱作業說明提及的規範。

排序合併的方式是使用一個暫時節點，並將較小的節點往後接上，最後判斷是否有剩餘的節點，若有就將剩下的串列內容接續到之前排序好的鏈結串列上

int cmp(const char *a, const char *b, bool descend)
{
    if (descend)
        return strcmp(b, a);
    else
        return strcmp(a, b);
}

減少非必要的項目縮排 (即 * )，使用清晰、明確，且流暢的漢語書寫。

－題目要求要能夠依據 descend 參數來判斷排序的方式，為了實現這樣的效果，可以利用 cmp 通過傳遞字串順序的不同來達成這樣的效果，使得程式碼看起來更加簡潔

for (pre = head, node = head->next; node->next != NULL;
         pre = node, node = node->next) {
        node->prev = pre;
    }
    node->next = head;
    head->prev = node;

回到 q_sort 時，由於之前有將鏈結串列的環狀結構截斷，因此在排序完成後，需要重新將鏈結串列恢復成正確的結構，使用這段 for 迴圈的方式將 prev 指標接上，最後更新 head 的指標

Todo 使用你所不知道的c語言 linked list 篇的技巧使 merge 更加簡潔

`q_merge`

commit 9bca09b

不符合作業規範，請用 git rebase -i 重新撰寫 git commit message，務必詳閱作業說明提及的規範。

while (move != head) {
    queue_contex_t *tmp = list_entry(move, queue_contex_t, chain);
    size += tmp->size;
    tmp->q->prev->next = NULL;
    mrg_q = merge(mrg_q, tmp->q->next, descend);
    move = move->next;
+   INIT_LIST_HEAD(tmp->q);
}

在merge 這個問題中，因為使用的資料結構稍微有點不同，但是概念還是一樣的所以需要做一些許變化，在前面的問題中，都是使用 head 連接 element_t 的節點，在這邊 head 則是連接 queue_contex_t ，在 queue_contex_t 的結構中使用 q 指標來指向佇列的 head 節點

對於這個問題的想法是，使用一個暫時的節點，遍歷 head 所連接的每個佇列待補經由前面 q_sort 所使用到的 merge 函式來進行合併，將 head->next 作為開頭的佇列與一開始所宣告的暫時節點合併最後形成一個排序好的佇列

再一開始時，要藉由斷開串列的技巧讓串列變成單向，所以在最後要合併回去，在這裡有一個需要特別注意的地方，就是將各個佇列合併時，必須對原先指向合併佇列的節點進行初始化INIT_LIST_HEAD，否則會發生Attempted to free unallocated block的錯誤

使用 valgrind 偵測記憶體問題

使用下方命令，利用 valgrind 找出記憶體洩漏問題

$ valgrind -q --leak-check=full ./qtest

對 qtest 程式碼進行測試，查看是否存在記憶體的問題

以 q_merge 為例，因為沒有正確將使用過的串列節點進行初始化，使其在 qtest 中正確釋放，因此發生記憶體錯誤問題

==7908== Invalid read of size 8
==7908==    at 0x10FA46: q_free (queue.c:29)
==7908==    by 0x10BF89: do_merge (qtest.c:906)
==7908==    by 0x10E2E0: interpret_cmda (console.c:181)
==7908==    by 0x10E895: interpret_cmd (console.c:201)
==7908==    by 0x10F4FF: run_console (console.c:691)
==7908==    by 0x10D6D2: main (qtest.c:1330)
==7908==  Address 0x4b8d120 is 48 bytes inside a block of size 64 free'd
==7908==    at 0x484B27F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==7908==    by 0x10F7AE: test_free (harness.c:204)
==7908==    by 0x10FA42: q_free (queue.c:31)
==7908==    by 0x10BF89: do_merge (qtest.c:906)
==7908==    by 0x10E2E0: interpret_cmda (console.c:181)
==7908==    by 0x10E895: interpret_cmd (console.c:201)
==7908==    by 0x10F4FF: run_console (console.c:691)
==7908==    by 0x10D6D2: main (qtest.c:1330)
==7908==  Block was alloc'd at
==7908==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)

可以藉由 valgrind 得知發現錯誤的地方，在去查看可能出現問題的函式在哪邊，藉此判斷出原因

以這邊的錯誤訊息來查看就可以知道問題發生在使用 merge 時，藉由這樣的方式到 qtest 中查看可能的問題所在再去排除

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


    KB
16.75^                                                                 ::     
     |                                                    ::@ ::  ::#  :      
     |                                                    : @ :   : #  :      
     |                                                    : @ :   : #  :      
     |                                                    : @ :   : #  :      
     |                                                    : @ :   : #  : :    
     |                                                    : @:: @:: #::: @:   
     |                                                    : @:: @:: #::: @:   
     |                                                   :: @:: @:: #::: @@   
     |                                                   :: @:: @:: #::: @@  :
     |                                                   :: @:: @:: #::: @@  :
     |                                                   :: @:: @:: #::: @@  :
     |                                                  ::: @:: @:: #::: @@  :
     |                                                  ::: @:: @:: #::: @@:::
     |                                                  ::: @:: @:: #::: @@: :
     |                                                  ::: @:: @:: #::: @@: :
     |                                                  ::: @:: @:: #::: @@: :
     |                                                  ::: @:: @:: #::: @@: :
     |                                                 :::: @:: @:: #::: @@: :
     |                                                ::::: @:: @:: #::: @@: :
   0 +----------------------------------------------------------------------->ki
     0                                                                   381.8

Number of snapshots: 57
 Detailed snapshots: [22, 29, 37 (peak), 47, 50]

可搭配 massif 工具，使用命令

$ valgrind --tool=massif ./qtest

獲得 massif.out.<number> 搭配下方命令獲得 heap 的時間變化量

$ ms_print massif.out.<number>

圖片意思為 heap 隨著測試時間的分配量變化

並使用視覺化工具 massif-visualizer 來進行記憶體查看

$ massif-visualizer massif.out.<number>

整合網頁伺服器

select()

讓當前程式可以監控多個 file descriptors 的狀態變化，直到一個或多個的 file descriptors 變成 ready 的狀態

fd_set

file descriptior 的集合

File descriptor sets

FD_ZERO(): 用來清空集合
FD_SET(): 將 file descriptior 加入集合
FD_CLR(): 將 file descriptior 從集合中移除
FD_ISSET()測試 file descriptior 是否在集合中

在 q_test 中提供新命令 `shuffle`

藉由 Knuth shuffle 演算法實作 shuffle 功能

這邊的想法是將 tmp 的節點由鏈結串列的最前端出發，藉由隨機值 rand() % (len - i) 選擇一個前進的步數來移動 tmp節點，將步數的範圍限制在 0 到 len - i - 1 之間

在進行節點交換的部份是先將要進行交換的兩個節點 n1 以 n2 分別先紀錄 n1->next 以及 n2->prev 作為連結的部份，這樣就可以不用考慮選到的兩個節點為相鄰節點的問題，而在每次交換完要記得將 move 的節點改為 tmp 不然可能會導致 move 的指標設定到 tmp 的位置，這樣才會符合原本的設定，使得下一輪開始的順序不會發生錯誤

完成 shuffle 的實作之後，就可以將 shuffle 的功能整合到 qtest 裡面，首先對照 qtest 內部的程式碼可以發現對每一個在 queue.c 中的功能在 qtest 中都有一個對應的 do_<function> 的函式，因此也對照實作do_shuffle，並且在 console_init 中新增命令 ADD_COMMAND(shuffle, ...) 這樣就可以在 qtest 中使用 shuffle 的功能

最後因為 shuffle 的標頭檔問題，由於不能修改 queue.h 的內容，所以要將 shuffle.h 另外撰寫，讓 qtest 使用

實驗

Expectation: 41666 
observation: {'1234': 41675, '1243': 41995, '1324': 41572, '1342': 41870, '1423': 41560, '1432': 41585, '2134': 41718, '2143': 41686, '2314': 41310, '2341': 41333, '2413': 41562, '2431': 41705, '3124': 41486, '3142': 41684, '3214': 41619, '3241': 41648, '3412': 41781, '3421': 41702, '4123': 41980, '4132': 41759, '4213': 41958, '4231': 41493, '4312': 41777, '4321': 41542}
chi square sum:  17.509480151682425

根據老師提供腳本裡面的設定可以看到，會進行 1000000 次 shuffle ，總共會有 24 種組合，在進行亂數之後每個組合出現的數字都非常接近平均的 41666 次

最後在根據提供的繪圖方式來繪製可以看到最後的結果

閱讀〈Dude is my code constant time〉論文

方法

對兩個不同類別的資料進行執行時間的測試並且觀察兩個時間分佈的不同

step1 測量執行時間

使用 fix-vs-random 的偵測方式來偵測兩種不同的測試資料，將第一類分成固定的值，而第二類為隨機選擇

現代 cpu 具備時脈週期的計算功能，可以準確的計算時間

為了最小話環境變化的影響每個測量都會對應到一個隨機類別

step2 後處理

每個測試資料在統計分析之前會進行後處理

crop 將執行時間超過一定閥值的測量截斷或丟棄

根據所應用統計測試，進行高階的預處理

step3 應用統計資料

利用統計資料來反駁虛無假說

使用 welch's t-test 來檢驗時間分佈的均值是否相等，welchl's t-test 失敗時代表存在一定的洩漏問題

可使用非參數測試，因非參數測試會對底層分佈有較少的假設

結果

作者使用 C 語言實作 dudect

對資料進行預處理，為了測試受限的資料分佈，將大於 p 百分位的資料丟棄，且也對沒進行預處理的資料進行測試

使用 welch's t-test 搭配 welford's 變異數計算來提升穩定

使用基於 memcmp 的 16-byte 記憶體比較函數測試，並設計兩種不同的洩漏檢測方式，在發現兩個類別的分佈明顯不同時即存在時間洩漏問題

查看 dudect 程式碼

在查看 dudect 的程式碼時可以發現在實作 p 值的這個部份是缺少的，
即在 crop 後處理部份的藉由閥值丟棄超過時間的測量部份因此我們需要去對照 dudect 中缺失的部份

可以看到 dudect 中的結構 dudect_ctx_t 這部份 fixture 內部的實作直接將結構的變數宣告在 doit 中使用但是少了 percentiles ，所以在這邊補上，並記得在最後使用完進行釋放

static bool doit(int mode)
{
    ...
+   int64_t *percentiles = calloc(DUDECT_NUMBER_PERCENTILES, sizeof(int64_t));
    ...
+   free(percentiles)
}

新增完之後還要記得將 first_time 加入到 do_it 中並且加入 if (first_time) 來判斷使用 prepare_percentiles

static int cmp(const int64_t *a, const int64_t *b){..}
static int64_t percentile(int64_t *a_sorted, double which, size_t size){..}
static void prepare_percentiles(int64_t *exec_times, int64_t *percentiles){..}

而缺失的部份還包含 cmp, percentile 以及 prepare_percentiles 將其補上

for (size_t crop_index = 0; crop_index < DUDECT_NUMBER_PERCENTILES;
         crop_index++) {
        if (difference < percentiles[crop_index]) {
            t_push(t, difference, classes[i]);
        }
    }

讓程式可以正常運作，在 doit 中加上對於 first_time 的判斷，來準備 percentiles 並且最後在 update_statics 的地方新增迴圈判斷 percentiles 的值來讓 lab0-c 可以在多項式時間內完成滿足要求的最後條件

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

參考 Risheng1128 和 chiangkd

list_sort 一開始會先先判斷是否是單一節點，並且將鏈結串列的環狀結構斷開，變成以單向的方式來進行，而這邊使用了 pending 指標來指向一段子串列

在 while 中以判斷 count 的 bit 這樣的方式來確認目前子串列的數量，當 count + 1 的值是2的冪時就不進行合併的在 for 中將 ...111 的 1 向右移清除成 0 來讓 if 判斷不會成立，而當 count 為其他值時則會進行合併

在進行 if (likely(bit)) 判斷完後則會進行指標的移動將 pending 跟 list 都向前一個節點，再離開 while 之後將剩下的 list 進行合併，並在最後用 final_merge 將鏈結串列的環狀結構重新建立

在 merge_final 中會看到一段 cmp(priv, b, b) 的比較而為什麼這邊要進行自己跟自己的比較是因為在原始程式碼中的 cmp 中有一個 cond_resched() 的函式，當發生對於以排序好的串列內容要進行，就可以藉由呼叫 cond_resched() 讓 kerne 將 cpu 將給其他優先權更高的來使用

`likely` 巨集

巨集中使用到 !!(x) 來確保得到的值一定為 1 或 0 透過這樣的方式就可以讓編譯器在編譯時對組合語言分支指令進行最佳化

`attribute((..))`

在函式宣告前增加特性，增強編譯器的錯誤檢查功能包含可填寫參數包含
packed aligned section unused nonnull…

在 list_sort 之中會看到 __attribute__((nonnull(1,2))) 功能為用來判斷說第幾個參數不能為空這邊填入 1, 2 也就是第 1 個以及第 2 個不能為空

將 `list_sort.c` 引入到專案中

原先打算建立新的 list_sort.c 以及 list_sort.h 到 lab0-c 中，在將 list_sort.c 以及 list_sort.h 的內容加入到新建立的 .c 以及 .h 檔之中

但是在將 list_sort 上傳到 github 階段發現在 commit 階段會產生錯誤訊息，而發生這樣問題的地方是在 cmp 函式中使用 strcmp 對 list_entry(a, element_t, list)->value 以及 list_entry(b, element_t, list)->value 進行比較時，在經過調查後發現是關於 cppcheck-suppress nullPointer 的問題，最後決定將 list_sort 放到 queue.c 中解決

list_sort.c:11:24: error: Null pointer dereference: (struct element_t*)0 [nullPointer]

在引入 list_sort 一開始，先建立 list_sort.h 將所要內容加入包含缺少的 likely 相關巨集加入到其中

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

也會發現 u8 這個資料型態沒辦法使用，而為什麼 linux kernel 的程式碼使用 u8這個資料型態可以參考 stackoverflow，要解決的這樣的問題可以 #include <stdint.h> 並使用 uint8_t 來取代，或是 typedef uint8_t u8 來解決這樣的問題

對於程式碼的部份，因為缺少 cmp 這個函式，而我在 queue.c 中原先就有宣告 cmp 所以我決定撰寫 ls_cmp 來取代，其內容為 strcmp(…) 的判斷，也因為在閱讀 list_sort 時發現 priv 這個指標只有 cmp 使用到，對於其他函式是沒有意義的，因此決定將其刪除

在新增完後再次編譯會發現 EXPORT_SYMBOL(list_sort) 出現問題，其功能為讓被 EXPORT_SYMBOL 定義的函式可以被 kernel 的其他 modlue 所使用

我在這邊選擇的方法為直接將其刪除，接下來就可以正常使用 list_sort了

- EXPORT_SYMBOL(list_sort);

比較所撰寫 `sort` 以及 linux 核心版本 `list_sort` 差異

明確標示 GitHub 帳號名稱。

在查閱參考筆記時發現，~~筆記同學~~ Risheng1128 同學是在使用 make check 時觀察到裡面的命令，並藉由這樣的方式來發現並去撰寫新的命令內容，讓我頗有啟發我原先都沒有想到可以藉由這樣的方式來了解內部檔案的使用

使用下方命令

$ ./qtest -f traces/<name>.cmd

來執行 lab0-c 中 traces 裡面所撰寫的測試檔，這邊是使用下方測試流程進行測試，並且更改 RAND 的值來比較兩個 sort之間的差異

new
ih RAND <times>
time
<sort>
time

時間比較

rand 100000

q_sort	time	list_sort	time
1	0.086	1	0.078
2	0.092	2	0.078
3	0.092	3	0.078
4	0.094	4	0.073
5	0.088	5	0.080

rand 600000

q_sort	time	list_sort	time
1	0.672	1	0.585
2	0.668	2	0.586
3	0.717	3	0.583
4	0.699	4	0.585
5	0.710	5	0.597

在時間效能上我使用的是 top down 版本的 merge sort　可以看到在時間上比起 list_sort 來的較慢，而且在對更多的字串進行排序時，top dwon 的這個版本在時間變化的幅度上也顯的較大

效能比較

利用 perf 指令來比較兩個排序演算法的 cache miss, cache-refernece, instrcution, cycles

$ sudo perf stat -r <times> -e cache-misses,cache-references,instructions,cycles,page-faults,branches ./qtest -f ./traces/<name>.cmd

可以在 <times> 中填入要重複執行的次數， <name>中填入所要執行的指令檔名稱

下方比較會連續執行 5 次並且計算平均值， RAND 設定為 600000

q_sort

Performance counter stats for './qtest -f ./traces/sort.cmd' (5 runs):

 7626,0285       cache-misses                     #   63.52% of all cache refs           ( +-  0.30% )
1,2005,0783      cache-references                                                        ( +-  0.41% )
29,4979,5909      instructions                     #    0.66  insn per cycle              ( +-  0.07% )
44,4143,2806      cycles                                                                  ( +-  0.56% )
    2,1170      page-faults                                                             ( +-  0.00% )
4,5792,7144      branches                                                                ( +-  0.07% )

    1.4424 +- 0.0106 seconds time elapsed  ( +-  0.74% )

list_sort

Performance counter stats for './qtest -f ./traces/sort.cmd' (5 runs):

 6467,3448      cache-misses                     #   65.98% of all cache refs           ( +-  0.25% )
 9802,1660      cache-references                                                        ( +-  0.05% )
27,7722,6241      instructions                     #    0.68  insn per cycle              ( +-  0.07% )
40,8011,8980      cycles                                                                  ( +-  0.23% )
    2,1170      page-faults                                                             ( +-  0.00% )
3,8986,9605      branches                                                                ( +-  0.08% )

   1.33843 +- 0.00338 seconds time elapsed  ( +-  0.25% )

在相同的數量下進行兩種排序後所產生的結果可以看到在自己所撰寫的 q_sort 在 cache misses 的次數上明顯比較多，而且可以看到有比較多次對於記憶體的參照，也對應到使用 top down 的　merge sort 會一直的進行 partition 導致記憶體內容不斷的更動造成了更多次的記憶體的參照

也因為記憶體內容會被不斷的更換，也會使得 cache 發生 thrashing 的機率變高，這樣就可以知道以 list_sort 這樣的方式來進行排序，除了~~記憶體更加友善~~ 可以減少記憶體的參照之外在指令數上以及所使用的 cycle 都更少，在 branch 的使用上也是比起 top dowm 的版本來的較少

用字該精準！

了解！已更改
shawn

整合 Timsort 並與上述排序演算法進行比較

將 quiz1 的 Timsort 整合進入 lab0-c 中，使用與上述加入 list_sort 相同步驟，將 Timsort 加入到 queue.c 中，加入之後會發現與有與 list_sort 相同且可以重複利用的部份，像是 merge_final 以及 merge_at 中使用到的 merge ，以及 cmp 的函式可以用與 list_sort 相同 ls_cmp 來進行字串的比較，同樣也將 priv 刪除

在這邊也發現到 build_prev_link 為最後將環狀鍊結串列結構重新建立的函式，在 timsort 中 if (stk_size <= 1) 這個判斷會使用到，原本想將 list_sort 的 merge_final 進行重建連結的部份用 build_prev_link 函式來重構，但是我覺得 list_sort　在 merge_final 重建的迴圈中藉由在判斷到排序好的陣列時自己與自己比較來把優先權交出去的這邊很有特色所以決定保留不去更動

if (unlikely(!++count)) 
    ls_cmp(b, b);

Timsort 相較於 mergesort　的優點

降低 cache miss
降低記憶體開銷
降低比較次數

隨機資料

先以隨機資料作為測試資料計算兩種排序的比較次數、時間再用 perf 觀察記憶體

比較次數

使用測驗 1 的 main 進行比較測試 RAND 設定為 1000，使其重複五次，在 RAND 設定為 10000 時也是相同結果

Creating sample
==== Testing timsort ====
  Comparisons:    9591
  List is sorted
==== Testing list_sort ====
  Comparisons:    8707
  List is sorted

Creating sample
==== Testing timsort ====
  Comparisons:    9640
  List is sorted
==== Testing list_sort ====
  Comparisons:    8686
  List is sorted

Creating sample
==== Testing timsort ====
  Comparisons:    9464
  List is sorted
==== Testing list_sort ====
  Comparisons:    8706
  List is sorted

Creating sample
==== Testing timsort ====
  Comparisons:    9286
  List is sorted
==== Testing list_sort ====
  Comparisons:    8709
  List is sorted

Creating sample
==== Testing timsort ====
  Comparisons:    9249
  List is sorted
==== Testing list_sort ====
  Comparisons:    8692
  List is sorted

Timsort	comparisons	list_sort	comparisons
1	9591	1	8707
2	9640	2	8686
3	9464	3	8706
4	9286	4	8709
5	9249	5	8692

可以明顯看到 Timsort 對隨機資料進行排序，整體比較次數大於 list_sort，此結果

時間

rand 100000

Timsort	time
1	0.075
2	0.088
3	0.070
4	0.076
5	0.079

rand 600000

Timsort	time
1	0.609
2	0.617
3	0.631
4	0.612
5	0.646

在時間方面可以看到在 100000 筆測試資料時的時間跟 list_sort 相比相當接近，但到了 600000 筆時就顯得稍差，但由於目前是使用隨機資料跟 timsort 假設的資料都是大致排序好前提不相符

效能比較

下方皆為 Timsort 的結果

  Performance counter stats for './qtest -f traces/sort.cmd' (5 runs):

         6306,4027      cache-misses                     #   64.69% of all cache refs           ( +-  0.99% )
         9748,4643      cache-references                                                        ( +-  0.76% )
      29,0396,2473      instructions                     #    0.69  insn per cycle              ( +-  0.10% )
      42,2630,9182      cycles                                                                  ( +-  0.34% )
            2,1172      page-faults                                                             ( +-  0.00% )
       4,2581,7808      branches                                                                ( +-  0.14% )

           1.38267 +- 0.00709 seconds time elapsed  ( +-  0.51% )

 Performance counter stats for './qtest -f traces/sort.cmd' (5 runs):

         6658,0858      cache-misses                     #   65.81% of all cache refs           ( +-  2.24% )
       1,0116,4395      cache-references                                                        ( +-  1.82% )
      29,0435,0597      instructions                     #    0.63  insn per cycle              ( +-  0.11% )
      46,0576,7540      cycles                                                                  ( +-  4.18% )
            2,1171      page-faults                                                             ( +-  0.00% )
       4,2627,6138      branches                                                                ( +-  0.20% )

            1.5017 +- 0.0593 seconds time elapsed  ( +-  3.95% )

先以隨機資料與先前的 q_sort 以及 list_sort 作比較，我在進行第一次測試時得到了在 cache-misses 以及 references 上 Timsort 得到了比較好的結果，在指令數以及 cycle 上需要花費較多的成本，而 brancches 則較少因此讓我好奇如果多作幾次是否會得到一樣的結果，但經過多次之後發現以隨機資料而言， references 的數量以及 cache misses 的差異可以到達 3000000 多筆的差距，再回去看測驗 1 時可以看到最下面對 Timsort 的說明有提到 Timsort 在合併 run 時會藉由 Galloping mode 來進行處理

而此動作對於大致排序好的序列會有較好的合併結果，但對於隨機資料而言若使用此機制要逐步的合併可能會導致效果不好，所以目前 Timsort 版本尚未完整，也缺少了對於 Galloping mode 的啟動機制也就是何時要進行 Galloping mode，所以可以看到目前的結果仍有較大幅度的變動

部份排序好資料

使用 1000 筆資料並且用 rand 決定隨機的區段也就是每次介於 x 到 y 之間並且讓排序好的區段由隨機的方式加入到鏈結串列的頭跟尾來獲得部份排序好的資料，使用此資料進行 Timsort 以及 list_sort 進行比較次數的比較

Creating sample
==== Testing timsort ====
  Comparisons:    1965
  List is sorted
==== Testing list_sort ====
  Comparisons:    5524
  List is sorted

Creating sample
==== Testing timsort ====
  Comparisons:    1652
  List is sorted
==== Testing list_sort ====
  Comparisons:    5354
  List is sorted

Creating sample
==== Testing timsort ====
  Comparisons:    1915
  List is sorted
==== Testing list_sort ====
  Comparisons:    5536
  List is sorted

Creating sample
==== Testing timsort ====
  Comparisons:    1931
  List is sorted
==== Testing list_sort ====
  Comparisons:    5503
  List is sorted

Creating sample
==== Testing timsort ====
  Comparisons:    1957
  List is sorted
==== Testing list_sort ====
  Comparisons:    5516
  List is sorted

interval = rand() % (max_part - min_part + 1) + min_part;

可以看到對於部份排序好的資料而言使用 Timsort 進行排序，與隨機資料相比下來使用比較少的比較次數即可完成排序，而對於部份排序好的資料而言，list_sort 就得花上較多的比較次數來完成排序，也由此可見在符合 Timsort 作者所假設的大部分的資料都是部分排序好的假設，Timosrt 可以發揮比較好的優勢

Timsort	comparisons	list_sort	comparisons
1	1965	1	5524
2	1652	2	5354
3	1915	3	5536
4	1931	4	5503
5	1957	5	5516

整合 Tic-Tac-Toe

negamax

為 minimax 經過數學方式改良，將判斷 min max 的部份以負號的方式來做取代，每次只要藉由負號就不用在判斷是在 min 層還是 max 層

mcts

主要分為三個步驟執行包含 1.select 2. expand rollout 3.backprobagate ，在 select 時會藉由 UCB 公式計算每個節點的值然後選取較大的節點，expand 跟 rollout 會藉由判斷當前的節點狀態，若是新的節點則會執行 rollout 即會從當前的狀態進行模擬模擬之後的行為直到計算出結果，而 expand 則是會產生新的 child 節點，最後一步 backprobagate 則是會將當前節點的結果向上 (當前節點的 parent 往上直到 root ) 傳遞

hlist

在 hlist 中使用了READ_ONCE WROTE_ONCE 這兩個巨集，而這兩個巨集在核心中的 list.h 程式碼中同樣也使用很多次可以對照到 lab0-c 中的 list.h 可以發現其實功能為進行讀取、寫入這兩件事，作用為防止編譯器對程式碼進行最佳化

因為在某些情況編譯器對程式碼的順序進行最佳化時可能就會打亂對共享變數存取的順序導致最後得到錯誤的值，

#define READ_ONCE(var) (*((volatile typeof(var) *)(&(var))))
#define WRITE_ONCE(var, val) \
	(*((volatile typeof(val) *)(&(var))) = (val))

而在使用 volatile 時即告訴編譯器每次讀取都是從記憶體位置讀取，不從暫存器讀取，來防止因優化而得到跟預料中不同的值

在進行 hlist 整合時配合 list.h 的風格來進行實現，將 READ_ONCE 以及 WRITE_ONCE 改為一般的讀取以及寫入， hlist_del 將 next 以及 pprev 指標指向無效位址的部份也指向 0x00100100 、 0x00200200

將 ttt 整合至 lab0-c

commit 909cd79

依據作業要求將 ttt 中的內容加入到 qtest 中成為新的功能，首先可以看到 main 中將 ttt 依造 define 的內容可以分為使用 reinforce learning、monte carlo tree search 以及 negamax 的方式來執行，從 main 中抽出 mcts 的內容成為 mcts_ttt

在將執行 mcts 時會用到檔案加入到 lab0-c 中在加入之後要到 makefile 修改 OBJS 並加入 agents 的資料夾內容

在進行編譯時會出現這些問題，要一一處理，這次一開始也同樣碰到了要處理 cppcheck 的問題，而根據上次的經驗會發現 queue 中有在 cppcheck 設置 supress 的內容，因此在這次作業中就依照 queue 的設置方式到　pre-commit.hook 中將有發生問題的檔案一一作設置

agents/mcts.c:147:21: warning: Possible null pointer dereference: best_node [nullPointer]
    int best_move = best_node->move;
                    ^
agents/mcts.c:139:30: note: Assignment 'best_node=NULL', assigned value is 0
    struct node *best_node = NULL;
                             ^
agents/mcts.c:142:31: note: Assuming condition is false
        if (root->children[i] && root->children[i]->n_visits > most_visits) {
                              ^
agents/mcts.c:147:21: note: Null pointer dereference
    int best_move = best_node->move;
                    ^
agents/mcts.c:67:10: style: The scope of the variable 'win' can be reduced. [variableScope]
    char win;
         ^
game.c:74:28: style: Parameter 'table' can be declared with const [constParameter]
int *available_moves(char *table)
                           ^
mt19937-64.c:83:9: style: The scope of the variable 'i' can be reduced. [variableScope]
    int i;
        ^
mt19937-64.c:85:21: style: The scope of the variable 'mag01' can be reduced. [variableScope]
    static uint64_t mag01[2] = {0ULL, MATRIX_A};
                    ^
mt19937-64.c:85:21: style: Variable 'mag01' can be declared with const [constVariable]
    static uint64_t mag01[2] = {0ULL, MATRIX_A};
                    ^
zobrist.c:63:21: error: Null pointer dereference: (struct zobrist_entry_t*)0 [nullPointer]
            entry = hlist_entry(hash_table[i].first, zobrist_entry_t, ht_list);
                    ^

Fail to pass static analysis.

還有發現在 game.c 以及 mt19937-64.c 有要求要將特定的變數設定為 const，照著去設定即可解決

新增 ai vs ai 功能

commit c72fcce

在 ttt 中新增 ai vs ai 功能使用兩種不同的演算法包含一開始使用的 mcts 以及 negamax 並使用 ttt_mode 讓 option 可以變更切換使用玩家對上 ai 還是 ai 對上 ai

並新增時間顯示，在 ai 對上 ai 每回合顯示棋盤之前使其暫停 1 秒否則會一瞬間就把結果顯示出來

coroutine

commit 8972f0c

使用 coroutine 實作 ttt 加入 qtest 命令中，將任務分成三個部份包含進行勝利判定的任務在某方取得勝利後列印出步數並將結果清空，以及執行演算法的任務使用 mcts 以及 negamax 進行對役，在過程中會間隔一秒並列印出時間

研讀〈並行程式設計：排程器原理〉根據 coro 中的 coro.c 實現 coroutine 的運行，任務會在初次執行 setjmp 時回傳 0 並藉由 task_add 將任務加入到 list 中進行排程，並根據 jmp_buf 的值跳回所屬的 setjmp 位置並將 setjmp 的回傳值修改成非 0這邊設定為 1

void schedule(void)
{
    static int i = 0;

    setjmp(sched);

    while (ntasks-- > 0) {
        struct arg arg = args[i];
        tasks[i++](&arg);
        printf("Never reached\n");
    }
    task_switch();
}

coro.c 的運行方式為由 schedule 進入 task 再藉由 task 中的第一個 if 判斷將任務加入到 list 中並使用 longjmp(sched, 1) 跳回到 schedule 將不同的任務的先加入一份到 list 中進行初次的排程，之後藉由 task_switch 中的 longjmp(t->env, 1)的值回所屬任務，回到所屬任務後會從第一個 if 的 setjmp 位置開始執行，也因為是藉由 longjmp 跳回的關係，所以回傳值為 1 不執行 if 中的內容從 task = cur_task 往下執行

void algotask(void *arg)
{
    ...
    if (setjmp(task->env) == 0) {
        task_add(task);
        longjmp(sched, 1);
    }
    task = cur_task;
    for (;;) {  
        if (setjmp(task->env) == 0) {
            int move = task->ai_algo(table, task->turn);
            if (move != -1) {
                table[move] = task->turn;
                record_move(move);
            }
            task_add(task);
            task_switch();
        }
        task = cur_task;
    }
    longjmp(sched, 1);
}

當進入到 for(;;) 中再次執行 setjmp 初次呼叫回傳值為 0 進入 if 內開始執行任務並將任務再次加入到 list 中進行排程並藉由 task_switch 切換到下一個任務，藉由這樣的方式將任務分別加入到排程中使 ttt 的運行可以不斷持續下去

commit 59aefc8
為了讓任務之間的差異可以更加明確，讓判定結果的任務進行判定以及結果顯示，而演算法任務專心執行相對應的演算法

2024q1 Homework1 (lab0)

Reviewed by SimonLee0316

Reviewed by SHChang-Anderson

Reviewed by Shiang1212

開發環境

指定佇列的操作

q_size

q_free

q_insert_head and q_inset_tail

new_element

Todo: 可以更加簡潔

q_remove_head and q_remove_tail

q_delete_dup

q_swap

q_reverseK

q_ascend and q_descend

q_sort

merge

q_merge

使用 valgrind 偵測記憶體問題

整合網頁伺服器

select()

fd_set

File descriptor sets

在 q_test 中提供新命令 shuffle

實驗

閱讀〈Dude is my code constant time〉論文

方法

step1 測量執行時間

step2 後處理

step3 應用統計資料

結果

查看 dudect 程式碼

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

likely 巨集

__attribute__((..))

將 list_sort.c 引入到專案中

比較所撰寫 sort 以及 linux 核心版本 list_sort 差異

時間比較

rand 100000

rand 600000

效能比較

q_sort

list_sort

整合 Timsort 並與上述排序演算法進行比較

Timsort 相較於 mergesort 的優點

隨機資料

比較次數

時間

rand 100000

rand 600000

效能比較

部份排序好資料

整合 Tic-Tac-Toe

negamax

mcts

hlist

將 ttt 整合至 lab0-c

新增 ai vs ai 功能

coroutine

Read more

Demystifying The Linux Cpu Scheduler

2024q1 Homework5 (assessment)

2024q1 Homework6 (integration)

2024q1 Homework4 (quiz3+4)

Reviewed by `SimonLee0316`

Reviewed by `SHChang-Anderson`

Reviewed by `Shiang1212`

`q_size`

`q_free`

`q_insert_head` and `q_inset_tail`

`new_element`

`q_remove_head` and `q_remove_tail`

`q_delete_dup`

`q_swap`

`q_reverseK`

`q_ascend` and `q_descend`

`q_sort`

`merge`

`q_merge`

在 q_test 中提供新命令 `shuffle`

`likely` 巨集

`attribute((..))`

將 `list_sort.c` 引入到專案中

比較所撰寫 `sort` 以及 linux 核心版本 `list_sort` 差異

Timsort 相較於 mergesort　的優點