# 2018q3 Homework2 (lab0)
contributed by < `siahuat0727` >
>請補上實驗環境
>[name=課程助教][color=red]

[作業說明](https://hackmd.io/s/BJp_jq-tm)

## 環境

$ uname -a
Linux siahuat0727 4.15.0-34-generic #37-Ubuntu SMP Mon Aug 27 15:21:48 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.3.0-16ubuntu3) 7.3.0

## 過程記錄

#### queue 及 list element 的資料結構

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

typedef struct ELE {
    char *value;
    struct ELE *next;
} list_ele_t;

#### q_free

void q_free(queue_t *q)
{
    if (q == NULL)
        return;

    /* How about freeing the list elements and the strings? */
    while (q->size)
        q_remove_head(q, NULL, 0);

    /* Free queue structure */
    free(q);
}

利用已寫好的 `q_remove_head` 完成 `q_free` 的要求，減少不必要的錯誤。
第 7 行處一開始爲 `while (q->head)` ，在實作 `size` 之後改爲現在的樣子，提高可讀性。

---

#### q_insert_tail

bool q_insert_tail(queue_t *q, char *s)
{
    /* Remember: It should operate in O(1) time */
    if (q == NULL)
        return false;

    list_ele_t *newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;

    /* Don't forget to allocate space for the string and copy it */
    newh->value = strdup(s);
    if (newh->value == NULL) {
        free(newh);
        return false;
    }

    /* Insert element and update queue structure*/
    if (q->size++)
        q->tail->next = newh;
    else
        q->head = newh;
    newh->next = NULL;
    q->tail = newh;

    return true;
}

過程中第 26 行 `newh->next = NULL` 忘了賦值間接造成測 `q_reverse` 時（Test 4）出錯。（無法判斷結束）

---

#### 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;

    /* Copy removed string */
    if (sp) {
        strncpy(sp, q->head->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    /* Remove element and update queue structure */
    list_ele_t *tmp = q->head;
    q->head = q->head->next;
    // free(tmp->value);
    free(tmp);
    if (--(q->size) == 0)
        q->tail = NULL;

    return true;
}

第 10 行存在原因
> strncpy 的 man page description 中：
Warning: If there is no null byte among the first n bytes of src, the string placed in dest will not be null-terminated.

發現要 `free(tmp->value)` 時會出錯，閱讀其他人的開發記錄發現大家都遇到同樣的問題，其中 `pjchiou` 同學有發現 `harness.h` 中有一段 `#define free test_free`，具體原因需要再研究。

> 是 strdup 惹的禍，因為 harness.h 有段 macro 會把 free 換成一個自己開發的函式，導致你用不到真正的 free ，變成在用 malloc 與 test_free ，因此直接用 malloc 讓 preprocessor 把它也轉成 test_malloc 就好了。
> [name=pjchiou] [time=2018 Sep 27 Thu 06:08]
>
> 感謝 `pjchiou` 同學的留言，已將 `strdup` 改爲 `malloc` 並把創建 list element 獨立出來避免 WET (write everything twice)。[git commit](https://github.com/siahuat0727/lab0-c/commit/1294f71886ce17b83c83fdd7674f7c3909a5f932)
> [name=siahuat0727] [time=Thu, Sep 27, 2018 12:47 PM]

---

#### q_reverse

void q_reverse(queue_t *q)
{
    if (q == NULL || q->size == 0)
        return;

    q->tail = q->head;
    while (q->tail->next) {
        list_ele_t *e = q->tail->next;
        q->tail->next = e->next;
        e->next = q->head;
        q->head = e;
    }
}

利用 `q->head` 和 `q->tail` 指向已 reverse 的 subqueue，`list_ele_t *e` 指向待 reverse 的 subqueue 的起始 element。

---

#### 較符合作業要求的 q_insert_head 和 q_insert_tail

*若使用 `strdup`， 系統沒辦法偵測是否發生 memory leak 及 memory allocation 失敗的情況，詳見[了解自動評分系統](#了解自動評分系統)。*

list_ele_t *ele_create(char *s)
{
    list_ele_t *newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return NULL;

    newh->value = malloc(strlen(s) + 1);

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

    strcpy(newh->value, s);
    newh->next = NULL;

    return newh;
}

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

    /* Create list element */
    list_ele_t *newh = ele_create(s);
    if (newh == NULL)
        return false;

    /* Insert element and update queue structure*/
    newh->next = q->head;
    q->head = newh;
    if (q->size++ == 0)
        q->tail = newh;

    return true;
}

bool q_insert_tail(queue_t *q, char *s)
{
    /* Remember: It should operate in O(1) time */
    if (q == NULL)
        return false;

    /* Create list element */
    list_ele_t *newh = ele_create(s);
    if (newh == NULL)
        return false;

    /* Insert element and update queue structure*/
    if (q->size++)
        q->tail->next = newh;
    else
        q->head = newh;
    q->tail = newh;

    return true;
}

---

## 了解自動評分系統

### 如何偵測 memory leak 和 double free 等問題？

harness.h 中有一段：

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

也就是我們在 queue.c 裡呼叫 `malloc` 和 `free` 都會被取代爲 `test_malloc` 和 `test_free`，後者會建立一個 doubly-linked list 來保存我們每次 `malloc` 和 `free` 的資訊，其資料結構如下：

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;

這裡 `payload` 用到 [Arrays of Length Zero](https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html) 的技巧，其中 `payload` 只在其他處出現過一次：

void *test_malloc(size_t size)
{
    ...
    block_ele_t *new_block =
        malloc(size + sizeof(block_ele_t) + sizeof(size_t));
    ...
    void *p = (void *) &new_block->payload // here
    ...
    return p;
}

不用 `payload` 也可以達到同樣的效果，其在**此處**等價如下，只是可讀性較差。

void *p = (void *) ((char *)new_block + sizeof(block_ele_t));

爲什麼不寫 `(void *)new_block + sizeof(block_ele_t)` ？
[Arithmetic on a void* is illegal in C](https://stackoverflow.com/questions/3523145/pointer-arithmetic-for-void-pointer-in-c), it's [GCC extension](https://gcc.gnu.org/onlinedocs/gcc-4.8.0/gcc/Pointer-Arith.html).

強調在**此處**是因爲這跟 alignment 有密切關係，假設今天 block_ele_t 改爲這樣：

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

那麼在有 alignment 且不改動其他程式碼的情況下就只有第二種方式可以執行成功了，原因是 `new_block` 在賦值時是這樣的：

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

這裡的設計是把所需的 `size` 接在 `sizeof(block_ele_t)` 後面使用，而 `block_ele_t` 在有 alignment 時會在 structure 最後進行 padding，但 `payload` 是緊接在 `char dummy` 之後的。

#### Alignment of arrays of length zero in structure

[Arrays of Length Zero](https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html) 中有一句話：

>The offset of a zero-length array member from the beginning of the enclosing structure is the same as the offset of an array with one or more elements of the same type. The alignment of a zero-length array is the same as the alignment of its elements.

看了好久看不懂，還找 `aben20807` 同學討論，最後終於搞懂了。
簡單來說，要計算 array of length zero 在 structure 中的位移，就是把它改成 array with one element 後的計算方法一樣：

#include <stdio.h>
                 
struct Foo {
    double d;  
    char c;   
    char arr_c[0];
    int arr_i[0];
    double arr_d[0];
};           

    struct Foo foo;  
    printf("%ld\n", (char *)foo.arr_c - (char *)&foo);
    printf("%ld\n", (char *)foo.arr_i - (char *)&foo);
    printf("%ld\n", (char *)foo.arr_d - (char *)&foo);
    return 0;  
}  

Output：

9
12
16

Arrays with length zero 通常是作爲整個 structure 的最後一個 member，這裡只是方便理解內容。

### Header and Footer

再看這段程式碼：

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

最後的 `sizeof(size_t)` 用來存某些特定的值（作者稱之爲 Special values），被安排在 `size` 的後面（整個可用空間的最後面，footer），也就是過程中哪怕只有 1 byte 的 buffer overflow 都可以在 `test_free` 時被測出來。
而 structure member `size_t magic_header` 用法也相同，可以檢查是否爲 unallocated memory 或被不合法的修改。

另外，一開始也好奇爲什麼 `test_malloc` 裡呼叫的 `malloc` 不會轉成 `test_malloc` ？
原因如下， harness.c：

#define INTERNAL 1
#include "harness.h"

先 `#define INTERNAL`，就不會 include 將 `malloc` 和 `free` 轉換的 macro 了。
[點此往上查看 harness.h 大致內容](#如何偵測-memory-leak-和-double-free-等問題？)

### 依據輸入指令執行對應的操作

指令的**第一個參數**（如 `ih some_string` 的 `ih`）對應個別 function，並用如下資料結構以 linked list 串接：

typedef struct CELE cmd_ele, *cmd_ptr;
struct CELE {
    char *name;
    cmd_function operation;
    char *documentation;
    cmd_ptr next;
};

每個指令會先經過 `char **parse_args(char *line, int *argcp)`
轉爲 `argc` 和 `argv` 的形式，統一對應 function 的 prototype：

typedef bool (*cmd_function)(int argc, char *argv[]);

### 利用 sigsetjmp 和 siglongjmp 模擬 try and catch 的效果

[C 語言 setjmp 與 longjmp 函數用法教學](https://blog.gtwang.org/programming/c-setjmp-longjmp-function-tutorial/)

if (exception_setup(true)) {
    ...
}
exception_cancel();

在 if-block 裡面觸發 signal 時，會由 signal handler 執行對應的指令後跳出 if-block。

`exception_setup`：通過 `sigsetjmp` 設定目標位置。若觸發 signal ，最後會透過 `siglongjmp` 跳回目標位置，又因爲 `exception_setup` 那時將 `return false` 而跳出 if-block。

`exception_cancel`：作用是限制異常處理的範圍，在 `exception_setup` 與 `exception_cancel` 之外的地方若觸發 signal 將導致程式強制結束。

### Variable arguments + `vprintf`

#### Variable arguments

report.c 中用了很多這技巧，如：
`void report(int level, char *fmt, ...)`
`void report_noreturn(int level, char *fmt, ...)`

#### vprintf
`int vprintf(const char *format, va_list ap);`
>equivalent to the functions printf() except that it is called with a va_list instead of a variable number of arguments. -- 截取自 man page （小改動）

兩者結合，以下 `my_printf` 與 `printf` 等價：

int my_printf(char *fmt, ...)
{
    va_list ap;
    va_start(ap, fmt);
    int ret = vprintf(fmt, ap);
    va_end(ap);
    return ret;
}