malloc.c (3029B)
1 #include <stdint.h> 2 #include <stdlib.h> 3 #include <string.h> 4 5 #include "malloc.h" 6 #include "syscall.h" 7 8 #define MAXADDR ((char *)-1) 9 #define ERRADDR ((char *)-1) 10 11 extern char end[]; 12 static Header base = { .h.next = &base }; 13 static Header *freep = &base; 14 static char *heap = end; 15 16 /* 17 * Run over the free list looking for the nearest previous 18 * block. There are two possible results: end of the list 19 * or an intermediary block. 20 */ 21 void * 22 _prevchunk(Header *hp) 23 { 24 Header *p; 25 26 for (p = freep; ;p = p->h.next) { 27 /* hp between p and p->h.next? */ 28 if (p < hp && hp < p->h.next) 29 break; 30 /* p before hp and hp at the end of list? */ 31 if (p->h.next <= p && (hp < p->h.next || hp > p)) 32 break; 33 } 34 return p; 35 } 36 37 /* 38 * Get the previous block and try to merge 39 * with next and previous blocks 40 */ 41 void 42 free(void *mem) 43 { 44 Header *hp, *prev; 45 46 if (!mem) 47 return; 48 49 hp = (Header *) mem - 1; 50 prev = _prevchunk(hp); 51 52 /* join to next */ 53 if (hp + hp->h.size == prev->h.next) { 54 hp->h.size += prev->h.next->h.size; 55 hp->h.next = prev->h.next->h.next; 56 } else { 57 hp->h.next = prev->h.next; 58 } 59 60 /* join to previous */ 61 if (prev + prev->h.size == hp) { 62 prev->h.size += hp->h.size; 63 prev->h.next = hp->h.next; 64 } else { 65 prev->h.next = hp; 66 } 67 68 freep = prev; 69 } 70 71 static void * 72 sbrk(uintptr_t inc) 73 { 74 char *new, *old = heap; 75 76 if (old >= MAXADDR - inc) 77 return ERRADDR; 78 79 new = old + inc; 80 if (_brk(new) < 0) 81 return ERRADDR; 82 heap = new; 83 84 return old; 85 } 86 87 static Header * 88 morecore(size_t nunits) 89 { 90 char *rawmem; 91 Header *hp; 92 93 if (nunits < NALLOC) 94 nunits = NALLOC; 95 96 rawmem = sbrk(nunits * sizeof(Header)); 97 if (rawmem == ERRADDR) 98 return NULL; 99 100 hp = (Header*)rawmem; 101 hp->h.size = nunits; 102 103 /* integrate new memory into the list */ 104 free(hp + 1); 105 106 return freep; 107 } 108 109 /* 110 * Run over the list of free blocks trying to find a block 111 * big enough for nbytes. If the block fit perfectly with 112 * the required size then we only have to unlink 113 * the block. Otherwise we have to split the block and 114 * return the right part. If we run over the full list 115 * without a fit then we have to require more memory 116 * 117 * ______________________________________ 118 * ___________./______________________________________\_____ 119 * ...| in | | | in | |.....| in | | | |.... 120 * ...| use | | | use | |.....| use | | | |.... 121 * ___|______|___|.____|_____|._|_____|______|._|.___|.|____ 122 * \__/ \_________/ \_____________/ \/ \__/ 123 */ 124 void * 125 malloc(size_t nbytes) 126 { 127 Header *cur, *prev; 128 size_t nunits; 129 130 /* 1 unit for header plus enough units to fit nbytes */ 131 nunits = (nbytes+sizeof(Header)-1) / sizeof(Header) + 1; 132 133 for (prev = freep; ; prev = cur) { 134 cur = prev->h.next; 135 if (cur->h.size >= nunits) { 136 if (cur->h.size == nunits) { 137 prev->h.next = cur->h.next; 138 } else { 139 cur->h.size -= nunits; 140 cur += cur->h.size; 141 cur->h.size = nunits; 142 } 143 freep = prev; 144 return cur + 1; 145 } 146 147 if (cur == freep) { 148 if ((cur = morecore(nunits)) == NULL) 149 return NULL; 150 } 151 } 152 }