# 2019q3 Homework2 (lab0)
contributed by < `shaojason999` >
###### tags: `sysprog2019`
[lab0 說明](https://hackmd.io/3AXCGEi6R6eh7zsnMicqQA?view)
[原作業檔案 (C Programming Lab)](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
[我的 github](https://github.com/shaojason999/lab0-c)

## 前置作業
1. 先 fork [lab0](https://github.com/sysprog21/lab0-c) 到自己的 github
2. git clone 到自己的作業環境中
`$ git clone https://github.com/shaojason999/lab0-c`
3. 安裝 cppcheck, clang-format
`$ sudo apt install build-essential git-core cppcheck clang-format`
4. 安裝 valgrind 分析工具
`$ sudo apt install valgrind`
5. 開始寫程式。寫完程式後記得要符合格式
`$ clang-format -i queue.c`

## queue.c 程式碼解析

### queue.h
因為作業特別要求 insert tail, size of list 這兩個操作都需要是 $O(1)$ 常數時間，因此我們需要==利用空間來換取時間==
* 改變 struct queue_t 結構
* 增加變數 tail
* 增加計數器 count

typedef struct {
    list_ele_t *head;
    list_ele_t *tail;
    int count;
} queue_t;

### q_new: 初始化
* head, tail 記得設為 NULL

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

### 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 */
    if (!q)
        return;
    list_ele_t *temp, *temp_next;
    temp = q->head;

    while (temp) {
        temp_next = temp->next;
        free(temp->value);
        free(temp);
        temp = temp_next;
    }

    free(q);
}

### q_insert_head: 插入在list的頭部
需要注意三點 :
1. 若 newh->value 沒有成功 malloc，return false 前需要 free newh，否則會 memory leak
2. malloc, memset 的參數要注意，詳細我打在最下面的 [Note ](https://hackmd.io/C1CCk2VBQOaEG_e8Le4KJA#Note)
3. 如果本來 queue 是 empty，則插入時須特別處理

bool q_insert_head(queue_t *q, char *s)
{
    if (!q)
        return false;
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
        
    newh->value = malloc(sizeof(char) * strlen(s) + 1);
    if (!(newh->value)) {
        free(newh);
        return false;
    }
    
    memset(newh->value, 0, sizeof(char) * strlen(s) + 1);
    strcpy(newh->value, s);

    if (!(q->head)) {  // empty queue
        q->head = newh;
        q->tail = newh;
        newh->next = NULL;
    } else {
        newh->next = q->head;
        q->head = newh;
    }
    ++(q->count);
    return true;
}

### q_insert_tail: 插入在尾部
注意事項跟 q_insert_head 一樣

bool q_insert_tail(queue_t *q, char *s)
{
    if (!q)
        return false;
    list_ele_t *newt;
    newt = malloc(sizeof(list_ele_t));
    if (!newt)
        return false;
        
    newt->value = malloc(sizeof(char) * strlen(s) + 1);
    if (!(newt->value)) {
        free(newt);
        return false;
    }
    
    memset(newt->value, 0, sizeof(char) * strlen(s) + 1);
    strcpy(newt->value, s);

    if (!(q->head)) {  // empty queue
        q->head = newt;
        q->tail = newt;
    } else {
        q->tail->next = newt;
        q->tail = newt;
    }
    newt->next = NULL;
    ++(q->count);

    return true;
}

### q_remove_head: 從頭部 free(element)
1. 兩種情況無法 free
* q is NULL or empty
2. 記得用 memset 把 sp 清空，或是在 strncpy 之後 `sp[bufsize-1] = '\0';`。這樣 sp 才知道字串到哪結束
3. 若 queue 又變回 empty，記得要 `q->head = NULL, q->tail = NULL;`

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !(q->head))
        return false;

    list_ele_t *temp;

    if (sp) {
        memset(sp, 0, bufsize);
        strncpy(sp, q->head->value, bufsize - 1);
    }

    free(q->head->value);
    temp = q->head;
    q->head = q->head->next;
    free(temp);
    --(q->count);
    if (q->count == 0)
        q->tail = NULL;
    return true;
}

### q_size: 利用 $O(1)$ 從 q->count 取得 size

int q_size(queue_t *q)
{
    if (!q || !(q->head))
        return 0;
    else
        return q->count;
}

### q_reverse: 整個 list 反轉
我利用三個變數 temp1, temp2, temp3 代表三個相鄰的 nodes
1. 每次迭代中把 temp2->next 指向 temp1，然後三個 nodes 都往前邁進一個 node
2. 結束後要記得更新 `q->tail, q->tail->next, q->head`

void q_reverse(queue_t *q)
{
    if (!q || !(q->head))
        return;

    list_ele_t *temp1, *temp2, *temp3;

    temp1 = q->head;
    temp2 = q->head->next;

    while (temp2) {
        temp3 = temp2->next;
        temp2->next = temp1;

        temp1 = temp2;
        temp2 = temp3;
    }

    q->tail = q->head;
    q->tail->next = NULL;
    q->head = temp1;
}

## 自動評分系統運作原理
首先看 Makefile 裡的程式碼

test: qtest scripts/driver.py
        scripts/driver.py

因此我們來看看 `scripts/driver.py` 裡面寫些甚麼
### 讀取參數
`optlist, args = getopt.getopt(args, 'hp:t:v:A', ['valgrind'])`
* 只接收五種短參數(-) : -h, -p -t -v -A，其中因為 ptv後面都有冒號，表示有附加參數
* 只接受一種長參數(--) : valgrind，且不代附加參數(['valgrind='] 這樣寫的話才有附加參數)
* 舉例: 在 Makefile 裡有一句 `scripts/driver.py -p $(patched_file) --valgrind`
* optlist 為分析出的參數，args 為不屬於以上的參數
### 如何跑測資?
1. 先在 run() 裡利用 for loop 讓所有測試目標 `t in tidList` 執行 runTrace()

    for t in tidList:
        ...
        ok = self.runTrace(t)
        ...

2. 接著在 runTrace() 裡利用這兩句指定目標檔案名以及 verblevel

    fname = "%s/%s.cmd" % (self.traceDirectory, self.traceDict[tid])
    vname = "%d" % self.verbLevel

其中 `self.traceDirectory = "./traces"`
`self.traceDict[1] = "trace-01-ops", elf.traceDict[2] = "trace-02-ops", ...`
3. 利用 list 把等等要執行的完整指令存起來

    clist = [self.command, self.qtest, "-v", vname, "-f", fname]

其中 `self.command` 預設為 `./qtest`，`self.qtest` 預設為 `''`
4. 利用 [subprocess](https://hackmd.io/C1CCk2VBQOaEG_e8Le4KJA?both#subprocess-%E5%9F%B7%E8%A1%8C%E5%A4%96%E9%83%A8%E7%9A%84%E5%91%BD%E4%BB%A4%E5%92%8C%E7%A8%8B%E5%BA%8F) 執行指令。若執行正常，回傳值為 0

    retcode = subprocess.call(clist)

5. 之後就是簡單的分數計算了

### subprocess
執行外部的命令和程序
[參考資料](https://www.cnblogs.com/vamei/archive/2012/09/23/2698014.html)
1. 功能和 shell 類似
2. 在 python 中利用 subprocess 來 fork 一個子進程，運行外部的程序
3. 在我們的例子中 `subprocess.call()` 父進程會等待子進程返回 exit code。實際例子像是這樣

    import subprocess
    rc = subprocess.call(["ls","-l"])

相較之下，subprocess.Popen() 具有更客制化的功能 (call() 是基於 Popen() 的包裝)

4. subprocess.Popen() 父進程不會等子進程完成

    import subprocess
    child = subprocess.Popen(["ping","-c","5","www.google.com"])
    print("parent process")

* 這個例子中，ping 完成之前，父進程會先 print

利用 wait() 來等待

    import subprocess
    child = subprocess.Popen(["ping","-c","5","www.google.com"])
    child.wait()
    print("parent process")

5. 利用 subprocess.PIPE 來讓多個子進程之間可以彼此溝通(或是與父進程溝通)，比如說

    import subprocess
    child1 = subprocess.Popen(["ls","-l"], stdout=subprocess.PIPE)
    child2 = subprocess.Popen(["wc"], stdin=child1.stdout,stdout=subprocess.PIPE)
    out = child2.communicate()
    print(out)

* child1 把結果傳到緩衝區，child2 從緩衝區讀取
* child2 把結果傳到緩衝區，利用 communicate 讀取給父進程

或是像這個例子，利用 communicate() 傳文字給子進程

    import subprocess
    child = subprocess.Popen(["cat"], stdin=subprocess.PIPE)
    child.communicate("vamei")

:::info
[line 64 - line 66](https://github.com/shaojason999/lab0-c/blob/master/scripts/driver.py#L64) 是否為多餘的?
因為同樣的檢查在 [line 83 - line 85](https://github.com/shaojason999/lab0-c/blob/master/scripts/driver.py#L83) 已經先檢查過了

if not tid in self.traceDict:
    print("ERROR: Invalid trace ID %d" % tid)
    return

:::

:::danger
做過實驗和確認了嗎？若是，提交 pull request，程式碼就是給你「修改」用的，而非「舉燭」
:notes: jserv
:::

## qtest 行為與技巧分析
### 指令處理流程 : 以 new 舉例
1. 先在 console_init() 設定輸入為 `new` 時處理的 function 為誰

    add_cmd("new", do_new, "                | Create new queue");

2. 接著在 do_new() 呼叫寫在 queue.c 裡面的 function

    q = q_new();

### signal 的處理
在一開始的 queue_init() 可以看到 signal 的處理，那讓我們在底下一一解釋

static void queue_init()
{
    fail_count = 0;
    q = NULL;
    signal(SIGSEGV, sigsegvhandler);
    signal(SIGALRM, sigalrmhandler);
}

第5行是在處理當 program 嘗試讀或寫某個超出範圍的記憶體位置
* SIGSEGV(Signal Segmentation Violation): Invalid access to storage: When a program tries to read or write outside the memory it is allocated for it.

第6行是在設定定時器，避免程式進入無限等待(無限輪迴)
* 每個進程都有唯一的一個定時器，以秒為單位
* alarm(5); 表示計時5秒後觸發 SIGALRM signal，接著就會執行上面設定好的 `sigalrmhandler()`
* alarm() 使用是放在 harness.c

void sigsegvhandler(int sig)
{
    trigger_exception(
        "Segmentation fault occurred.  You dereferenced a NULL or invalid "
        "pointer");
}
void sigalrmhandler(int sig)
{
    trigger_exception(
        "Time limit exceeded.  Either you are in an infinite loop, or your "
        "code is too inefficient");
}

## Valgrind 運作原理以及對此次作業的使用
Valgrind 模擬了 CPU 環境，並且維護暫存器和主記憶體各自的狀態維護一份，如此一來就可以在不影響程式的情況下輸出有用的訊息
* 架構圖

Valgrind 由核心和眾多工具組成，其中一個叫做 Memcheck，它擁有兩個表去紀錄
1. Valid-Value table，用一個 bit 去記錄這個 byte 是否有效、已經初始化
2. Valid-Address table，用一個 bit 去記錄這個 byte 是否可以備讀寫
3. 當要讀取某個 byte 時，Valgrind 就會從這兩個表去檢查，如果是無效的，則輸出錯誤報告

### [待補充]

#### 參考資料
1. [应用 Valgrind 发现 Linux 程序的内存问题](https://www.ibm.com/developerworks/cn/linux/l-cn-valgrind/index.html)
2. [Valgrind工作原理简介](https://blog.mengy.org/how-valgrind-work/)
3. [參考資料整理](https://www.cnblogs.com/sword03/p/9379605.html)

## dudect 以實驗分析時間複雜度
### [待補充]

## 留意`MAGICHEADER, MAGICFREE, MAGICFOOTER, FILLCHAR` 等巨集的使用，並探討其動機和用法
### [待補充]

## Note

1. 有一種情況是 list_ele_t \*newh 成功 malloc，但是 newh->value 失敗 malloc，這時不只要 return false，也需要 free(newh)

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

2. 當 queue 是 empty 時，q_insert_tail() 要小心不要出現以下程式碼

    q->tail->next = newt;

3. 這裡不是很懂[here](https://github.com/shaojason999/lab0-c/blob/master/qtest.c#L275)
4. sizeof() 包括 NULL character，strlen()不包括 NULL character(但包括 "\n")

    #include <stdio.h>
    #include <string.h>

    int main()
    {
        char a[]="aaa";
        printf("%ld %ld\n",sizeof(a),strlen(a));
    }

結果為 `4 3`

5. sizeof()使用在 char 時會有不同的行為

    #include <stdio.h>
    #include <string.h>

    int main()
    {
        char a[]="aaa";
        char b[10]="bbb";
        char *c=a;
        char *d="aaabbb";
        printf("%ld %ld %ld %ld\n",sizeof(a),sizeof(b),sizeof(c),sizeof(*d));
    }

結果為 `4 10 8 1`，特別要注意的是 `sizeof(a)` 跟 `sizeof(c)` 的結果不同。 `sizeof(c)` 的大小就只是一個 pointer 的大小而已(在 64-bit 系統下為 8 byte)
因此在 queue.c 裡面我要 malloc 空間給 string 時寫錯但一直找不到，因為我算成 `sizeof(char *)`

    newh->value = malloc(sizeof(char) * strlen(s) + 1);
    // 不要寫成 newh->value = malloc(sizeof(s));

6. 養成好習慣，每次 strcpy 或 strncpy 之前先清空

    memset(newh->value, 0, sizeof(char) * strlen(s) + 1);
    strcpy(newh->value, s);