Subversion Repositories Code-Repo

/*
 * This implementation of a memory allocation utilizes a segregated fits
 * appraoch. Multiple buckets are used for each size range and a doubly
 * linked list used to hold the list of free blocks for each bucket.
 * Free blocks for each bucket is choosen based on first fit, with the
 * search going into the next sized bucket if no fit is found in the
 * current bucket. If no free blocks are found that holds the requested
 * size, more memory is requested by incrementing the brk pointer using
 * mem_sbrk. The requested memory is in a multiple of the page size for
 * higher allocating efficiency. Freeing a previously allocated block
 * coalesces the block with the previous and next blocks if they are
 * empty. The last 4 bytes in each block is used as a boundary tag that
 * holds the size of the block it is in. This allows the code to 
 * traverse backwards in the address space and check if the previous
 * block is empty or allocated.
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include <stddef.h>
#include <limits.h>

#include "mm.h"
#include "memlib.h"
#include "list.h"
#include "config.h"             /* defines ALIGNMENT */

#define FREE_SPACE_SPLIT_OVERHEAD 512

/*********************************************************
 * NOTE TO STUDENTS: Before you do anything else, please
 * provide your team information in the following struct.
 ********************************************************/
team_t team = {
    /* Team name */
    "Team K",
    /* First member's full name */
    "Kevin Lee",
    /* First member's SLO (@cs.vt.edu) email address */
    "klee482@vt.edu",
    /* Second member's full name (leave blank if none) */
    "",
    /* Second member's SLO (@cs.vt.edu) email address (leave blank if none) */
    ""
};

/* 
 * If size is a multiple of ALIGNMENT, return size.
 * Else, return next larger multiple of ALIGNMENT:
 * (size/ALIGNMENT + 1) * ALIGNMENT
 * Does so without requiring integer division, assuming
 * ALIGNMENT is a power of 2.
 */
static size_t roundup(size_t size)
{
    return (size + ALIGNMENT - 1) & ~(ALIGNMENT - 1);
}

/* 
 * This C struct captures an allocated header.
 *
 * By casting a memory location to a pointer to a allocated_block_header,
 * we are able to treat a part of memory as if a header had been allocated
 * in it.
 *
 * Note: you should never define instances of 'struct allocated_block_header' -
 *       all accesses will be through pointers.
 */
struct allocated_block_header {
    size_t      size;   // Size of the block, includes header and padding

    /* 
     * Zero length arrays do not add size to the structure, they simply
     * provide a syntactic form to refer to a char array following the
     * structure.
     * See http://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html
     *
     * The 'aligned' attribute forces 'payload' to be aligned at a
     * multiple of alignment, counted from the beginning of the struct
     * See http://gcc.gnu.org/onlinedocs/gcc/Variable-Attributes.html
     */
    char        payload[0] __attribute__((aligned(ALIGNMENT)));
};

/* 
 * This C struct captures a free header.
 *
 * By casting a memory location to a pointer to a free_block_header,
 * we are able to treat a part of memory as if a header had been allocated
 * in it.
 */
struct free_block_header {
    size_t      size;               // Size of the block, includes header and padding
    struct      list_elem elem;     // Allows the struct to be used in a doublely linked list
};

/* 
 * This C struct captures a bucket of free blocks
 *
 * This struct is an element of a list that holds list of free blocks as
 * well as relevant information for the bucket (size of free blocks).
 */
struct free_list_index {
    struct      list free_block_list;   // List of free blocks
    int         size_min;               // Minimum size of each block
    int         size_max;               // Maximum size of each block
    struct      list_elem elem;          // Allows the struct to be used in a doublely linked list
};

/* 
 * This C struct captures a boundary tag
 *
 * By casting a memory location to a pointer to a boundary tag,
 * we can read the size of the block from the front or the back.
 */
struct boundary_block {
    size_t size;
};

