src/stdlib/SDL_malloc.c
author Ozkan Sezer <sezeroz@gmail.com>
Sun, 14 Oct 2018 15:25:04 +0300
branchSDL-1.2
changeset 12325 c4f2eeda176f
parent 6137 4720145f848b
permissions -rw-r--r--
remove symlink for libSDL-1.0.so.0 from the rpm spec file.

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