lib/malloc/malloc.c

   1 /* malloc.c - dynamic memory allocation for bash. */
   2
   3 /*  Copyright (C) 1985, 1987, 1997 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 2, 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., 59 Temple Place, Suite 330, Boston, MA 02111 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 MALLOC_STATS 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 #define MALLOC_STATS            /* for the time being */
  49
  50 /*
  51  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  52  * smallest allocatable block is 8 bytes.  The overhead information will
  53  * go in the first int of the block, and the returned pointer will point
  54  * to the second.
  55  */
  56
  57 /* Define this to have free() write 0xcf into memory as it's freed, to
  58    uncover callers that refer to freed memory. */
  59 /* SCO 3.2v4 getcwd and possibly other libc routines fail with MEMSCRAMBLE */
  60 #if !defined (NO_MEMSCRAMBLE)
  61 #  define MEMSCRAMBLE
  62 #endif
  63
  64 #if defined (HAVE_CONFIG_H)
  65 #  include <config.h>
  66 #endif /* HAVE_CONFIG_H */
  67
  68 #if defined (SHELL)
  69 #  include "bashtypes.h"
  70 #else
  71 #  include <sys/types.h>
  72 #endif
  73
  74 #if defined (HAVE_UNISTD_H)
  75 #  include <unistd.h>
  76 #endif
  77
  78 /* Determine which kind of system this is.  */
  79 #include <signal.h>
  80
  81 #if defined (HAVE_STRING_H)
  82 #  include <string.h>
  83 #else
  84 #  include <strings.h>
  85 #endif
  86
  87 #if defined (MALLOC_STATS) || !defined (botch)
  88 #  include <stdio.h>
  89 #endif /* MALLOC_STATS || !botch */
  90
  91 /* Define getpagesize () if the system does not.  */
  92 #ifndef HAVE_GETPAGESIZE
  93 #  include "getpagesize.h"
  94 #endif
  95
  96 #if __GNUC__ > 1
  97 #  define FASTCOPY(s, d, n)  __builtin_memcpy (d, s, n)
  98 #else /* !__GNUC__ */
  99 #  if !defined (HAVE_BCOPY)
 100 #    if !defined (HAVE_MEMMOVE)
 101 #      define FASTCOPY(s, d, n)  memcpy (d, s, n)
 102 #    else
 103 #      define FASTCOPY(s, d, n)  memmove (d, s, n)
 104 #    endif /* !HAVE_MEMMOVE */
 105 #  else /* HAVE_BCOPY */
 106 #    define FASTCOPY(s, d, n)  bcopy (s, d, n)
 107 #  endif /* HAVE_BCOPY */
 108 #endif /* !__GNUC__ */
 109
 110 /* Generic pointer type. */
 111 #ifndef PTR_T
 112 #  if defined (__STDC__)
 113 #    define PTR_T void *
 114 #  else
 115 #    define PTR_T char *
 116 #  endif
 117 #endif
 118
 119 #if !defined (NULL)
 120 #  define NULL 0
 121 #endif
 122
 123 #define NBUCKETS        30
 124
 125 #define ISALLOC ((char) 0xf7)   /* magic byte that implies allocation */
 126 #define ISFREE ((char) 0x54)    /* magic byte that implies free block */
 127                                 /* this is for error checking only */
 128 #define ISMEMALIGN ((char) 0xd6)  /* Stored before the value returned by
 129                                      memalign, with the rest of the word
 130                                      being the distance to the true
 131                                      beginning of the block.  */
 132
 133 #if !defined (SBRK_DECLARED)
 134 extern char *sbrk ();
 135 #endif /* !SBRK_DECLARED */
 136
 137 #ifdef MALLOC_STATS
 138 /*
 139  * NMALLOC[i] is the difference between the number of mallocs and frees
 140  * for a given block size.  TMALLOC[i] is the total number of mallocs for
 141  * a given block size.  NMORECORE[i] is the total number of calls to
 142  * morecore(i).  NMAL and NFRE are counts of the number of calls to malloc()
 143  * and free(), respectively.  NREALLOC is the total number of calls to
 144  * realloc(); NRCOPY is the number of times realloc() had to allocate new
 145  * memory and copy to it.  NRECURSE is a count of the number of recursive
 146  * calls to malloc() for the same bucket size, which can be caused by calls
 147  * to malloc() from a signal handler.  NSBRK is the number of calls to sbrk()
 148  * (whether by morecore() or for alignment); TSBRK is the total number of
 149  * bytes requested from the kernel with sbrk().  BYTESUSED is the total
 150  * number of bytes consumed by blocks currently in use; BYTESFREE is the
 151  * total number of bytes currently on all of the free lists.  TBSPLIT is
 152  * the number of times a larger block was split to satisfy a smaller request.
 153  * NSPLIT[i] is the number of times a block of size I was split.
 154  * TBCOALESCE is the number of times two adjacent smaller blocks off the free
 155  * list were combined to satisfy a larger request.
 156  */
 157 struct _malstats {
 158   int nmalloc[NBUCKETS];
 159   int tmalloc[NBUCKETS];
 160   int nmorecore[NBUCKETS];
 161   int nmal;
 162   int nfre;
 163   int nrealloc;
 164   int nrcopy;
 165   int nrecurse;
 166   int nsbrk;
 167   bits32_t tsbrk;
 168   bits32_t bytesused;
 169   bits32_t bytesfree;
 170   int tbsplit;
 171   int nsplit[NBUCKETS];
 172   int tbcoalesce;
 173 };
 174
 175 static struct _malstats _mstats;
 176
 177 /* Return statistics describing allocation of blocks of size BLOCKSIZE.
 178    NFREE is the number of free blocks for this allocation size.  NUSED
 179    is the number of blocks in use.  NMAL is the number of requests for
 180    blocks of size BLOCKSIZE.  NMORECORE is the number of times we had
 181    to call MORECORE to repopulate the free list for this bucket.  NSPLIT
 182    is the number of times a block of this size was split to satisfy a
 183    smaller request. */
 184 struct bucket_stats {
 185   u_bits32_t blocksize;
 186   int nfree;
 187   int nused;
 188   int nmal;
 189   int nmorecore;
 190   int nsplit;
 191 };
 192 #endif /* MALLOC_STATS */
 193
 194 /* We have a flag indicating whether memory is allocated, an index in
 195    nextf[], a size field, and a sentinel value to determine whether or
 196    not a caller wrote before the start of allocated memory; to realloc()
 197    memory we either copy mh_nbytes or just change mh_nbytes if there is
 198    enough room in the block for the new size.  Range checking is always
 199    done. */
 200 union mhead {
 201   bits64_t mh_align;                                    /* 8 */
 202   struct {
 203     char     mi_alloc;  /* ISALLOC or ISFREE */         /* 1 */
 204     char     mi_index;  /* index in nextf[] */          /* 1 */
 205     /* Remainder are valid only when block is allocated */
 206     u_bits32_t mi_nbytes;  /* # of bytes allocated */   /* 4 */
 207     u_bits16_t mi_magic2;/* should be == MAGIC2 */      /* 2 */
 208   } minfo;
 209 };
 210 #define mh_alloc        minfo.mi_alloc
 211 #define mh_index        minfo.mi_index
 212 #define mh_nbytes       minfo.mi_nbytes
 213 #define mh_magic2       minfo.mi_magic2
 214
 215 /* Access free-list pointer of a block.
 216    It is stored at block + sizeof (char *).
 217    This is not a field in the minfo structure member of union mhead
 218    because we want sizeof (union mhead)
 219    to describe the overhead for when the block is in use,
 220    and we do not want the free-list pointer to count in that.  */
 221
 222 #define CHAIN(a) \
 223   (*(union mhead **) (sizeof (char *) + (char *) (a)))
 224
 225 #if defined (botch)
 226 extern void botch ();
 227 #else
 228 static void
 229 botch (s)
 230      char *s;
 231 {
 232   fprintf (stderr, "\r\nmalloc: assertion botched: %s\r\n", s);
 233   (void)fflush (stderr);
 234   abort ();
 235 }
 236 #endif /* !botch */
 237
 238 #if !defined (__STRING)
 239 #  if defined (__STDC__)
 240 #    define __STRING(x) #x
 241 #  else
 242 #    define __STRING(x) "x"
 243 #  endif
 244 #endif /* !__STRING */
 245
 246 /* To implement range checking, we write magic values in at the beginning
 247    and end of each allocated block, and make sure they are undisturbed
 248    whenever a free or a realloc occurs. */
 249
 250 /* Written in each of the 4 bytes following the block's real space */
 251 #define MAGIC1 0x55
 252 /* Written in the 2 bytes before the block's real space */
 253 #define MAGIC2 0x5555
 254 #define ASSERT(p) do { if (!(p)) botch(__STRING(p)); } while (0)
 255 #define MSLOP  4                /* 4 bytes extra for MAGIC1s */
 256
 257 /* Minimum and maximum bucket indices for block splitting (and to bound
 258    the search for a block to split). */
 259 #define SPLIT_MIN       3
 260 #define SPLIT_MID       11      /* XXX - was 9 */
 261 #define SPLIT_MAX       14      /* XXX - was 12 */
 262
 263 /* Minimum and maximum bucket indices for block coalescing. */
 264 #define COMBINE_MIN     6
 265 #define COMBINE_MAX     (pagebucket - 1)
 266
 267 #define MIN_COMBINE_FREE        4
 268
 269 /* nextf[i] is free list of blocks of size 2**(i + 3)  */
 270
 271 static union mhead *nextf[NBUCKETS];
 272
 273 /* busy[i] is nonzero while allocation of block size i is in progress.  */
 274
 275 static char busy[NBUCKETS];
 276
 277 static int pagesz;      /* system page size. */
 278 static int pagebucket;  /* bucket for requests a page in size */
 279 static int maxbuck;     /* highest bucket receiving allocation request. */
 280
 281 #if 0
 282 /* Coalesce two adjacent free blocks off the free list for size NU - 1,
 283    as long as there are at least MIN_COMBINE_FREE free blocks and we
 284    can find two adjacent free blocks.  nextf[NU -1] is assumed to not
 285    be busy; the caller (morecore()) checks for this. */
 286 static void
 287 bcoalesce (nu)
 288      register int nu;
 289 {
 290   register union mhead *mp, *mp1, *mp2;
 291   register int nfree, nbuck;
 292   unsigned long siz;
 293
 294   nbuck = nu - 1;
 295   if (nextf[nbuck] == 0)
 296     return;
 297
 298   nfree = 1;
 299   mp1 = nextf[nbuck];
 300   mp = CHAIN (mp1);
 301   mp2 = (union mhead *)0;
 302   while (CHAIN (mp))
 303     {
 304       mp2 = mp1;
 305       mp1 = mp;
 306       mp = CHAIN (mp);
 307       nfree++;
 308       /* We may not want to run all the way through the free list here;
 309          if we do not, we need to check a threshold value here and break
 310          if nfree exceeds it. */
 311     }
 312   if (nfree < MIN_COMBINE_FREE)
 313     return;
 314   /* OK, now we have mp1 pointing to the block we want to add to nextf[NU].
 315      CHAIN(mp2) must equal mp1.  Check that mp1 and mp are adjacent. */
 316   if (CHAIN(mp2) != mp1)
 317     botch ("bcoalesce: CHAIN(mp2) != mp1");
 318   siz = 1 << (nbuck + 3);
 319   if (CHAIN (mp1) != (union mhead *)((char *)mp1 + siz))
 320     return;     /* not adjacent */
 321
 322 #ifdef MALLOC_STATS
 323   _mstats.tbcoalesce++;
 324 #endif
 325
 326   /* Since they are adjacent, remove them from the free list */
 327   CHAIN (mp2) = CHAIN (mp);
 328
 329   /* And add the combined two blocks to nextf[NU]. */
 330   mp1->mh_alloc = ISFREE;
 331   mp1->mh_index = nu;
 332   CHAIN (mp1) = nextf[nu];
 333   nextf[nu] = mp1;
 334 }
 335 #endif
 336
 337 /* Split a block at index > NU (but less than SPLIT_MAX) into a set of
 338    blocks of the correct size, and attach them to nextf[NU].  nextf[NU]
 339    is assumed to be empty.  Must be called with signals blocked (e.g.,
 340    by morecore()). */
 341 static void
 342 bsplit (nu)
 343      register int nu;
 344 {
 345   register union mhead *mp;
 346   int nbuck, nblks, split_max;
 347   unsigned long siz;
 348
 349   split_max = (maxbuck > SPLIT_MAX) ? maxbuck : SPLIT_MAX;
 350
 351   if (nu >= SPLIT_MID)
 352     {
 353       for (nbuck = split_max; nbuck > nu; nbuck--)
 354         {
 355           if (busy[nbuck] || nextf[nbuck] == 0)
 356             continue;
 357           break;
 358         }
 359     }
 360   else
 361     {
 362       for (nbuck = nu + 1; nbuck <= split_max; nbuck++)
 363         {
 364           if (busy[nbuck] || nextf[nbuck] == 0)
 365             continue;
 366           break;
 367         }
 368     }
 369
 370   if (nbuck > split_max || nbuck <= nu)
 371     return;
 372
 373   /* XXX might want to split only if nextf[nbuck] has >= 2 blocks free
 374      and nbuck is below some threshold. */
 375
 376 #ifdef MALLOC_STATS
 377   _mstats.tbsplit++;
 378   _mstats.nsplit[nbuck]++;
 379 #endif
 380
 381   /* Figure out how many blocks we'll get. */
 382   siz = (1 << (nu + 3));
 383   nblks = (1 << (nbuck + 3)) / siz;
 384
 385   /* Remove the block from the chain of larger blocks. */
 386   mp = nextf[nbuck];
 387   nextf[nbuck] = CHAIN (mp);
 388
 389   /* Split the block and put it on the requested chain. */
 390   nextf[nu] = mp;
 391   while (1)
 392     {
 393       mp->mh_alloc = ISFREE;
 394       mp->mh_index = nu;
 395       if (--nblks <= 0) break;
 396       CHAIN (mp) = (union mhead *)((char *)mp + siz);
 397       mp = (union mhead *)((char *)mp + siz);
 398     }
 399   CHAIN (mp) = 0;
 400 }
 401
 402 static void
 403 morecore (nu)                   /* ask system for more memory */
 404      register int nu;           /* size index to get more of  */
 405 {
 406   register union mhead *mp;
 407   register int nblks;
 408   register long siz;
 409   long sbrk_amt;                /* amount to get via sbrk() */
 410
 411   /* Block all signals in case we are executed from a signal handler. */
 412 #if defined (HAVE_BSD_SIGNALS)
 413   int oldmask;
 414   oldmask = sigsetmask (-1);
 415 #else
 416 #  if defined (HAVE_POSIX_SIGNALS)
 417   sigset_t set, oset;
 418   sigfillset (&set);
 419   sigemptyset (&oset);
 420   sigprocmask (SIG_BLOCK, &set, &oset);
 421 #  endif /* HAVE_POSIX_SIGNALS */
 422 #endif /* HAVE_BSD_SIGNALS */
 423
 424   siz = 1 << (nu + 3);  /* size of desired block for nextf[nu] */
 425
 426   if (siz < 0)
 427     goto morecore_done;         /* oops */
 428
 429 #ifdef MALLOC_STATS
 430   _mstats.nmorecore[nu]++;
 431 #endif
 432
 433   /* Try to split a larger block here, if we're within the range of sizes
 434      to split. */
 435 #if 0
 436   if (nu >= SPLIT_MIN && nu < SPLIT_MAX)
 437 #else
 438   if (nu >= SPLIT_MIN)
 439 #endif
 440     {
 441       bsplit (nu);
 442       if (nextf[nu] != 0)
 443         goto morecore_done;
 444     }
 445
 446 #if 0
 447   /* Try to coalesce two adjacent blocks from the free list on nextf[nu - 1],
 448      if we can, and we're withing the range of the block coalescing limits. */
 449   if (nu >= COMBINE_MIN && nu < COMBINE_MAX && busy[nu - 1] == 0 && nextf[nu - 1])
 450     {
 451       bcoalesce (nu);
 452       if (nextf[nu] != 0)
 453         goto morecore_done;
 454     }
 455 #endif
 456
 457   /* Take at least a page, and figure out how many blocks of the requested
 458      size we're getting. */
 459   if (siz <= pagesz)
 460     {
 461       sbrk_amt = pagesz;
 462       nblks = sbrk_amt / siz;
 463     }
 464   else
 465     {
 466       /* We always want to request an integral multiple of the page size
 467          from the kernel, so let's compute whether or not `siz' is such
 468          an amount.  If it is, we can just request it.  If not, we want
 469          the smallest integral multiple of pagesize that is larger than
 470          `siz' and will satisfy the request. */
 471       sbrk_amt = siz % pagesz;
 472       if (sbrk_amt == 0)
 473         sbrk_amt = siz;
 474       else
 475         sbrk_amt = siz + pagesz - sbrk_amt;
 476       nblks = 1;
 477     }
 478
 479 #ifdef MALLOC_STATS
 480   _mstats.nsbrk++;
 481   _mstats.tsbrk += sbrk_amt;
 482 #endif
 483
 484   mp = (union mhead *) sbrk (sbrk_amt);
 485
 486   /* Totally out of memory. */
 487   if ((long)mp == -1)
 488     goto morecore_done;
 489
 490   /* shouldn't happen, but just in case -- require 8-byte alignment */
 491   if ((long)mp & 7)
 492     {
 493       mp = (union mhead *) (((long)mp + 8) & ~7);
 494       nblks--;
 495     }
 496
 497   /* save new header and link the nblks blocks together */
 498   nextf[nu] = mp;
 499   while (1)
 500     {
 501       mp->mh_alloc = ISFREE;
 502       mp->mh_index = nu;
 503       if (--nblks <= 0) break;
 504       CHAIN (mp) = (union mhead *)((char *)mp + siz);
 505       mp = (union mhead *)((char *)mp + siz);
 506     }
 507   CHAIN (mp) = 0;
 508
 509 morecore_done:
 510 #if defined (HAVE_BSD_SIGNALS)
 511   sigsetmask (oldmask);
 512 #else
 513 #  if defined (HAVE_POSIX_SIGNALS)
 514   sigprocmask (SIG_SETMASK, &oset, (sigset_t *)NULL);
 515 #  else
 516   ; /* nothing to do, but need a null statement before the brace */
 517 #  endif
 518 #endif /* HAVE_BSD_SIGNALS */
 519 }
 520
 521 #if defined (MEMSCRAMBLE) || !defined (NO_CALLOC)
 522 static char *
 523 zmemset (s, c, n)
 524      char *s;
 525      int c;
 526      register int n;
 527 {
 528   register char *sp;
 529
 530   sp = s;
 531   while (--n >= 0)
 532     *sp++ = c;
 533   return (s);
 534 }
 535 #endif /* MEMSCRAMBLE || !NO_CALLOC */
 536
 537 static void
 538 malloc_debug_dummy ()
 539 {
 540   write (1, "malloc_debug_dummy\n", 19);
 541 }
 542
 543 PTR_T
 544 malloc (n)              /* get a block */
 545      size_t n;
 546 {
 547   register union mhead *p;
 548   register long nbytes;
 549   register int nunits;
 550
 551   /* Get the system page size and align break pointer so everything will
 552      be page-aligned.  The page size must be at least 1K -- anything
 553      smaller is increased. */
 554   if (pagesz == 0)
 555     {
 556       register long sbrk_needed;
 557
 558       pagesz = getpagesize ();
 559       if (pagesz < 1024)
 560         pagesz = 1024;
 561       /* OK, how much do we need to allocate to make things page-aligned?
 562          This partial page is wasted space.  Once we figure out how much
 563          to advance the break pointer, go ahead and do it. */
 564       sbrk_needed = pagesz - ((long)sbrk (0) & (pagesz - 1));   /* sbrk(0) % pagesz */
 565       if (sbrk_needed < 0)
 566         sbrk_needed += pagesz;
 567       /* Now allocate the wasted space. */
 568       if (sbrk_needed)
 569         {
 570 #ifdef MALLOC_STATS
 571           _mstats.nsbrk++;
 572           _mstats.tsbrk += sbrk_needed;
 573 #endif
 574           if ((long)sbrk (sbrk_needed) == -1)
 575             return (NULL);
 576         }
 577       nunits = 0;
 578       nbytes = 8;
 579       while (pagesz > nbytes)
 580         {
 581           nbytes <<= 1;
 582           nunits++;
 583         }
 584       pagebucket = nunits;
 585     }
 586
 587   /* Figure out how many bytes are required, rounding up to the nearest
 588      multiple of 4, then figure out which nextf[] area to use.  Try to
 589      be smart about where to start searching -- if the number of bytes
 590      needed is greater than the page size, we can start at pagebucket. */
 591   nbytes = (n + sizeof *p + MSLOP + 3) & ~3;
 592   nunits = 0;
 593   if (nbytes <= (pagesz >> 1))
 594     {
 595       register unsigned int shiftr;
 596
 597       shiftr = (nbytes - 1) >> 2;       /* == (nbytes - 1) / 4 */
 598       while (shiftr >>= 1)              /* == (nbytes - 1) / {8,16,32,...} */
 599         nunits++;
 600     }
 601   else
 602     {
 603       register u_bits32_t amt;
 604
 605       nunits = pagebucket;
 606       amt = pagesz;
 607       while (nbytes > amt)
 608         {
 609           amt <<= 1;
 610           nunits++;
 611         }
 612     }
 613
 614   /* In case this is reentrant use of malloc from signal handler,
 615      pick a block size that no other malloc level is currently
 616      trying to allocate.  That's the easiest harmless way not to
 617      interfere with the other level of execution.  */
 618 #ifdef MALLOC_STATS
 619   if (busy[nunits]) _mstats.nrecurse++;
 620 #endif
 621   while (busy[nunits]) nunits++;
 622   busy[nunits] = 1;
 623
 624   if (nunits > maxbuck)
 625     maxbuck = nunits;
 626
 627   /* If there are no blocks of the appropriate size, go get some */
 628   if (nextf[nunits] == 0)
 629     morecore (nunits);
 630
 631   /* Get one block off the list, and set the new list head */
 632   if ((p = nextf[nunits]) == NULL)
 633     {
 634       busy[nunits] = 0;
 635       return NULL;
 636     }
 637   nextf[nunits] = CHAIN (p);
 638   busy[nunits] = 0;
 639
 640   /* Check for free block clobbered */
 641   /* If not for this check, we would gobble a clobbered free chain ptr
 642      and bomb out on the NEXT allocate of this size block */
 643   if (p->mh_alloc != ISFREE || p->mh_index != nunits)
 644     botch ("malloc: block on free list clobbered");
 645
 646   /* Fill in the info, and if range checking, set up the magic numbers */
 647   p->mh_alloc = ISALLOC;
 648   p->mh_nbytes = n;
 649   p->mh_magic2 = MAGIC2;
 650   {
 651     register char  *m = (char *) (p + 1) + n;
 652
 653     *m++ = MAGIC1, *m++ = MAGIC1, *m++ = MAGIC1, *m = MAGIC1;
 654   }
 655
 656 #ifdef MEMSCRAMBLE
 657   zmemset ((char *)(p + 1), 0xdf, n);   /* scramble previous contents */
 658 #endif
 659 #ifdef MALLOC_STATS
 660   _mstats.nmalloc[nunits]++;
 661   _mstats.tmalloc[nunits]++;
 662   _mstats.nmal++;
 663 #endif /* MALLOC_STATS */
 664   return (char *) (p + 1);      /* XXX - should be cast to PTR_T? */
 665 }
 666
 667 void
 668 free (mem)
 669      PTR_T mem;
 670 {
 671   register union mhead *p;
 672   register char *ap;
 673   register int nunits;
 674
 675   if ((ap = (char *)mem) == 0)
 676     return;
 677
 678   p = (union mhead *) ap - 1;
 679
 680   if (p->mh_alloc == ISMEMALIGN)
 681     {
 682       ap -= p->mh_nbytes;
 683       p = (union mhead *) ap - 1;
 684     }
 685
 686   if (p->mh_alloc != ISALLOC)
 687     {
 688       if (p->mh_alloc == ISFREE)
 689         botch ("free: called with already freed block argument");
 690       else
 691         botch ("free: called with unallocated block argument");
 692     }
 693
 694   ASSERT (p->mh_magic2 == MAGIC2);
 695   ap += p->mh_nbytes;
 696   ASSERT (*ap++ == MAGIC1); ASSERT (*ap++ == MAGIC1);
 697   ASSERT (*ap++ == MAGIC1); ASSERT (*ap   == MAGIC1);
 698
 699 #ifdef MEMSCRAMBLE
 700   zmemset (mem, 0xcf, p->mh_nbytes);
 701 #endif
 702
 703   nunits = p->mh_index;
 704
 705   ASSERT (nunits < NBUCKETS);
 706   p->mh_alloc = ISFREE;
 707
 708 #if 0
 709   if (busy[nunits] == 1)
 710     botch ("calling free %d while in malloc for %d", nunits, nunits);
 711 #endif
 712
 713   /* Protect against signal handlers calling malloc.  */
 714   busy[nunits] = 1;
 715   /* Put this block on the free list.  */
 716   CHAIN (p) = nextf[nunits];
 717   nextf[nunits] = p;
 718   busy[nunits] = 0;
 719
 720 #ifdef MALLOC_STATS
 721   _mstats.nmalloc[nunits]--;
 722   _mstats.nfre++;
 723 #endif /* MALLOC_STATS */
 724 }
 725
 726 PTR_T
 727 realloc (mem, n)
 728      PTR_T mem;
 729      register size_t n;
 730 {
 731   register union mhead *p;
 732   register u_bits32_t tocopy;
 733   register unsigned int nbytes;
 734   register int nunits;
 735   register char *m;
 736
 737 #ifdef MALLOC_STATS
 738   _mstats.nrealloc++;
 739 #endif
 740
 741   if (n == 0)
 742     {
 743       free (mem);
 744       return (NULL);
 745     }
 746   if ((p = (union mhead *) mem) == 0)
 747     return malloc (n);
 748   p--;
 749   nunits = p->mh_index;
 750   ASSERT (p->mh_alloc == ISALLOC);
 751   ASSERT (p->mh_magic2 == MAGIC2);
 752
 753   m = (char *)mem + (tocopy = p->mh_nbytes);
 754   ASSERT (*m++ == MAGIC1); ASSERT (*m++ == MAGIC1);
 755   ASSERT (*m++ == MAGIC1); ASSERT (*m   == MAGIC1);
 756
 757   /* See if desired size rounds to same power of 2 as actual size. */
 758   nbytes = (n + sizeof *p + MSLOP + 7) & ~7;
 759
 760   /* If ok, use the same block, just marking its size as changed.  */
 761   if (nbytes > (4 << nunits) && nbytes <= (8 << nunits))
 762     {
 763       m = (char *)mem + tocopy;
 764       *m++ = 0;  *m++ = 0;  *m++ = 0;  *m++ = 0;
 765       p->mh_nbytes = n;
 766       m = (char *)mem + n;
 767       *m++ = MAGIC1;  *m++ = MAGIC1;  *m++ = MAGIC1;  *m++ = MAGIC1;
 768       return mem;
 769     }
 770
 771 #ifdef MALLOC_STATS
 772   _mstats.nrcopy++;
 773 #endif
 774
 775   if (n < tocopy)
 776     tocopy = n;
 777
 778   if ((m = malloc (n)) == 0)
 779     return 0;
 780   FASTCOPY (mem, m, tocopy);
 781   free (mem);
 782   return m;
 783 }
 784
 785 PTR_T
 786 memalign (alignment, size)
 787      unsigned int alignment;
 788      size_t size;
 789 {
 790   register char *ptr;
 791   register char *aligned;
 792   register union mhead *p;
 793
 794   ptr = malloc (size + alignment);
 795
 796   if (ptr == 0)
 797     return 0;
 798   /* If entire block has the desired alignment, just accept it.  */
 799   if (((int) ptr & (alignment - 1)) == 0)
 800     return ptr;
 801   /* Otherwise, get address of byte in the block that has that alignment.  */
 802   aligned = (char *) (((int) ptr + alignment - 1) & -alignment);
 803
 804   /* Store a suitable indication of how to free the block,
 805      so that free can find the true beginning of it.  */
 806   p = (union mhead *) aligned - 1;
 807   p->mh_nbytes = aligned - ptr;
 808   p->mh_alloc = ISMEMALIGN;
 809   return aligned;
 810 }
 811
 812 #if !defined (HPUX)
 813 /* This runs into trouble with getpagesize on HPUX, and Multimax machines.
 814    Patching out seems cleaner than the ugly fix needed.  */
 815 PTR_T
 816 valloc (size)
 817      size_t size;
 818 {
 819   return memalign (getpagesize (), size);
 820 }
 821 #endif /* !HPUX */
 822
 823 #ifndef NO_CALLOC
 824 PTR_T
 825 calloc (n, s)
 826      size_t n, s;
 827 {
 828   size_t total;
 829   char *result;
 830
 831   total = n * s;
 832   result = malloc (total);
 833   if (result)
 834     zmemset (result, 0, total);
 835   return result;
 836 }
 837
 838 void
 839 cfree (p)
 840      PTR_T p;
 841 {
 842   free (p);
 843 }
 844 #endif /* !NO_CALLOC */
 845
 846 #ifdef MALLOC_STATS
 847
 848 struct bucket_stats
 849 malloc_bucket_stats (size)
 850      int size;
 851 {
 852   struct bucket_stats v;
 853   register union mhead *p;
 854
 855   v.nfree = 0;
 856
 857   if (size < 0 || size >= NBUCKETS)
 858     {
 859       v.blocksize = 0;
 860       v.nused = v.nmal = v.nmorecore = v.nsplit = 0;
 861       return v;
 862     }
 863
 864   v.blocksize = 1 << (size + 3);
 865   v.nused = _mstats.nmalloc[size];
 866   v.nmal = _mstats.tmalloc[size];
 867   v.nmorecore = _mstats.nmorecore[size];
 868   v.nsplit = _mstats.nsplit[size];
 869
 870   for (p = nextf[size]; p; p = CHAIN (p))
 871     v.nfree++;
 872
 873   return v;
 874 }
 875
 876 /* Return a copy of _MSTATS, with two additional fields filled in:
 877    BYTESFREE is the total number of bytes on free lists.  BYTESUSED
 878    is the total number of bytes in use.  These two fields are fairly
 879    expensive to compute, so we do it only when asked to. */
 880 struct _malstats
 881 malloc_stats ()
 882 {
 883   struct _malstats result;
 884   struct bucket_stats v;
 885   register int i;
 886
 887   result = _mstats;
 888   result.bytesused = result.bytesfree = 0;
 889   for (i = 0; i < NBUCKETS; i++)
 890     {
 891       v = malloc_bucket_stats (i);
 892       result.bytesfree += v.nfree * v.blocksize;
 893       result.bytesused += v.nused * v.blocksize;
 894     }
 895   return (result);
 896 }
 897
 898 static void
 899 _print_malloc_stats (s, fp)
 900      char *s;
 901      FILE *fp;
 902 {
 903   register int i;
 904   int totused, totfree;
 905   struct bucket_stats v;
 906
 907   fprintf (fp, "Memory allocation statistics: %s\n\tsize\tfree\tin use\ttotal\tmorecore\tsplit\n", s ? s : "");
 908   for (i = totused = totfree = 0; i < NBUCKETS; i++)
 909     {
 910       v = malloc_bucket_stats (i);
 911       fprintf (fp, "%12lu\t%4d\t%6d\t%5d\t%8d\t%5d\n", v.blocksize, v.nfree, v.nused, v.nmal, v.nmorecore, v.nsplit);
 912       totfree += v.nfree * v.blocksize;
 913       totused += v.nused * v.blocksize;
 914     }
 915   fprintf (fp, "\nTotal bytes in use: %d, total bytes free: %d\n",
 916            totused, totfree);
 917   fprintf (fp, "Total mallocs: %d, total frees: %d, total reallocs: %d (%d copies)\n",
 918            _mstats.nmal, _mstats.nfre, _mstats.nrealloc, _mstats.nrcopy);
 919   fprintf (fp, "Total sbrks: %d, total bytes via sbrk: %d\n",
 920            _mstats.nsbrk, _mstats.tsbrk);
 921   fprintf (fp, "Total blocks split: %d, total block coalesces: %d\n",
 922            _mstats.tbsplit, _mstats.tbcoalesce);
 923 }
 924
 925 void
 926 print_malloc_stats (s)
 927 {
 928   _print_malloc_stats (s, stderr);
 929 }
 930
 931 #define TRACEROOT "/var/tmp/maltrace/trace."
 932 extern char *inttostr ();
 933
 934 void
 935 trace_malloc_stats (s)
 936 {
 937   char ibuf[32], *ip;
 938   char fname[64];
 939   int p;
 940   FILE *fp;
 941
 942   p = (int)getpid();
 943   ip = inttostr(p, ibuf, sizeof(ibuf));
 944   strcpy (fname, TRACEROOT);
 945   strcat (fname, ip);
 946   fp = fopen(fname, "w");
 947   if (fp)
 948     {
 949       _print_malloc_stats (s, fp);
 950       fflush(fp);
 951       fclose(fp);
 952     }
 953 }
 954 #endif /* MALLOC_STATS */