Malloc Lab

"In this lab, the task is to step by step implement memory management for heap allocation. In the first part, the checkpoint only requires the implementation of a fast enough malloc. In the second part, the final version aims to reduce internal fragmentation by removing the footer."

First Part

"In the first part, we will implement:

First, we need to understand the significance of some basic constants.

static const size_t wsize = sizeof(word_t);

wsize = 8 bytes, the unit size of data in malloc lab, is the smallest data unit.

static const size_t dsize = 2 * wsize;

dsize = 16 bytes, which is twice the wsize. It can be thought of as a combination of a header and a footer.

static const size_t chunksize = (1 << 12);

chunksize is the size by which the heap memory is extended when the largest remaining free block size is less than the required block size (asize).

static const word_t alloc_mask = 0x1;

alloc_mask is used to identify whether a block is allocated; if allocated, alloc is set to 1, and if free, it is set to 0.

static const word_t size_mask = ~(word_t)0xF;

size_mask is used to get the size of a block.

After understanding these basic constants, we will begin designing two fundamental data structures: block and free block."

typedef struct block {
    /** @brief Header contains size + allocation flag */
    word_t header;
    /**
     * @brief A pointer to the block payload.*
     */
    char payload[0];
} block_t;

A block contains two fields: a header and a payload. The footer is not explicitly marked in the struct; in fact, the footer is the last word_t of the payload. This function helps us understand it more clearly:

static word_t *header_to_footer(block_t *block) {
    dbg_requires(get_size(block) != 0 &&
                 "Called header_to_footer on the epilogue block");
    return (word_t *)(((char *)block->payload) + get_size(block) - dsize);
}

A char is one byte, so by moving the payload address forward by the payload size, then moving it backward by one dsize, you can find the location where the footer is stored.

/** @brief Represents free block to be allocated */
typedef struct free_block {
    /** @brief Header contains size + allocation flag */
    word_t header;
    /** @brief point to the previous block*/
    word_t ptr_prev;
    /** @brief point to the next block*/
    word_t ptr_next;
} free_block_t;

A free_block is structured as a linked list node. It points forward to the next free_block and backward to the previous free_block. The header stores information about the size and allocation status. The free_block also requires a footer, which, like before, is not explicitly mentioned. The footer is necessary during the coalescing phase to determine whether physically contiguous blocks are also free_blocks. Thus, when looking backward for a block, you need to use the footer of the previous block to find the location of its header.

Next, we will implement the core functions for the first part of malloc:

mm_init()

bool mm_init(void) {
    // initialize the seg list
    seg_list.list_num = 8;
    seg_list.threshlds[0] = min_block_size;
    seg_list.threshlds[1] = 64;
    seg_list.threshlds[2] = 128;
    seg_list.threshlds[3] = 256;
    seg_list.threshlds[4] = 512;
    seg_list.threshlds[5] = 2048;
    seg_list.threshlds[6] = 4096;
    seg_list.threshlds[7] = 8192;
    for(int i = 0; i < seg_list.list_num; ++i){
        seg_list.heads[i] = NULL;
    }
    // Create the initial empty heap
    word_t *start = (word_t *)(mem_sbrk(2 * wsize));

    if (start == (void *)-1) {
        return false;
    }
    start[0] = pack(0, true); // Heap prologue (block footer)
    start[1] = pack(0, true); // Heap epilogue (block header)

    // Heap starts with first "block header", currently the epilogue
    heap_start = (block_t *)&(start[1]);

    // Extend the empty heap with a free block of chunksize bytes
    if (extend_heap(chunksize) == NULL) {
        return false;
    }
    if(vbs)printf("mm_init success...\n");
    dbg_requires(mm_checkheap(__LINE__));
    return true;
}

During initialization, a series of tasks were performed.

typedef struct {
    block_t* heads[32];
    size_t threshlds[32];
    int list_num;
} segmentation_list_t;

static segmentation_list_t seg_list;

seg_list is a static pointer array that contains the heads of linked lists for free_blocks of various sizes. In mm_init, we initially define the size ranges for which they store free_blocks.

Afterward, the memory is initialized as shown in the diagram. Currently, there is only one free_block with a size of 4096.

malloc()

asize = round_up(size + 2 * dsize, dsize);

