- Main Page
- Related Pages
- Data Structures
- Files

- File List
- Globals

# lib/dlmalloc/dlmalloc.c

    00001 /*
    00002   This is a version (aka dlmalloc) of malloc/free/realloc written by
    00003   Doug Lea and released to the public domain, as explained at
    00004   http://creativecommons.org/licenses/publicdomain.  Send questions,
    00005   comments, complaints, performance data, etc to dl@cs.oswego.edu
    00006
    00007 * Version 2.8.3 Thu Sep 22 11:16:15 2005  Doug Lea  (dl at gee)
    00008
    00009    Note: There may be an updated version of this malloc obtainable at
    00010            ftp://gee.cs.oswego.edu/pub/misc/malloc.c
    00011          Check before installing!
    00012
    00013 * Quickstart
    00014
    00015   This library is all in one file to simplify the most common usage:
    00016   ftp it, compile it (-O3), and link it into another program. All of
    00017   the compile-time options default to reasonable values for use on
    00018   most platforms.  You might later want to step through various
    00019   compile-time and dynamic tuning options.
    00020
    00021   For convenience, an include file for code using this malloc is at:
    00022      ftp://gee.cs.oswego.edu/pub/misc/malloc-2.8.3.h
    00023   You don't really need this .h file unless you call functions not
    00024   defined in your system include files.  The .h file contains only the
    00025   excerpts from this file needed for using this malloc on ANSI C/C++
    00026   systems, so long as you haven't changed compile-time options about
    00027   naming and tuning parameters.  If you do, then you can create your
    00028   own malloc.h that does include all settings by cutting at the point
    00029   indicated below. Note that you may already by default be using a C
    00030   library containing a malloc that is based on some version of this
    00031   malloc (for example in linux). You might still want to use the one
    00032   in this file to customize settings or to avoid overheads associated
    00033   with library versions.
    00034
    00035 * Vital statistics:
    00036
    00037   Supported pointer/size_t representation:       4 or 8 bytes
    00038        size_t MUST be an unsigned type of the same width as
    00039        pointers. (If you are using an ancient system that declares
    00040        size_t as a signed type, or need it to be a different width
    00041        than pointers, you can use a previous release of this malloc
    00042        (e.g. 2.7.2) supporting these.)
    00043
    00044   Alignment:                                     8 bytes (default)
    00045        This suffices for nearly all current machines and C compilers.
    00046        However, you can define MALLOC_ALIGNMENT to be wider than this
    00047        if necessary (up to 128bytes), at the expense of using more space.
    00048
    00049   Minimum overhead per allocated chunk:   4 or  8 bytes (if 4byte sizes)
    00050                                           8 or 16 bytes (if 8byte sizes)
    00051        Each malloced chunk has a hidden word of overhead holding size
    00052        and status information, and additional cross-check word
    00053        if FOOTERS is defined.
    00054
    00055   Minimum allocated size: 4-byte ptrs:  16 bytes    (including overhead)
    00056                           8-byte ptrs:  32 bytes    (including overhead)
    00057
    00058        Even a request for zero bytes (i.e., malloc(0)) returns a
    00059        pointer to something of the minimum allocatable size.
    00060        The maximum overhead wastage (i.e., number of extra bytes
    00061        allocated than were requested in malloc) is less than or equal
    00062        to the minimum size, except for requests >= mmap_threshold that
    00063        are serviced via mmap(), where the worst case wastage is about
    00064        32 bytes plus the remainder from a system page (the minimal
    00065        mmap unit); typically 4096 or 8192 bytes.
    00066
    00067   Security: static-safe; optionally more or less
    00068        The "security" of malloc refers to the ability of malicious
    00069        code to accentuate the effects of errors (for example, freeing
    00070        space that is not currently malloc'ed or overwriting past the
    00071        ends of chunks) in code that calls malloc.  This malloc
    00072        guarantees not to modify any memory locations below the base of
    00073        heap, i.e., static variables, even in the presence of usage
    00074        errors.  The routines additionally detect most improper frees
    00075        and reallocs.  All this holds as long as the static bookkeeping
    00076        for malloc itself is not corrupted by some other means.  This
    00077        is only one aspect of security -- these checks do not, and
    00078        cannot, detect all possible programming errors.
    00079
    00080        If FOOTERS is defined nonzero, then each allocated chunk
    00081        carries an additional check word to verify that it was malloced
    00082        from its space.  These check words are the same within each
    00083        execution of a program using malloc, but differ across
    00084        executions, so externally crafted fake chunks cannot be
    00085        freed. This improves security by rejecting frees/reallocs that
    00086        could corrupt heap memory, in addition to the checks preventing
    00087        writes to statics that are always on.  This may further improve
    00088        security at the expense of time and space overhead.  (Note that
    00089        FOOTERS may also be worth using with MSPACES.)
    00090
    00091        By default detected errors cause the program to abort (calling
    00092        "abort()"). You can override this to instead proceed past
    00093        errors by defining PROCEED_ON_ERROR.  In this case, a bad free
    00094        has no effect, and a malloc that encounters a bad address
    00095        caused by user overwrites will ignore the bad address by
    00096        dropping pointers and indices to all known memory. This may
    00097        be appropriate for programs that should continue if at all
    00098        possible in the face of programming errors, although they may
    00099        run out of memory because dropped memory is never reclaimed.
    00100
    00101        If you don't like either of these options, you can define
    00102        CORRUPTION_ERROR_ACTION and USAGE_ERROR_ACTION to do anything
    00103        else. And if if you are sure that your program using malloc has
    00104        no errors or vulnerabilities, you can define INSECURE to 1,
    00105        which might (or might not) provide a small performance improvement.
    00106
    00107   Thread-safety: NOT thread-safe unless USE_LOCKS defined
    00108        When USE_LOCKS is defined, each public call to malloc, free,
    00109        etc is surrounded with either a pthread mutex or a win32
    00110        spinlock (depending on WIN32). This is not especially fast, and
    00111        can be a major bottleneck.  It is designed only to provide
    00112        minimal protection in concurrent environments, and to provide a
    00113        basis for extensions.  If you are using malloc in a concurrent
    00114        program, consider instead using ptmalloc, which is derived from
    00115        a version of this malloc. (See http://www.malloc.de).
    00116
    00117   System requirements: Any combination of MORECORE and/or MMAP/MUNMAP
    00118        This malloc can use unix sbrk or any emulation (invoked using
    00119        the CALL_MORECORE macro) and/or mmap/munmap or any emulation
    00120        (invoked using CALL_MMAP/CALL_MUNMAP) to get and release system
    00121        memory.  On most unix systems, it tends to work best if both
    00122        MORECORE and MMAP are enabled.  On Win32, it uses emulations
    00123        based on VirtualAlloc. It also uses common C library functions
    00124        like memset.
    00125
    00126   Compliance: I believe it is compliant with the Single Unix Specification
    00127        (See http://www.unix.org). Also SVID/XPG, ANSI C, and probably
    00128        others as well.
    00129
    00130 * Overview of algorithms
    00131
    00132   This is not the fastest, most space-conserving, most portable, or
    00133   most tunable malloc ever written. However it is among the fastest
    00134   while also being among the most space-conserving, portable and
    00135   tunable.  Consistent balance across these factors results in a good
    00136   general-purpose allocator for malloc-intensive programs.
    00137
    00138   In most ways, this malloc is a best-fit allocator. Generally, it
    00139   chooses the best-fitting existing chunk for a request, with ties
    00140   broken in approximately least-recently-used order. (This strategy
    00141   normally maintains low fragmentation.) However, for requests less
    00142   than 256bytes, it deviates from best-fit when there is not an
    00143   exactly fitting available chunk by preferring to use space adjacent
    00144   to that used for the previous small request, as well as by breaking
    00145   ties in approximately most-recently-used order. (These enhance
    00146   locality of series of small allocations.)  And for very large requests
    00147   (>= 256Kb by default), it relies on system memory mapping
    00148   facilities, if supported.  (This helps avoid carrying around and
    00149   possibly fragmenting memory used only for large chunks.)
    00150
    00151   All operations (except malloc_stats and mallinfo) have execution
    00152   times that are bounded by a constant factor of the number of bits in
    00153   a size_t, not counting any clearing in calloc or copying in realloc,
    00154   or actions surrounding MORECORE and MMAP that have times
    00155   proportional to the number of non-contiguous regions returned by
    00156   system allocation routines, which is often just 1.
    00157
    00158   The implementation is not very modular and seriously overuses
    00159   macros. Perhaps someday all C compilers will do as good a job
    00160   inlining modular code as can now be done by brute-force expansion,
    00161   but now, enough of them seem not to.
    00162
    00163   Some compilers issue a lot of warnings about code that is
    00164   dead/unreachable only on some platforms, and also about intentional
    00165   uses of negation on unsigned types. All known cases of each can be
    00166   ignored.
    00167
    00168   For a longer but out of date high-level description, see
    00169      http://gee.cs.oswego.edu/dl/html/malloc.html
    00170
    00171 * MSPACES
    00172   If MSPACES is defined, then in addition to malloc, free, etc.,
    00173   this file also defines mspace_malloc, mspace_free, etc. These
    00174   are versions of malloc routines that take an "mspace" argument
    00175   obtained using create_mspace, to control all internal bookkeeping.
    00176   If ONLY_MSPACES is defined, only these versions are compiled.
    00177   So if you would like to use this allocator for only some allocations,
    00178   and your system malloc for others, you can compile with
    00179   ONLY_MSPACES and then do something like...
    00180     static mspace mymspace = create_mspace(0,0); // for example
    00181     #define mymalloc(bytes)  mspace_malloc(mymspace, bytes)
    00182
    00183   (Note: If you only need one instance of an mspace, you can instead
    00184   use "USE_DL_PREFIX" to relabel the global malloc.)
    00185
    00186   You can similarly create thread-local allocators by storing
    00187   mspaces as thread-locals. For example:
    00188     static __thread mspace tlms = 0;
    00189     void*  tlmalloc(size_t bytes) {
    00190       if (tlms == 0) tlms = create_mspace(0, 0);
    00191       return mspace_malloc(tlms, bytes);
    00192     }
    00193     void  tlfree(void* mem) { mspace_free(tlms, mem); }
    00194
    00195   Unless FOOTERS is defined, each mspace is completely independent.
    00196   You cannot allocate from one and free to another (although
    00197   conformance is only weakly checked, so usage errors are not always
    00198   caught). If FOOTERS is defined, then each chunk carries around a tag
    00199   indicating its originating mspace, and frees are directed to their
    00200   originating spaces.
    00201
    00202  -------------------------  Compile-time options ---------------------------
    00203
    00204 Be careful in setting #define values for numerical constants of type
    00205 size_t. On some systems, literal values are not automatically extended
    00206 to size_t precision unless they are explicitly casted.
    00207
    00208 WIN32                    default: defined if _WIN32 defined
    00209   Defining WIN32 sets up defaults for MS environment and compilers.
    00210   Otherwise defaults are for unix.
    00211
    00212 MALLOC_ALIGNMENT         default: (size_t)8
    00213   Controls the minimum alignment for malloc'ed chunks.  It must be a
    00214   power of two and at least 8, even on machines for which smaller
    00215   alignments would suffice. It may be defined as larger than this
    00216   though. Note however that code and data structures are optimized for
    00217   the case of 8-byte alignment.
    00218
    00219 MSPACES                  default: 0 (false)
    00220   If true, compile in support for independent allocation spaces.
    00221   This is only supported if HAVE_MMAP is true.
    00222
    00223 ONLY_MSPACES             default: 0 (false)
    00224   If true, only compile in mspace versions, not regular versions.
    00225
    00226 USE_LOCKS                default: 0 (false)
    00227   Causes each call to each public routine to be surrounded with
    00228   pthread or WIN32 mutex lock/unlock. (If set true, this can be
    00229   overridden on a per-mspace basis for mspace versions.)
    00230
    00231 FOOTERS                  default: 0
    00232   If true, provide extra checking and dispatching by placing
    00233   information in the footers of allocated chunks. This adds
    00234   space and time overhead.
    00235
    00236 INSECURE                 default: 0
    00237   If true, omit checks for usage errors and heap space overwrites.
    00238
    00239 USE_DL_PREFIX            default: NOT defined
    00240   Causes compiler to prefix all public routines with the string 'dl'.
    00241   This can be useful when you only want to use this malloc in one part
    00242   of a program, using your regular system malloc elsewhere.
    00243
    00244 ABORT                    default: defined as abort()
    00245   Defines how to abort on failed checks.  On most systems, a failed
    00246   check cannot die with an "assert" or even print an informative
    00247   message, because the underlying print routines in turn call malloc,
    00248   which will fail again.  Generally, the best policy is to simply call
    00249   abort(). It's not very useful to do more than this because many
    00250   errors due to overwriting will show up as address faults (null, odd
    00251   addresses etc) rather than malloc-triggered checks, so will also
    00252   abort.  Also, most compilers know that abort() does not return, so
    00253   can better optimize code conditionally calling it.
    00254
    00255 PROCEED_ON_ERROR           default: defined as 0 (false)
    00256   Controls whether detected bad addresses cause them to bypassed
    00257   rather than aborting. If set, detected bad arguments to free and
    00258   realloc are ignored. And all bookkeeping information is zeroed out
    00259   upon a detected overwrite of freed heap space, thus losing the
    00260   ability to ever return it from malloc again, but enabling the
    00261   application to proceed. If PROCEED_ON_ERROR is defined, the
    00262   static variable malloc_corruption_error_count is compiled in
    00263   and can be examined to see if errors have occurred. This option
    00264   generates slower code than the default abort policy.
    00265
    00266 DEBUG                    default: NOT defined
    00267   The DEBUG setting is mainly intended for people trying to modify
    00268   this code or diagnose problems when porting to new platforms.
    00269   However, it may also be able to better isolate user errors than just
    00270   using runtime checks.  The assertions in the check routines spell
    00271   out in more detail the assumptions and invariants underlying the
    00272   algorithms.  The checking is fairly extensive, and will slow down
    00273   execution noticeably. Calling malloc_stats or mallinfo with DEBUG
    00274   set will attempt to check every non-mmapped allocated and free chunk
    00275   in the course of computing the summaries.
    00276
    00277 ABORT_ON_ASSERT_FAILURE   default: defined as 1 (true)
    00278   Debugging assertion failures can be nearly impossible if your
    00279   version of the assert macro causes malloc to be called, which will
    00280   lead to a cascade of further failures, blowing the runtime stack.
    00281   ABORT_ON_ASSERT_FAILURE cause assertions failures to call abort(),
    00282   which will usually make debugging easier.
    00283
    00284 MALLOC_FAILURE_ACTION     default: sets errno to ENOMEM, or no-op on win32
    00285   The action to take before "return 0" when malloc fails to be able to
    00286   return memory because there is none available.
    00287
    00288 HAVE_MORECORE             default: 1 (true) unless win32 or ONLY_MSPACES
    00289   True if this system supports sbrk or an emulation of it.
    00290
    00291 MORECORE                  default: sbrk
    00292   The name of the sbrk-style system routine to call to obtain more
    00293   memory.  See below for guidance on writing custom MORECORE
    00294   functions. The type of the argument to sbrk/MORECORE varies across
    00295   systems.  It cannot be size_t, because it supports negative
    00296   arguments, so it is normally the signed type of the same width as
    00297   size_t (sometimes declared as "intptr_t").  It doesn't much matter
    00298   though. Internally, we only call it with arguments less than half
    00299   the max value of a size_t, which should work across all reasonable
    00300   possibilities, although sometimes generating compiler warnings.  See
    00301   near the end of this file for guidelines for creating a custom
    00302   version of MORECORE.
    00303
    00304 MORECORE_CONTIGUOUS       default: 1 (true)
    00305   If true, take advantage of fact that consecutive calls to MORECORE
    00306   with positive arguments always return contiguous increasing
    00307   addresses.  This is true of unix sbrk. It does not hurt too much to
    00308   set it true anyway, since malloc copes with non-contiguities.
    00309   Setting it false when definitely non-contiguous saves time
    00310   and possibly wasted space it would take to discover this though.
    00311
    00312 MORECORE_CANNOT_TRIM      default: NOT defined
    00313   True if MORECORE cannot release space back to the system when given
    00314   negative arguments. This is generally necessary only if you are
    00315   using a hand-crafted MORECORE function that cannot handle negative
    00316   arguments.
    00317
    00318 HAVE_MMAP                 default: 1 (true)
    00319   True if this system supports mmap or an emulation of it.  If so, and
    00320   HAVE_MORECORE is not true, MMAP is used for all system
    00321   allocation. If set and HAVE_MORECORE is true as well, MMAP is
    00322   primarily used to directly allocate very large blocks. It is also
    00323   used as a backup strategy in cases where MORECORE fails to provide
    00324   space from system. Note: A single call to MUNMAP is assumed to be
    00325   able to unmap memory that may have be allocated using multiple calls
    00326   to MMAP, so long as they are adjacent.
    00327
    00328 HAVE_MREMAP               default: 1 on linux, else 0
    00329   If true realloc() uses mremap() to re-allocate large blocks and
    00330   extend or shrink allocation spaces.
    00331
    00332 MMAP_CLEARS               default: 1 on unix
    00333   True if mmap clears memory so calloc doesn't need to. This is true
    00334   for standard unix mmap using /dev/zero.
    00335
    00336 USE_BUILTIN_FFS            default: 0 (i.e., not used)
    00337   Causes malloc to use the builtin ffs() function to compute indices.
    00338   Some compilers may recognize and intrinsify ffs to be faster than the
    00339   supplied C version. Also, the case of x86 using gcc is special-cased
    00340   to an asm instruction, so is already as fast as it can be, and so
    00341   this setting has no effect. (On most x86s, the asm version is only
    00342   slightly faster than the C version.)
    00343
    00344 malloc_getpagesize         default: derive from system includes, or 4096.
    00345   The system page size. To the extent possible, this malloc manages
    00346   memory from the system in page-size units.  This may be (and
    00347   usually is) a function rather than a constant. This is ignored
    00348   if WIN32, where page size is determined using getSystemInfo during
    00349   initialization.
    00350
    00351 USE_DEV_RANDOM             default: 0 (i.e., not used)
    00352   Causes malloc to use /dev/random to initialize secure magic seed for
    00353   stamping footers. Otherwise, the current time is used.
    00354
    00355 NO_MALLINFO                default: 0
    00356   If defined, don't compile "mallinfo". This can be a simple way
    00357   of dealing with mismatches between system declarations and
    00358   those in this file.
    00359
    00360 MALLINFO_FIELD_TYPE        default: size_t
    00361   The type of the fields in the mallinfo struct. This was originally
    00362   defined as "int" in SVID etc, but is more usefully defined as
    00363   size_t. The value is used only if  HAVE_USR_INCLUDE_MALLOC_H is not set
    00364
    00365 REALLOC_ZERO_BYTES_FREES    default: not defined
    00366   This should be set if a call to realloc with zero bytes should
    00367   be the same as a call to free. Some people think it should. Otherwise,
    00368   since this malloc returns a unique pointer for malloc(0), so does
    00369   realloc(p, 0).
    00370
    00371 LACKS_UNISTD_H, LACKS_FCNTL_H, LACKS_SYS_PARAM_H, LACKS_SYS_MMAN_H
    00372 LACKS_STRINGS_H, LACKS_STRING_H, LACKS_SYS_TYPES_H,  LACKS_ERRNO_H
    00373 LACKS_STDLIB_H                default: NOT defined unless on WIN32
    00374   Define these if your system does not have these header files.
    00375   You might need to manually insert some of the declarations they provide.
    00376
    00377 DEFAULT_GRANULARITY        default: page size if MORECORE_CONTIGUOUS,
    00378                                 system_info.dwAllocationGranularity in WIN32,
    00379                                 otherwise 64K.
    00380       Also settable using mallopt(M_GRANULARITY, x)
    00381   The unit for allocating and deallocating memory from the system.  On
    00382   most systems with contiguous MORECORE, there is no reason to
    00383   make this more than a page. However, systems with MMAP tend to
    00384   either require or encourage larger granularities.  You can increase
    00385   this value to prevent system allocation functions to be called so
    00386   often, especially if they are slow.  The value must be at least one
    00387   page and must be a power of two.  Setting to 0 causes initialization
    00388   to either page size or win32 region size.  (Note: In previous
    00389   versions of malloc, the equivalent of this option was called
    00390   "TOP_PAD")
    00391
    00392 DEFAULT_TRIM_THRESHOLD    default: 2MB
    00393       Also settable using mallopt(M_TRIM_THRESHOLD, x)
    00394   The maximum amount of unused top-most memory to keep before
    00395   releasing via malloc_trim in free().  Automatic trimming is mainly
    00396   useful in long-lived programs using contiguous MORECORE.  Because
    00397   trimming via sbrk can be slow on some systems, and can sometimes be
    00398   wasteful (in cases where programs immediately afterward allocate
    00399   more large chunks) the value should be high enough so that your
    00400   overall system performance would improve by releasing this much
    00401   memory.  As a rough guide, you might set to a value close to the
    00402   average size of a process (program) running on your system.
    00403   Releasing this much memory would allow such a process to run in
    00404   memory.  Generally, it is worth tuning trim thresholds when a
    00405   program undergoes phases where several large chunks are allocated
    00406   and released in ways that can reuse each other's storage, perhaps
    00407   mixed with phases where there are no such chunks at all. The trim
    00408   value must be greater than page size to have any useful effect.  To
    00409   disable trimming completely, you can set to MAX_SIZE_T. Note that the trick
    00410   some people use of mallocing a huge space and then freeing it at
    00411   program startup, in an attempt to reserve system memory, doesn't
    00412   have the intended effect under automatic trimming, since that memory
    00413   will immediately be returned to the system.
    00414
    00415 DEFAULT_MMAP_THRESHOLD       default: 256K
    00416       Also settable using mallopt(M_MMAP_THRESHOLD, x)
    00417   The request size threshold for using MMAP to directly service a
    00418   request. Requests of at least this size that cannot be allocated
    00419   using already-existing space will be serviced via mmap.  (If enough
    00420   normal freed space already exists it is used instead.)  Using mmap
    00421   segregates relatively large chunks of memory so that they can be
    00422   individually obtained and released from the host system. A request
    00423   serviced through mmap is never reused by any other request (at least
    00424   not directly; the system may just so happen to remap successive
    00425   requests to the same locations).  Segregating space in this way has
    00426   the benefits that: Mmapped space can always be individually released
    00427   back to the system, which helps keep the system level memory demands
    00428   of a long-lived program low.  Also, mapped memory doesn't become
    00429   `locked' between other chunks, as can happen with normally allocated
    00430   chunks, which means that even trimming via malloc_trim would not
    00431   release them.  However, it has the disadvantage that the space
    00432   cannot be reclaimed, consolidated, and then used to service later
    00433   requests, as happens with normal chunks.  The advantages of mmap
    00434   nearly always outweigh disadvantages for "large" chunks, but the
    00435   value of "large" may vary across systems.  The default is an
    00436   empirically derived value that works well in most systems. You can
    00437   disable mmap by setting to MAX_SIZE_T.
    00438
    00439 */
    00440
    00441 #include "dlmalloc-config.h"
    00442
    00443 #ifndef WIN32
    00444 #ifdef _WIN32
    00445 #define WIN32 1
    00446 #endif  /* _WIN32 */
    00447 #endif  /* WIN32 */
    00448 #ifdef WIN32
    00449 #define WIN32_LEAN_AND_MEAN
    00450 #include <windows.h>
    00451 #define HAVE_MMAP 1
    00452 #define HAVE_MORECORE 0
    00453 #define LACKS_UNISTD_H
    00454 #define LACKS_SYS_PARAM_H
    00455 #define LACKS_SYS_MMAN_H
    00456 #define LACKS_STRING_H
    00457 #define LACKS_STRINGS_H
    00458 #define LACKS_SYS_TYPES_H
    00459 #define LACKS_ERRNO_H
    00460 #define MALLOC_FAILURE_ACTION
    00461 #define MMAP_CLEARS 0 /* WINCE and some others apparently don't clear */
    00462 #endif  /* WIN32 */
    00463
    00464 #if defined(DARWIN) || defined(_DARWIN)
    00465 /* Mac OSX docs advise not to use sbrk; it seems better to use mmap */
    00466 #ifndef HAVE_MORECORE
    00467 #define HAVE_MORECORE 0
    00468 #define HAVE_MMAP 1
    00469 #endif  /* HAVE_MORECORE */
    00470 #endif  /* DARWIN */
    00471
    00472 #ifndef LACKS_SYS_TYPES_H
    00473 #include <sys/types.h>  /* For size_t */
    00474 #endif  /* LACKS_SYS_TYPES_H */
    00475
    00476 /* The maximum possible size_t value has all bits set */
    00477 #define MAX_SIZE_T           (~(size_t)0)
    00478
    00479 #ifndef ONLY_MSPACES
    00480 #define ONLY_MSPACES 0
    00481 #endif  /* ONLY_MSPACES */
    00482 #ifndef MSPACES
    00483 #if ONLY_MSPACES
    00484 #define MSPACES 1
    00485 #else   /* ONLY_MSPACES */
    00486 #define MSPACES 0
    00487 #endif  /* ONLY_MSPACES */
    00488 #endif  /* MSPACES */
    00489 #ifndef MALLOC_ALIGNMENT
    00490 #define MALLOC_ALIGNMENT ((size_t)8U)
    00491 #endif  /* MALLOC_ALIGNMENT */
    00492 #ifndef FOOTERS
    00493 #define FOOTERS 0
    00494 #endif  /* FOOTERS */
    00495 #ifndef ABORT
    00496 #define ABORT  abort()
    00497 #endif  /* ABORT */
    00498 #ifndef ABORT_ON_ASSERT_FAILURE
    00499 #define ABORT_ON_ASSERT_FAILURE 1
    00500 #endif  /* ABORT_ON_ASSERT_FAILURE */
    00501 #ifndef PROCEED_ON_ERROR
    00502 #define PROCEED_ON_ERROR 0
    00503 #endif  /* PROCEED_ON_ERROR */
    00504 #ifndef USE_LOCKS
    00505 #define USE_LOCKS 0
    00506 #endif  /* USE_LOCKS */
    00507 #ifndef INSECURE
    00508 #define INSECURE 0
    00509 #endif  /* INSECURE */
    00510 #ifndef HAVE_MMAP
    00511 #define HAVE_MMAP 1
    00512 #endif  /* HAVE_MMAP */
    00513 #ifndef MMAP_CLEARS
    00514 #define MMAP_CLEARS 1
    00515 #endif  /* MMAP_CLEARS */
    00516 #ifndef HAVE_MREMAP
    00517 #ifdef linux
    00518 #define HAVE_MREMAP 1
    00519 #else   /* linux */
    00520 #define HAVE_MREMAP 0
    00521 #endif  /* linux */
    00522 #endif  /* HAVE_MREMAP */
    00523 #ifndef MALLOC_FAILURE_ACTION
    00524 #define MALLOC_FAILURE_ACTION  errno = ENOMEM;
    00525 #endif  /* MALLOC_FAILURE_ACTION */
    00526 #ifndef HAVE_MORECORE
    00527 #if ONLY_MSPACES
    00528 #define HAVE_MORECORE 0
    00529 #else   /* ONLY_MSPACES */
    00530 #define HAVE_MORECORE 1
    00531 #endif  /* ONLY_MSPACES */
    00532 #endif  /* HAVE_MORECORE */
    00533 #if !HAVE_MORECORE
    00534 #define MORECORE_CONTIGUOUS 0
    00535 #else   /* !HAVE_MORECORE */
    00536 #ifndef MORECORE
    00537 #define MORECORE sbrk
    00538 #endif  /* MORECORE */
    00539 #ifndef MORECORE_CONTIGUOUS
    00540 #define MORECORE_CONTIGUOUS 1
    00541 #endif  /* MORECORE_CONTIGUOUS */
    00542 #endif  /* HAVE_MORECORE */
    00543 #ifndef DEFAULT_GRANULARITY
    00544 #if MORECORE_CONTIGUOUS
    00545 #define DEFAULT_GRANULARITY (0)  /* 0 means to compute in init_mparams */
    00546 #else   /* MORECORE_CONTIGUOUS */
    00547 #define DEFAULT_GRANULARITY ((size_t)64U * (size_t)1024U)
    00548 #endif  /* MORECORE_CONTIGUOUS */
    00549 #endif  /* DEFAULT_GRANULARITY */
    00550 #ifndef DEFAULT_TRIM_THRESHOLD
    00551 #ifndef MORECORE_CANNOT_TRIM
    00552 #define DEFAULT_TRIM_THRESHOLD ((size_t)2U * (size_t)1024U * (size_t)1024U)
    00553 #else   /* MORECORE_CANNOT_TRIM */
    00554 #define DEFAULT_TRIM_THRESHOLD MAX_SIZE_T
    00555 #endif  /* MORECORE_CANNOT_TRIM */
    00556 #endif  /* DEFAULT_TRIM_THRESHOLD */
    00557 #ifndef DEFAULT_MMAP_THRESHOLD
    00558 #if HAVE_MMAP
    00559 #define DEFAULT_MMAP_THRESHOLD ((size_t)256U * (size_t)1024U)
    00560 #else   /* HAVE_MMAP */
    00561 #define DEFAULT_MMAP_THRESHOLD MAX_SIZE_T
    00562 #endif  /* HAVE_MMAP */
    00563 #endif  /* DEFAULT_MMAP_THRESHOLD */
    00564 #ifndef USE_BUILTIN_FFS
    00565 #define USE_BUILTIN_FFS 0
    00566 #endif  /* USE_BUILTIN_FFS */
    00567 #ifndef USE_DEV_RANDOM
    00568 #define USE_DEV_RANDOM 0
    00569 #endif  /* USE_DEV_RANDOM */
    00570 #ifndef NO_MALLINFO
    00571 #define NO_MALLINFO 0
    00572 #endif  /* NO_MALLINFO */
    00573 #ifndef MALLINFO_FIELD_TYPE
    00574 #define MALLINFO_FIELD_TYPE size_t
    00575 #endif  /* MALLINFO_FIELD_TYPE */
    00576
    00577 /*
    00578   mallopt tuning options.  SVID/XPG defines four standard parameter
    00579   numbers for mallopt, normally defined in malloc.h.  None of these
    00580   are used in this malloc, so setting them has no effect. But this
    00581   malloc does support the following options.
    00582 */
    00583
    00584 #define M_TRIM_THRESHOLD     (-1)
    00585 #define M_GRANULARITY        (-2)
    00586 #define M_MMAP_THRESHOLD     (-3)
    00587
    00588 /* ------------------------ Mallinfo declarations ------------------------ */
    00589
    00590 #if !NO_MALLINFO
    00591 /*
    00592   This version of malloc supports the standard SVID/XPG mallinfo
    00593   routine that returns a struct containing usage properties and
    00594   statistics. It should work on any system that has a
    00595   /usr/include/malloc.h defining struct mallinfo.  The main
    00596   declaration needed is the mallinfo struct that is returned (by-copy)
    00597   by mallinfo().  The malloinfo struct contains a bunch of fields that
    00598   are not even meaningful in this version of malloc.  These fields are
    00599   are instead filled by mallinfo() with other numbers that might be of
    00600   interest.
    00601
    00602   HAVE_USR_INCLUDE_MALLOC_H should be set if you have a
    00603   /usr/include/malloc.h file that includes a declaration of struct
    00604   mallinfo.  If so, it is included; else a compliant version is
    00605   declared below.  These must be precisely the same for mallinfo() to
    00606   work.  The original SVID version of this struct, defined on most
    00607   systems with mallinfo, declares all fields as ints. But some others
    00608   define as unsigned long. If your system defines the fields using a
    00609   type of different width than listed here, you MUST #include your
    00610   system version and #define HAVE_USR_INCLUDE_MALLOC_H.
    00611 */
    00612
    00613 /* #define HAVE_USR_INCLUDE_MALLOC_H */
    00614
    00615 #ifdef HAVE_USR_INCLUDE_MALLOC_H
    00616 #include "/usr/include/malloc.h"
    00617 #else /* HAVE_USR_INCLUDE_MALLOC_H */
    00618
    00619 struct mallinfo {
    00620   MALLINFO_FIELD_TYPE arena;    /* non-mmapped space allocated from system */
    00621   MALLINFO_FIELD_TYPE ordblks;  /* number of free chunks */
    00622   MALLINFO_FIELD_TYPE smblks;   /* always 0 */
    00623   MALLINFO_FIELD_TYPE hblks;    /* always 0 */
    00624   MALLINFO_FIELD_TYPE hblkhd;   /* space in mmapped regions */
    00625   MALLINFO_FIELD_TYPE usmblks;  /* maximum total allocated space */
    00626   MALLINFO_FIELD_TYPE fsmblks;  /* always 0 */
    00627   MALLINFO_FIELD_TYPE uordblks; /* total allocated space */
    00628   MALLINFO_FIELD_TYPE fordblks; /* total free space */
    00629   MALLINFO_FIELD_TYPE keepcost; /* releasable (via malloc_trim) space */
    00630 };
    00631
    00632 #endif /* HAVE_USR_INCLUDE_MALLOC_H */
    00633 #endif /* NO_MALLINFO */
    00634
    00635 #ifdef __cplusplus
    00636 extern "C" {
    00637 #endif /* __cplusplus */
    00638
    00639 #if !ONLY_MSPACES
    00640
    00641 /* ------------------- Declarations of public routines ------------------- */
    00642
    00643 #ifndef USE_DL_PREFIX
    00644 #define dlcalloc               calloc
    00645 #define dlfree                 free
    00646 #define dlmalloc               malloc
    00647 #define dlmemalign             memalign
    00648 #define dlrealloc              realloc
    00649 #define dlvalloc               valloc
    00650 #define dlpvalloc              pvalloc
    00651 #define dlmallinfo             mallinfo
    00652 #define dlmallopt              mallopt
    00653 #define dlmalloc_trim          malloc_trim
    00654 #define dlmalloc_stats         malloc_stats
    00655 #define dlmalloc_usable_size   malloc_usable_size
    00656 #define dlmalloc_footprint     malloc_footprint
    00657 #define dlmalloc_max_footprint malloc_max_footprint
    00658 #define dlindependent_calloc   independent_calloc
    00659 #define dlindependent_comalloc independent_comalloc
    00660 #endif /* USE_DL_PREFIX */
    00661
    00662
    00663 /*
    00664   malloc(size_t n)
    00665   Returns a pointer to a newly allocated chunk of at least n bytes, or
    00666   null if no space is available, in which case errno is set to ENOMEM
    00667   on ANSI C systems.
    00668
    00669   If n is zero, malloc returns a minimum-sized chunk. (The minimum
    00670   size is 16 bytes on most 32bit systems, and 32 bytes on 64bit
    00671   systems.)  Note that size_t is an unsigned type, so calls with
    00672   arguments that would be negative if signed are interpreted as
    00673   requests for huge amounts of space, which will often fail. The
    00674   maximum supported value of n differs across systems, but is in all
    00675   cases less than the maximum representable value of a size_t.
    00676 */
    00677 void* dlmalloc(size_t);
    00678
    00679 /*
    00680   free(void* p)
    00681   Releases the chunk of memory pointed to by p, that had been previously
    00682   allocated using malloc or a related routine such as realloc.
    00683   It has no effect if p is null. If p was not malloced or already
    00684   freed, free(p) will by default cause the current program to abort.
    00685 */
    00686 void  dlfree(void*);
    00687
    00688 /*
    00689   calloc(size_t n_elements, size_t element_size);
    00690   Returns a pointer to n_elements * element_size bytes, with all locations
    00691   set to zero.
    00692 */
    00693 void* dlcalloc(size_t, size_t);
    00694
    00695 /*
    00696   realloc(void* p, size_t n)
    00697   Returns a pointer to a chunk of size n that contains the same data
    00698   as does chunk p up to the minimum of (n, p's size) bytes, or null
    00699   if no space is available.
    00700
    00701   The returned pointer may or may not be the same as p. The algorithm
    00702   prefers extending p in most cases when possible, otherwise it
    00703   employs the equivalent of a malloc-copy-free sequence.
    00704
    00705   If p is null, realloc is equivalent to malloc.
    00706
    00707   If space is not available, realloc returns null, errno is set (if on
    00708   ANSI) and p is NOT freed.
    00709
    00710   if n is for fewer bytes than already held by p, the newly unused
    00711   space is lopped off and freed if possible.  realloc with a size
    00712   argument of zero (re)allocates a minimum-sized chunk.
    00713
    00714   The old unix realloc convention of allowing the last-free'd chunk
    00715   to be used as an argument to realloc is not supported.
    00716 */
    00717
    00718 void* dlrealloc(void*, size_t);
    00719
    00720 /*
    00721   memalign(size_t alignment, size_t n);
    00722   Returns a pointer to a newly allocated chunk of n bytes, aligned
    00723   in accord with the alignment argument.
    00724
    00725   The alignment argument should be a power of two. If the argument is
    00726   not a power of two, the nearest greater power is used.
    00727   8-byte alignment is guaranteed by normal malloc calls, so don't
    00728   bother calling memalign with an argument of 8 or less.
    00729
    00730   Overreliance on memalign is a sure way to fragment space.
    00731 */
    00732 void* dlmemalign(size_t, size_t);
    00733
    00734 /*
    00735   valloc(size_t n);
    00736   Equivalent to memalign(pagesize, n), where pagesize is the page
    00737   size of the system. If the pagesize is unknown, 4096 is used.
    00738 */
    00739 void* dlvalloc(size_t);
    00740
    00741 /*
    00742   mallopt(int parameter_number, int parameter_value)
    00743   Sets tunable parameters The format is to provide a
    00744   (parameter-number, parameter-value) pair.  mallopt then sets the
    00745   corresponding parameter to the argument value if it can (i.e., so
    00746   long as the value is meaningful), and returns 1 if successful else
    00747   0.  SVID/XPG/ANSI defines four standard param numbers for mallopt,
    00748   normally defined in malloc.h.  None of these are use in this malloc,
    00749   so setting them has no effect. But this malloc also supports other
    00750   options in mallopt. See below for details.  Briefly, supported
    00751   parameters are as follows (listed defaults are for "typical"
    00752   configurations).
    00753
    00754   Symbol            param #  default    allowed param values
    00755   M_TRIM_THRESHOLD     -1   2*1024*1024   any   (MAX_SIZE_T disables)
    00756   M_GRANULARITY        -2     page size   any power of 2 >= page size
    00757   M_MMAP_THRESHOLD     -3      256*1024   any   (or 0 if no MMAP support)
    00758 */
    00759 int dlmallopt(int, int);
    00760
    00761 /*
    00762   malloc_footprint();
    00763   Returns the number of bytes obtained from the system.  The total
    00764   number of bytes allocated by malloc, realloc etc., is less than this
    00765   value. Unlike mallinfo, this function returns only a precomputed
    00766   result, so can be called frequently to monitor memory consumption.
    00767   Even if locks are otherwise defined, this function does not use them,
    00768   so results might not be up to date.
    00769 */
    00770 size_t dlmalloc_footprint(void);
    00771
    00772 /*
    00773   malloc_max_footprint();
    00774   Returns the maximum number of bytes obtained from the system. This
    00775   value will be greater than current footprint if deallocated space
    00776   has been reclaimed by the system. The peak number of bytes allocated
    00777   by malloc, realloc etc., is less than this value. Unlike mallinfo,
    00778   this function returns only a precomputed result, so can be called
    00779   frequently to monitor memory consumption.  Even if locks are
    00780   otherwise defined, this function does not use them, so results might
    00781   not be up to date.
    00782 */
    00783 size_t dlmalloc_max_footprint(void);
    00784
    00785 #if !NO_MALLINFO
    00786 /*
    00787   mallinfo()
    00788   Returns (by copy) a struct containing various summary statistics:
    00789
    00790   arena:     current total non-mmapped bytes allocated from system
    00791   ordblks:   the number of free chunks
    00792   smblks:    always zero.
    00793   hblks:     current number of mmapped regions
    00794   hblkhd:    total bytes held in mmapped regions
    00795   usmblks:   the maximum total allocated space. This will be greater
    00796                 than current total if trimming has occurred.
    00797   fsmblks:   always zero
    00798   uordblks:  current total allocated space (normal or mmapped)
    00799   fordblks:  total free space
    00800   keepcost:  the maximum number of bytes that could ideally be released
    00801                back to system via malloc_trim. ("ideally" means that
    00802                it ignores page restrictions etc.)
    00803
    00804   Because these fields are ints, but internal bookkeeping may
    00805   be kept as longs, the reported values may wrap around zero and
    00806   thus be inaccurate.
    00807 */
    00808 struct mallinfo dlmallinfo(void);
    00809 #endif /* NO_MALLINFO */
    00810
    00811 /*
    00812   independent_calloc(size_t n_elements, size_t element_size, void* chunks[]);
    00813
    00814   independent_calloc is similar to calloc, but instead of returning a
    00815   single cleared space, it returns an array of pointers to n_elements
    00816   independent elements that can hold contents of size elem_size, each
    00817   of which starts out cleared, and can be independently freed,
    00818   realloc'ed etc. The elements are guaranteed to be adjacently
    00819   allocated (this is not guaranteed to occur with multiple callocs or
    00820   mallocs), which may also improve cache locality in some
    00821   applications.
    00822
    00823   The "chunks" argument is optional (i.e., may be null, which is
    00824   probably the most typical usage). If it is null, the returned array
    00825   is itself dynamically allocated and should also be freed when it is
    00826   no longer needed. Otherwise, the chunks array must be of at least
    00827   n_elements in length. It is filled in with the pointers to the
    00828   chunks.
    00829
    00830   In either case, independent_calloc returns this pointer array, or
    00831   null if the allocation failed.  If n_elements is zero and "chunks"
    00832   is null, it returns a chunk representing an array with zero elements
    00833   (which should be freed if not wanted).
    00834
    00835   Each element must be individually freed when it is no longer
    00836   needed. If you'd like to instead be able to free all at once, you
    00837   should instead use regular calloc and assign pointers into this
    00838   space to represent elements.  (In this case though, you cannot
    00839   independently free elements.)
    00840
    00841   independent_calloc simplifies and speeds up implementations of many
    00842   kinds of pools.  It may also be useful when constructing large data
    00843   structures that initially have a fixed number of fixed-sized nodes,
    00844   but the number is not known at compile time, and some of the nodes
    00845   may later need to be freed. For example:
    00846
    00847   struct Node { int item; struct Node* next; };
    00848
    00849   struct Node* build_list() {
    00850     struct Node** pool;
    00851     int n = read_number_of_nodes_needed();
    00852     if (n <= 0) return 0;
    00853     pool = (struct Node**)(independent_calloc(n, sizeof(struct Node), 0);
    00854     if (pool == 0) die();
    00855     // organize into a linked list...
    00856     struct Node* first = pool[0];
    00857     for (i = 0; i < n-1; ++i)
    00858       pool[i]->next = pool[i+1];
    00859     free(pool);     // Can now free the array (or not, if it is needed later)
    00860     return first;
    00861   }
    00862 */
    00863 void** dlindependent_calloc(size_t, size_t, void**);
    00864
    00865 /*
    00866   independent_comalloc(size_t n_elements, size_t sizes[], void* chunks[]);
    00867
    00868   independent_comalloc allocates, all at once, a set of n_elements
    00869   chunks with sizes indicated in the "sizes" array.    It returns
    00870   an array of pointers to these elements, each of which can be
    00871   independently freed, realloc'ed etc. The elements are guaranteed to
    00872   be adjacently allocated (this is not guaranteed to occur with
    00873   multiple callocs or mallocs), which may also improve cache locality
    00874   in some applications.
    00875
    00876   The "chunks" argument is optional (i.e., may be null). If it is null
    00877   the returned array is itself dynamically allocated and should also
    00878   be freed when it is no longer needed. Otherwise, the chunks array
    00879   must be of at least n_elements in length. It is filled in with the
    00880   pointers to the chunks.
    00881
    00882   In either case, independent_comalloc returns this pointer array, or
    00883   null if the allocation failed.  If n_elements is zero and chunks is
    00884   null, it returns a chunk representing an array with zero elements
    00885   (which should be freed if not wanted).
    00886
    00887   Each element must be individually freed when it is no longer
    00888   needed. If you'd like to instead be able to free all at once, you
    00889   should instead use a single regular malloc, and assign pointers at
    00890   particular offsets in the aggregate space. (In this case though, you
    00891   cannot independently free elements.)
    00892
    00893   independent_comallac differs from independent_calloc in that each
    00894   element may have a different size, and also that it does not
    00895   automatically clear elements.
    00896
    00897   independent_comalloc can be used to speed up allocation in cases
    00898   where several structs or objects must always be allocated at the
    00899   same time.  For example:
    00900
    00901   struct Head { ... }
    00902   struct Foot { ... }
    00903
    00904   void send_message(char* msg) {
    00905     int msglen = strlen(msg);
    00906     size_t sizes[3] = { sizeof(struct Head), msglen, sizeof(struct Foot) };
    00907     void* chunks[3];
    00908     if (independent_comalloc(3, sizes, chunks) == 0)
    00909       die();
    00910     struct Head* head = (struct Head*)(chunks[0]);
    00911     char*        body = (char*)(chunks[1]);
    00912     struct Foot* foot = (struct Foot*)(chunks[2]);
    00913     // ...
    00914   }
    00915
    00916   In general though, independent_comalloc is worth using only for
    00917   larger values of n_elements. For small values, you probably won't
    00918   detect enough difference from series of malloc calls to bother.
    00919
    00920   Overuse of independent_comalloc can increase overall memory usage,
    00921   since it cannot reuse existing noncontiguous small chunks that
    00922   might be available for some of the elements.
    00923 */
    00924 void** dlindependent_comalloc(size_t, size_t*, void**);
    00925
    00926
    00927 /*
    00928   pvalloc(size_t n);
    00929   Equivalent to valloc(minimum-page-that-holds(n)), that is,
    00930   round up n to nearest pagesize.
    00931  */
    00932 void*  dlpvalloc(size_t);
    00933
    00934 /*
    00935   malloc_trim(size_t pad);
    00936
    00937   If possible, gives memory back to the system (via negative arguments
    00938   to sbrk) if there is unused memory at the `high' end of the malloc
    00939   pool or in unused MMAP segments. You can call this after freeing
    00940   large blocks of memory to potentially reduce the system-level memory
    00941   requirements of a program. However, it cannot guarantee to reduce
    00942   memory. Under some allocation patterns, some large free blocks of
    00943   memory will be locked between two used chunks, so they cannot be
    00944   given back to the system.
    00945
    00946   The `pad' argument to malloc_trim represents the amount of free
    00947   trailing space to leave untrimmed. If this argument is zero, only
    00948   the minimum amount of memory to maintain internal data structures
    00949   will be left. Non-zero arguments can be supplied to maintain enough
    00950   trailing space to service future expected allocations without having
    00951   to re-obtain memory from the system.
    00952
    00953   Malloc_trim returns 1 if it actually released any memory, else 0.
    00954 */
    00955 int  dlmalloc_trim(size_t);
    00956
    00957 /*
    00958   malloc_usable_size(void* p);
    00959
    00960   Returns the number of bytes you can actually use in
    00961   an allocated chunk, which may be more than you requested (although
    00962   often not) due to alignment and minimum size constraints.
    00963   You can use this many bytes without worrying about
    00964   overwriting other allocated objects. This is not a particularly great
    00965   programming practice. malloc_usable_size can be more useful in
    00966   debugging and assertions, for example:
    00967
    00968   p = malloc(n);
    00969   assert(malloc_usable_size(p) >= 256);
    00970 */
    00971 size_t dlmalloc_usable_size(void*);
    00972
    00973 /*
    00974   malloc_stats();
    00975   Prints on stderr the amount of space obtained from the system (both
    00976   via sbrk and mmap), the maximum amount (which may be more than
    00977   current if malloc_trim and/or munmap got called), and the current
    00978   number of bytes allocated via malloc (or realloc, etc) but not yet
    00979   freed. Note that this is the number of bytes allocated, not the
    00980   number requested. It will be larger than the number requested
    00981   because of alignment and bookkeeping overhead. Because it includes
    00982   alignment wastage as being in use, this figure may be greater than
    00983   zero even when no user-level chunks are allocated.
    00984
    00985   The reported current and maximum system memory can be inaccurate if
    00986   a program makes other calls to system memory allocation functions
    00987   (normally sbrk) outside of malloc.
    00988
    00989   malloc_stats prints only the most commonly interesting statistics.
    00990   More information can be obtained by calling mallinfo.
    00991 */
    00992 void  dlmalloc_stats(void);
    00993
    00994 #endif /* ONLY_MSPACES */
    00995
    00996 #if MSPACES
    00997
    00998 /*
    00999   mspace is an opaque type representing an independent
    01000   region of space that supports mspace_malloc, etc.
    01001 */
    01002 typedef void* mspace;
    01003
    01004 /*
    01005   create_mspace creates and returns a new independent space with the
    01006   given initial capacity, or, if 0, the default granularity size.  It
    01007   returns null if there is no system memory available to create the
    01008   space.  If argument locked is non-zero, the space uses a separate
    01009   lock to control access. The capacity of the space will grow
    01010   dynamically as needed to service mspace_malloc requests.  You can
    01011   control the sizes of incremental increases of this space by
    01012   compiling with a different DEFAULT_GRANULARITY or dynamically
    01013   setting with mallopt(M_GRANULARITY, value).
    01014 */
    01015 mspace create_mspace(size_t capacity, int locked);
    01016
    01017 /*
    01018   destroy_mspace destroys the given space, and attempts to return all
    01019   of its memory back to the system, returning the total number of
    01020   bytes freed. After destruction, the results of access to all memory
    01021   used by the space become undefined.
    01022 */
    01023 size_t destroy_mspace(mspace msp);
    01024
    01025 /*
    01026   create_mspace_with_base uses the memory supplied as the initial base
    01027   of a new mspace. Part (less than 128*sizeof(size_t) bytes) of this
    01028   space is used for bookkeeping, so the capacity must be at least this
    01029   large. (Otherwise 0 is returned.) When this initial space is
    01030   exhausted, additional memory will be obtained from the system.
    01031   Destroying this space will deallocate all additionally allocated
    01032   space (if possible) but not the initial base.
    01033 */
    01034 mspace create_mspace_with_base(void* base, size_t capacity, int locked);
    01035
    01036 /*
    01037   mspace_malloc behaves as malloc, but operates within
    01038   the given space.
    01039 */
    01040 void* mspace_malloc(mspace msp, size_t bytes);
    01041
    01042 /*
    01043   mspace_free behaves as free, but operates within
    01044   the given space.
    01045
    01046   If compiled with FOOTERS==1, mspace_free is not actually needed.
    01047   free may be called instead of mspace_free because freed chunks from
    01048   any space are handled by their originating spaces.
    01049 */
    01050 void mspace_free(mspace msp, void* mem);
    01051
    01052 /*
    01053   mspace_realloc behaves as realloc, but operates within
    01054   the given space.
    01055
    01056   If compiled with FOOTERS==1, mspace_realloc is not actually
    01057   needed.  realloc may be called instead of mspace_realloc because
    01058   realloced chunks from any space are handled by their originating
    01059   spaces.
    01060 */
    01061 void* mspace_realloc(mspace msp, void* mem, size_t newsize);
    01062
    01063 /*
    01064   mspace_calloc behaves as calloc, but operates within
    01065   the given space.
    01066 */
    01067 void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size);
    01068
    01069 /*
    01070   mspace_memalign behaves as memalign, but operates within
    01071   the given space.
    01072 */
    01073 void* mspace_memalign(mspace msp, size_t alignment, size_t bytes);
    01074
    01075 /*
    01076   mspace_independent_calloc behaves as independent_calloc, but
    01077   operates within the given space.
    01078 */
    01079 void** mspace_independent_calloc(mspace msp, size_t n_elements,
    01080                                  size_t elem_size, void* chunks[]);
    01081
    01082 /*
    01083   mspace_independent_comalloc behaves as independent_comalloc, but
    01084   operates within the given space.
    01085 */
    01086 void** mspace_independent_comalloc(mspace msp, size_t n_elements,
    01087                                    size_t sizes[], void* chunks[]);
    01088
    01089 /*
    01090   mspace_footprint() returns the number of bytes obtained from the
    01091   system for this space.
    01092 */
    01093 size_t mspace_footprint(mspace msp);
    01094
    01095 /*
    01096   mspace_max_footprint() returns the peak number of bytes obtained from the
    01097   system for this space.
    01098 */
    01099 size_t mspace_max_footprint(mspace msp);
    01100
    01101
    01102 #if !NO_MALLINFO
    01103 /*
    01104   mspace_mallinfo behaves as mallinfo, but reports properties of
    01105   the given space.
    01106 */
    01107 struct mallinfo mspace_mallinfo(mspace msp);
    01108 #endif /* NO_MALLINFO */
    01109
    01110 /*
    01111   mspace_malloc_stats behaves as malloc_stats, but reports
    01112   properties of the given space.
    01113 */
    01114 void mspace_malloc_stats(mspace msp);
    01115
    01116 /*
    01117   mspace_trim behaves as malloc_trim, but
    01118   operates within the given space.
    01119 */
    01120 int mspace_trim(mspace msp, size_t pad);
    01121
    01122 /*
    01123   An alias for mallopt.
    01124 */
    01125 int mspace_mallopt(int, int);
    01126
    01127 #endif /* MSPACES */
    01128
    01129 #ifdef __cplusplus
    01130 };  /* end of extern "C" */
    01131 #endif /* __cplusplus */
    01132
    01133 /*
    01134   ========================================================================
    01135   To make a fully customizable malloc.h header file, cut everything
    01136   above this line, put into file malloc.h, edit to suit, and #include it
    01137   on the next line, as well as in programs that use this malloc.
    01138   ========================================================================
    01139 */
    01140
    01141 /* #include "malloc.h" */
    01142
    01143 /*------------------------------ internal #includes ---------------------- */
    01144
    01145 #ifdef WIN32
    01146 #pragma warning( disable : 4146 ) /* no "unsigned" warnings */
    01147 #endif /* WIN32 */
    01148
    01149 #ifndef LACKS_STDIO_H
    01150 #include <stdio.h>       /* for printing in malloc_stats */
    01151 #endif
    01152
    01153 #ifndef LACKS_ERRNO_H
    01154 #include <errno.h>       /* for MALLOC_FAILURE_ACTION */
    01155 #endif /* LACKS_ERRNO_H */
    01156 #if FOOTERS
    01157 #include <time.h>        /* for magic initialization */
    01158 #endif /* FOOTERS */
    01159 #ifndef LACKS_STDLIB_H
    01160 #include <stdlib.h>      /* for abort() */
    01161 #endif /* LACKS_STDLIB_H */
    01162 #ifdef DEBUG
    01163 #if ABORT_ON_ASSERT_FAILURE
    01164 #define assert(x) if(!(x)) ABORT
    01165 #else /* ABORT_ON_ASSERT_FAILURE */
    01166 #include <assert.h>
    01167 #endif /* ABORT_ON_ASSERT_FAILURE */
    01168 #else  /* DEBUG */
    01169 #define assert(x)
    01170 #endif /* DEBUG */
    01171 #ifndef LACKS_STRING_H
    01172 #include <string.h>      /* for memset etc */
    01173 #endif  /* LACKS_STRING_H */
    01174 #if USE_BUILTIN_FFS
    01175 #ifndef LACKS_STRINGS_H
    01176 #include <strings.h>     /* for ffs */
    01177 #endif /* LACKS_STRINGS_H */
    01178 #endif /* USE_BUILTIN_FFS */
    01179 #if HAVE_MMAP
    01180 #ifndef LACKS_SYS_MMAN_H
    01181 #include <sys/mman.h>    /* for mmap */
    01182 #endif /* LACKS_SYS_MMAN_H */
    01183 #ifndef LACKS_FCNTL_H
    01184 #include <fcntl.h>
    01185 #endif /* LACKS_FCNTL_H */
    01186 #endif /* HAVE_MMAP */
    01187 #if HAVE_MORECORE
    01188 #ifndef LACKS_UNISTD_H
    01189 #include <unistd.h>     /* for sbrk */
    01190 #else /* LACKS_UNISTD_H */
    01191 #if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)
    01192 extern void*     sbrk(ptrdiff_t);
    01193 #endif /* FreeBSD etc */
    01194 #endif /* LACKS_UNISTD_H */
    01195 #endif /* HAVE_MMAP */
    01196
    01197 #ifndef WIN32
    01198 #ifndef malloc_getpagesize
    01199 #  ifdef _SC_PAGESIZE         /* some SVR4 systems omit an underscore */
    01200 #    ifndef _SC_PAGE_SIZE
    01201 #      define _SC_PAGE_SIZE _SC_PAGESIZE
    01202 #    endif
    01203 #  endif
    01204 #  ifdef _SC_PAGE_SIZE
    01205 #    define malloc_getpagesize sysconf(_SC_PAGE_SIZE)
    01206 #  else
    01207 #    if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE)
    01208        extern size_t getpagesize();
    01209 #      define malloc_getpagesize getpagesize()
    01210 #    else
    01211 #      ifdef WIN32 /* use supplied emulation of getpagesize */
    01212 #        define malloc_getpagesize getpagesize()
    01213 #      else
    01214 #        ifndef LACKS_SYS_PARAM_H
    01215 #          include <sys/param.h>
    01216 #        endif
    01217 #        ifdef EXEC_PAGESIZE
    01218 #          define malloc_getpagesize EXEC_PAGESIZE
    01219 #        else
    01220 #          ifdef NBPG
    01221 #            ifndef CLSIZE
    01222 #              define malloc_getpagesize NBPG
    01223 #            else
    01224 #              define malloc_getpagesize (NBPG * CLSIZE)
    01225 #            endif
    01226 #          else
    01227 #            ifdef NBPC
    01228 #              define malloc_getpagesize NBPC
    01229 #            else
    01230 #              ifdef PAGESIZE
    01231 #                define malloc_getpagesize PAGESIZE
    01232 #              else /* just guess */
    01233 #                define malloc_getpagesize ((size_t)4096U)
    01234 #              endif
    01235 #            endif
    01236 #          endif
    01237 #        endif
    01238 #      endif
    01239 #    endif
    01240 #  endif
    01241 #endif
    01242 #endif
    01243
    01244 /* ------------------- size_t and alignment properties -------------------- */
    01245
    01246 /* The byte and bit size of a size_t */
    01247 #define SIZE_T_SIZE         (sizeof(size_t))
    01248 #define SIZE_T_BITSIZE      (sizeof(size_t) << 3)
    01249
    01250 /* Some constants coerced to size_t */
    01251 /* Annoying but necessary to avoid errors on some plaftorms */
    01252 #define SIZE_T_ZERO         ((size_t)0)
    01253 #define SIZE_T_ONE          ((size_t)1)
    01254 #define SIZE_T_TWO          ((size_t)2)
    01255 #define TWO_SIZE_T_SIZES    (SIZE_T_SIZE<<1)
    01256 #define FOUR_SIZE_T_SIZES   (SIZE_T_SIZE<<2)
    01257 #define SIX_SIZE_T_SIZES    (FOUR_SIZE_T_SIZES+TWO_SIZE_T_SIZES)
    01258 #define HALF_MAX_SIZE_T     (MAX_SIZE_T / 2U)
    01259
    01260 /* The bit mask value corresponding to MALLOC_ALIGNMENT */
    01261 #define CHUNK_ALIGN_MASK    (MALLOC_ALIGNMENT - SIZE_T_ONE)
    01262
    01263 /* True if address a has acceptable alignment */
    01264 #define is_aligned(A)       (((size_t)((A)) & (CHUNK_ALIGN_MASK)) == 0)
    01265
    01266 /* the number of bytes to offset an address to align it */
    01267 #define align_offset(A)\
    01268  ((((size_t)(A) & CHUNK_ALIGN_MASK) == 0)? 0 :\
    01269   ((MALLOC_ALIGNMENT - ((size_t)(A) & CHUNK_ALIGN_MASK)) & CHUNK_ALIGN_MASK))
    01270
    01271 /* -------------------------- MMAP preliminaries ------------------------- */
    01272
    01273 /*
    01274    If HAVE_MORECORE or HAVE_MMAP are false, we just define calls and
    01275    checks to fail so compiler optimizer can delete code rather than
    01276    using so many "#if"s.
    01277 */
    01278
    01279
    01280 /* MORECORE and MMAP must return MFAIL on failure */
    01281 #define MFAIL                ((void*)(MAX_SIZE_T))
    01282 #define CMFAIL               ((char*)(MFAIL)) /* defined for convenience */
    01283
    01284 #if !HAVE_MMAP
    01285 #define IS_MMAPPED_BIT       (SIZE_T_ZERO)
    01286 #define USE_MMAP_BIT         (SIZE_T_ZERO)
    01287 #define CALL_MMAP(s)         MFAIL
    01288 #define CALL_MUNMAP(a, s)    (-1)
    01289 #define DIRECT_MMAP(s)       MFAIL
    01290
    01291 #else /* HAVE_MMAP */
    01292 #define IS_MMAPPED_BIT       (SIZE_T_ONE)
    01293 #define USE_MMAP_BIT         (SIZE_T_ONE)
    01294
    01295 #ifndef WIN32
    01296 #define CALL_MUNMAP(a, s)    munmap((a), (s))
    01297 #define MMAP_PROT            (PROT_READ|PROT_WRITE)
    01298 #if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
    01299 #define MAP_ANONYMOUS        MAP_ANON
    01300 #endif /* MAP_ANON */
    01301 #ifdef MAP_ANONYMOUS
    01302 #define MMAP_FLAGS           (MAP_PRIVATE|MAP_ANONYMOUS)
    01303 #define CALL_MMAP(s)         mmap(0, (s), MMAP_PROT, MMAP_FLAGS, -1, 0)
    01304 #else /* MAP_ANONYMOUS */
    01305 /*
    01306    Nearly all versions of mmap support MAP_ANONYMOUS, so the following
    01307    is unlikely to be needed, but is supplied just in case.
    01308 */
    01309 #define MMAP_FLAGS           (MAP_PRIVATE)
    01310 static int dev_zero_fd = -1; /* Cached file descriptor for /dev/zero. */
    01311 #define CALL_MMAP(s) ((dev_zero_fd < 0) ? \
    01312            (dev_zero_fd = open("/dev/zero", O_RDWR), \
    01313             mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0)) : \
    01314             mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0))
    01315 #endif /* MAP_ANONYMOUS */
    01316
    01317 #define DIRECT_MMAP(s)       CALL_MMAP(s)
    01318 #else /* WIN32 */
    01319
    01320 /* Win32 MMAP via VirtualAlloc */
    01321 static void* win32mmap(size_t size) {
    01322   void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT, PAGE_READWRITE);
    01323   return (ptr != 0)? ptr: MFAIL;
    01324 }
    01325
    01326 /* For direct MMAP, use MEM_TOP_DOWN to minimize interference */
    01327 static void* win32direct_mmap(size_t size) {
    01328   void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT|MEM_TOP_DOWN,
    01329                            PAGE_READWRITE);
    01330   return (ptr != 0)? ptr: MFAIL;
    01331 }
    01332
    01333 /* This function supports releasing coalesed segments */
    01334 static int win32munmap(void* ptr, size_t size) {
    01335   MEMORY_BASIC_INFORMATION minfo;
    01336   char* cptr = ptr;
    01337   while (size) {
    01338     if (VirtualQuery(cptr, &minfo, sizeof(minfo)) == 0)
    01339       return -1;
    01340     if (minfo.BaseAddress != cptr || minfo.AllocationBase != cptr ||
    01341         minfo.State != MEM_COMMIT || minfo.RegionSize > size)
    01342       return -1;
    01343     if (VirtualFree(cptr, 0, MEM_RELEASE) == 0)
    01344       return -1;
    01345     cptr += minfo.RegionSize;
    01346     size -= minfo.RegionSize;
    01347   }
    01348   return 0;
    01349 }
    01350
    01351 #define CALL_MMAP(s)         win32mmap(s)
    01352 #define CALL_MUNMAP(a, s)    win32munmap((a), (s))
    01353 #define DIRECT_MMAP(s)       win32direct_mmap(s)
    01354 #endif /* WIN32 */
    01355 #endif /* HAVE_MMAP */
    01356
    01357 #if HAVE_MMAP && HAVE_MREMAP
    01358 #define CALL_MREMAP(addr, osz, nsz, mv) mremap((addr), (osz), (nsz), (mv))
    01359 #else  /* HAVE_MMAP && HAVE_MREMAP */
    01360 #define CALL_MREMAP(addr, osz, nsz, mv) MFAIL
    01361 #endif /* HAVE_MMAP && HAVE_MREMAP */
    01362
    01363 #if HAVE_MORECORE
    01364 #define CALL_MORECORE(S)     MORECORE(S)
    01365 #else  /* HAVE_MORECORE */
    01366 #define CALL_MORECORE(S)     MFAIL
    01367 #endif /* HAVE_MORECORE */
    01368
    01369 /* mstate bit set if continguous morecore disabled or failed */
    01370 #define USE_NONCONTIGUOUS_BIT (4U)
    01371
    01372 /* segment bit set in create_mspace_with_base */
    01373 #define EXTERN_BIT            (8U)
    01374
    01375
    01376 /* --------------------------- Lock preliminaries ------------------------ */
    01377
    01378 #if USE_LOCKS
    01379
    01380 /*
    01381   When locks are defined, there are up to two global locks:
    01382
    01383   * If HAVE_MORECORE, morecore_mutex protects sequences of calls to
    01384     MORECORE.  In many cases sys_alloc requires two calls, that should
    01385     not be interleaved with calls by other threads.  This does not
    01386     protect against direct calls to MORECORE by other threads not
    01387     using this lock, so there is still code to cope the best we can on
    01388     interference.
    01389
    01390   * magic_init_mutex ensures that mparams.magic and other
    01391     unique mparams values are initialized only once.
    01392 */
    01393
    01394 #ifndef WIN32
    01395 /* By default use posix locks */
    01396 #include <pthread.h>
    01397 #define MLOCK_T pthread_mutex_t
    01398 #define INITIAL_LOCK(l)      pthread_mutex_init(l, NULL)
    01399 #define ACQUIRE_LOCK(l)      pthread_mutex_lock(l)
    01400 #define RELEASE_LOCK(l)      pthread_mutex_unlock(l)
    01401
    01402 #if HAVE_MORECORE
    01403 static MLOCK_T morecore_mutex = PTHREAD_MUTEX_INITIALIZER;
    01404 #endif /* HAVE_MORECORE */
    01405
    01406 static MLOCK_T magic_init_mutex = PTHREAD_MUTEX_INITIALIZER;
    01407
    01408 #else /* WIN32 */
    01409 /*
    01410    Because lock-protected regions have bounded times, and there
    01411    are no recursive lock calls, we can use simple spinlocks.
    01412 */
    01413
    01414 #define MLOCK_T long
    01415 static int win32_acquire_lock (MLOCK_T *sl) {
    01416   for (;;) {
    01417 #ifdef InterlockedCompareExchangePointer
    01418     if (!InterlockedCompareExchange(sl, 1, 0))
    01419       return 0;
    01420 #else  /* Use older void* version */
    01421     if (!InterlockedCompareExchange((void**)sl, (void*)1, (void*)0))
    01422       return 0;
    01423 #endif /* InterlockedCompareExchangePointer */
    01424     Sleep (0);
    01425   }
    01426 }
    01427
    01428 static void win32_release_lock (MLOCK_T *sl) {
    01429   InterlockedExchange (sl, 0);
    01430 }
    01431
    01432 #define INITIAL_LOCK(l)      *(l)=0
    01433 #define ACQUIRE_LOCK(l)      win32_acquire_lock(l)
    01434 #define RELEASE_LOCK(l)      win32_release_lock(l)
    01435 #if HAVE_MORECORE
    01436 static MLOCK_T morecore_mutex;
    01437 #endif /* HAVE_MORECORE */
    01438 static MLOCK_T magic_init_mutex;
    01439 #endif /* WIN32 */
    01440
    01441 #define USE_LOCK_BIT               (2U)
    01442 #else  /* USE_LOCKS */
    01443 #define USE_LOCK_BIT               (0U)
    01444 #define INITIAL_LOCK(l)
    01445 #endif /* USE_LOCKS */
    01446
    01447 #if USE_LOCKS && HAVE_MORECORE
    01448 #define ACQUIRE_MORECORE_LOCK()    ACQUIRE_LOCK(&morecore_mutex);
    01449 #define RELEASE_MORECORE_LOCK()    RELEASE_LOCK(&morecore_mutex);
    01450 #else /* USE_LOCKS && HAVE_MORECORE */
    01451 #define ACQUIRE_MORECORE_LOCK()
    01452 #define RELEASE_MORECORE_LOCK()
    01453 #endif /* USE_LOCKS && HAVE_MORECORE */
    01454
    01455 #if USE_LOCKS
    01456 #define ACQUIRE_MAGIC_INIT_LOCK()  ACQUIRE_LOCK(&magic_init_mutex);
    01457 #define RELEASE_MAGIC_INIT_LOCK()  RELEASE_LOCK(&magic_init_mutex);
    01458 #else  /* USE_LOCKS */
    01459 #define ACQUIRE_MAGIC_INIT_LOCK()
    01460 #define RELEASE_MAGIC_INIT_LOCK()
    01461 #endif /* USE_LOCKS */
    01462
    01463
    01464 /* -----------------------  Chunk representations ------------------------ */
    01465
    01466 /*
    01467   (The following includes lightly edited explanations by Colin Plumb.)
    01468
    01469   The malloc_chunk declaration below is misleading (but accurate and
    01470   necessary).  It declares a "view" into memory allowing access to
    01471   necessary fields at known offsets from a given base.
    01472
    01473   Chunks of memory are maintained using a `boundary tag' method as
    01474   originally described by Knuth.  (See the paper by Paul Wilson
    01475   ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a survey of such
    01476   techniques.)  Sizes of free chunks are stored both in the front of
    01477   each chunk and at the end.  This makes consolidating fragmented
    01478   chunks into bigger chunks fast.  The head fields also hold bits
    01479   representing whether chunks are free or in use.
    01480
    01481   Here are some pictures to make it clearer.  They are "exploded" to
    01482   show that the state of a chunk can be thought of as extending from
    01483   the high 31 bits of the head field of its header through the
    01484   prev_foot and PINUSE_BIT bit of the following chunk header.
    01485
    01486   A chunk that's in use looks like:
    01487
    01488    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01489            | Size of previous chunk (if P = 1)                             |
    01490            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01491          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
    01492          | Size of this chunk                                         1| +-+
    01493    mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01494          |                                                               |
    01495          +-                                                             -+
    01496          |                                                               |
    01497          +-                                                             -+
    01498          |                                                               :
    01499          +-      size - sizeof(size_t) available payload bytes          -+
    01500          :                                                               |
    01501  chunk-> +-                                                             -+
    01502          |                                                               |
    01503          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01504        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1|
    01505        | Size of next chunk (may or may not be in use)               | +-+
    01506  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01507
    01508     And if it's free, it looks like this:
    01509
    01510    chunk-> +-                                                             -+
    01511            | User payload (must be in use, or we would have merged!)       |
    01512            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01513          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
    01514          | Size of this chunk                                         0| +-+
    01515    mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01516          | Next pointer                                                  |
    01517          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01518          | Prev pointer                                                  |
    01519          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01520          |                                                               :
    01521          +-      size - sizeof(struct chunk) unused bytes               -+
    01522          :                                                               |
    01523  chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01524          | Size of this chunk                                            |
    01525          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01526        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0|
    01527        | Size of next chunk (must be in use, or we would have merged)| +-+
    01528  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01529        |                                                               :
    01530        +- User payload                                                -+
    01531        :                                                               |
    01532        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01533                                                                      |0|
    01534                                                                      +-+
    01535   Note that since we always merge adjacent free chunks, the chunks
    01536   adjacent to a free chunk must be in use.
    01537
    01538   Given a pointer to a chunk (which can be derived trivially from the
    01539   payload pointer) we can, in O(1) time, find out whether the adjacent
    01540   chunks are free, and if so, unlink them from the lists that they
    01541   are on and merge them with the current chunk.
    01542
    01543   Chunks always begin on even word boundaries, so the mem portion
    01544   (which is returned to the user) is also on an even word boundary, and
    01545   thus at least double-word aligned.
    01546
    01547   The P (PINUSE_BIT) bit, stored in the unused low-order bit of the
    01548   chunk size (which is always a multiple of two words), is an in-use
    01549   bit for the *previous* chunk.  If that bit is *clear*, then the
    01550   word before the current chunk size contains the previous chunk
    01551   size, and can be used to find the front of the previous chunk.
    01552   The very first chunk allocated always has this bit set, preventing
    01553   access to non-existent (or non-owned) memory. If pinuse is set for
    01554   any given chunk, then you CANNOT determine the size of the
    01555   previous chunk, and might even get a memory addressing fault when
    01556   trying to do so.
    01557
    01558   The C (CINUSE_BIT) bit, stored in the unused second-lowest bit of
    01559   the chunk size redundantly records whether the current chunk is
    01560   inuse. This redundancy enables usage checks within free and realloc,
    01561   and reduces indirection when freeing and consolidating chunks.
    01562
    01563   Each freshly allocated chunk must have both cinuse and pinuse set.
    01564   That is, each allocated chunk borders either a previously allocated
    01565   and still in-use chunk, or the base of its memory arena. This is
    01566   ensured by making all allocations from the the `lowest' part of any
    01567   found chunk.  Further, no free chunk physically borders another one,
    01568   so each free chunk is known to be preceded and followed by either
    01569   inuse chunks or the ends of memory.
    01570
    01571   Note that the `foot' of the current chunk is actually represented
    01572   as the prev_foot of the NEXT chunk. This makes it easier to
    01573   deal with alignments etc but can be very confusing when trying
    01574   to extend or adapt this code.
    01575
    01576   The exceptions to all this are
    01577
    01578      1. The special chunk `top' is the top-most available chunk (i.e.,
    01579         the one bordering the end of available memory). It is treated
    01580         specially.  Top is never included in any bin, is used only if
    01581         no other chunk is available, and is released back to the
    01582         system if it is very large (see M_TRIM_THRESHOLD).  In effect,
    01583         the top chunk is treated as larger (and thus less well
    01584         fitting) than any other available chunk.  The top chunk
    01585         doesn't update its trailing size field since there is no next
    01586         contiguous chunk that would have to index off it. However,
    01587         space is still allocated for it (TOP_FOOT_SIZE) to enable
    01588         separation or merging when space is extended.
    01589
    01590      3. Chunks allocated via mmap, which have the lowest-order bit
    01591         (IS_MMAPPED_BIT) set in their prev_foot fields, and do not set
    01592         PINUSE_BIT in their head fields.  Because they are allocated
    01593         one-by-one, each must carry its own prev_foot field, which is
    01594         also used to hold the offset this chunk has within its mmapped
    01595         region, which is needed to preserve alignment. Each mmapped
    01596         chunk is trailed by the first two fields of a fake next-chunk
    01597         for sake of usage checks.
    01598
    01599 */
    01600
    01601 struct malloc_chunk {
    01602   size_t               prev_foot;  /* Size of previous chunk (if free).  */
    01603   size_t               head;       /* Size and inuse bits. */
    01604   struct malloc_chunk* fd;         /* double links -- used only if free. */
    01605   struct malloc_chunk* bk;
    01606 };
    01607
    01608 typedef struct malloc_chunk  mchunk;
    01609 typedef struct malloc_chunk* mchunkptr;
    01610 typedef struct malloc_chunk* sbinptr;  /* The type of bins of chunks */
    01611 typedef unsigned int bindex_t;         /* Described below */
    01612 typedef unsigned int binmap_t;         /* Described below */
    01613 typedef unsigned int flag_t;           /* The type of various bit flag sets */
    01614
    01615 /* ------------------- Chunks sizes and alignments ----------------------- */
    01616
    01617 #define MCHUNK_SIZE         (sizeof(mchunk))
    01618
    01619 #if FOOTERS
    01620 #define CHUNK_OVERHEAD      (TWO_SIZE_T_SIZES)
    01621 #else /* FOOTERS */
    01622 #define CHUNK_OVERHEAD      (SIZE_T_SIZE)
    01623 #endif /* FOOTERS */
    01624
    01625 /* MMapped chunks need a second word of overhead ... */
    01626 #define MMAP_CHUNK_OVERHEAD (TWO_SIZE_T_SIZES)
    01627 /* ... and additional padding for fake next-chunk at foot */
    01628 #define MMAP_FOOT_PAD       (FOUR_SIZE_T_SIZES)
    01629
    01630 /* The smallest size we can malloc is an aligned minimal chunk */
    01631 #define MIN_CHUNK_SIZE\
    01632   ((MCHUNK_SIZE + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
    01633
    01634 /* conversion from malloc headers to user pointers, and back */
    01635 #define chunk2mem(p)        ((void*)((char*)(p)       + TWO_SIZE_T_SIZES))
    01636 #define mem2chunk(mem)      ((mchunkptr)((char*)(mem) - TWO_SIZE_T_SIZES))
    01637 /* chunk associated with aligned address A */
    01638 #define align_as_chunk(A)   (mchunkptr)((A) + align_offset(chunk2mem(A)))
    01639
    01640 /* Bounds on request (not chunk) sizes. */
    01641 #define MAX_REQUEST         ((-MIN_CHUNK_SIZE) << 2)
    01642 #define MIN_REQUEST         (MIN_CHUNK_SIZE - CHUNK_OVERHEAD - SIZE_T_ONE)
    01643
    01644 /* pad request bytes into a usable size */
    01645 #define pad_request(req) \
    01646    (((req) + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
    01647
    01648 /* pad request, checking for minimum (but not maximum) */
    01649 #define request2size(req) \
    01650   (((req) < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(req))
    01651
    01652
    01653 /* ------------------ Operations on head and foot fields ----------------- */
    01654
    01655 /*
    01656   The head field of a chunk is or'ed with PINUSE_BIT when previous
    01657   adjacent chunk in use, and or'ed with CINUSE_BIT if this chunk is in
    01658   use. If the chunk was obtained with mmap, the prev_foot field has
    01659   IS_MMAPPED_BIT set, otherwise holding the offset of the base of the
    01660   mmapped region to the base of the chunk.
    01661 */
    01662
    01663 #define PINUSE_BIT          (SIZE_T_ONE)
    01664 #define CINUSE_BIT          (SIZE_T_TWO)
    01665 #define INUSE_BITS          (PINUSE_BIT|CINUSE_BIT)
    01666
    01667 /* Head value for fenceposts */
    01668 #define FENCEPOST_HEAD      (INUSE_BITS|SIZE_T_SIZE)
    01669
    01670 /* extraction of fields from head words */
    01671 #define cinuse(p)           ((p)->head & CINUSE_BIT)
    01672 #define pinuse(p)           ((p)->head & PINUSE_BIT)
    01673 #define chunksize(p)        ((p)->head & ~(INUSE_BITS))
    01674
    01675 #define clear_pinuse(p)     ((p)->head &= ~PINUSE_BIT)
    01676 #define clear_cinuse(p)     ((p)->head &= ~CINUSE_BIT)
    01677
    01678 /* Treat space at ptr +/- offset as a chunk */
    01679 #define chunk_plus_offset(p, s)  ((mchunkptr)(((char*)(p)) + (s)))
    01680 #define chunk_minus_offset(p, s) ((mchunkptr)(((char*)(p)) - (s)))
    01681
    01682 /* Ptr to next or previous physical malloc_chunk. */
    01683 #define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->head & ~INUSE_BITS)))
    01684 #define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_foot) ))
    01685
    01686 /* extract next chunk's pinuse bit */
    01687 #define next_pinuse(p)  ((next_chunk(p)->head) & PINUSE_BIT)
    01688
    01689 /* Get/set size at footer */
    01690 #define get_foot(p, s)  (((mchunkptr)((char*)(p) + (s)))->prev_foot)
    01691 #define set_foot(p, s)  (((mchunkptr)((char*)(p) + (s)))->prev_foot = (s))
    01692
    01693 /* Set size, pinuse bit, and foot */
    01694 #define set_size_and_pinuse_of_free_chunk(p, s)\
    01695   ((p)->head = (s|PINUSE_BIT), set_foot(p, s))
    01696
    01697 /* Set size, pinuse bit, foot, and clear next pinuse */
    01698 #define set_free_with_pinuse(p, s, n)\
    01699   (clear_pinuse(n), set_size_and_pinuse_of_free_chunk(p, s))
    01700
    01701 #define is_mmapped(p)\
    01702   (!((p)->head & PINUSE_BIT) && ((p)->prev_foot & IS_MMAPPED_BIT))
    01703
    01704 /* Get the internal overhead associated with chunk p */
    01705 #define overhead_for(p)\
    01706  (is_mmapped(p)? MMAP_CHUNK_OVERHEAD : CHUNK_OVERHEAD)
    01707
    01708 /* Return true if malloced space is not necessarily cleared */
    01709 #if MMAP_CLEARS
    01710 #define calloc_must_clear(p) (!is_mmapped(p))
    01711 #else /* MMAP_CLEARS */
    01712 #define calloc_must_clear(p) (1)
    01713 #endif /* MMAP_CLEARS */
    01714
    01715 /* ---------------------- Overlaid data structures ----------------------- */
    01716
    01717 /*
    01718   When chunks are not in use, they are treated as nodes of either
    01719   lists or trees.
    01720
    01721   "Small"  chunks are stored in circular doubly-linked lists, and look
    01722   like this:
    01723
    01724     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01725             |             Size of previous chunk                            |
    01726             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01727     `head:' |             Size of chunk, in bytes                         |P|
    01728       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01729             |             Forward pointer to next chunk in list             |
    01730             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01731             |             Back pointer to previous chunk in list            |
    01732             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01733             |             Unused space (may be 0 bytes long)                .
    01734             .                                                               .
    01735             .                                                               |
    01736 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01737     `foot:' |             Size of chunk, in bytes                           |
    01738             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01739
    01740   Larger chunks are kept in a form of bitwise digital trees (aka
    01741   tries) keyed on chunksizes.  Because malloc_tree_chunks are only for
    01742   free chunks greater than 256 bytes, their size doesn't impose any
    01743   constraints on user chunk sizes.  Each node looks like:
    01744
    01745     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01746             |             Size of previous chunk                            |
    01747             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01748     `head:' |             Size of chunk, in bytes                         |P|
    01749       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01750             |             Forward pointer to next chunk of same size        |
    01751             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01752             |             Back pointer to previous chunk of same size       |
    01753             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01754             |             Pointer to left child (child[0])                  |
    01755             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01756             |             Pointer to right child (child[1])                 |
    01757             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01758             |             Pointer to parent                                 |
    01759             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01760             |             bin index of this chunk                           |
    01761             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01762             |             Unused space                                      .
    01763             .                                                               |
    01764 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01765     `foot:' |             Size of chunk, in bytes                           |
    01766             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    01767
    01768   Each tree holding treenodes is a tree of unique chunk sizes.  Chunks
    01769   of the same size are arranged in a circularly-linked list, with only
    01770   the oldest chunk (the next to be used, in our FIFO ordering)
    01771   actually in the tree.  (Tree members are distinguished by a non-null
    01772   parent pointer.)  If a chunk with the same size an an existing node
    01773   is inserted, it is linked off the existing node using pointers that
    01774   work in the same way as fd/bk pointers of small chunks.
    01775
    01776   Each tree contains a power of 2 sized range of chunk sizes (the
    01777   smallest is 0x100 <= x < 0x180), which is is divided in half at each
    01778   tree level, with the chunks in the smaller half of the range (0x100
    01779   <= x < 0x140 for the top nose) in the left subtree and the larger
    01780   half (0x140 <= x < 0x180) in the right subtree.  This is, of course,
    01781   done by inspecting individual bits.
    01782
    01783   Using these rules, each node's left subtree contains all smaller
    01784   sizes than its right subtree.  However, the node at the root of each
    01785   subtree has no particular ordering relationship to either.  (The
    01786   dividing line between the subtree sizes is based on trie relation.)
    01787   If we remove the last chunk of a given size from the interior of the
    01788   tree, we need to replace it with a leaf node.  The tree ordering
    01789   rules permit a node to be replaced by any leaf below it.
    01790
    01791   The smallest chunk in a tree (a common operation in a best-fit
    01792   allocator) can be found by walking a path to the leftmost leaf in
    01793   the tree.  Unlike a usual binary tree, where we follow left child
    01794   pointers until we reach a null, here we follow the right child
    01795   pointer any time the left one is null, until we reach a leaf with
    01796   both child pointers null. The smallest chunk in the tree will be
    01797   somewhere along that path.
    01798
    01799   The worst case number of steps to add, find, or remove a node is
    01800   bounded by the number of bits differentiating chunks within
    01801   bins. Under current bin calculations, this ranges from 6 up to 21
    01802   (for 32 bit sizes) or up to 53 (for 64 bit sizes). The typical case
    01803   is of course much better.
    01804 */
    01805
    01806 struct malloc_tree_chunk {
    01807   /* The first four fields must be compatible with malloc_chunk */
    01808   size_t                    prev_foot;
    01809   size_t                    head;
    01810   struct malloc_tree_chunk* fd;
    01811   struct malloc_tree_chunk* bk;
    01812
    01813   struct malloc_tree_chunk* child[2];
    01814   struct malloc_tree_chunk* parent;
    01815   bindex_t                  index;
    01816 };
    01817
    01818 typedef struct malloc_tree_chunk  tchunk;
    01819 typedef struct malloc_tree_chunk* tchunkptr;
    01820 typedef struct malloc_tree_chunk* tbinptr; /* The type of bins of trees */
    01821
    01822 /* A little helper macro for trees */
    01823 #define leftmost_child(t) ((t)->child[0] != 0? (t)->child[0] : (t)->child[1])
    01824
    01825 /* ----------------------------- Segments -------------------------------- */
    01826
    01827 /*
    01828   Each malloc space may include non-contiguous segments, held in a
    01829   list headed by an embedded malloc_segment record representing the
    01830   top-most space. Segments also include flags holding properties of
    01831   the space. Large chunks that are directly allocated by mmap are not
    01832   included in this list. They are instead independently created and
    01833   destroyed without otherwise keeping track of them.
    01834
    01835   Segment management mainly comes into play for spaces allocated by
    01836   MMAP.  Any call to MMAP might or might not return memory that is
    01837   adjacent to an existing segment.  MORECORE normally contiguously
    01838   extends the current space, so this space is almost always adjacent,
    01839   which is simpler and faster to deal with. (This is why MORECORE is
    01840   used preferentially to MMAP when both are available -- see
    01841   sys_alloc.)  When allocating using MMAP, we don't use any of the
    01842   hinting mechanisms (inconsistently) supported in various
    01843   implementations of unix mmap, or distinguish reserving from
    01844   committing memory. Instead, we just ask for space, and exploit
    01845   contiguity when we get it.  It is probably possible to do
    01846   better than this on some systems, but no general scheme seems
    01847   to be significantly better.
    01848
    01849   Management entails a simpler variant of the consolidation scheme
    01850   used for chunks to reduce fragmentation -- new adjacent memory is
    01851   normally prepended or appended to an existing segment. However,
    01852   there are limitations compared to chunk consolidation that mostly
    01853   reflect the fact that segment processing is relatively infrequent
    01854   (occurring only when getting memory from system) and that we
    01855   don't expect to have huge numbers of segments:
    01856
    01857   * Segments are not indexed, so traversal requires linear scans.  (It
    01858     would be possible to index these, but is not worth the extra
    01859     overhead and complexity for most programs on most platforms.)
    01860   * New segments are only appended to old ones when holding top-most
    01861     memory; if they cannot be prepended to others, they are held in
    01862     different segments.
    01863
    01864   Except for the top-most segment of an mstate, each segment record
    01865   is kept at the tail of its segment. Segments are added by pushing
    01866   segment records onto the list headed by &mstate.seg for the
    01867   containing mstate.
    01868
    01869   Segment flags control allocation/merge/deallocation policies:
    01870   * If EXTERN_BIT set, then we did not allocate this segment,
    01871     and so should not try to deallocate or merge with others.
    01872     (This currently holds only for the initial segment passed
    01873     into create_mspace_with_base.)
    01874   * If IS_MMAPPED_BIT set, the segment may be merged with
    01875     other surrounding mmapped segments and trimmed/de-allocated
    01876     using munmap.
    01877   * If neither bit is set, then the segment was obtained using
    01878     MORECORE so can be merged with surrounding MORECORE'd segments
    01879     and deallocated/trimmed using MORECORE with negative arguments.
    01880 */
    01881
    01882 struct malloc_segment {
    01883   char*        base;             /* base address */
    01884   size_t       size;             /* allocated size */
    01885   struct malloc_segment* next;   /* ptr to next segment */
    01886   flag_t       sflags;           /* mmap and extern flag */
    01887 };
    01888
    01889 #define is_mmapped_segment(S)  ((S)->sflags & IS_MMAPPED_BIT)
    01890 #define is_extern_segment(S)   ((S)->sflags & EXTERN_BIT)
    01891
    01892 typedef struct malloc_segment  msegment;
    01893 typedef struct malloc_segment* msegmentptr;
    01894
    01895 /* ---------------------------- malloc_state ----------------------------- */
    01896
    01897 /*
    01898    A malloc_state holds all of the bookkeeping for a space.
    01899    The main fields are:
    01900
    01901   Top
    01902     The topmost chunk of the currently active segment. Its size is
    01903     cached in topsize.  The actual size of topmost space is
    01904     topsize+TOP_FOOT_SIZE, which includes space reserved for adding
    01905     fenceposts and segment records if necessary when getting more
    01906     space from the system.  The size at which to autotrim top is
    01907     cached from mparams in trim_check, except that it is disabled if
    01908     an autotrim fails.
    01909
    01910   Designated victim (dv)
    01911     This is the preferred chunk for servicing small requests that
    01912     don't have exact fits.  It is normally the chunk split off most
    01913     recently to service another small request.  Its size is cached in
    01914     dvsize. The link fields of this chunk are not maintained since it
    01915     is not kept in a bin.
    01916
    01917   SmallBins
    01918     An array of bin headers for free chunks.  These bins hold chunks
    01919     with sizes less than MIN_LARGE_SIZE bytes. Each bin contains
    01920     chunks of all the same size, spaced 8 bytes apart.  To simplify
    01921     use in double-linked lists, each bin header acts as a malloc_chunk
    01922     pointing to the real first node, if it exists (else pointing to
    01923     itself).  This avoids special-casing for headers.  But to avoid
    01924     waste, we allocate only the fd/bk pointers of bins, and then use
    01925     repositioning tricks to treat these as the fields of a chunk.
    01926
    01927   TreeBins
    01928     Treebins are pointers to the roots of trees holding a range of
    01929     sizes. There are 2 equally spaced treebins for each power of two
    01930     from TREE_SHIFT to TREE_SHIFT+16. The last bin holds anything
    01931     larger.
    01932
    01933   Bin maps
    01934     There is one bit map for small bins ("smallmap") and one for
    01935     treebins ("treemap).  Each bin sets its bit when non-empty, and
    01936     clears the bit when empty.  Bit operations are then used to avoid
    01937     bin-by-bin searching -- nearly all "search" is done without ever
    01938     looking at bins that won't be selected.  The bit maps
    01939     conservatively use 32 bits per map word, even if on 64bit system.
    01940     For a good description of some of the bit-based techniques used
    01941     here, see Henry S. Warren Jr's book "Hacker's Delight" (and
    01942     supplement at http://hackersdelight.org/). Many of these are
    01943     intended to reduce the branchiness of paths through malloc etc, as
    01944     well as to reduce the number of memory locations read or written.
    01945
    01946   Segments
    01947     A list of segments headed by an embedded malloc_segment record
    01948     representing the initial space.
    01949
    01950   Address check support
    01951     The least_addr field is the least address ever obtained from
    01952     MORECORE or MMAP. Attempted frees and reallocs of any address less
    01953     than this are trapped (unless INSECURE is defined).
    01954
    01955   Magic tag
    01956     A cross-check field that should always hold same value as mparams.magic.
    01957
    01958   Flags
    01959     Bits recording whether to use MMAP, locks, or contiguous MORECORE
    01960
    01961   Statistics
    01962     Each space keeps track of current and maximum system memory
    01963     obtained via MORECORE or MMAP.
    01964
    01965   Locking
    01966     If USE_LOCKS is defined, the "mutex" lock is acquired and released
    01967     around every public call using this mspace.
    01968 */
    01969
    01970 /* Bin types, widths and sizes */
    01971 #define NSMALLBINS        (32U)
    01972 #define NTREEBINS         (32U)
    01973 #define SMALLBIN_SHIFT    (3U)
    01974 #define SMALLBIN_WIDTH    (SIZE_T_ONE << SMALLBIN_SHIFT)
    01975 #define TREEBIN_SHIFT     (8U)
    01976 #define MIN_LARGE_SIZE    (SIZE_T_ONE << TREEBIN_SHIFT)
    01977 #define MAX_SMALL_SIZE    (MIN_LARGE_SIZE - SIZE_T_ONE)
    01978 #define MAX_SMALL_REQUEST (MAX_SMALL_SIZE - CHUNK_ALIGN_MASK - CHUNK_OVERHEAD)
    01979
    01980 struct malloc_state {
    01981   binmap_t   smallmap;
    01982   binmap_t   treemap;
    01983   size_t     dvsize;
    01984   size_t     topsize;
    01985   char*      least_addr;
    01986   mchunkptr  dv;
    01987   mchunkptr  top;
    01988   size_t     trim_check;
    01989   size_t     magic;
    01990   mchunkptr  smallbins[(NSMALLBINS+1)*2];
    01991   tbinptr    treebins[NTREEBINS];
    01992   size_t     footprint;
    01993   size_t     max_footprint;
    01994   flag_t     mflags;
    01995 #if USE_LOCKS
    01996   MLOCK_T    mutex;     /* locate lock among fields that rarely change */
    01997 #endif /* USE_LOCKS */
    01998   msegment   seg;
    01999 };
    02000
    02001 typedef struct malloc_state*    mstate;
    02002
    02003 /* ------------- Global malloc_state and malloc_params ------------------- */
    02004
    02005 /*
    02006   malloc_params holds global properties, including those that can be
    02007   dynamically set using mallopt. There is a single instance, mparams,
    02008   initialized in init_mparams.
    02009 */
    02010
    02011 struct malloc_params {
    02012   size_t magic;
    02013   size_t page_size;
    02014   size_t granularity;
    02015   size_t mmap_threshold;
    02016   size_t trim_threshold;
    02017   flag_t default_mflags;
    02018 };
    02019
    02020 static struct malloc_params mparams;
    02021
    02022 /* The global malloc_state used for all non-"mspace" calls */
    02023 static struct malloc_state _gm_;
    02024 #define gm                 (&_gm_)
    02025 #define is_global(M)       ((M) == &_gm_)
    02026 #define is_initialized(M)  ((M)->top != 0)
    02027
    02028 /* -------------------------- system alloc setup ------------------------- */
    02029
    02030 /* Operations on mflags */
    02031
    02032 #define use_lock(M)           ((M)->mflags &   USE_LOCK_BIT)
    02033 #define enable_lock(M)        ((M)->mflags |=  USE_LOCK_BIT)
    02034 #define disable_lock(M)       ((M)->mflags &= ~USE_LOCK_BIT)
    02035
    02036 #define use_mmap(M)           ((M)->mflags &   USE_MMAP_BIT)
    02037 #define enable_mmap(M)        ((M)->mflags |=  USE_MMAP_BIT)
    02038 #define disable_mmap(M)       ((M)->mflags &= ~USE_MMAP_BIT)
    02039
    02040 #define use_noncontiguous(M)  ((M)->mflags &   USE_NONCONTIGUOUS_BIT)
    02041 #define disable_contiguous(M) ((M)->mflags |=  USE_NONCONTIGUOUS_BIT)
    02042
    02043 #define set_lock(M,L)\
    02044  ((M)->mflags = (L)?\
    02045   ((M)->mflags | USE_LOCK_BIT) :\
    02046   ((M)->mflags & ~USE_LOCK_BIT))
    02047
    02048 /* page-align a size */
    02049 #define page_align(S)\
    02050  (((S) + (mparams.page_size)) & ~(mparams.page_size - SIZE_T_ONE))
    02051
    02052 /* granularity-align a size */
    02053 #define granularity_align(S)\
    02054   (((S) + (mparams.granularity)) & ~(mparams.granularity - SIZE_T_ONE))
    02055
    02056 #define is_page_aligned(S)\
    02057    (((size_t)(S) & (mparams.page_size - SIZE_T_ONE)) == 0)
    02058 #define is_granularity_aligned(S)\
    02059    (((size_t)(S) & (mparams.granularity - SIZE_T_ONE)) == 0)
    02060
    02061 /*  True if segment S holds address A */
    02062 #define segment_holds(S, A)\
    02063   ((char*)(A) >= S->base && (char*)(A) < S->base + S->size)
    02064
    02065 /* Return segment holding given address */
    02066 static msegmentptr segment_holding(mstate m, char* addr) {
    02067   msegmentptr sp = &m->seg;
    02068   for (;;) {
    02069     if (addr >= sp->base && addr < sp->base + sp->size)
    02070       return sp;
    02071     if ((sp = sp->next) == 0)
    02072       return 0;
    02073   }
    02074 }
    02075
    02076 /* Return true if segment contains a segment link */
    02077 static int has_segment_link(mstate m, msegmentptr ss) {
    02078   msegmentptr sp = &m->seg;
    02079   for (;;) {
    02080     if ((char*)sp >= ss->base && (char*)sp < ss->base + ss->size)
    02081       return 1;
    02082     if ((sp = sp->next) == 0)
    02083       return 0;
    02084   }
    02085 }
    02086
    02087 #ifndef MORECORE_CANNOT_TRIM
    02088 #define should_trim(M,s)  ((s) > (M)->trim_check)
    02089 #else  /* MORECORE_CANNOT_TRIM */
    02090 #define should_trim(M,s)  (0)
    02091 #endif /* MORECORE_CANNOT_TRIM */
    02092
    02093 /*
    02094   TOP_FOOT_SIZE is padding at the end of a segment, including space
    02095   that may be needed to place segment records and fenceposts when new
    02096   noncontiguous segments are added.
    02097 */
    02098 #define TOP_FOOT_SIZE\
    02099   (align_offset(chunk2mem(0))+pad_request(sizeof(struct malloc_segment))+MIN_CHUNK_SIZE)
    02100
    02101
    02102 /* -------------------------------  Hooks -------------------------------- */
    02103
    02104 /*
    02105   PREACTION should be defined to return 0 on success, and nonzero on
    02106   failure. If you are not using locking, you can redefine these to do
    02107   anything you like.
    02108 */
    02109
    02110 #if USE_LOCKS
    02111
    02112 /* Ensure locks are initialized */
    02113 #define GLOBALLY_INITIALIZE() (mparams.page_size == 0 && init_mparams())
    02114
    02115 #define PREACTION(M)  ((GLOBALLY_INITIALIZE() || use_lock(M))? ACQUIRE_LOCK(&(M)->mutex) : 0)
    02116 #define POSTACTION(M) { if (use_lock(M)) RELEASE_LOCK(&(M)->mutex); }
    02117 #else /* USE_LOCKS */
    02118
    02119 #ifndef PREACTION
    02120 #define PREACTION(M) (0)
    02121 #endif  /* PREACTION */
    02122
    02123 #ifndef POSTACTION
    02124 #define POSTACTION(M)
    02125 #endif  /* POSTACTION */
    02126
    02127 #endif /* USE_LOCKS */
    02128
    02129 /*
    02130   CORRUPTION_ERROR_ACTION is triggered upon detected bad addresses.
    02131   USAGE_ERROR_ACTION is triggered on detected bad frees and
    02132   reallocs. The argument p is an address that might have triggered the
    02133   fault. It is ignored by the two predefined actions, but might be
    02134   useful in custom actions that try to help diagnose errors.
    02135 */
    02136
    02137 #if PROCEED_ON_ERROR
    02138
    02139 /* A count of the number of corruption errors causing resets */
    02140 int malloc_corruption_error_count;
    02141
    02142 /* default corruption action */
    02143 static void reset_on_error(mstate m);
    02144
    02145 #define CORRUPTION_ERROR_ACTION(m)  reset_on_error(m)
    02146 #define USAGE_ERROR_ACTION(m, p)
    02147
    02148 #else /* PROCEED_ON_ERROR */
    02149
    02150 #ifndef CORRUPTION_ERROR_ACTION
    02151 #define CORRUPTION_ERROR_ACTION(m) ABORT
    02152 #endif /* CORRUPTION_ERROR_ACTION */
    02153
    02154 #ifndef USAGE_ERROR_ACTION
    02155 #define USAGE_ERROR_ACTION(m,p) ABORT
    02156 #endif /* USAGE_ERROR_ACTION */
    02157
    02158 #endif /* PROCEED_ON_ERROR */
    02159
    02160 /* -------------------------- Debugging setup ---------------------------- */
    02161
    02162 #if ! DEBUG
    02163
    02164 #define check_free_chunk(M,P)
    02165 #define check_inuse_chunk(M,P)
    02166 #define check_malloced_chunk(M,P,N)
    02167 #define check_mmapped_chunk(M,P)
    02168 #define check_malloc_state(M)
    02169 #define check_top_chunk(M,P)
    02170
    02171 #else /* DEBUG */
    02172 #define check_free_chunk(M,P)       do_check_free_chunk(M,P)
    02173 #define check_inuse_chunk(M,P)      do_check_inuse_chunk(M,P)
    02174 #define check_top_chunk(M,P)        do_check_top_chunk(M,P)
    02175 #define check_malloced_chunk(M,P,N) do_check_malloced_chunk(M,P,N)
    02176 #define check_mmapped_chunk(M,P)    do_check_mmapped_chunk(M,P)
    02177 #define check_malloc_state(M)       do_check_malloc_state(M)
    02178
    02179 static void   do_check_any_chunk(mstate m, mchunkptr p);
    02180 static void   do_check_top_chunk(mstate m, mchunkptr p);
    02181 static void   do_check_mmapped_chunk(mstate m, mchunkptr p);
    02182 static void   do_check_inuse_chunk(mstate m, mchunkptr p);
    02183 static void   do_check_free_chunk(mstate m, mchunkptr p);
    02184 static void   do_check_malloced_chunk(mstate m, void* mem, size_t s);
    02185 static void   do_check_tree(mstate m, tchunkptr t);
    02186 static void   do_check_treebin(mstate m, bindex_t i);
    02187 static void   do_check_smallbin(mstate m, bindex_t i);
    02188 static void   do_check_malloc_state(mstate m);
    02189 static int    bin_find(mstate m, mchunkptr x);
    02190 static size_t traverse_and_check(mstate m);
    02191 #endif /* DEBUG */
    02192
    02193 /* ---------------------------- Indexing Bins ---------------------------- */
    02194
    02195 #define is_small(s)         (((s) >> SMALLBIN_SHIFT) < NSMALLBINS)
    02196 #define small_index(s)      ((s)  >> SMALLBIN_SHIFT)
    02197 #define small_index2size(i) ((i)  << SMALLBIN_SHIFT)
    02198 #define MIN_SMALL_INDEX     (small_index(MIN_CHUNK_SIZE))
    02199
    02200 /* addressing by index. See above about smallbin repositioning */
    02201 #define smallbin_at(M, i)   ((sbinptr)((char*)&((M)->smallbins[(i)<<1])))
    02202 #define treebin_at(M,i)     (&((M)->treebins[i]))
    02203
    02204 /* assign tree index for size S to variable I */
    02205 #if defined(__GNUC__) && defined(i386)
    02206 #define compute_tree_index(S, I)\
    02207 {\
    02208   size_t X = S >> TREEBIN_SHIFT;\
    02209   if (X == 0)\
    02210     I = 0;\
    02211   else if (X > 0xFFFF)\
    02212     I = NTREEBINS-1;\
    02213   else {\
    02214     unsigned int K;\
    02215     __asm__("bsrl %1,%0\n\t" : "=r" (K) : "rm"  (X));\
    02216     I =  (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
    02217   }\
    02218 }
    02219 #else /* GNUC */
    02220 #define compute_tree_index(S, I)\
    02221 {\
    02222   size_t X = S >> TREEBIN_SHIFT;\
    02223   if (X == 0)\
    02224     I = 0;\
    02225   else if (X > 0xFFFF)\
    02226     I = NTREEBINS-1;\
    02227   else {\
    02228     unsigned int Y = (unsigned int)X;\
    02229     unsigned int N = ((Y - 0x100) >> 16) & 8;\
    02230     unsigned int K = (((Y <<= N) - 0x1000) >> 16) & 4;\
    02231     N += K;\
    02232     N += K = (((Y <<= K) - 0x4000) >> 16) & 2;\
    02233     K = 14 - N + ((Y <<= K) >> 15);\
    02234     I = (K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1));\
    02235   }\
    02236 }
    02237 #endif /* GNUC */
    02238
    02239 /* Bit representing maximum resolved size in a treebin at i */
    02240 #define bit_for_tree_index(i) \
    02241    (i == NTREEBINS-1)? (SIZE_T_BITSIZE-1) : (((i) >> 1) + TREEBIN_SHIFT - 2)
    02242
    02243 /* Shift placing maximum resolved bit in a treebin at i as sign bit */
    02244 #define leftshift_for_tree_index(i) \
    02245    ((i == NTREEBINS-1)? 0 : \
    02246     ((SIZE_T_BITSIZE-SIZE_T_ONE) - (((i) >> 1) + TREEBIN_SHIFT - 2)))
    02247
    02248 /* The size of the smallest chunk held in bin with index i */
    02249 #define minsize_for_tree_index(i) \
    02250    ((SIZE_T_ONE << (((i) >> 1) + TREEBIN_SHIFT)) |  \
    02251    (((size_t)((i) & SIZE_T_ONE)) << (((i) >> 1) + TREEBIN_SHIFT - 1)))
    02252
    02253
    02254 /* ------------------------ Operations on bin maps ----------------------- */
    02255
    02256 /* bit corresponding to given index */
    02257 #define idx2bit(i)              ((binmap_t)(1) << (i))
    02258
    02259 /* Mark/Clear bits with given index */
    02260 #define mark_smallmap(M,i)      ((M)->smallmap |=  idx2bit(i))
    02261 #define clear_smallmap(M,i)     ((M)->smallmap &= ~idx2bit(i))
    02262 #define smallmap_is_marked(M,i) ((M)->smallmap &   idx2bit(i))
    02263
    02264 #define mark_treemap(M,i)       ((M)->treemap  |=  idx2bit(i))
    02265 #define clear_treemap(M,i)      ((M)->treemap  &= ~idx2bit(i))
    02266 #define treemap_is_marked(M,i)  ((M)->treemap  &   idx2bit(i))
    02267
    02268 /* index corresponding to given bit */
    02269
    02270 #if defined(__GNUC__) && defined(i386)
    02271 #define compute_bit2idx(X, I)\
    02272 {\
    02273   unsigned int J;\
    02274   __asm__("bsfl %1,%0\n\t" : "=r" (J) : "rm" (X));\
    02275   I = (bindex_t)J;\
    02276 }
    02277
    02278 #else /* GNUC */
    02279 #if  USE_BUILTIN_FFS
    02280 #define compute_bit2idx(X, I) I = ffs(X)-1
    02281
    02282 #else /* USE_BUILTIN_FFS */
    02283 #define compute_bit2idx(X, I)\
    02284 {\
    02285   unsigned int Y = X - 1;\
    02286   unsigned int K = Y >> (16-4) & 16;\
    02287   unsigned int N = K;        Y >>= K;\
    02288   N += K = Y >> (8-3) &  8;  Y >>= K;\
    02289   N += K = Y >> (4-2) &  4;  Y >>= K;\
    02290   N += K = Y >> (2-1) &  2;  Y >>= K;\
    02291   N += K = Y >> (1-0) &  1;  Y >>= K;\
    02292   I = (bindex_t)(N + Y);\
    02293 }
    02294 #endif /* USE_BUILTIN_FFS */
    02295 #endif /* GNUC */
    02296
    02297 /* isolate the least set bit of a bitmap */
    02298 #define least_bit(x)         ((x) & -(x))
    02299
    02300 /* mask with all bits to left of least bit of x on */
    02301 #define left_bits(x)         ((x<<1) | -(x<<1))
    02302
    02303 /* mask with all bits to left of or equal to least bit of x on */
    02304 #define same_or_left_bits(x) ((x) | -(x))
    02305
    02306
    02307 /* ----------------------- Runtime Check Support ------------------------- */
    02308
    02309 /*
    02310   For security, the main invariant is that malloc/free/etc never
    02311   writes to a static address other than malloc_state, unless static
    02312   malloc_state itself has been corrupted, which cannot occur via
    02313   malloc (because of these checks). In essence this means that we
    02314   believe all pointers, sizes, maps etc held in malloc_state, but
    02315   check all of those linked or offsetted from other embedded data
    02316   structures.  These checks are interspersed with main code in a way
    02317   that tends to minimize their run-time cost.
    02318
    02319   When FOOTERS is defined, in addition to range checking, we also
    02320   verify footer fields of inuse chunks, which can be used guarantee
    02321   that the mstate controlling malloc/free is intact.  This is a
    02322   streamlined version of the approach described by William Robertson
    02323   et al in "Run-time Detection of Heap-based Overflows" LISA'03
    02324   http://www.usenix.org/events/lisa03/tech/robertson.html The footer
    02325   of an inuse chunk holds the xor of its mstate and a random seed,
    02326   that is checked upon calls to free() and realloc().  This is
    02327   (probablistically) unguessable from outside the program, but can be
    02328   computed by any code successfully malloc'ing any chunk, so does not
    02329   itself provide protection against code that has already broken
    02330   security through some other means.  Unlike Robertson et al, we
    02331   always dynamically check addresses of all offset chunks (previous,
    02332   next, etc). This turns out to be cheaper than relying on hashes.
    02333 */
    02334
    02335 #if !INSECURE
    02336 /* Check if address a is at least as high as any from MORECORE or MMAP */
    02337 #define ok_address(M, a) ((char*)(a) >= (M)->least_addr)
    02338 /* Check if address of next chunk n is higher than base chunk p */
    02339 #define ok_next(p, n)    ((char*)(p) < (char*)(n))
    02340 /* Check if p has its cinuse bit on */
    02341 #define ok_cinuse(p)     cinuse(p)
    02342 /* Check if p has its pinuse bit on */
    02343 #define ok_pinuse(p)     pinuse(p)
    02344
    02345 #else /* !INSECURE */
    02346 #define ok_address(M, a) (1)
    02347 #define ok_next(b, n)    (1)
    02348 #define ok_cinuse(p)     (1)
    02349 #define ok_pinuse(p)     (1)
    02350 #endif /* !INSECURE */
    02351
    02352 #if (FOOTERS && !INSECURE)
    02353 /* Check if (alleged) mstate m has expected magic field */
    02354 #define ok_magic(M)      ((M)->magic == mparams.magic)
    02355 #else  /* (FOOTERS && !INSECURE) */
    02356 #define ok_magic(M)      (1)
    02357 #endif /* (FOOTERS && !INSECURE) */
    02358
    02359
    02360 /* In gcc, use __builtin_expect to minimize impact of checks */
    02361 #if !INSECURE
    02362 #if defined(__GNUC__) && __GNUC__ >= 3
    02363 #define RTCHECK(e)  __builtin_expect(e, 1)
    02364 #else /* GNUC */
    02365 #define RTCHECK(e)  (e)
    02366 #endif /* GNUC */
    02367 #else /* !INSECURE */
    02368 #define RTCHECK(e)  (1)
    02369 #endif /* !INSECURE */
    02370
    02371 /* macros to set up inuse chunks with or without footers */
    02372
    02373 #if !FOOTERS
    02374
    02375 #define mark_inuse_foot(M,p,s)
    02376
    02377 /* Set cinuse bit and pinuse bit of next chunk */
    02378 #define set_inuse(M,p,s)\
    02379   ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
    02380   ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
    02381
    02382 /* Set cinuse and pinuse of this chunk and pinuse of next chunk */
    02383 #define set_inuse_and_pinuse(M,p,s)\
    02384   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
    02385   ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
    02386
    02387 /* Set size, cinuse and pinuse bit of this chunk */
    02388 #define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
    02389   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT))
    02390
    02391 #else /* FOOTERS */
    02392
    02393 /* Set foot of inuse chunk to be xor of mstate and seed */
    02394 #define mark_inuse_foot(M,p,s)\
    02395   (((mchunkptr)((char*)(p) + (s)))->prev_foot = ((size_t)(M) ^ mparams.magic))
    02396
    02397 #define get_mstate_for(p)\
    02398   ((mstate)(((mchunkptr)((char*)(p) +\
    02399     (chunksize(p))))->prev_foot ^ mparams.magic))
    02400
    02401 #define set_inuse(M,p,s)\
    02402   ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
    02403   (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT), \
    02404   mark_inuse_foot(M,p,s))
    02405
    02406 #define set_inuse_and_pinuse(M,p,s)\
    02407   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
    02408   (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT),\
    02409  mark_inuse_foot(M,p,s))
    02410
    02411 #define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
    02412   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
    02413   mark_inuse_foot(M, p, s))
    02414
    02415 #endif /* !FOOTERS */
    02416
    02417 /* ---------------------------- setting mparams -------------------------- */
    02418
    02419 /* Initialize mparams */
    02420 static int init_mparams(void) {
    02421   if (mparams.page_size == 0) {
    02422     size_t s;
    02423
    02424     mparams.mmap_threshold = DEFAULT_MMAP_THRESHOLD;
    02425     mparams.trim_threshold = DEFAULT_TRIM_THRESHOLD;
    02426 #if MORECORE_CONTIGUOUS
    02427     mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT;
    02428 #else  /* MORECORE_CONTIGUOUS */
    02429     mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT|USE_NONCONTIGUOUS_BIT;
    02430 #endif /* MORECORE_CONTIGUOUS */
    02431
    02432 #if (FOOTERS && !INSECURE)
    02433     {
    02434 #if USE_DEV_RANDOM
    02435       int fd;
    02436       unsigned char buf[sizeof(size_t)];
    02437       /* Try to use /dev/urandom, else fall back on using time */
    02438       if ((fd = open("/dev/urandom", O_RDONLY)) >= 0 &&
    02439           read(fd, buf, sizeof(buf)) == sizeof(buf)) {
    02440         s = *((size_t *) buf);
    02441         close(fd);
    02442       }
    02443       else
    02444 #endif /* USE_DEV_RANDOM */
    02445         s = (size_t)(time(0) ^ (size_t)0x55555555U);
    02446
    02447       s |= (size_t)8U;    /* ensure nonzero */
    02448       s &= ~(size_t)7U;   /* improve chances of fault for bad values */
    02449
    02450     }
    02451 #else /* (FOOTERS && !INSECURE) */
    02452     s = (size_t)0x58585858U;
    02453 #endif /* (FOOTERS && !INSECURE) */
    02454     ACQUIRE_MAGIC_INIT_LOCK();
    02455     if (mparams.magic == 0) {
    02456       mparams.magic = s;
    02457       /* Set up lock for main malloc area */
    02458       INITIAL_LOCK(&gm->mutex);
    02459       gm->mflags = mparams.default_mflags;
    02460     }
    02461     RELEASE_MAGIC_INIT_LOCK();
    02462
    02463 #ifndef WIN32
    02464     mparams.page_size = malloc_getpagesize;
    02465     mparams.granularity = ((DEFAULT_GRANULARITY != 0)?
    02466                            DEFAULT_GRANULARITY : mparams.page_size);
    02467 #else /* WIN32 */
    02468     {
    02469       SYSTEM_INFO system_info;
    02470       GetSystemInfo(&system_info);
    02471       mparams.page_size = system_info.dwPageSize;
    02472       mparams.granularity = system_info.dwAllocationGranularity;
    02473     }
    02474 #endif /* WIN32 */
    02475
    02476     /* Sanity-check configuration:
    02477        size_t must be unsigned and as wide as pointer type.
    02478        ints must be at least 4 bytes.
    02479        alignment must be at least 8.
    02480        Alignment, min chunk size, and page size must all be powers of 2.
    02481     */
    02482     if ((sizeof(size_t) != sizeof(char*)) ||
    02483         (MAX_SIZE_T < MIN_CHUNK_SIZE)  ||
    02484         (sizeof(int) < 4)  ||
    02485         (MALLOC_ALIGNMENT < (size_t)8U) ||
    02486         ((MALLOC_ALIGNMENT    & (MALLOC_ALIGNMENT-SIZE_T_ONE))    != 0) ||
    02487         ((MCHUNK_SIZE         & (MCHUNK_SIZE-SIZE_T_ONE))         != 0) ||
    02488         ((mparams.granularity & (mparams.granularity-SIZE_T_ONE)) != 0) ||
    02489         ((mparams.page_size   & (mparams.page_size-SIZE_T_ONE))   != 0))
    02490       ABORT;
    02491   }
    02492   return 0;
    02493 }
    02494
    02495 /* support for mallopt */
    02496 static int change_mparam(int param_number, int value) {
    02497   size_t val = (size_t)value;
    02498   init_mparams();
    02499   switch(param_number) {
    02500   case M_TRIM_THRESHOLD:
    02501     mparams.trim_threshold = val;
    02502     return 1;
    02503   case M_GRANULARITY:
    02504     if (val >= mparams.page_size && ((val & (val-1)) == 0)) {
    02505       mparams.granularity = val;
    02506       return 1;
    02507     }
    02508     else
    02509       return 0;
    02510   case M_MMAP_THRESHOLD:
    02511     mparams.mmap_threshold = val;
    02512     return 1;
    02513   default:
    02514     return 0;
    02515   }
    02516 }
    02517
    02518 #if DEBUG
    02519 /* ------------------------- Debugging Support --------------------------- */
    02520
    02521 /* Check properties of any chunk, whether free, inuse, mmapped etc  */
    02522 static void do_check_any_chunk(mstate m, mchunkptr p) {
    02523   assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
    02524   assert(ok_address(m, p));
    02525 }
    02526
    02527 /* Check properties of top chunk */
    02528 static void do_check_top_chunk(mstate m, mchunkptr p) {
    02529   msegmentptr sp = segment_holding(m, (char*)p);
    02530   size_t  sz = chunksize(p);
    02531   assert(sp != 0);
    02532   assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
    02533   assert(ok_address(m, p));
    02534   assert(sz == m->topsize);
    02535   assert(sz > 0);
    02536   assert(sz == ((sp->base + sp->size) - (char*)p) - TOP_FOOT_SIZE);
    02537   assert(pinuse(p));
    02538   assert(!next_pinuse(p));
    02539 }
    02540
    02541 /* Check properties of (inuse) mmapped chunks */
    02542 static void do_check_mmapped_chunk(mstate m, mchunkptr p) {
    02543   size_t  sz = chunksize(p);
    02544   size_t len = (sz + (p->prev_foot & ~IS_MMAPPED_BIT) + MMAP_FOOT_PAD);
    02545   assert(is_mmapped(p));
    02546   assert(use_mmap(m));
    02547   assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
    02548   assert(ok_address(m, p));
    02549   assert(!is_small(sz));
    02550   assert((len & (mparams.page_size-SIZE_T_ONE)) == 0);
    02551   assert(chunk_plus_offset(p, sz)->head == FENCEPOST_HEAD);
    02552   assert(chunk_plus_offset(p, sz+SIZE_T_SIZE)->head == 0);
    02553 }
    02554
    02555 /* Check properties of inuse chunks */
    02556 static void do_check_inuse_chunk(mstate m, mchunkptr p) {
    02557   do_check_any_chunk(m, p);
    02558   assert(cinuse(p));
    02559   assert(next_pinuse(p));
    02560   /* If not pinuse and not mmapped, previous chunk has OK offset */
    02561   assert(is_mmapped(p) || pinuse(p) || next_chunk(prev_chunk(p)) == p);
    02562   if (is_mmapped(p))
    02563     do_check_mmapped_chunk(m, p);
    02564 }
    02565
    02566 /* Check properties of free chunks */
    02567 static void do_check_free_chunk(mstate m, mchunkptr p) {
    02568   size_t sz = p->head & ~(PINUSE_BIT|CINUSE_BIT);
    02569   mchunkptr next = chunk_plus_offset(p, sz);
    02570   do_check_any_chunk(m, p);
    02571   assert(!cinuse(p));
    02572   assert(!next_pinuse(p));
    02573   assert (!is_mmapped(p));
    02574   if (p != m->dv && p != m->top) {
    02575     if (sz >= MIN_CHUNK_SIZE) {
    02576       assert((sz & CHUNK_ALIGN_MASK) == 0);
    02577       assert(is_aligned(chunk2mem(p)));
    02578       assert(next->prev_foot == sz);
    02579       assert(pinuse(p));
    02580       assert (next == m->top || cinuse(next));
    02581       assert(p->fd->bk == p);
    02582       assert(p->bk->fd == p);
    02583     }
    02584     else  /* markers are always of size SIZE_T_SIZE */
    02585       assert(sz == SIZE_T_SIZE);
    02586   }
    02587 }
    02588
    02589 /* Check properties of malloced chunks at the point they are malloced */
    02590 static void do_check_malloced_chunk(mstate m, void* mem, size_t s) {
    02591   if (mem != 0) {
    02592     mchunkptr p = mem2chunk(mem);
    02593     size_t sz = p->head & ~(PINUSE_BIT|CINUSE_BIT);
    02594     do_check_inuse_chunk(m, p);
    02595     assert((sz & CHUNK_ALIGN_MASK) == 0);
    02596     assert(sz >= MIN_CHUNK_SIZE);
    02597     assert(sz >= s);
    02598     /* unless mmapped, size is less than MIN_CHUNK_SIZE more than request */
    02599     assert(is_mmapped(p) || sz < (s + MIN_CHUNK_SIZE));
    02600   }
    02601 }
    02602
    02603 /* Check a tree and its subtrees.  */
    02604 static void do_check_tree(mstate m, tchunkptr t) {
    02605   tchunkptr head = 0;
    02606   tchunkptr u = t;
    02607   bindex_t tindex = t->index;
    02608   size_t tsize = chunksize(t);
    02609   bindex_t idx;
    02610   compute_tree_index(tsize, idx);
    02611   assert(tindex == idx);
    02612   assert(tsize >= MIN_LARGE_SIZE);
    02613   assert(tsize >= minsize_for_tree_index(idx));
    02614   assert((idx == NTREEBINS-1) || (tsize < minsize_for_tree_index((idx+1))));
    02615
    02616   do { /* traverse through chain of same-sized nodes */
    02617     do_check_any_chunk(m, ((mchunkptr)u));
    02618     assert(u->index == tindex);
    02619     assert(chunksize(u) == tsize);
    02620     assert(!cinuse(u));
    02621     assert(!next_pinuse(u));
    02622     assert(u->fd->bk == u);
    02623     assert(u->bk->fd == u);
    02624     if (u->parent == 0) {
    02625       assert(u->child[0] == 0);
    02626       assert(u->child[1] == 0);
    02627     }
    02628     else {
    02629       assert(head == 0); /* only one node on chain has parent */
    02630       head = u;
    02631       assert(u->parent != u);
    02632       assert (u->parent->child[0] == u ||
    02633               u->parent->child[1] == u ||
    02634               *((tbinptr*)(u->parent)) == u);
    02635       if (u->child[0] != 0) {
    02636         assert(u->child[0]->parent == u);
    02637         assert(u->child[0] != u);
    02638         do_check_tree(m, u->child[0]);
    02639       }
    02640       if (u->child[1] != 0) {
    02641         assert(u->child[1]->parent == u);
    02642         assert(u->child[1] != u);
    02643         do_check_tree(m, u->child[1]);
    02644       }
    02645       if (u->child[0] != 0 && u->child[1] != 0) {
    02646         assert(chunksize(u->child[0]) < chunksize(u->child[1]));
    02647       }
    02648     }
    02649     u = u->fd;
    02650   } while (u != t);
    02651   assert(head != 0);
    02652 }
    02653
    02654 /*  Check all the chunks in a treebin.  */
    02655 static void do_check_treebin(mstate m, bindex_t i) {
    02656   tbinptr* tb = treebin_at(m, i);
    02657   tchunkptr t = *tb;
    02658   int empty = (m->treemap & (1U << i)) == 0;
    02659   if (t == 0)
    02660     assert(empty);
    02661   if (!empty)
    02662     do_check_tree(m, t);
    02663 }
    02664
    02665 /*  Check all the chunks in a smallbin.  */
    02666 static void do_check_smallbin(mstate m, bindex_t i) {
    02667   sbinptr b = smallbin_at(m, i);
    02668   mchunkptr p = b->bk;
    02669   unsigned int empty = (m->smallmap & (1U << i)) == 0;
    02670   if (p == b)
    02671     assert(empty);
    02672   if (!empty) {
    02673     for (; p != b; p = p->bk) {
    02674       size_t size = chunksize(p);
    02675       mchunkptr q;
    02676       /* each chunk claims to be free */
    02677       do_check_free_chunk(m, p);
    02678       /* chunk belongs in bin */
    02679       assert(small_index(size) == i);
    02680       assert(p->bk == b || chunksize(p->bk) == chunksize(p));
    02681       /* chunk is followed by an inuse chunk */
    02682       q = next_chunk(p);
    02683       if (q->head != FENCEPOST_HEAD)
    02684         do_check_inuse_chunk(m, q);
    02685     }
    02686   }
    02687 }
    02688
    02689 /* Find x in a bin. Used in other check functions. */
    02690 static int bin_find(mstate m, mchunkptr x) {
    02691   size_t size = chunksize(x);
    02692   if (is_small(size)) {
    02693     bindex_t sidx = small_index(size);
    02694     sbinptr b = smallbin_at(m, sidx);
    02695     if (smallmap_is_marked(m, sidx)) {
    02696       mchunkptr p = b;
    02697       do {
    02698         if (p == x)
    02699           return 1;
    02700       } while ((p = p->fd) != b);
    02701     }
    02702   }
    02703   else {
    02704     bindex_t tidx;
    02705     compute_tree_index(size, tidx);
    02706     if (treemap_is_marked(m, tidx)) {
    02707       tchunkptr t = *treebin_at(m, tidx);
    02708       size_t sizebits = size << leftshift_for_tree_index(tidx);
    02709       while (t != 0 && chunksize(t) != size) {
    02710         t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
    02711         sizebits <<= 1;
    02712       }
    02713       if (t != 0) {
    02714         tchunkptr u = t;
    02715         do {
    02716           if (u == (tchunkptr)x)
    02717             return 1;
    02718         } while ((u = u->fd) != t);
    02719       }
    02720     }
    02721   }
    02722   return 0;
    02723 }
    02724
    02725 /* Traverse each chunk and check it; return total */
    02726 static size_t traverse_and_check(mstate m) {
    02727   size_t sum = 0;
    02728   if (is_initialized(m)) {
    02729     msegmentptr s = &m->seg;
    02730     sum += m->topsize + TOP_FOOT_SIZE;
    02731     while (s != 0) {
    02732       mchunkptr q = align_as_chunk(s->base);
    02733       mchunkptr lastq = 0;
    02734       assert(pinuse(q));
    02735       while (segment_holds(s, q) &&
    02736              q != m->top && q->head != FENCEPOST_HEAD) {
    02737         sum += chunksize(q);
    02738         if (cinuse(q)) {
    02739           assert(!bin_find(m, q));
    02740           do_check_inuse_chunk(m, q);
    02741         }
    02742         else {
    02743           assert(q == m->dv || bin_find(m, q));
    02744           assert(lastq == 0 || cinuse(lastq)); /* Not 2 consecutive free */
    02745           do_check_free_chunk(m, q);
    02746         }
    02747         lastq = q;
    02748         q = next_chunk(q);
    02749       }
    02750       s = s->next;
    02751     }
    02752   }
    02753   return sum;
    02754 }
    02755
    02756 /* Check all properties of malloc_state. */
    02757 static void do_check_malloc_state(mstate m) {
    02758   bindex_t i;
    02759   size_t total;
    02760   /* check bins */
    02761   for (i = 0; i < NSMALLBINS; ++i)
    02762     do_check_smallbin(m, i);
    02763   for (i = 0; i < NTREEBINS; ++i)
    02764     do_check_treebin(m, i);
    02765
    02766   if (m->dvsize != 0) { /* check dv chunk */
    02767     do_check_any_chunk(m, m->dv);
    02768     assert(m->dvsize == chunksize(m->dv));
    02769     assert(m->dvsize >= MIN_CHUNK_SIZE);
    02770     assert(bin_find(m, m->dv) == 0);
    02771   }
    02772
    02773   if (m->top != 0) {   /* check top chunk */
    02774     do_check_top_chunk(m, m->top);
    02775     assert(m->topsize == chunksize(m->top));
    02776     assert(m->topsize > 0);
    02777     assert(bin_find(m, m->top) == 0);
    02778   }
    02779
    02780   total = traverse_and_check(m);
    02781   assert(total <= m->footprint);
    02782   assert(m->footprint <= m->max_footprint);
    02783 }
    02784 #endif /* DEBUG */
    02785
    02786 /* ----------------------------- statistics ------------------------------ */
    02787
    02788 #if !NO_MALLINFO
    02789 static struct mallinfo internal_mallinfo(mstate m) {
    02790   struct mallinfo nm = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
    02791   if (!PREACTION(m)) {
    02792     check_malloc_state(m);
    02793     if (is_initialized(m)) {
    02794       size_t nfree = SIZE_T_ONE; /* top always free */
    02795       size_t mfree = m->topsize + TOP_FOOT_SIZE;
    02796       size_t sum = mfree;
    02797       msegmentptr s = &m->seg;
    02798       while (s != 0) {
    02799         mchunkptr q = align_as_chunk(s->base);
    02800         while (segment_holds(s, q) &&
    02801                q != m->top && q->head != FENCEPOST_HEAD) {
    02802           size_t sz = chunksize(q);
    02803           sum += sz;
    02804           if (!cinuse(q)) {
    02805             mfree += sz;
    02806             ++nfree;
    02807           }
    02808           q = next_chunk(q);
    02809         }
    02810         s = s->next;
    02811       }
    02812
    02813       nm.arena    = sum;
    02814       nm.ordblks  = nfree;
    02815       nm.hblkhd   = m->footprint - sum;
    02816       nm.usmblks  = m->max_footprint;
    02817       nm.uordblks = m->footprint - mfree;
    02818       nm.fordblks = mfree;
    02819       nm.keepcost = m->topsize;
    02820     }
    02821
    02822     POSTACTION(m);
    02823   }
    02824   return nm;
    02825 }
    02826 #endif /* !NO_MALLINFO */
    02827
    02828 static void internal_malloc_stats(mstate m) {
    02829   if (!PREACTION(m)) {
    02830     size_t maxfp = 0;
    02831     size_t fp = 0;
    02832     size_t used = 0;
    02833     check_malloc_state(m);
    02834     if (is_initialized(m)) {
    02835       msegmentptr s = &m->seg;
    02836       maxfp = m->max_footprint;
    02837       fp = m->footprint;
    02838       used = fp - (m->topsize + TOP_FOOT_SIZE);
    02839
    02840       while (s != 0) {
    02841         mchunkptr q = align_as_chunk(s->base);
    02842         while (segment_holds(s, q) &&
    02843                q != m->top && q->head != FENCEPOST_HEAD) {
    02844           if (!cinuse(q))
    02845             used -= chunksize(q);
    02846           q = next_chunk(q);
    02847         }
    02848         s = s->next;
    02849       }
    02850     }
    02851
    02852     fprintf(stderr, "max system bytes = %10lu\n", (unsigned long)(maxfp));
    02853     fprintf(stderr, "system bytes     = %10lu\n", (unsigned long)(fp));
    02854     fprintf(stderr, "in use bytes     = %10lu\n", (unsigned long)(used));
    02855
    02856     POSTACTION(m);
    02857   }
    02858 }
    02859
    02860 /* ----------------------- Operations on smallbins ----------------------- */
    02861
    02862 /*
    02863   Various forms of linking and unlinking are defined as macros.  Even
    02864   the ones for trees, which are very long but have very short typical
    02865   paths.  This is ugly but reduces reliance on inlining support of
    02866   compilers.
    02867 */
    02868
    02869 /* Link a free chunk into a smallbin  */
    02870 #define insert_small_chunk(M, P, S) {\
    02871   bindex_t I  = small_index(S);\
    02872   mchunkptr B = smallbin_at(M, I);\
    02873   mchunkptr F = B;\
    02874   assert(S >= MIN_CHUNK_SIZE);\
    02875   if (!smallmap_is_marked(M, I))\
    02876     mark_smallmap(M, I);\
    02877   else if (RTCHECK(ok_address(M, B->fd)))\
    02878     F = B->fd;\
    02879   else {\
    02880     CORRUPTION_ERROR_ACTION(M);\
    02881   }\
    02882   B->fd = P;\
    02883   F->bk = P;\
    02884   P->fd = F;\
    02885   P->bk = B;\
    02886 }
    02887
    02888 /* Unlink a chunk from a smallbin  */
    02889 #define unlink_small_chunk(M, P, S) {\
    02890   mchunkptr F = P->fd;\
    02891   mchunkptr B = P->bk;\
    02892   bindex_t I = small_index(S);\
    02893   assert(P != B);\
    02894   assert(P != F);\
    02895   assert(chunksize(P) == small_index2size(I));\
    02896   if (F == B)\
    02897     clear_smallmap(M, I);\
    02898   else if (RTCHECK((F == smallbin_at(M,I) || ok_address(M, F)) &&\
    02899                    (B == smallbin_at(M,I) || ok_address(M, B)))) {\
    02900     F->bk = B;\
    02901     B->fd = F;\
    02902   }\
    02903   else {\
    02904     CORRUPTION_ERROR_ACTION(M);\
    02905   }\
    02906 }
    02907
    02908 /* Unlink the first chunk from a smallbin */
    02909 #define unlink_first_small_chunk(M, B, P, I) {\
    02910   mchunkptr F = P->fd;\
    02911   assert(P != B);\
    02912   assert(P != F);\
    02913   assert(chunksize(P) == small_index2size(I));\
    02914   if (B == F)\
    02915     clear_smallmap(M, I);\
    02916   else if (RTCHECK(ok_address(M, F))) {\
    02917     B->fd = F;\
    02918     F->bk = B;\
    02919   }\
    02920   else {\
    02921     CORRUPTION_ERROR_ACTION(M);\
    02922   }\
    02923 }
    02924
    02925 /* Replace dv node, binning the old one */
    02926 /* Used only when dvsize known to be small */
    02927 #define replace_dv(M, P, S) {\
    02928   size_t DVS = M->dvsize;\
    02929   if (DVS != 0) {\
    02930     mchunkptr DV = M->dv;\
    02931     assert(is_small(DVS));\
    02932     insert_small_chunk(M, DV, DVS);\
    02933   }\
    02934   M->dvsize = S;\
    02935   M->dv = P;\
    02936 }
    02937
    02938 /* ------------------------- Operations on trees ------------------------- */
    02939
    02940 /* Insert chunk into tree */
    02941 #define insert_large_chunk(M, X, S) {\
    02942   tbinptr* H;\
    02943   bindex_t I;\
    02944   compute_tree_index(S, I);\
    02945   H = treebin_at(M, I);\
    02946   X->index = I;\
    02947   X->child[0] = X->child[1] = 0;\
    02948   if (!treemap_is_marked(M, I)) {\
    02949     mark_treemap(M, I);\
    02950     *H = X;\
    02951     X->parent = (tchunkptr)H;\
    02952     X->fd = X->bk = X;\
    02953   }\
    02954   else {\
    02955     tchunkptr T = *H;\
    02956     size_t K = S << leftshift_for_tree_index(I);\
    02957     for (;;) {\
    02958       if (chunksize(T) != S) {\
    02959         tchunkptr* C = &(T->child[(K >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1]);\
    02960         K <<= 1;\
    02961         if (*C != 0)\
    02962           T = *C;\
    02963         else if (RTCHECK(ok_address(M, C))) {\
    02964           *C = X;\
    02965           X->parent = T;\
    02966           X->fd = X->bk = X;\
    02967           break;\
    02968         }\
    02969         else {\
    02970           CORRUPTION_ERROR_ACTION(M);\
    02971           break;\
    02972         }\
    02973       }\
    02974       else {\
    02975         tchunkptr F = T->fd;\
    02976         if (RTCHECK(ok_address(M, T) && ok_address(M, F))) {\
    02977           T->fd = F->bk = X;\
    02978           X->fd = F;\
    02979           X->bk = T;\
    02980           X->parent = 0;\
    02981           break;\
    02982         }\
    02983         else {\
    02984           CORRUPTION_ERROR_ACTION(M);\
    02985           break;\
    02986         }\
    02987       }\
    02988     }\
    02989   }\
    02990 }
    02991
    02992 /*
    02993   Unlink steps:
    02994
    02995   1. If x is a chained node, unlink it from its same-sized fd/bk links
    02996      and choose its bk node as its replacement.
    02997   2. If x was the last node of its size, but not a leaf node, it must
    02998      be replaced with a leaf node (not merely one with an open left or
    02999      right), to make sure that lefts and rights of descendents
    03000      correspond properly to bit masks.  We use the rightmost descendent
    03001      of x.  We could use any other leaf, but this is easy to locate and
    03002      tends to counteract removal of leftmosts elsewhere, and so keeps
    03003      paths shorter than minimally guaranteed.  This doesn't loop much
    03004      because on average a node in a tree is near the bottom.
    03005   3. If x is the base of a chain (i.e., has parent links) relink
    03006      x's parent and children to x's replacement (or null if none).
    03007 */
    03008
    03009 #define unlink_large_chunk(M, X) {\
    03010   tchunkptr XP = X->parent;\
    03011   tchunkptr R;\
    03012   if (X->bk != X) {\
    03013     tchunkptr F = X->fd;\
    03014     R = X->bk;\
    03015     if (RTCHECK(ok_address(M, F))) {\
    03016       F->bk = R;\
    03017       R->fd = F;\
    03018     }\
    03019     else {\
    03020       CORRUPTION_ERROR_ACTION(M);\
    03021     }\
    03022   }\
    03023   else {\
    03024     tchunkptr* RP;\
    03025     if (((R = *(RP = &(X->child[1]))) != 0) ||\
    03026         ((R = *(RP = &(X->child[0]))) != 0)) {\
    03027       tchunkptr* CP;\
    03028       while ((*(CP = &(R->child[1])) != 0) ||\
    03029              (*(CP = &(R->child[0])) != 0)) {\
    03030         R = *(RP = CP);\
    03031       }\
    03032       if (RTCHECK(ok_address(M, RP)))\
    03033         *RP = 0;\
    03034       else {\
    03035         CORRUPTION_ERROR_ACTION(M);\
    03036       }\
    03037     }\
    03038   }\
    03039   if (XP != 0) {\
    03040     tbinptr* H = treebin_at(M, X->index);\
    03041     if (X == *H) {\
    03042       if ((*H = R) == 0) \
    03043         clear_treemap(M, X->index);\
    03044     }\
    03045     else if (RTCHECK(ok_address(M, XP))) {\
    03046       if (XP->child[0] == X) \
    03047         XP->child[0] = R;\
    03048       else \
    03049         XP->child[1] = R;\
    03050     }\
    03051     else\
    03052       CORRUPTION_ERROR_ACTION(M);\
    03053     if (R != 0) {\
    03054       if (RTCHECK(ok_address(M, R))) {\
    03055         tchunkptr C0, C1;\
    03056         R->parent = XP;\
    03057         if ((C0 = X->child[0]) != 0) {\
    03058           if (RTCHECK(ok_address(M, C0))) {\
    03059             R->child[0] = C0;\
    03060             C0->parent = R;\
    03061           }\
    03062           else\
    03063             CORRUPTION_ERROR_ACTION(M);\
    03064         }\
    03065         if ((C1 = X->child[1]) != 0) {\
    03066           if (RTCHECK(ok_address(M, C1))) {\
    03067             R->child[1] = C1;\
    03068             C1->parent = R;\
    03069           }\
    03070           else\
    03071             CORRUPTION_ERROR_ACTION(M);\
    03072         }\
    03073       }\
    03074       else\
    03075         CORRUPTION_ERROR_ACTION(M);\
    03076     }\
    03077   }\
    03078 }
    03079
    03080 /* Relays to large vs small bin operations */
    03081
    03082 #define insert_chunk(M, P, S)\
    03083   if (is_small(S)) insert_small_chunk(M, P, S)\
    03084   else { tchunkptr TP = (tchunkptr)(P); insert_large_chunk(M, TP, S); }
    03085
    03086 #define unlink_chunk(M, P, S)\
    03087   if (is_small(S)) unlink_small_chunk(M, P, S)\
    03088   else { tchunkptr TP = (tchunkptr)(P); unlink_large_chunk(M, TP); }
    03089
    03090
    03091 /* Relays to internal calls to malloc/free from realloc, memalign etc */
    03092
    03093 #if ONLY_MSPACES
    03094 #define internal_malloc(m, b) mspace_malloc(m, b)
    03095 #define internal_free(m, mem) mspace_free(m,mem);
    03096 #else /* ONLY_MSPACES */
    03097 #if MSPACES
    03098 #define internal_malloc(m, b)\
    03099    (m == gm)? dlmalloc(b) : mspace_malloc(m, b)
    03100 #define internal_free(m, mem)\
    03101    if (m == gm) dlfree(mem); else mspace_free(m,mem);
    03102 #else /* MSPACES */
    03103 #define internal_malloc(m, b) dlmalloc(b)
    03104 #define internal_free(m, mem) dlfree(mem)
    03105 #endif /* MSPACES */
    03106 #endif /* ONLY_MSPACES */
    03107
    03108 /* -----------------------  Direct-mmapping chunks ----------------------- */
    03109
    03110 /*
    03111   Directly mmapped chunks are set up with an offset to the start of
    03112   the mmapped region stored in the prev_foot field of the chunk. This
    03113   allows reconstruction of the required argument to MUNMAP when freed,
    03114   and also allows adjustment of the returned chunk to meet alignment
    03115   requirements (especially in memalign).  There is also enough space
    03116   allocated to hold a fake next chunk of size SIZE_T_SIZE to maintain
    03117   the PINUSE bit so frees can be checked.
    03118 */
    03119
    03120 /* Malloc using mmap */
    03121 static void* mmap_alloc(mstate m, size_t nb) {
    03122   size_t mmsize = granularity_align(nb + SIX_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
    03123   if (mmsize > nb) {     /* Check for wrap around 0 */
    03124     char* mm = (char*)(DIRECT_MMAP(mmsize));
    03125     if (mm != CMFAIL) {
    03126       size_t offset = align_offset(chunk2mem(mm));
    03127       size_t psize = mmsize - offset - MMAP_FOOT_PAD;
    03128       mchunkptr p = (mchunkptr)(mm + offset);
    03129       p->prev_foot = offset | IS_MMAPPED_BIT;
    03130       (p)->head = (psize|CINUSE_BIT);
    03131       mark_inuse_foot(m, p, psize);
    03132       chunk_plus_offset(p, psize)->head = FENCEPOST_HEAD;
    03133       chunk_plus_offset(p, psize+SIZE_T_SIZE)->head = 0;
    03134
    03135       if (mm < m->least_addr)
    03136         m->least_addr = mm;
    03137       if ((m->footprint += mmsize) > m->max_footprint)
    03138         m->max_footprint = m->footprint;
    03139       assert(is_aligned(chunk2mem(p)));
    03140       check_mmapped_chunk(m, p);
    03141       return chunk2mem(p);
    03142     }
    03143   }
    03144   return 0;
    03145 }
    03146
    03147 /* Realloc using mmap */
    03148 static mchunkptr mmap_resize(mstate m, mchunkptr oldp, size_t nb) {
    03149   size_t oldsize = chunksize(oldp);
    03150   if (is_small(nb)) /* Can't shrink mmap regions below small size */
    03151     return 0;
    03152   /* Keep old chunk if big enough but not too big */
    03153   if (oldsize >= nb + SIZE_T_SIZE &&
    03154       (oldsize - nb) <= (mparams.granularity << 1))
    03155     return oldp;
    03156   else {
    03157     size_t offset = oldp->prev_foot & ~IS_MMAPPED_BIT;
    03158     size_t oldmmsize = oldsize + offset + MMAP_FOOT_PAD;
    03159     size_t newmmsize = granularity_align(nb + SIX_SIZE_T_SIZES +
    03160                                          CHUNK_ALIGN_MASK);
    03161     char* cp = (char*)CALL_MREMAP((char*)oldp - offset,
    03162                                   oldmmsize, newmmsize, 1);
    03163     if (cp != CMFAIL) {
    03164       mchunkptr newp = (mchunkptr)(cp + offset);
    03165       size_t psize = newmmsize - offset - MMAP_FOOT_PAD;
    03166       newp->head = (psize|CINUSE_BIT);
    03167       mark_inuse_foot(m, newp, psize);
    03168       chunk_plus_offset(newp, psize)->head = FENCEPOST_HEAD;
    03169       chunk_plus_offset(newp, psize+SIZE_T_SIZE)->head = 0;
    03170
    03171       if (cp < m->least_addr)
    03172         m->least_addr = cp;
    03173       if ((m->footprint += newmmsize - oldmmsize) > m->max_footprint)
    03174         m->max_footprint = m->footprint;
    03175       check_mmapped_chunk(m, newp);
    03176       return newp;
    03177     }
    03178   }
    03179   return 0;
    03180 }
    03181
    03182 /* -------------------------- mspace management -------------------------- */
    03183
    03184 /* Initialize top chunk and its size */
    03185 static void init_top(mstate m, mchunkptr p, size_t psize) {
    03186   /* Ensure alignment */
    03187   size_t offset = align_offset(chunk2mem(p));
    03188   p = (mchunkptr)((char*)p + offset);
    03189   psize -= offset;
    03190
    03191   m->top = p;
    03192   m->topsize = psize;
    03193   p->head = psize | PINUSE_BIT;
    03194   /* set size of fake trailing chunk holding overhead space only once */
    03195   chunk_plus_offset(p, psize)->head = TOP_FOOT_SIZE;
    03196   m->trim_check = mparams.trim_threshold; /* reset on each update */
    03197 }
    03198
    03199 /* Initialize bins for a new mstate that is otherwise zeroed out */
    03200 static void init_bins(mstate m) {
    03201   /* Establish circular links for smallbins */
    03202   bindex_t i;
    03203   for (i = 0; i < NSMALLBINS; ++i) {
    03204     sbinptr bin = smallbin_at(m,i);
    03205     bin->fd = bin->bk = bin;
    03206   }
    03207 }
    03208
    03209 #if PROCEED_ON_ERROR
    03210
    03211 /* default corruption action */
    03212 static void reset_on_error(mstate m) {
    03213   int i;
    03214   ++malloc_corruption_error_count;
    03215   /* Reinitialize fields to forget about all memory */
    03216   m->smallbins = m->treebins = 0;
    03217   m->dvsize = m->topsize = 0;
    03218   m->seg.base = 0;
    03219   m->seg.size = 0;
    03220   m->seg.next = 0;
    03221   m->top = m->dv = 0;
    03222   for (i = 0; i < NTREEBINS; ++i)
    03223     *treebin_at(m, i) = 0;
    03224   init_bins(m);
    03225 }
    03226 #endif /* PROCEED_ON_ERROR */
    03227
    03228 /* Allocate chunk and prepend remainder with chunk in successor base. */
    03229 static void* prepend_alloc(mstate m, char* newbase, char* oldbase,
    03230                            size_t nb) {
    03231   mchunkptr p = align_as_chunk(newbase);
    03232   mchunkptr oldfirst = align_as_chunk(oldbase);
    03233   size_t psize = (char*)oldfirst - (char*)p;
    03234   mchunkptr q = chunk_plus_offset(p, nb);
    03235   size_t qsize = psize - nb;
    03236   set_size_and_pinuse_of_inuse_chunk(m, p, nb);
    03237
    03238   assert((char*)oldfirst > (char*)q);
    03239   assert(pinuse(oldfirst));
    03240   assert(qsize >= MIN_CHUNK_SIZE);
    03241
    03242   /* consolidate remainder with first chunk of old base */
    03243   if (oldfirst == m->top) {
    03244     size_t tsize = m->topsize += qsize;
    03245     m->top = q;
    03246     q->head = tsize | PINUSE_BIT;
    03247     check_top_chunk(m, q);
    03248   }
    03249   else if (oldfirst == m->dv) {
    03250     size_t dsize = m->dvsize += qsize;
    03251     m->dv = q;
    03252     set_size_and_pinuse_of_free_chunk(q, dsize);
    03253   }
    03254   else {
    03255     if (!cinuse(oldfirst)) {
    03256       size_t nsize = chunksize(oldfirst);
    03257       unlink_chunk(m, oldfirst, nsize);
    03258       oldfirst = chunk_plus_offset(oldfirst, nsize);
    03259       qsize += nsize;
    03260     }
    03261     set_free_with_pinuse(q, qsize, oldfirst);
    03262     insert_chunk(m, q, qsize);
    03263     check_free_chunk(m, q);
    03264   }
    03265
    03266   check_malloced_chunk(m, chunk2mem(p), nb);
    03267   return chunk2mem(p);
    03268 }
    03269
    03270
    03271 /* Add a segment to hold a new noncontiguous region */
    03272 static void add_segment(mstate m, char* tbase, size_t tsize, flag_t mmapped) {
    03273   /* Determine locations and sizes of segment, fenceposts, old top */
    03274   char* old_top = (char*)m->top;
    03275   msegmentptr oldsp = segment_holding(m, old_top);
    03276   char* old_end = oldsp->base + oldsp->size;
    03277   size_t ssize = pad_request(sizeof(struct malloc_segment));
    03278   char* rawsp = old_end - (ssize + FOUR_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
    03279   size_t offset = align_offset(chunk2mem(rawsp));
    03280   char* asp = rawsp + offset;
    03281   char* csp = (asp < (old_top + MIN_CHUNK_SIZE))? old_top : asp;
    03282   mchunkptr sp = (mchunkptr)csp;
    03283   msegmentptr ss = (msegmentptr)(chunk2mem(sp));
    03284   mchunkptr tnext = chunk_plus_offset(sp, ssize);
    03285   mchunkptr p = tnext;
    03286   int nfences = 0;
    03287
    03288   /* reset top to new space */
    03289   init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE);
    03290
    03291   /* Set up segment record */
    03292   assert(is_aligned(ss));
    03293   set_size_and_pinuse_of_inuse_chunk(m, sp, ssize);
    03294   *ss = m->seg; /* Push current record */
    03295   m->seg.base = tbase;
    03296   m->seg.size = tsize;
    03297   m->seg.sflags = mmapped;
    03298   m->seg.next = ss;
    03299
    03300   /* Insert trailing fenceposts */
    03301   for (;;) {
    03302     mchunkptr nextp = chunk_plus_offset(p, SIZE_T_SIZE);
    03303     p->head = FENCEPOST_HEAD;
    03304     ++nfences;
    03305     if ((char*)(&(nextp->head)) < old_end)
    03306       p = nextp;
    03307     else
    03308       break;
    03309   }
    03310   assert(nfences >= 2);
    03311
    03312   /* Insert the rest of old top into a bin as an ordinary free chunk */
    03313   if (csp != old_top) {
    03314     mchunkptr q = (mchunkptr)old_top;
    03315     size_t psize = csp - old_top;
    03316     mchunkptr tn = chunk_plus_offset(q, psize);
    03317     set_free_with_pinuse(q, psize, tn);
    03318     insert_chunk(m, q, psize);
    03319   }
    03320
    03321   check_top_chunk(m, m->top);
    03322 }
    03323
    03324 /* -------------------------- System allocation -------------------------- */
    03325
    03326 /* Get memory from system using MORECORE or MMAP */
    03327 static void* sys_alloc(mstate m, size_t nb) {
    03328   char* tbase = CMFAIL;
    03329   size_t tsize = 0;
    03330   flag_t mmap_flag = 0;
    03331
    03332   init_mparams();
    03333
    03334   /* Directly map large chunks */
    03335   if (use_mmap(m) && nb >= mparams.mmap_threshold) {
    03336     void* mem = mmap_alloc(m, nb);
    03337     if (mem != 0)
    03338       return mem;
    03339   }
    03340
    03341   /*
    03342     Try getting memory in any of three ways (in most-preferred to
    03343     least-preferred order):
    03344     1. A call to MORECORE that can normally contiguously extend memory.
    03345        (disabled if not MORECORE_CONTIGUOUS or not HAVE_MORECORE or
    03346        or main space is mmapped or a previous contiguous call failed)
    03347     2. A call to MMAP new space (disabled if not HAVE_MMAP).
    03348        Note that under the default settings, if MORECORE is unable to
    03349        fulfill a request, and HAVE_MMAP is true, then mmap is
    03350        used as a noncontiguous system allocator. This is a useful backup
    03351        strategy for systems with holes in address spaces -- in this case
    03352        sbrk cannot contiguously expand the heap, but mmap may be able to
    03353        find space.
    03354     3. A call to MORECORE that cannot usually contiguously extend memory.
    03355        (disabled if not HAVE_MORECORE)
    03356   */
    03357
    03358   if (MORECORE_CONTIGUOUS && !use_noncontiguous(m)) {
    03359     char* br = CMFAIL;
    03360     msegmentptr ss = (m->top == 0)? 0 : segment_holding(m, (char*)m->top);
    03361     size_t asize = 0;
    03362     ACQUIRE_MORECORE_LOCK();
    03363
    03364     if (ss == 0) {  /* First time through or recovery */
    03365       char* base = (char*)CALL_MORECORE(0);
    03366       if (base != CMFAIL) {
    03367         asize = granularity_align(nb + TOP_FOOT_SIZE + SIZE_T_ONE);
    03368         /* Adjust to end on a page boundary */
    03369         if (!is_page_aligned(base))
    03370           asize += (page_align((size_t)base) - (size_t)base);
    03371         /* Can't call MORECORE if size is negative when treated as signed */
    03372         if (asize < HALF_MAX_SIZE_T &&
    03373             (br = (char*)(CALL_MORECORE(asize))) == base) {
    03374           tbase = base;
    03375           tsize = asize;
    03376         }
    03377       }
    03378     }
    03379     else {
    03380       /* Subtract out existing available top space from MORECORE request. */
    03381       asize = granularity_align(nb - m->topsize + TOP_FOOT_SIZE + SIZE_T_ONE);
    03382       /* Use mem here only if it did continuously extend old space */
    03383       if (asize < HALF_MAX_SIZE_T &&
    03384           (br = (char*)(CALL_MORECORE(asize))) == ss->base+ss->size) {
    03385         tbase = br;
    03386         tsize = asize;
    03387       }
    03388     }
    03389
    03390     if (tbase == CMFAIL) {    /* Cope with partial failure */
    03391       if (br != CMFAIL) {    /* Try to use/extend the space we did get */
    03392         if (asize < HALF_MAX_SIZE_T &&
    03393             asize < nb + TOP_FOOT_SIZE + SIZE_T_ONE) {
    03394           size_t esize = granularity_align(nb + TOP_FOOT_SIZE + SIZE_T_ONE - asize);
    03395           if (esize < HALF_MAX_SIZE_T) {
    03396             char* end = (char*)CALL_MORECORE(esize);
    03397             if (end != CMFAIL)
    03398               asize += esize;
    03399             else {            /* Can't use; try to release */
    03400               CALL_MORECORE(-asize);
    03401               br = CMFAIL;
    03402             }
    03403           }
    03404         }
    03405       }
    03406       if (br != CMFAIL) {    /* Use the space we did get */
    03407         tbase = br;
    03408         tsize = asize;
    03409       }
    03410       else
    03411         disable_contiguous(m); /* Don't try contiguous path in the future */
    03412     }
    03413
    03414     RELEASE_MORECORE_LOCK();
    03415   }
    03416
    03417   if (HAVE_MMAP && tbase == CMFAIL) {  /* Try MMAP */
    03418     size_t req = nb + TOP_FOOT_SIZE + SIZE_T_ONE;
    03419     size_t rsize = granularity_align(req);
    03420     if (rsize > nb) { /* Fail if wraps around zero */
    03421       char* mp = (char*)(CALL_MMAP(rsize));
    03422       if (mp != CMFAIL) {
    03423         tbase = mp;
    03424         tsize = rsize;
    03425         mmap_flag = IS_MMAPPED_BIT;
    03426       }
    03427     }
    03428   }
    03429
    03430   if (HAVE_MORECORE && tbase == CMFAIL) { /* Try noncontiguous MORECORE */
    03431     size_t asize = granularity_align(nb + TOP_FOOT_SIZE + SIZE_T_ONE);
    03432     if (asize < HALF_MAX_SIZE_T) {
    03433       char* br = CMFAIL;
    03434       char* end = CMFAIL;
    03435       ACQUIRE_MORECORE_LOCK();
    03436       br = (char*)(CALL_MORECORE(asize));
    03437       end = (char*)(CALL_MORECORE(0));
    03438       RELEASE_MORECORE_LOCK();
    03439       if (br != CMFAIL && end != CMFAIL && br < end) {
    03440         size_t ssize = end - br;
    03441         if (ssize > nb + TOP_FOOT_SIZE) {
    03442           tbase = br;
    03443           tsize = ssize;
    03444         }
    03445       }
    03446     }
    03447   }
    03448
    03449   if (tbase != CMFAIL) {
    03450
    03451     if ((m->footprint += tsize) > m->max_footprint)
    03452       m->max_footprint = m->footprint;
    03453
    03454     if (!is_initialized(m)) { /* first-time initialization */
    03455       m->seg.base = m->least_addr = tbase;
    03456       m->seg.size = tsize;
    03457       m->seg.sflags = mmap_flag;
    03458       m->magic = mparams.magic;
    03459       init_bins(m);
    03460       if (is_global(m))
    03461         init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE);
    03462       else {
    03463         /* Offset top by embedded malloc_state */
    03464         mchunkptr mn = next_chunk(mem2chunk(m));
    03465         init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) -TOP_FOOT_SIZE);
    03466       }
    03467     }
    03468
    03469     else {
    03470       /* Try to merge with an existing segment */
    03471       msegmentptr sp = &m->seg;
    03472       while (sp != 0 && tbase != sp->base + sp->size)
    03473         sp = sp->next;
    03474       if (sp != 0 &&
    03475           !is_extern_segment(sp) &&
    03476           (sp->sflags & IS_MMAPPED_BIT) == mmap_flag &&
    03477           segment_holds(sp, m->top)) { /* append */
    03478         sp->size += tsize;
    03479         init_top(m, m->top, m->topsize + tsize);
    03480       }
    03481       else {
    03482         if (tbase < m->least_addr)
    03483           m->least_addr = tbase;
    03484         sp = &m->seg;
    03485         while (sp != 0 && sp->base != tbase + tsize)
    03486           sp = sp->next;
    03487         if (sp != 0 &&
    03488             !is_extern_segment(sp) &&
    03489             (sp->sflags & IS_MMAPPED_BIT) == mmap_flag) {
    03490           char* oldbase = sp->base;
    03491           sp->base = tbase;
    03492           sp->size += tsize;
    03493           return prepend_alloc(m, tbase, oldbase, nb);
    03494         }
    03495         else
    03496           add_segment(m, tbase, tsize, mmap_flag);
    03497       }
    03498     }
    03499
    03500     if (nb < m->topsize) { /* Allocate from new or extended top space */
    03501       size_t rsize = m->topsize -= nb;
    03502       mchunkptr p = m->top;
    03503       mchunkptr r = m->top = chunk_plus_offset(p, nb);
    03504       r->head = rsize | PINUSE_BIT;
    03505       set_size_and_pinuse_of_inuse_chunk(m, p, nb);
    03506       check_top_chunk(m, m->top);
    03507       check_malloced_chunk(m, chunk2mem(p), nb);
    03508       return chunk2mem(p);
    03509     }
    03510   }
    03511
    03512   MALLOC_FAILURE_ACTION;
    03513   return 0;
    03514 }
    03515
    03516 /* -----------------------  system deallocation -------------------------- */
    03517
    03518 /* Unmap and unlink any mmapped segments that don't contain used chunks */
    03519 static size_t release_unused_segments(mstate m) {
    03520   size_t released = 0;
    03521   msegmentptr pred = &m->seg;
    03522   msegmentptr sp = pred->next;
    03523   while (sp != 0) {
    03524     char* base = sp->base;
    03525     size_t size = sp->size;
    03526     msegmentptr next = sp->next;
    03527     if (is_mmapped_segment(sp) && !is_extern_segment(sp)) {
    03528       mchunkptr p = align_as_chunk(base);
    03529       size_t psize = chunksize(p);
    03530       /* Can unmap if first chunk holds entire segment and not pinned */
    03531       if (!cinuse(p) && (char*)p + psize >= base + size - TOP_FOOT_SIZE) {
    03532         tchunkptr tp = (tchunkptr)p;
    03533         assert(segment_holds(sp, (char*)sp));
    03534         if (p == m->dv) {
    03535           m->dv = 0;
    03536           m->dvsize = 0;
    03537         }
    03538         else {
    03539           unlink_large_chunk(m, tp);
    03540         }
    03541         if (CALL_MUNMAP(base, size) == 0) {
    03542           released += size;
    03543           m->footprint -= size;
    03544           /* unlink obsoleted record */
    03545           sp = pred;
    03546           sp->next = next;
    03547         }
    03548         else { /* back out if cannot unmap */
    03549           insert_large_chunk(m, tp, psize);
    03550         }
    03551       }
    03552     }
    03553     pred = sp;
    03554     sp = next;
    03555   }
    03556   return released;
    03557 }
    03558
    03559 static int sys_trim(mstate m, size_t pad) {
    03560   size_t released = 0;
    03561   if (pad < MAX_REQUEST && is_initialized(m)) {
    03562     pad += TOP_FOOT_SIZE; /* ensure enough room for segment overhead */
    03563
    03564     if (m->topsize > pad) {
    03565       /* Shrink top space in granularity-size units, keeping at least one */
    03566       size_t unit = mparams.granularity;
    03567       size_t extra = ((m->topsize - pad + (unit - SIZE_T_ONE)) / unit -
    03568                       SIZE_T_ONE) * unit;
    03569       msegmentptr sp = segment_holding(m, (char*)m->top);
    03570
    03571       if (!is_extern_segment(sp)) {
    03572         if (is_mmapped_segment(sp)) {
    03573           if (HAVE_MMAP &&
    03574               sp->size >= extra &&
    03575               !has_segment_link(m, sp)) { /* can't shrink if pinned */
    03576             size_t newsize = sp->size - extra;
    03577             /* Prefer mremap, fall back to munmap */
    03578             if ((CALL_MREMAP(sp->base, sp->size, newsize, 0) != MFAIL) ||
    03579                 (CALL_MUNMAP(sp->base + newsize, extra) == 0)) {
    03580               released = extra;
    03581             }
    03582           }
    03583         }
    03584         else if (HAVE_MORECORE) {
    03585           if (extra >= HALF_MAX_SIZE_T) /* Avoid wrapping negative */
    03586             extra = (HALF_MAX_SIZE_T) + SIZE_T_ONE - unit;
    03587           ACQUIRE_MORECORE_LOCK();
    03588           {
    03589             /* Make sure end of memory is where we last set it. */
    03590             char* old_br = (char*)(CALL_MORECORE(0));
    03591             if (old_br == sp->base + sp->size) {
    03592               char* rel_br = (char*)(CALL_MORECORE(-extra));
    03593               char* new_br = (char*)(CALL_MORECORE(0));
    03594               if (rel_br != CMFAIL && new_br < old_br)
    03595                 released = old_br - new_br;
    03596             }
    03597           }
    03598           RELEASE_MORECORE_LOCK();
    03599         }
    03600       }
    03601
    03602       if (released != 0) {
    03603         sp->size -= released;
    03604         m->footprint -= released;
    03605         init_top(m, m->top, m->topsize - released);
    03606         check_top_chunk(m, m->top);
    03607       }
    03608     }
    03609
    03610     /* Unmap any unused mmapped segments */
    03611     if (HAVE_MMAP)
    03612       released += release_unused_segments(m);
    03613
    03614     /* On failure, disable autotrim to avoid repeated failed future calls */
    03615     if (released == 0)
    03616       m->trim_check = MAX_SIZE_T;
    03617   }
    03618
    03619   return (released != 0)? 1 : 0;
    03620 }
    03621
    03622 /* ---------------------------- malloc support --------------------------- */
    03623
    03624 /* allocate a large request from the best fitting chunk in a treebin */
    03625 static void* tmalloc_large(mstate m, size_t nb) {
    03626   tchunkptr v = 0;
    03627   size_t rsize = -nb; /* Unsigned negation */
    03628   tchunkptr t;
    03629   bindex_t idx;
    03630   compute_tree_index(nb, idx);
    03631
    03632   if ((t = *treebin_at(m, idx)) != 0) {
    03633     /* Traverse tree for this bin looking for node with size == nb */
    03634     size_t sizebits = nb << leftshift_for_tree_index(idx);
    03635     tchunkptr rst = 0;  /* The deepest untaken right subtree */
    03636     for (;;) {
    03637       tchunkptr rt;
    03638       size_t trem = chunksize(t) - nb;
    03639       if (trem < rsize) {
    03640         v = t;
    03641         if ((rsize = trem) == 0)
    03642           break;
    03643       }
    03644       rt = t->child[1];
    03645       t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
    03646       if (rt != 0 && rt != t)
    03647         rst = rt;
    03648       if (t == 0) {
    03649         t = rst; /* set t to least subtree holding sizes > nb */
    03650         break;
    03651       }
    03652       sizebits <<= 1;
    03653     }
    03654   }
    03655
    03656   if (t == 0 && v == 0) { /* set t to root of next non-empty treebin */
    03657     binmap_t leftbits = left_bits(idx2bit(idx)) & m->treemap;
    03658     if (leftbits != 0) {
    03659       bindex_t i;
    03660       binmap_t leastbit = least_bit(leftbits);
    03661       compute_bit2idx(leastbit, i);
    03662       t = *treebin_at(m, i);
    03663     }
    03664   }
    03665
    03666   while (t != 0) { /* find smallest of tree or subtree */
    03667     size_t trem = chunksize(t) - nb;
    03668     if (trem < rsize) {
    03669       rsize = trem;
    03670       v = t;
    03671     }
    03672     t = leftmost_child(t);
    03673   }
    03674
    03675   /*  If dv is a better fit, return 0 so malloc will use it */
    03676   if (v != 0 && rsize < (size_t)(m->dvsize - nb)) {
    03677     if (RTCHECK(ok_address(m, v))) { /* split */
    03678       mchunkptr r = chunk_plus_offset(v, nb);
    03679       assert(chunksize(v) == rsize + nb);
    03680       if (RTCHECK(ok_next(v, r))) {
    03681         unlink_large_chunk(m, v);
    03682         if (rsize < MIN_CHUNK_SIZE)
    03683           set_inuse_and_pinuse(m, v, (rsize + nb));
    03684         else {
    03685           set_size_and_pinuse_of_inuse_chunk(m, v, nb);
    03686           set_size_and_pinuse_of_free_chunk(r, rsize);
    03687           insert_chunk(m, r, rsize);
    03688         }
    03689         return chunk2mem(v);
    03690       }
    03691     }
    03692     CORRUPTION_ERROR_ACTION(m);
    03693   }
    03694   return 0;
    03695 }
    03696
    03697 /* allocate a small request from the best fitting chunk in a treebin */
    03698 static void* tmalloc_small(mstate m, size_t nb) {
    03699   tchunkptr t, v;
    03700   size_t rsize;
    03701   bindex_t i;
    03702   binmap_t leastbit = least_bit(m->treemap);
    03703   compute_bit2idx(leastbit, i);
    03704
    03705   v = t = *treebin_at(m, i);
    03706   rsize = chunksize(t) - nb;
    03707
    03708   while ((t = leftmost_child(t)) != 0) {
    03709     size_t trem = chunksize(t) - nb;
    03710     if (trem < rsize) {
    03711       rsize = trem;
    03712       v = t;
    03713     }
    03714   }
    03715
    03716   if (RTCHECK(ok_address(m, v))) {
    03717     mchunkptr r = chunk_plus_offset(v, nb);
    03718     assert(chunksize(v) == rsize + nb);
    03719     if (RTCHECK(ok_next(v, r))) {
    03720       unlink_large_chunk(m, v);
    03721       if (rsize < MIN_CHUNK_SIZE)
    03722         set_inuse_and_pinuse(m, v, (rsize + nb));
    03723       else {
    03724         set_size_and_pinuse_of_inuse_chunk(m, v, nb);
    03725         set_size_and_pinuse_of_free_chunk(r, rsize);
    03726         replace_dv(m, r, rsize);
    03727       }
    03728       return chunk2mem(v);
    03729     }
    03730   }
    03731
    03732   CORRUPTION_ERROR_ACTION(m);
    03733   return 0;
    03734 }
    03735
    03736 /* --------------------------- realloc support --------------------------- */
    03737
    03738 static void* internal_realloc(mstate m, void* oldmem, size_t bytes) {
    03739   if (bytes >= MAX_REQUEST) {
    03740     MALLOC_FAILURE_ACTION;
    03741     return 0;
    03742   }
    03743   if (!PREACTION(m)) {
    03744     mchunkptr oldp = mem2chunk(oldmem);
    03745     size_t oldsize = chunksize(oldp);
    03746     mchunkptr next = chunk_plus_offset(oldp, oldsize);
    03747     mchunkptr newp = 0;
    03748     void* extra = 0;
    03749
    03750     /* Try to either shrink or extend into top. Else malloc-copy-free */
    03751
    03752     if (RTCHECK(ok_address(m, oldp) && ok_cinuse(oldp) &&
    03753                 ok_next(oldp, next) && ok_pinuse(next))) {
    03754       size_t nb = request2size(bytes);
    03755       if (is_mmapped(oldp))
    03756         newp = mmap_resize(m, oldp, nb);
    03757       else if (oldsize >= nb) { /* already big enough */
    03758         size_t rsize = oldsize - nb;
    03759         newp = oldp;
    03760         if (rsize >= MIN_CHUNK_SIZE) {
    03761           mchunkptr remainder = chunk_plus_offset(newp, nb);
    03762           set_inuse(m, newp, nb);
    03763           set_inuse(m, remainder, rsize);
    03764           extra = chunk2mem(remainder);
    03765         }
    03766       }
    03767       else if (next == m->top && oldsize + m->topsize > nb) {
    03768         /* Expand into top */
    03769         size_t newsize = oldsize + m->topsize;
    03770         size_t newtopsize = newsize - nb;
    03771         mchunkptr newtop = chunk_plus_offset(oldp, nb);
    03772         set_inuse(m, oldp, nb);
    03773         newtop->head = newtopsize |PINUSE_BIT;
    03774         m->top = newtop;
    03775         m->topsize = newtopsize;
    03776         newp = oldp;
    03777       }
    03778     }
    03779     else {
    03780       USAGE_ERROR_ACTION(m, oldmem);
    03781       POSTACTION(m);
    03782       return 0;
    03783     }
    03784
    03785     POSTACTION(m);
    03786
    03787     if (newp != 0) {
    03788       if (extra != 0) {
    03789         internal_free(m, extra);
    03790       }
    03791       check_inuse_chunk(m, newp);
    03792       return chunk2mem(newp);
    03793     }
    03794     else {
    03795       void* newmem = internal_malloc(m, bytes);
    03796       if (newmem != 0) {
    03797         size_t oc = oldsize - overhead_for(oldp);
    03798         memcpy(newmem, oldmem, (oc < bytes)? oc : bytes);
    03799         internal_free(m, oldmem);
    03800       }
    03801       return newmem;
    03802     }
    03803   }
    03804   return 0;
    03805 }
    03806
    03807 /* --------------------------- memalign support -------------------------- */
    03808
    03809 static void* internal_memalign(mstate m, size_t alignment, size_t bytes) {
    03810   if (alignment <= MALLOC_ALIGNMENT)    /* Can just use malloc */
    03811     return internal_malloc(m, bytes);
    03812   if (alignment <  MIN_CHUNK_SIZE) /* must be at least a minimum chunk size */
    03813     alignment = MIN_CHUNK_SIZE;
    03814   if ((alignment & (alignment-SIZE_T_ONE)) != 0) {/* Ensure a power of 2 */
    03815     size_t a = MALLOC_ALIGNMENT << 1;
    03816     while (a < alignment) a <<= 1;
    03817     alignment = a;
    03818   }
    03819
    03820   if (bytes >= MAX_REQUEST - alignment) {
    03821     if (m != 0)  { /* Test isn't needed but avoids compiler warning */
    03822       MALLOC_FAILURE_ACTION;
    03823     }
    03824   }
    03825   else {
    03826     size_t nb = request2size(bytes);
    03827     size_t req = nb + alignment + MIN_CHUNK_SIZE - CHUNK_OVERHEAD;
    03828     char* mem = (char*)internal_malloc(m, req);
    03829     if (mem != 0) {
    03830       void* leader = 0;
    03831       void* trailer = 0;
    03832       mchunkptr p = mem2chunk(mem);
    03833
    03834       if (PREACTION(m)) return 0;
    03835       if ((((size_t)(mem)) % alignment) != 0) { /* misaligned */
    03836         /*
    03837           Find an aligned spot inside chunk.  Since we need to give
    03838           back leading space in a chunk of at least MIN_CHUNK_SIZE, if
    03839           the first calculation places us at a spot with less than
    03840           MIN_CHUNK_SIZE leader, we can move to the next aligned spot.
    03841           We've allocated enough total room so that this is always
    03842           possible.
    03843         */
    03844         char* br = (char*)mem2chunk((size_t)(((size_t)(mem +
    03845                                                        alignment -
    03846                                                        SIZE_T_ONE)) &
    03847                                              -alignment));
    03848         char* pos = ((size_t)(br - (char*)(p)) >= MIN_CHUNK_SIZE)?
    03849           br : br+alignment;
    03850         mchunkptr newp = (mchunkptr)pos;
    03851         size_t leadsize = pos - (char*)(p);
    03852         size_t newsize = chunksize(p) - leadsize;
    03853
    03854         if (is_mmapped(p)) { /* For mmapped chunks, just adjust offset */
    03855           newp->prev_foot = p->prev_foot + leadsize;
    03856           newp->head = (newsize|CINUSE_BIT);
    03857         }
    03858         else { /* Otherwise, give back leader, use the rest */
    03859           set_inuse(m, newp, newsize);
    03860           set_inuse(m, p, leadsize);
    03861           leader = chunk2mem(p);
    03862         }
    03863         p = newp;
    03864       }
    03865
    03866       /* Give back spare room at the end */
    03867       if (!is_mmapped(p)) {
    03868         size_t size = chunksize(p);
    03869         if (size > nb + MIN_CHUNK_SIZE) {
    03870           size_t remainder_size = size - nb;
    03871           mchunkptr remainder = chunk_plus_offset(p, nb);
    03872           set_inuse(m, p, nb);
    03873           set_inuse(m, remainder, remainder_size);
    03874           trailer = chunk2mem(remainder);
    03875         }
    03876       }
    03877
    03878       assert (chunksize(p) >= nb);
    03879       assert((((size_t)(chunk2mem(p))) % alignment) == 0);
    03880       check_inuse_chunk(m, p);
    03881       POSTACTION(m);
    03882       if (leader != 0) {
    03883         internal_free(m, leader);
    03884       }
    03885       if (trailer != 0) {
    03886         internal_free(m, trailer);
    03887       }
    03888       return chunk2mem(p);
    03889     }
    03890   }
    03891   return 0;
    03892 }
    03893
    03894 /* ------------------------ comalloc/coalloc support --------------------- */
    03895
    03896 static void** ialloc(mstate m,
    03897                      size_t n_elements,
    03898                      size_t* sizes,
    03899                      int opts,
    03900                      void* chunks[]) {
    03901   /*
    03902     This provides common support for independent_X routines, handling
    03903     all of the combinations that can result.
    03904
    03905     The opts arg has:
    03906     bit 0 set if all elements are same size (using sizes[0])
    03907     bit 1 set if elements should be zeroed
    03908   */
    03909
    03910   size_t    element_size;   /* chunksize of each element, if all same */
    03911   size_t    contents_size;  /* total size of elements */
    03912   size_t    array_size;     /* request size of pointer array */
    03913   void*     mem;            /* malloced aggregate space */
    03914   mchunkptr p;              /* corresponding chunk */
    03915   size_t    remainder_size; /* remaining bytes while splitting */
    03916   void**    marray;         /* either "chunks" or malloced ptr array */
    03917   mchunkptr array_chunk;    /* chunk for malloced ptr array */
    03918   flag_t    was_enabled;    /* to disable mmap */
    03919   size_t    size;
    03920   size_t    i;
    03921
    03922   /* compute array length, if needed */
    03923   if (chunks != 0) {
    03924     if (n_elements == 0)
    03925       return chunks; /* nothing to do */
    03926     marray = chunks;
    03927     array_size = 0;
    03928   }
    03929   else {
    03930     /* if empty req, must still return chunk representing empty array */
    03931     if (n_elements == 0)
    03932       return (void**)internal_malloc(m, 0);
    03933     marray = 0;
    03934     array_size = request2size(n_elements * (sizeof(void*)));
    03935   }
    03936
    03937   /* compute total element size */
    03938   if (opts & 0x1) { /* all-same-size */
    03939     element_size = request2size(*sizes);
    03940     contents_size = n_elements * element_size;
    03941   }
    03942   else { /* add up all the sizes */
    03943     element_size = 0;
    03944     contents_size = 0;
    03945     for (i = 0; i != n_elements; ++i)
    03946       contents_size += request2size(sizes[i]);
    03947   }
    03948
    03949   size = contents_size + array_size;
    03950
    03951   /*
    03952      Allocate the aggregate chunk.  First disable direct-mmapping so
    03953      malloc won't use it, since we would not be able to later
    03954      free/realloc space internal to a segregated mmap region.
    03955   */
    03956   was_enabled = use_mmap(m);
    03957   disable_mmap(m);
    03958   mem = internal_malloc(m, size - CHUNK_OVERHEAD);
    03959   if (was_enabled)
    03960     enable_mmap(m);
    03961   if (mem == 0)
    03962     return 0;
    03963
    03964   if (PREACTION(m)) return 0;
    03965   p = mem2chunk(mem);
    03966   remainder_size = chunksize(p);
    03967
    03968   assert(!is_mmapped(p));
    03969
    03970   if (opts & 0x2) {       /* optionally clear the elements */
    03971     memset((size_t*)mem, 0, remainder_size - SIZE_T_SIZE - array_size);
    03972   }
    03973
    03974   /* If not provided, allocate the pointer array as final part of chunk */
    03975   if (marray == 0) {
    03976     size_t  array_chunk_size;
    03977     array_chunk = chunk_plus_offset(p, contents_size);
    03978     array_chunk_size = remainder_size - contents_size;
    03979     marray = (void**) (chunk2mem(array_chunk));
    03980     set_size_and_pinuse_of_inuse_chunk(m, array_chunk, array_chunk_size);
    03981     remainder_size = contents_size;
    03982   }
    03983
    03984   /* split out elements */
    03985   for (i = 0; ; ++i) {
    03986     marray[i] = chunk2mem(p);
    03987     if (i != n_elements-1) {
    03988       if (element_size != 0)
    03989         size = element_size;
    03990       else
    03991         size = request2size(sizes[i]);
    03992       remainder_size -= size;
    03993       set_size_and_pinuse_of_inuse_chunk(m, p, size);
    03994       p = chunk_plus_offset(p, size);
    03995     }
    03996     else { /* the final element absorbs any overallocation slop */
    03997       set_size_and_pinuse_of_inuse_chunk(m, p, remainder_size);
    03998       break;
    03999     }
    04000   }
    04001
    04002 #if DEBUG
    04003   if (marray != chunks) {
    04004     /* final element must have exactly exhausted chunk */
    04005     if (element_size != 0) {
    04006       assert(remainder_size == element_size);
    04007     }
    04008     else {
    04009       assert(remainder_size == request2size(sizes[i]));
    04010     }
    04011     check_inuse_chunk(m, mem2chunk(marray));
    04012   }
    04013   for (i = 0; i != n_elements; ++i)
    04014     check_inuse_chunk(m, mem2chunk(marray[i]));
    04015
    04016 #endif /* DEBUG */
    04017
    04018   POSTACTION(m);
    04019   return marray;
    04020 }
    04021
    04022
    04023 /* -------------------------- public routines ---------------------------- */
    04024
    04025 #if !ONLY_MSPACES
    04026
    04027 void* dlmalloc(size_t bytes) {
    04028   /*
    04029      Basic algorithm:
    04030      If a small request (< 256 bytes minus per-chunk overhead):
    04031        1. If one exists, use a remainderless chunk in associated smallbin.
    04032           (Remainderless means that there are too few excess bytes to
    04033           represent as a chunk.)
    04034        2. If it is big enough, use the dv chunk, which is normally the
    04035           chunk adjacent to the one used for the most recent small request.
    04036        3. If one exists, split the smallest available chunk in a bin,
    04037           saving remainder in dv.
    04038        4. If it is big enough, use the top chunk.
    04039        5. If available, get memory from system and use it
    04040      Otherwise, for a large request:
    04041        1. Find the smallest available binned chunk that fits, and use it
    04042           if it is better fitting than dv chunk, splitting if necessary.
    04043        2. If better fitting than any binned chunk, use the dv chunk.
    04044        3. If it is big enough, use the top chunk.
    04045        4. If request size >= mmap threshold, try to directly mmap this chunk.
    04046        5. If available, get memory from system and use it
    04047
    04048      The ugly goto's here ensure that postaction occurs along all paths.
    04049   */
    04050
    04051   if (!PREACTION(gm)) {
    04052     void* mem;
    04053     size_t nb;
    04054     if (bytes <= MAX_SMALL_REQUEST) {
    04055       bindex_t idx;
    04056       binmap_t smallbits;
    04057       nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes);
    04058       idx = small_index(nb);
    04059       smallbits = gm->smallmap >> idx;
    04060
    04061       if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */
    04062         mchunkptr b, p;
    04063         idx += ~smallbits & 1;       /* Uses next bin if idx empty */
    04064         b = smallbin_at(gm, idx);
    04065         p = b->fd;
    04066         assert(chunksize(p) == small_index2size(idx));
    04067         unlink_first_small_chunk(gm, b, p, idx);
    04068         set_inuse_and_pinuse(gm, p, small_index2size(idx));
    04069         mem = chunk2mem(p);
    04070         check_malloced_chunk(gm, mem, nb);
    04071         goto postaction;
    04072       }
    04073
    04074       else if (nb > gm->dvsize) {
    04075         if (smallbits != 0) { /* Use chunk in next nonempty smallbin */
    04076           mchunkptr b, p, r;
    04077           size_t rsize;
    04078           bindex_t i;
    04079           binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));
    04080           binmap_t leastbit = least_bit(leftbits);
    04081           compute_bit2idx(leastbit, i);
    04082           b = smallbin_at(gm, i);
    04083           p = b->fd;
    04084           assert(chunksize(p) == small_index2size(i));
    04085           unlink_first_small_chunk(gm, b, p, i);
    04086           rsize = small_index2size(i) - nb;
    04087           /* Fit here cannot be remainderless if 4byte sizes */
    04088           if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE)
    04089             set_inuse_and_pinuse(gm, p, small_index2size(i));
    04090           else {
    04091             set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
    04092             r = chunk_plus_offset(p, nb);
    04093             set_size_and_pinuse_of_free_chunk(r, rsize);
    04094             replace_dv(gm, r, rsize);
    04095           }
    04096           mem = chunk2mem(p);
    04097           check_malloced_chunk(gm, mem, nb);
    04098           goto postaction;
    04099         }
    04100
    04101         else if (gm->treemap != 0 && (mem = tmalloc_small(gm, nb)) != 0) {
    04102           check_malloced_chunk(gm, mem, nb);
    04103           goto postaction;
    04104         }
    04105       }
    04106     }
    04107     else if (bytes >= MAX_REQUEST)
    04108       nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */
    04109     else {
    04110       nb = pad_request(bytes);
    04111       if (gm->treemap != 0 && (mem = tmalloc_large(gm, nb)) != 0) {
    04112         check_malloced_chunk(gm, mem, nb);
    04113         goto postaction;
    04114       }
    04115     }
    04116
    04117     if (nb <= gm->dvsize) {
    04118       size_t rsize = gm->dvsize - nb;
    04119       mchunkptr p = gm->dv;
    04120       if (rsize >= MIN_CHUNK_SIZE) { /* split dv */
    04121         mchunkptr r = gm->dv = chunk_plus_offset(p, nb);
    04122         gm->dvsize = rsize;
    04123         set_size_and_pinuse_of_free_chunk(r, rsize);
    04124         set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
    04125       }
    04126       else { /* exhaust dv */
    04127         size_t dvs = gm->dvsize;
    04128         gm->dvsize = 0;
    04129         gm->dv = 0;
    04130         set_inuse_and_pinuse(gm, p, dvs);
    04131       }
    04132       mem = chunk2mem(p);
    04133       check_malloced_chunk(gm, mem, nb);
    04134       goto postaction;
    04135     }
    04136
    04137     else if (nb < gm->topsize) { /* Split top */
    04138       size_t rsize = gm->topsize -= nb;
    04139       mchunkptr p = gm->top;
    04140       mchunkptr r = gm->top = chunk_plus_offset(p, nb);
    04141       r->head = rsize | PINUSE_BIT;
    04142       set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
    04143       mem = chunk2mem(p);
    04144       check_top_chunk(gm, gm->top);
    04145       check_malloced_chunk(gm, mem, nb);
    04146       goto postaction;
    04147     }
    04148
    04149     mem = sys_alloc(gm, nb);
    04150
    04151   postaction:
    04152     POSTACTION(gm);
    04153     return mem;
    04154   }
    04155
    04156   return 0;
    04157 }
    04158
    04159 void dlfree(void* mem) {
    04160   /*
    04161      Consolidate freed chunks with preceeding or succeeding bordering
    04162      free chunks, if they exist, and then place in a bin.  Intermixed
    04163      with special cases for top, dv, mmapped chunks, and usage errors.
    04164   */
    04165
    04166   if (mem != 0) {
    04167     mchunkptr p  = mem2chunk(mem);
    04168 #if FOOTERS
    04169     mstate fm = get_mstate_for(p);
    04170     if (!ok_magic(fm)) {
    04171       USAGE_ERROR_ACTION(fm, p);
    04172       return;
    04173     }
    04174 #else /* FOOTERS */
    04175 #define fm gm
    04176 #endif /* FOOTERS */
    04177     if (!PREACTION(fm)) {
    04178       check_inuse_chunk(fm, p);
    04179       if (RTCHECK(ok_address(fm, p) && ok_cinuse(p))) {
    04180         size_t psize = chunksize(p);
    04181         mchunkptr next = chunk_plus_offset(p, psize);
    04182         if (!pinuse(p)) {
    04183           size_t prevsize = p->prev_foot;
    04184           if ((prevsize & IS_MMAPPED_BIT) != 0) {
    04185             prevsize &= ~IS_MMAPPED_BIT;
    04186             psize += prevsize + MMAP_FOOT_PAD;
    04187             if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)
    04188               fm->footprint -= psize;
    04189             goto postaction;
    04190           }
    04191           else {
    04192             mchunkptr prev = chunk_minus_offset(p, prevsize);
    04193             psize += prevsize;
    04194             p = prev;
    04195             if (RTCHECK(ok_address(fm, prev))) { /* consolidate backward */
    04196               if (p != fm->dv) {
    04197                 unlink_chunk(fm, p, prevsize);
    04198               }
    04199               else if ((next->head & INUSE_BITS) == INUSE_BITS) {
    04200                 fm->dvsize = psize;
    04201                 set_free_with_pinuse(p, psize, next);
    04202                 goto postaction;
    04203               }
    04204             }
    04205             else
    04206               goto erroraction;
    04207           }
    04208         }
    04209
    04210         if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) {
    04211           if (!cinuse(next)) {  /* consolidate forward */
    04212             if (next == fm->top) {
    04213               size_t tsize = fm->topsize += psize;
    04214               fm->top = p;
    04215               p->head = tsize | PINUSE_BIT;
    04216               if (p == fm->dv) {
    04217                 fm->dv = 0;
    04218                 fm->dvsize = 0;
    04219               }
    04220               if (should_trim(fm, tsize))
    04221                 sys_trim(fm, 0);
    04222               goto postaction;
    04223             }
    04224             else if (next == fm->dv) {
    04225               size_t dsize = fm->dvsize += psize;
    04226               fm->dv = p;
    04227               set_size_and_pinuse_of_free_chunk(p, dsize);
    04228               goto postaction;
    04229             }
    04230             else {
    04231               size_t nsize = chunksize(next);
    04232               psize += nsize;
    04233               unlink_chunk(fm, next, nsize);
    04234               set_size_and_pinuse_of_free_chunk(p, psize);
    04235               if (p == fm->dv) {
    04236                 fm->dvsize = psize;
    04237                 goto postaction;
    04238               }
    04239             }
    04240           }
    04241           else
    04242             set_free_with_pinuse(p, psize, next);
    04243           insert_chunk(fm, p, psize);
    04244           check_free_chunk(fm, p);
    04245           goto postaction;
    04246         }
    04247       }
    04248     erroraction:
    04249       USAGE_ERROR_ACTION(fm, p);
    04250     postaction:
    04251       POSTACTION(fm);
    04252     }
    04253   }
    04254 #if !FOOTERS
    04255 #undef fm
    04256 #endif /* FOOTERS */
    04257 }
    04258
    04259 void* dlcalloc(size_t n_elements, size_t elem_size) {
    04260   void* mem;
    04261   size_t req = 0;
    04262   if (n_elements != 0) {
    04263     req = n_elements * elem_size;
    04264     if (((n_elements | elem_size) & ~(size_t)0xffff) &&
    04265         (req / n_elements != elem_size))
    04266       req = MAX_SIZE_T; /* force downstream failure on overflow */
    04267   }
    04268   mem = dlmalloc(req);
    04269   if (mem != 0 && calloc_must_clear(mem2chunk(mem)))
    04270     memset(mem, 0, req);
    04271   return mem;
    04272 }
    04273
    04274 void* dlrealloc(void* oldmem, size_t bytes) {
    04275   if (oldmem == 0)
    04276     return dlmalloc(bytes);
    04277 #ifdef REALLOC_ZERO_BYTES_FREES
    04278   if (bytes == 0) {
    04279     dlfree(oldmem);
    04280     return 0;
    04281   }
    04282 #endif /* REALLOC_ZERO_BYTES_FREES */
    04283   else {
    04284 #if ! FOOTERS
    04285     mstate m = gm;
    04286 #else /* FOOTERS */
    04287     mstate m = get_mstate_for(mem2chunk(oldmem));
    04288     if (!ok_magic(m)) {
    04289       USAGE_ERROR_ACTION(m, oldmem);
    04290       return 0;
    04291     }
    04292 #endif /* FOOTERS */
    04293     return internal_realloc(m, oldmem, bytes);
    04294   }
    04295 }
    04296
    04297 void* dlmemalign(size_t alignment, size_t bytes) {
    04298   return internal_memalign(gm, alignment, bytes);
    04299 }
    04300
    04301 void** dlindependent_calloc(size_t n_elements, size_t elem_size,
    04302                                  void* chunks[]) {
    04303   size_t sz = elem_size; /* serves as 1-element array */
    04304   return ialloc(gm, n_elements, &sz, 3, chunks);
    04305 }
    04306
    04307 void** dlindependent_comalloc(size_t n_elements, size_t sizes[],
    04308                                    void* chunks[]) {
    04309   return ialloc(gm, n_elements, sizes, 0, chunks);
    04310 }
    04311
    04312 void* dlvalloc(size_t bytes) {
    04313   size_t pagesz;
    04314   init_mparams();
    04315   pagesz = mparams.page_size;
    04316   return dlmemalign(pagesz, bytes);
    04317 }
    04318
    04319 void* dlpvalloc(size_t bytes) {
    04320   size_t pagesz;
    04321   init_mparams();
    04322   pagesz = mparams.page_size;
    04323   return dlmemalign(pagesz, (bytes + pagesz - SIZE_T_ONE) & ~(pagesz - SIZE_T_ONE));
    04324 }
    04325
    04326 int dlmalloc_trim(size_t pad) {
    04327   int result = 0;
    04328   if (!PREACTION(gm)) {
    04329     result = sys_trim(gm, pad);
    04330     POSTACTION(gm);
    04331   }
    04332   return result;
    04333 }
    04334
    04335 size_t dlmalloc_footprint(void) {
    04336   return gm->footprint;
    04337 }
    04338
    04339 size_t dlmalloc_max_footprint(void) {
    04340   return gm->max_footprint;
    04341 }
    04342
    04343 #if !NO_MALLINFO
    04344 struct mallinfo dlmallinfo(void) {
    04345   return internal_mallinfo(gm);
    04346 }
    04347 #endif /* NO_MALLINFO */
    04348
    04349 void dlmalloc_stats() {
    04350   internal_malloc_stats(gm);
    04351 }
    04352
    04353 size_t dlmalloc_usable_size(void* mem) {
    04354   if (mem != 0) {
    04355     mchunkptr p = mem2chunk(mem);
    04356     if (cinuse(p))
    04357       return chunksize(p) - overhead_for(p);
    04358   }
    04359   return 0;
    04360 }
    04361
    04362 int dlmallopt(int param_number, int value) {
    04363   return change_mparam(param_number, value);
    04364 }
    04365
    04366 #endif /* !ONLY_MSPACES */
    04367
    04368 /* ----------------------------- user mspaces ---------------------------- */
    04369
    04370 #if MSPACES
    04371
    04372 static mstate init_user_mstate(char* tbase, size_t tsize) {
    04373   size_t msize = pad_request(sizeof(struct malloc_state));
    04374   mchunkptr mn;
    04375   mchunkptr msp = align_as_chunk(tbase);
    04376   mstate m = (mstate)(chunk2mem(msp));
    04377   memset(m, 0, msize);
    04378   INITIAL_LOCK(&m->mutex);
    04379   msp->head = (msize|PINUSE_BIT|CINUSE_BIT);
    04380   m->seg.base = m->least_addr = tbase;
    04381   m->seg.size = m->footprint = m->max_footprint = tsize;
    04382   m->magic = mparams.magic;
    04383   m->mflags = mparams.default_mflags;
    04384   disable_contiguous(m);
    04385   init_bins(m);
    04386   mn = next_chunk(mem2chunk(m));
    04387   init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) - TOP_FOOT_SIZE);
    04388   check_top_chunk(m, m->top);
    04389   return m;
    04390 }
    04391
    04392 mspace create_mspace(size_t capacity, int locked) {
    04393   mstate m = 0;
    04394   size_t msize = pad_request(sizeof(struct malloc_state));
    04395   init_mparams(); /* Ensure pagesize etc initialized */
    04396
    04397   if (capacity < (size_t) -(msize + TOP_FOOT_SIZE + mparams.page_size)) {
    04398     size_t rs = ((capacity == 0)? mparams.granularity :
    04399                  (capacity + TOP_FOOT_SIZE + msize));
    04400     size_t tsize = granularity_align(rs);
    04401     char* tbase = (char*)(CALL_MMAP(tsize));
    04402     if (tbase != CMFAIL) {
    04403       m = init_user_mstate(tbase, tsize);
    04404       m->seg.sflags = IS_MMAPPED_BIT;
    04405       set_lock(m, locked);
    04406     }
    04407   }
    04408   return (mspace)m;
    04409 }
    04410
    04411 mspace create_mspace_with_base(void* base, size_t capacity, int locked) {
    04412   mstate m = 0;
    04413   size_t msize = pad_request(sizeof(struct malloc_state));
    04414   init_mparams(); /* Ensure pagesize etc initialized */
    04415
    04416   if (capacity > msize + TOP_FOOT_SIZE &&
    04417       capacity < (size_t) -(msize + TOP_FOOT_SIZE + mparams.page_size)) {
    04418     m = init_user_mstate((char*)base, capacity);
    04419     m->seg.sflags = EXTERN_BIT;
    04420     set_lock(m, locked);
    04421   }
    04422   return (mspace)m;
    04423 }
    04424
    04425 size_t destroy_mspace(mspace msp) {
    04426   size_t freed = 0;
    04427   mstate ms = (mstate)msp;
    04428   if (ok_magic(ms)) {
    04429     msegmentptr sp = &ms->seg;
    04430     while (sp != 0) {
    04431       char* base = sp->base;
    04432       size_t size = sp->size;
    04433       flag_t flag = sp->sflags;
    04434       sp = sp->next;
    04435       if ((flag & IS_MMAPPED_BIT) && !(flag & EXTERN_BIT) &&
    04436           CALL_MUNMAP(base, size) == 0)
    04437         freed += size;
    04438     }
    04439   }
    04440   else {
    04441     USAGE_ERROR_ACTION(ms,ms);
    04442   }
    04443   return freed;
    04444 }
    04445
    04446 /*
    04447   mspace versions of routines are near-clones of the global
    04448   versions. This is not so nice but better than the alternatives.
    04449 */
    04450
    04451
    04452 void* mspace_malloc(mspace msp, size_t bytes) {
    04453   mstate ms = (mstate)msp;
    04454   if (!ok_magic(ms)) {
    04455     USAGE_ERROR_ACTION(ms,ms);
    04456     return 0;
    04457   }
    04458   if (!PREACTION(ms)) {
    04459     void* mem;
    04460     size_t nb;
    04461     if (bytes <= MAX_SMALL_REQUEST) {
    04462       bindex_t idx;
    04463       binmap_t smallbits;
    04464       nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes);
    04465       idx = small_index(nb);
    04466       smallbits = ms->smallmap >> idx;
    04467
    04468       if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */
    04469         mchunkptr b, p;
    04470         idx += ~smallbits & 1;       /* Uses next bin if idx empty */
    04471         b = smallbin_at(ms, idx);
    04472         p = b->fd;
    04473         assert(chunksize(p) == small_index2size(idx));
    04474         unlink_first_small_chunk(ms, b, p, idx);
    04475         set_inuse_and_pinuse(ms, p, small_index2size(idx));
    04476         mem = chunk2mem(p);
    04477         check_malloced_chunk(ms, mem, nb);
    04478         goto postaction;
    04479       }
    04480
    04481       else if (nb > ms->dvsize) {
    04482         if (smallbits != 0) { /* Use chunk in next nonempty smallbin */
    04483           mchunkptr b, p, r;
    04484           size_t rsize;
    04485           bindex_t i;
    04486           binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));
    04487           binmap_t leastbit = least_bit(leftbits);
    04488           compute_bit2idx(leastbit, i);
    04489           b = smallbin_at(ms, i);
    04490           p = b->fd;
    04491           assert(chunksize(p) == small_index2size(i));
    04492           unlink_first_small_chunk(ms, b, p, i);
    04493           rsize = small_index2size(i) - nb;
    04494           /* Fit here cannot be remainderless if 4byte sizes */
    04495           if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE)
    04496             set_inuse_and_pinuse(ms, p, small_index2size(i));
    04497           else {
    04498             set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
    04499             r = chunk_plus_offset(p, nb);
    04500             set_size_and_pinuse_of_free_chunk(r, rsize);
    04501             replace_dv(ms, r, rsize);
    04502           }
    04503           mem = chunk2mem(p);
    04504           check_malloced_chunk(ms, mem, nb);
    04505           goto postaction;
    04506         }
    04507
    04508         else if (ms->treemap != 0 && (mem = tmalloc_small(ms, nb)) != 0) {
    04509           check_malloced_chunk(ms, mem, nb);
    04510           goto postaction;
    04511         }
    04512       }
    04513     }
    04514     else if (bytes >= MAX_REQUEST)
    04515       nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */
    04516     else {
    04517       nb = pad_request(bytes);
    04518       if (ms->treemap != 0 && (mem = tmalloc_large(ms, nb)) != 0) {
    04519         check_malloced_chunk(ms, mem, nb);
    04520         goto postaction;
    04521       }
    04522     }
    04523
    04524     if (nb <= ms->dvsize) {
    04525       size_t rsize = ms->dvsize - nb;
    04526       mchunkptr p = ms->dv;
    04527       if (rsize >= MIN_CHUNK_SIZE) { /* split dv */
    04528         mchunkptr r = ms->dv = chunk_plus_offset(p, nb);
    04529         ms->dvsize = rsize;
    04530         set_size_and_pinuse_of_free_chunk(r, rsize);
    04531         set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
    04532       }
    04533       else { /* exhaust dv */
    04534         size_t dvs = ms->dvsize;
    04535         ms->dvsize = 0;
    04536         ms->dv = 0;
    04537         set_inuse_and_pinuse(ms, p, dvs);
    04538       }
    04539       mem = chunk2mem(p);
    04540       check_malloced_chunk(ms, mem, nb);
    04541       goto postaction;
    04542     }
    04543
    04544     else if (nb < ms->topsize) { /* Split top */
    04545       size_t rsize = ms->topsize -= nb;
    04546       mchunkptr p = ms->top;
    04547       mchunkptr r = ms->top = chunk_plus_offset(p, nb);
    04548       r->head = rsize | PINUSE_BIT;
    04549       set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
    04550       mem = chunk2mem(p);
    04551       check_top_chunk(ms, ms->top);
    04552       check_malloced_chunk(ms, mem, nb);
    04553       goto postaction;
    04554     }
    04555
    04556     mem = sys_alloc(ms, nb);
    04557
    04558   postaction:
    04559     POSTACTION(ms);
    04560     return mem;
    04561   }
    04562
    04563   return 0;
    04564 }
    04565
    04566 void mspace_free(mspace msp, void* mem) {
    04567   if (mem != 0) {
    04568     mchunkptr p  = mem2chunk(mem);
    04569 #if FOOTERS
    04570     mstate fm = get_mstate_for(p);
    04571 #else /* FOOTERS */
    04572     mstate fm = (mstate)msp;
    04573 #endif /* FOOTERS */
    04574     if (!ok_magic(fm)) {
    04575       USAGE_ERROR_ACTION(fm, p);
    04576       return;
    04577     }
    04578     if (!PREACTION(fm)) {
    04579       check_inuse_chunk(fm, p);
    04580       if (RTCHECK(ok_address(fm, p) && ok_cinuse(p))) {
    04581         size_t psize = chunksize(p);
    04582         mchunkptr next = chunk_plus_offset(p, psize);
    04583         if (!pinuse(p)) {
    04584           size_t prevsize = p->prev_foot;
    04585           if ((prevsize & IS_MMAPPED_BIT) != 0) {
    04586             prevsize &= ~IS_MMAPPED_BIT;
    04587             psize += prevsize + MMAP_FOOT_PAD;
    04588             if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)
    04589               fm->footprint -= psize;
    04590             goto postaction;
    04591           }
    04592           else {
    04593             mchunkptr prev = chunk_minus_offset(p, prevsize);
    04594             psize += prevsize;
    04595             p = prev;
    04596             if (RTCHECK(ok_address(fm, prev))) { /* consolidate backward */
    04597               if (p != fm->dv) {
    04598                 unlink_chunk(fm, p, prevsize);
    04599               }
    04600               else if ((next->head & INUSE_BITS) == INUSE_BITS) {
    04601                 fm->dvsize = psize;
    04602                 set_free_with_pinuse(p, psize, next);
    04603                 goto postaction;
    04604               }
    04605             }
    04606             else
    04607               goto erroraction;
    04608           }
    04609         }
    04610
    04611         if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) {
    04612           if (!cinuse(next)) {  /* consolidate forward */
    04613             if (next == fm->top) {
    04614               size_t tsize = fm->topsize += psize;
    04615               fm->top = p;
    04616               p->head = tsize | PINUSE_BIT;
    04617               if (p == fm->dv) {
    04618                 fm->dv = 0;
    04619                 fm->dvsize = 0;
    04620               }
    04621               if (should_trim(fm, tsize))
    04622                 sys_trim(fm, 0);
    04623               goto postaction;
    04624             }
    04625             else if (next == fm->dv) {
    04626               size_t dsize = fm->dvsize += psize;
    04627               fm->dv = p;
    04628               set_size_and_pinuse_of_free_chunk(p, dsize);
    04629               goto postaction;
    04630             }
    04631             else {
    04632               size_t nsize = chunksize(next);
    04633               psize += nsize;
    04634               unlink_chunk(fm, next, nsize);
    04635               set_size_and_pinuse_of_free_chunk(p, psize);
    04636               if (p == fm->dv) {
    04637                 fm->dvsize = psize;
    04638                 goto postaction;
    04639               }
    04640             }
    04641           }
    04642           else
    04643             set_free_with_pinuse(p, psize, next);
    04644           insert_chunk(fm, p, psize);
    04645           check_free_chunk(fm, p);
    04646           goto postaction;
    04647         }
    04648       }
    04649     erroraction:
    04650       USAGE_ERROR_ACTION(fm, p);
    04651     postaction:
    04652       POSTACTION(fm);
    04653     }
    04654   }
    04655 }
    04656
    04657 void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size) {
    04658   void* mem;
    04659   size_t req = 0;
    04660   mstate ms = (mstate)msp;
    04661   if (!ok_magic(ms)) {
    04662     USAGE_ERROR_ACTION(ms,ms);
    04663     return 0;
    04664   }
    04665   if (n_elements != 0) {
    04666     req = n_elements * elem_size;
    04667     if (((n_elements | elem_size) & ~(size_t)0xffff) &&
    04668         (req / n_elements != elem_size))
    04669       req = MAX_SIZE_T; /* force downstream failure on overflow */
    04670   }
    04671   mem = internal_malloc(ms, req);
    04672   if (mem != 0 && calloc_must_clear(mem2chunk(mem)))
    04673     memset(mem, 0, req);
    04674   return mem;
    04675 }
    04676
    04677 void* mspace_realloc(mspace msp, void* oldmem, size_t bytes) {
    04678   if (oldmem == 0)
    04679     return mspace_malloc(msp, bytes);
    04680 #ifdef REALLOC_ZERO_BYTES_FREES
    04681   if (bytes == 0) {
    04682     mspace_free(msp, oldmem);
    04683     return 0;
    04684   }
    04685 #endif /* REALLOC_ZERO_BYTES_FREES */
    04686   else {
    04687 #if FOOTERS
    04688     mchunkptr p  = mem2chunk(oldmem);
    04689     mstate ms = get_mstate_for(p);
    04690 #else /* FOOTERS */
    04691     mstate ms = (mstate)msp;
    04692 #endif /* FOOTERS */
    04693     if (!ok_magic(ms)) {
    04694       USAGE_ERROR_ACTION(ms,ms);
    04695       return 0;
    04696     }
    04697     return internal_realloc(ms, oldmem, bytes);
    04698   }
    04699 }
    04700
    04701 void* mspace_memalign(mspace msp, size_t alignment, size_t bytes) {
    04702   mstate ms = (mstate)msp;
    04703   if (!ok_magic(ms)) {
    04704     USAGE_ERROR_ACTION(ms,ms);
    04705     return 0;
    04706   }
    04707   return internal_memalign(ms, alignment, bytes);
    04708 }
    04709
    04710 void** mspace_independent_calloc(mspace msp, size_t n_elements,
    04711                                  size_t elem_size, void* chunks[]) {
    04712   size_t sz = elem_size; /* serves as 1-element array */
    04713   mstate ms = (mstate)msp;
    04714   if (!ok_magic(ms)) {
    04715     USAGE_ERROR_ACTION(ms,ms);
    04716     return 0;
    04717   }
    04718   return ialloc(ms, n_elements, &sz, 3, chunks);
    04719 }
    04720
    04721 void** mspace_independent_comalloc(mspace msp, size_t n_elements,
    04722                                    size_t sizes[], void* chunks[]) {
    04723   mstate ms = (mstate)msp;
    04724   if (!ok_magic(ms)) {
    04725     USAGE_ERROR_ACTION(ms,ms);
    04726     return 0;
    04727   }
    04728   return ialloc(ms, n_elements, sizes, 0, chunks);
    04729 }
    04730
    04731 int mspace_trim(mspace msp, size_t pad) {
    04732   int result = 0;
    04733   mstate ms = (mstate)msp;
    04734   if (ok_magic(ms)) {
    04735     if (!PREACTION(ms)) {
    04736       result = sys_trim(ms, pad);
    04737       POSTACTION(ms);
    04738     }
    04739   }
    04740   else {
    04741     USAGE_ERROR_ACTION(ms,ms);
    04742   }
    04743   return result;
    04744 }
    04745
    04746 void mspace_malloc_stats(mspace msp) {
    04747   mstate ms = (mstate)msp;
    04748   if (ok_magic(ms)) {
    04749     internal_malloc_stats(ms);
    04750   }
    04751   else {
    04752     USAGE_ERROR_ACTION(ms,ms);
    04753   }
    04754 }
    04755
    04756 size_t mspace_footprint(mspace msp) {
    04757   size_t result;
    04758   mstate ms = (mstate)msp;
    04759   if (ok_magic(ms)) {
    04760     result = ms->footprint;
    04761   }
    04762   USAGE_ERROR_ACTION(ms,ms);
    04763   return result;
    04764 }
    04765
    04766
    04767 size_t mspace_max_footprint(mspace msp) {
    04768   size_t result;
    04769   mstate ms = (mstate)msp;
    04770   if (ok_magic(ms)) {
    04771     result = ms->max_footprint;
    04772   }
    04773   USAGE_ERROR_ACTION(ms,ms);
    04774   return result;
    04775 }
    04776
    04777
    04778 #if !NO_MALLINFO
    04779 struct mallinfo mspace_mallinfo(mspace msp) {
    04780   mstate ms = (mstate)msp;
    04781   if (!ok_magic(ms)) {
    04782     USAGE_ERROR_ACTION(ms,ms);
    04783   }
    04784   return internal_mallinfo(ms);
    04785 }
    04786 #endif /* NO_MALLINFO */
    04787
    04788 int mspace_mallopt(int param_number, int value) {
    04789   return change_mparam(param_number, value);
    04790 }
    04791
    04792 #endif /* MSPACES */
    04793
    04794 /* -------------------- Alternative MORECORE functions ------------------- */
    04795
    04796 /*
    04797   Guidelines for creating a custom version of MORECORE:
    04798
    04799   * For best performance, MORECORE should allocate in multiples of pagesize.
    04800   * MORECORE may allocate more memory than requested. (Or even less,
    04801       but this will usually result in a malloc failure.)
    04802   * MORECORE must not allocate memory when given argument zero, but
    04803       instead return one past the end address of memory from previous
    04804       nonzero call.
    04805   * For best performance, consecutive calls to MORECORE with positive
    04806       arguments should return increasing addresses, indicating that
    04807       space has been contiguously extended.
    04808   * Even though consecutive calls to MORECORE need not return contiguous
    04809       addresses, it must be OK for malloc'ed chunks to span multiple
    04810       regions in those cases where they do happen to be contiguous.
    04811   * MORECORE need not handle negative arguments -- it may instead
    04812       just return MFAIL when given negative arguments.
    04813       Negative arguments are always multiples of pagesize. MORECORE
    04814       must not misinterpret negative args as large positive unsigned
    04815       args. You can suppress all such calls from even occurring by defining
    04816       MORECORE_CANNOT_TRIM,
    04817
    04818   As an example alternative MORECORE, here is a custom allocator
    04819   kindly contributed for pre-OSX macOS.  It uses virtually but not
    04820   necessarily physically contiguous non-paged memory (locked in,
    04821   present and won't get swapped out).  You can use it by uncommenting
    04822   this section, adding some #includes, and setting up the appropriate
    04823   defines above:
    04824
    04825       #define MORECORE osMoreCore
    04826
    04827   There is also a shutdown routine that should somehow be called for
    04828   cleanup upon program exit.
    04829
    04830   #define MAX_POOL_ENTRIES 100
    04831   #define MINIMUM_MORECORE_SIZE  (64 * 1024U)
    04832   static int next_os_pool;
    04833   void *our_os_pools[MAX_POOL_ENTRIES];
    04834
    04835   void *osMoreCore(int size)
    04836   {
    04837     void *ptr = 0;
    04838     static void *sbrk_top = 0;
    04839
    04840     if (size > 0)
    04841     {
    04842       if (size < MINIMUM_MORECORE_SIZE)
    04843          size = MINIMUM_MORECORE_SIZE;
    04844       if (CurrentExecutionLevel() == kTaskLevel)
    04845          ptr = PoolAllocateResident(size + RM_PAGE_SIZE, 0);
    04846       if (ptr == 0)
    04847       {
    04848         return (void *) MFAIL;
    04849       }
    04850       // save ptrs so they can be freed during cleanup
    04851       our_os_pools[next_os_pool] = ptr;
    04852       next_os_pool++;
    04853       ptr = (void *) ((((size_t) ptr) + RM_PAGE_MASK) & ~RM_PAGE_MASK);
    04854       sbrk_top = (char *) ptr + size;
    04855       return ptr;
    04856     }
    04857     else if (size < 0)
    04858     {
    04859       // we don't currently support shrink behavior
    04860       return (void *) MFAIL;
    04861     }
    04862     else
    04863     {
    04864       return sbrk_top;
    04865     }
    04866   }
    04867
    04868   // cleanup any allocated memory pools
    04869   // called as last thing before shutting down driver
    04870
    04871   void osCleanupMem(void)
    04872   {
    04873     void **ptr;
    04874
    04875     for (ptr = our_os_pools; ptr < &our_os_pools[MAX_POOL_ENTRIES]; ptr++)
    04876       if (*ptr)
    04877       {
    04878          PoolDeallocate(*ptr);
    04879          *ptr = 0;
    04880       }
    04881   }
    04882
    04883 */
    04884
    04885
    04886 /* -----------------------------------------------------------------------
    04887 History:
    04888     V2.8.3 Thu Sep 22 11:16:32 2005  Doug Lea  (dl at gee)
    04889       * Add max_footprint functions
    04890       * Ensure all appropriate literals are size_t
    04891       * Fix conditional compilation problem for some #define settings
    04892       * Avoid concatenating segments with the one provided
    04893         in create_mspace_with_base
    04894       * Rename some variables to avoid compiler shadowing warnings
    04895       * Use explicit lock initialization.
    04896       * Better handling of sbrk interference.
    04897       * Simplify and fix segment insertion, trimming and mspace_destroy
    04898       * Reinstate REALLOC_ZERO_BYTES_FREES option from 2.7.x
    04899       * Thanks especially to Dennis Flanagan for help on these.
    04900
    04901     V2.8.2 Sun Jun 12 16:01:10 2005  Doug Lea  (dl at gee)
    04902       * Fix memalign brace error.
    04903
    04904     V2.8.1 Wed Jun  8 16:11:46 2005  Doug Lea  (dl at gee)
    04905       * Fix improper #endif nesting in C++
    04906       * Add explicit casts needed for C++
    04907
    04908     V2.8.0 Mon May 30 14:09:02 2005  Doug Lea  (dl at gee)
    04909       * Use trees for large bins
    04910       * Support mspaces
    04911       * Use segments to unify sbrk-based and mmap-based system allocation,
    04912         removing need for emulation on most platforms without sbrk.
    04913       * Default safety checks
    04914       * Optional footer checks. Thanks to William Robertson for the idea.
    04915       * Internal code refactoring
    04916       * Incorporate suggestions and platform-specific changes.
    04917         Thanks to Dennis Flanagan, Colin Plumb, Niall Douglas,
    04918         Aaron Bachmann,  Emery Berger, and others.
    04919       * Speed up non-fastbin processing enough to remove fastbins.
    04920       * Remove useless cfree() to avoid conflicts with other apps.
    04921       * Remove internal memcpy, memset. Compilers handle builtins better.
    04922       * Remove some options that no one ever used and rename others.
    04923
    04924     V2.7.2 Sat Aug 17 09:07:30 2002  Doug Lea  (dl at gee)
    04925       * Fix malloc_state bitmap array misdeclaration
    04926
    04927     V2.7.1 Thu Jul 25 10:58:03 2002  Doug Lea  (dl at gee)
    04928       * Allow tuning of FIRST_SORTED_BIN_SIZE
    04929       * Use PTR_UINT as type for all ptr->int casts. Thanks to John Belmonte.
    04930       * Better detection and support for non-contiguousness of MORECORE.
    04931         Thanks to Andreas Mueller, Conal Walsh, and Wolfram Gloger
    04932       * Bypass most of malloc if no frees. Thanks To Emery Berger.
    04933       * Fix freeing of old top non-contiguous chunk im sysmalloc.
    04934       * Raised default trim and map thresholds to 256K.
    04935       * Fix mmap-related #defines. Thanks to Lubos Lunak.
    04936       * Fix copy macros; added LACKS_FCNTL_H. Thanks to Neal Walfield.
    04937       * Branch-free bin calculation
    04938       * Default trim and mmap thresholds now 256K.
    04939
    04940     V2.7.0 Sun Mar 11 14:14:06 2001  Doug Lea  (dl at gee)
    04941       * Introduce independent_comalloc and independent_calloc.
    04942         Thanks to Michael Pachos for motivation and help.
    04943       * Make optional .h file available
    04944       * Allow > 2GB requests on 32bit systems.
    04945       * new WIN32 sbrk, mmap, munmap, lock code from <Walter@GeNeSys-e.de>.
    04946         Thanks also to Andreas Mueller <a.mueller at paradatec.de>,
    04947         and Anonymous.
    04948       * Allow override of MALLOC_ALIGNMENT (Thanks to Ruud Waij for
    04949         helping test this.)
    04950       * memalign: check alignment arg
    04951       * realloc: don't try to shift chunks backwards, since this
    04952         leads to  more fragmentation in some programs and doesn't
    04953         seem to help in any others.
    04954       * Collect all cases in malloc requiring system memory into sysmalloc
    04955       * Use mmap as backup to sbrk
    04956       * Place all internal state in malloc_state
    04957       * Introduce fastbins (although similar to 2.5.1)
    04958       * Many minor tunings and cosmetic improvements
    04959       * Introduce USE_PUBLIC_MALLOC_WRAPPERS, USE_MALLOC_LOCK
    04960       * Introduce MALLOC_FAILURE_ACTION, MORECORE_CONTIGUOUS
    04961         Thanks to Tony E. Bennett <tbennett@nvidia.com> and others.
    04962       * Include errno.h to support default failure action.
    04963
    04964     V2.6.6 Sun Dec  5 07:42:19 1999  Doug Lea  (dl at gee)
    04965       * return null for negative arguments
    04966       * Added Several WIN32 cleanups from Martin C. Fong <mcfong at yahoo.com>
    04967          * Add 'LACKS_SYS_PARAM_H' for those systems without 'sys/param.h'
    04968           (e.g. WIN32 platforms)
    04969          * Cleanup header file inclusion for WIN32 platforms
    04970          * Cleanup code to avoid Microsoft Visual C++ compiler complaints
    04971          * Add 'USE_DL_PREFIX' to quickly allow co-existence with existing
    04972            memory allocation routines
    04973          * Set 'malloc_getpagesize' for WIN32 platforms (needs more work)
    04974          * Use 'assert' rather than 'ASSERT' in WIN32 code to conform to
    04975            usage of 'assert' in non-WIN32 code
    04976          * Improve WIN32 'sbrk()' emulation's 'findRegion()' routine to
    04977            avoid infinite loop
    04978       * Always call 'fREe()' rather than 'free()'
    04979
    04980     V2.6.5 Wed Jun 17 15:57:31 1998  Doug Lea  (dl at gee)
    04981       * Fixed ordering problem with boundary-stamping
    04982
    04983     V2.6.3 Sun May 19 08:17:58 1996  Doug Lea  (dl at gee)
    04984       * Added pvalloc, as recommended by H.J. Liu
    04985       * Added 64bit pointer support mainly from Wolfram Gloger
    04986       * Added anonymously donated WIN32 sbrk emulation
    04987       * Malloc, calloc, getpagesize: add optimizations from Raymond Nijssen
    04988       * malloc_extend_top: fix mask error that caused wastage after
    04989         foreign sbrks
    04990       * Add linux mremap support code from HJ Liu
    04991
    04992     V2.6.2 Tue Dec  5 06:52:55 1995  Doug Lea  (dl at gee)
    04993       * Integrated most documentation with the code.
    04994       * Add support for mmap, with help from
    04995         Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
    04996       * Use last_remainder in more cases.
    04997       * Pack bins using idea from  colin@nyx10.cs.du.edu
    04998       * Use ordered bins instead of best-fit threshhold
    04999       * Eliminate block-local decls to simplify tracing and debugging.
    05000       * Support another case of realloc via move into top
    05001       * Fix error occuring when initial sbrk_base not word-aligned.
    05002       * Rely on page size for units instead of SBRK_UNIT to
    05003         avoid surprises about sbrk alignment conventions.
    05004       * Add mallinfo, mallopt. Thanks to Raymond Nijssen
    05005         (raymond@es.ele.tue.nl) for the suggestion.
    05006       * Add `pad' argument to malloc_trim and top_pad mallopt parameter.
    05007       * More precautions for cases where other routines call sbrk,
    05008         courtesy of Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
    05009       * Added macros etc., allowing use in linux libc from
    05010         H.J. Lu (hjl@gnu.ai.mit.edu)
    05011       * Inverted this history list
    05012
    05013     V2.6.1 Sat Dec  2 14:10:57 1995  Doug Lea  (dl at gee)
    05014       * Re-tuned and fixed to behave more nicely with V2.6.0 changes.
    05015       * Removed all preallocation code since under current scheme
    05016         the work required to undo bad preallocations exceeds
    05017         the work saved in good cases for most test programs.
    05018       * No longer use return list or unconsolidated bins since
    05019         no scheme using them consistently outperforms those that don't
    05020         given above changes.
    05021       * Use best fit for very large chunks to prevent some worst-cases.
    05022       * Added some support for debugging
    05023
    05024     V2.6.0 Sat Nov  4 07:05:23 1995  Doug Lea  (dl at gee)
    05025       * Removed footers when chunks are in use. Thanks to
    05026         Paul Wilson (wilson@cs.texas.edu) for the suggestion.
    05027
    05028     V2.5.4 Wed Nov  1 07:54:51 1995  Doug Lea  (dl at gee)
    05029       * Added malloc_trim, with help from Wolfram Gloger
    05030         (wmglo@Dent.MED.Uni-Muenchen.DE).
    05031
    05032     V2.5.3 Tue Apr 26 10:16:01 1994  Doug Lea  (dl at g)
    05033
    05034     V2.5.2 Tue Apr  5 16:20:40 1994  Doug Lea  (dl at g)
    05035       * realloc: try to expand in both directions
    05036       * malloc: swap order of clean-bin strategy;
    05037       * realloc: only conditionally expand backwards
    05038       * Try not to scavenge used bins
    05039       * Use bin counts as a guide to preallocation
    05040       * Occasionally bin return list chunks in first scan
    05041       * Add a few optimizations from colin@nyx10.cs.du.edu
    05042
    05043     V2.5.1 Sat Aug 14 15:40:43 1993  Doug Lea  (dl at g)
    05044       * faster bin computation & slightly different binning
    05045       * merged all consolidations to one part of malloc proper
    05046          (eliminating old malloc_find_space & malloc_clean_bin)
    05047       * Scan 2 returns chunks (not just 1)
    05048       * Propagate failure in realloc if malloc returns 0
    05049       * Add stuff to allow compilation on non-ANSI compilers
    05050           from kpv@research.att.com
    05051
    05052     V2.5 Sat Aug  7 07:41:59 1993  Doug Lea  (dl at g.oswego.edu)
    05053       * removed potential for odd address access in prev_chunk
    05054       * removed dependency on getpagesize.h
    05055       * misc cosmetics and a bit more internal documentation
    05056       * anticosmetics: mangled names in macros to evade debugger strangeness
    05057       * tested on sparc, hp-700, dec-mips, rs6000
    05058           with gcc & native cc (hp, dec only) allowing
    05059           Detlefs & Zorn comparison study (in SIGPLAN Notices.)
    05060
    05061     Trial version Fri Aug 28 13:14:29 1992  Doug Lea  (dl at g.oswego.edu)
    05062       * Based loosely on libg++-1.2X malloc. (It retains some of the overall
    05063          structure of old version,  but most details differ.)
    05064
    05065 */