# 2024q1 Homework1 (lab0)
contributed by < `Bonnie-entre` >

### Reviewed by `brian049`
- 在`q_ascend` 函式那段當中可以使用 diff 來使閱讀者更能知道上下兩段程式碼的差別。
- 在 [commit a039359](https://github.com/Bonnie-entre/lab0-c/commit/a039359ce6375ce854b43603991dd2f9679b8401) 當中只有標題提到合併新的部份到你的專案當中，並未詳細說明實際的更改內容，會導致後續維護的困難，可以透過在 commit message 當中新增一些細節來讓更改更明瞭。
- 想了解你一開始提到 lima 是為了什麼?

:::danger
留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心
:::

## 開發環境

$ gcc --version
gcc (Ubuntu 13.2.0-4ubuntu3) 13.2.0

$ lscpu
Architecture:           x86_64
  CPU op-mode(s):       32-bit, 64-bit
  Address sizes:        36 bits physical, 48 bits virtual
  Byte Order:           Little Endian
CPU(s):                 4
  On-line CPU(s) list:  0-3
Vendor ID:              GenuineIntel
  Model name:           06/8e
    CPU family:         6
    Model:              142
    Thread(s) per core: 1
    Core(s) per socket: 4
    Socket(s):          1
    Stepping:           10
    BogoMIPS:           2784.04

### lima 的使用

:::danger
command 是「命令」，而非「指令」(instruction)
:::

常用<s>指令</s>命令

##cp file
## container format "conatiner_name:file_path"
limactl copy [SRC] [TAR]

## 指定的佇列操作

### q_insert_head, q_insert_tail 實作
#### ERROR: Need to allocate and copy string for new queue element

一開始的程式為以下

/* Create an element */
element_t *ele_new(char *s){
    element_t *ele = (element_t*) malloc(sizeof(element_t));
    if(!ele)
        return NULL;

    ele->value = s;
    INIT_LIST_HEAD(&ele->list);
    return ele;
}

/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
    if(!head)
        return false;

    element_t *ele = ele_new(s);
    if(!ele)
        return false;

    list_add(&ele->list, head);
    return true;
}

:::danger
allocate 的翻譯是「配置」，以區隔 dispatch (分配/分發) 的翻譯。
:::

問題的癥結點在於，對於 `char *value`，malloc 僅<s>分配</s> 配置了儲存指標本身的空間，而不是指標指向的字元陣列（字串）的空間**。value 是一個指標，它需要被指向一個足夠大的記憶體區域來儲存實際的字串資料。
對於 struct list_head list，malloc 確實為它分配了足夠的空間來儲存其成員（通常是兩個指標：prev 和 next），因為它是直接嵌入在 element_t 結構體中的。

:::danger
避免非必要的項目縮排 (即 `* `)，使用清晰、明確，且流暢的漢語書寫。
:::

所以可以自己用 malloc 分配，或是使用 `strdup`

strdup 是一個在 C 語言中常用的標準庫函數，用於複製字串。它會為給定的字串分配足夠的記憶體（使用 malloc），並將原字串複製到新分配的記憶體中，最後返回新字串的指標。如果記憶體分配失敗，它會返回 NULL。

注意事項：
* 使用 strdup 後，一定要記得在適當的時候使用 free 函數釋放分配的記憶體，以避免記憶體洩漏。
* strdup 是 POSIX 標準的一部分，而不是 C 標準庫的一部分，因此在某些環境（尤其是非 POSIX 相容的環境）中可能不可用。不過，大多數現代系統和編譯器都支援 strdup。
* 如果在一個不支援 strdup 的環境中工作，可以輕鬆地自己實現一個 strdup 功能的函數，方法是先使用 malloc 分配足夠的記憶體，然後使用 strcpy 或 memcpy 複製字串。
* strdup 通過簡化字串的複製操作，減少了程式碼量和潛在的錯誤，是處理字串時非常有用的工具。

更改後的版本

/* Create an element */
element_t *ele_new(char *s){
    element_t *ele = (element_t*) malloc(sizeof(element_t));
    if(!ele)
        return NULL;

-   ele->value = s;
+   ele->value = strdup(s);
+   if(!ele->value){
+       free(ele);
+       return NULL;
+  }
+
    INIT_LIST_HEAD(&ele->list);
    return ele;
}

:::danger
使用 `diff` 來標示
:::

