# 2019q3 Homework2 (lab0)
contributed by <`davinais`>
###### tags: `sysprog` `sysprog2019`

## 實驗環境
- 家中桌機
* OS: Linux Mint 17 3.13.0-139-generic
* gcc: 4.8.5
* 因為不只我在使用所以沒有隨便升級

## 作業要求

實作一個以 linked list 為基礎的 queue，將未完成的函數實作完成。

也就是將 `queue.h`、`queue.c` 中相關函數實作完成：
- `q_new`: 建立一個空的 queue
- `q_free`: free 掉一個 queue
- `q_insert_head`: 在 queue 的 head 處插入新元素(LIFO)
- `q_insert_tail`: 在 queue 的 tail 處插入新元素(FIFO)
- `q_remove_head`: 移除 queue 目前的 head 元素
- `q_size`: 計算 queue 中元素個數
- `q_reverse`: 反轉一個 queue ，其中不可 alloc 或 free 任何元素

## 函數實作

因為作業要求已經明確寫出是要去 `queue.h`、`queue.c` 將相關函數實作完成了，因此我先直接進入這兩個檔案完成作業之後，再來檢視整份作業。

`queue.h` 中定義了兩個 `struct`，分別是元素以及 queue 容器：

/* Linked list element (You shouldn't need to change this) */
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 */
} queue_t;

我們可以發現這是個 Singular Linked List 的架構，再來檢視一下 `queue.c` ，看對所實作的函數有沒有其他要求。

最後發現本作業還要求 `q_insert_tail()` 以及 `q_size()` 都需要在 $O(1)$ 時間內完成，很明顯的以上述提供的結構是不可能達成這個任務的，我們還需要一點其他資料來輔助。

既然要使 `q_insert_tail()` 在常數時間內完成，可以用 Doubly Linked List 解決這個問題，但是我們並不能改變 `list_ele_t` 的結構。那麼還有一個方法也非常簡單，我們同時也**將 tail 記錄下來就好了**，因此我們在 `queue_t` 中新增一個 member `list_ele_t *tail` 來表示 tail。

那麼 queue 的大小要怎麼辦呢？也沒辦法從 head 跟 tail 的位址計算得出大小。那麼很簡單，**我們也把大小記錄下來**，在每次新增或刪除時更新就好了，因此再新增一個 member `size_t size`。

最後我們的 `queue_t` 便長這樣：

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

處理好 `queue` 的結構了，那我們可以開始實作函數了。

### `q_new()`

`q_new()` 一開始是有實作內容的：

/*
  Create empty queue.
  Return NULL if could not allocate space.
*/
queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    q->head = NULL;
    return q;
}

很明顯的註解還給我們提示了，如果 `malloc()` 回傳 `NULL` 該怎麼辦？**不怎麼辦，檢查是不是`NULL`啊！** 如果是的話就回傳 `NULL` ，反之則開始初始化 `queue_t`。記得還要將我們剛剛所增加的 member 也一併初始化：

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

這裡將 head 以及 tail 都先設成 `NULL` 代表沒有東西，相當無腦且暴力的解決方案。

### `q_free()`

原本的實作相當的天真：

/* Free all storage used by queue */
void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    free(q);
}

直接 free 掉 `q` 就當成 free 完成，很明顯是有問題的，連註解都提醒我們了：這樣處理的話我們可**完全沒有將 list 中的所有元素以及字串都 free 掉，問題可大了！** 這可不是有自動管理的記憶體配置系統呢！

解決的方式就是一個一個依序 free 完之後，再將 free 掉 `queue_t`，理論上可以正確的釋放所有 `malloc` 的空間，當然我們還是要先檢查 `q` 是不是 `NULL`：

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

### `q_insert_head()`

原本的實作為以下：

/*
  Attempt to insert element at head of queue.
  Return true if successful.
  Return false if q is NULL or could not allocate space.
  Argument s points to the string to be stored.
  The function must explicitly allocate space and copy the string into it.
 */
bool q_insert_head(queue_t *q, char *s)
{
    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? */
    newh->next = q->head;
    q->head = newh;
    return true;
}

基本上都被註解給提示光了，首先我們要先確認 `q` 是否為 `NULL`，再來檢查我們 alloc 的 `newh` 以及 `newh->value` 字元陣列是否有成功，最後才是進行 insert 操作。

