/* ****************************************************************************** * mm-baseline.c * * 64-bit struct-based implicit free list memory allocator * * 15-213: Introduction to Computer Systems * * * * ************************************************************************ * * DOCUMENTATION * * * * ** STRUCTURE. ** * * * * Both allocated and free blocks share the same header structure. * * HEADER: 8-byte, aligned to 8th byte of an 16-byte aligned heap, where * * - The lowest order bit is 1 when the block is allocated, and * * 0 otherwise. * * - The whole 8-byte value with the least significant bit set to 0 * * represents the size of the block as a size_t * * The size of a block includes the header and footer. * * FOOTER: 8-byte, aligned to 0th byte of an 16-byte aligned heap. It * * contains the exact copy of the block's header. * * The minimum blocksize is 32 bytes. * * * * Allocated blocks contain the following: * * HEADER, as defined above. * * PAYLOAD: Memory allocated for program to store information. * * FOOTER, as defined above. * * The size of an allocated block is exactly PAYLOAD + HEADER + FOOTER. * * * * Free blocks contain the following: * * HEADER, as defined above. * * FOOTER, as defined above. * * The size of an unallocated block is at least 32 bytes. * * * * Block Visualization. * * block block+8 block+size-8 block+size * * Allocated blocks: | HEADER | ... PAYLOAD ... | FOOTER | * * * * block block+8 block+size-8 block+size * * Unallocated blocks: | HEADER | ... (empty) ... | FOOTER | * * * * ************************************************************************ * * ** INITIALIZATION. ** * * * * The following visualization reflects the beginning of the heap. * * start start+8 start+16 * * INIT: | PROLOGUE_FOOTER | EPILOGUE_HEADER | * * PROLOGUE_FOOTER: 8-byte footer, as defined above, that simulates the * * end of an allocated block. Also serves as padding. * * EPILOGUE_HEADER: 8-byte block indicating the end of the heap. * * It simulates the beginning of an allocated block * * The epilogue header is moved when the heap is extended. * * * * ************************************************************************ * * ** BLOCK ALLOCATION. ** * * * * Upon memory request of size S, a block of size S + dsize, rounded up to * * 16 bytes, is allocated on the heap, where dsize is 2*8 = 16. * * Selecting the block for allocation is performed by finding the first * * block that can fit the content based on a first-fit or next-fit search * * policy. * * The search starts from the beginning of the heap pointed by heap_listp. * * It sequentially goes through each block in the implicit free list, * * the end of the heap, until either * * - A sufficiently-large unallocated block is found, or * * - The end of the implicit free list is reached, which occurs * * when no sufficiently-large unallocated block is available. * * In case that a sufficiently-large unallocated block is found, then * * that block will be used for allocation. Otherwise--that is, when no * * sufficiently-large unallocated block is found--then more unallocated * * memory of size chunksize or requested size, whichever is larger, is * * requested through mem_sbrk, and the search is redone. * * * * ************************************************************************ * * ** ADVICE FOR STUDENTS. ** * * Step 0: Please read the writeup! * * Write your heap checker. Write your heap checker. Write. Heap. checker. * * Good luck, and have fun! * * * ****************************************************************************** */ /* Do not change the following! */ #include #include #include #include #include #include #undef NDEBUG // the assert()s in this particular implementation are all O(1) and vital #include #include "memlib.h" #define dbg_requires(...) assert(__VA_ARGS__) #define dbg_assert(...) assert(__VA_ARGS__) #define dbg_ensures(...) assert(__VA_ARGS__) /* Basic constants */ typedef uint64_t word_t; static const size_t wsize = sizeof(word_t); // word and header size (bytes) static const size_t dsize = 2*sizeof(word_t); // double word size (bytes) static const size_t min_block_size = 4*sizeof(word_t); // Minimum block size static const size_t chunksize = (1 << 12); // requires (chunksize % 16 == 0) static const word_t alloc_mask = 0x1; static const word_t size_mask = ~(word_t)0xF; typedef struct block { /* Header contains size + allocation flag */ word_t header; /* * We don't know how big the payload will be. Declaring it as an * array of size 0 allows computing its starting address using * pointer notation. */ char payload[0]; /* * We can't declare the footer as part of the struct, since its starting * position is unknown */ } block_t; /* Global variables */ /* Pointer to first block */ static block_t *heap_listp = NULL; /* Function prototypes for internal helper routines */ static block_t *extend_heap(size_t size); static void place(block_t *block, size_t asize); static block_t *find_fit(size_t asize); static block_t *coalesce(block_t *block); static size_t max(size_t x, size_t y); static size_t round_up(size_t size, size_t n); static word_t pack(size_t size, bool alloc); static size_t extract_size(word_t header); static size_t get_size(block_t *block); static size_t get_payload_size(block_t *block); static bool extract_alloc(word_t header); static bool get_alloc(block_t *block); static void write_header(block_t *block, size_t size, bool alloc); static void write_footer(block_t *block, size_t size, bool alloc); static block_t *payload_to_header(void *bp); static void *header_to_payload(block_t *block); static block_t *find_next(block_t *block); static word_t *find_prev_footer(block_t *block); static block_t *find_prev(block_t *block); bool mm_checkheap(int lineno); /* * mm_init: initializes the heap; it is run once when heap_start == NULL. * prior to any extend_heap operation, this is the heap: * start start+8 start+16 * INIT: | PROLOGUE_FOOTER | EPILOGUE_HEADER | * heap_listp ends up pointing to the epilogue header. */ bool mm_init(void) { mem_init(0xffffffff); // Create the initial empty heap word_t *start = (word_t *)(mem_sbrk(2*wsize)); if (start == NULL) { return false; } start[0] = pack(0, true); // Prologue footer start[1] = pack(0, true); // Epilogue header // Heap starts with first block header (epilogue) heap_listp = (block_t *) &(start[1]); // Extend the empty heap with a free block of chunksize bytes if (extend_heap(chunksize) == NULL) { return false; } return true; } /* * malloc: allocates a block with size at least (size + dsize), rounded up to * the nearest 16 bytes, with a minimum of 2*dsize. Seeks a * sufficiently-large unallocated block on the heap to be allocated. * If no such block is found, extends heap by the maximum between * chunksize and (size + dsize) rounded up to the nearest 16 bytes, * and then attempts to allocate all, or a part of, that memory. * Returns NULL on failure, otherwise returns a pointer to such block. * The allocated block will not be used for further allocations until * freed. */ void *_malloc(size_t size) { dbg_requires(mm_checkheap(__LINE__)); size_t asize; // Adjusted block size size_t extendsize; // Amount to extend heap if no fit is found block_t *block; void *bp = NULL; if (heap_listp == NULL) // Initialize heap if it isn't initialized { mm_init(); } if (size == 0) // Ignore spurious request { dbg_ensures(mm_checkheap(__LINE__)); return bp; } // Adjust block size to include overhead and to meet alignment requirements asize = round_up(size, dsize) + dsize; // Search the free list for a fit block = find_fit(asize); // If no fit is found, request more memory, and then and place the block if (block == NULL) { extendsize = max(asize, chunksize); block = extend_heap(extendsize); if (block == NULL) // extend_heap returns an error { return bp; } } place(block, asize); bp = header_to_payload(block); dbg_ensures(mm_checkheap(__LINE__)); return bp; } /* * free: Frees the block such that it is no longer allocated while still * maintaining its size. Block will be available for use on malloc. */ void _free(void *bp) { if (bp == NULL) { return; } block_t *block = payload_to_header(bp); size_t size = get_size(block); write_header(block, size, false); write_footer(block, size, false); coalesce(block); } /* * realloc: returns a pointer to an allocated region of at least size bytes: * if ptrv is NULL, then call malloc(size); * if size == 0, then call free(ptr) and returns NULL; * else allocates new region of memory, copies old data to new memory, * and then free old block. Returns old block if realloc fails or * returns new pointer on success. */ void *_realloc(void *ptr, size_t size) { block_t *block = payload_to_header(ptr); size_t copysize; void *newptr; // If size == 0, then free block and return NULL if (size == 0) { _free(ptr); return NULL; } // If ptr is NULL, then equivalent to malloc if (ptr == NULL) { return _malloc(size); } // Otherwise, proceed with reallocation newptr = _malloc(size); // If malloc fails, the original block is left untouched if (!newptr) { return NULL; } // Copy the old data copysize = get_payload_size(block); // gets size of old payload if(size < copysize) { copysize = size; } memcpy(newptr, ptr, copysize); // Free the old block _free(ptr); return newptr; } /* * calloc: Allocates a block with size at least (elements * size + dsize) * through malloc, then initializes all bits in allocated memory to 0. * Returns NULL on failure. */ void *_calloc(size_t nmemb, size_t size) { void *bp; size_t asize = nmemb * size; if (asize/nmemb != size) // Multiplication overflowed return NULL; bp = _malloc(asize); if (bp == NULL) { return NULL; } // Initialize all bits to 0 memset(bp, 0, asize); return bp; } /******** The remaining content below are helper and debug routines ********/ /* * extend_heap: Extends the heap with the requested number of bytes, and * recreates epilogue header. Returns a pointer to the result of * coalescing the newly-created block with previous free block, if * applicable, or NULL in failure. */ static block_t *extend_heap(size_t size) { void *bp; // Allocate an even number of words to maintain alignment size = round_up(size, dsize); if ((bp = mem_sbrk(size)) == NULL) { return NULL; } // Initialize free block header/footer block_t *block = payload_to_header(bp); write_header(block, size, false); write_footer(block, size, false); // Create new epilogue header block_t *block_next = find_next(block); write_header(block_next, 0, true); // Coalesce in case the previous block was free return coalesce(block); } /* Coalesce: Coalesces current block with previous and next blocks if either * or both are unallocated; otherwise the block is not modified. * Returns pointer to the coalesced block. After coalescing, the * immediate contiguous previous and next blocks must be allocated. */ static block_t *coalesce(block_t * block) { block_t *block_next = find_next(block); block_t *block_prev = find_prev(block); bool prev_alloc = extract_alloc(*(find_prev_footer(block))); bool next_alloc = get_alloc(block_next); size_t size = get_size(block); if (prev_alloc && next_alloc) // Case 1 { return block; } else if (prev_alloc && !next_alloc) // Case 2 { size += get_size(block_next); write_header(block, size, false); write_footer(block, size, false); } else if (!prev_alloc && next_alloc) // Case 3 { size += get_size(block_prev); write_header(block_prev, size, false); write_footer(block_prev, size, false); block = block_prev; } else // Case 4 { size += get_size(block_next) + get_size(block_prev); write_header(block_prev, size, false); write_footer(block_prev, size, false); block = block_prev; } return block; } /* * place: Places block with size of asize at the start of bp. If the remaining * size is at least the minimum block size, then split the block to the * the allocated block and the remaining block as free, which is then * inserted into the segregated list. Requires that the block is * initially unallocated. */ static void place(block_t *block, size_t asize) { size_t csize = get_size(block); if ((csize - asize) >= min_block_size) { block_t *block_next; write_header(block, asize, true); write_footer(block, asize, true); block_next = find_next(block); write_header(block_next, csize-asize, false); write_footer(block_next, csize-asize, false); } else { write_header(block, csize, true); write_footer(block, csize, true); } } /* * find_fit: Looks for a free block with at least asize bytes with * first-fit policy. Returns NULL if none is found. */ static block_t *find_fit(size_t asize) { block_t *block; for (block = heap_listp; get_size(block) > 0; block = find_next(block)) { if (!(get_alloc(block)) && (asize <= get_size(block))) { return block; } } return NULL; // no fit found } /* * max: returns x if x > y, and y otherwise. */ static size_t max(size_t x, size_t y) { return (x > y) ? x : y; } /* * round_up: Rounds size up to next multiple of n */ static size_t round_up(size_t size, size_t n) { return (n * ((size + (n-1)) / n)); } /* * pack: returns a header reflecting a specified size and its alloc status. * If the block is allocated, the lowest bit is set to 1, and 0 otherwise. */ static word_t pack(size_t size, bool alloc) { return alloc ? (size | 1) : size; } /* * extract_size: returns the size of a given header value based on the header * specification above. */ static size_t extract_size(word_t word) { return (word & size_mask); } /* * get_size: returns the size of a given block by clearing the lowest 4 bits * (as the heap is 16-byte aligned). */ static size_t get_size(block_t *block) { return extract_size(block->header); } /* * get_payload_size: returns the payload size of a given block, equal to * the entire block size minus the header and footer sizes. */ static size_t get_payload_size(block_t *block) { size_t asize = get_size(block); return asize - dsize; } /* * extract_alloc: returns the allocation status of a given header value based * on the header specification above. */ static bool extract_alloc(word_t word) { return (bool)(word & alloc_mask); } /* * get_alloc: returns true when the block is allocated based on the * block header's lowest bit, and false otherwise. */ static bool get_alloc(block_t *block) { return extract_alloc(block->header); } /* * write_header: given a block and its size and allocation status, * writes an appropriate value to the block header. */ static void write_header(block_t *block, size_t size, bool alloc) { block->header = pack(size, alloc); } /* * write_footer: given a block and its size and allocation status, * writes an appropriate value to the block footer by first * computing the position of the footer. */ static void write_footer(block_t *block, size_t size, bool alloc) { word_t *footerp = (word_t *)((block->payload) + get_size(block) - dsize); *footerp = pack(size, alloc); } /* * find_next: returns the next consecutive block on the heap by adding the * size of the block. */ static block_t *find_next(block_t *block) { dbg_requires(block != NULL); block_t *block_next = (block_t *)(((char *)block) + get_size(block)); dbg_ensures(block_next != NULL); return block_next; } /* * find_prev_footer: returns the footer of the previous block. */ static word_t *find_prev_footer(block_t *block) { // Compute previous footer position as one word before the header return (&(block->header)) - 1; } /* * find_prev: returns the previous block position by checking the previous * block's footer and calculating the start of the previous block * based on its size. */ static block_t *find_prev(block_t *block) { word_t *footerp = find_prev_footer(block); size_t size = extract_size(*footerp); return (block_t *)((char *)block - size); } /* * payload_to_header: given a payload pointer, returns a pointer to the * corresponding block. */ static block_t *payload_to_header(void *bp) { return (block_t *)(((char *)bp) - offsetof(block_t, payload)); } /* * header_to_payload: given a block pointer, returns a pointer to the * corresponding payload. */ static void *header_to_payload(block_t *block) { return (void *)(block->payload); } /* mm_checkheap: checks the heap for correctness; returns true if * the heap is correct, and false otherwise. * can call this function using mm_checkheap(__LINE__); * to identify the line number of the call site. */ bool mm_checkheap(int lineno) { (void)lineno; if (heap_listp != NULL) { // check prologue footer: size is 0 and prologue is allocated word_t prologue_footer = *find_prev_footer(heap_listp); assert(extract_size(prologue_footer) == 0 && extract_alloc(prologue_footer)); // check header-footer consistency block_t *block = heap_listp; if (get_size(block) != 0) { word_t block_header = block->header; word_t block_footer = *(find_prev_footer(find_next(heap_listp))); assert(extract_size(block_header) == extract_size(block_footer)); assert(extract_alloc(block_header) == extract_alloc(block_footer)); } } return true; }