# 2021q1 Homework1 (lab0)
contributed by < `RZHuangJeff` >
###### tags: `linux2021`

## Environment

$ uname -a
Linux vostro-5471 5.8.0-44-generic #50-Ubuntu SMP Tue Feb 9 06:29:41 UTC 2021 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version | head -1
gcc (Ubuntu 10.2.0-13ubuntu1) 10.2.0

## Goal of Homework
Impelment following functions in `queue.[ch]`:
- [x] `q_new`: Create a new, empty queue.
- [x] `q_free`: Free all storage used by a queue.
- [x] `q_insert_head`: Attempt to insert a new element at the head of the queue (LIFO discipline).
- [x] `q_insert_tail`: Attempt to insert a new element at the tail of the queue (FIFO discipline).
- [x] `q_remove_head`: Attempt to remove the element at the head of the queue.
- [x] `q_size`: Compute the number of elements in the queue.
- [x] `q_reverse`: Reorder the list so that the queue elements are reversed in order. This function should notallocate or free any list elements.
- [x] `q_sort`: Sort the elements of the given queue in ascending order.

## Development Flow
### queue.h

### queue.c
* **q_new**
* Make sure if `q` is valid before inititalizing its contents.

    queue_t *q_new()
    {
        queue_t *q;
        if (!(q = malloc(sizeof(queue_t))))
            return NULL;

        q->head = NULL;
        q->tail = &(q->head);
        q->size = 0;
        return q;
    }

* **q_free**
* Free all storage used by queue
* Do not thing if `q` is `NULL`
> Run through entire queue with a temporary variable `cur` and free the space pointed by `cur`

    void q_free(queue_t *q)
    {
        if (!q)
            return;

        list_ele_t *cur;
        while (q->head) {
            cur = q->head;
            q->head = cur->next;

            free(cur->value);
            free(cur);
        }

        free(q);
    }

* **q_insert_head**
* Insert an element at head of queue
* Allocate a space explicitly to copy string into it
* Make sure that all pointers are valid

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

        size_t slen = strlen(s) + 1;
        list_ele_t *newh;
        if (!(newh = malloc(sizeof(list_ele_t))))
            return false;

        if (!(newh->value = malloc(slen))) {
            free(newh);
            return false;
        }

        memcpy(newh->value, s, slen);

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

* **q_remove_head**
* Remove an element from head of queue
* Copy the value of removed element into `sp` if `sp` is not `NULL`

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

        list_ele_t *rem = q->head;
        size_t remlen = strlen(rem->value);
        size_t cpylen = remlen < bufsize - 1 ? remlen : bufsize - 1;

        if (sp) {
            memcpy(sp, rem->value, cpylen);
            sp[cpylen] = '\0';
        }

        q->head = rem->next;
        q->size--;
        if (!(q->head))
            q->tail = &(q->head);

        free(rem->value);
        free(rem);

        return true;
    }

* **q_insert_tail**
* Insert an element to tail of queue
* Do nothing while `q` is `NULL`
* Allocate a space explicitly to copy string into it
* Operating in O(1) time
> In order to reach O(1) operation time, `tail` is introduced to `queue_t`, which is type of `list_ele_t**`. The reason why defines `tail` as `list_ele_t**` is to simplify checking of edge condition such as insert tail in the empty queue.

    typedef struct {
        /* Other fields in structure */
        list_ele_t **tail;
    } queue_t;
    
    bool q_insert_tail(queue_t *q, char *s)
    {
        if (!q)
            return false;

        size_t slen = strlen(s) + 1;
        list_ele_t *newt;
        if (!(newt = malloc(sizeof(list_ele_t))))
            return false;

        if (!(newt->value = malloc(slen))) {
            free(newt);
            return false;
        }

        memcpy(newt->value, s, slen);

        newt->next = NULL;
        *(q->tail) = newt;
        q->tail = &(newt->next);
        q->size++;

        return true;
    }

* **q_reverse**
* Reverse the order of elements in the queue
* No effect if `q` is `NULL` or empty or with only one element in it
* No allocations of elements
> `temp_head` reprecents the head of reversed queue, in each loop round, `cur` points to the element would be reverse.

    void q_reverse(queue_t *q)
    {
        if (!q || !(q->head) || !(q->head->next))
            return;

        q->tail = &(q->head->next);

        list_ele_t *tmp_head = NULL, *cur;
        while (q->head) {
            cur = q->head;
            q->head = cur->next;

            cur->next = tmp_head;
            tmp_head = cur;
        }

        q->head = tmp_head;
    }

* **q_size**
* Report the size of given queue
* Return 0 for `NULL` or empty queue
* Operating in O(1) time
> In order to reach O(1) operation time, `size` was introduced to `queue_t`, initialized with zero, and will be updated each time an element is inserted or removed via `q_insert_head`, `q_insert_tail` or `q_remove_head`.

    typedef struct {
        /* Other fields in structure ... */
        
        size_t size;
    } queue_t;
    
    int q_size(queue_t *q)
    {
        return !q ? 0 : q->size;
    }

