1 /* $NetBSD: alloc.c,v 1.3 1997/07/20 17:41:59 christos Exp $ */ 2 3 /* 4 * area-based allocation built on malloc/free 5 */ 6 7 #include "sh.h" 8 #ifdef MEM_DEBUG 9 # undef alloc 10 # undef aresize 11 # undef afree 12 #endif /* MEM_DEBUG */ 13 14 #define ICELLS 100 /* number of Cells in small Block */ 15 16 typedef union Cell Cell; 17 typedef struct Block Block; 18 19 /* 20 * The Cells in a Block are organized as a set of objects. 21 * Each object (pointed to by dp) begins with a size in (dp-1)->size, 22 * followed with "size" data Cells. Free objects are 23 * linked together via dp->next. 24 */ 25 26 union Cell { 27 size_t size; 28 Cell *next; 29 struct {int _;} junk; /* alignment */ 30 }; 31 32 struct Block { 33 Block *next; /* list of Blocks in Area */ 34 Cell *freelist; /* object free list */ 35 Cell *last; /* &b.cell[size] */ 36 Cell cell [1]; /* [size] Cells for allocation */ 37 }; 38 39 static Block aempty = {&aempty, aempty.cell, aempty.cell}; 40 41 /* create empty Area */ 42 Area * 43 ainit(ap) 44 register Area *ap; 45 { 46 ap->freelist = &aempty; 47 return ap; 48 } 49 50 /* free all object in Area */ 51 void 52 afreeall(ap) 53 register Area *ap; 54 { 55 register Block *bp; 56 register Block *tmp; 57 58 bp = ap->freelist; 59 if (bp != NULL && bp != &aempty) { 60 do { 61 tmp = bp->next; 62 free((void*)bp); 63 bp = tmp; 64 } while (bp != ap->freelist); 65 ap->freelist = &aempty; 66 } 67 } 68 69 /* allocate object from Area */ 70 void * 71 alloc(size, ap) 72 size_t size; 73 register Area *ap; 74 { 75 int cells, split; 76 register Block *bp; 77 register Cell *dp, *fp, *fpp; 78 79 if (size <= 0) { 80 aerror(ap, "allocate bad size"); 81 return NULL; 82 } 83 cells = (unsigned)(size - 1) / sizeof(Cell) + 1; 84 85 /* find Cell large enough */ 86 for (bp = ap->freelist; ; bp = bp->next) { 87 for (fpp = NULL, fp = bp->freelist; 88 fp != bp->last; fpp = fp, fp = fpp->next) 89 if ((fp-1)->size >= cells) 90 goto Found; 91 92 /* wrapped around Block list, create new Block */ 93 if (bp->next == ap->freelist) { 94 bp = (Block*) malloc(offsetof(Block, cell[ICELLS]) 95 + sizeof(bp->cell[0]) * cells); 96 if (bp == NULL) { 97 aerror(ap, "cannot allocate"); 98 return NULL; 99 } 100 if (ap->freelist == &aempty) 101 bp->next = bp; 102 else { 103 bp->next = ap->freelist->next; 104 ap->freelist->next = bp; 105 } 106 bp->last = bp->cell + ICELLS + cells; 107 fp = bp->freelist = bp->cell + 1; /* initial free list */ 108 (fp-1)->size = ICELLS + cells - 1; 109 fp->next = bp->last; 110 fpp = NULL; 111 break; 112 } 113 } 114 Found: 115 ap->freelist = bp; 116 dp = fp; /* allocated object */ 117 split = (dp-1)->size - cells; 118 if (split < 0) 119 aerror(ap, "allocated object too small"); 120 if (--split <= 0) { /* allocate all */ 121 fp = fp->next; 122 } else { /* allocate head, free tail */ 123 (fp-1)->size = cells; 124 fp += cells + 1; 125 (fp-1)->size = split; 126 fp->next = dp->next; 127 } 128 if (fpp == NULL) 129 bp->freelist = fp; 130 else 131 fpp->next = fp; 132 return (void*) dp; 133 } 134 135 /* change size of object -- like realloc */ 136 void * 137 aresize(ptr, size, ap) 138 register void *ptr; 139 size_t size; 140 Area *ap; 141 { 142 int cells; 143 register Cell *dp = (Cell*) ptr; 144 145 if (size <= 0) { 146 aerror(ap, "allocate bad size"); 147 return NULL; 148 } 149 cells = (unsigned)(size - 1) / sizeof(Cell) + 1; 150 151 if (dp == NULL || (dp-1)->size < cells) { /* enlarge object */ 152 /* XXX check for available adjacent free block */ 153 ptr = alloc(size, ap); 154 if (dp != NULL) { 155 memcpy(ptr, dp, (dp-1)->size * sizeof(Cell)); 156 afree((void *) dp, ap); 157 } 158 } else { /* shrink object */ 159 int split; 160 161 split = (dp-1)->size - cells; 162 if (--split <= 0) /* cannot split */ 163 ; 164 else { /* shrink head, free tail */ 165 (dp-1)->size = cells; 166 dp += cells + 1; 167 (dp-1)->size = split; 168 afree((void*)dp, ap); 169 } 170 } 171 return (void*) ptr; 172 } 173 174 void 175 afree(ptr, ap) 176 void *ptr; 177 register Area *ap; 178 { 179 register Block *bp; 180 register Cell *fp, *fpp; 181 register Cell *dp = (Cell*)ptr; 182 183 /* find Block containing Cell */ 184 for (bp = ap->freelist; ; bp = bp->next) { 185 if (bp->cell <= dp && dp < bp->last) 186 break; 187 if (bp->next == ap->freelist) { 188 aerror(ap, "freeing with invalid area"); 189 return; 190 } 191 } 192 193 /* find position in free list */ 194 for (fpp = NULL, fp = bp->freelist; fp < dp; fpp = fp, fp = fpp->next) 195 ; 196 197 if (fp == dp) { 198 aerror(ap, "freeing free object"); 199 return; 200 } 201 202 /* join object with next */ 203 if (dp + (dp-1)->size == fp-1) { /* adjacent */ 204 (dp-1)->size += (fp-1)->size + 1; 205 dp->next = fp->next; 206 } else /* non-adjacent */ 207 dp->next = fp; 208 209 /* join previous with object */ 210 if (fpp == NULL) 211 bp->freelist = dp; 212 else if (fpp + (fpp-1)->size == dp-1) { /* adjacent */ 213 (fpp-1)->size += (dp-1)->size + 1; 214 fpp->next = dp->next; 215 } else /* non-adjacent */ 216 fpp->next = dp; 217 } 218 219 #if DEBUG_ALLOC 220 void 221 aprint(ap, ptr, size) 222 register Area *ap; 223 void *ptr; 224 size_t size; 225 { 226 Block *bp; 227 228 if (!ap) 229 shellf("aprint: null area pointer\n"); 230 else if (!(bp = ap->freelist)) 231 shellf("aprint: null area freelist\n"); 232 else if (bp == &aempty) 233 shellf("aprint: area is empty\n"); 234 else { 235 int i; 236 Cell *fp; 237 238 for (i = 0; !i || bp != ap->freelist; bp = bp->next, i++) { 239 if (ptr) { 240 void *eptr = (void *) (((char *) ptr) + size); 241 /* print block only if it overlaps ptr/size */ 242 if (!((ptr >= (void *) bp 243 && ptr <= (void *) bp->last) 244 || (eptr >= (void *) bp 245 && eptr <= (void *) bp->last))) 246 continue; 247 shellf("aprint: overlap of 0x%p .. 0x%p\n", 248 ptr, eptr); 249 } 250 shellf("aprint: block %2d: 0x%p .. 0x%p (%d)\n", i, 251 bp->cell, bp->last, 252 (char *) bp->last - (char *) bp->cell); 253 for (fp = bp->freelist; fp != bp->last; fp = fp->next) 254 shellf( 255 "aprint: 0x%p .. 0x%p (%d) free\n", 256 (fp-1), (fp-1) + (fp-1)->size, 257 (fp-1)->size * sizeof(Cell)); 258 } 259 } 260 } 261 #endif /* DEBUG_ALLOC */ 262 263 264 #ifdef TEST_ALLOC 265 266 Area a; 267 268 main(int argc, char **argv) { 269 int i; 270 char *p [9]; 271 272 ainit(&a); 273 for (i = 0; i < 9; i++) { 274 p[i] = alloc(124, &a); 275 printf("alloc: %x\n", p[i]); 276 } 277 for (i = 1; i < argc; i++) 278 afree(p[atoi(argv[i])], &a); 279 afreeall(&a); 280 return 0; 281 } 282 283 void aerror(Area *ap, const char *msg) { 284 abort(); 285 } 286 287 #endif 288 289