2022q1 Homework1 (lab0)

contributed by < ioksengtan >

實驗環境

$ gcc --version
Configured with: --prefix=/Library/Developer/CommandLineTools/usr --with-gxx-include-dir=/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/4.2.1
Apple clang version 12.0.5 (clang-1205.0.22.11)
Target: arm64-apple-darwin20.5.0
Thread model: posix

作業要求

Queue operation implementation

new command implementation

shuffle
提供新的命令 shuffle，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
web
提供新的命令 web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令

Documentation in Devlog

開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
先執行 qtest 再於命令提示列輸入 help 命令，會使開啟 Address Sanitizer 觸發錯誤，應予以排除
運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件的原理和考量點。可對照參考 CS:APP 第 10 章重點提示
研讀論文〈Dude, is my code constant time?〉，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;

Improve your writing! It is supposed to be an official document.
jserv

Thanks a lot jserv for feedback.
I will continue refining my documentation.
ioksengtan

Queue operation implementation

q_size

list_for_each

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_new

create a new element
return the pointer to the next list

struct list_head *q_new()
{
    element_t *q = malloc(sizeof(element_t));
    if (q == NULL) {
        return NULL;
    }
    INIT_LIST_HEAD(&q->list);
    return &q->list;
}

cmd> new
Freeing old queue
l = NULL
ERROR: Freed queue, but 2 blocks are still allocated
l = []

reference: https://myao0730.blogspot.com/2016/12/linux.html

q_insert_head

new an element
new_ele->next = head->next
head->next = new_ele

using provided list_add() in list.h

/**
 * list_add() - Add a list node to the beginning of the list
 * @node: pointer to the new node
 * @head: pointer to the head of the list
 */
static inline void list_add(struct list_head *node, struct list_head *head)
{
    struct list_head *next = head->next;

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

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;
    ele->value = malloc(sizeof(s));
    memset(ele->value, '\0', strlen(ele->value));
    strncpy(ele->value, s, strlen(s));
    list_add(&ele->list, head);
    return true;
}

testing

cmd> new
l = []
cmd> ih test
l = [test]
cmd> ih test2
l = [test2 test]

q_insert_tail

reuse list_add_tail in list.h

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;
    ele->value = malloc(sizeof(s));
    memset(ele->value, '\0', strlen(ele->value));
    strncpy(ele->value, s, strlen(s));
    list_add_tail(&ele->list, head);
    return true;
}

issue:

cmd> new
l = []
cmd> it test
l = [test]
cmd> free
ERROR: Corruption detected in block with address 0x12ef04130 when attempting to free it
l = NULL

Observation on solution

Corruption detected:



    ele->value = malloc(sizeof(s));
    memset(ele->value, '\0', strlen(ele->value));
    strncpy(ele->value, s, strlen(s));

No Corruption detection:


    ele->value = strdup(s);

Revised implementation of q_insert_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;
    ele->value = strdup(s);
    list_add_tail(&ele->list, head);
    return true;
}

You must explain your observations and reactions.
jserv

Thanks alot jserv for feedback,
I am cooking those information then document it later.
ioksengtan

Then there is no corruption

cmd> new
l = []
cmd> it test
l = [test]
cmd> rt
Removed test from queue
l = []
cmd> it test
l = [test]
cmd> free
l = NULL

discussion: what's the difference between strdup and malloc+memset+strncpy ?

discussion: what's the difference between following two lines?

(1) list_add_tail(&(ele->list), head);
(2) list_add_tail(&ele->list, head);

using (1), will fail the static analysis when git commit.

lab0-c git:(master) ✗ git commit -a

Following files need to be cleaned up:
queue.c
queue.c:118:5: error: Memory leak: ele [memleak]
    return true;
    ^

testing

cmd> new
l = []
cmd> it test
l = [test]
cmd> it test2
l = [test test2]
cmd> it test3
l = [test test2 test3]

q_remove_head

















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

    if (sp) {
        element_t *e = list_first_entry(head, element_t, list);
        size_t len = strlen(e->value);
        len = (bufsize-1)>len?len:(bufsize-1);
        memcpy(sp, e->value, len);
        sp[len] = '\0';

        list_del(&e->list);
        return e;
    }
    return NULL;
}

testing

cmd> new
l = []
cmd> ih test
l = [test]
cmd> ih test2
l = [test2 test]
cmd> rh
Removed test2 from queue
l = [test]

q_free

given the pointer of queue head
using provided q_release_element(element_t *e)
release all elements until end of queue















void q_free(struct list_head *l)
{
    if (l == NULL) {
        return;
    }
    struct list_head *node = l->next;
    while (node != l) {
        element_t *e = container_of(node, element_t, list);
        node = node->next;
        q_release_element(e);
    }
    // cppcheck-suppress nullPointer
    element_t *head = container_of(l, element_t, list);
    free(head);
}

Following implementation is wrongful, causing segmentation fault.

    if (!l)
        return;

    // iterate over the list entries and remove it
    element_t *entry, *safe;
    list_for_each_entry_safe (entry, safe, l, list)
        q_release_element(entry);
    free(l);

cmd> new
l = []
cmd> ih test
l = [test]
cmd> ih test2
l = [test2 test]
cmd> free
ERROR: Attempted to free unallocated block.  Address = 0x15bf042b8
ERROR: Attempted to free unallocated or corrupted block.  Address = 0x15bf042b8
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer

q_delete_mid

when number is even (N=4)

if front->next = end, remove node3

when number is odd (N=3)

if front = end, remove node2



















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 *front = head->next;
    struct list_head *end = head->prev;
    while (true) {
        if (front == end || front->next == end){
            list_del(front);
            q_release_element(list_entry(front, element_t, list));
            break;
        }
        front = front->next;
        end = end->prev;
    }
    return true;
}

q_delete_dup

q_swap

q_sort

worst case:

quick sort: time: O(N^2), spce: O(N)
merge sort: time: O(nlogn), spce: O(N)

看到一些同學實作quick sort有遇到效能的問題。
複習了sort 的時空複雜度，的確quick sort 的最差情境會是N^2。

merge sort原理：

將原始的list 以二分法切成最小單位(N=2 or 1)的sorted list
再兩兩一組合併回來 (Leetcode 24 Merge Two Sorted Lists)

2022q1 Homework1 (lab0)

實驗環境

作業要求

Queue operation implementation

new command implementation

Documentation in Devlog

Queue operation implementation

q_size

q_new

q_insert_head

testing

q_insert_tail

issue:

Observation on solution

discussion: what's the difference between strdup and malloc+memset+strncpy ?

discussion: what's the difference between following two lines?

testing

q_remove_head

testing

q_free

q_delete_mid

q_delete_dup

q_swap

q_sort

web