2021q1 Homework1 (lab0)

tags: `linux2021`

contributed by <Billy4195>

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

Requirements

Implementation

Struct design for `queue_t`

For the extra attributes that I added is an pointer tail to point the tail element of the queue, and size to store the number of elements in queue.
These two attributes are needed for the constant execution time for q_insert_tail and q_size





typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail; /* Linked list of elements */
    int size;
} queue_t;

`q_new()`

Allocate the memory for queue_t, if the allocation fail then return NULL as SPEC required. If success, initialize the attributes










queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (NULL == q)
        return NULL;
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

`q_free()`

q_free is used to free all the allocated memory space inside the queue struct. It is better to free the allocated memory from the inner of struct to outer. Otherwise, if we free the outer struct without recording the inner allocated memory, then we may cause memory leak because doesn't free the inner one, or read from the freed outer memory is also an dangerous operation.

As a result, we just traverse every element inside of the queue and using next to store the next element. Firstly, free the value memory, then free the element itself. After freed all the elements in the queue, we could finally free the queue_t itself.














void q_free(queue_t *q)
{
    list_ele_t *cur, *next;
    if (q) {
        cur = q->head;
        while (cur) {
            next = cur->next;
            free(cur->value);
            free(cur);
            cur = next;
        }
    }
    free(q);
}

`q_insert_head()`

The point of this function is to allocate the space for new element. Because all the allocated memory by malloc will be tracked, we can't use strdup function to allocate memory for the given string.

The tail pointer should also be setup if it has not been set.

I should take carefully of malloc failure, as line 9 and line 14 are two check for the malloc. Especially for lineine 14, don't forget to freed the allcated space for element































bool q_insert_head(queue_t *q, char *s)
{
    if (NULL == q)
        return false;

    list_ele_t *newh;
    int len = strlen(s);
    newh = malloc(sizeof(list_ele_t));
    if (NULL == newh)
        goto fail_head;
    newh->next = NULL;

    newh->value = (char *) malloc(sizeof(char) * (len + 1));
    if (NULL == newh->value)
        goto fail_value;

    memcpy(newh->value, s, len);
    newh->value[len] = '\0';

    newh->next = q->head;
    q->head = newh;
    if (NULL == q->tail)
        q->tail = newh;
    q->size++;
    return true;

fail_value:
    free(newh);
fail_head:
    return false;
}

`q_insert_tail`

The SPEC required us to implement an O(1) time complexity solution. As mentioned above, we have added a tail pointer to take care of this requirement. To achieve it, we just add element after the tail element and update the tail pointer.

The head pointer should also be check and set, if it has not been set.

I should also take care the malloc failure as we did in q_insert_head.
































bool q_insert_tail(queue_t *q, char *s)
{
    if (NULL == q)
        return false;

    int len = strlen(s);
    list_ele_t *node = malloc(sizeof(list_ele_t));
    if (NULL == node)
        goto fail_head;
    node->next = NULL;

    node->value = malloc(sizeof(char) * (len + 1));
    if (NULL == node->value)
        goto fail_value;

    memcpy(node->value, s, len);
    node->value[len] = '\0';

    if (q->tail)
        q->tail->next = node;

    q->tail = node;
    if (NULL == q->head)
        q->head = node;
    q->size++;
    return true;

fail_value:
    free(node);
fail_head:
    return false;
}

`q_remove_head`

As the requirement, we store the string of the head element in given sp pointer in L8~L13. At line 14 check if the head is the only element in the queue, if yes then we reset the tail pointer, too.






















bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (NULL == q || NULL == q->head)
        return false;

    list_ele_t *node = q->head;

    if (sp && bufsize > 0) {
        int vlen = strlen(node->value);
        int cpylen = vlen < bufsize ? vlen : bufsize - 1;
        memcpy(sp, node->value, cpylen);
        sp[cpylen] = '\0';
    }
    if (node == q->tail)
        q->tail = NULL;
    q->head = q->head->next;
    free(node->value);
    free(node);

    q->size--;
    return true;
}

`q_size`

To achieve the O(1) time complexity, I use the added size attribute to record the size of the queue.
Check the corner case when the given queue is NULL.







int q_size(queue_t *q)
{
    if (NULL == q)
        return 0;
    else
        return q->size;
}

`q_reverse`

I use to pointer left and right to traverse the queue and make the next pointer of each element point to the previous element to finish the reverse
























void q_reverse(queue_t *q)
{
    if (NULL == q || q->size <= 1)
        return;
    list_ele_t *left, *right;
    list_ele_t *tmp, *prev;
    prev = NULL;
    left = q->head;
    right = left->next;
    tmp = right->next;
    while (right) {
        left->next = prev;
        right->next = left;
        prev = left;
        left = right;
        right = tmp;
        tmp = tmp ? tmp->next : NULL;
    }
    left->next = prev;

    tmp = q->head;
    q->head = q->tail;
    q->tail = tmp;
}

`q_sort`

Recursive quick sort

I choose quick sort as the implementation ofq_sort. However, the worse case for quick sort may cause O(N^2) time complexity.



























































