2024q1 Homework1 (lab0)

contributed by < max890808 >

Reviewed by `mesohandsome`

敘述函式新增或修改什麼部分，可以貼出對應的關鍵程式碼，可善用 diff。

- strcpy()
+ strncpy()

有些 commit 沒有連結到正確的 github，例如 q_insert_head 實作中的這兩個

commit 8354a3d, commit 39a124d

研讀 lib_sort.c 並引入到 lab0-c 章節中，只有看到比較，沒有研讀？

開發環境

$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.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:                            2600.000
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

指定的佇列實作

`q_new`

commit ac06e12

Chris Beams 在 How to Write a Git Commit Message 一文 (繁體中文翻譯: 如何寫一個 Git Commit Message) 提出，好的 Git commit message 應符合七條規則:

用一行空白行分隔標題與內容
限制標題最多只有 50 字元
標題開頭要大寫
標題不以句點結尾
以祈使句撰寫標題
內文每行最多 72 字
用內文解釋 what 以及 why vs. how

你沒有依循上述規範，請詳讀作業說明，以 git rebase -i 改正。

使用 malloc() 配置 list_head 記憶體，並透過 INIT_LIST_HEAD 初始化 head 。

`q_free`

commit 92f4f21

Chris Beams 在 How to Write a Git Commit Message 一文 (繁體中文翻譯: 如何寫一個 Git Commit Message) 提出，好的 Git commit message 應符合七條規則:

用一行空白行分隔標題與內容
限制標題最多只有 50 字元
標題開頭要大寫
標題不以句點結尾
以祈使句撰寫標題
內文每行最多 72 字
用內文解釋 what 以及 why vs. how

你沒有依循上述規範，請詳讀作業說明，以 git rebase -i 改正。

使用 list_for_each_entry_safe 走訪每一個結構體，並透過 q_release_element 釋放結構體所在的記憶體位置。

`q_insert_head` `q_insert_tail`

commit 8354a3d, commit 39a124d

Chris Beams 在 How to Write a Git Commit Message 一文 (繁體中文翻譯: 如何寫一個 Git Commit Message) 提出，好的 Git commit message 應符合七條規則:

用一行空白行分隔標題與內容
限制標題最多只有 50 字元
標題開頭要大寫
標題不以句點結尾
以祈使句撰寫標題
內文每行最多 72 字
用內文解釋 what 以及 why vs. how

你沒有依循上述規範，請詳讀作業說明，以 git rebase -i 改正。

一開始在撰寫程式碼時使用 strcpy 處理複製字串的部份，在 git commit 時跳出 Dangerous function 通知，經查閱2024 年 Linux 核心設計/實作課程作業 —— lab0和 Common vulnerabilities guide for C programmers 後，將 strcpy 改用 strncpy 實作，但還是需要注意字串結尾字元 '\0' 的問題。

The strcpy built-in function does not check buffer lengths and may very well overwrite memory zone contiguous to the intended destination. In fact, the whole family of functions is similarly vulnerable: strcpy, strcat and strcmp.

strncpy(str1,str2, BUFFER_SIZE); /* limit number of characters to be copied */
// We need to set the limit to BUFFER_SIZE, so that all characters in the buffer 
// are set to '\0'. If the source buffer is longer than BUFFER_SIZE, all the 
// '\0' characters will be overwritten and the copy will be truncated.

`q_remove_head` `q_remove_tail`

commit 64fe21b, commit d0df781

Chris Beams 在 How to Write a Git Commit Message 一文 (繁體中文翻譯: 如何寫一個 Git Commit Message) 提出，好的 Git commit message 應符合七條規則:

用一行空白行分隔標題與內容
限制標題最多只有 50 字元
標題開頭要大寫
標題不以句點結尾
以祈使句撰寫標題
內文每行最多 72 字
用內文解釋 what 以及 why vs. how

你沒有依循上述規範，請詳讀作業說明，以 git rebase -i 改正。

使用 list_first_entry 或 list_last_entry 找到第一個結構體或最後一個結構體，之後使用 list_del 移除目標結構體。

`q_delete_mid`

commit 6cb8616 commit a9964f8

使用快慢指標的方法找出中間的結構體，之後使用 q_release_element 將結構體刪除。

使用 List API 中的 list_del 精簡程式碼。

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

-   struct list_head **indir = &head->next, *prev = NULL;
+   struct list_head **indir = &head->next;
    for (struct list_head *fast = head->next;
         fast != head && fast->next != head; fast = fast->next->next) {
-       prev = *indir;
        indir = &(*indir)->next;
    }