The input is the size needed to store the data, but we need to manually add space for the header and footer.

block = find_first_fit(asize);

Find a suitable free_block. If none is found, extend the heap.

split_block_seg_list(block, asize);

Manage the remaining free_block and add it to the seg_list.

This completes the malloc process.

free()

write_block(block, size, false);

mark block as free_block

coalesce_block(block);

coalesce and recycle free_block

coalesce_block()

static block_t *coalesce_block(block_t *block) {
    block_t *pys_prev_block = find_prev(block);
    block_t *pys_next_block = find_next(block);
    size_t size = get_size(block);
    bool pys_prev_alloc = get_alloc(pys_prev_block);
    bool pys_next_alloc = get_alloc(pys_next_block);
    
    if(pys_prev_alloc && pys_next_alloc){
        if(vbs)printf("A\n");
        insert_some_seg_list(block);
        return block;
    }else if (pys_prev_alloc && !pys_next_alloc)
    {
        if(vbs)printf("B\n");
        size += get_size(pys_next_block);
        remove_some_seg_list(pys_next_block);
        write_block(block, size, false);
        insert_some_seg_list(block);
    }else if (!pys_prev_alloc && pys_next_alloc)
    {
        if(vbs)printf("C\n");
        size += get_size(pys_prev_block);
        remove_some_seg_list(pys_prev_block);
        block = pys_prev_block;
        write_block(block, size, false);
        insert_some_seg_list(block);
    }else{
        if(vbs)printf("D\n");
        size += get_size(pys_prev_block) + get_size(pys_next_block);
        remove_some_seg_list(pys_prev_block);
        remove_some_seg_list(pys_next_block);
        block = pys_prev_block;
        write_block(block, size, false);
        insert_some_seg_list(block);
    }
    return block;
}

Before merging, it is necessary to check whether the preceding and following blocks are free_blocks that can be merged. Afterward, proceed with the removal and insertion operations in the linked list.

extend_heap()

size = round_up(size, dsize);

Round up and align the size that needs to be extended.

write_block(block, size, false);

Mark the new block as a free_block.

block_t *block_next = find_next(block);

write_epilogue(block_next);

Add the next header as an epilogue.

block = coalesce_block(block);

Merge the new free_block and add it to the appropriate seg_list.

split_block_seg_list()

static void split_block_seg_list(block_t *block, size_t asize){
    size_t size = get_size(block);
    size_t remainder_size = size-asize;
    if(remainder_size>=min_block_size){
        remove_some_seg_list(block);
        write_block(block, asize, true);
        block_t *remainder_block = find_next(block);
        write_block(remainder_block, remainder_size, false);
        insert_some_seg_list(remainder_block);
    }else{
        remove_some_seg_list(block);
        write_block(block, size, true);
    }
}

Note that marking the header of the allocated block as allocated (alloc state) is done at the end of the split_block_seg_list() function.

find_first_fit

static block_t *find_first_fit(size_t asize) {
    block_t *block;
    int seg_idx = fit_which_seg(asize);
    block_t *seg_head = seg_list.heads[seg_idx];
    if(seg_head == NULL){       // The seg list of good size is empty
        for(int i = seg_idx+1; i < seg_list.list_num; i++){
            if(seg_list.heads[i] != NULL){  // Search from small to big
                seg_head = seg_list.heads[i];
                if(vdbg)printf("Fund another head at seg_idx[%d](size=%d):%llx", i, (int)get_threshld(i), (unsigned long long)&(seg_head->header));
                break;
            }
        }
    }
    for(block = seg_head; block != NULL; block = get_list_next(block)){
        if(!(get_alloc(block)) && (get_size(block)>=asize)){
            return block;
        }
    }
    return NULL; // no fit found
}

Note here that if a suitable block of the required size is not found within the seg_list interval, you need to search in other seg_lists rather than directly returning NULL.

Second Part

In the second part, we will reduce internal fragmentation by removing the footer.

