Try   HackMD

2018q3 Homework2(lab0)

contributed by <posutsai>

實驗環境
Ubuntu 16.04.5 LTS
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 60
Model name: Intel® Core™ i7-4770 CPU @ > 3.40GHz
Stepping: 3
CPU MHz: 3454.851
CPU max MHz: 3900.0000
CPU min MHz: 800.0000
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 8192K

queue.h 資料結構的設計







/* Queue structure */
typedef struct {
    list_ele_t *head; 
    list_ele_t *tail;
    int size;
} queue_t;

  • tail pointer

    在實作 q_insert_tail function 發現，因為必須要在 O(1) 的時間複雜度完成勢必得要有一個 pointer 指向 list 的尾端，而不是每一次都從 head 一路走到底。

    當 list 內只有單一節點時，會讓 head 和 tail 都指向這唯一節點。

  • size

    有了這樣的一個 member 可以讓 q_size 在常數時間內回傳 list 內的 node 總數，而不是每次都計算一次。

    在實作 queue.c 當需要存取節點總數時，必須以 q->size 的型式，而不是呼叫 q_size() 函式，原因是在實作 q_size 函式時，若 q 是 NULL pointer 依然回傳 0 ，實作時因為這點困擾很久。

    不懂的點是為何要設定 q_size 是這樣的輸出型式，以物件導向的觀點， size 這一個 member 應該是 private 必須透過 getter 去存取，如果是我設計的話，可能會讓 q 是 NULL pointer 的情況回傳 -1。

queue.c 內部函數實作

  • Overview

    這次關於 linked list 的實作，並不是我第一次寫這系列的操作，不過從題目上的設計就可以了解到，我以前忽略的很多細節，甚至都已經假設輸入指標必定是有效的，沒做任何的 assertion 甚至考量到程式因此崩潰的狀況，我想這就是為什麼一個好的測試，對於工業級的產品來說那麼重要了。除此之外，這份作業內的 q_test 這支程式也讓我深深了解為何之前提到過的 google-test 和 google-mock 會應運而生了

  • queue_new

    如我在上節所述，我在實作這個 q_new 時才意識到 malloc 可能會回傳 NULL pointer，從 malloc 的 man page 可以看到，在此摘錄幾點使用 malloc 來做 dynamic allocation 需要注意的事項:

    • 經由 malloc 而來的記憶體並未初始化，要注意 linux kernel 內的 over commit 機制， kernel 允許 process 能申請使用的記憶體空間不等於實際可以拿來分配使用的空間量，而當多個 process 同時使用太多記憶體空間時會導致 kernel OOM killer 把 process 結束掉。至於在這次作業內怎麼解決可能會有 overcommit 的問題，因為必須使用到那段記憶體，作業系統才會決定是否允許使用，在 harness.c test_malloc 函數內，在一開始就會先以 memset 初始化一個常數。
    • 當 size 參數為 0 時，不是回傳一個 NULL pointer 就是一個可以被丟進 free 的指標。以往在做 free 時很怕會釋放到 NULL pointer 所以會多做一個 if 做判斷，在看了 man page 之後才知道這是沒必要的動作，但同一記憶體位置並不能被二次釋放。
    • 當 malloc 過程出現錯誤時會回傳 NULL。
    • 關於 malloc 這樣 memory allocation 的實作，我在 tensorflow 內部透過 macro 去開啟不同的實作方式，他採用的是 jemalloc 與之相對應的還有 google 開發的 tcmalloc ，以及預設採用 ptmalloc ，三者最主要的差異在於對 garbage collection 的處理不同導致相對於 ptmalloc 另外兩種模型的碎片化問題不會那麼嚴重。而底層跟作業系統申請 memory 則是使用 mmap。

  • q_insert_head

    在實作上，撇除 q 本身是 NULL 以及 malloc 失敗回傳 NULL 的狀況下，可以把 q_insert_head 分為兩種狀況:

    • 若 list 內沒有任何節點:
      • 把 s 以 strdup 複製一份 assign 進新節點
      • head 和 tail 指標都要指向插入之唯一節點
      • 把單一節點的 next 指標指向 NULL
    • 若 list 內已存在節點:
      • 把新節點的 next 指向原先的 q->head
      • 把 q->head 指向新節點
      • 把 s 以 strdup 複製一份 assign 進新節點






















