Try   HackMD

2023q1 Homework6 (quiz5)

contributed by < ItisCaleb >

測驗 1

題目的 memory pool 可以運用的空間是使用者自行先分配出來,再使用 pool_init 並傳入 size 來讓程式可以運用
在 memory pool 中,可以使用的空間會有個 header,用來紀錄上/下一個可以使用的空間及大小

typedef struct block {
    int size;                  /**< Size of the data payload */
    struct block *prev, *next; /**< Pointer to the previous/next block */
} block_t;

而使用中的空間則只會有一個 size 來紀錄 payload 的大小。







%0



Free Block
Free Block



In-use Block
In-use Block



Free Block->In-use Block





block1

size

next

prev

...



block2

size

payload



全域變數的 current 指向一個可以使用的空間

pool_malloc

會先把要的 size 變成 4/8 byte的倍數,如果 memory pool 剩下的空間塞不下 _size 跟 header 就直接回傳

void *pool_malloc(int size)
{
    if (!size)
        return NULL;

    /* Round up the size up to the arch width. Ensure the size is at minimum a
     * register size and a multiple of that register. So if use 64 bits arch, a
     * 4 bytes allocation is round up to 8 bytes, and 28 bytes is round up to
     * 32 bytes.
     */
    int _size = round_up(&size);

    /* Return NULL if failed to allocate a buffer */
    if (pool_free_space <= (_size + header_size))
        return NULL;

接下來則是用 get_loc_to_place 並使用 current 去尋找符合 _size 的空間

ret 應該設為 ret + word_size 而非 current + word_size,同時應該放到最後,這樣才方便去更新他的 size

    void *ret = get_loc_to_place(current, _size); 

    if (!ret)
        return NULL;

    /* payload's address the application can use */
    //ret = (char *) ret + word_size;

get_loc_to_place 的行為很簡單
就只是透過 current 去往前或往後搜尋大於等於 size 的 free block

第二段的 parse = ((block_t *) current)->prev; 應改成 parse = ((block_t *) current)->next;

/* Search for a free space to place a new block */
static inline void *get_loc_to_place(void *current, int size)
{
    block_t *parse = current;
    if (parse->size >= (size + header_size))
        return current;

    /* parse the prev blocks to find a place */
    for (parse = ((block_t *) current)->prev; parse; parse = parse->prev) {
        if (parse->size >= (size + header_size))
            return parse;
    }

    /* parse the next blocks to find a place */
    for (parse = ((block_t *) current)->next; parse; parse = parse->next) {
        if (parse->size >= (size + header_size))
            return parse;
    }

    /* No space found, stop the allocation */
    return NULL;
}

最後則是更新 current ,把原本的 prevnext 接上去

/* Store current's info before moving its head */
    void *next_pt = current->next, *prev_pt = current->prev;
    int new_size = current->size - word_size - _size;

    /* Adjust free space of current block and update its meta-data */
    void *new_space = (char *) current + word_size + _size;
    current = new_space;

    if (new_size < 0) {
        current->size = 0;
        return NULL;
    }
    current->size = new_size;

    current->prev = prev_pt, current->next = next_pt;

如果 currentprevnext 不為 NULL
則也同樣把他們接上 current

    /* Update previous block to link current */
    if (current->prev) {
        tmp_block = prev_pt;
        tmp_block->next = current;
    }
    /* Update next block to link current, only if exists */
    if (current->next) {
        tmp_block = next_pt;
        tmp_block->prev = current;
    }

在回傳 ret 之前,應該要先更新 pool_free_space 以及他本身的 size

    pool_free_space -= _size;
    /* payload's address the application can use */
    ((block_t *) ret)->size = _size;
    return (char *) ret + word_size;;

pool_free

在 free 之前會先獲取 block 的 size 然後加到 pool_free_space

void pool_free(void *addr)
{
    /* Get block info */
    void *block_pt = (char *) addr - word_size; //HHHH
    block_t *block = block_pt;

    /* Update pool arena statistics */
    pool_free_space += block->size;

接著是用 get_loc_to_free 來找到最近的 free block
為了等下可以 merge

    void *free_pt = get_loc_to_free(block_pt);
    block_t *free_block = (block_t *) free_pt;

在 merge 的時候會有兩種情況
分別是 free block 在要釋放的 block 前面及後面







%0



block1

free block

block









%0



block1

block

free block



在檢查 free block 是否跟要釋放的 block 相鄰後
如果是後者的情況則要將 free block 的 header 移到要釋放的 block 前面,並且更新 size 及連結的區塊
前者的情況則只要更新 free block 的 size 就好

/* Check the block can be merged with the current free space selected */
    if ((uintptr_t) block_pt < (uintptr_t) free_pt) {
        /* If block space matches free space start address, merge */
        region = (char *) block_pt + block->size + word_size;
        if (region == free_pt) {
            block->prev = free_block->prev, block->next = free_block->next;
            block->size += free_block->size + header_size;
            pool_free_space += word_size;
            /* If a next block exists, connect it */
            if (block->next) {
                tmp_block = block->next;
                tmp_block->prev = block_pt;
            }
            /* If a previsou block exists, connect it */
            if (block->prev) {
                tmp_block = block->prev;
                tmp_block->next = block_pt;
            }
        }
    } else {
        /* if free space range macthes the block start address, merge in this
         * case, the free space becomes the block to release
         */
        region = (char *) free_pt + free_block->size + header_size;
        if (region == block_pt) {
            free_block->size += block->size + word_size;
            block_pt = free_pt;
            block = block_pt;
            pool_free_space += word_size;
        }
    }

最後如果 merge 之後前方或後方還有 free block 則再一次去做 merge

/* Try to merge with next block if exists */
    if (block->next) {
        /* if next block is contiguous the one to free, merge them */
        region = (char *) block_pt + block->size + word_size;
        if (region == block->next) {
            /* extend block size with next size */
            tmp_block = block->next;
            block->size += tmp_block->size + word_size;
            /* link next->next block with current block */
            tmp_block = tmp_block->next;
            tmp_block->prev = block_pt;
            /* Update pool's statistics */
            pool_free_space += word_size;
        }
    }

    /* Try to merge with previous block if exists */
    if (block->prev) {
        /* if previous block is contiguous the one to free, merge them */
        tmp_block = block->prev;
        region = (char *) block->prev + tmp_block->size + header_size;
        if (region == block_pt) {
            /* Update previous block by extending its size with block */
            tmp_block->size += word_size + block->size;
            /* Link block - 1 and block + 1 together */
            tmp_block->next = block->next;
            /* Current block's prev becomes the new current block */
            block = block->prev;
            /* (block + 1)'s prev is now linked to orignal (block - 1) */
            tmp_block = block->next;
            tmp_block->prev = block;
            /* Update pool's statistics */
            pool_free_space += word_size;
        }
    }

整體的行為會像是下面這樣子







%0



block

free block

block

free block









%0



block

free block

free block









%0



block

free block




測驗 2

這個測驗裡的記憶體配置是搭配紅黑樹來實作的
演算法大致上的概念是在把空間 free 之後,不會直接將空間還給 kernel,而是會作為節點放到紅黑樹裡,待之後可以直接取用
這邊的紅黑樹是用 size 來當作 key ,同時如果有多個區塊是同一個 size 的話,則都會放入節點的 tab_values

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;

在 metadata 中除了 size 還會記載著 nextprev,也就是相鄰的區塊
是為了之後在 free 的時候看能不能去合併

typedef struct metadata {
    size_t size;
    size_t free;
    struct metadata *next, *prev;
} metadata_t;

而為了可以在多執行緒的狀況下執行,在每個操作裡都會有 mutex_lockmutex_unlock

malloc

一開始會先將要的 size 做記憶體對齊並且加上 metadata 的大小

void *malloc(size_t size)
{
    metadata_t *tmp;
    void *ptr;

    pthread_mutex_lock(&g_info.mutex);
    if (size < SIZE_DEFAULT_BLOCK)
        size = SIZE_DEFAULT_BLOCK;
    size = ALIGN_BYTES(size) + META_SIZE;

接著就是先去紅黑樹裡找到符合 size 的記憶體區塊
如果找到了還會透過 split_block 去分割區塊,然後把多餘的區塊重新插入到紅黑樹中
這樣子做就一定會保證是 best-fit

而如果沒有符合 size 的區塊,則透過 get_heap 來獲得更多記憶體空間

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

最後回傳 payload 的地址

    return ptr ? (GET_PAYLOAD(ptr)) : NULL;

split_block 會將找到的區塊分割成 size 的大小
並且將這兩個區塊連結在一起
然後把分割完剩下來的區塊放回紅黑樹裡

static void *split_block(metadata_t *node, size_t size)
{
    g_info.root_rbtree = remove_from_freed_list(g_info.root_rbtree, node);
    if (node->size > size + sizeof(size_t) &&
        node->size - size > sizeof(rbnode_t) + SIZE_DEFAULT_BLOCK) {
        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);
    }
    return node;
}

free

首先會先通過檢查位置及 magic number 來確認 ptr 是不是有效的記憶體位址
並且也會檢查是否 free 多次同一個位址

void free(void *ptr)
{
    if (!ptr)
        return;

    pthread_mutex_lock(&g_info.mutex);
    metadata_t *node = GET_NODE(ptr);
    if (ptr < g_info.first_block || ptr > g_info.end_in_page || !IS_VALID(node))
        invalid_pointer(ptr);
    if (node->free == YFREE)
        double_free(ptr);

如果都沒問題則會嘗試會合併記憶體區塊

    node = try_fusion(node);

try_fusion 會利用 metadata 的 nextprev 來讓相鄰的區塊合併
如果在合併之後 nextNULL 則表示現在的區塊是最後的區塊,把 g_info.last_node 設為現在的區塊

static metadata_t *fusion(metadata_t *first, metadata_t *second)
{
    first->size += second->size;
    first->next = second->next;
    if (first->next)
        first->next->prev = first;
    else
        g_info.last_node = first;
    return first;
}

static inline metadata_t *try_fusion(metadata_t *node)
{
    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);
    }
    return node;
}

當合併完之後會判斷現在的區塊是否是最後的區塊
如果是的話就使用 change_break 來把區塊還回 kernel
否則就插入到紅黑樹裡來讓之後的 malloc 操作可以利用

if (!node->next)
        change_break(node);
    else
        g_info.root_rbtree = insert_in_freed_list(g_info.root_rbtree, node);

change_break 會利用 sbrk 把剩下的區塊還回 kernel

static inline void change_break(metadata_t *node)
{
    size_t pages_to_remove;

    if (node->prev) {
        node->prev->next = NULL;
        g_info.last_node = node->prev;
        g_info.end_in_page = (void *) g_info.last_node + g_info.last_node->size;
    } else {
        g_info.end_in_page = g_info.last_node;
        g_info.last_node = NULL;
    }
    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)));
    g_info.page_remaining =
        g_info.page_remaining - (pages_to_remove * g_info.page_size);
}