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

Defined functions

Defined variables

Defined union's

Defined macros