/*  This is a version (aka dlmalloc) of malloc/free/realloc written by  Doug Lea and released to the public domain.  Use, modify, and  redistribute this code without permission or acknowledgement in any  way you wish.  Send questions, comments, complaints, performance  data, etc to dl@cs.oswego.edu* VERSION 2.7.2 Sat Aug 17 09:07:30 2002  Doug Lea  (dl at gee)   Note: There may be an updated version of this malloc obtainable at           ftp://gee.cs.oswego.edu/pub/misc/malloc.c         Check before installing!* Quickstart  This library is all in one file to simplify the most common usage:  ftp it, compile it (-O), and link it into another program. All  of the compile-time options default to reasonable values for use on  most unix platforms. Compile -DWIN32 for reasonable defaults on windows.  You might later want to step through various compile-time and dynamic  tuning options.  For convenience, an include file for code using this malloc is at:     ftp://gee.cs.oswego.edu/pub/misc/malloc-2.7.1.h  You don't really need this .h file unless you call functions not  defined in your system include files.  The .h file contains only the  excerpts from this file needed for using this malloc on ANSI C/C++  systems, so long as you haven't changed compile-time options about  naming and tuning parameters.  If you do, then you can create your  own malloc.h that does include all settings by cutting at the point  indicated below.* Why use this malloc?  This is not the fastest, most space-conserving, most portable, or  most tunable malloc ever written. However it is among the fastest  while also being among the most space-conserving, portable and tunable.  Consistent balance across these factors results in a good general-purpose  allocator for malloc-intensive programs.  The main properties of the algorithms are:  * For large (>= 512 bytes) requests, it is a pure best-fit allocator,    with ties normally decided via FIFO (i.e. least recently used).  * For small (<= 64 bytes by default) requests, it is a caching    allocator, that maintains pools of quickly recycled chunks.  * In between, and for combinations of large and small requests, it does    the best it can trying to meet both goals at once.  * For very large requests (>= 128KB by default), it relies on system    memory mapping facilities, if supported.  For a longer but slightly out of date high-level description, see     http://gee.cs.oswego.edu/dl/html/malloc.html  You may already by default be using a C library containing a malloc  that is  based on some version of this malloc (for example in  linux). You might still want to use the one in this file in order to  customize settings or to avoid overheads associated with library  versions.* Contents, described in more detail in "description of public routines" below.  Standard (ANSI/SVID/...)  functions:    malloc(size_t n);    calloc(size_t n_elements, size_t element_size);    free(Void_t* p);    realloc(Void_t* p, size_t n);    memalign(size_t alignment, size_t n);    valloc(size_t n);    mallinfo()    mallopt(int parameter_number, int parameter_value)  Additional functions:    independent_calloc(size_t n_elements, size_t size, Void_t* chunks[]);    independent_comalloc(size_t n_elements, size_t sizes[], Void_t* chunks[]);    pvalloc(size_t n);    cfree(Void_t* p);    malloc_trim(size_t pad);    malloc_usable_size(Void_t* p);    malloc_stats();* Vital statistics:  Supported pointer representation:       4 or 8 bytes  Supported size_t  representation:       4 or 8 bytes        Note that size_t is allowed to be 4 bytes even if pointers are 8.       You can adjust this by defining INTERNAL_SIZE_T  Alignment:                              2 * sizeof(size_t) (default)       (i.e., 8 byte alignment with 4byte size_t). This suffices for       nearly all current machines and C compilers. However, you can       define MALLOC_ALIGNMENT to be wider than this if necessary.  Minimum overhead per allocated chunk:   4 or 8 bytes       Each malloced chunk has a hidden word of overhead holding size       and status information.  Minimum allocated size: 4-byte ptrs:  16 bytes    (including 4 overhead)                          8-byte ptrs:  24/32 bytes (including, 4/8 overhead)       When a chunk is freed, 12 (for 4byte ptrs) or 20 (for 8 byte       ptrs but 4 byte size) or 24 (for 8/8) additional bytes are       needed; 4 (8) for a trailing size field and 8 (16) bytes for       free list pointers. Thus, the minimum allocatable size is       16/24/32 bytes.       Even a request for zero bytes (i.e., malloc(0)) returns a       pointer to something of the minimum allocatable size.       The maximum overhead wastage (i.e., number of extra bytes       allocated than were requested in malloc) is less than or equal       to the minimum size, except for requests >= mmap_threshold that       are serviced via mmap(), where the worst case wastage is 2 *       sizeof(size_t) bytes plus the remainder from a system page (the       minimal mmap unit); typically 4096 or 8192 bytes.  Maximum allocated size:  4-byte size_t: 2^32 minus about two pages                            8-byte size_t: 2^64 minus about two pages       It is assumed that (possibly signed) size_t values suffice to       represent chunk sizes. `Possibly signed' is due to the fact       that `size_t' may be defined on a system as either a signed or       an unsigned type. The ISO C standard says that it must be       unsigned, but a few systems are known not to adhere to this.       Additionally, even when size_t is unsigned, sbrk (which is by       default used to obtain memory from system) accepts signed       arguments, and may not be able to handle size_t-wide arguments       with negative sign bit.  Generally, values that would       appear as negative after accounting for overhead and alignment       are supported only via mmap(), which does not have this       limitation.       Requests for sizes outside the allowed range will perform an optional       failure action and then return null. (Requests may also       also fail because a system is out of memory.)  Thread-safety: NOT thread-safe unless USE_MALLOC_LOCK defined       When USE_MALLOC_LOCK is defined, wrappers are created to       surround every public call with either a pthread mutex or       a win32 spinlock (depending on WIN32). This is not       especially fast, and can be a major bottleneck.       It is designed only to provide minimal protection       in concurrent environments, and to provide a basis for       extensions.  If you are using malloc in a concurrent program,       you would be far better off obtaining ptmalloc, which is       derived from a version of this malloc, and is well-tuned for       concurrent programs. (See http://www.malloc.de) Note that       even when USE_MALLOC_LOCK is defined, you can can guarantee       full thread-safety only if no threads acquire memory through        direct calls to MORECORE or other system-level allocators.  Compliance: I believe it is compliant with the 1997 Single Unix Specification       (See http://www.opennc.org). Also SVID/XPG, ANSI C, and probably        others as well.* Synopsis of compile-time options:    People have reported using previous versions of this malloc on all    versions of Unix, sometimes by tweaking some of the defines    below. It has been tested most extensively on Solaris and    Linux. It is also reported to work on WIN32 platforms.    People also report using it in stand-alone embedded systems.    The implementation is in straight, hand-tuned ANSI C.  It is not    at all modular. (Sorry!)  It uses a lot of macros.  To be at all    usable, this code should be compiled using an optimizing compiler    (for example gcc -O3) that can simplify expressions and control    paths. (FAQ: some macros import variables as arguments rather than    declare locals because people reported that some debuggers    otherwise get confused.)    OPTION                     DEFAULT VALUE    Compilation Environment options:    __STD_C                    derived from C compiler defines    WIN32                      NOT defined    HAVE_MEMCPY                defined    USE_MEMCPY                 1 if HAVE_MEMCPY is defined    HAVE_MMAP                  defined as 1     MMAP_CLEARS                1    HAVE_MREMAP                0 unless linux defined    malloc_getpagesize         derived from system #includes, or 4096 if not    HAVE_USR_INCLUDE_MALLOC_H  NOT defined    LACKS_UNISTD_H             NOT defined unless WIN32    LACKS_SYS_PARAM_H          NOT defined unless WIN32    LACKS_SYS_MMAN_H           NOT defined unless WIN32    LACKS_FCNTL_H              NOT defined    Changing default word sizes:    INTERNAL_SIZE_T            size_t    MALLOC_ALIGNMENT           2 * sizeof(INTERNAL_SIZE_T)    PTR_UINT                   unsigned long    CHUNK_SIZE_T               unsigned long    Configuration and functionality options:    USE_DL_PREFIX              NOT defined    USE_PUBLIC_MALLOC_WRAPPERS NOT defined    USE_MALLOC_LOCK            NOT defined    DEBUG                      NOT defined    REALLOC_ZERO_BYTES_FREES   NOT defined    MALLOC_FAILURE_ACTION      errno = ENOMEM, if __STD_C defined, else no-op    TRIM_FASTBINS              0    FIRST_SORTED_BIN_SIZE      512    Options for customizing MORECORE:    MORECORE                   sbrk    MORECORE_CONTIGUOUS        1     MORECORE_CANNOT_TRIM       NOT defined    MMAP_AS_MORECORE_SIZE      (1024 * 1024)     Tuning options that are also dynamically changeable via mallopt:    DEFAULT_MXFAST             64    DEFAULT_TRIM_THRESHOLD     256 * 1024    DEFAULT_TOP_PAD            0    DEFAULT_MMAP_THRESHOLD     256 * 1024    DEFAULT_MMAP_MAX           65536    There are several other #defined constants and macros that you    probably don't want to touch unless you are extending or adapting malloc.*//*  WIN32 sets up defaults for MS environment and compilers.  Otherwise defaults are for unix.*//* #define WIN32 */#ifdef WIN32#define WIN32_LEAN_AND_MEAN#include <windows.h>/* Win32 doesn't supply or need the following headers */#define LACKS_UNISTD_H#define LACKS_SYS_PARAM_H#define LACKS_SYS_MMAN_H/* Use the supplied emulation of sbrk */#define MORECORE sbrk#define MORECORE_CONTIGUOUS 1#define MORECORE_FAILURE    ((void*)(-1))/* Use the supplied emulation of mmap and munmap */#define HAVE_MMAP 1#define MUNMAP_FAILURE  (-1)#define MMAP_CLEARS 1/* These values don't really matter in windows mmap emulation */#define MAP_PRIVATE 1#define MAP_ANONYMOUS 2#define PROT_READ 1#define PROT_WRITE 2/* Emulation functions defined at the end of this file *//* If USE_MALLOC_LOCK, use supplied critical-section-based lock functions */#ifdef USE_MALLOC_LOCKstatic int slwait(int *sl);static int slrelease(int *sl);#endifstatic long getpagesize(void);static long getregionsize(void);static void *sbrk(long size);static void *mmap(void *ptr, long size, long prot, long type, long handle, long arg);static long munmap(void *ptr, long size);static void vminfo (unsigned long*free, unsigned long*reserved, unsigned long*committed);static int cpuinfo (int whole, unsigned long*kernel, unsigned long*user);#endif/*  __STD_C should be nonzero if using ANSI-standard C compiler, a C++  compiler, or a C compiler sufficiently close to ANSI to get away  with it.*/#ifndef __STD_C#if defined(__STDC__) || defined(_cplusplus)#define __STD_C     1#else#define __STD_C     0#endif #endif /*__STD_C*//*  Void_t* is the pointer type that malloc should say it returns*/#ifndef Void_t#if (__STD_C || defined(WIN32))#define Void_t      void#else#define Void_t      char#endif#endif /*Void_t*/#if __STD_C#include <stddef.h>   /* for size_t */#else#include <sys/types.h>#endif#ifdef __cplusplusextern "C" {#endif/* define LACKS_UNISTD_H if your system does not have a <unistd.h>. *//* #define  LACKS_UNISTD_H */#ifndef LACKS_UNISTD_H#include <unistd.h>#endif/* define LACKS_SYS_PARAM_H if your system does not have a <sys/param.h>. *//* #define  LACKS_SYS_PARAM_H */#include <stdio.h>    /* needed for malloc_stats */#include <errno.h>    /* needed for optional MALLOC_FAILURE_ACTION *//*  Debugging:  Because freed chunks may be overwritten with bookkeeping fields, this  malloc will often die when freed memory is overwritten by user  programs.  This can be very effective (albeit in an annoying way)  in helping track down dangling pointers.  If you compile with -DDEBUG, a number of assertion checks are  enabled that will catch more memory errors. You probably won't be  able to make much sense of the actual assertion errors, but they  should help you locate incorrectly overwritten memory.  The  checking is fairly extensive, and will slow down execution  noticeably. Calling malloc_stats or mallinfo with DEBUG set will  attempt to check every non-mmapped allocated and free chunk in the  course of computing the summmaries. (By nature, mmapped regions  cannot be checked very much automatically.)  Setting DEBUG may also be helpful if you are trying to modify  this code. The assertions in the check routines spell out in more  detail the assumptions and invariants underlying the algorithms.  Setting DEBUG does NOT provide an automated mechanism for checking  that all accesses to malloced memory stay within their  bounds. However, there are several add-ons and adaptations of this  or other mallocs available that do this.*/#if DEBUG#include <assert.h>#else#define assert(x) ((void)0)#endif/*  The unsigned integer type used for comparing any two chunk sizes.  This should be at least as wide as size_t, but should not be signed.*/#ifndef CHUNK_SIZE_T#define CHUNK_SIZE_T unsigned long#endif/*   The unsigned integer type used to hold addresses when they are are  manipulated as integers. Except that it is not defined on all  systems, intptr_t would suffice.*/#ifndef PTR_UINT#define PTR_UINT unsigned long#endif