1 /*

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

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

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

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

     6 

     7 * Version 2.8.2 Sun Jun 12 16:05:14 2005  Doug Lea  (dl at gee)

     8 

     9    Note: There may be an updated version of this malloc obtainable at

    10            ftp://gee.cs.oswego.edu/pub/misc/malloc.c

    11          Check before installing!

    12 

    13 * Quickstart

    14 

    15   This library is all in one file to simplify the most common usage:

    16   ftp it, compile it (-O3), and link it into another program. All of

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

    18   most platforms.  You might later want to step through various

    19   compile-time and dynamic tuning options.

    20 

    21   For convenience, an include file for code using this malloc is at:

    22      ftp://gee.cs.oswego.edu/pub/misc/malloc-2.8.0.h

    23   You don't really need this .h file unless you call functions not

    24   defined in your system include files.  The .h file contains only the

    25   excerpts from this file needed for using this malloc on ANSI C/C++

    26   systems, so long as you haven't changed compile-time options about

    27   naming and tuning parameters.  If you do, then you can create your

    28   own malloc.h that does include all settings by cutting at the point

    29   indicated below. Note that you may already by default be using a C

    30   library containing a malloc that is based on some version of this

    31   malloc (for example in linux). You might still want to use the one

    32   in this file to customize settings or to avoid overheads associated

    33   with library versions.

    34 

    35 * Vital statistics:

    36 

    37   Supported pointer/size_t representation:       4 or 8 bytes

    38        size_t MUST be an unsigned type of the same width as

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

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

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

    42        (e.g. 2.7.2) supporting these.)

    43 

    44   Alignment:                                     8 bytes (default)

    45        This suffices for nearly all current machines and C compilers.

    46        However, you can define MALLOC_ALIGNMENT to be wider than this

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

    48 

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

    50                                           8 or 16 bytes (if 8byte sizes)

    51        Each malloced chunk has a hidden word of overhead holding size

    52        and status information, and additional cross-check word

    53        if FOOTERS is defined.

    54 

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

    56                           8-byte ptrs:  32 bytes    (including overhead)

    57 

    58        Even a request for zero bytes (i.e., malloc(0)) returns a

    59        pointer to something of the minimum allocatable size.

    60        The maximum overhead wastage (i.e., number of extra bytes

    61        allocated than were requested in malloc) is less than or equal

    62        to the minimum size, except for requests >= mmap_threshold that

    63        are serviced via mmap(), where the worst case wastage is about

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

    65        mmap unit); typically 4096 or 8192 bytes.

    66 

    67   Security: static-safe; optionally more or less

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

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

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

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

    72        guarantees not to modify any memory locations below the base of

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

    74        errors.  The routines additionally detect most improper frees

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

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

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

    78        cannot, detect all possible programming errors.

    79 

    80        If FOOTERS is defined nonzero, then each allocated chunk

    81        carries an additional check word to verify that it was malloced

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

    83        execution of a program using malloc, but differ across

    84        executions, so externally crafted fake chunks cannot be

    85        freed. This improves security by rejecting frees/reallocs that

    86        could corrupt heap memory, in addition to the checks preventing

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

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

    89        FOOTERS may also be worth using with MSPACES.)

    90 

    91        By default detected errors cause the program to abort (calling

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

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

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

    95        caused by user overwrites will ignore the bad address by

    96        dropping pointers and indices to all known memory. This may

    97        be appropriate for programs that should continue if at all

    98        possible in the face of programming errors, although they may

    99        run out of memory because dropped memory is never reclaimed.

   100 

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

   102        CORRUPTION_ERROR_ACTION and USAGE_ERROR_ACTION to do anything

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

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

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

   106 

   107   Thread-safety: NOT thread-safe unless USE_LOCKS defined

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

   109        etc is surrounded with either a pthread mutex or a win32

   110        spinlock (depending on WIN32). This is not especially fast, and

   111        can be a major bottleneck.  It is designed only to provide

   112        minimal protection in concurrent environments, and to provide a

   113        basis for extensions.  If you are using malloc in a concurrent

   114        program, consider instead using ptmalloc, which is derived from

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

   116 

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

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

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

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

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

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

   123        based on VirtualAlloc. It also uses common C library functions

   124        like memset.

   125 

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

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

   128        others as well.

   129 

   130 * Overview of algorithms

   131 

   132   This is not the fastest, most space-conserving, most portable, or

   133   most tunable malloc ever written. However it is among the fastest

   134   while also being among the most space-conserving, portable and

   135   tunable.  Consistent balance across these factors results in a good

   136   general-purpose allocator for malloc-intensive programs.

   137 

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

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

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

   141   normally maintains low fragmentation.) However, for requests less

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

   143   exactly fitting available chunk by preferring to use space adjacent

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

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

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

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

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

   149   possibly fragmenting memory used only for large chunks.)

   150 

   151   All operations (except malloc_stats and mallinfo) have execution

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

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

   154   or actions surrounding MORECORE and MMAP that have times

   155   proportional to the number of non-contiguous regions returned by

   156   system allocation routines, which is often just 1.

   157 

   158   The implementation is not very modular and seriously overuses

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

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

   161   but now, enough of them seem not to.

   162 

   163   Some compilers issue a lot of warnings about code that is

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

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

   166   ignored.

   167 

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

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

   170 

   171 * MSPACES

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

   173   this file also defines mspace_malloc, mspace_free, etc. These

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

   175   obtained using create_mspace, to control all internal bookkeeping.

   176   If ONLY_MSPACES is defined, only these versions are compiled.

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

   178   and your system malloc for others, you can compile with

   179   ONLY_MSPACES and then do something like...

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

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

   182 

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

   184   use "USE_DL_PREFIX" to relabel the global malloc.)

   185 

   186   You can similarly create thread-local allocators by storing

   187   mspaces as thread-locals. For example:

   188     static __thread mspace tlms = 0;

   189     void*  tlmalloc(size_t bytes) {

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

   191       return mspace_malloc(tlms, bytes);

   192     }

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

   194 

   195   Unless FOOTERS is defined, each mspace is completely independent.

   196   You cannot allocate from one and free to another (although

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

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

   199   indicating its originating mspace, and frees are directed to their

   200   originating spaces.

   201 

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

   203 

   204 WIN32                    default: defined if _WIN32 defined

   205   Defining WIN32 sets up defaults for MS environment and compilers.

   206   Otherwise defaults are for unix.

   207 

   208 MALLOC_ALIGNMENT         default: 8

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

   210   power of two and at least 8, even on machines for which smaller

   211   alignments would suffice. It may be defined as larger than this

   212   though. Note however that code and data structures are optimized for

   213   the case of 8-byte alignment.

   214 

   215 MSPACES                  default: 0 (false)

   216   If true, compile in support for independent allocation spaces.

   217   This is only supported if HAVE_MMAP is true.

   218 

   219 ONLY_MSPACES             default: 0 (false)

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

   221 

   222 USE_LOCKS                default: 0 (false)

   223   Causes each call to each public routine to be surrounded with

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

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

   226 

   227 FOOTERS                  default: 0

   228   If true, provide extra checking and dispatching by placing

   229   information in the footers of allocated chunks. This adds

   230   space and time overhead.

   231 

   232 INSECURE                 default: 0

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

   234 

   235 USE_DL_PREFIX            default: NOT defined

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

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

   238   of a program, using your regular system malloc elsewhere.

   239 

   240 ABORT                    default: defined as abort()

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

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

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

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

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

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

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

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

   249   can better optimize code conditionally calling it.

   250 

   251 PROCEED_ON_ERROR           default: defined as 0 (false)

   252   Controls whether detected bad addresses cause them to bypassed

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

   254   realloc are ignored. And all bookkeeping information is zeroed out

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

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

   257   application to proceed. If PROCEED_ON_ERROR is defined, the

   258   static variable malloc_corruption_error_count is compiled in

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

   260   generates slower code than the default abort policy.

   261 

   262 DEBUG                    default: NOT defined

   263   The DEBUG setting is mainly intended for people trying to modify

   264   this code or diagnose problems when porting to new platforms.

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

   266   using runtime checks.  The assertions in the check routines spell

   267   out in more detail the assumptions and invariants underlying the

   268   algorithms.  The checking is fairly extensive, and will slow down

   269   execution noticeably. Calling malloc_stats or mallinfo with DEBUG

   270   set will attempt to check every non-mmapped allocated and free chunk

   271   in the course of computing the summaries.

   272 

   273 ABORT_ON_ASSERT_FAILURE   default: defined as 1 (true)

   274   Debugging assertion failures can be nearly impossible if your

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

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

   277   ABORT_ON_ASSERT_FAILURE cause assertions failures to call abort(),

   278   which will usually make debugging easier.

   279 

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

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

   282   return memory because there is none available.

   283 

   284 HAVE_MORECORE             default: 1 (true) unless win32 or ONLY_MSPACES

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

   286 

   287 MORECORE                  default: sbrk

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

   289   memory.  See below for guidance on writing custom MORECORE

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

   291   systems.  It cannot be size_t, because it supports negative

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

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

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

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

   296   possibilities, although sometimes generating compiler warnings.  See

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

   298   version of MORECORE.

   299 

   300 MORECORE_CONTIGUOUS       default: 1 (true)

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

   302   with positive arguments always return contiguous increasing

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

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

   305   Setting it false when definitely non-contiguous saves time

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

   307 

   308 MORECORE_CANNOT_TRIM      default: NOT defined

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

   310   negative arguments. This is generally necessary only if you are

   311   using a hand-crafted MORECORE function that cannot handle negative

   312   arguments.

   313 

   314 HAVE_MMAP                 default: 1 (true)

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

   316   HAVE_MORECORE is not true, MMAP is used for all system

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

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

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

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

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

   322   to MMAP, so long as they are adjacent.

   323 

   324 HAVE_MREMAP               default: 1 on linux, else 0

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

   326   extend or shrink allocation spaces.

   327 

   328 MMAP_CLEARS               default: 1 on unix

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

   330   for standard unix mmap using /dev/zero.

   331 

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

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

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

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

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

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

   338   slightly faster than the C version.)

   339 

   340 malloc_getpagesize         default: derive from system includes, or 4096.

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

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

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

   344   if WIN32, where page size is determined using getSystemInfo during

   345   initialization.

   346 

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

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

   349   stamping footers. Otherwise, the current time is used.

   350 

   351 NO_MALLINFO                default: 0

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

   353   of dealing with mismatches between system declarations and

   354   those in this file.

   355 

   356 MALLINFO_FIELD_TYPE        default: size_t

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

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

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

   360 

   361 LACKS_UNISTD_H, LACKS_FCNTL_H, LACKS_SYS_PARAM_H, LACKS_SYS_MMAN_H

   362 LACKS_STRINGS_H, LACKS_STRING_H, LACKS_SYS_TYPES_H,  LACKS_ERRNO_H

   363 LACKS_STDLIB_H                default: NOT defined unless on WIN32

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

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

   366 

   367 DEFAULT_GRANULARITY        default: page size if MORECORE_CONTIGUOUS,

   368                                 system_info.dwAllocationGranularity in WIN32,

   369                                 otherwise 64K.

   370       Also settable using mallopt(M_GRANULARITY, x)

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

   372   most systems with contiguous MORECORE, there is no reason to

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

   374   either require or encourage larger granularities.  You can increase

   375   this value to prevent system allocation functions to be called so

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

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

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

   379   versions of malloc, the equivalent of this option was called

   380   "TOP_PAD")

   381 

   382 DEFAULT_TRIM_THRESHOLD    default: 2MB

   383       Also settable using mallopt(M_TRIM_THRESHOLD, x)

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

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

   386   useful in long-lived programs using contiguous MORECORE.  Because

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

   388   wasteful (in cases where programs immediately afterward allocate

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

   390   overall system performance would improve by releasing this much

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

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

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

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

   395   program undergoes phases where several large chunks are allocated

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

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

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

   399   disable trimming completely, you can set to -1U. Note that the trick

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

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

   402   have the intended effect under automatic trimming, since that memory

   403   will immediately be returned to the system.

   404 

   405 DEFAULT_MMAP_THRESHOLD       default: 256K

   406       Also settable using mallopt(M_MMAP_THRESHOLD, x)

   407   The request size threshold for using MMAP to directly service a

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

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

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

   411   segregates relatively large chunks of memory so that they can be

   412   individually obtained and released from the host system. A request

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

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

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

   416   the benefits that: Mmapped space can always be individually released

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

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

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

   420   chunks, which means that even trimming via malloc_trim would not

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

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

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

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

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

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

   427   disable mmap by setting to -1U.

   428 

   429 */

   430 #include <e32base.h>

   431 #include <e32hal.h>

   432 #include <hal.h>

   433 

   434 #include "MemoryManager.h"

   435 

   436 //#define OOM_LOGGING

   437 #include "MemoryLogger.h"

   438 

   439 /*

   440 #ifndef WIN32

   441 #ifdef _WIN32

   442 #define WIN32 1

   443 #endif

   444 #endif

   445 */

   446 #ifdef WIN32

   447 #define WIN32_LEAN_AND_MEAN

   448 #include <windows.h>

   449 #define HAVE_MMAP 1

   450 #define HAVE_MORECORE 0

   451 #define LACKS_UNISTD_H

   452 #define LACKS_SYS_PARAM_H

   453 #define LACKS_SYS_MMAN_H

   454 #define LACKS_STRING_H

   455 #define LACKS_STRINGS_H

   456 #define LACKS_SYS_TYPES_H

   457 #define LACKS_ERRNO_H

   458 #define MALLOC_FAILURE_ACTION

   459 #define MMAP_CLEARS 0 /* WINCE and some others apparently don't clear */

   460 #endif

   461 

   462 #if defined(DARWIN) || defined(_DARWIN)

   463 /* Mac OSX docs advise not to use sbrk; it seems better to use mmap */

   464 #ifndef HAVE_MORECORE

   465 #define HAVE_MORECORE 0

   466 #define HAVE_MMAP 1

   467 #endif

   468 #endif

   469 

   470 #define LACKS_SYS_MMAN_H 1

   471 #ifndef LACKS_SYS_TYPES_H

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

   473 #endif

   474 #ifndef ONLY_MSPACES

   475 #define ONLY_MSPACES 0

   476 #endif

   477 #ifndef MSPACES

   478 #if ONLY_MSPACES

   479 #define MSPACES 1

   480 #else

   481 #define MSPACES 0

   482 #endif

   483 #endif

   484 #ifndef MALLOC_ALIGNMENT

   485 #define MALLOC_ALIGNMENT (8U)

   486 #endif

   487 #ifndef FOOTERS

   488 #define FOOTERS 0

   489 #endif

   490 #ifndef ABORT

   491 #define ABORT  log_abort(__FILE__, __LINE__)

   492 #endif

   493 #ifndef ABORT_ON_ASSERT_FAILURE

   494 #define ABORT_ON_ASSERT_FAILURE 1

   495 #endif

   496 #ifndef PROCEED_ON_ERROR

   497 #define PROCEED_ON_ERROR 0

   498 #endif

   499 #ifndef USE_LOCKS

   500 #define USE_LOCKS 1

   501 #endif

   502 #ifndef INSECURE

   503 #define INSECURE 1

   504 #endif

   505 #ifndef HAVE_MMAP

   506 #define HAVE_MMAP 1

   507 #endif

   508 #ifndef MMAP_CLEARS

   509 #define MMAP_CLEARS 1

   510 #endif

   511 #ifndef HAVE_MREMAP

   512 #ifdef linux

   513 #define HAVE_MREMAP 1

   514 #else

   515 #define HAVE_MREMAP 0

   516 #endif

   517 #endif

   518 #ifndef MALLOC_FAILURE_ACTION

   519 #define MALLOC_FAILURE_ACTION  errno = ENOMEM;

   520 #endif

   521 #ifndef HAVE_MORECORE

   522 #if ONLY_MSPACES

   523 #define HAVE_MORECORE 0

   524 #else

   525 #define HAVE_MORECORE 1

   526 #endif

   527 #endif

   528 #if !HAVE_MORECORE

   529 #define MORECORE_CONTIGUOUS 0

   530 #else

   531 #ifndef MORECORE

   532 #define MORECORE chunkMoreCore

   533 #endif

   534 #ifndef MORECORE_CONTIGUOUS

   535 #define MORECORE_CONTIGUOUS 1

   536 #endif

   537 #endif

   538 #ifndef DEFAULT_GRANULARITY

   539 #if MORECORE_CONTIGUOUS

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

   541 #else

   542 #define DEFAULT_GRANULARITY (64 * 1024U)

   543 #endif

   544 #endif

   545 #ifndef DEFAULT_TRIM_THRESHOLD

   546 #ifndef MORECORE_CANNOT_TRIM

   547 #define DEFAULT_TRIM_THRESHOLD (64 * 1024U)

   548 #else

   549 #define DEFAULT_TRIM_THRESHOLD (-1U)

   550 #endif

   551 #endif

   552 #ifndef DEFAULT_MMAP_THRESHOLD

   553 #if HAVE_MMAP

   554 #define DEFAULT_MMAP_THRESHOLD (4U * 1024U)

   555 #else

   556 #define DEFAULT_MMAP_THRESHOLD (-1U)

   557 #endif

   558 #endif

   559 #ifndef USE_BUILTIN_FFS

   560 #define USE_BUILTIN_FFS 0

   561 #endif

   562 #ifndef USE_DEV_RANDOM

   563 #define USE_DEV_RANDOM 0

   564 #endif

   565 #ifndef NO_MALLINFO

   566 #define NO_MALLINFO 0

   567 #endif

   568 #ifndef MALLINFO_FIELD_TYPE

   569 #define MALLINFO_FIELD_TYPE size_t

   570 #endif

   571 

   572 /*

   573   mallopt tuning options.  SVID/XPG defines four standard parameter

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

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

   576   malloc does support the following options.

   577 */

   578 

   579 #define M_TRIM_THRESHOLD     (-1)

   580 #define M_GRANULARITY        (-2)

   581 #define M_MMAP_THRESHOLD     (-3)

   582 

   583 /* ------------------------ Mallinfo declarations ------------------------ */

   584 

   585 #if !NO_MALLINFO

   586 /*

   587   This version of malloc supports the standard SVID/XPG mallinfo

   588   routine that returns a struct containing usage properties and

   589   statistics. It should work on any system that has a

   590   /usr/include/malloc.h defining struct mallinfo.  The main

   591   declaration needed is the mallinfo struct that is returned (by-copy)

   592   by mallinfo().  The malloinfo struct contains a bunch of fields that

   593   are not even meaningful in this version of malloc.  These fields are

   594   are instead filled by mallinfo() with other numbers that might be of

   595   interest.

   596 

   597   HAVE_USR_INCLUDE_MALLOC_H should be set if you have a

   598   /usr/include/malloc.h file that includes a declaration of struct

   599   mallinfo.  If so, it is included; else a compliant version is

   600   declared below.  These must be precisely the same for mallinfo() to

   601   work.  The original SVID version of this struct, defined on most

   602   systems with mallinfo, declares all fields as ints. But some others

   603   define as unsigned long. If your system defines the fields using a

   604   type of different width than listed here, you MUST #include your

   605   system version and #define HAVE_USR_INCLUDE_MALLOC_H.

   606 */

   607 

   608 /* #define HAVE_USR_INCLUDE_MALLOC_H */

   609 

   610 #ifdef HAVE_USR_INCLUDE_MALLOC_H

   611 #include "/usr/include/malloc.h"

   612 #else

   613 

   614 struct mallinfo {

   615   MALLINFO_FIELD_TYPE arena;    /* non-mmapped space allocated from system */

   616   MALLINFO_FIELD_TYPE ordblks;  /* number of free chunks */

   617   MALLINFO_FIELD_TYPE smblks;   /* always 0 */

   618   MALLINFO_FIELD_TYPE hblks;    /* always 0 */

   619   MALLINFO_FIELD_TYPE hblkhd;   /* space in mmapped regions */

   620   MALLINFO_FIELD_TYPE usmblks;  /* maximum total allocated space */

   621   MALLINFO_FIELD_TYPE fsmblks;  /* always 0 */

   622   MALLINFO_FIELD_TYPE uordblks; /* total allocated space */

   623   MALLINFO_FIELD_TYPE fordblks; /* total free space */

   624   MALLINFO_FIELD_TYPE keepcost; /* releasable (via malloc_trim) space */

   625 };

   626 

   627 #endif

   628 #endif

   629 

   630 #if !ONLY_MSPACES

   631 

   632 /* ------------------- Declarations of public routines ------------------- */

   633 

   634 #ifndef USE_DL_PREFIX

   635 #define dlcalloc               fast_calloc

   636 #define dlfree                 fast_free

   637 #define dlmalloc               fast_malloc

   638 #define dlmemalign             fast_memalign

   639 #define dlrealloc              fast_realloc

   640 #define dlvalloc               fast_valloc

   641 #define dlpvalloc              fast_pvalloc

   642 #define dlmallinfo             fast_mallinfo

   643 #define dlmallopt              fast_mallopt

   644 #define dlmalloc_trim          fast_malloc_trim

   645 #define dlmalloc_stats         fast_malloc_stats

   646 #define dlmalloc_usable_size   fast_malloc_usable_size

   647 #define dlmalloc_footprint     fast_malloc_footprint

   648 #define dlindependent_calloc   fast_independent_calloc

   649 #define dlindependent_comalloc fast_independent_comalloc

   650 #endif

   651 

   652 

   653 /*

   654   malloc(size_t n)

   655   Returns a pointer to a newly allocated chunk of at least n bytes, or

   656   null if no space is available, in which case errno is set to ENOMEM

   657   on ANSI C systems.

   658 

   659   If n is zero, malloc returns a minimum-sized chunk. (The minimum

   660   size is 16 bytes on most 32bit systems, and 32 bytes on 64bit

   661   systems.)  Note that size_t is an unsigned type, so calls with

   662   arguments that would be negative if signed are interpreted as

   663   requests for huge amounts of space, which will often fail. The

   664   maximum supported value of n differs across systems, but is in all

   665   cases less than the maximum representable value of a size_t.

   666 */

   667 void* dlmalloc(size_t);

   668 

   669 /*

   670   free(void* p)

   671   Releases the chunk of memory pointed to by p, that had been previously

   672   allocated using malloc or a related routine such as realloc.

   673   It has no effect if p is null. If p was not malloced or already

   674   freed, free(p) will by default cuase the current program to abort.

   675 */

   676 void  dlfree(void*);

   677 

   678 /*

   679   calloc(size_t n_elements, size_t element_size);

   680   Returns a pointer to n_elements * element_size bytes, with all locations

   681   set to zero.

   682 */

   683 void* dlcalloc(size_t, size_t);

   684 

   685 /*

   686   realloc(void* p, size_t n)

   687   Returns a pointer to a chunk of size n that contains the same data

   688   as does chunk p up to the minimum of (n, p's size) bytes, or null

   689   if no space is available.

   690 

   691   The returned pointer may or may not be the same as p. The algorithm

   692   prefers extending p in most cases when possible, otherwise it

   693   employs the equivalent of a malloc-copy-free sequence.

   694 

   695   If p is null, realloc is equivalent to malloc.

   696 

   697   If space is not available, realloc returns null, errno is set (if on

   698   ANSI) and p is NOT freed.

   699 

   700   if n is for fewer bytes than already held by p, the newly unused

   701   space is lopped off and freed if possible.  realloc with a size

   702   argument of zero (re)allocates a minimum-sized chunk.

   703 

   704   The old unix realloc convention of allowing the last-free'd chunk

   705   to be used as an argument to realloc is not supported.

   706 */

   707 

   708 void* dlrealloc(void*, size_t);

   709 

   710 /*

   711   memalign(size_t alignment, size_t n);

   712   Returns a pointer to a newly allocated chunk of n bytes, aligned

   713   in accord with the alignment argument.

   714 

   715   The alignment argument should be a power of two. If the argument is

   716   not a power of two, the nearest greater power is used.

   717   8-byte alignment is guaranteed by normal malloc calls, so don't

   718   bother calling memalign with an argument of 8 or less.

   719 

   720   Overreliance on memalign is a sure way to fragment space.

   721 */

   722 void* dlmemalign(size_t, size_t);

   723 

   724 /*

   725   valloc(size_t n);

   726   Equivalent to memalign(pagesize, n), where pagesize is the page

   727   size of the system. If the pagesize is unknown, 4096 is used.

   728 */

   729 void* dlvalloc(size_t);

   730 

   731 /*

   732   mallopt(int parameter_number, int parameter_value)

   733   Sets tunable parameters The format is to provide a

   734   (parameter-number, parameter-value) pair.  mallopt then sets the

   735   corresponding parameter to the argument value if it can (i.e., so

   736   long as the value is meaningful), and returns 1 if successful else

   737   0.  SVID/XPG/ANSI defines four standard param numbers for mallopt,

   738   normally defined in malloc.h.  None of these are use in this malloc,

   739   so setting them has no effect. But this malloc also supports other

   740   options in mallopt. See below for details.  Briefly, supported

   741   parameters are as follows (listed defaults are for "typical"

   742   configurations).

   743 

   744   Symbol            param #  default    allowed param values

   745   M_TRIM_THRESHOLD     -1   2*1024*1024   any   (-1U disables trimming)

   746   M_GRANULARITY        -2     page size   any power of 2 >= page size

   747   M_MMAP_THRESHOLD     -3      256*1024   any   (or 0 if no MMAP support)

   748 */

   749 int dlmallopt(int, int);

   750 

   751 /*

   752   malloc_footprint();

   753   Returns the number of bytes obtained from the system.  The total

   754   number of bytes allocated by malloc, realloc etc., is less than this

   755   value. Unlike mallinfo, this function returns only a precomputed

   756   result, so can be called frequently to monitor memory consumption.

   757   Even if locks are otherwise defined, this function does not use them,

   758   so results might not be up to date.

   759 */

   760 size_t dlmalloc_footprint();

   761 

   762 #if !NO_MALLINFO

   763 /*

   764   mallinfo()

   765   Returns (by copy) a struct containing various summary statistics:

   766 

   767   arena:     current total non-mmapped bytes allocated from system

   768   ordblks:   the number of free chunks

   769   smblks:    always zero.

   770   hblks:     current number of mmapped regions

   771   hblkhd:    total bytes held in mmapped regions

   772   usmblks:   the maximum total allocated space. This will be greater

   773                 than current total if trimming has occurred.

   774   fsmblks:   always zero

   775   uordblks:  current total allocated space (normal or mmapped)

   776   fordblks:  total free space

   777   keepcost:  the maximum number of bytes that could ideally be released

   778                back to system via malloc_trim. ("ideally" means that

   779                it ignores page restrictions etc.)

   780 

   781   Because these fields are ints, but internal bookkeeping may

   782   be kept as longs, the reported values may wrap around zero and

   783   thus be inaccurate.

   784 */

   785 struct mallinfo dlmallinfo(void);

   786 #endif

   787 

   788 /*

   789   independent_calloc(size_t n_elements, size_t element_size, void* chunks[]);

   790 

   791   independent_calloc is similar to calloc, but instead of returning a

   792   single cleared space, it returns an array of pointers to n_elements

   793   independent elements that can hold contents of size elem_size, each

   794   of which starts out cleared, and can be independently freed,

   795   realloc'ed etc. The elements are guaranteed to be adjacently

   796   allocated (this is not guaranteed to occur with multiple callocs or

   797   mallocs), which may also improve cache locality in some

   798   applications.

   799 

   800   The "chunks" argument is optional (i.e., may be null, which is

   801   probably the most typical usage). If it is null, the returned array

   802   is itself dynamically allocated and should also be freed when it is

   803   no longer needed. Otherwise, the chunks array must be of at least

   804   n_elements in length. It is filled in with the pointers to the

   805   chunks.

   806 

   807   In either case, independent_calloc returns this pointer array, or

   808   null if the allocation failed.  If n_elements is zero and "chunks"

   809   is null, it returns a chunk representing an array with zero elements

   810   (which should be freed if not wanted).

   811 

   812   Each element must be individually freed when it is no longer

   813   needed. If you'd like to instead be able to free all at once, you

   814   should instead use regular calloc and assign pointers into this

   815   space to represent elements.  (In this case though, you cannot

   816   independently free elements.)

   817 

   818   independent_calloc simplifies and speeds up implementations of many

   819   kinds of pools.  It may also be useful when constructing large data

   820   structures that initially have a fixed number of fixed-sized nodes,

   821   but the number is not known at compile time, and some of the nodes

   822   may later need to be freed. For example:

   823 

   824   struct Node { int item; struct Node* next; };

   825 

   826   struct Node* build_list() {

   827     struct Node** pool;

   828     int n = read_number_of_nodes_needed();

   829     if (n <= 0) return 0;

   830     pool = (struct Node**)(independent_calloc(n, sizeof(struct Node), 0);

   831     if (pool == 0) die();

   832     // organize into a linked list...

   833     struct Node* first = pool[0];

   834     for (i = 0; i < n-1; ++i)

   835       pool[i]->next = pool[i+1];

   836     free(pool);     // Can now free the array (or not, if it is needed later)

   837     return first;

   838   }

   839 */

   840 void** dlindependent_calloc(size_t, size_t, void**);

   841 

   842 /*

   843   independent_comalloc(size_t n_elements, size_t sizes[], void* chunks[]);

   844 

   845   independent_comalloc allocates, all at once, a set of n_elements

   846   chunks with sizes indicated in the "sizes" array.    It returns

   847   an array of pointers to these elements, each of which can be

   848   independently freed, realloc'ed etc. The elements are guaranteed to

   849   be adjacently allocated (this is not guaranteed to occur with

   850   multiple callocs or mallocs), which may also improve cache locality

   851   in some applications.

   852 

   853   The "chunks" argument is optional (i.e., may be null). If it is null

   854   the returned array is itself dynamically allocated and should also

   855   be freed when it is no longer needed. Otherwise, the chunks array

   856   must be of at least n_elements in length. It is filled in with the

   857   pointers to the chunks.

   858 

   859   In either case, independent_comalloc returns this pointer array, or

   860   null if the allocation failed.  If n_elements is zero and chunks is

   861   null, it returns a chunk representing an array with zero elements

   862   (which should be freed if not wanted).

   863 

   864   Each element must be individually freed when it is no longer

   865   needed. If you'd like to instead be able to free all at once, you

   866   should instead use a single regular malloc, and assign pointers at

   867   particular offsets in the aggregate space. (In this case though, you

   868   cannot independently free elements.)

   869 

   870   independent_comallac differs from independent_calloc in that each

   871   element may have a different size, and also that it does not

   872   automatically clear elements.

   873 

   874   independent_comalloc can be used to speed up allocation in cases

   875   where several structs or objects must always be allocated at the

   876   same time.  For example:

   877 

   878   struct Head { ... }

   879   struct Foot { ... }

   880 

   881   void send_message(char* msg) {

   882     int msglen = strlen(msg);

   883     size_t sizes[3] = { sizeof(struct Head), msglen, sizeof(struct Foot) };

   884     void* chunks[3];

   885     if (independent_comalloc(3, sizes, chunks) == 0)

   886       die();

   887     struct Head* head = (struct Head*)(chunks[0]);

   888     char*        body = (char*)(chunks[1]);

   889     struct Foot* foot = (struct Foot*)(chunks[2]);

   890     // ...

   891   }

   892 

   893   In general though, independent_comalloc is worth using only for

   894   larger values of n_elements. For small values, you probably won't

   895   detect enough difference from series of malloc calls to bother.

   896 

   897   Overuse of independent_comalloc can increase overall memory usage,

   898   since it cannot reuse existing noncontiguous small chunks that

   899   might be available for some of the elements.

   900 */

   901 void** dlindependent_comalloc(size_t, size_t*, void**);

   902 

   903 

   904 /*

   905   pvalloc(size_t n);

   906   Equivalent to valloc(minimum-page-that-holds(n)), that is,

   907   round up n to nearest pagesize.

   908  */

   909 void*  dlpvalloc(size_t);

   910 

   911 /*

   912   malloc_trim(size_t pad);

   913 

   914   If possible, gives memory back to the system (via negative arguments

   915   to sbrk) if there is unused memory at the `high' end of the malloc

   916   pool or in unused MMAP segments. You can call this after freeing

   917   large blocks of memory to potentially reduce the system-level memory

   918   requirements of a program. However, it cannot guarantee to reduce

   919   memory. Under some allocation patterns, some large free blocks of

   920   memory will be locked between two used chunks, so they cannot be

   921   given back to the system.

   922 

   923   The `pad' argument to malloc_trim represents the amount of free

   924   trailing space to leave untrimmed. If this argument is zero, only

   925   the minimum amount of memory to maintain internal data structures

   926   will be left. Non-zero arguments can be supplied to maintain enough

   927   trailing space to service future expected allocations without having

   928   to re-obtain memory from the system.

   929 

   930   Malloc_trim returns 1 if it actually released any memory, else 0.

   931 */

   932 int  dlmalloc_trim(size_t);

   933 

   934 /*

   935   malloc_usable_size(void* p);

   936 

   937   Returns the number of bytes you can actually use in

   938   an allocated chunk, which may be more than you requested (although

   939   often not) due to alignment and minimum size constraints.

   940   You can use this many bytes without worrying about

   941   overwriting other allocated objects. This is not a particularly great

   942   programming practice. malloc_usable_size can be more useful in

   943   debugging and assertions, for example:

   944 

   945   p = malloc(n);

   946   assert(malloc_usable_size(p) >= 256);

   947 */

   948 size_t dlmalloc_usable_size(void*);

   949 

   950 /*

   951   malloc_stats();

   952   Prints on stderr the amount of space obtained from the system (both

   953   via sbrk and mmap), the maximum amount (which may be more than

   954   current if malloc_trim and/or munmap got called), and the current

   955   number of bytes allocated via malloc (or realloc, etc) but not yet

   956   freed. Note that this is the number of bytes allocated, not the

   957   number requested. It will be larger than the number requested

   958   because of alignment and bookkeeping overhead. Because it includes

   959   alignment wastage as being in use, this figure may be greater than

   960   zero even when no user-level chunks are allocated.

   961 

   962   The reported current and maximum system memory can be inaccurate if

   963   a program makes other calls to system memory allocation functions

   964   (normally sbrk) outside of malloc.

   965 

   966   malloc_stats prints only the most commonly interesting statistics.

   967   More information can be obtained by calling mallinfo.

   968 */

   969 void  dlmalloc_stats();

   970 

   971 #endif

   972 

   973 #if MSPACES

   974 

   975 /*

   976   mspace is an opaque type representing an independent

   977   region of space that supports mspace_malloc, etc.

   978 */

   979 typedef void* mspace;

   980 

   981 /*

   982   create_mspace creates and returns a new independent space with the

   983   given initial capacity, or, if 0, the default granularity size.  It

   984   returns null if there is no system memory available to create the

   985   space.  If argument locked is non-zero, the space uses a separate

   986   lock to control access. The capacity of the space will grow

   987   dynamically as needed to service mspace_malloc requests.  You can

   988   control the sizes of incremental increases of this space by

   989   compiling with a different DEFAULT_GRANULARITY or dynamically

   990   setting with mallopt(M_GRANULARITY, value).

   991 */

   992 mspace create_mspace(size_t capacity, int locked);

   993 

   994 /*

   995   destroy_mspace destroys the given space, and attempts to return all

   996   of its memory back to the system, returning the total number of

   997   bytes freed. After destruction, the results of access to all memory

   998   used by the space become undefined.

   999 */

  1000 size_t destroy_mspace(mspace msp);

  1001 

  1002 /*

  1003   create_mspace_with_base uses the memory supplied as the initial base

  1004   of a new mspace. Part (less than 128*sizeof(size_t) bytes) of this

  1005   space is used for bookkeeping, so the capacity must be at least this

  1006   large. (Otherwise 0 is returned.) When this initial space is

  1007   exhausted, additional memory will be obtained from the system.

  1008   Destroying this space will deallocate all additionally allocated

  1009   space (if possible) but not the initial base.

  1010 */

  1011 mspace create_mspace_with_base(void* base, size_t capacity, int locked);

  1012 

  1013 /*

  1014   mspace_malloc behaves as malloc, but operates within

  1015   the given space.

  1016 */

  1017 void* mspace_malloc(mspace msp, size_t bytes);

  1018 

  1019 /*

  1020   mspace_free behaves as free, but operates within

  1021   the given space.

  1022 

  1023   If compiled with FOOTERS==1, mspace_free is not actually needed.

  1024   free may be called instead of mspace_free because freed chunks from

  1025   any space are handled by their originating spaces.

  1026 */

  1027 void mspace_free(mspace msp, void* mem);

  1028 

  1029 /*

  1030   mspace_realloc behaves as realloc, but operates within

  1031   the given space.

  1032 

  1033   If compiled with FOOTERS==1, mspace_realloc is not actually

  1034   needed.  realloc may be called instead of mspace_realloc because

  1035   realloced chunks from any space are handled by their originating

  1036   spaces.

  1037 */

  1038 void* mspace_realloc(mspace msp, void* mem, size_t newsize);

  1039 

  1040 /*

  1041   mspace_calloc behaves as calloc, but operates within

  1042   the given space.

  1043 */

  1044 void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size);

  1045 

  1046 /*

  1047   mspace_memalign behaves as memalign, but operates within

  1048   the given space.

  1049 */

  1050 void* mspace_memalign(mspace msp, size_t alignment, size_t bytes);

  1051 

  1052 /*

  1053   mspace_independent_calloc behaves as independent_calloc, but

  1054   operates within the given space.

  1055 */

  1056 void** mspace_independent_calloc(mspace msp, size_t n_elements,

  1057                                  size_t elem_size, void* chunks[]);

  1058 

  1059 /*

  1060   mspace_independent_comalloc behaves as independent_comalloc, but

  1061   operates within the given space.

  1062 */

  1063 void** mspace_independent_comalloc(mspace msp, size_t n_elements,

  1064                                    size_t sizes[], void* chunks[]);

  1065 

  1066 /*

  1067   mspace_footprint() returns the number of bytes obtained from the

  1068   system for this space.

  1069 */

  1070 size_t mspace_footprint(mspace msp);

  1071 

  1072 

  1073 #if !NO_MALLINFO

  1074 /*

  1075   mspace_mallinfo behaves as mallinfo, but reports properties of

  1076   the given space.

  1077 */

  1078 struct mallinfo mspace_mallinfo(mspace msp);

  1079 #endif

  1080 

  1081 /*

  1082   mspace_malloc_stats behaves as malloc_stats, but reports

  1083   properties of the given space.

  1084 */

  1085 void mspace_malloc_stats(mspace msp);

  1086 

  1087 /*

  1088   mspace_trim behaves as malloc_trim, but

  1089   operates within the given space.

  1090 */

  1091 int mspace_trim(mspace msp, size_t pad);

  1092 

  1093 /*

  1094   An alias for mallopt.

  1095 */

  1096 int mspace_mallopt(int, int);

  1097 

  1098 #endif

  1099 

  1100 /*

  1101   ========================================================================

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

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

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

  1105   ========================================================================

  1106 */

  1107 

  1108 /* #include "malloc.h" */

  1109 

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

  1111 

  1112 #ifdef WIN32

  1113 #pragma warning( disable : 4146 ) /* no "unsigned" warnings */

  1114 #endif

  1115 

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

  1117 

  1118 #ifndef LACKS_ERRNO_H

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

  1120 #endif

  1121 #if FOOTERS

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

  1123 #endif

  1124 #ifndef LACKS_STDLIB_H

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

  1126 #endif

  1127 #ifdef DEBUG

  1128 #if ABORT_ON_ASSERT_FAILURE

  1129 #define assert(x) if(!(x)) ABORT

  1130 #else

  1131 #include <assert.h>

  1132 #endif

  1133 #else

  1134 #define assert(x)