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