<style>
h2.part{color:#000000;}
h3.part{color:#D92424;}
h4.part{color:#005BB0;}
h5.part{color:#FD6F0A;}
h6.part{color:#4400B0;}
</style>
# 2017q1 Homework4的觀念 (phonebook-concurrent)
## 開發環境
```shell
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
型號： 42
Model name: Intel(R) Core(TM) i5-2410M CPU @ 2.30GHz
製程： 7
CPU MHz： 799.890
CPU max MHz: 2900.0000
CPU min MHz: 800.0000
BogoMIPS: 4589.59
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 3072K
NUMA node0 CPU(s): 0-3
```
## [Toward Concurrency](https://hackmd.io/s/Skh_AaVix)
* concurrency(並行) 把可以拆開的部份拆開，不一定要同時執行
* parallelism(平行) 把程式拆開"一起執行"，最後在一起相加
multithread環境下，程式會出問題，往往在於執行順序的不確定性。
* Concurrency
* Sequenced-before
* 一種對同一個 thread 下，求值順序關係的描述
* Happens-Before
* 前一個操作的效果在後一個操作執行之前必須要可見
* Synchoronizes-with
* 跨 thread 版本的 happens-before
* Sequential Consistency
1. 對於每個獨立的處理單元，執行時都維持程式的順序 (Program Order)
2. 整個程式以某種順序在所有處理器上執行
## 開發紀錄
首先是最原始的效能
先研究一下 opt 的版本，一開始看到有的是 `ifndef OPT` 有的是 `if defined(OPT)` 蠻不習慣的，有時間把它改好看一點。
還沒使用過 pthread 要先讀個 code
> 有個疑惑，不知道為什麼`pthread_setconcurrency(THREAD_NUM + 1);`要+1
看完沒什麼好改善的主意，只好來選讀的前一屆的共筆，這邊我想到我在 Homework1 就有觀察過 memory leak 了
## memory leak
先使用以前用過的 `valgrind` 來觀察一下，能看到有 4 個尚未被 free，opt 版本裡面跟 4 有關的應該就是 pthread_num ，我大概是各個 thread 裡面有東西忘記 free
```
$ valgrind --leak-check=full ./phonebook_opt
==10606== HEAP SUMMARY:
==10606== in use at exit: 1,614 bytes in 4 blocks
==10606== total heap usage: 24 allocs, 20 frees, 8,421,863 bytes allocated
==10606==
==10606== LEAK SUMMARY:
==10606== definitely lost: 0 bytes in 0 blocks
==10606== indirectly lost: 0 bytes in 0 blocks
==10606== possibly lost: 0 bytes in 0 blocks
==10606== still reachable: 1,614 bytes in 4 blocks
==10606== suppressed: 0 bytes in 0 blocks
```
參考[LanKuDot (李昆憶)](https://hackmd.io/s/HJFhaiAp#asanaddres-sanitizer)，這裡面提到 asan 這個東西，在 Makefile 裡面也有放上相關的參數
```
ifdef CHECK_LEAK
CFLAGS_common += -fsanitize=address -fno-omit-frame-pointer
endif
```
大概是誘惑我去用用看
```
$ make CHECK_LEAK=1
$ ./phonebook_opt
orginal file size = 3206080
size of entry : 24 bytes
execution time of append() : 0.010399 sec
execution time of findName() : 0.007910 sec
```
！！！我還以為哪個指令下錯了，結果再去共筆看一下，原來我發現剩餘的 memory leak 也是屬於 `still reachable`
這邊因為還有有效指標指著未被 free 的記憶體區塊，並不會對程式造成什麼影響，所以 asan 才會沒有顯示出錯誤訊息
https://hackmd.io/s/BkN1JNQp
alligment!!?why??
對齊是為了 entry pool 每段名字一樣長可以方便
但是由於我們不知道每個字元的 offset，所以我先將 file整理成 16 char alignment，之後再使用 mmap()，就能夠直接 offset 16到下一個 word了。
### mmap
* original原本一直用append fget去拿資料,這樣太慢
* 因此我們用mmap比較快
* file.txt => 把它對應到memory可以節省到i/o處理的資源
* mmap 用法
http://man7.org/linux/man-pages/man2/mmap.2.html
```clike=
#include <sys/mman.h>
void *mmap(void *addr, size_t length, int prot, int flags,
int fd, off_t offset);
int munmap(void *addr, size_t length);
```
size_t => unsigned int
offset ：pointer面對string指向下一比資料的起始位置
* phonebook concurrent mmap 修改的地方
```clike=
char *map;//void pointer 需要拿來提取memory裡面的資料
map = mmap(NULL, file_size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);
```
[memory pool](https://hackmd.io/KwMwLGDGBMAMCcBaaA2AzADkWAJgRgENF4B2fYlOE2A+HAI0jCA=?both)
### aligment
```clike=
```
在main.c裡面會用到！！！
因為經過alligment後每筆資料大小現在是一樣的,故可以用固定的offset來存取資料
### main.c
```clike=
text_align(DICT_FILE, ALIGN_FILE, MAX_LAST_NAME_SIZE);
//讀完原始檔後 由text_align這個function每筆資料寫成同樣大小
//Max_Last_Name （每筆資料寫成16個byte的大小）
//if define 寫在h檔裡面
```
```clike=
/* build the entry"*/
entry *pHead, *e;
// entry就是linkedlist的結構
// 宣告 e, pHead兩個指向 entry 結構的指標
/* typedef struct __PHONE_BOOK_ENTRY {
char *lastName;
struct __PHONE_BOOK_ENTRY *pNext;
pdetail dtl;
} entry;
*/
```
```clike=
map = mmap(NULL, file_size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);
/*
* 我們把align（對齊的file每行固定大小）對應到memory裡面
* 因為是記憶體,所以要已指標的形式來宣告 map
*
*/
```
```clike=
entry_pool = (entry *)malloc(sizeof(entry) *
file_size / MAX_LAST_NAME_SIZE);
```
這一段就是memory pool的部份先malloc要的記憶體 省時間
```clike=
for (int i = 0; i < THREAD_NUM; i++)
// Created by malloc, remeber to free them.
thread_args[i] = createThread_arg(map + MAX_LAST_NAME_SIZE * i, map + file_size, i,
THREAD_NUM, entry_pool + i);
```
因為我們要對append（寫好的function)做平行處理
所以我們來設定參數
```clike=
for (int i = 0; i < THREAD_NUM; i++)
pthread_create(&threads[i], NULL, (void *)&append, (void *)thread_args[i]);
```
對append開始做平行處理！！！
```clike=
for (int i = 0; i < THREAD_NUM; i++)
pthread_join(threads[i], NULL);
```
因為thread做完,把thread給（destory)關掉
```clike=
/* Connect the linked list of each thread */
for (int i = 0; i < THREAD_NUM; i++) {
if (i == 0) {
pHead = thread_args[i]->lEntry_head->pNext;
DEBUG_LOG("Connect %d head string %s %p\n", i,
pHead->lastName, thread_args[i]->data_begin);
} else {
e->pNext = thread_args[i]->lEntry_head->pNext;
DEBUG_LOG("Connect %d head string %s %p\n", i,
e->pNext->lastName, thread_args[i]->data_begin);
}
e = thread_args[i]->lEntry_tail;
DEBUG_LOG("Connect %d tail string %s %p\n", i,
e->lastName, thread_args[i]->data_begin);
DEBUG_LOG("round %d\n", i);
}
```
example:
假設現在有1,2,3,4得資料
thraed1拿資料1
thread2拿資料2
thread3拿資料3
thread4拿資料4
所以要拿出資料需要將所有的資料儲存在一起
```clike=
/* Find the given entry */
/* the givn last name to find */
char input[MAX_LAST_NAME_SIZE] = "zyxel";
e = pHead;
```
你要找字串的名子
```clike=
/* Release memory */
#ifndef OPT
while (pHead) {
e = pHead;
pHead = pHead->pNext;
free(e);
}
```
未優話的部份
```clike=
#else
/* Release memory */
/* Free the allocated detail entry */
e = pHead;
while (e) {
free(e->dtl);
e = e->pNext;
}
free(entry_pool);
for (int i = 0; i < THREAD_NUM; ++i)
free(thread_args[i]);
munmap(map, file_size);
close(fd);
```
Sign in with Wallet
Connect another wallet