2023q1 Homework1 (lab0)

contributed by < JoshuaLee0321 >

開發環境

$ gcc --version
    gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.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:         43 bits physical, 48 bits virtual
      Byte Order:            Little Endian
    CPU(s):                  12
      On-line CPU(s) list:   0-11
    Vendor ID:               AuthenticAMD
      Model name:            AMD Ryzen 5 2600X Six-Core Processor
        CPU family:          23
        Model:               8
        Thread(s) per core:  2
        Core(s) per socket:  6
        Socket(s):           1
        Stepping:            2
        Frequency boost:     enabled
        CPU max MHz:         3600.0000
        CPU min MHz:         2200.0000
        BogoMIPS:            7199.10
        Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht

目前分數

目前分數 100/100 都卡在一些memory的分配問題 2023/2/23 由於課程時發現 C 語言的前置處理器可用來定義 function-like macro，從而使程式碼更容易維護，所以本日會專注在定義macro 2023/2/27 完成 delete_dup 2023/2/27 make valgrind 中出現非常多錯誤，目前正在debug 2023/2/27 由於 `memcpy` 會報錯，所以把所有有關於 `memcpy` 的都改成 `strncpy`

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` 的過程

`q_new`

首先利用 malloc 分配空間給queue，考量到malloc有機會出錯，那先判斷是不是沒有分配成功，之後再利用 Linux 核心中的 INIT_LIST_HEAD 來把指針指向自己

struct list_head *q_new()
{
    struct list_head *head = malloc(1 * sizeof(struct list_head));
    if(!head)
        return NULL;
    INIT_LIST_HEAD(head);
    return head;
}

`q_free`

最剛開始的寫法，利用 list_for_each_safe run 過所有的 item，一個一個節點 release 但這樣會出先 segmentation fault

改進你的漢語描述。

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

void q_free(struct list_head *l)
{
    if (!l || list_empty(l)) {
        free(l);
        return;
    }
    struct list_head *it,*safe;
    list_for_each_safe(it, safe, l){
        element_t *tmp = list_entry(it, element_t, list);
        list_del(it);
        free(tmp);
    }
    free(list_entry(l, element_t, list));

    return;
}

後續改成 q_release_element 的內建API

void q_free(struct list_head *l)
{
    if(!l || list_empty(l)) return;
// ~~    struct list_head *it, *safe;
//     list_for_each_safe(it, safe, l){
//         q_release_element(it);
//     }~~
    /*以上為錯誤版本，已修正成以下版本*/
    list_for_each_entry_safe(it, safe, l, list) {
        q_release_element(it);
    }
    free(l)
}

更正版本：
element_t *it = NULL, *safe = NULL;
list_for_each_entry_safe(it, safe, l, list) { q_release_element(it); }

(更新)發現 safe 並沒有初始化成NULL 導致出錯，已修正
(更新)發現 list_for_each_entry_safe 以及 q_release_element 才可以把東西刪除完全

`q_insert_head` `q_insert_tail` `q_delete_head` `q_delete_tail`

(更)剛開始的實做如下，但這樣會發生我的實做並不是constant time，錯誤還有代釐清
(更)以上課後學習到的新知 (macro) function 為基準重新製作了 q_insert_##type 在macro 中
(更)已把 q_insert 以及 q_remove 類型的都把它做成macro 方便維護，除此之外還找到了 q_remove_macro 中少加入 if(list_empty(head)) 而導致 segmentation fault

macro 如下

#define q_insert_macro(type, func)                                  \
    bool q_insert_##type(struct list_head *head, char *s)           \
    {                                                               \
        if (!head)                                                  \
            return false;                                           \
        element_t *new_node = malloc(1 * sizeof(*new_node));        \
        if (!new_node)                                              \
            return false;                                           \
        new_node->value = malloc((strlen(s) + 1) * sizeof(char));   \
        if (!new_node->value) {                                     \
            q_release_element(new_node);                            \
            return false;                                           \
        }                                                           \
        memcpy(new_node->value, s, strlen(s) + 1);                  \
        func(&new_node->list, head);                                \
        return true;                                                \
    }                                                               \
#define q_remove_macro(type, func)                               \
    element_t *q_remove_##type(struct list_head *head, char *sp, \
                               size_t bufsize)                   \
    {                                                            \
        if (!head || list_empty(head))                           \
            return NULL;                                         \
        element_t *del = func(head, element_t, list);            \
        list_del(&del->list);                                    \
        if (sp != NULL) {                                        \
            memcpy(sp, del->value, bufsize - 1);                 \
            sp[bufsize - 1] = '\0';                              \
        }                                                        \
        return del;                                              \
    }

而實際上我就可以只利用四行程式碼來實作

/* Insert an element at head of queue */
q_insert_macro(head, list_add);

/* Insert an element at tail of queue */
q_insert_macro(tail, list_add_tail);

/* Remove an element from head of queue */
q_remove_macro(head, list_first_entry);

/* Remove an element from tail of queue */
q_remove_macro(tail, list_last_entry);

如此一來 insert_head 跟 insert_tail 都可以在組譯階段被完成，如此一來可以節省空間之外還可以更好的維護兩個function
不過目前還在找出為甚麼此function 無法在constant time 完成，之後會研讀論文

`q_delete_dup`

利用 linux/list.h 中的 API 跑過迴圈；要注意的事情是，這個function 必須把重複的東西通通刪除掉。由於list_for_each_safe 中的 safe 可以當作 next 來使用，如此一來我們只要
1. 跑過 head 中的所有元素
2. 使用 iterator it 來觀察是否當前元素與下個元素相同
3. 利用 bool not_finished 變數來記錄是否要把當前 it 刪除
  以下為實作code

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_is_singular(head))
        return false;
    struct list_head *it, *safe = NULL;
    bool not_finished = false;
    list_for_each_safe (it, safe, head) {
        element_t *prev = list_entry(it, element_t, list);
        element_t *cur = list_entry(safe, element_t, list);
        if (!strcmp(prev->value, cur->value)) {
            not_finished = true;
            list_del(it);
            q_release_element(prev);
            if (safe->next == (head)) {
                list_del(safe);
                q_release_element(cur);
                break;
            }
        } else if (not_finished) {
            not_finished = false;
            list_del(it);
            q_release_element(prev);
        }
    }

    return true;
}

`q_size`

已經由 jserv 老師撰寫好了

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`

