/* This file should be edited with 4-column tabs! */ /* Author: Mark Moraes */ /*LINTLIBRARY*/ #include "adefs.h" #include "arena.h" RCSID("$Header: /home/mea/src/CVSROOT/zmailer/libmalloc/arena/amalloc.c,v 1.1.1.1 1998/02/10 21:01:46 mea Exp $"); static Arena colosseum = AINIT; void ainit(ap) Arena *ap; { *ap = colosseum; } static int grabhunk(ap, nwords) Arena *ap; size_t nwords; { univptr_t cp; int morecore; Word *ptr; size_t sbrkwords; size_t blksize; /* * two words for fake boundary tags for the entire block, and one * for the next ptr of the block. */ #define EXCESS 3 sbrkwords = (size_t) (((nwords + EXCESS) / ap->sbrkunits + 1) * ap->sbrkunits); morecore = sbrkwords * sizeof(Word) + SBRKEXTRA; if ((cp = (univptr_t) sbrk(morecore)) == (univptr_t) -1) return(0); /* * Should first GUARANTEE that what sbrk returns is aligned to * Word boundaries - see align.h. Unfortunately, to guarantee * that the pointer returned by sbrk is aligned on a word * boundary, we must ask for sizeof(Word) -1 extra bytes, since * we have no guarantee what other sbrk'ed blocks exist. (Sun * sbrk always returns an aligned value, that is another story!) * We use spare and nspare to keep track of the bytes wasted, so * that we can try and reuse them later. If no other sbrk()s are * called, then nspare rotates through the values 3, 2, 1, 0, * and the first branch of the if() is always taken. */ if ((ap->spare + ap->nspare) == (char *) cp) { ptr = (Word *) SBRKALIGN(ap->spare); morecore += ap->nspare; sbrkwords = morecore / sizeof(Word); } else { ptr = (Word *) SBRKALIGN(cp); morecore -= (char *) ptr - (char *) cp; } ap->spare = (char *) (ptr + sbrkwords); ap->nspare = (morecore - sbrkwords * sizeof(Word)); ap->totalavail += sbrkwords; PRTRACE(sprintf(ap->statsbuf, "sbrk %d\n", sbrkwords*sizeof(Word))); /* * Here we need to check if it adjoins the ap->hiword. If * it does, then ap->hiword need not be a fake boundary tag * any longer, (its a real one) and the higher end of the block * we sbrk'ed is the fake tag. So we tag it appropriately, make * the start of the block point to the old ap->hiword, and * free it. If we aren't next to ap->hiword, then someone * else sbrk'ed in between, so we can't coalesce over the * boundary anyway, in which case we just change ap->hiword * to be in the new sbrk'ed block without damaging the old one. * And we free the block. */ if (ptr != ap->hiword + 1) { /* Non-contiguous sbrk'ed block, or first sbrk we've done. */ /* * First push this block on the stack of non-contiguous blocks * we've sbrked. !! For real paranoia, we'd also check * ap->mem... */ REGISTER Word *tmp = ap->mem; ap->mem = ptr; ptr->next = tmp; ptr++; sbrkwords--; ap->hiword = ptr; if (ap->loword == NULL) { /* First time - set lower bound. */ PRTRACE(sprintf(ap->statsbuf, "heapstart 0x%x\n", ptr)); ap->loword = ptr; } /* * Fake boundary tags to indicate the ends of an arena. Since they * are marked as allocated, no attempt will be made to coalesce * before or after them. */ SIZEFIELD(ptr) = ALLOCED | sbrkwords; ap->hiword += sbrkwords - 1; PRTRACE(sprintf(ap->statsbuf, "heapend 0x%x\n", ap->hiword)); SIZEFIELD(ap->hiword) = ALLOCED | sbrkwords; ptr++; /* * The 2 we subtract are the special arena end tags, which is * why we don't use HEADERWORDS and TRAILERWORDS */ sbrkwords -= 2; SIZEFIELD(ptr) = FREEMASK(sbrkwords); DMEMSET(ptr + FREEHEADERWORDS, sbrkwords - FREE_OVERHEAD); ptr = ap->hiword - 1; SIZEFIELD(ptr) = FREEMASK(sbrkwords); /* links */ if (ap->rover == NULL) { /* Only block in free list - links point to itself */ NEXT(ptr) = ptr; PREV(ptr) = ptr; } else { /* * Non-contiguous sbrk - insert into free list. No * point calling free() because we know this cannot be * coalesced */ NEXT(ptr) = ap->rover; tmp = PREV(ap->rover); PREV(ptr) = tmp; /* PREV(ptr) = PREV(ap->rover); */ NEXT(tmp) = ptr; /* NEXT(PREV(ap->rover)) = ptr; */ PREV(ap->rover) = ptr; } ap->rover = ptr; return(1); } /* Set boundary tags and size */ ptr--; blksize = SIZE(ptr) + sbrkwords; SIZEFIELD(ptr) = ALLOCMASK(sbrkwords); ap->hiword += sbrkwords; SIZEFIELD(ap->hiword-1) = SIZEFIELD(ptr); /* Update fake end tags of the memory chunk */ SIZEFIELD(ap->hiword) = ALLOCMASK(blksize); SIZEFIELD(ap->hiword - blksize + 1) = ALLOCMASK(blksize); SET_REALSIZE(ptr, (sbrkwords - ALLOC_OVERHEAD) * sizeof(Word)); afree(ap, (univptr_t) (ptr + HEADERWORDS)); return(1); } univptr_t amalloc(ap, nbytes) Arena *ap; size_t nbytes; { REGISTER Word *start, *search; REGISTER Word *p; REGISTER size_t required; REGISTER size_t searchsize; REGISTER size_t rest; size_t roversize; #ifndef BUGCOMPATIBILITY ASSERT(nbytes != 0, "What do you expect when you malloc(0)?!!"); if (nbytes == 0) { /* If we're debugging, then we died on the ASSERT */ errno = EINVAL; return(NULL); } #endif /* BUGCOMPATIBILITY */ required = ALLOC_OVERHEAD + (nbytes + sizeof(Word) - 1) / sizeof(Word); if (required < (size_t) ap->minchunk) required = ap->minchunk; search = ap->rover; if (!search || required > ap->totalavail) { /* Not enough memory in free list - allocate enough memory. */ if (grabhunk(ap, required) == 0) { errno = ENOMEM; return( NULL); } search = ap->rover; } ASSERT(PTR_IN_HEAP(ap->rover), "corrupt rover pointer in malloc()"); ASSERT(VALID_END_SIZE_FIELD(ap->rover), "corrupt block in malloc()"); ASSERT(VALID_NEXT_PTR(ap->rover), "corrupt block in malloc()"); ASSERT(VALID_PREV_PTR(ap->rover), "corrupt block in malloc()"); CHECKHEAP(); start = search; roversize = FREESIZE(search); do { ASSERT(PTR_IN_HEAP(search), "corrupt pointer in malloc()"); ASSERT(VALID_END_SIZE_FIELD(search), "corrupt pointer in malloc()"); ASSERT(VALID_NEXT_PTR(search), "corrupt pointer in malloc()"); ASSERT(VALID_PREV_PTR(search), "corrupt pointer in malloc()"); searchsize = FREESIZE(search); if (searchsize >= required) { break; } else { search = NEXT(search); } } while (search != start); if (searchsize < required) { if (grabhunk(ap, required) == 0) { errno = ENOMEM; return( NULL); } /* * We made sure in grabhunk() or afree() that * ap->rover is pointing to the newly sbrked (and * freed) block. */ search = ap->rover; roversize = searchsize = FREESIZE(search); } rest = searchsize - required; if (rest >= ap->minchunk) { SIZEFIELD(search) = FREEMASK(rest); p = search - rest; SIZEFIELD(p+1) = FREEMASK(rest); SIZEFIELD(p) = ALLOCMASK(required); p -= required - 1; SIZEFIELD(p) = ALLOCMASK(required); ap->totalavail -= required; /* keep rover at the larger block */ if (rest > roversize) ap->rover = search; } else { /* alloc the entire block */ REGISTER Word *nextp = NEXT(search); SIZEFIELD(search) |= ALLOCED; p = search - searchsize + 1; SIZEFIELD(p) = SIZEFIELD(search); if (search == nextp) { ap->rover = NULL; } else { REGISTER Word *prevp = PREV(search); NEXT(prevp) = nextp; PREV(nextp) = prevp; /* keep rover at the larger block, unless we just allocated rover*/ if (search == ap->rover || FREESIZE(nextp) > roversize) ap->rover = nextp; } ap->totalavail -= searchsize; } PRTRACE(sprintf(ap->statsbuf, "+ %u %u 0x%x\n", nbytes, (SIZE(p) - ALLOC_OVERHEAD)*sizeof(Word), p + HEADERWORDS)); COUNTSIZE(SIZE(p)); SET_REALSIZE(p, nbytes); return((univptr_t) (p + HEADERWORDS)); } void afree(ap, cp) Arena *ap; univptr_t cp; { /* * This is where the boundary tags come into their own. The * boundary tag guarantees a constant time insert with full * coalescing (the time varies slightly for the four case possible, * but still, essentially a very fast free. */ /* * P0 is the block being freed. P1 is the pointer to the block * before the block being freed, and P2 is the block after it. * We can either coalesce with P1, P2, both, or neither */ REGISTER Word *p0, *p1, *p2; if (cp == NULL) return; p0 = (Word *) cp; p0 -= HEADERWORDS; /* A little paranoia... */ ASSERT(PTR_IN_HEAP(p0), "bad pointer passed to afree()"); ASSERT(TAG(p0) != FREE, "freed block passed to afree()"); ASSERT(VALID_START_SIZE_FIELD(p0), "corrupt block passed to afree()"); ASSERT(VALID_MAGIC(p0), "block with end overwritten passed to afree()"); /* With debugging, the assert would have already aborted */ if (TAG(p0) == FREE) { errno = EINVAL; return; } /* * clear the entire block that used to be p0's, just in case * someone tries to refer to it or anything in it again. We * leave the end tags alone for now - we'll smash them * individually depending on the way p0 merges with p1 and/or p2. */ DMEMSET(p0 + FREEHEADERWORDS, SIZE(p0) - FREE_OVERHEAD); PRTRACE(sprintf(ap->statsbuf, "- %u 0x%x\n", (SIZE(p0) - ALLOC_OVERHEAD)*sizeof(Word), p0 + HEADERWORDS)); ap->totalavail += SIZE(p0); p1 = p0 - 1; /* * p0 now points to the end of the block -- we start treating it as * a free block */ p0 += SIZE(p0) - 1; p2 = p0 + 1; /* * More paranoia.... We can't match the SIZEFIELDs of p1/p2 with * p1/p2 + SIZE(p1/p2) -1 because they might be a fake tag to * indicate the bounds of the arena. Further, we should only check * p1 if p0-1 is not the ap->loword or an arena bound - else p1 is * probably not a valid pointer. If tag p0-1 is allocated, then it * could be an arena bound. */ if (TAG(p2) == FREE) { /* * Aha - block which is physically after p0 is free. * Merging with it merely means increasing its size to * incorporate the block being freed - no pointer * shuffling. */ p2 += FREESIZE(p2) - 1; ASSERT(PTR_IN_HEAP(p2), "corrupt block in afree()"); ASSERT(TAG(p2)==FREE, "corrupt block in afree()"); ASSERT(VALID_END_SIZE_FIELD(p2), "corrupt block in afree()"); ASSERT(VALID_NEXT_PTR(p2), "corrupt block in afree()"); ASSERT(VALID_PREV_PTR(p2), "corrupt block in afree()"); SIZEFIELD(p2) = FREEMASK(FREESIZE(p2) + SIZE(p0)); SIZEFIELD(p2 - FREESIZE(p2) + 1) = SIZEFIELD(p2); /* * Smash p0's old end tag and p2's old start tag. */ DMEMSET(p0 - FREETRAILERWORDS + 1, FREETRAILERWORDS + FREEHEADERWORDS); p0 = p2; /* p0 just vanished - became part of p2 */ } if (TAG(p1) == FREE) { /* * Block that physically precedes p0 in memory is free. Merging * with it means rearranging the links to because the end of * the block (the handle it is known by) is now the end of p0 * rather than itself. So the blocks after and before it in the * free list need to be told. */ REGISTER Word *nextp1, *prevp1; ASSERT(PTR_IN_HEAP(p1), "corrupt block in afree()"); ASSERT(VALID_END_SIZE_FIELD(p1), "corrupt block in afree()"); ASSERT(VALID_NEXT_PTR(p1), "corrupt block in afree()"); ASSERT(VALID_PREV_PTR(p1), "corrupt block in afree()"); /* p0 grows to absorb p1 */ SIZEFIELD(p0) = FREEMASK(SIZE(p0) + FREESIZE(p1)); SIZEFIELD(p0 - FREESIZE(p0) + 1) = SIZEFIELD(p0); nextp1 = NEXT(p1); prevp1 = PREV(p1); /* * We smash the free list pointers in p1 (SIZE, NEXT, PREV) to * make sure no one refers to them again. We cannot smash the * start boundary tag because in both cases, it becomes the start * tag for the new block. We also trash p0's start tag. */ DMEMSET(p1 - FREETRAILERWORDS + 1, FREETRAILERWORDS + FREEHEADERWORDS); if (p0 != p2) { /* * Ok - p0 coalesced with the block physically * before it (p1) (which is why we're here, but * it didn't coalesce with the block after it * (p2) which is why p0 != p2. So we need to * insert p0 in the list in place of p1. */ if (nextp1 != p1) { /* Fix the PREV ptr of the next blk in the list */ PREV(nextp1) = p0; /* Fix the NEXT ptr of the previous blk in the list */ NEXT(prevp1) = p0; /* Copy the link info from p1 to p0 */ NEXT(p0) = nextp1; PREV(p0) = prevp1; } else { NEXT(p0) = p0; PREV(p0) = p0; } /* p1 just vanished - became part of p0 */ ap->rover = p0; CHECKHEAP(); return; } else { /* * p0 merged with p2, and with p1, which * essentially means that p2 grows to absorb p1 * in the free list (bridged by p0). So we * simply delete p1. Free list reduces by one * blk. */ /* Fix the PREV ptr of the next blk in the list */ PREV(nextp1) = prevp1; /* Fix the NEXT ptr of the previous blk in the list */ NEXT(prevp1) = nextp1; } } if (p0 != p2) { /* * If we're here, it means block P0 didn't coalesce, so * we need to insert it in the free list - we put it * before ROVER, and make ROVER point to it. Or it means * ROVER was NULL, i.e. free list is empty, which means * we have to take care of the boundary linking Free * list grows by one. */ if (ap->rover == NULL) { /* * Free list was empty - so we point * ap->rover at the block we're freeing to * get a proper circular linking. */ ap->rover = p0; } else { ASSERT(PTR_IN_HEAP(ap->rover), "corrupt rover pointer in afree()"); ASSERT(VALID_END_SIZE_FIELD(ap->rover), "corrupt block in afree()"); ASSERT(VALID_NEXT_PTR(ap->rover), "corrupt block in afree()"); ASSERT(VALID_PREV_PTR(ap->rover), "corrupt block in afree()"); } NEXT(p0) = ap->rover; PREV(p0) = PREV(ap->rover); PREV(ap->rover) = p0; NEXT(PREV(p0)) = p0; SIZEFIELD(p0) &= SIZEMASK; /* sets the boundary tag to FREE */ SIZEFIELD(p0 - FREESIZE(p0) + 1) = SIZEFIELD(p0); } ap->rover = p0; CHECKHEAP(); return; } /* * WARNING: This realloc() IS *NOT* upwards compatible with the * convention that the last freed block since the last malloc may be * realloced. Allegedly, this was because the old free() didn't coalesce * blocks, and reallocing a freed block would perform the compaction. * Yuk! */ univptr_t arealloc(ap, cp, nbytes) Arena *ap; univptr_t cp; size_t nbytes; { REGISTER Word *p0 = (Word *) cp; REGISTER Word *p1; univptr_t tmp; REGISTER size_t required; REGISTER size_t sizep0; if (p0 == NULL) return(amalloc(ap, nbytes)); if (nbytes == 0) { afree(ap, cp); return(NULL); } required = ALLOC_OVERHEAD + (nbytes + sizeof(Word) - 1) / sizeof(Word); p0 -= HEADERWORDS; /* A little paranoia... */ ASSERT(PTR_IN_HEAP(p0), "bad pointer passed to realloc()"); ASSERT(TAG(p0) != FREE, "freed block passed to realloc()"); ASSERT(VALID_START_SIZE_FIELD(p0), "corrupt block passed to realloc()"); ASSERT(VALID_MAGIC(p0), "block with end overwritten passed to realloc()"); /* With debugging, the assert would have already aborted */ if (TAG(p0) == FREE) { errno = EINVAL; return(NULL); } sizep0 = SIZE(p0); if (sizep0 >= required) { /* Shrinking the block */ size_t after = sizep0 - required; SET_REALSIZE(p0, nbytes); if (after < ap->minchunk) { /* * Not enough to free what's left so we return the block * intact - print no-op for neatness in output. */ PRTRACE(strcpy(ap->statsbuf, "no-op\n")); return(cp); } SIZEFIELD(p0) = ALLOCMASK(required); SIZEFIELD(p0 + required - 1) = SIZEFIELD(p0); p0 += required; /* * We free what's after the block - mark it alloced and * throw it to free() to figure out whether to merge it * with what follows... */ SIZEFIELD(p0) = ALLOCMASK(after); SIZEFIELD(p0 + after - 1) = SIZEFIELD(p0); SET_REALSIZE(p0, (after - ALLOC_OVERHEAD) * sizeof(Word)); afree(ap, (univptr_t) (p0 + HEADERWORDS)); return(cp); } /* * If we get here, then we are growing the block to something * bigger. If the following block is free and big enough to be * realloced, then we grow using that block. This resembles the * malloc code slightly. */ p1 = p0 + sizep0; required -= sizep0; if (TAG(p1) == FREE) { /* p1 not free, may be an arena bound or hiword */ ASSERT(PTR_IN_HEAP(p1), "corrupt pointer in realloc()"); ASSERT(VALID_START_SIZE_FIELD(p1), "corrupt block in realloc()"); ASSERT(VALID_NEXT_PTR(p1 + FREESIZE(p1) - 1), "corrupt block in realloc()"); ASSERT(VALID_PREV_PTR(p1 + FREESIZE(p1) - 1), "corrupt block in realloc()"); } if (TAG(p1) == FREE && FREESIZE(p1) >= required) { size_t rest = FREESIZE(p1) - required; REGISTER Word *p; if (rest >= ap->minchunk) { sizep0 += required; SIZEFIELD(p0) = ALLOCMASK(sizep0); p = p0 + sizep0; SIZEFIELD(p-1) = SIZEFIELD(p0);; SIZEFIELD(p) = FREEMASK(rest); SIZEFIELD(p + rest - 1) = FREEMASK(rest); ap->totalavail -= required; } else { /* * alloc the entire block and merge into p0. Free list * shrinks by a block */ REGISTER Word *nextp1, *prevp1; sizep0 += FREESIZE(p1); SIZEFIELD(p0) = ALLOCMASK(sizep0); SIZEFIELD(p0 + sizep0 - 1) = SIZEFIELD(p0); p1 += FREESIZE(p1) - 1; p = nextp1 = NEXT(p1); if (p1 == nextp1) { ap->rover = NULL; } else { prevp1 = PREV(p1); PREV(nextp1) = prevp1; NEXT(prevp1) = nextp1; ap->rover = nextp1; } ap->totalavail -= SIZE(p1); } SET_REALSIZE(p0, nbytes); CHECKHEAP(); PRTRACE(sprintf(ap->statsbuf, "++ %u %u 0x%x %u 0x%x\n", nbytes, (SIZE(p0) - ALLOC_OVERHEAD)*sizeof(Word), cp, SIZE(p)*sizeof(Word), p)); return(cp); } /* Have to do it the hard way */ tmp = amalloc(ap, nbytes); if (tmp != NULL) { MEMCPY(tmp, cp, ((SIZE(p0) - ALLOC_OVERHEAD))); afree(ap, cp); } return(tmp); } /* * !! Given what we know about alignment, we should be able to do better * than memset and set words. Hopefully memset has been tuned. */ univptr_t acalloc(ap, nelem, elsize) Arena *ap; size_t nelem, elsize; { REGISTER size_t nbytes = nelem * elsize; REGISTER univptr_t cp = amalloc(ap, nbytes); if (cp) (void) memset((univptr_t) cp, 0, (memsize_t) nbytes); return(cp); }