* **q_sort**
* Sort the elements in the given queue in acensing order
* Capable for passing `NULL` or empty queue as argument
* No Allocations or frees for temporary storage
* Operating in O(nlogn) time
> In order to reach O(nlogn) operation time, merge sort is choosen as the algorithm of implementation.
> There are two functions, `divide` and `merge`, introduced and will cooperate with `q_sort` to fulfill the task.
> Function `divide` aims to cut a queue into two. It first set the size of subqueue(line 15), then run through the list to find the point to cut(for loop around line 19), finally resets all coresponding fields around cut to make divide happend. Notice that there is **no checking for edge conditions** such as `NULL` or the queue with no more than 2 elements in it, since it will only be called by `q_sort`, which has already checked such conditions(line 3).
> Function `merge` expects two queues with their elements are both in acensing order as its arguments. To merge these queues, it will run through each elements in `a`(for loop between line 32 - 41), find the right place for each element in `b`(line 33), and insert them to that place(line 35 - 39). Since that elements in `b` are in acensing order, it should only run through `a` once. Finally, if there are any element in `b` after the for loop, those elements will be attached to the tail of `a`. With the same condition mentioned above, this function **does not provide checking for edge condition**.

    void q_sort(queue_t *q)
    {
        if (!q || !(q->head) || !(q->head->next))
            return;

        queue_t b;
        divide(q, &b);
        q_sort(q);
        q_sort(&b);
        merge(q, &b);
    }

    static void divide(queue_t *a, queue_t *b)
    {
        b->size = a->size / 2;
        b->tail = a->tail;

        list_ele_t *cut = a->head;
        for (size_t i = b->size; i > 1; i--)
            cut = cut->next;

        b->head = cut->next;

        cut->next = NULL;
        a->tail = &(cut->next);
        a->size -= b->size;
    }

    static void merge(queue_t *a, volatile queue_t *b)
    {
        list_ele_t *tmp, **ori_tail = a->tail;
        for (a->tail = &(a->head); *(a->tail) && b->head;
             a->tail = &((*(a->tail))->next)) {
            if (strcmp((*(a->tail))->value, b->head->value) > 0) {
                tmp = b->head;
                b->head = b->head->next;

                tmp->next = *(a->tail);
                *(a->tail) = tmp;
            }
        }

        if (b->head) {
            *(a->tail) = b->head;
            a->tail = b->tail;
        } else
            a->tail = ori_tail;

        a->size += b->size;
    }

## Address Sanitizer Error in `qtest`
### How I Locate the Error
First, I follow the step mentioned in homework description, which make error happend.

$ make SANITIZER=1

$ ./qtest
cmd> help
cmd> help
Commands:
        #        ...            | Display comment
        free                    | Delete queue
        help                    | Show documentation
        ih       str [n]        | Insert string str at head of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
        it       str [n]        | Insert string str at tail of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
        log      file           | Copy output to file
        new                     | Create new queue
        option   [name val]     | Display or set options
        quit                    | Exit program
        reverse                 | Reverse queue
        rh       [str]          | Remove from head of queue.  Optionally compare to expected value str
        rhq                     | Remove from head of queue without reporting value.
        show                    | Show queue contents
        size     [n]            | Compute queue size n times (default: n == 1)
        sort                    | Sort queue in ascending order
        source   file           | Read commands from source file
        time     cmd arg ...    | Time command execution
Options:
=================================================================
==60472==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55d6527d07a0 at pc 0x55d6527c042f bp 0x7ffcb7b353a0 sp 0x7ffcb7b35390
READ of size 4 at 0x55d6527d07a0 thread T0
    #0 0x55d6527c042e in do_help_cmd /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/console.c:306
    #1 0x55d6527c0542 in interpret_cmda /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/console.c:220
    #2 0x55d6527c0f7c in interpret_cmd /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/console.c:243
    #3 0x55d6527c1e4c in cmd_select /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/console.c:607
    #4 0x55d6527c1ffc in run_console /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/console.c:628
    #5 0x55d6527bf066 in main /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/qtest.c:772
    #6 0x7f35e48d2cb1 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x28cb1)
    #7 0x55d6527bc88d in _start (/media/forward1105/DATA_1/CCodes/linux2021/lab0-c/qtest+0x788d)

0x55d6527d07a1 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:58:13' (0x55d6527d07a0) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/console.c:306 in do_help_cmd
Shadow bytes around the buggy address:
  0x0abb4a4f20a0: 00 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
  0x0abb4a4f20b0: 04 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9
  0x0abb4a4f20c0: 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9
  0x0abb4a4f20d0: 00 00 00 00 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00
  0x0abb4a4f20e0: 00 00 00 00 00 00 f9 f9 f9 f9 f9 f9 01 f9 f9 f9
