2022q1 Homework1 (lab0)

contributed by < kaiweike >

實驗環境

剛開始的實驗環境

$ 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):                          4
On-line CPU(s) list:             0-3
Thread(s) per core:              2
Core(s) per socket:              2
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           61
Model name:                      Intel(R) Core(TM) i5-5257U CPU @ 2.70GHz
Stepping:                        4
CPU MHz:                         1405.132
CPU max MHz:                     3100.0000
CPU min MHz:                     500.0000
BogoMIPS:                        5399.87
Virtualization:                  VT-x
L1d cache:                       64 KiB
L1i cache:                       64 KiB
L2 cache:                        512 KiB
L3 cache:                        3 MiB
NUMA node0 CPU(s):               0-3

上面的環境一直故障，後來換成這個實驗環境

$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   48 bits physical, 48 bits virtual
CPU(s):                          4
On-line CPU(s) list:             0-3
Thread(s) per core:              2
Core(s) per socket:              2
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       AuthenticAMD
CPU family:                      21
Model:                           16
Model name:                      AMD A8-4500M APU with Radeon(tm) HD Graphics
Stepping:                        1
Frequency boost:                 enabled
CPU MHz:                         1511.772
CPU max MHz:                     1900.0000
CPU min MHz:                     1400.0000
BogoMIPS:                        3793.17
Virtualization:                  AMD-V
L1d cache:                       32 KiB
L1i cache:                       128 KiB
L2 cache:                        4 MiB
NUMA node0 CPU(s):               0-3

開發紀錄

$ make test
  CC	queue.o
  LD	qtest
scripts/driver.py -c
---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---	trace-01-ops	5/5
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
---	trace-02-ops	6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
---	trace-03-ops	6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, swap, and sort
---	trace-04-ops	6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
---	trace-05-ops	6/6
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, and sort
---	trace-06-ops	6/6
+++ TESTING trace trace-07-string:
# Test of truncated strings
---	trace-07-string	6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---	trace-08-robust	6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---	trace-09-robust	6/6
+++ TESTING trace trace-10-robust:
# Test operations on NULL queue
---	trace-10-robust	6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---	trace-11-malloc	6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
---	trace-12-malloc	6/6
+++ TESTING trace trace-13-malloc:
# Test of malloc failure on new
---	trace-13-malloc	6/6
+++ TESTING trace trace-14-perf:
# Test performance of insert_tail, reverse, and sort
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
---	trace-14-perf	0/6
+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
---	trace-15-perf	6/6
+++ TESTING trace trace-16-perf:
# Test performance of insert_tail
---	trace-16-perf	6/6
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---	TOTAL		94/100
make: *** [Makefile:56: test] Error 1

基礎概念

typeof
offsetof (參考你所不知道的 C 語言: linked list 和非連續記憶體-Linked list 在 Linux 核心原始程式碼-簡化的實作)
offsetof(type, member)
=>可得到成員的位址減去 struct 的起始位址
container_of (參考 Linux 核心原始程式碼巨集: container_of)
#define container_of(ptr, type, member)
=> 可得到 type 結構的 address
Common vulnerabilities guide for C programmers
“ Most vulnerabilities in C are related to buffer overflows external link and string manipulation. ”
- ~~gets()~~ -> fgets()
- ~~strcpy()~~ -> strlcpy() or strncpy()
- ~~strcat()~~ -> strncat()
- ~~strcmp()~~ -> strncmp()
- ~~sprintf()~~ -> snprintf()
- string formatting
  -> always hardcode the format string. At least, never let it come directly from any user's input.
- file opening

