]>
git.ipfire.org Git - thirdparty/bash.git/blob - lib/malloc/malloc.c
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 bits64_t mh_align
; /* 8 */
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 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. */
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 ; /* nothing to do, but need a null statement before the brace */
496 #endif /* HAVE_BSD_SIGNALS */
499 #if defined (MEMSCRAMBLE) || !defined (NO_CALLOC)
513 #endif /* MEMSCRAMBLE || !NO_CALLOC */
516 malloc_debug_dummy ()
522 malloc (n
) /* get a block */
525 register union mhead
*p
;
526 register long nbytes
;
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. */
534 register long sbrk_needed
;
536 pagesz
= getpagesize ();
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 */
544 sbrk_needed
+= pagesz
;
545 /* Now allocate the wasted space. */
550 _mstats
.tsbrk
+= sbrk_needed
;
552 if ((long)sbrk (sbrk_needed
) == -1)
557 while (pagesz
> nbytes
)
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;
571 if (nbytes
<= (pagesz
>> 1))
573 register unsigned int shiftr
;
575 shiftr
= (nbytes
- 1) >> 2; /* == (nbytes - 1) / 4 */
576 while (shiftr
>>= 1) /* == (nbytes - 1) / {8,16,32,...} */
581 register u_int32_t amt
;
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. */
597 if (busy
[nunits
]) _mstats
.nrecurse
++;
599 while (busy
[nunits
]) nunits
++;
602 /* If there are no blocks of the appropriate size, go get some */
603 if (nextf
[nunits
] == 0)
606 /* Get one block off the list, and set the new list head */
607 if ((p
= nextf
[nunits
]) == NULL
)
612 nextf
[nunits
] = CHAIN (p
);
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");
621 /* Fill in the info, and if range checking, set up the magic numbers */
622 p
->mh_alloc
= ISALLOC
;
624 p
->mh_magic2
= MAGIC2
;
626 register char *m
= (char *) (p
+ 1) + n
;
628 *m
++ = MAGIC1
, *m
++ = MAGIC1
, *m
++ = MAGIC1
, *m
= MAGIC1
;
632 zmemset ((char *)(p
+ 1), 0xdf, n
); /* scramble previous contents */
635 _mstats
.nmalloc
[nunits
]++;
636 _mstats
.tmalloc
[nunits
]++;
638 #endif /* MALLOC_STATS */
639 return (char *) (p
+ 1);
646 register union mhead
*p
;
653 p
= (union mhead
*) ap
- 1;
655 if (p
->mh_alloc
== ISMEMALIGN
)
658 p
= (union mhead
*) ap
- 1;
661 if (p
->mh_alloc
!= ISALLOC
)
663 if (p
->mh_alloc
== ISFREE
)
664 botch ("free: called with already freed block argument");
666 botch ("free: called with unallocated block argument");
669 ASSERT (p
->mh_magic2
== MAGIC2
);
671 ASSERT (*ap
++ == MAGIC1
); ASSERT (*ap
++ == MAGIC1
);
672 ASSERT (*ap
++ == MAGIC1
); ASSERT (*ap
== MAGIC1
);
675 zmemset (mem
, 0xcf, p
->mh_nbytes
);
678 nunits
= p
->mh_index
;
680 ASSERT (nunits
< NBUCKETS
);
681 p
->mh_alloc
= ISFREE
;
683 /* Protect against signal handlers calling malloc. */
685 /* Put this block on the free list. */
686 CHAIN (p
) = nextf
[nunits
];
691 _mstats
.nmalloc
[nunits
]--;
693 #endif /* MALLOC_STATS */
701 register union mhead
*p
;
702 register u_int32_t tocopy
;
703 register unsigned int nbytes
;
716 if ((p
= (union mhead
*) mem
) == 0)
719 nunits
= p
->mh_index
;
720 ASSERT (p
->mh_alloc
== ISALLOC
);
721 ASSERT (p
->mh_magic2
== MAGIC2
);
723 m
= mem
+ (tocopy
= p
->mh_nbytes
);
724 ASSERT (*m
++ == MAGIC1
); ASSERT (*m
++ == MAGIC1
);
725 ASSERT (*m
++ == MAGIC1
); ASSERT (*m
== MAGIC1
);
727 /* See if desired size rounds to same power of 2 as actual size. */
728 nbytes
= (n
+ sizeof *p
+ MSLOP
+ 7) & ~7;
730 /* If ok, use the same block, just marking its size as changed. */
731 if (nbytes
> (4 << nunits
) && nbytes
<= (8 << nunits
))
734 *m
++ = 0; *m
++ = 0; *m
++ = 0; *m
++ = 0;
737 *m
++ = MAGIC1
; *m
++ = MAGIC1
; *m
++ = MAGIC1
; *m
++ = MAGIC1
;
748 if ((m
= malloc (n
)) == 0)
750 FASTCOPY (mem
, m
, tocopy
);
756 memalign (alignment
, size
)
757 unsigned int alignment
;
761 register char *aligned
;
762 register union mhead
*p
;
764 ptr
= malloc (size
+ alignment
);
768 /* If entire block has the desired alignment, just accept it. */
769 if (((int) ptr
& (alignment
- 1)) == 0)
771 /* Otherwise, get address of byte in the block that has that alignment. */
772 aligned
= (char *) (((int) ptr
+ alignment
- 1) & -alignment
);
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
;
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__)
793 return memalign (getpagesize (), size
);
806 result
= malloc (total
);
808 zmemset (result
, 0, total
);
818 #endif /* !NO_CALLOC */
823 malloc_bucket_stats (size
)
826 struct bucket_stats v
;
827 register union mhead
*p
;
831 if (size
< 0 || size
>= NBUCKETS
)
834 v
.nused
= v
.nmal
= 0;
838 v
.blocksize
= 1 << (size
+ 3);
839 v
.nused
= _mstats
.nmalloc
[size
];
840 v
.nmal
= _mstats
.tmalloc
[size
];
841 v
.nmorecore
= _mstats
.nmorecore
[size
];
843 for (p
= nextf
[size
]; p
; p
= CHAIN (p
))
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. */
856 struct _malstats result
;
857 struct bucket_stats v
;
861 result
.bytesused
= result
.bytesfree
= 0;
862 for (i
= 0; i
< NBUCKETS
; i
++)
864 v
= malloc_bucket_stats (i
);
865 result
.bytesfree
+= v
.nfree
* v
.blocksize
;
866 result
.bytesused
+= v
.nused
* v
.blocksize
;
872 print_malloc_stats (s
)
876 int totused
, totfree
;
877 struct bucket_stats v
;
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
++)
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
;
887 fprintf (stderr
, "\nTotal bytes in use: %d, total bytes free: %d\n",
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
);
896 #endif /* MALLOC_STATS */