# 2018q3 Homework2 (lab0)

contributed by < `kevin110604` >
>記得補上實驗環境
>[name=課程助教][color=red]
>

>好的
>[name=kevic110604][color=green]
>

###### tags: `2018q3`

## 開發過程

### q_new()

* `malloc` 空間給 `queue_t *q` 。

### q_insert_head()

* 這邊我原本忘了考慮到如果第二次 `malloc()` 失敗，要記得把第一次 `malloc()` 的空間先 `free()` 再 `return` 。
* 在分配記憶體給字串的時候要記得多保留 1 bit 給 `\0` 的空間。

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    
    if (q == NULL)
        return false;
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;
    
    newh->value = malloc(strlen(s) + 1);   // watch out!!!
    if (newh->value == NULL) {
        free(newh);                        // watch out!!!
        return false;
    }
    ...
}

### q_remove_head()

* 這邊經朋友提醒 `strncpy()` 前要先檢查 `sp` 是否不為 `NULL` 。
* 同樣地要預留一個空間給 `\0` ，並在 `strncpy()` 之後自己在結尾補上 `\0`。

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
 {
     /* You need to fix up this code. */
     if (q == NULL || q->head == NULL)
         return false;
     if (sp != NULL) {             // watch out!!!
         strncpy(sp, q->head->value, bufsize - 1);
         sp[bufsize - 1] = '\0';   // watch out!!!
    }
    ...
}

### q_free()

* 在 free 掉每一個 node 之前，要先 free 裡面儲存字串的空間。

### q_insert_tail()

* 為了因應要求 operate in O(1) time ，所以修改了 structure:

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail; /* 新增 tail 指標指向尾巴的節點 */
    int size;
} queue_t;

### q_size()

* 同樣為了因應要求 operate in O(1) time ，所以修改了 structure:

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail; /* 新增 tail 指標指向尾巴的節點 */
    int size;         /* 隨時記錄現在有幾個節點 */
} queue_t;

### q_reverse()

* 這邊我用 for loop ，從頭 traverse linked list 每一個 element 的方式去完成。

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

當我們 `make test` 的時候，會執行 scripts/driver.py 這支程式，而由 `class Tracer` 裡面的 `runTrace()` 這個函式，可以發現：

    def runTrace(self, tid):
        if not tid in self.traceDict:
            print "ERROR: No trace with id %d" % tid
            return False
        fname = "%s/%s.cmd" % (self.traceDirectory, self.traceDict[tid])
        vname = "%d" % self.verbLevel
        clist = [self.qtest, "-v", vname, "-f", fname]
        try:
            retcode = subprocess.call(clist)  # 執行 qtest
        except Exception as e:
            print "Call of '%s' failed: %s" % (" ".join(clist), e)
            return False
        return retcode == 0

在第68行， driver.py 去 run qtest 。而在 `class Tracer` 裡面的 `run()` 裡可以看到評分的過程：

        score = 0
        maxscore = 0
        for t in tidList:
            tname = self.traceDict[t]
            if self.verbLevel > 0:
                print "+++ TESTING trace %s:" % tname
            ok = self.runTrace(t)
            maxval = self.maxScores[t]
            tval = maxval if ok else 0  # 檢查有無發生意外
            print "---\t%s\t%d/%d" % (tname, tval, maxval)
            score += tval      # 計算分數
            maxscore += maxval
            scoreDict[t] = tval
        print "---\tTOTAL\t\t%d/%d" % (score, maxscore)

測資是來自 traces/ 裡的15個檔案。每一個測資都有個別的分數，執行結果正確並且沒有發生 exception 就可以拿到分數。

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

觀察 `qtest.c` 裡的 `main()`

