4.3BSD - /usr/src/lib/libc/gen/malloc.c

   1: /*
   2:  * Copyright (c) 1983 Regents of the University of California.
   3:  * All rights reserved.  The Berkeley software License Agreement
   4:  * specifies the terms and conditions for redistribution.
   5:  */
   6: 
   7: #if defined(LIBC_SCCS) && !defined(lint)
   8: static char sccsid[] = "@(#)malloc.c	5.6 (Berkeley) 3/9/86";
   9: #endif LIBC_SCCS and not lint
  10: 
  11: /*
  12:  * malloc.c (Caltech) 2/21/82
  13:  * Chris Kingsley, kingsley@cit-20.
  14:  *
  15:  * This is a very fast storage allocator.  It allocates blocks of a small
  16:  * number of different sizes, and keeps free lists of each size.  Blocks that
  17:  * don't exactly fit are passed up to the next larger size.  In this
  18:  * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long.
  19:  * This is designed for use in a virtual memory environment.
  20:  */
  21: 
  22: #include <sys/types.h>
  23: 
  24: #define NULL 0
  25: 
  26: /*
  27:  * The overhead on a block is at least 4 bytes.  When free, this space
  28:  * contains a pointer to the next free block, and the bottom two bits must
  29:  * be zero.  When in use, the first byte is set to MAGIC, and the second
  30:  * byte is the size index.  The remaining bytes are for alignment.
  31:  * If range checking is enabled then a second word holds the size of the
  32:  * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC).
  33:  * The order of elements is critical: ov_magic must overlay the low order
  34:  * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern.
  35:  */
  36: union   overhead {
  37:     union   overhead *ov_next;  /* when free */
  38:     struct {
  39:         u_char  ovu_magic;  /* magic number */
  40:         u_char  ovu_index;  /* bucket # */
  41: #ifdef RCHECK
  42:         u_short ovu_rmagic; /* range magic number */
  43:         u_int   ovu_size;   /* actual block size */
  44: #endif
  45:     } ovu;
  46: #define ov_magic    ovu.ovu_magic
  47: #define ov_index    ovu.ovu_index
  48: #define ov_rmagic   ovu.ovu_rmagic
  49: #define ov_size     ovu.ovu_size
  50: };
  51: 
  52: #define MAGIC       0xef        /* magic # on accounting info */
  53: #define RMAGIC      0x5555      /* magic # on range info */
  54: 
  55: #ifdef RCHECK
  56: #define RSLOP       sizeof (u_short)
  57: #else
  58: #define RSLOP       0
  59: #endif
  60: 
  61: /*
  62:  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  63:  * smallest allocatable block is 8 bytes.  The overhead information
  64:  * precedes the data area returned to the user.
  65:  */
  66: #define NBUCKETS 30
  67: static  union overhead *nextf[NBUCKETS];
  68: extern  char *sbrk();
  69: 
  70: static  int pagesz;         /* page size */
  71: static  int pagebucket;         /* page size bucket */
  72: 
  73: #ifdef MSTATS
  74: /*
  75:  * nmalloc[i] is the difference between the number of mallocs and frees
  76:  * for a given block size.
  77:  */
  78: static  u_int nmalloc[NBUCKETS];
  79: #include <stdio.h>
  80: #endif
  81: 
  82: #if defined(DEBUG) || defined(RCHECK)
  83: #define ASSERT(p)   if (!(p)) botch("p")
  84: #include <stdio.h>
  85: static
  86: botch(s)
  87:     char *s;
  88: {
  89:     fprintf(stderr, "\r\nassertion botched: %s\r\n", s);
  90:     (void) fflush(stderr);      /* just in case user buffered it */
  91:     abort();
  92: }
  93: #else
  94: #define ASSERT(p)
  95: #endif
  96: 
  97: char *
  98: malloc(nbytes)
  99:     unsigned nbytes;
 100: {
 101:     register union overhead *op;
 102:     register int bucket;
 103:     register unsigned amt, n;
 104: 
 105:     /*
 106: 	 * First time malloc is called, setup page size and
 107: 	 * align break pointer so all data will be page aligned.
 108: 	 */
 109:     if (pagesz == 0) {
 110:         pagesz = n = getpagesize();
 111:         op = (union overhead *)sbrk(0);
 112:         n = n - sizeof (*op) - ((int)op & (n - 1));
 113:         if (n < 0)
 114:             n += pagesz;
 115:         if (n) {
 116:             if (sbrk(n) == (char *)-1)
 117:                 return (NULL);
 118:         }
 119:         bucket = 0;
 120:         amt = 8;
 121:         while (pagesz > amt) {
 122:             amt <<= 1;
 123:             bucket++;
 124:         }
 125:         pagebucket = bucket;
 126:     }
 127:     /*
 128: 	 * Convert amount of memory requested into closest block size
 129: 	 * stored in hash buckets which satisfies request.
 130: 	 * Account for space used per block for accounting.
 131: 	 */
 132:     if (nbytes <= (n = pagesz - sizeof (*op) - RSLOP)) {
 133: #ifndef RCHECK
 134:         amt = 8;    /* size of first bucket */
 135:         bucket = 0;
 136: #else
 137:         amt = 16;   /* size of first bucket */
 138:         bucket = 1;
 139: #endif
 140:         n = -(sizeof (*op) + RSLOP);
 141:     } else {
 142:         amt = pagesz;
 143:         bucket = pagebucket;
 144:     }
 145:     while (nbytes > amt + n) {
 146:         amt <<= 1;
 147:         if (amt == 0)
 148:             return (NULL);
 149:         bucket++;
 150:     }
 151:     /*
 152: 	 * If nothing in hash bucket right now,
 153: 	 * request more memory from the system.
 154: 	 */
 155:     if ((op = nextf[bucket]) == NULL) {
 156:         morecore(bucket);
 157:         if ((op = nextf[bucket]) == NULL)
 158:             return (NULL);
 159:     }
 160:     /* remove from linked list */
 161:     nextf[bucket] = op->ov_next;
 162:     op->ov_magic = MAGIC;
 163:     op->ov_index = bucket;
 164: #ifdef MSTATS
 165:     nmalloc[bucket]++;
 166: #endif
 167: #ifdef RCHECK
 168:     /*
 169: 	 * Record allocated size of block and
 170: 	 * bound space with magic numbers.
 171: 	 */
 172:     op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
 173:     op->ov_rmagic = RMAGIC;
 174:     *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
 175: #endif
 176:     return ((char *)(op + 1));
 177: }
 178: 
 179: /*
 180:  * Allocate more memory to the indicated bucket.
 181:  */
 182: morecore(bucket)
 183:     int bucket;
 184: {
 185:     register union overhead *op;
 186:     register int sz;        /* size of desired block */
 187:     int amt;            /* amount to allocate */
 188:     int nblks;          /* how many blocks we get */
 189: 
 190:     /*
 191: 	 * sbrk_size <= 0 only for big, FLUFFY, requests (about
 192: 	 * 2^30 bytes on a VAX, I think) or for a negative arg.
 193: 	 */
 194:     sz = 1 << (bucket + 3);
 195: #ifdef DEBUG
 196:     ASSERT(sz > 0);
 197: #else
 198:     if (sz <= 0)
 199:         return;
 200: #endif
 201:     if (sz < pagesz) {
 202:         amt = pagesz;
 203:         nblks = amt / sz;
 204:     } else {
 205:         amt = sz + pagesz;
 206:         nblks = 1;
 207:     }
 208:     op = (union overhead *)sbrk(amt);
 209:     /* no more room! */
 210:     if ((int)op == -1)
 211:         return;
 212:     /*
 213: 	 * Add new memory allocated to that on
 214: 	 * free list for this hash bucket.
 215: 	 */
 216:     nextf[bucket] = op;
 217:     while (--nblks > 0) {
 218:         op->ov_next = (union overhead *)((caddr_t)op + sz);
 219:         op = (union overhead *)((caddr_t)op + sz);
 220:     }
 221: }
 222: 
 223: free(cp)
 224:     char *cp;
 225: {
 226:     register int size;
 227:     register union overhead *op;
 228: 
 229:     if (cp == NULL)
 230:         return;
 231:     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
 232: #ifdef DEBUG
 233:     ASSERT(op->ov_magic == MAGIC);      /* make sure it was in use */
 234: #else
 235:     if (op->ov_magic != MAGIC)
 236:         return;             /* sanity */
 237: #endif
 238: #ifdef RCHECK
 239:     ASSERT(op->ov_rmagic == RMAGIC);
 240:     ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC);
 241: #endif
 242:     size = op->ov_index;
 243:     ASSERT(size < NBUCKETS);
 244:     op->ov_next = nextf[size];  /* also clobbers ov_magic */
 245:     nextf[size] = op;
 246: #ifdef MSTATS
 247:     nmalloc[size]--;
 248: #endif
 249: }
 250: 
 251: /*
 252:  * When a program attempts "storage compaction" as mentioned in the
 253:  * old malloc man page, it realloc's an already freed block.  Usually
 254:  * this is the last block it freed; occasionally it might be farther
 255:  * back.  We have to search all the free lists for the block in order
 256:  * to determine its bucket: 1st we make one pass thru the lists
 257:  * checking only the first block in each; if that fails we search
 258:  * ``realloc_srchlen'' blocks in each list for a match (the variable
 259:  * is extern so the caller can modify it).  If that fails we just copy
 260:  * however many bytes was given to realloc() and hope it's not huge.
 261:  */
 262: int realloc_srchlen = 4;    /* 4 should be plenty, -1 =>'s whole list */
 263: 
 264: char *
 265: realloc(cp, nbytes)
 266:     char *cp;
 267:     unsigned nbytes;
 268: {
 269:     register u_int onb, i;
 270:     union overhead *op;
 271:     char *res;
 272:     int was_alloced = 0;
 273: 
 274:     if (cp == NULL)
 275:         return (malloc(nbytes));
 276:     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
 277:     if (op->ov_magic == MAGIC) {
 278:         was_alloced++;
 279:         i = op->ov_index;
 280:     } else {
 281:         /*
 282: 		 * Already free, doing "compaction".
 283: 		 *
 284: 		 * Search for the old block of memory on the
 285: 		 * free list.  First, check the most common
 286: 		 * case (last element free'd), then (this failing)
 287: 		 * the last ``realloc_srchlen'' items free'd.
 288: 		 * If all lookups fail, then assume the size of
 289: 		 * the memory block being realloc'd is the
 290: 		 * largest possible (so that all "nbytes" of new
 291: 		 * memory are copied into).  Note that this could cause
 292: 		 * a memory fault if the old area was tiny, and the moon
 293: 		 * is gibbous.  However, that is very unlikely.
 294: 		 */
 295:         if ((i = findbucket(op, 1)) < 0 &&
 296:             (i = findbucket(op, realloc_srchlen)) < 0)
 297:             i = NBUCKETS;
 298:     }
 299:     onb = 1 << (i + 3);
 300:     if (onb < pagesz)
 301:         onb -= sizeof (*op) + RSLOP;
 302:     else
 303:         onb += pagesz - sizeof (*op) - RSLOP;
 304:     /* avoid the copy if same size block */
 305:     if (was_alloced) {
 306:         if (i) {
 307:             i = 1 << (i + 2);
 308:             if (i < pagesz)
 309:                 i -= sizeof (*op) + RSLOP;
 310:             else
 311:                 i += pagesz - sizeof (*op) - RSLOP;
 312:         }
 313:         if (nbytes <= onb && nbytes > i) {
 314: #ifdef RCHECK
 315:             op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
 316:             *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
 317: #endif
 318:             return(cp);
 319:         } else
 320:             free(cp);
 321:     }
 322:     if ((res = malloc(nbytes)) == NULL)
 323:         return (NULL);
 324:     if (cp != res)      /* common optimization if "compacting" */
 325:         bcopy(cp, res, (nbytes < onb) ? nbytes : onb);
 326:     return (res);
 327: }
 328: 
 329: /*
 330:  * Search ``srchlen'' elements of each free list for a block whose
 331:  * header starts at ``freep''.  If srchlen is -1 search the whole list.
 332:  * Return bucket number, or -1 if not found.
 333:  */
 334: static
 335: findbucket(freep, srchlen)
 336:     union overhead *freep;
 337:     int srchlen;
 338: {
 339:     register union overhead *p;
 340:     register int i, j;
 341: 
 342:     for (i = 0; i < NBUCKETS; i++) {
 343:         j = 0;
 344:         for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
 345:             if (p == freep)
 346:                 return (i);
 347:             j++;
 348:         }
 349:     }
 350:     return (-1);
 351: }
 352: 
 353: #ifdef MSTATS
 354: /*
 355:  * mstats - print out statistics about malloc
 356:  *
 357:  * Prints two lines of numbers, one showing the length of the free list
 358:  * for each size category, the second showing the number of mallocs -
 359:  * frees for each size category.
 360:  */
 361: mstats(s)
 362:     char *s;
 363: {
 364:     register int i, j;
 365:     register union overhead *p;
 366:     int totfree = 0,
 367:     totused = 0;
 368: 
 369:     fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
 370:     for (i = 0; i < NBUCKETS; i++) {
 371:         for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
 372:             ;
 373:         fprintf(stderr, " %d", j);
 374:         totfree += j * (1 << (i + 3));
 375:     }
 376:     fprintf(stderr, "\nused:\t");
 377:     for (i = 0; i < NBUCKETS; i++) {
 378:         fprintf(stderr, " %d", nmalloc[i]);
 379:         totused += nmalloc[i] * (1 << (i + 3));
 380:     }
 381:     fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",
 382:         totused, totfree);
 383: }
 384: #endif

Defined functions

Defined variables

Defined union's

Defined macros