contributed by < ItisCaleb
>
1
題目的 memory pool 可以運用的空間是使用者自行先分配出來,再使用 pool_init
並傳入 size
來讓程式可以運用
在 memory pool 中,可以使用的空間會有個 header,用來紀錄上/下一個可以使用的空間及大小
而使用中的空間則只會有一個 size
來紀錄 payload
的大小。
全域變數的 current
指向一個可以使用的空間
會先把要的 size
變成 4/8 byte的倍數,如果 memory pool 剩下的空間塞不下 _size
跟 header 就直接回傳
接下來則是用 get_loc_to_place
並使用 current
去尋找符合 _size
的空間
ret
應該設為ret + word_size
而非current + word_size
,同時應該放到最後,這樣才方便去更新他的size
get_loc_to_place
的行為很簡單
就只是透過 current
去往前或往後搜尋大於等於 size
的 free block
第二段的
parse = ((block_t *) current)->prev;
應改成parse = ((block_t *) current)->next;
最後則是更新 current
,把原本的 prev
跟 next
接上去
如果 current
的 prev
跟 next
不為 NULL
則也同樣把他們接上 current
在回傳 ret
之前,應該要先更新 pool_free_space
以及他本身的 size
在 free 之前會先獲取 block 的 size 然後加到 pool_free_space
裡
接著是用 get_loc_to_free
來找到最近的 free block
為了等下可以 merge
在 merge 的時候會有兩種情況
分別是 free block 在要釋放的 block 前面及後面
在檢查 free block 是否跟要釋放的 block 相鄰後
如果是後者的情況則要將 free block 的 header 移到要釋放的 block 前面,並且更新 size
及連結的區塊
前者的情況則只要更新 free block 的 size
就好
最後如果 merge 之後前方或後方還有 free block 則再一次去做 merge
整體的行為會像是下面這樣子
2
這個測驗裡的記憶體配置是搭配紅黑樹來實作的
演算法大致上的概念是在把空間 free 之後,不會直接將空間還給 kernel,而是會作為節點放到紅黑樹裡,待之後可以直接取用
這邊的紅黑樹是用 size 來當作 key ,同時如果有多個區塊是同一個 size 的話,則都會放入節點的 tab_values
裡
在 metadata 中除了 size
還會記載著 next
跟 prev
,也就是相鄰的區塊
是為了之後在 free 的時候看能不能去合併
而為了可以在多執行緒的狀況下執行,在每個操作裡都會有 mutex_lock
及 mutex_unlock
一開始會先將要的 size
做記憶體對齊並且加上 metadata 的大小
接著就是先去紅黑樹裡找到符合 size
的記憶體區塊
如果找到了還會透過 split_block
去分割區塊,然後把多餘的區塊重新插入到紅黑樹中
這樣子做就一定會保證是 best-fit
而如果沒有符合 size
的區塊,則透過 get_heap
來獲得更多記憶體空間
最後回傳 payload 的地址
split_block
會將找到的區塊分割成 size
的大小
並且將這兩個區塊連結在一起
然後把分割完剩下來的區塊放回紅黑樹裡
首先會先通過檢查位置及 magic number 來確認 ptr
是不是有效的記憶體位址
並且也會檢查是否 free 多次同一個位址
如果都沒問題則會嘗試會合併記憶體區塊
try_fusion
會利用 metadata 的 next
跟 prev
來讓相鄰的區塊合併
如果在合併之後 next
為 NULL
則表示現在的區塊是最後的區塊,把 g_info.last_node
設為現在的區塊
當合併完之後會判斷現在的區塊是否是最後的區塊
如果是的話就使用 change_break
來把區塊還回 kernel
否則就插入到紅黑樹裡來讓之後的 malloc
操作可以利用
change_break
會利用 sbrk
把剩下的區塊還回 kernel