2023q1 Homework6 (quiz5)

測驗一

程式碼原理

Basic data structure

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

block 為每塊可使用區塊的 metadata ，其中紀錄每個區塊的大小及前一個與後一個區塊的 link。

pool_init

首先會檢查要配置的記憶體位址是否合法，再去檢查大小是否能至少容納一個區塊所需的 metadata 大小，一個 block 包含 size, *prev, *next ，所以至少要 3 個 word 大小，所以 header_size 為 word_size * 3，current 去紀錄此可用區塊的位址。

round_up

static inline int round_up(const int *x)
{
    return ((*x + 7) >> log2_word_size) << log2_word_size;
}

round_up 是為了使宣告的大小能對齊記憶體，因為 x 至少為 1 ，所以當 word_size == 8 時，因為要對齊 8 bytes，所以最右邊 3 bits 要清除為 0 ，所以要 *x + 7，接著右移 3 bits 後，再左移 3 bits ，就能對齊 8 bytes。但這裡適用於 word_size == 8 時，所以當word_size == 4 ，並不適用，所以改成：

static inline int round_up(const int *x)
{
    return ((*x + word_size - 1) >> log2_word_size) << log2_word_size;
}

則當word_size == 4 or 8 時，都能對齊。

pool_malloc

用 pool_malloc 來配置在 memory pool 中的可用區塊，先檢查要配置的記憶體大小是否 > 0，再將要配置的大小對齊 word_size ，最後檢查 pool_free_space 須配置的大小是否足夠，然後用 ret 去紀錄要使用的區塊，由 get_loc_to_place 去尋找可使用的區塊。

void *ret = get_loc_to_place(current, _size);

因為採用 first-fit ，所以當有足夠大小的區塊時就直接配置，否則就往下尋找。這裡有個問題是 get_loc_to_place 傳入的參數名稱與全域變數 current 是一樣的，會導致自己判斷時可能會錯誤。

static inline void *get_loc_to_place(void *current, int size)
{
    block_t *parse = current;
    if (parse->size >= (size + header_size))
        return current;
    ...
}

因為將 memory pool 的區塊配置，所以更新 free space 的值，先更新 current 的位址，再更新 current->size 的值，為目前 free space 大小 - 以配置的空間大小 - 配置出去的區塊的 metadata 大小(size)。

/* 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;

最後將 free block 的 prev, next 的 link 接上。

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

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

pool_free

首先求出要釋放的 block 的位址，並將它的大小更新到 free space 中。

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

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

用 get_loc_to_free 去找到可以連接的 free block。

void *free_pt = get_loc_to_free(block_pt);

再來會檢查 released block 的位址是否跟 free block 相鄰，會有兩種情況，一是 free block 在 released block 前，二是 free block 在 released block 後，再進行合併。

/* 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; 
        ...
    }
    ...
}

最後合併完的 free block 可能也會跟其他 free block 相鄰，所以需要再次合併，分成兩種情況，分別是存在相鄰的 free block 在前或在後。

/* 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;
    }
}
...

答案

• AAAA = header_size
• BBBB = log2_word_size
• CCCC = log2_word_size
• DDDD = header_size
• EEEE = _size
• FFFF = word_size
• GGGG = word_size
• HHHH = word_size

---

測驗二

alloc.c 程式碼原理

split_block

主要將 node 從 freed list 移出，並用 new 去更新大小跟節點關係，最後更新 rb_tree 的資訊。

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

fusion

這裡主要是做將兩塊 free block 合併，首先將兩塊空間大小加總，再將 freed list 的 link 連接，若是合併後的空間為最後一塊，則會去更新最後一個節點的資訊 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; //JJJJ
    return first;
}

malloc

因為考慮到多執行序的問題，所以在配置 block 時，使用 mutex lock，防止可能重複配置空間的問題，首先檢查要配置的大小是否不足 4 bytes，再將 size 加上所需的 metadata 大小，最後去 freed list 尋找合適的空間，若有找到，則回傳位址，若無，則回傳 NULL 。

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;
    if (!g_info.page_size)
        g_info.page_size = getpagesize();
    if ((tmp = search_freed_block(g_info.root_rbtree, size)))
        ptr = split_block(tmp, size);
    else
        ptr = get_heap(size);
    pthread_mutex_unlock(&g_info.mutex);
    return ptr ? (GET_PAYLOAD(ptr)) : NULL;
}

free

首先判斷要釋放的指標是否合法，再去判斷是否為 double free ，最後將這塊空間加入到 freed list 中。

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);
    if (!node->next)
        change_break(node);
    else
        g_info.root_rbtree = insert_in_freed_list(g_info.root_rbtree, node);
    pthread_mutex_unlock(&g_info.mutex);
}

答案

• IIII = node->size - size
• JJJJ = g_info.last_node = first
• KKKK = pthread_mutex_lock(&g_info.mutex);
• LLLL = pthread_mutex_unlock(&g_info.mutex);