Subversion Repositories HelenOS-historic

/*

  This is a version (aka dlmalloc) of malloc/free/realloc written by

  Doug Lea and released to the public domain, as explained at

  http://creativecommons.org/licenses/publicdomain.  Send questions,

  comments, complaints, performance data, etc to dl@cs.oswego.edu

* Version 2.8.3 Thu Sep 22 11:16:15 2005  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 (-O3), and link it into another program. All of

  the compile-time options default to reasonable values for use on

  most platforms.  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.8.3.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. Note that 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 to customize settings or to avoid overheads associated

  with library versions.

* Vital statistics:

  Supported pointer/size_t representation:       4 or 8 bytes

       size_t MUST be an unsigned type of the same width as

       pointers. (If you are using an ancient system that declares

       size_t as a signed type, or need it to be a different width

       than pointers, you can use a previous release of this malloc

       (e.g. 2.7.2) supporting these.)

  Alignment:                                     8 bytes (default)

       This suffices for nearly all current machines and C compilers.

       However, you can define MALLOC_ALIGNMENT to be wider than this

       if necessary (up to 128bytes), at the expense of using more space.

  Minimum overhead per allocated chunk:   4 or  8 bytes (if 4byte sizes)

                                          8 or 16 bytes (if 8byte sizes)

       Each malloced chunk has a hidden word of overhead holding size

       and status information, and additional cross-check word

       if FOOTERS is defined.

  Minimum allocated size: 4-byte ptrs:  16 bytes    (including overhead)

                          8-byte ptrs:  32 bytes    (including overhead)

       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 about

       32 bytes plus the remainder from a system page (the minimal

       mmap unit); typically 4096 or 8192 bytes.

  Security: static-safe; optionally more or less

       The "security" of malloc refers to the ability of malicious

       code to accentuate the effects of errors (for example, freeing

       space that is not currently malloc'ed or overwriting past the

       ends of chunks) in code that calls malloc.  This malloc

       guarantees not to modify any memory locations below the base of

       heap, i.e., static variables, even in the presence of usage

       errors.  The routines additionally detect most improper frees

       and reallocs.  All this holds as long as the static bookkeeping

       for malloc itself is not corrupted by some other means.  This

       is only one aspect of security -- these checks do not, and

       cannot, detect all possible programming errors.

       If FOOTERS is defined nonzero, then each allocated chunk

       carries an additional check word to verify that it was malloced

       from its space.  These check words are the same within each

       execution of a program using malloc, but differ across

       executions, so externally crafted fake chunks cannot be

       freed. This improves security by rejecting frees/reallocs that

       could corrupt heap memory, in addition to the checks preventing

       writes to statics that are always on.  This may further improve

       security at the expense of time and space overhead.  (Note that

       FOOTERS may also be worth using with MSPACES.)

       By default detected errors cause the program to abort (calling

       "abort()"). You can override this to instead proceed past

       errors by defining PROCEED_ON_ERROR.  In this case, a bad free

       has no effect, and a malloc that encounters a bad address

       caused by user overwrites will ignore the bad address by

       dropping pointers and indices to all known memory. This may

       be appropriate for programs that should continue if at all

       possible in the face of programming errors, although they may

       run out of memory because dropped memory is never reclaimed.

       If you don't like either of these options, you can define

       CORRUPTION_ERROR_ACTION and USAGE_ERROR_ACTION to do anything

       else. And if if you are sure that your program using malloc has

       no errors or vulnerabilities, you can define INSECURE to 1,

       which might (or might not) provide a small performance improvement.

  Thread-safety: NOT thread-safe unless USE_LOCKS defined

       When USE_LOCKS is defined, each public call to malloc, free,

       etc is surrounded 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, consider instead using ptmalloc, which is derived from

       a version of this malloc. (See http://www.malloc.de).

  System requirements: Any combination of MORECORE and/or MMAP/MUNMAP

       This malloc can use unix sbrk or any emulation (invoked using

       the CALL_MORECORE macro) and/or mmap/munmap or any emulation

       (invoked using CALL_MMAP/CALL_MUNMAP) to get and release system

       memory.  On most unix systems, it tends to work best if both

       MORECORE and MMAP are enabled.  On Win32, it uses emulations

       based on VirtualAlloc. It also uses common C library functions

       like memset.

  Compliance: I believe it is compliant with the Single Unix Specification

       (See http://www.unix.org). Also SVID/XPG, ANSI C, and probably

       others as well.

* Overview of algorithms

  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.

  In most ways, this malloc is a best-fit allocator. Generally, it

  chooses the best-fitting existing chunk for a request, with ties

  broken in approximately least-recently-used order. (This strategy

  normally maintains low fragmentation.) However, for requests less

  than 256bytes, it deviates from best-fit when there is not an

  exactly fitting available chunk by preferring to use space adjacent

  to that used for the previous small request, as well as by breaking

  ties in approximately most-recently-used order. (These enhance

  locality of series of small allocations.)  And for very large requests

  (>= 256Kb by default), it relies on system memory mapping

  facilities, if supported.  (This helps avoid carrying around and

  possibly fragmenting memory used only for large chunks.)

  All operations (except malloc_stats and mallinfo) have execution

  times that are bounded by a constant factor of the number of bits in

  a size_t, not counting any clearing in calloc or copying in realloc,

  or actions surrounding MORECORE and MMAP that have times

  proportional to the number of non-contiguous regions returned by

  system allocation routines, which is often just 1.

  The implementation is not very modular and seriously overuses

  macros. Perhaps someday all C compilers will do as good a job

  inlining modular code as can now be done by brute-force expansion,

  but now, enough of them seem not to.

  Some compilers issue a lot of warnings about code that is

  dead/unreachable only on some platforms, and also about intentional

  uses of negation on unsigned types. All known cases of each can be

  ignored.

  For a longer but out of date high-level description, see

     http://gee.cs.oswego.edu/dl/html/malloc.html

* MSPACES

  If MSPACES is defined, then in addition to malloc, free, etc.,

  this file also defines mspace_malloc, mspace_free, etc. These

  are versions of malloc routines that take an "mspace" argument

  obtained using create_mspace, to control all internal bookkeeping.

  If ONLY_MSPACES is defined, only these versions are compiled.

  So if you would like to use this allocator for only some allocations,

  and your system malloc for others, you can compile with

  ONLY_MSPACES and then do something like...

    static mspace mymspace = create_mspace(0,0); // for example

    #define mymalloc(bytes)  mspace_malloc(mymspace, bytes)

  (Note: If you only need one instance of an mspace, you can instead

  use "USE_DL_PREFIX" to relabel the global malloc.)

  You can similarly create thread-local allocators by storing

  mspaces as thread-locals. For example:

    static __thread mspace tlms = 0;

    void*  tlmalloc(size_t bytes) {

      if (tlms == 0) tlms = create_mspace(0, 0);

      return mspace_malloc(tlms, bytes);

    }

    void  tlfree(void* mem) { mspace_free(tlms, mem); }

  Unless FOOTERS is defined, each mspace is completely independent.

  You cannot allocate from one and free to another (although

  conformance is only weakly checked, so usage errors are not always

  caught). If FOOTERS is defined, then each chunk carries around a tag

  indicating its originating mspace, and frees are directed to their

  originating spaces.

 -------------------------  Compile-time options ---------------------------

Be careful in setting #define values for numerical constants of type

size_t. On some systems, literal values are not automatically extended

to size_t precision unless they are explicitly casted.

WIN32                    default: defined if _WIN32 defined

  Defining WIN32 sets up defaults for MS environment and compilers.

  Otherwise defaults are for unix.

MALLOC_ALIGNMENT         default: (size_t)8

  Controls the minimum alignment for malloc'ed chunks.  It must be a

  power of two and at least 8, 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.

MSPACES                  default: 0 (false)

  If true, compile in support for independent allocation spaces.

  This is only supported if HAVE_MMAP is true.

ONLY_MSPACES             default: 0 (false)

  If true, only compile in mspace versions, not regular versions.

USE_LOCKS                default: 0 (false)

  Causes each call to each public routine to be surrounded with

  pthread or WIN32 mutex lock/unlock. (If set true, this can be

  overridden on a per-mspace basis for mspace versions.)

FOOTERS                  default: 0

  If true, provide extra checking and dispatching by placing

  information in the footers of allocated chunks. This adds

  space and time overhead.

INSECURE                 default: 0

  If true, omit checks for usage errors and heap space overwrites.

USE_DL_PREFIX            default: NOT defined

  Causes compiler to prefix all public routines with the string 'dl'.

  This can be useful when you only want to use this malloc in one part

  of a program, using your regular system malloc elsewhere.

ABORT                    default: defined as abort()

  Defines how to abort on failed checks.  On most systems, a failed

  check cannot die with an "assert" or even print an informative

  message, because the underlying print routines in turn call malloc,

  which will fail again.  Generally, the best policy is to simply call

  abort(). It's not very useful to do more than this because many

  errors due to overwriting will show up as address faults (null, odd

  addresses etc) rather than malloc-triggered checks, so will also

  abort.  Also, most compilers know that abort() does not return, so

  can better optimize code conditionally calling it.

PROCEED_ON_ERROR           default: defined as 0 (false)

  Controls whether detected bad addresses cause them to bypassed

  rather than aborting. If set, detected bad arguments to free and

  realloc are ignored. And all bookkeeping information is zeroed out

  upon a detected overwrite of freed heap space, thus losing the

  ability to ever return it from malloc again, but enabling the

  application to proceed. If PROCEED_ON_ERROR is defined, the

  static variable malloc_corruption_error_count is compiled in

  and can be examined to see if errors have occurred. This option

  generates slower code than the default abort policy.

DEBUG                    default: NOT defined

  The DEBUG setting is mainly intended for people trying to modify

  this code or diagnose problems when porting to new platforms.

  However, it may also be able to better isolate user errors than just

  using runtime checks.  The assertions in the check routines spell

  out in more detail the assumptions and invariants underlying the

  algorithms.  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 summaries.

ABORT_ON_ASSERT_FAILURE   default: defined as 1 (true)

  Debugging assertion failures can be nearly impossible if your

  version of the assert macro causes malloc to be called, which will

  lead to a cascade of further failures, blowing the runtime stack.

  ABORT_ON_ASSERT_FAILURE cause assertions failures to call abort(),

  which will usually make debugging easier.

MALLOC_FAILURE_ACTION     default: sets errno to ENOMEM, or no-op on win32

  The action to take before "return 0" when malloc fails to be able to

  return memory because there is none available.

HAVE_MORECORE             default: 1 (true) unless win32 or ONLY_MSPACES

  True if this system supports sbrk or an emulation of it.

MORECORE                  default: sbrk

  The name of the sbrk-style system routine to call to obtain more

  memory.  See below for guidance on writing custom MORECORE

  functions. The type of the argument to sbrk/MORECORE varies across

  systems.  It cannot be size_t, because it supports negative

  arguments, so it is normally the signed type of the same width as

  size_t (sometimes declared as "intptr_t").  It doesn't much matter

  though. Internally, we only call it with arguments less than half

  the max value of a size_t, which should work across all reasonable

  possibilities, although sometimes generating compiler warnings.  See

  near the end of this file for guidelines for creating a custom

  version of MORECORE.

MORECORE_CONTIGUOUS       default: 1 (true)

  If true, take advantage of fact that consecutive calls to MORECORE

  with positive arguments always return contiguous increasing

  addresses.  This is true of unix sbrk. It does not hurt too much to

  set it true anyway, since malloc copes with non-contiguities.

  Setting it false when definitely non-contiguous saves time

  and possibly wasted space it would take to discover this though.

MORECORE_CANNOT_TRIM      default: NOT defined

  True if MORECORE cannot release space back to the system when given

  negative arguments. This is generally necessary only if you are

  using a hand-crafted MORECORE function that cannot handle negative

  arguments.

HAVE_MMAP                 default: 1 (true)

  True if this system supports mmap or an emulation of it.  If so, and

  HAVE_MORECORE is not true, MMAP is used for all system

  allocation. If set and HAVE_MORECORE is true as well, MMAP is

  primarily used to directly allocate very large blocks. It is also

  used as a backup strategy in cases where MORECORE fails to provide

  space from system. Note: A single call to MUNMAP is assumed to be

  able to unmap memory that may have be allocated using multiple calls

  to MMAP, so long as they are adjacent.

HAVE_MREMAP               default: 1 on linux, else 0

  If true realloc() uses mremap() to re-allocate large blocks and

  extend or shrink allocation spaces.

MMAP_CLEARS               default: 1 on unix

  True if mmap clears memory so calloc doesn't need to. This is true

  for standard unix mmap using /dev/zero.

USE_BUILTIN_FFS            default: 0 (i.e., not used)

  Causes malloc to use the builtin ffs() function to compute indices.

  Some compilers may recognize and intrinsify ffs to be faster than the

  supplied C version. Also, the case of x86 using gcc is special-cased

  to an asm instruction, so is already as fast as it can be, and so

  this setting has no effect. (On most x86s, the asm version is only

  slightly faster than the C version.)

malloc_getpagesize         default: derive from system includes, or 4096.

  The system page size. To the extent possible, this malloc manages

  memory from the system in page-size units.  This may be (and

  usually is) a function rather than a constant. This is ignored

  if WIN32, where page size is determined using getSystemInfo during

  initialization.

USE_DEV_RANDOM             default: 0 (i.e., not used)

  Causes malloc to use /dev/random to initialize secure magic seed for

  stamping footers. Otherwise, the current time is used.

NO_MALLINFO                default: 0

  If defined, don't compile "mallinfo". This can be a simple way

  of dealing with mismatches between system declarations and

  those in this file.

MALLINFO_FIELD_TYPE        default: size_t

  The type of the fields in the mallinfo struct. This was originally

  defined as "int" in SVID etc, but is more usefully defined as

  size_t. The value is used only if  HAVE_USR_INCLUDE_MALLOC_H is not set

REALLOC_ZERO_BYTES_FREES    default: not defined

  This 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).

LACKS_UNISTD_H, LACKS_FCNTL_H, LACKS_SYS_PARAM_H, LACKS_SYS_MMAN_H

LACKS_STRINGS_H, LACKS_STRING_H, LACKS_SYS_TYPES_H,  LACKS_ERRNO_H

LACKS_STDLIB_H                default: NOT defined unless on WIN32

  Define these if your system does not have these header files.

  You might need to manually insert some of the declarations they provide.

DEFAULT_GRANULARITY        default: page size if MORECORE_CONTIGUOUS,

                                system_info.dwAllocationGranularity in WIN32,

                                otherwise 64K.

      Also settable using mallopt(M_GRANULARITY, x)

  The unit for allocating and deallocating memory from the system.  On

  most systems with contiguous MORECORE, there is no reason to

  make this more than a page. However, systems with MMAP tend to

  either require or encourage larger granularities.  You can increase

  this value to prevent system allocation functions to be called so

  often, especially if they are slow.  The value must be at least one

  page and must be a power of two.  Setting to 0 causes initialization

  to either page size or win32 region size.  (Note: In previous

  versions of malloc, the equivalent of this option was called

  "TOP_PAD")

DEFAULT_TRIM_THRESHOLD    default: 2MB

      Also settable using mallopt(M_TRIM_THRESHOLD, x)

  The maximum amount of unused top-most memory to keep before

  releasing via malloc_trim in free().  Automatic trimming is mainly

  useful in long-lived programs using contiguous MORECORE.  Because

  trimming via sbrk can be slow on some systems, and can sometimes be

  wasteful (in cases where programs immediately afterward allocate

  more large chunks) the value should be high enough so that your

  overall system performance would improve by releasing this much

  memory.  As a rough guide, you might set to a value close to the

  average size of a process (program) running on your system.

  Releasing this much memory would allow such a process to run in

  memory.  Generally, it is worth tuning trim thresholds when a

  program undergoes phases where several large chunks are allocated

  and released in ways that can reuse each other's storage, perhaps

  mixed with phases where there are no such chunks at all. The trim

  value must be greater than page size to have any useful effect.  To

  disable trimming completely, you can set to MAX_SIZE_T. Note that the trick

  some people use of mallocing a huge space and then freeing it at

  program startup, in an attempt to reserve system memory, doesn't

  have the intended effect under automatic trimming, since that memory

  will immediately be returned to the system.

DEFAULT_MMAP_THRESHOLD       default: 256K

      Also settable using mallopt(M_MMAP_THRESHOLD, x)

  The request size threshold for using MMAP to directly service a

  request. Requests of at least this size that cannot be allocated

  using already-existing space will be serviced via mmap.  (If enough

  normal freed space already exists it is used instead.)  Using mmap

  segregates relatively large chunks of memory so that they can be

  individually obtained and released from the host system. A request

  serviced through mmap is never reused by any other request (at least

  not directly; the system may just so happen to remap successive

  requests to the same locations).  Segregating space in this way has

  the benefits that: Mmapped space can always be individually released

  back to the system, which helps keep the system level memory demands

  of a long-lived program low.  Also, mapped memory doesn't become

  `locked' between other chunks, as can happen with normally allocated

  chunks, which means that even trimming via malloc_trim would not

  release them.  However, it has the disadvantage that the space

  cannot be reclaimed, consolidated, and then used to service later

  requests, as happens with normal chunks.  The advantages of mmap

  nearly always outweigh disadvantages for "large" chunks, but the

  value of "large" may vary across systems.  The default is an

  empirically derived value that works well in most systems. You can

  disable mmap by setting to MAX_SIZE_T.

*/

