2025q1 Homework1 (lab0)

contributed by < Hlunlun >

作業書寫規範:

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

開發環境

lun@lun-OMEN:~/linux2025/hw1/lab0-c$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 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.

開發步驟與工具

前置作業

安裝雙系統：安裝雙系統在有兩個 SSD 的 hp 筆電上

安裝套件

sudo apt install build-essential git-core valgrind
sudo apt install cppcheck clang-format aspell colordiff

取得程式碼與測試

git clone https://github.com/sysprog21/lab0-c

每次開發完一個函數就 commit ，紀錄開發過程

clang-format -i <file>
git add <file>
git commit -a
git push

實做佇列

`q_new`

C99 [7.20.3.3] The malloc function

The malloc function returns either a null pointer or a pointer to the allocated space

malloc 如果沒有成功配置到記憶體是有可能回傳 NULL 的，所以要檢查 malloc 要求的記憶體是否有成功
問題：但後來在 make test 後發現第 13 個 trace 無法通過

猜測這個函式可能是一定要配置到記憶體位置才是正確的，因此使用迴圈檢查記憶體配值直到成功為止，經過 Commit 4417ea0 竟然就通過測資了，但是這樣可能會造成記憶體一直不夠一直再回圈中檢查，造成整個系統異常，要在想原因是什麼
2025/03/09 不要平感覺寫程式

     struct list_head *q = malloc(sizeof(struct list_head));
-    if (q == NULL)
-        return NULL;
+    while (q == NULL)
+        q = malloc(sizeof(struct list_head));
     INIT_LIST_HEAD(q);
     return q;

`q_free`

先將 list 移除，在釋放整個節點

`q_insert_head` 、`q_insert_tail`

重點：需要更注意字串的記憶體配置
問題：原本我直接把 element->value 指向 s，如果有在其他地方有人對 s 做任何變更或是釋放記憶體，element->value 就會也跟著改變，所以應該是要用 strdup 配置新的空間給 element->value
在你不知道的C語言：指標篇中也有說到字串的生命週期有可能快結束，所以才使用 strdup

