2020q1 Homework1 (lab0)

contributed by < a20034294 >

實驗環境

• 硬體環境:
  • Guest CPU kvm64 QEMU(1:2.11+dfsg-1ubuntu7.23) in Proxmox VE
  • Host CPU X5650 2.66G*2
  • 2GB RAM
• 作業系統: Ubuntu 18.04.4
• 核心版本: Linux 4.15.0-88-generic
• gcc 版本: 7.4.0-1ubuntu1~18.04.1

作業目標

• 在 GitHub 上 fork lab0-c
  • 參閱 Git 教學和 GitHub 設定指引 ^{附教學影片}
• 詳細閱讀 C Programming Lab ，依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 q_sort 函式。
  • 在提交程式變更前，務必詳閱 如何寫好 Git Commit Message
  • 不用理會 Autolab 和檔案下載的描述，這兩者都是 CMU 專屬
• 修改排序所用的比較函式，變更為 natural sort，在 "simulation" 也該做對應的修改，得以反映出 natural sort 的使用。
• 除了修改程式，也要編輯「作業區」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
  • 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
  • 研讀論文 Dude, is my code constant time?，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student's t-distribution 及程式實作的原理;
  • 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點。可對照參考 CS:APP 第 10 章重點提示 為避免「舉燭」，請比照 qtest 實作，撰寫獨立的終端機命令解譯器 (可建立新的 GitHub repository)
• 挑戰題
  • 參照 antirez/linenoise，強化 qtest 命令列功能，使其支援單行或多行編輯、歷史命令處理、命令自動補完 (例如輸入 h 之後按下 Tab 按鍵，自動接續補上 elp，成為完整的 help 命令)。除了整合程式碼外，應當說明 antirez/linenoise 的運作原理，注意到 termios 的運用
  • 思考如何預設開啟 AddressSanitizer，卻又能滿足效能測試所需 (可能需要兩種以上的 build target)
  • 指出現有程式的缺陷 (提示: 和 RIO 套件 有關)，嘗試強化並提交 pull request
• 截止日期：
  • Mar 2, 2020 (含) 之前

    a20034294 大失敗

  • 越早在 GitHub 上有動態、越早接受 code review，評分越高

實作

依照 C Programming Lab 裡的說明，需要更改以下的 function 以完成作業要求

• q_new
• q_free
• q_insert_head
• q_insert_tail
• q_remove_head
• q_size
• q_reverse
• q_sort

q_new

新增 malloc return NULL 時的例外狀況，以及初始化 queue

   13 queue_t *q_new()
   14 {
   15     queue_t *q = malloc(sizeof(queue_t));
~  16
+  17     if (!q) {
+  18         return NULL;
+  19     }
   20     q->head = NULL;
+  21     q->tail = NULL;
+  22     q->size = 0;
   23     return q;
   24 }

q_free

將所使用的 string 空間以及 list_ele_t 所使用的 node 空間釋放

   27 void q_free(queue_t *q)
   28 {
~  29     // cppcheck-suppress variableScope
~  30     list_ele_t *p, *tmp;
+  31
+  32     if (!q)
+  33         return;
+  34
+  35     p = q->head;
+  36     while (p) {
+  37         free(p->value);
+  38         tmp = p;
+  39         p = p->next;
+  40         free(tmp);
+  41     }
   42     free(q);
   43 }

q_insert_head

與 q_insert_tail 差距不大，只貼其中一個
動態分配記憶體 copy 需要 insert 的 string 然後維護 queue
原本使用 strcpy() 進行 copy，但被報 Warnning

   52 bool q_insert_head(queue_t *q, char *s)
   53 {
   54     list_ele_t *newh;
~  55     char *tmp_s;
+  56
+  57     if (!q)
+  58         return false;
+  59
   60     newh = malloc(sizeof(list_ele_t));
~  61     if (!newh)
~  62         return false;
+  63
+  64     tmp_s = malloc(strlen(s) + 1);
+  65     if (!tmp_s) {
+  66         free(newh);
+  67         return false;
+  68     }
+  69     strncpy(tmp_s, s, strlen(s) + 1);
+  70
+  71     newh->value = tmp_s;
   72     newh->next = q->head;
   73     q->head = newh;
+  74     if (!q->size)
+  75         q->tail = newh;
+  76     q->size++;
   77     return true;
   78 }

