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