實做佇列(queue.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 →

jserv

q_new

最初的寫法

// Create empty queue.
// Return NULL if could not allocate space.

struct list_head *q_new()
{
    struct list_head *q = malloc(sizeof(struct list_head));
    if (q != NULL)
        q->next = q->prev = q;
    return q;
}

參考 2020leon ，並改寫為更簡潔的寫法：

利用 malloc 分配記憶體空間。
利用 INIT_LIST_HEAD 初始化 struct list_head 物件成員。

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

q_free

這個寫法一直出錯

void q_free(struct list_head *l)
{
    element_t *entry, *safe;
    if(!l || list_empty(l))
        return;
    list_for_each_entry_safe( entry, safe, l, list)
        q_release_element(entry);
    free(l);
}

後來刪掉 if 判斷中的 list_empty(l) 就好了，
因為當 list_empty() = !0 時表示 list is empty，
但 empty 還是指向有效結構，開頭(head)的值為NULL(參考 K01: lab0)。

void q_free(struct list_head *l)
{
    element_t *entry, *safe;
    if(!l)
        return;
    list_for_each_entry_safe( entry, safe, l, list)
        q_release_element(entry);
    free(l);
}

q_insert_head

這個寫法一直出現錯誤

// Attempt to insert element at head of queue.
// Return true if successful.
// Return false if q is NULL or could not allocate space.
// Argument s points to the string to be stored.
// The function must explicitly allocate space and copy the string into it.
bool q_insert_head(struct list_head *head, char *s)
{
    element_t n;
    n.value = s;
    if(list_empty(head))
        return false;
    list_add(&n.list, head);
    return true;
}

參考 freshLiver 的寫法後，
發現原來是少了 malloc 和 memcpy 這兩個步驟，沒有配置指定大小的記憶體空間。

另外，發現 list_empty != null，

“ 若你有空的紅包袋，裡面的東西是 empty;
若你連紅包袋都沒有，就可以說 NULL; ” (參考 K01: lab0)。

bool q_insert_head(struct list_head *head, char *s)
{
    if(!head)
       return false;

    element_t *n = malloc(sizeof(element_t));
    if(!n)
        return false;

    n->value = malloc(strlen(s)+1);
    if(!n->value)
        return false;

    memcpy(n->value, s, strlen(s));
    n->value[strlen(s)] = '\0';

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

參考 freshLiver 的寫法，
進一步使用 strdup 簡化 malloc、 memcpy 和 value[strlen(s)] = '\0' 的操作:

bool q_insert_head(struct list_head *head, char *s)
{
    if(!head)
       return false;

    element_t *n = malloc(sizeof(element_t));
    if(!n)
        return false;

    n->value = strdup(s);
    if (!n->value) {
        free(n);
        return false;
    }

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

q_insert_tail

操作邏輯和 q_insert_head 一樣，只是將 list_add 更換成 list_add_tail

bool q_insert_tail(struct list_head *head, char *s)
{
    if(!head)
       return false;

    element_t *n = malloc(sizeof(element_t));
    if(!n)
        return false;

    n->value = strdup(s);
    if (!n->value) {
        free(n);
        return false;
    }

    list_add_tail(&n->list, head);
    return true;
}

q_remove_head

// Attempt to remove element from head of queue.
// Return target element.
// Return NULL if queue is NULL or empty.
// If sp is non-NULL and an element is removed, copy the removed string to *sp
// (up to a maximum of bufsize-1 characters, plus a null terminator.)
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if(!head || list_empty(head))
        return NULL;

    element_t *n = list_first_entry(head, element_t, list);
    list_del(head->next);

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

    return n;
}

q_remove_tail

// Attempt to remove element from tail of queue.
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if(!head || list_empty(head))
        return NULL;

    element_t *n = list_last_entry(head, element_t, list);
    list_del(head->prev);

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

q_delete_mid

這樣的寫法有誤：

// Delete the middle node in list.
// The middle node of a linked list of size n is the
// ⌊n / 2⌋th node from the start using 0-based indexing.
// If there're six element, the third member should be return.
// Return true if successful.
// Return false if list is NULL or empty.

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    
    struct list_head *front = head->next;
    struct list_head *back = head->prev;
    while (front != back && front->next != back)
    {
        front = head->next;
        back = back->prev;
    }

    list_del(front);
    return true;
}

參考 LJP-TW 的寫法後修改為：

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;

    if (list_is_singular(head)){
        element_t *element = q_remove_head(head, NULL, 0);
        q_release_element(element);
        return true;
    }
    
    struct list_head *twoStep = head->next;
    struct list_head *oneStep = head->next;

    while (twoStep != head && twoStep->next != head){
        twoStep = twoStep->next->next;
        oneStep = oneStep->next;
    }

    element_t *element = list_entry(oneStep, element_t, list);    
    list_del(oneStep);
    q_release_element(element);

    return true;
}