q_remove_head

利用 strncpy 進行 copy 並在尾端補 \0
最後釋放記憶體空間

  125 bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
  126 {
~ 127     list_ele_t *head;
~ 128
+ 129     if (!q || !q->head)
+ 130         return false;
+ 131
+ 132     head = q->head;
+ 133     if (sp) {
+ 134         strncpy(sp, head->value, bufsize);
+ 135         sp[bufsize - 1] = '\0';
+ 136     }
  137     q->head = q->head->next;
+ 138     q->size--;
+ 139     free(head->value);
+ 140     free(head);
  141     return true;
  142 }

q_size

由於在各個會變動大小的函數內已經維護 size，因此直接 return q->size

  148 int q_size(queue_t *q)
  149 {
+ 150     if (!q)
+ 151         return 0;
+ 152
+ 153     return q->size;
  154 }

可改寫為:

int q_size(queue_t *q)
{
    return q ? q->size : 0;
}

jserv

a20034294已經修改完成 謝謝老師 4b2c0a

q_reverse

走訪 list 並將 next 指標反指
最後將 head、tail 互換

  163 void q_reverse(queue_t *q)
  164 {
~ 165     list_ele_t *p, *prev, *next;
~ 166
+ 167     if (!q || q->size <= 1)
+ 168         return;
+ 169
+ 170     p = q->head;
+ 171     prev = NULL;
+ 172     while (p) {
+ 173         next = p->next;
+ 174         p->next = prev;
+ 175         prev = p;
+ 176         p = next;
+ 177     }
+ 178
+ 179     // swap
+ 180     p = q->head;
+ 181     q->head = q->tail;
+ 182     q->tail = p;
  183 }

q_sort

使用 merge sort 由於 code 太長了就不貼了
值得一提的是原本直接引入 natural sort 作為比較使用，結果 make test 出現 TLE + seg fault，make valgrind 執行可以正常通過，判斷應是太慢導致。

調整 insert 的數量，從

$2e6$ 到

$8e5$ 之後可以通過，認為成因可能是 QEMU + x5650 2.66G 太慢。

突然想到可以用 hash 表，讓他可以在判斷字串不同之後才進行比較。
以下為 hash function

/*
 * Get the string hash
 * @char* s string
 */
inline void hash(list_ele_t *e)
{
    e->hash = 0;
    for (int i = 0; i < e->len; ++i) {
        e->hash *= 10000007;
        e->hash += e->value[i];
    }
}

然後正常通過，不過這對

$aaaa...aab$、

$aaaa...aaa$ 這樣的字串比對沒有幫助，因為 hash 值無法比較大小，用紅黑樹的 map(c++ STL) 或是 hash map 做 hash 比較結果的 cache 可以顯著提升效率，但是實作太難，也沒有必要就不實作了。

---

未完

==7135==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55b6cb8c19c0 at pc 0x55b6cb6b1d17 bp 0x7ffdba43b8d0 sp 0x7ffdba43b8c
0
READ of size 4 at 0x55b6cb8c19c0 thread T0
    #0 0x55b6cb6b1d16 in do_option_cmd /home/a20034294/lab0-c/console.c:368
    #1 0x55b6cb6b0ddc in interpret_cmda /home/a20034294/lab0-c/console.c:220
    #2 0x55b6cb6b10cc in interpret_cmd /home/a20034294/lab0-c/console.c:243
    #3 0x55b6cb6b1fb6 in cmd_select /home/a20034294/lab0-c/console.c:569
    #4 0x55b6cb6b223f in run_console /home/a20034294/lab0-c/console.c:628
    #5 0x55b6cb6ad26b in main /home/a20034294/lab0-c/qtest.c:772
    #6 0x7fbfe07dfb96 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b96)
    #7 0x55b6cb6ad549 in _start (/home/a20034294/lab0-c/qtest+0x7549)

0x55b6cb8c19c1 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:20:6' (0x55b6cb8c19c0) of size 1
  'simulation' is ascii string ''
SUMMARY: AddressSanitizer: global-buffer-overflow /home/a20034294/lab0-c/console.c:368 in do_option_cmd