2018q1 Homework1 (phonebook)

contributed by<nashi5566>
希望自己承擔的起 5566 這個數字

Reviewed by ryanpatiency

• Duplicate git commit message "Create new Structure"
• The current commit is about hash function, you should push your implementation of rb tree and other feature to github

Reviewed by e94046165

• 實作 hash search 中，提到 hash_table_size 如果是質數的話，可能會有較佳的效能。建議可以實際測試看看，比較不同 table_size 大小、質數/非質數的效能差異。
• 承上點，預先設定的搜尋目標 "zyxels" 在字典檔的最後。以搜尋這筆資料比較 findName 的 performance 可能有失公平，在比較不同 hash_table_size 時也會造成影響，建議可以試試別的搜尋目標。

系統環境

中英文字間記得空白
課程助教

謝謝助教！因為之前有些編輯是用手機打的沒有注意到，我之後會注意
林靜儀

因為我的電腦很早之前環境就是 Linux，這次就不再從頭灌作業系統

請升級到 Ubuntu 17.04 或者更新的版本，我們需要新的工具

jserv

• Linux Mint
  
• gcc 5.4.0
  

$ cat /proc/cpuinfo

processor	: 0
vendor_id	: GenuineIntel
cpu family	: 6
model		: 69
model name	: Intel(R) Core(TM) i5-4210U CPU @ 1.70GHz
stepping	: 1
microcode	: 0x17
cpu MHz		: 1699.968
cache size	: 3072 KB
physical id	: 0
siblings	: 4
core id		: 0
cpu cores	: 2
apicid		: 0
initial apicid	: 
fpu		: yes
fpu_exception	: yes
cpuid level	: 13
wp		: yes
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 arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf eagerfpu pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm epb tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt dtherm ida arat pln pts
bugs		:
bogomips	: 4800.25
clflush size	: 64
cache_alignment	: 64
address sizes	: 39 bits physical, 48 bits virtual
power management:

processor	: 1
vendor_id	: GenuineIntel
cpu family	: 6
model		: 69
model name	: Intel(R) Core(TM) i5-4210U CPU @ 1.70GHz
stepping	: 1
microcode	: 0x17
cpu MHz		: 1784.531
cache size	: 3072 KB
physical id	: 0
siblings	: 4
core id		: 0
cpu cores	: 2
apicid		: 1
initial apicid	: 1
fpu		: yes
fpu_exception	: yes
cpuid level	: 13
wp		: yes
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 arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf eagerfpu pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm epb tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt dtherm ida arat pln pts
bugs		:
bogomips	: 4800.25
clflush size	: 64
cache_alignment	: 64
address sizes	: 39 bits physical, 48 bits virtual
power management:

processor	: 2
vendor_id	: GenuineIntel
cpu family	: 6
model		: 69
model name	: Intel(R) Core(TM) i5-4210U CPU @ 1.70GHz
stepping	: 1
microcode	: 0x17
cpu MHz		: 1698.750
cache size	: 3072 KB
physical id	: 0
siblings	: 4
core id		: 1
cpu cores	: 2
apicid		: 2
initial apicid	: 2
fpu		: yes
fpu_exception	: yes
cpuid level	: 13
wp		: yes
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 arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf eagerfpu pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm epb tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt dtherm ida arat pln pts
bugs		:
bogomips	: 4800.25
clflush size	: 64
cache_alignment	: 64
address sizes	: 39 bits physical, 48 bits virtual
power management:

processor	: 3
vendor_id	: GenuineIntel
cpu family	: 6
model		: 69
model name	: Intel(R) Core(TM) i5-4210U CPU @ 1.70GHz
stepping	: 1
microcode	: 0x17
cpu MHz		: 1701.000
cache size	: 3072 KB
physical id	: 0
siblings	: 4
core id		: 1
cpu cores	: 2
apicid		: 3
initial apicid	: 3
fpu		: yes
fpu_exception	: yes
cpuid level	: 13
wp		: yes
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 arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf eagerfpu pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm epb tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt dtherm ida arat pln pts
bugs		:
bogomips	: 4800.25
clflush size	: 64
cache_alignment	: 64
address sizes	: 39 bits physical, 48 bits virtual
power management:

系統環境與安裝 20180301

• 現在才發現原來我目前的環境還不夠新，只不過因為我電腦作業系統只有Linux，那我就從做開機碟開始描述。

