Further harden glibc malloc metadata against 1-byte overflows.
[glibc.git] / malloc / malloc.c
blob994a23248e258501979138f3b07785045a60e69f
1 /* Malloc implementation for multiple threads without lock contention.
2 Copyright (C) 1996-2017 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-pointer-arith.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 mchunk_prev_size; /* Size of previous chunk (if free). */
1044 INTERNAL_SIZE_T mchunk_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 unallocated (P clear) |
1074 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1075 | Size of chunk, in bytes |A|M|P|
1076 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1077 | User data starts here... .
1079 . (malloc_usable_size() bytes) .
1081 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1082 | (size of chunk, but used for application data) |
1083 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1084 | Size of next chunk, in bytes |A|0|1|
1085 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1087 Where "chunk" is the front of the chunk for the purpose of most of
1088 the malloc code, but "mem" is the pointer that is returned to the
1089 user. "Nextchunk" is the beginning of the next contiguous chunk.
1091 Chunks always begin on even word boundaries, so the mem portion
1092 (which is returned to the user) is also on an even word boundary, and
1093 thus at least double-word aligned.
1095 Free chunks are stored in circular doubly-linked lists, and look like this:
1097 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1098 | Size of previous chunk, if unallocated (P clear) |
1099 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1100 `head:' | Size of chunk, in bytes |A|0|P|
1101 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1102 | Forward pointer to next chunk in list |
1103 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1104 | Back pointer to previous chunk in list |
1105 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1106 | Unused space (may be 0 bytes long) .
1109 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1110 `foot:' | Size of chunk, in bytes |
1111 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1112 | Size of next chunk, in bytes |A|0|0|
1113 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1115 The P (PREV_INUSE) bit, stored in the unused low-order bit of the
1116 chunk size (which is always a multiple of two words), is an in-use
1117 bit for the *previous* chunk. If that bit is *clear*, then the
1118 word before the current chunk size contains the previous chunk
1119 size, and can be used to find the front of the previous chunk.
1120 The very first chunk allocated always has this bit set,
1121 preventing access to non-existent (or non-owned) memory. If
1122 prev_inuse is set for any given chunk, then you CANNOT determine
1123 the size of the previous chunk, and might even get a memory
1124 addressing fault when trying to do so.
1126 The A (NON_MAIN_ARENA) bit is cleared for chunks on the initial,
1127 main arena, described by the main_arena variable. When additional
1128 threads are spawned, each thread receives its own arena (up to a
1129 configurable limit, after which arenas are reused for multiple
1130 threads), and the chunks in these arenas have the A bit set. To
1131 find the arena for a chunk on such a non-main arena, heap_for_ptr
1132 performs a bit mask operation and indirection through the ar_ptr
1133 member of the per-heap header heap_info (see arena.c).
1135 Note that the `foot' of the current chunk is actually represented
1136 as the prev_size of the NEXT chunk. This makes it easier to
1137 deal with alignments etc but can be very confusing when trying
1138 to extend or adapt this code.
1140 The three exceptions to all this are:
1142 1. The special chunk `top' doesn't bother using the
1143 trailing size field since there is no next contiguous chunk
1144 that would have to index off it. After initialization, `top'
1145 is forced to always exist. If it would become less than
1146 MINSIZE bytes long, it is replenished.
1148 2. Chunks allocated via mmap, which have the second-lowest-order
1149 bit M (IS_MMAPPED) set in their size fields. Because they are
1150 allocated one-by-one, each must contain its own trailing size
1151 field. If the M bit is set, the other bits are ignored
1152 (because mmapped chunks are neither in an arena, nor adjacent
1153 to a freed chunk). The M bit is also used for chunks which
1154 originally came from a dumped heap via malloc_set_state in
1155 hooks.c.
1157 3. Chunks in fastbins are treated as allocated chunks from the
1158 point of view of the chunk allocator. They are consolidated
1159 with their neighbors only in bulk, in malloc_consolidate.
1163 ---------- Size and alignment checks and conversions ----------
1166 /* conversion from malloc headers to user pointers, and back */
1168 #define chunk2mem(p) ((void*)((char*)(p) + 2*SIZE_SZ))
1169 #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))
1171 /* The smallest possible chunk */
1172 #define MIN_CHUNK_SIZE (offsetof(struct malloc_chunk, fd_nextsize))
1174 /* The smallest size we can malloc is an aligned minimal chunk */
1176 #define MINSIZE \
1177 (unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))
1179 /* Check if m has acceptable alignment */
1181 #define aligned_OK(m) (((unsigned long)(m) & MALLOC_ALIGN_MASK) == 0)
1183 #define misaligned_chunk(p) \
1184 ((uintptr_t)(MALLOC_ALIGNMENT == 2 * SIZE_SZ ? (p) : chunk2mem (p)) \
1185 & MALLOC_ALIGN_MASK)
1189 Check if a request is so large that it would wrap around zero when
1190 padded and aligned. To simplify some other code, the bound is made
1191 low enough so that adding MINSIZE will also not wrap around zero.
1194 #define REQUEST_OUT_OF_RANGE(req) \
1195 ((unsigned long) (req) >= \
1196 (unsigned long) (INTERNAL_SIZE_T) (-2 * MINSIZE))
1198 /* pad request bytes into a usable size -- internal version */
1200 #define request2size(req) \
1201 (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ? \
1202 MINSIZE : \
1203 ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
1205 /* Same, except also perform argument check */
1207 #define checked_request2size(req, sz) \
1208 if (REQUEST_OUT_OF_RANGE (req)) { \
1209 __set_errno (ENOMEM); \
1210 return 0; \
1212 (sz) = request2size (req);
1215 --------------- Physical chunk operations ---------------
1219 /* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
1220 #define PREV_INUSE 0x1
1222 /* extract inuse bit of previous chunk */
1223 #define prev_inuse(p) ((p)->mchunk_size & PREV_INUSE)
1226 /* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */
1227 #define IS_MMAPPED 0x2
1229 /* check for mmap()'ed chunk */
1230 #define chunk_is_mmapped(p) ((p)->mchunk_size & IS_MMAPPED)
1233 /* size field is or'ed with NON_MAIN_ARENA if the chunk was obtained
1234 from a non-main arena. This is only set immediately before handing
1235 the chunk to the user, if necessary. */
1236 #define NON_MAIN_ARENA 0x4
1238 /* Check for chunk from main arena. */
1239 #define chunk_main_arena(p) (((p)->mchunk_size & NON_MAIN_ARENA) == 0)
1241 /* Mark a chunk as not being on the main arena. */
1242 #define set_non_main_arena(p) ((p)->mchunk_size |= NON_MAIN_ARENA)
1246 Bits to mask off when extracting size
1248 Note: IS_MMAPPED is intentionally not masked off from size field in
1249 macros for which mmapped chunks should never be seen. This should
1250 cause helpful core dumps to occur if it is tried by accident by
1251 people extending or adapting this malloc.
1253 #define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
1255 /* Get size, ignoring use bits */
1256 #define chunksize(p) (chunksize_nomask (p) & ~(SIZE_BITS))
1258 /* Like chunksize, but do not mask SIZE_BITS. */
1259 #define chunksize_nomask(p) ((p)->mchunk_size)
1261 /* Ptr to next physical malloc_chunk. */
1262 #define next_chunk(p) ((mchunkptr) (((char *) (p)) + chunksize (p)))
1264 /* Size of the chunk below P. Only valid if prev_inuse (P). */
1265 #define prev_size(p) ((p)->mchunk_prev_size)
1267 /* Set the size of the chunk below P. Only valid if prev_inuse (P). */
1268 #define set_prev_size(p, sz) ((p)->mchunk_prev_size = (sz))
1270 /* Ptr to previous physical malloc_chunk. Only valid if prev_inuse (P). */
1271 #define prev_chunk(p) ((mchunkptr) (((char *) (p)) - prev_size (p)))
1273 /* Treat space at ptr + offset as a chunk */
1274 #define chunk_at_offset(p, s) ((mchunkptr) (((char *) (p)) + (s)))
1276 /* extract p's inuse bit */
1277 #define inuse(p) \
1278 ((((mchunkptr) (((char *) (p)) + chunksize (p)))->mchunk_size) & PREV_INUSE)
1280 /* set/clear chunk as being inuse without otherwise disturbing */
1281 #define set_inuse(p) \
1282 ((mchunkptr) (((char *) (p)) + chunksize (p)))->mchunk_size |= PREV_INUSE
1284 #define clear_inuse(p) \
1285 ((mchunkptr) (((char *) (p)) + chunksize (p)))->mchunk_size &= ~(PREV_INUSE)
1288 /* check/set/clear inuse bits in known places */
1289 #define inuse_bit_at_offset(p, s) \
1290 (((mchunkptr) (((char *) (p)) + (s)))->mchunk_size & PREV_INUSE)
1292 #define set_inuse_bit_at_offset(p, s) \
1293 (((mchunkptr) (((char *) (p)) + (s)))->mchunk_size |= PREV_INUSE)
1295 #define clear_inuse_bit_at_offset(p, s) \
1296 (((mchunkptr) (((char *) (p)) + (s)))->mchunk_size &= ~(PREV_INUSE))
1299 /* Set size at head, without disturbing its use bit */
1300 #define set_head_size(p, s) ((p)->mchunk_size = (((p)->mchunk_size & SIZE_BITS) | (s)))
1302 /* Set size/use field */
1303 #define set_head(p, s) ((p)->mchunk_size = (s))
1305 /* Set size at footer (only when chunk is not in use) */
1306 #define set_foot(p, s) (((mchunkptr) ((char *) (p) + (s)))->mchunk_prev_size = (s))
1309 #pragma GCC poison mchunk_size
1310 #pragma GCC poison mchunk_prev_size
1313 -------------------- Internal data structures --------------------
1315 All internal state is held in an instance of malloc_state defined
1316 below. There are no other static variables, except in two optional
1317 cases:
1318 * If USE_MALLOC_LOCK is defined, the mALLOC_MUTEx declared above.
1319 * If mmap doesn't support MAP_ANONYMOUS, a dummy file descriptor
1320 for mmap.
1322 Beware of lots of tricks that minimize the total bookkeeping space
1323 requirements. The result is a little over 1K bytes (for 4byte
1324 pointers and size_t.)
1328 Bins
1330 An array of bin headers for free chunks. Each bin is doubly
1331 linked. The bins are approximately proportionally (log) spaced.
1332 There are a lot of these bins (128). This may look excessive, but
1333 works very well in practice. Most bins hold sizes that are
1334 unusual as malloc request sizes, but are more usual for fragments
1335 and consolidated sets of chunks, which is what these bins hold, so
1336 they can be found quickly. All procedures maintain the invariant
1337 that no consolidated chunk physically borders another one, so each
1338 chunk in a list is known to be preceeded and followed by either
1339 inuse chunks or the ends of memory.
1341 Chunks in bins are kept in size order, with ties going to the
1342 approximately least recently used chunk. Ordering isn't needed
1343 for the small bins, which all contain the same-sized chunks, but
1344 facilitates best-fit allocation for larger chunks. These lists
1345 are just sequential. Keeping them in order almost never requires
1346 enough traversal to warrant using fancier ordered data
1347 structures.
1349 Chunks of the same size are linked with the most
1350 recently freed at the front, and allocations are taken from the
1351 back. This results in LRU (FIFO) allocation order, which tends
1352 to give each chunk an equal opportunity to be consolidated with
1353 adjacent freed chunks, resulting in larger free chunks and less
1354 fragmentation.
1356 To simplify use in double-linked lists, each bin header acts
1357 as a malloc_chunk. This avoids special-casing for headers.
1358 But to conserve space and improve locality, we allocate
1359 only the fd/bk pointers of bins, and then use repositioning tricks
1360 to treat these as the fields of a malloc_chunk*.
1363 typedef struct malloc_chunk *mbinptr;
1365 /* addressing -- note that bin_at(0) does not exist */
1366 #define bin_at(m, i) \
1367 (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2])) \
1368 - offsetof (struct malloc_chunk, fd))
1370 /* analog of ++bin */
1371 #define next_bin(b) ((mbinptr) ((char *) (b) + (sizeof (mchunkptr) << 1)))
1373 /* Reminders about list directionality within bins */
1374 #define first(b) ((b)->fd)
1375 #define last(b) ((b)->bk)
1377 /* Take a chunk off a bin list */
1378 #define unlink(AV, P, BK, FD) { \
1379 if (__builtin_expect (chunksize(P) != prev_size (next_chunk(P)), 0)) \
1380 malloc_printerr (check_action, "corrupted size vs. prev_size", P, AV); \
1381 FD = P->fd; \
1382 BK = P->bk; \
1383 if (__builtin_expect (FD->bk != P || BK->fd != P, 0)) \
1384 malloc_printerr (check_action, "corrupted double-linked list", P, AV); \
1385 else { \
1386 FD->bk = BK; \
1387 BK->fd = FD; \
1388 if (!in_smallbin_range (chunksize_nomask (P)) \
1389 && __builtin_expect (P->fd_nextsize != NULL, 0)) { \
1390 if (__builtin_expect (P->fd_nextsize->bk_nextsize != P, 0) \
1391 || __builtin_expect (P->bk_nextsize->fd_nextsize != P, 0)) \
1392 malloc_printerr (check_action, \
1393 "corrupted double-linked list (not small)", \
1394 P, AV); \
1395 if (FD->fd_nextsize == NULL) { \
1396 if (P->fd_nextsize == P) \
1397 FD->fd_nextsize = FD->bk_nextsize = FD; \
1398 else { \
1399 FD->fd_nextsize = P->fd_nextsize; \
1400 FD->bk_nextsize = P->bk_nextsize; \
1401 P->fd_nextsize->bk_nextsize = FD; \
1402 P->bk_nextsize->fd_nextsize = FD; \
1404 } else { \
1405 P->fd_nextsize->bk_nextsize = P->bk_nextsize; \
1406 P->bk_nextsize->fd_nextsize = P->fd_nextsize; \
1413 Indexing
1415 Bins for sizes < 512 bytes contain chunks of all the same size, spaced
1416 8 bytes apart. Larger bins are approximately logarithmically spaced:
1418 64 bins of size 8
1419 32 bins of size 64
1420 16 bins of size 512
1421 8 bins of size 4096
1422 4 bins of size 32768
1423 2 bins of size 262144
1424 1 bin of size what's left
1426 There is actually a little bit of slop in the numbers in bin_index
1427 for the sake of speed. This makes no difference elsewhere.
1429 The bins top out around 1MB because we expect to service large
1430 requests via mmap.
1432 Bin 0 does not exist. Bin 1 is the unordered list; if that would be
1433 a valid chunk size the small bins are bumped up one.
1436 #define NBINS 128
1437 #define NSMALLBINS 64
1438 #define SMALLBIN_WIDTH MALLOC_ALIGNMENT
1439 #define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ)
1440 #define MIN_LARGE_SIZE ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)
1442 #define in_smallbin_range(sz) \
1443 ((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)
1445 #define smallbin_index(sz) \
1446 ((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\
1447 + SMALLBIN_CORRECTION)
1449 #define largebin_index_32(sz) \
1450 (((((unsigned long) (sz)) >> 6) <= 38) ? 56 + (((unsigned long) (sz)) >> 6) :\
1451 ((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :\
1452 ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
1453 ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
1454 ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
1455 126)
1457 #define largebin_index_32_big(sz) \
1458 (((((unsigned long) (sz)) >> 6) <= 45) ? 49 + (((unsigned long) (sz)) >> 6) :\
1459 ((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :\
1460 ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
1461 ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
1462 ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
1463 126)
1465 // XXX It remains to be seen whether it is good to keep the widths of
1466 // XXX the buckets the same or whether it should be scaled by a factor
1467 // XXX of two as well.
1468 #define largebin_index_64(sz) \
1469 (((((unsigned long) (sz)) >> 6) <= 48) ? 48 + (((unsigned long) (sz)) >> 6) :\
1470 ((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :\
1471 ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
1472 ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
1473 ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
1474 126)
1476 #define largebin_index(sz) \
1477 (SIZE_SZ == 8 ? largebin_index_64 (sz) \
1478 : MALLOC_ALIGNMENT == 16 ? largebin_index_32_big (sz) \
1479 : largebin_index_32 (sz))
1481 #define bin_index(sz) \
1482 ((in_smallbin_range (sz)) ? smallbin_index (sz) : largebin_index (sz))
1486 Unsorted chunks
1488 All remainders from chunk splits, as well as all returned chunks,
1489 are first placed in the "unsorted" bin. They are then placed
1490 in regular bins after malloc gives them ONE chance to be used before
1491 binning. So, basically, the unsorted_chunks list acts as a queue,
1492 with chunks being placed on it in free (and malloc_consolidate),
1493 and taken off (to be either used or placed in bins) in malloc.
1495 The NON_MAIN_ARENA flag is never set for unsorted chunks, so it
1496 does not have to be taken into account in size comparisons.
1499 /* The otherwise unindexable 1-bin is used to hold unsorted chunks. */
1500 #define unsorted_chunks(M) (bin_at (M, 1))
1505 The top-most available chunk (i.e., the one bordering the end of
1506 available memory) is treated specially. It is never included in
1507 any bin, is used only if no other chunk is available, and is
1508 released back to the system if it is very large (see
1509 M_TRIM_THRESHOLD). Because top initially
1510 points to its own bin with initial zero size, thus forcing
1511 extension on the first malloc request, we avoid having any special
1512 code in malloc to check whether it even exists yet. But we still
1513 need to do so when getting memory from system, so we make
1514 initial_top treat the bin as a legal but unusable chunk during the
1515 interval between initialization and the first call to
1516 sysmalloc. (This is somewhat delicate, since it relies on
1517 the 2 preceding words to be zero during this interval as well.)
1520 /* Conveniently, the unsorted bin can be used as dummy top on first call */
1521 #define initial_top(M) (unsorted_chunks (M))
1524 Binmap
1526 To help compensate for the large number of bins, a one-level index
1527 structure is used for bin-by-bin searching. `binmap' is a
1528 bitvector recording whether bins are definitely empty so they can
1529 be skipped over during during traversals. The bits are NOT always
1530 cleared as soon as bins are empty, but instead only
1531 when they are noticed to be empty during traversal in malloc.
1534 /* Conservatively use 32 bits per map word, even if on 64bit system */
1535 #define BINMAPSHIFT 5
1536 #define BITSPERMAP (1U << BINMAPSHIFT)
1537 #define BINMAPSIZE (NBINS / BITSPERMAP)
1539 #define idx2block(i) ((i) >> BINMAPSHIFT)
1540 #define idx2bit(i) ((1U << ((i) & ((1U << BINMAPSHIFT) - 1))))
1542 #define mark_bin(m, i) ((m)->binmap[idx2block (i)] |= idx2bit (i))
1543 #define unmark_bin(m, i) ((m)->binmap[idx2block (i)] &= ~(idx2bit (i)))
1544 #define get_binmap(m, i) ((m)->binmap[idx2block (i)] & idx2bit (i))
1547 Fastbins
1549 An array of lists holding recently freed small chunks. Fastbins
1550 are not doubly linked. It is faster to single-link them, and
1551 since chunks are never removed from the middles of these lists,
1552 double linking is not necessary. Also, unlike regular bins, they
1553 are not even processed in FIFO order (they use faster LIFO) since
1554 ordering doesn't much matter in the transient contexts in which
1555 fastbins are normally used.
1557 Chunks in fastbins keep their inuse bit set, so they cannot
1558 be consolidated with other free chunks. malloc_consolidate
1559 releases all chunks in fastbins and consolidates them with
1560 other free chunks.
1563 typedef struct malloc_chunk *mfastbinptr;
1564 #define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])
1566 /* offset 2 to use otherwise unindexable first 2 bins */
1567 #define fastbin_index(sz) \
1568 ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)
1571 /* The maximum fastbin request size we support */
1572 #define MAX_FAST_SIZE (80 * SIZE_SZ / 4)
1574 #define NFASTBINS (fastbin_index (request2size (MAX_FAST_SIZE)) + 1)
1577 FASTBIN_CONSOLIDATION_THRESHOLD is the size of a chunk in free()
1578 that triggers automatic consolidation of possibly-surrounding
1579 fastbin chunks. This is a heuristic, so the exact value should not
1580 matter too much. It is defined at half the default trim threshold as a
1581 compromise heuristic to only attempt consolidation if it is likely
1582 to lead to trimming. However, it is not dynamically tunable, since
1583 consolidation reduces fragmentation surrounding large chunks even
1584 if trimming is not used.
1587 #define FASTBIN_CONSOLIDATION_THRESHOLD (65536UL)
1590 Since the lowest 2 bits in max_fast don't matter in size comparisons,
1591 they are used as flags.
1595 FASTCHUNKS_BIT held in max_fast indicates that there are probably
1596 some fastbin chunks. It is set true on entering a chunk into any
1597 fastbin, and cleared only in malloc_consolidate.
1599 The truth value is inverted so that have_fastchunks will be true
1600 upon startup (since statics are zero-filled), simplifying
1601 initialization checks.
1604 #define FASTCHUNKS_BIT (1U)
1606 #define have_fastchunks(M) (((M)->flags & FASTCHUNKS_BIT) == 0)
1607 #define clear_fastchunks(M) catomic_or (&(M)->flags, FASTCHUNKS_BIT)
1608 #define set_fastchunks(M) catomic_and (&(M)->flags, ~FASTCHUNKS_BIT)
1611 NONCONTIGUOUS_BIT indicates that MORECORE does not return contiguous
1612 regions. Otherwise, contiguity is exploited in merging together,
1613 when possible, results from consecutive MORECORE calls.
1615 The initial value comes from MORECORE_CONTIGUOUS, but is
1616 changed dynamically if mmap is ever used as an sbrk substitute.
1619 #define NONCONTIGUOUS_BIT (2U)
1621 #define contiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) == 0)
1622 #define noncontiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) != 0)
1623 #define set_noncontiguous(M) ((M)->flags |= NONCONTIGUOUS_BIT)
1624 #define set_contiguous(M) ((M)->flags &= ~NONCONTIGUOUS_BIT)
1626 /* ARENA_CORRUPTION_BIT is set if a memory corruption was detected on the
1627 arena. Such an arena is no longer used to allocate chunks. Chunks
1628 allocated in that arena before detecting corruption are not freed. */
1630 #define ARENA_CORRUPTION_BIT (4U)
1632 #define arena_is_corrupt(A) (((A)->flags & ARENA_CORRUPTION_BIT))
1633 #define set_arena_corrupt(A) ((A)->flags |= ARENA_CORRUPTION_BIT)
1636 Set value of max_fast.
1637 Use impossibly small value if 0.
1638 Precondition: there are no existing fastbin chunks.
1639 Setting the value clears fastchunk bit but preserves noncontiguous bit.
1642 #define set_max_fast(s) \
1643 global_max_fast = (((s) == 0) \
1644 ? SMALLBIN_WIDTH : ((s + SIZE_SZ) & ~MALLOC_ALIGN_MASK))
1645 #define get_max_fast() global_max_fast
1649 ----------- Internal state representation and initialization -----------
1652 struct malloc_state
1654 /* Serialize access. */
1655 __libc_lock_define (, mutex);
1657 /* Flags (formerly in max_fast). */
1658 int flags;
1660 /* Fastbins */
1661 mfastbinptr fastbinsY[NFASTBINS];
1663 /* Base of the topmost chunk -- not otherwise kept in a bin */
1664 mchunkptr top;
1666 /* The remainder from the most recent split of a small request */
1667 mchunkptr last_remainder;
1669 /* Normal bins packed as described above */
1670 mchunkptr bins[NBINS * 2 - 2];
1672 /* Bitmap of bins */
1673 unsigned int binmap[BINMAPSIZE];
1675 /* Linked list */
1676 struct malloc_state *next;
1678 /* Linked list for free arenas. Access to this field is serialized
1679 by free_list_lock in arena.c. */
1680 struct malloc_state *next_free;
1682 /* Number of threads attached to this arena. 0 if the arena is on
1683 the free list. Access to this field is serialized by
1684 free_list_lock in arena.c. */
1685 INTERNAL_SIZE_T attached_threads;
1687 /* Memory allocated from the system in this arena. */
1688 INTERNAL_SIZE_T system_mem;
1689 INTERNAL_SIZE_T max_system_mem;
1692 struct malloc_par
1694 /* Tunable parameters */
1695 unsigned long trim_threshold;
1696 INTERNAL_SIZE_T top_pad;
1697 INTERNAL_SIZE_T mmap_threshold;
1698 INTERNAL_SIZE_T arena_test;
1699 INTERNAL_SIZE_T arena_max;
1701 /* Memory map support */
1702 int n_mmaps;
1703 int n_mmaps_max;
1704 int max_n_mmaps;
1705 /* the mmap_threshold is dynamic, until the user sets
1706 it manually, at which point we need to disable any
1707 dynamic behavior. */
1708 int no_dyn_threshold;
1710 /* Statistics */
1711 INTERNAL_SIZE_T mmapped_mem;
1712 INTERNAL_SIZE_T max_mmapped_mem;
1714 /* First address handed out by MORECORE/sbrk. */
1715 char *sbrk_base;
1718 /* There are several instances of this struct ("arenas") in this
1719 malloc. If you are adapting this malloc in a way that does NOT use
1720 a static or mmapped malloc_state, you MUST explicitly zero-fill it
1721 before using. This malloc relies on the property that malloc_state
1722 is initialized to all zeroes (as is true of C statics). */
1724 static struct malloc_state main_arena =
1726 .mutex = _LIBC_LOCK_INITIALIZER,
1727 .next = &main_arena,
1728 .attached_threads = 1
1731 /* These variables are used for undumping support. Chunked are marked
1732 as using mmap, but we leave them alone if they fall into this
1733 range. NB: The chunk size for these chunks only includes the
1734 initial size field (of SIZE_SZ bytes), there is no trailing size
1735 field (unlike with regular mmapped chunks). */
1736 static mchunkptr dumped_main_arena_start; /* Inclusive. */
1737 static mchunkptr dumped_main_arena_end; /* Exclusive. */
1739 /* True if the pointer falls into the dumped arena. Use this after
1740 chunk_is_mmapped indicates a chunk is mmapped. */
1741 #define DUMPED_MAIN_ARENA_CHUNK(p) \
1742 ((p) >= dumped_main_arena_start && (p) < dumped_main_arena_end)
1744 /* There is only one instance of the malloc parameters. */
1746 static struct malloc_par mp_ =
1748 .top_pad = DEFAULT_TOP_PAD,
1749 .n_mmaps_max = DEFAULT_MMAP_MAX,
1750 .mmap_threshold = DEFAULT_MMAP_THRESHOLD,
1751 .trim_threshold = DEFAULT_TRIM_THRESHOLD,
1752 #define NARENAS_FROM_NCORES(n) ((n) * (sizeof (long) == 4 ? 2 : 8))
1753 .arena_test = NARENAS_FROM_NCORES (1)
1756 /* Maximum size of memory handled in fastbins. */
1757 static INTERNAL_SIZE_T global_max_fast;
1760 Initialize a malloc_state struct.
1762 This is called only from within malloc_consolidate, which needs
1763 be called in the same contexts anyway. It is never called directly
1764 outside of malloc_consolidate because some optimizing compilers try
1765 to inline it at all call points, which turns out not to be an
1766 optimization at all. (Inlining it in malloc_consolidate is fine though.)
1769 static void
1770 malloc_init_state (mstate av)
1772 int i;
1773 mbinptr bin;
1775 /* Establish circular links for normal bins */
1776 for (i = 1; i < NBINS; ++i)
1778 bin = bin_at (av, i);
1779 bin->fd = bin->bk = bin;
1782 #if MORECORE_CONTIGUOUS
1783 if (av != &main_arena)
1784 #endif
1785 set_noncontiguous (av);
1786 if (av == &main_arena)
1787 set_max_fast (DEFAULT_MXFAST);
1788 av->flags |= FASTCHUNKS_BIT;
1790 av->top = initial_top (av);
1794 Other internal utilities operating on mstates
1797 static void *sysmalloc (INTERNAL_SIZE_T, mstate);
1798 static int systrim (size_t, mstate);
1799 static void malloc_consolidate (mstate);
1802 /* -------------- Early definitions for debugging hooks ---------------- */
1804 /* Define and initialize the hook variables. These weak definitions must
1805 appear before any use of the variables in a function (arena.c uses one). */
1806 #ifndef weak_variable
1807 /* In GNU libc we want the hook variables to be weak definitions to
1808 avoid a problem with Emacs. */
1809 # define weak_variable weak_function
1810 #endif
1812 /* Forward declarations. */
1813 static void *malloc_hook_ini (size_t sz,
1814 const void *caller) __THROW;
1815 static void *realloc_hook_ini (void *ptr, size_t sz,
1816 const void *caller) __THROW;
1817 static void *memalign_hook_ini (size_t alignment, size_t sz,
1818 const void *caller) __THROW;
1820 #if HAVE_MALLOC_INIT_HOOK
1821 void weak_variable (*__malloc_initialize_hook) (void) = NULL;
1822 compat_symbol (libc, __malloc_initialize_hook,
1823 __malloc_initialize_hook, GLIBC_2_0);
1824 #endif
1826 void weak_variable (*__free_hook) (void *__ptr,
1827 const void *) = NULL;
1828 void *weak_variable (*__malloc_hook)
1829 (size_t __size, const void *) = malloc_hook_ini;
1830 void *weak_variable (*__realloc_hook)
1831 (void *__ptr, size_t __size, const void *)
1832 = realloc_hook_ini;
1833 void *weak_variable (*__memalign_hook)
1834 (size_t __alignment, size_t __size, const void *)
1835 = memalign_hook_ini;
1836 void weak_variable (*__after_morecore_hook) (void) = NULL;
1839 /* ---------------- Error behavior ------------------------------------ */
1841 #ifndef DEFAULT_CHECK_ACTION
1842 # define DEFAULT_CHECK_ACTION 3
1843 #endif
1845 static int check_action = DEFAULT_CHECK_ACTION;
1848 /* ------------------ Testing support ----------------------------------*/
1850 static int perturb_byte;
1852 static void
1853 alloc_perturb (char *p, size_t n)
1855 if (__glibc_unlikely (perturb_byte))
1856 memset (p, perturb_byte ^ 0xff, n);
1859 static void
1860 free_perturb (char *p, size_t n)
1862 if (__glibc_unlikely (perturb_byte))
1863 memset (p, perturb_byte, n);
1868 #include <stap-probe.h>
1870 /* ------------------- Support for multiple arenas -------------------- */
1871 #include "arena.c"
1874 Debugging support
1876 These routines make a number of assertions about the states
1877 of data structures that should be true at all times. If any
1878 are not true, it's very likely that a user program has somehow
1879 trashed memory. (It's also possible that there is a coding error
1880 in malloc. In which case, please report it!)
1883 #if !MALLOC_DEBUG
1885 # define check_chunk(A, P)
1886 # define check_free_chunk(A, P)
1887 # define check_inuse_chunk(A, P)
1888 # define check_remalloced_chunk(A, P, N)
1889 # define check_malloced_chunk(A, P, N)
1890 # define check_malloc_state(A)
1892 #else
1894 # define check_chunk(A, P) do_check_chunk (A, P)
1895 # define check_free_chunk(A, P) do_check_free_chunk (A, P)
1896 # define check_inuse_chunk(A, P) do_check_inuse_chunk (A, P)
1897 # define check_remalloced_chunk(A, P, N) do_check_remalloced_chunk (A, P, N)
1898 # define check_malloced_chunk(A, P, N) do_check_malloced_chunk (A, P, N)
1899 # define check_malloc_state(A) do_check_malloc_state (A)
1902 Properties of all chunks
1905 static void
1906 do_check_chunk (mstate av, mchunkptr p)
1908 unsigned long sz = chunksize (p);
1909 /* min and max possible addresses assuming contiguous allocation */
1910 char *max_address = (char *) (av->top) + chunksize (av->top);
1911 char *min_address = max_address - av->system_mem;
1913 if (!chunk_is_mmapped (p))
1915 /* Has legal address ... */
1916 if (p != av->top)
1918 if (contiguous (av))
1920 assert (((char *) p) >= min_address);
1921 assert (((char *) p + sz) <= ((char *) (av->top)));
1924 else
1926 /* top size is always at least MINSIZE */
1927 assert ((unsigned long) (sz) >= MINSIZE);
1928 /* top predecessor always marked inuse */
1929 assert (prev_inuse (p));
1932 else if (!DUMPED_MAIN_ARENA_CHUNK (p))
1934 /* address is outside main heap */
1935 if (contiguous (av) && av->top != initial_top (av))
1937 assert (((char *) p) < min_address || ((char *) p) >= max_address);
1939 /* chunk is page-aligned */
1940 assert (((prev_size (p) + sz) & (GLRO (dl_pagesize) - 1)) == 0);
1941 /* mem is aligned */
1942 assert (aligned_OK (chunk2mem (p)));
1947 Properties of free chunks
1950 static void
1951 do_check_free_chunk (mstate av, mchunkptr p)
1953 INTERNAL_SIZE_T sz = p->size & ~(PREV_INUSE | NON_MAIN_ARENA);
1954 mchunkptr next = chunk_at_offset (p, sz);
1956 do_check_chunk (av, p);
1958 /* Chunk must claim to be free ... */
1959 assert (!inuse (p));
1960 assert (!chunk_is_mmapped (p));
1962 /* Unless a special marker, must have OK fields */
1963 if ((unsigned long) (sz) >= MINSIZE)
1965 assert ((sz & MALLOC_ALIGN_MASK) == 0);
1966 assert (aligned_OK (chunk2mem (p)));
1967 /* ... matching footer field */
1968 assert (prev_size (p) == sz);
1969 /* ... and is fully consolidated */
1970 assert (prev_inuse (p));
1971 assert (next == av->top || inuse (next));
1973 /* ... and has minimally sane links */
1974 assert (p->fd->bk == p);
1975 assert (p->bk->fd == p);
1977 else /* markers are always of size SIZE_SZ */
1978 assert (sz == SIZE_SZ);
1982 Properties of inuse chunks
1985 static void
1986 do_check_inuse_chunk (mstate av, mchunkptr p)
1988 mchunkptr next;
1990 do_check_chunk (av, p);
1992 if (chunk_is_mmapped (p))
1993 return; /* mmapped chunks have no next/prev */
1995 /* Check whether it claims to be in use ... */
1996 assert (inuse (p));
1998 next = next_chunk (p);
2000 /* ... and is surrounded by OK chunks.
2001 Since more things can be checked with free chunks than inuse ones,
2002 if an inuse chunk borders them and debug is on, it's worth doing them.
2004 if (!prev_inuse (p))
2006 /* Note that we cannot even look at prev unless it is not inuse */
2007 mchunkptr prv = prev_chunk (p);
2008 assert (next_chunk (prv) == p);
2009 do_check_free_chunk (av, prv);
2012 if (next == av->top)
2014 assert (prev_inuse (next));
2015 assert (chunksize (next) >= MINSIZE);
2017 else if (!inuse (next))
2018 do_check_free_chunk (av, next);
2022 Properties of chunks recycled from fastbins
2025 static void
2026 do_check_remalloced_chunk (mstate av, mchunkptr p, INTERNAL_SIZE_T s)
2028 INTERNAL_SIZE_T sz = p->size & ~(PREV_INUSE | NON_MAIN_ARENA);
2030 if (!chunk_is_mmapped (p))
2032 assert (av == arena_for_chunk (p));
2033 if (chunk_main_arena (p))
2034 assert (av == &main_arena);
2035 else
2036 assert (av != &main_arena);
2039 do_check_inuse_chunk (av, p);
2041 /* Legal size ... */
2042 assert ((sz & MALLOC_ALIGN_MASK) == 0);
2043 assert ((unsigned long) (sz) >= MINSIZE);
2044 /* ... and alignment */
2045 assert (aligned_OK (chunk2mem (p)));
2046 /* chunk is less than MINSIZE more than request */
2047 assert ((long) (sz) - (long) (s) >= 0);
2048 assert ((long) (sz) - (long) (s + MINSIZE) < 0);
2052 Properties of nonrecycled chunks at the point they are malloced
2055 static void
2056 do_check_malloced_chunk (mstate av, mchunkptr p, INTERNAL_SIZE_T s)
2058 /* same as recycled case ... */
2059 do_check_remalloced_chunk (av, p, s);
2062 ... plus, must obey implementation invariant that prev_inuse is
2063 always true of any allocated chunk; i.e., that each allocated
2064 chunk borders either a previously allocated and still in-use
2065 chunk, or the base of its memory arena. This is ensured
2066 by making all allocations from the `lowest' part of any found
2067 chunk. This does not necessarily hold however for chunks
2068 recycled via fastbins.
2071 assert (prev_inuse (p));
2076 Properties of malloc_state.
2078 This may be useful for debugging malloc, as well as detecting user
2079 programmer errors that somehow write into malloc_state.
2081 If you are extending or experimenting with this malloc, you can
2082 probably figure out how to hack this routine to print out or
2083 display chunk addresses, sizes, bins, and other instrumentation.
2086 static void
2087 do_check_malloc_state (mstate av)
2089 int i;
2090 mchunkptr p;
2091 mchunkptr q;
2092 mbinptr b;
2093 unsigned int idx;
2094 INTERNAL_SIZE_T size;
2095 unsigned long total = 0;
2096 int max_fast_bin;
2098 /* internal size_t must be no wider than pointer type */
2099 assert (sizeof (INTERNAL_SIZE_T) <= sizeof (char *));
2101 /* alignment is a power of 2 */
2102 assert ((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT - 1)) == 0);
2104 /* cannot run remaining checks until fully initialized */
2105 if (av->top == 0 || av->top == initial_top (av))
2106 return;
2108 /* pagesize is a power of 2 */
2109 assert (powerof2(GLRO (dl_pagesize)));
2111 /* A contiguous main_arena is consistent with sbrk_base. */
2112 if (av == &main_arena && contiguous (av))
2113 assert ((char *) mp_.sbrk_base + av->system_mem ==
2114 (char *) av->top + chunksize (av->top));
2116 /* properties of fastbins */
2118 /* max_fast is in allowed range */
2119 assert ((get_max_fast () & ~1) <= request2size (MAX_FAST_SIZE));
2121 max_fast_bin = fastbin_index (get_max_fast ());
2123 for (i = 0; i < NFASTBINS; ++i)
2125 p = fastbin (av, i);
2127 /* The following test can only be performed for the main arena.
2128 While mallopt calls malloc_consolidate to get rid of all fast
2129 bins (especially those larger than the new maximum) this does
2130 only happen for the main arena. Trying to do this for any
2131 other arena would mean those arenas have to be locked and
2132 malloc_consolidate be called for them. This is excessive. And
2133 even if this is acceptable to somebody it still cannot solve
2134 the problem completely since if the arena is locked a
2135 concurrent malloc call might create a new arena which then
2136 could use the newly invalid fast bins. */
2138 /* all bins past max_fast are empty */
2139 if (av == &main_arena && i > max_fast_bin)
2140 assert (p == 0);
2142 while (p != 0)
2144 /* each chunk claims to be inuse */
2145 do_check_inuse_chunk (av, p);
2146 total += chunksize (p);
2147 /* chunk belongs in this bin */
2148 assert (fastbin_index (chunksize (p)) == i);
2149 p = p->fd;
2153 if (total != 0)
2154 assert (have_fastchunks (av));
2155 else if (!have_fastchunks (av))
2156 assert (total == 0);
2158 /* check normal bins */
2159 for (i = 1; i < NBINS; ++i)
2161 b = bin_at (av, i);
2163 /* binmap is accurate (except for bin 1 == unsorted_chunks) */
2164 if (i >= 2)
2166 unsigned int binbit = get_binmap (av, i);
2167 int empty = last (b) == b;
2168 if (!binbit)
2169 assert (empty);
2170 else if (!empty)
2171 assert (binbit);
2174 for (p = last (b); p != b; p = p->bk)
2176 /* each chunk claims to be free */
2177 do_check_free_chunk (av, p);
2178 size = chunksize (p);
2179 total += size;
2180 if (i >= 2)
2182 /* chunk belongs in bin */
2183 idx = bin_index (size);
2184 assert (idx == i);
2185 /* lists are sorted */
2186 assert (p->bk == b ||
2187 (unsigned long) chunksize (p->bk) >= (unsigned long) chunksize (p));
2189 if (!in_smallbin_range (size))
2191 if (p->fd_nextsize != NULL)
2193 if (p->fd_nextsize == p)
2194 assert (p->bk_nextsize == p);
2195 else
2197 if (p->fd_nextsize == first (b))
2198 assert (chunksize (p) < chunksize (p->fd_nextsize));
2199 else
2200 assert (chunksize (p) > chunksize (p->fd_nextsize));
2202 if (p == first (b))
2203 assert (chunksize (p) > chunksize (p->bk_nextsize));
2204 else
2205 assert (chunksize (p) < chunksize (p->bk_nextsize));
2208 else
2209 assert (p->bk_nextsize == NULL);
2212 else if (!in_smallbin_range (size))
2213 assert (p->fd_nextsize == NULL && p->bk_nextsize == NULL);
2214 /* chunk is followed by a legal chain of inuse chunks */
2215 for (q = next_chunk (p);
2216 (q != av->top && inuse (q) &&
2217 (unsigned long) (chunksize (q)) >= MINSIZE);
2218 q = next_chunk (q))
2219 do_check_inuse_chunk (av, q);
2223 /* top chunk is OK */
2224 check_chunk (av, av->top);
2226 #endif
2229 /* ----------------- Support for debugging hooks -------------------- */
2230 #include "hooks.c"
2233 /* ----------- Routines dealing with system allocation -------------- */
2236 sysmalloc handles malloc cases requiring more memory from the system.
2237 On entry, it is assumed that av->top does not have enough
2238 space to service request for nb bytes, thus requiring that av->top
2239 be extended or replaced.
2242 static void *
2243 sysmalloc (INTERNAL_SIZE_T nb, mstate av)
2245 mchunkptr old_top; /* incoming value of av->top */
2246 INTERNAL_SIZE_T old_size; /* its size */
2247 char *old_end; /* its end address */
2249 long size; /* arg to first MORECORE or mmap call */
2250 char *brk; /* return value from MORECORE */
2252 long correction; /* arg to 2nd MORECORE call */
2253 char *snd_brk; /* 2nd return val */
2255 INTERNAL_SIZE_T front_misalign; /* unusable bytes at front of new space */
2256 INTERNAL_SIZE_T end_misalign; /* partial page left at end of new space */
2257 char *aligned_brk; /* aligned offset into brk */
2259 mchunkptr p; /* the allocated/returned chunk */
2260 mchunkptr remainder; /* remainder from allocation */
2261 unsigned long remainder_size; /* its size */
2264 size_t pagesize = GLRO (dl_pagesize);
2265 bool tried_mmap = false;
2269 If have mmap, and the request size meets the mmap threshold, and
2270 the system supports mmap, and there are few enough currently
2271 allocated mmapped regions, try to directly map this request
2272 rather than expanding top.
2275 if (av == NULL
2276 || ((unsigned long) (nb) >= (unsigned long) (mp_.mmap_threshold)
2277 && (mp_.n_mmaps < mp_.n_mmaps_max)))
2279 char *mm; /* return value from mmap call*/
2281 try_mmap:
2283 Round up size to nearest page. For mmapped chunks, the overhead
2284 is one SIZE_SZ unit larger than for normal chunks, because there
2285 is no following chunk whose prev_size field could be used.
2287 See the front_misalign handling below, for glibc there is no
2288 need for further alignments unless we have have high alignment.
2290 if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
2291 size = ALIGN_UP (nb + SIZE_SZ, pagesize);
2292 else
2293 size = ALIGN_UP (nb + SIZE_SZ + MALLOC_ALIGN_MASK, pagesize);
2294 tried_mmap = true;
2296 /* Don't try if size wraps around 0 */
2297 if ((unsigned long) (size) > (unsigned long) (nb))
2299 mm = (char *) (MMAP (0, size, PROT_READ | PROT_WRITE, 0));
2301 if (mm != MAP_FAILED)
2304 The offset to the start of the mmapped region is stored
2305 in the prev_size field of the chunk. This allows us to adjust
2306 returned start address to meet alignment requirements here
2307 and in memalign(), and still be able to compute proper
2308 address argument for later munmap in free() and realloc().
2311 if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
2313 /* For glibc, chunk2mem increases the address by 2*SIZE_SZ and
2314 MALLOC_ALIGN_MASK is 2*SIZE_SZ-1. Each mmap'ed area is page
2315 aligned and therefore definitely MALLOC_ALIGN_MASK-aligned. */
2316 assert (((INTERNAL_SIZE_T) chunk2mem (mm) & MALLOC_ALIGN_MASK) == 0);
2317 front_misalign = 0;
2319 else
2320 front_misalign = (INTERNAL_SIZE_T) chunk2mem (mm) & MALLOC_ALIGN_MASK;
2321 if (front_misalign > 0)
2323 correction = MALLOC_ALIGNMENT - front_misalign;
2324 p = (mchunkptr) (mm + correction);
2325 set_prev_size (p, correction);
2326 set_head (p, (size - correction) | IS_MMAPPED);
2328 else
2330 p = (mchunkptr) mm;
2331 set_prev_size (p, 0);
2332 set_head (p, size | IS_MMAPPED);
2335 /* update statistics */
2337 int new = atomic_exchange_and_add (&mp_.n_mmaps, 1) + 1;
2338 atomic_max (&mp_.max_n_mmaps, new);
2340 unsigned long sum;
2341 sum = atomic_exchange_and_add (&mp_.mmapped_mem, size) + size;
2342 atomic_max (&mp_.max_mmapped_mem, sum);
2344 check_chunk (av, p);
2346 return chunk2mem (p);
2351 /* There are no usable arenas and mmap also failed. */
2352 if (av == NULL)
2353 return 0;
2355 /* Record incoming configuration of top */
2357 old_top = av->top;
2358 old_size = chunksize (old_top);
2359 old_end = (char *) (chunk_at_offset (old_top, old_size));
2361 brk = snd_brk = (char *) (MORECORE_FAILURE);
2364 If not the first time through, we require old_size to be
2365 at least MINSIZE and to have prev_inuse set.
2368 assert ((old_top == initial_top (av) && old_size == 0) ||
2369 ((unsigned long) (old_size) >= MINSIZE &&
2370 prev_inuse (old_top) &&
2371 ((unsigned long) old_end & (pagesize - 1)) == 0));
2373 /* Precondition: not enough current space to satisfy nb request */
2374 assert ((unsigned long) (old_size) < (unsigned long) (nb + MINSIZE));
2377 if (av != &main_arena)
2379 heap_info *old_heap, *heap;
2380 size_t old_heap_size;
2382 /* First try to extend the current heap. */
2383 old_heap = heap_for_ptr (old_top);
2384 old_heap_size = old_heap->size;
2385 if ((long) (MINSIZE + nb - old_size) > 0
2386 && grow_heap (old_heap, MINSIZE + nb - old_size) == 0)
2388 av->system_mem += old_heap->size - old_heap_size;
2389 set_head (old_top, (((char *) old_heap + old_heap->size) - (char *) old_top)
2390 | PREV_INUSE);
2392 else if ((heap = new_heap (nb + (MINSIZE + sizeof (*heap)), mp_.top_pad)))
2394 /* Use a newly allocated heap. */
2395 heap->ar_ptr = av;
2396 heap->prev = old_heap;
2397 av->system_mem += heap->size;
2398 /* Set up the new top. */
2399 top (av) = chunk_at_offset (heap, sizeof (*heap));
2400 set_head (top (av), (heap->size - sizeof (*heap)) | PREV_INUSE);
2402 /* Setup fencepost and free the old top chunk with a multiple of
2403 MALLOC_ALIGNMENT in size. */
2404 /* The fencepost takes at least MINSIZE bytes, because it might
2405 become the top chunk again later. Note that a footer is set
2406 up, too, although the chunk is marked in use. */
2407 old_size = (old_size - MINSIZE) & ~MALLOC_ALIGN_MASK;
2408 set_head (chunk_at_offset (old_top, old_size + 2 * SIZE_SZ), 0 | PREV_INUSE);
2409 if (old_size >= MINSIZE)
2411 set_head (chunk_at_offset (old_top, old_size), (2 * SIZE_SZ) | PREV_INUSE);
2412 set_foot (chunk_at_offset (old_top, old_size), (2 * SIZE_SZ));
2413 set_head (old_top, old_size | PREV_INUSE | NON_MAIN_ARENA);
2414 _int_free (av, old_top, 1);
2416 else
2418 set_head (old_top, (old_size + 2 * SIZE_SZ) | PREV_INUSE);
2419 set_foot (old_top, (old_size + 2 * SIZE_SZ));
2422 else if (!tried_mmap)
2423 /* We can at least try to use to mmap memory. */
2424 goto try_mmap;
2426 else /* av == main_arena */
2429 { /* Request enough space for nb + pad + overhead */
2430 size = nb + mp_.top_pad + MINSIZE;
2433 If contiguous, we can subtract out existing space that we hope to
2434 combine with new space. We add it back later only if
2435 we don't actually get contiguous space.
2438 if (contiguous (av))
2439 size -= old_size;
2442 Round to a multiple of page size.
2443 If MORECORE is not contiguous, this ensures that we only call it
2444 with whole-page arguments. And if MORECORE is contiguous and
2445 this is not first time through, this preserves page-alignment of
2446 previous calls. Otherwise, we correct to page-align below.
2449 size = ALIGN_UP (size, pagesize);
2452 Don't try to call MORECORE if argument is so big as to appear
2453 negative. Note that since mmap takes size_t arg, it may succeed
2454 below even if we cannot call MORECORE.
2457 if (size > 0)
2459 brk = (char *) (MORECORE (size));
2460 LIBC_PROBE (memory_sbrk_more, 2, brk, size);
2463 if (brk != (char *) (MORECORE_FAILURE))
2465 /* Call the `morecore' hook if necessary. */
2466 void (*hook) (void) = atomic_forced_read (__after_morecore_hook);
2467 if (__builtin_expect (hook != NULL, 0))
2468 (*hook)();
2470 else
2473 If have mmap, try using it as a backup when MORECORE fails or
2474 cannot be used. This is worth doing on systems that have "holes" in
2475 address space, so sbrk cannot extend to give contiguous space, but
2476 space is available elsewhere. Note that we ignore mmap max count
2477 and threshold limits, since the space will not be used as a
2478 segregated mmap region.
2481 /* Cannot merge with old top, so add its size back in */
2482 if (contiguous (av))
2483 size = ALIGN_UP (size + old_size, pagesize);
2485 /* If we are relying on mmap as backup, then use larger units */
2486 if ((unsigned long) (size) < (unsigned long) (MMAP_AS_MORECORE_SIZE))
2487 size = MMAP_AS_MORECORE_SIZE;
2489 /* Don't try if size wraps around 0 */
2490 if ((unsigned long) (size) > (unsigned long) (nb))
2492 char *mbrk = (char *) (MMAP (0, size, PROT_READ | PROT_WRITE, 0));
2494 if (mbrk != MAP_FAILED)
2496 /* We do not need, and cannot use, another sbrk call to find end */
2497 brk = mbrk;
2498 snd_brk = brk + size;
2501 Record that we no longer have a contiguous sbrk region.
2502 After the first time mmap is used as backup, we do not
2503 ever rely on contiguous space since this could incorrectly
2504 bridge regions.
2506 set_noncontiguous (av);
2511 if (brk != (char *) (MORECORE_FAILURE))
2513 if (mp_.sbrk_base == 0)
2514 mp_.sbrk_base = brk;
2515 av->system_mem += size;
2518 If MORECORE extends previous space, we can likewise extend top size.
2521 if (brk == old_end && snd_brk == (char *) (MORECORE_FAILURE))
2522 set_head (old_top, (size + old_size) | PREV_INUSE);
2524 else if (contiguous (av) && old_size && brk < old_end)
2526 /* Oops! Someone else killed our space.. Can't touch anything. */
2527 malloc_printerr (3, "break adjusted to free malloc space", brk,
2528 av);
2532 Otherwise, make adjustments:
2534 * If the first time through or noncontiguous, we need to call sbrk
2535 just to find out where the end of memory lies.
2537 * We need to ensure that all returned chunks from malloc will meet
2538 MALLOC_ALIGNMENT
2540 * If there was an intervening foreign sbrk, we need to adjust sbrk
2541 request size to account for fact that we will not be able to
2542 combine new space with existing space in old_top.
2544 * Almost all systems internally allocate whole pages at a time, in
2545 which case we might as well use the whole last page of request.
2546 So we allocate enough more memory to hit a page boundary now,
2547 which in turn causes future contiguous calls to page-align.
2550 else
2552 front_misalign = 0;
2553 end_misalign = 0;
2554 correction = 0;
2555 aligned_brk = brk;
2557 /* handle contiguous cases */
2558 if (contiguous (av))
2560 /* Count foreign sbrk as system_mem. */
2561 if (old_size)
2562 av->system_mem += brk - old_end;
2564 /* Guarantee alignment of first new chunk made from this space */
2566 front_misalign = (INTERNAL_SIZE_T) chunk2mem (brk) & MALLOC_ALIGN_MASK;
2567 if (front_misalign > 0)
2570 Skip over some bytes to arrive at an aligned position.
2571 We don't need to specially mark these wasted front bytes.
2572 They will never be accessed anyway because
2573 prev_inuse of av->top (and any chunk created from its start)
2574 is always true after initialization.
2577 correction = MALLOC_ALIGNMENT - front_misalign;
2578 aligned_brk += correction;
2582 If this isn't adjacent to existing space, then we will not
2583 be able to merge with old_top space, so must add to 2nd request.
2586 correction += old_size;
2588 /* Extend the end address to hit a page boundary */
2589 end_misalign = (INTERNAL_SIZE_T) (brk + size + correction);
2590 correction += (ALIGN_UP (end_misalign, pagesize)) - end_misalign;
2592 assert (correction >= 0);
2593 snd_brk = (char *) (MORECORE (correction));
2596 If can't allocate correction, try to at least find out current
2597 brk. It might be enough to proceed without failing.
2599 Note that if second sbrk did NOT fail, we assume that space
2600 is contiguous with first sbrk. This is a safe assumption unless
2601 program is multithreaded but doesn't use locks and a foreign sbrk
2602 occurred between our first and second calls.
2605 if (snd_brk == (char *) (MORECORE_FAILURE))
2607 correction = 0;
2608 snd_brk = (char *) (MORECORE (0));
2610 else
2612 /* Call the `morecore' hook if necessary. */
2613 void (*hook) (void) = atomic_forced_read (__after_morecore_hook);
2614 if (__builtin_expect (hook != NULL, 0))
2615 (*hook)();
2619 /* handle non-contiguous cases */
2620 else
2622 if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
2623 /* MORECORE/mmap must correctly align */
2624 assert (((unsigned long) chunk2mem (brk) & MALLOC_ALIGN_MASK) == 0);
2625 else
2627 front_misalign = (INTERNAL_SIZE_T) chunk2mem (brk) & MALLOC_ALIGN_MASK;
2628 if (front_misalign > 0)
2631 Skip over some bytes to arrive at an aligned position.
2632 We don't need to specially mark these wasted front bytes.
2633 They will never be accessed anyway because
2634 prev_inuse of av->top (and any chunk created from its start)
2635 is always true after initialization.
2638 aligned_brk += MALLOC_ALIGNMENT - front_misalign;
2642 /* Find out current end of memory */
2643 if (snd_brk == (char *) (MORECORE_FAILURE))
2645 snd_brk = (char *) (MORECORE (0));
2649 /* Adjust top based on results of second sbrk */
2650 if (snd_brk != (char *) (MORECORE_FAILURE))
2652 av->top = (mchunkptr) aligned_brk;
2653 set_head (av->top, (snd_brk - aligned_brk + correction) | PREV_INUSE);
2654 av->system_mem += correction;
2657 If not the first time through, we either have a
2658 gap due to foreign sbrk or a non-contiguous region. Insert a
2659 double fencepost at old_top to prevent consolidation with space
2660 we don't own. These fenceposts are artificial chunks that are
2661 marked as inuse and are in any case too small to use. We need
2662 two to make sizes and alignments work out.
2665 if (old_size != 0)
2668 Shrink old_top to insert fenceposts, keeping size a
2669 multiple of MALLOC_ALIGNMENT. We know there is at least
2670 enough space in old_top to do this.
2672 old_size = (old_size - 4 * SIZE_SZ) & ~MALLOC_ALIGN_MASK;
2673 set_head (old_top, old_size | PREV_INUSE);
2676 Note that the following assignments completely overwrite
2677 old_top when old_size was previously MINSIZE. This is
2678 intentional. We need the fencepost, even if old_top otherwise gets
2679 lost.
2681 set_head (chunk_at_offset (old_top, old_size),
2682 (2 * SIZE_SZ) | PREV_INUSE);
2683 set_head (chunk_at_offset (old_top, old_size + 2 * SIZE_SZ),
2684 (2 * SIZE_SZ) | PREV_INUSE);
2686 /* If possible, release the rest. */
2687 if (old_size >= MINSIZE)
2689 _int_free (av, old_top, 1);
2695 } /* if (av != &main_arena) */
2697 if ((unsigned long) av->system_mem > (unsigned long) (av->max_system_mem))
2698 av->max_system_mem = av->system_mem;
2699 check_malloc_state (av);
2701 /* finally, do the allocation */
2702 p = av->top;
2703 size = chunksize (p);
2705 /* check that one of the above allocation paths succeeded */
2706 if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
2708 remainder_size = size - nb;
2709 remainder = chunk_at_offset (p, nb);
2710 av->top = remainder;
2711 set_head (p, nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));
2712 set_head (remainder, remainder_size | PREV_INUSE);
2713 check_malloced_chunk (av, p, nb);
2714 return chunk2mem (p);
2717 /* catch all failure paths */
2718 __set_errno (ENOMEM);
2719 return 0;
2724 systrim is an inverse of sorts to sysmalloc. It gives memory back
2725 to the system (via negative arguments to sbrk) if there is unused
2726 memory at the `high' end of the malloc pool. It is called
2727 automatically by free() when top space exceeds the trim
2728 threshold. It is also called by the public malloc_trim routine. It
2729 returns 1 if it actually released any memory, else 0.
2732 static int
2733 systrim (size_t pad, mstate av)
2735 long top_size; /* Amount of top-most memory */
2736 long extra; /* Amount to release */
2737 long released; /* Amount actually released */
2738 char *current_brk; /* address returned by pre-check sbrk call */
2739 char *new_brk; /* address returned by post-check sbrk call */
2740 size_t pagesize;
2741 long top_area;
2743 pagesize = GLRO (dl_pagesize);
2744 top_size = chunksize (av->top);
2746 top_area = top_size - MINSIZE - 1;
2747 if (top_area <= pad)
2748 return 0;
2750 /* Release in pagesize units and round down to the nearest page. */
2751 extra = ALIGN_DOWN(top_area - pad, pagesize);
2753 if (extra == 0)
2754 return 0;
2757 Only proceed if end of memory is where we last set it.
2758 This avoids problems if there were foreign sbrk calls.
2760 current_brk = (char *) (MORECORE (0));
2761 if (current_brk == (char *) (av->top) + top_size)
2764 Attempt to release memory. We ignore MORECORE return value,
2765 and instead call again to find out where new end of memory is.
2766 This avoids problems if first call releases less than we asked,
2767 of if failure somehow altered brk value. (We could still
2768 encounter problems if it altered brk in some very bad way,
2769 but the only thing we can do is adjust anyway, which will cause
2770 some downstream failure.)
2773 MORECORE (-extra);
2774 /* Call the `morecore' hook if necessary. */
2775 void (*hook) (void) = atomic_forced_read (__after_morecore_hook);
2776 if (__builtin_expect (hook != NULL, 0))
2777 (*hook)();
2778 new_brk = (char *) (MORECORE (0));
2780 LIBC_PROBE (memory_sbrk_less, 2, new_brk, extra);
2782 if (new_brk != (char *) MORECORE_FAILURE)
2784 released = (long) (current_brk - new_brk);
2786 if (released != 0)
2788 /* Success. Adjust top. */
2789 av->system_mem -= released;
2790 set_head (av->top, (top_size - released) | PREV_INUSE);
2791 check_malloc_state (av);
2792 return 1;
2796 return 0;
2799 static void
2800 internal_function
2801 munmap_chunk (mchunkptr p)
2803 INTERNAL_SIZE_T size = chunksize (p);
2805 assert (chunk_is_mmapped (p));
2807 /* Do nothing if the chunk is a faked mmapped chunk in the dumped
2808 main arena. We never free this memory. */
2809 if (DUMPED_MAIN_ARENA_CHUNK (p))
2810 return;
2812 uintptr_t block = (uintptr_t) p - prev_size (p);
2813 size_t total_size = prev_size (p) + size;
2814 /* Unfortunately we have to do the compilers job by hand here. Normally
2815 we would test BLOCK and TOTAL-SIZE separately for compliance with the
2816 page size. But gcc does not recognize the optimization possibility
2817 (in the moment at least) so we combine the two values into one before
2818 the bit test. */
2819 if (__builtin_expect (((block | total_size) & (GLRO (dl_pagesize) - 1)) != 0, 0))
2821 malloc_printerr (check_action, "munmap_chunk(): invalid pointer",
2822 chunk2mem (p), NULL);
2823 return;
2826 atomic_decrement (&mp_.n_mmaps);
2827 atomic_add (&mp_.mmapped_mem, -total_size);
2829 /* If munmap failed the process virtual memory address space is in a
2830 bad shape. Just leave the block hanging around, the process will
2831 terminate shortly anyway since not much can be done. */
2832 __munmap ((char *) block, total_size);
2835 #if HAVE_MREMAP
2837 static mchunkptr
2838 internal_function
2839 mremap_chunk (mchunkptr p, size_t new_size)
2841 size_t pagesize = GLRO (dl_pagesize);
2842 INTERNAL_SIZE_T offset = prev_size (p);
2843 INTERNAL_SIZE_T size = chunksize (p);
2844 char *cp;
2846 assert (chunk_is_mmapped (p));
2847 assert (((size + offset) & (GLRO (dl_pagesize) - 1)) == 0);
2849 /* Note the extra SIZE_SZ overhead as in mmap_chunk(). */
2850 new_size = ALIGN_UP (new_size + offset + SIZE_SZ, pagesize);
2852 /* No need to remap if the number of pages does not change. */
2853 if (size + offset == new_size)
2854 return p;
2856 cp = (char *) __mremap ((char *) p - offset, size + offset, new_size,
2857 MREMAP_MAYMOVE);
2859 if (cp == MAP_FAILED)
2860 return 0;
2862 p = (mchunkptr) (cp + offset);
2864 assert (aligned_OK (chunk2mem (p)));
2866 assert (prev_size (p) == offset);
2867 set_head (p, (new_size - offset) | IS_MMAPPED);
2869 INTERNAL_SIZE_T new;
2870 new = atomic_exchange_and_add (&mp_.mmapped_mem, new_size - size - offset)
2871 + new_size - size - offset;
2872 atomic_max (&mp_.max_mmapped_mem, new);
2873 return p;
2875 #endif /* HAVE_MREMAP */
2877 /*------------------------ Public wrappers. --------------------------------*/
2879 void *
2880 __libc_malloc (size_t bytes)
2882 mstate ar_ptr;
2883 void *victim;
2885 void *(*hook) (size_t, const void *)
2886 = atomic_forced_read (__malloc_hook);
2887 if (__builtin_expect (hook != NULL, 0))
2888 return (*hook)(bytes, RETURN_ADDRESS (0));
2890 arena_get (ar_ptr, bytes);
2892 victim = _int_malloc (ar_ptr, bytes);
2893 /* Retry with another arena only if we were able to find a usable arena
2894 before. */
2895 if (!victim && ar_ptr != NULL)
2897 LIBC_PROBE (memory_malloc_retry, 1, bytes);
2898 ar_ptr = arena_get_retry (ar_ptr, bytes);
2899 victim = _int_malloc (ar_ptr, bytes);
2902 if (ar_ptr != NULL)
2903 __libc_lock_unlock (ar_ptr->mutex);
2905 assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
2906 ar_ptr == arena_for_chunk (mem2chunk (victim)));
2907 return victim;
2909 libc_hidden_def (__libc_malloc)
2911 void
2912 __libc_free (void *mem)
2914 mstate ar_ptr;
2915 mchunkptr p; /* chunk corresponding to mem */
2917 void (*hook) (void *, const void *)
2918 = atomic_forced_read (__free_hook);
2919 if (__builtin_expect (hook != NULL, 0))
2921 (*hook)(mem, RETURN_ADDRESS (0));
2922 return;
2925 if (mem == 0) /* free(0) has no effect */
2926 return;
2928 p = mem2chunk (mem);
2930 if (chunk_is_mmapped (p)) /* release mmapped memory. */
2932 /* See if the dynamic brk/mmap threshold needs adjusting.
2933 Dumped fake mmapped chunks do not affect the threshold. */
2934 if (!mp_.no_dyn_threshold
2935 && chunksize_nomask (p) > mp_.mmap_threshold
2936 && chunksize_nomask (p) <= DEFAULT_MMAP_THRESHOLD_MAX
2937 && !DUMPED_MAIN_ARENA_CHUNK (p))
2939 mp_.mmap_threshold = chunksize (p);
2940 mp_.trim_threshold = 2 * mp_.mmap_threshold;
2941 LIBC_PROBE (memory_mallopt_free_dyn_thresholds, 2,
2942 mp_.mmap_threshold, mp_.trim_threshold);
2944 munmap_chunk (p);
2945 return;
2948 ar_ptr = arena_for_chunk (p);
2949 _int_free (ar_ptr, p, 0);
2951 libc_hidden_def (__libc_free)
2953 void *
2954 __libc_realloc (void *oldmem, size_t bytes)
2956 mstate ar_ptr;
2957 INTERNAL_SIZE_T nb; /* padded request size */
2959 void *newp; /* chunk to return */
2961 void *(*hook) (void *, size_t, const void *) =
2962 atomic_forced_read (__realloc_hook);
2963 if (__builtin_expect (hook != NULL, 0))
2964 return (*hook)(oldmem, bytes, RETURN_ADDRESS (0));
2966 #if REALLOC_ZERO_BYTES_FREES
2967 if (bytes == 0 && oldmem != NULL)
2969 __libc_free (oldmem); return 0;
2971 #endif
2973 /* realloc of null is supposed to be same as malloc */
2974 if (oldmem == 0)
2975 return __libc_malloc (bytes);
2977 /* chunk corresponding to oldmem */
2978 const mchunkptr oldp = mem2chunk (oldmem);
2979 /* its size */
2980 const INTERNAL_SIZE_T oldsize = chunksize (oldp);
2982 if (chunk_is_mmapped (oldp))
2983 ar_ptr = NULL;
2984 else
2985 ar_ptr = arena_for_chunk (oldp);
2987 /* Little security check which won't hurt performance: the allocator
2988 never wrapps around at the end of the address space. Therefore
2989 we can exclude some size values which might appear here by
2990 accident or by "design" from some intruder. We need to bypass
2991 this check for dumped fake mmap chunks from the old main arena
2992 because the new malloc may provide additional alignment. */
2993 if ((__builtin_expect ((uintptr_t) oldp > (uintptr_t) -oldsize, 0)
2994 || __builtin_expect (misaligned_chunk (oldp), 0))
2995 && !DUMPED_MAIN_ARENA_CHUNK (oldp))
2997 malloc_printerr (check_action, "realloc(): invalid pointer", oldmem,
2998 ar_ptr);
2999 return NULL;
3002 checked_request2size (bytes, nb);
3004 if (chunk_is_mmapped (oldp))
3006 /* If this is a faked mmapped chunk from the dumped main arena,
3007 always make a copy (and do not free the old chunk). */
3008 if (DUMPED_MAIN_ARENA_CHUNK (oldp))
3010 /* Must alloc, copy, free. */
3011 void *newmem = __libc_malloc (bytes);
3012 if (newmem == 0)
3013 return NULL;
3014 /* Copy as many bytes as are available from the old chunk
3015 and fit into the new size. NB: The overhead for faked
3016 mmapped chunks is only SIZE_SZ, not 2 * SIZE_SZ as for
3017 regular mmapped chunks. */
3018 if (bytes > oldsize - SIZE_SZ)
3019 bytes = oldsize - SIZE_SZ;
3020 memcpy (newmem, oldmem, bytes);
3021 return newmem;
3024 void *newmem;
3026 #if HAVE_MREMAP
3027 newp = mremap_chunk (oldp, nb);
3028 if (newp)
3029 return chunk2mem (newp);
3030 #endif
3031 /* Note the extra SIZE_SZ overhead. */
3032 if (oldsize - SIZE_SZ >= nb)
3033 return oldmem; /* do nothing */
3035 /* Must alloc, copy, free. */
3036 newmem = __libc_malloc (bytes);
3037 if (newmem == 0)
3038 return 0; /* propagate failure */
3040 memcpy (newmem, oldmem, oldsize - 2 * SIZE_SZ);
3041 munmap_chunk (oldp);
3042 return newmem;
3045 __libc_lock_lock (ar_ptr->mutex);
3047 newp = _int_realloc (ar_ptr, oldp, oldsize, nb);
3049 __libc_lock_unlock (ar_ptr->mutex);
3050 assert (!newp || chunk_is_mmapped (mem2chunk (newp)) ||
3051 ar_ptr == arena_for_chunk (mem2chunk (newp)));
3053 if (newp == NULL)
3055 /* Try harder to allocate memory in other arenas. */
3056 LIBC_PROBE (memory_realloc_retry, 2, bytes, oldmem);
3057 newp = __libc_malloc (bytes);
3058 if (newp != NULL)
3060 memcpy (newp, oldmem, oldsize - SIZE_SZ);
3061 _int_free (ar_ptr, oldp, 0);
3065 return newp;
3067 libc_hidden_def (__libc_realloc)
3069 void *
3070 __libc_memalign (size_t alignment, size_t bytes)
3072 void *address = RETURN_ADDRESS (0);
3073 return _mid_memalign (alignment, bytes, address);
3076 static void *
3077 _mid_memalign (size_t alignment, size_t bytes, void *address)
3079 mstate ar_ptr;
3080 void *p;
3082 void *(*hook) (size_t, size_t, const void *) =
3083 atomic_forced_read (__memalign_hook);
3084 if (__builtin_expect (hook != NULL, 0))
3085 return (*hook)(alignment, bytes, address);
3087 /* If we need less alignment than we give anyway, just relay to malloc. */
3088 if (alignment <= MALLOC_ALIGNMENT)
3089 return __libc_malloc (bytes);
3091 /* Otherwise, ensure that it is at least a minimum chunk size */
3092 if (alignment < MINSIZE)
3093 alignment = MINSIZE;
3095 /* If the alignment is greater than SIZE_MAX / 2 + 1 it cannot be a
3096 power of 2 and will cause overflow in the check below. */
3097 if (alignment > SIZE_MAX / 2 + 1)
3099 __set_errno (EINVAL);
3100 return 0;
3103 /* Check for overflow. */
3104 if (bytes > SIZE_MAX - alignment - MINSIZE)
3106 __set_errno (ENOMEM);
3107 return 0;
3111 /* Make sure alignment is power of 2. */
3112 if (!powerof2 (alignment))
3114 size_t a = MALLOC_ALIGNMENT * 2;
3115 while (a < alignment)
3116 a <<= 1;
3117 alignment = a;
3120 arena_get (ar_ptr, bytes + alignment + MINSIZE);
3122 p = _int_memalign (ar_ptr, alignment, bytes);
3123 if (!p && ar_ptr != NULL)
3125 LIBC_PROBE (memory_memalign_retry, 2, bytes, alignment);
3126 ar_ptr = arena_get_retry (ar_ptr, bytes);
3127 p = _int_memalign (ar_ptr, alignment, bytes);
3130 if (ar_ptr != NULL)
3131 __libc_lock_unlock (ar_ptr->mutex);
3133 assert (!p || chunk_is_mmapped (mem2chunk (p)) ||
3134 ar_ptr == arena_for_chunk (mem2chunk (p)));
3135 return p;
3137 /* For ISO C11. */
3138 weak_alias (__libc_memalign, aligned_alloc)
3139 libc_hidden_def (__libc_memalign)
3141 void *
3142 __libc_valloc (size_t bytes)
3144 if (__malloc_initialized < 0)
3145 ptmalloc_init ();
3147 void *address = RETURN_ADDRESS (0);
3148 size_t pagesize = GLRO (dl_pagesize);
3149 return _mid_memalign (pagesize, bytes, address);
3152 void *
3153 __libc_pvalloc (size_t bytes)
3155 if (__malloc_initialized < 0)
3156 ptmalloc_init ();
3158 void *address = RETURN_ADDRESS (0);
3159 size_t pagesize = GLRO (dl_pagesize);
3160 size_t rounded_bytes = ALIGN_UP (bytes, pagesize);
3162 /* Check for overflow. */
3163 if (bytes > SIZE_MAX - 2 * pagesize - MINSIZE)
3165 __set_errno (ENOMEM);
3166 return 0;
3169 return _mid_memalign (pagesize, rounded_bytes, address);
3172 void *
3173 __libc_calloc (size_t n, size_t elem_size)
3175 mstate av;
3176 mchunkptr oldtop, p;
3177 INTERNAL_SIZE_T bytes, sz, csz, oldtopsize;
3178 void *mem;
3179 unsigned long clearsize;
3180 unsigned long nclears;
3181 INTERNAL_SIZE_T *d;
3183 /* size_t is unsigned so the behavior on overflow is defined. */
3184 bytes = n * elem_size;
3185 #define HALF_INTERNAL_SIZE_T \
3186 (((INTERNAL_SIZE_T) 1) << (8 * sizeof (INTERNAL_SIZE_T) / 2))
3187 if (__builtin_expect ((n | elem_size) >= HALF_INTERNAL_SIZE_T, 0))
3189 if (elem_size != 0 && bytes / elem_size != n)
3191 __set_errno (ENOMEM);
3192 return 0;
3196 void *(*hook) (size_t, const void *) =
3197 atomic_forced_read (__malloc_hook);
3198 if (__builtin_expect (hook != NULL, 0))
3200 sz = bytes;
3201 mem = (*hook)(sz, RETURN_ADDRESS (0));
3202 if (mem == 0)
3203 return 0;
3205 return memset (mem, 0, sz);
3208 sz = bytes;
3210 arena_get (av, sz);
3211 if (av)
3213 /* Check if we hand out the top chunk, in which case there may be no
3214 need to clear. */
3215 #if MORECORE_CLEARS
3216 oldtop = top (av);
3217 oldtopsize = chunksize (top (av));
3218 # if MORECORE_CLEARS < 2
3219 /* Only newly allocated memory is guaranteed to be cleared. */
3220 if (av == &main_arena &&
3221 oldtopsize < mp_.sbrk_base + av->max_system_mem - (char *) oldtop)
3222 oldtopsize = (mp_.sbrk_base + av->max_system_mem - (char *) oldtop);
3223 # endif
3224 if (av != &main_arena)
3226 heap_info *heap = heap_for_ptr (oldtop);
3227 if (oldtopsize < (char *) heap + heap->mprotect_size - (char *) oldtop)
3228 oldtopsize = (char *) heap + heap->mprotect_size - (char *) oldtop;
3230 #endif
3232 else
3234 /* No usable arenas. */
3235 oldtop = 0;
3236 oldtopsize = 0;
3238 mem = _int_malloc (av, sz);
3241 assert (!mem || chunk_is_mmapped (mem2chunk (mem)) ||
3242 av == arena_for_chunk (mem2chunk (mem)));
3244 if (mem == 0 && av != NULL)
3246 LIBC_PROBE (memory_calloc_retry, 1, sz);
3247 av = arena_get_retry (av, sz);
3248 mem = _int_malloc (av, sz);
3251 if (av != NULL)
3252 __libc_lock_unlock (av->mutex);
3254 /* Allocation failed even after a retry. */
3255 if (mem == 0)
3256 return 0;
3258 p = mem2chunk (mem);
3260 /* Two optional cases in which clearing not necessary */
3261 if (chunk_is_mmapped (p))
3263 if (__builtin_expect (perturb_byte, 0))
3264 return memset (mem, 0, sz);
3266 return mem;
3269 csz = chunksize (p);
3271 #if MORECORE_CLEARS
3272 if (perturb_byte == 0 && (p == oldtop && csz > oldtopsize))
3274 /* clear only the bytes from non-freshly-sbrked memory */
3275 csz = oldtopsize;
3277 #endif
3279 /* Unroll clear of <= 36 bytes (72 if 8byte sizes). We know that
3280 contents have an odd number of INTERNAL_SIZE_T-sized words;
3281 minimally 3. */
3282 d = (INTERNAL_SIZE_T *) mem;
3283 clearsize = csz - SIZE_SZ;
3284 nclears = clearsize / sizeof (INTERNAL_SIZE_T);
3285 assert (nclears >= 3);
3287 if (nclears > 9)
3288 return memset (d, 0, clearsize);
3290 else
3292 *(d + 0) = 0;
3293 *(d + 1) = 0;
3294 *(d + 2) = 0;
3295 if (nclears > 4)
3297 *(d + 3) = 0;
3298 *(d + 4) = 0;
3299 if (nclears > 6)
3301 *(d + 5) = 0;
3302 *(d + 6) = 0;
3303 if (nclears > 8)
3305 *(d + 7) = 0;
3306 *(d + 8) = 0;
3312 return mem;
3316 ------------------------------ malloc ------------------------------
3319 static void *
3320 _int_malloc (mstate av, size_t bytes)
3322 INTERNAL_SIZE_T nb; /* normalized request size */
3323 unsigned int idx; /* associated bin index */
3324 mbinptr bin; /* associated bin */
3326 mchunkptr victim; /* inspected/selected chunk */
3327 INTERNAL_SIZE_T size; /* its size */
3328 int victim_index; /* its bin index */
3330 mchunkptr remainder; /* remainder from a split */
3331 unsigned long remainder_size; /* its size */
3333 unsigned int block; /* bit map traverser */
3334 unsigned int bit; /* bit map traverser */
3335 unsigned int map; /* current word of binmap */
3337 mchunkptr fwd; /* misc temp for linking */
3338 mchunkptr bck; /* misc temp for linking */
3340 const char *errstr = NULL;
3343 Convert request size to internal form by adding SIZE_SZ bytes
3344 overhead plus possibly more to obtain necessary alignment and/or
3345 to obtain a size of at least MINSIZE, the smallest allocatable
3346 size. Also, checked_request2size traps (returning 0) request sizes
3347 that are so large that they wrap around zero when padded and
3348 aligned.
3351 checked_request2size (bytes, nb);
3353 /* There are no usable arenas. Fall back to sysmalloc to get a chunk from
3354 mmap. */
3355 if (__glibc_unlikely (av == NULL))
3357 void *p = sysmalloc (nb, av);
3358 if (p != NULL)
3359 alloc_perturb (p, bytes);
3360 return p;
3364 If the size qualifies as a fastbin, first check corresponding bin.
3365 This code is safe to execute even if av is not yet initialized, so we
3366 can try it without checking, which saves some time on this fast path.
3369 if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
3371 idx = fastbin_index (nb);
3372 mfastbinptr *fb = &fastbin (av, idx);
3373 mchunkptr pp = *fb;
3376 victim = pp;
3377 if (victim == NULL)
3378 break;
3380 while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
3381 != victim);
3382 if (victim != 0)
3384 if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
3386 errstr = "malloc(): memory corruption (fast)";
3387 errout:
3388 malloc_printerr (check_action, errstr, chunk2mem (victim), av);
3389 return NULL;
3391 check_remalloced_chunk (av, victim, nb);
3392 void *p = chunk2mem (victim);
3393 alloc_perturb (p, bytes);
3394 return p;
3399 If a small request, check regular bin. Since these "smallbins"
3400 hold one size each, no searching within bins is necessary.
3401 (For a large request, we need to wait until unsorted chunks are
3402 processed to find best fit. But for small ones, fits are exact
3403 anyway, so we can check now, which is faster.)
3406 if (in_smallbin_range (nb))
3408 idx = smallbin_index (nb);
3409 bin = bin_at (av, idx);
3411 if ((victim = last (bin)) != bin)
3413 if (victim == 0) /* initialization check */
3414 malloc_consolidate (av);
3415 else
3417 bck = victim->bk;
3418 if (__glibc_unlikely (bck->fd != victim))
3420 errstr = "malloc(): smallbin double linked list corrupted";
3421 goto errout;
3423 set_inuse_bit_at_offset (victim, nb);
3424 bin->bk = bck;
3425 bck->fd = bin;
3427 if (av != &main_arena)
3428 set_non_main_arena (victim);
3429 check_malloced_chunk (av, victim, nb);
3430 void *p = chunk2mem (victim);
3431 alloc_perturb (p, bytes);
3432 return p;
3438 If this is a large request, consolidate fastbins before continuing.
3439 While it might look excessive to kill all fastbins before
3440 even seeing if there is space available, this avoids
3441 fragmentation problems normally associated with fastbins.
3442 Also, in practice, programs tend to have runs of either small or
3443 large requests, but less often mixtures, so consolidation is not
3444 invoked all that often in most programs. And the programs that
3445 it is called frequently in otherwise tend to fragment.
3448 else
3450 idx = largebin_index (nb);
3451 if (have_fastchunks (av))
3452 malloc_consolidate (av);
3456 Process recently freed or remaindered chunks, taking one only if
3457 it is exact fit, or, if this a small request, the chunk is remainder from
3458 the most recent non-exact fit. Place other traversed chunks in
3459 bins. Note that this step is the only place in any routine where
3460 chunks are placed in bins.
3462 The outer loop here is needed because we might not realize until
3463 near the end of malloc that we should have consolidated, so must
3464 do so and retry. This happens at most once, and only when we would
3465 otherwise need to expand memory to service a "small" request.
3468 for (;; )
3470 int iters = 0;
3471 while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
3473 bck = victim->bk;
3474 if (__builtin_expect (chunksize_nomask (victim) <= 2 * SIZE_SZ, 0)
3475 || __builtin_expect (chunksize_nomask (victim)
3476 > av->system_mem, 0))
3477 malloc_printerr (check_action, "malloc(): memory corruption",
3478 chunk2mem (victim), av);
3479 size = chunksize (victim);
3482 If a small request, try to use last remainder if it is the
3483 only chunk in unsorted bin. This helps promote locality for
3484 runs of consecutive small requests. This is the only
3485 exception to best-fit, and applies only when there is
3486 no exact fit for a small chunk.
3489 if (in_smallbin_range (nb) &&
3490 bck == unsorted_chunks (av) &&
3491 victim == av->last_remainder &&
3492 (unsigned long) (size) > (unsigned long) (nb + MINSIZE))
3494 /* split and reattach remainder */
3495 remainder_size = size - nb;
3496 remainder = chunk_at_offset (victim, nb);
3497 unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
3498 av->last_remainder = remainder;
3499 remainder->bk = remainder->fd = unsorted_chunks (av);
3500 if (!in_smallbin_range (remainder_size))
3502 remainder->fd_nextsize = NULL;
3503 remainder->bk_nextsize = NULL;
3506 set_head (victim, nb | PREV_INUSE |
3507 (av != &main_arena ? NON_MAIN_ARENA : 0));
3508 set_head (remainder, remainder_size | PREV_INUSE);
3509 set_foot (remainder, remainder_size);
3511 check_malloced_chunk (av, victim, nb);
3512 void *p = chunk2mem (victim);
3513 alloc_perturb (p, bytes);
3514 return p;
3517 /* remove from unsorted list */
3518 unsorted_chunks (av)->bk = bck;
3519 bck->fd = unsorted_chunks (av);
3521 /* Take now instead of binning if exact fit */
3523 if (size == nb)
3525 set_inuse_bit_at_offset (victim, size);
3526 if (av != &main_arena)
3527 set_non_main_arena (victim);
3528 check_malloced_chunk (av, victim, nb);
3529 void *p = chunk2mem (victim);
3530 alloc_perturb (p, bytes);
3531 return p;
3534 /* place chunk in bin */
3536 if (in_smallbin_range (size))
3538 victim_index = smallbin_index (size);
3539 bck = bin_at (av, victim_index);
3540 fwd = bck->fd;
3542 else
3544 victim_index = largebin_index (size);
3545 bck = bin_at (av, victim_index);
3546 fwd = bck->fd;
3548 /* maintain large bins in sorted order */
3549 if (fwd != bck)
3551 /* Or with inuse bit to speed comparisons */
3552 size |= PREV_INUSE;
3553 /* if smaller than smallest, bypass loop below */
3554 assert (chunk_main_arena (bck->bk));
3555 if ((unsigned long) (size)
3556 < (unsigned long) chunksize_nomask (bck->bk))
3558 fwd = bck;
3559 bck = bck->bk;
3561 victim->fd_nextsize = fwd->fd;
3562 victim->bk_nextsize = fwd->fd->bk_nextsize;
3563 fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
3565 else
3567 assert (chunk_main_arena (fwd));
3568 while ((unsigned long) size < chunksize_nomask (fwd))
3570 fwd = fwd->fd_nextsize;
3571 assert (chunk_main_arena (fwd));
3574 if ((unsigned long) size
3575 == (unsigned long) chunksize_nomask (fwd))
3576 /* Always insert in the second position. */
3577 fwd = fwd->fd;
3578 else
3580 victim->fd_nextsize = fwd;
3581 victim->bk_nextsize = fwd->bk_nextsize;
3582 fwd->bk_nextsize = victim;
3583 victim->bk_nextsize->fd_nextsize = victim;
3585 bck = fwd->bk;
3588 else
3589 victim->fd_nextsize = victim->bk_nextsize = victim;
3592 mark_bin (av, victim_index);
3593 victim->bk = bck;
3594 victim->fd = fwd;
3595 fwd->bk = victim;
3596 bck->fd = victim;
3598 #define MAX_ITERS 10000
3599 if (++iters >= MAX_ITERS)
3600 break;
3604 If a large request, scan through the chunks of current bin in
3605 sorted order to find smallest that fits. Use the skip list for this.
3608 if (!in_smallbin_range (nb))
3610 bin = bin_at (av, idx);
3612 /* skip scan if empty or largest chunk is too small */
3613 if ((victim = first (bin)) != bin
3614 && (unsigned long) chunksize_nomask (victim)
3615 >= (unsigned long) (nb))
3617 victim = victim->bk_nextsize;
3618 while (((unsigned long) (size = chunksize (victim)) <
3619 (unsigned long) (nb)))
3620 victim = victim->bk_nextsize;
3622 /* Avoid removing the first entry for a size so that the skip
3623 list does not have to be rerouted. */
3624 if (victim != last (bin)
3625 && chunksize_nomask (victim)
3626 == chunksize_nomask (victim->fd))
3627 victim = victim->fd;
3629 remainder_size = size - nb;
3630 unlink (av, victim, bck, fwd);
3632 /* Exhaust */
3633 if (remainder_size < MINSIZE)
3635 set_inuse_bit_at_offset (victim, size);
3636 if (av != &main_arena)
3637 set_non_main_arena (victim);
3639 /* Split */
3640 else
3642 remainder = chunk_at_offset (victim, nb);
3643 /* We cannot assume the unsorted list is empty and therefore
3644 have to perform a complete insert here. */
3645 bck = unsorted_chunks (av);
3646 fwd = bck->fd;
3647 if (__glibc_unlikely (fwd->bk != bck))
3649 errstr = "malloc(): corrupted unsorted chunks";
3650 goto errout;
3652 remainder->bk = bck;
3653 remainder->fd = fwd;
3654 bck->fd = remainder;
3655 fwd->bk = remainder;
3656 if (!in_smallbin_range (remainder_size))
3658 remainder->fd_nextsize = NULL;
3659 remainder->bk_nextsize = NULL;
3661 set_head (victim, nb | PREV_INUSE |
3662 (av != &main_arena ? NON_MAIN_ARENA : 0));
3663 set_head (remainder, remainder_size | PREV_INUSE);
3664 set_foot (remainder, remainder_size);
3666 check_malloced_chunk (av, victim, nb);
3667 void *p = chunk2mem (victim);
3668 alloc_perturb (p, bytes);
3669 return p;
3674 Search for a chunk by scanning bins, starting with next largest
3675 bin. This search is strictly by best-fit; i.e., the smallest
3676 (with ties going to approximately the least recently used) chunk
3677 that fits is selected.
3679 The bitmap avoids needing to check that most blocks are nonempty.
3680 The particular case of skipping all bins during warm-up phases
3681 when no chunks have been returned yet is faster than it might look.
3684 ++idx;
3685 bin = bin_at (av, idx);
3686 block = idx2block (idx);
3687 map = av->binmap[block];
3688 bit = idx2bit (idx);
3690 for (;; )
3692 /* Skip rest of block if there are no more set bits in this block. */
3693 if (bit > map || bit == 0)
3697 if (++block >= BINMAPSIZE) /* out of bins */
3698 goto use_top;
3700 while ((map = av->binmap[block]) == 0);
3702 bin = bin_at (av, (block << BINMAPSHIFT));
3703 bit = 1;
3706 /* Advance to bin with set bit. There must be one. */
3707 while ((bit & map) == 0)
3709 bin = next_bin (bin);
3710 bit <<= 1;
3711 assert (bit != 0);
3714 /* Inspect the bin. It is likely to be non-empty */
3715 victim = last (bin);
3717 /* If a false alarm (empty bin), clear the bit. */
3718 if (victim == bin)
3720 av->binmap[block] = map &= ~bit; /* Write through */
3721 bin = next_bin (bin);
3722 bit <<= 1;
3725 else
3727 size = chunksize (victim);
3729 /* We know the first chunk in this bin is big enough to use. */
3730 assert ((unsigned long) (size) >= (unsigned long) (nb));
3732 remainder_size = size - nb;
3734 /* unlink */
3735 unlink (av, victim, bck, fwd);
3737 /* Exhaust */
3738 if (remainder_size < MINSIZE)
3740 set_inuse_bit_at_offset (victim, size);
3741 if (av != &main_arena)
3742 set_non_main_arena (victim);
3745 /* Split */
3746 else
3748 remainder = chunk_at_offset (victim, nb);
3750 /* We cannot assume the unsorted list is empty and therefore
3751 have to perform a complete insert here. */
3752 bck = unsorted_chunks (av);
3753 fwd = bck->fd;
3754 if (__glibc_unlikely (fwd->bk != bck))
3756 errstr = "malloc(): corrupted unsorted chunks 2";
3757 goto errout;
3759 remainder->bk = bck;
3760 remainder->fd = fwd;
3761 bck->fd = remainder;
3762 fwd->bk = remainder;
3764 /* advertise as last remainder */
3765 if (in_smallbin_range (nb))
3766 av->last_remainder = remainder;
3767 if (!in_smallbin_range (remainder_size))
3769 remainder->fd_nextsize = NULL;
3770 remainder->bk_nextsize = NULL;
3772 set_head (victim, nb | PREV_INUSE |
3773 (av != &main_arena ? NON_MAIN_ARENA : 0));
3774 set_head (remainder, remainder_size | PREV_INUSE);
3775 set_foot (remainder, remainder_size);
3777 check_malloced_chunk (av, victim, nb);
3778 void *p = chunk2mem (victim);
3779 alloc_perturb (p, bytes);
3780 return p;
3784 use_top:
3786 If large enough, split off the chunk bordering the end of memory
3787 (held in av->top). Note that this is in accord with the best-fit
3788 search rule. In effect, av->top is treated as larger (and thus
3789 less well fitting) than any other available chunk since it can
3790 be extended to be as large as necessary (up to system
3791 limitations).
3793 We require that av->top always exists (i.e., has size >=
3794 MINSIZE) after initialization, so if it would otherwise be
3795 exhausted by current request, it is replenished. (The main
3796 reason for ensuring it exists is that we may need MINSIZE space
3797 to put in fenceposts in sysmalloc.)
3800 victim = av->top;
3801 size = chunksize (victim);
3803 if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
3805 remainder_size = size - nb;
3806 remainder = chunk_at_offset (victim, nb);
3807 av->top = remainder;
3808 set_head (victim, nb | PREV_INUSE |
3809 (av != &main_arena ? NON_MAIN_ARENA : 0));
3810 set_head (remainder, remainder_size | PREV_INUSE);
3812 check_malloced_chunk (av, victim, nb);
3813 void *p = chunk2mem (victim);
3814 alloc_perturb (p, bytes);
3815 return p;
3818 /* When we are using atomic ops to free fast chunks we can get
3819 here for all block sizes. */
3820 else if (have_fastchunks (av))
3822 malloc_consolidate (av);
3823 /* restore original bin index */
3824 if (in_smallbin_range (nb))
3825 idx = smallbin_index (nb);
3826 else
3827 idx = largebin_index (nb);
3831 Otherwise, relay to handle system-dependent cases
3833 else
3835 void *p = sysmalloc (nb, av);
3836 if (p != NULL)
3837 alloc_perturb (p, bytes);
3838 return p;
3844 ------------------------------ free ------------------------------
3847 static void
3848 _int_free (mstate av, mchunkptr p, int have_lock)
3850 INTERNAL_SIZE_T size; /* its size */
3851 mfastbinptr *fb; /* associated fastbin */
3852 mchunkptr nextchunk; /* next contiguous chunk */
3853 INTERNAL_SIZE_T nextsize; /* its size */
3854 int nextinuse; /* true if nextchunk is used */
3855 INTERNAL_SIZE_T prevsize; /* size of previous contiguous chunk */
3856 mchunkptr bck; /* misc temp for linking */
3857 mchunkptr fwd; /* misc temp for linking */
3859 const char *errstr = NULL;
3860 int locked = 0;
3862 size = chunksize (p);
3864 /* Little security check which won't hurt performance: the
3865 allocator never wrapps around at the end of the address space.
3866 Therefore we can exclude some size values which might appear
3867 here by accident or by "design" from some intruder. */
3868 if (__builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0)
3869 || __builtin_expect (misaligned_chunk (p), 0))
3871 errstr = "free(): invalid pointer";
3872 errout:
3873 if (!have_lock && locked)
3874 __libc_lock_unlock (av->mutex);
3875 malloc_printerr (check_action, errstr, chunk2mem (p), av);
3876 return;
3878 /* We know that each chunk is at least MINSIZE bytes in size or a
3879 multiple of MALLOC_ALIGNMENT. */
3880 if (__glibc_unlikely (size < MINSIZE || !aligned_OK (size)))
3882 errstr = "free(): invalid size";
3883 goto errout;
3886 check_inuse_chunk(av, p);
3889 If eligible, place chunk on a fastbin so it can be found
3890 and used quickly in malloc.
3893 if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())
3895 #if TRIM_FASTBINS
3897 If TRIM_FASTBINS set, don't place chunks
3898 bordering top into fastbins
3900 && (chunk_at_offset(p, size) != av->top)
3901 #endif
3904 if (__builtin_expect (chunksize_nomask (chunk_at_offset (p, size))
3905 <= 2 * SIZE_SZ, 0)
3906 || __builtin_expect (chunksize (chunk_at_offset (p, size))
3907 >= av->system_mem, 0))
3909 /* We might not have a lock at this point and concurrent modifications
3910 of system_mem might have let to a false positive. Redo the test
3911 after getting the lock. */
3912 if (have_lock
3913 || ({ assert (locked == 0);
3914 __libc_lock_lock (av->mutex);
3915 locked = 1;
3916 chunksize_nomask (chunk_at_offset (p, size)) <= 2 * SIZE_SZ
3917 || chunksize (chunk_at_offset (p, size)) >= av->system_mem;
3920 errstr = "free(): invalid next size (fast)";
3921 goto errout;
3923 if (! have_lock)
3925 __libc_lock_unlock (av->mutex);
3926 locked = 0;
3930 free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
3932 set_fastchunks(av);
3933 unsigned int idx = fastbin_index(size);
3934 fb = &fastbin (av, idx);
3936 /* Atomically link P to its fastbin: P->FD = *FB; *FB = P; */
3937 mchunkptr old = *fb, old2;
3938 unsigned int old_idx = ~0u;
3941 /* Check that the top of the bin is not the record we are going to add
3942 (i.e., double free). */
3943 if (__builtin_expect (old == p, 0))
3945 errstr = "double free or corruption (fasttop)";
3946 goto errout;
3948 /* Check that size of fastbin chunk at the top is the same as
3949 size of the chunk that we are adding. We can dereference OLD
3950 only if we have the lock, otherwise it might have already been
3951 deallocated. See use of OLD_IDX below for the actual check. */
3952 if (have_lock && old != NULL)
3953 old_idx = fastbin_index(chunksize(old));
3954 p->fd = old2 = old;
3956 while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2);
3958 if (have_lock && old != NULL && __builtin_expect (old_idx != idx, 0))
3960 errstr = "invalid fastbin entry (free)";
3961 goto errout;
3966 Consolidate other non-mmapped chunks as they arrive.
3969 else if (!chunk_is_mmapped(p)) {
3970 if (! have_lock) {
3971 __libc_lock_lock (av->mutex);
3972 locked = 1;
3975 nextchunk = chunk_at_offset(p, size);
3977 /* Lightweight tests: check whether the block is already the
3978 top block. */
3979 if (__glibc_unlikely (p == av->top))
3981 errstr = "double free or corruption (top)";
3982 goto errout;
3984 /* Or whether the next chunk is beyond the boundaries of the arena. */
3985 if (__builtin_expect (contiguous (av)
3986 && (char *) nextchunk
3987 >= ((char *) av->top + chunksize(av->top)), 0))
3989 errstr = "double free or corruption (out)";
3990 goto errout;
3992 /* Or whether the block is actually not marked used. */
3993 if (__glibc_unlikely (!prev_inuse(nextchunk)))
3995 errstr = "double free or corruption (!prev)";
3996 goto errout;
3999 nextsize = chunksize(nextchunk);
4000 if (__builtin_expect (chunksize_nomask (nextchunk) <= 2 * SIZE_SZ, 0)
4001 || __builtin_expect (nextsize >= av->system_mem, 0))
4003 errstr = "free(): invalid next size (normal)";
4004 goto errout;
4007 free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
4009 /* consolidate backward */
4010 if (!prev_inuse(p)) {
4011 prevsize = prev_size (p);
4012 size += prevsize;
4013 p = chunk_at_offset(p, -((long) prevsize));
4014 unlink(av, p, bck, fwd);
4017 if (nextchunk != av->top) {
4018 /* get and clear inuse bit */
4019 nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
4021 /* consolidate forward */
4022 if (!nextinuse) {
4023 unlink(av, nextchunk, bck, fwd);
4024 size += nextsize;
4025 } else
4026 clear_inuse_bit_at_offset(nextchunk, 0);
4029 Place the chunk in unsorted chunk list. Chunks are
4030 not placed into regular bins until after they have
4031 been given one chance to be used in malloc.
4034 bck = unsorted_chunks(av);
4035 fwd = bck->fd;
4036 if (__glibc_unlikely (fwd->bk != bck))
4038 errstr = "free(): corrupted unsorted chunks";
4039 goto errout;
4041 p->fd = fwd;
4042 p->bk = bck;
4043 if (!in_smallbin_range(size))
4045 p->fd_nextsize = NULL;
4046 p->bk_nextsize = NULL;
4048 bck->fd = p;
4049 fwd->bk = p;
4051 set_head(p, size | PREV_INUSE);
4052 set_foot(p, size);
4054 check_free_chunk(av, p);
4058 If the chunk borders the current high end of memory,
4059 consolidate into top
4062 else {
4063 size += nextsize;
4064 set_head(p, size | PREV_INUSE);
4065 av->top = p;
4066 check_chunk(av, p);
4070 If freeing a large space, consolidate possibly-surrounding
4071 chunks. Then, if the total unused topmost memory exceeds trim
4072 threshold, ask malloc_trim to reduce top.
4074 Unless max_fast is 0, we don't know if there are fastbins
4075 bordering top, so we cannot tell for sure whether threshold
4076 has been reached unless fastbins are consolidated. But we
4077 don't want to consolidate on each free. As a compromise,
4078 consolidation is performed if FASTBIN_CONSOLIDATION_THRESHOLD
4079 is reached.
4082 if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
4083 if (have_fastchunks(av))
4084 malloc_consolidate(av);
4086 if (av == &main_arena) {
4087 #ifndef MORECORE_CANNOT_TRIM
4088 if ((unsigned long)(chunksize(av->top)) >=
4089 (unsigned long)(mp_.trim_threshold))
4090 systrim(mp_.top_pad, av);
4091 #endif
4092 } else {
4093 /* Always try heap_trim(), even if the top chunk is not
4094 large, because the corresponding heap might go away. */
4095 heap_info *heap = heap_for_ptr(top(av));
4097 assert(heap->ar_ptr == av);
4098 heap_trim(heap, mp_.top_pad);
4102 if (! have_lock) {
4103 assert (locked);
4104 __libc_lock_unlock (av->mutex);
4108 If the chunk was allocated via mmap, release via munmap().
4111 else {
4112 munmap_chunk (p);
4117 ------------------------- malloc_consolidate -------------------------
4119 malloc_consolidate is a specialized version of free() that tears
4120 down chunks held in fastbins. Free itself cannot be used for this
4121 purpose since, among other things, it might place chunks back onto
4122 fastbins. So, instead, we need to use a minor variant of the same
4123 code.
4125 Also, because this routine needs to be called the first time through
4126 malloc anyway, it turns out to be the perfect place to trigger
4127 initialization code.
4130 static void malloc_consolidate(mstate av)
4132 mfastbinptr* fb; /* current fastbin being consolidated */
4133 mfastbinptr* maxfb; /* last fastbin (for loop control) */
4134 mchunkptr p; /* current chunk being consolidated */
4135 mchunkptr nextp; /* next chunk to consolidate */
4136 mchunkptr unsorted_bin; /* bin header */
4137 mchunkptr first_unsorted; /* chunk to link to */
4139 /* These have same use as in free() */
4140 mchunkptr nextchunk;
4141 INTERNAL_SIZE_T size;
4142 INTERNAL_SIZE_T nextsize;
4143 INTERNAL_SIZE_T prevsize;
4144 int nextinuse;
4145 mchunkptr bck;
4146 mchunkptr fwd;
4149 If max_fast is 0, we know that av hasn't
4150 yet been initialized, in which case do so below
4153 if (get_max_fast () != 0) {
4154 clear_fastchunks(av);
4156 unsorted_bin = unsorted_chunks(av);
4159 Remove each chunk from fast bin and consolidate it, placing it
4160 then in unsorted bin. Among other reasons for doing this,
4161 placing in unsorted bin avoids needing to calculate actual bins
4162 until malloc is sure that chunks aren't immediately going to be
4163 reused anyway.
4166 maxfb = &fastbin (av, NFASTBINS - 1);
4167 fb = &fastbin (av, 0);
4168 do {
4169 p = atomic_exchange_acq (fb, NULL);
4170 if (p != 0) {
4171 do {
4172 check_inuse_chunk(av, p);
4173 nextp = p->fd;
4175 /* Slightly streamlined version of consolidation code in free() */
4176 size = chunksize (p);
4177 nextchunk = chunk_at_offset(p, size);
4178 nextsize = chunksize(nextchunk);
4180 if (!prev_inuse(p)) {
4181 prevsize = prev_size (p);
4182 size += prevsize;
4183 p = chunk_at_offset(p, -((long) prevsize));
4184 unlink(av, p, bck, fwd);
4187 if (nextchunk != av->top) {
4188 nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
4190 if (!nextinuse) {
4191 size += nextsize;
4192 unlink(av, nextchunk, bck, fwd);
4193 } else
4194 clear_inuse_bit_at_offset(nextchunk, 0);
4196 first_unsorted = unsorted_bin->fd;
4197 unsorted_bin->fd = p;
4198 first_unsorted->bk = p;
4200 if (!in_smallbin_range (size)) {
4201 p->fd_nextsize = NULL;
4202 p->bk_nextsize = NULL;
4205 set_head(p, size | PREV_INUSE);
4206 p->bk = unsorted_bin;
4207 p->fd = first_unsorted;
4208 set_foot(p, size);
4211 else {
4212 size += nextsize;
4213 set_head(p, size | PREV_INUSE);
4214 av->top = p;
4217 } while ( (p = nextp) != 0);
4220 } while (fb++ != maxfb);
4222 else {
4223 malloc_init_state(av);
4224 check_malloc_state(av);
4229 ------------------------------ realloc ------------------------------
4232 void*
4233 _int_realloc(mstate av, mchunkptr oldp, INTERNAL_SIZE_T oldsize,
4234 INTERNAL_SIZE_T nb)
4236 mchunkptr newp; /* chunk to return */
4237 INTERNAL_SIZE_T newsize; /* its size */
4238 void* newmem; /* corresponding user mem */
4240 mchunkptr next; /* next contiguous chunk after oldp */
4242 mchunkptr remainder; /* extra space at end of newp */
4243 unsigned long remainder_size; /* its size */
4245 mchunkptr bck; /* misc temp for linking */
4246 mchunkptr fwd; /* misc temp for linking */
4248 unsigned long copysize; /* bytes to copy */
4249 unsigned int ncopies; /* INTERNAL_SIZE_T words to copy */
4250 INTERNAL_SIZE_T* s; /* copy source */
4251 INTERNAL_SIZE_T* d; /* copy destination */
4253 const char *errstr = NULL;
4255 /* oldmem size */
4256 if (__builtin_expect (chunksize_nomask (oldp) <= 2 * SIZE_SZ, 0)
4257 || __builtin_expect (oldsize >= av->system_mem, 0))
4259 errstr = "realloc(): invalid old size";
4260 errout:
4261 malloc_printerr (check_action, errstr, chunk2mem (oldp), av);
4262 return NULL;
4265 check_inuse_chunk (av, oldp);
4267 /* All callers already filter out mmap'ed chunks. */
4268 assert (!chunk_is_mmapped (oldp));
4270 next = chunk_at_offset (oldp, oldsize);
4271 INTERNAL_SIZE_T nextsize = chunksize (next);
4272 if (__builtin_expect (chunksize_nomask (next) <= 2 * SIZE_SZ, 0)
4273 || __builtin_expect (nextsize >= av->system_mem, 0))
4275 errstr = "realloc(): invalid next size";
4276 goto errout;
4279 if ((unsigned long) (oldsize) >= (unsigned long) (nb))
4281 /* already big enough; split below */
4282 newp = oldp;
4283 newsize = oldsize;
4286 else
4288 /* Try to expand forward into top */
4289 if (next == av->top &&
4290 (unsigned long) (newsize = oldsize + nextsize) >=
4291 (unsigned long) (nb + MINSIZE))
4293 set_head_size (oldp, nb | (av != &main_arena ? NON_MAIN_ARENA : 0));
4294 av->top = chunk_at_offset (oldp, nb);
4295 set_head (av->top, (newsize - nb) | PREV_INUSE);
4296 check_inuse_chunk (av, oldp);
4297 return chunk2mem (oldp);
4300 /* Try to expand forward into next chunk; split off remainder below */
4301 else if (next != av->top &&
4302 !inuse (next) &&
4303 (unsigned long) (newsize = oldsize + nextsize) >=
4304 (unsigned long) (nb))
4306 newp = oldp;
4307 unlink (av, next, bck, fwd);
4310 /* allocate, copy, free */
4311 else
4313 newmem = _int_malloc (av, nb - MALLOC_ALIGN_MASK);
4314 if (newmem == 0)
4315 return 0; /* propagate failure */
4317 newp = mem2chunk (newmem);
4318 newsize = chunksize (newp);
4321 Avoid copy if newp is next chunk after oldp.
4323 if (newp == next)
4325 newsize += oldsize;
4326 newp = oldp;
4328 else
4331 Unroll copy of <= 36 bytes (72 if 8byte sizes)
4332 We know that contents have an odd number of
4333 INTERNAL_SIZE_T-sized words; minimally 3.
4336 copysize = oldsize - SIZE_SZ;
4337 s = (INTERNAL_SIZE_T *) (chunk2mem (oldp));
4338 d = (INTERNAL_SIZE_T *) (newmem);
4339 ncopies = copysize / sizeof (INTERNAL_SIZE_T);
4340 assert (ncopies >= 3);
4342 if (ncopies > 9)
4343 memcpy (d, s, copysize);
4345 else
4347 *(d + 0) = *(s + 0);
4348 *(d + 1) = *(s + 1);
4349 *(d + 2) = *(s + 2);
4350 if (ncopies > 4)
4352 *(d + 3) = *(s + 3);
4353 *(d + 4) = *(s + 4);
4354 if (ncopies > 6)
4356 *(d + 5) = *(s + 5);
4357 *(d + 6) = *(s + 6);
4358 if (ncopies > 8)
4360 *(d + 7) = *(s + 7);
4361 *(d + 8) = *(s + 8);
4367 _int_free (av, oldp, 1);
4368 check_inuse_chunk (av, newp);
4369 return chunk2mem (newp);
4374 /* If possible, free extra space in old or extended chunk */
4376 assert ((unsigned long) (newsize) >= (unsigned long) (nb));
4378 remainder_size = newsize - nb;
4380 if (remainder_size < MINSIZE) /* not enough extra to split off */
4382 set_head_size (newp, newsize | (av != &main_arena ? NON_MAIN_ARENA : 0));
4383 set_inuse_bit_at_offset (newp, newsize);
4385 else /* split remainder */
4387 remainder = chunk_at_offset (newp, nb);
4388 set_head_size (newp, nb | (av != &main_arena ? NON_MAIN_ARENA : 0));
4389 set_head (remainder, remainder_size | PREV_INUSE |
4390 (av != &main_arena ? NON_MAIN_ARENA : 0));
4391 /* Mark remainder as inuse so free() won't complain */
4392 set_inuse_bit_at_offset (remainder, remainder_size);
4393 _int_free (av, remainder, 1);