1 /* 2 * area-based allocation built on malloc/free 3 */ 4 5 #include "sh.h" 6 7 8 9 # if DEBUG_ALLOC 10 void acheck ARGS((Area *ap)); 11 # define ACHECK(ap) acheck(ap) 12 # else /* DEBUG_ALLOC */ 13 # define ACHECK(ap) 14 # endif /* DEBUG_ALLOC */ 15 16 #define ICELLS 200 /* number of Cells in small Block */ 17 18 typedef union Cell Cell; 19 typedef struct Block Block; 20 21 /* 22 * The Cells in a Block are organized as a set of objects. 23 * Each object (pointed to by dp) begins with the block it is in 24 * (dp-2)->block, then has a size in (dp-1)->size, which is 25 * followed with "size" data Cells. Free objects are 26 * linked together via dp->next. 27 */ 28 29 #define NOBJECT_FIELDS 2 /* the block and size `fields' */ 30 31 union Cell { 32 size_t size; 33 Cell *next; 34 Block *block; 35 struct {int _;} junk; /* alignment */ 36 double djunk; /* alignment */ 37 }; 38 39 struct Block { 40 Block *next; /* list of Blocks in Area */ 41 Block *prev; /* previous block in list */ 42 Cell *freelist; /* object free list */ 43 Cell *last; /* &b.cell[size] */ 44 Cell cell [1]; /* [size] Cells for allocation */ 45 }; 46 47 static Block aempty = {&aempty, &aempty, aempty.cell, aempty.cell}; 48 49 static void ablockfree ARGS((Block *bp, Area *ap)); 50 static void *asplit ARGS((Area *ap, Block *bp, Cell *fp, Cell *fpp, int cells)); 51 52 /* create empty Area */ 53 Area * 54 ainit(ap) 55 register Area *ap; 56 { 57 ap->freelist = &aempty; 58 ACHECK(ap); 59 return ap; 60 } 61 62 /* free all object in Area */ 63 void 64 afreeall(ap) 65 register Area *ap; 66 { 67 register Block *bp; 68 register Block *tmp; 69 70 ACHECK(ap); 71 bp = ap->freelist; 72 if (bp != NULL && bp != &aempty) { 73 do { 74 tmp = bp; 75 bp = bp->next; 76 free((void*)tmp); 77 } while (bp != ap->freelist); 78 ap->freelist = &aempty; 79 } 80 ACHECK(ap); 81 } 82 83 /* allocate object from Area */ 84 void * 85 alloc(size, ap) 86 size_t size; 87 register Area *ap; 88 { 89 int cells, acells; 90 Block *bp = 0; 91 Cell *fp = 0, *fpp = 0; 92 93 ACHECK(ap); 94 if (size <= 0) 95 aerror(ap, "allocate bad size"); 96 cells = (unsigned)(size + sizeof(Cell) - 1) / sizeof(Cell); 97 98 /* allocate at least this many cells */ 99 acells = cells + NOBJECT_FIELDS; 100 101 /* 102 * Only attempt to track small objects - let malloc deal 103 * with larger objects. (this way we don't have to deal with 104 * coalescing memory, or with releasing it to the system) 105 */ 106 if (cells <= ICELLS) { 107 /* find free Cell large enough */ 108 for (bp = ap->freelist; ; bp = bp->next) { 109 for (fpp = NULL, fp = bp->freelist; 110 fp != bp->last; fpp = fp, fp = fp->next) 111 { 112 if ((fp-1)->size >= cells) 113 goto Found; 114 } 115 /* wrapped around Block list, create new Block */ 116 if (bp->next == ap->freelist) { 117 bp = 0; 118 break; 119 } 120 } 121 /* Not much free space left? Allocate a big object this time */ 122 acells += ICELLS; 123 } 124 if (bp == 0) { 125 bp = (Block*) malloc(offsetof(Block, cell[acells])); 126 if (bp == NULL) 127 aerror(ap, "cannot allocate"); 128 if (ap->freelist == &aempty) { 129 ap->freelist = bp->next = bp->prev = bp; 130 } else { 131 bp->next = ap->freelist->next; 132 ap->freelist->next->prev = bp; 133 ap->freelist->next = bp; 134 bp->prev = ap->freelist; 135 } 136 bp->last = bp->cell + acells; 137 /* initial free list */ 138 fp = bp->freelist = bp->cell + NOBJECT_FIELDS; 139 (fp-1)->size = acells - NOBJECT_FIELDS; 140 (fp-2)->block = bp; 141 fp->next = bp->last; 142 fpp = NULL; 143 } 144 145 Found: 146 return asplit(ap, bp, fp, fpp, cells); 147 } 148 149 /* Do the work of splitting an object into allocated and (possibly) unallocated 150 * objects. Returns the `allocated' object. 151 */ 152 static void * 153 asplit(ap, bp, fp, fpp, cells) 154 Area *ap; 155 Block *bp; 156 Cell *fp; 157 Cell *fpp; 158 int cells; 159 { 160 Cell *dp = fp; /* allocated object */ 161 int split = (fp-1)->size - cells; 162 163 ACHECK(ap); 164 if (split < 0) 165 aerror(ap, "allocated object too small"); 166 if (split <= NOBJECT_FIELDS) { /* allocate all */ 167 fp = fp->next; 168 } else { /* allocate head, free tail */ 169 Cell *next = fp->next; /* needed, as cells may be 0 */ 170 ap->freelist = bp; /* next time, start looking for space here */ 171 (fp-1)->size = cells; 172 fp += cells + NOBJECT_FIELDS; 173 (fp-1)->size = split - NOBJECT_FIELDS; 174 (fp-2)->block = bp; 175 fp->next = next; 176 } 177 if (fpp == NULL) 178 bp->freelist = fp; 179 else 180 fpp->next = fp; 181 ACHECK(ap); 182 return (void*) dp; 183 } 184 185 /* change size of object -- like realloc */ 186 void * 187 aresize(ptr, size, ap) 188 register void *ptr; 189 size_t size; 190 Area *ap; 191 { 192 int cells; 193 Cell *dp = (Cell*) ptr; 194 int oldcells = dp ? (dp-1)->size : 0; 195 196 ACHECK(ap); 197 if (size <= 0) 198 aerror(ap, "allocate bad size"); 199 /* New size (in cells) */ 200 cells = (unsigned)(size - 1) / sizeof(Cell) + 1; 201 202 /* Is this a large object? If so, let malloc deal with it 203 * directly (unless we are crossing the ICELLS border, in 204 * which case the alloc/free below handles it - this should 205 * cut down on fragmentation, and will also keep the code 206 * working (as it assumes size < ICELLS means it is not 207 * a `large object'). 208 */ 209 if (oldcells > ICELLS && cells > ICELLS) { 210 Block *bp = (dp-2)->block; 211 Block *nbp; 212 /* Saved in case realloc fails.. */ 213 Block *next = bp->next, *prev = bp->prev; 214 215 if (bp->freelist != bp->last) 216 aerror(ap, "allocation resizing free pointer"); 217 nbp = realloc((void *) bp, 218 offsetof(Block, cell[cells + NOBJECT_FIELDS])); 219 if (!nbp) { 220 /* Have to clean up... */ 221 /* NOTE: If this code changes, similar changes may be 222 * needed in ablockfree(). 223 */ 224 if (next == bp) /* only block */ 225 ap->freelist = &aempty; 226 else { 227 next->prev = prev; 228 prev->next = next; 229 if (ap->freelist == bp) 230 ap->freelist = next; 231 } 232 aerror(ap, "cannot re-allocate"); 233 } 234 /* If location changed, keep pointers straight... */ 235 if (nbp != bp) { 236 if (next == bp) /* only one block */ 237 nbp->next = nbp->prev = nbp; 238 else { 239 next->prev = nbp; 240 prev->next = nbp; 241 } 242 if (ap->freelist == bp) 243 ap->freelist = nbp; 244 dp = nbp->cell + NOBJECT_FIELDS; 245 (dp-2)->block = nbp; 246 } 247 (dp-1)->size = cells; 248 nbp->last = nbp->cell + cells + NOBJECT_FIELDS; 249 nbp->freelist = nbp->last; 250 251 ACHECK(ap); 252 return (void*) dp; 253 } 254 255 /* Check if we can just grow this cell 256 * (need to check that cells < ICELLS so we don't make an 257 * object a `large' - that would mess everything up). 258 */ 259 if (dp && cells > oldcells && cells <= ICELLS) { 260 Cell *fp, *fpp; 261 Block *bp = (dp-2)->block; 262 int need = cells - oldcells - NOBJECT_FIELDS; 263 264 /* XXX if we had a flag in an object indicating 265 * if the object was free/allocated, we could 266 * avoid this loop (perhaps) 267 */ 268 for (fpp = NULL, fp = bp->freelist; 269 fp != bp->last 270 && dp + oldcells + NOBJECT_FIELDS <= fp 271 ; fpp = fp, fp = fp->next) 272 { 273 if (dp + oldcells + NOBJECT_FIELDS == fp 274 && (fp-1)->size >= need) 275 { 276 Cell *np = asplit(ap, bp, fp, fpp, need); 277 /* May get more than we need here */ 278 (dp-1)->size += (np-1)->size + NOBJECT_FIELDS; 279 ACHECK(ap); 280 return ptr; 281 } 282 } 283 } 284 285 /* Check if we can just shrink this cell 286 * (if oldcells > ICELLS, this is a large object and we leave 287 * it to malloc...) 288 * Note: this also handles cells == oldcells (a no-op). 289 */ 290 if (dp && cells <= oldcells && oldcells <= ICELLS) { 291 int split; 292 293 split = oldcells - cells; 294 if (split <= NOBJECT_FIELDS) /* cannot split */ 295 ; 296 else { /* shrink head, free tail */ 297 Block *bp = (dp-2)->block; 298 299 (dp-1)->size = cells; 300 dp += cells + NOBJECT_FIELDS; 301 (dp-1)->size = split - NOBJECT_FIELDS; 302 (dp-2)->block = bp; 303 afree((void*)dp, ap); 304 } 305 /* ACHECK() done in afree() */ 306 return ptr; 307 } 308 309 /* Have to do it the hard way... */ 310 ptr = alloc(size, ap); 311 if (dp != NULL) { 312 size_t s = (dp-1)->size * sizeof(Cell); 313 if (s > size) 314 s = size; 315 memcpy(ptr, dp, s); 316 afree((void *) dp, ap); 317 } 318 /* ACHECK() done in alloc()/afree() */ 319 return ptr; 320 } 321 322 void 323 afree(ptr, ap) 324 void *ptr; 325 register Area *ap; 326 { 327 register Block *bp; 328 register Cell *fp, *fpp; 329 register Cell *dp = (Cell*)ptr; 330 331 ACHECK(ap); 332 if (ptr == 0) 333 aerror(ap, "freeing null pointer"); 334 bp = (dp-2)->block; 335 336 /* If this is a large object, just free it up... */ 337 /* Release object... */ 338 if ((dp-1)->size > ICELLS) { 339 ablockfree(bp, ap); 340 ACHECK(ap); 341 return; 342 } 343 344 if (dp < &bp->cell[NOBJECT_FIELDS] || dp >= bp->last) 345 aerror(ap, "freeing memory outside of block (corrupted?)"); 346 347 /* find position in free list */ 348 /* XXX if we had prev/next pointers for objects, this loop could go */ 349 for (fpp = NULL, fp = bp->freelist; fp < dp; fpp = fp, fp = fp->next) 350 ; 351 352 if (fp == dp) 353 aerror(ap, "freeing free object"); 354 355 /* join object with next */ 356 if (dp + (dp-1)->size == fp-NOBJECT_FIELDS) { /* adjacent */ 357 (dp-1)->size += (fp-1)->size + NOBJECT_FIELDS; 358 dp->next = fp->next; 359 } else /* non-adjacent */ 360 dp->next = fp; 361 362 /* join previous with object */ 363 if (fpp == NULL) 364 bp->freelist = dp; 365 else if (fpp + (fpp-1)->size == dp-NOBJECT_FIELDS) { /* adjacent */ 366 (fpp-1)->size += (dp-1)->size + NOBJECT_FIELDS; 367 fpp->next = dp->next; 368 } else /* non-adjacent */ 369 fpp->next = dp; 370 371 /* If whole block is free (and we have some other blocks 372 * around), release this block back to the system... 373 */ 374 if (bp->next != bp && bp->freelist == bp->cell + NOBJECT_FIELDS 375 && bp->freelist + (bp->freelist-1)->size == bp->last 376 /* XXX and the other block has some free memory? */ 377 ) 378 ablockfree(bp, ap); 379 ACHECK(ap); 380 } 381 382 static void 383 ablockfree(bp, ap) 384 Block *bp; 385 Area *ap; 386 { 387 /* NOTE: If this code changes, similar changes may be 388 * needed in alloc() (where realloc fails). 389 */ 390 391 if (bp->next == bp) /* only block */ 392 ap->freelist = &aempty; 393 else { 394 bp->next->prev = bp->prev; 395 bp->prev->next = bp->next; 396 if (ap->freelist == bp) 397 ap->freelist = bp->next; 398 } 399 free((void*) bp); 400 } 401 402 # if DEBUG_ALLOC 403 void 404 acheck(ap) 405 Area *ap; 406 { 407 Block *bp, *bpp; 408 Cell *dp, *dptmp, *fp; 409 int ok = 1; 410 int isfree; 411 static int disabled; 412 413 if (disabled) 414 return; 415 416 if (!ap) { 417 disabled = 1; 418 aerror(ap, "acheck: null area pointer"); 419 } 420 421 bp = ap->freelist; 422 if (!bp) { 423 disabled = 1; 424 aerror(ap, "acheck: null area freelist"); 425 } 426 427 /* Nothing to check... */ 428 if (bp == &aempty) 429 return; 430 431 bpp = ap->freelist->prev; 432 while (1) { 433 if (bp->prev != bpp) { 434 shellf("acheck: bp->prev != previous\n"); 435 ok = 0; 436 } 437 fp = bp->freelist; 438 for (dp = &bp->cell[NOBJECT_FIELDS]; dp != bp->last; ) { 439 if ((dp-2)->block != bp) { 440 shellf("acheck: fragment's block is wrong\n"); 441 ok = 0; 442 } 443 isfree = dp == fp; 444 if ((dp-1)->size == 0 && isfree) { 445 shellf("acheck: 0 size frag\n"); 446 ok = 0; 447 } 448 if ((dp-1)->size > ICELLS 449 && !isfree 450 && (dp != &bp->cell[NOBJECT_FIELDS] 451 || dp + (dp-1)->size != bp->last)) 452 { 453 shellf("acheck: big cell doesn't make up whole block\n"); 454 ok = 0; 455 } 456 if (isfree) { 457 if (dp->next <= dp) { 458 shellf("acheck: free fragment's next <= self\n"); 459 ok = 0; 460 } 461 if (dp->next > bp->last) { 462 shellf("acheck: free fragment's next > last\n"); 463 ok = 0; 464 } 465 fp = dp->next; 466 } 467 dptmp = dp + (dp-1)->size; 468 if (dptmp > bp->last) { 469 shellf("acheck: next frag out of range\n"); 470 ok = 0; 471 break; 472 } else if (dptmp != bp->last) { 473 dptmp += NOBJECT_FIELDS; 474 if (dptmp > bp->last) { 475 shellf("acheck: next frag just out of range\n"); 476 ok = 0; 477 break; 478 } 479 } 480 if (isfree && dptmp == fp && dptmp != bp->last) { 481 shellf("acheck: adjacent free frags\n"); 482 ok = 0; 483 } else if (dptmp > fp) { 484 shellf("acheck: free frag list messed up\n"); 485 ok = 0; 486 } 487 dp = dptmp; 488 } 489 bpp = bp; 490 bp = bp->next; 491 if (bp == ap->freelist) 492 break; 493 } 494 if (!ok) { 495 disabled = 1; 496 aerror(ap, "acheck failed"); 497 } 498 } 499 500 void 501 aprint(ap, ptr, size) 502 register Area *ap; 503 void *ptr; 504 size_t size; 505 { 506 Block *bp; 507 508 if (!ap) 509 shellf("aprint: null area pointer\n"); 510 else if (!(bp = ap->freelist)) 511 shellf("aprint: null area freelist\n"); 512 else if (bp == &aempty) 513 shellf("aprint: area is empty\n"); 514 else { 515 int i; 516 Cell *dp, *fp; 517 Block *bpp; 518 519 bpp = ap->freelist->prev; 520 for (i = 0; ; i++) { 521 if (ptr) { 522 void *eptr = (void *) (((char *) ptr) + size); 523 /* print block only if it overlaps ptr/size */ 524 if (!((ptr >= (void *) bp 525 && ptr <= (void *) bp->last) 526 || (eptr >= (void *) bp 527 && eptr <= (void *) bp->last))) 528 continue; 529 shellf("aprint: overlap of 0x%p .. 0x%p\n", 530 ptr, eptr); 531 } 532 if (bp->prev != bpp || bp->next->prev != bp) 533 shellf( 534 "aprint: BAD prev pointer: bp %p, bp->prev %p, bp->next %p, bpp=%p\n", 535 bp, bp->prev, bp->next, bpp); 536 shellf("aprint: block %2d (p=%p,%p,n=%p): 0x%p .. 0x%p (%ld)\n", i, 537 bp->prev, bp, bp->next, 538 bp->cell, bp->last, 539 (long) ((char *) bp->last - (char *) bp->cell)); 540 fp = bp->freelist; 541 if (bp->last <= bp->cell + NOBJECT_FIELDS) 542 shellf( 543 "aprint: BAD bp->last too small: %p <= %p\n", 544 bp->last, bp->cell + NOBJECT_FIELDS); 545 if (bp->freelist < bp->cell + NOBJECT_FIELDS 546 || bp->freelist > bp->last) 547 shellf( 548 "aprint: BAD bp->freelist %p out of range: %p .. %p\n", 549 bp->freelist, 550 bp->cell + NOBJECT_FIELDS, bp->last); 551 for (dp = bp->cell; dp != bp->last ; ) { 552 dp += NOBJECT_FIELDS; 553 shellf( 554 "aprint: 0x%p .. 0x%p (%ld) %s\n", 555 (dp-NOBJECT_FIELDS), 556 (dp-NOBJECT_FIELDS) + (dp-1)->size 557 + NOBJECT_FIELDS, 558 (long) ((dp-1)->size + NOBJECT_FIELDS) 559 * sizeof(Cell), 560 dp == fp ? "free" : "allocated"); 561 if ((dp-2)->block != bp) 562 shellf( 563 "aprint: BAD dp->block %p != bp %p\n", 564 (dp-2)->block, bp); 565 if (dp > bp->last) 566 shellf( 567 "aprint: BAD dp gone past block: %p > %p\n", 568 dp, bp->last); 569 if (dp > fp) 570 shellf( 571 "aprint: BAD dp gone past free: %p > %p\n", 572 dp, fp); 573 if (dp == fp) { 574 fp = fp->next; 575 if (fp < dp || fp > bp->last) 576 shellf( 577 "aprint: BAD free object %p out of range: %p .. %p\n", 578 fp, 579 dp, bp->last); 580 } 581 dp += (dp-1)->size; 582 } 583 bpp = bp; 584 bp = bp->next; 585 if (bp == ap->freelist) 586 break; 587 } 588 } 589 } 590 591 #endif 592