2022q1 Homework1 (lab0)

contributed by < yaohwang99 >

實驗環境

$ 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):                          8
On-line CPU(s) list:             0-7
Thread(s) per core:              2
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           158
Model name:                      Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
Stepping:                        9
CPU MHz:                         2800.000
CPU max MHz:                     3800.0000
CPU min MHz:                     800.0000
BogoMIPS:                        5599.85
Virtualization:                  VT-x
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        6 MiB
NUMA node0 CPU(s):               0-7

作業要求

詳細閱讀 lab0 說明，依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改。

• q_new: 建立新的「空」佇列
• q_free: 釋放佇列所佔用的記憶體
• q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)
• q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)
• q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點
• q_release_element: 釋放特定節點的記憶體空間
• q_size: 計算目前佇列的節點總量
• q_delete_mid: 移走佇列中間的節點
• q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點
• q_swap: 交換佇列中鄰近的節點
• q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點
• q_sort: 以遞增順序來排序鏈結串列的節點

針對佇列的操作

q_new

Create empty queue.

• Return NULL if could not allocate space
• malloc() will return NULL if allocate failed.
• next and prev both points to head because it is a circular list

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if(!head)
        return NULL;
    head->next = head;
    head->prev = head;
    return head;
}

q_size

• Return number of elements in queue.
• Return 0 if q is NULL or empty

Copy q_size() from lab0

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_insert_head

Attempt to insert element at head of queue.

Use strlen and strcpy to copy string.
Attempted to insert node by writing the code myself, but later discovered that we can use list_add() from list.h. Because the list is circular, the insert procedure will always be the same.

First attempt:

bool q_insert_head(struct list_head *head, char *s)
{
    char *tmp = malloc((strlen(s)+1)*sizeof(char));
    element_t *n = malloc(sizeof(element_t));
    if(!tmp||!n)
        return false;
    n->value = strcpy(tmp,s);
    list_add(&n->list, head);
    return true;
}

Because strcpy causes memory leak, use strdup:

bool q_insert_head(struct list_head *head, char *s)
{
    char *tmp = strdup(s);
    element_t *n = malloc(sizeof(element_t));
    if (!tmp || !n)
        return false;
    n->value = tmp;
    list_add(&n->list, head);
    return true;
}

You should explain why it matters.

jserv

The strcpy() function does not stop until it sees '\0' in the source string. If the source string is longer than dst string, strcpy() will overwrite some unallocated memory contiguous to the intended destination.
Reference: Common vulnerabilities guide for C programmers

q_insert_tail

Same as q_insert_head()

bool q_insert_tail(struct list_head *head, char *s)
{
    char *tmp = strdup(s);
    element_t *n = malloc(sizeof(element_t));
    if (!tmp || !n)
        return false;
    n->value = tmp;
    list_add_tail(&n->list, head);
    return true;
}

---

Read list.h

Because I didn't read though list.h, I spent a lot of time writing q_insert(). I decide to read through list.h before continuing.

---

q_free

Uselist_for_each_entry_safe() to safely remove element.

void q_free(struct list_head *l)
{
    if (!l)
        return;
    element_t *entry;
    element_t *safe;
    list_for_each_entry_safe (entry, safe, l, list) {
        list_del_init(&entry->list);
        q_release_element(entry);
    }
    free(l);
}

q_remove_head

Fix "Error: Failed to store removed value"

The error occurs because we need to copy the value of deleted element to sp.
Cannot use strndup() because that makes sp point to other memory.
Use strncpy() to copy the value to sp.

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head)
        return NULL;
    if (list_empty(head))
        return NULL;
    element_t *tmp = list_first_entry(head, element_t, list);
    strncpy(sp, tmp->value, bufsize - 1);
    list_del_init(&tmp->list);
    return tmp;
}

q_remove_tail

Same as q_remove_head()

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head)
        return NULL;
    if (list_empty(head))
        return NULL;
    element_t *tmp = list_last_entry(head, element_t, list);
    strncpy(sp, tmp->value, bufsize - 1);
    list_del_init(&tmp->list);
    return tmp;
}

q_del_mid

Use two pointer from head and tail and move torward mid, remove target when they point to mid.

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head)
        return false;
    if (list_empty(head))
        return false;
    element_t *front = list_entry(head->next, element_t, list),
              *back = list_entry(head->prev, element_t, list);
    for (; front != back && front->list.next != &back->list;
         front = list_entry(front->list.next, element_t, list),
         back = list_entry(back->list.prev, element_t, list)) {
    }

    list_del_init(&back->list);
    q_release_element(back);
    return true;
}