/** @addtogroup libcmalloc malloc

  * @brief Malloc originally written by Doug Lea and ported to HelenOS.

  * @ingroup libc

 * @{

 */

/** @file

 */

#include <sys/types.h>  /* For size_t */

/** Non-default helenos customizations */

#define LACKS_FCNTL_H

#define LACKS_SYS_MMAN_H

#define LACKS_SYS_PARAM_H

#undef HAVE_MMAP

#define HAVE_MMAP 0

#define LACKS_ERRNO_H

/* Set errno? */

#undef MALLOC_FAILURE_ACTION

#define MALLOC_FAILURE_ACTION

/* The maximum possible size_t value has all bits set */

#define MAX_SIZE_T           (~(size_t)0)

#define ONLY_MSPACES 0

#define MSPACES 0

#define MALLOC_ALIGNMENT ((size_t)8U)

#define FOOTERS 0

#define ABORT  abort()

#define ABORT_ON_ASSERT_FAILURE 1

#define PROCEED_ON_ERROR 0

#define USE_LOCKS 1

#define INSECURE 0

#define HAVE_MMAP 0

#define MMAP_CLEARS 1

#define HAVE_MORECORE 1

#define MORECORE_CONTIGUOUS 1

#define MORECORE sbrk

#define DEFAULT_GRANULARITY (0)  /* 0 means to compute in init_mparams */

