Try   HackMD

2023q1 Homework6 (quiz5)

contributed by < willwillhi1 >

測驗二

逐行解釋程式碼之前,應先探討在記憶體配置器中,使用紅黑樹來處理 free list 的考慮因素。
:notes: jserv

free list 的理解

先從最基本的 allocator 講起,可以分為:

  • explicit allocator: 會要求使用者自行釋放記憶體,例如: C 語言的 mallocfree
  • implicit allocator: 又可以稱為 garbage collectorallocator 會自行檢查哪個記憶體空間不再使用然後釋放那個空間。

接下來列出一個 allocator 的要求和目標:

  • Handling arbitrary request sequences: 可以處理任意序列的分配請求和釋放,不過前提是每一個釋放都必須要先有配置請求,ex: free 前要有對應的 malloc
  • Making immediate responses to requests: allocator 要馬上回應每個呼叫。
  • Using only the heap: 只能使用 heap 的空間。
  • Aligning blocks (alignment requirement): 記憶體位址需要對齊,讓該空間可以保存任何資料型態。
  • Not modifying allocated blocks: 不得修改已分配的記憶體區塊。

接下來是 allocator 在實作時要考慮到的要素:

  • Free block organization: 如何管理 free block
  • Placement: 如何選擇合適的 free block 來放置新分配的 block
  • Splitting: 在 free block 配置後,如何處理剩餘(多出來)的空間。
  • Coalescing: 如何處理一個剛被釋放的 block

最基本的 allocator 的實作是 Implicit Free Lists
每個 block 都會有 header 來表示 payload 大小以及現在這格區塊的狀態(freeallocted),要注意的是如果位址是對齊 8 bytes 也就是末三位是 0,那就可以用最後一位來表示 free or allocated,與紅黑樹的親代節點同一個概念。
payload 表示資料實際會儲存的地方。
padding 是可能有或沒有的,用來處理 external fragmentation 或滿足 alignment requirement

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Implicit Free Lists 的優點就是實作簡單,但是缺點就是任何的操作(例如: free list 的搜尋, block 的合併等)基本上都是
O(N)
N 代表所有的 free & allocated blocks 總數。

Explicit Free Lists
Explicit Free Lists 可以說是 Implicit Free Lists 的優化,從原本的 singly linked list 變為 doubly linked list
結構變為當 blockfree 時會有 predsucc 分別指向前、後 block

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

藉由 doubly linked list 只存 free block 的機制,就可以把尋找的時間複雜度由 O(alloatedfree block 的總數) 降到 O(free block 的總數)。

Segregated Free Lists
多個不同大小的 Free Lists 組合再一起就是 Segregated Free Lists
比如根據 2 的冪來分可以分為:

{1}, {2}, {3, 4}, {5–8}, ... , {1,025–2,048}, {2,049–4,096}, {4,097–∞}

每個大小 (size class) 就是一個 free List,然後按照順序排列。
這個實作可以分為兩個模式:
Simple Segregated Storage
簡單來說就是不分割、不合併,每個 blokc 的大小就是 size class 中最大元素的大小,例如: size class 為 17~32 的 block 的大小都會固定是 32。
而且因為不分割也不合併,所以分配和釋放都可以在常數時間內完成,也就是從 free listhead 開始刪除和插入,因此 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 的模式。這種實作方法不僅可以將搜尋的時間複雜度控制在

O(logN) 內 (N 代表 free block 數),而且對這個紅黑樹執行 first fit 也相當於整個 heapbest fit

程式理解

先定義紅黑樹節點顏色,黑色是 0, 紅色是 1

typedef enum rbcolor { BLACK = 0, RED = 1 } rbcolor_t;

結構體 metadata_t 放在每塊記憶體的前面,size 用來表示 metameta_t 加上其管理的 memory block 大小,free 表示這塊記憶體是否已經被分配,next, prev 則分別連接到下、上一塊 metameta_t

typedef struct metadata {
    size_t size;
    size_t free;
    struct metadata *next, *prev;
} metadata_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: 可用的記憶體區塊的數量
typedef size_t t_key;
typedef metadata_t t_value;

typedef struct rbnode {
    size_t size;
    size_t free;
    metadata_t *next, *prev;
    t_key key;
    t_value **tab_values;
    size_t size_tab;
    size_t n_active;
    rbcolor_t color;
    struct rbnode *left, *right;
} rbnode_t;

最後是 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 函式使用,放在所有記憶體的最尾端。
typedef struct {
    rbnode_t *root_rbtree;
    metadata_t *last_node;
    void *end_in_page;
    void *first_block;
    int page_size;
    pthread_mutex_t mutex;
    size_t page_remaining;
} malloc_t;

先解釋 malloc 的運作:
考慮到多執行緒環境,所以在進行操作前後要上鎖、解鎖。

pthread_mutex_lock(&g_info.mutex);
/* operation */
pthread_mutex_unlock(&g_info.mutex);

然後判斷請求的空間大小是否小於 SIZE_DEFAULT_BLOCK,是則把它改為 SIZE_DEFAULT_BLOCK

if (size < SIZE_DEFAULT_BLOCK)
    size = SIZE_DEFAULT_BLOCK;

然後把它對齊 16 B (64 位元系統) 後再加上 metadata_t 結構體的大小。

#define ALIGN_BYTES(x) ((((x - 1) >> 4) << 4) + 16)

size = ALIGN_BYTES(size) + META_SIZE;

接著如果 g_info.page_size 還沒有值,就 assign 為 page size

if (!g_info.page_size)
    g_info.page_size = getpagesize();

最後從紅黑樹找出最適合的記憶體區塊,如果沒有就直接從 heap 拿。