-   struct list_head *next = (*indir)->next;
+
    element_t *mid_element = list_entry(*indir, element_t, list);
+   list_del(*indir);
    q_release_element(mid_element);
-   prev->next = next;
-   next->prev = prev;
    return true;
}

TODO: 使用 List API，撰寫出更精簡的程式碼。

`q_delete_dup`

commit 7477ca9

使用兩層迴圈實作，程式碼不精簡，應使用一個變數紀錄目前是否為最後一個相同值的結構體，並搭配 List API 撰寫更精簡的程式碼，之後還需要作修改。

`q_swap`

commit d125b96

運用指標的指標和 list_move 實作

`q_reverse`

commit 05c88a6

逐一走訪每個節點，將節點的 prev 和 next 交換。

`q_reverseK`

commit 9bc9849

使用 list_cut_position 將要反轉的鏈結串列移動到新的空佇列上，接著使用 q_reverse 將鏈結串列作反轉，最後使用 list_splice_init 將反轉完的鏈結串列移動回原本的佇列。

`q_sort`

commit 16cf13f

使用 merge sort 實作，採用遞迴呼叫，搭配快慢指標將鏈結串列左右對半切分，直到分割成單一節點再使用 merge 合併成排序好的鏈結串列。

`q_ascend` `q_descend`

commit 2e0d815

使用list_for_each_safe 走訪每個節點並判斷在此節點前是否存在比此節點較大或較小的節點，若存在則使用 list_del 和 q_release_element 刪除節點。

`q_merge`

commit ab45163

先將所有佇列合併到第一個佇列，再使用 q_sort 排序。

目前在 github 上分數為95分，下一步將閱讀 Dude, is my code constant time?

論文 Dude, is my code constant time?

這篇論文提出了一種可以檢測程式執行時間是否為常數時間的工具 dudect，此技術是基於 leakage detection techniques，不需要硬體模型，並且可以使用在 black-box testing。

接著作者說明如何實作 TIMING LEAKAGE DETECTION
Step 1: Measure execution time
使用兩種資料，分別為 fix-vs-random， fixed value 是為了要觸發 corner-case。

Step 2: Apply post-processing
對所收集的資料進行後處理，有2種方式

Cropping: Timing distributions 會往執行時間較長的方向偏移，可能是因為測量工具，或是主程式被作業系統或其它不相關的程式所中斷造成的，所以需要裁切過大的數值。
Higher-order preprocessing: 不懂。

Step 3: Apply statistical test
反駁 null hypothesis “the two timing distributions are equal”

t-test (Welch’s t-test)
Non-parametric tests

實作改進 lab0-c

commit 3010009

在比較 dudect 原始程式碼和 lab0-c 後，發現 lab0-c 缺少 percentile 的部份，因此我在lab0-c中加入 cmp 、 percentile 和 prepare_percentiles 函式計算 NUMBER_PERCENTILES(這裡為100) 個閾值(thresholds)，接著透過 update_statistics 過濾執行時間超過閾值的資料，符合條件的資料會放入對應該閾值的 t[crop_index]，max_test 函式會從 t[crop_index] 計算最大的 t 值回傳。report 函式比較 t 值和 t_threshold_bananas t_threshold_moderate 判斷程式執行是否為常數時間。

在 dudect 的 update_statistics 函式中，有捨棄前十筆資料，在一開始改進 lab0-c 時我也只有將 update_statistics 函式中的 i 改成10，但在參考 nosba0957 同學的實作後發現這樣改是錯的，lab0-c 原先就有在 measure 函式中加入 DROP_SIZE，但這樣在 differentiate 函式計算執行時間時會導致開頭和結尾的地方都是 0。因此應該要在 measure 時紀錄全部的時間，在update_statistics 再將頭尾值刪除。執行上述改進後 make test 就能得到滿分了。

使用 Valgrind 排除記憶體錯誤

輸入 make valgrind 檢查是否發生記憶體錯誤

測試結果

+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---     trace-01-ops    5/5
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
---     trace-02-ops    6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, remove_head, reverse and merge
---     trace-03-ops    6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, swap, and sort
---     trace-04-ops    6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
---     trace-05-ops    6/6
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK
---     trace-06-ops    6/6
+++ TESTING trace trace-07-string:
# Test of truncated strings
---     trace-07-string 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---     trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---     trace-09-robust 6/6
+++ TESTING trace trace-10-robust:
# Test operations on NULL queue
---     trace-10-robust 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---     trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
---     trace-12-malloc 6/6
+++ TESTING trace trace-13-malloc:
# Test of malloc failure on new
---     trace-13-malloc 6/6
+++ TESTING trace trace-14-perf:
# Test performance of insert_tail, reverse, and sort
---     trace-14-perf   6/6
+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
---     trace-15-perf   6/6
+++ TESTING trace trace-16-perf:
# Test performance of insert_tail
---     trace-16-perf   6/6
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---     TOTAL           100/100

