# 2019q3 Homework1 (lab0)
contributed by < `NoahNut` >

[作業說明](https://hackmd.io/s/BJA8EgFB4)
[C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)

## 實驗環境

$ uname -a
Linux noah-UX330UA 4.15.0-43-generic #46~16.04.1-Ubuntu SMP Fri Dec 7 13:31:08 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
$ gcc -version
gcc (Ubuntu 5.5.0-12ubuntu1~16.04) 5.5.0 20171010

:::info
Memory Leak
在實作所有 Function 的時候要注意，當有例外發生時，被 malloc 過的記憶體位置記得也要 free 掉，不然就會造成嚴重的 Memory leak。
:::

:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)

程式碼縮排是 4 spaces，而不是 tab，請修改下方所有程式碼。把細節做好，才有態度挑戰難題。
:notes: jserv
:::

---

## 過程

### queue_t data struct
在題目中提到 `q_size` 跟 `q_insert_tail` 都必須在 $O(1)$ 時間複雜度完成，所以必須隨時去紀錄 `queue` 的 size 跟 tail 的位置。

typedef struct {
    list_ele_t *head;
    list_ele_t *tail; /* Linked list of elements */
                      /*
                        You will need to add more fields to this structure
                        to efficiently implement q_size and q_insert_tail
                      */
    int size;
} queue_t

### q_new
- 初始化 queue

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (!q) {
        return NULL;
    }

    else {
        q->head = NULL;
        q->size = 0;
        return q;
    }
}

### q_insert_head
在實作這個函式時，遇到一個奇怪的問題，我在 allocate 一個空間給 string 時，我所使用的方式為 `malloc` 加 `strcpy`，出來的 string 總為亂碼，直到使用 `strdup` ，目前還是未解？

這種例外處理，就必須要很注意是否有 memory leak 發生，因為在前面已經` malloc` 過所以就必須要將分配的記憶體還回去。

    if (newh->value == NULL) {
        free(newh);
        return false;
    }

bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL) {
        return false;
    }
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    newh = malloc(sizeof(list_ele_t));

    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */

    if (!newh) {
        return false;
    }

    newh->value = strdup(s);

    if (newh->value == NULL) {
        free(newh);
        return false;
    }

    if (q->head == NULL) {
        q->tail = newh;
    }

    newh->next = q->head;
    q->head = newh;
    q->size++;
    return true;
}

### q_free
原先是利用`do while`的語法來寫，但是當是空 queue 的時候要 free 就會出現
`ERROR: Segmentation fault occurred. You dereferenced a NULL or invalid pointer`
跟`ERROR: Freed queue, but 1 blocks are still allocated`
原因是當 queue 是空的時候，在 `do while` 語法會先去跑其中的程式碼在看 while 的判斷後決定是否繼續跑下去，但是這樣就會 free 到 NULL，而造成錯誤。

void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */

    list_ele_t *temp;
    while (q->head) {
        temp = q->head->next;
        free(q->head);
        q->head = temp;
    }

    free(q);
}

