/*

  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 */

#ifndef MORECORE

#define MORECORE sbrk

#endif

#define MORECORE_CONTIGUOUS 1

#define MORECORE_FAILURE    ((void*)(-1))

/* Use the supplied emulation of mmap and munmap */

#ifndef HAVE_MMAP

#define HAVE_MMAP 1

#endif

#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_LOCK

static int slwait(int *sl);

static int slrelease(int *sl);

#endif

static 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 __cplusplus

extern "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 */

#ifndef LACKS_ERRNO_H

#include <errno.h>    /* needed for optional MALLOC_FAILURE_ACTION */

#endif

/*

  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

/*

  INTERNAL_SIZE_T is the word-size used for internal bookkeeping

  of chunk sizes.

  The default version is the same as size_t.

  While not strictly necessary, it is best to define this as an

  unsigned type, even if size_t is a signed type. This may avoid some

  artificial size limitations on some systems.

  On a 64-bit machine, you may be able to reduce malloc overhead by

  defining INTERNAL_SIZE_T to be a 32 bit `unsigned int' at the

  expense of not being able to handle more than 2^32 of malloced

  space. If this limitation is acceptable, you are encouraged to set

  this unless you are on a platform requiring 16byte alignments. In

  this case the alignment requirements turn out to negate any

  potential advantages of decreasing size_t word size.

  Implementors: Beware of the possible combinations of:

     - INTERNAL_SIZE_T might be signed or unsigned, might be 32 or 64 bits,

       and might be the same width as int or as long

     - size_t might have different width and signedness as INTERNAL_SIZE_T

     - int and long might be 32 or 64 bits, and might be the same width

  To deal with this, most comparisons and difference computations

  among INTERNAL_SIZE_Ts should cast them to CHUNK_SIZE_T, being

  aware of the fact that casting an unsigned int to a wider long does

  not sign-extend. (This also makes checking for negative numbers

  awkward.) Some of these casts result in harmless compiler warnings

  on some systems.

*/

#ifndef INTERNAL_SIZE_T

#define INTERNAL_SIZE_T size_t

#endif

/* The corresponding word size */

#define SIZE_SZ                (sizeof(INTERNAL_SIZE_T))

/*

  MALLOC_ALIGNMENT is the minimum alignment for malloc'ed chunks.

  It must be a power of two at least 2 * SIZE_SZ, even on machines

  for which smaller alignments would suffice. It may be defined as

  larger than this though. Note however that code and data structures

  are optimized for the case of 8-byte alignment.

*/

#ifndef MALLOC_ALIGNMENT

#define MALLOC_ALIGNMENT       (2 * SIZE_SZ)

#endif

/* The corresponding bit mask value */

#define MALLOC_ALIGN_MASK      (MALLOC_ALIGNMENT - 1)

/*

  REALLOC_ZERO_BYTES_FREES should be set if a call to

  realloc with zero bytes should be the same as a call to free.

  Some people think it should. Otherwise, since this malloc

  returns a unique pointer for malloc(0), so does realloc(p, 0).

*/

/*   #define REALLOC_ZERO_BYTES_FREES */

/*

  TRIM_FASTBINS controls whether free() of a very small chunk can

  immediately lead to trimming. Setting to true (1) can reduce memory

  footprint, but will almost always slow down programs that use a lot

  of small chunks.

  Define this only if you are willing to give up some speed to more

  aggressively reduce system-level memory footprint when releasing

  memory in programs that use many small chunks.  You can get

  essentially the same effect by setting MXFAST to 0, but this can

  lead to even greater slowdowns in programs using many small chunks.

  TRIM_FASTBINS is an in-between compile-time option, that disables

  only those chunks bordering topmost memory from being placed in

  fastbins.

*/

#ifndef TRIM_FASTBINS

#define TRIM_FASTBINS  0

#endif

/*

  USE_DL_PREFIX will prefix all public routines with the string 'dl'.

  This is necessary when you only want to use this malloc in one part 

  of a program, using your regular system malloc elsewhere.

*/

/* #define USE_DL_PREFIX */

/*

  USE_MALLOC_LOCK causes wrapper functions to surround each

  callable routine with pthread mutex lock/unlock.

  USE_MALLOC_LOCK forces USE_PUBLIC_MALLOC_WRAPPERS to be defined

*/

/* #define USE_MALLOC_LOCK */

/*

  If USE_PUBLIC_MALLOC_WRAPPERS is defined, every public routine is

  actually a wrapper function that first calls MALLOC_PREACTION, then

  calls the internal routine, and follows it with

  MALLOC_POSTACTION. This is needed for locking, but you can also use

  this, without USE_MALLOC_LOCK, for purposes of interception,

  instrumentation, etc. It is a sad fact that using wrappers often

  noticeably degrades performance of malloc-intensive programs.

*/

#ifdef USE_MALLOC_LOCK

#define USE_PUBLIC_MALLOC_WRAPPERS

#else

/* #define USE_PUBLIC_MALLOC_WRAPPERS */

#endif

/* 

   Two-phase name translation.

   All of the actual routines are given mangled names.

   When wrappers are used, they become the public callable versions.

   When DL_PREFIX is used, the callable names are prefixed.

*/

#ifndef USE_PUBLIC_MALLOC_WRAPPERS

#define cALLOc      public_cALLOc

#define fREe        public_fREe

#define cFREe       public_cFREe

#define mALLOc      public_mALLOc