# 2025q1 Homework1 (lab0)
contributed by < `liangchingyun` >
### Reviewed by `Urbaner3`
>根據作業 review，檢查事項 1, 5, 8 嘗試聚焦並整理程式碼，並加強改進。
>6.48 Alternate Keywords 此段落，注意表達的因果關係，我不是很容易直接解釋或是想到他與什麼有關聯，請舉例，並以此為例，再檢查作業一二文章表達通順。
>鼓勵根據作業要求、能力，挑戰論文閱讀，設計實驗。為了專題做預備。如果排程器、中斷、線程等名詞有不理解，隨時提出問題，向講師、同學、討論區發問，養成習慣作筆記，保持進步，一定會成功的。
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 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
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz
CPU family: 6
Model: 158
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 10
CPU(s) scaling MHz: 39%
CPU max MHz: 4600.0000
CPU min MHz: 800.0000
BogoMIPS: 6399.96
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 smx est tm2 ssse3 sdbg fma cx16 xtpr pd
cm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb pti ssbd ibrs ibpb stibp fsgs
base tsc_adjust bmi1 avx2 smep bmi2 erms invpcid 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 arch_capabilities
Caches (sum of all):
L1d: 192 KiB (6 instances)
L1i: 192 KiB (6 instances)
L2: 1.5 MiB (6 instances)
L3: 12 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-11
Vulnerabilities:
Gather data sampling: Mitigation; Microcode
Itlb multihit: KVM: Mitigation: VMX unsupported
L1tf: Mitigation; PTE Inversion
Mds: Mitigation; Clear CPU buffers; SMT vulnerable
Meltdown: Mitigation; PTI
Mmio stale data: Mitigation; Clear CPU buffers; SMT vulnerable
Reg file data sampling: Not affected
Retbleed: Mitigation; IBRS
Spec rstack overflow: Not affected
Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointer sanitization
Spectre v2: Mitigation; IBRS; IBPB conditional; STIBP conditional; RSB filling; PBRSB-eIBRS Not affected; BHI Not affected
Srbds: Mitigation; Microcode
Tsx async abort: Mitigation; TSX disabled
```
## 針對佇列操作的程式碼實作
> [作業要求](https://hackmd.io/@sysprog/linux2025-lab0-a)
### q_size
```c
int q_size(struct list_head *head)
{
if (!head)
return 0;
int len = 0;
struct list_head *pos;
list_for_each (pos, head)
len++;
return len;
}
```
> `list_for_each`: 走訪雙向鏈結串列中的每個節點
### q_new
一開始並沒有初始化`list_head`，這導致分配的記憶體中`list_head`結構的成員未被設置為預期的初始值，顯示錯誤：
`Segmentation fault occurred. You dereferenced a NULL or invalid pointerAborted (core dumped)`
修改後正確初始化`list_head`
```diff
struct list_head *q_new()
{
struct list_head *new_head = malloc(sizeof(struct list_head));
- if (new_head != NULL) {
+ if (new_head) {
+ INIT_LIST_HEAD(new_head);
return new_head;
}
return NULL;
}
```
### q_insert_head & q_insert_tail
`q_insert_head` : 將一個新元素插入到佇列的首部。
`q_insert_tail` : 將一個新元素插入到佇列的尾部。
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *new_ele = malloc(sizeof(element_t));
if (!new_ele)
return false;
INIT_LIST_HEAD(&new_ele->list);
new_ele->value = strdup(s);
if (!new_ele->value) {
free(new_ele);
return false;
}
list_add(&new_ele->list, head);
return true;
}
```
`q_insert_tail` 即是將 `list_add` 改為 `list_add_tail`
> `strdup`: 分配記憶體並將字符串複製到該記憶體中
### q_free
一開始使用 `list_for_each_entry_safe` 巨集指令，在commit時遇到問題：
```
Following files need to be cleaned up:
queue.c
Running static analysis...
queue.c:35:5: error: There is an unknown macro here somewhere. Configuration is required. If list_for_each_entry_safe is a macro then please configure it. [unknownMacro]
list_for_each_entry_safe (entry, safe, l, list)
^
Fail to pass static analysis.
```
因此我去查標頭檔中對`list_for_each_entry_safe` 的定義：
```c
#if __LIST_HAVE_TYPEOF
#define list_for_each_entry_safe(entry, safe, head, member) \
for (entry = list_entry((head)->next, typeof(*entry), member), \
safe = list_entry(entry->member.next, typeof(*entry), member); \
&entry->member != (head); entry = safe, \
safe = list_entry(safe->member.next, typeof(*entry), member))
#endif
```
根據 [3.4 Options Controlling C Dialect](http://gcc.gnu.org/onlinedocs/gcc/C-Dialect-Options.html)，使用 `-ansi` 會關閉某些 GCC 特性，因此會禁用 `typeof` 關鍵字。在 [6.48 Alternate Keywords](https://gcc.gnu.org/onlinedocs/gcc/Alternate-Keywords.html#index-_005f_005fextension_005f_005f) 中提到使用替代關鍵字（如 `__asm__` 、`__extension__` 、`__inline__` 和 `__typeof__` ）即可在啟用 `-ansi` 時使用。然而，若修改標頭檔會出現錯誤訊息，因此改成不使用巨集指令的寫法：
```diff
void q_free(struct list_head *l)
{
if (!l || list_empty(l)) {
free(l);
return;
}
- element_t *entry, *safe;
+ struct list_head *pos = l->next;
- list_for_each_entry_safe (
- entry, safe, l,
- list)
- q_release_element(entry);
+ while (pos != l) {
+ element_t *entry = list_entry(pos, element_t, list);
+ pos = pos->next;
+ q_release_element(entry);
+ }
free(l);
return;
}
```
此函式完成後 `q_new`, `q_insert_head` 和 `q_insert_tail` 均得以通過 make test
> `struct list_head`: 鏈結串列的節點
> `element_t`: 是包含鏈結節點的結構體
> `list_entry`: 一個巨集，用來從鏈結節點指標（pos）回推「擁有這個節點的結構體」
### q_romove_head & q_romove_tail
`q_romove_head` : 將佇列的首部的元素移除。
`q_romove_tail` : 將佇列的尾部的元素移除。
```diff
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *first_entry = list_first_entry(head, element_t, list);
if (sp != NULL) {
- sp = strncpy(sp, first_entry->value, bufsize - 1);
+ strncpy(sp, last_entry->value, bufsize - 1);
sp[bufsize - 1] = '\0'; // Ensure the string is null-terminated
}
list_del(&first_entry->list);
return first_entry;
}
```
`strncpy` 函數已經將 `first_entry->value` 中的內容複製到 `sp` 中，因此不需要將 `sp` 重新賦值。
> `first_entry->list`: first_entry 節點中用來鏈接到其他節點的鏈結串列指針。
然而，此作法無法通過 trace-17-complexity。因為這個函數沒有處理 `first_entry->value` 可能為 `NULL` 的情況。如果 `value` 為 `NULL`，在使用 `strncpy` 時可能會導致未定義行為。
```diff
if (sp != NULL) {
+ if (first_entry->value != NULL) {
strncpy(sp, first_entry->value, bufsize - 1);
sp[bufsize - 1] = '\0'; // Ensure the string is null-terminated
+ } else {
+ sp[0] = '\0';
+ }
}
```
修改後即可通過 trace-17-complexity。
`q_remove_tail` 即是將 `first_entry` 改為 `last_entry` 。
### q_swap
原本的程式碼：
```c
void q_swap(struct list_head *head)
{
if (head == NULL || head->next == head || head->next->next == head)
return;
struct list_head *iterator = head->next;
struct list_head *temp;
while (iterator != head && iterator->next != head) {
temp = iterator->next;
iterator->prev->next = temp;
temp->prev = iterator->prev;
iterator->next = temp->next;
if (temp->next != head) {
temp->next->prev = iterator;
}
temp->next = iterator;
iterator->prev = temp;
iterator = iterator->next->next;
}
}
```
因為 `q_swap` 是 `q_reverseK` 在 `K=2` 時的特例，因此改為以下程式碼:
```c
void q_swap(struct list_head *head)
{
q_reverseK(head, 2);
}
```
### q_delete_mid
將節點從鏈結串列中刪除後，需要手動釋放這些節點所佔用的記憶體，因此做了以下修正：
```diff
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head))
return false;
struct list_head *ptr_1 = head->next;
struct list_head *ptr_2 = head->next;
while (ptr_1 != head && ptr_1->next != head) {
ptr_1 = ptr_1->next->next;
ptr_2 = ptr_2->next;
}
+ element_t *mid = list_entry(ptr_2, element_t, list);
list_del(ptr_2);
+ free(mid->value);
+ free(mid);
return true;
}
```
### q_delete_dup
參考 [2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/) 的其中一個[解法](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/solutions/4705282/simple-beginner-friendly-dry-run-two-pointer-approach-time-o-n-space-o-1-gits)
> 使用 `strcmp` 比較兩個節點的 `value` 是否相同
### q_reverse
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head)) {
return;
}
struct list_head *cur = head->next;
struct list_head *temp = NULL;
while (cur != head) {
temp = cur->next;
cur->next = cur->prev;
cur->prev = temp;
cur = temp;
}
temp = head->next;
head->next = head->prev;
head->prev = temp;
}
```
### q_reverseK
```c
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (!head) {
return;
}
int split_time = q_size(head) / k;
struct list_head *tail;
LIST_HEAD(tmp);
LIST_HEAD(new_head);
for (int i = 0; i < split_time; i++) {
int j = 0;
list_for_each (tail, head) {
if (j >= k) {
break;
}
j++;
}
list_cut_position(&tmp, head, tail->prev);
q_reverse(&tmp);
list_splice_tail_init(&tmp, &new_head);
}
list_splice_init(&new_head, head);
}
```
### q_sort
參考同學寫法，使用 `MergeTwoLists`
* 將 `descend ^ (strcmp(e1->value, e2->value) < 0)` 定義成 `bool condition`，精簡了 `node` 的指派邏輯。
* 改寫了 `fast` 和 `slow` 指標的初始化方式，並將 `for` 循環改為 `while` 進行快慢指標的移動。
* 因為 `e1` 及 `e2` 的值不會遭變更，因此加上 `const`
```diff
void mergeTwoLists(struct list_head *L1, struct list_head *L2, bool descend)
{
if (!L1 || !L2)
return;
struct list_head head;
INIT_LIST_HEAD(&head);
while (!list_empty(L1) && !list_empty(L2)) {
- element_t *e1 = list_first_entry(L1, element_t, list);
- element_t *e2 = list_first_entry(L2, element_t, list);
- struct list_head *node = (descend ^ (strcmp(e1->value, e2->value) < 0))
- ? L1->next
- : L2->next;
+ const element_t *e1 = list_first_entry(L1, element_t, list);
+ const element_t *e2 = list_first_entry(L2, element_t, list);
+ bool condition = (descend ^ (strcmp(e1->value, e2->value) < 0));
+ struct list_head *node = condition ? L1->next : L2->next;
list_move_tail(node, &head);
}
list_splice_tail_init(list_empty(L1) ? L2 : L1, &head);
list_splice(&head, L1);
}
/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
// https://hackmd.io/IKsnn85aRHGMrNcRP7BJ1Q?view#2024q1-Homework1-lab0
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *slow = head;
- const struct list_head *fast = NULL;
+ struct list_head *fast = head->next;
- for (fast = head->next; fast != head && fast->next != head;
- fast = fast->next->next)
- slow = slow->next;
+ while (fast != head && fast->next != head) {
+ slow = slow->next;
+ fast = fast->next->next;
+ }
struct list_head left;
list_cut_position(&left, head, slow);
q_sort(&left, descend);
q_sort(head, descend);
mergeTwoLists(head, &left, descend);
}
```
### q_ascend & q_descend
簡化了走訪邏輯，直接用 `pos` 來控制位置，讓程式看起來更直觀。
```diff
int q_ascend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head))
return 0;
- element_t *right = list_entry(head->prev, element_t, list);
- element_t *left = list_entry(head->prev->prev, element_t, list);
- while (&left->list != head) {
+ struct list_head *pos = head->prev;
+ while (pos != head && pos->prev != head) {
+ const element_t *right = list_entry(pos, element_t, list);
+ element_t *left = list_entry(pos->prev, element_t, list);
if (strcmp(right->value, left->value) > 0) {
- left = list_entry(left->list.prev, element_t, list);
- right = list_entry(right->list.prev, element_t, list);
+ pos = pos->prev;
} else {
list_del(&left->list);
free(left->value);
free(left);
- left = list_entry(right->list.prev, element_t, list);
}
}
return q_size(head);
}
}
```
`q_descend` 即是將 `strcmp(right->value, left->value) > 0` 改成 `strcmp(right->value, left->value) < 0`
### q_merge
原本 `queue_to_merge` 是在迴圈外部宣告，但這個變數只在迴圈中使用，把它移進迴圈內。
```diff
int q_merge(struct list_head *head, bool descend)
{
if (!head || list_empty(head)) {
return 0;
}
queue_contex_t *base_queue = list_first_entry(head, queue_contex_t, chain);
if (list_is_singular(head)) {
return base_queue->size;
}
- queue_contex_t *queue_to_merge;
struct list_head *pos, *next;
list_for_each_safe (pos, next, head) {
if (pos == &base_queue->chain) {
continue;
}
- queue_to_merge = list_entry(pos, queue_contex_t, chain);
+ queue_contex_t *queue_to_merge = list_entry(pos, queue_contex_t, chain);
list_splice_tail_init(queue_to_merge->q, base_queue->q);
base_queue->size += queue_to_merge->size;
}
q_sort(base_queue->q, descend);
return base_queue->size;
}
```
## Valgrind 分析記憶體問題
> [作業要求](https://hackmd.io/@sysprog/linux2025-lab0-b)
### 運用 Valgrind 排除 qtest 實作的記憶體錯誤
執行 `$ make valgrind` 後，得到以下訊息：
```
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/liangchingyun/linux2025/lab0-c'
rm -f qtest.o report.o console.o harness.o queue.o random.o dudect/constant.o dudect/fixture.o dudect/ttest.o shannon_entropy.o linenoise.o web.o list_sort.o .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d .shannon_entropy.o.d .linenoise.o.d .web.o.d .list_sort.o.d *~ qtest /tmp/qtest.*
rm -rf .dudect
rm -rf *.dSYM
(cd traces; rm -f *~)
CC qtest.o
CC report.o
CC console.o
CC harness.o
CC queue.o
CC random.o
CC dudect/constant.o
CC dudect/fixture.o
CC dudect/ttest.o
CC shannon_entropy.o
CC linenoise.o
CC web.o
CC list_sort.o
LD qtest
make[1]: Leaving directory '/home/liangchingyun/linux2025/lab0-c'
cp qtest /tmp/qtest.fRLs65
chmod u+x /tmp/qtest.fRLs65
sed -i "s/alarm/isnan/g" /tmp/qtest.fRLs65
scripts/driver.py -p /tmp/qtest.fRLs65 --valgrind
--- Trace Points
+++ 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
Warning: Skip checking the stability of the sort because the number of elements 2000000 is too large, exceeds the limit 100000.
--- 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
Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.fRLs65 --valgrind -t <tid>
```
結果顯示程式通過所有測試，也沒有發生 Memory Leak 、 Invalid Memory Access 等問題。
### 透過 Massif 視覺化 simulation 過程中的記憶體使用量
## 整合網頁伺服器
## 研讀 lib/list_sort.c 並嘗試改進
> [作業要求](https://hackmd.io/@sysprog/linux2025-lab0-e)
這段程式碼涉及到三個核心函數：
1. `merge()` - 合併兩個已排序的單向鏈結串列，並返回排序後的鏈結串列
2. `merge_final()` - 進行最終合併並恢復雙向鏈結串列
3. `list_sort()` - 主排序函數，負責將鏈結串列拆分並合併排序
它使用空結尾的單向鏈結串列來合併子串列，最後再還原為雙向鏈結串列，提高效能。時間複雜度為 O(n log n)，適合排序大型鏈結串列。
### 流程舉例
在 `list_sort()` 中，排序過程透過 Bottom-Up 的方式進行合併：
1. 初始狀態：每個節點視為獨立的排序單元（1 個元素的區塊）
e.g., `[4] [2] [5] [3] [1]`
2. 合併相鄰的兩個區塊，確保每個合併後的區塊仍然有序
`[4]` + `[2]` → `[2,4]`
`[5]` + `[3]` → `[3,5]`
`[1]` (單獨保留，因為目前沒有另一個可合併的區塊)
3. 繼續合併已排序的區塊
`[2,4]` + `[3,5]` → `[2,3,4,5]`
`[1]` 保留
4. 最終合併
`[2,3,4,5]` + `[1]` → `[1,2,3,4,5]`
### 將 `list_sort.c` 加入 `lab0-c` 專案
> Commit: [0c1203d](https://github.com/sysprog21/lab0-c/commit/0c1203dc385bfbe40802563912f17ed72a08da16)
將 Linux 核心原始程式碼的 `list_sort.c` 和 `list_sort.h` 複製到 `lab0-c` 專案中，並且為了成功編譯做了以下修改：
* `list_sort.h` 與 `list.h` 路徑修正。
* 刪掉 `EXPORT_SYMBOL(list_sort)`
* 將 `u8` 改成 `uint8_t` 作為 `count`，並加入 `#include <stdint.h>`
* 移除不必要的 `#include`，手動加入 `likely` 和 `unlikely` 的定義。
在 `queue.h` 、 `queue.c` 中加入對應程式碼後，於 Makefile 中新增 `list_sort.o` 。另外，我在 `qtest.c` 中新增 option ksort ，用來切換原本的 `q_sort` 與新的 `q_ksort` 。
```c
static int sort_option = 0;
```
```c
add_param("ksort", &sort_option,
"Whether to use Linux kernel sorting algorithm", NULL);
```
```diff
if (current && exception_setup(true))
- q_sort(current->q, descend);
+ sort_option ? q_ksort(current->q, descend) : q_sort(current->q, descend);
exception_cancel();
```
### 效能分析
我執行 `./qtest` 並使用以下的命令來分析排序效能:
```
new
option ksort 1/0 <= (1: q_ksort; 0: q_sort)
ih RAND 100000
time sort
```
執行結果如下：
| q_sort | q_ksort |
| -------- | -------- |
| 0.111 | 0.089 |
因為不能變更 queue.h ，所以 commit 時將以下程式刪除，並註解掉相關部份：
```c
void q_ksort(struct list_head *head, bool descend);
```
### 開發 Timsort 排序程式
> 參考資料：[Linux 核心專題: 改進 lib/list_sort.c](https://hackmd.io/@sysprog/Hy5hmaKBh#TODO-%E5%BC%95%E5%85%A5-Timsort-%E5%8F%8A%E5%85%B6%E8%AE%8A%E5%BD%A2)、[Timsort 研究與對 Linux 核心貢獻嘗試](https://hackmd.io/@yanjiew/linux2023q1-timsort)、[最貼近現實的排序演算法- Timsort](https://jason18153.medium.com/%E6%9C%80%E8%B2%BC%E8%BF%91%E7%8F%BE%E5%AF%A6%E7%9A%84%E6%8E%92%E5%BA%8F%E6%BC%94%E7%AE%97%E6%B3%95-timsort-a75da75b65a2)、[linux23q1-timsort](https://github.com/visitorckw/linux23q1-timsort)
[liangchingyun/Sorts-main](https://github.com/liangchingyun/Sorts-main)
正確處理空指針的情況：
```diff
size_t get_run_size(struct list_head *run_head)
{
- return run_head ? 0 : (size_t)(run_head)->next->prev;
+ if (run_head == NULL || run_head->next == NULL ||
+ run_head->next->prev == NULL) {
+ return 0;
+ }
+ return (size_t)(run_head->next->prev);
}
```
縮小變數作用範圍：
```diff
static inline void list_rotate_left(struct list_head *head)
{
- struct list_head *first;
if (!list_empty(head)) {
- first = head->next;
+ struct list_head *first = head->next;
list_move_tail(first, head);
}
}
```
將沒有被修改的變數宣告為 `const` 指標
```diff
static inline int list_empty_careful(const struct list_head *head)
{
- struct list_head *next = head->next;
+ const struct list_head *next = head->next;
return (next == head) && (next == head->prev);
}
```
將 `head` 初始化為 `NULL`
```diff
static struct list_head *merge(void *priv, list_cmp_func_t cmp,
struct list_head *a, struct list_head *b)
{
- struct list_head *head, **tail = &head;
+ struct list_head *head = NULL, **tail = &head;
```
刪掉沒被使用的變數
```diff
static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
struct list_head *a, struct list_head *b)
{
struct list_head *tail = head;
- uint8_t count = 0;
```
指標 `tp` 指向 `stk - 1` 導致未定義行為的修正
```diff
void shiverssort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
struct list_head *list = head->next;
- struct run stk[MAX_MERGE_PENDING], *tp = stk - 1;
+ struct run stk[MAX_MERGE_PENDING], *tp = stk;
if (head == head->prev)
return;
/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;
do {
- tp++;
/* Find next run */
tp->list = list;
list = find_run(priv, list, &tp->len, cmp);
tp = merge_collapse(priv, cmp, stk, tp);
+ tp++;
} while (list);
+ tp--;
```
移除冗餘的運算
`(*tp).len` --> `tp->len`
`&(*(tp->next))` --> `->next`
`&(*(tp))` --> `tp`
測試結果:
| Implementation | Elapsed time | Comparisons |
| -------------- | ------------ | ----------- |
| Linux | 184876 | 19646345 |
| shiverssort | 137262 | 14339471 |
| timsort | 152536 | 15254864 |
## 實作 shuffle 命令
> [作業要求](https://hackmd.io/@sysprog/linux2025-lab0-d#%E5%9C%A8-qtest-%E6%8F%90%E4%BE%9B%E6%96%B0%E7%9A%84%E5%91%BD%E4%BB%A4-shuffle)
> Commit: [7023f89](https://github.com/sysprog21/lab0-c/commit/7023f8918e7f876caf681f0c737709fb40e5a570)
### 實作 Fisher-Yates shuffle Algorithm
從鏈結串列的尾端開始反向走訪，`pos` 表示目前尚未被抽取的最後一個節點，而 `pick` 則是從 `pos` 往前數的第 `r` 個節點，最後將 `pos` 和 `pick` 進行位置交換。
```c
static inline void swap(struct list_head *a, struct list_head *b)
{
if (a->prev != b) {
list_move(b, a->prev);
}
list_move(a, b->prev);
}
void q_shuffle(struct list_head *head)
{
if (!head || list_is_singular(head))
return;
for (int len = q_size(head); len > 1; len--) {
struct list_head *pos = head->prev;
struct list_head *pick = head->prev;
for (int r = rand() % len; r > 0; r--)
pick = pick->prev;
if (pick != pos)
swap(pos, pick);
}
}
```
因為不能變更 queue.h ，所以 commit 時將以下程式刪除，並註解掉相關部份：
```c
void q_shuffle(struct list_head *head);
```
### 統計方法驗證
用測試腳本進行測試，結果如下：
```
Expectation: 41666
Observation: {'1234': 41815, '1243': 41822, '1324': 41755, '1342': 41791, '1423': 41971, '1432': 41786, '2134': 41630, '2143': 41593, '2314': 41318, '2341': 41660, '2413': 41525, '2431': 41724, '3124': 41846, '3142': 41996, '3214': 42002, '3241': 41622, '3412': 41620, '3421': 41955, '4123': 41415, '4132': 41530, '4213': 41545, '4231': 41340, '4312': 41384, '4321': 41355}
chi square sum: 25.175106801708825
```
結果大致符合 uniform distribution。
## 亂數產生器
> [作業要求](https://hackmd.io/@sysprog/linux2025-lab0-d#%E4%BA%82%E6%95%B8)
嘗試計算 linux 內建的 PRNG /dev/random
```
$ head -c 10M /dev/random | ent
Entropy = 7.999980 bits per byte.
Optimum compression would reduce the size
of this 10485760 byte file by 0 percent.
Chi square distribution for 10485760 samples is 288.33, and randomly
would exceed this value 7.42 percent of the times.
Arithmetic mean value of data bytes is 127.4672 (127.5 = random).
Monte Carlo value for Pi is 3.142315347 (error 0.02 percent).
Serial correlation coefficient is -0.000074 (totally uncorrelated = 0.0).
```
## 研讀論文
### 〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉
> [作業要求](https://hackmd.io/@sysprog/linux2025-lab0-d#-%E8%AB%96%E6%96%87%E3%80%88Dude-is-my-code-constant-time%E3%80%89%E9%87%8D%E9%BB%9E%E6%8F%90%E7%A4%BA)
dudect 的檢測流程包含三個步驟：
1. 測量執行時間
針對不同的 輸入類別（input classes），測量其執行時間：
* 固定輸入（fixed class）：輸入值固定不變。
* 隨機輸入（random class）：每次測試時隨機選擇輸入值。
使用現代 CPU 提供的 cycle counter（如 x86 的 TSC 計數器或 ARM 的 systick）來測量執行時間。
2. 進行後處理
* 裁剪（cropping）： 為了減少環境雜訊影響，過大的測量值可以被丟棄。
* 高階處理（higher-order preprocessing）： 有時可以使用類似於 DPA 攻擊的方式進行數據處理，以提高檢測能力。
3. 進行統計測試
* Welch’s t-test（t 檢定）：檢測兩組輸入的執行時間分布是否有統計學上的顯著差異。
* Kolmogorov-Smirnov（K-S 檢定）：非參數檢定，適用於更廣泛的時間變異性分析。
### [Bottom-up Mergesort: A Detailed Analysis](https://link.springer.com/article/10.1007/BF01294131)
### [The cost distribution of queue-mergesort, optimal mergesorts, and power-of-two rules](https://doi.org/10.1006/jagm.1998.0986)
### [Queue-Mergesort](https://doi.org/10.1016/0020-0190(93)90088-q)
## Git 實作
### Commit & Push
```
clang-format -i *.[ch]
git commit -a
git push
```
### Config 設定
```
git config --global user.name "liangchingyun"
git config --global user.email "joanne10021@gmail.com"
```
### fetch
```
git remote add sysprog21 https://github.com/sysprog21/lab0-c.git
git fetch sysprog21
git remote remove sysprog21
```
### rebase
* `git branch` ：查看本地分支
* `git branch -r` ：查看遠端倉庫分支
* `git remote show origin` ：查看本地與遠端的關係
* `git status` ：檢查本地與遠端是否同步
* `git pull origin master` ：更新本地分支（拉取遠端的最新變更）
* `git push origin master` ：推送本地變更到遠端
* `git rebase -i HEAD~N`：查看最新的 N 個 Commit
* `git branch -d branch-name`：刪除本地分支
* `git branch -D branch-name`：強制刪除本地分支
* `git push origin --delete branch-name`：刪除遠端分支
* `git commit --amend --author="user-name <user-email>"`：修改最近一次 commit 的作者資訊
* `git rebase --abort`: 放棄剛才的 rebase
```
git checkout origin
git rebase sysprog21/master
// 處理未 commit 的檔案
git stash
git rebase jserv/main
git stash pop
git push branch_name --force
// 解決衝突
git add queue.c
git rebase --continue
// 更新到本地 branch
git reset --hard 7034022c
git pull origin master
git reset --hard 7034022c
這個指令 只影響本地端（local repository），不會對遠端造成任何
影響它重設你本地目前的分支（例如 master）到某個舊的 commit。
清除你本地的修改和暫存。
git pull origin master --force
```
### 建立 Pull Request
```
git remote add upstream https://github.com/sysprog21/vcam.git
git fetch upstream
git checkout upstream/main
-----------------------------
(might need to rebase to reviewer branch if you have two PR)
git checkout -b new-branch
git add .
git commit -m "Commit message"
git push origin new-branch
----------------------------
＊ open another new branch
git fetch jserv main
git branch -D Fix_verify.sh_typo
git checkout -b Fix_verify.sh_typo jserv/main
# (edit scripts/verify.sh)
git add scripts/verify.sh
git commit -m "Fix verify.sh typo and refine comments"
git push -u origin Fix_verify.sh_typo
git checkout dynamic_MCS
```
### squash：合併 commits
```
// 查commit歷史
git log --oneline
// 合併最新的n個commits
git rebase -i HEAD~n
將除了第一行外的 pick 改成 s
// 從某個commit
git rebase -i x3y4z5w // 想合併的最早那個commit的上一個
將要合併的的 pick 改成 s
// 修改前一次 commit
直接改檔案
git add
git commit --amend
git push origin branch_name --force
```
### edit：編輯 commit
```
// 查 commit 歷史
git log --oneline
// 修改倒數第 n 個 commit
git rebase -i HEAD~n
將要修改的 pick 改成 e
直接改檔案
git commit --amend
git rebase --continue
git push origin branch_name --force
```
Sign in with Wallet
Connect another wallet