2023q1 Homework6 (quiz5)

contributed by < terry23304 >

測驗 1

根據電腦結構設定 word_size ，header_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->prev 、 current->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->prev 跟 current ，應為 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;
}

把 node 從 freed_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;
}

合併 first 、 second

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

2023q1 Homework6 (quiz5)

測驗 1

測驗 2

Read more

Linux Kernel Development

RV32 port for MIT xv6 operating system (and contribute!)

Assignment 3: single-cycle RISC-V CPU

Computer Architecture HW2