基本上這個題目有兩種作法，一種先找出 queue 的長度除以2之後給定一個int cnt 去計算這個list目前到哪裡，但這個實做方法有一個問題，它會花到O(2N)的時間
- N = 得到 size 的時間
- N = traverse 到中間的時間
第二個作法就是利用兩種不同方向或速度的指標，而我的實做方法就是利用一個每一次只會往後走一歩的 single_p 以及每一次會往後走兩步的 double_p，在double走到底的時候single會直接在中間
- 如此一來只需要直接把 single_p 給移除掉即可

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 *single_p, *double_p;
    single_p = double_p = head->next;
    while(double_p != (head) && double_p->next != (head)) {
        single_p = single_p->next;
        double_p = double_p->next->next;
    }
    list_del_init(single_p);
    q_release_element(list_entry(single_p,element_t,list));
    return true;
}

`q_swap`

在 swap-nodes-in-pairs 中，可以使用 iterative 跟 recursive 的方法實做，而因為有linux kernel 的 API，我選擇使用 iterative 的作法
- 使用 it 當作每一次走過的node
- 每次 it 往前走一步
- 每次 it 跟 it->next 互換
  如此一來就可以達到每兩個 node 互相交換了

void q_swap(struct list_head *head)
{
    if(!head || list_empty(head) || head->next->next == head) return;
    struct list_head *it = head->next;

    while(it != (head) && it->next != (head)) {
        list_move(it,it->next);
        it = it->next;

    }
    // https://leetcode.com/problems/swap-nodes-in-pairs/
}

`q_reverse`

q_reverse 如果使用 Linux 核心的 api 就會非常簡單
- 儘需要走過這整個串列，並且每一次都把當前的node放到最前方即可

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

`q_sort`

參考你所不知道的 c 語言: linked list 和非連續記憶體及 Linked List Sort 中提到的Merge Sort ，並以 LiChiii 的程式碼為實作。

`Valgrind`

# Explicitly disable sanitizer(s)
$ make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/joshua/linux2023/lab0-c'
rm -f qtest.o report.o console.o harness.o queue.o random.o dudect/constant.o dudect/fixture.o dudect/ttest.o shannon_entropy.o linenoise.o web.o .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d .shannon_entropy.o.d .linenoise.o.d .web.o.d *~ qtest /tmp/qtest.*
rm -rf .dudect
rm -rf *.dSYM
(cd traces; rm -f *~)
  CC    qtest.o
  CC    report.o
  CC    console.o
  CC    harness.o
  CC    queue.o
  CC    random.o
  CC    dudect/constant.o
  CC    dudect/fixture.o
  CC    dudect/ttest.o
  CC    shannon_entropy.o
  CC    linenoise.o
  CC    web.o
  LD    qtest
make[1]: Leaving directory '/home/joshua/linux2023/lab0-c'
cp qtest /tmp/qtest.83iQ10
chmod u+x /tmp/qtest.83iQ10
sed -i "s/alarm/isnan/g" /tmp/qtest.83iQ10
scripts/driver.py -p /tmp/qtest.83iQ10 --valgrind
---     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, remove_head, reverse and merge
---     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, sort, descend and reverseK
---     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
---     trace-14-perf   6/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           100/100

Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.83iQ10 --valgrind -t <tid>

debug 紀錄

2 / 23

目前一直卡在 q_insert 的function 並沒有在constant time 處理完畢
除此之外，每一次free佇列都會發生一些問題

(更新) 發先是 q_free 中的safe 沒有初始化

2 / 27

測試時一直發現 trace - 17 一直報告不是常數時間。同時我也很確定我的實作方法為constant time，而經由閱讀 KHLEE 的實作方法，更改了 dudect/constant.c 以及 dudect/fixture 的計算方法後才得到目前的滿分

2023q1 Homework1 (lab0)

開發環境

目前分數

開發 queue.c 的過程

q_new

q_free

q_insert_head q_insert_tail q_delete_head q_delete_tail

macro 如下

q_delete_dup

q_size

q_delete_mid

q_swap

q_reverse

q_sort

Valgrind