Logo Search packages:      
Sourcecode: zmailer version File versions  Download package

amalloc.c

/*  This file should be edited with 4-column tabs! */
/*  Author: Mark Moraes <moraes@csri.toronto.edu> */

/*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);
}

Generated by  Doxygen 1.6.0   Back to index