src/stdlib/SDL_malloc.c
author Ryan C. Gordon <icculus@icculus.org>
Thu, 21 Apr 2016 03:16:44 -0400
changeset 11729 d1ce8396c356
parent 11618 bbbc6db5a2b3
child 11811 5d94cb6b24d3
permissions -rw-r--r--
Initial shot at a renderer target for Apple's Metal API.

This isn't complete, but is enough to run testsprite2. It's currently
Mac-only; with a little work to figure out how to properly glue in a Metal
layer to a UIView, this will likely work on iOS, too.

This is only wired up to the configure script right now, and disabled by
default. CMake and Xcode still need their bits filled in as appropriate.
slouken@1330
     1
/*
slouken@5535
     2
  Simple DirectMedia Layer
slouken@10737
     3
  Copyright (C) 1997-2017 Sam Lantinga <slouken@libsdl.org>
slouken@5535
     4
slouken@5535
     5
  This software is provided 'as-is', without any express or implied
slouken@5535
     6
  warranty.  In no event will the authors be held liable for any damages
slouken@5535
     7
  arising from the use of this software.
slouken@5535
     8
slouken@5535
     9
  Permission is granted to anyone to use this software for any purpose,
slouken@5535
    10
  including commercial applications, and to alter it and redistribute it
slouken@5535
    11
  freely, subject to the following restrictions:
slouken@5535
    12
slouken@5535
    13
  1. The origin of this software must not be misrepresented; you must not
slouken@5535
    14
     claim that you wrote the original software. If you use this software
slouken@5535
    15
     in a product, an acknowledgment in the product documentation would be
slouken@5535
    16
     appreciated but is not required.
slouken@5535
    17
  2. Altered source versions must be plainly marked as such, and must not be
slouken@5535
    18
     misrepresented as being the original software.
slouken@5535
    19
  3. This notice may not be removed or altered from any source distribution.
slouken@1330
    20
*/
icculus@9306
    21
icculus@9306
    22
#if defined(__clang_analyzer__) && !defined(SDL_DISABLE_ANALYZE_MACROS)
icculus@9306
    23
#define SDL_DISABLE_ANALYZE_MACROS 1
icculus@9306
    24
#endif
icculus@9306
    25
icculus@8093
    26
#include "../SDL_internal.h"
slouken@1330
    27
slouken@1330
    28
/* This file contains portable memory management functions for SDL */
slouken@1354
    29
#include "SDL_stdinc.h"
slouken@11610
    30
#include "SDL_atomic.h"
slouken@11610
    31
#include "SDL_error.h"
slouken@11610
    32
slouken@11610
    33
#ifndef HAVE_MALLOC
slouken@1465
    34
#define LACKS_SYS_TYPES_H
slouken@1330
    35
#define LACKS_STDIO_H
slouken@1330
    36
#define LACKS_STRINGS_H
slouken@1330
    37
#define LACKS_STRING_H
slouken@1330
    38
#define LACKS_STDLIB_H
slouken@1330
    39
#define ABORT
slouken@8758
    40
#define USE_LOCKS 1
slouken@11610
    41
#define USE_DL_PREFIX
slouken@1330
    42
slouken@1330
    43
/*
slouken@1330
    44
  This is a version (aka dlmalloc) of malloc/free/realloc written by
slouken@1330
    45
  Doug Lea and released to the public domain, as explained at
slouken@1330
    46
  http://creativecommons.org/licenses/publicdomain.  Send questions,
slouken@1330
    47
  comments, complaints, performance data, etc to dl@cs.oswego.edu
slouken@1330
    48
slouken@1330
    49
* Version 2.8.3 Thu Sep 22 11:16:15 2005  Doug Lea  (dl at gee)
slouken@1330
    50
slouken@1330
    51
   Note: There may be an updated version of this malloc obtainable at
slouken@1330
    52
           ftp://gee.cs.oswego.edu/pub/misc/malloc.c
slouken@1330
    53
         Check before installing!
slouken@1330
    54
slouken@1330
    55
* Quickstart
slouken@1330
    56
slouken@1330
    57
  This library is all in one file to simplify the most common usage:
slouken@1330
    58
  ftp it, compile it (-O3), and link it into another program. All of
slouken@1330
    59
  the compile-time options default to reasonable values for use on
slouken@1330
    60
  most platforms.  You might later want to step through various
slouken@1330
    61
  compile-time and dynamic tuning options.
slouken@1330
    62
slouken@1330
    63
  For convenience, an include file for code using this malloc is at:
slouken@1330
    64
     ftp://gee.cs.oswego.edu/pub/misc/malloc-2.8.3.h
slouken@1330
    65
  You don't really need this .h file unless you call functions not
slouken@1330
    66
  defined in your system include files.  The .h file contains only the
slouken@1330
    67
  excerpts from this file needed for using this malloc on ANSI C/C++
slouken@1330
    68
  systems, so long as you haven't changed compile-time options about
slouken@1330
    69
  naming and tuning parameters.  If you do, then you can create your
slouken@1330
    70
  own malloc.h that does include all settings by cutting at the point
slouken@1330
    71
  indicated below. Note that you may already by default be using a C
slouken@1330
    72
  library containing a malloc that is based on some version of this
slouken@1330
    73
  malloc (for example in linux). You might still want to use the one
slouken@1330
    74
  in this file to customize settings or to avoid overheads associated
slouken@1330
    75
  with library versions.
slouken@1330
    76
slouken@1330
    77
* Vital statistics:
slouken@1330
    78
slouken@1330
    79
  Supported pointer/size_t representation:       4 or 8 bytes
slouken@1330
    80
       size_t MUST be an unsigned type of the same width as
slouken@1330
    81
       pointers. (If you are using an ancient system that declares
slouken@1330
    82
       size_t as a signed type, or need it to be a different width
slouken@1330
    83
       than pointers, you can use a previous release of this malloc
slouken@1330
    84
       (e.g. 2.7.2) supporting these.)
slouken@1330
    85
slouken@1330
    86
  Alignment:                                     8 bytes (default)
slouken@1330
    87
       This suffices for nearly all current machines and C compilers.
slouken@1330
    88
       However, you can define MALLOC_ALIGNMENT to be wider than this
slouken@1330
    89
       if necessary (up to 128bytes), at the expense of using more space.
slouken@1330
    90
slouken@1330
    91
  Minimum overhead per allocated chunk:   4 or  8 bytes (if 4byte sizes)
slouken@1330
    92
                                          8 or 16 bytes (if 8byte sizes)
slouken@1330
    93
       Each malloced chunk has a hidden word of overhead holding size
slouken@1330
    94
       and status information, and additional cross-check word
slouken@1330
    95
       if FOOTERS is defined.
slouken@1330
    96
slouken@1330
    97
  Minimum allocated size: 4-byte ptrs:  16 bytes    (including overhead)
slouken@1330
    98
                          8-byte ptrs:  32 bytes    (including overhead)
slouken@1330
    99
slouken@1330
   100
       Even a request for zero bytes (i.e., malloc(0)) returns a
slouken@1330
   101
       pointer to something of the minimum allocatable size.
slouken@1330
   102
       The maximum overhead wastage (i.e., number of extra bytes
slouken@1330
   103
       allocated than were requested in malloc) is less than or equal
slouken@1330
   104
       to the minimum size, except for requests >= mmap_threshold that
slouken@1330
   105
       are serviced via mmap(), where the worst case wastage is about
slouken@1330
   106
       32 bytes plus the remainder from a system page (the minimal
slouken@1330
   107
       mmap unit); typically 4096 or 8192 bytes.
slouken@1330
   108
slouken@1330
   109
  Security: static-safe; optionally more or less
slouken@1330
   110
       The "security" of malloc refers to the ability of malicious
slouken@1330
   111
       code to accentuate the effects of errors (for example, freeing
slouken@1330
   112
       space that is not currently malloc'ed or overwriting past the
slouken@1330
   113
       ends of chunks) in code that calls malloc.  This malloc
slouken@1330
   114
       guarantees not to modify any memory locations below the base of
slouken@1330
   115
       heap, i.e., static variables, even in the presence of usage
slouken@1330
   116
       errors.  The routines additionally detect most improper frees
slouken@1330
   117
       and reallocs.  All this holds as long as the static bookkeeping
slouken@1330
   118
       for malloc itself is not corrupted by some other means.  This
slouken@1330
   119
       is only one aspect of security -- these checks do not, and
slouken@1330
   120
       cannot, detect all possible programming errors.
slouken@1330
   121
slouken@1330
   122
       If FOOTERS is defined nonzero, then each allocated chunk
slouken@1330
   123
       carries an additional check word to verify that it was malloced
slouken@1330
   124
       from its space.  These check words are the same within each
slouken@1330
   125
       execution of a program using malloc, but differ across
slouken@1330
   126
       executions, so externally crafted fake chunks cannot be
slouken@1330
   127
       freed. This improves security by rejecting frees/reallocs that
slouken@1330
   128
       could corrupt heap memory, in addition to the checks preventing
slouken@1330
   129
       writes to statics that are always on.  This may further improve
slouken@1330
   130
       security at the expense of time and space overhead.  (Note that
slouken@1330
   131
       FOOTERS may also be worth using with MSPACES.)
slouken@1330
   132
slouken@1330
   133
       By default detected errors cause the program to abort (calling
slouken@1330
   134
       "abort()"). You can override this to instead proceed past
slouken@1330
   135
       errors by defining PROCEED_ON_ERROR.  In this case, a bad free
slouken@1330
   136
       has no effect, and a malloc that encounters a bad address
slouken@1330
   137
       caused by user overwrites will ignore the bad address by
slouken@1330
   138
       dropping pointers and indices to all known memory. This may
slouken@1330
   139
       be appropriate for programs that should continue if at all
slouken@1330
   140
       possible in the face of programming errors, although they may
slouken@1330
   141
       run out of memory because dropped memory is never reclaimed.
slouken@1330
   142
slouken@1330
   143
       If you don't like either of these options, you can define
slouken@1330
   144
       CORRUPTION_ERROR_ACTION and USAGE_ERROR_ACTION to do anything
slouken@1330
   145
       else. And if if you are sure that your program using malloc has
slouken@1330
   146
       no errors or vulnerabilities, you can define INSECURE to 1,
slouken@1330
   147
       which might (or might not) provide a small performance improvement.
slouken@1330
   148
slouken@1330
   149
  Thread-safety: NOT thread-safe unless USE_LOCKS defined
slouken@1330
   150
       When USE_LOCKS is defined, each public call to malloc, free,
slouken@1330
   151
       etc is surrounded with either a pthread mutex or a win32
slouken@1330
   152
       spinlock (depending on WIN32). This is not especially fast, and
slouken@1330
   153
       can be a major bottleneck.  It is designed only to provide
slouken@1330
   154
       minimal protection in concurrent environments, and to provide a
slouken@1330
   155
       basis for extensions.  If you are using malloc in a concurrent
slouken@1330
   156
       program, consider instead using ptmalloc, which is derived from
slouken@1330
   157
       a version of this malloc. (See http://www.malloc.de).
slouken@1330
   158
slouken@1330
   159
  System requirements: Any combination of MORECORE and/or MMAP/MUNMAP
slouken@1330
   160
       This malloc can use unix sbrk or any emulation (invoked using
slouken@1330
   161
       the CALL_MORECORE macro) and/or mmap/munmap or any emulation
slouken@1330
   162
       (invoked using CALL_MMAP/CALL_MUNMAP) to get and release system
slouken@1330
   163
       memory.  On most unix systems, it tends to work best if both
slouken@1330
   164
       MORECORE and MMAP are enabled.  On Win32, it uses emulations
slouken@1330
   165
       based on VirtualAlloc. It also uses common C library functions
slouken@1330
   166
       like memset.
slouken@1330
   167
slouken@1330
   168
  Compliance: I believe it is compliant with the Single Unix Specification
slouken@1330
   169
       (See http://www.unix.org). Also SVID/XPG, ANSI C, and probably
slouken@1330
   170
       others as well.
slouken@1330
   171
slouken@1330
   172
* Overview of algorithms
slouken@1330
   173
slouken@1330
   174
  This is not the fastest, most space-conserving, most portable, or
slouken@1330
   175
  most tunable malloc ever written. However it is among the fastest
slouken@1330
   176
  while also being among the most space-conserving, portable and
slouken@1330
   177
  tunable.  Consistent balance across these factors results in a good
slouken@1330
   178
  general-purpose allocator for malloc-intensive programs.
slouken@1330
   179
slouken@1330
   180
  In most ways, this malloc is a best-fit allocator. Generally, it
slouken@1330
   181
  chooses the best-fitting existing chunk for a request, with ties
slouken@1330
   182
  broken in approximately least-recently-used order. (This strategy
slouken@1330
   183
  normally maintains low fragmentation.) However, for requests less
slouken@1330
   184
  than 256bytes, it deviates from best-fit when there is not an
slouken@1330
   185
  exactly fitting available chunk by preferring to use space adjacent
slouken@1330
   186
  to that used for the previous small request, as well as by breaking
slouken@1330
   187
  ties in approximately most-recently-used order. (These enhance
slouken@1330
   188
  locality of series of small allocations.)  And for very large requests
slouken@1330
   189
  (>= 256Kb by default), it relies on system memory mapping
slouken@1330
   190
  facilities, if supported.  (This helps avoid carrying around and
slouken@1330
   191
  possibly fragmenting memory used only for large chunks.)
slouken@1330
   192
slouken@1330
   193
  All operations (except malloc_stats and mallinfo) have execution
slouken@1330
   194
  times that are bounded by a constant factor of the number of bits in
slouken@1330
   195
  a size_t, not counting any clearing in calloc or copying in realloc,
slouken@1330
   196
  or actions surrounding MORECORE and MMAP that have times
slouken@1330
   197
  proportional to the number of non-contiguous regions returned by
slouken@1330
   198
  system allocation routines, which is often just 1.
slouken@1330
   199
slouken@1330
   200
  The implementation is not very modular and seriously overuses
slouken@1330
   201
  macros. Perhaps someday all C compilers will do as good a job
slouken@1330
   202
  inlining modular code as can now be done by brute-force expansion,
slouken@1330
   203
  but now, enough of them seem not to.
slouken@1330
   204
slouken@1330
   205
  Some compilers issue a lot of warnings about code that is
slouken@1330
   206
  dead/unreachable only on some platforms, and also about intentional
slouken@1330
   207
  uses of negation on unsigned types. All known cases of each can be
slouken@1330
   208
  ignored.
slouken@1330
   209
slouken@1330
   210
  For a longer but out of date high-level description, see
slouken@1330
   211
     http://gee.cs.oswego.edu/dl/html/malloc.html
slouken@1330
   212
slouken@1330
   213
* MSPACES
slouken@1330
   214
  If MSPACES is defined, then in addition to malloc, free, etc.,
slouken@1330
   215
  this file also defines mspace_malloc, mspace_free, etc. These
slouken@1330
   216
  are versions of malloc routines that take an "mspace" argument
slouken@1330
   217
  obtained using create_mspace, to control all internal bookkeeping.
slouken@1330
   218
  If ONLY_MSPACES is defined, only these versions are compiled.
slouken@1330
   219
  So if you would like to use this allocator for only some allocations,
slouken@1330
   220
  and your system malloc for others, you can compile with
slouken@1330
   221
  ONLY_MSPACES and then do something like...
slouken@1330
   222
    static mspace mymspace = create_mspace(0,0); // for example
slouken@1330
   223
    #define mymalloc(bytes)  mspace_malloc(mymspace, bytes)
slouken@1330
   224
slouken@1330
   225
  (Note: If you only need one instance of an mspace, you can instead
slouken@1330
   226
  use "USE_DL_PREFIX" to relabel the global malloc.)
slouken@1330
   227
slouken@1330
   228
  You can similarly create thread-local allocators by storing
slouken@1330
   229
  mspaces as thread-locals. For example:
slouken@1330
   230
    static __thread mspace tlms = 0;
slouken@1330
   231
    void*  tlmalloc(size_t bytes) {
slouken@1330
   232
      if (tlms == 0) tlms = create_mspace(0, 0);
slouken@1330
   233
      return mspace_malloc(tlms, bytes);
slouken@1330
   234
    }
slouken@1330
   235
    void  tlfree(void* mem) { mspace_free(tlms, mem); }
slouken@1330
   236
slouken@1330
   237
  Unless FOOTERS is defined, each mspace is completely independent.
slouken@1330
   238
  You cannot allocate from one and free to another (although
slouken@1330
   239
  conformance is only weakly checked, so usage errors are not always
slouken@1330
   240
  caught). If FOOTERS is defined, then each chunk carries around a tag
slouken@1330
   241
  indicating its originating mspace, and frees are directed to their
slouken@1330
   242
  originating spaces.
slouken@1330
   243
slouken@1330
   244
 -------------------------  Compile-time options ---------------------------
slouken@1330
   245
slouken@1330
   246
Be careful in setting #define values for numerical constants of type
slouken@1330
   247
size_t. On some systems, literal values are not automatically extended
slouken@1330
   248
to size_t precision unless they are explicitly casted.
slouken@1330
   249
slouken@1330
   250
WIN32                    default: defined if _WIN32 defined
slouken@1330
   251
  Defining WIN32 sets up defaults for MS environment and compilers.
slouken@1330
   252
  Otherwise defaults are for unix.
slouken@1330
   253
slouken@1330
   254
MALLOC_ALIGNMENT         default: (size_t)8
slouken@1330
   255
  Controls the minimum alignment for malloc'ed chunks.  It must be a
slouken@1330
   256
  power of two and at least 8, even on machines for which smaller
slouken@1330
   257
  alignments would suffice. It may be defined as larger than this
slouken@1330
   258
  though. Note however that code and data structures are optimized for
slouken@1330
   259
  the case of 8-byte alignment.
slouken@1330
   260
slouken@1330
   261
MSPACES                  default: 0 (false)
slouken@1330
   262
  If true, compile in support for independent allocation spaces.
slouken@1330
   263
  This is only supported if HAVE_MMAP is true.
slouken@1330
   264
slouken@1330
   265
ONLY_MSPACES             default: 0 (false)
slouken@1330
   266
  If true, only compile in mspace versions, not regular versions.
slouken@1330
   267
slouken@1330
   268
USE_LOCKS                default: 0 (false)
slouken@1330
   269
  Causes each call to each public routine to be surrounded with
slouken@1330
   270
  pthread or WIN32 mutex lock/unlock. (If set true, this can be
slouken@1330
   271
  overridden on a per-mspace basis for mspace versions.)
slouken@1330
   272
slouken@1330
   273
FOOTERS                  default: 0
slouken@1330
   274
  If true, provide extra checking and dispatching by placing
slouken@1330
   275
  information in the footers of allocated chunks. This adds
slouken@1330
   276
  space and time overhead.
slouken@1330
   277
slouken@1330
   278
INSECURE                 default: 0
slouken@1330
   279
  If true, omit checks for usage errors and heap space overwrites.
slouken@1330
   280
slouken@1330
   281
USE_DL_PREFIX            default: NOT defined
slouken@1330
   282
  Causes compiler to prefix all public routines with the string 'dl'.
slouken@1330
   283
  This can be useful when you only want to use this malloc in one part
slouken@1330
   284
  of a program, using your regular system malloc elsewhere.
slouken@1330
   285
slouken@1330
   286
ABORT                    default: defined as abort()
slouken@1330
   287
  Defines how to abort on failed checks.  On most systems, a failed
slouken@1330
   288
  check cannot die with an "assert" or even print an informative
slouken@1330
   289
  message, because the underlying print routines in turn call malloc,
slouken@1330
   290
  which will fail again.  Generally, the best policy is to simply call
slouken@1330
   291
  abort(). It's not very useful to do more than this because many
slouken@1330
   292
  errors due to overwriting will show up as address faults (null, odd
slouken@1330
   293
  addresses etc) rather than malloc-triggered checks, so will also
slouken@1330
   294
  abort.  Also, most compilers know that abort() does not return, so
slouken@1330
   295
  can better optimize code conditionally calling it.
slouken@1330
   296
slouken@1330
   297
PROCEED_ON_ERROR           default: defined as 0 (false)
slouken@1330
   298
  Controls whether detected bad addresses cause them to bypassed
slouken@1330
   299
  rather than aborting. If set, detected bad arguments to free and
slouken@1330
   300
  realloc are ignored. And all bookkeeping information is zeroed out
slouken@1330
   301
  upon a detected overwrite of freed heap space, thus losing the
slouken@1330
   302
  ability to ever return it from malloc again, but enabling the
slouken@1330
   303
  application to proceed. If PROCEED_ON_ERROR is defined, the
slouken@1330
   304
  static variable malloc_corruption_error_count is compiled in
slouken@1330
   305
  and can be examined to see if errors have occurred. This option
slouken@1330
   306
  generates slower code than the default abort policy.
slouken@1330
   307
slouken@1330
   308
DEBUG                    default: NOT defined
slouken@1330
   309
  The DEBUG setting is mainly intended for people trying to modify
slouken@1330
   310
  this code or diagnose problems when porting to new platforms.
slouken@1330
   311
  However, it may also be able to better isolate user errors than just
slouken@1330
   312
  using runtime checks.  The assertions in the check routines spell
slouken@1330
   313
  out in more detail the assumptions and invariants underlying the
slouken@1330
   314
  algorithms.  The checking is fairly extensive, and will slow down
slouken@1330
   315
  execution noticeably. Calling malloc_stats or mallinfo with DEBUG
slouken@1330
   316
  set will attempt to check every non-mmapped allocated and free chunk
slouken@1330
   317
  in the course of computing the summaries.
slouken@1330
   318
slouken@1330
   319
ABORT_ON_ASSERT_FAILURE   default: defined as 1 (true)
slouken@1330
   320
  Debugging assertion failures can be nearly impossible if your
slouken@1330
   321
  version of the assert macro causes malloc to be called, which will
slouken@1330
   322
  lead to a cascade of further failures, blowing the runtime stack.
slouken@1330
   323
  ABORT_ON_ASSERT_FAILURE cause assertions failures to call abort(),
slouken@1330
   324
  which will usually make debugging easier.
slouken@1330
   325
slouken@1330
   326
MALLOC_FAILURE_ACTION     default: sets errno to ENOMEM, or no-op on win32
slouken@1330
   327
  The action to take before "return 0" when malloc fails to be able to
slouken@1330
   328
  return memory because there is none available.
slouken@1330
   329
slouken@1330
   330
HAVE_MORECORE             default: 1 (true) unless win32 or ONLY_MSPACES
slouken@1330
   331
  True if this system supports sbrk or an emulation of it.
slouken@1330
   332
slouken@1330
   333
MORECORE                  default: sbrk
slouken@1330
   334
  The name of the sbrk-style system routine to call to obtain more
slouken@1330
   335
  memory.  See below for guidance on writing custom MORECORE
slouken@1330
   336
  functions. The type of the argument to sbrk/MORECORE varies across
slouken@1330
   337
  systems.  It cannot be size_t, because it supports negative
slouken@1330
   338
  arguments, so it is normally the signed type of the same width as
slouken@1330
   339
  size_t (sometimes declared as "intptr_t").  It doesn't much matter
slouken@1330
   340
  though. Internally, we only call it with arguments less than half
slouken@1330
   341
  the max value of a size_t, which should work across all reasonable
slouken@1330
   342
  possibilities, although sometimes generating compiler warnings.  See
slouken@1330
   343
  near the end of this file for guidelines for creating a custom
slouken@1330
   344
  version of MORECORE.
slouken@1330
   345
slouken@1330
   346
MORECORE_CONTIGUOUS       default: 1 (true)
slouken@1330
   347
  If true, take advantage of fact that consecutive calls to MORECORE
slouken@1330
   348
  with positive arguments always return contiguous increasing
slouken@1330
   349
  addresses.  This is true of unix sbrk. It does not hurt too much to
slouken@1330
   350
  set it true anyway, since malloc copes with non-contiguities.
slouken@1330
   351
  Setting it false when definitely non-contiguous saves time
slouken@1330
   352
  and possibly wasted space it would take to discover this though.
slouken@1330
   353
slouken@1330
   354
MORECORE_CANNOT_TRIM      default: NOT defined
slouken@1330
   355
  True if MORECORE cannot release space back to the system when given
slouken@1330
   356
  negative arguments. This is generally necessary only if you are
slouken@1330
   357
  using a hand-crafted MORECORE function that cannot handle negative
slouken@1330
   358
  arguments.
slouken@1330
   359
slouken@1330
   360
HAVE_MMAP                 default: 1 (true)
slouken@1330
   361
  True if this system supports mmap or an emulation of it.  If so, and
slouken@1330
   362
  HAVE_MORECORE is not true, MMAP is used for all system
slouken@1330
   363
  allocation. If set and HAVE_MORECORE is true as well, MMAP is
slouken@1330
   364
  primarily used to directly allocate very large blocks. It is also
slouken@1330
   365
  used as a backup strategy in cases where MORECORE fails to provide
slouken@1330
   366
  space from system. Note: A single call to MUNMAP is assumed to be
slouken@1330
   367
  able to unmap memory that may have be allocated using multiple calls
slouken@1330
   368
  to MMAP, so long as they are adjacent.
slouken@1330
   369
slouken@1330
   370
HAVE_MREMAP               default: 1 on linux, else 0
slouken@1330
   371
  If true realloc() uses mremap() to re-allocate large blocks and
slouken@1330
   372
  extend or shrink allocation spaces.
slouken@1330
   373
slouken@1330
   374
MMAP_CLEARS               default: 1 on unix
slouken@1330
   375
  True if mmap clears memory so calloc doesn't need to. This is true
slouken@1330
   376
  for standard unix mmap using /dev/zero.
slouken@1330
   377
slouken@1330
   378
USE_BUILTIN_FFS            default: 0 (i.e., not used)
slouken@1330
   379
  Causes malloc to use the builtin ffs() function to compute indices.
slouken@1330
   380
  Some compilers may recognize and intrinsify ffs to be faster than the
slouken@1330
   381
  supplied C version. Also, the case of x86 using gcc is special-cased
slouken@1330
   382
  to an asm instruction, so is already as fast as it can be, and so
slouken@1330
   383
  this setting has no effect. (On most x86s, the asm version is only
slouken@1330
   384
  slightly faster than the C version.)
slouken@1330
   385
slouken@1330
   386
malloc_getpagesize         default: derive from system includes, or 4096.
slouken@1330
   387
  The system page size. To the extent possible, this malloc manages
slouken@1330
   388
  memory from the system in page-size units.  This may be (and
slouken@1330
   389
  usually is) a function rather than a constant. This is ignored
slouken@1330
   390
  if WIN32, where page size is determined using getSystemInfo during
slouken@1330
   391
  initialization.
slouken@1330
   392
slouken@1330
   393
USE_DEV_RANDOM             default: 0 (i.e., not used)
slouken@1330
   394
  Causes malloc to use /dev/random to initialize secure magic seed for
slouken@1330
   395
  stamping footers. Otherwise, the current time is used.
slouken@1330
   396
slouken@1330
   397
NO_MALLINFO                default: 0
slouken@1330
   398
  If defined, don't compile "mallinfo". This can be a simple way
slouken@1330
   399
  of dealing with mismatches between system declarations and
slouken@1330
   400
  those in this file.
slouken@1330
   401
slouken@1330
   402
MALLINFO_FIELD_TYPE        default: size_t
slouken@1330
   403
  The type of the fields in the mallinfo struct. This was originally
slouken@1330
   404
  defined as "int" in SVID etc, but is more usefully defined as
slouken@1330
   405
  size_t. The value is used only if  HAVE_USR_INCLUDE_MALLOC_H is not set
slouken@1330
   406
slouken@1330
   407
REALLOC_ZERO_BYTES_FREES    default: not defined
slouken@7191
   408
  This should be set if a call to realloc with zero bytes should
slouken@7191
   409
  be the same as a call to free. Some people think it should. Otherwise,
slouken@7191
   410
  since this malloc returns a unique pointer for malloc(0), so does
slouken@1330
   411
  realloc(p, 0).
slouken@1330
   412
slouken@1330
   413
LACKS_UNISTD_H, LACKS_FCNTL_H, LACKS_SYS_PARAM_H, LACKS_SYS_MMAN_H
slouken@1330
   414
LACKS_STRINGS_H, LACKS_STRING_H, LACKS_SYS_TYPES_H,  LACKS_ERRNO_H
slouken@1330
   415
LACKS_STDLIB_H                default: NOT defined unless on WIN32
slouken@1330
   416
  Define these if your system does not have these header files.
slouken@1330
   417
  You might need to manually insert some of the declarations they provide.
slouken@1330
   418
slouken@1330
   419
DEFAULT_GRANULARITY        default: page size if MORECORE_CONTIGUOUS,
slouken@1330
   420
                                system_info.dwAllocationGranularity in WIN32,
slouken@1330
   421
                                otherwise 64K.
slouken@1330
   422
      Also settable using mallopt(M_GRANULARITY, x)
slouken@1330
   423
  The unit for allocating and deallocating memory from the system.  On
slouken@1330
   424
  most systems with contiguous MORECORE, there is no reason to
slouken@1330
   425
  make this more than a page. However, systems with MMAP tend to
slouken@1330
   426
  either require or encourage larger granularities.  You can increase
slouken@1330
   427
  this value to prevent system allocation functions to be called so
slouken@1330
   428
  often, especially if they are slow.  The value must be at least one
slouken@1330
   429
  page and must be a power of two.  Setting to 0 causes initialization
slouken@1330
   430
  to either page size or win32 region size.  (Note: In previous
slouken@1330
   431
  versions of malloc, the equivalent of this option was called
slouken@1330
   432
  "TOP_PAD")
slouken@1330
   433
slouken@1330
   434
DEFAULT_TRIM_THRESHOLD    default: 2MB
slouken@1330
   435
      Also settable using mallopt(M_TRIM_THRESHOLD, x)
slouken@1330
   436
  The maximum amount of unused top-most memory to keep before
slouken@1330
   437
  releasing via malloc_trim in free().  Automatic trimming is mainly
slouken@1330
   438
  useful in long-lived programs using contiguous MORECORE.  Because
slouken@1330
   439
  trimming via sbrk can be slow on some systems, and can sometimes be
slouken@1330
   440
  wasteful (in cases where programs immediately afterward allocate
slouken@1330
   441
  more large chunks) the value should be high enough so that your
slouken@1330
   442
  overall system performance would improve by releasing this much
slouken@1330
   443
  memory.  As a rough guide, you might set to a value close to the
slouken@1330
   444
  average size of a process (program) running on your system.
slouken@1330
   445
  Releasing this much memory would allow such a process to run in
slouken@1330
   446
  memory.  Generally, it is worth tuning trim thresholds when a
slouken@1330
   447
  program undergoes phases where several large chunks are allocated
slouken@1330
   448
  and released in ways that can reuse each other's storage, perhaps
slouken@1330
   449
  mixed with phases where there are no such chunks at all. The trim
slouken@1330
   450
  value must be greater than page size to have any useful effect.  To
slouken@1330
   451
  disable trimming completely, you can set to MAX_SIZE_T. Note that the trick
slouken@1330
   452
  some people use of mallocing a huge space and then freeing it at
slouken@1330
   453
  program startup, in an attempt to reserve system memory, doesn't
slouken@1330
   454
  have the intended effect under automatic trimming, since that memory
slouken@1330
   455
  will immediately be returned to the system.
slouken@1330
   456
slouken@1330
   457
DEFAULT_MMAP_THRESHOLD       default: 256K
slouken@1330
   458
      Also settable using mallopt(M_MMAP_THRESHOLD, x)
slouken@1330
   459
  The request size threshold for using MMAP to directly service a
slouken@1330
   460
  request. Requests of at least this size that cannot be allocated
slouken@1330
   461
  using already-existing space will be serviced via mmap.  (If enough
slouken@1330
   462
  normal freed space already exists it is used instead.)  Using mmap
slouken@1330
   463
  segregates relatively large chunks of memory so that they can be
slouken@1330
   464
  individually obtained and released from the host system. A request
slouken@1330
   465
  serviced through mmap is never reused by any other request (at least
slouken@1330
   466
  not directly; the system may just so happen to remap successive
slouken@1330
   467
  requests to the same locations).  Segregating space in this way has
slouken@1330
   468
  the benefits that: Mmapped space can always be individually released
slouken@1330
   469
  back to the system, which helps keep the system level memory demands
slouken@1330
   470
  of a long-lived program low.  Also, mapped memory doesn't become
slouken@1330
   471
  `locked' between other chunks, as can happen with normally allocated
slouken@1330
   472
  chunks, which means that even trimming via malloc_trim would not
slouken@1330
   473
  release them.  However, it has the disadvantage that the space
slouken@1330
   474
  cannot be reclaimed, consolidated, and then used to service later
slouken@1330
   475
  requests, as happens with normal chunks.  The advantages of mmap
slouken@1330
   476
  nearly always outweigh disadvantages for "large" chunks, but the
slouken@1330
   477
  value of "large" may vary across systems.  The default is an
slouken@1330
   478
  empirically derived value that works well in most systems. You can
slouken@1330
   479
  disable mmap by setting to MAX_SIZE_T.
slouken@1330
   480
slouken@1330
   481
*/
slouken@1330
   482
