HackMD
2025q1 Homework1 (lab0)
contributed by < BennyWang1007 >
開發環境
$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
$ lscpu
架構： x86_64
CPU 作業模式： 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 20
On-line CPU(s) list: 0-19
供應商識別號： GenuineIntel
Model name: 12th Gen Intel(R) Core(TM) i7-12700H
CPU 家族： 6
型號： 154
每核心執行緒數： 2
每通訊端核心數： 14
Socket(s): 1
製程： 3
CPU(s) scaling MHz: 23%
CPU max MHz: 4700.0000
CPU min MHz: 400.0000
BogoMIPS: 5376.00
Virtualization features:
虛擬： VT-x
Caches (sum of all):
L1d: 544 KiB (14 instances)
L1i: 704 KiB (14 instances)
L2: 11.5 MiB (8 instances)
L3: 24 MiB (1 instance)
NUMA:
NUMA 節點： 1
NUMA node0 CPU(s)： 0-19
針對佇列操作的程式碼實作
q_new
Commit 1414f73
此函式會創建一個全新的、初始為空的佇列，實作如下
- 使用
malloc申請一個list_head節點的空間，若申請失敗則返回NULL - 使節點的
prev和next皆指向自己，滿足雙向鏈結串列的定義
q_free
Commit 1414f73
此函式會移除並釋放佇列中的所有節點，實作過程如下
- 首先判斷 head 是否為
NULL，若空則返回 - 接著遍歷整個
queue，釋放將所有節點的value和節點本身
q_insert_head
Commit a9ee6cc
此函式會在佇列的頭部插入一個元素，實作過程如下：
- 若 head 為
NULL，則返回false。 - 使用
malloc申請element_t節點的空間，若申請失敗則返回false。 - 初始化
new_element節點。 - 使用
strdup()複製輸入字串s，若複製失敗，則釋放new_element並返回false。 - 使用
list_add將新節點加入 head。
q_insert_tail
Commit a9ee6cc
此函式會在佇列的尾部插入一個元素，實作過程如下：
- 若 head 為
NULL，則返回false。 - 使用
malloc申請element_t節點的空間，若申請失敗則返回false。 - 初始化
new_element節點。
使用 strdup 複製輸入字串 s，若strdup失敗則釋放new_element並返回false。 - 使用
list_add_tail將新節點加入 head。
q_remove_head
Commit edec651
此函式會從佇列的頭部移除一個元素，實作過程如下：
- 若 head 為
NULL或佇列為空，則返回NULL。 - 取得佇列的第一個元素 entry。
若sp和entry->value不為NULL，則將entry->value複製到sp，並確保字串以\0結尾。 - 使用
list_del_init從鏈結串列中移除該節點。 - 返回
entry，由呼叫者負責釋放記憶體。
q_remove_tail
Commit edec651
此函式會從佇列的尾部移除一個元素，實作過程如下：
- 若 head 為
NULL或佇列為空，則返回NULL。 - 取得佇列的最後一個元素
entry。
若sp和entry->value不為 NULL，則複製字串至 sp，確保字串結尾為'\0'。 - 使用
list_del_init從鏈結串列中移除該節點。 - 返回
entry，由呼叫者負責釋放記憶體。
q_size
Commit 6f82f18
此函式會回傳佇列中的元素數量，實作過程如下：
- 若 head 為
NULL，則返回 0。
使用變數count記錄節點數量，初始化為0。 - 使用
for迴圈遍歷佇列，每遇到一個節點就將count增加 1。 - 最後返回
count值。
q_delete_mid
Commit 3048563
此函式會刪除佇列的中間節點，實作過程如下：
- 若 head 為
NULL或佇列為空，則返回false。 - 使用兩個指標
slow和fast，slow每次移動一步，而fast每次移動兩步，以此找到佇列的中間節點。 - 當
fast到達佇列尾部時，slow 會指向中間節點。 - 使用
list_del移除slow指向的節點，並釋放其 value 及節點本身的記憶體。 - 返回
true以表示刪除成功。
q_delete_dup
Commit 9d5bb17
此函式會刪除所有具有重複字串的節點，實作過程如下：
- 若佇列為空，則直接返回
true。 - 使用
prev指向當前處理的節點，prev_node指向prev的list_head，node用於走訪佇列。 - 若當前節點與
prev的 value 相同，則標記is_dup = true，並刪除當前節點。 - 若當前節點與
prev不同，則檢查is_dup是否為true，若是則刪除prev_node，否則將prev更新為當前節點。 - 走訪完成後，若
is_dup為true，則刪除最後一個重複節點。 - 返回
true代表刪除成功。
q_swap
Commit 5f13d84
此函式會交換佇列中每兩個相鄰的節點，實作過程如下：
- 若佇列為空或只有一個節點，則不需進行交換，直接返回。
- 使用
node走訪佇列，每次處理兩個節點。 - 透過調整指標，將
node和node->next互換位置。 - 更新
node，跳過剛剛交換的節點，繼續處理下一對相鄰節點。
q_reverse
Commit 1b7b7ad
此函式會將佇列中的元素順序完全反轉，實作過程如下：
- 若 head 為
NULL，則直接返回。 - 使用
node遍歷佇列，並在每個節點上交換prev和next指標。 - 最後調整 head 的
next和prev，完成反轉。
Commit 25bcd80
此提交修正了原先實作雙向鏈結串列指標的錯誤，並將 for 迴圈改成 while 迴圈增加可讀性。
q_reverseK
Commit e8c1632
此函式會將佇列中的元素以 k 個節點為一組進行翻轉，實作過程如下：
- 若 head 為
NULL或對列為空，或k <= 1，則直接返回。 - 若佇列的節點數
count < k則無需翻轉。 - 設定整型變數
round為count / k，表示需要翻轉的區塊數。 - 使用
node作為翻轉起點，逐區塊進行處理：cur為當前區塊的第一個節點。- 使用
list_move(cur, node);將節點移動到當前區塊的起點。 - 逐步翻轉
k個節點後，將node移動到下一區塊的起點。
Commit 61ae3a9
此提交優化了 q_reverseK 的效率：
- 將
list_move改成直接的 pointer 交換，免去多餘的雙向串列操作 (list_del+list_add)。 - 將原本迭代
k次的for迴圈改為直接設node = node->next;，大幅降低尋找下一個 group 的起點的操作數（
void q_reverseK(struct list_head *head, int k)
{
...
for (int i = 0; i < round; i++) {
...
/* Reverse the nodes */
for (int j = 0; j < k; j++) {
next = cur->next;
- list_move(cur, node);
+ tmp = cur->next;
+ cur->next = cur->prev;
+ cur->prev = tmp;
cur = next;
}
/* Swap the pointers */
+ next->prev->prev = node;
+ node->next->next = next;
+ tmp = next->prev;
+ next->prev = node->next;
+ node->next = tmp;
/* Move to the next group */
- for (int j = 0; j < k; j++)
- node = node->next;
+ node = next->prev;
}
}
q_sort
Commit 38f7439
此函式會對佇列中的元素進行排序，並可選擇升冪或降冪排序，實作過程如下：
透過 merge_sort_ascend 使用 合併排序 演算法對佇列進行升冪排序。
若 descend 為 true，則呼叫 q_reverse 進行反轉，使佇列變為降冪排序。
merge_sort_ascend
Commit 38f7439
此函式使用合併排序將佇列 升冪排序：
- 若佇列為空或只有一個元素，則直接返回。
- 使用 快慢指標 找到佇列的 中間節點，將佇列拆分為左右兩半。
- 透過遞迴呼叫
merge_sort_ascend分別對left和right排序。 - 使用
merge合併left和right，將結果存入 head。
merge
Commit 38f7439
此函式負責合併兩個已排序的子串列 l 和 r，並將結果存入 head：
- 比較 l 和 r 首節點的 value，將較小的節點移至 head 的尾部。
- 當 l 或 r 中有節點未處理完時，直接將剩餘的節點拼接到 head。
此函式是參考去年作業< LIAO-JIAN-PENG > 的架構，在該實作之上我將該程式碼的分支簡化，提昇效率和品味。又因 list_splice_tail_init 內就會判斷是否為空，因此可以將 if 判斷式移除。
void merge(struct list_head *head, struct list_head *l, struct list_head *r)
{
/* Merge the two sorted lists left and right into head */
while (!list_empty(l) && !list_empty(r)) {
char *l_val = list_first_entry(l, element_t, list)->value;
char *r_val = list_first_entry(r, element_t, list)->value;
- if (strcmp(l_val , r_val) < 0) {
- list_move_tail(l->next, head);
- } else {
- list_move_tail(r->next, head);
- }
+ struct list_head *node = strcmp(l_val, r_val) <= 0 ? l->next : r->next;
+ list_move_tail(node, head);
}
- if (!list_empty(l))
- list_splice_tail_init(l, head);
- if (!list_empty(r))
- list_splice_tail_init(r, head);
/* Move the remaining elements to head */
+ list_splice_tail_init(l, head);
+ list_splice_tail_init(r, head);
}
q_ascend
Commit 2008bc4
此函式會 移除所有非遞增的節點，確保佇列中的值嚴格遞增，具體實作過程如下：
1 若佇列為空或僅有一個節點，則直接返回對應大小。
2. 從 倒數第二個節點開始 向前走訪佇列，並維護一個 min 變數，記錄目前遇到的最小值。
3. 若當前節點的值 小於 min，則更新 min，保留該節點；否則刪除該節點。
4. 最後返回佇列剩餘的節點數量。
此函式是參考去年作業< LIAO-JIAN-PENG > 的架構，但做了兩個效能上的優化：
- 避免兩次
q_reverse操作：- 原實作先反轉鏈結串列，然後使用
list_for_each_safe走訪刪除不符合條件的節點，最後再反轉回來，這樣多做了兩次O(n)的反轉操作。 - 優化後直接從尾端開始走訪，省去了
q_reverse的額外開銷。
- 原實作先反轉鏈結串列，然後使用
- 刪除多餘的
NULL判斷：- 原實作在走訪過程中皆需判斷
min是否為NULL。 - 優化後我直接將
min初始化為最後一個節點的值(head->prev)，避免了多餘的NULL判斷，減少不必要的條件分支，並從倒數第二個節點開始走訪。
- 原實作在走訪過程中皆需判斷
int q_ascend(struct list_head *head)
{
- q_reverse(head);
...
- char *min = NULL;
+ const char *min = list_entry(node, element_t, list)->value;
...
- if (!min || strcmp(e->value, min) < 0)
+ if (strcmp(e->value, min) < 0)
...
- q_reverse(head);
return q_size(head);
}
q_descend
Commit 2008bc4
此函式會 移除所有非遞減的節點，確保佇列中的值是嚴格遞減的，具體實作過程如下：
- 若佇列為空或僅有一個節點，則直接返回對應大小。
- 從 倒數第二個節點開始 向前走訪佇列，並維護一個
max變數，記錄目前遇到的最大值。 - 若當前節點的值 大於
max，則更新max，保留該節點；否則刪除該節點。 - 最後返回佇列剩餘的節點數量。
q_merge
Commit 77eba2e
此函式的作用是 合併所有已排序的佇列，並按照指定的升序或降序排列，具體實作過程如下：
- 若
head為空，則返回 0。 - 取得
head中的第一個queue_contex_t作為合併的主要佇列qc。 - 走訪
head中的其他queue_contex_t，將其佇列 (q) 併入qc->q，並更新size。 - 併入後，對
qc->q進行排序。 - 最後返回合併後的佇列大小。
Commit f656bf8
此提交優化了：
- 修正變數名稱，增加可讀性。（
qc→first_qc,tmp→cur_qc） - 不使用
list_for_each_entry，顯式地從第二個元素開始走訪，優化掉了迭代中的if判斷。
int q_merge(struct list_head *head, bool descend)
{
// https://leetcode.com/problems/merge-k-sorted-lists/
- queue_contex_t *qc = list_first_entry(head, queue_contex_t, chain);
- queue_contex_t *tmp = NULL;
+ queue_contex_t *first_qc = list_first_entry(head, queue_contex_t, chain);
+ struct list_head *cur_chain = (&(first_qc->chain))->next;
- list_for_each_entry (tmp, head, chain) {
+ for (; cur_chain != head; cur_chain = cur_chain->next) {
- if (tmp == qc)
- continue;
+ queue_contex_t *cur_qc = list_entry(cur_chain, queue_contex_t, chain);
...
}
...
}
Dudect 修正
Commit a3405ea
-
首先我先準備
prepare_percentiles()函式來生成指數遞減的不同的取樣域值：
-
接著在執行的過程中，使用不同的區間來進行 Welch's t-test，藉由取不同區間段的資料來排除掉極端值，或是因被 CPU 排程影響的異常值。
// t-test on cropped execution times, for several cropping thresholds.
for (size_t j = 0; j < NUM_PERCENTILES; j++) {
if (difference < percentiles[j]) {
t_push(t, difference, classes[i]);
}
}
Shuffle
實作 Fisher–Yates shuffle 演算法：
Commit c67bb6e
/* Fisher-Yates shuffle */
for (size_t i = qsize - 1; i > 0; i--) {
size_t j = rand() % (i + 1);
struct list_head *cur = head->next, *swap = head->next;
for (size_t k = 0; k < i; k++)
cur = cur->next;
for (size_t k = 0; k < j; k++)
swap = swap->next;
swap_nodes(swap, cur);
}
從尾部開始走訪，從該節點之前（包含）隨機抽取一個點進行互換。
機率計算
考慮佇列包含
假設從
此時點
因此
根據數學歸納法，
Shannon entropy
根據上述推導與熵的公式：
模擬測試
由測試用的 Python 腳本 shuffle_test.py 測試，得出以下結果以及作圖。
Expectation: 41666
Observation: {'1234': 41894, '1243': 41595, '1324': 41504, '1342': 41843, '1423': 41723, '1432': 41952, '2134': 41567, '2143': 41137, '2314': 41565, '2341': 41480, '2413': 41757, '2431': 41664, '3124': 41991, '3142': 41419, '3214': 41515, '3241': 41999, '3412': 41906, '3421': 41648, '4123': 41547, '4132': 41873, '4213': 41349, '4231': 41656, '4312': 41730, '4321': 41686}
chi square sum: 25.505448087169388
從
Linux List Sorting
Commit 940cc05
我將 Linux kernel 中的 lib/list_sort.c 移植到 linux_listsort.c 中，並在 qtest 內新增指令 sort_l 以供測試。
Commit f0147c7
並撰寫測試程式 sort_eff_read.c (讀取測試資料)、sort_eff_qsort.c (執行q_sort) 以及 sort_eff_linux.c (執行Linux listsort)、 配合 clock() 和以下 perf 指令進行測試。
$ perf stat ./test_filename
得出以下輸出：
Read testcases took 4.838672 sec
q_sort took 18.697750 sec
Linux sort took 8.900504 sec
Read test cases took 4.838672 sec
Performance counter stats for './sort_eff_read':
5,043.21 msec task-clock # 1.000 CPUs utilized
48 context-switches # 9.518 /sec
4 cpu-migrations # 0.793 /sec
2,109,444 page-faults # 418.274 K/sec
9,694,053,542 cpu_atom/cycles/ # 1.922 GHz (0.00%)
23,277,332,448 cpu_core/cycles/ # 4.616 GHz (100.00%)
5,632,706,802 cpu_atom/instructions/ # 0.58 insn per cycle (0.00%)
62,900,097,052 cpu_core/instructions/ # 6.49 insn per cycle (100.00%)
1,114,237,134 cpu_atom/branches/ # 220.938 M/sec (0.00%)
12,711,879,975 cpu_core/branches/ # 2.521 G/sec (100.00%)
50,854,925 cpu_atom/branch-misses/ # 4.56% of all branches (0.00%)
12,050,810 cpu_core/branch-misses/ # 1.08% of all branches (100.00%)
TopdownL1 (cpu_core) # 31.0 % tma_backend_bound
# 2.0 % tma_bad_speculation
# 20.0 % tma_frontend_bound
# 47.1 % tma_retiring (100.00%)
TopdownL1 (cpu_atom) # 41.9 % tma_bad_speculation
# 13.6 % tma_retiring (0.00%)
# 0.0 % tma_backend_bound
# 44.5 % tma_frontend_bound (0.00%)
5.045026600 seconds time elapsed
3.029803000 seconds user
2.013869000 seconds sys
q_sort took 18.697750 sec
Performance counter stats for './sort_eff_qsort':
23,617.91 msec task-clock # 0.999 CPUs utilized
882 context-switches # 37.345 /sec
43 cpu-migrations # 1.821 /sec
2,109,442 page-faults # 89.315 K/sec
80,433,036,134 cpu_atom/cycles/ # 3.406 GHz (0.17%)
108,092,876,794 cpu_core/cycles/ # 4.577 GHz (99.77%)
46,758,971,684 cpu_atom/instructions/ # 0.58 insn per cycle (0.20%)
89,704,983,258 cpu_core/instructions/ # 1.12 insn per cycle (99.77%)
8,907,805,711 cpu_atom/branches/ # 377.163 M/sec (0.20%)
17,480,987,840 cpu_core/branches/ # 740.158 M/sec (99.77%)
198,552,105 cpu_atom/branch-misses/ # 2.23% of all branches (0.20%)
213,863,677 cpu_core/branch-misses/ # 2.40% of all branches (99.77%)
TopdownL1 (cpu_core) # 67.2 % tma_backend_bound
# 3.1 % tma_bad_speculation
# 10.9 % tma_frontend_bound
# 18.8 % tma_retiring (99.77%)
TopdownL1 (cpu_atom) # 11.2 % tma_bad_speculation
# 12.3 % tma_retiring (0.20%)
# 69.3 % tma_backend_bound
# 7.2 % tma_frontend_bound (0.20%)
23.646281130 seconds time elapsed
21.631719000 seconds user
1.986239000 seconds sys
Linux sort took 8.900504 sec
Performance counter stats for './sort_eff_linux':
13,850.40 msec task-clock # 0.996 CPUs utilized
1,606 context-switches # 115.953 /sec
9 cpu-migrations # 0.650 /sec
2,109,444 page-faults # 152.302 K/sec
48,078,089,762 cpu_atom/cycles/ # 3.471 GHz (0.05%)
63,453,990,816 cpu_core/cycles/ # 4.581 GHz (99.93%)
114,601,258,673 cpu_atom/instructions/ # 2.38 insn per cycle (0.06%)
84,023,936,486 cpu_core/instructions/ # 1.75 insn per cycle (99.93%)
23,391,891,100 cpu_atom/branches/ # 1.689 G/sec (0.06%)
17,286,557,130 cpu_core/branches/ # 1.248 G/sec (99.93%)
26,820,239 cpu_atom/branch-misses/ # 0.11% of all branches (0.06%)
406,362,795 cpu_core/branch-misses/ # 1.74% of all branches (99.93%)
TopdownL1 (cpu_core) # 29.5 % tma_backend_bound
# 4.2 % tma_bad_speculation
# 22.2 % tma_frontend_bound
# 44.1 % tma_retiring (99.93%)
TopdownL1 (cpu_atom) # 2.1 % tma_bad_speculation
# 53.7 % tma_retiring (0.06%)
# 21.2 % tma_backend_bound
# 22.9 % tma_frontend_bound (0.06%)
13.908267131 seconds time elapsed
11.717652000 seconds user
2.127757000 seconds sys
注：以下皆以 Linux 實作 與 原版 代稱 Linux listsort 與 q_sort 。
比較perf輸出可發現：
- 可以發現 Linux 實作的效率比原版高非常多，Linux 實作的效率是原板的
- Linux 實作的 instructions/cycle 比原版高（1.75 > 1.12），這是因為 Linux 實作中，merge sort 的 bottom up 實作對 cache 較友善。
- Linux 實作的 branch miss 也比原版的低，可能是因為 Linux 實作比傳統的 bottom-up mergesort少了
Commit cca2af4
此提交將 sort_eff_qsort.c、sort_eff_linux.c以及sort_eff_read.c 合併到sort_eff.c中，減少程式碼重複性並增加維護性。
可以執行以下命令測試
$ make sort_eff
$ ./sort_eff [linux, qsort, read] [-wait]
嘗試改進
首先我先用 perf top 取樣：
$ perf top -p pid
q_sort：
44.30% sort_eff_qsort [.] merge
34.06% libc.so.6 [.] __strcmp_avx2
10.86% sort_eff_qsort [.] q_reverse
8.27% sort_eff_qsort [.] merge_sort_ascend
0.57% sort_eff_qsort [.] strcmp@plt
...
Linux listsort：
56.03% libc.so.6 [.] __strcmp_avx2
19.15% sort_eff_linux [.] cmp_descend
16.85% sort_eff_linux [.] linux_merge
2.94% sort_eff_linux [.] list_sort
1.67% sort_eff_linux [.] strcmp@plt
1.03% sort_eff_linux [.] merge_final
...
以及用 perf record 取樣並配合 perf report（篩選過後）
q_sort：
+ 34.06% 33.48% sort_eff_qsort sort_eff_qsort [.] merge
+ 29.52% 28.88% sort_eff_qsort libc.so.6 [.] __strcmp_avx2
+ 17.97% 1.60% sort_eff_qsort sort_eff_qsort [.] alloc
+ 11.63% 0.80% sort_eff_qsort libc.so.6 [.] malloc
+ 11.44% 3.65% sort_eff_qsort libc.so.6 [.] _int_malloc
+ 6.91% 6.88% sort_eff_qsort sort_eff_qsort [.] merge_sort_ascend
+ 6.38% 6.37% sort_eff_qsort sort_eff_qsort [.] q_reverse
+ 4.24% 4.03% sort_eff_qsort libc.so.6 [.] __random
+ 1.95% 0.58% sort_eff_qsort sort_eff_qsort [.] read_test_cases
+ 1.13% 0.59% sort_eff_qsort sort_eff_qsort [.] strcmp@plt
+ 0.83% 0.74% sort_eff_qsort libc.so.6 [.] __random_r
0.25% 0.06% sort_eff_qsort sort_eff_qsort [.] malloc@plt
Linux listsort：
+ 35.88% 35.09% sort_eff_linux libc.so.6 [.] __strcmp_avx2
+ 29.43% 2.31% sort_eff_linux sort_eff_linux [.] alloc
+ 19.25% 1.29% sort_eff_linux libc.so.6 [.] malloc
+ 18.89% 6.07% sort_eff_linux libc.so.6 [.] _int_malloc
+ 14.71% 13.36% sort_eff_linux sort_eff_linux [.] cmp_descend
+ 12.97% 10.12% sort_eff_linux sort_eff_linux [.] linux_merge
+ 7.16% 6.83% sort_eff_linux libc.so.6 [.] __random
+ 3.04% 0.84% sort_eff_linux sort_eff_linux [.] read_test_cases
1.70% 1.65% sort_eff_linux sort_eff_linux [.] list_sort
+ 1.55% 0.79% sort_eff_linux sort_eff_linux [.] strcmp@plt
+ 1.24% 1.03% sort_eff_linux libc.so.6 [.] __random_r
0.75% 0.51% sort_eff_linux sort_eff_linux [.] merge_final
0.74% 0.62% sort_eff_linux libc.so.6 [.] __strlen_avx2
觀察：
- 首先，
q_reverse佔了其中不小的比例，要提昇效率應該使用兩個不同的cmp函式而不是先排序成遞增再反轉。 - 另外，發現在兩種實作方法中，Linux
merge所佔的比例約只有q_sort 的 20% 。下圖為q_sortmerge不同程式碼段佔的時間比例，可以發現在指標的指派上花了很多時間，可能是因為cache miss的關係。 - 字串比較的時間也是 Linux 實作更快（雖然Linux看似比例較高，但整個程式花的時間差了兩倍以上，因此 Linux 還是更快），這源自於 Linux 實作時減少的比較數量。
│ char *l_val = list_first_entry(l, element_t, list)->value; ▒
│ char *r_val = list_first_entry(r, element_t, list)->value; ▒
│ struct list_head *node = strcmp(l_val, r_val) <= 0 ? l->next : r->n◆
23.41 │ mov -0x8(%rbx),%rsi
40.18 │ mov -0x8(%rbp),%rdi
1.40 │ → call strcmp@plt
0.15 │ test %eax,%eax
2.11 │ cmovle %rbp,%rbx
│ struct list_head *next = node->next;
12.55 │ mov 0x8(%rbx),%rdx
│ struct list_head *prev = node->prev;
0.02 │ mov (%rbx),%rax
│ next->prev = prev;
12.81 │ mov %rax,(%rdx)
Address Sanitizer
在執行 make SANITIZER=1 && make test 後，並沒有遇到錯誤訊息產生，完美通過 Address Sanitizer 的檢測。
Valgrind
我寫了一個簡單的 shell script 來使用 Valgrind 測試是否有記憶體錯誤，並將 stdout 導到 /dev/null 使輸出更整潔：
for file in traces/*.cmd; do
# test 14 and 16 are too slow with valgrind
if [[ $file == *"14"* ]] || [[ $file == *"16"* ]]; then
echo "Running test with $file without SIGALRM"
valgrind -q --leak-check=full ./scripts/debug.py -d < "$file" > /dev/null
continue
fi
echo "Running test with $file"
valgrind -q --leak-check=full ./qtest < "$file" > /dev/null
done
除了 14 和 16 號之外的測試皆沒有問題，而分析 14 和 16 號測試發現錯誤是來自 ./qtest 在超時後會直接報錯並中止程式，造成記憶體未正常釋放。（超時原因是因為 Valgrind 插入的測試程式嚴重脫慢程式）因此改為用 ./scripts/debug.py -d 來取消 Alarm clock。
最後所有測試皆通過 Valgrind 測試，如下圖所示。
Running test with traces/trace-01-ops.cmd
Running test with traces/trace-02-ops.cmd
Running test with traces/trace-03-ops.cmd
Running test with traces/trace-04-ops.cmd
Running test with traces/trace-05-ops.cmd
Running test with traces/trace-06-ops.cmd
Running test with traces/trace-07-string.cmd
Running test with traces/trace-08-robust.cmd
Running test with traces/trace-09-robust.cmd
Running test with traces/trace-10-robust.cmd
Running test with traces/trace-11-malloc.cmd
Running test with traces/trace-12-malloc.cmd
Running test with traces/trace-13-malloc.cmd
Running test with traces/trace-14-perf.cmd without SIGALRM
Running test with traces/trace-15-perf.cmd
Running test with traces/trace-16-perf.cmd without SIGALRM
Running test with traces/trace-17-complexity.cmd
更新：後來才發現有 make valgrind 可以使用，仍然有通過測試。
Web 命令/網頁伺服器改善
Commit 83ed391
- 首先我將變數
web_connfd從區域變數變成全域變數，方便在report.c中進行是否有連線的判斷，以及關閉連線。 - 接著在
report()，在訊息尾部傳送\0給接收者，並關閉連線並重置變數web_connfd = 0;。
void report(int level, char *fmt, ...)
{
...
if (web_connfd) {
...
web_send(web_connfd, buffer);
+ if (write(web_connfd, "\0", 1) == -1)
+ perror("write");
+ close(web_connfd);
+ web_connfd = 0;
}
}
- 新增
void send_response(int out_fd)取代原本的回覆：HTTP/1.1 200 OK\r\nContent-Type: text/plain\r\n\r\n，讓瀏覽器可以正常連接，解決favicon.ico的問題。 - 新增測試程式 test_web.c 測試結果如下，輸出有如預期。
HTTP/1.1 200 OK
%s%s%s%s%s%sContent-Type: text/html
<html><head><style>body{font-family: monospace; font-size: 13px;}td {padding: 1.5px 6px;}</style><link rel="shortcut icon" href="#"></head><body><table>
l = []
7 7
Match
- 使用
curl命令測試結果
curl http://localhost:9999/new --output -
curl http://localhost:9999/ih/1 --output -
curl http://localhost:9999/ih/2 --output -
curl http://localhost:9999/ih/3 --output -
curl http://localhost:9999/sort --output -
curl http://localhost:9999/quit --output -
輸出也如預期：
<html><head><style>body{font-family: monospace; font-size: 13px;}td {padding: 1.5px 6px;}</style><link rel="shortcut icon" href="data:image/x-icon;," type="image/x-icon"></head><body><table>
l = []
<html><head><style>body{font-family: monospace; font-size: 13px;}td {padding: 1.5px 6px;}</style><link rel="shortcut icon" href="data:image/x-icon;," type="image/x-icon"></head><body><table>
l = [1]
<html><head><style>body{font-family: monospace; font-size: 13px;}td {padding: 1.5px 6px;}</style><link rel="shortcut icon" href="data:image/x-icon;," type="image/x-icon"></head><body><table>
l = [2 1]
<html><head><style>body{font-family: monospace; font-size: 13px;}td {padding: 1.5px 6px;}</style><link rel="shortcut icon" href="data:image/x-icon;," type="image/x-icon"></head><body><table>
l = [3 2 1]
<html><head><style>body{font-family: monospace; font-size: 13px;}td {padding: 1.5px 6px;}</style><link rel="shortcut icon" href="data:image/x-icon;," type="image/x-icon"></head><body><table>
l = [1 2 3]
<html><head><style>body{font-family: monospace; font-size: 13px;}td {padding: 1.5px 6px;}</style><link rel="shortcut icon" href="data:image/x-icon;," type="image/x-icon"></head><body><table>
Freeing queue
- 使用瀏覽器進行測試，如圖所示傳送了
ih 2給伺服器，伺服器則返回了插入了 2 的佇列l = [2, 4, 5]。
Commit b6b6bf2
在測試中發現使用瀏覽器傳送 request 的時候，會重複執行兩次命令，如下圖：
終端也確實收到了兩份 request 並且兩個都接受了。終端顯示：
cmd>
l = [2]
cmd>
l = [2 2]
在與 @nyraa 詢問後，發現範例程式碼中 "</style><link rel=\"shortcut icon\" href=\"#\">" 會將 request 導到也就是目前網址#，但 # 會在瀏覽器內處理掉，因此等同於原網址。因此將 href 改為空的 data url ，以防止送出重複的 request，修改如下。
void send_response(int out_fd)
...
"td {padding: 1.5px 6px;}"
- "</style><link rel=\"shortcut icon\" href=\"#\">"
+ "</style><link rel=\"shortcut icon\" href=\"data:image/x-icon;,\" type=\"image/x-icon\">"
"</head><body><table>\n";
...
修改後，當瀏覽器傳送空的 request 時，server端會收到 . 指令，如下圖：
因此新增了command . 去處理。
bool do_no_command(int argc, char *argv[])
{
report(1, "Empty command");
return true;
}
void init_cmd()
{
...
add_cmd(".", do_no_command, "Empty command", "");
...
}
經過改動後，瀏覽器能進行正常的request，不會重複傳送之外，也解決了 Unknown command '.' 的問題。