• 其實在使用Linux Mint之前，我曾經使用過 Ubuntu 的其中一個分支 Kubuntu ，版本就是17.04。但是那個版本極度不穩定，我時常剛灌好三天後 GRUB 就會抓不到 Kernel ，被強迫學習了一些 GRUB 指令還看了Linux的 watchdog.c source code ，但還是救不回來，真的是很棒。雖然有句話說 「珍惜生命，遠離 KDE」 但我想這問題應該不是全出在 KDE 身上吧，只希望這次 17.10 不會暴走。

請搭配以下的歌服用：

1. 製作開機碟

• # df -Th 找到我們要作為開機碟使用的 USB 在哪裡

  • df 這個指令能夠列出檔案系統整體磁碟的使用量和狀況
  • 後面參數 T 代表「列出該分區的 file system 名稱」，h 代表以比較簡單閱讀的格式顯示，例如容量使用 Gbytes 為單位
    

• 找到 USB 的 mount point 之後做 umount $ umount /media/nashi/USB \隨身

• # mkfs.vfat /dev/sdc 格式化該 USB 成 VFAT

• 接著就是可怕的(?) dd 了 ，找到剛剛下載好的 ubuntu 映像檔路徑下
  # dd if=/home/nashi/下載/ubuntu-17.10.1-desktop-amd64.iso of=/dev/sdc

• 這個過程會花一點時間，我們就戒慎恐懼地(?)等待
  

2. 再來就是設定BIOS開機順序、灌上去之類的步驟，細節不詳述

• 只不過這裡有點尷尬的是，我之前 BIOS 不小心被鎖住了，雖然試著拯救過很多次但還是進不去，只不過我也不想花 1000 多塊，所以…這裡有個網站推荐給也被鎖住的大家(?)，只不過只適用於筆電

  BIOS Password Recovery for Laptops
  

• 這個 exploitation 是源自於 BIOS Password Backdoor in laptop[1]，會在後文詳述。

• 三次輸入錯誤之後會得到一組 checksum ，拿到這組 checksum 之後輸入到這個網站經由 hash 得到 master password (Hash 的方式應廠商而異)

  • 其實不該用 hash 這個動詞，只是因為也有人稱這段 checksum 為 hash 故借用這個動詞，但在密碼學中 hash 是不可逆的，用來檢查資料的完整性。

原理：

Reference 01

3. 額外問題

• 成功用開機碟畫面開啟安裝畫面時出現了錯誤訊息

[Firmware Bug]:TSC_DEADLINE disabled due to Errata; please update mircocode to version 0x20(or later)

• 似乎是最今 Intel 有新的 patch 我沒有更新所以不讓我安裝17.10
• 所以先下指令$ sudo apt-get update intel-microcode iucode-tool 結果如下圖，但還是 2017 年的，我現在缺的應該是 2018 年一月份的 patch
  

懷疑是不是因為在 16.04 的環境所以不能安裝 2018 的 patch?
先嘗試看看在17.10的試用版中更新看看再 reboot
林靜儀

看來不是這個問題，他連試用版都不讓我用。
這就代表我得更新 BIOS 了…
林靜儀

• ㄜ，Acer 官網這台型號的電腦 BIOS 是2016年的。看來…？

系統環境與安裝 20180302

• 一直找不到問題所以就去看 Ubuntu 的 release note 看這次更新到底更新了什麼和目前有哪些 issue ，便發現這次更新似乎跟 Acer 和 Lenovo 部分型號的 BIOS 不相容，這個 bug 修好之前安裝 ubuntu 的任何分支就是無解了，之後會試著裝 Fedora 看看

另一個思路是，如果你先在舊版的 Ubuntu Linux 執行 Docker，就能透過 docker 安裝新版的 Ubuntu Linux 系統，比方說: teresaejunior

jserv

之前都忘了有 docker 可以用，之後我會試試看！ 謝謝老師
林靜儀

系統安裝 20180303 - 使用 docker

• 依照老師的建議這次用 docker 來裝新的 Ubuntu
• 之前沒有考慮到用 docker 是因為怕會像 VM 一樣對硬體有做一層抽象而會有讀不到 PMU 的疑慮，但後來回想了一下 container 的架構之後發現應該沒這個問題，因為他是直接用 host kernel ，安裝過程步驟之後會補充關於 docker 的資料

1. 首先先裝 docker $ sudo apt-get install docker.io
2. 裝好之後，先切換到 root 會比較方便 (docker 的指令只能用 root 的身份運作)
3. 搜尋老師前文提供的發佈者的 image 有哪些 # docker search teresaejunior