slouken@1330
   483
#ifndef WIN32
slouken@1330
   484
#ifdef _WIN32
slouken@1330
   485
#define WIN32 1
slouken@1895
   486
#endif /* _WIN32 */
slouken@1895
   487
#endif /* WIN32 */
slouken@1330
   488
#ifdef WIN32
slouken@1433
   489
#define WIN32_LEAN_AND_MEAN
slouken@1433
   490
#include <windows.h>
slouken@1330
   491
#define HAVE_MMAP 1
slouken@1330
   492
#define HAVE_MORECORE 0
slouken@1330
   493
#define LACKS_UNISTD_H
slouken@1330
   494
#define LACKS_SYS_PARAM_H
slouken@1330
   495
#define LACKS_SYS_MMAN_H
slouken@1330
   496
#define LACKS_STRING_H
slouken@1330
   497
#define LACKS_STRINGS_H
slouken@1330
   498
#define LACKS_SYS_TYPES_H
slouken@1330
   499
#define LACKS_ERRNO_H
slouken@1895
   500
#define LACKS_FCNTL_H
slouken@1330
   501
#define MALLOC_FAILURE_ACTION
slouken@1895
   502
#define MMAP_CLEARS 0           /* WINCE and some others apparently don't clear */
slouken@1895
   503
#endif /* WIN32 */
slouken@1330
   504
slouken@1330
   505
#if defined(DARWIN) || defined(_DARWIN)
slouken@1330
   506
/* Mac OSX docs advise not to use sbrk; it seems better to use mmap */
slouken@1330
   507
#ifndef HAVE_MORECORE
slouken@1330
   508
#define HAVE_MORECORE 0
slouken@1330
   509
#define HAVE_MMAP 1
slouken@1895
   510
#endif /* HAVE_MORECORE */
slouken@1895
   511
#endif /* DARWIN */
slouken@1330
   512
slouken@1330
   513
#ifndef LACKS_SYS_TYPES_H
slouken@1895
   514
#include <sys/types.h>          /* For size_t */
slouken@1895
   515
#endif /* LACKS_SYS_TYPES_H */
slouken@1330
   516
slouken@1330
   517
/* The maximum possible size_t value has all bits set */
slouken@1330
   518
#define MAX_SIZE_T           (~(size_t)0)
slouken@1330
   519
slouken@1330
   520
#ifndef ONLY_MSPACES
slouken@1330
   521
#define ONLY_MSPACES 0
slouken@1895
   522
#endif /* ONLY_MSPACES */
slouken@1330
   523
#ifndef MSPACES
slouken@1330
   524
#if ONLY_MSPACES
slouken@1330
   525
#define MSPACES 1
slouken@1895
   526
#else /* ONLY_MSPACES */
slouken@1330
   527
#define MSPACES 0
slouken@1895
   528
#endif /* ONLY_MSPACES */
slouken@1895
   529
#endif /* MSPACES */
slouken@1330
   530
#ifndef MALLOC_ALIGNMENT
slouken@1330
   531
#define MALLOC_ALIGNMENT ((size_t)8U)
slouken@1895
   532
#endif /* MALLOC_ALIGNMENT */
slouken@1330
   533
#ifndef FOOTERS
slouken@1330
   534
#define FOOTERS 0
slouken@1895
   535
#endif /* FOOTERS */
slouken@1330
   536
#ifndef ABORT
slouken@1330
   537
#define ABORT  abort()
slouken@1895
   538
#endif /* ABORT */
slouken@1330
   539
#ifndef ABORT_ON_ASSERT_FAILURE
slouken@1330
   540
#define ABORT_ON_ASSERT_FAILURE 1
slouken@1895
   541
#endif /* ABORT_ON_ASSERT_FAILURE */
slouken@1330
   542
#ifndef PROCEED_ON_ERROR
slouken@1330
   543
#define PROCEED_ON_ERROR 0
slouken@1895
   544
#endif /* PROCEED_ON_ERROR */
slouken@1330
   545
#ifndef USE_LOCKS
slouken@1330
   546
#define USE_LOCKS 0
slouken@1895
   547
#endif /* USE_LOCKS */
slouken@1330
   548
#ifndef INSECURE
slouken@1330
   549
#define INSECURE 0
slouken@1895
   550
#endif /* INSECURE */
slouken@1330
   551
#ifndef HAVE_MMAP
slouken@1330
   552
#define HAVE_MMAP 1
slouken@1895
   553
#endif /* HAVE_MMAP */
slouken@1330
   554
#ifndef MMAP_CLEARS
slouken@1330
   555
#define MMAP_CLEARS 1
slouken@1895
   556
#endif /* MMAP_CLEARS */
slouken@1330
   557
#ifndef HAVE_MREMAP
slouken@1330
   558
#ifdef linux
slouken@1330
   559
#define HAVE_MREMAP 1
slouken@1895
   560
#else /* linux */
slouken@1330
   561
#define HAVE_MREMAP 0
slouken@1895
   562
#endif /* linux */
slouken@1895
   563
#endif /* HAVE_MREMAP */
slouken@1330
   564
#ifndef MALLOC_FAILURE_ACTION
slouken@1330
   565
#define MALLOC_FAILURE_ACTION  errno = ENOMEM;
slouken@1895
   566
#endif /* MALLOC_FAILURE_ACTION */
slouken@1330
   567
#ifndef HAVE_MORECORE
slouken@1330
   568
#if ONLY_MSPACES
slouken@1330
   569
#define HAVE_MORECORE 0
slouken@1895
   570
#else /* ONLY_MSPACES */
slouken@1330
   571
#define HAVE_MORECORE 1
slouken@1895
   572
#endif /* ONLY_MSPACES */
slouken@1895
   573
#endif /* HAVE_MORECORE */
slouken@1330
   574
#if !HAVE_MORECORE
slouken@1330
   575
#define MORECORE_CONTIGUOUS 0
slouken@1895
   576
#else /* !HAVE_MORECORE */
slouken@1330
   577
#ifndef MORECORE
slouken@1330
   578
#define MORECORE sbrk
slouken@1895
   579
#endif /* MORECORE */
slouken@1330
   580
#ifndef MORECORE_CONTIGUOUS
slouken@1330
   581
#define MORECORE_CONTIGUOUS 1
slouken@1895
   582
#endif /* MORECORE_CONTIGUOUS */
slouken@1895
   583
#endif /* HAVE_MORECORE */
slouken@1330
   584
#ifndef DEFAULT_GRANULARITY
slouken@1330
   585
#if MORECORE_CONTIGUOUS
slouken@1895
   586
#define DEFAULT_GRANULARITY (0) /* 0 means to compute in init_mparams */
slouken@1895
   587
