# 2019q1 Homework1 (lab0)
contributed by < `Superdanby` >

## Environment Setup

- Fedora 29
- gcc (GCC) 8.2.1 20181215 (Red Hat 8.2.1-6)

1. `sudo dnf install cppcheck colordiff`

## Function Analysis

### `queue_t *q_new()`

#### [Should one type cast malloc?]()

The first problem I encountered is whether I should type cast the memory returned from malloc. If I remembered right, there would be a warning/error if one didn't do it. Thus, I searched and found that it is suggested not doing so in C.

Note that [C and C++ have different behaviors on this issue](https://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc#answer-605858).

### `void q_free(queue_t *q)`

Needs to iterate through the queue and release the memory of value entry of each element.

### `bool q_insert_head(queue_t *q, char *s)`

Should also link tail if tail is empty.

### `bool q_insert_tail(queue_t *q, char *s)`, O(1)

Should also link head if head is empty.

### `bool q_remove_head(queue_t *q, char *sp, size_t bufsize)`

The first things I was thinking is that if I allocate `sp` a new block of memory with `malloc`, the caller will not receive the returned string. And then, I saw bufsize, which is when I realized the caller will `malloc` on its side.

### `int q_size(queue_t *q)`, O(1)

Add a new entry in queue_t, and this could be done in O(1).

### `void q_reverse(queue_t *q)`

Should not allocate or release memory.

Needs to traverse the whole queue and reverse each element one by one.

## Version History

### Version 1

- Score: 56/100
- Got lots of : `ERROR: Failed to store removed value`

After checking my code, I found that the `if` statement I used to check whether to copy `head->value` to `sp` in `bool q_remove_head(queue_t *q, char *sp, size_t bufsize)` is wrong.

Wrong version:

// Check sp and bufsize availability
if (!sp && (temp->value) && bufsize)

Corrected version:

// Check sp and bufsize availability
if (sp && (temp->value) && bufsize)

The reason why I code it wrong is because I wanted to write `sp != NULL`, but I gone lazy and make it `!sp` which is really stupid. I should be more cautious next time.

### Version 2

- Score: 93/100
- Test remove_head with NULL argument results in:
`ERROR: Freed queue, but 1 blocks are still allocated`

Wrong version:

if (sp && (temp->value) && bufsize) {
    strncpy(sp, temp->value, bufsize - 1);
    sp[bufsize - 1] = '\0';
    // Release value memory
    free(temp->value);
    temp->value = NULL;
}

Corrected version:

if (temp->value) {
    if (sp && bufsize) {
        strncpy(sp, temp->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    // Release value memory
    free(temp->value);
    temp->value = NULL;
}

`temp->value` needs to be cleared even if it couldn't be copied to `sp`.

### Version 3
- Score: 100/100

## Automated Grading System

Looking at `Makefile`, we can see that the `make test` executes `scripts/driver.py`.

### `driver.py`

#### `run` method

Increments the total score by the corresponding value in `maxScores` if no error detected after executing `runTrace`; the total score will not be incremented otherwise.

#### `runTrace` method

Executes `qtest` with different arguements composed in `clist`

## `qtest`

- Checks memory leaks with `allocation_check()`.
- Checks errors with `error_check()`.

### `bool error_check()`

Checks if an error had occured and clears `error_occurred`.

### `size_t allocation_check()`

Returns the number of blocks of memory still allocated. The number is actually stored in `allocated_count` and is incremented and decremented in `test_malloc` and `test_free` respectively. Thus, we can infer from this fact that all operations for memory allocation / release will be tested with these 2 functions.
Searching all files with `find . -exec grep 'test_free\|test_malloc' {} + 2> /dev/null`, we get the following result:

./harness.c:void *test_malloc(size_t size)
./harness.c:void test_free(void *p)
./harness.c:    void *new = test_malloc(len);
./harness.h:void *test_malloc(size_t size);
./harness.h:void test_free(void *p);
./harness.h:#define malloc test_malloc
./harness.h:#define free test_free
Binary file ./queue.o matches
Binary file ./qtest matches

From the result, we can know that all files which include `harness.h` have there `free()` and `malloc()` from standard library replaced with those of `harness.h`.
Next, using `find . -exec grep '#include "harness.h"' {} + 2> /dev/null`, we can see the following:

./harness.c:#include "harness.h"
./qtest.c:#include "harness.h"
./queue.c:#include "harness.h"

The file `queue.c` we were modifying is also using "harness.h"

### `char *test_strdup(const char *s)`

This function utilizes `test_malloc` to allocate memory, copies the contents of `s` to the newly allocated memory, and returns it. `#define strdup test_strdup` is also written in line 61 in `"harness.h"`. It seems that we should use this function in `q_remove_head` to return the string being deleted.

**But**, the operation returns a **new** address other than the given one recorded in `sp` of `bool q_remove_head(queue_t *q, char *sp, size_t bufsize)`. Thus, the caller of `bool q_remove_head` would never get `q->head->value` in `sp` if the implementation is `sp = strdup(q->head->value)`

### `void sigsegvhandler(int sig)`

Triggers when there is a segementation fault with `SIGSEGV`.

### `void sigalrmhandler(int sig)`

Triggers when time limit exceeded with `SIGALRM`.

### `bool exception_setup(bool limit_time)`

Saves states and sets up `alarm`.

if (sigsetjmp(env, 1)) {
    /* Got here from longjmp */
    jmp_ready = false;
    if (time_limited) {
        alarm(0);
        time_limited = false;
    }
    if (error_message) {
        report_event(MSG_ERROR, error_message);
    }
    error_message = "";
    return false;
} else {
    /* Got here from initial call */
    jmp_ready = true;
    if (limit_time) {
        alarm(time_limit);
        time_limited = true;
    }
    return true;
}

State is saved in line 1. It can later be recovered with `siglongjmp` in `void trigger_exception(char *msg)` if any exception is triggered.

From `man alarm`:
> `alarm()` arranges for a SIGALRM signal to be delivered to the calling process in `seconds` seconds.
> If `seconds` is zero, any pending alarm is canceled.
> In any event any previously set `alarm()` is canceled.

In line 17, time limit is set with `limit_time`, which is a `bool` type. So, the time limit is 1 second if time limit is set.

This function results in the behavior of `ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient` when `--valgrind` option is set, meaning `valgrind` affects the execution time of each operation:

$ ./scripts/driver.py --valgrind 2> /dev/null | grep "TOTAL"
---	TOTAL		79/100

$ ./scripts/driver.py 2> /dev/null | grep "TOTAL"
---	TOTAL		100/100