Try   HackMD

2022q1 Homework1 (lab0)

contributed by < garrod1227 >(網路旁聽)

tags: linux2022

實驗環境

$ uname -a
Linux AbcArchLinux 5.16.10-arch1-1 #1 SMP PREEMPT Wed, 16 Feb 2022 19:35:18 +0000 x86_64 GNU/Linux

$ gcc --version
gcc (GCC) 11.2.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Address sizes:                   39 bits physical, 48 bits virtual
Byte Order:                      Little Endian
CPU(s):                          8
On-line CPU(s) list:             0-7
Vendor ID:                       GenuineIntel
Model name:                      Intel(R) Core(TM) i5-10210U CPU @ 1.60GHz
CPU family:                      6
Model:                           142
Thread(s) per core:              2
Core(s) per socket:              4
Socket(s):                       1
Stepping:                        12
CPU max MHz:                     4200.0000
CPU min MHz:                     400.0000
BogoMIPS:                        4201.88
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 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 ssbd ibrs ibpb stibp ibrs_enhanced 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 arch_capabilities
L1d cache:                       128 KiB (4 instances)
L1i cache:                       128 KiB (4 instances)
L2 cache:                        1 MiB (4 instances)
L3 cache:                        6 MiB (1 instance)
NUMA node(s):                    1
NUMA node0 CPU(s):               0-7
Vulnerability Itlb multihit:     KVM: Mitigation: VMX unsupported
Vulnerability L1tf:              Not affected
Vulnerability Mds:               Not affected
Vulnerability Meltdown:          Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1:        Mitigation; usercopy/swapgs barriers and __user pointer sanitization
Vulnerability Spectre v2:        Mitigation; Enhanced IBRS, IBPB conditional, RSB filling
Vulnerability Srbds:             Mitigation; TSX disabled
Vulnerability Tsx async abort:   Not affected

作業要求

lab0

開發過程

首次 commit 就遇到錯誤

qtest.c:507:33: error: Uninitialized variable: item->value [uninitvar]
            slen = strlen(item->value) + 1;
                                ^
qtest.c:504:17: note: Assuming condition is false
            if (!tmp)
                ^
qtest.c:507:33: note: Uninitialized variable: item->value
            slen = strlen(item->value) + 1;
                                ^

Fail to pass static analysis.

由於不是使用建議的 Linux distribution 來寫作業，在首次 commit 時就遇到上述問題。
查了討論區與幾位同學前幾筆的 Git log 似乎未見到有人遭遇此問題。
調查後發現錯誤應該是來自 cppcheck ，決定暫時先用 suppression 忽略此錯誤，修改如下:

            slen = strlen(item->value) + 1;  // cppcheck-suppress uninitvar

Implemet operations on queue

初見 queue.c 時腦海一片空白沒有想法，不知從何下手所以決定先觀摩其他同學的作業。
概略的瀏覽 laneser、freshLiver 兩位同學的作業後，才慢慢浮現想法並動手開始實作。

q_new()

struct list_head *q_new()
{
    struct list_head *q = malloc(sizeof(struct list_head));
    if (q)
        INIT_LIST_HEAD(q);
    return q;
}

由於對於 list.h 還很陌生，實作過程中先想到的多是未使用 Linux 核心風格的鏈結串列 API的寫法。INIT_LIST_HEAD() 也是看到有同學使用才想到可以使用。

q_free()

void q_free(struct list_head *l)
{
    element_t *e;

    while (l && !list_empty(l)) {
        e = container_of(l->next, element_t, list);
        list_del(&e->list);
        q_release_element(e);
    }
    if (l)
        free(l);
}

container_of 的用法在你所不知道的 C 語言: linked list 和非連續記憶體有提到，這邊就直接拿來用。
過去在工作上曾看過類似的用法，例如：在 Base.h 詳細如下：

#define BASE_CR(Record, TYPE, Field)  ((TYPE *) ((CHAR8 *) (Record) - OFFSET_OF (TYPE, Field)))

初見這樣的用法時覺得很神奇，那時思索了好一會兒才理解其原理，這次再見到有種熟悉的感覺。

q_insert_head() and q_insert_tail()

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *e;

    if (!head)
        return false;
    e = malloc(sizeof(element_t));
    if (!e)
        goto err_ele;
    e->value = strdup(s);
    if (!e->value)
        goto err_str;
    list_add(&e->list, head);
    return true;