-    element->value = s;
+    element->value = strdup(s);
    if (!element->value) {
        free(element);
        return false;

那為何要判斷 element->value 是否為 NULL 呢？
可以運用 linux 的說明文件 man page，在 terminal 打上 man strdup，這時候就會看到因為在使用 strdup 時會用到 malloc，而在規格書 C99 [7.20.3.3] 中有提到 malloc 有可能因為記憶體不夠用而造成記憶體配置失敗從而回傳 NULL，所以才要檢查 element->value

The strdup() function returns a pointer to a new
string which is a duplicate of the string s. Memory
for the new string is obtained with malloc(3), and
can be freed with free(3).

`q_remove_head` 、`q_remove_tail`

重點：只要 unlinlk 就好，不用釋放記憶體，找到第一個 list_head 節點，然後 unlink
問題：copying of string in remove_head overflowed destination buffer.
原本我是直接用 bufsize 有多大就複製多大的 entry->value 到 sp ，但如果 entry->value 的長度比 bufsize 小，會有 buffer overflow detected 的錯誤
這裡就會好奇所以 strncpy 是否會自動補上 \0 ，從 man page 看到 strncpy 的實做原理，可以看到這個函式會用到 strpncpy 並且在其中會檢查 dsize 和 src 的長度，但是並沒有和 dst 比較，而這裡的 q_remove_* 會有 bufsize 的限制，所以要而外檢查 element->value 的大小，經過 commit 27965a2 即可解決這個問題
```
stpncpy(char *restrict dst, const char *restrict src, size_t dsize)
{
   size_t  dlen;
   dlen = strnlen(src, dsize);
   return memset(mempcpy(dst, src, dlen), 0, dsize - dlen);
}
```
關於可以複製多大的字串到 sp ，在 man strncpy 中，看到了 strncpy 的實做使用到 strnlen(src, dsize) ，這個函式會回傳 min(strlen(src), dsize) ，可以讓程式碼更精簡，因此做了 commit d03a3d8 的修改

     if (sp) {
-        size_t size = strlen(entry->value) < (bufsize - 1)
-                          ? strlen(entry->value)
-                          : (bufsize - 1);
-        strncpy(sp, entry->value, size);
-        sp[size] = '\0';
+        size_t dlen = strnlen(entry->value, bufsize - 1);
+        mempcpy(sp, entry->value, dlen);
+        *(sp + dlen) = 0;
     }

`q_delete_mid`

運用指標的指標技巧，找到指向 middle node 的指標，然後將它移除，只是這裡的迴圈判斷條件是 fast 和 fast->next 還沒到迭代到 head 之前，如 commit a351491

`q_delete_dup`

使用 list_for_each_entry_safe 才可以在迭代過程中移除節點

`q_swap`

先看 list_for_each_safe，所以使用這個巨集時，要 swap 的就是 node 和 safe

#define list_for_each_safe(node, safe, head)                     \
    for (node = (head)->next, safe = node->next; node != (head); \
         node = safe, safe = node->next)

參考 linux/list.h 的 swap 機制，所以應該要先將 safe 移除，在將 safe 取代 node，在將 node 放到 safe 後面

`q_reverse`

重點：利用雙向鍊結串列的特性，改變每個節點的 prev 和 next，如 commit 7203bbd

`q_reverseK`

`q_sort`

`q_ascend`

`q_descend`

`q_merge`

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

參考：坤諦江、The Linux Kernel、Risheng

`attribute`

參考 GNU 6.35.1 Common Function Attributes

其中這段有提到 nonnull function attribute 可能會用在至少有一個指標參數的函數，告訴編譯器哪幾個指標參數必為非空指標

The nonnull attribute may be applied to a function that takes at least one argument of a pointer type. It indicates that the referenced arguments must be non-null pointers. For instance, the declaration…informs the compiler that, in calls to my_memcpy, arguments dest and src must be non-null.

lib/list_sort.c 使用的函數屬性使其第 2、3、4 個參數 cmp 、a 、 b 必須為非空的指標，所以從程式碼可以間接知道 cmp 是指標，因為 __attribute__((nonnull)) 只用於限制指標參數(可以透過閱讀 nonnull function attribute 範例得出結論 )

__attribute__((nonnull(2,3,4)))
static struct list_head *merge(void *priv, list_cmp_func_t cmp,
                struct list_head *a, struct list_head *b)

仔細閱讀函數屬性在函數被觸發以及在編譯階段定義時會有不同的效果，在函數被觸發時如果在標記為 nonnull 的位置傳入 null 會觸發緊告，所以其實程式還是可以通過編譯，但是會有警告

If the compiler determines that a null pointer is passed in an argument slot marked as non-null, and the -Wnonnull option is enabled, a warning is issued.

在課堂上老師也不斷提及 linux kernel 是牽一髮而動全身的，所以開發者必須更謹慎小心，而 __attribute__ 就是一種警告機制，把控傳參數這樣的細節

`list_cmp_func_t cmp`

解釋函數屬性時提及 cmp 是一個指標，其型態定義於 linux/list_sort.h ，將整數定義為一個指標函數 (pointer to function) ，或者可以解釋為這是一個會回傳整數的指標函數

typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *,
        const struct list_head *, const struct list_head *);

為何不直接使用它原本的整數型態，還特別定義為指標函數呢？

透過程式中的註解解釋 cmp，此函數用於比較當前節點的數值，

 The comparison function @cmp must return > 0 if @a should sort after
 @b ("@a > @b" if you want an ascending sort), and <= 0 if @a should
 sort before @b *or* their original order should be preserved.  It is
 always called with the element that came first in the input in @a,
 and list_sort is a stable sort, so it is not necessary to distinguish
 the @a < @b and @a == @b cases.

`merge`

運用到指標的指標技巧，進行兩個雙向鍊結串列的合併，並沒有去修改 prev 指標指向的節點，舉例以下 a 和 b 可能的樣貌，且最後一個節點都會是 NULL ，原因可以看到 merge_final 的解釋內容

經過 merge 函數後，會呈現以下，也就是說只有將 next 指標指向對的節點，prev 指標依舊，也就是說按照 next 指標走，排列的順序是正確的

`merge_final`

首先看到函數定義可知，參數中 cmp 、head 、a 、b 必不為空指標

__attribute__((nonnull(2,3,4,5)))
static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
            struct list_head *a, struct list_head *b)

head 在 list_sort 中作為呼叫 merge_final 的引數，可以知道 head 是一個雙向鍊結串列的第一個節點，而在 merge_final 中 a 和 b 會有序的排列在 head 之後。

