# 2019q3 Homework2 (lab0)
contributed by < `kksweet8845` >

## C Programming Lab: Assessing Your C Programming Skills
This homework is a assessment to check whether the students have the fundemental skills of C programming.
Some of the skills tested are:
- Explicit memory management, as required in C.
- Creating and manipulating pointer-based data structures.
- Working with strings.
- Enhancing the performance of key operations by storing redundant information in data structures.
- Implementing robust code that operates correctly with invalid arguments, including NULL pointers.

Implementing a queue, supporting both queueing disciplines.
- LIFO
- FIFO

### My `list_ele_t` & `queue_t` data structure
Most of part is similiar to the official one.

typedef struct ELE {
    /* Pointer to array holding string.
       This array needs to be explicitly allocated and freed */
    char *value;
    struct ELE *next;
} list_ele_t;

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

And, I finally found that the `t` at the end of variables meaning `type`.

### Implementation

#### `queue_t *q_new()`

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (q == NULL)
        return NULL;
    else {
        q->head = NULL;
        q->tail = NULL;
        q->len = 0;
    }
    return q;
}

At the first, it is the basic function needed to be create. Create a new queue with `NULL` head, `NULL` tail and zero length.
If the overloading malloc occurred problem, such like return `NULL`, we also need to return `NULL` immediately.

#### `list_ele_t *list_new(char *s)`

list_ele_t *list_new(char *s)
{
    list_ele_t *l = malloc(sizeof(list_ele_t));
    if (l == NULL)
        return NULL;
    char *ts = malloc((strlen(s) + 1) * (sizeof(char)));
    if (ts == NULL) {
        free(l);
        return NULL;
    }
    strcpy(ts, s);
    l->value = ts;
    l->next = NULL;
    return l;
}

It is an original function make by myself in order to create a new list with some repreated operation. By the way, the length of string is needed to be add a additional `1` because of the `\0` terminator.

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

void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    if (q == NULL)
        return;
    list_ele_t *cur, *temp;
    for (cur = q->head; cur != NULL; cur = temp) {
        temp = cur->next;
        if (cur->value != NULL)
            free(cur->value);
        if (cur != NULL)
            free(cur);
    }
    free(q);
}

The function to free all the blocks with freeing string.

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

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    if (q == NULL)
        return false;
    /* Handling allocate space for the string and copy it */
    newh = list_new(s);
    if (newh == NULL)
        return false;
    newh->next = q->head;
    q->head = newh;
    q->len += 1;
    if (q->len == 1)
        q->tail = newh;
    return true;
}

Implement the insert_head() operation.

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

bool q_insert_tail(queue_t *q, char *s)
{
    /* Remember: It should operate in O(1) time */
    list_ele_t *newh;
    /*  Rturn false if q is NULL*/
    if (q == NULL)
        return false;
    /*  Create a new list */
    newh = list_new(s);
    /* Return false if the list is NULL */
    if (newh == NULL)
        return false;
    q->tail->next = newh;
    q->tail = newh;
    q->len += 1;
    if (q->len == 1)
        q->head = newh;
    return true;
}

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

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if (q == NULL || (q->head == NULL && q->tail == NULL) || q->len == 0 ||
        sp == NULL)
        return false;
    list_ele_t *cur = q->head;
    q->head = q->head->next;
    q->len -= 1;
    /* Tips: fill all the char with `\0` teminator */
    memset(sp, '\0', (bufsize) * sizeof(char));
    /* copy the first bufsize-1, then sp will already have the \0 teminator */
    strncpy(sp, cur->value, bufsize - 1);
    if (cur->value != NULL)
        free(cur->value);
    if (cur != NULL)
        free(cur);
    return true;
}

Remove the head list of queue. Check the
1. q is `NULL`
2. q is empty
3. sp is `NULL`

#### `int q_size(queue_t *q)`

int q_size(queue_t *q)
{
    /* Remember: It should operate in O(1) time */
    if (q == NULL)
        return 0;
    return q->len;
}

<a id="reverse"></a>
Support that if `q` is `NULL`.

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

void q_reverse(queue_t *q)
{
    if (q == NULL)
        return;
    list_ele_t *cur, *pre, *tmp_head = NULL;
    q->tail = q->head;
    for (cur = q->head; cur != NULL; cur = q->head) {
        pre = tmp_head;
        tmp_head = cur;
        q->head = cur->next;
        cur->next = pre;
    }
    q->head = tmp_head;
}

