2022q1 Homework1 (lab0)

contributed by < hsuedw >

• 課程網頁
• Linux 核心設計/實作 (2022 年): 課程說明 (直播)
• 「Linux 核心設計/實作」 課程說明 (2022年) (投影片)
• 第一周課程直播1
• 第一周課程直播2
• 作業講解
• 作業要求
• 作業繳交區

---

Resolve issue when I setup my development environment.

issue 1: Instead of password, GitHub accespts Personal Access Tokens (PAT) when I push code to my repository.

• solution: Creating a personal access token

issue 2: When installing the latest cppcheck, I had problems.

• This my solution for installing cppcheck 2.7 on Ubuntu 20.04
  • Uninstall the old cppcheck (1.90)
    $ sudo apt remove cppcheck
  • To avoid bulid fail by some missing header files, install this package
    $ sudo apt-get install libpcre3-dev
  • Download the latest cppcheck from Unbuntu.
    $ wget https://launchpad.net/ubuntu/+archive/primary/+sourcefiles/cppcheck/2.7-1/cppcheck_2.7.orig.tar.gz
  • Unpack the tarball.
    $ tar -vxf cppcheck_2.7.orig.tar.gz
  • After reading the Makefile and read.md of cppcheck, I realized the following command is the command for building it from source code.
    $ sudo make MATCHCOMPILER=yes FILESDIR=/usr/share/cppcheck HAVE_RULES=yes CXXFLAGS="-O2 -DNDEBUG -Wall -Wno-sign-compare -Wno-unused-function" install
  • Then, I have cppcheck 2.7 installed on my computer.
    $ cppcheck --version Cppcheck 2.7
  • After cppcheck 2.7 is installed, don't run apt install to install cppcheck again. Otherwise, the old version (1.90) will come back.
    sudo apt install cppcheck (Do not run this!)
    

---

Implement a queue by using linked list

TODO list

• q_new: 建立新的「空」佇列;
• q_free: 釋放佇列所佔用的記憶體;
• q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
• q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);
• q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點;
• q_remove_tail: 在佇列尾端 (tail) 移去 (remove) 給定的節點;
• q_release_element: 釋放特定節點的記憶體空間;
• q_size: 計算目前佇列的節點總量;
• q_delete_mid: 移走佇列中間的節點，詳見 LeetCode 2095. Delete the Middle Node of a Linked List
• q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 LeetCode 82. Remove Duplicates from Sorted List II
• q_swap: 交換佇列中鄰近的節點，詳見 LeetCode 24. Swap Nodes in Pairs
• q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
• q_sort: 以遞增順序來排序鏈結串列的節點，可參閱 Linked List Sort 得知實作手法;

q_size()

commit: bdacefa

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 -1;
}

• Time complexity: O(n)
  • where n is the number of nodes in the linked list.
• Space complexity: O(1)
• list_for_each(pos, head)
  • For iterating over a linked list, list_for_each(pos, head) is implemented in lab0-c/list.h Its usage is identical with it counterpart in Linux kernel API.

q_new()

commit: a06dd09

struct list_head *q_new()
{
    element_t *q = malloc (sizeof(element_t));
    if (!q) return NULL;

    q->value = NULL;
    INIT_LIST_HEAD(&q->list);

    return &q->list;
}

• Time complexity: O(1)
• Space complexity: O(1)
• Based upon the man page of malloc(), I check whether it returns NULL. If it returns NULL, no memory space can be allocated and q_new() returns NULL.

RETURN VALUE
       The malloc() and calloc() functions return a pointer to  the  allo?
       cated  memory, which is suitably aligned for any built-in type.  On
       error, these functions return NULL.  NULL may also be returned by a
       successful call to malloc() with a size of zero, or by a successful
       call to calloc() with nmemb or size equal to zero.

• void INIT_LIST_HEAD(struct list_head *list)

  • INIT_LIST_HEAD() is the Linux kernle API to initialize a list_head structure.

