Try   HackMD

2022q1 Homework1 (lab0)

contributed by < Korin777 >

開發環境

$ 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):                          8
On-line CPU(s) list:             0-7
Thread(s) per core:              2
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           142
Model name:                      Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
Stepping:                        10
CPU MHz:                         1800.000
CPU max MHz:                     3400.0000
CPU min MHz:                     400.0000
BogoMIPS:                        3600.00
Virtualization:                  VT-x
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        6 MiB
NUMA node0 CPU(s):               0-7

queue.c 實作

q_new

  • 一開始我是直接 malloc 一個 head 並回傳 , 後來發現這樣就無法透過 list.h 所提供的 list_empty 來判斷 list 是否為空 , 且這樣的 linked list 也並不是雙向環狀的
  • 後來透過 list.h 提供的 INIT_LIST_HEAD 將 head 的 prev 及 next 都指向自己 , 完成雙向環狀的 linked list
struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (!head)
        return NULL;
    INIT_LIST_HEAD(head);
    return head;
}

q_free

  • 透過 list.h 提供的 list_for_each_entry_safe 遍歷 list 並釋放每個 entry 所配置過的記憶體空間
  • list 的每個 entry 皆為 element_t
  • 一個 entry 要先釋放 element_t ->value 在釋放 element_t
  • 最後還要再釋放 list 的 head , 因為它並不是 list 中的一個 entry 而是用來當作 list 的開頭
void q_free(struct list_head *l)
{
    if (!l)
        return;
    element_t *ele, *tmpele;
    list_for_each_entry_safe (ele, tmpele, l, list)
        free(ele->value), free(ele);
    free(l);
}

q_insert_head

  • malloc 一個 element_t 作為 list 中一個 entry
  • element_t->value 的 size 為 strlen(s)+1 , 最後一個字元用來存放空字元 \0
  • element_t->list 是 struct list_head 的型態 , 為實際 linked list 互相連接的節點 , 透過 list.h 提供的 list_add 來將它加在 linked list 的最前面(不包含head)
  • 當配置 element_t ->value 記憶體失敗時 , 要釋放element_t 的記憶體 , 才不會產生 memory leak
  • 特別用一個 len 變數來儲存 s 的長度 , 減少重複呼叫 strlen 所花的時間 , 不過在測試 time complexity 有時還是會沒通過
  • 後來發現 time complexity 沒過得原因在 q_reverse 寫錯了
bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *ele = malloc(sizeof(element_t));
    if (!ele)
        return false;
    int len = strlen(s);
    ele->value = malloc(len + 1);
    if (!ele->value) {
        free(ele);
        return false;
    }
    strncpy(ele->value, s, len);
    ele->value[len] = '\0';
    list_add(&ele->list, head);
    return true;
}

q_insert_tail

  • 和 q_insert_head 差再需用 list.h 提供的list_add_tail 來連接節點
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *ele = malloc(sizeof(element_t));
    if (!ele)
        return false;
    int len = strlen(s);
    ele->value = malloc(len + 1);
    if (!ele->value) {
        free(ele);
        return false;
    }
    strncpy(ele->value, s, len);
    ele->value[len] = '\0';
    list_add_tail(&ele->list, head);
    return true;
}