#ifndef DEFAULT_TRIM_THRESHOLD

#ifndef MORECORE_CANNOT_TRIM

#define DEFAULT_TRIM_THRESHOLD ((size_t)2U * (size_t)1024U * (size_t)1024U)

#else   /* MORECORE_CANNOT_TRIM */

#define DEFAULT_TRIM_THRESHOLD MAX_SIZE_T

#endif  /* MORECORE_CANNOT_TRIM */

#endif  /* DEFAULT_TRIM_THRESHOLD */

#ifndef DEFAULT_MMAP_THRESHOLD

#if HAVE_MMAP

#define DEFAULT_MMAP_THRESHOLD ((size_t)256U * (size_t)1024U)

#else   /* HAVE_MMAP */

#define DEFAULT_MMAP_THRESHOLD MAX_SIZE_T

#endif  /* HAVE_MMAP */

#endif  /* DEFAULT_MMAP_THRESHOLD */

#ifndef USE_BUILTIN_FFS

#define USE_BUILTIN_FFS 0

#endif  /* USE_BUILTIN_FFS */

#ifndef USE_DEV_RANDOM

#define USE_DEV_RANDOM 0

#endif  /* USE_DEV_RANDOM */

#ifndef NO_MALLINFO

#define NO_MALLINFO 0

