2022q1 Homework1 (lab0)

contributed by < idoleat >

Working Environment

Details (click to expand)

$ uname -r        
5.16.10-arch1-1

$ gcc --version
gcc (GCC) 11.2.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.

$ valgrind --version
valgrind-3.18.1

$ cppcheck --version
Cppcheck 2.7

$ aspell --version
@(#) International Ispell Version 3.1.20 (but really Aspell 0.60.8)

作業要求

• 在 GitHub 上 fork lab0-c
  • 參閱 Git 教學和 GitHub 設定指引 ^{附教學影片}
• 依據上述指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 $ make test 自動評分系統的所有項目。
  • 在提交程式變更前，務必詳閱 如何寫好 Git Commit Message
  • 詳閱「你所不知道的 C 語言: linked list 和非連續記憶體」並應用裡頭提及的手法，例如 pointer to pointer (指向某個指標的指標，或說 indirect pointer)，讓程式碼更精簡且有效
  • 研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
• 在 qtest 提供新的命令 shuffle，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
• 在 qtest 提供新的命令 web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令
  • 可依據前述說明，嘗試整合 tiny-web-server
• 除了修改程式，也要編輯「作業區」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
  • 開啟 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 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
• 指出現有程式的缺陷 (提示: 和 RIO 套件 有關) 或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request

Queue Operations

q_new()

/*
 * Create empty queue.
 * Return NULL if could not allocate space.
 */
struct list_head *q_new()
{
    struct list_head *h = malloc(sizeof(struct list_head));
    if (h == NULL)
        return NULL;

    INIT_LIST_HEAD(h);  // Todo: what about using LIST_HEAD(head)?
    return h;
}

Initially, I thought a list_head * points to NULL would be an empty queue, but according to the comment it's the situation that could not allocate space. Seems that we still need an empty element_t. It's kind of weird to have an element containing nothing in a new queue since it makes the size of a new queue 1.(But not the real size because head is NULL and would make q_size() report 0 at this point)
After the class on 2/22, I found that there's really no need to allocate a whole element_t. But my original thoughts was wrong as well. It's not a list_head points to NULL. It's an initialized head.

For initializing the list head, besides using Linux kernel API INIT_LIST_HEAD, I found there's another macro LIST_HEAD (it's not kernel API though).

Memory leaks on return &(q->list) reported by Cppcheck need to be fix. I got a quick fix suggested by King Bur and Pin Lin in this post. Adding // cppcheck-suppress nullPointer inline and --inline-suppr as a cppcheck command argument can suppress the warning according to the manual. Or just maybe it really has memory leak. Listed in Todo. (@jasperlin1996 mentioned this in his note as well)

q_insert_head() and q_insert_tail()

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *q = malloc(sizeof(element_t));
    if (q == NULL)
        return false;

    q->value = malloc(sizeof(char) * (strlen(s) + 1));
    if (q->value == NULL) {
        free(q);
        return false;
    }

    strncpy(q->value, s, strlen(s) + 1);
    list_add(&(q->list), head);
    return true;
}

After allocating element_t and value in element_t, we should check if they are allocated successfully or not. Noted that the return value of strlen() doesn't include \0. I've seen others suggesting using memcpy to copy strings. I'm not sure if that's it's a better way. I'll experiment that later. Listed in Todo.

I've noticed that comparing to a queue implemented with non-circular doubly-linked list, which has explicit tail pointer, circular doubly-linked list can shrink down the complexity of implementation. We don't need to determine the queue is empty or not here.

Insert an element to tail is pretty much the same. Just substitute lisr_add to list_add_tail thanks to the convenient Linux API.

q_remove_head() and q_remove_tail()

Fix my mis-usage of head

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (head == NULL || list_empty(head))
        return NULL;
	
    element_t *entry = list_entry(head, element_t, list);
    if (sp != NULL) {
        strncpy(sp, entry->value, bufsize);
        sp[bufsize - 1] = '\0';
    }

    list_del(head);
    return entry;
}

Not sure what goes wrong but this piece of code produces segment fault (dereferenced NULL or invalid pointer) in strncpy according to gdb debug message. If I substitute strncpy with strndup("test", bufsize - 1) or even comment out the line, I'll get this instead:

ERROR: Attempted to free unallocated block.  Address = 0xdeadbeef

Program received signal SIGSEGV, Segmentation fault.
0x0000555555559dc2 in find_header (p=0xdeadbeef) at harness.c:103
103	    if (b->magic_header != MAGICHEADER) {

Since free() is substituted to test_free() in harness.c, let's see what look into it.

/* Value at start of every allocated block */
#define MAGICHEADER 0xdeadbeef

Since every block allocated start with 0xdeadbeef, any block not starting with 0xdeadbeef is not a legitimate block.
ok…I still don't know why. Maybe there's something wrong already while inserting…
Cppcheck says that

queue.c:98:24: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
    element_t *entry = list_entry(head, element_t, list);

So the answer is that I forgot the head is just a head to enter the queue, like what we get in q_new(). Sounds hilarious but I was troubled with this mistake a whole day. I should use Cppcheck earlier next time. My skill on solving segment fault is not trust worthy. Maybe in a memory inexpensive environment we can allocate a whole element_t for head and set "this is a head" for its value so that this won't happened (I'm not sure I can call it a fault tolerance design or not).

