src/stdlib/SDL_malloc.c
author Ozkan Sezer <sezeroz@gmail.com>
Sun, 14 Oct 2018 15:25:04 +0300
branchSDL-1.2
changeset 12325 c4f2eeda176f
parent 6137 4720145f848b
permissions -rw-r--r--
remove symlink for libSDL-1.0.so.0 from the rpm spec file.

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