memory.c (3280B)
1 #include "memory.h" 2 3 #include <pthread.h> 4 #include <stdio.h> 5 #include <unistd.h> 6 7 // An allocation header block. 8 // 9 // Allocation header blocks sit immediately before the allocated pointer in 10 // memory and form a linked list staring at |head| and ending at |tail|. 11 struct header_t { 12 size_t size; 13 struct header_t *next; 14 unsigned char is_free; 15 }; 16 17 static struct header_t *head, *tail; 18 static pthread_mutex_t global_malloc_lock; 19 20 // Returns the first free block of at least the specified size, or null if 21 // no such block exists. 22 static struct header_t *get_free_block(size_t size); 23 24 // Print header struct debug dump. 25 void print_header(struct header_t *header); 26 27 static struct header_t *get_free_block(size_t size) { 28 struct header_t *curr = head; 29 while (curr) { 30 if (curr->is_free && curr->size >= size) 31 return curr; 32 curr = curr->next; 33 } 34 return NULL; 35 } 36 37 void *malloc(size_t size) { 38 size_t total_size; 39 void *block; 40 struct header_t *header; 41 42 if (!size) 43 return NULL; 44 45 // Check for free previously-allocated block of the right size. 46 pthread_mutex_lock(&global_malloc_lock); 47 header = get_free_block(size); 48 if (header) { 49 header->is_free = 0; 50 pthread_mutex_unlock(&global_malloc_lock); 51 return (void*)(header + 1); 52 } 53 54 // If none, allocate a new block. 55 total_size = sizeof(struct header_t) + size; 56 block = sbrk((int)total_size); 57 if (block == (void*)-1) { 58 pthread_mutex_unlock(&global_malloc_lock); 59 return NULL; 60 } 61 62 header = (struct header_t*)block; 63 header->size = size; 64 header->is_free = 0; 65 header->next = NULL; 66 if (!head) 67 head = header; 68 if (tail) 69 tail->next = header; 70 tail = header; 71 pthread_mutex_unlock(&global_malloc_lock); 72 return (void*)(header + 1); 73 } 74 75 void free(void *block) { 76 if (!block) 77 return; 78 79 pthread_mutex_lock(&global_malloc_lock); 80 81 // Get block header. 82 struct header_t *header = (struct header_t*)block - 1; 83 84 void *program_break = sbrk(0); 85 if ((char*)block + header->size == program_break) { 86 // If we're the last allocated block before brk, decrement it. 87 if (head == tail) { 88 head = tail = NULL; 89 } else { 90 for (struct header_t *p = head; p != NULL; p = p->next) { 91 if (p->next == tail) { 92 p->next = NULL; 93 tail = p; 94 } 95 } 96 } 97 size_t total_size = sizeof(struct header_t) + header->size; 98 sbrk(-(int)total_size); 99 pthread_mutex_unlock(&global_malloc_lock); 100 return; 101 } else { 102 // Otherwise, mark the block as free. 103 header->is_free = 1; 104 } 105 106 pthread_mutex_unlock(&global_malloc_lock); 107 } 108 109 void print_brk() { 110 void *p = sbrk(0); 111 if (p == (void*)(-1)) 112 fprintf(stderr, "sbrk() failed\n"); 113 printf("brk: %p\n", p); 114 } 115 116 void print_header(struct header_t *header) { 117 printf("hdr: %p\n", header); 118 printf("sizeof(hdr): %#zx\n", sizeof(struct header_t)); 119 if (!header) { 120 return; 121 } 122 printf("size: %#zx\n", header->size); 123 printf("free: %s\n", header->is_free ? "true" : "false"); 124 } 125 126 void print_block(void *block) { 127 printf("addr: %p\n", block); 128 if (!block) 129 return; 130 struct header_t *h = (struct header_t*)(block) - 1; 131 print_header(h); 132 } 133 134 void print_alloc_list() { 135 printf("== head\n"); 136 print_header(head); 137 printf("== tail\n"); 138 print_header(tail); 139 } 140