Corrected code:

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (head == NULL || list_empty(head))
        return NULL;
	
    element_t *first_entry = list_first_entry(head, element_t, list);
    if (sp != NULL) {
        sp = strncpy(sp, first_entry->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    list_del(&first_entry->list);
    return first_entry;
}

I saw some others use list_entry(head->next, element_t, list) instead of list_first_entry. I think using list_first_entry is a more semantic way though.

Cppcheck: Null pointer dereference

Actually the error message from cppcheck wasn't indicating that I used head in the wrong way. In @Jasperlin1996's note, he not only deep dived into the issue, also submitted a PR. Worth taking some time give it a read.

q_free()

Recursive free

(WIP)
In the iterative way, the address of next list_head should be put in a temporary pointer (either in a loop-scoped variable or in a function local variable) before freeing the current element. It seems tedious to do so. So I come up with an idea to walk through whole list to the end, freeing elements from the tail back to the head. Since the previous element is known already, there is no need to remember anything before freeing elements. This is the recursive way.

To make it more efficient, I want to make it into a tail recursion. Otherwise, the stack might get overflowed by test cases with 1000000-elements queue, according to the lab-0 document.

Using list_for_each_entry_safe()

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

Return if the list is null.
There are 4 APIs to iterate though a list:
list_for_each
list_for_each_entry
list_for_each_safe
list_for_each_entry_safe
The first two don't allow you modify the entry while iterating. The later two allow because there's an extra pointer to get the next node first before anything changed. By using list_for_each_entry_safe and q_release_element() all the elements are freed. Lastly, free the head itself.

Even though it passed the test but I'm still wondering what's the point of remove head/tail instead of deleting it? The unlinked node becomes unaccessable. When will it get freed?
Ans: In qtest.c, the return value of q_remove_head() and q_remove_tail(), which are the removed nodes, will be released by calling q_release_element().

q_delete_mid()

bool q_delete_mid(struct list_head *head)
{
    if (head == NULL || list_empty(head))
        return false;

    element_t *entry, *tmp;
    int size = q_size(head);
    list_for_each_entry_safe (entry, tmp, head, list) {
        size -= 2;
        if (size <= 0) {
            list_del(&entry->list);
            q_release_element(entry);
            return true;
        }
    }

    return false;
}

There are two ways to find the middle in my mind. One is iterating from two ends toward each other and meeting at the middle. The other is iterating from same side but one is 2 times faster than the other. To utilize the list API the most, with the goal to iterate to the exact node to delete, I use a counter to count down 2 at once. When it's equal or less than 0, the entry is the one we want to delete.

q_delete_dup()

(WIP)
I'm trying to come up with the best solution.

q_reverse()

void q_reverse(struct list_head *head)
{
    if (head == NULL || list_empty(head))
        return;

    struct list_head *node, *tmp;
    list_for_each_safe (node, tmp, head) {
        node_np_swap(node);
    }
    node_np_swap(head);
}

node_np_swap() means swapping the next and prev in a list node. It's defined as:

void inline node_np_swap(struct list_head *node)
{
    struct list_head *tmp;
    tmp = node->next;
    node->next = node->prev;
    node->prev = tmp;
}

The idea is that every node in the list just turns around and the job is done. The node includes the head itself because the first(head->next) and the last(head->prev) needs to be swapped as well. If the list is not doubly linked and circular, the situation could be more complex.

I would like to use XOR to swap but ^ is not a valid operator for list_head * After checking ISO 9899 standard, it says

6.3.2.3 Pointers
Any pointer type may be converted to an integer type. Except as previously specified, the result is implementation-defined. If the result cannot be represented in the integer type, the behavior is undefined. The result need not be in the range of values of any integer type.

q_swap()

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs
    if (head == NULL)
        return;

    struct list_head *iterator = head->prev;
    bool last = true;
    int size = q_size(head);
    if ((size & 1) == 1) {
        list_move(iterator, head);
        size -= 1;
    }
    while (size--) {
        iterator = head->prev;
        if (last)
            iterator = iterator->prev;
        list_move(iterator, head);
        last = !last;
    }
}

The code looks tedious because of there are extra parts dealing with odd queue size and witch to move. I've seen @jasperlin1996 done it in a cleaner way by writing the restrictions in for condition statement.

(WIP)
There may be a way to write a better one by using list_head **

q_sort()

(WIP)
I choose heap sort here because it's doable here. Also, it's an unstable sort although the time complexity is O(n). I want to test how unstable is an unstable sort. No, heap sort is not O(nlogn) on linked list because element look up in linked list is O(n). This will make the total time complexity become O(n²logn).

Todo: compare the memory usage and execution time of both top-down and bottom-up way.

Extra: Concurrent FIFO queue

I'm interested in finding ways to divide jobs for programs (effortlessly ideally) to run on multiple machines. This may be a good chance to practice and trying out my new ideas and others' idea.
https://www.youtube.com/watch?v=BowcTNnkO7E

Comparing with list_sort.c in Linux kernel

You can modify the code to challenge the design