The initail situation of queue and fack header.
Using two pointer `cur` and `pre` to point each head of two queues.
Let the `q->head` point to the `cur->next`, then `fh` point to `cur`.
Repeat the opeation above again.

Reverse the queue with the technique, the insertion of link-list. This method will automatically reverser the list.

## The principle of grading system
The architecture of this project.

The main flow of qtest

st=>start: Start
get_opt=>operation: Get options
queue_init=>operation: Initialize a Queue
init_cmd=>operation: Initialize Commands
console_init=>operation: Initialize a console
set_verbose=>operation: Set the level of verbosibility
set_logf=>operation: Set the logfile if given
add_quit_helper=>operation: Add the quit helper
run_console=>operation: Activate a console
finish_cmd=>operation: Finish the command(quit command)
end=>end: return o or 1

st->get_opt->queue_init->init_cmd->console_init->set_verbose


set_verbose->set_logf->add_quit_helper->run_console->finish_cmd->end

- `qtest.c`
- Handle the main flow of program and initialize the queue, console and commands modules. There is a function named `run_console`,which will activate the console and pass authorization to the `console.c` then wait for it to finishe the console mode when the user types `quit` or `exit` command.
- Also defining the commands in this file then using a function named `add_cmd` defined in `console.c` which qtest will pass the pointer of function into it. Thus, the console module can using these cmd indirectly with a struct called `CELE`.

- `harness.c`
- Handle the part of testing operation and overloading the library version of `malloc` and `free` with ones that allow checking for common allocation errors.
- It uses doubly link list with a struct called `BELE`.

        typedef struct BELE {
            struct BELE *next;
            struct BELE *prev;
            size_t payload_size;
            size_t magic_header;
            unsigned char payload[0];
        } block_ele_t;

