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