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;

}