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