q_delete_dup

參考 eric88525 的寫法

// Delete all nodes that have duplicate string,
// leaving only distinct strings from the original list.
// Return true if successful.
// Return false if list is NULL.
//
// Note: this function always be called after sorting, in other words,
// list is guaranteed to be sorted in ascending order.
bool q_delete_dup(struct list_head *head)
{
    if(!head || list_empty(head))
        return false;
    
    struct list_head **p = &(head->next);
    struct list_head *curr = head->next;
    struct list_head *temp = NULL;
    
    while(curr != head && curr->next != head){
        if(strcmp(container_of(curr, element_t, list)->value,
                 container_of(curr->next, element_t, list)->value) == 0){
            do{
                temp = curr;
                curr = curr->next;
                list_del(tmp);
                q_release_element(container_of(temp, element_t, list));
            }while(curr->next != head &&
                  strcmp(container_of(curr, element_t, list)->value,
                        container_of(curr->next, element_t, list)->value) == 0);                  
        }
        
        p = &((*p)->next);
        curr = curr->next;
    }
    
    return true;
}

q_swap

// Attempt to swap every two adjacent nodes.
void q_swap(struct list_head *head)
{
    if(!head || list_empty(head))
        return;
    
    struct list_head *curr = head->next;
    struct list_head *next = NULL;
    while(curr && curr->next && curr != head && curr->next != head){
        next = curr->next;
        list_del(next);
        list_add_tail(next, curr);
        curr = curr->next;
    }
}

q_reverse

// Reverse elements in queue
// No effect if q is NULL or empty
// This function should not allocate or free any list elements
// (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
// It should rearrange the existing ones.
void q_reverse(struct list_head *head)
{
    if(!head|| list_empty(head))
        return;
    
    struct list_head *prev = head->prev;
    struct list_head *curr head;
    struct list_head *next NULL;
    
    while(next != head){
        next = curr->next;
        curr->next = prev;
        curr->prev = next;
        prev = curr;
        curr = next;
    }
}

參考 kdvnt 更精簡的方法：

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head)
        list_move(node, head);
}

q_sort

參考你所不知道的 C 語言: linked list 和非連續記憶體- MergeSort的實作

實做遞迴版本的 MergeSort:

// 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.
struct list_head *merge(struct list_head *L1, struct list_head *L2)
{
    struct list_head *head = NULL, **ptr = &head;

    while (L1 && L2) {
        if (strcmp(list_entry(L1, element_t, list)->value,
                   list_entry(L2, element_t, list)->value) < 0) {
            *ptr = L1;
            L1 = L1->next;
        } else {
            *ptr = L2;
            L2 = L2->next;
        }
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *) ((unsigned long int) L1 | (unsigned long int) L2);
    return head;
}

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

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

    struct list_head *L1 = mergesort(slow);
    struct list_head *L2 = mergesort(fast);

    return merge(L1, L2);
}

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

    head->prev->next = NULL;
    head->next = mergesort(head->next);

    struct list_head *prev = head, *cur = head->next;
    for (; cur != NULL; prev = cur, cur = cur->next) {
        cur->prev = prev;
    }
    prev->next = head;
    head->prev = prev;
}

測項 14 和 15 指出效能不夠好

+++ TESTING trace trace-14-perf:
# Test performance of insert_tail, reverse, and sort
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
---	trace-14-perf	0/6

