# 2020q1 Homework1 (lab0) contributed by < `oucs638` > ## 作業說明 - [H01: lab0](https://hackmd.io/@sysprog/linux2020-lab0) - - - ## 開發環境 ```shell $ uname -a Linux oucs638-ROG-Strix-G731GU-G731GU 5.3.0-40-generic #32~18.04.1-Ubuntu SMP Mon Feb 3 14:05:59 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian CPU(s): 12 On-line CPU(s) list: 0-11 Thread(s) per core: 2 Core(s) per socket: 6 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 158 Model name: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz Stepping: 13 CPU MHz: 800.015 CPU max MHz: 4500.0000 CPU min MHz: 800.0000 BogoMIPS: 5199.98 Virtualization: VT-x L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 12288K NUMA node0 CPU(s): 0-11 Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb invpcid_single ssbd ibrs ibpb stibp ibrs_enhanced tpr_shadow vnmi flexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap clflushopt intel_pt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp md_clear flush_l1d arch_capabilities $ gcc --version gcc (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0 ``` - - - ## 作業要求 - 在 GitHub fork [lab0-c](https://github.com/sysprog21/lab0-c) - 詳細閱讀 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) ，依據指示著手修改 `queue.[ch]` 和連帶的檔案，完成以下實作 - `q_new`: 建立新的「空」佇列 (`queue`) - `q_free`: 釋放佇列所佔用的記憶體 - `q_insert_head`: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則) - `q_insert_tail`: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則) - `q_remove_head`: 在佇列開頭 (head) 移除 (remove) 給定的元素 - `q_size`: 計算佇列中的元素數量 - `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素 - `q_sort`: 以 [natural sort](https://github.com/sourcefrog/natsort) 排序鍊結元素 - - - ## 參考資料 - [C99 規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) - [CS : APP 第十章重點提示](https://hackmd.io/@sysprog/H1TtmVTTz) - [select 系統](http://man7.org/linux/man-pages/man2/select.2.html) - [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf) - - - ## 實作紀錄 ### Define `queue_t` - 為了使 `q_insert_tail` 與 `q_size` 能在 $O(1)$ 條件下完成，新增: - `tail`: 紀錄佇列尾端元素的記憶體位置 - `size`: 紀錄佇列內總元素個數 ```cpp= typedef struct { list_ele_t *head; /* Linked list of elements */ list_ele_t *tail; int size; } queue_t; ``` ### `q_new` - 在 `malloc` 要求分配記憶體之後確認是否成功 - 失敗，回傳 `NULL` - 成功，初始化 ```cpp= queue_t *q_new() { queue_t *q = malloc(sizeof(queue_t)); if (!q) return NULL; q->head = NULL; q->tail = NULL; q->size = 0; return q; } ``` ### `q_free` - 確認 `queue` 非 `NULL` - 利用 `q_remove_head` 清除 `queue` 中元素 ```cpp= void q_free(queue_t *q) { /* Free queue structure */ if (!q) return; while (q->head) q_remove_head(q, NULL, 0); q->tail = NULL; // free(q->size); free(q); } ``` ### `q_insert_head` - 確認 `queue` 非 `NULL` - 確認有成功 `malloc` 到新增元素所思的記憶體空間 - 在要求新的字串空間時 `+1` ，以容納做結的 `\0` - 將新元素的 `next` 指向原本的 `head` - 再將 `head` 更新為新元素 ```cpp= bool q_insert_head(queue_t *q, char *s) { if (!q) return false; // make sure allocate the memory success list_ele_t *newh; newh = malloc(sizeof(list_ele_t)); if (!newh) return false; char *tmp = NULL; tmp = malloc((strlen(s) + 1) * sizeof(char)); if (!tmp) { free(newh); return false; } // copy the string memset(tmp, 0, (strlen(s) + 1) * sizeof(char)); strncpy(tmp, s, strlen(s)); newh->value = tmp; // link newh newh->next = q->head; q->head = newh; // refresh other information in queue if (!q->tail) q->tail = newh; q->size++; return true; } ``` - 針對字串空間處理，以及精簡後如下 ```cpp= bool q_insert_head(queue_t *q, char *s) { if (!q) return false; // make sure allocate the memory success list_ele_t *newh = malloc(sizeof(list_ele_t)); if (!newh) return false; newh->value = malloc((strlen(s) + 1) * sizeof(char)); if (!newh->value) { free(newh); return false; } // copy the string memset(newh->value, 0, (strlen(s) + 1) * sizeof(char)); strncpy(newh->value, s, strlen(s)); newh->value[strlen(s)] = '\0'; // link newh newh->next = q->head; q->head = newh; if (!q->tail) q->tail = newh; // refresh the size of queue q->size++; return true; } ``` ### `q_insert_tail` - 確認 `queue` 非 `NULL` - 確認有成功 `malloc` 到新增元素所思的記憶體空間 - 在要求新的字串空間時 `+1` ，以容納做結的 `\0` - 將原本 `tail` 的 `next` 指向新元素 - 再將 `tail` 更新為新元素 ```cpp= bool q_insert_tail(queue_t *q, char *s) { if (!q) return false; // make sure allocate the memory success list_ele_t *newt = NULL; newt = malloc(sizeof(list_ele_t)); if (!newt) return false; char *tmp = NULL; tmp = malloc((strlen(s) + 1) * sizeof(char)); if (!tmp) { free(newt); return false; } // copy the string memset(tmp, 0, (strlen(s) + 1) * sizeof(char)); strncpy(tmp, s, strlen(s)); newt->value = tmp; newt->next = NULL; // link newt if (!q->head) q->head = newt; else q->tail->next = newt; q->tail = newt; // refresh the size of queue q->size++; return true; } ``` - 針對字串空間處理，以及精簡後如下 ```cpp= bool q_insert_tail(queue_t *q, char *s) { if (!q) return false; // make sure allocate the memory success list_ele_t *newt = malloc(sizeof(list_ele_t)); if (!newt) return false; newt->value = malloc((strlen(s) + 1) * sizeof(char)); if (!newt->value) { free(newt); return false; } // copy the string memset(newt->value, 0, (strlen(s) + 1) * sizeof(char)); strncpy(newt->value, s, strlen(s)); newt->value[strlen(s)] = '\0'; // link newt newt->next = NULL; if (!q->head) q->head = newt; else q->tail->next = newt; q->tail = newt; // refresh the size of queue q->size++; return true; } ``` ### `q_remove_head` - 確認 `queue` 非空且有元素可被移除 - 依據註解的要求，對 `sp` 進行處理 - 用 `tmp` 紀錄要釋放的位置，再將 `head` 位置更新 - 最後更新 `q->size` ```cpp= bool q_remove_head(queue_t *q, char *sp, size_t bufsize) { if (!q || !q->head || !q->size) return false; if (sp && q->head->value) strncpy(sp, q->head->value, bufsize - 1); list_ele_t *tmp = q->head; q->head = q->head->next; free(tmp->value); free(tmp); q->size--; return true; } ``` - 後來在嘗試 `make valgrind` 時，在 `trace 5` 出現 ERROR ，報錯訊息顯示 `removed` 字串後的回傳值有包亂碼 - 新增步驟：在寫入 `sp` 之前，先將 `sp` 空間全部設為 `\0` - 更改後通過 `make valgrind` ```cpp= bool q_remove_head(queue_t *q, char *sp, size_t bufsize) { if (!q || !q->head || !q->size) return false; if (sp && q->head->value) { memset(sp, '\0', bufsize); strncpy(sp, q->head->value, bufsize - 1); } list_ele_t *tmp = q->head; q->head = q->head->next; free(tmp->value); free(tmp); q->size--; return true; } ``` ### `q_size` - 直接回傳 `q->size` ，時間複雜度為 $O(1)$ ```cpp= int q_size(queue_t *q) { if (q && q->size) return q->size; return 0; } ``` ### `q_reverse` - 原本的想法是使用迭代呼叫 `q_insert_head` - 但看到註解要不能使用，故作罷 - 後來想到逐個訪，將 `next` 指向前一個元素 - 故須紀錄前一個元素以及現在拜訪到那一個元素 - `pvv` 初始化為 `NULL` 是為了避免新的 `queue` 產生環 ```cpp= void q_reverse(queue_t *q) { if (!q || !q->head || q->size < 2) return; list_ele_t *prv = NULL, *now = q->head; q->tail = q->head; while (now) { list_ele_t *tmp = now; now = now->next; tmp->next = prv; prv = tmp; } q->head = prv; } ``` ### `q_sort` - 參考 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) - 我決定採用 Merge Sort 來實作，以符合自動測試程式的時間限制，新增下列 `function` - `mergeSortList` - `merge` - 因規定，參考 [natural sort](https://github.com/sourcefrog/natsort) 後，仿照 `strnatcmp[.ch]` 新增下列 `function` 用以比較 - `strnatcmp` - `compare_a` - `compare_r` - `compare_l` - `compare_r` ```cpp= static int compare_r(char const *st1, char const *st2) { int bis = 0; for (;; st1++, st2++) if (!isdigit((unsigned char) *st1)) return (!isdigit((unsigned char) *st2)) ? bis : -1; else if (!isdigit((unsigned char) *st2)) return 1; else if (!*st1 && !*st2) return bis; else if (!bis) bis = (*st1 < *st2) ? -1 : (*st1 > *st2) ? 1 : bis; return 0; } ``` - `compare_l` ```cpp= static int compare_l(char const *st1, char const *st2) { for (;; st1++, st2++) if (!isdigit((unsigned char) *st1)) return (!isdigit((unsigned char) *st2)) ? 0 : -1; else if (!isdigit((unsigned char) *st2)) return 1; else if (*st1 < *st2) return -1; else if (*st1 > *st2) return 1; return 0; } ``` - `compare_a` ```cpp= static int compare_a(char const *st1, char const *st2) { int id1 = 0, id2 = 0; while (1) { char ch1 = st1[id1], ch2 = st2[id2]; while (isspace((unsigned char) ch1)) ch1 = st1[++id1]; while (isspace((unsigned char) ch2)) ch2 = st2[++id2]; if (isdigit((unsigned char) ch1) && isdigit((unsigned char) ch2)) { int tmp = 0; if (ch1 == '0' || ch2 == '0') tmp = compare_l(st1 + id1, st2 + id2); else tmp = compare_r(st1 + id1, st2 + id2); if (tmp) return tmp; } if (!ch1 && !ch2) return 0; if (ch1 < ch2) return -1; if (ch1 > ch2) return 1; ++id1; ++id2; } } ``` - `strnatcmp` ```cpp= int strnatcmp(char const *st1, char const *st2) { return compare_a(st1, st2); } ``` - `merge` ```cpp= list_ele_t *merge(list_ele_t *ls1, list_ele_t *ls2) { list_ele_t *res = NULL, *lst = NULL; while (ls1 || ls2) { int tmp = 0; if (ls1 && ls2) tmp = (strnatcmp(ls1->value, ls2->value) < 0) ? 1 : -1; if (!ls1 || tmp == -1) { if (!res) res = ls2; else lst->next = ls2; lst = ls2; ls2 = ls2->next; } else if (!ls2 || tmp == 1) { if (!res) res = ls1; else lst->next = ls1; lst = ls1; ls1 = ls1->next; } } return res; } ``` - `mergeSortList` ```cpp= list_ele_t *mergeSortList(list_ele_t *head) { if (!head || !head->next) return head; list_ele_t *fast = head->next, *slow = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } fast = slow->next; slow->next = NULL; list_ele_t *ls1 = mergeSortList(head); list_ele_t *ls2 = mergeSortList(fast); return merge(ls1, ls2); } ``` - `q_sort` ```cpp= void q_sort(queue_t *q) { if (!q || !q->head || q->size < 2) return; q->head = mergeSortList(q->head); list_ele_t *tmp = q->head; // find the new tail while(tmp->next) tmp = tmp->next; q->tail = tmp; } ``` - - - ## 使用 Valgrind 檢測記憶體空間使用狀況 - 第一次嘗試結果失敗，待 Debug ```shell $ make valgrind # Explicitly disable sanitizer(s) make clean SANITIZER=0 qtest make[1]: Entering directory '/home/oucs638/GitHub/lab0-c' rm -f qtest.o report.o console.o harness.o queue.o random.o dudect/constant.o dudect/fixture.o dudect/ttest.o .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d *~ qtest /tmp/qtest.* rm -rf .dudect rm -rf *.dSYM (cd traces; rm -f *~) CC qtest.o CC report.o CC console.o CC harness.o CC queue.o CC random.o CC dudect/constant.o CC dudect/fixture.o CC dudect/ttest.o LD qtest make[1]: Leaving directory '/home/oucs638/GitHub/lab0-c' cp qtest /tmp/qtest.zqtFyF chmod u+x /tmp/qtest.zqtFyF sed -i "s/alarm/isnan/g" /tmp/qtest.zqtFyF scripts/driver.py -p /tmp/qtest.zqtFyF --valgrind --- Trace Points +++ TESTING trace trace-01-ops: Call of 'valgrind /tmp/qtest.zqtFyF -v 1 -f ./traces/trace-01-ops.cmd' failed: [Errno 2] No such file or directory --- trace-01-ops 0/6 +++ TESTING trace trace-02-ops: Call of 'valgrind /tmp/qtest.zqtFyF -v 1 -f ./traces/trace-02-ops.cmd' failed: [Errno 2] No such file or directory --- trace-02-ops 0/6 +++ TESTING trace trace-03-ops: Call of 'valgrind /tmp/qtest.zqtFyF -v 1 -f ./traces/trace-03-ops.cmd' failed: [Errno 2] No such file or directory --- trace-03-ops 0/6 +++ TESTING trace trace-04-ops: Call of 'valgrind /tmp/qtest.zqtFyF -v 1 -f ./traces/trace-04-ops.cmd' failed: [Errno 2] No such file or directory --- trace-04-ops 0/6 +++ TESTING trace trace-05-ops: Call of 'valgrind /tmp/qtest.zqtFyF -v 1 -f ./traces/trace-05-ops.cmd' failed: [Errno 2] No such file or directory --- trace-05-ops 0/5 +++ TESTING trace trace-06-string: Call of 'valgrind /tmp/qtest.zqtFyF -v 1 -f ./traces/trace-06-string.cmd' failed: [Errno 2] No such file or directory --- trace-06-string 0/6 +++ TESTING trace trace-07-robust: Call of 'valgrind /tmp/qtest.zqtFyF -v 1 -f ./traces/trace-07-robust.cmd' failed: [Errno 2] No such file or directory --- trace-07-robust 0/6 +++ TESTING trace trace-08-robust: Call of 'valgrind /tmp/qtest.zqtFyF -v 1 -f ./traces/trace-08-robust.cmd' failed: [Errno 2] No such file or directory --- trace-08-robust 0/6 +++ TESTING trace trace-09-robust: Call of 'valgrind /tmp/qtest.zqtFyF -v 1 -f ./traces/trace-09-robust.cmd' failed: [Errno 2] No such file or directory --- trace-09-robust 0/6 +++ TESTING trace trace-10-malloc: Call of 'valgrind /tmp/qtest.zqtFyF -v 1 -f ./traces/trace-10-malloc.cmd' failed: [Errno 2] No such file or directory --- trace-10-malloc 0/6 +++ TESTING trace trace-11-malloc: Call of 'valgrind /tmp/qtest.zqtFyF -v 1 -f ./traces/trace-11-malloc.cmd' failed: [Errno 2] No such file or directory --- trace-11-malloc 0/6 +++ TESTING trace trace-12-malloc: Call of 'valgrind /tmp/qtest.zqtFyF -v 1 -f ./traces/trace-12-malloc.cmd' failed: [Errno 2] No such file or directory --- trace-12-malloc 0/6 +++ TESTING trace trace-13-perf: Call of 'valgrind /tmp/qtest.zqtFyF -v 1 -f ./traces/trace-13-perf.cmd' failed: [Errno 2] No such file or directory --- trace-13-perf 0/6 +++ TESTING trace trace-14-perf: Call of 'valgrind /tmp/qtest.zqtFyF -v 1 -f ./traces/trace-14-perf.cmd' failed: [Errno 2] No such file or directory --- trace-14-perf 0/6 +++ TESTING trace trace-15-perf: Call of 'valgrind /tmp/qtest.zqtFyF -v 1 -f ./traces/trace-15-perf.cmd' failed: [Errno 2] No such file or directory --- trace-15-perf 0/6 +++ TESTING trace trace-16-perf: Call of 'valgrind /tmp/qtest.zqtFyF -v 1 -f ./traces/trace-16-perf.cmd' failed: [Errno 2] No such file or directory --- trace-16-perf 0/6 +++ TESTING trace trace-17-complexity: Call of 'valgrind /tmp/qtest.zqtFyF -v 1 -f ./traces/trace-17-complexity.cmd' failed: [Errno 2] No such file or directory --- trace-17-complexity 0/5 --- TOTAL 0/100 Test with specific case by running command: scripts/driver.py -p /tmp/qtest.zqtFyF --valgrind -t <tid> ``` - 後來從 fork 的 repo pull 更新就可執行 ```shell $ git remote add upstream git@github.com:sysprog21/lab0-c.git $ git pull upstream master $ git push origin master ``` - 但是有嚴重錯誤 ```shell $ make valgrind # Explicitly disable sanitizer(s) make clean SANITIZER=0 qtest make[1]: Entering directory '/home/oucs638/GitHub/lab0-c' rm -f qtest.o report.o console.o harness.o queue.o random.o dudect/constant.o dudect/fixture.o dudect/ttest.o .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d *~ qtest /tmp/qtest.* rm -rf .dudect rm -rf *.dSYM (cd traces; rm -f *~) CC qtest.o CC report.o CC console.o CC harness.o CC queue.o CC random.o CC dudect/constant.o CC dudect/fixture.o CC dudect/ttest.o LD qtest make[1]: Leaving directory '/home/oucs638/GitHub/lab0-c' cp qtest /tmp/qtest.gdrzkD chmod u+x /tmp/qtest.gdrzkD sed -i "s/alarm/isnan/g" /tmp/qtest.gdrzkD scripts/driver.py -p /tmp/qtest.gdrzkD --valgrind --- Trace Points +++ TESTING trace trace-01-ops: # Test of insert_head and remove_head --- trace-01-ops 6/6 +++ TESTING trace trace-02-ops: # Test of insert_head, insert_tail, and remove_head --- trace-02-ops 6/6 +++ TESTING trace trace-03-ops: # Test of insert_head, insert_tail, reverse, and remove_head --- trace-03-ops 6/6 +++ TESTING trace trace-04-ops: # Test of insert_head, insert_tail, size, and sort --- trace-04-ops 6/6 +++ TESTING trace trace-05-ops: # Test of insert_head, insert_tail, remove_head, reverse, size, and sort --- trace-05-ops 5/5 +++ TESTING trace trace-06-string: # Test of truncated strings ERROR: Removed value meerkat_panda_squirrel_vultureXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value meerkat_panda_squirrel_vulture ERROR: Removed value aardvark_bear_dolphin_gerbilXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value aardvark_bear_dolphin_gerbil ERROR: Removed value aardvark_bear_dolphinXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value aardvark_bear_dolphin ERROR: Removed value meerkat_panda_squirrelXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value meerkat_panda_squirrel ERROR: Removed value meerkatXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value meerkat Error limit exceeded. Stopping command execution ==7151== 32 bytes in 1 blocks are still reachable in loss record 1 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10B436: malloc_or_fail (report.c:189) ==7151== by 0x10BF48: add_cmd (console.c:123) ==7151== by 0x10C029: init_cmd (console.c:93) ==7151== by 0x10AC52: main (qtest.c:757) ==7151== ==7151== 32 bytes in 1 blocks are still reachable in loss record 2 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10B436: malloc_or_fail (report.c:189) ==7151== by 0x10BF48: add_cmd (console.c:123) ==7151== by 0x10C043: init_cmd (console.c:94) ==7151== by 0x10AC52: main (qtest.c:757) ==7151== ==7151== 32 bytes in 1 blocks are still reachable in loss record 3 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10B436: malloc_or_fail (report.c:189) ==7151== by 0x10BF48: add_cmd (console.c:123) ==7151== by 0x10C05D: init_cmd (console.c:96) ==7151== by 0x10AC52: main (qtest.c:757) ==7151== ==7151== 32 bytes in 1 blocks are still reachable in loss record 4 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10B436: malloc_or_fail (report.c:189) ==7151== by 0x10BF48: add_cmd (console.c:123) ==7151== by 0x10C077: init_cmd (console.c:97) ==7151== by 0x10AC52: main (qtest.c:757) ==7151== ==7151== 32 bytes in 1 blocks are still reachable in loss record 5 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10B436: malloc_or_fail (report.c:189) ==7151== by 0x10BF48: add_cmd (console.c:123) ==7151== by 0x10C091: init_cmd (console.c:99) ==7151== by 0x10AC52: main (qtest.c:757) ==7151== ==7151== 32 bytes in 1 blocks are still reachable in loss record 6 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10B436: malloc_or_fail (report.c:189) ==7151== by 0x10BF48: add_cmd (console.c:123) ==7151== by 0x10C0AB: init_cmd (console.c:100) ==7151== by 0x10AC52: main (qtest.c:757) ==7151== ==7151== 32 bytes in 1 blocks are still reachable in loss record 7 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10B436: malloc_or_fail (report.c:189) ==7151== by 0x10BF48: add_cmd (console.c:123) ==7151== by 0x10C0C5: init_cmd (console.c:101) ==7151== by 0x10AC52: main (qtest.c:757) ==7151== ==7151== 32 bytes in 1 blocks are still reachable in loss record 8 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10B436: malloc_or_fail (report.c:189) ==7151== by 0x10BF48: add_cmd (console.c:123) ==7151== by 0x10AC6C: console_init (qtest.c:82) ==7151== by 0x10AC6C: main (qtest.c:758) ==7151== ==7151== 32 bytes in 1 blocks are still reachable in loss record 9 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10B436: malloc_or_fail (report.c:189) ==7151== by 0x10BF48: add_cmd (console.c:123) ==7151== by 0x10AC86: console_init (qtest.c:83) ==7151== by 0x10AC86: main (qtest.c:758) ==7151== ==7151== 32 bytes in 1 blocks are still reachable in loss record 10 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10B436: malloc_or_fail (report.c:189) ==7151== by 0x10BF48: add_cmd (console.c:123) ==7151== by 0x10ACA0: console_init (qtest.c:84) ==7151== by 0x10ACA0: main (qtest.c:758) ==7151== ==7151== 32 bytes in 1 blocks are still reachable in loss record 11 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10B436: malloc_or_fail (report.c:189) ==7151== by 0x10BF48: add_cmd (console.c:123) ==7151== by 0x10ACBA: console_init (qtest.c:87) ==7151== by 0x10ACBA: main (qtest.c:758) ==7151== ==7151== 32 bytes in 1 blocks are still reachable in loss record 12 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10B436: malloc_or_fail (report.c:189) ==7151== by 0x10BF48: add_cmd (console.c:123) ==7151== by 0x10ACD4: console_init (qtest.c:90) ==7151== by 0x10ACD4: main (qtest.c:758) ==7151== ==7151== 32 bytes in 1 blocks are still reachable in loss record 13 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10B436: malloc_or_fail (report.c:189) ==7151== by 0x10BF48: add_cmd (console.c:123) ==7151== by 0x10ACEE: console_init (qtest.c:93) ==7151== by 0x10ACEE: main (qtest.c:758) ==7151== ==7151== 32 bytes in 1 blocks are still reachable in loss record 14 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10B436: malloc_or_fail (report.c:189) ==7151== by 0x10BF48: add_cmd (console.c:123) ==7151== by 0x10AD08: console_init (qtest.c:96) ==7151== by 0x10AD08: main (qtest.c:758) ==7151== ==7151== 32 bytes in 1 blocks are still reachable in loss record 15 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10B436: malloc_or_fail (report.c:189) ==7151== by 0x10BF48: add_cmd (console.c:123) ==7151== by 0x10AD22: console_init (qtest.c:97) ==7151== by 0x10AD22: main (qtest.c:758) ==7151== ==7151== 32 bytes in 1 blocks are still reachable in loss record 16 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10B436: malloc_or_fail (report.c:189) ==7151== by 0x10BF48: add_cmd (console.c:123) ==7151== by 0x10AD3C: console_init (qtest.c:98) ==7151== by 0x10AD3C: main (qtest.c:758) ==7151== ==7151== 32 bytes in 1 blocks are still reachable in loss record 17 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10B436: malloc_or_fail (report.c:189) ==7151== by 0x10BF48: add_cmd (console.c:123) ==7151== by 0x10AD56: console_init (qtest.c:100) ==7151== by 0x10AD56: main (qtest.c:758) ==7151== ==7151== 40 bytes in 1 blocks are still reachable in loss record 18 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10B436: malloc_or_fail (report.c:189) ==7151== by 0x10BFBE: add_param (console.c:144) ==7151== by 0x10C0E4: init_cmd (console.c:102) ==7151== by 0x10AC52: main (qtest.c:757) ==7151== ==7151== 40 bytes in 1 blocks are still reachable in loss record 19 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10B436: malloc_or_fail (report.c:189) ==7151== by 0x10BFBE: add_param (console.c:144) ==7151== by 0x10C103: init_cmd (console.c:104) ==7151== by 0x10AC52: main (qtest.c:757) ==7151== ==7151== 40 bytes in 1 blocks are still reachable in loss record 20 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10B436: malloc_or_fail (report.c:189) ==7151== by 0x10BFBE: add_param (console.c:144) ==7151== by 0x10C122: init_cmd (console.c:105) ==7151== by 0x10AC52: main (qtest.c:757) ==7151== ==7151== 40 bytes in 1 blocks are still reachable in loss record 21 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10B436: malloc_or_fail (report.c:189) ==7151== by 0x10BFBE: add_param (console.c:144) ==7151== by 0x10C141: init_cmd (console.c:106) ==7151== by 0x10AC52: main (qtest.c:757) ==7151== ==7151== 40 bytes in 1 blocks are still reachable in loss record 22 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10B436: malloc_or_fail (report.c:189) ==7151== by 0x10BFBE: add_param (console.c:144) ==7151== by 0x10AD75: console_init (qtest.c:101) ==7151== by 0x10AD75: main (qtest.c:758) ==7151== ==7151== 40 bytes in 1 blocks are still reachable in loss record 23 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10B436: malloc_or_fail (report.c:189) ==7151== by 0x10BFBE: add_param (console.c:144) ==7151== by 0x10AD94: console_init (qtest.c:103) ==7151== by 0x10AD94: main (qtest.c:758) ==7151== ==7151== 40 bytes in 1 blocks are still reachable in loss record 24 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10B436: malloc_or_fail (report.c:189) ==7151== by 0x10BFBE: add_param (console.c:144) ==7151== by 0x10ADB3: console_init (qtest.c:105) ==7151== by 0x10ADB3: main (qtest.c:758) ==7151== ==7151== 56 bytes in 1 blocks are still reachable in loss record 25 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10C739: test_malloc (harness.c:137) ==7151== by 0x10CEAB: q_insert_tail (queue.c:85) ==7151== by 0x10A548: do_insert_tail (qtest.c:297) ==7151== by 0x10B938: interpret_cmda (console.c:220) ==7151== by 0x10BEAC: interpret_cmd (console.c:243) ==7151== by 0x10C47A: cmd_select (console.c:571) ==7151== by 0x10C6C2: run_console (console.c:630) ==7151== by 0x10ADE7: main (qtest.c:770) ==7151== ==7151== 64 bytes in 1 blocks are still reachable in loss record 26 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10C739: test_malloc (harness.c:137) ==7151== by 0x10CD77: q_new (queue.c:14) ==7151== by 0x10A945: do_new (qtest.c:124) ==7151== by 0x10B938: interpret_cmda (console.c:220) ==7151== by 0x10BEAC: interpret_cmd (console.c:243) ==7151== by 0x10C47A: cmd_select (console.c:571) ==7151== by 0x10C6C2: run_console (console.c:630) ==7151== by 0x10ADE7: main (qtest.c:770) ==7151== ==7151== 76 bytes in 1 blocks are still reachable in loss record 27 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10C739: test_malloc (harness.c:137) ==7151== by 0x10CED3: q_insert_tail (queue.c:89) ==7151== by 0x10A548: do_insert_tail (qtest.c:297) ==7151== by 0x10B938: interpret_cmda (console.c:220) ==7151== by 0x10BEAC: interpret_cmd (console.c:243) ==7151== by 0x10C47A: cmd_select (console.c:571) ==7151== by 0x10C6C2: run_console (console.c:630) ==7151== by 0x10ADE7: main (qtest.c:770) ==7151== ==7151== 112 bytes in 2 blocks are still reachable in loss record 28 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10C739: test_malloc (harness.c:137) ==7151== by 0x10CDC3: q_insert_head (queue.c:49) ==7151== by 0x10A7CF: do_insert_head (qtest.c:212) ==7151== by 0x10B938: interpret_cmda (console.c:220) ==7151== by 0x10BEAC: interpret_cmd (console.c:243) ==7151== by 0x10C47A: cmd_select (console.c:571) ==7151== by 0x10C6C2: run_console (console.c:630) ==7151== by 0x10ADE7: main (qtest.c:770) ==7151== ==7151== 152 bytes in 2 blocks are still reachable in loss record 29 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10C739: test_malloc (harness.c:137) ==7151== by 0x10CDEB: q_insert_head (queue.c:53) ==7151== by 0x10A7CF: do_insert_head (qtest.c:212) ==7151== by 0x10B938: interpret_cmda (console.c:220) ==7151== by 0x10BEAC: interpret_cmd (console.c:243) ==7151== by 0x10C47A: cmd_select (console.c:571) ==7151== by 0x10C6C2: run_console (console.c:630) ==7151== by 0x10ADE7: main (qtest.c:770) ==7151== ==7151== 8,216 bytes in 1 blocks are still reachable in loss record 30 of 30 ==7151== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==7151== by 0x10B436: malloc_or_fail (report.c:189) ==7151== by 0x10BA86: push_file (console.c:448) ==7151== by 0x10C682: run_console (console.c:624) ==7151== by 0x10ADE7: main (qtest.c:770) ==7151== --- trace-06-string 0/6 +++ TESTING trace trace-07-robust: # Test operations on NULL queue --- trace-07-robust 6/6 +++ TESTING trace trace-08-robust: # Test operations on empty queue --- trace-08-robust 6/6 +++ TESTING trace trace-09-robust: # Test remove_head with NULL argument --- trace-09-robust 6/6 +++ TESTING trace trace-10-malloc: # Test of malloc failure on new --- trace-10-malloc 6/6 +++ TESTING trace trace-11-malloc: # Test of malloc failure on insert_head --- trace-11-malloc 6/6 +++ TESTING trace trace-12-malloc: # Test of malloc failure on insert_tail --- trace-12-malloc 6/6 +++ TESTING trace trace-13-perf: # Test performance of insert_tail --- trace-13-perf 6/6 +++ TESTING trace trace-14-perf: # Test performance of size --- trace-14-perf 6/6 +++ TESTING trace trace-15-perf: # Test performance of insert_tail, size, reverse, and sort --- trace-15-perf 6/6 +++ TESTING trace trace-16-perf: # Test performance of sort with random and descending orders # 10000: all correct sorting algorithms are expected pass # 50000: sorting algorithms with O(n^2) time complexity are expected failed # 100000: sorting algorithms with O(nlogn) time complexity are expected pass --- trace-16-perf 6/6 +++ TESTING trace trace-17-complexity: # Test if q_insert_tail and q_size is constant time complexity Probably constant time Probably constant time --- trace-17-complexity 5/5 --- TOTAL 94/100 Test with specific case by running command: scripts/driver.py -p /tmp/qtest.gdrzkD --valgrind -t <tid> ``` - 研判可能是在處理字串時，尾端並未妥善處理 - 修改 `q_insert_head`, `q_insert_tail`, `q_remove_head` - 最後發現在 `q_remove_head` 中，需要將 `sp` 的空間先全部以 `\0` 填滿 - 確保在寫入新字串後，剩下的空間不會出現亂碼 - 修改部份更新在上方實作說明的部份 - 修改後通過 `make valgrind` ```shell $ make valgrind # Explicitly disable sanitizer(s) make clean SANITIZER=0 qtest make[1]: Entering directory '/home/oucs638/GitHub/lab0-c' rm -f qtest.o report.o console.o harness.o queue.o random.o dudect/constant.o dudect/fixture.o dudect/ttest.o .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d *~ qtest /tmp/qtest.* rm -rf .dudect rm -rf *.dSYM (cd traces; rm -f *~) CC qtest.o CC report.o CC console.o CC harness.o CC queue.o CC random.o CC dudect/constant.o CC dudect/fixture.o CC dudect/ttest.o LD qtest make[1]: Leaving directory '/home/oucs638/GitHub/lab0-c' cp qtest /tmp/qtest.yCE5pu chmod u+x /tmp/qtest.yCE5pu sed -i "s/alarm/isnan/g" /tmp/qtest.yCE5pu scripts/driver.py -p /tmp/qtest.yCE5pu --valgrind --- Trace Points +++ TESTING trace trace-01-ops: # Test of insert_head and remove_head --- trace-01-ops 6/6 +++ TESTING trace trace-02-ops: # Test of insert_head, insert_tail, and remove_head --- trace-02-ops 6/6 +++ TESTING trace trace-03-ops: # Test of insert_head, insert_tail, reverse, and remove_head --- trace-03-ops 6/6 +++ TESTING trace trace-04-ops: # Test of insert_head, insert_tail, size, and sort --- trace-04-ops 6/6 +++ TESTING trace trace-05-ops: # Test of insert_head, insert_tail, remove_head, reverse, size, and sort --- trace-05-ops 5/5 +++ TESTING trace trace-06-string: # Test of truncated strings --- trace-06-string 6/6 +++ TESTING trace trace-07-robust: # Test operations on NULL queue --- trace-07-robust 6/6 +++ TESTING trace trace-08-robust: # Test operations on empty queue --- trace-08-robust 6/6 +++ TESTING trace trace-09-robust: # Test remove_head with NULL argument --- trace-09-robust 6/6 +++ TESTING trace trace-10-malloc: # Test of malloc failure on new --- trace-10-malloc 6/6 +++ TESTING trace trace-11-malloc: # Test of malloc failure on insert_head --- trace-11-malloc 6/6 +++ TESTING trace trace-12-malloc: # Test of malloc failure on insert_tail --- trace-12-malloc 6/6 +++ TESTING trace trace-13-perf: # Test performance of insert_tail --- trace-13-perf 6/6 +++ TESTING trace trace-14-perf: # Test performance of size --- trace-14-perf 6/6 +++ TESTING trace trace-15-perf: # Test performance of insert_tail, size, reverse, and sort --- trace-15-perf 6/6 +++ TESTING trace trace-16-perf: # Test performance of sort with random and descending orders # 10000: all correct sorting algorithms are expected pass # 50000: sorting algorithms with O(n^2) time complexity are expected failed # 100000: sorting algorithms with O(nlogn) time complexity are expected pass --- trace-16-perf 6/6 +++ TESTING trace trace-17-complexity: # Test if q_insert_tail and q_size is constant time complexity Probably constant time Probably constant time --- trace-17-complexity 5/5 --- TOTAL 100/100 Test with specific case by running command: scripts/driver.py -p /tmp/qtest.yCE5pu --valgrind -t <tid> ``` - - - ## Dude, is my code constant time? ### 前置說明 - [原文連結](https://eprint.iacr.org/2016/1123.pdf) - `dudect` 會先將輸入的測試資料定義成兩個不同的 `class` - `fix` - Fixed to a constant value - Might be choosen to trigger certain "special" conrner-case processing - `random` - Choosen at random for each measurement - 利用 cycle counters 來衡量執行時間 - Modern CPUs provide cycle counters, that can be used to accurately acquire execution time measurements - TSC register in the x86 family - systick peripheral avaiable in ARM - 為了降低測試環境的硬體影響因素，輸入測試資料的工作會優先於執行時間的計算 - To minimize the effect of environmental changes in the results, each measurement corresponds to a randomly choosen. - The class assignment and input preparation tasks are performed prior to the measurement phase. - 統計出來的資料在分析之前會經過一些修正 - Cropping - 排除因為 OS 或其他系統因素導致的不合理極端值 - Higher-order preprocessing - 根據採用不同的 statistical test 而對統計數據做不同的預處理 - Depending on the statistical test applied, it may be beneficial to apply some higherorder pre-processing, such as centered product mimicking higher-order DPA attacks. Higher-order leakage detection tests already appeared in other contexts. - 用 statistical test 反證出兩種結果的時間分佈是相同的 - t-test : 例如 Welch's u-test - Non-parametric tests : 例如 Kolmogorov-Smirnov ### 驗證實現 - [原始碼](https://github.com/oreparaz/dudect) - 觀察 `lab0-c/dudect/fixture.c` 中 `doit` 函式 - 可以看到 `line 15 to line 19` 呼叫函式執行了主要的流程 - 其中在 `measure` 函式中，紀錄了執行操作前後的 `clock` ，用以計算花費的 `cycle` 數 ```cpp= static bool doit(int mode) { int64_t *before_ticks = calloc(number_measurements + 1, sizeof(int64_t)); int64_t *after_ticks = calloc(number_measurements + 1, sizeof(int64_t)); int64_t *exec_times = calloc(number_measurements, sizeof(int64_t)); uint8_t *classes = calloc(number_measurements, sizeof(uint8_t)); uint8_t *input_data = calloc(number_measurements * chunk_size, sizeof(uint8_t)); if (!before_ticks || !after_ticks || !exec_times || !classes || !input_data) { die(); } prepare_inputs(input_data, classes); measure(before_ticks, after_ticks, input_data, mode); differentiate(exec_times, before_ticks, after_ticks); update_statistics(exec_times, classes); bool ret = report(); free(before_ticks); free(after_ticks); free(exec_times); free(classes); free(input_data); return ret; } ``` - 再來觀察 `lab0-c/dudect/constant.c` 中 `measure` 函式 - 一開始我不知道 `assert` 函式用途，翻閱 [C99 規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)後，發現是用確保給定的 `expression` 結果為 `true` ，否則報錯顯示中止錯誤訊息 - 可以看到 `line 14 to line 16` 和 `line 25 to line 27` ，皆依序紀錄執行函式前的 `cpucycles` 、執行函式、紀錄執行函式後的 `cpucycles` ```cpp= void measure(int64_t *before_ticks, int64_t *after_ticks, uint8_t *input_data, int mode) { assert(mode == test_insert_tail || mode == test_size); if (mode == test_insert_tail) { for (size_t i = drop_size; i < number_measurements - drop_size; i++) { char *s = get_random_string(); dut_new(); dut_insert_head( get_random_string(), *(uint16_t *) (input_data + i * chunk_size) % 10000); before_ticks[i] = cpucycles(); dut_insert_tail(s, 1); after_ticks[i] = cpucycles(); dut_free(); } } else { for (size_t i = drop_size; i < number_measurements - drop_size; i++) { dut_new(); dut_insert_head( get_random_string(), *(uint16_t *) (input_data + i * chunk_size) % 10000); before_ticks[i] = cpucycles(); dut_size(1); after_ticks[i] = cpucycles(); dut_free(); } } } ``` - 最後觀察在 `lab0-c/dudect/fixture.c` 判定是否為 `constant time` 的 `report` 函式 - 預設的測試樣本數為 `10000` - 原始的程式碼中以有差異的比例到達 $\frac{500}{10000} = 0.05$ 以及 $\frac{10}{10000} = 0.001$ 作為分類標準 - `lab0-c` 中，要求相同的比例要達到 $99.9\%$ ，才認定為 `constant time` ```cpp= static bool report(void) { double max_t = fabs(t_compute(t)); double number_traces_max_t = t->n[0] + t->n[1]; double max_tau = max_t / sqrt(number_traces_max_t); printf("\033[A\033[2K"); printf("meas: %7.2lf M, ", (number_traces_max_t / 1e6)); if (number_traces_max_t < enough_measurements) { printf("not enough measurements (%.0f still to go).\n", enough_measurements - number_traces_max_t); return false; } /* * max_t: the t statistic value * max_tau: a t value normalized by sqrt(number of measurements). * this way we can compare max_tau taken with different * number of measurements. This is sort of "distance * between distributions", independent of number of * measurements. * (5/tau)^2: how many measurements we would need to barely * detect the leak, if present. "barely detect the * leak" = have a t value greater than 5. */ printf("max t: %+7.2f, max tau: %.2e, (5/tau)^2: %.2e.\n", max_t, max_tau, (double) (5 * 5) / (double) (max_tau * max_tau)); if (max_t > t_threshold_bananas) { return false; } else if (max_t > t_threshold_moderate) { return false; } else { /* max_t < t_threshold_moderate */ return true; } } ``` - - - ## 解釋 select 系統呼叫本程式的使用方式，並分析 `console.c` - [select 系統](http://man7.org/linux/man-pages/man2/select.2.html) - [console.c](https://github.com/sysprog21/lab0-c/blob/master/console.c) - Linux Programmer's Manual 中對 `select` 的描述如下： > select() and pselect() allow a program to monitor multiple file descriptors, waiting until one or more of the file descriptors become "ready" for some class of I/O operation (e.g., input possible). A file descriptor is considered ready if it is possible to perform a corresponding I/O operation (e.g., read(2), or a sufficiently small write(2)) without blocking. - 依據說明， `select` 會監控檔案描述符 (file descriptors) ，確認程式準備好可以做 `I/O-operation` ，才執行程式 - 在 `lab0-c/console.c` 中， `cmd_select` 中使用了 `select` - 多增加了 `command input` 在 `internal buffer` 的讀寫是否可執行 ```cpp= /* * Handle command processing in program that uses select as main control loop. * Like select, but checks whether command input either present in internal * buffer * or readable from command input. If so, that command is executed. * Same return as select. Command input file removed from readfds * * nfds should be set to the maximum file descriptor for network sockets. * If nfds == 0, this indicates that there is no pending network activity */ int cmd_select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout) { char *cmdline; int infd; fd_set local_readset; while (!block_flag && read_ready()) { cmdline = readline(); interpret_cmd(cmdline); prompt_flag = true; } if (cmd_done()) return 0; if (!block_flag) { /* Process any commands in input buffer */ if (!readfds) readfds = &local_readset; /* Add input fd to readset for select */ infd = buf_stack->fd; FD_SET(infd, readfds); if (infd == STDIN_FILENO && prompt_flag) { printf("%s", prompt); fflush(stdout); prompt_flag = true; } if (infd >= nfds) nfds = infd + 1; } if (nfds == 0) return 0; int result = select(nfds, readfds, writefds, exceptfds, timeout); if (result <= 0) return result; infd = buf_stack->fd; if (readfds && FD_ISSET(infd, readfds)) { /* Commandline input available */ FD_CLR(infd, readfds); result--; cmdline = readline(); if (cmdline) interpret_cmd(cmdline); } return result; } ``` - `lab0-c/console.c` 中使用 [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 的原因 - 避免沒有完整讀取輸入的資料 - 直接使用 `internal buffer` 增加 `read text line` 速度 - 讀取的中止條件 - 已讀取的 bytes 到達 `RIO_BUFSIZE` (`maxlen` bytes read) - 遇到 `EOF` - 遇到 `'\n'` - - -
Last changed by  
 
Ralph Ou
405

Read more

2022q1 Homework6 (ktcp)

Contributed by < oucs638 > Requirements: ktcp GitHub: kecho, khttpd 實驗環境 $ gcc --version gcc (Ubuntu 9.4.0-1ubuntu1~20.04) 9.4.0 $ lscpu

5/15/2022
2022q1 Homework6 (sehttpd)

Contributed by < oucs638 > Requirements: sehttpd GitHub: sehttpd 實驗環境 $ gcc --version gcc (Ubuntu 9.4.0-1ubuntu1~20.04) 9.4.0 $ lscpu Architecture: x86_64

4/25/2022
2020q1 Final Project Linux `/dev/dem` 裝置

contributed by < oucs638 > 作業說明 Linux 核心的 /dev/mem 裝置 開發環境 作業系統

6/26/2020
2020q1 Homework2 (fibdrv)

contributed by < oucs638 > 作業說明 fibdriv 開發環境 $ uname -a Linux oucs638-ROG-Strix-G731GU-G731GU 5.3.0-40-generic #32~18.04.1-Ubuntu SMP Mon Feb 3 14:05:59 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

3/13/2020
Read more from Ralph Ou
Published on HackMD