此處也可解釋為何在 merge 在過程中 a 和 b 明明是雙向鍊結串列的型態 list_head 結構中卻有 NULL ，因為以下程式碼第 11 行將 head->prev 這個節點的 next 指標指向 NULL ，也就是原本指向 head 的 head->prev->next 指標，現在指向 NULL ( 這跟直接將 head 設置為 NULL 還是差別的！所以 head 依然存在並未變成 NULL )，所以才可以用跟合併單向鍊結串列一樣的判斷條件是迭代直至 NULL

















__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
    struct list_head *list = head->next, *pending = NULL;
    size_t count = 0;	/* Count of pending */

    if (list == head->prev)	/* Zero or one elements */
        return;

    /* Convert to a null-terminated singly-linked list. */
    head->prev->next = NULL;

        ...

    /* The final merge, rebuilding prev links */
    merge_final(priv, cmp, head, pending, list);
}

看完第 55 到到第 74 行的程式碼可以知道 merge_final 和 merge 作法大致相同，也就是會比較 a 和 b 這兩個雙向鍊結串列並且做合併，但是 merge_final 有調整每個節點的 prev 指標

for (;;) {
    /* if equal, take 'a' -- important for sort stability */
    if (cmp(priv, a, b) <= 0) {
        tail->next = a;
        a->prev = tail;
        tail = a;
        a = a->next;
        if (!a)
            break;
    } else {
        tail->next = b;
        b->prev = tail;
        tail = b;
        b = b->next;
        if (!b) {
            b = a;
            break;
        }
    }
}

若是兩個鍊結串列不是平衡的，代表只有將其中一個鍊結串列走完並排列到 head 後面，需要繼續處理另一個鍊結串列，以下程式碼即是處理此情況

/* Finish linking remainder of list b on to tail */
tail->next = b;
do {
    /*
     * If the merge is highly unbalanced (e.g. the input is
     * already sorted), this loop may run many iterations.
     * Continue callbacks to the client even though no
     * element comparison is needed, so the client's cmp()
     * routine can invoke cond_resched() periodically.
     */
    if (unlikely(!++count))
        cmp(priv, b, b);
    b->prev = tail;
    tail = b;
    b = b->next;
} while (b);

/* And the final links to make a circular doubly-linked list */
tail->next = head;
head->prev = tail;

`unlikely` 、 `likely`

參考 likely() and unlikely()

定義於 linux/compiler.h ，使用到 GCC 內建函式 __builtin_expect (long exp, long c) 如下

# define likely(x)	__builtin_expect(!!(x), 1)
# define unlikely(x)	__builtin_expect(!!(x), 0)

關於 __builtin_expect(long exp, long c) 的描述如下，此內建函數會提供編譯器分支預測的資訊，此處分支 branch 指程式中的能夠改變執行指令順序的如 if-else 和 switch 的條件表達式，這種功能可以避免指令跳轉從而優化程式執行過程

You may use __builtin_expect to provide the compiler with branch prediction information…

其運作方式如字面上 expect 的含意，編譯器會預期 exp 的數值結果是 c，回傳值會是 exp 的運算結果

The return value is the value of exp, which should be an integral expression. The semantics of the built-in are that it is expected that exp == c.

嘗試以下程式碼印出 __builtin_expect 的值，就是 exp 本身，此函數並不會影響 exp 本身，

#include<stdio.h>
int main(){
	int a = 10;
	printf("%ld\n", __builtin_expect(a, 1)); // 10
	printf("%ld\n", __builtin_expect(a==10, 0)); // 1
}

所以，__builtin_expect(!!(x), 1) 代表預期布林值 !!(x) 是對的，即希望執行 likely 這個分支；反之 __builtin_expect(!!(x), 0) 則代表預期布林值 !!(x) 是錯的，即不希望執行 unlikely 這個分支。透過預期 exp 發生的機率高低讓編譯器可以提早預測是否按照順序執行程式碼或是需要執行會降低效能的跳轉指令。

`list_sort`

此處一樣有限制第 2 和 3 個參數須不為空的指標

__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)

其參數定義如下，head 即 list_sort 要進行排序的雙向鍊結串列， cmp 則為的用於比較的函數

@priv: private data, opaque to list_sort(), passed to @cmp
@head: the list to sort
@cmp: the elements comparison function

參考 RinHizakura 中解釋 [RESEND PATCH v2 5/5] lib/list_sort: Optimize number of calls to comparison function

