# 2020q1 Homework1 (lab0)
contributed by < `eecheng87` >
###### tags: `linux2020`
## Patch `queue.c`

### q_new

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

This function is straightforward. What it ought to be changed is allocating a memory and check whether the return value is `NULL`. If not, remember to initialize field in `queue_t`. On the other hand, if return value is `NULL` wihch means allocated fail. The reason can be found through the function `void *test_malloc(size_t size)` in `harness.c`. Return type of this function is `void*` which can be cast to any type. Inside the function, you can find the reason is that when it is not in allocate mode or fail to allocate memory. Both of them will return `NULL`.

### q_free

if (!q)
    return;
list_ele_t *node = q->head;
while (node != NULL) {
    list_ele_t *tmp = node;
    node = node->next;
    free(tmp->value);
    free(tmp);
    q->size--;
}
free(q);

To implement robust free function, we need to free all memory you acquired before. There are three kind of memory you need to free. They are `queue_t`, `list_ele_t` linked after `queue_t` and `string` in each `list_ele_t`. The method is straight forward, traverse linked list and free all of them.

### q_insert_head

if (!q) {
    return false;
}
list_ele_t *newh;

newh = malloc(sizeof(list_ele_t));
if (!newh) {
    return false;
}

newh->value = malloc(strlen(s) + 1);
if (!newh->value) {
    free(newh);
    return false;
}
q->size++;
strncpy(newh->value, s, strlen(s) + 1);
if (!q->head) {
    /* Queue haven't contain any element */
    newh->next = NULL;
    q->head = q->tail = newh;
} else {
    /* Queue already have element */
    newh->next = q->head;
    q->head = newh;
}
return true;

Remember check whether return value is `NULL` from memory allocated for `string`. After that, the only thing left is insert node. There are two condition, list in `queue_t` is empty or not.

### q_insert_tail

if (!q) {
    return false;
}
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if (!newh) {
    return false;
}

newh->value = malloc(strlen(s) + 1);
if (!newh->value) {
    free(newh);
    return false;
}
q->size++;
strncpy(newh->value, s, strlen(s) + 1);
q->head = q->tail ? q->head : newh;
newh->next = NULL;
if (q->tail)
    q->tail->next = newh;
q->tail = newh;
return true;

Basically, the details need to be aware of are almost same as previous function. But, this assignment require the time complexity of `q_insert_tail` is $O(1)$ .The trick need to do is add addtional field `list_ele_t * tail` in `queue_t`. Record who is tail all the time. If so, insert node to tail is simply one line operation which cost $O(1)$ .

### q_remove_head

if (!q || !q->head)
        return false;
        
list_ele_t *node = q->head;
q->head = q->head->next;

if (bufsize != 0) {
    if (strlen(node->value) > bufsize) {
        strncpy(sp, node->value, bufsize);
        sp[bufsize - 1] = '\0';
    } else {
        strncpy(sp, node->value, 
        strlen(node->value) + 1);
    }
}
free(node->value);
free(node);
q->size--;
return true;

Hint gave by comment, we need to copy the removed string to `*sp`. If length of removed string is greater than `bufsize`, we need to assign last charater to `\0`. Last, remember to free memory of node and string in node.
### q_size

int q_size(queue_t *q)
{
    if (!q || !q->head)
        return 0;
    return q->size;
}

Because we have additional infomation `size` which is recorded in `queue`, it is easy to get size. The only thing we need to do is return this additional infomation.

### q_reverse

if (!q || !q->head || q->size == 1)
    return;
list_ele_t *reverse_list = q->head;
list_ele_t *list_to_do = q->head->next;

q->tail = reverse_list;
reverse_list->next = NULL;

while (list_to_do) {
    list_ele_t *tmp = list_to_do;
    list_to_do = list_to_do->next;
    tmp->next = reverse_list;
    reverse_list = tmp;
}
q->head = reverse_list;

