2022q1 Homework1 (lab0)

contributed by < Herakleos >

Environment

$ 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):                          4
On-line CPU(s) list:             0-3
Thread(s) per core:              2
Core(s) per socket:              2
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           142
Model name:                      Intel(R) Core(TM) i5-7200U CPU @ 2.50GHz
Stepping:                        9
CPU MHz:                         799.743
CPU max MHz:                     3100.0000
CPU min MHz:                     400.0000
BogoMIPS:                        5399.81
Virtualization:                  VT-x
L1d cache:                       64 KiB
L1i cache:                       64 KiB
L2 cache:                        512 KiB
L3 cache:                        3 MiB

---

Requirements

• Fork lab0-c from Github.
• Modify queue.[ch], and several files to meet the requirements of the automatic test.
  • How to write a good commit message.
  • Read 「你所不知道的 C 語言: linked list 和非連續記憶體」 carefully to improve your code.
  • Read lib/list_sort.c carefully, and try import to lab-0c. Compare the efficiency between the source code and yours.
• Add a new command shuffle in qtest by using Fisher–Yates shuffle to shuffle every nodes in the queue.
• Add a new command web in qtest to provide functions of web server.
  • Try to integrate tiny-web-server.
• Record your developing proccess.
  • Use Address Sanitizer to fix the problem while running qtest.
  • Use Valgrind to fix the memory problem while implement qtest, by using Massif to visualize the memory usage in the "simulation" progress.
  • Describe how to use select system call in this program, analyze the console.c and describe the concern and concept of using CS:APP [RIO package] in the program.
  • Read 〈Dude, is my code constant time?〉carefully, explain how does the program analyze "simulation" with experiment. You need to describe Student's t-distribution and how the program works.

There are serveral critical problems now, try to solve it and pull request.

---

Queue Functions

q_new:

    struct list_head *node = malloc(sizeof(struct list_head));
    if (!node)
        return NULL;
    INIT_LIST_HEAD(node);
    return node;

"Our program needs to use regular malloc/free" is written in qtest.c. Instead of using kmalloc(sizeof(struct list_head), GFP_KERNAL) or kfree.

q_free:

    // skip empty or NULL check
    struct list_head *li, *tmp;
    list_for_each_safe (li, tmp, l) {
        element_t *delete = list_entry(li, element_t, list);
        list_del(li);
        q_release_element(delete);
    }
    free(l);

The correct way to free the node, is to use q_release_element in order to release every single element in the node. If you free the node itself may occur "Freed queue, but … blocks are still allocated"

q_insert_head, q_insert_tail:

    // skip empty or NULL check
    element_t *new_head = malloc(sizeof(element_t));
    if (!new_head)
        return false;
    INIT_LIST_HEAD(&new_head->list);
    size_t size = sizeof(char) * (strlen(s) + 1);   // for NULL terminator
    new_head->value = malloc(size);
    if (!new_head->value) {
        free(new_head);
        return false;
    }
    strncpy(new_head->value, s, size);
    list_add(&new_head->list, head);
    return true;

The q_insert_tail is similar to q_insert_head, without initialize list head and change the function list_add to list_add_tail. I also found that,

• Instead of using strncpy, strscpy is often used in linux kernal.
  string: provide strscpy()

q_remove_head, q_remove_tail:

    // skip empty or NULL check
    element_t *remove = list_first_entry(head, element_t, list);
    list_del_init(head->next);

    if (sp) {
        memset(sp, '\0', bufsize);                  // plus a null terminator
        strncpy(sp, remove->value, (bufsize - 1));  // maximum of bufsize-1
    }
    return remove;

The q_remove_tail is much like q_remove_head, in spite of using list_del_init but list_del and replace list_first_entry to list_last_entry.

q_delete_mid:

    // find mid start
    struct list_head *forward = head->next, *backward = head->prev;
    while (forward != backward) {
        forward = forward->next;
        if (forward == backward)
            break;
        backward = backward->prev;
    }
    return forward;
    // find mid end
        
    // skip empty or NULL check
    struct list_head *forward = find_mid(head);
    element_t *delete = list_entry(forward, element_t, list);
    list_del(forward);
    q_release_element(delete);
    return true;

There are two ways to find the middle element. The other one is to set a fast and a slow parameter as following, the method is often used when we got a singly linked list. Since we got a doubly linked structure in the function, traversing from the both side is a better approach.

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