• 可以看到有這些 image 可以用

4. 再來下 # docker pull teresaejunior/ubuntu:17:10 ，冒號後面指的是你想下載的版本號碼，這裡就裝 17.10，記得都是冒號，或者使用 :latest 這個 tag (我一開始打錯了但其實應該還好)

5. 裝好之後可以用 # docker images 看到你目前電腦上已經有哪些 image
6. 之後只要再下 # docker run -i -t teresaejunior/ubuntu 就可以進入 container 進行作業了 ~

太好了，之後你可以幫忙整理 Docker 教材，這樣我們課程可透過 Docker 提供預先設定好的開發環境。

jserv

• docker 指令我是參照之前參加 UCCU Hacker 的 Honeypot 工作坊的上課資源，講者是許清雄先生

# 發現很神奇的錯誤！！

• docker 居然不能做 $ sudo sh -c " echo 0 > /proc/sys/kernel/kptr_restrict"

sh: 1: cannot create /proc/sys/kernel/perf_event_paranoid: Read-only file system

• 目前正在想辦法解決，總之先把目前的狀態 commit 避免 container 的內容遺失
• 然後這是我的 docker hub，用法和 github 很像但比 github 簡單
• 在你的 container 關掉之前，另外開一個 terminal，還有去 docker hub 辦一個帳號並新增一個目錄

# docker commit -m="commit message" -a="author name" <container ID> <image name>

• 然後下以下的指令，輸入帳號密碼登入

# docker login

• 接著用 tag 將這個 image 標記給要 push 的目錄，以我為例：(前面是要 push 的目錄名字，後面是在本地電腦 container 的名字)

# docker tag nashi5566/ubuntu_17 nashi/ubuntu

藉由這個步驟就可以在 # docker images 看到這兩個名稱都會指向同一個 container

• 接著 # docker push nashi5566/ubuntu_17 就會推到自己的 docker hub 上了，之後如果需要使用這個環境的 images 就用 pull 下載下來

覺得自己程式的進度落後，大部份的時間都花在架環境上，所以之後我會先寫程式，之後再用 docker 環境 clone 下來運行。
林靜儀

只不過好好奇一個 container 的 image 是怎麼做出來的，如果我心有餘力的話想要自己搞一個適合這個作業用的 image ，只不過也是要等我程式有寫好才行 QQ
林靜儀

結果後來發現我一直忘記把指令打成：
# sudo echo 0 | sudo tee /proc/sys/kernel/kptr_restrict
這樣權限就設定OK了！
更新過的 docker 也 push 上去了，歡迎想用的人 pull 下來玩
只不過 perf 還是有點問題，會被 permission denied ，目前正在研究下方新增的 Slide

# 可怕的小實驗

• 我在想說如果我自己手動更新 kernel 不知道會怎樣，然後就安裝了 Linux 4.15 的 kernel

• 結果因為我沒有移除舊的，導致電腦裡有兩個 kernel 並存，重新開機之後就炸了
  

  
  • 我的電腦啊啊啊啊啊

• 一開始沒發現是這個問題，然後我就想到用 Windows 開機碟進去洗掉全部，再用 Linux 開機碟洗掉變成 Linux (?)

• 結果居然系統會無視開機裝置優先順序，一直要我選開機選單的選項

• 直到進入開機選單的進階選項發現可以進入兩個不同的 kernel ，因為 4.15 好像果然真的不能用，所以進去舊的 4.4 之後就回到原來的 (?) 世界了

• 雖然應該是因為我對作業系統的了解還是很淺，但居然會無視 BIOS 內設定的內容，不是優先用 USB HDD 開機，而是用 HDD 的內容開機，難道 OS 不是聽韌體的嗎？？頓時間黑人問號了起來

是說我的共筆大部份都在講架環境的事，我都差點以為我的作業是寫架環境工具書了…

新研究

• 看到 2017 年的 dockerCON 有一個議程在討論 docker 的效能分析方法，目前正緩慢閱讀研究中

SlideShare

# 解決 permission denied 的方法

• 後來查了很多 docker 的指令後發現在 run 的指令下另有一種模式 --privilege ，只有在這個模式下才能夠讓 docker 取得真正的 root 權限
• 這是因為 docker 其實本身也是一個在 user mode 運行的 process ，只是在 docker 運行的環境下看到的 PID = 1 ，但其實他在原來的 host OS 下與其他 process 無異，同時也算是 docker 設計下一種保護措施