bool q_insert_head(queue_t *q, char *s) {
    if (q == NULL)
        return false;
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL) {
        return false;
    }
    // 在為新節點配置記憶體時，採用的是 strdup ，
    // 所以在 remove 時記得要 free
    newh->value = strdup(s);
    if (q->head == NULL) {
        q->head = newh;
        q->tail = newh;
        newh->next = NULL;
    } else {
        newh->next = q->head;
        q->head = newh;
    }
    q->size++;
    return true;
}

  • q_insert_tail

    與 q_insert_head 類似一樣以 strdup 為新節點配置記憶體及分為兩種狀況考慮，不過註解內有要求實作上必須要在常數的時間複雜度內完成，這也就是為什麼想要在 queue_t 內多一個 member 的原因:

    • list 內部目前沒有任何節點:

      • 把所要求的字串 assign 進新節點
      • head 和 tail 都指向新節點
      • 新節點的 next 設為 NULL

    • list 已存在節點:

      • 把 s 以 strdup 複製一份 assign 進新節點
      • 把原先 tail 指向的節點之 next 指向新節點
      • 更新 tail 指向新節點



















bool q_insert_tail(queue_t *q, char *s) {
    if (q == NULL)
        return false;
    list_ele_t *newt = malloc(sizeof(list_ele_t));
    if (newt == NULL) {
        return false;
    }
    newt->next = NULL;
    newt->value = strdup(s);
    if (q->tail == NULL) {
        q->head = newt;
        q->tail = newt;
    } else {
        q->tail->next = newt;
        q->tail = newt;
    }
    q->size++;
    return true;
}

  • q_free

    若 q 為有效指標則分為兩種狀況處理:

    • list 內沒有任何節點，則針對 q 這個指標做 free
    • 若 list 內還有節點，則遍歷整個 list ， free 各個節點，但在 free 的同時也會失去跟下一個節點的連結，所以要先用 tmp 存起來。