#else /* MORECORE_CONTIGUOUS */
slouken@1330
   588
#define DEFAULT_GRANULARITY ((size_t)64U * (size_t)1024U)
slouken@1895
   589
#endif /* MORECORE_CONTIGUOUS */
slouken@1895
   590
#endif /* DEFAULT_GRANULARITY */
slouken@1330
   591
#ifndef DEFAULT_TRIM_THRESHOLD
slouken@1330
   592
#ifndef MORECORE_CANNOT_TRIM
slouken@1330
   593
#define DEFAULT_TRIM_THRESHOLD ((size_t)2U * (size_t)1024U * (size_t)1024U)
slouken@1895
   594
#else /* MORECORE_CANNOT_TRIM */
slouken@1330
   595
#define DEFAULT_TRIM_THRESHOLD MAX_SIZE_T
slouken@1895
   596
#endif /* MORECORE_CANNOT_TRIM */
slouken@1895
   597
#endif /* DEFAULT_TRIM_THRESHOLD */
slouken@1330
   598
#ifndef DEFAULT_MMAP_THRESHOLD
slouken@1330
   599
#if HAVE_MMAP
slouken@1330
   600
#define DEFAULT_MMAP_THRESHOLD ((size_t)256U * (size_t)1024U)
slouken@1895
   601
#else /* HAVE_MMAP */
slouken@1330
   602
#define DEFAULT_MMAP_THRESHOLD MAX_SIZE_T
slouken@1895
   603
#endif /* HAVE_MMAP */
slouken@1895
   604
#endif /* DEFAULT_MMAP_THRESHOLD */
slouken@1330
   605
#ifndef USE_BUILTIN_FFS
slouken@1330
   606
#define USE_BUILTIN_FFS 0
slouken@1895
   607
#endif /* USE_BUILTIN_FFS */
slouken@1330
   608
#ifndef USE_DEV_RANDOM
slouken@1330
   609
#define USE_DEV_RANDOM 0
slouken@1895
   610
#endif /* USE_DEV_RANDOM */
slouken@1330
   611
#ifndef NO_MALLINFO
slouken@1330
   612
#define NO_MALLINFO 0
slouken@1895
   613
#endif /* NO_MALLINFO */
slouken@1330
   614
#ifndef MALLINFO_FIELD_TYPE
slouken@1330
   615
#define MALLINFO_FIELD_TYPE size_t
slouken@1895
   616
#endif /* MALLINFO_FIELD_TYPE */
slouken@1330
   617
slouken@11610
   618
#ifndef memset
slouken@7191
   619
#define memset  SDL_memset
slouken@11610
   620
#endif
slouken@11610
   621
#ifndef memcpy
slouken@7191
   622
#define memcpy  SDL_memcpy
slouken@11610
   623
#endif
slouken@1465
   624
slouken@1330
   625
/*
slouken@1330
   626
  mallopt tuning options.  SVID/XPG defines four standard parameter
slouken@1330
   627
  numbers for mallopt, normally defined in malloc.h.  None of these
slouken@1330
   628
  are used in this malloc, so setting them has no effect. But this
slouken@1330
   629
  malloc does support the following options.
slouken@1330
   630
*/
slouken@1330
   631
slouken@1330
   632
#define M_TRIM_THRESHOLD     (-1)
slouken@1330
   633
#define M_GRANULARITY        (-2)
slouken@1330
   634
#define M_MMAP_THRESHOLD     (-3)
slouken@1330
   635
slouken@1330
   636
/* ------------------------ Mallinfo declarations ------------------------ */
slouken@1330
   637
slouken@1330
   638
#if !NO_MALLINFO
slouken@1330
   639
/*
slouken@1330
   640
  This version of malloc supports the standard SVID/XPG mallinfo
slouken@1330
   641
  routine that returns a struct containing usage properties and
slouken@1330
   642
  statistics. It should work on any system that has a
slouken@1330
   643
  /usr/include/malloc.h defining struct mallinfo.  The main
slouken@1330
   644
  declaration needed is the mallinfo struct that is returned (by-copy)
slouken@1330
   645
  by mallinfo().  The malloinfo struct contains a bunch of fields that
slouken@1330
   646
  are not even meaningful in this version of malloc.  These fields are
slouken@1330
   647
  are instead filled by mallinfo() with other numbers that might be of
slouken@1330
   648
  interest.
slouken@1330
   649
slouken@1330
   650
  HAVE_USR_INCLUDE_MALLOC_H should be set if you have a
slouken@1330
   651
  /usr/include/malloc.h file that includes a declaration of struct
slouken@1330
   652
  mallinfo.  If so, it is included; else a compliant version is
slouken@1330
   653
  declared below.  These must be precisely the same for mallinfo() to
slouken@1330
   654
  work.  The original SVID version of this struct, defined on most
slouken@1330
   655
  systems with mallinfo, declares all fields as ints. But some others
slouken@1330
   656
  define as unsigned long. If your system defines the fields using a
slouken@1330
   657
  type of different width than listed here, you MUST #include your
slouken@1330
   658
  system version and #define HAVE_USR_INCLUDE_MALLOC_H.
slouken@1330
   659
*/
slouken@1330
   660
slouken@1330
   661
/* #define HAVE_USR_INCLUDE_MALLOC_H */
slouken@1330
   662
slouken@1330
   663
#ifdef HAVE_USR_INCLUDE_MALLOC_H
slouken@1330
   664
#include "/usr/include/malloc.h"
slouken@1330
   665
#else /* HAVE_USR_INCLUDE_MALLOC_H */
slouken@1330
   666
slouken@1895
   667
struct mallinfo
slouken@1895
   668
{
slouken@1895
   669
    MALLINFO_FIELD_TYPE arena;  /* non-mmapped space allocated from system */
slouken@1895
   670
    MALLINFO_FIELD_TYPE ordblks;        /* number of free chunks */
slouken@1895
   671
    MALLINFO_FIELD_TYPE smblks; /* always 0 */
slouken@1895
   672
    MALLINFO_FIELD_TYPE hblks;  /* always 0 */
slouken@1895
   673
    MALLINFO_FIELD_TYPE hblkhd; /* space in mmapped regions */
slouken@1895
   674
    MALLINFO_FIELD_TYPE usmblks;        /* maximum total allocated space */
slouken@1895
   675
    MALLINFO_FIELD_TYPE fsmblks;        /* always 0 */
slouken@1895
   676
    MALLINFO_FIELD_TYPE uordblks;       /* total allocated space */
slouken@1895
   677
    MALLINFO_FIELD_TYPE fordblks;       /* total free space */
slouken@1895
   678
    MALLINFO_FIELD_TYPE keepcost;       /* releasable (via malloc_trim) space */
slouken@1330
   679
};
slouken@1330
   680
slouken@1330
   681
#endif /* HAVE_USR_INCLUDE_MALLOC_H */
slouken@1330
   682
#endif /* NO_MALLINFO */
slouken@1330
   683
slouken@1330
   684
#ifdef __cplusplus
slouken@1895
   685
