2022q1 Homework1 (lab0)

contributed by < kuihao >

實驗環境

gcc version

$ gcc --version

輸出:

gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

lscpu

$ 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):                          8
On-line CPU(s) list:             0-7
Thread(s) per core:              2
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           142
Model name:                      Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
Stepping:                        10
CPU MHz:                         1800.000
CPU max MHz:                     3400.0000
CPU min MHz:                     400.0000
BogoMIPS:                        3600.00
Virtualization:                  VT-x
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        6 MiB
NUMA node0 CPU(s):               0-7
Vulnerability Itlb multihit:     KVM: Mitigation: VMX disabled
Vulnerability L1tf:              Mitigation; PTE Inversion; VMX conditional cache flushes, SMT vulnerable
Vulnerability Mds:               Mitigation; Clear CPU buffers; SMT vulnerable
Vulnerability Meltdown:          Mitigation; PTI
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl and seccomp
Vulnerability Spectre v1:        Mitigation; usercopy/swapgs barriers and __user pointer sanitization
Vulnerability Spectre v2:        Mitigation; Full generic retpoline, IBPB conditional, IBRS_FW, STIBP conditional, RSB filling
Vulnerability Srbds:             Mitigation; Microcode
Vulnerability Tsx async abort:   Not affected
Flags:                           fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap clflushopt intel_pt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp md_clear flush_l1d

輸出呢？
:notes: jserv

作業要求:penguin:

lab0

截止日期：
- Mar 1, 2022 (含) 之前
- 越早在 GitHub 上有動態、越早接受 code review 並持續改進者，評分越高

開發過程

開發準備

將 sysprog21/lab0-c fork 至自己的 GitHub 帳號下並 pull 至本地端
開啟 GitHub Actions 功能
確定 Cppcheck 套件版本至少 v1.90，執行方語法檢視目前版本：
```
$ cppcheck --version
```
顯示結果符合要求
```
Cppcheck 1.90
```
:warning: If your Cppcheck version is lower than 1.90: Follow here! (the ordered list
$5^{\circ}$ )

閱讀文件 The Linux Kernel API - List Management Functions

