2022q1 Homework1 (lab0)

tags: `Linux 核心設計` `成大課程`

contributed by < hbr890627 >

實驗環境

暫時使用 WSL (Windows Subsystem for Linux)

$ 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):                          12
On-line CPU(s) list:             0-11
Thread(s) per core:              2
Core(s) per socket:              6
Socket(s):                       1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           151
Model name:                      12th Gen Intel(R) Core(TM) i5-12400
Stepping:                        5
CPU MHz:                         2495.999
BogoMIPS:                        4991.99
Virtualization:                  VT-x
Hypervisor vendor:               Microsoft
Virtualization type:             full
L1d cache:                       288 KiB
L1i cache:                       192 KiB
L2 cache:                        7.5 MiB
L3 cache:                        18 MiB

進度

環境架設
- 暫時使用 WSL (Windows Subsystem for Linux)

~~2/20: 觀看lab0 解說影片~~

不需要在此標注日期，修改紀錄都在 HackMD 中。只是「觀看」不能算是成果，你至少該提出問題和摘要你所學到的事物。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

嘗試修改 queue.c

queue.c

q_new

struct list_head *q_new()
{
    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return NULL;

    e->value = NULL;
    INIT_LIST_HEAD(&e->list);
    return &e->list;
}

q_free

void q_free(struct list_head *l) {}

q_insert_head

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

注意書寫規範：中英文間用一個半形空白字元區隔。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

在 make check 後發現錯誤。

cmd> ih dolphin
ERROR: Need to allocate and copy string for new queue element

發現並未分配記憶體給 e->value ，修改程式碼。

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

在 make check 時不再發生 ERROR ，但無法 git commit 。

[2022-02-22T03:32:42.314Z] Following files need to be cleaned up:
queue.c
Dangerous function detected in /home/hbr/linux2022/lab0-c/queue.c
45:    strcpy(e->value, s);

Read 'Common vulnerabilities guide for C programmers' carefully.
    https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml

根據 https://security.web.cern.ch/recommendations/en/codetools/c.shtml ，將不安全的 strcpy ，改為 strncpy ，並補上字串的結尾\0。

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return false;
    e->value = malloc(sizeof(char) * (strlen(s) + 1));
    strncpy(e->value, s, strlen(s));
    *(e->value + strlen(s)) = '\0';
    list_add(&e->list, head);
    return true;
}

發現有些人使用 strdup 取代 strcpy ，雖然實作起來較方便，但這不包含在C的標準函式庫，不利於程式的移植性。
參考資料

q_insert_tail

大致上與 q_insert_head 差不多，將 list_add 改為 list_add_tail 。

bool q_insert_tail(struct list_head *head, char *s)
{
    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return false;
    e->value = malloc(sizeof(char) * (strlen(s) + 1));
    strncpy(e->value, s, strlen(s));
    *(e->value + strlen(s)) = '\0';
    list_add(&e->list, head);
    return true;
}

q_remove_head

要移除第一個節點，實際上就是要移除 head->next ，而在 list.h 中，有 list_first_entry 這個巨集可以使用，用來精簡程式碼。

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_first_entry(head, element_t, list);
    list_del(&node->list);

    if (sp) {
        strncpy(sp, node->value, bufsize);
        sp[bufsize - 1] = '\0';
    }
    return node;
}

q_remove_tail

與 q_remove_head 幾乎相同，將 list_first_entry 改為 list_last_entry 即可。

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

    element_t *node = list_last_entry(head, element_t, list);
    list_del(&node->list);

    if (sp) {
        strncpy(sp, node->value, bufsize);
        sp[bufsize - 1] = '\0';
    }
    return node;
}

q_release_element

此函式會被外部程式使用到，不用修改即可。

void q_release_element(element_t *e)
{
    free(e->value);
    free(e);
}

q_size

直接使用作業說明中的範例程式。
作業說明-lab0-牛刀小試

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

參考你所不知道的 C 語言: linked list 和非連續記憶體，使用龜兔賽跑的方式找到中間節點。

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;

    struct list_head *slow = head->next, *fast = head->next;
    while (fast != head && fast->next != head) {
        slow = slow->next;
        fast = fast->next->next;
    }

    list_del(slow);
    q_release_element(list_entry(slow, element_t, list));
    return true;
}

q_delete_dup

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

    element_t *entry, *safe;
    char *value = NULL;
    list_for_each_entry_safe (entry, safe, head, list) {
        if (strcmp(value, entry->value) == 0) {
            list_del(&entry->list);
            q_release_element(entry);
        } else {
            value = entry->value;
        }
    }

    return true;
}

此段程式碼會出現 You dereferenced a NULL or invalid pointer ，但一直找不到問題出現在哪，在參考 mm0809 後，發現只要使用""初始化 value 即可。

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

    element_t *entry, *safe;
    char *value = "";
    list_for_each_entry_safe (entry, safe, head, list) {
        if (strcmp(value, entry->value) == 0) {
            list_del(&entry->list);
            q_release_element(entry);
        } else {
            value = entry->value;
        }
    }

    return true;
}

q_swap

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head || list_empty(head))
        return;

    struct list_head *node = head->next;
    while (node != head && node->next != head) {
        struct list_head *next = node->next;
        list_del(node);
        list_add(node, next);
        node = node->next;
    }
}

q_reverse

想要實作 reverse 的其中一個方式，就是從頭將結點移出，再照順序將結點 enqueue 即可，但根據作業要求，在此函式中，不能再額外分配記憶體用來暫時儲存暫時移出的節點，在思考解決方式時，參考 mm0809 的方式，只要先固定第一個指標後，不斷將後面的節點移到前面即可。

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    struct list_head *tmp = head->next;
    for (struct list_head *node = tmp->next; tmp->next != head;
         node = tmp->next) {
        list_del(node);
        list_add(node, head);
    }
}

q_sort

使用到你所不知道的 C 語言: linked list 和非連續記憶體中的 mergesort ，但是其實作的是單向的鏈結串列，必須在 merge 結束後，將 prev 的節點補上。

/*
 * The sub-function of q_sort
 */
struct list_head *mergeTwoLists(struct list_head *h1, struct list_head *h2)
{
    struct list_head *head = NULL, **ptr = &head, **node;

    for (node = NULL; h1 && h2; *node = (*node)->next) {
        node = strcmp(list_entry(h1, element_t, list)->value,
                      list_entry(h2, element_t, list)->value) < 0
                   ? &h1
                   : &h2;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *) ((uintptr_t) h1 | (uintptr_t) h2);
    return head;
}

/*
 * The sub-function of q_sort
 */
struct list_head *mergesort(struct list_head *head)
{
    if (!head || !head->next)
        return head;

    // find middle node
    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(head), *right = mergesort(mid);
    return mergeTwoLists(left, right);
}

/*
 * Sort elements of queue in ascending order
 * No effect if q is NULL or empty. In addition, if q has only one
 * element, do nothing.
 */
void q_sort(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    head->prev->next = NULL;
    head->next->prev = NULL;

    struct list_head *sorted = mergesort(head->next);

    // link head & fix prev
    head->next = sorted;
    sorted->prev = head;
    struct list_head *temp = sorted;
    while (temp->next) {
        temp->next->prev = temp;
        temp = temp->next;
    }
    head->prev = temp;
    temp->next = head;
}