extern "C"
slouken@1895
   686
{
slouken@1895
   687
#endif                          /* __cplusplus */
slouken@1330
   688
slouken@1330
   689
#if !ONLY_MSPACES
slouken@1330
   690
slouken@1330
   691
/* ------------------- Declarations of public routines ------------------- */
slouken@1330
   692
slouken@1330
   693
#ifndef USE_DL_PREFIX
slouken@1330
   694
#define dlcalloc               calloc
slouken@1330
   695
#define dlfree                 free
slouken@1330
   696
#define dlmalloc               malloc
slouken@1330
   697
#define dlmemalign             memalign
slouken@1330
   698
#define dlrealloc              realloc
slouken@1330
   699
#define dlvalloc               valloc
slouken@1330
   700
#define dlpvalloc              pvalloc
slouken@1330
   701
#define dlmallinfo             mallinfo
slouken@1330
   702
#define dlmallopt              mallopt
slouken@1330
   703
#define dlmalloc_trim          malloc_trim
slouken@1330
   704
#define dlmalloc_stats         malloc_stats
slouken@1330
   705
#define dlmalloc_usable_size   malloc_usable_size
slouken@1330
   706
#define dlmalloc_footprint     malloc_footprint
slouken@1330
   707
#define dlmalloc_max_footprint malloc_max_footprint
slouken@1330
   708
#define dlindependent_calloc   independent_calloc
slouken@1330
   709
#define dlindependent_comalloc independent_comalloc
slouken@1895
   710
#endif                          /* USE_DL_PREFIX */
slouken@1330
   711
slouken@1330
   712
slouken@1330
   713
/*
slouken@1330
   714
  malloc(size_t n)
slouken@1330
   715
  Returns a pointer to a newly allocated chunk of at least n bytes, or
slouken@1330
   716
  null if no space is available, in which case errno is set to ENOMEM
slouken@1330
   717
  on ANSI C systems.
slouken@1330
   718
slouken@1330
   719
  If n is zero, malloc returns a minimum-sized chunk. (The minimum
slouken@1330
   720
  size is 16 bytes on most 32bit systems, and 32 bytes on 64bit
slouken@1330
   721
  systems.)  Note that size_t is an unsigned type, so calls with
slouken@1330
   722
  arguments that would be negative if signed are interpreted as
slouken@1330
   723
  requests for huge amounts of space, which will often fail. The
slouken@1330
   724
  maximum supported value of n differs across systems, but is in all
slouken@1330
   725
  cases less than the maximum representable value of a size_t.
slouken@1330
   726
*/
slouken@1895
   727
    void *dlmalloc(size_t);
slouken@1330
   728
slouken@1330
   729
/*
slouken@1330
   730
  free(void* p)
slouken@1330
   731
  Releases the chunk of memory pointed to by p, that had been previously
slouken@1330
   732
  allocated using malloc or a related routine such as realloc.
slouken@1330
   733
  It has no effect if p is null. If p was not malloced or already
slouken@1330
   734
  freed, free(p) will by default cause the current program to abort.
slouken@1330
   735
*/
slouken@1895
   736
    void dlfree(void *);
slouken@1330
   737
slouken@1330
   738
/*
slouken@1330
   739
  calloc(size_t n_elements, size_t element_size);
slouken@1330
   740
  Returns a pointer to n_elements * element_size bytes, with all locations
slouken@1330
   741
  set to zero.
slouken@1330
   742
*/
slouken@1895
   743
    void *dlcalloc(size_t, size_t);
slouken@1330
   744
slouken@1330
   745
/*
slouken@1330
   746
  realloc(void* p, size_t n)
slouken@1330
   747
  Returns a pointer to a chunk of size n that contains the same data
slouken@1330
   748
  as does chunk p up to the minimum of (n, p's size) bytes, or null
slouken@1330
   749
  if no space is available.
slouken@1330
   750
slouken@1330
   751
  The returned pointer may or may not be the same as p. The algorithm
slouken@1330
   752
  prefers extending p in most cases when possible, otherwise it
slouken@1330
   753
  employs the equivalent of a malloc-copy-free sequence.
slouken@1330
   754
slouken@1330
   755
  If p is null, realloc is equivalent to malloc.
slouken@1330
   756
slouken@1330
   757
  If space is not available, realloc returns null, errno is set (if on
slouken@1330
   758
  ANSI) and p is NOT freed.
slouken@1330
   759
slouken@1330
   760
  if n is for fewer bytes than already held by p, the newly unused
slouken@1330
   761
  space is lopped off and freed if possible.  realloc with a size
slouken@1330
   762
  argument of zero (re)allocates a minimum-sized chunk.
slouken@1330
   763
slouken@1330
   764
  The old unix realloc convention of allowing the last-free'd chunk
slouken@1330
   765
  to be used as an argument to realloc is not supported.
slouken@1330
   766
*/
slouken@1330
   767
slouken@1895
   768
    void *dlrealloc(void *, size_t);
slouken@1330
   769
slouken@1330
   770
/*
slouken@1330
   771
  memalign(size_t alignment, size_t n);
slouken@1330
   772
  Returns a pointer to a newly allocated chunk of n bytes, aligned
slouken@1330
   773
  in accord with the alignment argument.
slouken@1330
   774
slouken@1330
   775
  The alignment argument should be a power of two. If the argument is
slouken@1330
   776
  not a power of two, the nearest greater power is used.
slouken@1330
   777
  8-byte alignment is guaranteed by normal malloc calls, so don't
slouken@1330
   778
  bother calling memalign with an argument of 8 or less.
slouken@1330
   779
slouken@1330
   780
  Overreliance on memalign is a sure way to fragment space.
slouken@1330
   781
*/
slouken@1895
   782
    void *dlmemalign(size_t, size_t);
slouken@1330
   783
slouken@1330
   784
/*
slouken@1330
   785
  valloc(size_t n);
slouken@1330
   786
  Equivalent to memalign(pagesize, n), where pagesize is the page
slouken@1330
   787
  size of the system. If the pagesize is unknown, 4096 is used.
slouken@1330
   788
*/
slouken@1895
   789
    void *dlvalloc(size_t);
slouken@1330
   790
slouken@1330
   791
/*
slouken@1330
   792
  mallopt(int parameter_number, int parameter_value)
slouken@1330
   793
  Sets tunable parameters The format is to provide a
slouken@1330
   794
  (parameter-number, parameter-value) pair.  mallopt then sets the
slouken@1330
   795
  corresponding parameter to the argument value if it can (i.e., so
slouken@1330
   796
  long as the value is meaningful), and returns 1 if successful else
slouken@1330
   797
  0.  SVID/XPG/ANSI defines four standard param numbers for mallopt,
slouken@1330
   798
  normally defined in malloc.h.  None of these are use in this malloc,
slouken@1330
   799
  so setting them has no effect. But this malloc also supports other
slouken@1330
   800
  options in mallopt. See below for details.  Briefly, supported
slouken@1330
   801
  parameters are as follows (listed defaults are for "typical"
slouken@1330
   802
  configurations).
slouken@1330
   803
slouken@1330
   804
  Symbol            param #  default    allowed param values
slouken@1330
   805
  M_TRIM_THRESHOLD     -1   2*1024*1024   any   (MAX_SIZE_T disables)
slouken@1330
   806
  M_GRANULARITY        -2     page size   any power of 2 >= page size
slouken@1330
   807
  M_MMAP_THRESHOLD     -3      256*1024   any   (or 0 if no MMAP support)
slouken@1330
   808
*/
slouken@1895
   809
    int dlmallopt(int, int);
slouken@1330
   810
slouken@1330
   811
/*
slouken@1330
   812
  malloc_footprint();
slouken@1330
   813
  Returns the number of bytes obtained from the system.  The total
slouken@1330
   814
  number of bytes allocated by malloc, realloc etc., is less than this
slouken@1330
   815
  value. Unlike mallinfo, this function returns only a precomputed
slouken@1330
   816
  result, so can be called frequently to monitor memory consumption.
slouken@1330
   817
  Even if locks are otherwise defined, this function does not use them,
slouken@1330
   818
  so results might not be up to date.
slouken@1330
   819
*/
slouken@1895
   820
    size_t dlmalloc_footprint(void);
slouken@1330
   821
slouken@1330
   822
/*
slouken@1330
   823
  malloc_max_footprint();
slouken@1330
   824
  Returns the maximum number of bytes obtained from the system. This
slouken@1330
   825
  value will be greater than current footprint if deallocated space
slouken@1330
   826
  has been reclaimed by the system. The peak number of bytes allocated
slouken@1330
   827
  by malloc, realloc etc., is less than this value. Unlike mallinfo,
slouken@1330
   828
  this function returns only a precomputed result, so can be called
slouken@1330
   829
  frequently to monitor memory consumption.  Even if locks are
slouken@1330
   830
  otherwise defined, this function does not use them, so results might
slouken@1330
   831
  not be up to date.
slouken@1330
   832
*/
slouken@1895
   833
    size_t dlmalloc_max_footprint(void);
slouken@1330
   834
slouken@1330
   835
#if !NO_MALLINFO
slouken@1330
   836
/*
slouken@1330
   837
  mallinfo()
slouken@1330
   838
  Returns (by copy) a struct containing various summary statistics:
slouken@1330
   839
slouken@1330
   840
  arena:     current total non-mmapped bytes allocated from system
slouken@1330
   841
  ordblks:   the number of free chunks
slouken@1330
   842
  smblks:    always zero.
slouken@1330
   843
  hblks:     current number of mmapped regions
slouken@1330
   844
  hblkhd:    total bytes held in mmapped regions
slouken@1330
   845
  usmblks:   the maximum total allocated space. This will be greater
slouken@1330
   846
                than current total if trimming has occurred.
slouken@1330
   847
  fsmblks:   always zero
slouken@1330
   848
  uordblks:  current total allocated space (normal or mmapped)
slouken@1330
   849
  fordblks:  total free space
slouken@1330
   850
  keepcost:  the maximum number of bytes that could ideally be released
slouken@1330
   851
               back to system via malloc_trim. ("ideally" means that
slouken@1330
   852
               it ignores page restrictions etc.)
slouken@1330
   853
slouken@1330
   854
  Because these fields are ints, but internal bookkeeping may
slouken@1330
   855
  be kept as longs, the reported values may wrap around zero and
slouken@1330
   856
  thus be inaccurate.
slouken@1330
   857
*/
slouken@1895
   858
    struct mallinfo dlmallinfo(void);
slouken@1895
   859
#endif                          /* NO_MALLINFO */
slouken@1330
   860
slouken@1330
   861
/*
slouken@1330
   862
  independent_calloc(size_t n_elements, size_t element_size, void* chunks[]);
slouken@1330
   863
slouken@1330
   864
  independent_calloc is similar to calloc, but instead of returning a
slouken@1330
   865
  single cleared space, it returns an array of pointers to n_elements
slouken@1330
   866
  independent elements that can hold contents of size elem_size, each
slouken@1330
   867
  of which starts out cleared, and can be independently freed,
slouken@1330
   868
  realloc'ed etc. The elements are guaranteed to be adjacently
slouken@1330
   869
  allocated (this is not guaranteed to occur with multiple callocs or
slouken@1330
   870
  mallocs), which may also improve cache locality in some
slouken@1330
   871
  applications.
slouken@1330
   872
slouken@1330
   873
  The "chunks" argument is optional (i.e., may be null, which is
slouken@1330
   874
  probably the most typical usage). If it is null, the returned array
slouken@1330
   875
  is itself dynamically allocated and should also be freed when it is
slouken@1330
   876
  no longer needed. Otherwise, the chunks array must be of at least
slouken@1330
   877
  n_elements in length. It is filled in with the pointers to the
slouken@1330
   878
  chunks.
slouken@1330
   879
slouken@1330
   880
  In either case, independent_calloc returns this pointer array, or
slouken@1330
   881
  null if the allocation failed.  If n_elements is zero and "chunks"
slouken@1330
   882
  is null, it returns a chunk representing an array with zero elements
slouken@1330
   883
  (which should be freed if not wanted).
slouken@1330
   884
slouken@1330
   885
  Each element must be individually freed when it is no longer
slouken@1330
   886
  needed. If you'd like to instead be able to free all at once, you
slouken@1330
   887
  should instead use regular calloc and assign pointers into this
slouken@1330
   888
  space to represent elements.  (In this case though, you cannot
slouken@1330
   889
  independently free elements.)
slouken@1330
   890
slouken@1330
   891
  independent_calloc simplifies and speeds up implementations of many
slouken@1330
   892
  kinds of pools.  It may also be useful when constructing large data
slouken@1330
   893
  structures that initially have a fixed number of fixed-sized nodes,
slouken@1330
   894
  but the number is not known at compile time, and some of the nodes
slouken@1330
   895
  may later need to be freed. For example:
slouken@1330
   896
slouken@1330
   897
  struct Node { int item; struct Node* next; };
slouken@1330
   898
slouken@1330
   899
  struct Node* build_list() {
slouken@1330
   900
    struct Node** pool;
slouken@1330
   901
    int n = read_number_of_nodes_needed();
slouken@1330
   902
    if (n <= 0) return 0;
slouken@1330
   903
    pool = (struct Node**)(independent_calloc(n, sizeof(struct Node), 0);
slouken@1330
   904
    if (pool == 0) die();
slouken@1330
   905
    // organize into a linked list...
slouken@1330
   906
    struct Node* first = pool[0];
slouken@1330
   907
    for (i = 0; i < n-1; ++i)
slouken@1330
   908
      pool[i]->next = pool[i+1];
slouken@1330
   909
    free(pool);     // Can now free the array (or not, if it is needed later)
slouken@1330
   910
    return first;
slouken@1330
   911
  }
slouken@1330
   912
*/
slouken@1895
   913
    void **dlindependent_calloc(size_t, size_t, void **);
slouken@1330
   914
slouken@1330
   915
/*
slouken@1330
   916
  independent_comalloc(size_t n_elements, size_t sizes[], void* chunks[]);
slouken@1330
   917
slouken@1330
   918
  independent_comalloc allocates, all at once, a set of n_elements
slouken@1330
   919
  chunks with sizes indicated in the "sizes" array.    It returns
slouken@1330
   920
  an array of pointers to these elements, each of which can be
slouken@1330
   921
  independently freed, realloc'ed etc. The elements are guaranteed to
slouken@1330
   922
  be adjacently allocated (this is not guaranteed to occur with
slouken@1330
   923
  multiple callocs or mallocs), which may also improve cache locality
slouken@1330
   924
  in some applications.
slouken@1330
   925
slouken@1330
   926
  The "chunks" argument is optional (i.e., may be null). If it is null
slouken@1330
   927
  the returned array is itself dynamically allocated and should also
slouken@1330
   928
  be freed when it is no longer needed. Otherwise, the chunks array
slouken@1330
   929
  must be of at least n_elements in length. It is filled in with the
slouken@1330
   930
  pointers to the chunks.
slouken@1330
   931
slouken@1330
   932
  In either case, independent_comalloc returns this pointer array, or
slouken@1330
   933
  null if the allocation failed.  If n_elements is zero and chunks is
slouken@1330
   934
  null, it returns a chunk representing an array with zero elements
slouken@1330
   935
  (which should be freed if not wanted).
slouken@1330
   936
slouken@1330
   937
  Each element must be individually freed when it is no longer
slouken@1330
   938
  needed. If you'd like to instead be able to free all at once, you
slouken@1330
   939
  should instead use a single regular malloc, and assign pointers at
slouken@1330
   940
  particular offsets in the aggregate space. (In this case though, you
slouken@1330
   941
  cannot independently free elements.)
slouken@1330
   942
slouken@1330
   943
  independent_comallac differs from independent_calloc in that each
slouken@1330
   944
  element may have a different size, and also that it does not
slouken@1330
   945
  automatically clear elements.
slouken@1330
   946
slouken@1330
   947
  independent_comalloc can be used to speed up allocation in cases
slouken@1330
   948
  where several structs or objects must always be allocated at the
slouken@1330
   949
  same time.  For example:
slouken@1330
   950
slouken@1330
   951
  struct Head { ... }
slouken@1330
   952
  struct Foot { ... }
slouken@1330
   953
slouken@1330
   954
  void send_message(char* msg) {
slouken@1330
   955
    int msglen = strlen(msg);
slouken@1330
   956
    size_t sizes[3] = { sizeof(struct Head), msglen, sizeof(struct Foot) };
slouken@1330
   957
    void* chunks[3];
slouken@1330
   958
    if (independent_comalloc(3, sizes, chunks) == 0)
slouken@1330
   959
      die();
slouken@1330
   960
    struct Head* head = (struct Head*)(chunks[0]);
slouken@1330
   961
    char*        body = (char*)(chunks[1]);
slouken@1330
   962
    struct Foot* foot = (struct Foot*)(chunks[2]);
slouken@1330
   963
    // ...
slouken@1330
   964
  }
slouken@1330
   965
slouken@1330
   966
  In general though, independent_comalloc is worth using only for
slouken@1330
   967
  larger values of n_elements. For small values, you probably won't
slouken@1330
   968
  detect enough difference from series of malloc calls to bother.
slouken@1330
   969
slouken@1330
   970
  Overuse of independent_comalloc can increase overall memory usage,
slouken@1330
   971
  since it cannot reuse existing noncontiguous small chunks that
slouken@1330
   972
  might be available for some of the elements.
slouken@1330
   973
*/
slouken@1895
   974
    void **dlindependent_comalloc(size_t, size_t *, void **);
slouken@1330
   975
slouken@1330
   976
slouken@1330
   977
/*
slouken@1330
   978
  pvalloc(size_t n);
slouken@1330
   979
  Equivalent to valloc(minimum-page-that-holds(n)), that is,
slouken@1330
   980
  round up n to nearest pagesize.
slouken@1330
   981
 */
slouken@1895
   982
    void *dlpvalloc(size_t);
slouken@1330
   983
slouken@1330
   984
/*
slouken@1330
   985
  malloc_trim(size_t pad);
slouken@1330
   986
slouken@1330
   987
  If possible, gives memory back to the system (via negative arguments
slouken@1330
   988
  to sbrk) if there is unused memory at the `high' end of the malloc
slouken@1330
   989
  pool or in unused MMAP segments. You can call this after freeing
slouken@1330
   990
  large blocks of memory to potentially reduce the system-level memory
slouken@1330
   991
  requirements of a program. However, it cannot guarantee to reduce
slouken@1330
   992
  memory. Under some allocation patterns, some large free blocks of
slouken@1330
   993
  memory will be locked between two used chunks, so they cannot be
slouken@1330
   994
  given back to the system.
slouken@1330
   995
slouken@1330
   996
  The `pad' argument to malloc_trim represents the amount of free
slouken@1330
   997
  trailing space to leave untrimmed. If this argument is zero, only
slouken@1330
   998
  the minimum amount of memory to maintain internal data structures
slouken@1330
   999
  will be left. Non-zero arguments can be supplied to maintain enough
slouken@1330
  1000
  trailing space to service future expected allocations without having
slouken@1330
  1001
  to re-obtain memory from the system.
slouken@1330
  1002
slouken@1330
  1003
  Malloc_trim returns 1 if it actually released any memory, else 0.
slouken@1330
  1004
*/
slouken@1895
  1005
    int dlmalloc_trim(size_t);
slouken@1330
  1006
slouken@1330
  1007
/*
slouken@1330
  1008
  malloc_usable_size(void* p);
slouken@1330
  1009
slouken@1330
  1010
  Returns the number of bytes you can actually use in
slouken@1330
  1011
  an allocated chunk, which may be more than you requested (although
slouken@1330
  1012
  often not) due to alignment and minimum size constraints.
slouken@1330
  1013
  You can use this many bytes without worrying about
slouken@1330
  1014
  overwriting other allocated objects. This is not a particularly great
slouken@1330
  1015
  programming practice. malloc_usable_size can be more useful in
slouken@1330
  1016
  debugging and assertions, for example:
slouken@1330
  1017
slouken@1330
  1018
  p = malloc(n);
slouken@1330
  1019
  assert(malloc_usable_size(p) >= 256);
slouken@1330
  1020
*/
slouken@1895
  1021
    size_t dlmalloc_usable_size(void *);
slouken@1330
  1022
slouken@1330
  1023
/*
slouken@1330
  1024
  malloc_stats();
slouken@1330
  1025
  Prints on stderr the amount of space obtained from the system (both
slouken@1330
  1026
  via sbrk and mmap), the maximum amount (which may be more than
slouken@1330
  1027
  current if malloc_trim and/or munmap got called), and the current
slouken@1330
  1028
  number of bytes allocated via malloc (or realloc, etc) but not yet
slouken@1330
  1029
  freed. Note that this is the number of bytes allocated, not the
slouken@1330
  1030
  number requested. It will be larger than the number requested
slouken@1330
  1031
  because of alignment and bookkeeping overhead. Because it includes
slouken@1330
  1032
  alignment wastage as being in use, this figure may be greater than
slouken@1330
  1033
  zero even when no user-level chunks are allocated.
slouken@1330
  1034
slouken@1330
  1035
  The reported current and maximum system memory can be inaccurate if
slouken@1330
  1036
  a program makes other calls to system memory allocation functions
slouken@1330
  1037
  (normally sbrk) outside of malloc.
slouken@1330
  1038
slouken@1330
  1039
  malloc_stats prints only the most commonly interesting statistics.
slouken@1330
  1040
  More information can be obtained by calling mallinfo.
slouken@1330
  1041
*/
slouken@1895
  1042
    void dlmalloc_stats(void);
slouken@1895
  1043
slouken@1895
  1044
#endif                          /* ONLY_MSPACES */
slouken@1330
  1045
slouken@1330
  1046
#if MSPACES
slouken@1330
  1047
slouken@1330
  1048
/*
slouken@1330
  1049
  mspace is an opaque type representing an independent
slouken@1330
  1050
  region of space that supports mspace_malloc, etc.
slouken@1330
  1051
*/
slouken@1895
  1052
    typedef void *mspace;
slouken@1330
  1053
slouken@1330
  1054
/*
slouken@1330
  1055
  create_mspace creates and returns a new independent space with the
slouken@1330
  1056
  given initial capacity, or, if 0, the default granularity size.  It
slouken@1330
  1057
  returns null if there is no system memory available to create the
slouken@1330
  1058
  space.  If argument locked is non-zero, the space uses a separate
slouken@1330
  1059
  lock to control access. The capacity of the space will grow
slouken@1330
  1060
  dynamically as needed to service mspace_malloc requests.  You can
slouken@1330
  1061
  control the sizes of incremental increases of this space by
slouken@1330
  1062
  compiling with a different DEFAULT_GRANULARITY or dynamically
slouken@1330
  1063
  setting with mallopt(M_GRANULARITY, value).
slouken@1330
  1064
*/
slouken@1895
  1065
    mspace create_mspace(size_t capacity, int locked);
slouken@1330
  1066
slouken@1330
  1067
/*
slouken@1330
  1068
  destroy_mspace destroys the given space, and attempts to return all
slouken@1330
  1069
  of its memory back to the system, returning the total number of
slouken@1330
  1070
  bytes freed. After destruction, the results of access to all memory
slouken@1330
  1071
  used by the space become undefined.
slouken@1330
  1072
*/
slouken@1895
  1073
    size_t destroy_mspace(mspace msp);
slouken@1330
  1074
slouken@1330
  1075
/*
slouken@1330
  1076
  create_mspace_with_base uses the memory supplied as the initial base
slouken@1330
  1077
  of a new mspace. Part (less than 128*sizeof(size_t) bytes) of this
slouken@1330
  1078
  space is used for bookkeeping, so the capacity must be at least this
slouken@1330
  1079
  large. (Otherwise 0 is returned.) When this initial space is
slouken@1330
  1080
  exhausted, additional memory will be obtained from the system.
slouken@1330
  1081
  Destroying this space will deallocate all additionally allocated
slouken@1330
  1082
  space (if possible) but not the initial base.
slouken@1330
  1083
*/
slouken@1895
  1084
    mspace create_mspace_with_base(void *base, size_t capacity, int locked);
slouken@1330
  1085
slouken@1330
  1086
/*
slouken@1330
  1087
  mspace_malloc behaves as malloc, but operates within
slouken@1330
  1088
  the given space.
slouken@1330
  1089
*/
slouken@1895
  1090
    void *mspace_malloc(mspace msp, size_t bytes);
slouken@1330
  1091
slouken@1330
  1092
/*
slouken@1330
  1093
  mspace_free behaves as free, but operates within
slouken@1330
  1094
  the given space.
slouken@1330
  1095
slouken@1330
  1096
  If compiled with FOOTERS==1, mspace_free is not actually needed.
slouken@1330
  1097
  free may be called instead of mspace_free because freed chunks from
slouken@1330
  1098
  any space are handled by their originating spaces.
slouken@1330
  1099
*/
slouken@1895
  1100
    void mspace_free(mspace msp, void *mem);
slouken@1330
  1101
slouken@1330
  1102
/*
slouken@1330
  1103
  mspace_realloc behaves as realloc, but operates within
slouken@1330
  1104
  the given space.
slouken@1330
  1105
slouken@1330
  1106
  If compiled with FOOTERS==1, mspace_realloc is not actually
slouken@1330
  1107
  needed.  realloc may be called instead of mspace_realloc because
slouken@1330
  1108
  realloced chunks from any space are handled by their originating
slouken@1330
  1109
  spaces.
slouken@1330
  1110
*/
slouken@1895
  1111
    void *mspace_realloc(mspace msp, void *mem, size_t newsize);
slouken@1330
  1112
slouken@1330
  1113
/*
slouken@1330
  1114
  mspace_calloc behaves as calloc, but operates within
slouken@1330
  1115
  the given space.
slouken@1330
  1116
*/
slouken@1895
  1117
    void *mspace_calloc(mspace msp, size_t n_elements, size_t elem_size);
slouken@1330
  1118
slouken@1330
  1119
/*
slouken@1330
  1120
  mspace_memalign behaves as memalign, but operates within
slouken@1330
  1121
  the given space.
slouken@1330
  1122
*/
slouken@1895
  1123
    void *mspace_memalign(mspace msp, size_t alignment, size_t bytes);
slouken@1330
  1124
slouken@1330
  1125
/*
slouken@1330
  1126
  mspace_independent_calloc behaves as independent_calloc, but
slouken@1330
  1127
  operates within the given space.
slouken@1330
  1128
*/
slouken@1895
  1129
    void **mspace_independent_calloc(mspace msp, size_t n_elements,
slouken@1895
  1130
                                     size_t elem_size, void *chunks[]);
slouken@1330
  1131
slouken@1330
  1132
/*
slouken@1330
  1133
  mspace_independent_comalloc behaves as independent_comalloc, but
slouken@1330
  1134
  operates within the given space.
slouken@1330
  1135
*/
slouken@1895
  1136
    void **mspace_independent_comalloc(mspace msp, size_t n_elements,
slouken@1895
  1137
                                       size_t sizes[], void *chunks[]);
slouken@1330
  1138
slouken@1330
  1139
/*
slouken@1330
  1140
  mspace_footprint() returns the number of bytes obtained from the
slouken@1330
  1141
  system for this space.
slouken@1330
  1142
*/
slouken@1895
  1143
    size_t mspace_footprint(mspace msp);
slouken@1330
  1144
slouken@1330
  1145
/*
slouken@1330
  1146
  mspace_max_footprint() returns the peak number of bytes obtained from the
slouken@1330
  1147
  system for this space.
slouken@1330
  1148
*/
slouken@1895
  1149
    size_t mspace_max_footprint(mspace msp);
slouken@1330
  1150
slouken@1330
  1151
slouken@1330
  1152
#if !NO_MALLINFO
slouken@1330
  1153
/*
slouken@1330
  1154
  mspace_mallinfo behaves as mallinfo, but reports properties of
slouken@1330
  1155
  the given space.
slouken@1330
  1156
*/
slouken@1895
  1157
    struct mallinfo mspace_mallinfo(mspace msp);
slouken@1895
  1158
#endif                          /* NO_MALLINFO */
slouken@1330
  1159
slouken@1330
  1160
/*
slouken@1330
  1161
  mspace_malloc_stats behaves as malloc_stats, but reports
slouken@1330
  1162
  properties of the given space.
slouken@1330
  1163
*/
slouken@1895
  1164
    void mspace_malloc_stats(mspace msp);
slouken@1330
  1165
slouken@1330
  1166
/*
slouken@1330
  1167
  mspace_trim behaves as malloc_trim, but
slouken@1330
  1168
  operates within the given space.
slouken@1330
  1169
*/
slouken@1895
  1170
    int mspace_trim(mspace msp, size_t pad);
slouken@1330
  1171
slouken@1330
  1172
/*
slouken@1330
  1173
  An alias for mallopt.
slouken@1330
  1174
*/
slouken@1895
  1175
    int mspace_mallopt(int, int);
slouken@1895
  1176
slouken@1895
  1177
#endif                          /* MSPACES */
slouken@1330
  1178
slouken@1330
  1179
#ifdef __cplusplus
slouken@1895
  1180
};                              /* end of extern "C" */
slouken@1330
  1181
#endif /* __cplusplus */
slouken@1330
  1182
slouken@1330
  1183
/*
slouken@1330
  1184
  ========================================================================
slouken@1330
  1185
  To make a fully customizable malloc.h header file, cut everything
slouken@1330
  1186
  above this line, put into file malloc.h, edit to suit, and #include it
slouken@1330
  1187
  on the next line, as well as in programs that use this malloc.
slouken@1330
  1188
  ========================================================================
slouken@1330
  1189
*/
slouken@1330
  1190
slouken@1330
  1191
/* #include "malloc.h" */
slouken@1330
  1192
slouken@1330
  1193
/*------------------------------ internal #includes ---------------------- */
slouken@1330
  1194
slouken@1330
  1195
#ifdef _MSC_VER
slouken@1895
  1196
#pragma warning( disable : 4146 )       /* no "unsigned" warnings */
slouken@1330
  1197
#endif /* _MSC_VER */
slouken@1330
  1198
slouken@1330
  1199
#ifndef LACKS_STDIO_H
slouken@1895
  1200
#include <stdio.h>              /* for printing in malloc_stats */
slouken@1330
  1201
#endif
slouken@1330
  1202
slouken@1330
  1203
#ifndef LACKS_ERRNO_H
slouken@1895
  1204
#include <errno.h>              /* for MALLOC_FAILURE_ACTION */
slouken@1330
  1205
#endif /* LACKS_ERRNO_H */
slouken@1330
  1206
#if FOOTERS
slouken@1895
  1207
#include <time.h>               /* for magic initialization */
slouken@1330
  1208
#endif /* FOOTERS */
slouken@1330
  1209
#ifndef LACKS_STDLIB_H
slouken@1895
  1210
#include <stdlib.h>             /* for abort() */
slouken@1330
  1211
#endif /* LACKS_STDLIB_H */
slouken@1330
  1212
#ifdef DEBUG
slouken@1330
  1213
#if ABORT_ON_ASSERT_FAILURE
slouken@1330
  1214
#define assert(x) if(!(x)) ABORT
slouken@1330
  1215
#else /* ABORT_ON_ASSERT_FAILURE */
slouken@1330
  1216
#include <assert.h>
slouken@1330
  1217
#endif /* ABORT_ON_ASSERT_FAILURE */
slouken@1895
  1218
#else /* DEBUG */
slouken@1330
  1219
#define assert(x)
slouken@1330
  1220
#endif /* DEBUG */
slouken@1330
  1221
#ifndef LACKS_STRING_H
slouken@1895
  1222
#include <string.h>             /* for memset etc */
slouken@1895
  1223
#endif /* LACKS_STRING_H */
slouken@1330
  1224
#if USE_BUILTIN_FFS
slouken@1330
  1225
#ifndef LACKS_STRINGS_H
slouken@1895
  1226
#include <strings.h>            /* for ffs */
slouken@1330
  1227
#endif /* LACKS_STRINGS_H */
slouken@1330
  1228
#endif /* USE_BUILTIN_FFS */
slouken@1330
  1229
#if HAVE_MMAP
slouken@1330
  1230
#ifndef LACKS_SYS_MMAN_H
slouken@1895
  1231
#include <sys/mman.h>           /* for mmap */
slouken@1330
  1232
#endif /* LACKS_SYS_MMAN_H */
slouken@1330
  1233
#ifndef LACKS_FCNTL_H
slouken@1330
  1234
#include <fcntl.h>
slouken@1330
  1235
#endif /* LACKS_FCNTL_H */
slouken@1330
  1236
#endif /* HAVE_MMAP */
slouken@1330
  1237
#if HAVE_MORECORE
slouken@1330
  1238
#ifndef LACKS_UNISTD_H
slouken@1895
  1239
#include <unistd.h>             /* for sbrk */
slouken@1330
  1240
#else /* LACKS_UNISTD_H */
slouken@1330
  1241
#if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)
slouken@1895
  1242
extern void *sbrk(ptrdiff_t);
slouken@1330
  1243
