# 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
```cpp
typedef struct {
list_ele_t *head;
list_ele_t *tail;
int count;
} queue_t;
```
### q_new: 初始化
* head, tail 記得設為 NULL
```cpp
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: 全部記憶體釋放
```cpp
/* 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，則插入時須特別處理
```cpp
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 一樣
```cpp
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;`
```cpp
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
```cpp
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`
```cpp
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 裡的程式碼
```shell
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()
```python
for t in tidList:
...
ok = self.runTrace(t)
...
```
2. 接著在 runTrace() 裡利用這兩句指定目標檔案名以及 verblevel
```python
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 把等等要執行的完整指令存起來
```python
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
```python
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。實際例子像是這樣
```python
import subprocess
rc = subprocess.call(["ls","-l"])
```
相較之下，subprocess.Popen() 具有更客制化的功能 (call() 是基於 Popen() 的包裝)
4. subprocess.Popen() 父進程不會等子進程完成
```python
import subprocess
child = subprocess.Popen(["ping","-c","5","www.google.com"])
print("parent process")
```
* 這個例子中，ping 完成之前，父進程會先 print
利用 wait() 來等待
```python
import subprocess
child = subprocess.Popen(["ping","-c","5","www.google.com"])
child.wait()
print("parent process")
```
5. 利用 subprocess.PIPE 來讓多個子進程之間可以彼此溝通(或是與父進程溝通)，比如說
```python
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() 傳文字給子進程
```python
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) 已經先檢查過了
```python
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 為誰
```cpp
add_cmd("new", do_new, " | Create new queue");
```
2. 接著在 do_new() 呼叫寫在 queue.c 裡面的 function
```cpp
q = q_new();
```
### signal 的處理
在一開始的 queue_init() 可以看到 signal 的處理，那讓我們在底下一一解釋
```cpp=
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
```cpp
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)
```cpp
if (!(newh->value)) {
free(newh);
return false;
}
```
2. 當 queue 是 empty 時，q_insert_tail() 要小心不要出現以下程式碼
```cpp
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")
```cpp
#include <stdio.h>
#include <string.h>
int main()
{
char a[]="aaa";
printf("%ld %ld\n",sizeof(a),strlen(a));
}
```
結果為 `4 3`
5. sizeof()使用在 char 時會有不同的行為
```cpp
#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 *)`
```cpp
newh->value = malloc(sizeof(char) * strlen(s) + 1);
// 不要寫成 newh->value = malloc(sizeof(s));
```
6. 養成好習慣，每次 strcpy 或 strncpy 之前先清空
```cpp
memset(newh->value, 0, sizeof(char) * strlen(s) + 1);
strcpy(newh->value, s);
```
Sign in with Wallet
Connect another wallet