2022q1 Homework1 (lab0)

contributed by < DennisLiu16 >

實驗環境

$ gcc --version
 gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

$ lscpu
 Architecture:                    x86_64
 CPU op-mode(s):                  32-bit, 64-bit
 Byte Order:                      Little Endian
 Address sizes:                   39 bits physical, 48 bits virtual
 CPU(s):                          20
 On-line CPU(s) list:             0-19
 Thread(s) per core:              2
 Core(s) per socket:              10
 Socket(s):                       1
 NUMA node(s):                    1
 Vendor ID:                       GenuineIntel
 CPU family:                      6
 Model:                           165
 Model name:                      Intel(R) Core(TM) i9-10900F CPU @  2.80GHz
 Stepping:                        5
 CPU MHz:                         2800.000
 CPU max MHz:                     5200.0000
 CPU min MHz:                     800.0000
 BogoMIPS:                        5599.85
 Virtualization:                  VT-x
 L1d cache:                       320 KiB
 L1i cache:                       320 KiB
 L2 cache:                        2.5 MiB
 L3 cache:                        20 MiB
 NUMA node0 CPU(s):               0-19

事前

熟悉 Git 命令和 commit 格式 – 個人筆記
熟悉 Makefile 語法
熟悉 Valgrind
熟悉 Cppcheck
詳閱你所不知道的 C 語言: linked list 和非連續記憶體
研讀 lib/list_sort.c
fork lab0-c
設定 GitHub Actions

queue 實做

q_new: 建立新的「空」佇列;
q_free: 釋放佇列所佔用的記憶體;
q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);
q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點;
q_release_element: 釋放特定節點的記憶體空間;
q_size: 計算目前佇列的節點總量;
q_delete_mid: 移走佇列中間的節點，詳見 LeetCode 2095. Delete the Middle Node of a Linked List
q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 LeetCode 82. Remove Duplicates from Sorted List II
q_swap: 交換佇列中鄰近的節點，詳見 LeetCode 24. Swap Nodes in Pairs
q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
q_sort: 以遞增順序來排序鏈結串列的節點，可參閱 Linked List Sort 得知實作手法;

qtest 相關

提供新命令 shuffle，能透過 Fisher–Yates shuffle 對佇列中所有節進行洗牌 (shuffle) 動作
提供新命令 web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令，並嘗試整合 tiny-web-server – github

其他

使用 Address Sanitizer 修正錯誤
使用 Valgrind 進行記憶體錯誤排查
解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件的原理和考量點。可對照參考 CS:APP 第 10 章重點提示
研讀論文〈Dude, is my code constant time?〉，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student's t-distribution 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案
指出現有程式的缺陷 (提示: 和 RIO 套件有關) 或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request

環境設定紀錄

套件檢查 & 安裝

必要套件

$ sudo apt install build-essential git valgrind
$ sudo apt install clang-format aspell colordiff tig

Cppcheck

How to install latest Cppcheck using Git and CMake

# clone the repo
git clone git://github.com/danmar/cppcheck.git
cd cppcheck

# build and install
mkdir build && cd build && cmake .. && cmake --build .
make install

# reload terminal or open a new one
source ~/.bashrc

# check
which cppcheck
# /usr/local/bin/cppcheck

cppcheck --version
# Cppcheck 2.7

# make a test file test.c
echo -e "int main(){ \n\tchar a[10]; \n\ta[10] = 0; \n}" >> test.c

# test some file
cppcheck --enable=all test.c

# some error will show
# test.c:3:3: error: Array 'a[10]' accessed at index 10, which is out of bounds.[arrayIndexOutOfBounds]
# a[10] = 0;
#  ^
# test.c:3:8: style: Variable 'a[10]' is assigned a value that is never used. [unreadVariable]
# a[10] = 0;
#       ^

安裝 tig (較好檢視 git commit)

開通 GitHub Actions

Queue

`q_new`

思路

回傳型別是 list_head * 且沒有引數，需使用 malloc 在 heap 上申請大小同 struct list_head 的記憶體空間，malloc 在某些情況下會回傳 NULL，需於 INIT_LIST_HEAD 初始化前檢查，避免輸入 NULL 造成例外。
void * 的思考