q_remove_head

  • 透過 list.h 所提供的 list_entry , 有了包含在 element_t 中的 list 記憶體位置 , 就能算出此 element_t 的記憶體位置
  • 將 element_t->value 複製到 sp 並將最後一個字元設為空字元 \0
  • 透過 list.h 所提供的 list_del , 將節點移除
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    struct list_head *node = head->next;
    element_t *ele = list_entry(node, element_t, list);
    if (sp) {
        strncpy(sp, ele->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(node);
    return ele;
}

q_remove_tail

  • 和 q_remove_head 差在移除的節點為 head->prev
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    struct list_head *node = head->prev;
    element_t *ele = list_entry(node, element_t, list);
    if (sp) {
        strncpy(sp, ele->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(node);
    return ele;
}

q_size

  • 透過 list.h 提供的 list_for_each 遍歷 linked list 來取長度
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

  • h 一開始為第一個節點 , t 一開始為最後一個節點
  • h 一直往後走 , t 則一直往前走 , 當兩者相同或 h->next 與 t 相同時 , h 恰好為中點
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 *h = head->next, *t = head->prev;
    while (h != t) {
        if (h->next == t)
            break;
        h = h->next, t = t->prev;
    }
    element_t *ele = list_entry(h, element_t, list);
    list_del(h);
    free(ele->value), free(ele);
    return true;
}

q_delete_dup

  • tmp 為字元指標 , 配置記憶體前 tmp 不為 NULL 要先釋放 tmp 的記憶體 , 以免產生 memory leak
  • tmp為 NULL 或 tmp 和當前 entry 的字串不同 , 就看下個 entry 的字串是否與當前字串一樣 , 來判斷是否該移除當前節點及釋放對應的記憶體
  • tmp 和當前 entry 的字串相同 , 直接移除當前節點及釋放對應的記憶體
  • 若 tmp 最後不為 NULL 要釋放 tmp 記憶體
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head)
        return false;
    char *tmp = NULL;
    element_t *ele, *tmpele;
    list_for_each_entry_safe (ele, tmpele, head, list) {
        if (!tmp || strcmp(tmp, ele->value) != 0) {
            if (ele->list.next && ele->list.next != head) {
                element_t *elen = list_entry(ele->list.next, element_t, list);
                if (strcmp(elen->value, ele->value) == 0) {
                    if (tmp)
                        free(tmp);
                    tmp = malloc(sizeof(ele->value));
                    strncpy(tmp, ele->value, strlen(ele->value));
                    list_del(&ele->list);
                    free(ele->value), free(ele);
                }
            }
        } else {
            list_del(&ele->list);
            free(ele->value), free(ele);
        }
    }
    if (tmp)
        free(tmp);
    return true;
}

q_swap

  • li 為相鄰 node 的第一個 node , tmp 則為第二個 node , 並將兩者互換
  • 當 li 為 head 或 tmp 為 head , 表示已經沒有相鄰的 node 需要互換
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *li = head->next, *tmp;
    while (li != head) {
        tmp = li->next;
        if (tmp == head)
            break;
        li->prev->next = tmp;
        tmp->next->prev = li;
        li->next = tmp->next;
        tmp->next = li;
        tmp->prev = li->prev;
        li->prev = tmp;
        li = li->next;
    }
}

q_reverse

  • h 一開始為第一個節點 , t 一開始為最後一個節點
  • h 一直往後走 , t 則一直往前走 , 因為 h 跟 t 互換 , h 要更新為 t->next , t 則更新為 h->next
  • 當 h 與 t 相同或 t->next->prev 與 t 相同 , linked list 已反轉完畢
void q_reverse(struct list_head *head)
{
    struct list_head *tmp, *htmp, *ttmp;
    if (!head || list_is_singular(head))
        return;
    struct list_head *h = head->next, *t = head->prev;
    head->next = t;
    head->prev = h;
    while (h != t) {
        htmp = h->next;
        ttmp = t->prev;
        tmp = h->next;
        h->next = h->prev;
        h->prev = tmp;
        tmp = t->next;
        t->next = t->prev;
        t->prev = tmp;
        if (t->next->prev == t)
            break;
        h = htmp, t = ttmp;
    }
    if (h == t) {
        tmp = h->prev;
        h->prev = h->next;
        h->next = tmp;
    }
}
  • 原本以為 trace-17-complexity 有時會沒 pass 的原因只跟 q_insert_tail, q_insert_head, q_remove_tail, q_remove_head 有關 , 後來發現原來是我 q_reverse 寫錯了 , t->prev 是 t->next 才對 , 而 tmp 的宣告也是多餘的
  • 不過上面那個錯的 reverse 還是能成功將 reverse 後的 linke list show 出來 , 儘管前半段 linked list 節點的 prev 應該都是錯的
  • 後來推上 github trace-17-complexity 還是沒過 , 在本地端測試確實有時不會過 , 還要在看看是那出了問題
