malloc.c (2720B)
1 #include <malloc.h> 2 #include <string.h> 3 #include <unistd.h> 4 5 // Implementation copied from https://danluu.com/malloc-tutorial/ 6 7 struct block_meta { 8 size_t size; 9 struct block_meta *next; 10 int free; 11 }; 12 13 #define META_SIZE sizeof(struct block_meta) 14 15 void *global_base = NULL; 16 17 struct block_meta *find_free_block(struct block_meta **last, size_t size) { 18 struct block_meta *current = global_base; 19 while (current && !(current->free && current->size >= size)) { 20 *last = current; 21 current = current->next; 22 } 23 return current; 24 } 25 26 struct block_meta *request_space(struct block_meta* last, size_t size) { 27 struct block_meta *block; 28 block = sbrk(0); 29 void *request = sbrk(size + META_SIZE); 30 // assert((void*)block == request); // Not thread safe. 31 if (request == (void*) -1) { 32 return NULL; // sbrk failed. 33 } 34 35 if (last) { // NULL on first request. 36 last->next = block; 37 } 38 block->size = size; 39 block->next = NULL; 40 block->free = 0; 41 return block; 42 } 43 44 45 void *malloc(size_t size) { 46 struct block_meta *block; 47 // TODO: align size? 48 49 if (size <= 0) { 50 return NULL; 51 } 52 53 if (!global_base) { // First call. 54 block = request_space(NULL, size); 55 if (!block) { 56 return NULL; 57 } 58 global_base = block; 59 } else { 60 struct block_meta *last = global_base; 61 block = find_free_block(&last, size); 62 if (!block) { // Failed to find free block. 63 block = request_space(last, size); 64 if (!block) { 65 return NULL; 66 } 67 } else { // Found free block 68 // TODO: consider splitting block here. 69 block->free = 0; 70 } 71 } 72 73 return(block+1); 74 } 75 76 struct block_meta *get_block_ptr(void *ptr) { 77 return (struct block_meta*)ptr - 1; 78 } 79 80 void free(void *ptr) { 81 if (!ptr) { 82 return; 83 } 84 85 // TODO: consider merging blocks once splitting blocks is implemented. 86 struct block_meta* block_ptr = get_block_ptr(ptr); 87 // assert(block_ptr->free == 0); 88 block_ptr->free = 1; 89 } 90 91 void *realloc(void *ptr, size_t size) { 92 if (!ptr) { 93 // NULL ptr. realloc should act like malloc. 94 return malloc(size); 95 } 96 97 struct block_meta* block_ptr = get_block_ptr(ptr); 98 if (block_ptr->size >= size) { 99 // We have enough space. Could free some once we implement split. 100 return ptr; 101 } 102 103 // Need to really realloc. Malloc new space and free old space. 104 // Then copy old data to new space. 105 void *new_ptr; 106 new_ptr = malloc(size); 107 if (!new_ptr) { 108 return NULL; // TODO: set errno on failure. 109 } 110 memcpy(new_ptr, ptr, block_ptr->size); 111 free(ptr); 112 return new_ptr; 113 } 114 115 void *calloc(size_t nelem, size_t elsize) { 116 size_t size = nelem * elsize; // TODO: check for overflow. 117 void *ptr = malloc(size); 118 memset(ptr, 0, size); 119 return ptr; 120 }