# 2025q1 Homework1 (lab0)
contributed by < `DeanXu2357` >

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

## 開發環境

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` 都沒辦法達成常數時間。