void q_reverse(struct list_head *head)
{
    struct list_head *htmp, *ttmp;
    if (!head || list_is_singular(head))
        return;
    struct list_head *h = head->next, *t = head->prev;
    head->next = t;
    head->prev = h;
    while (h != t) {
        htmp = h->next;
        ttmp = t->prev;
        h->next = h->prev;
        h->prev = htmp;
        t->prev = t->next;
        t->next = ttmp;
        if (t->next->prev == t)
            break;
        h = htmp, t = ttmp;
    }
    if (h == t) {
        htmp = h->prev;
        h->prev = h->next;
        h->next = htmp;
    }
}

q_sort

  • 參考 geekforgeek 實作出適用於 Circular Doubly Linked List 的遞迴法（Top-down） Merge Sort
  • 在 Test performance 無法 pass , 在 qtest 跑 trace-14-perf.cmd 的測資 ， 發現會 Segmetation Fault
  • 自己測試後發現 , list 的 size 在約 1400000 就會 Segmetation Fault , 應該是 function 遞迴太多次的關係 , 所以下面改用迭代法（Bottom-up）實作
struct list_head *merge(struct list_head *first, struct list_head *second)
{
    if (!first)
        return second;
    if (!second)
        return first;
    element_t *elef = list_entry(first,element_t,list), *eles = list_entry(second,element_t,list);
    // elef->value < eles->value
    if(strcmp(elef->value,eles->value) < 0)
    {
        first->next = merge(first->next,second);
        first->next->prev = first;
        first->prev = NULL;
        return first;
    }
    else // elef->value >= eles->value
    {
        second->next = merge(first,second->next);
        second->next->prev = second;
        second->prev = NULL;
        return second;
    }
}
struct list_head *split(struct list_head *head)
{
    struct list_head *fast = head, *slow = head;
    while (fast->next && fast->next->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    struct list_head *temp = slow->next;
    slow->next = NULL;
    return temp;
}
struct list_head *mergeSort(struct list_head *head)
{
    if (!head || !head->next) {
        return head;
    }
    struct list_head *second = split(head);
    head = mergeSort(head);
    second = mergeSort(second);
    return merge(head, second);
}
  • 改用迭代法（Bottom-up）實作
  • 在 Test performance 還是無法 pass , 在 qtest 跑 trace-14-perf.cmd 的測資 ， 雖然解決了 Segmentation Fault 的問題 卻產生了 time limit exceeded
  • 因為 linked list 記憶體並不連續 , 無法像陣列那樣直接取得某個位置的值 , 而必須慢慢往後走 , 導致當要 merge 兩個子 list 前會產生許多很長的走訪
  • 所以我沿用原本的遞迴 merge sort ， 但將 merge 的過程改為迭代
void merge_iterative(struct list_head *first, struct list_head *second, int
ls, int rs) {
    int l = 0, r = 0;
    element_t *elef = list_entry(first,element_t,list), *eles = list_entry(second,element_t,list); while(l < ls && r < rs) {
        if(strcmp(elef->value,eles->value) < 0)
        {
            first = first->next;
            l++;
            if(l < ls)
                elef = list_entry(first,element_t,list);
        }
        else // elef->value >= eles->value
        {
            struct list_head *tmp = second->next;
            list_del(second);
            list_add_tail(second,first);
            second = tmp;
            r++;
            if(r < rs)
                eles = list_entry(second,element_t,list);
        }
    }
}

void mergeSort_iterative(struct list_head *head,int size)
{
    int sz = 1,n = size;
    while(sz < n) {
        struct list_head *f = head->next,*s = head->next, *nf = f, *ns;
        int i = 0;
        int j;
        for(j = 0; j < sz; j++)
            s = s->next;
        ns = s;
        while(i < n-1) {
            if(size - i <= sz)
                break;
            int l = sz, r = sz;
            if(n-i-sz < sz)
                r = n-i-sz;
            for(j = 0; j < sz*2; j++) {
                if(nf->next)
                    nf = nf->next;
                if(ns->next)
                    ns = ns->next;
            }
            merge_iterative(f,s,l,r);
            f = nf;
            s = ns;
            i += sz*2;
        }
        sz += sz;
    }
}
  • 將 merge 改為迭代的遞迴 mergesort , 總算通過 Test performance
  • merge 用來將兩個子 list 合併 , 回傳合併後的head
  • split 將 list 切半為兩個子 list
struct list_head *merge(struct list_head *first, struct list_head *second)
{
    if (!first)
        return second;
    if (!second)
        return first;
    struct list_head *tmphead = NULL, *tf = first, *ts = second;
    element_t *elef = list_entry(first, element_t, list),
              *eles = list_entry(second, element_t, list);
    while (first && second) {
        if (strcmp(elef->value, eles->value) < 0) {
            if (!tmphead)
                tmphead = first;
            tf = first;
            first = first->next;
            if (first)
                elef = list_entry(first, element_t, list);
        } else  // elef->value >= eles->value
        {
            if (!tmphead)
                tmphead = second;
            struct list_head *tmp = second->next;
            struct list_head *next = second->next;
            struct list_head *prev = second->prev;
            if (next)
                next->prev = prev;
            if (prev->next == second)
                prev->next = next;
            prev = first->prev;
            if (prev->next == first)
                prev->next = second;
            if (second->next)
                second->next = first;
            second->prev = prev;
            first->prev = second;
            ts = second;
            second = tmp;
            if (second)
                eles = list_entry(second, element_t, list);
        }
    }
    if (first) {
        ts->next = first;
        first->prev = ts;
    }
    if (second) {
        tf->next = second;
        second->prev = tf;
    }
    return tmphead;
}
struct list_head *split(struct list_head *head)
{
    struct list_head *fast = head, *slow = head;
    while (fast->next && fast->next->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    struct list_head *temp = slow->next;
    slow->next = NULL;
    return temp;
}
struct list_head *mergeSort(struct list_head *head)
{
    if (!head || !head->next) {
        return head;
    }
    struct list_head *second = split(head);
    head = mergeSort(head);
    second = mergeSort(second);
    return merge(head, second);
}
  • 將 linked list 最後一個節點的 next 改為 null , 在 split 時才不會又跑回最前面
  • 做完 merge sort 要更改 head 的 prev 、 最後一個節點的 next 及第一個節點的 prev
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 *li = head;
    while (li->next) {
        li = li->next;
    }
    head->prev = li;
    head->prev->next = head;
    head->next->prev = head;
}

struct list_head *merge(struct list_head *first, struct list_head *second)
{ 
    struct list_head *head = NULL, **ptr = &head, **node;
    for(node = NULL; first && second; *node = (*node)->next) {
        element_t *elef = list_entry(first, element_t, list), *eles = list_entry(second, element_t, list); 
        node = (strcmp(elef->value, eles->value) <= 0) ? &first : &second;
        *ptr = *node; 
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *)((uintptr_t) first | (uintptr_t) second);
    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(head->next);
    struct list_head *fix_prev ,*li = head;
    while (li->next) {
        fix_prev = li;
        li = li->next;
        li->prev = fix_prev;
    }
    head->prev = li;
    head->prev->next = head;
}

Linux list_sort

引入 lib/list_sort.c 到 lab0-c

