# 2019q1 Homework1 (lab0)
contributed by < `TsundereChen` >
###### tags: `sysprog` `TsundereChen`

* [GitHub Repo](https://github.com/TsundereChen/lab0-c)

## Report
### queue.h & queue.c
#### struct queue_t
* Add `list_ele_t *tail` and `int size` in order to track queue more easily

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

#### queue_t \*q_new()
* It's just initializing queue, using malloc
* Check if malloc failed

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

#### void q_free(queue_t \*q)
* Check if queue is valid, and free from the head to the tail

void q_free(queue_t *q)
{
    if (q != NULL && ((q->head != NULL) && (q->tail != NULL))) {
        while (q->head != q->tail) {
            list_ele_t *del_t = q->head;
            q->head = q->head->next;
            free(del_t->value);
            free(del_t);
        }
        free(q->tail->value);
        free(q->tail);
    }
    free(q);
}

#### bool q_insert_head(queue_t \*q, char \*s)
* Insert an element at head of the queue
* I thought this was easy, until I got a problem
* When doing malloc to `new_h->value`, I allocated 1 more char's size to it
I did the same thing at `strncpy(new_h->value...`
* I thought the right way to copy the value is to allocate only the string's size,
and don't need one more char's space.
But that failed, and add one more char's space makes me passes all the tests
* I don't know why
:::warning
Find out the problem
:notes: TsundereChen
:::

bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL)
        return false;
    list_ele_t *new_h = (list_ele_t *) malloc(sizeof(list_ele_t));
    if (new_h == NULL)
        return false;
    new_h->value = (char *) malloc(sizeof(char) * (strlen(s) + 1));
    if (new_h->value == NULL) {
        free(new_h);
        return false;
    }
    strncpy(new_h->value, s, strlen(s) + 1);
    new_h->next = q->head;
    q->head = new_h;
    if (q->tail == NULL)
        q->tail = new_h;
    q->size += 1;
    return true;
}

#### bool q_insert_tail(queue_t \*q, char \*s)
* Basically the same as `q_insert_head`
* And have the same issue just like `q_insert_head`
:::warning
Find out the problem
:notes: TsundereChen
:::

bool q_insert_tail(queue_t *q, char *s)
{
    if (q == NULL)
        return false;
    list_ele_t *new_t = (list_ele_t *) malloc(sizeof(list_ele_t));
    if (new_t == NULL)
        return false;
    new_t->value = (char *) malloc(sizeof(char) * (strlen(s) + 1));
    if (new_t->value == NULL) {
        free(new_t);
        return false;
    }
    strncpy(new_t->value, s, strlen(s) + 1);
    new_t->next = NULL;
    if (q->tail != NULL)
        q->tail->next = new_t;
    q->tail = new_t;
    if (q->head == NULL)
        q->head = new_t;
    q->size += 1;
    return true;
}

#### bool q_remove_head(queue_t \*q, char \*sp, size_t bufsize)
* There's a function called `do_remove_head_quiet` inside `qtest.c`,
what this function does is call `q_remove_head(queue, NULL, 0)`
* So need to check the value of `*sp` and `bufsize`

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL || q->size == 0)
        return false;
    if (sp == NULL && bufsize == 0) {
        // Do nothing, skip to value removal
    } else {
        memset(sp, '\0', bufsize);
        strncpy(sp, q->head->value, bufsize - 1);
    }
    list_ele_t *del_h = q->head;
    q->size -= 1;
    if (q->size == 0) {
        q->head = NULL;
        q->tail = NULL;
    } else
        q->head = q->head->next;
    free(del_h->value);
    free(del_h);
    return true;
}

#### int q_size(queue_t \*q)
* By adding `int size` in `struct queue_t`,
this function just need to check if `q` is valid, and return `q->size`

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