開頭解釋由於 CONFIG_RETPOLINE 降低了呼叫間接函數的表現，所以應該要減少使用間接函數如用來比較的 cmp() 函數，這也就是為什麼 list_sort 的合併排列中兩個序列長度需要以 2:1 的比例進行，因為此方式可以減少比較的次數，也就減少了調用 cmp() 而降低了系統的性能情況發生。

CONFIG_RETPOLINE has severely degraded indirect function call performance, so it's worth putting some effort into reducing the number of times cmp() is called.

這段程式碼改變了以前是用 Bottom-up mergesort 的方式(以下為前版本描述)，可以參考 patch 中提供的文獻：Bottom-up mergesort – A detailed analysis，比較特別的是這篇論文是一個經濟系和數學系的專家寫的，他們推導出可以表達 bottom-up mergesort 過程中做比較次數的表示式，並與 top-down 進行分析，並且得出結論雖然 top-down mergesort 的複雜度可能更低，但是它伴隨著需要先知道排列個數的限制，我想這也是為什麼以前是用 bottom-up 現在優化也不選擇 top-down 的原因

- * This function implements a bottom-up merge sort, which has O(nlog(n))
- * complexity.  We use depth-first order to take advantage of cacheing.
- * (E.g. when we get to the fourth element, we immediately merge the
- * first two 2-element lists.)

且合併排列的比例盡可能要是 2:1

兩個鍊結串列都是
$2^{k}$ ，所以合併後就是
$2^{k + 1}$
後續至少還有
$2^{k}$ 個元素
所以，合併過程中要同時處理的元素總數就是

$2^{k + 1} + 2^{k} = 2 \cdot 2^{k} + 2^{k} = 3 \cdot 2^{k}$

+ * This mergesort is as eager as possible while always performing at least
+ * 2:1 balanced merges.  Given two pending sublists of size 2^k, they are
+ * merged to a size-2^(k+1) list as soon as we have 2^k following elements.

cache thrashing 快取抖動：重複存取不在快取中的資料，導致快取不斷被替換，造成性能下降。

這邊有解釋到，因為這樣可以防止 cache thrashing，由於 CPU 的 cache 快取存取速度由快到慢分別為 L1, L2, L3，所以如果 CPU 要存取資料會最先到 L1，這

3 \cdot 2^{k}

個資料剛好可以都在 L1 就不會造成 cache thrashing

可以透過 lscpu 知道自己電腦的 L1 大小

+ * Thus, it will avoid cache thrashing as long as 3*2^k elements can
+ * fit into the cache.  Not quite as good as a fully-eager bottom-up
+ * mergesort, but it does use 0.2*n fewer comparisons, so is faster in
+ * the common case that everything fits into L1.

我們需要計算兩個鍊結串列的長度並且檢查是否為 2 的次方，而用來計算的 count 就是控制是否合併的因素，當兩個鍊結串列長度為

2^{k}

就合併，計算方式

+ * The merging is controlled by "count", the number of elements in the
+ * pending lists.  This is beautiully simple code, but rather subtle.
+ *
+ * Each time we increment "count", we set one bit (bit k) and clear
+ * bits k-1 .. 0.  Each time this happens (except the very first time
+ * for each bit, when count increments to 2^k), we merge two lists of
+ * size 2^k into one list of size 2^(k+1).

list_sort 排序過程

struct list_head *list = head->next, *pending = NULL;
size_t count = 0;	/* Count of pending */

if (list == head->prev)	/* Zero or one elements */
    return;

/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;

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

開發過程遇到的問題

commit message 遇到的問題: 說我用到非英文單字，後來我檢查，因為我在 body 中寫到 "Use INIT_LIST_HEAD" macro 的名字導致無法儲存，改掉就好，

不通過的詞：deallocation

Read https://github.com/sysprog21/lab0-c/blob/master/CONTRIBUTING.md#git-commit-style carefully.
Proceed with commit? [e/n/?] e
Implement q_new with circular list structure                               [line 1]
 - Avoid using non-American English words

Failed to retrieve upstream commit hash from GitHub.
解決：重開機或是等一陣子在試，3/9直播有說道不要急著做 make test ，先思考在執行

