Try   HackMD

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

  • 在第一個元素被插入時必須注意要把 headtail 指向同一個元素,因為該元素是第一個也是最後一個
  • 從尾端加入時要另外注意 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

  • 定義自訂的 mallocfree

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

遭遇問題記錄

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

  • $ sudo apt install cppcheck