ref: 26d36c3ae2fd6ae40148be58589ea5e81b0ca341
dir: /sys/src/ape/cmd/pdksh/alloc.c/
/* * area-based allocation built on malloc/free */ #include "sh.h" # if DEBUG_ALLOC void acheck ARGS((Area *ap)); # define ACHECK(ap) acheck(ap) # else /* DEBUG_ALLOC */ # define ACHECK(ap) # endif /* DEBUG_ALLOC */ #define ICELLS 200 /* number of Cells in small Block */ typedef union Cell Cell; typedef struct Block Block; /* * The Cells in a Block are organized as a set of objects. * Each object (pointed to by dp) begins with the block it is in * (dp-2)->block, then has a size in (dp-1)->size, which is * followed with "size" data Cells. Free objects are * linked together via dp->next. */ #define NOBJECT_FIELDS 2 /* the block and size `fields' */ union Cell { size_t size; Cell *next; Block *block; struct {int _;} junk; /* alignment */ double djunk; /* alignment */ }; struct Block { Block *next; /* list of Blocks in Area */ Block *prev; /* previous block in list */ Cell *freelist; /* object free list */ Cell *last; /* &b.cell[size] */ Cell cell [1]; /* [size] Cells for allocation */ }; static Block aempty = {&aempty, &aempty, aempty.cell, aempty.cell}; static void ablockfree ARGS((Block *bp, Area *ap)); static void *asplit ARGS((Area *ap, Block *bp, Cell *fp, Cell *fpp, int cells)); /* create empty Area */ Area * ainit(ap) register Area *ap; { ap->freelist = &aempty; ACHECK(ap); return ap; } /* free all object in Area */ void afreeall(ap) register Area *ap; { register Block *bp; register Block *tmp; ACHECK(ap); bp = ap->freelist; if (bp != NULL && bp != &aempty) { do { tmp = bp; bp = bp->next; free((void*)tmp); } while (bp != ap->freelist); ap->freelist = &aempty; } ACHECK(ap); } /* allocate object from Area */ void * alloc(size, ap) size_t size; register Area *ap; { int cells, acells; Block *bp = 0; Cell *fp = 0, *fpp = 0; ACHECK(ap); if (size <= 0) aerror(ap, "allocate bad size"); cells = (unsigned)(size + sizeof(Cell) - 1) / sizeof(Cell); /* allocate at least this many cells */ acells = cells + NOBJECT_FIELDS; /* * Only attempt to track small objects - let malloc deal * with larger objects. (this way we don't have to deal with * coalescing memory, or with releasing it to the system) */ if (cells <= ICELLS) { /* find free Cell large enough */ for (bp = ap->freelist; ; bp = bp->next) { for (fpp = NULL, fp = bp->freelist; fp != bp->last; fpp = fp, fp = fp->next) { if ((fp-1)->size >= cells) goto Found; } /* wrapped around Block list, create new Block */ if (bp->next == ap->freelist) { bp = 0; break; } } /* Not much free space left? Allocate a big object this time */ acells += ICELLS; } if (bp == 0) { bp = (Block*) malloc(offsetof(Block, cell[acells])); if (bp == NULL) aerror(ap, "cannot allocate"); if (ap->freelist == &aempty) { ap->freelist = bp->next = bp->prev = bp; } else { bp->next = ap->freelist->next; ap->freelist->next->prev = bp; ap->freelist->next = bp; bp->prev = ap->freelist; } bp->last = bp->cell + acells; /* initial free list */ fp = bp->freelist = bp->cell + NOBJECT_FIELDS; (fp-1)->size = acells - NOBJECT_FIELDS; (fp-2)->block = bp; fp->next = bp->last; fpp = NULL; } Found: return asplit(ap, bp, fp, fpp, cells); } /* Do the work of splitting an object into allocated and (possibly) unallocated * objects. Returns the `allocated' object. */ static void * asplit(ap, bp, fp, fpp, cells) Area *ap; Block *bp; Cell *fp; Cell *fpp; int cells; { Cell *dp = fp; /* allocated object */ int split = (fp-1)->size - cells; ACHECK(ap); if (split < 0) aerror(ap, "allocated object too small"); if (split <= NOBJECT_FIELDS) { /* allocate all */ fp = fp->next; } else { /* allocate head, free tail */ Cell *next = fp->next; /* needed, as cells may be 0 */ ap->freelist = bp; /* next time, start looking for space here */ (fp-1)->size = cells; fp += cells + NOBJECT_FIELDS; (fp-1)->size = split - NOBJECT_FIELDS; (fp-2)->block = bp; fp->next = next; } if (fpp == NULL) bp->freelist = fp; else fpp->next = fp; ACHECK(ap); return (void*) dp; } /* change size of object -- like realloc */ void * aresize(ptr, size, ap) register void *ptr; size_t size; Area *ap; { int cells; Cell *dp = (Cell*) ptr; int oldcells = dp ? (dp-1)->size : 0; ACHECK(ap); if (size <= 0) aerror(ap, "allocate bad size"); /* New size (in cells) */ cells = (unsigned)(size - 1) / sizeof(Cell) + 1; /* Is this a large object? If so, let malloc deal with it * directly (unless we are crossing the ICELLS border, in * which case the alloc/free below handles it - this should * cut down on fragmentation, and will also keep the code * working (as it assumes size < ICELLS means it is not * a `large object'). */ if (oldcells > ICELLS && cells > ICELLS) { Block *bp = (dp-2)->block; Block *nbp; /* Saved in case realloc fails.. */ Block *next = bp->next, *prev = bp->prev; if (bp->freelist != bp->last) aerror(ap, "allocation resizing free pointer"); nbp = realloc((void *) bp, offsetof(Block, cell[cells + NOBJECT_FIELDS])); if (!nbp) { /* Have to clean up... */ /* NOTE: If this code changes, similar changes may be * needed in ablockfree(). */ if (next == bp) /* only block */ ap->freelist = &aempty; else { next->prev = prev; prev->next = next; if (ap->freelist == bp) ap->freelist = next; } aerror(ap, "cannot re-allocate"); } /* If location changed, keep pointers straight... */ if (nbp != bp) { if (next == bp) /* only one block */ nbp->next = nbp->prev = nbp; else { next->prev = nbp; prev->next = nbp; } if (ap->freelist == bp) ap->freelist = nbp; dp = nbp->cell + NOBJECT_FIELDS; (dp-2)->block = nbp; } (dp-1)->size = cells; nbp->last = nbp->cell + cells + NOBJECT_FIELDS; nbp->freelist = nbp->last; ACHECK(ap); return (void*) dp; } /* Check if we can just grow this cell * (need to check that cells < ICELLS so we don't make an * object a `large' - that would mess everything up). */ if (dp && cells > oldcells && cells <= ICELLS) { Cell *fp, *fpp; Block *bp = (dp-2)->block; int need = cells - oldcells - NOBJECT_FIELDS; /* XXX if we had a flag in an object indicating * if the object was free/allocated, we could * avoid this loop (perhaps) */ for (fpp = NULL, fp = bp->freelist; fp != bp->last && dp + oldcells + NOBJECT_FIELDS <= fp ; fpp = fp, fp = fp->next) { if (dp + oldcells + NOBJECT_FIELDS == fp && (fp-1)->size >= need) { Cell *np = asplit(ap, bp, fp, fpp, need); /* May get more than we need here */ (dp-1)->size += (np-1)->size + NOBJECT_FIELDS; ACHECK(ap); return ptr; } } } /* Check if we can just shrink this cell * (if oldcells > ICELLS, this is a large object and we leave * it to malloc...) * Note: this also handles cells == oldcells (a no-op). */ if (dp && cells <= oldcells && oldcells <= ICELLS) { int split; split = oldcells - cells; if (split <= NOBJECT_FIELDS) /* cannot split */ ; else { /* shrink head, free tail */ Block *bp = (dp-2)->block; (dp-1)->size = cells; dp += cells + NOBJECT_FIELDS; (dp-1)->size = split - NOBJECT_FIELDS; (dp-2)->block = bp; afree((void*)dp, ap); } /* ACHECK() done in afree() */ return ptr; } /* Have to do it the hard way... */ ptr = alloc(size, ap); if (dp != NULL) { size_t s = (dp-1)->size * sizeof(Cell); if (s > size) s = size; memcpy(ptr, dp, s); afree((void *) dp, ap); } /* ACHECK() done in alloc()/afree() */ return ptr; } void afree(ptr, ap) void *ptr; register Area *ap; { register Block *bp; register Cell *fp, *fpp; register Cell *dp = (Cell*)ptr; ACHECK(ap); if (ptr == 0) aerror(ap, "freeing null pointer"); bp = (dp-2)->block; /* If this is a large object, just free it up... */ /* Release object... */ if ((dp-1)->size > ICELLS) { ablockfree(bp, ap); ACHECK(ap); return; } if (dp < &bp->cell[NOBJECT_FIELDS] || dp >= bp->last) aerror(ap, "freeing memory outside of block (corrupted?)"); /* find position in free list */ /* XXX if we had prev/next pointers for objects, this loop could go */ for (fpp = NULL, fp = bp->freelist; fp < dp; fpp = fp, fp = fp->next) ; if (fp == dp) aerror(ap, "freeing free object"); /* join object with next */ if (dp + (dp-1)->size == fp-NOBJECT_FIELDS) { /* adjacent */ (dp-1)->size += (fp-1)->size + NOBJECT_FIELDS; dp->next = fp->next; } else /* non-adjacent */ dp->next = fp; /* join previous with object */ if (fpp == NULL) bp->freelist = dp; else if (fpp + (fpp-1)->size == dp-NOBJECT_FIELDS) { /* adjacent */ (fpp-1)->size += (dp-1)->size + NOBJECT_FIELDS; fpp->next = dp->next; } else /* non-adjacent */ fpp->next = dp; /* If whole block is free (and we have some other blocks * around), release this block back to the system... */ if (bp->next != bp && bp->freelist == bp->cell + NOBJECT_FIELDS && bp->freelist + (bp->freelist-1)->size == bp->last /* XXX and the other block has some free memory? */ ) ablockfree(bp, ap); ACHECK(ap); } static void ablockfree(bp, ap) Block *bp; Area *ap; { /* NOTE: If this code changes, similar changes may be * needed in alloc() (where realloc fails). */ if (bp->next == bp) /* only block */ ap->freelist = &aempty; else { bp->next->prev = bp->prev; bp->prev->next = bp->next; if (ap->freelist == bp) ap->freelist = bp->next; } free((void*) bp); } # if DEBUG_ALLOC void acheck(ap) Area *ap; { Block *bp, *bpp; Cell *dp, *dptmp, *fp; int ok = 1; int isfree; static int disabled; if (disabled) return; if (!ap) { disabled = 1; aerror(ap, "acheck: null area pointer"); } bp = ap->freelist; if (!bp) { disabled = 1; aerror(ap, "acheck: null area freelist"); } /* Nothing to check... */ if (bp == &aempty) return; bpp = ap->freelist->prev; while (1) { if (bp->prev != bpp) { shellf("acheck: bp->prev != previous\n"); ok = 0; } fp = bp->freelist; for (dp = &bp->cell[NOBJECT_FIELDS]; dp != bp->last; ) { if ((dp-2)->block != bp) { shellf("acheck: fragment's block is wrong\n"); ok = 0; } isfree = dp == fp; if ((dp-1)->size == 0 && isfree) { shellf("acheck: 0 size frag\n"); ok = 0; } if ((dp-1)->size > ICELLS && !isfree && (dp != &bp->cell[NOBJECT_FIELDS] || dp + (dp-1)->size != bp->last)) { shellf("acheck: big cell doesn't make up whole block\n"); ok = 0; } if (isfree) { if (dp->next <= dp) { shellf("acheck: free fragment's next <= self\n"); ok = 0; } if (dp->next > bp->last) { shellf("acheck: free fragment's next > last\n"); ok = 0; } fp = dp->next; } dptmp = dp + (dp-1)->size; if (dptmp > bp->last) { shellf("acheck: next frag out of range\n"); ok = 0; break; } else if (dptmp != bp->last) { dptmp += NOBJECT_FIELDS; if (dptmp > bp->last) { shellf("acheck: next frag just out of range\n"); ok = 0; break; } } if (isfree && dptmp == fp && dptmp != bp->last) { shellf("acheck: adjacent free frags\n"); ok = 0; } else if (dptmp > fp) { shellf("acheck: free frag list messed up\n"); ok = 0; } dp = dptmp; } bpp = bp; bp = bp->next; if (bp == ap->freelist) break; } if (!ok) { disabled = 1; aerror(ap, "acheck failed"); } } void aprint(ap, ptr, size) register Area *ap; void *ptr; size_t size; { Block *bp; if (!ap) shellf("aprint: null area pointer\n"); else if (!(bp = ap->freelist)) shellf("aprint: null area freelist\n"); else if (bp == &aempty) shellf("aprint: area is empty\n"); else { int i; Cell *dp, *fp; Block *bpp; bpp = ap->freelist->prev; for (i = 0; ; i++) { if (ptr) { void *eptr = (void *) (((char *) ptr) + size); /* print block only if it overlaps ptr/size */ if (!((ptr >= (void *) bp && ptr <= (void *) bp->last) || (eptr >= (void *) bp && eptr <= (void *) bp->last))) continue; shellf("aprint: overlap of 0x%p .. 0x%p\n", ptr, eptr); } if (bp->prev != bpp || bp->next->prev != bp) shellf( "aprint: BAD prev pointer: bp %p, bp->prev %p, bp->next %p, bpp=%p\n", bp, bp->prev, bp->next, bpp); shellf("aprint: block %2d (p=%p,%p,n=%p): 0x%p .. 0x%p (%ld)\n", i, bp->prev, bp, bp->next, bp->cell, bp->last, (long) ((char *) bp->last - (char *) bp->cell)); fp = bp->freelist; if (bp->last <= bp->cell + NOBJECT_FIELDS) shellf( "aprint: BAD bp->last too small: %p <= %p\n", bp->last, bp->cell + NOBJECT_FIELDS); if (bp->freelist < bp->cell + NOBJECT_FIELDS || bp->freelist > bp->last) shellf( "aprint: BAD bp->freelist %p out of range: %p .. %p\n", bp->freelist, bp->cell + NOBJECT_FIELDS, bp->last); for (dp = bp->cell; dp != bp->last ; ) { dp += NOBJECT_FIELDS; shellf( "aprint: 0x%p .. 0x%p (%ld) %s\n", (dp-NOBJECT_FIELDS), (dp-NOBJECT_FIELDS) + (dp-1)->size + NOBJECT_FIELDS, (long) ((dp-1)->size + NOBJECT_FIELDS) * sizeof(Cell), dp == fp ? "free" : "allocated"); if ((dp-2)->block != bp) shellf( "aprint: BAD dp->block %p != bp %p\n", (dp-2)->block, bp); if (dp > bp->last) shellf( "aprint: BAD dp gone past block: %p > %p\n", dp, bp->last); if (dp > fp) shellf( "aprint: BAD dp gone past free: %p > %p\n", dp, fp); if (dp == fp) { fp = fp->next; if (fp < dp || fp > bp->last) shellf( "aprint: BAD free object %p out of range: %p .. %p\n", fp, dp, bp->last); } dp += (dp-1)->size; } bpp = bp; bp = bp->next; if (bp == ap->freelist) break; } } } #endif