---
# System prepended metadata

title: linux2025Q1-Homework1(lab0)

---

 # 2025q1_Homework1(lab0)
  contributed by [dingsen-Greenhorn](https://github.com/dingsen-Greenhorn/lab0-c)
### Reviewed by `yy214123`

`q_reverse` 可以如下改善：
```diff
/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head)) {
        return;
    }
    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head) {
-       node->next = node->prev;
-       node->prev = safe;
+       list_move(node, head);
    }
-   node->next = node->prev;
-   node->prev = safe;
    return;
}
```
如此一來更符合 linux 核心風格。

`q_delete_mid` 除了使用快慢指標的策略，也能使用另一個策略來實作：
```graphviz
digraph G {
    graph [
        nodesep=0.8,
        ranksep=0.8
    ];

    { rank=same; head; 1; 2; 3; 4; 5; }
    { rank=same; p1 [label="*p1", shape=box]; p2 [label="*p2", shape=box]; }

    head -> 1 -> 2 -> 3 -> 4 -> 5 -> head [dir=both];

    p1 [label="*p1", shape=box];
    p2 [label="*p2", shape=box];

    p1 -> 1 [color=red];
    p2 -> 5 [color=red];
}
```
```graphviz
digraph G {
    graph [
        nodesep=0.8,
        ranksep=0.8
    ];

    { rank=same; head; 1; 2; 3; 4; 5; }
    { rank=same; p1 [label="*p1", shape=box]; p2 [label="*p2", shape=box]; }

    head -> 1 -> 2 -> 3 -> 4 -> 5 -> head [dir=both];

    p1 [label="*p1", shape=box];
    p2 [label="*p2", shape=box];

    p1 -> 2 [color=red];
    p2 -> 4 [color=red];
}
```
```graphviz
digraph G {
    graph [
        nodesep=0.8,
        ranksep=0.8
    ];

    { rank=same; head; 1; 2; 3; 4; 5; }
    { rank=same; p1 [label="*p1", shape=box]; p2 [label="*p2", shape=box]; }

    head -> 1 -> 2 -> 3 -> 4 -> 5 -> head [dir=both];

    p1 [label="*p1", shape=box];
    p2 [label="*p2", shape=box];

    p1 -> 3 [color=red];
    p2 -> 3 [color=red];
}
```
由於使用的資料結構是環狀雙向串列，這個策略可以減少 $\frac {n}{2}$ 次走訪次數。


{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
 
## 開發環境
    
 ---
    
```
dingsen@dingsen:~/linux/lab0-c$ ./qtest
cmd> help
Commands:
  #           ...          | Display comment
  ascend                   | Remove every node which has a node with a strictly less value anywhere to the right side of it
  dedup                    | Delete all nodes that have duplicate string
  descend                  | Remove every node which has a node with a strictly greater value anywhere to the right side of it
  dm                       | Delete middle node in queue
  free                     | Delete queue
  help                     | Show summary
  ih          str [n]      | Insert string str at head of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
  it          str [n]      | Insert string str at tail of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
  log         file         | Copy output to file
  merge                    | Merge all the queues into one sorted queue
  new                      | Create new queue
  next                     | Switch to next queue
  option      [name val]   | Display or set options. See 'Options' section for details
  prev                     | Switch to previous queue
  quit                     | Exit program
  reverse                  | Reverse queue
  reverseK    [K]          | Reverse the nodes of the queue 'K' at a time
  rh          [str]        | Remove from head of queue. Optionally compare to expected value str
  rt          [str]        | Remove from tail of queue. Optionally compare to expected value str
  show                     | Show queue contents
  size        [n]          | Compute queue size n times (default: n == 1)
  sort                     | Sort queue in ascending/descening order
  source                   | Read commands from source file
  swap                     | Swap every two adjacent nodes in queue
  time        cmd arg ...  | Time command execution
  web         [port]       | Read commands from builtin web server
Options:
  descend     0            | Sort and merge queue in ascending/descending order
  echo        1            | Do/don't echo commands
  entropy     0            | Show/Hide Shannon entropy
  error       5            | Number of errors until exit
  fail        30           | Number of times allow queue operations to return false
  length      1024         | Maximum length of displayed string
  malloc      0            | Malloc failure probability percent
  simulation  0            | Start/Stop simulation mode
  verbose     4            | Verbosity level
cmd> 

```
## Quene 操作功能實現
---
### q_new
```
struct list_head *new_queue =
(struct list_head *) malloc(sizeof(struct list_head));
```
q_new 是其他功能的基礎功能，用動態分配記憶體 `malloc`分配空間給queue.
    
sizeof(struct list_head) 計算 struct list_head 結構的大小，確保分配足夠的記憶體空間來存儲這個結構。並且由於malloc 返回的是 void *，所以需要類型轉換成 struct list_head * 以符合變數 new_queue 的類型。


其中我一開始的寫法如下
```
        struct list_head *new_queue =
        malloc(sizeof(struct list_head));
```
    
後續再將自己的程式與同學討論發現，在 C 語言中，void * 因為可以自動轉換為任何指標類型，因此理論上
```
struct list_head *new_queue = malloc(sizeof(struct list_head)); 
```
也是可行的。
但是在 C++ 中，void * 不能隱式轉換為其他指標類型，所以如果這段程式碼將來可能會用 C++ 編譯，就需要顯式轉型 (struct list_head *) 來避免編譯錯誤。
因此，加入後可以同時兼容兩種語言，於是改進成以上方案。

---
### q_free
q_free 的目標是釋放不需要的queue。由於刪除queue的過程中，需要正確釋放並確保不會有記憶體洩漏 (memory leak)。
假設如果若先釋放 element_t，則 value 仍然指向已釋放的記憶體 (dangling pointer)，對該指標進行 free() 可能會導致未定義行為 (undefined behavior)。
    
因此釋放順序應當是 先內部資料、再外部結構、最後頭部。
```
        list_for_each_safe (node, safe_front, head) {
        list_del(node);
        free(list_entry(node, element_t, list)->value);
        free(list_entry(node, element_t, list));
    }
    free(head);
}
```

---
### q_insert_head & tail
基本上兩個設計幾乎一樣因此以q_insert_head為例：


#### 分配 element_t 結構記憶體
```
    element_t *new_content = (struct list_head *)malloc(sizeof(element_t));
```
如同前面所說明的一樣`malloc(sizeof(element_t))`會分配一塊記憶體空間，大小為 `element_t` 結構的大小，並回傳一個指向這塊記憶體的指標。
    `element_t` 的結構通常如下：
```  
    typedef struct {
    struct list_head list;  
    char *value;            
} element_t;
```

#### INIT_LIST_HEAD()
INIT_LIST_HEAD() 來自 Linux Kernel 的 list.h，它的定義如下
```  
static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}
```
它的作用是初始化新節點，讓 new_content->list 的 prev 和 next 都指向自己，避免指標未初始化的問題。
#### 分配字串記憶體
```
    new_content->value = strdup(s);
```

strdup(s) 會使用 malloc(strlen(s) + 1) 分配一塊新的字串記憶體。將 s 的內容複製到新記憶體中。回傳新字串的指標，讓 new_content->value 指向它。
這樣的設計可以確保：
        new_content->value 擁有自己的獨立記憶體，不會與 s 共用。s 可能來自不同的作用域（例如函式參數），如果不複製就直接儲存 s 的指標，可能會導致記憶體存取錯誤。
#### 插入鏈結串列
```

list_add(&new_content->list, head);
```
```
static inline void __list_add(struct list_head *new,
                              struct list_head *prev,
                              struct list_head *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}
```
```
list_add(&new_content->list, head);
```
讓 new_content 成為 head 之後的第一個節點。
  
相同的q_insert_tail,只差list_add_tail
在 Linux Kernel 的 list.h，list_add_tail 定義如下：
```
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head->prev, head);
}
```
與 list_add 相比，它呼叫 __list_add 時，參數改變：
```
    prev = head->prev（即原本的最後一個節點）
    next = head（因為 head 是循環鏈結串列的錨點）
```  

---
### q_remove_head & tail
q_remove_head and q_remove_tail基本上很類似，以q_remove_head為例：
#### 取得鏈結串列的第一個節點
```
element_t *first = list_first_entry(head, element_t, list);
```

list_first_entry() 是 Linux Kernel 提供的 macro，定義如下：
```
     #define list_first_entry(ptr, type, member) \
        list_entry((ptr)->next, type, member)
```

(ptr)->next → 取 head->next，即第一個節點。
list_entry(head->next, element_t, list) 會將 head->next 轉換為 element_t * 型態的指標
根據 list 成員的偏移量，找到 element_t 結構的起始位址


#### 從鏈結串列中移除該節點

list_del(&first->list);


list_del() 定義如下：
```
static inline void list_del(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    entry->next = NULL;
    entry->prev = NULL;
}
```
運作方式：

修改前後節點的指標
```
entry->prev->next = entry->next;
entry->next->prev = entry->prev;
```
這樣，first 節點從鏈結串列中移除，但仍然佔有記憶體。
避免野指標（Dangling Pointer）
```
        entry->next = NULL;
        entry->prev = NULL;
```
這樣 first->list 的指標會變成 NULL，避免程式誤用它。

#### 選擇性地複製字串

```
if (sp && bufsize > 0) {
    strncpy(sp, first->value, bufsize - 1);
    sp[bufsize - 1] = '\0';
}
```
為何要檢查 sp？
    sp 是一個指標，若 sp == NULL，則表示不需要複製字串，直接跳過這段程式碼。
    
為何要檢查 bufsize > 0？
        bufsize 是 sp 可用的記憶體大小，若 bufsize == 0，則不應該嘗試寫入，否則可能導致錯誤。
    
如何安全地複製字串？
    
strncpy(sp, first->value, bufsize - 1);
bufsize - 1 確保最多只複製 bufsize - 1 個字元，避免溢位（Buffer Overflow）。
sp[bufsize - 1] = '\0';
確保字串結尾是 \0，即使 first->value 的長度超過 bufsize - 1。

#### 回傳移除的節點
```
return first;
```
為何不直接釋放 first？
q_remove_head() 只負責從鏈結串列中移除節點，但並不釋放它的記憶體。
這樣設計的好處是由呼叫者決定何時釋放記憶體，提高靈活性

---
### Q_size
不知道大家對於head有沒有疑問？就是為什麼需要一個額外的東西來描述鍊結串列的referance point?
抱持這個疑問，我在網路上找到一個不錯的說例：

在 Linux list.h 的設計中，head 並不是一個真正的節點，而是作為鏈結串列的錨點（Sentinel Node），這樣能避免 NULL 指標錯誤，並且允許空的鏈結串列存在：

head → [A] → [B] → [C] → head

當鏈結串列為空時：

head → head
head->next == head，因此 list_for_each 直接結束，不會執行 len = len + 1;，這樣 len 保持 0。

---
### q_delete_mid
這裡有很多不同的作法，我使用傳統的快慢指標來實作。
```
struct list_head *fast = head->next, *slow = head->next;

while (fast != head && fast->next != head) {
    fast = fast->next->next;
    slow = slow->next;
}
```
找出中間節點刪除
```
element_t *mid = list_entry(slow, element_t, list);
list_del(slow);
free(mid->value);
free(mid);
return true;
```
為什麼要從內層刪除到外面呢？為什麼刪除NODE需要宣告ELEMENT_T不能直接刪除SLOW並釋放SLOW記憶體就好？
    
這裡不能直接釋放 slow，而是需要透過 list_entry(slow, element_t, list) 來取得 element_t，再進行釋放。原因如下：

##### 1. slow 是 list_head，而不是 element_t 本體
在 Linux kernel 的 list_head 佈局中，每個節點的 list_head 僅僅是鏈結串列指標部分，它嵌套在包含真實資料的結構體（如 element_t）內
舉個例子，假設 element_t 定義如下：
```
typedef struct {
    struct list_head list; // 用於鏈結串列的 list_head
    char *value;           // 真正存放的數據
} element_t;
```
記憶體佈局
假設 element_t 佔據的記憶體如下（簡化表示）：
```
地址偏移	內容
0x1000	list_head
0x1008	value 指標
```
slow 變數是 指向 list_head 的指標，即 slow == &element->list。
但 list_head 只是結構體的一部分，並不代表整個 element_t。

##### 2. 直接釋放 slow 會導致「部分釋放」
如果你這樣做：

list_del(slow);
free(slow);  // ❌ 這是錯的！
slow 只是 list_head 指標，而不是 element_t 的起始地址。
free(slow) 只會釋放 list_head（約 16 bytes），但 element_t 的其他部分仍未釋放，導致記憶體洩漏（memory leak）。
##### 3. 正確的釋放方式
為了完整釋放 element_t，我們需要透過 list_entry() 取得 element_t 本體：

element_t *mid = list_entry(slow, element_t, list);
list_del(slow);
free(mid->value); // 釋放 `value`（假設是動態分配的記憶體）
free(mid);        // 釋放 `element_t` 本身

這樣確保
正確刪除鏈結串列節點 list_del(slow)。
完整釋放 element_t 本體（free(mid)）。
避免記憶體洩漏,釋放 value。

---
### q_delete_dup
```
if (safe != head && !strcmp(first->value, second->value)) {
            list_del(node); 
            free(first->value); 
            free(first); 
            dup = true; 
        } 
        else if (dup) {
            element_t *tmp = list_entry(node, element_t, list);
            list_del(node); 
            free(tmp->value); 
            free(tmp); 
            dup = false; 
```
一開始我浮現一個疑問就是在前面已經刪除節點了，標記的意義是什麼？為什麼之後再發現dup的時候還需要刪除節點？

這段程式碼的處理想法是一個有重複字串的排序鏈表，並且在發現相鄰元素有相同的值時，會刪除這些元素。標記 dup 的目的是標示在遍歷過程中是否已經發現並刪除了重複元素。

關於 dup 標記的意義
當標記 dup 為 true 時，表示當前已經發現了一個重複的元素對。這時候，接下來遍歷到的所有具有相同字串的元素都應該被刪除。這是為了保證每一個重複元素都能被刪除，而不只是跳過已經處理過的元素。

---
## q_swap,q_reverse,and q_reversek
多虧老師上課提到q_swap是一個q_reversek的k=2特例，因此啟發我進一步思考發現其實q_reverse也是q_reversek的一個k=Q_size的特例！
經過這個邏輯直覺的思考後，便開始實做.
### q_swap
``
q_reverseK(head, 2);
``
### q_reverse
根據上面的想法
``
q_reverseK(head,q_size);
``
應該可以順利做出，然而仔細查看Q_reversek
```
       list_cut_position(&tmp, head, tail->prev);
        q_reverse(&tmp);
        list_splice_tail_init(&tmp, &new_head);
    }
    list_splice_init(&new_head, head);
```
錯誤是因為在 q_reverseK 中調用了 q_reverse，而 q_reverse 本身也會調用 q_reverseK。這可能導致遞迴調用，尤其是當 q_reverse 的實作本身依賴於 q_reverseK 時，最終會造成不必要的遞迴調用。
### q_reversek
```
list_for_each (tail, head)：遍歷 head 鏈結串列的節點，尋找 k 個節點的尾端。
當 j >= k 時，tail 會指向這組的 第 k+1 個節點。

list_cut_position(&tmp, head, tail->prev);
q_reverse(&tmp);
list_cut_position(&tmp, head, tail->prev)：將 head 前 k 個節點剪下，存放至 tmp。
q_reverse(&tmp)：反轉 tmp 內的 k 個節點。
```
以上為簡單講解實現方式。

#### 小結
由於作業時間的因素，以及最後評估效能增加不顯著，因此留作為未來改善的方向。

未來改善的初步想法：
我們可以避免在 q_reverse 內部調用 q_reverseK，從而避免遞迴調用的錯誤。最簡單的做法是在 q_reverseK 中實作鏈結串列反轉邏輯，而不依賴於 q_reverse。

---
### q_sort
---

#### Merge_two_lists 
```
struct list_head *node = (descend ^ (strcmp(e1->value, e2->value) < 0))
                                 ? L1->next
                                 : L2->next;
```
    strcmp(e1->value, e2->value) < 0：
        若 e1->value 小於 e2->value，則回傳 true（升冪順序）。
        若 e1->value 大於 e2->value，則回傳 false（降冪順序）。
    descend ^ (條件判斷)：使用 XOR 運算來決定選擇哪個節點。
        當 descend == false（升冪排序）：選擇較小的節點。
        當 descend == true（降冪排序）：選擇較大的節點。
```
list_move_tail(node, &head);
```
將選擇的節點移動到 head（新的合併串列）。
```
list_splice_tail_init(list_empty(L1) ? L2 : L1, &head);
```
如果 L1 或 L2 還有剩餘的節點，直接將剩下的部分接到 head 的尾部。
```
list_splice(&head, L1);
```
最後將 head 的內容搬回 L1，完成合併。

```
struct list_head *slow = head;
const struct list_head *fast = NULL;

for (fast = head->next; fast != head && fast->next != head;
     fast = fast->next->next)
    slow = slow->next;

這段程式碼使用快慢指標與前面相同
```
```
struct list_head left;
list_cut_position(&left, head, slow);

    list_cut_position：將 head 切成兩個部分：
        head 變成前半部分。
        left 變成後半部分。
```
q_sort(&left, descend);
q_sort(head, descend);

遞迴地對兩個部分進行排序。
```
mergeTwoLists(head, &left, descend);
```
最後使用 mergeTwoLists 合併兩個排序好的部分，完成排序。

### q_ascend and q_descend
---

由於兩者方法幾乎相同，以q_ascend為例。
```
list_for_each (curr, head) {

    list_for_each 是 Linux Kernel 提供的巨集，會遍歷 head 所指向的鏈結串列。
```
```
while (tail != head &&
       strcmp(list_entry(curr, element_t, list)->value,
              list_entry(tail, element_t, list)->value) < 0) {
```
```
strcmp(e1->value, e2->value) < 0：
```
如果當前節點 curr 的值小於 tail，表示 curr 需要被刪除，因為 右邊 tail 有更大的值。
```
tmp= tail->prev;
list_del(tail);
q_release_element(list_entry(tail, element_t, list));
tail = tmp;
```

刪除 tail，因為 tail 儲存的是右側的更大值，意味著 curr 需要移除。
list_del(tail)：從鏈結串列中刪除 tail。
q_release_element(list_entry(tail, element_t, list))：釋放 tail 所指向的記憶體。
tail = tmp：讓 tail 指向被刪除節點的前一個節點，以便繼續檢查。
### q_merge
---

合併所有佇列

```
struct list_head *pos = head->next->next;
struct list_head *n;
```
    pos：從 head->next->next 開始遍歷，因為 head->next 是 first_queue，不需要再合併自己。

while (pos != head) {

    遍歷 head 的鏈結串列，依次處理每個 queue_contex_t。
```
n = pos->next;
queue_contex_t *current_queue = container_of(pos, queue_contex_t, chain);
```
儲存下一個節點：避免修改鏈結串列後影響遍歷。
取得 current_queue：從 pos 轉換為 queue_contex_t 結構。

```
list_splice_init(current_queue->q, first_queue->q);
```

將 current_queue->q 佇列的所有元素移到 first_queue->q。
list_splice_init：
將 current_queue->q 佇列插入 first_queue->q 的尾端。
清空 current_queue->q（INIT_LIST_HEAD(current_queue->q)）。
```
current_queue->size = 0;
```
清空 current_queue 的大小，因為它已經合併到 first_queue。

```
pos = n;
```
移動到下一個 queue_contex_t，繼續合併。

## 論文 <Dude,is my code contstant time>
---
#### 1. 檢測流程概述
該方法的核心概念是 時間洩漏檢測（timing leakage detection），主要透過統計分析來確認執行時間是否會因輸入資料的不同而變化，從而推測程式是否可能受到時間攻擊（timing attack）。

整個檢測流程分為三個主要步驟：

    測量執行時間
    後處理測量數據
    應用統計檢定
#### 2. 詳細檢測流程
##### 步驟 1：測量執行時間
該步驟的目的是收集執行時間數據，以判斷程式是否存在時間變異性。


定義測試類別：將輸入數據分為 固定值類別（fix class） 和 隨機值類別（random class） 來進行測試。
執行時間測量：
使用 CPU 週期計數器（cycle counter）（如 x86 TSC 或 ARM systick）。
在低階硬體上，可能需要高解析度計時器或外部設備來測量。
環境條件控制：
為了避免測量誤差，每次測試的輸入類別應隨機選擇，並確保外部影響最小化（如系統中斷等）。
##### 步驟 2：後處理測量數據
收集的執行時間數據可能受到雜訊影響，因此需要進行後處理：

裁剪（Cropping）：
    由於計時數據通常呈現 右偏分佈（positively skewed），可以移除過高的數據點（如設定閾值）。
高階預處理：
可以使用非線性變換（如 centered product 方法）來增強檢測效果。
##### 步驟 3：應用統計檢定
最關鍵的一步是應用統計方法來判斷兩組執行時間分佈是否不同：

t-檢定（Welch’s t-test）：
測試兩組數據的均值是否相等。
若檢定結果顯示顯著差異，則表示執行時間依賴於輸入數據，可能存在時間洩漏。
非參數檢定（如 Kolmogorov-Smirnov test）：
適用於無法假設分佈形狀的情況，但可能需要更多數據來收斂結果。
##### 3. 測試結果與案例分析
研究者使用該方法測試了不同類型的加密演算法，結果顯示該方法能夠有效偵測變異時間執行：

變數時間（variable-time）記憶體比較：
測試了 memcmp，結果顯示執行時間與輸入數據相關，存在時間洩漏。
AES 加密：
傳統 T-tables 實作被檢測出明顯的時間變異性。
Bitsliced AES 則被確認為常數時間執行（未發現統計顯著的洩漏）。
Curve25519 在 ARM7TDMI 上的實作：
發現其變異時間執行來自 ARM7TDMI 處理器的變數時間乘法指令。

### dudect
---

## 亂數

### 實做shuffle命令
---
add_cmd 會在命令列表中添加新命令，要新增一條新命令 shuffle 則要實作 do_shuffle，並在qtest.c 的 console_init() 加上 ADD_COMMAND。
```
ADD_COMMAND(shuffle, "Do Fisher-Yates shuffle", "");
```
qtest 裡的 do_shuffle 加上shuffle的限制條件 :
```
static bool do_shuffle(int argc, char *argv[])
{
    if (!current || !current->q)
        report(3, "Warning: Calling shuffle on null queue");
    error_check();
    if (q_size(current->q) < 2)
        report(3, "Warning: Calling shuffle on single queue");
    error_check();
    if (exception_setup(true))
        q_shuffle(current->q);
    q_show(3);
    return !error_check();
}
```
依照 Fisher–Yates shuffle 提供的演算法:
將new指到 last->prev 也就是last 前一個
再用old （隨機的節點）與new交換，並逐漸減小大小



```
void q_shuffle(struct list_head *head) 
{
    if (!head || list_is_singular(head)) 
        return;
    struct list_head *last = head;
    int size = q_size(head);
    while (size > 0) {
        int index = rand() % size;
        struct list_head *new = last->prev;
        struct list_head *old = new;
        while (index--) 
            old = old->prev;
        swap(new, old);
        last = last->prev;
        size--;
    }
    return;
}
```
接下來用腳本測試結果
```
Expectation:  41666
Observation:  {'1234': 41889, '1243': 41786, '1324': 41679, '1342': 41628, '1423': 41565, '1432': 41527, '2134': 41724, '2143': 41962, '2314': 41514, '2341': 41524, '2413': 41735, '2431': 41478, '3124': 41788, '3142': 41491, '3214': 41716, '3241': 41830, '3412': 41962, '3421': 41807, '4123': 41662, '4132': 41598, '4213': 41375, '4231': 41420, '4312': 41400, '4321': 41940}
chi square sum:  17.94479911678587
```

![histogram](https://hackmd.io/_uploads/ryRCFQ2j1l.png)

---
## Valgrind

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

執行 $ make valgrind 後，得到以下訊息：

```
scripts/driver.py -p /tmp/qtest.xabQT9 --valgrind 
---     Trace           Points
+++ TESTING trace trace-01-ops:
--56105:0:libcfile Valgrind: FATAL: Private file creation failed.
   The current file descriptor limit is 1073741804.
   If you are running in Docker please consider
   lowering this limit with the shell built-in limit command.
--56105:0:libcfile Exiting now.
---     trace-01-ops    0/5
```
#### Why Does This Cause an Issue?

##### Valgrind 使用檔案描述符來管理內部檔案

Valgrind 在執行時會建立私有的暫存檔案，並且依賴合理的檔案描述符（File Descriptor, FD）上限來運作。若 FD 限制過高，Valgrind 可能無法正確建立這些檔案，因為它無法配置必要的結構來管理這麼大量的描述符。

##### 系統限制與核心約束

大多數 Linux 系統 預期的 FD 限制通常是 1024、4096 或 65536，但不會設定成數十億。若 FD 限制過高，可能會影響核心（Kernel）內部的檔案表分配，導致 Valgrind 無法正常建立私有檔案。

#### 如何修正？

將 FD 限制調整為更合理的數值
```
ulimit -n 65536
```
最終，執行 make valgrind 
```
dingsen@dingsen:~/linux/lab0-c$ make valgrind
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/dingsen/linux/lab0-c'
rm -f qtest.o report.o console.o harness.o queue.o random.o dudect/constant.o dudect/fixture.o dudect/ttest.o shannon_entropy.o linenoise.o web.o .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d .shannon_entropy.o.d .linenoise.o.d .web.o.d *~ qtest /tmp/qtest.*
rm -rf .dudect
rm -rf *.dSYM
(cd traces; rm -f *~)
  CC    qtest.o
  CC    report.o
  CC    console.o
  CC    harness.o
  CC    queue.o
  CC    random.o
  CC    dudect/constant.o
  CC    dudect/fixture.o
  CC    dudect/ttest.o
  CC    shannon_entropy.o
  CC    linenoise.o
  CC    web.o
  LD    qtest
make[1]: Leaving directory '/home/dingsen/linux/lab0-c'
cp qtest /tmp/qtest.2MIX7V
chmod u+x /tmp/qtest.2MIX7V
sed -i "s/alarm/isnan/g" /tmp/qtest.2MIX7V
scripts/driver.py -p /tmp/qtest.2MIX7V --valgrind 
---     Trace           Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---     trace-01-ops    5/5
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
---     trace-02-ops    6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, remove_head, reverse and merge
---     trace-03-ops    6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, swap, and sort
---     trace-04-ops    6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
---     trace-05-ops    6/6
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK
---     trace-06-ops    6/6
+++ TESTING trace trace-07-string:
# Test of truncated strings
---     trace-07-string 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---     trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---     trace-09-robust 6/6
+++ TESTING trace trace-10-robust:
# Test operations on NULL queue
---     trace-10-robust 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---     trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
---     trace-12-malloc 6/6
+++ TESTING trace trace-13-malloc:
# Test of malloc failure on new
---     trace-13-malloc 6/6
+++ TESTING trace trace-14-perf:
# Test performance of insert_tail, reverse, and sort
Warning: Skip checking the stability of the sort because the number of elements 2000000 is too large, exceeds the limit 100000.
---     trace-14-perf   6/6
+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
---     trace-15-perf   6/6
+++ TESTING trace trace-16-perf:
# Test performance of insert_tail
---     trace-16-perf   6/6
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---     TOTAL           100/100
```
通過！

## 研讀 lib/list_sort.c 並嘗試改進

## GIT
```
clang-format -i *.[ch]
git commit -a
git push
```
```
git remote add sysprog21 https://github.com/sysprog21/vwifi-c.git
git fetch sysprog21
git remote remove sysprog21
```
```c
git branch ：查看本地分支
git branch -r ：查看遠端倉庫分支
git remote show origin ：查看本地與遠端的關係
git status ：檢查本地與遠端是否同步
git pull origin master ：更新本地分支（拉取遠端的最新變更）
git push origin master ：推送本地變更到遠端
git rebase -i HEAD~N：查看最新的 N 個 Commit
git branch -d branch-name：刪除本地分支
git branch -D branch-name：強制刪除本地分支
git push origin --delete branch-name：刪除遠端分支
git commit --amend --author="user-name <user-email>"：修改最近一次 commit 的作者資訊
git rebase --abort: 放棄剛才的 rebase

git checkout origin
git rebase sysprog21/master


// 解決衝突
git add queue.c
git rebase --continue

// 更新到本地 branch
git reset --hard 7034022c
git pull origin master

git pull origin master --force


＊ open another new branch

git fetch jserv main
git branch -D Fix_verify.sh_typo
git checkout -b Fix_verify.sh_typo jserv/main
# (edit scripts/verify.sh)
git add scripts/verify.sh
git commit -m "Fix verify.sh typo and refine comments"
git push -u origin Fix_verify.sh_typo
git checkout dynamic_MCS
```

### 建立 PULL Request 
```c
git remote add upstream https://github.com/sysprog21/vwifi.git
git fetch jserv
git checkout jserv/main
git checkout -b new-branch
git add .
git commit -m "Commit message"
git push origin new-branch
```

### squash : 合併 commit 
```c
// 查commit歷史
git log --oneline

// 合併最新的n個commits
git rebase -i HEAD~n
將除了第一行外的 pick 改成 s

// 從某個commit
git rebase -i x3y4z5w // 想合併的最早那個commit的上一個
將要合併的的 pick 改成 s
```
### EDIT : 修改 commit
```c
// 修改前一次 commit
直接改檔案
git add
git commit --amend

git push origin branch_name --force


// 查 commit 歷史
git log --oneline

// 修改倒數第 n 個 commit
git rebase -i HEAD~n
將要修改的 pick 改成 e
直接改檔案
git commit --amend
git rebase --continue

git push origin branch_name --force

git push --force-with-lease origin branch_name

這比 --force 安全，會先檢查遠端分支是不是還是你本機最後拉下來的版本。 
```






