---
tags: linux2022
---

# 2022q1 Homework1 (lab0)
contributed by < `AxotZero` >

<s>
> My UBUNTU haven't install Chinese Input Tool.
- Because of personal reasons, I was late to join the course. I started watching youtube videos on 02/19 and finish the basic implementation of queue.c on 02/21. Still have a long journey to completely finish HW1.
</s>

:::danger
Show me the code rather than murmur!
:notes: jserv
:::

## 實驗環境

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

$ lscpu
架構：                           x86_64
CPU 作業模式：                   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
每核心執行緒數：                 2
每通訊端核心數：                 4
Socket(s):                       1
NUMA 節點：                      1
供應商識別號：                   GenuineIntel
CPU 家族：                       6
型號：                           158
Model name:                      Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz
製程：                           9
CPU MHz：                        3600.000
CPU max MHz:                     4200.0000
CPU min MHz:                     800.0000
BogoMIPS:                        7200.00
虛擬：                           VT-x
L1d 快取：                       128 KiB
L1i 快取：                       128 KiB
L2 快取：                        1 MiB
L3 快取：                        8 MiB
NUMA node0 CPU(s)：              0-7

## 針對佇列的操作
### q_new

struct list_head *q_new()
{
    struct list_head *q = malloc(sizeof(struct list_head));
    if (q)
        INIT_LIST_HEAD(q);
    return q;
}

### q_free

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

    element_t *safe = NULL;
    element_t *prev = NULL;
    list_for_each_entry_safe (prev, safe, l, list)
        q_release_element(prev);
    free(l);
}

### q_insert_head, q_insert_tail
Due to the same behavior of **q_insert_head** and **q_insert_tail** that both of them need to new an element, I create a function **new_element**.

element_t *new_element(char *s)
{
    element_t *q = malloc(sizeof(element_t));
    if (!q)
        return NULL;

    size_t s_len = strlen(s);
    q->value = malloc(s_len + 1);

    if (!q->value) {
        free(q);
        return NULL;
    }
    strncpy(q->value, s, strlen(s));
    q->value[s_len] = '\0';
    return q;
}

bool q_insert_head(struct list_head *head, char *s)
{
    // check if it is null
    if (!head)
        return false;

    // initialize the new node
    element_t *q = new_element(s);
    if (!q)
        return false;

    // add new node to head;
    list_add(&q->list, head);
    return true;
}


bool q_insert_tail(struct list_head *head, char *s)
{
    // check if it is null
    if (!head)
        return false;

    // initialize the new node
    element_t *q = new_element(s);
    if (!q)
        return false;

    // add new node to tail;
    list_add_tail(&q->list, head);
    return true;
}

