4.3BSD - /usr/src/new/emacs/src/malloc.c

   1: /* Dynamic memory allocation for GNU.
   2:    Copyright (C) 1985 Richard M. Stallman,
   3:     based mostly on the public domain work of others.
   4: 
   5: This program is distributed in the hope that it will be useful,
   6: but without any warranty.  No author or distributor
   7: accepts responsibility to anyone for the consequences of using it
   8: or for whether it serves any particular purpose or works at all,
   9: unless he says so in writing.
  10: 
  11:    Permission is granted to anyone to distribute verbatim copies
  12:    of this program's source code as received, in any medium, provided that
  13:    the copyright notice, the nonwarraty notice above
  14:    and this permission notice are preserved,
  15:    and that the distributor grants the recipient all rights
  16:    for further redistribution as permitted by this notice,
  17:    and informs him of these rights.
  18: 
  19:    Permission is granted to distribute modified versions of this
  20:    program's source code, or of portions of it, under the above
  21:    conditions, plus the conditions that all changed files carry
  22:    prominent notices stating who last changed them and that the
  23:    derived material, including anything packaged together with it and
  24:    conceptually functioning as a modification of it rather than an
  25:    application of it, is in its entirety subject to a permission
  26:    notice identical to this one.
  27: 
  28:    Permission is granted to distribute this program (verbatim or
  29:    as modified) in compiled or executable form, provided verbatim
  30:    redistribution is permitted as stated above for source code, and
  31:     A.  it is accompanied by the corresponding machine-readable
  32:       source code, under the above conditions, or
  33:     B.  it is accompanied by a written offer, with no time limit,
  34:       to distribute the corresponding machine-readable source code,
  35:       under the above conditions, to any one, in return for reimbursement
  36:       of the cost of distribution.   Verbatim redistribution of the
  37:       written offer must be permitted.  Or,
  38:     C.  it is distributed by someone who received only the
  39:       compiled or executable form, and is accompanied by a copy of the
  40:       written offer of source code which he received along with it.
  41: 
  42:    Permission is granted to distribute this program (verbatim or as modified)
  43:    in executable form as part of a larger system provided that the source
  44:    code for this program, including any modifications used,
  45:    is also distributed or offered as stated in the preceding paragraph.
  46: 
  47: In other words, you are welcome to use, share and improve this program.
  48: You are forbidden to forbid anyone else to use, share and improve
  49: what you give them.   Help stamp out software-hoarding!  */
  50: 
  51: 
  52: /*
  53:  * @(#)nmalloc.c 1 (Caltech) 2/21/82
  54:  *
  55:  *	U of M Modified: 20 Jun 1983 ACT: strange hacks for Emacs
  56:  *
  57:  *	Nov 1983, Mike@BRL, Added support for 4.1C/4.2 BSD.
  58:  *
  59:  * This is a very fast storage allocator.  It allocates blocks of a small
  60:  * number of different sizes, and keeps free lists of each size.  Blocks
  61:  * that don't exactly fit are passed up to the next larger size.  In this
  62:  * implementation, the available sizes are (2^n)-4 (or -16) bytes long.
  63:  * This is designed for use in a program that uses vast quantities of
  64:  * memory, but bombs when it runs out.  To make it a little better, it
  65:  * warns the user when he starts to get near the end.
  66:  *
  67:  * June 84, ACT: modified rcheck code to check the range given to malloc,
  68:  * rather than the range determined by the 2-power used.
  69:  *
  70:  * Jan 85, RMS: calls malloc_warning to issue warning on nearly full.
  71:  * No longer Emacs-specific; can serve as all-purpose malloc for GNU.
  72:  * You should call malloc_init to reinitialize after loading dumped Emacs.
  73:  * Call malloc_stats to get info on memory stats if MSTATS turned on.
  74:  * realloc knows how to return same block given, just changing its size,
  75:  * if the power of 2 is correct.
  76:  */
  77: 
  78: /*
  79:  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  80:  * smallest allocatable block is 8 bytes.  The overhead information will
  81:  * go in the first int of the block, and the returned pointer will point
  82:  * to the second.
  83:  *
  84: #ifdef MSTATS
  85:  * nmalloc[i] is the difference between the number of mallocs and frees
  86:  * for a given block size.
  87: #endif /* MSTATS */
  88: 
  89: #ifdef emacs
  90: #include "config.h"
  91: #endif /* emacs */
  92: 
  93: #include <sys/param.h>
  94: 
  95: /* Determine which kind of system this is.  */
  96: #include <signal.h>
  97: #ifndef SIGTSTP
  98: #define USG
  99: #else /* SIGTSTP */
 100: #ifdef SIGIO
 101: #define BSD42
 102: #endif /* SIGIO */
 103: #endif /* SIGTSTP */
 104: 
 105: #ifndef BSD42
 106: #ifndef USG
 107: #include <sys/vlimit.h>     /* warn the user when near the end */
 108: #endif
 109: #else /* if BSD42 */
 110: #include <sys/time.h>
 111: #include <sys/resource.h>
 112: #endif /* BSD42 */
 113: 
 114: 
 115: #if defined (BSD4_1) || defined (USG)
 116: #ifdef EXEC_PAGESIZE
 117: #define getpagesize() EXEC_PAGESIZE
 118: #else
 119: #ifdef NBPG
 120: #define getpagesize() NBPG * CLSIZE
 121: #ifndef CLSIZE
 122: #define CLSIZE 1
 123: #endif /* no CLSIZE */
 124: #else /* no NBPG */
 125: #define getpagesize() NBPC
 126: #endif /* no NBPG */
 127: #endif /* no EXEC_PAGESIZE */
 128: #endif /* BSD4_1 or USG */
 129: 
 130: 
 131: #define ISALLOC ((char) 0xf7)   /* magic byte that implies allocation */
 132: #define ISFREE ((char) 0x54)    /* magic byte that implies free block */
 133:                 /* this is for error checking only */
 134: #define ISMEMALIGN ((char) 0xd6)  /* Stored before the value returned by
 135: 				     memalign, with the rest of the word
 136: 				     being the distance to the true
 137: 				     beginning of the block.  */
 138: 
 139: extern char etext;
 140: extern char *start_of_data ();
 141: 
 142: /* These two are for user programs to look at, when they are interested.  */
 143: 
 144: int malloc_sbrk_used;       /* amount of data space used now */
 145: int malloc_sbrk_unused;     /* amount more we can have */
 146: 
 147: /* start of data space; can be changed by calling init_malloc */
 148: static char *data_space_start;
 149: 
 150: #ifdef MSTATS
 151: static int nmalloc[30];
 152: static int nmal, nfre;
 153: #endif /* MSTATS */
 154: 
 155: /* If range checking is not turned on, all we have is a flag indicating
 156:    whether memory is allocated, an index in nextf[], and a size field; to
 157:    realloc() memory we copy either size bytes or 1<<(index+3) bytes depending
 158:    on whether the former can hold the exact size (given the value of
 159:    'index').  If range checking is on, we always need to know how much space
 160:    is allocated, so the 'size' field is never used. */
 161: 
 162: struct mhead {
 163:     char     mh_alloc;  /* ISALLOC or ISFREE */
 164:     char     mh_index;  /* index in nextf[] */
 165: /* Remainder are valid only when block is allocated */
 166:     unsigned short mh_size; /* size, if < 0x10000 */
 167: #ifdef rcheck
 168:     unsigned mh_nbytes; /* number of bytes allocated */
 169:     int      mh_magic4; /* should be == MAGIC4 */
 170: #endif /* rcheck */
 171: };
 172: 
 173: /* Access free-list pointer of a block.
 174:   It is stored at block + 4.
 175:   This is not a field in the mhead structure
 176:   because we want sizeof (struct mhead)
 177:   to describe the overhead for when the block is in use,
 178:   and we do not want the free-list pointer to count in that.  */
 179: 
 180: #define CHAIN(a) \
 181:   (*(struct mhead **) (sizeof (char *) + (char *) (a)))
 182: 
 183: #ifdef rcheck
 184: 
 185: /* To implement range checking, we write magic values in at the beginning and
 186:    end of each allocated block, and make sure they are undisturbed whenever a
 187:    free or a realloc occurs. */
 188: /* Written in each of the 4 bytes following the block's real space */
 189: #define MAGIC1 0x55
 190: /* Written in the 4 bytes before the block's real space */
 191: #define MAGIC4 0x55555555
 192: #define ASSERT(p) if (!(p)) botch("p"); else
 193: #define EXTRA  4        /* 4 bytes extra for MAGIC1s */
 194: #else
 195: #define ASSERT(p)
 196: #define EXTRA  0
 197: #endif /* rcheck */
 198: 
 199: 
 200: /* nextf[i] is free list of blocks of size 2**(i + 3)  */
 201: 
 202: static struct mhead *nextf[30];
 203: 
 204: /* Number of bytes of writable memory we can expect to be able to get */
 205: static int lim_data;
 206: /* Level number of warnings already issued.
 207:   0 -- no warnings issued.
 208:   1 -- 75% warning already issued.
 209:   2 -- 85% warning already issued.
 210: */
 211: static int warnlevel;
 212: 
 213: /* nonzero once initial bunch of free blocks made */
 214: static int gotpool;
 215: 
 216: /* Cause reinitialization based on job parameters;
 217:   also declare where the end of pure storage is. */
 218: malloc_init (start)
 219:      char *start;
 220: {
 221:   data_space_start = start;
 222:   lim_data = 0;
 223:   warnlevel = 0;
 224: }
 225: 
 226: static
 227: morecore (nu)           /* ask system for more memory */
 228:      register int nu;       /* size index to get more of  */
 229: {
 230:   char *sbrk ();
 231:   register char *cp;
 232:   register int nblks;
 233:   register int siz;
 234: 
 235:   if (!data_space_start)
 236:     {
 237: #if defined(USG) && defined (emacs)
 238:       data_space_start = start_of_data ();
 239: #else /* not USG, or not Emacs */
 240:       data_space_start = &etext;
 241: #endif /* not USG, or not Emacs */
 242:     }
 243: 
 244:   if (lim_data == 0)
 245:     get_lim_data ();
 246: 
 247:  /* On initial startup, get two blocks of each size up to 1k bytes */
 248:   if (!gotpool)
 249:     getpool (), getpool (), gotpool = 1;
 250: 
 251:  /* Find current end of memory and issue warning if getting near max */
 252: 
 253:   cp = sbrk (0);
 254:   siz = cp - data_space_start;
 255:   malloc_sbrk_used = siz;
 256:   malloc_sbrk_unused = lim_data - siz;
 257: 
 258:   switch (warnlevel)
 259:     {
 260:     case 0:
 261:       if (siz > (lim_data / 4) * 3)
 262:     {
 263:       warnlevel++;
 264:       malloc_warning ("Warning: past 75% of memory limit");
 265:     }
 266:       break;
 267:     case 1:
 268:       if (siz > (lim_data / 20) * 17)
 269:     {
 270:       warnlevel++;
 271:       malloc_warning ("Warning: past 85% of memory limit");
 272:     }
 273:       break;
 274:     case 2:
 275:       if (siz > (lim_data / 20) * 19)
 276:     {
 277:       warnlevel++;
 278:       malloc_warning ("Warning: past 95% of memory limit");
 279:     }
 280:       break;
 281:     }
 282: 
 283:   if ((int) cp & 0x3ff) /* land on 1K boundaries */
 284:     sbrk (1024 - ((int) cp & 0x3ff));
 285: 
 286:  /* Take at least 2k, and figure out how many blocks of the desired size
 287:     we're about to get */
 288:   nblks = 1;
 289:   if ((siz = nu) < 8)
 290:     nblks = 1 << ((siz = 8) - nu);
 291: 
 292:   if ((cp = sbrk (1 << (siz + 3))) == (char *) -1)
 293:     return;         /* no more room! */
 294:   if ((int) cp & 7)
 295:     {       /* shouldn't happen, but just in case */
 296:       cp = (char *) (((int) cp + 8) & ~7);
 297:       nblks--;
 298:     }
 299: 
 300:  /* save new header and link the nblks blocks together */
 301:   nextf[nu] = (struct mhead *) cp;
 302:   siz = 1 << (nu + 3);
 303:   while (1)
 304:     {
 305:       ((struct mhead *) cp) -> mh_alloc = ISFREE;
 306:       ((struct mhead *) cp) -> mh_index = nu;
 307:       if (--nblks <= 0) break;
 308:       CHAIN ((struct mhead *) cp) = (struct mhead *) (cp + siz);
 309:       cp += siz;
 310:     }
 311:  /* CHAIN ((struct mhead *) cp) = 0; */
 312:  /* since sbrk() returns cleared core, this is already set */
 313: }
 314: 
 315: static
 316: getpool ()
 317: {
 318:   register int nu;
 319:   register char *cp = sbrk (0);
 320: 
 321:   if ((int) cp & 0x3ff) /* land on 1K boundaries */
 322:     sbrk (1024 - ((int) cp & 0x3ff));
 323: 
 324:   /* Get 2k of storage */
 325: 
 326:   cp = sbrk (04000);
 327:   if (cp == (char *) -1)
 328:     return;
 329: 
 330:   /* Divide it into an initial 8-word block
 331:      plus one block of size 2**nu for nu = 3 ... 10.  */
 332: 
 333:   CHAIN (cp) = nextf[0];
 334:   nextf[0] = (struct mhead *) cp;
 335:   ((struct mhead *) cp) -> mh_alloc = ISFREE;
 336:   ((struct mhead *) cp) -> mh_index = 0;
 337:   cp += 8;
 338: 
 339:   for (nu = 0; nu < 7; nu++)
 340:     {
 341:       CHAIN (cp) = nextf[nu];
 342:       nextf[nu] = (struct mhead *) cp;
 343:       ((struct mhead *) cp) -> mh_alloc = ISFREE;
 344:       ((struct mhead *) cp) -> mh_index = nu;
 345:       cp += 8 << nu;
 346:     }
 347: }
 348: 
 349: char *
 350: malloc (n)      /* get a block */
 351:      unsigned n;
 352: {
 353:   register struct mhead *p;
 354:   register unsigned int nbytes;
 355:   register int nunits = 0;
 356: 
 357:   /* Figure out how many bytes are required, rounding up to the nearest
 358:      multiple of 4, then figure out which nextf[] area to use */
 359:   nbytes = (n + sizeof *p + EXTRA + 3) & ~3;
 360:   {
 361:     register unsigned int   shiftr = (nbytes - 1) >> 2;
 362: 
 363:     while (shiftr >>= 1)
 364:       nunits++;
 365:   }
 366: 
 367:   /* If there are no blocks of the appropriate size, go get some */
 368:   /* COULD SPLIT UP A LARGER BLOCK HERE ... ACT */
 369:   if (nextf[nunits] == 0)
 370:     morecore (nunits);
 371: 
 372:   /* Get one block off the list, and set the new list head */
 373:   if ((p = nextf[nunits]) == 0)
 374:     return 0;
 375:   nextf[nunits] = CHAIN (p);
 376: 
 377:   /* Check for free block clobbered */
 378:   /* If not for this check, we would gobble a clobbered free chain ptr */
 379:   /* and bomb out on the NEXT allocate of this size block */
 380:   if (p -> mh_alloc != ISFREE || p -> mh_index != nunits)
 381: #ifdef rcheck
 382:     botch ("block on free list clobbered");
 383: #else /* not rcheck */
 384:     abort ();
 385: #endif /* not rcheck */
 386: 
 387:   /* Fill in the info, and if range checking, set up the magic numbers */
 388:   p -> mh_alloc = ISALLOC;
 389: #ifdef rcheck
 390:   p -> mh_nbytes = n;
 391:   p -> mh_magic4 = MAGIC4;
 392:   {
 393:     register char  *m = (char *) (p + 1) + n;
 394: 
 395:     *m++ = MAGIC1, *m++ = MAGIC1, *m++ = MAGIC1, *m = MAGIC1;
 396:   }
 397: #else /* not rcheck */
 398:   p -> mh_size = n;
 399: #endif /* not rcheck */
 400: #ifdef MSTATS
 401:   nmalloc[nunits]++;
 402:   nmal++;
 403: #endif /* MSTATS */
 404:   return (char *) (p + 1);
 405: }
 406: 
 407: free (mem)
 408:      char *mem;
 409: {
 410:   register struct mhead *p;
 411:   {
 412:     register char *ap = mem;
 413: 
 414:     if (ap == 0)
 415:       return;
 416: 
 417:     p = (struct mhead *) ap - 1;
 418:     if (p -> mh_alloc == ISMEMALIGN)
 419:       {
 420:     ap -= p->mh_size;
 421:     p = (struct mhead *) ap - 1;
 422:       }
 423: 
 424:     if (p -> mh_alloc != ISALLOC)
 425:       abort ();
 426: 
 427: #ifdef rcheck
 428:     ASSERT (p -> mh_magic4 == MAGIC4);
 429:     ap += p -> mh_nbytes;
 430:     ASSERT (*ap++ == MAGIC1); ASSERT (*ap++ == MAGIC1);
 431:     ASSERT (*ap++ == MAGIC1); ASSERT (*ap   == MAGIC1);
 432: #endif /* rcheck */
 433:   }
 434:   {
 435:     register int nunits = p -> mh_index;
 436: 
 437:     ASSERT (nunits <= 29);
 438:     p -> mh_alloc = ISFREE;
 439:     CHAIN (p) = nextf[nunits];
 440:     nextf[nunits] = p;
 441: #ifdef MSTATS
 442:     nmalloc[nunits]--;
 443:     nfre++;
 444: #endif /* MSTATS */
 445:   }
 446: }
 447: 
 448: char *
 449: realloc (mem, n)
 450:      char *mem;
 451:      register unsigned n;
 452: {
 453:   register struct mhead *p;
 454:   register unsigned int tocopy;
 455:   register int nbytes;
 456:   register int nunits;
 457: 
 458:   if ((p = (struct mhead *) mem) == 0)
 459:     return malloc (n);
 460:   p--;
 461:   nunits = p -> mh_index;
 462:   ASSERT (p -> mh_alloc == ISALLOC);
 463: #ifdef rcheck
 464:   ASSERT (p -> mh_magic4 == MAGIC4);
 465:   {
 466:     register char *m = mem + (tocopy = p -> mh_nbytes);
 467:     ASSERT (*m++ == MAGIC1); ASSERT (*m++ == MAGIC1);
 468:     ASSERT (*m++ == MAGIC1); ASSERT (*m   == MAGIC1);
 469:   }
 470: #else /* not rcheck */
 471:   if (p -> mh_index >= 13)
 472:     tocopy = (1 << (p -> mh_index + 3)) - sizeof *p;
 473:   else
 474:     tocopy = p -> mh_size;
 475: #endif /* not rcheck */
 476: 
 477:   /* See if desired size rounds to same power of 2 as actual size. */
 478:   nbytes = (n + sizeof *p + EXTRA + 7) & ~7;
 479: 
 480:   /* If ok, use the same block, just marking its size as changed.  */
 481:   if (nbytes > (4 << nunits) && nbytes <= (8 << nunits))
 482:     {
 483: #ifdef rcheck
 484:       register char *m = mem + tocopy;
 485:       *m++ = 0;  *m++ = 0;  *m++ = 0;  *m++ = 0;
 486:       p-> mh_nbytes = n;
 487:       m = mem + n;
 488:       *m++ = MAGIC1;  *m++ = MAGIC1;  *m++ = MAGIC1;  *m++ = MAGIC1;
 489: #else /* not rcheck */
 490:       p -> mh_size = n;
 491: #endif /* not rcheck */
 492:       return mem;
 493:     }
 494: 
 495:   if (n < tocopy)
 496:     tocopy = n;
 497:   {
 498:     register char *new;
 499: 
 500:     if ((new = malloc (n)) == 0)
 501:       return 0;
 502:     bcopy (mem, new, tocopy);
 503:     free (mem);
 504:     return new;
 505:   }
 506: }
 507: 
 508: char *
 509: memalign (alignment, size)
 510:      unsigned alignment, size;
 511: {
 512:   register char *ptr = malloc (size + alignment);
 513:   register char *aligned;
 514:   register struct mhead *p;
 515: 
 516:   if (ptr == 0)
 517:     return 0;
 518:   /* If entire block has the desired alignment, just accept it.  */
 519:   if (((int) ptr & (alignment - 1)) == 0)
 520:     return ptr;
 521:   /* Otherwise, get address of byte in the block that has that alignment.  */
 522:   aligned = (char *) (((int) ptr + alignment - 1) & -alignment);
 523: 
 524:   /* Store a suitable indication of how to free the block,
 525:      so that free can find the true beginning of it.  */
 526:   p = (struct mhead *) aligned - 1;
 527:   p -> mh_size = aligned - ptr;
 528:   p -> mh_alloc = ISMEMALIGN;
 529:   return aligned;
 530: }
 531: 
 532: #ifndef HPUX
 533: /* This runs into trouble with getpagesize on HPUX.
 534:    Patching out seems cleaner than the ugly fix needed.  */
 535: char *
 536: valloc (size)
 537: {
 538:   return memalign (getpagesize (), size);
 539: }
 540: #endif /* not HPUX */
 541: 
 542: #ifdef MSTATS
 543: /* Return statistics describing allocation of blocks of size 2**n. */
 544: 
 545: struct mstats_value
 546:   {
 547:     int blocksize;
 548:     int nfree;
 549:     int nused;
 550:   };
 551: 
 552: struct mstats_value
 553: malloc_stats (size)
 554:      int size;
 555: {
 556:   struct mstats_value v;
 557:   register int i;
 558:   register struct mhead *p;
 559: 
 560:   v.nfree = 0;
 561: 
 562:   if (size < 0 || size >= 30)
 563:     {
 564:       v.blocksize = 0;
 565:       v.nused = 0;
 566:       return v;
 567:     }
 568: 
 569:   v.blocksize = 1 << (size + 3);
 570:   v.nused = nmalloc[size];
 571: 
 572:   for (p = nextf[size]; p; p = CHAIN (p))
 573:     v.nfree++;
 574: 
 575:   return v;
 576: }
 577: #endif /* MSTATS */
 578: 
 579: /*
 580:  *	This function returns the total number of bytes that the process
 581:  *	will be allowed to allocate via the sbrk(2) system call.  On
 582:  *	BSD systems this is the total space allocatable to stack and
 583:  *	data.  On USG systems this is the data space only.
 584:  */
 585: 
 586: #ifdef USG
 587: 
 588: get_lim_data ()
 589: {
 590:   extern long ulimit ();
 591: 
 592:   lim_data = ulimit (3, 0);
 593:   lim_data -= (long) data_space_start;
 594: }
 595: 
 596: #else /* not USG */
 597: #ifndef BSD42
 598: 
 599: get_lim_data ()
 600: {
 601:   lim_data = vlimit (LIM_DATA, -1);
 602: }
 603: 
 604: #else /* BSD42 */
 605: 
 606: get_lim_data ()
 607: {
 608:   struct rlimit XXrlimit;
 609: 
 610:   getrlimit (RLIMIT_DATA, &XXrlimit);
 611:   lim_data = XXrlimit.rlim_cur;     /* soft limit */
 612: }
 613: 
 614: #endif /* BSD42 */
 615: #endif /* not USG */

Defined functions

Defined variables

Defined struct's

Defined macros