q_delete_dup

Use two pointer to sequence of identical values and move them to rec.
Call q_free() to delete rec.

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

    if (!head)
        return false;
    if (list_empty(head))
        return false;
    if (list_is_singular(head))
        return true;
    struct list_head *rec = q_new();
    struct list_head *front = head->next;
    struct list_head *back = head->next->next;
    while (front != head && back != head) {
        element_t *back_entry = list_entry(back, element_t, list);
        element_t *front_entry = list_entry(front, element_t, list);
        while (strcmp(front_entry->value, back_entry->value) == 0) {
            back = back->next;
            if (back == head)
                break;
            back_entry = list_entry(back, element_t, list);
        }
        if (front->next != back) {
            struct list_head *prev = front->prev;

            rec->next->prev = back->prev;
            back->prev->next = rec->next;
            front->prev = rec;
            rec->next = front;

            prev->next = back;
            back->prev = prev;
        }

        front = back;
        back = back->next;
    }
    q_free(rec);
    return true;
}

q_reverse

Use prev, next, and curr to reverse list.

void q_reverse(struct list_head *head)
{
    if (!head)
        return;
    if (list_empty(head))
        return;
    if (list_is_singular(head))
        return;
    struct list_head *curr = head;
    struct list_head *prev = head->prev;
    struct list_head *next = head->next;
    do {
        curr->prev = next;
        curr->next = prev;
        prev = curr;
        curr = next;
        next = next->next;
    } while (curr != head);
}

q_sort

1. Find the middle point to divide the list into two halves.
2. Call merge_sort for first half.
3. Call mergeSort for second half.
4. Merge the two halves sorted in step 2 and 3.

void merge(struct list_head **li, struct list_head **mi, struct list_head **ri)
{
    struct list_head *l_start = *li;
    struct list_head *l_end = *mi;
    struct list_head *r_start = (*mi)->next;
    struct list_head *r_end = *ri;
    struct list_head *walk = (*li)->prev;

    struct list_head *head = (*li)->prev;
    struct list_head *tail = (*ri)->next;

    element_t *l_entry = list_entry(l_start, element_t, list);
    element_t *r_entry = list_entry(r_start, element_t, list);
    while (true) {
        if (strcmp(l_entry->value, r_entry->value) > 0) {
            struct list_head *next_r_start = r_start->next;
            list_del_init(r_start);
            list_add(r_start, walk);

            walk = walk->next;
            if (r_start == r_end) {
                break;
            }

            r_start = next_r_start;
            r_entry = list_entry(r_start, element_t, list);
        } else {
            struct list_head *next_l_start = l_start->next;
            list_del_init(l_start);
            list_add(l_start, walk);
            walk = walk->next;
            if (l_start == l_end) {
                break;
            }

            l_start = next_l_start;
            l_entry = list_entry(l_start, element_t, list);
        }
    }
    *li = head->next;
    *ri = tail->prev;
}
void merge_sort(struct list_head **li, struct list_head **ri)
{
    if (*li == *ri)
        return;
    struct list_head *front = *li, *back = *ri;
    for (; front != back && front->next != back;
         front = front->next, back = back->prev) {
    }
    merge_sort(li, &back->prev);
    merge_sort(&back, ri);
    struct list_head **mi = &back->prev;
    merge(li, mi, ri);
}
/*
 * Sort elements of queue in ascending order
 * No effect if q is NULL or empty. In addition, if q has only one
 * element, do nothing.
 */
void q_sort(struct list_head *head)
{
    merge_sort(&head->next, &head->prev);
}

make test result:

Need to fix some error in allocating memory and string copy.
Everything else pass.

+++ TESTING trace trace-07-string:
---     trace-07-string 0/6
# Test of truncated strings
+++ TESTING trace trace-10-robust:
# Test operations on NULL queue
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
---     trace-10-robust 0/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
ERROR: Freed queue, but 10 blocks are still allocated
---     trace-11-malloc 0/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
ERROR: Freed queue, but 11 blocks are still allocated
---     trace-12-malloc 0/6

Fix error

q_remove_head() and q_remove_tail()

