contributed by < NoahNut
>
Memory Leak
在實作所有 Function 的時候要注意,當有例外發生時,被 malloc 過的記憶體位置記得也要 free 掉,不然就會造成嚴重的 Memory leak。
無論標題和內文中,中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
程式碼縮排是 4 spaces,而不是 tab,請修改下方所有程式碼。把細節做好,才有態度挑戰難題。
在題目中提到 q_size
跟 q_insert_tail
都必須在 時間複雜度完成,所以必須隨時去紀錄 queue
的 size 跟 tail 的位置。
在實作這個函式時,遇到一個奇怪的問題,我在 allocate 一個空間給 string 時,我所使用的方式為 malloc
加 strcpy
,出來的 string 總為亂碼,直到使用 strdup
,目前還是未解?
這種例外處理,就必須要很注意是否有 memory leak 發生,因為在前面已經 malloc
過所以就必須要將分配的記憶體還回去。
原先是利用do while
的語法來寫,但是當是空 queue 的時候要 free 就會出現
ERROR: Segmentation fault occurred. You dereferenced a NULL or invalid pointer
跟ERROR: Freed queue, but 1 blocks are still allocated
原因是當 queue 是空的時候,在 do while
語法會先去跑其中的程式碼在看 while 的判斷後決定是否繼續跑下去,但是這樣就會 free 到 NULL,而造成錯誤。
head
跟 tail
指到同一個記憶體位置。用三個指標來為實作 reverse,一開始先將 tail 跟 head 互換,然後將 head 的 next 指向 tail,作為 reverse 到最後的 index。
先將 temp
跟 iterator
初始化,iterator
指向新的 tail,temp
指向 tail 的 next block。
在 while 迴圈中,temp_two
會指向現在 iterator
的位置,iterator
會前進到 temp
,如果 iterator
不是指向 tail,就將 temp
在往前一格,最後在將 iterator
所指的 next 反轉。
最後將 tail 的 next 指向 NULL。
add_cmd
和 add_param
,利用到 function pointer 的技巧,只要跟著其對於函式回傳值與傳入值的規範,就能統一性的新增 command。add_cmd
的 function 中,next_cmd 是在 link list 中 command 的值,而 last_loc 是指向 cmd_list 中的位置。Linked list 這樣的資料結構,可以讓刪除跟新增資料變得相當容易,只需要改變其 struct 中 next 所指向的資料。
在之後許多原本要存 Array 的資料都可以改成 linked list 來實作,方便新增跟刪除。
在 harness.h
中可以看到以下preprocessor
的格式。
用以區別在 queue.c
中所使用的 malloc 和 free 是另外實現的, 這樣的技巧就可以在有 define 特定 flag 的檔中實現特定函式。
以 qtest 為例,除了 queue.c
之外都在檔案起頭處有 define INTERNAL
,都是使用 C 本身的 malloc 跟 free 只有 queue.c
是使用在 harness.h
中實作的。
這邊先留著,需要查更多的資料跟實驗來更詳細的描述這邊在編譯時期是怎樣運作。 將你所不知道的 C 語言:前置處理器應用篇補完
這裡可以發現 define INTERNAL
在 include
前。
而在 test_malloc
中所分配得到的記憶體,是被紀錄在一個 allocated
的 double linked list,這個linked list的每一個node 都是由定義在 harness.h
中 block_ele_t
的結構中。
在結構的最後用到了 Arrays of Length Zero 的技巧,這樣最後 payload 大小就能夠直接在 malloc
的時候調整,在這個結構的最後面還要在加入一個 magic number 作為此記憶體區塊 tail 的標示。
magic header
block_ele_t
結構中,可以看到有定義 magic_header
這個是作為這個記憶體區塊是否合法操作判定的標誌,harness.c
中就定義了 MAGICHEADER 0xdeadbeef
和 MAGICFREE 0xffffffff
如果是 0xdeadbeef
就代表此區塊已經被合法 malloc, 利用這樣的方式在 free 的時候可以避免 free 到一塊非法的記憶體位置。
magic tail
MAGICFOOTER 0xbeefdead
作為此區塊的記憶體結束位置的判定。
magic number 這一詞的意思是在程式碼中有些被設計師寫死的常數,如果沒下註解,會造成後續來維護的設計師,黑人問號…
其最早出處雷神之鎚III競技場
的一段 平方根快速演算法,雖然得到很好的優化,但是某段有 magic number 的程式碼卻讓人充滿疑惑(超神的拉)。
magic tail
。block_ele_t
結構中的 magic_header
填入 MAGICHEADER
跟 payload_size
填入欲輸入 payload 的 size。find_footer
這個 function 找到其記憶體的最後的位置,size_t
的 pointer
指向記憶體區塊最後的位置,在將 magic tail
的值 assign 到最後記憶體區塊最後的位置。在這個函式中,找到最後這個區塊記憶體位置的方式,是傳入之前 malloc 過後的 pointer struct
,因為傳進去的記憶體位置會是這個結構,在程式的 heap
上初始的 memory address
在加上 payload size
跟 block_ele_t
這個結構的大小,就能找到此區塊的結尾。
new_block
的 next 會指向前一個被分配的記憶體區塊,並且 new_block
因為是最新被分配出來的記憶體區塊,所以其 prev 會指向 NULL。new_block
。new_block
assign 給 allocated
這個指向 double linked list header block_ele_t
結構型態的指標。這個函式作為 queue.c
中 free
函式的實作。
一開始先找到想要 free 的記憶體區塊的頭跟尾,分別利用 find_header
跟 find_footer
函式,然後在將這個區塊頭尾的 magic number
改成 MAGICFREE
標示這個區塊已經被 free 過了,避免 double free。
如果將 size_t footer = *find_footer(b) 改寫成 size_t *footer = find_footer(b),這樣在 *find_footer(b) = MAGICFREE 就可以用 *foot 直接來設值,不用在跳到
find_footer
這個 function。
- 在 gdb 中做 debug 或追蹤內部運作時,需要先將
harness.c
中的static int time_limit
調長,不然時間一到系統就是發出 signal 將程式 interrupt,發出錯誤訊息。
memset
將原本 payload 初始成 FILLCHAR
之後在將這個記憶體區塊從 double linked list 中拿掉。在
free
之前使用memset
可能原因是free
只將這塊記憶體歸還給作業系統,但裡面的值可能還在裡面,如果下一個使用者也使用到這個記憶體裡面可能還有上一個殘存的值。