+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
---	trace-15-perf	6/6

推測可能是因為執行遞迴需要多次函式呼叫，如果呼叫層數比較深，增加的堆疊處理會影響效能。

實做迭代版本的 MergeSort:

struct list_head *merge(struct list_head *L1, struct list_head *L2)
{
    struct list_head *head = NULL, **ptr = &head;

    while (L1 && L2) {
        if (strcmp(list_entry(L1, element_t, list)->value,
                   list_entry(L2, element_t, list)->value) < 0) {
            *ptr = L1;
            L1 = L1->next;
        } else {
            *ptr = L2;
            L2 = L2->next;
        }
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *) ((unsigned long int) L1 | (unsigned long int) L2);
    return head;
}

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

    int top = 0;
    int listsSize = 0;
    struct list_head *stack[1000] = {NULL};
    struct list_head *lists[100000] = {NULL};
    stack[top] = head;

    while(top >= 0){
        struct list_head *left = stack[top--];

        if(left){
            struct list_head *slow = left;
            struct list_head *fast;

            for(fast = left->next; fast && fast->next; fast = fast->next->next)
                slow = slow->next;
            
            struct list_head *right = slow->next;
            slow->next = NULL;

            stack[++top] = left;
            stack[++top] = right;
        }else{
            lists[listsSize++] = stack[top--];
        }
    }

    while(listsSize>1){
        for(int i = 0, j = listsSize - 1; i < j; i++, j--)
            lists[i] = merge(lists[i], lists[j]);
        listsSize = (listsSize + 1) / 2;
    }

    head = lists[0];
    return head;
}

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

    head->prev->next = NULL;
    head->next = mergesort_iter(head->next);

    struct list_head *curr = head, *next = head->next;
    while(next){
        next->prev = curr;
        curr = next;
        next = next->next;
    }

    curr->next = head;
    head->prev = curr;
}

Segmentation fault..改寫中

+++ TESTING trace trace-14-perf:
# Test performance of insert_tail, reverse, and sort
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
---	trace-14-perf	0/6

+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass

實做洗牌(shuffle)

實做伺服器(web)

參考資訊

linked_list https://haogroot.com/2019/12/12/漫談-linked-list-在-linux-kernel-中的不一樣/ https://www.cntofu.com/book/46/linux_kernel/20.md https://myao0730.blogspot.com/2016/12/linux.html http://adrianhuang.blogspot.com/2007/10/linux-kernel-listhead.html

container_of
https://hackmd.io/@sysprog/linux-macro-containerof
http://adrianhuang.blogspot.com/2010/01/linux-kernel-containerof.html
https://myao0730.blogspot.com/2016/09/linuxcontainerof-offsetof.html
https://zhuanlan.zhihu.com/p/54932270
https://www.gushiciku.cn/pl/ggOa/zh-tw
https://blog.csdn.net/wukongmingjing/article/details/81746071

不用花太多時間 Google 搜尋，大部分需要細讀的材料，我已經列在教材和作業說明中，請確保你閱讀「每一段落」及其指向的「每個」超連結。

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

Jim Huang

2022/04/17 17:46:05

```c void q_free(struct list_head *l) { element_t *entry, *safe; if(!l) return; list_for_each_entry_safe( entry, safe, l, list) q_release_element(entry); free(l); } ```

對應的解釋在哪？ (Edited)

kaiweike

2022/06/30 09:08:36

已補上對應的解釋

2022/04/17 17:46:42

```c // Attempt to insert element at head of queue. // Return true if successful. // Return false if q is NULL or could not allocate space. // Argument s points to the string to be stored. // The function must explicitly allocate space and copy the string into it. bool q_insert_head(struct list_head *head, char *s) { element_t n; n.value = s; if(list_empty(head)) return false; list_add(&n.list, head); return true; } ```

不要將錯誤歸結在「寫法」，而是要用「工程」的術語來探討，否則你永遠只是邯鄲學步！ (Edited)