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 /* The following two functions are registered via thread_atfork() to
1599 make sure that the mutexes remain in a consistent state in the
1600 fork()ed version of a thread. Also adapt the malloc and free hooks
1601 temporarily, because the `atfork' handler mechanism may use
1602 malloc/free internally (e.g. in LinuxThreads). */
1604 #if defined _LIBC || defined MALLOC_HOOKS
1605 static __malloc_ptr_t (*save_malloc_hook
) __MALLOC_P ((size_t __size
,
1606 const __malloc_ptr_t
));
1607 static void (*save_free_hook
) __MALLOC_P ((__malloc_ptr_t __ptr
,
1608 const __malloc_ptr_t
));
1609 static Void_t
* save_arena
;
1613 ptmalloc_lock_all
__MALLOC_P((void))
1617 (void)mutex_lock(&list_lock
);
1618 for(ar_ptr
= &main_arena
;;) {
1619 (void)mutex_lock(&ar_ptr
->mutex
);
1620 ar_ptr
= ar_ptr
->next
;
1621 if(ar_ptr
== &main_arena
) break;
1623 #if defined _LIBC || defined MALLOC_HOOKS
1624 save_malloc_hook
= __malloc_hook
;
1625 save_free_hook
= __free_hook
;
1626 __malloc_hook
= malloc_atfork
;
1627 __free_hook
= free_atfork
;
1628 /* Only the current thread may perform malloc/free calls now. */
1629 tsd_getspecific(arena_key
, save_arena
);
1630 tsd_setspecific(arena_key
, (Void_t
*)0);
1635 ptmalloc_unlock_all
__MALLOC_P((void))
1639 #if defined _LIBC || defined MALLOC_HOOKS
1640 tsd_setspecific(arena_key
, save_arena
);
1641 __malloc_hook
= save_malloc_hook
;
1642 __free_hook
= save_free_hook
;
1644 for(ar_ptr
= &main_arena
;;) {
1645 (void)mutex_unlock(&ar_ptr
->mutex
);
1646 ar_ptr
= ar_ptr
->next
;
1647 if(ar_ptr
== &main_arena
) break;
1649 (void)mutex_unlock(&list_lock
);
1653 ptmalloc_init_all
__MALLOC_P((void))
1657 #if defined _LIBC || defined MALLOC_HOOKS
1658 tsd_setspecific(arena_key
, save_arena
);
1659 __malloc_hook
= save_malloc_hook
;
1660 __free_hook
= save_free_hook
;
1662 for(ar_ptr
= &main_arena
;;) {
1663 (void)mutex_init(&ar_ptr
->mutex
);
1664 ar_ptr
= ar_ptr
->next
;
1665 if(ar_ptr
== &main_arena
) break;
1667 (void)mutex_init(&list_lock
);
1670 #endif /* !defined NO_THREADS */
1672 /* Initialization routine. */
1675 static void ptmalloc_init
__MALLOC_P ((void)) __attribute__ ((constructor
));
1679 ptmalloc_init
__MALLOC_P((void))
1682 ptmalloc_init
__MALLOC_P((void))
1685 #if defined _LIBC || defined MALLOC_HOOKS
1694 if(__malloc_initialized
>= 0) return;
1695 __malloc_initialized
= 0;
1697 __libc_pagesize
= __getpagesize();
1700 #if defined _LIBC || defined MALLOC_HOOKS
1701 /* With some threads implementations, creating thread-specific data
1702 or initializing a mutex may call malloc() itself. Provide a
1703 simple starter version (realloc() won't work). */
1704 save_malloc_hook
= __malloc_hook
;
1705 save_free_hook
= __free_hook
;
1706 __malloc_hook
= malloc_starter
;
1707 __free_hook
= free_starter
;
1710 /* Initialize the pthreads interface. */
1711 if (__pthread_initialize
!= NULL
)
1712 __pthread_initialize();
1714 #endif /* !defined NO_THREADS */
1715 mutex_init(&main_arena
.mutex
);
1716 mutex_init(&list_lock
);
1717 tsd_key_create(&arena_key
, NULL
);
1718 tsd_setspecific(arena_key
, (Void_t
*)&main_arena
);
1719 thread_atfork(ptmalloc_lock_all
, ptmalloc_unlock_all
, ptmalloc_init_all
);
1720 #if defined _LIBC || defined MALLOC_HOOKS
1722 __malloc_hook
= save_malloc_hook
;
1723 __free_hook
= save_free_hook
;
1725 secure
= __libc_enable_secure
;
1728 if((s
= getenv("MALLOC_TRIM_THRESHOLD_")))
1729 mALLOPt(M_TRIM_THRESHOLD
, atoi(s
));
1730 if((s
= getenv("MALLOC_TOP_PAD_")))
1731 mALLOPt(M_TOP_PAD
, atoi(s
));
1732 if((s
= getenv("MALLOC_MMAP_THRESHOLD_")))
1733 mALLOPt(M_MMAP_THRESHOLD
, atoi(s
));
1734 if((s
= getenv("MALLOC_MMAP_MAX_")))
1735 mALLOPt(M_MMAP_MAX
, atoi(s
));
1737 s
= getenv("MALLOC_CHECK_");
1739 if(s
[0]) mALLOPt(M_CHECK_ACTION
, (int)(s
[0] - '0'));
1740 __malloc_check_init();
1742 if(__malloc_initialize_hook
!= NULL
)
1743 (*__malloc_initialize_hook
)();
1745 __malloc_initialized
= 1;
1748 /* There are platforms (e.g. Hurd) with a link-time hook mechanism. */
1749 #ifdef thread_atfork_static
1750 thread_atfork_static(ptmalloc_lock_all
, ptmalloc_unlock_all
, \
1754 #if defined _LIBC || defined MALLOC_HOOKS
1756 /* Hooks for debugging versions. The initial hooks just call the
1757 initialization routine, then do the normal work. */
1761 malloc_hook_ini(size_t sz
, const __malloc_ptr_t caller
)
1763 malloc_hook_ini(sz
, caller
)
1764 size_t sz
; const __malloc_ptr_t caller
;
1767 __malloc_hook
= NULL
;
1774 realloc_hook_ini(Void_t
* ptr
, size_t sz
, const __malloc_ptr_t caller
)
1776 realloc_hook_ini(ptr
, sz
, caller
)
1777 Void_t
* ptr
; size_t sz
; const __malloc_ptr_t caller
;
1780 __malloc_hook
= NULL
;
1781 __realloc_hook
= NULL
;
1783 return rEALLOc(ptr
, sz
);
1788 memalign_hook_ini(size_t alignment
, size_t sz
, const __malloc_ptr_t caller
)
1790 memalign_hook_ini(alignment
, sz
, caller
)
1791 size_t alignment
; size_t sz
; const __malloc_ptr_t caller
;
1794 __memalign_hook
= NULL
;
1796 return mEMALIGn(alignment
, sz
);
1799 void weak_variable (*__malloc_initialize_hook
) __MALLOC_P ((void)) = NULL
;
1800 void weak_variable (*__free_hook
) __MALLOC_P ((__malloc_ptr_t __ptr
,
1801 const __malloc_ptr_t
)) = NULL
;
1802 __malloc_ptr_t
weak_variable (*__malloc_hook
)
1803 __MALLOC_P ((size_t __size
, const __malloc_ptr_t
)) = malloc_hook_ini
;
1804 __malloc_ptr_t
weak_variable (*__realloc_hook
)
1805 __MALLOC_P ((__malloc_ptr_t __ptr
, size_t __size
, const __malloc_ptr_t
))
1807 __malloc_ptr_t
weak_variable (*__memalign_hook
)
1808 __MALLOC_P ((size_t __alignment
, size_t __size
, const __malloc_ptr_t
))
1809 = memalign_hook_ini
;
1810 void weak_variable (*__after_morecore_hook
) __MALLOC_P ((void)) = NULL
;
1812 /* Whether we are using malloc checking. */
1813 static int using_malloc_checking
;
1815 /* A flag that is set by malloc_set_state, to signal that malloc checking
1816 must not be enabled on the request from the user (via the MALLOC_CHECK_
1817 environment variable). It is reset by __malloc_check_init to tell
1818 malloc_set_state that the user has requested malloc checking.
1820 The purpose of this flag is to make sure that malloc checking is not
1821 enabled when the heap to be restored was constructed without malloc
1822 checking, and thus does not contain the required magic bytes.
1823 Otherwise the heap would be corrupted by calls to free and realloc. If
1824 it turns out that the heap was created with malloc checking and the
1825 user has requested it malloc_set_state just calls __malloc_check_init
1826 again to enable it. On the other hand, reusing such a heap without
1827 further malloc checking is safe. */
1828 static int disallow_malloc_check
;
1830 /* Activate a standard set of debugging hooks. */
1832 __malloc_check_init()
1834 if (disallow_malloc_check
) {
1835 disallow_malloc_check
= 0;
1838 using_malloc_checking
= 1;
1839 __malloc_hook
= malloc_check
;
1840 __free_hook
= free_check
;
1841 __realloc_hook
= realloc_check
;
1842 __memalign_hook
= memalign_check
;
1843 if(check_action
& 1)
1844 fprintf(stderr
, "malloc: using debugging hooks\n");
1853 /* Routines dealing with mmap(). */
1857 #ifndef MAP_ANONYMOUS
1859 static int dev_zero_fd
= -1; /* Cached file descriptor for /dev/zero. */
1861 #define MMAP(addr, size, prot, flags) ((dev_zero_fd < 0) ? \
1862 (dev_zero_fd = open("/dev/zero", O_RDWR), \
1863 mmap((addr), (size), (prot), (flags), dev_zero_fd, 0)) : \
1864 mmap((addr), (size), (prot), (flags), dev_zero_fd, 0))
1868 #define MMAP(addr, size, prot, flags) \
1869 (mmap((addr), (size), (prot), (flags)|MAP_ANONYMOUS, -1, 0))
1873 #if defined __GNUC__ && __GNUC__ >= 2
1874 /* This function is only called from one place, inline it. */
1880 mmap_chunk(size_t size
)
1882 mmap_chunk(size
) size_t size
;
1885 size_t page_mask
= malloc_getpagesize
- 1;
1888 /* For mmapped chunks, the overhead is one SIZE_SZ unit larger, because
1889 * there is no following chunk whose prev_size field could be used.
1891 size
= (size
+ SIZE_SZ
+ page_mask
) & ~page_mask
;
1893 p
= (mchunkptr
)MMAP(0, size
, PROT_READ
|PROT_WRITE
, MAP_PRIVATE
);
1894 if(p
== (mchunkptr
) MAP_FAILED
) return 0;
1897 if (n_mmaps
> max_n_mmaps
) max_n_mmaps
= n_mmaps
;
1899 /* We demand that eight bytes into a page must be 8-byte aligned. */
1900 assert(aligned_OK(chunk2mem(p
)));
1902 /* The offset to the start of the mmapped region is stored
1903 * in the prev_size field of the chunk; normally it is zero,
1904 * but that can be changed in memalign().
1907 set_head(p
, size
|IS_MMAPPED
);
1909 mmapped_mem
+= size
;
1910 if ((unsigned long)mmapped_mem
> (unsigned long)max_mmapped_mem
)
1911 max_mmapped_mem
= mmapped_mem
;
1913 if ((unsigned long)(mmapped_mem
+ arena_mem
+ sbrked_mem
) > max_total_mem
)
1914 max_total_mem
= mmapped_mem
+ arena_mem
+ sbrked_mem
;
1922 munmap_chunk(mchunkptr p
)
1924 munmap_chunk(p
) mchunkptr p
;
1927 INTERNAL_SIZE_T size
= chunksize(p
);
1930 assert (chunk_is_mmapped(p
));
1931 assert(! ((char*)p
>= sbrk_base
&& (char*)p
< sbrk_base
+ sbrked_mem
));
1932 assert((n_mmaps
> 0));
1933 assert(((p
->prev_size
+ size
) & (malloc_getpagesize
-1)) == 0);
1936 mmapped_mem
-= (size
+ p
->prev_size
);
1938 ret
= munmap((char *)p
- p
->prev_size
, size
+ p
->prev_size
);
1940 /* munmap returns non-zero on failure */
1949 mremap_chunk(mchunkptr p
, size_t new_size
)
1951 mremap_chunk(p
, new_size
) mchunkptr p
; size_t new_size
;
1954 size_t page_mask
= malloc_getpagesize
- 1;
1955 INTERNAL_SIZE_T offset
= p
->prev_size
;
1956 INTERNAL_SIZE_T size
= chunksize(p
);
1959 assert (chunk_is_mmapped(p
));
1960 assert(! ((char*)p
>= sbrk_base
&& (char*)p
< sbrk_base
+ sbrked_mem
));
1961 assert((n_mmaps
> 0));
1962 assert(((size
+ offset
) & (malloc_getpagesize
-1)) == 0);
1964 /* Note the extra SIZE_SZ overhead as in mmap_chunk(). */
1965 new_size
= (new_size
+ offset
+ SIZE_SZ
+ page_mask
) & ~page_mask
;
1967 cp
= (char *)mremap((char *)p
- offset
, size
+ offset
, new_size
,
1970 if (cp
== MAP_FAILED
) return 0;
1972 p
= (mchunkptr
)(cp
+ offset
);
1974 assert(aligned_OK(chunk2mem(p
)));
1976 assert((p
->prev_size
== offset
));
1977 set_head(p
, (new_size
- offset
)|IS_MMAPPED
);
1979 mmapped_mem
-= size
+ offset
;
1980 mmapped_mem
+= new_size
;
1981 if ((unsigned long)mmapped_mem
> (unsigned long)max_mmapped_mem
)
1982 max_mmapped_mem
= mmapped_mem
;
1984 if ((unsigned long)(mmapped_mem
+ arena_mem
+ sbrked_mem
) > max_total_mem
)
1985 max_total_mem
= mmapped_mem
+ arena_mem
+ sbrked_mem
;
1990 #endif /* HAVE_MREMAP */
1992 #endif /* HAVE_MMAP */
1996 /* Managing heaps and arenas (for concurrent threads) */
2000 /* Create a new heap. size is automatically rounded up to a multiple
2001 of the page size. */
2006 new_heap(size_t size
)
2008 new_heap(size
) size_t size
;
2011 size_t page_mask
= malloc_getpagesize
- 1;
2016 if(size
+top_pad
< HEAP_MIN_SIZE
)
2017 size
= HEAP_MIN_SIZE
;
2018 else if(size
+top_pad
<= HEAP_MAX_SIZE
)
2020 else if(size
> HEAP_MAX_SIZE
)
2023 size
= HEAP_MAX_SIZE
;
2024 size
= (size
+ page_mask
) & ~page_mask
;
2026 /* A memory region aligned to a multiple of HEAP_MAX_SIZE is needed.
2027 No swap space needs to be reserved for the following large
2028 mapping (on Linux, this is the case for all non-writable mappings
2030 p1
= (char *)MMAP(0, HEAP_MAX_SIZE
<<1, PROT_NONE
, MAP_PRIVATE
|MAP_NORESERVE
);
2031 if(p1
!= MAP_FAILED
) {
2032 p2
= (char *)(((unsigned long)p1
+ (HEAP_MAX_SIZE
-1)) & ~(HEAP_MAX_SIZE
-1));
2035 munmap(p2
+ HEAP_MAX_SIZE
, HEAP_MAX_SIZE
- ul
);
2037 /* Try to take the chance that an allocation of only HEAP_MAX_SIZE
2038 is already aligned. */
2039 p2
= (char *)MMAP(0, HEAP_MAX_SIZE
, PROT_NONE
, MAP_PRIVATE
|MAP_NORESERVE
);
2040 if(p2
== MAP_FAILED
)
2042 if((unsigned long)p2
& (HEAP_MAX_SIZE
-1)) {
2043 munmap(p2
, HEAP_MAX_SIZE
);
2047 if(mprotect(p2
, size
, PROT_READ
|PROT_WRITE
) != 0) {
2048 munmap(p2
, HEAP_MAX_SIZE
);
2051 h
= (heap_info
*)p2
;
2053 THREAD_STAT(stat_n_heaps
++);
2057 /* Grow or shrink a heap. size is automatically rounded up to a
2058 multiple of the page size if it is positive. */
2062 grow_heap(heap_info
*h
, long diff
)
2064 grow_heap(h
, diff
) heap_info
*h
; long diff
;
2067 size_t page_mask
= malloc_getpagesize
- 1;
2071 diff
= (diff
+ page_mask
) & ~page_mask
;
2072 new_size
= (long)h
->size
+ diff
;
2073 if(new_size
> HEAP_MAX_SIZE
)
2075 if(mprotect((char *)h
+ h
->size
, diff
, PROT_READ
|PROT_WRITE
) != 0)
2078 new_size
= (long)h
->size
+ diff
;
2079 if(new_size
< (long)sizeof(*h
))
2081 /* Try to re-map the extra heap space freshly to save memory, and
2082 make it inaccessible. */
2083 if((char *)MMAP((char *)h
+ new_size
, -diff
, PROT_NONE
,
2084 MAP_PRIVATE
|MAP_FIXED
) == (char *) MAP_FAILED
)
2091 /* Delete a heap. */
2093 #define delete_heap(heap) munmap((char*)(heap), HEAP_MAX_SIZE)
2095 /* arena_get() acquires an arena and locks the corresponding mutex.
2096 First, try the one last locked successfully by this thread. (This
2097 is the common case and handled with a macro for speed.) Then, loop
2098 once over the circularly linked list of arenas. If no arena is
2099 readily available, create a new one. In this latter case, `size'
2100 is just a hint as to how much memory will be required immediately
2101 in the new arena. */
2103 #define arena_get(ptr, size) do { \
2104 Void_t *vptr = NULL; \
2105 ptr = (arena *)tsd_getspecific(arena_key, vptr); \
2106 if(ptr && !mutex_trylock(&ptr->mutex)) { \
2107 THREAD_STAT(++(ptr->stat_lock_direct)); \
2109 ptr = arena_get2(ptr, (size)); \
2115 arena_get2(arena
*a_tsd
, size_t size
)
2117 arena_get2(a_tsd
, size
) arena
*a_tsd
; size_t size
;
2124 unsigned long misalign
;
2127 a
= a_tsd
= &main_arena
;
2131 /* This can only happen while initializing the new arena. */
2132 (void)mutex_lock(&main_arena
.mutex
);
2133 THREAD_STAT(++(main_arena
.stat_lock_wait
));
2138 /* Check the global, circularly linked list for available arenas. */
2141 if(!mutex_trylock(&a
->mutex
)) {
2142 THREAD_STAT(++(a
->stat_lock_loop
));
2143 tsd_setspecific(arena_key
, (Void_t
*)a
);
2147 } while(a
!= a_tsd
);
2149 /* If not even the list_lock can be obtained, try again. This can
2150 happen during `atfork', or for example on systems where thread
2151 creation makes it temporarily impossible to obtain _any_
2153 if(mutex_trylock(&list_lock
)) {
2157 (void)mutex_unlock(&list_lock
);
2159 /* Nothing immediately available, so generate a new arena. */
2160 h
= new_heap(size
+ (sizeof(*h
) + sizeof(*a
) + MALLOC_ALIGNMENT
));
2162 /* Maybe size is too large to fit in a single heap. So, just try
2163 to create a minimally-sized arena and let chunk_alloc() attempt
2164 to deal with the large request via mmap_chunk(). */
2165 h
= new_heap(sizeof(*h
) + sizeof(*a
) + MALLOC_ALIGNMENT
);
2169 a
= h
->ar_ptr
= (arena
*)(h
+1);
2170 for(i
=0; i
<NAV
; i
++)
2174 arena_mem
+= h
->size
;
2176 if((unsigned long)(mmapped_mem
+ arena_mem
+ sbrked_mem
) > max_total_mem
)
2177 max_total_mem
= mmapped_mem
+ arena_mem
+ sbrked_mem
;
2179 tsd_setspecific(arena_key
, (Void_t
*)a
);
2180 mutex_init(&a
->mutex
);
2181 i
= mutex_lock(&a
->mutex
); /* remember result */
2183 /* Set up the top chunk, with proper alignment. */
2184 ptr
= (char *)(a
+ 1);
2185 misalign
= (unsigned long)chunk2mem(ptr
) & MALLOC_ALIGN_MASK
;
2187 ptr
+= MALLOC_ALIGNMENT
- misalign
;
2188 top(a
) = (mchunkptr
)ptr
;
2189 set_head(top(a
), (((char*)h
+ h
->size
) - ptr
) | PREV_INUSE
);
2191 /* Add the new arena to the list. */
2192 (void)mutex_lock(&list_lock
);
2193 a
->next
= main_arena
.next
;
2194 main_arena
.next
= a
;
2195 (void)mutex_unlock(&list_lock
);
2197 if(i
) /* locking failed; keep arena for further attempts later */
2200 THREAD_STAT(++(a
->stat_lock_loop
));
2204 /* find the heap and corresponding arena for a given ptr */
2206 #define heap_for_ptr(ptr) \
2207 ((heap_info *)((unsigned long)(ptr) & ~(HEAP_MAX_SIZE-1)))
2208 #define arena_for_ptr(ptr) \
2209 (((mchunkptr)(ptr) < top(&main_arena) && (char *)(ptr) >= sbrk_base) ? \
2210 &main_arena : heap_for_ptr(ptr)->ar_ptr)
2212 #else /* !USE_ARENAS */
2214 /* There is only one arena, main_arena. */
2216 #define arena_get(ptr, sz) (ptr = &main_arena)
2217 #define arena_for_ptr(ptr) (&main_arena)
2219 #endif /* USE_ARENAS */
2231 These routines make a number of assertions about the states
2232 of data structures that should be true at all times. If any
2233 are not true, it's very likely that a user program has somehow
2234 trashed memory. (It's also possible that there is a coding error
2235 in malloc. In which case, please report it!)
2239 static void do_check_chunk(arena
*ar_ptr
, mchunkptr p
)
2241 static void do_check_chunk(ar_ptr
, p
) arena
*ar_ptr
; mchunkptr p
;
2244 INTERNAL_SIZE_T sz
= p
->size
& ~PREV_INUSE
;
2246 /* No checkable chunk is mmapped */
2247 assert(!chunk_is_mmapped(p
));
2250 if(ar_ptr
!= &main_arena
) {
2251 heap_info
*heap
= heap_for_ptr(p
);
2252 assert(heap
->ar_ptr
== ar_ptr
);
2253 if(p
!= top(ar_ptr
))
2254 assert((char *)p
+ sz
<= (char *)heap
+ heap
->size
);
2256 assert((char *)p
+ sz
== (char *)heap
+ heap
->size
);
2261 /* Check for legal address ... */
2262 assert((char*)p
>= sbrk_base
);
2263 if (p
!= top(ar_ptr
))
2264 assert((char*)p
+ sz
<= (char*)top(ar_ptr
));
2266 assert((char*)p
+ sz
<= sbrk_base
+ sbrked_mem
);
2272 static void do_check_free_chunk(arena
*ar_ptr
, mchunkptr p
)
2274 static void do_check_free_chunk(ar_ptr
, p
) arena
*ar_ptr
; mchunkptr p
;
2277 INTERNAL_SIZE_T sz
= p
->size
& ~PREV_INUSE
;
2278 mchunkptr next
= chunk_at_offset(p
, sz
);
2280 do_check_chunk(ar_ptr
, p
);
2282 /* Check whether it claims to be free ... */
2285 /* Must have OK size and fields */
2286 assert((long)sz
>= (long)MINSIZE
);
2287 assert((sz
& MALLOC_ALIGN_MASK
) == 0);
2288 assert(aligned_OK(chunk2mem(p
)));
2289 /* ... matching footer field */
2290 assert(next
->prev_size
== sz
);
2291 /* ... and is fully consolidated */
2292 assert(prev_inuse(p
));
2293 assert (next
== top(ar_ptr
) || inuse(next
));
2295 /* ... and has minimally sane links */
2296 assert(p
->fd
->bk
== p
);
2297 assert(p
->bk
->fd
== p
);
2301 static void do_check_inuse_chunk(arena
*ar_ptr
, mchunkptr p
)
2303 static void do_check_inuse_chunk(ar_ptr
, p
) arena
*ar_ptr
; mchunkptr p
;
2306 mchunkptr next
= next_chunk(p
);
2307 do_check_chunk(ar_ptr
, p
);
2309 /* Check whether it claims to be in use ... */
2312 /* ... whether its size is OK (it might be a fencepost) ... */
2313 assert(chunksize(p
) >= MINSIZE
|| next
->size
== (0|PREV_INUSE
));
2315 /* ... and is surrounded by OK chunks.
2316 Since more things can be checked with free chunks than inuse ones,
2317 if an inuse chunk borders them and debug is on, it's worth doing them.
2321 mchunkptr prv
= prev_chunk(p
);
2322 assert(next_chunk(prv
) == p
);
2323 do_check_free_chunk(ar_ptr
, prv
);
2325 if (next
== top(ar_ptr
))
2327 assert(prev_inuse(next
));
2328 assert(chunksize(next
) >= MINSIZE
);
2330 else if (!inuse(next
))
2331 do_check_free_chunk(ar_ptr
, next
);
2336 static void do_check_malloced_chunk(arena
*ar_ptr
,
2337 mchunkptr p
, INTERNAL_SIZE_T s
)
2339 static void do_check_malloced_chunk(ar_ptr
, p
, s
)
2340 arena
*ar_ptr
; mchunkptr p
; INTERNAL_SIZE_T s
;
2343 INTERNAL_SIZE_T sz
= p
->size
& ~PREV_INUSE
;
2346 do_check_inuse_chunk(ar_ptr
, p
);
2348 /* Legal size ... */
2349 assert((long)sz
>= (long)MINSIZE
);
2350 assert((sz
& MALLOC_ALIGN_MASK
) == 0);
2352 assert(room
< (long)MINSIZE
);
2354 /* ... and alignment */
2355 assert(aligned_OK(chunk2mem(p
)));
2358 /* ... and was allocated at front of an available chunk */
2359 assert(prev_inuse(p
));
2364 #define check_free_chunk(A,P) do_check_free_chunk(A,P)
2365 #define check_inuse_chunk(A,P) do_check_inuse_chunk(A,P)
2366 #define check_chunk(A,P) do_check_chunk(A,P)
2367 #define check_malloced_chunk(A,P,N) do_check_malloced_chunk(A,P,N)
2369 #define check_free_chunk(A,P)
2370 #define check_inuse_chunk(A,P)
2371 #define check_chunk(A,P)
2372 #define check_malloced_chunk(A,P,N)
2378 Macro-based internal utilities
2383 Linking chunks in bin lists.
2384 Call these only with variables, not arbitrary expressions, as arguments.
2388 Place chunk p of size s in its bin, in size order,
2389 putting it ahead of others of same size.
2393 #define frontlink(A, P, S, IDX, BK, FD) \
2395 if (S < MAX_SMALLBIN_SIZE) \
2397 IDX = smallbin_index(S); \
2398 mark_binblock(A, IDX); \
2399 BK = bin_at(A, IDX); \
2403 FD->bk = BK->fd = P; \
2407 IDX = bin_index(S); \
2408 BK = bin_at(A, IDX); \
2410 if (FD == BK) mark_binblock(A, IDX); \
2413 while (FD != BK && S < chunksize(FD)) FD = FD->fd; \
2418 FD->bk = BK->fd = P; \
2423 /* take a chunk off a list */
2425 #define unlink(P, BK, FD) \
2433 /* Place p as the last remainder */
2435 #define link_last_remainder(A, P) \
2437 last_remainder(A)->fd = last_remainder(A)->bk = P; \
2438 P->fd = P->bk = last_remainder(A); \
2441 /* Clear the last_remainder bin */
2443 #define clear_last_remainder(A) \
2444 (last_remainder(A)->fd = last_remainder(A)->bk = last_remainder(A))
2451 Extend the top-most chunk by obtaining memory from system.
2452 Main interface to sbrk (but see also malloc_trim).
2455 #if defined __GNUC__ && __GNUC__ >= 2
2456 /* This function is called only from one place, inline it. */
2462 malloc_extend_top(arena
*ar_ptr
, INTERNAL_SIZE_T nb
)
2464 malloc_extend_top(ar_ptr
, nb
) arena
*ar_ptr
; INTERNAL_SIZE_T nb
;
2467 unsigned long pagesz
= malloc_getpagesize
;
2468 mchunkptr old_top
= top(ar_ptr
); /* Record state of old top */
2469 INTERNAL_SIZE_T old_top_size
= chunksize(old_top
);
2470 INTERNAL_SIZE_T top_size
; /* new size of top chunk */
2473 if(ar_ptr
== &main_arena
) {
2476 char* brk
; /* return value from sbrk */
2477 INTERNAL_SIZE_T front_misalign
; /* unusable bytes at front of sbrked space */
2478 INTERNAL_SIZE_T correction
; /* bytes for 2nd sbrk call */
2479 char* new_brk
; /* return of 2nd sbrk call */
2480 char* old_end
= (char*)(chunk_at_offset(old_top
, old_top_size
));
2482 /* Pad request with top_pad plus minimal overhead */
2483 INTERNAL_SIZE_T sbrk_size
= nb
+ top_pad
+ MINSIZE
;
2485 /* If not the first time through, round to preserve page boundary */
2486 /* Otherwise, we need to correct to a page size below anyway. */
2487 /* (We also correct below if an intervening foreign sbrk call.) */
2489 if (sbrk_base
!= (char*)(-1))
2490 sbrk_size
= (sbrk_size
+ (pagesz
- 1)) & ~(pagesz
- 1);
2492 brk
= (char*)(MORECORE (sbrk_size
));
2494 /* Fail if sbrk failed or if a foreign sbrk call killed our space */
2495 if (brk
== (char*)(MORECORE_FAILURE
) ||
2496 (brk
< old_end
&& old_top
!= initial_top(&main_arena
)))
2499 #if defined _LIBC || defined MALLOC_HOOKS
2500 /* Call the `morecore' hook if necessary. */
2501 if (__after_morecore_hook
)
2502 (*__after_morecore_hook
) ();
2505 sbrked_mem
+= sbrk_size
;
2507 if (brk
== old_end
) { /* can just add bytes to current top */
2508 top_size
= sbrk_size
+ old_top_size
;
2509 set_head(old_top
, top_size
| PREV_INUSE
);
2510 old_top
= 0; /* don't free below */
2512 if (sbrk_base
== (char*)(-1)) /* First time through. Record base */
2515 /* Someone else called sbrk(). Count those bytes as sbrked_mem. */
2516 sbrked_mem
+= brk
- (char*)old_end
;
2518 /* Guarantee alignment of first new chunk made from this space */
2519 front_misalign
= (unsigned long)chunk2mem(brk
) & MALLOC_ALIGN_MASK
;
2520 if (front_misalign
> 0) {
2521 correction
= (MALLOC_ALIGNMENT
) - front_misalign
;
2526 /* Guarantee the next brk will be at a page boundary */
2527 correction
+= pagesz
- ((unsigned long)(brk
+ sbrk_size
) & (pagesz
- 1));
2529 /* Allocate correction */
2530 new_brk
= (char*)(MORECORE (correction
));
2531 if (new_brk
== (char*)(MORECORE_FAILURE
)) return;
2533 #if defined _LIBC || defined MALLOC_HOOKS
2534 /* Call the `morecore' hook if necessary. */
2535 if (__after_morecore_hook
)
2536 (*__after_morecore_hook
) ();
2539 sbrked_mem
+= correction
;
2541 top(&main_arena
) = chunk_at_offset(brk
, 0);
2542 top_size
= new_brk
- brk
+ correction
;
2543 set_head(top(&main_arena
), top_size
| PREV_INUSE
);
2545 if (old_top
== initial_top(&main_arena
))
2546 old_top
= 0; /* don't free below */
2549 if ((unsigned long)sbrked_mem
> (unsigned long)max_sbrked_mem
)
2550 max_sbrked_mem
= sbrked_mem
;
2552 if ((unsigned long)(mmapped_mem
+ arena_mem
+ sbrked_mem
) > max_total_mem
)
2553 max_total_mem
= mmapped_mem
+ arena_mem
+ sbrked_mem
;
2557 } else { /* ar_ptr != &main_arena */
2558 heap_info
*old_heap
, *heap
;
2559 size_t old_heap_size
;
2561 if(old_top_size
< MINSIZE
) /* this should never happen */
2564 /* First try to extend the current heap. */
2565 if(MINSIZE
+ nb
<= old_top_size
)
2567 old_heap
= heap_for_ptr(old_top
);
2568 old_heap_size
= old_heap
->size
;
2569 if(grow_heap(old_heap
, MINSIZE
+ nb
- old_top_size
) == 0) {
2570 ar_ptr
->size
+= old_heap
->size
- old_heap_size
;
2571 arena_mem
+= old_heap
->size
- old_heap_size
;
2573 if(mmapped_mem
+ arena_mem
+ sbrked_mem
> max_total_mem
)
2574 max_total_mem
= mmapped_mem
+ arena_mem
+ sbrked_mem
;
2576 top_size
= ((char *)old_heap
+ old_heap
->size
) - (char *)old_top
;
2577 set_head(old_top
, top_size
| PREV_INUSE
);
2581 /* A new heap must be created. */
2582 heap
= new_heap(nb
+ (MINSIZE
+ sizeof(*heap
)));
2585 heap
->ar_ptr
= ar_ptr
;
2586 heap
->prev
= old_heap
;
2587 ar_ptr
->size
+= heap
->size
;
2588 arena_mem
+= heap
->size
;
2590 if((unsigned long)(mmapped_mem
+ arena_mem
+ sbrked_mem
) > max_total_mem
)
2591 max_total_mem
= mmapped_mem
+ arena_mem
+ sbrked_mem
;
2594 /* Set up the new top, so we can safely use chunk_free() below. */
2595 top(ar_ptr
) = chunk_at_offset(heap
, sizeof(*heap
));
2596 top_size
= heap
->size
- sizeof(*heap
);
2597 set_head(top(ar_ptr
), top_size
| PREV_INUSE
);
2599 #endif /* USE_ARENAS */
2601 /* We always land on a page boundary */
2602 assert(((unsigned long)((char*)top(ar_ptr
) + top_size
) & (pagesz
-1)) == 0);
2604 /* Setup fencepost and free the old top chunk. */
2606 /* The fencepost takes at least MINSIZE bytes, because it might
2607 become the top chunk again later. Note that a footer is set
2608 up, too, although the chunk is marked in use. */
2609 old_top_size
-= MINSIZE
;
2610 set_head(chunk_at_offset(old_top
, old_top_size
+ 2*SIZE_SZ
), 0|PREV_INUSE
);
2611 if(old_top_size
>= MINSIZE
) {
2612 set_head(chunk_at_offset(old_top
, old_top_size
), (2*SIZE_SZ
)|PREV_INUSE
);
2613 set_foot(chunk_at_offset(old_top
, old_top_size
), (2*SIZE_SZ
));
2614 set_head_size(old_top
, old_top_size
);
2615 chunk_free(ar_ptr
, old_top
);
2617 set_head(old_top
, (old_top_size
+ 2*SIZE_SZ
)|PREV_INUSE
);
2618 set_foot(old_top
, (old_top_size
+ 2*SIZE_SZ
));
2626 /* Main public routines */
2632 The requested size is first converted into a usable form, `nb'.
2633 This currently means to add 4 bytes overhead plus possibly more to
2634 obtain 8-byte alignment and/or to obtain a size of at least
2635 MINSIZE (currently 16, 24, or 32 bytes), the smallest allocatable
2636 size. (All fits are considered `exact' if they are within MINSIZE
2639 From there, the first successful of the following steps is taken:
2641 1. The bin corresponding to the request size is scanned, and if
2642 a chunk of exactly the right size is found, it is taken.
2644 2. The most recently remaindered chunk is used if it is big
2645 enough. This is a form of (roving) first fit, used only in
2646 the absence of exact fits. Runs of consecutive requests use
2647 the remainder of the chunk used for the previous such request
2648 whenever possible. This limited use of a first-fit style
2649 allocation strategy tends to give contiguous chunks
2650 coextensive lifetimes, which improves locality and can reduce
2651 fragmentation in the long run.
2653 3. Other bins are scanned in increasing size order, using a
2654 chunk big enough to fulfill the request, and splitting off
2655 any remainder. This search is strictly by best-fit; i.e.,
2656 the smallest (with ties going to approximately the least
2657 recently used) chunk that fits is selected.
2659 4. If large enough, the chunk bordering the end of memory
2660 (`top') is split off. (This use of `top' is in accord with
2661 the best-fit search rule. In effect, `top' is treated as
2662 larger (and thus less well fitting) than any other available
2663 chunk since it can be extended to be as large as necessary
2664 (up to system limitations).
2666 5. If the request size meets the mmap threshold and the
2667 system supports mmap, and there are few enough currently
2668 allocated mmapped regions, and a call to mmap succeeds,
2669 the request is allocated via direct memory mapping.
2671 6. Otherwise, the top of memory is extended by
2672 obtaining more space from the system (normally using sbrk,
2673 but definable to anything else via the MORECORE macro).
2674 Memory is gathered from the system (in system page-sized
2675 units) in a way that allows chunks obtained across different
2676 sbrk calls to be consolidated, but does not require
2677 contiguous memory. Thus, it should be safe to intersperse
2678 mallocs with other sbrk calls.
2681 All allocations are made from the `lowest' part of any found
2682 chunk. (The implementation invariant is that prev_inuse is
2683 always true of any allocated chunk; i.e., that each allocated
2684 chunk borders either a previously allocated and still in-use chunk,
2685 or the base of its memory arena.)
2690 Void_t
* mALLOc(size_t bytes
)
2692 Void_t
* mALLOc(bytes
) size_t bytes
;
2696 INTERNAL_SIZE_T nb
; /* padded request size */
2699 #if defined _LIBC || defined MALLOC_HOOKS
2700 if (__malloc_hook
!= NULL
) {
2703 #if defined __GNUC__ && __GNUC__ >= 2
2704 result
= (*__malloc_hook
)(bytes
, RETURN_ADDRESS (0));
2706 result
= (*__malloc_hook
)(bytes
, NULL
);
2712 if(request2size(bytes
, nb
))
2714 arena_get(ar_ptr
, nb
);
2717 victim
= chunk_alloc(ar_ptr
, nb
);
2719 /* Maybe the failure is due to running out of mmapped areas. */
2720 if(ar_ptr
!= &main_arena
) {
2721 (void)mutex_unlock(&ar_ptr
->mutex
);
2722 (void)mutex_lock(&main_arena
.mutex
);
2723 victim
= chunk_alloc(&main_arena
, nb
);
2724 (void)mutex_unlock(&main_arena
.mutex
);
2727 /* ... or sbrk() has failed and there is still a chance to mmap() */
2728 ar_ptr
= arena_get2(ar_ptr
->next
? ar_ptr
: 0, nb
);
2729 (void)mutex_unlock(&main_arena
.mutex
);
2731 victim
= chunk_alloc(ar_ptr
, nb
);
2732 (void)mutex_unlock(&ar_ptr
->mutex
);
2736 if(!victim
) return 0;
2738 (void)mutex_unlock(&ar_ptr
->mutex
);
2739 return BOUNDED_N(chunk2mem(victim
), bytes
);
2745 chunk_alloc(arena
*ar_ptr
, INTERNAL_SIZE_T nb
)
2747 chunk_alloc(ar_ptr
, nb
) arena
*ar_ptr
; INTERNAL_SIZE_T nb
;
2750 mchunkptr victim
; /* inspected/selected chunk */
2751 INTERNAL_SIZE_T victim_size
; /* its size */
2752 int idx
; /* index for bin traversal */
2753 mbinptr bin
; /* associated bin */
2754 mchunkptr remainder
; /* remainder from a split */
2755 long remainder_size
; /* its size */
2756 int remainder_index
; /* its bin index */
2757 unsigned long block
; /* block traverser bit */
2758 int startidx
; /* first bin of a traversed block */
2759 mchunkptr fwd
; /* misc temp for linking */
2760 mchunkptr bck
; /* misc temp for linking */
2761 mbinptr q
; /* misc temp */
2764 /* Check for exact match in a bin */
2766 if (is_small_request(nb
)) /* Faster version for small requests */
2768 idx
= smallbin_index(nb
);
2770 /* No traversal or size check necessary for small bins. */
2772 q
= _bin_at(ar_ptr
, idx
);
2775 /* Also scan the next one, since it would have a remainder < MINSIZE */
2783 victim_size
= chunksize(victim
);
2784 unlink(victim
, bck
, fwd
);
2785 set_inuse_bit_at_offset(victim
, victim_size
);
2786 check_malloced_chunk(ar_ptr
, victim
, nb
);
2790 idx
+= 2; /* Set for bin scan below. We've already scanned 2 bins. */
2795 idx
= bin_index(nb
);
2796 bin
= bin_at(ar_ptr
, idx
);
2798 for (victim
= last(bin
); victim
!= bin
; victim
= victim
->bk
)
2800 victim_size
= chunksize(victim
);
2801 remainder_size
= victim_size
- nb
;
2803 if (remainder_size
>= (long)MINSIZE
) /* too big */
2805 --idx
; /* adjust to rescan below after checking last remainder */
2809 else if (remainder_size
>= 0) /* exact fit */
2811 unlink(victim
, bck
, fwd
);
2812 set_inuse_bit_at_offset(victim
, victim_size
);
2813 check_malloced_chunk(ar_ptr
, victim
, nb
);
2822 /* Try to use the last split-off remainder */
2824 if ( (victim
= last_remainder(ar_ptr
)->fd
) != last_remainder(ar_ptr
))
2826 victim_size
= chunksize(victim
);
2827 remainder_size
= victim_size
- nb
;
2829 if (remainder_size
>= (long)MINSIZE
) /* re-split */
2831 remainder
= chunk_at_offset(victim
, nb
);
2832 set_head(victim
, nb
| PREV_INUSE
);
2833 link_last_remainder(ar_ptr
, remainder
);
2834 set_head(remainder
, remainder_size
| PREV_INUSE
);
2835 set_foot(remainder
, remainder_size
);
2836 check_malloced_chunk(ar_ptr
, victim
, nb
);
2840 clear_last_remainder(ar_ptr
);
2842 if (remainder_size
>= 0) /* exhaust */
2844 set_inuse_bit_at_offset(victim
, victim_size
);
2845 check_malloced_chunk(ar_ptr
, victim
, nb
);
2849 /* Else place in bin */
2851 frontlink(ar_ptr
, victim
, victim_size
, remainder_index
, bck
, fwd
);
2855 If there are any possibly nonempty big-enough blocks,
2856 search for best fitting chunk by scanning bins in blockwidth units.
2859 if ( (block
= idx2binblock(idx
)) <= binblocks(ar_ptr
))
2862 /* Get to the first marked block */
2864 if ( (block
& binblocks(ar_ptr
)) == 0)
2866 /* force to an even block boundary */
2867 idx
= (idx
& ~(BINBLOCKWIDTH
- 1)) + BINBLOCKWIDTH
;
2869 while ((block
& binblocks(ar_ptr
)) == 0)
2871 idx
+= BINBLOCKWIDTH
;
2876 /* For each possibly nonempty block ... */
2879 startidx
= idx
; /* (track incomplete blocks) */
2880 q
= bin
= _bin_at(ar_ptr
, idx
);
2882 /* For each bin in this block ... */
2885 /* Find and use first big enough chunk ... */
2887 for (victim
= last(bin
); victim
!= bin
; victim
= victim
->bk
)
2889 victim_size
= chunksize(victim
);
2890 remainder_size
= victim_size
- nb
;
2892 if (remainder_size
>= (long)MINSIZE
) /* split */
2894 remainder
= chunk_at_offset(victim
, nb
);
2895 set_head(victim
, nb
| PREV_INUSE
);
2896 unlink(victim
, bck
, fwd
);
2897 link_last_remainder(ar_ptr
, remainder
);
2898 set_head(remainder
, remainder_size
| PREV_INUSE
);
2899 set_foot(remainder
, remainder_size
);
2900 check_malloced_chunk(ar_ptr
, victim
, nb
);
2904 else if (remainder_size
>= 0) /* take */
2906 set_inuse_bit_at_offset(victim
, victim_size
);
2907 unlink(victim
, bck
, fwd
);
2908 check_malloced_chunk(ar_ptr
, victim
, nb
);
2914 bin
= next_bin(bin
);
2916 } while ((++idx
& (BINBLOCKWIDTH
- 1)) != 0);
2918 /* Clear out the block bit. */
2920 do /* Possibly backtrack to try to clear a partial block */
2922 if ((startidx
& (BINBLOCKWIDTH
- 1)) == 0)
2924 binblocks(ar_ptr
) &= ~block
;
2929 } while (first(q
) == q
);
2931 /* Get to the next possibly nonempty block */
2933 if ( (block
<<= 1) <= binblocks(ar_ptr
) && (block
!= 0) )
2935 while ((block
& binblocks(ar_ptr
)) == 0)
2937 idx
+= BINBLOCKWIDTH
;
2947 /* Try to use top chunk */
2949 /* Require that there be a remainder, ensuring top always exists */
2950 if ( (remainder_size
= chunksize(top(ar_ptr
)) - nb
) < (long)MINSIZE
)
2954 /* If the request is big and there are not yet too many regions,
2955 and we would otherwise need to extend, try to use mmap instead. */
2956 if ((unsigned long)nb
>= (unsigned long)mmap_threshold
&&
2957 n_mmaps
< n_mmaps_max
&&
2958 (victim
= mmap_chunk(nb
)) != 0)
2963 malloc_extend_top(ar_ptr
, nb
);
2964 if ((remainder_size
= chunksize(top(ar_ptr
)) - nb
) < (long)MINSIZE
)
2967 /* A last attempt: when we are out of address space in a
2968 non-main arena, try mmap anyway, as long as it is allowed at
2970 if (ar_ptr
!= &main_arena
&&
2972 (victim
= mmap_chunk(nb
)) != 0)
2975 return 0; /* propagate failure */
2979 victim
= top(ar_ptr
);
2980 set_head(victim
, nb
| PREV_INUSE
);
2981 top(ar_ptr
) = chunk_at_offset(victim
, nb
);
2982 set_head(top(ar_ptr
), remainder_size
| PREV_INUSE
);
2983 check_malloced_chunk(ar_ptr
, victim
, nb
);
2997 1. free(0) has no effect.
2999 2. If the chunk was allocated via mmap, it is released via munmap().
3001 3. If a returned chunk borders the current high end of memory,
3002 it is consolidated into the top, and if the total unused
3003 topmost memory exceeds the trim threshold, malloc_trim is
3006 4. Other chunks are consolidated as they arrive, and
3007 placed in corresponding bins. (This includes the case of
3008 consolidating with the current `last_remainder').
3014 void fREe(Void_t
* mem
)
3016 void fREe(mem
) Void_t
* mem
;
3020 mchunkptr p
; /* chunk corresponding to mem */
3022 #if defined _LIBC || defined MALLOC_HOOKS
3023 if (__free_hook
!= NULL
) {
3024 #if defined __GNUC__ && __GNUC__ >= 2
3025 (*__free_hook
)(mem
, RETURN_ADDRESS (0));
3027 (*__free_hook
)(mem
, NULL
);
3033 if (mem
== 0) /* free(0) has no effect */
3039 if (chunk_is_mmapped(p
)) /* release mmapped memory. */
3046 ar_ptr
= arena_for_ptr(p
);
3048 if(!mutex_trylock(&ar_ptr
->mutex
))
3049 ++(ar_ptr
->stat_lock_direct
);
3051 (void)mutex_lock(&ar_ptr
->mutex
);
3052 ++(ar_ptr
->stat_lock_wait
);
3055 (void)mutex_lock(&ar_ptr
->mutex
);
3057 chunk_free(ar_ptr
, p
);
3058 (void)mutex_unlock(&ar_ptr
->mutex
);
3064 chunk_free(arena
*ar_ptr
, mchunkptr p
)
3066 chunk_free(ar_ptr
, p
) arena
*ar_ptr
; mchunkptr p
;
3069 INTERNAL_SIZE_T hd
= p
->size
; /* its head field */
3070 INTERNAL_SIZE_T sz
; /* its size */
3071 int idx
; /* its bin index */
3072 mchunkptr next
; /* next contiguous chunk */
3073 INTERNAL_SIZE_T nextsz
; /* its size */
3074 INTERNAL_SIZE_T prevsz
; /* size of previous contiguous chunk */
3075 mchunkptr bck
; /* misc temp for linking */
3076 mchunkptr fwd
; /* misc temp for linking */
3077 int islr
; /* track whether merging with last_remainder */
3079 check_inuse_chunk(ar_ptr
, p
);
3081 sz
= hd
& ~PREV_INUSE
;
3082 next
= chunk_at_offset(p
, sz
);
3083 nextsz
= chunksize(next
);
3085 if (next
== top(ar_ptr
)) /* merge with top */
3089 if (!(hd
& PREV_INUSE
)) /* consolidate backward */
3091 prevsz
= p
->prev_size
;
3092 p
= chunk_at_offset(p
, -(long)prevsz
);
3094 unlink(p
, bck
, fwd
);
3097 set_head(p
, sz
| PREV_INUSE
);
3101 if(ar_ptr
== &main_arena
) {
3103 if ((unsigned long)(sz
) >= (unsigned long)trim_threshold
)
3107 heap_info
*heap
= heap_for_ptr(p
);
3109 assert(heap
->ar_ptr
== ar_ptr
);
3111 /* Try to get rid of completely empty heaps, if possible. */
3112 if((unsigned long)(sz
) >= (unsigned long)trim_threshold
||
3113 p
== chunk_at_offset(heap
, sizeof(*heap
)))
3114 heap_trim(heap
, top_pad
);
3122 if (!(hd
& PREV_INUSE
)) /* consolidate backward */
3124 prevsz
= p
->prev_size
;
3125 p
= chunk_at_offset(p
, -(long)prevsz
);
3128 if (p
->fd
== last_remainder(ar_ptr
)) /* keep as last_remainder */
3131 unlink(p
, bck
, fwd
);
3134 if (!(inuse_bit_at_offset(next
, nextsz
))) /* consolidate forward */
3138 if (!islr
&& next
->fd
== last_remainder(ar_ptr
))
3139 /* re-insert last_remainder */
3142 link_last_remainder(ar_ptr
, p
);
3145 unlink(next
, bck
, fwd
);
3147 next
= chunk_at_offset(p
, sz
);
3150 set_head(next
, nextsz
); /* clear inuse bit */
3152 set_head(p
, sz
| PREV_INUSE
);
3153 next
->prev_size
= sz
;
3155 frontlink(ar_ptr
, p
, sz
, idx
, bck
, fwd
);
3158 /* Check whether the heap containing top can go away now. */
3159 if(next
->size
< MINSIZE
&&
3160 (unsigned long)sz
> trim_threshold
&&
3161 ar_ptr
!= &main_arena
) { /* fencepost */
3162 heap_info
*heap
= heap_for_ptr(top(ar_ptr
));
3164 if(top(ar_ptr
) == chunk_at_offset(heap
, sizeof(*heap
)) &&
3165 heap
->prev
== heap_for_ptr(p
))
3166 heap_trim(heap
, top_pad
);
3179 Chunks that were obtained via mmap cannot be extended or shrunk
3180 unless HAVE_MREMAP is defined, in which case mremap is used.
3181 Otherwise, if their reallocation is for additional space, they are
3182 copied. If for less, they are just left alone.
3184 Otherwise, if the reallocation is for additional space, and the
3185 chunk can be extended, it is, else a malloc-copy-free sequence is
3186 taken. There are several different ways that a chunk could be
3187 extended. All are tried:
3189 * Extending forward into following adjacent free chunk.
3190 * Shifting backwards, joining preceding adjacent space
3191 * Both shifting backwards and extending forward.
3192 * Extending into newly sbrked space
3194 Unless the #define REALLOC_ZERO_BYTES_FREES is set, realloc with a
3195 size argument of zero (re)allocates a minimum-sized chunk.
3197 If the reallocation is for less space, and the new request is for
3198 a `small' (<512 bytes) size, then the newly unused space is lopped
3201 The old unix realloc convention of allowing the last-free'd chunk
3202 to be used as an argument to realloc is no longer supported.
3203 I don't know of any programs still relying on this feature,
3204 and allowing it would also allow too many other incorrect
3205 usages of realloc to be sensible.
3212 Void_t
* rEALLOc(Void_t
* oldmem
, size_t bytes
)
3214 Void_t
* rEALLOc(oldmem
, bytes
) Void_t
* oldmem
; size_t bytes
;
3218 INTERNAL_SIZE_T nb
; /* padded request size */
3220 mchunkptr oldp
; /* chunk corresponding to oldmem */
3221 INTERNAL_SIZE_T oldsize
; /* its size */
3223 mchunkptr newp
; /* chunk to return */
3225 #if defined _LIBC || defined MALLOC_HOOKS
3226 if (__realloc_hook
!= NULL
) {
3229 #if defined __GNUC__ && __GNUC__ >= 2
3230 result
= (*__realloc_hook
)(oldmem
, bytes
, RETURN_ADDRESS (0));
3232 result
= (*__realloc_hook
)(oldmem
, bytes
, NULL
);
3238 #ifdef REALLOC_ZERO_BYTES_FREES
3239 if (bytes
== 0 && oldmem
!= NULL
) { fREe(oldmem
); return 0; }
3242 /* realloc of null is supposed to be same as malloc */
3243 if (oldmem
== 0) return mALLOc(bytes
);
3245 oldp
= mem2chunk(oldmem
);
3246 oldsize
= chunksize(oldp
);
3248 if(request2size(bytes
, nb
))
3252 if (chunk_is_mmapped(oldp
))
3257 newp
= mremap_chunk(oldp
, nb
);
3259 return BOUNDED_N(chunk2mem(newp
), bytes
);
3261 /* Note the extra SIZE_SZ overhead. */
3262 if(oldsize
- SIZE_SZ
>= nb
) return oldmem
; /* do nothing */
3263 /* Must alloc, copy, free. */
3264 newmem
= mALLOc(bytes
);
3265 if (newmem
== 0) return 0; /* propagate failure */
3266 MALLOC_COPY(newmem
, oldmem
, oldsize
- 2*SIZE_SZ
, 0);
3272 ar_ptr
= arena_for_ptr(oldp
);
3274 if(!mutex_trylock(&ar_ptr
->mutex
))
3275 ++(ar_ptr
->stat_lock_direct
);
3277 (void)mutex_lock(&ar_ptr
->mutex
);
3278 ++(ar_ptr
->stat_lock_wait
);
3281 (void)mutex_lock(&ar_ptr
->mutex
);
3285 /* As in malloc(), remember this arena for the next allocation. */
3286 tsd_setspecific(arena_key
, (Void_t
*)ar_ptr
);
3289 newp
= chunk_realloc(ar_ptr
, oldp
, oldsize
, nb
);
3291 (void)mutex_unlock(&ar_ptr
->mutex
);
3292 return newp
? BOUNDED_N(chunk2mem(newp
), bytes
) : NULL
;
3298 chunk_realloc(arena
* ar_ptr
, mchunkptr oldp
, INTERNAL_SIZE_T oldsize
,
3301 chunk_realloc(ar_ptr
, oldp
, oldsize
, nb
)
3302 arena
* ar_ptr
; mchunkptr oldp
; INTERNAL_SIZE_T oldsize
, nb
;
3305 mchunkptr newp
= oldp
; /* chunk to return */
3306 INTERNAL_SIZE_T newsize
= oldsize
; /* its size */
3308 mchunkptr next
; /* next contiguous chunk after oldp */
3309 INTERNAL_SIZE_T nextsize
; /* its size */
3311 mchunkptr prev
; /* previous contiguous chunk before oldp */
3312 INTERNAL_SIZE_T prevsize
; /* its size */
3314 mchunkptr remainder
; /* holds split off extra space from newp */
3315 INTERNAL_SIZE_T remainder_size
; /* its size */
3317 mchunkptr bck
; /* misc temp for linking */
3318 mchunkptr fwd
; /* misc temp for linking */
3320 check_inuse_chunk(ar_ptr
, oldp
);
3322 if ((long)(oldsize
) < (long)(nb
))
3324 Void_t
* oldmem
= BOUNDED_N(chunk2mem(oldp
), oldsize
);
3326 /* Try expanding forward */
3328 next
= chunk_at_offset(oldp
, oldsize
);
3329 if (next
== top(ar_ptr
) || !inuse(next
))
3331 nextsize
= chunksize(next
);
3333 /* Forward into top only if a remainder */
3334 if (next
== top(ar_ptr
))
3336 if ((long)(nextsize
+ newsize
) >= (long)(nb
+ MINSIZE
))
3338 newsize
+= nextsize
;
3339 top(ar_ptr
) = chunk_at_offset(oldp
, nb
);
3340 set_head(top(ar_ptr
), (newsize
- nb
) | PREV_INUSE
);
3341 set_head_size(oldp
, nb
);
3346 /* Forward into next chunk */
3347 else if (((long)(nextsize
+ newsize
) >= (long)(nb
)))
3349 unlink(next
, bck
, fwd
);
3350 newsize
+= nextsize
;
3362 /* Try shifting backwards. */
3364 if (!prev_inuse(oldp
))
3366 prev
= prev_chunk(oldp
);
3367 prevsize
= chunksize(prev
);
3369 /* try forward + backward first to save a later consolidation */
3374 if (next
== top(ar_ptr
))
3376 if ((long)(nextsize
+ prevsize
+ newsize
) >= (long)(nb
+ MINSIZE
))
3378 unlink(prev
, bck
, fwd
);
3380 newsize
+= prevsize
+ nextsize
;
3381 MALLOC_COPY(BOUNDED_N(chunk2mem(newp
), oldsize
), oldmem
, oldsize
,
3383 top(ar_ptr
) = chunk_at_offset(newp
, nb
);
3384 set_head(top(ar_ptr
), (newsize
- nb
) | PREV_INUSE
);
3385 set_head_size(newp
, nb
);
3390 /* into next chunk */
3391 else if (((long)(nextsize
+ prevsize
+ newsize
) >= (long)(nb
)))
3393 unlink(next
, bck
, fwd
);
3394 unlink(prev
, bck
, fwd
);
3396 newsize
+= nextsize
+ prevsize
;
3397 MALLOC_COPY(BOUNDED_N(chunk2mem(newp
), oldsize
), oldmem
, oldsize
, 1);
3403 if (prev
!= 0 && (long)(prevsize
+ newsize
) >= (long)nb
)
3405 unlink(prev
, bck
, fwd
);
3407 newsize
+= prevsize
;
3408 MALLOC_COPY(BOUNDED_N(chunk2mem(newp
), oldsize
), oldmem
, oldsize
, 1);
3415 newp
= chunk_alloc (ar_ptr
, nb
);
3418 /* Maybe the failure is due to running out of mmapped areas. */
3419 if (ar_ptr
!= &main_arena
) {
3420 (void)mutex_lock(&main_arena
.mutex
);
3421 newp
= chunk_alloc(&main_arena
, nb
);
3422 (void)mutex_unlock(&main_arena
.mutex
);
3425 /* ... or sbrk() has failed and there is still a chance to mmap() */
3426 arena
* ar_ptr2
= arena_get2(ar_ptr
->next
? ar_ptr
: 0, nb
);
3428 newp
= chunk_alloc(ar_ptr2
, nb
);
3429 (void)mutex_unlock(&ar_ptr2
->mutex
);
3433 if (newp
== 0) /* propagate failure */
3437 /* Avoid copy if newp is next chunk after oldp. */
3438 /* (This can only happen when new chunk is sbrk'ed.) */
3440 if ( newp
== next_chunk(oldp
))
3442 newsize
+= chunksize(newp
);
3447 /* Otherwise copy, free, and exit */
3448 MALLOC_COPY(BOUNDED_N(chunk2mem(newp
), oldsize
), oldmem
, oldsize
, 0);
3449 chunk_free(ar_ptr
, oldp
);
3454 split
: /* split off extra room in old or expanded chunk */
3456 if (newsize
- nb
>= MINSIZE
) /* split off remainder */
3458 remainder
= chunk_at_offset(newp
, nb
);
3459 remainder_size
= newsize
- nb
;
3460 set_head_size(newp
, nb
);
3461 set_head(remainder
, remainder_size
| PREV_INUSE
);
3462 set_inuse_bit_at_offset(remainder
, remainder_size
);
3463 chunk_free(ar_ptr
, remainder
);
3467 set_head_size(newp
, newsize
);
3468 set_inuse_bit_at_offset(newp
, newsize
);
3471 check_inuse_chunk(ar_ptr
, newp
);
3482 memalign requests more than enough space from malloc, finds a spot
3483 within that chunk that meets the alignment request, and then
3484 possibly frees the leading and trailing space.
3486 The alignment argument must be a power of two. This property is not
3487 checked by memalign, so misuse may result in random runtime errors.
3489 8-byte alignment is guaranteed by normal malloc calls, so don't
3490 bother calling memalign with an argument of 8 or less.
3492 Overreliance on memalign is a sure way to fragment space.
3498 Void_t
* mEMALIGn(size_t alignment
, size_t bytes
)
3500 Void_t
* mEMALIGn(alignment
, bytes
) size_t alignment
; size_t bytes
;
3504 INTERNAL_SIZE_T nb
; /* padded request size */
3507 #if defined _LIBC || defined MALLOC_HOOKS
3508 if (__memalign_hook
!= NULL
) {
3511 #if defined __GNUC__ && __GNUC__ >= 2
3512 result
= (*__memalign_hook
)(alignment
, bytes
, RETURN_ADDRESS (0));
3514 result
= (*__memalign_hook
)(alignment
, bytes
, NULL
);
3520 /* If need less alignment than we give anyway, just relay to malloc */
3522 if (alignment
<= MALLOC_ALIGNMENT
) return mALLOc(bytes
);
3524 /* Otherwise, ensure that it is at least a minimum chunk size */
3526 if (alignment
< MINSIZE
) alignment
= MINSIZE
;
3528 if(request2size(bytes
, nb
))
3530 arena_get(ar_ptr
, nb
+ alignment
+ MINSIZE
);
3533 p
= chunk_align(ar_ptr
, nb
, alignment
);
3534 (void)mutex_unlock(&ar_ptr
->mutex
);
3536 /* Maybe the failure is due to running out of mmapped areas. */
3537 if(ar_ptr
!= &main_arena
) {
3538 (void)mutex_lock(&main_arena
.mutex
);
3539 p
= chunk_align(&main_arena
, nb
, alignment
);
3540 (void)mutex_unlock(&main_arena
.mutex
);
3543 /* ... or sbrk() has failed and there is still a chance to mmap() */
3544 ar_ptr
= arena_get2(ar_ptr
->next
? ar_ptr
: 0, nb
);
3546 p
= chunk_align(ar_ptr
, nb
, alignment
);
3547 (void)mutex_unlock(&ar_ptr
->mutex
);
3553 return BOUNDED_N(chunk2mem(p
), bytes
);
3559 chunk_align(arena
* ar_ptr
, INTERNAL_SIZE_T nb
, size_t alignment
)
3561 chunk_align(ar_ptr
, nb
, alignment
)
3562 arena
* ar_ptr
; INTERNAL_SIZE_T nb
; size_t alignment
;
3565 unsigned long m
; /* memory returned by malloc call */
3566 mchunkptr p
; /* corresponding chunk */
3567 char* brk
; /* alignment point within p */
3568 mchunkptr newp
; /* chunk to return */
3569 INTERNAL_SIZE_T newsize
; /* its size */
3570 INTERNAL_SIZE_T leadsize
; /* leading space befor alignment point */
3571 mchunkptr remainder
; /* spare room at end to split off */
3572 long remainder_size
; /* its size */
3574 /* Call chunk_alloc with worst case padding to hit alignment. */
3575 p
= chunk_alloc(ar_ptr
, nb
+ alignment
+ MINSIZE
);
3577 return 0; /* propagate failure */
3579 m
= (unsigned long)chunk2mem(p
);
3581 if ((m
% alignment
) == 0) /* aligned */
3584 if(chunk_is_mmapped(p
)) {
3585 return p
; /* nothing more to do */
3589 else /* misaligned */
3592 Find an aligned spot inside chunk.
3593 Since we need to give back leading space in a chunk of at
3594 least MINSIZE, if the first calculation places us at
3595 a spot with less than MINSIZE leader, we can move to the
3596 next aligned spot -- we've allocated enough total room so that
3597 this is always possible.
3600 brk
= (char*)mem2chunk(((m
+ alignment
- 1)) & -(long)alignment
);
3601 if ((long)(brk
- (char*)(p
)) < (long)MINSIZE
) brk
+= alignment
;
3603 newp
= chunk_at_offset(brk
, 0);
3604 leadsize
= brk
- (char*)(p
);
3605 newsize
= chunksize(p
) - leadsize
;
3608 if(chunk_is_mmapped(p
))
3610 newp
->prev_size
= p
->prev_size
+ leadsize
;
3611 set_head(newp
, newsize
|IS_MMAPPED
);
3616 /* give back leader, use the rest */
3618 set_head(newp
, newsize
| PREV_INUSE
);
3619 set_inuse_bit_at_offset(newp
, newsize
);
3620 set_head_size(p
, leadsize
);
3621 chunk_free(ar_ptr
, p
);
3624 assert (newsize
>=nb
&& (((unsigned long)(chunk2mem(p
))) % alignment
) == 0);
3627 /* Also give back spare room at the end */
3629 remainder_size
= chunksize(p
) - nb
;
3631 if (remainder_size
>= (long)MINSIZE
)
3633 remainder
= chunk_at_offset(p
, nb
);
3634 set_head(remainder
, remainder_size
| PREV_INUSE
);
3635 set_head_size(p
, nb
);
3636 chunk_free(ar_ptr
, remainder
);
3639 check_inuse_chunk(ar_ptr
, p
);
3647 valloc just invokes memalign with alignment argument equal
3648 to the page size of the system (or as near to this as can
3649 be figured out from all the includes/defines above.)
3653 Void_t
* vALLOc(size_t bytes
)
3655 Void_t
* vALLOc(bytes
) size_t bytes
;
3658 if(__malloc_initialized
< 0)
3660 return mEMALIGn (malloc_getpagesize
, bytes
);
3664 pvalloc just invokes valloc for the nearest pagesize
3665 that will accommodate request
3670 Void_t
* pvALLOc(size_t bytes
)
3672 Void_t
* pvALLOc(bytes
) size_t bytes
;
3676 if(__malloc_initialized
< 0)
3678 pagesize
= malloc_getpagesize
;
3679 return mEMALIGn (pagesize
, (bytes
+ pagesize
- 1) & ~(pagesize
- 1));
3684 calloc calls chunk_alloc, then zeroes out the allocated chunk.
3689 Void_t
* cALLOc(size_t n
, size_t elem_size
)
3691 Void_t
* cALLOc(n
, elem_size
) size_t n
; size_t elem_size
;
3695 mchunkptr p
, oldtop
;
3696 INTERNAL_SIZE_T sz
, csz
, oldtopsize
;
3699 #if defined _LIBC || defined MALLOC_HOOKS
3700 if (__malloc_hook
!= NULL
) {
3702 #if defined __GNUC__ && __GNUC__ >= 2
3703 mem
= (*__malloc_hook
)(sz
, RETURN_ADDRESS (0));
3705 mem
= (*__malloc_hook
)(sz
, NULL
);
3710 return memset(mem
, 0, sz
);
3712 while(sz
> 0) ((char*)mem
)[--sz
] = 0; /* rather inefficient */
3718 if(request2size(n
* elem_size
, sz
))
3720 arena_get(ar_ptr
, sz
);
3724 /* Check if expand_top called, in which case there may be
3725 no need to clear. */
3727 oldtop
= top(ar_ptr
);
3728 oldtopsize
= chunksize(top(ar_ptr
));
3729 #if MORECORE_CLEARS < 2
3730 /* Only newly allocated memory is guaranteed to be cleared. */
3731 if (ar_ptr
== &main_arena
&&
3732 oldtopsize
< sbrk_base
+ max_sbrked_mem
- (char *)oldtop
)
3733 oldtopsize
= (sbrk_base
+ max_sbrked_mem
- (char *)oldtop
);
3736 p
= chunk_alloc (ar_ptr
, sz
);
3738 /* Only clearing follows, so we can unlock early. */
3739 (void)mutex_unlock(&ar_ptr
->mutex
);
3742 /* Maybe the failure is due to running out of mmapped areas. */
3743 if(ar_ptr
!= &main_arena
) {
3744 (void)mutex_lock(&main_arena
.mutex
);
3745 p
= chunk_alloc(&main_arena
, sz
);
3746 (void)mutex_unlock(&main_arena
.mutex
);
3749 /* ... or sbrk() has failed and there is still a chance to mmap() */
3750 (void)mutex_lock(&main_arena
.mutex
);
3751 ar_ptr
= arena_get2(ar_ptr
->next
? ar_ptr
: 0, sz
);
3752 (void)mutex_unlock(&main_arena
.mutex
);
3754 p
= chunk_alloc(ar_ptr
, sz
);
3755 (void)mutex_unlock(&ar_ptr
->mutex
);
3759 if (p
== 0) return 0;
3761 mem
= BOUNDED_N(chunk2mem(p
), n
* elem_size
);
3763 /* Two optional cases in which clearing not necessary */
3766 if (chunk_is_mmapped(p
)) return mem
;
3772 if (p
== oldtop
&& csz
> oldtopsize
) {
3773 /* clear only the bytes from non-freshly-sbrked memory */
3779 MALLOC_ZERO(BOUNDED_N(chunk2mem(p
), csz
), csz
);
3785 cfree just calls free. It is needed/defined on some systems
3786 that pair it with calloc, presumably for odd historical reasons.
3792 void cfree(Void_t
*mem
)
3794 void cfree(mem
) Void_t
*mem
;
3805 Malloc_trim gives memory back to the system (via negative
3806 arguments to sbrk) if there is unused memory at the `high' end of
3807 the malloc pool. You can call this after freeing large blocks of
3808 memory to potentially reduce the system-level memory requirements
3809 of a program. However, it cannot guarantee to reduce memory. Under
3810 some allocation patterns, some large free blocks of memory will be
3811 locked between two used chunks, so they cannot be given back to
3814 The `pad' argument to malloc_trim represents the amount of free
3815 trailing space to leave untrimmed. If this argument is zero,
3816 only the minimum amount of memory to maintain internal data
3817 structures will be left (one page or less). Non-zero arguments
3818 can be supplied to maintain enough trailing space to service
3819 future expected allocations without having to re-obtain memory
3822 Malloc_trim returns 1 if it actually released any memory, else 0.
3827 int mALLOC_TRIm(size_t pad
)
3829 int mALLOC_TRIm(pad
) size_t pad
;
3834 (void)mutex_lock(&main_arena
.mutex
);
3835 res
= main_trim(pad
);
3836 (void)mutex_unlock(&main_arena
.mutex
);
3840 /* Trim the main arena. */
3845 main_trim(size_t pad
)
3847 main_trim(pad
) size_t pad
;
3850 mchunkptr top_chunk
; /* The current top chunk */
3851 long top_size
; /* Amount of top-most memory */
3852 long extra
; /* Amount to release */
3853 char* current_brk
; /* address returned by pre-check sbrk call */
3854 char* new_brk
; /* address returned by negative sbrk call */
3856 unsigned long pagesz
= malloc_getpagesize
;
3858 top_chunk
= top(&main_arena
);
3859 top_size
= chunksize(top_chunk
);
3860 extra
= ((top_size
- pad
- MINSIZE
+ (pagesz
-1)) / pagesz
- 1) * pagesz
;
3862 if (extra
< (long)pagesz
) /* Not enough memory to release */
3865 /* Test to make sure no one else called sbrk */
3866 current_brk
= (char*)(MORECORE (0));
3867 if (current_brk
!= (char*)(top_chunk
) + top_size
)
3868 return 0; /* Apparently we don't own memory; must fail */
3870 new_brk
= (char*)(MORECORE (-extra
));
3872 #if defined _LIBC || defined MALLOC_HOOKS
3873 /* Call the `morecore' hook if necessary. */
3874 if (__after_morecore_hook
)
3875 (*__after_morecore_hook
) ();
3878 if (new_brk
== (char*)(MORECORE_FAILURE
)) { /* sbrk failed? */
3879 /* Try to figure out what we have */
3880 current_brk
= (char*)(MORECORE (0));
3881 top_size
= current_brk
- (char*)top_chunk
;
3882 if (top_size
>= (long)MINSIZE
) /* if not, we are very very dead! */
3884 sbrked_mem
= current_brk
- sbrk_base
;
3885 set_head(top_chunk
, top_size
| PREV_INUSE
);
3887 check_chunk(&main_arena
, top_chunk
);
3890 sbrked_mem
-= extra
;
3892 /* Success. Adjust top accordingly. */
3893 set_head(top_chunk
, (top_size
- extra
) | PREV_INUSE
);
3894 check_chunk(&main_arena
, top_chunk
);
3903 heap_trim(heap_info
*heap
, size_t pad
)
3905 heap_trim(heap
, pad
) heap_info
*heap
; size_t pad
;
3908 unsigned long pagesz
= malloc_getpagesize
;
3909 arena
*ar_ptr
= heap
->ar_ptr
;
3910 mchunkptr top_chunk
= top(ar_ptr
), p
, bck
, fwd
;
3911 heap_info
*prev_heap
;
3912 long new_size
, top_size
, extra
;
3914 /* Can this heap go away completely ? */
3915 while(top_chunk
== chunk_at_offset(heap
, sizeof(*heap
))) {
3916 prev_heap
= heap
->prev
;
3917 p
= chunk_at_offset(prev_heap
, prev_heap
->size
- (MINSIZE
-2*SIZE_SZ
));
3918 assert(p
->size
== (0|PREV_INUSE
)); /* must be fencepost */
3920 new_size
= chunksize(p
) + (MINSIZE
-2*SIZE_SZ
);
3921 assert(new_size
>0 && new_size
<(long)(2*MINSIZE
));
3923 new_size
+= p
->prev_size
;
3924 assert(new_size
>0 && new_size
<HEAP_MAX_SIZE
);
3925 if(new_size
+ (HEAP_MAX_SIZE
- prev_heap
->size
) < pad
+ MINSIZE
+ pagesz
)
3927 ar_ptr
->size
-= heap
->size
;
3928 arena_mem
-= heap
->size
;
3931 if(!prev_inuse(p
)) { /* consolidate backward */
3933 unlink(p
, bck
, fwd
);
3935 assert(((unsigned long)((char*)p
+ new_size
) & (pagesz
-1)) == 0);
3936 assert( ((char*)p
+ new_size
) == ((char*)heap
+ heap
->size
) );
3937 top(ar_ptr
) = top_chunk
= p
;
3938 set_head(top_chunk
, new_size
| PREV_INUSE
);
3939 check_chunk(ar_ptr
, top_chunk
);
3941 top_size
= chunksize(top_chunk
);
3942 extra
= ((top_size
- pad
- MINSIZE
+ (pagesz
-1))/pagesz
- 1) * pagesz
;
3943 if(extra
< (long)pagesz
)
3945 /* Try to shrink. */
3946 if(grow_heap(heap
, -extra
) != 0)
3948 ar_ptr
->size
-= extra
;
3951 /* Success. Adjust top accordingly. */
3952 set_head(top_chunk
, (top_size
- extra
) | PREV_INUSE
);
3953 check_chunk(ar_ptr
, top_chunk
);
3957 #endif /* USE_ARENAS */
3964 This routine tells you how many bytes you can actually use in an
3965 allocated chunk, which may be more than you requested (although
3966 often not). You can use this many bytes without worrying about
3967 overwriting other allocated objects. Not a particularly great
3968 programming practice, but still sometimes useful.
3973 size_t mALLOC_USABLE_SIZe(Void_t
* mem
)
3975 size_t mALLOC_USABLE_SIZe(mem
) Void_t
* mem
;
3985 if(!chunk_is_mmapped(p
))
3987 if (!inuse(p
)) return 0;
3988 check_inuse_chunk(arena_for_ptr(mem
), p
);
3989 return chunksize(p
) - SIZE_SZ
;
3991 return chunksize(p
) - 2*SIZE_SZ
;
3998 /* Utility to update mallinfo for malloc_stats() and mallinfo() */
4002 malloc_update_mallinfo(arena
*ar_ptr
, struct mallinfo
*mi
)
4004 malloc_update_mallinfo(ar_ptr
, mi
) arena
*ar_ptr
; struct mallinfo
*mi
;
4013 INTERNAL_SIZE_T avail
;
4015 (void)mutex_lock(&ar_ptr
->mutex
);
4016 avail
= chunksize(top(ar_ptr
));
4017 navail
= ((long)(avail
) >= (long)MINSIZE
)? 1 : 0;
4019 for (i
= 1; i
< NAV
; ++i
)
4021 b
= bin_at(ar_ptr
, i
);
4022 for (p
= last(b
); p
!= b
; p
= p
->bk
)
4025 check_free_chunk(ar_ptr
, p
);
4026 for (q
= next_chunk(p
);
4027 q
!= top(ar_ptr
) && inuse(q
) && (long)chunksize(q
) > 0;
4029 check_inuse_chunk(ar_ptr
, q
);
4031 avail
+= chunksize(p
);
4036 mi
->arena
= ar_ptr
->size
;
4037 mi
->ordblks
= navail
;
4038 mi
->smblks
= mi
->usmblks
= mi
->fsmblks
= 0; /* clear unused fields */
4039 mi
->uordblks
= ar_ptr
->size
- avail
;
4040 mi
->fordblks
= avail
;
4041 mi
->hblks
= n_mmaps
;
4042 mi
->hblkhd
= mmapped_mem
;
4043 mi
->keepcost
= chunksize(top(ar_ptr
));
4045 (void)mutex_unlock(&ar_ptr
->mutex
);
4048 #if USE_ARENAS && MALLOC_DEBUG > 1
4050 /* Print the complete contents of a single heap to stderr. */
4054 dump_heap(heap_info
*heap
)
4056 dump_heap(heap
) heap_info
*heap
;
4062 fprintf(stderr
, "Heap %p, size %10lx:\n", heap
, (long)heap
->size
);
4063 ptr
= (heap
->ar_ptr
!= (arena
*)(heap
+1)) ?
4064 (char*)(heap
+ 1) : (char*)(heap
+ 1) + sizeof(arena
);
4065 p
= (mchunkptr
)(((unsigned long)ptr
+ MALLOC_ALIGN_MASK
) &
4066 ~MALLOC_ALIGN_MASK
);
4068 fprintf(stderr
, "chunk %p size %10lx", p
, (long)p
->size
);
4069 if(p
== top(heap
->ar_ptr
)) {
4070 fprintf(stderr
, " (top)\n");
4072 } else if(p
->size
== (0|PREV_INUSE
)) {
4073 fprintf(stderr
, " (fence)\n");
4076 fprintf(stderr
, "\n");
4089 For all arenas separately and in total, prints on stderr the
4090 amount of space obtained from the system, and the current number
4091 of bytes allocated via malloc (or realloc, etc) but not yet
4092 freed. (Note that this is the number of bytes allocated, not the
4093 number requested. It will be larger than the number requested
4094 because of alignment and bookkeeping overhead.) When not compiled
4095 for multiple threads, the maximum amount of allocated memory
4096 (which may be more than current if malloc_trim and/or munmap got
4097 called) is also reported. When using mmap(), prints the maximum
4098 number of simultaneous mmap regions used, too.
4107 unsigned int in_use_b
= mmapped_mem
, system_b
= in_use_b
;
4109 long stat_lock_direct
= 0, stat_lock_loop
= 0, stat_lock_wait
= 0;
4112 for(i
=0, ar_ptr
= &main_arena
;; i
++) {
4113 malloc_update_mallinfo(ar_ptr
, &mi
);
4114 fprintf(stderr
, "Arena %d:\n", i
);
4115 fprintf(stderr
, "system bytes = %10u\n", (unsigned int)mi
.arena
);
4116 fprintf(stderr
, "in use bytes = %10u\n", (unsigned int)mi
.uordblks
);
4117 system_b
+= mi
.arena
;
4118 in_use_b
+= mi
.uordblks
;
4120 stat_lock_direct
+= ar_ptr
->stat_lock_direct
;
4121 stat_lock_loop
+= ar_ptr
->stat_lock_loop
;
4122 stat_lock_wait
+= ar_ptr
->stat_lock_wait
;
4124 #if USE_ARENAS && MALLOC_DEBUG > 1
4125 if(ar_ptr
!= &main_arena
) {
4127 (void)mutex_lock(&ar_ptr
->mutex
);
4128 heap
= heap_for_ptr(top(ar_ptr
));
4129 while(heap
) { dump_heap(heap
); heap
= heap
->prev
; }
4130 (void)mutex_unlock(&ar_ptr
->mutex
);
4133 ar_ptr
= ar_ptr
->next
;
4134 if(ar_ptr
== &main_arena
) break;
4137 fprintf(stderr
, "Total (incl. mmap):\n");
4139 fprintf(stderr
, "Total:\n");
4141 fprintf(stderr
, "system bytes = %10u\n", system_b
);
4142 fprintf(stderr
, "in use bytes = %10u\n", in_use_b
);
4144 fprintf(stderr
, "max system bytes = %10u\n", (unsigned int)max_total_mem
);
4147 fprintf(stderr
, "max mmap regions = %10u\n", (unsigned int)max_n_mmaps
);
4148 fprintf(stderr
, "max mmap bytes = %10lu\n", max_mmapped_mem
);
4151 fprintf(stderr
, "heaps created = %10d\n", stat_n_heaps
);
4152 fprintf(stderr
, "locked directly = %10ld\n", stat_lock_direct
);
4153 fprintf(stderr
, "locked in loop = %10ld\n", stat_lock_loop
);
4154 fprintf(stderr
, "locked waiting = %10ld\n", stat_lock_wait
);
4155 fprintf(stderr
, "locked total = %10ld\n",
4156 stat_lock_direct
+ stat_lock_loop
+ stat_lock_wait
);
4161 mallinfo returns a copy of updated current mallinfo.
4162 The information reported is for the arena last used by the thread.
4165 struct mallinfo
mALLINFo()
4168 Void_t
*vptr
= NULL
;
4171 tsd_getspecific(arena_key
, vptr
);
4173 malloc_update_mallinfo((vptr
? (arena
*)vptr
: &main_arena
), &mi
);
4183 mallopt is the general SVID/XPG interface to tunable parameters.
4184 The format is to provide a (parameter-number, parameter-value) pair.
4185 mallopt then sets the corresponding parameter to the argument
4186 value if it can (i.e., so long as the value is meaningful),
4187 and returns 1 if successful else 0.
4189 See descriptions of tunable parameters above.
4194 int mALLOPt(int param_number
, int value
)
4196 int mALLOPt(param_number
, value
) int param_number
; int value
;
4199 switch(param_number
)
4201 case M_TRIM_THRESHOLD
:
4202 trim_threshold
= value
; return 1;
4204 top_pad
= value
; return 1;
4205 case M_MMAP_THRESHOLD
:
4207 /* Forbid setting the threshold too high. */
4208 if((unsigned long)value
> HEAP_MAX_SIZE
/2) return 0;
4210 mmap_threshold
= value
; return 1;
4213 n_mmaps_max
= value
; return 1;
4215 if (value
!= 0) return 0; else n_mmaps_max
= value
; return 1;
4217 case M_CHECK_ACTION
:
4218 check_action
= value
; return 1;
4227 /* Get/set state: malloc_get_state() records the current state of all
4228 malloc variables (_except_ for the actual heap contents and `hook'
4229 function pointers) in a system dependent, opaque data structure.
4230 This data structure is dynamically allocated and can be free()d
4231 after use. malloc_set_state() restores the state of all malloc
4232 variables to the previously obtained state. This is especially
4233 useful when using this malloc as part of a shared library, and when
4234 the heap contents are saved/restored via some other method. The
4235 primary example for this is GNU Emacs with its `dumping' procedure.
4236 `Hook' function pointers are never saved or restored by these
4237 functions, with two exceptions: If malloc checking was in use when
4238 malloc_get_state() was called, then malloc_set_state() calls
4239 __malloc_check_init() if possible; if malloc checking was not in
4240 use in the recorded state but the user requested malloc checking,
4241 then the hooks are reset to 0. */
4243 #define MALLOC_STATE_MAGIC 0x444c4541l
4244 #define MALLOC_STATE_VERSION (0*0x100l + 1l) /* major*0x100 + minor */
4246 struct malloc_state
{
4249 mbinptr av
[NAV
* 2 + 2];
4251 int sbrked_mem_bytes
;
4252 unsigned long trim_threshold
;
4253 unsigned long top_pad
;
4254 unsigned int n_mmaps_max
;
4255 unsigned long mmap_threshold
;
4257 unsigned long max_sbrked_mem
;
4258 unsigned long max_total_mem
;
4259 unsigned int n_mmaps
;
4260 unsigned int max_n_mmaps
;
4261 unsigned long mmapped_mem
;
4262 unsigned long max_mmapped_mem
;
4263 int using_malloc_checking
;
4269 struct malloc_state
* ms
;
4273 ms
= (struct malloc_state
*)mALLOc(sizeof(*ms
));
4276 (void)mutex_lock(&main_arena
.mutex
);
4277 ms
->magic
= MALLOC_STATE_MAGIC
;
4278 ms
->version
= MALLOC_STATE_VERSION
;
4279 ms
->av
[0] = main_arena
.av
[0];
4280 ms
->av
[1] = main_arena
.av
[1];
4281 for(i
=0; i
<NAV
; i
++) {
4282 b
= bin_at(&main_arena
, i
);
4284 ms
->av
[2*i
+2] = ms
->av
[2*i
+3] = 0; /* empty bin (or initial top) */
4286 ms
->av
[2*i
+2] = first(b
);
4287 ms
->av
[2*i
+3] = last(b
);
4290 ms
->sbrk_base
= sbrk_base
;
4291 ms
->sbrked_mem_bytes
= sbrked_mem
;
4292 ms
->trim_threshold
= trim_threshold
;
4293 ms
->top_pad
= top_pad
;
4294 ms
->n_mmaps_max
= n_mmaps_max
;
4295 ms
->mmap_threshold
= mmap_threshold
;
4296 ms
->check_action
= check_action
;
4297 ms
->max_sbrked_mem
= max_sbrked_mem
;
4299 ms
->max_total_mem
= max_total_mem
;
4301 ms
->max_total_mem
= 0;
4303 ms
->n_mmaps
= n_mmaps
;
4304 ms
->max_n_mmaps
= max_n_mmaps
;
4305 ms
->mmapped_mem
= mmapped_mem
;
4306 ms
->max_mmapped_mem
= max_mmapped_mem
;
4307 #if defined _LIBC || defined MALLOC_HOOKS
4308 ms
->using_malloc_checking
= using_malloc_checking
;
4310 ms
->using_malloc_checking
= 0;
4312 (void)mutex_unlock(&main_arena
.mutex
);
4318 mALLOC_SET_STATe(Void_t
* msptr
)
4320 mALLOC_SET_STATe(msptr
) Void_t
* msptr
;
4323 struct malloc_state
* ms
= (struct malloc_state
*)msptr
;
4327 #if defined _LIBC || defined MALLOC_HOOKS
4328 disallow_malloc_check
= 1;
4331 if(ms
->magic
!= MALLOC_STATE_MAGIC
) return -1;
4332 /* Must fail if the major version is too high. */
4333 if((ms
->version
& ~0xffl
) > (MALLOC_STATE_VERSION
& ~0xffl
)) return -2;
4334 (void)mutex_lock(&main_arena
.mutex
);
4335 main_arena
.av
[0] = ms
->av
[0];
4336 main_arena
.av
[1] = ms
->av
[1];
4337 for(i
=0; i
<NAV
; i
++) {
4338 b
= bin_at(&main_arena
, i
);
4339 if(ms
->av
[2*i
+2] == 0)
4340 first(b
) = last(b
) = b
;
4342 first(b
) = ms
->av
[2*i
+2];
4343 last(b
) = ms
->av
[2*i
+3];
4345 /* Make sure the links to the `av'-bins in the heap are correct. */
4351 sbrk_base
= ms
->sbrk_base
;
4352 sbrked_mem
= ms
->sbrked_mem_bytes
;
4353 trim_threshold
= ms
->trim_threshold
;
4354 top_pad
= ms
->top_pad
;
4355 n_mmaps_max
= ms
->n_mmaps_max
;
4356 mmap_threshold
= ms
->mmap_threshold
;
4357 check_action
= ms
->check_action
;
4358 max_sbrked_mem
= ms
->max_sbrked_mem
;
4360 max_total_mem
= ms
->max_total_mem
;
4362 n_mmaps
= ms
->n_mmaps
;
4363 max_n_mmaps
= ms
->max_n_mmaps
;
4364 mmapped_mem
= ms
->mmapped_mem
;
4365 max_mmapped_mem
= ms
->max_mmapped_mem
;
4366 /* add version-dependent code here */
4367 if (ms
->version
>= 1) {
4368 #if defined _LIBC || defined MALLOC_HOOKS
4369 /* Check whether it is safe to enable malloc checking, or whether
4370 it is necessary to disable it. */
4371 if (ms
->using_malloc_checking
&& !using_malloc_checking
&&
4372 !disallow_malloc_check
)
4373 __malloc_check_init ();
4374 else if (!ms
->using_malloc_checking
&& using_malloc_checking
) {
4378 __memalign_hook
= 0;
4379 using_malloc_checking
= 0;
4384 (void)mutex_unlock(&main_arena
.mutex
);
4390 #if defined _LIBC || defined MALLOC_HOOKS
4392 /* A simple, standard set of debugging hooks. Overhead is `only' one
4393 byte per chunk; still this will catch most cases of double frees or
4394 overruns. The goal here is to avoid obscure crashes due to invalid
4395 usage, unlike in the MALLOC_DEBUG code. */
4397 #define MAGICBYTE(p) ( ( ((size_t)p >> 3) ^ ((size_t)p >> 11)) & 0xFF )
4399 /* Instrument a chunk with overrun detector byte(s) and convert it
4400 into a user pointer with requested size sz. */
4405 chunk2mem_check(mchunkptr p
, size_t sz
)
4407 chunk2mem_check(p
, sz
) mchunkptr p
; size_t sz
;
4410 unsigned char* m_ptr
= (unsigned char*)BOUNDED_N(chunk2mem(p
), sz
);
4413 for(i
= chunksize(p
) - (chunk_is_mmapped(p
) ? 2*SIZE_SZ
+1 : SIZE_SZ
+1);
4417 m_ptr
[i
] = (unsigned char)(i
-sz
);
4422 m_ptr
[sz
] = MAGICBYTE(p
);
4423 return (Void_t
*)m_ptr
;
4426 /* Convert a pointer to be free()d or realloc()ed to a valid chunk
4427 pointer. If the provided pointer is not valid, return NULL. */
4432 mem2chunk_check(Void_t
* mem
)
4434 mem2chunk_check(mem
) Void_t
* mem
;
4438 INTERNAL_SIZE_T sz
, c
;
4439 unsigned char magic
;
4442 if(!aligned_OK(p
)) return NULL
;
4443 if( (char*)p
>=sbrk_base
&& (char*)p
<(sbrk_base
+sbrked_mem
) ) {
4444 /* Must be a chunk in conventional heap memory. */
4445 if(chunk_is_mmapped(p
) ||
4446 ( (sz
= chunksize(p
)), ((char*)p
+ sz
)>=(sbrk_base
+sbrked_mem
) ) ||
4447 sz
<MINSIZE
|| sz
&MALLOC_ALIGN_MASK
|| !inuse(p
) ||
4448 ( !prev_inuse(p
) && (p
->prev_size
&MALLOC_ALIGN_MASK
||
4449 (long)prev_chunk(p
)<(long)sbrk_base
||
4450 next_chunk(prev_chunk(p
))!=p
) ))
4452 magic
= MAGICBYTE(p
);
4453 for(sz
+= SIZE_SZ
-1; (c
= ((unsigned char*)p
)[sz
]) != magic
; sz
-= c
) {
4454 if(c
<=0 || sz
<(c
+2*SIZE_SZ
)) return NULL
;
4456 ((unsigned char*)p
)[sz
] ^= 0xFF;
4458 unsigned long offset
, page_mask
= malloc_getpagesize
-1;
4460 /* mmap()ed chunks have MALLOC_ALIGNMENT or higher power-of-two
4461 alignment relative to the beginning of a page. Check this
4463 offset
= (unsigned long)mem
& page_mask
;
4464 if((offset
!=MALLOC_ALIGNMENT
&& offset
!=0 && offset
!=0x10 &&
4465 offset
!=0x20 && offset
!=0x40 && offset
!=0x80 && offset
!=0x100 &&
4466 offset
!=0x200 && offset
!=0x400 && offset
!=0x800 && offset
!=0x1000 &&
4468 !chunk_is_mmapped(p
) || (p
->size
& PREV_INUSE
) ||
4469 ( (((unsigned long)p
- p
->prev_size
) & page_mask
) != 0 ) ||
4470 ( (sz
= chunksize(p
)), ((p
->prev_size
+ sz
) & page_mask
) != 0 ) )
4472 magic
= MAGICBYTE(p
);
4473 for(sz
-= 1; (c
= ((unsigned char*)p
)[sz
]) != magic
; sz
-= c
) {
4474 if(c
<=0 || sz
<(c
+2*SIZE_SZ
)) return NULL
;
4476 ((unsigned char*)p
)[sz
] ^= 0xFF;
4481 /* Check for corruption of the top chunk, and try to recover if
4492 mchunkptr t
= top(&main_arena
);
4493 char* brk
, * new_brk
;
4494 INTERNAL_SIZE_T front_misalign
, sbrk_size
;
4495 unsigned long pagesz
= malloc_getpagesize
;
4497 if((char*)t
+ chunksize(t
) == sbrk_base
+ sbrked_mem
||
4498 t
== initial_top(&main_arena
)) return 0;
4500 if(check_action
& 1)
4501 fprintf(stderr
, "malloc: top chunk is corrupt\n");
4502 if(check_action
& 2)
4505 /* Try to set up a new top chunk. */
4507 front_misalign
= (unsigned long)chunk2mem(brk
) & MALLOC_ALIGN_MASK
;
4508 if (front_misalign
> 0)
4509 front_misalign
= MALLOC_ALIGNMENT
- front_misalign
;
4510 sbrk_size
= front_misalign
+ top_pad
+ MINSIZE
;
4511 sbrk_size
+= pagesz
- ((unsigned long)(brk
+ sbrk_size
) & (pagesz
- 1));
4512 new_brk
= (char*)(MORECORE (sbrk_size
));
4513 if (new_brk
== (char*)(MORECORE_FAILURE
)) return -1;
4514 sbrked_mem
= (new_brk
- sbrk_base
) + sbrk_size
;
4516 top(&main_arena
) = (mchunkptr
)(brk
+ front_misalign
);
4517 set_head(top(&main_arena
), (sbrk_size
- front_misalign
) | PREV_INUSE
);
4524 malloc_check(size_t sz
, const Void_t
*caller
)
4526 malloc_check(sz
, caller
) size_t sz
; const Void_t
*caller
;
4532 if(request2size(sz
+1, nb
))
4534 (void)mutex_lock(&main_arena
.mutex
);
4535 victim
= (top_check() >= 0) ? chunk_alloc(&main_arena
, nb
) : NULL
;
4536 (void)mutex_unlock(&main_arena
.mutex
);
4537 if(!victim
) return NULL
;
4538 return chunk2mem_check(victim
, sz
);
4543 free_check(Void_t
* mem
, const Void_t
*caller
)
4545 free_check(mem
, caller
) Void_t
* mem
; const Void_t
*caller
;
4551 (void)mutex_lock(&main_arena
.mutex
);
4552 p
= mem2chunk_check(mem
);
4554 (void)mutex_unlock(&main_arena
.mutex
);
4555 if(check_action
& 1)
4556 fprintf(stderr
, "free(): invalid pointer %p!\n", mem
);
4557 if(check_action
& 2)
4562 if (chunk_is_mmapped(p
)) {
4563 (void)mutex_unlock(&main_arena
.mutex
);
4568 #if 0 /* Erase freed memory. */
4569 memset(mem
, 0, chunksize(p
) - (SIZE_SZ
+1));
4571 chunk_free(&main_arena
, p
);
4572 (void)mutex_unlock(&main_arena
.mutex
);
4577 realloc_check(Void_t
* oldmem
, size_t bytes
, const Void_t
*caller
)
4579 realloc_check(oldmem
, bytes
, caller
)
4580 Void_t
* oldmem
; size_t bytes
; const Void_t
*caller
;
4583 mchunkptr oldp
, newp
;
4584 INTERNAL_SIZE_T nb
, oldsize
;
4586 if (oldmem
== 0) return malloc_check(bytes
, NULL
);
4587 (void)mutex_lock(&main_arena
.mutex
);
4588 oldp
= mem2chunk_check(oldmem
);
4590 (void)mutex_unlock(&main_arena
.mutex
);
4591 if(check_action
& 1)
4592 fprintf(stderr
, "realloc(): invalid pointer %p!\n", oldmem
);
4593 if(check_action
& 2)
4595 return malloc_check(bytes
, NULL
);
4597 oldsize
= chunksize(oldp
);
4599 if(request2size(bytes
+1, nb
)) {
4600 (void)mutex_unlock(&main_arena
.mutex
);
4605 if (chunk_is_mmapped(oldp
)) {
4607 newp
= mremap_chunk(oldp
, nb
);
4610 /* Note the extra SIZE_SZ overhead. */
4611 if(oldsize
- SIZE_SZ
>= nb
) newp
= oldp
; /* do nothing */
4613 /* Must alloc, copy, free. */
4614 newp
= (top_check() >= 0) ? chunk_alloc(&main_arena
, nb
) : NULL
;
4616 MALLOC_COPY(BOUNDED_N(chunk2mem(newp
), nb
),
4617 oldmem
, oldsize
- 2*SIZE_SZ
, 0);
4625 #endif /* HAVE_MMAP */
4626 newp
= (top_check() >= 0) ?
4627 chunk_realloc(&main_arena
, oldp
, oldsize
, nb
) : NULL
;
4628 #if 0 /* Erase freed memory. */
4629 nb
= chunksize(newp
);
4630 if(oldp
<newp
|| oldp
>=chunk_at_offset(newp
, nb
)) {
4631 memset((char*)oldmem
+ 2*sizeof(mbinptr
), 0,
4632 oldsize
- (2*sizeof(mbinptr
)+2*SIZE_SZ
+1));
4633 } else if(nb
> oldsize
+SIZE_SZ
) {
4634 memset((char*)BOUNDED_N(chunk2mem(newp
), bytes
) + oldsize
,
4635 0, nb
- (oldsize
+SIZE_SZ
));
4641 (void)mutex_unlock(&main_arena
.mutex
);
4643 if(!newp
) return NULL
;
4644 return chunk2mem_check(newp
, bytes
);
4649 memalign_check(size_t alignment
, size_t bytes
, const Void_t
*caller
)
4651 memalign_check(alignment
, bytes
, caller
)
4652 size_t alignment
; size_t bytes
; const Void_t
*caller
;
4658 if (alignment
<= MALLOC_ALIGNMENT
) return malloc_check(bytes
, NULL
);
4659 if (alignment
< MINSIZE
) alignment
= MINSIZE
;
4661 if(request2size(bytes
+1, nb
))
4663 (void)mutex_lock(&main_arena
.mutex
);
4664 p
= (top_check() >= 0) ? chunk_align(&main_arena
, nb
, alignment
) : NULL
;
4665 (void)mutex_unlock(&main_arena
.mutex
);
4667 return chunk2mem_check(p
, bytes
);
4672 /* The following hooks are used when the global initialization in
4673 ptmalloc_init() hasn't completed yet. */
4677 malloc_starter(size_t sz
, const Void_t
*caller
)
4679 malloc_starter(sz
, caller
) size_t sz
; const Void_t
*caller
;
4685 if(request2size(sz
, nb
))
4687 victim
= chunk_alloc(&main_arena
, nb
);
4689 return victim
? BOUNDED_N(chunk2mem(victim
), sz
) : 0;
4694 free_starter(Void_t
* mem
, const Void_t
*caller
)
4696 free_starter(mem
, caller
) Void_t
* mem
; const Void_t
*caller
;
4704 if (chunk_is_mmapped(p
)) {
4709 chunk_free(&main_arena
, p
);
4712 /* The following hooks are used while the `atfork' handling mechanism
4717 malloc_atfork (size_t sz
, const Void_t
*caller
)
4719 malloc_atfork(sz
, caller
) size_t sz
; const Void_t
*caller
;
4722 Void_t
*vptr
= NULL
;
4726 tsd_getspecific(arena_key
, vptr
);
4728 if(save_malloc_hook
!= malloc_check
) {
4729 if(request2size(sz
, nb
))
4731 victim
= chunk_alloc(&main_arena
, nb
);
4732 return victim
? BOUNDED_N(chunk2mem(victim
), sz
) : 0;
4734 if(top_check()<0 || request2size(sz
+1, nb
))
4736 victim
= chunk_alloc(&main_arena
, nb
);
4737 return victim
? chunk2mem_check(victim
, sz
) : 0;
4740 /* Suspend the thread until the `atfork' handlers have completed.
4741 By that time, the hooks will have been reset as well, so that
4742 mALLOc() can be used again. */
4743 (void)mutex_lock(&list_lock
);
4744 (void)mutex_unlock(&list_lock
);
4751 free_atfork(Void_t
* mem
, const Void_t
*caller
)
4753 free_atfork(mem
, caller
) Void_t
* mem
; const Void_t
*caller
;
4756 Void_t
*vptr
= NULL
;
4758 mchunkptr p
; /* chunk corresponding to mem */
4760 if (mem
== 0) /* free(0) has no effect */
4763 p
= mem2chunk(mem
); /* do not bother to replicate free_check here */
4766 if (chunk_is_mmapped(p
)) /* release mmapped memory. */
4773 ar_ptr
= arena_for_ptr(p
);
4774 tsd_getspecific(arena_key
, vptr
);
4776 (void)mutex_lock(&ar_ptr
->mutex
);
4777 chunk_free(ar_ptr
, p
);
4779 (void)mutex_unlock(&ar_ptr
->mutex
);
4782 #endif /* !defined NO_THREADS */
4784 #endif /* defined _LIBC || defined MALLOC_HOOKS */
4789 /* We need a wrapper function for one of the additions of POSIX. */
4791 __posix_memalign (void **memptr
, size_t alignment
, size_t size
)
4795 /* Test whether the SIZE argument is valid. It must be a power of
4796 two multiple of sizeof (void *). */
4797 if (size
% sizeof (void *) != 0 || (size
& (size
- 1)) != 0)
4800 mem
= __libc_memalign (alignment
, size
);
4810 weak_alias (__posix_memalign
, posix_memalign
)
4812 weak_alias (__libc_calloc
, __calloc
) weak_alias (__libc_calloc
, calloc
)
4813 weak_alias (__libc_free
, __cfree
) weak_alias (__libc_free
, cfree
)
4814 weak_alias (__libc_free
, __free
) weak_alias (__libc_free
, free
)
4815 weak_alias (__libc_malloc
, __malloc
) weak_alias (__libc_malloc
, malloc
)
4816 weak_alias (__libc_memalign
, __memalign
) weak_alias (__libc_memalign
, memalign
)
4817 weak_alias (__libc_realloc
, __realloc
) weak_alias (__libc_realloc
, realloc
)
4818 weak_alias (__libc_valloc
, __valloc
) weak_alias (__libc_valloc
, valloc
)
4819 weak_alias (__libc_pvalloc
, __pvalloc
) weak_alias (__libc_pvalloc
, pvalloc
)
4820 weak_alias (__libc_mallinfo
, __mallinfo
) weak_alias (__libc_mallinfo
, mallinfo
)
4821 weak_alias (__libc_mallopt
, __mallopt
) weak_alias (__libc_mallopt
, mallopt
)
4823 weak_alias (__malloc_stats
, malloc_stats
)
4824 weak_alias (__malloc_usable_size
, malloc_usable_size
)
4825 weak_alias (__malloc_trim
, malloc_trim
)
4826 weak_alias (__malloc_get_state
, malloc_get_state
)
4827 weak_alias (__malloc_set_state
, malloc_set_state
)
4834 V2.6.4-pt3 Thu Feb 20 1997 Wolfram Gloger (wmglo@dent.med.uni-muenchen.de)
4835 * Added malloc_get/set_state() (mainly for use in GNU emacs),
4836 using interface from Marcus Daniels
4837 * All parameters are now adjustable via environment variables
4839 V2.6.4-pt2 Sat Dec 14 1996 Wolfram Gloger (wmglo@dent.med.uni-muenchen.de)
4840 * Added debugging hooks
4841 * Fixed possible deadlock in realloc() when out of memory
4842 * Don't pollute namespace in glibc: use __getpagesize, __mmap, etc.
4844 V2.6.4-pt Wed Dec 4 1996 Wolfram Gloger (wmglo@dent.med.uni-muenchen.de)
4845 * Very minor updates from the released 2.6.4 version.
4846 * Trimmed include file down to exported data structures.
4847 * Changes from H.J. Lu for glibc-2.0.
4849 V2.6.3i-pt Sep 16 1996 Wolfram Gloger (wmglo@dent.med.uni-muenchen.de)
4850 * Many changes for multiple threads
4851 * Introduced arenas and heaps
4853 V2.6.3 Sun May 19 08:17:58 1996 Doug Lea (dl at gee)
4854 * Added pvalloc, as recommended by H.J. Liu
4855 * Added 64bit pointer support mainly from Wolfram Gloger
4856 * Added anonymously donated WIN32 sbrk emulation
4857 * Malloc, calloc, getpagesize: add optimizations from Raymond Nijssen
4858 * malloc_extend_top: fix mask error that caused wastage after
4860 * Add linux mremap support code from HJ Liu
4862 V2.6.2 Tue Dec 5 06:52:55 1995 Doug Lea (dl at gee)
4863 * Integrated most documentation with the code.
4864 * Add support for mmap, with help from
4865 Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
4866 * Use last_remainder in more cases.
4867 * Pack bins using idea from colin@nyx10.cs.du.edu
4868 * Use ordered bins instead of best-fit threshold
4869 * Eliminate block-local decls to simplify tracing and debugging.
4870 * Support another case of realloc via move into top
4871 * Fix error occurring when initial sbrk_base not word-aligned.
4872 * Rely on page size for units instead of SBRK_UNIT to
4873 avoid surprises about sbrk alignment conventions.
4874 * Add mallinfo, mallopt. Thanks to Raymond Nijssen
4875 (raymond@es.ele.tue.nl) for the suggestion.
4876 * Add `pad' argument to malloc_trim and top_pad mallopt parameter.
4877 * More precautions for cases where other routines call sbrk,
4878 courtesy of Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
4879 * Added macros etc., allowing use in linux libc from
4880 H.J. Lu (hjl@gnu.ai.mit.edu)
4881 * Inverted this history list
4883 V2.6.1 Sat Dec 2 14:10:57 1995 Doug Lea (dl at gee)
4884 * Re-tuned and fixed to behave more nicely with V2.6.0 changes.
4885 * Removed all preallocation code since under current scheme
4886 the work required to undo bad preallocations exceeds
4887 the work saved in good cases for most test programs.
4888 * No longer use return list or unconsolidated bins since
4889 no scheme using them consistently outperforms those that don't
4890 given above changes.
4891 * Use best fit for very large chunks to prevent some worst-cases.
4892 * Added some support for debugging
4894 V2.6.0 Sat Nov 4 07:05:23 1995 Doug Lea (dl at gee)
4895 * Removed footers when chunks are in use. Thanks to
4896 Paul Wilson (wilson@cs.texas.edu) for the suggestion.
4898 V2.5.4 Wed Nov 1 07:54:51 1995 Doug Lea (dl at gee)
4899 * Added malloc_trim, with help from Wolfram Gloger
4900 (wmglo@Dent.MED.Uni-Muenchen.DE).
4902 V2.5.3 Tue Apr 26 10:16:01 1994 Doug Lea (dl at g)
4904 V2.5.2 Tue Apr 5 16:20:40 1994 Doug Lea (dl at g)
4905 * realloc: try to expand in both directions
4906 * malloc: swap order of clean-bin strategy;
4907 * realloc: only conditionally expand backwards
4908 * Try not to scavenge used bins
4909 * Use bin counts as a guide to preallocation
4910 * Occasionally bin return list chunks in first scan
4911 * Add a few optimizations from colin@nyx10.cs.du.edu
4913 V2.5.1 Sat Aug 14 15:40:43 1993 Doug Lea (dl at g)
4914 * faster bin computation & slightly different binning
4915 * merged all consolidations to one part of malloc proper
4916 (eliminating old malloc_find_space & malloc_clean_bin)
4917 * Scan 2 returns chunks (not just 1)
4918 * Propagate failure in realloc if malloc returns 0
4919 * Add stuff to allow compilation on non-ANSI compilers
4920 from kpv@research.att.com
4922 V2.5 Sat Aug 7 07:41:59 1993 Doug Lea (dl at g.oswego.edu)
4923 * removed potential for odd address access in prev_chunk
4924 * removed dependency on getpagesize.h
4925 * misc cosmetics and a bit more internal documentation
4926 * anticosmetics: mangled names in macros to evade debugger strangeness
4927 * tested on sparc, hp-700, dec-mips, rs6000
4928 with gcc & native cc (hp, dec only) allowing
4929 Detlefs & Zorn comparison study (in SIGPLAN Notices.)
4931 Trial version Fri Aug 28 13:14:29 1992 Doug Lea (dl at g.oswego.edu)
4932 * Based loosely on libg++-1.2X malloc. (It retains some of the overall
4933 structure of old version, but most details differ.)