umalloc.c

#include "umalloc.h"
#include "csbrk.h"
#include <stdio.h>
#include <assert.h>
#include "ansicolors.h"

const char author[] = ANSI_BOLD ANSI_COLOR_RED "Derek Chen dyc377" ANSI_RESET;

/*
 * The following helpers can be used to interact with the memory_block_t
 * struct, they can be adjusted as necessary.
 */

// A sample pointer to the start of the free list.
memory_block_t *free_head;

/*
 * is_allocated - returns true if a block is marked as allocated.
 */
bool is_allocated(memory_block_t *block) {
    assert(block != NULL);
    return block->block_size_alloc & 0x1;
}

/*
 * allocate - marks a block as allocated.
 */
void allocate(memory_block_t *block) {
    assert(block != NULL);
    block->block_size_alloc |= 0x1;
}


/*
 * deallocate - marks a block as unallocated.
 */
void deallocate(memory_block_t *block) {
    assert(block != NULL);
    block->block_size_alloc &= ~0x1;
}

/*
 * get_size - gets the size of the block.
 */
size_t get_size(memory_block_t *block) {
    assert(block != NULL);
    return block->block_size_alloc & ~(ALIGNMENT-1);
}

/*
 * get_next - gets the next block.
 */
memory_block_t *get_next(memory_block_t *block) {
    assert(block != NULL);
    return block->next;
}

/*
 * put_block - puts a block struct into memory at the specified address.
 * Initializes the size and allocated fields, along with NUlling out the next 
 * field.
 */
void put_block(memory_block_t *block, size_t size, bool alloc) {
    assert(block != NULL);
    assert(size % ALIGNMENT == 0);
    assert(alloc >> 1 == 0);
    block->block_size_alloc = size | alloc;
    block->next = NULL;
}

/*
 * get_payload - gets the payload of the block.
 */
void *get_payload(memory_block_t *block) {
    assert(block != NULL);
    return (void*)(block + 1);
}

/*
 * get_block - given a payload, returns the block.
 */
memory_block_t *get_block(void *payload) {
    assert(payload != NULL);
    return ((memory_block_t *)payload) - 1;
}

/*
 * The following are helper functions that can be implemented to assist in your
 * design, but they are not required. 
 */

/*
 * find - finds a free block that can satisfy the umalloc request.
 */
memory_block_t *find(size_t size) {
    assert(size % ALIGNMENT == 0);
    memory_block_t *cur = free_head;
    memory_block_t *prev = NULL;
    while (cur) {
        /* Iterate through the free linkedlist
        Return a valid block that suits the size or NULL if none
        */
        if(get_size(cur) >= size) {
            return cur;
        }
        prev = cur;
        cur = cur->next;
    }   
    if(!cur) {
        /* If no suitable blocks were found in the free list extend and get a new block
        At this point, prev should point to the end of the list with cur
        being the next value (null)
        */
        memory_block_t *alloMem = extend(size);
        if(prev) {
            prev->next = alloMem;
        }
        return alloMem;
    }
    return NULL;
}

/*
 * extend - extends the heap if more memory is required.
 */
memory_block_t *extend(size_t size) {
    assert(size % ALIGNMENT == 0);
    memory_block_t *temp = csbrk(size + ALIGNMENT);
    temp->block_size_alloc = size + ALIGNMENT;
    return temp;
}

/*
 * split - splits a given block in parts, one allocated, one free.
 */
memory_block_t *split(memory_block_t *block, size_t size) {
    assert(block != NULL);
    assert(size % ALIGNMENT == 0);
    memory_block_t *endBlock = (memory_block_t*)((unsigned long)block + (block->block_size_alloc - size));
    block->block_size_alloc = block->block_size_alloc - size;
    /* So turns out using put_block was constantly incrementing the size I gave due to the bitwise OR..... that would've been nice to find when I was debugging at 3 AM 
    Trying to set the block_size_alloc manually now and it seems to work as intended yay.
    */
    endBlock->block_size_alloc = size;
    return endBlock;
}

/*
 * coalesce - coalesces a free memory block with neighbors.
 */
memory_block_t *coalesce(memory_block_t *block) {
    //* STUDENT TODO
    return NULL;
}

/*
 * uinit - Used initialize metadata required to manage the heap
 * along with allocating initial memory.
 */
int uinit() {
    free_head = csbrk(PAGESIZE + ALIGNMENT);
    return free_head ? 0 : -1;
}

/*
 * removeBlock - removes the given block from the LinkedList
 */
memory_block_t *removeBlock(memory_block_t *tgt) {
    assert(tgt != NULL);
    memory_block_t *cur = free_head;
    memory_block_t *prev = NULL;
    while (cur) {
        if(cur == tgt) {
            if(!prev) {
                // If the head is to be removed 
                free_head = cur->next;
            } else {
                // Block to be removed has a previous value
                prev->next = cur->next;
            }
            return cur;
        }
        prev = cur;
        cur = cur->next;
    }
    return NULL;
}

/*
 * umalloc -  allocates size bytes and returns a pointer to the allocated memory.
 */
void *umalloc(size_t size) {
    // Change size to aligned 
    size_t alignedSize = ALIGN(ALIGNMENT + size);
    memory_block_t *alloMem = find(alignedSize);
    if ((get_size(alloMem) * 0.5) >= alignedSize) {
        // If threshold is met, we split the block
        memory_block_t *splitMem = split(alloMem, alignedSize);
        allocate(splitMem);
        return get_payload(splitMem);
    } 
    // Otherwise remove the block from the list and give to user
    removeBlock(alloMem);
    allocate(alloMem);
    return get_payload(alloMem);
}

/*
 * ufree -  frees the memory space pointed to by ptr, which must have been called
 * by a previous call to malloc.
 */
void ufree(void *ptr) {
    memory_block_t *block = get_block(ptr);
    deallocate(block);
    if(!free_head) {
        // Makes free_head a block if it is null (list is empty)
        free_head = block;
        return;
    }
    memory_block_t *cur = free_head;
    memory_block_t *prev = NULL;
    while (cur) {
        if((long)block > (long)cur) {
            // Found spot where block is greater than cur in the list, insert it in
            block->next = cur->next;
            cur->next = block;
            return;
        }
        prev = cur;
        cur = cur->next;
    }    
    // If cur is null (reached the end), add block to the end
    prev->next = block;
}