Try   HackMD

2018q3 Homework2 (lab0)

contributed by < p61402 >

tags: sysprog

commit message 中的 "Complete" 改為 "Implement" 較為適合
課程助教

已修正
p61402

Overview

  • 前置準備
    • 遠端 SSH 設定及資料夾掛載
    • Github 設定
    • 開發環境
  • 開發流程
  • 解釋自動評分系統運作的原理
  • 參考資料

前置準備

遠端 SSH 設定及資料夾掛載

由於本身筆電沒有裝 linux 系統，因此決定使用 ssh 連線到另一台有 linux 系統的電腦。

輸入以下指令進行連線：

$ 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。

安裝完成後，建立一個掛載用的目錄。

$ mkdir ~/share

接著執行以下指令，其中user代換成使用者名稱，host代換成 IP 位址，/home/qoo/Documents/lab0-c則代表 server 端掛載的目錄。

$ sshfs user@host:/home/qoo/Documents/lab0-c ~/share

此時~/share資料夾就會跟遠端的資料夾同步，可以用mount指令查看目前掛載的目錄有哪些：

$ mount
... ...
... ...
qoo@140.116.112.113:/home/qoo/Documents/lab0-c on /Users/qoo/share (osxfuse, nodev, nosuid, synchronous, mounted by qoo)

要卸載時使用umount指令：

$ umount ~/share

Github 設定

從 Github 將專案 clone 到本機後，資料夾本身就具有 git 的特性，不必再進行git init的動作。

$ git clone https://github.com/sysprog21/lab0-c.git

在 Github 上新增 ssh key，可以不用在每次連結 Github 時都輸入帳號密碼，設定流程我參考這篇官方的完整教學。

在 Github 上建立一個新的 repository 後，輸入以下指令與 Github 進行連線並 push 目前的進度。

$ git remote add origin git@github.com:p61402/lab0-c.git
$ git push -u origin master

開發環境

$ cat /etc/lsb-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=16.04
DISTRIB_CODENAME=xenial
DISTRIB_DESCRIPTION="Ubuntu 16.04.5 LTS"

$ 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

$ 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





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

queue strcuture

由於作業規定q_inaert_tail以及q_size兩個函式的時間複雜度必須為 O(1)，因此必須使用額外的變數來儲存 queue 的尾端以及目前大小。
在 Programming Lab 提到，測試資料可能多達一百萬筆，建議使用迴圈而非遞迴來實作，否則可能造成 stackoverflow。至於 queue 的 size 使用int型別大小宣告即可應付一百萬筆資料。






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

queue.c

q_new

為一個新的 queue 配置一塊記憶體空間，回傳一個指向此記憶體空間的指標，若失敗則回傳 NULL pointer。













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)。
















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。



























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。





























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 的記憶體空間。




















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 個數。







int q_size(queue_t *q)
{
    if (!q)
        return 0;
    return q->size;
}

q_reverse

將 queue 的 element 反轉。



















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 紀錄：




















$ 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。































$ 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：

r k5ed7df0 Complete function q_new

存檔離開後，要開始修改剛剛選擇的 commit，此時系統會不斷跳出預設的編輯器，讓使用者逐一修改 commit 並存檔，最後出現以下訊息代表成功。

Successfully rebased and updated refs/heads/master.

但當要 push 時出現以下問題：

$ 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參數強制改寫為現在這個版本。[參考資料]

$ 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，已經修改成功囉！

$ 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。

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

接著查看scripts/driver.py檔，在第 12 行呼叫getopt函式，此函式能夠方便 parse command line 指令的參數，不必使用 regular expression 等複雜的方式來處理參數，真是太神奇了。
































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用來儲存每個測試檔的名稱。


















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資料夾內，例如traces/trace-01-ops.cmd，用來測試insert_head及remove_head的功能是否正確：











# 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決定每個測試佔多少分：

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 則代表正確，拿到該測試的分數，最後再將所有分數加總。


















































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

參考資料

Last changed by 
 
QOO
0
476
Published on HackMD