#endif  /* NO_MALLINFO */

#ifndef MALLINFO_FIELD_TYPE

#define MALLINFO_FIELD_TYPE size_t

#endif  /* MALLINFO_FIELD_TYPE */

/*

  mallopt tuning options.  SVID/XPG defines four standard parameter

  numbers for mallopt, normally defined in malloc.h.  None of these

  are used in this malloc, so setting them has no effect. But this

  malloc does support the following options.

*/

#define M_TRIM_THRESHOLD     (-1)

#define M_GRANULARITY        (-2)

#define M_MMAP_THRESHOLD     (-3)

/*

  ========================================================================

  To make a fully customizable malloc.h header file, cut everything

  above this line, put into file malloc.h, edit to suit, and #include it

  on the next line, as well as in programs that use this malloc.

  ========================================================================

*/

#include "malloc.h"

/*------------------------------ internal #includes ---------------------- */

#include <stdio.h>       /* for printing in malloc_stats */

#include <string.h>

#ifndef LACKS_ERRNO_H

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

#endif /* LACKS_ERRNO_H */

#if FOOTERS

#include <time.h>        /* for magic initialization */

#endif /* FOOTERS */

#ifndef LACKS_STDLIB_H

#include <stdlib.h>      /* for abort() */

#endif /* LACKS_STDLIB_H */