• Copy and paste the source code (include/linux/list.h) from Linux kernel.

  • By observing the code, after q_new() is run, the next and prev pointers of q->list point to itself.

struct list_head {
	struct list_head *next, *prev;
};

static inline void INIT_LIST_HEAD(struct list_head *list)
{
	WRITE_ONCE(list->next, list);
	list->prev = list;
}

@jserv
Sir! I have a couple of questions for WRITE_ONCE(). I have no idea why kernel developer use this, although looking into its implementation.
Also, what is the reason that the developer just apply WRITE_ONCE() on the next pointer?
Why not apply it on the prev pointer as well?

You should read the documentation in advance.

jserv

@jserv
Sir! I think that's my mistake. The above implementation of INIT_LIST_HEAD() is from LXR. However, I am doing homework1 (lab0) and developing a user space application. In this homework, one of the goals is to use kenenl APIs to manipulate doubly linked list. The function signatures of those kernel APIs are already in lab0-c/list.h. Instead of LXR, I should read lab0-c/list.h. Is this the documentation in your last reply?
@jserv
Sorry! My mistake again! The documentation you mentioned in your first message should be 你所不知道的 C 語言: linked list 和非連續記憶體, Linux-核心原始程式碼

q_insert_head()

commit: be50027

q_new_element() and q_init_element()

• Because I have to implement q_insert_tail() latter, I write two helper functions to new element_t objects.

/*
 * q_init_element() initializes a new object of element_t.
 * Assume e and s are not NULL and point to valid memory address.
 * Return true if successful. Otherwise, return false.
 */
bool q_init_element(element_t *e, char *s)
{
    size_t len = strlen(s) + 1;
    e->value = malloc(len);
    if (!e->value)
        return false;

    memcpy(e->value, s, len);
    INIT_LIST_HEAD(&e->list);

    return true;
}

• Time and space complexity: O(n)
  • where n is the length of s.
• Because a c-style string is terminated by an extra '\0' character, I add one to the return value of strlen(). Then, the variable, len, holds the valid value for malloc() and memcpy().
• If q_new_element() and q_init_element() work successfully, the newly allocated element_t object looks like this.
  

/*
 * q_new_element() create a new object of element_t.
 * Return NULL if could not allocate space.
 */
element_t *q_new_element(char *s)
{
    element_t *ne = malloc(sizeof(element_t));
    if (!ne)
        return NULL;

    if (!q_init_element(ne, s)) {
        free(ne);
        return NULL;
    }

    return ne;
}

• Time and space complexity: O(n)
  • where n is the length of s.

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *ne = q_new_element();
    if (!ne)
        return false;

    if (!q_init_element(ne, s)) {
        free(ne);
        return false;
    }

    list_add(&ne->list, head);

    return true;
}

• Time and space complexity: O(n)
  • where n is the length of s.
• Use list_add(), which is implemneted in lab0-c/list.h, to insert the newly created element_t object at queue head.

q_insert_tail()

commit: be50027

/*
 * Attempt to insert element at tail of queue.
 * Return true if successful.
 * Return false if q is NULL or could not allocate space.
 * Argument s points to the string to be stored.
 * The function must explicitly allocate space and copy the string into it.
 */
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *ne = q_new_element(s);
    if (!ne)
        return false;

    list_add_tail(&ne->list, head);

    return true;
}

• Time and space complexity: O(n)
  • where n is the length of s.
• Reuse the APIs implemented in commit be50027 to create a new element_t object.
• Use list_add_tail(), which is implemented in lab0-c/list.h, to insert the newly created elemnet_t object at queue tail.

q_reverse()

commit: f87171f

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

    struct list_head *it, *tmp;
    for (it = head->next; it != head; it = it->prev) {
        tmp = it->next;
        it->next = it->prev;
        it->prev = tmp;
    }
    tmp = head->next;
    head->next = head->prev;
    head->prev = tmp;
}

