1 /* Malloc implementation for multiple threads without lock contention.
2 Copyright (C) 1996,1997,1998,1999,2000,2001 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4 Contributed by Wolfram Gloger <wmglo@dent.med.uni-muenchen.de>
5 and Doug Lea <dl@cs.oswego.edu>, 1996.
7 The GNU C Library is free software; you can redistribute it and/or
8 modify it under the terms of the GNU Library General Public License as
9 published by the Free Software Foundation; either version 2 of the
10 License, or (at your option) any later version.
12 The GNU C Library is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 Library General Public License for more details.
17 You should have received a copy of the GNU Library General Public
18 License along with the GNU C Library; see the file COPYING.LIB. If not,
19 write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
24 This work is mainly derived from malloc-2.6.4 by Doug Lea
25 <dl@cs.oswego.edu>, which is available from:
27 ftp://g.oswego.edu/pub/misc/malloc.c
29 Most of the original comments are reproduced in the code below.
31 * Why use this malloc?
33 This is not the fastest, most space-conserving, most portable, or
34 most tunable malloc ever written. However it is among the fastest
35 while also being among the most space-conserving, portable and tunable.
36 Consistent balance across these factors results in a good general-purpose
37 allocator. For a high-level description, see
38 http://g.oswego.edu/dl/html/malloc.html
40 On many systems, the standard malloc implementation is by itself not
41 thread-safe, and therefore wrapped with a single global lock around
42 all malloc-related functions. In some applications, especially with
43 multiple available processors, this can lead to contention problems
44 and bad performance. This malloc version was designed with the goal
45 to avoid waiting for locks as much as possible. Statistics indicate
46 that this goal is achieved in many cases.
48 * Synopsis of public routines
50 (Much fuller descriptions are contained in the program documentation below.)
53 Initialize global configuration. When compiled for multiple threads,
54 this function must be called once before any other function in the
55 package. It is not required otherwise. It is called automatically
56 in the Linux/GNU C libray or when compiling with MALLOC_HOOKS.
58 Return a pointer to a newly allocated chunk of at least n bytes, or null
59 if no space is available.
61 Release the chunk of memory pointed to by p, or no effect if p is null.
62 realloc(Void_t* p, size_t n);
63 Return a pointer to a chunk of size n that contains the same data
64 as does chunk p up to the minimum of (n, p's size) bytes, or null
65 if no space is available. The returned pointer may or may not be
66 the same as p. If p is null, equivalent to malloc. Unless the
67 #define REALLOC_ZERO_BYTES_FREES below is set, realloc with a
68 size argument of zero (re)allocates a minimum-sized chunk.
69 memalign(size_t alignment, size_t n);
70 Return a pointer to a newly allocated chunk of n bytes, aligned
71 in accord with the alignment argument, which must be a power of
74 Equivalent to memalign(pagesize, n), where pagesize is the page
75 size of the system (or as near to this as can be figured out from
76 all the includes/defines below.)
78 Equivalent to valloc(minimum-page-that-holds(n)), that is,
79 round up n to nearest pagesize.
80 calloc(size_t unit, size_t quantity);
81 Returns a pointer to quantity * unit bytes, with all locations
84 Equivalent to free(p).
85 malloc_trim(size_t pad);
86 Release all but pad bytes of freed top-most memory back
87 to the system. Return 1 if successful, else 0.
88 malloc_usable_size(Void_t* p);
89 Report the number usable allocated bytes associated with allocated
90 chunk p. This may or may not report more bytes than were requested,
91 due to alignment and minimum size constraints.
93 Prints brief summary statistics on stderr.
95 Returns (by copy) a struct containing various summary statistics.
96 mallopt(int parameter_number, int parameter_value)
97 Changes one of the tunable parameters described below. Returns
98 1 if successful in changing the parameter, else 0.
103 8 byte alignment is currently hardwired into the design. This
104 seems to suffice for all current machines and C compilers.
106 Assumed pointer representation: 4 or 8 bytes
107 Code for 8-byte pointers is untested by me but has worked
108 reliably by Wolfram Gloger, who contributed most of the
109 changes supporting this.
111 Assumed size_t representation: 4 or 8 bytes
112 Note that size_t is allowed to be 4 bytes even if pointers are 8.
114 Minimum overhead per allocated chunk: 4 or 8 bytes
115 Each malloced chunk has a hidden overhead of 4 bytes holding size
116 and status information.
118 Minimum allocated size: 4-byte ptrs: 16 bytes (including 4 overhead)
119 8-byte ptrs: 24/32 bytes (including, 4/8 overhead)
121 When a chunk is freed, 12 (for 4byte ptrs) or 20 (for 8 byte
122 ptrs but 4 byte size) or 24 (for 8/8) additional bytes are
123 needed; 4 (8) for a trailing size field
124 and 8 (16) bytes for free list pointers. Thus, the minimum
125 allocatable size is 16/24/32 bytes.
127 Even a request for zero bytes (i.e., malloc(0)) returns a
128 pointer to something of the minimum allocatable size.
130 Maximum allocated size: 4-byte size_t: 2^31 - 8 bytes
131 8-byte size_t: 2^63 - 16 bytes
133 It is assumed that (possibly signed) size_t bit values suffice to
134 represent chunk sizes. `Possibly signed' is due to the fact
135 that `size_t' may be defined on a system as either a signed or
136 an unsigned type. To be conservative, values that would appear
137 as negative numbers are avoided.
138 Requests for sizes with a negative sign bit will return a
141 Maximum overhead wastage per allocated chunk: normally 15 bytes
143 Alignment demands, plus the minimum allocatable size restriction
144 make the normal worst-case wastage 15 bytes (i.e., up to 15
145 more bytes will be allocated than were requested in malloc), with
147 1. Because requests for zero bytes allocate non-zero space,
148 the worst case wastage for a request of zero bytes is 24 bytes.
149 2. For requests >= mmap_threshold that are serviced via
150 mmap(), the worst case wastage is 8 bytes plus the remainder
151 from a system page (the minimal mmap unit); typically 4096 bytes.
155 Here are some features that are NOT currently supported
157 * No automated mechanism for fully checking that all accesses
158 to malloced memory stay within their bounds.
159 * No support for compaction.
161 * Synopsis of compile-time options:
163 People have reported using previous versions of this malloc on all
164 versions of Unix, sometimes by tweaking some of the defines
165 below. It has been tested most extensively on Solaris and
166 Linux. People have also reported adapting this malloc for use in
167 stand-alone embedded systems.
169 The implementation is in straight, hand-tuned ANSI C. Among other
170 consequences, it uses a lot of macros. Because of this, to be at
171 all usable, this code should be compiled using an optimizing compiler
172 (for example gcc -O2) that can simplify expressions and control
175 __STD_C (default: derived from C compiler defines)
176 Nonzero if using ANSI-standard C compiler, a C++ compiler, or
177 a C compiler sufficiently close to ANSI to get away with it.
178 MALLOC_DEBUG (default: NOT defined)
179 Define to enable debugging. Adds fairly extensive assertion-based
180 checking to help track down memory errors, but noticeably slows down
182 MALLOC_HOOKS (default: NOT defined)
183 Define to enable support run-time replacement of the allocation
184 functions through user-defined `hooks'.
185 REALLOC_ZERO_BYTES_FREES (default: defined)
186 Define this if you think that realloc(p, 0) should be equivalent
187 to free(p). (The C standard requires this behaviour, therefore
188 it is the default.) Otherwise, since malloc returns a unique
189 pointer for malloc(0), so does realloc(p, 0).
190 HAVE_MEMCPY (default: defined)
191 Define if you are not otherwise using ANSI STD C, but still
192 have memcpy and memset in your C library and want to use them.
193 Otherwise, simple internal versions are supplied.
194 USE_MEMCPY (default: 1 if HAVE_MEMCPY is defined, 0 otherwise)
195 Define as 1 if you want the C library versions of memset and
196 memcpy called in realloc and calloc (otherwise macro versions are used).
197 At least on some platforms, the simple macro versions usually
198 outperform libc versions.
199 HAVE_MMAP (default: defined as 1)
200 Define to non-zero to optionally make malloc() use mmap() to
201 allocate very large blocks.
202 HAVE_MREMAP (default: defined as 0 unless Linux libc set)
203 Define to non-zero to optionally make realloc() use mremap() to
204 reallocate very large blocks.
205 USE_ARENAS (default: the same as HAVE_MMAP)
206 Enable support for multiple arenas, allocated using mmap().
207 malloc_getpagesize (default: derived from system #includes)
208 Either a constant or routine call returning the system page size.
209 HAVE_USR_INCLUDE_MALLOC_H (default: NOT defined)
210 Optionally define if you are on a system with a /usr/include/malloc.h
211 that declares struct mallinfo. It is not at all necessary to
212 define this even if you do, but will ensure consistency.
213 INTERNAL_SIZE_T (default: size_t)
214 Define to a 32-bit type (probably `unsigned int') if you are on a
215 64-bit machine, yet do not want or need to allow malloc requests of
216 greater than 2^31 to be handled. This saves space, especially for
218 _LIBC (default: NOT defined)
219 Defined only when compiled as part of the Linux libc/glibc.
220 Also note that there is some odd internal name-mangling via defines
221 (for example, internally, `malloc' is named `mALLOc') needed
222 when compiling in this case. These look funny but don't otherwise
224 LACKS_UNISTD_H (default: undefined)
225 Define this if your system does not have a <unistd.h>.
226 MORECORE (default: sbrk)
227 The name of the routine to call to obtain more memory from the system.
228 MORECORE_FAILURE (default: -1)
229 The value returned upon failure of MORECORE.
230 MORECORE_CLEARS (default 1)
231 The degree to which the routine mapped to MORECORE zeroes out
232 memory: never (0), only for newly allocated space (1) or always
233 (2). The distinction between (1) and (2) is necessary because on
234 some systems, if the application first decrements and then
235 increments the break value, the contents of the reallocated space
237 DEFAULT_TRIM_THRESHOLD
239 DEFAULT_MMAP_THRESHOLD
241 Default values of tunable parameters (described in detail below)
242 controlling interaction with host system routines (sbrk, mmap, etc).
243 These values may also be changed dynamically via mallopt(). The
244 preset defaults are those that give best performance for typical
247 When the standard debugging hooks are in place, and a pointer is
248 detected as corrupt, do nothing (0), print an error message (1),
256 * Compile-time options for multiple threads:
258 USE_PTHREADS, USE_THR, USE_SPROC
259 Define one of these as 1 to select the thread interface:
260 POSIX threads, Solaris threads or SGI sproc's, respectively.
261 If none of these is defined as non-zero, you get a `normal'
262 malloc implementation which is not thread-safe. Support for
263 multiple threads requires HAVE_MMAP=1. As an exception, when
264 compiling for GNU libc, i.e. when _LIBC is defined, then none of
265 the USE_... symbols have to be defined.
269 When thread support is enabled, additional `heap's are created
270 with mmap calls. These are limited in size; HEAP_MIN_SIZE should
271 be a multiple of the page size, while HEAP_MAX_SIZE must be a power
272 of two for alignment reasons. HEAP_MAX_SIZE should be at least
273 twice as large as the mmap threshold.
275 When this is defined as non-zero, some statistics on mutex locking
286 #if defined (__STDC__)
293 #endif /*__cplusplus*/
306 # include <stddef.h> /* for size_t */
307 # if defined _LIBC || defined MALLOC_HOOKS
308 # include <stdlib.h> /* for getenv(), abort() */
311 # include <sys/types.h>
312 # if defined _LIBC || defined MALLOC_HOOKS
313 extern char* getenv();
317 /* Macros for handling mutexes and thread-specific data. This is
318 included early, because some thread-related header files (such as
319 pthread.h) should be included before any others. */
320 #include "thread-m.h"
327 #include <stdio.h> /* needed for malloc_stats */
338 Because freed chunks may be overwritten with link fields, this
339 malloc will often die when freed memory is overwritten by user
340 programs. This can be very effective (albeit in an annoying way)
341 in helping track down dangling pointers.
343 If you compile with -DMALLOC_DEBUG, a number of assertion checks are
344 enabled that will catch more memory errors. You probably won't be
345 able to make much sense of the actual assertion errors, but they
346 should help you locate incorrectly overwritten memory. The
347 checking is fairly extensive, and will slow down execution
348 noticeably. Calling malloc_stats or mallinfo with MALLOC_DEBUG set will
349 attempt to check every non-mmapped allocated and free chunk in the
350 course of computing the summaries. (By nature, mmapped regions
351 cannot be checked very much automatically.)
353 Setting MALLOC_DEBUG may also be helpful if you are trying to modify
354 this code. The assertions in the check routines spell out in more
355 detail the assumptions and invariants underlying the algorithms.
362 #define assert(x) ((void)0)
367 INTERNAL_SIZE_T is the word-size used for internal bookkeeping
368 of chunk sizes. On a 64-bit machine, you can reduce malloc
369 overhead by defining INTERNAL_SIZE_T to be a 32 bit `unsigned int'
370 at the expense of not being able to handle requests greater than
371 2^31. This limitation is hardly ever a concern; you are encouraged
372 to set this. However, the default version is the same as size_t.
375 #ifndef INTERNAL_SIZE_T
376 #define INTERNAL_SIZE_T size_t
380 REALLOC_ZERO_BYTES_FREES should be set if a call to realloc with
381 zero bytes should be the same as a call to free. The C standard
382 requires this. Otherwise, since this malloc returns a unique pointer
383 for malloc(0), so does realloc(p, 0).
387 #define REALLOC_ZERO_BYTES_FREES
391 HAVE_MEMCPY should be defined if you are not otherwise using
392 ANSI STD C, but still have memcpy and memset in your C library
393 and want to use them in calloc and realloc. Otherwise simple
394 macro versions are defined here.
396 USE_MEMCPY should be defined as 1 if you actually want to
397 have memset and memcpy called. People report that the macro
398 versions are often enough faster than libc versions on many
399 systems that it is better to use them.
403 #define HAVE_MEMCPY 1
413 #if (__STD_C || defined(HAVE_MEMCPY))
416 void* memset(void*, int, size_t);
417 void* memcpy(void*, const void*, size_t);
418 void* memmove(void*, const void*, size_t);
426 /* The following macros are only invoked with (2n+1)-multiples of
427 INTERNAL_SIZE_T units, with a positive integer n. This is exploited
428 for fast inline execution when n is small. If the regions to be
429 copied do overlap, the destination lies always _below_ the source. */
433 #define MALLOC_ZERO(charp, nbytes) \
435 INTERNAL_SIZE_T mzsz = (nbytes); \
436 if(mzsz <= 9*sizeof(mzsz)) { \
437 INTERNAL_SIZE_T* mz = (INTERNAL_SIZE_T*) (charp); \
438 if(mzsz >= 5*sizeof(mzsz)) { *mz++ = 0; \
440 if(mzsz >= 7*sizeof(mzsz)) { *mz++ = 0; \
442 if(mzsz >= 9*sizeof(mzsz)) { *mz++ = 0; \
447 } else memset((charp), 0, mzsz); \
450 /* If the regions overlap, dest is always _below_ src. */
452 #define MALLOC_COPY(dest,src,nbytes,overlap) \
454 INTERNAL_SIZE_T mcsz = (nbytes); \
455 if(mcsz <= 9*sizeof(mcsz)) { \
456 INTERNAL_SIZE_T* mcsrc = (INTERNAL_SIZE_T*) (src); \
457 INTERNAL_SIZE_T* mcdst = (INTERNAL_SIZE_T*) (dest); \
458 if(mcsz >= 5*sizeof(mcsz)) { *mcdst++ = *mcsrc++; \
459 *mcdst++ = *mcsrc++; \
460 if(mcsz >= 7*sizeof(mcsz)) { *mcdst++ = *mcsrc++; \
461 *mcdst++ = *mcsrc++; \
462 if(mcsz >= 9*sizeof(mcsz)) { *mcdst++ = *mcsrc++; \
463 *mcdst++ = *mcsrc++; }}} \
464 *mcdst++ = *mcsrc++; \
465 *mcdst++ = *mcsrc++; \
468 memmove(dest, src, mcsz); \
470 memcpy(dest, src, mcsz); \
473 #else /* !USE_MEMCPY */
475 /* Use Duff's device for good zeroing/copying performance. */
477 #define MALLOC_ZERO(charp, nbytes) \
479 INTERNAL_SIZE_T* mzp = (INTERNAL_SIZE_T*)(charp); \
480 long mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T), mcn; \
481 if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; } \
483 case 0: for(;;) { *mzp++ = 0; \
484 case 7: *mzp++ = 0; \
485 case 6: *mzp++ = 0; \
486 case 5: *mzp++ = 0; \
487 case 4: *mzp++ = 0; \
488 case 3: *mzp++ = 0; \
489 case 2: *mzp++ = 0; \
490 case 1: *mzp++ = 0; if(mcn <= 0) break; mcn--; } \
494 /* If the regions overlap, dest is always _below_ src. */
496 #define MALLOC_COPY(dest,src,nbytes,overlap) \
498 INTERNAL_SIZE_T* mcsrc = (INTERNAL_SIZE_T*) src; \
499 INTERNAL_SIZE_T* mcdst = (INTERNAL_SIZE_T*) dest; \
500 long mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T), mcn; \
501 if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; } \
503 case 0: for(;;) { *mcdst++ = *mcsrc++; \
504 case 7: *mcdst++ = *mcsrc++; \
505 case 6: *mcdst++ = *mcsrc++; \
506 case 5: *mcdst++ = *mcsrc++; \
507 case 4: *mcdst++ = *mcsrc++; \
508 case 3: *mcdst++ = *mcsrc++; \
509 case 2: *mcdst++ = *mcsrc++; \
510 case 1: *mcdst++ = *mcsrc++; if(mcn <= 0) break; mcn--; } \
517 #ifndef LACKS_UNISTD_H
522 Define HAVE_MMAP to optionally make malloc() use mmap() to allocate
523 very large blocks. These will be returned to the operating system
524 immediately after a free(). HAVE_MMAP is also a prerequisite to
525 support multiple `arenas' (see USE_ARENAS below).
529 # ifdef _POSIX_MAPPED_FILES
535 Define HAVE_MREMAP to make realloc() use mremap() to re-allocate
536 large blocks. This is currently only possible on Linux with
537 kernel versions newer than 1.3.77.
541 #define HAVE_MREMAP defined(__linux__)
544 /* Define USE_ARENAS to enable support for multiple `arenas'. These
545 are allocated using mmap(), are necessary for threads and
546 occasionally useful to overcome address space limitations affecting
550 #define USE_ARENAS HAVE_MMAP
557 #include <sys/mman.h>
559 #if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
560 #define MAP_ANONYMOUS MAP_ANON
562 #if !defined(MAP_FAILED)
563 #define MAP_FAILED ((char*)-1)
566 #ifndef MAP_NORESERVE
567 # ifdef MAP_AUTORESRV
568 # define MAP_NORESERVE MAP_AUTORESRV
570 # define MAP_NORESERVE 0
574 #endif /* HAVE_MMAP */
577 Access to system page size. To the extent possible, this malloc
578 manages memory from the system in page-size units.
580 The following mechanics for getpagesize were adapted from
581 bsd/gnu getpagesize.h
584 #ifndef malloc_getpagesize
585 # ifdef _SC_PAGESIZE /* some SVR4 systems omit an underscore */
586 # ifndef _SC_PAGE_SIZE
587 # define _SC_PAGE_SIZE _SC_PAGESIZE
590 # ifdef _SC_PAGE_SIZE
591 # define malloc_getpagesize sysconf(_SC_PAGE_SIZE)
593 # if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE)
594 extern size_t getpagesize();
595 # define malloc_getpagesize getpagesize()
597 # include <sys/param.h>
598 # ifdef EXEC_PAGESIZE
599 # define malloc_getpagesize EXEC_PAGESIZE
603 # define malloc_getpagesize NBPG
605 # define malloc_getpagesize (NBPG * CLSIZE)
609 # define malloc_getpagesize NBPC
612 # define malloc_getpagesize PAGESIZE
614 # define malloc_getpagesize (4096) /* just guess */
627 This version of malloc supports the standard SVID/XPG mallinfo
628 routine that returns a struct containing the same kind of
629 information you can get from malloc_stats. It should work on
630 any SVID/XPG compliant system that has a /usr/include/malloc.h
631 defining struct mallinfo. (If you'd like to install such a thing
632 yourself, cut out the preliminary declarations as described above
633 and below and save them in a malloc.h file. But there's no
634 compelling reason to bother to do this.)
636 The main declaration needed is the mallinfo struct that is returned
637 (by-copy) by mallinfo(). The SVID/XPG malloinfo struct contains a
638 bunch of fields, most of which are not even meaningful in this
639 version of malloc. Some of these fields are are instead filled by
640 mallinfo() with other numbers that might possibly be of interest.
642 HAVE_USR_INCLUDE_MALLOC_H should be set if you have a
643 /usr/include/malloc.h file that includes a declaration of struct
644 mallinfo. If so, it is included; else an SVID2/XPG2 compliant
645 version is declared below. These must be precisely the same for
650 /* #define HAVE_USR_INCLUDE_MALLOC_H */
652 #if HAVE_USR_INCLUDE_MALLOC_H
653 # include "/usr/include/malloc.h"
658 # include "ptmalloc.h"
662 #include <bp-checks.h>
664 #ifndef DEFAULT_TRIM_THRESHOLD
665 #define DEFAULT_TRIM_THRESHOLD (128 * 1024)
669 M_TRIM_THRESHOLD is the maximum amount of unused top-most memory
670 to keep before releasing via malloc_trim in free().
672 Automatic trimming is mainly useful in long-lived programs.
673 Because trimming via sbrk can be slow on some systems, and can
674 sometimes be wasteful (in cases where programs immediately
675 afterward allocate more large chunks) the value should be high
676 enough so that your overall system performance would improve by
679 The trim threshold and the mmap control parameters (see below)
680 can be traded off with one another. Trimming and mmapping are
681 two different ways of releasing unused memory back to the
682 system. Between these two, it is often possible to keep
683 system-level demands of a long-lived program down to a bare
684 minimum. For example, in one test suite of sessions measuring
685 the XF86 X server on Linux, using a trim threshold of 128K and a
686 mmap threshold of 192K led to near-minimal long term resource
689 If you are using this malloc in a long-lived program, it should
690 pay to experiment with these values. As a rough guide, you
691 might set to a value close to the average size of a process
692 (program) running on your system. Releasing this much memory
693 would allow such a process to run in memory. Generally, it's
694 worth it to tune for trimming rather than memory mapping when a
695 program undergoes phases where several large chunks are
696 allocated and released in ways that can reuse each other's
697 storage, perhaps mixed with phases where there are no such
698 chunks at all. And in well-behaved long-lived programs,
699 controlling release of large blocks via trimming versus mapping
702 However, in most programs, these parameters serve mainly as
703 protection against the system-level effects of carrying around
704 massive amounts of unneeded memory. Since frequent calls to
705 sbrk, mmap, and munmap otherwise degrade performance, the default
706 parameters are set to relatively high values that serve only as
709 The default trim value is high enough to cause trimming only in
710 fairly extreme (by current memory consumption standards) cases.
711 It must be greater than page size to have any useful effect. To
712 disable trimming completely, you can set to (unsigned long)(-1);
718 #ifndef DEFAULT_TOP_PAD
719 #define DEFAULT_TOP_PAD (0)
723 M_TOP_PAD is the amount of extra `padding' space to allocate or
724 retain whenever sbrk is called. It is used in two ways internally:
726 * When sbrk is called to extend the top of the arena to satisfy
727 a new malloc request, this much padding is added to the sbrk
730 * When malloc_trim is called automatically from free(),
731 it is used as the `pad' argument.
733 In both cases, the actual amount of padding is rounded
734 so that the end of the arena is always a system page boundary.
736 The main reason for using padding is to avoid calling sbrk so
737 often. Having even a small pad greatly reduces the likelihood
738 that nearly every malloc request during program start-up (or
739 after trimming) will invoke sbrk, which needlessly wastes
742 Automatic rounding-up to page-size units is normally sufficient
743 to avoid measurable overhead, so the default is 0. However, in
744 systems where sbrk is relatively slow, it can pay to increase
745 this value, at the expense of carrying around more memory than
751 #ifndef DEFAULT_MMAP_THRESHOLD
752 #define DEFAULT_MMAP_THRESHOLD (128 * 1024)
757 M_MMAP_THRESHOLD is the request size threshold for using mmap()
758 to service a request. Requests of at least this size that cannot
759 be allocated using already-existing space will be serviced via mmap.
760 (If enough normal freed space already exists it is used instead.)
762 Using mmap segregates relatively large chunks of memory so that
763 they can be individually obtained and released from the host
764 system. A request serviced through mmap is never reused by any
765 other request (at least not directly; the system may just so
766 happen to remap successive requests to the same locations).
768 Segregating space in this way has the benefit that mmapped space
769 can ALWAYS be individually released back to the system, which
770 helps keep the system level memory demands of a long-lived
771 program low. Mapped memory can never become `locked' between
772 other chunks, as can happen with normally allocated chunks, which
773 menas that even trimming via malloc_trim would not release them.
775 However, it has the disadvantages that:
777 1. The space cannot be reclaimed, consolidated, and then
778 used to service later requests, as happens with normal chunks.
779 2. It can lead to more wastage because of mmap page alignment
781 3. It causes malloc performance to be more dependent on host
782 system memory management support routines which may vary in
783 implementation quality and may impose arbitrary
784 limitations. Generally, servicing a request via normal
785 malloc steps is faster than going through a system's mmap.
787 All together, these considerations should lead you to use mmap
788 only for relatively large requests.
795 #ifndef DEFAULT_MMAP_MAX
797 #define DEFAULT_MMAP_MAX (1024)
799 #define DEFAULT_MMAP_MAX (0)
804 M_MMAP_MAX is the maximum number of requests to simultaneously
805 service using mmap. This parameter exists because:
807 1. Some systems have a limited number of internal tables for
809 2. In most systems, overreliance on mmap can degrade overall
811 3. If a program allocates many large regions, it is probably
812 better off using normal sbrk-based allocation routines that
813 can reclaim and reallocate normal heap memory. Using a
814 small value allows transition into this mode after the
815 first few allocations.
817 Setting to 0 disables all use of mmap. If HAVE_MMAP is not set,
818 the default value is 0, and attempts to set it to non-zero values
819 in mallopt will fail.
824 #ifndef DEFAULT_CHECK_ACTION
825 #define DEFAULT_CHECK_ACTION 1
828 /* What to do if the standard debugging hooks are in place and a
829 corrupt pointer is detected: do nothing (0), print an error message
830 (1), or call abort() (2). */
834 #define HEAP_MIN_SIZE (32*1024)
835 #define HEAP_MAX_SIZE (1024*1024) /* must be a power of two */
837 /* HEAP_MIN_SIZE and HEAP_MAX_SIZE limit the size of mmap()ed heaps
838 that are dynamically created for multi-threaded programs. The
839 maximum size must be a power of two, for fast determination of
840 which heap belongs to a chunk. It should be much larger than
841 the mmap threshold, so that requests with a size just below that
842 threshold can be fulfilled without creating too many heaps.
848 #define THREAD_STATS 0
851 /* If THREAD_STATS is non-zero, some statistics on mutex locking are
855 /* Macro to set errno. */
857 # define __set_errno(val) errno = (val)
860 /* On some platforms we can compile internal, not exported functions better.
861 Let the environment provide a macro and define it to be empty if it
863 #ifndef internal_function
864 # define internal_function
870 Special defines for the Linux/GNU C library.
879 Void_t
* __default_morecore (ptrdiff_t);
880 Void_t
*(*__morecore
)(ptrdiff_t) = __default_morecore
;
884 Void_t
* __default_morecore ();
885 Void_t
*(*__morecore
)() = __default_morecore
;
889 #define MORECORE (*__morecore)
890 #define MORECORE_FAILURE 0
892 #ifndef MORECORE_CLEARS
893 #define MORECORE_CLEARS 1
896 static size_t __libc_pagesize
;
898 #define access __access
900 #define munmap __munmap
901 #define mremap __mremap
902 #define mprotect __mprotect
903 #undef malloc_getpagesize
904 #define malloc_getpagesize __libc_pagesize
909 extern Void_t
* sbrk(ptrdiff_t);
911 extern Void_t
* sbrk();
915 #define MORECORE sbrk
918 #ifndef MORECORE_FAILURE
919 #define MORECORE_FAILURE -1
922 #ifndef MORECORE_CLEARS
923 #define MORECORE_CLEARS 1
930 #define cALLOc __libc_calloc
931 #define fREe __libc_free
932 #define mALLOc __libc_malloc
933 #define mEMALIGn __libc_memalign
934 #define rEALLOc __libc_realloc
935 #define vALLOc __libc_valloc
936 #define pvALLOc __libc_pvalloc
937 #define mALLINFo __libc_mallinfo
938 #define mALLOPt __libc_mallopt
939 #define mALLOC_STATs __malloc_stats
940 #define mALLOC_USABLE_SIZe __malloc_usable_size
941 #define mALLOC_TRIm __malloc_trim
942 #define mALLOC_GET_STATe __malloc_get_state
943 #define mALLOC_SET_STATe __malloc_set_state
947 #define cALLOc calloc
949 #define mALLOc malloc
950 #define mEMALIGn memalign
951 #define rEALLOc realloc
952 #define vALLOc valloc
953 #define pvALLOc pvalloc
954 #define mALLINFo mallinfo
955 #define mALLOPt mallopt
956 #define mALLOC_STATs malloc_stats
957 #define mALLOC_USABLE_SIZe malloc_usable_size
958 #define mALLOC_TRIm malloc_trim
959 #define mALLOC_GET_STATe malloc_get_state
960 #define mALLOC_SET_STATe malloc_set_state
964 /* Public routines */
969 void ptmalloc_init(void);
971 Void_t
* mALLOc(size_t);
973 Void_t
* rEALLOc(Void_t
*, size_t);
974 Void_t
* mEMALIGn(size_t, size_t);
975 Void_t
* vALLOc(size_t);
976 Void_t
* pvALLOc(size_t);
977 Void_t
* cALLOc(size_t, size_t);
979 int mALLOC_TRIm(size_t);
980 size_t mALLOC_USABLE_SIZe(Void_t
*);
981 void mALLOC_STATs(void);
982 int mALLOPt(int, int);
983 struct mallinfo
mALLINFo(void);
984 Void_t
* mALLOC_GET_STATe(void);
985 int mALLOC_SET_STATe(Void_t
*);
990 void ptmalloc_init();
1001 size_t mALLOC_USABLE_SIZe();
1002 void mALLOC_STATs();
1004 struct mallinfo
mALLINFo();
1005 Void_t
* mALLOC_GET_STATe();
1006 int mALLOC_SET_STATe();
1008 #endif /* __STD_C */
1012 } /* end of extern "C" */
1015 #if !defined(NO_THREADS) && !HAVE_MMAP
1016 "Can't have threads support without mmap"
1018 #if USE_ARENAS && !HAVE_MMAP
1019 "Can't have multiple arenas without mmap"
1030 INTERNAL_SIZE_T prev_size
; /* Size of previous chunk (if free). */
1031 INTERNAL_SIZE_T size
; /* Size in bytes, including overhead. */
1032 struct malloc_chunk
* fd
; /* double links -- used only if free. */
1033 struct malloc_chunk
* bk
;
1036 typedef struct malloc_chunk
* mchunkptr
;
1040 malloc_chunk details:
1042 (The following includes lightly edited explanations by Colin Plumb.)
1044 Chunks of memory are maintained using a `boundary tag' method as
1045 described in e.g., Knuth or Standish. (See the paper by Paul
1046 Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a
1047 survey of such techniques.) Sizes of free chunks are stored both
1048 in the front of each chunk and at the end. This makes
1049 consolidating fragmented chunks into bigger chunks very fast. The
1050 size fields also hold bits representing whether chunks are free or
1053 An allocated chunk looks like this:
1056 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1057 | Size of previous chunk, if allocated | |
1058 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1059 | Size of chunk, in bytes |P|
1060 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1061 | User data starts here... .
1063 . (malloc_usable_space() bytes) .
1065 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1067 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1070 Where "chunk" is the front of the chunk for the purpose of most of
1071 the malloc code, but "mem" is the pointer that is returned to the
1072 user. "Nextchunk" is the beginning of the next contiguous chunk.
1074 Chunks always begin on even word boundaries, so the mem portion
1075 (which is returned to the user) is also on an even word boundary, and
1076 thus double-word aligned.
1078 Free chunks are stored in circular doubly-linked lists, and look like this:
1080 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1081 | Size of previous chunk |
1082 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1083 `head:' | Size of chunk, in bytes |P|
1084 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1085 | Forward pointer to next chunk in list |
1086 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1087 | Back pointer to previous chunk in list |
1088 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1089 | Unused space (may be 0 bytes long) .
1092 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1093 `foot:' | Size of chunk, in bytes |
1094 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1096 The P (PREV_INUSE) bit, stored in the unused low-order bit of the
1097 chunk size (which is always a multiple of two words), is an in-use
1098 bit for the *previous* chunk. If that bit is *clear*, then the
1099 word before the current chunk size contains the previous chunk
1100 size, and can be used to find the front of the previous chunk.
1101 (The very first chunk allocated always has this bit set,
1102 preventing access to non-existent (or non-owned) memory.)
1104 Note that the `foot' of the current chunk is actually represented
1105 as the prev_size of the NEXT chunk. (This makes it easier to
1106 deal with alignments etc).
1108 The two exceptions to all this are
1110 1. The special chunk `top', which doesn't bother using the
1111 trailing size field since there is no
1112 next contiguous chunk that would have to index off it. (After
1113 initialization, `top' is forced to always exist. If it would
1114 become less than MINSIZE bytes long, it is replenished via
1117 2. Chunks allocated via mmap, which have the second-lowest-order
1118 bit (IS_MMAPPED) set in their size fields. Because they are
1119 never merged or traversed from any other chunk, they have no
1120 foot size or inuse information.
1122 Available chunks are kept in any of several places (all declared below):
1124 * `av': An array of chunks serving as bin headers for consolidated
1125 chunks. Each bin is doubly linked. The bins are approximately
1126 proportionally (log) spaced. There are a lot of these bins
1127 (128). This may look excessive, but works very well in
1128 practice. All procedures maintain the invariant that no
1129 consolidated chunk physically borders another one. Chunks in
1130 bins are kept in size order, with ties going to the
1131 approximately least recently used chunk.
1133 The chunks in each bin are maintained in decreasing sorted order by
1134 size. This is irrelevant for the small bins, which all contain
1135 the same-sized chunks, but facilitates best-fit allocation for
1136 larger chunks. (These lists are just sequential. Keeping them in
1137 order almost never requires enough traversal to warrant using
1138 fancier ordered data structures.) Chunks of the same size are
1139 linked with the most recently freed at the front, and allocations
1140 are taken from the back. This results in LRU or FIFO allocation
1141 order, which tends to give each chunk an equal opportunity to be
1142 consolidated with adjacent freed chunks, resulting in larger free
1143 chunks and less fragmentation.
1145 * `top': The top-most available chunk (i.e., the one bordering the
1146 end of available memory) is treated specially. It is never
1147 included in any bin, is used only if no other chunk is
1148 available, and is released back to the system if it is very
1149 large (see M_TRIM_THRESHOLD).
1151 * `last_remainder': A bin holding only the remainder of the
1152 most recently split (non-top) chunk. This bin is checked
1153 before other non-fitting chunks, so as to provide better
1154 locality for runs of sequentially allocated chunks.
1156 * Implicitly, through the host system's memory mapping tables.
1157 If supported, requests greater than a threshold are usually
1158 serviced via calls to mmap, and then later released via munmap.
1165 The bins are an array of pairs of pointers serving as the
1166 heads of (initially empty) doubly-linked lists of chunks, laid out
1167 in a way so that each pair can be treated as if it were in a
1168 malloc_chunk. (This way, the fd/bk offsets for linking bin heads
1169 and chunks are the same).
1171 Bins for sizes < 512 bytes contain chunks of all the same size, spaced
1172 8 bytes apart. Larger bins are approximately logarithmically
1173 spaced. (See the table below.)
1181 4 bins of size 32768
1182 2 bins of size 262144
1183 1 bin of size what's left
1185 There is actually a little bit of slop in the numbers in bin_index
1186 for the sake of speed. This makes no difference elsewhere.
1188 The special chunks `top' and `last_remainder' get their own bins,
1189 (this is implemented via yet more trickery with the av array),
1190 although `top' is never properly linked to its bin since it is
1191 always handled specially.
1195 #define NAV 128 /* number of bins */
1197 typedef struct malloc_chunk
* mbinptr
;
1199 /* An arena is a configuration of malloc_chunks together with an array
1200 of bins. With multiple threads, it must be locked via a mutex
1201 before changing its data structures. One or more `heaps' are
1202 associated with each arena, except for the main_arena, which is
1203 associated only with the `main heap', i.e. the conventional free
1204 store obtained with calls to MORECORE() (usually sbrk). The `av'
1205 array is never mentioned directly in the code, but instead used via
1206 bin access macros. */
1208 typedef struct _arena
{
1209 mbinptr av
[2*NAV
+ 2];
1210 struct _arena
*next
;
1213 long stat_lock_direct
, stat_lock_loop
, stat_lock_wait
;
1219 /* A heap is a single contiguous memory region holding (coalesceable)
1220 malloc_chunks. It is allocated with mmap() and always starts at an
1221 address aligned to HEAP_MAX_SIZE. Not used unless compiling with
1224 typedef struct _heap_info
{
1225 arena
*ar_ptr
; /* Arena for this heap. */
1226 struct _heap_info
*prev
; /* Previous heap. */
1227 size_t size
; /* Current size in bytes. */
1228 size_t pad
; /* Make sure the following data is properly aligned. */
1233 Static functions (forward declarations)
1238 static void chunk_free(arena
*ar_ptr
, mchunkptr p
) internal_function
;
1239 static mchunkptr
chunk_alloc(arena
*ar_ptr
, INTERNAL_SIZE_T size
)
1241 static mchunkptr
chunk_realloc(arena
*ar_ptr
, mchunkptr oldp
,
1242 INTERNAL_SIZE_T oldsize
, INTERNAL_SIZE_T nb
)
1244 static mchunkptr
chunk_align(arena
*ar_ptr
, INTERNAL_SIZE_T nb
,
1245 size_t alignment
) internal_function
;
1246 static int main_trim(size_t pad
) internal_function
;
1248 static int heap_trim(heap_info
*heap
, size_t pad
) internal_function
;
1250 #if defined _LIBC || defined MALLOC_HOOKS
1251 static Void_t
* malloc_check(size_t sz
, const Void_t
*caller
);
1252 static void free_check(Void_t
* mem
, const Void_t
*caller
);
1253 static Void_t
* realloc_check(Void_t
* oldmem
, size_t bytes
,
1254 const Void_t
*caller
);
1255 static Void_t
* memalign_check(size_t alignment
, size_t bytes
,
1256 const Void_t
*caller
);
1258 static Void_t
* malloc_starter(size_t sz
, const Void_t
*caller
);
1259 static void free_starter(Void_t
* mem
, const Void_t
*caller
);
1260 static Void_t
* malloc_atfork(size_t sz
, const Void_t
*caller
);
1261 static void free_atfork(Void_t
* mem
, const Void_t
*caller
);
1267 static void chunk_free();
1268 static mchunkptr
chunk_alloc();
1269 static mchunkptr
chunk_realloc();
1270 static mchunkptr
chunk_align();
1271 static int main_trim();
1273 static int heap_trim();
1275 #if defined _LIBC || defined MALLOC_HOOKS
1276 static Void_t
* malloc_check();
1277 static void free_check();
1278 static Void_t
* realloc_check();
1279 static Void_t
* memalign_check();
1281 static Void_t
* malloc_starter();
1282 static void free_starter();
1283 static Void_t
* malloc_atfork();
1284 static void free_atfork();
1292 /* sizes, alignments */
1294 #define SIZE_SZ (sizeof(INTERNAL_SIZE_T))
1295 /* Allow the default to be overwritten on the compiler command line. */
1296 #ifndef MALLOC_ALIGNMENT
1297 # define MALLOC_ALIGNMENT (SIZE_SZ + SIZE_SZ)
1299 #define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1)
1300 #define MINSIZE (sizeof(struct malloc_chunk))
1302 /* conversion from malloc headers to user pointers, and back */
1304 #define chunk2mem(p) ((Void_t*)((char*)(p) + 2*SIZE_SZ))
1305 #define mem2chunk(mem) chunk_at_offset((mem), -2*SIZE_SZ)
1307 /* pad request bytes into a usable size, return non-zero on overflow */
1309 #define request2size(req, nb) \
1310 ((nb = (req) + (SIZE_SZ + MALLOC_ALIGN_MASK)),\
1311 ((long)nb <= 0 || nb < (INTERNAL_SIZE_T) (req) \
1312 ? (__set_errno (ENOMEM), 1) \
1313 : ((nb < (MINSIZE + MALLOC_ALIGN_MASK) \
1314 ? (nb = MINSIZE) : (nb &= ~MALLOC_ALIGN_MASK)), 0)))
1316 /* Check if m has acceptable alignment */
1318 #define aligned_OK(m) (((unsigned long)((m)) & (MALLOC_ALIGN_MASK)) == 0)
1324 Physical chunk operations
1328 /* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
1330 #define PREV_INUSE 0x1UL
1332 /* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */
1334 #define IS_MMAPPED 0x2UL
1336 /* Bits to mask off when extracting size */
1338 #define SIZE_BITS (PREV_INUSE|IS_MMAPPED)
1341 /* Ptr to next physical malloc_chunk. */
1343 #define next_chunk(p) chunk_at_offset((p), (p)->size & ~PREV_INUSE)
1345 /* Ptr to previous physical malloc_chunk */
1347 #define prev_chunk(p) chunk_at_offset((p), -(p)->prev_size)
1350 /* Treat space at ptr + offset as a chunk */
1352 #define chunk_at_offset(p, s) BOUNDED_1((mchunkptr)(((char*)(p)) + (s)))
1358 Dealing with use bits
1361 /* extract p's inuse bit */
1363 #define inuse(p) (next_chunk(p)->size & PREV_INUSE)
1365 /* extract inuse bit of previous chunk */
1367 #define prev_inuse(p) ((p)->size & PREV_INUSE)
1369 /* check for mmap()'ed chunk */
1371 #define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)
1373 /* set/clear chunk as in use without otherwise disturbing */
1375 #define set_inuse(p) (next_chunk(p)->size |= PREV_INUSE)
1377 #define clear_inuse(p) (next_chunk(p)->size &= ~PREV_INUSE)
1379 /* check/set/clear inuse bits in known places */
1381 #define inuse_bit_at_offset(p, s) \
1382 (chunk_at_offset((p), (s))->size & PREV_INUSE)
1384 #define set_inuse_bit_at_offset(p, s) \
1385 (chunk_at_offset((p), (s))->size |= PREV_INUSE)
1387 #define clear_inuse_bit_at_offset(p, s) \
1388 (chunk_at_offset((p), (s))->size &= ~(PREV_INUSE))
1394 Dealing with size fields
1397 /* Get size, ignoring use bits */
1399 #define chunksize(p) ((p)->size & ~(SIZE_BITS))
1401 /* Set size at head, without disturbing its use bit */
1403 #define set_head_size(p, s) ((p)->size = (((p)->size & PREV_INUSE) | (s)))
1405 /* Set size/use ignoring previous bits in header */
1407 #define set_head(p, s) ((p)->size = (s))
1409 /* Set size at footer (only when chunk is not in use) */
1411 #define set_foot(p, s) (chunk_at_offset(p, s)->prev_size = (s))
1419 #define bin_at(a, i) BOUNDED_1(_bin_at(a, i))
1420 #define _bin_at(a, i) ((mbinptr)((char*)&(((a)->av)[2*(i)+2]) - 2*SIZE_SZ))
1421 #define init_bin(a, i) ((a)->av[2*(i)+2] = (a)->av[2*(i)+3] = bin_at((a), (i)))
1422 #define next_bin(b) ((mbinptr)((char*)(b) + 2 * sizeof(((arena*)0)->av[0])))
1423 #define prev_bin(b) ((mbinptr)((char*)(b) - 2 * sizeof(((arena*)0)->av[0])))
1426 The first 2 bins are never indexed. The corresponding av cells are instead
1427 used for bookkeeping. This is not to save space, but to simplify
1428 indexing, maintain locality, and avoid some initialization tests.
1431 #define binblocks(a) (bin_at(a,0)->size)/* bitvector of nonempty blocks */
1432 #define top(a) (bin_at(a,0)->fd) /* The topmost chunk */
1433 #define last_remainder(a) (bin_at(a,1)) /* remainder from last split */
1436 Because top initially points to its own bin with initial
1437 zero size, thus forcing extension on the first malloc request,
1438 we avoid having any special code in malloc to check whether
1439 it even exists yet. But we still need to in malloc_extend_top.
1442 #define initial_top(a) ((mchunkptr)bin_at(a, 0))
1446 /* field-extraction macros */
1448 #define first(b) ((b)->fd)
1449 #define last(b) ((b)->bk)
1455 #define bin_index(sz) \
1456 (((((unsigned long)(sz)) >> 9) == 0) ? (((unsigned long)(sz)) >> 3):\
1457 ((((unsigned long)(sz)) >> 9) <= 4) ? 56 + (((unsigned long)(sz)) >> 6):\
1458 ((((unsigned long)(sz)) >> 9) <= 20) ? 91 + (((unsigned long)(sz)) >> 9):\
1459 ((((unsigned long)(sz)) >> 9) <= 84) ? 110 + (((unsigned long)(sz)) >> 12):\
1460 ((((unsigned long)(sz)) >> 9) <= 340) ? 119 + (((unsigned long)(sz)) >> 15):\
1461 ((((unsigned long)(sz)) >> 9) <= 1364) ? 124 + (((unsigned long)(sz)) >> 18):\
1464 bins for chunks < 512 are all spaced 8 bytes apart, and hold
1465 identically sized chunks. This is exploited in malloc.
1468 #define MAX_SMALLBIN 63
1469 #define MAX_SMALLBIN_SIZE 512
1470 #define SMALLBIN_WIDTH 8
1472 #define smallbin_index(sz) (((unsigned long)(sz)) >> 3)
1475 Requests are `small' if both the corresponding and the next bin are small
1478 #define is_small_request(nb) ((nb) < MAX_SMALLBIN_SIZE - SMALLBIN_WIDTH)
1483 To help compensate for the large number of bins, a one-level index
1484 structure is used for bin-by-bin searching. `binblocks' is a
1485 one-word bitvector recording whether groups of BINBLOCKWIDTH bins
1486 have any (possibly) non-empty bins, so they can be skipped over
1487 all at once during during traversals. The bits are NOT always
1488 cleared as soon as all bins in a block are empty, but instead only
1489 when all are noticed to be empty during traversal in malloc.
1492 #define BINBLOCKWIDTH 4 /* bins per block */
1494 /* bin<->block macros */
1496 #define idx2binblock(ix) ((unsigned)1 << ((ix) / BINBLOCKWIDTH))
1497 #define mark_binblock(a, ii) (binblocks(a) |= idx2binblock(ii))
1498 #define clear_binblock(a, ii) (binblocks(a) &= ~(idx2binblock(ii)))
1503 /* Static bookkeeping data */
1505 /* Helper macro to initialize bins */
1506 #define IAV(i) _bin_at(&main_arena, i), _bin_at(&main_arena, i)
1508 static arena main_arena
= {
1511 IAV(0), IAV(1), IAV(2), IAV(3), IAV(4), IAV(5), IAV(6), IAV(7),
1512 IAV(8), IAV(9), IAV(10), IAV(11), IAV(12), IAV(13), IAV(14), IAV(15),
1513 IAV(16), IAV(17), IAV(18), IAV(19), IAV(20), IAV(21), IAV(22), IAV(23),
1514 IAV(24), IAV(25), IAV(26), IAV(27), IAV(28), IAV(29), IAV(30), IAV(31),
1515 IAV(32), IAV(33), IAV(34), IAV(35), IAV(36), IAV(37), IAV(38), IAV(39),
1516 IAV(40), IAV(41), IAV(42), IAV(43), IAV(44), IAV(45), IAV(46), IAV(47),
1517 IAV(48), IAV(49), IAV(50), IAV(51), IAV(52), IAV(53), IAV(54), IAV(55),
1518 IAV(56), IAV(57), IAV(58), IAV(59), IAV(60), IAV(61), IAV(62), IAV(63),
1519 IAV(64), IAV(65), IAV(66), IAV(67), IAV(68), IAV(69), IAV(70), IAV(71),
1520 IAV(72), IAV(73), IAV(74), IAV(75), IAV(76), IAV(77), IAV(78), IAV(79),
1521 IAV(80), IAV(81), IAV(82), IAV(83), IAV(84), IAV(85), IAV(86), IAV(87),
1522 IAV(88), IAV(89), IAV(90), IAV(91), IAV(92), IAV(93), IAV(94), IAV(95),
1523 IAV(96), IAV(97), IAV(98), IAV(99), IAV(100), IAV(101), IAV(102), IAV(103),
1524 IAV(104), IAV(105), IAV(106), IAV(107), IAV(108), IAV(109), IAV(110), IAV(111),
1525 IAV(112), IAV(113), IAV(114), IAV(115), IAV(116), IAV(117), IAV(118), IAV(119),
1526 IAV(120), IAV(121), IAV(122), IAV(123), IAV(124), IAV(125), IAV(126), IAV(127)
1528 &main_arena
, /* next */
1531 0, 0, 0, /* stat_lock_direct, stat_lock_loop, stat_lock_wait */
1533 MUTEX_INITIALIZER
/* mutex */
1538 /* Thread specific data */
1540 static tsd_key_t arena_key
;
1541 static mutex_t list_lock
= MUTEX_INITIALIZER
;
1544 static int stat_n_heaps
;
1545 #define THREAD_STAT(x) x
1547 #define THREAD_STAT(x) do ; while(0)
1550 /* variables holding tunable values */
1552 static unsigned long trim_threshold
= DEFAULT_TRIM_THRESHOLD
;
1553 static unsigned long top_pad
= DEFAULT_TOP_PAD
;
1554 static unsigned int n_mmaps_max
= DEFAULT_MMAP_MAX
;
1555 static unsigned long mmap_threshold
= DEFAULT_MMAP_THRESHOLD
;
1556 static int check_action
= DEFAULT_CHECK_ACTION
;
1558 /* The first value returned from sbrk */
1559 static char* sbrk_base
= (char*)(-1);
1561 /* The maximum memory obtained from system via sbrk */
1562 static unsigned long max_sbrked_mem
;
1564 /* The maximum via either sbrk or mmap (too difficult to track with threads) */
1566 static unsigned long max_total_mem
;
1569 /* The total memory obtained from system via sbrk */
1570 #define sbrked_mem (main_arena.size)
1572 /* Tracking mmaps */
1574 static unsigned int n_mmaps
;
1575 static unsigned int max_n_mmaps
;
1576 static unsigned long mmapped_mem
;
1577 static unsigned long max_mmapped_mem
;
1579 /* Mapped memory in non-main arenas (reliable only for NO_THREADS). */
1580 static unsigned long arena_mem
;
1585 #define weak_variable
1587 /* In GNU libc we want the hook variables to be weak definitions to
1588 avoid a problem with Emacs. */
1589 #define weak_variable weak_function
1592 /* Already initialized? */
1593 int __malloc_initialized
= -1;
1598 /* Magic value for the thread-specific arena pointer when
1599 malloc_atfork() is in use. */
1601 #define ATFORK_ARENA_PTR ((Void_t*)-1)
1603 /* The following two functions are registered via thread_atfork() to
1604 make sure that the mutexes remain in a consistent state in the
1605 fork()ed version of a thread. Also adapt the malloc and free hooks
1606 temporarily, because the `atfork' handler mechanism may use
1607 malloc/free internally (e.g. in LinuxThreads). */
1609 #if defined _LIBC || defined MALLOC_HOOKS
1610 static __malloc_ptr_t (*save_malloc_hook
) __MALLOC_P ((size_t __size
,
1611 const __malloc_ptr_t
));
1612 static void (*save_free_hook
) __MALLOC_P ((__malloc_ptr_t __ptr
,
1613 const __malloc_ptr_t
));
1614 static Void_t
* save_arena
;
1618 ptmalloc_lock_all
__MALLOC_P((void))
1622 (void)mutex_lock(&list_lock
);
1623 for(ar_ptr
= &main_arena
;;) {
1624 (void)mutex_lock(&ar_ptr
->mutex
);
1625 ar_ptr
= ar_ptr
->next
;
1626 if(ar_ptr
== &main_arena
) break;
1628 #if defined _LIBC || defined MALLOC_HOOKS
1629 save_malloc_hook
= __malloc_hook
;
1630 save_free_hook
= __free_hook
;
1631 __malloc_hook
= malloc_atfork
;
1632 __free_hook
= free_atfork
;
1633 /* Only the current thread may perform malloc/free calls now. */
1634 tsd_getspecific(arena_key
, save_arena
);
1635 tsd_setspecific(arena_key
, ATFORK_ARENA_PTR
);
1640 ptmalloc_unlock_all
__MALLOC_P((void))
1644 #if defined _LIBC || defined MALLOC_HOOKS
1645 tsd_setspecific(arena_key
, save_arena
);
1646 __malloc_hook
= save_malloc_hook
;
1647 __free_hook
= save_free_hook
;
1649 for(ar_ptr
= &main_arena
;;) {
1650 (void)mutex_unlock(&ar_ptr
->mutex
);
1651 ar_ptr
= ar_ptr
->next
;
1652 if(ar_ptr
== &main_arena
) break;
1654 (void)mutex_unlock(&list_lock
);
1658 ptmalloc_init_all
__MALLOC_P((void))
1662 #if defined _LIBC || defined MALLOC_HOOKS
1663 tsd_setspecific(arena_key
, save_arena
);
1664 __malloc_hook
= save_malloc_hook
;
1665 __free_hook
= save_free_hook
;
1667 for(ar_ptr
= &main_arena
;;) {
1668 (void)mutex_init(&ar_ptr
->mutex
);
1669 ar_ptr
= ar_ptr
->next
;
1670 if(ar_ptr
== &main_arena
) break;
1672 (void)mutex_init(&list_lock
);
1675 #endif /* !defined NO_THREADS */
1677 /* Initialization routine. */
1680 static void ptmalloc_init
__MALLOC_P ((void)) __attribute__ ((constructor
));
1684 ptmalloc_init
__MALLOC_P((void))
1687 ptmalloc_init
__MALLOC_P((void))
1690 #if defined _LIBC || defined MALLOC_HOOKS
1699 if(__malloc_initialized
>= 0) return;
1700 __malloc_initialized
= 0;
1702 __libc_pagesize
= __getpagesize();
1705 #if defined _LIBC || defined MALLOC_HOOKS
1706 /* With some threads implementations, creating thread-specific data
1707 or initializing a mutex may call malloc() itself. Provide a
1708 simple starter version (realloc() won't work). */
1709 save_malloc_hook
= __malloc_hook
;
1710 save_free_hook
= __free_hook
;
1711 __malloc_hook
= malloc_starter
;
1712 __free_hook
= free_starter
;
1715 /* Initialize the pthreads interface. */
1716 if (__pthread_initialize
!= NULL
)
1717 __pthread_initialize();
1719 #endif /* !defined NO_THREADS */
1720 mutex_init(&main_arena
.mutex
);
1721 mutex_init(&list_lock
);
1722 tsd_key_create(&arena_key
, NULL
);
1723 tsd_setspecific(arena_key
, (Void_t
*)&main_arena
);
1724 thread_atfork(ptmalloc_lock_all
, ptmalloc_unlock_all
, ptmalloc_init_all
);
1725 #if defined _LIBC || defined MALLOC_HOOKS
1727 __malloc_hook
= save_malloc_hook
;
1728 __free_hook
= save_free_hook
;
1730 secure
= __libc_enable_secure
;
1733 if((s
= getenv("MALLOC_TRIM_THRESHOLD_")))
1734 mALLOPt(M_TRIM_THRESHOLD
, atoi(s
));
1735 if((s
= getenv("MALLOC_TOP_PAD_")))
1736 mALLOPt(M_TOP_PAD
, atoi(s
));
1737 if((s
= getenv("MALLOC_MMAP_THRESHOLD_")))
1738 mALLOPt(M_MMAP_THRESHOLD
, atoi(s
));
1739 if((s
= getenv("MALLOC_MMAP_MAX_")))
1740 mALLOPt(M_MMAP_MAX
, atoi(s
));
1742 s
= getenv("MALLOC_CHECK_");
1744 if(s
[0]) mALLOPt(M_CHECK_ACTION
, (int)(s
[0] - '0'));
1745 __malloc_check_init();
1747 if(__malloc_initialize_hook
!= NULL
)
1748 (*__malloc_initialize_hook
)();
1750 __malloc_initialized
= 1;
1753 /* There are platforms (e.g. Hurd) with a link-time hook mechanism. */
1754 #ifdef thread_atfork_static
1755 thread_atfork_static(ptmalloc_lock_all
, ptmalloc_unlock_all
, \
1759 #if defined _LIBC || defined MALLOC_HOOKS
1761 /* Hooks for debugging versions. The initial hooks just call the
1762 initialization routine, then do the normal work. */
1766 malloc_hook_ini(size_t sz
, const __malloc_ptr_t caller
)
1768 malloc_hook_ini(sz
, caller
)
1769 size_t sz
; const __malloc_ptr_t caller
;
1772 __malloc_hook
= NULL
;
1779 realloc_hook_ini(Void_t
* ptr
, size_t sz
, const __malloc_ptr_t caller
)
1781 realloc_hook_ini(ptr
, sz
, caller
)
1782 Void_t
* ptr
; size_t sz
; const __malloc_ptr_t caller
;
1785 __malloc_hook
= NULL
;
1786 __realloc_hook
= NULL
;
1788 return rEALLOc(ptr
, sz
);
1793 memalign_hook_ini(size_t alignment
, size_t sz
, const __malloc_ptr_t caller
)
1795 memalign_hook_ini(alignment
, sz
, caller
)
1796 size_t alignment
; size_t sz
; const __malloc_ptr_t caller
;
1799 __memalign_hook
= NULL
;
1801 return mEMALIGn(alignment
, sz
);
1804 void weak_variable (*__malloc_initialize_hook
) __MALLOC_P ((void)) = NULL
;
1805 void weak_variable (*__free_hook
) __MALLOC_P ((__malloc_ptr_t __ptr
,
1806 const __malloc_ptr_t
)) = NULL
;
1807 __malloc_ptr_t
weak_variable (*__malloc_hook
)
1808 __MALLOC_P ((size_t __size
, const __malloc_ptr_t
)) = malloc_hook_ini
;
1809 __malloc_ptr_t
weak_variable (*__realloc_hook
)
1810 __MALLOC_P ((__malloc_ptr_t __ptr
, size_t __size
, const __malloc_ptr_t
))
1812 __malloc_ptr_t
weak_variable (*__memalign_hook
)
1813 __MALLOC_P ((size_t __alignment
, size_t __size
, const __malloc_ptr_t
))
1814 = memalign_hook_ini
;
1815 void weak_variable (*__after_morecore_hook
) __MALLOC_P ((void)) = NULL
;
1817 /* Whether we are using malloc checking. */
1818 static int using_malloc_checking
;
1820 /* A flag that is set by malloc_set_state, to signal that malloc checking
1821 must not be enabled on the request from the user (via the MALLOC_CHECK_
1822 environment variable). It is reset by __malloc_check_init to tell
1823 malloc_set_state that the user has requested malloc checking.
1825 The purpose of this flag is to make sure that malloc checking is not
1826 enabled when the heap to be restored was constructed without malloc
1827 checking, and thus does not contain the required magic bytes.
1828 Otherwise the heap would be corrupted by calls to free and realloc. If
1829 it turns out that the heap was created with malloc checking and the
1830 user has requested it malloc_set_state just calls __malloc_check_init
1831 again to enable it. On the other hand, reusing such a heap without
1832 further malloc checking is safe. */
1833 static int disallow_malloc_check
;
1835 /* Activate a standard set of debugging hooks. */
1837 __malloc_check_init()
1839 if (disallow_malloc_check
) {
1840 disallow_malloc_check
= 0;
1843 using_malloc_checking
= 1;
1844 __malloc_hook
= malloc_check
;
1845 __free_hook
= free_check
;
1846 __realloc_hook
= realloc_check
;
1847 __memalign_hook
= memalign_check
;
1848 if(check_action
& 1)
1849 fprintf(stderr
, "malloc: using debugging hooks\n");
1858 /* Routines dealing with mmap(). */
1862 #ifndef MAP_ANONYMOUS
1864 static int dev_zero_fd
= -1; /* Cached file descriptor for /dev/zero. */
1866 #define MMAP(addr, size, prot, flags) ((dev_zero_fd < 0) ? \
1867 (dev_zero_fd = open("/dev/zero", O_RDWR), \
1868 mmap((addr), (size), (prot), (flags), dev_zero_fd, 0)) : \
1869 mmap((addr), (size), (prot), (flags), dev_zero_fd, 0))
1873 #define MMAP(addr, size, prot, flags) \
1874 (mmap((addr), (size), (prot), (flags)|MAP_ANONYMOUS, -1, 0))
1878 #if defined __GNUC__ && __GNUC__ >= 2
1879 /* This function is only called from one place, inline it. */
1885 mmap_chunk(size_t size
)
1887 mmap_chunk(size
) size_t size
;
1890 size_t page_mask
= malloc_getpagesize
- 1;
1893 /* For mmapped chunks, the overhead is one SIZE_SZ unit larger, because
1894 * there is no following chunk whose prev_size field could be used.
1896 size
= (size
+ SIZE_SZ
+ page_mask
) & ~page_mask
;
1898 p
= (mchunkptr
)MMAP(0, size
, PROT_READ
|PROT_WRITE
, MAP_PRIVATE
);
1899 if(p
== (mchunkptr
) MAP_FAILED
) return 0;
1902 if (n_mmaps
> max_n_mmaps
) max_n_mmaps
= n_mmaps
;
1904 /* We demand that eight bytes into a page must be 8-byte aligned. */
1905 assert(aligned_OK(chunk2mem(p
)));
1907 /* The offset to the start of the mmapped region is stored
1908 * in the prev_size field of the chunk; normally it is zero,
1909 * but that can be changed in memalign().
1912 set_head(p
, size
|IS_MMAPPED
);
1914 mmapped_mem
+= size
;
1915 if ((unsigned long)mmapped_mem
> (unsigned long)max_mmapped_mem
)
1916 max_mmapped_mem
= mmapped_mem
;
1918 if ((unsigned long)(mmapped_mem
+ arena_mem
+ sbrked_mem
) > max_total_mem
)
1919 max_total_mem
= mmapped_mem
+ arena_mem
+ sbrked_mem
;
1927 munmap_chunk(mchunkptr p
)
1929 munmap_chunk(p
) mchunkptr p
;
1932 INTERNAL_SIZE_T size
= chunksize(p
);
1935 assert (chunk_is_mmapped(p
));
1936 assert(! ((char*)p
>= sbrk_base
&& (char*)p
< sbrk_base
+ sbrked_mem
));
1937 assert((n_mmaps
> 0));
1938 assert(((p
->prev_size
+ size
) & (malloc_getpagesize
-1)) == 0);
1941 mmapped_mem
-= (size
+ p
->prev_size
);
1943 ret
= munmap((char *)p
- p
->prev_size
, size
+ p
->prev_size
);
1945 /* munmap returns non-zero on failure */
1954 mremap_chunk(mchunkptr p
, size_t new_size
)
1956 mremap_chunk(p
, new_size
) mchunkptr p
; size_t new_size
;
1959 size_t page_mask
= malloc_getpagesize
- 1;
1960 INTERNAL_SIZE_T offset
= p
->prev_size
;
1961 INTERNAL_SIZE_T size
= chunksize(p
);
1964 assert (chunk_is_mmapped(p
));
1965 assert(! ((char*)p
>= sbrk_base
&& (char*)p
< sbrk_base
+ sbrked_mem
));
1966 assert((n_mmaps
> 0));
1967 assert(((size
+ offset
) & (malloc_getpagesize
-1)) == 0);
1969 /* Note the extra SIZE_SZ overhead as in mmap_chunk(). */
1970 new_size
= (new_size
+ offset
+ SIZE_SZ
+ page_mask
) & ~page_mask
;
1972 cp
= (char *)mremap((char *)p
- offset
, size
+ offset
, new_size
,
1975 if (cp
== MAP_FAILED
) return 0;
1977 p
= (mchunkptr
)(cp
+ offset
);
1979 assert(aligned_OK(chunk2mem(p
)));
1981 assert((p
->prev_size
== offset
));
1982 set_head(p
, (new_size
- offset
)|IS_MMAPPED
);
1984 mmapped_mem
-= size
+ offset
;
1985 mmapped_mem
+= new_size
;
1986 if ((unsigned long)mmapped_mem
> (unsigned long)max_mmapped_mem
)
1987 max_mmapped_mem
= mmapped_mem
;
1989 if ((unsigned long)(mmapped_mem
+ arena_mem
+ sbrked_mem
) > max_total_mem
)
1990 max_total_mem
= mmapped_mem
+ arena_mem
+ sbrked_mem
;
1995 #endif /* HAVE_MREMAP */
1997 #endif /* HAVE_MMAP */
2001 /* Managing heaps and arenas (for concurrent threads) */
2005 /* Create a new heap. size is automatically rounded up to a multiple
2006 of the page size. */
2011 new_heap(size_t size
)
2013 new_heap(size
) size_t size
;
2016 size_t page_mask
= malloc_getpagesize
- 1;
2021 if(size
+top_pad
< HEAP_MIN_SIZE
)
2022 size
= HEAP_MIN_SIZE
;
2023 else if(size
+top_pad
<= HEAP_MAX_SIZE
)
2025 else if(size
> HEAP_MAX_SIZE
)
2028 size
= HEAP_MAX_SIZE
;
2029 size
= (size
+ page_mask
) & ~page_mask
;
2031 /* A memory region aligned to a multiple of HEAP_MAX_SIZE is needed.
2032 No swap space needs to be reserved for the following large
2033 mapping (on Linux, this is the case for all non-writable mappings
2035 p1
= (char *)MMAP(0, HEAP_MAX_SIZE
<<1, PROT_NONE
, MAP_PRIVATE
|MAP_NORESERVE
);
2036 if(p1
!= MAP_FAILED
) {
2037 p2
= (char *)(((unsigned long)p1
+ (HEAP_MAX_SIZE
-1)) & ~(HEAP_MAX_SIZE
-1));
2040 munmap(p2
+ HEAP_MAX_SIZE
, HEAP_MAX_SIZE
- ul
);
2042 /* Try to take the chance that an allocation of only HEAP_MAX_SIZE
2043 is already aligned. */
2044 p2
= (char *)MMAP(0, HEAP_MAX_SIZE
, PROT_NONE
, MAP_PRIVATE
|MAP_NORESERVE
);
2045 if(p2
== MAP_FAILED
)
2047 if((unsigned long)p2
& (HEAP_MAX_SIZE
-1)) {
2048 munmap(p2
, HEAP_MAX_SIZE
);
2052 if(mprotect(p2
, size
, PROT_READ
|PROT_WRITE
) != 0) {
2053 munmap(p2
, HEAP_MAX_SIZE
);
2056 h
= (heap_info
*)p2
;
2058 THREAD_STAT(stat_n_heaps
++);
2062 /* Grow or shrink a heap. size is automatically rounded up to a
2063 multiple of the page size if it is positive. */
2067 grow_heap(heap_info
*h
, long diff
)
2069 grow_heap(h
, diff
) heap_info
*h
; long diff
;
2072 size_t page_mask
= malloc_getpagesize
- 1;
2076 diff
= (diff
+ page_mask
) & ~page_mask
;
2077 new_size
= (long)h
->size
+ diff
;
2078 if(new_size
> HEAP_MAX_SIZE
)
2080 if(mprotect((char *)h
+ h
->size
, diff
, PROT_READ
|PROT_WRITE
) != 0)
2083 new_size
= (long)h
->size
+ diff
;
2084 if(new_size
< (long)sizeof(*h
))
2086 /* Try to re-map the extra heap space freshly to save memory, and
2087 make it inaccessible. */
2088 if((char *)MMAP((char *)h
+ new_size
, -diff
, PROT_NONE
,
2089 MAP_PRIVATE
|MAP_FIXED
) == (char *) MAP_FAILED
)
2096 /* Delete a heap. */
2098 #define delete_heap(heap) munmap((char*)(heap), HEAP_MAX_SIZE)
2100 /* arena_get() acquires an arena and locks the corresponding mutex.
2101 First, try the one last locked successfully by this thread. (This
2102 is the common case and handled with a macro for speed.) Then, loop
2103 once over the circularly linked list of arenas. If no arena is
2104 readily available, create a new one. In this latter case, `size'
2105 is just a hint as to how much memory will be required immediately
2106 in the new arena. */
2108 #define arena_get(ptr, size) do { \
2109 Void_t *vptr = NULL; \
2110 ptr = (arena *)tsd_getspecific(arena_key, vptr); \
2111 if(ptr && !mutex_trylock(&ptr->mutex)) { \
2112 THREAD_STAT(++(ptr->stat_lock_direct)); \
2114 ptr = arena_get2(ptr, (size)); \
2120 arena_get2(arena
*a_tsd
, size_t size
)
2122 arena_get2(a_tsd
, size
) arena
*a_tsd
; size_t size
;
2129 unsigned long misalign
;
2132 a
= a_tsd
= &main_arena
;
2136 /* This can only happen while initializing the new arena. */
2137 (void)mutex_lock(&main_arena
.mutex
);
2138 THREAD_STAT(++(main_arena
.stat_lock_wait
));
2143 /* Check the global, circularly linked list for available arenas. */
2146 if(!mutex_trylock(&a
->mutex
)) {
2147 THREAD_STAT(++(a
->stat_lock_loop
));
2148 tsd_setspecific(arena_key
, (Void_t
*)a
);
2152 } while(a
!= a_tsd
);
2154 /* If not even the list_lock can be obtained, try again. This can
2155 happen during `atfork', or for example on systems where thread
2156 creation makes it temporarily impossible to obtain _any_
2158 if(mutex_trylock(&list_lock
)) {
2162 (void)mutex_unlock(&list_lock
);
2164 /* Nothing immediately available, so generate a new arena. */
2165 h
= new_heap(size
+ (sizeof(*h
) + sizeof(*a
) + MALLOC_ALIGNMENT
));
2167 /* Maybe size is too large to fit in a single heap. So, just try
2168 to create a minimally-sized arena and let chunk_alloc() attempt
2169 to deal with the large request via mmap_chunk(). */
2170 h
= new_heap(sizeof(*h
) + sizeof(*a
) + MALLOC_ALIGNMENT
);
2174 a
= h
->ar_ptr
= (arena
*)(h
+1);
2175 for(i
=0; i
<NAV
; i
++)
2179 arena_mem
+= h
->size
;
2181 if((unsigned long)(mmapped_mem
+ arena_mem
+ sbrked_mem
) > max_total_mem
)
2182 max_total_mem
= mmapped_mem
+ arena_mem
+ sbrked_mem
;
2184 tsd_setspecific(arena_key
, (Void_t
*)a
);
2185 mutex_init(&a
->mutex
);
2186 i
= mutex_lock(&a
->mutex
); /* remember result */
2188 /* Set up the top chunk, with proper alignment. */
2189 ptr
= (char *)(a
+ 1);
2190 misalign
= (unsigned long)chunk2mem(ptr
) & MALLOC_ALIGN_MASK
;
2192 ptr
+= MALLOC_ALIGNMENT
- misalign
;
2193 top(a
) = (mchunkptr
)ptr
;
2194 set_head(top(a
), (((char*)h
+ h
->size
) - ptr
) | PREV_INUSE
);
2196 /* Add the new arena to the list. */
2197 (void)mutex_lock(&list_lock
);
2198 a
->next
= main_arena
.next
;
2199 main_arena
.next
= a
;
2200 (void)mutex_unlock(&list_lock
);
2202 if(i
) /* locking failed; keep arena for further attempts later */
2205 THREAD_STAT(++(a
->stat_lock_loop
));
2209 /* find the heap and corresponding arena for a given ptr */
2211 #define heap_for_ptr(ptr) \
2212 ((heap_info *)((unsigned long)(ptr) & ~(HEAP_MAX_SIZE-1)))
2213 #define arena_for_ptr(ptr) \
2214 (((mchunkptr)(ptr) < top(&main_arena) && (char *)(ptr) >= sbrk_base) ? \
2215 &main_arena : heap_for_ptr(ptr)->ar_ptr)
2217 #else /* !USE_ARENAS */
2219 /* There is only one arena, main_arena. */
2221 #define arena_get(ptr, sz) (ptr = &main_arena)
2222 #define arena_for_ptr(ptr) (&main_arena)
2224 #endif /* USE_ARENAS */
2236 These routines make a number of assertions about the states
2237 of data structures that should be true at all times. If any
2238 are not true, it's very likely that a user program has somehow
2239 trashed memory. (It's also possible that there is a coding error
2240 in malloc. In which case, please report it!)
2244 static void do_check_chunk(arena
*ar_ptr
, mchunkptr p
)
2246 static void do_check_chunk(ar_ptr
, p
) arena
*ar_ptr
; mchunkptr p
;
2249 INTERNAL_SIZE_T sz
= p
->size
& ~PREV_INUSE
;
2251 /* No checkable chunk is mmapped */
2252 assert(!chunk_is_mmapped(p
));
2255 if(ar_ptr
!= &main_arena
) {
2256 heap_info
*heap
= heap_for_ptr(p
);
2257 assert(heap
->ar_ptr
== ar_ptr
);
2258 if(p
!= top(ar_ptr
))
2259 assert((char *)p
+ sz
<= (char *)heap
+ heap
->size
);
2261 assert((char *)p
+ sz
== (char *)heap
+ heap
->size
);
2266 /* Check for legal address ... */
2267 assert((char*)p
>= sbrk_base
);
2268 if (p
!= top(ar_ptr
))
2269 assert((char*)p
+ sz
<= (char*)top(ar_ptr
));
2271 assert((char*)p
+ sz
<= sbrk_base
+ sbrked_mem
);
2277 static void do_check_free_chunk(arena
*ar_ptr
, mchunkptr p
)
2279 static void do_check_free_chunk(ar_ptr
, p
) arena
*ar_ptr
; mchunkptr p
;
2282 INTERNAL_SIZE_T sz
= p
->size
& ~PREV_INUSE
;
2283 mchunkptr next
= chunk_at_offset(p
, sz
);
2285 do_check_chunk(ar_ptr
, p
);
2287 /* Check whether it claims to be free ... */
2290 /* Must have OK size and fields */
2291 assert((long)sz
>= (long)MINSIZE
);
2292 assert((sz
& MALLOC_ALIGN_MASK
) == 0);
2293 assert(aligned_OK(chunk2mem(p
)));
2294 /* ... matching footer field */
2295 assert(next
->prev_size
== sz
);
2296 /* ... and is fully consolidated */
2297 assert(prev_inuse(p
));
2298 assert (next
== top(ar_ptr
) || inuse(next
));
2300 /* ... and has minimally sane links */
2301 assert(p
->fd
->bk
== p
);
2302 assert(p
->bk
->fd
== p
);
2306 static void do_check_inuse_chunk(arena
*ar_ptr
, mchunkptr p
)
2308 static void do_check_inuse_chunk(ar_ptr
, p
) arena
*ar_ptr
; mchunkptr p
;
2311 mchunkptr next
= next_chunk(p
);
2312 do_check_chunk(ar_ptr
, p
);
2314 /* Check whether it claims to be in use ... */
2317 /* ... whether its size is OK (it might be a fencepost) ... */
2318 assert(chunksize(p
) >= MINSIZE
|| next
->size
== (0|PREV_INUSE
));
2320 /* ... and is surrounded by OK chunks.
2321 Since more things can be checked with free chunks than inuse ones,
2322 if an inuse chunk borders them and debug is on, it's worth doing them.
2326 mchunkptr prv
= prev_chunk(p
);
2327 assert(next_chunk(prv
) == p
);
2328 do_check_free_chunk(ar_ptr
, prv
);
2330 if (next
== top(ar_ptr
))
2332 assert(prev_inuse(next
));
2333 assert(chunksize(next
) >= MINSIZE
);
2335 else if (!inuse(next
))
2336 do_check_free_chunk(ar_ptr
, next
);
2341 static void do_check_malloced_chunk(arena
*ar_ptr
,
2342 mchunkptr p
, INTERNAL_SIZE_T s
)
2344 static void do_check_malloced_chunk(ar_ptr
, p
, s
)
2345 arena
*ar_ptr
; mchunkptr p
; INTERNAL_SIZE_T s
;
2348 INTERNAL_SIZE_T sz
= p
->size
& ~PREV_INUSE
;
2351 do_check_inuse_chunk(ar_ptr
, p
);
2353 /* Legal size ... */
2354 assert((long)sz
>= (long)MINSIZE
);
2355 assert((sz
& MALLOC_ALIGN_MASK
) == 0);
2357 assert(room
< (long)MINSIZE
);
2359 /* ... and alignment */
2360 assert(aligned_OK(chunk2mem(p
)));
2363 /* ... and was allocated at front of an available chunk */
2364 assert(prev_inuse(p
));
2369 #define check_free_chunk(A,P) do_check_free_chunk(A,P)
2370 #define check_inuse_chunk(A,P) do_check_inuse_chunk(A,P)
2371 #define check_chunk(A,P) do_check_chunk(A,P)
2372 #define check_malloced_chunk(A,P,N) do_check_malloced_chunk(A,P,N)
2374 #define check_free_chunk(A,P)
2375 #define check_inuse_chunk(A,P)
2376 #define check_chunk(A,P)
2377 #define check_malloced_chunk(A,P,N)
2383 Macro-based internal utilities
2388 Linking chunks in bin lists.
2389 Call these only with variables, not arbitrary expressions, as arguments.
2393 Place chunk p of size s in its bin, in size order,
2394 putting it ahead of others of same size.
2398 #define frontlink(A, P, S, IDX, BK, FD) \
2400 if (S < MAX_SMALLBIN_SIZE) \
2402 IDX = smallbin_index(S); \
2403 mark_binblock(A, IDX); \
2404 BK = bin_at(A, IDX); \
2408 FD->bk = BK->fd = P; \
2412 IDX = bin_index(S); \
2413 BK = bin_at(A, IDX); \
2415 if (FD == BK) mark_binblock(A, IDX); \
2418 while (FD != BK && S < chunksize(FD)) FD = FD->fd; \
2423 FD->bk = BK->fd = P; \
2428 /* take a chunk off a list */
2430 #define unlink(P, BK, FD) \
2438 /* Place p as the last remainder */
2440 #define link_last_remainder(A, P) \
2442 last_remainder(A)->fd = last_remainder(A)->bk = P; \
2443 P->fd = P->bk = last_remainder(A); \
2446 /* Clear the last_remainder bin */
2448 #define clear_last_remainder(A) \
2449 (last_remainder(A)->fd = last_remainder(A)->bk = last_remainder(A))
2456 Extend the top-most chunk by obtaining memory from system.
2457 Main interface to sbrk (but see also malloc_trim).
2460 #if defined __GNUC__ && __GNUC__ >= 2
2461 /* This function is called only from one place, inline it. */
2467 malloc_extend_top(arena
*ar_ptr
, INTERNAL_SIZE_T nb
)
2469 malloc_extend_top(ar_ptr
, nb
) arena
*ar_ptr
; INTERNAL_SIZE_T nb
;
2472 unsigned long pagesz
= malloc_getpagesize
;
2473 mchunkptr old_top
= top(ar_ptr
); /* Record state of old top */
2474 INTERNAL_SIZE_T old_top_size
= chunksize(old_top
);
2475 INTERNAL_SIZE_T top_size
; /* new size of top chunk */
2478 if(ar_ptr
== &main_arena
) {
2481 char* brk
; /* return value from sbrk */
2482 INTERNAL_SIZE_T front_misalign
; /* unusable bytes at front of sbrked space */
2483 INTERNAL_SIZE_T correction
; /* bytes for 2nd sbrk call */
2484 char* new_brk
; /* return of 2nd sbrk call */
2485 char* old_end
= (char*)(chunk_at_offset(old_top
, old_top_size
));
2487 /* Pad request with top_pad plus minimal overhead */
2488 INTERNAL_SIZE_T sbrk_size
= nb
+ top_pad
+ MINSIZE
;
2490 /* If not the first time through, round to preserve page boundary */
2491 /* Otherwise, we need to correct to a page size below anyway. */
2492 /* (We also correct below if an intervening foreign sbrk call.) */
2494 if (sbrk_base
!= (char*)(-1))
2495 sbrk_size
= (sbrk_size
+ (pagesz
- 1)) & ~(pagesz
- 1);
2497 brk
= (char*)(MORECORE (sbrk_size
));
2499 /* Fail if sbrk failed or if a foreign sbrk call killed our space */
2500 if (brk
== (char*)(MORECORE_FAILURE
) ||
2501 (brk
< old_end
&& old_top
!= initial_top(&main_arena
)))
2504 #if defined _LIBC || defined MALLOC_HOOKS
2505 /* Call the `morecore' hook if necessary. */
2506 if (__after_morecore_hook
)
2507 (*__after_morecore_hook
) ();
2510 sbrked_mem
+= sbrk_size
;
2512 if (brk
== old_end
) { /* can just add bytes to current top */
2513 top_size
= sbrk_size
+ old_top_size
;
2514 set_head(old_top
, top_size
| PREV_INUSE
);
2515 old_top
= 0; /* don't free below */
2517 if (sbrk_base
== (char*)(-1)) /* First time through. Record base */
2520 /* Someone else called sbrk(). Count those bytes as sbrked_mem. */
2521 sbrked_mem
+= brk
- (char*)old_end
;
2523 /* Guarantee alignment of first new chunk made from this space */
2524 front_misalign
= (unsigned long)chunk2mem(brk
) & MALLOC_ALIGN_MASK
;
2525 if (front_misalign
> 0) {
2526 correction
= (MALLOC_ALIGNMENT
) - front_misalign
;
2531 /* Guarantee the next brk will be at a page boundary */
2532 correction
+= pagesz
- ((unsigned long)(brk
+ sbrk_size
) & (pagesz
- 1));
2534 /* Allocate correction */
2535 new_brk
= (char*)(MORECORE (correction
));
2536 if (new_brk
== (char*)(MORECORE_FAILURE
)) return;
2538 #if defined _LIBC || defined MALLOC_HOOKS
2539 /* Call the `morecore' hook if necessary. */
2540 if (__after_morecore_hook
)
2541 (*__after_morecore_hook
) ();
2544 sbrked_mem
+= correction
;
2546 top(&main_arena
) = chunk_at_offset(brk
, 0);
2547 top_size
= new_brk
- brk
+ correction
;
2548 set_head(top(&main_arena
), top_size
| PREV_INUSE
);
2550 if (old_top
== initial_top(&main_arena
))
2551 old_top
= 0; /* don't free below */
2554 if ((unsigned long)sbrked_mem
> (unsigned long)max_sbrked_mem
)
2555 max_sbrked_mem
= sbrked_mem
;
2557 if ((unsigned long)(mmapped_mem
+ arena_mem
+ sbrked_mem
) > max_total_mem
)
2558 max_total_mem
= mmapped_mem
+ arena_mem
+ sbrked_mem
;
2562 } else { /* ar_ptr != &main_arena */
2563 heap_info
*old_heap
, *heap
;
2564 size_t old_heap_size
;
2566 if(old_top_size
< MINSIZE
) /* this should never happen */
2569 /* First try to extend the current heap. */
2570 if(MINSIZE
+ nb
<= old_top_size
)
2572 old_heap
= heap_for_ptr(old_top
);
2573 old_heap_size
= old_heap
->size
;
2574 if(grow_heap(old_heap
, MINSIZE
+ nb
- old_top_size
) == 0) {
2575 ar_ptr
->size
+= old_heap
->size
- old_heap_size
;
2576 arena_mem
+= old_heap
->size
- old_heap_size
;
2578 if(mmapped_mem
+ arena_mem
+ sbrked_mem
> max_total_mem
)
2579 max_total_mem
= mmapped_mem
+ arena_mem
+ sbrked_mem
;
2581 top_size
= ((char *)old_heap
+ old_heap
->size
) - (char *)old_top
;
2582 set_head(old_top
, top_size
| PREV_INUSE
);
2586 /* A new heap must be created. */
2587 heap
= new_heap(nb
+ (MINSIZE
+ sizeof(*heap
)));
2590 heap
->ar_ptr
= ar_ptr
;
2591 heap
->prev
= old_heap
;
2592 ar_ptr
->size
+= heap
->size
;
2593 arena_mem
+= heap
->size
;
2595 if((unsigned long)(mmapped_mem
+ arena_mem
+ sbrked_mem
) > max_total_mem
)
2596 max_total_mem
= mmapped_mem
+ arena_mem
+ sbrked_mem
;
2599 /* Set up the new top, so we can safely use chunk_free() below. */
2600 top(ar_ptr
) = chunk_at_offset(heap
, sizeof(*heap
));
2601 top_size
= heap
->size
- sizeof(*heap
);
2602 set_head(top(ar_ptr
), top_size
| PREV_INUSE
);
2604 #endif /* USE_ARENAS */
2606 /* We always land on a page boundary */
2607 assert(((unsigned long)((char*)top(ar_ptr
) + top_size
) & (pagesz
-1)) == 0);
2609 /* Setup fencepost and free the old top chunk. */
2611 /* The fencepost takes at least MINSIZE bytes, because it might
2612 become the top chunk again later. Note that a footer is set
2613 up, too, although the chunk is marked in use. */
2614 old_top_size
-= MINSIZE
;
2615 set_head(chunk_at_offset(old_top
, old_top_size
+ 2*SIZE_SZ
), 0|PREV_INUSE
);
2616 if(old_top_size
>= MINSIZE
) {
2617 set_head(chunk_at_offset(old_top
, old_top_size
), (2*SIZE_SZ
)|PREV_INUSE
);
2618 set_foot(chunk_at_offset(old_top
, old_top_size
), (2*SIZE_SZ
));
2619 set_head_size(old_top
, old_top_size
);
2620 chunk_free(ar_ptr
, old_top
);
2622 set_head(old_top
, (old_top_size
+ 2*SIZE_SZ
)|PREV_INUSE
);
2623 set_foot(old_top
, (old_top_size
+ 2*SIZE_SZ
));
2631 /* Main public routines */
2637 The requested size is first converted into a usable form, `nb'.
2638 This currently means to add 4 bytes overhead plus possibly more to
2639 obtain 8-byte alignment and/or to obtain a size of at least
2640 MINSIZE (currently 16, 24, or 32 bytes), the smallest allocatable
2641 size. (All fits are considered `exact' if they are within MINSIZE
2644 From there, the first successful of the following steps is taken:
2646 1. The bin corresponding to the request size is scanned, and if
2647 a chunk of exactly the right size is found, it is taken.
2649 2. The most recently remaindered chunk is used if it is big
2650 enough. This is a form of (roving) first fit, used only in
2651 the absence of exact fits. Runs of consecutive requests use
2652 the remainder of the chunk used for the previous such request
2653 whenever possible. This limited use of a first-fit style
2654 allocation strategy tends to give contiguous chunks
2655 coextensive lifetimes, which improves locality and can reduce
2656 fragmentation in the long run.
2658 3. Other bins are scanned in increasing size order, using a
2659 chunk big enough to fulfill the request, and splitting off
2660 any remainder. This search is strictly by best-fit; i.e.,
2661 the smallest (with ties going to approximately the least
2662 recently used) chunk that fits is selected.
2664 4. If large enough, the chunk bordering the end of memory
2665 (`top') is split off. (This use of `top' is in accord with
2666 the best-fit search rule. In effect, `top' is treated as
2667 larger (and thus less well fitting) than any other available
2668 chunk since it can be extended to be as large as necessary
2669 (up to system limitations).
2671 5. If the request size meets the mmap threshold and the
2672 system supports mmap, and there are few enough currently
2673 allocated mmapped regions, and a call to mmap succeeds,
2674 the request is allocated via direct memory mapping.
2676 6. Otherwise, the top of memory is extended by
2677 obtaining more space from the system (normally using sbrk,
2678 but definable to anything else via the MORECORE macro).
2679 Memory is gathered from the system (in system page-sized
2680 units) in a way that allows chunks obtained across different
2681 sbrk calls to be consolidated, but does not require
2682 contiguous memory. Thus, it should be safe to intersperse
2683 mallocs with other sbrk calls.
2686 All allocations are made from the `lowest' part of any found
2687 chunk. (The implementation invariant is that prev_inuse is
2688 always true of any allocated chunk; i.e., that each allocated
2689 chunk borders either a previously allocated and still in-use chunk,
2690 or the base of its memory arena.)
2695 Void_t
* mALLOc(size_t bytes
)
2697 Void_t
* mALLOc(bytes
) size_t bytes
;
2701 INTERNAL_SIZE_T nb
; /* padded request size */
2704 #if defined _LIBC || defined MALLOC_HOOKS
2705 if (__malloc_hook
!= NULL
) {
2708 #if defined __GNUC__ && __GNUC__ >= 2
2709 result
= (*__malloc_hook
)(bytes
, RETURN_ADDRESS (0));
2711 result
= (*__malloc_hook
)(bytes
, NULL
);
2717 if(request2size(bytes
, nb
))
2719 arena_get(ar_ptr
, nb
);
2722 victim
= chunk_alloc(ar_ptr
, nb
);
2724 /* Maybe the failure is due to running out of mmapped areas. */
2725 if(ar_ptr
!= &main_arena
) {
2726 (void)mutex_unlock(&ar_ptr
->mutex
);
2727 (void)mutex_lock(&main_arena
.mutex
);
2728 victim
= chunk_alloc(&main_arena
, nb
);
2729 (void)mutex_unlock(&main_arena
.mutex
);
2732 /* ... or sbrk() has failed and there is still a chance to mmap() */
2733 ar_ptr
= arena_get2(ar_ptr
->next
? ar_ptr
: 0, nb
);
2734 (void)mutex_unlock(&main_arena
.mutex
);
2736 victim
= chunk_alloc(ar_ptr
, nb
);
2737 (void)mutex_unlock(&ar_ptr
->mutex
);
2741 if(!victim
) return 0;
2743 (void)mutex_unlock(&ar_ptr
->mutex
);
2744 return BOUNDED_N(chunk2mem(victim
), bytes
);
2750 chunk_alloc(arena
*ar_ptr
, INTERNAL_SIZE_T nb
)
2752 chunk_alloc(ar_ptr
, nb
) arena
*ar_ptr
; INTERNAL_SIZE_T nb
;
2755 mchunkptr victim
; /* inspected/selected chunk */
2756 INTERNAL_SIZE_T victim_size
; /* its size */
2757 int idx
; /* index for bin traversal */
2758 mbinptr bin
; /* associated bin */
2759 mchunkptr remainder
; /* remainder from a split */
2760 long remainder_size
; /* its size */
2761 int remainder_index
; /* its bin index */
2762 unsigned long block
; /* block traverser bit */
2763 int startidx
; /* first bin of a traversed block */
2764 mchunkptr fwd
; /* misc temp for linking */
2765 mchunkptr bck
; /* misc temp for linking */
2766 mbinptr q
; /* misc temp */
2769 /* Check for exact match in a bin */
2771 if (is_small_request(nb
)) /* Faster version for small requests */
2773 idx
= smallbin_index(nb
);
2775 /* No traversal or size check necessary for small bins. */
2777 q
= _bin_at(ar_ptr
, idx
);
2780 /* Also scan the next one, since it would have a remainder < MINSIZE */
2788 victim_size
= chunksize(victim
);
2789 unlink(victim
, bck
, fwd
);
2790 set_inuse_bit_at_offset(victim
, victim_size
);
2791 check_malloced_chunk(ar_ptr
, victim
, nb
);
2795 idx
+= 2; /* Set for bin scan below. We've already scanned 2 bins. */
2800 idx
= bin_index(nb
);
2801 bin
= bin_at(ar_ptr
, idx
);
2803 for (victim
= last(bin
); victim
!= bin
; victim
= victim
->bk
)
2805 victim_size
= chunksize(victim
);
2806 remainder_size
= victim_size
- nb
;
2808 if (remainder_size
>= (long)MINSIZE
) /* too big */
2810 --idx
; /* adjust to rescan below after checking last remainder */
2814 else if (remainder_size
>= 0) /* exact fit */
2816 unlink(victim
, bck
, fwd
);
2817 set_inuse_bit_at_offset(victim
, victim_size
);
2818 check_malloced_chunk(ar_ptr
, victim
, nb
);
2827 /* Try to use the last split-off remainder */
2829 if ( (victim
= last_remainder(ar_ptr
)->fd
) != last_remainder(ar_ptr
))
2831 victim_size
= chunksize(victim
);
2832 remainder_size
= victim_size
- nb
;
2834 if (remainder_size
>= (long)MINSIZE
) /* re-split */
2836 remainder
= chunk_at_offset(victim
, nb
);
2837 set_head(victim
, nb
| PREV_INUSE
);
2838 link_last_remainder(ar_ptr
, remainder
);
2839 set_head(remainder
, remainder_size
| PREV_INUSE
);
2840 set_foot(remainder
, remainder_size
);
2841 check_malloced_chunk(ar_ptr
, victim
, nb
);
2845 clear_last_remainder(ar_ptr
);
2847 if (remainder_size
>= 0) /* exhaust */
2849 set_inuse_bit_at_offset(victim
, victim_size
);
2850 check_malloced_chunk(ar_ptr
, victim
, nb
);
2854 /* Else place in bin */
2856 frontlink(ar_ptr
, victim
, victim_size
, remainder_index
, bck
, fwd
);
2860 If there are any possibly nonempty big-enough blocks,
2861 search for best fitting chunk by scanning bins in blockwidth units.
2864 if ( (block
= idx2binblock(idx
)) <= binblocks(ar_ptr
))
2867 /* Get to the first marked block */
2869 if ( (block
& binblocks(ar_ptr
)) == 0)
2871 /* force to an even block boundary */
2872 idx
= (idx
& ~(BINBLOCKWIDTH
- 1)) + BINBLOCKWIDTH
;
2874 while ((block
& binblocks(ar_ptr
)) == 0)
2876 idx
+= BINBLOCKWIDTH
;
2881 /* For each possibly nonempty block ... */
2884 startidx
= idx
; /* (track incomplete blocks) */
2885 q
= bin
= _bin_at(ar_ptr
, idx
);
2887 /* For each bin in this block ... */
2890 /* Find and use first big enough chunk ... */
2892 for (victim
= last(bin
); victim
!= bin
; victim
= victim
->bk
)
2894 victim_size
= chunksize(victim
);
2895 remainder_size
= victim_size
- nb
;
2897 if (remainder_size
>= (long)MINSIZE
) /* split */
2899 remainder
= chunk_at_offset(victim
, nb
);
2900 set_head(victim
, nb
| PREV_INUSE
);
2901 unlink(victim
, bck
, fwd
);
2902 link_last_remainder(ar_ptr
, remainder
);
2903 set_head(remainder
, remainder_size
| PREV_INUSE
);
2904 set_foot(remainder
, remainder_size
);
2905 check_malloced_chunk(ar_ptr
, victim
, nb
);
2909 else if (remainder_size
>= 0) /* take */
2911 set_inuse_bit_at_offset(victim
, victim_size
);
2912 unlink(victim
, bck
, fwd
);
2913 check_malloced_chunk(ar_ptr
, victim
, nb
);
2919 bin
= next_bin(bin
);
2921 } while ((++idx
& (BINBLOCKWIDTH
- 1)) != 0);
2923 /* Clear out the block bit. */
2925 do /* Possibly backtrack to try to clear a partial block */
2927 if ((startidx
& (BINBLOCKWIDTH
- 1)) == 0)
2929 binblocks(ar_ptr
) &= ~block
;
2934 } while (first(q
) == q
);
2936 /* Get to the next possibly nonempty block */
2938 if ( (block
<<= 1) <= binblocks(ar_ptr
) && (block
!= 0) )
2940 while ((block
& binblocks(ar_ptr
)) == 0)
2942 idx
+= BINBLOCKWIDTH
;
2952 /* Try to use top chunk */
2954 /* Require that there be a remainder, ensuring top always exists */
2955 if ( (remainder_size
= chunksize(top(ar_ptr
)) - nb
) < (long)MINSIZE
)
2959 /* If the request is big and there are not yet too many regions,
2960 and we would otherwise need to extend, try to use mmap instead. */
2961 if ((unsigned long)nb
>= (unsigned long)mmap_threshold
&&
2962 n_mmaps
< n_mmaps_max
&&
2963 (victim
= mmap_chunk(nb
)) != 0)
2968 malloc_extend_top(ar_ptr
, nb
);
2969 if ((remainder_size
= chunksize(top(ar_ptr
)) - nb
) < (long)MINSIZE
)
2972 /* A last attempt: when we are out of address space in a
2973 non-main arena, try mmap anyway, as long as it is allowed at
2975 if (ar_ptr
!= &main_arena
&&
2977 (victim
= mmap_chunk(nb
)) != 0)
2980 return 0; /* propagate failure */
2984 victim
= top(ar_ptr
);
2985 set_head(victim
, nb
| PREV_INUSE
);
2986 top(ar_ptr
) = chunk_at_offset(victim
, nb
);
2987 set_head(top(ar_ptr
), remainder_size
| PREV_INUSE
);
2988 check_malloced_chunk(ar_ptr
, victim
, nb
);
3002 1. free(0) has no effect.
3004 2. If the chunk was allocated via mmap, it is released via munmap().
3006 3. If a returned chunk borders the current high end of memory,
3007 it is consolidated into the top, and if the total unused
3008 topmost memory exceeds the trim threshold, malloc_trim is
3011 4. Other chunks are consolidated as they arrive, and
3012 placed in corresponding bins. (This includes the case of
3013 consolidating with the current `last_remainder').
3019 void fREe(Void_t
* mem
)
3021 void fREe(mem
) Void_t
* mem
;
3025 mchunkptr p
; /* chunk corresponding to mem */
3027 #if defined _LIBC || defined MALLOC_HOOKS
3028 if (__free_hook
!= NULL
) {
3029 #if defined __GNUC__ && __GNUC__ >= 2
3030 (*__free_hook
)(mem
, RETURN_ADDRESS (0));
3032 (*__free_hook
)(mem
, NULL
);
3038 if (mem
== 0) /* free(0) has no effect */
3044 if (chunk_is_mmapped(p
)) /* release mmapped memory. */
3051 ar_ptr
= arena_for_ptr(p
);
3053 if(!mutex_trylock(&ar_ptr
->mutex
))
3054 ++(ar_ptr
->stat_lock_direct
);
3056 (void)mutex_lock(&ar_ptr
->mutex
);
3057 ++(ar_ptr
->stat_lock_wait
);
3060 (void)mutex_lock(&ar_ptr
->mutex
);
3062 chunk_free(ar_ptr
, p
);
3063 (void)mutex_unlock(&ar_ptr
->mutex
);
3069 chunk_free(arena
*ar_ptr
, mchunkptr p
)
3071 chunk_free(ar_ptr
, p
) arena
*ar_ptr
; mchunkptr p
;
3074 INTERNAL_SIZE_T hd
= p
->size
; /* its head field */
3075 INTERNAL_SIZE_T sz
; /* its size */
3076 int idx
; /* its bin index */
3077 mchunkptr next
; /* next contiguous chunk */
3078 INTERNAL_SIZE_T nextsz
; /* its size */
3079 INTERNAL_SIZE_T prevsz
; /* size of previous contiguous chunk */
3080 mchunkptr bck
; /* misc temp for linking */
3081 mchunkptr fwd
; /* misc temp for linking */
3082 int islr
; /* track whether merging with last_remainder */
3084 check_inuse_chunk(ar_ptr
, p
);
3086 sz
= hd
& ~PREV_INUSE
;
3087 next
= chunk_at_offset(p
, sz
);
3088 nextsz
= chunksize(next
);
3090 if (next
== top(ar_ptr
)) /* merge with top */
3094 if (!(hd
& PREV_INUSE
)) /* consolidate backward */
3096 prevsz
= p
->prev_size
;
3097 p
= chunk_at_offset(p
, -(long)prevsz
);
3099 unlink(p
, bck
, fwd
);
3102 set_head(p
, sz
| PREV_INUSE
);
3106 if(ar_ptr
== &main_arena
) {
3108 if ((unsigned long)(sz
) >= (unsigned long)trim_threshold
)
3112 heap_info
*heap
= heap_for_ptr(p
);
3114 assert(heap
->ar_ptr
== ar_ptr
);
3116 /* Try to get rid of completely empty heaps, if possible. */
3117 if((unsigned long)(sz
) >= (unsigned long)trim_threshold
||
3118 p
== chunk_at_offset(heap
, sizeof(*heap
)))
3119 heap_trim(heap
, top_pad
);
3127 if (!(hd
& PREV_INUSE
)) /* consolidate backward */
3129 prevsz
= p
->prev_size
;
3130 p
= chunk_at_offset(p
, -(long)prevsz
);
3133 if (p
->fd
== last_remainder(ar_ptr
)) /* keep as last_remainder */
3136 unlink(p
, bck
, fwd
);
3139 if (!(inuse_bit_at_offset(next
, nextsz
))) /* consolidate forward */
3143 if (!islr
&& next
->fd
== last_remainder(ar_ptr
))
3144 /* re-insert last_remainder */
3147 link_last_remainder(ar_ptr
, p
);
3150 unlink(next
, bck
, fwd
);
3152 next
= chunk_at_offset(p
, sz
);
3155 set_head(next
, nextsz
); /* clear inuse bit */
3157 set_head(p
, sz
| PREV_INUSE
);
3158 next
->prev_size
= sz
;
3160 frontlink(ar_ptr
, p
, sz
, idx
, bck
, fwd
);
3163 /* Check whether the heap containing top can go away now. */
3164 if(next
->size
< MINSIZE
&&
3165 (unsigned long)sz
> trim_threshold
&&
3166 ar_ptr
!= &main_arena
) { /* fencepost */
3167 heap_info
*heap
= heap_for_ptr(top(ar_ptr
));
3169 if(top(ar_ptr
) == chunk_at_offset(heap
, sizeof(*heap
)) &&
3170 heap
->prev
== heap_for_ptr(p
))
3171 heap_trim(heap
, top_pad
);
3184 Chunks that were obtained via mmap cannot be extended or shrunk
3185 unless HAVE_MREMAP is defined, in which case mremap is used.
3186 Otherwise, if their reallocation is for additional space, they are
3187 copied. If for less, they are just left alone.
3189 Otherwise, if the reallocation is for additional space, and the
3190 chunk can be extended, it is, else a malloc-copy-free sequence is
3191 taken. There are several different ways that a chunk could be
3192 extended. All are tried:
3194 * Extending forward into following adjacent free chunk.
3195 * Shifting backwards, joining preceding adjacent space
3196 * Both shifting backwards and extending forward.
3197 * Extending into newly sbrked space
3199 Unless the #define REALLOC_ZERO_BYTES_FREES is set, realloc with a
3200 size argument of zero (re)allocates a minimum-sized chunk.
3202 If the reallocation is for less space, and the new request is for
3203 a `small' (<512 bytes) size, then the newly unused space is lopped
3206 The old unix realloc convention of allowing the last-free'd chunk
3207 to be used as an argument to realloc is no longer supported.
3208 I don't know of any programs still relying on this feature,
3209 and allowing it would also allow too many other incorrect
3210 usages of realloc to be sensible.
3217 Void_t
* rEALLOc(Void_t
* oldmem
, size_t bytes
)
3219 Void_t
* rEALLOc(oldmem
, bytes
) Void_t
* oldmem
; size_t bytes
;
3223 INTERNAL_SIZE_T nb
; /* padded request size */
3225 mchunkptr oldp
; /* chunk corresponding to oldmem */
3226 INTERNAL_SIZE_T oldsize
; /* its size */
3228 mchunkptr newp
; /* chunk to return */
3230 #if defined _LIBC || defined MALLOC_HOOKS
3231 if (__realloc_hook
!= NULL
) {
3234 #if defined __GNUC__ && __GNUC__ >= 2
3235 result
= (*__realloc_hook
)(oldmem
, bytes
, RETURN_ADDRESS (0));
3237 result
= (*__realloc_hook
)(oldmem
, bytes
, NULL
);
3243 #ifdef REALLOC_ZERO_BYTES_FREES
3244 if (bytes
== 0 && oldmem
!= NULL
) { fREe(oldmem
); return 0; }
3247 /* realloc of null is supposed to be same as malloc */
3248 if (oldmem
== 0) return mALLOc(bytes
);
3250 oldp
= mem2chunk(oldmem
);
3251 oldsize
= chunksize(oldp
);
3253 if(request2size(bytes
, nb
))
3257 if (chunk_is_mmapped(oldp
))
3262 newp
= mremap_chunk(oldp
, nb
);
3264 return BOUNDED_N(chunk2mem(newp
), bytes
);
3266 /* Note the extra SIZE_SZ overhead. */
3267 if(oldsize
- SIZE_SZ
>= nb
) return oldmem
; /* do nothing */
3268 /* Must alloc, copy, free. */
3269 newmem
= mALLOc(bytes
);
3270 if (newmem
== 0) return 0; /* propagate failure */
3271 MALLOC_COPY(newmem
, oldmem
, oldsize
- 2*SIZE_SZ
, 0);
3277 ar_ptr
= arena_for_ptr(oldp
);
3279 if(!mutex_trylock(&ar_ptr
->mutex
))
3280 ++(ar_ptr
->stat_lock_direct
);
3282 (void)mutex_lock(&ar_ptr
->mutex
);
3283 ++(ar_ptr
->stat_lock_wait
);
3286 (void)mutex_lock(&ar_ptr
->mutex
);
3290 /* As in malloc(), remember this arena for the next allocation. */
3291 tsd_setspecific(arena_key
, (Void_t
*)ar_ptr
);
3294 newp
= chunk_realloc(ar_ptr
, oldp
, oldsize
, nb
);
3296 (void)mutex_unlock(&ar_ptr
->mutex
);
3297 return newp
? BOUNDED_N(chunk2mem(newp
), bytes
) : NULL
;
3303 chunk_realloc(arena
* ar_ptr
, mchunkptr oldp
, INTERNAL_SIZE_T oldsize
,
3306 chunk_realloc(ar_ptr
, oldp
, oldsize
, nb
)
3307 arena
* ar_ptr
; mchunkptr oldp
; INTERNAL_SIZE_T oldsize
, nb
;
3310 mchunkptr newp
= oldp
; /* chunk to return */
3311 INTERNAL_SIZE_T newsize
= oldsize
; /* its size */
3313 mchunkptr next
; /* next contiguous chunk after oldp */
3314 INTERNAL_SIZE_T nextsize
; /* its size */
3316 mchunkptr prev
; /* previous contiguous chunk before oldp */
3317 INTERNAL_SIZE_T prevsize
; /* its size */
3319 mchunkptr remainder
; /* holds split off extra space from newp */
3320 INTERNAL_SIZE_T remainder_size
; /* its size */
3322 mchunkptr bck
; /* misc temp for linking */
3323 mchunkptr fwd
; /* misc temp for linking */
3325 check_inuse_chunk(ar_ptr
, oldp
);
3327 if ((long)(oldsize
) < (long)(nb
))
3329 Void_t
* oldmem
= BOUNDED_N(chunk2mem(oldp
), oldsize
);
3331 /* Try expanding forward */
3333 next
= chunk_at_offset(oldp
, oldsize
);
3334 if (next
== top(ar_ptr
) || !inuse(next
))
3336 nextsize
= chunksize(next
);
3338 /* Forward into top only if a remainder */
3339 if (next
== top(ar_ptr
))
3341 if ((long)(nextsize
+ newsize
) >= (long)(nb
+ MINSIZE
))
3343 newsize
+= nextsize
;
3344 top(ar_ptr
) = chunk_at_offset(oldp
, nb
);
3345 set_head(top(ar_ptr
), (newsize
- nb
) | PREV_INUSE
);
3346 set_head_size(oldp
, nb
);
3351 /* Forward into next chunk */
3352 else if (((long)(nextsize
+ newsize
) >= (long)(nb
)))
3354 unlink(next
, bck
, fwd
);
3355 newsize
+= nextsize
;
3367 /* Try shifting backwards. */
3369 if (!prev_inuse(oldp
))
3371 prev
= prev_chunk(oldp
);
3372 prevsize
= chunksize(prev
);
3374 /* try forward + backward first to save a later consolidation */
3379 if (next
== top(ar_ptr
))
3381 if ((long)(nextsize
+ prevsize
+ newsize
) >= (long)(nb
+ MINSIZE
))
3383 unlink(prev
, bck
, fwd
);
3385 newsize
+= prevsize
+ nextsize
;
3386 MALLOC_COPY(BOUNDED_N(chunk2mem(newp
), oldsize
), oldmem
, oldsize
,
3388 top(ar_ptr
) = chunk_at_offset(newp
, nb
);
3389 set_head(top(ar_ptr
), (newsize
- nb
) | PREV_INUSE
);
3390 set_head_size(newp
, nb
);
3395 /* into next chunk */
3396 else if (((long)(nextsize
+ prevsize
+ newsize
) >= (long)(nb
)))
3398 unlink(next
, bck
, fwd
);
3399 unlink(prev
, bck
, fwd
);
3401 newsize
+= nextsize
+ prevsize
;
3402 MALLOC_COPY(BOUNDED_N(chunk2mem(newp
), oldsize
), oldmem
, oldsize
, 1);
3408 if (prev
!= 0 && (long)(prevsize
+ newsize
) >= (long)nb
)
3410 unlink(prev
, bck
, fwd
);
3412 newsize
+= prevsize
;
3413 MALLOC_COPY(BOUNDED_N(chunk2mem(newp
), oldsize
), oldmem
, oldsize
, 1);
3420 newp
= chunk_alloc (ar_ptr
, nb
);
3423 /* Maybe the failure is due to running out of mmapped areas. */
3424 if (ar_ptr
!= &main_arena
) {
3425 (void)mutex_lock(&main_arena
.mutex
);
3426 newp
= chunk_alloc(&main_arena
, nb
);
3427 (void)mutex_unlock(&main_arena
.mutex
);
3430 /* ... or sbrk() has failed and there is still a chance to mmap() */
3431 arena
* ar_ptr2
= arena_get2(ar_ptr
->next
? ar_ptr
: 0, nb
);
3433 newp
= chunk_alloc(ar_ptr2
, nb
);
3434 (void)mutex_unlock(&ar_ptr2
->mutex
);
3438 if (newp
== 0) /* propagate failure */
3442 /* Avoid copy if newp is next chunk after oldp. */
3443 /* (This can only happen when new chunk is sbrk'ed.) */
3445 if ( newp
== next_chunk(oldp
))
3447 newsize
+= chunksize(newp
);
3452 /* Otherwise copy, free, and exit */
3453 MALLOC_COPY(BOUNDED_N(chunk2mem(newp
), oldsize
), oldmem
, oldsize
, 0);
3454 chunk_free(ar_ptr
, oldp
);
3459 split
: /* split off extra room in old or expanded chunk */
3461 if (newsize
- nb
>= MINSIZE
) /* split off remainder */
3463 remainder
= chunk_at_offset(newp
, nb
);
3464 remainder_size
= newsize
- nb
;
3465 set_head_size(newp
, nb
);
3466 set_head(remainder
, remainder_size
| PREV_INUSE
);
3467 set_inuse_bit_at_offset(remainder
, remainder_size
);
3468 chunk_free(ar_ptr
, remainder
);
3472 set_head_size(newp
, newsize
);
3473 set_inuse_bit_at_offset(newp
, newsize
);
3476 check_inuse_chunk(ar_ptr
, newp
);
3487 memalign requests more than enough space from malloc, finds a spot
3488 within that chunk that meets the alignment request, and then
3489 possibly frees the leading and trailing space.
3491 The alignment argument must be a power of two. This property is not
3492 checked by memalign, so misuse may result in random runtime errors.
3494 8-byte alignment is guaranteed by normal malloc calls, so don't
3495 bother calling memalign with an argument of 8 or less.
3497 Overreliance on memalign is a sure way to fragment space.
3503 Void_t
* mEMALIGn(size_t alignment
, size_t bytes
)
3505 Void_t
* mEMALIGn(alignment
, bytes
) size_t alignment
; size_t bytes
;
3509 INTERNAL_SIZE_T nb
; /* padded request size */
3512 #if defined _LIBC || defined MALLOC_HOOKS
3513 if (__memalign_hook
!= NULL
) {
3516 #if defined __GNUC__ && __GNUC__ >= 2
3517 result
= (*__memalign_hook
)(alignment
, bytes
, RETURN_ADDRESS (0));
3519 result
= (*__memalign_hook
)(alignment
, bytes
, NULL
);
3525 /* If need less alignment than we give anyway, just relay to malloc */
3527 if (alignment
<= MALLOC_ALIGNMENT
) return mALLOc(bytes
);
3529 /* Otherwise, ensure that it is at least a minimum chunk size */
3531 if (alignment
< MINSIZE
) alignment
= MINSIZE
;
3533 if(request2size(bytes
, nb
))
3535 arena_get(ar_ptr
, nb
+ alignment
+ MINSIZE
);
3538 p
= chunk_align(ar_ptr
, nb
, alignment
);
3539 (void)mutex_unlock(&ar_ptr
->mutex
);
3541 /* Maybe the failure is due to running out of mmapped areas. */
3542 if(ar_ptr
!= &main_arena
) {
3543 (void)mutex_lock(&main_arena
.mutex
);
3544 p
= chunk_align(&main_arena
, nb
, alignment
);
3545 (void)mutex_unlock(&main_arena
.mutex
);
3548 /* ... or sbrk() has failed and there is still a chance to mmap() */
3549 ar_ptr
= arena_get2(ar_ptr
->next
? ar_ptr
: 0, nb
);
3551 p
= chunk_align(ar_ptr
, nb
, alignment
);
3552 (void)mutex_unlock(&ar_ptr
->mutex
);
3558 return BOUNDED_N(chunk2mem(p
), bytes
);
3564 chunk_align(arena
* ar_ptr
, INTERNAL_SIZE_T nb
, size_t alignment
)
3566 chunk_align(ar_ptr
, nb
, alignment
)
3567 arena
* ar_ptr
; INTERNAL_SIZE_T nb
; size_t alignment
;
3570 unsigned long m
; /* memory returned by malloc call */
3571 mchunkptr p
; /* corresponding chunk */
3572 char* brk
; /* alignment point within p */
3573 mchunkptr newp
; /* chunk to return */
3574 INTERNAL_SIZE_T newsize
; /* its size */
3575 INTERNAL_SIZE_T leadsize
; /* leading space befor alignment point */
3576 mchunkptr remainder
; /* spare room at end to split off */
3577 long remainder_size
; /* its size */
3579 /* Call chunk_alloc with worst case padding to hit alignment. */
3580 p
= chunk_alloc(ar_ptr
, nb
+ alignment
+ MINSIZE
);
3582 return 0; /* propagate failure */
3584 m
= (unsigned long)chunk2mem(p
);
3586 if ((m
% alignment
) == 0) /* aligned */
3589 if(chunk_is_mmapped(p
)) {
3590 return p
; /* nothing more to do */
3594 else /* misaligned */
3597 Find an aligned spot inside chunk.
3598 Since we need to give back leading space in a chunk of at
3599 least MINSIZE, if the first calculation places us at
3600 a spot with less than MINSIZE leader, we can move to the
3601 next aligned spot -- we've allocated enough total room so that
3602 this is always possible.
3605 brk
= (char*)mem2chunk(((m
+ alignment
- 1)) & -(long)alignment
);
3606 if ((long)(brk
- (char*)(p
)) < (long)MINSIZE
) brk
+= alignment
;
3608 newp
= chunk_at_offset(brk
, 0);
3609 leadsize
= brk
- (char*)(p
);
3610 newsize
= chunksize(p
) - leadsize
;
3613 if(chunk_is_mmapped(p
))
3615 newp
->prev_size
= p
->prev_size
+ leadsize
;
3616 set_head(newp
, newsize
|IS_MMAPPED
);
3621 /* give back leader, use the rest */
3623 set_head(newp
, newsize
| PREV_INUSE
);
3624 set_inuse_bit_at_offset(newp
, newsize
);
3625 set_head_size(p
, leadsize
);
3626 chunk_free(ar_ptr
, p
);
3629 assert (newsize
>=nb
&& (((unsigned long)(chunk2mem(p
))) % alignment
) == 0);
3632 /* Also give back spare room at the end */
3634 remainder_size
= chunksize(p
) - nb
;
3636 if (remainder_size
>= (long)MINSIZE
)
3638 remainder
= chunk_at_offset(p
, nb
);
3639 set_head(remainder
, remainder_size
| PREV_INUSE
);
3640 set_head_size(p
, nb
);
3641 chunk_free(ar_ptr
, remainder
);
3644 check_inuse_chunk(ar_ptr
, p
);
3652 valloc just invokes memalign with alignment argument equal
3653 to the page size of the system (or as near to this as can
3654 be figured out from all the includes/defines above.)
3658 Void_t
* vALLOc(size_t bytes
)
3660 Void_t
* vALLOc(bytes
) size_t bytes
;
3663 if(__malloc_initialized
< 0)
3665 return mEMALIGn (malloc_getpagesize
, bytes
);
3669 pvalloc just invokes valloc for the nearest pagesize
3670 that will accommodate request
3675 Void_t
* pvALLOc(size_t bytes
)
3677 Void_t
* pvALLOc(bytes
) size_t bytes
;
3681 if(__malloc_initialized
< 0)
3683 pagesize
= malloc_getpagesize
;
3684 return mEMALIGn (pagesize
, (bytes
+ pagesize
- 1) & ~(pagesize
- 1));
3689 calloc calls chunk_alloc, then zeroes out the allocated chunk.
3694 Void_t
* cALLOc(size_t n
, size_t elem_size
)
3696 Void_t
* cALLOc(n
, elem_size
) size_t n
; size_t elem_size
;
3700 mchunkptr p
, oldtop
;
3701 INTERNAL_SIZE_T sz
, csz
, oldtopsize
;
3704 #if defined _LIBC || defined MALLOC_HOOKS
3705 if (__malloc_hook
!= NULL
) {
3707 #if defined __GNUC__ && __GNUC__ >= 2
3708 mem
= (*__malloc_hook
)(sz
, RETURN_ADDRESS (0));
3710 mem
= (*__malloc_hook
)(sz
, NULL
);
3715 return memset(mem
, 0, sz
);
3717 while(sz
> 0) ((char*)mem
)[--sz
] = 0; /* rather inefficient */
3723 if(request2size(n
* elem_size
, sz
))
3725 arena_get(ar_ptr
, sz
);
3729 /* Check if expand_top called, in which case there may be
3730 no need to clear. */
3732 oldtop
= top(ar_ptr
);
3733 oldtopsize
= chunksize(top(ar_ptr
));
3734 #if MORECORE_CLEARS < 2
3735 /* Only newly allocated memory is guaranteed to be cleared. */
3736 if (ar_ptr
== &main_arena
&&
3737 oldtopsize
< sbrk_base
+ max_sbrked_mem
- (char *)oldtop
)
3738 oldtopsize
= (sbrk_base
+ max_sbrked_mem
- (char *)oldtop
);
3741 p
= chunk_alloc (ar_ptr
, sz
);
3743 /* Only clearing follows, so we can unlock early. */
3744 (void)mutex_unlock(&ar_ptr
->mutex
);
3747 /* Maybe the failure is due to running out of mmapped areas. */
3748 if(ar_ptr
!= &main_arena
) {
3749 (void)mutex_lock(&main_arena
.mutex
);
3750 p
= chunk_alloc(&main_arena
, sz
);
3751 (void)mutex_unlock(&main_arena
.mutex
);
3754 /* ... or sbrk() has failed and there is still a chance to mmap() */
3755 (void)mutex_lock(&main_arena
.mutex
);
3756 ar_ptr
= arena_get2(ar_ptr
->next
? ar_ptr
: 0, sz
);
3757 (void)mutex_unlock(&main_arena
.mutex
);
3759 p
= chunk_alloc(ar_ptr
, sz
);
3760 (void)mutex_unlock(&ar_ptr
->mutex
);
3764 if (p
== 0) return 0;
3766 mem
= BOUNDED_N(chunk2mem(p
), n
* elem_size
);
3768 /* Two optional cases in which clearing not necessary */
3771 if (chunk_is_mmapped(p
)) return mem
;
3777 if (p
== oldtop
&& csz
> oldtopsize
) {
3778 /* clear only the bytes from non-freshly-sbrked memory */
3784 MALLOC_ZERO(BOUNDED_N(chunk2mem(p
), csz
), csz
);
3790 cfree just calls free. It is needed/defined on some systems
3791 that pair it with calloc, presumably for odd historical reasons.
3797 void cfree(Void_t
*mem
)
3799 void cfree(mem
) Void_t
*mem
;
3810 Malloc_trim gives memory back to the system (via negative
3811 arguments to sbrk) if there is unused memory at the `high' end of
3812 the malloc pool. You can call this after freeing large blocks of
3813 memory to potentially reduce the system-level memory requirements
3814 of a program. However, it cannot guarantee to reduce memory. Under
3815 some allocation patterns, some large free blocks of memory will be
3816 locked between two used chunks, so they cannot be given back to
3819 The `pad' argument to malloc_trim represents the amount of free
3820 trailing space to leave untrimmed. If this argument is zero,
3821 only the minimum amount of memory to maintain internal data
3822 structures will be left (one page or less). Non-zero arguments
3823 can be supplied to maintain enough trailing space to service
3824 future expected allocations without having to re-obtain memory
3827 Malloc_trim returns 1 if it actually released any memory, else 0.
3832 int mALLOC_TRIm(size_t pad
)
3834 int mALLOC_TRIm(pad
) size_t pad
;
3839 (void)mutex_lock(&main_arena
.mutex
);
3840 res
= main_trim(pad
);
3841 (void)mutex_unlock(&main_arena
.mutex
);
3845 /* Trim the main arena. */
3850 main_trim(size_t pad
)
3852 main_trim(pad
) size_t pad
;
3855 mchunkptr top_chunk
; /* The current top chunk */
3856 long top_size
; /* Amount of top-most memory */
3857 long extra
; /* Amount to release */
3858 char* current_brk
; /* address returned by pre-check sbrk call */
3859 char* new_brk
; /* address returned by negative sbrk call */
3861 unsigned long pagesz
= malloc_getpagesize
;
3863 top_chunk
= top(&main_arena
);
3864 top_size
= chunksize(top_chunk
);
3865 extra
= ((top_size
- pad
- MINSIZE
+ (pagesz
-1)) / pagesz
- 1) * pagesz
;
3867 if (extra
< (long)pagesz
) /* Not enough memory to release */
3870 /* Test to make sure no one else called sbrk */
3871 current_brk
= (char*)(MORECORE (0));
3872 if (current_brk
!= (char*)(top_chunk
) + top_size
)
3873 return 0; /* Apparently we don't own memory; must fail */
3875 new_brk
= (char*)(MORECORE (-extra
));
3877 #if defined _LIBC || defined MALLOC_HOOKS
3878 /* Call the `morecore' hook if necessary. */
3879 if (__after_morecore_hook
)
3880 (*__after_morecore_hook
) ();
3883 if (new_brk
== (char*)(MORECORE_FAILURE
)) { /* sbrk failed? */
3884 /* Try to figure out what we have */
3885 current_brk
= (char*)(MORECORE (0));
3886 top_size
= current_brk
- (char*)top_chunk
;
3887 if (top_size
>= (long)MINSIZE
) /* if not, we are very very dead! */
3889 sbrked_mem
= current_brk
- sbrk_base
;
3890 set_head(top_chunk
, top_size
| PREV_INUSE
);
3892 check_chunk(&main_arena
, top_chunk
);
3895 sbrked_mem
-= extra
;
3897 /* Success. Adjust top accordingly. */
3898 set_head(top_chunk
, (top_size
- extra
) | PREV_INUSE
);
3899 check_chunk(&main_arena
, top_chunk
);
3908 heap_trim(heap_info
*heap
, size_t pad
)
3910 heap_trim(heap
, pad
) heap_info
*heap
; size_t pad
;
3913 unsigned long pagesz
= malloc_getpagesize
;
3914 arena
*ar_ptr
= heap
->ar_ptr
;
3915 mchunkptr top_chunk
= top(ar_ptr
), p
, bck
, fwd
;
3916 heap_info
*prev_heap
;
3917 long new_size
, top_size
, extra
;
3919 /* Can this heap go away completely ? */
3920 while(top_chunk
== chunk_at_offset(heap
, sizeof(*heap
))) {
3921 prev_heap
= heap
->prev
;
3922 p
= chunk_at_offset(prev_heap
, prev_heap
->size
- (MINSIZE
-2*SIZE_SZ
));
3923 assert(p
->size
== (0|PREV_INUSE
)); /* must be fencepost */
3925 new_size
= chunksize(p
) + (MINSIZE
-2*SIZE_SZ
);
3926 assert(new_size
>0 && new_size
<(long)(2*MINSIZE
));
3928 new_size
+= p
->prev_size
;
3929 assert(new_size
>0 && new_size
<HEAP_MAX_SIZE
);
3930 if(new_size
+ (HEAP_MAX_SIZE
- prev_heap
->size
) < pad
+ MINSIZE
+ pagesz
)
3932 ar_ptr
->size
-= heap
->size
;
3933 arena_mem
-= heap
->size
;
3936 if(!prev_inuse(p
)) { /* consolidate backward */
3938 unlink(p
, bck
, fwd
);
3940 assert(((unsigned long)((char*)p
+ new_size
) & (pagesz
-1)) == 0);
3941 assert( ((char*)p
+ new_size
) == ((char*)heap
+ heap
->size
) );
3942 top(ar_ptr
) = top_chunk
= p
;
3943 set_head(top_chunk
, new_size
| PREV_INUSE
);
3944 check_chunk(ar_ptr
, top_chunk
);
3946 top_size
= chunksize(top_chunk
);
3947 extra
= ((top_size
- pad
- MINSIZE
+ (pagesz
-1))/pagesz
- 1) * pagesz
;
3948 if(extra
< (long)pagesz
)
3950 /* Try to shrink. */
3951 if(grow_heap(heap
, -extra
) != 0)
3953 ar_ptr
->size
-= extra
;
3956 /* Success. Adjust top accordingly. */
3957 set_head(top_chunk
, (top_size
- extra
) | PREV_INUSE
);
3958 check_chunk(ar_ptr
, top_chunk
);
3962 #endif /* USE_ARENAS */
3969 This routine tells you how many bytes you can actually use in an
3970 allocated chunk, which may be more than you requested (although
3971 often not). You can use this many bytes without worrying about
3972 overwriting other allocated objects. Not a particularly great
3973 programming practice, but still sometimes useful.
3978 size_t mALLOC_USABLE_SIZe(Void_t
* mem
)
3980 size_t mALLOC_USABLE_SIZe(mem
) Void_t
* mem
;
3990 if(!chunk_is_mmapped(p
))
3992 if (!inuse(p
)) return 0;
3993 check_inuse_chunk(arena_for_ptr(mem
), p
);
3994 return chunksize(p
) - SIZE_SZ
;
3996 return chunksize(p
) - 2*SIZE_SZ
;
4003 /* Utility to update mallinfo for malloc_stats() and mallinfo() */
4007 malloc_update_mallinfo(arena
*ar_ptr
, struct mallinfo
*mi
)
4009 malloc_update_mallinfo(ar_ptr
, mi
) arena
*ar_ptr
; struct mallinfo
*mi
;
4018 INTERNAL_SIZE_T avail
;
4020 (void)mutex_lock(&ar_ptr
->mutex
);
4021 avail
= chunksize(top(ar_ptr
));
4022 navail
= ((long)(avail
) >= (long)MINSIZE
)? 1 : 0;
4024 for (i
= 1; i
< NAV
; ++i
)
4026 b
= bin_at(ar_ptr
, i
);
4027 for (p
= last(b
); p
!= b
; p
= p
->bk
)
4030 check_free_chunk(ar_ptr
, p
);
4031 for (q
= next_chunk(p
);
4032 q
!= top(ar_ptr
) && inuse(q
) && (long)chunksize(q
) > 0;
4034 check_inuse_chunk(ar_ptr
, q
);
4036 avail
+= chunksize(p
);
4041 mi
->arena
= ar_ptr
->size
;
4042 mi
->ordblks
= navail
;
4043 mi
->smblks
= mi
->usmblks
= mi
->fsmblks
= 0; /* clear unused fields */
4044 mi
->uordblks
= ar_ptr
->size
- avail
;
4045 mi
->fordblks
= avail
;
4046 mi
->hblks
= n_mmaps
;
4047 mi
->hblkhd
= mmapped_mem
;
4048 mi
->keepcost
= chunksize(top(ar_ptr
));
4050 (void)mutex_unlock(&ar_ptr
->mutex
);
4053 #if USE_ARENAS && MALLOC_DEBUG > 1
4055 /* Print the complete contents of a single heap to stderr. */
4059 dump_heap(heap_info
*heap
)
4061 dump_heap(heap
) heap_info
*heap
;
4067 fprintf(stderr
, "Heap %p, size %10lx:\n", heap
, (long)heap
->size
);
4068 ptr
= (heap
->ar_ptr
!= (arena
*)(heap
+1)) ?
4069 (char*)(heap
+ 1) : (char*)(heap
+ 1) + sizeof(arena
);
4070 p
= (mchunkptr
)(((unsigned long)ptr
+ MALLOC_ALIGN_MASK
) &
4071 ~MALLOC_ALIGN_MASK
);
4073 fprintf(stderr
, "chunk %p size %10lx", p
, (long)p
->size
);
4074 if(p
== top(heap
->ar_ptr
)) {
4075 fprintf(stderr
, " (top)\n");
4077 } else if(p
->size
== (0|PREV_INUSE
)) {
4078 fprintf(stderr
, " (fence)\n");
4081 fprintf(stderr
, "\n");
4094 For all arenas separately and in total, prints on stderr the
4095 amount of space obtained from the system, and the current number
4096 of bytes allocated via malloc (or realloc, etc) but not yet
4097 freed. (Note that this is the number of bytes allocated, not the
4098 number requested. It will be larger than the number requested
4099 because of alignment and bookkeeping overhead.) When not compiled
4100 for multiple threads, the maximum amount of allocated memory
4101 (which may be more than current if malloc_trim and/or munmap got
4102 called) is also reported. When using mmap(), prints the maximum
4103 number of simultaneous mmap regions used, too.
4112 unsigned int in_use_b
= mmapped_mem
, system_b
= in_use_b
;
4114 long stat_lock_direct
= 0, stat_lock_loop
= 0, stat_lock_wait
= 0;
4117 for(i
=0, ar_ptr
= &main_arena
;; i
++) {
4118 malloc_update_mallinfo(ar_ptr
, &mi
);
4119 fprintf(stderr
, "Arena %d:\n", i
);
4120 fprintf(stderr
, "system bytes = %10u\n", (unsigned int)mi
.arena
);
4121 fprintf(stderr
, "in use bytes = %10u\n", (unsigned int)mi
.uordblks
);
4122 system_b
+= mi
.arena
;
4123 in_use_b
+= mi
.uordblks
;
4125 stat_lock_direct
+= ar_ptr
->stat_lock_direct
;
4126 stat_lock_loop
+= ar_ptr
->stat_lock_loop
;
4127 stat_lock_wait
+= ar_ptr
->stat_lock_wait
;
4129 #if USE_ARENAS && MALLOC_DEBUG > 1
4130 if(ar_ptr
!= &main_arena
) {
4132 (void)mutex_lock(&ar_ptr
->mutex
);
4133 heap
= heap_for_ptr(top(ar_ptr
));
4134 while(heap
) { dump_heap(heap
); heap
= heap
->prev
; }
4135 (void)mutex_unlock(&ar_ptr
->mutex
);
4138 ar_ptr
= ar_ptr
->next
;
4139 if(ar_ptr
== &main_arena
) break;
4142 fprintf(stderr
, "Total (incl. mmap):\n");
4144 fprintf(stderr
, "Total:\n");
4146 fprintf(stderr
, "system bytes = %10u\n", system_b
);
4147 fprintf(stderr
, "in use bytes = %10u\n", in_use_b
);
4149 fprintf(stderr
, "max system bytes = %10u\n", (unsigned int)max_total_mem
);
4152 fprintf(stderr
, "max mmap regions = %10u\n", (unsigned int)max_n_mmaps
);
4153 fprintf(stderr
, "max mmap bytes = %10lu\n", max_mmapped_mem
);
4156 fprintf(stderr
, "heaps created = %10d\n", stat_n_heaps
);
4157 fprintf(stderr
, "locked directly = %10ld\n", stat_lock_direct
);
4158 fprintf(stderr
, "locked in loop = %10ld\n", stat_lock_loop
);
4159 fprintf(stderr
, "locked waiting = %10ld\n", stat_lock_wait
);
4160 fprintf(stderr
, "locked total = %10ld\n",
4161 stat_lock_direct
+ stat_lock_loop
+ stat_lock_wait
);
4166 mallinfo returns a copy of updated current mallinfo.
4167 The information reported is for the arena last used by the thread.
4170 struct mallinfo
mALLINFo()
4173 Void_t
*vptr
= NULL
;
4176 tsd_getspecific(arena_key
, vptr
);
4177 if(vptr
== ATFORK_ARENA_PTR
)
4178 vptr
= (Void_t
*)&main_arena
;
4180 malloc_update_mallinfo((vptr
? (arena
*)vptr
: &main_arena
), &mi
);
4190 mallopt is the general SVID/XPG interface to tunable parameters.
4191 The format is to provide a (parameter-number, parameter-value) pair.
4192 mallopt then sets the corresponding parameter to the argument
4193 value if it can (i.e., so long as the value is meaningful),
4194 and returns 1 if successful else 0.
4196 See descriptions of tunable parameters above.
4201 int mALLOPt(int param_number
, int value
)
4203 int mALLOPt(param_number
, value
) int param_number
; int value
;
4206 switch(param_number
)
4208 case M_TRIM_THRESHOLD
:
4209 trim_threshold
= value
; return 1;
4211 top_pad
= value
; return 1;
4212 case M_MMAP_THRESHOLD
:
4214 /* Forbid setting the threshold too high. */
4215 if((unsigned long)value
> HEAP_MAX_SIZE
/2) return 0;
4217 mmap_threshold
= value
; return 1;
4220 n_mmaps_max
= value
; return 1;
4222 if (value
!= 0) return 0; else n_mmaps_max
= value
; return 1;
4224 case M_CHECK_ACTION
:
4225 check_action
= value
; return 1;
4234 /* Get/set state: malloc_get_state() records the current state of all
4235 malloc variables (_except_ for the actual heap contents and `hook'
4236 function pointers) in a system dependent, opaque data structure.
4237 This data structure is dynamically allocated and can be free()d
4238 after use. malloc_set_state() restores the state of all malloc
4239 variables to the previously obtained state. This is especially
4240 useful when using this malloc as part of a shared library, and when
4241 the heap contents are saved/restored via some other method. The
4242 primary example for this is GNU Emacs with its `dumping' procedure.
4243 `Hook' function pointers are never saved or restored by these
4244 functions, with two exceptions: If malloc checking was in use when
4245 malloc_get_state() was called, then malloc_set_state() calls
4246 __malloc_check_init() if possible; if malloc checking was not in
4247 use in the recorded state but the user requested malloc checking,
4248 then the hooks are reset to 0. */
4250 #define MALLOC_STATE_MAGIC 0x444c4541l
4251 #define MALLOC_STATE_VERSION (0*0x100l + 1l) /* major*0x100 + minor */
4253 struct malloc_state
{
4256 mbinptr av
[NAV
* 2 + 2];
4258 int sbrked_mem_bytes
;
4259 unsigned long trim_threshold
;
4260 unsigned long top_pad
;
4261 unsigned int n_mmaps_max
;
4262 unsigned long mmap_threshold
;
4264 unsigned long max_sbrked_mem
;
4265 unsigned long max_total_mem
;
4266 unsigned int n_mmaps
;
4267 unsigned int max_n_mmaps
;
4268 unsigned long mmapped_mem
;
4269 unsigned long max_mmapped_mem
;
4270 int using_malloc_checking
;
4276 struct malloc_state
* ms
;
4280 ms
= (struct malloc_state
*)mALLOc(sizeof(*ms
));
4283 (void)mutex_lock(&main_arena
.mutex
);
4284 ms
->magic
= MALLOC_STATE_MAGIC
;
4285 ms
->version
= MALLOC_STATE_VERSION
;
4286 ms
->av
[0] = main_arena
.av
[0];
4287 ms
->av
[1] = main_arena
.av
[1];
4288 for(i
=0; i
<NAV
; i
++) {
4289 b
= bin_at(&main_arena
, i
);
4291 ms
->av
[2*i
+2] = ms
->av
[2*i
+3] = 0; /* empty bin (or initial top) */
4293 ms
->av
[2*i
+2] = first(b
);
4294 ms
->av
[2*i
+3] = last(b
);
4297 ms
->sbrk_base
= sbrk_base
;
4298 ms
->sbrked_mem_bytes
= sbrked_mem
;
4299 ms
->trim_threshold
= trim_threshold
;
4300 ms
->top_pad
= top_pad
;
4301 ms
->n_mmaps_max
= n_mmaps_max
;
4302 ms
->mmap_threshold
= mmap_threshold
;
4303 ms
->check_action
= check_action
;
4304 ms
->max_sbrked_mem
= max_sbrked_mem
;
4306 ms
->max_total_mem
= max_total_mem
;
4308 ms
->max_total_mem
= 0;
4310 ms
->n_mmaps
= n_mmaps
;
4311 ms
->max_n_mmaps
= max_n_mmaps
;
4312 ms
->mmapped_mem
= mmapped_mem
;
4313 ms
->max_mmapped_mem
= max_mmapped_mem
;
4314 #if defined _LIBC || defined MALLOC_HOOKS
4315 ms
->using_malloc_checking
= using_malloc_checking
;
4317 ms
->using_malloc_checking
= 0;
4319 (void)mutex_unlock(&main_arena
.mutex
);
4325 mALLOC_SET_STATe(Void_t
* msptr
)
4327 mALLOC_SET_STATe(msptr
) Void_t
* msptr
;
4330 struct malloc_state
* ms
= (struct malloc_state
*)msptr
;
4334 #if defined _LIBC || defined MALLOC_HOOKS
4335 disallow_malloc_check
= 1;
4338 if(ms
->magic
!= MALLOC_STATE_MAGIC
) return -1;
4339 /* Must fail if the major version is too high. */
4340 if((ms
->version
& ~0xffl
) > (MALLOC_STATE_VERSION
& ~0xffl
)) return -2;
4341 (void)mutex_lock(&main_arena
.mutex
);
4342 main_arena
.av
[0] = ms
->av
[0];
4343 main_arena
.av
[1] = ms
->av
[1];
4344 for(i
=0; i
<NAV
; i
++) {
4345 b
= bin_at(&main_arena
, i
);
4346 if(ms
->av
[2*i
+2] == 0)
4347 first(b
) = last(b
) = b
;
4349 first(b
) = ms
->av
[2*i
+2];
4350 last(b
) = ms
->av
[2*i
+3];
4352 /* Make sure the links to the `av'-bins in the heap are correct. */
4358 sbrk_base
= ms
->sbrk_base
;
4359 sbrked_mem
= ms
->sbrked_mem_bytes
;
4360 trim_threshold
= ms
->trim_threshold
;
4361 top_pad
= ms
->top_pad
;
4362 n_mmaps_max
= ms
->n_mmaps_max
;
4363 mmap_threshold
= ms
->mmap_threshold
;
4364 check_action
= ms
->check_action
;
4365 max_sbrked_mem
= ms
->max_sbrked_mem
;
4367 max_total_mem
= ms
->max_total_mem
;
4369 n_mmaps
= ms
->n_mmaps
;
4370 max_n_mmaps
= ms
->max_n_mmaps
;
4371 mmapped_mem
= ms
->mmapped_mem
;
4372 max_mmapped_mem
= ms
->max_mmapped_mem
;
4373 /* add version-dependent code here */
4374 if (ms
->version
>= 1) {
4375 #if defined _LIBC || defined MALLOC_HOOKS
4376 /* Check whether it is safe to enable malloc checking, or whether
4377 it is necessary to disable it. */
4378 if (ms
->using_malloc_checking
&& !using_malloc_checking
&&
4379 !disallow_malloc_check
)
4380 __malloc_check_init ();
4381 else if (!ms
->using_malloc_checking
&& using_malloc_checking
) {
4385 __memalign_hook
= 0;
4386 using_malloc_checking
= 0;
4391 (void)mutex_unlock(&main_arena
.mutex
);
4397 #if defined _LIBC || defined MALLOC_HOOKS
4399 /* A simple, standard set of debugging hooks. Overhead is `only' one
4400 byte per chunk; still this will catch most cases of double frees or
4401 overruns. The goal here is to avoid obscure crashes due to invalid
4402 usage, unlike in the MALLOC_DEBUG code. */
4404 #define MAGICBYTE(p) ( ( ((size_t)p >> 3) ^ ((size_t)p >> 11)) & 0xFF )
4406 /* Instrument a chunk with overrun detector byte(s) and convert it
4407 into a user pointer with requested size sz. */
4412 chunk2mem_check(mchunkptr p
, size_t sz
)
4414 chunk2mem_check(p
, sz
) mchunkptr p
; size_t sz
;
4417 unsigned char* m_ptr
= (unsigned char*)BOUNDED_N(chunk2mem(p
), sz
);
4420 for(i
= chunksize(p
) - (chunk_is_mmapped(p
) ? 2*SIZE_SZ
+1 : SIZE_SZ
+1);
4424 m_ptr
[i
] = (unsigned char)(i
-sz
);
4429 m_ptr
[sz
] = MAGICBYTE(p
);
4430 return (Void_t
*)m_ptr
;
4433 /* Convert a pointer to be free()d or realloc()ed to a valid chunk
4434 pointer. If the provided pointer is not valid, return NULL. */
4439 mem2chunk_check(Void_t
* mem
)
4441 mem2chunk_check(mem
) Void_t
* mem
;
4445 INTERNAL_SIZE_T sz
, c
;
4446 unsigned char magic
;
4449 if(!aligned_OK(p
)) return NULL
;
4450 if( (char*)p
>=sbrk_base
&& (char*)p
<(sbrk_base
+sbrked_mem
) ) {
4451 /* Must be a chunk in conventional heap memory. */
4452 if(chunk_is_mmapped(p
) ||
4453 ( (sz
= chunksize(p
)), ((char*)p
+ sz
)>=(sbrk_base
+sbrked_mem
) ) ||
4454 sz
<MINSIZE
|| sz
&MALLOC_ALIGN_MASK
|| !inuse(p
) ||
4455 ( !prev_inuse(p
) && (p
->prev_size
&MALLOC_ALIGN_MASK
||
4456 (long)prev_chunk(p
)<(long)sbrk_base
||
4457 next_chunk(prev_chunk(p
))!=p
) ))
4459 magic
= MAGICBYTE(p
);
4460 for(sz
+= SIZE_SZ
-1; (c
= ((unsigned char*)p
)[sz
]) != magic
; sz
-= c
) {
4461 if(c
<=0 || sz
<(c
+2*SIZE_SZ
)) return NULL
;
4463 ((unsigned char*)p
)[sz
] ^= 0xFF;
4465 unsigned long offset
, page_mask
= malloc_getpagesize
-1;
4467 /* mmap()ed chunks have MALLOC_ALIGNMENT or higher power-of-two
4468 alignment relative to the beginning of a page. Check this
4470 offset
= (unsigned long)mem
& page_mask
;
4471 if((offset
!=MALLOC_ALIGNMENT
&& offset
!=0 && offset
!=0x10 &&
4472 offset
!=0x20 && offset
!=0x40 && offset
!=0x80 && offset
!=0x100 &&
4473 offset
!=0x200 && offset
!=0x400 && offset
!=0x800 && offset
!=0x1000 &&
4475 !chunk_is_mmapped(p
) || (p
->size
& PREV_INUSE
) ||
4476 ( (((unsigned long)p
- p
->prev_size
) & page_mask
) != 0 ) ||
4477 ( (sz
= chunksize(p
)), ((p
->prev_size
+ sz
) & page_mask
) != 0 ) )
4479 magic
= MAGICBYTE(p
);
4480 for(sz
-= 1; (c
= ((unsigned char*)p
)[sz
]) != magic
; sz
-= c
) {
4481 if(c
<=0 || sz
<(c
+2*SIZE_SZ
)) return NULL
;
4483 ((unsigned char*)p
)[sz
] ^= 0xFF;
4488 /* Check for corruption of the top chunk, and try to recover if
4499 mchunkptr t
= top(&main_arena
);
4500 char* brk
, * new_brk
;
4501 INTERNAL_SIZE_T front_misalign
, sbrk_size
;
4502 unsigned long pagesz
= malloc_getpagesize
;
4504 if((char*)t
+ chunksize(t
) == sbrk_base
+ sbrked_mem
||
4505 t
== initial_top(&main_arena
)) return 0;
4507 if(check_action
& 1)
4508 fprintf(stderr
, "malloc: top chunk is corrupt\n");
4509 if(check_action
& 2)
4512 /* Try to set up a new top chunk. */
4514 front_misalign
= (unsigned long)chunk2mem(brk
) & MALLOC_ALIGN_MASK
;
4515 if (front_misalign
> 0)
4516 front_misalign
= MALLOC_ALIGNMENT
- front_misalign
;
4517 sbrk_size
= front_misalign
+ top_pad
+ MINSIZE
;
4518 sbrk_size
+= pagesz
- ((unsigned long)(brk
+ sbrk_size
) & (pagesz
- 1));
4519 new_brk
= (char*)(MORECORE (sbrk_size
));
4520 if (new_brk
== (char*)(MORECORE_FAILURE
)) return -1;
4521 sbrked_mem
= (new_brk
- sbrk_base
) + sbrk_size
;
4523 top(&main_arena
) = (mchunkptr
)(brk
+ front_misalign
);
4524 set_head(top(&main_arena
), (sbrk_size
- front_misalign
) | PREV_INUSE
);
4531 malloc_check(size_t sz
, const Void_t
*caller
)
4533 malloc_check(sz
, caller
) size_t sz
; const Void_t
*caller
;
4539 if(request2size(sz
+1, nb
))
4541 (void)mutex_lock(&main_arena
.mutex
);
4542 victim
= (top_check() >= 0) ? chunk_alloc(&main_arena
, nb
) : NULL
;
4543 (void)mutex_unlock(&main_arena
.mutex
);
4544 if(!victim
) return NULL
;
4545 return chunk2mem_check(victim
, sz
);
4550 free_check(Void_t
* mem
, const Void_t
*caller
)
4552 free_check(mem
, caller
) Void_t
* mem
; const Void_t
*caller
;
4558 (void)mutex_lock(&main_arena
.mutex
);
4559 p
= mem2chunk_check(mem
);
4561 (void)mutex_unlock(&main_arena
.mutex
);
4562 if(check_action
& 1)
4563 fprintf(stderr
, "free(): invalid pointer %p!\n", mem
);
4564 if(check_action
& 2)
4569 if (chunk_is_mmapped(p
)) {
4570 (void)mutex_unlock(&main_arena
.mutex
);
4575 #if 0 /* Erase freed memory. */
4576 memset(mem
, 0, chunksize(p
) - (SIZE_SZ
+1));
4578 chunk_free(&main_arena
, p
);
4579 (void)mutex_unlock(&main_arena
.mutex
);
4584 realloc_check(Void_t
* oldmem
, size_t bytes
, const Void_t
*caller
)
4586 realloc_check(oldmem
, bytes
, caller
)
4587 Void_t
* oldmem
; size_t bytes
; const Void_t
*caller
;
4590 mchunkptr oldp
, newp
;
4591 INTERNAL_SIZE_T nb
, oldsize
;
4593 if (oldmem
== 0) return malloc_check(bytes
, NULL
);
4594 (void)mutex_lock(&main_arena
.mutex
);
4595 oldp
= mem2chunk_check(oldmem
);
4597 (void)mutex_unlock(&main_arena
.mutex
);
4598 if(check_action
& 1)
4599 fprintf(stderr
, "realloc(): invalid pointer %p!\n", oldmem
);
4600 if(check_action
& 2)
4602 return malloc_check(bytes
, NULL
);
4604 oldsize
= chunksize(oldp
);
4606 if(request2size(bytes
+1, nb
)) {
4607 (void)mutex_unlock(&main_arena
.mutex
);
4612 if (chunk_is_mmapped(oldp
)) {
4614 newp
= mremap_chunk(oldp
, nb
);
4617 /* Note the extra SIZE_SZ overhead. */
4618 if(oldsize
- SIZE_SZ
>= nb
) newp
= oldp
; /* do nothing */
4620 /* Must alloc, copy, free. */
4621 newp
= (top_check() >= 0) ? chunk_alloc(&main_arena
, nb
) : NULL
;
4623 MALLOC_COPY(BOUNDED_N(chunk2mem(newp
), nb
),
4624 oldmem
, oldsize
- 2*SIZE_SZ
, 0);
4632 #endif /* HAVE_MMAP */
4633 newp
= (top_check() >= 0) ?
4634 chunk_realloc(&main_arena
, oldp
, oldsize
, nb
) : NULL
;
4635 #if 0 /* Erase freed memory. */
4636 nb
= chunksize(newp
);
4637 if(oldp
<newp
|| oldp
>=chunk_at_offset(newp
, nb
)) {
4638 memset((char*)oldmem
+ 2*sizeof(mbinptr
), 0,
4639 oldsize
- (2*sizeof(mbinptr
)+2*SIZE_SZ
+1));
4640 } else if(nb
> oldsize
+SIZE_SZ
) {
4641 memset((char*)BOUNDED_N(chunk2mem(newp
), bytes
) + oldsize
,
4642 0, nb
- (oldsize
+SIZE_SZ
));
4648 (void)mutex_unlock(&main_arena
.mutex
);
4650 if(!newp
) return NULL
;
4651 return chunk2mem_check(newp
, bytes
);
4656 memalign_check(size_t alignment
, size_t bytes
, const Void_t
*caller
)
4658 memalign_check(alignment
, bytes
, caller
)
4659 size_t alignment
; size_t bytes
; const Void_t
*caller
;
4665 if (alignment
<= MALLOC_ALIGNMENT
) return malloc_check(bytes
, NULL
);
4666 if (alignment
< MINSIZE
) alignment
= MINSIZE
;
4668 if(request2size(bytes
+1, nb
))
4670 (void)mutex_lock(&main_arena
.mutex
);
4671 p
= (top_check() >= 0) ? chunk_align(&main_arena
, nb
, alignment
) : NULL
;
4672 (void)mutex_unlock(&main_arena
.mutex
);
4674 return chunk2mem_check(p
, bytes
);
4679 /* The following hooks are used when the global initialization in
4680 ptmalloc_init() hasn't completed yet. */
4684 malloc_starter(size_t sz
, const Void_t
*caller
)
4686 malloc_starter(sz
, caller
) size_t sz
; const Void_t
*caller
;
4692 if(request2size(sz
, nb
))
4694 victim
= chunk_alloc(&main_arena
, nb
);
4696 return victim
? BOUNDED_N(chunk2mem(victim
), sz
) : 0;
4701 free_starter(Void_t
* mem
, const Void_t
*caller
)
4703 free_starter(mem
, caller
) Void_t
* mem
; const Void_t
*caller
;
4711 if (chunk_is_mmapped(p
)) {
4716 chunk_free(&main_arena
, p
);
4719 /* The following hooks are used while the `atfork' handling mechanism
4724 malloc_atfork (size_t sz
, const Void_t
*caller
)
4726 malloc_atfork(sz
, caller
) size_t sz
; const Void_t
*caller
;
4729 Void_t
*vptr
= NULL
;
4733 tsd_getspecific(arena_key
, vptr
);
4734 if(vptr
== ATFORK_ARENA_PTR
) {
4735 /* We are the only thread that may allocate at all. */
4736 if(save_malloc_hook
!= malloc_check
) {
4737 if(request2size(sz
, nb
))
4739 victim
= chunk_alloc(&main_arena
, nb
);
4740 return victim
? BOUNDED_N(chunk2mem(victim
), sz
) : 0;
4742 if(top_check()<0 || request2size(sz
+1, nb
))
4744 victim
= chunk_alloc(&main_arena
, nb
);
4745 return victim
? chunk2mem_check(victim
, sz
) : 0;
4748 /* Suspend the thread until the `atfork' handlers have completed.
4749 By that time, the hooks will have been reset as well, so that
4750 mALLOc() can be used again. */
4751 (void)mutex_lock(&list_lock
);
4752 (void)mutex_unlock(&list_lock
);
4759 free_atfork(Void_t
* mem
, const Void_t
*caller
)
4761 free_atfork(mem
, caller
) Void_t
* mem
; const Void_t
*caller
;
4764 Void_t
*vptr
= NULL
;
4766 mchunkptr p
; /* chunk corresponding to mem */
4768 if (mem
== 0) /* free(0) has no effect */
4771 p
= mem2chunk(mem
); /* do not bother to replicate free_check here */
4774 if (chunk_is_mmapped(p
)) /* release mmapped memory. */
4781 ar_ptr
= arena_for_ptr(p
);
4782 tsd_getspecific(arena_key
, vptr
);
4783 if(vptr
!= ATFORK_ARENA_PTR
)
4784 (void)mutex_lock(&ar_ptr
->mutex
);
4785 chunk_free(ar_ptr
, p
);
4786 if(vptr
!= ATFORK_ARENA_PTR
)
4787 (void)mutex_unlock(&ar_ptr
->mutex
);
4790 #endif /* !defined NO_THREADS */
4792 #endif /* defined _LIBC || defined MALLOC_HOOKS */
4797 /* We need a wrapper function for one of the additions of POSIX. */
4799 __posix_memalign (void **memptr
, size_t alignment
, size_t size
)
4803 /* Test whether the SIZE argument is valid. It must be a power of
4804 two multiple of sizeof (void *). */
4805 if (size
% sizeof (void *) != 0 || (size
& (size
- 1)) != 0)
4808 mem
= __libc_memalign (alignment
, size
);
4818 weak_alias (__posix_memalign
, posix_memalign
)
4820 weak_alias (__libc_calloc
, __calloc
) weak_alias (__libc_calloc
, calloc
)
4821 weak_alias (__libc_free
, __cfree
) weak_alias (__libc_free
, cfree
)
4822 weak_alias (__libc_free
, __free
) weak_alias (__libc_free
, free
)
4823 weak_alias (__libc_malloc
, __malloc
) weak_alias (__libc_malloc
, malloc
)
4824 weak_alias (__libc_memalign
, __memalign
) weak_alias (__libc_memalign
, memalign
)
4825 weak_alias (__libc_realloc
, __realloc
) weak_alias (__libc_realloc
, realloc
)
4826 weak_alias (__libc_valloc
, __valloc
) weak_alias (__libc_valloc
, valloc
)
4827 weak_alias (__libc_pvalloc
, __pvalloc
) weak_alias (__libc_pvalloc
, pvalloc
)
4828 weak_alias (__libc_mallinfo
, __mallinfo
) weak_alias (__libc_mallinfo
, mallinfo
)
4829 weak_alias (__libc_mallopt
, __mallopt
) weak_alias (__libc_mallopt
, mallopt
)
4831 weak_alias (__malloc_stats
, malloc_stats
)
4832 weak_alias (__malloc_usable_size
, malloc_usable_size
)
4833 weak_alias (__malloc_trim
, malloc_trim
)
4834 weak_alias (__malloc_get_state
, malloc_get_state
)
4835 weak_alias (__malloc_set_state
, malloc_set_state
)
4842 V2.6.4-pt3 Thu Feb 20 1997 Wolfram Gloger (wmglo@dent.med.uni-muenchen.de)
4843 * Added malloc_get/set_state() (mainly for use in GNU emacs),
4844 using interface from Marcus Daniels
4845 * All parameters are now adjustable via environment variables
4847 V2.6.4-pt2 Sat Dec 14 1996 Wolfram Gloger (wmglo@dent.med.uni-muenchen.de)
4848 * Added debugging hooks
4849 * Fixed possible deadlock in realloc() when out of memory
4850 * Don't pollute namespace in glibc: use __getpagesize, __mmap, etc.
4852 V2.6.4-pt Wed Dec 4 1996 Wolfram Gloger (wmglo@dent.med.uni-muenchen.de)
4853 * Very minor updates from the released 2.6.4 version.
4854 * Trimmed include file down to exported data structures.
4855 * Changes from H.J. Lu for glibc-2.0.
4857 V2.6.3i-pt Sep 16 1996 Wolfram Gloger (wmglo@dent.med.uni-muenchen.de)
4858 * Many changes for multiple threads
4859 * Introduced arenas and heaps
4861 V2.6.3 Sun May 19 08:17:58 1996 Doug Lea (dl at gee)
4862 * Added pvalloc, as recommended by H.J. Liu
4863 * Added 64bit pointer support mainly from Wolfram Gloger
4864 * Added anonymously donated WIN32 sbrk emulation
4865 * Malloc, calloc, getpagesize: add optimizations from Raymond Nijssen
4866 * malloc_extend_top: fix mask error that caused wastage after
4868 * Add linux mremap support code from HJ Liu
4870 V2.6.2 Tue Dec 5 06:52:55 1995 Doug Lea (dl at gee)
4871 * Integrated most documentation with the code.
4872 * Add support for mmap, with help from
4873 Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
4874 * Use last_remainder in more cases.
4875 * Pack bins using idea from colin@nyx10.cs.du.edu
4876 * Use ordered bins instead of best-fit threshold
4877 * Eliminate block-local decls to simplify tracing and debugging.
4878 * Support another case of realloc via move into top
4879 * Fix error occurring when initial sbrk_base not word-aligned.
4880 * Rely on page size for units instead of SBRK_UNIT to
4881 avoid surprises about sbrk alignment conventions.
4882 * Add mallinfo, mallopt. Thanks to Raymond Nijssen
4883 (raymond@es.ele.tue.nl) for the suggestion.
4884 * Add `pad' argument to malloc_trim and top_pad mallopt parameter.
4885 * More precautions for cases where other routines call sbrk,
4886 courtesy of Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
4887 * Added macros etc., allowing use in linux libc from
4888 H.J. Lu (hjl@gnu.ai.mit.edu)
4889 * Inverted this history list
4891 V2.6.1 Sat Dec 2 14:10:57 1995 Doug Lea (dl at gee)
4892 * Re-tuned and fixed to behave more nicely with V2.6.0 changes.
4893 * Removed all preallocation code since under current scheme
4894 the work required to undo bad preallocations exceeds
4895 the work saved in good cases for most test programs.
4896 * No longer use return list or unconsolidated bins since
4897 no scheme using them consistently outperforms those that don't
4898 given above changes.
4899 * Use best fit for very large chunks to prevent some worst-cases.
4900 * Added some support for debugging
4902 V2.6.0 Sat Nov 4 07:05:23 1995 Doug Lea (dl at gee)
4903 * Removed footers when chunks are in use. Thanks to
4904 Paul Wilson (wilson@cs.texas.edu) for the suggestion.
4906 V2.5.4 Wed Nov 1 07:54:51 1995 Doug Lea (dl at gee)
4907 * Added malloc_trim, with help from Wolfram Gloger
4908 (wmglo@Dent.MED.Uni-Muenchen.DE).
4910 V2.5.3 Tue Apr 26 10:16:01 1994 Doug Lea (dl at g)
4912 V2.5.2 Tue Apr 5 16:20:40 1994 Doug Lea (dl at g)
4913 * realloc: try to expand in both directions
4914 * malloc: swap order of clean-bin strategy;
4915 * realloc: only conditionally expand backwards
4916 * Try not to scavenge used bins
4917 * Use bin counts as a guide to preallocation
4918 * Occasionally bin return list chunks in first scan
4919 * Add a few optimizations from colin@nyx10.cs.du.edu
4921 V2.5.1 Sat Aug 14 15:40:43 1993 Doug Lea (dl at g)
4922 * faster bin computation & slightly different binning
4923 * merged all consolidations to one part of malloc proper
4924 (eliminating old malloc_find_space & malloc_clean_bin)
4925 * Scan 2 returns chunks (not just 1)
4926 * Propagate failure in realloc if malloc returns 0
4927 * Add stuff to allow compilation on non-ANSI compilers
4928 from kpv@research.att.com
4930 V2.5 Sat Aug 7 07:41:59 1993 Doug Lea (dl at g.oswego.edu)
4931 * removed potential for odd address access in prev_chunk
4932 * removed dependency on getpagesize.h
4933 * misc cosmetics and a bit more internal documentation
4934 * anticosmetics: mangled names in macros to evade debugger strangeness
4935 * tested on sparc, hp-700, dec-mips, rs6000
4936 with gcc & native cc (hp, dec only) allowing
4937 Detlefs & Zorn comparison study (in SIGPLAN Notices.)
4939 Trial version Fri Aug 28 13:14:29 1992 Doug Lea (dl at g.oswego.edu)
4940 * Based loosely on libg++-1.2X malloc. (It retains some of the overall
4941 structure of old version, but most details differ.)