err_str:
    if (e->value)
        free(e->value);
    if (e)
        free(e);
err_ele:
    return false;
}

bool q_insert_tail(struct list_head *head, char *s)
{
    element_t *e;

    if (!head)
        return false;
    e = malloc(sizeof(element_t));
    if (!e)
        goto err_ele;
    e->value = strdup(s);
    if (!e->value)
        goto err_str;
    list_add_tail(&e->list, head);
    return true;
err_str:
    if (e->value)
        free(e->value);
    if (e)
        free(e);
err_ele:
    return false;
}

這兩個 function 的動作極為相似，只差在 elememt_t 是往頭串還是往尾串。
看見有同學把重複的 code 抽出來實作成一個獨立的 function ,這部分後續應該也可以做，目前先求功能可以正常動作，。
strdup() 過去不知有這 function 可使用，這次看到有同學用了，就學起來用了。
我在實作時想到可以使用 goto 來減少重複的 return false ,但是做完後感覺 code 好像也沒有精簡多少就是了。

q_remove_head() and q_remove_tail()

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

    element_t *e = container_of(head->next, element_t, list);
    if (sp) {
        strncpy(sp, e->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(head->next);
    return e;
}

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

    element_t *e = container_of(head->prev, element_t, list);
    if (sp) {
        strncpy(sp, e->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(head->prev);
    return e;
}

印象之前有看到名為 strncpy_s 的 function ，使用時不需要自己額外去補 null terminator ，但嘗試使用 strncpy_s 會遇到不認識此 function 的編譯錯誤，還是繼續使用 ‵strncpy` 。

q_size()

int q_size(struct list_head *head)
{
    struct list_head *n;
    int l = 0;

    if (!head || list_empty(head))
        return 0;
    list_for_each (n, head)
        l++;
    return l;
}

看過別人的 code 以後，這裡好像也寫不出什麼新花樣

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 →

q_delete_mid()

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    struct list_head *f, *b;

    if (!head || list_empty(head))
        return false;

    for (f = (head)->next, b = (head)->prev;; f = f->next, b = b->prev) {
        if (f == b || f == b->prev)
            break;
    }

    list_del(f);
    q_release_element(container_of(f, 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/
    struct list_head *l;
    element_t *b, *c;
    bool del_cur = false;

    if (!head)
        return false;

    l = head->next;
    while (l->next != head) {
        b = list_entry(l, element_t, list);
        c = list_entry(l->next, element_t, list);
        if (strcmp(b->value, c->value) == 0) {
            del_cur = true;
            list_del(&c->list);
            q_release_element(c);
        } else {
            l = l->next;
            if (del_cur) {
                del_cur = false;
                list_del(&b->list);
                q_release_element(b);
            }
        }
    }
    if (del_cur) {
        list_del(&b->list);
        q_release_element(b);
    }
    return true;
}

q_swap()

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    struct list_head *n;

    if (!head || list_empty(head))
        return;

    list_for_each (n, head) {
        if (n->next == head)
            break;
        struct list_head *fwn = n->next;
        list_del(n);
        list_add(n, fwn);
    }
}

q_reverse()

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

    n = head;
    do {
        t = n->next;
        n->next = n->prev;
        n->prev = t;
        n = t;
    } while (n != head);
}

q_sort()

void list_qsort(struct list_head *head)
{
    struct list_head list_less, list_greater;
    element_t *pivot;
    element_t *item = NULL, *is = NULL;

    if (list_empty(head) || list_is_singular(head))
        return;

    INIT_LIST_HEAD(&list_less);
    INIT_LIST_HEAD(&list_greater);

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

    list_for_each_entry_safe (item, is, head, list) {
        if (strcmp(item->value, pivot->value) <= 0)
            list_move_tail(&item->list, &list_less);
        else
            list_move(&item->list, &list_greater);
    }

    list_qsort(&list_less);
    list_qsort(&list_greater);

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

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    list_qsort(head);
}

list_qsort()先嘗試參考 sysprog21/linux-list 專案中的 quick-sort.c 程式碼

心得

距離要看到皮卡丘還有段路要走

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 →
，看到皮卡丘後似乎也還有段漫漫長路得走。

Last changed by 
 
Chun Yu Chen
0
344
Published on HackMD