typedef struct block {
    /** @brief Header contains size + allocation flag 
     * normal block:
     * | size         |  x       | mini   | prev_alloc | alloc  |
     * | 63-4th:60bits| 3th:1bit |2th:1bit|  1th:1bit  |0th:1bit|
     * |              |          | 0      |            |        |
     * mini block:
     * | prev_address |  x       | mini   | prev_alloc | alloc  |
     * | 63-4th:60bits| 3th:1bit |2th:1bit|  1th:1bit  |0th:1bit|
     * |              |          | 1      |            |        |
    */
    word_t header;
    /**
     * @brief A pointer to the block payload.*
     */
    char payload[0];
} block_t;
/** @brief Represents free block to be allocated */
typedef struct free_block {
    /** @brief Header contains size + allocation flag 
     * normal block:
     * | size         |  x       | mini   | prev_alloc | alloc  |
     * | 63-4th:60bits| 3th:1bit |2th:1bit|  1th:1bit  |0th:1bit|
     * |              |          |        |            |        |
     * mini block:
     * | prev_address |  x       | mini   | prev_alloc | alloc  |
     * | 63-4th:60bits| 3th:1bit |2th:1bit|  1th:1bit  |0th:1bit|
     * |              |          |        |            |        |
    */
    word_t header;
    /** @brief point to the previous block*/
    block_t *ptr_prev;
    /** @brief point to the next block*/
    block_t *ptr_next;
} free_block_t;

In the first part, the footer was not explicitly marked to facilitate the removal of the footer in the second part. After removing the footer, coalescing can be achieved by marking in the header whether the previous block is a free_block. Additionally, to further reduce internal fragmentation, a mini flag is introduced in the header to distinguish between normal blocks and mini blocks. Note that mini here refers to whether the previous contiguous block in memory is a mini block. The following constants are introduced:

/** @brief Minimum block size (bytes) 16 bytes */
static const size_t min_block_size = dsize;

/** prev_alloc_mask is to find out the second last bit of the value to see whether prev alloc*/
static const word_t prev_alloc_mask = 0x1<<1;

/** prev_alloc_mask is to find out the second last bit of the value to see whether prev alloc*/
static const word_t mini_block_mask = 0x1<<2;

Additionally, mini_block free_blocks are distinguished as follows:

typedef struct mini_free_block {
    word_t header;
    block_t *ptr_next;
} mini_free_block_t;

So a mini_free_block is a singly linked list because there is no space to include a ptr_prev to point to the previous node.

The changes to the block structure primarily modify the implementation logic for marking and using blocks.

static void write_block(block_t *block, size_t size, bool alloc) {
    dbg_requires(block != NULL);
    dbg_requires(size > 0);
    bool prev_alloc = get_prev_alloc(block); // get the status of prev alloc
    bool prev_mini = get_prev_mini(block);   // get the status of prev mini
    block->header = pack(size, alloc);       // update the header
    write_block_prev_alloc(block,
                           prev_alloc); // remain the prev allocation status
    write_block_prev_mini(block, prev_mini); // remain the prev miniblock status
    if (alloc == false &&
        (size > min_block_size)) { // write footer if block free
        word_t *footerp = header_to_footer(block);
        *footerp = pack(size, alloc);
    }
}

Other functions also need to adjust the marking logic accordingly, particularly in coalesce.

    // update the header's  previous alloc to true
    write_block_prev_alloc(block, true);
    // update the next block's mini status
    write_block_prev_mini(find_next(block), size == min_block_size);
    // mark the next block's previous alloc status as false
    write_block_prev_alloc(find_next(block), false);

Additionally, if the previous block is a mini block, you directly move back by 16 bytes. If the previous block is not a mini block and is not allocated, you need to find the footer of the previous block, then obtain the size of the previous block, and finally move back to find the header of the previous block.

Since mini_free_block is a singly linked list, deleting a mini_free_block node inevitably incurs an O(N) complexity.

    if (seg_idx == 0) {
        dbg_requires(get_size(block) == min_block_size &&
                     "insert first seg list should be size 16");
        // O(N) search
        block_t *prev_block;
        for (prev_block = seg_list.heads[0]; prev_block != NULL;
             prev_block = get_list_next(prev_block)) {
            if (&prev_block->header == &block->header) { // block found at head
                seg_list.heads[0] = NULL;
                break;
            } else if (&(get_list_next(prev_block)->header) == &block->header) {
                set_list_next(prev_block, NULL);
                b2mf(block)->ptr_next = NULL;
                break;
            }
        }
    }

At this point, the Malloc Lab is complete.