4.3BSD - /usr/src/ucb/lisp/franz/vax/malloc.c

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

Defined functions

Defined variables

Defined union's

Defined macros