// Global list holding the main list of buckets and each bucket's list
struct list index_of_free_lists;
struct free_list_index bucket_1 = {.size_min = 1, .size_max = 2};
struct free_list_index bucket_2 = {.size_min = 3, .size_max = 8};
struct free_list_index bucket_3 = {.size_min = 9, .size_max = 32};
struct free_list_index bucket_4 = {.size_min = 33, .size_max = 128};
struct free_list_index bucket_5 = {.size_min = 129, .size_max = 512};
struct free_list_index bucket_6 = {.size_min = 513, .size_max = 1024};
struct free_list_index bucket_7 = {.size_min = 1025, .size_max = 2048};
struct free_list_index bucket_8 = {.size_min = 2049, .size_max = 4096};
struct free_list_index bucket_9 = {.size_min = 4097, .size_max = 8192};
struct free_list_index bucket_10 = {.size_min = 8193, .size_max = 16384};
struct free_list_index bucket_11 = {.size_min = 16385, .size_max = 32768};
struct free_list_index bucket_12 = {.size_min = 32769, .size_max = 65536};
struct free_list_index bucket_13 = {.size_min = 65537, .size_max = INT_MAX};

/*
 * alloc_block_set_boundary_tags - Sets the boundary tags for allocated blocks
 */
void alloc_block_set_boundary_tags(void *alloc_block) {
    struct allocated_block_header *block = alloc_block;
    int size = block->size;
    block->size |= 1;

    struct boundary_block *f = alloc_block + size - sizeof(size_t);

    f->size = size |= 1;
}

/*
 * free_block_set_boundary_tags - Sets the boundary tags for free blocks
 */
void free_block_set_boundary_tags(void *free_block) {
    struct free_block_header *block = free_block;

    struct boundary_block *f = free_block + block->size - sizeof(size_t);

    f->size = block->size;
}

/*
 * free_block_insert - Takes a free block and pushes it to the front of the
 *      correct list that it fits in. Also coalesces the block with the blocks
 *      before and after it in the address space.
 */
void free_block_insert(void *free_block) {
    struct free_block_header *block = free_block;

    // Check if the block can be combined with any free blocks before or after
    bool prev_block_empty = false;
    bool next_block_empty = false;

    struct boundary_block *prev = free_block - sizeof(size_t);
    struct boundary_block *next = free_block + block->size;

    if (free_block != mem_heap_lo()) {   
        if ((prev->size & 1) == 0) {
            prev_block_empty = true;
        }
    }

    if (free_block + block->size != mem_heap_hi() + 1) {
        if ((next->size & 1) == 0) {
            next_block_empty = true;
        }
    }

    // Combine blocks accordingly
    if (prev_block_empty && next_block_empty) {
        // Both previous and next blocks are empty
        struct free_block_header *prev_block = free_block - prev->size;
        struct free_block_header *next_block = free_block + block->size;
        list_remove(&prev_block->elem); 
        list_remove(&next_block->elem);
        prev_block->size += block->size;
        prev_block->size += next_block->size;
        block = prev_block;
    } else if (prev_block_empty && !next_block_empty) {
        // Only the previous block is empty
        struct free_block_header *prev_block = free_block - prev->size;
        list_remove(&prev_block->elem); 
        prev_block->size += block->size;
        block = prev_block;
    } else if (!prev_block_empty && next_block_empty) {
        // Only the next block is empty
        struct free_block_header *next_block = free_block + block->size;
        list_remove(&next_block->elem);
        block->size += next_block->size;
    }

    free_block_set_boundary_tags(block);

    // Insert the free block into the bucket that it belongs to
    struct list_elem *index = list_begin(&index_of_free_lists);
    while (index != list_end(&index_of_free_lists)) {
        struct free_list_index *index_entry = list_entry(index, struct free_list_index, elem);

        if (block->size >= index_entry->size_min && block->size <= index_entry->size_max) {
            list_push_front(&index_entry->free_block_list, &block->elem);
            return;
        }

        index = list_next(index);
    }
}