關於 linux/list.h
list (Circular doubly-linked list) 的關鍵概念是，將結構體 list_head 嵌入到所需的結構體中，再藉由稍後會提及的 container_of 巨集得知 list 個別節點的地址。示意如下圖:
Image Not Showing Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
(原文: "你所不知道的 C 語言: linked list 和非連續記憶體")
Jim Huang2018
作業所使用的結構
由上述得知，Linux Kernel 的 linked-list 結構稱為 list_head，list_head 專職於指向其他非連續記憶體並且有另一個專有名詞稱作 head，其存放著 list_head 型別的位址，其功用是找到整條 linked-list。
- head 的程式碼與示意圖
```
list_head *head;
```
此外，作業中用來封裝 list_head 的節點結構稱為 element_t，由下方 queue.h 中的程式碼可知 element_t 的 value 也是一個指標，用來指向另一個實際存放字串的記憶體空間。由此可見這就是 Linux Kernel 管理非連續記憶體的方式：
1. 透過指標存取非連續記憶體的資料 (char *value）
2. 透過封裝著 list_head 的結構體（e.g. element_t）來管理眾多的指標 (char *value)
我認為這樣的程式設計 (OS: 此時才驚覺原來這才是程式設計) 正是為了方便協作及開發大型的程式專案。各項資料結構的用途專一、各司其職，char *value 專注於資料位址的存取、list_head 專注於串接各個 element_t，element_t 專注於管理多個指標。
- element_t 的程式碼與示意圖
```
/* 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;
```

本作業欲開發的 Linux Kernel 風格的 queue 的示意圖：

註: 上述示意圖可使用 graphviz playground (線上繪圖編輯器) 協助繪製

list.h Function 功能簡記

Function	Description
INIT_LIST_HEAD()	產生一個指向自己的 Head_ptr
list_add	於 head 向前插入一個新 node 可用於實作 Stacks (like liunx kernel api document descriped, "This is good for implementing stacks.")
list_add_tail	於 head 向後插入一個新 node 可用於實作 Queues (like liunx kernel api document descriped, "This is useful for implementing queues.")
list_del	將其他指向此 node 的鍵斷開，並重新相連時跳過此 node
list_del_init	此 node 不但被斷鍵 (list_del) 同時也將本身的鍵初始化
list_empty	向前為空：next 指向 head
list_is_singular	next, prev 指向 head
list_splice	head 向前插入一條新的 linked list
list_splice_tail	head 向後插入一條新的 linked list (方向維持正確，舊鏈的尾巴接新鏈的尾巴)
list_splice_init	執行 list_splice() 並順便把新鏈的 head 給初始化 (變成空鏈)
list_splice_tail_init	執行 list_splice_tail() 並順便把新鏈的 head 給初始化 (變成空鏈)
list_cut_position	將一個環切成兩個環
list_move	將目標 Node 移動至 Head->next
list_move_tail	將目標 Node 移動至 Head->prev

Entry
- Such an container object is called entry.
- Linked Lists
- Stacks and Queues

list_cut_position() 說明
將一個環切成兩個環，並指派給新的 head (head_to)






















static inline void list_cut_position(struct list_head *head_to, 
                                     struct list_head *head_from, 
                                     struct list_head *node)
{
    struct list_head *head_from_first = head_from->next;

    if (list_empty(head_from))
        return;

    if (head_from == node) {
        INIT_LIST_HEAD(head_to);
        return;
    }

    head_from->next = node->next;
    head_from->next->prev = head_from;

    head_to->prev = node;
    node->next = head_to;
    head_to->next = head_from_first;
    head_to->next->prev = head_to;
}

初始狀態

程式碼第 15、16 行

程式碼第 18 至 21 行

container_of

#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

Parameters 說明:
- ptr: member 的位址
- type: container 的型別
- member: member 的名稱
演算法簡述:
先利用 container 的型別與 member 的名稱，得到 container 與 member 之間的 offset。
```
offsetof(type, member);
```
再透過 member 的位址減去 offset，得到 container 的位址。
參考

q_new

(程式碼修改紀錄)

/* old version */
struct list_head *q_new()
{
    /*read and write head of queue*/
    element_t *rw_head = malloc(sizeof(element_t));
    if (!rw_head) {
        return NULL;
    }
    // struct list_head **indirect = &(rw_head->list;
    INIT_LIST_HEAD(&(rw_head->list));
    return &(rw_head->list);
}

git commit -a 時會被偵測出 memory leak 問題，原因 2022 年系統軟體系列課程討論區: commit 的時候出現 memory leak ，並學習使用 valgrind 動態檢測。

後來參考同學們的實作方式才發現我當初誤會 head 的意義，head 不必實作成 element_t，只需生成 list_head (*) 指標作為新生成的空 Queue。

/* new version */
struct list_head *q_new()
{
    struct list_head *q_head = malloc(sizeof(struct list_head));
    if (q_head) {
        INIT_LIST_HEAD(q_head);
    }
    return q_head;
}

配置一個 list_head 的實際空間，並將 q_head ptr 指向該實際空間。

q_free

code edition history













/* Free all storage used by queue */
void q_free(struct list_head *l)
{
    struct list_head **indirect = &l;
    /* Traverse will stop if the next ptr point to head itself */
    while ((*indirect)->next != l) {
        indirect = &(*indirect)->next;
        free(list_entry((*indirect)->prev, element_t, list)->value);
        free(list_entry((*indirect)->prev, element_t, list));
    }
    free(l);
    return;
}

Indirect pointer 風格的實作方式，每次先判斷 next pointer 是否指向 q_head (

l

)，若否，表示還有 node 可以 free，先將 indirect pointer 指向下一個 node 的 next pointer，並將前一顆 node 釋放掉；反之，將 q_head 釋放。

然而，此寫法再執行時會指向並釋放 Null Address，主要問題發生在第 7 至 9 行，凸顯出我這個寫法不適合使用 indirect pointer。第 7 行，indirect 先指向 head 的 next 指標的位址，但並非直接指向 next node 的位址，當第 9 行釋放 head 的記憶體位置，便會連帶 head 的 next 指標一起釋放，因此 indirect 就指向非法記憶體位址。並且另一個問題是通常 head 所指的位置一開始不應該被釋放掉，這會導致演算法設計上不易追蹤 queue 的所在位置。後來仔細研讀 list.h 發現 list_for_each_entry_safe，可以預先存取下下顆 node 的位址，如此一來即使釋放掉下顆 node，也能將指標指向下下顆位址。

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(l);
}

