2018q3 Homework2 (lab0)
===

contributed by < [`ChingChieh`](https://github.com/ChingChieh) >
###### tags: `sysprog2018`
## 開發紀錄

### 環境
* 系統版本：unbuntu 18.04.1
* gcc 版本：gcc (Ubuntu 7.3.0-16ubuntu3) 7.3.0
## 過程
### queue_t

typedef struct {
    list_ele_t *head; 
    list_ele_t *tail; 
    size_t size;
} queue_t;

因為 [q_insert_tail](#q_insert_tail) 和 [q_size](#q_size) 要達到 $O(1)$ 所以需要額外記住 queue size 和 tail 位子

---

### q_size

int q_size(queue_t *q) 
{
    /* You need to write the code for this function */
    /* Remember: It should operate in O(1) time */
    if (q == NULL || q->head == NULL) {
        return 0;
    }   
    return q->size;
}

---

### q_free

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

要記得先free(q->head->value)再free(q->head)
因為我一開始就沒有用strdup的方式複製字串，所以沒遇到free(q->head->value)會錯誤的問題

---

### q_insert_head

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;
    }
    newh = (list_ele_t *) malloc(sizeof(list_ele_t));
    if (newh == NULL) {
        return false;
    }
    size_t s_len = strlen(s) + 1;  // Don't forget the \0!!!!!!!
    /* Don't forget to allocate space for the string and copy it */
    newh->value = (char *) malloc(s_len * sizeof(char));
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    strcpy(newh->value, s);
    /* What if either call to malloc returns NULL? */
    newh->next = q->head;
    if (newh->next == NULL) {  // Change the tail
        q->tail = newh;
    }
    q->head = newh;
    q->size++;
    return true;
}

要記得malloc的時候要多給他一個 char 的空間存 '\0'

---

### q_insert_tail

bool q_insert_tail(queue_t *q, char *s)
{
    /* You need to write the complete code for this function */
    /* Remember: It should operate in O(1) time */
    if (q == NULL) {
        return false;
    }
    list_ele_t *newt;
    newt = (list_ele_t *) malloc(sizeof(list_ele_t));
    if (newt == NULL) {
        return false;
    }
    long int slen = strlen(s) + 1;
    newt->value = (char *) malloc(sizeof(char) * slen);
    if (newt->value == NULL) {
        free(newt);
        return false;
    }
    strcpy(newt->value, s);
    if (q->tail != NULL) {
        q->tail->next = newt;
    } else {
        q->head = newt;
    }
    q->tail = newt;
    newt->next = NULL;
    q->size++;
    return true;
}

---

### q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL || q->head == NULL || bufsize <= 0) {
        return false;
    }
    if (sp != NULL) {
        strncpy(sp, q->head->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    list_ele_t *headnext = q->head->next;

    free(q->head->value);
    free(q->head);
    q->head = headnext;
    q->size--;
    return true;
}

---

### q_reverse

void q_reverse(queue_t *q)
{
    if (q == NULL || q->size < 2) {
        return;
    }
    q->tail = q->head;
    list_ele_t *prev = NULL;
    list_ele_t *temp;
    list_ele_t *curr = q->head;
    while (curr != NULL) {
        temp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = temp;
    }
    q->head = prev;
}                                             

## 進度

$ make test
scripts/driver.py
...
...
---	trace-15-perf	7/7
---	TOTAL		100/100

## makefile
* rm *~ 意思
* 把檔案結尾是~的檔案刪掉，這種檔案是 editor 產生的備用檔。如果在 .vimrc 設定set backup也可以產生這種備用檔
## 遭遇問題
1. [queue.c:79]: (error) Memory leak: newh
* 原因:當要對 queue 做 insert 的時候總共要 `malloc()` 兩次，如果回傳結果是 NULL 就 return false，但在第二次檢查的時候忘記把第一次 `malloc()` 的空間 free 掉

    newh = (list_ele_t *) malloc(sizeof(list_ele_t));
    if (newh == NULL) {
        return false;
    }                                                                                                                   
    newh->value = (char *) malloc(s_len * sizeof(char));
    if (newh->value == NULL) {
        free(newh);  //要記得 free 掉之前成功 malloc 的空間
        return false;
    }   

## 自動評分系統運作原理

## qtest行為＆技巧
用有沒有 define INTERNAL 來判斷是否使用自定義的malloc和free

在 harrness.h 裡面有

#ifdef INTERNAL
...
#else
#define malloc test_malloc
#define free test_free
#endif                

帶表如果有先定義INTERNAL就不會把 malloc、free 改成 test_malloc、test_free

---

### 如何偵測buffer overflow
test_malloc 程式碼:

void *test_malloc(size_t size)
{
    ...
    block_ele_t *new_block =
        malloc(size + sizeof(block_ele_t) + sizeof(size_t));
    if (new_block == NULL) {
        report_event(MSG_FATAL, "Couldn't allocate any more memory");
        error_occurred = true;
    }
    new_block->magic_header = MAGICHEADER;
    new_block->payload_size = size;
    *find_footer(new_block) = MAGICFOOTER;
    void *p = (void *) &new_block->payload;
    memset(p, FILLCHAR, size);
    new_block->next = allocated;
    new_block->prev = NULL;
    if (allocated)
        allocated->prev = new_block;
    allocated = new_block;
    allocated_count++;
    return p;
}

每次呼叫test_malloc(size)分配的空間:

malloc(size + sizeof(block_ele_t) + sizeof(size_t));

test_malloc return 的是指向size起始address的pointer:

void *p = (void *) &new_block->payload;

這裡用到的技巧是arrays of length zero，通常是用在struct的最後一個element，這樣的好處是可以把payload當成block_ele_t後面記憶體位址的開頭

此外再用find_footer()定出size結尾的記憶體位址，然後把後面那塊sizeof(size_t)記憶體的值改成MAGICFOOTER

static size_t *find_footer(block_ele_t *b) 
{
    size_t *p = (size_t *) ((size_t) b + b->payload_size + sizeof(block_ele_t));
    //payload_size 是使用者可以用的空間大小
    return p;
}

*find_footer(new_block) = MAGICFOOTER;

加上之前把magic_header的值設成MAGICHEADER，所以使用者能合法使用的空間就像被兩塊記憶體空間夾在中間，使用超出size的空間就會改到MAGICFOOTER或MAGICHEADER因此可以在test_free時被偵測出來