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