2025q1 Homework1 (lab0)

contributed by < DeanXu2357 >

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
避免使用不必要的 emoji 字元

開發環境

poyu@fedora41:~/Linux_2025/lab0-c$ gcc --version
gcc (GCC) 14.2.1 20250110 (Red Hat 14.2.1-7)
Copyright (C) 2024 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.

poyu@fedora41:~/Linux_2025/lab0-c$ 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):                   32
  On-line CPU(s) list:    0-31
Vendor ID:                AuthenticAMD
  Model name:             AMD Ryzen 9 9950X 16-Core Processor
    CPU family:           26
    Model:                68
    Thread(s) per core:   2
    Core(s) per socket:   16
    Socket(s):            1
    Stepping:             0
    Frequency boost:      enabled
    CPU(s) scaling MHz:   57%
    CPU max MHz:          5752.0000
    CPU min MHz:          600.0000
    BogoMIPS:             8583.30
    Flags:                fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext fxsr_opt pdpe
                          1gb rdtscp lm constant_tsc rep_good amd_lbr_v2 nopl xtopology nonstop_tsc cpuid extd_apicid aperfmperf rapl pni pclmulqdq monitor ss
                          se3 fma cx16 sse4_1 sse4_2 movbe popcnt aes xsave avx f16c rdrand lahf_lm cmp_legacy svm extapic cr8_legacy abm sse4a misalignsse 3d
                          nowprefetch osvw ibs skinit wdt tce topoext perfctr_core perfctr_nb bpext perfctr_llc mwaitx cpb cat_l3 cdp_l3 hw_pstate ssbd mba pe
                          rfmon_v2 ibrs ibpb stibp ibrs_enhanced vmmcall fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid cqm rdt_a avx512f avx512dq rdsee
                          d adx smap avx512ifma clflushopt clwb avx512cd sha_ni avx512bw avx512vl xsaveopt xsavec xgetbv1 xsaves cqm_llc cqm_occup_llc cqm_mbm
                          _total cqm_mbm_local user_shstk avx_vnni avx512_bf16 clzero irperf xsaveerptr rdpru wbnoinvd cppc arat npt lbrv svm_lock nrip_save t
                          sc_scale vmcb_clean flushbyasid decodeassists pausefilter pfthreshold v_vmsave_vmload vgif v_spec_ctrl vnmi avx512vbmi umip pku ospk
                          e avx512_vbmi2 gfni vaes vpclmulqdq avx512_vnni avx512_bitalg avx512_vpopcntdq rdpid bus_lock_detect movdiri movdir64b overflow_reco
                          v succor smca fsrm avx512_vp2intersect flush_l1d amd_lbr_pmc_freeze
Virtualization features:  
  Virtualization:         AMD-V
Caches (sum of all):      
  L1d:                    768 KiB (16 instances)
  L1i:                    512 KiB (16 instances)
  L2:                     16 MiB (16 instances)
  L3:                     64 MiB (2 instances)
NUMA:                     
  NUMA node(s):           1
  NUMA node0 CPU(s):      0-31
Vulnerabilities:          
  Gather data sampling:   Not affected
  Itlb multihit:          Not affected
  L1tf:                   Not affected
  Mds:                    Not affected
  Meltdown:               Not affected
  Mmio stale data:        Not affected
  Reg file data sampling: Not affected
  Retbleed:               Not affected
  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; Enhanced / Automatic IBRS; IBPB conditional; STIBP always-on; RSB filling; PBRSB-eIBRS Not affected; BHI Not affected
  Srbds:                  Not affected
  Tsx async abort:        Not affected

執行＆測試

根據上課內容，執行 make check 和 make test 可以編譯和執行簡單測試或是完整評分測試。
在 Makefile 中找到相對應區塊

check: qtest
	./$< -v 3 -f traces/trace-eg.cmd

根據 qtest 執行檔說明

poyu@fedora41:~/Linux_2025/lab0-c$ ./qtest --help
./qtest: invalid option -- '-'
Unknown option '?'
Usage: ./qtest [-h] [-f IFILE][-v VLEVEL][-l LFILE]
        -h         Print this information
        -f IFILE   Read commands from IFILE
        -v VLEVEL  Set verbosity level
        -l LFILE   Echo results to LFILE

-v 3: 設置詳細程度（verbosity level）為 3，控制輸出信息的詳細程度
-f traces/trace-eg.cmd: 指定從 traces/trace-eg.cmd 文件讀取命令

所以我們可以直接執行指定測試

./qtest -v 3 -f ./traces/trace-17-complexity.cmd

q_free

根據題目要求釋放所有 queue 佔用的儲存空間，但題目並未明確指出是否需要釋放傳入的 head 指標。經執行 make test 測試後，我確認必須釋放 head 指標，否則測試程式會檢測到仍有記憶體佔用而導致測試失敗。

在執行 free(head) 後，我考慮是否應該將 head 指向 NULL 以防止錯誤使用已釋放的指標。但由於傳入參數類型是 struct list_head *，這表示函式內的 head 只是傳入指標的複本。在函式內將此複本指向 NULL 並不會改變原始傳入指標的指向。若要實現這一功能，函式介面應改為接收指標的指標，即 struct list_head **。
最後，在 qtest.c 中函式的實際使用情況顯示，所有傳給 q_free 的指標都來自 queue_context_t 結構的 q 成員。檢視使用 q_free 的三個程式碼段落，可以確認不會出現上述的問題。

觀察 queue_context_t 的釋放相關程式碼後，我發現將釋放操作包裝在一個專門處理 queue_context_t 的介面中會更為合理。然而，這三段使用 q_free 的程式碼並非完全相同，推測這可能是為了配合 qtest.c 輸出測試結果的邏輯，因此不進行封裝反而更容易實現所需功能。

q_reverse

最一開始我採用 list_for_each_safe 迴圈取出節點後逐一 list_add 加到列表最前面，已達成反轉效果。
但是 list_for_each_safe 的註解

Iterates over a circular doubly-linked list, starting from the first node
after @head and continuing until reaching @head again. This macro allows
safe removal of the current node (@node) during iteration by pre-fetching
the next node into @safe. Other modifications to the list structure (e.g.,
adding nodes or altering @head) may result in undefined behavior.

指出不應該對 @head 新增或是變更節點，以防止未定義行為。
雖然知道 list_for_each_safe 的實作，我的作法可以正確執行，但是為了符合註解指示，所以改為使用臨時鏈結串列複製原 head 變數的串列內容後，迴圈逐步加到 head 開頭。

q_insert_head

在 trace-17-complexity.cmd 中的測試不過，錯誤訊息為
ERROR: Probably not constant time or wrong implementation

嘗試過使用 strlen 計算長度後 strncpy 或 memcpy 都沒辦法達成常數時間。