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 中,可以使用 iterativerecursive 的方法實做,而因為有linux kernel 的 API,我選擇使用 iterative 的作法
    • 使用 it 當作 每一次走過的node
    • 每次 it 往前走一步
    • 每次 itit->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

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 的計算方法後才得到目前的滿分