2018q3 Homework2 (lab0)

Contributed by <aben20807>

tags: sysprog2018

開發記錄

環境

$ uname -a
Linux ben-UX410UQK 4.15.0-23-generic #25-Ubuntu SMP Wed May 23 18:02:16 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version 
gcc (Ubuntu 7.3.0-16ubuntu3) 7.3.0

結果

專案連結，已達到 100/100

結構

• 要求：q_insert_tail()、q_size() 需要
  $O(1)$
• 解決：在結構中加上指向 tail 的 pointer 和 queue 的 size 即可在常數時間存取

q_new()

• q malloc() 後必須不是 NULL 才有 head 成員可以被指向
• 而不管 malloc() 成功與否都要回傳 (失敗回傳 NULL)
• 所以此處最簡潔語法就是當 q != NULL 時再去對成員初始化
• [score]: trace-10-malloc 7/7

malloc 機率性失敗

• 遇到 malloc 失敗時，必須要有對應的處理方式
• 例如 element 失敗可以直接回傳 false
• 但若是 element 成功，但是 element 的 value 失敗，就需要先把剛剛的 element free 掉才能回傳 false
• 解決：雖然處理例外的行數不多，但還是採用下水道式的設計，利用 goto 來做流程控制

head、tail

• 在第一個元素被插入時必須注意要把 head、tail 指向同一個元素，因為該元素是第一個也是最後一個
• 從尾端加入時要另外注意 tail == NULL 的情況，因為是單向 linked list 所以一定要透過 tail->next 來插入尾端

複製字串

長度

• strlen() 的計算是不包含 '\0'
  • e.g. strlen("abcd") 是 4
• 作業要求中的 bool q_remove_head(queue_t *q, char *sp, size_t bufsize) 若 sp 不為 NULL 就要複製 bufsize - 1 個字元並在最後加上一個 '\0'

strncpy() 的危險性

• man page 中警告 strncpy() 不會自動在複製完後加上 '\0'
• char *strncpy(char *dest, const char *src, size_t n);：從 src 複製 n 個字元到 dest
  • 其中有提及簡單的實作：
    ​​​​​​​​   char *
    ​​​​​​​​   strncpy(char *dest, const char *src, size_t n)
    ​​​​​​​​   {
    ​​​​​​​​       size_t i;
    ​​​​​​​​       for (i = 0; i < n && src[i] != '\0'; i++)
    ​​​​​​​​           dest[i] = src[i];
    ​​​​​​​​       for ( ; i < n; i++)
    ​​​​​​​​           dest[i] = '\0';
    ​​​​​​​​       return dest;
    ​​​​​​​​   }
    

  • 也就是當原始長度大於想要複製的長度時，目標字串就不會有 '\0' 結尾
    • "abcd\0" -4-> "abcd"
  • 一般測試時並不會有異狀，但這是很危險的，尤其是 malloc 不保證回傳的記憶體區塊會清空，而這次作業也有出現相關的測試下方討論
• 因此若只使用 strncpy(sp, rm->value, bufsize - 1); 會因為沒有 '\0' 結尾就印出一堆奇怪的東西
• 解法1：給定 bufsize - 1 個字元後要在最後加上 '\0'
• 解法2：改用 snprintf()
  • int snprintf(char *str, size_t size, const char *format, ...);
  • 保證目標會以 '\0' 結束
    • "abcd\0" -4-> "abc\0"

free(NULL);

• 因為 free 不是系統的，所以對 NULL free 會發生錯誤！[link]

測試程式研究

malloc()

可以追蹤使用者行為

• 有一個變數 INTERNAL [link] 是用來隔離呼叫 malloc() 的行為
• 有定義 INTERNAL 的地方是使用 glibc 提供的 malloc
• 沒定義就是呼叫 harness.c 所定義的 malloc，這樣就可以記錄使用者的使用情況甚至可以給定失敗的機率

不乾淨的區塊

• malloc 原本就不保證回傳區塊會是空的，只有 calloc 保證
• 本次作業中實作的 malloc 會初始化成非空 [link]
  • e.g.
  ​​​​char *s = malloc(30);
  ​​​​printf("%s\n", s);
  

  ​​​​UUUUUUUUUUUUUUUUUUUUUUUUUUUUUU����
  

Test

scripts/driver.py

• $ make test 會去執行 scripts/driver.py
• scripts/driver.py -v [0-3] 可以改變輸出的訊息量
• 利用 subprocess 來執行 /traces 中的 .cmd 檔案 [link]，可解讀成

$ ./qtest -v [level] -f [cmd file]

• 比較特別的是 verblevel (全名： Verbosity level) 設定，如果用 $./qtest level 會是 4 所以在輸入指令時可以看到 queue 中間的內容

harness

• 定義自訂的 malloc 與 free

qtest

• 一開始在處理 option 時有一個技巧，以輸入檔為例，宣告檔名變數時使用先給定 NULL，等到有指定的 option (-f xxx.cmd) 時，先將檔名寫進一開始有給空間的 buffer 再賦值給檔名變數，這樣做可以避免使用到 malloc 動態配置。簡易流程如下

char buf[BUFSIZE];
char *infile_name = NULL;
strncpy(buf, optarg, BUFSIZE);
infile_name = buf;

• interpreter 初始化，加入 help、option、time 等指令，是利用 console.c 中的 cmd_list 記錄指令以及對應的 callback 函式 [link]，結構如下：
  • 參數 (param) 同樣利用 param_list

typedef bool (*cmd_function)(int argc, char *argv[]);
typedef struct CELE cmd_ele, *cmd_ptr;
struct CELE {
    char *name;
    cmd_function operation;
    char *documentation;
    cmd_ptr next;
};

• qtest 在印出 queue 時是直接印出 queue 中的內容，而不是另存一個陣列，所以插入會刪除時能夠看到實際結果 [link]

console

• int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);
  • monitor multiple file descriptors
  • 可以達到 non-blocking，不必非要等待事件的發生
  • timeout
    • NULL：blocking
    • 0：non-blocking and return immediately
    • 大於 0：blocking until timeout
  • [Ref] select()函數分析

遭遇問題記錄

[!] cppcheck not installed. Unable to perform static analysis.

• $ sudo apt install cppcheck