bool q_insert_head(queue_t *q, char *s)
{
    if(!q) {
        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;
    }
    // Alloc for string
    size_t len = (strlen(s) + 1);
    newh->value = malloc(len);
    if(!(newh->value)) {
        return false;
    }
    memcpy(newh->value, s, len);
    // Insert to head
    newh->next = q->head;
    // If the queue was empty, we need to revise tail too
    if(q_is_empty(q)) {
        q->tail = newh;
    }
    q->head = newh;
    q->size++;
    return true;
}

第 65~75 行是正常的檢查步驟，76~82行，我們 alloc 空間給 string 並且進行複製。

:::danger
這邊其實有點小 bug，參見 [執行自動評分](##執行自動評分)
:::

#### 為什麼不用 `strdup` 而使用 `memcpy`？

不使用 `strdup` 的原因是因為它是 POSIX 標準而非 C99 標準(7.21 一章沒有出現 `strdup`)，可以的話我希望儘量以 C99 標準以內的東西完成，因此並沒有採用 `strdup`。使用 `strlen` 再加上結尾的 `'\0'` 作為 alloc 大小進行 `malloc`，再來進行後面 copy 的動作。

那麼為什麼在 copy 時選用 `memcpy` 而不是 `strcpy` 或者是 `strncpy` ？純粹是因為 **`strcpy` 以及 `strncpy` 在 copy 時還會檢查複製的 byte 是不是 `'\0'`** ，是的話會直接結束(參閱 C99 7.21.2)，**在我們已經確定長度的情況下有些浪費時間**。在這種情況下採用 `memcpy` 我認為是比較有效率的作法。

:::info
由於 `strcpy` 與 `strncpy` 還要檢查被複製的 byte 是不是 `'\0'` ，我想應該只能一個 byte 一個 byte 依序複製，最佳化空間比較小；相比 `memcpy` 就不會有這個問題了，因此我認為在確定長度的情況下 `memcpy` 效能必定較佳。待驗證。
:::

最後就是進行 insert，因為我們還增加了 tail 這個 member，因此在 insert 時會有兩種情況：
- `q` 原本為空佇列，我們還需要設定 `q->tail` 為 `newh`
- `q` 非空佇列，不用改動 `q->tail`

因此我們還需檢查 `q` 是否為空佇列，在這裡我多實作了一個 `q_is_empty` 的 inline 函數以供後面也能直接調用檢查。

將 `newh->next` 設定為原本的 `head` ，並且更新完 `head` 之後，將 `q->size` 增加即完成 insert 的動作。

### `q_is_empty()`

這就是我上面提到的增加來檢查 `q` 是否為空佇列的函數，實作很簡單，其實只要檢查 `head` 、 `tail` 是否為 `NULL` ，或者直接檢查 `size` 是不是 0 就可以了：

/*
  Check if queue is empty
  Return true if is empty.
  Return false in other circumstances
 */
static inline bool q_is_empty(queue_t *q)
{
    /* Check twice to avoid we only revised one of them when we call this func
     */
    return (!(q->head) && q->size == 0);
}

檢查兩個條件是為了防呆，避免改到一半的時候呼叫此函數，~~不過其實沒什麼用啦因為這樣寫也不會有編譯錯誤~~，其實只要檢查一個就好了。
:::info
其實我有點在意這種部分到底是要讓 programmer 自己注意，還是要把防呆做好才行？
:::

### `q_insert_tail()`

這裡就真的要自己實作了，不過因為我們有紀錄 tail ，所以其實和 `q_insert_head()` 類似：

/*
  Attempt to insert element at tail of queue.
  Return true if successful.
  Return false if q is NULL or could not allocate space.
  Argument s points to the string to be stored.
  The function must explicitly allocate space and copy the string into it.
 */
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) {
        return false;
    }
    list_ele_t *newt;
    newt = malloc(sizeof(list_ele_t));
    if (!newt) {
        return false;
    }
    // Alloc for string
    size_t len = (strlen(s) + 1);
    newt->value = malloc(len);
    if (!(newt->value)) {
        return false;
    }
    memcpy(newt->value, s, len);
    // Insert to tail
    newt->next = NULL;
    // If the queue was empty, we need to revise head too
    // And also we only need to revise tail->next if q was not empty
    if (q_is_empty(q)) {
        q->head = newt;
    } else {
        q->tail->next = newt;
    }
    q->tail = newt;
    q->size++;
    return true;
}

