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
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。
Overview
這次關於 linked list 的實作,並不是我第一次寫這系列的操作,不過從題目上的設計就可以了解到,我以前忽略的很多細節,甚至都已經假設輸入指標必定是有效的,沒做任何的 assertion 甚至考量到程式因此崩潰的狀況,我想這就是為什麼一個好的測試,對於工業級的產品來說那麼重要了。除此之外,這份作業內的 q_test
這支程式也讓我深深了解為何之前提到過的 google-test 和 google-mock 會應運而生了
如我在上節所述,我在實作這個 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 初始化一個常數。free
的指標。以往在做 free 時很怕會釋放到 NULL pointer 所以會多做一個 if 做判斷,在看了 man page 之後才知道這是沒必要的動作,但同一記憶體位置並不能被二次釋放。在實作上,撇除 q 本身是 NULL 以及 malloc 失敗回傳 NULL 的狀況下,可以把 q_insert_head 分為兩種狀況:
q->head
q->head
指向新節點與 q_insert_head 類似一樣以 strdup 為新節點配置記憶體及分為兩種狀況考慮,不過註解內有要求實作上必須要在常數的時間複雜度內完成,這也就是為什麼想要在 queue_t
內多一個 member 的原因:
list 內部目前沒有任何節點:
list 已存在節點:
若 q 為有效指標則分為兩種狀況處理:
移除 head 的條件是 q 必須為有效指標且 size > 0,在實作移除節點時,必須注意移除節點後可能會分為兩個狀況,沒有節點或是只剩一個或是多個節點:
q->head = q->head->next
並不會受到影響因為會被更新為 NULL。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。
以 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 的新增和刪除結點上,對於一些步驟並不了解存在的意義:
qtest 內類似 error handling 的機制