If sp is NULL, do nothing.
Compare strlen(tmp->value) with bufsize-1. Copy tmp->value to sp and set last element of sp to '\0'.

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head)
        return NULL;
    if (list_empty(head))
        return NULL;
    element_t *tmp = list_first_entry(head, element_t, list);
    list_del_init(&tmp->list);
    if (!sp)
        return tmp;
    size_t len = strlen(tmp->value);
    len = len > bufsize - 1 ? bufsize - 1 : len;
    strncpy(sp, tmp->value, len);
    sp[len] = '\0';
    return tmp;
}

q_insert_head() and q_insert_tail()

Return false when strdup() failed (malloc failed).
Free tmp and return false when malloc for new element failed.

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    if (!s)
        return false;
    char *tmp = strdup(s);
    if (!tmp)
        return false;
    element_t *n = malloc(sizeof(element_t));
    if (!n) {
        free(tmp);
        return false;
    }
    n->value = tmp;
    list_add(&n->list, head);
    return true;
}

q_sort()

Return if queue is empty.

void q_sort(struct list_head *head)
{
    if (!head)
        return;
    merge_sort(&head->next, &head->prev);
}

Add sort from list_sort.c

Create list_sort.h file, copy-paste the code from list_sort.c and modify the code to suit our need.

1. Initiate head to NULL in line 19 in merge() to avoid compile warning/error.

struct list_head *head = NULL, **tail = &head;

2. Include needed library, define list_cmp_func_t, likely(),unlikely() and compare function compare_entry for comparison.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "harness.h"
#include "queue.h"
#define likely(x) __builtin_expect((x), 1)
#define unlikely(x) __builtin_expect((x), 0)