  • 將 linux listsort 程式碼拿到 queue.c 中
  • 宣告用來比較 queue 每個 entry 的字串大小的 compare 函式
int list_val_cmp(void *priv, const struct list_head *a, const struct list_head *b) 
{
    element_t *elea = list_entry(a,element_t,list), *eleb = list_entry(b,element_t,list);
    // elea->value <= eleb->value return <= 0
    // elea->value > eleb->value return > 0
    return strcmp(elea->value,eleb->value);
} 
void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    list_sort(NULL,head,list_val_cmp);
}

比較自己實做的 Merge Sort 和 Linux 核心程式碼之間效能落差

沿用 trace-14-perf.cmd 的測資 , 並透過 qtest 所提供的 time 命令來測量排序時間

option fail 0
option malloc 0
new
ih dolphin 1000000
it gerbil 1000000
reverse
time
sort
time
排序函式 執行時間
My MergeSort 0.95s
Linux MergeSort 0.55s

在 qtest 提供新的命令 shuffle

在 qtest.c 加上 shuffle 指令

  • 在 console_init 新增 shuffle 指令
  • ADD_COMMAND 是定義在 console.h 的巨集 #define ADD_COMMAND(cmd, msg) add_cmd(#cmd, do_##cmd, msg) , 也是為什麼當我們想新增一個指令 cmd , 對應的 function 一定要是 do_cmd