#endif /* FreeBSD etc */
slouken@1330
  1244
#endif /* LACKS_UNISTD_H */
slouken@1330
  1245
#endif /* HAVE_MMAP */
slouken@1330
  1246
slouken@1330
  1247
#ifndef WIN32
slouken@1330
  1248
#ifndef malloc_getpagesize
slouken@1895
  1249
#  ifdef _SC_PAGESIZE           /* some SVR4 systems omit an underscore */
slouken@1330
  1250
#    ifndef _SC_PAGE_SIZE
slouken@1330
  1251
#      define _SC_PAGE_SIZE _SC_PAGESIZE
slouken@1330
  1252
#    endif
slouken@1330
  1253
#  endif
slouken@1330
  1254
#  ifdef _SC_PAGE_SIZE
slouken@1330
  1255
#    define malloc_getpagesize sysconf(_SC_PAGE_SIZE)
slouken@1330
  1256
#  else
slouken@1330
  1257
#    if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE)
slouken@1895
  1258
extern size_t getpagesize();
slouken@1330
  1259
#      define malloc_getpagesize getpagesize()
slouken@1330
  1260
#    else
slouken@1895
  1261
#      ifdef WIN32              /* use supplied emulation of getpagesize */
slouken@1330
  1262
#        define malloc_getpagesize getpagesize()
slouken@1330
  1263
#      else
slouken@1330
  1264
#        ifndef LACKS_SYS_PARAM_H
slouken@1330
  1265
#          include <sys/param.h>
slouken@1330
  1266
#        endif
slouken@1330
  1267
#        ifdef EXEC_PAGESIZE
slouken@1330
  1268
#          define malloc_getpagesize EXEC_PAGESIZE
slouken@1330
  1269
#        else
slouken@1330
  1270
#          ifdef NBPG
slouken@1330
  1271
#            ifndef CLSIZE
slouken@1330
  1272
#              define malloc_getpagesize NBPG
slouken@1330
  1273
#            else
slouken@1330
  1274
#              define malloc_getpagesize (NBPG * CLSIZE)
slouken@1330
  1275
#            endif
slouken@1330
  1276
#          else
slouken@1330
  1277
#            ifdef NBPC
slouken@1330
  1278
#              define malloc_getpagesize NBPC
slouken@1330
  1279
#            else
slouken@1330
  1280
#              ifdef PAGESIZE
slouken@1330
  1281
#                define malloc_getpagesize PAGESIZE
slouken@1330
  1282
#              else /* just guess */
slouken@1330
  1283
#                define malloc_getpagesize ((size_t)4096U)
slouken@1330
  1284
#              endif
slouken@1330
  1285
#            endif
slouken@1330
  1286
#          endif
slouken@1330
  1287
#        endif
slouken@1330
  1288
#      endif
slouken@1330
  1289
#    endif
slouken@1330
  1290
#  endif
slouken@1330
  1291
#endif
slouken@1330
  1292
#endif
slouken@1330
  1293
slouken@1330
  1294
/* ------------------- size_t and alignment properties -------------------- */
slouken@1330
  1295
slouken@1330
  1296
/* The byte and bit size of a size_t */
slouken@1330
  1297
#define SIZE_T_SIZE         (sizeof(size_t))
slouken@1330
  1298
#define SIZE_T_BITSIZE      (sizeof(size_t) << 3)
slouken@1330
  1299
slouken@1330
  1300
/* Some constants coerced to size_t */
slouken@1330
  1301
/* Annoying but necessary to avoid errors on some plaftorms */
slouken@1330
  1302
#define SIZE_T_ZERO         ((size_t)0)
slouken@1330
  1303
#define SIZE_T_ONE          ((size_t)1)
slouken@1330
  1304
#define SIZE_T_TWO          ((size_t)2)
slouken@1330
  1305
#define TWO_SIZE_T_SIZES    (SIZE_T_SIZE<<1)
slouken@1330
  1306
#define FOUR_SIZE_T_SIZES   (SIZE_T_SIZE<<2)
slouken@1330
  1307
#define SIX_SIZE_T_SIZES    (FOUR_SIZE_T_SIZES+TWO_SIZE_T_SIZES)
slouken@1330
  1308
#define HALF_MAX_SIZE_T     (MAX_SIZE_T / 2U)
slouken@1330
  1309
slouken@1330
  1310
/* The bit mask value corresponding to MALLOC_ALIGNMENT */
slouken@1330
  1311
#define CHUNK_ALIGN_MASK    (MALLOC_ALIGNMENT - SIZE_T_ONE)
slouken@1330
  1312
slouken@1330
  1313
/* True if address a has acceptable alignment */
slouken@1330
  1314
#define is_aligned(A)       (((size_t)((A)) & (CHUNK_ALIGN_MASK)) == 0)
slouken@1330
  1315
slouken@1330
  1316
/* the number of bytes to offset an address to align it */
slouken@1330
  1317
#define align_offset(A)\
slouken@1330
  1318
 ((((size_t)(A) & CHUNK_ALIGN_MASK) == 0)? 0 :\
slouken@1330
  1319
  ((MALLOC_ALIGNMENT - ((size_t)(A) & CHUNK_ALIGN_MASK)) & CHUNK_ALIGN_MASK))
slouken@1330
  1320
slouken@1330
  1321
/* -------------------------- MMAP preliminaries ------------------------- */
slouken@1330
  1322
slouken@1330
  1323
/*
slouken@1330
  1324
   If HAVE_MORECORE or HAVE_MMAP are false, we just define calls and
slouken@1330
  1325
   checks to fail so compiler optimizer can delete code rather than
slouken@1330
  1326
   using so many "#if"s.
slouken@1330
  1327
*/
slouken@1330
  1328
slouken@1330
  1329
slouken@1330
  1330
/* MORECORE and MMAP must return MFAIL on failure */
slouken@1330
  1331
#define MFAIL                ((void*)(MAX_SIZE_T))
slouken@1895
  1332
#define CMFAIL               ((char*)(MFAIL))   /* defined for convenience */
slouken@1330
  1333
slouken@1330
  1334
#if !HAVE_MMAP
slouken@1330
  1335
#define IS_MMAPPED_BIT       (SIZE_T_ZERO)
slouken@1330
  1336
#define USE_MMAP_BIT         (SIZE_T_ZERO)
slouken@1330
  1337
#define CALL_MMAP(s)         MFAIL
slouken@1330
  1338
#define CALL_MUNMAP(a, s)    (-1)
slouken@1330
  1339
#define DIRECT_MMAP(s)       MFAIL
slouken@1330
  1340
slouken@1330
  1341
#else /* HAVE_MMAP */
slouken@1330
  1342
#define IS_MMAPPED_BIT       (SIZE_T_ONE)
slouken@1330
  1343
#define USE_MMAP_BIT         (SIZE_T_ONE)
slouken@1330
  1344
slouken@1330
  1345
#ifndef WIN32
slouken@1330
  1346
#define CALL_MUNMAP(a, s)    munmap((a), (s))
slouken@1330
  1347
#define MMAP_PROT            (PROT_READ|PROT_WRITE)
slouken@1330
  1348
#if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
slouken@1330
  1349
#define MAP_ANONYMOUS        MAP_ANON
slouken@1330
  1350
#endif /* MAP_ANON */
slouken@1330
  1351
#ifdef MAP_ANONYMOUS
slouken@1330
  1352
#define MMAP_FLAGS           (MAP_PRIVATE|MAP_ANONYMOUS)
slouken@1330
  1353
#define CALL_MMAP(s)         mmap(0, (s), MMAP_PROT, MMAP_FLAGS, -1, 0)
slouken@1330
  1354
#else /* MAP_ANONYMOUS */
slouken@1330
  1355
/*
slouken@1330
  1356
   Nearly all versions of mmap support MAP_ANONYMOUS, so the following
slouken@1330
  1357
   is unlikely to be needed, but is supplied just in case.
slouken@1330
  1358
*/
slouken@1330
  1359
#define MMAP_FLAGS           (MAP_PRIVATE)
slouken@1895
  1360
static int dev_zero_fd = -1;    /* Cached file descriptor for /dev/zero. */
slouken@1330
  1361
#define CALL_MMAP(s) ((dev_zero_fd < 0) ? \
slouken@1330
  1362
           (dev_zero_fd = open("/dev/zero", O_RDWR), \
slouken@1330
  1363
            mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0)) : \
slouken@1330
  1364
            mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0))
slouken@1330
  1365
#endif /* MAP_ANONYMOUS */
slouken@1330
  1366
slouken@1330
  1367
#define DIRECT_MMAP(s)       CALL_MMAP(s)
slouken@1330
  1368
#else /* WIN32 */
slouken@1330
  1369
slouken@1330
  1370
/* Win32 MMAP via VirtualAlloc */
slouken@1895
  1371
static void *
slouken@1895
  1372
win32mmap(size_t size)
slouken@1895
  1373
{
slouken@1895
  1374
    void *ptr =
slouken@1895
  1375
        VirtualAlloc(0, size, MEM_RESERVE | MEM_COMMIT, PAGE_READWRITE);
slouken@1895
  1376
    return (ptr != 0) ? ptr : MFAIL;
slouken@1330
  1377
}
slouken@1330
  1378
slouken@1330
  1379
/* For direct MMAP, use MEM_TOP_DOWN to minimize interference */
slouken@1895
  1380
static void *
slouken@1895
  1381
win32direct_mmap(size_t size)
slouken@1895
  1382
{
slouken@1895
  1383
    void *ptr = VirtualAlloc(0, size, MEM_RESERVE | MEM_COMMIT | MEM_TOP_DOWN,
slouken@1895
  1384
                             PAGE_READWRITE);
slouken@1895
  1385
    return (ptr != 0) ? ptr : MFAIL;
slouken@1330
  1386
}
slouken@1330
  1387
slouken@1330
  1388
/* This function supports releasing coalesed segments */
slouken@1895
  1389
static int
slouken@1895
  1390
win32munmap(void *ptr, size_t size)
slouken@1895
  1391
{
slouken@1895
  1392
    MEMORY_BASIC_INFORMATION minfo;
slouken@1895
  1393
    char *cptr = ptr;
slouken@1895
  1394
    while (size) {
slouken@1895
  1395
        if (VirtualQuery(cptr, &minfo, sizeof(minfo)) == 0)
slouken@1895
  1396
            return -1;
slouken@1895
  1397
        if (minfo.BaseAddress != cptr || minfo.AllocationBase != cptr ||
slouken@1895
  1398
            minfo.State != MEM_COMMIT || minfo.RegionSize > size)
slouken@1895
  1399
            return -1;
slouken@1895
  1400
        if (VirtualFree(cptr, 0, MEM_RELEASE) == 0)
slouken@1895
  1401
            return -1;
slouken@1895
  1402
        cptr += minfo.RegionSize;
slouken@1895
  1403
        size -= minfo.RegionSize;
slouken@1895
  1404
    }
slouken@1895
  1405
    return 0;
slouken@1330
  1406
}
slouken@1330
  1407
slouken@1330
  1408
#define CALL_MMAP(s)         win32mmap(s)
slouken@1330
  1409
#define CALL_MUNMAP(a, s)    win32munmap((a), (s))
slouken@1330
  1410
#define DIRECT_MMAP(s)       win32direct_mmap(s)
slouken@1330
  1411
#endif /* WIN32 */
slouken@1330
  1412
#endif /* HAVE_MMAP */
slouken@1330
  1413
slouken@1330
  1414
#if HAVE_MMAP && HAVE_MREMAP
slouken@1330
  1415
#define CALL_MREMAP(addr, osz, nsz, mv) mremap((addr), (osz), (nsz), (mv))
slouken@1895
  1416
#else /* HAVE_MMAP && HAVE_MREMAP */
slouken@1330
  1417
#define CALL_MREMAP(addr, osz, nsz, mv) MFAIL
slouken@1330
  1418
#endif /* HAVE_MMAP && HAVE_MREMAP */
slouken@1330
  1419
slouken@1330
  1420
#if HAVE_MORECORE
slouken@1330
  1421
#define CALL_MORECORE(S)     MORECORE(S)
slouken@1895
  1422
#else /* HAVE_MORECORE */
slouken@1330
  1423
#define CALL_MORECORE(S)     MFAIL
slouken@1330
  1424
#endif /* HAVE_MORECORE */
slouken@1330
  1425
slouken@1330
  1426
/* mstate bit set if continguous morecore disabled or failed */
slouken@1330
  1427
#define USE_NONCONTIGUOUS_BIT (4U)
slouken@1330
  1428
slouken@1330
  1429
/* segment bit set in create_mspace_with_base */
slouken@1330
  1430
#define EXTERN_BIT            (8U)
slouken@1330
  1431
slouken@1330
  1432
slouken@1330
  1433
/* --------------------------- Lock preliminaries ------------------------ */
slouken@1330
  1434
slouken@1330
  1435
#if USE_LOCKS
slouken@1330
  1436
slouken@1330
  1437
/*
slouken@1330
  1438
  When locks are defined, there are up to two global locks:
slouken@1330
  1439
slouken@1330
  1440
  * If HAVE_MORECORE, morecore_mutex protects sequences of calls to
slouken@1330
  1441
    MORECORE.  In many cases sys_alloc requires two calls, that should
slouken@1330
  1442
    not be interleaved with calls by other threads.  This does not
slouken@1330
  1443
    protect against direct calls to MORECORE by other threads not
slouken@1330
  1444
    using this lock, so there is still code to cope the best we can on
slouken@1330
  1445
    interference.
slouken@1330
  1446
slouken@1330
  1447
  * magic_init_mutex ensures that mparams.magic and other
slouken@1330
  1448
    unique mparams values are initialized only once.
slouken@1330
  1449
*/
slouken@1330
  1450
slouken@1330
  1451
#ifndef WIN32
slouken@1330
  1452
/* By default use posix locks */
slouken@1330
  1453
#include <pthread.h>
slouken@1330
  1454
#define MLOCK_T pthread_mutex_t
slouken@1330
  1455
#define INITIAL_LOCK(l)      pthread_mutex_init(l, NULL)
slouken@1330
  1456
#define ACQUIRE_LOCK(l)      pthread_mutex_lock(l)
slouken@1330
  1457
#define RELEASE_LOCK(l)      pthread_mutex_unlock(l)
slouken@1330
  1458
slouken@1330
  1459
#if HAVE_MORECORE
slouken@1330
  1460
static MLOCK_T morecore_mutex = PTHREAD_MUTEX_INITIALIZER;
slouken@1330
  1461
#endif /* HAVE_MORECORE */
slouken@1330
  1462
slouken@1330
  1463
static MLOCK_T magic_init_mutex = PTHREAD_MUTEX_INITIALIZER;
slouken@1330
  1464
slouken@1330
  1465
#else /* WIN32 */
slouken@1330
  1466
/*
slouken@1330
  1467
   Because lock-protected regions have bounded times, and there
slouken@1330
  1468
   are no recursive lock calls, we can use simple spinlocks.
slouken@1330
  1469
*/
slouken@1330
  1470
slouken@1330
  1471
#define MLOCK_T long
slouken@1895
  1472
static int
slouken@1895
  1473
win32_acquire_lock(MLOCK_T * sl)
slouken@1895
  1474
{
slouken@1895
  1475
    for (;;) {
slouken@1330
  1476
#ifdef InterlockedCompareExchangePointer
slouken@1895
  1477
        if (!InterlockedCompareExchange(sl, 1, 0))
slouken@1895
  1478
            return 0;
slouken@1895
  1479
#else /* Use older void* version */
slouken@1895
  1480
        if (!InterlockedCompareExchange((void **) sl, (void *) 1, (void *) 0))
slouken@1895
  1481
            return 0;
slouken@1330
  1482
#endif /* InterlockedCompareExchangePointer */
slouken@1895
  1483
        Sleep(0);
slouken@1895
  1484
    }
slouken@1330
  1485
}
slouken@1330
  1486
slouken@1895
  1487
static void
slouken@1895
  1488
win32_release_lock(MLOCK_T * sl)
slouken@1895
  1489
{
slouken@1895
  1490
    InterlockedExchange(sl, 0);
slouken@1330
  1491
}
slouken@1330
  1492
slouken@1330
  1493
#define INITIAL_LOCK(l)      *(l)=0
slouken@1330
  1494
#define ACQUIRE_LOCK(l)      win32_acquire_lock(l)
slouken@1330
  1495
#define RELEASE_LOCK(l)      win32_release_lock(l)
slouken@1330
  1496
#if HAVE_MORECORE
slouken@1330
  1497
static MLOCK_T morecore_mutex;
slouken@1330
  1498
#endif /* HAVE_MORECORE */
slouken@1330
  1499
static MLOCK_T magic_init_mutex;
slouken@1330
  1500
#endif /* WIN32 */
slouken@1330
  1501
slouken@1330
  1502
#define USE_LOCK_BIT               (2U)
slouken@1895
  1503
#else /* USE_LOCKS */
slouken@1330
  1504
#define USE_LOCK_BIT               (0U)
slouken@1330
  1505
#define INITIAL_LOCK(l)
slouken@1330
  1506
#endif /* USE_LOCKS */
slouken@1330
  1507
slouken@1330
  1508
#if USE_LOCKS && HAVE_MORECORE
slouken@1330
  1509
#define ACQUIRE_MORECORE_LOCK()    ACQUIRE_LOCK(&morecore_mutex);
slouken@1330
  1510
#define RELEASE_MORECORE_LOCK()    RELEASE_LOCK(&morecore_mutex);
slouken@1330
  1511
#else /* USE_LOCKS && HAVE_MORECORE */
slouken@1330
  1512
#define ACQUIRE_MORECORE_LOCK()
slouken@1330
  1513
#define RELEASE_MORECORE_LOCK()
slouken@1330
  1514
#endif /* USE_LOCKS && HAVE_MORECORE */
slouken@1330
  1515
slouken@1330
  1516
#if USE_LOCKS
slouken@1330
  1517
#define ACQUIRE_MAGIC_INIT_LOCK()  ACQUIRE_LOCK(&magic_init_mutex);
slouken@1330
  1518
#define RELEASE_MAGIC_INIT_LOCK()  RELEASE_LOCK(&magic_init_mutex);
slouken@1895
  1519
#else /* USE_LOCKS */
slouken@1330
  1520
#define ACQUIRE_MAGIC_INIT_LOCK()
slouken@1330
  1521
#define RELEASE_MAGIC_INIT_LOCK()
slouken@1330
  1522
#endif /* USE_LOCKS */
slouken@1330
  1523
slouken@1330
  1524
slouken@1330
  1525
/* -----------------------  Chunk representations ------------------------ */
slouken@1330
  1526
slouken@1330
  1527
