HackMD
2024q1 Homework1 (lab0)
contributed by < slipet >
移除 </details>，開發紀錄的存在是讓他人更容易理解你所作所為，從而協同開發，但過多的 </details> 只是增加編輯的難度。
開發環境
$ gcc --version
gcc (Ubuntu 12.3.0-1ubuntu1~22.04) 12.3.0
$lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 48 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 5 5600X 6-Core Processor
CPU family: 25
Model: 33
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 0
Frequency boost: enabled
CPU max MHz: 4650.2920
CPU min MHz: 2200.0000
BogoMIPS: 7399.64
改進 queue.c
q_new
commit: 629656
將記憶體分配 配置給指標 q 後檢查是否成功配置記憶體，並且使用ININT_LIST_HEAD 將 q->next 和 q->prev 指向自身。
allocate 翻譯為「配置」，而非「分配」，是為了跟「分發」(dispatch) 區隔，二者都會在作業系統領域多次出現。
q_insert_head and q_insert_tail
$ sed -n '/bool q_insert_head/,/^\}/p' queue.c > q_insert_head.tmp
$ sed -n '/bool q_insert_tail/,/^\}/p' queue.c > q_insert_tail.tmp
$ diff q_insert_head.tmp q_insert_tail.tmp
... ...
13c13
< list_add(&new_element->list, head);
---
> list_add_tail(&new_element->list, head);
利用 diff 命令，我們能分辨出 q_insert_head 和 q_insert_tail 分別使用了不同的插入函式。
使用 diff -u
當我們在 head->prev 位置利用 list_add 函式插入元素時，這一操作實際上與使用 list_add_tail 函式達到的插入效果相同。
因此，透過統一採用 q_insert 函式來統一這兩種插入操作，從而減少程式碼的重複性。
q_remove_head and q_remove_tail
原本想重用之前寫過的程式碼，但這次想嘗試讓程式碼更簡潔，因此參考 Linux 核心原始程式碼巨集: max, min 定義了一個 MIN 的巨集，被複製的字串長度最多不會超過 bufsize - 1，預留一個空間的用意是為了放置字串的結束字元 \0。
- size_t len = strlen(del->value);
- len = (len + 1 > bufsize) ? bufsize : len + 1;
- strncpy(sp, del->value, bufsize);
- sp[len - 1] = '\0';
+ /* Bufsize reserves space for a null terminator.*/
+ size_t len = MIN(strlen(del->value), bufsize - 1);
+ strncpy(sp, del->value, len);
+ sp[len + 1] = '\0';
但是上述的程式碼在第一個測試案例會出現錯誤。
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
ERROR: Removed value dolphinX != expected value dolphin
ERROR: Removed value bearX != expected value bear
...
被移除的字串並沒有正確的複製到 sp ，因為結尾都是 X，在 qtest.c 的 queue_remove() 可以發現測試程式會事先在 removes 填入 X ，透過檢查 [string_length + 1, string_length + STRINGPAD) 區間的字元判斷記憶體操作是否有越界。
memset(removes + 1, 'X', string_length + STRINGPAD - 1);
我推測是 sp[len + 1] = '\0'; 寫錯了， strncpy 複製長度 len 的字串填入 \0 的位置應該是 sp[len] 。
- sp[len + 1] = '\0';
+ sp[len] = '\0';
修改後可以通過第一個測試案例。
最後，與 q_insert 相同，採用 q_remove 函式統一這兩種移除操作，減少重複的程式碼。
q_delete_mid
分析「快慢指標」 裡討論了兩種實作方式 (1) 單一節點走訪 (2) 快慢指標，兩者的時間複雜度皆為
這裡我想嘗試"從頭尾兩端相向前進"的方式來刪除中間的節點，具體方法為從頭尾兩端相向走訪，最後會在中間相遇，時間複雜度為
bool q_delete_mid(struct list_head *head)
{
if (head == NULL || list_empty(head))
return false;
struct list_head **iter = &head;
struct list_head *tail = head->prev;
while ((*iter) != tail && (*iter)->next != tail) {
iter = &(*iter)->next;
tail = tail->prev;
}
struct list_head *del = (*iter)->next;
list_del(del);
q_release_element(container_of(del, element_t, list));
return true;
}
在 Makefile 中修改編譯選項 旗標，分別採用 -O0 和 -O3 兩種最佳化等級來編譯，得到的組合語言分別為 53 行和 41 行。可以觀察到，由於對 list_empty 函式的聲明中加入inline 關鍵字，在 -O3 最佳化等級下（第 4、5 行）可以直接將程式碼展開，而不需要像在 -O0 等級（第 11、12 行）那樣進行函式呼叫。此外，在 -O0 最佳化等級下發現了對 list_del 和 q_release_element 的呼叫，但在 -O3 下則未見這些呼叫，推測這與 list_empty 一樣，已經被編譯器進行了最佳化。
-O0
45a: f3 0f 1e fa endbr64
45e: 55 push %rbp
45f: 48 89 e5 mov %rsp,%rbp
462: 48 83 ec 30 sub $0x30,%rsp
466: 48 89 7d d8 mov %rdi,-0x28(%rbp)
46a: 48 8b 45 d8 mov -0x28(%rbp),%rax
+ 46e: 48 85 c0 test %rax,%rax // head == NULL
+ 471: 74 10 je 483 <q_delete_mid+0x29> // 如果 head 為 NULL 跳到 483
473: 48 8b 45 d8 mov -0x28(%rbp),%rax
477: 48 89 c7 mov %rax,%rdi
+ 47a: e8 4c fc ff ff call cb <list_empty> 呼叫 list_empty
+ 47f: 85 c0 test %eax,%eax // 確認 list_empty 的回傳值
+ 481: 74 0a je 48d <q_delete_mid+0x33> // 如果 回傳值為 0 跳到 48d
+ 483: b8 00 00 00 00 mov $0x0,%eax //把 false 搬到 %eax
+ 488: e9 85 00 00 00 jmp 512 <q_delete_mid+0xb8> // 跳到 return => 512
48d: 48 8d 45 d8 lea -0x28(%rbp),%rax
491: 48 89 45 e0 mov %rax,-0x20(%rbp)
495: 48 8b 45 d8 mov -0x28(%rbp),%rax
499: 48 8b 00 mov (%rax),%rax
49c: 48 89 45 e8 mov %rax,-0x18(%rbp)
4a0: eb 1a jmp 4bc <q_delete_mid+0x62>
+ 4a2: 48 8b 45 e0 mov -0x20(%rbp),%rax // while-loop body start
4a6: 48 8b 00 mov (%rax),%rax
4a9: 48 83 c0 08 add $0x8,%rax
4ad: 48 89 45 e0 mov %rax,-0x20(%rbp)
4b1: 48 8b 45 e8 mov -0x18(%rbp),%rax
4b5: 48 8b 00 mov (%rax),%rax
4b8: 48 89 45 e8 mov %rax,-0x18(%rbp)
4bc: 48 8b 45 e0 mov -0x20(%rbp),%rax
4c0: 48 8b 00 mov (%rax),%rax
+ 4c3: 48 39 45 e8 cmp %rax,-0x18(%rbp) //(*iter) != tail
+ 4c7: 74 11 je 4da <q_delete_mid+0x80> // 如果等於成立跳到 4da
4c9: 48 8b 45 e0 mov -0x20(%rbp),%rax
4cd: 48 8b 00 mov (%rax),%rax
4d0: 48 8b 40 08 mov 0x8(%rax),%rax
+ 4d4: 48 39 45 e8 cmp %rax,-0x18(%rbp) // (*iter)->next != tail
+ 4d8: 75 c8 jne 4a2 <q_delete_mid+0x48> // 如果不等於成立 跳到 4a2
4da: 48 8b 45 e0 mov -0x20(%rbp),%rax
4de: 48 8b 00 mov (%rax),%rax
4e1: 48 8b 40 08 mov 0x8(%rax),%rax
4e5: 48 89 45 f0 mov %rax,-0x10(%rbp)
4e9: 48 8b 45 f0 mov -0x10(%rbp),%rax
4ed: 48 89 c7 mov %rax,%rdi
+ 4f0: e8 76 fb ff ff call 6b <list_del> // 呼叫 list_del
4f5: 48 8b 45 f0 mov -0x10(%rbp),%rax
4f9: 48 89 45 f8 mov %rax,-0x8(%rbp)
4fd: 48 8b 45 f8 mov -0x8(%rbp),%rax
501: 48 83 e8 08 sub $0x8,%rax
505: 48 89 c7 mov %rax,%rdi
+ 508: e8 da fb ff ff call e7 <q_release_element> // 呼叫 q_release_element
50d: b8 01 00 00 00 mov $0x1,%eax
512: c9 leave
+ 513: c3 ret
-O3
380: f3 0f 1e fa endbr64
+ 384: 48 85 ff test %rdi,%rdi //檢查指標 head 是否為 0
+ 387: 74 57 je 3e0 <q_delete_mid+0x60> // 如果為 0 跳到 3e0
+ 389: 48 8b 47 08 mov 0x8(%rdi),%rax // head->next
+ 38d: 48 39 c7 cmp %rax,%rdi // head->next == head
+ 390: 74 4e je 3e0 <q_delete_mid+0x60> // 如果為 0 跳到 3e0
392: 53 push %rbx
393: 48 8b 1f mov (%rdi),%rbx
+ 396: 48 39 df cmp %rbx,%rdi //(*iter) != tail
+ 399: 75 11 jne 3ac <q_delete_mid+0x2c> //如果不等於跳到 3ac
39b: eb 51 jmp 3ee <q_delete_mid+0x6e>
39d: 0f 1f 00 nopl (%rax)
3a0: 48 8b 1b mov (%rbx),%rbx
3a3: 48 39 d8 cmp %rbx,%rax
3a6: 74 40 je 3e8 <q_delete_mid+0x68>
3a8: 48 8b 40 08 mov 0x8(%rax),%rax
+ 3ac: 48 39 d8 cmp %rbx,%rax //(*iter)->next != tail)
+ 3af: 75 ef jne 3a0 <q_delete_mid+0x20> // 如果不等於跳到 3a0
3b1: 48 8b 03 mov (%rbx),%rax
3b4: 48 8b 53 08 mov 0x8(%rbx),%rdx
3b8: 48 8b 7b f8 mov -0x8(%rbx),%rdi
3bc: 48 89 02 mov %rax,(%rdx)
3bf: 48 89 50 08 mov %rdx,0x8(%rax)
3c3: e8 00 00 00 00 call 3c8 <q_delete_mid+0x48>
3c8: 48 8d 7b f8 lea -0x8(%rbx),%rdi
3cc: e8 00 00 00 00 call 3d1 <q_delete_mid+0x51>
3d1: b8 01 00 00 00 mov $0x1,%eax
3d6: 5b pop %rbx
+ 3d7: c3 ret
3d8: 0f 1f 84 00 00 00 00 nopl 0x0(%rax,%rax,1)
3df: 00
3e0: 31 c0 xor %eax,%eax
+ 3e2: c3 ret
3e3: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)
3e8: 48 8b 5b 08 mov 0x8(%rbx),%rbx
3ec: eb c3 jmp 3b1 <q_delete_mid+0x31>
3ee: 48 89 c3 mov %rax,%rbx
3f1: eb be jmp 3b1 <q_delete_mid+0x31>
3f3: 66 66 2e 0f 1f 84 00 data16 cs nopw 0x0(%rax,%rax,1)
3fa: 00 00 00 00
3fe: 66 90 xchg %ax,%ax
去閱讀 Intel 指令集手冊，而非毫無權威可言的 ChatGPT!
為何要捨近求遠呢？
TODO:設計實驗比較文章裡的兩種方法跟我的方法，速度，快取錯失 (cache miss)，要注意實驗的資料量。
q_delete_dup
使用 list_for_each_entry_safe 迭代檢查 entry 和 safe 是否相等，若是相等則進入 while 迴圈將重複的元素刪除。實作完成後測試程式碼時出現 Segmentation fault 。
Segmentation fault occurred. You dereferenced a NULL or invalid pointerAborted (core dumped)
bool q_delete_dup(struct list_head *head)
{
if (head == NULL || list_empty(head) || list_is_singular(head))
return false;
element_t *entry = NULL, *safe = NULL;
list_for_each_entry_safe (entry, safe, head, list) {
if (strcmp(entry->value, safe->value) == 0) {
element_t *del;
while (&safe->list != head &&
strcmp(entry->value, safe->value) == 0) {
del = safe;
safe = list_entry(safe->list.next, element_t, list);
list_del_init(&(del->list));
q_release_element(del);
}
list_del_init(&entry->list);
q_release_element(entry);
}
}
return true;
}
使用 valgrind 觀察錯誤發生時的訊息:
$ valgrind ./qtest -f traces/trace-18-dedup.cmd
# Test of insert_head and remove_head
l = []
l = [a]
l = [aa a]
l = [z aa a]
==39771== Invalid read of size 1
==39771== at 0x484FBD7: strcmp (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==39771== by 0x10FAF9: q_delete_dup (queue.c:138)
==39771== by 0x10C081: do_dedup (qtest.c:465)
==39771== by 0x10E02E: interpret_cmda (console.c:181)
==39771== by 0x10E5DF: interpret_cmd (console.c:201)
==39771== by 0x10E9E0: cmd_select (console.c:610)
==39771== by 0x10F2BE: run_console (console.c:705)
==39771== by 0x10D420: main (qtest.c:1258)
==39771== Address 0xdeadbeef is not stack'd, malloc'd or (recently) free'd
==39771==
Segmentation fault occurred. You dereferenced a NULL or invalid pointer==39771== 2 bytes in 1 blocks are still reachable in loss record 1 of 48
==39771== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==39771== by 0x10BEF5: do_dedup (qtest.c:442)
==39771== by 0x10E02E: interpret_cmda (console.c:181)
==39771== by 0x10E5DF: interpret_cmd (console.c:201)
==39771== by 0x10E9E0: cmd_select (console.c:610)
==39771== by 0x10F2BE: run_console (console.c:705)
==39771== by 0x10D420: main (qtest.c:1258)
從前兩個區塊的開頭訊息可以分別得知 Invalid read of size 1 和 Segmentation fault occurred. You dereferenced a NULL or invalid pointer，並且從 at 0x484FBD7: strcmp 可以得知錯誤可能發生在上述實作的第 7 行 if 內的 strcmp 。
仔細觀察程式碼後，發現 list_for_each_entry_safe 有確保進入迴圈的 entry 不等於 head，但是 safe 則沒有。當迴圈走訪至鏈結串列最後一個元素時， safe 的 list 位置會在 head 上，因此這時如果 safe->value 則會存取一個未知的記憶體空間而產生 Segmentation fault 。
- if (strcmp(entry->value, safe->value) == 0) {
+ if (&safe->list != head && strcmp(entry->value, safe->value) == 0) {
多加一個條件檢查 safe 確保不是 head ，修改後可以正確的刪除重複的元素。
q_reverse
走訪每一個節點，把節點移出並且加入開頭，如下圖所示:
走訪完成可以得到翻轉後的鏈結串列。
q_reverseK
維護一個計數器 counter 一旦走訪 k 個節點後利用 list_cut_position 將剛剛所經過的子串列截取出來，使用 q_reverse 將子串列翻轉並用 list_splice_init 插入原本的鏈結串列。要注意的是翻轉的是 (start, end] ，也就是 q_reverse 傳入的節點位置必須是子串列開頭的前一個位置。
假設 k = 3，翻轉 (3, 6] 內的子串列。
翻轉完後插入原本的串列，接著將 start 指到子串列的尾端 safe->prev ，要注意這裡 end 因為翻轉後變成子串列的開頭所以不能將 start 指向 end 。
q_swap 是 q_reverseK 在 k = 2 時的特例，因此選擇重用 q_reverseK。
q_ascend and q_descend
q_ascend 從 head 沿著 next 的方向走訪至鏈結串列的尾端，在走訪的過程中不斷更新目前的最大值，移除比最大值還小的節點，以維持串列的單調性。 而 q_descend 也是相同的概念，但是走訪的方向則是從 head 沿著 prev 的方向走訪至鏈結串列的開頭。兩者的差別如下:
$ diff q_ascend.tmp q_descend.tmp
4,5c4,5
- < element_t *entry = list_entry(head->next, element_t, list);
- < element_t *safe = list_entry((entry->list).next, element_t, list);
---
+ > element_t *entry = list_entry(head->prev, element_t, list);
+ > element_t *safe = list_entry((entry->list).prev, element_t, list);
14c14
- < safe = list_entry((entry->list).next, element_t, list);
---
+ > safe = list_entry((entry->list).prev, element_t, list);
前四行為一開始初始化的宣告，可以觀察到兩個函式只差別在從 next 或是 prev 開始走訪。最後兩行則是走訪方向，分別為 next 和 prev 。
因為程式碼有大量重複的部份，所以想嘗試設計一個 q_monotonic 函式，利用傳入 descend 決定鏈結的單調性。
static inline int q_monotonic(struct list_head *head, bool descend)
{
// 1 for descend
// 0 for ascend
if (head == NULL || list_empty(head) || list_is_singular(head))
return list_is_singular(head);
element_t *entry, *safe;
if (descend) {
entry = list_entry(head->prev, element_t, list);
safe = list_entry((entry->list).prev, element_t, list);
} else {
entry = list_entry(head->next, element_t, list);
safe = list_entry((entry->list).next, element_t, list);
}
char *mx = entry->value;
while (&entry->list != head) {
if (compare(mx, entry->value)) {
list_del_init(&entry->list);
q_release_element(entry);
} else
mx = entry->value;
entry = safe;
if (descend) {
safe = list_entry((entry->list).prev, element_t, list);
} else {
safe = list_entry((entry->list).next, element_t, list);
}
}
return q_size(head);
}
結果為了判斷遞增或遞減，加入額外的 if-else 並沒有使得程式碼更精簡。因此，考慮使用前處理器產生程式碼，一開始設計的時候不太確定前處理器是否可以使用巢狀的方式撰寫巨集，查詢 C 語言規格書 可以發現 6.10.3.4 Rescanning and further replacement 就有關於前處理器關於取代規則的說明。
- After all parameters in the replacement list have been substituted and # and ## processing has taken place, all placemarker preprocessing tokens are removed. Then, the resulting preprocessing token sequence is rescanned, along with all subsequent preprocessing tokens of the source file, for more macro names to replace.
以我的理解，這段告訴我們可以使用巢狀巨集 (nested macro) 的技巧，因為前處理器會在取代後會再次掃描產生出來的 preprocessing token sequence ， 儘可能地尋找要取代的巨集。
我們可以從 list.h 裡的 list_for_each_entry 為例子，在展開的程式碼裡又有一個 list_entry 的巨集。
- If the name of the macro being replaced is found during this scan of the replacement list (not including the rest of the source file’s preprocessing tokens), it is not replaced. Furthermore, if any nested replacements encounter the name of the macro being replaced, it is not replaced. These nonreplaced macro name preprocessing tokens are no longer available for further replacement even if they are later (re)examined in contexts in which that macro name preprocessing token would otherwise have been replaced.
這段接著解釋，前處理器在哪些情況下不會進行展開。首先，在當前掃描的部份不會遞迴展開。此外，如果在當前的掃描中如果沒有符合的巨集可以取代的部份，那在後續的掃描即使這部份有符合的巨集名稱也無法進行取代。
#define q_monotonic(head, direction) \
({ \
if (!head || list_empty(head) || list_is_singular(head)) \
return q_size(head); \
element_t *entry = list_entry(head->direction, element_t, list); \
element_t *safe = \
list_entry((entry->list).direction, element_t, list); \
char *mx = entry->value; \
while (&entry->list != head) { \
if (compare(mx, entry->value)) { \
list_del(&entry->list); \
q_release_element(entry); \
} else { \
mx = entry->value; \
} \
entry = safe; \
safe = list_entry((entry->list).direction, element_t, list); \
} \
q_size(head); \
})
int q_ascend(struct list_head *head)
{
return q_monotonic(head, next);
}
int q_descend(struct list_head *head)
{
return q_monotonic(head, prev);
}
q_monotonic(head, direction) 利用取代 direction 的方式決定鏈結為遞增或是遞減。使用前處理器的方式會有一個缺點，必須在編譯時期就決定為遞增或是遞減，若使用函數 q_ascend 和 q_descend 包裝起來可以在使用上更彈性。
q_sort
使用 top-down 的方法:
- 頭尾相向而行尋找中點。
- 將鏈結串列從中點斷開成左右兩個子串列。
- 對子串列進行遞迴排序，直到子串列為空或是剩下一個節點。
- 呼叫
q_merge_two將兩個排序完成的子鏈結串列結合成一個鏈結串列。
commit 79b62e
q_merge_two 比較左右子串列的節點大小，將被選擇的節點加入 head。因為需要支援升序和降序排列的功能，因此會有四種情況需要考慮。
降序排列時:
使用 compare(left, right) ＆ descend 判斷將左或右的子鏈結的節點加入 head ，必須將較大的節點加入 head 維持降序排列。
- 當
compare(left, right) == true時，表示左邊節點的字串"大於"右邊節點，因此選擇左鏈結的節點。 - 當
compare(left, right) == false時，表示左邊節點的字串"小於等於"右邊節點，因此選擇右鏈結的節點。
升序排列時:
使用 compare(right, left) ＆ ！descend 判斷將左或右的子鏈結的節點加入 head ，必須將較小的節點加入 head 維持升序排列。
- 當
compare(right, left) == true時，表示右邊節點的字串"大於"左邊節點，因此選擇左鏈結的節點。 - 當
compare(right, left) == false時，表示右邊節點的字串"小於等於"左邊節點，因此選擇右鏈結的節點。
static inline bool compare(char *left, char *right)
{
return strcmp(left, right) > 0;
}
static inline void q_merge_two(struct list_head *head,
struct list_head *left,
struct list_head *right,
bool descend)
{
while (!list_empty(left) && !list_empty(right)) {
if ((compare(list_entry(left->next, element_t, list)->value,
list_entry(right->next, element_t, list)->value) &
descend) ||
(compare(list_entry(right->next, element_t, list)->value,
list_entry(left->next, element_t, list)->value) &
(!descend))) {
list_move_tail(left->next, head);
} else {
list_move_tail(right->next, head);
}
}
if (!list_empty(left)) {
list_splice_tail_init(left, head);
} else {
list_splice_tail_init(right, head);
}
}
q_merge
跟 q_sort 一樣，走訪時會從頭尾兩端相向而行，將合併後的佇列放回原本的鏈結等待下輪合併，反覆的迭代直到整個鏈結串列只剩一個佇列。
commit: fb1594
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
整合網頁伺服器
從程式碼可以發現，網頁伺服器啟動後，因為use_linenoise被設為false導致linenoise不能使用，這時會執行cmd_select函式處理使用者從命令列和網頁輸入的命令。修改run_console中while-loop的判斷式使linenoise的功能可以在網頁伺服器啟動後仍然得以執行，如下所示:
- while (use_linenoise && (cmdline = linenoise(prompt, web_proc))) {
+ while ((cmdline = linenoise(prompt, web_proc))) {
雖然修改後linenoise得以恢復執行，但linenoise會不斷讀取使用者的輸入導致網頁的輸入阻塞沒有回應。而原本能處理網頁輸入的cmd_select也因此無法執行。
這裡我參考原本cmd_select裡關於處理網頁輸入的方法，額外定義一個web_proc的函式處裡網頁的輸入，並且使用參數傳遞(linenoise -> line_raw -> line_edit)將web_proc以函式指標傳遞至line_edit內的while-loop處理網頁輸入。
commit: 6d9771c
參考vax-r後發現我目前的實作方式有一個缺點，使用函數指標傳遞會造成傳遞的路徑過長(linenoise -> line_raw -> line_edit)，會增加未來除錯與維護時的困難度，應該使用註冊函式的方式將處理網頁輸入的函式獨立於linenoise。
引入 lib/list_sort.c
參考 chiangkd 的方法引入 list_sort.c 和 list_sort.h
因為需要支援 descend 和 ascend 兩種功能，因此在 cmp 使用跟前面 qsort 裡的 compare 相似的技巧減少重複的程式碼。
int cmp(void *priv, const struct list_head *a, const struct list_head *b)
{
element_t *itemA = list_entry(a, element_t, list);
element_t *itemB = list_entry(b, element_t, list);
int ascend_result = ((strcmp(itemB->value, itemA->value) > 0) & descend);
int descend_result = ((strcmp(itemA->value, itemB->value) > 0) & !descend);
return ascend_result || descend_result;
}
在 qtest.c 加入新的指令命令。
command 的翻譯是「命令」，而非「指令」(instruction)
ADD_COMMAND(kernel_sort,"Sort queue in ascending/descening order with lib/list_sort.c","");
kernel_sort 的實作大部分都跟原本的 sort 相同，只有在實作時呼叫 list_sort 取代原本的 qsort。
...
- q_sort(current->q, descend);
+ list_sort(NULL, current->q, cmp);
...
定義實驗的腳本如下:
# Test qsort & list_sort
option fail 0
option malloc 0
new
ih RAND 1000000
time
sort/kernel_sort
time
分別執行五次紀錄所需時間
| qsort | list_sort | |
|---|---|---|
| 1st | 0.420 | 0.471 |
| 2nd | 0.416 | 0.472 |
| 3rd | 0.428 | 0.488 |
| 4th | 0.435 | 0.459 |
| 5th | 0.426 | 0.469 |
| avg | 0.425 | 0.472 |
實驗結果發現使用的執行時間 list_sort 並沒有優於 qsort。參考 Linux 效能分析工具: Perf，使用perf 觀察兩者的 instruction 、 cpu cycle 、 cache miss/references。
$perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./qtest -f ./traces/trace-sort.cmd
| qsort | list_sort | |
|---|---|---|
| cache-misses | 2,6957,4388 58.089 % of all cache refs |
2,3196,1362 60.275 % of all cache refs |
| cache-references | 7,7342,3443 | 6,4220,6947 |
| instructions | 270,7594,3722 | 276,6568,6444 |
| cycles | 275,3986,7721 | 285,9127,1880 |
| elapsed time(s) | 1.2012 ± 0.0107 | 1.23950 ± 0.00852 |
可以發現雖然使用 lib/list_sort 的 cache-misses 較低，但是在 instructions 、 cycles 、 elapsed time 的表現都是都是比 qsort 要高一點的。
注意測試案例是否反映出資料分布
shuffle
將隨機選到的 node 用 list_move_tail 插入 list 的尾端，並且用 size 的控制隨機取值的區間。
void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
int size = q_size(head);
struct list_head *cur;
while(size--) {
int idx = rand()%(size);
cur = head->next;
while(idx--)cur = cur->next;
list_move_tail(cur,head);
}
}
在 qtest 執行 shuffle 後會出現錯誤:
Floating point exception (core dumped)
使用 valgrind 後可以發現是因為除以零出現 SIGFPE 這個 signal 而出錯。
==1288817==
==1288817== Process terminating with default action of signal 8 (SIGFPE)
==1288817== Integer divide by zero at address 0x1002DE3155
==1288817== at 0x1104BA: q_shuffle (queue.c:350)
==1288817== by 0x10C628: do_shuffle (qtest.c:526)
==1288817== by 0x10E306: interpret_cmda (console.c:181)
==1288817== by 0x10E8BB: interpret_cmd (console.c:201)
==1288817== by 0x10ECBC: cmd_select (console.c:610)
==1288817== by 0x10F5A8: run_console (console.c:705)
==1288817== by 0x10D6F8: main (qtest.c:1341)
...
最後修改成下面：
void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
int size = q_size(head);
struct list_head *cur;
- while(size--) {
+ while(size) {
int idx = rand()%(size);
cur = head->next;
while(idx--)cur = cur->next;
list_move_tail(cur,head);
+ size--;
}
}
接著使用 [1,2,3] shuffle 一百萬次，
設
Expectation: 166666
Observation: {'123': 166680, '132': 166887, '213': 166492, '231': 166606, '312': 166431, '321': 166904}
chi square sum: 1.1686966747866991
我們的
因此 P value(0.90~0.95)>
分佈圖如下：
研讀論文〈Dude, is my code constant time?〉
- 論文的方法是計算兩組 input data(fix-vs-random) 的執行時間，進行 Student’s t-test 驗證是否能推翻虛無假說
- 本專案使用的是 Welch’s t-test ， 與 Student’s t-test 相比會在兩組樣本有不同的變異數和樣本數時更可靠
- 從論文的 II-B 可以得知因為 process 可能會因為 OS 的中斷或其他因素導致 timing distributions 比較偏向分佈的右邊。
Typical timing distributions are positively skewed towards larger execution times. This may be caused by measurement artifacts, the main process being interrupted by the OS or other extraneous activities.
- 由作業可以得知 lab0-c 並未實作 percentile 的處理。
We discard measurements that are larger than the p percentile, for various^2 values of p. The rationale here is to test a restricted distribution range, especially the lower cycle count tail. The upper tail may be more influenced by data-independent noise.
嘗試引入 dudect.h 的 percentile 處理
在 dudect.h 的實作將 percentiles 定義在 dudect_ctx_t 這個資料結構中，但是 lab0 的實作則沒有，所以我也遵循 lab0 的方式將 percentiles 定義在 do_it。
static bool doit(int mode)
{
......
+ int64_t *percentiles =
+ (int64_t *) calloc(DUDECT_NUMBER_PERCENTILES, sizeof(int64_t));
if (!before_ticks || !after_ticks || !exec_times || !classes ||
!input_data) {
die();
}
prepare_inputs(input_data, classes);
bool ret = measure(before_ticks, after_ticks, input_data, mode);
differentiate(exec_times, before_ticks, after_ticks);
- update_statistics(exec_times, classes);
+ bool first_time = percentiles[DUDECT_NUMBER_PERCENTILES - 1] == 0;
+ if (first_time) {
+ prepare_percentiles(exec_times, percentiles);
+ }
update_statistics(exec_times, classes, percentiles);
ret &= report();
......
}
工程人員說話要精準，看不懂就是看不懂，不要說「比較看不懂」
誠實面對自己！
將 exec_times 利用 qsort 排序，計算每個百分點位置對應的值存入 percentiles。 1 - (pow(0.5, 10 * (double) (i + 1) / DUDECT_NUMBER_PERCENTILES) 這段程式碼的計算是 比較看不懂 的部份。 這裡我們把 DUDECT_NUMBER_PERCENTILES 設為 100 ，可以把前面寫成數學式
| i-th | |
|---|---|
| 0 | 0.066967008 |
| 1 | 0.129449437 |
| 2 | 0.187747604 |
| 3 | 0.242141717 |
| … | … … |
| 30 | 0.883370876 |
| 31 | 0.891181180 |
| … | … … |
| 98 | 0.998878224 |
| 98 | 0.998953346 |
| 99 | 0.999023438 |
我們可以發現這段數學是主要是算出每個百分點位置，並且對分佈在右側的資料密集的取樣。
static int cmp(const int64_t *a, const int64_t *b)
{
return (int) (*a - *b);
}
static int64_t percentile(int64_t *a_sorted, double which, size_t size)
{
size_t array_position = (size_t) ((double) size * (double) which);
assert(array_position >= 0);
assert(array_position < size);
return a_sorted[array_position];
}
static void prepare_percentiles(int64_t *exec_times, int64_t *percentiles)
{
qsort(exec_times, N_MEASURES, sizeof(int64_t),
(int (*)(const void *, const void *)) cmp);
for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) {
percentiles[i] = percentile(
exec_times,
1 - (pow(0.5, 10 * (double) (i + 1) / DUDECT_NUMBER_PERCENTILES)),
N_MEASURES);
}
}
接著在 update_statistics 中利用 percentiles 進行裁切。
static void update_statistics(const int64_t *exec_times,
uint8_t *classes,
int64_t *percentiles)
{
......
/*do cropping ...*/
+ for (size_t crop_index = 0; crop_index < DUDECT_NUMBER_PERCENTILES;
+ crop_index++) {
+ if (difference < percentiles[crop_index]) {
+ t_push(t, difference, classes[i]);
+ }
+ }
}
}
加入 percetiles 的部份後，測試程式可達到目標的 100/100 並且看到皮卡丘卡比。
為什麼是皮卡丘？
你應該確認程式碼是在 2024 年 2 月 21 日 09:10AM 以後取得。
務必細讀 2024 年 Linux 核心設計/實作課程作業 —— lab0
使用 git rebase，而非 git merge
先在 540e9b 建立一個新的 branch develop_2024， 然後使用 $git rebase -i develop_2024 540e9b 。 並且將之前的 commit 移除。
回顧現有的 git commits:
存在以下錯誤:
- 未依據 Chris Beams 撰寫的 How to Write a Git Commit Message 一文，撰寫明確的 git commit message。你可以想像 Apple 和 Google 的工程師隨便安置程式碼，然後不用管合作的議題嗎？
- 在 git commit message 中，應該在內文解釋 what 以及 why vs. how
- 單一 commit 混雜不相關的修改，例如
q_size與q_insert無關 - 使用的英語詞彙太困乏，無助於溝通
重新 fork 再來，不要假裝自己有投入，我們追求的是「有強度」的資訊系統。
MCTS
由 MCTS 可以知道每個節點的權重會扮演著非常重要的角色，其計算公式如下:
empirically 參數，通常為 exploitation 項(利用過去經驗)，右項當成 exploration (當模擬次數越多，此節點被選次數越少，比重越大)。
上述公式會在 ttt 中的 uct_score 進行計算，為了避免使用浮點運算單元 (FPU)，可以以定點數來替代浮點數運算。定點數的加減乘除可以利用位移的方式確保正確計算，但是公式內自然對數
論文作者 IBM 研究員 J.E. Meggitt 改良了一個中古世紀時人們計算對數的演算法 Radix Method，模擬除法的運算期間將除數進行調整，可以幫助我們獲得
這個我們從高中就可以學到的對數性質，可以將 N 分解成若干個
由文章可以得知等式:
我們可以將一個 10 進制的實數
對兩邊取
Fixed Point Arithmetic 內有詳細的公式推導說明，這裡的
要注意的是這個公式是應用在10進制的計算。關於二進制部分接著介紹一篇由浮點數之父 William Kahan 撰寫的一篇文章 Pseudo-Division Algorithms for Floating-Point Logarithms and Exponentials ，主要的內容只有6頁，但是卻可以言簡意賅的闡述從推導到實際演算法的過程。
What makes the pseudo-division algorithms so attractive is their close resemblance to the simplest binary multiplication and division algorithms
這段話可以得知為何人們一開始會選擇使用 pseudo-division 的原因，因為整個演算法只需要單純的加法和位移操作即可實作，因此文中也有提到像是 8087 數值協同處理器也有使用此演算法。
Algorithms like these are used by the Intel 8087 family of numeric coprocessors.
雖然這篇文章的內容是應用在浮點數， 但是對於 pseudo division 的核心想法同樣適用在定點數上。由於計算 uct_score 時只會有正整數，所以這裡只考慮關於正整數的部份。
首先定義等式:
這個無窮乘積需要使用 Euler function (不是 Euler's totient function) 才能計算[註]，可以得到 link 與論文中相同的答案。可以得到
對於單精度的浮點數至小數點後第7位即足夠(
對於一個浮點數 Y，想計算其
可以知道"正" 單精度的浮點數 表示為:
只考慮正數部分，對於 Normorlized 的部分可以將
對於 Denormorlized 的部分同樣可以得到:
可以發現不管是浮點數或是定點數，都可以透過提取出
仍然可以提取出
對於每個 pseudo-quotient bit
這個不等式可以理解為，為了找出符合所求
從上面的不等式可以得到下面的遞迴式:
Implementation
由前一小節得到的遞迴式:
可以實作出32位元 UQ16.16 的定點數 __builtin_clz 得到最高項的係數 expo = 32 - lz，可以將前面的定點數表示為 UQ1.16。第 17 ~ 35 行是上述遞迴式的實作，當等式成立時 pseudo-qoutient bit
下面的實作透過變數 r 儲存當
必須把事先計算的對數值轉換成定點數的格式，所以此時必須乘 0x95C0。
由[註]可以知道如果要對小於
因此所得到的補償值會是
最終，將前面得到的 expo 轉換成 (expo << FSHIFT32) - r 得到輸出的答案。下面是對應的實作:
#define FSHIFT32 16
#define FIXED32_1 (1 << FSHIFT32)
uint32_t log2(uint32_t x)
{
if (x == 1) return 0;
uint32_t z, t, one = FIXED32_1; // UQ1.16
uint32_t r = 0;
uint32_t lz, expo;
/* split: x = a * 2**expo, 0 < a < 1 */
lz = __builtin_clz(x);
expo = 32 - lz;
z = (x << lz) >> (32 - FSHIFT32); // UQ1.16
/* try factors (1+2**(-i)) with i = 1, ..., 16 */
if ((t = z + (z >> 1)) < one) { z = t; r += 0x095c0; }
if ((t = z + (z >> 2)) < one) { z = t; r += 0x0526a; }
if ((t = z + (z >> 3)) < one) { z = t; r += 0x02b80; }
if ((t = z + (z >> 4)) < one) { z = t; r += 0x01664; }
if ((t = z + (z >> 5)) < one) { z = t; r += 0x00b5d; }
if ((t = z + (z >> 6)) < one) { z = t; r += 0x005ba; }
if ((t = z + (z >> 7)) < one) { z = t; r += 0x002e0; }
if ((t = z + (z >> 8)) < one) { z = t; r += 0x00171; }
if ((t = z + (z >> 9)) < one) { z = t; r += 0x000b8; }
if ((t = z + (z >> 10)) < one) { z = t; r += 0x00052; }
if ((t = z + (z >> 11)) < one) { z = t; r += 0x0002e; }
if ((t = z + (z >> 12)) < one) { z = t; r += 0x00017; }
if ((t = z + (z >> 13)) < one) { z = t; r += 0x0000c; }
if ((t = z + (z >> 14)) < one) { z = t; r += 0x00006; }
if ((t = z + (z >> 15)) < one) { z = t; r += 0x00003; }
if ((z + (z >> 16)) < one) { /* z = t;*/ r += 0x00001; }
r-=2;
r = (expo << FSHIFT32) - r;
return r;
}
原本的遞迴式可以透過迭代加上查找表的方式實作，但是直接展開可以利用編譯器的最佳化選項改善，另外最後一個判斷式內的 z = t 其實是冗餘，展開後可以直接省略。這裡要注意的是這個函式輸入為32位元的無號整數，而輸出則是
Square Root
由 從 √2 的存在談開平方根的快速運算 可以知道對於開根號有非常多種的方式可以實作，這裡會接著介紹如合從 Meggitt 的 10 進制 pseudo division 計算開根號並推廣至 2 進制的實作，核心想法與 Digit-by-digit calculation 類似。
首先定義等式:
假設對於 pseudo qoutient bit
此等式的目標是要盡可能的使
跟之前一樣簡化遞迴式:
遞迴式會一直計算
對於初始條件可以知道，當從第
另外可以知道，
由上面性質可以得到，當需要計算
完成整個演算法。
Binary
接著將演算法推廣至2進制，假設定點數:
定義遞迴式:
簡化遞迴式:
初始條件為，
對於初始條件可以知道，當從第
由前面 10 進制的介紹對於
Implementation
為了將輸入改寫成下面的形式:
需要將
可以發現下面第 9 行就是為了將
從前面的說明可以知道如果
由上面的說明可以知道初始條件為，
下面程式碼是對應的實作:
uint32_t UQ16P16_pseudo_division_sqrt(uint32_t n)
{
const int lz = __builtin_clz(n);
const uint32_t one = 1UL << 29;
uint32_t y = n;
uint32_t x = one, d = one << 2;
uint32_t r = 0, count = 0;
y = (y << lz >> 1) >> (lz & 1);
int expo = (FSHIFT - lz + (lz & 1)) / 2;
while (count < (FSHIFT) ) {
d >>= 1;
if (y >= x) {
y -= (x);
x = x + (d);
r += (one >> count >> 14);
}
y <<=1;
x-= (d >> 2);
count++;
}
return (expo >= 0) ? r << (expo) : r >> (-expo);
}
客製化定點數
前面的實作為
Coroutine
參考 coro 設計我的 coroutine 實作，coro 使用 setjmp 和 longjmp 達到在不同任務間切換。
當使用者輸入指令 ttt 會呼叫 schedule 利用使用者輸入的參數初始化遊戲，將執行遊戲的 task 放入一個鏈結串列 tasklist 中提供 task_switch 挑選執行的任務，如同 coro 設計的一樣， task 反覆的呼叫 gameplay 函數進行遊玩，每個 task 的目標很簡單只需要在 gameplay 返回時跳轉至 task_switch，task_switch 會從 tasklist 中選出下一個要執行的任務進行跳轉。
整個過程如同下面這張圖:
將每場 ttt 遊戲的遊玩狀態劃分成 INIT, MOVE, DRAW, CMPLT, END，因此可以利用目前的狀態得知下一個階段該怎麼執行，INIT 為開始時初始化遊戲的部分，狀態 DRAW 會判斷當前棋盤是否有贏家產生並繪製棋盤，MOVE 可以利用目前玩家的參數使用 AI 或是 HUMAN 選擇落子，若是兩個玩家的參數都是 AI 則是 AI 與 AI 互相對弈，當遊戲進行中時會不斷地在 DRAW 和 MOVE 間切換，一旦其中一方勝利時會切換至 CMPLT 將遊戲收尾並將狀態設為 END 宣告這局遊戲真正的結束。狀態圖的變化如下:
由於每局遊戲的狀態都是各自分配空間儲存，儘管其中一局遊戲提前結束時，task 不會將結束的遊戲加入 tasklist 進行排程，所以不會影響未結束的遊戲，這個設計可以使我們同時觀看多局遊戲同時進行。
暫停當前畫面輸出的功能則是利用將 stdout 導入一個暫時的 buffer達到暫停的效果。
接著參考 Build Your Own Text Editor 的方式建立一個 pthread 監聽目前的鍵盤事件，這裡選擇使用 pthread 的方式的原因為如果在原本的 tasklist 加入監聽任務，會因為其他的任務執行而沒辦法及時的對鍵盤事件進行回應。
目前的實作有一個缺點未來可以繼續改進的部分，一旦暫停畫面輸出時若是有某局遊戲已經結束了，仍然會留在 tasklist 中參與排程等待停止暫停輸出時繪製遊戲結果，造成占用執行資源的情況，隨著同時遊玩的局數增加時，大量的任務會在列隊裡等待輸出遊戲結果，這種情況勢必會影響到尚未結束的遊戲執行時間。目前的初步的改良想法為增加一個 idlelist，將遊玩結束後等待輸出結果的任務放入 idlelist 等待恢復輸出，當重新開始輸出時便加入一個任務將 idlelist 內等待的任務加回 tasklist。
Reference
- 你所不知道的 C 語言: linked list 和非連續記憶體
- chiangkd
- hongpei100
- Linux 效能分析工具: Perf
- Compute logarithmic expression without floating point arithmetics or log
- https://stackoverflow.com/questions/76908525/how-do-i-compute-a-fixed-point-binary-logarithm
本文標題用 # (一個井字號)，子項目標題用 ## (二個井字號)。注意細節！