### q_insert_tail
- 如果 q 是空的就必須將 `head` 跟 `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 *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh) {
        return false;
    }

    newh->value = strdup(s);
    newh->next = NULL;

    if (newh->value == NULL) {
        free(newh);
        return false;
    }

    if (q->head == NULL) {
        q->head = newh;
        q->tail = newh;
    } else {
        q->tail->next = newh;
        q->tail = newh;
    }

    q->size++;

    return true;
 }

### 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->size == 0) {
        return 0;
    }

    return q->size;
}

### q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if (q == NULL || q->size == 0) {
        return false;
    }

    if (sp) {
        list_ele_t *temp;

        strncpy(sp, q->head->value, bufsize - 1);

        temp = q->head;
        q->head = q->head->next;
        free(temp);
        q->size--;
        return true;
    }
    return false;
}

### q_reverse
- 用三個指標來為實作 reverse，一開始先將 tail 跟 head 互換，然後將 head 的 next 指向 tail，作為 reverse 到最後的 index。

- 先將 `temp` 跟 `iterator` 初始化，`iterator` 指向新的 tail，`temp` 指向 tail 的 next block。

- 在 while 迴圈中，`temp_two` 會指向現在 `iterator` 的位置，`iterator` 會前進到 `temp`，如果 `iterator` 不是指向 tail，就將 `temp` 在往前一格，最後在將 `iterator` 所指的 next 反轉。

- 最後將 tail 的 next 指向 NULL。

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    
    if (q == NULL || q->size == 0) {
        return;
    }
  
    list_ele_t *temp;
    list_ele_t *iterator;
    list_ele_t *temp_two;

    temp = q->tail;
    q->tail = q->head;
    q->head = temp;
    q->head->next = q->tail;
    iterator = q->tail;
    temp = q->tail->next;

    while (temp != q->tail) {
       temp_two = iterator;
       iterator = temp;
       if(iterator != q->tail){
         temp = iterator->next;
       }
       iterator->next = temp_two; 
    }
    
    q->tail->next = NULL;
}
    

## qtest 的行為和裡頭的技巧

### console_init
- 在 console_init 中的 `add_cmd` 和 `add_param`，利用到 function pointer 的技巧，只要跟著其對於函式回傳值與傳入值的規範，就能統一性的新增 command。

/* Each command defined in terms of a function */
typedef bool (*cmd_function)(int argc, char *argv[]);

static void console_init()
{
    add_cmd("new", do_new, "                | Create new queue");
    add_cmd("free", do_free, "                | Delete queue");
    add_cmd("ih", do_insert_head,
            " str [n]        | Insert string str at head of queue n times "
            "(default: n == 1)");
    add_cmd("it", do_insert_tail,
            " str [n]        | Insert string str at tail of queue n times "
            "(default: n == 1)");
    add_cmd("rh", do_remove_head,
            " [str]          | Remove from head of queue.  Optionally compare "
            "to expected value str");
    add_cmd(
        "rhq", do_remove_head_quiet,
        "                | Remove from head of queue without reporting value.");
    add_cmd("reverse", do_reverse, "                | Reverse queue");
    add_cmd("size", do_size,
            " [n]            | Compute queue size n times (default: n == 1)");
    add_cmd("show", do_show, "                | Show queue contents");
    add_param("length", &string_length, "Maximum length of displayed string",
              NULL);
    add_param("malloc", &fail_probability, "Malloc failure probability percent",
              NULL);
    add_param("fail", &fail_limit,
              "Number of times allow queue operations to return false", NULL);
}

### add_cmd

- Command 由一個 alphabetical order 的 link list 所儲存。

static cmd_ptr cmd_list = NULL;

- 在 `add_cmd` 的 function 中，next_cmd 是在 link list 中 command 的值，而 last_loc 是指向 cmd_list 中的位置。

cmd_ptr next_cmd = cmd_list;
cmd_ptr *last_loc = &cmd_list;

- 這個 while 迴圈是作為 alphabetical order 的位置判斷。

    while (next_cmd && strcmp(name, next_cmd->name) > 0) {
        last_loc = &next_cmd->next;
        next_cmd = next_cmd->next;
    }

- 找到適合的位置後，在這個 linked list 中插入。

cmd_ptr ele = (cmd_ptr) malloc_or_fail(sizeof(cmd_ele), "add_cmd");
ele->name = name;
ele->operation = operation;
ele->documentation = documentation;
ele->next = next_cmd;
*last_loc = ele;

Linked list 這樣的資料結構，可以讓刪除跟新增資料變得相當容易，只需要改變其 struct 中 next 所指向的資料。
在之後許多原本要存 Array 的資料都可以改成 linked list 來實作，方便新增跟刪除。

### malloc and free

在 `harness.h` 中可以看到以下`preprocessor`的格式。
用以區別在 `queue.c` 中所使用的 malloc 和 free 是另外實現的， 這樣的技巧就可以在有 define 特定 flag 的檔中實現特定函式。
以 qtest 為例，除了 `queue.c` 之外都在檔案起頭處有 `define INTERNAL` ，都是使用 C 本身的 malloc 跟 free 只有 `queue.c`是使用在 `harness.h` 中實作的。
:::danger
這邊先留著，需要查更多的資料跟實驗來更詳細的描述這邊在編譯時期是怎樣運作。 將[你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/s/S1maxCXMl#)補完
:::

#ifdef INTERNAL
size_t allocation_check();
...
#else
/* Tested program use our versions of malloc and free */
#define malloc test_malloc
#define free test_free
#endif

這裡可以發現 `define INTERNAL` 在 `include` 前。

/* Our program needs to use regular malloc/free */
#define INTERNAL 1
#include "harness.h"

---
### test_malloc
而在 `test_malloc` 中所分配得到的記憶體，是被紀錄在一個 `allocated` 的 double linked list，這個linked list的每一個node 都是由定義在 `harness.h` 中 `block_ele_t` 的結構中。

typedef struct BELE {
    struct BELE *next;
    struct BELE *prev;
    size_t payload_size;
    size_t magic_header; /* Marker to see if block seems legitimate */
    unsigned char payload[0];
    /* Also place magic number at tail of every block */
} block_ele_t;

在結構的最後用到了 [Arrays of Length Zero](https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html) 的技巧，這樣最後 payload 大小就能夠直接在 `malloc` 的時候調整，在這個結構的最後面還要在加入一個 magic number 作為此記憶體區塊 tail 的標示。

- `magic header`
`block_ele_t` 結構中，可以看到有定義 `magic_header` 這個是作為這個記憶體區塊是否合法操作判定的標誌，`harness.c` 中就定義了 `MAGICHEADER 0xdeadbeef` 和 `MAGICFREE 0xffffffff` 如果是 `0xdeadbeef` 就代表此區塊已經被合法 malloc， 利用這樣的方式在 free 的時候可以避免 free 到一塊非法的記憶體位置。

- `magic tail`
`MAGICFOOTER 0xbeefdead` 作為此區塊的記憶體結束位置的判定。

> magic number 這一詞的意思是在程式碼中有些被設計師寫死的常數，如果沒下註解，會造成後續來維護的設計師，黑人問號...
> 其最早出處`雷神之鎚III競技場` 的一段 [平方根快速演算法](https://zh.wikipedia.org/wiki/%E5%B9%B3%E6%96%B9%E6%A0%B9%E5%80%92%E6%95%B0%E9%80%9F%E7%AE%97%E6%B3%95)，雖然得到很好的優化，但是某段有 magic number 的程式碼卻讓人充滿疑惑(超神的拉)。

- 記憶體區塊
這個記憶體的區塊大小分配是根據， payload 的大小、紀錄這個區塊性質的結構與最後標示區塊結束位置的 `magic tail` 。

    block_ele_t *new_block =
        malloc(size + sizeof(block_ele_t) +        
        sizeof(size_t));

- malloc 成功之後在 `block_ele_t` 結構中的 `magic_header` 填入 `MAGICHEADER` 跟 `payload_size` 填入欲輸入 payload 的 size。
- 利用 `find_footer` 這個 function 找到其記憶體的最後的位置，
這個 function 回傳一個型態為 `size_t` 的 `pointer` 指向記憶體區塊最後的位置，在將 `magic tail` 的值 assign 到最後記憶體區塊最後的位置。

static size_t *find_footer(block_ele_t *b)
{
    size_t *p = (size_t *) ((size_t) b + b->payload_size + sizeof(block_ele_t));
    return p;
}

在這個函式中，找到最後這個區塊記憶體位置的方式，是傳入之前 malloc 過後的 `pointer struct`，因為傳進去的記憶體位置會是這個結構，在程式的 `heap` 上初始的 `memory address` 在加上 `payload size` 跟 `block_ele_t` 這個結構的大小，就能找到此區塊的結尾。

---

#### Double Linked list

    new_block->next = allocated;
    new_block->prev = NULL;
    if (allocated)
        allocated->prev = new_block;
    allocated = new_block;

1. 在將新 malloc 的記憶體區塊，放到現有的 double linked list 的最前面，`new_block` 的 next 會指向前一個被分配的記憶體區塊，並且 `new_block` 因為是最新被分配出來的記憶體區塊，所以其 prev 會指向 NULL。
2. 如果這個 double linked list 已經有一個以上的記憶體區塊，前一個被 allocated 記憶體區塊 prev 就會指向 `new_block` 。
3. 最後將 `new_block` assign 給 `allocated` 這個指向 double linked list header `block_ele_t` 結構型態的指標。

### test_free

這個函式作為 `queue.c` 中 `free` 函式的實作。
一開始先找到想要 free 的記憶體區塊的頭跟尾，分別利用 `find_header` 跟 `find_footer` 函式，然後在將這個區塊頭尾的 `magic number` 改成 `MAGICFREE` 標示這個區塊已經被 free 過了，避免 double free。

    block_ele_t *b = find_header(p);
    size_t footer = *find_footer(b);
    if (footer != MAGICFOOTER) {
        report_event(MSG_ERROR,
                     "Corruption detected in block with address %p when "
                     "attempting to free it",
                     p);
        error_occurred = true;
    }
    b->magic_header = MAGICFREE;
    *find_footer(b) = MAGICFREE;

> 如果將 size_t footer = *find_footer(b) 改寫成 size_t *footer = find_footer(b)，這樣在 *find_footer(b) = MAGICFREE 就可以用 *foot 直接來設值，不用在跳到 `find_footer` 這個 function。
>
> - 在 gdb 中做 debug 或追蹤內部運作時，需要先將 `harness.c` 中的 `static int time_limit` 調長，不然時間一到系統就是發出 signal 將程式 interrupt，發出錯誤訊息。

- 之後就是單純用 `memset` 將原本 payload 初始成 `FILLCHAR` 之後在將這個記憶體區塊從 double linked list 中拿掉。

> 在 `free` 之前使用 `memset` 可能原因是 `free` 只將這塊記憶體歸還給作業系統，但裡面的值可能還在裡面，如果下一個使用者也使用到這個記憶體裡面可能還有上一個殘存的值。