2025q1 Homework1 (lab0)

contributed by < eastWillow >

作業書寫規範:

• 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
• 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
• 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
• 不要在筆記內加入 [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 字元

開發環境

$ uname -a
Linux jens 6.8.0-52-generic #53~22.04.1-Ubuntu SMP PREEMPT_DYNAMIC Wed Jan 15 19:18:46 UTC 2 x86_64 x86_64 x86_64 GNU/Linux

$ 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:          48 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   16
  On-line CPU(s) list:    0-15
Vendor ID:                AuthenticAMD
  Model name:             AMD Ryzen 7 7800X3D 8-Core Processor
    CPU family:           25
    Model:                97
    Thread(s) per core:   2
    Core(s) per socket:   8
    Socket(s):            1
    Stepping:             2
    CPU max MHz:          5050.0000
    CPU min MHz:          545.0000
    BogoMIPS:             8399.99

閱讀 driver.py 了解成績標準

針對執行順序與檢查的項目來寫作業，要把時間花在刀口上，卡超過2 天就參考同學的寫法
單獨執行檢查分數的指令scripts/driver.py -c

trace-01-ops.cmd

q_new

commit 1acccae

參考第一周作業

q_insert_head

commit c01a625

發現 string.h 當中原來有 strdup 可以直接使用
練習都使用 $ man strdup 當記憶體無法成功配置的時候會回傳 NULL
根據前面的作業練習，要考慮這些fail 的情境
因為還有發現malloc 失敗的比例是可以設定的，代表這件事情很重要，先放在心上

q_remove_head

commit 96d8835

想了一陣子發現一個關鍵第一個節點當作head ，必須是第二個節點以後才能使用list_entry

附上Debug 用的表達式
(element_t*)((char*)head->next - (sizeof(element_t) - sizeof(struct list_head)))

q_free

隱藏關卡，這一題沒有寫qtest 會跳錯誤
ERROR: Freed queue, but 1 blocks are still allocated

q_insert_tail (do_it)

參考 q_insert_head

q_size

trace-02-ops.cmd

q_remove_tail (do_rt)

參考 q_remove_head, 因為是circular linkage list, 直接使用 head->prev

q_delete_mid (do_dm)

[n / 2]th node from the start using 0-based indexing

驗算一下公式

$$\begin{array}{rl}{i}_{m}iddle& =\frac{n_{size}}{2}\\ [0,1],n_{size}=2,i& =1,\text{result is}[1]\\ [0,1,2,3,4],n_{size}=5,i& =2,\text{result is}[2]\\ [0,1,2,3],n_{size}=4,i& =2,\text{result is}[2]\end{array}$$

trace-03-ops.cmd

q_sort (do_sort)

$ man strcmp

strcmp, strncmp - compare two strings
int strcmp(const char *s1, const char *s2);
• 0, if the s1 and s2 are equal;
• a negative value if s1 is less than s2;
• a positive value if s1 is greater than s2.

descending order is : 5, 4, 3, 2, 1

排列演算法先直接使用第一周作業
2025 年春季「Linux 核心設計」第 1 週測驗題
附上當時寫隨堂測驗的心得 第一週: 誠實面對自己

q_merge (do_merge)

這裡傳入的list_head *head 是 &chain.head，所以看物件的角度要換成chain
(queue_contex_t*)((char*)head->next - (sizeof(queue_contex_t) - sizeof(struct queue_chain_t)))

queue_contex_t *node = list_entry(head->next, queue_contex_t, chain);
拿到第一個queue

list_is_singular(&node->chain) 才是代表第一個queue 的head_list *head

參考 2025 年 Linux 核心設計課程作業 —— lab0 (E)
你所不知道的 C 語言: linked list 和非連續記憶體
參考 Linux 核心原始程式碼的 lib/list_sort.c 當中的Merge
需要注意 sort stability 排序的穩定與不穩定

因為卡住超過三天，研究一下其他同學的寫法

https://hackmd.io/@Charlie1123/linux2025-homework1 merge 的寫法最接近教材

取得第一個 a list
(element_t*)((char*)a->next - (sizeof(element_t) - sizeof(struct list_head)))

取得第二個 b list
(element_t*)((char*)b->next - (sizeof(element_t) - sizeof(struct list_head)))

(gdb) lanuch trace-03-ops.cmd

如果有人想要使用vscode + gdb 可以參考以下這一部的設定，剩下使用vscode 的預設就可以了

"program": "${workspaceFolder}/qtest",
"args": [
    "-v",
    "3",
    "-f",
    "traces/trace-03-ops.cmd"
],
"cwd": "${workspaceFolder}",

q_reverse (do_reverse)

trace-04-ops.cmd

q_swap

trace-05-ops.cmd

trace-06-ops.cmd

q_delete_dup

q_descend

q_reverseK

代辦

Malloc failure probability percent

重購

改用 list_is_singular

sort stability

研讀 Linux 核心原始程式碼的 lib/list_sort.c

研讀論文〈Dude, is my code constant time?〉

指出lab0的缺陷或者可改進之處

開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤

運用 Valgrind 排除 qtest 實作的記憶體錯誤

研讀 2025 年 Linux 核心設計課程作業 —— lab0 (E)