• Time complexity: O(n)
  • where n is the number of nodes in queue.
• Space complexity: O(1)
• Reuse the API implemented in lab0-c/list.h, list_empty(), to detect whether queue is empty.

static inline int list_empty(const struct list_head *head)
{
    return (head->next == head);
}

q_free()

commit: 978dec0 (original implementation)
commit: debbd35 (Fix the issue that the head node is not freed if queue is empty.)

void q_free(struct list_head *l)
{
    if (!l)
        return;

    struct list_head *it = l->next;
    while (it != l) {
        element_t *e = container_of(it, element_t, list);
        it = it->next;
        q_release_element(e);
    }
    element_t *head = container_of(l, element_t, list);
    free(head);
}

• Time complexity: O(n)
  • where n is the number of nodes in queue.
• Space complexity: O(1)

q_remove_head()

commit: debbd35

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

    // cppcheck-suppress nullPointer
    element_t *target = list_entry(head->next, element_t, list);
    list_del_init(head->next);
    strncpy(sp, target->value, bufsize - 1);

    sp[bufsize - 1] = '\0';
    return target;
}

• Time and space complexity: O(bufsize)

q_remove_tail()

commit: 3ebdf77

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    return q_remove_head(head->prev->prev, sp, bufsize);
}

• Time and space complexity: O(bufsize)

q_delete_mid()

Implementation by using pionter

commit: 8e72fbc

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

    struct list_head *fast = head->next, *slow = head->next;
    while (fast != head && fast->next != head) {
        slow = slow->next;
        fast = fast->next->next;
    }

    list_del_init(slow);
    element_t *e = container_of(slow->next, element_t, list);
    q_release_element(e);

    return true;
}

• Time complexity: O(n)
• Space complexity: O(1)
• I use two pointers, fast and slow, to find the middle node in queue. Because in each iteration, slow moves one hop and fast move two hops, slow references the middle node while fast traverses the whole queue.

Implementation by using pointer of pointer

• After reading 你所不知道的 C 語言: linked list 和非連續記憶體, I decided to follow the idea in this article and use pointer of pointer to implement q_delete_mid() again.

@jserv
Thanks sir! I am impressed and learned. However, I need more time and practice to accept this idea.

commit: 5c98453

bool q_delete_mid(struct list_head *head)
{
    /*
     * Use pointer of pointer to implement q_delete().
     */
    if (!head)
        return false;

    struct list_head **indir = &head->next, *fast = head->next;
    while (fast != head && fast->next != head) {
        indir = &(*indir)->next;
        fast = fast->next->next;
    }

    struct list_head *del = *indir;
    list_del_init(del);
    element_t *e = container_of(del->next, element_t, list);
    q_release_element(e);

    return true;
}

q_swap()

commit: f41ead9

• In this implementation, I use two Linux kernel APIs which are not included in lab0-c/list.h. Therefore, I copy and paste them in a newly created header file, mylist.h, and fix indentations to meet our coding style.

static inline void list_replace(struct list_head *old, struct list_head *new)
{
    new->next = old->next;
    new->next->prev = new;
    new->prev = old->prev;
    new->prev->next = new;
}

static inline void list_swap(struct list_head *entry1, struct list_head *entry2)
{
    struct list_head *pos = entry2->prev;

    list_del(entry2);
    list_replace(entry1, entry2);
    if (pos == entry1)
        pos = entry2;
    list_add(entry1, pos);
}

• Then, the implementation of my q_swap() is listed as following.

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_swap(it->next, it);
        it = it->next;
    }
}

• Time complexity: O(n)

• Space complexity: O(1)

• If queue is NULL, empty or has only one node, return immediately.

• it is the iterator to traverse over queue. It starts from the first node, which is head->next. While both it != head and it != head->next are true, there are two adjacent nodes to swap.

• Because github rejects mylist.h, I deleted it and use the other two APIs in list.h to implement q_swap().