q_insert_head

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new_node = malloc(sizeof(element_t));
    if (!new_node)
        return false;
    INIT_LIST_HEAD(&new_node->list);
    new_node->value = strdup(s);
    if (!new_node->value) {
        free(new_node);
        return false;
    }
    list_add(&new_node->list, head);
    return true;
}

q_insert_tail

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new_node = malloc(sizeof(element_t));
    if (!new_node)
        return false;
    INIT_LIST_HEAD(&new_node->list);
    new_node->value = strdup(s);
    if (!new_node->value) {
        free(new_node);
        return false;
    }
    list_add_tail(&new_node->list, head);
    return true;
}

q_remove_head

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head)) {
        return NULL;
    }
    
    element_t *node = list_entry(head->next, element_t, list);
    list_del(head->next);
    if (sp && bufsize) {
        strncpy(sp, node->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return node;
}

q_remove_tail

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    /* Ref. https://hackmd.io/@blueskyson/linux2022-lab0 */
    if (!head || list_empty(head)) {
        return NULL;
    }
    
    element_t *node = list_entry(head->prev, element_t, list);
    list_del(head->prev);
    if (sp && bufsize) {
        strncpy(sp, node->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return node;
}

q_release_element

void q_release_element(element_t *e)
{
    free(e->value);
    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;
}

思考改進方式:
也許能透過修改 queue 節點的 struct，或另外準備一個儲存空間專門存放 queue 的節點數量，並於生成、新增、刪除時都順便修改該數值，q_size 函式就能改為直接讀取該儲存值以提升效能。

q_delete_mid

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (head->next == NULL) {
        return false;
    } else {
        struct list_head *current = head->next;
        int size = q_size(head);
        for (int i = 0; i < size / 2; i++) {
            current = current->next;
        }
        list_del(current);
        free(list_entry(current, element_t, list)->value);
        free(list_entry(current, element_t, list));
        return true;
    }
}

q_delete_dup

核心想法：設置一個回收桶存放暫存的副本，最後再一次清空回收桶。

利用指向 head->next 的 inderect pointer (pointer's poniter) 來處理 node 的移動或釋放。
每次走訪都會檢視 head->next 與 head->next->next
當發現 duplicates (副本) 發生，若 duplicates 的字串是第一次出現，則將第一次出現的副本先放入回收桶，後續副本與路圾桶內的 node 比較；若 duplicate 已出現於回收桶，就直接將 duplicate 釋放
最後清空垃圾桶

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head) {
        return false;
    }

    if (list_empty(head) || list_is_singular(head) ||
        head->prev == head->next) {
        return true;
    }

    /* 指向「指向當前 Node 的指標」的指標 */
    struct list_head **inderect = &head->next;
    /* 一個環狀垃圾桶 */
    struct list_head *GarbageCan = q_new();
    INIT_LIST_HEAD(GarbageCan);

    for (; *inderect != head;) {  // && (*inderect)->next!=head
        char *first_node_str = list_entry(*inderect, element_t, list)->value;
        char *second_node_str =
            list_entry((*inderect)->next, element_t, list)->value;
        /* 垃圾桶最上層將存放最新的副本，Node 優先與垃圾桶比對 */
        if ((GarbageCan->next != GarbageCan) &&
            (strcmp(list_entry(GarbageCan->next, element_t, list)->value,
                    first_node_str) == 0)) {
            struct list_head *directly_recycle = *inderect;
            list_del(directly_recycle);
            q_release_element(list_entry(directly_recycle, element_t, list));
        } else {
            /* 垃圾桶內找不到才跟下一個 Node 比對 */
            if (!strcmp(first_node_str, second_node_str)) {
                struct list_head *goto_GarbageCan = *inderect;
                struct list_head *directly_recycle = (*inderect)->next;
                list_del(goto_GarbageCan);
                list_add(goto_GarbageCan, GarbageCan);

                list_del(directly_recycle);
                q_release_element(
                    list_entry(directly_recycle, element_t, list));
            } else
                inderect = &(*inderect)->next;
        }
    }
    q_free(GarbageCan);  // 清空垃圾桶
    return true;
}

