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

### Reviewed by `SimonLiu423`
1. Commit [fc06cb9](https://github.com/jouae/lab0-c/commit/fc06cb91e7852b07d289f9904a169aa28eee04b7) 中同時修改了 `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](#console.c) 中使用 `printf()` 去進行 debug，建議可以利用 **GDB** 在程式中插入 breakpoint ，並在執行期間透過 `p` 輸出資訊方便偵錯。

### Reviewed by `NeedToDebugMyLife`
1. Commit [fc06cb9](https://github.com/jouae/lab0-c/commit/fc06cb91e7852b07d289f9904a169aa28eee04b7) 中實作了多個函式，包含 `q_new`、 `q_free`、 `q_insert_head`、`q_insert_tail` 以及 `q_size`。這會讓commit message 的閱讀難度變高，建議將此 commit 針對函式的功能性做細部的分割。
2. commit message 內的說明並沒有包含 `q_size` 的實作方式

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

## 開發環境

$ 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)](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-a)
- [ ] []

## 實作 queue.[ch]
### q_new
> commit [fc06cb9](https://github.com/jouae/lab0-c/commit/fc06cb91e7852b07d289f9904a169aa28eee04b7)

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

**配置記憶體**
使用 `malloc` 配置記憶體，查閱 [malloc(3) — Linux manual page](https://man7.org/linux/man-pages/man3/free.3.html) 摘要如下：
>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**

digraph INIT_LIST_HEAD {
    rankdir=LR;
    node [shape=record, style=filled, fillcolor=lightgray];
    
    head [label="{ head } | { <prev> prev | <next> next }", fillcolor=lightblue];

    head:prev -> head [tailport=sw  headport=n];
    head:next -> head [tailport=se  headport=n];
}

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

第 3 點，參考 [weihsinyeh](https://hackmd.io/@weihsinyeh/SJUVTnEn6#q_new) 紀錄
>**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](https://github.com/jouae/lab0-c/commit/fc06cb91e7852b07d289f9904a169aa28eee04b7)
<!-- [你所不知道的C語言：Stream I/O, EOF 和例外處理](https://www.youtube.com/watch?v=6BUlahVE6FE&t=10230s) -->

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

在 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Linked-list-%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC) 一文中，指示出自定義結構體只要加入`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` 可能會因為被其他行程修改或釋放，所以需要藉由複製一份同樣的資料至另一段記憶體，並用這個被複製的資料進行插入操作。
<!-- 與 [你所不知道的C語言：Stream I/O, EOF 和例外處理](https://www.youtube.com/watch?v=6BUlahVE6FE&t=10230s)，fork 跟 pipe 的處理機制很相似 -->

**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’’.

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

### q_free
> commit [fc06cb9](https://github.com/jouae/lab0-c/commit/fc06cb91e7852b07d289f9904a169aa28eee04b7)

### 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](https://man7.org/linux/man-pages/man3/free.3.html) 說明，所配置的記憶體都是未初始化。

隨後藉由指向命令列輸入的指標 `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](https://man7.org/linux/man-pages/man3/strlen.3.html) 說明
>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](https://github.com/sysprog21/lab0-c/pull/234/commits/d5f0495df0418ef631022ce51cb45dd3579eb289)

## 測試程式
<!-- [你所不知道的C語言：Stream I/O, EOF 和例外處理](https://youtu.be/6BUlahVE6FE?si=2xoGvF6lnxONfMiL&t=4119) 1:08:24 處，開始講述「狀態」。 -->