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.
6
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.
11
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.
16
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/>. */
20
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.
24
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.
28
29* Version ptmalloc2-20011215
30 based on:
31 VERSION 2.7.0 Sun Mar 11 14:14:06 2001 Doug Lea (dl at gee)
32
33* Quickstart
34
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".
43
44* Why use this malloc?
45
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.
51
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.
61
62 For a longer but slightly out of date high-level description, see
63 http://gee.cs.oswego.edu/dl/html/malloc.html
64
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.
70
71* Contents, described in more detail in "description of public routines" below.
72
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)
82
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();
91
92* Vital statistics:
93
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
98
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.
103
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.
107
108 Minimum allocated size: 4-byte ptrs: 16 bytes (including 4 overhead)
109 8-byte ptrs: 24/32 bytes (including, 4/8 overhead)
110
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.
116
117 Even a request for zero bytes (i.e., malloc(0)) returns a
118 pointer to something of the minimum allocatable size.
119
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.
126
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
129
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.
142
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.)
146
147 Thread-safety: thread-safe
148
149 Compliance: I believe it is compliant with the 1997 Single Unix Specification
150 Also SVID/XPG, ANSI C, and probably others as well.
151
152* Synopsis of compile-time options:
153
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.
158
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.)
166
167 OPTION DEFAULT VALUE
168
169 Compilation Environment options:
170
171 HAVE_MREMAP 0
172
173 Changing default word sizes:
174
175 INTERNAL_SIZE_T size_t
176 MALLOC_ALIGNMENT MAX (2 * sizeof(INTERNAL_SIZE_T),
177 __alignof__ (long double))
178
179 Configuration and functionality options:
180
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
186
187 Options for customizing MORECORE:
188
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)
195
196 Tuning options that are also dynamically changeable via mallopt:
197
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
203
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. */
206
207/*
208 void* is the pointer type that malloc should say it returns
209*/
210
211#ifndef void
212#define void void
213#endif /*void*/
214
215#include <stddef.h> /* for size_t */
216#include <stdlib.h> /* for getenv(), abort() */
217#include <unistd.h> /* for __libc_enable_secure */
218
219#include <malloc-machine.h>
220#include <malloc-sysdep.h>
221
222#include <atomic.h>
223#include <_itoa.h>
224#include <bits/wordsize.h>
225#include <sys/sysinfo.h>
226
227#include <ldsodefs.h>
228
229#include <unistd.h>
230#include <stdio.h> /* needed for malloc_stats */
231#include <errno.h>
232
233#include <shlib-compat.h>
234
235/* For uintptr_t. */
236#include <stdint.h>
237
238/* For va_arg, va_start, va_end. */
239#include <stdarg.h>
240
241/* For MIN, MAX, powerof2. */
242#include <sys/param.h>
243
244/* For ALIGN_UP et. al. */
245#include <libc-internal.h>
246
247#include <malloc/malloc-internal.h>
248
249/*
250 Debugging:
251
252 Because freed chunks may be overwritten with bookkeeping fields, this
253 malloc will often die when freed memory is overwritten by user
254 programs. This can be very effective (albeit in an annoying way)
255 in helping track down dangling pointers.
256
257 If you compile with -DMALLOC_DEBUG, a number of assertion checks are
258 enabled that will catch more memory errors. You probably won't be
259 able to make much sense of the actual assertion errors, but they
260 should help you locate incorrectly overwritten memory. The checking
261 is fairly extensive, and will slow down execution
262 noticeably. Calling malloc_stats or mallinfo with MALLOC_DEBUG set
263 will attempt to check every non-mmapped allocated and free chunk in
264 the course of computing the summmaries. (By nature, mmapped regions
265 cannot be checked very much automatically.)
266
267 Setting MALLOC_DEBUG may also be helpful if you are trying to modify
268 this code. The assertions in the check routines spell out in more
269 detail the assumptions and invariants underlying the algorithms.
270
271 Setting MALLOC_DEBUG does NOT provide an automated mechanism for
272 checking that all accesses to malloced memory stay within their
273 bounds. However, there are several add-ons and adaptations of this
274 or other mallocs available that do this.
275*/
276
277#ifndef MALLOC_DEBUG
278#define MALLOC_DEBUG 0
279#endif
280
281#ifdef NDEBUG
282# define assert(expr) ((void) 0)
283#else
284# define assert(expr) \
285 ((expr) \
286 ? ((void) 0) \
287 : __malloc_assert (#expr, __FILE__, __LINE__, __func__))
288
289extern const char *__progname;
290
291static void
292__malloc_assert (const char *assertion, const char *file, unsigned int line,
293 const char *function)
294{
295 (void) __fxprintf (NULL, "%s%s%s:%u: %s%sAssertion `%s' failed.\n",
296 __progname, __progname[0] ? ": " : "",
297 file, line,
298 function ? function : "", function ? ": " : "",
299 assertion);
300 fflush (stderr);
301 abort ();
302}
303#endif
304
305
306/*
307 INTERNAL_SIZE_T is the word-size used for internal bookkeeping
308 of chunk sizes.
309
310 The default version is the same as size_t.
311
312 While not strictly necessary, it is best to define this as an
313 unsigned type, even if size_t is a signed type. This may avoid some
314 artificial size limitations on some systems.
315
316 On a 64-bit machine, you may be able to reduce malloc overhead by
317 defining INTERNAL_SIZE_T to be a 32 bit `unsigned int' at the
318 expense of not being able to handle more than 2^32 of malloced
319 space. If this limitation is acceptable, you are encouraged to set
320 this unless you are on a platform requiring 16byte alignments. In
321 this case the alignment requirements turn out to negate any
322 potential advantages of decreasing size_t word size.
323
324 Implementors: Beware of the possible combinations of:
325 - INTERNAL_SIZE_T might be signed or unsigned, might be 32 or 64 bits,
326 and might be the same width as int or as long
327 - size_t might have different width and signedness as INTERNAL_SIZE_T
328 - int and long might be 32 or 64 bits, and might be the same width
329 To deal with this, most comparisons and difference computations
330 among INTERNAL_SIZE_Ts should cast them to unsigned long, being
331 aware of the fact that casting an unsigned int to a wider long does
332 not sign-extend. (This also makes checking for negative numbers
333 awkward.) Some of these casts result in harmless compiler warnings
334 on some systems.
335*/
336
337#ifndef INTERNAL_SIZE_T
338#define INTERNAL_SIZE_T size_t
339#endif
340
341/* The corresponding word size */
342#define SIZE_SZ (sizeof(INTERNAL_SIZE_T))
343
344
345/*
346 MALLOC_ALIGNMENT is the minimum alignment for malloc'ed chunks.
347 It must be a power of two at least 2 * SIZE_SZ, even on machines
348 for which smaller alignments would suffice. It may be defined as
349 larger than this though. Note however that code and data structures
350 are optimized for the case of 8-byte alignment.
351*/
352
353
354#ifndef MALLOC_ALIGNMENT
355# if !SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_16)
356/* This is the correct definition when there is no past ABI to constrain it.
357
358 Among configurations with a past ABI constraint, it differs from
359 2*SIZE_SZ only on powerpc32. For the time being, changing this is
360 causing more compatibility problems due to malloc_get_state and
361 malloc_set_state than will returning blocks not adequately aligned for
362 long double objects under -mlong-double-128. */
363
364# define MALLOC_ALIGNMENT (2 *SIZE_SZ < __alignof__ (long double) \
365 ? __alignof__ (long double) : 2 *SIZE_SZ)
366# else
367# define MALLOC_ALIGNMENT (2 *SIZE_SZ)
368# endif
369#endif
370
371/* The corresponding bit mask value */
372#define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1)
373
374
375
376/*
377 REALLOC_ZERO_BYTES_FREES should be set if a call to
378 realloc with zero bytes should be the same as a call to free.
379 This is required by the C standard. Otherwise, since this malloc
380 returns a unique pointer for malloc(0), so does realloc(p, 0).
381*/
382
383#ifndef REALLOC_ZERO_BYTES_FREES
384#define REALLOC_ZERO_BYTES_FREES 1
385#endif
386
387/*
388 TRIM_FASTBINS controls whether free() of a very small chunk can
389 immediately lead to trimming. Setting to true (1) can reduce memory
390 footprint, but will almost always slow down programs that use a lot
391 of small chunks.
392
393 Define this only if you are willing to give up some speed to more
394 aggressively reduce system-level memory footprint when releasing
395 memory in programs that use many small chunks. You can get
396 essentially the same effect by setting MXFAST to 0, but this can
397 lead to even greater slowdowns in programs using many small chunks.
398 TRIM_FASTBINS is an in-between compile-time option, that disables
399 only those chunks bordering topmost memory from being placed in
400 fastbins.
401*/
402
403#ifndef TRIM_FASTBINS
404#define TRIM_FASTBINS 0
405#endif
406
407
408/* Definition for getting more memory from the OS. */
409#define MORECORE (*__morecore)
410#define MORECORE_FAILURE 0
411void * __default_morecore (ptrdiff_t);
412void *(*__morecore)(ptrdiff_t) = __default_morecore;
413
414
415#include <string.h>
416
417/*
418 MORECORE-related declarations. By default, rely on sbrk
419*/
420
421
422/*
423 MORECORE is the name of the routine to call to obtain more memory
424 from the system. See below for general guidance on writing
425 alternative MORECORE functions, as well as a version for WIN32 and a
426 sample version for pre-OSX macos.
427*/
428
429#ifndef MORECORE
430#define MORECORE sbrk
431#endif
432
433/*
434 MORECORE_FAILURE is the value returned upon failure of MORECORE
435 as well as mmap. Since it cannot be an otherwise valid memory address,
436 and must reflect values of standard sys calls, you probably ought not
437 try to redefine it.
438*/
439
440#ifndef MORECORE_FAILURE
441#define MORECORE_FAILURE (-1)
442#endif
443
444/*
445 If MORECORE_CONTIGUOUS is true, take advantage of fact that
446 consecutive calls to MORECORE with positive arguments always return
447 contiguous increasing addresses. This is true of unix sbrk. Even
448 if not defined, when regions happen to be contiguous, malloc will
449 permit allocations spanning regions obtained from different
450 calls. But defining this when applicable enables some stronger
451 consistency checks and space efficiencies.
452*/
453
454#ifndef MORECORE_CONTIGUOUS
455#define MORECORE_CONTIGUOUS 1
456#endif
457
458/*
459 Define MORECORE_CANNOT_TRIM if your version of MORECORE
460 cannot release space back to the system when given negative
461 arguments. This is generally necessary only if you are using
462 a hand-crafted MORECORE function that cannot handle negative arguments.
463*/
464
465/* #define MORECORE_CANNOT_TRIM */
466
467/* MORECORE_CLEARS (default 1)
468 The degree to which the routine mapped to MORECORE zeroes out
469 memory: never (0), only for newly allocated space (1) or always
470 (2). The distinction between (1) and (2) is necessary because on
471 some systems, if the application first decrements and then
472 increments the break value, the contents of the reallocated space
473 are unspecified.
474 */
475
476#ifndef MORECORE_CLEARS
477# define MORECORE_CLEARS 1
478#endif
479
480
481/*
482 MMAP_AS_MORECORE_SIZE is the minimum mmap size argument to use if
483 sbrk fails, and mmap is used as a backup. The value must be a
484 multiple of page size. This backup strategy generally applies only
485 when systems have "holes" in address space, so sbrk cannot perform
486 contiguous expansion, but there is still space available on system.
487 On systems for which this is known to be useful (i.e. most linux
488 kernels), this occurs only when programs allocate huge amounts of
489 memory. Between this, and the fact that mmap regions tend to be
490 limited, the size should be large, to avoid too many mmap calls and
491 thus avoid running out of kernel resources. */
492
493#ifndef MMAP_AS_MORECORE_SIZE
494#define MMAP_AS_MORECORE_SIZE (1024 * 1024)
495#endif
496
497/*
498 Define HAVE_MREMAP to make realloc() use mremap() to re-allocate
499 large blocks.
500*/
501
502#ifndef HAVE_MREMAP
503#define HAVE_MREMAP 0
504#endif
505
506
507/*
508 This version of malloc supports the standard SVID/XPG mallinfo
509 routine that returns a struct containing usage properties and
510 statistics. It should work on any SVID/XPG compliant system that has
511 a /usr/include/malloc.h defining struct mallinfo. (If you'd like to
512 install such a thing yourself, cut out the preliminary declarations
513 as described above and below and save them in a malloc.h file. But
514 there's no compelling reason to bother to do this.)
515
516 The main declaration needed is the mallinfo struct that is returned
517 (by-copy) by mallinfo(). The SVID/XPG malloinfo struct contains a
518 bunch of fields that are not even meaningful in this version of
519 malloc. These fields are are instead filled by mallinfo() with
520 other numbers that might be of interest.
521*/
522
523
524/* ---------- description of public routines ------------ */
525
526/*
527 malloc(size_t n)
528 Returns a pointer to a newly allocated chunk of at least n bytes, or null
529 if no space is available. Additionally, on failure, errno is
530 set to ENOMEM on ANSI C systems.
531
532 If n is zero, malloc returns a minumum-sized chunk. (The minimum
533 size is 16 bytes on most 32bit systems, and 24 or 32 bytes on 64bit
534 systems.) On most systems, size_t is an unsigned type, so calls
535 with negative arguments are interpreted as requests for huge amounts
536 of space, which will often fail. The maximum supported value of n
537 differs across systems, but is in all cases less than the maximum
538 representable value of a size_t.
539*/
540void* __libc_malloc(size_t);
541libc_hidden_proto (__libc_malloc)
542
543/*
544 free(void* p)
545 Releases the chunk of memory pointed to by p, that had been previously
546 allocated using malloc or a related routine such as realloc.
547 It has no effect if p is null. It can have arbitrary (i.e., bad!)
548 effects if p has already been freed.
549
550 Unless disabled (using mallopt), freeing very large spaces will
551 when possible, automatically trigger operations that give
552 back unused memory to the system, thus reducing program footprint.
553*/
554void __libc_free(void*);
555libc_hidden_proto (__libc_free)
556
557/*
558 calloc(size_t n_elements, size_t element_size);
559 Returns a pointer to n_elements * element_size bytes, with all locations
560 set to zero.
561*/
562void* __libc_calloc(size_t, size_t);
563
564/*
565 realloc(void* p, size_t n)
566 Returns a pointer to a chunk of size n that contains the same data
567 as does chunk p up to the minimum of (n, p's size) bytes, or null
568 if no space is available.
569
570 The returned pointer may or may not be the same as p. The algorithm
571 prefers extending p when possible, otherwise it employs the
572 equivalent of a malloc-copy-free sequence.
573
574 If p is null, realloc is equivalent to malloc.
575
576 If space is not available, realloc returns null, errno is set (if on
577 ANSI) and p is NOT freed.
578
579 if n is for fewer bytes than already held by p, the newly unused
580 space is lopped off and freed if possible. Unless the #define
581 REALLOC_ZERO_BYTES_FREES is set, realloc with a size argument of
582 zero (re)allocates a minimum-sized chunk.
583
584 Large chunks that were internally obtained via mmap will always
585 be reallocated using malloc-copy-free sequences unless
586 the system supports MREMAP (currently only linux).
587
588 The old unix realloc convention of allowing the last-free'd chunk
589 to be used as an argument to realloc is not supported.
590*/
591void* __libc_realloc(void*, size_t);
592libc_hidden_proto (__libc_realloc)
593
594/*
595 memalign(size_t alignment, size_t n);
596 Returns a pointer to a newly allocated chunk of n bytes, aligned
597 in accord with the alignment argument.
598
599 The alignment argument should be a power of two. If the argument is
600 not a power of two, the nearest greater power is used.
601 8-byte alignment is guaranteed by normal malloc calls, so don't
602 bother calling memalign with an argument of 8 or less.
603
604 Overreliance on memalign is a sure way to fragment space.
605*/
606void* __libc_memalign(size_t, size_t);
607libc_hidden_proto (__libc_memalign)
608
609/*
610 valloc(size_t n);
611 Equivalent to memalign(pagesize, n), where pagesize is the page
612 size of the system. If the pagesize is unknown, 4096 is used.
613*/
614void* __libc_valloc(size_t);
615
616
617
618/*
619 mallopt(int parameter_number, int parameter_value)
620 Sets tunable parameters The format is to provide a
621 (parameter-number, parameter-value) pair. mallopt then sets the
622 corresponding parameter to the argument value if it can (i.e., so
623 long as the value is meaningful), and returns 1 if successful else
624 0. SVID/XPG/ANSI defines four standard param numbers for mallopt,
625 normally defined in malloc.h. Only one of these (M_MXFAST) is used
626 in this malloc. The others (M_NLBLKS, M_GRAIN, M_KEEP) don't apply,
627 so setting them has no effect. But this malloc also supports four
628 other options in mallopt. See below for details. Briefly, supported
629 parameters are as follows (listed defaults are for "typical"
630 configurations).
631
632 Symbol param # default allowed param values
633 M_MXFAST 1 64 0-80 (0 disables fastbins)
634 M_TRIM_THRESHOLD -1 128*1024 any (-1U disables trimming)
635 M_TOP_PAD -2 0 any
636 M_MMAP_THRESHOLD -3 128*1024 any (or 0 if no MMAP support)
637 M_MMAP_MAX -4 65536 any (0 disables use of mmap)
638*/
639int __libc_mallopt(int, int);
640libc_hidden_proto (__libc_mallopt)
641
642
643/*
644 mallinfo()
645 Returns (by copy) a struct containing various summary statistics:
646
647 arena: current total non-mmapped bytes allocated from system
648 ordblks: the number of free chunks
649 smblks: the number of fastbin blocks (i.e., small chunks that
650 have been freed but not use resused or consolidated)
651 hblks: current number of mmapped regions
652 hblkhd: total bytes held in mmapped regions
653 usmblks: the maximum total allocated space. This will be greater
654 than current total if trimming has occurred.
655 fsmblks: total bytes held in fastbin blocks
656 uordblks: current total allocated space (normal or mmapped)
657 fordblks: total free space
658 keepcost: the maximum number of bytes that could ideally be released
659 back to system via malloc_trim. ("ideally" means that
660 it ignores page restrictions etc.)
661
662 Because these fields are ints, but internal bookkeeping may
663 be kept as longs, the reported values may wrap around zero and
664 thus be inaccurate.
665*/
666struct mallinfo __libc_mallinfo(void);
667
668
669/*
670 pvalloc(size_t n);
671 Equivalent to valloc(minimum-page-that-holds(n)), that is,
672 round up n to nearest pagesize.
673 */
674void* __libc_pvalloc(size_t);
675
676/*
677 malloc_trim(size_t pad);
678
679 If possible, gives memory back to the system (via negative
680 arguments to sbrk) if there is unused memory at the `high' end of
681 the malloc pool. You can call this after freeing large blocks of
682 memory to potentially reduce the system-level memory requirements
683 of a program. However, it cannot guarantee to reduce memory. Under
684 some allocation patterns, some large free blocks of memory will be
685 locked between two used chunks, so they cannot be given back to
686 the system.
687
688 The `pad' argument to malloc_trim represents the amount of free
689 trailing space to leave untrimmed. If this argument is zero,
690 only the minimum amount of memory to maintain internal data
691 structures will be left (one page or less). Non-zero arguments
692 can be supplied to maintain enough trailing space to service
693 future expected allocations without having to re-obtain memory
694 from the system.
695
696 Malloc_trim returns 1 if it actually released any memory, else 0.
697 On systems that do not support "negative sbrks", it will always
698 return 0.
699*/
700int __malloc_trim(size_t);
701
702/*
703 malloc_usable_size(void* p);
704
705 Returns the number of bytes you can actually use in
706 an allocated chunk, which may be more than you requested (although
707 often not) due to alignment and minimum size constraints.
708 You can use this many bytes without worrying about
709 overwriting other allocated objects. This is not a particularly great
710 programming practice. malloc_usable_size can be more useful in
711 debugging and assertions, for example:
712
713 p = malloc(n);
714 assert(malloc_usable_size(p) >= 256);
715
716*/
717size_t __malloc_usable_size(void*);
718
719/*
720 malloc_stats();
721 Prints on stderr the amount of space obtained from the system (both
722 via sbrk and mmap), the maximum amount (which may be more than
723 current if malloc_trim and/or munmap got called), and the current
724 number of bytes allocated via malloc (or realloc, etc) but not yet
725 freed. Note that this is the number of bytes allocated, not the
726 number requested. It will be larger than the number requested
727 because of alignment and bookkeeping overhead. Because it includes
728 alignment wastage as being in use, this figure may be greater than
729 zero even when no user-level chunks are allocated.
730
731 The reported current and maximum system memory can be inaccurate if
732 a program makes other calls to system memory allocation functions
733 (normally sbrk) outside of malloc.
734
735 malloc_stats prints only the most commonly interesting statistics.
736 More information can be obtained by calling mallinfo.
737
738*/
739void __malloc_stats(void);
740
741/*
742 malloc_get_state(void);
743
744 Returns the state of all malloc variables in an opaque data
745 structure.
746*/
747void* __malloc_get_state(void);
748
749/*
750 malloc_set_state(void* state);
751
752 Restore the state of all malloc variables from data obtained with
753 malloc_get_state().
754*/
755int __malloc_set_state(void*);
756
757/*
758 posix_memalign(void **memptr, size_t alignment, size_t size);
759
760 POSIX wrapper like memalign(), checking for validity of size.
761*/
762int __posix_memalign(void **, size_t, size_t);
763
764/* mallopt tuning options */
765
766/*
767 M_MXFAST is the maximum request size used for "fastbins", special bins
768 that hold returned chunks without consolidating their spaces. This
769 enables future requests for chunks of the same size to be handled
770 very quickly, but can increase fragmentation, and thus increase the
771 overall memory footprint of a program.
772
773 This malloc manages fastbins very conservatively yet still
774 efficiently, so fragmentation is rarely a problem for values less
775 than or equal to the default. The maximum supported value of MXFAST
776 is 80. You wouldn't want it any higher than this anyway. Fastbins
777 are designed especially for use with many small structs, objects or
778 strings -- the default handles structs/objects/arrays with sizes up
779 to 8 4byte fields, or small strings representing words, tokens,
780 etc. Using fastbins for larger objects normally worsens
781 fragmentation without improving speed.
782
783 M_MXFAST is set in REQUEST size units. It is internally used in
784 chunksize units, which adds padding and alignment. You can reduce
785 M_MXFAST to 0 to disable all use of fastbins. This causes the malloc
786 algorithm to be a closer approximation of fifo-best-fit in all cases,
787 not just for larger requests, but will generally cause it to be
788 slower.
789*/
790
791
792/* M_MXFAST is a standard SVID/XPG tuning option, usually listed in malloc.h */
793#ifndef M_MXFAST
794#define M_MXFAST 1
795#endif
796
797#ifndef DEFAULT_MXFAST
798#define DEFAULT_MXFAST (64 * SIZE_SZ / 4)
799#endif
800
801
802/*
803 M_TRIM_THRESHOLD is the maximum amount of unused top-most memory
804 to keep before releasing via malloc_trim in free().
805
806 Automatic trimming is mainly useful in long-lived programs.
807 Because trimming via sbrk can be slow on some systems, and can
808 sometimes be wasteful (in cases where programs immediately
809 afterward allocate more large chunks) the value should be high
810 enough so that your overall system performance would improve by
811 releasing this much memory.
812
813 The trim threshold and the mmap control parameters (see below)
814 can be traded off with one another. Trimming and mmapping are
815 two different ways of releasing unused memory back to the
816 system. Between these two, it is often possible to keep
817 system-level demands of a long-lived program down to a bare
818 minimum. For example, in one test suite of sessions measuring
819 the XF86 X server on Linux, using a trim threshold of 128K and a
820 mmap threshold of 192K led to near-minimal long term resource
821 consumption.
822
823 If you are using this malloc in a long-lived program, it should
824 pay to experiment with these values. As a rough guide, you
825 might set to a value close to the average size of a process
826 (program) running on your system. Releasing this much memory
827 would allow such a process to run in memory. Generally, it's
828 worth it to tune for trimming rather tham memory mapping when a
829 program undergoes phases where several large chunks are
830 allocated and released in ways that can reuse each other's
831 storage, perhaps mixed with phases where there are no such
832 chunks at all. And in well-behaved long-lived programs,
833 controlling release of large blocks via trimming versus mapping
834 is usually faster.
835
836 However, in most programs, these parameters serve mainly as
837 protection against the system-level effects of carrying around
838 massive amounts of unneeded memory. Since frequent calls to
839 sbrk, mmap, and munmap otherwise degrade performance, the default
840 parameters are set to relatively high values that serve only as
841 safeguards.
842
843 The trim value It must be greater than page size to have any useful
844 effect. To disable trimming completely, you can set to
845 (unsigned long)(-1)
846
847 Trim settings interact with fastbin (MXFAST) settings: Unless
848 TRIM_FASTBINS is defined, automatic trimming never takes place upon
849 freeing a chunk with size less than or equal to MXFAST. Trimming is
850 instead delayed until subsequent freeing of larger chunks. However,
851 you can still force an attempted trim by calling malloc_trim.
852
853 Also, trimming is not generally possible in cases where
854 the main arena is obtained via mmap.
855
856 Note that the trick some people use of mallocing a huge space and
857 then freeing it at program startup, in an attempt to reserve system
858 memory, doesn't have the intended effect under automatic trimming,
859 since that memory will immediately be returned to the system.
860*/
861
862#define M_TRIM_THRESHOLD -1
863
864#ifndef DEFAULT_TRIM_THRESHOLD
865#define DEFAULT_TRIM_THRESHOLD (128 * 1024)
866#endif
867
868/*
869 M_TOP_PAD is the amount of extra `padding' space to allocate or
870 retain whenever sbrk is called. It is used in two ways internally:
871
872 * When sbrk is called to extend the top of the arena to satisfy
873 a new malloc request, this much padding is added to the sbrk
874 request.
875
876 * When malloc_trim is called automatically from free(),
877 it is used as the `pad' argument.
878
879 In both cases, the actual amount of padding is rounded
880 so that the end of the arena is always a system page boundary.
881
882 The main reason for using padding is to avoid calling sbrk so
883 often. Having even a small pad greatly reduces the likelihood
884 that nearly every malloc request during program start-up (or
885 after trimming) will invoke sbrk, which needlessly wastes
886 time.
887
888 Automatic rounding-up to page-size units is normally sufficient
889 to avoid measurable overhead, so the default is 0. However, in
890 systems where sbrk is relatively slow, it can pay to increase
891 this value, at the expense of carrying around more memory than
892 the program needs.
893*/
894
895#define M_TOP_PAD -2
896
897#ifndef DEFAULT_TOP_PAD
898#define DEFAULT_TOP_PAD (0)
899#endif
900
901/*
902 MMAP_THRESHOLD_MAX and _MIN are the bounds on the dynamically
903 adjusted MMAP_THRESHOLD.
904*/
905
906#ifndef DEFAULT_MMAP_THRESHOLD_MIN
907#define DEFAULT_MMAP_THRESHOLD_MIN (128 * 1024)
908#endif
909
910#ifndef DEFAULT_MMAP_THRESHOLD_MAX
911 /* For 32-bit platforms we cannot increase the maximum mmap
912 threshold much because it is also the minimum value for the
913 maximum heap size and its alignment. Going above 512k (i.e., 1M
914 for new heaps) wastes too much address space. */
915# if __WORDSIZE == 32
916# define DEFAULT_MMAP_THRESHOLD_MAX (512 * 1024)
917# else
918# define DEFAULT_MMAP_THRESHOLD_MAX (4 * 1024 * 1024 * sizeof(long))
919# endif
920#endif
921
922/*
923 M_MMAP_THRESHOLD is the request size threshold for using mmap()
924 to service a request. Requests of at least this size that cannot
925 be allocated using already-existing space will be serviced via mmap.
926 (If enough normal freed space already exists it is used instead.)
927
928 Using mmap segregates relatively large chunks of memory so that
929 they can be individually obtained and released from the host
930 system. A request serviced through mmap is never reused by any
931 other request (at least not directly; the system may just so
932 happen to remap successive requests to the same locations).
933
934 Segregating space in this way has the benefits that:
935
936 1. Mmapped space can ALWAYS be individually released back
937 to the system, which helps keep the system level memory
938 demands of a long-lived program low.
939 2. Mapped memory can never become `locked' between
940 other chunks, as can happen with normally allocated chunks, which
941 means that even trimming via malloc_trim would not release them.
942 3. On some systems with "holes" in address spaces, mmap can obtain
943 memory that sbrk cannot.
944
945 However, it has the disadvantages that:
946
947 1. The space cannot be reclaimed, consolidated, and then
948 used to service later requests, as happens with normal chunks.
949 2. It can lead to more wastage because of mmap page alignment
950 requirements
951 3. It causes malloc performance to be more dependent on host
952 system memory management support routines which may vary in
953 implementation quality and may impose arbitrary
954 limitations. Generally, servicing a request via normal
955 malloc steps is faster than going through a system's mmap.
956
957 The advantages of mmap nearly always outweigh disadvantages for
958 "large" chunks, but the value of "large" varies across systems. The
959 default is an empirically derived value that works well in most
960 systems.
961
962
963 Update in 2006:
964 The above was written in 2001. Since then the world has changed a lot.
965 Memory got bigger. Applications got bigger. The virtual address space
966 layout in 32 bit linux changed.
967
968 In the new situation, brk() and mmap space is shared and there are no
969 artificial limits on brk size imposed by the kernel. What is more,
970 applications have started using transient allocations larger than the
971 128Kb as was imagined in 2001.
972
973 The price for mmap is also high now; each time glibc mmaps from the
974 kernel, the kernel is forced to zero out the memory it gives to the
975 application. Zeroing memory is expensive and eats a lot of cache and
976 memory bandwidth. This has nothing to do with the efficiency of the
977 virtual memory system, by doing mmap the kernel just has no choice but
978 to zero.
979
980 In 2001, the kernel had a maximum size for brk() which was about 800
981 megabytes on 32 bit x86, at that point brk() would hit the first
982 mmaped shared libaries and couldn't expand anymore. With current 2.6
983 kernels, the VA space layout is different and brk() and mmap
984 both can span the entire heap at will.
985
986 Rather than using a static threshold for the brk/mmap tradeoff,
987 we are now using a simple dynamic one. The goal is still to avoid
988 fragmentation. The old goals we kept are
989 1) try to get the long lived large allocations to use mmap()
990 2) really large allocations should always use mmap()
991 and we're adding now:
992 3) transient allocations should use brk() to avoid forcing the kernel
993 having to zero memory over and over again
994
995 The implementation works with a sliding threshold, which is by default
996 limited to go between 128Kb and 32Mb (64Mb for 64 bitmachines) and starts
997 out at 128Kb as per the 2001 default.
998
999 This allows us to satisfy requirement 1) under the assumption that long
1000 lived allocations are made early in the process' lifespan, before it has
1001 started doing dynamic allocations of the same size (which will
1002 increase the threshold).
1003
1004 The upperbound on the threshold satisfies requirement 2)
1005
1006 The threshold goes up in value when the application frees memory that was
1007 allocated with the mmap allocator. The idea is that once the application
1008 starts freeing memory of a certain size, it's highly probable that this is
1009 a size the application uses for transient allocations. This estimator
1010 is there to satisfy the new third requirement.
1011
1012*/
1013
1014#define M_MMAP_THRESHOLD -3
1015
1016#ifndef DEFAULT_MMAP_THRESHOLD
1017#define DEFAULT_MMAP_THRESHOLD DEFAULT_MMAP_THRESHOLD_MIN
1018#endif
1019
1020/*
1021 M_MMAP_MAX is the maximum number of requests to simultaneously
1022 service using mmap. This parameter exists because
1023 some systems have a limited number of internal tables for
1024 use by mmap, and using more than a few of them may degrade
1025 performance.
1026
1027 The default is set to a value that serves only as a safeguard.
1028 Setting to 0 disables use of mmap for servicing large requests.
1029*/
1030
1031#define M_MMAP_MAX -4
1032
1033#ifndef DEFAULT_MMAP_MAX
1034#define DEFAULT_MMAP_MAX (65536)
1035#endif
1036
1037#include <malloc.h>
1038
1039#ifndef RETURN_ADDRESS
1040#define RETURN_ADDRESS(X_) (NULL)
1041#endif
1042
1043/* On some platforms we can compile internal, not exported functions better.
1044 Let the environment provide a macro and define it to be empty if it
1045 is not available. */
1046#ifndef internal_function
1047# define internal_function
1048#endif
1049
1050/* Forward declarations. */
1051struct malloc_chunk;
1052typedef struct malloc_chunk* mchunkptr;
1053
1054/* Internal routines. */
1055
1056static void* _int_malloc(mstate, size_t);
1057static void _int_free(mstate, mchunkptr, int);
1058static void* _int_realloc(mstate, mchunkptr, INTERNAL_SIZE_T,
1059 INTERNAL_SIZE_T);
1060static void* _int_memalign(mstate, size_t, size_t);
1061static void* _mid_memalign(size_t, size_t, void *);
1062
1063static void malloc_printerr(int action, const char *str, void *ptr, mstate av);
1064
1065static void* internal_function mem2mem_check(void *p, size_t sz);
1066static int internal_function top_check(void);
1067static void internal_function munmap_chunk(mchunkptr p);
1068#if HAVE_MREMAP
1069static mchunkptr internal_function mremap_chunk(mchunkptr p, size_t new_size);
1070#endif
1071
1072static void* malloc_check(size_t sz, const void *caller);
1073static void free_check(void* mem, const void *caller);
1074static void* realloc_check(void* oldmem, size_t bytes,
1075 const void *caller);
1076static void* memalign_check(size_t alignment, size_t bytes,
1077 const void *caller);
1078
1079/* ------------------ MMAP support ------------------ */
1080
1081
1082#include <fcntl.h>
1083#include <sys/mman.h>
1084
1085#if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
1086# define MAP_ANONYMOUS MAP_ANON
1087#endif
1088
1089#ifndef MAP_NORESERVE
1090# define MAP_NORESERVE 0
1091#endif
1092
1093#define MMAP(addr, size, prot, flags) \
1094 __mmap((addr), (size), (prot), (flags)|MAP_ANONYMOUS|MAP_PRIVATE, -1, 0)
1095
1096
1097/*
1098 ----------------------- Chunk representations -----------------------
1099*/
1100
1101
1102/*
1103 This struct declaration is misleading (but accurate and necessary).
1104 It declares a "view" into memory allowing access to necessary
1105 fields at known offsets from a given base. See explanation below.
1106*/
1107
1108struct malloc_chunk {
1109
1110 INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
1111 INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
1112
1113 struct malloc_chunk* fd; /* double links -- used only if free. */
1114 struct malloc_chunk* bk;
1115
1116 /* Only used for large blocks: pointer to next larger size. */
1117 struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
1118 struct malloc_chunk* bk_nextsize;
1119};
1120
1121
1122/*
1123 malloc_chunk details:
1124
1125 (The following includes lightly edited explanations by Colin Plumb.)
1126
1127 Chunks of memory are maintained using a `boundary tag' method as
1128 described in e.g., Knuth or Standish. (See the paper by Paul
1129 Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a
1130 survey of such techniques.) Sizes of free chunks are stored both
1131 in the front of each chunk and at the end. This makes
1132 consolidating fragmented chunks into bigger chunks very fast. The
1133 size fields also hold bits representing whether chunks are free or
1134 in use.
1135
1136 An allocated chunk looks like this:
1137
1138
1139 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1140 | Size of previous chunk, if allocated | |
1141 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1142 | Size of chunk, in bytes |M|P|
1143 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1144 | User data starts here... .
1145 . .
1146 . (malloc_usable_size() bytes) .
1147 . |
1148nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1149 | Size of chunk |
1150 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1151
1152
1153 Where "chunk" is the front of the chunk for the purpose of most of
1154 the malloc code, but "mem" is the pointer that is returned to the
1155 user. "Nextchunk" is the beginning of the next contiguous chunk.
1156
1157 Chunks always begin on even word boundaries, so the mem portion
1158 (which is returned to the user) is also on an even word boundary, and
1159 thus at least double-word aligned.
1160
1161 Free chunks are stored in circular doubly-linked lists, and look like this:
1162
1163 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1164 | Size of previous chunk |
1165 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1166 `head:' | Size of chunk, in bytes |P|
1167 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1168 | Forward pointer to next chunk in list |
1169 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1170 | Back pointer to previous chunk in list |
1171 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1172 | Unused space (may be 0 bytes long) .
1173 . .
1174 . |
1175nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1176 `foot:' | Size of chunk, in bytes |
1177 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1178
1179 The P (PREV_INUSE) bit, stored in the unused low-order bit of the
1180 chunk size (which is always a multiple of two words), is an in-use
1181 bit for the *previous* chunk. If that bit is *clear*, then the
1182 word before the current chunk size contains the previous chunk
1183 size, and can be used to find the front of the previous chunk.
1184 The very first chunk allocated always has this bit set,
1185 preventing access to non-existent (or non-owned) memory. If
1186 prev_inuse is set for any given chunk, then you CANNOT determine
1187 the size of the previous chunk, and might even get a memory
1188 addressing fault when trying to do so.
1189
1190 Note that the `foot' of the current chunk is actually represented
1191 as the prev_size of the NEXT chunk. This makes it easier to
1192 deal with alignments etc but can be very confusing when trying
1193 to extend or adapt this code.
1194
1195 The two exceptions to all this are
1196
1197 1. The special chunk `top' doesn't bother using the
1198 trailing size field since there is no next contiguous chunk
1199 that would have to index off it. After initialization, `top'
1200 is forced to always exist. If it would become less than
1201 MINSIZE bytes long, it is replenished.
1202
1203 2. Chunks allocated via mmap, which have the second-lowest-order
1204 bit M (IS_MMAPPED) set in their size fields. Because they are
1205 allocated one-by-one, each must contain its own trailing size field.
1206
1207*/
1208
1209/*
1210 ---------- Size and alignment checks and conversions ----------
1211*/
1212
1213/* conversion from malloc headers to user pointers, and back */
1214
1215#define chunk2mem(p) ((void*)((char*)(p) + 2*SIZE_SZ))
1216#define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))
1217
1218/* The smallest possible chunk */
1219#define MIN_CHUNK_SIZE (offsetof(struct malloc_chunk, fd_nextsize))
1220
1221/* The smallest size we can malloc is an aligned minimal chunk */
1222
1223#define MINSIZE \
1224 (unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))
1225
1226/* Check if m has acceptable alignment */
1227
1228#define aligned_OK(m) (((unsigned long)(m) & MALLOC_ALIGN_MASK) == 0)
1229
1230#define misaligned_chunk(p) \
1231 ((uintptr_t)(MALLOC_ALIGNMENT == 2 * SIZE_SZ ? (p) : chunk2mem (p)) \
1232 & MALLOC_ALIGN_MASK)
1233
1234
1235/*
1236 Check if a request is so large that it would wrap around zero when
1237 padded and aligned. To simplify some other code, the bound is made
1238 low enough so that adding MINSIZE will also not wrap around zero.
1239 */
1240
1241#define REQUEST_OUT_OF_RANGE(req) \
1242 ((unsigned long) (req) >= \
1243 (unsigned long) (INTERNAL_SIZE_T) (-2 * MINSIZE))
1244
1245/* pad request bytes into a usable size -- internal version */
1246
1247#define request2size(req) \
1248 (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ? \
1249 MINSIZE : \
1250 ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
1251
1252/* Same, except also perform argument check */
1253
1254#define checked_request2size(req, sz) \
1255 if (REQUEST_OUT_OF_RANGE (req)) { \
1256 __set_errno (ENOMEM); \
1257 return 0; \
1258 } \
1259 (sz) = request2size (req);
1260
1261/*
1262 --------------- Physical chunk operations ---------------
1263 */
1264
1265
1266/* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
1267#define PREV_INUSE 0x1
1268
1269/* extract inuse bit of previous chunk */
1270#define prev_inuse(p) ((p)->size & PREV_INUSE)
1271
1272
1273/* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */
1274#define IS_MMAPPED 0x2
1275
1276/* check for mmap()'ed chunk */
1277#define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)
1278
1279
1280/* size field is or'ed with NON_MAIN_ARENA if the chunk was obtained
1281 from a non-main arena. This is only set immediately before handing
1282 the chunk to the user, if necessary. */
1283#define NON_MAIN_ARENA 0x4
1284
1285/* check for chunk from non-main arena */
1286#define chunk_non_main_arena(p) ((p)->size & NON_MAIN_ARENA)
1287
1288
1289/*
1290 Bits to mask off when extracting size
1291
1292 Note: IS_MMAPPED is intentionally not masked off from size field in
1293 macros for which mmapped chunks should never be seen. This should
1294 cause helpful core dumps to occur if it is tried by accident by
1295 people extending or adapting this malloc.
1296 */
1297#define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
1298
1299/* Get size, ignoring use bits */
1300#define chunksize(p) ((p)->size & ~(SIZE_BITS))
1301
1302
1303/* Ptr to next physical malloc_chunk. */
1304#define next_chunk(p) ((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))
1305
1306/* Ptr to previous physical malloc_chunk */
1307#define prev_chunk(p) ((mchunkptr) (((char *) (p)) - ((p)->prev_size)))
1308
1309/* Treat space at ptr + offset as a chunk */
1310#define chunk_at_offset(p, s) ((mchunkptr) (((char *) (p)) + (s)))
1311
1312/* extract p's inuse bit */
1313#define inuse(p) \
1314 ((((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))->size) & PREV_INUSE)
1315
1316/* set/clear chunk as being inuse without otherwise disturbing */
1317#define set_inuse(p) \
1318 ((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))->size |= PREV_INUSE
1319
1320#define clear_inuse(p) \
1321 ((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))->size &= ~(PREV_INUSE)
1322
1323
1324/* check/set/clear inuse bits in known places */
1325#define inuse_bit_at_offset(p, s) \
1326 (((mchunkptr) (((char *) (p)) + (s)))->size & PREV_INUSE)
1327
1328#define set_inuse_bit_at_offset(p, s) \
1329 (((mchunkptr) (((char *) (p)) + (s)))->size |= PREV_INUSE)
1330
1331#define clear_inuse_bit_at_offset(p, s) \
1332 (((mchunkptr) (((char *) (p)) + (s)))->size &= ~(PREV_INUSE))
1333
1334
1335/* Set size at head, without disturbing its use bit */
1336#define set_head_size(p, s) ((p)->size = (((p)->size & SIZE_BITS) | (s)))
1337
1338/* Set size/use field */
1339#define set_head(p, s) ((p)->size = (s))
1340
1341/* Set size at footer (only when chunk is not in use) */
1342#define set_foot(p, s) (((mchunkptr) ((char *) (p) + (s)))->prev_size = (s))
1343
1344
1345/*
1346 -------------------- Internal data structures --------------------
1347
1348 All internal state is held in an instance of malloc_state defined
1349 below. There are no other static variables, except in two optional
1350 cases:
1351 * If USE_MALLOC_LOCK is defined, the mALLOC_MUTEx declared above.
1352 * If mmap doesn't support MAP_ANONYMOUS, a dummy file descriptor
1353 for mmap.
1354
1355 Beware of lots of tricks that minimize the total bookkeeping space
1356 requirements. The result is a little over 1K bytes (for 4byte
1357 pointers and size_t.)
1358 */
1359
1360/*
1361 Bins
1362
1363 An array of bin headers for free chunks. Each bin is doubly
1364 linked. The bins are approximately proportionally (log) spaced.
1365 There are a lot of these bins (128). This may look excessive, but
1366 works very well in practice. Most bins hold sizes that are
1367 unusual as malloc request sizes, but are more usual for fragments
1368 and consolidated sets of chunks, which is what these bins hold, so
1369 they can be found quickly. All procedures maintain the invariant
1370 that no consolidated chunk physically borders another one, so each
1371 chunk in a list is known to be preceeded and followed by either
1372 inuse chunks or the ends of memory.
1373
1374 Chunks in bins are kept in size order, with ties going to the
1375 approximately least recently used chunk. Ordering isn't needed
1376 for the small bins, which all contain the same-sized chunks, but
1377 facilitates best-fit allocation for larger chunks. These lists
1378 are just sequential. Keeping them in order almost never requires
1379 enough traversal to warrant using fancier ordered data
1380 structures.
1381
1382 Chunks of the same size are linked with the most
1383 recently freed at the front, and allocations are taken from the
1384 back. This results in LRU (FIFO) allocation order, which tends
1385 to give each chunk an equal opportunity to be consolidated with
1386 adjacent freed chunks, resulting in larger free chunks and less
1387 fragmentation.
1388
1389 To simplify use in double-linked lists, each bin header acts
1390 as a malloc_chunk. This avoids special-casing for headers.
1391 But to conserve space and improve locality, we allocate
1392 only the fd/bk pointers of bins, and then use repositioning tricks
1393 to treat these as the fields of a malloc_chunk*.
1394 */
1395
1396typedef struct malloc_chunk *mbinptr;
1397
1398/* addressing -- note that bin_at(0) does not exist */
1399#define bin_at(m, i) \
1400 (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2])) \
1401 - offsetof (struct malloc_chunk, fd))
1402
1403/* analog of ++bin */
1404#define next_bin(b) ((mbinptr) ((char *) (b) + (sizeof (mchunkptr) << 1)))
1405
1406/* Reminders about list directionality within bins */
1407#define first(b) ((b)->fd)
1408#define last(b) ((b)->bk)
1409
1410/* Take a chunk off a bin list */
1411#define unlink(AV, P, BK, FD) { \
1412 FD = P->fd; \
1413 BK = P->bk; \
1414 if (__builtin_expect (FD->bk != P || BK->fd != P, 0)) \
1415 malloc_printerr (check_action, "corrupted double-linked list", P, AV); \
1416 else { \
1417 FD->bk = BK; \
1418 BK->fd = FD; \
1419 if (!in_smallbin_range (P->size) \
1420 && __builtin_expect (P->fd_nextsize != NULL, 0)) { \
1421 if (__builtin_expect (P->fd_nextsize->bk_nextsize != P, 0) \
1422 || __builtin_expect (P->bk_nextsize->fd_nextsize != P, 0)) \
1423 malloc_printerr (check_action, \
1424 "corrupted double-linked list (not small)", \
1425 P, AV); \
1426 if (FD->fd_nextsize == NULL) { \
1427 if (P->fd_nextsize == P) \
1428 FD->fd_nextsize = FD->bk_nextsize = FD; \
1429 else { \
1430 FD->fd_nextsize = P->fd_nextsize; \
1431 FD->bk_nextsize = P->bk_nextsize; \
1432 P->fd_nextsize->bk_nextsize = FD; \
1433 P->bk_nextsize->fd_nextsize = FD; \
1434 } \
1435 } else { \
1436 P->fd_nextsize->bk_nextsize = P->bk_nextsize; \
1437 P->bk_nextsize->fd_nextsize = P->fd_nextsize; \
1438 } \
1439 } \
1440 } \
1441}
1442
1443/*
1444 Indexing
1445
1446 Bins for sizes < 512 bytes contain chunks of all the same size, spaced
1447 8 bytes apart. Larger bins are approximately logarithmically spaced:
1448
1449 64 bins of size 8
1450 32 bins of size 64
1451 16 bins of size 512
1452 8 bins of size 4096
1453 4 bins of size 32768
1454 2 bins of size 262144
1455 1 bin of size what's left
1456
1457 There is actually a little bit of slop in the numbers in bin_index
1458 for the sake of speed. This makes no difference elsewhere.
1459
1460 The bins top out around 1MB because we expect to service large
1461 requests via mmap.
1462
1463 Bin 0 does not exist. Bin 1 is the unordered list; if that would be
1464 a valid chunk size the small bins are bumped up one.
1465 */
1466
1467#define NBINS 128
1468#define NSMALLBINS 64
1469#define SMALLBIN_WIDTH MALLOC_ALIGNMENT
1470#define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ)
1471#define MIN_LARGE_SIZE ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)
1472
1473#define in_smallbin_range(sz) \
1474 ((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)
1475
1476#define smallbin_index(sz) \
1477 ((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\
1478 + SMALLBIN_CORRECTION)
1479
1480#define largebin_index_32(sz) \
1481 (((((unsigned long) (sz)) >> 6) <= 38) ? 56 + (((unsigned long) (sz)) >> 6) :\
1482 ((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :\
1483 ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
1484 ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
1485 ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
1486 126)
1487
1488#define largebin_index_32_big(sz) \
1489 (((((unsigned long) (sz)) >> 6) <= 45) ? 49 + (((unsigned long) (sz)) >> 6) :\
1490 ((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :\
1491 ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
1492 ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
1493 ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
1494 126)
1495
1496// XXX It remains to be seen whether it is good to keep the widths of
1497// XXX the buckets the same or whether it should be scaled by a factor
1498// XXX of two as well.
1499#define largebin_index_64(sz) \
1500 (((((unsigned long) (sz)) >> 6) <= 48) ? 48 + (((unsigned long) (sz)) >> 6) :\
1501 ((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :\
1502 ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
1503 ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
1504 ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
1505 126)
1506
1507#define largebin_index(sz) \
1508 (SIZE_SZ == 8 ? largebin_index_64 (sz) \
1509 : MALLOC_ALIGNMENT == 16 ? largebin_index_32_big (sz) \
1510 : largebin_index_32 (sz))
1511
1512#define bin_index(sz) \
1513 ((in_smallbin_range (sz)) ? smallbin_index (sz) : largebin_index (sz))
1514
1515
1516/*
1517 Unsorted chunks
1518
1519 All remainders from chunk splits, as well as all returned chunks,
1520 are first placed in the "unsorted" bin. They are then placed
1521 in regular bins after malloc gives them ONE chance to be used before
1522 binning. So, basically, the unsorted_chunks list acts as a queue,
1523 with chunks being placed on it in free (and malloc_consolidate),
1524 and taken off (to be either used or placed in bins) in malloc.
1525
1526 The NON_MAIN_ARENA flag is never set for unsorted chunks, so it
1527 does not have to be taken into account in size comparisons.
1528 */
1529
1530/* The otherwise unindexable 1-bin is used to hold unsorted chunks. */
1531#define unsorted_chunks(M) (bin_at (M, 1))
1532
1533/*
1534 Top
1535
1536 The top-most available chunk (i.e., the one bordering the end of
1537 available memory) is treated specially. It is never included in
1538 any bin, is used only if no other chunk is available, and is
1539 released back to the system if it is very large (see
1540 M_TRIM_THRESHOLD). Because top initially
1541 points to its own bin with initial zero size, thus forcing
1542 extension on the first malloc request, we avoid having any special
1543 code in malloc to check whether it even exists yet. But we still
1544 need to do so when getting memory from system, so we make
1545 initial_top treat the bin as a legal but unusable chunk during the
1546 interval between initialization and the first call to
1547 sysmalloc. (This is somewhat delicate, since it relies on
1548 the 2 preceding words to be zero during this interval as well.)
1549 */
1550
1551/* Conveniently, the unsorted bin can be used as dummy top on first call */
1552#define initial_top(M) (unsorted_chunks (M))
1553
1554/*
1555 Binmap
1556
1557 To help compensate for the large number of bins, a one-level index
1558 structure is used for bin-by-bin searching. `binmap' is a
1559 bitvector recording whether bins are definitely empty so they can
1560 be skipped over during during traversals. The bits are NOT always
1561 cleared as soon as bins are empty, but instead only
1562 when they are noticed to be empty during traversal in malloc.
1563 */
1564
1565/* Conservatively use 32 bits per map word, even if on 64bit system */
1566#define BINMAPSHIFT 5
1567#define BITSPERMAP (1U << BINMAPSHIFT)
1568#define BINMAPSIZE (NBINS / BITSPERMAP)
1569
1570#define idx2block(i) ((i) >> BINMAPSHIFT)
1571#define idx2bit(i) ((1U << ((i) & ((1U << BINMAPSHIFT) - 1))))
1572
1573#define mark_bin(m, i) ((m)->binmap[idx2block (i)] |= idx2bit (i))
1574#define unmark_bin(m, i) ((m)->binmap[idx2block (i)] &= ~(idx2bit (i)))
1575#define get_binmap(m, i) ((m)->binmap[idx2block (i)] & idx2bit (i))
1576
1577/*
1578 Fastbins
1579
1580 An array of lists holding recently freed small chunks. Fastbins
1581 are not doubly linked. It is faster to single-link them, and
1582 since chunks are never removed from the middles of these lists,
1583 double linking is not necessary. Also, unlike regular bins, they
1584 are not even processed in FIFO order (they use faster LIFO) since
1585 ordering doesn't much matter in the transient contexts in which
1586 fastbins are normally used.
1587
1588 Chunks in fastbins keep their inuse bit set, so they cannot
1589 be consolidated with other free chunks. malloc_consolidate
1590 releases all chunks in fastbins and consolidates them with
1591 other free chunks.
1592 */
1593
1594typedef struct malloc_chunk *mfastbinptr;
1595#define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])
1596
1597/* offset 2 to use otherwise unindexable first 2 bins */
1598#define fastbin_index(sz) \
1599 ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)
1600
1601
1602/* The maximum fastbin request size we support */
1603#define MAX_FAST_SIZE (80 * SIZE_SZ / 4)
1604
1605#define NFASTBINS (fastbin_index (request2size (MAX_FAST_SIZE)) + 1)
1606
1607/*
1608 FASTBIN_CONSOLIDATION_THRESHOLD is the size of a chunk in free()
1609 that triggers automatic consolidation of possibly-surrounding
1610 fastbin chunks. This is a heuristic, so the exact value should not
1611 matter too much. It is defined at half the default trim threshold as a
1612 compromise heuristic to only attempt consolidation if it is likely
1613 to lead to trimming. However, it is not dynamically tunable, since
1614 consolidation reduces fragmentation surrounding large chunks even
1615 if trimming is not used.
1616 */
1617
1618#define FASTBIN_CONSOLIDATION_THRESHOLD (65536UL)
1619
1620/*
1621 Since the lowest 2 bits in max_fast don't matter in size comparisons,
1622 they are used as flags.
1623 */
1624
1625/*
1626 FASTCHUNKS_BIT held in max_fast indicates that there are probably
1627 some fastbin chunks. It is set true on entering a chunk into any
1628 fastbin, and cleared only in malloc_consolidate.
1629
1630 The truth value is inverted so that have_fastchunks will be true
1631 upon startup (since statics are zero-filled), simplifying
1632 initialization checks.
1633 */
1634
1635#define FASTCHUNKS_BIT (1U)
1636
1637#define have_fastchunks(M) (((M)->flags & FASTCHUNKS_BIT) == 0)
1638#define clear_fastchunks(M) catomic_or (&(M)->flags, FASTCHUNKS_BIT)
1639#define set_fastchunks(M) catomic_and (&(M)->flags, ~FASTCHUNKS_BIT)
1640
1641/*
1642 NONCONTIGUOUS_BIT indicates that MORECORE does not return contiguous
1643 regions. Otherwise, contiguity is exploited in merging together,
1644 when possible, results from consecutive MORECORE calls.
1645
1646 The initial value comes from MORECORE_CONTIGUOUS, but is
1647 changed dynamically if mmap is ever used as an sbrk substitute.
1648 */
1649
1650#define NONCONTIGUOUS_BIT (2U)
1651
1652#define contiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) == 0)
1653#define noncontiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) != 0)
1654#define set_noncontiguous(M) ((M)->flags |= NONCONTIGUOUS_BIT)
1655#define set_contiguous(M) ((M)->flags &= ~NONCONTIGUOUS_BIT)
1656
1657/* ARENA_CORRUPTION_BIT is set if a memory corruption was detected on the
1658 arena. Such an arena is no longer used to allocate chunks. Chunks
1659 allocated in that arena before detecting corruption are not freed. */
1660
1661#define ARENA_CORRUPTION_BIT (4U)
1662
1663#define arena_is_corrupt(A) (((A)->flags & ARENA_CORRUPTION_BIT))
1664#define set_arena_corrupt(A) ((A)->flags |= ARENA_CORRUPTION_BIT)
1665
1666/*
1667 Set value of max_fast.
1668 Use impossibly small value if 0.
1669 Precondition: there are no existing fastbin chunks.
1670 Setting the value clears fastchunk bit but preserves noncontiguous bit.
1671 */
1672
1673#define set_max_fast(s) \
1674 global_max_fast = (((s) == 0) \
1675 ? SMALLBIN_WIDTH : ((s + SIZE_SZ) & ~MALLOC_ALIGN_MASK))
1676#define get_max_fast() global_max_fast
1677
1678
1679/*
1680 ----------- Internal state representation and initialization -----------
1681 */
1682
1683struct malloc_state
1684{
1685 /* Serialize access. */
1686 mutex_t mutex;
1687
1688 /* Flags (formerly in max_fast). */
1689 int flags;
1690
1691 /* Fastbins */
1692 mfastbinptr fastbinsY[NFASTBINS];
1693
1694 /* Base of the topmost chunk -- not otherwise kept in a bin */
1695 mchunkptr top;
1696
1697 /* The remainder from the most recent split of a small request */
1698 mchunkptr last_remainder;
1699
1700 /* Normal bins packed as described above */
1701 mchunkptr bins[NBINS * 2 - 2];
1702
1703 /* Bitmap of bins */
1704 unsigned int binmap[BINMAPSIZE];
1705
1706 /* Linked list */
1707 struct malloc_state *next;
1708
1709 /* Linked list for free arenas. Access to this field is serialized
1710 by free_list_lock in arena.c. */
1711 struct malloc_state *next_free;
1712
1713 /* Number of threads attached to this arena. 0 if the arena is on
1714 the free list. Access to this field is serialized by
1715 free_list_lock in arena.c. */
1716 INTERNAL_SIZE_T attached_threads;
1717
1718 /* Memory allocated from the system in this arena. */
1719 INTERNAL_SIZE_T system_mem;
1720 INTERNAL_SIZE_T max_system_mem;
1721};
1722
1723struct malloc_par
1724{
1725 /* Tunable parameters */
1726 unsigned long trim_threshold;
1727 INTERNAL_SIZE_T top_pad;
1728 INTERNAL_SIZE_T mmap_threshold;
1729 INTERNAL_SIZE_T arena_test;
1730 INTERNAL_SIZE_T arena_max;
1731
1732 /* Memory map support */
1733 int n_mmaps;
1734 int n_mmaps_max;
1735 int max_n_mmaps;
1736 /* the mmap_threshold is dynamic, until the user sets
1737 it manually, at which point we need to disable any
1738 dynamic behavior. */
1739 int no_dyn_threshold;
1740
1741 /* Statistics */
1742 INTERNAL_SIZE_T mmapped_mem;
1743 /*INTERNAL_SIZE_T sbrked_mem;*/
1744 /*INTERNAL_SIZE_T max_sbrked_mem;*/
1745 INTERNAL_SIZE_T max_mmapped_mem;
1746 INTERNAL_SIZE_T max_total_mem; /* only kept for NO_THREADS */
1747
1748 /* First address handed out by MORECORE/sbrk. */
1749 char *sbrk_base;
1750};
1751
1752/* There are several instances of this struct ("arenas") in this
1753 malloc. If you are adapting this malloc in a way that does NOT use
1754 a static or mmapped malloc_state, you MUST explicitly zero-fill it
1755 before using. This malloc relies on the property that malloc_state
1756 is initialized to all zeroes (as is true of C statics). */
1757
1758static struct malloc_state main_arena =
1759{
1760 .mutex = _LIBC_LOCK_INITIALIZER,
1761 .next = &main_arena,
1762 .attached_threads = 1
1763};
1764
1765/* There is only one instance of the malloc parameters. */
1766
1767static struct malloc_par mp_ =
1768{
1769 .top_pad = DEFAULT_TOP_PAD,
1770 .n_mmaps_max = DEFAULT_MMAP_MAX,
1771 .mmap_threshold = DEFAULT_MMAP_THRESHOLD,
1772 .trim_threshold = DEFAULT_TRIM_THRESHOLD,
1773#define NARENAS_FROM_NCORES(n) ((n) * (sizeof (long) == 4 ? 2 : 8))
1774 .arena_test = NARENAS_FROM_NCORES (1)
1775};
1776
1777
1778/* Non public mallopt parameters. */
1779#define M_ARENA_TEST -7
1780#define M_ARENA_MAX -8
1781
1782
1783/* Maximum size of memory handled in fastbins. */
1784static INTERNAL_SIZE_T global_max_fast;
1785
1786/*
1787 Initialize a malloc_state struct.
1788
1789 This is called only from within malloc_consolidate, which needs
1790 be called in the same contexts anyway. It is never called directly
1791 outside of malloc_consolidate because some optimizing compilers try
1792 to inline it at all call points, which turns out not to be an
1793 optimization at all. (Inlining it in malloc_consolidate is fine though.)
1794 */
1795
1796static void
1797malloc_init_state (mstate av)
1798{
1799 int i;
1800 mbinptr bin;
1801
1802 /* Establish circular links for normal bins */
1803 for (i = 1; i < NBINS; ++i)
1804 {
1805 bin = bin_at (av, i);
1806 bin->fd = bin->bk = bin;
1807 }
1808
1809#if MORECORE_CONTIGUOUS
1810 if (av != &main_arena)
1811#endif
1812 set_noncontiguous (av);
1813 if (av == &main_arena)
1814 set_max_fast (DEFAULT_MXFAST);
1815 av->flags |= FASTCHUNKS_BIT;
1816
1817 av->top = initial_top (av);
1818}
1819
1820/*
1821 Other internal utilities operating on mstates
1822 */
1823
1824static void *sysmalloc (INTERNAL_SIZE_T, mstate);
1825static int systrim (size_t, mstate);
1826static void malloc_consolidate (mstate);
1827
1828
1829/* -------------- Early definitions for debugging hooks ---------------- */
1830
1831/* Define and initialize the hook variables. These weak definitions must
1832 appear before any use of the variables in a function (arena.c uses one). */
1833#ifndef weak_variable
1834/* In GNU libc we want the hook variables to be weak definitions to
1835 avoid a problem with Emacs. */
1836# define weak_variable weak_function
1837#endif
1838
1839/* Forward declarations. */
1840static void *malloc_hook_ini (size_t sz,
1841 const void *caller) __THROW;
1842static void *realloc_hook_ini (void *ptr, size_t sz,
1843 const void *caller) __THROW;
1844static void *memalign_hook_ini (size_t alignment, size_t sz,
1845 const void *caller) __THROW;
1846
1847void weak_variable (*__malloc_initialize_hook) (void) = NULL;
1848void weak_variable (*__free_hook) (void *__ptr,
1849 const void *) = NULL;
1850void *weak_variable (*__malloc_hook)
1851 (size_t __size, const void *) = malloc_hook_ini;
1852void *weak_variable (*__realloc_hook)
1853 (void *__ptr, size_t __size, const void *)
1854 = realloc_hook_ini;
1855void *weak_variable (*__memalign_hook)
1856 (size_t __alignment, size_t __size, const void *)
1857 = memalign_hook_ini;
1858void weak_variable (*__after_morecore_hook) (void) = NULL;
1859
1860
1861/* ---------------- Error behavior ------------------------------------ */
1862
1863#ifndef DEFAULT_CHECK_ACTION
1864# define DEFAULT_CHECK_ACTION 3
1865#endif
1866
1867static int check_action = DEFAULT_CHECK_ACTION;
1868
1869
1870/* ------------------ Testing support ----------------------------------*/
1871
1872static int perturb_byte;
1873
1874static void
1875alloc_perturb (char *p, size_t n)
1876{
1877 if (__glibc_unlikely (perturb_byte))
1878 memset (p, perturb_byte ^ 0xff, n);
1879}
1880
1881static void
1882free_perturb (char *p, size_t n)
1883{
1884 if (__glibc_unlikely (perturb_byte))
1885 memset (p, perturb_byte, n);
1886}
1887
1888
1889
1890#include <stap-probe.h>
1891
1892/* ------------------- Support for multiple arenas -------------------- */
1893#include "arena.c"
1894
1895/*
1896 Debugging support
1897
1898 These routines make a number of assertions about the states
1899 of data structures that should be true at all times. If any
1900 are not true, it's very likely that a user program has somehow
1901 trashed memory. (It's also possible that there is a coding error
1902 in malloc. In which case, please report it!)
1903 */
1904
1905#if !MALLOC_DEBUG
1906
1907# define check_chunk(A, P)
1908# define check_free_chunk(A, P)
1909# define check_inuse_chunk(A, P)
1910# define check_remalloced_chunk(A, P, N)
1911# define check_malloced_chunk(A, P, N)
1912# define check_malloc_state(A)
1913
1914#else
1915
1916# define check_chunk(A, P) do_check_chunk (A, P)
1917# define check_free_chunk(A, P) do_check_free_chunk (A, P)
1918# define check_inuse_chunk(A, P) do_check_inuse_chunk (A, P)
1919# define check_remalloced_chunk(A, P, N) do_check_remalloced_chunk (A, P, N)
1920# define check_malloced_chunk(A, P, N) do_check_malloced_chunk (A, P, N)
1921# define check_malloc_state(A) do_check_malloc_state (A)
1922
1923/*
1924 Properties of all chunks
1925 */
1926
1927static void
1928do_check_chunk (mstate av, mchunkptr p)
1929{
1930 unsigned long sz = chunksize (p);
1931 /* min and max possible addresses assuming contiguous allocation */
1932 char *max_address = (char *) (av->top) + chunksize (av->top);
1933 char *min_address = max_address - av->system_mem;
1934
1935 if (!chunk_is_mmapped (p))
1936 {
1937 /* Has legal address ... */
1938 if (p != av->top)
1939 {
1940 if (contiguous (av))
1941 {
1942 assert (((char *) p) >= min_address);
1943 assert (((char *) p + sz) <= ((char *) (av->top)));
1944 }
1945 }
1946 else
1947 {
1948 /* top size is always at least MINSIZE */
1949 assert ((unsigned long) (sz) >= MINSIZE);
1950 /* top predecessor always marked inuse */
1951 assert (prev_inuse (p));
1952 }
1953 }
1954 else
1955 {
1956 /* address is outside main heap */
1957 if (contiguous (av) && av->top != initial_top (av))
1958 {
1959 assert (((char *) p) < min_address || ((char *) p) >= max_address);
1960 }
1961 /* chunk is page-aligned */
1962 assert (((p->prev_size + sz) & (GLRO (dl_pagesize) - 1)) == 0);
1963 /* mem is aligned */
1964 assert (aligned_OK (chunk2mem (p)));
1965 }
1966}
1967
1968/*
1969 Properties of free chunks
1970 */
1971
1972static void
1973do_check_free_chunk (mstate av, mchunkptr p)
1974{
1975 INTERNAL_SIZE_T sz = p->size & ~(PREV_INUSE | NON_MAIN_ARENA);
1976 mchunkptr next = chunk_at_offset (p, sz);
1977
1978 do_check_chunk (av, p);
1979
1980 /* Chunk must claim to be free ... */
1981 assert (!inuse (p));
1982 assert (!chunk_is_mmapped (p));
1983
1984 /* Unless a special marker, must have OK fields */
1985 if ((unsigned long) (sz) >= MINSIZE)
1986 {
1987 assert ((sz & MALLOC_ALIGN_MASK) == 0);
1988 assert (aligned_OK (chunk2mem (p)));
1989 /* ... matching footer field */
1990 assert (next->prev_size == sz);
1991 /* ... and is fully consolidated */
1992 assert (prev_inuse (p));
1993 assert (next == av->top || inuse (next));
1994
1995 /* ... and has minimally sane links */
1996 assert (p->fd->bk == p);
1997 assert (p->bk->fd == p);
1998 }
1999 else /* markers are always of size SIZE_SZ */
2000 assert (sz == SIZE_SZ);
2001}
2002
2003/*
2004 Properties of inuse chunks
2005 */
2006
2007static void
2008do_check_inuse_chunk (mstate av, mchunkptr p)
2009{
2010 mchunkptr next;
2011
2012 do_check_chunk (av, p);
2013
2014 if (chunk_is_mmapped (p))
2015 return; /* mmapped chunks have no next/prev */
2016
2017 /* Check whether it claims to be in use ... */
2018 assert (inuse (p));
2019
2020 next = next_chunk (p);
2021
2022 /* ... and is surrounded by OK chunks.
2023 Since more things can be checked with free chunks than inuse ones,
2024 if an inuse chunk borders them and debug is on, it's worth doing them.
2025 */
2026 if (!prev_inuse (p))
2027 {
2028 /* Note that we cannot even look at prev unless it is not inuse */
2029 mchunkptr prv = prev_chunk (p);
2030 assert (next_chunk (prv) == p);
2031 do_check_free_chunk (av, prv);
2032 }
2033
2034 if (next == av->top)
2035 {
2036 assert (prev_inuse (next));
2037 assert (chunksize (next) >= MINSIZE);
2038 }
2039 else if (!inuse (next))
2040 do_check_free_chunk (av, next);
2041}
2042
2043/*
2044 Properties of chunks recycled from fastbins
2045 */
2046
2047static void
2048do_check_remalloced_chunk (mstate av, mchunkptr p, INTERNAL_SIZE_T s)
2049{
2050 INTERNAL_SIZE_T sz = p->size & ~(PREV_INUSE | NON_MAIN_ARENA);
2051
2052 if (!chunk_is_mmapped (p))
2053 {
2054 assert (av == arena_for_chunk (p));
2055 if (chunk_non_main_arena (p))
2056 assert (av != &main_arena);
2057 else
2058 assert (av == &main_arena);
2059 }
2060
2061 do_check_inuse_chunk (av, p);
2062
2063 /* Legal size ... */
2064 assert ((sz & MALLOC_ALIGN_MASK) == 0);
2065 assert ((unsigned long) (sz) >= MINSIZE);
2066 /* ... and alignment */
2067 assert (aligned_OK (chunk2mem (p)));
2068 /* chunk is less than MINSIZE more than request */
2069 assert ((long) (sz) - (long) (s) >= 0);
2070 assert ((long) (sz) - (long) (s + MINSIZE) < 0);
2071}
2072
2073/*
2074 Properties of nonrecycled chunks at the point they are malloced
2075 */
2076
2077static void
2078do_check_malloced_chunk (mstate av, mchunkptr p, INTERNAL_SIZE_T s)
2079{
2080 /* same as recycled case ... */
2081 do_check_remalloced_chunk (av, p, s);
2082
2083 /*
2084 ... plus, must obey implementation invariant that prev_inuse is
2085 always true of any allocated chunk; i.e., that each allocated
2086 chunk borders either a previously allocated and still in-use
2087 chunk, or the base of its memory arena. This is ensured
2088 by making all allocations from the `lowest' part of any found
2089 chunk. This does not necessarily hold however for chunks
2090 recycled via fastbins.
2091 */
2092
2093 assert (prev_inuse (p));
2094}
2095
2096
2097/*
2098 Properties of malloc_state.
2099
2100 This may be useful for debugging malloc, as well as detecting user
2101 programmer errors that somehow write into malloc_state.
2102
2103 If you are extending or experimenting with this malloc, you can
2104 probably figure out how to hack this routine to print out or
2105 display chunk addresses, sizes, bins, and other instrumentation.
2106 */
2107
2108static void
2109do_check_malloc_state (mstate av)
2110{
2111 int i;
2112 mchunkptr p;
2113 mchunkptr q;
2114 mbinptr b;
2115 unsigned int idx;
2116 INTERNAL_SIZE_T size;
2117 unsigned long total = 0;
2118 int max_fast_bin;
2119
2120 /* internal size_t must be no wider than pointer type */
2121 assert (sizeof (INTERNAL_SIZE_T) <= sizeof (char *));
2122
2123 /* alignment is a power of 2 */
2124 assert ((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT - 1)) == 0);
2125
2126 /* cannot run remaining checks until fully initialized */
2127 if (av->top == 0 || av->top == initial_top (av))
2128 return;
2129
2130 /* pagesize is a power of 2 */
2131 assert (powerof2(GLRO (dl_pagesize)));
2132
2133 /* A contiguous main_arena is consistent with sbrk_base. */
2134 if (av == &main_arena && contiguous (av))
2135 assert ((char *) mp_.sbrk_base + av->system_mem ==
2136 (char *) av->top + chunksize (av->top));
2137
2138 /* properties of fastbins */
2139
2140 /* max_fast is in allowed range */
2141 assert ((get_max_fast () & ~1) <= request2size (MAX_FAST_SIZE));
2142
2143 max_fast_bin = fastbin_index (get_max_fast ());
2144
2145 for (i = 0; i < NFASTBINS; ++i)
2146 {
2147 p = fastbin (av, i);
2148
2149 /* The following test can only be performed for the main arena.
2150 While mallopt calls malloc_consolidate to get rid of all fast
2151 bins (especially those larger than the new maximum) this does
2152 only happen for the main arena. Trying to do this for any
2153 other arena would mean those arenas have to be locked and
2154 malloc_consolidate be called for them. This is excessive. And
2155 even if this is acceptable to somebody it still cannot solve
2156 the problem completely since if the arena is locked a
2157 concurrent malloc call might create a new arena which then
2158 could use the newly invalid fast bins. */
2159
2160 /* all bins past max_fast are empty */
2161 if (av == &main_arena && i > max_fast_bin)
2162 assert (p == 0);
2163
2164 while (p != 0)
2165 {
2166 /* each chunk claims to be inuse */
2167 do_check_inuse_chunk (av, p);
2168 total += chunksize (p);
2169 /* chunk belongs in this bin */
2170 assert (fastbin_index (chunksize (p)) == i);
2171 p = p->fd;
2172 }
2173 }
2174
2175 if (total != 0)
2176 assert (have_fastchunks (av));
2177 else if (!have_fastchunks (av))
2178 assert (total == 0);
2179
2180 /* check normal bins */
2181 for (i = 1; i < NBINS; ++i)
2182 {
2183 b = bin_at (av, i);
2184
2185 /* binmap is accurate (except for bin 1 == unsorted_chunks) */
2186 if (i >= 2)
2187 {
2188 unsigned int binbit = get_binmap (av, i);
2189 int empty = last (b) == b;
2190 if (!binbit)
2191 assert (empty);
2192 else if (!empty)
2193 assert (binbit);
2194 }
2195
2196 for (p = last (b); p != b; p = p->bk)
2197 {
2198 /* each chunk claims to be free */
2199 do_check_free_chunk (av, p);
2200 size = chunksize (p);
2201 total += size;
2202 if (i >= 2)
2203 {
2204 /* chunk belongs in bin */
2205 idx = bin_index (size);
2206 assert (idx == i);
2207 /* lists are sorted */
2208 assert (p->bk == b ||
2209 (unsigned long) chunksize (p->bk) >= (unsigned long) chunksize (p));
2210
2211 if (!in_smallbin_range (size))
2212 {
2213 if (p->fd_nextsize != NULL)
2214 {
2215 if (p->fd_nextsize == p)
2216 assert (p->bk_nextsize == p);
2217 else
2218 {
2219 if (p->fd_nextsize == first (b))
2220 assert (chunksize (p) < chunksize (p->fd_nextsize));
2221 else
2222 assert (chunksize (p) > chunksize (p->fd_nextsize));
2223
2224 if (p == first (b))
2225 assert (chunksize (p) > chunksize (p->bk_nextsize));
2226 else
2227 assert (chunksize (p) < chunksize (p->bk_nextsize));
2228 }
2229 }
2230 else
2231 assert (p->bk_nextsize == NULL);
2232 }
2233 }
2234 else if (!in_smallbin_range (size))
2235 assert (p->fd_nextsize == NULL && p->bk_nextsize == NULL);
2236 /* chunk is followed by a legal chain of inuse chunks */
2237 for (q = next_chunk (p);
2238 (q != av->top && inuse (q) &&
2239 (unsigned long) (chunksize (q)) >= MINSIZE);
2240 q = next_chunk (q))
2241 do_check_inuse_chunk (av, q);
2242 }
2243 }
2244
2245 /* top chunk is OK */
2246 check_chunk (av, av->top);
2247}
2248#endif
2249
2250
2251/* ----------------- Support for debugging hooks -------------------- */
2252#include "hooks.c"
2253
2254
2255/* ----------- Routines dealing with system allocation -------------- */
2256
2257/*
2258 sysmalloc handles malloc cases requiring more memory from the system.
2259 On entry, it is assumed that av->top does not have enough
2260 space to service request for nb bytes, thus requiring that av->top
2261 be extended or replaced.
2262 */
2263
2264static void *
2265sysmalloc (INTERNAL_SIZE_T nb, mstate av)
2266{
2267 mchunkptr old_top; /* incoming value of av->top */
2268 INTERNAL_SIZE_T old_size; /* its size */
2269 char *old_end; /* its end address */
2270
2271 long size; /* arg to first MORECORE or mmap call */
2272 char *brk; /* return value from MORECORE */
2273
2274 long correction; /* arg to 2nd MORECORE call */
2275 char *snd_brk; /* 2nd return val */
2276
2277 INTERNAL_SIZE_T front_misalign; /* unusable bytes at front of new space */
2278 INTERNAL_SIZE_T end_misalign; /* partial page left at end of new space */
2279 char *aligned_brk; /* aligned offset into brk */
2280
2281 mchunkptr p; /* the allocated/returned chunk */
2282 mchunkptr remainder; /* remainder from allocation */
2283 unsigned long remainder_size; /* its size */
2284
2285
2286 size_t pagesize = GLRO (dl_pagesize);
2287 bool tried_mmap = false;
2288
2289
2290 /*
2291 If have mmap, and the request size meets the mmap threshold, and
2292 the system supports mmap, and there are few enough currently
2293 allocated mmapped regions, try to directly map this request
2294 rather than expanding top.
2295 */
2296
2297 if (av == NULL
2298 || ((unsigned long) (nb) >= (unsigned long) (mp_.mmap_threshold)
2299 && (mp_.n_mmaps < mp_.n_mmaps_max)))
2300 {
2301 char *mm; /* return value from mmap call*/
2302
2303 try_mmap:
2304 /*
2305 Round up size to nearest page. For mmapped chunks, the overhead
2306 is one SIZE_SZ unit larger than for normal chunks, because there
2307 is no following chunk whose prev_size field could be used.
2308
2309 See the front_misalign handling below, for glibc there is no
2310 need for further alignments unless we have have high alignment.
2311 */
2312 if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
2313 size = ALIGN_UP (nb + SIZE_SZ, pagesize);
2314 else
2315 size = ALIGN_UP (nb + SIZE_SZ + MALLOC_ALIGN_MASK, pagesize);
2316 tried_mmap = true;
2317
2318 /* Don't try if size wraps around 0 */
2319 if ((unsigned long) (size) > (unsigned long) (nb))
2320 {
2321 mm = (char *) (MMAP (0, size, PROT_READ | PROT_WRITE, 0));
2322
2323 if (mm != MAP_FAILED)
2324 {
2325 /*
2326 The offset to the start of the mmapped region is stored
2327 in the prev_size field of the chunk. This allows us to adjust
2328 returned start address to meet alignment requirements here
2329 and in memalign(), and still be able to compute proper
2330 address argument for later munmap in free() and realloc().
2331 */
2332
2333 if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
2334 {
2335 /* For glibc, chunk2mem increases the address by 2*SIZE_SZ and
2336 MALLOC_ALIGN_MASK is 2*SIZE_SZ-1. Each mmap'ed area is page
2337 aligned and therefore definitely MALLOC_ALIGN_MASK-aligned. */
2338 assert (((INTERNAL_SIZE_T) chunk2mem (mm) & MALLOC_ALIGN_MASK) == 0);
2339 front_misalign = 0;
2340 }
2341 else
2342 front_misalign = (INTERNAL_SIZE_T) chunk2mem (mm) & MALLOC_ALIGN_MASK;
2343 if (front_misalign > 0)
2344 {
2345 correction = MALLOC_ALIGNMENT - front_misalign;
2346 p = (mchunkptr) (mm + correction);
2347 p->prev_size = correction;
2348 set_head (p, (size - correction) | IS_MMAPPED);
2349 }
2350 else
2351 {
2352 p = (mchunkptr) mm;
2353 set_head (p, size | IS_MMAPPED);
2354 }
2355
2356 /* update statistics */
2357
2358 int new = atomic_exchange_and_add (&mp_.n_mmaps, 1) + 1;
2359 atomic_max (&mp_.max_n_mmaps, new);
2360
2361 unsigned long sum;
2362 sum = atomic_exchange_and_add (&mp_.mmapped_mem, size) + size;
2363 atomic_max (&mp_.max_mmapped_mem, sum);
2364
2365 check_chunk (av, p);
2366
2367 return chunk2mem (p);
2368 }
2369 }
2370 }
2371
2372 /* There are no usable arenas and mmap also failed. */
2373 if (av == NULL)
2374 return 0;
2375
2376 /* Record incoming configuration of top */
2377
2378 old_top = av->top;
2379 old_size = chunksize (old_top);
2380 old_end = (char *) (chunk_at_offset (old_top, old_size));
2381
2382 brk = snd_brk = (char *) (MORECORE_FAILURE);
2383
2384 /*
2385 If not the first time through, we require old_size to be
2386 at least MINSIZE and to have prev_inuse set.
2387 */
2388
2389 assert ((old_top == initial_top (av) && old_size == 0) ||
2390 ((unsigned long) (old_size) >= MINSIZE &&
2391 prev_inuse (old_top) &&
2392 ((unsigned long) old_end & (pagesize - 1)) == 0));
2393
2394 /* Precondition: not enough current space to satisfy nb request */
2395 assert ((unsigned long) (old_size) < (unsigned long) (nb + MINSIZE));
2396
2397
2398 if (av != &main_arena)
2399 {
2400 heap_info *old_heap, *heap;
2401 size_t old_heap_size;
2402
2403 /* First try to extend the current heap. */
2404 old_heap = heap_for_ptr (old_top);
2405 old_heap_size = old_heap->size;
2406 if ((long) (MINSIZE + nb - old_size) > 0
2407 && grow_heap (old_heap, MINSIZE + nb - old_size) == 0)
2408 {
2409 av->system_mem += old_heap->size - old_heap_size;
2410 arena_mem += old_heap->size - old_heap_size;
2411 set_head (old_top, (((char *) old_heap + old_heap->size) - (char *) old_top)
2412 | PREV_INUSE);
2413 }
2414 else if ((heap = new_heap (nb + (MINSIZE + sizeof (*heap)), mp_.top_pad)))
2415 {
2416 /* Use a newly allocated heap. */
2417 heap->ar_ptr = av;
2418 heap->prev = old_heap;
2419 av->system_mem += heap->size;
2420 arena_mem += heap->size;
2421 /* Set up the new top. */
2422 top (av) = chunk_at_offset (heap, sizeof (*heap));
2423 set_head (top (av), (heap->size - sizeof (*heap)) | PREV_INUSE);
2424
2425 /* Setup fencepost and free the old top chunk with a multiple of
2426 MALLOC_ALIGNMENT in size. */
2427 /* The fencepost takes at least MINSIZE bytes, because it might
2428 become the top chunk again later. Note that a footer is set
2429 up, too, although the chunk is marked in use. */
2430 old_size = (old_size - MINSIZE) & ~MALLOC_ALIGN_MASK;
2431 set_head (chunk_at_offset (old_top, old_size + 2 * SIZE_SZ), 0 | PREV_INUSE);
2432 if (old_size >= MINSIZE)
2433 {
2434 set_head (chunk_at_offset (old_top, old_size), (2 * SIZE_SZ) | PREV_INUSE);
2435 set_foot (chunk_at_offset (old_top, old_size), (2 * SIZE_SZ));
2436 set_head (old_top, old_size | PREV_INUSE | NON_MAIN_ARENA);
2437 _int_free (av, old_top, 1);
2438 }
2439 else
2440 {
2441 set_head (old_top, (old_size + 2 * SIZE_SZ) | PREV_INUSE);
2442 set_foot (old_top, (old_size + 2 * SIZE_SZ));
2443 }
2444 }
2445 else if (!tried_mmap)
2446 /* We can at least try to use to mmap memory. */
2447 goto try_mmap;
2448 }
2449 else /* av == main_arena */
2450
2451
2452 { /* Request enough space for nb + pad + overhead */
2453 size = nb + mp_.top_pad + MINSIZE;
2454
2455 /*
2456 If contiguous, we can subtract out existing space that we hope to
2457 combine with new space. We add it back later only if
2458 we don't actually get contiguous space.
2459 */
2460
2461 if (contiguous (av))
2462 size -= old_size;
2463
2464 /*
2465 Round to a multiple of page size.
2466 If MORECORE is not contiguous, this ensures that we only call it
2467 with whole-page arguments. And if MORECORE is contiguous and
2468 this is not first time through, this preserves page-alignment of
2469 previous calls. Otherwise, we correct to page-align below.
2470 */
2471
2472 size = ALIGN_UP (size, pagesize);
2473
2474 /*
2475 Don't try to call MORECORE if argument is so big as to appear
2476 negative. Note that since mmap takes size_t arg, it may succeed
2477 below even if we cannot call MORECORE.
2478 */
2479
2480 if (size > 0)
2481 {
2482 brk = (char *) (MORECORE (size));
2483 LIBC_PROBE (memory_sbrk_more, 2, brk, size);
2484 }
2485
2486 if (brk != (char *) (MORECORE_FAILURE))
2487 {
2488 /* Call the `morecore' hook if necessary. */
2489 void (*hook) (void) = atomic_forced_read (__after_morecore_hook);
2490 if (__builtin_expect (hook != NULL, 0))
2491 (*hook)();
2492 }
2493 else
2494 {
2495 /*
2496 If have mmap, try using it as a backup when MORECORE fails or
2497 cannot be used. This is worth doing on systems that have "holes" in
2498 address space, so sbrk cannot extend to give contiguous space, but
2499 space is available elsewhere. Note that we ignore mmap max count
2500 and threshold limits, since the space will not be used as a
2501 segregated mmap region.
2502 */
2503
2504 /* Cannot merge with old top, so add its size back in */
2505 if (contiguous (av))
2506 size = ALIGN_UP (size + old_size, pagesize);
2507
2508 /* If we are relying on mmap as backup, then use larger units */
2509 if ((unsigned long) (size) < (unsigned long) (MMAP_AS_MORECORE_SIZE))
2510 size = MMAP_AS_MORECORE_SIZE;
2511
2512 /* Don't try if size wraps around 0 */
2513 if ((unsigned long) (size) > (unsigned long) (nb))
2514 {
2515 char *mbrk = (char *) (MMAP (0, size, PROT_READ | PROT_WRITE, 0));
2516
2517 if (mbrk != MAP_FAILED)
2518 {
2519 /* We do not need, and cannot use, another sbrk call to find end */
2520 brk = mbrk;
2521 snd_brk = brk + size;
2522
2523 /*
2524 Record that we no longer have a contiguous sbrk region.
2525 After the first time mmap is used as backup, we do not
2526 ever rely on contiguous space since this could incorrectly
2527 bridge regions.
2528 */
2529 set_noncontiguous (av);
2530 }
2531 }
2532 }
2533
2534 if (brk != (char *) (MORECORE_FAILURE))
2535 {
2536 if (mp_.sbrk_base == 0)
2537 mp_.sbrk_base = brk;
2538 av->system_mem += size;
2539
2540 /*
2541 If MORECORE extends previous space, we can likewise extend top size.
2542 */
2543
2544 if (brk == old_end && snd_brk == (char *) (MORECORE_FAILURE))
2545 set_head (old_top, (size + old_size) | PREV_INUSE);
2546
2547 else if (contiguous (av) && old_size && brk < old_end)
2548 {
2549 /* Oops! Someone else killed our space.. Can't touch anything. */
2550 malloc_printerr (3, "break adjusted to free malloc space", brk,
2551 av);
2552 }
2553
2554 /*
2555 Otherwise, make adjustments:
2556
2557 * If the first time through or noncontiguous, we need to call sbrk
2558 just to find out where the end of memory lies.
2559
2560 * We need to ensure that all returned chunks from malloc will meet
2561 MALLOC_ALIGNMENT
2562
2563 * If there was an intervening foreign sbrk, we need to adjust sbrk
2564 request size to account for fact that we will not be able to
2565 combine new space with existing space in old_top.
2566
2567 * Almost all systems internally allocate whole pages at a time, in
2568 which case we might as well use the whole last page of request.
2569 So we allocate enough more memory to hit a page boundary now,
2570 which in turn causes future contiguous calls to page-align.
2571 */
2572
2573 else
2574 {
2575 front_misalign = 0;
2576 end_misalign = 0;
2577 correction = 0;
2578 aligned_brk = brk;
2579
2580 /* handle contiguous cases */
2581 if (contiguous (av))
2582 {
2583 /* Count foreign sbrk as system_mem. */
2584 if (old_size)
2585 av->system_mem += brk - old_end;
2586
2587 /* Guarantee alignment of first new chunk made from this space */
2588
2589 front_misalign = (INTERNAL_SIZE_T) chunk2mem (brk) & MALLOC_ALIGN_MASK;
2590 if (front_misalign > 0)
2591 {
2592 /*
2593 Skip over some bytes to arrive at an aligned position.
2594 We don't need to specially mark these wasted front bytes.
2595 They will never be accessed anyway because
2596 prev_inuse of av->top (and any chunk created from its start)
2597 is always true after initialization.
2598 */
2599
2600 correction = MALLOC_ALIGNMENT - front_misalign;
2601 aligned_brk += correction;
2602 }
2603
2604 /*
2605 If this isn't adjacent to existing space, then we will not
2606 be able to merge with old_top space, so must add to 2nd request.
2607 */
2608
2609 correction += old_size;
2610
2611 /* Extend the end address to hit a page boundary */
2612 end_misalign = (INTERNAL_SIZE_T) (brk + size + correction);
2613 correction += (ALIGN_UP (end_misalign, pagesize)) - end_misalign;
2614
2615 assert (correction >= 0);
2616 snd_brk = (char *) (MORECORE (correction));
2617
2618 /*
2619 If can't allocate correction, try to at least find out current
2620 brk. It might be enough to proceed without failing.
2621
2622 Note that if second sbrk did NOT fail, we assume that space
2623 is contiguous with first sbrk. This is a safe assumption unless
2624 program is multithreaded but doesn't use locks and a foreign sbrk
2625 occurred between our first and second calls.
2626 */
2627
2628 if (snd_brk == (char *) (MORECORE_FAILURE))
2629 {
2630 correction = 0;
2631 snd_brk = (char *) (MORECORE (0));
2632 }
2633 else
2634 {
2635 /* Call the `morecore' hook if necessary. */
2636 void (*hook) (void) = atomic_forced_read (__after_morecore_hook);
2637 if (__builtin_expect (hook != NULL, 0))
2638 (*hook)();
2639 }
2640 }
2641
2642 /* handle non-contiguous cases */
2643 else
2644 {
2645 if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
2646 /* MORECORE/mmap must correctly align */
2647 assert (((unsigned long) chunk2mem (brk) & MALLOC_ALIGN_MASK) == 0);
2648 else
2649 {
2650 front_misalign = (INTERNAL_SIZE_T) chunk2mem (brk) & MALLOC_ALIGN_MASK;
2651 if (front_misalign > 0)
2652 {
2653 /*
2654 Skip over some bytes to arrive at an aligned position.
2655 We don't need to specially mark these wasted front bytes.
2656 They will never be accessed anyway because
2657 prev_inuse of av->top (and any chunk created from its start)
2658 is always true after initialization.
2659 */
2660
2661 aligned_brk += MALLOC_ALIGNMENT - front_misalign;
2662 }
2663 }
2664
2665 /* Find out current end of memory */
2666 if (snd_brk == (char *) (MORECORE_FAILURE))
2667 {
2668 snd_brk = (char *) (MORECORE (0));
2669 }
2670 }
2671
2672 /* Adjust top based on results of second sbrk */
2673 if (snd_brk != (char *) (MORECORE_FAILURE))
2674 {
2675 av->top = (mchunkptr) aligned_brk;
2676 set_head (av->top, (snd_brk - aligned_brk + correction) | PREV_INUSE);
2677 av->system_mem += correction;
2678
2679 /*
2680 If not the first time through, we either have a
2681 gap due to foreign sbrk or a non-contiguous region. Insert a
2682 double fencepost at old_top to prevent consolidation with space
2683 we don't own. These fenceposts are artificial chunks that are
2684 marked as inuse and are in any case too small to use. We need
2685 two to make sizes and alignments work out.
2686 */
2687
2688 if (old_size != 0)
2689 {
2690 /*
2691 Shrink old_top to insert fenceposts, keeping size a
2692 multiple of MALLOC_ALIGNMENT. We know there is at least
2693 enough space in old_top to do this.
2694 */
2695 old_size = (old_size - 4 * SIZE_SZ) & ~MALLOC_ALIGN_MASK;
2696 set_head (old_top, old_size | PREV_INUSE);
2697
2698 /*
2699 Note that the following assignments completely overwrite
2700 old_top when old_size was previously MINSIZE. This is
2701 intentional. We need the fencepost, even if old_top otherwise gets
2702 lost.
2703 */
2704 chunk_at_offset (old_top, old_size)->size =
2705 (2 * SIZE_SZ) | PREV_INUSE;
2706
2707 chunk_at_offset (old_top, old_size + 2 * SIZE_SZ)->size =
2708 (2 * SIZE_SZ) | PREV_INUSE;
2709
2710 /* If possible, release the rest. */
2711 if (old_size >= MINSIZE)
2712 {
2713 _int_free (av, old_top, 1);
2714 }
2715 }
2716 }
2717 }
2718 }
2719 } /* if (av != &main_arena) */
2720
2721 if ((unsigned long) av->system_mem > (unsigned long) (av->max_system_mem))
2722 av->max_system_mem = av->system_mem;
2723 check_malloc_state (av);
2724
2725 /* finally, do the allocation */
2726 p = av->top;
2727 size = chunksize (p);
2728
2729 /* check that one of the above allocation paths succeeded */
2730 if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
2731 {
2732 remainder_size = size - nb;
2733 remainder = chunk_at_offset (p, nb);
2734 av->top = remainder;
2735 set_head (p, nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));
2736 set_head (remainder, remainder_size | PREV_INUSE);
2737 check_malloced_chunk (av, p, nb);
2738 return chunk2mem (p);
2739 }
2740
2741 /* catch all failure paths */
2742 __set_errno (ENOMEM);
2743 return 0;
2744}
2745
2746
2747/*
2748 systrim is an inverse of sorts to sysmalloc. It gives memory back
2749 to the system (via negative arguments to sbrk) if there is unused
2750 memory at the `high' end of the malloc pool. It is called
2751 automatically by free() when top space exceeds the trim
2752 threshold. It is also called by the public malloc_trim routine. It
2753 returns 1 if it actually released any memory, else 0.
2754 */
2755
2756static int
2757systrim (size_t pad, mstate av)
2758{
2759 long top_size; /* Amount of top-most memory */
2760 long extra; /* Amount to release */
2761 long released; /* Amount actually released */
2762 char *current_brk; /* address returned by pre-check sbrk call */
2763 char *new_brk; /* address returned by post-check sbrk call */
2764 size_t pagesize;
2765 long top_area;
2766
2767 pagesize = GLRO (dl_pagesize);
2768 top_size = chunksize (av->top);
2769
2770 top_area = top_size - MINSIZE - 1;
2771 if (top_area <= pad)
2772 return 0;
2773
2774 /* Release in pagesize units and round down to the nearest page. */
2775 extra = ALIGN_DOWN(top_area - pad, pagesize);
2776
2777 if (extra == 0)
2778 return 0;
2779
2780 /*
2781 Only proceed if end of memory is where we last set it.
2782 This avoids problems if there were foreign sbrk calls.
2783 */
2784 current_brk = (char *) (MORECORE (0));
2785 if (current_brk == (char *) (av->top) + top_size)
2786 {
2787 /*
2788 Attempt to release memory. We ignore MORECORE return value,
2789 and instead call again to find out where new end of memory is.
2790 This avoids problems if first call releases less than we asked,
2791 of if failure somehow altered brk value. (We could still
2792 encounter problems if it altered brk in some very bad way,
2793 but the only thing we can do is adjust anyway, which will cause
2794 some downstream failure.)
2795 */
2796
2797 MORECORE (-extra);
2798 /* Call the `morecore' hook if necessary. */
2799 void (*hook) (void) = atomic_forced_read (__after_morecore_hook);
2800 if (__builtin_expect (hook != NULL, 0))
2801 (*hook)();
2802 new_brk = (char *) (MORECORE (0));
2803
2804 LIBC_PROBE (memory_sbrk_less, 2, new_brk, extra);
2805
2806 if (new_brk != (char *) MORECORE_FAILURE)
2807 {
2808 released = (long) (current_brk - new_brk);
2809
2810 if (released != 0)
2811 {
2812 /* Success. Adjust top. */
2813 av->system_mem -= released;
2814 set_head (av->top, (top_size - released) | PREV_INUSE);
2815 check_malloc_state (av);
2816 return 1;
2817 }
2818 }
2819 }
2820 return 0;
2821}
2822
2823static void
2824internal_function
2825munmap_chunk (mchunkptr p)
2826{
2827 INTERNAL_SIZE_T size = chunksize (p);
2828
2829 assert (chunk_is_mmapped (p));
2830
2831 uintptr_t block = (uintptr_t) p - p->prev_size;
2832 size_t total_size = p->prev_size + size;
2833 /* Unfortunately we have to do the compilers job by hand here. Normally
2834 we would test BLOCK and TOTAL-SIZE separately for compliance with the
2835 page size. But gcc does not recognize the optimization possibility
2836 (in the moment at least) so we combine the two values into one before
2837 the bit test. */
2838 if (__builtin_expect (((block | total_size) & (GLRO (dl_pagesize) - 1)) != 0, 0))
2839 {
2840 malloc_printerr (check_action, "munmap_chunk(): invalid pointer",
2841 chunk2mem (p), NULL);
2842 return;
2843 }
2844
2845 atomic_decrement (&mp_.n_mmaps);
2846 atomic_add (&mp_.mmapped_mem, -total_size);
2847
2848 /* If munmap failed the process virtual memory address space is in a
2849 bad shape. Just leave the block hanging around, the process will
2850 terminate shortly anyway since not much can be done. */
2851 __munmap ((char *) block, total_size);
2852}
2853
2854#if HAVE_MREMAP
2855
2856static mchunkptr
2857internal_function
2858mremap_chunk (mchunkptr p, size_t new_size)
2859{
2860 size_t pagesize = GLRO (dl_pagesize);
2861 INTERNAL_SIZE_T offset = p->prev_size;
2862 INTERNAL_SIZE_T size = chunksize (p);
2863 char *cp;
2864
2865 assert (chunk_is_mmapped (p));
2866 assert (((size + offset) & (GLRO (dl_pagesize) - 1)) == 0);
2867
2868 /* Note the extra SIZE_SZ overhead as in mmap_chunk(). */
2869 new_size = ALIGN_UP (new_size + offset + SIZE_SZ, pagesize);
2870
2871 /* No need to remap if the number of pages does not change. */
2872 if (size + offset == new_size)
2873 return p;
2874
2875 cp = (char *) __mremap ((char *) p - offset, size + offset, new_size,
2876 MREMAP_MAYMOVE);
2877
2878 if (cp == MAP_FAILED)
2879 return 0;
2880
2881 p = (mchunkptr) (cp + offset);
2882
2883 assert (aligned_OK (chunk2mem (p)));
2884
2885 assert ((p->prev_size == offset));
2886 set_head (p, (new_size - offset) | IS_MMAPPED);
2887
2888 INTERNAL_SIZE_T new;
2889 new = atomic_exchange_and_add (&mp_.mmapped_mem, new_size - size - offset)
2890 + new_size - size - offset;
2891 atomic_max (&mp_.max_mmapped_mem, new);
2892 return p;
2893}
2894#endif /* HAVE_MREMAP */
2895
2896/*------------------------ Public wrappers. --------------------------------*/
2897
2898void *
2899__libc_malloc (size_t bytes)
2900{
2901 mstate ar_ptr;
2902 void *victim;
2903
2904 void *(*hook) (size_t, const void *)
2905 = atomic_forced_read (__malloc_hook);
2906 if (__builtin_expect (hook != NULL, 0))
2907 return (*hook)(bytes, RETURN_ADDRESS (0));
2908
2909 arena_get (ar_ptr, bytes);
2910
2911 victim = _int_malloc (ar_ptr, bytes);
2912 /* Retry with another arena only if we were able to find a usable arena
2913 before. */
2914 if (!victim && ar_ptr != NULL)
2915 {
2916 LIBC_PROBE (memory_malloc_retry, 1, bytes);
2917 ar_ptr = arena_get_retry (ar_ptr, bytes);
2918 victim = _int_malloc (ar_ptr, bytes);
2919 }
2920
2921 if (ar_ptr != NULL)
2922 (void) mutex_unlock (&ar_ptr->mutex);
2923
2924 assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
2925 ar_ptr == arena_for_chunk (mem2chunk (victim)));
2926 return victim;
2927}
2928libc_hidden_def (__libc_malloc)
2929
2930void
2931__libc_free (void *mem)
2932{
2933 mstate ar_ptr;
2934 mchunkptr p; /* chunk corresponding to mem */
2935
2936 void (*hook) (void *, const void *)
2937 = atomic_forced_read (__free_hook);
2938 if (__builtin_expect (hook != NULL, 0))
2939 {
2940 (*hook)(mem, RETURN_ADDRESS (0));
2941 return;
2942 }
2943
2944 if (mem == 0) /* free(0) has no effect */
2945 return;
2946
2947 p = mem2chunk (mem);
2948
2949 if (chunk_is_mmapped (p)) /* release mmapped memory. */
2950 {
2951 /* see if the dynamic brk/mmap threshold needs adjusting */
2952 if (!mp_.no_dyn_threshold
2953 && p->size > mp_.mmap_threshold
2954 && p->size <= DEFAULT_MMAP_THRESHOLD_MAX)
2955 {
2956 mp_.mmap_threshold = chunksize (p);
2957 mp_.trim_threshold = 2 * mp_.mmap_threshold;
2958 LIBC_PROBE (memory_mallopt_free_dyn_thresholds, 2,
2959 mp_.mmap_threshold, mp_.trim_threshold);
2960 }
2961 munmap_chunk (p);
2962 return;
2963 }
2964
2965 ar_ptr = arena_for_chunk (p);
2966 _int_free (ar_ptr, p, 0);
2967}
2968libc_hidden_def (__libc_free)
2969
2970void *
2971__libc_realloc (void *oldmem, size_t bytes)
2972{
2973 mstate ar_ptr;
2974 INTERNAL_SIZE_T nb; /* padded request size */
2975
2976 void *newp; /* chunk to return */
2977
2978 void *(*hook) (void *, size_t, const void *) =
2979 atomic_forced_read (__realloc_hook);
2980 if (__builtin_expect (hook != NULL, 0))
2981 return (*hook)(oldmem, bytes, RETURN_ADDRESS (0));
2982
2983#if REALLOC_ZERO_BYTES_FREES
2984 if (bytes == 0 && oldmem != NULL)
2985 {
2986 __libc_free (oldmem); return 0;
2987 }
2988#endif
2989
2990 /* realloc of null is supposed to be same as malloc */
2991 if (oldmem == 0)
2992 return __libc_malloc (bytes);
2993
2994 /* chunk corresponding to oldmem */
2995 const mchunkptr oldp = mem2chunk (oldmem);
2996 /* its size */
2997 const INTERNAL_SIZE_T oldsize = chunksize (oldp);
2998
2999 if (chunk_is_mmapped (oldp))
3000 ar_ptr = NULL;
3001 else
3002 ar_ptr = arena_for_chunk (oldp);
3003
3004 /* Little security check which won't hurt performance: the
3005 allocator never wrapps around at the end of the address space.
3006 Therefore we can exclude some size values which might appear
3007 here by accident or by "design" from some intruder. */
3008 if (__builtin_expect ((uintptr_t) oldp > (uintptr_t) -oldsize, 0)
3009 || __builtin_expect (misaligned_chunk (oldp), 0))
3010 {
3011 malloc_printerr (check_action, "realloc(): invalid pointer", oldmem,
3012 ar_ptr);
3013 return NULL;
3014 }
3015
3016 checked_request2size (bytes, nb);
3017
3018 if (chunk_is_mmapped (oldp))
3019 {
3020 void *newmem;
3021
3022#if HAVE_MREMAP
3023 newp = mremap_chunk (oldp, nb);
3024 if (newp)
3025 return chunk2mem (newp);
3026#endif
3027 /* Note the extra SIZE_SZ overhead. */
3028 if (oldsize - SIZE_SZ >= nb)
3029 return oldmem; /* do nothing */
3030
3031 /* Must alloc, copy, free. */
3032 newmem = __libc_malloc (bytes);
3033 if (newmem == 0)
3034 return 0; /* propagate failure */
3035
3036 memcpy (newmem, oldmem, oldsize - 2 * SIZE_SZ);
3037 munmap_chunk (oldp);
3038 return newmem;
3039 }
3040
3041 (void) mutex_lock (&ar_ptr->mutex);
3042
3043 newp = _int_realloc (ar_ptr, oldp, oldsize, nb);
3044
3045 (void) mutex_unlock (&ar_ptr->mutex);
3046 assert (!newp || chunk_is_mmapped (mem2chunk (newp)) ||
3047 ar_ptr == arena_for_chunk (mem2chunk (newp)));
3048
3049 if (newp == NULL)
3050 {
3051 /* Try harder to allocate memory in other arenas. */
3052 LIBC_PROBE (memory_realloc_retry, 2, bytes, oldmem);
3053 newp = __libc_malloc (bytes);
3054 if (newp != NULL)
3055 {
3056 memcpy (newp, oldmem, oldsize - SIZE_SZ);
3057 _int_free (ar_ptr, oldp, 0);
3058 }
3059 }
3060
3061 return newp;
3062}
3063libc_hidden_def (__libc_realloc)
3064
3065void *
3066__libc_memalign (size_t alignment, size_t bytes)
3067{
3068 void *address = RETURN_ADDRESS (0);
3069 return _mid_memalign (alignment, bytes, address);
3070}
3071
3072static void *
3073_mid_memalign (size_t alignment, size_t bytes, void *address)
3074{
3075 mstate ar_ptr;
3076 void *p;
3077
3078 void *(*hook) (size_t, size_t, const void *) =
3079 atomic_forced_read (__memalign_hook);
3080 if (__builtin_expect (hook != NULL, 0))
3081 return (*hook)(alignment, bytes, address);
3082
3083 /* If we need less alignment than we give anyway, just relay to malloc. */
3084 if (alignment <= MALLOC_ALIGNMENT)
3085 return __libc_malloc (bytes);
3086
3087 /* Otherwise, ensure that it is at least a minimum chunk size */
3088 if (alignment < MINSIZE)
3089 alignment = MINSIZE;
3090
3091 /* If the alignment is greater than SIZE_MAX / 2 + 1 it cannot be a
3092 power of 2 and will cause overflow in the check below. */
3093 if (alignment > SIZE_MAX / 2 + 1)
3094 {
3095 __set_errno (EINVAL);
3096 return 0;
3097 }
3098
3099 /* Check for overflow. */
3100 if (bytes > SIZE_MAX - alignment - MINSIZE)
3101 {
3102 __set_errno (ENOMEM);
3103 return 0;
3104 }
3105
3106
3107 /* Make sure alignment is power of 2. */
3108 if (!powerof2 (alignment))
3109 {
3110 size_t a = MALLOC_ALIGNMENT * 2;
3111 while (a < alignment)
3112 a <<= 1;
3113 alignment = a;
3114 }
3115
3116 arena_get (ar_ptr, bytes + alignment + MINSIZE);
3117
3118 p = _int_memalign (ar_ptr, alignment, bytes);
3119 if (!p && ar_ptr != NULL)
3120 {
3121 LIBC_PROBE (memory_memalign_retry, 2, bytes, alignment);
3122 ar_ptr = arena_get_retry (ar_ptr, bytes);
3123 p = _int_memalign (ar_ptr, alignment, bytes);
3124 }
3125
3126 if (ar_ptr != NULL)
3127 (void) mutex_unlock (&ar_ptr->mutex);
3128
3129 assert (!p || chunk_is_mmapped (mem2chunk (p)) ||
3130 ar_ptr == arena_for_chunk (mem2chunk (p)));
3131 return p;
3132}
3133/* For ISO C11. */
3134weak_alias (__libc_memalign, aligned_alloc)
3135libc_hidden_def (__libc_memalign)
3136
3137void *
3138__libc_valloc (size_t bytes)
3139{
3140 if (__malloc_initialized < 0)
3141 ptmalloc_init ();
3142
3143 void *address = RETURN_ADDRESS (0);
3144 size_t pagesize = GLRO (dl_pagesize);
3145 return _mid_memalign (pagesize, bytes, address);
3146}
3147
3148void *
3149__libc_pvalloc (size_t bytes)
3150{
3151 if (__malloc_initialized < 0)
3152 ptmalloc_init ();
3153
3154 void *address = RETURN_ADDRESS (0);
3155 size_t pagesize = GLRO (dl_pagesize);
3156 size_t rounded_bytes = ALIGN_UP (bytes, pagesize);
3157
3158 /* Check for overflow. */
3159 if (bytes > SIZE_MAX - 2 * pagesize - MINSIZE)
3160 {
3161 __set_errno (ENOMEM);
3162 return 0;
3163 }
3164
3165 return _mid_memalign (pagesize, rounded_bytes, address);
3166}
3167
3168void *
3169__libc_calloc (size_t n, size_t elem_size)
3170{
3171 mstate av;
3172 mchunkptr oldtop, p;
3173 INTERNAL_SIZE_T bytes, sz, csz, oldtopsize;
3174 void *mem;
3175 unsigned long clearsize;
3176 unsigned long nclears;
3177 INTERNAL_SIZE_T *d;
3178
3179 /* size_t is unsigned so the behavior on overflow is defined. */
3180 bytes = n * elem_size;
3181#define HALF_INTERNAL_SIZE_T \
3182 (((INTERNAL_SIZE_T) 1) << (8 * sizeof (INTERNAL_SIZE_T) / 2))
3183 if (__builtin_expect ((n | elem_size) >= HALF_INTERNAL_SIZE_T, 0))
3184 {
3185 if (elem_size != 0 && bytes / elem_size != n)
3186 {
3187 __set_errno (ENOMEM);
3188 return 0;
3189 }
3190 }
3191
3192 void *(*hook) (size_t, const void *) =
3193 atomic_forced_read (__malloc_hook);
3194 if (__builtin_expect (hook != NULL, 0))
3195 {
3196 sz = bytes;
3197 mem = (*hook)(sz, RETURN_ADDRESS (0));
3198 if (mem == 0)
3199 return 0;
3200
3201 return memset (mem, 0, sz);
3202 }
3203
3204 sz = bytes;
3205
3206 arena_get (av, sz);
3207 if (av)
3208 {
3209 /* Check if we hand out the top chunk, in which case there may be no
3210 need to clear. */
3211#if MORECORE_CLEARS
3212 oldtop = top (av);
3213 oldtopsize = chunksize (top (av));
3214# if MORECORE_CLEARS < 2
3215 /* Only newly allocated memory is guaranteed to be cleared. */
3216 if (av == &main_arena &&
3217 oldtopsize < mp_.sbrk_base + av->max_system_mem - (char *) oldtop)
3218 oldtopsize = (mp_.sbrk_base + av->max_system_mem - (char *) oldtop);
3219# endif
3220 if (av != &main_arena)
3221 {
3222 heap_info *heap = heap_for_ptr (oldtop);
3223 if (oldtopsize < (char *) heap + heap->mprotect_size - (char *) oldtop)
3224 oldtopsize = (char *) heap + heap->mprotect_size - (char *) oldtop;
3225 }
3226#endif
3227 }
3228 else
3229 {
3230 /* No usable arenas. */
3231 oldtop = 0;
3232 oldtopsize = 0;
3233 }
3234 mem = _int_malloc (av, sz);
3235
3236
3237 assert (!mem || chunk_is_mmapped (mem2chunk (mem)) ||
3238 av == arena_for_chunk (mem2chunk (mem)));
3239
3240 if (mem == 0 && av != NULL)
3241 {
3242 LIBC_PROBE (memory_calloc_retry, 1, sz);
3243 av = arena_get_retry (av, sz);
3244 mem = _int_malloc (av, sz);
3245 }
3246
3247 if (av != NULL)
3248 (void) mutex_unlock (&av->mutex);
3249
3250 /* Allocation failed even after a retry. */
3251 if (mem == 0)
3252 return 0;
3253
3254 p = mem2chunk (mem);
3255
3256 /* Two optional cases in which clearing not necessary */
3257 if (chunk_is_mmapped (p))
3258 {
3259 if (__builtin_expect (perturb_byte, 0))
3260 return memset (mem, 0, sz);
3261
3262 return mem;
3263 }
3264
3265 csz = chunksize (p);
3266
3267#if MORECORE_CLEARS
3268 if (perturb_byte == 0 && (p == oldtop && csz > oldtopsize))
3269 {
3270 /* clear only the bytes from non-freshly-sbrked memory */
3271 csz = oldtopsize;
3272 }
3273#endif
3274
3275 /* Unroll clear of <= 36 bytes (72 if 8byte sizes). We know that
3276 contents have an odd number of INTERNAL_SIZE_T-sized words;
3277 minimally 3. */
3278 d = (INTERNAL_SIZE_T *) mem;
3279 clearsize = csz - SIZE_SZ;
3280 nclears = clearsize / sizeof (INTERNAL_SIZE_T);
3281 assert (nclears >= 3);
3282
3283 if (nclears > 9)
3284 return memset (d, 0, clearsize);
3285
3286 else
3287 {
3288 *(d + 0) = 0;
3289 *(d + 1) = 0;
3290 *(d + 2) = 0;
3291 if (nclears > 4)
3292 {
3293 *(d + 3) = 0;
3294 *(d + 4) = 0;
3295 if (nclears > 6)
3296 {
3297 *(d + 5) = 0;
3298 *(d + 6) = 0;
3299 if (nclears > 8)
3300 {
3301 *(d + 7) = 0;
3302 *(d + 8) = 0;
3303 }
3304 }
3305 }
3306 }
3307
3308 return mem;
3309}
3310
3311/*
3312 ------------------------------ malloc ------------------------------
3313 */
3314
3315static void *
3316_int_malloc (mstate av, size_t bytes)
3317{
3318 INTERNAL_SIZE_T nb; /* normalized request size */
3319 unsigned int idx; /* associated bin index */
3320 mbinptr bin; /* associated bin */
3321
3322 mchunkptr victim; /* inspected/selected chunk */
3323 INTERNAL_SIZE_T size; /* its size */
3324 int victim_index; /* its bin index */
3325
3326 mchunkptr remainder; /* remainder from a split */
3327 unsigned long remainder_size; /* its size */
3328
3329 unsigned int block; /* bit map traverser */
3330 unsigned int bit; /* bit map traverser */
3331 unsigned int map; /* current word of binmap */
3332
3333 mchunkptr fwd; /* misc temp for linking */
3334 mchunkptr bck; /* misc temp for linking */
3335
3336 const char *errstr = NULL;
3337
3338 /*
3339 Convert request size to internal form by adding SIZE_SZ bytes
3340 overhead plus possibly more to obtain necessary alignment and/or
3341 to obtain a size of at least MINSIZE, the smallest allocatable
3342 size. Also, checked_request2size traps (returning 0) request sizes
3343 that are so large that they wrap around zero when padded and
3344 aligned.
3345 */
3346
3347 checked_request2size (bytes, nb);
3348
3349 /* There are no usable arenas. Fall back to sysmalloc to get a chunk from
3350 mmap. */
3351 if (__glibc_unlikely (av == NULL))
3352 {
3353 void *p = sysmalloc (nb, av);
3354 if (p != NULL)
3355 alloc_perturb (p, bytes);
3356 return p;
3357 }
3358
3359 /*
3360 If the size qualifies as a fastbin, first check corresponding bin.
3361 This code is safe to execute even if av is not yet initialized, so we
3362 can try it without checking, which saves some time on this fast path.
3363 */
3364
3365 if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
3366 {
3367 idx = fastbin_index (nb);
3368 mfastbinptr *fb = &fastbin (av, idx);
3369 mchunkptr pp = *fb;
3370 do
3371 {
3372 victim = pp;
3373 if (victim == NULL)
3374 break;
3375 }
3376 while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
3377 != victim);
3378 if (victim != 0)
3379 {
3380 if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
3381 {
3382 errstr = "malloc(): memory corruption (fast)";
3383 errout:
3384 malloc_printerr (check_action, errstr, chunk2mem (victim), av);
3385 return NULL;
3386 }
3387 check_remalloced_chunk (av, victim, nb);
3388 void *p = chunk2mem (victim);
3389 alloc_perturb (p, bytes);
3390 return p;
3391 }
3392 }
3393
3394 /*
3395 If a small request, check regular bin. Since these "smallbins"
3396 hold one size each, no searching within bins is necessary.
3397 (For a large request, we need to wait until unsorted chunks are
3398 processed to find best fit. But for small ones, fits are exact
3399 anyway, so we can check now, which is faster.)
3400 */
3401
3402 if (in_smallbin_range (nb))
3403 {
3404 idx = smallbin_index (nb);
3405 bin = bin_at (av, idx);
3406
3407 if ((victim = last (bin)) != bin)
3408 {
3409 if (victim == 0) /* initialization check */
3410 malloc_consolidate (av);
3411 else
3412 {
3413 bck = victim->bk;
3414 if (__glibc_unlikely (bck->fd != victim))
3415 {
3416 errstr = "malloc(): smallbin double linked list corrupted";
3417 goto errout;
3418 }
3419 set_inuse_bit_at_offset (victim, nb);
3420 bin->bk = bck;
3421 bck->fd = bin;
3422
3423 if (av != &main_arena)
3424 victim->size |= NON_MAIN_ARENA;
3425 check_malloced_chunk (av, victim, nb);
3426 void *p = chunk2mem (victim);
3427 alloc_perturb (p, bytes);
3428 return p;
3429 }
3430 }
3431 }
3432
3433 /*
3434 If this is a large request, consolidate fastbins before continuing.
3435 While it might look excessive to kill all fastbins before
3436 even seeing if there is space available, this avoids
3437 fragmentation problems normally associated with fastbins.
3438 Also, in practice, programs tend to have runs of either small or
3439 large requests, but less often mixtures, so consolidation is not
3440 invoked all that often in most programs. And the programs that
3441 it is called frequently in otherwise tend to fragment.
3442 */
3443
3444 else
3445 {
3446 idx = largebin_index (nb);
3447 if (have_fastchunks (av))
3448 malloc_consolidate (av);
3449 }
3450
3451 /*
3452 Process recently freed or remaindered chunks, taking one only if
3453 it is exact fit, or, if this a small request, the chunk is remainder from
3454 the most recent non-exact fit. Place other traversed chunks in
3455 bins. Note that this step is the only place in any routine where
3456 chunks are placed in bins.
3457
3458 The outer loop here is needed because we might not realize until
3459 near the end of malloc that we should have consolidated, so must
3460 do so and retry. This happens at most once, and only when we would
3461 otherwise need to expand memory to service a "small" request.
3462 */
3463
3464 for (;; )
3465 {
3466 int iters = 0;
3467 while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
3468 {
3469 bck = victim->bk;
3470 if (__builtin_expect (victim->size <= 2 * SIZE_SZ, 0)
3471 || __builtin_expect (victim->size > av->system_mem, 0))
3472 malloc_printerr (check_action, "malloc(): memory corruption",
3473 chunk2mem (victim), av);
3474 size = chunksize (victim);
3475
3476 /*
3477 If a small request, try to use last remainder if it is the
3478 only chunk in unsorted bin. This helps promote locality for
3479 runs of consecutive small requests. This is the only
3480 exception to best-fit, and applies only when there is
3481 no exact fit for a small chunk.
3482 */
3483
3484 if (in_smallbin_range (nb) &&
3485 bck == unsorted_chunks (av) &&
3486 victim == av->last_remainder &&
3487 (unsigned long) (size) > (unsigned long) (nb + MINSIZE))
3488 {
3489 /* split and reattach remainder */
3490 remainder_size = size - nb;
3491 remainder = chunk_at_offset (victim, nb);
3492 unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
3493 av->last_remainder = remainder;
3494 remainder->bk = remainder->fd = unsorted_chunks (av);
3495 if (!in_smallbin_range (remainder_size))
3496 {
3497 remainder->fd_nextsize = NULL;
3498 remainder->bk_nextsize = NULL;
3499 }
3500
3501 set_head (victim, nb | PREV_INUSE |
3502 (av != &main_arena ? NON_MAIN_ARENA : 0));
3503 set_head (remainder, remainder_size | PREV_INUSE);
3504 set_foot (remainder, remainder_size);
3505
3506 check_malloced_chunk (av, victim, nb);
3507 void *p = chunk2mem (victim);
3508 alloc_perturb (p, bytes);
3509 return p;
3510 }
3511
3512 /* remove from unsorted list */
3513 unsorted_chunks (av)->bk = bck;
3514 bck->fd = unsorted_chunks (av);
3515
3516 /* Take now instead of binning if exact fit */
3517
3518 if (size == nb)
3519 {
3520 set_inuse_bit_at_offset (victim, size);
3521 if (av != &main_arena)
3522 victim->size |= NON_MAIN_ARENA;
3523 check_malloced_chunk (av, victim, nb);
3524 void *p = chunk2mem (victim);
3525 alloc_perturb (p, bytes);
3526 return p;
3527 }
3528
3529 /* place chunk in bin */
3530
3531 if (in_smallbin_range (size))
3532 {
3533 victim_index = smallbin_index (size);
3534 bck = bin_at (av, victim_index);
3535 fwd = bck->fd;
3536 }
3537 else
3538 {
3539 victim_index = largebin_index (size);
3540 bck = bin_at (av, victim_index);
3541 fwd = bck->fd;
3542
3543 /* maintain large bins in sorted order */
3544 if (fwd != bck)
3545 {
3546 /* Or with inuse bit to speed comparisons */
3547 size |= PREV_INUSE;
3548 /* if smaller than smallest, bypass loop below */
3549 assert ((bck->bk->size & NON_MAIN_ARENA) == 0);
3550 if ((unsigned long) (size) < (unsigned long) (bck->bk->size))
3551 {
3552 fwd = bck;
3553 bck = bck->bk;
3554
3555 victim->fd_nextsize = fwd->fd;
3556 victim->bk_nextsize = fwd->fd->bk_nextsize;
3557 fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
3558 }
3559 else
3560 {
3561 assert ((fwd->size & NON_MAIN_ARENA) == 0);
3562 while ((unsigned long) size < fwd->size)
3563 {
3564 fwd = fwd->fd_nextsize;
3565 assert ((fwd->size & NON_MAIN_ARENA) == 0);
3566 }
3567
3568 if ((unsigned long) size == (unsigned long) fwd->size)
3569 /* Always insert in the second position. */
3570 fwd = fwd->fd;
3571 else
3572 {
3573 victim->fd_nextsize = fwd;
3574 victim->bk_nextsize = fwd->bk_nextsize;
3575 fwd->bk_nextsize = victim;
3576 victim->bk_nextsize->fd_nextsize = victim;
3577 }
3578 bck = fwd->bk;
3579 }
3580 }
3581 else
3582 victim->fd_nextsize = victim->bk_nextsize = victim;
3583 }
3584
3585 mark_bin (av, victim_index);
3586 victim->bk = bck;
3587 victim->fd = fwd;
3588 fwd->bk = victim;
3589 bck->fd = victim;
3590
3591#define MAX_ITERS 10000
3592 if (++iters >= MAX_ITERS)
3593 break;
3594 }
3595
3596 /*
3597 If a large request, scan through the chunks of current bin in
3598 sorted order to find smallest that fits. Use the skip list for this.
3599 */
3600
3601 if (!in_smallbin_range (nb))
3602 {
3603 bin = bin_at (av, idx);
3604
3605 /* skip scan if empty or largest chunk is too small */
3606 if ((victim = first (bin)) != bin &&
3607 (unsigned long) (victim->size) >= (unsigned long) (nb))
3608 {
3609 victim = victim->bk_nextsize;
3610 while (((unsigned long) (size = chunksize (victim)) <
3611 (unsigned long) (nb)))
3612 victim = victim->bk_nextsize;
3613
3614 /* Avoid removing the first entry for a size so that the skip
3615 list does not have to be rerouted. */
3616 if (victim != last (bin) && victim->size == victim->fd->size)
3617 victim = victim->fd;
3618
3619 remainder_size = size - nb;
3620 unlink (av, victim, bck, fwd);
3621
3622 /* Exhaust */
3623 if (remainder_size < MINSIZE)
3624 {
3625 set_inuse_bit_at_offset (victim, size);
3626 if (av != &main_arena)
3627 victim->size |= NON_MAIN_ARENA;
3628 }
3629 /* Split */
3630 else
3631 {
3632 remainder = chunk_at_offset (victim, nb);
3633 /* We cannot assume the unsorted list is empty and therefore
3634 have to perform a complete insert here. */
3635 bck = unsorted_chunks (av);
3636 fwd = bck->fd;
3637 if (__glibc_unlikely (fwd->bk != bck))
3638 {
3639 errstr = "malloc(): corrupted unsorted chunks";
3640 goto errout;
3641 }
3642 remainder->bk = bck;
3643 remainder->fd = fwd;
3644 bck->fd = remainder;
3645 fwd->bk = remainder;
3646 if (!in_smallbin_range (remainder_size))
3647 {
3648 remainder->fd_nextsize = NULL;
3649 remainder->bk_nextsize = NULL;
3650 }
3651 set_head (victim, nb | PREV_INUSE |
3652 (av != &main_arena ? NON_MAIN_ARENA : 0));
3653 set_head (remainder, remainder_size | PREV_INUSE);
3654 set_foot (remainder, remainder_size);
3655 }
3656 check_malloced_chunk (av, victim, nb);
3657 void *p = chunk2mem (victim);
3658 alloc_perturb (p, bytes);
3659 return p;
3660 }
3661 }
3662
3663 /*
3664 Search for a chunk by scanning bins, starting with next largest
3665 bin. This search is strictly by best-fit; i.e., the smallest
3666 (with ties going to approximately the least recently used) chunk
3667 that fits is selected.
3668
3669 The bitmap avoids needing to check that most blocks are nonempty.
3670 The particular case of skipping all bins during warm-up phases
3671 when no chunks have been returned yet is faster than it might look.
3672 */
3673
3674 ++idx;
3675 bin = bin_at (av, idx);
3676 block = idx2block (idx);
3677 map = av->binmap[block];
3678 bit = idx2bit (idx);
3679
3680 for (;; )
3681 {
3682 /* Skip rest of block if there are no more set bits in this block. */
3683 if (bit > map || bit == 0)
3684 {
3685 do
3686 {
3687 if (++block >= BINMAPSIZE) /* out of bins */
3688 goto use_top;
3689 }
3690 while ((map = av->binmap[block]) == 0);
3691
3692 bin = bin_at (av, (block << BINMAPSHIFT));
3693 bit = 1;
3694 }
3695
3696 /* Advance to bin with set bit. There must be one. */
3697 while ((bit & map) == 0)
3698 {
3699 bin = next_bin (bin);
3700 bit <<= 1;
3701 assert (bit != 0);
3702 }
3703
3704 /* Inspect the bin. It is likely to be non-empty */
3705 victim = last (bin);
3706
3707 /* If a false alarm (empty bin), clear the bit. */
3708 if (victim == bin)
3709 {
3710 av->binmap[block] = map &= ~bit; /* Write through */
3711 bin = next_bin (bin);
3712 bit <<= 1;
3713 }
3714
3715 else
3716 {
3717 size = chunksize (victim);
3718
3719 /* We know the first chunk in this bin is big enough to use. */
3720 assert ((unsigned long) (size) >= (unsigned long) (nb));
3721
3722 remainder_size = size - nb;
3723
3724 /* unlink */
3725 unlink (av, victim, bck, fwd);
3726
3727 /* Exhaust */
3728 if (remainder_size < MINSIZE)
3729 {
3730 set_inuse_bit_at_offset (victim, size);
3731 if (av != &main_arena)
3732 victim->size |= NON_MAIN_ARENA;
3733 }
3734
3735 /* Split */
3736 else
3737 {
3738 remainder = chunk_at_offset (victim, nb);
3739
3740 /* We cannot assume the unsorted list is empty and therefore
3741 have to perform a complete insert here. */
3742 bck = unsorted_chunks (av);
3743 fwd = bck->fd;
3744 if (__glibc_unlikely (fwd->bk != bck))
3745 {
3746 errstr = "malloc(): corrupted unsorted chunks 2";
3747 goto errout;
3748 }
3749 remainder->bk = bck;
3750 remainder->fd = fwd;
3751 bck->fd = remainder;
3752 fwd->bk = remainder;
3753
3754 /* advertise as last remainder */
3755 if (in_smallbin_range (nb))
3756 av->last_remainder = remainder;
3757 if (!in_smallbin_range (remainder_size))
3758 {
3759 remainder->fd_nextsize = NULL;
3760 remainder->bk_nextsize = NULL;
3761 }
3762 set_head (victim, nb | PREV_INUSE |
3763 (av != &main_arena ? NON_MAIN_ARENA : 0));
3764 set_head (remainder, remainder_size | PREV_INUSE);
3765 set_foot (remainder, remainder_size);
3766 }
3767 check_malloced_chunk (av, victim, nb);
3768 void *p = chunk2mem (victim);
3769 alloc_perturb (p, bytes);
3770 return p;
3771 }
3772 }
3773
3774 use_top:
3775 /*
3776 If large enough, split off the chunk bordering the end of memory
3777 (held in av->top). Note that this is in accord with the best-fit
3778 search rule. In effect, av->top is treated as larger (and thus
3779 less well fitting) than any other available chunk since it can
3780 be extended to be as large as necessary (up to system
3781 limitations).
3782
3783 We require that av->top always exists (i.e., has size >=
3784 MINSIZE) after initialization, so if it would otherwise be
3785 exhausted by current request, it is replenished. (The main
3786 reason for ensuring it exists is that we may need MINSIZE space
3787 to put in fenceposts in sysmalloc.)
3788 */
3789
3790 victim = av->top;
3791 size = chunksize (victim);
3792
3793 if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
3794 {
3795 remainder_size = size - nb;
3796 remainder = chunk_at_offset (victim, nb);
3797 av->top = remainder;
3798 set_head (victim, nb | PREV_INUSE |
3799 (av != &main_arena ? NON_MAIN_ARENA : 0));
3800 set_head (remainder, remainder_size | PREV_INUSE);
3801
3802 check_malloced_chunk (av, victim, nb);
3803 void *p = chunk2mem (victim);
3804 alloc_perturb (p, bytes);
3805 return p;
3806 }
3807
3808 /* When we are using atomic ops to free fast chunks we can get
3809 here for all block sizes. */
3810 else if (have_fastchunks (av))
3811 {
3812 malloc_consolidate (av);
3813 /* restore original bin index */
3814 if (in_smallbin_range (nb))
3815 idx = smallbin_index (nb);
3816 else
3817 idx = largebin_index (nb);
3818 }
3819
3820 /*
3821 Otherwise, relay to handle system-dependent cases
3822 */
3823 else
3824 {
3825 void *p = sysmalloc (nb, av);
3826 if (p != NULL)
3827 alloc_perturb (p, bytes);
3828 return p;
3829 }
3830 }
3831}
3832
3833/*
3834 ------------------------------ free ------------------------------
3835 */
3836
3837static void
3838_int_free (mstate av, mchunkptr p, int have_lock)
3839{
3840 INTERNAL_SIZE_T size; /* its size */
3841 mfastbinptr *fb; /* associated fastbin */
3842 mchunkptr nextchunk; /* next contiguous chunk */
3843 INTERNAL_SIZE_T nextsize; /* its size */
3844 int nextinuse; /* true if nextchunk is used */
3845 INTERNAL_SIZE_T prevsize; /* size of previous contiguous chunk */
3846 mchunkptr bck; /* misc temp for linking */
3847 mchunkptr fwd; /* misc temp for linking */
3848
3849 const char *errstr = NULL;
3850 int locked = 0;
3851
3852 size = chunksize (p);
3853
3854 /* Little security check which won't hurt performance: the
3855 allocator never wrapps around at the end of the address space.
3856 Therefore we can exclude some size values which might appear
3857 here by accident or by "design" from some intruder. */
3858 if (__builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0)
3859 || __builtin_expect (misaligned_chunk (p), 0))
3860 {
3861 errstr = "free(): invalid pointer";
3862 errout:
3863 if (!have_lock && locked)
3864 (void) mutex_unlock (&av->mutex);
3865 malloc_printerr (check_action, errstr, chunk2mem (p), av);
3866 return;
3867 }
3868 /* We know that each chunk is at least MINSIZE bytes in size or a
3869 multiple of MALLOC_ALIGNMENT. */
3870 if (__glibc_unlikely (size < MINSIZE || !aligned_OK (size)))
3871 {
3872 errstr = "free(): invalid size";
3873 goto errout;
3874 }
3875
3876 check_inuse_chunk(av, p);
3877
3878 /*
3879 If eligible, place chunk on a fastbin so it can be found
3880 and used quickly in malloc.
3881 */
3882
3883 if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())
3884
3885#if TRIM_FASTBINS
3886 /*
3887 If TRIM_FASTBINS set, don't place chunks
3888 bordering top into fastbins
3889 */
3890 && (chunk_at_offset(p, size) != av->top)
3891#endif
3892 ) {
3893
3894 if (__builtin_expect (chunk_at_offset (p, size)->size <= 2 * SIZE_SZ, 0)
3895 || __builtin_expect (chunksize (chunk_at_offset (p, size))
3896 >= av->system_mem, 0))
3897 {
3898 /* We might not have a lock at this point and concurrent modifications
3899 of system_mem might have let to a false positive. Redo the test
3900 after getting the lock. */
3901 if (have_lock
3902 || ({ assert (locked == 0);
3903 mutex_lock(&av->mutex);
3904 locked = 1;
3905 chunk_at_offset (p, size)->size <= 2 * SIZE_SZ
3906 || chunksize (chunk_at_offset (p, size)) >= av->system_mem;
3907 }))
3908 {
3909 errstr = "free(): invalid next size (fast)";
3910 goto errout;
3911 }
3912 if (! have_lock)
3913 {
3914 (void)mutex_unlock(&av->mutex);
3915 locked = 0;
3916 }
3917 }
3918
3919 free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
3920
3921 set_fastchunks(av);
3922 unsigned int idx = fastbin_index(size);
3923 fb = &fastbin (av, idx);
3924
3925 /* Atomically link P to its fastbin: P->FD = *FB; *FB = P; */
3926 mchunkptr old = *fb, old2;
3927 unsigned int old_idx = ~0u;
3928 do
3929 {
3930 /* Check that the top of the bin is not the record we are going to add
3931 (i.e., double free). */
3932 if (__builtin_expect (old == p, 0))
3933 {
3934 errstr = "double free or corruption (fasttop)";
3935 goto errout;
3936 }
3937 /* Check that size of fastbin chunk at the top is the same as
3938 size of the chunk that we are adding. We can dereference OLD
3939 only if we have the lock, otherwise it might have already been
3940 deallocated. See use of OLD_IDX below for the actual check. */
3941 if (have_lock && old != NULL)
3942 old_idx = fastbin_index(chunksize(old));
3943 p->fd = old2 = old;
3944 }
3945 while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2);
3946
3947 if (have_lock && old != NULL && __builtin_expect (old_idx != idx, 0))
3948 {
3949 errstr = "invalid fastbin entry (free)";
3950 goto errout;
3951 }
3952 }
3953
3954 /*
3955 Consolidate other non-mmapped chunks as they arrive.
3956 */
3957
3958 else if (!chunk_is_mmapped(p)) {
3959 if (! have_lock) {
3960 (void)mutex_lock(&av->mutex);
3961 locked = 1;
3962 }
3963
3964 nextchunk = chunk_at_offset(p, size);
3965
3966 /* Lightweight tests: check whether the block is already the
3967 top block. */
3968 if (__glibc_unlikely (p == av->top))
3969 {
3970 errstr = "double free or corruption (top)";
3971 goto errout;
3972 }
3973 /* Or whether the next chunk is beyond the boundaries of the arena. */
3974 if (__builtin_expect (contiguous (av)
3975 && (char *) nextchunk
3976 >= ((char *) av->top + chunksize(av->top)), 0))
3977 {
3978 errstr = "double free or corruption (out)";
3979 goto errout;
3980 }
3981 /* Or whether the block is actually not marked used. */
3982 if (__glibc_unlikely (!prev_inuse(nextchunk)))
3983 {
3984 errstr = "double free or corruption (!prev)";
3985 goto errout;
3986 }
3987
3988 nextsize = chunksize(nextchunk);
3989 if (__builtin_expect (nextchunk->size <= 2 * SIZE_SZ, 0)
3990 || __builtin_expect (nextsize >= av->system_mem, 0))
3991 {
3992 errstr = "free(): invalid next size (normal)";
3993 goto errout;
3994 }
3995
3996 free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
3997
3998 /* consolidate backward */
3999 if (!prev_inuse(p)) {
4000 prevsize = p->prev_size;
4001 size += prevsize;
4002 p = chunk_at_offset(p, -((long) prevsize));
4003 unlink(av, p, bck, fwd);
4004 }
4005
4006 if (nextchunk != av->top) {
4007 /* get and clear inuse bit */
4008 nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
4009
4010 /* consolidate forward */
4011 if (!nextinuse) {
4012 unlink(av, nextchunk, bck, fwd);
4013 size += nextsize;
4014 } else
4015 clear_inuse_bit_at_offset(nextchunk, 0);
4016
4017 /*
4018 Place the chunk in unsorted chunk list. Chunks are
4019 not placed into regular bins until after they have
4020 been given one chance to be used in malloc.
4021 */
4022
4023 bck = unsorted_chunks(av);
4024 fwd = bck->fd;
4025 if (__glibc_unlikely (fwd->bk != bck))
4026 {
4027 errstr = "free(): corrupted unsorted chunks";
4028 goto errout;
4029 }
4030 p->fd = fwd;
4031 p->bk = bck;
4032 if (!in_smallbin_range(size))
4033 {
4034 p->fd_nextsize = NULL;
4035 p->bk_nextsize = NULL;
4036 }
4037 bck->fd = p;
4038 fwd->bk = p;
4039
4040 set_head(p, size | PREV_INUSE);
4041 set_foot(p, size);
4042
4043 check_free_chunk(av, p);
4044 }
4045
4046 /*
4047 If the chunk borders the current high end of memory,
4048 consolidate into top
4049 */
4050
4051 else {
4052 size += nextsize;
4053 set_head(p, size | PREV_INUSE);
4054 av->top = p;
4055 check_chunk(av, p);
4056 }
4057
4058 /*
4059 If freeing a large space, consolidate possibly-surrounding
4060 chunks. Then, if the total unused topmost memory exceeds trim
4061 threshold, ask malloc_trim to reduce top.
4062
4063 Unless max_fast is 0, we don't know if there are fastbins
4064 bordering top, so we cannot tell for sure whether threshold
4065 has been reached unless fastbins are consolidated. But we
4066 don't want to consolidate on each free. As a compromise,
4067 consolidation is performed if FASTBIN_CONSOLIDATION_THRESHOLD
4068 is reached.
4069 */
4070
4071 if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
4072 if (have_fastchunks(av))
4073 malloc_consolidate(av);
4074
4075 if (av == &main_arena) {
4076#ifndef MORECORE_CANNOT_TRIM
4077 if ((unsigned long)(chunksize(av->top)) >=
4078 (unsigned long)(mp_.trim_threshold))
4079 systrim(mp_.top_pad, av);
4080#endif
4081 } else {
4082 /* Always try heap_trim(), even if the top chunk is not
4083 large, because the corresponding heap might go away. */
4084 heap_info *heap = heap_for_ptr(top(av));
4085
4086 assert(heap->ar_ptr == av);
4087 heap_trim(heap, mp_.top_pad);
4088 }
4089 }
4090
4091 if (! have_lock) {
4092 assert (locked);
4093 (void)mutex_unlock(&av->mutex);
4094 }
4095 }
4096 /*
4097 If the chunk was allocated via mmap, release via munmap().
4098 */
4099
4100 else {
4101 munmap_chunk (p);
4102 }
4103}
4104
4105/*
4106 ------------------------- malloc_consolidate -------------------------
4107
4108 malloc_consolidate is a specialized version of free() that tears
4109 down chunks held in fastbins. Free itself cannot be used for this
4110 purpose since, among other things, it might place chunks back onto
4111 fastbins. So, instead, we need to use a minor variant of the same
4112 code.
4113
4114 Also, because this routine needs to be called the first time through
4115 malloc anyway, it turns out to be the perfect place to trigger
4116 initialization code.
4117*/
4118
4119static void malloc_consolidate(mstate av)
4120{
4121 mfastbinptr* fb; /* current fastbin being consolidated */
4122 mfastbinptr* maxfb; /* last fastbin (for loop control) */
4123 mchunkptr p; /* current chunk being consolidated */
4124 mchunkptr nextp; /* next chunk to consolidate */
4125 mchunkptr unsorted_bin; /* bin header */
4126 mchunkptr first_unsorted; /* chunk to link to */
4127
4128 /* These have same use as in free() */
4129 mchunkptr nextchunk;
4130 INTERNAL_SIZE_T size;
4131 INTERNAL_SIZE_T nextsize;
4132 INTERNAL_SIZE_T prevsize;
4133 int nextinuse;
4134 mchunkptr bck;
4135 mchunkptr fwd;
4136
4137 /*
4138 If max_fast is 0, we know that av hasn't
4139 yet been initialized, in which case do so below
4140 */
4141
4142 if (get_max_fast () != 0) {
4143 clear_fastchunks(av);
4144
4145 unsorted_bin = unsorted_chunks(av);
4146
4147 /*
4148 Remove each chunk from fast bin and consolidate it, placing it
4149 then in unsorted bin. Among other reasons for doing this,
4150 placing in unsorted bin avoids needing to calculate actual bins
4151 until malloc is sure that chunks aren't immediately going to be
4152 reused anyway.
4153 */
4154
4155 maxfb = &fastbin (av, NFASTBINS - 1);
4156 fb = &fastbin (av, 0);
4157 do {
4158 p = atomic_exchange_acq (fb, 0);
4159 if (p != 0) {
4160 do {
4161 check_inuse_chunk(av, p);
4162 nextp = p->fd;
4163
4164 /* Slightly streamlined version of consolidation code in free() */
4165 size = p->size & ~(PREV_INUSE|NON_MAIN_ARENA);
4166 nextchunk = chunk_at_offset(p, size);
4167 nextsize = chunksize(nextchunk);
4168
4169 if (!prev_inuse(p)) {
4170 prevsize = p->prev_size;
4171 size += prevsize;
4172 p = chunk_at_offset(p, -((long) prevsize));
4173 unlink(av, p, bck, fwd);
4174 }
4175
4176 if (nextchunk != av->top) {
4177 nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
4178
4179 if (!nextinuse) {
4180 size += nextsize;
4181 unlink(av, nextchunk, bck, fwd);
4182 } else
4183 clear_inuse_bit_at_offset(nextchunk, 0);
4184
4185 first_unsorted = unsorted_bin->fd;
4186 unsorted_bin->fd = p;
4187 first_unsorted->bk = p;
4188
4189 if (!in_smallbin_range (size)) {
4190 p->fd_nextsize = NULL;
4191 p->bk_nextsize = NULL;
4192 }
4193
4194 set_head(p, size | PREV_INUSE);
4195 p->bk = unsorted_bin;
4196 p->fd = first_unsorted;
4197 set_foot(p, size);
4198 }
4199
4200 else {
4201 size += nextsize;
4202 set_head(p, size | PREV_INUSE);
4203 av->top = p;
4204 }
4205
4206 } while ( (p = nextp) != 0);
4207
4208 }
4209 } while (fb++ != maxfb);
4210 }
4211 else {
4212 malloc_init_state(av);
4213 check_malloc_state(av);
4214 }
4215}
4216
4217/*
4218 ------------------------------ realloc ------------------------------
4219*/
4220
4221void*
4222_int_realloc(mstate av, mchunkptr oldp, INTERNAL_SIZE_T oldsize,
4223 INTERNAL_SIZE_T nb)
4224{
4225 mchunkptr newp; /* chunk to return */
4226 INTERNAL_SIZE_T newsize; /* its size */
4227 void* newmem; /* corresponding user mem */
4228
4229 mchunkptr next; /* next contiguous chunk after oldp */
4230
4231 mchunkptr remainder; /* extra space at end of newp */
4232 unsigned long remainder_size; /* its size */
4233
4234 mchunkptr bck; /* misc temp for linking */
4235 mchunkptr fwd; /* misc temp for linking */
4236
4237 unsigned long copysize; /* bytes to copy */
4238 unsigned int ncopies; /* INTERNAL_SIZE_T words to copy */
4239 INTERNAL_SIZE_T* s; /* copy source */
4240 INTERNAL_SIZE_T* d; /* copy destination */
4241
4242 const char *errstr = NULL;
4243
4244 /* oldmem size */
4245 if (__builtin_expect (oldp->size <= 2 * SIZE_SZ, 0)
4246 || __builtin_expect (oldsize >= av->system_mem, 0))
4247 {
4248 errstr = "realloc(): invalid old size";
4249 errout:
4250 malloc_printerr (check_action, errstr, chunk2mem (oldp), av);
4251 return NULL;
4252 }
4253
4254 check_inuse_chunk (av, oldp);
4255
4256 /* All callers already filter out mmap'ed chunks. */
4257 assert (!chunk_is_mmapped (oldp));
4258
4259 next = chunk_at_offset (oldp, oldsize);
4260 INTERNAL_SIZE_T nextsize = chunksize (next);
4261 if (__builtin_expect (next->size <= 2 * SIZE_SZ, 0)
4262 || __builtin_expect (nextsize >= av->system_mem, 0))
4263 {
4264 errstr = "realloc(): invalid next size";
4265 goto errout;
4266 }
4267
4268 if ((unsigned long) (oldsize) >= (unsigned long) (nb))
4269 {
4270 /* already big enough; split below */
4271 newp = oldp;
4272 newsize = oldsize;
4273 }
4274
4275 else
4276 {
4277 /* Try to expand forward into top */
4278 if (next == av->top &&
4279 (unsigned long) (newsize = oldsize + nextsize) >=
4280 (unsigned long) (nb + MINSIZE))
4281 {
4282 set_head_size (oldp, nb | (av != &main_arena ? NON_MAIN_ARENA : 0));
4283 av->top = chunk_at_offset (oldp, nb);
4284 set_head (av->top, (newsize - nb) | PREV_INUSE);
4285 check_inuse_chunk (av, oldp);
4286 return chunk2mem (oldp);
4287 }
4288
4289 /* Try to expand forward into next chunk; split off remainder below */
4290 else if (next != av->top &&
4291 !inuse (next) &&
4292 (unsigned long) (newsize = oldsize + nextsize) >=
4293 (unsigned long) (nb))
4294 {
4295 newp = oldp;
4296 unlink (av, next, bck, fwd);
4297 }
4298
4299 /* allocate, copy, free */
4300 else
4301 {
4302 newmem = _int_malloc (av, nb - MALLOC_ALIGN_MASK);
4303 if (newmem == 0)
4304 return 0; /* propagate failure */
4305
4306 newp = mem2chunk (newmem);
4307 newsize = chunksize (newp);
4308
4309 /*
4310 Avoid copy if newp is next chunk after oldp.
4311 */
4312 if (newp == next)
4313 {
4314 newsize += oldsize;
4315 newp = oldp;
4316 }
4317 else
4318 {
4319 /*
4320 Unroll copy of <= 36 bytes (72 if 8byte sizes)
4321 We know that contents have an odd number of
4322 INTERNAL_SIZE_T-sized words; minimally 3.
4323 */
4324
4325 copysize = oldsize - SIZE_SZ;
4326 s = (INTERNAL_SIZE_T *) (chunk2mem (oldp));
4327 d = (INTERNAL_SIZE_T *) (newmem);
4328 ncopies = copysize / sizeof (INTERNAL_SIZE_T);
4329 assert (ncopies >= 3);
4330
4331 if (ncopies > 9)
4332 memcpy (d, s, copysize);
4333
4334 else
4335 {
4336 *(d + 0) = *(s + 0);
4337 *(d + 1) = *(s + 1);
4338 *(d + 2) = *(s + 2);
4339 if (ncopies > 4)
4340 {
4341 *(d + 3) = *(s + 3);
4342 *(d + 4) = *(s + 4);
4343 if (ncopies > 6)
4344 {
4345 *(d + 5) = *(s + 5);
4346 *(d + 6) = *(s + 6);
4347 if (ncopies > 8)
4348 {
4349 *(d + 7) = *(s + 7);
4350 *(d + 8) = *(s + 8);
4351 }
4352 }
4353 }
4354 }
4355
4356 _int_free (av, oldp, 1);
4357 check_inuse_chunk (av, newp);
4358 return chunk2mem (newp);
4359 }
4360 }
4361 }
4362
4363 /* If possible, free extra space in old or extended chunk */
4364
4365 assert ((unsigned long) (newsize) >= (unsigned long) (nb));
4366
4367 remainder_size = newsize - nb;
4368
4369 if (remainder_size < MINSIZE) /* not enough extra to split off */
4370 {
4371 set_head_size (newp, newsize | (av != &main_arena ? NON_MAIN_ARENA : 0));
4372 set_inuse_bit_at_offset (newp, newsize);
4373 }
4374 else /* split remainder */
4375 {
4376 remainder = chunk_at_offset (newp, nb);
4377 set_head_size (newp, nb | (av != &main_arena ? NON_MAIN_ARENA : 0));
4378 set_head (remainder, remainder_size | PREV_INUSE |
4379 (av != &main_arena ? NON_MAIN_ARENA : 0));
4380 /* Mark remainder as inuse so free() won't complain */
4381 set_inuse_bit_at_offset (remainder, remainder_size);
4382 _int_free (av, remainder, 1);
4383 }
4384
4385 check_inuse_chunk (av, newp);
4386 return chunk2mem (newp);
4387}
4388
4389/*
4390 ------------------------------ memalign ------------------------------
4391 */
4392
4393static void *
4394_int_memalign (mstate av, size_t alignment, size_t bytes)
4395{
4396 INTERNAL_SIZE_T nb; /* padded request size */
4397 char *m; /* memory returned by malloc call */
4398 mchunkptr p; /* corresponding chunk */
4399 char *brk; /* alignment point within p */
4400 mchunkptr newp; /* chunk to return */
4401 INTERNAL_SIZE_T newsize; /* its size */
4402 INTERNAL_SIZE_T leadsize; /* leading space before alignment point */
4403 mchunkptr remainder; /* spare room at end to split off */
4404 unsigned long remainder_size; /* its size */
4405 INTERNAL_SIZE_T size;
4406
4407
4408
4409 checked_request2size (bytes, nb);
4410
4411 /*
4412 Strategy: find a spot within that chunk that meets the alignment
4413 request, and then possibly free the leading and trailing space.
4414 */
4415
4416
4417 /* Call malloc with worst case padding to hit alignment. */
4418
4419 m = (char *) (_int_malloc (av, nb + alignment + MINSIZE));
4420
4421 if (m == 0)
4422 return 0; /* propagate failure */
4423
4424 p = mem2chunk (m);
4425
4426 if ((((unsigned long) (m)) % alignment) != 0) /* misaligned */
4427
4428 { /*
4429 Find an aligned spot inside chunk. Since we need to give back
4430 leading space in a chunk of at least MINSIZE, if the first
4431 calculation places us at a spot with less than MINSIZE leader,
4432 we can move to the next aligned spot -- we've allocated enough
4433 total room so that this is always possible.
4434 */
4435 brk = (char *) mem2chunk (((unsigned long) (m + alignment - 1)) &
4436 - ((signed long) alignment));
4437 if ((unsigned long) (brk - (char *) (p)) < MINSIZE)
4438 brk += alignment;
4439
4440 newp = (mchunkptr) brk;
4441 leadsize = brk - (char *) (p);
4442 newsize = chunksize (p) - leadsize;
4443
4444 /* For mmapped chunks, just adjust offset */
4445 if (chunk_is_mmapped (p))
4446 {
4447 newp->prev_size = p->prev_size + leadsize;
4448 set_head (newp, newsize | IS_MMAPPED);
4449 return chunk2mem (newp);
4450 }
4451
4452 /* Otherwise, give back leader, use the rest */
4453 set_head (newp, newsize | PREV_INUSE |
4454 (av != &main_arena ? NON_MAIN_ARENA : 0));
4455 set_inuse_bit_at_offset (newp, newsize);
4456 set_head_size (p, leadsize | (av != &main_arena ? NON_MAIN_ARENA : 0));
4457 _int_free (av, p, 1);
4458 p = newp;
4459
4460 assert (newsize >= nb &&
4461 (((unsigned long) (chunk2mem (p))) % alignment) == 0);
4462 }
4463
4464 /* Also give back spare room at the end */
4465 if (!chunk_is_mmapped (p))
4466 {
4467 size = chunksize (p);
4468 if ((unsigned long) (size) > (unsigned long) (nb + MINSIZE))
4469 {
4470 remainder_size = size - nb;
4471 remainder = chunk_at_offset (p, nb);
4472 set_head (remainder, remainder_size | PREV_INUSE |
4473 (av != &main_arena ? NON_MAIN_ARENA : 0));
4474 set_head_size (p, nb);
4475 _int_free (av, remainder, 1);
4476 }
4477 }
4478
4479 check_inuse_chunk (av, p);
4480 return chunk2mem (p);
4481}
4482
4483
4484/*
4485 ------------------------------ malloc_trim ------------------------------
4486 */
4487
4488static int
4489mtrim (mstate av, size_t pad)
4490{
4491 /* Don't touch corrupt arenas. */
4492 if (arena_is_corrupt (av))
4493 return 0;
4494
4495 /* Ensure initialization/consolidation */
4496 malloc_consolidate (av);
4497
4498 const size_t ps = GLRO (dl_pagesize);
4499 int psindex = bin_index (ps);
4500 const size_t psm1 = ps - 1;
4501
4502 int result = 0;
4503 for (int i = 1; i < NBINS; ++i)
4504 if (i == 1 || i >= psindex)
4505 {
4506 mbinptr bin = bin_at (av, i);
4507
4508 for (mchunkptr p = last (bin); p != bin; p = p->bk)
4509 {
4510 INTERNAL_SIZE_T size = chunksize (p);
4511
4512 if (size > psm1 + sizeof (struct malloc_chunk))
4513 {
4514 /* See whether the chunk contains at least one unused page. */
4515 char *paligned_mem = (char *) (((uintptr_t) p
4516 + sizeof (struct malloc_chunk)
4517 + psm1) & ~psm1);
4518
4519 assert ((char *) chunk2mem (p) + 4 * SIZE_SZ <= paligned_mem);
4520 assert ((char *) p + size > paligned_mem);
4521
4522 /* This is the size we could potentially free. */
4523 size -= paligned_mem - (char *) p;
4524
4525 if (size > psm1)
4526 {
4527#if MALLOC_DEBUG
4528 /* When debugging we simulate destroying the memory
4529 content. */
4530 memset (paligned_mem, 0x89, size & ~psm1);
4531#endif
4532 __madvise (paligned_mem, size & ~psm1, MADV_DONTNEED);
4533
4534 result = 1;
4535 }
4536 }
4537 }
4538 }
4539
4540#ifndef MORECORE_CANNOT_TRIM
4541 return result | (av == &main_arena ? systrim (pad, av) : 0);
4542
4543#else
4544 return result;
4545#endif
4546}
4547
4548
4549int
4550__malloc_trim (size_t s)
4551{
4552 int result = 0;
4553
4554 if (__malloc_initialized < 0)
4555 ptmalloc_init ();
4556
4557 mstate ar_ptr = &main_arena;
4558 do
4559 {
4560 (void) mutex_lock (&ar_ptr->mutex);
4561 result |= mtrim (ar_ptr, s);
4562 (void) mutex_unlock (&ar_ptr->mutex);
4563
4564 ar_ptr = ar_ptr->next;
4565 }
4566 while (ar_ptr != &main_arena);
4567
4568 return result;
4569}
4570
4571
4572/*
4573 ------------------------- malloc_usable_size -------------------------
4574 */
4575
4576static size_t
4577musable (void *mem)
4578{
4579 mchunkptr p;
4580 if (mem != 0)
4581 {
4582 p = mem2chunk (mem);
4583
4584 if (__builtin_expect (using_malloc_checking == 1, 0))
4585 return malloc_check_get_size (p);
4586
4587 if (chunk_is_mmapped (p))
4588 return chunksize (p) - 2 * SIZE_SZ;
4589 else if (inuse (p))
4590 return chunksize (p) - SIZE_SZ;
4591 }
4592 return 0;
4593}
4594
4595
4596size_t
4597__malloc_usable_size (void *m)
4598{
4599 size_t result;
4600
4601 result = musable (m);
4602 return result;
4603}
4604
4605/*
4606 ------------------------------ mallinfo ------------------------------
4607 Accumulate malloc statistics for arena AV into M.
4608 */
4609
4610static void
4611int_mallinfo (mstate av, struct mallinfo *m)
4612{
4613 size_t i;
4614 mbinptr b;
4615 mchunkptr p;
4616 INTERNAL_SIZE_T avail;
4617 INTERNAL_SIZE_T fastavail;
4618 int nblocks;
4619 int nfastblocks;
4620
4621 /* Ensure initialization */
4622 if (av->top == 0)
4623 malloc_consolidate (av);
4624
4625 check_malloc_state (av);
4626
4627 /* Account for top */
4628 avail = chunksize (av->top);
4629 nblocks = 1; /* top always exists */
4630
4631 /* traverse fastbins */
4632 nfastblocks = 0;
4633 fastavail = 0;
4634
4635 for (i = 0; i < NFASTBINS; ++i)
4636 {
4637 for (p = fastbin (av, i); p != 0; p = p->fd)
4638 {
4639 ++nfastblocks;
4640 fastavail += chunksize (p);
4641 }
4642 }
4643
4644 avail += fastavail;
4645
4646 /* traverse regular bins */
4647 for (i = 1; i < NBINS; ++i)
4648 {
4649 b = bin_at (av, i);
4650 for (p = last (b); p != b; p = p->bk)
4651 {
4652 ++nblocks;
4653 avail += chunksize (p);
4654 }
4655 }
4656
4657 m->smblks += nfastblocks;
4658 m->ordblks += nblocks;
4659 m->fordblks += avail;
4660 m->uordblks += av->system_mem - avail;
4661 m->arena += av->system_mem;
4662 m->fsmblks += fastavail;
4663 if (av == &main_arena)
4664 {
4665 m->hblks = mp_.n_mmaps;
4666 m->hblkhd = mp_.mmapped_mem;
4667 m->usmblks = mp_.max_total_mem;
4668 m->keepcost = chunksize (av->top);
4669 }
4670}
4671
4672
4673struct mallinfo
4674__libc_mallinfo (void)
4675{
4676 struct mallinfo m;
4677 mstate ar_ptr;
4678
4679 if (__malloc_initialized < 0)
4680 ptmalloc_init ();
4681
4682 memset (&m, 0, sizeof (m));
4683 ar_ptr = &main_arena;
4684 do
4685 {
4686 (void) mutex_lock (&ar_ptr->mutex);
4687 int_mallinfo (ar_ptr, &m);
4688 (void) mutex_unlock (&ar_ptr->mutex);
4689
4690 ar_ptr = ar_ptr->next;
4691 }
4692 while (ar_ptr != &main_arena);
4693
4694 return m;
4695}
4696
4697/*
4698 ------------------------------ malloc_stats ------------------------------
4699 */
4700
4701void
4702__malloc_stats (void)
4703{
4704 int i;
4705 mstate ar_ptr;
4706 unsigned int in_use_b = mp_.mmapped_mem, system_b = in_use_b;
4707
4708 if (__malloc_initialized < 0)
4709 ptmalloc_init ();
4710 _IO_flockfile (stderr);
4711 int old_flags2 = ((_IO_FILE *) stderr)->_flags2;
4712 ((_IO_FILE *) stderr)->_flags2 |= _IO_FLAGS2_NOTCANCEL;
4713 for (i = 0, ar_ptr = &main_arena;; i++)
4714 {
4715 struct mallinfo mi;
4716
4717 memset (&mi, 0, sizeof (mi));
4718 (void) mutex_lock (&ar_ptr->mutex);
4719 int_mallinfo (ar_ptr, &mi);
4720 fprintf (stderr, "Arena %d:\n", i);
4721 fprintf (stderr, "system bytes = %10u\n", (unsigned int) mi.arena);
4722 fprintf (stderr, "in use bytes = %10u\n", (unsigned int) mi.uordblks);
4723#if MALLOC_DEBUG > 1
4724 if (i > 0)
4725 dump_heap (heap_for_ptr (top (ar_ptr)));
4726#endif
4727 system_b += mi.arena;
4728 in_use_b += mi.uordblks;
4729 (void) mutex_unlock (&ar_ptr->mutex);
4730 ar_ptr = ar_ptr->next;
4731 if (ar_ptr == &main_arena)
4732 break;
4733 }
4734 fprintf (stderr, "Total (incl. mmap):\n");
4735 fprintf (stderr, "system bytes = %10u\n", system_b);
4736 fprintf (stderr, "in use bytes = %10u\n", in_use_b);
4737 fprintf (stderr, "max mmap regions = %10u\n", (unsigned int) mp_.max_n_mmaps);
4738 fprintf (stderr, "max mmap bytes = %10lu\n",
4739 (unsigned long) mp_.max_mmapped_mem);
4740 ((_IO_FILE *) stderr)->_flags2 |= old_flags2;
4741 _IO_funlockfile (stderr);
4742}
4743
4744
4745/*
4746 ------------------------------ mallopt ------------------------------
4747 */
4748
4749int
4750__libc_mallopt (int param_number, int value)
4751{
4752 mstate av = &main_arena;
4753 int res = 1;
4754
4755 if (__malloc_initialized < 0)
4756 ptmalloc_init ();
4757 (void) mutex_lock (&av->mutex);
4758 /* Ensure initialization/consolidation */
4759 malloc_consolidate (av);
4760
4761 LIBC_PROBE (memory_mallopt, 2, param_number, value);
4762
4763 switch (param_number)
4764 {
4765 case M_MXFAST:
4766 if (value >= 0 && value <= MAX_FAST_SIZE)
4767 {
4768 LIBC_PROBE (memory_mallopt_mxfast, 2, value, get_max_fast ());
4769 set_max_fast (value);
4770 }
4771 else
4772 res = 0;
4773 break;
4774
4775 case M_TRIM_THRESHOLD:
4776 LIBC_PROBE (memory_mallopt_trim_threshold, 3, value,
4777 mp_.trim_threshold, mp_.no_dyn_threshold);
4778 mp_.trim_threshold = value;
4779 mp_.no_dyn_threshold = 1;
4780 break;
4781
4782 case M_TOP_PAD:
4783 LIBC_PROBE (memory_mallopt_top_pad, 3, value,
4784 mp_.top_pad, mp_.no_dyn_threshold);
4785 mp_.top_pad = value;
4786 mp_.no_dyn_threshold = 1;
4787 break;
4788
4789 case M_MMAP_THRESHOLD:
4790 /* Forbid setting the threshold too high. */
4791 if ((unsigned long) value > HEAP_MAX_SIZE / 2)
4792 res = 0;
4793 else
4794 {
4795 LIBC_PROBE (memory_mallopt_mmap_threshold, 3, value,
4796 mp_.mmap_threshold, mp_.no_dyn_threshold);
4797 mp_.mmap_threshold = value;
4798 mp_.no_dyn_threshold = 1;
4799 }
4800 break;
4801
4802 case M_MMAP_MAX:
4803 LIBC_PROBE (memory_mallopt_mmap_max, 3, value,
4804 mp_.n_mmaps_max, mp_.no_dyn_threshold);
4805 mp_.n_mmaps_max = value;
4806 mp_.no_dyn_threshold = 1;
4807 break;
4808
4809 case M_CHECK_ACTION:
4810 LIBC_PROBE (memory_mallopt_check_action, 2, value, check_action);
4811 check_action = value;
4812 break;
4813
4814 case M_PERTURB:
4815 LIBC_PROBE (memory_mallopt_perturb, 2, value, perturb_byte);
4816 perturb_byte = value;
4817 break;
4818
4819 case M_ARENA_TEST:
4820 if (value > 0)
4821 {
4822 LIBC_PROBE (memory_mallopt_arena_test, 2, value, mp_.arena_test);
4823 mp_.arena_test = value;
4824 }
4825 break;
4826
4827 case M_ARENA_MAX:
4828 if (value > 0)
4829 {
4830 LIBC_PROBE (memory_mallopt_arena_max, 2, value, mp_.arena_max);
4831 mp_.arena_max = value;
4832 }
4833 break;
4834 }
4835 (void) mutex_unlock (&av->mutex);
4836 return res;
4837}
4838libc_hidden_def (__libc_mallopt)
4839
4840
4841/*
4842 -------------------- Alternative MORECORE functions --------------------
4843 */
4844
4845
4846/*
4847 General Requirements for MORECORE.
4848
4849 The MORECORE function must have the following properties:
4850
4851 If MORECORE_CONTIGUOUS is false:
4852
4853 * MORECORE must allocate in multiples of pagesize. It will
4854 only be called with arguments that are multiples of pagesize.
4855
4856 * MORECORE(0) must return an address that is at least
4857 MALLOC_ALIGNMENT aligned. (Page-aligning always suffices.)
4858
4859 else (i.e. If MORECORE_CONTIGUOUS is true):
4860
4861 * Consecutive calls to MORECORE with positive arguments
4862 return increasing addresses, indicating that space has been
4863 contiguously extended.
4864
4865 * MORECORE need not allocate in multiples of pagesize.
4866 Calls to MORECORE need not have args of multiples of pagesize.
4867
4868 * MORECORE need not page-align.
4869
4870 In either case:
4871
4872 * MORECORE may allocate more memory than requested. (Or even less,
4873 but this will generally result in a malloc failure.)
4874
4875 * MORECORE must not allocate memory when given argument zero, but
4876 instead return one past the end address of memory from previous
4877 nonzero call. This malloc does NOT call MORECORE(0)
4878 until at least one call with positive arguments is made, so
4879 the initial value returned is not important.
4880
4881 * Even though consecutive calls to MORECORE need not return contiguous
4882 addresses, it must be OK for malloc'ed chunks to span multiple
4883 regions in those cases where they do happen to be contiguous.
4884
4885 * MORECORE need not handle negative arguments -- it may instead
4886 just return MORECORE_FAILURE when given negative arguments.
4887 Negative arguments are always multiples of pagesize. MORECORE
4888 must not misinterpret negative args as large positive unsigned
4889 args. You can suppress all such calls from even occurring by defining
4890 MORECORE_CANNOT_TRIM,
4891
4892 There is some variation across systems about the type of the
4893 argument to sbrk/MORECORE. If size_t is unsigned, then it cannot
4894 actually be size_t, because sbrk supports negative args, so it is
4895 normally the signed type of the same width as size_t (sometimes
4896 declared as "intptr_t", and sometimes "ptrdiff_t"). It doesn't much
4897 matter though. Internally, we use "long" as arguments, which should
4898 work across all reasonable possibilities.
4899
4900 Additionally, if MORECORE ever returns failure for a positive
4901 request, then mmap is used as a noncontiguous system allocator. This
4902 is a useful backup strategy for systems with holes in address spaces
4903 -- in this case sbrk cannot contiguously expand the heap, but mmap
4904 may be able to map noncontiguous space.
4905
4906 If you'd like mmap to ALWAYS be used, you can define MORECORE to be
4907 a function that always returns MORECORE_FAILURE.
4908
4909 If you are using this malloc with something other than sbrk (or its
4910 emulation) to supply memory regions, you probably want to set
4911 MORECORE_CONTIGUOUS as false. As an example, here is a custom
4912 allocator kindly contributed for pre-OSX macOS. It uses virtually
4913 but not necessarily physically contiguous non-paged memory (locked
4914 in, present and won't get swapped out). You can use it by
4915 uncommenting this section, adding some #includes, and setting up the
4916 appropriate defines above:
4917
4918 *#define MORECORE osMoreCore
4919 *#define MORECORE_CONTIGUOUS 0
4920
4921 There is also a shutdown routine that should somehow be called for
4922 cleanup upon program exit.
4923
4924 *#define MAX_POOL_ENTRIES 100
4925 *#define MINIMUM_MORECORE_SIZE (64 * 1024)
4926 static int next_os_pool;
4927 void *our_os_pools[MAX_POOL_ENTRIES];
4928
4929 void *osMoreCore(int size)
4930 {
4931 void *ptr = 0;
4932 static void *sbrk_top = 0;
4933
4934 if (size > 0)
4935 {
4936 if (size < MINIMUM_MORECORE_SIZE)
4937 size = MINIMUM_MORECORE_SIZE;
4938 if (CurrentExecutionLevel() == kTaskLevel)
4939 ptr = PoolAllocateResident(size + RM_PAGE_SIZE, 0);
4940 if (ptr == 0)
4941 {
4942 return (void *) MORECORE_FAILURE;
4943 }
4944 // save ptrs so they can be freed during cleanup
4945 our_os_pools[next_os_pool] = ptr;
4946 next_os_pool++;
4947 ptr = (void *) ((((unsigned long) ptr) + RM_PAGE_MASK) & ~RM_PAGE_MASK);
4948 sbrk_top = (char *) ptr + size;
4949 return ptr;
4950 }
4951 else if (size < 0)
4952 {
4953 // we don't currently support shrink behavior
4954 return (void *) MORECORE_FAILURE;
4955 }
4956 else
4957 {
4958 return sbrk_top;
4959 }
4960 }
4961
4962 // cleanup any allocated memory pools
4963 // called as last thing before shutting down driver
4964
4965 void osCleanupMem(void)
4966 {
4967 void **ptr;
4968
4969 for (ptr = our_os_pools; ptr < &our_os_pools[MAX_POOL_ENTRIES]; ptr++)
4970 if (*ptr)
4971 {
4972 PoolDeallocate(*ptr);
4973 * ptr = 0;
4974 }
4975 }
4976
4977 */
4978
4979
4980/* Helper code. */
4981
4982extern char **__libc_argv attribute_hidden;
4983
4984static void
4985malloc_printerr (int action, const char *str, void *ptr, mstate ar_ptr)
4986{
4987 /* Avoid using this arena in future. We do not attempt to synchronize this
4988 with anything else because we minimally want to ensure that __libc_message
4989 gets its resources safely without stumbling on the current corruption. */
4990 if (ar_ptr)
4991 set_arena_corrupt (ar_ptr);
4992
4993 if ((action & 5) == 5)
4994 __libc_message (action & 2, "%s\n", str);
4995 else if (action & 1)
4996 {
4997 char buf[2 * sizeof (uintptr_t) + 1];
4998
4999 buf[sizeof (buf) - 1] = '\0';
5000 char *cp = _itoa_word ((uintptr_t) ptr, &buf[sizeof (buf) - 1], 16, 0);
5001 while (cp > buf)
5002 *--cp = '0';
5003
5004 __libc_message (action & 2, "*** Error in `%s': %s: 0x%s ***\n",
5005 __libc_argv[0] ? : "<unknown>", str, cp);
5006 }
5007 else if (action & 2)
5008 abort ();
5009}
5010
5011/* We need a wrapper function for one of the additions of POSIX. */
5012int
5013__posix_memalign (void **memptr, size_t alignment, size_t size)
5014{
5015 void *mem;
5016
5017 /* Test whether the SIZE argument is valid. It must be a power of
5018 two multiple of sizeof (void *). */
5019 if (alignment % sizeof (void *) != 0
5020 || !powerof2 (alignment / sizeof (void *))
5021 || alignment == 0)
5022 return EINVAL;
5023
5024
5025 void *address = RETURN_ADDRESS (0);
5026 mem = _mid_memalign (alignment, size, address);
5027
5028 if (mem != NULL)
5029 {
5030 *memptr = mem;
5031 return 0;
5032 }
5033
5034 return ENOMEM;
5035}
5036weak_alias (__posix_memalign, posix_memalign)
5037
5038
5039int
5040__malloc_info (int options, FILE *fp)
5041{
5042 /* For now, at least. */
5043 if (options != 0)
5044 return EINVAL;
5045
5046 int n = 0;
5047 size_t total_nblocks = 0;
5048 size_t total_nfastblocks = 0;
5049 size_t total_avail = 0;
5050 size_t total_fastavail = 0;
5051 size_t total_system = 0;
5052 size_t total_max_system = 0;
5053 size_t total_aspace = 0;
5054 size_t total_aspace_mprotect = 0;
5055
5056
5057
5058 if (__malloc_initialized < 0)
5059 ptmalloc_init ();
5060
5061 fputs ("<malloc version=\"1\">\n", fp);
5062
5063 /* Iterate over all arenas currently in use. */
5064 mstate ar_ptr = &main_arena;
5065 do
5066 {
5067 fprintf (fp, "<heap nr=\"%d\">\n<sizes>\n", n++);
5068
5069 size_t nblocks = 0;
5070 size_t nfastblocks = 0;
5071 size_t avail = 0;
5072 size_t fastavail = 0;
5073 struct
5074 {
5075 size_t from;
5076 size_t to;
5077 size_t total;
5078 size_t count;
5079 } sizes[NFASTBINS + NBINS - 1];
5080#define nsizes (sizeof (sizes) / sizeof (sizes[0]))
5081
5082 mutex_lock (&ar_ptr->mutex);
5083
5084 for (size_t i = 0; i < NFASTBINS; ++i)
5085 {
5086 mchunkptr p = fastbin (ar_ptr, i);
5087 if (p != NULL)
5088 {
5089 size_t nthissize = 0;
5090 size_t thissize = chunksize (p);
5091
5092 while (p != NULL)
5093 {
5094 ++nthissize;
5095 p = p->fd;
5096 }
5097
5098 fastavail += nthissize * thissize;
5099 nfastblocks += nthissize;
5100 sizes[i].from = thissize - (MALLOC_ALIGNMENT - 1);
5101 sizes[i].to = thissize;
5102 sizes[i].count = nthissize;
5103 }
5104 else
5105 sizes[i].from = sizes[i].to = sizes[i].count = 0;
5106
5107 sizes[i].total = sizes[i].count * sizes[i].to;
5108 }
5109
5110
5111 mbinptr bin;
5112 struct malloc_chunk *r;
5113
5114 for (size_t i = 1; i < NBINS; ++i)
5115 {
5116 bin = bin_at (ar_ptr, i);
5117 r = bin->fd;
5118 sizes[NFASTBINS - 1 + i].from = ~((size_t) 0);
5119 sizes[NFASTBINS - 1 + i].to = sizes[NFASTBINS - 1 + i].total
5120 = sizes[NFASTBINS - 1 + i].count = 0;
5121
5122 if (r != NULL)
5123 while (r != bin)
5124 {
5125 ++sizes[NFASTBINS - 1 + i].count;
5126 sizes[NFASTBINS - 1 + i].total += r->size;
5127 sizes[NFASTBINS - 1 + i].from
5128 = MIN (sizes[NFASTBINS - 1 + i].from, r->size);
5129 sizes[NFASTBINS - 1 + i].to = MAX (sizes[NFASTBINS - 1 + i].to,
5130 r->size);
5131
5132 r = r->fd;
5133 }
5134
5135 if (sizes[NFASTBINS - 1 + i].count == 0)
5136 sizes[NFASTBINS - 1 + i].from = 0;
5137 nblocks += sizes[NFASTBINS - 1 + i].count;
5138 avail += sizes[NFASTBINS - 1 + i].total;
5139 }
5140
5141 mutex_unlock (&ar_ptr->mutex);
5142
5143 total_nfastblocks += nfastblocks;
5144 total_fastavail += fastavail;
5145
5146 total_nblocks += nblocks;
5147 total_avail += avail;
5148
5149 for (size_t i = 0; i < nsizes; ++i)
5150 if (sizes[i].count != 0 && i != NFASTBINS)
5151 fprintf (fp, " \
5152 <size from=\"%zu\" to=\"%zu\" total=\"%zu\" count=\"%zu\"/>\n",
5153 sizes[i].from, sizes[i].to, sizes[i].total, sizes[i].count);
5154
5155 if (sizes[NFASTBINS].count != 0)
5156 fprintf (fp, "\
5157 <unsorted from=\"%zu\" to=\"%zu\" total=\"%zu\" count=\"%zu\"/>\n",
5158 sizes[NFASTBINS].from, sizes[NFASTBINS].to,
5159 sizes[NFASTBINS].total, sizes[NFASTBINS].count);
5160
5161 total_system += ar_ptr->system_mem;
5162 total_max_system += ar_ptr->max_system_mem;
5163
5164 fprintf (fp,
5165 "</sizes>\n<total type=\"fast\" count=\"%zu\" size=\"%zu\"/>\n"
5166 "<total type=\"rest\" count=\"%zu\" size=\"%zu\"/>\n"
5167 "<system type=\"current\" size=\"%zu\"/>\n"
5168 "<system type=\"max\" size=\"%zu\"/>\n",
5169 nfastblocks, fastavail, nblocks, avail,
5170 ar_ptr->system_mem, ar_ptr->max_system_mem);
5171
5172 if (ar_ptr != &main_arena)
5173 {
5174 heap_info *heap = heap_for_ptr (top (ar_ptr));
5175 fprintf (fp,
5176 "<aspace type=\"total\" size=\"%zu\"/>\n"
5177 "<aspace type=\"mprotect\" size=\"%zu\"/>\n",
5178 heap->size, heap->mprotect_size);
5179 total_aspace += heap->size;
5180 total_aspace_mprotect += heap->mprotect_size;
5181 }
5182 else
5183 {
5184 fprintf (fp,
5185 "<aspace type=\"total\" size=\"%zu\"/>\n"
5186 "<aspace type=\"mprotect\" size=\"%zu\"/>\n",
5187 ar_ptr->system_mem, ar_ptr->system_mem);
5188 total_aspace += ar_ptr->system_mem;
5189 total_aspace_mprotect += ar_ptr->system_mem;
5190 }
5191
5192 fputs ("</heap>\n", fp);
5193 ar_ptr = ar_ptr->next;
5194 }
5195 while (ar_ptr != &main_arena);
5196
5197 fprintf (fp,
5198 "<total type=\"fast\" count=\"%zu\" size=\"%zu\"/>\n"
5199 "<total type=\"rest\" count=\"%zu\" size=\"%zu\"/>\n"
5200 "<total type=\"mmap\" count=\"%d\" size=\"%zu\"/>\n"
5201 "<system type=\"current\" size=\"%zu\"/>\n"
5202 "<system type=\"max\" size=\"%zu\"/>\n"
5203 "<aspace type=\"total\" size=\"%zu\"/>\n"
5204 "<aspace type=\"mprotect\" size=\"%zu\"/>\n"
5205 "</malloc>\n",
5206 total_nfastblocks, total_fastavail, total_nblocks, total_avail,
5207 mp_.n_mmaps, mp_.mmapped_mem,
5208 total_system, total_max_system,
5209 total_aspace, total_aspace_mprotect);
5210
5211 return 0;
5212}
5213weak_alias (__malloc_info, malloc_info)
5214
5215
5216strong_alias (__libc_calloc, __calloc) weak_alias (__libc_calloc, calloc)
5217strong_alias (__libc_free, __cfree) weak_alias (__libc_free, cfree)
5218strong_alias (__libc_free, __free) strong_alias (__libc_free, free)
5219strong_alias (__libc_malloc, __malloc) strong_alias (__libc_malloc, malloc)
5220strong_alias (__libc_memalign, __memalign)
5221weak_alias (__libc_memalign, memalign)
5222strong_alias (__libc_realloc, __realloc) strong_alias (__libc_realloc, realloc)
5223strong_alias (__libc_valloc, __valloc) weak_alias (__libc_valloc, valloc)
5224strong_alias (__libc_pvalloc, __pvalloc) weak_alias (__libc_pvalloc, pvalloc)
5225strong_alias (__libc_mallinfo, __mallinfo)
5226weak_alias (__libc_mallinfo, mallinfo)
5227strong_alias (__libc_mallopt, __mallopt) weak_alias (__libc_mallopt, mallopt)
5228
5229weak_alias (__malloc_stats, malloc_stats)
5230weak_alias (__malloc_usable_size, malloc_usable_size)
5231weak_alias (__malloc_trim, malloc_trim)
5232weak_alias (__malloc_get_state, malloc_get_state)
5233weak_alias (__malloc_set_state, malloc_set_state)
5234
5235
5236/* ------------------------------------------------------------
5237 History:
5238
5239 [see ftp://g.oswego.edu/pub/misc/malloc.c for the history of dlmalloc]
5240
5241 */
5242/*
5243 * Local variables:
5244 * c-basic-offset: 2
5245 * End:
5246 */
5247