2025q1 Homework1 (lab0)

contributed by < jouae >

Reviewed by SimonLiu423

1. Commit fc06cb9 中同時修改了 q_new, q_free, q_insert_*, q_size 函式，然而這幾個函式並沒有都彼此相關，全部放在同個 commit 容易造成閱讀的人混淆，建議將 commit 細拆成更多個，例如：

   • q_new, q_free: 與 queue 配置、釋放相關的放一個 commit
   • q_insert_*: 與新增元素至 queue 相關的放一個 commit
   • q_size: 獨自一個 commit

   此外，commit message 中有提到 malloc 的 reference, 建議可以直接將連結放在 commit message 的末端： Link: <...>，確保讀者跟你看的 refenrece 是同一個。

2. 對於 queue.[ch] 實作的說明，建議可以貼出部分程式碼好讓讀者知道你在指哪段程式碼，例如在 q_remove_head, q_remove_tail：

   …所以需要先判定佇列是否為空佇列

   這裡可以貼上判斷是否佇列為空的程式碼

3. 你在 console.c 中使用 printf() 去進行 debug，建議可以利用 GDB 在程式中插入 breakpoint ，並在執行期間透過 p 輸出資訊方便偵錯。

Reviewed by NeedToDebugMyLife

1. Commit fc06cb9 中實作了多個函式，包含 q_new、 q_free、 q_insert_head、q_insert_tail 以及 q_size。這會讓commit message 的閱讀難度變高，建議將此 commit 針對函式的功能性做細部的分割。
2. commit message 內的說明並沒有包含 q_size 的實作方式

作業書寫規範:

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

開發環境

$ gcc --version
gcc (Ubuntu 12.3.0-1ubuntu1~22.04) 12.3.0
Copyright (C) 2022 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:          48 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   6
  On-line CPU(s) list:    0-5
Vendor ID:                AuthenticAMD
  Model name:             AMD Ryzen 5 4500U with Radeon Graphics
    CPU family:           23
    Model:                96
    Thread(s) per core:   1
    Core(s) per socket:   6
    Socket(s):            1
    Stepping:             1
    Frequency boost:      enabled
    CPU max MHz:          2375.0000
    CPU min MHz:          1400.0000
    BogoMIPS:             4741.49
    Flags:                ......
Caches (sum of all):      
  L1d:                    192 KiB (6 instances)
  L1i:                    192 KiB (6 instances)
  L2:                     3 MiB (6 instances)
  L3:                     8 MiB (2 instances)

教材閱讀紀錄

lab0-c

• 2025 年 Linux 核心設計課程作業 —— lab0 (A)
• []

實作 queue.[ch]

q_new

commit fc06cb9

q_new 作用為建立一個空的環狀佇列，對應 q_test 中的 new 指令，多個環狀佇列之間會以環狀鏈結串列串連在一起，並能夠藉由 prev 及 next 指令切換對應當前環狀佇列的前一及後一環狀佇列。

配置記憶體
使用 malloc 配置記憶體，查閱 malloc(3) — Linux manual page 摘要如下：

1. The memory is not initialized.
2. On error, these functions return NULL.
3. When malloc() returns non-NULL there is no guarantee that the memory really is available. In case it turns out that the system is out of memory, one or more processes will be killed by the Out-Of-Memory(OOM) killer.

第 1 點，藉由 INIT_LIST_HEAD 將被配置的 list_head 結構體中的 prev 及 next 指向自己本身，以達到初始化記憶體的目的。

INIT_LIST_HEAD

第 2 點，藉由判斷回傳值是否為 NULL ，當判定出 NULL 時， q_new 回傳 NULL 。

第 3 點，參考 weihsinyeh 紀錄

C99 Standard (§ 7.20.3 (28))
If the space cannot be allocated, a null pointer is returned. If the size of the space requested is zero, the behavior is implementation defined: either a null pointer is returned, or the behavior is as if the size were some nonzero value, except that the returned pointer shall not be used to access an object.

配合第 1 點，利用 INIT_LIST_HEAD ，立即利用被配置的 list_head ，指向自己本身，除了初始化記憶體的目的外，還能確保這個記憶體是確實能使用的。