typedef int list_cmp_func_t(void *, struct list_head *, struct list_head *);
int compare_entry(void *priv, struct list_head *a, struct list_head *b)
{
    element_t *ca = list_entry(a, element_t, list);
    element_t *cb = list_entry(b, element_t, list);
    return strcmp(ca->value, cb->value);
}
3. Define the funtion called by qtest, `priv` is always `NULL`, it is unused.
```c
void linux_q_sort(struct list_head *head)
{
    if (!head)
        return;
    void *priv = NULL;
    list_cmp_func_t *cmp = compare_entry;
    list_sort(priv, head, cmp);
}

4. Add command for linux_q_sort() in qtest.c

ADD_COMMAND(
        lsort,
        "                | Sort queue in ascending order by linux list sort");

5. Add do_lsort() by modifying do_sort() in qtest.c.

bool do_lsort(int argc, char *argv[])
{
    ...
   
    if (exception_setup(true))
        linux_q_sort(l_meta.l);
    ...
}

DON'T DO THAT. You can introduce single sort command with different options, which allow run-time switching.

jserv

Update

Delete the lsort command and change the sort command for different option.

bool do_sort(int argc, char *argv[])
{
    if (argc > 2) {
        report(1, "%s takes 0 or 1 arguments", argv[0]);
        return false;
    }
    ...

    if (argc == 1) {
        if (exception_setup(true))
            q_sort(l_meta.l);
    } else {
        if (exception_setup(true))
            linux_q_sort(l_meta.l);
    }
    ...
}

Compare sort

Compare the two method with traces/trace-sort.cmd

result: 0.58/0.68=0.85, the sort from linux is about 15% faster.

# Test performance of sort and linux sort with random orders
option fail 0
option malloc 0
new
ih RAND 500000
time sort 0
new
ih RAND 500000
time sort 0
new
ih RAND 500000
time sort 0
new
ih RAND 500000
time sort 0
new
ih RAND 500000
time sort 0
new
ih RAND 500000
time sort
new
ih RAND 500000
time sort
new
ih RAND 500000
time sort
new
ih RAND 500000
time sort
new
ih RAND 500000
time sort
# Exit program
quit

Implement shuffle

Add shuffle command

1. In qtest.c, add the following code.

ADD_COMMAND(shuffle, "                | Shuffle queue.");

2. Add do_shuffle() command like do_sort().

bool do_shuffle(int argc, char *argv[])
{
    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();

    set_noallocate_mode(true);
    if (exception_setup(true))
        q_shuffle(l_meta.l);
    exception_cancel();
    set_noallocate_mode(false);

    bool ok = true;
    show_queue(3);
    return ok && !error_check();
}

Implement Fisher-Yates shuffle algorithm

Add the following code in list_sort.h.

Pre-allocate array to store pointers to achieve O(n) time complexity.

void q_shuffle(struct list_head *head)
{
    if (!head)
        return;
    if (list_empty(head))
        return;
    if (list_is_singular(head))
        return;
    srand(time(NULL));

    int len = q_size(head);
    struct list_head *target = head->next;
    struct list_head *tail = head->prev;
    struct list_head **list_arr = malloc(len * sizeof(struct list_head *));
    if (!list_arr) {
        printf("list_arr malloc failed\n");
        return;
    }
    for (int i = 0; i < len; ++i) {
        list_arr[i] = target;
        target = target->next;
    }
    while (len) {
        int random = rand() % len;
        if (random == len - 1) {
            tail = tail->prev;
            len--;
            continue;
        }
        target = list_arr[random];
        struct list_head *target_prev = target->prev;
        struct list_head *tail_next = tail->next;
        list_del_init(tail);
        list_add(tail, target_prev);
        list_del_init(target);

        target->prev = tail_next->prev;
        tail_next->prev = target;
        target->next = tail_next;
        target->prev->next = target;

        list_arr[random] = tail;
        list_arr[len - 1] = target;
        tail = tail_next->prev->prev;
        len--;
    }
    free(list_arr);
}

Web server

Reference: lab0-c, 2020leon

1. Split tiny.c into tiny.c and tiny.h. Include tiny.h in other file.
2. Fix error detected by cppcheck (unused function, variable scope, potential sscanf() error).
3. Declare extern int listenfd; extern bool noise; because we need to use them in other script.
4. Add do_web() and web command to qtest.c.
5. Modify cmd_select() and run_console() according to lab0-c.

process()

The web server has to respond something to form a connection. Otherwise, the browser will display "unable to connect".

void handle_request(int fd)
{
    writen(fd, "server", strlen("server"));
}
char *process(int fd, struct sockaddr_in *clientaddr)
{
#ifdef LOG_ACCESS
    printf("accept request, fd is %d, pid is %d\n", fd, getpid());
#endif
    http_request req;
    parse_request(fd, &req);
    int status = 200;

    char *p = req.filename;
    /* Change '/' to ' ' */
    while (*p) {
        ++p;
        if (*p == '/') {
            *p = ' ';
        }
    }
    handle_request(fd);
#ifdef LOG_ACCESS
    log_access(status, clientaddr, &req);
#endif
    char *ret = malloc(strlen(req.filename) + 1);
    strncpy(ret, req.filename, strlen(req.filename) + 1);

    return ret;
}

result:

$ ./qtest
cmd> web
listen on port 9999
cmd> 
cmd> accept request, fd is 4, pid is 39369
127.0.0.1:35274 200 - '.'
Unknown command '.'
cmd> accept request, fd is 4, pid is 39369
127.0.0.1:35276 200 - 'favicon.ico'
Unknown command 'favicon.ico'
cmd> accept request, fd is 4, pid is 39369
127.0.0.1:35278 200 - 'new'
l = []
cmd> accept request, fd is 4, pid is 39369
127.0.0.1:35280 200 - 'favicon.ico'
Unknown command 'favicon.ico'
cmd> accept request, fd is 4, pid is 39369
127.0.0.1:35282 200 - 'ih RAND 1000'
l = [hvvbiggpa joxngrm mlffsdmqe fvrhq jaagnqc lthyhwy vnbszvyp hvxnn wslmpadd uvmudn aqequ uyqxnpl ducxibkr fwrtkloq huflsrb eqvizffok lqsikqw fpxkqvj wqrepu pwtppmtx ngrevsif pwycz proyuyrrd ivbnpkkcp swfonxhn aulxklec niyet djrvwrsta hvoxh inshjpjir ... ]
cmd> accept request, fd is 4, pid is 39369
127.0.0.1:35284 200 - 'favicon.ico'
Unknown command 'favicon.ico'
cmd> accept request, fd is 4, pid is 39369
127.0.0.1:35286 200 - 'sort'
l = [acuvclab adgvveq aemil afifxh afphp afqfwyuw afsoa aglveoklb agzctnrn ahwjyg aioknms ajehvsj ajryccr ajvito akccvrhb almzz alskvrh alvklner amafepe amerbmi amgaeqf amwvf aneqyycc anjfcq anmdao aorjbzlg apkbzaer apnbdw apnlt aqequ ... ]
cmd> accept request, fd is 4, pid is 39369
127.0.0.1:35288 200 - 'favicon.ico'
Unknown command 'favicon.ico'
Error limit exceeded.  Stopping command execution

TODO:

1. We cannot connect to the server until at least one command is executed after the web command.
2. Fix 'favicon.ico' error.

參考資訊

• 共筆格式參考：共筆示範