Thanks for [laneser 開發紀錄 (lab0)](https://hackmd.io/@laneser/linux2022_lab0). I improve function **new_element** with **strdup**.

element_t *new_element(char *s)
{
    element_t *q = malloc(sizeof(element_t));
    if (!q)
        return NULL;

    q->value = strdup(s);
    if (!q->value) {
        free(q);
        return NULL;
    }
    return q;
}

### q_remove_head, q_remove_tail
Due to the same behaviour of these two, I create a function **q_remove** wich remove the **target** node and copy the value of removed node to **sp**.

element_t *q_remove(struct list_head *target, char *sp, size_t bufsize)
{
    // remove target
    list_del_init(target);

    // get target element
    element_t *ret = container_of(target, element_t, list);

    // copy removed element value to sp
    if (sp && ret->value) {
        strncpy(sp, ret->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return ret;
}

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    // check queue is null of empty;
    if (!head || list_empty(head))
        return NULL;

    // remove head
    element_t *ret = q_remove(head->next, sp, bufsize);
    return ret;
}

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    // check queue is null of empty;
    if (!head || list_empty(head))
        return NULL;

    // remove tail
    element_t *ret = q_remove(head->prev, sp, bufsize);
    return ret;
}

### q_size

int q_size(struct list_head *head)
{
    // check null or empty
    if (!head || list_empty(head))
        return 0;

    // compute len
    int len = 0;
    struct list_head *node = NULL;
    list_for_each (node, head)
        ++len;
    return len;
}

### q_delete_mid
#### slow, fast pointer version.

bool q_delete_mid(struct list_head *head)
{
    // check if it's NULL or empty
    if (!head || list_empty(head))
        return false;

    // search middle node
    struct list_head **slow = &head->next;
    for (struct list_head *fast = head->next->next;
         fast != head && fast->next != head; fast = fast->next->next)
        slow = &(*slow)->next;

    // get target element
    element_t *target = container_of(*slow, element_t, list);

    // remove node and release element
    list_del_init(*slow);
    q_release_element(target);
    return true;
}

#### Utilize prev pointer version
search by both sides.

bool q_delete_mid(struct list_head *head)
{
    // check if it's NULL or empty
    if (!head || list_empty(head))
        return false;

    // search middle node
    struct list_head *r = head->next, *l = head->prev;
    for(; r != l && r->next != l; r = r->next)
        l = l->prev;

    // remove node and release element
    list_del_init(l);
    q_release_element(container_of(l, element_t, list));
    return true;
}

### q_delete_dup
Searches the start node and end node of duplicate string list, removed duplicate list and concat to **remove_head**. At the end of the algorithm, **q_free(remove_head)**. In the future improvement, this operation may can be executed when the system is not busy.

bool q_delete_dup(struct list_head *head)
{
    // check if it's NULL or empty
    if (!head || list_empty(head))
        return false;

    // check if it's singular
    if (list_is_singular(head))
        return true;

    struct list_head *first_node = head->next, *end_node = head->next;
    struct list_head *remove_head = q_new(), *tmp = q_new();
    while (end_node != head) {
        // search the start and end of duplicates string node
        element_t *first_element = container_of(first_node, element_t, list);
        element_t *end_element = NULL;
        do {
            end_node = end_node->next;
            end_element = container_of(end_node, element_t, list);
        } while (end_node != head &&
                 !strcmp(first_element->value, end_element->value));

        // concat duplicates node to remove_head
        if (first_node->next != end_node) {
            list_cut_position(tmp, first_node->prev, end_node->prev);
            list_splice_init(tmp, remove_head);
        }
        first_node = end_node;
    }
    q_free(remove_head);
    q_free(tmp);
    return true;
}

### q_swap

void q_swap(struct list_head *head)
{
    // check if it's NULL or empty
    if (!head || list_empty(head))
        return;

    // q_swap
    struct list_head *node = head->next, *curr = NULL, *next = NULL;
    while (node != head && node->next != head) {
        next = node->next;
        curr = node;
        node = node->next->next;

        // swap adjacent nodes.
        curr->next = next->next;
        next->prev = curr->prev;
        curr->prev->next = next;
        curr->prev = next;
        next->next->prev = curr;
        next->next = curr;
    }
}

### q_reverse

void swap_list_head(struct list_head **a, struct list_head **b)
{
    struct list_head *tmp = *a;
    *a = *b;
    *b = tmp;
}

void q_reverse(struct list_head *head)
{
    // check if it's NULL or empty
    if (!head || list_empty(head))
        return;

    struct list_head *safe = NULL, *curr = NULL;

    list_for_each_safe (curr, safe, head)
        swap_list_head(&curr->prev, &curr->next);
    swap_list_head(&curr->prev, &curr->next);
}

### q_sort

struct list_head *merge_two_list(struct list_head *a, struct list_head *b)
{
    struct list_head *head = NULL, **ptr = &head;
    for (struct list_head **node = NULL; a && b; *node = (*node)->next) {
        node = strcmp(container_of(a, element_t, list)->value,
                      container_of(b, element_t, list)->value) < 0
                   ? &a
                   : &b;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *) ((uintptr_t) a | (uintptr_t) b);
    return head;
}

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

    // search middle node
    struct list_head *slow = head, *fast = head->next;
    for (; fast && fast->next; fast = fast->next->next)
        slow = slow->next;

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

    return merge_two_list(merge_sort(head), merge_sort(middle));
}

