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