### q_ascend, q_descend, q_reverse
在練習了 [Leetcode 2487](https://leetcode.com/problems/remove-nodes-from-linked-list/description/) 後理解到：由於是以右側數值作為基準，所以應以倒序先知基準數值之後，再取之比較之後的數值是否需要被踢除，為較容易的做法。

其中，`element_t` 中的 `value` 是為字串位址的型別，若要比較字串字典序的大小，可以使用標準庫函~~數~~式 `strcmp()` 或 `strncmp()`。這兩個函~~數~~式都會逐個字元比較字串，直到找到一個不同的字元或遇到字串結束符 '\0'，二函~~數~~式的關鍵差異在於好者可以指定比較的長度。

:::danger
注意[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::

此外，要注意的是在<s>歷遍</s> 逐一走訪每個元素時要使用 `list_head` ，而非 `entry`(`list_for_each_safe` 而非 `list_for_each_entry_safe`)，因為會在進行 `list_del`(是針對 list_head 做操作的) 與釋放 entry 後，再去訪問無效的地址。如下為錯誤情境

int q_ascend(struct list_head *head)
{
    if(!head || list_empty(head))
        return 0;

    char *max_val = NULL;
    element_t *entry, *safe;
    // after reverse, keep this big & delete ones bigger than it
    for (entry = list_entry((head)->prev, __typeof__(*entry), list),     \
        safe = list_entry(entry->list.prev, __typeof__(*entry), list); \
         &entry->list != (head); entry = safe,                           \
        safe = list_entry(safe->list.prev, __typeof__(*entry), list)){
            if(safe!=list_entry((head)->prev, __typeof__(*entry), list)\
                 && strcmp(max_val, safe->value)<0){
                    list_del(&safe->list);
                    free(safe->value);
                    free(safe);
                }
            else{
                free(max_val);
                max_val = strdup(entry->value);
            }
        }

    free(max_val);
    return q_size(head);
}

最後的實作如下，此處不使用 `q_reverse`，而是直接在 for 迴圈指向 `prev` 作為倒以提高效率。

int q_ascend(struct list_head *head)
{
    if(!head || list_empty(head))
        return 0;
    
    char *max_val = NULL;
    struct list_head *cur, *safe;
    // after reverse, keep this big & delete ones bigger than it
    for (cur = (head)->prev, safe = cur->prev; cur != (head); \
         cur = safe, safe = cur->prev){
        element_t *cur_ele = list_entry(cur, element_t, list);
        if(cur!=head->prev && strcmp(max_val, cur_ele->value)<0){
                list_del(cur);
                free(cur_ele->value);
                free(cur_ele);
            }
        else{
            free(max_val);
            max_val = strdup(cur_ele->value);
        }
    }

    free(max_val);
    return q_size(head);
}

### q_sort

實作上特別釐清了 `struct list_head list_less, list_greater;` 的型別選擇，在此處不適合宣告為指標的形式，因為容易遺漏掉**要為指標所指向的節點配置記憶體**的步驟，且會將程式碼複雜化。

/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    struct list_head list_less, list_greater;
    INIT_LIST_HEAD(&list_less);
    INIT_LIST_HEAD(&list_greater);

    element_t *pivot;
    pivot = list_first_entry(head, element_t, list);
    list_del(&pivot->list);

    element_t *cur, *safe;
    list_for_each_entry_safe (cur, safe, head, list) {
        if (strcmp(cur->value, pivot->value) < 0)
            list_move_tail(&cur->list, &list_less);
        else
            list_move_tail(&cur->list, &list_greater);
    }

    q_sort(&list_less, descend);
    q_sort(&list_greater, descend);

    list_add(&pivot->list, head);
    if (descend) {
        list_splice(&list_greater, head);
        list_splice_tail(&list_less, head);
    } else {
        list_splice(&list_less, head);
        list_splice_tail(&list_greater, head);
    }
}

### q_swap, q_reverseK
在此處的 `q_swap` 實作並非兩指定元素交換，而是倆倆為一群組倒序，背後的實作邏輯與 `q_reverseK` 是相同的，差異僅在於群組節點的數目，因此一起實作。

思考實作的過程學到的教訓在於，儘量採用 `list.h` 中已存在的函式，避免直接操作 `list_head` 的前後指標，一方面避免複雜化錯誤率降低，另一方面程式碼也更精簡。以此考量點來思考算法，會更聚焦思考方向。

/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    q_reverseK(head, 2);
}

/* Reverse the nodes of the list k at a time */
void q_reverseK(struct list_head *head, int K)
{
    int k = K;
    int cnt = q_size(head);
    struct list_head tmp;
    while (cnt > 0) {
        struct list_head *node = head;
        INIT_LIST_HEAD(&tmp);
        while (k--) {
            node = node->next;
        }
        list_cut_position(&tmp, head, node);
        if (cnt / K)
            q_reverse(&tmp);
        list_splice_tail(&tmp, head);

        cnt -= K;
        k = (cnt / K) ? K : cnt;
    }
}

### q_delete_dup

原本的程式碼會因為釋放內存 `free(entry)` ，而讓指標 `cur` 的走訪出問題。為函式功能為刪除所有重複元素（不至少保留一次該值），**用兩個變數分別儲存上一輪與這一輪比較時的相同狀況**，可以在比較的邊界時，確保將上一輪遺留的相同值刪除掉。

