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