1 /* 2 * malloc.c 3 * 4 * Very simple linked-list based malloc()/free(). 5 */ 6 7 #include <stdlib.h> 8 #include <string.h> 9 #include "malloc.h" 10 11 struct free_arena_header __malloc_head = { 12 { 13 ARENA_TYPE_HEAD, 14 0, 15 &__malloc_head, 16 &__malloc_head, 17 }, 18 &__malloc_head, 19 &__malloc_head 20 }; 21 22 extern void *__mem_end; /* In argv.c */ 23 24 void __init_memory_arena(void) 25 { 26 extern char __heap_end[]; 27 struct free_arena_header *fp; 28 29 fp = (struct free_arena_header *)__mem_end; 30 fp->a.type = ARENA_TYPE_FREE; 31 fp->a.size = __heap_end - (char *)__mem_end; 32 33 /* Insert into chains */ 34 fp->a.next = fp->a.prev = &__malloc_head; 35 fp->next_free = fp->prev_free = &__malloc_head; 36 __malloc_head.a.next = __malloc_head.a.prev = fp; 37 __malloc_head.next_free = __malloc_head.prev_free = fp; 38 } 39 40 static void *__malloc_from_block(struct free_arena_header *fp, size_t size) 41 { 42 size_t fsize; 43 struct free_arena_header *nfp, *na; 44 45 fsize = fp->a.size; 46 47 /* We need the 2* to account for the larger requirements of a free block */ 48 if (fsize >= size + 2 * sizeof(struct arena_header)) { 49 /* Bigger block than required -- split block */ 50 nfp = (struct free_arena_header *)((char *)fp + size); 51 na = fp->a.next; 52 53 nfp->a.type = ARENA_TYPE_FREE; 54 nfp->a.size = fsize - size; 55 fp->a.type = ARENA_TYPE_USED; 56 fp->a.size = size; 57 58 /* Insert into all-block chain */ 59 nfp->a.prev = fp; 60 nfp->a.next = na; 61 na->a.prev = nfp; 62 fp->a.next = nfp; 63 64 /* Replace current block on free chain */ 65 nfp->next_free = fp->next_free; 66 nfp->prev_free = fp->prev_free; 67 fp->next_free->prev_free = nfp; 68 fp->prev_free->next_free = nfp; 69 } else { 70 /* Allocate the whole block */ 71 fp->a.type = ARENA_TYPE_USED; 72 73 /* Remove from free chain */ 74 fp->next_free->prev_free = fp->prev_free; 75 fp->prev_free->next_free = fp->next_free; 76 } 77 78 return (void *)(&fp->a + 1); 79 } 80 81 void *malloc(size_t size) 82 { 83 struct free_arena_header *fp; 84 85 if (size == 0) 86 return NULL; 87 88 /* Add the obligatory arena header, and round up */ 89 size = (size + 2 * sizeof(struct arena_header) - 1) & ~ARENA_SIZE_MASK; 90 91 for (fp = __malloc_head.next_free; fp->a.type != ARENA_TYPE_HEAD; 92 fp = fp->next_free) { 93 if (fp->a.size >= size) { 94 /* Found fit -- allocate out of this block */ 95 return __malloc_from_block(fp, size); 96 } 97 } 98 99 /* Nothing found... need to request a block from the kernel */ 100 return NULL; /* No kernel to get stuff from */ 101 } 102 103 void *calloc(size_t nmemb, size_t size) 104 { 105 void *p; 106 size *= nmemb; 107 p = malloc(size); 108 if (p) 109 memset(p, 0, size); 110 return p; 111 } 112
