39d5b3fa52cfb8d1d6382556b057c818b8b697e9
[kopensolaris-gnu/glibc.git] / malloc / malloc.c
1 /* Malloc implementation for multiple threads without lock contention.
2    Copyright (C) 1996-2006, 2007 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 not,
19    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
20    Boston, MA 02111-1307, USA.  */
21
22 /*
23   This is a version (aka ptmalloc2) of malloc/free/realloc written by
24   Doug Lea and adapted to multiple threads/arenas by Wolfram Gloger.
25
26 * Version ptmalloc2-20011215
27   based on:
28   VERSION 2.7.0 Sun Mar 11 14:14:06 2001  Doug Lea  (dl at gee)
29
30 * Quickstart
31
32   In order to compile this implementation, a Makefile is provided with
33   the ptmalloc2 distribution, which has pre-defined targets for some
34   popular systems (e.g. "make posix" for Posix threads).  All that is
35   typically required with regard to compiler flags is the selection of
36   the thread package via defining one out of USE_PTHREADS, USE_THR or
37   USE_SPROC.  Check the thread-m.h file for what effects this has.
38   Many/most systems will additionally require USE_TSD_DATA_HACK to be
39   defined, so this is the default for "make posix".
40
41 * Why use this malloc?
42
43   This is not the fastest, most space-conserving, most portable, or
44   most tunable malloc ever written. However it is among the fastest
45   while also being among the most space-conserving, portable and tunable.
46   Consistent balance across these factors results in a good general-purpose
47   allocator for malloc-intensive programs.
48
49   The main properties of the algorithms are:
50   * For large (>= 512 bytes) requests, it is a pure best-fit allocator,
51     with ties normally decided via FIFO (i.e. least recently used).
52   * For small (<= 64 bytes by default) requests, it is a caching
53     allocator, that maintains pools of quickly recycled chunks.
54   * In between, and for combinations of large and small requests, it does
55     the best it can trying to meet both goals at once.
56   * For very large requests (>= 128KB by default), it relies on system
57     memory mapping facilities, if supported.
58
59   For a longer but slightly out of date high-level description, see
60      http://gee.cs.oswego.edu/dl/html/malloc.html
61
62   You may already by default be using a C library containing a malloc
63   that is  based on some version of this malloc (for example in
64   linux). You might still want to use the one in this file in order to
65   customize settings or to avoid overheads associated with library
66   versions.
67
68 * Contents, described in more detail in "description of public routines" below.
69
70   Standard (ANSI/SVID/...)  functions:
71     malloc(size_t n);
72     calloc(size_t n_elements, size_t element_size);
73     free(Void_t* p);
74     realloc(Void_t* p, size_t n);
75     memalign(size_t alignment, size_t n);
76     valloc(size_t n);
77     mallinfo()
78     mallopt(int parameter_number, int parameter_value)
79
80   Additional functions:
81     independent_calloc(size_t n_elements, size_t size, Void_t* chunks[]);
82     independent_comalloc(size_t n_elements, size_t sizes[], Void_t* chunks[]);
83     pvalloc(size_t n);
84     cfree(Void_t* p);
85     malloc_trim(size_t pad);
86     malloc_usable_size(Void_t* p);
87     malloc_stats();
88
89 * Vital statistics:
90
91   Supported pointer representation:       4 or 8 bytes
92   Supported size_t  representation:       4 or 8 bytes
93        Note that size_t is allowed to be 4 bytes even if pointers are 8.
94        You can adjust this by defining INTERNAL_SIZE_T
95
96   Alignment:                              2 * sizeof(size_t) (default)
97        (i.e., 8 byte alignment with 4byte size_t). This suffices for
98        nearly all current machines and C compilers. However, you can
99        define MALLOC_ALIGNMENT to be wider than this if necessary.
100
101   Minimum overhead per allocated chunk:   4 or 8 bytes
102        Each malloced chunk has a hidden word of overhead holding size
103        and status information.
104
105   Minimum allocated size: 4-byte ptrs:  16 bytes    (including 4 overhead)
106                           8-byte ptrs:  24/32 bytes (including, 4/8 overhead)
107
108        When a chunk is freed, 12 (for 4byte ptrs) or 20 (for 8 byte
109        ptrs but 4 byte size) or 24 (for 8/8) additional bytes are
110        needed; 4 (8) for a trailing size field and 8 (16) bytes for
111        free list pointers. Thus, the minimum allocatable size is
112        16/24/32 bytes.
113
114        Even a request for zero bytes (i.e., malloc(0)) returns a
115        pointer to something of the minimum allocatable size.
116
117        The maximum overhead wastage (i.e., number of extra bytes
118        allocated than were requested in malloc) is less than or equal
119        to the minimum size, except for requests >= mmap_threshold that
120        are serviced via mmap(), where the worst case wastage is 2 *
121        sizeof(size_t) bytes plus the remainder from a system page (the
122        minimal mmap unit); typically 4096 or 8192 bytes.
123
124   Maximum allocated size:  4-byte size_t: 2^32 minus about two pages
125                            8-byte size_t: 2^64 minus about two pages
126
127        It is assumed that (possibly signed) size_t values suffice to
128        represent chunk sizes. `Possibly signed' is due to the fact
129        that `size_t' may be defined on a system as either a signed or
130        an unsigned type. The ISO C standard says that it must be
131        unsigned, but a few systems are known not to adhere to this.
132        Additionally, even when size_t is unsigned, sbrk (which is by
133        default used to obtain memory from system) accepts signed
134        arguments, and may not be able to handle size_t-wide arguments
135        with negative sign bit.  Generally, values that would
136        appear as negative after accounting for overhead and alignment
137        are supported only via mmap(), which does not have this
138        limitation.
139
140        Requests for sizes outside the allowed range will perform an optional
141        failure action and then return null. (Requests may also
142        also fail because a system is out of memory.)
143
144   Thread-safety: thread-safe unless NO_THREADS is defined
145
146   Compliance: I believe it is compliant with the 1997 Single Unix Specification
147        (See http://www.opennc.org). Also SVID/XPG, ANSI C, and probably
148        others as well.
149
150 * Synopsis of compile-time options:
151
152     People have reported using previous versions of this malloc on all
153     versions of Unix, sometimes by tweaking some of the defines
154     below. It has been tested most extensively on Solaris and
155     Linux. It is also reported to work on WIN32 platforms.
156     People also report using it in stand-alone embedded systems.
157
158     The implementation is in straight, hand-tuned ANSI C.  It is not
159     at all modular. (Sorry!)  It uses a lot of macros.  To be at all
160     usable, this code should be compiled using an optimizing compiler
161     (for example gcc -O3) that can simplify expressions and control
162     paths. (FAQ: some macros import variables as arguments rather than
163     declare locals because people reported that some debuggers
164     otherwise get confused.)
165
166     OPTION                     DEFAULT VALUE
167
168     Compilation Environment options:
169
170     __STD_C                    derived from C compiler defines
171     WIN32                      NOT defined
172     HAVE_MEMCPY                defined
173     USE_MEMCPY                 1 if HAVE_MEMCPY is defined
174     HAVE_MMAP                  defined as 1
175     MMAP_CLEARS                1
176     HAVE_MREMAP                0 unless linux defined
177     USE_ARENAS                 the same as HAVE_MMAP
178     malloc_getpagesize         derived from system #includes, or 4096 if not
179     HAVE_USR_INCLUDE_MALLOC_H  NOT defined
180     LACKS_UNISTD_H             NOT defined unless WIN32
181     LACKS_SYS_PARAM_H          NOT defined unless WIN32
182     LACKS_SYS_MMAN_H           NOT defined unless WIN32
183
184     Changing default word sizes:
185
186     INTERNAL_SIZE_T            size_t
187     MALLOC_ALIGNMENT           MAX (2 * sizeof(INTERNAL_SIZE_T),
188                                     __alignof__ (long double))
189
190     Configuration and functionality options:
191
192     USE_DL_PREFIX              NOT defined
193     USE_PUBLIC_MALLOC_WRAPPERS NOT defined
194     USE_MALLOC_LOCK            NOT defined
195     MALLOC_DEBUG               NOT defined
196     REALLOC_ZERO_BYTES_FREES   1
197     MALLOC_FAILURE_ACTION      errno = ENOMEM, if __STD_C defined, else no-op
198     TRIM_FASTBINS              0
199
200     Options for customizing MORECORE:
201
202     MORECORE                   sbrk
203     MORECORE_FAILURE           -1
204     MORECORE_CONTIGUOUS        1
205     MORECORE_CANNOT_TRIM       NOT defined
206     MORECORE_CLEARS            1
207     MMAP_AS_MORECORE_SIZE      (1024 * 1024)
208
209     Tuning options that are also dynamically changeable via mallopt:
210
211     DEFAULT_MXFAST             64
212     DEFAULT_TRIM_THRESHOLD     128 * 1024
213     DEFAULT_TOP_PAD            0
214     DEFAULT_MMAP_THRESHOLD     128 * 1024
215     DEFAULT_MMAP_MAX           65536
216
217     There are several other #defined constants and macros that you
218     probably don't want to touch unless you are extending or adapting malloc.  */
219
220 /*
221   __STD_C should be nonzero if using ANSI-standard C compiler, a C++
222   compiler, or a C compiler sufficiently close to ANSI to get away
223   with it.
224 */
225
226 #ifndef __STD_C
227 #if defined(__STDC__) || defined(__cplusplus)
228 #define __STD_C     1
229 #else
230 #define __STD_C     0
231 #endif
232 #endif /*__STD_C*/
233
234
235 /*
236   Void_t* is the pointer type that malloc should say it returns
237 */
238
239 #ifndef Void_t
240 #if (__STD_C || defined(WIN32))
241 #define Void_t      void
242 #else
243 #define Void_t      char
244 #endif
245 #endif /*Void_t*/
246
247 #if __STD_C
248 #include <stddef.h>   /* for size_t */
249 #include <stdlib.h>   /* for getenv(), abort() */
250 #else
251 #include <sys/types.h>
252 #endif
253
254 #include <malloc-machine.h>
255
256 #ifdef _LIBC
257 #include <stdio-common/_itoa.h>
258 #include <bits/wordsize.h>
259 #endif
260
261 #ifdef __cplusplus
262 extern "C" {
263 #endif
264
265 /* define LACKS_UNISTD_H if your system does not have a <unistd.h>. */
266
267 /* #define  LACKS_UNISTD_H */
268
269 #ifndef LACKS_UNISTD_H
270 #include <unistd.h>
271 #endif
272
273 /* define LACKS_SYS_PARAM_H if your system does not have a <sys/param.h>. */
274
275 /* #define  LACKS_SYS_PARAM_H */
276
277
278 #include <stdio.h>    /* needed for malloc_stats */
279 #include <errno.h>    /* needed for optional MALLOC_FAILURE_ACTION */
280
281 /* For uintptr_t.  */
282 #include <stdint.h>
283
284 /* For va_arg, va_start, va_end.  */
285 #include <stdarg.h>
286
287 /* For writev and struct iovec.  */
288 #include <sys/uio.h>
289 /* For syslog.  */
290 #include <sys/syslog.h>
291
292 /* For various dynamic linking things.  */
293 #include <dlfcn.h>
294
295
296 /*
297   Debugging:
298
299   Because freed chunks may be overwritten with bookkeeping fields, this
300   malloc will often die when freed memory is overwritten by user
301   programs.  This can be very effective (albeit in an annoying way)
302   in helping track down dangling pointers.
303
304   If you compile with -DMALLOC_DEBUG, a number of assertion checks are
305   enabled that will catch more memory errors. You probably won't be
306   able to make much sense of the actual assertion errors, but they
307   should help you locate incorrectly overwritten memory.  The checking
308   is fairly extensive, and will slow down execution
309   noticeably. Calling malloc_stats or mallinfo with MALLOC_DEBUG set
310   will attempt to check every non-mmapped allocated and free chunk in
311   the course of computing the summmaries. (By nature, mmapped regions
312   cannot be checked very much automatically.)
313
314   Setting MALLOC_DEBUG may also be helpful if you are trying to modify
315   this code. The assertions in the check routines spell out in more
316   detail the assumptions and invariants underlying the algorithms.
317
318   Setting MALLOC_DEBUG does NOT provide an automated mechanism for
319   checking that all accesses to malloced memory stay within their
320   bounds. However, there are several add-ons and adaptations of this
321   or other mallocs available that do this.
322 */
323
324 #if MALLOC_DEBUG
325 #include <assert.h>
326 #else
327 #undef  assert
328 #define assert(x) ((void)0)
329 #endif
330
331
332 /*
333   INTERNAL_SIZE_T is the word-size used for internal bookkeeping
334   of chunk sizes.
335
336   The default version is the same as size_t.
337
338   While not strictly necessary, it is best to define this as an
339   unsigned type, even if size_t is a signed type. This may avoid some
340   artificial size limitations on some systems.
341
342   On a 64-bit machine, you may be able to reduce malloc overhead by
343   defining INTERNAL_SIZE_T to be a 32 bit `unsigned int' at the
344   expense of not being able to handle more than 2^32 of malloced
345   space. If this limitation is acceptable, you are encouraged to set
346   this unless you are on a platform requiring 16byte alignments. In
347   this case the alignment requirements turn out to negate any
348   potential advantages of decreasing size_t word size.
349
350   Implementors: Beware of the possible combinations of:
351      - INTERNAL_SIZE_T might be signed or unsigned, might be 32 or 64 bits,
352        and might be the same width as int or as long
353      - size_t might have different width and signedness as INTERNAL_SIZE_T
354      - int and long might be 32 or 64 bits, and might be the same width
355   To deal with this, most comparisons and difference computations
356   among INTERNAL_SIZE_Ts should cast them to unsigned long, being
357   aware of the fact that casting an unsigned int to a wider long does
358   not sign-extend. (This also makes checking for negative numbers
359   awkward.) Some of these casts result in harmless compiler warnings
360   on some systems.
361 */
362
363 #ifndef INTERNAL_SIZE_T
364 #define INTERNAL_SIZE_T size_t
365 #endif
366
367 /* The corresponding word size */
368 #define SIZE_SZ                (sizeof(INTERNAL_SIZE_T))
369
370
371 /*
372   MALLOC_ALIGNMENT is the minimum alignment for malloc'ed chunks.
373   It must be a power of two at least 2 * SIZE_SZ, even on machines
374   for which smaller alignments would suffice. It may be defined as
375   larger than this though. Note however that code and data structures
376   are optimized for the case of 8-byte alignment.
377 */
378
379
380 #ifndef MALLOC_ALIGNMENT
381 /* XXX This is the correct definition.  It differs from 2*SIZE_SZ only on
382    powerpc32.  For the time being, changing this is causing more
383    compatibility problems due to malloc_get_state/malloc_set_state than
384    will returning blocks not adequately aligned for long double objects
385    under -mlong-double-128.
386
387 #define MALLOC_ALIGNMENT       (2 * SIZE_SZ < __alignof__ (long double) \
388                                 ? __alignof__ (long double) : 2 * SIZE_SZ)
389 */
390 #define MALLOC_ALIGNMENT       (2 * SIZE_SZ)
391 #endif
392
393 /* The corresponding bit mask value */
394 #define MALLOC_ALIGN_MASK      (MALLOC_ALIGNMENT - 1)
395
396
397
398 /*
399   REALLOC_ZERO_BYTES_FREES should be set if a call to
400   realloc with zero bytes should be the same as a call to free.
401   This is required by the C standard. Otherwise, since this malloc
402   returns a unique pointer for malloc(0), so does realloc(p, 0).
403 */
404
405 #ifndef REALLOC_ZERO_BYTES_FREES
406 #define REALLOC_ZERO_BYTES_FREES 1
407 #endif
408
409 /*
410   TRIM_FASTBINS controls whether free() of a very small chunk can
411   immediately lead to trimming. Setting to true (1) can reduce memory
412   footprint, but will almost always slow down programs that use a lot
413   of small chunks.
414
415   Define this only if you are willing to give up some speed to more
416   aggressively reduce system-level memory footprint when releasing
417   memory in programs that use many small chunks.  You can get
418   essentially the same effect by setting MXFAST to 0, but this can
419   lead to even greater slowdowns in programs using many small chunks.
420   TRIM_FASTBINS is an in-between compile-time option, that disables
421   only those chunks bordering topmost memory from being placed in
422   fastbins.
423 */
424
425 #ifndef TRIM_FASTBINS
426 #define TRIM_FASTBINS  0
427 #endif
428
429
430 /*
431   USE_DL_PREFIX will prefix all public routines with the string 'dl'.
432   This is necessary when you only want to use this malloc in one part
433   of a program, using your regular system malloc elsewhere.
434 */
435
436 /* #define USE_DL_PREFIX */
437
438
439 /*
440    Two-phase name translation.
441    All of the actual routines are given mangled names.
442    When wrappers are used, they become the public callable versions.
443    When DL_PREFIX is used, the callable names are prefixed.
444 */
445
446 #ifdef USE_DL_PREFIX
447 #define public_cALLOc    dlcalloc
448 #define public_fREe      dlfree
449 #define public_cFREe     dlcfree
450 #define public_mALLOc    dlmalloc
451 #define public_mEMALIGn  dlmemalign
452 #define public_rEALLOc   dlrealloc
453 #define public_vALLOc    dlvalloc
454 #define public_pVALLOc   dlpvalloc
455 #define public_mALLINFo  dlmallinfo
456 #define public_mALLOPt   dlmallopt
457 #define public_mTRIm     dlmalloc_trim
458 #define public_mSTATs    dlmalloc_stats
459 #define public_mUSABLe   dlmalloc_usable_size
460 #define public_iCALLOc   dlindependent_calloc
461 #define public_iCOMALLOc dlindependent_comalloc
462 #define public_gET_STATe dlget_state
463 #define public_sET_STATe dlset_state
464 #else /* USE_DL_PREFIX */
465 #ifdef _LIBC
466
467 /* Special defines for the GNU C library.  */
468 #define public_cALLOc    __libc_calloc
469 #define public_fREe      __libc_free
470 #define public_cFREe     __libc_cfree
471 #define public_mALLOc    __libc_malloc
472 #define public_mEMALIGn  __libc_memalign
473 #define public_rEALLOc   __libc_realloc
474 #define public_vALLOc    __libc_valloc
475 #define public_pVALLOc   __libc_pvalloc
476 #define public_mALLINFo  __libc_mallinfo
477 #define public_mALLOPt   __libc_mallopt
478 #define public_mTRIm     __malloc_trim
479 #define public_mSTATs    __malloc_stats
480 #define public_mUSABLe   __malloc_usable_size
481 #define public_iCALLOc   __libc_independent_calloc
482 #define public_iCOMALLOc __libc_independent_comalloc
483 #define public_gET_STATe __malloc_get_state
484 #define public_sET_STATe __malloc_set_state
485 #define malloc_getpagesize __getpagesize()
486 #define open             __open
487 #define mmap             __mmap
488 #define munmap           __munmap
489 #define mremap           __mremap
490 #define mprotect         __mprotect
491 #define MORECORE         (*__morecore)
492 #define MORECORE_FAILURE 0
493
494 Void_t * __default_morecore (ptrdiff_t);
495 Void_t *(*__morecore)(ptrdiff_t) = __default_morecore;
496
497 #else /* !_LIBC */
498 #define public_cALLOc    calloc
499 #define public_fREe      free
500 #define public_cFREe     cfree
501 #define public_mALLOc    malloc
502 #define public_mEMALIGn  memalign
503 #define public_rEALLOc   realloc
504 #define public_vALLOc    valloc
505 #define public_pVALLOc   pvalloc
506 #define public_mALLINFo  mallinfo
507 #define public_mALLOPt   mallopt
508 #define public_mTRIm     malloc_trim
509 #define public_mSTATs    malloc_stats
510 #define public_mUSABLe   malloc_usable_size
511 #define public_iCALLOc   independent_calloc
512 #define public_iCOMALLOc independent_comalloc
513 #define public_gET_STATe malloc_get_state
514 #define public_sET_STATe malloc_set_state
515 #endif /* _LIBC */
516 #endif /* USE_DL_PREFIX */
517
518 #ifndef _LIBC
519 #define __builtin_expect(expr, val)     (expr)
520
521 #define fwrite(buf, size, count, fp) _IO_fwrite (buf, size, count, fp)
522 #endif
523
524 /*
525   HAVE_MEMCPY should be defined if you are not otherwise using
526   ANSI STD C, but still have memcpy and memset in your C library
527   and want to use them in calloc and realloc. Otherwise simple
528   macro versions are defined below.
529
530   USE_MEMCPY should be defined as 1 if you actually want to
531   have memset and memcpy called. People report that the macro
532   versions are faster than libc versions on some systems.
533
534   Even if USE_MEMCPY is set to 1, loops to copy/clear small chunks
535   (of <= 36 bytes) are manually unrolled in realloc and calloc.
536 */
537
538 #define HAVE_MEMCPY
539
540 #ifndef USE_MEMCPY
541 #ifdef HAVE_MEMCPY
542 #define USE_MEMCPY 1
543 #else
544 #define USE_MEMCPY 0
545 #endif
546 #endif
547
548
549 #if (__STD_C || defined(HAVE_MEMCPY))
550
551 #ifdef _LIBC
552 # include <string.h>
553 #else
554 #ifdef WIN32
555 /* On Win32 memset and memcpy are already declared in windows.h */
556 #else
557 #if __STD_C
558 void* memset(void*, int, size_t);
559 void* memcpy(void*, const void*, size_t);
560 #else
561 Void_t* memset();
562 Void_t* memcpy();
563 #endif
564 #endif
565 #endif
566 #endif
567
568 /*
569   MALLOC_FAILURE_ACTION is the action to take before "return 0" when
570   malloc fails to be able to return memory, either because memory is
571   exhausted or because of illegal arguments.
572
573   By default, sets errno if running on STD_C platform, else does nothing.
574 */
575
576 #ifndef MALLOC_FAILURE_ACTION
577 #if __STD_C
578 #define MALLOC_FAILURE_ACTION \
579    errno = ENOMEM;
580
581 #else
582 #define MALLOC_FAILURE_ACTION
583 #endif
584 #endif
585
586 /*
587   MORECORE-related declarations. By default, rely on sbrk
588 */
589
590
591 #ifdef LACKS_UNISTD_H
592 #if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)
593 #if __STD_C
594 extern Void_t*     sbrk(ptrdiff_t);
595 #else
596 extern Void_t*     sbrk();
597 #endif
598 #endif
599 #endif
600
601 /*
602   MORECORE is the name of the routine to call to obtain more memory
603   from the system.  See below for general guidance on writing
604   alternative MORECORE functions, as well as a version for WIN32 and a
605   sample version for pre-OSX macos.
606 */
607
608 #ifndef MORECORE
609 #define MORECORE sbrk
610 #endif
611
612 /*
613   MORECORE_FAILURE is the value returned upon failure of MORECORE
614   as well as mmap. Since it cannot be an otherwise valid memory address,
615   and must reflect values of standard sys calls, you probably ought not
616   try to redefine it.
617 */
618
619 #ifndef MORECORE_FAILURE
620 #define MORECORE_FAILURE (-1)
621 #endif
622
623 /*
624   If MORECORE_CONTIGUOUS is true, take advantage of fact that
625   consecutive calls to MORECORE with positive arguments always return
626   contiguous increasing addresses.  This is true of unix sbrk.  Even
627   if not defined, when regions happen to be contiguous, malloc will
628   permit allocations spanning regions obtained from different
629   calls. But defining this when applicable enables some stronger
630   consistency checks and space efficiencies.
631 */
632
633 #ifndef MORECORE_CONTIGUOUS
634 #define MORECORE_CONTIGUOUS 1
635 #endif
636
637 /*
638   Define MORECORE_CANNOT_TRIM if your version of MORECORE
639   cannot release space back to the system when given negative
640   arguments. This is generally necessary only if you are using
641   a hand-crafted MORECORE function that cannot handle negative arguments.
642 */
643
644 /* #define MORECORE_CANNOT_TRIM */
645
646 /*  MORECORE_CLEARS           (default 1)
647      The degree to which the routine mapped to MORECORE zeroes out
648      memory: never (0), only for newly allocated space (1) or always
649      (2).  The distinction between (1) and (2) is necessary because on
650      some systems, if the application first decrements and then
651      increments the break value, the contents of the reallocated space
652      are unspecified.
653 */
654
655 #ifndef MORECORE_CLEARS
656 #define MORECORE_CLEARS 1
657 #endif
658
659
660 /*
661   Define HAVE_MMAP as true to optionally make malloc() use mmap() to
662   allocate very large blocks.  These will be returned to the
663   operating system immediately after a free(). Also, if mmap
664   is available, it is used as a backup strategy in cases where
665   MORECORE fails to provide space from system.
666
667   This malloc is best tuned to work with mmap for large requests.
668   If you do not have mmap, operations involving very large chunks (1MB
669   or so) may be slower than you'd like.
670 */
671
672 #ifndef HAVE_MMAP
673 #define HAVE_MMAP 1
674
675 /*
676    Standard unix mmap using /dev/zero clears memory so calloc doesn't
677    need to.
678 */
679
680 #ifndef MMAP_CLEARS
681 #define MMAP_CLEARS 1
682 #endif
683
684 #else /* no mmap */
685 #ifndef MMAP_CLEARS
686 #define MMAP_CLEARS 0
687 #endif
688 #endif
689
690
691 /*
692    MMAP_AS_MORECORE_SIZE is the minimum mmap size argument to use if
693    sbrk fails, and mmap is used as a backup (which is done only if
694    HAVE_MMAP).  The value must be a multiple of page size.  This
695    backup strategy generally applies only when systems have "holes" in
696    address space, so sbrk cannot perform contiguous expansion, but
697    there is still space available on system.  On systems for which
698    this is known to be useful (i.e. most linux kernels), this occurs
699    only when programs allocate huge amounts of memory.  Between this,
700    and the fact that mmap regions tend to be limited, the size should
701    be large, to avoid too many mmap calls and thus avoid running out
702    of kernel resources.
703 */
704
705 #ifndef MMAP_AS_MORECORE_SIZE
706 #define MMAP_AS_MORECORE_SIZE (1024 * 1024)
707 #endif
708
709 /*
710   Define HAVE_MREMAP to make realloc() use mremap() to re-allocate
711   large blocks.  This is currently only possible on Linux with
712   kernel versions newer than 1.3.77.
713 */
714
715 #ifndef HAVE_MREMAP
716 #ifdef linux
717 #define HAVE_MREMAP 1
718 #else
719 #define HAVE_MREMAP 0
720 #endif
721
722 #endif /* HAVE_MMAP */
723
724 /* Define USE_ARENAS to enable support for multiple `arenas'.  These
725    are allocated using mmap(), are necessary for threads and
726    occasionally useful to overcome address space limitations affecting
727    sbrk(). */
728
729 #ifndef USE_ARENAS
730 #define USE_ARENAS HAVE_MMAP
731 #endif
732
733
734 /*
735   The system page size. To the extent possible, this malloc manages
736   memory from the system in page-size units.  Note that this value is
737   cached during initialization into a field of malloc_state. So even
738   if malloc_getpagesize is a function, it is only called once.
739
740   The following mechanics for getpagesize were adapted from bsd/gnu
741   getpagesize.h. If none of the system-probes here apply, a value of
742   4096 is used, which should be OK: If they don't apply, then using
743   the actual value probably doesn't impact performance.
744 */
745
746
747 #ifndef malloc_getpagesize
748
749 #ifndef LACKS_UNISTD_H
750 #  include <unistd.h>
751 #endif
752
753 #  ifdef _SC_PAGESIZE         /* some SVR4 systems omit an underscore */
754 #    ifndef _SC_PAGE_SIZE
755 #      define _SC_PAGE_SIZE _SC_PAGESIZE
756 #    endif
757 #  endif
758
759 #  ifdef _SC_PAGE_SIZE
760 #    define malloc_getpagesize sysconf(_SC_PAGE_SIZE)
761 #  else
762 #    if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE)
763        extern size_t getpagesize();
764 #      define malloc_getpagesize getpagesize()
765 #    else
766 #      ifdef WIN32 /* use supplied emulation of getpagesize */
767 #        define malloc_getpagesize getpagesize()
768 #      else
769 #        ifndef LACKS_SYS_PARAM_H
770 #          include <sys/param.h>
771 #        endif
772 #        ifdef EXEC_PAGESIZE
773 #          define malloc_getpagesize EXEC_PAGESIZE
774 #        else
775 #          ifdef NBPG
776 #            ifndef CLSIZE
777 #              define malloc_getpagesize NBPG
778 #            else
779 #              define malloc_getpagesize (NBPG * CLSIZE)
780 #            endif
781 #          else
782 #            ifdef NBPC
783 #              define malloc_getpagesize NBPC
784 #            else
785 #              ifdef PAGESIZE
786 #                define malloc_getpagesize PAGESIZE
787 #              else /* just guess */
788 #                define malloc_getpagesize (4096)
789 #              endif
790 #            endif
791 #          endif
792 #        endif
793 #      endif
794 #    endif
795 #  endif
796 #endif
797
798 /*
799   This version of malloc supports the standard SVID/XPG mallinfo
800   routine that returns a struct containing usage properties and
801   statistics. It should work on any SVID/XPG compliant system that has
802   a /usr/include/malloc.h defining struct mallinfo. (If you'd like to
803   install such a thing yourself, cut out the preliminary declarations
804   as described above and below and save them in a malloc.h file. But
805   there's no compelling reason to bother to do this.)
806
807   The main declaration needed is the mallinfo struct that is returned
808   (by-copy) by mallinfo().  The SVID/XPG malloinfo struct contains a
809   bunch of fields that are not even meaningful in this version of
810   malloc.  These fields are are instead filled by mallinfo() with
811   other numbers that might be of interest.
812
813   HAVE_USR_INCLUDE_MALLOC_H should be set if you have a
814   /usr/include/malloc.h file that includes a declaration of struct
815   mallinfo.  If so, it is included; else an SVID2/XPG2 compliant
816   version is declared below.  These must be precisely the same for
817   mallinfo() to work.  The original SVID version of this struct,
818   defined on most systems with mallinfo, declares all fields as
819   ints. But some others define as unsigned long. If your system
820   defines the fields using a type of different width than listed here,
821   you must #include your system version and #define
822   HAVE_USR_INCLUDE_MALLOC_H.
823 */
824
825 /* #define HAVE_USR_INCLUDE_MALLOC_H */
826
827 #ifdef HAVE_USR_INCLUDE_MALLOC_H
828 #include "/usr/include/malloc.h"
829 #endif
830
831
832 /* ---------- description of public routines ------------ */
833
834 /*
835   malloc(size_t n)
836   Returns a pointer to a newly allocated chunk of at least n bytes, or null
837   if no space is available. Additionally, on failure, errno is
838   set to ENOMEM on ANSI C systems.
839
840   If n is zero, malloc returns a minumum-sized chunk. (The minimum
841   size is 16 bytes on most 32bit systems, and 24 or 32 bytes on 64bit
842   systems.)  On most systems, size_t is an unsigned type, so calls
843   with negative arguments are interpreted as requests for huge amounts
844   of space, which will often fail. The maximum supported value of n
845   differs across systems, but is in all cases less than the maximum
846   representable value of a size_t.
847 */
848 #if __STD_C
849 Void_t*  public_mALLOc(size_t);
850 #else
851 Void_t*  public_mALLOc();
852 #endif
853 #ifdef libc_hidden_proto
854 libc_hidden_proto (public_mALLOc)
855 #endif
856
857 /*
858   free(Void_t* p)
859   Releases the chunk of memory pointed to by p, that had been previously
860   allocated using malloc or a related routine such as realloc.
861   It has no effect if p is null. It can have arbitrary (i.e., bad!)
862   effects if p has already been freed.
863
864   Unless disabled (using mallopt), freeing very large spaces will
865   when possible, automatically trigger operations that give
866   back unused memory to the system, thus reducing program footprint.
867 */
868 #if __STD_C
869 void     public_fREe(Void_t*);
870 #else
871 void     public_fREe();
872 #endif
873 #ifdef libc_hidden_proto
874 libc_hidden_proto (public_fREe)
875 #endif
876
877 /*
878   calloc(size_t n_elements, size_t element_size);
879   Returns a pointer to n_elements * element_size bytes, with all locations
880   set to zero.
881 */
882 #if __STD_C
883 Void_t*  public_cALLOc(size_t, size_t);
884 #else
885 Void_t*  public_cALLOc();
886 #endif
887
888 /*
889   realloc(Void_t* p, size_t n)
890   Returns a pointer to a chunk of size n that contains the same data
891   as does chunk p up to the minimum of (n, p's size) bytes, or null
892   if no space is available.
893
894   The returned pointer may or may not be the same as p. The algorithm
895   prefers extending p when possible, otherwise it employs the
896   equivalent of a malloc-copy-free sequence.
897
898   If p is null, realloc is equivalent to malloc.
899
900   If space is not available, realloc returns null, errno is set (if on
901   ANSI) and p is NOT freed.
902
903   if n is for fewer bytes than already held by p, the newly unused
904   space is lopped off and freed if possible.  Unless the #define
905   REALLOC_ZERO_BYTES_FREES is set, realloc with a size argument of
906   zero (re)allocates a minimum-sized chunk.
907
908   Large chunks that were internally obtained via mmap will always
909   be reallocated using malloc-copy-free sequences unless
910   the system supports MREMAP (currently only linux).
911
912   The old unix realloc convention of allowing the last-free'd chunk
913   to be used as an argument to realloc is not supported.
914 */
915 #if __STD_C
916 Void_t*  public_rEALLOc(Void_t*, size_t);
917 #else
918 Void_t*  public_rEALLOc();
919 #endif
920 #ifdef libc_hidden_proto
921 libc_hidden_proto (public_rEALLOc)
922 #endif
923
924 /*
925   memalign(size_t alignment, size_t n);
926   Returns a pointer to a newly allocated chunk of n bytes, aligned
927   in accord with the alignment argument.
928
929   The alignment argument should be a power of two. If the argument is
930   not a power of two, the nearest greater power is used.
931   8-byte alignment is guaranteed by normal malloc calls, so don't
932   bother calling memalign with an argument of 8 or less.
933
934   Overreliance on memalign is a sure way to fragment space.
935 */
936 #if __STD_C
937 Void_t*  public_mEMALIGn(size_t, size_t);
938 #else
939 Void_t*  public_mEMALIGn();
940 #endif
941 #ifdef libc_hidden_proto
942 libc_hidden_proto (public_mEMALIGn)
943 #endif
944
945 /*
946   valloc(size_t n);
947   Equivalent to memalign(pagesize, n), where pagesize is the page
948   size of the system. If the pagesize is unknown, 4096 is used.
949 */
950 #if __STD_C
951 Void_t*  public_vALLOc(size_t);
952 #else
953 Void_t*  public_vALLOc();
954 #endif
955
956
957
958 /*
959   mallopt(int parameter_number, int parameter_value)
960   Sets tunable parameters The format is to provide a
961   (parameter-number, parameter-value) pair.  mallopt then sets the
962   corresponding parameter to the argument value if it can (i.e., so
963   long as the value is meaningful), and returns 1 if successful else
964   0.  SVID/XPG/ANSI defines four standard param numbers for mallopt,
965   normally defined in malloc.h.  Only one of these (M_MXFAST) is used
966   in this malloc. The others (M_NLBLKS, M_GRAIN, M_KEEP) don't apply,
967   so setting them has no effect. But this malloc also supports four
968   other options in mallopt. See below for details.  Briefly, supported
969   parameters are as follows (listed defaults are for "typical"
970   configurations).
971
972   Symbol            param #   default    allowed param values
973   M_MXFAST          1         64         0-80  (0 disables fastbins)
974   M_TRIM_THRESHOLD -1         128*1024   any   (-1U disables trimming)
975   M_TOP_PAD        -2         0          any
976   M_MMAP_THRESHOLD -3         128*1024   any   (or 0 if no MMAP support)
977   M_MMAP_MAX       -4         65536      any   (0 disables use of mmap)
978 */
979 #if __STD_C
980 int      public_mALLOPt(int, int);
981 #else
982 int      public_mALLOPt();
983 #endif
984
985
986 /*
987   mallinfo()
988   Returns (by copy) a struct containing various summary statistics:
989
990   arena:     current total non-mmapped bytes allocated from system
991   ordblks:   the number of free chunks
992   smblks:    the number of fastbin blocks (i.e., small chunks that
993                have been freed but not use resused or consolidated)
994   hblks:     current number of mmapped regions
995   hblkhd:    total bytes held in mmapped regions
996   usmblks:   the maximum total allocated space. This will be greater
997                 than current total if trimming has occurred.
998   fsmblks:   total bytes held in fastbin blocks
999   uordblks:  current total allocated space (normal or mmapped)
1000   fordblks:  total free space
1001   keepcost:  the maximum number of bytes that could ideally be released
1002                back to system via malloc_trim. ("ideally" means that
1003                it ignores page restrictions etc.)
1004
1005   Because these fields are ints, but internal bookkeeping may
1006   be kept as longs, the reported values may wrap around zero and
1007   thus be inaccurate.
1008 */
1009 #if __STD_C
1010 struct mallinfo public_mALLINFo(void);
1011 #else
1012 struct mallinfo public_mALLINFo();
1013 #endif
1014
1015 #ifndef _LIBC
1016 /*
1017   independent_calloc(size_t n_elements, size_t element_size, Void_t* chunks[]);
1018
1019   independent_calloc is similar to calloc, but instead of returning a
1020   single cleared space, it returns an array of pointers to n_elements
1021   independent elements that can hold contents of size elem_size, each
1022   of which starts out cleared, and can be independently freed,
1023   realloc'ed etc. The elements are guaranteed to be adjacently
1024   allocated (this is not guaranteed to occur with multiple callocs or
1025   mallocs), which may also improve cache locality in some
1026   applications.
1027
1028   The "chunks" argument is optional (i.e., may be null, which is
1029   probably the most typical usage). If it is null, the returned array
1030   is itself dynamically allocated and should also be freed when it is
1031   no longer needed. Otherwise, the chunks array must be of at least
1032   n_elements in length. It is filled in with the pointers to the
1033   chunks.
1034
1035   In either case, independent_calloc returns this pointer array, or
1036   null if the allocation failed.  If n_elements is zero and "chunks"
1037   is null, it returns a chunk representing an array with zero elements
1038   (which should be freed if not wanted).
1039
1040   Each element must be individually freed when it is no longer
1041   needed. If you'd like to instead be able to free all at once, you
1042   should instead use regular calloc and assign pointers into this
1043   space to represent elements.  (In this case though, you cannot
1044   independently free elements.)
1045
1046   independent_calloc simplifies and speeds up implementations of many
1047   kinds of pools.  It may also be useful when constructing large data
1048   structures that initially have a fixed number of fixed-sized nodes,
1049   but the number is not known at compile time, and some of the nodes
1050   may later need to be freed. For example:
1051
1052   struct Node { int item; struct Node* next; };
1053
1054   struct Node* build_list() {
1055     struct Node** pool;
1056     int n = read_number_of_nodes_needed();
1057     if (n <= 0) return 0;
1058     pool = (struct Node**)(independent_calloc(n, sizeof(struct Node), 0);
1059     if (pool == 0) die();
1060     // organize into a linked list...
1061     struct Node* first = pool[0];
1062     for (i = 0; i < n-1; ++i)
1063       pool[i]->next = pool[i+1];
1064     free(pool);     // Can now free the array (or not, if it is needed later)
1065     return first;
1066   }
1067 */
1068 #if __STD_C
1069 Void_t** public_iCALLOc(size_t, size_t, Void_t**);
1070 #else
1071 Void_t** public_iCALLOc();
1072 #endif
1073
1074 /*
1075   independent_comalloc(size_t n_elements, size_t sizes[], Void_t* chunks[]);
1076
1077   independent_comalloc allocates, all at once, a set of n_elements
1078   chunks with sizes indicated in the "sizes" array.    It returns
1079   an array of pointers to these elements, each of which can be
1080   independently freed, realloc'ed etc. The elements are guaranteed to
1081   be adjacently allocated (this is not guaranteed to occur with
1082   multiple callocs or mallocs), which may also improve cache locality
1083   in some applications.
1084
1085   The "chunks" argument is optional (i.e., may be null). If it is null
1086   the returned array is itself dynamically allocated and should also
1087   be freed when it is no longer needed. Otherwise, the chunks array
1088   must be of at least n_elements in length. It is filled in with the
1089   pointers to the chunks.
1090
1091   In either case, independent_comalloc returns this pointer array, or
1092   null if the allocation failed.  If n_elements is zero and chunks is
1093   null, it returns a chunk representing an array with zero elements
1094   (which should be freed if not wanted).
1095
1096   Each element must be individually freed when it is no longer
1097   needed. If you'd like to instead be able to free all at once, you
1098   should instead use a single regular malloc, and assign pointers at
1099   particular offsets in the aggregate space. (In this case though, you
1100   cannot independently free elements.)
1101
1102   independent_comallac differs from independent_calloc in that each
1103   element may have a different size, and also that it does not
1104   automatically clear elements.
1105
1106   independent_comalloc can be used to speed up allocation in cases
1107   where several structs or objects must always be allocated at the
1108   same time.  For example:
1109
1110   struct Head { ... }
1111   struct Foot { ... }
1112
1113   void send_message(char* msg) {
1114     int msglen = strlen(msg);
1115     size_t sizes[3] = { sizeof(struct Head), msglen, sizeof(struct Foot) };
1116     void* chunks[3];
1117     if (independent_comalloc(3, sizes, chunks) == 0)
1118       die();
1119     struct Head* head = (struct Head*)(chunks[0]);
1120     char*        body = (char*)(chunks[1]);
1121     struct Foot* foot = (struct Foot*)(chunks[2]);
1122     // ...
1123   }
1124
1125   In general though, independent_comalloc is worth using only for
1126   larger values of n_elements. For small values, you probably won't
1127   detect enough difference from series of malloc calls to bother.
1128
1129   Overuse of independent_comalloc can increase overall memory usage,
1130   since it cannot reuse existing noncontiguous small chunks that
1131   might be available for some of the elements.
1132 */
1133 #if __STD_C
1134 Void_t** public_iCOMALLOc(size_t, size_t*, Void_t**);
1135 #else
1136 Void_t** public_iCOMALLOc();
1137 #endif
1138
1139 #endif /* _LIBC */
1140
1141
1142 /*
1143   pvalloc(size_t n);
1144   Equivalent to valloc(minimum-page-that-holds(n)), that is,
1145   round up n to nearest pagesize.
1146  */
1147 #if __STD_C
1148 Void_t*  public_pVALLOc(size_t);
1149 #else
1150 Void_t*  public_pVALLOc();
1151 #endif
1152
1153 /*
1154   cfree(Void_t* p);
1155   Equivalent to free(p).
1156
1157   cfree is needed/defined on some systems that pair it with calloc,
1158   for odd historical reasons (such as: cfree is used in example
1159   code in the first edition of K&R).
1160 */
1161 #if __STD_C
1162 void     public_cFREe(Void_t*);
1163 #else
1164 void     public_cFREe();
1165 #endif
1166
1167 /*
1168   malloc_trim(size_t pad);
1169
1170   If possible, gives memory back to the system (via negative
1171   arguments to sbrk) if there is unused memory at the `high' end of
1172   the malloc pool. You can call this after freeing large blocks of
1173   memory to potentially reduce the system-level memory requirements
1174   of a program. However, it cannot guarantee to reduce memory. Under
1175   some allocation patterns, some large free blocks of memory will be
1176   locked between two used chunks, so they cannot be given back to
1177   the system.
1178
1179   The `pad' argument to malloc_trim represents the amount of free
1180   trailing space to leave untrimmed. If this argument is zero,
1181   only the minimum amount of memory to maintain internal data
1182   structures will be left (one page or less). Non-zero arguments
1183   can be supplied to maintain enough trailing space to service
1184   future expected allocations without having to re-obtain memory
1185   from the system.
1186
1187   Malloc_trim returns 1 if it actually released any memory, else 0.
1188   On systems that do not support "negative sbrks", it will always
1189   rreturn 0.
1190 */
1191 #if __STD_C
1192 int      public_mTRIm(size_t);
1193 #else
1194 int      public_mTRIm();
1195 #endif
1196
1197 /*
1198   malloc_usable_size(Void_t* p);
1199
1200   Returns the number of bytes you can actually use in
1201   an allocated chunk, which may be more than you requested (although
1202   often not) due to alignment and minimum size constraints.
1203   You can use this many bytes without worrying about
1204   overwriting other allocated objects. This is not a particularly great
1205   programming practice. malloc_usable_size can be more useful in
1206   debugging and assertions, for example:
1207
1208   p = malloc(n);
1209   assert(malloc_usable_size(p) >= 256);
1210
1211 */
1212 #if __STD_C
1213 size_t   public_mUSABLe(Void_t*);
1214 #else
1215 size_t   public_mUSABLe();
1216 #endif
1217
1218 /*
1219   malloc_stats();
1220   Prints on stderr the amount of space obtained from the system (both
1221   via sbrk and mmap), the maximum amount (which may be more than
1222   current if malloc_trim and/or munmap got called), and the current
1223   number of bytes allocated via malloc (or realloc, etc) but not yet
1224   freed. Note that this is the number of bytes allocated, not the
1225   number requested. It will be larger than the number requested
1226   because of alignment and bookkeeping overhead. Because it includes
1227   alignment wastage as being in use, this figure may be greater than
1228   zero even when no user-level chunks are allocated.
1229
1230   The reported current and maximum system memory can be inaccurate if
1231   a program makes other calls to system memory allocation functions
1232   (normally sbrk) outside of malloc.
1233
1234   malloc_stats prints only the most commonly interesting statistics.
1235   More information can be obtained by calling mallinfo.
1236
1237 */
1238 #if __STD_C
1239 void     public_mSTATs(void);
1240 #else
1241 void     public_mSTATs();
1242 #endif
1243
1244 /*
1245   malloc_get_state(void);
1246
1247   Returns the state of all malloc variables in an opaque data
1248   structure.
1249 */
1250 #if __STD_C
1251 Void_t*  public_gET_STATe(void);
1252 #else
1253 Void_t*  public_gET_STATe();
1254 #endif
1255
1256 /*
1257   malloc_set_state(Void_t* state);
1258
1259   Restore the state of all malloc variables from data obtained with
1260   malloc_get_state().
1261 */
1262 #if __STD_C
1263 int      public_sET_STATe(Void_t*);
1264 #else
1265 int      public_sET_STATe();
1266 #endif
1267
1268 #ifdef _LIBC
1269 /*
1270   posix_memalign(void **memptr, size_t alignment, size_t size);
1271
1272   POSIX wrapper like memalign(), checking for validity of size.
1273 */
1274 int      __posix_memalign(void **, size_t, size_t);
1275 #endif
1276
1277 /* mallopt tuning options */
1278
1279 /*
1280   M_MXFAST is the maximum request size used for "fastbins", special bins
1281   that hold returned chunks without consolidating their spaces. This
1282   enables future requests for chunks of the same size to be handled
1283   very quickly, but can increase fragmentation, and thus increase the
1284   overall memory footprint of a program.
1285
1286   This malloc manages fastbins very conservatively yet still
1287   efficiently, so fragmentation is rarely a problem for values less
1288   than or equal to the default.  The maximum supported value of MXFAST
1289   is 80. You wouldn't want it any higher than this anyway.  Fastbins
1290   are designed especially for use with many small structs, objects or
1291   strings -- the default handles structs/objects/arrays with sizes up
1292   to 8 4byte fields, or small strings representing words, tokens,
1293   etc. Using fastbins for larger objects normally worsens
1294   fragmentation without improving speed.
1295
1296   M_MXFAST is set in REQUEST size units. It is internally used in
1297   chunksize units, which adds padding and alignment.  You can reduce
1298   M_MXFAST to 0 to disable all use of fastbins.  This causes the malloc
1299   algorithm to be a closer approximation of fifo-best-fit in all cases,
1300   not just for larger requests, but will generally cause it to be
1301   slower.
1302 */
1303
1304
1305 /* M_MXFAST is a standard SVID/XPG tuning option, usually listed in malloc.h */
1306 #ifndef M_MXFAST
1307 #define M_MXFAST            1
1308 #endif
1309
1310 #ifndef DEFAULT_MXFAST
1311 #define DEFAULT_MXFAST     64
1312 #endif
1313
1314
1315 /*
1316   M_TRIM_THRESHOLD is the maximum amount of unused top-most memory
1317   to keep before releasing via malloc_trim in free().
1318
1319   Automatic trimming is mainly useful in long-lived programs.
1320   Because trimming via sbrk can be slow on some systems, and can
1321   sometimes be wasteful (in cases where programs immediately
1322   afterward allocate more large chunks) the value should be high
1323   enough so that your overall system performance would improve by
1324   releasing this much memory.
1325
1326   The trim threshold and the mmap control parameters (see below)
1327   can be traded off with one another. Trimming and mmapping are
1328   two different ways of releasing unused memory back to the
1329   system. Between these two, it is often possible to keep
1330   system-level demands of a long-lived program down to a bare
1331   minimum. For example, in one test suite of sessions measuring
1332   the XF86 X server on Linux, using a trim threshold of 128K and a
1333   mmap threshold of 192K led to near-minimal long term resource
1334   consumption.
1335
1336   If you are using this malloc in a long-lived program, it should
1337   pay to experiment with these values.  As a rough guide, you
1338   might set to a value close to the average size of a process
1339   (program) running on your system.  Releasing this much memory
1340   would allow such a process to run in memory.  Generally, it's
1341   worth it to tune for trimming rather tham memory mapping when a
1342   program undergoes phases where several large chunks are
1343   allocated and released in ways that can reuse each other's
1344   storage, perhaps mixed with phases where there are no such
1345   chunks at all.  And in well-behaved long-lived programs,
1346   controlling release of large blocks via trimming versus mapping
1347   is usually faster.
1348
1349   However, in most programs, these parameters serve mainly as
1350   protection against the system-level effects of carrying around
1351   massive amounts of unneeded memory. Since frequent calls to
1352   sbrk, mmap, and munmap otherwise degrade performance, the default
1353   parameters are set to relatively high values that serve only as
1354   safeguards.
1355
1356   The trim value It must be greater than page size to have any useful
1357   effect.  To disable trimming completely, you can set to
1358   (unsigned long)(-1)
1359
1360   Trim settings interact with fastbin (MXFAST) settings: Unless
1361   TRIM_FASTBINS is defined, automatic trimming never takes place upon
1362   freeing a chunk with size less than or equal to MXFAST. Trimming is
1363   instead delayed until subsequent freeing of larger chunks. However,
1364   you can still force an attempted trim by calling malloc_trim.
1365
1366   Also, trimming is not generally possible in cases where
1367   the main arena is obtained via mmap.
1368
1369   Note that the trick some people use of mallocing a huge space and
1370   then freeing it at program startup, in an attempt to reserve system
1371   memory, doesn't have the intended effect under automatic trimming,
1372   since that memory will immediately be returned to the system.
1373 */
1374
1375 #define M_TRIM_THRESHOLD       -1
1376
1377 #ifndef DEFAULT_TRIM_THRESHOLD
1378 #define DEFAULT_TRIM_THRESHOLD (128 * 1024)
1379 #endif
1380
1381 /*
1382   M_TOP_PAD is the amount of extra `padding' space to allocate or
1383   retain whenever sbrk is called. It is used in two ways internally:
1384
1385   * When sbrk is called to extend the top of the arena to satisfy
1386   a new malloc request, this much padding is added to the sbrk
1387   request.
1388
1389   * When malloc_trim is called automatically from free(),
1390   it is used as the `pad' argument.
1391
1392   In both cases, the actual amount of padding is rounded
1393   so that the end of the arena is always a system page boundary.
1394
1395   The main reason for using padding is to avoid calling sbrk so
1396   often. Having even a small pad greatly reduces the likelihood
1397   that nearly every malloc request during program start-up (or
1398   after trimming) will invoke sbrk, which needlessly wastes
1399   time.
1400
1401   Automatic rounding-up to page-size units is normally sufficient
1402   to avoid measurable overhead, so the default is 0.  However, in
1403   systems where sbrk is relatively slow, it can pay to increase
1404   this value, at the expense of carrying around more memory than
1405   the program needs.
1406 */
1407
1408 #define M_TOP_PAD              -2
1409
1410 #ifndef DEFAULT_TOP_PAD
1411 #define DEFAULT_TOP_PAD        (0)
1412 #endif
1413
1414 /*
1415   MMAP_THRESHOLD_MAX and _MIN are the bounds on the dynamically
1416   adjusted MMAP_THRESHOLD.
1417 */
1418
1419 #ifndef DEFAULT_MMAP_THRESHOLD_MIN
1420 #define DEFAULT_MMAP_THRESHOLD_MIN (128 * 1024)
1421 #endif
1422
1423 #ifndef DEFAULT_MMAP_THRESHOLD_MAX
1424   /* For 32-bit platforms we cannot increase the maximum mmap
1425      threshold much because it is also the minimum value for the
1426      maximum heap size and its alignment.  Going above 512k (i.e., 1M
1427      for new heaps) wastes too much address space.  */
1428 # if __WORDSIZE == 32
1429 #  define DEFAULT_MMAP_THRESHOLD_MAX (512 * 1024)
1430 # else
1431 #  define DEFAULT_MMAP_THRESHOLD_MAX (4 * 1024 * 1024 * sizeof(long))
1432 # endif
1433 #endif
1434
1435 /*
1436   M_MMAP_THRESHOLD is the request size threshold for using mmap()
1437   to service a request. Requests of at least this size that cannot
1438   be allocated using already-existing space will be serviced via mmap.
1439   (If enough normal freed space already exists it is used instead.)
1440
1441   Using mmap segregates relatively large chunks of memory so that
1442   they can be individually obtained and released from the host
1443   system. A request serviced through mmap is never reused by any
1444   other request (at least not directly; the system may just so
1445   happen to remap successive requests to the same locations).
1446
1447   Segregating space in this way has the benefits that:
1448
1449    1. Mmapped space can ALWAYS be individually released back
1450       to the system, which helps keep the system level memory
1451       demands of a long-lived program low.
1452    2. Mapped memory can never become `locked' between
1453       other chunks, as can happen with normally allocated chunks, which
1454       means that even trimming via malloc_trim would not release them.
1455    3. On some systems with "holes" in address spaces, mmap can obtain
1456       memory that sbrk cannot.
1457
1458   However, it has the disadvantages that:
1459
1460    1. The space cannot be reclaimed, consolidated, and then
1461       used to service later requests, as happens with normal chunks.
1462    2. It can lead to more wastage because of mmap page alignment
1463       requirements
1464    3. It causes malloc performance to be more dependent on host
1465       system memory management support routines which may vary in
1466       implementation quality and may impose arbitrary
1467       limitations. Generally, servicing a request via normal
1468       malloc steps is faster than going through a system's mmap.
1469
1470   The advantages of mmap nearly always outweigh disadvantages for
1471   "large" chunks, but the value of "large" varies across systems.  The
1472   default is an empirically derived value that works well in most
1473   systems.
1474
1475
1476   Update in 2006:
1477   The above was written in 2001. Since then the world has changed a lot.
1478   Memory got bigger. Applications got bigger. The virtual address space
1479   layout in 32 bit linux changed.
1480
1481   In the new situation, brk() and mmap space is shared and there are no
1482   artificial limits on brk size imposed by the kernel. What is more,
1483   applications have started using transient allocations larger than the
1484   128Kb as was imagined in 2001.
1485
1486   The price for mmap is also high now; each time glibc mmaps from the
1487   kernel, the kernel is forced to zero out the memory it gives to the
1488   application. Zeroing memory is expensive and eats a lot of cache and
1489   memory bandwidth. This has nothing to do with the efficiency of the
1490   virtual memory system, by doing mmap the kernel just has no choice but
1491   to zero.
1492
1493   In 2001, the kernel had a maximum size for brk() which was about 800
1494   megabytes on 32 bit x86, at that point brk() would hit the first
1495   mmaped shared libaries and couldn't expand anymore. With current 2.6
1496   kernels, the VA space layout is different and brk() and mmap
1497   both can span the entire heap at will.
1498
1499   Rather than using a static threshold for the brk/mmap tradeoff,
1500   we are now using a simple dynamic one. The goal is still to avoid
1501   fragmentation. The old goals we kept are
1502   1) try to get the long lived large allocations to use mmap()
1503   2) really large allocations should always use mmap()
1504   and we're adding now:
1505   3) transient allocations should use brk() to avoid forcing the kernel
1506      having to zero memory over and over again
1507
1508   The implementation works with a sliding threshold, which is by default
1509   limited to go between 128Kb and 32Mb (64Mb for 64 bitmachines) and starts
1510   out at 128Kb as per the 2001 default.
1511
1512   This allows us to satisfy requirement 1) under the assumption that long
1513   lived allocations are made early in the process' lifespan, before it has
1514   started doing dynamic allocations of the same size (which will
1515   increase the threshold).
1516
1517   The upperbound on the threshold satisfies requirement 2)
1518
1519   The threshold goes up in value when the application frees memory that was
1520   allocated with the mmap allocator. The idea is that once the application
1521   starts freeing memory of a certain size, it's highly probable that this is
1522   a size the application uses for transient allocations. This estimator
1523   is there to satisfy the new third requirement.
1524
1525 */
1526
1527 #define M_MMAP_THRESHOLD      -3
1528
1529 #ifndef DEFAULT_MMAP_THRESHOLD
1530 #define DEFAULT_MMAP_THRESHOLD DEFAULT_MMAP_THRESHOLD_MIN
1531 #endif
1532
1533 /*
1534   M_MMAP_MAX is the maximum number of requests to simultaneously
1535   service using mmap. This parameter exists because
1536   some systems have a limited number of internal tables for
1537   use by mmap, and using more than a few of them may degrade
1538   performance.
1539
1540   The default is set to a value that serves only as a safeguard.
1541   Setting to 0 disables use of mmap for servicing large requests.  If
1542   HAVE_MMAP is not set, the default value is 0, and attempts to set it
1543   to non-zero values in mallopt will fail.
1544 */
1545
1546 #define M_MMAP_MAX             -4
1547
1548 #ifndef DEFAULT_MMAP_MAX
1549 #if HAVE_MMAP
1550 #define DEFAULT_MMAP_MAX       (65536)
1551 #else
1552 #define DEFAULT_MMAP_MAX       (0)
1553 #endif
1554 #endif
1555
1556 #ifdef __cplusplus
1557 } /* end of extern "C" */
1558 #endif
1559
1560 #include <malloc.h>
1561
1562 #ifndef BOUNDED_N
1563 #define BOUNDED_N(ptr, sz) (ptr)
1564 #endif
1565 #ifndef RETURN_ADDRESS
1566 #define RETURN_ADDRESS(X_) (NULL)
1567 #endif
1568
1569 /* On some platforms we can compile internal, not exported functions better.
1570    Let the environment provide a macro and define it to be empty if it
1571    is not available.  */
1572 #ifndef internal_function
1573 # define internal_function
1574 #endif
1575
1576 /* Forward declarations.  */
1577 struct malloc_chunk;
1578 typedef struct malloc_chunk* mchunkptr;
1579
1580 /* Internal routines.  */
1581
1582 #if __STD_C
1583
1584 Void_t*         _int_malloc(mstate, size_t);
1585 void            _int_free(mstate, Void_t*);
1586 Void_t*         _int_realloc(mstate, Void_t*, size_t);
1587 Void_t*         _int_memalign(mstate, size_t, size_t);
1588 Void_t*         _int_valloc(mstate, size_t);
1589 static Void_t*  _int_pvalloc(mstate, size_t);
1590 /*static Void_t*  cALLOc(size_t, size_t);*/
1591 #ifndef _LIBC
1592 static Void_t** _int_icalloc(mstate, size_t, size_t, Void_t**);
1593 static Void_t** _int_icomalloc(mstate, size_t, size_t*, Void_t**);
1594 #endif
1595 static int      mTRIm(size_t);
1596 static size_t   mUSABLe(Void_t*);
1597 static void     mSTATs(void);
1598 static int      mALLOPt(int, int);
1599 static struct mallinfo mALLINFo(mstate);
1600 static void malloc_printerr(int action, const char *str, void *ptr);
1601
1602 static Void_t* internal_function mem2mem_check(Void_t *p, size_t sz);
1603 static int internal_function top_check(void);
1604 static void internal_function munmap_chunk(mchunkptr p);
1605 #if HAVE_MREMAP
1606 static mchunkptr internal_function mremap_chunk(mchunkptr p, size_t new_size);
1607 #endif
1608
1609 static Void_t*   malloc_check(size_t sz, const Void_t *caller);
1610 static void      free_check(Void_t* mem, const Void_t *caller);
1611 static Void_t*   realloc_check(Void_t* oldmem, size_t bytes,
1612                                const Void_t *caller);
1613 static Void_t*   memalign_check(size_t alignment, size_t bytes,
1614                                 const Void_t *caller);
1615 #ifndef NO_THREADS
1616 # ifdef _LIBC
1617 #  if USE___THREAD || !defined SHARED
1618     /* These routines are never needed in this configuration.  */
1619 #   define NO_STARTER
1620 #  endif
1621 # endif
1622 # ifdef NO_STARTER
1623 #  undef NO_STARTER
1624 # else
1625 static Void_t*   malloc_starter(size_t sz, const Void_t *caller);
1626 static Void_t*   memalign_starter(size_t aln, size_t sz, const Void_t *caller);
1627 static void      free_starter(Void_t* mem, const Void_t *caller);
1628 # endif
1629 static Void_t*   malloc_atfork(size_t sz, const Void_t *caller);
1630 static void      free_atfork(Void_t* mem, const Void_t *caller);
1631 #endif
1632
1633 #else
1634
1635 Void_t*         _int_malloc();
1636 void            _int_free();
1637 Void_t*         _int_realloc();
1638 Void_t*         _int_memalign();
1639 Void_t*         _int_valloc();
1640 Void_t*         _int_pvalloc();
1641 /*static Void_t*  cALLOc();*/
1642 static Void_t** _int_icalloc();
1643 static Void_t** _int_icomalloc();
1644 static int      mTRIm();
1645 static size_t   mUSABLe();
1646 static void     mSTATs();
1647 static int      mALLOPt();
1648 static struct mallinfo mALLINFo();
1649
1650 #endif
1651
1652
1653
1654
1655 /* ------------- Optional versions of memcopy ---------------- */
1656
1657
1658 #if USE_MEMCPY
1659
1660 /*
1661   Note: memcpy is ONLY invoked with non-overlapping regions,
1662   so the (usually slower) memmove is not needed.
1663 */
1664
1665 #define MALLOC_COPY(dest, src, nbytes)  memcpy(dest, src, nbytes)
1666 #define MALLOC_ZERO(dest, nbytes)       memset(dest, 0,   nbytes)
1667
1668 #else /* !USE_MEMCPY */
1669
1670 /* Use Duff's device for good zeroing/copying performance. */
1671
1672 #define MALLOC_ZERO(charp, nbytes)                                            \
1673 do {                                                                          \
1674   INTERNAL_SIZE_T* mzp = (INTERNAL_SIZE_T*)(charp);                           \
1675   unsigned long mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T);                     \
1676   long mcn;                                                                   \
1677   if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; }             \
1678   switch (mctmp) {                                                            \
1679     case 0: for(;;) { *mzp++ = 0;                                             \
1680     case 7:           *mzp++ = 0;                                             \
1681     case 6:           *mzp++ = 0;                                             \
1682     case 5:           *mzp++ = 0;                                             \
1683     case 4:           *mzp++ = 0;                                             \
1684     case 3:           *mzp++ = 0;                                             \
1685     case 2:           *mzp++ = 0;                                             \
1686     case 1:           *mzp++ = 0; if(mcn <= 0) break; mcn--; }                \
1687   }                                                                           \
1688 } while(0)
1689
1690 #define MALLOC_COPY(dest,src,nbytes)                                          \
1691 do {                                                                          \
1692   INTERNAL_SIZE_T* mcsrc = (INTERNAL_SIZE_T*) src;                            \
1693   INTERNAL_SIZE_T* mcdst = (INTERNAL_SIZE_T*) dest;                           \
1694   unsigned long mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T);                     \
1695   long mcn;                                                                   \
1696   if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; }             \
1697   switch (mctmp) {                                                            \
1698     case 0: for(;;) { *mcdst++ = *mcsrc++;                                    \
1699     case 7:           *mcdst++ = *mcsrc++;                                    \
1700     case 6:           *mcdst++ = *mcsrc++;                                    \
1701     case 5:           *mcdst++ = *mcsrc++;                                    \
1702     case 4:           *mcdst++ = *mcsrc++;                                    \
1703     case 3:           *mcdst++ = *mcsrc++;                                    \
1704     case 2:           *mcdst++ = *mcsrc++;                                    \
1705     case 1:           *mcdst++ = *mcsrc++; if(mcn <= 0) break; mcn--; }       \
1706   }                                                                           \
1707 } while(0)
1708
1709 #endif
1710
1711 /* ------------------ MMAP support ------------------  */
1712
1713
1714 #if HAVE_MMAP
1715
1716 #include <fcntl.h>
1717 #ifndef LACKS_SYS_MMAN_H
1718 #include <sys/mman.h>
1719 #endif
1720
1721 #if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
1722 # define MAP_ANONYMOUS MAP_ANON
1723 #endif
1724 #if !defined(MAP_FAILED)
1725 # define MAP_FAILED ((char*)-1)
1726 #endif
1727
1728 #ifndef MAP_NORESERVE
1729 # ifdef MAP_AUTORESRV
1730 #  define MAP_NORESERVE MAP_AUTORESRV
1731 # else
1732 #  define MAP_NORESERVE 0
1733 # endif
1734 #endif
1735
1736 /*
1737    Nearly all versions of mmap support MAP_ANONYMOUS,
1738    so the following is unlikely to be needed, but is
1739    supplied just in case.
1740 */
1741
1742 #ifndef MAP_ANONYMOUS
1743
1744 static int dev_zero_fd = -1; /* Cached file descriptor for /dev/zero. */
1745
1746 #define MMAP(addr, size, prot, flags) ((dev_zero_fd < 0) ? \
1747  (dev_zero_fd = open("/dev/zero", O_RDWR), \
1748   mmap((addr), (size), (prot), (flags), dev_zero_fd, 0)) : \
1749    mmap((addr), (size), (prot), (flags), dev_zero_fd, 0))
1750
1751 #else
1752
1753 #define MMAP(addr, size, prot, flags) \
1754  (mmap((addr), (size), (prot), (flags)|MAP_ANONYMOUS, -1, 0))
1755
1756 #endif
1757
1758
1759 #endif /* HAVE_MMAP */
1760
1761
1762 /*
1763   -----------------------  Chunk representations -----------------------
1764 */
1765
1766
1767 /*
1768   This struct declaration is misleading (but accurate and necessary).
1769   It declares a "view" into memory allowing access to necessary
1770   fields at known offsets from a given base. See explanation below.
1771 */
1772
1773 struct malloc_chunk {
1774
1775   INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
1776   INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */
1777
1778   struct malloc_chunk* fd;         /* double links -- used only if free. */
1779   struct malloc_chunk* bk;
1780
1781   /* Only used for large blocks: pointer to next larger size.  */
1782   struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
1783   struct malloc_chunk* bk_nextsize;
1784 };
1785
1786
1787 /*
1788    malloc_chunk details:
1789
1790     (The following includes lightly edited explanations by Colin Plumb.)
1791
1792     Chunks of memory are maintained using a `boundary tag' method as
1793     described in e.g., Knuth or Standish.  (See the paper by Paul
1794     Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a
1795     survey of such techniques.)  Sizes of free chunks are stored both
1796     in the front of each chunk and at the end.  This makes
1797     consolidating fragmented chunks into bigger chunks very fast.  The
1798     size fields also hold bits representing whether chunks are free or
1799     in use.
1800
1801     An allocated chunk looks like this:
1802
1803
1804     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1805             |             Size of previous chunk, if allocated            | |
1806             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1807             |             Size of chunk, in bytes                       |M|P|
1808       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1809             |             User data starts here...                          .
1810             .                                                               .
1811             .             (malloc_usable_size() bytes)                      .
1812             .                                                               |
1813 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1814             |             Size of chunk                                     |
1815             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1816
1817
1818     Where "chunk" is the front of the chunk for the purpose of most of
1819     the malloc code, but "mem" is the pointer that is returned to the
1820     user.  "Nextchunk" is the beginning of the next contiguous chunk.
1821
1822     Chunks always begin on even word boundries, so the mem portion
1823     (which is returned to the user) is also on an even word boundary, and
1824     thus at least double-word aligned.
1825
1826     Free chunks are stored in circular doubly-linked lists, and look like this:
1827
1828     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1829             |             Size of previous chunk                            |
1830             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1831     `head:' |             Size of chunk, in bytes                         |P|
1832       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1833             |             Forward pointer to next chunk in list             |
1834             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1835             |             Back pointer to previous chunk in list            |
1836             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1837             |             Unused space (may be 0 bytes long)                .
1838             .                                                               .
1839             .                                                               |
1840 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1841     `foot:' |             Size of chunk, in bytes                           |
1842             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1843
1844     The P (PREV_INUSE) bit, stored in the unused low-order bit of the
1845     chunk size (which is always a multiple of two words), is an in-use
1846     bit for the *previous* chunk.  If that bit is *clear*, then the
1847     word before the current chunk size contains the previous chunk
1848     size, and can be used to find the front of the previous chunk.
1849     The very first chunk allocated always has this bit set,
1850     preventing access to non-existent (or non-owned) memory. If
1851     prev_inuse is set for any given chunk, then you CANNOT determine
1852     the size of the previous chunk, and might even get a memory
1853     addressing fault when trying to do so.
1854
1855     Note that the `foot' of the current chunk is actually represented
1856     as the prev_size of the NEXT chunk. This makes it easier to
1857     deal with alignments etc but can be very confusing when trying
1858     to extend or adapt this code.
1859
1860     The two exceptions to all this are
1861
1862      1. The special chunk `top' doesn't bother using the
1863         trailing size field since there is no next contiguous chunk
1864         that would have to index off it. After initialization, `top'
1865         is forced to always exist.  If it would become less than
1866         MINSIZE bytes long, it is replenished.
1867
1868      2. Chunks allocated via mmap, which have the second-lowest-order
1869         bit M (IS_MMAPPED) set in their size fields.  Because they are
1870         allocated one-by-one, each must contain its own trailing size field.
1871
1872 */
1873
1874 /*
1875   ---------- Size and alignment checks and conversions ----------
1876 */
1877
1878 /* conversion from malloc headers to user pointers, and back */
1879
1880 #define chunk2mem(p)   ((Void_t*)((char*)(p) + 2*SIZE_SZ))
1881 #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))
1882
1883 /* The smallest possible chunk */
1884 #define MIN_CHUNK_SIZE        (offsetof(struct malloc_chunk, fd_nextsize))
1885
1886 /* The smallest size we can malloc is an aligned minimal chunk */
1887
1888 #define MINSIZE  \
1889   (unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))
1890
1891 /* Check if m has acceptable alignment */
1892
1893 #define aligned_OK(m)  (((unsigned long)(m) & MALLOC_ALIGN_MASK) == 0)
1894
1895 #define misaligned_chunk(p) \
1896   ((uintptr_t)(MALLOC_ALIGNMENT == 2 * SIZE_SZ ? (p) : chunk2mem (p)) \
1897    & MALLOC_ALIGN_MASK)
1898
1899
1900 /*
1901    Check if a request is so large that it would wrap around zero when
1902    padded and aligned. To simplify some other code, the bound is made
1903    low enough so that adding MINSIZE will also not wrap around zero.
1904 */
1905
1906 #define REQUEST_OUT_OF_RANGE(req)                                 \
1907   ((unsigned long)(req) >=                                        \
1908    (unsigned long)(INTERNAL_SIZE_T)(-2 * MINSIZE))
1909
1910 /* pad request bytes into a usable size -- internal version */
1911
1912 #define request2size(req)                                         \
1913   (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE)  ?             \
1914    MINSIZE :                                                      \
1915    ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
1916
1917 /*  Same, except also perform argument check */
1918
1919 #define checked_request2size(req, sz)                             \
1920   if (REQUEST_OUT_OF_RANGE(req)) {                                \
1921     MALLOC_FAILURE_ACTION;                                        \
1922     return 0;                                                     \
1923   }                                                               \
1924   (sz) = request2size(req);
1925
1926 /*
1927   --------------- Physical chunk operations ---------------
1928 */
1929
1930
1931 /* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
1932 #define PREV_INUSE 0x1
1933
1934 /* extract inuse bit of previous chunk */
1935 #define prev_inuse(p)       ((p)->size & PREV_INUSE)
1936
1937
1938 /* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */
1939 #define IS_MMAPPED 0x2
1940
1941 /* check for mmap()'ed chunk */
1942 #define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)
1943
1944
1945 /* size field is or'ed with NON_MAIN_ARENA if the chunk was obtained
1946    from a non-main arena.  This is only set immediately before handing
1947    the chunk to the user, if necessary.  */
1948 #define NON_MAIN_ARENA 0x4
1949
1950 /* check for chunk from non-main arena */
1951 #define chunk_non_main_arena(p) ((p)->size & NON_MAIN_ARENA)
1952
1953
1954 /*
1955   Bits to mask off when extracting size
1956
1957   Note: IS_MMAPPED is intentionally not masked off from size field in
1958   macros for which mmapped chunks should never be seen. This should
1959   cause helpful core dumps to occur if it is tried by accident by
1960   people extending or adapting this malloc.
1961 */
1962 #define SIZE_BITS (PREV_INUSE|IS_MMAPPED|NON_MAIN_ARENA)
1963
1964 /* Get size, ignoring use bits */
1965 #define chunksize(p)         ((p)->size & ~(SIZE_BITS))
1966
1967
1968 /* Ptr to next physical malloc_chunk. */
1969 #define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->size & ~SIZE_BITS) ))
1970
1971 /* Ptr to previous physical malloc_chunk */
1972 #define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_size) ))
1973
1974 /* Treat space at ptr + offset as a chunk */
1975 #define chunk_at_offset(p, s)  ((mchunkptr)(((char*)(p)) + (s)))
1976
1977 /* extract p's inuse bit */
1978 #define inuse(p)\
1979 ((((mchunkptr)(((char*)(p))+((p)->size & ~SIZE_BITS)))->size) & PREV_INUSE)
1980
1981 /* set/clear chunk as being inuse without otherwise disturbing */
1982 #define set_inuse(p)\
1983 ((mchunkptr)(((char*)(p)) + ((p)->size & ~SIZE_BITS)))->size |= PREV_INUSE
1984
1985 #define clear_inuse(p)\
1986 ((mchunkptr)(((char*)(p)) + ((p)->size & ~SIZE_BITS)))->size &= ~(PREV_INUSE)
1987
1988
1989 /* check/set/clear inuse bits in known places */
1990 #define inuse_bit_at_offset(p, s)\
1991  (((mchunkptr)(((char*)(p)) + (s)))->size & PREV_INUSE)
1992
1993 #define set_inuse_bit_at_offset(p, s)\
1994  (((mchunkptr)(((char*)(p)) + (s)))->size |= PREV_INUSE)
1995
1996 #define clear_inuse_bit_at_offset(p, s)\
1997  (((mchunkptr)(((char*)(p)) + (s)))->size &= ~(PREV_INUSE))
1998
1999
2000 /* Set size at head, without disturbing its use bit */
2001 #define set_head_size(p, s)  ((p)->size = (((p)->size & SIZE_BITS) | (s)))
2002
2003 /* Set size/use field */
2004 #define set_head(p, s)       ((p)->size = (s))
2005
2006 /* Set size at footer (only when chunk is not in use) */
2007 #define set_foot(p, s)       (((mchunkptr)((char*)(p) + (s)))->prev_size = (s))
2008
2009
2010 /*
2011   -------------------- Internal data structures --------------------
2012
2013    All internal state is held in an instance of malloc_state defined
2014    below. There are no other static variables, except in two optional
2015    cases:
2016    * If USE_MALLOC_LOCK is defined, the mALLOC_MUTEx declared above.
2017    * If HAVE_MMAP is true, but mmap doesn't support
2018      MAP_ANONYMOUS, a dummy file descriptor for mmap.
2019
2020    Beware of lots of tricks that minimize the total bookkeeping space
2021    requirements. The result is a little over 1K bytes (for 4byte
2022    pointers and size_t.)
2023 */
2024
2025 /*
2026   Bins
2027
2028     An array of bin headers for free chunks. Each bin is doubly
2029     linked.  The bins are approximately proportionally (log) spaced.
2030     There are a lot of these bins (128). This may look excessive, but
2031     works very well in practice.  Most bins hold sizes that are
2032     unusual as malloc request sizes, but are more usual for fragments
2033     and consolidated sets of chunks, which is what these bins hold, so
2034     they can be found quickly.  All procedures maintain the invariant
2035     that no consolidated chunk physically borders another one, so each
2036     chunk in a list is known to be preceeded and followed by either
2037     inuse chunks or the ends of memory.
2038
2039     Chunks in bins are kept in size order, with ties going to the
2040     approximately least recently used chunk. Ordering isn't needed
2041     for the small bins, which all contain the same-sized chunks, but
2042     facilitates best-fit allocation for larger chunks. These lists
2043     are just sequential. Keeping them in order almost never requires
2044     enough traversal to warrant using fancier ordered data
2045     structures.
2046
2047     Chunks of the same size are linked with the most
2048     recently freed at the front, and allocations are taken from the
2049     back.  This results in LRU (FIFO) allocation order, which tends
2050     to give each chunk an equal opportunity to be consolidated with
2051     adjacent freed chunks, resulting in larger free chunks and less
2052     fragmentation.
2053
2054     To simplify use in double-linked lists, each bin header acts
2055     as a malloc_chunk. This avoids special-casing for headers.
2056     But to conserve space and improve locality, we allocate
2057     only the fd/bk pointers of bins, and then use repositioning tricks
2058     to treat these as the fields of a malloc_chunk*.
2059 */
2060
2061 typedef struct malloc_chunk* mbinptr;
2062
2063 /* addressing -- note that bin_at(0) does not exist */
2064 #define bin_at(m, i) \
2065   (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2]))                           \
2066              - offsetof (struct malloc_chunk, fd))
2067
2068 /* analog of ++bin */
2069 #define next_bin(b)  ((mbinptr)((char*)(b) + (sizeof(mchunkptr)<<1)))
2070
2071 /* Reminders about list directionality within bins */
2072 #define first(b)     ((b)->fd)
2073 #define last(b)      ((b)->bk)
2074
2075 /* Take a chunk off a bin list */
2076 #define unlink(P, BK, FD) {                                            \
2077   FD = P->fd;                                                          \
2078   BK = P->bk;                                                          \
2079   if (__builtin_expect (FD->bk != P || BK->fd != P, 0))                \
2080     malloc_printerr (check_action, "corrupted double-linked list", P); \
2081   else {                                                               \
2082     FD->bk = BK;                                                       \
2083     BK->fd = FD;                                                       \
2084     if (!in_smallbin_range (P->size)                                   \
2085         && __builtin_expect (P->fd_nextsize != NULL, 0)) {             \
2086       assert (P->fd_nextsize->bk_nextsize == P);                       \
2087       assert (P->bk_nextsize->fd_nextsize == P);                       \
2088       if (FD->fd_nextsize == NULL) {                                   \
2089         if (P->fd_nextsize == P)                                       \
2090           FD->fd_nextsize = FD->bk_nextsize = FD;                      \
2091         else {                                                         \
2092           FD->fd_nextsize = P->fd_nextsize;                            \
2093           FD->bk_nextsize = P->bk_nextsize;                            \
2094           P->fd_nextsize->bk_nextsize = FD;                            \
2095           P->bk_nextsize->fd_nextsize = FD;                            \
2096         }                                                              \
2097       } else {                                                         \
2098         P->fd_nextsize->bk_nextsize = P->bk_nextsize;                  \
2099         P->bk_nextsize->fd_nextsize = P->fd_nextsize;                  \
2100       }                                                                \
2101     }                                                                  \
2102   }                                                                    \
2103 }
2104
2105 /*
2106   Indexing
2107
2108     Bins for sizes < 512 bytes contain chunks of all the same size, spaced
2109     8 bytes apart. Larger bins are approximately logarithmically spaced:
2110
2111     64 bins of size       8
2112     32 bins of size      64
2113     16 bins of size     512
2114      8 bins of size    4096
2115      4 bins of size   32768
2116      2 bins of size  262144
2117      1 bin  of size what's left
2118
2119     There is actually a little bit of slop in the numbers in bin_index
2120     for the sake of speed. This makes no difference elsewhere.
2121
2122     The bins top out around 1MB because we expect to service large
2123     requests via mmap.
2124 */
2125
2126 #define NBINS             128
2127 #define NSMALLBINS         64
2128 #define SMALLBIN_WIDTH    MALLOC_ALIGNMENT
2129 #define MIN_LARGE_SIZE    (NSMALLBINS * SMALLBIN_WIDTH)
2130
2131 #define in_smallbin_range(sz)  \
2132   ((unsigned long)(sz) < (unsigned long)MIN_LARGE_SIZE)
2133
2134 #define smallbin_index(sz) \
2135   (SMALLBIN_WIDTH == 16 ? (((unsigned)(sz)) >> 4) : (((unsigned)(sz)) >> 3))
2136
2137 #define largebin_index_32(sz)                                                \
2138 (((((unsigned long)(sz)) >>  6) <= 38)?  56 + (((unsigned long)(sz)) >>  6): \
2139  ((((unsigned long)(sz)) >>  9) <= 20)?  91 + (((unsigned long)(sz)) >>  9): \
2140  ((((unsigned long)(sz)) >> 12) <= 10)? 110 + (((unsigned long)(sz)) >> 12): \
2141  ((((unsigned long)(sz)) >> 15) <=  4)? 119 + (((unsigned long)(sz)) >> 15): \
2142  ((((unsigned long)(sz)) >> 18) <=  2)? 124 + (((unsigned long)(sz)) >> 18): \
2143                                         126)
2144
2145 // XXX It remains to be seen whether it is good to keep the widths of
2146 // XXX the buckets the same or whether it should be scaled by a factor
2147 // XXX of two as well.
2148 #define largebin_index_64(sz)                                                \
2149 (((((unsigned long)(sz)) >>  6) <= 48)?  48 + (((unsigned long)(sz)) >>  6): \
2150  ((((unsigned long)(sz)) >>  9) <= 20)?  91 + (((unsigned long)(sz)) >>  9): \
2151  ((((unsigned long)(sz)) >> 12) <= 10)? 110 + (((unsigned long)(sz)) >> 12): \
2152  ((((unsigned long)(sz)) >> 15) <=  4)? 119 + (((unsigned long)(sz)) >> 15): \
2153  ((((unsigned long)(sz)) >> 18) <=  2)? 124 + (((unsigned long)(sz)) >> 18): \
2154                                         126)
2155
2156 #define largebin_index(sz) \
2157   (SIZE_SZ == 8 ? largebin_index_64 (sz) : largebin_index_32 (sz))
2158
2159 #define bin_index(sz) \
2160  ((in_smallbin_range(sz)) ? smallbin_index(sz) : largebin_index(sz))
2161
2162
2163 /*
2164   Unsorted chunks
2165
2166     All remainders from chunk splits, as well as all returned chunks,
2167     are first placed in the "unsorted" bin. They are then placed
2168     in regular bins after malloc gives them ONE chance to be used before
2169     binning. So, basically, the unsorted_chunks list acts as a queue,
2170     with chunks being placed on it in free (and malloc_consolidate),
2171     and taken off (to be either used or placed in bins) in malloc.
2172
2173     The NON_MAIN_ARENA flag is never set for unsorted chunks, so it
2174     does not have to be taken into account in size comparisons.
2175 */
2176
2177 /* The otherwise unindexable 1-bin is used to hold unsorted chunks. */
2178 #define unsorted_chunks(M)          (bin_at(M, 1))
2179
2180 /*
2181   Top
2182
2183     The top-most available chunk (i.e., the one bordering the end of
2184     available memory) is treated specially. It is never included in
2185     any bin, is used only if no other chunk is available, and is
2186     released back to the system if it is very large (see
2187     M_TRIM_THRESHOLD).  Because top initially
2188     points to its own bin with initial zero size, thus forcing
2189     extension on the first malloc request, we avoid having any special
2190     code in malloc to check whether it even exists yet. But we still
2191     need to do so when getting memory from system, so we make
2192     initial_top treat the bin as a legal but unusable chunk during the
2193     interval between initialization and the first call to
2194     sYSMALLOc. (This is somewhat delicate, since it relies on
2195     the 2 preceding words to be zero during this interval as well.)
2196 */
2197
2198 /* Conveniently, the unsorted bin can be used as dummy top on first call */
2199 #define initial_top(M)              (unsorted_chunks(M))
2200
2201 /*
2202   Binmap
2203
2204     To help compensate for the large number of bins, a one-level index
2205     structure is used for bin-by-bin searching.  `binmap' is a
2206     bitvector recording whether bins are definitely empty so they can
2207     be skipped over during during traversals.  The bits are NOT always
2208     cleared as soon as bins are empty, but instead only
2209     when they are noticed to be empty during traversal in malloc.
2210 */
2211
2212 /* Conservatively use 32 bits per map word, even if on 64bit system */
2213 #define BINMAPSHIFT      5
2214 #define BITSPERMAP       (1U << BINMAPSHIFT)
2215 #define BINMAPSIZE       (NBINS / BITSPERMAP)
2216
2217 #define idx2block(i)     ((i) >> BINMAPSHIFT)
2218 #define idx2bit(i)       ((1U << ((i) & ((1U << BINMAPSHIFT)-1))))
2219
2220 #define mark_bin(m,i)    ((m)->binmap[idx2block(i)] |=  idx2bit(i))
2221 #define unmark_bin(m,i)  ((m)->binmap[idx2block(i)] &= ~(idx2bit(i)))
2222 #define get_binmap(m,i)  ((m)->binmap[idx2block(i)] &   idx2bit(i))
2223
2224 /*
2225   Fastbins
2226
2227     An array of lists holding recently freed small chunks.  Fastbins
2228     are not doubly linked.  It is faster to single-link them, and
2229     since chunks are never removed from the middles of these lists,
2230     double linking is not necessary. Also, unlike regular bins, they
2231     are not even processed in FIFO order (they use faster LIFO) since
2232     ordering doesn't much matter in the transient contexts in which
2233     fastbins are normally used.
2234
2235     Chunks in fastbins keep their inuse bit set, so they cannot
2236     be consolidated with other free chunks. malloc_consolidate
2237     releases all chunks in fastbins and consolidates them with
2238     other free chunks.
2239 */
2240
2241 typedef struct malloc_chunk* mfastbinptr;
2242
2243 /* offset 2 to use otherwise unindexable first 2 bins */
2244 #define fastbin_index(sz)        ((((unsigned int)(sz)) >> 3) - 2)
2245
2246 /* The maximum fastbin request size we support */
2247 #define MAX_FAST_SIZE     80
2248
2249 #define NFASTBINS  (fastbin_index(request2size(MAX_FAST_SIZE))+1)
2250
2251 /*
2252   FASTBIN_CONSOLIDATION_THRESHOLD is the size of a chunk in free()
2253   that triggers automatic consolidation of possibly-surrounding
2254   fastbin chunks. This is a heuristic, so the exact value should not
2255   matter too much. It is defined at half the default trim threshold as a
2256   compromise heuristic to only attempt consolidation if it is likely
2257   to lead to trimming. However, it is not dynamically tunable, since
2258   consolidation reduces fragmentation surrounding large chunks even
2259   if trimming is not used.
2260 */
2261
2262 #define FASTBIN_CONSOLIDATION_THRESHOLD  (65536UL)
2263
2264 /*
2265   Since the lowest 2 bits in max_fast don't matter in size comparisons,
2266   they are used as flags.
2267 */
2268
2269 /*
2270   FASTCHUNKS_BIT held in max_fast indicates that there are probably
2271   some fastbin chunks. It is set true on entering a chunk into any
2272   fastbin, and cleared only in malloc_consolidate.
2273
2274   The truth value is inverted so that have_fastchunks will be true
2275   upon startup (since statics are zero-filled), simplifying
2276   initialization checks.
2277 */
2278
2279 #define FASTCHUNKS_BIT        (1U)
2280
2281 #define have_fastchunks(M)     (((M)->flags &  FASTCHUNKS_BIT) == 0)
2282 #define clear_fastchunks(M)    ((M)->flags |=  FASTCHUNKS_BIT)
2283 #define set_fastchunks(M)      ((M)->flags &= ~FASTCHUNKS_BIT)
2284
2285 /*
2286   NONCONTIGUOUS_BIT indicates that MORECORE does not return contiguous
2287   regions.  Otherwise, contiguity is exploited in merging together,
2288   when possible, results from consecutive MORECORE calls.
2289
2290   The initial value comes from MORECORE_CONTIGUOUS, but is
2291   changed dynamically if mmap is ever used as an sbrk substitute.
2292 */
2293
2294 #define NONCONTIGUOUS_BIT     (2U)
2295
2296 #define contiguous(M)          (((M)->flags &  NONCONTIGUOUS_BIT) == 0)
2297 #define noncontiguous(M)       (((M)->flags &  NONCONTIGUOUS_BIT) != 0)
2298 #define set_noncontiguous(M)   ((M)->flags |=  NONCONTIGUOUS_BIT)
2299 #define set_contiguous(M)      ((M)->flags &= ~NONCONTIGUOUS_BIT)
2300
2301 /*
2302    Set value of max_fast.
2303    Use impossibly small value if 0.
2304    Precondition: there are no existing fastbin chunks.
2305    Setting the value clears fastchunk bit but preserves noncontiguous bit.
2306 */
2307
2308 #define set_max_fast(s) \
2309   global_max_fast = ((s) == 0)? SMALLBIN_WIDTH: request2size(s)
2310 #define get_max_fast() global_max_fast
2311
2312
2313 /*
2314    ----------- Internal state representation and initialization -----------
2315 */
2316
2317 struct malloc_state {
2318   /* Serialize access.  */
2319   mutex_t mutex;
2320
2321   /* Flags (formerly in max_fast).  */
2322   int flags;
2323
2324 #if THREAD_STATS
2325   /* Statistics for locking.  Only used if THREAD_STATS is defined.  */
2326   long stat_lock_direct, stat_lock_loop, stat_lock_wait;
2327 #endif
2328
2329   /* Fastbins */
2330   mfastbinptr      fastbins[NFASTBINS];
2331
2332   /* Base of the topmost chunk -- not otherwise kept in a bin */
2333   mchunkptr        top;
2334
2335   /* The remainder from the most recent split of a small request */
2336   mchunkptr        last_remainder;
2337
2338   /* Normal bins packed as described above */
2339   mchunkptr        bins[NBINS * 2 - 2];
2340
2341   /* Bitmap of bins */
2342   unsigned int     binmap[BINMAPSIZE];
2343
2344   /* Linked list */
2345   struct malloc_state *next;
2346
2347   /* Memory allocated from the system in this arena.  */
2348   INTERNAL_SIZE_T system_mem;
2349   INTERNAL_SIZE_T max_system_mem;
2350 };
2351
2352 struct malloc_par {
2353   /* Tunable parameters */
2354   unsigned long    trim_threshold;
2355   INTERNAL_SIZE_T  top_pad;
2356   INTERNAL_SIZE_T  mmap_threshold;
2357
2358   /* Memory map support */
2359   int              n_mmaps;
2360   int              n_mmaps_max;
2361   int              max_n_mmaps;
2362   /* the mmap_threshold is dynamic, until the user sets
2363      it manually, at which point we need to disable any
2364      dynamic behavior. */
2365   int              no_dyn_threshold;
2366
2367   /* Cache malloc_getpagesize */
2368   unsigned int     pagesize;
2369
2370   /* Statistics */
2371   INTERNAL_SIZE_T  mmapped_mem;
2372   /*INTERNAL_SIZE_T  sbrked_mem;*/
2373   /*INTERNAL_SIZE_T  max_sbrked_mem;*/
2374   INTERNAL_SIZE_T  max_mmapped_mem;
2375   INTERNAL_SIZE_T  max_total_mem; /* only kept for NO_THREADS */
2376
2377   /* First address handed out by MORECORE/sbrk.  */
2378   char*            sbrk_base;
2379 };
2380
2381 /* There are several instances of this struct ("arenas") in this
2382    malloc.  If you are adapting this malloc in a way that does NOT use
2383    a static or mmapped malloc_state, you MUST explicitly zero-fill it
2384    before using. This malloc relies on the property that malloc_state
2385    is initialized to all zeroes (as is true of C statics).  */
2386
2387 static struct malloc_state main_arena;
2388
2389 /* There is only one instance of the malloc parameters.  */
2390
2391 static struct malloc_par mp_;
2392
2393
2394 /* Maximum size of memory handled in fastbins.  */
2395 static INTERNAL_SIZE_T global_max_fast;
2396
2397 /*
2398   Initialize a malloc_state struct.
2399
2400   This is called only from within malloc_consolidate, which needs
2401   be called in the same contexts anyway.  It is never called directly
2402   outside of malloc_consolidate because some optimizing compilers try
2403   to inline it at all call points, which turns out not to be an
2404   optimization at all. (Inlining it in malloc_consolidate is fine though.)
2405 */
2406
2407 #if __STD_C
2408 static void malloc_init_state(mstate av)
2409 #else
2410 static void malloc_init_state(av) mstate av;
2411 #endif
2412 {
2413   int     i;
2414   mbinptr bin;
2415
2416   /* Establish circular links for normal bins */
2417   for (i = 1; i < NBINS; ++i) {
2418     bin = bin_at(av,i);
2419     bin->fd = bin->bk = bin;
2420   }
2421
2422 #if MORECORE_CONTIGUOUS
2423   if (av != &main_arena)
2424 #endif
2425     set_noncontiguous(av);
2426   if (av == &main_arena)
2427     set_max_fast(DEFAULT_MXFAST);
2428   av->flags |= FASTCHUNKS_BIT;
2429
2430   av->top            = initial_top(av);
2431 }
2432
2433 /*
2434    Other internal utilities operating on mstates
2435 */
2436
2437 #if __STD_C
2438 static Void_t*  sYSMALLOc(INTERNAL_SIZE_T, mstate);
2439 static int      sYSTRIm(size_t, mstate);
2440 static void     malloc_consolidate(mstate);
2441 #ifndef _LIBC
2442 static Void_t** iALLOc(mstate, size_t, size_t*, int, Void_t**);
2443 #endif
2444 #else
2445 static Void_t*  sYSMALLOc();
2446 static int      sYSTRIm();
2447 static void     malloc_consolidate();
2448 static Void_t** iALLOc();
2449 #endif
2450
2451
2452 /* -------------- Early definitions for debugging hooks ---------------- */
2453
2454 /* Define and initialize the hook variables.  These weak definitions must
2455    appear before any use of the variables in a function (arena.c uses one).  */
2456 #ifndef weak_variable
2457 #ifndef _LIBC
2458 #define weak_variable /**/
2459 #else
2460 /* In GNU libc we want the hook variables to be weak definitions to
2461    avoid a problem with Emacs.  */
2462 #define weak_variable weak_function
2463 #endif
2464 #endif
2465
2466 /* Forward declarations.  */
2467 static Void_t* malloc_hook_ini __MALLOC_P ((size_t sz,
2468                                             const __malloc_ptr_t caller));
2469 static Void_t* realloc_hook_ini __MALLOC_P ((Void_t* ptr, size_t sz,
2470                                              const __malloc_ptr_t caller));
2471 static Void_t* memalign_hook_ini __MALLOC_P ((size_t alignment, size_t sz,
2472                                               const __malloc_ptr_t caller));
2473
2474 void weak_variable (*__malloc_initialize_hook) (void) = NULL;
2475 void weak_variable (*__free_hook) (__malloc_ptr_t __ptr,
2476                                    const __malloc_ptr_t) = NULL;
2477 __malloc_ptr_t weak_variable (*__malloc_hook)
2478      (size_t __size, const __malloc_ptr_t) = malloc_hook_ini;
2479 __malloc_ptr_t weak_variable (*__realloc_hook)
2480      (__malloc_ptr_t __ptr, size_t __size, const __malloc_ptr_t)
2481      = realloc_hook_ini;
2482 __malloc_ptr_t weak_variable (*__memalign_hook)
2483      (size_t __alignment, size_t __size, const __malloc_ptr_t)
2484      = memalign_hook_ini;
2485 void weak_variable (*__after_morecore_hook) (void) = NULL;
2486
2487
2488 /* ---------------- Error behavior ------------------------------------ */
2489
2490 #ifndef DEFAULT_CHECK_ACTION
2491 #define DEFAULT_CHECK_ACTION 3
2492 #endif
2493
2494 static int check_action = DEFAULT_CHECK_ACTION;
2495
2496
2497 /* ------------------ Testing support ----------------------------------*/
2498
2499 static int perturb_byte;
2500
2501 #define alloc_perturb(p, n) memset (p, (perturb_byte ^ 0xff) & 0xff, n)
2502 #define free_perturb(p, n) memset (p, perturb_byte & 0xff, n)
2503
2504
2505 /* ------------------- Support for multiple arenas -------------------- */
2506 #include "arena.c"
2507
2508 /*
2509   Debugging support
2510
2511   These routines make a number of assertions about the states
2512   of data structures that should be true at all times. If any
2513   are not true, it's very likely that a user program has somehow
2514   trashed memory. (It's also possible that there is a coding error
2515   in malloc. In which case, please report it!)
2516 */
2517
2518 #if ! MALLOC_DEBUG
2519
2520 #define check_chunk(A,P)
2521 #define check_free_chunk(A,P)
2522 #define check_inuse_chunk(A,P)
2523 #define check_remalloced_chunk(A,P,N)
2524 #define check_malloced_chunk(A,P,N)
2525 #define check_malloc_state(A)
2526
2527 #else
2528
2529 #define check_chunk(A,P)              do_check_chunk(A,P)
2530 #define check_free_chunk(A,P)         do_check_free_chunk(A,P)
2531 #define check_inuse_chunk(A,P)        do_check_inuse_chunk(A,P)
2532 #define check_remalloced_chunk(A,P,N) do_check_remalloced_chunk(A,P,N)
2533 #define check_malloced_chunk(A,P,N)   do_check_malloced_chunk(A,P,N)
2534 #define check_malloc_state(A)         do_check_malloc_state(A)
2535
2536 /*
2537   Properties of all chunks
2538 */
2539
2540 #if __STD_C
2541 static void do_check_chunk(mstate av, mchunkptr p)
2542 #else
2543 static void do_check_chunk(av, p) mstate av; mchunkptr p;
2544 #endif
2545 {
2546   unsigned long sz = chunksize(p);
2547   /* min and max possible addresses assuming contiguous allocation */
2548   char* max_address = (char*)(av->top) + chunksize(av->top);
2549   char* min_address = max_address - av->system_mem;
2550
2551   if (!chunk_is_mmapped(p)) {
2552
2553     /* Has legal address ... */
2554     if (p != av->top) {
2555       if (contiguous(av)) {
2556         assert(((char*)p) >= min_address);
2557         assert(((char*)p + sz) <= ((char*)(av->top)));
2558       }
2559     }
2560     else {
2561       /* top size is always at least MINSIZE */
2562       assert((unsigned long)(sz) >= MINSIZE);
2563       /* top predecessor always marked inuse */
2564       assert(prev_inuse(p));
2565     }
2566
2567   }
2568   else {
2569 #if HAVE_MMAP
2570     /* address is outside main heap  */
2571     if (contiguous(av) && av->top != initial_top(av)) {
2572       assert(((char*)p) < min_address || ((char*)p) >= max_address);
2573     }
2574     /* chunk is page-aligned */
2575     assert(((p->prev_size + sz) & (mp_.pagesize-1)) == 0);
2576     /* mem is aligned */
2577     assert(aligned_OK(chunk2mem(p)));
2578 #else
2579     /* force an appropriate assert violation if debug set */
2580     assert(!chunk_is_mmapped(p));
2581 #endif
2582   }
2583 }
2584
2585 /*
2586   Properties of free chunks
2587 */
2588
2589 #if __STD_C
2590 static void do_check_free_chunk(mstate av, mchunkptr p)
2591 #else
2592 static void do_check_free_chunk(av, p) mstate av; mchunkptr p;
2593 #endif
2594 {
2595   INTERNAL_SIZE_T sz = p->size & ~(PREV_INUSE|NON_MAIN_ARENA);
2596   mchunkptr next = chunk_at_offset(p, sz);
2597
2598   do_check_chunk(av, p);
2599
2600   /* Chunk must claim to be free ... */
2601   assert(!inuse(p));
2602   assert (!chunk_is_mmapped(p));
2603
2604   /* Unless a special marker, must have OK fields */
2605   if ((unsigned long)(sz) >= MINSIZE)
2606   {
2607     assert((sz & MALLOC_ALIGN_MASK) == 0);
2608     assert(aligned_OK(chunk2mem(p)));
2609     /* ... matching footer field */
2610     assert(next->prev_size == sz);
2611     /* ... and is fully consolidated */
2612     assert(prev_inuse(p));
2613     assert (next == av->top || inuse(next));
2614
2615     /* ... and has minimally sane links */
2616     assert(p->fd->bk == p);
2617     assert(p->bk->fd == p);
2618   }
2619   else /* markers are always of size SIZE_SZ */
2620     assert(sz == SIZE_SZ);
2621 }
2622
2623 /*
2624   Properties of inuse chunks
2625 */
2626
2627 #if __STD_C
2628 static void do_check_inuse_chunk(mstate av, mchunkptr p)
2629 #else
2630 static void do_check_inuse_chunk(av, p) mstate av; mchunkptr p;
2631 #endif
2632 {
2633   mchunkptr next;
2634
2635   do_check_chunk(av, p);
2636
2637   if (chunk_is_mmapped(p))
2638     return; /* mmapped chunks have no next/prev */
2639
2640   /* Check whether it claims to be in use ... */
2641   assert(inuse(p));
2642
2643   next = next_chunk(p);
2644
2645   /* ... and is surrounded by OK chunks.
2646     Since more things can be checked with free chunks than inuse ones,
2647     if an inuse chunk borders them and debug is on, it's worth doing them.
2648   */
2649   if (!prev_inuse(p))  {
2650     /* Note that we cannot even look at prev unless it is not inuse */
2651     mchunkptr prv = prev_chunk(p);
2652     assert(next_chunk(prv) == p);
2653     do_check_free_chunk(av, prv);
2654   }
2655
2656   if (next == av->top) {
2657     assert(prev_inuse(next));
2658     assert(chunksize(next) >= MINSIZE);
2659   }
2660   else if (!inuse(next))
2661     do_check_free_chunk(av, next);
2662 }
2663
2664 /*
2665   Properties of chunks recycled from fastbins
2666 */
2667
2668 #if __STD_C
2669 static void do_check_remalloced_chunk(mstate av, mchunkptr p, INTERNAL_SIZE_T s)
2670 #else
2671 static void do_check_remalloced_chunk(av, p, s)
2672 mstate av; mchunkptr p; INTERNAL_SIZE_T s;
2673 #endif
2674 {
2675   INTERNAL_SIZE_T sz = p->size & ~(PREV_INUSE|NON_MAIN_ARENA);
2676
2677   if (!chunk_is_mmapped(p)) {
2678     assert(av == arena_for_chunk(p));
2679     if (chunk_non_main_arena(p))
2680       assert(av != &main_arena);
2681     else
2682       assert(av == &main_arena);
2683   }
2684
2685   do_check_inuse_chunk(av, p);
2686
2687   /* Legal size ... */
2688   assert((sz & MALLOC_ALIGN_MASK) == 0);
2689   assert((unsigned long)(sz) >= MINSIZE);
2690   /* ... and alignment */
2691   assert(aligned_OK(chunk2mem(p)));
2692   /* chunk is less than MINSIZE more than request */
2693   assert((long)(sz) - (long)(s) >= 0);
2694   assert((long)(sz) - (long)(s + MINSIZE) < 0);
2695 }
2696
2697 /*
2698   Properties of nonrecycled chunks at the point they are malloced
2699 */
2700
2701 #if __STD_C
2702 static void do_check_malloced_chunk(mstate av, mchunkptr p, INTERNAL_SIZE_T s)
2703 #else
2704 static void do_check_malloced_chunk(av, p, s)
2705 mstate av; mchunkptr p; INTERNAL_SIZE_T s;
2706 #endif
2707 {
2708   /* same as recycled case ... */
2709   do_check_remalloced_chunk(av, p, s);
2710
2711   /*
2712     ... plus,  must obey implementation invariant that prev_inuse is
2713     always true of any allocated chunk; i.e., that each allocated
2714     chunk borders either a previously allocated and still in-use
2715     chunk, or the base of its memory arena. This is ensured
2716     by making all allocations from the the `lowest' part of any found
2717     chunk.  This does not necessarily hold however for chunks
2718     recycled via fastbins.
2719   */
2720
2721   assert(prev_inuse(p));
2722 }
2723
2724
2725 /*
2726   Properties of malloc_state.
2727
2728   This may be useful for debugging malloc, as well as detecting user
2729   programmer errors that somehow write into malloc_state.
2730
2731   If you are extending or experimenting with this malloc, you can
2732   probably figure out how to hack this routine to print out or
2733   display chunk addresses, sizes, bins, and other instrumentation.
2734 */
2735
2736 static void do_check_malloc_state(mstate av)
2737 {
2738   int i;
2739   mchunkptr p;
2740   mchunkptr q;
2741   mbinptr b;
2742   unsigned int binbit;
2743   int empty;
2744   unsigned int idx;
2745   INTERNAL_SIZE_T size;
2746   unsigned long total = 0;
2747   int max_fast_bin;
2748
2749   /* internal size_t must be no wider than pointer type */
2750   assert(sizeof(INTERNAL_SIZE_T) <= sizeof(char*));
2751
2752   /* alignment is a power of 2 */
2753   assert((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT-1)) == 0);
2754
2755   /* cannot run remaining checks until fully initialized */
2756   if (av->top == 0 || av->top == initial_top(av))
2757     return;
2758
2759   /* pagesize is a power of 2 */
2760   assert((mp_.pagesize & (mp_.pagesize-1)) == 0);
2761
2762   /* A contiguous main_arena is consistent with sbrk_base.  */
2763   if (av == &main_arena && contiguous(av))
2764     assert((char*)mp_.sbrk_base + av->system_mem ==
2765            (char*)av->top + chunksize(av->top));
2766
2767   /* properties of fastbins */
2768
2769   /* max_fast is in allowed range */
2770   assert((get_max_fast () & ~1) <= request2size(MAX_FAST_SIZE));
2771
2772   max_fast_bin = fastbin_index(get_max_fast ());
2773
2774   for (i = 0; i < NFASTBINS; ++i) {
2775     p = av->fastbins[i];
2776
2777     /* The following test can only be performed for the main arena.
2778        While mallopt calls malloc_consolidate to get rid of all fast
2779        bins (especially those larger than the new maximum) this does
2780        only happen for the main arena.  Trying to do this for any
2781        other arena would mean those arenas have to be locked and
2782        malloc_consolidate be called for them.  This is excessive.  And
2783        even if this is acceptable to somebody it still cannot solve
2784        the problem completely since if the arena is locked a
2785        concurrent malloc call might create a new arena which then
2786        could use the newly invalid fast bins.  */
2787
2788     /* all bins past max_fast are empty */
2789     if (av == &main_arena && i > max_fast_bin)
2790       assert(p == 0);
2791
2792     while (p != 0) {
2793       /* each chunk claims to be inuse */
2794       do_check_inuse_chunk(av, p);
2795       total += chunksize(p);
2796       /* chunk belongs in this bin */
2797       assert(fastbin_index(chunksize(p)) == i);
2798       p = p->fd;
2799     }
2800   }
2801
2802   if (total != 0)
2803     assert(have_fastchunks(av));
2804   else if (!have_fastchunks(av))
2805     assert(total == 0);
2806
2807   /* check normal bins */
2808   for (i = 1; i < NBINS; ++i) {
2809     b = bin_at(av,i);
2810
2811     /* binmap is accurate (except for bin 1 == unsorted_chunks) */
2812     if (i >= 2) {
2813       binbit = get_binmap(av,i);
2814       empty = last(b) == b;
2815       if (!binbit)
2816         assert(empty);
2817       else if (!empty)
2818         assert(binbit);
2819     }
2820
2821     for (p = last(b); p != b; p = p->bk) {
2822       /* each chunk claims to be free */
2823       do_check_free_chunk(av, p);
2824       size = chunksize(p);
2825       total += size;
2826       if (i >= 2) {
2827         /* chunk belongs in bin */
2828         idx = bin_index(size);
2829         assert(idx == i);
2830         /* lists are sorted */
2831         assert(p->bk == b ||
2832                (unsigned long)chunksize(p->bk) >= (unsigned long)chunksize(p));
2833
2834         if (!in_smallbin_range(size))
2835           {
2836             if (p->fd_nextsize != NULL)
2837               {
2838                 if (p->fd_nextsize == p)
2839                   assert (p->bk_nextsize == p);
2840                 else
2841                   {
2842                     if (p->fd_nextsize == first (b))
2843                       assert (chunksize (p) < chunksize (p->fd_nextsize));
2844                     else
2845                       assert (chunksize (p) > chunksize (p->fd_nextsize));
2846
2847                     if (p == first (b))
2848                       assert (chunksize (p) > chunksize (p->bk_nextsize));
2849                     else
2850                       assert (chunksize (p) < chunksize (p->bk_nextsize));
2851                   }
2852               }
2853             else
2854               assert (p->bk_nextsize == NULL);
2855           }
2856       } else if (!in_smallbin_range(size))
2857         assert (p->fd_nextsize == NULL && p->bk_nextsize == NULL);
2858       /* chunk is followed by a legal chain of inuse chunks */
2859       for (q = next_chunk(p);
2860            (q != av->top && inuse(q) &&
2861              (unsigned long)(chunksize(q)) >= MINSIZE);
2862            q = next_chunk(q))
2863         do_check_inuse_chunk(av, q);
2864     }
2865   }
2866
2867   /* top chunk is OK */
2868   check_chunk(av, av->top);
2869
2870   /* sanity checks for statistics */
2871
2872 #ifdef NO_THREADS
2873   assert(total <= (unsigned long)(mp_.max_total_mem));
2874   assert(mp_.n_mmaps >= 0);
2875 #endif
2876   assert(mp_.n_mmaps <= mp_.max_n_mmaps);
2877
2878   assert((unsigned long)(av->system_mem) <=
2879          (unsigned long)(av->max_system_mem));
2880
2881   assert((unsigned long)(mp_.mmapped_mem) <=
2882          (unsigned long)(mp_.max_mmapped_mem));
2883
2884 #ifdef NO_THREADS
2885   assert((unsigned long)(mp_.max_total_mem) >=
2886          (unsigned long)(mp_.mmapped_mem) + (unsigned long)(av->system_mem));
2887 #endif
2888 }
2889 #endif
2890
2891
2892 /* ----------------- Support for debugging hooks -------------------- */
2893 #include "hooks.c"
2894
2895
2896 /* ----------- Routines dealing with system allocation -------------- */
2897
2898 /*
2899   sysmalloc handles malloc cases requiring more memory from the system.
2900   On entry, it is assumed that av->top does not have enough
2901   space to service request for nb bytes, thus requiring that av->top
2902   be extended or replaced.
2903 */
2904
2905 #if __STD_C
2906 static Void_t* sYSMALLOc(INTERNAL_SIZE_T nb, mstate av)
2907 #else
2908 static Void_t* sYSMALLOc(nb, av) INTERNAL_SIZE_T nb; mstate av;
2909 #endif
2910 {
2911   mchunkptr       old_top;        /* incoming value of av->top */
2912   INTERNAL_SIZE_T old_size;       /* its size */
2913   char*           old_end;        /* its end address */
2914
2915   long            size;           /* arg to first MORECORE or mmap call */
2916   char*           brk;            /* return value from MORECORE */
2917
2918   long            correction;     /* arg to 2nd MORECORE call */
2919   char*           snd_brk;        /* 2nd return val */
2920
2921   INTERNAL_SIZE_T front_misalign; /* unusable bytes at front of new space */
2922   INTERNAL_SIZE_T end_misalign;   /* partial page left at end of new space */
2923   char*           aligned_brk;    /* aligned offset into brk */
2924
2925   mchunkptr       p;              /* the allocated/returned chunk */
2926   mchunkptr       remainder;      /* remainder from allocation */
2927   unsigned long   remainder_size; /* its size */
2928
2929   unsigned long   sum;            /* for updating stats */
2930
2931   size_t          pagemask  = mp_.pagesize - 1;
2932   bool            tried_mmap = false;
2933
2934
2935 #if HAVE_MMAP
2936
2937   /*
2938     If have mmap, and the request size meets the mmap threshold, and
2939     the system supports mmap, and there are few enough currently
2940     allocated mmapped regions, try to directly map this request
2941     rather than expanding top.
2942   */
2943
2944   if ((unsigned long)(nb) >= (unsigned long)(mp_.mmap_threshold) &&
2945       (mp_.n_mmaps < mp_.n_mmaps_max)) {
2946
2947     char* mm;             /* return value from mmap call*/
2948
2949   try_mmap:
2950     /*
2951       Round up size to nearest page.  For mmapped chunks, the overhead
2952       is one SIZE_SZ unit larger than for normal chunks, because there
2953       is no following chunk whose prev_size field could be used.
2954     */
2955 #if 1
2956     /* See the front_misalign handling below, for glibc there is no
2957        need for further alignments.  */
2958     size = (nb + SIZE_SZ + pagemask) & ~pagemask;
2959 #else
2960     size = (nb + SIZE_SZ + MALLOC_ALIGN_MASK + pagemask) & ~pagemask;
2961 #endif
2962     tried_mmap = true;
2963
2964     /* Don't try if size wraps around 0 */
2965     if ((unsigned long)(size) > (unsigned long)(nb)) {
2966
2967       mm = (char*)(MMAP(0, size, PROT_READ|PROT_WRITE, MAP_PRIVATE));
2968
2969       if (mm != MAP_FAILED) {
2970
2971         /*
2972           The offset to the start of the mmapped region is stored
2973           in the prev_size field of the chunk. This allows us to adjust
2974           returned start address to meet alignment requirements here
2975           and in memalign(), and still be able to compute proper
2976           address argument for later munmap in free() and realloc().
2977         */
2978
2979 #if 1
2980         /* For glibc, chunk2mem increases the address by 2*SIZE_SZ and
2981            MALLOC_ALIGN_MASK is 2*SIZE_SZ-1.  Each mmap'ed area is page
2982            aligned and therefore definitely MALLOC_ALIGN_MASK-aligned.  */
2983         assert (((INTERNAL_SIZE_T)chunk2mem(mm) & MALLOC_ALIGN_MASK) == 0);
2984 #else
2985         front_misalign = (INTERNAL_SIZE_T)chunk2mem(mm) & MALLOC_ALIGN_MASK;
2986         if (front_misalign > 0) {
2987           correction = MALLOC_ALIGNMENT - front_misalign;
2988           p = (mchunkptr)(mm + correction);
2989           p->prev_size = correction;
2990           set_head(p, (size - correction) |IS_MMAPPED);
2991         }
2992         else
2993 #endif
2994           {
2995             p = (mchunkptr)mm;
2996             set_head(p, size|IS_MMAPPED);
2997           }
2998
2999         /* update statistics */
3000
3001         if (++mp_.n_mmaps > mp_.max_n_mmaps)
3002           mp_.max_n_mmaps = mp_.n_mmaps;
3003
3004         sum = mp_.mmapped_mem += size;
3005         if (sum > (unsigned long)(mp_.max_mmapped_mem))
3006           mp_.max_mmapped_mem = sum;
3007 #ifdef NO_THREADS
3008         sum += av->system_mem;
3009         if (sum > (unsigned long)(mp_.max_total_mem))
3010           mp_.max_total_mem = sum;
3011 #endif
3012
3013         check_chunk(av, p);
3014
3015         return chunk2mem(p);
3016       }
3017     }
3018   }
3019 #endif
3020
3021   /* Record incoming configuration of top */
3022
3023   old_top  = av->top;
3024   old_size = chunksize(old_top);
3025   old_end  = (char*)(chunk_at_offset(old_top, old_size));
3026
3027   brk = snd_brk = (char*)(MORECORE_FAILURE);
3028
3029   /*
3030      If not the first time through, we require old_size to be
3031      at least MINSIZE and to have prev_inuse set.
3032   */
3033
3034   assert((old_top == initial_top(av) && old_size == 0) ||
3035          ((unsigned long) (old_size) >= MINSIZE &&
3036           prev_inuse(old_top) &&
3037           ((unsigned long)old_end & pagemask) == 0));
3038
3039   /* Precondition: not enough current space to satisfy nb request */
3040   assert((unsigned long)(old_size) < (unsigned long)(nb + MINSIZE));
3041
3042   /* Precondition: all fastbins are consolidated */
3043   assert(!have_fastchunks(av));
3044
3045
3046   if (av != &main_arena) {
3047
3048     heap_info *old_heap, *heap;
3049     size_t old_heap_size;
3050
3051     /* First try to extend the current heap. */
3052     old_heap = heap_for_ptr(old_top);
3053     old_heap_size = old_heap->size;
3054     if ((long) (MINSIZE + nb - old_size) > 0
3055         && grow_heap(old_heap, MINSIZE + nb - old_size) == 0) {
3056       av->system_mem += old_heap->size - old_heap_size;
3057       arena_mem += old_heap->size - old_heap_size;
3058 #if 0
3059       if(mmapped_mem + arena_mem + sbrked_mem > max_total_mem)
3060         max_total_mem = mmapped_mem + arena_mem + sbrked_mem;
3061 #endif
3062       set_head(old_top, (((char *)old_heap + old_heap->size) - (char *)old_top)
3063                | PREV_INUSE);
3064     }
3065     else if ((heap = new_heap(nb + (MINSIZE + sizeof(*heap)), mp_.top_pad))) {
3066       /* Use a newly allocated heap.  */
3067       heap->ar_ptr = av;
3068       heap->prev = old_heap;
3069       av->system_mem += heap->size;
3070       arena_mem += heap->size;
3071 #if 0
3072       if((unsigned long)(mmapped_mem + arena_mem + sbrked_mem) > max_total_mem)
3073         max_total_mem = mmapped_mem + arena_mem + sbrked_mem;
3074 #endif
3075       /* Set up the new top.  */
3076       top(av) = chunk_at_offset(heap, sizeof(*heap));
3077       set_head(top(av), (heap->size - sizeof(*heap)) | PREV_INUSE);
3078
3079       /* Setup fencepost and free the old top chunk. */
3080       /* The fencepost takes at least MINSIZE bytes, because it might
3081          become the top chunk again later.  Note that a footer is set
3082          up, too, although the chunk is marked in use. */
3083       old_size -= MINSIZE;
3084       set_head(chunk_at_offset(old_top, old_size + 2*SIZE_SZ), 0|PREV_INUSE);
3085       if (old_size >= MINSIZE) {
3086         set_head(chunk_at_offset(old_top, old_size), (2*SIZE_SZ)|PREV_INUSE);
3087         set_foot(chunk_at_offset(old_top, old_size), (2*SIZE_SZ));
3088         set_head(old_top, old_size|PREV_INUSE|NON_MAIN_ARENA);
3089         _int_free(av, chunk2mem(old_top));
3090       } else {
3091         set_head(old_top, (old_size + 2*SIZE_SZ)|PREV_INUSE);
3092         set_foot(old_top, (old_size + 2*SIZE_SZ));
3093       }
3094     }
3095     else if (!tried_mmap)
3096       /* We can at least try to use to mmap memory.  */
3097       goto try_mmap;
3098
3099   } else { /* av == main_arena */
3100
3101
3102   /* Request enough space for nb + pad + overhead */
3103
3104   size = nb + mp_.top_pad + MINSIZE;
3105
3106   /*
3107     If contiguous, we can subtract out existing space that we hope to
3108     combine with new space. We add it back later only if
3109     we don't actually get contiguous space.
3110   */
3111
3112   if (contiguous(av))
3113     size -= old_size;
3114
3115   /*
3116     Round to a multiple of page size.
3117     If MORECORE is not contiguous, this ensures that we only call it
3118     with whole-page arguments.  And if MORECORE is contiguous and
3119     this is not first time through, this preserves page-alignment of
3120     previous calls. Otherwise, we correct to page-align below.
3121   */
3122
3123   size = (size + pagemask) & ~pagemask;
3124
3125   /*
3126     Don't try to call MORECORE if argument is so big as to appear
3127     negative. Note that since mmap takes size_t arg, it may succeed
3128     below even if we cannot call MORECORE.
3129   */
3130
3131   if (size > 0)
3132     brk = (char*)(MORECORE(size));
3133
3134   if (brk != (char*)(MORECORE_FAILURE)) {
3135     /* Call the `morecore' hook if necessary.  */
3136     if (__after_morecore_hook)
3137       (*__after_morecore_hook) ();
3138   } else {
3139   /*
3140     If have mmap, try using it as a backup when MORECORE fails or
3141     cannot be used. This is worth doing on systems that have "holes" in
3142     address space, so sbrk cannot extend to give contiguous space, but
3143     space is available elsewhere.  Note that we ignore mmap max count
3144     and threshold limits, since the space will not be used as a
3145     segregated mmap region.
3146   */
3147
3148 #if HAVE_MMAP
3149     /* Cannot merge with old top, so add its size back in */
3150     if (contiguous(av))
3151       size = (size + old_size + pagemask) & ~pagemask;
3152
3153     /* If we are relying on mmap as backup, then use larger units */
3154     if ((unsigned long)(size) < (unsigned long)(MMAP_AS_MORECORE_SIZE))
3155       size = MMAP_AS_MORECORE_SIZE;
3156
3157     /* Don't try if size wraps around 0 */
3158     if ((unsigned long)(size) > (unsigned long)(nb)) {
3159
3160       char *mbrk = (char*)(MMAP(0, size, PROT_READ|PROT_WRITE, MAP_PRIVATE));
3161
3162       if (mbrk != MAP_FAILED) {
3163
3164         /* We do not need, and cannot use, another sbrk call to find end */
3165         brk = mbrk;
3166         snd_brk = brk + size;
3167
3168         /*
3169            Record that we no longer have a contiguous sbrk region.
3170            After the first time mmap is used as backup, we do not
3171            ever rely on contiguous space since this could incorrectly
3172            bridge regions.
3173         */
3174         set_noncontiguous(av);
3175       }
3176     }
3177 #endif
3178   }
3179
3180   if (brk != (char*)(MORECORE_FAILURE)) {
3181     if (mp_.sbrk_base == 0)
3182       mp_.sbrk_base = brk;
3183     av->system_mem += size;
3184
3185     /*
3186       If MORECORE extends previous space, we can likewise extend top size.
3187     */
3188
3189     if (brk == old_end && snd_brk == (char*)(MORECORE_FAILURE))
3190       set_head(old_top, (size + old_size) | PREV_INUSE);
3191
3192     else if (contiguous(av) && old_size && brk < old_end) {
3193       /* Oops!  Someone else killed our space..  Can't touch anything.  */
3194       assert(0);
3195     }
3196
3197     /*
3198       Otherwise, make adjustments:
3199
3200       * If the first time through or noncontiguous, we need to call sbrk
3201         just to find out where the end of memory lies.
3202
3203       * We need to ensure that all returned chunks from malloc will meet
3204         MALLOC_ALIGNMENT
3205
3206       * If there was an intervening foreign sbrk, we need to adjust sbrk
3207         request size to account for fact that we will not be able to
3208         combine new space with existing space in old_top.
3209
3210       * Almost all systems internally allocate whole pages at a time, in
3211         which case we might as well use the whole last page of request.
3212         So we allocate enough more memory to hit a page boundary now,
3213         which in turn causes future contiguous calls to page-align.
3214     */
3215
3216     else {
3217       front_misalign = 0;
3218       end_misalign = 0;
3219       correction = 0;
3220       aligned_brk = brk;
3221
3222       /* handle contiguous cases */
3223       if (contiguous(av)) {
3224
3225         /* Count foreign sbrk as system_mem.  */
3226         if (old_size)
3227           av->system_mem += brk - old_end;
3228
3229         /* Guarantee alignment of first new chunk made from this space */
3230
3231         front_misalign = (INTERNAL_SIZE_T)chunk2mem(brk) & MALLOC_ALIGN_MASK;
3232         if (front_misalign > 0) {
3233
3234           /*
3235             Skip over some bytes to arrive at an aligned position.
3236             We don't need to specially mark these wasted front bytes.
3237             They will never be accessed anyway because
3238             prev_inuse of av->top (and any chunk created from its start)
3239             is always true after initialization.
3240           */
3241
3242           correction = MALLOC_ALIGNMENT - front_misalign;
3243           aligned_brk += correction;
3244         }
3245
3246         /*
3247           If this isn't adjacent to existing space, then we will not
3248           be able to merge with old_top space, so must add to 2nd request.
3249         */
3250
3251         correction += old_size;
3252
3253         /* Extend the end address to hit a page boundary */
3254         end_misalign = (INTERNAL_SIZE_T)(brk + size + correction);
3255         correction += ((end_misalign + pagemask) & ~pagemask) - end_misalign;
3256
3257         assert(correction >= 0);
3258         snd_brk = (char*)(MORECORE(correction));
3259
3260         /*
3261           If can't allocate correction, try to at least find out current
3262           brk.  It might be enough to proceed without failing.
3263
3264           Note that if second sbrk did NOT fail, we assume that space
3265           is contiguous with first sbrk. This is a safe assumption unless
3266           program is multithreaded but doesn't use locks and a foreign sbrk
3267           occurred between our first and second calls.
3268         */
3269
3270         if (snd_brk == (char*)(MORECORE_FAILURE)) {
3271           correction = 0;
3272           snd_brk = (char*)(MORECORE(0));
3273         } else
3274           /* Call the `morecore' hook if necessary.  */
3275           if (__after_morecore_hook)
3276             (*__after_morecore_hook) ();
3277       }
3278
3279       /* handle non-contiguous cases */
3280       else {
3281         /* MORECORE/mmap must correctly align */
3282         assert(((unsigned long)chunk2mem(brk) & MALLOC_ALIGN_MASK) == 0);
3283
3284         /* Find out current end of memory */
3285         if (snd_brk == (char*)(MORECORE_FAILURE)) {
3286           snd_brk = (char*)(MORECORE(0));
3287         }
3288       }
3289
3290       /* Adjust top based on results of second sbrk */
3291       if (snd_brk != (char*)(MORECORE_FAILURE)) {
3292         av->top = (mchunkptr)aligned_brk;
3293         set_head(av->top, (snd_brk - aligned_brk + correction) | PREV_INUSE);
3294         av->system_mem += correction;
3295
3296         /*
3297           If not the first time through, we either have a
3298           gap due to foreign sbrk or a non-contiguous region.  Insert a
3299           double fencepost at old_top to prevent consolidation with space
3300           we don't own. These fenceposts are artificial chunks that are
3301           marked as inuse and are in any case too small to use.  We need
3302           two to make sizes and alignments work out.
3303         */
3304
3305         if (old_size != 0) {
3306           /*
3307              Shrink old_top to insert fenceposts, keeping size a
3308              multiple of MALLOC_ALIGNMENT. We know there is at least
3309              enough space in old_top to do this.
3310           */
3311           old_size = (old_size - 4*SIZE_SZ) & ~MALLOC_ALIGN_MASK;
3312           set_head(old_top, old_size | PREV_INUSE);
3313
3314           /*
3315             Note that the following assignments completely overwrite
3316             old_top when old_size was previously MINSIZE.  This is
3317             intentional. We need the fencepost, even if old_top otherwise gets
3318             lost.
3319           */
3320           chunk_at_offset(old_top, old_size            )->size =
3321             (2*SIZE_SZ)|PREV_INUSE;
3322
3323           chunk_at_offset(old_top, old_size + 2*SIZE_SZ)->size =
3324             (2*SIZE_SZ)|PREV_INUSE;
3325
3326           /* If possible, release the rest. */
3327           if (old_size >= MINSIZE) {
3328             _int_free(av, chunk2mem(old_top));
3329           }
3330
3331         }
3332       }
3333     }
3334
3335     /* Update statistics */
3336 #ifdef NO_THREADS
3337     sum = av->system_mem + mp_.mmapped_mem;
3338     if (sum > (unsigned long)(mp_.max_total_mem))
3339       mp_.max_total_mem = sum;
3340 #endif
3341
3342   }
3343
3344   } /* if (av !=  &main_arena) */
3345
3346   if ((unsigned long)av->system_mem > (unsigned long)(av->max_system_mem))
3347     av->max_system_mem = av->system_mem;
3348   check_malloc_state(av);
3349
3350   /* finally, do the allocation */
3351   p = av->top;
3352   size = chunksize(p);
3353
3354   /* check that one of the above allocation paths succeeded */
3355   if ((unsigned long)(size) >= (unsigned long)(nb + MINSIZE)) {
3356     remainder_size = size - nb;
3357     remainder = chunk_at_offset(p, nb);
3358     av->top = remainder;
3359     set_head(p, nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));
3360     set_head(remainder, remainder_size | PREV_INUSE);
3361     check_malloced_chunk(av, p, nb);
3362     return chunk2mem(p);
3363   }
3364
3365   /* catch all failure paths */
3366   MALLOC_FAILURE_ACTION;
3367   return 0;
3368 }
3369
3370
3371 /*
3372   sYSTRIm is an inverse of sorts to sYSMALLOc.  It gives memory back
3373   to the system (via negative arguments to sbrk) if there is unused
3374   memory at the `high' end of the malloc pool. It is called
3375   automatically by free() when top space exceeds the trim
3376   threshold. It is also called by the public malloc_trim routine.  It
3377   returns 1 if it actually released any memory, else 0.
3378 */
3379
3380 #if __STD_C
3381 static int sYSTRIm(size_t pad, mstate av)
3382 #else
3383 static int sYSTRIm(pad, av) size_t pad; mstate av;
3384 #endif
3385 {
3386   long  top_size;        /* Amount of top-most memory */
3387   long  extra;           /* Amount to release */
3388   long  released;        /* Amount actually released */
3389   char* current_brk;     /* address returned by pre-check sbrk call */
3390   char* new_brk;         /* address returned by post-check sbrk call */
3391   size_t pagesz;
3392
3393   pagesz = mp_.pagesize;
3394   top_size = chunksize(av->top);
3395
3396   /* Release in pagesize units, keeping at least one page */
3397   extra = ((top_size - pad - MINSIZE + (pagesz-1)) / pagesz - 1) * pagesz;
3398
3399   if (extra > 0) {
3400
3401     /*
3402       Only proceed if end of memory is where we last set it.
3403       This avoids problems if there were foreign sbrk calls.
3404     */
3405     current_brk = (char*)(MORECORE(0));
3406     if (current_brk == (char*)(av->top) + top_size) {
3407
3408       /*
3409         Attempt to release memory. We ignore MORECORE return value,
3410         and instead call again to find out where new end of memory is.
3411         This avoids problems if first call releases less than we asked,
3412         of if failure somehow altered brk value. (We could still
3413         encounter problems if it altered brk in some very bad way,
3414         but the only thing we can do is adjust anyway, which will cause
3415         some downstream failure.)
3416       */
3417
3418       MORECORE(-extra);
3419       /* Call the `morecore' hook if necessary.  */
3420       if (__after_morecore_hook)
3421         (*__after_morecore_hook) ();
3422       new_brk = (char*)(MORECORE(0));
3423
3424       if (new_brk != (char*)MORECORE_FAILURE) {
3425         released = (long)(current_brk - new_brk);
3426
3427         if (released != 0) {
3428           /* Success. Adjust top. */
3429           av->system_mem -= released;
3430           set_head(av->top, (top_size - released) | PREV_INUSE);
3431           check_malloc_state(av);
3432           return 1;
3433         }
3434       }
3435     }
3436   }
3437   return 0;
3438 }
3439
3440 #ifdef HAVE_MMAP
3441
3442 static void
3443 internal_function
3444 #if __STD_C
3445 munmap_chunk(mchunkptr p)
3446 #else
3447 munmap_chunk(p) mchunkptr p;
3448 #endif
3449 {
3450   INTERNAL_SIZE_T size = chunksize(p);
3451
3452   assert (chunk_is_mmapped(p));
3453 #if 0
3454   assert(! ((char*)p >= mp_.sbrk_base && (char*)p < mp_.sbrk_base + mp_.sbrked_mem));
3455   assert((mp_.n_mmaps > 0));
3456 #endif
3457
3458   uintptr_t block = (uintptr_t) p - p->prev_size;
3459   size_t total_size = p->prev_size + size;
3460   /* Unfortunately we have to do the compilers job by hand here.  Normally
3461      we would test BLOCK and TOTAL-SIZE separately for compliance with the
3462      page size.  But gcc does not recognize the optimization possibility
3463      (in the moment at least) so we combine the two values into one before
3464      the bit test.  */
3465   if (__builtin_expect (((block | total_size) & (mp_.pagesize - 1)) != 0, 0))
3466     {
3467       malloc_printerr (check_action, "munmap_chunk(): invalid pointer",
3468                        chunk2mem (p));
3469       return;
3470     }
3471
3472   mp_.n_mmaps--;
3473   mp_.mmapped_mem -= total_size;
3474
3475   int ret __attribute__ ((unused)) = munmap((char *)block, total_size);
3476
3477   /* munmap returns non-zero on failure */
3478   assert(ret == 0);
3479 }
3480
3481 #if HAVE_MREMAP
3482
3483 static mchunkptr
3484 internal_function
3485 #if __STD_C
3486 mremap_chunk(mchunkptr p, size_t new_size)
3487 #else
3488 mremap_chunk(p, new_size) mchunkptr p; size_t new_size;
3489 #endif
3490 {
3491   size_t page_mask = mp_.pagesize - 1;
3492   INTERNAL_SIZE_T offset = p->prev_size;
3493   INTERNAL_SIZE_T size = chunksize(p);
3494   char *cp;
3495
3496   assert (chunk_is_mmapped(p));
3497 #if 0
3498   assert(! ((char*)p >= mp_.sbrk_base && (char*)p < mp_.sbrk_base + mp_.sbrked_mem));
3499   assert((mp_.n_mmaps > 0));
3500 #endif
3501   assert(((size + offset) & (mp_.pagesize-1)) == 0);
3502
3503   /* Note the extra SIZE_SZ overhead as in mmap_chunk(). */
3504   new_size = (new_size + offset + SIZE_SZ + page_mask) & ~page_mask;
3505
3506   /* No need to remap if the number of pages does not change.  */
3507   if (size + offset == new_size)
3508     return p;
3509
3510   cp = (char *)mremap((char *)p - offset, size + offset, new_size,
3511                       MREMAP_MAYMOVE);
3512
3513   if (cp == MAP_FAILED) return 0;
3514
3515   p = (mchunkptr)(cp + offset);
3516
3517   assert(aligned_OK(chunk2mem(p)));
3518
3519   assert((p->prev_size == offset));
3520   set_head(p, (new_size - offset)|IS_MMAPPED);
3521
3522   mp_.mmapped_mem -= size + offset;
3523   mp_.mmapped_mem += new_size;
3524   if ((unsigned long)mp_.mmapped_mem > (unsigned long)mp_.max_mmapped_mem)
3525     mp_.max_mmapped_mem = mp_.mmapped_mem;
3526 #ifdef NO_THREADS
3527   if ((unsigned long)(mp_.mmapped_mem + arena_mem + main_arena.system_mem) >
3528       mp_.max_total_mem)
3529     mp_.max_total_mem = mp_.mmapped_mem + arena_mem + main_arena.system_mem;
3530 #endif
3531   return p;
3532 }
3533
3534 #endif /* HAVE_MREMAP */
3535
3536 #endif /* HAVE_MMAP */
3537
3538 /*------------------------ Public wrappers. --------------------------------*/
3539
3540 Void_t*
3541 public_mALLOc(size_t bytes)
3542 {
3543   mstate ar_ptr;
3544   Void_t *victim;
3545
3546   __malloc_ptr_t (*hook) (size_t, __const __malloc_ptr_t) = __malloc_hook;
3547   if (hook != NULL)
3548     return (*hook)(bytes, RETURN_ADDRESS (0));
3549
3550   arena_get(ar_ptr, bytes);
3551   if(!ar_ptr)
3552     return 0;
3553   victim = _int_malloc(ar_ptr, bytes);
3554   if(!victim) {
3555     /* Maybe the failure is due to running out of mmapped areas. */
3556     if(ar_ptr != &main_arena) {
3557       (void)mutex_unlock(&ar_ptr->mutex);
3558       (void)mutex_lock(&main_arena.mutex);
3559       victim = _int_malloc(&main_arena, bytes);
3560       (void)mutex_unlock(&main_arena.mutex);
3561     } else {
3562 #if USE_ARENAS
3563       /* ... or sbrk() has failed and there is still a chance to mmap() */
3564       ar_ptr = arena_get2(ar_ptr->next ? ar_ptr : 0, bytes);
3565       (void)mutex_unlock(&main_arena.mutex);
3566       if(ar_ptr) {
3567         victim = _int_malloc(ar_ptr, bytes);
3568         (void)mutex_unlock(&ar_ptr->mutex);
3569       }
3570 #endif
3571     }
3572   } else
3573     (void)mutex_unlock(&ar_ptr->mutex);
3574   assert(!victim || chunk_is_mmapped(mem2chunk(victim)) ||
3575          ar_ptr == arena_for_chunk(mem2chunk(victim)));
3576   return victim;
3577 }
3578 #ifdef libc_hidden_def
3579 libc_hidden_def(public_mALLOc)
3580 #endif
3581
3582 void
3583 public_fREe(Void_t* mem)
3584 {
3585   mstate ar_ptr;
3586   mchunkptr p;                          /* chunk corresponding to mem */
3587
3588   void (*hook) (__malloc_ptr_t, __const __malloc_ptr_t) = __free_hook;
3589   if (hook != NULL) {
3590     (*hook)(mem, RETURN_ADDRESS (0));
3591     return;
3592   }
3593
3594   if (mem == 0)                              /* free(0) has no effect */
3595     return;
3596
3597   p = mem2chunk(mem);
3598
3599 #if HAVE_MMAP
3600   if (chunk_is_mmapped(p))                       /* release mmapped memory. */
3601   {
3602     /* see if the dynamic brk/mmap threshold needs adjusting */
3603     if (!mp_.no_dyn_threshold
3604         && p->size > mp_.mmap_threshold
3605         && p->size <= DEFAULT_MMAP_THRESHOLD_MAX)
3606       {
3607         mp_.mmap_threshold = chunksize (p);
3608         mp_.trim_threshold = 2 * mp_.mmap_threshold;
3609       }
3610     munmap_chunk(p);
3611     return;
3612   }
3613 #endif
3614
3615   ar_ptr = arena_for_chunk(p);
3616 #if THREAD_STATS
3617   if(!mutex_trylock(&ar_ptr->mutex))
3618     ++(ar_ptr->stat_lock_direct);
3619   else {
3620     (void)mutex_lock(&ar_ptr->mutex);
3621     ++(ar_ptr->stat_lock_wait);
3622   }
3623 #else
3624   (void)mutex_lock(&ar_ptr->mutex);
3625 #endif
3626   _int_free(ar_ptr, mem);
3627   (void)mutex_unlock(&ar_ptr->mutex);
3628 }
3629 #ifdef libc_hidden_def
3630 libc_hidden_def (public_fREe)
3631 #endif
3632
3633 Void_t*
3634 public_rEALLOc(Void_t* oldmem, size_t bytes)
3635 {
3636   mstate ar_ptr;
3637   INTERNAL_SIZE_T    nb;      /* padded request size */
3638
3639   mchunkptr oldp;             /* chunk corresponding to oldmem */
3640   INTERNAL_SIZE_T    oldsize; /* its size */
3641
3642   Void_t* newp;             /* chunk to return */
3643
3644   __malloc_ptr_t (*hook) (__malloc_ptr_t, size_t, __const __malloc_ptr_t) =
3645     __realloc_hook;
3646   if (hook != NULL)
3647     return (*hook)(oldmem, bytes, RETURN_ADDRESS (0));
3648
3649 #if REALLOC_ZERO_BYTES_FREES
3650   if (bytes == 0 && oldmem != NULL) { public_fREe(oldmem); return 0; }
3651 #endif
3652
3653   /* realloc of null is supposed to be same as malloc */
3654   if (oldmem == 0) return public_mALLOc(bytes);
3655
3656   oldp    = mem2chunk(oldmem);
3657   oldsize = chunksize(oldp);
3658
3659   /* Little security check which won't hurt performance: the
3660      allocator never wrapps around at the end of the address space.
3661      Therefore we can exclude some size values which might appear
3662      here by accident or by "design" from some intruder.  */
3663   if (__builtin_expect ((uintptr_t) oldp > (uintptr_t) -oldsize, 0)
3664       || __builtin_expect (misaligned_chunk (oldp), 0))
3665     {
3666       malloc_printerr (check_action, "realloc(): invalid pointer", oldmem);
3667       return NULL;
3668     }
3669
3670   checked_request2size(bytes, nb);
3671
3672 #if HAVE_MMAP
3673   if (chunk_is_mmapped(oldp))
3674   {
3675     Void_t* newmem;
3676
3677 #if HAVE_MREMAP
3678     newp = mremap_chunk(oldp, nb);
3679     if(newp) return chunk2mem(newp);
3680 #endif
3681     /* Note the extra SIZE_SZ overhead. */
3682     if(oldsize - SIZE_SZ >= nb) return oldmem; /* do nothing */
3683     /* Must alloc, copy, free. */
3684     newmem = public_mALLOc(bytes);
3685     if (newmem == 0) return 0; /* propagate failure */
3686     MALLOC_COPY(newmem, oldmem, oldsize - 2*SIZE_SZ);
3687     munmap_chunk(oldp);
3688     return newmem;
3689   }
3690 #endif
3691
3692   ar_ptr = arena_for_chunk(oldp);
3693 #if THREAD_STATS
3694   if(!mutex_trylock(&ar_ptr->mutex))
3695     ++(ar_ptr->stat_lock_direct);
3696   else {
3697     (void)mutex_lock(&ar_ptr->mutex);
3698     ++(ar_ptr->stat_lock_wait);
3699   }
3700 #else
3701   (void)mutex_lock(&ar_ptr->mutex);
3702 #endif
3703
3704 #ifndef NO_THREADS
3705   /* As in malloc(), remember this arena for the next allocation. */
3706   tsd_setspecific(arena_key, (Void_t *)ar_ptr);
3707 #endif
3708
3709   newp = _int_realloc(ar_ptr, oldmem, bytes);
3710
3711   (void)mutex_unlock(&ar_ptr->mutex);
3712   assert(!newp || chunk_is_mmapped(mem2chunk(newp)) ||
3713          ar_ptr == arena_for_chunk(mem2chunk(newp)));
3714
3715   if (newp == NULL)
3716     {
3717       /* Try harder to allocate memory in other arenas.  */
3718       newp = public_mALLOc(bytes);
3719       if (newp != NULL)
3720         {
3721           MALLOC_COPY (newp, oldmem, oldsize - 2 * SIZE_SZ);
3722 #if THREAD_STATS
3723           if(!mutex_trylock(&ar_ptr->mutex))
3724             ++(ar_ptr->stat_lock_direct);
3725           else {
3726             (void)mutex_lock(&ar_ptr->mutex);
3727             ++(ar_ptr->stat_lock_wait);
3728           }
3729 #else
3730           (void)mutex_lock(&ar_ptr->mutex);
3731 #endif
3732           _int_free(ar_ptr, oldmem);
3733           (void)mutex_unlock(&ar_ptr->mutex);
3734         }
3735     }
3736
3737   return newp;
3738 }
3739 #ifdef libc_hidden_def
3740 libc_hidden_def (public_rEALLOc)
3741 #endif
3742
3743 Void_t*
3744 public_mEMALIGn(size_t alignment, size_t bytes)
3745 {
3746   mstate ar_ptr;
3747   Void_t *p;
3748
3749   __malloc_ptr_t (*hook) __MALLOC_PMT ((size_t, size_t,
3750                                         __const __malloc_ptr_t)) =
3751     __memalign_hook;
3752   if (hook != NULL)
3753     return (*hook)(alignment, bytes, RETURN_ADDRESS (0));
3754
3755   /* If need less alignment than we give anyway, just relay to malloc */
3756   if (alignment <= MALLOC_ALIGNMENT) return public_mALLOc(bytes);
3757
3758   /* Otherwise, ensure that it is at least a minimum chunk size */
3759   if (alignment <  MINSIZE) alignment = MINSIZE;
3760
3761   arena_get(ar_ptr, bytes + alignment + MINSIZE);
3762   if(!ar_ptr)
3763     return 0;
3764   p = _int_memalign(ar_ptr, alignment, bytes);
3765   (void)mutex_unlock(&ar_ptr->mutex);
3766   if(!p) {
3767     /* Maybe the failure is due to running out of mmapped areas. */
3768     if(ar_ptr != &main_arena) {
3769       (void)mutex_lock(&main_arena.mutex);
3770       p = _int_memalign(&main_arena, alignment, bytes);
3771       (void)mutex_unlock(&main_arena.mutex);
3772     } else {
3773 #if USE_ARENAS
3774       /* ... or sbrk() has failed and there is still a chance to mmap() */
3775       ar_ptr = arena_get2(ar_ptr->next ? ar_ptr : 0, bytes);
3776       if(ar_ptr) {
3777         p = _int_memalign(ar_ptr, alignment, bytes);
3778         (void)mutex_unlock(&ar_ptr->mutex);
3779       }
3780 #endif
3781     }
3782   }
3783   assert(!p || chunk_is_mmapped(mem2chunk(p)) ||
3784          ar_ptr == arena_for_chunk(mem2chunk(p)));
3785   return p;
3786 }
3787 #ifdef libc_hidden_def
3788 libc_hidden_def (public_mEMALIGn)
3789 #endif
3790
3791 Void_t*
3792 public_vALLOc(size_t bytes)
3793 {
3794   mstate ar_ptr;
3795   Void_t *p;
3796
3797   if(__malloc_initialized < 0)
3798     ptmalloc_init ();
3799
3800   __malloc_ptr_t (*hook) __MALLOC_PMT ((size_t, size_t,
3801                                         __const __malloc_ptr_t)) =
3802     __memalign_hook;
3803   if (hook != NULL)
3804     return (*hook)(mp_.pagesize, bytes, RETURN_ADDRESS (0));
3805
3806   arena_get(ar_ptr, bytes + mp_.pagesize + MINSIZE);
3807   if(!ar_ptr)
3808     return 0;
3809   p = _int_valloc(ar_ptr, bytes);
3810   (void)mutex_unlock(&ar_ptr->mutex);
3811   return p;
3812 }
3813
3814 Void_t*
3815 public_pVALLOc(size_t bytes)
3816 {
3817   mstate ar_ptr;
3818   Void_t *p;
3819
3820   if(__malloc_initialized < 0)
3821     ptmalloc_init ();
3822
3823   __malloc_ptr_t (*hook) __MALLOC_PMT ((size_t, size_t,
3824                                         __const __malloc_ptr_t)) =
3825     __memalign_hook;
3826   if (hook != NULL)
3827     return (*hook)(mp_.pagesize,
3828                    (bytes + mp_.pagesize - 1) & ~(mp_.pagesize - 1),
3829                    RETURN_ADDRESS (0));
3830
3831   arena_get(ar_ptr, bytes + 2*mp_.pagesize + MINSIZE);
3832   p = _int_pvalloc(ar_ptr, bytes);
3833   (void)mutex_unlock(&ar_ptr->mutex);
3834   return p;
3835 }
3836
3837 Void_t*
3838 public_cALLOc(size_t n, size_t elem_size)
3839 {
3840   mstate av;
3841   mchunkptr oldtop, p;
3842   INTERNAL_SIZE_T bytes, sz, csz, oldtopsize;
3843   Void_t* mem;
3844   unsigned long clearsize;
3845   unsigned long nclears;
3846   INTERNAL_SIZE_T* d;
3847   __malloc_ptr_t (*hook) __MALLOC_PMT ((size_t, __const __malloc_ptr_t)) =
3848     __malloc_hook;
3849
3850   /* size_t is unsigned so the behavior on overflow is defined.  */
3851   bytes = n * elem_size;
3852 #define HALF_INTERNAL_SIZE_T \
3853   (((INTERNAL_SIZE_T) 1) << (8 * sizeof (INTERNAL_SIZE_T) / 2))
3854   if (__builtin_expect ((n | elem_size) >= HALF_INTERNAL_SIZE_T, 0)) {
3855     if (elem_size != 0 && bytes / elem_size != n) {
3856       MALLOC_FAILURE_ACTION;
3857       return 0;
3858     }
3859   }
3860
3861   if (hook != NULL) {
3862     sz = bytes;
3863     mem = (*hook)(sz, RETURN_ADDRESS (0));
3864     if(mem == 0)
3865       return 0;
3866 #ifdef HAVE_MEMCPY
3867     return memset(mem, 0, sz);
3868 #else
3869     while(sz > 0) ((char*)mem)[--sz] = 0; /* rather inefficient */
3870     return mem;
3871 #endif
3872   }
3873
3874   sz = bytes;
3875
3876   arena_get(av, sz);
3877   if(!av)
3878     return 0;
3879
3880   /* Check if we hand out the top chunk, in which case there may be no
3881      need to clear. */
3882 #if MORECORE_CLEARS
3883   oldtop = top(av);
3884   oldtopsize = chunksize(top(av));
3885 #if MORECORE_CLEARS < 2
3886   /* Only newly allocated memory is guaranteed to be cleared.  */
3887   if (av == &main_arena &&
3888       oldtopsize < mp_.sbrk_base + av->max_system_mem - (char *)oldtop)
3889     oldtopsize = (mp_.sbrk_base + av->max_system_mem - (char *)oldtop);
3890 #endif
3891 #endif
3892   mem = _int_malloc(av, sz);
3893
3894   /* Only clearing follows, so we can unlock early. */
3895   (void)mutex_unlock(&av->mutex);
3896
3897   assert(!mem || chunk_is_mmapped(mem2chunk(mem)) ||
3898          av == arena_for_chunk(mem2chunk(mem)));
3899
3900   if (mem == 0) {
3901     /* Maybe the failure is due to running out of mmapped areas. */
3902     if(av != &main_arena) {
3903       (void)mutex_lock(&main_arena.mutex);
3904       mem = _int_malloc(&main_arena, sz);
3905       (void)mutex_unlock(&main_arena.mutex);
3906     } else {
3907 #if USE_ARENAS
3908       /* ... or sbrk() has failed and there is still a chance to mmap() */
3909       (void)mutex_lock(&main_arena.mutex);
3910       av = arena_get2(av->next ? av : 0, sz);
3911       (void)mutex_unlock(&main_arena.mutex);
3912       if(av) {
3913         mem = _int_malloc(av, sz);
3914         (void)mutex_unlock(&av->mutex);
3915       }
3916 #endif
3917     }
3918     if (mem == 0) return 0;
3919   }
3920   p = mem2chunk(mem);
3921
3922   /* Two optional cases in which clearing not necessary */
3923 #if HAVE_MMAP
3924   if (chunk_is_mmapped (p))
3925     {
3926       if (__builtin_expect (perturb_byte, 0))
3927         MALLOC_ZERO (mem, sz);
3928       return mem;
3929     }
3930 #endif
3931
3932   csz = chunksize(p);
3933
3934 #if MORECORE_CLEARS
3935   if (perturb_byte == 0 && (p == oldtop && csz > oldtopsize)) {
3936     /* clear only the bytes from non-freshly-sbrked memory */
3937     csz = oldtopsize;
3938   }
3939 #endif
3940
3941   /* Unroll clear of <= 36 bytes (72 if 8byte sizes).  We know that
3942      contents have an odd number of INTERNAL_SIZE_T-sized words;
3943      minimally 3.  */
3944   d = (INTERNAL_SIZE_T*)mem;
3945   clearsize = csz - SIZE_SZ;
3946   nclears = clearsize / sizeof(INTERNAL_SIZE_T);
3947   assert(nclears >= 3);
3948
3949   if (nclears > 9)
3950     MALLOC_ZERO(d, clearsize);
3951
3952   else {
3953     *(d+0) = 0;
3954     *(d+1) = 0;
3955     *(d+2) = 0;
3956     if (nclears > 4) {
3957       *(d+3) = 0;
3958       *(d+4) = 0;
3959       if (nclears > 6) {
3960         *(d+5) = 0;
3961         *(d+6) = 0;
3962         if (nclears > 8) {
3963           *(d+7) = 0;
3964           *(d+8) = 0;
3965         }
3966       }
3967     }
3968   }
3969
3970   return mem;
3971 }
3972
3973 #ifndef _LIBC
3974
3975 Void_t**
3976 public_iCALLOc(size_t n, size_t elem_size, Void_t** chunks)
3977 {
3978   mstate ar_ptr;
3979   Void_t** m;
3980
3981   arena_get(ar_ptr, n*elem_size);
3982   if(!ar_ptr)
3983     return 0;
3984
3985   m = _int_icalloc(ar_ptr, n, elem_size, chunks);
3986   (void)mutex_unlock(&ar_ptr->mutex);
3987   return m;
3988 }
3989
3990 Void_t**
3991 public_iCOMALLOc(size_t n, size_t sizes[], Void_t** chunks)
3992 {
3993   mstate ar_ptr;
3994   Void_t** m;
3995
3996   arena_get(ar_ptr, 0);
3997   if(!ar_ptr)
3998     return 0;
3999
4000   m = _int_icomalloc(ar_ptr, n, sizes, chunks);
4001   (void)mutex_unlock(&ar_ptr->mutex);
4002   return m;
4003 }
4004
4005 void
4006 public_cFREe(Void_t* m)
4007 {
4008   public_fREe(m);
4009 }
4010
4011 #endif /* _LIBC */
4012
4013 int
4014 public_mTRIm(size_t s)
4015 {
4016   int result;
4017
4018   if(__malloc_initialized < 0)
4019     ptmalloc_init ();
4020   (void)mutex_lock(&main_arena.mutex);
4021   result = mTRIm(s);
4022   (void)mutex_unlock(&main_arena.mutex);
4023   return result;
4024 }
4025
4026 size_t
4027 public_mUSABLe(Void_t* m)
4028 {
4029   size_t result;
4030
4031   result = mUSABLe(m);
4032   return result;
4033 }
4034
4035 void
4036 public_mSTATs()
4037 {
4038   mSTATs();
4039 }
4040
4041 struct mallinfo public_mALLINFo()
4042 {
4043   struct mallinfo m;
4044
4045   if(__malloc_initialized < 0)
4046     ptmalloc_init ();
4047   (void)mutex_lock(&main_arena.mutex);
4048   m = mALLINFo(&main_arena);
4049   (void)mutex_unlock(&main_arena.mutex);
4050   return m;
4051 }
4052
4053 int
4054 public_mALLOPt(int p, int v)
4055 {
4056   int result;
4057   result = mALLOPt(p, v);
4058   return result;
4059 }
4060
4061 /*
4062   ------------------------------ malloc ------------------------------
4063 */
4064
4065 Void_t*
4066 _int_malloc(mstate av, size_t bytes)
4067 {
4068   INTERNAL_SIZE_T nb;               /* normalized request size */
4069   unsigned int    idx;              /* associated bin index */
4070   mbinptr         bin;              /* associated bin */
4071   mfastbinptr*    fb;               /* associated fastbin */
4072
4073   mchunkptr       victim;           /* inspected/selected chunk */
4074   INTERNAL_SIZE_T size;             /* its size */
4075   int             victim_index;     /* its bin index */
4076
4077   mchunkptr       remainder;        /* remainder from a split */
4078   unsigned long   remainder_size;   /* its size */
4079
4080   unsigned int    block;            /* bit map traverser */
4081   unsigned int    bit;              /* bit map traverser */
4082   unsigned int    map;              /* current word of binmap */
4083
4084   mchunkptr       fwd;              /* misc temp for linking */
4085   mchunkptr       bck;              /* misc temp for linking */
4086
4087   /*
4088     Convert request size to internal form by adding SIZE_SZ bytes
4089     overhead plus possibly more to obtain necessary alignment and/or
4090     to obtain a size of at least MINSIZE, the smallest allocatable
4091     size. Also, checked_request2size traps (returning 0) request sizes
4092     that are so large that they wrap around zero when padded and
4093     aligned.
4094   */
4095
4096   checked_request2size(bytes, nb);
4097
4098   /*
4099     If the size qualifies as a fastbin, first check corresponding bin.
4100     This code is safe to execute even if av is not yet initialized, so we
4101     can try it without checking, which saves some time on this fast path.
4102   */
4103
4104   if ((unsigned long)(nb) <= (unsigned long)(get_max_fast ())) {
4105     long int idx = fastbin_index(nb);
4106     fb = &(av->fastbins[idx]);
4107     if ( (victim = *fb) != 0) {
4108       if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
4109         malloc_printerr (check_action, "malloc(): memory corruption (fast)",
4110                          chunk2mem (victim));
4111       *fb = victim->fd;
4112       check_remalloced_chunk(av, victim, nb);
4113       void *p = chunk2mem(victim);
4114       if (__builtin_expect (perturb_byte, 0))
4115         alloc_perturb (p, bytes);
4116       return p;
4117     }
4118   }
4119
4120   /*
4121     If a small request, check regular bin.  Since these "smallbins"
4122     hold one size each, no searching within bins is necessary.
4123     (For a large request, we need to wait until unsorted chunks are
4124     processed to find best fit. But for small ones, fits are exact
4125     anyway, so we can check now, which is faster.)
4126   */
4127
4128   if (in_smallbin_range(nb)) {
4129     idx = smallbin_index(nb);
4130     bin = bin_at(av,idx);
4131
4132     if ( (victim = last(bin)) != bin) {
4133       if (victim == 0) /* initialization check */
4134         malloc_consolidate(av);
4135       else {
4136         bck = victim->bk;
4137         set_inuse_bit_at_offset(victim, nb);
4138         bin->bk = bck;
4139         bck->fd = bin;
4140
4141         if (av != &main_arena)
4142           victim->size |= NON_MAIN_ARENA;
4143         check_malloced_chunk(av, victim, nb);
4144         void *p = chunk2mem(victim);
4145         if (__builtin_expect (perturb_byte, 0))
4146           alloc_perturb (p, bytes);
4147         return p;
4148       }
4149     }
4150   }
4151
4152   /*
4153      If this is a large request, consolidate fastbins before continuing.
4154      While it might look excessive to kill all fastbins before
4155      even seeing if there is space available, this avoids
4156      fragmentation problems normally associated with fastbins.
4157      Also, in practice, programs tend to have runs of either small or
4158      large requests, but less often mixtures, so consolidation is not
4159      invoked all that often in most programs. And the programs that
4160      it is called frequently in otherwise tend to fragment.
4161   */
4162
4163   else {
4164     idx = largebin_index(nb);
4165     if (have_fastchunks(av))
4166       malloc_consolidate(av);
4167   }
4168
4169   /*
4170     Process recently freed or remaindered chunks, taking one only if
4171     it is exact fit, or, if this a small request, the chunk is remainder from
4172     the most recent non-exact fit.  Place other traversed chunks in
4173     bins.  Note that this step is the only place in any routine where
4174     chunks are placed in bins.
4175
4176     The outer loop here is needed because we might not realize until
4177     near the end of malloc that we should have consolidated, so must
4178     do so and retry. This happens at most once, and only when we would
4179     otherwise need to expand memory to service a "small" request.
4180   */
4181
4182   for(;;) {
4183
4184     int iters = 0;
4185     while ( (victim = unsorted_chunks(av)->bk) != unsorted_chunks(av)) {
4186       bck = victim->bk;
4187       if (__builtin_expect (victim->size <= 2 * SIZE_SZ, 0)
4188           || __builtin_expect (victim->size > av->system_mem, 0))
4189         malloc_printerr (check_action, "malloc(): memory corruption",
4190                          chunk2mem (victim));
4191       size = chunksize(victim);
4192
4193       /*
4194          If a small request, try to use last remainder if it is the
4195          only chunk in unsorted bin.  This helps promote locality for
4196          runs of consecutive small requests. This is the only
4197          exception to best-fit, and applies only when there is
4198          no exact fit for a small chunk.
4199       */
4200
4201       if (in_smallbin_range(nb) &&
4202           bck == unsorted_chunks(av) &&
4203           victim == av->last_remainder &&
4204           (unsigned long)(size) > (unsigned long)(nb + MINSIZE)) {
4205
4206         /* split and reattach remainder */
4207         remainder_size = size - nb;
4208         remainder = chunk_at_offset(victim, nb);
4209         unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
4210         av->last_remainder = remainder;
4211         remainder->bk = remainder->fd = unsorted_chunks(av);
4212         if (!in_smallbin_range(remainder_size))
4213           {
4214             remainder->fd_nextsize = NULL;
4215             remainder->bk_nextsize = NULL;
4216           }
4217
4218         set_head(victim, nb | PREV_INUSE |
4219                  (av != &main_arena ? NON_MAIN_ARENA : 0));
4220         set_head(remainder, remainder_size | PREV_INUSE);
4221         set_foot(remainder, remainder_size);
4222
4223         check_malloced_chunk(av, victim, nb);
4224         void *p = chunk2mem(victim);
4225         if (__builtin_expect (perturb_byte, 0))
4226           alloc_perturb (p, bytes);
4227         return p;
4228       }
4229
4230       /* remove from unsorted list */
4231       unsorted_chunks(av)->bk = bck;
4232       bck->fd = unsorted_chunks(av);
4233
4234       /* Take now instead of binning if exact fit */
4235
4236       if (size == nb) {
4237         set_inuse_bit_at_offset(victim, size);
4238         if (av != &main_arena)
4239           victim->size |= NON_MAIN_ARENA;
4240         check_malloced_chunk(av, victim, nb);
4241         void *p = chunk2mem(victim);
4242         if (__builtin_expect (perturb_byte, 0))
4243           alloc_perturb (p, bytes);
4244         return p;
4245       }
4246
4247       /* place chunk in bin */
4248
4249       if (in_smallbin_range(size)) {
4250         victim_index = smallbin_index(size);
4251         bck = bin_at(av, victim_index);
4252         fwd = bck->fd;
4253       }
4254       else {
4255         victim_index = largebin_index(size);
4256         bck = bin_at(av, victim_index);
4257         fwd = bck->fd;
4258
4259         /* maintain large bins in sorted order */
4260         if (fwd != bck) {
4261           /* Or with inuse bit to speed comparisons */
4262           size |= PREV_INUSE;
4263           /* if smaller than smallest, bypass loop below */
4264           assert((bck->bk->size & NON_MAIN_ARENA) == 0);
4265           if ((unsigned long)(size) < (unsigned long)(bck->bk->size)) {
4266             fwd = bck;
4267             bck = bck->bk;
4268
4269             victim->fd_nextsize = fwd->fd;
4270             victim->bk_nextsize = fwd->fd->bk_nextsize;
4271             fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
4272           }
4273           else {
4274             assert((fwd->size & NON_MAIN_ARENA) == 0);
4275             while ((unsigned long) size < fwd->size)
4276               {
4277                 fwd = fwd->fd_nextsize;
4278                 assert((fwd->size & NON_MAIN_ARENA) == 0);
4279               }
4280
4281             if ((unsigned long) size == (unsigned long) fwd->size)
4282               /* Always insert in the second position.  */
4283               fwd = fwd->fd;
4284             else
4285               {
4286                 victim->fd_nextsize = fwd;
4287                 victim->bk_nextsize = fwd->bk_nextsize;
4288                 fwd->bk_nextsize = victim;
4289                 victim->bk_nextsize->fd_nextsize = victim;
4290               }
4291             bck = fwd->bk;
4292           }