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