#### void q_reverse(queue_t \*q)
* I found this page online: [Linked List: 新增資料、刪除資料、反轉](http://alrightchiu.github.io/SecondRound/linked-list-xin-zeng-zi-liao-shan-chu-zi-liao-fan-zhuan.html)
* This method keeps the time complexity in O(n), which can pass the test

void q_reverse(queue_t *q)
{
   	if (q == NULL || q->size < 2)
       	return;
   	else {
       	list_ele_t *tmph = q->head;
       	list_ele_t *tmpt = q->tail;
       	list_ele_t *previous = NULL;
       	list_ele_t *current = q->head;
       	list_ele_t *preceding = q->head->next;
       	while (preceding != NULL) {
           	current->next = previous;
           	previous = current;
           	current = preceding;
           	preceding = preceding->next;
       	}
       	current->next = previous;
       	q->head = tmpt;
       	q->tail = tmph;
       	return;
   	}
}

### qtest.c
* There are two kinds of `malloc`/`free`/`strdup`
One is provided by `<string.h>`, the other one is written by CMU
Latter is for tracking if your program behaves correctly or not
Check `harness.c` & `harness.h` for more information
*

### report.c & report.h

### harness.h
* In these files, there are some functions related to testing the program
#### void \*test_malloc(size_t size)

#### void test_free(void \*p)
#### char \*test_strdup(const cahr \*s)
:::info
Functions below are defined only if INTERNAL is defined
:::
#### size_t allocation_check()
#### int fail_probability
#### void set_cautious_mode(bool cautious)
#### void set_noallocate_mode(bool noallocate)
#### bool error_check()
#### bool exception_setup(bool limit_time)
#### void exception_cancel()
#### void trigger_exception(char \*msg)

### harness.c
* Test program has designed few values for checking the program
* `MAGICHEADER`, value at start of every allocated block
* `MAGICFREE`, value when deallocate block
* `MAGICFOOTER`, value at end of every block
* `FILLCHAR`, value to fill every malloced space
* The `qtest` program validates the queue using these values
* Inside `harness.c`, there are boolean values being used to change
behavior while testing the queue
* `cautious_mode`
* `noallocate_mode`
* There's a comment called `Data for managing exceptions`, and there are
three variables
* `static jmp_buf env`
* `static volatile sig_atomic_t jmp_ready = false`
* `static bool time_limited`
* According to this page [C 語言 setjmp 與 longjmp 函數用法教學](https://blog.gtwang.org/programming/c-setjmp-longjmp-function-tutorial/)
* The testing program is using `static jmp_buf env` to jump back when error occured
* And according to **[C99 standard](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf)** - 5.1.2.3 Program execution - Point 5
* `volatile` is keep the variable stable when previous acceses
are completed and subsequent accesses haven't yet occured
* In other words, `volatile` means when using this variable, program must get its value from its address
* And according to [GNU libc Manual - 24.4.7.2 Atomic Types](http://www.gnu.org/savannah-checkouts/gnu/libc/manual/html_node/Atomic-Types.html)
* `sig_atomic_t` can guarantee that read/write to this data type must happen in a single instruction, so there's no chance for "interruption"
* `volatile sig_atomic_t` can ensure that this variable won't be optimized by compiler,
and operation related to this variable must be done in single instruction

### console.c & console.h

## TODO
- [x] Modify queue.c/.h to pass `make test`
- [ ] Find the issue with `q_insert_head` and `q_insert_tail`
- [x] Test lab0-c with `valgrind`
- [ ] Understand how auto-testing system works

## Environment

tsundere:~/ $ lscpu
Architecture:        x86_64
CPU op-mode(s):      32-bit, 64-bit
Byte Order:          Little Endian
CPU(s):              4
On-line CPU(s) list: 0-3
Thread(s) per core:  1
Core(s) per socket:  4
Socket(s):           1
NUMA node(s):        1
Vendor ID:           GenuineIntel
CPU family:          6
Model:               45
Model name:          Intel(R) Xeon(R) CPU E5-2609 0 @ 2.40GHz
Stepping:            7
CPU MHz:             1588.970
CPU max MHz:         2400.0000
CPU min MHz:         1200.0000
BogoMIPS:            4787.82
Virtualization:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            10240K
NUMA node0 CPU(s):   0-3
Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 cx16 xtpr pdcm pcid dca sse4_1 sse4_2 x2apic popcnt tsc_deadline_timer aes xsave avx lahf_lm epb pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid xsaveopt dtherm arat pln pts flush_l1d
tsundere:~/ $ free -h
              total        used        free      shared  buff/cache   available
Mem:           7.7G        327M        130M        1.5M        7.3G        7.1G
Swap:          4.0G        1.0M        4.0G
tsundere:~/ $ hostnamectl
   Static hostname: tsundere-ml350p-gen8
         Icon name: computer-desktop
           Chassis: desktop
        Machine ID: 720027c2530340c2adc88062a5ca9e3d
           Boot ID: 20ff904e3f6f454e8095de141c1e3c10
  Operating System: Ubuntu 18.04.2 LTS
            Kernel: Linux 4.15.0-45-generic
      Architecture: x86-64

## Reference