2005-11-07 Roland McGrath <roland@redhat.com>
[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 #ifndef _LIBC
1010 /*
1011   independent_calloc(size_t n_elements, size_t element_size, Void_t* chunks[]);
1012
1013   independent_calloc is similar to calloc, but instead of returning a
1014   single cleared space, it returns an array of pointers to n_elements
1015   independent elements that can hold contents of size elem_size, each
1016   of which starts out cleared, and can be independently freed,
1017   realloc'ed etc. The elements are guaranteed to be adjacently
1018   allocated (this is not guaranteed to occur with multiple callocs or
1019   mallocs), which may also improve cache locality in some
1020   applications.
1021
1022   The "chunks" argument is optional (i.e., may be null, which is
1023   probably the most typical usage). If it is null, the returned array
1024   is itself dynamically allocated and should also be freed when it is
1025   no longer needed. Otherwise, the chunks array must be of at least
1026   n_elements in length. It is filled in with the pointers to the
1027   chunks.
1028
1029   In either case, independent_calloc returns this pointer array, or
1030   null if the allocation failed.  If n_elements is zero and "chunks"
1031   is null, it returns a chunk representing an array with zero elements
1032   (which should be freed if not wanted).
1033
1034   Each element must be individually freed when it is no longer
1035   needed. If you'd like to instead be able to free all at once, you
1036   should instead use regular calloc and assign pointers into this
1037   space to represent elements.  (In this case though, you cannot
1038   independently free elements.)
1039
1040   independent_calloc simplifies and speeds up implementations of many
1041   kinds of pools.  It may also be useful when constructing large data
1042   structures that initially have a fixed number of fixed-sized nodes,
1043   but the number is not known at compile time, and some of the nodes
1044   may later need to be freed. For example:
1045
1046   struct Node { int item; struct Node* next; };
1047
1048   struct Node* build_list() {
1049     struct Node** pool;
1050     int n = read_number_of_nodes_needed();
1051     if (n <= 0) return 0;
1052     pool = (struct Node**)(independent_calloc(n, sizeof(struct Node), 0);
1053     if (pool == 0) die();
1054     // organize into a linked list...
1055     struct Node* first = pool[0];
1056     for (i = 0; i < n-1; ++i)
1057       pool[i]->next = pool[i+1];
1058     free(pool);     // Can now free the array (or not, if it is needed later)
1059     return first;
1060   }
1061 */
1062 #if __STD_C
1063 Void_t** public_iCALLOc(size_t, size_t, Void_t**);
1064 #else
1065 Void_t** public_iCALLOc();
1066 #endif
1067
1068 /*
1069   independent_comalloc(size_t n_elements, size_t sizes[], Void_t* chunks[]);
1070
1071   independent_comalloc allocates, all at once, a set of n_elements
1072   chunks with sizes indicated in the "sizes" array.    It returns
1073   an array of pointers to these elements, each of which can be
1074   independently freed, realloc'ed etc. The elements are guaranteed to
1075   be adjacently allocated (this is not guaranteed to occur with
1076   multiple callocs or mallocs), which may also improve cache locality
1077   in some applications.
1078
1079   The "chunks" argument is optional (i.e., may be null). If it is null
1080   the returned array is itself dynamically allocated and should also
1081   be freed when it is no longer needed. Otherwise, the chunks array
1082   must be of at least n_elements in length. It is filled in with the
1083   pointers to the chunks.
1084
1085   In either case, independent_comalloc returns this pointer array, or
1086   null if the allocation failed.  If n_elements is zero and chunks is
1087   null, it returns a chunk representing an array with zero elements
1088   (which should be freed if not wanted).
1089
1090   Each element must be individually freed when it is no longer
1091   needed. If you'd like to instead be able to free all at once, you
1092   should instead use a single regular malloc, and assign pointers at
1093   particular offsets in the aggregate space. (In this case though, you
1094   cannot independently free elements.)
1095
1096   independent_comallac differs from independent_calloc in that each
1097   element may have a different size, and also that it does not
1098   automatically clear elements.
1099
1100   independent_comalloc can be used to speed up allocation in cases
1101   where several structs or objects must always be allocated at the
1102   same time.  For example:
1103
1104   struct Head { ... }
1105   struct Foot { ... }
1106
1107   void send_message(char* msg) {
1108     int msglen = strlen(msg);
1109     size_t sizes[3] = { sizeof(struct Head), msglen, sizeof(struct Foot) };
1110     void* chunks[3];
1111     if (independent_comalloc(3, sizes, chunks) == 0)
1112       die();
1113     struct Head* head = (struct Head*)(chunks[0]);
1114     char*        body = (char*)(chunks[1]);
1115     struct Foot* foot = (struct Foot*)(chunks[2]);
1116     // ...
1117   }
1118
1119   In general though, independent_comalloc is worth using only for
1120   larger values of n_elements. For small values, you probably won't
1121   detect enough difference from series of malloc calls to bother.
1122
1123   Overuse of independent_comalloc can increase overall memory usage,
1124   since it cannot reuse existing noncontiguous small chunks that
1125   might be available for some of the elements.
1126 */
1127 #if __STD_C
1128 Void_t** public_iCOMALLOc(size_t, size_t*, Void_t**);
1129 #else
1130 Void_t** public_iCOMALLOc();
1131 #endif
1132
1133 #endif /* _LIBC */
1134
1135
1136 /*
1137   pvalloc(size_t n);
1138   Equivalent to valloc(minimum-page-that-holds(n)), that is,
1139   round up n to nearest pagesize.
1140  */
1141 #if __STD_C
1142 Void_t*  public_pVALLOc(size_t);
1143 #else
1144 Void_t*  public_pVALLOc();
1145 #endif
1146
1147 /*
1148   cfree(Void_t* p);
1149   Equivalent to free(p).
1150
1151   cfree is needed/defined on some systems that pair it with calloc,
1152   for odd historical reasons (such as: cfree is used in example
1153   code in the first edition of K&R).
1154 */
1155 #if __STD_C
1156 void     public_cFREe(Void_t*);
1157 #else
1158 void     public_cFREe();
1159 #endif
1160
1161 /*
1162   malloc_trim(size_t pad);
1163
1164   If possible, gives memory back to the system (via negative
1165   arguments to sbrk) if there is unused memory at the `high' end of
1166   the malloc pool. You can call this after freeing large blocks of
1167   memory to potentially reduce the system-level memory requirements
1168   of a program. However, it cannot guarantee to reduce memory. Under
1169   some allocation patterns, some large free blocks of memory will be
1170   locked between two used chunks, so they cannot be given back to
1171   the system.
1172
1173   The `pad' argument to malloc_trim represents the amount of free
1174   trailing space to leave untrimmed. If this argument is zero,
1175   only the minimum amount of memory to maintain internal data
1176   structures will be left (one page or less). Non-zero arguments
1177   can be supplied to maintain enough trailing space to service
1178   future expected allocations without having to re-obtain memory
1179   from the system.
1180
1181   Malloc_trim returns 1 if it actually released any memory, else 0.
1182   On systems that do not support "negative sbrks", it will always
1183   rreturn 0.
1184 */
1185 #if __STD_C
1186 int      public_mTRIm(size_t);
1187 #else
1188 int      public_mTRIm();
1189 #endif
1190
1191 /*
1192   malloc_usable_size(Void_t* p);
1193
1194   Returns the number of bytes you can actually use in
1195   an allocated chunk, which may be more than you requested (although
1196   often not) due to alignment and minimum size constraints.
1197   You can use this many bytes without worrying about
1198   overwriting other allocated objects. This is not a particularly great
1199   programming practice. malloc_usable_size can be more useful in
1200   debugging and assertions, for example:
1201
1202   p = malloc(n);
1203   assert(malloc_usable_size(p) >= 256);
1204
1205 */
1206 #if __STD_C
1207 size_t   public_mUSABLe(Void_t*);
1208 #else
1209 size_t   public_mUSABLe();
1210 #endif
1211
1212 /*
1213   malloc_stats();
1214   Prints on stderr the amount of space obtained from the system (both
1215   via sbrk and mmap), the maximum amount (which may be more than
1216   current if malloc_trim and/or munmap got called), and the current
1217   number of bytes allocated via malloc (or realloc, etc) but not yet
1218   freed. Note that this is the number of bytes allocated, not the
1219   number requested. It will be larger than the number requested
1220   because of alignment and bookkeeping overhead. Because it includes
1221   alignment wastage as being in use, this figure may be greater than
1222   zero even when no user-level chunks are allocated.
1223
1224   The reported current and maximum system memory can be inaccurate if
1225   a program makes other calls to system memory allocation functions
1226   (normally sbrk) outside of malloc.
1227
1228   malloc_stats prints only the most commonly interesting statistics.
1229   More information can be obtained by calling mallinfo.
1230
1231 */
1232 #if __STD_C
1233 void     public_mSTATs(void);
1234 #else
1235 void     public_mSTATs();
1236 #endif
1237
1238 /*
1239   malloc_get_state(void);
1240
1241   Returns the state of all malloc variables in an opaque data
1242   structure.
1243 */
1244 #if __STD_C
1245 Void_t*  public_gET_STATe(void);
1246 #else
1247 Void_t*  public_gET_STATe();
1248 #endif
1249
1250 /*
1251   malloc_set_state(Void_t* state);
1252
1253   Restore the state of all malloc variables from data obtained with
1254   malloc_get_state().
1255 */
1256 #if __STD_C
1257 int      public_sET_STATe(Void_t*);
1258 #else
1259 int      public_sET_STATe();
1260 #endif
1261
1262 #ifdef _LIBC
1263 /*
1264   posix_memalign(void **memptr, size_t alignment, size_t size);
1265
1266   POSIX wrapper like memalign(), checking for validity of size.
1267 */
1268 int      __posix_memalign(void **, size_t, size_t);
1269 #endif
1270
1271 /* mallopt tuning options */
1272
1273 /*
1274   M_MXFAST is the maximum request size used for "fastbins", special bins
1275   that hold returned chunks without consolidating their spaces. This
1276   enables future requests for chunks of the same size to be handled
1277   very quickly, but can increase fragmentation, and thus increase the
1278   overall memory footprint of a program.
1279
1280   This malloc manages fastbins very conservatively yet still
1281   efficiently, so fragmentation is rarely a problem for values less
1282   than or equal to the default.  The maximum supported value of MXFAST
1283   is 80. You wouldn't want it any higher than this anyway.  Fastbins
1284   are designed especially for use with many small structs, objects or
1285   strings -- the default handles structs/objects/arrays with sizes up
1286   to 8 4byte fields, or small strings representing words, tokens,
1287   etc. Using fastbins for larger objects normally worsens
1288   fragmentation without improving speed.
1289
1290   M_MXFAST is set in REQUEST size units. It is internally used in
1291   chunksize units, which adds padding and alignment.  You can reduce
1292   M_MXFAST to 0 to disable all use of fastbins.  This causes the malloc
1293   algorithm to be a closer approximation of fifo-best-fit in all cases,
1294   not just for larger requests, but will generally cause it to be
1295   slower.
1296 */
1297
1298
1299 /* M_MXFAST is a standard SVID/XPG tuning option, usually listed in malloc.h */
1300 #ifndef M_MXFAST
1301 #define M_MXFAST            1
1302 #endif
1303
1304 #ifndef DEFAULT_MXFAST
1305 #define DEFAULT_MXFAST     64
1306 #endif
1307
1308
1309 /*
1310   M_TRIM_THRESHOLD is the maximum amount of unused top-most memory
1311   to keep before releasing via malloc_trim in free().
1312
1313   Automatic trimming is mainly useful in long-lived programs.
1314   Because trimming via sbrk can be slow on some systems, and can
1315   sometimes be wasteful (in cases where programs immediately
1316   afterward allocate more large chunks) the value should be high
1317   enough so that your overall system performance would improve by
1318   releasing this much memory.
1319
1320   The trim threshold and the mmap control parameters (see below)
1321   can be traded off with one another. Trimming and mmapping are
1322   two different ways of releasing unused memory back to the
1323   system. Between these two, it is often possible to keep
1324   system-level demands of a long-lived program down to a bare
1325   minimum. For example, in one test suite of sessions measuring
1326   the XF86 X server on Linux, using a trim threshold of 128K and a
1327   mmap threshold of 192K led to near-minimal long term resource
1328   consumption.
1329
1330   If you are using this malloc in a long-lived program, it should
1331   pay to experiment with these values.  As a rough guide, you
1332   might set to a value close to the average size of a process
1333   (program) running on your system.  Releasing this much memory
1334   would allow such a process to run in memory.  Generally, it's
1335   worth it to tune for trimming rather tham memory mapping when a
1336   program undergoes phases where several large chunks are
1337   allocated and released in ways that can reuse each other's
1338   storage, perhaps mixed with phases where there are no such
1339   chunks at all.  And in well-behaved long-lived programs,
1340   controlling release of large blocks via trimming versus mapping
1341   is usually faster.
1342
1343   However, in most programs, these parameters serve mainly as
1344   protection against the system-level effects of carrying around
1345   massive amounts of unneeded memory. Since frequent calls to
1346   sbrk, mmap, and munmap otherwise degrade performance, the default
1347   parameters are set to relatively high values that serve only as
1348   safeguards.
1349
1350   The trim value It must be greater than page size to have any useful
1351   effect.  To disable trimming completely, you can set to
1352   (unsigned long)(-1)
1353
1354   Trim settings interact with fastbin (MXFAST) settings: Unless
1355   TRIM_FASTBINS is defined, automatic trimming never takes place upon
1356   freeing a chunk with size less than or equal to MXFAST. Trimming is
1357   instead delayed until subsequent freeing of larger chunks. However,
1358   you can still force an attempted trim by calling malloc_trim.
1359
1360   Also, trimming is not generally possible in cases where
1361   the main arena is obtained via mmap.
1362
1363   Note that the trick some people use of mallocing a huge space and
1364   then freeing it at program startup, in an attempt to reserve system
1365   memory, doesn't have the intended effect under automatic trimming,
1366   since that memory will immediately be returned to the system.
1367 */
1368
1369 #define M_TRIM_THRESHOLD       -1
1370
1371 #ifndef DEFAULT_TRIM_THRESHOLD
1372 #define DEFAULT_TRIM_THRESHOLD (128 * 1024)
1373 #endif
1374
1375 /*
1376   M_TOP_PAD is the amount of extra `padding' space to allocate or
1377   retain whenever sbrk is called. It is used in two ways internally:
1378
1379   * When sbrk is called to extend the top of the arena to satisfy
1380   a new malloc request, this much padding is added to the sbrk
1381   request.
1382
1383   * When malloc_trim is called automatically from free(),
1384   it is used as the `pad' argument.
1385
1386   In both cases, the actual amount of padding is rounded
1387   so that the end of the arena is always a system page boundary.
1388
1389   The main reason for using padding is to avoid calling sbrk so
1390   often. Having even a small pad greatly reduces the likelihood
1391   that nearly every malloc request during program start-up (or
1392   after trimming) will invoke sbrk, which needlessly wastes
1393   time.
1394
1395   Automatic rounding-up to page-size units is normally sufficient
1396   to avoid measurable overhead, so the default is 0.  However, in
1397   systems where sbrk is relatively slow, it can pay to increase
1398   this value, at the expense of carrying around more memory than
1399   the program needs.
1400 */
1401
1402 #define M_TOP_PAD              -2
1403
1404 #ifndef DEFAULT_TOP_PAD
1405 #define DEFAULT_TOP_PAD        (0)
1406 #endif
1407
1408 /*
1409   M_MMAP_THRESHOLD is the request size threshold for using mmap()
1410   to service a request. Requests of at least this size that cannot
1411   be allocated using already-existing space will be serviced via mmap.
1412   (If enough normal freed space already exists it is used instead.)
1413
1414   Using mmap segregates relatively large chunks of memory so that
1415   they can be individually obtained and released from the host
1416   system. A request serviced through mmap is never reused by any
1417   other request (at least not directly; the system may just so
1418   happen to remap successive requests to the same locations).
1419
1420   Segregating space in this way has the benefits that:
1421
1422    1. Mmapped space can ALWAYS be individually released back
1423       to the system, which helps keep the system level memory
1424       demands of a long-lived program low.
1425    2. Mapped memory can never become `locked' between
1426       other chunks, as can happen with normally allocated chunks, which
1427       means that even trimming via malloc_trim would not release them.
1428    3. On some systems with "holes" in address spaces, mmap can obtain
1429       memory that sbrk cannot.
1430
1431   However, it has the disadvantages that:
1432
1433    1. The space cannot be reclaimed, consolidated, and then
1434       used to service later requests, as happens with normal chunks.
1435    2. It can lead to more wastage because of mmap page alignment
1436       requirements
1437    3. It causes malloc performance to be more dependent on host
1438       system memory management support routines which may vary in
1439       implementation quality and may impose arbitrary
1440       limitations. Generally, servicing a request via normal
1441       malloc steps is faster than going through a system's mmap.
1442
1443   The advantages of mmap nearly always outweigh disadvantages for
1444   "large" chunks, but the value of "large" varies across systems.  The
1445   default is an empirically derived value that works well in most
1446   systems.
1447 */
1448
1449 #define M_MMAP_THRESHOLD      -3
1450
1451 #ifndef DEFAULT_MMAP_THRESHOLD
1452 #define DEFAULT_MMAP_THRESHOLD (128 * 1024)
1453 #endif
1454
1455 /*
1456   M_MMAP_MAX is the maximum number of requests to simultaneously
1457   service using mmap. This parameter exists because
1458   some systems have a limited number of internal tables for
1459   use by mmap, and using more than a few of them may degrade
1460   performance.
1461
1462   The default is set to a value that serves only as a safeguard.
1463   Setting to 0 disables use of mmap for servicing large requests.  If
1464   HAVE_MMAP is not set, the default value is 0, and attempts to set it
1465   to non-zero values in mallopt will fail.
1466 */
1467
1468 #define M_MMAP_MAX             -4
1469
1470 #ifndef DEFAULT_MMAP_MAX
1471 #if HAVE_MMAP
1472 #define DEFAULT_MMAP_MAX       (65536)
1473 #else
1474 #define DEFAULT_MMAP_MAX       (0)
1475 #endif
1476 #endif
1477
1478 #ifdef __cplusplus
1479 } /* end of extern "C" */
1480 #endif
1481
1482 #include <malloc.h>
1483
1484 #ifndef BOUNDED_N
1485 #define BOUNDED_N(ptr, sz) (ptr)
1486 #endif
1487 #ifndef RETURN_ADDRESS
1488 #define RETURN_ADDRESS(X_) (NULL)
1489 #endif
1490
1491 /* On some platforms we can compile internal, not exported functions better.
1492    Let the environment provide a macro and define it to be empty if it
1493    is not available.  */
1494 #ifndef internal_function
1495 # define internal_function
1496 #endif
1497
1498 /* Forward declarations.  */
1499 struct malloc_chunk;
1500 typedef struct malloc_chunk* mchunkptr;
1501
1502 /* Internal routines.  */
1503
1504 #if __STD_C
1505
1506 Void_t*         _int_malloc(mstate, size_t);
1507 void            _int_free(mstate, Void_t*);
1508 Void_t*         _int_realloc(mstate, Void_t*, size_t);
1509 Void_t*         _int_memalign(mstate, size_t, size_t);
1510 Void_t*         _int_valloc(mstate, size_t);
1511 static Void_t*  _int_pvalloc(mstate, size_t);
1512 /*static Void_t*  cALLOc(size_t, size_t);*/
1513 #ifndef _LIBC
1514 static Void_t** _int_icalloc(mstate, size_t, size_t, Void_t**);
1515 static Void_t** _int_icomalloc(mstate, size_t, size_t*, Void_t**);
1516 #endif
1517 static int      mTRIm(size_t);
1518 static size_t   mUSABLe(Void_t*);
1519 static void     mSTATs(void);
1520 static int      mALLOPt(int, int);
1521 static struct mallinfo mALLINFo(mstate);
1522 static void malloc_printerr(int action, const char *str, void *ptr);
1523
1524 static Void_t* internal_function mem2mem_check(Void_t *p, size_t sz);
1525 static int internal_function top_check(void);
1526 static void internal_function munmap_chunk(mchunkptr p);
1527 #if HAVE_MREMAP
1528 static mchunkptr internal_function mremap_chunk(mchunkptr p, size_t new_size);
1529 #endif
1530
1531 static Void_t*   malloc_check(size_t sz, const Void_t *caller);
1532 static void      free_check(Void_t* mem, const Void_t *caller);
1533 static Void_t*   realloc_check(Void_t* oldmem, size_t bytes,
1534                                const Void_t *caller);
1535 static Void_t*   memalign_check(size_t alignment, size_t bytes,
1536                                 const Void_t *caller);
1537 #ifndef NO_THREADS
1538 # ifdef _LIBC
1539 #  if USE___THREAD || (defined USE_TLS && !defined SHARED)
1540     /* These routines are never needed in this configuration.  */
1541 #   define NO_STARTER
1542 #  endif
1543 # endif
1544 # ifdef NO_STARTER
1545 #  undef NO_STARTER
1546 # else
1547 static Void_t*   malloc_starter(size_t sz, const Void_t *caller);
1548 static Void_t*   memalign_starter(size_t aln, size_t sz, const Void_t *caller);
1549 static void      free_starter(Void_t* mem, const Void_t *caller);
1550 # endif
1551 static Void_t*   malloc_atfork(size_t sz, const Void_t *caller);
1552 static void      free_atfork(Void_t* mem, const Void_t *caller);
1553 #endif
1554
1555 #else
1556
1557 Void_t*         _int_malloc();
1558 void            _int_free();
1559 Void_t*         _int_realloc();
1560 Void_t*         _int_memalign();
1561 Void_t*         _int_valloc();
1562 Void_t*         _int_pvalloc();
1563 /*static Void_t*  cALLOc();*/
1564 static Void_t** _int_icalloc();
1565 static Void_t** _int_icomalloc();
1566 static int      mTRIm();
1567 static size_t   mUSABLe();
1568 static void     mSTATs();
1569 static int      mALLOPt();
1570 static struct mallinfo mALLINFo();
1571
1572 #endif
1573
1574
1575
1576
1577 /* ------------- Optional versions of memcopy ---------------- */
1578
1579
1580 #if USE_MEMCPY
1581
1582 /*
1583   Note: memcpy is ONLY invoked with non-overlapping regions,
1584   so the (usually slower) memmove is not needed.
1585 */
1586
1587 #define MALLOC_COPY(dest, src, nbytes)  memcpy(dest, src, nbytes)
1588 #define MALLOC_ZERO(dest, nbytes)       memset(dest, 0,   nbytes)
1589
1590 #else /* !USE_MEMCPY */
1591
1592 /* Use Duff's device for good zeroing/copying performance. */
1593
1594 #define MALLOC_ZERO(charp, nbytes)                                            \
1595 do {                                                                          \
1596   INTERNAL_SIZE_T* mzp = (INTERNAL_SIZE_T*)(charp);                           \
1597   unsigned long mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T);                     \
1598   long mcn;                                                                   \
1599   if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; }             \
1600   switch (mctmp) {                                                            \
1601     case 0: for(;;) { *mzp++ = 0;                                             \
1602     case 7:           *mzp++ = 0;                                             \
1603     case 6:           *mzp++ = 0;                                             \
1604     case 5:           *mzp++ = 0;                                             \
1605     case 4:           *mzp++ = 0;                                             \
1606     case 3:           *mzp++ = 0;                                             \
1607     case 2:           *mzp++ = 0;                                             \
1608     case 1:           *mzp++ = 0; if(mcn <= 0) break; mcn--; }                \
1609   }                                                                           \
1610 } while(0)
1611
1612 #define MALLOC_COPY(dest,src,nbytes)                                          \
1613 do {                                                                          \
1614   INTERNAL_SIZE_T* mcsrc = (INTERNAL_SIZE_T*) src;                            \
1615   INTERNAL_SIZE_T* mcdst = (INTERNAL_SIZE_T*) dest;                           \
1616   unsigned long mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T);                     \
1617   long mcn;                                                                   \
1618   if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; }             \
1619   switch (mctmp) {                                                            \
1620     case 0: for(;;) { *mcdst++ = *mcsrc++;                                    \
1621     case 7:           *mcdst++ = *mcsrc++;                                    \
1622     case 6:           *mcdst++ = *mcsrc++;                                    \
1623     case 5:           *mcdst++ = *mcsrc++;                                    \
1624     case 4:           *mcdst++ = *mcsrc++;                                    \
1625     case 3:           *mcdst++ = *mcsrc++;                                    \
1626     case 2:           *mcdst++ = *mcsrc++;                                    \
1627     case 1:           *mcdst++ = *mcsrc++; if(mcn <= 0) break; mcn--; }       \
1628   }                                                                           \
1629 } while(0)
1630
1631 #endif
1632
1633 /* ------------------ MMAP support ------------------  */
1634
1635
1636 #if HAVE_MMAP
1637
1638 #include <fcntl.h>
1639 #ifndef LACKS_SYS_MMAN_H
1640 #include <sys/mman.h>
1641 #endif
1642
1643 #if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
1644 # define MAP_ANONYMOUS MAP_ANON
1645 #endif
1646 #if !defined(MAP_FAILED)
1647 # define MAP_FAILED ((char*)-1)
1648 #endif
1649
1650 #ifndef MAP_NORESERVE
1651 # ifdef MAP_AUTORESRV
1652 #  define MAP_NORESERVE MAP_AUTORESRV
1653 # else
1654 #  define MAP_NORESERVE 0
1655 # endif
1656 #endif
1657
1658 /*
1659    Nearly all versions of mmap support MAP_ANONYMOUS,
1660    so the following is unlikely to be needed, but is
1661    supplied just in case.
1662 */
1663
1664 #ifndef MAP_ANONYMOUS
1665
1666 static int dev_zero_fd = -1; /* Cached file descriptor for /dev/zero. */
1667
1668 #define MMAP(addr, size, prot, flags) ((dev_zero_fd < 0) ? \
1669  (dev_zero_fd = open("/dev/zero", O_RDWR), \
1670   mmap((addr), (size), (prot), (flags), dev_zero_fd, 0)) : \
1671    mmap((addr), (size), (prot), (flags), dev_zero_fd, 0))
1672
1673 #else
1674
1675 #define MMAP(addr, size, prot, flags) \
1676  (mmap((addr), (size), (prot), (flags)|MAP_ANONYMOUS, -1, 0))
1677
1678 #endif
1679
1680
1681 #endif /* HAVE_MMAP */
1682
1683
1684 /*
1685   -----------------------  Chunk representations -----------------------
1686 */
1687
1688
1689 /*
1690   This struct declaration is misleading (but accurate and necessary).
1691   It declares a "view" into memory allowing access to necessary
1692   fields at known offsets from a given base. See explanation below.
1693 */
1694
1695 struct malloc_chunk {
1696
1697   INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
1698   INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */
1699
1700   struct malloc_chunk* fd;         /* double links -- used only if free. */
1701   struct malloc_chunk* bk;
1702 };
1703
1704
1705 /*
1706    malloc_chunk details:
1707
1708     (The following includes lightly edited explanations by Colin Plumb.)
1709
1710     Chunks of memory are maintained using a `boundary tag' method as
1711     described in e.g., Knuth or Standish.  (See the paper by Paul
1712     Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a
1713     survey of such techniques.)  Sizes of free chunks are stored both
1714     in the front of each chunk and at the end.  This makes
1715     consolidating fragmented chunks into bigger chunks very fast.  The
1716     size fields also hold bits representing whether chunks are free or
1717     in use.
1718
1719     An allocated chunk looks like this:
1720
1721
1722     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1723             |             Size of previous chunk, if allocated            | |
1724             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1725             |             Size of chunk, in bytes                       |M|P|
1726       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1727             |             User data starts here...                          .
1728             .                                                               .
1729             .             (malloc_usable_size() bytes)                      .
1730             .                                                               |
1731 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1732             |             Size of chunk                                     |
1733             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1734
1735
1736     Where "chunk" is the front of the chunk for the purpose of most of
1737     the malloc code, but "mem" is the pointer that is returned to the
1738     user.  "Nextchunk" is the beginning of the next contiguous chunk.
1739
1740     Chunks always begin on even word boundries, so the mem portion
1741     (which is returned to the user) is also on an even word boundary, and
1742     thus at least double-word aligned.
1743
1744     Free chunks are stored in circular doubly-linked lists, and look like this:
1745
1746     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1747             |             Size of previous chunk                            |
1748             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1749     `head:' |             Size of chunk, in bytes                         |P|
1750       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1751             |             Forward pointer to next chunk in list             |
1752             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1753             |             Back pointer to previous chunk in list            |
1754             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1755             |             Unused space (may be 0 bytes long)                .
1756             .                                                               .
1757             .                                                               |
1758 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1759     `foot:' |             Size of chunk, in bytes                           |
1760             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1761
1762     The P (PREV_INUSE) bit, stored in the unused low-order bit of the
1763     chunk size (which is always a multiple of two words), is an in-use
1764     bit for the *previous* chunk.  If that bit is *clear*, then the
1765     word before the current chunk size contains the previous chunk
1766     size, and can be used to find the front of the previous chunk.
1767     The very first chunk allocated always has this bit set,
1768     preventing access to non-existent (or non-owned) memory. If
1769     prev_inuse is set for any given chunk, then you CANNOT determine
1770     the size of the previous chunk, and might even get a memory
1771     addressing fault when trying to do so.
1772
1773     Note that the `foot' of the current chunk is actually represented
1774     as the prev_size of the NEXT chunk. This makes it easier to
1775     deal with alignments etc but can be very confusing when trying
1776     to extend or adapt this code.
1777
1778     The two exceptions to all this are
1779
1780      1. The special chunk `top' doesn't bother using the
1781         trailing size field since there is no next contiguous chunk
1782         that would have to index off it. After initialization, `top'
1783         is forced to always exist.  If it would become less than
1784         MINSIZE bytes long, it is replenished.
1785
1786      2. Chunks allocated via mmap, which have the second-lowest-order
1787         bit M (IS_MMAPPED) set in their size fields.  Because they are
1788         allocated one-by-one, each must contain its own trailing size field.
1789
1790 */
1791
1792 /*
1793   ---------- Size and alignment checks and conversions ----------
1794 */
1795
1796 /* conversion from malloc headers to user pointers, and back */
1797
1798 #define chunk2mem(p)   ((Void_t*)((char*)(p) + 2*SIZE_SZ))
1799 #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))
1800
1801 /* The smallest possible chunk */
1802 #define MIN_CHUNK_SIZE        (sizeof(struct malloc_chunk))
1803
1804 /* The smallest size we can malloc is an aligned minimal chunk */
1805
1806 #define MINSIZE  \
1807   (unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))
1808
1809 /* Check if m has acceptable alignment */
1810
1811 #define aligned_OK(m)  (((unsigned long)((m)) & (MALLOC_ALIGN_MASK)) == 0)
1812
1813
1814 /*
1815    Check if a request is so large that it would wrap around zero when
1816    padded and aligned. To simplify some other code, the bound is made
1817    low enough so that adding MINSIZE will also not wrap around zero.
1818 */
1819
1820 #define REQUEST_OUT_OF_RANGE(req)                                 \
1821   ((unsigned long)(req) >=                                        \
1822    (unsigned long)(INTERNAL_SIZE_T)(-2 * MINSIZE))
1823
1824 /* pad request bytes into a usable size -- internal version */
1825
1826 #define request2size(req)                                         \
1827   (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE)  ?             \
1828    MINSIZE :                                                      \
1829    ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
1830
1831 /*  Same, except also perform argument check */
1832
1833 #define checked_request2size(req, sz)                             \
1834   if (REQUEST_OUT_OF_RANGE(req)) {                                \
1835     MALLOC_FAILURE_ACTION;                                        \
1836     return 0;                                                     \
1837   }                                                               \
1838   (sz) = request2size(req);
1839
1840 /*
1841   --------------- Physical chunk operations ---------------
1842 */
1843
1844
1845 /* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
1846 #define PREV_INUSE 0x1
1847
1848 /* extract inuse bit of previous chunk */
1849 #define prev_inuse(p)       ((p)->size & PREV_INUSE)
1850
1851
1852 /* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */
1853 #define IS_MMAPPED 0x2
1854
1855 /* check for mmap()'ed chunk */
1856 #define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)
1857
1858
1859 /* size field is or'ed with NON_MAIN_ARENA if the chunk was obtained
1860    from a non-main arena.  This is only set immediately before handing
1861    the chunk to the user, if necessary.  */
1862 #define NON_MAIN_ARENA 0x4
1863
1864 /* check for chunk from non-main arena */
1865 #define chunk_non_main_arena(p) ((p)->size & NON_MAIN_ARENA)
1866
1867
1868 /*
1869   Bits to mask off when extracting size
1870
1871   Note: IS_MMAPPED is intentionally not masked off from size field in
1872   macros for which mmapped chunks should never be seen. This should
1873   cause helpful core dumps to occur if it is tried by accident by
1874   people extending or adapting this malloc.
1875 */
1876 #define SIZE_BITS (PREV_INUSE|IS_MMAPPED|NON_MAIN_ARENA)
1877
1878 /* Get size, ignoring use bits */
1879 #define chunksize(p)         ((p)->size & ~(SIZE_BITS))
1880
1881
1882 /* Ptr to next physical malloc_chunk. */
1883 #define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->size & ~SIZE_BITS) ))
1884
1885 /* Ptr to previous physical malloc_chunk */
1886 #define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_size) ))
1887
1888 /* Treat space at ptr + offset as a chunk */
1889 #define chunk_at_offset(p, s)  ((mchunkptr)(((char*)(p)) + (s)))
1890
1891 /* extract p's inuse bit */
1892 #define inuse(p)\
1893 ((((mchunkptr)(((char*)(p))+((p)->size & ~SIZE_BITS)))->size) & PREV_INUSE)
1894
1895 /* set/clear chunk as being inuse without otherwise disturbing */
1896 #define set_inuse(p)\
1897 ((mchunkptr)(((char*)(p)) + ((p)->size & ~SIZE_BITS)))->size |= PREV_INUSE
1898
1899 #define clear_inuse(p)\
1900 ((mchunkptr)(((char*)(p)) + ((p)->size & ~SIZE_BITS)))->size &= ~(PREV_INUSE)
1901
1902
1903 /* check/set/clear inuse bits in known places */
1904 #define inuse_bit_at_offset(p, s)\
1905  (((mchunkptr)(((char*)(p)) + (s)))->size & PREV_INUSE)
1906
1907 #define set_inuse_bit_at_offset(p, s)\
1908  (((mchunkptr)(((char*)(p)) + (s)))->size |= PREV_INUSE)
1909
1910 #define clear_inuse_bit_at_offset(p, s)\
1911  (((mchunkptr)(((char*)(p)) + (s)))->size &= ~(PREV_INUSE))
1912
1913
1914 /* Set size at head, without disturbing its use bit */
1915 #define set_head_size(p, s)  ((p)->size = (((p)->size & SIZE_BITS) | (s)))
1916
1917 /* Set size/use field */
1918 #define set_head(p, s)       ((p)->size = (s))
1919
1920 /* Set size at footer (only when chunk is not in use) */
1921 #define set_foot(p, s)       (((mchunkptr)((char*)(p) + (s)))->prev_size = (s))
1922
1923
1924 /*
1925   -------------------- Internal data structures --------------------
1926
1927    All internal state is held in an instance of malloc_state defined
1928    below. There are no other static variables, except in two optional
1929    cases:
1930    * If USE_MALLOC_LOCK is defined, the mALLOC_MUTEx declared above.
1931    * If HAVE_MMAP is true, but mmap doesn't support
1932      MAP_ANONYMOUS, a dummy file descriptor for mmap.
1933
1934    Beware of lots of tricks that minimize the total bookkeeping space
1935    requirements. The result is a little over 1K bytes (for 4byte
1936    pointers and size_t.)
1937 */
1938
1939 /*
1940   Bins
1941
1942     An array of bin headers for free chunks. Each bin is doubly
1943     linked.  The bins are approximately proportionally (log) spaced.
1944     There are a lot of these bins (128). This may look excessive, but
1945     works very well in practice.  Most bins hold sizes that are
1946     unusual as malloc request sizes, but are more usual for fragments
1947     and consolidated sets of chunks, which is what these bins hold, so
1948     they can be found quickly.  All procedures maintain the invariant
1949     that no consolidated chunk physically borders another one, so each
1950     chunk in a list is known to be preceeded and followed by either
1951     inuse chunks or the ends of memory.
1952
1953     Chunks in bins are kept in size order, with ties going to the
1954     approximately least recently used chunk. Ordering isn't needed
1955     for the small bins, which all contain the same-sized chunks, but
1956     facilitates best-fit allocation for larger chunks. These lists
1957     are just sequential. Keeping them in order almost never requires
1958     enough traversal to warrant using fancier ordered data
1959     structures.
1960
1961     Chunks of the same size are linked with the most
1962     recently freed at the front, and allocations are taken from the
1963     back.  This results in LRU (FIFO) allocation order, which tends
1964     to give each chunk an equal opportunity to be consolidated with
1965     adjacent freed chunks, resulting in larger free chunks and less
1966     fragmentation.
1967
1968     To simplify use in double-linked lists, each bin header acts
1969     as a malloc_chunk. This avoids special-casing for headers.
1970     But to conserve space and improve locality, we allocate
1971     only the fd/bk pointers of bins, and then use repositioning tricks
1972     to treat these as the fields of a malloc_chunk*.
1973 */
1974
1975 typedef struct malloc_chunk* mbinptr;
1976
1977 /* addressing -- note that bin_at(0) does not exist */
1978 #define bin_at(m, i) ((mbinptr)((char*)&((m)->bins[(i)<<1]) - (SIZE_SZ<<1)))
1979
1980 /* analog of ++bin */
1981 #define next_bin(b)  ((mbinptr)((char*)(b) + (sizeof(mchunkptr)<<1)))
1982
1983 /* Reminders about list directionality within bins */
1984 #define first(b)     ((b)->fd)
1985 #define last(b)      ((b)->bk)
1986
1987 /* Take a chunk off a bin list */
1988 #define unlink(P, BK, FD) {                                            \
1989   FD = P->fd;                                                          \
1990   BK = P->bk;                                                          \
1991   if (__builtin_expect (FD->bk != P || BK->fd != P, 0))                \
1992     malloc_printerr (check_action, "corrupted double-linked list", P); \
1993   else {                                                               \
1994     FD->bk = BK;                                                       \
1995     BK->fd = FD;                                                       \
1996   }                                                                    \
1997 }
1998
1999 /*
2000   Indexing
2001
2002     Bins for sizes < 512 bytes contain chunks of all the same size, spaced
2003     8 bytes apart. Larger bins are approximately logarithmically spaced:
2004
2005     64 bins of size       8
2006     32 bins of size      64
2007     16 bins of size     512
2008      8 bins of size    4096
2009      4 bins of size   32768
2010      2 bins of size  262144
2011      1 bin  of size what's left
2012
2013     There is actually a little bit of slop in the numbers in bin_index
2014     for the sake of speed. This makes no difference elsewhere.
2015
2016     The bins top out around 1MB because we expect to service large
2017     requests via mmap.
2018 */
2019
2020 #define NBINS             128
2021 #define NSMALLBINS         64
2022 #define SMALLBIN_WIDTH      8
2023 #define MIN_LARGE_SIZE    512
2024
2025 #define in_smallbin_range(sz)  \
2026   ((unsigned long)(sz) < (unsigned long)MIN_LARGE_SIZE)
2027
2028 #define smallbin_index(sz)     (((unsigned)(sz)) >> 3)
2029
2030 #define largebin_index(sz)                                                   \
2031 (((((unsigned long)(sz)) >>  6) <= 32)?  56 + (((unsigned long)(sz)) >>  6): \
2032  ((((unsigned long)(sz)) >>  9) <= 20)?  91 + (((unsigned long)(sz)) >>  9): \
2033  ((((unsigned long)(sz)) >> 12) <= 10)? 110 + (((unsigned long)(sz)) >> 12): \
2034  ((((unsigned long)(sz)) >> 15) <=  4)? 119 + (((unsigned long)(sz)) >> 15): \
2035  ((((unsigned long)(sz)) >> 18) <=  2)? 124 + (((unsigned long)(sz)) >> 18): \
2036                                         126)
2037
2038 #define bin_index(sz) \
2039  ((in_smallbin_range(sz)) ? smallbin_index(sz) : largebin_index(sz))
2040
2041
2042 /*
2043   Unsorted chunks
2044
2045     All remainders from chunk splits, as well as all returned chunks,
2046     are first placed in the "unsorted" bin. They are then placed
2047     in regular bins after malloc gives them ONE chance to be used before
2048     binning. So, basically, the unsorted_chunks list acts as a queue,
2049     with chunks being placed on it in free (and malloc_consolidate),
2050     and taken off (to be either used or placed in bins) in malloc.
2051
2052     The NON_MAIN_ARENA flag is never set for unsorted chunks, so it
2053     does not have to be taken into account in size comparisons.
2054 */
2055
2056 /* The otherwise unindexable 1-bin is used to hold unsorted chunks. */
2057 #define unsorted_chunks(M)          (bin_at(M, 1))
2058
2059 /*
2060   Top
2061
2062     The top-most available chunk (i.e., the one bordering the end of
2063     available memory) is treated specially. It is never included in
2064     any bin, is used only if no other chunk is available, and is
2065     released back to the system if it is very large (see
2066     M_TRIM_THRESHOLD).  Because top initially
2067     points to its own bin with initial zero size, thus forcing
2068     extension on the first malloc request, we avoid having any special
2069     code in malloc to check whether it even exists yet. But we still
2070     need to do so when getting memory from system, so we make
2071     initial_top treat the bin as a legal but unusable chunk during the
2072     interval between initialization and the first call to
2073     sYSMALLOc. (This is somewhat delicate, since it relies on
2074     the 2 preceding words to be zero during this interval as well.)
2075 */
2076
2077 /* Conveniently, the unsorted bin can be used as dummy top on first call */
2078 #define initial_top(M)              (unsorted_chunks(M))
2079
2080 /*
2081   Binmap
2082
2083     To help compensate for the large number of bins, a one-level index
2084     structure is used for bin-by-bin searching.  `binmap' is a
2085     bitvector recording whether bins are definitely empty so they can
2086     be skipped over during during traversals.  The bits are NOT always
2087     cleared as soon as bins are empty, but instead only
2088     when they are noticed to be empty during traversal in malloc.
2089 */
2090
2091 /* Conservatively use 32 bits per map word, even if on 64bit system */
2092 #define BINMAPSHIFT      5
2093 #define BITSPERMAP       (1U << BINMAPSHIFT)
2094 #define BINMAPSIZE       (NBINS / BITSPERMAP)
2095
2096 #define idx2block(i)     ((i) >> BINMAPSHIFT)
2097 #define idx2bit(i)       ((1U << ((i) & ((1U << BINMAPSHIFT)-1))))
2098
2099 #define mark_bin(m,i)    ((m)->binmap[idx2block(i)] |=  idx2bit(i))
2100 #define unmark_bin(m,i)  ((m)->binmap[idx2block(i)] &= ~(idx2bit(i)))
2101 #define get_binmap(m,i)  ((m)->binmap[idx2block(i)] &   idx2bit(i))
2102
2103 /*
2104   Fastbins
2105
2106     An array of lists holding recently freed small chunks.  Fastbins
2107     are not doubly linked.  It is faster to single-link them, and
2108     since chunks are never removed from the middles of these lists,
2109     double linking is not necessary. Also, unlike regular bins, they
2110     are not even processed in FIFO order (they use faster LIFO) since
2111     ordering doesn't much matter in the transient contexts in which
2112     fastbins are normally used.
2113
2114     Chunks in fastbins keep their inuse bit set, so they cannot
2115     be consolidated with other free chunks. malloc_consolidate
2116     releases all chunks in fastbins and consolidates them with
2117     other free chunks.
2118 */
2119
2120 typedef struct malloc_chunk* mfastbinptr;
2121
2122 /* offset 2 to use otherwise unindexable first 2 bins */
2123 #define fastbin_index(sz)        ((((unsigned int)(sz)) >> 3) - 2)
2124
2125 /* The maximum fastbin request size we support */
2126 #define MAX_FAST_SIZE     80
2127
2128 #define NFASTBINS  (fastbin_index(request2size(MAX_FAST_SIZE))+1)
2129
2130 /*
2131   FASTBIN_CONSOLIDATION_THRESHOLD is the size of a chunk in free()
2132   that triggers automatic consolidation of possibly-surrounding
2133   fastbin chunks. This is a heuristic, so the exact value should not
2134   matter too much. It is defined at half the default trim threshold as a
2135   compromise heuristic to only attempt consolidation if it is likely
2136   to lead to trimming. However, it is not dynamically tunable, since
2137   consolidation reduces fragmentation surrounding large chunks even
2138   if trimming is not used.
2139 */
2140
2141 #define FASTBIN_CONSOLIDATION_THRESHOLD  (65536UL)
2142
2143 /*
2144   Since the lowest 2 bits in max_fast don't matter in size comparisons,
2145   they are used as flags.
2146 */
2147
2148 /*
2149   FASTCHUNKS_BIT held in max_fast indicates that there are probably
2150   some fastbin chunks. It is set true on entering a chunk into any
2151   fastbin, and cleared only in malloc_consolidate.
2152
2153   The truth value is inverted so that have_fastchunks will be true
2154   upon startup (since statics are zero-filled), simplifying
2155   initialization checks.
2156 */
2157
2158 #define FASTCHUNKS_BIT        (1U)
2159
2160 #define have_fastchunks(M)     (((M)->flags &  FASTCHUNKS_BIT) == 0)
2161 #define clear_fastchunks(M)    ((M)->flags |=  FASTCHUNKS_BIT)
2162 #define set_fastchunks(M)      ((M)->flags &= ~FASTCHUNKS_BIT)
2163
2164 /*
2165   NONCONTIGUOUS_BIT indicates that MORECORE does not return contiguous
2166   regions.  Otherwise, contiguity is exploited in merging together,
2167   when possible, results from consecutive MORECORE calls.
2168
2169   The initial value comes from MORECORE_CONTIGUOUS, but is
2170   changed dynamically if mmap is ever used as an sbrk substitute.
2171 */
2172
2173 #define NONCONTIGUOUS_BIT     (2U)
2174
2175 #define contiguous(M)          (((M)->flags &  NONCONTIGUOUS_BIT) == 0)
2176 #define noncontiguous(M)       (((M)->flags &  NONCONTIGUOUS_BIT) != 0)
2177 #define set_noncontiguous(M)   ((M)->flags |=  NONCONTIGUOUS_BIT)
2178 #define set_contiguous(M)      ((M)->flags &= ~NONCONTIGUOUS_BIT)
2179
2180 /*
2181    Set value of max_fast.
2182    Use impossibly small value if 0.
2183    Precondition: there are no existing fastbin chunks.
2184    Setting the value clears fastchunk bit but preserves noncontiguous bit.
2185 */
2186
2187 #define set_max_fast(s) \
2188   global_max_fast = ((s) == 0)? SMALLBIN_WIDTH: request2size(s)
2189 #define get_max_fast() global_max_fast
2190
2191
2192 /*
2193    ----------- Internal state representation and initialization -----------
2194 */
2195
2196 struct malloc_state {
2197   /* Serialize access.  */
2198   mutex_t mutex;
2199
2200   /* Flags (formerly in max_fast).  */
2201   int flags;
2202
2203 #if THREAD_STATS
2204   /* Statistics for locking.  Only used if THREAD_STATS is defined.  */
2205   long stat_lock_direct, stat_lock_loop, stat_lock_wait;
2206 #endif
2207
2208   /* Fastbins */
2209   mfastbinptr      fastbins[NFASTBINS];
2210
2211   /* Base of the topmost chunk -- not otherwise kept in a bin */
2212   mchunkptr        top;
2213
2214   /* The remainder from the most recent split of a small request */
2215   mchunkptr        last_remainder;
2216
2217   /* Normal bins packed as described above */
2218   mchunkptr        bins[NBINS * 2];
2219
2220   /* Bitmap of bins */
2221   unsigned int     binmap[BINMAPSIZE];
2222
2223   /* Linked list */
2224   struct malloc_state *next;
2225
2226   /* Memory allocated from the system in this arena.  */
2227   INTERNAL_SIZE_T system_mem;
2228   INTERNAL_SIZE_T max_system_mem;
2229 };
2230
2231 struct malloc_par {
2232   /* Tunable parameters */
2233   unsigned long    trim_threshold;
2234   INTERNAL_SIZE_T  top_pad;
2235   INTERNAL_SIZE_T  mmap_threshold;
2236
2237   /* Memory map support */
2238   int              n_mmaps;
2239   int              n_mmaps_max;
2240   int              max_n_mmaps;
2241
2242   /* Cache malloc_getpagesize */
2243   unsigned int     pagesize;
2244
2245   /* Statistics */
2246   INTERNAL_SIZE_T  mmapped_mem;
2247   /*INTERNAL_SIZE_T  sbrked_mem;*/
2248   /*INTERNAL_SIZE_T  max_sbrked_mem;*/
2249   INTERNAL_SIZE_T  max_mmapped_mem;
2250   INTERNAL_SIZE_T  max_total_mem; /* only kept for NO_THREADS */
2251
2252   /* First address handed out by MORECORE/sbrk.  */
2253   char*            sbrk_base;
2254 };
2255
2256 /* There are several instances of this struct ("arenas") in this
2257    malloc.  If you are adapting this malloc in a way that does NOT use
2258    a static or mmapped malloc_state, you MUST explicitly zero-fill it
2259    before using. This malloc relies on the property that malloc_state
2260    is initialized to all zeroes (as is true of C statics).  */
2261
2262 static struct malloc_state main_arena;
2263
2264 /* There is only one instance of the malloc parameters.  */
2265
2266 static struct malloc_par mp_;
2267
2268
2269 /* Maximum size of memory handled in fastbins.  */
2270 static INTERNAL_SIZE_T global_max_fast;
2271
2272 /*
2273   Initialize a malloc_state struct.
2274
2275   This is called only from within malloc_consolidate, which needs
2276   be called in the same contexts anyway.  It is never called directly
2277   outside of malloc_consolidate because some optimizing compilers try
2278   to inline it at all call points, which turns out not to be an
2279   optimization at all. (Inlining it in malloc_consolidate is fine though.)
2280 */
2281
2282 #if __STD_C
2283 static void malloc_init_state(mstate av)
2284 #else
2285 static void malloc_init_state(av) mstate av;
2286 #endif
2287 {
2288   int     i;
2289   mbinptr bin;
2290
2291   /* Establish circular links for normal bins */
2292   for (i = 1; i < NBINS; ++i) {
2293     bin = bin_at(av,i);
2294     bin->fd = bin->bk = bin;
2295   }
2296
2297 #if MORECORE_CONTIGUOUS
2298   if (av != &main_arena)
2299 #endif
2300     set_noncontiguous(av);
2301   if (av == &main_arena)
2302     set_max_fast(DEFAULT_MXFAST);
2303   av->flags |= FASTCHUNKS_BIT;
2304
2305   av->top            = initial_top(av);
2306 }
2307
2308 /*
2309    Other internal utilities operating on mstates
2310 */
2311
2312 #if __STD_C
2313 static Void_t*  sYSMALLOc(INTERNAL_SIZE_T, mstate);
2314 static int      sYSTRIm(size_t, mstate);
2315 static void     malloc_consolidate(mstate);
2316 #ifndef _LIBC
2317 static Void_t** iALLOc(mstate, size_t, size_t*, int, Void_t**);
2318 #endif
2319 #else
2320 static Void_t*  sYSMALLOc();
2321 static int      sYSTRIm();
2322 static void     malloc_consolidate();
2323 static Void_t** iALLOc();
2324 #endif
2325
2326
2327 /* -------------- Early definitions for debugging hooks ---------------- */
2328
2329 /* Define and initialize the hook variables.  These weak definitions must
2330    appear before any use of the variables in a function (arena.c uses one).  */
2331 #ifndef weak_variable
2332 #ifndef _LIBC
2333 #define weak_variable /**/
2334 #else
2335 /* In GNU libc we want the hook variables to be weak definitions to
2336    avoid a problem with Emacs.  */
2337 #define weak_variable weak_function
2338 #endif
2339 #endif
2340
2341 /* Forward declarations.  */
2342 static Void_t* malloc_hook_ini __MALLOC_P ((size_t sz,
2343                                             const __malloc_ptr_t caller));
2344 static Void_t* realloc_hook_ini __MALLOC_P ((Void_t* ptr, size_t sz,
2345                                              const __malloc_ptr_t caller));
2346 static Void_t* memalign_hook_ini __MALLOC_P ((size_t alignment, size_t sz,
2347                                               const __malloc_ptr_t caller));
2348
2349 void weak_variable (*__malloc_initialize_hook) (void) = NULL;
2350 void weak_variable (*__free_hook) (__malloc_ptr_t __ptr,
2351                                    const __malloc_ptr_t) = NULL;
2352 __malloc_ptr_t weak_variable (*__malloc_hook)
2353      (size_t __size, const __malloc_ptr_t) = malloc_hook_ini;
2354 __malloc_ptr_t weak_variable (*__realloc_hook)
2355      (__malloc_ptr_t __ptr, size_t __size, const __malloc_ptr_t)
2356      = realloc_hook_ini;
2357 __malloc_ptr_t weak_variable (*__memalign_hook)
2358      (size_t __alignment, size_t __size, const __malloc_ptr_t)
2359      = memalign_hook_ini;
2360 void weak_variable (*__after_morecore_hook) (void) = NULL;
2361
2362
2363 /* ---------------- Error behavior ------------------------------------ */
2364
2365 #ifndef DEFAULT_CHECK_ACTION
2366 #define DEFAULT_CHECK_ACTION 3
2367 #endif
2368
2369 static int check_action = DEFAULT_CHECK_ACTION;
2370
2371
2372 /* ------------------ Testing support ----------------------------------*/
2373
2374 static int perturb_byte;
2375
2376 #define alloc_perturb(p, n) memset (p, (perturb_byte ^ 0xff) & 0xff, n)
2377 #define free_perturb(p, n) memset (p, perturb_byte & 0xff, n)
2378
2379
2380 /* ------------------- Support for multiple arenas -------------------- */
2381 #include "arena.c"
2382
2383 /*
2384   Debugging support
2385
2386   These routines make a number of assertions about the states
2387   of data structures that should be true at all times. If any
2388   are not true, it's very likely that a user program has somehow
2389   trashed memory. (It's also possible that there is a coding error
2390   in malloc. In which case, please report it!)
2391 */
2392
2393 #if ! MALLOC_DEBUG
2394
2395 #define check_chunk(A,P)
2396 #define check_free_chunk(A,P)
2397 #define check_inuse_chunk(A,P)
2398 #define check_remalloced_chunk(A,P,N)
2399 #define check_malloced_chunk(A,P,N)
2400 #define check_malloc_state(A)
2401
2402 #else
2403
2404 #define check_chunk(A,P)              do_check_chunk(A,P)
2405 #define check_free_chunk(A,P)         do_check_free_chunk(A,P)
2406 #define check_inuse_chunk(A,P)        do_check_inuse_chunk(A,P)
2407 #define check_remalloced_chunk(A,P,N) do_check_remalloced_chunk(A,P,N)
2408 #define check_malloced_chunk(A,P,N)   do_check_malloced_chunk(A,P,N)
2409 #define check_malloc_state(A)         do_check_malloc_state(A)
2410
2411 /*
2412   Properties of all chunks
2413 */
2414
2415 #if __STD_C
2416 static void do_check_chunk(mstate av, mchunkptr p)
2417 #else
2418 static void do_check_chunk(av, p) mstate av; mchunkptr p;
2419 #endif
2420 {
2421   unsigned long sz = chunksize(p);
2422   /* min and max possible addresses assuming contiguous allocation */
2423   char* max_address = (char*)(av->top) + chunksize(av->top);
2424   char* min_address = max_address - av->system_mem;
2425
2426   if (!chunk_is_mmapped(p)) {
2427
2428     /* Has legal address ... */
2429     if (p != av->top) {
2430       if (contiguous(av)) {
2431         assert(((char*)p) >= min_address);
2432         assert(((char*)p + sz) <= ((char*)(av->top)));
2433       }
2434     }
2435     else {
2436       /* top size is always at least MINSIZE */
2437       assert((unsigned long)(sz) >= MINSIZE);
2438       /* top predecessor always marked inuse */
2439       assert(prev_inuse(p));
2440     }
2441
2442   }
2443   else {
2444 #if HAVE_MMAP
2445     /* address is outside main heap  */
2446     if (contiguous(av) && av->top != initial_top(av)) {
2447       assert(((char*)p) < min_address || ((char*)p) > max_address);
2448     }
2449     /* chunk is page-aligned */
2450     assert(((p->prev_size + sz) & (mp_.pagesize-1)) == 0);
2451     /* mem is aligned */
2452     assert(aligned_OK(chunk2mem(p)));
2453 #else
2454     /* force an appropriate assert violation if debug set */
2455     assert(!chunk_is_mmapped(p));
2456 #endif
2457   }
2458 }
2459
2460 /*
2461   Properties of free chunks
2462 */
2463
2464 #if __STD_C
2465 static void do_check_free_chunk(mstate av, mchunkptr p)
2466 #else
2467 static void do_check_free_chunk(av, p) mstate av; mchunkptr p;
2468 #endif
2469 {
2470   INTERNAL_SIZE_T sz = p->size & ~(PREV_INUSE|NON_MAIN_ARENA);
2471   mchunkptr next = chunk_at_offset(p, sz);
2472
2473   do_check_chunk(av, p);
2474
2475   /* Chunk must claim to be free ... */
2476   assert(!inuse(p));
2477   assert (!chunk_is_mmapped(p));
2478
2479   /* Unless a special marker, must have OK fields */
2480   if ((unsigned long)(sz) >= MINSIZE)
2481   {
2482     assert((sz & MALLOC_ALIGN_MASK) == 0);
2483     assert(aligned_OK(chunk2mem(p)));
2484     /* ... matching footer field */
2485     assert(next->prev_size == sz);
2486     /* ... and is fully consolidated */
2487     assert(prev_inuse(p));
2488     assert (next == av->top || inuse(next));
2489
2490     /* ... and has minimally sane links */
2491     assert(p->fd->bk == p);
2492     assert(p->bk->fd == p);
2493   }
2494   else /* markers are always of size SIZE_SZ */
2495     assert(sz == SIZE_SZ);
2496 }
2497
2498 /*
2499   Properties of inuse chunks
2500 */
2501
2502 #if __STD_C
2503 static void do_check_inuse_chunk(mstate av, mchunkptr p)
2504 #else
2505 static void do_check_inuse_chunk(av, p) mstate av; mchunkptr p;
2506 #endif
2507 {
2508   mchunkptr next;
2509
2510   do_check_chunk(av, p);
2511
2512   if (chunk_is_mmapped(p))
2513     return; /* mmapped chunks have no next/prev */
2514
2515   /* Check whether it claims to be in use ... */
2516   assert(inuse(p));
2517
2518   next = next_chunk(p);
2519
2520   /* ... and is surrounded by OK chunks.
2521     Since more things can be checked with free chunks than inuse ones,
2522     if an inuse chunk borders them and debug is on, it's worth doing them.
2523   */
2524   if (!prev_inuse(p))  {
2525     /* Note that we cannot even look at prev unless it is not inuse */
2526     mchunkptr prv = prev_chunk(p);
2527     assert(next_chunk(prv) == p);
2528     do_check_free_chunk(av, prv);
2529   }
2530
2531   if (next == av->top) {
2532     assert(prev_inuse(next));
2533     assert(chunksize(next) >= MINSIZE);
2534   }
2535   else if (!inuse(next))
2536     do_check_free_chunk(av, next);
2537 }
2538
2539 /*
2540   Properties of chunks recycled from fastbins
2541 */
2542
2543 #if __STD_C
2544 static void do_check_remalloced_chunk(mstate av, mchunkptr p, INTERNAL_SIZE_T s)
2545 #else
2546 static void do_check_remalloced_chunk(av, p, s)
2547 mstate av; mchunkptr p; INTERNAL_SIZE_T s;
2548 #endif
2549 {
2550   INTERNAL_SIZE_T sz = p->size & ~(PREV_INUSE|NON_MAIN_ARENA);
2551
2552   if (!chunk_is_mmapped(p)) {
2553     assert(av == arena_for_chunk(p));
2554     if (chunk_non_main_arena(p))
2555       assert(av != &main_arena);
2556     else
2557       assert(av == &main_arena);
2558   }
2559
2560   do_check_inuse_chunk(av, p);
2561
2562   /* Legal size ... */
2563   assert((sz & MALLOC_ALIGN_MASK) == 0);
2564   assert((unsigned long)(sz) >= MINSIZE);
2565   /* ... and alignment */
2566   assert(aligned_OK(chunk2mem(p)));
2567   /* chunk is less than MINSIZE more than request */
2568   assert((long)(sz) - (long)(s) >= 0);
2569   assert((long)(sz) - (long)(s + MINSIZE) < 0);
2570 }
2571
2572 /*
2573   Properties of nonrecycled chunks at the point they are malloced
2574 */
2575
2576 #if __STD_C
2577 static void do_check_malloced_chunk(mstate av, mchunkptr p, INTERNAL_SIZE_T s)
2578 #else
2579 static void do_check_malloced_chunk(av, p, s)
2580 mstate av; mchunkptr p; INTERNAL_SIZE_T s;
2581 #endif
2582 {
2583   /* same as recycled case ... */
2584   do_check_remalloced_chunk(av, p, s);
2585
2586   /*
2587     ... plus,  must obey implementation invariant that prev_inuse is
2588     always true of any allocated chunk; i.e., that each allocated
2589     chunk borders either a previously allocated and still in-use
2590     chunk, or the base of its memory arena. This is ensured
2591     by making all allocations from the the `lowest' part of any found
2592     chunk.  This does not necessarily hold however for chunks
2593     recycled via fastbins.
2594   */
2595
2596   assert(prev_inuse(p));
2597 }
2598
2599
2600 /*
2601   Properties of malloc_state.
2602
2603   This may be useful for debugging malloc, as well as detecting user
2604   programmer errors that somehow write into malloc_state.
2605
2606   If you are extending or experimenting with this malloc, you can
2607   probably figure out how to hack this routine to print out or
2608   display chunk addresses, sizes, bins, and other instrumentation.
2609 */
2610
2611 static void do_check_malloc_state(mstate av)
2612 {
2613   int i;
2614   mchunkptr p;
2615   mchunkptr q;
2616   mbinptr b;
2617   unsigned int binbit;
2618   int empty;
2619   unsigned int idx;
2620   INTERNAL_SIZE_T size;
2621   unsigned long total = 0;
2622   int max_fast_bin;
2623
2624   /* internal size_t must be no wider than pointer type */
2625   assert(sizeof(INTERNAL_SIZE_T) <= sizeof(char*));
2626
2627   /* alignment is a power of 2 */
2628   assert((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT-1)) == 0);
2629
2630   /* cannot run remaining checks until fully initialized */
2631   if (av->top == 0 || av->top == initial_top(av))
2632     return;
2633
2634   /* pagesize is a power of 2 */
2635   assert((mp_.pagesize & (mp_.pagesize-1)) == 0);
2636
2637   /* A contiguous main_arena is consistent with sbrk_base.  */
2638   if (av == &main_arena && contiguous(av))
2639     assert((char*)mp_.sbrk_base + av->system_mem ==
2640            (char*)av->top + chunksize(av->top));
2641
2642   /* properties of fastbins */
2643
2644   /* max_fast is in allowed range */
2645   assert((get_max_fast () & ~1) <= request2size(MAX_FAST_SIZE));
2646
2647   max_fast_bin = fastbin_index(get_max_fast ());
2648
2649   for (i = 0; i < NFASTBINS; ++i) {
2650     p = av->fastbins[i];
2651
2652     /* all bins past max_fast are empty */
2653     if (i > max_fast_bin)
2654       assert(p == 0);
2655
2656     while (p != 0) {
2657       /* each chunk claims to be inuse */
2658       do_check_inuse_chunk(av, p);
2659       total += chunksize(p);
2660       /* chunk belongs in this bin */
2661       assert(fastbin_index(chunksize(p)) == i);
2662       p = p->fd;
2663     }
2664   }
2665
2666   if (total != 0)
2667     assert(have_fastchunks(av));
2668   else if (!have_fastchunks(av))
2669     assert(total == 0);
2670
2671   /* check normal bins */
2672   for (i = 1; i < NBINS; ++i) {
2673     b = bin_at(av,i);
2674
2675     /* binmap is accurate (except for bin 1 == unsorted_chunks) */
2676     if (i >= 2) {
2677       binbit = get_binmap(av,i);
2678       empty = last(b) == b;
2679       if (!binbit)
2680         assert(empty);
2681       else if (!empty)
2682         assert(binbit);
2683     }
2684
2685     for (p = last(b); p != b; p = p->bk) {
2686       /* each chunk claims to be free */
2687       do_check_free_chunk(av, p);
2688       size = chunksize(p);
2689       total += size;
2690       if (i >= 2) {
2691         /* chunk belongs in bin */
2692         idx = bin_index(size);
2693         assert(idx == i);
2694         /* lists are sorted */
2695         assert(p->bk == b ||
2696                (unsigned long)chunksize(p->bk) >= (unsigned long)chunksize(p));
2697       }
2698       /* chunk is followed by a legal chain of inuse chunks */
2699       for (q = next_chunk(p);
2700            (q != av->top && inuse(q) &&
2701              (unsigned long)(chunksize(q)) >= MINSIZE);
2702            q = next_chunk(q))
2703         do_check_inuse_chunk(av, q);
2704     }
2705   }
2706
2707   /* top chunk is OK */
2708   check_chunk(av, av->top);
2709
2710   /* sanity checks for statistics */
2711
2712 #ifdef NO_THREADS
2713   assert(total <= (unsigned long)(mp_.max_total_mem));
2714   assert(mp_.n_mmaps >= 0);
2715 #endif
2716   assert(mp_.n_mmaps <= mp_.n_mmaps_max);
2717   assert(mp_.n_mmaps <= mp_.max_n_mmaps);
2718
2719   assert((unsigned long)(av->system_mem) <=
2720          (unsigned long)(av->max_system_mem));
2721
2722   assert((unsigned long)(mp_.mmapped_mem) <=
2723          (unsigned long)(mp_.max_mmapped_mem));
2724
2725 #ifdef NO_THREADS
2726   assert((unsigned long)(mp_.max_total_mem) >=
2727          (unsigned long)(mp_.mmapped_mem) + (unsigned long)(av->system_mem));
2728 #endif
2729 }
2730 #endif
2731
2732
2733 /* ----------------- Support for debugging hooks -------------------- */
2734 #include "hooks.c"
2735
2736
2737 /* ----------- Routines dealing with system allocation -------------- */
2738
2739 /*
2740   sysmalloc handles malloc cases requiring more memory from the system.
2741   On entry, it is assumed that av->top does not have enough
2742   space to service request for nb bytes, thus requiring that av->top
2743   be extended or replaced.
2744 */
2745
2746 #if __STD_C
2747 static Void_t* sYSMALLOc(INTERNAL_SIZE_T nb, mstate av)
2748 #else
2749 static Void_t* sYSMALLOc(nb, av) INTERNAL_SIZE_T nb; mstate av;
2750 #endif
2751 {
2752   mchunkptr       old_top;        /* incoming value of av->top */
2753   INTERNAL_SIZE_T old_size;       /* its size */
2754   char*           old_end;        /* its end address */
2755
2756   long            size;           /* arg to first MORECORE or mmap call */
2757   char*           brk;            /* return value from MORECORE */
2758
2759   long            correction;     /* arg to 2nd MORECORE call */
2760   char*           snd_brk;        /* 2nd return val */
2761
2762   INTERNAL_SIZE_T front_misalign; /* unusable bytes at front of new space */
2763   INTERNAL_SIZE_T end_misalign;   /* partial page left at end of new space */
2764   char*           aligned_brk;    /* aligned offset into brk */
2765
2766   mchunkptr       p;              /* the allocated/returned chunk */
2767   mchunkptr       remainder;      /* remainder from allocation */
2768   unsigned long   remainder_size; /* its size */
2769
2770   unsigned long   sum;            /* for updating stats */
2771
2772   size_t          pagemask  = mp_.pagesize - 1;
2773
2774
2775 #if HAVE_MMAP
2776
2777   /*
2778     If have mmap, and the request size meets the mmap threshold, and
2779     the system supports mmap, and there are few enough currently
2780     allocated mmapped regions, try to directly map this request
2781     rather than expanding top.
2782   */
2783
2784   if ((unsigned long)(nb) >= (unsigned long)(mp_.mmap_threshold) &&
2785       (mp_.n_mmaps < mp_.n_mmaps_max)) {
2786
2787     char* mm;             /* return value from mmap call*/
2788
2789     /*
2790       Round up size to nearest page.  For mmapped chunks, the overhead
2791       is one SIZE_SZ unit larger than for normal chunks, because there
2792       is no following chunk whose prev_size field could be used.
2793     */
2794     size = (nb + SIZE_SZ + MALLOC_ALIGN_MASK + pagemask) & ~pagemask;
2795
2796     /* Don't try if size wraps around 0 */
2797     if ((unsigned long)(size) > (unsigned long)(nb)) {
2798
2799       mm = (char*)(MMAP(0, size, PROT_READ|PROT_WRITE, MAP_PRIVATE));
2800
2801       if (mm != MAP_FAILED) {
2802
2803         /*
2804           The offset to the start of the mmapped region is stored
2805           in the prev_size field of the chunk. This allows us to adjust
2806           returned start address to meet alignment requirements here
2807           and in memalign(), and still be able to compute proper
2808           address argument for later munmap in free() and realloc().
2809         */
2810
2811         front_misalign = (INTERNAL_SIZE_T)chunk2mem(mm) & MALLOC_ALIGN_MASK;
2812         if (front_misalign > 0) {
2813           correction = MALLOC_ALIGNMENT - front_misalign;
2814           p = (mchunkptr)(mm + correction);
2815           p->prev_size = correction;
2816           set_head(p, (size - correction) |IS_MMAPPED);
2817         }
2818         else {
2819           p = (mchunkptr)mm;
2820           set_head(p, size|IS_MMAPPED);
2821         }
2822
2823         /* update statistics */
2824
2825         if (++mp_.n_mmaps > mp_.max_n_mmaps)
2826           mp_.max_n_mmaps = mp_.n_mmaps;
2827
2828         sum = mp_.mmapped_mem += size;
2829         if (sum > (unsigned long)(mp_.max_mmapped_mem))
2830           mp_.max_mmapped_mem = sum;
2831 #ifdef NO_THREADS
2832         sum += av->system_mem;
2833         if (sum > (unsigned long)(mp_.max_total_mem))
2834           mp_.max_total_mem = sum;
2835 #endif
2836
2837         check_chunk(av, p);
2838
2839         return chunk2mem(p);
2840       }
2841     }
2842   }
2843 #endif
2844
2845   /* Record incoming configuration of top */
2846
2847   old_top  = av->top;
2848   old_size = chunksize(old_top);
2849   old_end  = (char*)(chunk_at_offset(old_top, old_size));
2850
2851   brk = snd_brk = (char*)(MORECORE_FAILURE);
2852
2853   /*
2854      If not the first time through, we require old_size to be
2855      at least MINSIZE and to have prev_inuse set.
2856   */
2857
2858   assert((old_top == initial_top(av) && old_size == 0) ||
2859          ((unsigned long) (old_size) >= MINSIZE &&
2860           prev_inuse(old_top) &&
2861           ((unsigned long)old_end & pagemask) == 0));
2862
2863   /* Precondition: not enough current space to satisfy nb request */
2864   assert((unsigned long)(old_size) < (unsigned long)(nb + MINSIZE));
2865
2866   /* Precondition: all fastbins are consolidated */
2867   assert(!have_fastchunks(av));
2868
2869
2870   if (av != &main_arena) {
2871
2872     heap_info *old_heap, *heap;
2873     size_t old_heap_size;
2874
2875     /* First try to extend the current heap. */
2876     old_heap = heap_for_ptr(old_top);
2877     old_heap_size = old_heap->size;
2878     if (grow_heap(old_heap, MINSIZE + nb - old_size) == 0) {
2879       av->system_mem += old_heap->size - old_heap_size;
2880       arena_mem += old_heap->size - old_heap_size;
2881 #if 0
2882       if(mmapped_mem + arena_mem + sbrked_mem > max_total_mem)
2883         max_total_mem = mmapped_mem + arena_mem + sbrked_mem;
2884 #endif
2885       set_head(old_top, (((char *)old_heap + old_heap->size) - (char *)old_top)
2886                | PREV_INUSE);
2887     }
2888     else if ((heap = new_heap(nb + (MINSIZE + sizeof(*heap)), mp_.top_pad))) {
2889       /* Use a newly allocated heap.  */
2890       heap->ar_ptr = av;
2891       heap->prev = old_heap;
2892       av->system_mem += heap->size;
2893       arena_mem += heap->size;
2894 #if 0
2895       if((unsigned long)(mmapped_mem + arena_mem + sbrked_mem) > max_total_mem)
2896         max_total_mem = mmapped_mem + arena_mem + sbrked_mem;
2897 #endif
2898       /* Set up the new top.  */
2899       top(av) = chunk_at_offset(heap, sizeof(*heap));
2900       set_head(top(av), (heap->size - sizeof(*heap)) | PREV_INUSE);
2901
2902       /* Setup fencepost and free the old top chunk. */
2903       /* The fencepost takes at least MINSIZE bytes, because it might
2904          become the top chunk again later.  Note that a footer is set
2905          up, too, although the chunk is marked in use. */
2906       old_size -= MINSIZE;
2907       set_head(chunk_at_offset(old_top, old_size + 2*SIZE_SZ), 0|PREV_INUSE);
2908       if (old_size >= MINSIZE) {
2909         set_head(chunk_at_offset(old_top, old_size), (2*SIZE_SZ)|PREV_INUSE);
2910         set_foot(chunk_at_offset(old_top, old_size), (2*SIZE_SZ));
2911         set_head(old_top, old_size|PREV_INUSE|NON_MAIN_ARENA);
2912         _int_free(av, chunk2mem(old_top));
2913       } else {
2914         set_head(old_top, (old_size + 2*SIZE_SZ)|PREV_INUSE);
2915         set_foot(old_top, (old_size + 2*SIZE_SZ));
2916       }
2917     }
2918
2919   } else { /* av == main_arena */
2920
2921
2922   /* Request enough space for nb + pad + overhead */
2923
2924   size = nb + mp_.top_pad + MINSIZE;
2925
2926   /*
2927     If contiguous, we can subtract out existing space that we hope to
2928     combine with new space. We add it back later only if
2929     we don't actually get contiguous space.
2930   */
2931
2932   if (contiguous(av))
2933     size -= old_size;
2934
2935   /*
2936     Round to a multiple of page size.
2937     If MORECORE is not contiguous, this ensures that we only call it
2938     with whole-page arguments.  And if MORECORE is contiguous and
2939     this is not first time through, this preserves page-alignment of
2940     previous calls. Otherwise, we correct to page-align below.
2941   */
2942
2943   size = (size + pagemask) & ~pagemask;
2944
2945   /*
2946     Don't try to call MORECORE if argument is so big as to appear
2947     negative. Note that since mmap takes size_t arg, it may succeed
2948     below even if we cannot call MORECORE.
2949   */
2950
2951   if (size > 0)
2952     brk = (char*)(MORECORE(size));
2953
2954   if (brk != (char*)(MORECORE_FAILURE)) {
2955     /* Call the `morecore' hook if necessary.  */
2956     if (__after_morecore_hook)
2957       (*__after_morecore_hook) ();
2958   } else {
2959   /*
2960     If have mmap, try using it as a backup when MORECORE fails or
2961     cannot be used. This is worth doing on systems that have "holes" in
2962     address space, so sbrk cannot extend to give contiguous space, but
2963     space is available elsewhere.  Note that we ignore mmap max count
2964     and threshold limits, since the space will not be used as a
2965     segregated mmap region.
2966   */
2967
2968 #if HAVE_MMAP
2969     /* Cannot merge with old top, so add its size back in */
2970     if (contiguous(av))
2971       size = (size + old_size + pagemask) & ~pagemask;
2972
2973     /* If we are relying on mmap as backup, then use larger units */
2974     if ((unsigned long)(size) < (unsigned long)(MMAP_AS_MORECORE_SIZE))
2975       size = MMAP_AS_MORECORE_SIZE;
2976
2977     /* Don't try if size wraps around 0 */
2978     if ((unsigned long)(size) > (unsigned long)(nb)) {
2979
2980       char *mbrk = (char*)(MMAP(0, size, PROT_READ|PROT_WRITE, MAP_PRIVATE));
2981
2982       if (mbrk != MAP_FAILED) {
2983
2984         /* We do not need, and cannot use, another sbrk call to find end */
2985         brk = mbrk;
2986         snd_brk = brk + size;
2987
2988         /*
2989            Record that we no longer have a contiguous sbrk region.
2990            After the first time mmap is used as backup, we do not
2991            ever rely on contiguous space since this could incorrectly
2992            bridge regions.
2993         */
2994         set_noncontiguous(av);
2995       }
2996     }
2997 #endif
2998   }
2999
3000   if (brk != (char*)(MORECORE_FAILURE)) {
3001     if (mp_.sbrk_base == 0)
3002       mp_.sbrk_base = brk;
3003     av->system_mem += size;
3004
3005     /*
3006       If MORECORE extends previous space, we can likewise extend top size.
3007     */
3008
3009     if (brk == old_end && snd_brk == (char*)(MORECORE_FAILURE))
3010       set_head(old_top, (size + old_size) | PREV_INUSE);
3011
3012     else if (contiguous(av) && old_size && brk < old_end) {
3013       /* Oops!  Someone else killed our space..  Can't touch anything.  */
3014       assert(0);
3015     }
3016
3017     /*
3018       Otherwise, make adjustments:
3019
3020       * If the first time through or noncontiguous, we need to call sbrk
3021         just to find out where the end of memory lies.
3022
3023       * We need to ensure that all returned chunks from malloc will meet
3024         MALLOC_ALIGNMENT
3025
3026       * If there was an intervening foreign sbrk, we need to adjust sbrk
3027         request size to account for fact that we will not be able to
3028         combine new space with existing space in old_top.
3029
3030       * Almost all systems internally allocate whole pages at a time, in
3031         which case we might as well use the whole last page of request.
3032         So we allocate enough more memory to hit a page boundary now,
3033         which in turn causes future contiguous calls to page-align.
3034     */
3035
3036     else {
3037       front_misalign = 0;
3038       end_misalign = 0;
3039       correction = 0;
3040       aligned_brk = brk;
3041
3042       /* handle contiguous cases */
3043       if (contiguous(av)) {
3044
3045         /* Count foreign sbrk as system_mem.  */
3046         if (old_size)
3047           av->system_mem += brk - old_end;
3048
3049         /* Guarantee alignment of first new chunk made from this space */
3050
3051         front_misalign = (INTERNAL_SIZE_T)chunk2mem(brk) & MALLOC_ALIGN_MASK;
3052         if (front_misalign > 0) {
3053
3054           /*
3055             Skip over some bytes to arrive at an aligned position.
3056             We don't need to specially mark these wasted front bytes.
3057             They will never be accessed anyway because
3058             prev_inuse of av->top (and any chunk created from its start)
3059             is always true after initialization.
3060           */
3061
3062           correction = MALLOC_ALIGNMENT - front_misalign;
3063           aligned_brk += correction;
3064         }
3065
3066         /*
3067           If this isn't adjacent to existing space, then we will not
3068           be able to merge with old_top space, so must add to 2nd request.
3069         */
3070
3071         correction += old_size;
3072
3073         /* Extend the end address to hit a page boundary */
3074         end_misalign = (INTERNAL_SIZE_T)(brk + size + correction);
3075         correction += ((end_misalign + pagemask) & ~pagemask) - end_misalign;
3076
3077         assert(correction >= 0);
3078         snd_brk = (char*)(MORECORE(correction));
3079
3080         /*
3081           If can't allocate correction, try to at least find out current
3082           brk.  It might be enough to proceed without failing.
3083
3084           Note that if second sbrk did NOT fail, we assume that space
3085           is contiguous with first sbrk. This is a safe assumption unless
3086           program is multithreaded but doesn't use locks and a foreign sbrk
3087           occurred between our first and second calls.
3088         */
3089
3090         if (snd_brk == (char*)(MORECORE_FAILURE)) {
3091           correction = 0;
3092           snd_brk = (char*)(MORECORE(0));
3093         } else
3094           /* Call the `morecore' hook if necessary.  */
3095           if (__after_morecore_hook)
3096             (*__after_morecore_hook) ();
3097       }
3098
3099       /* handle non-contiguous cases */
3100       else {
3101         /* MORECORE/mmap must correctly align */
3102         assert(((unsigned long)chunk2mem(brk) & MALLOC_ALIGN_MASK) == 0);
3103
3104         /* Find out current end of memory */
3105         if (snd_brk == (char*)(MORECORE_FAILURE)) {
3106           snd_brk = (char*)(MORECORE(0));
3107         }
3108       }
3109
3110       /* Adjust top based on results of second sbrk */
3111       if (snd_brk != (char*)(MORECORE_FAILURE)) {
3112         av->top = (mchunkptr)aligned_brk;
3113         set_head(av->top, (snd_brk - aligned_brk + correction) | PREV_INUSE);
3114         av->system_mem += correction;
3115
3116         /*
3117           If not the first time through, we either have a
3118           gap due to foreign sbrk or a non-contiguous region.  Insert a
3119           double fencepost at old_top to prevent consolidation with space
3120           we don't own. These fenceposts are artificial chunks that are
3121           marked as inuse and are in any case too small to use.  We need
3122           two to make sizes and alignments work out.
3123         */
3124
3125         if (old_size != 0) {
3126           /*
3127              Shrink old_top to insert fenceposts, keeping size a
3128              multiple of MALLOC_ALIGNMENT. We know there is at least
3129              enough space in old_top to do this.
3130           */
3131           old_size = (old_size - 4*SIZE_SZ) & ~MALLOC_ALIGN_MASK;
3132           set_head(old_top, old_size | PREV_INUSE);
3133
3134           /*
3135             Note that the following assignments completely overwrite
3136             old_top when old_size was previously MINSIZE.  This is
3137             intentional. We need the fencepost, even if old_top otherwise gets
3138             lost.
3139           */
3140           chunk_at_offset(old_top, old_size            )->size =
3141             (2*SIZE_SZ)|PREV_INUSE;
3142
3143           chunk_at_offset(old_top, old_size + 2*SIZE_SZ)->size =
3144             (2*SIZE_SZ)|PREV_INUSE;
3145
3146           /* If possible, release the rest. */
3147           if (old_size >= MINSIZE) {
3148             _int_free(av, chunk2mem(old_top));
3149           }
3150
3151         }
3152       }
3153     }
3154
3155     /* Update statistics */
3156 #ifdef NO_THREADS
3157     sum = av->system_mem + mp_.mmapped_mem;
3158     if (sum > (unsigned long)(mp_.max_total_mem))
3159       mp_.max_total_mem = sum;
3160 #endif
3161
3162   }
3163
3164   } /* if (av !=  &main_arena) */
3165
3166   if ((unsigned long)av->system_mem > (unsigned long)(av->max_system_mem))
3167     av->max_system_mem = av->system_mem;
3168   check_malloc_state(av);
3169
3170   /* finally, do the allocation */
3171   p = av->top;
3172   size = chunksize(p);
3173
3174   /* check that one of the above allocation paths succeeded */
3175   if ((unsigned long)(size) >= (unsigned long)(nb + MINSIZE)) {
3176     remainder_size = size - nb;
3177     remainder = chunk_at_offset(p, nb);
3178     av->top = remainder;
3179     set_head(p, nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));
3180     set_head(remainder, remainder_size | PREV_INUSE);
3181     check_malloced_chunk(av, p, nb);
3182     return chunk2mem(p);
3183   }
3184
3185   /* catch all failure paths */
3186   MALLOC_FAILURE_ACTION;
3187   return 0;
3188 }
3189
3190
3191 /*
3192   sYSTRIm is an inverse of sorts to sYSMALLOc.  It gives memory back
3193   to the system (via negative arguments to sbrk) if there is unused
3194   memory at the `high' end of the malloc pool. It is called
3195   automatically by free() when top space exceeds the trim
3196   threshold. It is also called by the public malloc_trim routine.  It
3197   returns 1 if it actually released any memory, else 0.
3198 */
3199
3200 #if __STD_C
3201 static int sYSTRIm(size_t pad, mstate av)
3202 #else
3203 static int sYSTRIm(pad, av) size_t pad; mstate av;
3204 #endif
3205 {
3206   long  top_size;        /* Amount of top-most memory */
3207   long  extra;           /* Amount to release */
3208   long  released;        /* Amount actually released */
3209   char* current_brk;     /* address returned by pre-check sbrk call */
3210   char* new_brk;         /* address returned by post-check sbrk call */
3211   size_t pagesz;
3212
3213   pagesz = mp_.pagesize;
3214   top_size = chunksize(av->top);
3215
3216   /* Release in pagesize units, keeping at least one page */
3217   extra = ((top_size - pad - MINSIZE + (pagesz-1)) / pagesz - 1) * pagesz;
3218
3219   if (extra > 0) {
3220
3221     /*
3222       Only proceed if end of memory is where we last set it.
3223       This avoids problems if there were foreign sbrk calls.
3224     */
3225     current_brk = (char*)(MORECORE(0));
3226     if (current_brk == (char*)(av->top) + top_size) {
3227
3228       /*
3229         Attempt to release memory. We ignore MORECORE return value,
3230         and instead call again to find out where new end of memory is.
3231         This avoids problems if first call releases less than we asked,
3232         of if failure somehow altered brk value. (We could still
3233         encounter problems if it altered brk in some very bad way,
3234         but the only thing we can do is adjust anyway, which will cause
3235         some downstream failure.)
3236       */
3237
3238       MORECORE(-extra);
3239       /* Call the `morecore' hook if necessary.  */
3240       if (__after_morecore_hook)
3241         (*__after_morecore_hook) ();
3242       new_brk = (char*)(MORECORE(0));
3243
3244       if (new_brk != (char*)MORECORE_FAILURE) {
3245         released = (long)(current_brk - new_brk);
3246
3247         if (released != 0) {
3248           /* Success. Adjust top. */
3249           av->system_mem -= released;
3250           set_head(av->top, (top_size - released) | PREV_INUSE);
3251           check_malloc_state(av);
3252           return 1;
3253         }
3254       }
3255     }
3256   }
3257   return 0;
3258 }
3259
3260 #ifdef HAVE_MMAP
3261
3262 static void
3263 internal_function
3264 #if __STD_C
3265 munmap_chunk(mchunkptr p)
3266 #else
3267 munmap_chunk(p) mchunkptr p;
3268 #endif
3269 {
3270   INTERNAL_SIZE_T size = chunksize(p);
3271
3272   assert (chunk_is_mmapped(p));
3273 #if 0
3274   assert(! ((char*)p >= mp_.sbrk_base && (char*)p < mp_.sbrk_base + mp_.sbrked_mem));
3275   assert((mp_.n_mmaps > 0));
3276 #endif
3277
3278   uintptr_t block = (uintptr_t) p - p->prev_size;
3279   size_t total_size = p->prev_size + size;
3280   /* Unfortunately we have to do the compilers job by hand here.  Normally
3281      we would test BLOCK and TOTAL-SIZE separately for compliance with the
3282      page size.  But gcc does not recognize the optimization possibility
3283      (in the moment at least) so we combine the two values into one before
3284      the bit test.  */
3285   if (__builtin_expect (((block | total_size) & (mp_.pagesize - 1)) != 0, 0))
3286     {
3287       malloc_printerr (check_action, "munmap_chunk(): invalid pointer",
3288                        chunk2mem (p));
3289       return;
3290     }
3291
3292   mp_.n_mmaps--;
3293   mp_.mmapped_mem -= total_size;
3294
3295   int ret __attribute__ ((unused)) = munmap((char *)block, total_size);
3296
3297   /* munmap returns non-zero on failure */
3298   assert(ret == 0);
3299 }
3300
3301 #if HAVE_MREMAP
3302
3303 static mchunkptr
3304 internal_function
3305 #if __STD_C
3306 mremap_chunk(mchunkptr p, size_t new_size)
3307 #else
3308 mremap_chunk(p, new_size) mchunkptr p; size_t new_size;
3309 #endif
3310 {
3311   size_t page_mask = mp_.pagesize - 1;
3312   INTERNAL_SIZE_T offset = p->prev_size;
3313   INTERNAL_SIZE_T size = chunksize(p);
3314   char *cp;
3315
3316   assert (chunk_is_mmapped(p));
3317 #if 0
3318   assert(! ((char*)p >= mp_.sbrk_base && (char*)p < mp_.sbrk_base + mp_.sbrked_mem));
3319   assert((mp_.n_mmaps > 0));
3320 #endif
3321   assert(((size + offset) & (mp_.pagesize-1)) == 0);
3322
3323   /* Note the extra SIZE_SZ overhead as in mmap_chunk(). */
3324   new_size = (new_size + offset + SIZE_SZ + page_mask) & ~page_mask;
3325
3326   cp = (char *)mremap((char *)p - offset, size + offset, new_size,
3327                       MREMAP_MAYMOVE);
3328
3329   if (cp == MAP_FAILED) return 0;
3330
3331   p = (mchunkptr)(cp + offset);
3332
3333   assert(aligned_OK(chunk2mem(p)));
3334
3335   assert((p->prev_size == offset));
3336   set_head(p, (new_size - offset)|IS_MMAPPED);
3337
3338   mp_.mmapped_mem -= size + offset;
3339   mp_.mmapped_mem += new_size;
3340   if ((unsigned long)mp_.mmapped_mem > (unsigned long)mp_.max_mmapped_mem)
3341     mp_.max_mmapped_mem = mp_.mmapped_mem;
3342 #ifdef NO_THREADS
3343   if ((unsigned long)(mp_.mmapped_mem + arena_mem + main_arena.system_mem) >
3344       mp_.max_total_mem)
3345     mp_.max_total_mem = mp_.mmapped_mem + arena_mem + main_arena.system_mem;
3346 #endif
3347   return p;
3348 }
3349
3350 #endif /* HAVE_MREMAP */
3351
3352 #endif /* HAVE_MMAP */
3353
3354 /*------------------------ Public wrappers. --------------------------------*/
3355
3356 Void_t*
3357 public_mALLOc(size_t bytes)
3358 {
3359   mstate ar_ptr;
3360   Void_t *victim;
3361
3362   __malloc_ptr_t (*hook) (size_t, __const __malloc_ptr_t) = __malloc_hook;
3363   if (hook != NULL)
3364     return (*hook)(bytes, RETURN_ADDRESS (0));
3365
3366   arena_get(ar_ptr, bytes);
3367   if(!ar_ptr)
3368     return 0;
3369   victim = _int_malloc(ar_ptr, bytes);
3370   if(!victim) {
3371     /* Maybe the failure is due to running out of mmapped areas. */
3372     if(ar_ptr != &main_arena) {
3373       (void)mutex_unlock(&ar_ptr->mutex);
3374       (void)mutex_lock(&main_arena.mutex);
3375       victim = _int_malloc(&main_arena, bytes);
3376       (void)mutex_unlock(&main_arena.mutex);
3377     } else {
3378 #if USE_ARENAS
3379       /* ... or sbrk() has failed and there is still a chance to mmap() */
3380       ar_ptr = arena_get2(ar_ptr->next ? ar_ptr : 0, bytes);
3381       (void)mutex_unlock(&main_arena.mutex);
3382       if(ar_ptr) {
3383         victim = _int_malloc(ar_ptr, bytes);
3384         (void)mutex_unlock(&ar_ptr->mutex);
3385       }
3386 #endif
3387     }
3388   } else
3389     (void)mutex_unlock(&ar_ptr->mutex);
3390   assert(!victim || chunk_is_mmapped(mem2chunk(victim)) ||
3391          ar_ptr == arena_for_chunk(mem2chunk(victim)));
3392   return victim;
3393 }
3394 #ifdef libc_hidden_def
3395 libc_hidden_def(public_mALLOc)
3396 #endif
3397
3398 void
3399 public_fREe(Void_t* mem)
3400 {
3401   mstate ar_ptr;
3402   mchunkptr p;                          /* chunk corresponding to mem */
3403
3404   void (*hook) (__malloc_ptr_t, __const __malloc_ptr_t) = __free_hook;
3405   if (hook != NULL) {
3406     (*hook)(mem, RETURN_ADDRESS (0));
3407     return;
3408   }
3409
3410   if (mem == 0)                              /* free(0) has no effect */
3411     return;
3412
3413   p = mem2chunk(mem);
3414
3415 #if HAVE_MMAP
3416   if (chunk_is_mmapped(p))                       /* release mmapped memory. */
3417   {
3418     munmap_chunk(p);
3419     return;
3420   }
3421 #endif
3422
3423   ar_ptr = arena_for_chunk(p);
3424 #if THREAD_STATS
3425   if(!mutex_trylock(&ar_ptr->mutex))
3426     ++(ar_ptr->stat_lock_direct);
3427   else {
3428     (void)mutex_lock(&ar_ptr->mutex);
3429     ++(ar_ptr->stat_lock_wait);
3430   }
3431 #else
3432   (void)mutex_lock(&ar_ptr->mutex);
3433 #endif
3434   _int_free(ar_ptr, mem);
3435   (void)mutex_unlock(&ar_ptr->mutex);
3436 }
3437 #ifdef libc_hidden_def
3438 libc_hidden_def (public_fREe)
3439 #endif
3440
3441 Void_t*
3442 public_rEALLOc(Void_t* oldmem, size_t bytes)
3443 {
3444   mstate ar_ptr;
3445   INTERNAL_SIZE_T    nb;      /* padded request size */
3446
3447   mchunkptr oldp;             /* chunk corresponding to oldmem */
3448   INTERNAL_SIZE_T    oldsize; /* its size */
3449
3450   Void_t* newp;             /* chunk to return */
3451
3452   __malloc_ptr_t (*hook) (__malloc_ptr_t, size_t, __const __malloc_ptr_t) =
3453     __realloc_hook;
3454   if (hook != NULL)
3455     return (*hook)(oldmem, bytes, RETURN_ADDRESS (0));
3456
3457 #if REALLOC_ZERO_BYTES_FREES
3458   if (bytes == 0 && oldmem != NULL) { public_fREe(oldmem); return 0; }
3459 #endif
3460
3461   /* realloc of null is supposed to be same as malloc */
3462   if (oldmem == 0) return public_mALLOc(bytes);
3463
3464   oldp    = mem2chunk(oldmem);
3465   oldsize = chunksize(oldp);
3466
3467   /* Little security check which won't hurt performance: the
3468      allocator never wrapps around at the end of the address space.
3469      Therefore we can exclude some size values which might appear
3470      here by accident or by "design" from some intruder.  */
3471   if (__builtin_expect ((uintptr_t) oldp > (uintptr_t) -oldsize, 0)
3472       || __builtin_expect ((uintptr_t) oldp & MALLOC_ALIGN_MASK, 0))
3473     {
3474       malloc_printerr (check_action, "realloc(): invalid pointer", oldmem);
3475       return NULL;
3476     }
3477
3478   checked_request2size(bytes, nb);
3479
3480 #if HAVE_MMAP
3481   if (chunk_is_mmapped(oldp))
3482   {
3483     Void_t* newmem;
3484
3485 #if HAVE_MREMAP
3486     newp = mremap_chunk(oldp, nb);
3487     if(newp) return chunk2mem(newp);
3488 #endif
3489     /* Note the extra SIZE_SZ overhead. */
3490     if(oldsize - SIZE_SZ >= nb) return oldmem; /* do nothing */
3491     /* Must alloc, copy, free. */
3492     newmem = public_mALLOc(bytes);
3493     if (newmem == 0) return 0; /* propagate failure */
3494     MALLOC_COPY(newmem, oldmem, oldsize - 2*SIZE_SZ);
3495     munmap_chunk(oldp);
3496     return newmem;
3497   }
3498 #endif
3499
3500   ar_ptr = arena_for_chunk(oldp);
3501 #if THREAD_STATS
3502   if(!mutex_trylock(&ar_ptr->mutex))
3503     ++(ar_ptr->stat_lock_direct);
3504   else {
3505     (void)mutex_lock(&ar_ptr->mutex);
3506     ++(ar_ptr->stat_lock_wait);
3507   }
3508 #else
3509   (void)mutex_lock(&ar_ptr->mutex);
3510 #endif
3511
3512 #ifndef NO_THREADS
3513   /* As in malloc(), remember this arena for the next allocation. */
3514   tsd_setspecific(arena_key, (Void_t *)ar_ptr);
3515 #endif
3516
3517   newp = _int_realloc(ar_ptr, oldmem, bytes);
3518
3519   (void)mutex_unlock(&ar_ptr->mutex);
3520   assert(!newp || chunk_is_mmapped(mem2chunk(newp)) ||
3521          ar_ptr == arena_for_chunk(mem2chunk(newp)));
3522   return newp;
3523 }
3524 #ifdef libc_hidden_def
3525 libc_hidden_def (public_rEALLOc)
3526 #endif
3527
3528 Void_t*
3529 public_mEMALIGn(size_t alignment, size_t bytes)
3530 {
3531   mstate ar_ptr;
3532   Void_t *p;
3533
3534   __malloc_ptr_t (*hook) __MALLOC_PMT ((size_t, size_t,
3535                                         __const __malloc_ptr_t)) =
3536     __memalign_hook;
3537   if (hook != NULL)
3538     return (*hook)(alignment, bytes, RETURN_ADDRESS (0));
3539
3540   /* If need less alignment than we give anyway, just relay to malloc */
3541   if (alignment <= MALLOC_ALIGNMENT) return public_mALLOc(bytes);
3542
3543   /* Otherwise, ensure that it is at least a minimum chunk size */
3544   if (alignment <  MINSIZE) alignment = MINSIZE;
3545
3546   arena_get(ar_ptr, bytes + alignment + MINSIZE);
3547   if(!ar_ptr)
3548     return 0;
3549   p = _int_memalign(ar_ptr, alignment, bytes);
3550   (void)mutex_unlock(&ar_ptr->mutex);
3551   if(!p) {
3552     /* Maybe the failure is due to running out of mmapped areas. */
3553     if(ar_ptr != &main_arena) {
3554       (void)mutex_lock(&main_arena.mutex);
3555       p = _int_memalign(&main_arena, alignment, bytes);
3556       (void)mutex_unlock(&main_arena.mutex);
3557     } else {
3558 #if USE_ARENAS
3559       /* ... or sbrk() has failed and there is still a chance to mmap() */
3560       ar_ptr = arena_get2(ar_ptr->next ? ar_ptr : 0, bytes);
3561       if(ar_ptr) {
3562         p = _int_memalign(ar_ptr, alignment, bytes);
3563         (void)mutex_unlock(&ar_ptr->mutex);
3564       }
3565 #endif
3566     }
3567   }
3568   assert(!p || chunk_is_mmapped(mem2chunk(p)) ||
3569          ar_ptr == arena_for_chunk(mem2chunk(p)));
3570   return p;
3571 }
3572 #ifdef libc_hidden_def
3573 libc_hidden_def (public_mEMALIGn)
3574 #endif
3575
3576 Void_t*
3577 public_vALLOc(size_t bytes)
3578 {
3579   mstate ar_ptr;
3580   Void_t *p;
3581
3582   if(__malloc_initialized < 0)
3583     ptmalloc_init ();
3584
3585   __malloc_ptr_t (*hook) __MALLOC_PMT ((size_t, size_t,
3586                                         __const __malloc_ptr_t)) =
3587     __memalign_hook;
3588   if (hook != NULL)
3589     return (*hook)(mp_.pagesize, bytes, RETURN_ADDRESS (0));
3590
3591   arena_get(ar_ptr, bytes + mp_.pagesize + MINSIZE);
3592   if(!ar_ptr)
3593     return 0;
3594   p = _int_valloc(ar_ptr, bytes);
3595   (void)mutex_unlock(&ar_ptr->mutex);
3596   return p;
3597 }
3598
3599 Void_t*
3600 public_pVALLOc(size_t bytes)
3601 {
3602   mstate ar_ptr;
3603   Void_t *p;
3604
3605   if(__malloc_initialized < 0)
3606     ptmalloc_init ();
3607
3608   __malloc_ptr_t (*hook) __MALLOC_PMT ((size_t, size_t,
3609                                         __const __malloc_ptr_t)) =
3610     __memalign_hook;
3611   if (hook != NULL)
3612     return (*hook)(mp_.pagesize,
3613                    (bytes + mp_.pagesize - 1) & ~(mp_.pagesize - 1),
3614                    RETURN_ADDRESS (0));
3615
3616   arena_get(ar_ptr, bytes + 2*mp_.pagesize + MINSIZE);
3617   p = _int_pvalloc(ar_ptr, bytes);
3618   (void)mutex_unlock(&ar_ptr->mutex);
3619   return p;
3620 }
3621
3622 Void_t*
3623 public_cALLOc(size_t n, size_t elem_size)
3624 {
3625   mstate av;
3626   mchunkptr oldtop, p;
3627   INTERNAL_SIZE_T bytes, sz, csz, oldtopsize;
3628   Void_t* mem;
3629   unsigned long clearsize;
3630   unsigned long nclears;
3631   INTERNAL_SIZE_T* d;
3632   __malloc_ptr_t (*hook) __MALLOC_PMT ((size_t, __const __malloc_ptr_t)) =
3633     __malloc_hook;
3634
3635   /* size_t is unsigned so the behavior on overflow is defined.  */
3636   bytes = n * elem_size;
3637 #define HALF_INTERNAL_SIZE_T \
3638   (((INTERNAL_SIZE_T) 1) << (8 * sizeof (INTERNAL_SIZE_T) / 2))
3639   if (__builtin_expect ((n | elem_size) >= HALF_INTERNAL_SIZE_T, 0)) {
3640     if (elem_size != 0 && bytes / elem_size != n) {
3641       MALLOC_FAILURE_ACTION;
3642       return 0;
3643     }
3644   }
3645
3646   if (hook != NULL) {
3647     sz = bytes;
3648     mem = (*hook)(sz, RETURN_ADDRESS (0));
3649     if(mem == 0)
3650       return 0;
3651 #ifdef HAVE_MEMCPY
3652     return memset(mem, 0, sz);
3653 #else
3654     while(sz > 0) ((char*)mem)[--sz] = 0; /* rather inefficient */
3655     return mem;