#ifdef DEBUG

#if ABORT_ON_ASSERT_FAILURE

#define assert(x) {if(!(x)) {printf(#x);ABORT;}}

#else /* ABORT_ON_ASSERT_FAILURE */

#include <assert.h>

#endif /* ABORT_ON_ASSERT_FAILURE */

#else  /* DEBUG */

#define assert(x)

#endif /* DEBUG */

#if USE_BUILTIN_FFS

#ifndef LACKS_STRINGS_H

#include <strings.h>     /* for ffs */

#endif /* LACKS_STRINGS_H */

#endif /* USE_BUILTIN_FFS */

#if HAVE_MMAP

#ifndef LACKS_SYS_MMAN_H

#include <sys/mman.h>    /* for mmap */

#endif /* LACKS_SYS_MMAN_H */

#ifndef LACKS_FCNTL_H

#include <fcntl.h>

#endif /* LACKS_FCNTL_H */

#endif /* HAVE_MMAP */

#if HAVE_MORECORE

#ifndef LACKS_UNISTD_H

#include <unistd.h>     /* for sbrk */

#else /* LACKS_UNISTD_H */

#if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)

extern void*     sbrk(ptrdiff_t);

#endif /* FreeBSD etc */

#endif /* LACKS_UNISTD_H */

#endif /* HAVE_MMAP */

#ifndef WIN32

#ifndef malloc_getpagesize

#  ifdef _SC_PAGESIZE         /* some SVR4 systems omit an underscore */

#    ifndef _SC_PAGE_SIZE

#      define _SC_PAGE_SIZE _SC_PAGESIZE

#    endif

#  endif

#  ifdef _SC_PAGE_SIZE

#    define malloc_getpagesize sysconf(_SC_PAGE_SIZE)

#  else

#    if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE)

       extern size_t getpagesize();

#      define malloc_getpagesize getpagesize()

#    else

#      ifdef WIN32 /* use supplied emulation of getpagesize */

#        define malloc_getpagesize getpagesize()

#      else

#        ifndef LACKS_SYS_PARAM_H

#          include <sys/param.h>

#        endif

#        ifdef EXEC_PAGESIZE

#          define malloc_getpagesize EXEC_PAGESIZE

#        else

#          ifdef NBPG

#            ifndef CLSIZE

#              define malloc_getpagesize NBPG

#            else

#              define malloc_getpagesize (NBPG * CLSIZE)

#            endif

#          else

#            ifdef NBPC

#              define malloc_getpagesize NBPC

#            else

#              ifdef PAGESIZE

#                define malloc_getpagesize PAGESIZE

#              else /* just guess */

#                define malloc_getpagesize ((size_t)4096U)

#              endif

#            endif