/*
slouken@1330
  1528
  (The following includes lightly edited explanations by Colin Plumb.)
slouken@1330
  1529
slouken@1330
  1530
  The malloc_chunk declaration below is misleading (but accurate and
slouken@1330
  1531
  necessary).  It declares a "view" into memory allowing access to
slouken@1330
  1532
  necessary fields at known offsets from a given base.
slouken@1330
  1533
slouken@1330
  1534
  Chunks of memory are maintained using a `boundary tag' method as
slouken@1330
  1535
  originally described by Knuth.  (See the paper by Paul Wilson
slouken@1330
  1536
  ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a survey of such
slouken@1330
  1537
  techniques.)  Sizes of free chunks are stored both in the front of
slouken@1330
  1538
  each chunk and at the end.  This makes consolidating fragmented
slouken@1330
  1539
  chunks into bigger chunks fast.  The head fields also hold bits
slouken@1330
  1540
  representing whether chunks are free or in use.
slouken@1330
  1541
slouken@1330
  1542
  Here are some pictures to make it clearer.  They are "exploded" to
slouken@1330
  1543
  show that the state of a chunk can be thought of as extending from
slouken@1330
  1544
  the high 31 bits of the head field of its header through the
slouken@1330
  1545
  prev_foot and PINUSE_BIT bit of the following chunk header.
slouken@1330
  1546
slouken@1330
  1547
  A chunk that's in use looks like:
slouken@1330
  1548
slouken@1330
  1549
   chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1550
           | Size of previous chunk (if P = 1)                             |
slouken@1330
  1551
           +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1552
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
slouken@1330
  1553
         | Size of this chunk                                         1| +-+
slouken@1330
  1554
   mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1555
         |                                                               |
slouken@1330
  1556
         +-                                                             -+
slouken@1330
  1557
         |                                                               |
slouken@1330
  1558
         +-                                                             -+
slouken@1330
  1559
         |                                                               :
slouken@1330
  1560
         +-      size - sizeof(size_t) available payload bytes          -+
slouken@1330
  1561
         :                                                               |
slouken@1330
  1562
 chunk-> +-                                                             -+
slouken@1330
  1563
         |                                                               |
slouken@1330
  1564
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1565
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1|
slouken@1330
  1566
       | Size of next chunk (may or may not be in use)               | +-+
slouken@1330
  1567
 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1568
slouken@1330
  1569
    And if it's free, it looks like this:
slouken@1330
  1570
slouken@1330
  1571
   chunk-> +-                                                             -+
slouken@1330
  1572
           | User payload (must be in use, or we would have merged!)       |
slouken@1330
  1573
           +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1574
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
slouken@1330
  1575
         | Size of this chunk                                         0| +-+
slouken@1330
  1576
   mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1577
         | Next pointer                                                  |
slouken@1330
  1578
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1579
         | Prev pointer                                                  |
slouken@1330
  1580
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1581
         |                                                               :
slouken@1330
  1582
         +-      size - sizeof(struct chunk) unused bytes               -+
slouken@1330
  1583
         :                                                               |
slouken@1330
  1584
 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1585
         | Size of this chunk                                            |
slouken@1330
  1586
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1587
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0|
slouken@1330
  1588
       | Size of next chunk (must be in use, or we would have merged)| +-+
slouken@1330
  1589
 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1590
       |                                                               :
slouken@1330
  1591
       +- User payload                                                -+
slouken@1330
  1592
       :                                                               |
slouken@1330
  1593
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1594
                                                                     |0|
slouken@1330
  1595
                                                                     +-+
slouken@1330
  1596
  Note that since we always merge adjacent free chunks, the chunks
slouken@1330
  1597
  adjacent to a free chunk must be in use.
slouken@1330
  1598
slouken@1330
  1599
  Given a pointer to a chunk (which can be derived trivially from the
slouken@1330
  1600
  payload pointer) we can, in O(1) time, find out whether the adjacent
slouken@1330
  1601
  chunks are free, and if so, unlink them from the lists that they
slouken@1330
  1602
  are on and merge them with the current chunk.
slouken@1330
  1603
slouken@1330
  1604
  Chunks always begin on even word boundaries, so the mem portion
slouken@1330
  1605
  (which is returned to the user) is also on an even word boundary, and
slouken@1330
  1606
  thus at least double-word aligned.
slouken@1330
  1607
slouken@1330
  1608
  The P (PINUSE_BIT) bit, stored in the unused low-order bit of the
slouken@1330
  1609
  chunk size (which is always a multiple of two words), is an in-use
slouken@1330
  1610
  bit for the *previous* chunk.  If that bit is *clear*, then the
slouken@1330
  1611
  word before the current chunk size contains the previous chunk
slouken@1330
  1612
  size, and can be used to find the front of the previous chunk.
slouken@1330
  1613
  The very first chunk allocated always has this bit set, preventing
slouken@1330
  1614
  access to non-existent (or non-owned) memory. If pinuse is set for
slouken@1330
  1615
  any given chunk, then you CANNOT determine the size of the
slouken@1330
  1616
  previous chunk, and might even get a memory addressing fault when
slouken@1330
  1617
  trying to do so.
slouken@1330
  1618
slouken@1330
  1619
  The C (CINUSE_BIT) bit, stored in the unused second-lowest bit of
slouken@1330
  1620
  the chunk size redundantly records whether the current chunk is
slouken@1330
  1621
  inuse. This redundancy enables usage checks within free and realloc,
slouken@1330
  1622
  and reduces indirection when freeing and consolidating chunks.
slouken@1330
  1623
slouken@1330
  1624
  Each freshly allocated chunk must have both cinuse and pinuse set.
slouken@1330
  1625
  That is, each allocated chunk borders either a previously allocated
slouken@1330
  1626
  and still in-use chunk, or the base of its memory arena. This is
slouken@1330
  1627
  ensured by making all allocations from the the `lowest' part of any
slouken@1330
  1628
  found chunk.  Further, no free chunk physically borders another one,
slouken@1330
  1629
  so each free chunk is known to be preceded and followed by either
slouken@1330
  1630
  inuse chunks or the ends of memory.
slouken@1330
  1631
slouken@1330
  1632
  Note that the `foot' of the current chunk is actually represented
slouken@1330
  1633
  as the prev_foot of the NEXT chunk. This makes it easier to
slouken@1330
  1634
  deal with alignments etc but can be very confusing when trying
slouken@1330
  1635
  to extend or adapt this code.
slouken@1330
  1636
slouken@1330
  1637
  The exceptions to all this are
slouken@1330
  1638
slouken@1330
  1639
     1. The special chunk `top' is the top-most available chunk (i.e.,
slouken@1330
  1640
        the one bordering the end of available memory). It is treated
slouken@1330
  1641
        specially.  Top is never included in any bin, is used only if
slouken@1330
  1642
        no other chunk is available, and is released back to the
slouken@1330
  1643
        system if it is very large (see M_TRIM_THRESHOLD).  In effect,
slouken@1330
  1644
        the top chunk is treated as larger (and thus less well
slouken@1330
  1645
        fitting) than any other available chunk.  The top chunk
slouken@1330
  1646
        doesn't update its trailing size field since there is no next
slouken@1330
  1647
        contiguous chunk that would have to index off it. However,
slouken@1330
  1648
        space is still allocated for it (TOP_FOOT_SIZE) to enable
slouken@1330
  1649
        separation or merging when space is extended.
slouken@1330
  1650
slouken@1330
  1651
     3. Chunks allocated via mmap, which have the lowest-order bit
slouken@1330
  1652
        (IS_MMAPPED_BIT) set in their prev_foot fields, and do not set
slouken@1330
  1653
        PINUSE_BIT in their head fields.  Because they are allocated
slouken@1330
  1654
        one-by-one, each must carry its own prev_foot field, which is
slouken@1330
  1655
        also used to hold the offset this chunk has within its mmapped
slouken@1330
  1656
        region, which is needed to preserve alignment. Each mmapped
slouken@1330
  1657
        chunk is trailed by the first two fields of a fake next-chunk
slouken@1330
  1658
        for sake of usage checks.
slouken@1330
  1659
slouken@1330
  1660
*/
slouken@1330
  1661
slouken@1895
  1662
struct malloc_chunk
slouken@1895
  1663
{
slouken@1895
  1664
    size_t prev_foot;           /* Size of previous chunk (if free).  */
slouken@1895
  1665
    size_t head;                /* Size and inuse bits. */
slouken@1895
  1666
    struct malloc_chunk *fd;    /* double links -- used only if free. */
slouken@1895
  1667
    struct malloc_chunk *bk;
slouken@1330
  1668
};
slouken@1330
  1669
slouken@1895
  1670
typedef struct malloc_chunk mchunk;
slouken@1895
  1671
typedef struct malloc_chunk *mchunkptr;
slouken@1895
  1672
typedef struct malloc_chunk *sbinptr;   /* The type of bins of chunks */
slouken@1895
  1673
typedef size_t bindex_t;        /* Described below */
slouken@1895
  1674
typedef unsigned int binmap_t;  /* Described below */
slouken@1895
  1675
typedef unsigned int flag_t;    /* The type of various bit flag sets */
slouken@1330
  1676
slouken@1330
  1677
/* ------------------- Chunks sizes and alignments ----------------------- */
slouken@1330
  1678
slouken@1330
  1679
#define MCHUNK_SIZE         (sizeof(mchunk))
slouken@1330
  1680
slouken@1330
  1681
#if FOOTERS
slouken@1330
  1682
#define CHUNK_OVERHEAD      (TWO_SIZE_T_SIZES)
slouken@1330
  1683
#else /* FOOTERS */
slouken@1330
  1684
#define CHUNK_OVERHEAD      (SIZE_T_SIZE)
slouken@1330
  1685
#endif /* FOOTERS */
slouken@1330
  1686
slouken@1330
  1687
/* MMapped chunks need a second word of overhead ... */
slouken@1330
  1688
#define MMAP_CHUNK_OVERHEAD (TWO_SIZE_T_SIZES)
slouken@1330
  1689
/* ... and additional padding for fake next-chunk at foot */
slouken@1330
  1690
#define MMAP_FOOT_PAD       (FOUR_SIZE_T_SIZES)
slouken@1330
  1691
slouken@1330
  1692
/* The smallest size we can malloc is an aligned minimal chunk */
slouken@1330
  1693