commit: cbeabf2

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *it = head->next;
    while (it != head && it->next != head) {
        struct list_head *tmp = it->next;
        list_del_init(it);
        list_add(it, tmp);
        it = it->next;
    }
}

q_release_element()

• q_release_element() is implemented in the original code.

q_sort()

• I think it is better to read 你所不知道的 C 語言: linked list 和非連續記憶體 first.
  • I think I should read this artical before working on this homework. Big mistake!
• note:
  • Inorder to use uintptr_t, I include #include <stdint.h>. See this reference.
• The sorting algorithm is merge sort.
• To merge two sorted lists, I modified the code in 你所不知道的 C 語言: linked list 和非連續記憶體, 案例探討: LeetCode 21. Merge Two Sorted Lists to implement __q_merge().
• I also reference this implementation

commit: ebead52

/*
 * __q_merge() is an internal API for q_merge_sort().
 * Input: left and right are two sorted doubly linked lists.
 * Output: A sorted doubly linked list merged from left and right.
 */
struct list_head *__q_merge(struct list_head *left, struct list_head *right)
{
    struct list_head *head = NULL, **ptr = &head, **node;

    for (node = NULL; left && right; *node = (*node)->next) {
        if (strcmp(list_entry(left, element_t, list)->value,
                   list_entry(right, element_t, list)->value) < 0)
            node = &left;
        else
            node = &right;

        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *)((uintptr_t) left | (uintptr_t) right);

    return head;
}

struct list_head *q_merge_sort(struct list_head *head)
{
    if (!head->next)
        return head;

    struct list_head *slow = head, *fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    struct list_head *head2 = slow->next;
    slow->next = NULL;

    struct list_head *left = q_merge_sort(head), *right = q_merge_sort(head2);
    return __q_merge(left, right);
}

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *node = head->next;
    head->prev->next = NULL;
    head->next = NULL;

    node = q_merge_sort(node);

    // We use doubly linked list to implement queue. However, q_merge_sort()
    // treat it as a singly linked list and only use the next pointer to sort
    // all the nodes. Use a loop and traverse along the next pointers to
    // rearrange the prev pointers.
    struct list_head *it = head;
    it->next = node;
    while (it->next) {
        it->next->prev = it;
        it = it->next;
    }
    it->next = head;
    head->prev = it;
}

q_delete_dup()

commit: c338565

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return false;

    struct list_head *prev = head->next, *node = head->next->next;
    bool dup_flag = false;

    while (prev != head && node != head) {
        element_t *prev_element = list_entry(prev, element_t, list);
        element_t *node_element = list_entry(node, element_t, list);

        while (node != head &&
               strcmp(prev_element->value, node_element->value) == 0) {
            dup_flag = true;
            list_del(node);
            q_release_element(node_element);
            node = prev->next;
            node_element = list_entry(node, element_t, list);
        }

        if (dup_flag) {
            dup_flag = false;
            list_del(prev);
            q_release_element(prev_element);
        }

        prev = node;
        node = node->next;
    }
    return true;
}

• Time complexity: O(n)
• Space complexity: O(1)

Performance issue

• Although I have implemented all the required queue APIs, my code cannot pass trace-17-complexity.cmd. I need to think about my implementation of q_insert_head(), q_insert_tail(), q_remove_head() and q_remove_tail().

• This is what trace-17-complexity.cmd do.

option simulation 1
it
ih
rh
rt
option simulation 0

• I modify driver.py and it will only run trace-17-complexity.cmd. Then, try to figure out what is going on.
• After reviewing my code and doing some experiments, I cannot draw any conclution. I have no idea for resolving this issue.
• I went to 2022q1 Homework1 (作業區) and cloned following github repositories and run 'make test' on my computer. Because they have 👍 behind their names and some of them claim they pass all the test cases, I guess they probably pass trace-17-complexity and can learn something from them. Surprisingly! None of them can pass the time complexity test!
  • blueskyson
  • laneser
  • risheng1128
  • 2020leon
  • kdnvt
  • mm0809
  • tinyynoob