:::danger
這邊其實有點小 bug，參見 [執行自動評分](##執行自動評分)
:::
前面到字串複製的部分都大同小異，唯一要注意的是仍舊需檢查 `q` 是否為空佇列：
- `q` 原本為空佇列，我們還需要設定 `q->head` 為 `newh`，而且不能設定 `q->tail->next` ！（因為 `q->tail` 為 `NULL`）
- `q` 非空佇列，不用改動 `q->head`

最後再增加 `q->size` 即可。

### `q_remove_head()`

原本的實作真的單純只有移除 `head`：

/*
  Attempt to remove element from head of queue.
  Return true if successful.
  Return false if queue is NULL or empty.
  If sp is non-NULL and an element is removed, copy the removed string to *sp
  (up to a maximum of bufsize-1 characters, plus a null terminator.)
  The space used by the list element and the string should be freed.
*/
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    q->head = q->head->next;
    return true;
}

很明顯的沒有那麼單純，而且我們還沒有複製字串呢。

加入對 q 的檢查以 return 正確的結果，並且將字串 copy 到 `sp` 中，最後再 free 掉需要 remove 的元素：

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if ((!q) || q_is_empty(q)) {
        return false;
    }
    list_ele_t *old_head = q->head;
    q->head = q->head->next;
    if (!!sp && bufsize > 0) {
        memcpy(sp, old_head->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    free(old_head->value);
    free(old_head);
    q->size--;
    return true;
}

要注意我們還需要檢查 `bufsize` 是否 > 0，不然會出錯。還要記得在最後一個 byte 手動補上 `'\0'` ，不然原本的字串比 `bufsize` 長的話，可能會導致存取越界造成 Segmentaion fault。
:::success
然而其實這邊還是有機會造成 Segmentaion fault 的，寫在 [評分不夠完整](##評分不夠完整)。
:::

### `q_size()`

很簡單，只要 q 不是 NULL 就直接回傳 `q->size` 就好：

/*
  Return number of elements in queue.
  Return 0 if q is NULL or empty
 */
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) {
        return 0;
    }
    return q->size;
}

### `q_reverse()`

反轉其實不用多想，我們只要將整個 queue 遍歷過一遍，過程中記得將前一個元素以及目前的元素紀錄下來，再將目前元素的 `next` 更改連結到前一個元素即可，最後記得也要交換 `q->head` 以及 `q->tail`：

/*
  Reverse elements in queue
  No effect if q is NULL or empty
  This function should not allocate or free any list elements
  (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
  It should rearrange the existing ones.
 */
void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if ((!q) || q_is_empty(q)) {
        return;
    }
    list_ele_t *prev = NULL;
    list_ele_t *tmp = NULL;
    list_ele_t *current = q->head;
    while (current) {
        tmp = current->next;
        current->next = prev;
        prev = current;
        current = tmp;
    }
    tmp = q->tail;
    q->tail = q->head;
    q->head = tmp;
}

## 執行自動評分

好了，一切看起來都很美好，但是執行起來不是這麼回事：

---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---	trace-01-ops	6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
---	trace-02-ops	6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
---	trace-03-ops	6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, and size
---	trace-04-ops	6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head reverse, and size
---	trace-05-ops	6/6
+++ TESTING trace trace-06-string:
# Test of truncated strings
---	trace-06-string	7/7
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
---	trace-07-robust	7/7
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---	trace-08-robust	7/7
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---	trace-09-robust	7/7
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
---	trace-10-malloc	7/7
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
ERROR: Freed queue, but 4 blocks are still allocated
---	trace-11-malloc	0/7
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
ERROR: Freed queue, but 3 blocks are still allocated
---	trace-12-malloc	0/7
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
---	trace-13-perf	7/7
+++ TESTING trace trace-14-perf:
# Test performance of size
---	trace-14-perf	7/7
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, and reverse
---	trace-15-perf	7/7
---	TOTAL		86/100

是的，沒想到在測試 malloc_failure 的時候 (第11, 12個 script) 都出了問題。

該來看看 malloc_failure 是怎麼模擬的了，首先我們直接來看看在資料夾內搜尋 `malloc` 看看會調用什麼？

在 `harness.h` 內我們找到了以下代換：

/* Tested program use our versions of malloc and free */
#define malloc test_malloc
#define free test_free
#define strdup test_strdup

