| 0,0 → 1,440 |
|---|
| /* |
| * 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; |
| } |
| |