Linux namespaces

• 只要指令下 # sudo docker run -it --privileged <image name> 之後， perf 就能正常使用了

---

TODO List

• 影片中的要求：
  • Perf:
    • Perf top
    • Perf state
  • Out-of-order execution
  • Make file
  • dual issue
  • clock_gettime
  • gnuplot
  • tracepoint
• 目標：
  • 實作phonebook_opt.h
  • 比較find()、append()的run time 和 cache miss狀況
  • challenge: fuzzy search

---

Out-of-order execution

• 複習一下白算盤第四章的內容，並搭配同作者的 Computer Architecture 看一些實際案例
• 搭配 CMU 的影片參考

I. 原理

II. Tomasulo’s Algorithm

III. OoO 在現實生活中的具體例子

---

方向和猜測

1. 先試著更改資料的儲存方式

   • 改成Binary Searching Tree
   • 使用Hash Table
   • 減少 entry size →在影片中提到的

2. 繼續壓低 entry size 使其小於 32 bytes

與其標注 20180301 這樣的日期，不如建立對應的 git branch，並且在共筆標註 branch, tag, 或者 git commit，這樣日後追蹤會更便利且精確。

jserv

好的，我之後會注意
nashi5566

---

整理 Dataset

• 我一開始以為資料只有 word.txt ，想說要自己上網爬資料來用，結果發現其實作業的檔案裡面有，所以之後應該會用裡面的 all-name.txt 來試試看 fuzzy search。
• 但是這裡還是整理一些指令給大家，如果需要自己製作字典檔的話：

$ curl http://deron.meranda.us/data/census-derived-all-first.txt | awk '{print $1}' > name.txt

• 這裡 curl 是將後方網址 GET request 得到的 body 下載下來，而後方 awk '{print $1}' 指令則是印出該 txt 檔中第 1 行的內容，後方加上 > 和要輸出檔名就能得到一個 name.txt
• 然後這個網站只包含 US 常見男女姓名，資料量比較少一點
• 基本上網路上找到的 name list 都是照常見程度排序的 (所以通常前面都是 j 開頭的) ，如果要排序的話就 $ sort -d name.txt

---

實驗結果

I. 先從減少 size of entry 著手 link

1. 一開始先跑跑看 phonebook_orign 的狀況

• 首先清空 cache $ sudo echo 1 > /proc/sys/vm/drop_caches

• 再來在~/phonebook/ 底下 make cache-test：

size of entry : 136 bytes
execution time of append() : 0.048616 sec
execution time of findName() : 0.005629 sec

    Performance counter stats for './phonebook_orig' (100 runs):

        1,000,856      cache-misses              #   89.422 % of all cache refs         ( +-  0.39% )
        1,119,254      cache-references                                                                        ( +-  0.19% )
        260,653,083      instructions              #    1.47  insns per cycle                     ( +-  0.02% )
        177,184,802      cycles                                                                                              ( +-  0.23% )

    0.068426836 seconds time elapsed                                                                   ( +-  0.42% )
 

• 可以看到 cache miss 高達 89.422%

2. 減少 size of entry：

• 做以下的更動，之後 phonebook_opt 以使用後者的 entry 為主

typedef struct __PHONE_BOOK_ENTRY_OLD {
    char lastName[MAX_LAST_NAME_SIZE];
    char firstName[16];
    char email[16];
    char phone[10];
    char cell[10];
    char addr1[16];
    char addr2[16];
    char city[16];
    char state[2];
    char zip[5];
    struct __PHONE_BOOK_ENTRY *pNext;
} entry_old;

typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    entry_old *old;
    struct __PHONE_BOOK_ENTRY *pNext;
} entry;

• phonebook_opt.c 中的 implementation 先暫時和 phonebook_orign.c 一樣不作更動
• 之後再做一次 $ make cache-test ，可以看到結果如下：

size of entry : 32 bytes
execution time of append() : 0.038097 sec
execution time of findName() : 0.002305 sec

															 Performance counter stats for './phonebook_opt' (100 runs):

																            127,416      cache-misses              #   32.105 % of all cache refs      ( +-  0.64% )
	           396,874      cache-references                                              ( +-  0.82% )
	       243,908,527      instructions              #    1.93  insns per cycle          ( +-  0.02% )
	       126,182,514      cycles                                                        ( +-  0.43% )

	       0.048843834 seconds time elapsed                                          ( +-  0.53% )