/* Delete all nodes that have duplicate string */
bool q_delete_dup(struct list_head *head)
{
    if (list_empty(head))
        return false;
    else if(list_is_singular(head))
        return true;

    struct list_head *cur, *next;
+    bool last = false;
+    list_for_each_safe(cur, next, head){
+        element_t *entry = list_entry(cur, element_t, list);
+        bool match = (next!=head &&
+                    !strcmp(entry->value, list_entry(next, element_t, list)->value));

+        if(last || match){
-        if(next!=head &&
-            !strcmp(list_entry(cur, element_t, list)->value, list_entry(next, element_t, list)->value)){
-            char *cmp_value = list_entry(cur, element_t, list)->value;
-            while(cur!=head && !strcmp(cmp_value, list_entry(cur, element_t, list)->value)){
-                struct list_head *del = cur;
-                element_t *entry = list_entry(del, element_t, list);

-                cur = next;
-                next = cur->next;

-                list_del(del);
-                free(entry->value);
-                free(entry);

-            }
+               list_del(cur);
+               free(entry->value);
+               free(entry);
        }
+       last = match;
    }

    return true;
}

---

## 研讀 lib/list_sort.c

### 關鍵特性：
* list_sort 是 stable sort
* merge sort 實作原理與重點有
* 為降低有效的比較次數，會保持兩個要被 merge 的 list 至少是 2 : 1
* merge sort 使用 bottom-up 取代 top-down 為的就是更好的避免 Cache thrashing，而當 2 : 1 的 list 可以完全被放到 cache 裡，就可以避免
* 實作方式則是由 `count` 以及利用二進制的特性去做判斷（[作業說明](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-e#M01-lab0)有清楚的例子與圖解說明合併機制）

#### Cache thrashing 是什麼？

首先要從作業系統的記憶體管理開始說起，基本上可以分成硬碟(secondary memory)以及 RAM(memory/ primary memory/ main memory)，後者眾所週知的讀寫資料速度較快，而在 RAM 裡存在的記憶體硬碟必定存在，一般來說是儲存多個進程較常使用到的資料或是程式。

一般的作業系統具有「虛擬記憶體」的設計，也就是每個進程都會維護自己的 page table （內含虛擬記憶體位址以及實體記憶體位址的對應），一方面讓儲存空間變多，二方面也是實作快取的機制使得進程在執行工作時處理資料的速度加快。

接著來說明 page, page frame, paging, page hit, page fault 的概念，以使用場景來說明，當該進程需要特定的資料時就會去查詢自己維護的 page table，虛擬地址對應的實體地址是否存在 RAM 中，也就是 RAM 存在該 page frame 嗎？假如有，便是 page hit；反之，即為 page fault，需要執行 paging 的動作從 hard disk 取得資料，也就是取得該 page。

Cache Thrashing 就發生在高頻率發生 page fault 超過一個臨界值，使得電腦處理速度下降的時候。這裡可以多補充說明造成 page fault 發生的情境，由於 RAM 容量也是有限的，因此會按照記憶體管理的演算法去決定要留下或是釋放哪些資料，當容量到達上限且 page fault 發生時即會進行耗成本的 paging 動作。

由此可以推斷 Merge sort 若是使用 Top-down 的算法，便會不斷地讀取多個反覆被 partition 的資料，就會容易使得 RAM 容量達到上限，進而高機率造成 Cache thrashing。

:::danger
原理呢？
:::

---

## CppCheck 回報錯誤

在執行 pre-commit-hook 會出現以下錯誤。

$ cppcheck --verson
Cppcheck 2.11

$ git commit -a

Following files need to be cleaned up:
queue.c
log2_lshift16.h:15:1: information: ValueFlow analysis is limited in log2_lshift16. Use --check-level=exhaustive if full analysis is wanted. [checkLevelNormal]
{
^

Fail to pass static analysis.

原先是 `Cppcheck 2.11`，但後來更新至最新版本 `Cppcheck 2.14`，更多錯

$ git commit -a
random.h:21:2: error: #error Platform pointers must be 32 or 64 bits [preprocessorErrorDirective]
#error Platform pointers must be 32 or 64 bits
 ^
report.c:64:11: style: Variable 'msg_name' can be declared as pointer to const [constVariablePointer]
    char *msg_name = msg_name_text[2];
          ^
log2_lshift16.h:15:1: information: Limiting ValueFlow analysis in function 'log2_lshift16' since it is too complex. Please specify --check-level=exhaustive to perform full analysis. [checkLevelNormal]
{
^
nofile:0:0: information: Active checkers: There was critical errors (use --checkers-report=<filename> to see details) [checkersReport]


Fail to pass static analysis.

:::warning
更新 `sysprog21/lab0-c` 的程式碼。
:::

最後一路降到 `Cppcheck 2.9`，便沒有問題了。