void q_sort(struct list_head *head)
{
    // check if it's NULL or empty
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    // remove the link of tail and head to create stop condition for merge_sort
    head->prev->next = NULL;

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

    // assign prev to each node
    struct list_head *tmp = head;
    while (tmp->next) {
        tmp->next->prev = tmp;
        tmp = tmp->next;
    }
    // concat head and tail
    tmp->next = head;
    head->prev = tmp;
}

## Add "shuffle" command to qtest
- I create `extra_func.h` and `extra_func.c` to write the code for **shuffle**
- There are two version of shuffle
1. q_shuffle: need to for-loop to search the node we want to swap
- Time Complexity: `O(n^2)`
- Space Complexity: `O(1)`
3. q_shuffle_dp: store all the address to a list then we can avoid the for-loop to search the node
- Time Complexity: `O(n)`
- Space Complexity: `O(N)`
- Hence, I add two commands.

    ADD_COMMAND(shuffle,"| shuffle the queue with O(n^2) time "
                "complexity and constant space complexity");
    ADD_COMMAND(shuffle_dp,"| shuffle the queue with O(n) time and space "

> shuffle_dp will also be used to compare merge_sort.

void swap_ptr(struct list_head **a, struct list_head **b)
{
    struct list_head *tmp = *a;
    *a = *b;
    *b = tmp;
}
/*
 * Swap nodes in doubly linked list
 */
void swap_node(struct list_head *a, struct list_head *b)
{
    if (a == b)
        return;
    else if (a->next == b || b->next == a)  // if they are neighbors
    {
        // decide who is left and who is right
        struct list_head *l = a, *r = b;
        if (b->next == a) {
            r = a;
            l = b;
        }

        // swap
        l->next = r->next;
        r->prev = l->prev;
        l->prev->next = r;
        l->prev = r;
        r->next->prev = l;
        r->next = l;
        
    } else {
        a->next->prev = b;
        b->next->prev = a;
        a->prev->next = b;
        b->prev->next = a;
        swap_ptr(&a->next, &b->next);
        swap_ptr(&a->prev, &b->prev);
    }
}

/*
 * Get list node by given index
 */
struct list_head *get_node_by_idx(struct list_head *head, int idx)
{
    for (; idx > 0; --idx)
        head = head->next;
    return head;
}

/*
 * Shuffle the list with Fisher–Yates shuffle algorithm
 * Time Complexity: O(N^2)
 * Space Complexity: O(1)
 */
void q_shuffle(struct list_head *head)
{
    srand(time(NULL));
    struct list_head *curr = head->prev;
    struct list_head *curr_next = NULL;
    for (int i = q_size(head); i > 1; --i) {
        curr_next = curr->prev;
        swap_node(curr, get_node_by_idx(head, rand() % i));
        curr = curr_next;
    }
}

/*
 * Utilize extra space to shuffle with Fisher–Yates shuffle
 * Time Complexity: O(N)
 * Space Complexity: O(N)
 */
void q_shuffle_dp(struct list_head *head)
{
    srand(time(NULL));
    int len = q_size(head);

    // list space to store all addressed of the queue.
    struct list_head **dp = malloc(sizeof(struct list_head **) * len);
    struct list_head *curr = head->next;
    for (int i = 0; i < len; ++i, curr = curr->next)
        dp[i] = curr;

    // shuffle
    curr = head->prev;
    struct list_head *curr_prev = NULL, *tmp = NULL;
    for (int i = len; i > 1; --i) {
        curr_prev = curr->prev;
        // swap nodes
        tmp = dp[rand() % i];
        swap_node(curr, tmp);

        // swap addresses in the list space
        swap_ptr(&dp[i], &tmp);

        // move to next
        curr = curr_prev;
    }
    free(dp);
}

## Compare my merge_sort and linux/list_sort.c
1. I write a new `trace-19-compare_sort.cmd` which generate 750,000 elements to sort and contains three kinds of string `aaaa`, `cccc`, `eeee`

    new
    ih eeee 250000
    ih cccc 250000
    ih aaaa 250000    

    # sort sorted array
    time sort
    time linux_sort

    # sort reversed sorted array
    reverse
    time sort
    reverse
    time linux_sort

    # sort shuffled array
    shuffle_dp
    time sort
    shuffle_dp
    time linux_sort

3. comparison of **my_sort** and **linux_sort** in three cases.

| Cases | my_sort | linux_sort |
| -------- | -------- | -------- |
| sorted array | 0.278s | 0.15s |
| reversed sorted | 0.273s | 0.154s |
| shuffled | 1.236s | 0.744s |

    $ ./qtest  -f traces/trace-19-compare_sort.cmd 
    cmd> option fail 0
    cmd> option malloc 0
    cmd> 
    cmd> new
    l = []
    cmd> ih eeee 250000
    l = [eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee ... ]
    cmd> ih cccc 250000
    l = [cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc ... ]
    cmd> ih aaaa 250000
    l = [aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa ... ]
    cmd> 
    cmd> # sort sorted array
    cmd> time sort
    l = [aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa ... ]
    Delta time = 0.287
    cmd> time linux_sort
    l = [aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa ... ]
    Delta time = 0.150
    cmd> 
    cmd> # sort reversed sorted array
    cmd> reverse
    l = [eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee ... ]
    cmd> time sort
    l = [aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa ... ]
    Delta time = 0.273
    cmd> reverse
    l = [eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee ... ]
    cmd> time linux_sort
    l = [aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa ... ]
    Delta time = 0.154
    cmd> 
    cmd> # sort shuffled array
    cmd> shuffle_dp
    l = [cccc cccc aaaa aaaa eeee aaaa aaaa eeee aaaa aaaa aaaa cccc cccc aaaa aaaa eeee aaaa eeee aaaa eeee cccc aaaa aaaa eeee eeee eeee eeee aaaa eeee eeee ... ]
    cmd> time sort
    l = [aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa ... ]
    Delta time = 1.242
    cmd> shuffle_dp
    l = [eeee aaaa aaaa eeee aaaa cccc aaaa eeee aaaa aaaa aaaa cccc aaaa aaaa cccc aaaa eeee eeee cccc cccc eeee aaaa aaaa eeee eeee aaaa eeee aaaa cccc eeee ... ]
    cmd> time linux_sort
    l = [aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa ... ]
    Delta time = 0.744
    Freeing queue

## Tiny Web server
<!-- ### What is file descripter?
Since this is the first time I trace the c code, file descriptor is the thing that I'm curious the most. The -->

### First Development process - [git commit](https://github.com/AxotZero/lab0-c/commit/899f5862ee0a53dcb86e5b5ccc37dd69b49eed56)
1. Copy most of the code of [tiny web server](https://github.com/7890/tiny-web-server/blob/master/tiny.c) to my `extra_func.c`.
3. Add following code to `extra_func.h`

    extern int listenfd;
    extern bool noise;

    char *process(int fd, struct sockaddr_in *clientaddr);
    int open_listenfd();

3. Add command to `qtest.c` and overwrite function `run_console`, `cmd_select` to `console.c` from [lab01-tiny-web-server](https://hackmd.io/@sysprog/linux2022-lab0#%E6%95%B4%E5%90%88-tiny-web-server).
4. remove all cppcheck warning and errors.
- Still try to figuring out whether there is a better way to avoid
- **warning: sscanf() without field width limits can crash with huge input data. [invalidscanf]**.
- The following is my current solution.

      sscanf(buf, "%1023s %1023s", method, uri); 

- The solution of [LJP-TW](https://github.com/LJP-TW)

        sscanf(buf, "%" xstr(MAXLINE) "s %" xstr(MAXLINE) "s", method, uri); 

5. The web server now can work, but met two error:
- Diffirent behaviour between curl and browser
- If I send a command from through curl, the program will execute correctly

            curl -v localhost:9999/new
            curl -v localhost:9999/it/1

- If I send a command from the chrome browser, the program will execute the command at most three times. I think this is because of the auto-retry of chrome browser.
- If I run web server, any command from the console will get into infinite for-loop

### Bug Fix
1. Infinite for-loop
- In function `cmd_select`, I forgot to delete the condition ```if(has_infile)``` while we have user input. It leads ```cmdline = readline()``` will never be executed which makes the buffer never be clear. Hence, the `select()` always detect user input and leads to infinite for loop.
-