2.11BSD#431 - /usr/src/new/PORT/perl.1.0.10/malloc.c

   1: /* $Header: malloc.c,v 1.0.1.1 88/01/24 03:53:23 root Exp $
   2:  *
   3:  * $Log:	malloc.c,v $
   4:  * Revision 1.0.1.1  88/01/24  03:53:23  root
   5:  * patch 2: made depend on perl.h.
   6:  *
   7:  * Revision 1.0  87/12/18  13:05:35  root
   8:  * Initial revision
   9:  *
  10:  */
  11: 
  12: #ifndef lint
  13: static char sccsid[] = "@(#)malloc.c	4.3 (Berkeley) 9/16/83";
  14: #endif
  15: #include <stdio.h>
  16: 
  17: #define RCHECK
  18: /*
  19:  * malloc.c (Caltech) 2/21/82
  20:  * Chris Kingsley, kingsley@cit-20.
  21:  *
  22:  * This is a very fast storage allocator.  It allocates blocks of a small
  23:  * number of different sizes, and keeps free lists of each size.  Blocks that
  24:  * don't exactly fit are passed up to the next larger size.  In this
  25:  * implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
  26:  * This is designed for use in a program that uses vast quantities of memory,
  27:  * but bombs when it runs out.
  28:  */
  29: 
  30: #include "EXTERN.h"
  31: #include "handy.h"
  32: #include "search.h"
  33: #include "perl.h"
  34: 
  35: /* I don't much care whether these are defined in sys/types.h--LAW */
  36: 
  37: #define u_char unsigned char
  38: #define u_int unsigned int
  39: #define u_short unsigned short
  40: 
  41: #define NULL 0
  42: 
  43: /*
  44:  * The overhead on a block is at least 4 bytes.  When free, this space
  45:  * contains a pointer to the next free block, and the bottom two bits must
  46:  * be zero.  When in use, the first byte is set to MAGIC, and the second
  47:  * byte is the size index.  The remaining bytes are for alignment.
  48:  * If range checking is enabled and the size of the block fits
  49:  * in two bytes, then the top two bytes hold the size of the requested block
  50:  * plus the range checking words, and the header word MINUS ONE.
  51:  */
  52: union   overhead {
  53:     union   overhead *ov_next;  /* when free */
  54:     struct {
  55:         u_char  ovu_magic;  /* magic number */
  56:         u_char  ovu_index;  /* bucket # */
  57: #ifdef RCHECK
  58:         u_short ovu_size;   /* actual block size */
  59:         u_int   ovu_rmagic; /* range magic number */
  60: #endif
  61:     } ovu;
  62: #define ov_magic    ovu.ovu_magic
  63: #define ov_index    ovu.ovu_index
  64: #define ov_size     ovu.ovu_size
  65: #define ov_rmagic   ovu.ovu_rmagic
  66: };
  67: 
  68: #define MAGIC       0xff        /* magic # on accounting info */
  69: #define RMAGIC      0x55555555  /* magic # on range info */
  70: #ifdef RCHECK
  71: #define RSLOP       sizeof (u_int)
  72: #else
  73: #define RSLOP       0
  74: #endif
  75: 
  76: /*
  77:  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  78:  * smallest allocatable block is 8 bytes.  The overhead information
  79:  * precedes the data area returned to the user.
  80:  */
  81: #define NBUCKETS 30
  82: static  union overhead *nextf[NBUCKETS];
  83: extern  char *sbrk();
  84: 
  85: #ifdef MSTATS
  86: /*
  87:  * nmalloc[i] is the difference between the number of mallocs and frees
  88:  * for a given block size.
  89:  */
  90: static  u_int nmalloc[NBUCKETS];
  91: #include <stdio.h>
  92: #endif
  93: 
  94: #ifdef debug
  95: #define ASSERT(p)   if (!(p)) botch("p"); else
  96: static
  97: botch(s)
  98:     char *s;
  99: {
 100: 
 101:     printf("assertion botched: %s\n", s);
 102:     abort();
 103: }
 104: #else
 105: #define ASSERT(p)
 106: #endif
 107: 
 108: char *
 109: malloc(nbytes)
 110:     register unsigned nbytes;
 111: {
 112:     register union overhead *p;
 113:     register int bucket = 0;
 114:     register unsigned shiftr;
 115: 
 116:     /*
 117: 	 * Convert amount of memory requested into
 118: 	 * closest block size stored in hash buckets
 119: 	 * which satisfies request.  Account for
 120: 	 * space used per block for accounting.
 121: 	 */
 122:     nbytes += sizeof (union overhead) + RSLOP;
 123:     nbytes = (nbytes + 3) &~ 3;
 124:     shiftr = (nbytes - 1) >> 2;
 125:     /* apart from this loop, this is O(1) */
 126:     while (shiftr >>= 1)
 127:         bucket++;
 128:     /*
 129: 	 * If nothing in hash bucket right now,
 130: 	 * request more memory from the system.
 131: 	 */
 132:     if (nextf[bucket] == NULL)
 133:         morecore(bucket);
 134:     if ((p = (union overhead *)nextf[bucket]) == NULL)
 135:         return (NULL);
 136:     /* remove from linked list */
 137:     if (*((int*)p) > 0x10000000)
 138:         fprintf(stderr,"Corrupt malloc ptr 0x%x at 0x%x\n",*((int*)p),p);
 139:     nextf[bucket] = nextf[bucket]->ov_next;
 140:     p->ov_magic = MAGIC;
 141:     p->ov_index= bucket;
 142: #ifdef MSTATS
 143:     nmalloc[bucket]++;
 144: #endif
 145: #ifdef RCHECK
 146:     /*
 147: 	 * Record allocated size of block and
 148: 	 * bound space with magic numbers.
 149: 	 */
 150:     if (nbytes <= 0x10000)
 151:         p->ov_size = nbytes - 1;
 152:     p->ov_rmagic = RMAGIC;
 153:     *((u_int *)((caddr_t)p + nbytes - RSLOP)) = RMAGIC;
 154: #endif
 155:     return ((char *)(p + 1));
 156: }
 157: 
 158: /*
 159:  * Allocate more memory to the indicated bucket.
 160:  */
 161: static
 162: morecore(bucket)
 163:     register bucket;
 164: {
 165:     register union overhead *op;
 166:     register int rnu;       /* 2^rnu bytes will be requested */
 167:     register int nblks;     /* become nblks blocks of the desired size */
 168:     register int siz;
 169: 
 170:     if (nextf[bucket])
 171:         return;
 172:     /*
 173: 	 * Insure memory is allocated
 174: 	 * on a page boundary.  Should
 175: 	 * make getpageize call?
 176: 	 */
 177:     op = (union overhead *)sbrk(0);
 178:     if ((int)op & 0x3ff)
 179:         sbrk(1024 - ((int)op & 0x3ff));
 180:     /* take 2k unless the block is bigger than that */
 181:     rnu = (bucket <= 8) ? 11 : bucket + 3;
 182:     nblks = 1 << (rnu - (bucket + 3));  /* how many blocks to get */
 183:     if (rnu < bucket)
 184:         rnu = bucket;
 185:     op = (union overhead *)sbrk(1 << rnu);
 186:     /* no more room! */
 187:     if ((int)op == -1)
 188:         return;
 189:     /*
 190: 	 * Round up to minimum allocation size boundary
 191: 	 * and deduct from block count to reflect.
 192: 	 */
 193:     if ((int)op & 7) {
 194:         op = (union overhead *)(((int)op + 8) &~ 7);
 195:         nblks--;
 196:     }
 197:     /*
 198: 	 * Add new memory allocated to that on
 199: 	 * free list for this hash bucket.
 200: 	 */
 201:     nextf[bucket] = op;
 202:     siz = 1 << (bucket + 3);
 203:     while (--nblks > 0) {
 204:         op->ov_next = (union overhead *)((caddr_t)op + siz);
 205:         op = (union overhead *)((caddr_t)op + siz);
 206:     }
 207: }
 208: 
 209: free(cp)
 210:     char *cp;
 211: {
 212:     register int size;
 213:     register union overhead *op;
 214: 
 215:     if (cp == NULL)
 216:         return;
 217:     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
 218: #ifdef debug
 219:     ASSERT(op->ov_magic == MAGIC);      /* make sure it was in use */
 220: #else
 221:     if (op->ov_magic != MAGIC)
 222:         return;             /* sanity */
 223: #endif
 224: #ifdef RCHECK
 225:     ASSERT(op->ov_rmagic == RMAGIC);
 226:     if (op->ov_index <= 13)
 227:         ASSERT(*(u_int *)((caddr_t)op + op->ov_size + 1 - RSLOP) == RMAGIC);
 228: #endif
 229:     ASSERT(op->ov_index < NBUCKETS);
 230:     size = op->ov_index;
 231:     op->ov_next = nextf[size];
 232:     nextf[size] = op;
 233: #ifdef MSTATS
 234:     nmalloc[size]--;
 235: #endif
 236: }
 237: 
 238: /*
 239:  * When a program attempts "storage compaction" as mentioned in the
 240:  * old malloc man page, it realloc's an already freed block.  Usually
 241:  * this is the last block it freed; occasionally it might be farther
 242:  * back.  We have to search all the free lists for the block in order
 243:  * to determine its bucket: 1st we make one pass thru the lists
 244:  * checking only the first block in each; if that fails we search
 245:  * ``realloc_srchlen'' blocks in each list for a match (the variable
 246:  * is extern so the caller can modify it).  If that fails we just copy
 247:  * however many bytes was given to realloc() and hope it's not huge.
 248:  */
 249: int realloc_srchlen = 4;    /* 4 should be plenty, -1 =>'s whole list */
 250: 
 251: char *
 252: realloc(cp, nbytes)
 253:     char *cp;
 254:     unsigned nbytes;
 255: {
 256:     register u_int onb;
 257:     union overhead *op;
 258:     char *res;
 259:     register int i;
 260:     int was_alloced = 0;
 261: 
 262:     if (cp == NULL)
 263:         return (malloc(nbytes));
 264:     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
 265:     if (op->ov_magic == MAGIC) {
 266:         was_alloced++;
 267:         i = op->ov_index;
 268:     } else {
 269:         /*
 270: 		 * Already free, doing "compaction".
 271: 		 *
 272: 		 * Search for the old block of memory on the
 273: 		 * free list.  First, check the most common
 274: 		 * case (last element free'd), then (this failing)
 275: 		 * the last ``realloc_srchlen'' items free'd.
 276: 		 * If all lookups fail, then assume the size of
 277: 		 * the memory block being realloc'd is the
 278: 		 * smallest possible.
 279: 		 */
 280:         if ((i = findbucket(op, 1)) < 0 &&
 281:             (i = findbucket(op, realloc_srchlen)) < 0)
 282:             i = 0;
 283:     }
 284:     onb = (1 << (i + 3)) - sizeof (*op) - RSLOP;
 285:     /* avoid the copy if same size block */
 286:     if (was_alloced &&
 287:         nbytes <= onb && nbytes > (onb >> 1) - sizeof(*op) - RSLOP)
 288:         return(cp);
 289:     if ((res = malloc(nbytes)) == NULL)
 290:         return (NULL);
 291:     if (cp != res)          /* common optimization */
 292:         bcopy(cp, res, (nbytes < onb) ? nbytes : onb);
 293:     if (was_alloced)
 294:         free(cp);
 295:     return (res);
 296: }
 297: 
 298: /*
 299:  * Search ``srchlen'' elements of each free list for a block whose
 300:  * header starts at ``freep''.  If srchlen is -1 search the whole list.
 301:  * Return bucket number, or -1 if not found.
 302:  */
 303: static
 304: findbucket(freep, srchlen)
 305:     union overhead *freep;
 306:     int srchlen;
 307: {
 308:     register union overhead *p;
 309:     register int i, j;
 310: 
 311:     for (i = 0; i < NBUCKETS; i++) {
 312:         j = 0;
 313:         for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
 314:             if (p == freep)
 315:                 return (i);
 316:             j++;
 317:         }
 318:     }
 319:     return (-1);
 320: }
 321: 
 322: #ifdef MSTATS
 323: /*
 324:  * mstats - print out statistics about malloc
 325:  *
 326:  * Prints two lines of numbers, one showing the length of the free list
 327:  * for each size category, the second showing the number of mallocs -
 328:  * frees for each size category.
 329:  */
 330: mstats(s)
 331:     char *s;
 332: {
 333:     register int i, j;
 334:     register union overhead *p;
 335:     int totfree = 0,
 336:     totused = 0;
 337: 
 338:     fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
 339:     for (i = 0; i < NBUCKETS; i++) {
 340:         for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
 341:             ;
 342:         fprintf(stderr, " %d", j);
 343:         totfree += j * (1 << (i + 3));
 344:     }
 345:     fprintf(stderr, "\nused:\t");
 346:     for (i = 0; i < NBUCKETS; i++) {
 347:         fprintf(stderr, " %d", nmalloc[i]);
 348:         totused += nmalloc[i] * (1 << (i + 3));
 349:     }
 350:     fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",
 351:         totused, totfree);
 352: }
 353: #endif

Defined functions

Defined variables

Defined union's

Defined macros