q_delete_dup:

    // skip empty or NULL check
    int delete = 0;
    struct list_head *li, *tmp;
    list_for_each_safe (li, tmp, head) {
        element_t *current = list_entry(li, element_t, list);
        element_t *next = list_entry(li->next, element_t, list);
        if ((li->next != head) && !strcmp(current->value, next->value)) {
            delete = 1;
            list_del(li);
            q_release_element(current);
        } else if (delete) {
            list_del(li);
            q_release_element(current);
            delete = 0;
        }
    }

While the for each function goes through every element in the sorted queue, we are able to create a parameter to check the current element is duplicate or not. Delete the current duplicate element and change the status, the rest of the work belongs to the next round.

q_swap:

    // skip empty or NULL check
    struct list_head *cur = head->next;
    while ((cur != head) && (cur->next != head)) {
        struct list_head *tmp = cur->next;
        list_del(cur);
        list_add(cur, tmp);
        cur = cur->next;
    }

This function is not a typical swap but attempt to swap every two adjacent nodes. This reminds me list_swap do list_del, list_replace and list_add at the end. Brillant.

    // list_replace start
    new->next = old->next;
    new->next->prev = new;
    new->prev = old->prev;
    new->prev->next = new;
    // list_replace end

    // list_swap start
    struct list_head *pos = e2->prev;

    list_del(e2);
    list_replace(e1, e2);
    if (pos == e1)
        pos = e2;
    list_add(e1, pos);
    // list_swap end

q_reverse:

    // swap function start
    char *tmp = *x;
    *x = *y;
    *y = tmp;  
    // swap function end    

    // skip empty or NULL check
    struct list_head *forward = head->next, *backward = head->prev;
    while (forward != backward) {
        element_t *fwd = list_entry(forward, element_t, list);
        element_t *bwd = list_entry(backward, element_t, list);
        swap(&fwd->value, &bwd->value);
        forward = forward->next;
        if (forward == backward)
            break;
        backward = backward->prev;
    }

Reverse can be seen as "switching the first and the last element, the second and the last-1 element… all the way to the middle".

q_sort:

I devide the sorting proccess to 3 parts:

1. Main:
   First, transform the doubly linked list structure to singly, that will be way more easier. We then rebuild the connect after sorting.

    // skip empty or NULL check
    // to singly linked list
    head->prev->next = NULL;

    head->next = merge_sort(head->next);

    // to doubly linked list
    struct list_head *tail = head;
    while (tail->next) {
        tail->next->prev = tail;
        tail = tail->next;
    }
    tail->next = head;
    head->prev = tail;

2. Split the queue:
   Second, we find the middle element to split the queue, then we sort and merge them.

    if (!head || !head->next)
        return head;

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

    struct list_head *left = merge_sort(head);
    struct list_head *right = merge_sort(fast);

    return merge(left, right);

More details: Linked list sort

3. Merge:
   The function is modified from list_sort in /lib/list_sort.c.

    // merge start    
    struct list_head *head = NULL, **tail = &head;

    for (;;) {
        if (strcmp(list_entry(a, element_t, list)->value,
                   list_entry(b, element_t, list)->value) <= 0) {
            *tail = a;
            tail = &a->next;
            a = a->next;
            if (!a) {
                *tail = b;
                break;
            }
        } else {
            *tail = b;
            tail = &b->next;
            b = b->next;
            if (!b) {
                *tail = a;
                break;
            }
        }
    }
    return head;
    // merge end    

Github Action:

You did it!

---

Qtest

Shuffle

Since the original shuffle algorithm spend too much effort to get the target from the remaining number. The modern approach is to exchange the target with the tail element decreasing each round.

    for i from n−1 downto 1 do
         j ← random integer such that 0 ≤ j ≤ i
         exchange a[j] and a[i]

1. Add new line in console_init.

    ADD_COMMAND(shuffle, "               | Shuffle every node in queue");

2. Add new function do_shuffle.

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

    if (!l_meta.l)
        report(3, "Warning: Calling shuffle on null queue");
    error_check();

    int cnt = q_size(l_meta.l);
    if (cnt < 2)
        report(3, "Warning: Calling shuffle on single node");
    error_check();

    struct list_head *li;
    for (li = l_meta.l->prev; (li != l_meta.l && cnt > 1); li = li->prev) {
        int r = rand() % cnt;
        struct list_head *tmp = l_meta.l->next;
        for (int i = 0; i < r; i++)
            tmp = tmp->next;
        // same swap function as above
        swap(&list_entry(li, element_t, list)->value,
             &list_entry(tmp, element_t, list)->value);
        cnt--;
    }

    show_queue(3);
    return !error_check();

Noticed that linux kernal has it own random number generator, I tried to trace get_random_bytes in /drivers/char/random.c

Web

Working on…

Reading

lib/list_sort.c

Dude, is my code constant time?