Reference this [link](https://www.geeksforgeeks.org/reverse-a-linked-list/). `reverse_list` always point to head of reverse list. `list_to_do` point to head of un-reverse list.

### q_sort

if (!q || !q->head || q->size == 1)
    return;
int block_size = 1, n = q->size, i, alen, blen;
list_ele_t virtual_head;
list_ele_t *last = NULL, *it = NULL, *l1 = NULL, *l2 = NULL, *tmp = NULL;
list_ele_t *l1head = NULL, *l1tail = NULL, *l2head = NULL, *l2tail = NULL;
virtual_head.next = q->head;
while (block_size < n) {
    int iter = 0;
    last = &virtual_head;
    it = virtual_head.next;
    while (iter < n) {
        // decide each iterate time's block size a and b
        alen = min(n - iter, block_size);
        // avoid odd block
        blen = min(n - iter - alen, block_size);
       

        l1 = it;
        l1head = l1;
        // if left block is odd, just skip
        if(alen == blen && alen > 1){
            //printf("hi");
            list_ele_t *slow = l1head;
            for (i = 0; i < alen - 1; ++i){
                slow = slow->next;
                it = it->next->next;
            }
            it = it->next;
            l1tail = slow;
            l2 = l2head = slow->next;
            slow->next = NULL;
            l2tail = it;
            tmp = it->next;
            it->next = NULL;
            it = tmp;
        } else if (blen != 0) {
            // seperate one list into l1 and l2
            for (i = 0; i < alen - 1; ++i)
                it = it->next;
            l1tail = it;
            l2 = l2head = it->next;
            it->next = NULL;
            it = l2head;
            for (i = 0; i < blen - 1; ++i)
                it = it->next;
            l2tail = it;
            tmp = it->next;
            it->next = NULL;
            it = tmp;
        }else{
            l2 = l2head = l2tail = NULL;
            l1tail = l1head;
            while (l1tail->next)
            {
                l1tail = l1tail->next;
            }
        }

        if (l1head && l2tail && l1tail && l2head &&
            strcmp(l1head->value, l1tail->value) == 0
            && strcmp(l1head->value,l2head->value) == 0
            && strcmp(l1head->value,l2tail->value) == 0){
            //printf("%d\n",iter);
            iter += alen + blen;
            last->next = l1head;
            l1tail->next = l2head;
            last = l2tail;
            l2tail->next = NULL;
            q->tail = l2tail;
        } else {
            while (l1 && l2) {
                if (strcmp(l1->value, l2->value) <= 0) {
                    // if l2 doesn't contain any node, just append l1 to
                    // merge list or if value of l1 is smaller
                    last->next = l1;
                    last = last->next;
                    l1 = l1->next;
                } else {
                    // if l1 doesn't contain any node, just append l2 to
                    // merge list or if value of l2 is smaller
                    last->next = l2;
                    last = last->next;
                    l2 = l2->next;
                }
            }
            if(l1){
                //printf("l1: %d\n",alen);
                last->next = l1;
                last = l1tail;
            }
            if(l2){
                //printf("l2: %d\n",blen);
                last->next = l2;
                last = l2tail;
            }
            l1 = l2 = NULL;


            last->next = NULL;
            //q->tail = last;
            iter += alen + blen;
        }
    }
    block_size <<= 1;
}

q->head = virtual_head.next;
list_ele_t *nd = q->head;
while (nd->next) {
    nd = nd->next;
}
q->tail = nd;

Good algorithm need to consider time complexity and space complexity. For first, we need to find $O(nlogn)$ sorting algorithm because comment in `trace-16.cmd` mentioned. Merge sort is $O(nlogn)$ algorithm. Second, how about space complexity? Most of merge sort implementation is based on recursive way. This is straight forward but cost lot of resources. What worse, it will cause stack overflow. As a result, I decide to use iterative method to implement, its space complexity is real $O(1)$.

But executed time of my iterative method is longer than time limit in 2 million nodes case. I have no idea why my pure iterative method will slower than classmate [SymbolWu's](https://hackmd.io/@SymbolWu/lab0-c#q_sort) divide and conquer version ( Both of our sorting flow is very similar ). His `sort` contain recursive method, it will call itself several times. I guess stack operation for recursive will degrade speed. In reality, my assumption is totally wrong. My iterative method cost 0.9s to complete 2 million nodes sorting slower 1.5 times than SymbolWu's.

I found list of `trace-15.cmd` contain lot of repeative string, so I tried to optimize it. I check whether both sub-lists' string are all the same. If so, we don't need to do `merge` step, just append a sub-list to another.

strcmp(l1head->value, l1tail->value) == 0
&& strcmp(l1head->value,l2head->value) == 0
&& strcmp(l1head->value,l2tail->value) == 0)

Although add this kind of optimization, my code still slower than SymbolWu's.

##

## Read `Dude, is my code constant time?` and explain how `qtest` simulate work

### Paper

#### Timing attack
Ideal algorithm checking correctness of password is $O(1)$. If not in $O(1)$, it will raise security issue. Hacker can guess your password depends on how long this alorithm checks your password. As a result, constant time algorithm is important, but how we measure it?

#### TIMING LEAKAGE DETECTION
In this paper, dudect: a tool to detect whether a piece of code runs in constant-time or not on a given platform. There are three steps to judge if a algorithm is $O(1)$

First, **measure execution time**. We repeatedly measure the execution time of the target function ( e.g. `insert_tail`) for inputs belonging to two different input data classes. First class input data is fixed to a constant value, and the second class input data is chosen at random for each measurement.

Second, **apply post-processing**. process like removing outlier and higher-order preprocessing.

Last, **apply statistical test**. Choose t-test and implement in [Welch’s t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test) model. t-value got from theorem can determine answer to question "the two timing distributions are equal?"

### Explain how simulate work

At first, I find property `simulate` in test bench 17, which is aiming at scoring the time complexity of `insert_tail()` and `size()`.

Then, we can see `do_insert_tail` in `qtest.c`. This function contain two mode. If variable `simulate` is set, program will start simulate.

if (simulation) {
        if (argc != 1) {
            report(1, "%s does not need arguments in simulation mode", argv[0]);
            return false;
        }
        bool ok = is_insert_tail_const();
        if (!ok) {
            report(1, "ERROR: Probably not constant time");
            return false;
        }
        report(1, "Probably constant time");
        return ok;
}

In this block, we can figure out the result of simulate depends on variable `ok`. What's more, `ok` depends on the return value of `is_insert_tail_const()`. So we need to take a look at this function.

We find `is_insert_tail_const()` under folder `dudect`. Again, the return value of function depends on variable `result` which depends on `doit()`. As a result, we need to dive into `doit()`.

prepare_inputs(input_data, classes);

measure(before_ticks, after_ticks,
input_data, mode);

differentiate(exec_times,
before_ticks, after_ticks);

update_statistics(exec_times, classes);

bool ret = report();

Above is part in `doit()`, we need to do these four function sequentially then get the result `ret` which indicate whether complexity is constant time.

* `prepare_inputs()` generate lots of random string.
* `measure()` record time when operation ( insert to tail ) start and end.

    before_ticks[i] = cpucycles();
    dut_insert_tail(s, 1);
    after_ticks[i] = cpucycles();

* `differentiate()` get time interval in operation
* `update_statistics()` drop negative result which is not reasonable. e.g. cpu time overflow.
* `report()` determine whether the operation is in constant time. This function is more complex, so I will explain detailly.
Before calling `report()`, we already collect lot of time interval. We can use these time interval, sample, to calculate `t` value base on `Welch's t-test `. Following is formula for `t` value

$t = \dfrac{\overline{X}_{1} + \overline{X}_{2}}{\sqrt{\dfrac{s_{1}^{2} }{N_{1}}+\dfrac{s_{2}^{2} }{N_{2}}}}$

Detail implementation can be found in function `t_compute()` under `ttest.c`.
Finally, the only thing left is to check whether `t` value is larger than threshold. In this experiment, they choose `t_threshold_bananas` and `t_threshold_moderate`, which is 500 and 10 respectively.
Through concept mentioned in the pape, we discern if the two distributions are different by making sure `t` value is below threshold. (We expected all of t values is between 0 and threshold which implies they are similar). By the way, threshold is 4.5 in paper instead of 10 in implementaion.


<br>

After talking a lot, so why this program can judge if opreation can be done in $O(1)$ ?
**Conclusion**:
$O(1)$ also called constant time, which means it isn't affected by other condition such as length of list. If so, we expect when we execute multiple times same operation with differant list length and string size will get similar distribution(not time).
Alright, we get several distributions but how to tell they are similar or not? `t-test` is what exactly the theorem for testing this kind of problem. Aftering calculating `t` value, we can tell whether they're similar, or in constant time.

## Explain how to use system call `select` and analyze the implementation of `console.c`

### select
>select() **allow a program to monitor multiple file
descriptors**, waiting until one or more of the file descriptors become
"ready" for some class of I/O operation (e.g., input possible).

`select` is **non-blocking** function, it has time limit as a argument. It will return before time limit even though there isn't any file can read.

Some basic turtorial about `select` is [here](http://beej-zhtw.netdpi.net/07-advanced-technology/7-2-select)

### console.c

Work flow of `console.c` is illustrated clearly in homework description.

> main → run_console → cmd_select → interpret_cmd → parse_args
>

Thanks for this hint, we can research `console.c` faster.

* main: In console.c line 770, call `run_console(infile_name)` to forward to next step.
* run_console: Initiate basic information about input file such as file descriptor. Then, call `cmd_select`.
* cmd_select: Besides manage `readset`, `cmd_select` also checks whether command input either present in internal buffer or readable from command input( through `read_ready()`).After `select`, if target `fd` is in `read_set`, it means available ( but maybe invalid, `interpret` will check later ).
* system call `select`: I have used this system call for socket programing. The main reason to use this system call is that `select` have **non-blocking** property. Due to this assignment, I found [another usage](https://www.gnu.org/software/libc/manual/html_node/Waiting-for-I_002fO.html) for `select`. This usage seems like have closer relation to `console.c`.
* interpret_cmd: As the name implies, this function need to interpret input. For example, if input is `ih RAND 3`, then this function take it (`ih RAND 3`) as parameter `char *cmdline`. Pass it into `parse_args(char *line, int *argcp)`, you will get the string array seperated by space as return value. Last, pass string array `argv` into `interpret_cmda`.
* interpret_cmda: The purpose of this function is check whether command is valid and call the operation based on what command you type. Implementation can be found around line 217. This block traverse `cmd_list` which contain all of enrolled command. If there is a key word as same as the input (`argv[0] which is already parsed`), it means input command is valid and `next_cmd` must have value.

        if (next_cmd) {
        
        // if command is valid, then it will 
        // call operation through function pointer 
        // which is already bound by registering command
        // in the begining
            ok = next_cmd->operation(argc, argv);
            if (!ok)
                record_error();
        }

If not, `next_cmd` should be `NULL` and will do some remedies. e.g. report it is "Unknown command".

## Massif 視覺化工具
### First attempt

Command

* How to generate output file which record heap info

$ valgrind --tool=massif ./program

* How to draw graph through above output file

$ ms_print massif.out.6865

> PS: in my case, need to do it under `sudo` mode
>

Tips

* make graph more normal --> chang time unit

           KB
    19.63^                                                                       #
         |                                                                       #
         |                                                                       #
         |                                                                       #
         |                                                                       #
         |                                                                       #
         |                                                                       #
         |                                                                       #
         |                                                                       #
         |                                                                       #
         |                                                                       #
         |                                                                       #
         |                                                                       #
         |                                                                       #
         |                                                                       #
         |                                                                       #
         |                                                                       #
         |                                                                      :#
         |                                                                      :#
         |                                                                      :#
       0 +----------------------------------------------------------------------->ki     0                                                                   113.4
    
    Above graph is werid because of its vertical line
    Let's change time unit to  `--time-unit=B`
    
    19.63^                                               ###                      
     |                                               #                        
     |                                               #  ::                    
     |                                               #  : :::                 
     |                                      :::::::::#  : :  ::               
     |                                      :        #  : :  : ::             
     |                                      :        #  : :  : : :::          
     |                                      :        #  : :  : : :  ::        
     |                            :::::::::::        #  : :  : : :  : :::     
     |                            :         :        #  : :  : : :  : :  ::   
     |                        :::::         :        #  : :  : : :  : :  : :: 
     |                     @@@:   :         :        #  : :  : : :  : :  : : @
     |                   ::@  :   :         :        #  : :  : : :  : :  : : @
     |                :::: @  :   :         :        #  : :  : : :  : :  : : @
     |              :::  : @  :   :         :        #  : :  : : :  : :  : : @
     |            ::: :  : @  :   :         :        #  : :  : : :  : :  : : @
     |         :::: : :  : @  :   :         :        #  : :  : : :  : :  : : @
     |       :::  : : :  : @  :   :         :        #  : :  : : :  : :  : : @
     |    :::: :  : : :  : @  :   :         :        #  : :  : : :  : :  : : @
     |  :::  : :  : : :  : @  :   :         :        #  : :  : : :  : :  : : @
   0 +----------------------------------------------------------------------->KB     0                                                                   29.48

Explaination:
* By default, Massif uses "instructions executed" as the unit of time.
* `#` is peak, `:` is normal snapshot, `@` is detail snapshot.

Document:
>--time-unit=<i|ms|B> [default: i]
The time unit used for the profiling. There are three possibilities: instructions executed (i), which is good for most cases; real (wallclock) time (ms, i.e. milliseconds), which is sometimes useful; and bytes allocated/deallocated on the heap and/or stack (B), which is useful for very short-run programs, and for testing purposes, because it is the most reproducible across different machines.

### Visualize it

We need 3rd app to help us to transfer `massif.out` into beautiful picture. Type command in this [link](https://askubuntu.com/questions/522263/installing-massif-visualizer-on-ubuntu-14-04) and then you can get app.


:::success
I don't know why the text in legend can't display properly ( empty square ), is this bug? or I need to adjust something?

Following is how I get this app

$ sudo add-apt-repository ppa:kubuntu-ppa/backports
$ sudo apt-get update
$ sudo apt-get install massif-visualizer

$ massif-visualizer --version
massif-visualizer 0.7

:::