#          endif

#        endif

#      endif

#    endif

#  endif

#endif

#endif

/* ------------------- size_t and alignment properties -------------------- */

/* The byte and bit size of a size_t */

#define SIZE_T_SIZE         (sizeof(size_t))

#define SIZE_T_BITSIZE      (sizeof(size_t) << 3)

/* Some constants coerced to size_t */

/* Annoying but necessary to avoid errors on some plaftorms */

#define SIZE_T_ZERO         ((size_t)0)

#define SIZE_T_ONE          ((size_t)1)

#define SIZE_T_TWO          ((size_t)2)

#define TWO_SIZE_T_SIZES    (SIZE_T_SIZE<<1)

#define FOUR_SIZE_T_SIZES   (SIZE_T_SIZE<<2)

#define SIX_SIZE_T_SIZES    (FOUR_SIZE_T_SIZES+TWO_SIZE_T_SIZES)

#define HALF_MAX_SIZE_T     (MAX_SIZE_T / 2U)

/* The bit mask value corresponding to MALLOC_ALIGNMENT */

#define CHUNK_ALIGN_MASK    (MALLOC_ALIGNMENT - SIZE_T_ONE)

/* True if address a has acceptable alignment */

#define is_aligned(A)       (((size_t)((A)) & (CHUNK_ALIGN_MASK)) == 0)

/* the number of bytes to offset an address to align it */

#define align_offset(A)\

 ((((size_t)(A) & CHUNK_ALIGN_MASK) == 0)? 0 :\

  ((MALLOC_ALIGNMENT - ((size_t)(A) & CHUNK_ALIGN_MASK)) & CHUNK_ALIGN_MASK))

/* -------------------------- MMAP preliminaries ------------------------- */

/*

   If HAVE_MORECORE or HAVE_MMAP are false, we just define calls and

   checks to fail so compiler optimizer can delete code rather than

   using so many "#if"s.

*/

/* MORECORE and MMAP must return MFAIL on failure */

#define MFAIL                ((void*)(MAX_SIZE_T))

#define CMFAIL               ((char*)(MFAIL)) /* defined for convenience */

#if !HAVE_MMAP

#define IS_MMAPPED_BIT       (SIZE_T_ZERO)

#define USE_MMAP_BIT         (SIZE_T_ZERO)

#define CALL_MMAP(s)         MFAIL

#define CALL_MUNMAP(a, s)    (-1)

#define DIRECT_MMAP(s)       MFAIL

#else /* HAVE_MMAP */

#define IS_MMAPPED_BIT       (SIZE_T_ONE)

#define USE_MMAP_BIT         (SIZE_T_ONE)

#ifndef WIN32

#define CALL_MUNMAP(a, s)    munmap((a), (s))

#define MMAP_PROT            (PROT_READ|PROT_WRITE)

#if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)

#define MAP_ANONYMOUS        MAP_ANON

#endif /* MAP_ANON */

#ifdef MAP_ANONYMOUS

#define MMAP_FLAGS           (MAP_PRIVATE|MAP_ANONYMOUS)

#define CALL_MMAP(s)         mmap(0, (s), MMAP_PROT, MMAP_FLAGS, -1, 0)

#else /* MAP_ANONYMOUS */

/*

   Nearly all versions of mmap support MAP_ANONYMOUS, so the following

   is unlikely to be needed, but is supplied just in case.

*/

#define MMAP_FLAGS           (MAP_PRIVATE)

static int dev_zero_fd = -1; /* Cached file descriptor for /dev/zero. */

#define CALL_MMAP(s) ((dev_zero_fd < 0) ? \

           (dev_zero_fd = open("/dev/zero", O_RDWR), \

            mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0)) : \

            mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0))

#endif /* MAP_ANONYMOUS */

#define DIRECT_MMAP(s)       CALL_MMAP(s)

#else /* WIN32 */

/* Win32 MMAP via VirtualAlloc */

static void* win32mmap(size_t size) {

  void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT, PAGE_READWRITE);

  return (ptr != 0)? ptr: MFAIL;

}

/* For direct MMAP, use MEM_TOP_DOWN to minimize interference */

static void* win32direct_mmap(size_t size) {

  void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT|MEM_TOP_DOWN,

                           PAGE_READWRITE);

  return (ptr != 0)? ptr: MFAIL;

}

/* This function supports releasing coalesed segments */

static int win32munmap(void* ptr, size_t size) {

  MEMORY_BASIC_INFORMATION minfo;

  char* cptr = ptr;

  while (size) {

    if (VirtualQuery(cptr, &minfo, sizeof(minfo)) == 0)

      return -1;

    if (minfo.BaseAddress != cptr || minfo.AllocationBase != cptr ||

        minfo.State != MEM_COMMIT || minfo.RegionSize > size)

      return -1;

    if (VirtualFree(cptr, 0, MEM_RELEASE) == 0)

      return -1;

    cptr += minfo.RegionSize;

    size -= minfo.RegionSize;

  }

  return 0;

}