int main(int argc, char *argv[])
{
    /* To hold input file name */
    char buf[BUFSIZE];
    char *infile_name = NULL;
    char lbuf[BUFSIZE];
    char *logfile_name = NULL;
    int level = 4;
    int c;

    while ((c = getopt(argc, argv, "hv:f:l:")) != -1) {
        switch (c) {
        case 'h':
            usage(argv[0]);
            break;
        case 'f':
            strncpy(buf, optarg, BUFSIZE);
            buf[BUFSIZE - 1] = '\0';
            infile_name = buf;
            break;
        case 'v':
            level = atoi(optarg);
            break;
        case 'l':
            strncpy(lbuf, optarg, BUFSIZE);
            buf[BUFSIZE - 1] = '\0';
            logfile_name = lbuf;
            break;
        default:
            printf("Unknown option '%c'\n", c);
            usage(argv[0]);
            break;
        }
    }
    queue_init();
    init_cmd();
    console_init();
    set_verblevel(level);
    if (level > 1) {
        set_echo(true);
    }
    if (logfile_name)
        set_logfile(logfile_name);
    add_quit_helper(queue_quit);
    bool ok = true;
    ok = ok && run_console(infile_name);
    ok = ok && finish_cmd();
    return ok ? 0 : 1;
}

前面大致上是一些初始化的設定，直到573行的 `run_console(infile_name);` 才是真正開始執行整個 console 的地方。值得注意的是從 `console.c` 和 `console_init()`:

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)");
    ...
}

可以發現有使用到 GDB (GNU debugger) ，舉例來說，上面就利用 `add_cmd()` 來新增 `new`, `free`, `ih`, `it`...等指令，後面的 `do_new`, `do_free`, `do_insert_head`... 則是這些指令的函式實作，裡面會呼叫我們在 queue.c 裡寫的函式，例如 `q_new()`, `q_free()`, `q_insert_head()`...。

### harness.[ch]

以下內容是詢問朋友 `ChingChieh` 後才知道的。

在 harness.h 裡可以發現我們之前使用的 `malloc()`, `free()` 都是自己定義的

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

先看 `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;

然後再看到 `test_malloc()` ，可以在裡面發現真正使用 `malloc()` 的地方

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

也就是說，除了我們需要 allocate 的大小 `size` bits 之外，這個 pointer `new_block` 還包含了 `sizeof(block_ele_t)` bits 的空間和 `sizeof(size_t)` bits 的空間。
而 `test_malloc()` 最後 return 的 `p` 實際上是

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

也就是我們 return 的 pointer `p` 指向的是 `new_block->payload` 之後的空間。
綜合以上幾點的觀察，我們可以推測 `new_block` 的空間分配情形如下圖

digraph graphname{

    node[shape=record]


    memory[label="struct block_ele_t| size bits|size_t"]
}

又 `test_malloc()` 裡面有這段 code

    new_block->magic_header = MAGICHEADER;
    new_block->payload_size = size;
    *find_footer(new_block) = MAGICFOOTER;

然後 `find_footer()` 回傳的是那個我們在 queue.c malloc 的那段空間的尾巴

/* Given pointer to block, find its footer */
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;
}

也就是說我們在 queue.c malloc 的那段空間的頭 `new_block->magic_header` 和我們在 queue.c malloc 的那段空間的尾巴 `*find_footer(new_block)` 都被assign 成某個特定的值，所以我們可以透過檢查這些值來偵測是否有不合法的空間存取。例如在 `test_free()` 裡：

if (footer != MAGICFOOTER) {
    ...
    error_occurred = true;
}

## 實驗環境

$ cat /etc/os-release 
NAME="Ubuntu"
VERSION="18.04.1 LTS (Bionic Beaver)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 18.04.1 LTS"
VERSION_ID="18.04"
HOME_URL="https://www.ubuntu.com/"
SUPPORT_URL="https://help.ubuntu.com/"
BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/"
PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy"
VERSION_CODENAME=bionic
UBUNTU_CODENAME=bionic

$ cat /proc/version
Linux version 4.15.0-34-generic (buildd@lgw01-amd64-047) (gcc version 7.3.0 (Ubuntu 7.3.0-16ubuntu3)) #37-Ubuntu SMP Mon Aug 27 15:21:48 UTC 2018