src/stdlib/SDL_malloc.c
author Sam Lantinga
Mon, 06 Feb 2006 08:58:44 +0000
changeset 1333 39b0d60d3f50
parent 1330 450721ad5436
child 1336 3692456e7b0f
permissions -rw-r--r--
*** empty log message ***
     1 /*
     2     SDL - Simple DirectMedia Layer
     3     Copyright (C) 1997-2006 Sam Lantinga
     4 
     5     This library is free software; you can redistribute it and/or
     6     modify it under the terms of the GNU Lesser General Public
     7     License as published by the Free Software Foundation; either
     8     version 2.1 of the License, or (at your option) any later version.
     9 
    10     This library is distributed in the hope that it will be useful,
    11     but WITHOUT ANY WARRANTY; without even the implied warranty of
    12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    13     Lesser General Public License for more details.
    14 
    15     You should have received a copy of the GNU Lesser General Public
    16     License along with this library; if not, write to the Free Software
    17     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
    18 
    19     Sam Lantinga
    20     slouken@libsdl.org
    21 */
    22 
    23 
    24 /* This file contains portable memory management functions for SDL */
    25 
    26 #include "SDL_stdlib.h"
    27 #include "SDL_string.h"
    28 
    29 #ifndef HAVE_MALLOC
    30 
    31 #define LACKS_STDIO_H
    32 #define LACKS_UNISTD_H
    33 #define LACKS_FCNTL_H
    34 #define LACKS_SYS_PARAM_H
    35 #define LACKS_SYS_MMAN_H
    36 #define LACKS_STRINGS_H
    37 #define LACKS_STRING_H
    38 #define LACKS_SYS_TYPES_H
    39 #define LACKS_ERRNO_H
    40 #define LACKS_STDLIB_H
    41 #define ABORT
    42 
    43 /*
    44   This is a version (aka dlmalloc) of malloc/free/realloc written by
    45   Doug Lea and released to the public domain, as explained at
    46   http://creativecommons.org/licenses/publicdomain.  Send questions,
    47   comments, complaints, performance data, etc to dl@cs.oswego.edu
    48 
    49 * Version 2.8.3 Thu Sep 22 11:16:15 2005  Doug Lea  (dl at gee)
    50 
    51    Note: There may be an updated version of this malloc obtainable at
    52            ftp://gee.cs.oswego.edu/pub/misc/malloc.c
    53          Check before installing!
    54 
    55 * Quickstart
    56 
    57   This library is all in one file to simplify the most common usage:
    58   ftp it, compile it (-O3), and link it into another program. All of
    59   the compile-time options default to reasonable values for use on
    60   most platforms.  You might later want to step through various
    61   compile-time and dynamic tuning options.
    62 
    63   For convenience, an include file for code using this malloc is at:
    64      ftp://gee.cs.oswego.edu/pub/misc/malloc-2.8.3.h
    65   You don't really need this .h file unless you call functions not
    66   defined in your system include files.  The .h file contains only the
    67   excerpts from this file needed for using this malloc on ANSI C/C++
    68   systems, so long as you haven't changed compile-time options about
    69   naming and tuning parameters.  If you do, then you can create your
    70   own malloc.h that does include all settings by cutting at the point
    71   indicated below. Note that you may already by default be using a C
    72   library containing a malloc that is based on some version of this
    73   malloc (for example in linux). You might still want to use the one
    74   in this file to customize settings or to avoid overheads associated
    75   with library versions.
    76 
    77 * Vital statistics:
    78 
    79   Supported pointer/size_t representation:       4 or 8 bytes
    80        size_t MUST be an unsigned type of the same width as
    81        pointers. (If you are using an ancient system that declares
    82        size_t as a signed type, or need it to be a different width
    83        than pointers, you can use a previous release of this malloc
    84        (e.g. 2.7.2) supporting these.)
    85 
    86   Alignment:                                     8 bytes (default)
    87        This suffices for nearly all current machines and C compilers.
    88        However, you can define MALLOC_ALIGNMENT to be wider than this
    89        if necessary (up to 128bytes), at the expense of using more space.
    90 
    91   Minimum overhead per allocated chunk:   4 or  8 bytes (if 4byte sizes)
    92                                           8 or 16 bytes (if 8byte sizes)
    93        Each malloced chunk has a hidden word of overhead holding size
    94        and status information, and additional cross-check word
    95        if FOOTERS is defined.
    96 
    97   Minimum allocated size: 4-byte ptrs:  16 bytes    (including overhead)
    98                           8-byte ptrs:  32 bytes    (including overhead)
    99 
   100        Even a request for zero bytes (i.e., malloc(0)) returns a
   101        pointer to something of the minimum allocatable size.
   102        The maximum overhead wastage (i.e., number of extra bytes
   103        allocated than were requested in malloc) is less than or equal
   104        to the minimum size, except for requests >= mmap_threshold that
   105        are serviced via mmap(), where the worst case wastage is about
   106        32 bytes plus the remainder from a system page (the minimal
   107        mmap unit); typically 4096 or 8192 bytes.
   108 
   109   Security: static-safe; optionally more or less
   110        The "security" of malloc refers to the ability of malicious
   111        code to accentuate the effects of errors (for example, freeing
   112        space that is not currently malloc'ed or overwriting past the
   113        ends of chunks) in code that calls malloc.  This malloc
   114        guarantees not to modify any memory locations below the base of
   115        heap, i.e., static variables, even in the presence of usage
   116        errors.  The routines additionally detect most improper frees
   117        and reallocs.  All this holds as long as the static bookkeeping
   118        for malloc itself is not corrupted by some other means.  This
   119        is only one aspect of security -- these checks do not, and
   120        cannot, detect all possible programming errors.
   121 
   122        If FOOTERS is defined nonzero, then each allocated chunk
   123        carries an additional check word to verify that it was malloced
   124        from its space.  These check words are the same within each
   125        execution of a program using malloc, but differ across
   126        executions, so externally crafted fake chunks cannot be
   127        freed. This improves security by rejecting frees/reallocs that
   128        could corrupt heap memory, in addition to the checks preventing
   129        writes to statics that are always on.  This may further improve
   130        security at the expense of time and space overhead.  (Note that
   131        FOOTERS may also be worth using with MSPACES.)
   132 
   133        By default detected errors cause the program to abort (calling
   134        "abort()"). You can override this to instead proceed past
   135        errors by defining PROCEED_ON_ERROR.  In this case, a bad free
   136        has no effect, and a malloc that encounters a bad address
   137        caused by user overwrites will ignore the bad address by
   138        dropping pointers and indices to all known memory. This may
   139        be appropriate for programs that should continue if at all
   140        possible in the face of programming errors, although they may
   141        run out of memory because dropped memory is never reclaimed.
   142 
   143        If you don't like either of these options, you can define
   144        CORRUPTION_ERROR_ACTION and USAGE_ERROR_ACTION to do anything
   145        else. And if if you are sure that your program using malloc has
   146        no errors or vulnerabilities, you can define INSECURE to 1,
   147        which might (or might not) provide a small performance improvement.
   148 
   149   Thread-safety: NOT thread-safe unless USE_LOCKS defined
   150        When USE_LOCKS is defined, each public call to malloc, free,
   151        etc is surrounded with either a pthread mutex or a win32
   152        spinlock (depending on WIN32). This is not especially fast, and
   153        can be a major bottleneck.  It is designed only to provide
   154        minimal protection in concurrent environments, and to provide a
   155        basis for extensions.  If you are using malloc in a concurrent
   156        program, consider instead using ptmalloc, which is derived from
   157        a version of this malloc. (See http://www.malloc.de).
   158 
   159   System requirements: Any combination of MORECORE and/or MMAP/MUNMAP
   160        This malloc can use unix sbrk or any emulation (invoked using
   161        the CALL_MORECORE macro) and/or mmap/munmap or any emulation
   162        (invoked using CALL_MMAP/CALL_MUNMAP) to get and release system
   163        memory.  On most unix systems, it tends to work best if both
   164        MORECORE and MMAP are enabled.  On Win32, it uses emulations
   165        based on VirtualAlloc. It also uses common C library functions
   166        like memset.
   167 
   168   Compliance: I believe it is compliant with the Single Unix Specification
   169        (See http://www.unix.org). Also SVID/XPG, ANSI C, and probably
   170        others as well.
   171 
   172 * Overview of algorithms
   173 
   174   This is not the fastest, most space-conserving, most portable, or
   175   most tunable malloc ever written. However it is among the fastest
   176   while also being among the most space-conserving, portable and
   177   tunable.  Consistent balance across these factors results in a good
   178   general-purpose allocator for malloc-intensive programs.
   179 
   180   In most ways, this malloc is a best-fit allocator. Generally, it
   181   chooses the best-fitting existing chunk for a request, with ties
   182   broken in approximately least-recently-used order. (This strategy
   183   normally maintains low fragmentation.) However, for requests less
   184   than 256bytes, it deviates from best-fit when there is not an
   185   exactly fitting available chunk by preferring to use space adjacent
   186   to that used for the previous small request, as well as by breaking
   187   ties in approximately most-recently-used order. (These enhance
   188   locality of series of small allocations.)  And for very large requests
   189   (>= 256Kb by default), it relies on system memory mapping
   190   facilities, if supported.  (This helps avoid carrying around and
   191   possibly fragmenting memory used only for large chunks.)
   192 
   193   All operations (except malloc_stats and mallinfo) have execution
   194   times that are bounded by a constant factor of the number of bits in
   195   a size_t, not counting any clearing in calloc or copying in realloc,
   196   or actions surrounding MORECORE and MMAP that have times
   197   proportional to the number of non-contiguous regions returned by
   198   system allocation routines, which is often just 1.
   199 
   200   The implementation is not very modular and seriously overuses
   201   macros. Perhaps someday all C compilers will do as good a job
   202   inlining modular code as can now be done by brute-force expansion,
   203   but now, enough of them seem not to.
   204 
   205   Some compilers issue a lot of warnings about code that is
   206   dead/unreachable only on some platforms, and also about intentional
   207   uses of negation on unsigned types. All known cases of each can be
   208   ignored.
   209 
   210   For a longer but out of date high-level description, see
   211      http://gee.cs.oswego.edu/dl/html/malloc.html
   212 
   213 * MSPACES
   214   If MSPACES is defined, then in addition to malloc, free, etc.,
   215   this file also defines mspace_malloc, mspace_free, etc. These
   216   are versions of malloc routines that take an "mspace" argument
   217   obtained using create_mspace, to control all internal bookkeeping.
   218   If ONLY_MSPACES is defined, only these versions are compiled.
   219   So if you would like to use this allocator for only some allocations,
   220   and your system malloc for others, you can compile with
   221   ONLY_MSPACES and then do something like...
   222     static mspace mymspace = create_mspace(0,0); // for example
   223     #define mymalloc(bytes)  mspace_malloc(mymspace, bytes)
   224 
   225   (Note: If you only need one instance of an mspace, you can instead
   226   use "USE_DL_PREFIX" to relabel the global malloc.)
   227 
   228   You can similarly create thread-local allocators by storing
   229   mspaces as thread-locals. For example:
   230     static __thread mspace tlms = 0;
   231     void*  tlmalloc(size_t bytes) {
   232       if (tlms == 0) tlms = create_mspace(0, 0);
   233       return mspace_malloc(tlms, bytes);
   234     }
   235     void  tlfree(void* mem) { mspace_free(tlms, mem); }
   236 
   237   Unless FOOTERS is defined, each mspace is completely independent.
   238   You cannot allocate from one and free to another (although
   239   conformance is only weakly checked, so usage errors are not always
   240   caught). If FOOTERS is defined, then each chunk carries around a tag
   241   indicating its originating mspace, and frees are directed to their
   242   originating spaces.
   243 
   244  -------------------------  Compile-time options ---------------------------
   245 
   246 Be careful in setting #define values for numerical constants of type
   247 size_t. On some systems, literal values are not automatically extended
   248 to size_t precision unless they are explicitly casted.
   249 
   250 WIN32                    default: defined if _WIN32 defined
   251   Defining WIN32 sets up defaults for MS environment and compilers.
   252   Otherwise defaults are for unix.
   253 
   254 MALLOC_ALIGNMENT         default: (size_t)8
   255   Controls the minimum alignment for malloc'ed chunks.  It must be a
   256   power of two and at least 8, even on machines for which smaller
   257   alignments would suffice. It may be defined as larger than this
   258   though. Note however that code and data structures are optimized for
   259   the case of 8-byte alignment.
   260 
   261 MSPACES                  default: 0 (false)
   262   If true, compile in support for independent allocation spaces.
   263   This is only supported if HAVE_MMAP is true.
   264 
   265 ONLY_MSPACES             default: 0 (false)
   266   If true, only compile in mspace versions, not regular versions.
   267 
   268 USE_LOCKS                default: 0 (false)
   269   Causes each call to each public routine to be surrounded with
   270   pthread or WIN32 mutex lock/unlock. (If set true, this can be
   271   overridden on a per-mspace basis for mspace versions.)
   272 
   273 FOOTERS                  default: 0
   274   If true, provide extra checking and dispatching by placing
   275   information in the footers of allocated chunks. This adds
   276   space and time overhead.
   277 
   278 INSECURE                 default: 0
   279   If true, omit checks for usage errors and heap space overwrites.
   280 
   281 USE_DL_PREFIX            default: NOT defined
   282   Causes compiler to prefix all public routines with the string 'dl'.
   283   This can be useful when you only want to use this malloc in one part
   284   of a program, using your regular system malloc elsewhere.
   285 
   286 ABORT                    default: defined as abort()
   287   Defines how to abort on failed checks.  On most systems, a failed
   288   check cannot die with an "assert" or even print an informative
   289   message, because the underlying print routines in turn call malloc,
   290   which will fail again.  Generally, the best policy is to simply call
   291   abort(). It's not very useful to do more than this because many
   292   errors due to overwriting will show up as address faults (null, odd
   293   addresses etc) rather than malloc-triggered checks, so will also
   294   abort.  Also, most compilers know that abort() does not return, so
   295   can better optimize code conditionally calling it.
   296 
   297 PROCEED_ON_ERROR           default: defined as 0 (false)
   298   Controls whether detected bad addresses cause them to bypassed
   299   rather than aborting. If set, detected bad arguments to free and
   300   realloc are ignored. And all bookkeeping information is zeroed out
   301   upon a detected overwrite of freed heap space, thus losing the
   302   ability to ever return it from malloc again, but enabling the
   303   application to proceed. If PROCEED_ON_ERROR is defined, the
   304   static variable malloc_corruption_error_count is compiled in
   305   and can be examined to see if errors have occurred. This option
   306   generates slower code than the default abort policy.
   307 
   308 DEBUG                    default: NOT defined
   309   The DEBUG setting is mainly intended for people trying to modify
   310   this code or diagnose problems when porting to new platforms.
   311   However, it may also be able to better isolate user errors than just
   312   using runtime checks.  The assertions in the check routines spell
   313   out in more detail the assumptions and invariants underlying the
   314   algorithms.  The checking is fairly extensive, and will slow down
   315   execution noticeably. Calling malloc_stats or mallinfo with DEBUG
   316   set will attempt to check every non-mmapped allocated and free chunk
   317   in the course of computing the summaries.
   318 
   319 ABORT_ON_ASSERT_FAILURE   default: defined as 1 (true)
   320   Debugging assertion failures can be nearly impossible if your
   321   version of the assert macro causes malloc to be called, which will
   322   lead to a cascade of further failures, blowing the runtime stack.
   323   ABORT_ON_ASSERT_FAILURE cause assertions failures to call abort(),
   324   which will usually make debugging easier.
   325 
   326 MALLOC_FAILURE_ACTION     default: sets errno to ENOMEM, or no-op on win32
   327   The action to take before "return 0" when malloc fails to be able to
   328   return memory because there is none available.
   329 
   330 HAVE_MORECORE             default: 1 (true) unless win32 or ONLY_MSPACES
   331   True if this system supports sbrk or an emulation of it.
   332 
   333 MORECORE                  default: sbrk
   334   The name of the sbrk-style system routine to call to obtain more
   335   memory.  See below for guidance on writing custom MORECORE
   336   functions. The type of the argument to sbrk/MORECORE varies across
   337   systems.  It cannot be size_t, because it supports negative
   338   arguments, so it is normally the signed type of the same width as
   339   size_t (sometimes declared as "intptr_t").  It doesn't much matter
   340   though. Internally, we only call it with arguments less than half
   341   the max value of a size_t, which should work across all reasonable
   342   possibilities, although sometimes generating compiler warnings.  See
   343   near the end of this file for guidelines for creating a custom
   344   version of MORECORE.
   345 
   346 MORECORE_CONTIGUOUS       default: 1 (true)
   347   If true, take advantage of fact that consecutive calls to MORECORE
   348   with positive arguments always return contiguous increasing
   349   addresses.  This is true of unix sbrk. It does not hurt too much to
   350   set it true anyway, since malloc copes with non-contiguities.
   351   Setting it false when definitely non-contiguous saves time
   352   and possibly wasted space it would take to discover this though.
   353 
   354 MORECORE_CANNOT_TRIM      default: NOT defined
   355   True if MORECORE cannot release space back to the system when given
   356   negative arguments. This is generally necessary only if you are
   357   using a hand-crafted MORECORE function that cannot handle negative
   358   arguments.
   359 
   360 HAVE_MMAP                 default: 1 (true)
   361   True if this system supports mmap or an emulation of it.  If so, and
   362   HAVE_MORECORE is not true, MMAP is used for all system
   363   allocation. If set and HAVE_MORECORE is true as well, MMAP is
   364   primarily used to directly allocate very large blocks. It is also
   365   used as a backup strategy in cases where MORECORE fails to provide
   366   space from system. Note: A single call to MUNMAP is assumed to be
   367   able to unmap memory that may have be allocated using multiple calls
   368   to MMAP, so long as they are adjacent.
   369 
   370 HAVE_MREMAP               default: 1 on linux, else 0
   371   If true realloc() uses mremap() to re-allocate large blocks and
   372   extend or shrink allocation spaces.
   373 
   374 MMAP_CLEARS               default: 1 on unix
   375   True if mmap clears memory so calloc doesn't need to. This is true
   376   for standard unix mmap using /dev/zero.
   377 
   378 USE_BUILTIN_FFS            default: 0 (i.e., not used)
   379   Causes malloc to use the builtin ffs() function to compute indices.
   380   Some compilers may recognize and intrinsify ffs to be faster than the
   381   supplied C version. Also, the case of x86 using gcc is special-cased
   382   to an asm instruction, so is already as fast as it can be, and so
   383   this setting has no effect. (On most x86s, the asm version is only
   384   slightly faster than the C version.)
   385 
   386 malloc_getpagesize         default: derive from system includes, or 4096.
   387   The system page size. To the extent possible, this malloc manages
   388   memory from the system in page-size units.  This may be (and
   389   usually is) a function rather than a constant. This is ignored
   390   if WIN32, where page size is determined using getSystemInfo during
   391   initialization.
   392 
   393 USE_DEV_RANDOM             default: 0 (i.e., not used)
   394   Causes malloc to use /dev/random to initialize secure magic seed for
   395   stamping footers. Otherwise, the current time is used.
   396 
   397 NO_MALLINFO                default: 0
   398   If defined, don't compile "mallinfo". This can be a simple way
   399   of dealing with mismatches between system declarations and
   400   those in this file.
   401 
   402 MALLINFO_FIELD_TYPE        default: size_t
   403   The type of the fields in the mallinfo struct. This was originally
   404   defined as "int" in SVID etc, but is more usefully defined as
   405   size_t. The value is used only if  HAVE_USR_INCLUDE_MALLOC_H is not set
   406 
   407 REALLOC_ZERO_BYTES_FREES    default: not defined
   408   This should be set if a call to realloc with zero bytes should 
   409   be the same as a call to free. Some people think it should. Otherwise, 
   410   since this malloc returns a unique pointer for malloc(0), so does 
   411   realloc(p, 0).
   412 
   413 LACKS_UNISTD_H, LACKS_FCNTL_H, LACKS_SYS_PARAM_H, LACKS_SYS_MMAN_H
   414 LACKS_STRINGS_H, LACKS_STRING_H, LACKS_SYS_TYPES_H,  LACKS_ERRNO_H
   415 LACKS_STDLIB_H                default: NOT defined unless on WIN32
   416   Define these if your system does not have these header files.
   417   You might need to manually insert some of the declarations they provide.
   418 
   419 DEFAULT_GRANULARITY        default: page size if MORECORE_CONTIGUOUS,
   420                                 system_info.dwAllocationGranularity in WIN32,
   421                                 otherwise 64K.
   422       Also settable using mallopt(M_GRANULARITY, x)
   423   The unit for allocating and deallocating memory from the system.  On
   424   most systems with contiguous MORECORE, there is no reason to
   425   make this more than a page. However, systems with MMAP tend to
   426   either require or encourage larger granularities.  You can increase
   427   this value to prevent system allocation functions to be called so
   428   often, especially if they are slow.  The value must be at least one
   429   page and must be a power of two.  Setting to 0 causes initialization
   430   to either page size or win32 region size.  (Note: In previous
   431   versions of malloc, the equivalent of this option was called
   432   "TOP_PAD")
   433 
   434 DEFAULT_TRIM_THRESHOLD    default: 2MB
   435       Also settable using mallopt(M_TRIM_THRESHOLD, x)
   436   The maximum amount of unused top-most memory to keep before
   437   releasing via malloc_trim in free().  Automatic trimming is mainly
   438   useful in long-lived programs using contiguous MORECORE.  Because
   439   trimming via sbrk can be slow on some systems, and can sometimes be
   440   wasteful (in cases where programs immediately afterward allocate
   441   more large chunks) the value should be high enough so that your
   442   overall system performance would improve by releasing this much
   443   memory.  As a rough guide, you might set to a value close to the
   444   average size of a process (program) running on your system.
   445   Releasing this much memory would allow such a process to run in
   446   memory.  Generally, it is worth tuning trim thresholds when a
   447   program undergoes phases where several large chunks are allocated
   448   and released in ways that can reuse each other's storage, perhaps
   449   mixed with phases where there are no such chunks at all. The trim
   450   value must be greater than page size to have any useful effect.  To
   451   disable trimming completely, you can set to MAX_SIZE_T. Note that the trick
   452   some people use of mallocing a huge space and then freeing it at
   453   program startup, in an attempt to reserve system memory, doesn't
   454   have the intended effect under automatic trimming, since that memory
   455   will immediately be returned to the system.
   456 
   457 DEFAULT_MMAP_THRESHOLD       default: 256K
   458       Also settable using mallopt(M_MMAP_THRESHOLD, x)
   459   The request size threshold for using MMAP to directly service a
   460   request. Requests of at least this size that cannot be allocated
   461   using already-existing space will be serviced via mmap.  (If enough
   462   normal freed space already exists it is used instead.)  Using mmap
   463   segregates relatively large chunks of memory so that they can be
   464   individually obtained and released from the host system. A request
   465   serviced through mmap is never reused by any other request (at least
   466   not directly; the system may just so happen to remap successive
   467   requests to the same locations).  Segregating space in this way has
   468   the benefits that: Mmapped space can always be individually released
   469   back to the system, which helps keep the system level memory demands
   470   of a long-lived program low.  Also, mapped memory doesn't become
   471   `locked' between other chunks, as can happen with normally allocated
   472   chunks, which means that even trimming via malloc_trim would not
   473   release them.  However, it has the disadvantage that the space
   474   cannot be reclaimed, consolidated, and then used to service later
   475   requests, as happens with normal chunks.  The advantages of mmap
   476   nearly always outweigh disadvantages for "large" chunks, but the
   477   value of "large" may vary across systems.  The default is an
   478   empirically derived value that works well in most systems. You can
   479   disable mmap by setting to MAX_SIZE_T.
   480 
   481 */
   482 
   483 #ifndef WIN32
   484 #ifdef _WIN32
   485 #define WIN32 1
   486 #endif  /* _WIN32 */
   487 #endif  /* WIN32 */
   488 #ifdef WIN32
   489 #include "SDL_windows.h"
   490 #define HAVE_MMAP 1
   491 #define HAVE_MORECORE 0
   492 #define LACKS_UNISTD_H
   493 #define LACKS_SYS_PARAM_H
   494 #define LACKS_SYS_MMAN_H
   495 #define LACKS_STRING_H
   496 #define LACKS_STRINGS_H
   497 #define LACKS_SYS_TYPES_H
   498 #define LACKS_ERRNO_H
   499 #define MALLOC_FAILURE_ACTION
   500 #define MMAP_CLEARS 0 /* WINCE and some others apparently don't clear */
   501 #endif  /* WIN32 */
   502 
   503 #if defined(DARWIN) || defined(_DARWIN)
   504 /* Mac OSX docs advise not to use sbrk; it seems better to use mmap */
   505 #ifndef HAVE_MORECORE
   506 #define HAVE_MORECORE 0
   507 #define HAVE_MMAP 1
   508 #endif  /* HAVE_MORECORE */
   509 #endif  /* DARWIN */
   510 
   511 #ifndef LACKS_SYS_TYPES_H
   512 #include <sys/types.h>  /* For size_t */
   513 #endif  /* LACKS_SYS_TYPES_H */
   514 
   515 /* The maximum possible size_t value has all bits set */
   516 #define MAX_SIZE_T           (~(size_t)0)
   517 
   518 #ifndef ONLY_MSPACES
   519 #define ONLY_MSPACES 0
   520 #endif  /* ONLY_MSPACES */
   521 #ifndef MSPACES
   522 #if ONLY_MSPACES
   523 #define MSPACES 1
   524 #else   /* ONLY_MSPACES */
   525 #define MSPACES 0
   526 #endif  /* ONLY_MSPACES */
   527 #endif  /* MSPACES */
   528 #ifndef MALLOC_ALIGNMENT
   529 #define MALLOC_ALIGNMENT ((size_t)8U)
   530 #endif  /* MALLOC_ALIGNMENT */
   531 #ifndef FOOTERS
   532 #define FOOTERS 0
   533 #endif  /* FOOTERS */
   534 #ifndef ABORT
   535 #define ABORT  abort()
   536 #endif  /* ABORT */
   537 #ifndef ABORT_ON_ASSERT_FAILURE
   538 #define ABORT_ON_ASSERT_FAILURE 1
   539 #endif  /* ABORT_ON_ASSERT_FAILURE */
   540 #ifndef PROCEED_ON_ERROR
   541 #define PROCEED_ON_ERROR 0
   542 #endif  /* PROCEED_ON_ERROR */
   543 #ifndef USE_LOCKS
   544 #define USE_LOCKS 0
   545 #endif  /* USE_LOCKS */
   546 #ifndef INSECURE
   547 #define INSECURE 0
   548 #endif  /* INSECURE */
   549 #ifndef HAVE_MMAP
   550 #define HAVE_MMAP 1
   551 #endif  /* HAVE_MMAP */
   552 #ifndef MMAP_CLEARS
   553 #define MMAP_CLEARS 1
   554 #endif  /* MMAP_CLEARS */
   555 #ifndef HAVE_MREMAP
   556 #ifdef linux
   557 #define HAVE_MREMAP 1
   558 #else   /* linux */
   559 #define HAVE_MREMAP 0
   560 #endif  /* linux */
   561 #endif  /* HAVE_MREMAP */
   562 #ifndef MALLOC_FAILURE_ACTION
   563 #define MALLOC_FAILURE_ACTION  errno = ENOMEM;
   564 #endif  /* MALLOC_FAILURE_ACTION */
   565 #ifndef HAVE_MORECORE
   566 #if ONLY_MSPACES
   567 #define HAVE_MORECORE 0
   568 #else   /* ONLY_MSPACES */
   569 #define HAVE_MORECORE 1
   570 #endif  /* ONLY_MSPACES */
   571 #endif  /* HAVE_MORECORE */
   572 #if !HAVE_MORECORE
   573 #define MORECORE_CONTIGUOUS 0
   574 #else   /* !HAVE_MORECORE */
   575 #ifndef MORECORE
   576 #define MORECORE sbrk
   577 #endif  /* MORECORE */
   578 #ifndef MORECORE_CONTIGUOUS
   579 #define MORECORE_CONTIGUOUS 1
   580 #endif  /* MORECORE_CONTIGUOUS */
   581 #endif  /* HAVE_MORECORE */
   582 #ifndef DEFAULT_GRANULARITY
   583 #if MORECORE_CONTIGUOUS
   584 #define DEFAULT_GRANULARITY (0)  /* 0 means to compute in init_mparams */
   585 #else   /* MORECORE_CONTIGUOUS */
   586 #define DEFAULT_GRANULARITY ((size_t)64U * (size_t)1024U)
   587 #endif  /* MORECORE_CONTIGUOUS */
   588 #endif  /* DEFAULT_GRANULARITY */
   589 #ifndef DEFAULT_TRIM_THRESHOLD
   590 #ifndef MORECORE_CANNOT_TRIM
   591 #define DEFAULT_TRIM_THRESHOLD ((size_t)2U * (size_t)1024U * (size_t)1024U)
   592 #else   /* MORECORE_CANNOT_TRIM */
   593 #define DEFAULT_TRIM_THRESHOLD MAX_SIZE_T
   594 #endif  /* MORECORE_CANNOT_TRIM */
   595 #endif  /* DEFAULT_TRIM_THRESHOLD */
   596 #ifndef DEFAULT_MMAP_THRESHOLD
   597 #if HAVE_MMAP
   598 #define DEFAULT_MMAP_THRESHOLD ((size_t)256U * (size_t)1024U)
   599 #else   /* HAVE_MMAP */
   600 #define DEFAULT_MMAP_THRESHOLD MAX_SIZE_T
   601 #endif  /* HAVE_MMAP */
   602 #endif  /* DEFAULT_MMAP_THRESHOLD */
   603 #ifndef USE_BUILTIN_FFS
   604 #define USE_BUILTIN_FFS 0
   605 #endif  /* USE_BUILTIN_FFS */
   606 #ifndef USE_DEV_RANDOM
   607 #define USE_DEV_RANDOM 0
   608 #endif  /* USE_DEV_RANDOM */
   609 #ifndef NO_MALLINFO
   610 #define NO_MALLINFO 0
   611 #endif  /* NO_MALLINFO */
   612 #ifndef MALLINFO_FIELD_TYPE
   613 #define MALLINFO_FIELD_TYPE size_t
   614 #endif  /* MALLINFO_FIELD_TYPE */
   615 
   616 /*
   617   mallopt tuning options.  SVID/XPG defines four standard parameter
   618   numbers for mallopt, normally defined in malloc.h.  None of these
   619   are used in this malloc, so setting them has no effect. But this
   620   malloc does support the following options.
   621 */
   622 
   623 #define M_TRIM_THRESHOLD     (-1)
   624 #define M_GRANULARITY        (-2)
   625 #define M_MMAP_THRESHOLD     (-3)
   626 
   627 /* ------------------------ Mallinfo declarations ------------------------ */
   628 
   629 #if !NO_MALLINFO
   630 /*
   631   This version of malloc supports the standard SVID/XPG mallinfo
   632   routine that returns a struct containing usage properties and
   633   statistics. It should work on any system that has a
   634   /usr/include/malloc.h defining struct mallinfo.  The main
   635   declaration needed is the mallinfo struct that is returned (by-copy)
   636   by mallinfo().  The malloinfo struct contains a bunch of fields that
   637   are not even meaningful in this version of malloc.  These fields are
   638   are instead filled by mallinfo() with other numbers that might be of
   639   interest.
   640 
   641   HAVE_USR_INCLUDE_MALLOC_H should be set if you have a
   642   /usr/include/malloc.h file that includes a declaration of struct
   643   mallinfo.  If so, it is included; else a compliant version is
   644   declared below.  These must be precisely the same for mallinfo() to
   645   work.  The original SVID version of this struct, defined on most
   646   systems with mallinfo, declares all fields as ints. But some others
   647   define as unsigned long. If your system defines the fields using a
   648   type of different width than listed here, you MUST #include your
   649   system version and #define HAVE_USR_INCLUDE_MALLOC_H.
   650 */
   651 
   652 /* #define HAVE_USR_INCLUDE_MALLOC_H */
   653 
   654 #ifdef HAVE_USR_INCLUDE_MALLOC_H
   655 #include "/usr/include/malloc.h"
   656 #else /* HAVE_USR_INCLUDE_MALLOC_H */
   657 
   658 struct mallinfo {
   659   MALLINFO_FIELD_TYPE arena;    /* non-mmapped space allocated from system */
   660   MALLINFO_FIELD_TYPE ordblks;  /* number of free chunks */
   661   MALLINFO_FIELD_TYPE smblks;   /* always 0 */
   662   MALLINFO_FIELD_TYPE hblks;    /* always 0 */
   663   MALLINFO_FIELD_TYPE hblkhd;   /* space in mmapped regions */
   664   MALLINFO_FIELD_TYPE usmblks;  /* maximum total allocated space */
   665   MALLINFO_FIELD_TYPE fsmblks;  /* always 0 */
   666   MALLINFO_FIELD_TYPE uordblks; /* total allocated space */
   667   MALLINFO_FIELD_TYPE fordblks; /* total free space */
   668   MALLINFO_FIELD_TYPE keepcost; /* releasable (via malloc_trim) space */
   669 };
   670 
   671 #endif /* HAVE_USR_INCLUDE_MALLOC_H */
   672 #endif /* NO_MALLINFO */
   673 
   674 #ifdef __cplusplus
   675 extern "C" {
   676 #endif /* __cplusplus */
   677 
   678 #if !ONLY_MSPACES
   679 
   680 /* ------------------- Declarations of public routines ------------------- */
   681 
   682 #ifndef USE_DL_PREFIX
   683 #define dlcalloc               calloc
   684 #define dlfree                 free
   685 #define dlmalloc               malloc
   686 #define dlmemalign             memalign
   687 #define dlrealloc              realloc
   688 #define dlvalloc               valloc
   689 #define dlpvalloc              pvalloc
   690 #define dlmallinfo             mallinfo
   691 #define dlmallopt              mallopt
   692 #define dlmalloc_trim          malloc_trim
   693 #define dlmalloc_stats         malloc_stats
   694 #define dlmalloc_usable_size   malloc_usable_size
   695 #define dlmalloc_footprint     malloc_footprint
   696 #define dlmalloc_max_footprint malloc_max_footprint
   697 #define dlindependent_calloc   independent_calloc
   698 #define dlindependent_comalloc independent_comalloc
   699 #endif /* USE_DL_PREFIX */
   700 
   701 
   702 /*
   703   malloc(size_t n)
   704   Returns a pointer to a newly allocated chunk of at least n bytes, or
   705   null if no space is available, in which case errno is set to ENOMEM
   706   on ANSI C systems.
   707 
   708   If n is zero, malloc returns a minimum-sized chunk. (The minimum
   709   size is 16 bytes on most 32bit systems, and 32 bytes on 64bit
   710   systems.)  Note that size_t is an unsigned type, so calls with
   711   arguments that would be negative if signed are interpreted as
   712   requests for huge amounts of space, which will often fail. The
   713   maximum supported value of n differs across systems, but is in all
   714   cases less than the maximum representable value of a size_t.
   715 */
   716 void* dlmalloc(size_t);
   717 
   718 /*
   719   free(void* p)
   720   Releases the chunk of memory pointed to by p, that had been previously
   721   allocated using malloc or a related routine such as realloc.
   722   It has no effect if p is null. If p was not malloced or already
   723   freed, free(p) will by default cause the current program to abort.
   724 */
   725 void  dlfree(void*);
   726 
   727 /*
   728   calloc(size_t n_elements, size_t element_size);
   729   Returns a pointer to n_elements * element_size bytes, with all locations
   730   set to zero.
   731 */
   732 void* dlcalloc(size_t, size_t);
   733 
   734 /*
   735   realloc(void* p, size_t n)
   736   Returns a pointer to a chunk of size n that contains the same data
   737   as does chunk p up to the minimum of (n, p's size) bytes, or null
   738   if no space is available.
   739 
   740   The returned pointer may or may not be the same as p. The algorithm
   741   prefers extending p in most cases when possible, otherwise it
   742   employs the equivalent of a malloc-copy-free sequence.
   743 
   744   If p is null, realloc is equivalent to malloc.
   745 
   746   If space is not available, realloc returns null, errno is set (if on
   747   ANSI) and p is NOT freed.
   748 
   749   if n is for fewer bytes than already held by p, the newly unused
   750   space is lopped off and freed if possible.  realloc with a size
   751   argument of zero (re)allocates a minimum-sized chunk.
   752 
   753   The old unix realloc convention of allowing the last-free'd chunk
   754   to be used as an argument to realloc is not supported.
   755 */
   756 
   757 void* dlrealloc(void*, size_t);
   758 
   759 /*
   760   memalign(size_t alignment, size_t n);
   761   Returns a pointer to a newly allocated chunk of n bytes, aligned
   762   in accord with the alignment argument.
   763 
   764   The alignment argument should be a power of two. If the argument is
   765   not a power of two, the nearest greater power is used.
   766   8-byte alignment is guaranteed by normal malloc calls, so don't
   767   bother calling memalign with an argument of 8 or less.
   768 
   769   Overreliance on memalign is a sure way to fragment space.
   770 */
   771 void* dlmemalign(size_t, size_t);
   772 
   773 /*
   774   valloc(size_t n);
   775   Equivalent to memalign(pagesize, n), where pagesize is the page
   776   size of the system. If the pagesize is unknown, 4096 is used.
   777 */
   778 void* dlvalloc(size_t);
   779 
   780 /*
   781   mallopt(int parameter_number, int parameter_value)
   782   Sets tunable parameters The format is to provide a
   783   (parameter-number, parameter-value) pair.  mallopt then sets the
   784   corresponding parameter to the argument value if it can (i.e., so
   785   long as the value is meaningful), and returns 1 if successful else
   786   0.  SVID/XPG/ANSI defines four standard param numbers for mallopt,
   787   normally defined in malloc.h.  None of these are use in this malloc,
   788   so setting them has no effect. But this malloc also supports other
   789   options in mallopt. See below for details.  Briefly, supported
   790   parameters are as follows (listed defaults are for "typical"
   791   configurations).
   792 
   793   Symbol            param #  default    allowed param values
   794   M_TRIM_THRESHOLD     -1   2*1024*1024   any   (MAX_SIZE_T disables)
   795   M_GRANULARITY        -2     page size   any power of 2 >= page size
   796   M_MMAP_THRESHOLD     -3      256*1024   any   (or 0 if no MMAP support)
   797 */
   798 int dlmallopt(int, int);
   799 
   800 /*
   801   malloc_footprint();
   802   Returns the number of bytes obtained from the system.  The total
   803   number of bytes allocated by malloc, realloc etc., is less than this
   804   value. Unlike mallinfo, this function returns only a precomputed
   805   result, so can be called frequently to monitor memory consumption.
   806   Even if locks are otherwise defined, this function does not use them,
   807   so results might not be up to date.
   808 */
   809 size_t dlmalloc_footprint(void);
   810 
   811 /*
   812   malloc_max_footprint();
   813   Returns the maximum number of bytes obtained from the system. This
   814   value will be greater than current footprint if deallocated space
   815   has been reclaimed by the system. The peak number of bytes allocated
   816   by malloc, realloc etc., is less than this value. Unlike mallinfo,
   817   this function returns only a precomputed result, so can be called
   818   frequently to monitor memory consumption.  Even if locks are
   819   otherwise defined, this function does not use them, so results might
   820   not be up to date.
   821 */
   822 size_t dlmalloc_max_footprint(void);
   823 
   824 #if !NO_MALLINFO
   825 /*
   826   mallinfo()
   827   Returns (by copy) a struct containing various summary statistics:
   828 
   829   arena:     current total non-mmapped bytes allocated from system
   830   ordblks:   the number of free chunks
   831   smblks:    always zero.
   832   hblks:     current number of mmapped regions
   833   hblkhd:    total bytes held in mmapped regions
   834   usmblks:   the maximum total allocated space. This will be greater
   835                 than current total if trimming has occurred.
   836   fsmblks:   always zero
   837   uordblks:  current total allocated space (normal or mmapped)
   838   fordblks:  total free space
   839   keepcost:  the maximum number of bytes that could ideally be released
   840                back to system via malloc_trim. ("ideally" means that
   841                it ignores page restrictions etc.)
   842 
   843   Because these fields are ints, but internal bookkeeping may
   844   be kept as longs, the reported values may wrap around zero and
   845   thus be inaccurate.
   846 */
   847 struct mallinfo dlmallinfo(void);
   848 #endif /* NO_MALLINFO */
   849 
   850 /*
   851   independent_calloc(size_t n_elements, size_t element_size, void* chunks[]);
   852 
   853   independent_calloc is similar to calloc, but instead of returning a
   854   single cleared space, it returns an array of pointers to n_elements
   855   independent elements that can hold contents of size elem_size, each
   856   of which starts out cleared, and can be independently freed,
   857   realloc'ed etc. The elements are guaranteed to be adjacently
   858   allocated (this is not guaranteed to occur with multiple callocs or
   859   mallocs), which may also improve cache locality in some
   860   applications.
   861 
   862   The "chunks" argument is optional (i.e., may be null, which is
   863   probably the most typical usage). If it is null, the returned array
   864   is itself dynamically allocated and should also be freed when it is
   865   no longer needed. Otherwise, the chunks array must be of at least
   866   n_elements in length. It is filled in with the pointers to the
   867   chunks.
   868 
   869   In either case, independent_calloc returns this pointer array, or
   870   null if the allocation failed.  If n_elements is zero and "chunks"
   871   is null, it returns a chunk representing an array with zero elements
   872   (which should be freed if not wanted).
   873 
   874   Each element must be individually freed when it is no longer
   875   needed. If you'd like to instead be able to free all at once, you
   876   should instead use regular calloc and assign pointers into this
   877   space to represent elements.  (In this case though, you cannot
   878   independently free elements.)
   879 
   880   independent_calloc simplifies and speeds up implementations of many
   881   kinds of pools.  It may also be useful when constructing large data
   882   structures that initially have a fixed number of fixed-sized nodes,
   883   but the number is not known at compile time, and some of the nodes
   884   may later need to be freed. For example:
   885 
   886   struct Node { int item; struct Node* next; };
   887 
   888   struct Node* build_list() {
   889     struct Node** pool;
   890     int n = read_number_of_nodes_needed();
   891     if (n <= 0) return 0;
   892     pool = (struct Node**)(independent_calloc(n, sizeof(struct Node), 0);
   893     if (pool == 0) die();
   894     // organize into a linked list...
   895     struct Node* first = pool[0];
   896     for (i = 0; i < n-1; ++i)
   897       pool[i]->next = pool[i+1];
   898     free(pool);     // Can now free the array (or not, if it is needed later)
   899     return first;
   900   }
   901 */
   902 void** dlindependent_calloc(size_t, size_t, void**);
   903 
   904 /*
   905   independent_comalloc(size_t n_elements, size_t sizes[], void* chunks[]);
   906 
   907   independent_comalloc allocates, all at once, a set of n_elements
   908   chunks with sizes indicated in the "sizes" array.    It returns
   909   an array of pointers to these elements, each of which can be
   910   independently freed, realloc'ed etc. The elements are guaranteed to
   911   be adjacently allocated (this is not guaranteed to occur with
   912   multiple callocs or mallocs), which may also improve cache locality
   913   in some applications.
   914 
   915   The "chunks" argument is optional (i.e., may be null). If it is null
   916   the returned array is itself dynamically allocated and should also
   917   be freed when it is no longer needed. Otherwise, the chunks array
   918   must be of at least n_elements in length. It is filled in with the
   919   pointers to the chunks.
   920 
   921   In either case, independent_comalloc returns this pointer array, or
   922   null if the allocation failed.  If n_elements is zero and chunks is
   923   null, it returns a chunk representing an array with zero elements
   924   (which should be freed if not wanted).
   925 
   926   Each element must be individually freed when it is no longer
   927   needed. If you'd like to instead be able to free all at once, you
   928   should instead use a single regular malloc, and assign pointers at
   929   particular offsets in the aggregate space. (In this case though, you
   930   cannot independently free elements.)
   931 
   932   independent_comallac differs from independent_calloc in that each
   933   element may have a different size, and also that it does not
   934   automatically clear elements.
   935 
   936   independent_comalloc can be used to speed up allocation in cases
   937   where several structs or objects must always be allocated at the
   938   same time.  For example:
   939 
   940   struct Head { ... }
   941   struct Foot { ... }
   942 
   943   void send_message(char* msg) {
   944     int msglen = strlen(msg);
   945     size_t sizes[3] = { sizeof(struct Head), msglen, sizeof(struct Foot) };
   946     void* chunks[3];
   947     if (independent_comalloc(3, sizes, chunks) == 0)
   948       die();
   949     struct Head* head = (struct Head*)(chunks[0]);
   950     char*        body = (char*)(chunks[1]);
   951     struct Foot* foot = (struct Foot*)(chunks[2]);
   952     // ...
   953   }
   954 
   955   In general though, independent_comalloc is worth using only for
   956   larger values of n_elements. For small values, you probably won't
   957   detect enough difference from series of malloc calls to bother.
   958 
   959   Overuse of independent_comalloc can increase overall memory usage,
   960   since it cannot reuse existing noncontiguous small chunks that
   961   might be available for some of the elements.
   962 */
   963 void** dlindependent_comalloc(size_t, size_t*, void**);
   964 
   965 
   966 /*
   967   pvalloc(size_t n);
   968   Equivalent to valloc(minimum-page-that-holds(n)), that is,
   969   round up n to nearest pagesize.
   970  */
   971 void*  dlpvalloc(size_t);
   972 
   973 /*
   974   malloc_trim(size_t pad);
   975 
   976   If possible, gives memory back to the system (via negative arguments
   977   to sbrk) if there is unused memory at the `high' end of the malloc
   978   pool or in unused MMAP segments. You can call this after freeing
   979   large blocks of memory to potentially reduce the system-level memory
   980   requirements of a program. However, it cannot guarantee to reduce
   981   memory. Under some allocation patterns, some large free blocks of
   982   memory will be locked between two used chunks, so they cannot be
   983   given back to the system.
   984 
   985   The `pad' argument to malloc_trim represents the amount of free
   986   trailing space to leave untrimmed. If this argument is zero, only
   987   the minimum amount of memory to maintain internal data structures
   988   will be left. Non-zero arguments can be supplied to maintain enough
   989   trailing space to service future expected allocations without having
   990   to re-obtain memory from the system.
   991 
   992   Malloc_trim returns 1 if it actually released any memory, else 0.
   993 */
   994 int  dlmalloc_trim(size_t);
   995 
   996 /*
   997   malloc_usable_size(void* p);
   998 
   999   Returns the number of bytes you can actually use in
  1000   an allocated chunk, which may be more than you requested (although
  1001   often not) due to alignment and minimum size constraints.
  1002   You can use this many bytes without worrying about
  1003   overwriting other allocated objects. This is not a particularly great
  1004   programming practice. malloc_usable_size can be more useful in
  1005   debugging and assertions, for example:
  1006 
  1007   p = malloc(n);
  1008   assert(malloc_usable_size(p) >= 256);
  1009 */
  1010 size_t dlmalloc_usable_size(void*);
  1011 
  1012 /*
  1013   malloc_stats();
  1014   Prints on stderr the amount of space obtained from the system (both
  1015   via sbrk and mmap), the maximum amount (which may be more than
  1016   current if malloc_trim and/or munmap got called), and the current
  1017   number of bytes allocated via malloc (or realloc, etc) but not yet
  1018   freed. Note that this is the number of bytes allocated, not the
  1019   number requested. It will be larger than the number requested
  1020   because of alignment and bookkeeping overhead. Because it includes
  1021   alignment wastage as being in use, this figure may be greater than
  1022   zero even when no user-level chunks are allocated.
  1023 
  1024   The reported current and maximum system memory can be inaccurate if
  1025   a program makes other calls to system memory allocation functions
  1026   (normally sbrk) outside of malloc.
  1027 
  1028   malloc_stats prints only the most commonly interesting statistics.
  1029   More information can be obtained by calling mallinfo.
  1030 */
  1031 void  dlmalloc_stats(void);
  1032 
  1033 #endif /* ONLY_MSPACES */
  1034 
  1035 #if MSPACES
  1036 
  1037 /*
  1038   mspace is an opaque type representing an independent
  1039   region of space that supports mspace_malloc, etc.
  1040 */
  1041 typedef void* mspace;
  1042 
  1043 /*
  1044   create_mspace creates and returns a new independent space with the
  1045   given initial capacity, or, if 0, the default granularity size.  It
  1046   returns null if there is no system memory available to create the
  1047   space.  If argument locked is non-zero, the space uses a separate
  1048   lock to control access. The capacity of the space will grow
  1049   dynamically as needed to service mspace_malloc requests.  You can
  1050   control the sizes of incremental increases of this space by
  1051   compiling with a different DEFAULT_GRANULARITY or dynamically
  1052   setting with mallopt(M_GRANULARITY, value).
  1053 */
  1054 mspace create_mspace(size_t capacity, int locked);
  1055 
  1056 /*
  1057   destroy_mspace destroys the given space, and attempts to return all
  1058   of its memory back to the system, returning the total number of
  1059   bytes freed. After destruction, the results of access to all memory
  1060   used by the space become undefined.
  1061 */
  1062 size_t destroy_mspace(mspace msp);
  1063 
  1064 /*
  1065   create_mspace_with_base uses the memory supplied as the initial base
  1066   of a new mspace. Part (less than 128*sizeof(size_t) bytes) of this
  1067   space is used for bookkeeping, so the capacity must be at least this
  1068   large. (Otherwise 0 is returned.) When this initial space is
  1069   exhausted, additional memory will be obtained from the system.
  1070   Destroying this space will deallocate all additionally allocated
  1071   space (if possible) but not the initial base.
  1072 */
  1073 mspace create_mspace_with_base(void* base, size_t capacity, int locked);
  1074 
  1075 /*
  1076   mspace_malloc behaves as malloc, but operates within
  1077   the given space.
  1078 */
  1079 void* mspace_malloc(mspace msp, size_t bytes);
  1080 
  1081 /*
  1082   mspace_free behaves as free, but operates within
  1083   the given space.
  1084 
  1085   If compiled with FOOTERS==1, mspace_free is not actually needed.
  1086   free may be called instead of mspace_free because freed chunks from
  1087   any space are handled by their originating spaces.
  1088 */
  1089 void mspace_free(mspace msp, void* mem);
  1090 
  1091 /*
  1092   mspace_realloc behaves as realloc, but operates within
  1093   the given space.
  1094 
  1095   If compiled with FOOTERS==1, mspace_realloc is not actually
  1096   needed.  realloc may be called instead of mspace_realloc because
  1097   realloced chunks from any space are handled by their originating
  1098   spaces.
  1099 */
  1100 void* mspace_realloc(mspace msp, void* mem, size_t newsize);
  1101 
  1102 /*
  1103   mspace_calloc behaves as calloc, but operates within
  1104   the given space.
  1105 */
  1106 void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size);
  1107 
  1108 /*
  1109   mspace_memalign behaves as memalign, but operates within
  1110   the given space.
  1111 */
  1112 void* mspace_memalign(mspace msp, size_t alignment, size_t bytes);
  1113 
  1114 /*
  1115   mspace_independent_calloc behaves as independent_calloc, but
  1116   operates within the given space.
  1117 */
  1118 void** mspace_independent_calloc(mspace msp, size_t n_elements,
  1119                                  size_t elem_size, void* chunks[]);
  1120 
  1121 /*
  1122   mspace_independent_comalloc behaves as independent_comalloc, but
  1123   operates within the given space.
  1124 */
  1125 void** mspace_independent_comalloc(mspace msp, size_t n_elements,
  1126                                    size_t sizes[], void* chunks[]);
  1127 
  1128 /*
  1129   mspace_footprint() returns the number of bytes obtained from the
  1130   system for this space.
  1131 */
  1132 size_t mspace_footprint(mspace msp);
  1133 
  1134 /*
  1135   mspace_max_footprint() returns the peak number of bytes obtained from the
  1136   system for this space.
  1137 */
  1138 size_t mspace_max_footprint(mspace msp);
  1139 
  1140 
  1141 #if !NO_MALLINFO
  1142 /*
  1143   mspace_mallinfo behaves as mallinfo, but reports properties of
  1144   the given space.
  1145 */
  1146 struct mallinfo mspace_mallinfo(mspace msp);
  1147 #endif /* NO_MALLINFO */
  1148 
  1149 /*
  1150   mspace_malloc_stats behaves as malloc_stats, but reports
  1151   properties of the given space.
  1152 */
  1153 void mspace_malloc_stats(mspace msp);
  1154 
  1155 /*
  1156   mspace_trim behaves as malloc_trim, but
  1157   operates within the given space.
  1158 */
  1159 int mspace_trim(mspace msp, size_t pad);
  1160 
  1161 /*
  1162   An alias for mallopt.
  1163 */
  1164 int mspace_mallopt(int, int);
  1165 
  1166 #endif /* MSPACES */
  1167 
  1168 #ifdef __cplusplus
  1169 };  /* end of extern "C" */
  1170 #endif /* __cplusplus */
  1171 
  1172 /*
  1173   ========================================================================
  1174   To make a fully customizable malloc.h header file, cut everything
  1175   above this line, put into file malloc.h, edit to suit, and #include it
  1176   on the next line, as well as in programs that use this malloc.
  1177   ========================================================================
  1178 */
  1179 
  1180 /* #include "malloc.h" */
  1181 
  1182 /*------------------------------ internal #includes ---------------------- */
  1183 
  1184 #ifdef _MSC_VER
  1185 #pragma warning( disable : 4146 ) /* no "unsigned" warnings */
  1186 #endif /* _MSC_VER */
  1187 
  1188 #ifndef LACKS_STDIO_H
  1189 #include <stdio.h>       /* for printing in malloc_stats */
  1190 #endif
  1191 
  1192 #ifndef LACKS_ERRNO_H
  1193 #include <errno.h>       /* for MALLOC_FAILURE_ACTION */
  1194 #endif /* LACKS_ERRNO_H */
  1195 #if FOOTERS
  1196 #include <time.h>        /* for magic initialization */
  1197 #endif /* FOOTERS */
  1198 #ifndef LACKS_STDLIB_H
  1199 #include <stdlib.h>      /* for abort() */
  1200 #endif /* LACKS_STDLIB_H */
  1201 #ifdef DEBUG
  1202 #if ABORT_ON_ASSERT_FAILURE
  1203 #define assert(x) if(!(x)) ABORT
  1204 #else /* ABORT_ON_ASSERT_FAILURE */
  1205 #include <assert.h>
  1206 #endif /* ABORT_ON_ASSERT_FAILURE */
  1207 #else  /* DEBUG */
  1208 #define assert(x)
  1209 #endif /* DEBUG */
  1210 #ifndef LACKS_STRING_H
  1211 #include <string.h>      /* for memset etc */
  1212 #endif  /* LACKS_STRING_H */
  1213 #if USE_BUILTIN_FFS
  1214 #ifndef LACKS_STRINGS_H
  1215 #include <strings.h>     /* for ffs */
  1216 #endif /* LACKS_STRINGS_H */
  1217 #endif /* USE_BUILTIN_FFS */
  1218 #if HAVE_MMAP
  1219 #ifndef LACKS_SYS_MMAN_H
  1220 #include <sys/mman.h>    /* for mmap */
  1221 #endif /* LACKS_SYS_MMAN_H */
  1222 #ifndef LACKS_FCNTL_H
  1223 #include <fcntl.h>
  1224 #endif /* LACKS_FCNTL_H */
  1225 #endif /* HAVE_MMAP */
  1226 #if HAVE_MORECORE
  1227 #ifndef LACKS_UNISTD_H
  1228 #include <unistd.h>     /* for sbrk */
  1229 #else /* LACKS_UNISTD_H */
  1230 #if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)
  1231 extern void*     sbrk(ptrdiff_t);
  1232 #endif /* FreeBSD etc */
  1233 #endif /* LACKS_UNISTD_H */
  1234 #endif /* HAVE_MMAP */
  1235 
  1236 #ifndef WIN32
  1237 #ifndef malloc_getpagesize
  1238 #  ifdef _SC_PAGESIZE         /* some SVR4 systems omit an underscore */
  1239 #    ifndef _SC_PAGE_SIZE
  1240 #      define _SC_PAGE_SIZE _SC_PAGESIZE
  1241 #    endif
  1242 #  endif
  1243 #  ifdef _SC_PAGE_SIZE
  1244 #    define malloc_getpagesize sysconf(_SC_PAGE_SIZE)
  1245 #  else
  1246 #    if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE)
  1247        extern size_t getpagesize();
  1248 #      define malloc_getpagesize getpagesize()
  1249 #    else
  1250 #      ifdef WIN32 /* use supplied emulation of getpagesize */
  1251 #        define malloc_getpagesize getpagesize()
  1252 #      else
  1253 #        ifndef LACKS_SYS_PARAM_H
  1254 #          include <sys/param.h>
  1255 #        endif
  1256 #        ifdef EXEC_PAGESIZE
  1257 #          define malloc_getpagesize EXEC_PAGESIZE
  1258 #        else
  1259 #          ifdef NBPG
  1260 #            ifndef CLSIZE
  1261 #              define malloc_getpagesize NBPG
  1262 #            else
  1263 #              define malloc_getpagesize (NBPG * CLSIZE)
  1264 #            endif
  1265 #          else
  1266 #            ifdef NBPC
  1267 #              define malloc_getpagesize NBPC
  1268 #            else
  1269 #              ifdef PAGESIZE
  1270 #                define malloc_getpagesize PAGESIZE
  1271 #              else /* just guess */
  1272 #                define malloc_getpagesize ((size_t)4096U)
  1273 #              endif
  1274 #            endif
  1275 #          endif
  1276 #        endif
  1277 #      endif
  1278 #    endif
  1279 #  endif
  1280 #endif
  1281 #endif
  1282 
  1283 /* ------------------- size_t and alignment properties -------------------- */
  1284 
  1285 /* The byte and bit size of a size_t */
  1286 #define SIZE_T_SIZE         (sizeof(size_t))
  1287 #define SIZE_T_BITSIZE      (sizeof(size_t) << 3)
  1288 
  1289 /* Some constants coerced to size_t */
  1290 /* Annoying but necessary to avoid errors on some plaftorms */
  1291 #define SIZE_T_ZERO         ((size_t)0)
  1292 #define SIZE_T_ONE          ((size_t)1)
  1293 #define SIZE_T_TWO          ((size_t)2)
  1294 #define TWO_SIZE_T_SIZES    (SIZE_T_SIZE<<1)
  1295 #define FOUR_SIZE_T_SIZES   (SIZE_T_SIZE<<2)
  1296 #define SIX_SIZE_T_SIZES    (FOUR_SIZE_T_SIZES+TWO_SIZE_T_SIZES)
  1297 #define HALF_MAX_SIZE_T     (MAX_SIZE_T / 2U)
  1298 
  1299 /* The bit mask value corresponding to MALLOC_ALIGNMENT */
  1300 #define CHUNK_ALIGN_MASK    (MALLOC_ALIGNMENT - SIZE_T_ONE)
  1301 
  1302 /* True if address a has acceptable alignment */
  1303 #define is_aligned(A)       (((size_t)((A)) & (CHUNK_ALIGN_MASK)) == 0)
  1304 
  1305 /* the number of bytes to offset an address to align it */
  1306 #define align_offset(A)\
  1307  ((((size_t)(A) & CHUNK_ALIGN_MASK) == 0)? 0 :\
  1308   ((MALLOC_ALIGNMENT - ((size_t)(A) & CHUNK_ALIGN_MASK)) & CHUNK_ALIGN_MASK))
  1309 
  1310 /* -------------------------- MMAP preliminaries ------------------------- */
  1311 
  1312 /*
  1313    If HAVE_MORECORE or HAVE_MMAP are false, we just define calls and
  1314    checks to fail so compiler optimizer can delete code rather than
  1315    using so many "#if"s.
  1316 */
  1317 
  1318 
  1319 /* MORECORE and MMAP must return MFAIL on failure */
  1320 #define MFAIL                ((void*)(MAX_SIZE_T))
  1321 #define CMFAIL               ((char*)(MFAIL)) /* defined for convenience */
  1322 
  1323 #if !HAVE_MMAP
  1324 #define IS_MMAPPED_BIT       (SIZE_T_ZERO)
  1325 #define USE_MMAP_BIT         (SIZE_T_ZERO)
  1326 #define CALL_MMAP(s)         MFAIL
  1327 #define CALL_MUNMAP(a, s)    (-1)
  1328 #define DIRECT_MMAP(s)       MFAIL
  1329 
  1330 #else /* HAVE_MMAP */
  1331 #define IS_MMAPPED_BIT       (SIZE_T_ONE)
  1332 #define USE_MMAP_BIT         (SIZE_T_ONE)
  1333 
  1334 #ifndef WIN32
  1335 #define CALL_MUNMAP(a, s)    munmap((a), (s))
  1336 #define MMAP_PROT            (PROT_READ|PROT_WRITE)
  1337 #if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
  1338 #define MAP_ANONYMOUS        MAP_ANON
  1339 #endif /* MAP_ANON */
  1340 #ifdef MAP_ANONYMOUS
  1341 #define MMAP_FLAGS           (MAP_PRIVATE|MAP_ANONYMOUS)
  1342 #define CALL_MMAP(s)         mmap(0, (s), MMAP_PROT, MMAP_FLAGS, -1, 0)
  1343 #else /* MAP_ANONYMOUS */
  1344 /*
  1345    Nearly all versions of mmap support MAP_ANONYMOUS, so the following
  1346    is unlikely to be needed, but is supplied just in case.
  1347 */
  1348 #define MMAP_FLAGS           (MAP_PRIVATE)
  1349 static int dev_zero_fd = -1; /* Cached file descriptor for /dev/zero. */
  1350 #define CALL_MMAP(s) ((dev_zero_fd < 0) ? \
  1351            (dev_zero_fd = open("/dev/zero", O_RDWR), \
  1352             mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0)) : \
  1353             mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0))
  1354 #endif /* MAP_ANONYMOUS */
  1355 
  1356 #define DIRECT_MMAP(s)       CALL_MMAP(s)
  1357 #else /* WIN32 */
  1358 
  1359 /* Win32 MMAP via VirtualAlloc */
  1360 static void* win32mmap(size_t size) {
  1361   void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT, PAGE_READWRITE);
  1362   return (ptr != 0)? ptr: MFAIL;
  1363 }
  1364 
  1365 /* For direct MMAP, use MEM_TOP_DOWN to minimize interference */
  1366 static void* win32direct_mmap(size_t size) {
  1367   void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT|MEM_TOP_DOWN,
  1368                            PAGE_READWRITE);
  1369   return (ptr != 0)? ptr: MFAIL;
  1370 }
  1371 
  1372 /* This function supports releasing coalesed segments */
  1373 static int win32munmap(void* ptr, size_t size) {
  1374   MEMORY_BASIC_INFORMATION minfo;
  1375   char* cptr = ptr;
  1376   while (size) {
  1377     if (VirtualQuery(cptr, &minfo, sizeof(minfo)) == 0)
  1378       return -1;
  1379     if (minfo.BaseAddress != cptr || minfo.AllocationBase != cptr ||
  1380         minfo.State != MEM_COMMIT || minfo.RegionSize > size)
  1381       return -1;
  1382     if (VirtualFree(cptr, 0, MEM_RELEASE) == 0)
  1383       return -1;
  1384     cptr += minfo.RegionSize;
  1385     size -= minfo.RegionSize;
  1386   }
  1387   return 0;
  1388 }
  1389 
  1390 #define CALL_MMAP(s)         win32mmap(s)
  1391 #define CALL_MUNMAP(a, s)    win32munmap((a), (s))
  1392 #define DIRECT_MMAP(s)       win32direct_mmap(s)
  1393 #endif /* WIN32 */
  1394 #endif /* HAVE_MMAP */
  1395 
  1396 #if HAVE_MMAP && HAVE_MREMAP
  1397 #define CALL_MREMAP(addr, osz, nsz, mv) mremap((addr), (osz), (nsz), (mv))
  1398 #else  /* HAVE_MMAP && HAVE_MREMAP */
  1399 #define CALL_MREMAP(addr, osz, nsz, mv) MFAIL
  1400 #endif /* HAVE_MMAP && HAVE_MREMAP */
  1401 
  1402 #if HAVE_MORECORE
  1403 #define CALL_MORECORE(S)     MORECORE(S)
  1404 #else  /* HAVE_MORECORE */
  1405 #define CALL_MORECORE(S)     MFAIL
  1406 #endif /* HAVE_MORECORE */
  1407 
  1408 /* mstate bit set if continguous morecore disabled or failed */
  1409 #define USE_NONCONTIGUOUS_BIT (4U)
  1410 
  1411 /* segment bit set in create_mspace_with_base */
  1412 #define EXTERN_BIT            (8U)
  1413 
  1414 
  1415 /* --------------------------- Lock preliminaries ------------------------ */
  1416 
  1417 #if USE_LOCKS
  1418 
  1419 /*
  1420   When locks are defined, there are up to two global locks:
  1421 
  1422   * If HAVE_MORECORE, morecore_mutex protects sequences of calls to
  1423     MORECORE.  In many cases sys_alloc requires two calls, that should
  1424     not be interleaved with calls by other threads.  This does not
  1425     protect against direct calls to MORECORE by other threads not
  1426     using this lock, so there is still code to cope the best we can on
  1427     interference.
  1428 
  1429   * magic_init_mutex ensures that mparams.magic and other
  1430     unique mparams values are initialized only once.
  1431 */
  1432 
  1433 #ifndef WIN32
  1434 /* By default use posix locks */
  1435 #include <pthread.h>
  1436 #define MLOCK_T pthread_mutex_t
  1437 #define INITIAL_LOCK(l)      pthread_mutex_init(l, NULL)
  1438 #define ACQUIRE_LOCK(l)      pthread_mutex_lock(l)
  1439 #define RELEASE_LOCK(l)      pthread_mutex_unlock(l)
  1440 
  1441 #if HAVE_MORECORE
  1442 static MLOCK_T morecore_mutex = PTHREAD_MUTEX_INITIALIZER;
  1443 #endif /* HAVE_MORECORE */
  1444 
  1445 static MLOCK_T magic_init_mutex = PTHREAD_MUTEX_INITIALIZER;
  1446 
  1447 #else /* WIN32 */
  1448 /*
  1449    Because lock-protected regions have bounded times, and there
  1450    are no recursive lock calls, we can use simple spinlocks.
  1451 */
  1452 
  1453 #define MLOCK_T long
  1454 static int win32_acquire_lock (MLOCK_T *sl) {
  1455   for (;;) {
  1456 #ifdef InterlockedCompareExchangePointer
  1457     if (!InterlockedCompareExchange(sl, 1, 0))
  1458       return 0;
  1459 #else  /* Use older void* version */
  1460     if (!InterlockedCompareExchange((void**)sl, (void*)1, (void*)0))
  1461       return 0;
  1462 #endif /* InterlockedCompareExchangePointer */
  1463     Sleep (0);
  1464   }
  1465 }
  1466 
  1467 static void win32_release_lock (MLOCK_T *sl) {
  1468   InterlockedExchange (sl, 0);
  1469 }
  1470 
  1471 #define INITIAL_LOCK(l)      *(l)=0
  1472 #define ACQUIRE_LOCK(l)      win32_acquire_lock(l)
  1473 #define RELEASE_LOCK(l)      win32_release_lock(l)
  1474 #if HAVE_MORECORE
  1475 static MLOCK_T morecore_mutex;
  1476 #endif /* HAVE_MORECORE */
  1477 static MLOCK_T magic_init_mutex;
  1478 #endif /* WIN32 */
  1479 
  1480 #define USE_LOCK_BIT               (2U)
  1481 #else  /* USE_LOCKS */
  1482 #define USE_LOCK_BIT               (0U)
  1483 #define INITIAL_LOCK(l)
  1484 #endif /* USE_LOCKS */
  1485 
  1486 #if USE_LOCKS && HAVE_MORECORE
  1487 #define ACQUIRE_MORECORE_LOCK()    ACQUIRE_LOCK(&morecore_mutex);
  1488 #define RELEASE_MORECORE_LOCK()    RELEASE_LOCK(&morecore_mutex);
  1489 #else /* USE_LOCKS && HAVE_MORECORE */
  1490 #define ACQUIRE_MORECORE_LOCK()
  1491 #define RELEASE_MORECORE_LOCK()
  1492 #endif /* USE_LOCKS && HAVE_MORECORE */
  1493 
  1494 #if USE_LOCKS
  1495 #define ACQUIRE_MAGIC_INIT_LOCK()  ACQUIRE_LOCK(&magic_init_mutex);
  1496 #define RELEASE_MAGIC_INIT_LOCK()  RELEASE_LOCK(&magic_init_mutex);
  1497 #else  /* USE_LOCKS */
  1498 #define ACQUIRE_MAGIC_INIT_LOCK()
  1499 #define RELEASE_MAGIC_INIT_LOCK()
  1500 #endif /* USE_LOCKS */
  1501 
  1502 
  1503 /* -----------------------  Chunk representations ------------------------ */
  1504 
  1505 /*
  1506   (The following includes lightly edited explanations by Colin Plumb.)
  1507 
  1508   The malloc_chunk declaration below is misleading (but accurate and
  1509   necessary).  It declares a "view" into memory allowing access to
  1510   necessary fields at known offsets from a given base.
  1511 
  1512   Chunks of memory are maintained using a `boundary tag' method as
  1513   originally described by Knuth.  (See the paper by Paul Wilson
  1514   ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a survey of such
  1515   techniques.)  Sizes of free chunks are stored both in the front of
  1516   each chunk and at the end.  This makes consolidating fragmented
  1517   chunks into bigger chunks fast.  The head fields also hold bits
  1518   representing whether chunks are free or in use.
  1519 
  1520   Here are some pictures to make it clearer.  They are "exploded" to
  1521   show that the state of a chunk can be thought of as extending from
  1522   the high 31 bits of the head field of its header through the
  1523   prev_foot and PINUSE_BIT bit of the following chunk header.
  1524 
  1525   A chunk that's in use looks like:
  1526 
  1527    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1528            | Size of previous chunk (if P = 1)                             |
  1529            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1530          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
  1531          | Size of this chunk                                         1| +-+
  1532    mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1533          |                                                               |
  1534          +-                                                             -+
  1535          |                                                               |
  1536          +-                                                             -+
  1537          |                                                               :
  1538          +-      size - sizeof(size_t) available payload bytes          -+
  1539          :                                                               |
  1540  chunk-> +-                                                             -+
  1541          |                                                               |
  1542          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1543        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1|
  1544        | Size of next chunk (may or may not be in use)               | +-+
  1545  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1546 
  1547     And if it's free, it looks like this:
  1548 
  1549    chunk-> +-                                                             -+
  1550            | User payload (must be in use, or we would have merged!)       |
  1551            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1552          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
  1553          | Size of this chunk                                         0| +-+
  1554    mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1555          | Next pointer                                                  |
  1556          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1557          | Prev pointer                                                  |
  1558          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1559          |                                                               :
  1560          +-      size - sizeof(struct chunk) unused bytes               -+
  1561          :                                                               |
  1562  chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1563          | Size of this chunk                                            |
  1564          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1565        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0|
  1566        | Size of next chunk (must be in use, or we would have merged)| +-+
  1567  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1568        |                                                               :
  1569        +- User payload                                                -+
  1570        :                                                               |
  1571        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1572                                                                      |0|
  1573                                                                      +-+
  1574   Note that since we always merge adjacent free chunks, the chunks
  1575   adjacent to a free chunk must be in use.
  1576 
  1577   Given a pointer to a chunk (which can be derived trivially from the
  1578   payload pointer) we can, in O(1) time, find out whether the adjacent
  1579   chunks are free, and if so, unlink them from the lists that they
  1580   are on and merge them with the current chunk.
  1581 
  1582   Chunks always begin on even word boundaries, so the mem portion
  1583   (which is returned to the user) is also on an even word boundary, and
  1584   thus at least double-word aligned.
  1585 
  1586   The P (PINUSE_BIT) bit, stored in the unused low-order bit of the
  1587   chunk size (which is always a multiple of two words), is an in-use
  1588   bit for the *previous* chunk.  If that bit is *clear*, then the
  1589   word before the current chunk size contains the previous chunk
  1590   size, and can be used to find the front of the previous chunk.
  1591   The very first chunk allocated always has this bit set, preventing
  1592   access to non-existent (or non-owned) memory. If pinuse is set for
  1593   any given chunk, then you CANNOT determine the size of the
  1594   previous chunk, and might even get a memory addressing fault when
  1595   trying to do so.
  1596 
  1597   The C (CINUSE_BIT) bit, stored in the unused second-lowest bit of
  1598   the chunk size redundantly records whether the current chunk is
  1599   inuse. This redundancy enables usage checks within free and realloc,
  1600   and reduces indirection when freeing and consolidating chunks.
  1601 
  1602   Each freshly allocated chunk must have both cinuse and pinuse set.
  1603   That is, each allocated chunk borders either a previously allocated
  1604   and still in-use chunk, or the base of its memory arena. This is
  1605   ensured by making all allocations from the the `lowest' part of any
  1606   found chunk.  Further, no free chunk physically borders another one,
  1607   so each free chunk is known to be preceded and followed by either
  1608   inuse chunks or the ends of memory.
  1609 
  1610   Note that the `foot' of the current chunk is actually represented
  1611   as the prev_foot of the NEXT chunk. This makes it easier to
  1612   deal with alignments etc but can be very confusing when trying
  1613   to extend or adapt this code.
  1614 
  1615   The exceptions to all this are
  1616 
  1617      1. The special chunk `top' is the top-most available chunk (i.e.,
  1618         the one bordering the end of available memory). It is treated
  1619         specially.  Top is never included in any bin, is used only if
  1620         no other chunk is available, and is released back to the
  1621         system if it is very large (see M_TRIM_THRESHOLD).  In effect,
  1622         the top chunk is treated as larger (and thus less well
  1623         fitting) than any other available chunk.  The top chunk
  1624         doesn't update its trailing size field since there is no next
  1625         contiguous chunk that would have to index off it. However,
  1626         space is still allocated for it (TOP_FOOT_SIZE) to enable
  1627         separation or merging when space is extended.
  1628 
  1629      3. Chunks allocated via mmap, which have the lowest-order bit
  1630         (IS_MMAPPED_BIT) set in their prev_foot fields, and do not set
  1631         PINUSE_BIT in their head fields.  Because they are allocated
  1632         one-by-one, each must carry its own prev_foot field, which is
  1633         also used to hold the offset this chunk has within its mmapped
  1634         region, which is needed to preserve alignment. Each mmapped
  1635         chunk is trailed by the first two fields of a fake next-chunk
  1636         for sake of usage checks.
  1637 
  1638 */
  1639 
  1640 struct malloc_chunk {
  1641   size_t               prev_foot;  /* Size of previous chunk (if free).  */
  1642   size_t               head;       /* Size and inuse bits. */
  1643   struct malloc_chunk* fd;         /* double links -- used only if free. */
  1644   struct malloc_chunk* bk;
  1645 };
  1646 
  1647 typedef struct malloc_chunk  mchunk;
  1648 typedef struct malloc_chunk* mchunkptr;
  1649 typedef struct malloc_chunk* sbinptr;  /* The type of bins of chunks */
  1650 typedef unsigned int bindex_t;         /* Described below */
  1651 typedef unsigned int binmap_t;         /* Described below */
  1652 typedef unsigned int flag_t;           /* The type of various bit flag sets */
  1653 
  1654 /* ------------------- Chunks sizes and alignments ----------------------- */
  1655 
  1656 #define MCHUNK_SIZE         (sizeof(mchunk))
  1657 
  1658 #if FOOTERS
  1659 #define CHUNK_OVERHEAD      (TWO_SIZE_T_SIZES)
  1660 #else /* FOOTERS */
  1661 #define CHUNK_OVERHEAD      (SIZE_T_SIZE)
  1662 #endif /* FOOTERS */
  1663 
  1664 /* MMapped chunks need a second word of overhead ... */
  1665 #define MMAP_CHUNK_OVERHEAD (TWO_SIZE_T_SIZES)
  1666 /* ... and additional padding for fake next-chunk at foot */
  1667 #define MMAP_FOOT_PAD       (FOUR_SIZE_T_SIZES)
  1668 
  1669 /* The smallest size we can malloc is an aligned minimal chunk */
  1670 #define MIN_CHUNK_SIZE\
  1671   ((MCHUNK_SIZE + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
  1672 
  1673 /* conversion from malloc headers to user pointers, and back */
  1674 #define chunk2mem(p)        ((void*)((char*)(p)       + TWO_SIZE_T_SIZES))
  1675 #define mem2chunk(mem)      ((mchunkptr)((char*)(mem) - TWO_SIZE_T_SIZES))
  1676 /* chunk associated with aligned address A */
  1677 #define align_as_chunk(A)   (mchunkptr)((A) + align_offset(chunk2mem(A)))
  1678 
  1679 /* Bounds on request (not chunk) sizes. */
  1680 #define MAX_REQUEST         ((-MIN_CHUNK_SIZE) << 2)
  1681 #define MIN_REQUEST         (MIN_CHUNK_SIZE - CHUNK_OVERHEAD - SIZE_T_ONE)
  1682 
  1683 /* pad request bytes into a usable size */
  1684 #define pad_request(req) \
  1685    (((req) + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
  1686 
  1687 /* pad request, checking for minimum (but not maximum) */
  1688 #define request2size(req) \
  1689   (((req) < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(req))
  1690 
  1691 
  1692 /* ------------------ Operations on head and foot fields ----------------- */
  1693 
  1694 /*
  1695   The head field of a chunk is or'ed with PINUSE_BIT when previous
  1696   adjacent chunk in use, and or'ed with CINUSE_BIT if this chunk is in
  1697   use. If the chunk was obtained with mmap, the prev_foot field has
  1698   IS_MMAPPED_BIT set, otherwise holding the offset of the base of the
  1699   mmapped region to the base of the chunk.
  1700 */
  1701 
  1702 #define PINUSE_BIT          (SIZE_T_ONE)
  1703 #define CINUSE_BIT          (SIZE_T_TWO)
  1704 #define INUSE_BITS          (PINUSE_BIT|CINUSE_BIT)
  1705 
  1706 /* Head value for fenceposts */
  1707 #define FENCEPOST_HEAD      (INUSE_BITS|SIZE_T_SIZE)
  1708 
  1709 /* extraction of fields from head words */
  1710 #define cinuse(p)           ((p)->head & CINUSE_BIT)
  1711 #define pinuse(p)           ((p)->head & PINUSE_BIT)
  1712 #define chunksize(p)        ((p)->head & ~(INUSE_BITS))
  1713 
  1714 #define clear_pinuse(p)     ((p)->head &= ~PINUSE_BIT)
  1715 #define clear_cinuse(p)     ((p)->head &= ~CINUSE_BIT)
  1716 
  1717 /* Treat space at ptr +/- offset as a chunk */
  1718 #define chunk_plus_offset(p, s)  ((mchunkptr)(((char*)(p)) + (s)))
  1719 #define chunk_minus_offset(p, s) ((mchunkptr)(((char*)(p)) - (s)))
  1720 
  1721 /* Ptr to next or previous physical malloc_chunk. */
  1722 #define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->head & ~INUSE_BITS)))
  1723 #define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_foot) ))
  1724 
  1725 /* extract next chunk's pinuse bit */
  1726 #define next_pinuse(p)  ((next_chunk(p)->head) & PINUSE_BIT)
  1727 
  1728 /* Get/set size at footer */
  1729 #define get_foot(p, s)  (((mchunkptr)((char*)(p) + (s)))->prev_foot)
  1730 #define set_foot(p, s)  (((mchunkptr)((char*)(p) + (s)))->prev_foot = (s))
  1731 
  1732 /* Set size, pinuse bit, and foot */
  1733 #define set_size_and_pinuse_of_free_chunk(p, s)\
  1734   ((p)->head = (s|PINUSE_BIT), set_foot(p, s))
  1735 
  1736 /* Set size, pinuse bit, foot, and clear next pinuse */
  1737 #define set_free_with_pinuse(p, s, n)\
  1738   (clear_pinuse(n), set_size_and_pinuse_of_free_chunk(p, s))
  1739 
  1740 #define is_mmapped(p)\
  1741   (!((p)->head & PINUSE_BIT) && ((p)->prev_foot & IS_MMAPPED_BIT))
  1742 
  1743 /* Get the internal overhead associated with chunk p */
  1744 #define overhead_for(p)\
  1745  (is_mmapped(p)? MMAP_CHUNK_OVERHEAD : CHUNK_OVERHEAD)
  1746 
  1747 /* Return true if malloced space is not necessarily cleared */
  1748 #if MMAP_CLEARS
  1749 #define calloc_must_clear(p) (!is_mmapped(p))
  1750 #else /* MMAP_CLEARS */
  1751 #define calloc_must_clear(p) (1)
  1752 #endif /* MMAP_CLEARS */
  1753 
  1754 /* ---------------------- Overlaid data structures ----------------------- */
  1755 
  1756 /*
  1757   When chunks are not in use, they are treated as nodes of either
  1758   lists or trees.
  1759 
  1760   "Small"  chunks are stored in circular doubly-linked lists, and look
  1761   like this:
  1762 
  1763     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1764             |             Size of previous chunk                            |
  1765             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1766     `head:' |             Size of chunk, in bytes                         |P|
  1767       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1768             |             Forward pointer to next chunk in list             |
  1769             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1770             |             Back pointer to previous chunk in list            |
  1771             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1772             |             Unused space (may be 0 bytes long)                .
  1773             .                                                               .
  1774             .                                                               |
  1775 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1776     `foot:' |             Size of chunk, in bytes                           |
  1777             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1778 
  1779   Larger chunks are kept in a form of bitwise digital trees (aka
  1780   tries) keyed on chunksizes.  Because malloc_tree_chunks are only for
  1781   free chunks greater than 256 bytes, their size doesn't impose any
  1782   constraints on user chunk sizes.  Each node looks like:
  1783 
  1784     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1785             |             Size of previous chunk                            |
  1786             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1787     `head:' |             Size of chunk, in bytes                         |P|
  1788       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1789             |             Forward pointer to next chunk of same size        |
  1790             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1791             |             Back pointer to previous chunk of same size       |
  1792             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1793             |             Pointer to left child (child[0])                  |
  1794             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1795             |             Pointer to right child (child[1])                 |
  1796             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1797             |             Pointer to parent                                 |
  1798             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1799             |             bin index of this chunk                           |
  1800             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1801             |             Unused space                                      .
  1802             .                                                               |
  1803 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1804     `foot:' |             Size of chunk, in bytes                           |
  1805             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1806 
  1807   Each tree holding treenodes is a tree of unique chunk sizes.  Chunks
  1808   of the same size are arranged in a circularly-linked list, with only
  1809   the oldest chunk (the next to be used, in our FIFO ordering)
  1810   actually in the tree.  (Tree members are distinguished by a non-null
  1811   parent pointer.)  If a chunk with the same size an an existing node
  1812   is inserted, it is linked off the existing node using pointers that
  1813   work in the same way as fd/bk pointers of small chunks.
  1814 
  1815   Each tree contains a power of 2 sized range of chunk sizes (the
  1816   smallest is 0x100 <= x < 0x180), which is is divided in half at each
  1817   tree level, with the chunks in the smaller half of the range (0x100
  1818   <= x < 0x140 for the top nose) in the left subtree and the larger
  1819   half (0x140 <= x < 0x180) in the right subtree.  This is, of course,
  1820   done by inspecting individual bits.
  1821 
  1822   Using these rules, each node's left subtree contains all smaller
  1823   sizes than its right subtree.  However, the node at the root of each
  1824   subtree has no particular ordering relationship to either.  (The
  1825   dividing line between the subtree sizes is based on trie relation.)
  1826   If we remove the last chunk of a given size from the interior of the
  1827   tree, we need to replace it with a leaf node.  The tree ordering
  1828   rules permit a node to be replaced by any leaf below it.
  1829 
  1830   The smallest chunk in a tree (a common operation in a best-fit
  1831   allocator) can be found by walking a path to the leftmost leaf in
  1832   the tree.  Unlike a usual binary tree, where we follow left child
  1833   pointers until we reach a null, here we follow the right child
  1834   pointer any time the left one is null, until we reach a leaf with
  1835   both child pointers null. The smallest chunk in the tree will be
  1836   somewhere along that path.
  1837 
  1838   The worst case number of steps to add, find, or remove a node is
  1839   bounded by the number of bits differentiating chunks within
  1840   bins. Under current bin calculations, this ranges from 6 up to 21
  1841   (for 32 bit sizes) or up to 53 (for 64 bit sizes). The typical case
  1842   is of course much better.
  1843 */
  1844 
  1845 struct malloc_tree_chunk {
  1846   /* The first four fields must be compatible with malloc_chunk */
  1847   size_t                    prev_foot;
  1848   size_t                    head;
  1849   struct malloc_tree_chunk* fd;
  1850   struct malloc_tree_chunk* bk;
  1851 
  1852   struct malloc_tree_chunk* child[2];
  1853   struct malloc_tree_chunk* parent;
  1854   bindex_t                  index;
  1855 };
  1856 
  1857 typedef struct malloc_tree_chunk  tchunk;
  1858 typedef struct malloc_tree_chunk* tchunkptr;
  1859 typedef struct malloc_tree_chunk* tbinptr; /* The type of bins of trees */
  1860 
  1861 /* A little helper macro for trees */
  1862 #define leftmost_child(t) ((t)->child[0] != 0? (t)->child[0] : (t)->child[1])
  1863 
  1864 /* ----------------------------- Segments -------------------------------- */
  1865 
  1866 /*
  1867   Each malloc space may include non-contiguous segments, held in a
  1868   list headed by an embedded malloc_segment record representing the
  1869   top-most space. Segments also include flags holding properties of
  1870   the space. Large chunks that are directly allocated by mmap are not
  1871   included in this list. They are instead independently created and
  1872   destroyed without otherwise keeping track of them.
  1873 
  1874   Segment management mainly comes into play for spaces allocated by
  1875   MMAP.  Any call to MMAP might or might not return memory that is
  1876   adjacent to an existing segment.  MORECORE normally contiguously
  1877   extends the current space, so this space is almost always adjacent,
  1878   which is simpler and faster to deal with. (This is why MORECORE is
  1879   used preferentially to MMAP when both are available -- see
  1880   sys_alloc.)  When allocating using MMAP, we don't use any of the
  1881   hinting mechanisms (inconsistently) supported in various
  1882   implementations of unix mmap, or distinguish reserving from
  1883   committing memory. Instead, we just ask for space, and exploit
  1884   contiguity when we get it.  It is probably possible to do
  1885   better than this on some systems, but no general scheme seems
  1886   to be significantly better.
  1887 
  1888   Management entails a simpler variant of the consolidation scheme
  1889   used for chunks to reduce fragmentation -- new adjacent memory is
  1890   normally prepended or appended to an existing segment. However,
  1891   there are limitations compared to chunk consolidation that mostly
  1892   reflect the fact that segment processing is relatively infrequent
  1893   (occurring only when getting memory from system) and that we
  1894   don't expect to have huge numbers of segments:
  1895 
  1896   * Segments are not indexed, so traversal requires linear scans.  (It
  1897     would be possible to index these, but is not worth the extra
  1898     overhead and complexity for most programs on most platforms.)
  1899   * New segments are only appended to old ones when holding top-most
  1900     memory; if they cannot be prepended to others, they are held in
  1901     different segments.
  1902 
  1903   Except for the top-most segment of an mstate, each segment record
  1904   is kept at the tail of its segment. Segments are added by pushing
  1905   segment records onto the list headed by &mstate.seg for the
  1906   containing mstate.
  1907 
  1908   Segment flags control allocation/merge/deallocation policies:
  1909   * If EXTERN_BIT set, then we did not allocate this segment,
  1910     and so should not try to deallocate or merge with others.
  1911     (This currently holds only for the initial segment passed
  1912     into create_mspace_with_base.)
  1913   * If IS_MMAPPED_BIT set, the segment may be merged with
  1914     other surrounding mmapped segments and trimmed/de-allocated
  1915     using munmap.
  1916   * If neither bit is set, then the segment was obtained using
  1917     MORECORE so can be merged with surrounding MORECORE'd segments
  1918     and deallocated/trimmed using MORECORE with negative arguments.
  1919 */
  1920 
  1921 struct malloc_segment {
  1922   char*        base;             /* base address */
  1923   size_t       size;             /* allocated size */
  1924   struct malloc_segment* next;   /* ptr to next segment */
  1925   flag_t       sflags;           /* mmap and extern flag */
  1926 };
  1927 
  1928 #define is_mmapped_segment(S)  ((S)->sflags & IS_MMAPPED_BIT)
  1929 #define is_extern_segment(S)   ((S)->sflags & EXTERN_BIT)
  1930 
  1931 typedef struct malloc_segment  msegment;
  1932 typedef struct malloc_segment* msegmentptr;
  1933 
  1934 /* ---------------------------- malloc_state ----------------------------- */
  1935 
  1936 /*
  1937    A malloc_state holds all of the bookkeeping for a space.
  1938    The main fields are:
  1939 
  1940   Top
  1941     The topmost chunk of the currently active segment. Its size is
  1942     cached in topsize.  The actual size of topmost space is
  1943     topsize+TOP_FOOT_SIZE, which includes space reserved for adding
  1944     fenceposts and segment records if necessary when getting more
  1945     space from the system.  The size at which to autotrim top is
  1946     cached from mparams in trim_check, except that it is disabled if
  1947     an autotrim fails.
  1948 
  1949   Designated victim (dv)
  1950     This is the preferred chunk for servicing small requests that
  1951     don't have exact fits.  It is normally the chunk split off most
  1952     recently to service another small request.  Its size is cached in
  1953     dvsize. The link fields of this chunk are not maintained since it
  1954     is not kept in a bin.
  1955 
  1956   SmallBins
  1957     An array of bin headers for free chunks.  These bins hold chunks
  1958     with sizes less than MIN_LARGE_SIZE bytes. Each bin contains
  1959     chunks of all the same size, spaced 8 bytes apart.  To simplify
  1960     use in double-linked lists, each bin header acts as a malloc_chunk
  1961     pointing to the real first node, if it exists (else pointing to
  1962     itself).  This avoids special-casing for headers.  But to avoid
  1963     waste, we allocate only the fd/bk pointers of bins, and then use
  1964     repositioning tricks to treat these as the fields of a chunk.
  1965 
  1966   TreeBins
  1967     Treebins are pointers to the roots of trees holding a range of
  1968     sizes. There are 2 equally spaced treebins for each power of two
  1969     from TREE_SHIFT to TREE_SHIFT+16. The last bin holds anything
  1970     larger.
  1971 
  1972   Bin maps
  1973     There is one bit map for small bins ("smallmap") and one for
  1974     treebins ("treemap).  Each bin sets its bit when non-empty, and
  1975     clears the bit when empty.  Bit operations are then used to avoid
  1976     bin-by-bin searching -- nearly all "search" is done without ever
  1977     looking at bins that won't be selected.  The bit maps
  1978     conservatively use 32 bits per map word, even if on 64bit system.
  1979     For a good description of some of the bit-based techniques used
  1980     here, see Henry S. Warren Jr's book "Hacker's Delight" (and
  1981     supplement at http://hackersdelight.org/). Many of these are
  1982     intended to reduce the branchiness of paths through malloc etc, as
  1983     well as to reduce the number of memory locations read or written.
  1984 
  1985   Segments
  1986     A list of segments headed by an embedded malloc_segment record
  1987     representing the initial space.
  1988 
  1989   Address check support
  1990     The least_addr field is the least address ever obtained from
  1991     MORECORE or MMAP. Attempted frees and reallocs of any address less
  1992     than this are trapped (unless INSECURE is defined).
  1993 
  1994   Magic tag
  1995     A cross-check field that should always hold same value as mparams.magic.
  1996 
  1997   Flags
  1998     Bits recording whether to use MMAP, locks, or contiguous MORECORE
  1999 
  2000   Statistics
  2001     Each space keeps track of current and maximum system memory
  2002     obtained via MORECORE or MMAP.
  2003 
  2004   Locking
  2005     If USE_LOCKS is defined, the "mutex" lock is acquired and released
  2006     around every public call using this mspace.
  2007 */
  2008 
  2009 /* Bin types, widths and sizes */
  2010 #define NSMALLBINS        (32U)
  2011 #define NTREEBINS         (32U)
  2012 #define SMALLBIN_SHIFT    (3U)
  2013 #define SMALLBIN_WIDTH    (SIZE_T_ONE << SMALLBIN_SHIFT)
  2014 #define TREEBIN_SHIFT     (8U)
  2015 #define MIN_LARGE_SIZE    (SIZE_T_ONE << TREEBIN_SHIFT)
  2016 #define MAX_SMALL_SIZE    (MIN_LARGE_SIZE - SIZE_T_ONE)
  2017 #define MAX_SMALL_REQUEST (MAX_SMALL_SIZE - CHUNK_ALIGN_MASK - CHUNK_OVERHEAD)
  2018 
  2019 struct malloc_state {
  2020   binmap_t   smallmap;
  2021   binmap_t   treemap;
  2022   size_t     dvsize;
  2023   size_t     topsize;
  2024   char*      least_addr;
  2025   mchunkptr  dv;
  2026   mchunkptr  top;
  2027   size_t     trim_check;
  2028   size_t     magic;
  2029   mchunkptr  smallbins[(NSMALLBINS+1)*2];
  2030   tbinptr    treebins[NTREEBINS];
  2031   size_t     footprint;
  2032   size_t     max_footprint;
  2033   flag_t     mflags;
  2034 #if USE_LOCKS
  2035   MLOCK_T    mutex;     /* locate lock among fields that rarely change */
  2036 #endif /* USE_LOCKS */
  2037   msegment   seg;
  2038 };
  2039 
  2040 typedef struct malloc_state*    mstate;
  2041 
  2042 /* ------------- Global malloc_state and malloc_params ------------------- */
  2043 
  2044 /*
  2045   malloc_params holds global properties, including those that can be
  2046   dynamically set using mallopt. There is a single instance, mparams,
  2047   initialized in init_mparams.
  2048 */
  2049 
  2050 struct malloc_params {
  2051   size_t magic;
  2052   size_t page_size;
  2053   size_t granularity;
  2054   size_t mmap_threshold;
  2055   size_t trim_threshold;
  2056   flag_t default_mflags;
  2057 };
  2058 
  2059 static struct malloc_params mparams;
  2060 
  2061 /* The global malloc_state used for all non-"mspace" calls */
  2062 static struct malloc_state _gm_;
  2063 #define gm                 (&_gm_)
  2064 #define is_global(M)       ((M) == &_gm_)
  2065 #define is_initialized(M)  ((M)->top != 0)
  2066 
  2067 /* -------------------------- system alloc setup ------------------------- */
  2068 
  2069 /* Operations on mflags */
  2070 
  2071 #define use_lock(M)           ((M)->mflags &   USE_LOCK_BIT)
  2072 #define enable_lock(M)        ((M)->mflags |=  USE_LOCK_BIT)
  2073 #define disable_lock(M)       ((M)->mflags &= ~USE_LOCK_BIT)
  2074 
  2075 #define use_mmap(M)           ((M)->mflags &   USE_MMAP_BIT)
  2076 #define enable_mmap(M)        ((M)->mflags |=  USE_MMAP_BIT)
  2077 #define disable_mmap(M)       ((M)->mflags &= ~USE_MMAP_BIT)
  2078 
  2079 #define use_noncontiguous(M)  ((M)->mflags &   USE_NONCONTIGUOUS_BIT)
  2080 #define disable_contiguous(M) ((M)->mflags |=  USE_NONCONTIGUOUS_BIT)
  2081 
  2082 #define set_lock(M,L)\
  2083  ((M)->mflags = (L)?\
  2084   ((M)->mflags | USE_LOCK_BIT) :\
  2085   ((M)->mflags & ~USE_LOCK_BIT))
  2086 
  2087 /* page-align a size */
  2088 #define page_align(S)\
  2089  (((S) + (mparams.page_size)) & ~(mparams.page_size - SIZE_T_ONE))
  2090 
  2091 /* granularity-align a size */
  2092 #define granularity_align(S)\
  2093   (((S) + (mparams.granularity)) & ~(mparams.granularity - SIZE_T_ONE))
  2094 
  2095 #define is_page_aligned(S)\
  2096    (((size_t)(S) & (mparams.page_size - SIZE_T_ONE)) == 0)
  2097 #define is_granularity_aligned(S)\
  2098    (((size_t)(S) & (mparams.granularity - SIZE_T_ONE)) == 0)
  2099 
  2100 /*  True if segment S holds address A */
  2101 #define segment_holds(S, A)\
  2102   ((char*)(A) >= S->base && (char*)(A) < S->base + S->size)
  2103 
  2104 /* Return segment holding given address */
  2105 static msegmentptr segment_holding(mstate m, char* addr) {
  2106   msegmentptr sp = &m->seg;
  2107   for (;;) {
  2108     if (addr >= sp->base && addr < sp->base + sp->size)
  2109       return sp;
  2110     if ((sp = sp->next) == 0)
  2111       return 0;
  2112   }
  2113 }
  2114 
  2115 /* Return true if segment contains a segment link */
  2116 static int has_segment_link(mstate m, msegmentptr ss) {
  2117   msegmentptr sp = &m->seg;
  2118   for (;;) {
  2119     if ((char*)sp >= ss->base && (char*)sp < ss->base + ss->size)
  2120       return 1;
  2121     if ((sp = sp->next) == 0)
  2122       return 0;
  2123   }
  2124 }
  2125 
  2126 #ifndef MORECORE_CANNOT_TRIM
  2127 #define should_trim(M,s)  ((s) > (M)->trim_check)
  2128 #else  /* MORECORE_CANNOT_TRIM */
  2129 #define should_trim(M,s)  (0)
  2130 #endif /* MORECORE_CANNOT_TRIM */
  2131 
  2132 /*
  2133   TOP_FOOT_SIZE is padding at the end of a segment, including space
  2134   that may be needed to place segment records and fenceposts when new
  2135   noncontiguous segments are added.
  2136 */
  2137 #define TOP_FOOT_SIZE\
  2138   (align_offset(chunk2mem(0))+pad_request(sizeof(struct malloc_segment))+MIN_CHUNK_SIZE)
  2139 
  2140 
  2141 /* -------------------------------  Hooks -------------------------------- */
  2142 
  2143 /*
  2144   PREACTION should be defined to return 0 on success, and nonzero on
  2145   failure. If you are not using locking, you can redefine these to do
  2146   anything you like.
  2147 */
  2148 
  2149 #if USE_LOCKS
  2150 
  2151 /* Ensure locks are initialized */
  2152 #define GLOBALLY_INITIALIZE() (mparams.page_size == 0 && init_mparams())
  2153 
  2154 #define PREACTION(M)  ((GLOBALLY_INITIALIZE() || use_lock(M))? ACQUIRE_LOCK(&(M)->mutex) : 0)
  2155 #define POSTACTION(M) { if (use_lock(M)) RELEASE_LOCK(&(M)->mutex); }
  2156 #else /* USE_LOCKS */
  2157 
  2158 #ifndef PREACTION
  2159 #define PREACTION(M) (0)
  2160 #endif  /* PREACTION */
  2161 
  2162 #ifndef POSTACTION
  2163 #define POSTACTION(M)
  2164 #endif  /* POSTACTION */
  2165 
  2166 #endif /* USE_LOCKS */
  2167 
  2168 /*
  2169   CORRUPTION_ERROR_ACTION is triggered upon detected bad addresses.
  2170   USAGE_ERROR_ACTION is triggered on detected bad frees and
  2171   reallocs. The argument p is an address that might have triggered the
  2172   fault. It is ignored by the two predefined actions, but might be
  2173   useful in custom actions that try to help diagnose errors.
  2174 */
  2175 
  2176 #if PROCEED_ON_ERROR
  2177 
  2178 /* A count of the number of corruption errors causing resets */
  2179 int malloc_corruption_error_count;
  2180 
  2181 /* default corruption action */
  2182 static void reset_on_error(mstate m);
  2183 
  2184 #define CORRUPTION_ERROR_ACTION(m)  reset_on_error(m)
  2185 #define USAGE_ERROR_ACTION(m, p)
  2186 
  2187 #else /* PROCEED_ON_ERROR */
  2188 
  2189 #ifndef CORRUPTION_ERROR_ACTION
  2190 #define CORRUPTION_ERROR_ACTION(m) ABORT
  2191 #endif /* CORRUPTION_ERROR_ACTION */
  2192 
  2193 #ifndef USAGE_ERROR_ACTION
  2194 #define USAGE_ERROR_ACTION(m,p) ABORT
  2195 #endif /* USAGE_ERROR_ACTION */
  2196 
  2197 #endif /* PROCEED_ON_ERROR */
  2198 
  2199 /* -------------------------- Debugging setup ---------------------------- */
  2200 
  2201 #if ! DEBUG
  2202 
  2203 #define check_free_chunk(M,P)
  2204 #define check_inuse_chunk(M,P)
  2205 #define check_malloced_chunk(M,P,N)
  2206 #define check_mmapped_chunk(M,P)
  2207 #define check_malloc_state(M)
  2208 #define check_top_chunk(M,P)
  2209 
  2210 #else /* DEBUG */
  2211 #define check_free_chunk(M,P)       do_check_free_chunk(M,P)
  2212 #define check_inuse_chunk(M,P)      do_check_inuse_chunk(M,P)
  2213 #define check_top_chunk(M,P)        do_check_top_chunk(M,P)
  2214 #define check_malloced_chunk(M,P,N) do_check_malloced_chunk(M,P,N)
  2215 #define check_mmapped_chunk(M,P)    do_check_mmapped_chunk(M,P)
  2216 #define check_malloc_state(M)       do_check_malloc_state(M)
  2217 
  2218 static void   do_check_any_chunk(mstate m, mchunkptr p);
  2219 static void   do_check_top_chunk(mstate m, mchunkptr p);
  2220 static void   do_check_mmapped_chunk(mstate m, mchunkptr p);
  2221 static void   do_check_inuse_chunk(mstate m, mchunkptr p);
  2222 static void   do_check_free_chunk(mstate m, mchunkptr p);
  2223 static void   do_check_malloced_chunk(mstate m, void* mem, size_t s);
  2224 static void   do_check_tree(mstate m, tchunkptr t);
  2225 static void   do_check_treebin(mstate m, bindex_t i);
  2226 static void   do_check_smallbin(mstate m, bindex_t i);
  2227 static void   do_check_malloc_state(mstate m);
  2228 static int    bin_find(mstate m, mchunkptr x);
  2229 static size_t traverse_and_check(mstate m);
  2230 #endif /* DEBUG */
  2231 
  2232 /* ---------------------------- Indexing Bins ---------------------------- */
  2233 
  2234 #define is_small(s)         (((s) >> SMALLBIN_SHIFT) < NSMALLBINS)
  2235 #define small_index(s)      ((s)  >> SMALLBIN_SHIFT)
  2236 #define small_index2size(i) ((i)  << SMALLBIN_SHIFT)
  2237 #define MIN_SMALL_INDEX     (small_index(MIN_CHUNK_SIZE))
  2238 
  2239 /* addressing by index. See above about smallbin repositioning */
  2240 #define smallbin_at(M, i)   ((sbinptr)((char*)&((M)->smallbins[(i)<<1])))
  2241 #define treebin_at(M,i)     (&((M)->treebins[i]))
  2242 
  2243 /* assign tree index for size S to variable I */
  2244 #if defined(__GNUC__) && defined(i386)
  2245 #define compute_tree_index(S, I)\
  2246 {\
  2247   size_t X = S >> TREEBIN_SHIFT;\
  2248   if (X == 0)\
  2249     I = 0;\
  2250   else if (X > 0xFFFF)\
  2251     I = NTREEBINS-1;\
  2252   else {\
  2253     unsigned int K;\
  2254     __asm__("bsrl %1,%0\n\t" : "=r" (K) : "rm"  (X));\
  2255     I =  (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
  2256   }\
  2257 }
  2258 #else /* GNUC */
  2259 #define compute_tree_index(S, I)\
  2260 {\
  2261   size_t X = S >> TREEBIN_SHIFT;\
  2262   if (X == 0)\
  2263     I = 0;\
  2264   else if (X > 0xFFFF)\
  2265     I = NTREEBINS-1;\
  2266   else {\
  2267     unsigned int Y = (unsigned int)X;\
  2268     unsigned int N = ((Y - 0x100) >> 16) & 8;\
  2269     unsigned int K = (((Y <<= N) - 0x1000) >> 16) & 4;\
  2270     N += K;\
  2271     N += K = (((Y <<= K) - 0x4000) >> 16) & 2;\
  2272     K = 14 - N + ((Y <<= K) >> 15);\
  2273     I = (K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1));\
  2274   }\
  2275 }
  2276 #endif /* GNUC */
  2277 
  2278 /* Bit representing maximum resolved size in a treebin at i */
  2279 #define bit_for_tree_index(i) \
  2280    (i == NTREEBINS-1)? (SIZE_T_BITSIZE-1) : (((i) >> 1) + TREEBIN_SHIFT - 2)
  2281 
  2282 /* Shift placing maximum resolved bit in a treebin at i as sign bit */
  2283 #define leftshift_for_tree_index(i) \
  2284    ((i == NTREEBINS-1)? 0 : \
  2285     ((SIZE_T_BITSIZE-SIZE_T_ONE) - (((i) >> 1) + TREEBIN_SHIFT - 2)))
  2286 
  2287 /* The size of the smallest chunk held in bin with index i */
  2288 #define minsize_for_tree_index(i) \
  2289    ((SIZE_T_ONE << (((i) >> 1) + TREEBIN_SHIFT)) |  \
  2290    (((size_t)((i) & SIZE_T_ONE)) << (((i) >> 1) + TREEBIN_SHIFT - 1)))
  2291 
  2292 
  2293 /* ------------------------ Operations on bin maps ----------------------- */
  2294 
  2295 /* bit corresponding to given index */
  2296 #define idx2bit(i)              ((binmap_t)(1) << (i))
  2297 
  2298 /* Mark/Clear bits with given index */
  2299 #define mark_smallmap(M,i)      ((M)->smallmap |=  idx2bit(i))
  2300 #define clear_smallmap(M,i)     ((M)->smallmap &= ~idx2bit(i))
  2301 #define smallmap_is_marked(M,i) ((M)->smallmap &   idx2bit(i))
  2302 
  2303 #define mark_treemap(M,i)       ((M)->treemap  |=  idx2bit(i))
  2304 #define clear_treemap(M,i)      ((M)->treemap  &= ~idx2bit(i))
  2305 #define treemap_is_marked(M,i)  ((M)->treemap  &   idx2bit(i))
  2306 
  2307 /* index corresponding to given bit */
  2308 
  2309 #if defined(__GNUC__) && defined(i386)
  2310 #define compute_bit2idx(X, I)\
  2311 {\
  2312   unsigned int J;\
  2313   __asm__("bsfl %1,%0\n\t" : "=r" (J) : "rm" (X));\
  2314   I = (bindex_t)J;\
  2315 }
  2316 
  2317 #else /* GNUC */
  2318 #if  USE_BUILTIN_FFS
  2319 #define compute_bit2idx(X, I) I = ffs(X)-1
  2320 
  2321 #else /* USE_BUILTIN_FFS */
  2322 #define compute_bit2idx(X, I)\
  2323 {\
  2324   unsigned int Y = X - 1;\
  2325   unsigned int K = Y >> (16-4) & 16;\
  2326   unsigned int N = K;        Y >>= K;\
  2327   N += K = Y >> (8-3) &  8;  Y >>= K;\
  2328   N += K = Y >> (4-2) &  4;  Y >>= K;\
  2329   N += K = Y >> (2-1) &  2;  Y >>= K;\
  2330   N += K = Y >> (1-0) &  1;  Y >>= K;\
  2331   I = (bindex_t)(N + Y);\
  2332 }
  2333 #endif /* USE_BUILTIN_FFS */
  2334 #endif /* GNUC */
  2335 
  2336 /* isolate the least set bit of a bitmap */
  2337 #define least_bit(x)         ((x) & -(x))
  2338 
  2339 /* mask with all bits to left of least bit of x on */
  2340 #define left_bits(x)         ((x<<1) | -(x<<1))
  2341 
  2342 /* mask with all bits to left of or equal to least bit of x on */
  2343 #define same_or_left_bits(x) ((x) | -(x))
  2344 
  2345 
  2346 /* ----------------------- Runtime Check Support ------------------------- */
  2347 
  2348 /*
  2349   For security, the main invariant is that malloc/free/etc never
  2350   writes to a static address other than malloc_state, unless static
  2351   malloc_state itself has been corrupted, which cannot occur via
  2352   malloc (because of these checks). In essence this means that we
  2353   believe all pointers, sizes, maps etc held in malloc_state, but
  2354   check all of those linked or offsetted from other embedded data
  2355   structures.  These checks are interspersed with main code in a way
  2356   that tends to minimize their run-time cost.
  2357 
  2358   When FOOTERS is defined, in addition to range checking, we also
  2359   verify footer fields of inuse chunks, which can be used guarantee
  2360   that the mstate controlling malloc/free is intact.  This is a
  2361   streamlined version of the approach described by William Robertson
  2362   et al in "Run-time Detection of Heap-based Overflows" LISA'03
  2363   http://www.usenix.org/events/lisa03/tech/robertson.html The footer
  2364   of an inuse chunk holds the xor of its mstate and a random seed,
  2365   that is checked upon calls to free() and realloc().  This is
  2366   (probablistically) unguessable from outside the program, but can be
  2367   computed by any code successfully malloc'ing any chunk, so does not
  2368   itself provide protection against code that has already broken
  2369   security through some other means.  Unlike Robertson et al, we
  2370   always dynamically check addresses of all offset chunks (previous,
  2371   next, etc). This turns out to be cheaper than relying on hashes.
  2372 */
  2373 
  2374 #if !INSECURE
  2375 /* Check if address a is at least as high as any from MORECORE or MMAP */
  2376 #define ok_address(M, a) ((char*)(a) >= (M)->least_addr)
  2377 /* Check if address of next chunk n is higher than base chunk p */
  2378 #define ok_next(p, n)    ((char*)(p) < (char*)(n))
  2379 /* Check if p has its cinuse bit on */
  2380 #define ok_cinuse(p)     cinuse(p)
  2381 /* Check if p has its pinuse bit on */
  2382 #define ok_pinuse(p)     pinuse(p)
  2383 
  2384 #else /* !INSECURE */
  2385 #define ok_address(M, a) (1)
  2386 #define ok_next(b, n)    (1)
  2387 #define ok_cinuse(p)     (1)
  2388 #define ok_pinuse(p)     (1)
  2389 #endif /* !INSECURE */
  2390 
  2391 #if (FOOTERS && !INSECURE)
  2392 /* Check if (alleged) mstate m has expected magic field */
  2393 #define ok_magic(M)      ((M)->magic == mparams.magic)
  2394 #else  /* (FOOTERS && !INSECURE) */
  2395 #define ok_magic(M)      (1)
  2396 #endif /* (FOOTERS && !INSECURE) */
  2397 
  2398 
  2399 /* In gcc, use __builtin_expect to minimize impact of checks */
  2400 #if !INSECURE
  2401 #if defined(__GNUC__) && __GNUC__ >= 3
  2402 #define RTCHECK(e)  __builtin_expect(e, 1)
  2403 #else /* GNUC */
  2404 #define RTCHECK(e)  (e)
  2405 #endif /* GNUC */
  2406 #else /* !INSECURE */
  2407 #define RTCHECK(e)  (1)
  2408 #endif /* !INSECURE */
  2409 
  2410 /* macros to set up inuse chunks with or without footers */
  2411 
  2412 #if !FOOTERS
  2413 
  2414 #define mark_inuse_foot(M,p,s)
  2415 
  2416 /* Set cinuse bit and pinuse bit of next chunk */
  2417 #define set_inuse(M,p,s)\
  2418   ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
  2419   ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
  2420 
  2421 /* Set cinuse and pinuse of this chunk and pinuse of next chunk */
  2422 #define set_inuse_and_pinuse(M,p,s)\
  2423   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
  2424   ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
  2425 
  2426 /* Set size, cinuse and pinuse bit of this chunk */
  2427 #define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
  2428   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT))
  2429 
  2430 #else /* FOOTERS */
  2431 
  2432 /* Set foot of inuse chunk to be xor of mstate and seed */
  2433 #define mark_inuse_foot(M,p,s)\
  2434   (((mchunkptr)((char*)(p) + (s)))->prev_foot = ((size_t)(M) ^ mparams.magic))
  2435 
  2436 #define get_mstate_for(p)\
  2437   ((mstate)(((mchunkptr)((char*)(p) +\
  2438     (chunksize(p))))->prev_foot ^ mparams.magic))
  2439 
  2440 #define set_inuse(M,p,s)\
  2441   ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
  2442   (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT), \
  2443   mark_inuse_foot(M,p,s))
  2444 
  2445 #define set_inuse_and_pinuse(M,p,s)\
  2446   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
  2447   (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT),\
  2448  mark_inuse_foot(M,p,s))
  2449 
  2450 #define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
  2451   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
  2452   mark_inuse_foot(M, p, s))
  2453 
  2454 #endif /* !FOOTERS */
  2455 
  2456 /* ---------------------------- setting mparams -------------------------- */
  2457 
  2458 /* Initialize mparams */
  2459 static int init_mparams(void) {
  2460   if (mparams.page_size == 0) {
  2461     size_t s;
  2462 
  2463     mparams.mmap_threshold = DEFAULT_MMAP_THRESHOLD;
  2464     mparams.trim_threshold = DEFAULT_TRIM_THRESHOLD;
  2465 #if MORECORE_CONTIGUOUS
  2466     mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT;
  2467 #else  /* MORECORE_CONTIGUOUS */
  2468     mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT|USE_NONCONTIGUOUS_BIT;
  2469 #endif /* MORECORE_CONTIGUOUS */
  2470 
  2471 #if (FOOTERS && !INSECURE)
  2472     {
  2473 #if USE_DEV_RANDOM
  2474       int fd;
  2475       unsigned char buf[sizeof(size_t)];
  2476       /* Try to use /dev/urandom, else fall back on using time */
  2477       if ((fd = open("/dev/urandom", O_RDONLY)) >= 0 &&
  2478           read(fd, buf, sizeof(buf)) == sizeof(buf)) {
  2479         s = *((size_t *) buf);
  2480         close(fd);
  2481       }
  2482       else
  2483 #endif /* USE_DEV_RANDOM */
  2484         s = (size_t)(time(0) ^ (size_t)0x55555555U);
  2485 
  2486       s |= (size_t)8U;    /* ensure nonzero */
  2487       s &= ~(size_t)7U;   /* improve chances of fault for bad values */
  2488 
  2489     }
  2490 #else /* (FOOTERS && !INSECURE) */
  2491     s = (size_t)0x58585858U;
  2492 #endif /* (FOOTERS && !INSECURE) */
  2493     ACQUIRE_MAGIC_INIT_LOCK();
  2494     if (mparams.magic == 0) {
  2495       mparams.magic = s;
  2496       /* Set up lock for main malloc area */
  2497       INITIAL_LOCK(&gm->mutex);
  2498       gm->mflags = mparams.default_mflags;
  2499     }
  2500     RELEASE_MAGIC_INIT_LOCK();
  2501 
  2502 #ifndef WIN32
  2503     mparams.page_size = malloc_getpagesize;
  2504     mparams.granularity = ((DEFAULT_GRANULARITY != 0)?
  2505                            DEFAULT_GRANULARITY : mparams.page_size);
  2506 #else /* WIN32 */
  2507     {
  2508       SYSTEM_INFO system_info;
  2509       GetSystemInfo(&system_info);
  2510       mparams.page_size = system_info.dwPageSize;
  2511       mparams.granularity = system_info.dwAllocationGranularity;
  2512     }
  2513 #endif /* WIN32 */
  2514 
  2515     /* Sanity-check configuration:
  2516        size_t must be unsigned and as wide as pointer type.
  2517        ints must be at least 4 bytes.
  2518        alignment must be at least 8.
  2519        Alignment, min chunk size, and page size must all be powers of 2.
  2520     */
  2521     if ((sizeof(size_t) != sizeof(char*)) ||
  2522         (MAX_SIZE_T < MIN_CHUNK_SIZE)  ||
  2523         (sizeof(int) < 4)  ||
  2524         (MALLOC_ALIGNMENT < (size_t)8U) ||
  2525         ((MALLOC_ALIGNMENT    & (MALLOC_ALIGNMENT-SIZE_T_ONE))    != 0) ||
  2526         ((MCHUNK_SIZE         & (MCHUNK_SIZE-SIZE_T_ONE))         != 0) ||
  2527         ((mparams.granularity & (mparams.granularity-SIZE_T_ONE)) != 0) ||
  2528         ((mparams.page_size   & (mparams.page_size-SIZE_T_ONE))   != 0))
  2529       ABORT;
  2530   }
  2531   return 0;
  2532 }
  2533 
  2534 /* support for mallopt */
  2535 static int change_mparam(int param_number, int value) {
  2536   size_t val = (size_t)value;
  2537   init_mparams();
  2538   switch(param_number) {
  2539   case M_TRIM_THRESHOLD:
  2540     mparams.trim_threshold = val;
  2541     return 1;
  2542   case M_GRANULARITY:
  2543     if (val >= mparams.page_size && ((val & (val-1)) == 0)) {
  2544       mparams.granularity = val;
  2545       return 1;
  2546     }
  2547     else
  2548       return 0;
  2549   case M_MMAP_THRESHOLD:
  2550     mparams.mmap_threshold = val;
  2551     return 1;
  2552   default:
  2553     return 0;
  2554   }
  2555 }
  2556 
  2557 #if DEBUG
  2558 /* ------------------------- Debugging Support --------------------------- */
  2559 
  2560 /* Check properties of any chunk, whether free, inuse, mmapped etc  */
  2561 static void do_check_any_chunk(mstate m, mchunkptr p) {
  2562   assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
  2563   assert(ok_address(m, p));
  2564 }
  2565 
  2566 /* Check properties of top chunk */
  2567 static void do_check_top_chunk(mstate m, mchunkptr p) {
  2568   msegmentptr sp = segment_holding(m, (char*)p);
  2569   size_t  sz = chunksize(p);
  2570   assert(sp != 0);
  2571   assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
  2572   assert(ok_address(m, p));
  2573   assert(sz == m->topsize);
  2574   assert(sz > 0);
  2575   assert(sz == ((sp->base + sp->size) - (char*)p) - TOP_FOOT_SIZE);
  2576   assert(pinuse(p));
  2577   assert(!next_pinuse(p));
  2578 }
  2579 
  2580 /* Check properties of (inuse) mmapped chunks */
  2581 static void do_check_mmapped_chunk(mstate m, mchunkptr p) {
  2582   size_t  sz = chunksize(p);
  2583   size_t len = (sz + (p->prev_foot & ~IS_MMAPPED_BIT) + MMAP_FOOT_PAD);
  2584   assert(is_mmapped(p));
  2585   assert(use_mmap(m));
  2586   assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
  2587   assert(ok_address(m, p));
  2588   assert(!is_small(sz));
  2589   assert((len & (mparams.page_size-SIZE_T_ONE)) == 0);
  2590   assert(chunk_plus_offset(p, sz)->head == FENCEPOST_HEAD);
  2591   assert(chunk_plus_offset(p, sz+SIZE_T_SIZE)->head == 0);
  2592 }
  2593 
  2594 /* Check properties of inuse chunks */
  2595 static void do_check_inuse_chunk(mstate m, mchunkptr p) {
  2596   do_check_any_chunk(m, p);
  2597   assert(cinuse(p));
  2598   assert(next_pinuse(p));
  2599   /* If not pinuse and not mmapped, previous chunk has OK offset */
  2600   assert(is_mmapped(p) || pinuse(p) || next_chunk(prev_chunk(p)) == p);
  2601   if (is_mmapped(p))
  2602     do_check_mmapped_chunk(m, p);
  2603 }
  2604 
  2605 /* Check properties of free chunks */
  2606 static void do_check_free_chunk(mstate m, mchunkptr p) {
  2607   size_t sz = p->head & ~(PINUSE_BIT|CINUSE_BIT);
  2608   mchunkptr next = chunk_plus_offset(p, sz);
  2609   do_check_any_chunk(m, p);
  2610   assert(!cinuse(p));
  2611   assert(!next_pinuse(p));
  2612   assert (!is_mmapped(p));
  2613   if (p != m->dv && p != m->top) {
  2614     if (sz >= MIN_CHUNK_SIZE) {
  2615       assert((sz & CHUNK_ALIGN_MASK) == 0);
  2616       assert(is_aligned(chunk2mem(p)));
  2617       assert(next->prev_foot == sz);
  2618       assert(pinuse(p));
  2619       assert (next == m->top || cinuse(next));
  2620       assert(p->fd->bk == p);
  2621       assert(p->bk->fd == p);
  2622     }
  2623     else  /* markers are always of size SIZE_T_SIZE */
  2624       assert(sz == SIZE_T_SIZE);
  2625   }
  2626 }
  2627 
  2628 /* Check properties of malloced chunks at the point they are malloced */
  2629 static void do_check_malloced_chunk(mstate m, void* mem, size_t s) {
  2630   if (mem != 0) {
  2631     mchunkptr p = mem2chunk(mem);
  2632     size_t sz = p->head & ~(PINUSE_BIT|CINUSE_BIT);
  2633     do_check_inuse_chunk(m, p);
  2634     assert((sz & CHUNK_ALIGN_MASK) == 0);
  2635     assert(sz >= MIN_CHUNK_SIZE);
  2636     assert(sz >= s);
  2637     /* unless mmapped, size is less than MIN_CHUNK_SIZE more than request */
  2638     assert(is_mmapped(p) || sz < (s + MIN_CHUNK_SIZE));
  2639   }
  2640 }
  2641 
  2642 /* Check a tree and its subtrees.  */
  2643 static void do_check_tree(mstate m, tchunkptr t) {
  2644   tchunkptr head = 0;
  2645   tchunkptr u = t;
  2646   bindex_t tindex = t->index;
  2647   size_t tsize = chunksize(t);
  2648   bindex_t idx;
  2649   compute_tree_index(tsize, idx);
  2650   assert(tindex == idx);
  2651   assert(tsize >= MIN_LARGE_SIZE);
  2652   assert(tsize >= minsize_for_tree_index(idx));
  2653   assert((idx == NTREEBINS-1) || (tsize < minsize_for_tree_index((idx+1))));
  2654 
  2655   do { /* traverse through chain of same-sized nodes */
  2656     do_check_any_chunk(m, ((mchunkptr)u));
  2657     assert(u->index == tindex);
  2658     assert(chunksize(u) == tsize);
  2659     assert(!cinuse(u));
  2660     assert(!next_pinuse(u));
  2661     assert(u->fd->bk == u);
  2662     assert(u->bk->fd == u);
  2663     if (u->parent == 0) {
  2664       assert(u->child[0] == 0);
  2665       assert(u->child[1] == 0);
  2666     }
  2667     else {
  2668       assert(head == 0); /* only one node on chain has parent */
  2669       head = u;
  2670       assert(u->parent != u);
  2671       assert (u->parent->child[0] == u ||
  2672               u->parent->child[1] == u ||
  2673               *((tbinptr*)(u->parent)) == u);
  2674       if (u->child[0] != 0) {
  2675         assert(u->child[0]->parent == u);
  2676         assert(u->child[0] != u);
  2677         do_check_tree(m, u->child[0]);
  2678       }
  2679       if (u->child[1] != 0) {
  2680         assert(u->child[1]->parent == u);
  2681         assert(u->child[1] != u);
  2682         do_check_tree(m, u->child[1]);
  2683       }
  2684       if (u->child[0] != 0 && u->child[1] != 0) {
  2685         assert(chunksize(u->child[0]) < chunksize(u->child[1]));
  2686       }
  2687     }
  2688     u = u->fd;
  2689   } while (u != t);
  2690   assert(head != 0);
  2691 }
  2692 
  2693 /*  Check all the chunks in a treebin.  */
  2694 static void do_check_treebin(mstate m, bindex_t i) {
  2695   tbinptr* tb = treebin_at(m, i);
  2696   tchunkptr t = *tb;
  2697   int empty = (m->treemap & (1U << i)) == 0;
  2698   if (t == 0)
  2699     assert(empty);
  2700   if (!empty)
  2701     do_check_tree(m, t);
  2702 }
  2703 
  2704 /*  Check all the chunks in a smallbin.  */
  2705 static void do_check_smallbin(mstate m, bindex_t i) {
  2706   sbinptr b = smallbin_at(m, i);
  2707   mchunkptr p = b->bk;
  2708   unsigned int empty = (m->smallmap & (1U << i)) == 0;
  2709   if (p == b)
  2710     assert(empty);
  2711   if (!empty) {
  2712     for (; p != b; p = p->bk) {
  2713       size_t size = chunksize(p);
  2714       mchunkptr q;
  2715       /* each chunk claims to be free */
  2716       do_check_free_chunk(m, p);
  2717       /* chunk belongs in bin */
  2718       assert(small_index(size) == i);
  2719       assert(p->bk == b || chunksize(p->bk) == chunksize(p));
  2720       /* chunk is followed by an inuse chunk */
  2721       q = next_chunk(p);
  2722       if (q->head != FENCEPOST_HEAD)
  2723         do_check_inuse_chunk(m, q);
  2724     }
  2725   }
  2726 }
  2727 
  2728 /* Find x in a bin. Used in other check functions. */
  2729 static int bin_find(mstate m, mchunkptr x) {
  2730   size_t size = chunksize(x);
  2731   if (is_small(size)) {
  2732     bindex_t sidx = small_index(size);
  2733     sbinptr b = smallbin_at(m, sidx);
  2734     if (smallmap_is_marked(m, sidx)) {
  2735       mchunkptr p = b;
  2736       do {
  2737         if (p == x)
  2738           return 1;
  2739       } while ((p = p->fd) != b);
  2740     }
  2741   }
  2742   else {
  2743     bindex_t tidx;
  2744     compute_tree_index(size, tidx);
  2745     if (treemap_is_marked(m, tidx)) {
  2746       tchunkptr t = *treebin_at(m, tidx);
  2747       size_t sizebits = size << leftshift_for_tree_index(tidx);
  2748       while (t != 0 && chunksize(t) != size) {
  2749         t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
  2750         sizebits <<= 1;
  2751       }
  2752       if (t != 0) {
  2753         tchunkptr u = t;
  2754         do {
  2755           if (u == (tchunkptr)x)
  2756             return 1;
  2757         } while ((u = u->fd) != t);
  2758       }
  2759     }
  2760   }
  2761   return 0;
  2762 }
  2763 
  2764 /* Traverse each chunk and check it; return total */
  2765 static size_t traverse_and_check(mstate m) {
  2766   size_t sum = 0;
  2767   if (is_initialized(m)) {
  2768     msegmentptr s = &m->seg;
  2769     sum += m->topsize + TOP_FOOT_SIZE;
  2770     while (s != 0) {
  2771       mchunkptr q = align_as_chunk(s->base);
  2772       mchunkptr lastq = 0;
  2773       assert(pinuse(q));
  2774       while (segment_holds(s, q) &&
  2775              q != m->top && q->head != FENCEPOST_HEAD) {
  2776         sum += chunksize(q);
  2777         if (cinuse(q)) {
  2778           assert(!bin_find(m, q));
  2779           do_check_inuse_chunk(m, q);
  2780         }
  2781         else {
  2782           assert(q == m->dv || bin_find(m, q));
  2783           assert(lastq == 0 || cinuse(lastq)); /* Not 2 consecutive free */
  2784           do_check_free_chunk(m, q);
  2785         }
  2786         lastq = q;
  2787         q = next_chunk(q);
  2788       }
  2789       s = s->next;
  2790     }
  2791   }
  2792   return sum;
  2793 }
  2794 
  2795 /* Check all properties of malloc_state. */
  2796 static void do_check_malloc_state(mstate m) {
  2797   bindex_t i;
  2798   size_t total;
  2799   /* check bins */
  2800   for (i = 0; i < NSMALLBINS; ++i)
  2801     do_check_smallbin(m, i);
  2802   for (i = 0; i < NTREEBINS; ++i)
  2803     do_check_treebin(m, i);
  2804 
  2805   if (m->dvsize != 0) { /* check dv chunk */
  2806     do_check_any_chunk(m, m->dv);
  2807     assert(m->dvsize == chunksize(m->dv));
  2808     assert(m->dvsize >= MIN_CHUNK_SIZE);
  2809     assert(bin_find(m, m->dv) == 0);
  2810   }
  2811 
  2812   if (m->top != 0) {   /* check top chunk */
  2813     do_check_top_chunk(m, m->top);
  2814     assert(m->topsize == chunksize(m->top));
  2815     assert(m->topsize > 0);
  2816     assert(bin_find(m, m->top) == 0);
  2817   }
  2818 
  2819   total = traverse_and_check(m);
  2820   assert(total <= m->footprint);
  2821   assert(m->footprint <= m->max_footprint);
  2822 }
  2823 #endif /* DEBUG */
  2824 
  2825 /* ----------------------------- statistics ------------------------------ */
  2826 
  2827 #if !NO_MALLINFO
  2828 static struct mallinfo internal_mallinfo(mstate m) {
  2829   struct mallinfo nm = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
  2830   if (!PREACTION(m)) {
  2831     check_malloc_state(m);
  2832     if (is_initialized(m)) {
  2833       size_t nfree = SIZE_T_ONE; /* top always free */
  2834       size_t mfree = m->topsize + TOP_FOOT_SIZE;
  2835       size_t sum = mfree;
  2836       msegmentptr s = &m->seg;
  2837       while (s != 0) {
  2838         mchunkptr q = align_as_chunk(s->base);
  2839         while (segment_holds(s, q) &&
  2840                q != m->top && q->head != FENCEPOST_HEAD) {
  2841           size_t sz = chunksize(q);
  2842           sum += sz;
  2843           if (!cinuse(q)) {
  2844             mfree += sz;
  2845             ++nfree;
  2846           }
  2847           q = next_chunk(q);
  2848         }
  2849         s = s->next;
  2850       }
  2851 
  2852       nm.arena    = sum;
  2853       nm.ordblks  = nfree;
  2854       nm.hblkhd   = m->footprint - sum;
  2855       nm.usmblks  = m->max_footprint;
  2856       nm.uordblks = m->footprint - mfree;
  2857       nm.fordblks = mfree;
  2858       nm.keepcost = m->topsize;
  2859     }
  2860 
  2861     POSTACTION(m);
  2862   }
  2863   return nm;
  2864 }
  2865 #endif /* !NO_MALLINFO */
  2866 
  2867 static void internal_malloc_stats(mstate m) {
  2868   if (!PREACTION(m)) {
  2869     size_t maxfp = 0;
  2870     size_t fp = 0;
  2871     size_t used = 0;
  2872     check_malloc_state(m);
  2873     if (is_initialized(m)) {
  2874       msegmentptr s = &m->seg;
  2875       maxfp = m->max_footprint;
  2876       fp = m->footprint;
  2877       used = fp - (m->topsize + TOP_FOOT_SIZE);
  2878 
  2879       while (s != 0) {
  2880         mchunkptr q = align_as_chunk(s->base);
  2881         while (segment_holds(s, q) &&
  2882                q != m->top && q->head != FENCEPOST_HEAD) {
  2883           if (!cinuse(q))
  2884             used -= chunksize(q);
  2885           q = next_chunk(q);
  2886         }
  2887         s = s->next;
  2888       }
  2889     }
  2890 
  2891 #ifndef LACKS_STDIO_H
  2892     fprintf(stderr, "max system bytes = %10lu\n", (unsigned long)(maxfp));
  2893     fprintf(stderr, "system bytes     = %10lu\n", (unsigned long)(fp));
  2894     fprintf(stderr, "in use bytes     = %10lu\n", (unsigned long)(used));
  2895 #endif
  2896 
  2897     POSTACTION(m);
  2898   }
  2899 }
  2900 
  2901 /* ----------------------- Operations on smallbins ----------------------- */
  2902 
  2903 /*
  2904   Various forms of linking and unlinking are defined as macros.  Even
  2905   the ones for trees, which are very long but have very short typical
  2906   paths.  This is ugly but reduces reliance on inlining support of
  2907   compilers.
  2908 */
  2909 
  2910 /* Link a free chunk into a smallbin  */
  2911 #define insert_small_chunk(M, P, S) {\
  2912   bindex_t I  = small_index(S);\
  2913   mchunkptr B = smallbin_at(M, I);\
  2914   mchunkptr F = B;\
  2915   assert(S >= MIN_CHUNK_SIZE);\
  2916   if (!smallmap_is_marked(M, I))\
  2917     mark_smallmap(M, I);\
  2918   else if (RTCHECK(ok_address(M, B->fd)))\
  2919     F = B->fd;\
  2920   else {\
  2921     CORRUPTION_ERROR_ACTION(M);\
  2922   }\
  2923   B->fd = P;\
  2924   F->bk = P;\
  2925   P->fd = F;\
  2926   P->bk = B;\
  2927 }
  2928 
  2929 /* Unlink a chunk from a smallbin  */
  2930 #define unlink_small_chunk(M, P, S) {\
  2931   mchunkptr F = P->fd;\
  2932   mchunkptr B = P->bk;\
  2933   bindex_t I = small_index(S);\
  2934   assert(P != B);\
  2935   assert(P != F);\
  2936   assert(chunksize(P) == small_index2size(I));\
  2937   if (F == B)\
  2938     clear_smallmap(M, I);\
  2939   else if (RTCHECK((F == smallbin_at(M,I) || ok_address(M, F)) &&\
  2940                    (B == smallbin_at(M,I) || ok_address(M, B)))) {\
  2941     F->bk = B;\
  2942     B->fd = F;\
  2943   }\
  2944   else {\
  2945     CORRUPTION_ERROR_ACTION(M);\
  2946   }\
  2947 }
  2948 
  2949 /* Unlink the first chunk from a smallbin */
  2950 #define unlink_first_small_chunk(M, B, P, I) {\
  2951   mchunkptr F = P->fd;\
  2952   assert(P != B);\
  2953   assert(P != F);\
  2954   assert(chunksize(P) == small_index2size(I));\
  2955   if (B == F)\
  2956     clear_smallmap(M, I);\
  2957   else if (RTCHECK(ok_address(M, F))) {\
  2958     B->fd = F;\
  2959     F->bk = B;\
  2960   }\
  2961   else {\
  2962     CORRUPTION_ERROR_ACTION(M);\
  2963   }\
  2964 }
  2965 
  2966 /* Replace dv node, binning the old one */
  2967 /* Used only when dvsize known to be small */
  2968 #define replace_dv(M, P, S) {\
  2969   size_t DVS = M->dvsize;\
  2970   if (DVS != 0) {\
  2971     mchunkptr DV = M->dv;\
  2972     assert(is_small(DVS));\
  2973     insert_small_chunk(M, DV, DVS);\
  2974   }\
  2975   M->dvsize = S;\
  2976   M->dv = P;\
  2977 }
  2978 
  2979 /* ------------------------- Operations on trees ------------------------- */
  2980 
  2981 /* Insert chunk into tree */
  2982 #define insert_large_chunk(M, X, S) {\
  2983   tbinptr* H;\
  2984   bindex_t I;\
  2985   compute_tree_index(S, I);\
  2986   H = treebin_at(M, I);\
  2987   X->index = I;\
  2988   X->child[0] = X->child[1] = 0;\
  2989   if (!treemap_is_marked(M, I)) {\
  2990     mark_treemap(M, I);\
  2991     *H = X;\
  2992     X->parent = (tchunkptr)H;\
  2993     X->fd = X->bk = X;\
  2994   }\
  2995   else {\
  2996     tchunkptr T = *H;\
  2997     size_t K = S << leftshift_for_tree_index(I);\
  2998     for (;;) {\
  2999       if (chunksize(T) != S) {\
  3000         tchunkptr* C = &(T->child[(K >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1]);\
  3001         K <<= 1;\
  3002         if (*C != 0)\
  3003           T = *C;\
  3004         else if (RTCHECK(ok_address(M, C))) {\
  3005           *C = X;\
  3006           X->parent = T;\
  3007           X->fd = X->bk = X;\
  3008           break;\
  3009         }\
  3010         else {\
  3011           CORRUPTION_ERROR_ACTION(M);\
  3012           break;\
  3013         }\
  3014       }\
  3015       else {\
  3016         tchunkptr F = T->fd;\
  3017         if (RTCHECK(ok_address(M, T) && ok_address(M, F))) {\
  3018           T->fd = F->bk = X;\
  3019           X->fd = F;\
  3020           X->bk = T;\
  3021           X->parent = 0;\
  3022           break;\
  3023         }\
  3024         else {\
  3025           CORRUPTION_ERROR_ACTION(M);\
  3026           break;\
  3027         }\
  3028       }\
  3029     }\
  3030   }\
  3031 }
  3032 
  3033 /*
  3034   Unlink steps:
  3035 
  3036   1. If x is a chained node, unlink it from its same-sized fd/bk links
  3037      and choose its bk node as its replacement.
  3038   2. If x was the last node of its size, but not a leaf node, it must
  3039      be replaced with a leaf node (not merely one with an open left or
  3040      right), to make sure that lefts and rights of descendents
  3041      correspond properly to bit masks.  We use the rightmost descendent
  3042      of x.  We could use any other leaf, but this is easy to locate and
  3043      tends to counteract removal of leftmosts elsewhere, and so keeps
  3044      paths shorter than minimally guaranteed.  This doesn't loop much
  3045      because on average a node in a tree is near the bottom.
  3046   3. If x is the base of a chain (i.e., has parent links) relink
  3047      x's parent and children to x's replacement (or null if none).
  3048 */
  3049 
  3050 #define unlink_large_chunk(M, X) {\
  3051   tchunkptr XP = X->parent;\
  3052   tchunkptr R;\
  3053   if (X->bk != X) {\
  3054     tchunkptr F = X->fd;\
  3055     R = X->bk;\
  3056     if (RTCHECK(ok_address(M, F))) {\
  3057       F->bk = R;\
  3058       R->fd = F;\
  3059     }\
  3060     else {\
  3061       CORRUPTION_ERROR_ACTION(M);\
  3062     }\
  3063   }\
  3064   else {\
  3065     tchunkptr* RP;\
  3066     if (((R = *(RP = &(X->child[1]))) != 0) ||\
  3067         ((R = *(RP = &(X->child[0]))) != 0)) {\
  3068       tchunkptr* CP;\
  3069       while ((*(CP = &(R->child[1])) != 0) ||\
  3070              (*(CP = &(R->child[0])) != 0)) {\
  3071         R = *(RP = CP);\
  3072       }\
  3073       if (RTCHECK(ok_address(M, RP)))\
  3074         *RP = 0;\
  3075       else {\
  3076         CORRUPTION_ERROR_ACTION(M);\
  3077       }\
  3078     }\
  3079   }\
  3080   if (XP != 0) {\
  3081     tbinptr* H = treebin_at(M, X->index);\
  3082     if (X == *H) {\
  3083       if ((*H = R) == 0) \
  3084         clear_treemap(M, X->index);\
  3085     }\
  3086     else if (RTCHECK(ok_address(M, XP))) {\
  3087       if (XP->child[0] == X) \
  3088         XP->child[0] = R;\
  3089       else \
  3090         XP->child[1] = R;\
  3091     }\
  3092     else\
  3093       CORRUPTION_ERROR_ACTION(M);\
  3094     if (R != 0) {\
  3095       if (RTCHECK(ok_address(M, R))) {\
  3096         tchunkptr C0, C1;\
  3097         R->parent = XP;\
  3098         if ((C0 = X->child[0]) != 0) {\
  3099           if (RTCHECK(ok_address(M, C0))) {\
  3100             R->child[0] = C0;\
  3101             C0->parent = R;\
  3102           }\
  3103           else\
  3104             CORRUPTION_ERROR_ACTION(M);\
  3105         }\
  3106         if ((C1 = X->child[1]) != 0) {\
  3107           if (RTCHECK(ok_address(M, C1))) {\
  3108             R->child[1] = C1;\
  3109             C1->parent = R;\
  3110           }\
  3111           else\
  3112             CORRUPTION_ERROR_ACTION(M);\
  3113         }\
  3114       }\
  3115       else\
  3116         CORRUPTION_ERROR_ACTION(M);\
  3117     }\
  3118   }\
  3119 }
  3120 
  3121 /* Relays to large vs small bin operations */
  3122 
  3123 #define insert_chunk(M, P, S)\
  3124   if (is_small(S)) insert_small_chunk(M, P, S)\
  3125   else { tchunkptr TP = (tchunkptr)(P); insert_large_chunk(M, TP, S); }
  3126 
  3127 #define unlink_chunk(M, P, S)\
  3128   if (is_small(S)) unlink_small_chunk(M, P, S)\
  3129   else { tchunkptr TP = (tchunkptr)(P); unlink_large_chunk(M, TP); }
  3130 
  3131 
  3132 /* Relays to internal calls to malloc/free from realloc, memalign etc */
  3133 
  3134 #if ONLY_MSPACES
  3135 #define internal_malloc(m, b) mspace_malloc(m, b)
  3136 #define internal_free(m, mem) mspace_free(m,mem);
  3137 #else /* ONLY_MSPACES */
  3138 #if MSPACES
  3139 #define internal_malloc(m, b)\
  3140    (m == gm)? dlmalloc(b) : mspace_malloc(m, b)
  3141 #define internal_free(m, mem)\
  3142    if (m == gm) dlfree(mem); else mspace_free(m,mem);
  3143 #else /* MSPACES */
  3144 #define internal_malloc(m, b) dlmalloc(b)
  3145 #define internal_free(m, mem) dlfree(mem)
  3146 #endif /* MSPACES */
  3147 #endif /* ONLY_MSPACES */
  3148 
  3149 /* -----------------------  Direct-mmapping chunks ----------------------- */
  3150 
  3151 /*
  3152   Directly mmapped chunks are set up with an offset to the start of
  3153   the mmapped region stored in the prev_foot field of the chunk. This
  3154   allows reconstruction of the required argument to MUNMAP when freed,
  3155   and also allows adjustment of the returned chunk to meet alignment
  3156   requirements (especially in memalign).  There is also enough space
  3157   allocated to hold a fake next chunk of size SIZE_T_SIZE to maintain
  3158   the PINUSE bit so frees can be checked.
  3159 */
  3160 
  3161 /* Malloc using mmap */
  3162 static void* mmap_alloc(mstate m, size_t nb) {
  3163   size_t mmsize = granularity_align(nb + SIX_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
  3164   if (mmsize > nb) {     /* Check for wrap around 0 */
  3165     char* mm = (char*)(DIRECT_MMAP(mmsize));
  3166     if (mm != CMFAIL) {
  3167       size_t offset = align_offset(chunk2mem(mm));
  3168       size_t psize = mmsize - offset - MMAP_FOOT_PAD;
  3169       mchunkptr p = (mchunkptr)(mm + offset);
  3170       p->prev_foot = offset | IS_MMAPPED_BIT;
  3171       (p)->head = (psize|CINUSE_BIT);
  3172       mark_inuse_foot(m, p, psize);
  3173       chunk_plus_offset(p, psize)->head = FENCEPOST_HEAD;
  3174       chunk_plus_offset(p, psize+SIZE_T_SIZE)->head = 0;
  3175 
  3176       if (mm < m->least_addr)
  3177         m->least_addr = mm;
  3178       if ((m->footprint += mmsize) > m->max_footprint)
  3179         m->max_footprint = m->footprint;
  3180       assert(is_aligned(chunk2mem(p)));
  3181       check_mmapped_chunk(m, p);
  3182       return chunk2mem(p);
  3183     }
  3184   }
  3185   return 0;
  3186 }
  3187 
  3188 /* Realloc using mmap */
  3189 static mchunkptr mmap_resize(mstate m, mchunkptr oldp, size_t nb) {
  3190   size_t oldsize = chunksize(oldp);
  3191   if (is_small(nb)) /* Can't shrink mmap regions below small size */
  3192     return 0;
  3193   /* Keep old chunk if big enough but not too big */
  3194   if (oldsize >= nb + SIZE_T_SIZE &&
  3195       (oldsize - nb) <= (mparams.granularity << 1))
  3196     return oldp;
  3197   else {
  3198     size_t offset = oldp->prev_foot & ~IS_MMAPPED_BIT;
  3199     size_t oldmmsize = oldsize + offset + MMAP_FOOT_PAD;
  3200     size_t newmmsize = granularity_align(nb + SIX_SIZE_T_SIZES +
  3201                                          CHUNK_ALIGN_MASK);
  3202     char* cp = (char*)CALL_MREMAP((char*)oldp - offset,
  3203                                   oldmmsize, newmmsize, 1);
  3204     if (cp != CMFAIL) {
  3205       mchunkptr newp = (mchunkptr)(cp + offset);
  3206       size_t psize = newmmsize - offset - MMAP_FOOT_PAD;
  3207       newp->head = (psize|CINUSE_BIT);
  3208       mark_inuse_foot(m, newp, psize);
  3209       chunk_plus_offset(newp, psize)->head = FENCEPOST_HEAD;
  3210       chunk_plus_offset(newp, psize+SIZE_T_SIZE)->head = 0;
  3211 
  3212       if (cp < m->least_addr)
  3213         m->least_addr = cp;
  3214       if ((m->footprint += newmmsize - oldmmsize) > m->max_footprint)
  3215         m->max_footprint = m->footprint;
  3216       check_mmapped_chunk(m, newp);
  3217       return newp;
  3218     }
  3219   }
  3220   return 0;
  3221 }
  3222 
  3223 /* -------------------------- mspace management -------------------------- */
  3224 
  3225 /* Initialize top chunk and its size */
  3226 static void init_top(mstate m, mchunkptr p, size_t psize) {
  3227   /* Ensure alignment */
  3228   size_t offset = align_offset(chunk2mem(p));
  3229   p = (mchunkptr)((char*)p + offset);
  3230   psize -= offset;
  3231 
  3232   m->top = p;
  3233   m->topsize = psize;
  3234   p->head = psize | PINUSE_BIT;
  3235   /* set size of fake trailing chunk holding overhead space only once */
  3236   chunk_plus_offset(p, psize)->head = TOP_FOOT_SIZE;
  3237   m->trim_check = mparams.trim_threshold; /* reset on each update */
  3238 }
  3239 
  3240 /* Initialize bins for a new mstate that is otherwise zeroed out */
  3241 static void init_bins(mstate m) {
  3242   /* Establish circular links for smallbins */
  3243   bindex_t i;
  3244   for (i = 0; i < NSMALLBINS; ++i) {
  3245     sbinptr bin = smallbin_at(m,i);
  3246     bin->fd = bin->bk = bin;
  3247   }
  3248 }
  3249 
  3250 #if PROCEED_ON_ERROR
  3251 
  3252 /* default corruption action */
  3253 static void reset_on_error(mstate m) {
  3254   int i;
  3255   ++malloc_corruption_error_count;
  3256   /* Reinitialize fields to forget about all memory */
  3257   m->smallbins = m->treebins = 0;
  3258   m->dvsize = m->topsize = 0;
  3259   m->seg.base = 0;
  3260   m->seg.size = 0;
  3261   m->seg.next = 0;
  3262   m->top = m->dv = 0;
  3263   for (i = 0; i < NTREEBINS; ++i)
  3264     *treebin_at(m, i) = 0;
  3265   init_bins(m);
  3266 }
  3267 #endif /* PROCEED_ON_ERROR */
  3268 
  3269 /* Allocate chunk and prepend remainder with chunk in successor base. */
  3270 static void* prepend_alloc(mstate m, char* newbase, char* oldbase,
  3271                            size_t nb) {
  3272   mchunkptr p = align_as_chunk(newbase);
  3273   mchunkptr oldfirst = align_as_chunk(oldbase);
  3274   size_t psize = (char*)oldfirst - (char*)p;
  3275   mchunkptr q = chunk_plus_offset(p, nb);
  3276   size_t qsize = psize - nb;
  3277   set_size_and_pinuse_of_inuse_chunk(m, p, nb);
  3278 
  3279   assert((char*)oldfirst > (char*)q);
  3280   assert(pinuse(oldfirst));
  3281   assert(qsize >= MIN_CHUNK_SIZE);
  3282 
  3283   /* consolidate remainder with first chunk of old base */
  3284   if (oldfirst == m->top) {
  3285     size_t tsize = m->topsize += qsize;
  3286     m->top = q;
  3287     q->head = tsize | PINUSE_BIT;
  3288     check_top_chunk(m, q);
  3289   }
  3290   else if (oldfirst == m->dv) {
  3291     size_t dsize = m->dvsize += qsize;
  3292     m->dv = q;
  3293     set_size_and_pinuse_of_free_chunk(q, dsize);
  3294   }
  3295   else {
  3296     if (!cinuse(oldfirst)) {
  3297       size_t nsize = chunksize(oldfirst);
  3298       unlink_chunk(m, oldfirst, nsize);
  3299       oldfirst = chunk_plus_offset(oldfirst, nsize);
  3300       qsize += nsize;
  3301     }
  3302     set_free_with_pinuse(q, qsize, oldfirst);
  3303     insert_chunk(m, q, qsize);
  3304     check_free_chunk(m, q);
  3305   }
  3306 
  3307   check_malloced_chunk(m, chunk2mem(p), nb);
  3308   return chunk2mem(p);
  3309 }
  3310 
  3311 
  3312 /* Add a segment to hold a new noncontiguous region */
  3313 static void add_segment(mstate m, char* tbase, size_t tsize, flag_t mmapped) {
  3314   /* Determine locations and sizes of segment, fenceposts, old top */
  3315   char* old_top = (char*)m->top;
  3316   msegmentptr oldsp = segment_holding(m, old_top);
  3317   char* old_end = oldsp->base + oldsp->size;
  3318   size_t ssize = pad_request(sizeof(struct malloc_segment));
  3319   char* rawsp = old_end - (ssize + FOUR_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
  3320   size_t offset = align_offset(chunk2mem(rawsp));
  3321   char* asp = rawsp + offset;
  3322   char* csp = (asp < (old_top + MIN_CHUNK_SIZE))? old_top : asp;
  3323   mchunkptr sp = (mchunkptr)csp;
  3324   msegmentptr ss = (msegmentptr)(chunk2mem(sp));
  3325   mchunkptr tnext = chunk_plus_offset(sp, ssize);
  3326   mchunkptr p = tnext;
  3327   int nfences = 0;
  3328 
  3329   /* reset top to new space */
  3330   init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE);
  3331 
  3332   /* Set up segment record */
  3333   assert(is_aligned(ss));
  3334   set_size_and_pinuse_of_inuse_chunk(m, sp, ssize);
  3335   *ss = m->seg; /* Push current record */
  3336   m->seg.base = tbase;
  3337   m->seg.size = tsize;
  3338   m->seg.sflags = mmapped;
  3339   m->seg.next = ss;
  3340 
  3341   /* Insert trailing fenceposts */
  3342   for (;;) {
  3343     mchunkptr nextp = chunk_plus_offset(p, SIZE_T_SIZE);
  3344     p->head = FENCEPOST_HEAD;
  3345     ++nfences;
  3346     if ((char*)(&(nextp->head)) < old_end)
  3347       p = nextp;
  3348     else
  3349       break;
  3350   }
  3351   assert(nfences >= 2);
  3352 
  3353   /* Insert the rest of old top into a bin as an ordinary free chunk */
  3354   if (csp != old_top) {
  3355     mchunkptr q = (mchunkptr)old_top;
  3356     size_t psize = csp - old_top;
  3357     mchunkptr tn = chunk_plus_offset(q, psize);
  3358     set_free_with_pinuse(q, psize, tn);
  3359     insert_chunk(m, q, psize);
  3360   }
  3361 
  3362   check_top_chunk(m, m->top);
  3363 }
  3364 
  3365 /* -------------------------- System allocation -------------------------- */
  3366 
  3367 /* Get memory from system using MORECORE or MMAP */
  3368 static void* sys_alloc(mstate m, size_t nb) {
  3369   char* tbase = CMFAIL;
  3370   size_t tsize = 0;
  3371   flag_t mmap_flag = 0;
  3372 
  3373   init_mparams();
  3374 
  3375   /* Directly map large chunks */
  3376   if (use_mmap(m) && nb >= mparams.mmap_threshold) {
  3377     void* mem = mmap_alloc(m, nb);
  3378     if (mem != 0)
  3379       return mem;
  3380   }
  3381 
  3382   /*
  3383     Try getting memory in any of three ways (in most-preferred to
  3384     least-preferred order):
  3385     1. A call to MORECORE that can normally contiguously extend memory.
  3386        (disabled if not MORECORE_CONTIGUOUS or not HAVE_MORECORE or
  3387        or main space is mmapped or a previous contiguous call failed)
  3388     2. A call to MMAP new space (disabled if not HAVE_MMAP).
  3389        Note that under the default settings, if MORECORE is unable to
  3390        fulfill a request, and HAVE_MMAP is true, then mmap is
  3391        used as a noncontiguous system allocator. This is a useful backup
  3392        strategy for systems with holes in address spaces -- in this case
  3393        sbrk cannot contiguously expand the heap, but mmap may be able to
  3394        find space.
  3395     3. A call to MORECORE that cannot usually contiguously extend memory.
  3396        (disabled if not HAVE_MORECORE)
  3397   */
  3398 
  3399   if (MORECORE_CONTIGUOUS && !use_noncontiguous(m)) {
  3400     char* br = CMFAIL;
  3401     msegmentptr ss = (m->top == 0)? 0 : segment_holding(m, (char*)m->top);
  3402     size_t asize = 0;
  3403     ACQUIRE_MORECORE_LOCK();
  3404 
  3405     if (ss == 0) {  /* First time through or recovery */
  3406       char* base = (char*)CALL_MORECORE(0);
  3407       if (base != CMFAIL) {
  3408         asize = granularity_align(nb + TOP_FOOT_SIZE + SIZE_T_ONE);
  3409         /* Adjust to end on a page boundary */
  3410         if (!is_page_aligned(base))
  3411           asize += (page_align((size_t)base) - (size_t)base);
  3412         /* Can't call MORECORE if size is negative when treated as signed */
  3413         if (asize < HALF_MAX_SIZE_T &&
  3414             (br = (char*)(CALL_MORECORE(asize))) == base) {
  3415           tbase = base;
  3416           tsize = asize;
  3417         }
  3418       }
  3419     }
  3420     else {
  3421       /* Subtract out existing available top space from MORECORE request. */
  3422       asize = granularity_align(nb - m->topsize + TOP_FOOT_SIZE + SIZE_T_ONE);
  3423       /* Use mem here only if it did continuously extend old space */
  3424       if (asize < HALF_MAX_SIZE_T &&
  3425           (br = (char*)(CALL_MORECORE(asize))) == ss->base+ss->size) {
  3426         tbase = br;
  3427         tsize = asize;
  3428       }
  3429     }
  3430 
  3431     if (tbase == CMFAIL) {    /* Cope with partial failure */
  3432       if (br != CMFAIL) {    /* Try to use/extend the space we did get */
  3433         if (asize < HALF_MAX_SIZE_T &&
  3434             asize < nb + TOP_FOOT_SIZE + SIZE_T_ONE) {
  3435           size_t esize = granularity_align(nb + TOP_FOOT_SIZE + SIZE_T_ONE - asize);
  3436           if (esize < HALF_MAX_SIZE_T) {
  3437             char* end = (char*)CALL_MORECORE(esize);
  3438             if (end != CMFAIL)
  3439               asize += esize;
  3440             else {            /* Can't use; try to release */
  3441               end = (char*)CALL_MORECORE(-asize);
  3442               br = CMFAIL;
  3443             }
  3444           }
  3445         }
  3446       }
  3447       if (br != CMFAIL) {    /* Use the space we did get */
  3448         tbase = br;
  3449         tsize = asize;
  3450       }
  3451       else
  3452         disable_contiguous(m); /* Don't try contiguous path in the future */
  3453     }
  3454 
  3455     RELEASE_MORECORE_LOCK();
  3456   }
  3457 
  3458   if (HAVE_MMAP && tbase == CMFAIL) {  /* Try MMAP */
  3459     size_t req = nb + TOP_FOOT_SIZE + SIZE_T_ONE;
  3460     size_t rsize = granularity_align(req);
  3461     if (rsize > nb) { /* Fail if wraps around zero */
  3462       char* mp = (char*)(CALL_MMAP(rsize));
  3463       if (mp != CMFAIL) {
  3464         tbase = mp;
  3465         tsize = rsize;
  3466         mmap_flag = IS_MMAPPED_BIT;
  3467       }
  3468     }
  3469   }
  3470 
  3471   if (HAVE_MORECORE && tbase == CMFAIL) { /* Try noncontiguous MORECORE */
  3472     size_t asize = granularity_align(nb + TOP_FOOT_SIZE + SIZE_T_ONE);
  3473     if (asize < HALF_MAX_SIZE_T) {
  3474       char* br = CMFAIL;
  3475       char* end = CMFAIL;
  3476       ACQUIRE_MORECORE_LOCK();
  3477       br = (char*)(CALL_MORECORE(asize));
  3478       end = (char*)(CALL_MORECORE(0));
  3479       RELEASE_MORECORE_LOCK();
  3480       if (br != CMFAIL && end != CMFAIL && br < end) {
  3481         size_t ssize = end - br;
  3482         if (ssize > nb + TOP_FOOT_SIZE) {
  3483           tbase = br;
  3484           tsize = ssize;
  3485         }
  3486       }
  3487     }
  3488   }
  3489 
  3490   if (tbase != CMFAIL) {
  3491 
  3492     if ((m->footprint += tsize) > m->max_footprint)
  3493       m->max_footprint = m->footprint;
  3494 
  3495     if (!is_initialized(m)) { /* first-time initialization */
  3496       m->seg.base = m->least_addr = tbase;
  3497       m->seg.size = tsize;
  3498       m->seg.sflags = mmap_flag;
  3499       m->magic = mparams.magic;
  3500       init_bins(m);
  3501       if (is_global(m)) 
  3502         init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE);
  3503       else {
  3504         /* Offset top by embedded malloc_state */
  3505         mchunkptr mn = next_chunk(mem2chunk(m));
  3506         init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) -TOP_FOOT_SIZE);
  3507       }
  3508     }
  3509 
  3510     else {
  3511       /* Try to merge with an existing segment */
  3512       msegmentptr sp = &m->seg;
  3513       while (sp != 0 && tbase != sp->base + sp->size)
  3514         sp = sp->next;
  3515       if (sp != 0 &&
  3516           !is_extern_segment(sp) &&
  3517           (sp->sflags & IS_MMAPPED_BIT) == mmap_flag &&
  3518           segment_holds(sp, m->top)) { /* append */
  3519         sp->size += tsize;
  3520         init_top(m, m->top, m->topsize + tsize);
  3521       }
  3522       else {
  3523         if (tbase < m->least_addr)
  3524           m->least_addr = tbase;
  3525         sp = &m->seg;
  3526         while (sp != 0 && sp->base != tbase + tsize)
  3527           sp = sp->next;
  3528         if (sp != 0 &&
  3529             !is_extern_segment(sp) &&
  3530             (sp->sflags & IS_MMAPPED_BIT) == mmap_flag) {
  3531           char* oldbase = sp->base;
  3532           sp->base = tbase;
  3533           sp->size += tsize;
  3534           return prepend_alloc(m, tbase, oldbase, nb);
  3535         }
  3536         else
  3537           add_segment(m, tbase, tsize, mmap_flag);
  3538       }
  3539     }
  3540 
  3541     if (nb < m->topsize) { /* Allocate from new or extended top space */
  3542       size_t rsize = m->topsize -= nb;
  3543       mchunkptr p = m->top;
  3544       mchunkptr r = m->top = chunk_plus_offset(p, nb);
  3545       r->head = rsize | PINUSE_BIT;
  3546       set_size_and_pinuse_of_inuse_chunk(m, p, nb);
  3547       check_top_chunk(m, m->top);
  3548       check_malloced_chunk(m, chunk2mem(p), nb);
  3549       return chunk2mem(p);
  3550     }
  3551   }
  3552 
  3553   MALLOC_FAILURE_ACTION;
  3554   return 0;
  3555 }
  3556 
  3557 /* -----------------------  system deallocation -------------------------- */
  3558 
  3559 /* Unmap and unlink any mmapped segments that don't contain used chunks */
  3560 static size_t release_unused_segments(mstate m) {
  3561   size_t released = 0;
  3562   msegmentptr pred = &m->seg;
  3563   msegmentptr sp = pred->next;
  3564   while (sp != 0) {
  3565     char* base = sp->base;
  3566     size_t size = sp->size;
  3567     msegmentptr next = sp->next;
  3568     if (is_mmapped_segment(sp) && !is_extern_segment(sp)) {
  3569       mchunkptr p = align_as_chunk(base);
  3570       size_t psize = chunksize(p);
  3571       /* Can unmap if first chunk holds entire segment and not pinned */
  3572       if (!cinuse(p) && (char*)p + psize >= base + size - TOP_FOOT_SIZE) {
  3573         tchunkptr tp = (tchunkptr)p;
  3574         assert(segment_holds(sp, (char*)sp));
  3575         if (p == m->dv) {
  3576           m->dv = 0;
  3577           m->dvsize = 0;
  3578         }
  3579         else {
  3580           unlink_large_chunk(m, tp);
  3581         }
  3582         if (CALL_MUNMAP(base, size) == 0) {
  3583           released += size;
  3584           m->footprint -= size;
  3585           /* unlink obsoleted record */
  3586           sp = pred;
  3587           sp->next = next;
  3588         }
  3589         else { /* back out if cannot unmap */
  3590           insert_large_chunk(m, tp, psize);
  3591         }
  3592       }
  3593     }
  3594     pred = sp;
  3595     sp = next;
  3596   }
  3597   return released;
  3598 }
  3599 
  3600 static int sys_trim(mstate m, size_t pad) {
  3601   size_t released = 0;
  3602   if (pad < MAX_REQUEST && is_initialized(m)) {
  3603     pad += TOP_FOOT_SIZE; /* ensure enough room for segment overhead */
  3604 
  3605     if (m->topsize > pad) {
  3606       /* Shrink top space in granularity-size units, keeping at least one */
  3607       size_t unit = mparams.granularity;
  3608       size_t extra = ((m->topsize - pad + (unit - SIZE_T_ONE)) / unit -
  3609                       SIZE_T_ONE) * unit;
  3610       msegmentptr sp = segment_holding(m, (char*)m->top);
  3611 
  3612       if (!is_extern_segment(sp)) {
  3613         if (is_mmapped_segment(sp)) {
  3614           if (HAVE_MMAP &&
  3615               sp->size >= extra &&
  3616               !has_segment_link(m, sp)) { /* can't shrink if pinned */
  3617             size_t newsize = sp->size - extra;
  3618             /* Prefer mremap, fall back to munmap */
  3619             if ((CALL_MREMAP(sp->base, sp->size, newsize, 0) != MFAIL) ||
  3620                 (CALL_MUNMAP(sp->base + newsize, extra) == 0)) {
  3621               released = extra;
  3622             }
  3623           }
  3624         }
  3625         else if (HAVE_MORECORE) {
  3626           if (extra >= HALF_MAX_SIZE_T) /* Avoid wrapping negative */
  3627             extra = (HALF_MAX_SIZE_T) + SIZE_T_ONE - unit;
  3628           ACQUIRE_MORECORE_LOCK();
  3629           {
  3630             /* Make sure end of memory is where we last set it. */
  3631             char* old_br = (char*)(CALL_MORECORE(0));
  3632             if (old_br == sp->base + sp->size) {
  3633               char* rel_br = (char*)(CALL_MORECORE(-extra));
  3634               char* new_br = (char*)(CALL_MORECORE(0));
  3635               if (rel_br != CMFAIL && new_br < old_br)
  3636                 released = old_br - new_br;
  3637             }
  3638           }
  3639           RELEASE_MORECORE_LOCK();
  3640         }
  3641       }
  3642 
  3643       if (released != 0) {
  3644         sp->size -= released;
  3645         m->footprint -= released;
  3646         init_top(m, m->top, m->topsize - released);
  3647         check_top_chunk(m, m->top);
  3648       }
  3649     }
  3650 
  3651     /* Unmap any unused mmapped segments */
  3652     if (HAVE_MMAP) 
  3653       released += release_unused_segments(m);
  3654 
  3655     /* On failure, disable autotrim to avoid repeated failed future calls */
  3656     if (released == 0)
  3657       m->trim_check = MAX_SIZE_T;
  3658   }
  3659 
  3660   return (released != 0)? 1 : 0;
  3661 }
  3662 
  3663 /* ---------------------------- malloc support --------------------------- */
  3664 
  3665 /* allocate a large request from the best fitting chunk in a treebin */
  3666 static void* tmalloc_large(mstate m, size_t nb) {
  3667   tchunkptr v = 0;
  3668   size_t rsize = -nb; /* Unsigned negation */
  3669   tchunkptr t;
  3670   bindex_t idx;
  3671   compute_tree_index(nb, idx);
  3672 
  3673   if ((t = *treebin_at(m, idx)) != 0) {
  3674     /* Traverse tree for this bin looking for node with size == nb */
  3675     size_t sizebits = nb << leftshift_for_tree_index(idx);
  3676     tchunkptr rst = 0;  /* The deepest untaken right subtree */
  3677     for (;;) {
  3678       tchunkptr rt;
  3679       size_t trem = chunksize(t) - nb;
  3680       if (trem < rsize) {
  3681         v = t;
  3682         if ((rsize = trem) == 0)
  3683           break;
  3684       }
  3685       rt = t->child[1];
  3686       t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
  3687       if (rt != 0 && rt != t)
  3688         rst = rt;
  3689       if (t == 0) {
  3690         t = rst; /* set t to least subtree holding sizes > nb */
  3691         break;
  3692       }
  3693       sizebits <<= 1;
  3694     }
  3695   }
  3696 
  3697   if (t == 0 && v == 0) { /* set t to root of next non-empty treebin */
  3698     binmap_t leftbits = left_bits(idx2bit(idx)) & m->treemap;
  3699     if (leftbits != 0) {
  3700       bindex_t i;
  3701       binmap_t leastbit = least_bit(leftbits);
  3702       compute_bit2idx(leastbit, i);
  3703       t = *treebin_at(m, i);
  3704     }
  3705   }
  3706 
  3707   while (t != 0) { /* find smallest of tree or subtree */
  3708     size_t trem = chunksize(t) - nb;
  3709     if (trem < rsize) {
  3710       rsize = trem;
  3711       v = t;
  3712     }
  3713     t = leftmost_child(t);
  3714   }
  3715 
  3716   /*  If dv is a better fit, return 0 so malloc will use it */
  3717   if (v != 0 && rsize < (size_t)(m->dvsize - nb)) {
  3718     if (RTCHECK(ok_address(m, v))) { /* split */
  3719       mchunkptr r = chunk_plus_offset(v, nb);
  3720       assert(chunksize(v) == rsize + nb);
  3721       if (RTCHECK(ok_next(v, r))) {
  3722         unlink_large_chunk(m, v);
  3723         if (rsize < MIN_CHUNK_SIZE)
  3724           set_inuse_and_pinuse(m, v, (rsize + nb));
  3725         else {
  3726           set_size_and_pinuse_of_inuse_chunk(m, v, nb);
  3727           set_size_and_pinuse_of_free_chunk(r, rsize);
  3728           insert_chunk(m, r, rsize);
  3729         }
  3730         return chunk2mem(v);
  3731       }
  3732     }
  3733     CORRUPTION_ERROR_ACTION(m);
  3734   }
  3735   return 0;
  3736 }
  3737 
  3738 /* allocate a small request from the best fitting chunk in a treebin */
  3739 static void* tmalloc_small(mstate m, size_t nb) {
  3740   tchunkptr t, v;
  3741   size_t rsize;
  3742   bindex_t i;
  3743   binmap_t leastbit = least_bit(m->treemap);
  3744   compute_bit2idx(leastbit, i);
  3745 
  3746   v = t = *treebin_at(m, i);
  3747   rsize = chunksize(t) - nb;
  3748 
  3749   while ((t = leftmost_child(t)) != 0) {
  3750     size_t trem = chunksize(t) - nb;
  3751     if (trem < rsize) {
  3752       rsize = trem;
  3753       v = t;
  3754     }
  3755   }
  3756 
  3757   if (RTCHECK(ok_address(m, v))) {
  3758     mchunkptr r = chunk_plus_offset(v, nb);
  3759     assert(chunksize(v) == rsize + nb);
  3760     if (RTCHECK(ok_next(v, r))) {
  3761       unlink_large_chunk(m, v);
  3762       if (rsize < MIN_CHUNK_SIZE)
  3763         set_inuse_and_pinuse(m, v, (rsize + nb));
  3764       else {
  3765         set_size_and_pinuse_of_inuse_chunk(m, v, nb);
  3766         set_size_and_pinuse_of_free_chunk(r, rsize);
  3767         replace_dv(m, r, rsize);
  3768       }
  3769       return chunk2mem(v);
  3770     }
  3771   }
  3772 
  3773   CORRUPTION_ERROR_ACTION(m);
  3774   return 0;
  3775 }
  3776 
  3777 /* --------------------------- realloc support --------------------------- */
  3778 
  3779 static void* internal_realloc(mstate m, void* oldmem, size_t bytes) {
  3780   if (bytes >= MAX_REQUEST) {
  3781     MALLOC_FAILURE_ACTION;
  3782     return 0;
  3783   }
  3784   if (!PREACTION(m)) {
  3785     mchunkptr oldp = mem2chunk(oldmem);
  3786     size_t oldsize = chunksize(oldp);
  3787     mchunkptr next = chunk_plus_offset(oldp, oldsize);
  3788     mchunkptr newp = 0;
  3789     void* extra = 0;
  3790 
  3791     /* Try to either shrink or extend into top. Else malloc-copy-free */
  3792 
  3793     if (RTCHECK(ok_address(m, oldp) && ok_cinuse(oldp) &&
  3794                 ok_next(oldp, next) && ok_pinuse(next))) {
  3795       size_t nb = request2size(bytes);
  3796       if (is_mmapped(oldp))
  3797         newp = mmap_resize(m, oldp, nb);
  3798       else if (oldsize >= nb) { /* already big enough */
  3799         size_t rsize = oldsize - nb;
  3800         newp = oldp;
  3801         if (rsize >= MIN_CHUNK_SIZE) {
  3802           mchunkptr remainder = chunk_plus_offset(newp, nb);
  3803           set_inuse(m, newp, nb);
  3804           set_inuse(m, remainder, rsize);
  3805           extra = chunk2mem(remainder);
  3806         }
  3807       }
  3808       else if (next == m->top && oldsize + m->topsize > nb) {
  3809         /* Expand into top */
  3810         size_t newsize = oldsize + m->topsize;
  3811         size_t newtopsize = newsize - nb;
  3812         mchunkptr newtop = chunk_plus_offset(oldp, nb);
  3813         set_inuse(m, oldp, nb);
  3814         newtop->head = newtopsize |PINUSE_BIT;
  3815         m->top = newtop;
  3816         m->topsize = newtopsize;
  3817         newp = oldp;
  3818       }
  3819     }
  3820     else {
  3821       USAGE_ERROR_ACTION(m, oldmem);
  3822       POSTACTION(m);
  3823       return 0;
  3824     }
  3825 
  3826     POSTACTION(m);
  3827 
  3828     if (newp != 0) {
  3829       if (extra != 0) {
  3830         internal_free(m, extra);
  3831       }
  3832       check_inuse_chunk(m, newp);
  3833       return chunk2mem(newp);
  3834     }
  3835     else {
  3836       void* newmem = internal_malloc(m, bytes);
  3837       if (newmem != 0) {
  3838         size_t oc = oldsize - overhead_for(oldp);
  3839         memcpy(newmem, oldmem, (oc < bytes)? oc : bytes);
  3840         internal_free(m, oldmem);
  3841       }
  3842       return newmem;
  3843     }
  3844   }
  3845   return 0;
  3846 }
  3847 
  3848 /* --------------------------- memalign support -------------------------- */
  3849 
  3850 static void* internal_memalign(mstate m, size_t alignment, size_t bytes) {
  3851   if (alignment <= MALLOC_ALIGNMENT)    /* Can just use malloc */
  3852     return internal_malloc(m, bytes);
  3853   if (alignment <  MIN_CHUNK_SIZE) /* must be at least a minimum chunk size */
  3854     alignment = MIN_CHUNK_SIZE;
  3855   if ((alignment & (alignment-SIZE_T_ONE)) != 0) {/* Ensure a power of 2 */
  3856     size_t a = MALLOC_ALIGNMENT << 1;
  3857     while (a < alignment) a <<= 1;
  3858     alignment = a;
  3859   }
  3860   
  3861   if (bytes >= MAX_REQUEST - alignment) {
  3862     if (m != 0)  { /* Test isn't needed but avoids compiler warning */
  3863       MALLOC_FAILURE_ACTION;
  3864     }
  3865   }
  3866   else {
  3867     size_t nb = request2size(bytes);
  3868     size_t req = nb + alignment + MIN_CHUNK_SIZE - CHUNK_OVERHEAD;
  3869     char* mem = (char*)internal_malloc(m, req);
  3870     if (mem != 0) {
  3871       void* leader = 0;
  3872       void* trailer = 0;
  3873       mchunkptr p = mem2chunk(mem);
  3874 
  3875       if (PREACTION(m)) return 0;
  3876       if ((((size_t)(mem)) % alignment) != 0) { /* misaligned */
  3877         /*
  3878           Find an aligned spot inside chunk.  Since we need to give
  3879           back leading space in a chunk of at least MIN_CHUNK_SIZE, if
  3880           the first calculation places us at a spot with less than
  3881           MIN_CHUNK_SIZE leader, we can move to the next aligned spot.
  3882           We've allocated enough total room so that this is always
  3883           possible.
  3884         */
  3885         char* br = (char*)mem2chunk((size_t)(((size_t)(mem +
  3886                                                        alignment -
  3887                                                        SIZE_T_ONE)) &
  3888                                              -alignment));
  3889         char* pos = ((size_t)(br - (char*)(p)) >= MIN_CHUNK_SIZE)?
  3890           br : br+alignment;
  3891         mchunkptr newp = (mchunkptr)pos;
  3892         size_t leadsize = pos - (char*)(p);
  3893         size_t newsize = chunksize(p) - leadsize;
  3894 
  3895         if (is_mmapped(p)) { /* For mmapped chunks, just adjust offset */
  3896           newp->prev_foot = p->prev_foot + leadsize;
  3897           newp->head = (newsize|CINUSE_BIT);
  3898         }
  3899         else { /* Otherwise, give back leader, use the rest */
  3900           set_inuse(m, newp, newsize);
  3901           set_inuse(m, p, leadsize);
  3902           leader = chunk2mem(p);
  3903         }
  3904         p = newp;
  3905       }
  3906 
  3907       /* Give back spare room at the end */
  3908       if (!is_mmapped(p)) {
  3909         size_t size = chunksize(p);
  3910         if (size > nb + MIN_CHUNK_SIZE) {
  3911           size_t remainder_size = size - nb;
  3912           mchunkptr remainder = chunk_plus_offset(p, nb);
  3913           set_inuse(m, p, nb);
  3914           set_inuse(m, remainder, remainder_size);
  3915           trailer = chunk2mem(remainder);
  3916         }
  3917       }
  3918 
  3919       assert (chunksize(p) >= nb);
  3920       assert((((size_t)(chunk2mem(p))) % alignment) == 0);
  3921       check_inuse_chunk(m, p);
  3922       POSTACTION(m);
  3923       if (leader != 0) {
  3924         internal_free(m, leader);
  3925       }
  3926       if (trailer != 0) {
  3927         internal_free(m, trailer);
  3928       }
  3929       return chunk2mem(p);
  3930     }
  3931   }
  3932   return 0;
  3933 }
  3934 
  3935 /* ------------------------ comalloc/coalloc support --------------------- */
  3936 
  3937 static void** ialloc(mstate m,
  3938                      size_t n_elements,
  3939                      size_t* sizes,
  3940                      int opts,
  3941                      void* chunks[]) {
  3942   /*
  3943     This provides common support for independent_X routines, handling
  3944     all of the combinations that can result.
  3945 
  3946     The opts arg has:
  3947     bit 0 set if all elements are same size (using sizes[0])
  3948     bit 1 set if elements should be zeroed
  3949   */
  3950 
  3951   size_t    element_size;   /* chunksize of each element, if all same */
  3952   size_t    contents_size;  /* total size of elements */
  3953   size_t    array_size;     /* request size of pointer array */
  3954   void*     mem;            /* malloced aggregate space */
  3955   mchunkptr p;              /* corresponding chunk */
  3956   size_t    remainder_size; /* remaining bytes while splitting */
  3957   void**    marray;         /* either "chunks" or malloced ptr array */
  3958   mchunkptr array_chunk;    /* chunk for malloced ptr array */
  3959   flag_t    was_enabled;    /* to disable mmap */
  3960   size_t    size;
  3961   size_t    i;
  3962 
  3963   /* compute array length, if needed */
  3964   if (chunks != 0) {
  3965     if (n_elements == 0)
  3966       return chunks; /* nothing to do */
  3967     marray = chunks;
  3968     array_size = 0;
  3969   }
  3970   else {
  3971     /* if empty req, must still return chunk representing empty array */
  3972     if (n_elements == 0)
  3973       return (void**)internal_malloc(m, 0);
  3974     marray = 0;
  3975     array_size = request2size(n_elements * (sizeof(void*)));
  3976   }
  3977 
  3978   /* compute total element size */
  3979   if (opts & 0x1) { /* all-same-size */
  3980     element_size = request2size(*sizes);
  3981     contents_size = n_elements * element_size;
  3982   }
  3983   else { /* add up all the sizes */
  3984     element_size = 0;
  3985     contents_size = 0;
  3986     for (i = 0; i != n_elements; ++i)
  3987       contents_size += request2size(sizes[i]);
  3988   }
  3989 
  3990   size = contents_size + array_size;
  3991 
  3992   /*
  3993      Allocate the aggregate chunk.  First disable direct-mmapping so
  3994      malloc won't use it, since we would not be able to later
  3995      free/realloc space internal to a segregated mmap region.
  3996   */
  3997   was_enabled = use_mmap(m);
  3998   disable_mmap(m);
  3999   mem = internal_malloc(m, size - CHUNK_OVERHEAD);
  4000   if (was_enabled)
  4001     enable_mmap(m);
  4002   if (mem == 0)
  4003     return 0;
  4004 
  4005   if (PREACTION(m)) return 0;
  4006   p = mem2chunk(mem);
  4007   remainder_size = chunksize(p);
  4008 
  4009   assert(!is_mmapped(p));
  4010 
  4011   if (opts & 0x2) {       /* optionally clear the elements */
  4012     memset((size_t*)mem, 0, remainder_size - SIZE_T_SIZE - array_size);
  4013   }
  4014 
  4015   /* If not provided, allocate the pointer array as final part of chunk */
  4016   if (marray == 0) {
  4017     size_t  array_chunk_size;
  4018     array_chunk = chunk_plus_offset(p, contents_size);
  4019     array_chunk_size = remainder_size - contents_size;
  4020     marray = (void**) (chunk2mem(array_chunk));
  4021     set_size_and_pinuse_of_inuse_chunk(m, array_chunk, array_chunk_size);
  4022     remainder_size = contents_size;
  4023   }
  4024 
  4025   /* split out elements */
  4026   for (i = 0; ; ++i) {
  4027     marray[i] = chunk2mem(p);
  4028     if (i != n_elements-1) {
  4029       if (element_size != 0)
  4030         size = element_size;
  4031       else
  4032         size = request2size(sizes[i]);
  4033       remainder_size -= size;
  4034       set_size_and_pinuse_of_inuse_chunk(m, p, size);
  4035       p = chunk_plus_offset(p, size);
  4036     }
  4037     else { /* the final element absorbs any overallocation slop */
  4038       set_size_and_pinuse_of_inuse_chunk(m, p, remainder_size);
  4039       break;
  4040     }
  4041   }
  4042 
  4043 #if DEBUG
  4044   if (marray != chunks) {
  4045     /* final element must have exactly exhausted chunk */
  4046     if (element_size != 0) {
  4047       assert(remainder_size == element_size);
  4048     }
  4049     else {
  4050       assert(remainder_size == request2size(sizes[i]));
  4051     }
  4052     check_inuse_chunk(m, mem2chunk(marray));
  4053   }
  4054   for (i = 0; i != n_elements; ++i)
  4055     check_inuse_chunk(m, mem2chunk(marray[i]));
  4056 
  4057 #endif /* DEBUG */
  4058 
  4059   POSTACTION(m);
  4060   return marray;
  4061 }
  4062 
  4063 
  4064 /* -------------------------- public routines ---------------------------- */
  4065 
  4066 #if !ONLY_MSPACES
  4067 
  4068 void* dlmalloc(size_t bytes) {
  4069   /*
  4070      Basic algorithm:
  4071      If a small request (< 256 bytes minus per-chunk overhead):
  4072        1. If one exists, use a remainderless chunk in associated smallbin.
  4073           (Remainderless means that there are too few excess bytes to
  4074           represent as a chunk.)
  4075        2. If it is big enough, use the dv chunk, which is normally the
  4076           chunk adjacent to the one used for the most recent small request.
  4077        3. If one exists, split the smallest available chunk in a bin,
  4078           saving remainder in dv.
  4079        4. If it is big enough, use the top chunk.
  4080        5. If available, get memory from system and use it
  4081      Otherwise, for a large request:
  4082        1. Find the smallest available binned chunk that fits, and use it
  4083           if it is better fitting than dv chunk, splitting if necessary.
  4084        2. If better fitting than any binned chunk, use the dv chunk.
  4085        3. If it is big enough, use the top chunk.
  4086        4. If request size >= mmap threshold, try to directly mmap this chunk.
  4087        5. If available, get memory from system and use it
  4088 
  4089      The ugly goto's here ensure that postaction occurs along all paths.
  4090   */
  4091 
  4092   if (!PREACTION(gm)) {
  4093     void* mem;
  4094     size_t nb;
  4095     if (bytes <= MAX_SMALL_REQUEST) {
  4096       bindex_t idx;
  4097       binmap_t smallbits;
  4098       nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes);
  4099       idx = small_index(nb);
  4100       smallbits = gm->smallmap >> idx;
  4101 
  4102       if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */
  4103         mchunkptr b, p;
  4104         idx += ~smallbits & 1;       /* Uses next bin if idx empty */
  4105         b = smallbin_at(gm, idx);
  4106         p = b->fd;
  4107         assert(chunksize(p) == small_index2size(idx));
  4108         unlink_first_small_chunk(gm, b, p, idx);
  4109         set_inuse_and_pinuse(gm, p, small_index2size(idx));
  4110         mem = chunk2mem(p);
  4111         check_malloced_chunk(gm, mem, nb);
  4112         goto postaction;
  4113       }
  4114 
  4115       else if (nb > gm->dvsize) {
  4116         if (smallbits != 0) { /* Use chunk in next nonempty smallbin */
  4117           mchunkptr b, p, r;
  4118           size_t rsize;
  4119           bindex_t i;
  4120           binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));
  4121           binmap_t leastbit = least_bit(leftbits);
  4122           compute_bit2idx(leastbit, i);
  4123           b = smallbin_at(gm, i);
  4124           p = b->fd;
  4125           assert(chunksize(p) == small_index2size(i));
  4126           unlink_first_small_chunk(gm, b, p, i);
  4127           rsize = small_index2size(i) - nb;
  4128           /* Fit here cannot be remainderless if 4byte sizes */
  4129           if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE)
  4130             set_inuse_and_pinuse(gm, p, small_index2size(i));
  4131           else {
  4132             set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
  4133             r = chunk_plus_offset(p, nb);
  4134             set_size_and_pinuse_of_free_chunk(r, rsize);
  4135             replace_dv(gm, r, rsize);
  4136           }
  4137           mem = chunk2mem(p);
  4138           check_malloced_chunk(gm, mem, nb);
  4139           goto postaction;
  4140         }
  4141 
  4142         else if (gm->treemap != 0 && (mem = tmalloc_small(gm, nb)) != 0) {
  4143           check_malloced_chunk(gm, mem, nb);
  4144           goto postaction;
  4145         }
  4146       }
  4147     }
  4148     else if (bytes >= MAX_REQUEST)
  4149       nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */
  4150     else {
  4151       nb = pad_request(bytes);
  4152       if (gm->treemap != 0 && (mem = tmalloc_large(gm, nb)) != 0) {
  4153         check_malloced_chunk(gm, mem, nb);
  4154         goto postaction;
  4155       }
  4156     }
  4157 
  4158     if (nb <= gm->dvsize) {
  4159       size_t rsize = gm->dvsize - nb;
  4160       mchunkptr p = gm->dv;
  4161       if (rsize >= MIN_CHUNK_SIZE) { /* split dv */
  4162         mchunkptr r = gm->dv = chunk_plus_offset(p, nb);
  4163         gm->dvsize = rsize;
  4164         set_size_and_pinuse_of_free_chunk(r, rsize);
  4165         set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
  4166       }
  4167       else { /* exhaust dv */
  4168         size_t dvs = gm->dvsize;
  4169         gm->dvsize = 0;
  4170         gm->dv = 0;
  4171         set_inuse_and_pinuse(gm, p, dvs);
  4172       }
  4173       mem = chunk2mem(p);
  4174       check_malloced_chunk(gm, mem, nb);
  4175       goto postaction;
  4176     }
  4177 
  4178     else if (nb < gm->topsize) { /* Split top */
  4179       size_t rsize = gm->topsize -= nb;
  4180       mchunkptr p = gm->top;
  4181       mchunkptr r = gm->top = chunk_plus_offset(p, nb);
  4182       r->head = rsize | PINUSE_BIT;
  4183       set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
  4184       mem = chunk2mem(p);
  4185       check_top_chunk(gm, gm->top);
  4186       check_malloced_chunk(gm, mem, nb);
  4187       goto postaction;
  4188     }
  4189 
  4190     mem = sys_alloc(gm, nb);
  4191 
  4192   postaction:
  4193     POSTACTION(gm);
  4194     return mem;
  4195   }
  4196 
  4197   return 0;
  4198 }
  4199 
  4200 void dlfree(void* mem) {
  4201   /*
  4202      Consolidate freed chunks with preceeding or succeeding bordering
  4203      free chunks, if they exist, and then place in a bin.  Intermixed
  4204      with special cases for top, dv, mmapped chunks, and usage errors.
  4205   */
  4206 
  4207   if (mem != 0) {
  4208     mchunkptr p  = mem2chunk(mem);
  4209 #if FOOTERS
  4210     mstate fm = get_mstate_for(p);
  4211     if (!ok_magic(fm)) {
  4212       USAGE_ERROR_ACTION(fm, p);
  4213       return;
  4214     }
  4215 #else /* FOOTERS */
  4216 #define fm gm
  4217 #endif /* FOOTERS */
  4218     if (!PREACTION(fm)) {
  4219       check_inuse_chunk(fm, p);
  4220       if (RTCHECK(ok_address(fm, p) && ok_cinuse(p))) {
  4221         size_t psize = chunksize(p);
  4222         mchunkptr next = chunk_plus_offset(p, psize);
  4223         if (!pinuse(p)) {
  4224           size_t prevsize = p->prev_foot;
  4225           if ((prevsize & IS_MMAPPED_BIT) != 0) {
  4226             prevsize &= ~IS_MMAPPED_BIT;
  4227             psize += prevsize + MMAP_FOOT_PAD;
  4228             if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)
  4229               fm->footprint -= psize;
  4230             goto postaction;
  4231           }
  4232           else {
  4233             mchunkptr prev = chunk_minus_offset(p, prevsize);
  4234             psize += prevsize;
  4235             p = prev;
  4236             if (RTCHECK(ok_address(fm, prev))) { /* consolidate backward */
  4237               if (p != fm->dv) {
  4238                 unlink_chunk(fm, p, prevsize);
  4239               }
  4240               else if ((next->head & INUSE_BITS) == INUSE_BITS) {
  4241                 fm->dvsize = psize;
  4242                 set_free_with_pinuse(p, psize, next);
  4243                 goto postaction;
  4244               }
  4245             }
  4246             else
  4247               goto erroraction;
  4248           }
  4249         }
  4250 
  4251         if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) {
  4252           if (!cinuse(next)) {  /* consolidate forward */
  4253             if (next == fm->top) {
  4254               size_t tsize = fm->topsize += psize;
  4255               fm->top = p;
  4256               p->head = tsize | PINUSE_BIT;
  4257               if (p == fm->dv) {
  4258                 fm->dv = 0;
  4259                 fm->dvsize = 0;
  4260               }
  4261               if (should_trim(fm, tsize))
  4262                 sys_trim(fm, 0);
  4263               goto postaction;
  4264             }
  4265             else if (next == fm->dv) {
  4266               size_t dsize = fm->dvsize += psize;
  4267               fm->dv = p;
  4268               set_size_and_pinuse_of_free_chunk(p, dsize);
  4269               goto postaction;
  4270             }
  4271             else {
  4272               size_t nsize = chunksize(next);
  4273               psize += nsize;
  4274               unlink_chunk(fm, next, nsize);
  4275               set_size_and_pinuse_of_free_chunk(p, psize);
  4276               if (p == fm->dv) {
  4277                 fm->dvsize = psize;
  4278                 goto postaction;
  4279               }
  4280             }
  4281           }
  4282           else
  4283             set_free_with_pinuse(p, psize, next);
  4284           insert_chunk(fm, p, psize);
  4285           check_free_chunk(fm, p);
  4286           goto postaction;
  4287         }
  4288       }
  4289     erroraction:
  4290       USAGE_ERROR_ACTION(fm, p);
  4291     postaction:
  4292       POSTACTION(fm);
  4293     }
  4294   }
  4295 #if !FOOTERS
  4296 #undef fm
  4297 #endif /* FOOTERS */
  4298 }
  4299 
  4300 void* dlcalloc(size_t n_elements, size_t elem_size) {
  4301   void* mem;
  4302   size_t req = 0;
  4303   if (n_elements != 0) {
  4304     req = n_elements * elem_size;
  4305     if (((n_elements | elem_size) & ~(size_t)0xffff) &&
  4306         (req / n_elements != elem_size))
  4307       req = MAX_SIZE_T; /* force downstream failure on overflow */
  4308   }
  4309   mem = dlmalloc(req);
  4310   if (mem != 0 && calloc_must_clear(mem2chunk(mem)))
  4311     memset(mem, 0, req);
  4312   return mem;
  4313 }
  4314 
  4315 void* dlrealloc(void* oldmem, size_t bytes) {
  4316   if (oldmem == 0)
  4317     return dlmalloc(bytes);
  4318 #ifdef REALLOC_ZERO_BYTES_FREES
  4319   if (bytes == 0) {
  4320     dlfree(oldmem);
  4321     return 0;
  4322   }
  4323 #endif /* REALLOC_ZERO_BYTES_FREES */
  4324   else {
  4325 #if ! FOOTERS
  4326     mstate m = gm;
  4327 #else /* FOOTERS */
  4328     mstate m = get_mstate_for(mem2chunk(oldmem));
  4329     if (!ok_magic(m)) {
  4330       USAGE_ERROR_ACTION(m, oldmem);
  4331       return 0;
  4332     }
  4333 #endif /* FOOTERS */
  4334     return internal_realloc(m, oldmem, bytes);
  4335   }
  4336 }
  4337 
  4338 void* dlmemalign(size_t alignment, size_t bytes) {
  4339   return internal_memalign(gm, alignment, bytes);
  4340 }
  4341 
  4342 void** dlindependent_calloc(size_t n_elements, size_t elem_size,
  4343                                  void* chunks[]) {
  4344   size_t sz = elem_size; /* serves as 1-element array */
  4345   return ialloc(gm, n_elements, &sz, 3, chunks);
  4346 }
  4347 
  4348 void** dlindependent_comalloc(size_t n_elements, size_t sizes[],
  4349                                    void* chunks[]) {
  4350   return ialloc(gm, n_elements, sizes, 0, chunks);
  4351 }
  4352 
  4353 void* dlvalloc(size_t bytes) {
  4354   size_t pagesz;
  4355   init_mparams();
  4356   pagesz = mparams.page_size;
  4357   return dlmemalign(pagesz, bytes);
  4358 }
  4359 
  4360 void* dlpvalloc(size_t bytes) {
  4361   size_t pagesz;
  4362   init_mparams();
  4363   pagesz = mparams.page_size;
  4364   return dlmemalign(pagesz, (bytes + pagesz - SIZE_T_ONE) & ~(pagesz - SIZE_T_ONE));
  4365 }
  4366 
  4367 int dlmalloc_trim(size_t pad) {
  4368   int result = 0;
  4369   if (!PREACTION(gm)) {
  4370     result = sys_trim(gm, pad);
  4371     POSTACTION(gm);
  4372   }
  4373   return result;
  4374 }
  4375 
  4376 size_t dlmalloc_footprint(void) {
  4377   return gm->footprint;
  4378 }
  4379 
  4380 size_t dlmalloc_max_footprint(void) {
  4381   return gm->max_footprint;
  4382 }
  4383 
  4384 #if !NO_MALLINFO
  4385 struct mallinfo dlmallinfo(void) {
  4386   return internal_mallinfo(gm);
  4387 }
  4388 #endif /* NO_MALLINFO */
  4389 
  4390 void dlmalloc_stats() {
  4391   internal_malloc_stats(gm);
  4392 }
  4393 
  4394 size_t dlmalloc_usable_size(void* mem) {
  4395   if (mem != 0) {
  4396     mchunkptr p = mem2chunk(mem);
  4397     if (cinuse(p))
  4398       return chunksize(p) - overhead_for(p);
  4399   }
  4400   return 0;
  4401 }
  4402 
  4403 int dlmallopt(int param_number, int value) {
  4404   return change_mparam(param_number, value);
  4405 }
  4406 
  4407 #endif /* !ONLY_MSPACES */
  4408 
  4409 /* ----------------------------- user mspaces ---------------------------- */
  4410 
  4411 #if MSPACES
  4412 
  4413 static mstate init_user_mstate(char* tbase, size_t tsize) {
  4414   size_t msize = pad_request(sizeof(struct malloc_state));
  4415   mchunkptr mn;
  4416   mchunkptr msp = align_as_chunk(tbase);
  4417   mstate m = (mstate)(chunk2mem(msp));
  4418   memset(m, 0, msize);
  4419   INITIAL_LOCK(&m->mutex);
  4420   msp->head = (msize|PINUSE_BIT|CINUSE_BIT);
  4421   m->seg.base = m->least_addr = tbase;
  4422   m->seg.size = m->footprint = m->max_footprint = tsize;
  4423   m->magic = mparams.magic;
  4424   m->mflags = mparams.default_mflags;
  4425   disable_contiguous(m);
  4426   init_bins(m);
  4427   mn = next_chunk(mem2chunk(m));
  4428   init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) - TOP_FOOT_SIZE);
  4429   check_top_chunk(m, m->top);
  4430   return m;
  4431 }
  4432 
  4433 mspace create_mspace(size_t capacity, int locked) {
  4434   mstate m = 0;
  4435   size_t msize = pad_request(sizeof(struct malloc_state));
  4436   init_mparams(); /* Ensure pagesize etc initialized */
  4437 
  4438   if (capacity < (size_t) -(msize + TOP_FOOT_SIZE + mparams.page_size)) {
  4439     size_t rs = ((capacity == 0)? mparams.granularity :
  4440                  (capacity + TOP_FOOT_SIZE + msize));
  4441     size_t tsize = granularity_align(rs);
  4442     char* tbase = (char*)(CALL_MMAP(tsize));
  4443     if (tbase != CMFAIL) {
  4444       m = init_user_mstate(tbase, tsize);
  4445       m->seg.sflags = IS_MMAPPED_BIT;
  4446       set_lock(m, locked);
  4447     }
  4448   }
  4449   return (mspace)m;
  4450 }
  4451 
  4452 mspace create_mspace_with_base(void* base, size_t capacity, int locked) {
  4453   mstate m = 0;
  4454   size_t msize = pad_request(sizeof(struct malloc_state));
  4455   init_mparams(); /* Ensure pagesize etc initialized */
  4456 
  4457   if (capacity > msize + TOP_FOOT_SIZE &&
  4458       capacity < (size_t) -(msize + TOP_FOOT_SIZE + mparams.page_size)) {
  4459     m = init_user_mstate((char*)base, capacity);
  4460     m->seg.sflags = EXTERN_BIT;
  4461     set_lock(m, locked);
  4462   }
  4463   return (mspace)m;
  4464 }
  4465 
  4466 size_t destroy_mspace(mspace msp) {
  4467   size_t freed = 0;
  4468   mstate ms = (mstate)msp;
  4469   if (ok_magic(ms)) {
  4470     msegmentptr sp = &ms->seg;
  4471     while (sp != 0) {
  4472       char* base = sp->base;
  4473       size_t size = sp->size;
  4474       flag_t flag = sp->sflags;
  4475       sp = sp->next;
  4476       if ((flag & IS_MMAPPED_BIT) && !(flag & EXTERN_BIT) &&
  4477           CALL_MUNMAP(base, size) == 0)
  4478         freed += size;
  4479     }
  4480   }
  4481   else {
  4482     USAGE_ERROR_ACTION(ms,ms);
  4483   }
  4484   return freed;
  4485 }
  4486 
  4487 /*
  4488   mspace versions of routines are near-clones of the global
  4489   versions. This is not so nice but better than the alternatives.
  4490 */
  4491 
  4492 
  4493 void* mspace_malloc(mspace msp, size_t bytes) {
  4494   mstate ms = (mstate)msp;
  4495   if (!ok_magic(ms)) {
  4496     USAGE_ERROR_ACTION(ms,ms);
  4497     return 0;
  4498   }
  4499   if (!PREACTION(ms)) {
  4500     void* mem;
  4501     size_t nb;
  4502     if (bytes <= MAX_SMALL_REQUEST) {
  4503       bindex_t idx;
  4504       binmap_t smallbits;
  4505       nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes);
  4506       idx = small_index(nb);
  4507       smallbits = ms->smallmap >> idx;
  4508 
  4509       if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */
  4510         mchunkptr b, p;
  4511         idx += ~smallbits & 1;       /* Uses next bin if idx empty */
  4512         b = smallbin_at(ms, idx);
  4513         p = b->fd;
  4514         assert(chunksize(p) == small_index2size(idx));
  4515         unlink_first_small_chunk(ms, b, p, idx);
  4516         set_inuse_and_pinuse(ms, p, small_index2size(idx));
  4517         mem = chunk2mem(p);
  4518         check_malloced_chunk(ms, mem, nb);
  4519         goto postaction;
  4520       }
  4521 
  4522       else if (nb > ms->dvsize) {
  4523         if (smallbits != 0) { /* Use chunk in next nonempty smallbin */
  4524           mchunkptr b, p, r;
  4525           size_t rsize;
  4526           bindex_t i;
  4527           binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));
  4528           binmap_t leastbit = least_bit(leftbits);
  4529           compute_bit2idx(leastbit, i);
  4530           b = smallbin_at(ms, i);
  4531           p = b->fd;
  4532           assert(chunksize(p) == small_index2size(i));
  4533           unlink_first_small_chunk(ms, b, p, i);
  4534           rsize = small_index2size(i) - nb;
  4535           /* Fit here cannot be remainderless if 4byte sizes */
  4536           if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE)
  4537             set_inuse_and_pinuse(ms, p, small_index2size(i));
  4538           else {
  4539             set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
  4540             r = chunk_plus_offset(p, nb);
  4541             set_size_and_pinuse_of_free_chunk(r, rsize);
  4542             replace_dv(ms, r, rsize);
  4543           }
  4544           mem = chunk2mem(p);
  4545           check_malloced_chunk(ms, mem, nb);
  4546           goto postaction;
  4547         }
  4548 
  4549         else if (ms->treemap != 0 && (mem = tmalloc_small(ms, nb)) != 0) {
  4550           check_malloced_chunk(ms, mem, nb);
  4551           goto postaction;
  4552         }
  4553       }
  4554     }
  4555     else if (bytes >= MAX_REQUEST)
  4556       nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */
  4557     else {
  4558       nb = pad_request(bytes);
  4559       if (ms->treemap != 0 && (mem = tmalloc_large(ms, nb)) != 0) {
  4560         check_malloced_chunk(ms, mem, nb);
  4561         goto postaction;
  4562       }
  4563     }
  4564 
  4565     if (nb <= ms->dvsize) {
  4566       size_t rsize = ms->dvsize - nb;
  4567       mchunkptr p = ms->dv;
  4568       if (rsize >= MIN_CHUNK_SIZE) { /* split dv */
  4569         mchunkptr r = ms->dv = chunk_plus_offset(p, nb);
  4570         ms->dvsize = rsize;
  4571         set_size_and_pinuse_of_free_chunk(r, rsize);
  4572         set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
  4573       }
  4574       else { /* exhaust dv */
  4575         size_t dvs = ms->dvsize;
  4576         ms->dvsize = 0;
  4577         ms->dv = 0;
  4578         set_inuse_and_pinuse(ms, p, dvs);
  4579       }
  4580       mem = chunk2mem(p);
  4581       check_malloced_chunk(ms, mem, nb);
  4582       goto postaction;
  4583     }
  4584 
  4585     else if (nb < ms->topsize) { /* Split top */
  4586       size_t rsize = ms->topsize -= nb;
  4587       mchunkptr p = ms->top;
  4588       mchunkptr r = ms->top = chunk_plus_offset(p, nb);
  4589       r->head = rsize | PINUSE_BIT;
  4590       set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
  4591       mem = chunk2mem(p);
  4592       check_top_chunk(ms, ms->top);
  4593       check_malloced_chunk(ms, mem, nb);
  4594       goto postaction;
  4595     }
  4596 
  4597     mem = sys_alloc(ms, nb);
  4598 
  4599   postaction:
  4600     POSTACTION(ms);
  4601     return mem;
  4602   }
  4603 
  4604   return 0;
  4605 }
  4606 
  4607 void mspace_free(mspace msp, void* mem) {
  4608   if (mem != 0) {
  4609     mchunkptr p  = mem2chunk(mem);
  4610 #if FOOTERS
  4611     mstate fm = get_mstate_for(p);
  4612 #else /* FOOTERS */
  4613     mstate fm = (mstate)msp;
  4614 #endif /* FOOTERS */
  4615     if (!ok_magic(fm)) {
  4616       USAGE_ERROR_ACTION(fm, p);
  4617       return;
  4618     }
  4619     if (!PREACTION(fm)) {
  4620       check_inuse_chunk(fm, p);
  4621       if (RTCHECK(ok_address(fm, p) && ok_cinuse(p))) {
  4622         size_t psize = chunksize(p);
  4623         mchunkptr next = chunk_plus_offset(p, psize);
  4624         if (!pinuse(p)) {
  4625           size_t prevsize = p->prev_foot;
  4626           if ((prevsize & IS_MMAPPED_BIT) != 0) {
  4627             prevsize &= ~IS_MMAPPED_BIT;
  4628             psize += prevsize + MMAP_FOOT_PAD;
  4629             if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)
  4630               fm->footprint -= psize;
  4631             goto postaction;
  4632           }
  4633           else {
  4634             mchunkptr prev = chunk_minus_offset(p, prevsize);
  4635             psize += prevsize;
  4636             p = prev;
  4637             if (RTCHECK(ok_address(fm, prev))) { /* consolidate backward */
  4638               if (p != fm->dv) {
  4639                 unlink_chunk(fm, p, prevsize);
  4640               }
  4641               else if ((next->head & INUSE_BITS) == INUSE_BITS) {
  4642                 fm->dvsize = psize;
  4643                 set_free_with_pinuse(p, psize, next);
  4644                 goto postaction;
  4645               }
  4646             }
  4647             else
  4648               goto erroraction;
  4649           }
  4650         }
  4651 
  4652         if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) {
  4653           if (!cinuse(next)) {  /* consolidate forward */
  4654             if (next == fm->top) {
  4655               size_t tsize = fm->topsize += psize;
  4656               fm->top = p;
  4657               p->head = tsize | PINUSE_BIT;
  4658               if (p == fm->dv) {
  4659                 fm->dv = 0;
  4660                 fm->dvsize = 0;
  4661               }
  4662               if (should_trim(fm, tsize))
  4663                 sys_trim(fm, 0);
  4664               goto postaction;
  4665             }
  4666             else if (next == fm->dv) {
  4667               size_t dsize = fm->dvsize += psize;
  4668               fm->dv = p;
  4669               set_size_and_pinuse_of_free_chunk(p, dsize);
  4670               goto postaction;
  4671             }
  4672             else {
  4673               size_t nsize = chunksize(next);
  4674               psize += nsize;
  4675               unlink_chunk(fm, next, nsize);
  4676               set_size_and_pinuse_of_free_chunk(p, psize);
  4677               if (p == fm->dv) {
  4678                 fm->dvsize = psize;
  4679                 goto postaction;
  4680               }
  4681             }
  4682           }
  4683           else
  4684             set_free_with_pinuse(p, psize, next);
  4685           insert_chunk(fm, p, psize);
  4686           check_free_chunk(fm, p);
  4687           goto postaction;
  4688         }
  4689       }
  4690     erroraction:
  4691       USAGE_ERROR_ACTION(fm, p);
  4692     postaction:
  4693       POSTACTION(fm);
  4694     }
  4695   }
  4696 }
  4697 
  4698 void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size) {
  4699   void* mem;
  4700   size_t req = 0;
  4701   mstate ms = (mstate)msp;
  4702   if (!ok_magic(ms)) {
  4703     USAGE_ERROR_ACTION(ms,ms);
  4704     return 0;
  4705   }
  4706   if (n_elements != 0) {
  4707     req = n_elements * elem_size;
  4708     if (((n_elements | elem_size) & ~(size_t)0xffff) &&
  4709         (req / n_elements != elem_size))
  4710       req = MAX_SIZE_T; /* force downstream failure on overflow */
  4711   }
  4712   mem = internal_malloc(ms, req);
  4713   if (mem != 0 && calloc_must_clear(mem2chunk(mem)))
  4714     memset(mem, 0, req);
  4715   return mem;
  4716 }
  4717 
  4718 void* mspace_realloc(mspace msp, void* oldmem, size_t bytes) {
  4719   if (oldmem == 0)
  4720     return mspace_malloc(msp, bytes);
  4721 #ifdef REALLOC_ZERO_BYTES_FREES
  4722   if (bytes == 0) {
  4723     mspace_free(msp, oldmem);
  4724     return 0;
  4725   }
  4726 #endif /* REALLOC_ZERO_BYTES_FREES */
  4727   else {
  4728 #if FOOTERS
  4729     mchunkptr p  = mem2chunk(oldmem);
  4730     mstate ms = get_mstate_for(p);
  4731 #else /* FOOTERS */
  4732     mstate ms = (mstate)msp;
  4733 #endif /* FOOTERS */
  4734     if (!ok_magic(ms)) {
  4735       USAGE_ERROR_ACTION(ms,ms);
  4736       return 0;
  4737     }
  4738     return internal_realloc(ms, oldmem, bytes);
  4739   }
  4740 }
  4741 
  4742 void* mspace_memalign(mspace msp, size_t alignment, size_t bytes) {
  4743   mstate ms = (mstate)msp;
  4744   if (!ok_magic(ms)) {
  4745     USAGE_ERROR_ACTION(ms,ms);
  4746     return 0;
  4747   }
  4748   return internal_memalign(ms, alignment, bytes);
  4749 }
  4750 
  4751 void** mspace_independent_calloc(mspace msp, size_t n_elements,
  4752                                  size_t elem_size, void* chunks[]) {
  4753   size_t sz = elem_size; /* serves as 1-element array */
  4754   mstate ms = (mstate)msp;
  4755   if (!ok_magic(ms)) {
  4756     USAGE_ERROR_ACTION(ms,ms);
  4757     return 0;
  4758   }
  4759   return ialloc(ms, n_elements, &sz, 3, chunks);
  4760 }
  4761 
  4762 void** mspace_independent_comalloc(mspace msp, size_t n_elements,
  4763                                    size_t sizes[], void* chunks[]) {
  4764   mstate ms = (mstate)msp;
  4765   if (!ok_magic(ms)) {
  4766     USAGE_ERROR_ACTION(ms,ms);
  4767     return 0;
  4768   }
  4769   return ialloc(ms, n_elements, sizes, 0, chunks);
  4770 }
  4771 
  4772 int mspace_trim(mspace msp, size_t pad) {
  4773   int result = 0;
  4774   mstate ms = (mstate)msp;
  4775   if (ok_magic(ms)) {
  4776     if (!PREACTION(ms)) {
  4777       result = sys_trim(ms, pad);
  4778       POSTACTION(ms);
  4779     }
  4780   }
  4781   else {
  4782     USAGE_ERROR_ACTION(ms,ms);
  4783   }
  4784   return result;
  4785 }
  4786 
  4787 void mspace_malloc_stats(mspace msp) {
  4788   mstate ms = (mstate)msp;
  4789   if (ok_magic(ms)) {
  4790     internal_malloc_stats(ms);
  4791   }
  4792   else {
  4793     USAGE_ERROR_ACTION(ms,ms);
  4794   }
  4795 }
  4796 
  4797 size_t mspace_footprint(mspace msp) {
  4798   size_t result;
  4799   mstate ms = (mstate)msp;
  4800   if (ok_magic(ms)) {
  4801     result = ms->footprint;
  4802   }
  4803   USAGE_ERROR_ACTION(ms,ms);
  4804   return result;
  4805 }
  4806 
  4807 
  4808 size_t mspace_max_footprint(mspace msp) {
  4809   size_t result;
  4810   mstate ms = (mstate)msp;
  4811   if (ok_magic(ms)) {
  4812     result = ms->max_footprint;
  4813   }
  4814   USAGE_ERROR_ACTION(ms,ms);
  4815   return result;
  4816 }
  4817 
  4818 
  4819 #if !NO_MALLINFO
  4820 struct mallinfo mspace_mallinfo(mspace msp) {
  4821   mstate ms = (mstate)msp;
  4822   if (!ok_magic(ms)) {
  4823     USAGE_ERROR_ACTION(ms,ms);
  4824   }
  4825   return internal_mallinfo(ms);
  4826 }
  4827 #endif /* NO_MALLINFO */
  4828 
  4829 int mspace_mallopt(int param_number, int value) {
  4830   return change_mparam(param_number, value);
  4831 }
  4832 
  4833 #endif /* MSPACES */
  4834 
  4835 /* -------------------- Alternative MORECORE functions ------------------- */
  4836 
  4837 /*
  4838   Guidelines for creating a custom version of MORECORE:
  4839 
  4840   * For best performance, MORECORE should allocate in multiples of pagesize.
  4841   * MORECORE may allocate more memory than requested. (Or even less,
  4842       but this will usually result in a malloc failure.)
  4843   * MORECORE must not allocate memory when given argument zero, but
  4844       instead return one past the end address of memory from previous
  4845       nonzero call.
  4846   * For best performance, consecutive calls to MORECORE with positive
  4847       arguments should return increasing addresses, indicating that
  4848       space has been contiguously extended.
  4849   * Even though consecutive calls to MORECORE need not return contiguous
  4850       addresses, it must be OK for malloc'ed chunks to span multiple
  4851       regions in those cases where they do happen to be contiguous.
  4852   * MORECORE need not handle negative arguments -- it may instead
  4853       just return MFAIL when given negative arguments.
  4854       Negative arguments are always multiples of pagesize. MORECORE
  4855       must not misinterpret negative args as large positive unsigned
  4856       args. You can suppress all such calls from even occurring by defining
  4857       MORECORE_CANNOT_TRIM,
  4858 
  4859   As an example alternative MORECORE, here is a custom allocator
  4860   kindly contributed for pre-OSX macOS.  It uses virtually but not
  4861   necessarily physically contiguous non-paged memory (locked in,
  4862   present and won't get swapped out).  You can use it by uncommenting
  4863   this section, adding some #includes, and setting up the appropriate
  4864   defines above:
  4865 
  4866       #define MORECORE osMoreCore
  4867 
  4868   There is also a shutdown routine that should somehow be called for
  4869   cleanup upon program exit.
  4870 
  4871   #define MAX_POOL_ENTRIES 100
  4872   #define MINIMUM_MORECORE_SIZE  (64 * 1024U)
  4873   static int next_os_pool;
  4874   void *our_os_pools[MAX_POOL_ENTRIES];
  4875 
  4876   void *osMoreCore(int size)
  4877   {
  4878     void *ptr = 0;
  4879     static void *sbrk_top = 0;
  4880 
  4881     if (size > 0)
  4882     {
  4883       if (size < MINIMUM_MORECORE_SIZE)
  4884          size = MINIMUM_MORECORE_SIZE;
  4885       if (CurrentExecutionLevel() == kTaskLevel)
  4886          ptr = PoolAllocateResident(size + RM_PAGE_SIZE, 0);
  4887       if (ptr == 0)
  4888       {
  4889         return (void *) MFAIL;
  4890       }
  4891       // save ptrs so they can be freed during cleanup
  4892       our_os_pools[next_os_pool] = ptr;
  4893       next_os_pool++;
  4894       ptr = (void *) ((((size_t) ptr) + RM_PAGE_MASK) & ~RM_PAGE_MASK);
  4895       sbrk_top = (char *) ptr + size;
  4896       return ptr;
  4897     }
  4898     else if (size < 0)
  4899     {
  4900       // we don't currently support shrink behavior
  4901       return (void *) MFAIL;
  4902     }
  4903     else
  4904     {
  4905       return sbrk_top;
  4906     }
  4907   }
  4908 
  4909   // cleanup any allocated memory pools
  4910   // called as last thing before shutting down driver
  4911 
  4912   void osCleanupMem(void)
  4913   {
  4914     void **ptr;
  4915 
  4916     for (ptr = our_os_pools; ptr < &our_os_pools[MAX_POOL_ENTRIES]; ptr++)
  4917       if (*ptr)
  4918       {
  4919          PoolDeallocate(*ptr);
  4920          *ptr = 0;
  4921       }
  4922   }
  4923 
  4924 */
  4925 
  4926 
  4927 /* -----------------------------------------------------------------------
  4928 History:
  4929     V2.8.3 Thu Sep 22 11:16:32 2005  Doug Lea  (dl at gee)
  4930       * Add max_footprint functions
  4931       * Ensure all appropriate literals are size_t
  4932       * Fix conditional compilation problem for some #define settings
  4933       * Avoid concatenating segments with the one provided
  4934         in create_mspace_with_base
  4935       * Rename some variables to avoid compiler shadowing warnings
  4936       * Use explicit lock initialization.
  4937       * Better handling of sbrk interference.
  4938       * Simplify and fix segment insertion, trimming and mspace_destroy
  4939       * Reinstate REALLOC_ZERO_BYTES_FREES option from 2.7.x
  4940       * Thanks especially to Dennis Flanagan for help on these.
  4941 
  4942     V2.8.2 Sun Jun 12 16:01:10 2005  Doug Lea  (dl at gee)
  4943       * Fix memalign brace error.
  4944 
  4945     V2.8.1 Wed Jun  8 16:11:46 2005  Doug Lea  (dl at gee)
  4946       * Fix improper #endif nesting in C++
  4947       * Add explicit casts needed for C++
  4948 
  4949     V2.8.0 Mon May 30 14:09:02 2005  Doug Lea  (dl at gee)
  4950       * Use trees for large bins
  4951       * Support mspaces
  4952       * Use segments to unify sbrk-based and mmap-based system allocation,
  4953         removing need for emulation on most platforms without sbrk.
  4954       * Default safety checks
  4955       * Optional footer checks. Thanks to William Robertson for the idea.
  4956       * Internal code refactoring
  4957       * Incorporate suggestions and platform-specific changes.
  4958         Thanks to Dennis Flanagan, Colin Plumb, Niall Douglas,
  4959         Aaron Bachmann,  Emery Berger, and others.
  4960       * Speed up non-fastbin processing enough to remove fastbins.
  4961       * Remove useless cfree() to avoid conflicts with other apps.
  4962       * Remove internal memcpy, memset. Compilers handle builtins better.
  4963       * Remove some options that no one ever used and rename others.
  4964 
  4965     V2.7.2 Sat Aug 17 09:07:30 2002  Doug Lea  (dl at gee)
  4966       * Fix malloc_state bitmap array misdeclaration
  4967 
  4968     V2.7.1 Thu Jul 25 10:58:03 2002  Doug Lea  (dl at gee)
  4969       * Allow tuning of FIRST_SORTED_BIN_SIZE
  4970       * Use PTR_UINT as type for all ptr->int casts. Thanks to John Belmonte.
  4971       * Better detection and support for non-contiguousness of MORECORE.
  4972         Thanks to Andreas Mueller, Conal Walsh, and Wolfram Gloger
  4973       * Bypass most of malloc if no frees. Thanks To Emery Berger.
  4974       * Fix freeing of old top non-contiguous chunk im sysmalloc.
  4975       * Raised default trim and map thresholds to 256K.
  4976       * Fix mmap-related #defines. Thanks to Lubos Lunak.
  4977       * Fix copy macros; added LACKS_FCNTL_H. Thanks to Neal Walfield.
  4978       * Branch-free bin calculation
  4979       * Default trim and mmap thresholds now 256K.
  4980 
  4981     V2.7.0 Sun Mar 11 14:14:06 2001  Doug Lea  (dl at gee)
  4982       * Introduce independent_comalloc and independent_calloc.
  4983         Thanks to Michael Pachos for motivation and help.
  4984       * Make optional .h file available
  4985       * Allow > 2GB requests on 32bit systems.
  4986       * new WIN32 sbrk, mmap, munmap, lock code from <Walter@GeNeSys-e.de>.
  4987         Thanks also to Andreas Mueller <a.mueller at paradatec.de>,
  4988         and Anonymous.
  4989       * Allow override of MALLOC_ALIGNMENT (Thanks to Ruud Waij for
  4990         helping test this.)
  4991       * memalign: check alignment arg
  4992       * realloc: don't try to shift chunks backwards, since this
  4993         leads to  more fragmentation in some programs and doesn't
  4994         seem to help in any others.
  4995       * Collect all cases in malloc requiring system memory into sysmalloc
  4996       * Use mmap as backup to sbrk
  4997       * Place all internal state in malloc_state
  4998       * Introduce fastbins (although similar to 2.5.1)
  4999       * Many minor tunings and cosmetic improvements
  5000       * Introduce USE_PUBLIC_MALLOC_WRAPPERS, USE_MALLOC_LOCK
  5001       * Introduce MALLOC_FAILURE_ACTION, MORECORE_CONTIGUOUS
  5002         Thanks to Tony E. Bennett <tbennett@nvidia.com> and others.
  5003       * Include errno.h to support default failure action.
  5004 
  5005     V2.6.6 Sun Dec  5 07:42:19 1999  Doug Lea  (dl at gee)
  5006       * return null for negative arguments
  5007       * Added Several WIN32 cleanups from Martin C. Fong <mcfong at yahoo.com>
  5008          * Add 'LACKS_SYS_PARAM_H' for those systems without 'sys/param.h'
  5009           (e.g. WIN32 platforms)
  5010          * Cleanup header file inclusion for WIN32 platforms
  5011          * Cleanup code to avoid Microsoft Visual C++ compiler complaints
  5012          * Add 'USE_DL_PREFIX' to quickly allow co-existence with existing
  5013            memory allocation routines
  5014          * Set 'malloc_getpagesize' for WIN32 platforms (needs more work)
  5015          * Use 'assert' rather than 'ASSERT' in WIN32 code to conform to
  5016            usage of 'assert' in non-WIN32 code
  5017          * Improve WIN32 'sbrk()' emulation's 'findRegion()' routine to
  5018            avoid infinite loop
  5019       * Always call 'fREe()' rather than 'free()'
  5020 
  5021     V2.6.5 Wed Jun 17 15:57:31 1998  Doug Lea  (dl at gee)
  5022       * Fixed ordering problem with boundary-stamping
  5023 
  5024     V2.6.3 Sun May 19 08:17:58 1996  Doug Lea  (dl at gee)
  5025       * Added pvalloc, as recommended by H.J. Liu
  5026       * Added 64bit pointer support mainly from Wolfram Gloger
  5027       * Added anonymously donated WIN32 sbrk emulation
  5028       * Malloc, calloc, getpagesize: add optimizations from Raymond Nijssen
  5029       * malloc_extend_top: fix mask error that caused wastage after
  5030         foreign sbrks
  5031       * Add linux mremap support code from HJ Liu
  5032 
  5033     V2.6.2 Tue Dec  5 06:52:55 1995  Doug Lea  (dl at gee)
  5034       * Integrated most documentation with the code.
  5035       * Add support for mmap, with help from
  5036         Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
  5037       * Use last_remainder in more cases.
  5038       * Pack bins using idea from  colin@nyx10.cs.du.edu
  5039       * Use ordered bins instead of best-fit threshhold
  5040       * Eliminate block-local decls to simplify tracing and debugging.
  5041       * Support another case of realloc via move into top
  5042       * Fix error occuring when initial sbrk_base not word-aligned.
  5043       * Rely on page size for units instead of SBRK_UNIT to
  5044         avoid surprises about sbrk alignment conventions.
  5045       * Add mallinfo, mallopt. Thanks to Raymond Nijssen
  5046         (raymond@es.ele.tue.nl) for the suggestion.
  5047       * Add `pad' argument to malloc_trim and top_pad mallopt parameter.
  5048       * More precautions for cases where other routines call sbrk,
  5049         courtesy of Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
  5050       * Added macros etc., allowing use in linux libc from
  5051         H.J. Lu (hjl@gnu.ai.mit.edu)
  5052       * Inverted this history list
  5053 
  5054     V2.6.1 Sat Dec  2 14:10:57 1995  Doug Lea  (dl at gee)
  5055       * Re-tuned and fixed to behave more nicely with V2.6.0 changes.
  5056       * Removed all preallocation code since under current scheme
  5057         the work required to undo bad preallocations exceeds
  5058         the work saved in good cases for most test programs.
  5059       * No longer use return list or unconsolidated bins since
  5060         no scheme using them consistently outperforms those that don't
  5061         given above changes.
  5062       * Use best fit for very large chunks to prevent some worst-cases.
  5063       * Added some support for debugging
  5064 
  5065     V2.6.0 Sat Nov  4 07:05:23 1995  Doug Lea  (dl at gee)
  5066       * Removed footers when chunks are in use. Thanks to
  5067         Paul Wilson (wilson@cs.texas.edu) for the suggestion.
  5068 
  5069     V2.5.4 Wed Nov  1 07:54:51 1995  Doug Lea  (dl at gee)
  5070       * Added malloc_trim, with help from Wolfram Gloger
  5071         (wmglo@Dent.MED.Uni-Muenchen.DE).
  5072 
  5073     V2.5.3 Tue Apr 26 10:16:01 1994  Doug Lea  (dl at g)
  5074 
  5075     V2.5.2 Tue Apr  5 16:20:40 1994  Doug Lea  (dl at g)
  5076       * realloc: try to expand in both directions
  5077       * malloc: swap order of clean-bin strategy;
  5078       * realloc: only conditionally expand backwards
  5079       * Try not to scavenge used bins
  5080       * Use bin counts as a guide to preallocation
  5081       * Occasionally bin return list chunks in first scan
  5082       * Add a few optimizations from colin@nyx10.cs.du.edu
  5083 
  5084     V2.5.1 Sat Aug 14 15:40:43 1993  Doug Lea  (dl at g)
  5085       * faster bin computation & slightly different binning
  5086       * merged all consolidations to one part of malloc proper
  5087          (eliminating old malloc_find_space & malloc_clean_bin)
  5088       * Scan 2 returns chunks (not just 1)
  5089       * Propagate failure in realloc if malloc returns 0
  5090       * Add stuff to allow compilation on non-ANSI compilers
  5091           from kpv@research.att.com
  5092 
  5093     V2.5 Sat Aug  7 07:41:59 1993  Doug Lea  (dl at g.oswego.edu)
  5094       * removed potential for odd address access in prev_chunk
  5095       * removed dependency on getpagesize.h
  5096       * misc cosmetics and a bit more internal documentation
  5097       * anticosmetics: mangled names in macros to evade debugger strangeness
  5098       * tested on sparc, hp-700, dec-mips, rs6000
  5099           with gcc & native cc (hp, dec only) allowing
  5100           Detlefs & Zorn comparison study (in SIGPLAN Notices.)
  5101 
  5102     Trial version Fri Aug 28 13:14:29 1992  Doug Lea  (dl at g.oswego.edu)
  5103       * Based loosely on libg++-1.2X malloc. (It retains some of the overall
  5104          structure of old version,  but most details differ.)
  5105  
  5106 */
  5107 
  5108 #endif /* !HAVE_MALLOC */