# 2025q1 Homework1 (lab0)
contributed by < horseface1110 >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 40 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 1
On-line CPU(s) list: 0
Vendor ID: GenuineIntel
Model name: QEMU Virtual CPU version 2.5+
CPU family: 15
Model: 107
Thread(s) per core: 1
Core(s) per socket: 1
Socket(s): 1
Stepping: 1
BogoMIPS: 5199.99
Flags: fpu de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 syscall nx lm constant_tsc nopl xtopo
logy cpuid tsc_known_freq pni ssse3 cx16 sse4_1 sse4_2 x2apic popcnt aes hypervisor lahf_lm cpuid_fault pti
Virtualization features:
Hypervisor vendor: KVM
Virtualization type: full
Caches (sum of all):
L1d: 32 KiB (1 instance)
L1i: 32 KiB (1 instance)
L2: 4 MiB (1 instance)
L3: 16 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0
Vulnerabilities:
Itlb multihit: KVM: Mitigation: VMX unsupported
L1tf: Mitigation; PTE Inversion
Mds: Vulnerable: Clear CPU buffers attempted, no microcode; SMT Host state unknown
Meltdown: Mitigation; PTI
Spec store bypass: Vulnerable
Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointer sanitization
Spectre v2: Mitigation; Retpolines, STIBP disabled, RSB filling
Srbds: Not affected
Tsx async abort: Not affected
```
## 針對佇列操作的程式碼實作
### q_free
commit：[76f27e2](https://github.com/sysprog21/lab0-c/commit/76f27e2834f589f6c46d67be7e3c2fa6a53e6b9d)
```
/* Free all storage used by queue */
void q_free(struct list_head *head) {
element_t *entry, *safe;
list_for_each_entry_safe(entry, safe, head, list) {
if (entry->value) {
free(entry->value);
}
free(entry);
}
free(head);
}
```
發現list.h有一個function：`q_release_element`，之前忘記檢查head是否為空，新增
```
if (!head || list_empty(head)) {
free(head);
return;
}
```
### q_insert_head
commit：[9359749](https://github.com/sysprog21/lab0-c/commit/93597492d1b9f8639a0091b3f011c70766224e54)
一開始的用list_empty()檢查是否為空，新分配空間後，再檢查是否有成功分配，最後用`list_add`添加節點在頭部。
但發現無法正確執行插入，我想是沒有檢查是否成功放入值到新的節點
所以新增了檢查的函式。
```
if (!new->value) {
free(new);
return false;
}
```
### q_remove_head
commit：[f8f5cf2](https://github.com/sysprog21/lab0-c/commit/f8f5cf25ba8741465e907e812a2bb83cd3bb4e7b)
- 實作細節：
移除並返回鏈結串列的第一個節點（head->next）。
若提供了 sp，則將該節點的 value 字串複製到 sp 中。
- 問題：一開始看不懂sp要做什麼
### q_insert_tail、q_remove_tail
commit：[c2cd219](https://github.com/sysprog21/lab0-c/commit/c2cd219d940afd8ab9cddc914ab43fd131676b20)
inser_tail跟remove_tail是一起做的
- 功能描述：
- q_remove_head() 與 q_remove_tail() 分別負責從雙向循環鏈結串列的頭部與尾部移除元素。若有提供 sp 緩衝區，則會將被移除節點的字串值安全地複製至 sp。
- 實作細節：
- 空串列檢查：在移除前，會先檢查鏈結串列是否為空，避免對空串列進行操作。
- 字串值複製：若提供了 sp 且節點的值不為空，會使用安全的字串複製方式，確保不會超出緩衝區大小，並保證字串結尾為 '\0'。
- 移除節點：透過 list_del() 將目標節點從鏈結串列中移除，並確保鏈結結構的正確性。
- 節點返回：函式會返回已移除的節點指標，供外部進行記憶體釋放或後續處理。
### q_delete_mid
Commit：[6f51bb3](https://github.com/sysprog21/lab0-c/commit/6f51bb31b5a9e45a41f8281bde408805e51a1983)
- 實作細節：
- 功能：刪除雙向循環鏈結串列中的中間節點，成功返回 true，否則返回 false。
- 檢查 head 是否為空或空串列。
- 使用快慢指標找到中間節點。
- 移除節點並釋放 value 和節點記憶體。
邏輯重點：偶數個節點的話，是刪除正中間的下一個，一開始寫錯，會抓到前一個
### q_sort
commit：[f2e792f](https://github.com/sysprog21/lab0-c/commit/f2e792f1c98351971ed9fdbf005a8021bc9564ec)
- 會用到q_size......
- 實作細節：
這段程式碼實作了雙向循環鏈結串列的歸併排序，主要包含以下函式：
- compare()
比較兩個節點的值，根據 descend 判斷排序方向（遞減或遞增）。
- merge()
合併兩個已排序的鏈結串列，並維持 prev 和 next 的正確連接，最後恢復循環結構。
- q_merge_two_lists()
使用遞迴將鏈結串列分割為左右兩部分，分別排序後再合併。
- q_sort()
主排序函式，檢查特殊情況、暫時斷開循環、執行遞迴排序，最後恢復循環鏈結。
重點：確保每次分割與合併後，鏈結串列的 prev 和 next 指標正確，避免結構損壞或無窮遞迴。
- 遇到的問題：
- 起初的compare function沒有固定好回傳ture / false分別代表什麼，後來大改。
- q_merge_two_lists()一開始沒有做好分割串列，導致分割後的串列仍舊相連，在執行時出現無窮迴圈
- merge()：邏輯錯誤，導致出現segmentation fault，最後使用pointer to pointer編寫。
- 最大的問題！！即使沒有呼叫q_size()，但還是會用到，我q_size()沒有先寫，
#### merge
```
struct list_head *merge(struct list_head *left, struct list_head *right, bool descend){
left->prev->next = NULL;
right->prev->next = NULL;
struct list_head *head = NULL, *ptr = head, *current = head;
/*head 是 dummy node，ptr是目前被移出的節點，current是新串列的尾巴*/
while(left && right){
if(compare(left, right, descend)){
ptr = left;
left = left->next;
list_del_init(ptr);
current->next = ptr;
ptr->prev = current;
current = current->next;
}else{
ptr = right;
right = right->next;
list_del_init(ptr);
current->next = ptr;
ptr->prev = current;
current = current->next;
}
}
if(left){
current->next = left;
}else{
current->next = right;
}
return head;
}
```
segmetation fault
### q_ascend、q_descend
Commit：[8feb2a4](https://github.com/sysprog21/lab0-c/commit/8feb2a418283fbb7128aa070ec3ad31900b83525)
- 實作細節：
- 此函式從右往左遍歷雙向循環鏈結串列，刪除右側存在更大值的節點。先檢查串列是否為空或僅有一個節點，若是則直接返回。遍歷時，從倒數第二個節點開始，max 初始化為最後一個節點。若當前節點小於 max，則刪除並釋放記憶體；否則更新 max。遍歷至 head 為止，最後返回 0 表示完成。
- 困難：
- 一開始用`current = head`並在迴圈中`current = current->prev`，不直觀，改為`head = head->prev->prev`
- 原本手刻element_t釋放節點，後來發現`q_release_element`
- 直接從倒數第二個開始檢查，若大於等於max，保留並更新max；小於max，則刪除
但會遇到
```
l = [c a d c b a]
cmd> descend
l = [ ... ]
ERROR: Queue has more than 0 elements
Freeing queue
```
更改為`return q_size(head)`即可
### q_reverse_segment
- 目標：反轉一個區間內的節點順序
- 排序：
- 先使用 q_sort() 對鏈結串列進行排序，確保相同元素相鄰，便於後續判斷重複。
- 歷與判斷：使用遍歷邏輯依序比對相鄰節點的值：
- 發現重複時，刪除該節點，並標記當前為重複狀態。
- 遇到重複結尾時，將標記為重複的起始節點刪除，確保所有重複元素被移除。
- 記憶體釋放：每次刪除節點時，確保釋放其佔用的記憶體，避免洩漏。
- 困難：因為輸入的第一個節點也是需要被反轉的，所以不能用以前的head->next邏輯當第一個節點。在這邊錯了蠻多次的
### q_reverse
直接使用q_reverseK
### q_reverseK
Commit：[853e3cd](https://github.com/sysprog21/lab0-c/commit/853e3cd174d2082e2980d5ccd6a7e7fe8e55d7c0#diff-3f6f16518a74b523b2cad7ede4d4a9c11605317dfed2905cdaf12e242ee05923L143-L167)
```diff=
- struct list_head *start = NULL, *end = NULL, *current = NULL;
+ struct list_head *start = head, *end = NULL, *current = start;
```
遇到segmentation fault
發現：index = 0 要放在 index == k 時
current會指向現在檢查到的最後一個，但 q_reverse_segment後，他指向的node不變，導致錯誤
### q_merge
q_merge一次合併兩個queue，直到全部都合併完，使用了`merge_lists_with_sentinel_node`，前半部分跟merge很像，但不用斷頭，直接用L1的頭當回傳的頭，最後把L2的頭初始化
##3 q_descend
直接從倒數第二個開始檢查，若大於等於max，保留並更新max；小於max，則刪除
但會遇到
```
l = [c a d c b a]
cmd> descend
l = [ ... ]
ERROR: Queue has more than 0 elements
Freeing queue
```
更改為`return q_size(head)`即可
### q_delete_dup
Commit：[853e3cd](https://github.com/sysprog21/lab0-c/commit/853e3cd174d2082e2980d5ccd6a7e7fe8e55d7c0)
- 實作細節：
- 排序：先使用 q_sort() 對鏈結串列進行排序，確保相同元素相鄰，便於後續判斷重複。
- 遍歷與判斷：使用遍歷邏輯依序比對相鄰節點的值：
- 發現重複時，刪除該節點，並標記當前為重複狀態。
- 遇到重複結尾時，將標記為重複的起始節點刪除，確保所有重複元素被移除。
- 記憶體釋放：每次刪除節點時，確保釋放其佔用的記憶體，避免洩漏。
- 錯誤：
```
queue.c:152:43: error: passing argument 1 of ‘strcmp’ makes pointer from integer without a cast [-Werror=int-conversion]
152 | if(*entry->value != head & strcmp(*entry->value, *safe->value) == 0){
| ^~~~~~~~~~~~~
| |
| char
```
Strcmp的參數為指標
錯誤：
```
queue.c:152:26: error: comparison between pointer and integer [-Werror]
152 | if(*entry->value != head & strcmp(*entry->value, *safe->value) == 0){
```
*entry->value 改為 entry->list.next
錯誤：
```
queue.c:161:22: error: passing argument 1 of ‘list_del’ from incompatible pointer type [-Werror=incompatible-pointer-types]
161 | list_del(entry);
| ^~~~~
| |
| element_t *
```
list_del(entry->list.next->prev);，目標：移除當下的node
最後：需要先sort才能使用
錯誤：
```
l = [b r b r b r a]
cmd>
cmd> dedup
ERROR: Duplicate strings are in queue or distinct strings are not in queue
l = [a]
Freeing queue
```
### swap
```
/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
q_reverseK(head, 2);
}
```
reverseK修好就好了
## 閱讀論文〈Dude, is my code constant time〉
### lab0 dudect程式碼的缺陷
Commit [156c254](https://github.com/horseface1110/lab0-c/commit/156c254b3d489bcc858a3b2f12d2801522826d41)
rebase後，commit 遇到問題，說是printf出壞東西
```
oloomb@oloomb:~/linux2025/tmp/tmp/lab0-c$ git commit -a
--- modified dudect/fixture.c
+++ expected coding style
@@ -75,7 +75,7 @@ static void update_statistics(const int6
/* do a t-test on the execution time */
t_push(t, difference, classes[i]);
}
-}
+}
static bool report(void)
{
[!] dudect/fixture.c does not follow the consistent coding style.
Make sure you indent as the following:
clang-format -i dudect/fixture.c
Following files were changed:
- dudect/fixture.c : 1 insertions(+), 1 deletions(-)
Running fmtscan...
No dictionary found.
[!] Check format strings for spelling
```
執行`sudo apt install wamerican`後問題解決，是他的字典
原本的diot中沒有先進行排序，就直接進入update_statistics，導致依據這些閾值裁剪的操作失準。這會使得統計上下文中 t 值、t_cropped 的數據累計出錯，進而導致最終的 t-test 結果不可靠，也就是說可能錯誤判定目標函式是否具有常數時間行為。所以我在這邊加了一個排序`prepare_percentiles(exec_times);`，但出現`segmentation fault `，我猜想問題是在使用 t_cropped 或 t_second_order 前，沒有分配及初始化它們導致的。
``` diff
static void init_once(void)
{
init_dut();
t_init(t);
+ for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) {
+ t_cropped[i] = malloc(sizeof(t_context_t));
+ if (!t_cropped[i]) die();
+ t_init(t_cropped[i]);
+ }
+ t_second_order = malloc(sizeof(t_context_t));
+ if (!t_second_order) die();
+ t_init(t_second_order);
}
```
Commit [db4bd7b](https://github.com/horseface1110/lab0-c/commit/db4bd7b4a1bf5592adfe5af3404eb5adb394183a)
雖然這樣可以通過測驗，但我心裡不踏實，因為只對`exec_time`排序，讓`exec_time`和`classes`脫鉤了。所以我改了`prepare_percentiles`，用結構保存 exec_times 與 classes 的對偶型別
```
typedef struct {
int64_t exec_time;
uint8_t cls;
} pair_t;
```
再把有效區間複製資料到 pairs 陣列，排序完後再更新原始陣列
Sign in with Wallet
Connect another wallet