q_insert_head, q_insert_tail

commit fc06cb9

將 char 型態所指向的 s 資料插入至佇列的頭或是尾。

在 你所不知道的 C 語言: linked list 和非連續記憶體 一文中，指示出自定義結構體只要加入struct list_head 即可利用 Linux 提供的一系列 API 操作。在 lab0 中也是， element_t 結構體包含 list_head list 用於作為環狀鏈結串列的結點，所以對於佇列中任一元素皆可以利用 list.h 中提供的 API 根據 list_head list 對佇列元素進行修改、新增、釋放等操作。

因此，對於待插入元素 s ，我們可以改使用包含待插入字串及 list_head 的 element_t 結構體來進行插入操作。

能不能直接將 element_t->value 直接指向 s 記憶體位置？結論是不行，因為 s 可能會因為被其他行程修改或釋放，所以需要藉由複製一份同樣的資料至另一段記憶體，並用這個被複製的資料進行插入操作。

list_add
list_add(*node, *head) 的功用是將 *node 待新增元素佇列 *head

C99 Standard (§ 6.5.3.2 (3))
The unary & operator yields the address of its operand. If the operand has type ‘‘type’’ , the result has type ‘‘pointer to type’’.

區分「命令」(command) 和「指令」(instruction)，本例是「命令」

q_free

commit fc06cb9

q_remove_head, q_remove_tail

如果直接對空佇列使用 rh 或 rt 會導致

l = []
cmd> rh
Warning: Calling remove head on empty queue
Segmentation fault occurred.  You dereferenced a NULL or invalid pointerAborted

所以需要先判定佇列是否為空佇列

console.c

執行 ih 命令時，參數輸入加入多個空格在欲輸入字串前，會導致非預期結果，如下：

cmd> new
l = []
cmd> ih        1
l = [1V]

查看 qtest.c 中 ih 命令是藉由呼叫函式 do_ih ，在此我簡易的使用 printf 輸出 argv ，先確認參數輸入是否正確

static bool do_ih(int argc, char *argv[])
{
+    for(int i = 0; i<argc; i++)
+        printf("str: %s\n", argv[i]);
    return queue_insert(POS_HEAD, argc, argv);
}

再次執行 ./qtest 及 new 和 ih 命令得到：

cmd> new
l = []
cmd> ih              1
str: ih
str: 1cU
l = [1cU]

可以初步排除錯誤並非在插入時產生，而是在讀取輸入參數時產生錯誤。console.c 中，讀取參數的函式為 **parse_args，其作用是解析本機終端命令列輸入的字串，先藉由 report.c 中 malloc_or_fail 配置一段大小與命令列輸入字串一致的記憶體，根據 malloc(3) — Linux manual page 說明，所配置的記憶體都是未初始化。

隨後藉由指向命令列輸入的指標 src 和 skipping 判定是否為連續字元，並使用 *dst 修改 buf 記憶體地址的值。

修改完 buf 中的值後藉由以下程式碼，進行字串複製：

    src = buf;
    for (int i = 0; i < argc; i++) {
        argv[i] = strsave_or_fail(src, "parse_args");
        src += strlen(argv[i]) + 1;
    }

argv 是藉由 strsave_or_fail 中複製 src 指向的記憶體內容，透過 strncpy 將長度 len 的記憶體地址複製，其中，len 透過 strlen 獲得，根據 strlen(3) — Linux manual page 說明

The strlen() function calculates the length of the string pointed to by s, excluding the terminating null byte ('\0').

得知 strlen 不包含 null-terminated 字元，為了更詳細的得知當 \0 不在字串末時，strlen 是多少，使用以下片段程式碼確認：

char s[] = {'h','i','\0','t','h','e','r','e'};
size_t len = strlen(s); // len is 2

在此確認了非預期輸出的原因是， buf 在配置記憶體時，由於未初始化記憶體地址的值，以至於 strlen 得到非實際參數的長度，例如上述 1cU。

解決方式是在 while ((c = *src++) != '\0') 後補上 *dst++ = '\0'

while ((c = *src++) != '\0') {
...
}
+ *dst++ = '\0';

commit d5f0495

測試程式