- `console.c`
- Implement buffered I/O using variant of RIO package from CS:APP. Must create stack of buffers to handle I/O with nested source commands. (from the Jim Huang's comment)
- `report.c`
- Record and report the event when there is any information when excuting `console module`. It not only holds the definition of commands but also report error when error occurred.
- The `report` function is also been used by `qtest.c`.

- `queue.c`
- The program implements the queue with both LIFO and FIFO.

### Automatic grading `driver.py`
The driver.py store the fifteen file names of the trace-file in a Class called `Tracer`. This class will automaticly test the operations in each trace file and record the operation is successful or not. Then, it will output the final score to the screen.

## The techniques in qtest

### The mechanism of switching authorization

queue_init();
init_cmd(); // Initialize the command interpreter
console_init(); // Initialize the commands
set_verblevel(level);
if (level > 1) {
    set_echo(true);
}
if (logfile_name)
    set_logfile(logfile_name);
add_quit_helper(queue_quit);
bool ok = true;
ok = ok && run_console(infile_name); // Passing authorization to console
ok = ok && finish_cmd();
return ok ? 0 : 1;

This is a clever tip for programmers when developing a project. It is encouraged that separating the module with clear definition.
- Like the `console_init()` and `init_cmd()`, which will initialize the console with `add_cmd()` to add the operation of commands as a stack consisting of `CELE` implementing by link list,which can store the name of commands the operation of commands, the description of commands.

`qtest.c` don't have to care about the issue occurred executing console. Just like the OS passes the authorization to usr program. It just needs to handle the utility of CPU and other management.

### The signal handler
In `qtest.c`, there are two code exists in `queue_init()`

static void queue_init()
{
    /*Initialize the queue
    1. The number of failure
    2. Initialize the queue with a `NULL`.*/
    fail_count = 0;
    q = NULL;
    signal(SIGSEGV, sigsegvhandler); /* Invalid access to storage */
    signal(SIGALRM, sigalrmhandler); /* Alarm clock */
}

- `signal(int, ()=>{})`
- Declared as `void (*signal(int, void(*func)(int))) (int)`
- These two line of code will like a listener, if there is any signal raised by user using `raise` or by system, then it will call the `signal handler` which is declared as a function with an argument of int.
- `sigsegvhandler`
- It is a function will be called after occurring `SIGSEGV`(Invalid access to storage) signal.
- Which calls `trigger_exception()` to trigger a exception with custimized error message.
- `sigalrmhandler`
- Calls after occurring `SIGALRM`(Alarm clock)
- Which calls `trigger_exception()` to trigger a exception with custimized error message.

- `trigger_exception()`
- It will call the `siglongjmp(jmp_buf, int)` which is paired with `sigsetjmp(jmp_buf, int)` then return to the most recent invocation environment.

## The principle of Valgrind
According to this [paper](http://valgrind.org/docs/valgrind2007.pdf) published by Nicholas and Julian, this tool is so called shadow value tools --- a powerful but previously little-studied and difficult-to-implemnet DBA technique, which requires a tool to shadow every register and memory value with another value that describes it.
### overview
#### Basic Architecture
Valgrind tools are created as plug-ins, written in C, to Valgrind's core.
#### Execution
Quote from the [paper](http://valgrind.org/docs/valgrind2007.pdf)
>> Valgrind uses dyamic binary re-compilation, similar to many other DBI frameworks. The core disassembles the code block into an intermediate representation (IR) which is instrumented with analysis code by the tool plug-in, and then converted by the core back into machine code.

#### Starting Up
The goal of start-up is to
1. Load Valgrind's core
2. The plug-in tool
3. The client program

into a single process, sharing the same address space.

- `1. Core`
Valgrind's core first initialises some sub-systems, such as the address space manager and its own internal memory allocator.

- `2. client program`
It then sets up the clients stack and data segment.

- `3. plug-ins & sub-systems`
The core then tells the tool to initialise itself. The command-line is parsed and core and tool options are dealt with. Finally, more core sub-systems are initialised: The translation table, the signal-handling machinery, the thread scheduler, and debug information for the client is loaded.

### Using `valgrind`
Valgrind has many plug-in tools and the default one is `Memcheck`. Although valgrind is a powerful DBI, it may slow the execution time.
Take the `traces/traces-01-ops.cmd` for example

The it produced the following message.

==11541== Memcheck, a memory error detector
==11541== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==11541== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==11541== Command: ./qtest -f traces/trace-01-ops.cmd
==11541==
cmd># Test of insert_head and remove_head
cmd>option fail 0
cmd>option malloc 0
cmd>new
q = []
cmd>ih gerbil
q = [gerbil]
cmd>ih bear
q = [bear gerbil]
cmd>ih dolphin
q = [dolphin bear gerbil]
cmd>rh dolphin
Removed dolphin from queue
q = [bear gerbil]
cmd>rh bear
Removed bear from queue
q = [gerbil]
cmd>rh gerbil
Removed gerbil from queue
q = []
cmd>
Freeing queue
==11541==
==11541== HEAP SUMMARY:
==11541== in use at exit: 0 bytes in 0 blocks
==11541== total heap usage: 84 allocs, 84 frees, 20,058 bytes allocated
==11541==
==11541== All heap blocks were freed -- no leaks are possible
==11541==
==11541== For counts of detected and suppressed errors, rerun with: -v
==11541== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

We can see that this program has no memory leckage problem. Let take more testing.

cp qtest /tmp/qtest.93eNQj
chmod u+x /tmp/qtest.93eNQj
sed -i "s/alarm/isnan/g" /tmp/qtest.93eNQj
scripts/driver.py -p /tmp/qtest.93eNQj --valgrind
---	Trace		Points
+++ TESTING trace trace-01-ops:
==12003== Memcheck, a memory error detector
==12003== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==12003== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==12003== Command: /tmp/qtest.93eNQj -v 1 -f ./traces/trace-01-ops.cmd
==12003== 
# Test of insert_head and remove_head
==12003== 
==12003== HEAP SUMMARY:
==12003==     in use at exit: 0 bytes in 0 blocks
==12003==   total heap usage: 84 allocs, 84 frees, 20,058 bytes allocated
==12003== 
==12003== All heap blocks were freed -- no leaks are possible
==12003== 
==12003== For counts of detected and suppressed errors, rerun with: -v
==12003== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
---	trace-01-ops	6/6
+++ TESTING trace trace-02-ops:
==12004== Memcheck, a memory error detector
==12004== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==12004== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==12004== Command: /tmp/qtest.93eNQj -v 1 -f ./traces/trace-02-ops.cmd
==12004== 
# Test of insert_head, insert_tail, and remove_head
==12004== 
==12004== HEAP SUMMARY:
==12004==     in use at exit: 0 bytes in 0 blocks
==12004==   total heap usage: 119 allocs, 119 frees, 29,840 bytes allocated
==12004== 
==12004== All heap blocks were freed -- no leaks are possible
==12004== 
==12004== For counts of detected and suppressed errors, rerun with: -v
==12004== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
---	trace-02-ops	6/6
+++ TESTING trace trace-03-ops:
==12010== Memcheck, a memory error detector
==12010== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==12010== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==12010== Command: /tmp/qtest.93eNQj -v 1 -f ./traces/trace-03-ops.cmd
==12010== 
# Test of insert_head, insert_tail, reverse, and remove_head
==12010== 
==12010== HEAP SUMMARY:
==12010==     in use at exit: 0 bytes in 0 blocks
==12010==   total heap usage: 156 allocs, 156 frees, 36,483 bytes allocated
==12010== 
==12010== All heap blocks were freed -- no leaks are possible
==12010== 
==12010== For counts of detected and suppressed errors, rerun with: -v
==12010== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
---	trace-03-ops	6/6
+++ TESTING trace trace-04-ops:
==12011== Memcheck, a memory error detector
==12011== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==12011== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==12011== Command: /tmp/qtest.93eNQj -v 1 -f ./traces/trace-04-ops.cmd
==12011== 
# Test of insert_head, insert_tail, and size
==12011== 
==12011== HEAP SUMMARY:
==12011==     in use at exit: 0 bytes in 0 blocks
==12011==   total heap usage: 115 allocs, 115 frees, 23,603 bytes allocated
==12011== 
==12011== All heap blocks were freed -- no leaks are possible
==12011== 
==12011== For counts of detected and suppressed errors, rerun with: -v
==12011== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
---	trace-04-ops	6/6
+++ TESTING trace trace-05-ops:
==12012== Memcheck, a memory error detector
==12012== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==12012== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==12012== Command: /tmp/qtest.93eNQj -v 1 -f ./traces/trace-05-ops.cmd
==12012== 
# Test of insert_head, insert_tail, remove_head reverse, and size
==12012== 
==12012== HEAP SUMMARY:
==12012==     in use at exit: 0 bytes in 0 blocks
==12012==   total heap usage: 142 allocs, 142 frees, 30,029 bytes allocated
==12012== 
==12012== All heap blocks were freed -- no leaks are possible
==12012== 
==12012== For counts of detected and suppressed errors, rerun with: -v
==12012== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
---	trace-05-ops	6/6
+++ TESTING trace trace-06-string:
==12013== Memcheck, a memory error detector
==12013== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==12013== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==12013== Command: /tmp/qtest.93eNQj -v 1 -f ./traces/trace-06-string.cmd
==12013== 
# Test of truncated strings
==12013== 
==12013== HEAP SUMMARY:
==12013==     in use at exit: 0 bytes in 0 blocks
==12013==   total heap usage: 191 allocs, 191 frees, 28,138 bytes allocated
==12013== 
==12013== All heap blocks were freed -- no leaks are possible
==12013== 
==12013== For counts of detected and suppressed errors, rerun with: -v
==12013== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
---	trace-06-string	7/7
+++ TESTING trace trace-07-robust:
==12015== Memcheck, a memory error detector
==12015== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==12015== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==12015== Command: /tmp/qtest.93eNQj -v 1 -f ./traces/trace-07-robust.cmd
==12015== 
# Test operations on NULL queue
==12015== 
==12015== HEAP SUMMARY:
==12015==     in use at exit: 0 bytes in 0 blocks
==12015==   total heap usage: 64 allocs, 64 frees, 13,441 bytes allocated
==12015== 
==12015== All heap blocks were freed -- no leaks are possible
==12015== 
==12015== For counts of detected and suppressed errors, rerun with: -v
==12015== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
---	trace-07-robust	7/7
+++ TESTING trace trace-08-robust:
==12016== Memcheck, a memory error detector
==12016== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==12016== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==12016== Command: /tmp/qtest.93eNQj -v 1 -f ./traces/trace-08-robust.cmd
==12016== 
# Test operations on empty queue
==12016== 
==12016== HEAP SUMMARY:
==12016==     in use at exit: 0 bytes in 0 blocks
==12016==   total heap usage: 57 allocs, 57 frees, 13,433 bytes allocated
==12016== 
==12016== All heap blocks were freed -- no leaks are possible
==12016== 
==12016== For counts of detected and suppressed errors, rerun with: -v
==12016== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
---	trace-08-robust	7/7
+++ TESTING trace trace-09-robust:
==12017== Memcheck, a memory error detector
==12017== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==12017== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==12017== Command: /tmp/qtest.93eNQj -v 1 -f ./traces/trace-09-robust.cmd
==12017== 
# Test remove_head with NULL argument
==12017== 
==12017== HEAP SUMMARY:
==12017==     in use at exit: 0 bytes in 0 blocks
==12017==   total heap usage: 57 allocs, 57 frees, 10,463 bytes allocated
==12017== 
==12017== All heap blocks were freed -- no leaks are possible
==12017== 
==12017== For counts of detected and suppressed errors, rerun with: -v
==12017== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
---	trace-09-robust	7/7
+++ TESTING trace trace-10-malloc:
==12019== Memcheck, a memory error detector
==12019== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==12019== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==12019== Command: /tmp/qtest.93eNQj -v 1 -f ./traces/trace-10-malloc.cmd
==12019== 
# Test of malloc failure on new
==12019== 
==12019== HEAP SUMMARY:
==12019==     in use at exit: 0 bytes in 0 blocks
==12019==   total heap usage: 69 allocs, 69 frees, 10,589 bytes allocated
==12019== 
==12019== All heap blocks were freed -- no leaks are possible
==12019== 
==12019== For counts of detected and suppressed errors, rerun with: -v
==12019== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
---	trace-10-malloc	7/7
+++ TESTING trace trace-11-malloc:
==12020== Memcheck, a memory error detector
==12020== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==12020== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==12020== Command: /tmp/qtest.93eNQj -v 1 -f ./traces/trace-11-malloc.cmd
==12020== 
# Test of malloc failure on insert_head
==12020== 
==12020== HEAP SUMMARY:
==12020==     in use at exit: 0 bytes in 0 blocks
==12020==   total heap usage: 89 allocs, 89 frees, 11,795 bytes allocated
==12020== 
==12020== All heap blocks were freed -- no leaks are possible
==12020== 
==12020== For counts of detected and suppressed errors, rerun with: -v
==12020== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
---	trace-11-malloc	7/7
+++ TESTING trace trace-12-malloc:
==12021== Memcheck, a memory error detector
==12021== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==12021== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==12021== Command: /tmp/qtest.93eNQj -v 1 -f ./traces/trace-12-malloc.cmd
==12021== 
# Test of malloc failure on insert_tail
==12021== 
==12021== HEAP SUMMARY:
==12021==     in use at exit: 0 bytes in 0 blocks
==12021==   total heap usage: 135 allocs, 135 frees, 13,953 bytes allocated
==12021== 
==12021== All heap blocks were freed -- no leaks are possible
==12021== 
==12021== For counts of detected and suppressed errors, rerun with: -v
==12021== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
---	trace-12-malloc	7/7
+++ TESTING trace trace-13-perf:
==12023== Memcheck, a memory error detector
==12023== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==12023== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==12023== Command: /tmp/qtest.93eNQj -v 1 -f ./traces/trace-13-perf.cmd
==12023== 
# Test performance of insert_tail
==12023== 
==12023== HEAP SUMMARY:
==12023==     in use at exit: 0 bytes in 0 blocks
==12023==   total heap usage: 2,004,063 allocs, 2,004,063 frees, 104,216,490 bytes allocated
==12023== 
==12023== All heap blocks were freed -- no leaks are possible
==12023== 
==12023== For counts of detected and suppressed errors, rerun with: -v
==12023== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
---	trace-13-perf	7/7
+++ TESTING trace trace-14-perf:
==12025== Memcheck, a memory error detector
==12025== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==12025== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==12025== Command: /tmp/qtest.93eNQj -v 1 -f ./traces/trace-14-perf.cmd
==12025== 
# Test performance of size
==12025== 
==12025== HEAP SUMMARY:
==12025==     in use at exit: 0 bytes in 0 blocks
==12025==   total heap usage: 2,000,056 allocs, 2,000,056 frees, 104,010,380 bytes allocated
==12025== 
==12025== All heap blocks were freed -- no leaks are possible
==12025== 
==12025== For counts of detected and suppressed errors, rerun with: -v
==12025== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
---	trace-14-perf	7/7
+++ TESTING trace trace-15-perf:
==12029== Memcheck, a memory error detector
==12029== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==12029== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==12029== Command: /tmp/qtest.93eNQj -v 1 -f ./traces/trace-15-perf.cmd
==12029== 
# Test performance of insert_tail, size, and reverse
==12029== 
==12029== HEAP SUMMARY:
==12029==     in use at exit: 0 bytes in 0 blocks
==12029==   total heap usage: 4,000,074 allocs, 4,000,074 frees, 207,010,604 bytes allocated
==12029== 
==12029== All heap blocks were freed -- no leaks are possible
==12029== 
==12029== For counts of detected and suppressed errors, rerun with: -v
==12029== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
---	trace-15-perf	7/7
---	TOTAL		100/100

Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.93eNQj --valgrind -t <tid>
make valgrind  30.69s user 0.92s system 99% cpu 31.622 total

All operations with no memory leakage.
## `dudect`
For now, I still can't understand the principle of `dudect`. Right now, I try to understand how to use `dudect`.
:::info
The github has no explaination to the source code. After I traced the src, I found that there is no `int main() {}` in every test files.
- How can these programs run without `int main() {}` ?
- Or, is there any background knowledge needed to know in advanced ?

Thanks !
:::

## `MAGICHEADER` , `MAGICFOOTER` and `MAGICFREE`
The three macro number is used to mark the struct with typedef named `block_ele_t`.
- `MAGICHEADER`
- If a new block_ele_t is being created successfully, the overloading version of library function `test_malloc` will set the magic_header as `MAGICHEADER`.

- `MAGICFOOTER`
- If a new block_ele_t is being created successfully, the overloading version of library function `test_malloc` will set the content of the end of block as `MAGICFOOTER`.

- `MAGICFREE`
- If a block_ele_t is being deleted, the overloading version of library function `test_free` will overwrite the magic_header to `MAGICFOOTER`.


That is, the machnism of the `MAGIC-` macro is to set the mark to check the block is being allocated successfully depending on the content in the end of the block whether it is `MAGICFOOTER` or not. If not, it will report a exception with error message,`"Corruption detected in block with address %p when "
"attempting to free it"`. Otherwise, `test_free()` will overwrite the content of `magic_header` to `MAGICFREE` representing the block is being freed.

It's a good method to control and shadow all operation when executing a queue in console. We can custimized the operation when the usr is operating a malloc function. And, the `MACRO-` also offer a glance way to handle whether the block is being freed or not by checking the `magic_header` is `MAGICHEADER` or `MAGICFOOTER`.

## How to make the complexity of `insert_tail` and `q_size()` converge to `O(1)`

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail; /* Add a pointer named tail point the tail of a queue*/
    int len; /* Record the length of queue */
} queue_t;

- `insert_tail()`
If we store the address of the tail of queue, then we can save the operation to traverse the queue in order to find out tail. It make the `insert_tail()` operation into constant time.

- `q_size()`
Save the length of the queue when operating `insert_head` or `insert_tail` every time. Then, we can save the time to traverse whole queue to know the length of queue.

## No allocation to reverse the queue
<a href="#reverse">See</a>
Using a temporary pointer which type is `list_ele_t*` be a fake header which the queue point called fake queue. Then, pop the geninne queue and let the fh(fake header) point to the new popped-out block. Finally, let the popped-out block point to the head of fake queue which fh originally point. Using a for loop to traverse the whole genine queue util the last one. Then, let the queue header point back to the fake queue.

## Reference

* [signal](https://www.ibm.com/support/knowledgecenter/en/SSLTBW_2.4.0/com.ibm.zos.v2r4.bpxbd00/rtsigsl.htm)
* [signalMask](https://www.gnu.org/software/libc/manual/html_node/Process-Signal-Mask.html)
* [fork system call](http://www.csl.mtu.edu/cs4411.ck/www/NOTES/process/fork/create.html)
* [dude, is my code constant time?](https://github.com/oreparaz/dudect)