# 2016q3 Homework2 (phonebook-concurrent)
contributed by <`LanKuDot`>
## 閱讀筆記
### [The free lunch is over](http://www.gotw.ca/publications/concurrency-ddj.htm)
* Free (performance) lunch 指的是程式設計的效能可以透過 CPU 時脈的進步而得到改善。會說 over 是因為 CPU 的時脈無法得到更進一步的增加，由於耗電和散熱的問題，所以程式設計師必須要修改程式才能改善效能
* 文章中 `Figure 1`，可以看到 CPU 時脈並沒有隨著電晶體數量而增加，反而是趨緩了
* 以前 CPU 如何增進效能
* Clock speed
* Execution Optimization
* Pipelining、Branch prediction
* Out-of-order execution 還要注意不能讓原本程式崩潰 (read/write reorder)
* Cache：盡量減少存取 Main memory 的機會
* 現在 CPU 如何增進效能
* Hyperthreading：在 single CPU 上同時執行多個 thread，但是共用 ALU、FPU
* Multicore：多個 CPU
* 迷思：2 x 3GHz < 6GHz
* Cache
* 軟體開發革命 (Software development revolution) 是源自於存在一陣子的技術 (擁有成熟的銷售商和工具支援)，而非新技術一出現即發生。
#### Concurrency
* 兩個會使用 Concurrency 的理由：分離可獨立運作的工作；為了效能，像是使用多核新的 CPU
* 難點：並非所有的程式都合適平行化；程式要設計可以實行 Concurrency 是困難的
* 如果程式的相依性太高或是太常取用共同資源則會拖慢 Concurrency 的效率
* 作者提出 Concurrency 對我們的影響
1. 想要完全使用到 CPU 所有的資源
2. 程式越來越有機會造成 CPU-bound。雖然主要還是 IO-bound 等，但如果 CPU 時脈無法增加，而其他存取方式速度變快，最後會發生 CPU-bound
3. 效能優化將會越來越重要
4. 程式語言強迫必須好好處理 concurrency
### [Concurrency is not parallelism](https://blog.golang.org/concurrency-is-not-parallelism)
* **Concurrency** 是指程式架構，將程式拆開成多個可獨立運作的工作。eg：drivers，都可以獨立運作，但不需要平行化。
* 拆開多個的工作不一定要同時運行
* 多個工作在單核心 CPU 上運行
* **Parallelism** 是指程式執行，同時執行多個程式。Concurrency 可能會用到 parallelism，但不一定要用 parallelism 才能實現 concurrency。eg：Vector dot product
* 程式會同時執行 (例如：分支後，同時執行，再收集結果)
* 一個工作在多核心 CPU 上運行
### Concurrecncy 系列
* A **happends-before** B：在 B 開始執行之前，A 的執行效果必須可見。
* A is **Sequenced-Before** B：在**同一個 thread** 下，A 比 B 先求值。
* A is **synchronized-with** B：A 在這一個 thread 對記憶體的操作，在**另一個 thread** 的 B 必須可見。
* Sequential consistency：無論處理器實際怎麼執行，確保結果跟照程式順序執行一樣
* Read before Write：在新值寫入前讀取到舊值
* Write after Write：在正確值寫入後被舊值複寫 (有先後)
### Process && Thread && Coroutine
[[Source](http://learn-gevent-socketio.readthedocs.io/en/latest/general_concepts.html)]
* Process：一個完整的執行程式，擁有自己的 memory space、執行檔的鏡像、系統配給的存取資源的 descriptor 等
* Thread：輕量的 process，在 process 中被創造，**與同一個 process 中的其他 thread 共用 process 的資源**。
* Coroutine：合作函式 (Cooperative **functions**)。允許函式執行到一半離開 (`yield`)，去執行其他函式，再次呼叫這個函式時會從上次離開點開始執行。
#### [用 macro 實現 coroutine](http://blog.linux.org.tw/~jserv/archives/001848.html)
* 將 Jserv 老師給的用 macro 實現 coroutine 的程式只經過 Preprocessor 處理，會比較容易理解運作，以下程式碼是整理過後的
```c=
static int condition = 1;
static void user_thread_1()
{
static int __s = 0;
switch (__s) {
case 0:;
for (;;) {
printf("Run %s\n", __func__);
{ __s = 21;
usleep(THREAD_INTERVAL);
return;
case 21: ;
};
}
} __s = 0;;
}
static void user_thread_2()
{
static int __s = 0;
switch (__s) {
case 0:;
for (;;) {
if (condition) {
printf("Run %s - (1)\n" , __func__);
{ __s = 32;
usleep(THREAD_INTERVAL);
return;
case 32: ;
};
}
printf("Run %s - (2)\n", __func__);
condition = !condition;
{ __s = 36;
usleep(THREAD_INTERVAL);
return;
case 36: ;
};
}
} __s = 0;;
}
```
```
Output:
Run user_thread_1
Run user_thread_2 - (1)
Run user_thread_1
Run user_thread_2 - (2)
Run user_thread_1
Run user_thread_2 - (2)
Run user_thread_1
Run user_thread_2 - (1)
Run user_thread_1
Run user_thread_2 - (2)
Run user_thread_1
Run user_thread_2 - (2)
...
```
* 比較令我在意的是那個 case in for loop，所以我寫了小程式驗證
```c=
static void caseInForLoop()
{
static int __s = 0;
switch (__s) {
case 0:
for (;;) {
printf("Run to case 0.\n");
__s = 1;
return;
case 1:
printf("Run to case 1.\n");
}
}
}
int main(void)
{
caseInForLoop();
caseInForLoop();
return 0;
}
```
```
Output:
Run to case 0.
Run to case 1.
Run to case 0.
```
* ~~驚呆了~~，可以發現到 `caseInForLoop()` 只有呼叫兩次，但實際輸出卻有三次！
* 分析：
* 第一次執行沒有問題，一開始 `__s` 的值為 0，所以會印出 case 0 的訊息，然後值被改為 1，之後回傳。
* 然而第二次執行時，`__s` 值為 1，從輸出可以知道他跳到 case 1 開始執行，之後又回到迴圈頭重新執行，所以又會再輸出一次 case 0 的訊息
* 我現在才知道 switch-case 的 `case` 是類似 `goto`，以 `switch` statement 裡面的值決定要從 switch block 裡面的那一個點開始執行，而 `break` 是跟程式說執行到這裡就好了
* 回到 Jserv 老師的程式，`user_thread_1` 比較好理解，與測試程式一樣，只有第一次進入時 `__s` 值為 0，之後在無限迴圈中值都會保持在 21，從 `case 21` 開始執行，在無限迴圈中印完訊息後，delay、回傳。
* 至於 `user_thread_2`，
* 第一次進入時 `__s` 為 0，`condition` 為 1，所以會印出 `(1)`，`__s` 變為 32
* 再來從 `case 32` 開始，印出 `(2)`，`condition` 為 0，`__s` 變為 36
* 然後下次進來從 `case 36` 開始
* 這樣應該就會發現**每次再次呼叫函式時，都會從上次的離開點的下一行開始執行**，這正是 coroutine 中 `yield` 的功能。再檢視一次 `cr_yield` macro
```c
#define cr_yield \
{ __s = __LINE__; \ // 紀錄下一次進來的起始點
usleep(THREAD_INTERVAL); \
return; \ // 離開了
case __LINE__: ; \ // 再回來就從這裡開始
}
// 用 __LINE__ macro 作為 case 的好處在於一個函式中
// 可能會使用兩次以上的 yield，所以必須要區分不同 yield
// 的重新進入點，比起手動編碼，不如用行號來區分
```
### Switch-Case
* `switch` statement 會從輸入的變數值判斷要從 `switch` statment block 中的哪一個部分開始執行。而 `case` 就是一個標籤，告訴 `switch` statment 可以從哪裡開始，`break` 則是到哪裡結束。
* 注意 `case` 之間的 scope 除非特別指定 (用 `{}`)，否則是相通的。見下例：
```clike
switch (foo) {
case 1:
int z = 1;
printf("%d\n", z);
break;
case 2:
int z = 2;
printf("%d\n", z);
break;
}
```
* 因為 case 之間的 scope 是相通的，會發現在同一個 switch scope 下出現兩個 `z` 的宣告 (把 `case` 無視掉可以比較容易理解)，編譯就會出現錯誤訊息。
```clike
switch (foo) {
// case 1:
int z = 1;
printf("%d\n", z);
break;
// case 2:
int z = 2;
printf("%d\n", z);
break;
}
```
* 所以要避免這個情況的話，就要特別指定 `z` 的 scope，讓他只適用在一個 `case` statement 下：
```clike
switch (foo) {
case 1: {
int z = 1;
printf("%d\n", z);
break;
}
case 2: {
int z = 2;
printf("%d\n", z);
break;
}
}
```
* 或
```clike
switch (foo) {
case 1: {
int z = 1;
printf("%d\n", z);
}
break;
case 2: {
int z = 2;
printf("%d\n", z);
}
break;
}
```
### Refactoring
[[Source 1](http://teddy-chen-tw.blogspot.tw/2014/04/refactoring.html)] [[Source 2](http://www.ithome.com.tw/node/79813)]
* 「在不改變軟體的外在行為之下，**改善**既有軟體的內部設計」
* 對於既有的 context (codebase，原始碼)，找到需要重構的對象 form。form 中有東西因為無法平衡 force 而發出壞味道 (像 long method 就會受到 explanation、sharing、choosing 的 force)，讓整個 form 也有壞味道。
* Refactoring 可以調和不平衡的 force，讓 form 更合適這個 context (例如：提昇可讀性)，但不一定能完全消除壞味道。
* Refactoring 隨時在進行 (為了增加功能、除錯、程式碼審閱而觸發 refactoring)
### SuperMalloc
* 原本不同時候配置的記憶體會分散在記憶體的各處。SuperMalloc 針對每種不同的 object 大小給予一塊連續的記憶體，例如：bin 0 專屬於 8 bytes 的 objects，bin 1 專屬於 10 bytes 的 objects 以此類推。`size_2_bin` 負責運算要配置的物件需要從那一塊記憶體去配置。
# 作業
## 程式碼解析
### `file_align.c`
* 目的在於將檔案中每一行的字串長度貼到指定長度
* `stat`：display file or file system status
* 用 `$ man 2 stat` 可以看到其函式的用法
* `int stat(const char *pathname, struct stat *buf);`
* `struct stat`：是用來儲存檔案資訊的資料結構，包含檔案大小、類型、修改日期等資訊
* `strncpy`：複製 source 的前 n 個 byte 到 destination
* 如果 source 的程度小於 n 則會用 0 補滿
* 經過轉換之後的字串會是：`<originText>(會有newline)+<serial of \0>`
* 用 `size_t fwrite(const void *ptr, size_t size, size_t nmemb, FILE *stream);` 會取來自 `*ptr` 直接寫入 `size * nmemb` bytes 到檔案中，不會因為有 null character 而中斷寫入
* 所以用 vim 開啟 aligned 後的檔案會看到 `^@`，這是 null character
#### 程式問題
1. 第一步先改檔名XD，我覺得用 `text_align.c` 或 `line_align.c` 更能描述這個程式的功能
2. `wbuf` 是用 `malloc` 配置的，程式結束時沒有使用 `free`
3. 當讀入的字串長度"不等於"要 padding 到的長度，`rbuf` 的內容才會被複製到 `wbuf`，問題有二：
a. 當讀入字串長度等於 padding 的長度時 (`!= 0`不成立)，沒有任何東西被寫到 `wbuf`，會造成這筆資料遺失
b. 當字串資料過長時，會被截短。
* 我這邊選擇的修正是無論來源字串多長，就是會複製要 padding 的 bytes，但是對於過長的來源字串會輸出警告訊息給使用者
```c=
suffix = pad - strlen(rbuf);
// The length of the input text is longer than the length to padding to.
// Warn the user, and still write to the output file but with only
// first "PadToLen" bytes.
if (suffix ＜ 0)
printf("Warning:"
" The length of %s is longer than %d.\n", rbuf, pad);
strncpy(wbuf, rbuf, strlen(rbuf));
```
4. `file.c` 與 `file_align.c` 很相似，查看兩者用途發現 `file.c` 是模組化的版本
* 留下模組化的版本，建立 header file，讓主程式及測試程式都可以直接使用。模組化的好處是相容性高，而且只要維護一組程式碼就好
### `debug.h`
* 提供 macro `dprintf`，與 `printf` 的用法一樣，只是會在前面增加 `DEBUG:` 的字樣，透過定義 `DEBUG` macro 啟用。
* 與 c library 提供的 `dprintf` 功能不一樣，c library 的為將輸出寫入指定的 file descriptor
### `phonebook_opt.c`
* 第一眼看到函式跟變數名稱不知道用途((淚
* `append_a`：主要是用在傳遞給 thread 的訊息之資料結構，以下是修改過後的，更能辨別用途
```c
typedef struct _thread_argument {
char *data_begin;
char *data_end;
int threadID;
int numOfThread;
entry *lEentryPool_begin;
entry *lEntry_head;
entry *lEntry_tail;
} thread_arg;
```
* 其對應產生函式 `new_append_a()` 改為 `createThread_arg()`
* kl
### 主程式
1. 將檔案的內容映射到 memory 上，讓每個 thread 可以同時存取。
* `mmap`：將指定檔案的資料映射到 process 的 virtual memory space 上，可以防止 blocking I/O 的發生。
> 關於 `mmap` 詳細用法可以參考[林哲亘的共筆](https://hackmd.io/s/rJPYFYRa)
>
* 根據 manual，有提供 `munmap` system call 來刪除配給的區塊，不過在程式結束時，這個區塊會自動被 delete 掉。關閉對應的 file descriptor 不會刪除配給的記憶體
2. 一次建立足夠的空 entry 給所有 thread 使用，避免因為 `malloc` system call 所造成的 waiting。
3. `pthread_setconcurrency`：Setting the concurrency level allows the application to give the system a hint as to the number of kernel-scheduling entities that should be provided for efficient execution of the application，還不太懂用途
4. 準備每個 thread 所需要的資訊，例如：讀取資料區間的開頭與結尾、寫入資料區間的開頭與結尾等
5. 創造 thread，開始讓各自的 thread 工作
6. 等待所有 thread 完成之後將每一段 thread 所屬的 entry list 組合起來
#### 程式問題
* 開啟 aligned 之後的檔案但是沒有關閉，透過 `open` 開啟檔案會配置資源給對應的 file descriptor，要用 `close` 來釋放資源
* 搭配 `valgrind` 檢查有無 memory leak 的問題。可以發現 malloc 28次，卻只有 13 次 free
```
==4768== HEAP SUMMARY:
==4768== in use at exit: 2,199 bytes in 15 blocks
==4768== total heap usage: 28 allocs, 13 frees, 8,410,205 bytes allocated
==4768==
==4768== LEAK SUMMARY:
==4768== definitely lost: 585 bytes in 11 blocks
==4768== indirectly lost: 0 bytes in 0 blocks
==4768== possibly lost: 0 bytes in 0 blocks
==4768== still reachable: 1,614 bytes in 4 blocks
==4768== suppressed: 0 bytes in 0 blocks
==4768== Rerun with --leak-check=full to see details of leaked memory
```
* 處理 memory leak
* 既然 `THREAD_NUM` 是在 compilation 時期指定，則隨 `THREAD_NUM` 變動的 array 長度可以不用使用 `malloc`
* `thread_args` 的元素也是透過 `malloc` 取得，要 free 掉
* 在 `findName()` 中會給找到的 entry 的 `lastname` 和 `detail` 配給記憶體，但是沒有處理已經被搜尋過的 entry 不需要再配置記憶體的情況，像在主程式中搜尋 `zyxel` 就有三次，造成前兩次配置的記憶體遺失。
* 解決方案：在 `mmap` 多加一個 `PROT_WRITE` 的 flag，直接在映射的記憶體上處理 `\n`，而不配置記憶體給他。另外在 `append` 中取用一個新的 entry 時也會同時初始化 `dtl` 為 `NULL`，讓 `findName()` 判斷要不要配置新記憶體給他。另一個好處是在釋放 entry 的記憶體時不需要檢查 `dtl` 是否為 `NULL`，根據 [manual](http://man7.org/linux/man-pages/man3/malloc.3.html) 如果 `free()` 收到 `NULL` 並不會做任何事情。
> 不過我在修改這裡時發生神奇的事情，原先我只加 `PROT_WRITE`，會在第一個 assertion (問你有沒有實做 findName 那個) 失敗。將 `MAP_SHARE` 改成 `MAP_PRIVATE` 才正常運作。是因為沒有 sync? (同一個程序去修改需要 sync 嗎？)
>
* 但還是有 memory leak，所以我透過 `valgrind --tool=memcheck --leak-check=yes <executable>` 可以更詳細知道哪裡有配置記憶體但沒有 free 的程式碼，還包含 call stack。一個是 `pHead` 在 main 中被移動到下一個，造成原版的頭遺失。另一個是在 `findName()` 中配置的 detail 記憶體沒有被一併 free 掉。
```
==6392== 24 bytes in 1 blocks are definitely lost in loss record 1 of 7
==6392== at 0x4C2BBA0: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==6392== by 0x400F79: main (main.c:61)
==6392==
==6392== 107 bytes in 1 blocks are definitely lost in loss record 4 of 7
==6392== at 0x4C2BBA0: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==6392== by 0x401535: findName (phonebook_opt.c:18)
==6392== by 0x4012A6: main (main.c:148)
```
* 修正完還是有 5 個 block lost 掉，但是不知道在哪裡
>> 這時候就要出動 [LeakSanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizerLeakSanitizer)，可一併對照 Mozilla Taiwan 的網誌: [Address-Sanitizer(ASAN): 一個 C/C++ 記憶體偵錯的工具](http://tech.mozilla.com.tw/posts/4282) [name=jserv]
>> 我使用 ASAN 去偵測，但是程式很安靜的結束了，不過我檢查 valgrind 的報表，他標示 5 個 block 是 still reachable，然後查 [StackOverflow](http://stackoverflow.com/questions/3840582/still-reachable-leak-detected-by-valgrind)，提到可以不必擔心這一區塊的 memory，整理到下面。[name=LanKuDot]
* 另外這次的 refactoring 中，主程式花最多時間修改。我感受到為了讓優化過的版本可以運作，所以在 code 中這邊貼一塊，那邊補一塊 (原始版到處都是 `#ifndef, #else, #endif`)。就好像是要重新粉刷牆面的某一些地方，沒有照著原本牆面的粉刷方向去刷，整面牆就會有各種方向的刷痕。
* 整理過後讓 free processing、build entry、release the memory 這三個部份都只有一組 `OPT` 的 condition macro，增加可讀性。
### [ASAN(Addres-Sanitizer)](http://tech.mozilla.com.tw/posts/4282)
* 偵測 Memory corruption，LLVM 3.1 及 GCC 4.8 後內建 ASAN
* 可以偵測下列問題
* Use after free (Dangling pointer dereference)
* Heap buffer overflow
* Stack buffer overflow
* Global buffer overflow
* Use after return
* 編譯時加入 `-fsanitize=address`，編譯器會插入除錯程式碼，再加上 `-fno-omit-frame-pointer` 可以讓錯誤訊息回報正確的 call stack
* ASAN 是以 **continue-after-error** mode 執行，所以就算遇到第一個錯誤，程式還是可以繼續執行
* 示範一個 use after free 的程式
```c
#include <stdlib.h>
int main(void)
{
char *x = (char *)malloc(10 * sizeof(char));
free(x);
return x[5]; // Use after free
}
Compile: gcc -fsanitize=address -fno-omit-frame-pointer useAfterFree.c
```
```
Execution: ./a.out
=================================================================
==4547==ERROR: AddressSanitizer: heap-use-after-free on address 0x60200000eff5 at pc 0x4007f4 bp 0x7ffca341e6a0 sp 0x7ffca341e690
READ of size 1 at 0x60200000eff5 thread T0
#0 0x4007f3 in main
#1 0x7f4484687a3f in __libc_start_main
#2 0x4006c8 in _start
```
### 關於 Valgrind 回報的 still reachable
根據[這篇](http://stackoverflow.com/questions/3840582/still-reachable-leak-detected-by-valgrind)回答：memory leak 有兩種定義
* 配置的記憶體在程式結束後**沒有**被 free
* 配置的記憶體**無法**被 free，因為沒有有效指標指向他
只有第二種才是真正的 memory leak。然而如果 `valgrind` 回報的區塊是分類在 still reachable 的話 (由於 program 尚在追蹤指向這些區塊的指標)，代表這些區塊雖然還沒被 free，但是之後還是可以被系統取回。所以不必擔心被分類在 still reachable 的區塊
```
==4443== HEAP SUMMARY:
==4443== in use at exit: 7,780 bytes in 5 blocks
==4443== total heap usage: 20 allocs, 15 frees, 8,409,647 bytes allocated
==4443==
==4443== LEAK SUMMARY:
==4443== definitely lost: 0 bytes in 0 blocks
==4443== indirectly lost: 0 bytes in 0 blocks
==4443== possibly lost: 0 bytes in 0 blocks
==4443== still reachable: 7,780 bytes in 5 blocks
==4443== suppressed: 0 bytes in 0 blocks
```
### 進一步優化 append()
原本的版本中 `append()` 還有兩個地方可以改進：
1. C 中 memory 是以 row-major 的方式儲存，但原本程式碼取址的方式 (包含 `data` 跟 `entry`) 卻以 column-major 去存取。這樣會造成大量 cache-miss 和 cache-reference。
* Thread 0: 0, 3, 6, 9, ...
Thread 1: 1, 4, 7, 10, ...
Thread 2: 2, 5, 8, 11, ...
2. 原版程式中的 local linked list 第一個是空資料，而且在連接的時候，會拋棄第一個 entry。所以如果配給剛好數量的 entry，然後都從第二個 entry 開始填資料，一定會有一筆資料沒有地方填。
所以我做了以下修正：
1. 每個 thread 取得的 entry 跟 data 會是連續的，以 row-major 的方式取址
* Thread 0: 0, 1, 2, 3, ...
Thread 1: 10, 11, 12, 13, ...
Thread 2: 20, 21, 22, 23, ...
* 要注意每個 thread 的範圍：我讓每個 thread 分到 `num_of_data / THREAD_NUM + 1` 的資料去處理，+1 是為了避免餘數集中在最後一個 thread。最後一個 thread 的資料結尾則直接指定 `data_pool` 的結尾。
>> 想問這邊 ```num_of_data / THREAD_NUM + 1``` 如果無法整除的話該如何處理？？
>> 我嘗試過這樣做，但是如果在 words.txt 裡新增一筆資料後會有問題...
[name=littlewhiteYA]
2. 處理第二個問題，必須要先讓第一個 entry 填入資料，才能進入迴圈從第二個 entry 開始處理 (因為第一個 entry 沒有前面可以 append)，也能避免少掉幾個資料的問題。
#### Cache 分析及執行時間
改變取址的方式得到了大量的改進，~~起飛拉~~
* 改進前：
* append time：0.019036 sec
```
Performance counter stats for './phonebook_opt':
254,263 cache-misses # 6.179 % of all cache refs [76.70%]
4,115,040 cache-references [49.89%]
251,354,400 instructions # 1.12 insns per cycle [76.12%]
224,681,630 cycles [74.70%]
```
* 改進後：得到近一倍的改善
* append time：0.009584 sec (49.6% improved)
* cache misses 62.9% improved
* cache references 41.7% improved
```
Performance counter stats for './phonebook_opt':
94,171 cache-misses # 3.922 % of all cache refs [78.01%]
2,400,810 cache-references [45.85%]
264,389,689 instructions # 1.41 insns per cycle [76.93%]
187,534,122 cycles [78.00%]
```
## 效能分析
[append() time], [findname() time] in seconds
* Baseline：0.145418, 0.022165
* Optimized_Origin：0.022656, 0.012122
* Handle memory leak：0.019036, 0.011447
* Use row-major `append()`：0.009584(!!!) 0.010219
Sign in with Wallet
Connect another wallet