metadata_t *tmp;
void *ptr;

if ((tmp = search_freed_block(g_info.root_rbtree, size)))
    ptr = split_block(tmp, size);
else
    ptr = get_heap(size);

search_freed_block 會先通過 find_best 函式從紅黑樹找出大小最合適的點,也就是 best fit 策略。

/* best fit */
while (node) {
    if (node->key >= size) {
        tmp = node;
        node = node->left;
    } else
        node = node->right;
}

如果有找到 (tmp 不為 NULL) 就回傳該點所管理的 metadata_t 陣列中可以使用的 metadata_t (也就是不為 NULL)。
反之沒找到則回傳 NULL

if (tmp) {
    size_t size_tab = tmp->size_tab;
    metadata_t **tab = tmp->tab_values;
    for (size_t i = 0; i < size_tab; i++) {
        if (tab[i])
            return tab[i];
    }
}

回到 malloc 的程式中,
如果有找到就會執行 split_block
split_block 會通過 remove_from_freed_list 把指定的 metadata_t 從紅黑樹中移除。
這邊 remove_from_freed_list 傳入的第一個參數是 root

g_info.root_rbtree = remove_from_freed_list(g_info.root_rbtree, node);

不過去看 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 插入樹中。
metadata_t *new = (void *) node + size;
new->size = node->size - size;
new->free = YFREE;
new->prev = node;
new->next = node->next;
node->next = new;
node->size = size;
if (new->next)
    new->next->prev = new;
g_info.root_rbtree = insert_in_freed_list(g_info.root_rbtree, new);

回到 malloc,如果 search_freed_block 找不到適合的記憶體就要用 get_heapheap 拿。
get_heap 會先判斷目前的 remain page 夠不夠,如果不夠會透過 get_new_pageheap 取記憶體。

if (g_info.page_remaining < size) {
    if ((tmp = get_new_page(size)) == (size_t) -1)
        return NULL;
    g_info.page_remaining += tmp;
}

接下來 get_new_page 會先把請求的記憶體大小 size 轉為以 g_info.page_size 為單位。

size_t pages = ((size / g_info.page_size) + 1) * g_info.page_size;

get_new_page 如果是第一次就會用 sbrk(0) (previous program break) 初始化 g_info.first_blockg_info.end_in_page

if (!g_info.end_in_page) {
    if ((g_info.end_in_page = sbrk(0)) == (void *) -1)
        return (size_t) -1;
    g_info.first_block = g_info.end_in_page;
}

然後將 program break 往後移 pagesbytes

if (sbrk(pages) == (void *) -1) {
    errno = ENOMEM;
    return (size_t) -1;
}

最後 get_in_page 會回傳 pagesget_heap 中的 tmp
回到 get_heap,執行完 get_new_page 後會把取得的空間的大小加到 g_info.page_remaining 中,然後再扣掉原本要分配出去的空間大小。

g_info.page_remaining += tmp;
g_info.page_remaining -= size;

get_heap 會回傳 get_in_page(size)
get_in_page 會初始化這塊記憶體的 metadata_t,並更新 g_info.last_nodeg_info.end_in_page

metadata_t *new = g_info.end_in_page;
new->size = size;
new->free = NFREE;
new->next = NULL;
new->prev = g_info.last_node;
if (g_info.last_node)
    g_info.last_node->next = new;
g_info.last_node = new;
g_info.end_in_page = (void *) new + size;
return new;

最後終於回到 malloc 的最後
把鎖解開後回傳取得的 memory block 的起始位置。

#define GET_PAYLOAD(x) ((void *) ((size_t) x + META_SIZE))

pthread_mutex_unlock(&g_info.mutex);
return ptr ? (GET_PAYLOAD(ptr)) : NULL;

接下來是 free 的部分
首先要做的就是上鎖,然後取得該 memory blockmetadata_t 位址。

#define GET_NODE(x) ((void *) ((size_t) x - META_SIZE))

pthread_mutex_lock(&g_info.mutex);
metadata_t *node = GET_NODE(ptr);

之後判斷完 invalid_pointerdouble_free 後會做 try_fusion
try_fusion 會去檢查該 metadata_t 前後的節點狀態是否為 free,如果是則會先用 remove_from_freed_list 把該 metadata_t 的前或後從紅黑樹移除,接著再用 fusion 把第二個空間合併到第一個記憶體的 metadata_t 中。

while (IS_FREE(node->prev)) {
    g_info.root_rbtree =
        remove_from_freed_list(g_info.root_rbtree, node->prev);
    node = fusion(node->prev, node);
}
while (IS_FREE(node->next)) {
    g_info.root_rbtree =
        remove_from_freed_list(g_info.root_rbtree, node->next);
    node = fusion(node, node->next);
}

回到 free,合併完接下來會有兩個情況,第一個情況是如果這個釋放的節點是在最尾端就直接用 change_breakprogram break 往前(回)移,要移動的空間大小為 g_info.page_remaining += node->size,另外再移動前要先用除法無條件捨去取 page count,避免以 page 為單位釋放記憶體時釋放到正在使用的空間。

g_info.page_remaining += node->size;
pages_to_remove = g_info.page_remaining / g_info.page_size;
/* FIXME: sbrk is deprecated */
brk((sbrk(0) - (pages_to_remove * g_info.page_size)));

最後更新 page_remaining 即可。

g_info.page_remaining =
    g_info.page_remaining - (pages_to_remove * g_info.page_size);

回到 free,合併完接下來的第二個情況就是釋放的節點不在最尾端,那就直接插入紅黑樹即可。

g_info.root_rbtree = insert_in_freed_list(g_info.root_rbtree, node);