• size of entry 從原先 136 bytes 降到 32 bytes ，cache miss 也降到 32.105%

3. 兩者的結果做 plot：

• $ make plot
  

  

• 可以看到不管是 append() 還是 findName() 時間都有所縮減

4. 結論：

• 原先的 entry 資料量較大，對 cache 帶來相當的 overhead ，但是其實大部份在 cache 中會被 reference 到的資料卻很少(因為只有用 lastName )
• 之後會嘗試是否能將 entry 壓得更小，且驗證是否能對效能提升

II. 加入 hash function

1. 使用 djb2 hash function link

• djb2 hash function

int hash(char lastName[])
{
    unsigned long hash = 5381;

    while(*lastName) {
        hash = ((hash << 5) + hash) + (*lastName++); /*hash*33 + (*lastname++)*/
    }

    return hash%HASH_TABLE_SIZE;
    /*HASH_TABLE_SIZE 1024*/
}

• 一開始發生了很蠢的事，寫上來給大家笑一笑，我忘了 malloc 空間給 hash table 結果就噴了一堆越權存取哈哈哈哈

• 這次使用 hash function ，可以看到 findName() 時間下降很多，但是因為 gnuplot 設定的精度太小，只能看到 0 ，之後會參照 bauuuu1021 同學的方式調整精度
  
  

size of entry : 32 bytes
execution time of append() : 0.045169 sec
execution time of findName() : 0.000000 sec

 Performance counter stats for './phonebook_opt' (100 runs):

            80,706      cache-misses              #   47.345 % of all cache refs      ( +-  0.79% )
           170,462      cache-references                                              ( +-  1.95% )
       241,088,895      instructions              #    1.92  insns per cycle          ( +-  0.02% )
       125,277,516      cycles                                                        ( +-  0.35% )

       0.048735985 seconds time elapsed                                          ( +-  0.46% )

• 但是 append() 的時間卻比原來高一點，是因為原來資料的存放方式是 linked list ，而加入 hash function 之後會先計算 hash 值，放入 table 之後有 collision 再 chaining
• 而 cache misses rate 比只有減少 entry size 的結果高出約 20% ，原因是原先資料是 linked list ，存放的順序是 sequential ，對於 prediction 來說比較容易預測正確，但是 hash function 則是將資料打散，因此比較容易發生 cache miss。

2. 使用其他的數值作為 hash table size (使用質數)

參考 good hash table primes

a. HASH_TABLE_SIZE 1543

---

III. 資料儲存方式改成 Binary Searching Tree

• BST 如果沒有 balanced 就會退化成 linked list，因此這裡會使用 AVL Tree 和 Red-Black Tree 來達到 O(logn)

• 只不過之前有聽過都市傳說 (?) 提到 RB Tree 比 AVL Tree 更有效率，一直不知道為什麼，可以藉由這次的實作來驗證看看讓這句話有科學依據點，之後也會查相關的原理差別

• Rotation 在任何 BST 結構中都是一樣的，差別只有在於調整與否的條件，因此這裡參考了這個網站的內容

• Left Rotation

entry *leftRotate(entry *pHead, entry *a)
{
	if (a->pRight != nil){
		entry *b = a->pRight;
		if (b->pLeft != nil) {
			b->pLeft->pParent = a;
		}
		b->pParent = a->pParent;

		if (a->pParent != nil) {
			if (a->pParent->pLeft == a) { /* a is left node*/
				a->pParent->pLeft = b;
			}
			else {
                a->pParent->pRight = b;
			}	
		}
		
		b->pLeft = a;

		if (a->pParent == nil) { /* a is root*/
			a->pParent = b;
			return b;
		}
		else {
			a->pParent = b;
		}

		return pHead;

}

1. 使用 AVL Tree

2. 使用 RB Tree

• 如何調整 RB Tree 的顏色我參考了以下的影片：
  
  
  

---

參考資料

系統安裝

1. Linux 下製作 USB 開機碟
2. BIOS Password Recovery for Laptops
   
3. Ubuntu 17.10 release note

Out-of-order Execution

1. Out-of-order Execution
2. Lecture 14 - Out-of-Order Execution - Carnegie Mellon - Computer Architecture 2013
3. An Efficient Algorithm for Exploiting Multiple Arithmetic Units

hash function

1. hash function

Balanced BST

1. Red Black Tree
2. 演算法筆記 Order

RB Tree 和 AVL Tree 之間效能比較的傳言是引自演算法筆記作者的發言
林靜儀