Try   HackMD

2023q1 Homework6 (quiz5)

contributed by < terry23304 >

測驗 1

根據電腦結構設定 word_sizeheader_size = sizeof(block_t) 更好理解

/* Size of a memory element, 32 or 64 bits */
enum {
    word_size = __SIZE_WIDTH__ / 8, /**< size of memory element */
#if __SIZE_WIDTH__ == 64
    log2_word_size = 3,
#else
    log2_word_size = 2,
#endif
    // header_size = 3 * word_size, /**< size, previous/next block addresses */
    header_size = sizeof(block_t), /**< size, previous/next block addresses */
};
  • pool_init
    檢查傳入的 address 是否合法與大小是否大於 block_t 的大小,若通過則用 current->size 紀錄可用空間, current->size 要減去儲存 size 的大小, current->prevcurrent->next 因為是指向 NULL 所以不占空間。

    ​​​​pool_free_space = size - word_size;
    
    ​​​​current = (block_t *) addr;
    ​​​​current->size = pool_free_space;
    ​​​​current->prev = NULL, current->next = NULL;
    
  • round_up
    確保空間為 word_size 的倍數,原本的寫法在 32 位元時不成立

    ​​​​static inline int round_up(const int *x)
    ​​​​{
    ​​​​    // return ((*x + 7) >> log2_word_size) << log2_word_size;
    ​​​​    return ((*x + (word_size - 1)) >> log2_word_size) << log2_word_size;
    ​​​​}
    
  • get_loc_to_place
    找到可以配置的空間
    先確認 current size 夠不夠大,因為是 first-fit,找到就直接 retrun

    ​​​​static inline void *get_loc_to_place(void *current, int size)
    ​​​​{
    ​​​​    /* Search for a free space to place a new block */
    ​​​​    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 = ((block_t *) current)->prev , 會重複檢查 current->prevcurrent ,應為 parse = ((block_t *) current)->next

    ​​​​// for (parse = ((block_t *) current)->prev; parse; parse = parse->next) {
    ​​​​for (parse = ((block_t *) current)->next; parse; parse = parse->next) {
    ​​​​    if (parse->size >= (size + header_size))
    ​​​​        return parse;
    ​​​​}
    
    ​​​​return NULL;
    ​​​​}
    
  • pool_malloc
    先把大小補到 word_size 的倍數後,找到可配置的空間,但得到可配置空間後卻使用 current 來配置

    ​​​​int _size = round_up(&size);
    
    ​​​​/* Return NULL if failed to allocate a buffer */
    ​​​​if (pool_free_space <= (_size + header_size))
    ​​​​    return NULL;
    
    ​​​​void *ret = get_loc_to_place(current, _size);
    
    ​​​​if (!ret)
    ​​​​    return NULL;
    
    ​​​​/* payload's address the application can use */
    ​​​​ret = (char *) current + word_size;
    ​​​​void *next_pt = current->next, *prev_pt = current->prev;
    ​​​​int new_size = current->size - word_size - _size;
    
  • pool_free
    呼叫 get_loc_to_free 得到 free space,並檢查 block 能不能跟 free space 合併,再嘗試與前後的 block 合併

    ​​​​/* Get block info */
    ​​​​void *block_pt = (char *) addr - word_size;
    ​​​​block_t *block = block_pt;
    
    ​​​​/* Update pool arena statistics */
    ​​​​pool_free_space += block->size;
    
    ​​​​void *region;
    
    ​​​​void *free_pt = get_loc_to_free(block_pt);
    ​​​​block_t *free_block = (block_t *) free_pt;
    

修改 first-fit 成 best-fit

static inline void *get_loc_to_place(void *current, int size) {
    block_t *parse = current;
    block_t *best_fit = NULL;

    if (parse->size >= (size + header_size))
        best_fit = parse;

    for (parse = ((block_t *)current)->prev; parse; parse = parse->prev) {
        if (parse->size >= (size + header_size) &&
            (best_fit == NULL || parse->size < best_fit->size)) {
            best_fit = parse;
        }
    }

    for (parse = ((block_t *)current)->next; parse; parse = parse->next) {
        if (parse->size >= (size + header_size) &&
            (best_fit == NULL || parse->size < best_fit->size)) {
            best_fit = parse;
        }
    }

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

測驗 2

rbnode 儲存各個 block 的資訊

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;

TODO: 討論使用紅黑樹實作 free list 的好處和考量因素

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 →
jserv

走訪紅黑樹找到最接近且大於 size 的 node

static inline rbnode_t *find_best(rbnode_t *node, size_t size)
{
    rbnode_t *tmp = NULL;
    while (node) {
        if (node->key >= size) {
            tmp = node;
            node = node->left;
        } else
            node = node->right;
    }
    return tmp;
}

nodefreed_list 中刪除後,用 new 更新剩餘空間的大小,再插入 freed list

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;
}

合併 firstsecond

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;
} 

free 時檢查前後是否為 freed 狀態,若則合併兩個 node

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;
}

避免多個 thread 同時存取 memory block

void *realloc(void *ptr, size_t size)
{
    if (!ptr)
        return malloc(size);
    if (!size)
        return free_realloc(ptr);

    ptr = (void *) ptr - META_SIZE;
    metadata_t *tmp = (metadata_t *) ptr;
    metadata_t *new = ptr;
    if (size + META_SIZE > tmp->size) {
        if (!(new = malloc(size)))
            return NULL;

        size = ALIGN_BYTES(size);
        pthread_mutex_lock(&g_info.mutex);
        memcpy(new, (void *) ptr + META_SIZE,
               (size <= tmp->size) ? (size) : (tmp->size));
        pthread_mutex_unlock(&g_info.mutex);
        free((void *) ptr + META_SIZE);
    } else
        new = GET_PAYLOAD(new);
    return new;
}