由測試結果可以可以發現目前的實作 valgrind 沒有發出任何的警告

研讀 Linux 核心原始程式碼 lib/list_sort.c 並引入到 lab0-c 專案

引入 lib/list_sort.c 到 lab0-c

commit 37715dc

參考 Risheng1128 的作法，將 lib/list_sort.c 引入 lab0-c 專案

比較自己實作的 merge sort 和 Linux 核心程式碼

使用 Risheng1128 的方法，建立一個用來量測排序時間的測試檔 trace-time-measure.cmd

option fail 0
option malloc 0
new
ih RAND 100000
time
sort
time

資料總數	`q_sort` 第一次 (s)	`q_sort` 第二次 (s)	`q_sort` 第三次 (s)	`q_sort` 平均 (s)	`list_sort` 第一次 (s)	`list_sort` 第二次 (s)	`list_sort` 第三次 (s)	`list_sort` 平均 (s)
100000	0.093	0.090	0.086	0.090	0.093	0.082	0.089	0.088
200000	0.202	0.204	0.203	0.203	0.199	0.199	0.204	0.200
300000	0.333	0.358	0.360	0.350	0.322	0.325	0.322	0.323
400000	0.496	0.492	0.485	0.491	0.448	0.454	0.388	0.430
500000	0.642	0.628	0.631	0.634	0.563	0.578	0.583	0.575

從平均的結果可以看到 list_sort 的執行時間比 q_sort 短，但幅度不大。接著使用 perf 工具進一步分析效能
輸入命令 perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./qtest -f traces/trace-time-measure.cmd
→ 程式會執行 5 次，並且自動平均，其中每次測試的資料數都設定為 500000 ，以下為 q_sort 及 list_sort 執行的結果

list_sort

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

         4981,3140      cache-misses              #   62.649 % of all cache refs      ( +-  0.41% )
         7947,5959      cache-references                                              ( +-  0.14% )
      23,1425,8918      instructions              #    0.60  insn per cycle           ( +-  0.07% )
      38,2314,6420      cycles                                                        ( +-  0.33% )

           1.39582 +- 0.00995 seconds time elapsed  ( +-  0.71% )

q_sort

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

         5715,4304      cache-misses              #   58.633 % of all cache refs      ( +-  0.85% )
         9665,6148      cache-references                                              ( +-  0.37% )
      23,8540,9426      instructions              #    0.58  insn per cycle           ( +-  0.06% )
      41,2860,8108      cycles                                                        ( +-  0.23% )

            1.4561 +- 0.0103 seconds time elapsed  ( +-  0.71% )

	`q_sort`	`list_sort`
cycles	41,2860,8108	38,2314,6420
instructions	23,8540,9426	23,1425,8918
cache-references	9665,6148	7947,5959
cache-misses	5715,4304	4981,3140
insn per cycle	0.58	0.60

從 perf 的分析結果可以看到， list_sort 發生 cache miss 的次數比 q_sort 來的少，可以對應到 Linux 核心的鏈結串列排序裡提到的「用 bottom up 實作 merge sort 對 cache 較友善，可避免大量的 cache trashing」

2024q1 Homework1 (lab0)

Reviewed by mesohandsome

開發環境

指定的佇列實作

q_new

q_free

q_insert_head q_insert_tail

q_remove_head q_remove_tail

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_reverseK

q_sort

q_ascend q_descend

q_merge

論文 Dude, is my code constant time?

實作改進 lab0-c

使用 Valgrind 排除記憶體錯誤

研讀 Linux 核心原始程式碼 lib/list_sort.c 並引入到 lab0-c 專案

引入 lib/list_sort.c 到 lab0-c

比較自己實作的 merge sort 和 Linux 核心程式碼

確保 qtest 提供的 web 命令得以搭配上述佇列實作使用

Read more

2024q1 Homework6 (integration)

2024q1 Homework4 (quiz3+4)

2024q1 Homework5 (assessment)

2024q1 Homework2 (quiz1+2)

Reviewed by `mesohandsome`

`q_new`

`q_free`

`q_insert_head` `q_insert_tail`

`q_remove_head` `q_remove_tail`

`q_delete_mid`

`q_delete_dup`

`q_swap`

`q_reverse`

`q_reverseK`

`q_sort`

`q_ascend` `q_descend`

`q_merge`