lib/malloc/malloc.c

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