2017q1 Team6 phonebook-concurrent

contribute by <illusion030, ryanwang522, hugikun999, claaaaassic, Weinux>

tags: `sysprog2017`

Github
整理過後的共筆

作業要求

比照 B07: phonebook-concurrent 要求，嘗試重構 (refactor) 給定的程式碼，使得程式更容易閱讀和維護。不只是在共筆上用文字提出良性詳盡的批評，也該反映在程式碼的變革

Code Refactoring

refactoring（重構）的定義：「在不改變軟體的外在行為之下，改善既有軟體的內部設計」
侯捷：「作為一個程式員，任誰都有看不順眼手上程式碼的經驗 —— 程式碼來自你鄰桌那個菜鳥，或三個月前的自己。面臨此境，有人選擇得過且過；然而根據我對『程式員』人格特質的了解，更多人盼望插手整頓。挽起袖子劍及履及，其勇可嘉其慮未縝。過去或許不得不暴虎憑河，忍受風險。現在，有了嚴謹的重構準則和嚴密的重構手法，『穩定中求發展』終於有了保障。」

原始程式碼的缺點

在原本的程式的 main.c 充滿大量的 define 來區隔不同版本的實作，讓程式碼看起來很雜亂

































#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 或 phonebook_opt.c 中都有一個 function 叫 findName


entry *findName(char lastname[], entry *pHead)

叫 findName 不太精確，因為是傳入 lastname 來 find，所以應該改成更精確的名字

整個程式中出現兩個 header file 分別為 phonebook_orig.h 及 phonebook_opt.h 對應到不同的實作，這樣代表每增加一個實作就需要重新寫一個 header file，可以考慮共用同一個 header file 就好

在原本的 phonebook_opt.c 裡的 append() 函式中






























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()


















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 改成看得出意思的名稱






















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 和 async.c 將許多功能包成 API






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

OO的一個非常重要的特性，其實就是延後 function bind 的時間，一般 source code 通過 compiler 編譯成 executable，程式會有什麼樣的行為在編譯成執行檔的時期就已經決定好，然而如果透過 polymorphism 可以延後到程式執行時才依據收到訊息的物件而做出不同的反應行為。C++ 本身是OO語言，可以利用 Inheritance 和 Overriding 來達到多型的目的。
C 就沒有 Inheritance 和 Overriding 可以使用，因此只能利用別的方法達到多型的目的，參考了這篇的方法，其實就是在 strcut 中利用 pointer 來讓各個 instance 可以共用。類似做成 array ，再將各個版本的 function 放進這個 array。如此就可以在執行時期依據不同的版本選擇不同的反應行為。

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 的包裝方式將 header file 整合成一個 phonebook.h 並且有 phonebook API 的 provider 供選擇




























...

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 裡的資訊












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 裡的內容
















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 裡的值


info f = pb->getInfo(pb->getlastName(lastname, pHEAD));

其中 __PHONE_BOOK_ENTRY 因為 struct 的內容在 original 版本跟 optimal 的版本中不一樣，所以在 .c 檔裡面給內容
phonebook_orig.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



















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 宣告 Provider 並且執行時從外部傳入選擇要用哪一種 Provider





Phonebook *PBProvider[] = { 
    &OrigPBProvider,
    &ThreadPBProvider,
    &DllPBProvider,
};



assert((argc == 2) && "Usage: ./phonebook impl_selector");
assert((atoi(argv[1]) < 3) && "Can't find impl");
Phonebook *pb = PBProvider[atoi(argv[1])];

編譯時編譯成一個執行檔


phonebook: $(SRCS_common) phonebook_orig.c phonebook_thread.c phonebook_dll.c
    $(CC) $(CFLAGS) -o $@ $^

測試時傳入數字來選擇不同實作










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 變得更簡潔 (許多事變成只需要呼叫 API)
- 因為在 phonebook.h 中沒有給 __PHONE_BOOK_ENTRY 的內容，所以不能在 main.c 中修改 entry 的值

嘗試 C11 _Generic

看到 yen-wu 的共筆中提到，如果程式碼中需要 malloc 給許多不同型態的指標變數空間，可以使用 C11 _Generic 功能來使得程式碼更為簡潔，正好為重構的精神之一，只是 phonebook-concurrent 裡並沒有頻繁的 malloc ，導致看起來也只是把 malloc 換成另一種寫法而已＠＠。
- 參考了網路上的範例，都只有對基本變數型態使用，所以不太確定對於自訂型態能否有預期的效果，自己寫了個小程式測試過後發竟然可以！
- 實作（entry 的型態是指向 __PHONE_BOOK_ENTRY 的指標）







#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 空間，就只要執行


var = allocSpace(var);

如果要分配連續的空間（如五個該型態的陣列）如下


var = allocSpaceFor(var, 5);

修改 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 的檔案






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.





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結構在對照 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 結構，用來串接自定義結構的指標
```
typedef struct __LIST_HEAD{
    struct __LIST_HEAD *next, *prev;
} list_head;
```
- 在（舉例用的）結構中加入用來串接的指標，就可以得到一個雙向連結串列的節點，並且利用 list 就可以去取得資料
```
typedef struct __STUDENT {
    char lastName[16];
    int id;
    list_head list;
} phonebook;
```
- offsetof （在 stddef.h 裡可以看到）
  - 可以用來取得在 type 結構裡，成員 member 相對於結構起始位址的偏移量
  - 針對 null pointer 做強制轉型取得其成員的位址，覺得是因為 null pointer 的位址是 0，不過對 null pointer 不是很熟悉，還有待查證
```
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
```
- list_entry
  - 丟入一個 list_head 的指標，回傳該 list_head 所屬於的 type 型態的指標，用來取得存放資料的結構
  - 原理是用 list_head 的位址減去自己在存放資料的結構裡的偏移量去取得該結構的位址
```
#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
```
#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;
```
#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 宣告實作的 Provider
  - 在 main.c 中新增實作的 Provider
  - 在 Makefile 中多加上 Compile 時會用到的檔案
- 配置記憶體給變數 var 時只要呼叫 allocSpace 的macro，e.g
```
var = allocSpace(var);
```
  - 需要用到陣列時（第二個參數代表元素個數）
```
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()) 的執行時間增加？
韻華

改變 inline 寫法變為 always_inline 後
有包含 text-align
沒包含 text-align