2025q1 Homework1 (lab0)

contributed by <Today-Asked>

作業書寫規範:

• 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
• 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
• 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
• 不要在筆記內加入 [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 today-asked-MS-7E14 6.11.0-19-generic #19~24.04.1-Ubuntu SMP PREEMPT_DYNAMIC Mon Feb 17 11:51:52 UTC 2 x86_64 x86_64 x86_64 GNU/Linux
    
$ 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.
    
$ lscpu
Architecture:             x86_64
  CPU op-mode(s):         32-bit, 64-bit
  Address sizes:          39 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   12
  On-line CPU(s) list:    0-11
Vendor ID:                GenuineIntel
  Model name:             12th Gen Intel(R) Core(TM) i5-12400
    CPU family:           6
    Model:                151
    Thread(s) per core:   2
    Core(s) per socket:   6
    Socket(s):            1
    Stepping:             5
    CPU(s) scaling MHz:   24%
    CPU max MHz:          4400.0000
    CPU min MHz:          800.0000
    BogoMIPS:             4992.00

實作 queue.[ch]

q_new

commit f7abe63 （commit message 錯誤，待修改）

使用 malloc 分配一個 list_head 的空間給變數 head，使用巨集 INIT_LIST_HEAD 把 prev 與 next 都指向自身，然後回傳 head。
僅閱讀函式說明時，誤解為必須為 queue_context_t 分配空間，但在閱讀 qtest.c 以及 Dennis40816 的紀錄後，才發現相關的實作細節已出現在 qtest.c 的 do_new 函式中：

if (exception_setup(true)) {
    queue_contex_t *qctx = malloc(sizeof(queue_contex_t));
    list_add_tail(&qctx->chain, &chain.head);

    qctx->size = 0;
    qctx->q = q_new();
    qctx->id = chain.size++;

    current = qctx;
}    

q_free

commit 82aceb3

也是在閱讀 qtest.c 後得知只需釋放單一佇列所佔的空間，因此我宣告一個指標 li 指向 head->next，使用 list_entry() 找到內嵌 li 的結構體 element_t，並且釋放該空間。
然而在初步編譯並執行 make check 後，執行 free 命令後出現了錯誤：

ERROR: Attempted to free unallocated block. Address = 0x56106b2170d8 
ERROR: Attempted to free unallocated or corrupted block. Address = 0x56106b2170d8 
Segmentation fault occurred. You dereferenced a NULL or invalid pointer.

我很納悶為何此處並非出現 AddressSanitizer 形式的錯誤訊息 (待完成)

總之在 copilot 的協助下，我才知道是因為原先未加上 li != head 的限制，導致迴圈存取到已經被釋放的記憶體。
修改上述不安全處，並且釋放並改用 list_for_each_entry_safe 巨集讓程式更簡短易讀後，最終程式如下：

void q_free(struct list_head *head)
{
    if (!head)
        return;
    element_t *e, *next_e;
    list_for_each_entry_safe(e, next_e, head, list){
        free(e->value);
        free(e);
    }
    free(head);
}    

q_insert_head & q_insert_tail

comment 1e4385b

先檢查 head 是否為 NULL，若是則回傳 false。
分配一塊空間予 element_t 結構體，並明確分配一塊空間予其 value 成員。
實施的記憶體安全措施包含：

1. 若 malloc(sizeof(element_t)) 未成功，回傳 false
2. 使用 strdup() 指定一塊記憶體空間，複製傳入的字元指標，避免傳入指標處的記憶體被刪除而出現 dangling pointer 的問題。

q_remove_head & q_remove_tail

commit 6ffe018

此處不必釋放 element_t 的空間，因此只需對 head->next 進行
list_del_init 即可。
使用 strncpy 函式，避免緩衝區溢位。

q_size

commit 82aceb3

使用最原始的方法，遍歷過整個鏈結串列，回到頭時結束迴圈。
可能的改進方式: 使用快慢指標

q_delete_mid

commit

最直覺的方法是使用 q_size() 得到串列的長度並算出中間值，使用一個變數計算何時會到達該節點，並刪除之。
但我後來參閱 leetcode 上的解法後改為使用兩個指標，一個往前一個往後，當兩者相遇時刪除該節點，如此可以將時間縮短為一半。

q_delete_dup

commit

我花了很多時間才理解題意，一開始以為是對於一個隨機排列的串列刪除複製的節點，因此我原想使用雜湊表來完成。
後來看了很多同學（）的解法，才發現在呼叫之前佇列的值便已排列，因此只須注意前一個與本身的值是否相同。
另外使用一個 del_last 變數，判斷是否為最後一個被刪除的複製元素，若是則將其刪除。

q_swap

commit

利用 list_del 並未將對於每兩個節點，

q_reverse

q_reverseK

q_ascend & q_decend

由於一開始沒有想法，我是參考這篇 leetcode solution 的作法，由後往前走過整個鏈結串列，（以 ascend 為例，）比較目前節點 li 和前一個節點 prev 的外嵌結構體（e 及 prev_e）值，當前一個節點的值大於自身時刪除前者，否則將目前節點移至前一個，繼續走訪串列直到回到 head。
在撰寫的過程中遇到了 Segmentation fault 的情況，後發現是因未處理兩個結構體的值相等的情況，導致程式陷入無限迴圈而記憶體傾印。

疑問

為何 list_del 只是將節點從鏈結串列中移除，並未釋放記憶體，函式名稱卻是 delete 而非 remove？
查看 linux/list.h 中與 list_del 相關的程式碼：

/*
 * Delete a list entry by making the prev/next entries
 * point to each other.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
	next->prev = prev;
	WRITE_ONCE(prev->next, next);
}

/*
 * Delete a list entry and clear the 'prev' pointer.
 *
 * This is a special-purpose list clearing method used in the networking code
 * for lists allocated as per-cpu, where we don't want to incur the extra
 * WRITE_ONCE() overhead of a regular list_del_init(). The code that uses this
 * needs to check the node 'prev' pointer instead of calling list_empty().
 */
static inline void __list_del_clearprev(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
	entry->prev = NULL;
}

static inline void __list_del_entry(struct list_head *entry)
{
	if (!__list_del_entry_valid(entry))
		return;

	__list_del(entry->prev, entry->next);
}

/**
 * list_del - deletes entry from list.
 * @entry: the element to delete from the list.
 * Note: list_empty() on entry does not return true after this, the entry is
 * in an undefined state.
 */
static inline void list_del(struct list_head *entry)
{
	__list_del_entry(entry);
	entry->next = LIST_POISON1;
	entry->prev = LIST_POISON2;
}

發現 list_del 的說明的確就是 "deletes entry from list."
查看 git blame，發現這段程式是由 Linus Torvalds 在 2005 年上傳（我想這應該是），此後未再修改，然而 Linus Torvalds 的演講 中作為範例的函式 remove_list_entry，執行的也是將一個節點從鏈結串列中移除，這代表他在 2013 年也認同 remove 的定義，那麼為何函式名稱並非後綴 remove，是沿用習慣，還是當時並未清楚定義兩者差別？