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