ADD_COMMAND(shuffle, "                | Do Fisher–Yates shuffle in queue");

static bool do_shuffle(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }
    if (!l_meta.l)
        report(3, "Warning: Try to access null queue");
    error_check();
    set_noallocate_mode(true);
    if (exception_setup(true)) 
        shuffle(l_meta.l);
    exception_cancel();
    set_noallocate_mode(false);
    show_queue(3);
    return !error_check();
}

實做 Fisher–Yates shuffle

  • Fisher–Yates shuffle
    1. 有一長度為 len 的 list , 設 i 初始為 len
    2. 每次隨機取一數 j , 0 <= j <= i
    3. 將第 j 個節點與第 i 個節點互換 , 並將 i - 1
    4. 重複步驟 2 、 3 直到 i = 1
  • shuffle_point 為當前要調換位置的節點 , next_shuffle_point 為下一個要調換的節點
  • 當要互換的節點是同一個節點 , 不做任何事
  • 當要互換的節點相鄰 , 移除第一個節點並接在第二個之後
  • 其餘的情況 , 先移除第一個節點並接在第二個之後 , 再移除第二個節點並接在原本第一個節點的 prev 之後
  • next_shuffle_point 在互換節點相鄰時 , 節點互換後這時shuffle_point 即為下次的 shuffle_point , 所以 next_shuffle_point 要改為 shuffle_point->prev
void shuffle(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    int len = q_size(head), x, it;
    struct list_head *li, *shuffle_point = head->prev, *tmp, *next_shuffle_point = shuffle_point->prev;
    while(len-- > 1) {
        li = head->next, it = 0, x = rand() % len;
        while (it++ < x) {
            li = li->next;
        }
        if(li == shuffle_point);
        else if(li->next == shuffle_point) {
            list_del(li);
            list_add(li,shuffle_point);
        }
        else {
            tmp = li->prev;
            list_del(li);
            list_add(li,shuffle_point);
            list_del(shuffle_point);
            list_add(shuffle_point, tmp);
        }
        if(next_shuffle_point != shuffle_point) {
            shuffle_point = next_shuffle_point;
            next_shuffle_point = next_shuffle_point->prev;
            next_shuffle_point = shuffle_point->prev;
        }
        else {
            next_shuffle_point = shuffle_point->prev;
        }
    }
}

運用 Valgrind 排除 qtest 實作的記憶體錯誤

透過 make valgrind 可以看到以下訊息 , 這裡取 trace-01-ops 產生的訊息來看 , 看起來像是有記憶體沒有釋放

