# 2018q1 Homework2 (prefix-search)
contributed by <`bauuuu1021`>
###### tags: `bauuuu1021`, `sysprog`
## 開發環境
```
bauuuu1021@X555LB:~$ lscpu
Architecture: x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
每核心執行緒數：2
每通訊端核心數：2
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 61
Model name: Intel(R) Core(TM) i5-5200U CPU @ 2.20GHz
製程： 4
CPU MHz： 2196.790
CPU max MHz: 2700.0000
CPU min MHz: 500.0000
BogoMIPS: 4393.58
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 3072K
NUMA node0 CPU(s): 0-3
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsrsse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc 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 aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb invpcid_single pti retpoline intel_pt tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid rdseed adx smap xsaveopt dtherm ida arat pln pts
```
## 理解程式碼
* 變數定義
* INS = REF = 0
* DEL = CPY = 1
* tst_ins_del() 中
* 傳入的字串 s 有出現在樹中
* del != 0 : 刪除字串
* del == 0 : refcnt+1
* 傳入的字串 s 沒有出現在樹中
* cpy != 0 : allocate storage for 's'
* cpy == 0 : save pointer to 's'
* 傳入參數 char* const* s
* [reference](http://www.cplusplus.com/forum/unices/51539/)
* s 為一個 pointer to a "const pointer to char"
* gdb 結果
```
(gdb) p s
$9 = (char * const *) 0x7fffffffb9a0
(gdb) p *s
$10 = 0x7fffffffd9f0 "Shanghai,"
(gdb) p **s
$11 = 83 'S'
(gdb) p *p
$12 = 83 'S'
(gdb) p p
$13 = 0x7fffffffd9f0 "Shanghai,"
```
## Prefix 缺陷
### 搜尋城市名問題
* [Github](https://github.com/bauuuu1021/prefix-search/commit/b9c2f1ce6ecfabd562246c1d194cfeb3ee47e0b5)
* 因為 input 檔中都是 `城市`, `國家`，導致搜尋城市時如果不加 "," 就找不到
```
choice: f
find word in tree: Tainan
Tainan not found.
Commands:
a add word to the tree
f find word in tree
s search words matching prefix
d delete word from the tree
q quit, freeing all data
choice: f
find word in tree: Tainan,
found Tainan, in 0.000003 sec.
```
* 仿造 rmcrlf() 寫了一個 addComma() ，當第一次搜尋不到時會在字尾加逗號再搜一次，結果如下
```
choice: f
find word in tree: Tainan
found Tainan, in 0.000001 sec.
```
### 刪除不存在的字串會變成輸入
* [Github](https://github.com/bauuuu1021/prefix-search/commit/9b49b99beeca1be4c91bc0d3b480970d3966ea5f)
* 例如：
```
choice: d
enter word to del: aaaaaa
deleting aaaaaa
delete failed.
Commands:
a add word to the tree
f find word in tree
s search words matching prefix
d delete word from the tree
q quit, freeing all data
choice: f
find word in tree: aaaaaa
found aaaaaa in 0.000004 sec.
```
* 發現是在執行 tst_ins_del() 時，只要字串原本不存在就會 insert
* 要是刪除時發現沒有這個字串，就跳出不下執行
```
choice: d
enter word to del: aaaaaa
deleting aaaaaa
delete failed.
Commands:
a add word to the tree
f find word in tree
s search words matching prefix
d delete word from the tree
q quit, freeing all data
choice: f
find word in tree: aaaaaa
aaaaaa not found.
```
## 修改 FIXME
### 更改 tst_ins_del() 的參數
* 發現 fix me 註解後接的都是 tst_ins_del() 這個 function，這個函式的前三個參數跟功能有關，應該不能更動。所以將第四個參數改成 REF
```
choice: s
find words matching prefix (at least 1 char): Tai
Tai - searched prefix in 0.000685 sec
suggest[0] : Tai
suggest[1] : Tai
suggest[2] : Tai
suggest[3] : Tai
suggest[4] : Tai
suggest[5] : Tai
suggest[6] : Tai
suggest[7] : Tai
.
.
.
.
suggest[970] : Tai
```
* 結果全部建議字串都 == 輸入字串
* 而且結束 (q) 會跳 core dumped
```
choice: q
*** Error in `./test_ref': free(): invalid pointer: 0x00007ffc61cf3c20 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x777e5)[0x7fb9feb987e5]
/lib/x86_64-linux-gnu/libc.so.6(+0x8037a)[0x7fb9feba137a]
/lib/x86_64-linux-gnu/libc.so.6(cfree+0x4c)[0x7fb9feba553c]
./test_ref[0x4020d1]
./test_ref[0x4020a6]
.......
(中略)
.......
./test_ref[0x401226]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0)[0x7fb9feb41830]
./test_ref[0x4008e9]
======= Memory map: ========
00400000-00403000 r-xp 00000000 08:14 133834 /home/bauuuu1021/prefix-search/test_ref
00602000-00603000 r--p 00002000 08:14 133834 /home/bauuuu1021/prefix-search/test_ref
00603000-00604000 rw-p 00003000 08:14 133834 /home/bauuuu1021/prefix-search/test_ref
01827000-02f3a000 rw-p 00000000 00:00 0 [heap]
7fb9f8000000-7fb9f8021000 rw-p 00000000 00:00 0
7fb9f8021000-7fb9fc000000 ---p 00000000 00:00 0
......
(中略)
......
7ffc61d55000-7ffc61d57000 r-xp 00000000 00:00 0 [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0 [vsyscall]
已經終止 (core dumped)
```
* 參考 [HTYISABUG](https://hackmd.io/s/BkiEdEj3-) 同學的方法，將`case 'q':` 中 tst_free_all(root) 改成 tst_free(root) 即解決。在 tst.c 中，兩個函式只差前者多了這兩行
```C=
if (!p->key)
free(p->eqkid);
```
* 因此推斷是在 free() 的時候出問題，因此在 free() 前後各加上一個 printf()，結果只有前面的字串印出，所以確認為 free() 的時候出問題
```
choice: q
before free
*** Error in `./test_ref': free(): invalid pointer: 0x00007ffe30083650 ***
```
> 早安
> [name=ryanpatiency][color=red]
>>[color=blue]ㄜ...早安?[name=bauuuu1021]
### 使用 GDB 觀察
* 決定使用 gdb 看一下，以下紀錄一些本來不了解的指令
* 在其他檔案設中斷點 : (gdb)b `file.c` : `line or func()`
* 逐行執行 : (gdb)s
* 現在位置 : (gdb)frame
* 在使用 gdb 的過程中，執行到有關進入檔案系統或是 malloc 就會有以下情形，所以要把中斷點設在開檔或配置記憶體後面，不然會花很多時間跳過
```
230 if (!root || !*s)
(gdb)
232 if (strlen(*s) + 1 > STKMAX / 2) /* limit length to 1/2 STKMAX */
(gdb)
strlen () at ../sysdeps/x86_64/strlen.S:66
66 ../sysdeps/x86_64/strlen.S: 沒有此一檔案或目錄.
(gdb)
67 in ../sysdeps/x86_64/strlen.S
(gdb)
68 in ../sysdeps/x86_64/strlen.S
(gdb)
69 in ../sysdeps/x86_64/strlen.S
(gdb)
70 in ../sysdeps/x86_64/strlen.S
(gdb)
71 in ../sysdeps/x86_64/strlen.S
(gdb)
72 in ../sysdeps/x86_64/strlen.S
(gdb)
74 in ../sysdeps/x86_64/strlen.S
(gdb)
...
...
...
```
* test_ref
```
(gdb) p sgl
$3 = {0x7fffffffd9f0 "Tai" <repeats 971 times>, 0x0 <repeats 53 times>}
```
* test_cpy
```
(gdb) p sgl
$1 = {0x60ae80 "Tai’an,", 0xaf5cf0 "Tai,", 0x1a4dae0 "Taibon", 0x70fca0 "Taicheng,", 0x62d980 "Taichung,",
0x61ef60 "Taiden,", 0x1279cf0 "Taigum,", 0x895a10 "Taikang,", 0x82e830 "Tailai,", 0x19c74d0 "Taillades,",
0xf8b080 "Taillan-Médoc,", 0x1e22410 "Taillecourt,", 0x1562640 "Tain,", 0x63b580 "Tainan,", 0x15e2d80 "Taino,",
0x1891800 "Tainter", 0x1bf6ae0 "Taintrux,", 0xae2bd0 "Taiobeiras,", 0x1a75dd0 "Taipa,", 0x1305010 "Taipalsaari,",
0x608c70 "Taipei,", 0x6bf280 "Taiping,", 0x1343970 "Taipu,", 0x16fcae0 "Tairan", 0x1b0c2d0 "Tairua,",
0x855230 "Taisen-ri,", 0x18d8cc0 "Taissy,", 0x758bc0 "Taitung", 0x132a140 "Taivalkoski,", 0x1a8f010 "Taivassalo,",
0x172d540 "Taiwala,", 0x608d50 "Taiwan", 0x7d6f40 "Taixing,", 0xd66da0 "Taiynsha,", 0x612a90 "Taiyuan,",
0x64aa70 "Taizhou,", 0x0 <repeats 988 times>}
```
* **發現 suggest 不但字串都相同，指向的位置也相同**；又參照 CPY 跟 REF 兩個 case，發現兩者差異只有再有沒有事先 alloc 一塊空間；還發現這句註解 `/* save pointer to 's' (allocated elsewhere) */`
* **代表另外給字串儲存空間應改可解決**
### 引入 Sbrk
* 打算用 sbrk 在 heap 給一塊空間再存入字串
```C=
else { /* save pointer to 's' (allocated elsewhere) */
void *ptr=sbrk(8); //alloc 8 bytes and store addr. in ptr
*(char*)(ptr+0)=**s; // assign pointer to string to the 8 bytes space
curr->eqkid = (tst_node *) (sbrk(0)-8);
return (void *) ptr;
}
```
>[color=red]**發現結果完全不對.......崩潰= =**
>決定換方法重來[name=bauuuu1021]
### 引入 memory pool
* 參考 [tina0405](https://hackmd.io/s/SkEFpwh2-) 同學的方法並改寫
* [Github](https://github.com/bauuuu1021/prefix-search/commit/49d31334b7795c8431fd4a891d5efa272f85ad82)
```C=
typedef struct MemoryPool {
char *current;
char *tail;
} pool;
pool *init (size_t size)
{
pool *p = (pool*)malloc(size * sizeof(pool));
p->current=(char*)p+0;
*(p->current)=0; //clean up
p->tail=(char*)p+(int)size;
return p;
}
char *memAlloc (pool *p, size_t size)
{
if ( p->tail-p->current < size )
return NULL;
char *temp = (char*)p->current;
p->current += size;
*(p->current)=0;
return temp;
}
```
* 原本在建置 tst 時就會 sigmentation fault ，以 gdb 逐行檢視發現是在 tst.c 的這行被擋下來
```C=227
if (strlen(*s) + 1 > STKMAX/2) /* limit length to 1/2 STKMAX */
return NULL; /* 128 char word length is plenty */
```
* 判斷是在傳到 tst_ins_del() 的字串 s 有問題，多方嘗試後，發現如果先把 pool->current 的值清除即解決
```C=10
*(p->current)=0; //clean up
```
>[color=red] 這樣並沒有解決問題，只是那一次的記憶體位置剛好可以運行而已，current 跟 tail 在 struct 中會有自己指向自己的問題，要是不將指向的記憶體位置更改的話你 memAlloc 時就可能會錯誤的把 pool 內部 current 的值改掉。
[name=BodomMoon]
>>[color=blue] 感謝指正，BodomMoon 同學共筆中有很詳盡的解說，請大家[參考](https://hackmd.io/s/r1tAcJWjz#) [name=bauuuu1021]
## 修改 Makefile
> 前面用的有點灰心QQ，先來嘗試其他要求 [name=bauuuu1021]
* 自動輸入命令
* 每個 fgets() 的最後一個參數改成 selectFP
* 如果執行檔後有輸入 `--bench <file.txt>` 就將 selectFP assign 為測試檔的檔案指標
* 否則 selectFP 設為 stdin 以手動輸入
* Makefile 新增 target，可透過 `$make bench` 將 "cities.txt" 中全部字串搜尋一次
```
bench: test\_ref.o test\_cpy.o benchmark.txt
$(info performance of test_ref)
./test_ref --bench benchmark.txt
$(info performance of test_cpy)
./test_cpy --bench benchmark.txt
```
:::info
不知道為甚麼會先 print 完兩個字串才開始執行@@
:::
## 效能分析
### 分析工具
* 因為需要針對某段程式碼進行效能分析， perf 好像不支援（有誤的話麻煩打臉！）因此找了一些工具：
* [papi](http://icl.cs.utk.edu/papi/)
* 需要另外安裝，而且試了一下我的環境好像不支援，放棄
* [rdtsc](https://stackoverflow.com/questions/13772567/get-cpu-cycle-count)
* [another reference](https://stackoverflow.com/questions/3830883/cpu-cycle-count-based-profiling-in-c-c-linux-x86-64)
* 寫了一個小程式測試與 perf 的差別，發現好像差蠻多的...，推斷是因為兩者包含的範圍不完全相同的關係
```
root@X555LB:/home/bauuuu1021# cat test.c
#include <stdio.h>
#include <inttypes.h>
uint64_t rdtsc(){
unsigned int lo,hi;
__asm__ __volatile__ ("rdtsc" : "=a" (lo), "=d" (hi));
return ((uint64_t)hi << 32) | lo;
}
int main (){
uint64_t s;
s=rdtsc();
printf("rdtsc result :");
printf("%" PRIu64 "\n",rdtsc()-s);
}
root@X555LB:/home/bauuuu1021# perf stat -e cycles ./test
rdtsc result : 192332
Performance counter stats for './test':
739,440 cycles
0.001069438 seconds time elapsed
```
:::warning
剛剛在 git commit 的時候因為檔案變很多（那時候QQ），還有一個叫 .vscode 的怪怪東西，想說就把他刪掉好了。結果不知道是下錯指令還是怎樣，整個專案全部88...心已死...大概兩天的心血全部不見= =
奉勸大家真的要
**寫到哪上傳到哪**
**寫到哪上傳到哪**
**寫到哪上傳到哪**
:::
* 提交 commit 時遇到以下問題，是因為沒有將以 FILE* 開的檔 fclose() 的關係，不只是要在程式的結尾加，還有中間要是有某些功能執行失敗及跳出程式也要加。
```
bauuuu1021@X555LB:~/prefix-search$ git commit
[test_cpy.c:74]: (error) Resource leak: outputCycle
[test_ref.c:72]: (error) Resource leak: outputCycle
Fail to pass static analysis.
```
### GNU Plot 製圖
* [教學共筆](https://hackmd.io/c/rJKbX1pFZ/https%3A%2F%2Fhackmd.io%2Fs%2FSkwp-alOg)
* [Github](https://github.com/bauuuu1021/prefix-search/commit/afa19c57a279d1ac1e8ec21f384a9586a47a7f74)
* 可透過 `$make plot` 製圖
* 以長條圖呈現建立 tst 的時間
* 以點狀分佈圖呈現 prefix-search 時所需 cycle 數發生機率
#### Memory pool
```
cpy mean 1339 sig 1222.847665
ref mean 1451 sig 1279.723762
```
* 和預先猜測的不太一樣，發現好像並沒有什麼明顯的差異
## 參考資料
* [動態 ternary tree](https://www.cs.usfca.edu/~galles/visualization/TST.html)
Sign in with Wallet
Connect another wallet