/*
 * free_block_alloc - Uses the free space specified in free_block_header to
 *      hold a new allocated block of size alloc_size.
 */
void *free_block_alloc(void *free_block, size_t alloc_size, bool block_in_list) {
    struct free_block_header *block = free_block;
    if (block_in_list)
        list_remove(&block->elem);

    // Before we split up the free block, we need to check if there is enough 
    //  space for holding another free block header.
    if (block->size - alloc_size > sizeof(struct free_block_header)+FREE_SPACE_SPLIT_OVERHEAD) {
        // There is enough space for another free block + overhead
        int combined_size = block->size;
        block = free_block + alloc_size;
        block->size = combined_size - alloc_size;

        struct allocated_block_header *ret = free_block;
        ret->size = alloc_size;
        alloc_block_set_boundary_tags(ret);

        free_block_insert(block);
        return ret;
    } else {
        // If there is not enough space for a free block header, simply
        //  convert to an allocated block header and return
        struct allocated_block_header *ret = free_block;
        alloc_block_set_boundary_tags(ret);
        return ret;
    }
}

/* 
 * free_block_search - Given a list of free_block_headers, finds
 *      and returns the first block that can hold the requested size. 
 *      If no blocks were found, returns NULL.
 */
void *free_block_search(void *free_block_list, int requested_size) {
    struct list *block_list = free_block_list;
    struct list_elem *e = list_begin(block_list);
    while (e != list_end(block_list)) {
        struct free_block_header *entry= list_entry(e, struct free_block_header, elem);
        if (entry->size >= requested_size) {
            return entry;
        } 
        e = list_next(e);
    }

    return NULL;
}

/*
 * mm_check - Checks the heap for consistency. Returns a non-zero value
 *      only if the heap is consistent.
 */
 int mm_check(void)
 {
    // Prints out the free blocks in each bucket when called
    printf("Heap allocated from %d to %d of size %d\n", (int)mem_heap_lo(), (int)mem_heap_hi(), mem_heapsize());
    printf("----------------------------------------\n");
    struct list_elem *index = list_begin(&index_of_free_lists);
    while (index != list_end(&index_of_free_lists)) {
        struct free_list_index *index_entry = list_entry(index, struct free_list_index, elem);
        printf("Bucket of size %d - %d:\n", index_entry->size_min, index_entry->size_max);

        struct list_elem *entry = list_begin(&index_entry->free_block_list);
        while(entry != list_end(&index_entry->free_block_list)) {
            struct free_block_header *block = list_entry(entry, struct free_block_header, elem);
            printf("\tFree Block at %d of size %d\n", (int)block, block->size);
            entry = list_next(entry);
        }

        index = list_next(index);
    }
    printf("----------------------------------------\n");
    return 1;
 }

/* 
 * mm_init - Initialize the malloc package.
 */
int mm_init(void)
{
    /* Sanity checks. */
    assert((ALIGNMENT & (ALIGNMENT - 1)) == 0); // power of 2
    assert(sizeof(struct allocated_block_header) == ALIGNMENT);
    assert(offsetof(struct allocated_block_header, size) == 0);
    assert(offsetof(struct allocated_block_header, payload) % ALIGNMENT == 0);

    // Initialize the overall list of free lists
    list_init(&index_of_free_lists);

    // Initialize the list for each bucket size
    list_init(&bucket_1.free_block_list);
    list_init(&bucket_2.free_block_list);
    list_init(&bucket_3.free_block_list);
    list_init(&bucket_4.free_block_list);
    list_init(&bucket_5.free_block_list);
    list_init(&bucket_6.free_block_list);
    list_init(&bucket_7.free_block_list);
    list_init(&bucket_8.free_block_list);
    list_init(&bucket_9.free_block_list);
    list_init(&bucket_10.free_block_list);
    list_init(&bucket_11.free_block_list);
    list_init(&bucket_12.free_block_list);
    list_init(&bucket_13.free_block_list);

    // Insert the list into the main list
    list_push_back(&index_of_free_lists, &bucket_1.elem);
    list_push_back(&index_of_free_lists, &bucket_2.elem);
    list_push_back(&index_of_free_lists, &bucket_3.elem);
    list_push_back(&index_of_free_lists, &bucket_4.elem);
    list_push_back(&index_of_free_lists, &bucket_5.elem);
    list_push_back(&index_of_free_lists, &bucket_6.elem);
    list_push_back(&index_of_free_lists, &bucket_7.elem);
    list_push_back(&index_of_free_lists, &bucket_8.elem);
    list_push_back(&index_of_free_lists, &bucket_9.elem);
    list_push_back(&index_of_free_lists, &bucket_10.elem);
    list_push_back(&index_of_free_lists, &bucket_11.elem);
    list_push_back(&index_of_free_lists, &bucket_12.elem);
    list_push_back(&index_of_free_lists, &bucket_13.elem);

    return 0;
}

