Make common fmax implementation generic.
[glibc.git] / malloc / malloc.c
blobbb52b3e1773056974b97fce1d343de87868f26aa
1 /* Malloc implementation for multiple threads without lock contention.
2 Copyright (C) 1996-2016 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
19 not, see <http://www.gnu.org/licenses/>. */
22 This is a version (aka ptmalloc2) of malloc/free/realloc written by
23 Doug Lea and adapted to multiple threads/arenas by Wolfram Gloger.
25 There have been substantial changes made after the integration into
26 glibc in all parts of the code. Do not look for much commonality
27 with the ptmalloc2 version.
29 * Version ptmalloc2-20011215
30 based on:
31 VERSION 2.7.0 Sun Mar 11 14:14:06 2001 Doug Lea (dl at gee)
33 * Quickstart
35 In order to compile this implementation, a Makefile is provided with
36 the ptmalloc2 distribution, which has pre-defined targets for some
37 popular systems (e.g. "make posix" for Posix threads). All that is
38 typically required with regard to compiler flags is the selection of
39 the thread package via defining one out of USE_PTHREADS, USE_THR or
40 USE_SPROC. Check the thread-m.h file for what effects this has.
41 Many/most systems will additionally require USE_TSD_DATA_HACK to be
42 defined, so this is the default for "make posix".
44 * Why use this malloc?
46 This is not the fastest, most space-conserving, most portable, or
47 most tunable malloc ever written. However it is among the fastest
48 while also being among the most space-conserving, portable and tunable.
49 Consistent balance across these factors results in a good general-purpose
50 allocator for malloc-intensive programs.
52 The main properties of the algorithms are:
53 * For large (>= 512 bytes) requests, it is a pure best-fit allocator,
54 with ties normally decided via FIFO (i.e. least recently used).
55 * For small (<= 64 bytes by default) requests, it is a caching
56 allocator, that maintains pools of quickly recycled chunks.
57 * In between, and for combinations of large and small requests, it does
58 the best it can trying to meet both goals at once.
59 * For very large requests (>= 128KB by default), it relies on system
60 memory mapping facilities, if supported.
62 For a longer but slightly out of date high-level description, see
63 http://gee.cs.oswego.edu/dl/html/malloc.html
65 You may already by default be using a C library containing a malloc
66 that is based on some version of this malloc (for example in
67 linux). You might still want to use the one in this file in order to
68 customize settings or to avoid overheads associated with library
69 versions.
71 * Contents, described in more detail in "description of public routines" below.
73 Standard (ANSI/SVID/...) functions:
74 malloc(size_t n);
75 calloc(size_t n_elements, size_t element_size);
76 free(void* p);
77 realloc(void* p, size_t n);
78 memalign(size_t alignment, size_t n);
79 valloc(size_t n);
80 mallinfo()
81 mallopt(int parameter_number, int parameter_value)
83 Additional functions:
84 independent_calloc(size_t n_elements, size_t size, void* chunks[]);
85 independent_comalloc(size_t n_elements, size_t sizes[], void* chunks[]);
86 pvalloc(size_t n);
87 cfree(void* p);
88 malloc_trim(size_t pad);
89 malloc_usable_size(void* p);
90 malloc_stats();
92 * Vital statistics:
94 Supported pointer representation: 4 or 8 bytes
95 Supported size_t representation: 4 or 8 bytes
96 Note that size_t is allowed to be 4 bytes even if pointers are 8.
97 You can adjust this by defining INTERNAL_SIZE_T
99 Alignment: 2 * sizeof(size_t) (default)
100 (i.e., 8 byte alignment with 4byte size_t). This suffices for
101 nearly all current machines and C compilers. However, you can
102 define MALLOC_ALIGNMENT to be wider than this if necessary.
104 Minimum overhead per allocated chunk: 4 or 8 bytes
105 Each malloced chunk has a hidden word of overhead holding size
106 and status information.
108 Minimum allocated size: 4-byte ptrs: 16 bytes (including 4 overhead)
109 8-byte ptrs: 24/32 bytes (including, 4/8 overhead)
111 When a chunk is freed, 12 (for 4byte ptrs) or 20 (for 8 byte
112 ptrs but 4 byte size) or 24 (for 8/8) additional bytes are
113 needed; 4 (8) for a trailing size field and 8 (16) bytes for
114 free list pointers. Thus, the minimum allocatable size is
115 16/24/32 bytes.
117 Even a request for zero bytes (i.e., malloc(0)) returns a
118 pointer to something of the minimum allocatable size.
120 The maximum overhead wastage (i.e., number of extra bytes
121 allocated than were requested in malloc) is less than or equal
122 to the minimum size, except for requests >= mmap_threshold that
123 are serviced via mmap(), where the worst case wastage is 2 *
124 sizeof(size_t) bytes plus the remainder from a system page (the
125 minimal mmap unit); typically 4096 or 8192 bytes.
127 Maximum allocated size: 4-byte size_t: 2^32 minus about two pages
128 8-byte size_t: 2^64 minus about two pages
130 It is assumed that (possibly signed) size_t values suffice to
131 represent chunk sizes. `Possibly signed' is due to the fact
132 that `size_t' may be defined on a system as either a signed or
133 an unsigned type. The ISO C standard says that it must be
134 unsigned, but a few systems are known not to adhere to this.
135 Additionally, even when size_t is unsigned, sbrk (which is by
136 default used to obtain memory from system) accepts signed
137 arguments, and may not be able to handle size_t-wide arguments
138 with negative sign bit. Generally, values that would
139 appear as negative after accounting for overhead and alignment
140 are supported only via mmap(), which does not have this
141 limitation.
143 Requests for sizes outside the allowed range will perform an optional
144 failure action and then return null. (Requests may also
145 also fail because a system is out of memory.)
147 Thread-safety: thread-safe
149 Compliance: I believe it is compliant with the 1997 Single Unix Specification
150 Also SVID/XPG, ANSI C, and probably others as well.
152 * Synopsis of compile-time options:
154 People have reported using previous versions of this malloc on all
155 versions of Unix, sometimes by tweaking some of the defines
156 below. It has been tested most extensively on Solaris and Linux.
157 People also report using it in stand-alone embedded systems.
159 The implementation is in straight, hand-tuned ANSI C. It is not
160 at all modular. (Sorry!) It uses a lot of macros. To be at all
161 usable, this code should be compiled using an optimizing compiler
162 (for example gcc -O3) that can simplify expressions and control
163 paths. (FAQ: some macros import variables as arguments rather than
164 declare locals because people reported that some debuggers
165 otherwise get confused.)
167 OPTION DEFAULT VALUE
169 Compilation Environment options:
171 HAVE_MREMAP 0
173 Changing default word sizes:
175 INTERNAL_SIZE_T size_t
177 Configuration and functionality options:
179 USE_PUBLIC_MALLOC_WRAPPERS NOT defined
180 USE_MALLOC_LOCK NOT defined
181 MALLOC_DEBUG NOT defined
182 REALLOC_ZERO_BYTES_FREES 1
183 TRIM_FASTBINS 0
185 Options for customizing MORECORE:
187 MORECORE sbrk
188 MORECORE_FAILURE -1
189 MORECORE_CONTIGUOUS 1
190 MORECORE_CANNOT_TRIM NOT defined
191 MORECORE_CLEARS 1
192 MMAP_AS_MORECORE_SIZE (1024 * 1024)
194 Tuning options that are also dynamically changeable via mallopt:
196 DEFAULT_MXFAST 64 (for 32bit), 128 (for 64bit)
197 DEFAULT_TRIM_THRESHOLD 128 * 1024
198 DEFAULT_TOP_PAD 0
199 DEFAULT_MMAP_THRESHOLD 128 * 1024
200 DEFAULT_MMAP_MAX 65536
202 There are several other #defined constants and macros that you
203 probably don't want to touch unless you are extending or adapting malloc. */
206 void* is the pointer type that malloc should say it returns
209 #ifndef void
210 #define void void
211 #endif /*void*/
213 #include <stddef.h> /* for size_t */
214 #include <stdlib.h> /* for getenv(), abort() */
215 #include <unistd.h> /* for __libc_enable_secure */
217 #include <atomic.h>
218 #include <_itoa.h>
219 #include <bits/wordsize.h>
220 #include <sys/sysinfo.h>
222 #include <ldsodefs.h>
224 #include <unistd.h>
225 #include <stdio.h> /* needed for malloc_stats */
226 #include <errno.h>
228 #include <shlib-compat.h>
230 /* For uintptr_t. */
231 #include <stdint.h>
233 /* For va_arg, va_start, va_end. */
234 #include <stdarg.h>
236 /* For MIN, MAX, powerof2. */
237 #include <sys/param.h>
239 /* For ALIGN_UP et. al. */
240 #include <libc-internal.h>
242 #include <malloc/malloc-internal.h>
245 Debugging:
247 Because freed chunks may be overwritten with bookkeeping fields, this
248 malloc will often die when freed memory is overwritten by user
249 programs. This can be very effective (albeit in an annoying way)
250 in helping track down dangling pointers.
252 If you compile with -DMALLOC_DEBUG, a number of assertion checks are
253 enabled that will catch more memory errors. You probably won't be
254 able to make much sense of the actual assertion errors, but they
255 should help you locate incorrectly overwritten memory. The checking
256 is fairly extensive, and will slow down execution
257 noticeably. Calling malloc_stats or mallinfo with MALLOC_DEBUG set
258 will attempt to check every non-mmapped allocated and free chunk in
259 the course of computing the summmaries. (By nature, mmapped regions
260 cannot be checked very much automatically.)
262 Setting MALLOC_DEBUG may also be helpful if you are trying to modify
263 this code. The assertions in the check routines spell out in more
264 detail the assumptions and invariants underlying the algorithms.
266 Setting MALLOC_DEBUG does NOT provide an automated mechanism for
267 checking that all accesses to malloced memory stay within their
268 bounds. However, there are several add-ons and adaptations of this
269 or other mallocs available that do this.
272 #ifndef MALLOC_DEBUG
273 #define MALLOC_DEBUG 0
274 #endif
276 #ifdef NDEBUG
277 # define assert(expr) ((void) 0)
278 #else
279 # define assert(expr) \
280 ((expr) \
281 ? ((void) 0) \
282 : __malloc_assert (#expr, __FILE__, __LINE__, __func__))
284 extern const char *__progname;
286 static void
287 __malloc_assert (const char *assertion, const char *file, unsigned int line,
288 const char *function)
290 (void) __fxprintf (NULL, "%s%s%s:%u: %s%sAssertion `%s' failed.\n",
291 __progname, __progname[0] ? ": " : "",
292 file, line,
293 function ? function : "", function ? ": " : "",
294 assertion);
295 fflush (stderr);
296 abort ();
298 #endif
302 REALLOC_ZERO_BYTES_FREES should be set if a call to
303 realloc with zero bytes should be the same as a call to free.
304 This is required by the C standard. Otherwise, since this malloc
305 returns a unique pointer for malloc(0), so does realloc(p, 0).
308 #ifndef REALLOC_ZERO_BYTES_FREES
309 #define REALLOC_ZERO_BYTES_FREES 1
310 #endif
313 TRIM_FASTBINS controls whether free() of a very small chunk can
314 immediately lead to trimming. Setting to true (1) can reduce memory
315 footprint, but will almost always slow down programs that use a lot
316 of small chunks.
318 Define this only if you are willing to give up some speed to more
319 aggressively reduce system-level memory footprint when releasing
320 memory in programs that use many small chunks. You can get
321 essentially the same effect by setting MXFAST to 0, but this can
322 lead to even greater slowdowns in programs using many small chunks.
323 TRIM_FASTBINS is an in-between compile-time option, that disables
324 only those chunks bordering topmost memory from being placed in
325 fastbins.
328 #ifndef TRIM_FASTBINS
329 #define TRIM_FASTBINS 0
330 #endif
333 /* Definition for getting more memory from the OS. */
334 #define MORECORE (*__morecore)
335 #define MORECORE_FAILURE 0
336 void * __default_morecore (ptrdiff_t);
337 void *(*__morecore)(ptrdiff_t) = __default_morecore;
340 #include <string.h>
343 MORECORE-related declarations. By default, rely on sbrk
348 MORECORE is the name of the routine to call to obtain more memory
349 from the system. See below for general guidance on writing
350 alternative MORECORE functions, as well as a version for WIN32 and a
351 sample version for pre-OSX macos.
354 #ifndef MORECORE
355 #define MORECORE sbrk
356 #endif
359 MORECORE_FAILURE is the value returned upon failure of MORECORE
360 as well as mmap. Since it cannot be an otherwise valid memory address,
361 and must reflect values of standard sys calls, you probably ought not
362 try to redefine it.
365 #ifndef MORECORE_FAILURE
366 #define MORECORE_FAILURE (-1)
367 #endif
370 If MORECORE_CONTIGUOUS is true, take advantage of fact that
371 consecutive calls to MORECORE with positive arguments always return
372 contiguous increasing addresses. This is true of unix sbrk. Even
373 if not defined, when regions happen to be contiguous, malloc will
374 permit allocations spanning regions obtained from different
375 calls. But defining this when applicable enables some stronger
376 consistency checks and space efficiencies.
379 #ifndef MORECORE_CONTIGUOUS
380 #define MORECORE_CONTIGUOUS 1
381 #endif
384 Define MORECORE_CANNOT_TRIM if your version of MORECORE
385 cannot release space back to the system when given negative
386 arguments. This is generally necessary only if you are using
387 a hand-crafted MORECORE function that cannot handle negative arguments.
390 /* #define MORECORE_CANNOT_TRIM */
392 /* MORECORE_CLEARS (default 1)
393 The degree to which the routine mapped to MORECORE zeroes out
394 memory: never (0), only for newly allocated space (1) or always
395 (2). The distinction between (1) and (2) is necessary because on
396 some systems, if the application first decrements and then
397 increments the break value, the contents of the reallocated space
398 are unspecified.
401 #ifndef MORECORE_CLEARS
402 # define MORECORE_CLEARS 1
403 #endif
407 MMAP_AS_MORECORE_SIZE is the minimum mmap size argument to use if
408 sbrk fails, and mmap is used as a backup. The value must be a
409 multiple of page size. This backup strategy generally applies only
410 when systems have "holes" in address space, so sbrk cannot perform
411 contiguous expansion, but there is still space available on system.
412 On systems for which this is known to be useful (i.e. most linux
413 kernels), this occurs only when programs allocate huge amounts of
414 memory. Between this, and the fact that mmap regions tend to be
415 limited, the size should be large, to avoid too many mmap calls and
416 thus avoid running out of kernel resources. */
418 #ifndef MMAP_AS_MORECORE_SIZE
419 #define MMAP_AS_MORECORE_SIZE (1024 * 1024)
420 #endif
423 Define HAVE_MREMAP to make realloc() use mremap() to re-allocate
424 large blocks.
427 #ifndef HAVE_MREMAP
428 #define HAVE_MREMAP 0
429 #endif
431 /* We may need to support __malloc_initialize_hook for backwards
432 compatibility. */
434 #if SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_24)
435 # define HAVE_MALLOC_INIT_HOOK 1
436 #else
437 # define HAVE_MALLOC_INIT_HOOK 0
438 #endif
442 This version of malloc supports the standard SVID/XPG mallinfo
443 routine that returns a struct containing usage properties and
444 statistics. It should work on any SVID/XPG compliant system that has
445 a /usr/include/malloc.h defining struct mallinfo. (If you'd like to
446 install such a thing yourself, cut out the preliminary declarations
447 as described above and below and save them in a malloc.h file. But
448 there's no compelling reason to bother to do this.)
450 The main declaration needed is the mallinfo struct that is returned
451 (by-copy) by mallinfo(). The SVID/XPG malloinfo struct contains a
452 bunch of fields that are not even meaningful in this version of
453 malloc. These fields are are instead filled by mallinfo() with
454 other numbers that might be of interest.
458 /* ---------- description of public routines ------------ */
461 malloc(size_t n)
462 Returns a pointer to a newly allocated chunk of at least n bytes, or null
463 if no space is available. Additionally, on failure, errno is
464 set to ENOMEM on ANSI C systems.
466 If n is zero, malloc returns a minumum-sized chunk. (The minimum
467 size is 16 bytes on most 32bit systems, and 24 or 32 bytes on 64bit
468 systems.) On most systems, size_t is an unsigned type, so calls
469 with negative arguments are interpreted as requests for huge amounts
470 of space, which will often fail. The maximum supported value of n
471 differs across systems, but is in all cases less than the maximum
472 representable value of a size_t.
474 void* __libc_malloc(size_t);
475 libc_hidden_proto (__libc_malloc)
478 free(void* p)
479 Releases the chunk of memory pointed to by p, that had been previously
480 allocated using malloc or a related routine such as realloc.
481 It has no effect if p is null. It can have arbitrary (i.e., bad!)
482 effects if p has already been freed.
484 Unless disabled (using mallopt), freeing very large spaces will
485 when possible, automatically trigger operations that give
486 back unused memory to the system, thus reducing program footprint.
488 void __libc_free(void*);
489 libc_hidden_proto (__libc_free)
492 calloc(size_t n_elements, size_t element_size);
493 Returns a pointer to n_elements * element_size bytes, with all locations
494 set to zero.
496 void* __libc_calloc(size_t, size_t);
499 realloc(void* p, size_t n)
500 Returns a pointer to a chunk of size n that contains the same data
501 as does chunk p up to the minimum of (n, p's size) bytes, or null
502 if no space is available.
504 The returned pointer may or may not be the same as p. The algorithm
505 prefers extending p when possible, otherwise it employs the
506 equivalent of a malloc-copy-free sequence.
508 If p is null, realloc is equivalent to malloc.
510 If space is not available, realloc returns null, errno is set (if on
511 ANSI) and p is NOT freed.
513 if n is for fewer bytes than already held by p, the newly unused
514 space is lopped off and freed if possible. Unless the #define
515 REALLOC_ZERO_BYTES_FREES is set, realloc with a size argument of
516 zero (re)allocates a minimum-sized chunk.
518 Large chunks that were internally obtained via mmap will always
519 be reallocated using malloc-copy-free sequences unless
520 the system supports MREMAP (currently only linux).
522 The old unix realloc convention of allowing the last-free'd chunk
523 to be used as an argument to realloc is not supported.
525 void* __libc_realloc(void*, size_t);
526 libc_hidden_proto (__libc_realloc)
529 memalign(size_t alignment, size_t n);
530 Returns a pointer to a newly allocated chunk of n bytes, aligned
531 in accord with the alignment argument.
533 The alignment argument should be a power of two. If the argument is
534 not a power of two, the nearest greater power is used.
535 8-byte alignment is guaranteed by normal malloc calls, so don't
536 bother calling memalign with an argument of 8 or less.
538 Overreliance on memalign is a sure way to fragment space.
540 void* __libc_memalign(size_t, size_t);
541 libc_hidden_proto (__libc_memalign)
544 valloc(size_t n);
545 Equivalent to memalign(pagesize, n), where pagesize is the page
546 size of the system. If the pagesize is unknown, 4096 is used.
548 void* __libc_valloc(size_t);
553 mallopt(int parameter_number, int parameter_value)
554 Sets tunable parameters The format is to provide a
555 (parameter-number, parameter-value) pair. mallopt then sets the
556 corresponding parameter to the argument value if it can (i.e., so
557 long as the value is meaningful), and returns 1 if successful else
558 0. SVID/XPG/ANSI defines four standard param numbers for mallopt,
559 normally defined in malloc.h. Only one of these (M_MXFAST) is used
560 in this malloc. The others (M_NLBLKS, M_GRAIN, M_KEEP) don't apply,
561 so setting them has no effect. But this malloc also supports four
562 other options in mallopt. See below for details. Briefly, supported
563 parameters are as follows (listed defaults are for "typical"
564 configurations).
566 Symbol param # default allowed param values
567 M_MXFAST 1 64 0-80 (0 disables fastbins)
568 M_TRIM_THRESHOLD -1 128*1024 any (-1U disables trimming)
569 M_TOP_PAD -2 0 any
570 M_MMAP_THRESHOLD -3 128*1024 any (or 0 if no MMAP support)
571 M_MMAP_MAX -4 65536 any (0 disables use of mmap)
573 int __libc_mallopt(int, int);
574 libc_hidden_proto (__libc_mallopt)
578 mallinfo()
579 Returns (by copy) a struct containing various summary statistics:
581 arena: current total non-mmapped bytes allocated from system
582 ordblks: the number of free chunks
583 smblks: the number of fastbin blocks (i.e., small chunks that
584 have been freed but not use resused or consolidated)
585 hblks: current number of mmapped regions
586 hblkhd: total bytes held in mmapped regions
587 usmblks: always 0
588 fsmblks: total bytes held in fastbin blocks
589 uordblks: current total allocated space (normal or mmapped)
590 fordblks: total free space
591 keepcost: the maximum number of bytes that could ideally be released
592 back to system via malloc_trim. ("ideally" means that
593 it ignores page restrictions etc.)
595 Because these fields are ints, but internal bookkeeping may
596 be kept as longs, the reported values may wrap around zero and
597 thus be inaccurate.
599 struct mallinfo __libc_mallinfo(void);
603 pvalloc(size_t n);
604 Equivalent to valloc(minimum-page-that-holds(n)), that is,
605 round up n to nearest pagesize.
607 void* __libc_pvalloc(size_t);
610 malloc_trim(size_t pad);
612 If possible, gives memory back to the system (via negative
613 arguments to sbrk) if there is unused memory at the `high' end of
614 the malloc pool. You can call this after freeing large blocks of
615 memory to potentially reduce the system-level memory requirements
616 of a program. However, it cannot guarantee to reduce memory. Under
617 some allocation patterns, some large free blocks of memory will be
618 locked between two used chunks, so they cannot be given back to
619 the system.
621 The `pad' argument to malloc_trim represents the amount of free
622 trailing space to leave untrimmed. If this argument is zero,
623 only the minimum amount of memory to maintain internal data
624 structures will be left (one page or less). Non-zero arguments
625 can be supplied to maintain enough trailing space to service
626 future expected allocations without having to re-obtain memory
627 from the system.
629 Malloc_trim returns 1 if it actually released any memory, else 0.
630 On systems that do not support "negative sbrks", it will always
631 return 0.
633 int __malloc_trim(size_t);
636 malloc_usable_size(void* p);
638 Returns the number of bytes you can actually use in
639 an allocated chunk, which may be more than you requested (although
640 often not) due to alignment and minimum size constraints.
641 You can use this many bytes without worrying about
642 overwriting other allocated objects. This is not a particularly great
643 programming practice. malloc_usable_size can be more useful in
644 debugging and assertions, for example:
646 p = malloc(n);
647 assert(malloc_usable_size(p) >= 256);
650 size_t __malloc_usable_size(void*);
653 malloc_stats();
654 Prints on stderr the amount of space obtained from the system (both
655 via sbrk and mmap), the maximum amount (which may be more than
656 current if malloc_trim and/or munmap got called), and the current
657 number of bytes allocated via malloc (or realloc, etc) but not yet
658 freed. Note that this is the number of bytes allocated, not the
659 number requested. It will be larger than the number requested
660 because of alignment and bookkeeping overhead. Because it includes
661 alignment wastage as being in use, this figure may be greater than
662 zero even when no user-level chunks are allocated.
664 The reported current and maximum system memory can be inaccurate if
665 a program makes other calls to system memory allocation functions
666 (normally sbrk) outside of malloc.
668 malloc_stats prints only the most commonly interesting statistics.
669 More information can be obtained by calling mallinfo.
672 void __malloc_stats(void);
675 malloc_get_state(void);
677 Returns the state of all malloc variables in an opaque data
678 structure.
680 void* __malloc_get_state(void);
683 malloc_set_state(void* state);
685 Restore the state of all malloc variables from data obtained with
686 malloc_get_state().
688 int __malloc_set_state(void*);
691 posix_memalign(void **memptr, size_t alignment, size_t size);
693 POSIX wrapper like memalign(), checking for validity of size.
695 int __posix_memalign(void **, size_t, size_t);
697 /* mallopt tuning options */
700 M_MXFAST is the maximum request size used for "fastbins", special bins
701 that hold returned chunks without consolidating their spaces. This
702 enables future requests for chunks of the same size to be handled
703 very quickly, but can increase fragmentation, and thus increase the
704 overall memory footprint of a program.
706 This malloc manages fastbins very conservatively yet still
707 efficiently, so fragmentation is rarely a problem for values less
708 than or equal to the default. The maximum supported value of MXFAST
709 is 80. You wouldn't want it any higher than this anyway. Fastbins
710 are designed especially for use with many small structs, objects or
711 strings -- the default handles structs/objects/arrays with sizes up
712 to 8 4byte fields, or small strings representing words, tokens,
713 etc. Using fastbins for larger objects normally worsens
714 fragmentation without improving speed.
716 M_MXFAST is set in REQUEST size units. It is internally used in
717 chunksize units, which adds padding and alignment. You can reduce
718 M_MXFAST to 0 to disable all use of fastbins. This causes the malloc
719 algorithm to be a closer approximation of fifo-best-fit in all cases,
720 not just for larger requests, but will generally cause it to be
721 slower.
725 /* M_MXFAST is a standard SVID/XPG tuning option, usually listed in malloc.h */
726 #ifndef M_MXFAST
727 #define M_MXFAST 1
728 #endif
730 #ifndef DEFAULT_MXFAST
731 #define DEFAULT_MXFAST (64 * SIZE_SZ / 4)
732 #endif
736 M_TRIM_THRESHOLD is the maximum amount of unused top-most memory
737 to keep before releasing via malloc_trim in free().
739 Automatic trimming is mainly useful in long-lived programs.
740 Because trimming via sbrk can be slow on some systems, and can
741 sometimes be wasteful (in cases where programs immediately
742 afterward allocate more large chunks) the value should be high
743 enough so that your overall system performance would improve by
744 releasing this much memory.
746 The trim threshold and the mmap control parameters (see below)
747 can be traded off with one another. Trimming and mmapping are
748 two different ways of releasing unused memory back to the
749 system. Between these two, it is often possible to keep
750 system-level demands of a long-lived program down to a bare
751 minimum. For example, in one test suite of sessions measuring
752 the XF86 X server on Linux, using a trim threshold of 128K and a
753 mmap threshold of 192K led to near-minimal long term resource
754 consumption.
756 If you are using this malloc in a long-lived program, it should
757 pay to experiment with these values. As a rough guide, you
758 might set to a value close to the average size of a process
759 (program) running on your system. Releasing this much memory
760 would allow such a process to run in memory. Generally, it's
761 worth it to tune for trimming rather tham memory mapping when a
762 program undergoes phases where several large chunks are
763 allocated and released in ways that can reuse each other's
764 storage, perhaps mixed with phases where there are no such
765 chunks at all. And in well-behaved long-lived programs,
766 controlling release of large blocks via trimming versus mapping
767 is usually faster.
769 However, in most programs, these parameters serve mainly as
770 protection against the system-level effects of carrying around
771 massive amounts of unneeded memory. Since frequent calls to
772 sbrk, mmap, and munmap otherwise degrade performance, the default
773 parameters are set to relatively high values that serve only as
774 safeguards.
776 The trim value It must be greater than page size to have any useful
777 effect. To disable trimming completely, you can set to
778 (unsigned long)(-1)
780 Trim settings interact with fastbin (MXFAST) settings: Unless
781 TRIM_FASTBINS is defined, automatic trimming never takes place upon
782 freeing a chunk with size less than or equal to MXFAST. Trimming is
783 instead delayed until subsequent freeing of larger chunks. However,
784 you can still force an attempted trim by calling malloc_trim.
786 Also, trimming is not generally possible in cases where
787 the main arena is obtained via mmap.
789 Note that the trick some people use of mallocing a huge space and
790 then freeing it at program startup, in an attempt to reserve system
791 memory, doesn't have the intended effect under automatic trimming,
792 since that memory will immediately be returned to the system.
795 #define M_TRIM_THRESHOLD -1
797 #ifndef DEFAULT_TRIM_THRESHOLD
798 #define DEFAULT_TRIM_THRESHOLD (128 * 1024)
799 #endif
802 M_TOP_PAD is the amount of extra `padding' space to allocate or
803 retain whenever sbrk is called. It is used in two ways internally:
805 * When sbrk is called to extend the top of the arena to satisfy
806 a new malloc request, this much padding is added to the sbrk
807 request.
809 * When malloc_trim is called automatically from free(),
810 it is used as the `pad' argument.
812 In both cases, the actual amount of padding is rounded
813 so that the end of the arena is always a system page boundary.
815 The main reason for using padding is to avoid calling sbrk so
816 often. Having even a small pad greatly reduces the likelihood
817 that nearly every malloc request during program start-up (or
818 after trimming) will invoke sbrk, which needlessly wastes
819 time.
821 Automatic rounding-up to page-size units is normally sufficient
822 to avoid measurable overhead, so the default is 0. However, in
823 systems where sbrk is relatively slow, it can pay to increase
824 this value, at the expense of carrying around more memory than
825 the program needs.
828 #define M_TOP_PAD -2
830 #ifndef DEFAULT_TOP_PAD
831 #define DEFAULT_TOP_PAD (0)
832 #endif
835 MMAP_THRESHOLD_MAX and _MIN are the bounds on the dynamically
836 adjusted MMAP_THRESHOLD.
839 #ifndef DEFAULT_MMAP_THRESHOLD_MIN
840 #define DEFAULT_MMAP_THRESHOLD_MIN (128 * 1024)
841 #endif
843 #ifndef DEFAULT_MMAP_THRESHOLD_MAX
844 /* For 32-bit platforms we cannot increase the maximum mmap
845 threshold much because it is also the minimum value for the
846 maximum heap size and its alignment. Going above 512k (i.e., 1M
847 for new heaps) wastes too much address space. */
848 # if __WORDSIZE == 32
849 # define DEFAULT_MMAP_THRESHOLD_MAX (512 * 1024)
850 # else
851 # define DEFAULT_MMAP_THRESHOLD_MAX (4 * 1024 * 1024 * sizeof(long))
852 # endif
853 #endif
856 M_MMAP_THRESHOLD is the request size threshold for using mmap()
857 to service a request. Requests of at least this size that cannot
858 be allocated using already-existing space will be serviced via mmap.
859 (If enough normal freed space already exists it is used instead.)
861 Using mmap segregates relatively large chunks of memory so that
862 they can be individually obtained and released from the host
863 system. A request serviced through mmap is never reused by any
864 other request (at least not directly; the system may just so
865 happen to remap successive requests to the same locations).
867 Segregating space in this way has the benefits that:
869 1. Mmapped space can ALWAYS be individually released back
870 to the system, which helps keep the system level memory
871 demands of a long-lived program low.
872 2. Mapped memory can never become `locked' between
873 other chunks, as can happen with normally allocated chunks, which
874 means that even trimming via malloc_trim would not release them.
875 3. On some systems with "holes" in address spaces, mmap can obtain
876 memory that sbrk cannot.
878 However, it has the disadvantages that:
880 1. The space cannot be reclaimed, consolidated, and then
881 used to service later requests, as happens with normal chunks.
882 2. It can lead to more wastage because of mmap page alignment
883 requirements
884 3. It causes malloc performance to be more dependent on host
885 system memory management support routines which may vary in
886 implementation quality and may impose arbitrary
887 limitations. Generally, servicing a request via normal
888 malloc steps is faster than going through a system's mmap.
890 The advantages of mmap nearly always outweigh disadvantages for
891 "large" chunks, but the value of "large" varies across systems. The
892 default is an empirically derived value that works well in most
893 systems.
896 Update in 2006:
897 The above was written in 2001. Since then the world has changed a lot.
898 Memory got bigger. Applications got bigger. The virtual address space
899 layout in 32 bit linux changed.
901 In the new situation, brk() and mmap space is shared and there are no
902 artificial limits on brk size imposed by the kernel. What is more,
903 applications have started using transient allocations larger than the
904 128Kb as was imagined in 2001.
906 The price for mmap is also high now; each time glibc mmaps from the
907 kernel, the kernel is forced to zero out the memory it gives to the
908 application. Zeroing memory is expensive and eats a lot of cache and
909 memory bandwidth. This has nothing to do with the efficiency of the
910 virtual memory system, by doing mmap the kernel just has no choice but
911 to zero.
913 In 2001, the kernel had a maximum size for brk() which was about 800
914 megabytes on 32 bit x86, at that point brk() would hit the first
915 mmaped shared libaries and couldn't expand anymore. With current 2.6
916 kernels, the VA space layout is different and brk() and mmap
917 both can span the entire heap at will.
919 Rather than using a static threshold for the brk/mmap tradeoff,
920 we are now using a simple dynamic one. The goal is still to avoid
921 fragmentation. The old goals we kept are
922 1) try to get the long lived large allocations to use mmap()
923 2) really large allocations should always use mmap()
924 and we're adding now:
925 3) transient allocations should use brk() to avoid forcing the kernel
926 having to zero memory over and over again
928 The implementation works with a sliding threshold, which is by default
929 limited to go between 128Kb and 32Mb (64Mb for 64 bitmachines) and starts
930 out at 128Kb as per the 2001 default.
932 This allows us to satisfy requirement 1) under the assumption that long
933 lived allocations are made early in the process' lifespan, before it has
934 started doing dynamic allocations of the same size (which will
935 increase the threshold).
937 The upperbound on the threshold satisfies requirement 2)
939 The threshold goes up in value when the application frees memory that was
940 allocated with the mmap allocator. The idea is that once the application
941 starts freeing memory of a certain size, it's highly probable that this is
942 a size the application uses for transient allocations. This estimator
943 is there to satisfy the new third requirement.
947 #define M_MMAP_THRESHOLD -3
949 #ifndef DEFAULT_MMAP_THRESHOLD
950 #define DEFAULT_MMAP_THRESHOLD DEFAULT_MMAP_THRESHOLD_MIN
951 #endif
954 M_MMAP_MAX is the maximum number of requests to simultaneously
955 service using mmap. This parameter exists because
956 some systems have a limited number of internal tables for
957 use by mmap, and using more than a few of them may degrade
958 performance.
960 The default is set to a value that serves only as a safeguard.
961 Setting to 0 disables use of mmap for servicing large requests.
964 #define M_MMAP_MAX -4
966 #ifndef DEFAULT_MMAP_MAX
967 #define DEFAULT_MMAP_MAX (65536)
968 #endif
970 #include <malloc.h>
972 #ifndef RETURN_ADDRESS
973 #define RETURN_ADDRESS(X_) (NULL)
974 #endif
976 /* On some platforms we can compile internal, not exported functions better.
977 Let the environment provide a macro and define it to be empty if it
978 is not available. */
979 #ifndef internal_function
980 # define internal_function
981 #endif
983 /* Forward declarations. */
984 struct malloc_chunk;
985 typedef struct malloc_chunk* mchunkptr;
987 /* Internal routines. */
989 static void* _int_malloc(mstate, size_t);
990 static void _int_free(mstate, mchunkptr, int);
991 static void* _int_realloc(mstate, mchunkptr, INTERNAL_SIZE_T,
992 INTERNAL_SIZE_T);
993 static void* _int_memalign(mstate, size_t, size_t);
994 static void* _mid_memalign(size_t, size_t, void *);
996 static void malloc_printerr(int action, const char *str, void *ptr, mstate av);
998 static void* internal_function mem2mem_check(void *p, size_t sz);
999 static int internal_function top_check(void);
1000 static void internal_function munmap_chunk(mchunkptr p);
1001 #if HAVE_MREMAP
1002 static mchunkptr internal_function mremap_chunk(mchunkptr p, size_t new_size);
1003 #endif
1005 static void* malloc_check(size_t sz, const void *caller);
1006 static void free_check(void* mem, const void *caller);
1007 static void* realloc_check(void* oldmem, size_t bytes,
1008 const void *caller);
1009 static void* memalign_check(size_t alignment, size_t bytes,
1010 const void *caller);
1012 /* ------------------ MMAP support ------------------ */
1015 #include <fcntl.h>
1016 #include <sys/mman.h>
1018 #if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
1019 # define MAP_ANONYMOUS MAP_ANON
1020 #endif
1022 #ifndef MAP_NORESERVE
1023 # define MAP_NORESERVE 0
1024 #endif
1026 #define MMAP(addr, size, prot, flags) \
1027 __mmap((addr), (size), (prot), (flags)|MAP_ANONYMOUS|MAP_PRIVATE, -1, 0)
1031 ----------------------- Chunk representations -----------------------
1036 This struct declaration is misleading (but accurate and necessary).
1037 It declares a "view" into memory allowing access to necessary
1038 fields at known offsets from a given base. See explanation below.
1041 struct malloc_chunk {
1043 INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
1044 INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
1046 struct malloc_chunk* fd; /* double links -- used only if free. */
1047 struct malloc_chunk* bk;
1049 /* Only used for large blocks: pointer to next larger size. */
1050 struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
1051 struct malloc_chunk* bk_nextsize;
1056 malloc_chunk details:
1058 (The following includes lightly edited explanations by Colin Plumb.)
1060 Chunks of memory are maintained using a `boundary tag' method as
1061 described in e.g., Knuth or Standish. (See the paper by Paul
1062 Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a
1063 survey of such techniques.) Sizes of free chunks are stored both
1064 in the front of each chunk and at the end. This makes
1065 consolidating fragmented chunks into bigger chunks very fast. The
1066 size fields also hold bits representing whether chunks are free or
1067 in use.
1069 An allocated chunk looks like this:
1072 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1073 | Size of previous chunk, if allocated | |
1074 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1075 | Size of chunk, in bytes |M|P|
1076 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1077 | User data starts here... .
1079 . (malloc_usable_size() bytes) .
1081 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1082 | Size of chunk |
1083 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1086 Where "chunk" is the front of the chunk for the purpose of most of
1087 the malloc code, but "mem" is the pointer that is returned to the
1088 user. "Nextchunk" is the beginning of the next contiguous chunk.
1090 Chunks always begin on even word boundaries, so the mem portion
1091 (which is returned to the user) is also on an even word boundary, and
1092 thus at least double-word aligned.
1094 Free chunks are stored in circular doubly-linked lists, and look like this:
1096 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1097 | Size of previous chunk |
1098 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1099 `head:' | Size of chunk, in bytes |P|
1100 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1101 | Forward pointer to next chunk in list |
1102 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1103 | Back pointer to previous chunk in list |
1104 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1105 | Unused space (may be 0 bytes long) .
1108 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1109 `foot:' | Size of chunk, in bytes |
1110 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1112 The P (PREV_INUSE) bit, stored in the unused low-order bit of the
1113 chunk size (which is always a multiple of two words), is an in-use
1114 bit for the *previous* chunk. If that bit is *clear*, then the
1115 word before the current chunk size contains the previous chunk
1116 size, and can be used to find the front of the previous chunk.
1117 The very first chunk allocated always has this bit set,
1118 preventing access to non-existent (or non-owned) memory. If
1119 prev_inuse is set for any given chunk, then you CANNOT determine
1120 the size of the previous chunk, and might even get a memory
1121 addressing fault when trying to do so.
1123 Note that the `foot' of the current chunk is actually represented
1124 as the prev_size of the NEXT chunk. This makes it easier to
1125 deal with alignments etc but can be very confusing when trying
1126 to extend or adapt this code.
1128 The two exceptions to all this are
1130 1. The special chunk `top' doesn't bother using the
1131 trailing size field since there is no next contiguous chunk
1132 that would have to index off it. After initialization, `top'
1133 is forced to always exist. If it would become less than
1134 MINSIZE bytes long, it is replenished.
1136 2. Chunks allocated via mmap, which have the second-lowest-order
1137 bit M (IS_MMAPPED) set in their size fields. Because they are
1138 allocated one-by-one, each must contain its own trailing size field.
1143 ---------- Size and alignment checks and conversions ----------
1146 /* conversion from malloc headers to user pointers, and back */
1148 #define chunk2mem(p) ((void*)((char*)(p) + 2*SIZE_SZ))
1149 #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))
1151 /* The smallest possible chunk */
1152 #define MIN_CHUNK_SIZE (offsetof(struct malloc_chunk, fd_nextsize))
1154 /* The smallest size we can malloc is an aligned minimal chunk */
1156 #define MINSIZE \
1157 (unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))
1159 /* Check if m has acceptable alignment */
1161 #define aligned_OK(m) (((unsigned long)(m) & MALLOC_ALIGN_MASK) == 0)
1163 #define misaligned_chunk(p) \
1164 ((uintptr_t)(MALLOC_ALIGNMENT == 2 * SIZE_SZ ? (p) : chunk2mem (p)) \
1165 & MALLOC_ALIGN_MASK)
1169 Check if a request is so large that it would wrap around zero when
1170 padded and aligned. To simplify some other code, the bound is made
1171 low enough so that adding MINSIZE will also not wrap around zero.
1174 #define REQUEST_OUT_OF_RANGE(req) \
1175 ((unsigned long) (req) >= \
1176 (unsigned long) (INTERNAL_SIZE_T) (-2 * MINSIZE))
1178 /* pad request bytes into a usable size -- internal version */
1180 #define request2size(req) \
1181 (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ? \
1182 MINSIZE : \
1183 ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
1185 /* Same, except also perform argument check */
1187 #define checked_request2size(req, sz) \
1188 if (REQUEST_OUT_OF_RANGE (req)) { \
1189 __set_errno (ENOMEM); \
1190 return 0; \
1192 (sz) = request2size (req);
1195 --------------- Physical chunk operations ---------------
1199 /* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
1200 #define PREV_INUSE 0x1
1202 /* extract inuse bit of previous chunk */
1203 #define prev_inuse(p) ((p)->size & PREV_INUSE)
1206 /* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */
1207 #define IS_MMAPPED 0x2
1209 /* check for mmap()'ed chunk */
1210 #define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)
1213 /* size field is or'ed with NON_MAIN_ARENA if the chunk was obtained
1214 from a non-main arena. This is only set immediately before handing
1215 the chunk to the user, if necessary. */
1216 #define NON_MAIN_ARENA 0x4
1218 /* check for chunk from non-main arena */
1219 #define chunk_non_main_arena(p) ((p)->size & NON_MAIN_ARENA)
1223 Bits to mask off when extracting size
1225 Note: IS_MMAPPED is intentionally not masked off from size field in
1226 macros for which mmapped chunks should never be seen. This should
1227 cause helpful core dumps to occur if it is tried by accident by
1228 people extending or adapting this malloc.
1230 #define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
1232 /* Get size, ignoring use bits */
1233 #define chunksize(p) ((p)->size & ~(SIZE_BITS))
1236 /* Ptr to next physical malloc_chunk. */
1237 #define next_chunk(p) ((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))
1239 /* Ptr to previous physical malloc_chunk */
1240 #define prev_chunk(p) ((mchunkptr) (((char *) (p)) - ((p)->prev_size)))
1242 /* Treat space at ptr + offset as a chunk */
1243 #define chunk_at_offset(p, s) ((mchunkptr) (((char *) (p)) + (s)))
1245 /* extract p's inuse bit */
1246 #define inuse(p) \
1247 ((((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))->size) & PREV_INUSE)
1249 /* set/clear chunk as being inuse without otherwise disturbing */
1250 #define set_inuse(p) \
1251 ((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))->size |= PREV_INUSE
1253 #define clear_inuse(p) \
1254 ((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))->size &= ~(PREV_INUSE)
1257 /* check/set/clear inuse bits in known places */
1258 #define inuse_bit_at_offset(p, s) \
1259 (((mchunkptr) (((char *) (p)) + (s)))->size & PREV_INUSE)
1261 #define set_inuse_bit_at_offset(p, s) \
1262 (((mchunkptr) (((char *) (p)) + (s)))->size |= PREV_INUSE)
1264 #define clear_inuse_bit_at_offset(p, s) \
1265 (((mchunkptr) (((char *) (p)) + (s)))->size &= ~(PREV_INUSE))
1268 /* Set size at head, without disturbing its use bit */
1269 #define set_head_size(p, s) ((p)->size = (((p)->size & SIZE_BITS) | (s)))
1271 /* Set size/use field */
1272 #define set_head(p, s) ((p)->size = (s))
1274 /* Set size at footer (only when chunk is not in use) */
1275 #define set_foot(p, s) (((mchunkptr) ((char *) (p) + (s)))->prev_size = (s))
1279 -------------------- Internal data structures --------------------
1281 All internal state is held in an instance of malloc_state defined
1282 below. There are no other static variables, except in two optional
1283 cases:
1284 * If USE_MALLOC_LOCK is defined, the mALLOC_MUTEx declared above.
1285 * If mmap doesn't support MAP_ANONYMOUS, a dummy file descriptor
1286 for mmap.
1288 Beware of lots of tricks that minimize the total bookkeeping space
1289 requirements. The result is a little over 1K bytes (for 4byte
1290 pointers and size_t.)
1294 Bins
1296 An array of bin headers for free chunks. Each bin is doubly
1297 linked. The bins are approximately proportionally (log) spaced.
1298 There are a lot of these bins (128). This may look excessive, but
1299 works very well in practice. Most bins hold sizes that are
1300 unusual as malloc request sizes, but are more usual for fragments
1301 and consolidated sets of chunks, which is what these bins hold, so
1302 they can be found quickly. All procedures maintain the invariant
1303 that no consolidated chunk physically borders another one, so each
1304 chunk in a list is known to be preceeded and followed by either
1305 inuse chunks or the ends of memory.
1307 Chunks in bins are kept in size order, with ties going to the
1308 approximately least recently used chunk. Ordering isn't needed
1309 for the small bins, which all contain the same-sized chunks, but
1310 facilitates best-fit allocation for larger chunks. These lists
1311 are just sequential. Keeping them in order almost never requires
1312 enough traversal to warrant using fancier ordered data
1313 structures.
1315 Chunks of the same size are linked with the most
1316 recently freed at the front, and allocations are taken from the
1317 back. This results in LRU (FIFO) allocation order, which tends
1318 to give each chunk an equal opportunity to be consolidated with
1319 adjacent freed chunks, resulting in larger free chunks and less
1320 fragmentation.
1322 To simplify use in double-linked lists, each bin header acts
1323 as a malloc_chunk. This avoids special-casing for headers.
1324 But to conserve space and improve locality, we allocate
1325 only the fd/bk pointers of bins, and then use repositioning tricks
1326 to treat these as the fields of a malloc_chunk*.
1329 typedef struct malloc_chunk *mbinptr;
1331 /* addressing -- note that bin_at(0) does not exist */
1332 #define bin_at(m, i) \
1333 (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2])) \
1334 - offsetof (struct malloc_chunk, fd))
1336 /* analog of ++bin */
1337 #define next_bin(b) ((mbinptr) ((char *) (b) + (sizeof (mchunkptr) << 1)))
1339 /* Reminders about list directionality within bins */
1340 #define first(b) ((b)->fd)
1341 #define last(b) ((b)->bk)
1343 /* Take a chunk off a bin list */
1344 #define unlink(AV, P, BK, FD) { \
1345 FD = P->fd; \
1346 BK = P->bk; \
1347 if (__builtin_expect (FD->bk != P || BK->fd != P, 0)) \
1348 malloc_printerr (check_action, "corrupted double-linked list", P, AV); \
1349 else { \
1350 FD->bk = BK; \
1351 BK->fd = FD; \
1352 if (!in_smallbin_range (P->size) \
1353 && __builtin_expect (P->fd_nextsize != NULL, 0)) { \
1354 if (__builtin_expect (P->fd_nextsize->bk_nextsize != P, 0) \
1355 || __builtin_expect (P->bk_nextsize->fd_nextsize != P, 0)) \
1356 malloc_printerr (check_action, \
1357 "corrupted double-linked list (not small)", \
1358 P, AV); \
1359 if (FD->fd_nextsize == NULL) { \
1360 if (P->fd_nextsize == P) \
1361 FD->fd_nextsize = FD->bk_nextsize = FD; \
1362 else { \
1363 FD->fd_nextsize = P->fd_nextsize; \
1364 FD->bk_nextsize = P->bk_nextsize; \
1365 P->fd_nextsize->bk_nextsize = FD; \
1366 P->bk_nextsize->fd_nextsize = FD; \
1368 } else { \
1369 P->fd_nextsize->bk_nextsize = P->bk_nextsize; \
1370 P->bk_nextsize->fd_nextsize = P->fd_nextsize; \
1377 Indexing
1379 Bins for sizes < 512 bytes contain chunks of all the same size, spaced
1380 8 bytes apart. Larger bins are approximately logarithmically spaced:
1382 64 bins of size 8
1383 32 bins of size 64
1384 16 bins of size 512
1385 8 bins of size 4096
1386 4 bins of size 32768
1387 2 bins of size 262144
1388 1 bin of size what's left
1390 There is actually a little bit of slop in the numbers in bin_index
1391 for the sake of speed. This makes no difference elsewhere.
1393 The bins top out around 1MB because we expect to service large
1394 requests via mmap.
1396 Bin 0 does not exist. Bin 1 is the unordered list; if that would be
1397 a valid chunk size the small bins are bumped up one.
1400 #define NBINS 128
1401 #define NSMALLBINS 64
1402 #define SMALLBIN_WIDTH MALLOC_ALIGNMENT
1403 #define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ)
1404 #define MIN_LARGE_SIZE ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)
1406 #define in_smallbin_range(sz) \
1407 ((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)
1409 #define smallbin_index(sz) \
1410 ((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\
1411 + SMALLBIN_CORRECTION)
1413 #define largebin_index_32(sz) \
1414 (((((unsigned long) (sz)) >> 6) <= 38) ? 56 + (((unsigned long) (sz)) >> 6) :\
1415 ((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :\
1416 ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
1417 ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
1418 ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
1419 126)
1421 #define largebin_index_32_big(sz) \
1422 (((((unsigned long) (sz)) >> 6) <= 45) ? 49 + (((unsigned long) (sz)) >> 6) :\
1423 ((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :\
1424 ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
1425 ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
1426 ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
1427 126)
1429 // XXX It remains to be seen whether it is good to keep the widths of
1430 // XXX the buckets the same or whether it should be scaled by a factor
1431 // XXX of two as well.
1432 #define largebin_index_64(sz) \
1433 (((((unsigned long) (sz)) >> 6) <= 48) ? 48 + (((unsigned long) (sz)) >> 6) :\
1434 ((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :\
1435 ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
1436 ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
1437 ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
1438 126)
1440 #define largebin_index(sz) \
1441 (SIZE_SZ == 8 ? largebin_index_64 (sz) \
1442 : MALLOC_ALIGNMENT == 16 ? largebin_index_32_big (sz) \
1443 : largebin_index_32 (sz))
1445 #define bin_index(sz) \
1446 ((in_smallbin_range (sz)) ? smallbin_index (sz) : largebin_index (sz))
1450 Unsorted chunks
1452 All remainders from chunk splits, as well as all returned chunks,
1453 are first placed in the "unsorted" bin. They are then placed
1454 in regular bins after malloc gives them ONE chance to be used before
1455 binning. So, basically, the unsorted_chunks list acts as a queue,
1456 with chunks being placed on it in free (and malloc_consolidate),
1457 and taken off (to be either used or placed in bins) in malloc.
1459 The NON_MAIN_ARENA flag is never set for unsorted chunks, so it
1460 does not have to be taken into account in size comparisons.
1463 /* The otherwise unindexable 1-bin is used to hold unsorted chunks. */
1464 #define unsorted_chunks(M) (bin_at (M, 1))
1469 The top-most available chunk (i.e., the one bordering the end of
1470 available memory) is treated specially. It is never included in
1471 any bin, is used only if no other chunk is available, and is
1472 released back to the system if it is very large (see
1473 M_TRIM_THRESHOLD). Because top initially
1474 points to its own bin with initial zero size, thus forcing
1475 extension on the first malloc request, we avoid having any special
1476 code in malloc to check whether it even exists yet. But we still
1477 need to do so when getting memory from system, so we make
1478 initial_top treat the bin as a legal but unusable chunk during the
1479 interval between initialization and the first call to
1480 sysmalloc. (This is somewhat delicate, since it relies on
1481 the 2 preceding words to be zero during this interval as well.)
1484 /* Conveniently, the unsorted bin can be used as dummy top on first call */
1485 #define initial_top(M) (unsorted_chunks (M))
1488 Binmap
1490 To help compensate for the large number of bins, a one-level index
1491 structure is used for bin-by-bin searching. `binmap' is a
1492 bitvector recording whether bins are definitely empty so they can
1493 be skipped over during during traversals. The bits are NOT always
1494 cleared as soon as bins are empty, but instead only
1495 when they are noticed to be empty during traversal in malloc.
1498 /* Conservatively use 32 bits per map word, even if on 64bit system */
1499 #define BINMAPSHIFT 5
1500 #define BITSPERMAP (1U << BINMAPSHIFT)
1501 #define BINMAPSIZE (NBINS / BITSPERMAP)
1503 #define idx2block(i) ((i) >> BINMAPSHIFT)
1504 #define idx2bit(i) ((1U << ((i) & ((1U << BINMAPSHIFT) - 1))))
1506 #define mark_bin(m, i) ((m)->binmap[idx2block (i)] |= idx2bit (i))
1507 #define unmark_bin(m, i) ((m)->binmap[idx2block (i)] &= ~(idx2bit (i)))
1508 #define get_binmap(m, i) ((m)->binmap[idx2block (i)] & idx2bit (i))
1511 Fastbins
1513 An array of lists holding recently freed small chunks. Fastbins
1514 are not doubly linked. It is faster to single-link them, and
1515 since chunks are never removed from the middles of these lists,
1516 double linking is not necessary. Also, unlike regular bins, they
1517 are not even processed in FIFO order (they use faster LIFO) since
1518 ordering doesn't much matter in the transient contexts in which
1519 fastbins are normally used.
1521 Chunks in fastbins keep their inuse bit set, so they cannot
1522 be consolidated with other free chunks. malloc_consolidate
1523 releases all chunks in fastbins and consolidates them with
1524 other free chunks.
1527 typedef struct malloc_chunk *mfastbinptr;
1528 #define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])
1530 /* offset 2 to use otherwise unindexable first 2 bins */
1531 #define fastbin_index(sz) \
1532 ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)
1535 /* The maximum fastbin request size we support */
1536 #define MAX_FAST_SIZE (80 * SIZE_SZ / 4)
1538 #define NFASTBINS (fastbin_index (request2size (MAX_FAST_SIZE)) + 1)
1541 FASTBIN_CONSOLIDATION_THRESHOLD is the size of a chunk in free()
1542 that triggers automatic consolidation of possibly-surrounding
1543 fastbin chunks. This is a heuristic, so the exact value should not
1544 matter too much. It is defined at half the default trim threshold as a
1545 compromise heuristic to only attempt consolidation if it is likely
1546 to lead to trimming. However, it is not dynamically tunable, since
1547 consolidation reduces fragmentation surrounding large chunks even
1548 if trimming is not used.
1551 #define FASTBIN_CONSOLIDATION_THRESHOLD (65536UL)
1554 Since the lowest 2 bits in max_fast don't matter in size comparisons,
1555 they are used as flags.
1559 FASTCHUNKS_BIT held in max_fast indicates that there are probably
1560 some fastbin chunks. It is set true on entering a chunk into any
1561 fastbin, and cleared only in malloc_consolidate.
1563 The truth value is inverted so that have_fastchunks will be true
1564 upon startup (since statics are zero-filled), simplifying
1565 initialization checks.
1568 #define FASTCHUNKS_BIT (1U)
1570 #define have_fastchunks(M) (((M)->flags & FASTCHUNKS_BIT) == 0)
1571 #define clear_fastchunks(M) catomic_or (&(M)->flags, FASTCHUNKS_BIT)
1572 #define set_fastchunks(M) catomic_and (&(M)->flags, ~FASTCHUNKS_BIT)
1575 NONCONTIGUOUS_BIT indicates that MORECORE does not return contiguous
1576 regions. Otherwise, contiguity is exploited in merging together,
1577 when possible, results from consecutive MORECORE calls.
1579 The initial value comes from MORECORE_CONTIGUOUS, but is
1580 changed dynamically if mmap is ever used as an sbrk substitute.
1583 #define NONCONTIGUOUS_BIT (2U)
1585 #define contiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) == 0)
1586 #define noncontiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) != 0)
1587 #define set_noncontiguous(M) ((M)->flags |= NONCONTIGUOUS_BIT)
1588 #define set_contiguous(M) ((M)->flags &= ~NONCONTIGUOUS_BIT)
1590 /* ARENA_CORRUPTION_BIT is set if a memory corruption was detected on the
1591 arena. Such an arena is no longer used to allocate chunks. Chunks
1592 allocated in that arena before detecting corruption are not freed. */
1594 #define ARENA_CORRUPTION_BIT (4U)
1596 #define arena_is_corrupt(A) (((A)->flags & ARENA_CORRUPTION_BIT))
1597 #define set_arena_corrupt(A) ((A)->flags |= ARENA_CORRUPTION_BIT)
1600 Set value of max_fast.
1601 Use impossibly small value if 0.
1602 Precondition: there are no existing fastbin chunks.
1603 Setting the value clears fastchunk bit but preserves noncontiguous bit.
1606 #define set_max_fast(s) \
1607 global_max_fast = (((s) == 0) \
1608 ? SMALLBIN_WIDTH : ((s + SIZE_SZ) & ~MALLOC_ALIGN_MASK))
1609 #define get_max_fast() global_max_fast
1613 ----------- Internal state representation and initialization -----------
1616 struct malloc_state
1618 /* Serialize access. */
1619 mutex_t mutex;
1621 /* Flags (formerly in max_fast). */
1622 int flags;
1624 /* Fastbins */
1625 mfastbinptr fastbinsY[NFASTBINS];
1627 /* Base of the topmost chunk -- not otherwise kept in a bin */
1628 mchunkptr top;
1630 /* The remainder from the most recent split of a small request */
1631 mchunkptr last_remainder;
1633 /* Normal bins packed as described above */
1634 mchunkptr bins[NBINS * 2 - 2];
1636 /* Bitmap of bins */
1637 unsigned int binmap[BINMAPSIZE];
1639 /* Linked list */
1640 struct malloc_state *next;
1642 /* Linked list for free arenas. Access to this field is serialized
1643 by free_list_lock in arena.c. */
1644 struct malloc_state *next_free;
1646 /* Number of threads attached to this arena. 0 if the arena is on
1647 the free list. Access to this field is serialized by
1648 free_list_lock in arena.c. */
1649 INTERNAL_SIZE_T attached_threads;
1651 /* Memory allocated from the system in this arena. */
1652 INTERNAL_SIZE_T system_mem;
1653 INTERNAL_SIZE_T max_system_mem;
1656 struct malloc_par
1658 /* Tunable parameters */
1659 unsigned long trim_threshold;
1660 INTERNAL_SIZE_T top_pad;
1661 INTERNAL_SIZE_T mmap_threshold;
1662 INTERNAL_SIZE_T arena_test;
1663 INTERNAL_SIZE_T arena_max;
1665 /* Memory map support */
1666 int n_mmaps;
1667 int n_mmaps_max;
1668 int max_n_mmaps;
1669 /* the mmap_threshold is dynamic, until the user sets
1670 it manually, at which point we need to disable any
1671 dynamic behavior. */
1672 int no_dyn_threshold;
1674 /* Statistics */
1675 INTERNAL_SIZE_T mmapped_mem;
1676 INTERNAL_SIZE_T max_mmapped_mem;
1678 /* First address handed out by MORECORE/sbrk. */
1679 char *sbrk_base;
1682 /* There are several instances of this struct ("arenas") in this
1683 malloc. If you are adapting this malloc in a way that does NOT use
1684 a static or mmapped malloc_state, you MUST explicitly zero-fill it
1685 before using. This malloc relies on the property that malloc_state
1686 is initialized to all zeroes (as is true of C statics). */
1688 static struct malloc_state main_arena =
1690 .mutex = _LIBC_LOCK_INITIALIZER,
1691 .next = &main_arena,
1692 .attached_threads = 1
1695 /* These variables are used for undumping support. Chunked are marked
1696 as using mmap, but we leave them alone if they fall into this
1697 range. NB: The chunk size for these chunks only includes the
1698 initial size field (of SIZE_SZ bytes), there is no trailing size
1699 field (unlike with regular mmapped chunks). */
1700 static mchunkptr dumped_main_arena_start; /* Inclusive. */
1701 static mchunkptr dumped_main_arena_end; /* Exclusive. */
1703 /* True if the pointer falls into the dumped arena. Use this after
1704 chunk_is_mmapped indicates a chunk is mmapped. */
1705 #define DUMPED_MAIN_ARENA_CHUNK(p) \
1706 ((p) >= dumped_main_arena_start && (p) < dumped_main_arena_end)
1708 /* There is only one instance of the malloc parameters. */
1710 static struct malloc_par mp_ =
1712 .top_pad = DEFAULT_TOP_PAD,
1713 .n_mmaps_max = DEFAULT_MMAP_MAX,
1714 .mmap_threshold = DEFAULT_MMAP_THRESHOLD,
1715 .trim_threshold = DEFAULT_TRIM_THRESHOLD,
1716 #define NARENAS_FROM_NCORES(n) ((n) * (sizeof (long) == 4 ? 2 : 8))
1717 .arena_test = NARENAS_FROM_NCORES (1)
1721 /* Non public mallopt parameters. */
1722 #define M_ARENA_TEST -7
1723 #define M_ARENA_MAX -8
1726 /* Maximum size of memory handled in fastbins. */
1727 static INTERNAL_SIZE_T global_max_fast;
1730 Initialize a malloc_state struct.
1732 This is called only from within malloc_consolidate, which needs
1733 be called in the same contexts anyway. It is never called directly
1734 outside of malloc_consolidate because some optimizing compilers try
1735 to inline it at all call points, which turns out not to be an
1736 optimization at all. (Inlining it in malloc_consolidate is fine though.)
1739 static void
1740 malloc_init_state (mstate av)
1742 int i;
1743 mbinptr bin;
1745 /* Establish circular links for normal bins */
1746 for (i = 1; i < NBINS; ++i)
1748 bin = bin_at (av, i);
1749 bin->fd = bin->bk = bin;
1752 #if MORECORE_CONTIGUOUS
1753 if (av != &main_arena)
1754 #endif
1755 set_noncontiguous (av);
1756 if (av == &main_arena)
1757 set_max_fast (DEFAULT_MXFAST);
1758 av->flags |= FASTCHUNKS_BIT;
1760 av->top = initial_top (av);
1764 Other internal utilities operating on mstates
1767 static void *sysmalloc (INTERNAL_SIZE_T, mstate);
1768 static int systrim (size_t, mstate);
1769 static void malloc_consolidate (mstate);
1772 /* -------------- Early definitions for debugging hooks ---------------- */
1774 /* Define and initialize the hook variables. These weak definitions must
1775 appear before any use of the variables in a function (arena.c uses one). */
1776 #ifndef weak_variable
1777 /* In GNU libc we want the hook variables to be weak definitions to
1778 avoid a problem with Emacs. */
1779 # define weak_variable weak_function
1780 #endif
1782 /* Forward declarations. */
1783 static void *malloc_hook_ini (size_t sz,
1784 const void *caller) __THROW;
1785 static void *realloc_hook_ini (void *ptr, size_t sz,
1786 const void *caller) __THROW;
1787 static void *memalign_hook_ini (size_t alignment, size_t sz,
1788 const void *caller) __THROW;
1790 #if HAVE_MALLOC_INIT_HOOK
1791 void weak_variable (*__malloc_initialize_hook) (void) = NULL;
1792 compat_symbol (libc, __malloc_initialize_hook,
1793 __malloc_initialize_hook, GLIBC_2_0);
1794 #endif
1796 void weak_variable (*__free_hook) (void *__ptr,
1797 const void *) = NULL;
1798 void *weak_variable (*__malloc_hook)
1799 (size_t __size, const void *) = malloc_hook_ini;
1800 void *weak_variable (*__realloc_hook)
1801 (void *__ptr, size_t __size, const void *)
1802 = realloc_hook_ini;
1803 void *weak_variable (*__memalign_hook)
1804 (size_t __alignment, size_t __size, const void *)
1805 = memalign_hook_ini;
1806 void weak_variable (*__after_morecore_hook) (void) = NULL;
1809 /* ---------------- Error behavior ------------------------------------ */
1811 #ifndef DEFAULT_CHECK_ACTION
1812 # define DEFAULT_CHECK_ACTION 3
1813 #endif
1815 static int check_action = DEFAULT_CHECK_ACTION;
1818 /* ------------------ Testing support ----------------------------------*/
1820 static int perturb_byte;
1822 static void
1823 alloc_perturb (char *p, size_t n)
1825 if (__glibc_unlikely (perturb_byte))
1826 memset (p, perturb_byte ^ 0xff, n);
1829 static void
1830 free_perturb (char *p, size_t n)
1832 if (__glibc_unlikely (perturb_byte))
1833 memset (p, perturb_byte, n);
1838 #include <stap-probe.h>
1840 /* ------------------- Support for multiple arenas -------------------- */
1841 #include "arena.c"
1844 Debugging support
1846 These routines make a number of assertions about the states
1847 of data structures that should be true at all times. If any
1848 are not true, it's very likely that a user program has somehow
1849 trashed memory. (It's also possible that there is a coding error
1850 in malloc. In which case, please report it!)
1853 #if !MALLOC_DEBUG
1855 # define check_chunk(A, P)
1856 # define check_free_chunk(A, P)
1857 # define check_inuse_chunk(A, P)
1858 # define check_remalloced_chunk(A, P, N)
1859 # define check_malloced_chunk(A, P, N)
1860 # define check_malloc_state(A)
1862 #else
1864 # define check_chunk(A, P) do_check_chunk (A, P)
1865 # define check_free_chunk(A, P) do_check_free_chunk (A, P)
1866 # define check_inuse_chunk(A, P) do_check_inuse_chunk (A, P)
1867 # define check_remalloced_chunk(A, P, N) do_check_remalloced_chunk (A, P, N)
1868 # define check_malloced_chunk(A, P, N) do_check_malloced_chunk (A, P, N)
1869 # define check_malloc_state(A) do_check_malloc_state (A)
1872 Properties of all chunks
1875 static void
1876 do_check_chunk (mstate av, mchunkptr p)
1878 unsigned long sz = chunksize (p);
1879 /* min and max possible addresses assuming contiguous allocation */
1880 char *max_address = (char *) (av->top) + chunksize (av->top);
1881 char *min_address = max_address - av->system_mem;
1883 if (!chunk_is_mmapped (p))
1885 /* Has legal address ... */
1886 if (p != av->top)
1888 if (contiguous (av))
1890 assert (((char *) p) >= min_address);
1891 assert (((char *) p + sz) <= ((char *) (av->top)));
1894 else
1896 /* top size is always at least MINSIZE */
1897 assert ((unsigned long) (sz) >= MINSIZE);
1898 /* top predecessor always marked inuse */
1899 assert (prev_inuse (p));
1902 else if (!DUMPED_MAIN_ARENA_CHUNK (p))
1904 /* address is outside main heap */
1905 if (contiguous (av) && av->top != initial_top (av))
1907 assert (((char *) p) < min_address || ((char *) p) >= max_address);
1909 /* chunk is page-aligned */
1910 assert (((p->prev_size + sz) & (GLRO (dl_pagesize) - 1)) == 0);
1911 /* mem is aligned */
1912 assert (aligned_OK (chunk2mem (p)));
1917 Properties of free chunks
1920 static void
1921 do_check_free_chunk (mstate av, mchunkptr p)
1923 INTERNAL_SIZE_T sz = p->size & ~(PREV_INUSE | NON_MAIN_ARENA);
1924 mchunkptr next = chunk_at_offset (p, sz);
1926 do_check_chunk (av, p);
1928 /* Chunk must claim to be free ... */
1929 assert (!inuse (p));
1930 assert (!chunk_is_mmapped (p));
1932 /* Unless a special marker, must have OK fields */
1933 if ((unsigned long) (sz) >= MINSIZE)
1935 assert ((sz & MALLOC_ALIGN_MASK) == 0);
1936 assert (aligned_OK (chunk2mem (p)));
1937 /* ... matching footer field */
1938 assert (next->prev_size == sz);
1939 /* ... and is fully consolidated */
1940 assert (prev_inuse (p));
1941 assert (next == av->top || inuse (next));
1943 /* ... and has minimally sane links */
1944 assert (p->fd->bk == p);
1945 assert (p->bk->fd == p);
1947 else /* markers are always of size SIZE_SZ */
1948 assert (sz == SIZE_SZ);
1952 Properties of inuse chunks
1955 static void
1956 do_check_inuse_chunk (mstate av, mchunkptr p)
1958 mchunkptr next;
1960 do_check_chunk (av, p);
1962 if (chunk_is_mmapped (p))
1963 return; /* mmapped chunks have no next/prev */
1965 /* Check whether it claims to be in use ... */
1966 assert (inuse (p));
1968 next = next_chunk (p);
1970 /* ... and is surrounded by OK chunks.
1971 Since more things can be checked with free chunks than inuse ones,
1972 if an inuse chunk borders them and debug is on, it's worth doing them.
1974 if (!prev_inuse (p))
1976 /* Note that we cannot even look at prev unless it is not inuse */
1977 mchunkptr prv = prev_chunk (p);
1978 assert (next_chunk (prv) == p);
1979 do_check_free_chunk (av, prv);
1982 if (next == av->top)
1984 assert (prev_inuse (next));
1985 assert (chunksize (next) >= MINSIZE);
1987 else if (!inuse (next))
1988 do_check_free_chunk (av, next);
1992 Properties of chunks recycled from fastbins
1995 static void
1996 do_check_remalloced_chunk (mstate av, mchunkptr p, INTERNAL_SIZE_T s)
1998 INTERNAL_SIZE_T sz = p->size & ~(PREV_INUSE | NON_MAIN_ARENA);
2000 if (!chunk_is_mmapped (p))
2002 assert (av == arena_for_chunk (p));
2003 if (chunk_non_main_arena (p))
2004 assert (av != &main_arena);
2005 else
2006 assert (av == &main_arena);
2009 do_check_inuse_chunk (av, p);
2011 /* Legal size ... */
2012 assert ((sz & MALLOC_ALIGN_MASK) == 0);
2013 assert ((unsigned long) (sz) >= MINSIZE);
2014 /* ... and alignment */
2015 assert (aligned_OK (chunk2mem (p)));
2016 /* chunk is less than MINSIZE more than request */
2017 assert ((long) (sz) - (long) (s) >= 0);
2018 assert ((long) (sz) - (long) (s + MINSIZE) < 0);
2022 Properties of nonrecycled chunks at the point they are malloced
2025 static void
2026 do_check_malloced_chunk (mstate av, mchunkptr p, INTERNAL_SIZE_T s)
2028 /* same as recycled case ... */
2029 do_check_remalloced_chunk (av, p, s);
2032 ... plus, must obey implementation invariant that prev_inuse is
2033 always true of any allocated chunk; i.e., that each allocated
2034 chunk borders either a previously allocated and still in-use
2035 chunk, or the base of its memory arena. This is ensured
2036 by making all allocations from the `lowest' part of any found
2037 chunk. This does not necessarily hold however for chunks
2038 recycled via fastbins.
2041 assert (prev_inuse (p));
2046 Properties of malloc_state.
2048 This may be useful for debugging malloc, as well as detecting user
2049 programmer errors that somehow write into malloc_state.
2051 If you are extending or experimenting with this malloc, you can
2052 probably figure out how to hack this routine to print out or
2053 display chunk addresses, sizes, bins, and other instrumentation.
2056 static void
2057 do_check_malloc_state (mstate av)
2059 int i;
2060 mchunkptr p;
2061 mchunkptr q;
2062 mbinptr b;
2063 unsigned int idx;
2064 INTERNAL_SIZE_T size;
2065 unsigned long total = 0;
2066 int max_fast_bin;
2068 /* internal size_t must be no wider than pointer type */
2069 assert (sizeof (INTERNAL_SIZE_T) <= sizeof (char *));
2071 /* alignment is a power of 2 */
2072 assert ((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT - 1)) == 0);
2074 /* cannot run remaining checks until fully initialized */
2075 if (av->top == 0 || av->top == initial_top (av))
2076 return;
2078 /* pagesize is a power of 2 */
2079 assert (powerof2(GLRO (dl_pagesize)));
2081 /* A contiguous main_arena is consistent with sbrk_base. */
2082 if (av == &main_arena && contiguous (av))
2083 assert ((char *) mp_.sbrk_base + av->system_mem ==
2084 (char *) av->top + chunksize (av->top));
2086 /* properties of fastbins */
2088 /* max_fast is in allowed range */
2089 assert ((get_max_fast () & ~1) <= request2size (MAX_FAST_SIZE));
2091 max_fast_bin = fastbin_index (get_max_fast ());
2093 for (i = 0; i < NFASTBINS; ++i)
2095 p = fastbin (av, i);
2097 /* The following test can only be performed for the main arena.
2098 While mallopt calls malloc_consolidate to get rid of all fast
2099 bins (especially those larger than the new maximum) this does
2100 only happen for the main arena. Trying to do this for any
2101 other arena would mean those arenas have to be locked and
2102 malloc_consolidate be called for them. This is excessive. And
2103 even if this is acceptable to somebody it still cannot solve
2104 the problem completely since if the arena is locked a
2105 concurrent malloc call might create a new arena which then
2106 could use the newly invalid fast bins. */
2108 /* all bins past max_fast are empty */
2109 if (av == &main_arena && i > max_fast_bin)
2110 assert (p == 0);
2112 while (p != 0)
2114 /* each chunk claims to be inuse */
2115 do_check_inuse_chunk (av, p);
2116 total += chunksize (p);
2117 /* chunk belongs in this bin */
2118 assert (fastbin_index (chunksize (p)) == i);
2119 p = p->fd;
2123 if (total != 0)
2124 assert (have_fastchunks (av));
2125 else if (!have_fastchunks (av))
2126 assert (total == 0);
2128 /* check normal bins */
2129 for (i = 1; i < NBINS; ++i)
2131 b = bin_at (av, i);
2133 /* binmap is accurate (except for bin 1 == unsorted_chunks) */
2134 if (i >= 2)
2136 unsigned int binbit = get_binmap (av, i);
2137 int empty = last (b) == b;
2138 if (!binbit)
2139 assert (empty);
2140 else if (!empty)
2141 assert (binbit);
2144 for (p = last (b); p != b; p = p->bk)
2146 /* each chunk claims to be free */
2147 do_check_free_chunk (av, p);
2148 size = chunksize (p);
2149 total += size;
2150 if (i >= 2)
2152 /* chunk belongs in bin */
2153 idx = bin_index (size);
2154 assert (idx == i);
2155 /* lists are sorted */
2156 assert (p->bk == b ||
2157 (unsigned long) chunksize (p->bk) >= (unsigned long) chunksize (p));
2159 if (!in_smallbin_range (size))
2161 if (p->fd_nextsize != NULL)
2163 if (p->fd_nextsize == p)
2164 assert (p->bk_nextsize == p);
2165 else
2167 if (p->fd_nextsize == first (b))
2168 assert (chunksize (p) < chunksize (p->fd_nextsize));
2169 else
2170 assert (chunksize (p) > chunksize (p->fd_nextsize));
2172 if (p == first (b))
2173 assert (chunksize (p) > chunksize (p->bk_nextsize));
2174 else
2175 assert (chunksize (p) < chunksize (p->bk_nextsize));
2178 else
2179 assert (p->bk_nextsize == NULL);
2182 else if (!in_smallbin_range (size))
2183 assert (p->fd_nextsize == NULL && p->bk_nextsize == NULL);
2184 /* chunk is followed by a legal chain of inuse chunks */
2185 for (q = next_chunk (p);
2186 (q != av->top && inuse (q) &&
2187 (unsigned long) (chunksize (q)) >= MINSIZE);
2188 q = next_chunk (q))
2189 do_check_inuse_chunk (av, q);
2193 /* top chunk is OK */
2194 check_chunk (av, av->top);
2196 #endif
2199 /* ----------------- Support for debugging hooks -------------------- */
2200 #include "hooks.c"
2203 /* ----------- Routines dealing with system allocation -------------- */
2206 sysmalloc handles malloc cases requiring more memory from the system.
2207 On entry, it is assumed that av->top does not have enough
2208 space to service request for nb bytes, thus requiring that av->top
2209 be extended or replaced.
2212 static void *
2213 sysmalloc (INTERNAL_SIZE_T nb, mstate av)
2215 mchunkptr old_top; /* incoming value of av->top */
2216 INTERNAL_SIZE_T old_size; /* its size */
2217 char *old_end; /* its end address */
2219 long size; /* arg to first MORECORE or mmap call */
2220 char *brk; /* return value from MORECORE */
2222 long correction; /* arg to 2nd MORECORE call */
2223 char *snd_brk; /* 2nd return val */
2225 INTERNAL_SIZE_T front_misalign; /* unusable bytes at front of new space */
2226 INTERNAL_SIZE_T end_misalign; /* partial page left at end of new space */
2227 char *aligned_brk; /* aligned offset into brk */
2229 mchunkptr p; /* the allocated/returned chunk */
2230 mchunkptr remainder; /* remainder from allocation */
2231 unsigned long remainder_size; /* its size */
2234 size_t pagesize = GLRO (dl_pagesize);
2235 bool tried_mmap = false;
2239 If have mmap, and the request size meets the mmap threshold, and
2240 the system supports mmap, and there are few enough currently
2241 allocated mmapped regions, try to directly map this request
2242 rather than expanding top.
2245 if (av == NULL
2246 || ((unsigned long) (nb) >= (unsigned long) (mp_.mmap_threshold)
2247 && (mp_.n_mmaps < mp_.n_mmaps_max)))
2249 char *mm; /* return value from mmap call*/
2251 try_mmap:
2253 Round up size to nearest page. For mmapped chunks, the overhead
2254 is one SIZE_SZ unit larger than for normal chunks, because there
2255 is no following chunk whose prev_size field could be used.
2257 See the front_misalign handling below, for glibc there is no
2258 need for further alignments unless we have have high alignment.
2260 if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
2261 size = ALIGN_UP (nb + SIZE_SZ, pagesize);
2262 else
2263 size = ALIGN_UP (nb + SIZE_SZ + MALLOC_ALIGN_MASK, pagesize);
2264 tried_mmap = true;
2266 /* Don't try if size wraps around 0 */
2267 if ((unsigned long) (size) > (unsigned long) (nb))
2269 mm = (char *) (MMAP (0, size, PROT_READ | PROT_WRITE, 0));
2271 if (mm != MAP_FAILED)
2274 The offset to the start of the mmapped region is stored
2275 in the prev_size field of the chunk. This allows us to adjust
2276 returned start address to meet alignment requirements here
2277 and in memalign(), and still be able to compute proper
2278 address argument for later munmap in free() and realloc().
2281 if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
2283 /* For glibc, chunk2mem increases the address by 2*SIZE_SZ and
2284 MALLOC_ALIGN_MASK is 2*SIZE_SZ-1. Each mmap'ed area is page
2285 aligned and therefore definitely MALLOC_ALIGN_MASK-aligned. */
2286 assert (((INTERNAL_SIZE_T) chunk2mem (mm) & MALLOC_ALIGN_MASK) == 0);
2287 front_misalign = 0;
2289 else
2290 front_misalign = (INTERNAL_SIZE_T) chunk2mem (mm) & MALLOC_ALIGN_MASK;
2291 if (front_misalign > 0)
2293 correction = MALLOC_ALIGNMENT - front_misalign;
2294 p = (mchunkptr) (mm + correction);
2295 p->prev_size = correction;
2296 set_head (p, (size - correction) | IS_MMAPPED);
2298 else
2300 p = (mchunkptr) mm;
2301 set_head (p, size | IS_MMAPPED);
2304 /* update statistics */
2306 int new = atomic_exchange_and_add (&mp_.n_mmaps, 1) + 1;
2307 atomic_max (&mp_.max_n_mmaps, new);
2309 unsigned long sum;
2310 sum = atomic_exchange_and_add (&mp_.mmapped_mem, size) + size;
2311 atomic_max (&mp_.max_mmapped_mem, sum);
2313 check_chunk (av, p);
2315 return chunk2mem (p);
2320 /* There are no usable arenas and mmap also failed. */
2321 if (av == NULL)
2322 return 0;
2324 /* Record incoming configuration of top */
2326 old_top = av->top;
2327 old_size = chunksize (old_top);
2328 old_end = (char *) (chunk_at_offset (old_top, old_size));
2330 brk = snd_brk = (char *) (MORECORE_FAILURE);
2333 If not the first time through, we require old_size to be
2334 at least MINSIZE and to have prev_inuse set.
2337 assert ((old_top == initial_top (av) && old_size == 0) ||
2338 ((unsigned long) (old_size) >= MINSIZE &&
2339 prev_inuse (old_top) &&
2340 ((unsigned long) old_end & (pagesize - 1)) == 0));
2342 /* Precondition: not enough current space to satisfy nb request */
2343 assert ((unsigned long) (old_size) < (unsigned long) (nb + MINSIZE));
2346 if (av != &main_arena)
2348 heap_info *old_heap, *heap;
2349 size_t old_heap_size;
2351 /* First try to extend the current heap. */
2352 old_heap = heap_for_ptr (old_top);
2353 old_heap_size = old_heap->size;
2354 if ((long) (MINSIZE + nb - old_size) > 0
2355 && grow_heap (old_heap, MINSIZE + nb - old_size) == 0)
2357 av->system_mem += old_heap->size - old_heap_size;
2358 set_head (old_top, (((char *) old_heap + old_heap->size) - (char *) old_top)
2359 | PREV_INUSE);
2361 else if ((heap = new_heap (nb + (MINSIZE + sizeof (*heap)), mp_.top_pad)))
2363 /* Use a newly allocated heap. */
2364 heap->ar_ptr = av;
2365 heap->prev = old_heap;
2366 av->system_mem += heap->size;
2367 /* Set up the new top. */
2368 top (av) = chunk_at_offset (heap, sizeof (*heap));
2369 set_head (top (av), (heap->size - sizeof (*heap)) | PREV_INUSE);
2371 /* Setup fencepost and free the old top chunk with a multiple of
2372 MALLOC_ALIGNMENT in size. */
2373 /* The fencepost takes at least MINSIZE bytes, because it might
2374 become the top chunk again later. Note that a footer is set
2375 up, too, although the chunk is marked in use. */
2376 old_size = (old_size - MINSIZE) & ~MALLOC_ALIGN_MASK;
2377 set_head (chunk_at_offset (old_top, old_size + 2 * SIZE_SZ), 0 | PREV_INUSE);
2378 if (old_size >= MINSIZE)
2380 set_head (chunk_at_offset (old_top, old_size), (2 * SIZE_SZ) | PREV_INUSE);
2381 set_foot (chunk_at_offset (old_top, old_size), (2 * SIZE_SZ));
2382 set_head (old_top, old_size | PREV_INUSE | NON_MAIN_ARENA);
2383 _int_free (av, old_top, 1);
2385 else
2387 set_head (old_top, (old_size + 2 * SIZE_SZ) | PREV_INUSE);
2388 set_foot (old_top, (old_size + 2 * SIZE_SZ));
2391 else if (!tried_mmap)
2392 /* We can at least try to use to mmap memory. */
2393 goto try_mmap;
2395 else /* av == main_arena */
2398 { /* Request enough space for nb + pad + overhead */
2399 size = nb + mp_.top_pad + MINSIZE;
2402 If contiguous, we can subtract out existing space that we hope to
2403 combine with new space. We add it back later only if
2404 we don't actually get contiguous space.
2407 if (contiguous (av))
2408 size -= old_size;
2411 Round to a multiple of page size.
2412 If MORECORE is not contiguous, this ensures that we only call it
2413 with whole-page arguments. And if MORECORE is contiguous and
2414 this is not first time through, this preserves page-alignment of
2415 previous calls. Otherwise, we correct to page-align below.
2418 size = ALIGN_UP (size, pagesize);
2421 Don't try to call MORECORE if argument is so big as to appear
2422 negative. Note that since mmap takes size_t arg, it may succeed
2423 below even if we cannot call MORECORE.
2426 if (size > 0)
2428 brk = (char *) (MORECORE (size));
2429 LIBC_PROBE (memory_sbrk_more, 2, brk, size);
2432 if (brk != (char *) (MORECORE_FAILURE))
2434 /* Call the `morecore' hook if necessary. */
2435 void (*hook) (void) = atomic_forced_read (__after_morecore_hook);
2436 if (__builtin_expect (hook != NULL, 0))
2437 (*hook)();
2439 else
2442 If have mmap, try using it as a backup when MORECORE fails or
2443 cannot be used. This is worth doing on systems that have "holes" in
2444 address space, so sbrk cannot extend to give contiguous space, but
2445 space is available elsewhere. Note that we ignore mmap max count
2446 and threshold limits, since the space will not be used as a
2447 segregated mmap region.
2450 /* Cannot merge with old top, so add its size back in */
2451 if (contiguous (av))
2452 size = ALIGN_UP (size + old_size, pagesize);
2454 /* If we are relying on mmap as backup, then use larger units */
2455 if ((unsigned long) (size) < (unsigned long) (MMAP_AS_MORECORE_SIZE))
2456 size = MMAP_AS_MORECORE_SIZE;
2458 /* Don't try if size wraps around 0 */
2459 if ((unsigned long) (size) > (unsigned long) (nb))
2461 char *mbrk = (char *) (MMAP (0, size, PROT_READ | PROT_WRITE, 0));
2463 if (mbrk != MAP_FAILED)
2465 /* We do not need, and cannot use, another sbrk call to find end */
2466 brk = mbrk;
2467 snd_brk = brk + size;
2470 Record that we no longer have a contiguous sbrk region.
2471 After the first time mmap is used as backup, we do not
2472 ever rely on contiguous space since this could incorrectly
2473 bridge regions.
2475 set_noncontiguous (av);
2480 if (brk != (char *) (MORECORE_FAILURE))
2482 if (mp_.sbrk_base == 0)
2483 mp_.sbrk_base = brk;
2484 av->system_mem += size;
2487 If MORECORE extends previous space, we can likewise extend top size.
2490 if (brk == old_end && snd_brk == (char *) (MORECORE_FAILURE))
2491 set_head (old_top, (size + old_size) | PREV_INUSE);
2493 else if (contiguous (av) && old_size && brk < old_end)
2495 /* Oops! Someone else killed our space.. Can't touch anything. */
2496 malloc_printerr (3, "break adjusted to free malloc space", brk,
2497 av);
2501 Otherwise, make adjustments:
2503 * If the first time through or noncontiguous, we need to call sbrk
2504 just to find out where the end of memory lies.
2506 * We need to ensure that all returned chunks from malloc will meet
2507 MALLOC_ALIGNMENT
2509 * If there was an intervening foreign sbrk, we need to adjust sbrk
2510 request size to account for fact that we will not be able to
2511 combine new space with existing space in old_top.
2513 * Almost all systems internally allocate whole pages at a time, in
2514 which case we might as well use the whole last page of request.
2515 So we allocate enough more memory to hit a page boundary now,
2516 which in turn causes future contiguous calls to page-align.
2519 else
2521 front_misalign = 0;
2522 end_misalign = 0;
2523 correction = 0;
2524 aligned_brk = brk;
2526 /* handle contiguous cases */
2527 if (contiguous (av))
2529 /* Count foreign sbrk as system_mem. */
2530 if (old_size)
2531 av->system_mem += brk - old_end;
2533 /* Guarantee alignment of first new chunk made from this space */
2535 front_misalign = (INTERNAL_SIZE_T) chunk2mem (brk) & MALLOC_ALIGN_MASK;
2536 if (front_misalign > 0)
2539 Skip over some bytes to arrive at an aligned position.
2540 We don't need to specially mark these wasted front bytes.
2541 They will never be accessed anyway because
2542 prev_inuse of av->top (and any chunk created from its start)
2543 is always true after initialization.
2546 correction = MALLOC_ALIGNMENT - front_misalign;
2547 aligned_brk += correction;
2551 If this isn't adjacent to existing space, then we will not
2552 be able to merge with old_top space, so must add to 2nd request.
2555 correction += old_size;
2557 /* Extend the end address to hit a page boundary */
2558 end_misalign = (INTERNAL_SIZE_T) (brk + size + correction);
2559 correction += (ALIGN_UP (end_misalign, pagesize)) - end_misalign;
2561 assert (correction >= 0);
2562 snd_brk = (char *) (MORECORE (correction));
2565 If can't allocate correction, try to at least find out current
2566 brk. It might be enough to proceed without failing.
2568 Note that if second sbrk did NOT fail, we assume that space
2569 is contiguous with first sbrk. This is a safe assumption unless
2570 program is multithreaded but doesn't use locks and a foreign sbrk
2571 occurred between our first and second calls.
2574 if (snd_brk == (char *) (MORECORE_FAILURE))
2576 correction = 0;
2577 snd_brk = (char *) (MORECORE (0));
2579 else
2581 /* Call the `morecore' hook if necessary. */
2582 void (*hook) (void) = atomic_forced_read (__after_morecore_hook);
2583 if (__builtin_expect (hook != NULL, 0))
2584 (*hook)();
2588 /* handle non-contiguous cases */
2589 else
2591 if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
2592 /* MORECORE/mmap must correctly align */
2593 assert (((unsigned long) chunk2mem (brk) & MALLOC_ALIGN_MASK) == 0);
2594 else
2596 front_misalign = (INTERNAL_SIZE_T) chunk2mem (brk) & MALLOC_ALIGN_MASK;
2597 if (front_misalign > 0)
2600 Skip over some bytes to arrive at an aligned position.
2601 We don't need to specially mark these wasted front bytes.
2602 They will never be accessed anyway because
2603 prev_inuse of av->top (and any chunk created from its start)
2604 is always true after initialization.
2607 aligned_brk += MALLOC_ALIGNMENT - front_misalign;
2611 /* Find out current end of memory */
2612 if (snd_brk == (char *) (MORECORE_FAILURE))
2614 snd_brk = (char *) (MORECORE (0));
2618 /* Adjust top based on results of second sbrk */
2619 if (snd_brk != (char *) (MORECORE_FAILURE))
2621 av->top = (mchunkptr) aligned_brk;
2622 set_head (av->top, (snd_brk - aligned_brk + correction) | PREV_INUSE);
2623 av->system_mem += correction;
2626 If not the first time through, we either have a
2627 gap due to foreign sbrk or a non-contiguous region. Insert a
2628 double fencepost at old_top to prevent consolidation with space
2629 we don't own. These fenceposts are artificial chunks that are
2630 marked as inuse and are in any case too small to use. We need
2631 two to make sizes and alignments work out.
2634 if (old_size != 0)
2637 Shrink old_top to insert fenceposts, keeping size a
2638 multiple of MALLOC_ALIGNMENT. We know there is at least
2639 enough space in old_top to do this.
2641 old_size = (old_size - 4 * SIZE_SZ) & ~MALLOC_ALIGN_MASK;
2642 set_head (old_top, old_size | PREV_INUSE);
2645 Note that the following assignments completely overwrite
2646 old_top when old_size was previously MINSIZE. This is
2647 intentional. We need the fencepost, even if old_top otherwise gets
2648 lost.
2650 chunk_at_offset (old_top, old_size)->size =
2651 (2 * SIZE_SZ) | PREV_INUSE;
2653 chunk_at_offset (old_top, old_size + 2 * SIZE_SZ)->size =
2654 (2 * SIZE_SZ) | PREV_INUSE;
2656 /* If possible, release the rest. */
2657 if (old_size >= MINSIZE)
2659 _int_free (av, old_top, 1);
2665 } /* if (av != &main_arena) */
2667 if ((unsigned long) av->system_mem > (unsigned long) (av->max_system_mem))
2668 av->max_system_mem = av->system_mem;
2669 check_malloc_state (av);
2671 /* finally, do the allocation */
2672 p = av->top;
2673 size = chunksize (p);
2675 /* check that one of the above allocation paths succeeded */
2676 if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
2678 remainder_size = size - nb;
2679 remainder = chunk_at_offset (p, nb);
2680 av->top = remainder;
2681 set_head (p, nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));
2682 set_head (remainder, remainder_size | PREV_INUSE);
2683 check_malloced_chunk (av, p, nb);
2684 return chunk2mem (p);
2687 /* catch all failure paths */
2688 __set_errno (ENOMEM);
2689 return 0;
2694 systrim is an inverse of sorts to sysmalloc. It gives memory back
2695 to the system (via negative arguments to sbrk) if there is unused
2696 memory at the `high' end of the malloc pool. It is called
2697 automatically by free() when top space exceeds the trim
2698 threshold. It is also called by the public malloc_trim routine. It
2699 returns 1 if it actually released any memory, else 0.
2702 static int
2703 systrim (size_t pad, mstate av)
2705 long top_size; /* Amount of top-most memory */
2706 long extra; /* Amount to release */
2707 long released; /* Amount actually released */
2708 char *current_brk; /* address returned by pre-check sbrk call */
2709 char *new_brk; /* address returned by post-check sbrk call */
2710 size_t pagesize;
2711 long top_area;
2713 pagesize = GLRO (dl_pagesize);
2714 top_size = chunksize (av->top);
2716 top_area = top_size - MINSIZE - 1;
2717 if (top_area <= pad)
2718 return 0;
2720 /* Release in pagesize units and round down to the nearest page. */
2721 extra = ALIGN_DOWN(top_area - pad, pagesize);
2723 if (extra == 0)
2724 return 0;
2727 Only proceed if end of memory is where we last set it.
2728 This avoids problems if there were foreign sbrk calls.
2730 current_brk = (char *) (MORECORE (0));
2731 if (current_brk == (char *) (av->top) + top_size)
2734 Attempt to release memory. We ignore MORECORE return value,
2735 and instead call again to find out where new end of memory is.
2736 This avoids problems if first call releases less than we asked,
2737 of if failure somehow altered brk value. (We could still
2738 encounter problems if it altered brk in some very bad way,
2739 but the only thing we can do is adjust anyway, which will cause
2740 some downstream failure.)
2743 MORECORE (-extra);
2744 /* Call the `morecore' hook if necessary. */
2745 void (*hook) (void) = atomic_forced_read (__after_morecore_hook);
2746 if (__builtin_expect (hook != NULL, 0))
2747 (*hook)();
2748 new_brk = (char *) (MORECORE (0));
2750 LIBC_PROBE (memory_sbrk_less, 2, new_brk, extra);
2752 if (new_brk != (char *) MORECORE_FAILURE)
2754 released = (long) (current_brk - new_brk);
2756 if (released != 0)
2758 /* Success. Adjust top. */
2759 av->system_mem -= released;
2760 set_head (av->top, (top_size - released) | PREV_INUSE);
2761 check_malloc_state (av);
2762 return 1;
2766 return 0;
2769 static void
2770 internal_function
2771 munmap_chunk (mchunkptr p)
2773 INTERNAL_SIZE_T size = chunksize (p);
2775 assert (chunk_is_mmapped (p));
2777 /* Do nothing if the chunk is a faked mmapped chunk in the dumped
2778 main arena. We never free this memory. */
2779 if (DUMPED_MAIN_ARENA_CHUNK (p))
2780 return;
2782 uintptr_t block = (uintptr_t) p - p->prev_size;
2783 size_t total_size = p->prev_size + size;
2784 /* Unfortunately we have to do the compilers job by hand here. Normally
2785 we would test BLOCK and TOTAL-SIZE separately for compliance with the
2786 page size. But gcc does not recognize the optimization possibility
2787 (in the moment at least) so we combine the two values into one before
2788 the bit test. */
2789 if (__builtin_expect (((block | total_size) & (GLRO (dl_pagesize) - 1)) != 0, 0))
2791 malloc_printerr (check_action, "munmap_chunk(): invalid pointer",
2792 chunk2mem (p), NULL);
2793 return;
2796 atomic_decrement (&mp_.n_mmaps);
2797 atomic_add (&mp_.mmapped_mem, -total_size);
2799 /* If munmap failed the process virtual memory address space is in a
2800 bad shape. Just leave the block hanging around, the process will
2801 terminate shortly anyway since not much can be done. */
2802 __munmap ((char *) block, total_size);
2805 #if HAVE_MREMAP
2807 static mchunkptr
2808 internal_function
2809 mremap_chunk (mchunkptr p, size_t new_size)
2811 size_t pagesize = GLRO (dl_pagesize);
2812 INTERNAL_SIZE_T offset = p->prev_size;
2813 INTERNAL_SIZE_T size = chunksize (p);
2814 char *cp;
2816 assert (chunk_is_mmapped (p));
2817 assert (((size + offset) & (GLRO (dl_pagesize) - 1)) == 0);
2819 /* Note the extra SIZE_SZ overhead as in mmap_chunk(). */
2820 new_size = ALIGN_UP (new_size + offset + SIZE_SZ, pagesize);
2822 /* No need to remap if the number of pages does not change. */
2823 if (size + offset == new_size)
2824 return p;
2826 cp = (char *) __mremap ((char *) p - offset, size + offset, new_size,
2827 MREMAP_MAYMOVE);
2829 if (cp == MAP_FAILED)
2830 return 0;
2832 p = (mchunkptr) (cp + offset);
2834 assert (aligned_OK (chunk2mem (p)));
2836 assert ((p->prev_size == offset));
2837 set_head (p, (new_size - offset) | IS_MMAPPED);
2839 INTERNAL_SIZE_T new;
2840 new = atomic_exchange_and_add (&mp_.mmapped_mem, new_size - size - offset)
2841 + new_size - size - offset;
2842 atomic_max (&mp_.max_mmapped_mem, new);
2843 return p;
2845 #endif /* HAVE_MREMAP */
2847 /*------------------------ Public wrappers. --------------------------------*/
2849 void *
2850 __libc_malloc (size_t bytes)
2852 mstate ar_ptr;
2853 void *victim;
2855 void *(*hook) (size_t, const void *)
2856 = atomic_forced_read (__malloc_hook);
2857 if (__builtin_expect (hook != NULL, 0))
2858 return (*hook)(bytes, RETURN_ADDRESS (0));
2860 arena_get (ar_ptr, bytes);
2862 victim = _int_malloc (ar_ptr, bytes);
2863 /* Retry with another arena only if we were able to find a usable arena
2864 before. */
2865 if (!victim && ar_ptr != NULL)
2867 LIBC_PROBE (memory_malloc_retry, 1, bytes);
2868 ar_ptr = arena_get_retry (ar_ptr, bytes);
2869 victim = _int_malloc (ar_ptr, bytes);
2872 if (ar_ptr != NULL)
2873 (void) mutex_unlock (&ar_ptr->mutex);
2875 assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
2876 ar_ptr == arena_for_chunk (mem2chunk (victim)));
2877 return victim;
2879 libc_hidden_def (__libc_malloc)
2881 void
2882 __libc_free (void *mem)
2884 mstate ar_ptr;
2885 mchunkptr p; /* chunk corresponding to mem */
2887 void (*hook) (void *, const void *)
2888 = atomic_forced_read (__free_hook);
2889 if (__builtin_expect (hook != NULL, 0))
2891 (*hook)(mem, RETURN_ADDRESS (0));
2892 return;
2895 if (mem == 0) /* free(0) has no effect */
2896 return;
2898 p = mem2chunk (mem);
2900 if (chunk_is_mmapped (p)) /* release mmapped memory. */
2902 /* See if the dynamic brk/mmap threshold needs adjusting.
2903 Dumped fake mmapped chunks do not affect the threshold. */
2904 if (!mp_.no_dyn_threshold
2905 && p->size > mp_.mmap_threshold
2906 && p->size <= DEFAULT_MMAP_THRESHOLD_MAX
2907 && !DUMPED_MAIN_ARENA_CHUNK (p))
2909 mp_.mmap_threshold = chunksize (p);
2910 mp_.trim_threshold = 2 * mp_.mmap_threshold;
2911 LIBC_PROBE (memory_mallopt_free_dyn_thresholds, 2,
2912 mp_.mmap_threshold, mp_.trim_threshold);
2914 munmap_chunk (p);
2915 return;
2918 ar_ptr = arena_for_chunk (p);
2919 _int_free (ar_ptr, p, 0);
2921 libc_hidden_def (__libc_free)
2923 void *
2924 __libc_realloc (void *oldmem, size_t bytes)
2926 mstate ar_ptr;
2927 INTERNAL_SIZE_T nb; /* padded request size */
2929 void *newp; /* chunk to return */
2931 void *(*hook) (void *, size_t, const void *) =
2932 atomic_forced_read (__realloc_hook);
2933 if (__builtin_expect (hook != NULL, 0))
2934 return (*hook)(oldmem, bytes, RETURN_ADDRESS (0));
2936 #if REALLOC_ZERO_BYTES_FREES
2937 if (bytes == 0 && oldmem != NULL)
2939 __libc_free (oldmem); return 0;
2941 #endif
2943 /* realloc of null is supposed to be same as malloc */
2944 if (oldmem == 0)
2945 return __libc_malloc (bytes);
2947 /* chunk corresponding to oldmem */
2948 const mchunkptr oldp = mem2chunk (oldmem);
2949 /* its size */
2950 const INTERNAL_SIZE_T oldsize = chunksize (oldp);
2952 if (chunk_is_mmapped (oldp))
2953 ar_ptr = NULL;
2954 else
2955 ar_ptr = arena_for_chunk (oldp);
2957 /* Little security check which won't hurt performance: the allocator
2958 never wrapps around at the end of the address space. Therefore
2959 we can exclude some size values which might appear here by
2960 accident or by "design" from some intruder. We need to bypass
2961 this check for dumped fake mmap chunks from the old main arena
2962 because the new malloc may provide additional alignment. */
2963 if ((__builtin_expect ((uintptr_t) oldp > (uintptr_t) -oldsize, 0)
2964 || __builtin_expect (misaligned_chunk (oldp), 0))
2965 && !DUMPED_MAIN_ARENA_CHUNK (oldp))
2967 malloc_printerr (check_action, "realloc(): invalid pointer", oldmem,
2968 ar_ptr);
2969 return NULL;
2972 checked_request2size (bytes, nb);
2974 if (chunk_is_mmapped (oldp))
2976 /* If this is a faked mmapped chunk from the dumped main arena,
2977 always make a copy (and do not free the old chunk). */
2978 if (DUMPED_MAIN_ARENA_CHUNK (oldp))
2980 /* Must alloc, copy, free. */
2981 void *newmem = __libc_malloc (bytes);
2982 if (newmem == 0)
2983 return NULL;
2984 /* Copy as many bytes as are available from the old chunk
2985 and fit into the new size. NB: The overhead for faked
2986 mmapped chunks is only SIZE_SZ, not 2 * SIZE_SZ as for
2987 regular mmapped chunks. */
2988 if (bytes > oldsize - SIZE_SZ)
2989 bytes = oldsize - SIZE_SZ;
2990 memcpy (newmem, oldmem, bytes);
2991 return newmem;
2994 void *newmem;
2996 #if HAVE_MREMAP
2997 newp = mremap_chunk (oldp, nb);
2998 if (newp)
2999 return chunk2mem (newp);
3000 #endif
3001 /* Note the extra SIZE_SZ overhead. */
3002 if (oldsize - SIZE_SZ >= nb)
3003 return oldmem; /* do nothing */
3005 /* Must alloc, copy, free. */
3006 newmem = __libc_malloc (bytes);
3007 if (newmem == 0)
3008 return 0; /* propagate failure */
3010 memcpy (newmem, oldmem, oldsize - 2 * SIZE_SZ);
3011 munmap_chunk (oldp);
3012 return newmem;
3015 (void) mutex_lock (&ar_ptr->mutex);
3017 newp = _int_realloc (ar_ptr, oldp, oldsize, nb);
3019 (void) mutex_unlock (&ar_ptr->mutex);
3020 assert (!newp || chunk_is_mmapped (mem2chunk (newp)) ||
3021 ar_ptr == arena_for_chunk (mem2chunk (newp)));
3023 if (newp == NULL)
3025 /* Try harder to allocate memory in other arenas. */
3026 LIBC_PROBE (memory_realloc_retry, 2, bytes, oldmem);
3027 newp = __libc_malloc (bytes);
3028 if (newp != NULL)
3030 memcpy (newp, oldmem, oldsize - SIZE_SZ);
3031 _int_free (ar_ptr, oldp, 0);
3035 return newp;
3037 libc_hidden_def (__libc_realloc)
3039 void *
3040 __libc_memalign (size_t alignment, size_t bytes)
3042 void *address = RETURN_ADDRESS (0);
3043 return _mid_memalign (alignment, bytes, address);
3046 static void *
3047 _mid_memalign (size_t alignment, size_t bytes, void *address)
3049 mstate ar_ptr;
3050 void *p;
3052 void *(*hook) (size_t, size_t, const void *) =
3053 atomic_forced_read (__memalign_hook);
3054 if (__builtin_expect (hook != NULL, 0))
3055 return (*hook)(alignment, bytes, address);
3057 /* If we need less alignment than we give anyway, just relay to malloc. */
3058 if (alignment <= MALLOC_ALIGNMENT)
3059 return __libc_malloc (bytes);
3061 /* Otherwise, ensure that it is at least a minimum chunk size */
3062 if (alignment < MINSIZE)
3063 alignment = MINSIZE;
3065 /* If the alignment is greater than SIZE_MAX / 2 + 1 it cannot be a
3066 power of 2 and will cause overflow in the check below. */
3067 if (alignment > SIZE_MAX / 2 + 1)
3069 __set_errno (EINVAL);
3070 return 0;
3073 /* Check for overflow. */
3074 if (bytes > SIZE_MAX - alignment - MINSIZE)
3076 __set_errno (ENOMEM);
3077 return 0;
3081 /* Make sure alignment is power of 2. */
3082 if (!powerof2 (alignment))
3084 size_t a = MALLOC_ALIGNMENT * 2;
3085 while (a < alignment)
3086 a <<= 1;
3087 alignment = a;
3090 arena_get (ar_ptr, bytes + alignment + MINSIZE);
3092 p = _int_memalign (ar_ptr, alignment, bytes);
3093 if (!p && ar_ptr != NULL)
3095 LIBC_PROBE (memory_memalign_retry, 2, bytes, alignment);
3096 ar_ptr = arena_get_retry (ar_ptr, bytes);
3097 p = _int_memalign (ar_ptr, alignment, bytes);
3100 if (ar_ptr != NULL)
3101 (void) mutex_unlock (&ar_ptr->mutex);
3103 assert (!p || chunk_is_mmapped (mem2chunk (p)) ||
3104 ar_ptr == arena_for_chunk (mem2chunk (p)));
3105 return p;
3107 /* For ISO C11. */
3108 weak_alias (__libc_memalign, aligned_alloc)
3109 libc_hidden_def (__libc_memalign)
3111 void *
3112 __libc_valloc (size_t bytes)
3114 if (__malloc_initialized < 0)
3115 ptmalloc_init ();
3117 void *address = RETURN_ADDRESS (0);
3118 size_t pagesize = GLRO (dl_pagesize);
3119 return _mid_memalign (pagesize, bytes, address);
3122 void *
3123 __libc_pvalloc (size_t bytes)
3125 if (__malloc_initialized < 0)
3126 ptmalloc_init ();
3128 void *address = RETURN_ADDRESS (0);
3129 size_t pagesize = GLRO (dl_pagesize);
3130 size_t rounded_bytes = ALIGN_UP (bytes, pagesize);
3132 /* Check for overflow. */
3133 if (bytes > SIZE_MAX - 2 * pagesize - MINSIZE)
3135 __set_errno (ENOMEM);
3136 return 0;
3139 return _mid_memalign (pagesize, rounded_bytes, address);
3142 void *
3143 __libc_calloc (size_t n, size_t elem_size)
3145 mstate av;
3146 mchunkptr oldtop, p;
3147 INTERNAL_SIZE_T bytes, sz, csz, oldtopsize;
3148 void *mem;
3149 unsigned long clearsize;
3150 unsigned long nclears;
3151 INTERNAL_SIZE_T *d;
3153 /* size_t is unsigned so the behavior on overflow is defined. */
3154 bytes = n * elem_size;
3155 #define HALF_INTERNAL_SIZE_T \
3156 (((INTERNAL_SIZE_T) 1) << (8 * sizeof (INTERNAL_SIZE_T) / 2))
3157 if (__builtin_expect ((n | elem_size) >= HALF_INTERNAL_SIZE_T, 0))
3159 if (elem_size != 0 && bytes / elem_size != n)
3161 __set_errno (ENOMEM);
3162 return 0;
3166 void *(*hook) (size_t, const void *) =
3167 atomic_forced_read (__malloc_hook);
3168 if (__builtin_expect (hook != NULL, 0))
3170 sz = bytes;
3171 mem = (*hook)(sz, RETURN_ADDRESS (0));
3172 if (mem == 0)
3173 return 0;
3175 return memset (mem, 0, sz);
3178 sz = bytes;
3180 arena_get (av, sz);
3181 if (av)
3183 /* Check if we hand out the top chunk, in which case there may be no
3184 need to clear. */
3185 #if MORECORE_CLEARS
3186 oldtop = top (av);
3187 oldtopsize = chunksize (top (av));
3188 # if MORECORE_CLEARS < 2
3189 /* Only newly allocated memory is guaranteed to be cleared. */
3190 if (av == &main_arena &&
3191 oldtopsize < mp_.sbrk_base + av->max_system_mem - (char *) oldtop)
3192 oldtopsize = (mp_.sbrk_base + av->max_system_mem - (char *) oldtop);
3193 # endif
3194 if (av != &main_arena)
3196 heap_info *heap = heap_for_ptr (oldtop);
3197 if (oldtopsize < (char *) heap + heap->mprotect_size - (char *) oldtop)
3198 oldtopsize = (char *) heap + heap->mprotect_size - (char *) oldtop;
3200 #endif
3202 else
3204 /* No usable arenas. */
3205 oldtop = 0;
3206 oldtopsize = 0;
3208 mem = _int_malloc (av, sz);
3211 assert (!mem || chunk_is_mmapped (mem2chunk (mem)) ||
3212 av == arena_for_chunk (mem2chunk (mem)));
3214 if (mem == 0 && av != NULL)
3216 LIBC_PROBE (memory_calloc_retry, 1, sz);
3217 av = arena_get_retry (av, sz);
3218 mem = _int_malloc (av, sz);
3221 if (av != NULL)
3222 (void) mutex_unlock (&av->mutex);
3224 /* Allocation failed even after a retry. */
3225 if (mem == 0)
3226 return 0;
3228 p = mem2chunk (mem);
3230 /* Two optional cases in which clearing not necessary */
3231 if (chunk_is_mmapped (p))
3233 if (__builtin_expect (perturb_byte, 0))
3234 return memset (mem, 0, sz);
3236 return mem;
3239 csz = chunksize (p);
3241 #if MORECORE_CLEARS
3242 if (perturb_byte == 0 && (p == oldtop && csz > oldtopsize))
3244 /* clear only the bytes from non-freshly-sbrked memory */
3245 csz = oldtopsize;
3247 #endif
3249 /* Unroll clear of <= 36 bytes (72 if 8byte sizes). We know that
3250 contents have an odd number of INTERNAL_SIZE_T-sized words;
3251 minimally 3. */
3252 d = (INTERNAL_SIZE_T *) mem;
3253 clearsize = csz - SIZE_SZ;
3254 nclears = clearsize / sizeof (INTERNAL_SIZE_T);
3255 assert (nclears >= 3);
3257 if (nclears > 9)
3258 return memset (d, 0, clearsize);
3260 else
3262 *(d + 0) = 0;
3263 *(d + 1) = 0;
3264 *(d + 2) = 0;
3265 if (nclears > 4)
3267 *(d + 3) = 0;
3268 *(d + 4) = 0;
3269 if (nclears > 6)
3271 *(d + 5) = 0;
3272 *(d + 6) = 0;
3273 if (nclears > 8)
3275 *(d + 7) = 0;
3276 *(d + 8) = 0;
3282 return mem;
3286 ------------------------------ malloc ------------------------------
3289 static void *
3290 _int_malloc (mstate av, size_t bytes)
3292 INTERNAL_SIZE_T nb; /* normalized request size */
3293 unsigned int idx; /* associated bin index */
3294 mbinptr bin; /* associated bin */
3296 mchunkptr victim; /* inspected/selected chunk */
3297 INTERNAL_SIZE_T size; /* its size */
3298 int victim_index; /* its bin index */
3300 mchunkptr remainder; /* remainder from a split */
3301 unsigned long remainder_size; /* its size */
3303 unsigned int block; /* bit map traverser */
3304 unsigned int bit; /* bit map traverser */
3305 unsigned int map; /* current word of binmap */
3307 mchunkptr fwd; /* misc temp for linking */
3308 mchunkptr bck; /* misc temp for linking */
3310 const char *errstr = NULL;
3313 Convert request size to internal form by adding SIZE_SZ bytes
3314 overhead plus possibly more to obtain necessary alignment and/or
3315 to obtain a size of at least MINSIZE, the smallest allocatable
3316 size. Also, checked_request2size traps (returning 0) request sizes
3317 that are so large that they wrap around zero when padded and
3318 aligned.
3321 checked_request2size (bytes, nb);
3323 /* There are no usable arenas. Fall back to sysmalloc to get a chunk from
3324 mmap. */
3325 if (__glibc_unlikely (av == NULL))
3327 void *p = sysmalloc (nb, av);
3328 if (p != NULL)
3329 alloc_perturb (p, bytes);
3330 return p;
3334 If the size qualifies as a fastbin, first check corresponding bin.
3335 This code is safe to execute even if av is not yet initialized, so we
3336 can try it without checking, which saves some time on this fast path.
3339 if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
3341 idx = fastbin_index (nb);
3342 mfastbinptr *fb = &fastbin (av, idx);
3343 mchunkptr pp = *fb;
3346 victim = pp;
3347 if (victim == NULL)
3348 break;
3350 while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
3351 != victim);
3352 if (victim != 0)
3354 if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
3356 errstr = "malloc(): memory corruption (fast)";
3357 errout:
3358 malloc_printerr (check_action, errstr, chunk2mem (victim), av);
3359 return NULL;
3361 check_remalloced_chunk (av, victim, nb);
3362 void *p = chunk2mem (victim);
3363 alloc_perturb (p, bytes);
3364 return p;
3369 If a small request, check regular bin. Since these "smallbins"
3370 hold one size each, no searching within bins is necessary.
3371 (For a large request, we need to wait until unsorted chunks are
3372 processed to find best fit. But for small ones, fits are exact
3373 anyway, so we can check now, which is faster.)
3376 if (in_smallbin_range (nb))
3378 idx = smallbin_index (nb);
3379 bin = bin_at (av, idx);
3381 if ((victim = last (bin)) != bin)
3383 if (victim == 0) /* initialization check */
3384 malloc_consolidate (av);
3385 else
3387 bck = victim->bk;
3388 if (__glibc_unlikely (bck->fd != victim))
3390 errstr = "malloc(): smallbin double linked list corrupted";
3391 goto errout;
3393 set_inuse_bit_at_offset (victim, nb);
3394 bin->bk = bck;
3395 bck->fd = bin;
3397 if (av != &main_arena)
3398 victim->size |= NON_MAIN_ARENA;
3399 check_malloced_chunk (av, victim, nb);
3400 void *p = chunk2mem (victim);
3401 alloc_perturb (p, bytes);
3402 return p;
3408 If this is a large request, consolidate fastbins before continuing.
3409 While it might look excessive to kill all fastbins before
3410 even seeing if there is space available, this avoids
3411 fragmentation problems normally associated with fastbins.
3412 Also, in practice, programs tend to have runs of either small or
3413 large requests, but less often mixtures, so consolidation is not
3414 invoked all that often in most programs. And the programs that
3415 it is called frequently in otherwise tend to fragment.
3418 else
3420 idx = largebin_index (nb);
3421 if (have_fastchunks (av))
3422 malloc_consolidate (av);
3426 Process recently freed or remaindered chunks, taking one only if
3427 it is exact fit, or, if this a small request, the chunk is remainder from
3428 the most recent non-exact fit. Place other traversed chunks in
3429 bins. Note that this step is the only place in any routine where
3430 chunks are placed in bins.
3432 The outer loop here is needed because we might not realize until
3433 near the end of malloc that we should have consolidated, so must
3434 do so and retry. This happens at most once, and only when we would
3435 otherwise need to expand memory to service a "small" request.
3438 for (;; )
3440 int iters = 0;
3441 while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
3443 bck = victim->bk;
3444 if (__builtin_expect (victim->size <= 2 * SIZE_SZ, 0)
3445 || __builtin_expect (victim->size > av->system_mem, 0))
3446 malloc_printerr (check_action, "malloc(): memory corruption",
3447 chunk2mem (victim), av);
3448 size = chunksize (victim);
3451 If a small request, try to use last remainder if it is the
3452 only chunk in unsorted bin. This helps promote locality for
3453 runs of consecutive small requests. This is the only
3454 exception to best-fit, and applies only when there is
3455 no exact fit for a small chunk.
3458 if (in_smallbin_range (nb) &&
3459 bck == unsorted_chunks (av) &&
3460 victim == av->last_remainder &&
3461 (unsigned long) (size) > (unsigned long) (nb + MINSIZE))
3463 /* split and reattach remainder */
3464 remainder_size = size - nb;
3465 remainder = chunk_at_offset (victim, nb);
3466 unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
3467 av->last_remainder = remainder;
3468 remainder->bk = remainder->fd = unsorted_chunks (av);
3469 if (!in_smallbin_range (remainder_size))
3471 remainder->fd_nextsize = NULL;
3472 remainder->bk_nextsize = NULL;
3475 set_head (victim, nb | PREV_INUSE |
3476 (av != &main_arena ? NON_MAIN_ARENA : 0));
3477 set_head (remainder, remainder_size | PREV_INUSE);
3478 set_foot (remainder, remainder_size);
3480 check_malloced_chunk (av, victim, nb);
3481 void *p = chunk2mem (victim);
3482 alloc_perturb (p, bytes);
3483 return p;
3486 /* remove from unsorted list */
3487 unsorted_chunks (av)->bk = bck;
3488 bck->fd = unsorted_chunks (av);
3490 /* Take now instead of binning if exact fit */
3492 if (size == nb)
3494 set_inuse_bit_at_offset (victim, size);
3495 if (av != &main_arena)
3496 victim->size |= NON_MAIN_ARENA;
3497 check_malloced_chunk (av, victim, nb);
3498 void *p = chunk2mem (victim);
3499 alloc_perturb (p, bytes);
3500 return p;
3503 /* place chunk in bin */
3505 if (in_smallbin_range (size))
3507 victim_index = smallbin_index (size);
3508 bck = bin_at (av, victim_index);
3509 fwd = bck->fd;
3511 else
3513 victim_index = largebin_index (size);
3514 bck = bin_at (av, victim_index);
3515 fwd = bck->fd;
3517 /* maintain large bins in sorted order */
3518 if (fwd != bck)
3520 /* Or with inuse bit to speed comparisons */
3521 size |= PREV_INUSE;
3522 /* if smaller than smallest, bypass loop below */
3523 assert ((bck->bk->size & NON_MAIN_ARENA) == 0);
3524 if ((unsigned long) (size) < (unsigned long) (bck->bk->size))
3526 fwd = bck;
3527 bck = bck->bk;
3529 victim->fd_nextsize = fwd->fd;
3530 victim->bk_nextsize = fwd->fd->bk_nextsize;
3531 fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
3533 else
3535 assert ((fwd->size & NON_MAIN_ARENA) == 0);
3536 while ((unsigned long) size < fwd->size)
3538 fwd = fwd->fd_nextsize;
3539 assert ((fwd->size & NON_MAIN_ARENA) == 0);
3542 if ((unsigned long) size == (unsigned long) fwd->size)
3543 /* Always insert in the second position. */
3544 fwd = fwd->fd;
3545 else
3547 victim->fd_nextsize = fwd;
3548 victim->bk_nextsize = fwd->bk_nextsize;
3549 fwd->bk_nextsize = victim;
3550 victim->bk_nextsize->fd_nextsize = victim;
3552 bck = fwd->bk;
3555 else
3556 victim->fd_nextsize = victim->bk_nextsize = victim;
3559 mark_bin (av, victim_index);
3560 victim->bk = bck;
3561 victim->fd = fwd;
3562 fwd->bk = victim;
3563 bck->fd = victim;
3565 #define MAX_ITERS 10000
3566 if (++iters >= MAX_ITERS)
3567 break;
3571 If a large request, scan through the chunks of current bin in
3572 sorted order to find smallest that fits. Use the skip list for this.
3575 if (!in_smallbin_range (nb))
3577 bin = bin_at (av, idx);
3579 /* skip scan if empty or largest chunk is too small */
3580 if ((victim = first (bin)) != bin &&
3581 (unsigned long) (victim->size) >= (unsigned long) (nb))
3583 victim = victim->bk_nextsize;
3584 while (((unsigned long) (size = chunksize (victim)) <
3585 (unsigned long) (nb)))
3586 victim = victim->bk_nextsize;
3588 /* Avoid removing the first entry for a size so that the skip
3589 list does not have to be rerouted. */
3590 if (victim != last (bin) && victim->size == victim->fd->size)
3591 victim = victim->fd;
3593 remainder_size = size - nb;
3594 unlink (av, victim, bck, fwd);
3596 /* Exhaust */
3597 if (remainder_size < MINSIZE)
3599 set_inuse_bit_at_offset (victim, size);
3600 if (av != &main_arena)
3601 victim->size |= NON_MAIN_ARENA;
3603 /* Split */
3604 else
3606 remainder = chunk_at_offset (victim, nb);
3607 /* We cannot assume the unsorted list is empty and therefore
3608 have to perform a complete insert here. */
3609 bck = unsorted_chunks (av);
3610 fwd = bck->fd;
3611 if (__glibc_unlikely (fwd->bk != bck))
3613 errstr = "malloc(): corrupted unsorted chunks";
3614 goto errout;
3616 remainder->bk = bck;
3617 remainder->fd = fwd;
3618 bck->fd = remainder;
3619 fwd->bk = remainder;
3620 if (!in_smallbin_range (remainder_size))
3622 remainder->fd_nextsize = NULL;
3623 remainder->bk_nextsize = NULL;
3625 set_head (victim, nb | PREV_INUSE |
3626 (av != &main_arena ? NON_MAIN_ARENA : 0));
3627 set_head (remainder, remainder_size | PREV_INUSE);
3628 set_foot (remainder, remainder_size);
3630 check_malloced_chunk (av, victim, nb);
3631 void *p = chunk2mem (victim);
3632 alloc_perturb (p, bytes);
3633 return p;
3638 Search for a chunk by scanning bins, starting with next largest
3639 bin. This search is strictly by best-fit; i.e., the smallest
3640 (with ties going to approximately the least recently used) chunk
3641 that fits is selected.
3643 The bitmap avoids needing to check that most blocks are nonempty.
3644 The particular case of skipping all bins during warm-up phases
3645 when no chunks have been returned yet is faster than it might look.
3648 ++idx;
3649 bin = bin_at (av, idx);
3650 block = idx2block (idx);
3651 map = av->binmap[block];
3652 bit = idx2bit (idx);
3654 for (;; )
3656 /* Skip rest of block if there are no more set bits in this block. */
3657 if (bit > map || bit == 0)
3661 if (++block >= BINMAPSIZE) /* out of bins */
3662 goto use_top;
3664 while ((map = av->binmap[block]) == 0);
3666 bin = bin_at (av, (block << BINMAPSHIFT));
3667 bit = 1;
3670 /* Advance to bin with set bit. There must be one. */
3671 while ((bit & map) == 0)
3673 bin = next_bin (bin);
3674 bit <<= 1;
3675 assert (bit != 0);
3678 /* Inspect the bin. It is likely to be non-empty */
3679 victim = last (bin);
3681 /* If a false alarm (empty bin), clear the bit. */
3682 if (victim == bin)
3684 av->binmap[block] = map &= ~bit; /* Write through */
3685 bin = next_bin (bin);
3686 bit <<= 1;
3689 else
3691 size = chunksize (victim);
3693 /* We know the first chunk in this bin is big enough to use. */
3694 assert ((unsigned long) (size) >= (unsigned long) (nb));
3696 remainder_size = size - nb;
3698 /* unlink */
3699 unlink (av, victim, bck, fwd);
3701 /* Exhaust */
3702 if (remainder_size < MINSIZE)
3704 set_inuse_bit_at_offset (victim, size);
3705 if (av != &main_arena)
3706 victim->size |= NON_MAIN_ARENA;
3709 /* Split */
3710 else
3712 remainder = chunk_at_offset (victim, nb);
3714 /* We cannot assume the unsorted list is empty and therefore
3715 have to perform a complete insert here. */
3716 bck = unsorted_chunks (av);
3717 fwd = bck->fd;
3718 if (__glibc_unlikely (fwd->bk != bck))
3720 errstr = "malloc(): corrupted unsorted chunks 2";
3721 goto errout;
3723 remainder->bk = bck;
3724 remainder->fd = fwd;
3725 bck->fd = remainder;
3726 fwd->bk = remainder;
3728 /* advertise as last remainder */
3729 if (in_smallbin_range (nb))
3730 av->last_remainder = remainder;
3731 if (!in_smallbin_range (remainder_size))
3733 remainder->fd_nextsize = NULL;
3734 remainder->bk_nextsize = NULL;
3736 set_head (victim, nb | PREV_INUSE |
3737 (av != &main_arena ? NON_MAIN_ARENA : 0));
3738 set_head (remainder, remainder_size | PREV_INUSE);
3739 set_foot (remainder, remainder_size);
3741 check_malloced_chunk (av, victim, nb);
3742 void *p = chunk2mem (victim);
3743 alloc_perturb (p, bytes);
3744 return p;
3748 use_top:
3750 If large enough, split off the chunk bordering the end of memory
3751 (held in av->top). Note that this is in accord with the best-fit
3752 search rule. In effect, av->top is treated as larger (and thus
3753 less well fitting) than any other available chunk since it can
3754 be extended to be as large as necessary (up to system
3755 limitations).
3757 We require that av->top always exists (i.e., has size >=
3758 MINSIZE) after initialization, so if it would otherwise be
3759 exhausted by current request, it is replenished. (The main
3760 reason for ensuring it exists is that we may need MINSIZE space
3761 to put in fenceposts in sysmalloc.)
3764 victim = av->top;
3765 size = chunksize (victim);
3767 if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
3769 remainder_size = size - nb;
3770 remainder = chunk_at_offset (victim, nb);
3771 av->top = remainder;
3772 set_head (victim, nb | PREV_INUSE |
3773 (av != &main_arena ? NON_MAIN_ARENA : 0));
3774 set_head (remainder, remainder_size | PREV_INUSE);
3776 check_malloced_chunk (av, victim, nb);
3777 void *p = chunk2mem (victim);
3778 alloc_perturb (p, bytes);
3779 return p;
3782 /* When we are using atomic ops to free fast chunks we can get
3783 here for all block sizes. */
3784 else if (have_fastchunks (av))
3786 malloc_consolidate (av);
3787 /* restore original bin index */
3788 if (in_smallbin_range (nb))
3789 idx = smallbin_index (nb);
3790 else
3791 idx = largebin_index (nb);
3795 Otherwise, relay to handle system-dependent cases
3797 else
3799 void *p = sysmalloc (nb, av);
3800 if (p != NULL)
3801 alloc_perturb (p, bytes);
3802 return p;
3808 ------------------------------ free ------------------------------
3811 static void
3812 _int_free (mstate av, mchunkptr p, int have_lock)
3814 INTERNAL_SIZE_T size; /* its size */
3815 mfastbinptr *fb; /* associated fastbin */
3816 mchunkptr nextchunk; /* next contiguous chunk */
3817 INTERNAL_SIZE_T nextsize; /* its size */
3818 int nextinuse; /* true if nextchunk is used */
3819 INTERNAL_SIZE_T prevsize; /* size of previous contiguous chunk */
3820 mchunkptr bck; /* misc temp for linking */
3821 mchunkptr fwd; /* misc temp for linking */
3823 const char *errstr = NULL;
3824 int locked = 0;
3826 size = chunksize (p);
3828 /* Little security check which won't hurt performance: the
3829 allocator never wrapps around at the end of the address space.
3830 Therefore we can exclude some size values which might appear
3831 here by accident or by "design" from some intruder. */
3832 if (__builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0)
3833 || __builtin_expect (misaligned_chunk (p), 0))
3835 errstr = "free(): invalid pointer";
3836 errout:
3837 if (!have_lock && locked)
3838 (void) mutex_unlock (&av->mutex);
3839 malloc_printerr (check_action, errstr, chunk2mem (p), av);
3840 return;
3842 /* We know that each chunk is at least MINSIZE bytes in size or a
3843 multiple of MALLOC_ALIGNMENT. */
3844 if (__glibc_unlikely (size < MINSIZE || !aligned_OK (size)))
3846 errstr = "free(): invalid size";
3847 goto errout;
3850 check_inuse_chunk(av, p);
3853 If eligible, place chunk on a fastbin so it can be found
3854 and used quickly in malloc.
3857 if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())
3859 #if TRIM_FASTBINS
3861 If TRIM_FASTBINS set, don't place chunks
3862 bordering top into fastbins
3864 && (chunk_at_offset(p, size) != av->top)
3865 #endif
3868 if (__builtin_expect (chunk_at_offset (p, size)->size <= 2 * SIZE_SZ, 0)
3869 || __builtin_expect (chunksize (chunk_at_offset (p, size))
3870 >= av->system_mem, 0))
3872 /* We might not have a lock at this point and concurrent modifications
3873 of system_mem might have let to a false positive. Redo the test
3874 after getting the lock. */
3875 if (have_lock
3876 || ({ assert (locked == 0);
3877 mutex_lock(&av->mutex);
3878 locked = 1;
3879 chunk_at_offset (p, size)->size <= 2 * SIZE_SZ
3880 || chunksize (chunk_at_offset (p, size)) >= av->system_mem;
3883 errstr = "free(): invalid next size (fast)";
3884 goto errout;
3886 if (! have_lock)
3888 (void)mutex_unlock(&av->mutex);
3889 locked = 0;
3893 free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
3895 set_fastchunks(av);
3896 unsigned int idx = fastbin_index(size);
3897 fb = &fastbin (av, idx);
3899 /* Atomically link P to its fastbin: P->FD = *FB; *FB = P; */
3900 mchunkptr old = *fb, old2;
3901 unsigned int old_idx = ~0u;
3904 /* Check that the top of the bin is not the record we are going to add
3905 (i.e., double free). */
3906 if (__builtin_expect (old == p, 0))
3908 errstr = "double free or corruption (fasttop)";
3909 goto errout;
3911 /* Check that size of fastbin chunk at the top is the same as
3912 size of the chunk that we are adding. We can dereference OLD
3913 only if we have the lock, otherwise it might have already been
3914 deallocated. See use of OLD_IDX below for the actual check. */
3915 if (have_lock && old != NULL)
3916 old_idx = fastbin_index(chunksize(old));
3917 p->fd = old2 = old;
3919 while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2);
3921 if (have_lock && old != NULL && __builtin_expect (old_idx != idx, 0))
3923 errstr = "invalid fastbin entry (free)";
3924 goto errout;
3929 Consolidate other non-mmapped chunks as they arrive.
3932 else if (!chunk_is_mmapped(p)) {
3933 if (! have_lock) {
3934 (void)mutex_lock(&av->mutex);
3935 locked = 1;
3938 nextchunk = chunk_at_offset(p, size);
3940 /* Lightweight tests: check whether the block is already the
3941 top block. */
3942 if (__glibc_unlikely (p == av->top))
3944 errstr = "double free or corruption (top)";
3945 goto errout;
3947 /* Or whether the next chunk is beyond the boundaries of the arena. */
3948 if (__builtin_expect (contiguous (av)
3949 && (char *) nextchunk
3950 >= ((char *) av->top + chunksize(av->top)), 0))
3952 errstr = "double free or corruption (out)";
3953 goto errout;
3955 /* Or whether the block is actually not marked used. */
3956 if (__glibc_unlikely (!prev_inuse(nextchunk)))
3958 errstr = "double free or corruption (!prev)";
3959 goto errout;
3962 nextsize = chunksize(nextchunk);
3963 if (__builtin_expect (nextchunk->size <= 2 * SIZE_SZ, 0)
3964 || __builtin_expect (nextsize >= av->system_mem, 0))
3966 errstr = "free(): invalid next size (normal)";
3967 goto errout;
3970 free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
3972 /* consolidate backward */
3973 if (!prev_inuse(p)) {
3974 prevsize = p->prev_size;
3975 size += prevsize;
3976 p = chunk_at_offset(p, -((long) prevsize));
3977 unlink(av, p, bck, fwd);
3980 if (nextchunk != av->top) {
3981 /* get and clear inuse bit */
3982 nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
3984 /* consolidate forward */
3985 if (!nextinuse) {
3986 unlink(av, nextchunk, bck, fwd);
3987 size += nextsize;
3988 } else
3989 clear_inuse_bit_at_offset(nextchunk, 0);
3992 Place the chunk in unsorted chunk list. Chunks are
3993 not placed into regular bins until after they have
3994 been given one chance to be used in malloc.
3997 bck = unsorted_chunks(av);
3998 fwd = bck->fd;
3999 if (__glibc_unlikely (fwd->bk != bck))
4001 errstr = "free(): corrupted unsorted chunks";
4002 goto errout;
4004 p->fd = fwd;
4005 p->bk = bck;
4006 if (!in_smallbin_range(size))
4008 p->fd_nextsize = NULL;
4009 p->bk_nextsize = NULL;
4011 bck->fd = p;
4012 fwd->bk = p;
4014 set_head(p, size | PREV_INUSE);
4015 set_foot(p, size);
4017 check_free_chunk(av, p);
4021 If the chunk borders the current high end of memory,
4022 consolidate into top
4025 else {
4026 size += nextsize;
4027 set_head(p, size | PREV_INUSE);
4028 av->top = p;
4029 check_chunk(av, p);
4033 If freeing a large space, consolidate possibly-surrounding
4034 chunks. Then, if the total unused topmost memory exceeds trim
4035 threshold, ask malloc_trim to reduce top.
4037 Unless max_fast is 0, we don't know if there are fastbins
4038 bordering top, so we cannot tell for sure whether threshold
4039 has been reached unless fastbins are consolidated. But we
4040 don't want to consolidate on each free. As a compromise,
4041 consolidation is performed if FASTBIN_CONSOLIDATION_THRESHOLD
4042 is reached.
4045 if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
4046 if (have_fastchunks(av))
4047 malloc_consolidate(av);
4049 if (av == &main_arena) {
4050 #ifndef MORECORE_CANNOT_TRIM
4051 if ((unsigned long)(chunksize(av->top)) >=
4052 (unsigned long)(mp_.trim_threshold))
4053 systrim(mp_.top_pad, av);
4054 #endif
4055 } else {
4056 /* Always try heap_trim(), even if the top chunk is not
4057 large, because the corresponding heap might go away. */
4058 heap_info *heap = heap_for_ptr(top(av));
4060 assert(heap->ar_ptr == av);
4061 heap_trim(heap, mp_.top_pad);
4065 if (! have_lock) {
4066 assert (locked);
4067 (void)mutex_unlock(&av->mutex);
4071 If the chunk was allocated via mmap, release via munmap().
4074 else {
4075 munmap_chunk (p);
4080 ------------------------- malloc_consolidate -------------------------
4082 malloc_consolidate is a specialized version of free() that tears
4083 down chunks held in fastbins. Free itself cannot be used for this
4084 purpose since, among other things, it might place chunks back onto
4085 fastbins. So, instead, we need to use a minor variant of the same
4086 code.
4088 Also, because this routine needs to be called the first time through
4089 malloc anyway, it turns out to be the perfect place to trigger
4090 initialization code.
4093 static void malloc_consolidate(mstate av)
4095 mfastbinptr* fb; /* current fastbin being consolidated */
4096 mfastbinptr* maxfb; /* last fastbin (for loop control) */
4097 mchunkptr p; /* current chunk being consolidated */
4098 mchunkptr nextp; /* next chunk to consolidate */
4099 mchunkptr unsorted_bin; /* bin header */
4100 mchunkptr first_unsorted; /* chunk to link to */
4102 /* These have same use as in free() */
4103 mchunkptr nextchunk;
4104 INTERNAL_SIZE_T size;
4105 INTERNAL_SIZE_T nextsize;
4106 INTERNAL_SIZE_T prevsize;
4107 int nextinuse;
4108 mchunkptr bck;
4109 mchunkptr fwd;
4112 If max_fast is 0, we know that av hasn't
4113 yet been initialized, in which case do so below
4116 if (get_max_fast () != 0) {
4117 clear_fastchunks(av);
4119 unsorted_bin = unsorted_chunks(av);
4122 Remove each chunk from fast bin and consolidate it, placing it
4123 then in unsorted bin. Among other reasons for doing this,
4124 placing in unsorted bin avoids needing to calculate actual bins
4125 until malloc is sure that chunks aren't immediately going to be
4126 reused anyway.
4129 maxfb = &fastbin (av, NFASTBINS - 1);
4130 fb = &fastbin (av, 0);
4131 do {
4132 p = atomic_exchange_acq (fb, NULL);
4133 if (p != 0) {
4134 do {
4135 check_inuse_chunk(av, p);
4136 nextp = p->fd;
4138 /* Slightly streamlined version of consolidation code in free() */
4139 size = p->size & ~(PREV_INUSE|NON_MAIN_ARENA);
4140 nextchunk = chunk_at_offset(p, size);
4141 nextsize = chunksize(nextchunk);
4143 if (!prev_inuse(p)) {
4144 prevsize = p->prev_size;
4145 size += prevsize;
4146 p = chunk_at_offset(p, -((long) prevsize));
4147 unlink(av, p, bck, fwd);
4150 if (nextchunk != av->top) {
4151 nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
4153 if (!nextinuse) {
4154 size += nextsize;
4155 unlink(av, nextchunk, bck, fwd);
4156 } else
4157 clear_inuse_bit_at_offset(nextchunk, 0);
4159 first_unsorted = unsorted_bin->fd;
4160 unsorted_bin->fd = p;
4161 first_unsorted->bk = p;
4163 if (!in_smallbin_range (size)) {
4164 p->fd_nextsize = NULL;
4165 p->bk_nextsize = NULL;
4168 set_head(p, size | PREV_INUSE);
4169 p->bk = unsorted_bin;
4170 p->fd = first_unsorted;
4171 set_foot(p, size);
4174 else {
4175 size += nextsize;
4176 set_head(p, size | PREV_INUSE);
4177 av->top = p;
4180 } while ( (p = nextp) != 0);
4183 } while (fb++ != maxfb);
4185 else {
4186 malloc_init_state(av);
4187 check_malloc_state(av);
4192 ------------------------------ realloc ------------------------------
4195 void*
4196 _int_realloc(mstate av, mchunkptr oldp, INTERNAL_SIZE_T oldsize,
4197 INTERNAL_SIZE_T nb)
4199 mchunkptr newp; /* chunk to return */
4200 INTERNAL_SIZE_T newsize; /* its size */
4201 void* newmem; /* corresponding user mem */
4203 mchunkptr next; /* next contiguous chunk after oldp */
4205 mchunkptr remainder; /* extra space at end of newp */
4206 unsigned long remainder_size; /* its size */
4208 mchunkptr bck; /* misc temp for linking */
4209 mchunkptr fwd; /* misc temp for linking */
4211 unsigned long copysize; /* bytes to copy */
4212 unsigned int ncopies; /* INTERNAL_SIZE_T words to copy */
4213 INTERNAL_SIZE_T* s; /* copy source */
4214 INTERNAL_SIZE_T* d; /* copy destination */
4216 const char *errstr = NULL;
4218 /* oldmem size */
4219 if (__builtin_expect (oldp->size <= 2 * SIZE_SZ, 0)
4220 || __builtin_expect (oldsize >= av->system_mem, 0))
4222 errstr = "realloc(): invalid old size";
4223 errout:
4224 malloc_printerr (check_action, errstr, chunk2mem (oldp), av);
4225 return NULL;
4228 check_inuse_chunk (av, oldp);
4230 /* All callers already filter out mmap'ed chunks. */
4231 assert (!chunk_is_mmapped (oldp));
4233 next = chunk_at_offset (oldp, oldsize);
4234 INTERNAL_SIZE_T nextsize = chunksize (next);
4235 if (__builtin_expect (next->size <= 2 * SIZE_SZ, 0)
4236 || __builtin_expect (nextsize >= av->system_mem, 0))
4238 errstr = "realloc(): invalid next size";
4239 goto errout;
4242 if ((unsigned long) (oldsize) >= (unsigned long) (nb))
4244 /* already big enough; split below */
4245 newp = oldp;
4246 newsize = oldsize;
4249 else
4251 /* Try to expand forward into top */
4252 if (next == av->top &&
4253 (unsigned long) (newsize = oldsize + nextsize) >=
4254 (unsigned long) (nb + MINSIZE))
4256 set_head_size (oldp, nb | (av != &main_arena ? NON_MAIN_ARENA : 0));
4257 av->top = chunk_at_offset (oldp, nb);
4258 set_head (av->top, (newsize - nb) | PREV_INUSE);
4259 check_inuse_chunk (av, oldp);
4260 return chunk2mem (oldp);
4263 /* Try to expand forward into next chunk; split off remainder below */
4264 else if (next != av->top &&
4265 !inuse (next) &&
4266 (unsigned long) (newsize = oldsize + nextsize) >=
4267 (unsigned long) (nb))
4269 newp = oldp;
4270 unlink (av, next, bck, fwd);
4273 /* allocate, copy, free */
4274 else
4276 newmem = _int_malloc (av, nb - MALLOC_ALIGN_MASK);
4277 if (newmem == 0)
4278 return 0; /* propagate failure */
4280 newp = mem2chunk (newmem);
4281 newsize = chunksize (newp);
4284 Avoid copy if newp is next chunk after oldp.
4286 if (newp == next)
4288 newsize += oldsize;
4289 newp = oldp;
4291 else
4294 Unroll copy of <= 36 bytes (72 if 8byte sizes)
4295 We know that contents have an odd number of
4296 INTERNAL_SIZE_T-sized words; minimally 3.
4299 copysize = oldsize - SIZE_SZ;
4300 s = (INTERNAL_SIZE_T *) (chunk2mem (oldp));
4301 d = (INTERNAL_SIZE_T *) (newmem);
4302 ncopies = copysize / sizeof (INTERNAL_SIZE_T);
4303 assert (ncopies >= 3);
4305 if (ncopies > 9)
4306 memcpy (d, s, copysize);
4308 else
4310 *(d + 0) = *(s + 0);
4311 *(d + 1) = *(s + 1);
4312 *(d + 2) = *(s + 2);
4313 if (ncopies > 4)
4315 *(d + 3) = *(s + 3);
4316 *(d + 4) = *(s + 4);
4317 if (ncopies > 6)
4319 *(d + 5) = *(s + 5);
4320 *(d + 6) = *(s + 6);
4321 if (ncopies > 8)
4323 *(d + 7) = *(s + 7);
4324 *(d + 8) = *(s + 8);
4330 _int_free (av, oldp, 1);
4331 check_inuse_chunk (av, newp);
4332 return chunk2mem (newp);
4337 /* If possible, free extra space in old or extended chunk */
4339 assert ((unsigned long) (newsize) >= (unsigned long) (nb));
4341 remainder_size = newsize - nb;
4343 if (remainder_size < MINSIZE) /* not enough extra to split off */
4345 set_head_size (newp, newsize | (av != &main_arena ? NON_MAIN_ARENA : 0));
4346 set_inuse_bit_at_offset (newp, newsize);
4348 else /* split remainder */
4350 remainder = chunk_at_offset (newp, nb);
4351 set_head_size (newp, nb | (av != &main_arena ? NON_MAIN_ARENA : 0));
4352 set_head (remainder, remainder_size | PREV_INUSE |
4353 (av != &main_arena ? NON_MAIN_ARENA : 0));
4354 /* Mark remainder as inuse so free() won't complain */
4355 set_inuse_bit_at_offset (remainder, remainder_size);
4356 _int_free (av, remainder, 1);
4359 check_inuse_chunk (av, newp);
4360 return chunk2mem (newp);
4364 ------------------------------ memalign ------------------------------
4367 static void *
4368 _int_memalign (mstate av, size_t alignment, size_t bytes)
4370 INTERNAL_SIZE_T nb; /* padded request size */
4371 char *m; /* memory returned by malloc call */
4372 mchunkptr p; /* corresponding chunk */
4373 char *brk; /* alignment point within p */
4374 mchunkptr newp; /* chunk to return */
4375 INTERNAL_SIZE_T newsize; /* its size */
4376 INTERNAL_SIZE_T leadsize; /* leading space before alignment point */
4377 mchunkptr remainder; /* spare room at end to split off */
4378 unsigned long remainder_size; /* its size */
4379 INTERNAL_SIZE_T size;
4383 checked_request2size (bytes, nb);
4386 Strategy: find a spot within that chunk that meets the alignment
4387 request, and then possibly free the leading and trailing space.
4391 /* Call malloc with worst case padding to hit alignment. */
4393 m = (char *) (_int_malloc (av, nb + alignment + MINSIZE));
4395 if (m == 0)
4396 return 0; /* propagate failure */
4398 p = mem2chunk (m);
4400 if ((((unsigned long) (m)) % alignment) != 0) /* misaligned */
4402 { /*
4403 Find an aligned spot inside chunk. Since we need to give back
4404 leading space in a chunk of at least MINSIZE, if the first
4405 calculation places us at a spot with less than MINSIZE leader,
4406 we can move to the next aligned spot -- we've allocated enough
4407 total room so that this is always possible.
4409 brk = (char *) mem2chunk (((unsigned long) (m + alignment - 1)) &
4410 - ((signed long) alignment));
4411 if ((unsigned long) (brk - (char *) (p)) < MINSIZE)
4412 brk += alignment;
4414 newp = (mchunkptr) brk;
4415 leadsize = brk - (char *) (p);
4416 newsize = chunksize (p) - leadsize;
4418 /* For mmapped chunks, just adjust offset */
4419 if (chunk_is_mmapped (p))
4421 newp->prev_size = p->prev_size + leadsize;
4422 set_head (newp, newsize | IS_MMAPPED);
4423 return chunk2mem (newp);
4426 /* Otherwise, give back leader, use the rest */
4427 set_head (newp, newsize | PREV_INUSE |
4428 (av != &main_arena ? NON_MAIN_ARENA : 0));
4429 set_inuse_bit_at_offset (newp, newsize);
4430 set_head_size (p, leadsize | (av != &main_arena ? NON_MAIN_ARENA : 0));
4431 _int_free (av, p, 1);
4432 p = newp;
4434 assert (newsize >= nb &&
4435 (((unsigned long) (chunk2mem (p))) % alignment) == 0);
4438 /* Also give back spare room at the end */
4439 if (!chunk_is_mmapped (p))
4441 size = chunksize (p);
4442 if ((unsigned long) (size) > (unsigned long) (nb + MINSIZE))
4444 remainder_size = size - nb;
4445 remainder = chunk_at_offset (p, nb);
4446 set_head (remainder, remainder_size | PREV_INUSE |
4447 (av != &main_arena ? NON_MAIN_ARENA : 0));
4448 set_head_size (p, nb);
4449 _int_free (av, remainder, 1);
4453 check_inuse_chunk (av, p);
4454 return chunk2mem (p);
4459 ------------------------------ malloc_trim ------------------------------
4462 static int
4463 mtrim (mstate av, size_t pad)
4465 /* Don't touch corrupt arenas. */
4466 if (arena_is_corrupt (av))
4467 return 0;
4469 /* Ensure initialization/consolidation */
4470 malloc_consolidate (av);
4472 const size_t ps = GLRO (dl_pagesize);
4473 int psindex = bin_index (ps);
4474 const size_t psm1 = ps - 1;
4476 int result = 0;
4477 for (int i = 1; i < NBINS; ++i)
4478 if (i == 1 || i >= psindex)
4480 mbinptr bin = bin_at (av, i);
4482 for (mchunkptr p = last (bin); p != bin; p = p->bk)
4484 INTERNAL_SIZE_T size = chunksize (p);
4486 if (size > psm1 + sizeof (struct malloc_chunk))
4488 /* See whether the chunk contains at least one unused page. */
4489 char *paligned_mem = (char *) (((uintptr_t) p
4490 + sizeof (struct malloc_chunk)
4491 + psm1) & ~psm1);
4493 assert ((char *) chunk2mem (p) + 4 * SIZE_SZ <= paligned_mem);
4494 assert ((char *) p + size > paligned_mem);
4496 /* This is the size we could potentially free. */
4497 size -= paligned_mem - (char *) p;
4499 if (size > psm1)
4501 #if MALLOC_DEBUG
4502 /* When debugging we simulate destroying the memory
4503 content. */
4504 memset (paligned_mem, 0x89, size & ~psm1);
4505 #endif
4506 __madvise (paligned_mem, size & ~psm1, MADV_DONTNEED);
4508 result = 1;
4514 #ifndef MORECORE_CANNOT_TRIM
4515 return result | (av == &main_arena ? systrim (pad, av) : 0);
4517 #else
4518 return result;
4519 #endif
4524 __malloc_trim (size_t s)
4526 int result = 0;
4528 if (__malloc_initialized < 0)
4529 ptmalloc_init ();
4531 mstate ar_ptr = &main_arena;
4534 (void) mutex_lock (&ar_ptr->mutex);
4535 result |= mtrim (ar_ptr, s);
4536 (void) mutex_unlock (&ar_ptr->mutex);
4538 ar_ptr = ar_ptr->next;
4540 while (ar_ptr != &main_arena);
4542 return result;
4547 ------------------------- malloc_usable_size -------------------------
4550 static size_t
4551 musable (void *mem)
4553 mchunkptr p;
4554 if (mem != 0)
4556 p = mem2chunk (mem);
4558 if (__builtin_expect (using_malloc_checking == 1, 0))
4559 return malloc_check_get_size (p);
4561 if (chunk_is_mmapped (p))
4563 if (DUMPED_MAIN_ARENA_CHUNK (p))
4564 return chunksize (p) - SIZE_SZ;
4565 else
4566 return chunksize (p) - 2 * SIZE_SZ;
4568 else if (inuse (p))
4569 return chunksize (p) - SIZE_SZ;
4571 return 0;
4575 size_t
4576 __malloc_usable_size (void *m)
4578 size_t result;
4580 result = musable (m);
4581 return result;
4585 ------------------------------ mallinfo ------------------------------
4586 Accumulate malloc statistics for arena AV into M.
4589 static void
4590 int_mallinfo (mstate av, struct mallinfo *m)
4592 size_t i;
4593 mbinptr b;
4594 mchunkptr p;
4595 INTERNAL_SIZE_T avail;
4596 INTERNAL_SIZE_T fastavail;
4597 int nblocks;
4598 int nfastblocks;
4600 /* Ensure initialization */
4601 if (av->top == 0)
4602 malloc_consolidate (av);
4604 check_malloc_state (av);
4606 /* Account for top */
4607 avail = chunksize (av->top);
4608 nblocks = 1; /* top always exists */
4610 /* traverse fastbins */
4611 nfastblocks = 0;
4612 fastavail = 0;
4614 for (i = 0; i < NFASTBINS; ++i)
4616 for (p = fastbin (av, i); p != 0; p = p->fd)
4618 ++nfastblocks;
4619 fastavail += chunksize (p);
4623 avail += fastavail;
4625 /* traverse regular bins */
4626 for (i = 1; i < NBINS; ++i)
4628 b = bin_at (av, i);
4629 for (p = last (b); p != b; p = p->bk)
4631 ++nblocks;
4632 avail += chunksize (p);
4636 m->smblks += nfastblocks;
4637 m->ordblks += nblocks;
4638 m->fordblks += avail;
4639 m->uordblks += av->system_mem - avail;
4640 m->arena += av->system_mem;
4641 m->fsmblks += fastavail;
4642 if (av == &main_arena)
4644 m->hblks = mp_.n_mmaps;
4645 m->hblkhd = mp_.mmapped_mem;
4646 m->usmblks = 0;
4647 m->keepcost = chunksize (av->top);
4652 struct mallinfo
4653 __libc_mallinfo (void)
4655 struct mallinfo m;
4656 mstate ar_ptr;
4658 if (__malloc_initialized < 0)
4659 ptmalloc_init ();
4661 memset (&m, 0, sizeof (m));
4662 ar_ptr = &main_arena;
4665 (void) mutex_lock (&ar_ptr->mutex);
4666 int_mallinfo (ar_ptr, &m);
4667 (void) mutex_unlock (&ar_ptr->mutex);
4669 ar_ptr = ar_ptr->next;
4671 while (ar_ptr != &main_arena);
4673 return m;
4677 ------------------------------ malloc_stats ------------------------------
4680 void
4681 __malloc_stats (void)
4683 int i;
4684 mstate ar_ptr;
4685 unsigned int in_use_b = mp_.mmapped_mem, system_b = in_use_b;
4687 if (__malloc_initialized < 0)
4688 ptmalloc_init ();
4689 _IO_flockfile (stderr);
4690 int old_flags2 = ((_IO_FILE *) stderr)->_flags2;
4691 ((_IO_FILE *) stderr)->_flags2 |= _IO_FLAGS2_NOTCANCEL;
4692 for (i = 0, ar_ptr = &main_arena;; i++)
4694 struct mallinfo mi;
4696 memset (&mi, 0, sizeof (mi));
4697 (void) mutex_lock (&ar_ptr->mutex);
4698 int_mallinfo (ar_ptr, &mi);
4699 fprintf (stderr, "Arena %d:\n", i);
4700 fprintf (stderr, "system bytes = %10u\n", (unsigned int) mi.arena);
4701 fprintf (stderr, "in use bytes = %10u\n", (unsigned int) mi.uordblks);
4702 #if MALLOC_DEBUG > 1
4703 if (i > 0)
4704 dump_heap (heap_for_ptr (top (ar_ptr)));
4705 #endif
4706 system_b += mi.arena;
4707 in_use_b += mi.uordblks;
4708 (void) mutex_unlock (&ar_ptr->mutex);
4709 ar_ptr = ar_ptr->next;
4710 if (ar_ptr == &main_arena)
4711 break;
4713 fprintf (stderr, "Total (incl. mmap):\n");
4714 fprintf (stderr, "system bytes = %10u\n", system_b);
4715 fprintf (stderr, "in use bytes = %10u\n", in_use_b);
4716 fprintf (stderr, "max mmap regions = %10u\n", (unsigned int) mp_.max_n_mmaps);
4717 fprintf (stderr, "max mmap bytes = %10lu\n",
4718 (unsigned long) mp_.max_mmapped_mem);
4719 ((_IO_FILE *) stderr)->_flags2 |= old_flags2;
4720 _IO_funlockfile (stderr);
4725 ------------------------------ mallopt ------------------------------
4729 __libc_mallopt (int param_number, int value)
4731 mstate av = &main_arena;
4732 int res = 1;
4734 if (__malloc_initialized < 0)
4735 ptmalloc_init ();
4736 (void) mutex_lock (&av->mutex);
4737 /* Ensure initialization/consolidation */
4738 malloc_consolidate (av);
4740 LIBC_PROBE (memory_mallopt, 2, param_number, value);
4742 switch (param_number)
4744 case M_MXFAST:
4745 if (value >= 0 && value <= MAX_FAST_SIZE)
4747 LIBC_PROBE (memory_mallopt_mxfast, 2, value, get_max_fast ());
4748 set_max_fast (value);
4750 else
4751 res = 0;
4752 break;
4754 case M_TRIM_THRESHOLD:
4755 LIBC_PROBE (memory_mallopt_trim_threshold, 3, value,
4756 mp_.trim_threshold, mp_.no_dyn_threshold);
4757 mp_.trim_threshold = value;
4758 mp_.no_dyn_threshold = 1;
4759 break;
4761 case M_TOP_PAD:
4762 LIBC_PROBE (memory_mallopt_top_pad, 3, value,
4763 mp_.top_pad, mp_.no_dyn_threshold);
4764 mp_.top_pad = value;
4765 mp_.no_dyn_threshold = 1;
4766 break;
4768 case M_MMAP_THRESHOLD:
4769 /* Forbid setting the threshold too high. */
4770 if ((unsigned long) value > HEAP_MAX_SIZE / 2)
4771 res = 0;
4772 else
4774 LIBC_PROBE (memory_mallopt_mmap_threshold, 3, value,
4775 mp_.mmap_threshold, mp_.no_dyn_threshold);
4776 mp_.mmap_threshold = value;
4777 mp_.no_dyn_threshold = 1;
4779 break;
4781 case M_MMAP_MAX:
4782 LIBC_PROBE (memory_mallopt_mmap_max, 3, value,
4783 mp_.n_mmaps_max, mp_.no_dyn_threshold);
4784 mp_.n_mmaps_max = value;
4785 mp_.no_dyn_threshold = 1;
4786 break;
4788 case M_CHECK_ACTION:
4789 LIBC_PROBE (memory_mallopt_check_action, 2, value, check_action);
4790 check_action = value;
4791 break;
4793 case M_PERTURB:
4794 LIBC_PROBE (memory_mallopt_perturb, 2, value, perturb_byte);
4795 perturb_byte = value;
4796 break;
4798 case M_ARENA_TEST:
4799 if (value > 0)
4801 LIBC_PROBE (memory_mallopt_arena_test, 2, value, mp_.arena_test);
4802 mp_.arena_test = value;
4804 break;
4806 case M_ARENA_MAX:
4807 if (value > 0)
4809 LIBC_PROBE (memory_mallopt_arena_max, 2, value, mp_.arena_max);
4810 mp_.arena_max = value;
4812 break;
4814 (void) mutex_unlock (&av->mutex);
4815 return res;
4817 libc_hidden_def (__libc_mallopt)
4821 -------------------- Alternative MORECORE functions --------------------
4826 General Requirements for MORECORE.
4828 The MORECORE function must have the following properties:
4830 If MORECORE_CONTIGUOUS is false:
4832 * MORECORE must allocate in multiples of pagesize. It will
4833 only be called with arguments that are multiples of pagesize.
4835 * MORECORE(0) must return an address that is at least
4836 MALLOC_ALIGNMENT aligned. (Page-aligning always suffices.)
4838 else (i.e. If MORECORE_CONTIGUOUS is true):
4840 * Consecutive calls to MORECORE with positive arguments
4841 return increasing addresses, indicating that space has been
4842 contiguously extended.
4844 * MORECORE need not allocate in multiples of pagesize.
4845 Calls to MORECORE need not have args of multiples of pagesize.
4847 * MORECORE need not page-align.
4849 In either case:
4851 * MORECORE may allocate more memory than requested. (Or even less,
4852 but this will generally result in a malloc failure.)
4854 * MORECORE must not allocate memory when given argument zero, but
4855 instead return one past the end address of memory from previous
4856 nonzero call. This malloc does NOT call MORECORE(0)
4857 until at least one call with positive arguments is made, so
4858 the initial value returned is not important.
4860 * Even though consecutive calls to MORECORE need not return contiguous
4861 addresses, it must be OK for malloc'ed chunks to span multiple
4862 regions in those cases where they do happen to be contiguous.
4864 * MORECORE need not handle negative arguments -- it may instead
4865 just return MORECORE_FAILURE when given negative arguments.
4866 Negative arguments are always multiples of pagesize. MORECORE
4867 must not misinterpret negative args as large positive unsigned
4868 args. You can suppress all such calls from even occurring by defining
4869 MORECORE_CANNOT_TRIM,
4871 There is some variation across systems about the type of the
4872 argument to sbrk/MORECORE. If size_t is unsigned, then it cannot
4873 actually be size_t, because sbrk supports negative args, so it is
4874 normally the signed type of the same width as size_t (sometimes
4875 declared as "intptr_t", and sometimes "ptrdiff_t"). It doesn't much
4876 matter though. Internally, we use "long" as arguments, which should
4877 work across all reasonable possibilities.
4879 Additionally, if MORECORE ever returns failure for a positive
4880 request, then mmap is used as a noncontiguous system allocator. This
4881 is a useful backup strategy for systems with holes in address spaces
4882 -- in this case sbrk cannot contiguously expand the heap, but mmap
4883 may be able to map noncontiguous space.
4885 If you'd like mmap to ALWAYS be used, you can define MORECORE to be
4886 a function that always returns MORECORE_FAILURE.
4888 If you are using this malloc with something other than sbrk (or its
4889 emulation) to supply memory regions, you probably want to set
4890 MORECORE_CONTIGUOUS as false. As an example, here is a custom
4891 allocator kindly contributed for pre-OSX macOS. It uses virtually
4892 but not necessarily physically contiguous non-paged memory (locked
4893 in, present and won't get swapped out). You can use it by
4894 uncommenting this section, adding some #includes, and setting up the
4895 appropriate defines above:
4897 *#define MORECORE osMoreCore
4898 *#define MORECORE_CONTIGUOUS 0
4900 There is also a shutdown routine that should somehow be called for
4901 cleanup upon program exit.
4903 *#define MAX_POOL_ENTRIES 100
4904 *#define MINIMUM_MORECORE_SIZE (64 * 1024)
4905 static int next_os_pool;
4906 void *our_os_pools[MAX_POOL_ENTRIES];
4908 void *osMoreCore(int size)
4910 void *ptr = 0;
4911 static void *sbrk_top = 0;
4913 if (size > 0)
4915 if (size < MINIMUM_MORECORE_SIZE)
4916 size = MINIMUM_MORECORE_SIZE;
4917 if (CurrentExecutionLevel() == kTaskLevel)
4918 ptr = PoolAllocateResident(size + RM_PAGE_SIZE, 0);
4919 if (ptr == 0)
4921 return (void *) MORECORE_FAILURE;
4923 // save ptrs so they can be freed during cleanup
4924 our_os_pools[next_os_pool] = ptr;
4925 next_os_pool++;
4926 ptr = (void *) ((((unsigned long) ptr) + RM_PAGE_MASK) & ~RM_PAGE_MASK);
4927 sbrk_top = (char *) ptr + size;
4928 return ptr;
4930 else if (size < 0)
4932 // we don't currently support shrink behavior
4933 return (void *) MORECORE_FAILURE;
4935 else
4937 return sbrk_top;
4941 // cleanup any allocated memory pools
4942 // called as last thing before shutting down driver
4944 void osCleanupMem(void)
4946 void **ptr;
4948 for (ptr = our_os_pools; ptr < &our_os_pools[MAX_POOL_ENTRIES]; ptr++)
4949 if (*ptr)
4951 PoolDeallocate(*ptr);
4952 * ptr = 0;
4959 /* Helper code. */
4961 extern char **__libc_argv attribute_hidden;
4963 static void
4964 malloc_printerr (int action, const char *str, void *ptr, mstate ar_ptr)
4966 /* Avoid using this arena in future. We do not attempt to synchronize this
4967 with anything else because we minimally want to ensure that __libc_message
4968 gets its resources safely without stumbling on the current corruption. */
4969 if (ar_ptr)
4970 set_arena_corrupt (ar_ptr);
4972 if ((action & 5) == 5)
4973 __libc_message (action & 2, "%s\n", str);
4974 else if (action & 1)
4976 char buf[2 * sizeof (uintptr_t) + 1];
4978 buf[sizeof (buf) - 1] = '\0';
4979 char *cp = _itoa_word ((uintptr_t) ptr, &buf[sizeof (buf) - 1], 16, 0);
4980 while (cp > buf)
4981 *--cp = '0';
4983 __libc_message (action & 2, "*** Error in `%s': %s: 0x%s ***\n",
4984 __libc_argv[0] ? : "<unknown>", str, cp);
4986 else if (action & 2)
4987 abort ();
4990 /* We need a wrapper function for one of the additions of POSIX. */
4992 __posix_memalign (void **memptr, size_t alignment, size_t size)
4994 void *mem;
4996 /* Test whether the SIZE argument is valid. It must be a power of
4997 two multiple of sizeof (void *). */
4998 if (alignment % sizeof (void *) != 0
4999 || !powerof2 (alignment / sizeof (void *))
5000 || alignment == 0)
5001 return EINVAL;
5004 void *address = RETURN_ADDRESS (0);
5005 mem = _mid_memalign (alignment, size, address);
5007 if (mem != NULL)
5009 *memptr = mem;
5010 return 0;
5013 return ENOMEM;
5015 weak_alias (__posix_memalign, posix_memalign)
5019 __malloc_info (int options, FILE *fp)
5021 /* For now, at least. */
5022 if (options != 0)
5023 return EINVAL;
5025 int n = 0;
5026 size_t total_nblocks = 0;
5027 size_t total_nfastblocks = 0;
5028 size_t total_avail = 0;
5029 size_t total_fastavail = 0;
5030 size_t total_system = 0;
5031 size_t total_max_system = 0;
5032 size_t total_aspace = 0;
5033 size_t total_aspace_mprotect = 0;
5037 if (__malloc_initialized < 0)
5038 ptmalloc_init ();
5040 fputs ("<malloc version=\"1\">\n", fp);
5042 /* Iterate over all arenas currently in use. */
5043 mstate ar_ptr = &main_arena;
5046 fprintf (fp, "<heap nr=\"%d\">\n<sizes>\n", n++);
5048 size_t nblocks = 0;
5049 size_t nfastblocks = 0;
5050 size_t avail = 0;
5051 size_t fastavail = 0;
5052 struct
5054 size_t from;
5055 size_t to;
5056 size_t total;
5057 size_t count;
5058 } sizes[NFASTBINS + NBINS - 1];
5059 #define nsizes (sizeof (sizes) / sizeof (sizes[0]))
5061 mutex_lock (&ar_ptr->mutex);
5063 for (size_t i = 0; i < NFASTBINS; ++i)
5065 mchunkptr p = fastbin (ar_ptr, i);
5066 if (p != NULL)
5068 size_t nthissize = 0;
5069 size_t thissize = chunksize (p);
5071 while (p != NULL)
5073 ++nthissize;
5074 p = p->fd;
5077 fastavail += nthissize * thissize;
5078 nfastblocks += nthissize;
5079 sizes[i].from = thissize - (MALLOC_ALIGNMENT - 1);
5080 sizes[i].to = thissize;
5081 sizes[i].count = nthissize;
5083 else
5084 sizes[i].from = sizes[i].to = sizes[i].count = 0;
5086 sizes[i].total = sizes[i].count * sizes[i].to;
5090 mbinptr bin;
5091 struct malloc_chunk *r;
5093 for (size_t i = 1; i < NBINS; ++i)
5095 bin = bin_at (ar_ptr, i);
5096 r = bin->fd;
5097 sizes[NFASTBINS - 1 + i].from = ~((size_t) 0);
5098 sizes[NFASTBINS - 1 + i].to = sizes[NFASTBINS - 1 + i].total
5099 = sizes[NFASTBINS - 1 + i].count = 0;
5101 if (r != NULL)
5102 while (r != bin)
5104 ++sizes[NFASTBINS - 1 + i].count;
5105 sizes[NFASTBINS - 1 + i].total += r->size;
5106 sizes[NFASTBINS - 1 + i].from
5107 = MIN (sizes[NFASTBINS - 1 + i].from, r->size);
5108 sizes[NFASTBINS - 1 + i].to = MAX (sizes[NFASTBINS - 1 + i].to,
5109 r->size);
5111 r = r->fd;
5114 if (sizes[NFASTBINS - 1 + i].count == 0)
5115 sizes[NFASTBINS - 1 + i].from = 0;
5116 nblocks += sizes[NFASTBINS - 1 + i].count;
5117 avail += sizes[NFASTBINS - 1 + i].total;
5120 mutex_unlock (&ar_ptr->mutex);
5122 total_nfastblocks += nfastblocks;
5123 total_fastavail += fastavail;
5125 total_nblocks += nblocks;
5126 total_avail += avail;
5128 for (size_t i = 0; i < nsizes; ++i)
5129 if (sizes[i].count != 0 && i != NFASTBINS)
5130 fprintf (fp, " \
5131 <size from=\"%zu\" to=\"%zu\" total=\"%zu\" count=\"%zu\"/>\n",
5132 sizes[i].from, sizes[i].to, sizes[i].total, sizes[i].count);
5134 if (sizes[NFASTBINS].count != 0)
5135 fprintf (fp, "\
5136 <unsorted from=\"%zu\" to=\"%zu\" total=\"%zu\" count=\"%zu\"/>\n",
5137 sizes[NFASTBINS].from, sizes[NFASTBINS].to,
5138 sizes[NFASTBINS].total, sizes[NFASTBINS].count);
5140 total_system += ar_ptr->system_mem;
5141 total_max_system += ar_ptr->max_system_mem;
5143 fprintf (fp,
5144 "</sizes>\n<total type=\"fast\" count=\"%zu\" size=\"%zu\"/>\n"
5145 "<total type=\"rest\" count=\"%zu\" size=\"%zu\"/>\n"
5146 "<system type=\"current\" size=\"%zu\"/>\n"
5147 "<system type=\"max\" size=\"%zu\"/>\n",
5148 nfastblocks, fastavail, nblocks, avail,
5149 ar_ptr->system_mem, ar_ptr->max_system_mem);
5151 if (ar_ptr != &main_arena)
5153 heap_info *heap = heap_for_ptr (top (ar_ptr));
5154 fprintf (fp,
5155 "<aspace type=\"total\" size=\"%zu\"/>\n"
5156 "<aspace type=\"mprotect\" size=\"%zu\"/>\n",
5157 heap->size, heap->mprotect_size);
5158 total_aspace += heap->size;
5159 total_aspace_mprotect += heap->mprotect_size;
5161 else
5163 fprintf (fp,
5164 "<aspace type=\"total\" size=\"%zu\"/>\n"
5165 "<aspace type=\"mprotect\" size=\"%zu\"/>\n",
5166 ar_ptr->system_mem, ar_ptr->system_mem);
5167 total_aspace += ar_ptr->system_mem;
5168 total_aspace_mprotect += ar_ptr->system_mem;
5171 fputs ("</heap>\n", fp);
5172 ar_ptr = ar_ptr->next;
5174 while (ar_ptr != &main_arena);
5176 fprintf (fp,
5177 "<total type=\"fast\" count=\"%zu\" size=\"%zu\"/>\n"
5178 "<total type=\"rest\" count=\"%zu\" size=\"%zu\"/>\n"
5179 "<total type=\"mmap\" count=\"%d\" size=\"%zu\"/>\n"
5180 "<system type=\"current\" size=\"%zu\"/>\n"
5181 "<system type=\"max\" size=\"%zu\"/>\n"
5182 "<aspace type=\"total\" size=\"%zu\"/>\n"
5183 "<aspace type=\"mprotect\" size=\"%zu\"/>\n"
5184 "</malloc>\n",
5185 total_nfastblocks, total_fastavail, total_nblocks, total_avail,
5186 mp_.n_mmaps, mp_.mmapped_mem,
5187 total_system, total_max_system,
5188 total_aspace, total_aspace_mprotect);
5190 return 0;
5192 weak_alias (__malloc_info, malloc_info)
5195 strong_alias (__libc_calloc, __calloc) weak_alias (__libc_calloc, calloc)
5196 strong_alias (__libc_free, __cfree) weak_alias (__libc_free, cfree)
5197 strong_alias (__libc_free, __free) strong_alias (__libc_free, free)
5198 strong_alias (__libc_malloc, __malloc) strong_alias (__libc_malloc, malloc)
5199 strong_alias (__libc_memalign, __memalign)
5200 weak_alias (__libc_memalign, memalign)
5201 strong_alias (__libc_realloc, __realloc) strong_alias (__libc_realloc, realloc)
5202 strong_alias (__libc_valloc, __valloc) weak_alias (__libc_valloc, valloc)
5203 strong_alias (__libc_pvalloc, __pvalloc) weak_alias (__libc_pvalloc, pvalloc)
5204 strong_alias (__libc_mallinfo, __mallinfo)
5205 weak_alias (__libc_mallinfo, mallinfo)
5206 strong_alias (__libc_mallopt, __mallopt) weak_alias (__libc_mallopt, mallopt)
5208 weak_alias (__malloc_stats, malloc_stats)
5209 weak_alias (__malloc_usable_size, malloc_usable_size)
5210 weak_alias (__malloc_trim, malloc_trim)
5211 weak_alias (__malloc_get_state, malloc_get_state)
5212 weak_alias (__malloc_set_state, malloc_set_state)
5215 /* ------------------------------------------------------------
5216 History:
5218 [see ftp://g.oswego.edu/pub/misc/malloc.c for the history of dlmalloc]
5222 * Local variables:
5223 * c-basic-offset: 2
5224 * End: