# 2020q1 Homework1 (lab0)
contributed by < `fwfly` >

## Sort
因為上次有寫過這份作業，所以知道會有超過 10000 筆的資料要排序．因此採用 Merge sort.
比對的部分則是參考 [natsort](https://github.com/sourcefrog/natsort)

原則上 英文 > 數字
所以分成三種情形
1. 英文(包含數字)比對
2. 數字比對
3. 浮點數比對

#### 英文比對
直接比對大小．如果是英文跟數字，數字永遠最小
#### 數字比對
從左到右比對數字大小，然後再比對數字長度．比較長則較大
#### 浮點數比對
從左到右比對數字，只要其中一個數字較大，則為大

原始程式是用 strcasecmp 但是這個 function 出來的結果跟 natural sort 不太ㄧ樣，
所以直接使用自己寫的 compare function 替換掉，不知道會不會增加額外的測試成本

## make test 結果
移除掉會造成效能問題的 print_list function 之後就完整個跑完 17 項測試結果

## 濾掉 ld-musl leak error
如果使用 alpinelinux 做開發，valgrind 便會出現以下 ld-musl leak

adminuser:~/lab0-c$ make
  CC	queue.o
  LD	qtest
adminuser:~/lab0-c$ valgrind ./qtest
cmd> quit
cmd> quit
Freeing queue
q_free
==15401== 16 bytes in 2 blocks are still reachable in loss record 1 of 3
==15401==    at 0x48A06F2: calloc (vg_replace_malloc.c:762)
==15401==    by 0x4058BCB: ??? (in /lib/ld-musl-x86_64.so.1)
==15401==
.....
==15401== 420 bytes in 1 blocks are still reachable in loss record 3 of 3
==15401==    at 0x48A06F2: calloc (vg_replace_malloc.c:762)
==15401==    by 0x4058993: ??? (in /lib/ld-musl-x86_64.so.1)
==15401==    by 0x4059609: __dls3 (in /lib/ld-musl-x86_64.so.1)
==15401==    by 0xDEF5300BF07D54D5: ???
==15401==    by 0x74736574712F2E7A: ???
==15401==    by 0x34365F363877FF: ???
==15401==

在去年 9月有人做了一個 patch.
https://github.com/alpinelinux/aports/pull/8779
細節原因不是非常清楚，目前大多數人都是透過 suppressions file 隱藏掉這個 leak.

### suppressions file
可以透過 suppressions file 去 filter 掉不必要的 leak 資訊．
原則上上面的 valgrid issue 應該已經被 patch 掉．

以下為 supp 的內容 /usr/lib/valgrind/default.supp
可以看到 musl lib 的 __dls3 已經被 filter 掉．
但是執行時卻還是看得到這個 issue.

# Suppressions for musl libc
# See: https://www.openwall.com/lists/musl/2017/06/15/4

{
   musl-dynlink-false-positive1
   Memcheck:Leak
   fun:calloc
   fun:load_direct_deps
   fun:load_deps
   fun:load_deps
   fun:__dls3
   fun:__dls2b
   fun:__dls2
}
.....

基本上 valgrind 的 map 滿死的，stack 必須要完全依樣才能夠 filter 掉．
所以可以透過 ```--gen-suppressions=yes``` 找出需要 patch 的內容．
則會出現以下內容

valgrind --leak-check=full --show-leak-kinds=all  --gen-suppressions=yes ./a.out
-10-1-1==4341==
==4341== HEAP SUMMARY:
==4341==     in use at exit: 468 bytes in 4 blocks
==4341==   total heap usage: 5 allocs, 1 frees, 508 bytes allocated
==4341==
==4341== 16 bytes in 2 blocks are still reachable in loss record 1 of 3
==4341==    at 0x48A16F2: calloc (vg_replace_malloc.c:762)
==4341==    by 0x4059056: ??? (in /lib/ld-musl-x86_64.so.1)
==4341==
==4341==
==4341== ---- Print suppression ? --- [Return/N/n/Y/y/C/c] ---- y
{
   <insert_a_suppression_name_here>
   Memcheck:Leak
   match-leak-kinds: reachable
   fun:calloc
   obj:/lib/ld-musl-x86_64.so.1
}

再把大括弧內的內容複製到 /usr/lib/valgrind/default.supp 中
然後重新執行一次，就可以發現 leak 消失了．
同時會看到 ```suppressed: 468 bytes in 4 blocks```

adminuser:~/w3$ valgrind --leak-check=full --show-leak-kinds=all  --gen-suppressions=yes ./a.out
==4350== Memcheck, a memory error detector
==4350== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==4350== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==4350== Command: ./a.out
==4350==
-10-1-1==4350==
==4350== HEAP SUMMARY:
==4350==     in use at exit: 468 bytes in 4 blocks
==4350==   total heap usage: 5 allocs, 1 frees, 508 bytes allocated
==4350==
==4350== LEAK SUMMARY:
==4350==    definitely lost: 0 bytes in 0 blocks
==4350==    indirectly lost: 0 bytes in 0 blocks
==4350==      possibly lost: 0 bytes in 0 blocks
==4350==    still reachable: 0 bytes in 0 blocks
==4350==         suppressed: 468 bytes in 4 blocks
==4350==
==4350== For lists of detected and suppressed errors, rerun with: -s
==4350== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

參考 ： https://blog.csdn.net/u010168781/article/details/83547788

## make valgrind
在 valgrind 的測試下會導致執行速度太慢，因為是 VM 的關係，所以可能效能不太好．

adminuser:~/lab0-c$ valgrind ./qtest
cmd> new
cmd> new
q = []
cmd> ih dolphin 1000000
cmd> ih dolphin 1000000
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
Insertion of dolphin failed
q = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> quit
cmd> quit
Freeing queue
ERROR: Freed queue, but 1 blocks are still allocated
==5081== 48 bytes in 1 blocks are definitely lost in loss record 3 of 5
==5081==    at 0x489F72A: malloc (vg_replace_malloc.c:309)
==5081==    by 0x10D59D: test_malloc (harness.c:138)
==5081==    by 0x10DA55: q_insert_head (queue.c:63)
==5081==    by 0x10B6F3: do_insert_head (qtest.c:211)
==5081==    by 0x10C7E5: interpret_cmda (console.c:220)
==5081==    by 0x10CD5C: interpret_cmd (console.c:243)
==5081==    by 0x10D40E: cmd_select (console.c:607)
==5081==    by 0x10D52F: run_console (console.c:628)
==5081==    by 0x10BCAE: main (qtest.c:772)
==5081==

### massif
#### preparation
安裝 perl

sudo apk add perl

#### 測試

## Select
* 解釋 select 系統呼叫在本程式的使用方式
* 比照 qtest 實作，撰寫獨立的終端機命令解譯器