=>0x0abb4a4f20f0: f9 f9 f9 f9[01]f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9
  0x0abb4a4f2100: f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00
  0x0abb4a4f2110: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0abb4a4f2120: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0abb4a4f2130: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0abb4a4f2140: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==60472==ABORTING

At this moment, I notice several lines of this error message, which helps me to locate where exactly error happends: First, at line 24, after showing `Options:` there should be several lines of options. Second, from the stack trace shown by Address Sanitizer(around line 28 - 35), it shows that the error happends at line 306 in file console.c.

/* Line 306 of console.c */
report(1, "\t%s\t%d\t%s", plist->name, *plist->valp, plist->documentation);

### What Happend
Since that the stack trace of Address Sanitizer says that the error happened in `do_help_cmd`, not in `report`, furthermore, at line 27 of error message shown above, it says that a `READ` of size 4 at `0x55d6527d07a0` causes the error.
At this moment, I can roughly determine that `*plist->valp` causes the error, since that only field `valp`, which has type of `int*`, can cause a read of size 4 while dereferencing it and passing it as argument.
Since `parm_list` was initialized in function `init_cmd`, I turn my attention to this function. According to `add_param` in console.c, the parameters in `param_list` are ranked with dictionary order, we can find that parameter `echo` added at line 106 in console.c causes that error.
At line 58, `echo` is defined as type `bool` rather than `int`. Dereferencing it as `int*` may cause the error. To confirm my hypothesis, I comment out line 106, which add option `echo` into option list, then following happends:

## Lines of outputs
==61145==ERROR: AddressSanitizer: global-buffer-overflow on address 0x56434c3bb940 at pc 0x56434c3a942f bp 0x7fff1611ca50 sp 0x7fff1611ca40
READ of size 4 at 0x56434c3bb940 thread T0
    #0 0x56434c3a942e in do_help_cmd /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/console.c:306
    #1 0x56434c3a9542 in interpret_cmda /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/console.c:220
    #2 0x56434c3a9f7c in interpret_cmd /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/console.c:243
    #3 0x56434c3aae2d in cmd_select /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/console.c:607
    #4 0x56434c3aafdd in run_console /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/console.c:628
    #5 0x56434c3a8066 in main /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/qtest.c:772
    #6 0x7f1a37a50cb1 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x28cb1)
    #7 0x56434c3a588d in _start (/media/forward1105/DATA_1/CCodes/linux2021/lab0-c/qtest+0x788d)

0x56434c3bb941 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:20:6' (0x56434c3bb940) of size 1
  'simulation' is ascii string ''
SUMMARY: AddressSanitizer: global-buffer-overflow /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/console.c:306 in do_help_cmd

## Following lines are omited

The same error happended on parameter `simulation`, which also defined as type `bool`. And both `echo` and `simulation` are casted to `int*` while being added into `param_list`.
Since here, I guess that the difference between the size of `bool` and `int` causes the error. To ensure that, I compile and run the following code(with compile flags `-fsanitize=address -fno-omit-frame-pointer -fno-common`).

#include <stdio.h>
#include <stdbool.h>

static bool a = false;

int main()
{
    printf("sizeof bool: %lu\nsizeof int: %lu\n", sizeof(bool), sizeof(int));

    int *aptr = (int*)&a;
    int result = *aptr;

    return 0;
}

The program reports that the size of `bool` and `int` are 1 and 4, respectively. And it also causes the same error while tries to access `a` via `aptr`(reported at line 6 - 7 in following error messages):

$ ./test
sizeof bool: 1
sizeof int: 4
=================================================================
==61999==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55e53027e0e0 at pc 0x55e53027b252 bp 0x7fffe53b2d90 sp 0x7fffe53b2d80
READ of size 4 at 0x55e53027e0e0 thread T0
    #0 0x55e53027b251 in main /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/test.c:11
    #1 0x7f1b9b053cb1 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x28cb1)
    #2 0x55e53027b12d in _start (/media/forward1105/DATA_1/CCodes/linux2021/lab0-c/test+0x112d)

0x55e53027e0e1 is located 0 bytes to the right of global variable 'a' defined in 'test.c:4:13' (0x55e53027e0e0) of size 1

## Following lines are omited

With such evidence, I believe that dereferencing a pointer to `int`, which actually points to variable with type `bool`, causes the error.

### Solution
The first solution came up my mind is to redefine `echo` and `simulation` as type `int`. I think this solution works fine to `echo`, since it is a static variable, which can only be accessed inside console.c, but not for `simulation`, which is defined export in console.h and would be accessed in qtest.c, redefine it will cause a chain effect to recheck files that access it.
Cause the reson mentioned above, I'm still figuring out if there is another solution.