Revert "ChangeLogs: convert to utf-8"
[glibc.git] / malloc / malloc.c
blobd20d5955db4d814b73a5b1829d1bc7874c94024d
1 /* Malloc implementation for multiple threads without lock contention.
2 Copyright (C) 1996-2016 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4 Contributed by Wolfram Gloger <wg@malloc.de>
5 and Doug Lea <dl@cs.oswego.edu>, 2001.
7 The GNU C Library is free software; you can redistribute it and/or
8 modify it under the terms of the GNU Lesser General Public License as
9 published by the Free Software Foundation; either version 2.1 of the
10 License, or (at your option) any later version.
12 The GNU C Library is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 Lesser General Public License for more details.
17 You should have received a copy of the GNU Lesser General Public
18 License along with the GNU C Library; see the file COPYING.LIB. If
19 not, see <http://www.gnu.org/licenses/>. */
21 /*
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
176 MALLOC_ALIGNMENT MAX (2 * sizeof(INTERNAL_SIZE_T),
177 __alignof__ (long double))
179 Configuration and functionality options:
181 USE_PUBLIC_MALLOC_WRAPPERS NOT defined
182 USE_MALLOC_LOCK NOT defined
183 MALLOC_DEBUG NOT defined
184 REALLOC_ZERO_BYTES_FREES 1
185 TRIM_FASTBINS 0
187 Options for customizing MORECORE:
189 MORECORE sbrk
190 MORECORE_FAILURE -1
191 MORECORE_CONTIGUOUS 1
192 MORECORE_CANNOT_TRIM NOT defined
193 MORECORE_CLEARS 1
194 MMAP_AS_MORECORE_SIZE (1024 * 1024)
196 Tuning options that are also dynamically changeable via mallopt:
198 DEFAULT_MXFAST 64 (for 32bit), 128 (for 64bit)
199 DEFAULT_TRIM_THRESHOLD 128 * 1024
200 DEFAULT_TOP_PAD 0
201 DEFAULT_MMAP_THRESHOLD 128 * 1024
202 DEFAULT_MMAP_MAX 65536
204 There are several other #defined constants and macros that you
205 probably don't want to touch unless you are extending or adapting malloc. */
207 /*
208 void* is the pointer type that malloc should say it returns
209 */
211 #ifndef void
212 #define void void
213 #endif /*void*/
215 #include <stddef.h> /* for size_t */
216 #include <stdlib.h> /* for getenv(), abort() */
217 #include <unistd.h> /* for __libc_enable_secure */
219 #include <malloc-machine.h>
220 #include <malloc-sysdep.h>
222 #include <atomic.h>
223 #include <_itoa.h>
224 #include <bits/wordsize.h>
225 #include <sys/sysinfo.h>
227 #include <ldsodefs.h>
229 #include <unistd.h>
230 #include <stdio.h> /* needed for malloc_stats */
231 #include <errno.h>
233 #include <shlib-compat.h>
235 /* For uintptr_t. */
236 #include <stdint.h>
238 /* For va_arg, va_start, va_end. */
239 #include <stdarg.h>
241 /* For MIN, MAX, powerof2. */
242 #include <sys/param.h>
244 /* For ALIGN_UP et. al. */
245 #include <libc-internal.h>
248 /*
249 Debugging:
251 Because freed chunks may be overwritten with bookkeeping fields, this
252 malloc will often die when freed memory is overwritten by user
253 programs. This can be very effective (albeit in an annoying way)
254 in helping track down dangling pointers.
256 If you compile with -DMALLOC_DEBUG, a number of assertion checks are
257 enabled that will catch more memory errors. You probably won't be
258 able to make much sense of the actual assertion errors, but they
259 should help you locate incorrectly overwritten memory. The checking
260 is fairly extensive, and will slow down execution
261 noticeably. Calling malloc_stats or mallinfo with MALLOC_DEBUG set
262 will attempt to check every non-mmapped allocated and free chunk in
263 the course of computing the summmaries. (By nature, mmapped regions
264 cannot be checked very much automatically.)
266 Setting MALLOC_DEBUG may also be helpful if you are trying to modify
267 this code. The assertions in the check routines spell out in more
268 detail the assumptions and invariants underlying the algorithms.
270 Setting MALLOC_DEBUG does NOT provide an automated mechanism for
271 checking that all accesses to malloced memory stay within their
272 bounds. However, there are several add-ons and adaptations of this
273 or other mallocs available that do this.
274 */
276 #ifndef MALLOC_DEBUG
277 #define MALLOC_DEBUG 0
278 #endif
280 #ifdef NDEBUG
281 # define assert(expr) ((void) 0)
282 #else
283 # define assert(expr) \
284 ((expr) \
285 ? ((void) 0) \
286 : __malloc_assert (#expr, __FILE__, __LINE__, __func__))
288 extern const char *__progname;
290 static void
291 __malloc_assert (const char *assertion, const char *file, unsigned int line,
292 const char *function)
294 (void) __fxprintf (NULL, "%s%s%s:%u: %s%sAssertion `%s' failed.\n",
295 __progname, __progname[0] ? ": " : "",
296 file, line,
297 function ? function : "", function ? ": " : "",
298 assertion);
299 fflush (stderr);
300 abort ();
302 #endif
305 /*
306 INTERNAL_SIZE_T is the word-size used for internal bookkeeping
307 of chunk sizes.
309 The default version is the same as size_t.
311 While not strictly necessary, it is best to define this as an
312 unsigned type, even if size_t is a signed type. This may avoid some
313 artificial size limitations on some systems.
315 On a 64-bit machine, you may be able to reduce malloc overhead by
316 defining INTERNAL_SIZE_T to be a 32 bit `unsigned int' at the
317 expense of not being able to handle more than 2^32 of malloced
318 space. If this limitation is acceptable, you are encouraged to set
319 this unless you are on a platform requiring 16byte alignments. In
320 this case the alignment requirements turn out to negate any
321 potential advantages of decreasing size_t word size.
323 Implementors: Beware of the possible combinations of:
324 - INTERNAL_SIZE_T might be signed or unsigned, might be 32 or 64 bits,
325 and might be the same width as int or as long
326 - size_t might have different width and signedness as INTERNAL_SIZE_T
327 - int and long might be 32 or 64 bits, and might be the same width
328 To deal with this, most comparisons and difference computations
329 among INTERNAL_SIZE_Ts should cast them to unsigned long, being
330 aware of the fact that casting an unsigned int to a wider long does
331 not sign-extend. (This also makes checking for negative numbers
332 awkward.) Some of these casts result in harmless compiler warnings
333 on some systems.
334 */
336 #ifndef INTERNAL_SIZE_T
337 #define INTERNAL_SIZE_T size_t
338 #endif
340 /* The corresponding word size */
341 #define SIZE_SZ (sizeof(INTERNAL_SIZE_T))
344 /*
345 MALLOC_ALIGNMENT is the minimum alignment for malloc'ed chunks.
346 It must be a power of two at least 2 * SIZE_SZ, even on machines
347 for which smaller alignments would suffice. It may be defined as
348 larger than this though. Note however that code and data structures
349 are optimized for the case of 8-byte alignment.
350 */
353 #ifndef MALLOC_ALIGNMENT
354 # if !SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_16)
355 /* This is the correct definition when there is no past ABI to constrain it.
357 Among configurations with a past ABI constraint, it differs from
358 2*SIZE_SZ only on powerpc32. For the time being, changing this is
359 causing more compatibility problems due to malloc_get_state and
360 malloc_set_state than will returning blocks not adequately aligned for
361 long double objects under -mlong-double-128. */
363 # define MALLOC_ALIGNMENT (2 *SIZE_SZ < __alignof__ (long double) \
364 ? __alignof__ (long double) : 2 *SIZE_SZ)
365 # else
366 # define MALLOC_ALIGNMENT (2 *SIZE_SZ)
367 # endif
368 #endif
370 /* The corresponding bit mask value */
371 #define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1)
375 /*
376 REALLOC_ZERO_BYTES_FREES should be set if a call to
377 realloc with zero bytes should be the same as a call to free.
378 This is required by the C standard. Otherwise, since this malloc
379 returns a unique pointer for malloc(0), so does realloc(p, 0).
380 */
382 #ifndef REALLOC_ZERO_BYTES_FREES
383 #define REALLOC_ZERO_BYTES_FREES 1
384 #endif
386 /*
387 TRIM_FASTBINS controls whether free() of a very small chunk can
388 immediately lead to trimming. Setting to true (1) can reduce memory
389 footprint, but will almost always slow down programs that use a lot
390 of small chunks.
392 Define this only if you are willing to give up some speed to more
393 aggressively reduce system-level memory footprint when releasing
394 memory in programs that use many small chunks. You can get
395 essentially the same effect by setting MXFAST to 0, but this can
396 lead to even greater slowdowns in programs using many small chunks.
397 TRIM_FASTBINS is an in-between compile-time option, that disables
398 only those chunks bordering topmost memory from being placed in
399 fastbins.
400 */
402 #ifndef TRIM_FASTBINS
403 #define TRIM_FASTBINS 0
404 #endif
407 /* Definition for getting more memory from the OS. */
408 #define MORECORE (*__morecore)
409 #define MORECORE_FAILURE 0
410 void * __default_morecore (ptrdiff_t);
411 void *(*__morecore)(ptrdiff_t) = __default_morecore;
414 #include <string.h>
416 /*
417 MORECORE-related declarations. By default, rely on sbrk
418 */
421 /*
422 MORECORE is the name of the routine to call to obtain more memory
423 from the system. See below for general guidance on writing
424 alternative MORECORE functions, as well as a version for WIN32 and a
425 sample version for pre-OSX macos.
426 */
428 #ifndef MORECORE
429 #define MORECORE sbrk
430 #endif
432 /*
433 MORECORE_FAILURE is the value returned upon failure of MORECORE
434 as well as mmap. Since it cannot be an otherwise valid memory address,
435 and must reflect values of standard sys calls, you probably ought not
436 try to redefine it.
437 */
439 #ifndef MORECORE_FAILURE
440 #define MORECORE_FAILURE (-1)
441 #endif
443 /*
444 If MORECORE_CONTIGUOUS is true, take advantage of fact that
445 consecutive calls to MORECORE with positive arguments always return
446 contiguous increasing addresses. This is true of unix sbrk. Even
447 if not defined, when regions happen to be contiguous, malloc will
448 permit allocations spanning regions obtained from different
449 calls. But defining this when applicable enables some stronger
450 consistency checks and space efficiencies.
451 */
453 #ifndef MORECORE_CONTIGUOUS
454 #define MORECORE_CONTIGUOUS 1
455 #endif
457 /*
458 Define MORECORE_CANNOT_TRIM if your version of MORECORE
459 cannot release space back to the system when given negative
460 arguments. This is generally necessary only if you are using
461 a hand-crafted MORECORE function that cannot handle negative arguments.
462 */
464 /* #define MORECORE_CANNOT_TRIM */
466 /* MORECORE_CLEARS (default 1)
467 The degree to which the routine mapped to MORECORE zeroes out
468 memory: never (0), only for newly allocated space (1) or always
469 (2). The distinction between (1) and (2) is necessary because on
470 some systems, if the application first decrements and then
471 increments the break value, the contents of the reallocated space
472 are unspecified.
473 */
475 #ifndef MORECORE_CLEARS
476 # define MORECORE_CLEARS 1
477 #endif
480 /*
481 MMAP_AS_MORECORE_SIZE is the minimum mmap size argument to use if
482 sbrk fails, and mmap is used as a backup. The value must be a
483 multiple of page size. This backup strategy generally applies only
484 when systems have "holes" in address space, so sbrk cannot perform
485 contiguous expansion, but there is still space available on system.
486 On systems for which this is known to be useful (i.e. most linux
487 kernels), this occurs only when programs allocate huge amounts of
488 memory. Between this, and the fact that mmap regions tend to be
489 limited, the size should be large, to avoid too many mmap calls and
490 thus avoid running out of kernel resources. */
492 #ifndef MMAP_AS_MORECORE_SIZE
493 #define MMAP_AS_MORECORE_SIZE (1024 * 1024)
494 #endif
496 /*
497 Define HAVE_MREMAP to make realloc() use mremap() to re-allocate
498 large blocks.
499 */
501 #ifndef HAVE_MREMAP
502 #define HAVE_MREMAP 0
503 #endif
506 /*
507 This version of malloc supports the standard SVID/XPG mallinfo
508 routine that returns a struct containing usage properties and
509 statistics. It should work on any SVID/XPG compliant system that has
510 a /usr/include/malloc.h defining struct mallinfo. (If you'd like to
511 install such a thing yourself, cut out the preliminary declarations
512 as described above and below and save them in a malloc.h file. But
513 there's no compelling reason to bother to do this.)
515 The main declaration needed is the mallinfo struct that is returned
516 (by-copy) by mallinfo(). The SVID/XPG malloinfo struct contains a
517 bunch of fields that are not even meaningful in this version of
518 malloc. These fields are are instead filled by mallinfo() with
519 other numbers that might be of interest.
520 */
523 /* ---------- description of public routines ------------ */
525 /*
526 malloc(size_t n)
527 Returns a pointer to a newly allocated chunk of at least n bytes, or null
528 if no space is available. Additionally, on failure, errno is
529 set to ENOMEM on ANSI C systems.
531 If n is zero, malloc returns a minumum-sized chunk. (The minimum
532 size is 16 bytes on most 32bit systems, and 24 or 32 bytes on 64bit
533 systems.) On most systems, size_t is an unsigned type, so calls
534 with negative arguments are interpreted as requests for huge amounts
535 of space, which will often fail. The maximum supported value of n
536 differs across systems, but is in all cases less than the maximum
537 representable value of a size_t.
538 */
539 void* __libc_malloc(size_t);
540 libc_hidden_proto (__libc_malloc)
542 /*
543 free(void* p)
544 Releases the chunk of memory pointed to by p, that had been previously
545 allocated using malloc or a related routine such as realloc.
546 It has no effect if p is null. It can have arbitrary (i.e., bad!)
547 effects if p has already been freed.
549 Unless disabled (using mallopt), freeing very large spaces will
550 when possible, automatically trigger operations that give
551 back unused memory to the system, thus reducing program footprint.
552 */
553 void __libc_free(void*);
554 libc_hidden_proto (__libc_free)
556 /*
557 calloc(size_t n_elements, size_t element_size);
558 Returns a pointer to n_elements * element_size bytes, with all locations
559 set to zero.
560 */
561 void* __libc_calloc(size_t, size_t);
563 /*
564 realloc(void* p, size_t n)
565 Returns a pointer to a chunk of size n that contains the same data
566 as does chunk p up to the minimum of (n, p's size) bytes, or null
567 if no space is available.
569 The returned pointer may or may not be the same as p. The algorithm
570 prefers extending p when possible, otherwise it employs the
571 equivalent of a malloc-copy-free sequence.
573 If p is null, realloc is equivalent to malloc.
575 If space is not available, realloc returns null, errno is set (if on
576 ANSI) and p is NOT freed.
578 if n is for fewer bytes than already held by p, the newly unused
579 space is lopped off and freed if possible. Unless the #define
580 REALLOC_ZERO_BYTES_FREES is set, realloc with a size argument of
581 zero (re)allocates a minimum-sized chunk.
583 Large chunks that were internally obtained via mmap will always
584 be reallocated using malloc-copy-free sequences unless
585 the system supports MREMAP (currently only linux).
587 The old unix realloc convention of allowing the last-free'd chunk
588 to be used as an argument to realloc is not supported.
589 */
590 void* __libc_realloc(void*, size_t);
591 libc_hidden_proto (__libc_realloc)
593 /*
594 memalign(size_t alignment, size_t n);
595 Returns a pointer to a newly allocated chunk of n bytes, aligned
596 in accord with the alignment argument.
598 The alignment argument should be a power of two. If the argument is
599 not a power of two, the nearest greater power is used.
600 8-byte alignment is guaranteed by normal malloc calls, so don't
601 bother calling memalign with an argument of 8 or less.
603 Overreliance on memalign is a sure way to fragment space.
604 */
605 void* __libc_memalign(size_t, size_t);
606 libc_hidden_proto (__libc_memalign)
608 /*
609 valloc(size_t n);
610 Equivalent to memalign(pagesize, n), where pagesize is the page
611 size of the system. If the pagesize is unknown, 4096 is used.
612 */
613 void* __libc_valloc(size_t);
617 /*
618 mallopt(int parameter_number, int parameter_value)
619 Sets tunable parameters The format is to provide a
620 (parameter-number, parameter-value) pair. mallopt then sets the
621 corresponding parameter to the argument value if it can (i.e., so
622 long as the value is meaningful), and returns 1 if successful else
623 0. SVID/XPG/ANSI defines four standard param numbers for mallopt,
624 normally defined in malloc.h. Only one of these (M_MXFAST) is used
625 in this malloc. The others (M_NLBLKS, M_GRAIN, M_KEEP) don't apply,
626 so setting them has no effect. But this malloc also supports four
627 other options in mallopt. See below for details. Briefly, supported
628 parameters are as follows (listed defaults are for "typical"
629 configurations).
631 Symbol param # default allowed param values
632 M_MXFAST 1 64 0-80 (0 disables fastbins)
633 M_TRIM_THRESHOLD -1 128*1024 any (-1U disables trimming)
634 M_TOP_PAD -2 0 any
635 M_MMAP_THRESHOLD -3 128*1024 any (or 0 if no MMAP support)
636 M_MMAP_MAX -4 65536 any (0 disables use of mmap)
637 */
638 int __libc_mallopt(int, int);
639 libc_hidden_proto (__libc_mallopt)
642 /*
643 mallinfo()
644 Returns (by copy) a struct containing various summary statistics:
646 arena: current total non-mmapped bytes allocated from system
647 ordblks: the number of free chunks
648 smblks: the number of fastbin blocks (i.e., small chunks that
649 have been freed but not use resused or consolidated)
650 hblks: current number of mmapped regions
651 hblkhd: total bytes held in mmapped regions
652 usmblks: the maximum total allocated space. This will be greater
653 than current total if trimming has occurred.
654 fsmblks: total bytes held in fastbin blocks
655 uordblks: current total allocated space (normal or mmapped)
656 fordblks: total free space
657 keepcost: the maximum number of bytes that could ideally be released
658 back to system via malloc_trim. ("ideally" means that
659 it ignores page restrictions etc.)
661 Because these fields are ints, but internal bookkeeping may
662 be kept as longs, the reported values may wrap around zero and
663 thus be inaccurate.
664 */
665 struct mallinfo __libc_mallinfo(void);
668 /*
669 pvalloc(size_t n);
670 Equivalent to valloc(minimum-page-that-holds(n)), that is,
671 round up n to nearest pagesize.
672 */
673 void* __libc_pvalloc(size_t);
675 /*
676 malloc_trim(size_t pad);
678 If possible, gives memory back to the system (via negative
679 arguments to sbrk) if there is unused memory at the `high' end of
680 the malloc pool. You can call this after freeing large blocks of
681 memory to potentially reduce the system-level memory requirements
682 of a program. However, it cannot guarantee to reduce memory. Under
683 some allocation patterns, some large free blocks of memory will be
684 locked between two used chunks, so they cannot be given back to
685 the system.
687 The `pad' argument to malloc_trim represents the amount of free
688 trailing space to leave untrimmed. If this argument is zero,
689 only the minimum amount of memory to maintain internal data
690 structures will be left (one page or less). Non-zero arguments
691 can be supplied to maintain enough trailing space to service
692 future expected allocations without having to re-obtain memory
693 from the system.
695 Malloc_trim returns 1 if it actually released any memory, else 0.
696 On systems that do not support "negative sbrks", it will always
697 return 0.
698 */
699 int __malloc_trim(size_t);
701 /*
702 malloc_usable_size(void* p);
704 Returns the number of bytes you can actually use in
705 an allocated chunk, which may be more than you requested (although
706 often not) due to alignment and minimum size constraints.
707 You can use this many bytes without worrying about
708 overwriting other allocated objects. This is not a particularly great
709 programming practice. malloc_usable_size can be more useful in
710 debugging and assertions, for example:
712 p = malloc(n);
713 assert(malloc_usable_size(p) >= 256);
715 */
716 size_t __malloc_usable_size(void*);
718 /*
719 malloc_stats();
720 Prints on stderr the amount of space obtained from the system (both
721 via sbrk and mmap), the maximum amount (which may be more than
722 current if malloc_trim and/or munmap got called), and the current
723 number of bytes allocated via malloc (or realloc, etc) but not yet
724 freed. Note that this is the number of bytes allocated, not the
725 number requested. It will be larger than the number requested
726 because of alignment and bookkeeping overhead. Because it includes
727 alignment wastage as being in use, this figure may be greater than
728 zero even when no user-level chunks are allocated.
730 The reported current and maximum system memory can be inaccurate if
731 a program makes other calls to system memory allocation functions
732 (normally sbrk) outside of malloc.
734 malloc_stats prints only the most commonly interesting statistics.
735 More information can be obtained by calling mallinfo.
737 */
738 void __malloc_stats(void);
740 /*
741 malloc_get_state(void);
743 Returns the state of all malloc variables in an opaque data
744 structure.
745 */
746 void* __malloc_get_state(void);
748 /*
749 malloc_set_state(void* state);
751 Restore the state of all malloc variables from data obtained with
752 malloc_get_state().
753 */
754 int __malloc_set_state(void*);
756 /*
757 posix_memalign(void **memptr, size_t alignment, size_t size);
759 POSIX wrapper like memalign(), checking for validity of size.
760 */
761 int __posix_memalign(void **, size_t, size_t);
763 /* mallopt tuning options */
765 /*
766 M_MXFAST is the maximum request size used for "fastbins", special bins
767 that hold returned chunks without consolidating their spaces. This
768 enables future requests for chunks of the same size to be handled
769 very quickly, but can increase fragmentation, and thus increase the
770 overall memory footprint of a program.
772 This malloc manages fastbins very conservatively yet still
773 efficiently, so fragmentation is rarely a problem for values less
774 than or equal to the default. The maximum supported value of MXFAST
775 is 80. You wouldn't want it any higher than this anyway. Fastbins
776 are designed especially for use with many small structs, objects or
777 strings -- the default handles structs/objects/arrays with sizes up
778 to 8 4byte fields, or small strings representing words, tokens,
779 etc. Using fastbins for larger objects normally worsens
780 fragmentation without improving speed.
782 M_MXFAST is set in REQUEST size units. It is internally used in
783 chunksize units, which adds padding and alignment. You can reduce
784 M_MXFAST to 0 to disable all use of fastbins. This causes the malloc
785 algorithm to be a closer approximation of fifo-best-fit in all cases,
786 not just for larger requests, but will generally cause it to be
787 slower.
788 */
791 /* M_MXFAST is a standard SVID/XPG tuning option, usually listed in malloc.h */
792 #ifndef M_MXFAST
793 #define M_MXFAST 1
794 #endif
796 #ifndef DEFAULT_MXFAST
797 #define DEFAULT_MXFAST (64 * SIZE_SZ / 4)
798 #endif
801 /*
802 M_TRIM_THRESHOLD is the maximum amount of unused top-most memory
803 to keep before releasing via malloc_trim in free().
805 Automatic trimming is mainly useful in long-lived programs.
806 Because trimming via sbrk can be slow on some systems, and can
807 sometimes be wasteful (in cases where programs immediately
808 afterward allocate more large chunks) the value should be high
809 enough so that your overall system performance would improve by
810 releasing this much memory.
812 The trim threshold and the mmap control parameters (see below)
813 can be traded off with one another. Trimming and mmapping are
814 two different ways of releasing unused memory back to the
815 system. Between these two, it is often possible to keep
816 system-level demands of a long-lived program down to a bare
817 minimum. For example, in one test suite of sessions measuring
818 the XF86 X server on Linux, using a trim threshold of 128K and a
819 mmap threshold of 192K led to near-minimal long term resource
820 consumption.
822 If you are using this malloc in a long-lived program, it should
823 pay to experiment with these values. As a rough guide, you
824 might set to a value close to the average size of a process
825 (program) running on your system. Releasing this much memory
826 would allow such a process to run in memory. Generally, it's
827 worth it to tune for trimming rather tham memory mapping when a
828 program undergoes phases where several large chunks are
829 allocated and released in ways that can reuse each other's
830 storage, perhaps mixed with phases where there are no such
831 chunks at all. And in well-behaved long-lived programs,
832 controlling release of large blocks via trimming versus mapping
833 is usually faster.
835 However, in most programs, these parameters serve mainly as
836 protection against the system-level effects of carrying around
837 massive amounts of unneeded memory. Since frequent calls to
838 sbrk, mmap, and munmap otherwise degrade performance, the default
839 parameters are set to relatively high values that serve only as
840 safeguards.
842 The trim value It must be greater than page size to have any useful
843 effect. To disable trimming completely, you can set to
844 (unsigned long)(-1)
846 Trim settings interact with fastbin (MXFAST) settings: Unless
847 TRIM_FASTBINS is defined, automatic trimming never takes place upon
848 freeing a chunk with size less than or equal to MXFAST. Trimming is
849 instead delayed until subsequent freeing of larger chunks. However,
850 you can still force an attempted trim by calling malloc_trim.
852 Also, trimming is not generally possible in cases where
853 the main arena is obtained via mmap.
855 Note that the trick some people use of mallocing a huge space and
856 then freeing it at program startup, in an attempt to reserve system
857 memory, doesn't have the intended effect under automatic trimming,
858 since that memory will immediately be returned to the system.
859 */
861 #define M_TRIM_THRESHOLD -1
863 #ifndef DEFAULT_TRIM_THRESHOLD
864 #define DEFAULT_TRIM_THRESHOLD (128 * 1024)
865 #endif
867 /*
868 M_TOP_PAD is the amount of extra `padding' space to allocate or
869 retain whenever sbrk is called. It is used in two ways internally:
871 * When sbrk is called to extend the top of the arena to satisfy
872 a new malloc request, this much padding is added to the sbrk
873 request.
875 * When malloc_trim is called automatically from free(),
876 it is used as the `pad' argument.
878 In both cases, the actual amount of padding is rounded
879 so that the end of the arena is always a system page boundary.
881 The main reason for using padding is to avoid calling sbrk so
882 often. Having even a small pad greatly reduces the likelihood
883 that nearly every malloc request during program start-up (or
884 after trimming) will invoke sbrk, which needlessly wastes
885 time.
887 Automatic rounding-up to page-size units is normally sufficient
888 to avoid measurable overhead, so the default is 0. However, in
889 systems where sbrk is relatively slow, it can pay to increase
890 this value, at the expense of carrying around more memory than
891 the program needs.
892 */
894 #define M_TOP_PAD -2
896 #ifndef DEFAULT_TOP_PAD
897 #define DEFAULT_TOP_PAD (0)
898 #endif
900 /*
901 MMAP_THRESHOLD_MAX and _MIN are the bounds on the dynamically
902 adjusted MMAP_THRESHOLD.
903 */
905 #ifndef DEFAULT_MMAP_THRESHOLD_MIN
906 #define DEFAULT_MMAP_THRESHOLD_MIN (128 * 1024)
907 #endif
909 #ifndef DEFAULT_MMAP_THRESHOLD_MAX
910 /* For 32-bit platforms we cannot increase the maximum mmap
911 threshold much because it is also the minimum value for the
912 maximum heap size and its alignment. Going above 512k (i.e., 1M
913 for new heaps) wastes too much address space. */
914 # if __WORDSIZE == 32
915 # define DEFAULT_MMAP_THRESHOLD_MAX (512 * 1024)
916 # else
917 # define DEFAULT_MMAP_THRESHOLD_MAX (4 * 1024 * 1024 * sizeof(long))
918 # endif
919 #endif
921 /*
922 M_MMAP_THRESHOLD is the request size threshold for using mmap()
923 to service a request. Requests of at least this size that cannot
924 be allocated using already-existing space will be serviced via mmap.
925 (If enough normal freed space already exists it is used instead.)
927 Using mmap segregates relatively large chunks of memory so that
928 they can be individually obtained and released from the host
929 system. A request serviced through mmap is never reused by any
930 other request (at least not directly; the system may just so
931 happen to remap successive requests to the same locations).
933 Segregating space in this way has the benefits that:
935 1. Mmapped space can ALWAYS be individually released back
936 to the system, which helps keep the system level memory
937 demands of a long-lived program low.
938 2. Mapped memory can never become `locked' between
939 other chunks, as can happen with normally allocated chunks, which
940 means that even trimming via malloc_trim would not release them.
941 3. On some systems with "holes" in address spaces, mmap can obtain
942 memory that sbrk cannot.
944 However, it has the disadvantages that:
946 1. The space cannot be reclaimed, consolidated, and then
947 used to service later requests, as happens with normal chunks.
948 2. It can lead to more wastage because of mmap page alignment
949 requirements
950 3. It causes malloc performance to be more dependent on host
951 system memory management support routines which may vary in
952 implementation quality and may impose arbitrary
953 limitations. Generally, servicing a request via normal
954 malloc steps is faster than going through a system's mmap.
956 The advantages of mmap nearly always outweigh disadvantages for
957 "large" chunks, but the value of "large" varies across systems. The
958 default is an empirically derived value that works well in most
959 systems.
962 Update in 2006:
963 The above was written in 2001. Since then the world has changed a lot.
964 Memory got bigger. Applications got bigger. The virtual address space
965 layout in 32 bit linux changed.
967 In the new situation, brk() and mmap space is shared and there are no
968 artificial limits on brk size imposed by the kernel. What is more,
969 applications have started using transient allocations larger than the
970 128Kb as was imagined in 2001.
972 The price for mmap is also high now; each time glibc mmaps from the
973 kernel, the kernel is forced to zero out the memory it gives to the
974 application. Zeroing memory is expensive and eats a lot of cache and
975 memory bandwidth. This has nothing to do with the efficiency of the
976 virtual memory system, by doing mmap the kernel just has no choice but
977 to zero.
979 In 2001, the kernel had a maximum size for brk() which was about 800
980 megabytes on 32 bit x86, at that point brk() would hit the first
981 mmaped shared libaries and couldn't expand anymore. With current 2.6
982 kernels, the VA space layout is different and brk() and mmap
983 both can span the entire heap at will.
985 Rather than using a static threshold for the brk/mmap tradeoff,
986 we are now using a simple dynamic one. The goal is still to avoid
987 fragmentation. The old goals we kept are
988 1) try to get the long lived large allocations to use mmap()
989 2) really large allocations should always use mmap()
990 and we're adding now:
991 3) transient allocations should use brk() to avoid forcing the kernel
992 having to zero memory over and over again
994 The implementation works with a sliding threshold, which is by default
995 limited to go between 128Kb and 32Mb (64Mb for 64 bitmachines) and starts
996 out at 128Kb as per the 2001 default.
998 This allows us to satisfy requirement 1) under the assumption that long
999 lived allocations are made early in the process' lifespan, before it has
1000 started doing dynamic allocations of the same size (which will
1001 increase the threshold).
1003 The upperbound on the threshold satisfies requirement 2)
1005 The threshold goes up in value when the application frees memory that was
1006 allocated with the mmap allocator. The idea is that once the application
1007 starts freeing memory of a certain size, it's highly probable that this is
1008 a size the application uses for transient allocations. This estimator
1009 is there to satisfy the new third requirement.
1011 */
1013 #define M_MMAP_THRESHOLD -3
1015 #ifndef DEFAULT_MMAP_THRESHOLD
1016 #define DEFAULT_MMAP_THRESHOLD DEFAULT_MMAP_THRESHOLD_MIN
1017 #endif
1019 /*
1020 M_MMAP_MAX is the maximum number of requests to simultaneously
1021 service using mmap. This parameter exists because
1022 some systems have a limited number of internal tables for
1023 use by mmap, and using more than a few of them may degrade
1024 performance.
1026 The default is set to a value that serves only as a safeguard.
1027 Setting to 0 disables use of mmap for servicing large requests.
1028 */
1030 #define M_MMAP_MAX -4
1032 #ifndef DEFAULT_MMAP_MAX
1033 #define DEFAULT_MMAP_MAX (65536)
1034 #endif
1036 #include <malloc.h>
1038 #ifndef RETURN_ADDRESS
1039 #define RETURN_ADDRESS(X_) (NULL)
1040 #endif
1042 /* On some platforms we can compile internal, not exported functions better.
1043 Let the environment provide a macro and define it to be empty if it
1044 is not available. */
1045 #ifndef internal_function
1046 # define internal_function
1047 #endif
1049 /* Forward declarations. */
1050 struct malloc_chunk;
1051 typedef struct malloc_chunk* mchunkptr;
1053 /* Internal routines. */
1055 static void* _int_malloc(mstate, size_t);
1056 static void _int_free(mstate, mchunkptr, int);
1057 static void* _int_realloc(mstate, mchunkptr, INTERNAL_SIZE_T,
1058 INTERNAL_SIZE_T);
1059 static void* _int_memalign(mstate, size_t, size_t);
1060 static void* _mid_memalign(size_t, size_t, void *);
1062 static void malloc_printerr(int action, const char *str, void *ptr, mstate av);
1064 static void* internal_function mem2mem_check(void *p, size_t sz);
1065 static int internal_function top_check(void);
1066 static void internal_function munmap_chunk(mchunkptr p);
1067 #if HAVE_MREMAP
1068 static mchunkptr internal_function mremap_chunk(mchunkptr p, size_t new_size);
1069 #endif
1071 static void* malloc_check(size_t sz, const void *caller);
1072 static void free_check(void* mem, const void *caller);
1073 static void* realloc_check(void* oldmem, size_t bytes,
1074 const void *caller);
1075 static void* memalign_check(size_t alignment, size_t bytes,
1076 const void *caller);
1077 #ifndef NO_THREADS
1078 static void* malloc_atfork(size_t sz, const void *caller);
1079 static void free_atfork(void* mem, const void *caller);
1080 #endif
1082 /* ------------------ MMAP support ------------------ */
1085 #include <fcntl.h>
1086 #include <sys/mman.h>
1088 #if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
1089 # define MAP_ANONYMOUS MAP_ANON
1090 #endif
1092 #ifndef MAP_NORESERVE
1093 # define MAP_NORESERVE 0
1094 #endif
1096 #define MMAP(addr, size, prot, flags) \
1097 __mmap((addr), (size), (prot), (flags)|MAP_ANONYMOUS|MAP_PRIVATE, -1, 0)
1100 /*
1101 ----------------------- Chunk representations -----------------------
1102 */
1105 /*
1106 This struct declaration is misleading (but accurate and necessary).
1107 It declares a "view" into memory allowing access to necessary
1108 fields at known offsets from a given base. See explanation below.
1109 */
1111 struct malloc_chunk {
1113 INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
1114 INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
1116 struct malloc_chunk* fd; /* double links -- used only if free. */
1117 struct malloc_chunk* bk;
1119 /* Only used for large blocks: pointer to next larger size. */
1120 struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
1121 struct malloc_chunk* bk_nextsize;
1122 };
1125 /*
1126 malloc_chunk details:
1128 (The following includes lightly edited explanations by Colin Plumb.)
1130 Chunks of memory are maintained using a `boundary tag' method as
1131 described in e.g., Knuth or Standish. (See the paper by Paul
1132 Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a
1133 survey of such techniques.) Sizes of free chunks are stored both
1134 in the front of each chunk and at the end. This makes
1135 consolidating fragmented chunks into bigger chunks very fast. The
1136 size fields also hold bits representing whether chunks are free or
1137 in use.
1139 An allocated chunk looks like this:
1142 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1143 | Size of previous chunk, if allocated | |
1144 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1145 | Size of chunk, in bytes |M|P|
1146 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1147 | User data starts here... .
1148 . .
1149 . (malloc_usable_size() bytes) .
1150 . |
1151 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1152 | Size of chunk |
1153 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1156 Where "chunk" is the front of the chunk for the purpose of most of
1157 the malloc code, but "mem" is the pointer that is returned to the
1158 user. "Nextchunk" is the beginning of the next contiguous chunk.
1160 Chunks always begin on even word boundaries, so the mem portion
1161 (which is returned to the user) is also on an even word boundary, and
1162 thus at least double-word aligned.
1164 Free chunks are stored in circular doubly-linked lists, and look like this:
1166 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1167 | Size of previous chunk |
1168 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1169 `head:' | Size of chunk, in bytes |P|
1170 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1171 | Forward pointer to next chunk in list |
1172 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1173 | Back pointer to previous chunk in list |
1174 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1175 | Unused space (may be 0 bytes long) .
1176 . .
1177 . |
1178 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1179 `foot:' | Size of chunk, in bytes |
1180 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1182 The P (PREV_INUSE) bit, stored in the unused low-order bit of the
1183 chunk size (which is always a multiple of two words), is an in-use
1184 bit for the *previous* chunk. If that bit is *clear*, then the
1185 word before the current chunk size contains the previous chunk
1186 size, and can be used to find the front of the previous chunk.
1187 The very first chunk allocated always has this bit set,
1188 preventing access to non-existent (or non-owned) memory. If
1189 prev_inuse is set for any given chunk, then you CANNOT determine
1190 the size of the previous chunk, and might even get a memory
1191 addressing fault when trying to do so.
1193 Note that the `foot' of the current chunk is actually represented
1194 as the prev_size of the NEXT chunk. This makes it easier to
1195 deal with alignments etc but can be very confusing when trying
1196 to extend or adapt this code.
1198 The two exceptions to all this are
1200 1. The special chunk `top' doesn't bother using the
1201 trailing size field since there is no next contiguous chunk
1202 that would have to index off it. After initialization, `top'
1203 is forced to always exist. If it would become less than
1204 MINSIZE bytes long, it is replenished.
1206 2. Chunks allocated via mmap, which have the second-lowest-order
1207 bit M (IS_MMAPPED) set in their size fields. Because they are
1208 allocated one-by-one, each must contain its own trailing size field.
1210 */
1212 /*
1213 ---------- Size and alignment checks and conversions ----------
1214 */
1216 /* conversion from malloc headers to user pointers, and back */
1218 #define chunk2mem(p) ((void*)((char*)(p) + 2*SIZE_SZ))
1219 #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))
1221 /* The smallest possible chunk */
1222 #define MIN_CHUNK_SIZE (offsetof(struct malloc_chunk, fd_nextsize))
1224 /* The smallest size we can malloc is an aligned minimal chunk */
1226 #define MINSIZE \
1227 (unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))
1229 /* Check if m has acceptable alignment */
1231 #define aligned_OK(m) (((unsigned long)(m) & MALLOC_ALIGN_MASK) == 0)
1233 #define misaligned_chunk(p) \
1234 ((uintptr_t)(MALLOC_ALIGNMENT == 2 * SIZE_SZ ? (p) : chunk2mem (p)) \
1235 & MALLOC_ALIGN_MASK)
1238 /*
1239 Check if a request is so large that it would wrap around zero when
1240 padded and aligned. To simplify some other code, the bound is made
1241 low enough so that adding MINSIZE will also not wrap around zero.
1242 */
1244 #define REQUEST_OUT_OF_RANGE(req) \
1245 ((unsigned long) (req) >= \
1246 (unsigned long) (INTERNAL_SIZE_T) (-2 * MINSIZE))
1248 /* pad request bytes into a usable size -- internal version */
1250 #define request2size(req) \
1251 (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ? \
1252 MINSIZE : \
1253 ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
1255 /* Same, except also perform argument check */
1257 #define checked_request2size(req, sz) \
1258 if (REQUEST_OUT_OF_RANGE (req)) { \
1259 __set_errno (ENOMEM); \
1260 return 0; \
1261 } \
1262 (sz) = request2size (req);
1264 /*
1265 --------------- Physical chunk operations ---------------
1266 */
1269 /* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
1270 #define PREV_INUSE 0x1
1272 /* extract inuse bit of previous chunk */
1273 #define prev_inuse(p) ((p)->size & PREV_INUSE)
1276 /* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */
1277 #define IS_MMAPPED 0x2
1279 /* check for mmap()'ed chunk */
1280 #define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)
1283 /* size field is or'ed with NON_MAIN_ARENA if the chunk was obtained
1284 from a non-main arena. This is only set immediately before handing
1285 the chunk to the user, if necessary. */
1286 #define NON_MAIN_ARENA 0x4
1288 /* check for chunk from non-main arena */
1289 #define chunk_non_main_arena(p) ((p)->size & NON_MAIN_ARENA)
1292 /*
1293 Bits to mask off when extracting size
1295 Note: IS_MMAPPED is intentionally not masked off from size field in
1296 macros for which mmapped chunks should never be seen. This should
1297 cause helpful core dumps to occur if it is tried by accident by
1298 people extending or adapting this malloc.
1299 */
1300 #define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
1302 /* Get size, ignoring use bits */
1303 #define chunksize(p) ((p)->size & ~(SIZE_BITS))
1306 /* Ptr to next physical malloc_chunk. */
1307 #define next_chunk(p) ((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))
1309 /* Ptr to previous physical malloc_chunk */
1310 #define prev_chunk(p) ((mchunkptr) (((char *) (p)) - ((p)->prev_size)))
1312 /* Treat space at ptr + offset as a chunk */
1313 #define chunk_at_offset(p, s) ((mchunkptr) (((char *) (p)) + (s)))
1315 /* extract p's inuse bit */
1316 #define inuse(p) \
1317 ((((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))->size) & PREV_INUSE)
1319 /* set/clear chunk as being inuse without otherwise disturbing */
1320 #define set_inuse(p) \
1321 ((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))->size |= PREV_INUSE
1323 #define clear_inuse(p) \
1324 ((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))->size &= ~(PREV_INUSE)
1327 /* check/set/clear inuse bits in known places */
1328 #define inuse_bit_at_offset(p, s) \
1329 (((mchunkptr) (((char *) (p)) + (s)))->size & PREV_INUSE)
1331 #define set_inuse_bit_at_offset(p, s) \
1332 (((mchunkptr) (((char *) (p)) + (s)))->size |= PREV_INUSE)
1334 #define clear_inuse_bit_at_offset(p, s) \
1335 (((mchunkptr) (((char *) (p)) + (s)))->size &= ~(PREV_INUSE))
1338 /* Set size at head, without disturbing its use bit */
1339 #define set_head_size(p, s) ((p)->size = (((p)->size & SIZE_BITS) | (s)))
1341 /* Set size/use field */
1342 #define set_head(p, s) ((p)->size = (s))
1344 /* Set size at footer (only when chunk is not in use) */
1345 #define set_foot(p, s) (((mchunkptr) ((char *) (p) + (s)))->prev_size = (s))
1348 /*
1349 -------------------- Internal data structures --------------------
1351 All internal state is held in an instance of malloc_state defined
1352 below. There are no other static variables, except in two optional
1353 cases:
1354 * If USE_MALLOC_LOCK is defined, the mALLOC_MUTEx declared above.
1355 * If mmap doesn't support MAP_ANONYMOUS, a dummy file descriptor
1356 for mmap.
1358 Beware of lots of tricks that minimize the total bookkeeping space
1359 requirements. The result is a little over 1K bytes (for 4byte
1360 pointers and size_t.)
1361 */
1363 /*
1364 Bins
1366 An array of bin headers for free chunks. Each bin is doubly
1367 linked. The bins are approximately proportionally (log) spaced.
1368 There are a lot of these bins (128). This may look excessive, but
1369 works very well in practice. Most bins hold sizes that are
1370 unusual as malloc request sizes, but are more usual for fragments
1371 and consolidated sets of chunks, which is what these bins hold, so
1372 they can be found quickly. All procedures maintain the invariant
1373 that no consolidated chunk physically borders another one, so each
1374 chunk in a list is known to be preceeded and followed by either
1375 inuse chunks or the ends of memory.
1377 Chunks in bins are kept in size order, with ties going to the
1378 approximately least recently used chunk. Ordering isn't needed
1379 for the small bins, which all contain the same-sized chunks, but
1380 facilitates best-fit allocation for larger chunks. These lists
1381 are just sequential. Keeping them in order almost never requires
1382 enough traversal to warrant using fancier ordered data
1383 structures.
1385 Chunks of the same size are linked with the most
1386 recently freed at the front, and allocations are taken from the
1387 back. This results in LRU (FIFO) allocation order, which tends
1388 to give each chunk an equal opportunity to be consolidated with
1389 adjacent freed chunks, resulting in larger free chunks and less
1390 fragmentation.
1392 To simplify use in double-linked lists, each bin header acts
1393 as a malloc_chunk. This avoids special-casing for headers.
1394 But to conserve space and improve locality, we allocate
1395 only the fd/bk pointers of bins, and then use repositioning tricks
1396 to treat these as the fields of a malloc_chunk*.
1397 */
1399 typedef struct malloc_chunk *mbinptr;
1401 /* addressing -- note that bin_at(0) does not exist */
1402 #define bin_at(m, i) \
1403 (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2])) \
1404 - offsetof (struct malloc_chunk, fd))
1406 /* analog of ++bin */
1407 #define next_bin(b) ((mbinptr) ((char *) (b) + (sizeof (mchunkptr) << 1)))
1409 /* Reminders about list directionality within bins */
1410 #define first(b) ((b)->fd)
1411 #define last(b) ((b)->bk)
1413 /* Take a chunk off a bin list */
1414 #define unlink(AV, P, BK, FD) { \
1415 FD = P->fd; \
1416 BK = P->bk; \
1417 if (__builtin_expect (FD->bk != P || BK->fd != P, 0)) \
1418 malloc_printerr (check_action, "corrupted double-linked list", P, AV); \
1419 else { \
1420 FD->bk = BK; \
1421 BK->fd = FD; \
1422 if (!in_smallbin_range (P->size) \
1423 && __builtin_expect (P->fd_nextsize != NULL, 0)) { \
1424 if (__builtin_expect (P->fd_nextsize->bk_nextsize != P, 0) \
1425 || __builtin_expect (P->bk_nextsize->fd_nextsize != P, 0)) \
1426 malloc_printerr (check_action, \
1427 "corrupted double-linked list (not small)", \
1428 P, AV); \
1429 if (FD->fd_nextsize == NULL) { \
1430 if (P->fd_nextsize == P) \
1431 FD->fd_nextsize = FD->bk_nextsize = FD; \
1432 else { \
1433 FD->fd_nextsize = P->fd_nextsize; \
1434 FD->bk_nextsize = P->bk_nextsize; \
1435 P->fd_nextsize->bk_nextsize = FD; \
1436 P->bk_nextsize->fd_nextsize = FD; \
1437 } \
1438 } else { \
1439 P->fd_nextsize->bk_nextsize = P->bk_nextsize; \
1440 P->bk_nextsize->fd_nextsize = P->fd_nextsize; \
1441 } \
1442 } \
1443 } \
1446 /*
1447 Indexing
1449 Bins for sizes < 512 bytes contain chunks of all the same size, spaced
1450 8 bytes apart. Larger bins are approximately logarithmically spaced:
1452 64 bins of size 8
1453 32 bins of size 64
1454 16 bins of size 512
1455 8 bins of size 4096
1456 4 bins of size 32768
1457 2 bins of size 262144
1458 1 bin of size what's left
1460 There is actually a little bit of slop in the numbers in bin_index
1461 for the sake of speed. This makes no difference elsewhere.
1463 The bins top out around 1MB because we expect to service large
1464 requests via mmap.
1466 Bin 0 does not exist. Bin 1 is the unordered list; if that would be
1467 a valid chunk size the small bins are bumped up one.
1468 */
1470 #define NBINS 128
1471 #define NSMALLBINS 64
1472 #define SMALLBIN_WIDTH MALLOC_ALIGNMENT
1473 #define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ)
1474 #define MIN_LARGE_SIZE ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)
1476 #define in_smallbin_range(sz) \
1477 ((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)
1479 #define smallbin_index(sz) \
1480 ((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\
1481 + SMALLBIN_CORRECTION)
1483 #define largebin_index_32(sz) \
1484 (((((unsigned long) (sz)) >> 6) <= 38) ? 56 + (((unsigned long) (sz)) >> 6) :\
1485 ((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :\
1486 ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
1487 ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
1488 ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
1489 126)
1491 #define largebin_index_32_big(sz) \
1492 (((((unsigned long) (sz)) >> 6) <= 45) ? 49 + (((unsigned long) (sz)) >> 6) :\
1493 ((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :\
1494 ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
1495 ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
1496 ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
1497 126)
1499 // XXX It remains to be seen whether it is good to keep the widths of
1500 // XXX the buckets the same or whether it should be scaled by a factor
1501 // XXX of two as well.
1502 #define largebin_index_64(sz) \
1503 (((((unsigned long) (sz)) >> 6) <= 48) ? 48 + (((unsigned long) (sz)) >> 6) :\
1504 ((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :\
1505 ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
1506 ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
1507 ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
1508 126)
1510 #define largebin_index(sz) \
1511 (SIZE_SZ == 8 ? largebin_index_64 (sz) \
1512 : MALLOC_ALIGNMENT == 16 ? largebin_index_32_big (sz) \
1513 : largebin_index_32 (sz))
1515 #define bin_index(sz) \
1516 ((in_smallbin_range (sz)) ? smallbin_index (sz) : largebin_index (sz))
1519 /*
1520 Unsorted chunks
1522 All remainders from chunk splits, as well as all returned chunks,
1523 are first placed in the "unsorted" bin. They are then placed
1524 in regular bins after malloc gives them ONE chance to be used before
1525 binning. So, basically, the unsorted_chunks list acts as a queue,
1526 with chunks being placed on it in free (and malloc_consolidate),
1527 and taken off (to be either used or placed in bins) in malloc.
1529 The NON_MAIN_ARENA flag is never set for unsorted chunks, so it
1530 does not have to be taken into account in size comparisons.
1531 */
1533 /* The otherwise unindexable 1-bin is used to hold unsorted chunks. */
1534 #define unsorted_chunks(M) (bin_at (M, 1))
1536 /*
1537 Top
1539 The top-most available chunk (i.e., the one bordering the end of
1540 available memory) is treated specially. It is never included in
1541 any bin, is used only if no other chunk is available, and is
1542 released back to the system if it is very large (see
1543 M_TRIM_THRESHOLD). Because top initially
1544 points to its own bin with initial zero size, thus forcing
1545 extension on the first malloc request, we avoid having any special
1546 code in malloc to check whether it even exists yet. But we still
1547 need to do so when getting memory from system, so we make
1548 initial_top treat the bin as a legal but unusable chunk during the
1549 interval between initialization and the first call to
1550 sysmalloc. (This is somewhat delicate, since it relies on
1551 the 2 preceding words to be zero during this interval as well.)
1552 */
1554 /* Conveniently, the unsorted bin can be used as dummy top on first call */
1555 #define initial_top(M) (unsorted_chunks (M))
1557 /*
1558 Binmap
1560 To help compensate for the large number of bins, a one-level index
1561 structure is used for bin-by-bin searching. `binmap' is a
1562 bitvector recording whether bins are definitely empty so they can
1563 be skipped over during during traversals. The bits are NOT always
1564 cleared as soon as bins are empty, but instead only
1565 when they are noticed to be empty during traversal in malloc.
1566 */
1568 /* Conservatively use 32 bits per map word, even if on 64bit system */
1569 #define BINMAPSHIFT 5
1570 #define BITSPERMAP (1U << BINMAPSHIFT)
1571 #define BINMAPSIZE (NBINS / BITSPERMAP)
1573 #define idx2block(i) ((i) >> BINMAPSHIFT)
1574 #define idx2bit(i) ((1U << ((i) & ((1U << BINMAPSHIFT) - 1))))
1576 #define mark_bin(m, i) ((m)->binmap[idx2block (i)] |= idx2bit (i))
1577 #define unmark_bin(m, i) ((m)->binmap[idx2block (i)] &= ~(idx2bit (i)))
1578 #define get_binmap(m, i) ((m)->binmap[idx2block (i)] & idx2bit (i))
1580 /*
1581 Fastbins
1583 An array of lists holding recently freed small chunks. Fastbins
1584 are not doubly linked. It is faster to single-link them, and
1585 since chunks are never removed from the middles of these lists,
1586 double linking is not necessary. Also, unlike regular bins, they
1587 are not even processed in FIFO order (they use faster LIFO) since
1588 ordering doesn't much matter in the transient contexts in which
1589 fastbins are normally used.
1591 Chunks in fastbins keep their inuse bit set, so they cannot
1592 be consolidated with other free chunks. malloc_consolidate
1593 releases all chunks in fastbins and consolidates them with
1594 other free chunks.
1595 */
1597 typedef struct malloc_chunk *mfastbinptr;
1598 #define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])
1600 /* offset 2 to use otherwise unindexable first 2 bins */
1601 #define fastbin_index(sz) \
1602 ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)
1605 /* The maximum fastbin request size we support */
1606 #define MAX_FAST_SIZE (80 * SIZE_SZ / 4)
1608 #define NFASTBINS (fastbin_index (request2size (MAX_FAST_SIZE)) + 1)
1610 /*
1611 FASTBIN_CONSOLIDATION_THRESHOLD is the size of a chunk in free()
1612 that triggers automatic consolidation of possibly-surrounding
1613 fastbin chunks. This is a heuristic, so the exact value should not
1614 matter too much. It is defined at half the default trim threshold as a
1615 compromise heuristic to only attempt consolidation if it is likely
1616 to lead to trimming. However, it is not dynamically tunable, since
1617 consolidation reduces fragmentation surrounding large chunks even
1618 if trimming is not used.
1619 */
1621 #define FASTBIN_CONSOLIDATION_THRESHOLD (65536UL)
1623 /*
1624 Since the lowest 2 bits in max_fast don't matter in size comparisons,
1625 they are used as flags.
1626 */
1628 /*
1629 FASTCHUNKS_BIT held in max_fast indicates that there are probably
1630 some fastbin chunks. It is set true on entering a chunk into any
1631 fastbin, and cleared only in malloc_consolidate.
1633 The truth value is inverted so that have_fastchunks will be true
1634 upon startup (since statics are zero-filled), simplifying
1635 initialization checks.
1636 */
1638 #define FASTCHUNKS_BIT (1U)
1640 #define have_fastchunks(M) (((M)->flags & FASTCHUNKS_BIT) == 0)
1641 #define clear_fastchunks(M) catomic_or (&(M)->flags, FASTCHUNKS_BIT)
1642 #define set_fastchunks(M) catomic_and (&(M)->flags, ~FASTCHUNKS_BIT)
1644 /*
1645 NONCONTIGUOUS_BIT indicates that MORECORE does not return contiguous
1646 regions. Otherwise, contiguity is exploited in merging together,
1647 when possible, results from consecutive MORECORE calls.
1649 The initial value comes from MORECORE_CONTIGUOUS, but is
1650 changed dynamically if mmap is ever used as an sbrk substitute.
1651 */
1653 #define NONCONTIGUOUS_BIT (2U)
1655 #define contiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) == 0)
1656 #define noncontiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) != 0)
1657 #define set_noncontiguous(M) ((M)->flags |= NONCONTIGUOUS_BIT)
1658 #define set_contiguous(M) ((M)->flags &= ~NONCONTIGUOUS_BIT)
1660 /* ARENA_CORRUPTION_BIT is set if a memory corruption was detected on the
1661 arena. Such an arena is no longer used to allocate chunks. Chunks
1662 allocated in that arena before detecting corruption are not freed. */
1664 #define ARENA_CORRUPTION_BIT (4U)
1666 #define arena_is_corrupt(A) (((A)->flags & ARENA_CORRUPTION_BIT))
1667 #define set_arena_corrupt(A) ((A)->flags |= ARENA_CORRUPTION_BIT)
1669 /*
1670 Set value of max_fast.
1671 Use impossibly small value if 0.
1672 Precondition: there are no existing fastbin chunks.
1673 Setting the value clears fastchunk bit but preserves noncontiguous bit.
1674 */
1676 #define set_max_fast(s) \
1677 global_max_fast = (((s) == 0) \
1678 ? SMALLBIN_WIDTH : ((s + SIZE_SZ) & ~MALLOC_ALIGN_MASK))
1679 #define get_max_fast() global_max_fast
1682 /*
1683 ----------- Internal state representation and initialization -----------
1684 */
1686 struct malloc_state
1688 /* Serialize access. */
1689 mutex_t mutex;
1691 /* Flags (formerly in max_fast). */
1692 int flags;
1694 /* Fastbins */
1695 mfastbinptr fastbinsY[NFASTBINS];
1697 /* Base of the topmost chunk -- not otherwise kept in a bin */
1698 mchunkptr top;
1700 /* The remainder from the most recent split of a small request */
1701 mchunkptr last_remainder;
1703 /* Normal bins packed as described above */
1704 mchunkptr bins[NBINS * 2 - 2];
1706 /* Bitmap of bins */
1707 unsigned int binmap[BINMAPSIZE];
1709 /* Linked list */
1710 struct malloc_state *next;
1712 /* Linked list for free arenas. Access to this field is serialized
1713 by free_list_lock in arena.c. */
1714 struct malloc_state *next_free;
1716 /* Number of threads attached to this arena. 0 if the arena is on
1717 the free list. Access to this field is serialized by
1718 free_list_lock in arena.c. */
1719 INTERNAL_SIZE_T attached_threads;
1721 /* Memory allocated from the system in this arena. */
1722 INTERNAL_SIZE_T system_mem;
1723 INTERNAL_SIZE_T max_system_mem;
1724 };
1726 struct malloc_par
1728 /* Tunable parameters */
1729 unsigned long trim_threshold;
1730 INTERNAL_SIZE_T top_pad;
1731 INTERNAL_SIZE_T mmap_threshold;
1732 INTERNAL_SIZE_T arena_test;
1733 INTERNAL_SIZE_T arena_max;
1735 /* Memory map support */
1736 int n_mmaps;
1737 int n_mmaps_max;
1738 int max_n_mmaps;
1739 /* the mmap_threshold is dynamic, until the user sets
1740 it manually, at which point we need to disable any
1741 dynamic behavior. */
1742 int no_dyn_threshold;
1744 /* Statistics */
1745 INTERNAL_SIZE_T mmapped_mem;
1746 /*INTERNAL_SIZE_T sbrked_mem;*/
1747 /*INTERNAL_SIZE_T max_sbrked_mem;*/
1748 INTERNAL_SIZE_T max_mmapped_mem;
1749 INTERNAL_SIZE_T max_total_mem; /* only kept for NO_THREADS */
1751 /* First address handed out by MORECORE/sbrk. */
1752 char *sbrk_base;
1753 };
1755 /* There are several instances of this struct ("arenas") in this
1756 malloc. If you are adapting this malloc in a way that does NOT use
1757 a static or mmapped malloc_state, you MUST explicitly zero-fill it
1758 before using. This malloc relies on the property that malloc_state
1759 is initialized to all zeroes (as is true of C statics). */
1761 static struct malloc_state main_arena =
1763 .mutex = _LIBC_LOCK_INITIALIZER,
1764 .next = &main_arena,
1765 .attached_threads = 1
1766 };
1768 /* There is only one instance of the malloc parameters. */
1770 static struct malloc_par mp_ =
1772 .top_pad = DEFAULT_TOP_PAD,
1773 .n_mmaps_max = DEFAULT_MMAP_MAX,
1774 .mmap_threshold = DEFAULT_MMAP_THRESHOLD,
1775 .trim_threshold = DEFAULT_TRIM_THRESHOLD,
1776 #define NARENAS_FROM_NCORES(n) ((n) * (sizeof (long) == 4 ? 2 : 8))
1777 .arena_test = NARENAS_FROM_NCORES (1)
1778 };
1781 /* Non public mallopt parameters. */
1782 #define M_ARENA_TEST -7
1783 #define M_ARENA_MAX -8
1786 /* Maximum size of memory handled in fastbins. */
1787 static INTERNAL_SIZE_T global_max_fast;
1789 /*
1790 Initialize a malloc_state struct.
1792 This is called only from within malloc_consolidate, which needs
1793 be called in the same contexts anyway. It is never called directly
1794 outside of malloc_consolidate because some optimizing compilers try
1795 to inline it at all call points, which turns out not to be an
1796 optimization at all. (Inlining it in malloc_consolidate is fine though.)
1797 */
1799 static void
1800 malloc_init_state (mstate av)
1802 int i;
1803 mbinptr bin;
1805 /* Establish circular links for normal bins */
1806 for (i = 1; i < NBINS; ++i)
1808 bin = bin_at (av, i);
1809 bin->fd = bin->bk = bin;
1812 #if MORECORE_CONTIGUOUS
1813 if (av != &main_arena)
1814 #endif
1815 set_noncontiguous (av);
1816 if (av == &main_arena)
1817 set_max_fast (DEFAULT_MXFAST);
1818 av->flags |= FASTCHUNKS_BIT;
1820 av->top = initial_top (av);
1823 /*
1824 Other internal utilities operating on mstates
1825 */
1827 static void *sysmalloc (INTERNAL_SIZE_T, mstate);
1828 static int systrim (size_t, mstate);
1829 static void malloc_consolidate (mstate);
1832 /* -------------- Early definitions for debugging hooks ---------------- */
1834 /* Define and initialize the hook variables. These weak definitions must
1835 appear before any use of the variables in a function (arena.c uses one). */
1836 #ifndef weak_variable
1837 /* In GNU libc we want the hook variables to be weak definitions to
1838 avoid a problem with Emacs. */
1839 # define weak_variable weak_function
1840 #endif
1842 /* Forward declarations. */
1843 static void *malloc_hook_ini (size_t sz,
1844 const void *caller) __THROW;
1845 static void *realloc_hook_ini (void *ptr, size_t sz,
1846 const void *caller) __THROW;
1847 static void *memalign_hook_ini (size_t alignment, size_t sz,
1848 const void *caller) __THROW;
1850 void weak_variable (*__malloc_initialize_hook) (void) = NULL;
1851 void weak_variable (*__free_hook) (void *__ptr,
1852 const void *) = NULL;
1853 void *weak_variable (*__malloc_hook)
1854 (size_t __size, const void *) = malloc_hook_ini;
1855 void *weak_variable (*__realloc_hook)
1856 (void *__ptr, size_t __size, const void *)
1857 = realloc_hook_ini;
1858 void *weak_variable (*__memalign_hook)
1859 (size_t __alignment, size_t __size, const void *)
1860 = memalign_hook_ini;
1861 void weak_variable (*__after_morecore_hook) (void) = NULL;
1864 /* ---------------- Error behavior ------------------------------------ */
1866 #ifndef DEFAULT_CHECK_ACTION
1867 # define DEFAULT_CHECK_ACTION 3
1868 #endif
1870 static int check_action = DEFAULT_CHECK_ACTION;
1873 /* ------------------ Testing support ----------------------------------*/
1875 static int perturb_byte;
1877 static void
1878 alloc_perturb (char *p, size_t n)
1880 if (__glibc_unlikely (perturb_byte))
1881 memset (p, perturb_byte ^ 0xff, n);
1884 static void
1885 free_perturb (char *p, size_t n)
1887 if (__glibc_unlikely (perturb_byte))
1888 memset (p, perturb_byte, n);
1893 #include <stap-probe.h>
1895 /* ------------------- Support for multiple arenas -------------------- */
1896 #include "arena.c"
1898 /*
1899 Debugging support
1901 These routines make a number of assertions about the states
1902 of data structures that should be true at all times. If any
1903 are not true, it's very likely that a user program has somehow
1904 trashed memory. (It's also possible that there is a coding error
1905 in malloc. In which case, please report it!)
1906 */
1908 #if !MALLOC_DEBUG
1910 # define check_chunk(A, P)
1911 # define check_free_chunk(A, P)
1912 # define check_inuse_chunk(A, P)
1913 # define check_remalloced_chunk(A, P, N)
1914 # define check_malloced_chunk(A, P, N)
1915 # define check_malloc_state(A)
1917 #else
1919 # define check_chunk(A, P) do_check_chunk (A, P)
1920 # define check_free_chunk(A, P) do_check_free_chunk (A, P)
1921 # define check_inuse_chunk(A, P) do_check_inuse_chunk (A, P)
1922 # define check_remalloced_chunk(A, P, N) do_check_remalloced_chunk (A, P, N)
1923 # define check_malloced_chunk(A, P, N) do_check_malloced_chunk (A, P, N)
1924 # define check_malloc_state(A) do_check_malloc_state (A)
1926 /*
1927 Properties of all chunks
1928 */
1930 static void
1931 do_check_chunk (mstate av, mchunkptr p)
1933 unsigned long sz = chunksize (p);
1934 /* min and max possible addresses assuming contiguous allocation */
1935 char *max_address = (char *) (av->top) + chunksize (av->top);
1936 char *min_address = max_address - av->system_mem;
1938 if (!chunk_is_mmapped (p))
1940 /* Has legal address ... */
1941 if (p != av->top)
1943 if (contiguous (av))
1945 assert (((char *) p) >= min_address);
1946 assert (((char *) p + sz) <= ((char *) (av->top)));
1949 else
1951 /* top size is always at least MINSIZE */
1952 assert ((unsigned long) (sz) >= MINSIZE);
1953 /* top predecessor always marked inuse */
1954 assert (prev_inuse (p));
1957 else
1959 /* address is outside main heap */
1960 if (contiguous (av) && av->top != initial_top (av))
1962 assert (((char *) p) < min_address || ((char *) p) >= max_address);
1964 /* chunk is page-aligned */
1965 assert (((p->prev_size + sz) & (GLRO (dl_pagesize) - 1)) == 0);
1966 /* mem is aligned */
1967 assert (aligned_OK (chunk2mem (p)));
1971 /*
1972 Properties of free chunks
1973 */
1975 static void
1976 do_check_free_chunk (mstate av, mchunkptr p)
1978 INTERNAL_SIZE_T sz = p->size & ~(PREV_INUSE | NON_MAIN_ARENA);
1979 mchunkptr next = chunk_at_offset (p, sz);
1981 do_check_chunk (av, p);
1983 /* Chunk must claim to be free ... */
1984 assert (!inuse (p));
1985 assert (!chunk_is_mmapped (p));
1987 /* Unless a special marker, must have OK fields */
1988 if ((unsigned long) (sz) >= MINSIZE)
1990 assert ((sz & MALLOC_ALIGN_MASK) == 0);
1991 assert (aligned_OK (chunk2mem (p)));
1992 /* ... matching footer field */
1993 assert (next->prev_size == sz);
1994 /* ... and is fully consolidated */
1995 assert (prev_inuse (p));
1996 assert (next == av->top || inuse (next));
1998 /* ... and has minimally sane links */
1999 assert (p->fd->bk == p);
2000 assert (p->bk->fd == p);
2002 else /* markers are always of size SIZE_SZ */
2003 assert (sz == SIZE_SZ);
2006 /*
2007 Properties of inuse chunks
2008 */
2010 static void
2011 do_check_inuse_chunk (mstate av, mchunkptr p)
2013 mchunkptr next;
2015 do_check_chunk (av, p);
2017 if (chunk_is_mmapped (p))
2018 return; /* mmapped chunks have no next/prev */
2020 /* Check whether it claims to be in use ... */
2021 assert (inuse (p));
2023 next = next_chunk (p);
2025 /* ... and is surrounded by OK chunks.
2026 Since more things can be checked with free chunks than inuse ones,
2027 if an inuse chunk borders them and debug is on, it's worth doing them.
2028 */
2029 if (!prev_inuse (p))
2031 /* Note that we cannot even look at prev unless it is not inuse */
2032 mchunkptr prv = prev_chunk (p);
2033 assert (next_chunk (prv) == p);
2034 do_check_free_chunk (av, prv);
2037 if (next == av->top)
2039 assert (prev_inuse (next));
2040 assert (chunksize (next) >= MINSIZE);
2042 else if (!inuse (next))
2043 do_check_free_chunk (av, next);
2046 /*
2047 Properties of chunks recycled from fastbins
2048 */
2050 static void
2051 do_check_remalloced_chunk (mstate av, mchunkptr p, INTERNAL_SIZE_T s)
2053 INTERNAL_SIZE_T sz = p->size & ~(PREV_INUSE | NON_MAIN_ARENA);
2055 if (!chunk_is_mmapped (p))
2057 assert (av == arena_for_chunk (p));
2058 if (chunk_non_main_arena (p))
2059 assert (av != &main_arena);
2060 else
2061 assert (av == &main_arena);
2064 do_check_inuse_chunk (av, p);
2066 /* Legal size ... */
2067 assert ((sz & MALLOC_ALIGN_MASK) == 0);
2068 assert ((unsigned long) (sz) >= MINSIZE);
2069 /* ... and alignment */
2070 assert (aligned_OK (chunk2mem (p)));
2071 /* chunk is less than MINSIZE more than request */
2072 assert ((long) (sz) - (long) (s) >= 0);
2073 assert ((long) (sz) - (long) (s + MINSIZE) < 0);
2076 /*
2077 Properties of nonrecycled chunks at the point they are malloced
2078 */
2080 static void
2081 do_check_malloced_chunk (mstate av, mchunkptr p, INTERNAL_SIZE_T s)
2083 /* same as recycled case ... */
2084 do_check_remalloced_chunk (av, p, s);
2086 /*
2087 ... plus, must obey implementation invariant that prev_inuse is
2088 always true of any allocated chunk; i.e., that each allocated
2089 chunk borders either a previously allocated and still in-use
2090 chunk, or the base of its memory arena. This is ensured
2091 by making all allocations from the `lowest' part of any found
2092 chunk. This does not necessarily hold however for chunks
2093 recycled via fastbins.
2094 */
2096 assert (prev_inuse (p));
2100 /*
2101 Properties of malloc_state.
2103 This may be useful for debugging malloc, as well as detecting user
2104 programmer errors that somehow write into malloc_state.
2106 If you are extending or experimenting with this malloc, you can
2107 probably figure out how to hack this routine to print out or
2108 display chunk addresses, sizes, bins, and other instrumentation.
2109 */
2111 static void
2112 do_check_malloc_state (mstate av)
2114 int i;
2115 mchunkptr p;
2116 mchunkptr q;
2117 mbinptr b;
2118 unsigned int idx;
2119 INTERNAL_SIZE_T size;
2120 unsigned long total = 0;
2121 int max_fast_bin;
2123 /* internal size_t must be no wider than pointer type */
2124 assert (sizeof (INTERNAL_SIZE_T) <= sizeof (char *));
2126 /* alignment is a power of 2 */
2127 assert ((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT - 1)) == 0);
2129 /* cannot run remaining checks until fully initialized */
2130 if (av->top == 0 || av->top == initial_top (av))
2131 return;
2133 /* pagesize is a power of 2 */
2134 assert (powerof2(GLRO (dl_pagesize)));
2136 /* A contiguous main_arena is consistent with sbrk_base. */
2137 if (av == &main_arena && contiguous (av))
2138 assert ((char *) mp_.sbrk_base + av->system_mem ==
2139 (char *) av->top + chunksize (av->top));
2141 /* properties of fastbins */
2143 /* max_fast is in allowed range */
2144 assert ((get_max_fast () & ~1) <= request2size (MAX_FAST_SIZE));
2146 max_fast_bin = fastbin_index (get_max_fast ());
2148 for (i = 0; i < NFASTBINS; ++i)
2150 p = fastbin (av, i);
2152 /* The following test can only be performed for the main arena.
2153 While mallopt calls malloc_consolidate to get rid of all fast
2154 bins (especially those larger than the new maximum) this does
2155 only happen for the main arena. Trying to do this for any
2156 other arena would mean those arenas have to be locked and
2157 malloc_consolidate be called for them. This is excessive. And
2158 even if this is acceptable to somebody it still cannot solve
2159 the problem completely since if the arena is locked a
2160 concurrent malloc call might create a new arena which then
2161 could use the newly invalid fast bins. */
2163 /* all bins past max_fast are empty */
2164 if (av == &main_arena && i > max_fast_bin)
2165 assert (p == 0);
2167 while (p != 0)
2169 /* each chunk claims to be inuse */
2170 do_check_inuse_chunk (av, p);
2171 total += chunksize (p);
2172 /* chunk belongs in this bin */
2173 assert (fastbin_index (chunksize (p)) == i);
2174 p = p->fd;
2178 if (total != 0)
2179 assert (have_fastchunks (av));
2180 else if (!have_fastchunks (av))
2181 assert (total == 0);
2183 /* check normal bins */
2184 for (i = 1; i < NBINS; ++i)
2186 b = bin_at (av, i);
2188 /* binmap is accurate (except for bin 1 == unsorted_chunks) */
2189 if (i >= 2)
2191 unsigned int binbit = get_binmap (av, i);
2192 int empty = last (b) == b;
2193 if (!binbit)
2194 assert (empty);
2195 else if (!empty)
2196 assert (binbit);
2199 for (p = last (b); p != b; p = p->bk)
2201 /* each chunk claims to be free */
2202 do_check_free_chunk (av, p);
2203 size = chunksize (p);
2204 total += size;
2205 if (i >= 2)
2207 /* chunk belongs in bin */
2208 idx = bin_index (size);
2209 assert (idx == i);
2210 /* lists are sorted */
2211 assert (p->bk == b ||
2212 (unsigned long) chunksize (p->bk) >= (unsigned long) chunksize (p));
2214 if (!in_smallbin_range (size))
2216 if (p->fd_nextsize != NULL)
2218 if (p->fd_nextsize == p)
2219 assert (p->bk_nextsize == p);
2220 else
2222 if (p->fd_nextsize == first (b))
2223 assert (chunksize (p) < chunksize (p->fd_nextsize));
2224 else
2225 assert (chunksize (p) > chunksize (p->fd_nextsize));
2227 if (p == first (b))
2228 assert (chunksize (p) > chunksize (p->bk_nextsize));
2229 else
2230 assert (chunksize (p) < chunksize (p->bk_nextsize));
2233 else
2234 assert (p->bk_nextsize == NULL);
2237 else if (!in_smallbin_range (size))
2238 assert (p->fd_nextsize == NULL && p->bk_nextsize == NULL);
2239 /* chunk is followed by a legal chain of inuse chunks */
2240 for (q = next_chunk (p);
2241 (q != av->top && inuse (q) &&
2242 (unsigned long) (chunksize (q)) >= MINSIZE);
2243 q = next_chunk (q))
2244 do_check_inuse_chunk (av, q);
2248 /* top chunk is OK */
2249 check_chunk (av, av->top);
2251 #endif
2254 /* ----------------- Support for debugging hooks -------------------- */
2255 #include "hooks.c"
2258 /* ----------- Routines dealing with system allocation -------------- */
2260 /*
2261 sysmalloc handles malloc cases requiring more memory from the system.
2262 On entry, it is assumed that av->top does not have enough
2263 space to service request for nb bytes, thus requiring that av->top
2264 be extended or replaced.
2265 */
2267 static void *
2268 sysmalloc (INTERNAL_SIZE_T nb, mstate av)
2270 mchunkptr old_top; /* incoming value of av->top */
2271 INTERNAL_SIZE_T old_size; /* its size */
2272 char *old_end; /* its end address */
2274 long size; /* arg to first MORECORE or mmap call */
2275 char *brk; /* return value from MORECORE */
2277 long correction; /* arg to 2nd MORECORE call */
2278 char *snd_brk; /* 2nd return val */
2280 INTERNAL_SIZE_T front_misalign; /* unusable bytes at front of new space */
2281 INTERNAL_SIZE_T end_misalign; /* partial page left at end of new space */
2282 char *aligned_brk; /* aligned offset into brk */
2284 mchunkptr p; /* the allocated/returned chunk */
2285 mchunkptr remainder; /* remainder from allocation */
2286 unsigned long remainder_size; /* its size */
2289 size_t pagesize = GLRO (dl_pagesize);
2290 bool tried_mmap = false;
2293 /*
2294 If have mmap, and the request size meets the mmap threshold, and
2295 the system supports mmap, and there are few enough currently
2296 allocated mmapped regions, try to directly map this request
2297 rather than expanding top.
2298 */
2300 if (av == NULL
2301 || ((unsigned long) (nb) >= (unsigned long) (mp_.mmap_threshold)
2302 && (mp_.n_mmaps < mp_.n_mmaps_max)))
2304 char *mm; /* return value from mmap call*/
2306 try_mmap:
2307 /*
2308 Round up size to nearest page. For mmapped chunks, the overhead
2309 is one SIZE_SZ unit larger than for normal chunks, because there
2310 is no following chunk whose prev_size field could be used.
2312 See the front_misalign handling below, for glibc there is no
2313 need for further alignments unless we have have high alignment.
2314 */
2315 if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
2316 size = ALIGN_UP (nb + SIZE_SZ, pagesize);
2317 else
2318 size = ALIGN_UP (nb + SIZE_SZ + MALLOC_ALIGN_MASK, pagesize);
2319 tried_mmap = true;
2321 /* Don't try if size wraps around 0 */
2322 if ((unsigned long) (size) > (unsigned long) (nb))
2324 mm = (char *) (MMAP (0, size, PROT_READ | PROT_WRITE, 0));
2326 if (mm != MAP_FAILED)
2328 /*
2329 The offset to the start of the mmapped region is stored
2330 in the prev_size field of the chunk. This allows us to adjust
2331 returned start address to meet alignment requirements here
2332 and in memalign(), and still be able to compute proper
2333 address argument for later munmap in free() and realloc().
2334 */
2336 if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
2338 /* For glibc, chunk2mem increases the address by 2*SIZE_SZ and
2339 MALLOC_ALIGN_MASK is 2*SIZE_SZ-1. Each mmap'ed area is page
2340 aligned and therefore definitely MALLOC_ALIGN_MASK-aligned. */
2341 assert (((INTERNAL_SIZE_T) chunk2mem (mm) & MALLOC_ALIGN_MASK) == 0);
2342 front_misalign = 0;
2344 else
2345 front_misalign = (INTERNAL_SIZE_T) chunk2mem (mm) & MALLOC_ALIGN_MASK;
2346 if (front_misalign > 0)
2348 correction = MALLOC_ALIGNMENT - front_misalign;
2349 p = (mchunkptr) (mm + correction);
2350 p->prev_size = correction;
2351 set_head (p, (size - correction) | IS_MMAPPED);
2353 else
2355 p = (mchunkptr) mm;
2356 set_head (p, size | IS_MMAPPED);
2359 /* update statistics */
2361 int new = atomic_exchange_and_add (&mp_.n_mmaps, 1) + 1;
2362 atomic_max (&mp_.max_n_mmaps, new);
2364 unsigned long sum;
2365 sum = atomic_exchange_and_add (&mp_.mmapped_mem, size) + size;
2366 atomic_max (&mp_.max_mmapped_mem, sum);
2368 check_chunk (av, p);
2370 return chunk2mem (p);
2375 /* There are no usable arenas and mmap also failed. */
2376 if (av == NULL)
2377 return 0;
2379 /* Record incoming configuration of top */
2381 old_top = av->top;
2382 old_size = chunksize (old_top);
2383 old_end = (char *) (chunk_at_offset (old_top, old_size));
2385 brk = snd_brk = (char *) (MORECORE_FAILURE);
2387 /*
2388 If not the first time through, we require old_size to be
2389 at least MINSIZE and to have prev_inuse set.
2390 */
2392 assert ((old_top == initial_top (av) && old_size == 0) ||
2393 ((unsigned long) (old_size) >= MINSIZE &&
2394 prev_inuse (old_top) &&
2395 ((unsigned long) old_end & (pagesize - 1)) == 0));
2397 /* Precondition: not enough current space to satisfy nb request */
2398 assert ((unsigned long) (old_size) < (unsigned long) (nb + MINSIZE));
2401 if (av != &main_arena)
2403 heap_info *old_heap, *heap;
2404 size_t old_heap_size;
2406 /* First try to extend the current heap. */
2407 old_heap = heap_for_ptr (old_top);
2408 old_heap_size = old_heap->size;
2409 if ((long) (MINSIZE + nb - old_size) > 0
2410 && grow_heap (old_heap, MINSIZE + nb - old_size) == 0)
2412 av->system_mem += old_heap->size - old_heap_size;
2413 arena_mem += old_heap->size - old_heap_size;
2414 set_head (old_top, (((char *) old_heap + old_heap->size) - (char *) old_top)
2415 | PREV_INUSE);
2417 else if ((heap = new_heap (nb + (MINSIZE + sizeof (*heap)), mp_.top_pad)))
2419 /* Use a newly allocated heap. */
2420 heap->ar_ptr = av;
2421 heap->prev = old_heap;
2422 av->system_mem += heap->size;
2423 arena_mem += heap->size;
2424 /* Set up the new top. */
2425 top (av) = chunk_at_offset (heap, sizeof (*heap));
2426 set_head (top (av), (heap->size - sizeof (*heap)) | PREV_INUSE);
2428 /* Setup fencepost and free the old top chunk with a multiple of
2429 MALLOC_ALIGNMENT in size. */
2430 /* The fencepost takes at least MINSIZE bytes, because it might
2431 become the top chunk again later. Note that a footer is set
2432 up, too, although the chunk is marked in use. */
2433 old_size = (old_size - MINSIZE) & ~MALLOC_ALIGN_MASK;
2434 set_head (chunk_at_offset (old_top, old_size + 2 * SIZE_SZ), 0 | PREV_INUSE);
2435 if (old_size >= MINSIZE)
2437 set_head (chunk_at_offset (old_top, old_size), (2 * SIZE_SZ) | PREV_INUSE);
2438 set_foot (chunk_at_offset (old_top, old_size), (2 * SIZE_SZ));
2439 set_head (old_top, old_size | PREV_INUSE | NON_MAIN_ARENA);
2440 _int_free (av, old_top, 1);
2442 else
2444 set_head (old_top, (old_size + 2 * SIZE_SZ) | PREV_INUSE);
2445 set_foot (old_top, (old_size + 2 * SIZE_SZ));
2448 else if (!tried_mmap)
2449 /* We can at least try to use to mmap memory. */
2450 goto try_mmap;
2452 else /* av == main_arena */
2455 { /* Request enough space for nb + pad + overhead */
2456 size = nb + mp_.top_pad + MINSIZE;
2458 /*
2459 If contiguous, we can subtract out existing space that we hope to
2460 combine with new space. We add it back later only if
2461 we don't actually get contiguous space.
2462 */
2464 if (contiguous (av))
2465 size -= old_size;
2467 /*
2468 Round to a multiple of page size.
2469 If MORECORE is not contiguous, this ensures that we only call it
2470 with whole-page arguments. And if MORECORE is contiguous and
2471 this is not first time through, this preserves page-alignment of
2472 previous calls. Otherwise, we correct to page-align below.
2473 */
2475 size = ALIGN_UP (size, pagesize);
2477 /*
2478 Don't try to call MORECORE if argument is so big as to appear
2479 negative. Note that since mmap takes size_t arg, it may succeed
2480 below even if we cannot call MORECORE.
2481 */
2483 if (size > 0)
2485 brk = (char *) (MORECORE (size));
2486 LIBC_PROBE (memory_sbrk_more, 2, brk, size);
2489 if (brk != (char *) (MORECORE_FAILURE))
2491 /* Call the `morecore' hook if necessary. */
2492 void (*hook) (void) = atomic_forced_read (__after_morecore_hook);
2493 if (__builtin_expect (hook != NULL, 0))
2494 (*hook)();
2496 else
2498 /*
2499 If have mmap, try using it as a backup when MORECORE fails or
2500 cannot be used. This is worth doing on systems that have "holes" in
2501 address space, so sbrk cannot extend to give contiguous space, but
2502 space is available elsewhere. Note that we ignore mmap max count
2503 and threshold limits, since the space will not be used as a
2504 segregated mmap region.
2505 */
2507 /* Cannot merge with old top, so add its size back in */
2508 if (contiguous (av))
2509 size = ALIGN_UP (size + old_size, pagesize);
2511 /* If we are relying on mmap as backup, then use larger units */
2512 if ((unsigned long) (size) < (unsigned long) (MMAP_AS_MORECORE_SIZE))
2513 size = MMAP_AS_MORECORE_SIZE;
2515 /* Don't try if size wraps around 0 */
2516 if ((unsigned long) (size) > (unsigned long) (nb))
2518 char *mbrk = (char *) (MMAP (0, size, PROT_READ | PROT_WRITE, 0));
2520 if (mbrk != MAP_FAILED)
2522 /* We do not need, and cannot use, another sbrk call to find end */
2523 brk = mbrk;
2524 snd_brk = brk + size;
2526 /*
2527 Record that we no longer have a contiguous sbrk region.
2528 After the first time mmap is used as backup, we do not
2529 ever rely on contiguous space since this could incorrectly
2530 bridge regions.
2531 */
2532 set_noncontiguous (av);
2537 if (brk != (char *) (MORECORE_FAILURE))
2539 if (mp_.sbrk_base == 0)
2540 mp_.sbrk_base = brk;
2541 av->system_mem += size;
2543 /*
2544 If MORECORE extends previous space, we can likewise extend top size.
2545 */
2547 if (brk == old_end && snd_brk == (char *) (MORECORE_FAILURE))
2548 set_head (old_top, (size + old_size) | PREV_INUSE);
2550 else if (contiguous (av) && old_size && brk < old_end)
2552 /* Oops! Someone else killed our space.. Can't touch anything. */
2553 malloc_printerr (3, "break adjusted to free malloc space", brk,
2554 av);
2557 /*
2558 Otherwise, make adjustments:
2560 * If the first time through or noncontiguous, we need to call sbrk
2561 just to find out where the end of memory lies.
2563 * We need to ensure that all returned chunks from malloc will meet
2564 MALLOC_ALIGNMENT
2566 * If there was an intervening foreign sbrk, we need to adjust sbrk
2567 request size to account for fact that we will not be able to
2568 combine new space with existing space in old_top.
2570 * Almost all systems internally allocate whole pages at a time, in
2571 which case we might as well use the whole last page of request.
2572 So we allocate enough more memory to hit a page boundary now,
2573 which in turn causes future contiguous calls to page-align.
2574 */
2576 else
2578 front_misalign = 0;
2579 end_misalign = 0;
2580 correction = 0;
2581 aligned_brk = brk;
2583 /* handle contiguous cases */
2584 if (contiguous (av))
2586 /* Count foreign sbrk as system_mem. */
2587 if (old_size)
2588 av->system_mem += brk - old_end;
2590 /* Guarantee alignment of first new chunk made from this space */
2592 front_misalign = (INTERNAL_SIZE_T) chunk2mem (brk) & MALLOC_ALIGN_MASK;
2593 if (front_misalign > 0)
2595 /*
2596 Skip over some bytes to arrive at an aligned position.
2597 We don't need to specially mark these wasted front bytes.
2598 They will never be accessed anyway because
2599 prev_inuse of av->top (and any chunk created from its start)
2600 is always true after initialization.
2601 */
2603 correction = MALLOC_ALIGNMENT - front_misalign;
2604 aligned_brk += correction;
2607 /*
2608 If this isn't adjacent to existing space, then we will not
2609 be able to merge with old_top space, so must add to 2nd request.
2610 */
2612 correction += old_size;
2614 /* Extend the end address to hit a page boundary */
2615 end_misalign = (INTERNAL_SIZE_T) (brk + size + correction);
2616 correction += (ALIGN_UP (end_misalign, pagesize)) - end_misalign;
2618 assert (correction >= 0);
2619 snd_brk = (char *) (MORECORE (correction));
2621 /*
2622 If can't allocate correction, try to at least find out current
2623 brk. It might be enough to proceed without failing.
2625 Note that if second sbrk did NOT fail, we assume that space
2626 is contiguous with first sbrk. This is a safe assumption unless
2627 program is multithreaded but doesn't use locks and a foreign sbrk
2628 occurred between our first and second calls.
2629 */
2631 if (snd_brk == (char *) (MORECORE_FAILURE))
2633 correction = 0;
2634 snd_brk = (char *) (MORECORE (0));
2636 else
2638 /* Call the `morecore' hook if necessary. */
2639 void (*hook) (void) = atomic_forced_read (__after_morecore_hook);
2640 if (__builtin_expect (hook != NULL, 0))
2641 (*hook)();
2645 /* handle non-contiguous cases */
2646 else
2648 if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
2649 /* MORECORE/mmap must correctly align */
2650 assert (((unsigned long) chunk2mem (brk) & MALLOC_ALIGN_MASK) == 0);
2651 else
2653 front_misalign = (INTERNAL_SIZE_T) chunk2mem (brk) & MALLOC_ALIGN_MASK;
2654 if (front_misalign > 0)
2656 /*
2657 Skip over some bytes to arrive at an aligned position.
2658 We don't need to specially mark these wasted front bytes.
2659 They will never be accessed anyway because
2660 prev_inuse of av->top (and any chunk created from its start)
2661 is always true after initialization.
2662 */
2664 aligned_brk += MALLOC_ALIGNMENT - front_misalign;
2668 /* Find out current end of memory */
2669 if (snd_brk == (char *) (MORECORE_FAILURE))
2671 snd_brk = (char *) (MORECORE (0));
2675 /* Adjust top based on results of second sbrk */
2676 if (snd_brk != (char *) (MORECORE_FAILURE))
2678 av->top = (mchunkptr) aligned_brk;
2679 set_head (av->top, (snd_brk - aligned_brk + correction) | PREV_INUSE);
2680 av->system_mem += correction;
2682 /*
2683 If not the first time through, we either have a
2684 gap due to foreign sbrk or a non-contiguous region. Insert a
2685 double fencepost at old_top to prevent consolidation with space
2686 we don't own. These fenceposts are artificial chunks that are
2687 marked as inuse and are in any case too small to use. We need
2688 two to make sizes and alignments work out.
2689 */
2691 if (old_size != 0)
2693 /*
2694 Shrink old_top to insert fenceposts, keeping size a
2695 multiple of MALLOC_ALIGNMENT. We know there is at least
2696 enough space in old_top to do this.
2697 */
2698 old_size = (old_size - 4 * SIZE_SZ) & ~MALLOC_ALIGN_MASK;
2699 set_head (old_top, old_size | PREV_INUSE);
2701 /*
2702 Note that the following assignments completely overwrite
2703 old_top when old_size was previously MINSIZE. This is
2704 intentional. We need the fencepost, even if old_top otherwise gets
2705 lost.
2706 */
2707 chunk_at_offset (old_top, old_size)->size =
2708 (2 * SIZE_SZ) | PREV_INUSE;
2710 chunk_at_offset (old_top, old_size + 2 * SIZE_SZ)->size =
2711 (2 * SIZE_SZ) | PREV_INUSE;
2713 /* If possible, release the rest. */
2714 if (old_size >= MINSIZE)
2716 _int_free (av, old_top, 1);
2722 } /* if (av != &main_arena) */
2724 if ((unsigned long) av->system_mem > (unsigned long) (av->max_system_mem))
2725 av->max_system_mem = av->system_mem;
2726 check_malloc_state (av);
2728 /* finally, do the allocation */
2729 p = av->top;
2730 size = chunksize (p);
2732 /* check that one of the above allocation paths succeeded */
2733 if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
2735 remainder_size = size - nb;
2736 remainder = chunk_at_offset (p, nb);
2737 av->top = remainder;
2738 set_head (p, nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));
2739 set_head (remainder, remainder_size | PREV_INUSE);
2740 check_malloced_chunk (av, p, nb);
2741 return chunk2mem (p);
2744 /* catch all failure paths */
2745 __set_errno (ENOMEM);
2746 return 0;
2750 /*
2751 systrim is an inverse of sorts to sysmalloc. It gives memory back
2752 to the system (via negative arguments to sbrk) if there is unused
2753 memory at the `high' end of the malloc pool. It is called
2754 automatically by free() when top space exceeds the trim
2755 threshold. It is also called by the public malloc_trim routine. It
2756 returns 1 if it actually released any memory, else 0.
2757 */
2759 static int
2760 systrim (size_t pad, mstate av)
2762 long top_size; /* Amount of top-most memory */
2763 long extra; /* Amount to release */
2764 long released; /* Amount actually released */
2765 char *current_brk; /* address returned by pre-check sbrk call */
2766 char *new_brk; /* address returned by post-check sbrk call */
2767 size_t pagesize;
2768 long top_area;
2770 pagesize = GLRO (dl_pagesize);
2771 top_size = chunksize (av->top);
2773 top_area = top_size - MINSIZE - 1;
2774 if (top_area <= pad)
2775 return 0;
2777 /* Release in pagesize units and round down to the nearest page. */
2778 extra = ALIGN_DOWN(top_area - pad, pagesize);
2780 if (extra == 0)
2781 return 0;
2783 /*
2784 Only proceed if end of memory is where we last set it.
2785 This avoids problems if there were foreign sbrk calls.
2786 */
2787 current_brk = (char *) (MORECORE (0));
2788 if (current_brk == (char *) (av->top) + top_size)
2790 /*
2791 Attempt to release memory. We ignore MORECORE return value,
2792 and instead call again to find out where new end of memory is.
2793 This avoids problems if first call releases less than we asked,
2794 of if failure somehow altered brk value. (We could still
2795 encounter problems if it altered brk in some very bad way,
2796 but the only thing we can do is adjust anyway, which will cause
2797 some downstream failure.)
2798 */
2800 MORECORE (-extra);
2801 /* Call the `morecore' hook if necessary. */
2802 void (*hook) (void) = atomic_forced_read (__after_morecore_hook);
2803 if (__builtin_expect (hook != NULL, 0))
2804 (*hook)();
2805 new_brk = (char *) (MORECORE (0));
2807 LIBC_PROBE (memory_sbrk_less, 2, new_brk, extra);
2809 if (new_brk != (char *) MORECORE_FAILURE)
2811 released = (long) (current_brk - new_brk);
2813 if (released != 0)
2815 /* Success. Adjust top. */
2816 av->system_mem -= released;
2817 set_head (av->top, (top_size - released) | PREV_INUSE);
2818 check_malloc_state (av);
2819 return 1;
2823 return 0;
2826 static void
2827 internal_function
2828 munmap_chunk (mchunkptr p)
2830 INTERNAL_SIZE_T size = chunksize (p);
2832 assert (chunk_is_mmapped (p));
2834 uintptr_t block = (uintptr_t) p - p->prev_size;
2835 size_t total_size = p->prev_size + size;
2836 /* Unfortunately we have to do the compilers job by hand here. Normally
2837 we would test BLOCK and TOTAL-SIZE separately for compliance with the
2838 page size. But gcc does not recognize the optimization possibility
2839 (in the moment at least) so we combine the two values into one before
2840 the bit test. */
2841 if (__builtin_expect (((block | total_size) & (GLRO (dl_pagesize) - 1)) != 0, 0))
2843 malloc_printerr (check_action, "munmap_chunk(): invalid pointer",
2844 chunk2mem (p), NULL);
2845 return;
2848 atomic_decrement (&mp_.n_mmaps);
2849 atomic_add (&mp_.mmapped_mem, -total_size);
2851 /* If munmap failed the process virtual memory address space is in a
2852 bad shape. Just leave the block hanging around, the process will
2853 terminate shortly anyway since not much can be done. */
2854 __munmap ((char *) block, total_size);
2857 #if HAVE_MREMAP
2859 static mchunkptr
2860 internal_function
2861 mremap_chunk (mchunkptr p, size_t new_size)
2863 size_t pagesize = GLRO (dl_pagesize);
2864 INTERNAL_SIZE_T offset = p->prev_size;
2865 INTERNAL_SIZE_T size = chunksize (p);
2866 char *cp;
2868 assert (chunk_is_mmapped (p));
2869 assert (((size + offset) & (GLRO (dl_pagesize) - 1)) == 0);
2871 /* Note the extra SIZE_SZ overhead as in mmap_chunk(). */
2872 new_size = ALIGN_UP (new_size + offset + SIZE_SZ, pagesize);
2874 /* No need to remap if the number of pages does not change. */
2875 if (size + offset == new_size)
2876 return p;
2878 cp = (char *) __mremap ((char *) p - offset, size + offset, new_size,
2879 MREMAP_MAYMOVE);
2881 if (cp == MAP_FAILED)
2882 return 0;
2884 p = (mchunkptr) (cp + offset);
2886 assert (aligned_OK (chunk2mem (p)));
2888 assert ((p->prev_size == offset));
2889 set_head (p, (new_size - offset) | IS_MMAPPED);
2891 INTERNAL_SIZE_T new;
2892 new = atomic_exchange_and_add (&mp_.mmapped_mem, new_size - size - offset)
2893 + new_size - size - offset;
2894 atomic_max (&mp_.max_mmapped_mem, new);
2895 return p;
2897 #endif /* HAVE_MREMAP */
2899 /*------------------------ Public wrappers. --------------------------------*/
2901 void *
2902 __libc_malloc (size_t bytes)
2904 mstate ar_ptr;
2905 void *victim;
2907 void *(*hook) (size_t, const void *)
2908 = atomic_forced_read (__malloc_hook);
2909 if (__builtin_expect (hook != NULL, 0))
2910 return (*hook)(bytes, RETURN_ADDRESS (0));
2912 arena_get (ar_ptr, bytes);
2914 victim = _int_malloc (ar_ptr, bytes);
2915 /* Retry with another arena only if we were able to find a usable arena
2916 before. */
2917 if (!victim && ar_ptr != NULL)
2919 LIBC_PROBE (memory_malloc_retry, 1, bytes);
2920 ar_ptr = arena_get_retry (ar_ptr, bytes);
2921 victim = _int_malloc (ar_ptr, bytes);
2924 if (ar_ptr != NULL)
2925 (void) mutex_unlock (&ar_ptr->mutex);
2927 assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
2928 ar_ptr == arena_for_chunk (mem2chunk (victim)));
2929 return victim;
2931 libc_hidden_def (__libc_malloc)
2933 void
2934 __libc_free (void *mem)
2936 mstate ar_ptr;
2937 mchunkptr p; /* chunk corresponding to mem */
2939 void (*hook) (void *, const void *)
2940 = atomic_forced_read (__free_hook);
2941 if (__builtin_expect (hook != NULL, 0))
2943 (*hook)(mem, RETURN_ADDRESS (0));
2944 return;
2947 if (mem == 0) /* free(0) has no effect */
2948 return;
2950 p = mem2chunk (mem);
2952 if (chunk_is_mmapped (p)) /* release mmapped memory. */
2954 /* see if the dynamic brk/mmap threshold needs adjusting */
2955 if (!mp_.no_dyn_threshold
2956 && p->size > mp_.mmap_threshold
2957 && p->size <= DEFAULT_MMAP_THRESHOLD_MAX)
2959 mp_.mmap_threshold = chunksize (p);
2960 mp_.trim_threshold = 2 * mp_.mmap_threshold;
2961 LIBC_PROBE (memory_mallopt_free_dyn_thresholds, 2,
2962 mp_.mmap_threshold, mp_.trim_threshold);
2964 munmap_chunk (p);
2965 return;
2968 ar_ptr = arena_for_chunk (p);
2969 _int_free (ar_ptr, p, 0);
2971 libc_hidden_def (__libc_free)
2973 void *
2974 __libc_realloc (void *oldmem, size_t bytes)
2976 mstate ar_ptr;
2977 INTERNAL_SIZE_T nb; /* padded request size */
2979 void *newp; /* chunk to return */
2981 void *(*hook) (void *, size_t, const void *) =
2982 atomic_forced_read (__realloc_hook);
2983 if (__builtin_expect (hook != NULL, 0))
2984 return (*hook)(oldmem, bytes, RETURN_ADDRESS (0));
2986 #if REALLOC_ZERO_BYTES_FREES
2987 if (bytes == 0 && oldmem != NULL)
2989 __libc_free (oldmem); return 0;
2991 #endif
2993 /* realloc of null is supposed to be same as malloc */
2994 if (oldmem == 0)
2995 return __libc_malloc (bytes);
2997 /* chunk corresponding to oldmem */
2998 const mchunkptr oldp = mem2chunk (oldmem);
2999 /* its size */
3000 const INTERNAL_SIZE_T oldsize = chunksize (oldp);
3002 if (chunk_is_mmapped (oldp))
3003 ar_ptr = NULL;
3004 else
3005 ar_ptr = arena_for_chunk (oldp);
3007 /* Little security check which won't hurt performance: the
3008 allocator never wrapps around at the end of the address space.
3009 Therefore we can exclude some size values which might appear
3010 here by accident or by "design" from some intruder. */
3011 if (__builtin_expect ((uintptr_t) oldp > (uintptr_t) -oldsize, 0)
3012 || __builtin_expect (misaligned_chunk (oldp), 0))
3014 malloc_printerr (check_action, "realloc(): invalid pointer", oldmem,
3015 ar_ptr);
3016 return NULL;
3019 checked_request2size (bytes, nb);
3021 if (chunk_is_mmapped (oldp))
3023 void *newmem;
3025 #if HAVE_MREMAP
3026 newp = mremap_chunk (oldp, nb);
3027 if (newp)
3028 return chunk2mem (newp);
3029 #endif
3030 /* Note the extra SIZE_SZ overhead. */
3031 if (oldsize - SIZE_SZ >= nb)
3032 return oldmem; /* do nothing */
3034 /* Must alloc, copy, free. */
3035 newmem = __libc_malloc (bytes);
3036 if (newmem == 0)
3037 return 0; /* propagate failure */
3039 memcpy (newmem, oldmem, oldsize - 2 * SIZE_SZ);
3040 munmap_chunk (oldp);
3041 return newmem;
3044 (void) mutex_lock (&ar_ptr->mutex);
3046 newp = _int_realloc (ar_ptr, oldp, oldsize, nb);
3048 (void) mutex_unlock (&ar_ptr->mutex);
3049 assert (!newp || chunk_is_mmapped (mem2chunk (newp)) ||
3050 ar_ptr == arena_for_chunk (mem2chunk (newp)));
3052 if (newp == NULL)
3054 /* Try harder to allocate memory in other arenas. */
3055 LIBC_PROBE (memory_realloc_retry, 2, bytes, oldmem);
3056 newp = __libc_malloc (bytes);
3057 if (newp != NULL)
3059 memcpy (newp, oldmem, oldsize - SIZE_SZ);
3060 _int_free (ar_ptr, oldp, 0);
3064 return newp;
3066 libc_hidden_def (__libc_realloc)
3068 void *
3069 __libc_memalign (size_t alignment, size_t bytes)
3071 void *address = RETURN_ADDRESS (0);
3072 return _mid_memalign (alignment, bytes, address);
3075 static void *
3076 _mid_memalign (size_t alignment, size_t bytes, void *address)
3078 mstate ar_ptr;
3079 void *p;
3081 void *(*hook) (size_t, size_t, const void *) =
3082 atomic_forced_read (__memalign_hook);
3083 if (__builtin_expect (hook != NULL, 0))
3084 return (*hook)(alignment, bytes, address);
3086 /* If we need less alignment than we give anyway, just relay to malloc. */
3087 if (alignment <= MALLOC_ALIGNMENT)
3088 return __libc_malloc (bytes);
3090 /* Otherwise, ensure that it is at least a minimum chunk size */
3091 if (alignment < MINSIZE)
3092 alignment = MINSIZE;
3094 /* If the alignment is greater than SIZE_MAX / 2 + 1 it cannot be a
3095 power of 2 and will cause overflow in the check below. */
3096 if (alignment > SIZE_MAX / 2 + 1)
3098 __set_errno (EINVAL);
3099 return 0;
3102 /* Check for overflow. */
3103 if (bytes > SIZE_MAX - alignment - MINSIZE)
3105 __set_errno (ENOMEM);
3106 return 0;
3110 /* Make sure alignment is power of 2. */
3111 if (!powerof2 (alignment))
3113 size_t a = MALLOC_ALIGNMENT * 2;
3114 while (a < alignment)
3115 a <<= 1;
3116 alignment = a;
3119 arena_get (ar_ptr, bytes + alignment + MINSIZE);
3121 p = _int_memalign (ar_ptr, alignment, bytes);
3122 if (!p && ar_ptr != NULL)
3124 LIBC_PROBE (memory_memalign_retry, 2, bytes, alignment);
3125 ar_ptr = arena_get_retry (ar_ptr, bytes);
3126 p = _int_memalign (ar_ptr, alignment, bytes);
3129 if (ar_ptr != NULL)
3130 (void) mutex_unlock (&ar_ptr->mutex);
3132 assert (!p || chunk_is_mmapped (mem2chunk (p)) ||
3133 ar_ptr == arena_for_chunk (mem2chunk (p)));
3134 return p;
3136 /* For ISO C11. */
3137 weak_alias (__libc_memalign, aligned_alloc)
3138 libc_hidden_def (__libc_memalign)
3140 void *
3141 __libc_valloc (size_t bytes)
3143 if (__malloc_initialized < 0)
3144 ptmalloc_init ();
3146 void *address = RETURN_ADDRESS (0);
3147 size_t pagesize = GLRO (dl_pagesize);
3148 return _mid_memalign (pagesize, bytes, address);
3151 void *
3152 __libc_pvalloc (size_t bytes)
3154 if (__malloc_initialized < 0)
3155 ptmalloc_init ();
3157 void *address = RETURN_ADDRESS (0);
3158 size_t pagesize = GLRO (dl_pagesize);
3159 size_t rounded_bytes = ALIGN_UP (bytes, pagesize);
3161 /* Check for overflow. */
3162 if (bytes > SIZE_MAX - 2 * pagesize - MINSIZE)
3164 __set_errno (ENOMEM);
3165 return 0;
3168 return _mid_memalign (pagesize, rounded_bytes, address);
3171 void *
3172 __libc_calloc (size_t n, size_t elem_size)
3174 mstate av;
3175 mchunkptr oldtop, p;
3176 INTERNAL_SIZE_T bytes, sz, csz, oldtopsize;
3177 void *mem;
3178 unsigned long clearsize;
3179 unsigned long nclears;
3180 INTERNAL_SIZE_T *d;
3182 /* size_t is unsigned so the behavior on overflow is defined. */
3183 bytes = n * elem_size;
3184 #define HALF_INTERNAL_SIZE_T \
3185 (((INTERNAL_SIZE_T) 1) << (8 * sizeof (INTERNAL_SIZE_T) / 2))
3186 if (__builtin_expect ((n | elem_size) >= HALF_INTERNAL_SIZE_T, 0))
3188 if (elem_size != 0 && bytes / elem_size != n)
3190 __set_errno (ENOMEM);
3191 return 0;
3195 void *(*hook) (size_t, const void *) =
3196 atomic_forced_read (__malloc_hook);
3197 if (__builtin_expect (hook != NULL, 0))
3199 sz = bytes;
3200 mem = (*hook)(sz, RETURN_ADDRESS (0));
3201 if (mem == 0)
3202 return 0;
3204 return memset (mem, 0, sz);
3207 sz = bytes;
3209 arena_get (av, sz);
3210 if (av)
3212 /* Check if we hand out the top chunk, in which case there may be no
3213 need to clear. */
3214 #if MORECORE_CLEARS
3215 oldtop = top (av);
3216 oldtopsize = chunksize (top (av));
3217 # if MORECORE_CLEARS < 2
3218 /* Only newly allocated memory is guaranteed to be cleared. */
3219 if (av == &main_arena &&
3220 oldtopsize < mp_.sbrk_base + av->max_system_mem - (char *) oldtop)
3221 oldtopsize = (mp_.sbrk_base + av->max_system_mem - (char *) oldtop);
3222 # endif
3223 if (av != &main_arena)
3225 heap_info *heap = heap_for_ptr (oldtop);
3226 if (oldtopsize < (char *) heap + heap->mprotect_size - (char *) oldtop)
3227 oldtopsize = (char *) heap + heap->mprotect_size - (char *) oldtop;
3229 #endif
3231 else
3233 /* No usable arenas. */
3234 oldtop = 0;
3235 oldtopsize = 0;
3237 mem = _int_malloc (av, sz);
3240 assert (!mem || chunk_is_mmapped (mem2chunk (mem)) ||
3241 av == arena_for_chunk (mem2chunk (mem)));
3243 if (mem == 0 && av != NULL)
3245 LIBC_PROBE (memory_calloc_retry, 1, sz);
3246 av = arena_get_retry (av, sz);
3247 mem = _int_malloc (av, sz);
3250 if (av != NULL)
3251 (void) mutex_unlock (&av->mutex);
3253 /* Allocation failed even after a retry. */
3254 if (mem == 0)
3255 return 0;
3257 p = mem2chunk (mem);
3259 /* Two optional cases in which clearing not necessary */
3260 if (chunk_is_mmapped (p))
3262 if (__builtin_expect (perturb_byte, 0))
3263 return memset (mem, 0, sz);
3265 return mem;
3268 csz = chunksize (p);
3270 #if MORECORE_CLEARS
3271 if (perturb_byte == 0 && (p == oldtop && csz > oldtopsize))
3273 /* clear only the bytes from non-freshly-sbrked memory */
3274 csz = oldtopsize;
3276 #endif
3278 /* Unroll clear of <= 36 bytes (72 if 8byte sizes). We know that
3279 contents have an odd number of INTERNAL_SIZE_T-sized words;
3280 minimally 3. */
3281 d = (INTERNAL_SIZE_T *) mem;
3282 clearsize = csz - SIZE_SZ;
3283 nclears = clearsize / sizeof (INTERNAL_SIZE_T);
3284 assert (nclears >= 3);
3286 if (nclears > 9)
3287 return memset (d, 0, clearsize);
3289 else
3291 *(d + 0) = 0;
3292 *(d + 1) = 0;
3293 *(d + 2) = 0;
3294 if (nclears > 4)
3296 *(d + 3) = 0;
3297 *(d + 4) = 0;
3298 if (nclears > 6)
3300 *(d + 5) = 0;
3301 *(d + 6) = 0;
3302 if (nclears > 8)
3304 *(d + 7) = 0;
3305 *(d + 8) = 0;
3311 return mem;
3314 /*
3315 ------------------------------ malloc ------------------------------
3316 */
3318 static void *
3319 _int_malloc (mstate av, size_t bytes)
3321 INTERNAL_SIZE_T nb; /* normalized request size */
3322 unsigned int idx; /* associated bin index */
3323 mbinptr bin; /* associated bin */
3325 mchunkptr victim; /* inspected/selected chunk */
3326 INTERNAL_SIZE_T size; /* its size */
3327 int victim_index; /* its bin index */
3329 mchunkptr remainder; /* remainder from a split */
3330 unsigned long remainder_size; /* its size */
3332 unsigned int block; /* bit map traverser */
3333 unsigned int bit; /* bit map traverser */
3334 unsigned int map; /* current word of binmap */
3336 mchunkptr fwd; /* misc temp for linking */
3337 mchunkptr bck; /* misc temp for linking */
3339 const char *errstr = NULL;
3341 /*
3342 Convert request size to internal form by adding SIZE_SZ bytes
3343 overhead plus possibly more to obtain necessary alignment and/or
3344 to obtain a size of at least MINSIZE, the smallest allocatable
3345 size. Also, checked_request2size traps (returning 0) request sizes
3346 that are so large that they wrap around zero when padded and
3347 aligned.
3348 */
3350 checked_request2size (bytes, nb);
3352 /* There are no usable arenas. Fall back to sysmalloc to get a chunk from
3353 mmap. */
3354 if (__glibc_unlikely (av == NULL))
3356 void *p = sysmalloc (nb, av);
3357 if (p != NULL)
3358 alloc_perturb (p, bytes);
3359 return p;
3362 /*
3363 If the size qualifies as a fastbin, first check corresponding bin.
3364 This code is safe to execute even if av is not yet initialized, so we
3365 can try it without checking, which saves some time on this fast path.
3366 */
3368 if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
3370 idx = fastbin_index (nb);
3371 mfastbinptr *fb = &fastbin (av, idx);
3372 mchunkptr pp = *fb;
3373 do
3375 victim = pp;
3376 if (victim == NULL)
3377 break;
3379 while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
3380 != victim);
3381 if (victim != 0)
3383 if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
3385 errstr = "malloc(): memory corruption (fast)";
3386 errout:
3387 malloc_printerr (check_action, errstr, chunk2mem (victim), av);
3388 return NULL;
3390 check_remalloced_chunk (av, victim, nb);
3391 void *p = chunk2mem (victim);
3392 alloc_perturb (p, bytes);
3393 return p;
3397 /*
3398 If a small request, check regular bin. Since these "smallbins"
3399 hold one size each, no searching within bins is necessary.
3400 (For a large request, we need to wait until unsorted chunks are
3401 processed to find best fit. But for small ones, fits are exact
3402 anyway, so we can check now, which is faster.)
3403 */
3405 if (in_smallbin_range (nb))
3407 idx = smallbin_index (nb);
3408 bin = bin_at (av, idx);
3410 if ((victim = last (bin)) != bin)
3412 if (victim == 0) /* initialization check */
3413 malloc_consolidate (av);
3414 else
3416 bck = victim->bk;
3417 if (__glibc_unlikely (bck->fd != victim))
3419 errstr = "malloc(): smallbin double linked list corrupted";
3420 goto errout;
3422 set_inuse_bit_at_offset (victim, nb);
3423 bin->bk = bck;
3424 bck->fd = bin;
3426 if (av != &main_arena)
3427 victim->size |= NON_MAIN_ARENA;
3428 check_malloced_chunk (av, victim, nb);
3429 void *p = chunk2mem (victim);
3430 alloc_perturb (p, bytes);
3431 return p;
3436 /*
3437 If this is a large request, consolidate fastbins before continuing.
3438 While it might look excessive to kill all fastbins before
3439 even seeing if there is space available, this avoids
3440 fragmentation problems normally associated with fastbins.
3441 Also, in practice, programs tend to have runs of either small or
3442 large requests, but less often mixtures, so consolidation is not
3443 invoked all that often in most programs. And the programs that
3444 it is called frequently in otherwise tend to fragment.
3445 */
3447 else
3449 idx = largebin_index (nb);
3450 if (have_fastchunks (av))
3451 malloc_consolidate (av);
3454 /*
3455 Process recently freed or remaindered chunks, taking one only if
3456 it is exact fit, or, if this a small request, the chunk is remainder from
3457 the most recent non-exact fit. Place other traversed chunks in
3458 bins. Note that this step is the only place in any routine where
3459 chunks are placed in bins.
3461 The outer loop here is needed because we might not realize until
3462 near the end of malloc that we should have consolidated, so must
3463 do so and retry. This happens at most once, and only when we would
3464 otherwise need to expand memory to service a "small" request.
3465 */
3467 for (;; )
3469 int iters = 0;
3470 while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
3472 bck = victim->bk;
3473 if (__builtin_expect (victim->size <= 2 * SIZE_SZ, 0)
3474 || __builtin_expect (victim->size > av->system_mem, 0))
3475 malloc_printerr (check_action, "malloc(): memory corruption",
3476 chunk2mem (victim), av);
3477 size = chunksize (victim);
3479 /*
3480 If a small request, try to use last remainder if it is the
3481 only chunk in unsorted bin. This helps promote locality for
3482 runs of consecutive small requests. This is the only
3483 exception to best-fit, and applies only when there is
3484 no exact fit for a small chunk.
3485 */
3487 if (in_smallbin_range (nb) &&
3488 bck == unsorted_chunks (av) &&
3489 victim == av->last_remainder &&
3490 (unsigned long) (size) > (unsigned long) (nb + MINSIZE))
3492 /* split and reattach remainder */
3493 remainder_size = size - nb;
3494 remainder = chunk_at_offset (victim, nb);
3495 unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
3496 av->last_remainder = remainder;
3497 remainder->bk = remainder->fd = unsorted_chunks (av);
3498 if (!in_smallbin_range (remainder_size))
3500 remainder->fd_nextsize = NULL;
3501 remainder->bk_nextsize = NULL;
3504 set_head (victim, nb | PREV_INUSE |
3505 (av != &main_arena ? NON_MAIN_ARENA : 0));
3506 set_head (remainder, remainder_size | PREV_INUSE);
3507 set_foot (remainder, remainder_size);
3509 check_malloced_chunk (av, victim, nb);
3510 void *p = chunk2mem (victim);
3511 alloc_perturb (p, bytes);
3512 return p;
3515 /* remove from unsorted list */
3516 unsorted_chunks (av)->bk = bck;
3517 bck->fd = unsorted_chunks (av);
3519 /* Take now instead of binning if exact fit */
3521 if (size == nb)
3523 set_inuse_bit_at_offset (victim, size);
3524 if (av != &main_arena)
3525 victim->size |= NON_MAIN_ARENA;
3526 check_malloced_chunk (av, victim, nb);
3527 void *p = chunk2mem (victim);
3528 alloc_perturb (p, bytes);
3529 return p;
3532 /* place chunk in bin */
3534 if (in_smallbin_range (size))
3536 victim_index = smallbin_index (size);
3537 bck = bin_at (av, victim_index);
3538 fwd = bck->fd;
3540 else
3542 victim_index = largebin_index (size);
3543 bck = bin_at (av, victim_index);
3544 fwd = bck->fd;
3546 /* maintain large bins in sorted order */
3547 if (fwd != bck)
3549 /* Or with inuse bit to speed comparisons */
3550 size |= PREV_INUSE;
3551 /* if smaller than smallest, bypass loop below */
3552 assert ((bck->bk->size & NON_MAIN_ARENA) == 0);
3553 if ((unsigned long) (size) < (unsigned long) (bck->bk->size))
3555 fwd = bck;
3556 bck = bck->bk;
3558 victim->fd_nextsize = fwd->fd;
3559 victim->bk_nextsize = fwd->fd->bk_nextsize;
3560 fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
3562 else
3564 assert ((fwd->size & NON_MAIN_ARENA) == 0);
3565 while ((unsigned long) size < fwd->size)
3567 fwd = fwd->fd_nextsize;
3568 assert ((fwd->size & NON_MAIN_ARENA) == 0);
3571 if ((unsigned long) size == (unsigned long) fwd->size)
3572 /* Always insert in the second position. */
3573 fwd = fwd->fd;
3574 else
3576 victim->fd_nextsize = fwd;
3577 victim->bk_nextsize = fwd->bk_nextsize;
3578 fwd->bk_nextsize = victim;
3579 victim->bk_nextsize->fd_nextsize = victim;
3581 bck = fwd->bk;
3584 else
3585 victim->fd_nextsize = victim->bk_nextsize = victim;
3588 mark_bin (av, victim_index);
3589 victim->bk = bck;
3590 victim->fd = fwd;
3591 fwd->bk = victim;
3592 bck->fd = victim;
3594 #define MAX_ITERS 10000
3595 if (++iters >= MAX_ITERS)
3596 break;
3599 /*
3600 If a large request, scan through the chunks of current bin in
3601 sorted order to find smallest that fits. Use the skip list for this.
3602 */
3604 if (!in_smallbin_range (nb))
3606 bin = bin_at (av, idx);
3608 /* skip scan if empty or largest chunk is too small */
3609 if ((victim = first (bin)) != bin &&
3610 (unsigned long) (victim->size) >= (unsigned long) (nb))
3612 victim = victim->bk_nextsize;
3613 while (((unsigned long) (size = chunksize (victim)) <
3614 (unsigned long) (nb)))
3615 victim = victim->bk_nextsize;
3617 /* Avoid removing the first entry for a size so that the skip
3618 list does not have to be rerouted. */
3619 if (victim != last (bin) && victim->size == victim->fd->size)
3620 victim = victim->fd;
3622 remainder_size = size - nb;
3623 unlink (av, victim, bck, fwd);
3625 /* Exhaust */
3626 if (remainder_size < MINSIZE)
3628 set_inuse_bit_at_offset (victim, size);
3629 if (av != &main_arena)
3630 victim->size |= NON_MAIN_ARENA;
3632 /* Split */
3633 else
3635 remainder = chunk_at_offset (victim, nb);
3636 /* We cannot assume the unsorted list is empty and therefore
3637 have to perform a complete insert here. */
3638 bck = unsorted_chunks (av);
3639 fwd = bck->fd;
3640 if (__glibc_unlikely (fwd->bk != bck))
3642 errstr = "malloc(): corrupted unsorted chunks";
3643 goto errout;
3645 remainder->bk = bck;
3646 remainder->fd = fwd;
3647 bck->fd = remainder;
3648 fwd->bk = remainder;
3649 if (!in_smallbin_range (remainder_size))
3651 remainder->fd_nextsize = NULL;
3652 remainder->bk_nextsize = NULL;
3654 set_head (victim, nb | PREV_INUSE |
3655 (av != &main_arena ? NON_MAIN_ARENA : 0));
3656 set_head (remainder, remainder_size | PREV_INUSE);
3657 set_foot (remainder, remainder_size);
3659 check_malloced_chunk (av, victim, nb);
3660 void *p = chunk2mem (victim);
3661 alloc_perturb (p, bytes);
3662 return p;
3666 /*
3667 Search for a chunk by scanning bins, starting with next largest
3668 bin. This search is strictly by best-fit; i.e., the smallest
3669 (with ties going to approximately the least recently used) chunk
3670 that fits is selected.
3672 The bitmap avoids needing to check that most blocks are nonempty.
3673 The particular case of skipping all bins during warm-up phases
3674 when no chunks have been returned yet is faster than it might look.
3675 */
3677 ++idx;
3678 bin = bin_at (av, idx);
3679 block = idx2block (idx);
3680 map = av->binmap[block];
3681 bit = idx2bit (idx);
3683 for (;; )
3685 /* Skip rest of block if there are no more set bits in this block. */
3686 if (bit > map || bit == 0)
3688 do
3690 if (++block >= BINMAPSIZE) /* out of bins */
3691 goto use_top;
3693 while ((map = av->binmap[block]) == 0);
3695 bin = bin_at (av, (block << BINMAPSHIFT));
3696 bit = 1;
3699 /* Advance to bin with set bit. There must be one. */
3700 while ((bit & map) == 0)
3702 bin = next_bin (bin);
3703 bit <<= 1;
3704 assert (bit != 0);
3707 /* Inspect the bin. It is likely to be non-empty */
3708 victim = last (bin);
3710 /* If a false alarm (empty bin), clear the bit. */
3711 if (victim == bin)
3713 av->binmap[block] = map &= ~bit; /* Write through */
3714 bin = next_bin (bin);
3715 bit <<= 1;
3718 else
3720 size = chunksize (victim);
3722 /* We know the first chunk in this bin is big enough to use. */
3723 assert ((unsigned long) (size) >= (unsigned long) (nb));
3725 remainder_size = size - nb;
3727 /* unlink */
3728 unlink (av, victim, bck, fwd);
3730 /* Exhaust */
3731 if (remainder_size < MINSIZE)
3733 set_inuse_bit_at_offset (victim, size);
3734 if (av != &main_arena)
3735 victim->size |= NON_MAIN_ARENA;
3738 /* Split */
3739 else
3741 remainder = chunk_at_offset (victim, nb);
3743 /* We cannot assume the unsorted list is empty and therefore
3744 have to perform a complete insert here. */
3745 bck = unsorted_chunks (av);
3746 fwd = bck->fd;
3747 if (__glibc_unlikely (fwd->bk != bck))
3749 errstr = "malloc(): corrupted unsorted chunks 2";
3750 goto errout;
3752 remainder->bk = bck;
3753 remainder->fd = fwd;
3754 bck->fd = remainder;
3755 fwd->bk = remainder;
3757 /* advertise as last remainder */
3758 if (in_smallbin_range (nb))
3759 av->last_remainder = remainder;
3760 if (!in_smallbin_range (remainder_size))
3762 remainder->fd_nextsize = NULL;
3763 remainder->bk_nextsize = NULL;
3765 set_head (victim, nb | PREV_INUSE |
3766 (av != &main_arena ? NON_MAIN_ARENA : 0));
3767 set_head (remainder, remainder_size | PREV_INUSE);
3768 set_foot (remainder, remainder_size);
3770 check_malloced_chunk (av, victim, nb);
3771 void *p = chunk2mem (victim);
3772 alloc_perturb (p, bytes);
3773 return p;
3777 use_top:
3778 /*
3779 If large enough, split off the chunk bordering the end of memory
3780 (held in av->top). Note that this is in accord with the best-fit
3781 search rule. In effect, av->top is treated as larger (and thus
3782 less well fitting) than any other available chunk since it can
3783 be extended to be as large as necessary (up to system
3784 limitations).
3786 We require that av->top always exists (i.e., has size >=
3787 MINSIZE) after initialization, so if it would otherwise be
3788 exhausted by current request, it is replenished. (The main
3789 reason for ensuring it exists is that we may need MINSIZE space
3790 to put in fenceposts in sysmalloc.)
3791 */
3793 victim = av->top;
3794 size = chunksize (victim);
3796 if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
3798 remainder_size = size - nb;
3799 remainder = chunk_at_offset (victim, nb);
3800 av->top = remainder;
3801 set_head (victim, nb | PREV_INUSE |
3802 (av != &main_arena ? NON_MAIN_ARENA : 0));
3803 set_head (remainder, remainder_size | PREV_INUSE);
3805 check_malloced_chunk (av, victim, nb);
3806 void *p = chunk2mem (victim);
3807 alloc_perturb (p, bytes);
3808 return p;
3811 /* When we are using atomic ops to free fast chunks we can get
3812 here for all block sizes. */
3813 else if (have_fastchunks (av))
3815 malloc_consolidate (av);
3816 /* restore original bin index */
3817 if (in_smallbin_range (nb))
3818 idx = smallbin_index (nb);
3819 else
3820 idx = largebin_index (nb);
3823 /*
3824 Otherwise, relay to handle system-dependent cases
3825 */
3826 else
3828 void *p = sysmalloc (nb, av);
3829 if (p != NULL)
3830 alloc_perturb (p, bytes);
3831 return p;
3836 /*
3837 ------------------------------ free ------------------------------
3838 */
3840 static void
3841 _int_free (mstate av, mchunkptr p, int have_lock)
3843 INTERNAL_SIZE_T size; /* its size */
3844 mfastbinptr *fb; /* associated fastbin */
3845 mchunkptr nextchunk; /* next contiguous chunk */
3846 INTERNAL_SIZE_T nextsize; /* its size */
3847 int nextinuse; /* true if nextchunk is used */
3848 INTERNAL_SIZE_T prevsize; /* size of previous contiguous chunk */
3849 mchunkptr bck; /* misc temp for linking */
3850 mchunkptr fwd; /* misc temp for linking */
3852 const char *errstr = NULL;
3853 int locked = 0;
3855 size = chunksize (p);
3857 /* Little security check which won't hurt performance: the
3858 allocator never wrapps around at the end of the address space.
3859 Therefore we can exclude some size values which might appear
3860 here by accident or by "design" from some intruder. */
3861 if (__builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0)
3862 || __builtin_expect (misaligned_chunk (p), 0))
3864 errstr = "free(): invalid pointer";
3865 errout:
3866 if (!have_lock && locked)
3867 (void) mutex_unlock (&av->mutex);
3868 malloc_printerr (check_action, errstr, chunk2mem (p), av);
3869 return;
3871 /* We know that each chunk is at least MINSIZE bytes in size or a
3872 multiple of MALLOC_ALIGNMENT. */
3873 if (__glibc_unlikely (size < MINSIZE || !aligned_OK (size)))
3875 errstr = "free(): invalid size";
3876 goto errout;
3879 check_inuse_chunk(av, p);
3881 /*
3882 If eligible, place chunk on a fastbin so it can be found
3883 and used quickly in malloc.
3884 */
3886 if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())
3888 #if TRIM_FASTBINS
3889 /*
3890 If TRIM_FASTBINS set, don't place chunks
3891 bordering top into fastbins
3892 */
3893 && (chunk_at_offset(p, size) != av->top)
3894 #endif
3895 ) {
3897 if (__builtin_expect (chunk_at_offset (p, size)->size <= 2 * SIZE_SZ, 0)
3898 || __builtin_expect (chunksize (chunk_at_offset (p, size))
3899 >= av->system_mem, 0))
3901 /* We might not have a lock at this point and concurrent modifications
3902 of system_mem might have let to a false positive. Redo the test
3903 after getting the lock. */
3904 if (have_lock
3905 || ({ assert (locked == 0);
3906 mutex_lock(&av->mutex);
3907 locked = 1;
3908 chunk_at_offset (p, size)->size <= 2 * SIZE_SZ
3909 || chunksize (chunk_at_offset (p, size)) >= av->system_mem;
3910 }))
3912 errstr = "free(): invalid next size (fast)";
3913 goto errout;
3915 if (! have_lock)
3917 (void)mutex_unlock(&av->mutex);
3918 locked = 0;
3922 free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
3924 set_fastchunks(av);
3925 unsigned int idx = fastbin_index(size);
3926 fb = &fastbin (av, idx);
3928 /* Atomically link P to its fastbin: P->FD = *FB; *FB = P; */
3929 mchunkptr old = *fb, old2;
3930 unsigned int old_idx = ~0u;
3931 do
3933 /* Check that the top of the bin is not the record we are going to add
3934 (i.e., double free). */
3935 if (__builtin_expect (old == p, 0))
3937 errstr = "double free or corruption (fasttop)";
3938 goto errout;
3940 /* Check that size of fastbin chunk at the top is the same as
3941 size of the chunk that we are adding. We can dereference OLD
3942 only if we have the lock, otherwise it might have already been
3943 deallocated. See use of OLD_IDX below for the actual check. */
3944 if (have_lock && old != NULL)
3945 old_idx = fastbin_index(chunksize(old));
3946 p->fd = old2 = old;
3948 while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2);
3950 if (have_lock && old != NULL && __builtin_expect (old_idx != idx, 0))
3952 errstr = "invalid fastbin entry (free)";
3953 goto errout;
3957 /*
3958 Consolidate other non-mmapped chunks as they arrive.
3959 */
3961 else if (!chunk_is_mmapped(p)) {
3962 if (! have_lock) {
3963 (void)mutex_lock(&av->mutex);
3964 locked = 1;
3967 nextchunk = chunk_at_offset(p, size);
3969 /* Lightweight tests: check whether the block is already the
3970 top block. */
3971 if (__glibc_unlikely (p == av->top))
3973 errstr = "double free or corruption (top)";
3974 goto errout;
3976 /* Or whether the next chunk is beyond the boundaries of the arena. */
3977 if (__builtin_expect (contiguous (av)
3978 && (char *) nextchunk
3979 >= ((char *) av->top + chunksize(av->top)), 0))
3981 errstr = "double free or corruption (out)";
3982 goto errout;
3984 /* Or whether the block is actually not marked used. */
3985 if (__glibc_unlikely (!prev_inuse(nextchunk)))
3987 errstr = "double free or corruption (!prev)";
3988 goto errout;
3991 nextsize = chunksize(nextchunk);
3992 if (__builtin_expect (nextchunk->size <= 2 * SIZE_SZ, 0)
3993 || __builtin_expect (nextsize >= av->system_mem, 0))
3995 errstr = "free(): invalid next size (normal)";
3996 goto errout;
3999 free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
4001 /* consolidate backward */
4002 if (!prev_inuse(p)) {
4003 prevsize = p->prev_size;
4004 size += prevsize;
4005 p = chunk_at_offset(p, -((long) prevsize));
4006 unlink(av, p, bck, fwd);
4009 if (nextchunk != av->top) {
4010 /* get and clear inuse bit */
4011 nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
4013 /* consolidate forward */
4014 if (!nextinuse) {
4015 unlink(av, nextchunk, bck, fwd);
4016 size += nextsize;
4017 } else
4018 clear_inuse_bit_at_offset(nextchunk, 0);
4020 /*
4021 Place the chunk in unsorted chunk list. Chunks are
4022 not placed into regular bins until after they have
4023 been given one chance to be used in malloc.
4024 */
4026 bck = unsorted_chunks(av);
4027 fwd = bck->fd;
4028 if (__glibc_unlikely (fwd->bk != bck))
4030 errstr = "free(): corrupted unsorted chunks";
4031 goto errout;
4033 p->fd = fwd;
4034 p->bk = bck;
4035 if (!in_smallbin_range(size))
4037 p->fd_nextsize = NULL;
4038 p->bk_nextsize = NULL;
4040 bck->fd = p;
4041 fwd->bk = p;
4043 set_head(p, size | PREV_INUSE);
4044 set_foot(p, size);
4046 check_free_chunk(av, p);
4049 /*
4050 If the chunk borders the current high end of memory,
4051 consolidate into top
4052 */
4054 else {
4055 size += nextsize;
4056 set_head(p, size | PREV_INUSE);
4057 av->top = p;
4058 check_chunk(av, p);
4061 /*
4062 If freeing a large space, consolidate possibly-surrounding
4063 chunks. Then, if the total unused topmost memory exceeds trim
4064 threshold, ask malloc_trim to reduce top.
4066 Unless max_fast is 0, we don't know if there are fastbins
4067 bordering top, so we cannot tell for sure whether threshold
4068 has been reached unless fastbins are consolidated. But we
4069 don't want to consolidate on each free. As a compromise,
4070 consolidation is performed if FASTBIN_CONSOLIDATION_THRESHOLD
4071 is reached.
4072 */
4074 if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
4075 if (have_fastchunks(av))
4076 malloc_consolidate(av);
4078 if (av == &main_arena) {
4079 #ifndef MORECORE_CANNOT_TRIM
4080 if ((unsigned long)(chunksize(av->top)) >=
4081 (unsigned long)(mp_.trim_threshold))
4082 systrim(mp_.top_pad, av);
4083 #endif
4084 } else {
4085 /* Always try heap_trim(), even if the top chunk is not
4086 large, because the corresponding heap might go away. */
4087 heap_info *heap = heap_for_ptr(top(av));
4089 assert(heap->ar_ptr == av);
4090 heap_trim(heap, mp_.top_pad);
4094 if (! have_lock) {
4095 assert (locked);
4096 (void)mutex_unlock(&av->mutex);
4099 /*
4100 If the chunk was allocated via mmap, release via munmap().
4101 */
4103 else {
4104 munmap_chunk (p);
4108 /*
4109 ------------------------- malloc_consolidate -------------------------
4111 malloc_consolidate is a specialized version of free() that tears
4112 down chunks held in fastbins. Free itself cannot be used for this
4113 purpose since, among other things, it might place chunks back onto
4114 fastbins. So, instead, we need to use a minor variant of the same
4115 code.
4117 Also, because this routine needs to be called the first time through
4118 malloc anyway, it turns out to be the perfect place to trigger
4119 initialization code.
4120 */
4122 static void malloc_consolidate(mstate av)
4124 mfastbinptr* fb; /* current fastbin being consolidated */
4125 mfastbinptr* maxfb; /* last fastbin (for loop control) */
4126 mchunkptr p; /* current chunk being consolidated */
4127 mchunkptr nextp; /* next chunk to consolidate */
4128 mchunkptr unsorted_bin; /* bin header */
4129 mchunkptr first_unsorted; /* chunk to link to */
4131 /* These have same use as in free() */
4132 mchunkptr nextchunk;
4133 INTERNAL_SIZE_T size;
4134 INTERNAL_SIZE_T nextsize;
4135 INTERNAL_SIZE_T prevsize;
4136 int nextinuse;
4137 mchunkptr bck;
4138 mchunkptr fwd;
4140 /*
4141 If max_fast is 0, we know that av hasn't
4142 yet been initialized, in which case do so below
4143 */
4145 if (get_max_fast () != 0) {
4146 clear_fastchunks(av);
4148 unsorted_bin = unsorted_chunks(av);
4150 /*
4151 Remove each chunk from fast bin and consolidate it, placing it
4152 then in unsorted bin. Among other reasons for doing this,
4153 placing in unsorted bin avoids needing to calculate actual bins
4154 until malloc is sure that chunks aren't immediately going to be
4155 reused anyway.
4156 */
4158 maxfb = &fastbin (av, NFASTBINS - 1);
4159 fb = &fastbin (av, 0);
4160 do {
4161 p = atomic_exchange_acq (fb, 0);
4162 if (p != 0) {
4163 do {
4164 check_inuse_chunk(av, p);
4165 nextp = p->fd;
4167 /* Slightly streamlined version of consolidation code in free() */
4168 size = p->size & ~(PREV_INUSE|NON_MAIN_ARENA);
4169 nextchunk = chunk_at_offset(p, size);
4170 nextsize = chunksize(nextchunk);
4172 if (!prev_inuse(p)) {
4173 prevsize = p->prev_size;
4174 size += prevsize;
4175 p = chunk_at_offset(p, -((long) prevsize));
4176 unlink(av, p, bck, fwd);
4179 if (nextchunk != av->top) {
4180 nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
4182 if (!nextinuse) {
4183 size += nextsize;
4184 unlink(av, nextchunk, bck, fwd);
4185 } else
4186 clear_inuse_bit_at_offset(nextchunk, 0);
4188 first_unsorted = unsorted_bin->fd;
4189 unsorted_bin->fd = p;
4190 first_unsorted->bk = p;
4192 if (!in_smallbin_range (size)) {
4193 p->fd_nextsize = NULL;
4194 p->bk_nextsize = NULL;
4197 set_head(p, size | PREV_INUSE);
4198 p->bk = unsorted_bin;
4199 p->fd = first_unsorted;
4200 set_foot(p, size);
4203 else {
4204 size += nextsize;
4205 set_head(p, size | PREV_INUSE);
4206 av->top = p;
4209 } while ( (p = nextp) != 0);
4212 } while (fb++ != maxfb);
4214 else {
4215 malloc_init_state(av);
4216 check_malloc_state(av);
4220 /*
4221 ------------------------------ realloc ------------------------------
4222 */
4224 void*
4225 _int_realloc(mstate av, mchunkptr oldp, INTERNAL_SIZE_T oldsize,
4226 INTERNAL_SIZE_T nb)
4228 mchunkptr newp; /* chunk to return */
4229 INTERNAL_SIZE_T newsize; /* its size */
4230 void* newmem; /* corresponding user mem */
4232 mchunkptr next; /* next contiguous chunk after oldp */
4234 mchunkptr remainder; /* extra space at end of newp */
4235 unsigned long remainder_size; /* its size */
4237 mchunkptr bck; /* misc temp for linking */
4238 mchunkptr fwd; /* misc temp for linking */
4240 unsigned long copysize; /* bytes to copy */
4241 unsigned int ncopies; /* INTERNAL_SIZE_T words to copy */
4242 INTERNAL_SIZE_T* s; /* copy source */
4243 INTERNAL_SIZE_T* d; /* copy destination */
4245 const char *errstr = NULL;
4247 /* oldmem size */
4248 if (__builtin_expect (oldp->size <= 2 * SIZE_SZ, 0)
4249 || __builtin_expect (oldsize >= av->system_mem, 0))
4251 errstr = "realloc(): invalid old size";
4252 errout:
4253 malloc_printerr (check_action, errstr, chunk2mem (oldp), av);
4254 return NULL;
4257 check_inuse_chunk (av, oldp);
4259 /* All callers already filter out mmap'ed chunks. */
4260 assert (!chunk_is_mmapped (oldp));
4262 next = chunk_at_offset (oldp, oldsize);
4263 INTERNAL_SIZE_T nextsize = chunksize (next);
4264 if (__builtin_expect (next->size <= 2 * SIZE_SZ, 0)
4265 || __builtin_expect (nextsize >= av->system_mem, 0))
4267 errstr = "realloc(): invalid next size";
4268 goto errout;
4271 if ((unsigned long) (oldsize) >= (unsigned long) (nb))
4273 /* already big enough; split below */
4274 newp = oldp;
4275 newsize = oldsize;
4278 else
4280 /* Try to expand forward into top */
4281 if (next == av->top &&
4282 (unsigned long) (newsize = oldsize + nextsize) >=
4283 (unsigned long) (nb + MINSIZE))
4285 set_head_size (oldp, nb | (av != &main_arena ? NON_MAIN_ARENA : 0));
4286 av->top = chunk_at_offset (oldp, nb);
4287 set_head (av->top, (newsize - nb) | PREV_INUSE);
4288 check_inuse_chunk (av, oldp);
4289 return chunk2mem (oldp);
4292 /* Try to expand forward into next chunk; split off remainder below */
4293 else if (next != av->top &&
4294 !inuse (next) &&
4295 (unsigned long) (newsize = oldsize + nextsize) >=
4296 (unsigned long) (nb))
4298 newp = oldp;
4299 unlink (av, next, bck, fwd);
4302 /* allocate, copy, free */
4303 else
4305 newmem = _int_malloc (av, nb - MALLOC_ALIGN_MASK);
4306 if (newmem == 0)
4307 return 0; /* propagate failure */
4309 newp = mem2chunk (newmem);
4310 newsize = chunksize (newp);
4312 /*
4313 Avoid copy if newp is next chunk after oldp.
4314 */
4315 if (newp == next)
4317 newsize += oldsize;
4318 newp = oldp;
4320 else
4322 /*
4323 Unroll copy of <= 36 bytes (72 if 8byte sizes)
4324 We know that contents have an odd number of
4325 INTERNAL_SIZE_T-sized words; minimally 3.
4326 */
4328 copysize = oldsize - SIZE_SZ;
4329 s = (INTERNAL_SIZE_T *) (chunk2mem (oldp));
4330 d = (INTERNAL_SIZE_T *) (newmem);
4331 ncopies = copysize / sizeof (INTERNAL_SIZE_T);
4332 assert (ncopies >= 3);
4334 if (ncopies > 9)
4335 memcpy (d, s, copysize);
4337 else
4339 *(d + 0) = *(s + 0);
4340 *(d + 1) = *(s + 1);
4341 *(d + 2) = *(s + 2);
4342 if (ncopies > 4)
4344 *(d + 3) = *(s + 3);
4345 *(d + 4) = *(s + 4);
4346 if (ncopies > 6)
4348 *(d + 5) = *(s + 5);
4349 *(d + 6) = *(s + 6);
4350 if (ncopies > 8)
4352 *(d + 7) = *(s + 7);
4353 *(d + 8) = *(s + 8);
4359 _int_free (av, oldp, 1);
4360 check_inuse_chunk (av, newp);
4361 return chunk2mem (newp);
4366 /* If possible, free extra space in old or extended chunk */
4368 assert ((unsigned long) (newsize) >= (unsigned long) (nb));
4370 remainder_size = newsize - nb;
4372 if (remainder_size < MINSIZE) /* not enough extra to split off */
4374 set_head_size (newp, newsize | (av != &main_arena ? NON_MAIN_ARENA : 0));
4375 set_inuse_bit_at_offset (newp, newsize);
4377 else /* split remainder */
4379 remainder = chunk_at_offset (newp, nb);
4380 set_head_size (newp, nb | (av != &main_arena ? NON_MAIN_ARENA : 0));
4381 set_head (remainder, remainder_size | PREV_INUSE |
4382 (av != &main_arena ? NON_MAIN_ARENA : 0));
4383 /* Mark remainder as inuse so free() won't complain */
4384 set_inuse_bit_at_offset (remainder, remainder_size);
4385 _int_free (av, remainder, 1);
4388 check_inuse_chunk (av, newp);
4389 return chunk2mem (newp);
4392 /*
4393 ------------------------------ memalign ------------------------------
4394 */
4396 static void *
4397 _int_memalign (mstate av, size_t alignment, size_t bytes)
4399 INTERNAL_SIZE_T nb; /* padded request size */
4400 char *m; /* memory returned by malloc call */
4401 mchunkptr p; /* corresponding chunk */
4402 char *brk; /* alignment point within p */
4403 mchunkptr newp; /* chunk to return */
4404 INTERNAL_SIZE_T newsize; /* its size */
4405 INTERNAL_SIZE_T leadsize; /* leading space before alignment point */
4406 mchunkptr remainder; /* spare room at end to split off */
4407 unsigned long remainder_size; /* its size */
4408 INTERNAL_SIZE_T size;
4412 checked_request2size (bytes, nb);
4414 /*
4415 Strategy: find a spot within that chunk that meets the alignment
4416 request, and then possibly free the leading and trailing space.
4417 */
4420 /* Call malloc with worst case padding to hit alignment. */
4422 m = (char *) (_int_malloc (av, nb + alignment + MINSIZE));
4424 if (m == 0)
4425 return 0; /* propagate failure */
4427 p = mem2chunk (m);
4429 if ((((unsigned long) (m)) % alignment) != 0) /* misaligned */
4431 { /*
4432 Find an aligned spot inside chunk. Since we need to give back
4433 leading space in a chunk of at least MINSIZE, if the first
4434 calculation places us at a spot with less than MINSIZE leader,
4435 we can move to the next aligned spot -- we've allocated enough
4436 total room so that this is always possible.
4437 */
4438 brk = (char *) mem2chunk (((unsigned long) (m + alignment - 1)) &
4439 - ((signed long) alignment));
4440 if ((unsigned long) (brk - (char *) (p)) < MINSIZE)
4441 brk += alignment;
4443 newp = (mchunkptr) brk;
4444 leadsize = brk - (char *) (p);
4445 newsize = chunksize (p) - leadsize;
4447 /* For mmapped chunks, just adjust offset */
4448 if (chunk_is_mmapped (p))
4450 newp->prev_size = p->prev_size + leadsize;
4451 set_head (newp, newsize | IS_MMAPPED);
4452 return chunk2mem (newp);
4455 /* Otherwise, give back leader, use the rest */
4456 set_head (newp, newsize | PREV_INUSE |
4457 (av != &main_arena ? NON_MAIN_ARENA : 0));
4458 set_inuse_bit_at_offset (newp, newsize);
4459 set_head_size (p, leadsize | (av != &main_arena ? NON_MAIN_ARENA : 0));
4460 _int_free (av, p, 1);
4461 p = newp;
4463 assert (newsize >= nb &&
4464 (((unsigned long) (chunk2mem (p))) % alignment) == 0);
4467 /* Also give back spare room at the end */
4468 if (!chunk_is_mmapped (p))
4470 size = chunksize (p);
4471 if ((unsigned long) (size) > (unsigned long) (nb + MINSIZE))
4473 remainder_size = size - nb;
4474 remainder = chunk_at_offset (p, nb);
4475 set_head (remainder, remainder_size | PREV_INUSE |
4476 (av != &main_arena ? NON_MAIN_ARENA : 0));
4477 set_head_size (p, nb);
4478 _int_free (av, remainder, 1);
4482 check_inuse_chunk (av, p);
4483 return chunk2mem (p);
4487 /*
4488 ------------------------------ malloc_trim ------------------------------
4489 */
4491 static int
4492 mtrim (mstate av, size_t pad)
4494 /* Don't touch corrupt arenas. */
4495 if (arena_is_corrupt (av))
4496 return 0;
4498 /* Ensure initialization/consolidation */
4499 malloc_consolidate (av);
4501 const size_t ps = GLRO (dl_pagesize);
4502 int psindex = bin_index (ps);
4503 const size_t psm1 = ps - 1;
4505 int result = 0;
4506 for (int i = 1; i < NBINS; ++i)
4507 if (i == 1 || i >= psindex)
4509 mbinptr bin = bin_at (av, i);
4511 for (mchunkptr p = last (bin); p != bin; p = p->bk)
4513 INTERNAL_SIZE_T size = chunksize (p);
4515 if (size > psm1 + sizeof (struct malloc_chunk))
4517 /* See whether the chunk contains at least one unused page. */
4518 char *paligned_mem = (char *) (((uintptr_t) p
4519 + sizeof (struct malloc_chunk)
4520 + psm1) & ~psm1);
4522 assert ((char *) chunk2mem (p) + 4 * SIZE_SZ <= paligned_mem);
4523 assert ((char *) p + size > paligned_mem);
4525 /* This is the size we could potentially free. */
4526 size -= paligned_mem - (char *) p;
4528 if (size > psm1)
4530 #if MALLOC_DEBUG
4531 /* When debugging we simulate destroying the memory
4532 content. */
4533 memset (paligned_mem, 0x89, size & ~psm1);
4534 #endif
4535 __madvise (paligned_mem, size & ~psm1, MADV_DONTNEED);
4537 result = 1;
4543 #ifndef MORECORE_CANNOT_TRIM
4544 return result | (av == &main_arena ? systrim (pad, av) : 0);
4546 #else
4547 return result;
4548 #endif
4552 int
4553 __malloc_trim (size_t s)
4555 int result = 0;
4557 if (__malloc_initialized < 0)
4558 ptmalloc_init ();
4560 mstate ar_ptr = &main_arena;
4561 do
4563 (void) mutex_lock (&ar_ptr->mutex);
4564 result |= mtrim (ar_ptr, s);
4565 (void) mutex_unlock (&ar_ptr->mutex);
4567 ar_ptr = ar_ptr->next;
4569 while (ar_ptr != &main_arena);
4571 return result;
4575 /*
4576 ------------------------- malloc_usable_size -------------------------
4577 */
4579 static size_t
4580 musable (void *mem)
4582 mchunkptr p;
4583 if (mem != 0)
4585 p = mem2chunk (mem);
4587 if (__builtin_expect (using_malloc_checking == 1, 0))
4588 return malloc_check_get_size (p);
4590 if (chunk_is_mmapped (p))
4591 return chunksize (p) - 2 * SIZE_SZ;
4592 else if (inuse (p))
4593 return chunksize (p) - SIZE_SZ;
4595 return 0;
4599 size_t
4600 __malloc_usable_size (void *m)
4602 size_t result;
4604 result = musable (m);
4605 return result;
4608 /*
4609 ------------------------------ mallinfo ------------------------------
4610 Accumulate malloc statistics for arena AV into M.
4611 */
4613 static void
4614 int_mallinfo (mstate av, struct mallinfo *m)
4616 size_t i;
4617 mbinptr b;
4618 mchunkptr p;
4619 INTERNAL_SIZE_T avail;
4620 INTERNAL_SIZE_T fastavail;
4621 int nblocks;
4622 int nfastblocks;
4624 /* Ensure initialization */
4625 if (av->top == 0)
4626 malloc_consolidate (av);
4628 check_malloc_state (av);
4630 /* Account for top */
4631 avail = chunksize (av->top);
4632 nblocks = 1; /* top always exists */
4634 /* traverse fastbins */
4635 nfastblocks = 0;
4636 fastavail = 0;
4638 for (i = 0; i < NFASTBINS; ++i)
4640 for (p = fastbin (av, i); p != 0; p = p->fd)
4642 ++nfastblocks;
4643 fastavail += chunksize (p);
4647 avail += fastavail;
4649 /* traverse regular bins */
4650 for (i = 1; i < NBINS; ++i)
4652 b = bin_at (av, i);
4653 for (p = last (b); p != b; p = p->bk)
4655 ++nblocks;
4656 avail += chunksize (p);
4660 m->smblks += nfastblocks;
4661 m->ordblks += nblocks;
4662 m->fordblks += avail;
4663 m->uordblks += av->system_mem - avail;
4664 m->arena += av->system_mem;
4665 m->fsmblks += fastavail;
4666 if (av == &main_arena)
4668 m->hblks = mp_.n_mmaps;
4669 m->hblkhd = mp_.mmapped_mem;
4670 m->usmblks = mp_.max_total_mem;
4671 m->keepcost = chunksize (av->top);
4676 struct mallinfo
4677 __libc_mallinfo (void)
4679 struct mallinfo m;
4680 mstate ar_ptr;
4682 if (__malloc_initialized < 0)
4683 ptmalloc_init ();
4685 memset (&m, 0, sizeof (m));
4686 ar_ptr = &main_arena;
4687 do
4689 (void) mutex_lock (&ar_ptr->mutex);
4690 int_mallinfo (ar_ptr, &m);
4691 (void) mutex_unlock (&ar_ptr->mutex);
4693 ar_ptr = ar_ptr->next;
4695 while (ar_ptr != &main_arena);
4697 return m;
4700 /*
4701 ------------------------------ malloc_stats ------------------------------
4702 */
4704 void
4705 __malloc_stats (void)
4707 int i;
4708 mstate ar_ptr;
4709 unsigned int in_use_b = mp_.mmapped_mem, system_b = in_use_b;
4711 if (__malloc_initialized < 0)
4712 ptmalloc_init ();
4713 _IO_flockfile (stderr);
4714 int old_flags2 = ((_IO_FILE *) stderr)->_flags2;
4715 ((_IO_FILE *) stderr)->_flags2 |= _IO_FLAGS2_NOTCANCEL;
4716 for (i = 0, ar_ptr = &main_arena;; i++)
4718 struct mallinfo mi;
4720 memset (&mi, 0, sizeof (mi));
4721 (void) mutex_lock (&ar_ptr->mutex);
4722 int_mallinfo (ar_ptr, &mi);
4723 fprintf (stderr, "Arena %d:\n", i);
4724 fprintf (stderr, "system bytes = %10u\n", (unsigned int) mi.arena);
4725 fprintf (stderr, "in use bytes = %10u\n", (unsigned int) mi.uordblks);
4726 #if MALLOC_DEBUG > 1
4727 if (i > 0)
4728 dump_heap (heap_for_ptr (top (ar_ptr)));
4729 #endif
4730 system_b += mi.arena;
4731 in_use_b += mi.uordblks;
4732 (void) mutex_unlock (&ar_ptr->mutex);
4733 ar_ptr = ar_ptr->next;
4734 if (ar_ptr == &main_arena)
4735 break;
4737 fprintf (stderr, "Total (incl. mmap):\n");
4738 fprintf (stderr, "system bytes = %10u\n", system_b);
4739 fprintf (stderr, "in use bytes = %10u\n", in_use_b);
4740 fprintf (stderr, "max mmap regions = %10u\n", (unsigned int) mp_.max_n_mmaps);
4741 fprintf (stderr, "max mmap bytes = %10lu\n",
4742 (unsigned long) mp_.max_mmapped_mem);
4743 ((_IO_FILE *) stderr)->_flags2 |= old_flags2;
4744 _IO_funlockfile (stderr);
4748 /*
4749 ------------------------------ mallopt ------------------------------
4750 */
4752 int
4753 __libc_mallopt (int param_number, int value)
4755 mstate av = &main_arena;
4756 int res = 1;
4758 if (__malloc_initialized < 0)
4759 ptmalloc_init ();
4760 (void) mutex_lock (&av->mutex);
4761 /* Ensure initialization/consolidation */
4762 malloc_consolidate (av);
4764 LIBC_PROBE (memory_mallopt, 2, param_number, value);
4766 switch (param_number)
4768 case M_MXFAST:
4769 if (value >= 0 && value <= MAX_FAST_SIZE)
4771 LIBC_PROBE (memory_mallopt_mxfast, 2, value, get_max_fast ());
4772 set_max_fast (value);
4774 else
4775 res = 0;
4776 break;
4778 case M_TRIM_THRESHOLD:
4779 LIBC_PROBE (memory_mallopt_trim_threshold, 3, value,
4780 mp_.trim_threshold, mp_.no_dyn_threshold);
4781 mp_.trim_threshold = value;
4782 mp_.no_dyn_threshold = 1;
4783 break;
4785 case M_TOP_PAD:
4786 LIBC_PROBE (memory_mallopt_top_pad, 3, value,
4787 mp_.top_pad, mp_.no_dyn_threshold);
4788 mp_.top_pad = value;
4789 mp_.no_dyn_threshold = 1;
4790 break;
4792 case M_MMAP_THRESHOLD:
4793 /* Forbid setting the threshold too high. */
4794 if ((unsigned long) value > HEAP_MAX_SIZE / 2)
4795 res = 0;
4796 else
4798 LIBC_PROBE (memory_mallopt_mmap_threshold, 3, value,
4799 mp_.mmap_threshold, mp_.no_dyn_threshold);
4800 mp_.mmap_threshold = value;
4801 mp_.no_dyn_threshold = 1;
4803 break;
4805 case M_MMAP_MAX:
4806 LIBC_PROBE (memory_mallopt_mmap_max, 3, value,
4807 mp_.n_mmaps_max, mp_.no_dyn_threshold);
4808 mp_.n_mmaps_max = value;
4809 mp_.no_dyn_threshold = 1;
4810 break;
4812 case M_CHECK_ACTION:
4813 LIBC_PROBE (memory_mallopt_check_action, 2, value, check_action);
4814 check_action = value;
4815 break;
4817 case M_PERTURB:
4818 LIBC_PROBE (memory_mallopt_perturb, 2, value, perturb_byte);
4819 perturb_byte = value;
4820 break;
4822 case M_ARENA_TEST:
4823 if (value > 0)
4825 LIBC_PROBE (memory_mallopt_arena_test, 2, value, mp_.arena_test);
4826 mp_.arena_test = value;
4828 break;
4830 case M_ARENA_MAX:
4831 if (value > 0)
4833 LIBC_PROBE (memory_mallopt_arena_max, 2, value, mp_.arena_max);
4834 mp_.arena_max = value;
4836 break;
4838 (void) mutex_unlock (&av->mutex);
4839 return res;
4841 libc_hidden_def (__libc_mallopt)
4844 /*
4845 -------------------- Alternative MORECORE functions --------------------
4846 */
4849 /*
4850 General Requirements for MORECORE.
4852 The MORECORE function must have the following properties:
4854 If MORECORE_CONTIGUOUS is false:
4856 * MORECORE must allocate in multiples of pagesize. It will
4857 only be called with arguments that are multiples of pagesize.
4859 * MORECORE(0) must return an address that is at least
4860 MALLOC_ALIGNMENT aligned. (Page-aligning always suffices.)
4862 else (i.e. If MORECORE_CONTIGUOUS is true):
4864 * Consecutive calls to MORECORE with positive arguments
4865 return increasing addresses, indicating that space has been
4866 contiguously extended.
4868 * MORECORE need not allocate in multiples of pagesize.
4869 Calls to MORECORE need not have args of multiples of pagesize.
4871 * MORECORE need not page-align.
4873 In either case:
4875 * MORECORE may allocate more memory than requested. (Or even less,
4876 but this will generally result in a malloc failure.)
4878 * MORECORE must not allocate memory when given argument zero, but
4879 instead return one past the end address of memory from previous
4880 nonzero call. This malloc does NOT call MORECORE(0)
4881 until at least one call with positive arguments is made, so
4882 the initial value returned is not important.
4884 * Even though consecutive calls to MORECORE need not return contiguous
4885 addresses, it must be OK for malloc'ed chunks to span multiple
4886 regions in those cases where they do happen to be contiguous.
4888 * MORECORE need not handle negative arguments -- it may instead
4889 just return MORECORE_FAILURE when given negative arguments.
4890 Negative arguments are always multiples of pagesize. MORECORE
4891 must not misinterpret negative args as large positive unsigned
4892 args. You can suppress all such calls from even occurring by defining
4893 MORECORE_CANNOT_TRIM,
4895 There is some variation across systems about the type of the
4896 argument to sbrk/MORECORE. If size_t is unsigned, then it cannot
4897 actually be size_t, because sbrk supports negative args, so it is
4898 normally the signed type of the same width as size_t (sometimes
4899 declared as "intptr_t", and sometimes "ptrdiff_t"). It doesn't much
4900 matter though. Internally, we use "long" as arguments, which should
4901 work across all reasonable possibilities.
4903 Additionally, if MORECORE ever returns failure for a positive
4904 request, then mmap is used as a noncontiguous system allocator. This
4905 is a useful backup strategy for systems with holes in address spaces
4906 -- in this case sbrk cannot contiguously expand the heap, but mmap
4907 may be able to map noncontiguous space.
4909 If you'd like mmap to ALWAYS be used, you can define MORECORE to be
4910 a function that always returns MORECORE_FAILURE.
4912 If you are using this malloc with something other than sbrk (or its
4913 emulation) to supply memory regions, you probably want to set
4914 MORECORE_CONTIGUOUS as false. As an example, here is a custom
4915 allocator kindly contributed for pre-OSX macOS. It uses virtually
4916 but not necessarily physically contiguous non-paged memory (locked
4917 in, present and won't get swapped out). You can use it by
4918 uncommenting this section, adding some #includes, and setting up the
4919 appropriate defines above:
4921 *#define MORECORE osMoreCore
4922 *#define MORECORE_CONTIGUOUS 0
4924 There is also a shutdown routine that should somehow be called for
4925 cleanup upon program exit.
4927 *#define MAX_POOL_ENTRIES 100
4928 *#define MINIMUM_MORECORE_SIZE (64 * 1024)
4929 static int next_os_pool;
4930 void *our_os_pools[MAX_POOL_ENTRIES];
4932 void *osMoreCore(int size)
4934 void *ptr = 0;
4935 static void *sbrk_top = 0;
4937 if (size > 0)
4939 if (size < MINIMUM_MORECORE_SIZE)
4940 size = MINIMUM_MORECORE_SIZE;
4941 if (CurrentExecutionLevel() == kTaskLevel)
4942 ptr = PoolAllocateResident(size + RM_PAGE_SIZE, 0);
4943 if (ptr == 0)
4945 return (void *) MORECORE_FAILURE;
4947 // save ptrs so they can be freed during cleanup
4948 our_os_pools[next_os_pool] = ptr;
4949 next_os_pool++;
4950 ptr = (void *) ((((unsigned long) ptr) + RM_PAGE_MASK) & ~RM_PAGE_MASK);
4951 sbrk_top = (char *) ptr + size;
4952 return ptr;
4954 else if (size < 0)
4956 // we don't currently support shrink behavior
4957 return (void *) MORECORE_FAILURE;
4959 else
4961 return sbrk_top;
4965 // cleanup any allocated memory pools
4966 // called as last thing before shutting down driver
4968 void osCleanupMem(void)
4970 void **ptr;
4972 for (ptr = our_os_pools; ptr < &our_os_pools[MAX_POOL_ENTRIES]; ptr++)
4973 if (*ptr)
4975 PoolDeallocate(*ptr);
4976 * ptr = 0;
4980 */
4983 /* Helper code. */
4985 extern char **__libc_argv attribute_hidden;
4987 static void
4988 malloc_printerr (int action, const char *str, void *ptr, mstate ar_ptr)
4990 /* Avoid using this arena in future. We do not attempt to synchronize this
4991 with anything else because we minimally want to ensure that __libc_message
4992 gets its resources safely without stumbling on the current corruption. */
4993 if (ar_ptr)
4994 set_arena_corrupt (ar_ptr);
4996 if ((action & 5) == 5)
4997 __libc_message (action & 2, "%s\n", str);
4998 else if (action & 1)
5000 char buf[2 * sizeof (uintptr_t) + 1];
5002 buf[sizeof (buf) - 1] = '\0';
5003 char *cp = _itoa_word ((uintptr_t) ptr, &buf[sizeof (buf) - 1], 16, 0);
5004 while (cp > buf)
5005 *--cp = '0';
5007 __libc_message (action & 2, "*** Error in `%s': %s: 0x%s ***\n",
5008 __libc_argv[0] ? : "<unknown>", str, cp);
5010 else if (action & 2)
5011 abort ();
5014 /* We need a wrapper function for one of the additions of POSIX. */
5015 int
5016 __posix_memalign (void **memptr, size_t alignment, size_t size)
5018 void *mem;
5020 /* Test whether the SIZE argument is valid. It must be a power of
5021 two multiple of sizeof (void *). */
5022 if (alignment % sizeof (void *) != 0
5023 || !powerof2 (alignment / sizeof (void *))
5024 || alignment == 0)
5025 return EINVAL;
5028 void *address = RETURN_ADDRESS (0);
5029 mem = _mid_memalign (alignment, size, address);
5031 if (mem != NULL)
5033 *memptr = mem;
5034 return 0;
5037 return ENOMEM;
5039 weak_alias (__posix_memalign, posix_memalign)
5042 int
5043 __malloc_info (int options, FILE *fp)
5045 /* For now, at least. */
5046 if (options != 0)
5047 return EINVAL;
5049 int n = 0;
5050 size_t total_nblocks = 0;
5051 size_t total_nfastblocks = 0;
5052 size_t total_avail = 0;
5053 size_t total_fastavail = 0;
5054 size_t total_system = 0;
5055 size_t total_max_system = 0;
5056 size_t total_aspace = 0;
5057 size_t total_aspace_mprotect = 0;
5061 if (__malloc_initialized < 0)
5062 ptmalloc_init ();
5064 fputs ("<malloc version=\"1\">\n", fp);
5066 /* Iterate over all arenas currently in use. */
5067 mstate ar_ptr = &main_arena;
5068 do
5070 fprintf (fp, "<heap nr=\"%d\">\n<sizes>\n", n++);
5072 size_t nblocks = 0;
5073 size_t nfastblocks = 0;
5074 size_t avail = 0;
5075 size_t fastavail = 0;
5076 struct
5078 size_t from;
5079 size_t to;
5080 size_t total;
5081 size_t count;
5082 } sizes[NFASTBINS + NBINS - 1];
5083 #define nsizes (sizeof (sizes) / sizeof (sizes[0]))
5085 mutex_lock (&ar_ptr->mutex);
5087 for (size_t i = 0; i < NFASTBINS; ++i)
5089 mchunkptr p = fastbin (ar_ptr, i);
5090 if (p != NULL)
5092 size_t nthissize = 0;
5093 size_t thissize = chunksize (p);
5095 while (p != NULL)
5097 ++nthissize;
5098 p = p->fd;
5101 fastavail += nthissize * thissize;
5102 nfastblocks += nthissize;
5103 sizes[i].from = thissize - (MALLOC_ALIGNMENT - 1);
5104 sizes[i].to = thissize;
5105 sizes[i].count = nthissize;
5107 else
5108 sizes[i].from = sizes[i].to = sizes[i].count = 0;
5110 sizes[i].total = sizes[i].count * sizes[i].to;
5114 mbinptr bin;
5115 struct malloc_chunk *r;
5117 for (size_t i = 1; i < NBINS; ++i)
5119 bin = bin_at (ar_ptr, i);
5120 r = bin->fd;
5121 sizes[NFASTBINS - 1 + i].from = ~((size_t) 0);
5122 sizes[NFASTBINS - 1 + i].to = sizes[NFASTBINS - 1 + i].total
5123 = sizes[NFASTBINS - 1 + i].count = 0;
5125 if (r != NULL)
5126 while (r != bin)
5128 ++sizes[NFASTBINS - 1 + i].count;
5129 sizes[NFASTBINS - 1 + i].total += r->size;
5130 sizes[NFASTBINS - 1 + i].from
5131 = MIN (sizes[NFASTBINS - 1 + i].from, r->size);
5132 sizes[NFASTBINS - 1 + i].to = MAX (sizes[NFASTBINS - 1 + i].to,
5133 r->size);
5135 r = r->fd;
5138 if (sizes[NFASTBINS - 1 + i].count == 0)
5139 sizes[NFASTBINS - 1 + i].from = 0;
5140 nblocks += sizes[NFASTBINS - 1 + i].count;
5141 avail += sizes[NFASTBINS - 1 + i].total;
5144 mutex_unlock (&ar_ptr->mutex);
5146 total_nfastblocks += nfastblocks;
5147 total_fastavail += fastavail;
5149 total_nblocks += nblocks;
5150 total_avail += avail;
5152 for (size_t i = 0; i < nsizes; ++i)
5153 if (sizes[i].count != 0 && i != NFASTBINS)
5154 fprintf (fp, " \
5155 <size from=\"%zu\" to=\"%zu\" total=