1 /* Malloc implementation for multiple threads without lock contention.
2 Copyright (C) 1996-2006, 2007, 2008, 2009 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4 Contributed by Wolfram Gloger <wg@malloc.de>
5 and Doug Lea <dl@cs.oswego.edu>, 2001.
7 The GNU C Library is free software; you can redistribute it and/or
8 modify it under the terms of the GNU Lesser General Public License as
9 published by the Free Software Foundation; either version 2.1 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 Lesser General Public License for more details.
17 You should have received a copy of the GNU Lesser 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. */
23 This is a version (aka ptmalloc2) of malloc/free/realloc written by
24 Doug Lea and adapted to multiple threads/arenas by Wolfram Gloger.
26 There have been substantial changesmade after the integration into
27 glibc in all parts of the code. Do not look for much commonality
28 with the ptmalloc2 version.
30 * Version ptmalloc2-20011215
32 VERSION 2.7.0 Sun Mar 11 14:14:06 2001 Doug Lea (dl at gee)
36 In order to compile this implementation, a Makefile is provided with
37 the ptmalloc2 distribution, which has pre-defined targets for some
38 popular systems (e.g. "make posix" for Posix threads). All that is
39 typically required with regard to compiler flags is the selection of
40 the thread package via defining one out of USE_PTHREADS, USE_THR or
41 USE_SPROC. Check the thread-m.h file for what effects this has.
42 Many/most systems will additionally require USE_TSD_DATA_HACK to be
43 defined, so this is the default for "make posix".
45 * Why use this malloc?
47 This is not the fastest, most space-conserving, most portable, or
48 most tunable malloc ever written. However it is among the fastest
49 while also being among the most space-conserving, portable and tunable.
50 Consistent balance across these factors results in a good general-purpose
51 allocator for malloc-intensive programs.
53 The main properties of the algorithms are:
54 * For large (>= 512 bytes) requests, it is a pure best-fit allocator,
55 with ties normally decided via FIFO (i.e. least recently used).
56 * For small (<= 64 bytes by default) requests, it is a caching
57 allocator, that maintains pools of quickly recycled chunks.
58 * In between, and for combinations of large and small requests, it does
59 the best it can trying to meet both goals at once.
60 * For very large requests (>= 128KB by default), it relies on system
61 memory mapping facilities, if supported.
63 For a longer but slightly out of date high-level description, see
64 http://gee.cs.oswego.edu/dl/html/malloc.html
66 You may already by default be using a C library containing a malloc
67 that is based on some version of this malloc (for example in
68 linux). You might still want to use the one in this file in order to
69 customize settings or to avoid overheads associated with library
72 * Contents, described in more detail in "description of public routines" below.
74 Standard (ANSI/SVID/...) functions:
76 calloc(size_t n_elements, size_t element_size);
78 realloc(Void_t* p, size_t n);
79 memalign(size_t alignment, size_t n);
82 mallopt(int parameter_number, int parameter_value)
85 independent_calloc(size_t n_elements, size_t size, Void_t* chunks[]);
86 independent_comalloc(size_t n_elements, size_t sizes[], Void_t* chunks[]);
89 malloc_trim(size_t pad);
90 malloc_usable_size(Void_t* p);
95 Supported pointer representation: 4 or 8 bytes
96 Supported size_t representation: 4 or 8 bytes
97 Note that size_t is allowed to be 4 bytes even if pointers are 8.
98 You can adjust this by defining INTERNAL_SIZE_T
100 Alignment: 2 * sizeof(size_t) (default)
101 (i.e., 8 byte alignment with 4byte size_t). This suffices for
102 nearly all current machines and C compilers. However, you can
103 define MALLOC_ALIGNMENT to be wider than this if necessary.
105 Minimum overhead per allocated chunk: 4 or 8 bytes
106 Each malloced chunk has a hidden word of overhead holding size
107 and status information.
109 Minimum allocated size: 4-byte ptrs: 16 bytes (including 4 overhead)
110 8-byte ptrs: 24/32 bytes (including, 4/8 overhead)
112 When a chunk is freed, 12 (for 4byte ptrs) or 20 (for 8 byte
113 ptrs but 4 byte size) or 24 (for 8/8) additional bytes are
114 needed; 4 (8) for a trailing size field and 8 (16) bytes for
115 free list pointers. Thus, the minimum allocatable size is
118 Even a request for zero bytes (i.e., malloc(0)) returns a
119 pointer to something of the minimum allocatable size.
121 The maximum overhead wastage (i.e., number of extra bytes
122 allocated than were requested in malloc) is less than or equal
123 to the minimum size, except for requests >= mmap_threshold that
124 are serviced via mmap(), where the worst case wastage is 2 *
125 sizeof(size_t) bytes plus the remainder from a system page (the
126 minimal mmap unit); typically 4096 or 8192 bytes.
128 Maximum allocated size: 4-byte size_t: 2^32 minus about two pages
129 8-byte size_t: 2^64 minus about two pages
131 It is assumed that (possibly signed) size_t values suffice to
132 represent chunk sizes. `Possibly signed' is due to the fact
133 that `size_t' may be defined on a system as either a signed or
134 an unsigned type. The ISO C standard says that it must be
135 unsigned, but a few systems are known not to adhere to this.
136 Additionally, even when size_t is unsigned, sbrk (which is by
137 default used to obtain memory from system) accepts signed
138 arguments, and may not be able to handle size_t-wide arguments
139 with negative sign bit. Generally, values that would
140 appear as negative after accounting for overhead and alignment
141 are supported only via mmap(), which does not have this
144 Requests for sizes outside the allowed range will perform an optional
145 failure action and then return null. (Requests may also
146 also fail because a system is out of memory.)
148 Thread-safety: thread-safe unless NO_THREADS is defined
150 Compliance: I believe it is compliant with the 1997 Single Unix Specification
151 (See http://www.opennc.org). Also SVID/XPG, ANSI C, and probably
154 * Synopsis of compile-time options:
156 People have reported using previous versions of this malloc on all
157 versions of Unix, sometimes by tweaking some of the defines
158 below. It has been tested most extensively on Solaris and
159 Linux. It is also reported to work on WIN32 platforms.
160 People also report using it in stand-alone embedded systems.
162 The implementation is in straight, hand-tuned ANSI C. It is not
163 at all modular. (Sorry!) It uses a lot of macros. To be at all
164 usable, this code should be compiled using an optimizing compiler
165 (for example gcc -O3) that can simplify expressions and control
166 paths. (FAQ: some macros import variables as arguments rather than
167 declare locals because people reported that some debuggers
168 otherwise get confused.)
172 Compilation Environment options:
174 __STD_C derived from C compiler defines
177 USE_MEMCPY 1 if HAVE_MEMCPY is defined
178 HAVE_MMAP defined as 1
180 HAVE_MREMAP 0 unless linux defined
181 USE_ARENAS the same as HAVE_MMAP
182 malloc_getpagesize derived from system #includes, or 4096 if not
183 HAVE_USR_INCLUDE_MALLOC_H NOT defined
184 LACKS_UNISTD_H NOT defined unless WIN32
185 LACKS_SYS_PARAM_H NOT defined unless WIN32
186 LACKS_SYS_MMAN_H NOT defined unless WIN32
188 Changing default word sizes:
190 INTERNAL_SIZE_T size_t
191 MALLOC_ALIGNMENT MAX (2 * sizeof(INTERNAL_SIZE_T),
192 __alignof__ (long double))
194 Configuration and functionality options:
196 USE_DL_PREFIX NOT defined
197 USE_PUBLIC_MALLOC_WRAPPERS NOT defined
198 USE_MALLOC_LOCK NOT defined
199 MALLOC_DEBUG NOT defined
200 REALLOC_ZERO_BYTES_FREES 1
201 MALLOC_FAILURE_ACTION errno = ENOMEM, if __STD_C defined, else no-op
204 Options for customizing MORECORE:
208 MORECORE_CONTIGUOUS 1
209 MORECORE_CANNOT_TRIM NOT defined
211 MMAP_AS_MORECORE_SIZE (1024 * 1024)
213 Tuning options that are also dynamically changeable via mallopt:
215 DEFAULT_MXFAST 64 (for 32bit), 128 (for 64bit)
216 DEFAULT_TRIM_THRESHOLD 128 * 1024
218 DEFAULT_MMAP_THRESHOLD 128 * 1024
219 DEFAULT_MMAP_MAX 65536
221 There are several other #defined constants and macros that you
222 probably don't want to touch unless you are extending or adapting malloc. */
225 __STD_C should be nonzero if using ANSI-standard C compiler, a C++
226 compiler, or a C compiler sufficiently close to ANSI to get away
231 #if defined(__STDC__) || defined(__cplusplus)
240 Void_t* is the pointer type that malloc should say it returns
244 #if (__STD_C || defined(WIN32))
252 #include <stddef.h> /* for size_t */
253 #include <stdlib.h> /* for getenv(), abort() */
255 #include <sys/types.h>
258 #include <malloc-machine.h>
261 #ifdef ATOMIC_FASTBINS
264 #include <stdio-common/_itoa.h>
265 #include <bits/wordsize.h>
266 #include <sys/sysinfo.h>
273 /* define LACKS_UNISTD_H if your system does not have a <unistd.h>. */
275 /* #define LACKS_UNISTD_H */
277 #ifndef LACKS_UNISTD_H
281 /* define LACKS_SYS_PARAM_H if your system does not have a <sys/param.h>. */
283 /* #define LACKS_SYS_PARAM_H */
286 #include <stdio.h> /* needed for malloc_stats */
287 #include <errno.h> /* needed for optional MALLOC_FAILURE_ACTION */
292 /* For va_arg, va_start, va_end. */
295 /* For writev and struct iovec. */
298 #include <sys/syslog.h>
300 /* For various dynamic linking things. */
307 Because freed chunks may be overwritten with bookkeeping fields, this
308 malloc will often die when freed memory is overwritten by user
309 programs. This can be very effective (albeit in an annoying way)
310 in helping track down dangling pointers.
312 If you compile with -DMALLOC_DEBUG, a number of assertion checks are
313 enabled that will catch more memory errors. You probably won't be
314 able to make much sense of the actual assertion errors, but they
315 should help you locate incorrectly overwritten memory. The checking
316 is fairly extensive, and will slow down execution
317 noticeably. Calling malloc_stats or mallinfo with MALLOC_DEBUG set
318 will attempt to check every non-mmapped allocated and free chunk in
319 the course of computing the summmaries. (By nature, mmapped regions
320 cannot be checked very much automatically.)
322 Setting MALLOC_DEBUG may also be helpful if you are trying to modify
323 this code. The assertions in the check routines spell out in more
324 detail the assumptions and invariants underlying the algorithms.
326 Setting MALLOC_DEBUG does NOT provide an automated mechanism for
327 checking that all accesses to malloced memory stay within their
328 bounds. However, there are several add-ons and adaptations of this
329 or other mallocs available that do this.
336 INTERNAL_SIZE_T is the word-size used for internal bookkeeping
339 The default version is the same as size_t.
341 While not strictly necessary, it is best to define this as an
342 unsigned type, even if size_t is a signed type. This may avoid some
343 artificial size limitations on some systems.
345 On a 64-bit machine, you may be able to reduce malloc overhead by
346 defining INTERNAL_SIZE_T to be a 32 bit `unsigned int' at the
347 expense of not being able to handle more than 2^32 of malloced
348 space. If this limitation is acceptable, you are encouraged to set
349 this unless you are on a platform requiring 16byte alignments. In
350 this case the alignment requirements turn out to negate any
351 potential advantages of decreasing size_t word size.
353 Implementors: Beware of the possible combinations of:
354 - INTERNAL_SIZE_T might be signed or unsigned, might be 32 or 64 bits,
355 and might be the same width as int or as long
356 - size_t might have different width and signedness as INTERNAL_SIZE_T
357 - int and long might be 32 or 64 bits, and might be the same width
358 To deal with this, most comparisons and difference computations
359 among INTERNAL_SIZE_Ts should cast them to unsigned long, being
360 aware of the fact that casting an unsigned int to a wider long does
361 not sign-extend. (This also makes checking for negative numbers
362 awkward.) Some of these casts result in harmless compiler warnings
366 #ifndef INTERNAL_SIZE_T
367 #define INTERNAL_SIZE_T size_t
370 /* The corresponding word size */
371 #define SIZE_SZ (sizeof(INTERNAL_SIZE_T))
375 MALLOC_ALIGNMENT is the minimum alignment for malloc'ed chunks.
376 It must be a power of two at least 2 * SIZE_SZ, even on machines
377 for which smaller alignments would suffice. It may be defined as
378 larger than this though. Note however that code and data structures
379 are optimized for the case of 8-byte alignment.
383 #ifndef MALLOC_ALIGNMENT
384 /* XXX This is the correct definition. It differs from 2*SIZE_SZ only on
385 powerpc32. For the time being, changing this is causing more
386 compatibility problems due to malloc_get_state/malloc_set_state than
387 will returning blocks not adequately aligned for long double objects
388 under -mlong-double-128.
390 #define MALLOC_ALIGNMENT (2 * SIZE_SZ < __alignof__ (long double) \
391 ? __alignof__ (long double) : 2 * SIZE_SZ)
393 #define MALLOC_ALIGNMENT (2 * SIZE_SZ)
396 /* The corresponding bit mask value */
397 #define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1)
402 REALLOC_ZERO_BYTES_FREES should be set if a call to
403 realloc with zero bytes should be the same as a call to free.
404 This is required by the C standard. Otherwise, since this malloc
405 returns a unique pointer for malloc(0), so does realloc(p, 0).
408 #ifndef REALLOC_ZERO_BYTES_FREES
409 #define REALLOC_ZERO_BYTES_FREES 1
413 TRIM_FASTBINS controls whether free() of a very small chunk can
414 immediately lead to trimming. Setting to true (1) can reduce memory
415 footprint, but will almost always slow down programs that use a lot
418 Define this only if you are willing to give up some speed to more
419 aggressively reduce system-level memory footprint when releasing
420 memory in programs that use many small chunks. You can get
421 essentially the same effect by setting MXFAST to 0, but this can
422 lead to even greater slowdowns in programs using many small chunks.
423 TRIM_FASTBINS is an in-between compile-time option, that disables
424 only those chunks bordering topmost memory from being placed in
428 #ifndef TRIM_FASTBINS
429 #define TRIM_FASTBINS 0
434 USE_DL_PREFIX will prefix all public routines with the string 'dl'.
435 This is necessary when you only want to use this malloc in one part
436 of a program, using your regular system malloc elsewhere.
439 /* #define USE_DL_PREFIX */
443 Two-phase name translation.
444 All of the actual routines are given mangled names.
445 When wrappers are used, they become the public callable versions.
446 When DL_PREFIX is used, the callable names are prefixed.
450 #define public_cALLOc dlcalloc
451 #define public_fREe dlfree
452 #define public_cFREe dlcfree
453 #define public_mALLOc dlmalloc
454 #define public_mEMALIGn dlmemalign
455 #define public_rEALLOc dlrealloc
456 #define public_vALLOc dlvalloc
457 #define public_pVALLOc dlpvalloc
458 #define public_mALLINFo dlmallinfo
459 #define public_mALLOPt dlmallopt
460 #define public_mTRIm dlmalloc_trim
461 #define public_mSTATs dlmalloc_stats
462 #define public_mUSABLe dlmalloc_usable_size
463 #define public_iCALLOc dlindependent_calloc
464 #define public_iCOMALLOc dlindependent_comalloc
465 #define public_gET_STATe dlget_state
466 #define public_sET_STATe dlset_state
467 #else /* USE_DL_PREFIX */
470 /* Special defines for the GNU C library. */
471 #define public_cALLOc __libc_calloc
472 #define public_fREe __libc_free
473 #define public_cFREe __libc_cfree
474 #define public_mALLOc __libc_malloc
475 #define public_mEMALIGn __libc_memalign
476 #define public_rEALLOc __libc_realloc
477 #define public_vALLOc __libc_valloc
478 #define public_pVALLOc __libc_pvalloc
479 #define public_mALLINFo __libc_mallinfo
480 #define public_mALLOPt __libc_mallopt
481 #define public_mTRIm __malloc_trim
482 #define public_mSTATs __malloc_stats
483 #define public_mUSABLe __malloc_usable_size
484 #define public_iCALLOc __libc_independent_calloc
485 #define public_iCOMALLOc __libc_independent_comalloc
486 #define public_gET_STATe __malloc_get_state
487 #define public_sET_STATe __malloc_set_state
488 #define malloc_getpagesize __getpagesize()
491 #define munmap __munmap
492 #define mremap __mremap
493 #define mprotect __mprotect
494 #define MORECORE (*__morecore)
495 #define MORECORE_FAILURE 0
497 Void_t
* __default_morecore (ptrdiff_t);
498 Void_t
*(*__morecore
)(ptrdiff_t) = __default_morecore
;
501 #define public_cALLOc calloc
502 #define public_fREe free
503 #define public_cFREe cfree
504 #define public_mALLOc malloc
505 #define public_mEMALIGn memalign
506 #define public_rEALLOc realloc
507 #define public_vALLOc valloc
508 #define public_pVALLOc pvalloc
509 #define public_mALLINFo mallinfo
510 #define public_mALLOPt mallopt
511 #define public_mTRIm malloc_trim
512 #define public_mSTATs malloc_stats
513 #define public_mUSABLe malloc_usable_size
514 #define public_iCALLOc independent_calloc
515 #define public_iCOMALLOc independent_comalloc
516 #define public_gET_STATe malloc_get_state
517 #define public_sET_STATe malloc_set_state
519 #endif /* USE_DL_PREFIX */
522 #define __builtin_expect(expr, val) (expr)
524 #define fwrite(buf, size, count, fp) _IO_fwrite (buf, size, count, fp)
528 HAVE_MEMCPY should be defined if you are not otherwise using
529 ANSI STD C, but still have memcpy and memset in your C library
530 and want to use them in calloc and realloc. Otherwise simple
531 macro versions are defined below.
533 USE_MEMCPY should be defined as 1 if you actually want to
534 have memset and memcpy called. People report that the macro
535 versions are faster than libc versions on some systems.
537 Even if USE_MEMCPY is set to 1, loops to copy/clear small chunks
538 (of <= 36 bytes) are manually unrolled in realloc and calloc.
552 #if (__STD_C || defined(HAVE_MEMCPY))
558 /* On Win32 memset and memcpy are already declared in windows.h */
561 void* memset(void*, int, size_t);
562 void* memcpy(void*, const void*, size_t);
572 /* Force a value to be in a register and stop the compiler referring
573 to the source (mostly memory location) again. */
574 #define force_reg(val) \
575 ({ __typeof (val) _v; asm ("" : "=r" (_v) : "0" (val)); _v; })
579 MALLOC_FAILURE_ACTION is the action to take before "return 0" when
580 malloc fails to be able to return memory, either because memory is
581 exhausted or because of illegal arguments.
583 By default, sets errno if running on STD_C platform, else does nothing.
586 #ifndef MALLOC_FAILURE_ACTION
588 #define MALLOC_FAILURE_ACTION \
592 #define MALLOC_FAILURE_ACTION
597 MORECORE-related declarations. By default, rely on sbrk
601 #ifdef LACKS_UNISTD_H
602 #if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)
604 extern Void_t
* sbrk(ptrdiff_t);
606 extern Void_t
* sbrk();
612 MORECORE is the name of the routine to call to obtain more memory
613 from the system. See below for general guidance on writing
614 alternative MORECORE functions, as well as a version for WIN32 and a
615 sample version for pre-OSX macos.
619 #define MORECORE sbrk
623 MORECORE_FAILURE is the value returned upon failure of MORECORE
624 as well as mmap. Since it cannot be an otherwise valid memory address,
625 and must reflect values of standard sys calls, you probably ought not
629 #ifndef MORECORE_FAILURE
630 #define MORECORE_FAILURE (-1)
634 If MORECORE_CONTIGUOUS is true, take advantage of fact that
635 consecutive calls to MORECORE with positive arguments always return
636 contiguous increasing addresses. This is true of unix sbrk. Even
637 if not defined, when regions happen to be contiguous, malloc will
638 permit allocations spanning regions obtained from different
639 calls. But defining this when applicable enables some stronger
640 consistency checks and space efficiencies.
643 #ifndef MORECORE_CONTIGUOUS
644 #define MORECORE_CONTIGUOUS 1
648 Define MORECORE_CANNOT_TRIM if your version of MORECORE
649 cannot release space back to the system when given negative
650 arguments. This is generally necessary only if you are using
651 a hand-crafted MORECORE function that cannot handle negative arguments.
654 /* #define MORECORE_CANNOT_TRIM */
656 /* MORECORE_CLEARS (default 1)
657 The degree to which the routine mapped to MORECORE zeroes out
658 memory: never (0), only for newly allocated space (1) or always
659 (2). The distinction between (1) and (2) is necessary because on
660 some systems, if the application first decrements and then
661 increments the break value, the contents of the reallocated space
665 #ifndef MORECORE_CLEARS
666 #define MORECORE_CLEARS 1
671 Define HAVE_MMAP as true to optionally make malloc() use mmap() to
672 allocate very large blocks. These will be returned to the
673 operating system immediately after a free(). Also, if mmap
674 is available, it is used as a backup strategy in cases where
675 MORECORE fails to provide space from system.
677 This malloc is best tuned to work with mmap for large requests.
678 If you do not have mmap, operations involving very large chunks (1MB
679 or so) may be slower than you'd like.
686 Standard unix mmap using /dev/zero clears memory so calloc doesn't
691 #define MMAP_CLEARS 1
696 #define MMAP_CLEARS 0
702 MMAP_AS_MORECORE_SIZE is the minimum mmap size argument to use if
703 sbrk fails, and mmap is used as a backup (which is done only if
704 HAVE_MMAP). The value must be a multiple of page size. This
705 backup strategy generally applies only when systems have "holes" in
706 address space, so sbrk cannot perform contiguous expansion, but
707 there is still space available on system. On systems for which
708 this is known to be useful (i.e. most linux kernels), this occurs
709 only when programs allocate huge amounts of memory. Between this,
710 and the fact that mmap regions tend to be limited, the size should
711 be large, to avoid too many mmap calls and thus avoid running out
715 #ifndef MMAP_AS_MORECORE_SIZE
716 #define MMAP_AS_MORECORE_SIZE (1024 * 1024)
720 Define HAVE_MREMAP to make realloc() use mremap() to re-allocate
721 large blocks. This is currently only possible on Linux with
722 kernel versions newer than 1.3.77.
727 #define HAVE_MREMAP 1
729 #define HAVE_MREMAP 0
732 #endif /* HAVE_MMAP */
734 /* Define USE_ARENAS to enable support for multiple `arenas'. These
735 are allocated using mmap(), are necessary for threads and
736 occasionally useful to overcome address space limitations affecting
740 #define USE_ARENAS HAVE_MMAP
745 The system page size. To the extent possible, this malloc manages
746 memory from the system in page-size units. Note that this value is
747 cached during initialization into a field of malloc_state. So even
748 if malloc_getpagesize is a function, it is only called once.
750 The following mechanics for getpagesize were adapted from bsd/gnu
751 getpagesize.h. If none of the system-probes here apply, a value of
752 4096 is used, which should be OK: If they don't apply, then using
753 the actual value probably doesn't impact performance.
757 #ifndef malloc_getpagesize
759 #ifndef LACKS_UNISTD_H
763 # ifdef _SC_PAGESIZE /* some SVR4 systems omit an underscore */
764 # ifndef _SC_PAGE_SIZE
765 # define _SC_PAGE_SIZE _SC_PAGESIZE
769 # ifdef _SC_PAGE_SIZE
770 # define malloc_getpagesize sysconf(_SC_PAGE_SIZE)
772 # if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE)
773 extern size_t getpagesize();
774 # define malloc_getpagesize getpagesize()
776 # ifdef WIN32 /* use supplied emulation of getpagesize */
777 # define malloc_getpagesize getpagesize()
779 # ifndef LACKS_SYS_PARAM_H
780 # include <sys/param.h>
782 # ifdef EXEC_PAGESIZE
783 # define malloc_getpagesize EXEC_PAGESIZE
787 # define malloc_getpagesize NBPG
789 # define malloc_getpagesize (NBPG * CLSIZE)
793 # define malloc_getpagesize NBPC
796 # define malloc_getpagesize PAGESIZE
797 # else /* just guess */
798 # define malloc_getpagesize (4096)
809 This version of malloc supports the standard SVID/XPG mallinfo
810 routine that returns a struct containing usage properties and
811 statistics. It should work on any SVID/XPG compliant system that has
812 a /usr/include/malloc.h defining struct mallinfo. (If you'd like to
813 install such a thing yourself, cut out the preliminary declarations
814 as described above and below and save them in a malloc.h file. But
815 there's no compelling reason to bother to do this.)
817 The main declaration needed is the mallinfo struct that is returned
818 (by-copy) by mallinfo(). The SVID/XPG malloinfo struct contains a
819 bunch of fields that are not even meaningful in this version of
820 malloc. These fields are are instead filled by mallinfo() with
821 other numbers that might be of interest.
823 HAVE_USR_INCLUDE_MALLOC_H should be set if you have a
824 /usr/include/malloc.h file that includes a declaration of struct
825 mallinfo. If so, it is included; else an SVID2/XPG2 compliant
826 version is declared below. These must be precisely the same for
827 mallinfo() to work. The original SVID version of this struct,
828 defined on most systems with mallinfo, declares all fields as
829 ints. But some others define as unsigned long. If your system
830 defines the fields using a type of different width than listed here,
831 you must #include your system version and #define
832 HAVE_USR_INCLUDE_MALLOC_H.
835 /* #define HAVE_USR_INCLUDE_MALLOC_H */
837 #ifdef HAVE_USR_INCLUDE_MALLOC_H
838 #include "/usr/include/malloc.h"
842 /* ---------- description of public routines ------------ */
846 Returns a pointer to a newly allocated chunk of at least n bytes, or null
847 if no space is available. Additionally, on failure, errno is
848 set to ENOMEM on ANSI C systems.
850 If n is zero, malloc returns a minumum-sized chunk. (The minimum
851 size is 16 bytes on most 32bit systems, and 24 or 32 bytes on 64bit
852 systems.) On most systems, size_t is an unsigned type, so calls
853 with negative arguments are interpreted as requests for huge amounts
854 of space, which will often fail. The maximum supported value of n
855 differs across systems, but is in all cases less than the maximum
856 representable value of a size_t.
859 Void_t
* public_mALLOc(size_t);
861 Void_t
* public_mALLOc();
863 #ifdef libc_hidden_proto
864 libc_hidden_proto (public_mALLOc
)
869 Releases the chunk of memory pointed to by p, that had been previously
870 allocated using malloc or a related routine such as realloc.
871 It has no effect if p is null. It can have arbitrary (i.e., bad!)
872 effects if p has already been freed.
874 Unless disabled (using mallopt), freeing very large spaces will
875 when possible, automatically trigger operations that give
876 back unused memory to the system, thus reducing program footprint.
879 void public_fREe(Void_t
*);
883 #ifdef libc_hidden_proto
884 libc_hidden_proto (public_fREe
)
888 calloc(size_t n_elements, size_t element_size);
889 Returns a pointer to n_elements * element_size bytes, with all locations
893 Void_t
* public_cALLOc(size_t, size_t);
895 Void_t
* public_cALLOc();
899 realloc(Void_t* p, size_t n)
900 Returns a pointer to a chunk of size n that contains the same data
901 as does chunk p up to the minimum of (n, p's size) bytes, or null
902 if no space is available.
904 The returned pointer may or may not be the same as p. The algorithm
905 prefers extending p when possible, otherwise it employs the
906 equivalent of a malloc-copy-free sequence.
908 If p is null, realloc is equivalent to malloc.
910 If space is not available, realloc returns null, errno is set (if on
911 ANSI) and p is NOT freed.
913 if n is for fewer bytes than already held by p, the newly unused
914 space is lopped off and freed if possible. Unless the #define
915 REALLOC_ZERO_BYTES_FREES is set, realloc with a size argument of
916 zero (re)allocates a minimum-sized chunk.
918 Large chunks that were internally obtained via mmap will always
919 be reallocated using malloc-copy-free sequences unless
920 the system supports MREMAP (currently only linux).
922 The old unix realloc convention of allowing the last-free'd chunk
923 to be used as an argument to realloc is not supported.
926 Void_t
* public_rEALLOc(Void_t
*, size_t);
928 Void_t
* public_rEALLOc();
930 #ifdef libc_hidden_proto
931 libc_hidden_proto (public_rEALLOc
)
935 memalign(size_t alignment, size_t n);
936 Returns a pointer to a newly allocated chunk of n bytes, aligned
937 in accord with the alignment argument.
939 The alignment argument should be a power of two. If the argument is
940 not a power of two, the nearest greater power is used.
941 8-byte alignment is guaranteed by normal malloc calls, so don't
942 bother calling memalign with an argument of 8 or less.
944 Overreliance on memalign is a sure way to fragment space.
947 Void_t
* public_mEMALIGn(size_t, size_t);
949 Void_t
* public_mEMALIGn();
951 #ifdef libc_hidden_proto
952 libc_hidden_proto (public_mEMALIGn
)
957 Equivalent to memalign(pagesize, n), where pagesize is the page
958 size of the system. If the pagesize is unknown, 4096 is used.
961 Void_t
* public_vALLOc(size_t);
963 Void_t
* public_vALLOc();
969 mallopt(int parameter_number, int parameter_value)
970 Sets tunable parameters The format is to provide a
971 (parameter-number, parameter-value) pair. mallopt then sets the
972 corresponding parameter to the argument value if it can (i.e., so
973 long as the value is meaningful), and returns 1 if successful else
974 0. SVID/XPG/ANSI defines four standard param numbers for mallopt,
975 normally defined in malloc.h. Only one of these (M_MXFAST) is used
976 in this malloc. The others (M_NLBLKS, M_GRAIN, M_KEEP) don't apply,
977 so setting them has no effect. But this malloc also supports four
978 other options in mallopt. See below for details. Briefly, supported
979 parameters are as follows (listed defaults are for "typical"
982 Symbol param # default allowed param values
983 M_MXFAST 1 64 0-80 (0 disables fastbins)
984 M_TRIM_THRESHOLD -1 128*1024 any (-1U disables trimming)
986 M_MMAP_THRESHOLD -3 128*1024 any (or 0 if no MMAP support)
987 M_MMAP_MAX -4 65536 any (0 disables use of mmap)
990 int public_mALLOPt(int, int);
992 int public_mALLOPt();
998 Returns (by copy) a struct containing various summary statistics:
1000 arena: current total non-mmapped bytes allocated from system
1001 ordblks: the number of free chunks
1002 smblks: the number of fastbin blocks (i.e., small chunks that
1003 have been freed but not use resused or consolidated)
1004 hblks: current number of mmapped regions
1005 hblkhd: total bytes held in mmapped regions
1006 usmblks: the maximum total allocated space. This will be greater
1007 than current total if trimming has occurred.
1008 fsmblks: total bytes held in fastbin blocks
1009 uordblks: current total allocated space (normal or mmapped)
1010 fordblks: total free space
1011 keepcost: the maximum number of bytes that could ideally be released
1012 back to system via malloc_trim. ("ideally" means that
1013 it ignores page restrictions etc.)
1015 Because these fields are ints, but internal bookkeeping may
1016 be kept as longs, the reported values may wrap around zero and
1020 struct mallinfo
public_mALLINFo(void);
1022 struct mallinfo
public_mALLINFo();
1027 independent_calloc(size_t n_elements, size_t element_size, Void_t* chunks[]);
1029 independent_calloc is similar to calloc, but instead of returning a
1030 single cleared space, it returns an array of pointers to n_elements
1031 independent elements that can hold contents of size elem_size, each
1032 of which starts out cleared, and can be independently freed,
1033 realloc'ed etc. The elements are guaranteed to be adjacently
1034 allocated (this is not guaranteed to occur with multiple callocs or
1035 mallocs), which may also improve cache locality in some
1038 The "chunks" argument is optional (i.e., may be null, which is
1039 probably the most typical usage). If it is null, the returned array
1040 is itself dynamically allocated and should also be freed when it is
1041 no longer needed. Otherwise, the chunks array must be of at least
1042 n_elements in length. It is filled in with the pointers to the
1045 In either case, independent_calloc returns this pointer array, or
1046 null if the allocation failed. If n_elements is zero and "chunks"
1047 is null, it returns a chunk representing an array with zero elements
1048 (which should be freed if not wanted).
1050 Each element must be individually freed when it is no longer
1051 needed. If you'd like to instead be able to free all at once, you
1052 should instead use regular calloc and assign pointers into this
1053 space to represent elements. (In this case though, you cannot
1054 independently free elements.)
1056 independent_calloc simplifies and speeds up implementations of many
1057 kinds of pools. It may also be useful when constructing large data
1058 structures that initially have a fixed number of fixed-sized nodes,
1059 but the number is not known at compile time, and some of the nodes
1060 may later need to be freed. For example:
1062 struct Node { int item; struct Node* next; };
1064 struct Node* build_list() {
1066 int n = read_number_of_nodes_needed();
1067 if (n <= 0) return 0;
1068 pool = (struct Node**)(independent_calloc(n, sizeof(struct Node), 0);
1069 if (pool == 0) die();
1070 // organize into a linked list...
1071 struct Node* first = pool[0];
1072 for (i = 0; i < n-1; ++i)
1073 pool[i]->next = pool[i+1];
1074 free(pool); // Can now free the array (or not, if it is needed later)
1079 Void_t
** public_iCALLOc(size_t, size_t, Void_t
**);
1081 Void_t
** public_iCALLOc();
1085 independent_comalloc(size_t n_elements, size_t sizes[], Void_t* chunks[]);
1087 independent_comalloc allocates, all at once, a set of n_elements
1088 chunks with sizes indicated in the "sizes" array. It returns
1089 an array of pointers to these elements, each of which can be
1090 independently freed, realloc'ed etc. The elements are guaranteed to
1091 be adjacently allocated (this is not guaranteed to occur with
1092 multiple callocs or mallocs), which may also improve cache locality
1093 in some applications.
1095 The "chunks" argument is optional (i.e., may be null). If it is null
1096 the returned array is itself dynamically allocated and should also
1097 be freed when it is no longer needed. Otherwise, the chunks array
1098 must be of at least n_elements in length. It is filled in with the
1099 pointers to the chunks.
1101 In either case, independent_comalloc returns this pointer array, or
1102 null if the allocation failed. If n_elements is zero and chunks is
1103 null, it returns a chunk representing an array with zero elements
1104 (which should be freed if not wanted).
1106 Each element must be individually freed when it is no longer
1107 needed. If you'd like to instead be able to free all at once, you
1108 should instead use a single regular malloc, and assign pointers at
1109 particular offsets in the aggregate space. (In this case though, you
1110 cannot independently free elements.)
1112 independent_comallac differs from independent_calloc in that each
1113 element may have a different size, and also that it does not
1114 automatically clear elements.
1116 independent_comalloc can be used to speed up allocation in cases
1117 where several structs or objects must always be allocated at the
1118 same time. For example:
1123 void send_message(char* msg) {
1124 int msglen = strlen(msg);
1125 size_t sizes[3] = { sizeof(struct Head), msglen, sizeof(struct Foot) };
1127 if (independent_comalloc(3, sizes, chunks) == 0)
1129 struct Head* head = (struct Head*)(chunks[0]);
1130 char* body = (char*)(chunks[1]);
1131 struct Foot* foot = (struct Foot*)(chunks[2]);
1135 In general though, independent_comalloc is worth using only for
1136 larger values of n_elements. For small values, you probably won't
1137 detect enough difference from series of malloc calls to bother.
1139 Overuse of independent_comalloc can increase overall memory usage,
1140 since it cannot reuse existing noncontiguous small chunks that
1141 might be available for some of the elements.
1144 Void_t
** public_iCOMALLOc(size_t, size_t*, Void_t
**);
1146 Void_t
** public_iCOMALLOc();
1154 Equivalent to valloc(minimum-page-that-holds(n)), that is,
1155 round up n to nearest pagesize.
1158 Void_t
* public_pVALLOc(size_t);
1160 Void_t
* public_pVALLOc();
1165 Equivalent to free(p).
1167 cfree is needed/defined on some systems that pair it with calloc,
1168 for odd historical reasons (such as: cfree is used in example
1169 code in the first edition of K&R).
1172 void public_cFREe(Void_t
*);
1174 void public_cFREe();
1178 malloc_trim(size_t pad);
1180 If possible, gives memory back to the system (via negative
1181 arguments to sbrk) if there is unused memory at the `high' end of
1182 the malloc pool. You can call this after freeing large blocks of
1183 memory to potentially reduce the system-level memory requirements
1184 of a program. However, it cannot guarantee to reduce memory. Under
1185 some allocation patterns, some large free blocks of memory will be
1186 locked between two used chunks, so they cannot be given back to
1189 The `pad' argument to malloc_trim represents the amount of free
1190 trailing space to leave untrimmed. If this argument is zero,
1191 only the minimum amount of memory to maintain internal data
1192 structures will be left (one page or less). Non-zero arguments
1193 can be supplied to maintain enough trailing space to service
1194 future expected allocations without having to re-obtain memory
1197 Malloc_trim returns 1 if it actually released any memory, else 0.
1198 On systems that do not support "negative sbrks", it will always
1202 int public_mTRIm(size_t);
1208 malloc_usable_size(Void_t* p);
1210 Returns the number of bytes you can actually use in
1211 an allocated chunk, which may be more than you requested (although
1212 often not) due to alignment and minimum size constraints.
1213 You can use this many bytes without worrying about
1214 overwriting other allocated objects. This is not a particularly great
1215 programming practice. malloc_usable_size can be more useful in
1216 debugging and assertions, for example:
1219 assert(malloc_usable_size(p) >= 256);
1223 size_t public_mUSABLe(Void_t
*);
1225 size_t public_mUSABLe();
1230 Prints on stderr the amount of space obtained from the system (both
1231 via sbrk and mmap), the maximum amount (which may be more than
1232 current if malloc_trim and/or munmap got called), and the current
1233 number of bytes allocated via malloc (or realloc, etc) but not yet
1234 freed. Note that this is the number of bytes allocated, not the
1235 number requested. It will be larger than the number requested
1236 because of alignment and bookkeeping overhead. Because it includes
1237 alignment wastage as being in use, this figure may be greater than
1238 zero even when no user-level chunks are allocated.
1240 The reported current and maximum system memory can be inaccurate if
1241 a program makes other calls to system memory allocation functions
1242 (normally sbrk) outside of malloc.
1244 malloc_stats prints only the most commonly interesting statistics.
1245 More information can be obtained by calling mallinfo.
1249 void public_mSTATs(void);
1251 void public_mSTATs();
1255 malloc_get_state(void);
1257 Returns the state of all malloc variables in an opaque data
1261 Void_t
* public_gET_STATe(void);
1263 Void_t
* public_gET_STATe();
1267 malloc_set_state(Void_t* state);
1269 Restore the state of all malloc variables from data obtained with
1273 int public_sET_STATe(Void_t
*);
1275 int public_sET_STATe();
1280 posix_memalign(void **memptr, size_t alignment, size_t size);
1282 POSIX wrapper like memalign(), checking for validity of size.
1284 int __posix_memalign(void **, size_t, size_t);
1287 /* mallopt tuning options */
1290 M_MXFAST is the maximum request size used for "fastbins", special bins
1291 that hold returned chunks without consolidating their spaces. This
1292 enables future requests for chunks of the same size to be handled
1293 very quickly, but can increase fragmentation, and thus increase the
1294 overall memory footprint of a program.
1296 This malloc manages fastbins very conservatively yet still
1297 efficiently, so fragmentation is rarely a problem for values less
1298 than or equal to the default. The maximum supported value of MXFAST
1299 is 80. You wouldn't want it any higher than this anyway. Fastbins
1300 are designed especially for use with many small structs, objects or
1301 strings -- the default handles structs/objects/arrays with sizes up
1302 to 8 4byte fields, or small strings representing words, tokens,
1303 etc. Using fastbins for larger objects normally worsens
1304 fragmentation without improving speed.
1306 M_MXFAST is set in REQUEST size units. It is internally used in
1307 chunksize units, which adds padding and alignment. You can reduce
1308 M_MXFAST to 0 to disable all use of fastbins. This causes the malloc
1309 algorithm to be a closer approximation of fifo-best-fit in all cases,
1310 not just for larger requests, but will generally cause it to be
1315 /* M_MXFAST is a standard SVID/XPG tuning option, usually listed in malloc.h */
1320 #ifndef DEFAULT_MXFAST
1321 #define DEFAULT_MXFAST (64 * SIZE_SZ / 4)
1326 M_TRIM_THRESHOLD is the maximum amount of unused top-most memory
1327 to keep before releasing via malloc_trim in free().
1329 Automatic trimming is mainly useful in long-lived programs.
1330 Because trimming via sbrk can be slow on some systems, and can
1331 sometimes be wasteful (in cases where programs immediately
1332 afterward allocate more large chunks) the value should be high
1333 enough so that your overall system performance would improve by
1334 releasing this much memory.
1336 The trim threshold and the mmap control parameters (see below)
1337 can be traded off with one another. Trimming and mmapping are
1338 two different ways of releasing unused memory back to the
1339 system. Between these two, it is often possible to keep
1340 system-level demands of a long-lived program down to a bare
1341 minimum. For example, in one test suite of sessions measuring
1342 the XF86 X server on Linux, using a trim threshold of 128K and a
1343 mmap threshold of 192K led to near-minimal long term resource
1346 If you are using this malloc in a long-lived program, it should
1347 pay to experiment with these values. As a rough guide, you
1348 might set to a value close to the average size of a process
1349 (program) running on your system. Releasing this much memory
1350 would allow such a process to run in memory. Generally, it's
1351 worth it to tune for trimming rather tham memory mapping when a
1352 program undergoes phases where several large chunks are
1353 allocated and released in ways that can reuse each other's
1354 storage, perhaps mixed with phases where there are no such
1355 chunks at all. And in well-behaved long-lived programs,
1356 controlling release of large blocks via trimming versus mapping
1359 However, in most programs, these parameters serve mainly as
1360 protection against the system-level effects of carrying around
1361 massive amounts of unneeded memory. Since frequent calls to
1362 sbrk, mmap, and munmap otherwise degrade performance, the default
1363 parameters are set to relatively high values that serve only as
1366 The trim value It must be greater than page size to have any useful
1367 effect. To disable trimming completely, you can set to
1370 Trim settings interact with fastbin (MXFAST) settings: Unless
1371 TRIM_FASTBINS is defined, automatic trimming never takes place upon
1372 freeing a chunk with size less than or equal to MXFAST. Trimming is
1373 instead delayed until subsequent freeing of larger chunks. However,
1374 you can still force an attempted trim by calling malloc_trim.
1376 Also, trimming is not generally possible in cases where
1377 the main arena is obtained via mmap.
1379 Note that the trick some people use of mallocing a huge space and
1380 then freeing it at program startup, in an attempt to reserve system
1381 memory, doesn't have the intended effect under automatic trimming,
1382 since that memory will immediately be returned to the system.
1385 #define M_TRIM_THRESHOLD -1
1387 #ifndef DEFAULT_TRIM_THRESHOLD
1388 #define DEFAULT_TRIM_THRESHOLD (128 * 1024)
1392 M_TOP_PAD is the amount of extra `padding' space to allocate or
1393 retain whenever sbrk is called. It is used in two ways internally:
1395 * When sbrk is called to extend the top of the arena to satisfy
1396 a new malloc request, this much padding is added to the sbrk
1399 * When malloc_trim is called automatically from free(),
1400 it is used as the `pad' argument.
1402 In both cases, the actual amount of padding is rounded
1403 so that the end of the arena is always a system page boundary.
1405 The main reason for using padding is to avoid calling sbrk so
1406 often. Having even a small pad greatly reduces the likelihood
1407 that nearly every malloc request during program start-up (or
1408 after trimming) will invoke sbrk, which needlessly wastes
1411 Automatic rounding-up to page-size units is normally sufficient
1412 to avoid measurable overhead, so the default is 0. However, in
1413 systems where sbrk is relatively slow, it can pay to increase
1414 this value, at the expense of carrying around more memory than
1418 #define M_TOP_PAD -2
1420 #ifndef DEFAULT_TOP_PAD
1421 #define DEFAULT_TOP_PAD (0)
1425 MMAP_THRESHOLD_MAX and _MIN are the bounds on the dynamically
1426 adjusted MMAP_THRESHOLD.
1429 #ifndef DEFAULT_MMAP_THRESHOLD_MIN
1430 #define DEFAULT_MMAP_THRESHOLD_MIN (128 * 1024)
1433 #ifndef DEFAULT_MMAP_THRESHOLD_MAX
1434 /* For 32-bit platforms we cannot increase the maximum mmap
1435 threshold much because it is also the minimum value for the
1436 maximum heap size and its alignment. Going above 512k (i.e., 1M
1437 for new heaps) wastes too much address space. */
1438 # if __WORDSIZE == 32
1439 # define DEFAULT_MMAP_THRESHOLD_MAX (512 * 1024)
1441 # define DEFAULT_MMAP_THRESHOLD_MAX (4 * 1024 * 1024 * sizeof(long))
1446 M_MMAP_THRESHOLD is the request size threshold for using mmap()
1447 to service a request. Requests of at least this size that cannot
1448 be allocated using already-existing space will be serviced via mmap.
1449 (If enough normal freed space already exists it is used instead.)
1451 Using mmap segregates relatively large chunks of memory so that
1452 they can be individually obtained and released from the host
1453 system. A request serviced through mmap is never reused by any
1454 other request (at least not directly; the system may just so
1455 happen to remap successive requests to the same locations).
1457 Segregating space in this way has the benefits that:
1459 1. Mmapped space can ALWAYS be individually released back
1460 to the system, which helps keep the system level memory
1461 demands of a long-lived program low.
1462 2. Mapped memory can never become `locked' between
1463 other chunks, as can happen with normally allocated chunks, which
1464 means that even trimming via malloc_trim would not release them.
1465 3. On some systems with "holes" in address spaces, mmap can obtain
1466 memory that sbrk cannot.
1468 However, it has the disadvantages that:
1470 1. The space cannot be reclaimed, consolidated, and then
1471 used to service later requests, as happens with normal chunks.
1472 2. It can lead to more wastage because of mmap page alignment
1474 3. It causes malloc performance to be more dependent on host
1475 system memory management support routines which may vary in
1476 implementation quality and may impose arbitrary
1477 limitations. Generally, servicing a request via normal
1478 malloc steps is faster than going through a system's mmap.
1480 The advantages of mmap nearly always outweigh disadvantages for
1481 "large" chunks, but the value of "large" varies across systems. The
1482 default is an empirically derived value that works well in most
1487 The above was written in 2001. Since then the world has changed a lot.
1488 Memory got bigger. Applications got bigger. The virtual address space
1489 layout in 32 bit linux changed.
1491 In the new situation, brk() and mmap space is shared and there are no
1492 artificial limits on brk size imposed by the kernel. What is more,
1493 applications have started using transient allocations larger than the
1494 128Kb as was imagined in 2001.
1496 The price for mmap is also high now; each time glibc mmaps from the
1497 kernel, the kernel is forced to zero out the memory it gives to the
1498 application. Zeroing memory is expensive and eats a lot of cache and
1499 memory bandwidth. This has nothing to do with the efficiency of the
1500 virtual memory system, by doing mmap the kernel just has no choice but
1503 In 2001, the kernel had a maximum size for brk() which was about 800
1504 megabytes on 32 bit x86, at that point brk() would hit the first
1505 mmaped shared libaries and couldn't expand anymore. With current 2.6
1506 kernels, the VA space layout is different and brk() and mmap
1507 both can span the entire heap at will.
1509 Rather than using a static threshold for the brk/mmap tradeoff,
1510 we are now using a simple dynamic one. The goal is still to avoid
1511 fragmentation. The old goals we kept are
1512 1) try to get the long lived large allocations to use mmap()
1513 2) really large allocations should always use mmap()
1514 and we're adding now:
1515 3) transient allocations should use brk() to avoid forcing the kernel
1516 having to zero memory over and over again
1518 The implementation works with a sliding threshold, which is by default
1519 limited to go between 128Kb and 32Mb (64Mb for 64 bitmachines) and starts
1520 out at 128Kb as per the 2001 default.
1522 This allows us to satisfy requirement 1) under the assumption that long
1523 lived allocations are made early in the process' lifespan, before it has
1524 started doing dynamic allocations of the same size (which will
1525 increase the threshold).
1527 The upperbound on the threshold satisfies requirement 2)
1529 The threshold goes up in value when the application frees memory that was
1530 allocated with the mmap allocator. The idea is that once the application
1531 starts freeing memory of a certain size, it's highly probable that this is
1532 a size the application uses for transient allocations. This estimator
1533 is there to satisfy the new third requirement.
1537 #define M_MMAP_THRESHOLD -3
1539 #ifndef DEFAULT_MMAP_THRESHOLD
1540 #define DEFAULT_MMAP_THRESHOLD DEFAULT_MMAP_THRESHOLD_MIN
1544 M_MMAP_MAX is the maximum number of requests to simultaneously
1545 service using mmap. This parameter exists because
1546 some systems have a limited number of internal tables for
1547 use by mmap, and using more than a few of them may degrade
1550 The default is set to a value that serves only as a safeguard.
1551 Setting to 0 disables use of mmap for servicing large requests. If
1552 HAVE_MMAP is not set, the default value is 0, and attempts to set it
1553 to non-zero values in mallopt will fail.
1556 #define M_MMAP_MAX -4
1558 #ifndef DEFAULT_MMAP_MAX
1560 #define DEFAULT_MMAP_MAX (65536)
1562 #define DEFAULT_MMAP_MAX (0)
1567 } /* end of extern "C" */
1573 #define BOUNDED_N(ptr, sz) (ptr)
1575 #ifndef RETURN_ADDRESS
1576 #define RETURN_ADDRESS(X_) (NULL)
1579 /* On some platforms we can compile internal, not exported functions better.
1580 Let the environment provide a macro and define it to be empty if it
1581 is not available. */
1582 #ifndef internal_function
1583 # define internal_function
1586 /* Forward declarations. */
1587 struct malloc_chunk
;
1588 typedef struct malloc_chunk
* mchunkptr
;
1590 /* Internal routines. */
1594 static Void_t
* _int_malloc(mstate
, size_t);
1595 #ifdef ATOMIC_FASTBINS
1596 static void _int_free(mstate
, mchunkptr
, int);
1598 static void _int_free(mstate
, mchunkptr
);
1600 static Void_t
* _int_realloc(mstate
, mchunkptr
, INTERNAL_SIZE_T
,
1602 static Void_t
* _int_memalign(mstate
, size_t, size_t);
1603 static Void_t
* _int_valloc(mstate
, size_t);
1604 static Void_t
* _int_pvalloc(mstate
, size_t);
1605 /*static Void_t* cALLOc(size_t, size_t);*/
1607 static Void_t
** _int_icalloc(mstate
, size_t, size_t, Void_t
**);
1608 static Void_t
** _int_icomalloc(mstate
, size_t, size_t*, Void_t
**);
1610 static int mTRIm(mstate
, size_t);
1611 static size_t mUSABLe(Void_t
*);
1612 static void mSTATs(void);
1613 static int mALLOPt(int, int);
1614 static struct mallinfo
mALLINFo(mstate
);
1615 static void malloc_printerr(int action
, const char *str
, void *ptr
);
1617 static Void_t
* internal_function
mem2mem_check(Void_t
*p
, size_t sz
);
1618 static int internal_function
top_check(void);
1619 static void internal_function
munmap_chunk(mchunkptr p
);
1621 static mchunkptr internal_function
mremap_chunk(mchunkptr p
, size_t new_size
);
1624 static Void_t
* malloc_check(size_t sz
, const Void_t
*caller
);
1625 static void free_check(Void_t
* mem
, const Void_t
*caller
);
1626 static Void_t
* realloc_check(Void_t
* oldmem
, size_t bytes
,
1627 const Void_t
*caller
);
1628 static Void_t
* memalign_check(size_t alignment
, size_t bytes
,
1629 const Void_t
*caller
);
1632 # if USE___THREAD || !defined SHARED
1633 /* These routines are never needed in this configuration. */
1640 static Void_t
* malloc_starter(size_t sz
, const Void_t
*caller
);
1641 static Void_t
* memalign_starter(size_t aln
, size_t sz
, const Void_t
*caller
);
1642 static void free_starter(Void_t
* mem
, const Void_t
*caller
);
1644 static Void_t
* malloc_atfork(size_t sz
, const Void_t
*caller
);
1645 static void free_atfork(Void_t
* mem
, const Void_t
*caller
);
1650 static Void_t
* _int_malloc();
1651 static void _int_free();
1652 static Void_t
* _int_realloc();
1653 static Void_t
* _int_memalign();
1654 static Void_t
* _int_valloc();
1655 static Void_t
* _int_pvalloc();
1656 /*static Void_t* cALLOc();*/
1657 static Void_t
** _int_icalloc();
1658 static Void_t
** _int_icomalloc();
1660 static size_t mUSABLe();
1661 static void mSTATs();
1662 static int mALLOPt();
1663 static struct mallinfo
mALLINFo();
1670 /* ------------- Optional versions of memcopy ---------------- */
1676 Note: memcpy is ONLY invoked with non-overlapping regions,
1677 so the (usually slower) memmove is not needed.
1680 #define MALLOC_COPY(dest, src, nbytes) memcpy(dest, src, nbytes)
1681 #define MALLOC_ZERO(dest, nbytes) memset(dest, 0, nbytes)
1683 #else /* !USE_MEMCPY */
1685 /* Use Duff's device for good zeroing/copying performance. */
1687 #define MALLOC_ZERO(charp, nbytes) \
1689 INTERNAL_SIZE_T* mzp = (INTERNAL_SIZE_T*)(charp); \
1690 unsigned long mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T); \
1692 if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; } \
1694 case 0: for(;;) { *mzp++ = 0; \
1695 case 7: *mzp++ = 0; \
1696 case 6: *mzp++ = 0; \
1697 case 5: *mzp++ = 0; \
1698 case 4: *mzp++ = 0; \
1699 case 3: *mzp++ = 0; \
1700 case 2: *mzp++ = 0; \
1701 case 1: *mzp++ = 0; if(mcn <= 0) break; mcn--; } \
1705 #define MALLOC_COPY(dest,src,nbytes) \
1707 INTERNAL_SIZE_T* mcsrc = (INTERNAL_SIZE_T*) src; \
1708 INTERNAL_SIZE_T* mcdst = (INTERNAL_SIZE_T*) dest; \
1709 unsigned long mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T); \
1711 if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; } \
1713 case 0: for(;;) { *mcdst++ = *mcsrc++; \
1714 case 7: *mcdst++ = *mcsrc++; \
1715 case 6: *mcdst++ = *mcsrc++; \
1716 case 5: *mcdst++ = *mcsrc++; \
1717 case 4: *mcdst++ = *mcsrc++; \
1718 case 3: *mcdst++ = *mcsrc++; \
1719 case 2: *mcdst++ = *mcsrc++; \
1720 case 1: *mcdst++ = *mcsrc++; if(mcn <= 0) break; mcn--; } \
1726 /* ------------------ MMAP support ------------------ */
1732 #ifndef LACKS_SYS_MMAN_H
1733 #include <sys/mman.h>
1736 #if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
1737 # define MAP_ANONYMOUS MAP_ANON
1739 #if !defined(MAP_FAILED)
1740 # define MAP_FAILED ((char*)-1)
1743 #ifndef MAP_NORESERVE
1744 # ifdef MAP_AUTORESRV
1745 # define MAP_NORESERVE MAP_AUTORESRV
1747 # define MAP_NORESERVE 0
1752 Nearly all versions of mmap support MAP_ANONYMOUS,
1753 so the following is unlikely to be needed, but is
1754 supplied just in case.
1757 #ifndef MAP_ANONYMOUS
1759 static int dev_zero_fd
= -1; /* Cached file descriptor for /dev/zero. */
1761 #define MMAP(addr, size, prot, flags) ((dev_zero_fd < 0) ? \
1762 (dev_zero_fd = open("/dev/zero", O_RDWR), \
1763 mmap((addr), (size), (prot), (flags), dev_zero_fd, 0)) : \
1764 mmap((addr), (size), (prot), (flags), dev_zero_fd, 0))
1768 #define MMAP(addr, size, prot, flags) \
1769 (mmap((addr), (size), (prot), (flags)|MAP_ANONYMOUS, -1, 0))
1774 #endif /* HAVE_MMAP */
1778 ----------------------- Chunk representations -----------------------
1783 This struct declaration is misleading (but accurate and necessary).
1784 It declares a "view" into memory allowing access to necessary
1785 fields at known offsets from a given base. See explanation below.
1788 struct malloc_chunk
{
1790 INTERNAL_SIZE_T prev_size
; /* Size of previous chunk (if free). */
1791 INTERNAL_SIZE_T size
; /* Size in bytes, including overhead. */
1793 struct malloc_chunk
* fd
; /* double links -- used only if free. */
1794 struct malloc_chunk
* bk
;
1796 /* Only used for large blocks: pointer to next larger size. */
1797 struct malloc_chunk
* fd_nextsize
; /* double links -- used only if free. */
1798 struct malloc_chunk
* bk_nextsize
;
1803 malloc_chunk details:
1805 (The following includes lightly edited explanations by Colin Plumb.)
1807 Chunks of memory are maintained using a `boundary tag' method as
1808 described in e.g., Knuth or Standish. (See the paper by Paul
1809 Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a
1810 survey of such techniques.) Sizes of free chunks are stored both
1811 in the front of each chunk and at the end. This makes
1812 consolidating fragmented chunks into bigger chunks very fast. The
1813 size fields also hold bits representing whether chunks are free or
1816 An allocated chunk looks like this:
1819 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1820 | Size of previous chunk, if allocated | |
1821 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1822 | Size of chunk, in bytes |M|P|
1823 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1824 | User data starts here... .
1826 . (malloc_usable_size() bytes) .
1828 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1830 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1833 Where "chunk" is the front of the chunk for the purpose of most of
1834 the malloc code, but "mem" is the pointer that is returned to the
1835 user. "Nextchunk" is the beginning of the next contiguous chunk.
1837 Chunks always begin on even word boundries, so the mem portion
1838 (which is returned to the user) is also on an even word boundary, and
1839 thus at least double-word aligned.
1841 Free chunks are stored in circular doubly-linked lists, and look like this:
1843 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1844 | Size of previous chunk |
1845 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1846 `head:' | Size of chunk, in bytes |P|
1847 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1848 | Forward pointer to next chunk in list |
1849 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1850 | Back pointer to previous chunk in list |
1851 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1852 | Unused space (may be 0 bytes long) .
1855 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1856 `foot:' | Size of chunk, in bytes |
1857 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1859 The P (PREV_INUSE) bit, stored in the unused low-order bit of the
1860 chunk size (which is always a multiple of two words), is an in-use
1861 bit for the *previous* chunk. If that bit is *clear*, then the
1862 word before the current chunk size contains the previous chunk
1863 size, and can be used to find the front of the previous chunk.
1864 The very first chunk allocated always has this bit set,
1865 preventing access to non-existent (or non-owned) memory. If
1866 prev_inuse is set for any given chunk, then you CANNOT determine
1867 the size of the previous chunk, and might even get a memory
1868 addressing fault when trying to do so.
1870 Note that the `foot' of the current chunk is actually represented
1871 as the prev_size of the NEXT chunk. This makes it easier to
1872 deal with alignments etc but can be very confusing when trying
1873 to extend or adapt this code.
1875 The two exceptions to all this are
1877 1. The special chunk `top' doesn't bother using the
1878 trailing size field since there is no next contiguous chunk
1879 that would have to index off it. After initialization, `top'
1880 is forced to always exist. If it would become less than
1881 MINSIZE bytes long, it is replenished.
1883 2. Chunks allocated via mmap, which have the second-lowest-order
1884 bit M (IS_MMAPPED) set in their size fields. Because they are
1885 allocated one-by-one, each must contain its own trailing size field.
1890 ---------- Size and alignment checks and conversions ----------
1893 /* conversion from malloc headers to user pointers, and back */
1895 #define chunk2mem(p) ((Void_t*)((char*)(p) + 2*SIZE_SZ))
1896 #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))
1898 /* The smallest possible chunk */
1899 #define MIN_CHUNK_SIZE (offsetof(struct malloc_chunk, fd_nextsize))
1901 /* The smallest size we can malloc is an aligned minimal chunk */
1904 (unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))
1906 /* Check if m has acceptable alignment */
1908 #define aligned_OK(m) (((unsigned long)(m) & MALLOC_ALIGN_MASK) == 0)
1910 #define misaligned_chunk(p) \
1911 ((uintptr_t)(MALLOC_ALIGNMENT == 2 * SIZE_SZ ? (p) : chunk2mem (p)) \
1912 & MALLOC_ALIGN_MASK)
1916 Check if a request is so large that it would wrap around zero when
1917 padded and aligned. To simplify some other code, the bound is made
1918 low enough so that adding MINSIZE will also not wrap around zero.
1921 #define REQUEST_OUT_OF_RANGE(req) \
1922 ((unsigned long)(req) >= \
1923 (unsigned long)(INTERNAL_SIZE_T)(-2 * MINSIZE))
1925 /* pad request bytes into a usable size -- internal version */
1927 #define request2size(req) \
1928 (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ? \
1930 ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
1932 /* Same, except also perform argument check */
1934 #define checked_request2size(req, sz) \
1935 if (REQUEST_OUT_OF_RANGE(req)) { \
1936 MALLOC_FAILURE_ACTION; \
1939 (sz) = request2size(req);
1942 --------------- Physical chunk operations ---------------
1946 /* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
1947 #define PREV_INUSE 0x1
1949 /* extract inuse bit of previous chunk */
1950 #define prev_inuse(p) ((p)->size & PREV_INUSE)
1953 /* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */
1954 #define IS_MMAPPED 0x2
1956 /* check for mmap()'ed chunk */
1957 #define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)
1960 /* size field is or'ed with NON_MAIN_ARENA if the chunk was obtained
1961 from a non-main arena. This is only set immediately before handing
1962 the chunk to the user, if necessary. */
1963 #define NON_MAIN_ARENA 0x4
1965 /* check for chunk from non-main arena */
1966 #define chunk_non_main_arena(p) ((p)->size & NON_MAIN_ARENA)
1970 Bits to mask off when extracting size
1972 Note: IS_MMAPPED is intentionally not masked off from size field in
1973 macros for which mmapped chunks should never be seen. This should
1974 cause helpful core dumps to occur if it is tried by accident by
1975 people extending or adapting this malloc.
1977 #define SIZE_BITS (PREV_INUSE|IS_MMAPPED|NON_MAIN_ARENA)
1979 /* Get size, ignoring use bits */
1980 #define chunksize(p) ((p)->size & ~(SIZE_BITS))
1983 /* Ptr to next physical malloc_chunk. */
1984 #define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->size & ~SIZE_BITS) ))
1986 /* Ptr to previous physical malloc_chunk */
1987 #define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_size) ))
1989 /* Treat space at ptr + offset as a chunk */
1990 #define chunk_at_offset(p, s) ((mchunkptr)(((char*)(p)) + (s)))
1992 /* extract p's inuse bit */
1994 ((((mchunkptr)(((char*)(p))+((p)->size & ~SIZE_BITS)))->size) & PREV_INUSE)
1996 /* set/clear chunk as being inuse without otherwise disturbing */
1997 #define set_inuse(p)\
1998 ((mchunkptr)(((char*)(p)) + ((p)->size & ~SIZE_BITS)))->size |= PREV_INUSE
2000 #define clear_inuse(p)\
2001 ((mchunkptr)(((char*)(p)) + ((p)->size & ~SIZE_BITS)))->size &= ~(PREV_INUSE)
2004 /* check/set/clear inuse bits in known places */
2005 #define inuse_bit_at_offset(p, s)\
2006 (((mchunkptr)(((char*)(p)) + (s)))->size & PREV_INUSE)
2008 #define set_inuse_bit_at_offset(p, s)\
2009 (((mchunkptr)(((char*)(p)) + (s)))->size |= PREV_INUSE)
2011 #define clear_inuse_bit_at_offset(p, s)\
2012 (((mchunkptr)(((char*)(p)) + (s)))->size &= ~(PREV_INUSE))
2015 /* Set size at head, without disturbing its use bit */
2016 #define set_head_size(p, s) ((p)->size = (((p)->size & SIZE_BITS) | (s)))
2018 /* Set size/use field */
2019 #define set_head(p, s) ((p)->size = (s))
2021 /* Set size at footer (only when chunk is not in use) */
2022 #define set_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_size = (s))
2026 -------------------- Internal data structures --------------------
2028 All internal state is held in an instance of malloc_state defined
2029 below. There are no other static variables, except in two optional
2031 * If USE_MALLOC_LOCK is defined, the mALLOC_MUTEx declared above.
2032 * If HAVE_MMAP is true, but mmap doesn't support
2033 MAP_ANONYMOUS, a dummy file descriptor for mmap.
2035 Beware of lots of tricks that minimize the total bookkeeping space
2036 requirements. The result is a little over 1K bytes (for 4byte
2037 pointers and size_t.)
2043 An array of bin headers for free chunks. Each bin is doubly
2044 linked. The bins are approximately proportionally (log) spaced.
2045 There are a lot of these bins (128). This may look excessive, but
2046 works very well in practice. Most bins hold sizes that are
2047 unusual as malloc request sizes, but are more usual for fragments
2048 and consolidated sets of chunks, which is what these bins hold, so
2049 they can be found quickly. All procedures maintain the invariant
2050 that no consolidated chunk physically borders another one, so each
2051 chunk in a list is known to be preceeded and followed by either
2052 inuse chunks or the ends of memory.
2054 Chunks in bins are kept in size order, with ties going to the
2055 approximately least recently used chunk. Ordering isn't needed
2056 for the small bins, which all contain the same-sized chunks, but
2057 facilitates best-fit allocation for larger chunks. These lists
2058 are just sequential. Keeping them in order almost never requires
2059 enough traversal to warrant using fancier ordered data
2062 Chunks of the same size are linked with the most
2063 recently freed at the front, and allocations are taken from the
2064 back. This results in LRU (FIFO) allocation order, which tends
2065 to give each chunk an equal opportunity to be consolidated with
2066 adjacent freed chunks, resulting in larger free chunks and less
2069 To simplify use in double-linked lists, each bin header acts
2070 as a malloc_chunk. This avoids special-casing for headers.
2071 But to conserve space and improve locality, we allocate
2072 only the fd/bk pointers of bins, and then use repositioning tricks
2073 to treat these as the fields of a malloc_chunk*.
2076 typedef struct malloc_chunk
* mbinptr
;
2078 /* addressing -- note that bin_at(0) does not exist */
2079 #define bin_at(m, i) \
2080 (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2])) \
2081 - offsetof (struct malloc_chunk, fd))
2083 /* analog of ++bin */
2084 #define next_bin(b) ((mbinptr)((char*)(b) + (sizeof(mchunkptr)<<1)))
2086 /* Reminders about list directionality within bins */
2087 #define first(b) ((b)->fd)
2088 #define last(b) ((b)->bk)
2090 /* Take a chunk off a bin list */
2091 #define unlink(P, BK, FD) { \
2094 if (__builtin_expect (FD->bk != P || BK->fd != P, 0)) \
2095 malloc_printerr (check_action, "corrupted double-linked list", P); \
2099 if (!in_smallbin_range (P->size) \
2100 && __builtin_expect (P->fd_nextsize != NULL, 0)) { \
2101 assert (P->fd_nextsize->bk_nextsize == P); \
2102 assert (P->bk_nextsize->fd_nextsize == P); \
2103 if (FD->fd_nextsize == NULL) { \
2104 if (P->fd_nextsize == P) \
2105 FD->fd_nextsize = FD->bk_nextsize = FD; \
2107 FD->fd_nextsize = P->fd_nextsize; \
2108 FD->bk_nextsize = P->bk_nextsize; \
2109 P->fd_nextsize->bk_nextsize = FD; \
2110 P->bk_nextsize->fd_nextsize = FD; \
2113 P->fd_nextsize->bk_nextsize = P->bk_nextsize; \
2114 P->bk_nextsize->fd_nextsize = P->fd_nextsize; \
2123 Bins for sizes < 512 bytes contain chunks of all the same size, spaced
2124 8 bytes apart. Larger bins are approximately logarithmically spaced:
2130 4 bins of size 32768
2131 2 bins of size 262144
2132 1 bin of size what's left
2134 There is actually a little bit of slop in the numbers in bin_index
2135 for the sake of speed. This makes no difference elsewhere.
2137 The bins top out around 1MB because we expect to service large
2142 #define NSMALLBINS 64
2143 #define SMALLBIN_WIDTH MALLOC_ALIGNMENT
2144 #define MIN_LARGE_SIZE (NSMALLBINS * SMALLBIN_WIDTH)
2146 #define in_smallbin_range(sz) \
2147 ((unsigned long)(sz) < (unsigned long)MIN_LARGE_SIZE)
2149 #define smallbin_index(sz) \
2150 (SMALLBIN_WIDTH == 16 ? (((unsigned)(sz)) >> 4) : (((unsigned)(sz)) >> 3))
2152 #define largebin_index_32(sz) \
2153 (((((unsigned long)(sz)) >> 6) <= 38)? 56 + (((unsigned long)(sz)) >> 6): \
2154 ((((unsigned long)(sz)) >> 9) <= 20)? 91 + (((unsigned long)(sz)) >> 9): \
2155 ((((unsigned long)(sz)) >> 12) <= 10)? 110 + (((unsigned long)(sz)) >> 12): \
2156 ((((unsigned long)(sz)) >> 15) <= 4)? 119 + (((unsigned long)(sz)) >> 15): \
2157 ((((unsigned long)(sz)) >> 18) <= 2)? 124 + (((unsigned long)(sz)) >> 18): \
2160 // XXX It remains to be seen whether it is good to keep the widths of
2161 // XXX the buckets the same or whether it should be scaled by a factor
2162 // XXX of two as well.
2163 #define largebin_index_64(sz) \
2164 (((((unsigned long)(sz)) >> 6) <= 48)? 48 + (((unsigned long)(sz)) >> 6): \
2165 ((((unsigned long)(sz)) >> 9) <= 20)? 91 + (((unsigned long)(sz)) >> 9): \
2166 ((((unsigned long)(sz)) >> 12) <= 10)? 110 + (((unsigned long)(sz)) >> 12): \
2167 ((((unsigned long)(sz)) >> 15) <= 4)? 119 + (((unsigned long)(sz)) >> 15): \
2168 ((((unsigned long)(sz)) >> 18) <= 2)? 124 + (((unsigned long)(sz)) >> 18): \
2171 #define largebin_index(sz) \
2172 (SIZE_SZ == 8 ? largebin_index_64 (sz) : largebin_index_32 (sz))
2174 #define bin_index(sz) \
2175 ((in_smallbin_range(sz)) ? smallbin_index(sz) : largebin_index(sz))
2181 All remainders from chunk splits, as well as all returned chunks,
2182 are first placed in the "unsorted" bin. They are then placed
2183 in regular bins after malloc gives them ONE chance to be used before
2184 binning. So, basically, the unsorted_chunks list acts as a queue,
2185 with chunks being placed on it in free (and malloc_consolidate),
2186 and taken off (to be either used or placed in bins) in malloc.
2188 The NON_MAIN_ARENA flag is never set for unsorted chunks, so it
2189 does not have to be taken into account in size comparisons.
2192 /* The otherwise unindexable 1-bin is used to hold unsorted chunks. */
2193 #define unsorted_chunks(M) (bin_at(M, 1))
2198 The top-most available chunk (i.e., the one bordering the end of
2199 available memory) is treated specially. It is never included in
2200 any bin, is used only if no other chunk is available, and is
2201 released back to the system if it is very large (see
2202 M_TRIM_THRESHOLD). Because top initially
2203 points to its own bin with initial zero size, thus forcing
2204 extension on the first malloc request, we avoid having any special
2205 code in malloc to check whether it even exists yet. But we still
2206 need to do so when getting memory from system, so we make
2207 initial_top treat the bin as a legal but unusable chunk during the
2208 interval between initialization and the first call to
2209 sYSMALLOc. (This is somewhat delicate, since it relies on
2210 the 2 preceding words to be zero during this interval as well.)
2213 /* Conveniently, the unsorted bin can be used as dummy top on first call */
2214 #define initial_top(M) (unsorted_chunks(M))
2219 To help compensate for the large number of bins, a one-level index
2220 structure is used for bin-by-bin searching. `binmap' is a
2221 bitvector recording whether bins are definitely empty so they can
2222 be skipped over during during traversals. The bits are NOT always
2223 cleared as soon as bins are empty, but instead only
2224 when they are noticed to be empty during traversal in malloc.
2227 /* Conservatively use 32 bits per map word, even if on 64bit system */
2228 #define BINMAPSHIFT 5
2229 #define BITSPERMAP (1U << BINMAPSHIFT)
2230 #define BINMAPSIZE (NBINS / BITSPERMAP)
2232 #define idx2block(i) ((i) >> BINMAPSHIFT)
2233 #define idx2bit(i) ((1U << ((i) & ((1U << BINMAPSHIFT)-1))))
2235 #define mark_bin(m,i) ((m)->binmap[idx2block(i)] |= idx2bit(i))
2236 #define unmark_bin(m,i) ((m)->binmap[idx2block(i)] &= ~(idx2bit(i)))
2237 #define get_binmap(m,i) ((m)->binmap[idx2block(i)] & idx2bit(i))
2242 An array of lists holding recently freed small chunks. Fastbins
2243 are not doubly linked. It is faster to single-link them, and
2244 since chunks are never removed from the middles of these lists,
2245 double linking is not necessary. Also, unlike regular bins, they
2246 are not even processed in FIFO order (they use faster LIFO) since
2247 ordering doesn't much matter in the transient contexts in which
2248 fastbins are normally used.
2250 Chunks in fastbins keep their inuse bit set, so they cannot
2251 be consolidated with other free chunks. malloc_consolidate
2252 releases all chunks in fastbins and consolidates them with
2256 typedef struct malloc_chunk
* mfastbinptr
;
2257 #define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])
2259 /* offset 2 to use otherwise unindexable first 2 bins */
2260 #define fastbin_index(sz) \
2261 ((((unsigned int)(sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)
2264 /* The maximum fastbin request size we support */
2265 #define MAX_FAST_SIZE (80 * SIZE_SZ / 4)
2267 #define NFASTBINS (fastbin_index(request2size(MAX_FAST_SIZE))+1)
2270 FASTBIN_CONSOLIDATION_THRESHOLD is the size of a chunk in free()
2271 that triggers automatic consolidation of possibly-surrounding
2272 fastbin chunks. This is a heuristic, so the exact value should not
2273 matter too much. It is defined at half the default trim threshold as a
2274 compromise heuristic to only attempt consolidation if it is likely
2275 to lead to trimming. However, it is not dynamically tunable, since
2276 consolidation reduces fragmentation surrounding large chunks even
2277 if trimming is not used.
2280 #define FASTBIN_CONSOLIDATION_THRESHOLD (65536UL)
2283 Since the lowest 2 bits in max_fast don't matter in size comparisons,
2284 they are used as flags.
2288 FASTCHUNKS_BIT held in max_fast indicates that there are probably
2289 some fastbin chunks. It is set true on entering a chunk into any
2290 fastbin, and cleared only in malloc_consolidate.
2292 The truth value is inverted so that have_fastchunks will be true
2293 upon startup (since statics are zero-filled), simplifying
2294 initialization checks.
2297 #define FASTCHUNKS_BIT (1U)
2299 #define have_fastchunks(M) (((M)->flags & FASTCHUNKS_BIT) == 0)
2300 #ifdef ATOMIC_FASTBINS
2301 #define clear_fastchunks(M) catomic_or (&(M)->flags, FASTCHUNKS_BIT)
2302 #define set_fastchunks(M) catomic_and (&(M)->flags, ~FASTCHUNKS_BIT)
2304 #define clear_fastchunks(M) ((M)->flags |= FASTCHUNKS_BIT)
2305 #define set_fastchunks(M) ((M)->flags &= ~FASTCHUNKS_BIT)
2309 NONCONTIGUOUS_BIT indicates that MORECORE does not return contiguous
2310 regions. Otherwise, contiguity is exploited in merging together,
2311 when possible, results from consecutive MORECORE calls.
2313 The initial value comes from MORECORE_CONTIGUOUS, but is
2314 changed dynamically if mmap is ever used as an sbrk substitute.
2317 #define NONCONTIGUOUS_BIT (2U)
2319 #define contiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) == 0)
2320 #define noncontiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) != 0)
2321 #define set_noncontiguous(M) ((M)->flags |= NONCONTIGUOUS_BIT)
2322 #define set_contiguous(M) ((M)->flags &= ~NONCONTIGUOUS_BIT)
2325 Set value of max_fast.
2326 Use impossibly small value if 0.
2327 Precondition: there are no existing fastbin chunks.
2328 Setting the value clears fastchunk bit but preserves noncontiguous bit.
2331 #define set_max_fast(s) \
2332 global_max_fast = ((s) == 0)? SMALLBIN_WIDTH: request2size(s)
2333 #define get_max_fast() global_max_fast
2337 ----------- Internal state representation and initialization -----------
2340 struct malloc_state
{
2341 /* Serialize access. */
2344 /* Flags (formerly in max_fast). */
2348 /* Statistics for locking. Only used if THREAD_STATS is defined. */
2349 long stat_lock_direct
, stat_lock_loop
, stat_lock_wait
;
2353 mfastbinptr fastbinsY
[NFASTBINS
];
2355 /* Base of the topmost chunk -- not otherwise kept in a bin */
2358 /* The remainder from the most recent split of a small request */
2359 mchunkptr last_remainder
;
2361 /* Normal bins packed as described above */
2362 mchunkptr bins
[NBINS
* 2 - 2];
2364 /* Bitmap of bins */
2365 unsigned int binmap
[BINMAPSIZE
];
2368 struct malloc_state
*next
;
2371 /* Linked list for free arenas. */
2372 struct malloc_state
*next_free
;
2375 /* Memory allocated from the system in this arena. */
2376 INTERNAL_SIZE_T system_mem
;
2377 INTERNAL_SIZE_T max_system_mem
;
2381 /* Tunable parameters */
2382 unsigned long trim_threshold
;
2383 INTERNAL_SIZE_T top_pad
;
2384 INTERNAL_SIZE_T mmap_threshold
;
2386 INTERNAL_SIZE_T arena_test
;
2387 INTERNAL_SIZE_T arena_max
;
2390 /* Memory map support */
2394 /* the mmap_threshold is dynamic, until the user sets
2395 it manually, at which point we need to disable any
2396 dynamic behavior. */
2397 int no_dyn_threshold
;
2399 /* Cache malloc_getpagesize */
2400 unsigned int pagesize
;
2403 INTERNAL_SIZE_T mmapped_mem
;
2404 /*INTERNAL_SIZE_T sbrked_mem;*/
2405 /*INTERNAL_SIZE_T max_sbrked_mem;*/
2406 INTERNAL_SIZE_T max_mmapped_mem
;
2407 INTERNAL_SIZE_T max_total_mem
; /* only kept for NO_THREADS */
2409 /* First address handed out by MORECORE/sbrk. */
2413 /* There are several instances of this struct ("arenas") in this
2414 malloc. If you are adapting this malloc in a way that does NOT use
2415 a static or mmapped malloc_state, you MUST explicitly zero-fill it
2416 before using. This malloc relies on the property that malloc_state
2417 is initialized to all zeroes (as is true of C statics). */
2419 static struct malloc_state main_arena
;
2421 /* There is only one instance of the malloc parameters. */
2423 static struct malloc_par mp_
;
2427 /* Non public mallopt parameters. */
2428 #define M_ARENA_TEST -7
2429 #define M_ARENA_MAX -8
2433 /* Maximum size of memory handled in fastbins. */
2434 static INTERNAL_SIZE_T global_max_fast
;
2437 Initialize a malloc_state struct.
2439 This is called only from within malloc_consolidate, which needs
2440 be called in the same contexts anyway. It is never called directly
2441 outside of malloc_consolidate because some optimizing compilers try
2442 to inline it at all call points, which turns out not to be an
2443 optimization at all. (Inlining it in malloc_consolidate is fine though.)
2447 static void malloc_init_state(mstate av
)
2449 static void malloc_init_state(av
) mstate av
;
2455 /* Establish circular links for normal bins */
2456 for (i
= 1; i
< NBINS
; ++i
) {
2458 bin
->fd
= bin
->bk
= bin
;
2461 #if MORECORE_CONTIGUOUS
2462 if (av
!= &main_arena
)
2464 set_noncontiguous(av
);
2465 if (av
== &main_arena
)
2466 set_max_fast(DEFAULT_MXFAST
);
2467 av
->flags
|= FASTCHUNKS_BIT
;
2469 av
->top
= initial_top(av
);
2473 Other internal utilities operating on mstates
2477 static Void_t
* sYSMALLOc(INTERNAL_SIZE_T
, mstate
);
2478 static int sYSTRIm(size_t, mstate
);
2479 static void malloc_consolidate(mstate
);
2481 static Void_t
** iALLOc(mstate
, size_t, size_t*, int, Void_t
**);
2484 static Void_t
* sYSMALLOc();
2485 static int sYSTRIm();
2486 static void malloc_consolidate();
2487 static Void_t
** iALLOc();
2491 /* -------------- Early definitions for debugging hooks ---------------- */
2493 /* Define and initialize the hook variables. These weak definitions must
2494 appear before any use of the variables in a function (arena.c uses one). */
2495 #ifndef weak_variable
2497 #define weak_variable /**/
2499 /* In GNU libc we want the hook variables to be weak definitions to
2500 avoid a problem with Emacs. */
2501 #define weak_variable weak_function
2505 /* Forward declarations. */
2506 static Void_t
* malloc_hook_ini
__MALLOC_P ((size_t sz
,
2507 const __malloc_ptr_t caller
));
2508 static Void_t
* realloc_hook_ini
__MALLOC_P ((Void_t
* ptr
, size_t sz
,
2509 const __malloc_ptr_t caller
));
2510 static Void_t
* memalign_hook_ini
__MALLOC_P ((size_t alignment
, size_t sz
,
2511 const __malloc_ptr_t caller
));
2513 void weak_variable (*__malloc_initialize_hook
) (void) = NULL
;
2514 void weak_variable (*__free_hook
) (__malloc_ptr_t __ptr
,
2515 const __malloc_ptr_t
) = NULL
;
2516 __malloc_ptr_t
weak_variable (*__malloc_hook
)
2517 (size_t __size
, const __malloc_ptr_t
) = malloc_hook_ini
;
2518 __malloc_ptr_t
weak_variable (*__realloc_hook
)
2519 (__malloc_ptr_t __ptr
, size_t __size
, const __malloc_ptr_t
)
2521 __malloc_ptr_t
weak_variable (*__memalign_hook
)
2522 (size_t __alignment
, size_t __size
, const __malloc_ptr_t
)
2523 = memalign_hook_ini
;
2524 void weak_variable (*__after_morecore_hook
) (void) = NULL
;
2527 /* ---------------- Error behavior ------------------------------------ */
2529 #ifndef DEFAULT_CHECK_ACTION
2530 #define DEFAULT_CHECK_ACTION 3
2533 static int check_action
= DEFAULT_CHECK_ACTION
;
2536 /* ------------------ Testing support ----------------------------------*/
2538 static int perturb_byte
;
2540 #define alloc_perturb(p, n) memset (p, (perturb_byte ^ 0xff) & 0xff, n)
2541 #define free_perturb(p, n) memset (p, perturb_byte & 0xff, n)
2544 /* ------------------- Support for multiple arenas -------------------- */
2550 These routines make a number of assertions about the states
2551 of data structures that should be true at all times. If any
2552 are not true, it's very likely that a user program has somehow
2553 trashed memory. (It's also possible that there is a coding error
2554 in malloc. In which case, please report it!)
2559 #define check_chunk(A,P)
2560 #define check_free_chunk(A,P)
2561 #define check_inuse_chunk(A,P)
2562 #define check_remalloced_chunk(A,P,N)
2563 #define check_malloced_chunk(A,P,N)
2564 #define check_malloc_state(A)
2568 #define check_chunk(A,P) do_check_chunk(A,P)
2569 #define check_free_chunk(A,P) do_check_free_chunk(A,P)
2570 #define check_inuse_chunk(A,P) do_check_inuse_chunk(A,P)
2571 #define check_remalloced_chunk(A,P,N) do_check_remalloced_chunk(A,P,N)
2572 #define check_malloced_chunk(A,P,N) do_check_malloced_chunk(A,P,N)
2573 #define check_malloc_state(A) do_check_malloc_state(A)
2576 Properties of all chunks
2580 static void do_check_chunk(mstate av
, mchunkptr p
)
2582 static void do_check_chunk(av
, p
) mstate av
; mchunkptr p
;
2585 unsigned long sz
= chunksize(p
);
2586 /* min and max possible addresses assuming contiguous allocation */
2587 char* max_address
= (char*)(av
->top
) + chunksize(av
->top
);
2588 char* min_address
= max_address
- av
->system_mem
;
2590 if (!chunk_is_mmapped(p
)) {
2592 /* Has legal address ... */
2594 if (contiguous(av
)) {
2595 assert(((char*)p
) >= min_address
);
2596 assert(((char*)p
+ sz
) <= ((char*)(av
->top
)));
2600 /* top size is always at least MINSIZE */
2601 assert((unsigned long)(sz
) >= MINSIZE
);
2602 /* top predecessor always marked inuse */
2603 assert(prev_inuse(p
));
2609 /* address is outside main heap */
2610 if (contiguous(av
) && av
->top
!= initial_top(av
)) {
2611 assert(((char*)p
) < min_address
|| ((char*)p
) >= max_address
);
2613 /* chunk is page-aligned */
2614 assert(((p
->prev_size
+ sz
) & (mp_
.pagesize
-1)) == 0);
2615 /* mem is aligned */
2616 assert(aligned_OK(chunk2mem(p
)));
2618 /* force an appropriate assert violation if debug set */
2619 assert(!chunk_is_mmapped(p
));
2625 Properties of free chunks
2629 static void do_check_free_chunk(mstate av
, mchunkptr p
)
2631 static void do_check_free_chunk(av
, p
) mstate av
; mchunkptr p
;
2634 INTERNAL_SIZE_T sz
= p
->size
& ~(PREV_INUSE
|NON_MAIN_ARENA
);
2635 mchunkptr next
= chunk_at_offset(p
, sz
);
2637 do_check_chunk(av
, p
);
2639 /* Chunk must claim to be free ... */
2641 assert (!chunk_is_mmapped(p
));
2643 /* Unless a special marker, must have OK fields */
2644 if ((unsigned long)(sz
) >= MINSIZE
)
2646 assert((sz
& MALLOC_ALIGN_MASK
) == 0);
2647 assert(aligned_OK(chunk2mem(p
)));
2648 /* ... matching footer field */
2649 assert(next
->prev_size
== sz
);
2650 /* ... and is fully consolidated */
2651 assert(prev_inuse(p
));
2652 assert (next
== av
->top
|| inuse(next
));
2654 /* ... and has minimally sane links */
2655 assert(p
->fd
->bk
== p
);
2656 assert(p
->bk
->fd
== p
);
2658 else /* markers are always of size SIZE_SZ */
2659 assert(sz
== SIZE_SZ
);
2663 Properties of inuse chunks
2667 static void do_check_inuse_chunk(mstate av
, mchunkptr p
)
2669 static void do_check_inuse_chunk(av
, p
) mstate av
; mchunkptr p
;
2674 do_check_chunk(av
, p
);
2676 if (chunk_is_mmapped(p
))
2677 return; /* mmapped chunks have no next/prev */
2679 /* Check whether it claims to be in use ... */
2682 next
= next_chunk(p
);
2684 /* ... and is surrounded by OK chunks.
2685 Since more things can be checked with free chunks than inuse ones,
2686 if an inuse chunk borders them and debug is on, it's worth doing them.
2688 if (!prev_inuse(p
)) {
2689 /* Note that we cannot even look at prev unless it is not inuse */
2690 mchunkptr prv
= prev_chunk(p
);
2691 assert(next_chunk(prv
) == p
);
2692 do_check_free_chunk(av
, prv
);
2695 if (next
== av
->top
) {
2696 assert(prev_inuse(next
));
2697 assert(chunksize(next
) >= MINSIZE
);
2699 else if (!inuse(next
))
2700 do_check_free_chunk(av
, next
);
2704 Properties of chunks recycled from fastbins
2708 static void do_check_remalloced_chunk(mstate av
, mchunkptr p
, INTERNAL_SIZE_T s
)
2710 static void do_check_remalloced_chunk(av
, p
, s
)
2711 mstate av
; mchunkptr p
; INTERNAL_SIZE_T s
;
2714 INTERNAL_SIZE_T sz
= p
->size
& ~(PREV_INUSE
|NON_MAIN_ARENA
);
2716 if (!chunk_is_mmapped(p
)) {
2717 assert(av
== arena_for_chunk(p
));
2718 if (chunk_non_main_arena(p
))
2719 assert(av
!= &main_arena
);
2721 assert(av
== &main_arena
);
2724 do_check_inuse_chunk(av
, p
);
2726 /* Legal size ... */
2727 assert((sz
& MALLOC_ALIGN_MASK
) == 0);
2728 assert((unsigned long)(sz
) >= MINSIZE
);
2729 /* ... and alignment */
2730 assert(aligned_OK(chunk2mem(p
)));
2731 /* chunk is less than MINSIZE more than request */
2732 assert((long)(sz
) - (long)(s
) >= 0);
2733 assert((long)(sz
) - (long)(s
+ MINSIZE
) < 0);
2737 Properties of nonrecycled chunks at the point they are malloced
2741 static void do_check_malloced_chunk(mstate av
, mchunkptr p
, INTERNAL_SIZE_T s
)
2743 static void do_check_malloced_chunk(av
, p
, s
)
2744 mstate av
; mchunkptr p
; INTERNAL_SIZE_T s
;
2747 /* same as recycled case ... */
2748 do_check_remalloced_chunk(av
, p
, s
);
2751 ... plus, must obey implementation invariant that prev_inuse is
2752 always true of any allocated chunk; i.e., that each allocated
2753 chunk borders either a previously allocated and still in-use
2754 chunk, or the base of its memory arena. This is ensured
2755 by making all allocations from the the `lowest' part of any found
2756 chunk. This does not necessarily hold however for chunks
2757 recycled via fastbins.
2760 assert(prev_inuse(p
));
2765 Properties of malloc_state.
2767 This may be useful for debugging malloc, as well as detecting user
2768 programmer errors that somehow write into malloc_state.
2770 If you are extending or experimenting with this malloc, you can
2771 probably figure out how to hack this routine to print out or
2772 display chunk addresses, sizes, bins, and other instrumentation.
2775 static void do_check_malloc_state(mstate av
)
2782 INTERNAL_SIZE_T size
;
2783 unsigned long total
= 0;
2786 /* internal size_t must be no wider than pointer type */
2787 assert(sizeof(INTERNAL_SIZE_T
) <= sizeof(char*));
2789 /* alignment is a power of 2 */
2790 assert((MALLOC_ALIGNMENT
& (MALLOC_ALIGNMENT
-1)) == 0);
2792 /* cannot run remaining checks until fully initialized */
2793 if (av
->top
== 0 || av
->top
== initial_top(av
))
2796 /* pagesize is a power of 2 */
2797 assert((mp_
.pagesize
& (mp_
.pagesize
-1)) == 0);
2799 /* A contiguous main_arena is consistent with sbrk_base. */
2800 if (av
== &main_arena
&& contiguous(av
))
2801 assert((char*)mp_
.sbrk_base
+ av
->system_mem
==
2802 (char*)av
->top
+ chunksize(av
->top
));
2804 /* properties of fastbins */
2806 /* max_fast is in allowed range */
2807 assert((get_max_fast () & ~1) <= request2size(MAX_FAST_SIZE
));
2809 max_fast_bin
= fastbin_index(get_max_fast ());
2811 for (i
= 0; i
< NFASTBINS
; ++i
) {
2812 p
= av
->fastbins
[i
];
2814 /* The following test can only be performed for the main arena.
2815 While mallopt calls malloc_consolidate to get rid of all fast
2816 bins (especially those larger than the new maximum) this does
2817 only happen for the main arena. Trying to do this for any
2818 other arena would mean those arenas have to be locked and
2819 malloc_consolidate be called for them. This is excessive. And
2820 even if this is acceptable to somebody it still cannot solve
2821 the problem completely since if the arena is locked a
2822 concurrent malloc call might create a new arena which then
2823 could use the newly invalid fast bins. */
2825 /* all bins past max_fast are empty */
2826 if (av
== &main_arena
&& i
> max_fast_bin
)
2830 /* each chunk claims to be inuse */
2831 do_check_inuse_chunk(av
, p
);
2832 total
+= chunksize(p
);
2833 /* chunk belongs in this bin */
2834 assert(fastbin_index(chunksize(p
)) == i
);
2840 assert(have_fastchunks(av
));
2841 else if (!have_fastchunks(av
))
2844 /* check normal bins */
2845 for (i
= 1; i
< NBINS
; ++i
) {
2848 /* binmap is accurate (except for bin 1 == unsorted_chunks) */
2850 unsigned int binbit
= get_binmap(av
,i
);
2851 int empty
= last(b
) == b
;
2858 for (p
= last(b
); p
!= b
; p
= p
->bk
) {
2859 /* each chunk claims to be free */
2860 do_check_free_chunk(av
, p
);
2861 size
= chunksize(p
);
2864 /* chunk belongs in bin */
2865 idx
= bin_index(size
);
2867 /* lists are sorted */
2868 assert(p
->bk
== b
||
2869 (unsigned long)chunksize(p
->bk
) >= (unsigned long)chunksize(p
));
2871 if (!in_smallbin_range(size
))
2873 if (p
->fd_nextsize
!= NULL
)
2875 if (p
->fd_nextsize
== p
)
2876 assert (p
->bk_nextsize
== p
);
2879 if (p
->fd_nextsize
== first (b
))
2880 assert (chunksize (p
) < chunksize (p
->fd_nextsize
));
2882 assert (chunksize (p
) > chunksize (p
->fd_nextsize
));
2885 assert (chunksize (p
) > chunksize (p
->bk_nextsize
));
2887 assert (chunksize (p
) < chunksize (p
->bk_nextsize
));
2891 assert (p
->bk_nextsize
== NULL
);
2893 } else if (!in_smallbin_range(size
))
2894 assert (p
->fd_nextsize
== NULL
&& p
->bk_nextsize
== NULL
);
2895 /* chunk is followed by a legal chain of inuse chunks */
2896 for (q
= next_chunk(p
);
2897 (q
!= av
->top
&& inuse(q
) &&
2898 (unsigned long)(chunksize(q
)) >= MINSIZE
);
2900 do_check_inuse_chunk(av
, q
);
2904 /* top chunk is OK */
2905 check_chunk(av
, av
->top
);
2907 /* sanity checks for statistics */
2910 assert(total
<= (unsigned long)(mp_
.max_total_mem
));
2911 assert(mp_
.n_mmaps
>= 0);
2913 assert(mp_
.n_mmaps
<= mp_
.max_n_mmaps
);
2915 assert((unsigned long)(av
->system_mem
) <=
2916 (unsigned long)(av
->max_system_mem
));
2918 assert((unsigned long)(mp_
.mmapped_mem
) <=
2919 (unsigned long)(mp_
.max_mmapped_mem
));
2922 assert((unsigned long)(mp_
.max_total_mem
) >=
2923 (unsigned long)(mp_
.mmapped_mem
) + (unsigned long)(av
->system_mem
));
2929 /* ----------------- Support for debugging hooks -------------------- */
2933 /* ----------- Routines dealing with system allocation -------------- */
2936 sysmalloc handles malloc cases requiring more memory from the system.
2937 On entry, it is assumed that av->top does not have enough
2938 space to service request for nb bytes, thus requiring that av->top
2939 be extended or replaced.
2943 static Void_t
* sYSMALLOc(INTERNAL_SIZE_T nb
, mstate av
)
2945 static Void_t
* sYSMALLOc(nb
, av
) INTERNAL_SIZE_T nb
; mstate av
;
2948 mchunkptr old_top
; /* incoming value of av->top */
2949 INTERNAL_SIZE_T old_size
; /* its size */
2950 char* old_end
; /* its end address */
2952 long size
; /* arg to first MORECORE or mmap call */
2953 char* brk
; /* return value from MORECORE */
2955 long correction
; /* arg to 2nd MORECORE call */
2956 char* snd_brk
; /* 2nd return val */
2958 INTERNAL_SIZE_T front_misalign
; /* unusable bytes at front of new space */
2959 INTERNAL_SIZE_T end_misalign
; /* partial page left at end of new space */
2960 char* aligned_brk
; /* aligned offset into brk */
2962 mchunkptr p
; /* the allocated/returned chunk */
2963 mchunkptr remainder
; /* remainder from allocation */
2964 unsigned long remainder_size
; /* its size */
2966 unsigned long sum
; /* for updating stats */
2968 size_t pagemask
= mp_
.pagesize
- 1;
2969 bool tried_mmap
= false;
2975 If have mmap, and the request size meets the mmap threshold, and
2976 the system supports mmap, and there are few enough currently
2977 allocated mmapped regions, try to directly map this request
2978 rather than expanding top.
2981 if ((unsigned long)(nb
) >= (unsigned long)(mp_
.mmap_threshold
) &&
2982 (mp_
.n_mmaps
< mp_
.n_mmaps_max
)) {
2984 char* mm
; /* return value from mmap call*/
2988 Round up size to nearest page. For mmapped chunks, the overhead
2989 is one SIZE_SZ unit larger than for normal chunks, because there
2990 is no following chunk whose prev_size field could be used.
2993 /* See the front_misalign handling below, for glibc there is no
2994 need for further alignments. */
2995 size
= (nb
+ SIZE_SZ
+ pagemask
) & ~pagemask
;
2997 size
= (nb
+ SIZE_SZ
+ MALLOC_ALIGN_MASK
+ pagemask
) & ~pagemask
;
3001 /* Don't try if size wraps around 0 */
3002 if ((unsigned long)(size
) > (unsigned long)(nb
)) {
3004 mm
= (char*)(MMAP(0, size
, PROT_READ
|PROT_WRITE
, MAP_PRIVATE
));
3006 if (mm
!= MAP_FAILED
) {
3009 The offset to the start of the mmapped region is stored
3010 in the prev_size field of the chunk. This allows us to adjust
3011 returned start address to meet alignment requirements here
3012 and in memalign(), and still be able to compute proper
3013 address argument for later munmap in free() and realloc().
3017 /* For glibc, chunk2mem increases the address by 2*SIZE_SZ and
3018 MALLOC_ALIGN_MASK is 2*SIZE_SZ-1. Each mmap'ed area is page
3019 aligned and therefore definitely MALLOC_ALIGN_MASK-aligned. */
3020 assert (((INTERNAL_SIZE_T
)chunk2mem(mm
) & MALLOC_ALIGN_MASK
) == 0);
3022 front_misalign
= (INTERNAL_SIZE_T
)chunk2mem(mm
) & MALLOC_ALIGN_MASK
;
3023 if (front_misalign
> 0) {
3024 correction
= MALLOC_ALIGNMENT
- front_misalign
;
3025 p
= (mchunkptr
)(mm
+ correction
);
3026 p
->prev_size
= correction
;
3027 set_head(p
, (size
- correction
) |IS_MMAPPED
);
3033 set_head(p
, size
|IS_MMAPPED
);
3036 /* update statistics */
3038 if (++mp_
.n_mmaps
> mp_
.max_n_mmaps
)
3039 mp_
.max_n_mmaps
= mp_
.n_mmaps
;
3041 sum
= mp_
.mmapped_mem
+= size
;
3042 if (sum
> (unsigned long)(mp_
.max_mmapped_mem
))
3043 mp_
.max_mmapped_mem
= sum
;
3045 sum
+= av
->system_mem
;
3046 if (sum
> (unsigned long)(mp_
.max_total_mem
))
3047 mp_
.max_total_mem
= sum
;
3052 return chunk2mem(p
);
3058 /* Record incoming configuration of top */
3061 old_size
= chunksize(old_top
);
3062 old_end
= (char*)(chunk_at_offset(old_top
, old_size
));
3064 brk
= snd_brk
= (char*)(MORECORE_FAILURE
);
3067 If not the first time through, we require old_size to be
3068 at least MINSIZE and to have prev_inuse set.
3071 assert((old_top
== initial_top(av
) && old_size
== 0) ||
3072 ((unsigned long) (old_size
) >= MINSIZE
&&
3073 prev_inuse(old_top
) &&
3074 ((unsigned long)old_end
& pagemask
) == 0));
3076 /* Precondition: not enough current space to satisfy nb request */
3077 assert((unsigned long)(old_size
) < (unsigned long)(nb
+ MINSIZE
));
3079 #ifndef ATOMIC_FASTBINS
3080 /* Precondition: all fastbins are consolidated */
3081 assert(!have_fastchunks(av
));
3085 if (av
!= &main_arena
) {
3087 heap_info
*old_heap
, *heap
;
3088 size_t old_heap_size
;
3090 /* First try to extend the current heap. */
3091 old_heap
= heap_for_ptr(old_top
);
3092 old_heap_size
= old_heap
->size
;
3093 if ((long) (MINSIZE
+ nb
- old_size
) > 0
3094 && grow_heap(old_heap
, MINSIZE
+ nb
- old_size
) == 0) {
3095 av
->system_mem
+= old_heap
->size
- old_heap_size
;
3096 arena_mem
+= old_heap
->size
- old_heap_size
;
3098 if(mmapped_mem
+ arena_mem
+ sbrked_mem
> max_total_mem
)
3099 max_total_mem
= mmapped_mem
+ arena_mem
+ sbrked_mem
;
3101 set_head(old_top
, (((char *)old_heap
+ old_heap
->size
) - (char *)old_top
)
3104 else if ((heap
= new_heap(nb
+ (MINSIZE
+ sizeof(*heap
)), mp_
.top_pad
))) {
3105 /* Use a newly allocated heap. */
3107 heap
->prev
= old_heap
;
3108 av
->system_mem
+= heap
->size
;
3109 arena_mem
+= heap
->size
;
3111 if((unsigned long)(mmapped_mem
+ arena_mem
+ sbrked_mem
) > max_total_mem
)
3112 max_total_mem
= mmapped_mem
+ arena_mem
+ sbrked_mem
;
3114 /* Set up the new top. */
3115 top(av
) = chunk_at_offset(heap
, sizeof(*heap
));
3116 set_head(top(av
), (heap
->size
- sizeof(*heap
)) | PREV_INUSE
);
3118 /* Setup fencepost and free the old top chunk. */
3119 /* The fencepost takes at least MINSIZE bytes, because it might
3120 become the top chunk again later. Note that a footer is set
3121 up, too, although the chunk is marked in use. */
3122 old_size
-= MINSIZE
;
3123 set_head(chunk_at_offset(old_top
, old_size
+ 2*SIZE_SZ
), 0|PREV_INUSE
);
3124 if (old_size
>= MINSIZE
) {
3125 set_head(chunk_at_offset(old_top
, old_size
), (2*SIZE_SZ
)|PREV_INUSE
);
3126 set_foot(chunk_at_offset(old_top
, old_size
), (2*SIZE_SZ
));
3127 set_head(old_top
, old_size
|PREV_INUSE
|NON_MAIN_ARENA
);
3128 #ifdef ATOMIC_FASTBINS
3129 _int_free(av
, old_top
, 1);
3131 _int_free(av
, old_top
);
3134 set_head(old_top
, (old_size
+ 2*SIZE_SZ
)|PREV_INUSE
);
3135 set_foot(old_top
, (old_size
+ 2*SIZE_SZ
));
3138 else if (!tried_mmap
)
3139 /* We can at least try to use to mmap memory. */
3142 } else { /* av == main_arena */
3145 /* Request enough space for nb + pad + overhead */
3147 size
= nb
+ mp_
.top_pad
+ MINSIZE
;
3150 If contiguous, we can subtract out existing space that we hope to
3151 combine with new space. We add it back later only if
3152 we don't actually get contiguous space.
3159 Round to a multiple of page size.
3160 If MORECORE is not contiguous, this ensures that we only call it
3161 with whole-page arguments. And if MORECORE is contiguous and
3162 this is not first time through, this preserves page-alignment of
3163 previous calls. Otherwise, we correct to page-align below.
3166 size
= (size
+ pagemask
) & ~pagemask
;
3169 Don't try to call MORECORE if argument is so big as to appear
3170 negative. Note that since mmap takes size_t arg, it may succeed
3171 below even if we cannot call MORECORE.
3175 brk
= (char*)(MORECORE(size
));
3177 if (brk
!= (char*)(MORECORE_FAILURE
)) {
3178 /* Call the `morecore' hook if necessary. */
3179 void (*hook
) (void) = force_reg (__after_morecore_hook
);
3180 if (__builtin_expect (hook
!= NULL
, 0))
3184 If have mmap, try using it as a backup when MORECORE fails or
3185 cannot be used. This is worth doing on systems that have "holes" in
3186 address space, so sbrk cannot extend to give contiguous space, but
3187 space is available elsewhere. Note that we ignore mmap max count
3188 and threshold limits, since the space will not be used as a
3189 segregated mmap region.
3193 /* Cannot merge with old top, so add its size back in */
3195 size
= (size
+ old_size
+ pagemask
) & ~pagemask
;
3197 /* If we are relying on mmap as backup, then use larger units */
3198 if ((unsigned long)(size
) < (unsigned long)(MMAP_AS_MORECORE_SIZE
))
3199 size
= MMAP_AS_MORECORE_SIZE
;
3201 /* Don't try if size wraps around 0 */
3202 if ((unsigned long)(size
) > (unsigned long)(nb
)) {
3204 char *mbrk
= (char*)(MMAP(0, size
, PROT_READ
|PROT_WRITE
, MAP_PRIVATE
));
3206 if (mbrk
!= MAP_FAILED
) {
3208 /* We do not need, and cannot use, another sbrk call to find end */
3210 snd_brk
= brk
+ size
;
3213 Record that we no longer have a contiguous sbrk region.
3214 After the first time mmap is used as backup, we do not
3215 ever rely on contiguous space since this could incorrectly
3218 set_noncontiguous(av
);
3224 if (brk
!= (char*)(MORECORE_FAILURE
)) {
3225 if (mp_
.sbrk_base
== 0)
3226 mp_
.sbrk_base
= brk
;
3227 av
->system_mem
+= size
;
3230 If MORECORE extends previous space, we can likewise extend top size.
3233 if (brk
== old_end
&& snd_brk
== (char*)(MORECORE_FAILURE
))
3234 set_head(old_top
, (size
+ old_size
) | PREV_INUSE
);
3236 else if (contiguous(av
) && old_size
&& brk
< old_end
) {
3237 /* Oops! Someone else killed our space.. Can't touch anything. */
3238 malloc_printerr (3, "break adjusted to free malloc space", brk
);
3242 Otherwise, make adjustments:
3244 * If the first time through or noncontiguous, we need to call sbrk
3245 just to find out where the end of memory lies.
3247 * We need to ensure that all returned chunks from malloc will meet
3250 * If there was an intervening foreign sbrk, we need to adjust sbrk
3251 request size to account for fact that we will not be able to
3252 combine new space with existing space in old_top.
3254 * Almost all systems internally allocate whole pages at a time, in
3255 which case we might as well use the whole last page of request.
3256 So we allocate enough more memory to hit a page boundary now,
3257 which in turn causes future contiguous calls to page-align.
3266 /* handle contiguous cases */
3267 if (contiguous(av
)) {
3269 /* Count foreign sbrk as system_mem. */
3271 av
->system_mem
+= brk
- old_end
;
3273 /* Guarantee alignment of first new chunk made from this space */
3275 front_misalign
= (INTERNAL_SIZE_T
)chunk2mem(brk
) & MALLOC_ALIGN_MASK
;
3276 if (front_misalign
> 0) {
3279 Skip over some bytes to arrive at an aligned position.
3280 We don't need to specially mark these wasted front bytes.
3281 They will never be accessed anyway because
3282 prev_inuse of av->top (and any chunk created from its start)
3283 is always true after initialization.
3286 correction
= MALLOC_ALIGNMENT
- front_misalign
;
3287 aligned_brk
+= correction
;
3291 If this isn't adjacent to existing space, then we will not
3292 be able to merge with old_top space, so must add to 2nd request.
3295 correction
+= old_size
;
3297 /* Extend the end address to hit a page boundary */
3298 end_misalign
= (INTERNAL_SIZE_T
)(brk
+ size
+ correction
);
3299 correction
+= ((end_misalign
+ pagemask
) & ~pagemask
) - end_misalign
;
3301 assert(correction
>= 0);
3302 snd_brk
= (char*)(MORECORE(correction
));
3305 If can't allocate correction, try to at least find out current
3306 brk. It might be enough to proceed without failing.
3308 Note that if second sbrk did NOT fail, we assume that space
3309 is contiguous with first sbrk. This is a safe assumption unless
3310 program is multithreaded but doesn't use locks and a foreign sbrk
3311 occurred between our first and second calls.
3314 if (snd_brk
== (char*)(MORECORE_FAILURE
)) {
3316 snd_brk
= (char*)(MORECORE(0));
3318 /* Call the `morecore' hook if necessary. */
3319 void (*hook
) (void) = force_reg (__after_morecore_hook
);
3320 if (__builtin_expect (hook
!= NULL
, 0))
3325 /* handle non-contiguous cases */
3327 /* MORECORE/mmap must correctly align */
3328 assert(((unsigned long)chunk2mem(brk
) & MALLOC_ALIGN_MASK
) == 0);
3330 /* Find out current end of memory */
3331 if (snd_brk
== (char*)(MORECORE_FAILURE
)) {
3332 snd_brk
= (char*)(MORECORE(0));
3336 /* Adjust top based on results of second sbrk */
3337 if (snd_brk
!= (char*)(MORECORE_FAILURE
)) {
3338 av
->top
= (mchunkptr
)aligned_brk
;
3339 set_head(av
->top
, (snd_brk
- aligned_brk
+ correction
) | PREV_INUSE
);
3340 av
->system_mem
+= correction
;
3343 If not the first time through, we either have a
3344 gap due to foreign sbrk or a non-contiguous region. Insert a
3345 double fencepost at old_top to prevent consolidation with space
3346 we don't own. These fenceposts are artificial chunks that are
3347 marked as inuse and are in any case too small to use. We need
3348 two to make sizes and alignments work out.
3351 if (old_size
!= 0) {
3353 Shrink old_top to insert fenceposts, keeping size a
3354 multiple of MALLOC_ALIGNMENT. We know there is at least
3355 enough space in old_top to do this.
3357 old_size
= (old_size
- 4*SIZE_SZ
) & ~MALLOC_ALIGN_MASK
;
3358 set_head(old_top
, old_size
| PREV_INUSE
);
3361 Note that the following assignments completely overwrite
3362 old_top when old_size was previously MINSIZE. This is
3363 intentional. We need the fencepost, even if old_top otherwise gets
3366 chunk_at_offset(old_top
, old_size
)->size
=
3367 (2*SIZE_SZ
)|PREV_INUSE
;
3369 chunk_at_offset(old_top
, old_size
+ 2*SIZE_SZ
)->size
=
3370 (2*SIZE_SZ
)|PREV_INUSE
;
3372 /* If possible, release the rest. */
3373 if (old_size
>= MINSIZE
) {
3374 #ifdef ATOMIC_FASTBINS
3375 _int_free(av
, old_top
, 1);
3377 _int_free(av
, old_top
);
3385 /* Update statistics */
3387 sum
= av
->system_mem
+ mp_
.mmapped_mem
;
3388 if (sum
> (unsigned long)(mp_
.max_total_mem
))
3389 mp_
.max_total_mem
= sum
;
3394 } /* if (av != &main_arena) */
3396 if ((unsigned long)av
->system_mem
> (unsigned long)(av
->max_system_mem
))
3397 av
->max_system_mem
= av
->system_mem
;
3398 check_malloc_state(av
);
3400 /* finally, do the allocation */
3402 size
= chunksize(p
);
3404 /* check that one of the above allocation paths succeeded */
3405 if ((unsigned long)(size
) >= (unsigned long)(nb
+ MINSIZE
)) {
3406 remainder_size
= size
- nb
;
3407 remainder
= chunk_at_offset(p
, nb
);
3408 av
->top
= remainder
;
3409 set_head(p
, nb
| PREV_INUSE
| (av
!= &main_arena
? NON_MAIN_ARENA
: 0));
3410 set_head(remainder
, remainder_size
| PREV_INUSE
);
3411 check_malloced_chunk(av
, p
, nb
);
3412 return chunk2mem(p
);
3415 /* catch all failure paths */
3416 MALLOC_FAILURE_ACTION
;
3422 sYSTRIm is an inverse of sorts to sYSMALLOc. It gives memory back
3423 to the system (via negative arguments to sbrk) if there is unused
3424 memory at the `high' end of the malloc pool. It is called
3425 automatically by free() when top space exceeds the trim
3426 threshold. It is also called by the public malloc_trim routine. It
3427 returns 1 if it actually released any memory, else 0.
3431 static int sYSTRIm(size_t pad
, mstate av
)
3433 static int sYSTRIm(pad
, av
) size_t pad
; mstate av
;
3436 long top_size
; /* Amount of top-most memory */
3437 long extra
; /* Amount to release */
3438 long released
; /* Amount actually released */
3439 char* current_brk
; /* address returned by pre-check sbrk call */
3440 char* new_brk
; /* address returned by post-check sbrk call */
3443 pagesz
= mp_
.pagesize
;
3444 top_size
= chunksize(av
->top
);
3446 /* Release in pagesize units, keeping at least one page */
3447 extra
= ((top_size
- pad
- MINSIZE
+ (pagesz
-1)) / pagesz
- 1) * pagesz
;
3452 Only proceed if end of memory is where we last set it.
3453 This avoids problems if there were foreign sbrk calls.
3455 current_brk
= (char*)(MORECORE(0));
3456 if (current_brk
== (char*)(av
->top
) + top_size
) {
3459 Attempt to release memory. We ignore MORECORE return value,
3460 and instead call again to find out where new end of memory is.
3461 This avoids problems if first call releases less than we asked,
3462 of if failure somehow altered brk value. (We could still
3463 encounter problems if it altered brk in some very bad way,
3464 but the only thing we can do is adjust anyway, which will cause
3465 some downstream failure.)
3469 /* Call the `morecore' hook if necessary. */
3470 void (*hook
) (void) = force_reg (__after_morecore_hook
);
3471 if (__builtin_expect (hook
!= NULL
, 0))
3473 new_brk
= (char*)(MORECORE(0));
3475 if (new_brk
!= (char*)MORECORE_FAILURE
) {
3476 released
= (long)(current_brk
- new_brk
);
3478 if (released
!= 0) {
3479 /* Success. Adjust top. */
3480 av
->system_mem
-= released
;
3481 set_head(av
->top
, (top_size
- released
) | PREV_INUSE
);
3482 check_malloc_state(av
);
3496 munmap_chunk(mchunkptr p
)
3498 munmap_chunk(p
) mchunkptr p
;
3501 INTERNAL_SIZE_T size
= chunksize(p
);
3503 assert (chunk_is_mmapped(p
));
3505 assert(! ((char*)p
>= mp_
.sbrk_base
&& (char*)p
< mp_
.sbrk_base
+ mp_
.sbrked_mem
));
3506 assert((mp_
.n_mmaps
> 0));
3509 uintptr_t block
= (uintptr_t) p
- p
->prev_size
;
3510 size_t total_size
= p
->prev_size
+ size
;
3511 /* Unfortunately we have to do the compilers job by hand here. Normally
3512 we would test BLOCK and TOTAL-SIZE separately for compliance with the
3513 page size. But gcc does not recognize the optimization possibility
3514 (in the moment at least) so we combine the two values into one before
3516 if (__builtin_expect (((block
| total_size
) & (mp_
.pagesize
- 1)) != 0, 0))
3518 malloc_printerr (check_action
, "munmap_chunk(): invalid pointer",
3524 mp_
.mmapped_mem
-= total_size
;
3526 int ret
__attribute__ ((unused
)) = munmap((char *)block
, total_size
);
3528 /* munmap returns non-zero on failure */
3537 mremap_chunk(mchunkptr p
, size_t new_size
)
3539 mremap_chunk(p
, new_size
) mchunkptr p
; size_t new_size
;
3542 size_t page_mask
= mp_
.pagesize
- 1;
3543 INTERNAL_SIZE_T offset
= p
->prev_size
;
3544 INTERNAL_SIZE_T size
= chunksize(p
);
3547 assert (chunk_is_mmapped(p
));
3549 assert(! ((char*)p
>= mp_
.sbrk_base
&& (char*)p
< mp_
.sbrk_base
+ mp_
.sbrked_mem
));
3550 assert((mp_
.n_mmaps
> 0));
3552 assert(((size
+ offset
) & (mp_
.pagesize
-1)) == 0);
3554 /* Note the extra SIZE_SZ overhead as in mmap_chunk(). */
3555 new_size
= (new_size
+ offset
+ SIZE_SZ
+ page_mask
) & ~page_mask
;
3557 /* No need to remap if the number of pages does not change. */
3558 if (size
+ offset
== new_size
)
3561 cp
= (char *)mremap((char *)p
- offset
, size
+ offset
, new_size
,
3564 if (cp
== MAP_FAILED
) return 0;
3566 p
= (mchunkptr
)(cp
+ offset
);
3568 assert(aligned_OK(chunk2mem(p
)));
3570 assert((p
->prev_size
== offset
));
3571 set_head(p
, (new_size
- offset
)|IS_MMAPPED
);
3573 mp_
.mmapped_mem
-= size
+ offset
;
3574 mp_
.mmapped_mem
+= new_size
;
3575 if ((unsigned long)mp_
.mmapped_mem
> (unsigned long)mp_
.max_mmapped_mem
)
3576 mp_
.max_mmapped_mem
= mp_
.mmapped_mem
;
3578 if ((unsigned long)(mp_
.mmapped_mem
+ arena_mem
+ main_arena
.system_mem
) >
3580 mp_
.max_total_mem
= mp_
.mmapped_mem
+ arena_mem
+ main_arena
.system_mem
;
3585 #endif /* HAVE_MREMAP */
3587 #endif /* HAVE_MMAP */
3589 /*------------------------ Public wrappers. --------------------------------*/
3592 public_mALLOc(size_t bytes
)
3597 __malloc_ptr_t (*hook
) (size_t, __const __malloc_ptr_t
)
3598 = force_reg (__malloc_hook
);
3599 if (__builtin_expect (hook
!= NULL
, 0))
3600 return (*hook
)(bytes
, RETURN_ADDRESS (0));
3602 arena_lookup(ar_ptr
);
3604 // XXX We need double-word CAS and fastbins must be extended to also
3605 // XXX hold a generation counter for each entry.
3607 INTERNAL_SIZE_T nb
; /* normalized request size */
3608 checked_request2size(bytes
, nb
);
3609 if (nb
<= get_max_fast ()) {
3610 long int idx
= fastbin_index(nb
);
3611 mfastbinptr
* fb
= &fastbin (ar_ptr
, idx
);
3620 while ((pp
= catomic_compare_and_exchange_val_acq (fb
, v
->fd
, v
)) != v
);
3622 if (__builtin_expect (fastbin_index (chunksize (v
)) != idx
, 0))
3623 malloc_printerr (check_action
, "malloc(): memory corruption (fast)",
3625 check_remalloced_chunk(ar_ptr
, v
, nb
);
3626 void *p
= chunk2mem(v
);
3627 if (__builtin_expect (perturb_byte
, 0))
3628 alloc_perturb (p
, bytes
);
3635 arena_lock(ar_ptr
, bytes
);
3638 victim
= _int_malloc(ar_ptr
, bytes
);
3640 /* Maybe the failure is due to running out of mmapped areas. */
3641 if(ar_ptr
!= &main_arena
) {
3642 (void)mutex_unlock(&ar_ptr
->mutex
);
3643 ar_ptr
= &main_arena
;
3644 (void)mutex_lock(&ar_ptr
->mutex
);
3645 victim
= _int_malloc(ar_ptr
, bytes
);
3646 (void)mutex_unlock(&ar_ptr
->mutex
);
3649 /* ... or sbrk() has failed and there is still a chance to mmap() */
3650 ar_ptr
= arena_get2(ar_ptr
->next
? ar_ptr
: 0, bytes
);
3651 (void)mutex_unlock(&main_arena
.mutex
);
3653 victim
= _int_malloc(ar_ptr
, bytes
);
3654 (void)mutex_unlock(&ar_ptr
->mutex
);
3659 (void)mutex_unlock(&ar_ptr
->mutex
);
3660 assert(!victim
|| chunk_is_mmapped(mem2chunk(victim
)) ||
3661 ar_ptr
== arena_for_chunk(mem2chunk(victim
)));
3664 #ifdef libc_hidden_def
3665 libc_hidden_def(public_mALLOc
)
3669 public_fREe(Void_t
* mem
)
3672 mchunkptr p
; /* chunk corresponding to mem */
3674 void (*hook
) (__malloc_ptr_t
, __const __malloc_ptr_t
)
3675 = force_reg (__free_hook
);
3676 if (__builtin_expect (hook
!= NULL
, 0)) {
3677 (*hook
)(mem
, RETURN_ADDRESS (0));
3681 if (mem
== 0) /* free(0) has no effect */
3687 if (chunk_is_mmapped(p
)) /* release mmapped memory. */
3689 /* see if the dynamic brk/mmap threshold needs adjusting */
3690 if (!mp_
.no_dyn_threshold
3691 && p
->size
> mp_
.mmap_threshold
3692 && p
->size
<= DEFAULT_MMAP_THRESHOLD_MAX
)
3694 mp_
.mmap_threshold
= chunksize (p
);
3695 mp_
.trim_threshold
= 2 * mp_
.mmap_threshold
;
3702 ar_ptr
= arena_for_chunk(p
);
3703 #ifdef ATOMIC_FASTBINS
3704 _int_free(ar_ptr
, p
, 0);
3707 if(!mutex_trylock(&ar_ptr
->mutex
))
3708 ++(ar_ptr
->stat_lock_direct
);
3710 (void)mutex_lock(&ar_ptr
->mutex
);
3711 ++(ar_ptr
->stat_lock_wait
);
3714 (void)mutex_lock(&ar_ptr
->mutex
);
3716 _int_free(ar_ptr
, p
);
3717 (void)mutex_unlock(&ar_ptr
->mutex
);
3720 #ifdef libc_hidden_def
3721 libc_hidden_def (public_fREe
)
3725 public_rEALLOc(Void_t
* oldmem
, size_t bytes
)
3728 INTERNAL_SIZE_T nb
; /* padded request size */
3730 Void_t
* newp
; /* chunk to return */
3732 __malloc_ptr_t (*hook
) (__malloc_ptr_t
, size_t, __const __malloc_ptr_t
) =
3733 force_reg (__realloc_hook
);
3734 if (__builtin_expect (hook
!= NULL
, 0))
3735 return (*hook
)(oldmem
, bytes
, RETURN_ADDRESS (0));
3737 #if REALLOC_ZERO_BYTES_FREES
3738 if (bytes
== 0 && oldmem
!= NULL
) { public_fREe(oldmem
); return 0; }
3741 /* realloc of null is supposed to be same as malloc */
3742 if (oldmem
== 0) return public_mALLOc(bytes
);
3744 /* chunk corresponding to oldmem */
3745 const mchunkptr oldp
= mem2chunk(oldmem
);
3747 const INTERNAL_SIZE_T oldsize
= chunksize(oldp
);
3749 /* Little security check which won't hurt performance: the
3750 allocator never wrapps around at the end of the address space.
3751 Therefore we can exclude some size values which might appear
3752 here by accident or by "design" from some intruder. */
3753 if (__builtin_expect ((uintptr_t) oldp
> (uintptr_t) -oldsize
, 0)
3754 || __builtin_expect (misaligned_chunk (oldp
), 0))
3756 malloc_printerr (check_action
, "realloc(): invalid pointer", oldmem
);
3760 checked_request2size(bytes
, nb
);
3763 if (chunk_is_mmapped(oldp
))
3768 newp
= mremap_chunk(oldp
, nb
);
3769 if(newp
) return chunk2mem(newp
);
3771 /* Note the extra SIZE_SZ overhead. */
3772 if(oldsize
- SIZE_SZ
>= nb
) return oldmem
; /* do nothing */
3773 /* Must alloc, copy, free. */
3774 newmem
= public_mALLOc(bytes
);
3775 if (newmem
== 0) return 0; /* propagate failure */
3776 MALLOC_COPY(newmem
, oldmem
, oldsize
- 2*SIZE_SZ
);
3782 ar_ptr
= arena_for_chunk(oldp
);
3784 if(!mutex_trylock(&ar_ptr
->mutex
))
3785 ++(ar_ptr
->stat_lock_direct
);
3787 (void)mutex_lock(&ar_ptr
->mutex
);
3788 ++(ar_ptr
->stat_lock_wait
);
3791 (void)mutex_lock(&ar_ptr
->mutex
);
3794 #if !defined NO_THREADS && !defined PER_THREAD
3795 /* As in malloc(), remember this arena for the next allocation. */
3796 tsd_setspecific(arena_key
, (Void_t
*)ar_ptr
);
3799 newp
= _int_realloc(ar_ptr
, oldp
, oldsize
, nb
);
3801 (void)mutex_unlock(&ar_ptr
->mutex
);
3802 assert(!newp
|| chunk_is_mmapped(mem2chunk(newp
)) ||
3803 ar_ptr
== arena_for_chunk(mem2chunk(newp
)));
3807 /* Try harder to allocate memory in other arenas. */
3808 newp
= public_mALLOc(bytes
);
3811 MALLOC_COPY (newp
, oldmem
, oldsize
- SIZE_SZ
);
3812 #ifdef ATOMIC_FASTBINS
3813 _int_free(ar_ptr
, oldp
, 0);
3816 if(!mutex_trylock(&ar_ptr
->mutex
))
3817 ++(ar_ptr
->stat_lock_direct
);
3819 (void)mutex_lock(&ar_ptr
->mutex
);
3820 ++(ar_ptr
->stat_lock_wait
);
3823 (void)mutex_lock(&ar_ptr
->mutex
);
3825 _int_free(ar_ptr
, oldp
);
3826 (void)mutex_unlock(&ar_ptr
->mutex
);
3833 #ifdef libc_hidden_def
3834 libc_hidden_def (public_rEALLOc
)
3838 public_mEMALIGn(size_t alignment
, size_t bytes
)
3843 __malloc_ptr_t (*hook
) __MALLOC_PMT ((size_t, size_t,
3844 __const __malloc_ptr_t
)) =
3845 force_reg (__memalign_hook
);
3846 if (__builtin_expect (hook
!= NULL
, 0))
3847 return (*hook
)(alignment
, bytes
, RETURN_ADDRESS (0));
3849 /* If need less alignment than we give anyway, just relay to malloc */
3850 if (alignment
<= MALLOC_ALIGNMENT
) return public_mALLOc(bytes
);
3852 /* Otherwise, ensure that it is at least a minimum chunk size */
3853 if (alignment
< MINSIZE
) alignment
= MINSIZE
;
3855 arena_get(ar_ptr
, bytes
+ alignment
+ MINSIZE
);
3858 p
= _int_memalign(ar_ptr
, alignment
, bytes
);
3860 /* Maybe the failure is due to running out of mmapped areas. */
3861 if(ar_ptr
!= &main_arena
) {
3862 (void)mutex_unlock(&ar_ptr
->mutex
);
3863 ar_ptr
= &main_arena
;
3864 (void)mutex_lock(&ar_ptr
->mutex
);
3865 p
= _int_memalign(ar_ptr
, alignment
, bytes
);
3866 (void)mutex_unlock(&ar_ptr
->mutex
);
3869 /* ... or sbrk() has failed and there is still a chance to mmap() */
3870 mstate prev
= ar_ptr
->next
? ar_ptr
: 0;
3871 (void)mutex_unlock(&ar_ptr
->mutex
);
3872 ar_ptr
= arena_get2(prev
, bytes
);
3874 p
= _int_memalign(ar_ptr
, alignment
, bytes
);
3875 (void)mutex_unlock(&ar_ptr
->mutex
);
3880 (void)mutex_unlock(&ar_ptr
->mutex
);
3881 assert(!p
|| chunk_is_mmapped(mem2chunk(p
)) ||
3882 ar_ptr
== arena_for_chunk(mem2chunk(p
)));
3885 #ifdef libc_hidden_def
3886 libc_hidden_def (public_mEMALIGn
)
3890 public_vALLOc(size_t bytes
)
3895 if(__malloc_initialized
< 0)
3898 size_t pagesz
= mp_
.pagesize
;
3900 __malloc_ptr_t (*hook
) __MALLOC_PMT ((size_t, size_t,
3901 __const __malloc_ptr_t
)) =
3902 force_reg (__memalign_hook
);
3903 if (__builtin_expect (hook
!= NULL
, 0))
3904 return (*hook
)(pagesz
, bytes
, RETURN_ADDRESS (0));
3906 arena_get(ar_ptr
, bytes
+ pagesz
+ MINSIZE
);
3909 p
= _int_valloc(ar_ptr
, bytes
);
3910 (void)mutex_unlock(&ar_ptr
->mutex
);
3912 /* Maybe the failure is due to running out of mmapped areas. */
3913 if(ar_ptr
!= &main_arena
) {
3914 (void)mutex_lock(&main_arena
.mutex
);
3915 p
= _int_memalign(&main_arena
, pagesz
, bytes
);
3916 (void)mutex_unlock(&main_arena
.mutex
);
3919 /* ... or sbrk() has failed and there is still a chance to mmap() */
3920 ar_ptr
= arena_get2(ar_ptr
->next
? ar_ptr
: 0, bytes
);
3922 p
= _int_memalign(ar_ptr
, pagesz
, bytes
);
3923 (void)mutex_unlock(&ar_ptr
->mutex
);
3928 assert(!p
|| chunk_is_mmapped(mem2chunk(p
)) ||
3929 ar_ptr
== arena_for_chunk(mem2chunk(p
)));
3935 public_pVALLOc(size_t bytes
)
3940 if(__malloc_initialized
< 0)
3943 size_t pagesz
= mp_
.pagesize
;
3944 size_t page_mask
= mp_
.pagesize
- 1;
3945 size_t rounded_bytes
= (bytes
+ page_mask
) & ~(page_mask
);
3947 __malloc_ptr_t (*hook
) __MALLOC_PMT ((size_t, size_t,
3948 __const __malloc_ptr_t
)) =
3949 force_reg (__memalign_hook
);
3950 if (__builtin_expect (hook
!= NULL
, 0))
3951 return (*hook
)(pagesz
, rounded_bytes
, RETURN_ADDRESS (0));
3953 arena_get(ar_ptr
, bytes
+ 2*pagesz
+ MINSIZE
);
3954 p
= _int_pvalloc(ar_ptr
, bytes
);
3955 (void)mutex_unlock(&ar_ptr
->mutex
);
3957 /* Maybe the failure is due to running out of mmapped areas. */
3958 if(ar_ptr
!= &main_arena
) {
3959 (void)mutex_lock(&main_arena
.mutex
);
3960 p
= _int_memalign(&main_arena
, pagesz
, rounded_bytes
);
3961 (void)mutex_unlock(&main_arena
.mutex
);
3964 /* ... or sbrk() has failed and there is still a chance to mmap() */
3965 ar_ptr
= arena_get2(ar_ptr
->next
? ar_ptr
: 0,
3966 bytes
+ 2*pagesz
+ MINSIZE
);
3968 p
= _int_memalign(ar_ptr
, pagesz
, rounded_bytes
);
3969 (void)mutex_unlock(&ar_ptr
->mutex
);
3974 assert(!p
|| chunk_is_mmapped(mem2chunk(p
)) ||
3975 ar_ptr
== arena_for_chunk(mem2chunk(p
)));
3981 public_cALLOc(size_t n
, size_t elem_size
)
3984 mchunkptr oldtop
, p
;
3985 INTERNAL_SIZE_T bytes
, sz
, csz
, oldtopsize
;
3987 unsigned long clearsize
;
3988 unsigned long nclears
;
3991 /* size_t is unsigned so the behavior on overflow is defined. */
3992 bytes
= n
* elem_size
;
3993 #define HALF_INTERNAL_SIZE_T \
3994 (((INTERNAL_SIZE_T) 1) << (8 * sizeof (INTERNAL_SIZE_T) / 2))
3995 if (__builtin_expect ((n
| elem_size
) >= HALF_INTERNAL_SIZE_T
, 0)) {
3996 if (elem_size
!= 0 && bytes
/ elem_size
!= n
) {
3997 MALLOC_FAILURE_ACTION
;
4002 __malloc_ptr_t (*hook
) __MALLOC_PMT ((size_t, __const __malloc_ptr_t
)) =
4003 force_reg (__malloc_hook
);
4004 if (__builtin_expect (hook
!= NULL
, 0)) {
4006 mem
= (*hook
)(sz
, RETURN_ADDRESS (0));
4010 return memset(mem
, 0, sz
);
4012 while(sz
> 0) ((char*)mem
)[--sz
] = 0; /* rather inefficient */
4023 /* Check if we hand out the top chunk, in which case there may be no
4027 oldtopsize
= chunksize(top(av
));
4028 #if MORECORE_CLEARS < 2
4029 /* Only newly allocated memory is guaranteed to be cleared. */
4030 if (av
== &main_arena
&&
4031 oldtopsize
< mp_
.sbrk_base
+ av
->max_system_mem
- (char *)oldtop
)
4032 oldtopsize
= (mp_
.sbrk_base
+ av
->max_system_mem
- (char *)oldtop
);
4034 if (av
!= &main_arena
)
4036 heap_info
*heap
= heap_for_ptr (oldtop
);
4037 if (oldtopsize
< (char *) heap
+ heap
->mprotect_size
- (char *) oldtop
)
4038 oldtopsize
= (char *) heap
+ heap
->mprotect_size
- (char *) oldtop
;
4041 mem
= _int_malloc(av
, sz
);
4043 /* Only clearing follows, so we can unlock early. */
4044 (void)mutex_unlock(&av
->mutex
);
4046 assert(!mem
|| chunk_is_mmapped(mem2chunk(mem
)) ||
4047 av
== arena_for_chunk(mem2chunk(mem
)));
4050 /* Maybe the failure is due to running out of mmapped areas. */
4051 if(av
!= &main_arena
) {
4052 (void)mutex_lock(&main_arena
.mutex
);
4053 mem
= _int_malloc(&main_arena
, sz
);
4054 (void)mutex_unlock(&main_arena
.mutex
);
4057 /* ... or sbrk() has failed and there is still a chance to mmap() */
4058 (void)mutex_lock(&main_arena
.mutex
);
4059 av
= arena_get2(av
->next
? av
: 0, sz
);
4060 (void)mutex_unlock(&main_arena
.mutex
);
4062 mem
= _int_malloc(av
, sz
);
4063 (void)mutex_unlock(&av
->mutex
);
4067 if (mem
== 0) return 0;
4071 /* Two optional cases in which clearing not necessary */
4073 if (chunk_is_mmapped (p
))
4075 if (__builtin_expect (perturb_byte
, 0))
4076 MALLOC_ZERO (mem
, sz
);
4084 if (perturb_byte
== 0 && (p
== oldtop
&& csz
> oldtopsize
)) {
4085 /* clear only the bytes from non-freshly-sbrked memory */
4090 /* Unroll clear of <= 36 bytes (72 if 8byte sizes). We know that
4091 contents have an odd number of INTERNAL_SIZE_T-sized words;
4093 d
= (INTERNAL_SIZE_T
*)mem
;
4094 clearsize
= csz
- SIZE_SZ
;
4095 nclears
= clearsize
/ sizeof(INTERNAL_SIZE_T
);
4096 assert(nclears
>= 3);
4099 MALLOC_ZERO(d
, clearsize
);
4125 public_iCALLOc(size_t n
, size_t elem_size
, Void_t
** chunks
)
4130 arena_get(ar_ptr
, n
*elem_size
);
4134 m
= _int_icalloc(ar_ptr
, n
, elem_size
, chunks
);
4135 (void)mutex_unlock(&ar_ptr
->mutex
);
4140 public_iCOMALLOc(size_t n
, size_t sizes
[], Void_t
** chunks
)
4145 arena_get(ar_ptr
, 0);
4149 m
= _int_icomalloc(ar_ptr
, n
, sizes
, chunks
);
4150 (void)mutex_unlock(&ar_ptr
->mutex
);
4155 public_cFREe(Void_t
* m
)
4163 public_mTRIm(size_t s
)
4167 if(__malloc_initialized
< 0)
4170 mstate ar_ptr
= &main_arena
;
4173 (void) mutex_lock (&ar_ptr
->mutex
);
4174 result
|= mTRIm (ar_ptr
, s
);
4175 (void) mutex_unlock (&ar_ptr
->mutex
);
4177 ar_ptr
= ar_ptr
->next
;
4179 while (ar_ptr
!= &main_arena
);
4185 public_mUSABLe(Void_t
* m
)
4189 result
= mUSABLe(m
);
4199 struct mallinfo
public_mALLINFo()
4203 if(__malloc_initialized
< 0)
4205 (void)mutex_lock(&main_arena
.mutex
);
4206 m
= mALLINFo(&main_arena
);
4207 (void)mutex_unlock(&main_arena
.mutex
);
4212 public_mALLOPt(int p
, int v
)
4215 result
= mALLOPt(p
, v
);
4220 ------------------------------ malloc ------------------------------
4224 _int_malloc(mstate av
, size_t bytes
)
4226 INTERNAL_SIZE_T nb
; /* normalized request size */
4227 unsigned int idx
; /* associated bin index */
4228 mbinptr bin
; /* associated bin */
4230 mchunkptr victim
; /* inspected/selected chunk */
4231 INTERNAL_SIZE_T size
; /* its size */
4232 int victim_index
; /* its bin index */
4234 mchunkptr remainder
; /* remainder from a split */
4235 unsigned long remainder_size
; /* its size */
4237 unsigned int block
; /* bit map traverser */
4238 unsigned int bit
; /* bit map traverser */
4239 unsigned int map
; /* current word of binmap */
4241 mchunkptr fwd
; /* misc temp for linking */
4242 mchunkptr bck
; /* misc temp for linking */
4244 const char *errstr
= NULL
;
4247 Convert request size to internal form by adding SIZE_SZ bytes
4248 overhead plus possibly more to obtain necessary alignment and/or
4249 to obtain a size of at least MINSIZE, the smallest allocatable
4250 size. Also, checked_request2size traps (returning 0) request sizes
4251 that are so large that they wrap around zero when padded and
4255 checked_request2size(bytes
, nb
);
4258 If the size qualifies as a fastbin, first check corresponding bin.
4259 This code is safe to execute even if av is not yet initialized, so we
4260 can try it without checking, which saves some time on this fast path.
4263 if ((unsigned long)(nb
) <= (unsigned long)(get_max_fast ())) {
4264 idx
= fastbin_index(nb
);
4265 mfastbinptr
* fb
= &fastbin (av
, idx
);
4266 #ifdef ATOMIC_FASTBINS
4274 while ((pp
= catomic_compare_and_exchange_val_acq (fb
, victim
->fd
, victim
))
4280 if (__builtin_expect (fastbin_index (chunksize (victim
)) != idx
, 0))
4282 errstr
= "malloc(): memory corruption (fast)";
4284 malloc_printerr (check_action
, errstr
, chunk2mem (victim
));
4286 #ifndef ATOMIC_FASTBINS
4289 check_remalloced_chunk(av
, victim
, nb
);
4290 void *p
= chunk2mem(victim
);
4291 if (__builtin_expect (perturb_byte
, 0))
4292 alloc_perturb (p
, bytes
);
4298 If a small request, check regular bin. Since these "smallbins"
4299 hold one size each, no searching within bins is necessary.
4300 (For a large request, we need to wait until unsorted chunks are
4301 processed to find best fit. But for small ones, fits are exact
4302 anyway, so we can check now, which is faster.)
4305 if (in_smallbin_range(nb
)) {
4306 idx
= smallbin_index(nb
);
4307 bin
= bin_at(av
,idx
);
4309 if ( (victim
= last(bin
)) != bin
) {
4310 if (victim
== 0) /* initialization check */
4311 malloc_consolidate(av
);
4314 if (__builtin_expect (bck
->fd
!= victim
, 0))
4316 errstr
= "malloc(): smallbin double linked list corrupted";
4319 set_inuse_bit_at_offset(victim
, nb
);
4323 if (av
!= &main_arena
)
4324 victim
->size
|= NON_MAIN_ARENA
;
4325 check_malloced_chunk(av
, victim
, nb
);
4326 void *p
= chunk2mem(victim
);
4327 if (__builtin_expect (perturb_byte
, 0))
4328 alloc_perturb (p
, bytes
);
4335 If this is a large request, consolidate fastbins before continuing.
4336 While it might look excessive to kill all fastbins before
4337 even seeing if there is space available, this avoids
4338 fragmentation problems normally associated with fastbins.
4339 Also, in practice, programs tend to have runs of either small or
4340 large requests, but less often mixtures, so consolidation is not
4341 invoked all that often in most programs. And the programs that
4342 it is called frequently in otherwise tend to fragment.
4346 idx
= largebin_index(nb
);
4347 if (have_fastchunks(av
))
4348 malloc_consolidate(av
);
4352 Process recently freed or remaindered chunks, taking one only if
4353 it is exact fit, or, if this a small request, the chunk is remainder from
4354 the most recent non-exact fit. Place other traversed chunks in
4355 bins. Note that this step is the only place in any routine where
4356 chunks are placed in bins.
4358 The outer loop here is needed because we might not realize until
4359 near the end of malloc that we should have consolidated, so must
4360 do so and retry. This happens at most once, and only when we would
4361 otherwise need to expand memory to service a "small" request.
4367 while ( (victim
= unsorted_chunks(av
)->bk
) != unsorted_chunks(av
)) {
4369 if (__builtin_expect (victim
->size
<= 2 * SIZE_SZ
, 0)
4370 || __builtin_expect (victim
->size
> av
->system_mem
, 0))
4371 malloc_printerr (check_action
, "malloc(): memory corruption",
4372 chunk2mem (victim
));
4373 size
= chunksize(victim
);
4376 If a small request, try to use last remainder if it is the
4377 only chunk in unsorted bin. This helps promote locality for
4378 runs of consecutive small requests. This is the only
4379 exception to best-fit, and applies only when there is
4380 no exact fit for a small chunk.
4383 if (in_smallbin_range(nb
) &&
4384 bck
== unsorted_chunks(av
) &&
4385 victim
== av
->last_remainder
&&
4386 (unsigned long)(size
) > (unsigned long)(nb
+ MINSIZE
)) {
4388 /* split and reattach remainder */
4389 remainder_size
= size
- nb
;
4390 remainder
= chunk_at_offset(victim
, nb
);
4391 unsorted_chunks(av
)->bk
= unsorted_chunks(av
)->fd
= remainder
;
4392 av
->last_remainder
= remainder
;
4393 remainder
->bk
= remainder
->fd
= unsorted_chunks(av
);
4394 if (!in_smallbin_range(remainder_size
))
4396 remainder
->fd_nextsize
= NULL
;
4397 remainder
->bk_nextsize
= NULL
;
4400 set_head(victim
, nb
| PREV_INUSE
|
4401 (av
!= &main_arena
? NON_MAIN_ARENA
: 0));
4402 set_head(remainder
, remainder_size
| PREV_INUSE
);
4403 set_foot(remainder
, remainder_size
);
4405 check_malloced_chunk(av
, victim
, nb
);
4406 void *p
= chunk2mem(victim
);
4407 if (__builtin_expect (perturb_byte
, 0))
4408 alloc_perturb (p
, bytes
);
4412 /* remove from unsorted list */
4413 unsorted_chunks(av
)->bk
= bck
;
4414 bck
->fd
= unsorted_chunks(av
);
4416 /* Take now instead of binning if exact fit */
4419 set_inuse_bit_at_offset(victim
, size
);
4420 if (av
!= &main_arena
)
4421 victim
->size
|= NON_MAIN_ARENA
;
4422 check_malloced_chunk(av
, victim
, nb
);
4423 void *p
= chunk2mem(victim
);
4424 if (__builtin_expect (perturb_byte
, 0))
4425 alloc_perturb (p
, bytes
);
4429 /* place chunk in bin */
4431 if (in_smallbin_range(size
)) {
4432 victim_index
= smallbin_index(size
);
4433 bck
= bin_at(av
, victim_index
);
4437 victim_index
= largebin_index(size
);
4438 bck
= bin_at(av
, victim_index
);
4441 /* maintain large bins in sorted order */
4443 /* Or with inuse bit to speed comparisons */
4445 /* if smaller than smallest, bypass loop below */
4446 assert((bck
->bk
->size
& NON_MAIN_ARENA
) == 0);
4447 if ((unsigned long)(size
) < (unsigned long)(bck
->bk
->size
)) {
4451 victim
->fd_nextsize
= fwd
->fd
;
4452 victim
->bk_nextsize
= fwd
->fd
->bk_nextsize
;
4453 fwd
->fd
->bk_nextsize
= victim
->bk_nextsize
->fd_nextsize
= victim
;
4456 assert((fwd
->size
& NON_MAIN_ARENA
) == 0);
4457 while ((unsigned long) size
< fwd
->size
)
4459 fwd
= fwd
->fd_nextsize
;
4460 assert((fwd
->size
& NON_MAIN_ARENA
) == 0);
4463 if ((unsigned long) size
== (unsigned long) fwd
->size
)
4464 /* Always insert in the second position. */
4468 victim
->fd_nextsize
= fwd
;
4469 victim
->bk_nextsize
= fwd
->bk_nextsize
;
4470 fwd
->bk_nextsize
= victim
;
4471 victim
->bk_nextsize
->fd_nextsize
= victim
;
4476 victim
->fd_nextsize
= victim
->bk_nextsize
= victim
;
4479 mark_bin(av
, victim_index
);
4485 #define MAX_ITERS 10000
4486 if (++iters
>= MAX_ITERS
)
4491 If a large request, scan through the chunks of current bin in
4492 sorted order to find smallest that fits. Use the skip list for this.
4495 if (!in_smallbin_range(nb
)) {
4496 bin
= bin_at(av
, idx
);
4498 /* skip scan if empty or largest chunk is too small */
4499 if ((victim
= first(bin
)) != bin
&&
4500 (unsigned long)(victim
->size
) >= (unsigned long)(nb
)) {
4502 victim
= victim
->bk_nextsize
;
4503 while (((unsigned long)(size
= chunksize(victim
)) <
4504 (unsigned long)(nb
)))
4505 victim
= victim
->bk_nextsize
;
4507 /* Avoid removing the first entry for a size so that the skip
4508 list does not have to be rerouted. */
4509 if (victim
!= last(bin
) && victim
->size
== victim
->fd
->size
)
4510 victim
= victim
->fd
;
4512 remainder_size
= size
- nb
;
4513 unlink(victim
, bck
, fwd
);
4516 if (remainder_size
< MINSIZE
) {
4517 set_inuse_bit_at_offset(victim
, size
);
4518 if (av
!= &main_arena
)
4519 victim
->size
|= NON_MAIN_ARENA
;
4523 remainder
= chunk_at_offset(victim
, nb
);
4524 /* We cannot assume the unsorted list is empty and therefore
4525 have to perform a complete insert here. */
4526 bck
= unsorted_chunks(av
);
4528 if (__builtin_expect (fwd
->bk
!= bck
, 0))
4530 errstr
= "malloc(): corrupted unsorted chunks";
4533 remainder
->bk
= bck
;
4534 remainder
->fd
= fwd
;
4535 bck
->fd
= remainder
;
4536 fwd
->bk
= remainder
;
4537 if (!in_smallbin_range(remainder_size
))
4539 remainder
->fd_nextsize
= NULL
;
4540 remainder
->bk_nextsize
= NULL
;
4542 set_head(victim
, nb
| PREV_INUSE
|
4543 (av
!= &main_arena
? NON_MAIN_ARENA
: 0));
4544 set_head(remainder
, remainder_size
| PREV_INUSE
);
4545 set_foot(remainder
, remainder_size
);
4547 check_malloced_chunk(av
, victim
, nb
);
4548 void *p
= chunk2mem(victim
);
4549 if (__builtin_expect (perturb_byte
, 0))
4550 alloc_perturb (p
, bytes
);
4556 Search for a chunk by scanning bins, starting with next largest
4557 bin. This search is strictly by best-fit; i.e., the smallest
4558 (with ties going to approximately the least recently used) chunk
4559 that fits is selected.
4561 The bitmap avoids needing to check that most blocks are nonempty.
4562 The particular case of skipping all bins during warm-up phases
4563 when no chunks have been returned yet is faster than it might look.
4567 bin
= bin_at(av
,idx
);
4568 block
= idx2block(idx
);
4569 map
= av
->binmap
[block
];
4574 /* Skip rest of block if there are no more set bits in this block. */
4575 if (bit
> map
|| bit
== 0) {
4577 if (++block
>= BINMAPSIZE
) /* out of bins */
4579 } while ( (map
= av
->binmap
[block
]) == 0);
4581 bin
= bin_at(av
, (block
<< BINMAPSHIFT
));
4585 /* Advance to bin with set bit. There must be one. */
4586 while ((bit
& map
) == 0) {
4587 bin
= next_bin(bin
);
4592 /* Inspect the bin. It is likely to be non-empty */
4595 /* If a false alarm (empty bin), clear the bit. */
4596 if (victim
== bin
) {
4597 av
->binmap
[block
] = map
&= ~bit
; /* Write through */
4598 bin
= next_bin(bin
);
4603 size
= chunksize(victim
);
4605 /* We know the first chunk in this bin is big enough to use. */
4606 assert((unsigned long)(size
) >= (unsigned long)(nb
));
4608 remainder_size
= size
- nb
;
4611 unlink(victim
, bck
, fwd
);
4614 if (remainder_size
< MINSIZE
) {
4615 set_inuse_bit_at_offset(victim
, size
);
4616 if (av
!= &main_arena
)
4617 victim
->size
|= NON_MAIN_ARENA
;
4622 remainder
= chunk_at_offset(victim
, nb
);
4624 /* We cannot assume the unsorted list is empty and therefore
4625 have to perform a complete insert here. */
4626 bck
= unsorted_chunks(av
);
4628 if (__builtin_expect (fwd
->bk
!= bck
, 0))
4630 errstr
= "malloc(): corrupted unsorted chunks 2";
4633 remainder
->bk
= bck
;
4634 remainder
->fd
= fwd
;
4635 bck
->fd
= remainder
;
4636 fwd
->bk
= remainder
;
4638 /* advertise as last remainder */
4639 if (in_smallbin_range(nb
))
4640 av
->last_remainder
= remainder
;
4641 if (!in_smallbin_range(remainder_size
))
4643 remainder
->fd_nextsize
= NULL
;
4644 remainder
->bk_nextsize
= NULL
;
4646 set_head(victim
, nb
| PREV_INUSE
|
4647 (av
!= &main_arena
? NON_MAIN_ARENA
: 0));
4648 set_head(remainder
, remainder_size
| PREV_INUSE
);
4649 set_foot(remainder
, remainder_size
);
4651 check_malloced_chunk(av
, victim
, nb
);
4652 void *p
= chunk2mem(victim
);
4653 if (__builtin_expect (perturb_byte
, 0))
4654 alloc_perturb (p
, bytes
);
4661 If large enough, split off the chunk bordering the end of memory
4662 (held in av->top). Note that this is in accord with the best-fit
4663 search rule. In effect, av->top is treated as larger (and thus
4664 less well fitting) than any other available chunk since it can
4665 be extended to be as large as necessary (up to system
4668 We require that av->top always exists (i.e., has size >=
4669 MINSIZE) after initialization, so if it would otherwise be
4670 exhausted by current request, it is replenished. (The main
4671 reason for ensuring it exists is that we may need MINSIZE space
4672 to put in fenceposts in sysmalloc.)
4676 size
= chunksize(victim
);
4678 if ((unsigned long)(size
) >= (unsigned long)(nb
+ MINSIZE
)) {
4679 remainder_size
= size
- nb
;
4680 remainder
= chunk_at_offset(victim
, nb
);
4681 av
->top
= remainder
;
4682 set_head(victim
, nb
| PREV_INUSE
|
4683 (av
!= &main_arena
? NON_MAIN_ARENA
: 0));
4684 set_head(remainder
, remainder_size
| PREV_INUSE
);
4686 check_malloced_chunk(av
, victim
, nb
);
4687 void *p
= chunk2mem(victim
);
4688 if (__builtin_expect (perturb_byte
, 0))
4689 alloc_perturb (p
, bytes
);
4693 #ifdef ATOMIC_FASTBINS
4694 /* When we are using atomic ops to free fast chunks we can get
4695 here for all block sizes. */
4696 else if (have_fastchunks(av
)) {
4697 malloc_consolidate(av
);
4698 /* restore original bin index */
4699 if (in_smallbin_range(nb
))
4700 idx
= smallbin_index(nb
);
4702 idx
= largebin_index(nb
);
4706 If there is space available in fastbins, consolidate and retry,
4707 to possibly avoid expanding memory. This can occur only if nb is
4708 in smallbin range so we didn't consolidate upon entry.
4711 else if (have_fastchunks(av
)) {
4712 assert(in_smallbin_range(nb
));
4713 malloc_consolidate(av
);
4714 idx
= smallbin_index(nb
); /* restore original bin index */
4719 Otherwise, relay to handle system-dependent cases
4722 void *p
= sYSMALLOc(nb
, av
);
4723 if (p
!= NULL
&& __builtin_expect (perturb_byte
, 0))
4724 alloc_perturb (p
, bytes
);
4731 ------------------------------ free ------------------------------
4735 #ifdef ATOMIC_FASTBINS
4736 _int_free(mstate av
, mchunkptr p
, int have_lock
)
4738 _int_free(mstate av
, mchunkptr p
)
4741 INTERNAL_SIZE_T size
; /* its size */
4742 mfastbinptr
* fb
; /* associated fastbin */
4743 mchunkptr nextchunk
; /* next contiguous chunk */
4744 INTERNAL_SIZE_T nextsize
; /* its size */
4745 int nextinuse
; /* true if nextchunk is used */
4746 INTERNAL_SIZE_T prevsize
; /* size of previous contiguous chunk */
4747 mchunkptr bck
; /* misc temp for linking */
4748 mchunkptr fwd
; /* misc temp for linking */
4750 const char *errstr
= NULL
;
4751 #ifdef ATOMIC_FASTBINS
4755 size
= chunksize(p
);
4757 /* Little security check which won't hurt performance: the
4758 allocator never wrapps around at the end of the address space.
4759 Therefore we can exclude some size values which might appear
4760 here by accident or by "design" from some intruder. */
4761 if (__builtin_expect ((uintptr_t) p
> (uintptr_t) -size
, 0)
4762 || __builtin_expect (misaligned_chunk (p
), 0))
4764 errstr
= "free(): invalid pointer";
4766 #ifdef ATOMIC_FASTBINS
4767 if (! have_lock
&& locked
)
4768 (void)mutex_unlock(&av
->mutex
);
4770 malloc_printerr (check_action
, errstr
, chunk2mem(p
));
4773 /* We know that each chunk is at least MINSIZE bytes in size. */
4774 if (__builtin_expect (size
< MINSIZE
, 0))
4776 errstr
= "free(): invalid size";
4780 check_inuse_chunk(av
, p
);
4783 If eligible, place chunk on a fastbin so it can be found
4784 and used quickly in malloc.
4787 if ((unsigned long)(size
) <= (unsigned long)(get_max_fast ())
4791 If TRIM_FASTBINS set, don't place chunks
4792 bordering top into fastbins
4794 && (chunk_at_offset(p
, size
) != av
->top
)
4798 if (__builtin_expect (chunk_at_offset (p
, size
)->size
<= 2 * SIZE_SZ
, 0)
4799 || __builtin_expect (chunksize (chunk_at_offset (p
, size
))
4800 >= av
->system_mem
, 0))
4802 #ifdef ATOMIC_FASTBINS
4803 /* We might not have a lock at this point and concurrent modifications
4804 of system_mem might have let to a false positive. Redo the test
4805 after getting the lock. */
4807 || ({ assert (locked
== 0);
4808 mutex_lock(&av
->mutex
);
4810 chunk_at_offset (p
, size
)->size
<= 2 * SIZE_SZ
4811 || chunksize (chunk_at_offset (p
, size
)) >= av
->system_mem
;
4815 errstr
= "free(): invalid next size (fast)";
4818 #ifdef ATOMIC_FASTBINS
4821 (void)mutex_unlock(&av
->mutex
);
4827 if (__builtin_expect (perturb_byte
, 0))
4828 free_perturb (chunk2mem(p
), size
- SIZE_SZ
);
4831 fb
= &fastbin (av
, fastbin_index(size
));
4833 #ifdef ATOMIC_FASTBINS
4835 mchunkptr old
= *fb
;
4838 /* Another simple check: make sure the top of the bin is not the
4839 record we are going to add (i.e., double free). */
4840 if (__builtin_expect (old
== p
, 0))
4842 errstr
= "double free or corruption (fasttop)";
4847 while ((old
= catomic_compare_and_exchange_val_rel (fb
, p
, fd
)) != fd
);
4849 /* Another simple check: make sure the top of the bin is not the
4850 record we are going to add (i.e., double free). */
4851 if (__builtin_expect (*fb
== p
, 0))
4853 errstr
= "double free or corruption (fasttop)";
4863 Consolidate other non-mmapped chunks as they arrive.
4866 else if (!chunk_is_mmapped(p
)) {
4867 #ifdef ATOMIC_FASTBINS
4870 if(!mutex_trylock(&av
->mutex
))
4871 ++(av
->stat_lock_direct
);
4873 (void)mutex_lock(&av
->mutex
);
4874 ++(av
->stat_lock_wait
);
4877 (void)mutex_lock(&av
->mutex
);
4883 nextchunk
= chunk_at_offset(p
, size
);
4885 /* Lightweight tests: check whether the block is already the
4887 if (__builtin_expect (p
== av
->top
, 0))
4889 errstr
= "double free or corruption (top)";
4892 /* Or whether the next chunk is beyond the boundaries of the arena. */
4893 if (__builtin_expect (contiguous (av
)
4894 && (char *) nextchunk
4895 >= ((char *) av
->top
+ chunksize(av
->top
)), 0))
4897 errstr
= "double free or corruption (out)";
4900 /* Or whether the block is actually not marked used. */
4901 if (__builtin_expect (!prev_inuse(nextchunk
), 0))
4903 errstr
= "double free or corruption (!prev)";
4907 nextsize
= chunksize(nextchunk
);
4908 if (__builtin_expect (nextchunk
->size
<= 2 * SIZE_SZ
, 0)
4909 || __builtin_expect (nextsize
>= av
->system_mem
, 0))
4911 errstr
= "free(): invalid next size (normal)";
4915 if (__builtin_expect (perturb_byte
, 0))
4916 free_perturb (chunk2mem(p
), size
- SIZE_SZ
);
4918 /* consolidate backward */
4919 if (!prev_inuse(p
)) {
4920 prevsize
= p
->prev_size
;
4922 p
= chunk_at_offset(p
, -((long) prevsize
));
4923 unlink(p
, bck
, fwd
);
4926 if (nextchunk
!= av
->top
) {
4927 /* get and clear inuse bit */
4928 nextinuse
= inuse_bit_at_offset(nextchunk
, nextsize
);
4930 /* consolidate forward */
4932 unlink(nextchunk
, bck
, fwd
);
4935 clear_inuse_bit_at_offset(nextchunk
, 0);
4938 Place the chunk in unsorted chunk list. Chunks are
4939 not placed into regular bins until after they have
4940 been given one chance to be used in malloc.
4943 bck
= unsorted_chunks(av
);
4945 if (__builtin_expect (fwd
->bk
!= bck
, 0))
4947 errstr
= "free(): corrupted unsorted chunks";
4952 if (!in_smallbin_range(size
))
4954 p
->fd_nextsize
= NULL
;
4955 p
->bk_nextsize
= NULL
;
4960 set_head(p
, size
| PREV_INUSE
);
4963 check_free_chunk(av
, p
);
4967 If the chunk borders the current high end of memory,
4968 consolidate into top
4973 set_head(p
, size
| PREV_INUSE
);
4979 If freeing a large space, consolidate possibly-surrounding
4980 chunks. Then, if the total unused topmost memory exceeds trim
4981 threshold, ask malloc_trim to reduce top.
4983 Unless max_fast is 0, we don't know if there are fastbins
4984 bordering top, so we cannot tell for sure whether threshold
4985 has been reached unless fastbins are consolidated. But we
4986 don't want to consolidate on each free. As a compromise,
4987 consolidation is performed if FASTBIN_CONSOLIDATION_THRESHOLD
4991 if ((unsigned long)(size
) >= FASTBIN_CONSOLIDATION_THRESHOLD
) {
4992 if (have_fastchunks(av
))
4993 malloc_consolidate(av
);
4995 if (av
== &main_arena
) {
4996 #ifndef MORECORE_CANNOT_TRIM
4997 if ((unsigned long)(chunksize(av
->top
)) >=
4998 (unsigned long)(mp_
.trim_threshold
))
4999 sYSTRIm(mp_
.top_pad
, av
);
5002 /* Always try heap_trim(), even if the top chunk is not
5003 large, because the corresponding heap might go away. */
5004 heap_info
*heap
= heap_for_ptr(top(av
));
5006 assert(heap
->ar_ptr
== av
);
5007 heap_trim(heap
, mp_
.top_pad
);
5011 #ifdef ATOMIC_FASTBINS
5014 (void)mutex_unlock(&av
->mutex
);
5019 If the chunk was allocated via mmap, release via munmap(). Note
5020 that if HAVE_MMAP is false but chunk_is_mmapped is true, then
5021 user must have overwritten memory. There's nothing we can do to
5022 catch this error unless MALLOC_DEBUG is set, in which case
5023 check_inuse_chunk (above) will have triggered error.
5034 ------------------------- malloc_consolidate -------------------------
5036 malloc_consolidate is a specialized version of free() that tears
5037 down chunks held in fastbins. Free itself cannot be used for this
5038 purpose since, among other things, it might place chunks back onto
5039 fastbins. So, instead, we need to use a minor variant of the same
5042 Also, because this routine needs to be called the first time through
5043 malloc anyway, it turns out to be the perfect place to trigger
5044 initialization code.
5048 static void malloc_consolidate(mstate av
)
5050 static void malloc_consolidate(av
) mstate av
;
5053 mfastbinptr
* fb
; /* current fastbin being consolidated */
5054 mfastbinptr
* maxfb
; /* last fastbin (for loop control) */
5055 mchunkptr p
; /* current chunk being consolidated */
5056 mchunkptr nextp
; /* next chunk to consolidate */
5057 mchunkptr unsorted_bin
; /* bin header */
5058 mchunkptr first_unsorted
; /* chunk to link to */
5060 /* These have same use as in free() */
5061 mchunkptr nextchunk
;
5062 INTERNAL_SIZE_T size
;
5063 INTERNAL_SIZE_T nextsize
;
5064 INTERNAL_SIZE_T prevsize
;
5070 If max_fast is 0, we know that av hasn't
5071 yet been initialized, in which case do so below
5074 if (get_max_fast () != 0) {
5075 clear_fastchunks(av
);
5077 unsorted_bin
= unsorted_chunks(av
);
5080 Remove each chunk from fast bin and consolidate it, placing it
5081 then in unsorted bin. Among other reasons for doing this,
5082 placing in unsorted bin avoids needing to calculate actual bins
5083 until malloc is sure that chunks aren't immediately going to be
5088 /* It is wrong to limit the fast bins to search using get_max_fast
5089 because, except for the main arena, all the others might have
5090 blocks in the high fast bins. It's not worth it anyway, just
5091 search all bins all the time. */
5092 maxfb
= &fastbin (av
, fastbin_index(get_max_fast ()));
5094 maxfb
= &fastbin (av
, NFASTBINS
- 1);
5096 fb
= &fastbin (av
, 0);
5098 #ifdef ATOMIC_FASTBINS
5099 p
= atomic_exchange_acq (fb
, 0);
5104 #ifndef ATOMIC_FASTBINS
5108 check_inuse_chunk(av
, p
);
5111 /* Slightly streamlined version of consolidation code in free() */
5112 size
= p
->size
& ~(PREV_INUSE
|NON_MAIN_ARENA
);
5113 nextchunk
= chunk_at_offset(p
, size
);
5114 nextsize
= chunksize(nextchunk
);
5116 if (!prev_inuse(p
)) {
5117 prevsize
= p
->prev_size
;
5119 p
= chunk_at_offset(p
, -((long) prevsize
));
5120 unlink(p
, bck
, fwd
);
5123 if (nextchunk
!= av
->top
) {
5124 nextinuse
= inuse_bit_at_offset(nextchunk
, nextsize
);
5128 unlink(nextchunk
, bck
, fwd
);
5130 clear_inuse_bit_at_offset(nextchunk
, 0);
5132 first_unsorted
= unsorted_bin
->fd
;
5133 unsorted_bin
->fd
= p
;
5134 first_unsorted
->bk
= p
;
5136 if (!in_smallbin_range (size
)) {
5137 p
->fd_nextsize
= NULL
;
5138 p
->bk_nextsize
= NULL
;
5141 set_head(p
, size
| PREV_INUSE
);
5142 p
->bk
= unsorted_bin
;
5143 p
->fd
= first_unsorted
;
5149 set_head(p
, size
| PREV_INUSE
);
5153 } while ( (p
= nextp
) != 0);
5156 } while (fb
++ != maxfb
);
5159 malloc_init_state(av
);
5160 check_malloc_state(av
);
5165 ------------------------------ realloc ------------------------------
5169 _int_realloc(mstate av
, mchunkptr oldp
, INTERNAL_SIZE_T oldsize
,
5172 mchunkptr newp
; /* chunk to return */
5173 INTERNAL_SIZE_T newsize
; /* its size */
5174 Void_t
* newmem
; /* corresponding user mem */
5176 mchunkptr next
; /* next contiguous chunk after oldp */
5178 mchunkptr remainder
; /* extra space at end of newp */
5179 unsigned long remainder_size
; /* its size */
5181 mchunkptr bck
; /* misc temp for linking */
5182 mchunkptr fwd
; /* misc temp for linking */
5184 unsigned long copysize
; /* bytes to copy */
5185 unsigned int ncopies
; /* INTERNAL_SIZE_T words to copy */
5186 INTERNAL_SIZE_T
* s
; /* copy source */
5187 INTERNAL_SIZE_T
* d
; /* copy destination */
5189 const char *errstr
= NULL
;
5192 if (__builtin_expect (oldp
->size
<= 2 * SIZE_SZ
, 0)
5193 || __builtin_expect (oldsize
>= av
->system_mem
, 0))
5195 errstr
= "realloc(): invalid old size";
5197 malloc_printerr (check_action
, errstr
, chunk2mem(oldp
));
5201 check_inuse_chunk(av
, oldp
);
5203 /* All callers already filter out mmap'ed chunks. */
5205 if (!chunk_is_mmapped(oldp
))
5207 assert (!chunk_is_mmapped(oldp
));
5211 next
= chunk_at_offset(oldp
, oldsize
);
5212 INTERNAL_SIZE_T nextsize
= chunksize(next
);
5213 if (__builtin_expect (next
->size
<= 2 * SIZE_SZ
, 0)
5214 || __builtin_expect (nextsize
>= av
->system_mem
, 0))
5216 errstr
= "realloc(): invalid next size";
5220 if ((unsigned long)(oldsize
) >= (unsigned long)(nb
)) {
5221 /* already big enough; split below */
5227 /* Try to expand forward into top */
5228 if (next
== av
->top
&&
5229 (unsigned long)(newsize
= oldsize
+ nextsize
) >=
5230 (unsigned long)(nb
+ MINSIZE
)) {
5231 set_head_size(oldp
, nb
| (av
!= &main_arena
? NON_MAIN_ARENA
: 0));
5232 av
->top
= chunk_at_offset(oldp
, nb
);
5233 set_head(av
->top
, (newsize
- nb
) | PREV_INUSE
);
5234 check_inuse_chunk(av
, oldp
);
5235 return chunk2mem(oldp
);
5238 /* Try to expand forward into next chunk; split off remainder below */
5239 else if (next
!= av
->top
&&
5241 (unsigned long)(newsize
= oldsize
+ nextsize
) >=
5242 (unsigned long)(nb
)) {
5244 unlink(next
, bck
, fwd
);
5247 /* allocate, copy, free */
5249 newmem
= _int_malloc(av
, nb
- MALLOC_ALIGN_MASK
);
5251 return 0; /* propagate failure */
5253 newp
= mem2chunk(newmem
);
5254 newsize
= chunksize(newp
);
5257 Avoid copy if newp is next chunk after oldp.
5265 Unroll copy of <= 36 bytes (72 if 8byte sizes)
5266 We know that contents have an odd number of
5267 INTERNAL_SIZE_T-sized words; minimally 3.
5270 copysize
= oldsize
- SIZE_SZ
;
5271 s
= (INTERNAL_SIZE_T
*)(chunk2mem(oldp
));
5272 d
= (INTERNAL_SIZE_T
*)(newmem
);
5273 ncopies
= copysize
/ sizeof(INTERNAL_SIZE_T
);
5274 assert(ncopies
>= 3);
5277 MALLOC_COPY(d
, s
, copysize
);
5297 #ifdef ATOMIC_FASTBINS
5298 _int_free(av
, oldp
, 1);
5300 _int_free(av
, oldp
);
5302 check_inuse_chunk(av
, newp
);
5303 return chunk2mem(newp
);
5308 /* If possible, free extra space in old or extended chunk */
5310 assert((unsigned long)(newsize
) >= (unsigned long)(nb
));
5312 remainder_size
= newsize
- nb
;
5314 if (remainder_size
< MINSIZE
) { /* not enough extra to split off */
5315 set_head_size(newp
, newsize
| (av
!= &main_arena
? NON_MAIN_ARENA
: 0));
5316 set_inuse_bit_at_offset(newp
, newsize
);
5318 else { /* split remainder */
5319 remainder
= chunk_at_offset(newp
, nb
);
5320 set_head_size(newp
, nb
| (av
!= &main_arena
? NON_MAIN_ARENA
: 0));
5321 set_head(remainder
, remainder_size
| PREV_INUSE
|
5322 (av
!= &main_arena
? NON_MAIN_ARENA
: 0));
5323 /* Mark remainder as inuse so free() won't complain */
5324 set_inuse_bit_at_offset(remainder
, remainder_size
);
5325 #ifdef ATOMIC_FASTBINS
5326 _int_free(av
, remainder
, 1);
5328 _int_free(av
, remainder
);
5332 check_inuse_chunk(av
, newp
);
5333 return chunk2mem(newp
);
5345 INTERNAL_SIZE_T offset
= oldp
->prev_size
;
5346 size_t pagemask
= mp_
.pagesize
- 1;
5350 /* Note the extra SIZE_SZ overhead */
5351 newsize
= (nb
+ offset
+ SIZE_SZ
+ pagemask
) & ~pagemask
;
5353 /* don't need to remap if still within same page */
5354 if (oldsize
== newsize
- offset
)
5355 return chunk2mem(oldp
);
5357 cp
= (char*)mremap((char*)oldp
- offset
, oldsize
+ offset
, newsize
, 1);
5359 if (cp
!= MAP_FAILED
) {
5361 newp
= (mchunkptr
)(cp
+ offset
);
5362 set_head(newp
, (newsize
- offset
)|IS_MMAPPED
);
5364 assert(aligned_OK(chunk2mem(newp
)));
5365 assert((newp
->prev_size
== offset
));
5367 /* update statistics */
5368 sum
= mp_
.mmapped_mem
+= newsize
- oldsize
;
5369 if (sum
> (unsigned long)(mp_
.max_mmapped_mem
))
5370 mp_
.max_mmapped_mem
= sum
;
5372 sum
+= main_arena
.system_mem
;
5373 if (sum
> (unsigned long)(mp_
.max_total_mem
))
5374 mp_
.max_total_mem
= sum
;
5377 return chunk2mem(newp
);
5381 /* Note the extra SIZE_SZ overhead. */
5382 if ((unsigned long)(oldsize
) >= (unsigned long)(nb
+ SIZE_SZ
))
5383 newmem
= chunk2mem(oldp
); /* do nothing */
5385 /* Must alloc, copy, free. */
5386 newmem
= _int_malloc(av
, nb
- MALLOC_ALIGN_MASK
);
5388 MALLOC_COPY(newmem
, chunk2mem(oldp
), oldsize
- 2*SIZE_SZ
);
5389 #ifdef ATOMIC_FASTBINS
5390 _int_free(av
, oldp
, 1);
5392 _int_free(av
, oldp
);
5399 /* If !HAVE_MMAP, but chunk_is_mmapped, user must have overwritten mem */
5400 check_malloc_state(av
);
5401 MALLOC_FAILURE_ACTION
;
5409 ------------------------------ memalign ------------------------------
5413 _int_memalign(mstate av
, size_t alignment
, size_t bytes
)
5415 INTERNAL_SIZE_T nb
; /* padded request size */
5416 char* m
; /* memory returned by malloc call */
5417 mchunkptr p
; /* corresponding chunk */
5418 char* brk
; /* alignment point within p */
5419 mchunkptr newp
; /* chunk to return */
5420 INTERNAL_SIZE_T newsize
; /* its size */
5421 INTERNAL_SIZE_T leadsize
; /* leading space before alignment point */
5422 mchunkptr remainder
; /* spare room at end to split off */
5423 unsigned long remainder_size
; /* its size */
5424 INTERNAL_SIZE_T size
;
5426 /* If need less alignment than we give anyway, just relay to malloc */
5428 if (alignment
<= MALLOC_ALIGNMENT
) return _int_malloc(av
, bytes
);
5430 /* Otherwise, ensure that it is at least a minimum chunk size */
5432 if (alignment
< MINSIZE
) alignment
= MINSIZE
;
5434 /* Make sure alignment is power of 2 (in case MINSIZE is not). */
5435 if ((alignment
& (alignment
- 1)) != 0) {
5436 size_t a
= MALLOC_ALIGNMENT
* 2;
5437 while ((unsigned long)a
< (unsigned long)alignment
) a
<<= 1;
5441 checked_request2size(bytes
, nb
);
5444 Strategy: find a spot within that chunk that meets the alignment
5445 request, and then possibly free the leading and trailing space.
5449 /* Call malloc with worst case padding to hit alignment. */
5451 m
= (char*)(_int_malloc(av
, nb
+ alignment
+ MINSIZE
));
5453 if (m
== 0) return 0; /* propagate failure */
5457 if ((((unsigned long)(m
)) % alignment
) != 0) { /* misaligned */
5460 Find an aligned spot inside chunk. Since we need to give back
5461 leading space in a chunk of at least MINSIZE, if the first
5462 calculation places us at a spot with less than MINSIZE leader,
5463 we can move to the next aligned spot -- we've allocated enough
5464 total room so that this is always possible.
5467 brk
= (char*)mem2chunk(((unsigned long)(m
+ alignment
- 1)) &
5468 -((signed long) alignment
));
5469 if ((unsigned long)(brk
- (char*)(p
)) < MINSIZE
)
5472 newp
= (mchunkptr
)brk
;
5473 leadsize
= brk
- (char*)(p
);
5474 newsize
= chunksize(p
) - leadsize
;
5476 /* For mmapped chunks, just adjust offset */
5477 if (chunk_is_mmapped(p
)) {
5478 newp
->prev_size
= p
->prev_size
+ leadsize
;
5479 set_head(newp
, newsize
|IS_MMAPPED
);
5480 return chunk2mem(newp
);
5483 /* Otherwise, give back leader, use the rest */
5484 set_head(newp
, newsize
| PREV_INUSE
|
5485 (av
!= &main_arena
? NON_MAIN_ARENA
: 0));
5486 set_inuse_bit_at_offset(newp
, newsize
);
5487 set_head_size(p
, leadsize
| (av
!= &main_arena
? NON_MAIN_ARENA
: 0));
5488 #ifdef ATOMIC_FASTBINS
5489 _int_free(av
, p
, 1);
5495 assert (newsize
>= nb
&&
5496 (((unsigned long)(chunk2mem(p
))) % alignment
) == 0);
5499 /* Also give back spare room at the end */
5500 if (!chunk_is_mmapped(p
)) {
5501 size
= chunksize(p
);
5502 if ((unsigned long)(size
) > (unsigned long)(nb
+ MINSIZE
)) {
5503 remainder_size
= size
- nb
;
5504 remainder
= chunk_at_offset(p
, nb
);
5505 set_head(remainder
, remainder_size
| PREV_INUSE
|
5506 (av
!= &main_arena
? NON_MAIN_ARENA
: 0));
5507 set_head_size(p
, nb
);
5508 #ifdef ATOMIC_FASTBINS
5509 _int_free(av
, remainder
, 1);
5511 _int_free(av
, remainder
);
5516 check_inuse_chunk(av
, p
);
5517 return chunk2mem(p
);
5522 ------------------------------ calloc ------------------------------
5526 Void_t
* cALLOc(size_t n_elements
, size_t elem_size
)
5528 Void_t
* cALLOc(n_elements
, elem_size
) size_t n_elements
; size_t elem_size
;
5532 unsigned long clearsize
;
5533 unsigned long nclears
;
5536 Void_t
* mem
= mALLOc(n_elements
* elem_size
);
5542 if (!chunk_is_mmapped(p
)) /* don't need to clear mmapped space */
5546 Unroll clear of <= 36 bytes (72 if 8byte sizes)
5547 We know that contents have an odd number of
5548 INTERNAL_SIZE_T-sized words; minimally 3.
5551 d
= (INTERNAL_SIZE_T
*)mem
;
5552 clearsize
= chunksize(p
) - SIZE_SZ
;
5553 nclears
= clearsize
/ sizeof(INTERNAL_SIZE_T
);
5554 assert(nclears
>= 3);
5557 MALLOC_ZERO(d
, clearsize
);
5584 ------------------------- independent_calloc -------------------------
5589 _int_icalloc(mstate av
, size_t n_elements
, size_t elem_size
, Void_t
* chunks
[])
5591 _int_icalloc(av
, n_elements
, elem_size
, chunks
)
5592 mstate av
; size_t n_elements
; size_t elem_size
; Void_t
* chunks
[];
5595 size_t sz
= elem_size
; /* serves as 1-element array */
5596 /* opts arg of 3 means all elements are same size, and should be cleared */
5597 return iALLOc(av
, n_elements
, &sz
, 3, chunks
);
5601 ------------------------- independent_comalloc -------------------------
5606 _int_icomalloc(mstate av
, size_t n_elements
, size_t sizes
[], Void_t
* chunks
[])
5608 _int_icomalloc(av
, n_elements
, sizes
, chunks
)
5609 mstate av
; size_t n_elements
; size_t sizes
[]; Void_t
* chunks
[];
5612 return iALLOc(av
, n_elements
, sizes
, 0, chunks
);
5617 ------------------------------ ialloc ------------------------------
5618 ialloc provides common support for independent_X routines, handling all of
5619 the combinations that can result.
5622 bit 0 set if all elements are same size (using sizes[0])
5623 bit 1 set if elements should be zeroed
5629 iALLOc(mstate av
, size_t n_elements
, size_t* sizes
, int opts
, Void_t
* chunks
[])
5631 iALLOc(av
, n_elements
, sizes
, opts
, chunks
)
5632 mstate av
; size_t n_elements
; size_t* sizes
; int opts
; Void_t
* chunks
[];
5635 INTERNAL_SIZE_T element_size
; /* chunksize of each element, if all same */
5636 INTERNAL_SIZE_T contents_size
; /* total size of elements */
5637 INTERNAL_SIZE_T array_size
; /* request size of pointer array */
5638 Void_t
* mem
; /* malloced aggregate space */
5639 mchunkptr p
; /* corresponding chunk */
5640 INTERNAL_SIZE_T remainder_size
; /* remaining bytes while splitting */
5641 Void_t
** marray
; /* either "chunks" or malloced ptr array */
5642 mchunkptr array_chunk
; /* chunk for malloced ptr array */
5643 int mmx
; /* to disable mmap */
5644 INTERNAL_SIZE_T size
;
5645 INTERNAL_SIZE_T size_flags
;
5648 /* Ensure initialization/consolidation */
5649 if (have_fastchunks(av
)) malloc_consolidate(av
);
5651 /* compute array length, if needed */
5653 if (n_elements
== 0)
5654 return chunks
; /* nothing to do */
5659 /* if empty req, must still return chunk representing empty array */
5660 if (n_elements
== 0)
5661 return (Void_t
**) _int_malloc(av
, 0);
5663 array_size
= request2size(n_elements
* (sizeof(Void_t
*)));
5666 /* compute total element size */
5667 if (opts
& 0x1) { /* all-same-size */
5668 element_size
= request2size(*sizes
);
5669 contents_size
= n_elements
* element_size
;
5671 else { /* add up all the sizes */
5674 for (i
= 0; i
!= n_elements
; ++i
)
5675 contents_size
+= request2size(sizes
[i
]);
5678 /* subtract out alignment bytes from total to minimize overallocation */
5679 size
= contents_size
+ array_size
- MALLOC_ALIGN_MASK
;
5682 Allocate the aggregate chunk.
5683 But first disable mmap so malloc won't use it, since
5684 we would not be able to later free/realloc space internal
5685 to a segregated mmap region.
5687 mmx
= mp_
.n_mmaps_max
; /* disable mmap */
5688 mp_
.n_mmaps_max
= 0;
5689 mem
= _int_malloc(av
, size
);
5690 mp_
.n_mmaps_max
= mmx
; /* reset mmap */
5695 assert(!chunk_is_mmapped(p
));
5696 remainder_size
= chunksize(p
);
5698 if (opts
& 0x2) { /* optionally clear the elements */
5699 MALLOC_ZERO(mem
, remainder_size
- SIZE_SZ
- array_size
);
5702 size_flags
= PREV_INUSE
| (av
!= &main_arena
? NON_MAIN_ARENA
: 0);
5704 /* If not provided, allocate the pointer array as final part of chunk */
5706 array_chunk
= chunk_at_offset(p
, contents_size
);
5707 marray
= (Void_t
**) (chunk2mem(array_chunk
));
5708 set_head(array_chunk
, (remainder_size
- contents_size
) | size_flags
);
5709 remainder_size
= contents_size
;
5712 /* split out elements */
5713 for (i
= 0; ; ++i
) {
5714 marray
[i
] = chunk2mem(p
);
5715 if (i
!= n_elements
-1) {
5716 if (element_size
!= 0)
5717 size
= element_size
;
5719 size
= request2size(sizes
[i
]);
5720 remainder_size
-= size
;
5721 set_head(p
, size
| size_flags
);
5722 p
= chunk_at_offset(p
, size
);
5724 else { /* the final element absorbs any overallocation slop */
5725 set_head(p
, remainder_size
| size_flags
);
5731 if (marray
!= chunks
) {
5732 /* final element must have exactly exhausted chunk */
5733 if (element_size
!= 0)
5734 assert(remainder_size
== element_size
);
5736 assert(remainder_size
== request2size(sizes
[i
]));
5737 check_inuse_chunk(av
, mem2chunk(marray
));
5740 for (i
= 0; i
!= n_elements
; ++i
)
5741 check_inuse_chunk(av
, mem2chunk(marray
[i
]));
5750 ------------------------------ valloc ------------------------------
5755 _int_valloc(mstate av
, size_t bytes
)
5757 _int_valloc(av
, bytes
) mstate av
; size_t bytes
;
5760 /* Ensure initialization/consolidation */
5761 if (have_fastchunks(av
)) malloc_consolidate(av
);
5762 return _int_memalign(av
, mp_
.pagesize
, bytes
);
5766 ------------------------------ pvalloc ------------------------------
5772 _int_pvalloc(mstate av
, size_t bytes
)
5774 _int_pvalloc(av
, bytes
) mstate av
, size_t bytes
;
5779 /* Ensure initialization/consolidation */
5780 if (have_fastchunks(av
)) malloc_consolidate(av
);
5781 pagesz
= mp_
.pagesize
;
5782 return _int_memalign(av
, pagesz
, (bytes
+ pagesz
- 1) & ~(pagesz
- 1));
5787 ------------------------------ malloc_trim ------------------------------
5791 static int mTRIm(mstate av
, size_t pad
)
5793 static int mTRIm(av
, pad
) mstate av
; size_t pad
;
5796 /* Ensure initialization/consolidation */
5797 malloc_consolidate (av
);
5799 const size_t ps
= mp_
.pagesize
;
5800 int psindex
= bin_index (ps
);
5801 const size_t psm1
= ps
- 1;
5804 for (int i
= 1; i
< NBINS
; ++i
)
5805 if (i
== 1 || i
>= psindex
)
5807 mbinptr bin
= bin_at (av
, i
);
5809 for (mchunkptr p
= last (bin
); p
!= bin
; p
= p
->bk
)
5811 INTERNAL_SIZE_T size
= chunksize (p
);
5813 if (size
> psm1
+ sizeof (struct malloc_chunk
))
5815 /* See whether the chunk contains at least one unused page. */
5816 char *paligned_mem
= (char *) (((uintptr_t) p
5817 + sizeof (struct malloc_chunk
)
5820 assert ((char *) chunk2mem (p
) + 4 * SIZE_SZ
<= paligned_mem
);
5821 assert ((char *) p
+ size
> paligned_mem
);
5823 /* This is the size we could potentially free. */
5824 size
-= paligned_mem
- (char *) p
;
5829 /* When debugging we simulate destroying the memory
5831 memset (paligned_mem
, 0x89, size
& ~psm1
);
5833 madvise (paligned_mem
, size
& ~psm1
, MADV_DONTNEED
);
5841 #ifndef MORECORE_CANNOT_TRIM
5842 return result
| (av
== &main_arena
? sYSTRIm (pad
, av
) : 0);
5850 ------------------------- malloc_usable_size -------------------------
5854 size_t mUSABLe(Void_t
* mem
)
5856 size_t mUSABLe(mem
) Void_t
* mem
;
5862 if (chunk_is_mmapped(p
))
5863 return chunksize(p
) - 2*SIZE_SZ
;
5865 return chunksize(p
) - SIZE_SZ
;
5871 ------------------------------ mallinfo ------------------------------
5874 struct mallinfo
mALLINFo(mstate av
)
5880 INTERNAL_SIZE_T avail
;
5881 INTERNAL_SIZE_T fastavail
;
5885 /* Ensure initialization */
5886 if (av
->top
== 0) malloc_consolidate(av
);
5888 check_malloc_state(av
);
5890 /* Account for top */
5891 avail
= chunksize(av
->top
);
5892 nblocks
= 1; /* top always exists */
5894 /* traverse fastbins */
5898 for (i
= 0; i
< NFASTBINS
; ++i
) {
5899 for (p
= fastbin (av
, i
); p
!= 0; p
= p
->fd
) {
5901 fastavail
+= chunksize(p
);
5907 /* traverse regular bins */
5908 for (i
= 1; i
< NBINS
; ++i
) {
5910 for (p
= last(b
); p
!= b
; p
= p
->bk
) {
5912 avail
+= chunksize(p
);
5916 mi
.smblks
= nfastblocks
;
5917 mi
.ordblks
= nblocks
;
5918 mi
.fordblks
= avail
;
5919 mi
.uordblks
= av
->system_mem
- avail
;
5920 mi
.arena
= av
->system_mem
;
5921 mi
.hblks
= mp_
.n_mmaps
;
5922 mi
.hblkhd
= mp_
.mmapped_mem
;
5923 mi
.fsmblks
= fastavail
;
5924 mi
.keepcost
= chunksize(av
->top
);
5925 mi
.usmblks
= mp_
.max_total_mem
;
5930 ------------------------------ malloc_stats ------------------------------
5938 unsigned int in_use_b
= mp_
.mmapped_mem
, system_b
= in_use_b
;
5940 long stat_lock_direct
= 0, stat_lock_loop
= 0, stat_lock_wait
= 0;
5943 if(__malloc_initialized
< 0)
5946 _IO_flockfile (stderr
);
5947 int old_flags2
= ((_IO_FILE
*) stderr
)->_flags2
;
5948 ((_IO_FILE
*) stderr
)->_flags2
|= _IO_FLAGS2_NOTCANCEL
;
5950 for (i
=0, ar_ptr
= &main_arena
;; i
++) {
5951 (void)mutex_lock(&ar_ptr
->mutex
);
5952 mi
= mALLINFo(ar_ptr
);
5953 fprintf(stderr
, "Arena %d:\n", i
);
5954 fprintf(stderr
, "system bytes = %10u\n", (unsigned int)mi
.arena
);
5955 fprintf(stderr
, "in use bytes = %10u\n", (unsigned int)mi
.uordblks
);
5956 #if MALLOC_DEBUG > 1
5958 dump_heap(heap_for_ptr(top(ar_ptr
)));
5960 system_b
+= mi
.arena
;
5961 in_use_b
+= mi
.uordblks
;
5963 stat_lock_direct
+= ar_ptr
->stat_lock_direct
;
5964 stat_lock_loop
+= ar_ptr
->stat_lock_loop
;
5965 stat_lock_wait
+= ar_ptr
->stat_lock_wait
;
5967 (void)mutex_unlock(&ar_ptr
->mutex
);
5968 ar_ptr
= ar_ptr
->next
;
5969 if(ar_ptr
== &main_arena
) break;
5972 fprintf(stderr
, "Total (incl. mmap):\n");
5974 fprintf(stderr
, "Total:\n");
5976 fprintf(stderr
, "system bytes = %10u\n", system_b
);
5977 fprintf(stderr
, "in use bytes = %10u\n", in_use_b
);
5979 fprintf(stderr
, "max system bytes = %10u\n", (unsigned int)mp_
.max_total_mem
);
5982 fprintf(stderr
, "max mmap regions = %10u\n", (unsigned int)mp_
.max_n_mmaps
);
5983 fprintf(stderr
, "max mmap bytes = %10lu\n",
5984 (unsigned long)mp_
.max_mmapped_mem
);
5987 fprintf(stderr
, "heaps created = %10d\n", stat_n_heaps
);
5988 fprintf(stderr
, "locked directly = %10ld\n", stat_lock_direct
);
5989 fprintf(stderr
, "locked in loop = %10ld\n", stat_lock_loop
);
5990 fprintf(stderr
, "locked waiting = %10ld\n", stat_lock_wait
);
5991 fprintf(stderr
, "locked total = %10ld\n",
5992 stat_lock_direct
+ stat_lock_loop
+ stat_lock_wait
);
5995 ((_IO_FILE
*) stderr
)->_flags2
|= old_flags2
;
5996 _IO_funlockfile (stderr
);
6002 ------------------------------ mallopt ------------------------------
6006 int mALLOPt(int param_number
, int value
)
6008 int mALLOPt(param_number
, value
) int param_number
; int value
;
6011 mstate av
= &main_arena
;
6014 if(__malloc_initialized
< 0)
6016 (void)mutex_lock(&av
->mutex
);
6017 /* Ensure initialization/consolidation */
6018 malloc_consolidate(av
);
6020 switch(param_number
) {
6022 if (value
>= 0 && value
<= MAX_FAST_SIZE
) {
6023 set_max_fast(value
);
6029 case M_TRIM_THRESHOLD
:
6030 mp_
.trim_threshold
= value
;
6031 mp_
.no_dyn_threshold
= 1;
6035 mp_
.top_pad
= value
;
6036 mp_
.no_dyn_threshold
= 1;
6039 case M_MMAP_THRESHOLD
:
6041 /* Forbid setting the threshold too high. */
6042 if((unsigned long)value
> HEAP_MAX_SIZE
/2)
6046 mp_
.mmap_threshold
= value
;
6047 mp_
.no_dyn_threshold
= 1;
6056 mp_
.n_mmaps_max
= value
;
6057 mp_
.no_dyn_threshold
= 1;
6060 case M_CHECK_ACTION
:
6061 check_action
= value
;
6065 perturb_byte
= value
;
6071 mp_
.arena_test
= value
;
6076 mp_
.arena_max
= value
;
6080 (void)mutex_unlock(&av
->mutex
);
6086 -------------------- Alternative MORECORE functions --------------------
6091 General Requirements for MORECORE.
6093 The MORECORE function must have the following properties:
6095 If MORECORE_CONTIGUOUS is false:
6097 * MORECORE must allocate in multiples of pagesize. It will
6098 only be called with arguments that are multiples of pagesize.
6100 * MORECORE(0) must return an address that is at least
6101 MALLOC_ALIGNMENT aligned. (Page-aligning always suffices.)
6103 else (i.e. If MORECORE_CONTIGUOUS is true):
6105 * Consecutive calls to MORECORE with positive arguments
6106 return increasing addresses, indicating that space has been
6107 contiguously extended.
6109 * MORECORE need not allocate in multiples of pagesize.
6110 Calls to MORECORE need not have args of multiples of pagesize.
6112 * MORECORE need not page-align.
6116 * MORECORE may allocate more memory than requested. (Or even less,
6117 but this will generally result in a malloc failure.)
6119 * MORECORE must not allocate memory when given argument zero, but
6120 instead return one past the end address of memory from previous
6121 nonzero call. This malloc does NOT call MORECORE(0)
6122 until at least one call with positive arguments is made, so
6123 the initial value returned is not important.
6125 * Even though consecutive calls to MORECORE need not return contiguous
6126 addresses, it must be OK for malloc'ed chunks to span multiple
6127 regions in those cases where they do happen to be contiguous.
6129 * MORECORE need not handle negative arguments -- it may instead
6130 just return MORECORE_FAILURE when given negative arguments.
6131 Negative arguments are always multiples of pagesize. MORECORE
6132 must not misinterpret negative args as large positive unsigned
6133 args. You can suppress all such calls from even occurring by defining
6134 MORECORE_CANNOT_TRIM,
6136 There is some variation across systems about the type of the
6137 argument to sbrk/MORECORE. If size_t is unsigned, then it cannot
6138 actually be size_t, because sbrk supports negative args, so it is
6139 normally the signed type of the same width as size_t (sometimes
6140 declared as "intptr_t", and sometimes "ptrdiff_t"). It doesn't much
6141 matter though. Internally, we use "long" as arguments, which should
6142 work across all reasonable possibilities.
6144 Additionally, if MORECORE ever returns failure for a positive
6145 request, and HAVE_MMAP is true, then mmap is used as a noncontiguous
6146 system allocator. This is a useful backup strategy for systems with
6147 holes in address spaces -- in this case sbrk cannot contiguously
6148 expand the heap, but mmap may be able to map noncontiguous space.
6150 If you'd like mmap to ALWAYS be used, you can define MORECORE to be
6151 a function that always returns MORECORE_FAILURE.
6153 If you are using this malloc with something other than sbrk (or its
6154 emulation) to supply memory regions, you probably want to set
6155 MORECORE_CONTIGUOUS as false. As an example, here is a custom
6156 allocator kindly contributed for pre-OSX macOS. It uses virtually
6157 but not necessarily physically contiguous non-paged memory (locked
6158 in, present and won't get swapped out). You can use it by
6159 uncommenting this section, adding some #includes, and setting up the
6160 appropriate defines above:
6162 #define MORECORE osMoreCore
6163 #define MORECORE_CONTIGUOUS 0
6165 There is also a shutdown routine that should somehow be called for
6166 cleanup upon program exit.
6168 #define MAX_POOL_ENTRIES 100
6169 #define MINIMUM_MORECORE_SIZE (64 * 1024)
6170 static int next_os_pool;
6171 void *our_os_pools[MAX_POOL_ENTRIES];
6173 void *osMoreCore(int size)
6176 static void *sbrk_top = 0;
6180 if (size < MINIMUM_MORECORE_SIZE)
6181 size = MINIMUM_MORECORE_SIZE;
6182 if (CurrentExecutionLevel() == kTaskLevel)
6183 ptr = PoolAllocateResident(size + RM_PAGE_SIZE, 0);
6186 return (void *) MORECORE_FAILURE;
6188 // save ptrs so they can be freed during cleanup
6189 our_os_pools[next_os_pool] = ptr;
6191 ptr = (void *) ((((unsigned long) ptr) + RM_PAGE_MASK) & ~RM_PAGE_MASK);
6192 sbrk_top = (char *) ptr + size;
6197 // we don't currently support shrink behavior
6198 return (void *) MORECORE_FAILURE;
6206 // cleanup any allocated memory pools
6207 // called as last thing before shutting down driver
6209 void osCleanupMem(void)
6213 for (ptr = our_os_pools; ptr < &our_os_pools[MAX_POOL_ENTRIES]; ptr++)
6216 PoolDeallocate(*ptr);
6226 extern char **__libc_argv attribute_hidden
;
6229 malloc_printerr(int action
, const char *str
, void *ptr
)
6231 if ((action
& 5) == 5)
6232 __libc_message (action
& 2, "%s\n", str
);
6233 else if (action
& 1)
6235 char buf
[2 * sizeof (uintptr_t) + 1];
6237 buf
[sizeof (buf
) - 1] = '\0';
6238 char *cp
= _itoa_word ((uintptr_t) ptr
, &buf
[sizeof (buf
) - 1], 16, 0);
6242 __libc_message (action
& 2,
6243 "*** glibc detected *** %s: %s: 0x%s ***\n",
6244 __libc_argv
[0] ?: "<unknown>", str
, cp
);
6246 else if (action
& 2)
6251 # include <sys/param.h>
6253 /* We need a wrapper function for one of the additions of POSIX. */
6255 __posix_memalign (void **memptr
, size_t alignment
, size_t size
)
6259 /* Test whether the SIZE argument is valid. It must be a power of
6260 two multiple of sizeof (void *). */
6261 if (alignment
% sizeof (void *) != 0
6262 || !powerof2 (alignment
/ sizeof (void *)) != 0
6266 /* Call the hook here, so that caller is posix_memalign's caller
6267 and not posix_memalign itself. */
6268 __malloc_ptr_t (*hook
) __MALLOC_PMT ((size_t, size_t,
6269 __const __malloc_ptr_t
)) =
6270 force_reg (__memalign_hook
);
6271 if (__builtin_expect (hook
!= NULL
, 0))
6272 mem
= (*hook
)(alignment
, size
, RETURN_ADDRESS (0));
6274 mem
= public_mEMALIGn (alignment
, size
);
6283 weak_alias (__posix_memalign
, posix_memalign
)
6287 malloc_info (int options
, FILE *fp
)
6289 /* For now, at least. */
6294 size_t total_nblocks
= 0;
6295 size_t total_nfastblocks
= 0;
6296 size_t total_avail
= 0;
6297 size_t total_fastavail
= 0;
6298 size_t total_system
= 0;
6299 size_t total_max_system
= 0;
6300 size_t total_aspace
= 0;
6301 size_t total_aspace_mprotect
= 0;
6303 void mi_arena (mstate ar_ptr
)
6305 fprintf (fp
, "<heap nr=\"%d\">\n<sizes>\n", n
++);
6308 size_t nfastblocks
= 0;
6310 size_t fastavail
= 0;
6317 } sizes
[NFASTBINS
+ NBINS
- 1];
6318 #define nsizes (sizeof (sizes) / sizeof (sizes[0]))
6320 mutex_lock (&ar_ptr
->mutex
);
6322 for (size_t i
= 0; i
< NFASTBINS
; ++i
)
6324 mchunkptr p
= fastbin (ar_ptr
, i
);
6327 size_t nthissize
= 0;
6328 size_t thissize
= chunksize (p
);
6336 fastavail
+= nthissize
* thissize
;
6337 nfastblocks
+= nthissize
;
6338 sizes
[i
].from
= thissize
- (MALLOC_ALIGNMENT
- 1);
6339 sizes
[i
].to
= thissize
;
6340 sizes
[i
].count
= nthissize
;
6343 sizes
[i
].from
= sizes
[i
].to
= sizes
[i
].count
= 0;
6345 sizes
[i
].total
= sizes
[i
].count
* sizes
[i
].to
;
6348 mbinptr bin
= bin_at (ar_ptr
, 1);
6349 struct malloc_chunk
*r
= bin
->fd
;
6352 ++sizes
[NFASTBINS
].count
;
6353 sizes
[NFASTBINS
].total
+= r
->size
;
6354 sizes
[NFASTBINS
].from
= MIN (sizes
[NFASTBINS
].from
, r
->size
);
6355 sizes
[NFASTBINS
].to
= MAX (sizes
[NFASTBINS
].to
, r
->size
);
6358 nblocks
+= sizes
[NFASTBINS
].count
;
6359 avail
+= sizes
[NFASTBINS
].total
;
6361 for (size_t i
= 2; i
< NBINS
; ++i
)
6363 bin
= bin_at (ar_ptr
, i
);
6365 sizes
[NFASTBINS
- 1 + i
].from
= ~((size_t) 0);
6366 sizes
[NFASTBINS
- 1 + i
].to
= sizes
[NFASTBINS
- 1 + i
].total
6367 = sizes
[NFASTBINS
- 1 + i
].count
= 0;
6371 ++sizes
[NFASTBINS
- 1 + i
].count
;
6372 sizes
[NFASTBINS
- 1 + i
].total
+= r
->size
;
6373 sizes
[NFASTBINS
- 1 + i
].from
= MIN (sizes
[NFASTBINS
- 1 + i
].from
,
6375 sizes
[NFASTBINS
- 1 + i
].to
= MAX (sizes
[NFASTBINS
- 1 + i
].to
,
6381 if (sizes
[NFASTBINS
- 1 + i
].count
== 0)
6382 sizes
[NFASTBINS
- 1 + i
].from
= 0;
6383 nblocks
+= sizes
[NFASTBINS
- 1 + i
].count
;
6384 avail
+= sizes
[NFASTBINS
- 1 + i
].total
;
6387 mutex_unlock (&ar_ptr
->mutex
);
6389 total_nfastblocks
+= nfastblocks
;
6390 total_fastavail
+= fastavail
;
6392 total_nblocks
+= nblocks
;
6393 total_avail
+= avail
;
6395 for (size_t i
= 0; i
< nsizes
; ++i
)
6396 if (sizes
[i
].count
!= 0 && i
!= NFASTBINS
)
6398 <size from=\"%zu\" to=\"%zu\" total=\"%zu\" count=\"%zu\"/>\n",
6399 sizes
[i
].from
, sizes
[i
].to
, sizes
[i
].total
, sizes
[i
].count
);
6401 if (sizes
[NFASTBINS
].count
!= 0)
6403 <unsorted from=\"%zu\" to=\"%zu\" total=\"%zu\" count=\"%zu\"/>\n",
6404 sizes
[NFASTBINS
].from
, sizes
[NFASTBINS
].to
,
6405 sizes
[NFASTBINS
].total
, sizes
[NFASTBINS
].count
);
6407 total_system
+= ar_ptr
->system_mem
;
6408 total_max_system
+= ar_ptr
->max_system_mem
;
6411 "</sizes>\n<total type=\"fast\" count=\"%zu\" size=\"%zu\"/>\n"
6412 "<total type=\"rest\" count=\"%zu\" size=\"%zu\"/>\n"
6413 "<system type=\"current\" size=\"%zu\"/>\n"
6414 "<system type=\"max\" size=\"%zu\"/>\n",
6415 nfastblocks
, fastavail
, nblocks
, avail
,
6416 ar_ptr
->system_mem
, ar_ptr
->max_system_mem
);
6418 if (ar_ptr
!= &main_arena
)
6420 heap_info
*heap
= heap_for_ptr(top(ar_ptr
));
6422 "<aspace type=\"total\" size=\"%zu\"/>\n"
6423 "<aspace type=\"mprotect\" size=\"%zu\"/>\n",
6424 heap
->size
, heap
->mprotect_size
);
6425 total_aspace
+= heap
->size
;
6426 total_aspace_mprotect
+= heap
->mprotect_size
;
6431 "<aspace type=\"total\" size=\"%zu\"/>\n"
6432 "<aspace type=\"mprotect\" size=\"%zu\"/>\n",
6433 ar_ptr
->system_mem
, ar_ptr
->system_mem
);
6434 total_aspace
+= ar_ptr
->system_mem
;
6435 total_aspace_mprotect
+= ar_ptr
->system_mem
;
6438 fputs ("</heap>\n", fp
);
6441 fputs ("<malloc version=\"1\">\n", fp
);
6443 /* Iterate over all arenas currently in use. */
6444 mstate ar_ptr
= &main_arena
;
6448 ar_ptr
= ar_ptr
->next
;
6450 while (ar_ptr
!= &main_arena
);
6453 "<total type=\"fast\" count=\"%zu\" size=\"%zu\"/>\n"
6454 "<total type=\"rest\" count=\"%zu\" size=\"%zu\"/>\n"
6455 "<system type=\"current\" size=\"%zu\n/>\n"
6456 "<system type=\"max\" size=\"%zu\n/>\n"
6457 "<aspace type=\"total\" size=\"%zu\"/>\n"
6458 "<aspace type=\"mprotect\" size=\"%zu\"/>\n"
6460 total_nfastblocks
, total_fastavail
, total_nblocks
, total_avail
,
6461 total_system
, total_max_system
,
6462 total_aspace
, total_aspace_mprotect
);
6468 strong_alias (__libc_calloc
, __calloc
) weak_alias (__libc_calloc
, calloc
)
6469 strong_alias (__libc_free
, __cfree
) weak_alias (__libc_free
, cfree
)
6470 strong_alias (__libc_free
, __free
) strong_alias (__libc_free
, free
)
6471 strong_alias (__libc_malloc
, __malloc
) strong_alias (__libc_malloc
, malloc
)
6472 strong_alias (__libc_memalign
, __memalign
)
6473 weak_alias (__libc_memalign
, memalign
)
6474 strong_alias (__libc_realloc
, __realloc
) strong_alias (__libc_realloc
, realloc
)
6475 strong_alias (__libc_valloc
, __valloc
) weak_alias (__libc_valloc
, valloc
)
6476 strong_alias (__libc_pvalloc
, __pvalloc
) weak_alias (__libc_pvalloc
, pvalloc
)
6477 strong_alias (__libc_mallinfo
, __mallinfo
)
6478 weak_alias (__libc_mallinfo
, mallinfo
)
6479 strong_alias (__libc_mallopt
, __mallopt
) weak_alias (__libc_mallopt
, mallopt
)
6481 weak_alias (__malloc_stats
, malloc_stats
)
6482 weak_alias (__malloc_usable_size
, malloc_usable_size
)
6483 weak_alias (__malloc_trim
, malloc_trim
)
6484 weak_alias (__malloc_get_state
, malloc_get_state
)
6485 weak_alias (__malloc_set_state
, malloc_set_state
)
6489 /* ------------------------------------------------------------
6492 [see ftp://g.oswego.edu/pub/misc/malloc.c for the history of dlmalloc]