因此我們所呼叫的 `malloc` 都會被代換成 `test_malloc`，從 [afcidk同學的開發紀錄](https://hackmd.io/@afcidk/ry4VZS9SN?type=view) 可以發現這是名為 `function hooking` 的技巧。之前在嵌入式系統上開發時（比如說 STM32、ARC等等），原廠所提供的 SDK 好像也有這種類似的技巧，讓我們可以用 `my_alloc` 、 `my_free` 或者是 `my_printf` 這種方式來呼叫我們自己修改過後的函數。
:::success
其實我記憶有點模糊不太確定是不是這樣，去翻以前的專案結果一時翻不到，待查證。
:::
:::info
是說我發現我自己也常常用的 `calloc` 被漏掉了，~~這樣可以鑽漏洞~~，應該要修改一下才對。
:::

觀察 `test_alloc` 裏面到底在賣什麼關子：

void *test_malloc(size_t size)
{
    if (noallocate_mode) {
        report_event(MSG_FATAL, "Calls to malloc disallowed");
        return NULL;
    }
    if (fail_allocation()) {
        report_event(MSG_WARN, "Malloc returning NULL");
        return NULL;
    }
    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;
}

看起來 malloc_failure 是來測試如果突然的錯誤回傳 `NULL` ，程式會怎麼回應，很顯然的我剛剛撰寫的程式並沒有完全解決這個問題。

### 直接執行第 11 個腳本

直接執行看看會怎樣：

$ ./qtest -f traces/trace-11-malloc.cmd

cmd># Test of malloc failure on insert_head
cmd>option fail 30
cmd>option malloc 0
cmd>new
q = []
cmd>option malloc 25
cmd>ih gerbil 20
WARNING: Malloc returning NULL
Insertion of gerbil failed
WARNING: Malloc returning NULL
Insertion of gerbil failed
WARNING: Malloc returning NULL
Insertion of gerbil failed
WARNING: Malloc returning NULL
Insertion of gerbil failed
WARNING: Malloc returning NULL
Insertion of gerbil failed
WARNING: Malloc returning NULL
Insertion of gerbil failed
WARNING: Malloc returning NULL
Insertion of gerbil failed
WARNING: Malloc returning NULL
Insertion of gerbil failed
WARNING: Malloc returning NULL
Insertion of gerbil failed
q = [gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil]
cmd>
cmd>
cmd>
Freeing queue
ERROR: Freed queue, but 4 blocks are still allocated

看起來其實是 free 的錯誤而不是 insert 的錯誤，沒有完全的 free 乾淨。

### 天真地用 `printf` 抓錯

為了了解到底是哪裡出問題，我在 `test_free` 、 `test_alloc` 把 `allocated_count` 印出來，並且在 insert 、 free 成功時將字串印出，總算是找到問題點了。
:::success
用 gdb 抓錯或許會更快
:::

理論上每次 insert 成功的話應該要有兩次 alloc ，但是有時候只有一次，這就代表了 `newh`、`newt` alloc 成功，可是在 alloc 字串時失敗了！而且我在 alloc 字串失敗時，並沒有將剛剛 alloc 成功的 `newh`、`newt` free 掉，因此造成了 memory leak。

稍微修改一下便能解決這個問題：

bool q_insert_head(queue_t *q, char *s)
{
    if (!q) {
        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;
    }
    // Alloc for string
    size_t len = (strlen(s) + 1);
    newh->value = malloc(len);
    if (!(newh->value)) {
        free(newh);
        return false;
    }
    memcpy(newh->value, s, len);
    // Insert to head
    newh->next = q->head;
    // If the queue was empty, we need to revise tail too
    if (q_is_empty(q)) {
        q->tail = newh;
    }
    q->head = newh;
    q->size++;
    return true;
}


/*
  Attempt to insert element at tail of queue.
  Return true if successful.
  Return false if q is NULL or could not allocate space.
  Argument s points to the string to be stored.
  The function must explicitly allocate space and copy the string into it.
 */
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) {
        return false;
    }
    list_ele_t *newt;
    newt = malloc(sizeof(list_ele_t));
    if (!newt) {
        return false;
    }
    // Alloc for string
    size_t len = (strlen(s) + 1);
    newt->value = malloc(len);
    if (!(newt->value)) {
        free(newt);
        return false;
    }
    memcpy(newt->value, s, len);
    // Insert to tail
    newt->next = NULL;
    // If the queue was empty, we need to revise head too
    // And also we only need to revise tail->next if q was not empty
    if (q_is_empty(q)) {
        q->head = newt;
    } else {
        q->tail->next = newt;
    }
    q->tail = newt;
    q->size++;
    return true;
}

