# G02: lab0 :::info 主講人: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) / 課程討論區: [2019 年系統軟體課程](https://www.facebook.com/groups/system.software2019/) :mega: 返回「[進階電腦系統理論與實作](http://wiki.csie.ncku.edu.tw/sysprog/schedule)」課程進度表 ::: ==[作業說明直播錄影](https://youtu.be/Oryj98W9wHs)== ## 預期目標 * 英文閱讀 * C 語言程式設計基礎 * 準備 GNU/Linux 開發工具 * 學習使用 Git 與 GitHub * 學習效能分析 * 研究自動測試機制 ## Introduction to Computer Systems (ICS) 的第一份作業 CMU [Introduction to Computer Systems (ICS)](http://www.cs.cmu.edu/~213/index.html) 準備了 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) 作為檢閱學生 C 語言程式設計的認知: * Explicit memory management, as required in C. * Creating and manipulating pointer-based data structures. * Working with strings. * Enhancing the performance of key operations by storing redundant information in data structures. * Implementing robust code that operates correctly with invalid arguments, including NULL pointers. 實驗目標為實作 queue * first in, first out (FIFO) * last in, first out (LIFO) ## 使用 clang-format + [Git Hooks](https://www.atlassian.com/git/tutorials/git-hooks) 進行自動程式碼排版檢查 * 使用一致的 coding style 很重要，我們可透過 [clang-format](https://clang.llvm.org/docs/ClangFormat.html) 這個工具來調整作業程式要求的風格為以下: ```shell $ clang-format -i *.[ch] ``` * 你可以想像 Apple 和 Google 的工程師隨便安置程式碼，然後不用管合作的議題嗎？ * 即便一個人寫作業，其實是三人的參與：過去的你、現在的你，以及未來的你 * 當首次執行 `make` 後，Git pre-commit hook 將自動安裝到現行的工作區 (workspace)，之後每次執行 `git commit` 時，Git hook 會檢查 C/C++ 原始程式碼的風格是否一致: * 我們介紹 [Git hooks](https://goo.gl/CNMHZJ) 是為了日後銜接 Continuous integration (CI)，專業程式設計必備的準備工作 * 任何人都可以寫出機器看得懂的程式碼 (在檔案總管裡面對 EXE 檔複製貼上即可)，但我們之所以到資訊工程系接受訓練，為了寫出人看得懂、可持續維護和改進的程式 * 下圖展示 Git pre-commit hook 偵測到開發者的修改並未遵守一致的 coding style，主動回報並提醒開發者: ![](https://i.imgur.com/ZUslMF0.jpg) ## 自動評分系統 `qtest` 執行檔內有包裝許多測試這次作業可用的工具，執行 `qtest` 後可打 `help` 即有各指令解說 ```shell make ./qtest cmd>help Commands: # ... | Display comment free | Delete queue help | Show documentation ih v [n] | Insert v at head of queue n times (default: n == 1) it v [n] | Insert v at tail of queue n times (default: n == 1) log file | Copy output to file new | Create new queue option [name val] | Display or set options quit | Exit program reverse | Reverse queue rh [v] | Remove from head of queue. Optionally compare to expected value v rhq [v] | Remove from head of queue without reporting value show | Show queue contents size [n] | Compute queue size n times (default: n == 1) source file | Read commands from source file time cmd arg ... | Time command execution Options: echo 1 Do/don't echo commands error 5 Number of errors until exit fail 30 Number of times allow queue operations to return false malloc 0 Malloc failure probability percent verbose 4 Verbosity level ``` qtest 使用範例: ``` # 確認目前 queue 內容（一開始應該是空的 q = NULL） show # 新建一個 queue (q = []) new # 在 head 新增數值 ih 2 ih 1 ih 3 # 結果： #q = [] #cmd>ih 1 #cmd>ih 1 #q = [1] #cmd>ih 2 #cmd>ih 2 #q = [2 1] #cmd>ih 3 #cmd>ih 3 #q = [3 2 1] # 現在從尾巴加（應該會失敗因為還沒實作) it 5 4 it 1 # 反轉 queue, 算長度, 釋放記憶體等..（應該都會失敗因為還沒實作) reverse size free # 離開 quit ``` * 計算得分： ```shell make test ``` 如果什麼都沒做，當然是零分，參考輸出: ``` Test performance of insert_tail, size, and reverse ERROR: Need to allocate separate string for each list element ERROR: Insertion of gerbil failed (1 failures total) ERROR: Computed queue size as 0, but correct value is 2 ERROR: Computed queue size as 0, but correct value is 2 --- trace-15-perf 0/7 --- TOTAL 0/100 ``` ## 開發環境設定 1. 依據 [GNU/Linux 開發工具共筆](https://hackmd.io/c/rJKbX1pFZ) 的指引，設定好 git, GitHub 帳號, vim (或其他你偏好的編輯器), perf, gnuplot 2. 安裝以下開發工具 ```shell $ apt install build-essential git-core cppcheck clang-format ``` 3. 如果你之前尚未設定或使用過 GitHub 服務，請依循 [GitHub 設定指引](http://wiki.csie.ncku.edu.tw/github) ## Git 操作和 GitHub 使用示範 取得程式碼: (一旦你 fork 後，可將 `sysprog21` 換為你的 GitHub 帳號) ```shell $ git clone https://github.com/sysprog21/lab0-c ``` 編譯: ```shell $ make ``` 預期會看到以下輸出: ``` gcc -O0 -g -Wall -Werror -c queue.c gcc -O0 -g -Wall -Werror -o qtest qtest.c report.c console.c harness.c queue.o ``` 事先編輯檔案 `queue.h` 後，執行 `git commit` 會發現: ```shell $ git commit On branch master Your branch is up-to-date with 'origin/master'. Changes not staged for commit: modified: queue.h no changes added to commit ``` 原來要指定變更的檔案，用命令 `git add`: ```shell $ git add queue.h ``` * 在實際 `git commit` 前，應詳閱 [如何寫好 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/) 重新 `git commit`，這時可發現安裝的 Git hooks 發揮作用了: ```shell= $ git commit -m "add fields to point to the tail" add fields to point to the tail [line 1] - Capitalize the subject line Proceed with commit? [e/n/?] e add fields to point to the tail [line 1] - Capitalize the subject line Proceed with commit? [e/n/?] y How to Write a Git Commit Message: https://chris.beams.io/posts/git-commit/ e - edit commit message n - abort commit ? - print help Proceed with commit? [e/n/?] ? How to Write a Git Commit Message: https://chris.beams.io/posts/git-commit/ e - edit commit message n - abort commit ? - print help Proceed with commit? [e/n/?] e [master 23f7113] Add fields to point to the tail ``` Git hook 提示我們: * 第 4 行輸入 `e`，可編輯 `git commit` 的訊息 * 第 7 行輸入 `y`，因為 y 不是有效選項, 所以出現 help * 第 17 行輸入 `e`, 再次編輯訊息，因訊息有限制標題開頭要大寫 commit 前再調整訊息，注意，請避免用 `git commit -m`，而是透過編輯器調整 git commit message。 ``` shell $ git commit On branch master Your branch is ahead of 'origin/master' by 1 commit. (use "git push" to publish your local commits) nothing to commit, working tree clean ``` 接著將本地端的修改同步 GitHub 上，執行 `git push`: (下方的 `butastur-rtos` 是示範帳號，請換為你自己的 GitHub 帳號名稱) ```shell $ git push Username for 'https://github.com': butastur-rtos Password for 'https://butastur-rtos@github.com': Counting objects: 3, done. Delta compression using up to 2 threads. Compressing objects: 100% (3/3), done. Writing objects: 100% (3/3), 324 bytes | 0 bytes/s, done. Total 3 (delta 2), reused 0 (delta 0) remote: Resolving deltas: 100% (2/2), completed with 2 local objects. To https://github.com/butastur-rtos/lab0-c.git 7251dad..b119f00 master -> master ``` 牛刀小試，嘗試實作函式 `q_size`。 `int q_size(queue_t *q)` 由於要在 $O(1)$ 的常數時間內執行完成, 所以也不可能每次都遍歷整個 list 來取得 queue 的大小, [`queue.h`](https://github.com/sysprog21/lab0-c/blob/master/queue.h#L30) 的註解提到: > You will need to add more fields to this structure to efficiently implement q_size and q_insert_tail 因此，我們增加 <b>int size</b> 到 `struct queue_t`: ```clike typedef struct { list_ele_t *head; /* Linked list of elements */ /* You will need to add more fields to this structure to efficiently implement q_size and q_insert_tail */ list_ele_t *tail; int size; } queue_t; ``` 接著修改 `q_size` 的傳回值, 改成傳回 `q->size`, 一切就緒後，提交修改: ```shell $ git commit -m "Change q_size return value to q->size" --- .merge_file_Iu0bic 2018-09-21 13:33:12.940675156 -0500 +++ /tmp/.merge_file_Iu0bic.rV006h 2018-09-21 13:33:12.953675156 -0500 @@ -70,7 +70,7 @@ bool q_insert_tail(queue_t *q, char *s) { /* You need to write the complete code for this function */ /* Remember: It should operate in O(1) time */ - list_ele_t *newt; // newt means new tail + list_ele_t *newt; // newt means new tail newt = malloc(sizeof(list_ele_t)); q->tail = newt; return true; [!] queue.c does not follow the consistent coding style. Make sure you indent as the following: clang-format -i queue.c ``` 發現格式不對，所以 Git commit hook 擋住了，所以我們用 `clang-format -i` 去調整格式，才能繼續。 ### 使用工具分析 q_reverse 的執行表現 * $O(n)$ * valgrind 用 `valgrind` 來檢查一下 [`qtest`](https://github.com/butastur-rtos/lab0-c/blob/master/queue.c) 的執行結果是否存在 memory leak ```shell $ valgrind ./qtest cmd>new cmd>new q = [] cmd>ih str 1000 cmd>ih str 1000 q = [str str str str str str str str str str str str str str str str str str str str str str str str str str str str str str ... ] cmd>quit cmd>quit Freeing queue ==18771== ==18771== HEAP SUMMARY: ==18771== in use at exit: 4,000 bytes in 1,000 blocks ==18771== total heap usage: 2,041 allocs, 1,041 frees, 70,190 bytes allocated ==18771== ==18771== LEAK SUMMARY: ==18771== definitely lost: 4,000 bytes in 1,000 blocks ==18771== indirectly lost: 0 bytes in 0 blocks ==18771== possibly lost: 0 bytes in 0 blocks ==18771== still reachable: 0 bytes in 0 blocks ==18771== suppressed: 0 bytes in 0 blocks ==18771== Rerun with --leak-check=full to see details of leaked memory ==18771== ==18771== For counts of detected and suppressed errors, rerun with: -v ==18771== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) ``` 對 `valgrind` 多一些嘗試, 試一下 `valgrind --leak-check=full` ```shell $ valgrind --leak-check=full ./qtest ==18783== Memcheck, a memory error detector ==18783== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al. ==18783== Using Valgrind-3.12.0.SVN and LibVEX; rerun with -h for copyright info ==18783== Command: ./qtest ==18783== cmd>new cmd>new q = [] cmd>ih str 1000 cmd>ih str 1000 q = [str str str str str str str str str str str str str str str str str str str str str str str str str str str str str str ... ] cmd>quit cmd>quit Freeing queue ==18783== ==18783== HEAP SUMMARY: ==18783== in use at exit: 4,000 bytes in 1,000 blocks ==18783== total heap usage: 2,036 allocs, 1,036 frees, 70,141 bytes allocated ==18783== ==18783== 4,000 bytes in 1,000 blocks are definitely lost in loss record 1 of 1 ==18783== at 0x4C2BBAF: malloc (vg_replace_malloc.c:299) ==18783== by 0x4EB83B9: strdup (strdup.c:42) ==18783== by 0x10D1E0: q_insert_head (queue.c:75) ==18783== by 0x10968C: do_insert_head (qtest.c:166) ==18783== by 0x10BB68: interpret_cmda (console.c:218) ==18783== by 0x10BBFC: interpret_cmd (console.c:239) ==18783== by 0x10CA14: cmd_select (console.c:605) ==18783== by 0x10CB67: run_console (console.c:642) ==18783== by 0x10A77D: main (qtest.c:573) ==18783== ==18783== LEAK SUMMARY: ==18783== definitely lost: 4,000 bytes in 1,000 blocks ==18783== indirectly lost: 0 bytes in 0 blocks ==18783== possibly lost: 0 bytes in 0 blocks ==18783== still reachable: 0 bytes in 0 blocks ==18783== suppressed: 0 bytes in 0 blocks ==18783== ==18783== For counts of detected and suppressed errors, rerun with: -v ==18783== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0) ``` ## 作業要求 * 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c) * 參閱 [GitHub 設定指引](http://wiki.csie.ncku.edu.tw/github) * ==詳細閱讀 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)== (英文閱讀正是我們想強化的議題，你應該在共筆上摘要題目要求)，依據指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改。 * 在提交程式前，務必詳閱 [如何寫好 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/) * 不用理會 [Autolab](http://www.autolabproject.com/) 和檔案下載的描述，這兩者都是 CMU 專屬 * 除了修改程式，也要編輯「[作業區](https://hackmd.io/@sysprog/BkZ4h5xPB)」，增添開發紀錄和 GitHub 連結，提及如何逐步達到要求，以及如何改善效能 * 解釋自動評分系統運作的原理 * 提及 `qtest` 的行為和裡頭的技巧，特別是 signal handler * 解析 Valgrind 的運作原理和針對本程式的使用 * 根據 [dudect](https://github.com/oreparaz/dudect) 工具以及提出的對應論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)，探討一種以實驗而非理論驗證時間複雜度的方法 * 留意 `MAGICHEADER`, `MAGICFREE`, `MAGICFOOTER`, `FILLCHAR` 等巨集的使用，並探討其動機和用法 * 截止日期： * Oct 2, 2019 (含) 之前 * 越早在 GitHub 上有動態、越早接受 code review，評分越高 ## 作業觀摩 * [2019 年春季班](https://hackmd.io/@sysprog/SJ4kPZYS4) * [2018 年秋季班](https://hackmd.io/@sysprog/rJwiDHGKQ)