malloc 回傳 void * 型別指標，根據你所不知道的C語言：指標篇 – void *之謎，void * 的存在是確保使用者確實轉型，那是否需要進行強制轉型呢？
參考問題 Do I cast the result of malloc? 下的三個回答:
- Issue of cast and sizeof. (Someone said this answer should update)
- In C, you don't need to cast the return value of malloc.
- You do cast.
  
  問題使我困惑，目前對本例(即 malloc)而言，評論中贊同 C 中要 casting 主要立場是 C/C++ 有更好的相容性和能讓編譯器提出轉型相關的警告。不贊同要 casting 的主張 malloc 內部已經包含能使 void *安全轉型成各種 pointer 的實做，因此不需要多此一舉，造成閱讀困難。目前看起來不應該使用 casting 比合理，因為可以透過 extern 界面達到 C/C++ 的兼容，所以看起來沒有一定要使用 casting 的理由？
  
  C 和 C++ 已是截然不同的程式語言，在 C++ 混用 malloc 可能會造成非預期的行為，另外，C++ 有專用的運算子，如 static_cast，本質上不該仰賴 C 語言風格的 casting。本課程要求學員撰寫出簡短、有效，和符合規格的程式碼，因此你不需要額外對 void * 型態的 malloc 返回值進行 casting，因為編譯器會幫你做。不用看太多網際網路上面的討論，應該儘量閱讀規格書並運用其中的條款來分析程式碼的運作。
  :notes: jserv
一致的是，大家建議在 sizeof 中使用 dereference of lvalue，避免更動左值時忘記更動型別。

INIT_LIST_HEAD 的變革 (WRITE_ONCE 的使用)

最新版本中(v5.17-rc5)，被定義於include/linux/list.h之下的INIT_LIST_HEAD的程式如下

/**
 * INIT_LIST_HEAD - Initialize a list_head structure
 * @list: list_head structure to be initialized.
 *
 * Initializes the list_head to point to itself.  If it is a list header,
 * the result is an empty list.
 */
static inline void INIT_LIST_HEAD(struct list_head *list)
{
    WRITE_ONCE(list->next, list);
    list->prev = list;
}

而在 v4.5-rc1 之前的版本如下

static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}

程式

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(*head));

    if (head != NULL) 
        INIT_LIST_HEAD(head);

    return head;
}

`q_free`

list 走訪 macro

list_entry

list_entry 透過 container_of 與輸入 list_head * 可返回指向 entry「結構體」指標，本作業中即返回指向結構 element_t 的指標，而非返回指向 list_head 的指標。可使用該返回值對結構體進行 -> 操作。

list 之中有眾多走訪巨集，以下分析適用情境
list_for_each

此種走訪適用於讀取鏈結串列資訊 (read only) e.g. q_size，註解同樣提到若改動 list 中的 element (list_head) 可能產生 UB。

The nodes and the head of the list must be kept unmodified while
iterating through it. Any modifications to the the list will cause undefined
behavior.
list_for_each_entry
- member 是 list_head 在 entry 的變數名
此種走訪適用於讀取結構體參數 (read only)，註解提到若改動 list 中的 element (list_head) e.g. 指標指向，則可能產生 UB。
list_for_each_safe
此種走訪適用於更改鏈結串列資訊 (R/W)，透過多輸入 safe 指標儲存下一個 list_head node 確保修正不造成鏈結串列毀損
list_for_each_entry_safe
此種走訪適用於更改結構體參數 (R/W)，可修改原理同上

思路
釋放結構體時，需考慮結構體中的指標是否由 malloc 動態配置，因此要觀察 queue 內的元素組成。由 q_remove_head 可知佇列中的元素類型 element_t (包含 list 和字串)， queue.h 中的定義為：
```
  /* Linked list element */
  typedef struct {
      /* Pointer to array holding string.
       * This array needs to be explicitly allocated and freed
       */
      char *value;
      struct list_head list;
  } element_t;
```
1. 註解中提到 value 用於保存字串，需由我們進行配置和「刪除」，因此刪除節點前應先刪除 char * 記憶體空間
2. element 是透過 q_insert_xxx 申請的
3. l 也是我們利用 malloc 申請的
因此三者皆需刪除。由於需要修改 (free) entry 內部，因此要用 list_for_each_entry_safe走訪。
free 可以用 q_release_element 代替

程式

/* Free all storage used by queue */
void q_free(struct list_head *l)
{
    if (!l)
        return;

    element_t *entry, *safe;
    list_for_each_entry_safe (entry, safe, l, list) { 
        q_release_element(entry);
        //free(entry->value);
        //free(entry);
    }

    free(l);
}

`q_insert_head`

思路
- 從頭插入，即將鏈表插入到 head->next，對應list_add

strlcpy

不使用 strcpy 的原因是容易造成記憶體溢位。代替方法可以使用 strlcpy，透過直接輸入長度確保不溢位。CERN 有提供 strlcpy 的實做

#include <stdio.h>

#ifndef strlcpy
#define strlcpy(dst,src,sz) snprintf((dst), (sz), "%s", (src))
#endif

