2017q1 Team6 phonebook-concurrent
===
contribute by <`illusion030`, `ryanwang522`, `hugikun999`, `claaaaassic`, `Weinux`>
###### tags: `sysprog2017`
[Github](https://github.com/ryanwang522/phonebook-concurrent)
[整理過後的共筆](https://hackmd.io/s/SklSEW6G-)
## 作業要求
* 比照 [B07: phonebook-concurrent](https://hackmd.io/s/rkOExTOoe) 要求，嘗試重構 (refactor) 給定的程式碼，使得程式更容易閱讀和維護。不只是在共筆上用文字提出良性詳盡的批評，也該反映在程式碼的變革
---
### Code Refactoring
* refactoring（重構）的定義：「在不改變軟體的外在行為之下，改善既有軟體的內部設計」
* 侯捷：「作為一個程式員，任誰都有看不順眼手上程式碼的經驗 —— 程式碼來自你鄰桌那個菜鳥，或三個月前的自己。面臨此境，有人選擇得過且過；然而根據我對『程式員』人格特質的了解，更多人盼望插手整頓。挽起袖子劍及履及，其勇可嘉其慮未縝。過去或許不得不暴虎憑河，忍受風險。現在，有了嚴謹的重構準則和嚴密的重構手法，『穩定中求發展』終於有了保障。」
## 原始程式碼的缺點
* 在原本的程式的 [main.c](https://github.com/sysprog21/phonebook-concurrent/blob/master/main.c) 充滿大量的 define 來區隔不同版本的實作，讓程式碼看起來很雜亂
```C=
#ifndef OPT
FILE *fp;
int i = 0;
char line[MAX_LAST_NAME_SIZE];
#else
struct timespec mid;
#endif
struct timespec start, end;
double cpu_time1, cpu_time2;
/* File preprocessing */
#ifndef OPT
/* check file opening */
fp = fopen(DICT_FILE, "r");
if (!fp) {
printf("cannot open the file\n");
return -1;
}
#else
text_align(DICT_FILE, ALIGN_FILE, MAX_LAST_NAME_SIZE);
int fd = open(ALIGN_FILE, O_RDONLY | O_NONBLOCK);
off_t file_size = fsize(ALIGN_FILE);
#endif
/* Build the entry */
entry *pHead, *e;
printf("size of entry : %lu bytes\n", sizeof(entry));
#if defined(OPT)
char *map;
entry *entry_pool;
pthread_t threads[THREAD_NUM];
thread_arg *thread_args[THREAD_NUM];
```
* 這樣做的問題是當你有其他版本時，你會需要更多的 `#ifdef` `#elif` 來實作不同的版本，版本越多，程式碼就越難閱讀
---
* 在不管是 [phonebook_orig.c](https://github.com/sysprog21/phonebook-concurrent/blob/master/phonebook_orig.c) 或 [phonebook_opt.c](https://github.com/sysprog21/phonebook-concurrent/blob/master/phonebook_opt.c) 中都有一個 function 叫 findName
```C=
entry *findName(char lastname[], entry *pHead)
```
* 叫 findName 不太精確，因為是傳入 lastname 來 find，所以應該改成更精確的名字
---
* 整個程式中出現兩個 header file 分別為 [phonebook_orig.h](https://github.com/sysprog21/phonebook-concurrent/blob/master/phonebook_orig.h) 及 [phonebook_opt.h](https://github.com/sysprog21/phonebook-concurrent/blob/master/phonebook_opt.h) 對應到不同的實作，這樣代表每增加一個實作就需要重新寫一個 header file，可以考慮共用同一個 header file 就好
---
* 在原本的 [phonebook_opt.c](https://github.com/sysprog21/phonebook-concurrent/blob/master/phonebook_opt.c) 裡的 `append()` 函式中
```C=
static void append(void *arg)
{
struct timespec start, end;
double cpu_time;
clock_gettime(CLOCK_REALTIME, &start);
thread_arg *t_arg = (thread_arg *) arg;
int count = 0;
entry *j = t_arg->lEntryPool_begin;
for (char *i = t_arg->data_begin; i < t_arg->data_end;
i += MAX_LAST_NAME_SIZE * t_arg->numOfThread,
j += t_arg->numOfThread, count++) {
/* Append the new at the end of the local linked list */
t_arg->lEntry_tail->pNext = j;
t_arg->lEntry_tail = t_arg->lEntry_tail->pNext;
t_arg->lEntry_tail->lastName = i;
t_arg->lEntry_tail->pNext = NULL;
t_arg->lEntry_tail->dtl = NULL;
DEBUG_LOG("thread %d t_argend string = %s\n",
t_arg->threadID, t_arg->lEntry_tail->lastName);
}
clock_gettime(CLOCK_REALTIME, &end);
cpu_time = diff_in_second(start, end);
DEBUG_LOG("thread take %lf sec, count %d\n", cpu_time, count);
pthread_exit(NULL);
}
```
* for-loop 負責產生每個執行序所負責的 entry linked-list ，然而由於需要傳入 thread 的參數太多加上一些 debug message，導致整個迴圈看起來很雜亂。
* 又有不只一個變量需要隨著迴圈變動，第一次看這段 code 無法很直觀的知道實際上的作用
* 再者 `i` , `j` 的命名也不優雅，畢竟不只是單單代表著迴圈的次數
---
* 原本的程式碼中缺乏完整的 Exception handling 機制
* 例如 `phonebook_opt.c` 裡的 `findName()`
```C=
static entry *findName(char lastname[], entry *pHead)
{
size_t len = strlen(lastname);
while (pHead) {
if (strncasecmp(lastname, pHead->lastName, len) == 0
&& (pHead->lastName[len] == '\n' ||
pHead->lastName[len] == '\0')) {
pHead->lastName[len] = '\0';
if (!pHead->dtl)
pHead->dtl = (pdetail) malloc(sizeof(detail));
return pHead;
}
DEBUG_LOG("find string = %s\n", pHead->lastName);
prev = pHead;
pHead = pHead->pNext;
}
return NULL;
}
```
* 其中沒有考慮到 `malloc()` 函式呼叫失敗的例外處理
---
## 對不直觀的程式碼進行調整
* 將 `findName()` 改名為 `findLastName()` 因為是用 lastName 去 find，改名後比較清楚 function 的功能
* 把 `append()` 的 for-loop 改用 while 表示，因為太多變量需要隨著迴圈改變
* 修改一些變數命名，將原本沒有意義的 `i`，`j` 改成看得出意思的名稱
```C=
static void append(void *arg)
{
// Remove previous debug code
thread_arg *t_arg = (thread_arg *) arg;
char *data = t_arg->data_begin;
entry localEntry = t_arg->lEntryPool_begin;
while (data < t_arg->data_end) {
t_arg->lEntry_tail->pNext = localEntry;
t_arg->lEntry_tail = t_arg->lEntry_tail->pNext;
t_arg->lEntry_tail->lastName = data;
t_arg->lEntry_tail->pNext = NULL;
t_arg->lEntry_tail->dtl = NULL;
data += MAX_LAST_NAME_SIZE * t_arg->numOfThread;
localEntry += t_arg->numOfThread;
}
pthread_exit(NULL);
}
```
* 適當的函數命名搭配註解有助於日後修改維護，也使得程式碼更讓人易懂。
## API
* 參考 [async.h](https://github.com/embedded2016/server-framework/blob/master/async.h) 和 [async.c](https://github.com/embedded2016/server-framework/blob/master/async.c) 將許多功能包成 API
```C=
entry find(char *lastName, entry pHead);
entry import(char *fileName);
void remove(char *lastName, entry pHead);
void write(double cpu_time[]);
void free(entry pHead);
info (*getInfo)(entry e);
```
### [polymorphism](http://antrash.pixnet.net/blog/post/69452213-%E8%AB%96%E7%89%A9%E4%BB%B6%E5%B0%8E%E5%90%91part-5%EF%BC%9Apolymorphism)
OO的一個非常重要的特性，其實就是**延後 function bind 的時間**，一般 source code 通過 compiler 編譯成 executable，程式會有什麼樣的行為在編譯成執行檔的時期就已經決定好，然而如果透過 polymorphism 可以延後到程式執行時才依據收到訊息的物件而做出不同的反應行為。C++ 本身是OO語言，可以利用 **Inheritance** 和 **Overriding** 來達到多型的目的。
C 就沒有 **Inheritance** 和 **Overriding** 可以使用，因此只能利用別的方法達到多型的目的，參考了[這篇](https://stackoverflow.com/questions/8194250/polymorphism-in-c)的方法，其實就是在 strcut 中利用 pointer 來讓各個 instance 可以共用。類似做成 array ，再將各個版本的 function 放進這個 array。如此就可以在執行時期依據不同的版本選擇不同的反應行為。
```C
typedef struct __API {
struct find_table_ *ftable_;
struct import_table_ *itable_;
void (*remove)(char *lastName, entry pHead);
void (*write)(double cpu_time[]);
void (*free)(entry pHead);
info (*getInfo)(entry e);
} Phonebook;
```
* 接著參考 [B10 : Matrix](https://hackmd.io/s/rkrrpHm2e) 的包裝方式將 header file 整合成一個 [phonebook.h](https://github.com/ryanwang522/phonebook-concurrent/blob/master/phonebook.h) 並且有 phonebook API 的 provider 供選擇
```C=
...
typedef struct __PHONE_BOOK_ENTRY *entry;
typedef struct __PHONE_BOOK_ENTRY pbEntry;
typedef struct __PHONE_BOOK_INFO *info;
typedef struct __PHONE_BOOK_INFO pbInfo;
...
typedef struct __API {
struct find_table_ *ftable_;
struct import_table_ *itable_;
void (*remove)(char *lastName, entry pHead);
void (*write)(double cpu_time[]);
void (*free)(entry pHead);
info (*getInfo)(entry e);
} Phonebook;
...
extern Phonebook OrigPBProvider;
extern Phonebook ThreadPBProvider;
extern Phonebook DllPBProvider;
...
```
* 增加 struct `__PHONE_BOOK_INFO` 來讓外界可以得到 PHONEBOOK 裡的資訊
```C=
struct __PHONE_BOOK_INFO {
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];
};
```
* API `getInfo()`，使用者呼叫後就可以得到 entry 裡的內容
```C=
static info getInfo(entry e)
{
info f = allocSpace(f);
assert(f && "malloc for f error");
strcpy(f->lastName, e->lastName);
strcpy(f->firstName, e->firstName);
strcpy(f->email, e->email);
strcpy(f->phone, e->phone);
strcpy(f->cell, e->cell);
strcpy(f->addr1, e->addr1);
strcpy(f->addr2, e->addr2);
strcpy(f->city, e->city);
strcpy(f->state, e->state);
strcpy(f->zip, e->zip);
return f;
}
```
* 在 main.c 裡可以這樣呼叫來得到我們給的 `lastname` 找到的 entry 裡的值
```C=
info f = pb->getInfo(pb->getlastName(lastname, pHEAD));
```
* 其中 `__PHONE_BOOK_ENTRY` 因為 struct 的內容在 original 版本跟 optimal 的版本中不一樣，所以在 .c 檔裡面給內容
* [phonebook_orig.c](https://github.com/ryanwang522/phonebook-concurrent/blob/master/phonebook_orig.c)
```C=
struct __PHONE_BOOK_ENTRY {
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;
};
```
* [phonebook_thread.c](https://github.com/ryanwang522/phonebook-concurrent/blob/master/phonebook_thread.c)
```C=
typedef struct _detail {
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];
} detail;
typedef detail *pdetail;
struct __PHONE_BOOK_ENTRY {
char *lastName;
struct __PHONE_BOOK_ENTRY *pNext;
pdetail dtl;
};
```
* 在 [main.c](https://github.com/ryanwang522/phonebook-concurrent/blob/master/main.c) 宣告 Provider 並且執行時從外部傳入選擇要用哪一種 Provider
```C=
Phonebook *PBProvider[] = {
&OrigPBProvider,
&ThreadPBProvider,
&DllPBProvider,
};
```
```C=
assert((argc == 2) && "Usage: ./phonebook impl_selector");
assert((atoi(argv[1]) < 3) && "Can't find impl");
Phonebook *pb = PBProvider[atoi(argv[1])];
```
* 編譯時編譯成一個執行檔
```Makefile=
phonebook: $(SRCS_common) phonebook_orig.c phonebook_thread.c phonebook_dll.c
$(CC) $(CFLAGS) -o $@ $^
```
* 測試時傳入數字來選擇不同實作
```Makefile=
cache-test: $(EXEC)
perf stat --repeat 100 \
-e cache-misses,cache-references,instructions,cycles \
./phonebook 0
perf stat --repeat 100 \
-e cache-misses,cache-references,instructions,cycles \
./phonebook 1
perf stat --repeat 100 \
-e cache-misses,cache-references,instructions,cycles \
./phonebook 2
```
* 包成 API 後的影響
* [main.c](https://github.com/ryanwang522/phonebook-concurrent/blob/master/main.c) 變得更簡潔 (許多事變成只需要呼叫 API)
* 因為在 [phonebook.h](https://github.com/ryanwang522/phonebook-concurrent/blob/master/phonebook.h) 中沒有給 `__PHONE_BOOK_ENTRY` 的內容，所以不能在 [main.c](https://github.com/ryanwang522/phonebook-concurrent/blob/master/main.c) 中修改 entry 的值
---
## 嘗試 C11 _Generic
* 看到 [yen-wu 的共筆](https://hackmd.io/s/BykQDVTp#template-in-c) 中提到，如果程式碼中需要 malloc 給許多不同型態的指標變數空間，可以使用 C11 \_Generic 功能來使得程式碼更為簡潔，正好為重構的精神之一，只是 `phonebook-concurrent` 裡並沒有頻繁的 malloc ，導致看起來也只是把 malloc 換成另一種寫法而已＠＠。
* 參考了網路上的範例，都只有對基本變數型態使用，所以不太確定對於自訂型態能否有預期的效果，自己寫了個小程式測試過後發竟然可以！
* 實作 （entry 的型態是指向 `__PHONE_BOOK_ENTRY` 的指標）
```C=
#define gen(X) _Generic((X), \
int *: sizeof(int), \
entry: sizeof(entry), \
detail *: sizeof(detail), \
thread_arg *: sizeof(thread_arg))
#define allocSpace(type) malloc(gen(type))
#define allocSpaceFor(type, objectNum) malloc(gen(type) * objectNum)
```
* \_Generic 通常都搭配 Macro 使用，主要功能就是可以自動配對丟進去的參數的的型態，並且採用後面的敘述，自己覺得有點類似 `switch-case` 的作用
* 完成了上面的定義之後，如果要 malloc 給某個型態的指標變數 `var` 空間，就只要執行
```C=
var = allocSpace(var);
```
* 如果要分配連續的空間（如五個該型態的陣列）如下
```C=
var = allocSpaceFor(var, 5);
```
## 修改 Makefile
* 修改 Makefile 變得更簡潔
* 原始版本
```Makefile=
phonebook_orig: $(SRCS_common) phonebook_orig.c phonebook_orig.h
$(CC) $(CFLAGS_common) $(CFLAGS_orig) \
-DIMPL="\"$@.h\"" -o $@ \
$(SRCS_common) $@.c
phonebook_opt: $(SRCS_common) phonebook_opt.c phonebook_opt.h text_align.c
$(CC) $(CFLAGS_common) $(CFLAGS_opt) \
-DIMPL="\"$@.h\"" -o $@ \
$(SRCS_common) $@.c text_align.c
```
* 將會共用到的檔案放在 `SRCS_common`，其他實作獨立出來，並且用 $^ 來一次包含要 compile 的檔案
```Makefile=
SRCS_common = \
main.c \
text_align.c
phonebook: $(SRCS_common) phonebook_orig.c phonebook_thread.c phonebook_dll.c
$(CC) $(CFLAGS) -o $@ $^
```
## Exception handling
* 使用 assert 來實作 exception handling
* 用 `$man assert` 來看一下定義
```
void assert(scalar expression);
by calling abort(3) if expression is false
```
* 所以當 `assert()` 裡的值為 false 時，就會呼叫 `abort(3)` 來中止程式
* 實作在開檔跟 malloc 上，
e.g.
```C=
pHead->dtl = (pdetail) allocSpace(pHead->dtl);
assert(pHead->dtl && "malloc for pHead->dtl error");
...
output = fopen("opt.txt", "a");
assert(output && "fopen opt.txt error");
```
## Linux kernel *list.h*
* 先來看看他有什麼優點
* Type Oblivious
* 不管你的資料結構式什麼，list 都能夠「隨插即用」，意思是只要將 list 放入原先的結構裡就可以達成將資料雙向串接起來的目的了。
* Portable
* 因為使用的原理很基本只是指標跟記憶體的操作，在不同平台上都能夠運作（不然就不會存在在核心裡面了）
* Easy to Use
* 如同先前提到可以隨插即用，當我們把 list 放入結構中之後，就可以依照需求去使用他的 function 以及 macro，不管是要初始化、存取或是遍歷都很方便
* Readable
* 各種 function 跟 macro 都用很簡潔優雅的方式實作，了解原理後容易讀懂
* Saves Times
* 有現成的 linked-list 的各種功能函式使用，~~省去了自己串還會串錯要 debug 的時間~~
* 原理部份主要是參考了 [強大又好用的list_head結構](http://adrianhuang.blogspot.tw/2007/10/linux-kernel-listhead.html) 在對照 kernel 裡的實際 code（註解很詳細）， 去大致了解 `list.h` 的基本原理
* `list.h` 是 linux ~~內核~~核心裡的 double linked-list 實作，並且有許多好用的 macro 可以效仿
* 原本以為直接 `#include <linux/list.h>` 就可以直接使用，但是會出現編譯錯誤，因為 gcc 的預設 include path 是 `/usr/inlcude` ，但 list.h 是存放在 `/usr/src/linux-headers-x.x.x-xx/linux` 裡，才會導致錯誤。
* 想到的解決辦法就是直接複製 `list.h` 到 user space ，只是裡面也有用到一些其他在 kernel 才有的標頭檔，所以決定自己寫一個。
* 這裡介紹一些常用的 Macro 以及結構定義跟範例
* 有一點要注意的是，list.h 裡面的各種函式都是預設你的 linked-list 中 **head 為空的**，也就是說每一條 linked-list 從 `pHead->next` 才開始放資料
* list_head 結構，用來串接自定義結構的指標
```C=
typedef struct __LIST_HEAD{
struct __LIST_HEAD *next, *prev;
} list_head;
```
* 在（舉例用的）結構中加入用來串接的指標，就可以得到一個雙向連結串列的節點，並且利用 `list` 就可以去取得資料
```C=
typedef struct __STUDENT {
char lastName[16];
int id;
list_head list;
} phonebook;
```
* `offsetof` （在 `stddef.h` 裡可以看到）
* 可以用來取得在 `type` 結構裡，成員 `member` 相對於結構起始位址的偏移量
* 針對 null pointer 做強制轉型取得其成員的位址，覺得是因為 null pointer 的位址是 0，不過對 null pointer 不是很熟悉，還有待查證
```C=
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
```
* `list_entry`
* 丟入一個 `list_head` 的指標，回傳該 list_head 所屬於的 `type` 型態的指標，用來取得存放資料的結構
* 原理是用 list_head 的位址減去自己在存放資料的結構裡的偏移量去取得該結構的位址
```C=
#define list_entry(ptr, type, member) \
(type *)((char *)ptr - offsetof(type, member))
```
* `list_for_each`
* 用來走訪 list_head 節點的 for-loop ，通常和 `list_entry` 連用以取得實際資料，也因此產生了 `list_for_each_entry` 這個很方便的 macro
```C=
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
```
* `list_for_each_entry`
* 上述兩個的綜合體，pos 是用來走訪的 「結構指標型態」iterator，換言之介是可以直接利用給入的 pos 去取得結構成員的資料，如 `pos->id = 132;`
```C=
#define list_for_each_entry(pos, head, member) \
for (pos = list_first_entry(head, typeof(*pos), member); \
&pos->member != (head); \
pos = list_next_entry(pos, member))
```
* 講了這麼多，其實是想學習這些方便的 macro 用法去改進 `phonebook_opt.c` 的 linked-list 實作
* 根據老師的建議去參考 `list.h` 的 double linked list 實作，並且新增一個版本來進行比較，結果發現 `append()` 有些微地變快，`find()` 稍微便慢，還不太懂為什麼會有這一些微小的差異，還有待研究
---
## 總結
* Refactor 後的影響
* 程式碼變得更簡潔、更容易讀懂
* 程式更容易擴充以進行各種不同的測量實驗 e.g.當我們需要新增一個實作方式時我們需要
* 寫好實作的 `.c` 檔
* 在 [phonebook.h](https://github.com/ryanwang522/phonebook-concurrent/blob/master/phonebook.h) 宣告實作的 Provider
* 在 [main.c](https://github.com/ryanwang522/phonebook-concurrent/blob/master/main.c) 中新增實作的 Provider
* 在 [Makefile](https://github.com/ryanwang522/phonebook-concurrent/blob/master/Makefile) 中多加上 Compile 時會用到的檔案
* 配置記憶體給變數 `var` 時只要呼叫 `allocSpace` 的macro，e.g
```C=
var = allocSpace(var);
```
* 需要用到陣列時（第二個參數代表元素個數）
```C=
var = allocSpaceFor(var, 5);
```
---
## 實驗
* 比較三種方式
* 原始版本
* multi-thread 版本
* multi-thread + 參考 Linux kernel list.h 實作的 doubleLinkedList 版本
* 實驗方式
* 三種版本各跑 100 次取平均值
* Thread 數 = 4
* 將 text-align 從 `import()` 移到 `main.c` 裡
* 實驗發現 multi-thread 版本因為要執行 text-align 對齊，導致時間大幅增加，要想辦法降低 text-align 所帶來的成本
* 而 multi-thread 使用 doubleLinkedList 後的版本在 `import()` 時有減少，但在 `findLastName()` 時反而增加了
> 在想是不是因為 doublell 版本有大量的 function call 所以導致 `import()` (也可以說是 `append()`) 的執行時間增加？
[name=韻華]
* 改變 inline 寫法變為 always_inline 後
* 有包含 text-align
* 沒包含 text-align
---
## 參考資料
* [c11 \_Generic](http://en.cppreference.com/w/c/language/generic)
* [async.h](https://github.com/embedded2016/server-framework/blob/master/async.h)
* [async.c](https://github.com/embedded2016/server-framework)
* [B10 : Matrix](https://hackmd.io/s/rkrrpHm2e)
* [yen-wu 的共筆](https://hackmd.io/s/BykQDVTp#template-in-c)
* [polymorphism](http://antrash.pixnet.net/blog/post/69452213-%E8%AB%96%E7%89%A9%E4%BB%B6%E5%B0%8E%E5%90%91part-5%EF%BC%9Apolymorphism)
* [polymorphism-in-c](https://stackoverflow.com/questions/8194250/polymorphism-in-c)
* [強大又好用的list_head結構](http://adrianhuang.blogspot.tw/2007/10/linux-kernel-listhead.html)
* [Linux kernel Linked-list](https://isis.poly.edu/kulesh/stuff/src/klist/)
Sign in with Wallet
Connect another wallet