+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
==19148== 5 bytes in 1 blocks are still reachable in loss record 1 of 3
==19148==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19148==    by 0x4A4D50E: strdup (strdup.c:42)
==19148==    by 0x110C05: linenoiseHistoryAdd (linenoise.c:1240)
==19148==    by 0x111798: linenoiseHistoryLoad (linenoise.c:1329)
==19148==    by 0x10C861: main (qtest.c:1016)
==19148== 
==19148== 137 bytes in 19 blocks are still reachable in loss record 2 of 3
==19148==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19148==    by 0x4A4D50E: strdup (strdup.c:42)
==19148==    by 0x110B79: linenoiseHistoryAdd (linenoise.c:1240)
==19148==    by 0x111798: linenoiseHistoryLoad (linenoise.c:1329)
==19148==    by 0x10C861: main (qtest.c:1016)
==19148== 
==19148== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==19148==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19148==    by 0x110BC5: linenoiseHistoryAdd (linenoise.c:1228)
==19148==    by 0x111798: linenoiseHistoryLoad (linenoise.c:1329)
==19148==    by 0x10C861: main (qtest.c:1016)
==19148== 
---	trace-01-ops	5/5

qtest.c

linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */

linenoise.c

int linenoiseHistoryAdd(const char *line)
{
    char *linecopy;

    if (history_max_len == 0)
        return 0;

    /* Initialization on first call. */
    if (history == NULL) {
        history = malloc(sizeof(char *) * history_max_len);
        if (history == NULL)
            return 0;
        memset(history, 0, (sizeof(char *) * history_max_len));
    }

    /* Don't add duplicated lines. */
    if (history_len && !strcmp(history[history_len - 1], line))
        return 0;

    /* Add an heap allocated copy of the line in the history.
     * If we reached the max length, remove the older line. */
    linecopy = strdup(line);
    if (!linecopy)
        return 0;
    if (history_len == history_max_len) {
        free(history[0]);
        memmove(history, history + 1, sizeof(char *) * (history_max_len - 1));
        history_len--;
    }
    history[history_len] = linecopy;
    history_len++;
    return 1;
}
int linenoiseHistoryLoad(const char *filename)
{
    FILE *fp = fopen(filename, "r");
    char buf[LINENOISE_MAX_LINE];

    if (fp == NULL)
        return -1;

    while (fgets(buf, LINENOISE_MAX_LINE, fp) != NULL) {
        char *p;

        p = strchr(buf, '\r');
        if (!p)
            p = strchr(buf, '\n');
        if (p)
            *p = '\0';
        linenoiseHistoryAdd(buf);
    }
    fclose(fp);
    return 0;
}
  • 一開始以為是 linenoiseHistoryAdd 的 linecopy 沒有釋放 , 因為他透過 strdup 配置記憶體卻沒釋放 , 便嘗試在函式結束前將它釋放 , 結果訊息卻便多了