void q_free(queue_t *q) {
    if (q != NULL) {
        if (q->size == 0) {
            free(q);
            return;
        }
        for (list_ele_t *cur = q->head; cur != NULL;) {
            list_ele_t *tmp = cur->next;
            free(cur);
            cur = tmp;
        }
        /* Free queue structure */
        free(q);
    }

  • q_remove_head

    移除 head 的條件是 q 必須為有效指標且 size > 0，在實作移除節點時，必須注意移除節點後可能會分為兩個狀況，沒有節點或是只剩一個或是多個節點:

    • 先分析有剩餘節點的狀況
      • 先用一個 tmp pointer 儲存原始 head 作為後來的 free 以及字串處理使用
      • 更新 q->head 並調整 size
      • 題目要求要複製 bufsize - 1 長度的字串到 sp ，並在字串最後補上節數字元 '\0'，我這裡使用的是 memcpy 而非 strdup，memcpy 的第三個參數，表示的是要拷貝的長度，所以我們必須先計算這樣的長度代表幾個 char 並在適當位置補上結束字元。
      • 最後在針對 tmp 做釋放。
    • 若是在移除 head 之後，list 內沒有任何節點
      • 重複上述所有步驟， q->head = q->head->next 並不會受到影響因為會被更新為 NULL。
      • 由於現在 list 內沒有任一結點，所以我們也要把 tail 設為 NULL ，在這個地方卡了很久。
















bool q_remove_head(queue_t *q, char *sp, size_t bufsize) {
    if (q == NULL || q->size == 0)
        return false;
    list_ele_t *tmp = q->head;
    q->head = q->head->next;
    int copy_len = bufsize / sizeof(char) - 1;
    if (sp != NULL) {
        memcpy(sp, tmp->value, copy_len);
        sp[copy_len] = '\0';
    }
    free(tmp);
    q->size--;
    if (q->size == 0)
        q->tail = NULL;
    return true;
}

測試環境的分析

  • q_reverse 內對 malloc 的偵測機制

    一直對於 q_reverse 內如何偵測實作細節是否有用到 malloc 感到好奇，從 q_test.c 可以看到 do_reverse 函數內呼叫了兩次 set_noallocate_mode 去調整是否可以呼叫 malloc 的狀態，重點在於使用 macro 把 malloc 轉為 test_malloc，所以我們看似使用預設的 malloc 但其實是呼叫 test_malloc 。
    我原先以為他是想辦法在我們呼叫 glibc malloc 內寫一層類似 middle ware 的結構，若只是以 preprocess 的方式做偵測的話，可以用 mmap, brk 和 sbrk 這類的系統呼叫替代而不被偵測出來，事實上在 glibc 內也是以演算法去決定使用哪個系統呼叫，比較好的做法是使用 GNU 提供的 malloc hook 在 do_reverse 先註冊會讓他跳出一個 exception，這樣的做法可以更有效的偵測是否使用 malloc。 jemalloc 和 tcmalloc 也都是以這樣的手法在不影響原始程式碼的情形下改變 memory management model，基於上述理由，我試著以 glibc hook 實作 malloc detection。

    







































    ​​​​// modify harness.[c|h] to add following code
​​​​#include <malloc.h>
​​​​
​​​​// use two function pointer to store original malloc and free hook
​​​​void *(original_malloc_hook) (size_t size, const void *caller);
​​​​void (original_free_hook) (void *ptr, const void *caller);
​​​​
​​​​void hook_init() {
​​​​    original_malloc_hook = __malloc_hook;
​​​​    original_free_hook = __free_hook;
​​​​    // test_malloc prototype 改為 void *test_malloc (size_t, const void *)
​​​​    __malloc_hook = test_malloc; 
​​​​    // 同理，把 test_free 改為 void test_free(void *, const void *)
​​​​    __free_hook = test_free;
​​​​}
​​​​
​​​​void *test_malloc(size_t size, const void *caller) {
​​​​    __malloc_hook = original_malloc_hook;
​​​​    __free_hook = original_free_hook;
​​​​    .... // test_malloc 內原始程式碼
​​​​    __malloc_hook = test_malloc;
​​​​    __free_hook = test_free;
​​​​}
​​​​
​​​​void test_free(void *ptr, const void *caller) {
​​​​    __malloc_hook = original_malloc_hook;
​​​​    __free_hook = original_free_hook;
​​​​    .... // test_free 內原始程式碼
​​​​    __malloc_hook = test_malloc;
​​​​    __free_hook = test_free;
​​​​}
​​​​
​​​​// -----------------------------------------------------
​​​​// qtest.c
​​​​int main() {
​​​​// command parser ...
​​​​    hook_init();
​​​​    queue_init();
​​​​    ....
​​​​}

    以 make test 進行編譯時，發現會 free 產生問題，進一步發現在 test_free 裡大量使用 MAGICHEADER 、 MAGICFOOTER 和 MAGICFREE 這三個 macro ，似乎在原版的 test_malloc 和 test_free 內並不只是單純的以 preprocessor 替換，猜測可能是為了追蹤尚有多少空間位被釋放，採取間接的方式釋放記憶體。

    harness.c 內有自己實作一個 doubly linked list 去把每一個 allocated chunk 彼此相連，並以 block_ele_t 這樣的資料結構儲存相關的 metadata ，在 test_malloc 內可以看到在每個 block 的尾端放入 MAGICFOOTER 的值，目的在於辨認當想要 free 時，是否位於合法空間，並以 find_header 找出這個 block 的起始指標，並把 header 到 footer 之間的記憶體通通 assign 1，最後在把整個 block 釋放掉，在整個對 doubly linked list 的新增和刪除結點上，對於一些步驟並不了解存在的意義:

    • 不懂為何需要 header 和 footer 都 assign MAGICFREE，且 pay_load 內通通設為 0x55，在 test_malloc 內可以理解，但在 test_free 就不懂為何要這樣做了。
    • 從程式碼可以看出 MAGICHEAD 和 MAGICFOOTER 是作為辨認合法性的用途，但這個做法應該很難保證記憶體內容不會是我們設定的值 0xdeadbeef 或是 0xbeefdead，感覺是個不太好的作法。

  • qtest 內類似 error handling 的機制

Last changed by 
 
Yueh Lin Tsai
0
569
Published on HackMD