在第 80 行與 118 行補上 free ，問題解決。

重新測試一次，果然功德圓滿，100 分結束。

### 評分不夠完整
功德圓滿才怪，後來檢查才發現 `q_remove_head()` 忘記了如果刪除完最後變空的， `q->tail` 也要指回 `NULL` 才行。看來這個測試沒有完整含括到所有情況。

## `MAGICHEADER` 、 `MAGICFOOTER` 、 `MAGICFREE` 以及 `FILLCHAR` 的運用

在`harness.c` 中，可以發現到 `MAGICHEADER` 、 `MAGICFOOTER` 、 `MAGICFREE` 以及 `FILLCHAR` 這幾個巨集的應用，主要與自訂的 memory block 型態一同使用：

/** Special values **/

/* Value at start of every allocated block */
#define MAGICHEADER 0xdeadbeef
/* Value when deallocate block */
#define MAGICFREE 0xffffffff
/* Value at end of every block */
#define MAGICFOOTER 0xbeefdead
/* Byte to fill newly malloced space with */
#define FILLCHAR 0x55

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;

它採用了 Doubly-Linked List 的架構管理 memory block，可以方便地找到所有目前已 allocated 的 block，還有一個 `magic_header` 欄位拿來存放 `MAGICHEADER` ，可以在 `test_malloc` 發現它的存在：

void *test_malloc(size_t size)
{
    if (noallocate_mode) {
        report_event(MSG_FATAL, "Calls to malloc disallowed");
        return NULL;
    }
    if (fail_allocation()) {
        report_event(MSG_WARN, "Malloc returning NULL");
        return NULL;
    }
    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;
}

第 136 行將 `MAGICHEADER` 指給 `magic_header`，目的應該是為了標定我們所提供的指標真的是由 `test_malloc` 所 alloc 出來的 memory，我想同時也能檢查有沒有簡單的存取越界問題。如果在檢查 `magic_header` 的內容時發現內容並不是 `MAGICHEADER`，那麼不是我們所給的指標並不是 allocated 出來的 memory，就是我們不小心改到不合法位址造成 memory block 損壞了。

`MAGICFOOTER` 應該也是同理，用來檢測 memory block 是否為 allocated 或者損毀。
:::info
不過這裡決定 footer 的方式是先將 `block_ele_t *` 轉成 `size_t` 之後再與其他 size 做相加，最後再轉回 `size_t *` ，不知道這麼做的用意為何？
:::

`FILLCHAR` 在第 140 行出現，我們以該值 `0x55` 填滿整個 memory block 的 payload 部分。我們知道 $55_{16} = 01010101_{2}$，我認為這是特別將 memory 的每個 byte 都設成 1 ，來考驗大家會不會記得在 `q_remove_head` 複製字串的時候，要記得把最後一個 byte 設成 `'\0'` 。
:::info
但是我認為他在 `test_free` 中有點多餘，

    b->magic_header = MAGICFREE;
    *find_footer(b) = MAGICFREE;
    memset(p, FILLCHAR, b->payload_size);

有一種可能性是重新清空以避免意外調用然後發現資料還能使用，保障資料安全問題...，好吧這麼說來好像有一點用。
:::

`MAGICFREE`，顧名思義只出現在 `test_free` 中：

void test_free(void *p)
{
    if (noallocate_mode) {
        report_event(MSG_FATAL, "Calls to free disallowed");
        return;
    }
    if (p == NULL) {
        return;
    }
    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;
    memset(p, FILLCHAR, b->payload_size);

    /* Unlink from list */
    block_ele_t *bn = b->next;
    block_ele_t *bp = b->prev;
    if (bp)
        bp->next = bn;
    else
        allocated = bn;
    if (bn)
        bn->prev = bp;

    free(b);
    allocated_count--;
}

我猜測可能是故意先用此值將 `magic_header` 以及 `footer` 改掉，避免我們之後不小心把已經 free 掉的 block 的指標傳進去的時候，在對應 `magic_header` 位址的部分剛好殘餘舊值，導致程式誤會成這是還沒被 `free` 掉的 block。

## Reference
- [afcidk同學的開發紀錄](https://hackmd.io/@afcidk/ry4VZS9SN?type=view)