void q_sort(queue_t *q)
{
    if (NULL == q || q->size <= 1)
        return;

    list_ele_t *cur;
    quick_sort(&(q->head));
    cur = q->head;
    while (cur->next) {
        cur = cur->next;
    }
    q->tail = cur;
}


void list_add(list_ele_t **list, list_ele_t *node)
{
    node->next = *list;
    *list = node;
}

void list_concat(list_ele_t **left, list_ele_t *right)
{
    while (*left) {
        left = &((*left)->next);
    }
    *left = right;
}

void quick_sort(list_ele_t **list)
{
    if (NULL == list || NULL == *list)
        return;
    list_ele_t *pivot;
    list_ele_t *left = NULL, *right = NULL;
    list_ele_t *ptr;

    pivot = *list;
    ptr = pivot->next;
    pivot->next = NULL;

    while (ptr) {
        list_ele_t *node = ptr;
        ptr = ptr->next;
        if (strcmp(pivot->value, node->value) <= 0) {
            list_add(&right, node);
        } else {
            list_add(&left, node);
        }
    }

    quick_sort(&left);
    quick_sort(&right);

    *list = NULL;
    list_concat(list, left);
    list_concat(list, pivot);
    list_concat(list, right);
}

Failure

After finish the q_sort, some related test passed, but some are still failed.
















---     trace-15-perf   0/6
+++ TESTING trace trace-16-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
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
---     trace-16-perf   0/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---     TOTAL           88/100

Fix address sanitizer

As the SPEC mentioned, we need to fix the problem of address sanitizer, and and we can see the error message show at Line 15 that it is related to echo in console.c




























$ make SANITIZER=1
$ ./qtest
cmd> help
=================================================================
==103297==ERROR: AddressSanitizer: global-buffer-overflow on address 0x5611d6d743c0 at pc 0x5611d6d5d7bd bp 0x7ffd209c6730 sp 0x7ffd209c6720
READ of size 4 at 0x5611d6d743c0 thread T0
    #0 0x5611d6d5d7bc in do_help_cmd /home/su/repo/lab0-c/console.c:307
    #1 0x5611d6d5d8d0 in interpret_cmda /home/su/repo/lab0-c/console.c:221
    #2 0x5611d6d5e0b5 in interpret_cmd /home/su/repo/lab0-c/console.c:244
    #3 0x5611d6d5f7f8 in run_console /home/su/repo/lab0-c/console.c:660
    #4 0x5611d6d5c3e5 in main /home/su/repo/lab0-c/qtest.c:780
    #5 0x7f2d76c260b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
    #6 0x5611d6d59b8d in _start (/home/su/repo/lab0-c/qtest+0x8b8d)
                                    
0x5611d6d743c1 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x5611d6d743c0) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /home/su/repo/lab0-c/console.c:307 in do_help_cmd
Shadow bytes around the buggy address:                                                                                                           
  0x0ac2bada6820: f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9
  0x0ac2bada6830: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
  0x0ac2bada6840: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 00 00 00
  0x0ac2bada6850: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
  0x0ac2bada6860: 00 00 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9
=>0x0ac2bada6870: 01 f9 f9 f9 f9 f9 f9 f9[01]f9 f9 f9 f9 f9 f9 f9
  0x0ac2bada6880: 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
  0x0ac2bada6890: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ac2bada68a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ac2bada68b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ac2bada68c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

Check console.c:307 in do_help_cmd(), we can see the problem happens at calling report function. While the error said that it's related to the global variableecho in console.c:59. So we could guess it has something to do with param_ptr.


















//console.c
static bool do_help_cmd(int argc, char *argv[])
{
    cmd_ptr clist = cmd_list;
    report(1, "Commands:", argv[0]);
    while (clist) {
        report(1, "\t%s\t%s", clist->name, clist->documentation);
        clist = clist->next;
    }
    param_ptr plist = param_list;
    report(1, "Options:");
    while (plist) {
        report(1, "\t%s\t%d\t%s", plist->name, *plist->valp,
               plist->documentation);
        plist = plist->next;
    }
    return true;
}

Then we check the definition of param_ptr for plistand the call to add echo command in console.c.










//console.h
typedef struct PELE param_ele, *param_ptr;
struct PELE {
    char *name;
    int *valp;
    char *documentation;
    /* Function that gets called whenever parameter changes */
    setter_function setter;
    param_ptr next;
};


//console.c
add_param("echo", (int *) &echo, "Do/don't echo commands", NULL);

We can see that the echo is declared as a bool type and in add_param() using an int pointer to store it in param_ele that is the cause for the address sanitizer error. To fix this problem we can just change the type from bool to int for the echo variable.


// console.c
static int echo = 0;

Problems

Why the global variable simulation didn't cause the same error as echo, since it it also declared as bool type

Notes: sorting without problem https://hackmd.io/@jasonmatobo/2021q1_homweork_lab0
merge sort without error https://hackmd.io/@gyes00205/2021q1_lab0

2021q1 Homework1 (lab0)

tags: linux2021

Image Not Showing Possible Reasons The image file may be corruptedThe server hosting the image is unavailableThe image path is incorrectThe image format is not supported Learn More → Requirements

Implementation

Struct design for queue_t

q_new()

q_free()

q_insert_head()

q_insert_tail

q_remove_head

q_size

q_reverse

q_sort