由 snprtinf 實現所以會自動添加中止符'\0'，即僅複製 sz - 1 個字元，以下是測試：

#include <stdio.h>
#include <stdlib.h>

#ifndef strlcpy
#define strlcpy(dst,src,sz) snprintf((dst), (sz), "%s", (src))
#endif

int main() {
    size_t bufsize = 10;
    char *sp = malloc(sizeof(*sp) * bufsize);
    char *s = "stop at->nothing should show out";

    strlcpy(sp, s, bufsize);
    printf("%s", sp);
}
// return "stop at->", 9 char + '\0' == 10 char

程式

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *entry;
    if (!head || !(entry = malloc(sizeof(*entry))))
        return false;

    size_t len = strlen(s) + 1;
    if (!(entry->value = malloc(sizeof(char) * len)))
        return false;

    strlcpy(entry->value, s, len);
    list_add(&entry->list, head);
    return true;
}

`q_insert_tail`

思路
- 實做概念同 q_insert_head

程式

bool q_insert_tail(struct list_head *head, char *s)
{
    element_t *entry;
    if (!head || !(entry = malloc(sizeof(*entry))))
        return false;

    size_t len = strlen(s) + 1;
    if (!(entry->value = malloc(sizeof(char) * len)))
        return false;

    strlcpy(entry->value, s, len);
    list_add_tail(&entry->list, head);
    return true;
}

`q_remove_head`

思路
- 可以透過巨集 list_first_entry 得到首個 entry
- 由 list_del 移除該 entry
- 若 sp 地址有效才複製
- strlcpy 會自動加上 '\0'，因此不用特別修改 bufsize

程式

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *entry = list_first_entry(head, element_t, list);

    list_del(&entry->list);
    if (sp)
        strlcpy(sp, entry->value, bufsize);

    return entry;   // memory leak if user forget to check ret
}

`q_remove_tail`

思路
- 實做概念同 q_remove_head，重複程式之後再透過其他函式包裝？

程式

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *entry = list_last_entry(head, element_t, list);

    list_del(&entry->list);
    if (sp)
        strlcpy(sp, entry->value, bufsize);

    return entry;   // memory leak if user forgets to check ret
}

`q_release_element`

題目說不能動

程式

void q_release_element(element_t *e)
{
    free(e->value);  // free(NULL) is ok.
    free(e);
}

`q_size`

程式

int q_size(struct list_head *head)
{
    if (!head)
        return 0;

    int len = 0;
    struct list_head *li;

    list_for_each (li, head)
        ++len;
    return len;
}

`q_delete_mid`

思路
- 先檢查 head 是否有效
- 透過 list_for_each 初始式先走快指針，於迴圈中再一起走一步，之後靠迴圈和迴圈內雙重檢查可以讓佇列中不論是奇數或偶數都讓慢指針停在正確的位置
- 透過 list_entry 得到 entry指標，並透過 list_del 移除該entry
- 移除完成後要釋放，透過 free 或 q_release_element 都可以
透過 indirect pointer 的實做待補

程式

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if(!head || list_empty(head))
        return false;

    // using fast and slow pointer
    struct list_head *fast = head, *slow = head;

    list_for_each(fast, head) {
        fast = fast->next;
        slow = slow->next;
        if(fast == head) 
            break;
    }
    element_t *e = list_entry(slow, element_t, list);

    list_del(&e->list);
    q_release_element(e);

    /* using indirect pointer

    */

    return true;
}

`q_delete_dup`

思路

list_for_each_entry_safe 注意事項
list_for_each_entry_safe 中僅保證對 entry 的操作安全，並不保證對 safe 的操作是安全的

// my.c, compile cmd : gcc -o my my.c queue.o harness.o report.o
#include <stdio.h>
#include <stdlib.h>

#include "list.h"
#include "queue.h"

int main()
{
    struct list_head *head = q_new();
    char* s = "test";
    q_insert_head(head, s);
    q_insert_head(head, s);
    q_insert_head(head, s);
    element_t *e, *safe;
    list_for_each_entry_safe(e, safe, head, list) {
        printf("safe->list is head : %d, value:%s\n",&safe->list == head,safe->value);
    }
}

會得到

safe->list is head : 0, value:test
safe->list is head : 0, value:test
Segmentation fault (core dumped)

程式

`q_swap`

思路
程式

`q_reverse`

思路
程式

`q_sort`

思路
程式

2022q1 Homework1 (lab0)

實驗環境

事前

queue 實做

qtest 相關

其他

環境設定紀錄

套件檢查 & 安裝

開通 GitHub Actions

Queue

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_remove_tail

q_release_element

q_size

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_sort

Read more

WSL2 中連接 USB 的疑難雜症

ROS 問題