contributed by < willwillhi1
>
逐行解釋程式碼之前,應先探討在記憶體配置器中,使用紅黑樹來處理 free list 的考慮因素。
:notes: jserv
先從最基本的 allocator
講起,可以分為:
explicit allocator
: 會要求使用者自行釋放記憶體,例如: C 語言的 malloc
和 free
。implicit allocator
: 又可以稱為 garbage collector
,allocator
會自行檢查哪個記憶體空間不再使用然後釋放那個空間。接下來列出一個 allocator
的要求和目標:
free
前要有對應的 malloc
。allocator
要馬上回應每個呼叫。heap
的空間。接下來是 allocator
在實作時要考慮到的要素:
free block
。free block
來放置新分配的 block
。free block
配置後,如何處理剩餘(多出來)的空間。block
。最基本的 allocator
的實作是 Implicit Free Lists
。
每個 block
都會有 header
來表示 payload
大小以及現在這格區塊的狀態(free
或 allocted
),要注意的是如果位址是對齊 8 bytes
也就是末三位是 0
,那就可以用最後一位來表示 free
or allocated
,與紅黑樹的親代節點同一個概念。
payload
表示資料實際會儲存的地方。
padding
是可能有或沒有的,用來處理 external fragmentation
或滿足 alignment requirement
。
Implicit Free Lists
的優點就是實作簡單,但是缺點就是任何的操作(例如: free list
的搜尋, block
的合併等)基本上都是 ,N
代表所有的 free & allocated blocks
總數。
Explicit Free Lists
Explicit Free Lists
可以說是 Implicit Free Lists
的優化,從原本的 singly linked list
變為 doubly linked list
。
結構變為當 block
是 free
時會有 pred
和 succ
分別指向前、後 block
。
藉由 doubly linked list
只存 free block
的機制,就可以把尋找的時間複雜度由 O(alloated
和 free block
的總數) 降到 O(free block
的總數)。
Segregated Free Lists
多個不同大小的 Free Lists
組合再一起就是 Segregated Free Lists
。
比如根據 2 的冪來分可以分為:
每個大小 (size class
) 就是一個 free List
,然後按照順序排列。
這個實作可以分為兩個模式:
Simple Segregated Storage
簡單來說就是不分割、不合併,每個 blokc
的大小就是 size class
中最大元素的大小,例如: size class
為 17~32 的 block
的大小都會固定是 32。
而且因為不分割也不合併,所以分配和釋放都可以在常數時間內完成,也就是從 free list
的 head
開始刪除和插入,因此 free list
可以是單向鏈結串列,從而節省記憶體的開銷。
但是不分割也不合併也造成了一個明顯的缺點,那就是 internal and external fragmentation
。
Segregated Fits
與 Simple Segregated Storage
最大的不同在於每當找到了合適的 free list
後會依情況來切割這個 block
藉此避免 internal fragmentation
,那如果沒有找到合適的 block
,就從 heap
拿。
另外在釋放一個 block
的時候會與前後的 free block
合併。
在這次的測驗題中可以發現是使用紅黑樹來實作 free list
並且是 Segregated Fits
的模式。這種實作方法不僅可以將搜尋的時間複雜度控制在 內 (N 代表 free block
數),而且對這個紅黑樹執行 first fit
也相當於整個 heap
的 best fit
。
先定義紅黑樹節點顏色,黑色是 0
, 紅色是 1
結構體 metadata_t
放在每塊記憶體的前面,size
用來表示 metameta_t
加上其管理的 memory block
大小,free
表示這塊記憶體是否已經被分配,next
, prev
則分別連接到下、上一塊 metameta_t
。
接下來定義紅黑樹節點:
size
: 節點大小free
: 表示節點是否被釋放(用 YFREE
, NFREE
表示)next
, prev
: 用於連接相鄰節點的 metadata_t
? (程式中都沒用到,初始化為 NULL
)key
: 表示該節點所存放的每個記憶體 (metadata_t
+ memory block
) 的大小tab_values
: 指向 metadata_t
結構體的指標陣列size_tab
: tab_values
陣列長度n_active
: 可用的記憶體區塊的數量最後是 malloc_t
結構體:
root_rbtree
: 表示整棵樹的 root
last_node
: 代表最後一個 metadata_t
指標end_in_page
: 所有使用到的記憶體的尾端位址(不包含 page_remaining
的記憶體)first_block
: 所有請求記憶體的起始位置page_size
: page_size
大小mutex
: 用於多執行緒環境的鎖page_remaining
: 表示沒有被使用但也沒有被納入紅黑樹的空間,該空間保留給 get_heap
函式使用,放在所有記憶體的最尾端。先解釋 malloc
的運作:
考慮到多執行緒環境,所以在進行操作前後要上鎖、解鎖。
然後判斷請求的空間大小是否小於 SIZE_DEFAULT_BLOCK
,是則把它改為 SIZE_DEFAULT_BLOCK
。
然後把它對齊 16 B
(64 位元系統) 後再加上 metadata_t
結構體的大小。
接著如果 g_info.page_size
還沒有值,就 assign 為 page size
。
最後從紅黑樹找出最適合的記憶體區塊,如果沒有就直接從 heap
拿。
search_freed_block
會先通過 find_best
函式從紅黑樹找出大小最合適的點,也就是 best fit
策略。
如果有找到 (tmp
不為 NULL
) 就回傳該點所管理的 metadata_t
陣列中可以使用的 metadata_t
(也就是不為 NULL
)。
反之沒找到則回傳 NULL
。
回到 malloc
的程式中,
如果有找到就會執行 split_block
。
split_block
會通過 remove_from_freed_list
把指定的 metadata_t
從紅黑樹中移除。
這邊 remove_from_freed_list
傳入的第一個參數是 root
,
不過去看 remove_from_freed_list
發現用 get_key
來找到紅黑樹節點,等同多走訪一次樹,所以我感覺應該可以傳入之前透過 search_freed_block
找到的節點位址來節省時間。
remove_from_freed_list
找到節點後會把 n_active
減一,然後如果 n_active
等於零就通過 remove_k
函式把該節點從紅黑樹中移除。
回到 split_block
中,移除完後
會先做兩個判斷,但是還不是很懂會何為甚麼要這樣判斷?
node->size > size + sizeof(size_t)
node->size - size > sizeof(rbnode_t) + SIZE_DEFAULT_BLOCK
node
做分割然後把新的點 new
插入樹中。回到 malloc
,如果 search_freed_block
找不到適合的記憶體就要用 get_heap
從 heap
拿。
get_heap
會先判斷目前的 remain page
夠不夠,如果不夠會透過 get_new_page
從 heap
取記憶體。
接下來 get_new_page
會先把請求的記憶體大小 size
轉為以 g_info.page_size
為單位。
get_new_page
如果是第一次就會用 sbrk(0)
(previous program break) 初始化 g_info.first_block
和 g_info.end_in_page
。
然後將 program break
往後移 pages
個 bytes
。
最後 get_in_page
會回傳 pages
給 get_heap
中的 tmp
。
回到 get_heap
,執行完 get_new_page
後會把取得的空間的大小加到 g_info.page_remaining
中,然後再扣掉原本要分配出去的空間大小。
get_heap
會回傳 get_in_page(size)
,
get_in_page
會初始化這塊記憶體的 metadata_t
,並更新 g_info.last_node
和 g_info.end_in_page
。
最後終於回到 malloc
的最後
把鎖解開後回傳取得的 memory block
的起始位置。
接下來是 free
的部分
首先要做的就是上鎖,然後取得該 memory block
的 metadata_t
位址。
之後判斷完 invalid_pointer
和 double_free
後會做 try_fusion
。
try_fusion
會去檢查該 metadata_t
前後的節點狀態是否為 free
,如果是則會先用 remove_from_freed_list
把該 metadata_t
的前或後從紅黑樹移除,接著再用 fusion
把第二個空間合併到第一個記憶體的 metadata_t
中。
回到 free
,合併完接下來會有兩個情況,第一個情況是如果這個釋放的節點是在最尾端就直接用 change_break
把 program break
往前(回)移,要移動的空間大小為 g_info.page_remaining += node->size
,另外再移動前要先用除法無條件捨去取 page count
,避免以 page
為單位釋放記憶體時釋放到正在使用的空間。
最後更新 page_remaining
即可。
回到 free
,合併完接下來的第二個情況就是釋放的節點不在最尾端,那就直接插入紅黑樹即可。