#define CALL_MMAP(s)         win32mmap(s)

#define CALL_MUNMAP(a, s)    win32munmap((a), (s))

#define DIRECT_MMAP(s)       win32direct_mmap(s)

#endif /* WIN32 */

#endif /* HAVE_MMAP */

#if HAVE_MMAP && HAVE_MREMAP

#define CALL_MREMAP(addr, osz, nsz, mv) mremap((addr), (osz), (nsz), (mv))

#else  /* HAVE_MMAP && HAVE_MREMAP */

#define CALL_MREMAP(addr, osz, nsz, mv) MFAIL

#endif /* HAVE_MMAP && HAVE_MREMAP */

#if HAVE_MORECORE

#define CALL_MORECORE(S)     MORECORE(S)

#else  /* HAVE_MORECORE */

#define CALL_MORECORE(S)     MFAIL

#endif /* HAVE_MORECORE */

/* mstate bit set if continguous morecore disabled or failed */

#define USE_NONCONTIGUOUS_BIT (4U)

/* segment bit set in create_mspace_with_base */

#define EXTERN_BIT            (8U)

/* --------------------------- Lock preliminaries ------------------------ */

#if USE_LOCKS

/*

  When locks are defined, there are up to two global locks:

  * If HAVE_MORECORE, morecore_mutex protects sequences of calls to

    MORECORE.  In many cases sys_alloc requires two calls, that should

    not be interleaved with calls by other threads.  This does not

    protect against direct calls to MORECORE by other threads not

    using this lock, so there is still code to cope the best we can on

    interference.

  * magic_init_mutex ensures that mparams.magic and other

    unique mparams values are initialized only once.

*/

/* By default use posix locks */

#include <futex.h>

#define MLOCK_T atomic_t

#define INITIAL_LOCK(l)      futex_initialize(l, 1)

/* futex_down cannot fail, but can return different

 * retvals for OK

 */

#define ACQUIRE_LOCK(l)      ({futex_down(l);0;})

#define RELEASE_LOCK(l)      futex_up(l)

#if HAVE_MORECORE

static MLOCK_T morecore_mutex = FUTEX_INITIALIZER;

#endif /* HAVE_MORECORE */

static MLOCK_T magic_init_mutex = FUTEX_INITIALIZER;

#define USE_LOCK_BIT               (2U)

#else  /* USE_LOCKS */

#define USE_LOCK_BIT               (0U)

#define INITIAL_LOCK(l)

#endif /* USE_LOCKS */

#if USE_LOCKS && HAVE_MORECORE

#define ACQUIRE_MORECORE_LOCK()    ACQUIRE_LOCK(&morecore_mutex);

#define RELEASE_MORECORE_LOCK()    RELEASE_LOCK(&morecore_mutex);

#else /* USE_LOCKS && HAVE_MORECORE */

#define ACQUIRE_MORECORE_LOCK()

#define RELEASE_MORECORE_LOCK()

#endif /* USE_LOCKS && HAVE_MORECORE */

#if USE_LOCKS

#define ACQUIRE_MAGIC_INIT_LOCK()  ACQUIRE_LOCK(&magic_init_mutex);

#define RELEASE_MAGIC_INIT_LOCK()  RELEASE_LOCK(&magic_init_mutex);

#else  /* USE_LOCKS */

#define ACQUIRE_MAGIC_INIT_LOCK()

#define RELEASE_MAGIC_INIT_LOCK()

#endif /* USE_LOCKS */

/* -----------------------  Chunk representations ------------------------ */