+++ TESTING trace trace-01-ops:
==19917== Invalid read of size 1
==19917==    at 0x483FED4: strcmp (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19917==    by 0x110B6D: linenoiseHistoryAdd (linenoise.c:1235)
==19917==    by 0x1117A0: linenoiseHistoryLoad (linenoise.c:1330)
==19917==    by 0x10C861: main (qtest.c:1016)
==19917==  Address 0x4ba1ed0 is 0 bytes inside a block of size 5 free'd
==19917==    at 0x483CA3F: free (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19917==    by 0x110C29: linenoiseHistoryAdd (linenoise.c:1249)
==19917==    by 0x1117A0: linenoiseHistoryLoad (linenoise.c:1330)
==19917==    by 0x10C861: main (qtest.c:1016)
==19917==  Block was alloc'd at
==19917==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19917==    by 0x4A4D50E: strdup (strdup.c:42)
==19917==    by 0x110C05: linenoiseHistoryAdd (linenoise.c:1240)
==19917==    by 0x1117A0: linenoiseHistoryLoad (linenoise.c:1330)
==19917==    by 0x10C861: main (qtest.c:1016)
==19917== 
==19917== Invalid read of size 1
==19917==    at 0x483FEE8: strcmp (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19917==    by 0x110B6D: linenoiseHistoryAdd (linenoise.c:1235)
==19917==    by 0x1117A0: linenoiseHistoryLoad (linenoise.c:1330)
==19917==    by 0x10C861: main (qtest.c:1016)
==19917==  Address 0x4ba21f1 is 1 bytes inside a block of size 14 free'd
==19917==    at 0x483CA3F: free (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19917==    by 0x110C29: linenoiseHistoryAdd (linenoise.c:1249)
==19917==    by 0x1117A0: linenoiseHistoryLoad (linenoise.c:1330)
==19917==    by 0x10C861: main (qtest.c:1016)
==19917==  Block was alloc'd at
==19917==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19917==    by 0x4A4D50E: strdup (strdup.c:42)
==19917==    by 0x110B79: linenoiseHistoryAdd (linenoise.c:1240)
==19917==    by 0x1117A0: linenoiseHistoryLoad (linenoise.c:1330)
==19917==    by 0x10C861: main (qtest.c:1016)
==19917== 
# Test of insert_head and remove_head
==19917== 160 bytes in 1 blocks are still reachable in loss record 1 of 1
==19917==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19917==    by 0x110BC5: linenoiseHistoryAdd (linenoise.c:1228)
==19917==    by 0x1117A0: linenoiseHistoryLoad (linenoise.c:1330)
==19917==    by 0x10C861: main (qtest.c:1016)
==19917== 
---	trace-01-ops	0/5
  • 決定先看看 linenoiseHistoryLoad(HISTORY_FILE) 的 HISTORY_FILE 是什麼 , 發現原來是紀錄 qtest cmd 曾打過的指令紀錄 .cmd_history , 而這些紀錄會記在 **history 這個類似字串陣列裡頭
  • 所以嘗試把這個 histroy 給釋放 , 寫了一個freeHistory 的函式來完成 , 卻發現 linenoise.c 原本就有定義這個函式了
  • 最後 , 在 linenoise.c 裡寫一個函式 freelinenoise 來呼叫釋放 histroy 記憶體的函式 linenoiseAtExit , 並在 qtest 主程式結束前呼叫它 , 成功解決 memory leak 的問題
void freelinenoise() {
    linenoiseAtExit();
}
Last changed by 
 
Korin777
0
636

Read more

2023q1 Homework7 (ktcp)

contributed by &lt; Korin777 &gt; 開發環境 $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 39 bits physical, 48 bits virtual Byte Order: Little Endian

May 8, 2023
2023q1 Homework5 (quiz5)

contributed by &lt; Korin777 &gt; 測驗題目 測驗一 運作原理 pool_malloc 透過 get_loc_to_place 從 memory pool 的 free block 中配置記憶體給使用者 配置記憶體的大小會根據 32 bits 或 64 bits 進行 round up

Apr 21, 2023
2023q1 Homework4 (quiz4)

contributed by &lt; Korin777 &gt; 測驗題目 測驗三 RB_LOG2_MAX_NODES node_t 的大小為 sizeof(void*) * 4 所以 node 最多有 $$\frac{1 &lt;&lt; (sizeof(void ) &lt;&lt; 3)} {(sizeof(void) * 4)}$$ 取 log2 可以得到 RB_LOG2_MAX_MEM_BYTES - log2(sizeof(void*)*2) - 1，若 sizeof(void*) == 8 就會是 RB_LOG2_MAX_MEM_BYTES - 4 - 1 tree_insert 這裡透過 path 來記錄插入節點的所有祖先節點，所以節點不須記錄自己的親代節點也能在插入後向上修復紅黑數，遇到黑色節點就可以停下，因為只有紅色節點可能會違反規則

Apr 8, 2023
2023q1 Homework3 (quiz3)

contributed by &lt; Korin777 &gt; 測驗四 int ceil_log2(uint32_t x) { uint32_t r, shift; x--; r = (x &gt; 0xFFFF) &lt;&lt; 4; x &gt;&gt;= r;

Mar 15, 2023
Read more from Korin777
Published on HackMD