1 /* malloc.c - dynamic memory allocation for bash. */
3 /* Copyright (C) 1985, 1987, 1997 Free Software Foundation, Inc.
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)
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.
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.
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! */
24 * @(#)nmalloc.c 1 (Caltech) 2/21/82
26 * U of M Modified: 20 Jun 1983 ACT: strange hacks for Emacs
28 * Nov 1983, Mike@BRL, Added support for 4.1C/4.2 BSD.
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.
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.
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.
48 #define MALLOC_STATS /* for the time being */
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
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)
64 #if defined (HAVE_CONFIG_H)
66 #endif /* HAVE_CONFIG_H */
69 # include "bashtypes.h"
71 # include <sys/types.h>
74 #if defined (HAVE_UNISTD_H)
78 /* Determine which kind of system this is. */
81 #if defined (HAVE_STRING_H)
87 #if defined (MALLOC_STATS) || !defined (botch)
89 #endif /* MALLOC_STATS || !botch */
91 /* Define getpagesize () if the system does not. */
92 #ifndef HAVE_GETPAGESIZE
93 # include "getpagesize.h"
97 # define FASTCOPY(s, d, n) __builtin_memcpy (d, s, n)
99 # if !defined (HAVE_BCOPY)
100 # if !defined (HAVE_MEMMOVE)
101 # define FASTCOPY(s, d, n) memcpy (d, s, n)
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__ */
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. */
124 #if !defined (SBRK_DECLARED)
125 extern char *sbrk ();
126 #endif /* !SBRK_DECLARED */
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.
148 int nmalloc[NBUCKETS];
149 int tmalloc[NBUCKETS];
150 int nmorecore[NBUCKETS];
164 static struct _malstats _mstats;
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 {
178 #endif /* MALLOC_STATS */
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
187 union mhead *mh_align;
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 */
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
201 /* Access free-list pointer of a block.
202 It is stored at block + sizeof (char *).
203 This is not a field in the mhead structure
204 because we want sizeof (struct 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. */
209 (*(union mhead **) (sizeof (char *) + (char *) (a)))
212 extern void botch ();
218 fprintf (stderr, "\r\nmalloc: assertion botched: %s\r\n", s);
219 (void)fflush (stderr);
224 #if !defined (__STRING)
225 # if defined (__STDC__)
226 # define __STRING(x) #x
228 # define __STRING(x) "x"
230 #endif /* !__STRING */
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. */
236 /* Written in each of the 4 bytes following the block's real space */
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 */
243 /* Minimum and maximum bucket indices for block splitting (and to bound
244 the search for a block to split). */
249 /* Minimum and maximum bucket indices for block coalescing. */
250 #define COMBINE_MIN 6
251 #define COMBINE_MAX (pagebucket - 1)
253 #define MIN_COMBINE_FREE 4
255 /* nextf[i] is free list of blocks of size 2**(i + 3) */
257 static union mhead *nextf[NBUCKETS];
259 /* busy[i] is nonzero while allocation of block size i is in progress. */
261 static char busy[NBUCKETS];
263 static int pagesz; /* system page size. */
264 static int pagebucket; /* bucket for requests a page in size */
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. */
275 register union mhead *mp, *mp1, *mp2;
276 register int nfree, nbuck;
280 if (nextf[nbuck] == 0)
286 mp2 = (union mhead *)0;
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. */
297 if (nfree < MIN_COMBINE_FREE)
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 */
308 _mstats.nbcoalesce++;
311 /* Since they are adjacent, remove them from the free list */
312 CHAIN (mp2) = CHAIN (mp);
314 /* And add the combined two blocks to nextf[NU]. */
315 mp1->mh_alloc = ISFREE;
317 CHAIN (mp1) = nextf[nu];
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.,
330 register union mhead *mp;
336 for (nbuck = SPLIT_MAX; nbuck > nu; nbuck--)
338 if (busy[nbuck] || nextf[nbuck] == 0)
345 for (nbuck = nu + 1; nbuck <= SPLIT_MAX; nbuck++)
347 if (busy[nbuck] || nextf[nbuck] == 0)
353 if (nbuck > SPLIT_MAX || nbuck <= nu)
356 /* XXX might want to split only if nextf[nbuck] has >= 2 blocks free
357 and nbuck is below some threshold. */
363 /* Figure out how many blocks we'll get. */
364 siz = (1 << (nu + 3));
365 nblks = (1 << (nbuck + 3)) / siz;
367 /* Remove the block from the chain of larger blocks. */
369 nextf[nbuck] = CHAIN (mp);
371 /* Split the block and put it on the requested chain. */
375 mp->mh_alloc = ISFREE;
377 if (--nblks <= 0) break;
378 CHAIN (mp) = (union mhead *)((char *)mp + siz);
379 mp = (union mhead *)((char *)mp + siz);
385 morecore (nu) /* ask system for more memory */
386 register int nu; /* size index to get more of */
388 register union mhead *mp;
391 long sbrk_amt; /* amount to get via sbrk() */
393 /* Block all signals in case we are executed from a signal handler. */
394 #if defined (HAVE_BSD_SIGNALS)
396 oldmask = sigsetmask (-1);
398 # if defined (HAVE_POSIX_SIGNALS)
402 sigprocmask (SIG_BLOCK, &set, &oset);
403 # endif /* HAVE_POSIX_SIGNALS */
404 #endif /* HAVE_BSD_SIGNALS */
406 siz = 1 << (nu + 3); /* size of desired block for nextf[nu] */
412 _mstats.nmorecore[nu]++;
415 /* Try to split a larger block here, if we're within the range of sizes
417 if (nu >= SPLIT_MIN && nu < SPLIT_MAX)
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])
435 /* Take at least a page, and figure out how many blocks of the requested
436 size we're getting. */
440 nblks = sbrk_amt / siz;
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;
453 sbrk_amt = siz + pagesz - sbrk_amt;
459 _mstats.tsbrk += sbrk_amt;
462 mp = (union mhead *) sbrk (sbrk_amt);
464 /* Totally out of memory. */
468 /* shouldn't happen, but just in case -- require 8-byte alignment */
471 mp = (union mhead *) (((long)mp + 8) & ~7);
475 /* save new header and link the nblks blocks together */
479 mp->mh_alloc = ISFREE;
481 if (--nblks <= 0) break;
482 CHAIN (mp) = (union mhead *)((char *)mp + siz);
483 mp = (union mhead *)((char *)mp + siz);
488 #if defined (HAVE_BSD_SIGNALS)
489 sigsetmask (oldmask);
491 # if defined (HAVE_POSIX_SIGNALS)
492 sigprocmask (SIG_SETMASK, &oset, (sigset_t *)NULL);
494 #endif /* HAVE_BSD_SIGNALS */
497 #if defined (MEMSCRAMBLE) || !defined (NO_CALLOC)
511 #endif /* MEMSCRAMBLE || !NO_CALLOC */
514 malloc_debug_dummy ()
520 malloc (n) /* get a block */
523 register union mhead *p;
524 register long nbytes;
527 /* Get the system page size and align break pointer so everything will
528 be page-aligned. The page size must be at least 1K -- anything
529 smaller is increased. */
532 register long sbrk_needed;
534 pagesz = getpagesize ();
537 /* OK, how much do we need to allocate to make things page-aligned?
538 This partial page is wasted space. Once we figure out how much
539 to advance the break pointer, go ahead and do it. */
540 sbrk_needed = pagesz - ((long)sbrk (0) & (pagesz - 1)); /* sbrk(0) % pagesz */
542 sbrk_needed += pagesz;
543 /* Now allocate the wasted space. */
548 _mstats.tsbrk += sbrk_needed;
550 if ((long)sbrk (sbrk_needed) == -1)
555 while (pagesz > nbytes)
563 /* Figure out how many bytes are required, rounding up to the nearest
564 multiple of 4, then figure out which nextf[] area to use. Try to
565 be smart about where to start searching -- if the number of bytes
566 needed is greater than the page size, we can start at pagebucket. */
567 nbytes = (n + sizeof *p + MSLOP + 3) & ~3;
569 if (nbytes <= (pagesz >> 1))
571 register unsigned int shiftr;
573 shiftr = (nbytes - 1) >> 2; /* == (nbytes - 1) / 4 */
574 while (shiftr >>= 1) /* == (nbytes - 1) / {8,16,32,...} */
579 register u_int32_t amt;
590 /* In case this is reentrant use of malloc from signal handler,
591 pick a block size that no other malloc level is currently
592 trying to allocate. That's the easiest harmless way not to
593 interfere with the other level of execution. */
595 if (busy[nunits]) _mstats.nrecurse++;
597 while (busy[nunits]) nunits++;
600 /* If there are no blocks of the appropriate size, go get some */
601 if (nextf[nunits] == 0)
604 /* Get one block off the list, and set the new list head */
605 if ((p = nextf[nunits]) == NULL)
610 nextf[nunits] = CHAIN (p);
613 /* Check for free block clobbered */
614 /* If not for this check, we would gobble a clobbered free chain ptr
615 and bomb out on the NEXT allocate of this size block */
616 if (p->mh_alloc != ISFREE || p->mh_index != nunits)
617 botch ("malloc: block on free list clobbered");
619 /* Fill in the info, and if range checking, set up the magic numbers */
620 p->mh_alloc = ISALLOC;
622 p->mh_magic2 = MAGIC2;
624 register char *m = (char *) (p + 1) + n;
626 *m++ = MAGIC1, *m++ = MAGIC1, *m++ = MAGIC1, *m = MAGIC1;
630 zmemset ((char *)(p + 1), 0xdf, n); /* scramble previous contents */
633 _mstats.nmalloc[nunits]++;
634 _mstats.tmalloc[nunits]++;
636 #endif /* MALLOC_STATS */
637 return (char *) (p + 1);
644 register union mhead *p;
651 p = (union mhead *) ap - 1;
653 if (p->mh_alloc == ISMEMALIGN)
656 p = (union mhead *) ap - 1;
659 if (p->mh_alloc != ISALLOC)
661 if (p->mh_alloc == ISFREE)
662 botch ("free: called with already freed block argument");
664 botch ("free: called with unallocated block argument");
667 ASSERT (p->mh_magic2 == MAGIC2);
669 ASSERT (*ap++ == MAGIC1); ASSERT (*ap++ == MAGIC1);
670 ASSERT (*ap++ == MAGIC1); ASSERT (*ap == MAGIC1);
673 zmemset (mem, 0xcf, p->mh_nbytes);
676 nunits = p->mh_index;
678 ASSERT (nunits < NBUCKETS);
679 p->mh_alloc = ISFREE;
681 /* Protect against signal handlers calling malloc. */
683 /* Put this block on the free list. */
684 CHAIN (p) = nextf[nunits];
689 _mstats.nmalloc[nunits]--;
691 #endif /* MALLOC_STATS */
699 register union mhead *p;
700 register u_int32_t tocopy;
701 register unsigned int nbytes;
714 if ((p = (union mhead *) mem) == 0)
717 nunits = p->mh_index;
718 ASSERT (p->mh_alloc == ISALLOC);
719 ASSERT (p->mh_magic2 == MAGIC2);
721 m = mem + (tocopy = p->mh_nbytes);
722 ASSERT (*m++ == MAGIC1); ASSERT (*m++ == MAGIC1);
723 ASSERT (*m++ == MAGIC1); ASSERT (*m == MAGIC1);
725 /* See if desired size rounds to same power of 2 as actual size. */
726 nbytes = (n + sizeof *p + MSLOP + 7) & ~7;
728 /* If ok, use the same block, just marking its size as changed. */
729 if (nbytes > (4 << nunits) && nbytes <= (8 << nunits))
732 *m++ = 0; *m++ = 0; *m++ = 0; *m++ = 0;
735 *m++ = MAGIC1; *m++ = MAGIC1; *m++ = MAGIC1; *m++ = MAGIC1;
746 if ((m = malloc (n)) == 0)
748 FASTCOPY (mem, m, tocopy);
754 memalign (alignment, size)
755 unsigned int alignment;
759 register char *aligned;
760 register union mhead *p;
762 ptr = malloc (size + alignment);
766 /* If entire block has the desired alignment, just accept it. */
767 if (((int) ptr & (alignment - 1)) == 0)
769 /* Otherwise, get address of byte in the block that has that alignment. */
770 aligned = (char *) (((int) ptr + alignment - 1) & -alignment);
772 /* Store a suitable indication of how to free the block,
773 so that free can find the true beginning of it. */
774 p = (union mhead *) aligned - 1;
775 p->mh_nbytes = aligned - ptr;
776 p->mh_alloc = ISMEMALIGN;
781 /* This runs into trouble with getpagesize on HPUX, and Multimax machines.
782 Patching out seems cleaner than the ugly fix needed. */
783 #if defined (__STDC__)
791 return memalign (getpagesize (), size);
804 result = malloc (total);
806 zmemset (result, 0, total);
816 #endif /* !NO_CALLOC */
821 malloc_bucket_stats (size)
824 struct bucket_stats v;
825 register union mhead *p;
829 if (size < 0 || size >= NBUCKETS)
832 v.nused = v.nmal = 0;
836 v.blocksize = 1 << (size + 3);
837 v.nused = _mstats.nmalloc[size];
838 v.nmal = _mstats.tmalloc[size];
839 v.nmorecore = _mstats.nmorecore[size];
841 for (p = nextf[size]; p; p = CHAIN (p))
847 /* Return a copy of _MSTATS, with two additional fields filled in:
848 BYTESFREE is the total number of bytes on free lists. BYTESUSED
849 is the total number of bytes in use. These two fields are fairly
850 expensive to compute, so we do it only when asked to. */
854 struct _malstats result;
855 struct bucket_stats v;
859 result.bytesused = result.bytesfree = 0;
860 for (i = 0; i < NBUCKETS; i++)
862 v = malloc_bucket_stats (i);
863 result.bytesfree += v.nfree * v.blocksize;
864 result.bytesused += v.nused * v.blocksize;
870 print_malloc_stats (s)
874 int totused, totfree;
875 struct bucket_stats v;
877 fprintf (stderr, "Memory allocation statistics: %s\n\tsize\tfree\tin use\ttotal\tmorecore\n", s ? s : "");
878 for (i = totused = totfree = 0; i < NBUCKETS; i++)
880 v = malloc_bucket_stats (i);
881 fprintf (stderr, "%12lu\t%4d\t%6d\t%5d\t%8d\n", v.blocksize, v.nfree, v.nused, v.nmal, v.nmorecore);
882 totfree += v.nfree * v.blocksize;
883 totused += v.nused * v.blocksize;
885 fprintf (stderr, "\nTotal bytes in use: %d, total bytes free: %d\n",
887 fprintf (stderr, "Total mallocs: %d, total frees: %d, total reallocs: %d (%d copies)\n",
888 _mstats.nmal, _mstats.nfre, _mstats.nrealloc, _mstats.nrcopy);
889 fprintf (stderr, "Total sbrks: %d, total bytes via sbrk: %d\n",
890 _mstats.nsbrk, _mstats.tsbrk);
891 fprintf (stderr, "Total blocks split: %d, total block coalesces: %d\n",
892 _mstats.nbsplit, _mstats.nbcoalesce);
894 #endif /* MALLOC_STATS */