/*

  (The following includes lightly edited explanations by Colin Plumb.)

  The malloc_chunk declaration below is misleading (but accurate and

  necessary).  It declares a "view" into memory allowing access to

  necessary fields at known offsets from a given base.

  Chunks of memory are maintained using a `boundary tag' method as

  originally described by Knuth.  (See the paper by Paul Wilson

  ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a survey of such

  techniques.)  Sizes of free chunks are stored both in the front of

  each chunk and at the end.  This makes consolidating fragmented

  chunks into bigger chunks fast.  The head fields also hold bits

  representing whether chunks are free or in use.

  Here are some pictures to make it clearer.  They are "exploded" to

  show that the state of a chunk can be thought of as extending from

  the high 31 bits of the head field of its header through the

  prev_foot and PINUSE_BIT bit of the following chunk header.

  A chunk that's in use looks like:

   chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

           | Size of previous chunk (if P = 1)                             |

           +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|

         | Size of this chunk                                         1| +-+

   mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

         |                                                               |

         +-                                                             -+

         |                                                               |

         +-                                                             -+

         |                                                               :

         +-      size - sizeof(size_t) available payload bytes          -+

         :                                                               |

 chunk-> +-                                                             -+

         |                                                               |

         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1|

       | Size of next chunk (may or may not be in use)               | +-+

 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

    And if it's free, it looks like this:

   chunk-> +-                                                             -+

           | User payload (must be in use, or we would have merged!)       |

           +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|

         | Size of this chunk                                         0| +-+

   mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

         | Next pointer                                                  |

         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

         | Prev pointer                                                  |

         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

         |                                                               :

         +-      size - sizeof(struct chunk) unused bytes               -+

         :                                                               |

 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

         | Size of this chunk                                            |

         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0|

       | Size of next chunk (must be in use, or we would have merged)| +-+

 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

       |                                                               :

       +- User payload                                                -+

       :                                                               |

       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                                                                     |0|

                                                                     +-+

  Note that since we always merge adjacent free chunks, the chunks

  adjacent to a free chunk must be in use.

  Given a pointer to a chunk (which can be derived trivially from the

  payload pointer) we can, in O(1) time, find out whether the adjacent

  chunks are free, and if so, unlink them from the lists that they

  are on and merge them with the current chunk.

  Chunks always begin on even word boundaries, so the mem portion

  (which is returned to the user) is also on an even word boundary, and

  thus at least double-word aligned.

  The P (PINUSE_BIT) bit, stored in the unused low-order bit of the

  chunk size (which is always a multiple of two words), is an in-use

  bit for the *previous* chunk.  If that bit is *clear*, then the

  word before the current chunk size contains the previous chunk

  size, and can be used to find the front of the previous chunk.

  The very first chunk allocated always has this bit set, preventing

  access to non-existent (or non-owned) memory. If pinuse is set for

  any given chunk, then you CANNOT determine the size of the

  previous chunk, and might even get a memory addressing fault when

  trying to do so.

  The C (CINUSE_BIT) bit, stored in the unused second-lowest bit of

  the chunk size redundantly records whether the current chunk is

  inuse. This redundancy enables usage checks within free and realloc,

  and reduces indirection when freeing and consolidating chunks.

  Each freshly allocated chunk must have both cinuse and pinuse set.

  That is, each allocated chunk borders either a previously allocated

  and still in-use chunk, or the base of its memory arena. This is

  ensured by making all allocations from the the `lowest' part of any

  found chunk.  Further, no free chunk physically borders another one,

  so each free chunk is known to be preceded and followed by either

  inuse chunks or the ends of memory.

  Note that the `foot' of the current chunk is actually represented

  as the prev_foot of the NEXT chunk. This makes it easier to

  deal with alignments etc but can be very confusing when trying

  to extend or adapt this code.

  The exceptions to all this are

     1. The special chunk `top' is the top-most available chunk (i.e.,

        the one bordering the end of available memory). It is treated

        specially.  Top is never included in any bin, is used only if

        no other chunk is available, and is released back to the

        system if it is very large (see M_TRIM_THRESHOLD).  In effect,

        the top chunk is treated as larger (and thus less well

        fitting) than any other available chunk.  The top chunk

        doesn't update its trailing size field since there is no next

        contiguous chunk that would have to index off it. However,

        space is still allocated for it (TOP_FOOT_SIZE) to enable

        separation or merging when space is extended.

     3. Chunks allocated via mmap, which have the lowest-order bit

        (IS_MMAPPED_BIT) set in their prev_foot fields, and do not set

        PINUSE_BIT in their head fields.  Because they are allocated

        one-by-one, each must carry its own prev_foot field, which is

        also used to hold the offset this chunk has within its mmapped

        region, which is needed to preserve alignment. Each mmapped

        chunk is trailed by the first two fields of a fake next-chunk

        for sake of usage checks.

*/

struct malloc_chunk {

  size_t               prev_foot;  /* Size of previous chunk (if free).  */

  size_t               head;       /* Size and inuse bits. */

  struct malloc_chunk* fd;         /* double links -- used only if free. */

  struct malloc_chunk* bk;

};

typedef struct malloc_chunk  mchunk;

typedef struct malloc_chunk* mchunkptr;

typedef struct malloc_chunk* sbinptr;  /* The type of bins of chunks */

typedef unsigned int bindex_t;         /* Described below */

typedef unsigned int binmap_t;         /* Described below */

typedef unsigned int flag_t;           /* The type of various bit flag sets */

/* ------------------- Chunks sizes and alignments ----------------------- */

#define MCHUNK_SIZE         (sizeof(mchunk))

#if FOOTERS

#define CHUNK_OVERHEAD      (TWO_SIZE_T_SIZES)

#else /* FOOTERS */

#define CHUNK_OVERHEAD      (SIZE_T_SIZE)

#endif /* FOOTERS */

/* MMapped chunks need a second word of overhead ... */

#define MMAP_CHUNK_OVERHEAD (TWO_SIZE_T_SIZES)

/* ... and additional padding for fake next-chunk at foot */

#define MMAP_FOOT_PAD       (FOUR_SIZE_T_SIZES)

/* The smallest size we can malloc is an aligned minimal chunk */

#define MIN_CHUNK_SIZE\