• Actually, during my debugging, sometimes my code can pass all the test cases but sometimes cannot. I guess the root cause could be string copy during node insertion and deletion. But I have no evidence.

$ make clean test
rm -f qtest.o report.o console.o harness.o queue.o random.o dudect/constant.o dudect/fixture.o dudect/ttest.o linenoise.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 .linenoise.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    linenoise.o
  LD    qtest
scripts/driver.py -c
---     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, reverse, and remove_head
---     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, and sort
---     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

• Move on. But I will come back.
  • This could probably give me some idea.
    • Dude, is my code constant time?

Implement a new command, shuffle, in qtest

commit: 27ebbc4

• Add a new command in qtest.
  • In console_init(), use the ADD_COMMAND() macro to add a command in console_init.
  • In qtest.c, implement do_shuffle() to call q_shuffle(), which is a queue API that I will implement latter.

static bool do_shuffle(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }

    bool ok = q_shuffle(l_meta.l);
    if (ok)
        ok = show_queue(0);

    return ok;
}

• In queue.c, implement q_shuffle() to do Fisher-Yates shuffle.
  • Time complexity: O(n²)
  • Space complexity: O(1)

bool q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return false;

    srand(time(NULL));

    int window = q_size(head);
    while (window) {
        int x = rand() % window;
        struct list_head *it = head->next;
        for (int i = 0; i < x; ++i)
            it = it->next;
        list_del_init(it);
        list_add(it, head);
        --window;
    }

    return true;
}

• After thinking for a while, a new idea come to my mind. I think I can improve the time complexity to O(n) by using an array of pointers.

commit: 27ebbc4

bool q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return false;

    size_t len = q_size(head);
    size_t i = 0;
    struct list_head *it, *parray[len];
    while (!list_empty(head)) {
        it = head->next;
        list_del_init(it);
        parray[i] = it;
        ++i;
    }
    INIT_LIST_HEAD(head);
    /* Queue is empty now. */

    size_t window = len;
    /* Fisher-Yates shuffle */
    srand(time(NULL));
    for (i = 0; i < len - 1; ++i) {
        int x = rand() % window;
        struct list_head *tmp = parray[x];
        parray[x] = parray[window - 1];
        parray[window - 1] = tmp;
        --window;
    }

    /* Insert the shuffled nodes into queue. */
    i = 0;
    while (i < len) {
        list_add_tail(parray[i], head);
        ++i;
    }

    return true;
}

• In this implementation, there are three passes.
• In pass one (line 9-14), I traverse over the doubly linkded list, delete each node and put each of them in an array of pointers (parray).
• In pass two (line 18-27), based on the description of wiki, I implement the Fisher-Yates shuffle algorithm to shuffle parray. Because all the nodes' memory addresses are kept in parray, shuffle parray means shuffle queue nodes.
• In pass three (line 30-34), I insert all the nodes back to queue.
• Actually, I can combine pass two and three. Because I do shuffle and node insertion in one while-loop, the code will be more concise. The time complexity is also O(n).

commit: 587aa5e

bool q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return false;

    size_t len = q_size(head);
    size_t i = 0;
    struct list_head *it, *parray[len];
    while (!list_empty(head)) {
        it = head->next;
        list_del_init(it);
        parray[i] = it;
        ++i;
    }
    INIT_LIST_HEAD(head);
    /* Queue is empty now. */

    size_t window = len;
    srand(time(NULL));

    /* Fisher-Yates shuffle */
    for (i = 0; i < len - 1; ++i) {
        int x = rand() % window;

        /* Insert the randomly picked node back to queue. */
        list_add_tail(parray[x], head);

        /* Replace the randomly picked node with that at the end of window */
        parray[x] = parray[window - 1];
        --window;
    }
    list_add_tail(parray[0], head);

    return true;
}