# 2018q3 Homework2 (lab0)
contributed by < [`p61402`](https://github.com/p61402) >
###### tags: `sysprog`
>commit message 中的 "Complete" 改為 "Implement" 較為適合
>[name=課程助教][color=red]
>[已修正](#修改歷史-commit-紀錄)
>[name=p61402][color=LawnGreen]
## Overview
* 前置準備
* 遠端 SSH 設定及資料夾掛載
* Github 設定
* 開發環境
* 開發流程
* 解釋自動評分系統運作的原理
* 參考資料
## 前置準備
### 遠端 SSH 設定及資料夾掛載
由於本身筆電沒有裝 linux 系統，因此決定使用 ssh 連線到另一台有 linux 系統的電腦。
輸入以下指令進行連線：
```bash
$ ssh user@140.116.112.113
```
其中`user`為 server 端的使用者名稱，後方 IP 也是 server 端的 IP，依照提示輸入密碼後，出現以下文字即代表連線成功：
```
Welcome to Ubuntu 16.04.5 LTS (GNU/Linux 4.15.0-34-generic x86_64)
* Documentation: https://help.ubuntu.com
* Management: https://landscape.canonical.com
* Support: https://ubuntu.com/advantage
8 packages can be updated.
0 updates are security updates.
Last login: Thu Sep 27 19:04:41 2018 from 192.168.208.121
```
由於不習慣使用 vim 進行編輯，因此為了在本地端以慣用編輯器開啟檔案，我會利用 sshfs 透過 ssh 協定掛載遠端硬碟。
在 Mac OS X 若要使用 sshfs，可以下載 [FUSE for OS X](http://osxfuse.github.io/)。
安裝完成後，建立一個掛載用的目錄。
```bash
$ mkdir ~/share
```
接著執行以下指令，其中`user`代換成使用者名稱，`host`代換成 IP 位址，`/home/qoo/Documents/lab0-c`則代表 server 端掛載的目錄。
```bash
$ sshfs user@host:/home/qoo/Documents/lab0-c ~/share
```
此時`~/share`資料夾就會跟遠端的資料夾同步，可以用`mount`指令查看目前掛載的目錄有哪些：
```bash
$ mount
... ...
... ...
qoo@140.116.112.113:/home/qoo/Documents/lab0-c on /Users/qoo/share (osxfuse, nodev, nosuid, synchronous, mounted by qoo)
```
要卸載時使用`umount`指令：
```bash
$ umount ~/share
```
### Github 設定
從 Github 將專案 clone 到本機後，資料夾本身就具有 git 的特性，不必再進行`git init`的動作。
```bash
$ git clone https://github.com/sysprog21/lab0-c.git
```
在 Github 上新增 ssh key，可以不用在每次連結 Github 時都輸入帳號密碼，設定流程我參考[這篇](https://help.github.com/articles/connecting-to-github-with-ssh/)官方的完整教學。
在 Github 上建立一個新的 repository 後，輸入以下指令與 Github 進行連線並 push 目前的進度。
```
$ git remote add origin git@github.com:p61402/lab0-c.git
$ git push -u origin master
```
### 開發環境
```bash
$ cat /etc/lsb-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=16.04
DISTRIB_CODENAME=xenial
DISTRIB_DESCRIPTION="Ubuntu 16.04.5 LTS"
```
```bash
$ uname -a
Linux qoo-S551LN 4.15.0-34-generic #37~16.04.1-Ubuntu SMP Tue Aug 28 10:44:06 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
```
```bash
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 69
Model name: Intel(R) Core(TM) i7-4500U CPU @ 1.80GHz
Stepping: 1
CPU MHz: 1297.879
CPU max MHz: 3000.0000
CPU min MHz: 800.0000
BogoMIPS: 4788.95
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 4096K
NUMA node0 CPU(s): 0-3
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm cpuid_fault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt dtherm ida arat pln pts flush_l1d
```
## 開發流程
### queue.h
#### linked list element
```C=
typedef struct ELE {
char *value;
struct ELE *next;
} list_ele_t;
```
#### queue strcuture
由於作業規定`q_inaert_tail`以及`q_size`兩個函式的時間複雜度必須為 O(1)，因此必須使用額外的變數來儲存 queue 的尾端以及目前大小。
在 [Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) 提到，測試資料可能多達一百萬筆，建議使用迴圈而非遞迴來實作，否則可能造成 stackoverflow。至於 queue 的 size 使用`int`型別大小宣告即可應付一百萬筆資料。
```C=
typedef struct {
list_ele_t *head;
list_ele_t *tail;
int size;
} queue_t;
```
### queue.c
#### q_new
為一個新的 queue 配置一塊記憶體空間，回傳一個指向此記憶體空間的指標，若失敗則回傳 NULL pointer。
```C=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q) {
q->head = NULL;
q->tail = NULL;
q->size = 0;
}
return q;
}
```
#### q_free
釋放整個 queue 所佔用的記憶體，由於每個 element 在 insert 的時候會配置記憶體空間，因此要使用迴圈將每個 element (包括其中的`value`) 的記憶體循序釋放，時間複雜度 O(n)。
```C=
void q_free(queue_t *q)
{
if (!q)
return;
list_ele_t *e = q->head;
while (e) {
list_ele_t *t = e->next;
free(e->value);
free(e);
e = t;
}
free(q);
}
```
#### q_insert_head
在 queue 前端 insert 一個新的 element。
使用`malloc`配置一段給新 element 的記憶體，以及`value`的記憶體，並透過`strcpy`將字串內容複製到`value`。
```C=
bool q_insert_head(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
newh->value = malloc(strlen(s) + 1);
if (!newh->value) {
free(newh);
return false;
}
strcpy(newh->value, s);
newh->next = q->head;
q->head = newh;
if (q->size == 0)
q->tail = q->head;
q->size++;
return true;
}
```
#### q_insert_tail
在 queue 的尾端 insert 一個新的 element。
方法同`q_insert_head`。
```C=
bool q_insert_tail(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
newh->value = malloc(strlen(s) + 1);
if (!newh->value) {
free(newh);
return false;
}
strcpy(newh->value, s);
newh->next = NULL;
if (q->size == 0)
q->head = newh;
else
q->tail->next = newh;
q->tail = newh;
q->size++;
return true;
}
```
#### q_remove_head
移除 queue 前端第一個 element，並且在`sp`不為`NULL`時將移除之 element 的`value`複製到`sp`，並且必須釋放移除之 element 的記憶體空間。
```C=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
/* You need to fix up this code. */
if (!q || q->size == 0)
return false;
if (sp) {
strncpy(sp, q->head->value, bufsize);
sp[bufsize - 1] = '\0';
}
list_ele_t *e = q->head;
q->head = q->head->next;
free(e->value);
free(e);
q->size--;
return true;
}
```
#### q_size
回傳 queue 目前的 element 個數。
```C=
int q_size(queue_t *q)
{
if (!q)
return 0;
return q->size;
}
```
#### q_reverse
將 queue 的 element 反轉。
```C=
void q_reverse(queue_t *q)
{
if (!q || q->size == 0)
return;
list_ele_t *pre = NULL, *temp, *cur = q->head;
q->tail = q->head;
while (cur) {
temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
q->head = pre;
}
```
### 修改歷史 commit 紀錄
目的：將原先 commit 中的字詞 complete 代換成 implement。
先查看歷史的 commit 紀錄：
```bash=
$ git log --oneline
f426e99 Modify function q_remove_head
e99ef0f Modify function q_size to handle NULL case
fdb9b8f Modify q_free function
3ea2a1e Complete function q_reverse
77b76d7 Complete function q_size
8d5643c Complete function q_remove_head
88a2bd3 Complete function q_insert_tail
0c5529f Complete function q_insert_head
a950563 Complete function q_free
5ed7df0 Complete function q_new
bd8aa24 Add extra field to struct queue_t
67654f5 Indent with given style
9509239 Merge pull request #2 from Jyun-Neng/master
399cb2e Eliminate unnecessary tar command
7251dad Change to Markdown syntax
95fb056 Move test driver to scripts/ for consistency
7795fdd Add Git pre-commit hook to validate each change
542c9b7 Initial import from CMU CS213
```
使用`rebase`指令，範圍選取自`bd8aa24`到現在為止的 commit。
```bash=
$ git rebase -i bd8aa24
pick 5ed7df0 Complete function q_new
pick a950563 Complete function q_free
pick 0c5529f Complete function q_insert_head
pick 88a2bd3 Complete function q_insert_tail
pick 8d5643c Complete function q_remove_head
pick 77b76d7 Complete function q_size
pick 3ea2a1e Complete function q_reverse
pick fdb9b8f Modify q_free function
pick e99ef0f Modify function q_size to handle NULL case
pick f426e99 Modify function q_remove_head
# Rebase bd8aa24..f426e99 onto bd8aa24 (10 command(s))
#
# Commands:
# p, pick = use commit
# r, reword = use commit, but edit the commit message
# e, edit = use commit, but stop for amending
# s, squash = use commit, but meld into previous commit
# f, fixup = like "squash", but discard this commit's log message
# x, exec = run command (the rest of the line) using shell
# d, drop = remove commit
#
# These lines can be re-ordered; they are executed from top to bottom.
#
# If you remove a line here THAT COMMIT WILL BE LOST.
#
# However, if you remove everything, the rebase will be aborted.
#
# Note that empty commits are commented out
```
將欲修改的 commit 前方的`pick`改為`reword`或`r`：
```bash
r k5ed7df0 Complete function q_new
```
存檔離開後，要開始修改剛剛選擇的 commit，此時系統會不斷跳出預設的編輯器，讓使用者逐一修改 commit 並存檔，最後出現以下訊息代表成功。
```bash
Successfully rebased and updated refs/heads/master.
```
但當要 push 時出現以下問題：
```bash
$ git push origin master
To git@github.com:p61402/lab0-c.git
! [rejected] master -> master (non-fast-forward)
error: failed to push some refs to 'git@github.com:p61402/lab0-c.git'
hint: Updates were rejected because the tip of your current branch is behind
hint: its remote counterpart. Integrate the remote changes (e.g.
hint: 'git pull ...') before pushing again.
hint: See the 'Note about fast-forwards' in 'git push --help' for details.
```
大概是因為修改 commit 的關係，讓 git 認為目前的版本是某個點的另一個分支，因為希望以目前這個版本為主，所以加入`force`參數強制改寫為現在這個版本。[[參考資料](https://gitbook.tw/chapters/github/fail-to-push.html)]
```bash
$ git push --force-with-lease origin master
Counting objects: 30, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (30/30), done.
Writing objects: 100% (30/30), 3.31 KiB | 0 bytes/s, done.
Total 30 (delta 20), reused 0 (delta 0)
remote: Resolving deltas: 100% (20/20), completed with 2 local objects.
To git@github.com:p61402/lab0-c.git
+ f426e99...b51d5b9 master -> master (forced update)
```
再次查看歷史 commit，已經修改成功囉！
```bash
$ git log --online
b51d5b9 Modify function q_remove_head
d3fa313 Modify function q_size to handle NULL case
0449937 Modify q_free function
c7a1a41 Implement function q_reverse
ddeba2c Implement function q_size
831a253 Implement function q_remove_head
8085304 Implement function q_insert_tail
3280fde Implement function q_insert_head
452c946 Implement function q_free
3eea241 Implement function q_new
bd8aa24 Add extra field to struct queue_t
67654f5 Indent with given style
9509239 Merge pull request #2 from Jyun-Neng/master
399cb2e Eliminate unnecessary tar command
7251dad Change to Markdown syntax
95fb056 Move test driver to scripts/ for consistency
7795fdd Add Git pre-commit hook to validate each change
542c9b7 Initial import from CMU CS213
```
## 解釋自動評分系統運作的原理
首先查看 Makefile 檔案，可以看到指令`make test`會執行 `scripts/driver.py`。
```make
test: qtest scripts/driver.py
scripts/driver.py
```
接著查看[`scripts/driver.py`](https://github.com/p61402/lab0-c/blob/master/scripts/driver.py)檔，在第 12 行呼叫[`getopt`](https://docs.python.org/2/library/getopt.html)函式，此函式能夠方便 parse command line 指令的參數，不必使用 regular expression 等複雜的方式來處理參數，真是太神奇了。
```C=
if __name__ == "__main__":
run(sys.argv[0], sys.argv[1:])
def run(name, args):
prog = ""
tid = 0
vlevel = 1
levelFixed = False
autograde = False
optlist, args = getopt.getopt(args, 'hp:t:v:A')
for (opt, val) in optlist:
if opt == '-h':
usage(name)
elif opt == '-p':
prog = val
elif opt == '-t':
tid = int(val)
elif opt == '-v':
vlevel = int(val)
levelFixed = True
elif opt == '-A':
autograde = True
else:
print "Unrecognized option '%s'" % opt
usage(name)
if not levelFixed and autograde:
vlevel = 0
t = Tracer(qtest = prog, verbLevel = vlevel, autograde = autograde)
t.run(tid)
```
接著函式宣告一個`Tracer`的 instance，在`Tracer`當中，`traceDict`用來儲存每個測試檔的名稱。
```C=
traceDict = {
1 : "trace-01-ops",
2 : "trace-02-ops",
3 : "trace-03-ops",
4 : "trace-04-ops",
5 : "trace-05-ops",
6 : "trace-06-string",
7 : "trace-07-robust",
8 : "trace-08-robust",
9 : "trace-09-robust",
10 : "trace-10-malloc",
11 : "trace-11-malloc",
12 : "trace-12-malloc",
13 : "trace-13-perf",
14 : "trace-14-perf",
15 : "trace-15-perf"
}
```
每段測試的指令都被收錄在[`trace`](https://github.com/p61402/lab0-c/tree/master/traces)資料夾內，例如[`traces/trace-01-ops.cmd`](https://github.com/p61402/lab0-c/blob/master/traces/trace-01-ops.cmd)，用來測試`insert_head`及`remove_head`的功能是否正確：
```bash=
# Test of insert_head and remove_head
option fail 0
option malloc 0
new
ih gerbil
ih bear
ih dolphin
rh dolphin
rh bear
rh gerbil
```
而`maxScores`決定每個測試佔多少分：
```C=
maxScores = [0, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7]
```
`Tracer`會透過在`qtest`中執行每個測試檔的指令，來判斷所測試的項目是否正確，在第 9 行，`subprocess.call`會回傳 process 的 exit status，若 return 0 則代表正確，拿到該測試的分數，最後再將所有分數加總。
```C=
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)
except Exception as e:
print "Call of '%s' failed: %s" % (" ".join(clist), e)
return False
return retcode == 0
def run(self, tid = 0):
scoreDict = { k : 0 for k in self.traceDict.keys() }
print "---\tTrace\t\tPoints"
if tid == 0:
tidList = self.traceDict.keys()
else:
if not tid in self.traceDict:
print "ERROR: Invalid trace ID %d" % tid
return
tidList = [tid]
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)
if self.autograde:
# Generate JSON string
jstring = '{"scores": {'
first = True
for k in scoreDict.keys():
if not first:
jstring += ', '
first = False
jstring += '"%s" : %d' % (self.traceProbs[k], scoreDict[k])
jstring += '}}'
print jstring
```
## 參考資料
- [SSHFS：透過 SSH 掛載遠端 Linux 伺服器上的硬碟](https://blog.gtwang.org/linux/sshfs-ssh-linux-windows-mac-os-x/)
- [Wiki - GitHub 設定指引](http://wiki.csie.ncku.edu.tw/github)
- [Connecting to GitHub with SSH - User Documentation](https://help.github.com/articles/connecting-to-github-with-ssh/)
- [如何查詢 Linux 的發行版名稱與版本](https://blog.gtwang.org/linux/find-linux-distribution-name-version-number/)
- [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
Sign in with Wallet
Connect another wallet