/* 
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */
void *mm_malloc(size_t size)
{
    int newsize = roundup(size + sizeof(struct free_block_header));
    int searchsize = newsize;

    // Look for free block list that contains the right sized blocks
    struct list_elem *index = list_begin(&index_of_free_lists);
    while (index != list_end(&index_of_free_lists)) {
        struct free_list_index *index_entry = list_entry(index, struct free_list_index, elem);

        if (searchsize >= index_entry->size_min && searchsize <= index_entry->size_max) {
            // Try to get a free block that is large enough to hold the requested size
            struct free_block_header *free_block = free_block_search(&index_entry->free_block_list, newsize);
            if (free_block == NULL) {
                // List is empty, look at the next block size
                searchsize = index_entry->size_max + 1;
            } else {
                // Empty block was found, use the block to allocate space
                struct allocated_block_header *alloc_block = free_block_alloc(free_block, newsize, true);
                return alloc_block->payload;
            }
        }
        index = list_next(index);
    }


    // If no blocks were found, expand the heap and allocate the block from there

    // Calculage how many pages are needed to fit the block
    int alloc_size = (newsize / mem_pagesize() + 1) * mem_pagesize();

    // Get a number of pages from the heap and allocate from there
    struct free_block_header *free_block = mem_sbrk(alloc_size);
    if (free_block == NULL)
        return NULL;
    free_block->size = alloc_size;
    struct allocated_block_header *alloc_block = free_block_alloc(free_block, newsize, false);
    return alloc_block->payload;
}

/*
 * mm_free - Frees the specified block, inserting it into the list of free blocks
 */
void mm_free(void *ptr)
{
    // Get a pointer to the original block
    struct free_block_header *new_block = ptr - offsetof(struct allocated_block_header, payload);

    // Mark the block as free and insert it into the list of free blocks
    new_block->size ^= 1;   
    free_block_insert(new_block);
}

/*
 * mm_realloc - Resizes the specified block, leaving it if the size is smaller and allocating
 *      and copying the data to a new block if the size is larger. Extra space is left for
 *      future resizing.
 */
void *mm_realloc(void *oldptr, size_t size)
{
    struct allocated_block_header *old_block = oldptr - offsetof(struct allocated_block_header, payload);
    // old_block->size ^= 1;

    // If the block is already large enough to hold the new size, simply return
    if (size <= old_block->size - sizeof(struct free_block_header) - sizeof(size_t))
        return old_block->payload;

    // // Otherwise we need to allocate a new block of the request size
    void *new_block = mm_malloc(size + 6 * mem_pagesize());
    if (new_block == NULL)
        return NULL;

    // Copy the old data to the new block
    size_t copySize = old_block->size;
    if (size < copySize)
        copySize = size;

    memcpy(new_block, oldptr, copySize);

    // Free the old block and return the new one
    mm_free(oldptr);
    return new_block;
}