q_swap

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!(head) || list_empty(head) || list_is_singular(head)) {
        return;
    }
    struct list_head *current = head;
    for (; current->next != head && current->next->next != head;
         current = current->next->next) {
        list_move(current->next->next, current);
    }
}

q_reverse

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head) ||
        head->next == head->prev)
        return;
    // [1]-> [2]-> [3]-> [4]
    struct list_head *current = head;
    do {
        struct list_head *tmp = current->next;
        current->next = current->prev;
        current->prev = tmp;

        current = current->next;
    } while (current != head);
}

q_sort

參考「你所不知道的 C 語言: linked list 和非連續記憶體」的 indirect pointer 版本 mergeTwoLists、Mergesort_list

struct list_head *Merge2Lists(struct list_head *list1, struct list_head *list2)
{
    struct list_head *head = NULL, **ptr = &head, **node;
    for (node = NULL; list1 && list2; *node = (*node)->next) {
        node =
            signbit((float) strcmp(list_entry(list1, element_t, list)->value,
                                   list_entry(list2, element_t, list)->value))
                ? &list1
                : &list2;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *) ((uintptr_t) list1 | (uintptr_t) list2);
    return head;
}

struct list_head *Mergesort_list(struct list_head *head)
{
    if (!head || !head->next)
        return head;

    struct list_head *slow = head;
    for (struct list_head *fast = head->next; fast && fast->next;
         fast = fast->next->next)
        slow = slow->next;
    struct list_head *mid = slow->next;
    slow->next = NULL;

    struct list_head *left = Mergesort_list(head), *right = Mergesort_list(mid);
    return Merge2Lists(left, right);
}

如何運用原本用於普通非環狀 linked list 的 Merge sort?

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    head->prev->next = NULL;
    head->next = Mergesort_list(head->next);
    struct list_head *ptr = head;
    for (; ptr->next; ptr = ptr->next) {
        ptr->next->prev = ptr;
    }
    ptr->next = head;
    head->prev = ptr;
}

先將 linux kernel 的環狀 list 從 tail 切開 (head->prev->next = NULL) 變成非環狀 linked list，套用 Mergesort_list()，排序完成後再將尾端上鏈並順時針將每個 node 的 prev pointer 重新上鏈

關於 Linux 的其他收穫

gdb

GNU debugger 文件
使用 gdb 開啟執行檔之後，務必記得下斷點及執行的命令。若未下斷點 (breakpoints) 及未使用 run 命令，就直接使用 print 命令對變數 assign 數值，gdb 會顯示 Cannot access memory address 0xXXXX.

協助產生或解釋C語言宣告: cdecl

剪貼簿套件: xclip

將命令的標準輸出存入剪貼簿 (clipboard)

$ <command> | xclip -selection clipboard

可簡寫為

$ <command> | xclip -sel c

將檔案內容存入剪貼簿

$ xclip -selection clipboard <path>

可簡寫為

$ xclip -sel c <path>

多顯示器套件 (Multi-monitor): xrandr

檢視目前與系統相連接的輸出
```
$ xrandr
```
xrandr shows you the names of different outputs available on your system (LVDS, VGA-0, etc.) and resolutions available on each. For more details
將 HDMI顯示器 (e.g. HDMI-1) 與目前的顯示器 (eDP-1) 畫面同步
```
$ xrandr --output eDP-1 --same-as HDMI-1
```

HackMD 常用鍵盤快捷鍵 (keymap)

Discription	Keymap
複製前一行並向下新增	Shift + Ctrl + D
整行向上移動	Shift + Ctrl + Up
整行向下移動	Shift + Ctrl + Down
選取下一個相同的 Occurrence	Ctrl + D
選取所有相同的 Occurrence	Alt + F3

Github SSH keys 及將本地端 remote's URL 從 https 變更為 SSH

依 GitHub 設定指引於 Github 新增 SSH Public Key

當本地端執行 git push 時出現以下警告:

remote: Support for password authentication was removed on August 13, 2021. Please use a personal access token instead.
remote: Please see https://github.blog/2020-12-15-token-authentication-requirements-for-git-operations/ for more information.
fatal: Authentication failed for 'https://github.com/XXXX/XXXX/'

表示本地端的 Remote's URL 尚未設定成 SSH 模式，
依 Switching remote URLs from HTTPS to SSH 之步驟可順利更改設定，並成功執行 git push