#define MIN_CHUNK_SIZE\
slouken@1330
  1694
  ((MCHUNK_SIZE + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
slouken@1330
  1695
slouken@1330
  1696
/* conversion from malloc headers to user pointers, and back */
slouken@1330
  1697
#define chunk2mem(p)        ((void*)((char*)(p)       + TWO_SIZE_T_SIZES))
slouken@1330
  1698
#define mem2chunk(mem)      ((mchunkptr)((char*)(mem) - TWO_SIZE_T_SIZES))
slouken@1330
  1699
/* chunk associated with aligned address A */
slouken@1330
  1700
#define align_as_chunk(A)   (mchunkptr)((A) + align_offset(chunk2mem(A)))
slouken@1330
  1701
slouken@1330
  1702
/* Bounds on request (not chunk) sizes. */
slouken@1330
  1703
#define MAX_REQUEST         ((-MIN_CHUNK_SIZE) << 2)
slouken@1330
  1704
#define MIN_REQUEST         (MIN_CHUNK_SIZE - CHUNK_OVERHEAD - SIZE_T_ONE)
slouken@1330
  1705
slouken@1330
  1706
/* pad request bytes into a usable size */
slouken@1330
  1707
#define pad_request(req) \
slouken@1330
  1708
   (((req) + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
slouken@1330
  1709
slouken@1330
  1710
/* pad request, checking for minimum (but not maximum) */
slouken@1330
  1711
#define request2size(req) \
slouken@1330
  1712
  (((req) < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(req))
slouken@1330
  1713
slouken@1330
  1714
slouken@1330
  1715
/* ------------------ Operations on head and foot fields ----------------- */
slouken@1330
  1716
slouken@1330
  1717
/*
slouken@1330
  1718
  The head field of a chunk is or'ed with PINUSE_BIT when previous
slouken@1330
  1719
  adjacent chunk in use, and or'ed with CINUSE_BIT if this chunk is in
slouken@1330
  1720
  use. If the chunk was obtained with mmap, the prev_foot field has
slouken@1330
  1721
  IS_MMAPPED_BIT set, otherwise holding the offset of the base of the
slouken@1330
  1722
  mmapped region to the base of the chunk.
slouken@1330
  1723
*/
slouken@1330
  1724
slouken@1330
  1725
#define PINUSE_BIT          (SIZE_T_ONE)
slouken@1330
  1726
#define CINUSE_BIT          (SIZE_T_TWO)
slouken@1330
  1727
#define INUSE_BITS          (PINUSE_BIT|CINUSE_BIT)
slouken@1330
  1728
slouken@1330
  1729
/* Head value for fenceposts */
slouken@1330
  1730
#define FENCEPOST_HEAD      (INUSE_BITS|SIZE_T_SIZE)
slouken@1330
  1731
slouken@1330
  1732
/* extraction of fields from head words */
slouken@1330
  1733
#define cinuse(p)           ((p)->head & CINUSE_BIT)
slouken@1330
  1734
#define pinuse(p)           ((p)->head & PINUSE_BIT)
slouken@1330
  1735
#define chunksize(p)        ((p)->head & ~(INUSE_BITS))
slouken@1330
  1736
slouken@1330
  1737
#define clear_pinuse(p)     ((p)->head &= ~PINUSE_BIT)
slouken@1330
  1738
#define clear_cinuse(p)     ((p)->head &= ~CINUSE_BIT)
slouken@1330
  1739
slouken@1330
  1740
/* Treat space at ptr +/- offset as a chunk */
slouken@1330
  1741
#define chunk_plus_offset(p, s)  ((mchunkptr)(((char*)(p)) + (s)))
slouken@1330
  1742
#define chunk_minus_offset(p, s) ((mchunkptr)(((char*)(p)) - (s)))
slouken@1330
  1743
slouken@1330
  1744
/* Ptr to next or previous physical malloc_chunk. */
slouken@1330
  1745
#define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->head & ~INUSE_BITS)))
slouken@1330
  1746
#define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_foot) ))
slouken@1330
  1747
slouken@1330
  1748
/* extract next chunk's pinuse bit */
slouken@1330
  1749
#define next_pinuse(p)  ((next_chunk(p)->head) & PINUSE_BIT)
slouken@1330
  1750
slouken@1330
  1751
/* Get/set size at footer */
slouken@1330
  1752
#define get_foot(p, s)  (((mchunkptr)((char*)(p) + (s)))->prev_foot)
slouken@1330
  1753
#define set_foot(p, s)  (((mchunkptr)((char*)(p) + (s)))->prev_foot = (s))
slouken@1330
  1754
slouken@1330
  1755
/* Set size, pinuse bit, and foot */
slouken@1330
  1756
#define set_size_and_pinuse_of_free_chunk(p, s)\
slouken@1330
  1757
  ((p)->head = (s|PINUSE_BIT), set_foot(p, s))
slouken@1330
  1758
slouken@1330
  1759
/* Set size, pinuse bit, foot, and clear next pinuse */
slouken@1330
  1760
#define set_free_with_pinuse(p, s, n)\
slouken@1330
  1761
  (clear_pinuse(n), set_size_and_pinuse_of_free_chunk(p, s))
slouken@1330
  1762
slouken@1330
  1763
#define is_mmapped(p)\
slouken@1330
  1764
  (!((p)->head & PINUSE_BIT) && ((p)->prev_foot & IS_MMAPPED_BIT))
slouken@1330
  1765
slouken@1330
  1766
/* Get the internal overhead associated with chunk p */
slouken@1330
  1767
#define overhead_for(p)\
slouken@1330
  1768
 (is_mmapped(p)? MMAP_CHUNK_OVERHEAD : CHUNK_OVERHEAD)
slouken@1330
  1769
slouken@1330
  1770
/* Return true if malloced space is not necessarily cleared */
slouken@1330
  1771
#if MMAP_CLEARS
slouken@1330
  1772
#define calloc_must_clear(p) (!is_mmapped(p))
slouken@1330
  1773
#else /* MMAP_CLEARS */
slouken@1330
  1774
#define calloc_must_clear(p) (1)
slouken@1330
  1775
#endif /* MMAP_CLEARS */
slouken@1330
  1776
slouken@1330
  1777
/* ---------------------- Overlaid data structures ----------------------- */
slouken@1330
  1778
slouken@1330
  1779
/*
slouken@1330
  1780
  When chunks are not in use, they are treated as nodes of either
slouken@1330
  1781
  lists or trees.
slouken@1330
  1782
slouken@1330
  1783
  "Small"  chunks are stored in circular doubly-linked lists, and look
slouken@1330
  1784
  like this:
slouken@1330
  1785
slouken@1330
  1786
    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1787
            |             Size of previous chunk                            |
slouken@1330
  1788
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1789
    `head:' |             Size of chunk, in bytes                         |P|
slouken@1330
  1790
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1791
            |             Forward pointer to next chunk in list             |
slouken@1330
  1792
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1793
            |             Back pointer to previous chunk in list            |
slouken@1330
  1794
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1795
            |             Unused space (may be 0 bytes long)                .
slouken@1330
  1796
            .                                                               .
slouken@1330
  1797
            .                                                               |
slouken@1330
  1798
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1799
    `foot:' |             Size of chunk, in bytes                           |
slouken@1330
  1800
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1801
slouken@1330
  1802
  Larger chunks are kept in a form of bitwise digital trees (aka
slouken@1330
  1803
  tries) keyed on chunksizes.  Because malloc_tree_chunks are only for
slouken@1330
  1804
  free chunks greater than 256 bytes, their size doesn't impose any
slouken@1330
  1805
  constraints on user chunk sizes.  Each node looks like:
slouken@1330
  1806
slouken@1330
  1807
    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1808
            |             Size of previous chunk                            |
slouken@1330
  1809
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1810
    `head:' |             Size of chunk, in bytes                         |P|
slouken@1330
  1811
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1812
            |             Forward pointer to next chunk of same size        |
slouken@1330
  1813
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1814
            |             Back pointer to previous chunk of same size       |
slouken@1330
  1815
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1816
            |             Pointer to left child (child[0])                  |
slouken@1330
  1817
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1818
            |             Pointer to right child (child[1])                 |
slouken@1330
  1819
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1820
            |             Pointer to parent                                 |
slouken@1330
  1821
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1822
            |             bin index of this chunk                           |
slouken@1330
  1823
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1824
            |             Unused space                                      .
slouken@1330
  1825
            .                                                               |
slouken@1330
  1826
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1827
    `foot:' |             Size of chunk, in bytes                           |
slouken@1330
  1828
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
slouken@1330
  1829
slouken@1330
  1830
  Each tree holding treenodes is a tree of unique chunk sizes.  Chunks
slouken@1330
  1831
  of the same size are arranged in a circularly-linked list, with only
slouken@1330
  1832
  the oldest chunk (the next to be used, in our FIFO ordering)
slouken@1330
  1833
  actually in the tree.  (Tree members are distinguished by a non-null
slouken@1330
  1834
  parent pointer.)  If a chunk with the same size an an existing node
slouken@1330
  1835
  is inserted, it is linked off the existing node using pointers that
slouken@1330
  1836
  work in the same way as fd/bk pointers of small chunks.
slouken@1330
  1837
slouken@1330
  1838
  Each tree contains a power of 2 sized range of chunk sizes (the
slouken@1330
  1839
  smallest is 0x100 <= x < 0x180), which is is divided in half at each
slouken@1330
  1840
  tree level, with the chunks in the smaller half of the range (0x100
slouken@1330
  1841
  <= x < 0x140 for the top nose) in the left subtree and the larger
slouken@1330
  1842
  half (0x140 <= x < 0x180) in the right subtree.  This is, of course,
slouken@1330
  1843
  done by inspecting individual bits.
slouken@1330
  1844
slouken@1330
  1845
  Using these rules, each node's left subtree contains all smaller
slouken@1330
  1846
  sizes than its right subtree.  However, the node at the root of each
slouken@1330
  1847
  subtree has no particular ordering relationship to either.  (The
slouken@1330
  1848
  dividing line between the subtree sizes is based on trie relation.)
slouken@1330
  1849
  If we remove the last chunk of a given size from the interior of the
slouken@1330
  1850
  tree, we need to replace it with a leaf node.  The tree ordering
slouken@1330
  1851
  rules permit a node to be replaced by any leaf below it.
slouken@1330
  1852
slouken@1330
  1853
  The smallest chunk in a tree (a common operation in a best-fit
slouken@1330
  1854
  allocator) can be found by walking a path to the leftmost leaf in
slouken@1330
  1855
  the tree.  Unlike a usual binary tree, where we follow left child
slouken@1330
  1856
  pointers until we reach a null, here we follow the right child
slouken@1330
  1857
  pointer any time the left one is null, until we reach a leaf with
slouken@1330
  1858
  both child pointers null. The smallest chunk in the tree will be
slouken@1330
  1859
  somewhere along that path.
slouken@1330
  1860
slouken@1330
  1861
  The worst case number of steps to add, find, or remove a node is
slouken@1330
  1862
  bounded by the number of bits differentiating chunks within
slouken@1330
  1863
  bins. Under current bin calculations, this ranges from 6 up to 21
slouken@1330
  1864
  (for 32 bit sizes) or up to 53 (for 64 bit sizes). The typical case
slouken@1330
  1865
  is of course much better.
slouken@1330
  1866
*/
slouken@1330
  1867
slouken@1895
  1868
struct malloc_tree_chunk
slouken@1895
  1869
{
slouken@1895
  1870
    /* The first four fields must be compatible with malloc_chunk */
slouken@1895
  1871
    size_t prev_foot;
slouken@1895
  1872
    size_t head;
slouken@1895
  1873
    struct malloc_tree_chunk *fd;
slouken@1895
  1874
    struct malloc_tree_chunk *bk;
slouken@1895
  1875
slouken@1895
  1876
    struct malloc_tree_chunk *child[2];
slouken@1895
  1877
    struct malloc_tree_chunk *parent;
slouken@1895
  1878
    bindex_t index;
slouken@1330
  1879
};
slouken@1330
  1880
slouken@1895
  1881
typedef struct malloc_tree_chunk tchunk;
slouken@1895
  1882
typedef struct malloc_tree_chunk *tchunkptr;
slouken@1895
  1883
typedef struct malloc_tree_chunk *tbinptr;      /* The type of bins of trees */
slouken@1330
  1884
slouken@1330
  1885
/* A little helper macro for trees */
slouken@1330
  1886
#define leftmost_child(t) ((t)->child[0] != 0? (t)->child[0] : (t)->child[1])
slouken@1330
  1887
slouken@1330
  1888
/* ----------------------------- Segments -------------------------------- */
slouken@1330
  1889
slouken@1330
  1890
/*
slouken@1330
  1891
  Each malloc space may include non-contiguous segments, held in a
slouken@1330
  1892
  list headed by an embedded malloc_segment record representing the
slouken@1330
  1893
  top-most space. Segments also include flags holding properties of
slouken@1330
  1894
  the space. Large chunks that are directly allocated by mmap are not
slouken@1330
  1895
  included in this list. They are instead independently created and
slouken@1330
  1896
  destroyed without otherwise keeping track of them.
slouken@1330
  1897
slouken@1330
  1898
  Segment management mainly comes into play for spaces allocated by
slouken@1330
  1899
  MMAP.  Any call to MMAP might or might not return memory that is
slouken@1330
  1900
  adjacent to an existing segment.  MORECORE normally contiguously
slouken@1330
  1901
  extends the current space, so this space is almost always adjacent,
slouken@1330
  1902
  which is simpler and faster to deal with. (This is why MORECORE is
slouken@1330
  1903
  used preferentially to MMAP when both are available -- see
slouken@1330
  1904
  sys_alloc.)  When allocating using MMAP, we don't use any of the
slouken@1330
  1905
  hinting mechanisms (inconsistently) supported in various
slouken@1330
  1906
  implementations of unix mmap, or distinguish reserving from
slouken@1330
  1907
  committing memory. Instead, we just ask for space, and exploit
slouken@1330
  1908
  contiguity when we get it.  It is probably possible to do
slouken@1330
  1909
  better than this on some systems, but no general scheme seems
slouken@1330
  1910
  to be significantly better.
slouken@1330
  1911
slouken@1330
  1912
  Management entails a simpler variant of the consolidation scheme
slouken@1330
  1913
  used for chunks to reduce fragmentation -- new adjacent memory is
slouken@1330
  1914
  normally prepended or appended to an existing segment. However,
slouken@1330
  1915
  there are limitations compared to chunk consolidation that mostly
slouken@1330
  1916
  reflect the fact that segment processing is relatively infrequent
slouken@1330
  1917
  (occurring only when getting memory from system) and that we
slouken@1330
  1918
  don't expect to have huge numbers of segments:
slouken@1330
  1919
slouken@1330
  1920
  * Segments are not indexed, so traversal requires linear scans.  (It
slouken@1330
  1921
    would be possible to index these, but is not worth the extra
slouken@1330
  1922
    overhead and complexity for most programs on most platforms.)
slouken@1330
  1923
  * New segments are only appended to old ones when holding top-most
slouken@1330
  1924
    memory; if they cannot be prepended to others, they are held in
slouken@1330
  1925
    different segments.
slouken@1330
  1926
slouken@1330
  1927
  Except for the top-most segment of an mstate, each segment record
slouken@1330
  1928
  is kept at the tail of its segment. Segments are added by pushing
slouken@1330
  1929
  segment records onto the list headed by &mstate.seg for the
slouken@1330
  1930
  containing mstate.
slouken@1330
  1931
slouken@1330
  1932
  Segment flags control allocation/merge/deallocation policies:
slouken@1330
  1933
  * If EXTERN_BIT set, then we did not allocate this segment,
slouken@1330
  1934
    and so should not try to deallocate or merge with others.
slouken@1330
  1935
    (This currently holds only for the initial segment passed
slouken@1330
  1936
    into create_mspace_with_base.)
slouken@1330
  1937
  * If IS_MMAPPED_BIT set, the segment may be merged with
slouken@1330
  1938
    other surrounding mmapped segments and trimmed/de-allocated
slouken@1330
  1939
    using munmap.
slouken@1330
  1940
  * If neither bit is set, then the segment was obtained using
slouken@1330
  1941
    MORECORE so can be merged with surrounding MORECORE'd segments
slouken@1330
  1942
    and deallocated/trimmed using MORECORE with negative arguments.
slouken@1330
  1943
*/
slouken@1330
  1944
slouken@1895
  1945
struct malloc_segment
slouken@1895
  1946
{
slouken@1895
  1947
    char *base;                 /* base address */
slouken@1895
  1948
    size_t size;                /* allocated size */
slouken@1895
  1949
    struct malloc_segment *next;        /* ptr to next segment */
slouken@1895
  1950
    flag_t sflags;              /* mmap and extern flag */
slouken@1330
  1951
};
slouken@1330
  1952
slouken@1330
  1953
#define is_mmapped_segment(S)  ((S)->sflags & IS_MMAPPED_BIT)
slouken@1330
  1954
#define is_extern_segment(S)   ((S)->sflags & EXTERN_BIT)
slouken@1330
  1955
slouken@1895
  1956
typedef struct malloc_segment msegment;
slouken@1895
  1957
typedef struct malloc_segment *msegmentptr;
slouken@1330
  1958
slouken@1330
  1959
/* ---------------------------- malloc_state ----------------------------- */
slouken@1330
  1960
slouken@1330
  1961
/*
slouken@1330
  1962
   A malloc_state holds all of the bookkeeping for a space.
slouken@1330
  1963
   The main fields are:
slouken@1330
  1964
slouken@1330
  1965
  Top
slouken@1330
  1966
    The topmost chunk of the currently active segment. Its size is
slouken@1330
  1967
    cached in topsize.  The actual size of topmost space is
slouken@1330
  1968
    topsize+TOP_FOOT_SIZE, which includes space reserved for adding
slouken@1330
  1969
    fenceposts and segment records if necessary when getting more
slouken@1330
  1970
    space from the system.  The size at which to autotrim top is
slouken@1330
  1971
    cached from mparams in trim_check, except that it is disabled if
slouken@1330
  1972
    an autotrim fails.
slouken@1330
  1973
slouken@1330
  1974
  Designated victim (dv)
slouken@1330
  1975
    This is the preferred chunk for servicing small requests that
slouken@1330
  1976
    don't have exact fits.  It is normally the chunk split off most
slouken@1330
  1977
    recently to service another small request.  Its size is cached in
slouken@1330
  1978
    dvsize. The link fields of this chunk are not maintained since it
slouken@1330
  1979
    is not kept in a bin.
slouken@1330
  1980
slouken@1330
  1981
  SmallBins
slouken@1330
  1982
    An array of bin headers for free chunks.  These bins hold chunks
slouken@1330
  1983
    with sizes less than MIN_LARGE_SIZE bytes. Each bin contains
slouken@1330
  1984
    chunks of all the same size, spaced 8 bytes apart.  To simplify
slouken@1330
  1985
    use in double-linked lists, each bin header acts as a malloc_chunk
slouken@1330
  1986
    pointing to the real first node, if it exists (else pointing to
slouken@1330
  1987
    itself).  This avoids special-casing for headers.  But to avoid
slouken@1330
  1988
    waste, we allocate only the fd/bk pointers of bins, and then use
slouken@1330
  1989
    repositioning tricks to treat these as the fields of a chunk.
slouken@1330
  1990
slouken@1330
  1991
  TreeBins
slouken@1330
  1992
    Treebins are pointers to the roots of trees holding a range of
slouken@1330
  1993
    sizes. There are 2 equally spaced treebins for each power of two
slouken@1330
  1994
    from TREE_SHIFT to TREE_SHIFT+16. The last bin holds anything
slouken@1330
  1995
    larger.
slouken@1330
  1996
slouken@1330
  1997
  Bin maps
slouken@1330
  1998
    There is one bit map for small bins ("smallmap") and one for
slouken@1330
  1999
    treebins ("treemap).  Each bin sets its bit when non-empty, and
slouken@1330
  2000
    clears the bit when empty.  Bit operations are then used to avoid
slouken@1330
  2001
    bin-by-bin searching -- nearly all "search" is done without ever
slouken@1330
  2002
    looking at bins that won't be selected.  The bit maps
slouken@1330
  2003
    conservatively use 32 bits per map word, even if on 64bit system.
slouken@1330
  2004
    For a good description of some of the bit-based techniques used
slouken@1330
  2005
    here, see Henry S. Warren Jr's book "Hacker's Delight" (and
slouken@1330
  2006
    supplement at http://hackersdelight.org/). Many of these are
slouken@1330
  2007
    intended to reduce the branchiness of paths through malloc etc, as
slouken@1330
  2008
    well as to reduce the number of memory locations read or written.
slouken@1330
  2009
slouken@1330
  2010
  Segments
slouken@1330
  2011
    A list of segments headed by an embedded malloc_segment record
slouken@1330
  2012
    representing the initial space.
slouken@1330
  2013
slouken@1330
  2014
  Address check support
slouken@1330
  2015
    The least_addr field is the least address ever obtained from
slouken@1330
  2016
    MORECORE or MMAP. Attempted frees and reallocs of any address less
slouken@1330
  2017
    than this are trapped (unless INSECURE is defined).
slouken@1330
  2018
slouken@1330
  2019
  Magic tag
slouken@1330
  2020
    A cross-check field that should always hold same value as mparams.magic.
slouken@1330
  2021
slouken@1330
  2022
  Flags
slouken@1330
  2023
    Bits recording whether to use MMAP, locks, or contiguous MORECORE
slouken@1330
  2024
slouken@1330
  2025
  Statistics
slouken@1330
  2026
    Each space keeps track of current and maximum system memory
slouken@1330
  2027
    obtained via MORECORE or MMAP.
slouken@1330
  2028
slouken@1330
  2029
  Locking
slouken@1330
  2030
    If USE_LOCKS is defined, the "mutex" lock is acquired and released
slouken@1330
  2031
    around every public call using this mspace.
slouken@1330
  2032
*/
slouken@1330
  2033
slouken@1330
  2034
/* Bin types, widths and sizes */
slouken@1330
  2035
#define NSMALLBINS        (32U)
slouken@1330
  2036
#define NTREEBINS         (32U)
slouken@1330
  2037
#define SMALLBIN_SHIFT    (3U)
slouken@1330
  2038
#define SMALLBIN_WIDTH    (SIZE_T_ONE << SMALLBIN_SHIFT)
slouken@1330
  2039
#define TREEBIN_SHIFT     (8U)
slouken@1330
  2040
#define MIN_LARGE_SIZE    (SIZE_T_ONE << TREEBIN_SHIFT)
slouken@1330
  2041
#define MAX_SMALL_SIZE    (MIN_LARGE_SIZE - SIZE_T_ONE)
slouken@1330
  2042
#define MAX_SMALL_REQUEST (MAX_SMALL_SIZE - CHUNK_ALIGN_MASK - CHUNK_OVERHEAD)
slouken@1330
  2043
slouken@1895
  2044
struct malloc_state
slouken@1895
  2045
{
slouken@1895
  2046
    binmap_t smallmap;
slouken@1895
  2047
    binmap_t treemap;
slouken@1895
  2048
    size_t dvsize;
slouken@1895
  2049
    size_t topsize;
slouken@1895
  2050
    char *least_addr;
slouken@1895
  2051
    mchunkptr dv;
slouken@1895
  2052
    mchunkptr top;
slouken@1895
  2053
    size_t trim_check;
slouken@1895
  2054
    size_t magic;
slouken@1895
  2055
    mchunkptr smallbins[(NSMALLBINS + 1) * 2];
slouken@1895
  2056
    tbinptr treebins[NTREEBINS];
slouken@1895
  2057
    size_t footprint;
slouken@1895
  2058
    size_t max_footprint;
slouken@1895
  2059
    flag_t mflags;
slouken@1330
  2060
#if USE_LOCKS
slouken@1895
  2061
    MLOCK_T mutex;              /* locate lock among fields that rarely change */
slouken@1895
  2062
#endif                          /* USE_LOCKS */
slouken@1895
  2063
    msegment seg;
slouken@1330
  2064
};
slouken@1330
  2065
slouken@1895
  2066
typedef struct malloc_state *mstate;
slouken@1330
  2067
slouken@1330
  2068
/* ------------- Global malloc_state and malloc_params ------------------- */
slouken@1330
  2069
slouken@1330
  2070
/*
slouken@1330
  2071
  malloc_params holds global properties, including those that can be
slouken@1330
  2072
  dynamically set using mallopt. There is a single instance, mparams,
slouken@1330
  2073
  initialized in init_mparams.
slouken@1330
  2074
*/
slouken@1330
  2075
slouken@1895
  2076
struct malloc_params
slouken@1895
  2077
{
slouken@1895
  2078
    size_t magic;
slouken@1895
  2079
    size_t page_size;
slouken@1895
  2080
    size_t granularity;
slouken@1895
  2081
    size_t mmap_threshold;
slouken@1895
  2082
    size_t trim_threshold;
slouken@1895
  2083
    flag_t default_mflags;
slouken@1330
  2084
};
slouken@1330
  2085
slouken@1330
  2086
static struct malloc_params mparams;
slouken@1330
  2087
slouken@1330
  2088
/* The global malloc_state used for all non-"mspace" calls */
slouken@1330
  2089
static struct malloc_state _gm_;
slouken@1330
  2090
#define gm                 (&_gm_)
slouken@1330
  2091
#define is_global(M)       ((M) == &_gm_)
slouken@1330
  2092
#define is_initialized(M)  ((M)->top != 0)
slouken@1330
  2093
slouken@1330
  2094
/* -------------------------- system alloc setup ------------------------- */
slouken@1330
  2095
slouken@1330
  2096
/* Operations on mflags */
slouken@1330
  2097
slouken@1330
  2098
#define use_lock(M)           ((M)->mflags &   USE_LOCK_BIT)
slouken@1330
  2099
#define enable_lock(M)        ((M)->mflags |=  USE_LOCK_BIT)
slouken@1330
  2100
#define disable_lock(M)       ((M)->mflags &= ~USE_LOCK_BIT)
slouken@1330
  2101
slouken@1330
  2102
#define use_mmap(M)           ((M)->mflags &   USE_MMAP_BIT)
slouken@1330
  2103
#define enable_mmap(M)        ((M)->mflags |=  USE_MMAP_BIT)
slouken@1330
  2104
#define disable_mmap(M)       ((M)->mflags &= ~USE_MMAP_BIT)
slouken@1330
  2105
slouken@1330
  2106
#define use_noncontiguous(M)  ((M)->mflags &   USE_NONCONTIGUOUS_BIT)
slouken@1330
  2107
#define disable_contiguous(M) ((M)->mflags |=  USE_NONCONTIGUOUS_BIT)
slouken@1330
  2108
slouken@1330
  2109
#define set_lock(M,L)\
slouken@1330
  2110
 ((M)->mflags = (L)?\
slouken@1330
  2111
  ((M)->mflags | USE_LOCK_BIT) :\
slouken@1330
  2112
  ((M)->mflags & ~USE_LOCK_BIT))
slouken@1330
  2113
slouken@1330
  2114
/* page-align a size */
slouken@1330
  2115
#define page_align(S)\
slouken@1330
  2116
 (((S) + (mparams.page_size)) & ~(mparams.page_size - SIZE_T_ONE))
slouken@1330
  2117
slouken@1330
  2118
/* granularity-align a size */
slouken@1330
  2119
#define granularity_align(S)\
slouken@1330
  2120
  (((S) + (mparams.granularity)) & ~(mparams.granularity - SIZE_T_ONE))
slouken@1330
  2121
slouken@1330
  2122
#define is_page_aligned(S)\
slouken@1330
  2123
   (((size_t)(S) & (mparams.page_size - SIZE_T_ONE)) == 0)
slouken@1330
  2124
#define is_granularity_aligned(S)\
slouken@1330
  2125
   (((size_t)(S) & (mparams.granularity - SIZE_T_ONE)) == 0)
slouken@1330
  2126
slouken@1330
  2127
/*  True if segment S holds address A */
slouken@1330
  2128
#define segment_holds(S, A)\
slouken@1330
  2129
  ((char*)(A) >= S->base && (char*)(A) < S->base + S->size)
slouken@1330
  2130
slouken@1330
  2131
/* Return segment holding given address */
slouken@1895
  2132
static msegmentptr
slouken@1895
  2133
segment_holding(mstate m, char *addr)
slouken@1895
  2134
{
slouken@1895
  2135
    msegmentptr sp = &m->seg;
slouken@1895
  2136
    for (;;) {
slouken@1895
  2137
        if (addr >= sp->base && addr < sp->base + sp->size)
slouken@1895
  2138
            return sp;
slouken@1895
  2139
        if ((sp = sp->next) == 0)
slouken@1895
  2140
            return 0;
slouken@1895
  2141
    }
slouken@1330
  2142
}
slouken@1330
  2143
slouken@1330
  2144
/* Return true if segment contains a segment link */
slouken@1895
  2145
static int
slouken@1895
  2146
has_segment_link(mstate m, msegmentptr ss)
slouken@1895
  2147
{
slouken@1895
  2148
    msegmentptr sp = &m->seg;
slouken@1895
  2149
    for (;;) {
slouken@1895
  2150
        if ((char *) sp >= ss->base && (char *) sp < ss->base + ss->size)
slouken@1895
  2151
            return 1;
slouken@1895
  2152
        if ((sp = sp->next) == 0)
slouken@1895
  2153
            return 0;
slouken@1895
  2154
    }
slouken@1330
  2155
}
slouken@1330
  2156
slouken@1330
  2157
#ifndef MORECORE_CANNOT_TRIM
slouken@1330
  2158
#define should_trim(M,s)  ((s) > (M)->trim_check)
slouken@1895
  2159
#else /* MORECORE_CANNOT_TRIM */
slouken@1330
  2160
#define should_trim(M,s)  (0)
slouken@1330
  2161
#endif /* MORECORE_CANNOT_TRIM */
slouken@1330
  2162
slouken@1330
  2163
/*
slouken@1330
  2164
  TOP_FOOT_SIZE is padding at the end of a segment, including space
slouken@1330
  2165
  that may be needed to place segment records and fenceposts when new
slouken@1330
  2166
  noncontiguous segments are added.
slouken@1330
  2167
*/
slouken@1330
  2168
#define TOP_FOOT_SIZE\
slouken@1330
  2169
  (align_offset(chunk2mem(0))+pad_request(sizeof(struct malloc_segment))+MIN_CHUNK_SIZE)
slouken@1330
  2170
slouken@1330
  2171
slouken@1330
  2172
/* -------------------------------  Hooks -------------------------------- */
slouken@1330
  2173
slouken@1330
  2174
/*
slouken@1330
  2175
  PREACTION should be defined to return 0 on success, and nonzero on
slouken@1330
  2176
  failure. If you are not using locking, you can redefine these to do
slouken@1330
  2177
  anything you like.
slouken@1330
  2178
*/
slouken@1330
  2179
slouken@1330
  2180
#if USE_LOCKS
slouken@1330
  2181
slouken@1330
  2182
/* Ensure locks are initialized */
slouken@1330
  2183
#define GLOBALLY_INITIALIZE() (mparams.page_size == 0 && init_mparams())
slouken@1330
  2184
slouken@1330
  2185
#define PREACTION(M)  ((GLOBALLY_INITIALIZE() || use_lock(M))? ACQUIRE_LOCK(&(M)->mutex) : 0)
slouken@1330
  2186
#define POSTACTION(M) { if (use_lock(M)) RELEASE_LOCK(&(M)->mutex); }
slouken@1330
  2187
#else /* USE_LOCKS */
slouken@1330
  2188
slouken@1330
  2189
#ifndef PREACTION
slouken@1330
  2190
#define PREACTION(M) (0)
slouken@1895
  2191
#endif /* PREACTION */
slouken@1330
  2192
slouken@1330
  2193
#ifndef POSTACTION
slouken@1330
  2194
#define POSTACTION(M)
slouken@1895
  2195
#endif /* POSTACTION */
slouken@1330
  2196
slouken@1330
  2197
#endif /* USE_LOCKS */
slouken@1330
  2198
slouken@1330
  2199
/*
slouken@1330
  2200
  CORRUPTION_ERROR_ACTION is triggered upon detected bad addresses.
slouken@1330
  2201
  USAGE_ERROR_ACTION is triggered on detected bad frees and
slouken@1330
  2202
  reallocs. The argument p is an address that might have triggered the
slouken@1330
  2203
  fault. It is ignored by the two predefined actions, but might be
slouken@1330
  2204
  useful in custom actions that try to help diagnose errors.
slouken@1330
  2205
*/
slouken@1330
  2206
slouken@1330
  2207
#if PROCEED_ON_ERROR
slouken@1330
  2208
slouken@1330
  2209
/* A count of the number of corruption errors causing resets */
slouken@1330
  2210
int malloc_corruption_error_count;
slouken@1330
  2211
slouken@1330
  2212
/* default corruption action */
slouken@1330
  2213
static void reset_on_error(mstate m);
slouken@1330
  2214
slouken@1330
  2215
#define CORRUPTION_ERROR_ACTION(m)  reset_on_error(m)
slouken@1330
  2216
#define USAGE_ERROR_ACTION(m, p)
slouken@1330
  2217
slouken@1330
  2218
#else /* PROCEED_ON_ERROR */
slouken@1330
  2219
slouken@1330
  2220
#ifndef CORRUPTION_ERROR_ACTION
slouken@1330
  2221
#define CORRUPTION_ERROR_ACTION(m) ABORT
slouken@1330
  2222
#endif /* CORRUPTION_ERROR_ACTION */
slouken@1330
  2223
slouken@1330
  2224
#ifndef USAGE_ERROR_ACTION
slouken@1330
  2225
#define USAGE_ERROR_ACTION(m,p) ABORT
slouken@1330
  2226
#endif /* USAGE_ERROR_ACTION */
slouken@1330
  2227
slouken@1330
  2228
#endif /* PROCEED_ON_ERROR */
slouken@1330
  2229
slouken@1330
  2230
/* -------------------------- Debugging setup ---------------------------- */
slouken@1330
  2231
slouken@1330
  2232
#if ! DEBUG
slouken@1330
  2233
slouken@1330
  2234
#define check_free_chunk(M,P)
slouken@1330
  2235
#define check_inuse_chunk(M,P)
slouken@1330
  2236
#define check_malloced_chunk(M,P,N)
slouken@1330
  2237
#define check_mmapped_chunk(M,P)
slouken@1330
  2238
#define check_malloc_state(M)
slouken@1330
  2239
#define check_top_chunk(M,P)
slouken@1330
  2240
slouken@1330
  2241
#else /* DEBUG */
slouken@1330
  2242
#define check_free_chunk(M,P)       do_check_free_chunk(M,P)
slouken@1330
  2243
#define check_inuse_chunk(M,P)      do_check_inuse_chunk(M,P)
slouken@1330
  2244
#define check_top_chunk(M,P)        do_check_top_chunk(M,P)
slouken@1330
  2245
#define check_malloced_chunk(M,P,N) do_check_malloced_chunk(M,P,N)
slouken@1330
  2246
#define check_mmapped_chunk(M,P)    do_check_mmapped_chunk(M,P)
slouken@1330
  2247
#define check_malloc_state(M)       do_check_malloc_state(M)
slouken@1330
  2248
slouken@1895
  2249
static void do_check_any_chunk(mstate m, mchunkptr p);
slouken@1895
  2250
static void do_check_top_chunk(mstate m, mchunkptr p);
slouken@1895
  2251
static void do_check_mmapped_chunk(mstate m, mchunkptr p);
slouken@1895
  2252
static void do_check_inuse_chunk(mstate m, mchunkptr p);
slouken@1895
  2253
static void do_check_free_chunk(mstate m, mchunkptr p);
slouken@1895
  2254
static void do_check_malloced_chunk(mstate m, void *mem, size_t s);
slouken@1895
  2255
static void do_check_tree(mstate m, tchunkptr t);
slouken@1895
  2256
static void do_check_treebin(mstate m, bindex_t i);
slouken@1895
  2257
static void do_check_smallbin(mstate m, bindex_t i);
slouken@1895
  2258
static void do_check_malloc_state(mstate m);
slouken@1895
  2259
static int bin_find(mstate m, mchunkptr x);
slouken@1330
  2260
static size_t traverse_and_check(mstate m);
slouken@1330
  2261
#endif /* DEBUG */
slouken@1330
  2262
slouken@1330
  2263
/* ---------------------------- Indexing Bins ---------------------------- */
slouken@1330
  2264
slouken@1330
  2265
#define is_small(s)         (((s) >> SMALLBIN_SHIFT) < NSMALLBINS)
slouken@1330
  2266
#define small_index(s)      ((s)  >> SMALLBIN_SHIFT)
slouken@1330
  2267
#define small_index2size(i) ((i)  << SMALLBIN_SHIFT)
slouken@1330
  2268
#define MIN_SMALL_INDEX     (small_index(MIN_CHUNK_SIZE))
slouken@1330
  2269
slouken@1330
  2270
/* addressing by index. See above about smallbin repositioning */
slouken@1330
  2271
#define smallbin_at(M, i)   ((sbinptr)((char*)&((M)->smallbins[(i)<<1])))
slouken@1330
  2272
#define treebin_at(M,i)     (&((M)->treebins[i]))
slouken@1330
  2273
slouken@1330
  2274
/* assign tree index for size S to variable I */
slouken@1330
  2275
#if defined(__GNUC__) && defined(i386)
slouken@1330
  2276
#define compute_tree_index(S, I)\
slouken@1330
  2277
{\
slouken@1330
  2278
  size_t X = S >> TREEBIN_SHIFT;\
slouken@1330
  2279
  if (X == 0)\
slouken@1330
  2280
    I = 0;\
slouken@1330
  2281
  else if (X > 0xFFFF)\
slouken@1330
  2282
    I = NTREEBINS-1;\
slouken@1330
  2283
  else {\
slouken@1330
  2284
    unsigned int K;\
slouken@1330
  2285
    __asm__("bsrl %1,%0\n\t" : "=r" (K) : "rm"  (X));\
slouken@1330
  2286
    I =  (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
slouken@1330
  2287
  }\
slouken@1330
  2288
}
slouken@1330
  2289
#else /* GNUC */
slouken@1330
  2290
#define compute_tree_index(S, I)\
slouken@1330
  2291
{\
slouken@1330
  2292
  size_t X = S >> TREEBIN_SHIFT;\
slouken@1330
  2293
  if (X == 0)\
slouken@1330
  2294
    I = 0;\
slouken@1330
  2295
  else if (X > 0xFFFF)\
slouken@1330
  2296
    I = NTREEBINS-1;\
slouken@1330
  2297
  else {\
slouken@1330
  2298
    unsigned int Y = (unsigned int)X;\
slouken@1330
  2299
    unsigned int N = ((Y - 0x100) >> 16) & 8;\
slouken@1330
  2300
    unsigned int K = (((Y <<= N) - 0x1000) >> 16) & 4;\
slouken@1330
  2301
    N += K;\
slouken@1330
  2302
    N += K = (((Y <<= K) - 0x4000) >> 16) & 2;\
slouken@1330
  2303
    K = 14 - N + ((Y <<= K) >> 15);\
slouken@1330
  2304
    I = (K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1));\
slouken@1330
  2305
  }\
slouken@1330
  2306
}
slouken@1330
  2307
#endif /* GNUC */
slouken@1330
  2308
slouken@1330
  2309
/* Bit representing maximum resolved size in a treebin at i */
slouken@1330
  2310
#define bit_for_tree_index(i) \
slouken@1330
  2311
   (i == NTREEBINS-1)? (SIZE_T_BITSIZE-1) : (((i) >> 1) + TREEBIN_SHIFT - 2)
slouken@1330
  2312
slouken@1330
  2313
/* Shift placing maximum resolved bit in a treebin at i as sign bit */
slouken@1330
  2314
#define leftshift_for_tree_index(i) \
slouken@1330
  2315
   ((i == NTREEBINS-1)? 0 : \
slouken@1330
  2316
    ((SIZE_T_BITSIZE-SIZE_T_ONE) - (((i) >> 1) + TREEBIN_SHIFT - 2)))
slouken@1330
  2317
slouken@1330
  2318
/* The size of the smallest chunk held in bin with index i */
slouken@1330
  2319
#define minsize_for_tree_index(i) \
slouken@1330
  2320
   ((SIZE_T_ONE << (((i) >> 1) + TREEBIN_SHIFT)) |  \
slouken@1330
  2321
   (((size_t)((i) & SIZE_T_ONE)) << (((i) >> 1) + TREEBIN_SHIFT - 1)))
slouken@1330
  2322
slouken@1330
  2323
slouken@1330
  2324
/* ------------------------ Operations on bin maps ----------------------- */
slouken@1330
  2325
slouken@1330
  2326
/* bit corresponding to given index */
slouken@1330
  2327
#define idx2bit(i)              ((binmap_t)(1) << (i))
slouken@1330
  2328
slouken@1330
  2329
/* Mark/Clear bits with given index */
slouken@1330
  2330
#define mark_smallmap(M,i)      ((M)->smallmap |=  idx2bit(i))
slouken@1330
  2331
#define clear_smallmap(M,i)     ((M)->smallmap &= ~idx2bit(i))
slouken@1330
  2332
#define smallmap_is_marked(M,i) ((M)->smallmap &   idx2bit(i))
slouken@1330
  2333
slouken@1330
  2334
#define mark_treemap(M,i)       ((M)->treemap  |=  idx2bit(i))
slouken@1330
  2335
#define clear_treemap(M,i)      ((M)->treemap  &= ~idx2bit(i))
slouken@1330
  2336
#define treemap_is_marked(M,i)  ((M)->treemap  &   idx2bit(i))
slouken@1330
  2337
slouken@1330
  2338
/* index corresponding to given bit */
slouken@1330
  2339
slouken@1330
  2340
#if defined(__GNUC__) && defined(i386)
slouken@1330
  2341
#define compute_bit2idx(X, I)\
slouken@1330
  2342
{\
slouken@1330
  2343
  unsigned int J;\
slouken@1330
  2344
  __asm__("bsfl %1,%0\n\t" : "=r" (J) : "rm" (X));\
slouken@1330
  2345
  I = (bindex_t)J;\
slouken@1330
  2346
}
slouken@1330
  2347
slouken@1330
  2348
#else /* GNUC */
slouken@1330
  2349
#if  USE_BUILTIN_FFS
slouken@1330
  2350
#define compute_bit2idx(X, I) I = ffs(X)-1
slouken@1330
  2351
slouken@1330
  2352
#else /* USE_BUILTIN_FFS */
slouken@1330
  2353
#define compute_bit2idx(X, I)\
slouken@1330
  2354
{\
slouken@1330
  2355
  unsigned int Y = X - 1;\
slouken@1330
  2356
  unsigned int K = Y >> (16-4) & 16;\
slouken@1330
  2357
  unsigned int N = K;        Y >>= K;\
slouken@1330
  2358
  N += K = Y >> (8-3) &  8;  Y >>= K;\
slouken@1330
  2359
  N += K = Y >> (4-2) &  4;  Y >>= K;\
slouken@1330
  2360
  N += K = Y >> (2-1) &  2;  Y >>= K;\
slouken@1330
  2361
  N += K = Y >> (1-0) &  1;  Y >>= K;\
slouken@1330
  2362
  I = (bindex_t)(N + Y);\
slouken@1330
  2363
}
slouken@1330
  2364
#endif /* USE_BUILTIN_FFS */
slouken@1330
  2365
#endif /* GNUC */
slouken@1330
  2366
slouken@1330
  2367
/* isolate the least set bit of a bitmap */
slouken@1330
  2368
#define least_bit(x)         ((x) & -(x))
slouken@1330
  2369
slouken@1330
  2370
/* mask with all bits to left of least bit of x on */
slouken@1330
  2371
#define left_bits(x)         ((x<<1) | -(x<<1))
slouken@1330
  2372
slouken@1330
  2373
/* mask with all bits to left of or equal to least bit of x on */
slouken@1330
  2374
#define same_or_left_bits(x) ((x) | -(x))
slouken@1330
  2375
slouken@1330
  2376
slouken@1330
  2377
/* ----------------------- Runtime Check Support ------------------------- */
slouken@1330
  2378
slouken@1330
  2379
/*
slouken@1330
  2380
  For security, the main invariant is that malloc/free/etc never
slouken@1330
  2381
  writes to a static address other than malloc_state, unless static
slouken@1330
  2382
  malloc_state itself has been corrupted, which cannot occur via
slouken@1330
  2383
  malloc (because of these checks). In essence this means that we
slouken@1330
  2384
  believe all pointers, sizes, maps etc held in malloc_state, but
slouken@1330
  2385
  check all of those linked or offsetted from other embedded data
slouken@1330
  2386
  structures.  These checks are interspersed with main code in a way
slouken@1330
  2387
  that tends to minimize their run-time cost.
slouken@1330
  2388
slouken@1330
  2389
  When FOOTERS is defined, in addition to range checking, we also
slouken@1330
  2390
  verify footer fields of inuse chunks, which can be used guarantee
slouken@1330
  2391
  that the mstate controlling malloc/free is intact.  This is a
slouken@1330
  2392
  streamlined version of the approach described by William Robertson
slouken@1330
  2393
  et al in "Run-time Detection of Heap-based Overflows" LISA'03
slouken@1330
  2394
  http://www.usenix.org/events/lisa03/tech/robertson.html The footer
slouken@1330
  2395
  of an inuse chunk holds the xor of its mstate and a random seed,
slouken@1330
  2396
  that is checked upon calls to free() and realloc().  This is
slouken@1330
  2397
  (probablistically) unguessable from outside the program, but can be
slouken@1330
  2398
  computed by any code successfully malloc'ing any chunk, so does not
slouken@1330
  2399
  itself provide protection against code that has already broken
slouken@1330
  2400
  security through some other means.  Unlike Robertson et al, we
slouken@1330
  2401
  always dynamically check addresses of all offset chunks (previous,
slouken@1330
  2402
  next, etc). This turns out to be cheaper than relying on hashes.
slouken@1330
  2403
*/
slouken@1330
  2404
slouken@1330
  2405
#if !INSECURE
slouken@1330
  2406
/* Check if address a is at least as high as any from MORECORE or MMAP */
slouken@1330
  2407
#define ok_address(M, a) ((char*)(a) >= (M)->least_addr)
slouken@1330
  2408
/* Check if address of next chunk n is higher than base chunk p */
slouken@1330
  2409
#define ok_next(p, n)    ((char*)(p) < (char*)(n))
slouken@1330
  2410
/* Check if p has its cinuse bit on */
slouken@1330
  2411
#define ok_cinuse(p)     cinuse(p)
slouken@1330
  2412
/* Check if p has its pinuse bit on */
slouken@1330
  2413
#define ok_pinuse(p)     pinuse(p)
slouken@1330
  2414
slouken@1330
  2415
#else /* !INSECURE */
slouken@1330
  2416
#define ok_address(M, a) (1)
slouken@1330
  2417
#define ok_next(b, n)    (1)
slouken@1330
  2418
#define ok_cinuse(p)     (1)
slouken@1330
  2419
#define ok_pinuse(p)     (1)
slouken@1330
  2420
#endif /* !INSECURE */
slouken@1330
  2421
slouken@1330
  2422
#if (FOOTERS && !INSECURE)
slouken@1330
  2423
/* Check if (alleged) mstate m has expected magic field */
slouken@1330
  2424
#define ok_magic(M)      ((M)->magic == mparams.magic)
slouken@1895
  2425
#else /* (FOOTERS && !INSECURE) */
slouken@1330
  2426
#define ok_magic(M)      (1)
slouken@1330
  2427
#endif /* (FOOTERS && !INSECURE) */
slouken@1330
  2428
slouken@1330
  2429
slouken@1330
  2430
/* In gcc, use __builtin_expect to minimize impact of checks */
slouken@1330
  2431
#if !INSECURE
slouken@1330
  2432
#if defined(__GNUC__) && __GNUC__ >= 3
slouken@1330
  2433
#define RTCHECK(e)  __builtin_expect(e, 1)
slouken@1330
  2434
#else /* GNUC */
slouken@1330
  2435
#define RTCHECK(e)  (e)
slouken@1330
  2436
#endif /* GNUC */
slouken@1330
  2437
#else /* !INSECURE */
slouken@1330
  2438
#define RTCHECK(e)  (1)
slouken@1330
  2439
#endif /* !INSECURE */
slouken@1330
  2440
slouken@1330
  2441
/* macros to set up inuse chunks with or without footers */
slouken@1330
  2442
slouken@1330
  2443
#if !FOOTERS
slouken@1330
  2444
slouken@1330
  2445
#define mark_inuse_foot(M,p,s)
slouken@1330
  2446
slouken@1330
  2447
/* Set cinuse bit and pinuse bit of next chunk */
slouken@1330
  2448
#define set_inuse(M,p,s)\
slouken@1330
  2449
  ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
slouken@1330
  2450
  ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
slouken@1330
  2451
slouken@1330
  2452
/* Set cinuse and pinuse of this chunk and pinuse of next chunk */
slouken@1330
  2453
#define set_inuse_and_pinuse(M,p,s)\
slouken@1330
  2454
  ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
slouken@1330
  2455
  ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
slouken@1330
  2456
slouken@1330
  2457
/* Set size, cinuse and pinuse bit of this chunk */
slouken@1330
  2458
#define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
slouken@1330
  2459
  ((p)->head = (s|PINUSE_BIT|CINUSE_BIT))
slouken@1330
  2460
slouken@1330
  2461
#else /* FOOTERS */
slouken@1330
  2462
slouken@1330
  2463
/* Set foot of inuse chunk to be xor of mstate and seed */
slouken@1330
  2464
#define mark_inuse_foot(M,p,s)\
slouken@1330
  2465
  (((mchunkptr)((char*)(p) + (s)))->prev_foot = ((size_t)(M) ^ mparams.magic))
slouken@1330
  2466
slouken@1330
  2467
#define get_mstate_for(p)\
slouken@1330
  2468
  ((mstate)(((mchunkptr)((char*)(p) +\
slouken@1330
  2469
    (chunksize(p))))->prev_foot ^ mparams.magic))
slouken@1330
  2470
slouken@1330
  2471
#define set_inuse(M,p,s)\
slouken@1330
  2472
  ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
slouken@1330
  2473
  (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT), \
slouken@1330
  2474
  mark_inuse_foot(M,p,s))
slouken@1330
  2475
slouken@1330
  2476
#define set_inuse_and_pinuse(M,p,s)\
slouken@1330
  2477
  ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
slouken@1330
  2478
  (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT),\
slouken@1330
  2479
 mark_inuse_foot(M,p,s))
slouken@1330
  2480
slouken@1330
  2481
#define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
slouken@1330
  2482