G02: lab0

主講人: jserv / 課程討論區: 2019 年系統軟體課程
:mega: 返回「進階電腦系統理論與實作」課程進度表

作業說明直播錄影

預期目標

英文閱讀
C 語言程式設計基礎
準備 GNU/Linux 開發工具
學習使用 Git 與 GitHub
學習效能分析
研究自動測試機制

Introduction to Computer Systems (ICS) 的第一份作業

CMU Introduction to Computer Systems (ICS) 準備了 C Programming Lab 作為檢閱學生 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 進行自動程式碼排版檢查

使用一致的 coding style 很重要，我們可透過 clang-format 這個工具來調整作業程式要求的風格為以下:
```
$ clang-format -i *.[ch]
```
你可以想像 Apple 和 Google 的工程師隨便安置程式碼，然後不用管合作的議題嗎？
- 即便一個人寫作業，其實是三人的參與：過去的你、現在的你，以及未來的你
當首次執行 make 後，Git pre-commit hook 將自動安裝到現行的工作區 (workspace)，之後每次執行 git commit 時，Git hook 會檢查 C/C++ 原始程式碼的風格是否一致:
- 我們介紹 Git hooks 是為了日後銜接 Continuous integration (CI)，專業程式設計必備的準備工作
- 任何人都可以寫出機器看得懂的程式碼 (在檔案總管裡面對 EXE 檔複製貼上即可)，但我們之所以到資訊工程系接受訓練，為了寫出人看得懂、可持續維護和改進的程式
下圖展示 Git pre-commit hook 偵測到開發者的修改並未遵守一致的 coding style，主動回報並提醒開發者:
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →

自動評分系統

qtest 執行檔內有包裝許多測試這次作業可用的工具，執行 qtest 後可打 help 即有各指令解說

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

計算得分：

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

開發環境設定

依據 GNU/Linux 開發工具共筆的指引，設定好 git, GitHub 帳號, vim (或其他你偏好的編輯器), perf, gnuplot

安裝以下開發工具

$ apt install build-essential git-core cppcheck clang-format

如果你之前尚未設定或使用過 GitHub 服務，請依循 GitHub 設定指引

Git 操作和 GitHub 使用示範

取得程式碼: (一旦你 fork 後，可將 sysprog21 換為你的 GitHub 帳號)

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

編譯:

$ 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 會發現:

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

$ git add queue.h

在實際 git commit 前，應詳閱如何寫好 Git Commit Message

重新 git commit，這時可發現安裝的 Git hooks 發揮作用了:


















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

$ 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 帳號名稱)

$ 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 的註解提到:

You will need to add more fields to this structure to efficiently implement q_size and q_insert_tail

因此，我們增加 int size 到 struct queue_t:

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, 一切就緒後，提交修改:

$ 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 的執行結果是否存在 memory leak

$ 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

$ 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
- 參閱 GitHub 設定指引
詳細閱讀 C Programming Lab (英文閱讀正是我們想強化的議題，你應該在共筆上摘要題目要求)，依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改。
- 在提交程式前，務必詳閱如何寫好 Git Commit Message
- 不用理會 Autolab 和檔案下載的描述，這兩者都是 CMU 專屬
除了修改程式，也要編輯「作業區」，增添開發紀錄和 GitHub 連結，提及如何逐步達到要求，以及如何改善效能
- 解釋自動評分系統運作的原理
- 提及 qtest 的行為和裡頭的技巧，特別是 signal handler
- 解析 Valgrind 的運作原理和針對本程式的使用
- 根據 dudect 工具以及提出的對應論文 Dude, is my code constant time?，探討一種以實驗而非理論驗證時間複雜度的方法
- 留意 MAGICHEADER, MAGICFREE, MAGICFOOTER, FILLCHAR 等巨集的使用，並探討其動機和用法
截止日期：
- Oct 2, 2019 (含) 之前
- 越早在 GitHub 上有動態、越早接受 code review，評分越高

G02: lab0

預期目標

Introduction to Computer Systems (ICS) 的第一份作業

使用 clang-format + Git Hooks 進行自動程式碼排版檢查

自動評分系統

開發環境設定

Git 操作和 GitHub 使用示範

使用工具分析 q_reverse 的執行表現

作業要求

作業觀摩

Read more

關於「一切皆為檔案」的理念和解讀

2025 年春季「Linux 核心設計」第 6 週測驗題

淺談 Microkernel 設計和真實世界中的應用

你所不知道的 C 語言：指標篇