lun@lun-OMEN:~/linux2025/hw1/lab0-c$ make test
Progress: [####################--------------------] 50%
[!] Failed to retrieve upstream commit hash from GitHub.

make: *** [Makefile:60: test] Error 1

閱讀資料

你所不知道的C語言：指標篇

釐清 pointer
引用 C語言: 超好懂的指標，初學者請進～中的描述可以很好理解

指標 (Pointer) 就是某變數的位址。而這邊的指標變數 (Pointer Variable)，則是用來存放指標的變數。
array subscripting 在編譯時期只確認以下兩件事:
- 得知 size
- 取得陣列第 0 個 (即最初的一項) 元素的指標
前兩者以外的操作，都透過 pointer
array subscripting => syntax sugar
C has no real "array"!
關於為什麼　&b[0] 是　pointer to struct?　& 不是　address of 用來取位置的嗎？那為什麼不是一個數值？
因為我們前面有了解過指標變數中存的值就是記憶體位置，在這裡我的理解是：把　b[0] 看成一個變數，&b[0] 這個數值就是記憶體位置，那什麼變數會存放記憶體位置呢？就是指標變數了，所以才會是　pointer to struct
```
(gdb) whatis &b[0]
type = struct {...} *
```

遇到 gdb 無法存取記憶體

(gdb) p &b
$1 = (struct {...} (*)[17]) 0x4620 <b>
(gdb) x/4 b
0x4620 <b>:	0	0	0	0
(gdb) p (&b[0])->v = {1, 2, 3}
Cannot access memory at address 0x4620

後來找到原因，因為我沒有把程式跑起來，但是跑起來後，因為 main() 中沒有程式碼，整個程式會直接結束，還來不急跟變數做互動它就結束的概念，所以要在 main() 這個地方做一個 break point，讓它停在那裡我們就可以對 b[0] 做修改記憶體了

(gdb) break main
Breakpoint 1 at 0x555555555136: file s.c, line 5.
(gdb) run
Starting program: /home/lun/linux2025/hw1/s 
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".

Breakpoint 1, main () at s.c:5
5	int main(){}
(gdb) p (&b[0])->v = {1, 2, 3}
$1 = {1, 2, 3}

關於你所不知道的C語言：指標篇的這個部份，我和影片中實做的結果不一樣

(gdb) p &b
$31 = (struct {...} (*)[17]) 0x555555558060 <b>
(gdb) p &b+1
$32 = (struct {...} (*)[17]) 0x555555558280 <calendar>
(gdb) p &a[0]
$33 = (int *) 0x555555558040 <a>
(gdb) p &a[3]
$34 = (int *) 0x55555555804c

其中 &b+1 不是 a[0] 或是 a[3] 的位置，而是 calendar 的位置

(gdb) p &b[16]     
$42 = (struct {...} *) 0x555555558260 <b+512>
(gdb) p &calendar
$43 = (int (*)[12][31]) 0x555555558280 <calendar>

在查看 calendar 位置的實做過程中，發現 memcpy 不能直接使用，要先強至轉型才能看到值

$3 = (double *) 0x555555558280 <calendar>
(gdb) p memcpy(calendar, b, sizeof b[0])         
'memcpy' has unknown return type; cast the call to its declared return type
(gdb) p (double*)memcpy(calendar, b, sizeof b[0])
$3 = (double *) 0x555555558280 <calendar>

你所不知道的 C 語言: linked list 和非連續記憶體

pointer to pointer 的實做理解
用 leetcode 82. Remove Duplicates from Sorted List II 來實做，並用 graphviz 畫每個步驟

每一個節點都是一個 ListNode 物件

最一開始 indirect 指向 head，head 指向第一個節點的位置，cur 指向 indirect 指向的 head 指向的位置（指標的指標）

如果 cur 的值與下一個節點值不相同

改變 indirect 中儲存的記憶體位置，改到指向位置的指標的 next(也是一個指標)的位置

所以，indirect 不是直接指向 2 !! 而是指向指向 2 的 1->next 指標

如果 cur的值與下一個節點值相同

迭代 cur 一直到不相同

然後把 indirect 指到的 next 指標，指向 cur 指向的節點 4

重複以上步驟，直到 indirect 指向的指標指向的物件為 NULL

*-safe 就是不管任何條件 *，這個函式都可以執行

2025q1 Homework1 (lab0)

開發環境

開發步驟與工具

實做佇列

q_new

q_free

q_insert_head 、q_insert_tail

q_remove_head 、q_remove_tail

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_reverseK

q_sort

q_ascend

q_descend

q_merge