2.11BSD#431 - /usr/src/usr.bin/patch/malloc.c

   1: /*
   2:  * @(#)nmalloc.c 1 (Caltech) 2/21/82
   3:  *
   4:  *	U of M Modified: 20 Jun 1983 ACT: strange hacks for Emacs
   5:  *
   6:  *	Nov 1983, Mike@BRL, Added support for 4.1C/4.2 BSD.
   7:  *
   8:  * This is a very fast storage allocator.  It allocates blocks of a small
   9:  * number of different sizes, and keeps free lists of each size.  Blocks
  10:  * that don't exactly fit are passed up to the next larger size.  In this
  11:  * implementation, the available sizes are (2^n)-4 (or -16) bytes long.
  12:  * This is designed for use in a program that uses vast quantities of
  13:  * memory, but bombs when it runs out.  To make it a little better, it
  14:  * warns the user when he starts to get near the end.
  15:  *
  16:  * June 84, ACT: modified rcheck code to check the range given to malloc,
  17:  * rather than the range determined by the 2-power used.
  18:  *
  19:  * Jan 85, RMS: calls malloc_warning to issue warning on nearly full.
  20:  * No longer Emacs-specific; can serve as all-purpose malloc for GNU.
  21:  * You should call malloc_init to reinitialize after loading dumped Emacs.
  22:  * Call malloc_stats to get info on memory stats if MSTATS turned on.
  23:  * realloc knows how to return same block given, just changing its size,
  24:  * if the power of 2 is correct.
  25:  */
  26: 
  27: /*
  28:  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  29:  * smallest allocatable block is 8 bytes.  The overhead information will
  30:  * go in the first int of the block, and the returned pointer will point
  31:  * to the second.
  32:  *
  33: #ifdef MSTATS
  34:  * nmalloc[i] is the difference between the number of mallocs and frees
  35:  * for a given block size.
  36: #endif /* MSTATS */
  37:  */
  38: 
  39: #define ISALLOC ((char) 0xf7)   /* magic byte that implies allocation */
  40: #define ISFREE ((char) 0x54)    /* magic byte that implies free block */
  41:                 /* this is for error checking only */
  42: 
  43: extern char etext;
  44: 
  45: /* end of the program; can be changed by calling init_malloc */
  46: static char *endofpure = &etext;
  47: 
  48: #ifdef MSTATS
  49: static int nmalloc[30];
  50: static int nmal, nfre;
  51: #endif /* MSTATS */
  52: 
  53: /* If range checking is not turned on, all we have is a flag indicating
  54:    whether memory is allocated, an index in nextf[], and a size field; to
  55:    realloc() memory we copy either size bytes or 1<<(index+3) bytes depending
  56:    on whether the former can hold the exact size (given the value of
  57:    'index').  If range checking is on, we always need to know how much space
  58:    is allocated, so the 'size' field is never used. */
  59: 
  60: struct mhead {
  61:     char     mh_alloc;  /* ISALLOC or ISFREE */
  62:     char     mh_index;  /* index in nextf[] */
  63: /* Remainder are valid only when block is allocated */
  64:     unsigned short mh_size; /* size, if < 0x10000 */
  65: #ifdef rcheck
  66:     unsigned mh_nbytes; /* number of bytes allocated */
  67:     int      mh_magic4; /* should be == MAGIC4 */
  68: #endif /* rcheck */
  69:     };
  70: 
  71: /* Access free-list pointer of a block.
  72:   It is stored at block + 4.
  73:   This is not a field in the mhead structure
  74:   because we want sizeof (struct mhead)
  75:   to describe the overhead for when the block is in use,
  76:   and we do not want the free-list pointer to count in that.  */
  77: 
  78: #define CHAIN(a) \
  79:   (*(struct mhead **) (sizeof (char *) + (char *) (a)))
  80: 
  81: #ifdef rcheck
  82: 
  83: /* To implement range checking, we write magic values in at the beginning and
  84:    end of each allocated block, and make sure they are undisturbed whenever a
  85:    free or a realloc occurs. */
  86: /* Written in each of the 4 bytes following the block's real space */
  87: #define MAGIC1 0x55
  88: /* Written in the 4 bytes before the block's real space */
  89: #define MAGIC4 0x55555555
  90: #define ASSERT(p) if (!(p)) botch("p"); else
  91: static
  92: botch(s)
  93:     char *s;
  94: {
  95: 
  96:     printf("assertion botched: %s\n", s);
  97:     abort();
  98: }
  99: #define EXTRA  4        /* 4 bytes extra for MAGIC1s */
 100: #else
 101: #define ASSERT(p)
 102: #define EXTRA  0
 103: #endif /* rcheck */
 104: 
 105: /* nextf[i] is free list of blocks of size 2**(i + 3)  */
 106: 
 107: static struct mhead *nextf[30];
 108: 
 109: #ifdef  M_WARN
 110: /* Number of bytes of writable memory we can expect to be able to get */
 111: static int  lim_data;
 112: /* Level number of warnings already issued.
 113:   0 -- no warnings issued.
 114:   1 -- 75% warning already issued.
 115:   2 -- 85% warning already issued.
 116: */
 117: static int  warnlevel;
 118: #endif /* M_WARN */
 119: 
 120: /* nonzero once initial bunch of free blocks made */
 121: static int gotpool;
 122: 
 123: /* Cause reinitialization based on job parameters;
 124:   also declare where the end of pure storage is. */
 125: malloc_init (end)
 126:     char *end; {
 127:     endofpure = end;
 128: #ifdef  M_WARN
 129:     lim_data = 0;
 130:     warnlevel = 0;
 131: #endif /* M_WARN */
 132:     }
 133: 
 134: static
 135: morecore (nu)           /* ask system for more memory */
 136:     register int nu; {      /* size index to get more of  */
 137:     char   *sbrk ();
 138:     register char  *cp;
 139:     register int    nblks;
 140:     register int    siz;
 141: 
 142: #ifdef  M_WARN
 143: #ifndef BSD42
 144: #ifdef USG
 145:     extern long ulimit ();
 146:     if (lim_data == 0)      /* find out how much we can get */
 147:         lim_data = ulimit (3, 0) - TEXT_START;
 148: #else   /*HMS: was endif */
 149:     if (lim_data == 0)      /* find out how much we can get */
 150:         lim_data = vlimit (LIM_DATA, -1);
 151: #endif /* USG */	/HMS:* was not here */
 152: #else
 153:     if (lim_data == 0) {
 154:         struct rlimit   XXrlimit;
 155: 
 156:         getrlimit (RLIMIT_DATA, &XXrlimit);
 157:         lim_data = XXrlimit.rlim_cur;}  /* soft limit */
 158: #endif /* BSD42 */
 159: #endif /* M_WARN */
 160: 
 161:     /* On initial startup, get two blocks of each size up to 1k bytes */
 162:     if (!gotpool)
 163:         getpool (), getpool (), gotpool = 1;
 164: 
 165:     /* Find current end of memory and issue warning if getting near max */
 166: 
 167:     cp = sbrk (0);
 168:     siz = cp - endofpure;
 169: #ifdef  M_WARN
 170:     switch (warnlevel) {
 171:         case 0:
 172:         if (siz > (lim_data / 4) * 3) {
 173:             warnlevel++;
 174:             malloc_warning ("Warning: past 75% of memory limit");}
 175:         break;
 176:         case 1:
 177:         if (siz > (lim_data / 20) * 17) {
 178:             warnlevel++;
 179:             malloc_warning ("Warning: past 85% of memory limit");}
 180:         break;
 181:         case 2:
 182:         if (siz > (lim_data / 20) * 19) {
 183:             warnlevel++;
 184:             malloc_warning ("Warning: past 95% of memory limit");}
 185:         break;}
 186: #endif /* M_WARN */
 187: 
 188:     if ((int) cp & 0x3ff)   /* land on 1K boundaries */
 189:         sbrk (1024 - ((int) cp & 0x3ff));
 190: 
 191:     /* Take at least 2k, and figure out how many blocks of the desired size we're about to get */
 192:     nblks = 1;
 193:     if ((siz = nu) < 8)
 194:         nblks = 1 << ((siz = 8) - nu);
 195: 
 196:     if ((cp = sbrk (1 << (siz + 3))) == (char *) -1)
 197:         return;         /* no more room! */
 198:     if ((int) cp & 7) {     /* shouldn't happen, but just in case */
 199:         cp = (char *) (((int) cp + 8) & ~7);
 200:         nblks--;}
 201: 
 202:     /* save new header and link the nblks blocks together */
 203:     nextf[nu] = (struct mhead *) cp;
 204:     siz = 1 << (nu + 3);
 205:     while (1) {
 206:         ((struct mhead *) cp) -> mh_alloc = ISFREE;
 207:         ((struct mhead *) cp) -> mh_index = nu;
 208:         if (--nblks <= 0) break;
 209:         CHAIN ((struct mhead *) cp) = (struct mhead *) (cp + siz);
 210:         cp += siz;}
 211: /*	CHAIN ((struct mhead *) cp) = 0;	/* since sbrk() returns cleared core, this is already set */
 212:     }
 213: 
 214: static
 215: getpool () {
 216:     register int nu;
 217:     register char *cp = sbrk (0);
 218: 
 219:     if ((int) cp & 0x3ff)   /* land on 1K boundaries */
 220:         sbrk (1024 - ((int) cp & 0x3ff));
 221: 
 222:     /* Get 2k of storage */
 223: 
 224:     cp = sbrk (04000);
 225:     if (cp == (char *) -1)
 226:         return;
 227: 
 228:     /* Divide it into an initial 8-word block
 229: 	plus one block of size 2**nu for nu = 3 ... 10.  */
 230: 
 231:     CHAIN (cp) = nextf[0];
 232:     nextf[0] = (struct mhead *) cp;
 233:     ((struct mhead *) cp) -> mh_alloc = ISFREE;
 234:     ((struct mhead *) cp) -> mh_index = 0;
 235:     cp += 8;
 236: 
 237:     for (nu = 0; nu < 7; nu++) {
 238:         CHAIN (cp) = nextf[nu];
 239:         nextf[nu] = (struct mhead *) cp;
 240:         ((struct mhead *) cp) -> mh_alloc = ISFREE;
 241:         ((struct mhead *) cp) -> mh_index = nu;
 242:         cp += 8 << nu;}}
 243: 
 244: char *
 245: malloc (n)      /* get a block */
 246:     unsigned n; {
 247:     register struct  mhead *p;
 248:     register unsigned int  nbytes;
 249:     register int    nunits = 0;
 250: 
 251:     /* Figure out how many bytes are required, rounding up to the nearest
 252: 	multiple of 4, then figure out which nextf[] area to use */
 253:     nbytes = (n + sizeof *p + EXTRA + 3) & ~3;
 254:         {
 255:         register unsigned int   shiftr = (nbytes - 1) >> 2;
 256: 
 257:         while (shiftr >>= 1)
 258:             nunits++;
 259:         }
 260: 
 261:     /* If there are no blocks of the appropriate size, go get some */
 262:     /* COULD SPLIT UP A LARGER BLOCK HERE ... ACT */
 263:     if (nextf[nunits] == 0)
 264:         morecore (nunits);
 265: 
 266:     /* Get one block off the list, and set the new list head */
 267:     if ((p = nextf[nunits]) == 0)
 268:         return 0;
 269:     nextf[nunits] = CHAIN (p);
 270: 
 271:     /* Check for free block clobbered */
 272:     /* If not for this check, we would gobble a clobbered free chain ptr */
 273:     /* and bomb out on the NEXT allocate of this size block */
 274:     if (p -> mh_alloc != ISFREE || p -> mh_index != nunits)
 275: #ifdef rcheck
 276:         botch ("block on free list clobbered");
 277: #else
 278:         abort ();
 279: #endif /* rcheck */
 280: 
 281:     /* Fill in the info, and if range checking, set up the magic numbers */
 282:     p -> mh_alloc = ISALLOC;
 283: #ifdef rcheck
 284:     p -> mh_nbytes = n;
 285:     p -> mh_magic4 = MAGIC4;
 286:         {
 287:         register char  *m = (char *) (p + 1) + n;
 288: 
 289:         *m++ = MAGIC1, *m++ = MAGIC1, *m++ = MAGIC1, *m = MAGIC1;
 290:         }
 291: #else
 292:     p -> mh_size = n;
 293: #endif /* rcheck */
 294: #ifdef MSTATS
 295:     nmalloc[nunits]++;
 296:     nmal++;
 297: #endif /* MSTATS */
 298:     return (char *) (p + 1);}
 299: 
 300: free (mem)
 301:     char *mem; {
 302:     register struct mhead *p;
 303:         {
 304:         register char *ap = mem;
 305: 
 306:         ASSERT (ap != 0);
 307:         p = (struct mhead *) ap - 1;
 308:         ASSERT (p -> mh_alloc == ISALLOC);
 309: #ifdef rcheck
 310:         ASSERT (p -> mh_magic4 == MAGIC4);
 311:         ap += p -> mh_nbytes;
 312:         ASSERT (*ap++ == MAGIC1); ASSERT (*ap++ == MAGIC1);
 313:         ASSERT (*ap++ == MAGIC1); ASSERT (*ap   == MAGIC1);
 314: #endif /* rcheck */
 315:         }
 316:         {
 317:         register int nunits = p -> mh_index;
 318: 
 319:         ASSERT (nunits <= 29);
 320:         p -> mh_alloc = ISFREE;
 321:         CHAIN (p) = nextf[nunits];
 322:         nextf[nunits] = p;
 323: #ifdef MSTATS
 324:         nmalloc[nunits]--;
 325:         nfre++;
 326: #endif /* MSTATS */
 327:         }
 328:     }
 329: 
 330: char *
 331: realloc (mem, n)
 332:     char *mem;
 333:     register unsigned n; {
 334:     register struct mhead *p;
 335:     register unsigned int tocopy;
 336:     register int nbytes;
 337:     register int nunits;
 338: 
 339:     if ((p = (struct mhead *) mem) == 0)
 340:         return malloc (n);
 341:     p--;
 342:     nunits = p -> mh_index;
 343:     ASSERT (p -> mh_alloc == ISALLOC);
 344: #ifdef rcheck
 345:     ASSERT (p -> mh_magic4 == MAGIC4);
 346:         {
 347:         register char *m = mem + (tocopy = p -> mh_nbytes);
 348:         ASSERT (*m++ == MAGIC1); ASSERT (*m++ == MAGIC1);
 349:         ASSERT (*m++ == MAGIC1); ASSERT (*m   == MAGIC1);
 350:         }
 351: #else
 352:     if (p -> mh_index >= 13)
 353:         tocopy = (1 << (p -> mh_index + 3)) - sizeof *p;
 354:     else
 355:         tocopy = p -> mh_size;
 356: #endif /* rcheck */
 357: 
 358:     /* See if desired size rounds to same power of 2 as actual size. */
 359:     nbytes = (n + sizeof *p + EXTRA + 7) & ~7;
 360: 
 361:     /* If ok, use the same block, just marking its size as changed.  */
 362:     if (nbytes > (4 << nunits) && nbytes <= (8 << nunits)) {
 363: #ifdef rcheck
 364:         register char *m = mem + tocopy;
 365:         *m++ = 0;  *m++ = 0;  *m++ = 0;  *m++ = 0;
 366:         p-> mh_nbytes = n;
 367:         m = mem + n;
 368:         *m++ = MAGIC1;  *m++ = MAGIC1;  *m++ = MAGIC1;  *m++ = MAGIC1;
 369: #else
 370:         p -> mh_size = n;
 371: #endif /* rcheck */
 372:         return mem;}
 373: 
 374:     if (n < tocopy)
 375:         tocopy = n;
 376:         {
 377:         register char *new;
 378:         void bcopy();   /*HMS: here? */
 379: 
 380:         if ((new = malloc (n)) == 0)
 381:             return 0;
 382:         bcopy (mem, new, tocopy);
 383:         free (mem);
 384:         return new;
 385:         }
 386:     }
 387: 
 388: #ifdef MSTATS
 389: /* Return statistics describing allocation of blocks of size 2**n. */
 390: 
 391: struct mstats_value {
 392:     int blocksize;
 393:     int nfree;
 394:     int nused;
 395:     };
 396: 
 397: struct mstats_value
 398: malloc_stats (size)
 399:     int size; {
 400:     struct mstats_value v;
 401:     register int i;
 402:     register struct mhead *p;
 403: 
 404:     v.nfree = 0;
 405: 
 406:     if (size < 0 || size >= 30) {
 407:         v.blocksize = 0;
 408:         v.nused = 0;
 409:         return v;}
 410: 
 411:     v.blocksize = 1 << (size + 3);
 412:     v.nused = nmalloc[size];
 413: 
 414:     for (p = nextf[size]; p; p = CHAIN (p))
 415:         v.nfree++;
 416: 
 417:     return v;}
 418: #endif
 419: 
 420: /* how much space is available? */
 421: 
 422: unsigned freespace() {
 423:     register int i, j;
 424:     register struct mhead *p;
 425:     register unsigned space = 0;
 426:     int local;  /* address only is used */
 427: 
 428:     space = (char *)&local - sbrk(0);   /* stack space */
 429: 
 430:     for (i = 0; i < 30; i++) {
 431:         for (j = 0, p = nextf[i]; p; p = CHAIN (p), j++) ;
 432:         space += j * (1 << (i + 3));}
 433: 
 434:     return(space);}
 435: 
 436: /* How big is this cell? */
 437: 
 438: unsigned mc_size(cp)
 439:     char *cp;{
 440:     register struct mhead *p;
 441: 
 442:     if ((p = (struct mhead *) cp) == 0) {
 443:         /*HMS? */
 444:         }
 445:     p--;
 446: #ifdef rcheck
 447:     return p -> mh_nbytes;
 448: #else
 449:     return (1 << (p -> mh_index + 3)) - sizeof *p;
 450: /**/
 451: /*	if (p -> mh_index >= 13)
 452: /*	    return (1 << (p -> mh_index + 3)) - sizeof *p;
 453: /*	else
 454: /*	    return p -> mh_size;
 455: /**/
 456: #endif /* rcheck */
 457:     }
 458: 
 459: /*HMS: Really should use memcpy, if available... */
 460: 
 461: void bcopy(source, dest, len)
 462:     register char *source, *dest;
 463:     register len; {
 464:     register i;
 465: 
 466:     for (i = 0; i < len; i++)
 467:         *dest++ = *source++;}

Defined functions

Defined variables

Defined struct's

Defined macros