malloc/malloc.c

   1 /* Malloc implementation for multiple threads without lock contention.
   2    Copyright (C) 1996, 1997 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4    Contributed by Wolfram Gloger <wmglo@dent.med.uni-muenchen.de>
   5    and Doug Lea <dl@cs.oswego.edu>, 1996.
   6
   7    The GNU C Library is free software; you can redistribute it and/or
   8    modify it under the terms of the GNU Library General Public License as
   9    published by the Free Software Foundation; either version 2 of the
  10    License, or (at your option) any later version.
  11
  12    The GNU C Library is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15    Library General Public License for more details.
  16
  17    You should have received a copy of the GNU Library General Public
  18    License along with the GNU C Library; see the file COPYING.LIB.  If not,
  19    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  20    Boston, MA 02111-1307, USA.  */
  21
  22 /* V2.6.4-pt3 Thu Feb 20 1997
  23
  24   This work is mainly derived from malloc-2.6.4 by Doug Lea
  25   <dl@cs.oswego.edu>, which is available from:
  26
  27                  ftp://g.oswego.edu/pub/misc/malloc.c
  28
  29   Most of the original comments are reproduced in the code below.
  30
  31 * Why use this malloc?
  32
  33   This is not the fastest, most space-conserving, most portable, or
  34   most tunable malloc ever written. However it is among the fastest
  35   while also being among the most space-conserving, portable and tunable.
  36   Consistent balance across these factors results in a good general-purpose
  37   allocator. For a high-level description, see
  38      http://g.oswego.edu/dl/html/malloc.html
  39
  40   On many systems, the standard malloc implementation is by itself not
  41   thread-safe, and therefore wrapped with a single global lock around
  42   all malloc-related functions.  In some applications, especially with
  43   multiple available processors, this can lead to contention problems
  44   and bad performance.  This malloc version was designed with the goal
  45   to avoid waiting for locks as much as possible.  Statistics indicate
  46   that this goal is achieved in many cases.
  47
  48 * Synopsis of public routines
  49
  50   (Much fuller descriptions are contained in the program documentation below.)
  51
  52   ptmalloc_init();
  53      Initialize global configuration.  When compiled for multiple threads,
  54      this function must be called once before any other function in the
  55      package.  It is not required otherwise.  It is called automatically
  56      in the Linux/GNU C libray or when compiling with MALLOC_HOOKS.
  57   malloc(size_t n);
  58      Return a pointer to a newly allocated chunk of at least n bytes, or null
  59      if no space is available.
  60   free(Void_t* p);
  61      Release the chunk of memory pointed to by p, or no effect if p is null.
  62   realloc(Void_t* p, size_t n);
  63      Return a pointer to a chunk of size n that contains the same data
  64      as does chunk p up to the minimum of (n, p's size) bytes, or null
  65      if no space is available. The returned pointer may or may not be
  66      the same as p. If p is null, equivalent to malloc.  Unless the
  67      #define REALLOC_ZERO_BYTES_FREES below is set, realloc with a
  68      size argument of zero (re)allocates a minimum-sized chunk.
  69   memalign(size_t alignment, size_t n);
  70      Return a pointer to a newly allocated chunk of n bytes, aligned
  71      in accord with the alignment argument, which must be a power of
  72      two.
  73   valloc(size_t n);
  74      Equivalent to memalign(pagesize, n), where pagesize is the page
  75      size of the system (or as near to this as can be figured out from
  76      all the includes/defines below.)
  77   pvalloc(size_t n);
  78      Equivalent to valloc(minimum-page-that-holds(n)), that is,
  79      round up n to nearest pagesize.
  80   calloc(size_t unit, size_t quantity);
  81      Returns a pointer to quantity * unit bytes, with all locations
  82      set to zero.
  83   cfree(Void_t* p);
  84      Equivalent to free(p).
  85   malloc_trim(size_t pad);
  86      Release all but pad bytes of freed top-most memory back
  87      to the system. Return 1 if successful, else 0.
  88   malloc_usable_size(Void_t* p);
  89      Report the number usable allocated bytes associated with allocated
  90      chunk p. This may or may not report more bytes than were requested,
  91      due to alignment and minimum size constraints.
  92   malloc_stats();
  93      Prints brief summary statistics on stderr.
  94   mallinfo()
  95      Returns (by copy) a struct containing various summary statistics.
  96   mallopt(int parameter_number, int parameter_value)
  97      Changes one of the tunable parameters described below. Returns
  98      1 if successful in changing the parameter, else 0.
  99
 100 * Vital statistics:
 101
 102   Alignment:                            8-byte
 103        8 byte alignment is currently hardwired into the design.  This
 104        seems to suffice for all current machines and C compilers.
 105
 106   Assumed pointer representation:       4 or 8 bytes
 107        Code for 8-byte pointers is untested by me but has worked
 108        reliably by Wolfram Gloger, who contributed most of the
 109        changes supporting this.
 110
 111   Assumed size_t  representation:       4 or 8 bytes
 112        Note that size_t is allowed to be 4 bytes even if pointers are 8.
 113
 114   Minimum overhead per allocated chunk: 4 or 8 bytes
 115        Each malloced chunk has a hidden overhead of 4 bytes holding size
 116        and status information.
 117
 118   Minimum allocated size: 4-byte ptrs:  16 bytes    (including 4 overhead)
 119                           8-byte ptrs:  24/32 bytes (including, 4/8 overhead)
 120
 121        When a chunk is freed, 12 (for 4byte ptrs) or 20 (for 8 byte
 122        ptrs but 4 byte size) or 24 (for 8/8) additional bytes are
 123        needed; 4 (8) for a trailing size field
 124        and 8 (16) bytes for free list pointers. Thus, the minimum
 125        allocatable size is 16/24/32 bytes.
 126
 127        Even a request for zero bytes (i.e., malloc(0)) returns a
 128        pointer to something of the minimum allocatable size.
 129
 130   Maximum allocated size: 4-byte size_t: 2^31 -  8 bytes
 131                           8-byte size_t: 2^63 - 16 bytes
 132
 133        It is assumed that (possibly signed) size_t bit values suffice to
 134        represent chunk sizes. `Possibly signed' is due to the fact
 135        that `size_t' may be defined on a system as either a signed or
 136        an unsigned type. To be conservative, values that would appear
 137        as negative numbers are avoided.
 138        Requests for sizes with a negative sign bit will return a
 139        minimum-sized chunk.
 140
 141   Maximum overhead wastage per allocated chunk: normally 15 bytes
 142
 143        Alignment demands, plus the minimum allocatable size restriction
 144        make the normal worst-case wastage 15 bytes (i.e., up to 15
 145        more bytes will be allocated than were requested in malloc), with
 146        two exceptions:
 147          1. Because requests for zero bytes allocate non-zero space,
 148             the worst case wastage for a request of zero bytes is 24 bytes.
 149          2. For requests >= mmap_threshold that are serviced via
 150             mmap(), the worst case wastage is 8 bytes plus the remainder
 151             from a system page (the minimal mmap unit); typically 4096 bytes.
 152
 153 * Limitations
 154
 155     Here are some features that are NOT currently supported
 156
 157     * No automated mechanism for fully checking that all accesses
 158       to malloced memory stay within their bounds.
 159     * No support for compaction.
 160
 161 * Synopsis of compile-time options:
 162
 163     People have reported using previous versions of this malloc on all
 164     versions of Unix, sometimes by tweaking some of the defines
 165     below. It has been tested most extensively on Solaris and
 166     Linux. People have also reported adapting this malloc for use in
 167     stand-alone embedded systems.
 168
 169     The implementation is in straight, hand-tuned ANSI C.  Among other
 170     consequences, it uses a lot of macros.  Because of this, to be at
 171     all usable, this code should be compiled using an optimizing compiler
 172     (for example gcc -O2) that can simplify expressions and control
 173     paths.
 174
 175   __STD_C                  (default: derived from C compiler defines)
 176      Nonzero if using ANSI-standard C compiler, a C++ compiler, or
 177      a C compiler sufficiently close to ANSI to get away with it.
 178   MALLOC_DEBUG             (default: NOT defined)
 179      Define to enable debugging. Adds fairly extensive assertion-based
 180      checking to help track down memory errors, but noticeably slows down
 181      execution.
 182   MALLOC_HOOKS             (default: NOT defined)
 183      Define to enable support run-time replacement of the allocation
 184      functions through user-defined `hooks'.
 185   REALLOC_ZERO_BYTES_FREES (default: NOT defined)
 186      Define this if you think that realloc(p, 0) should be equivalent
 187      to free(p). Otherwise, since malloc returns a unique pointer for
 188      malloc(0), so does realloc(p, 0).
 189   HAVE_MEMCPY               (default: defined)
 190      Define if you are not otherwise using ANSI STD C, but still
 191      have memcpy and memset in your C library and want to use them.
 192      Otherwise, simple internal versions are supplied.
 193   USE_MEMCPY               (default: 1 if HAVE_MEMCPY is defined, 0 otherwise)
 194      Define as 1 if you want the C library versions of memset and
 195      memcpy called in realloc and calloc (otherwise macro versions are used).
 196      At least on some platforms, the simple macro versions usually
 197      outperform libc versions.
 198   HAVE_MMAP                 (default: defined as 1)
 199      Define to non-zero to optionally make malloc() use mmap() to
 200      allocate very large blocks.
 201   HAVE_MREMAP                 (default: defined as 0 unless Linux libc set)
 202      Define to non-zero to optionally make realloc() use mremap() to
 203      reallocate very large blocks.
 204   malloc_getpagesize        (default: derived from system #includes)
 205      Either a constant or routine call returning the system page size.
 206   HAVE_USR_INCLUDE_MALLOC_H (default: NOT defined)
 207      Optionally define if you are on a system with a /usr/include/malloc.h
 208      that declares struct mallinfo. It is not at all necessary to
 209      define this even if you do, but will ensure consistency.
 210   INTERNAL_SIZE_T           (default: size_t)
 211      Define to a 32-bit type (probably `unsigned int') if you are on a
 212      64-bit machine, yet do not want or need to allow malloc requests of
 213      greater than 2^31 to be handled. This saves space, especially for
 214      very small chunks.
 215   _LIBC                     (default: NOT defined)
 216      Defined only when compiled as part of the Linux libc/glibc.
 217      Also note that there is some odd internal name-mangling via defines
 218      (for example, internally, `malloc' is named `mALLOc') needed
 219      when compiling in this case. These look funny but don't otherwise
 220      affect anything.
 221   LACKS_UNISTD_H            (default: undefined)
 222      Define this if your system does not have a <unistd.h>.
 223   MORECORE                  (default: sbrk)
 224      The name of the routine to call to obtain more memory from the system.
 225   MORECORE_FAILURE          (default: -1)
 226      The value returned upon failure of MORECORE.
 227   MORECORE_CLEARS           (default 1)
 228      True (1) if the routine mapped to MORECORE zeroes out memory (which
 229      holds for sbrk).
 230   DEFAULT_TRIM_THRESHOLD
 231   DEFAULT_TOP_PAD
 232   DEFAULT_MMAP_THRESHOLD
 233   DEFAULT_MMAP_MAX
 234      Default values of tunable parameters (described in detail below)
 235      controlling interaction with host system routines (sbrk, mmap, etc).
 236      These values may also be changed dynamically via mallopt(). The
 237      preset defaults are those that give best performance for typical
 238      programs/systems.
 239   DEFAULT_CHECK_ACTION
 240      When the standard debugging hooks are in place, and a pointer is
 241      detected as corrupt, do nothing (0), print an error message (1),
 242      or call abort() (2).
 243
 244
 245 */
 246
 247 /*
 248
 249 * Compile-time options for multiple threads:
 250
 251   USE_PTHREADS, USE_THR, USE_SPROC
 252      Define one of these as 1 to select the thread interface:
 253      POSIX threads, Solaris threads or SGI sproc's, respectively.
 254      If none of these is defined as non-zero, you get a `normal'
 255      malloc implementation which is not thread-safe.  Support for
 256      multiple threads requires HAVE_MMAP=1.  As an exception, when
 257      compiling for GNU libc, i.e. when _LIBC is defined, then none of
 258      the USE_... symbols have to be defined.
 259
 260   HEAP_MIN_SIZE
 261   HEAP_MAX_SIZE
 262      When thread support is enabled, additional `heap's are created
 263      with mmap calls.  These are limited in size; HEAP_MIN_SIZE should
 264      be a multiple of the page size, while HEAP_MAX_SIZE must be a power
 265      of two for alignment reasons.  HEAP_MAX_SIZE should be at least
 266      twice as large as the mmap threshold.
 267   THREAD_STATS
 268      When this is defined as non-zero, some statistics on mutex locking
 269      are computed.
 270
 271 */
 272
 273 \f
 274
 275
 276 /* Preliminaries */
 277
 278 #ifndef __STD_C
 279 #if defined (__STDC__)
 280 #define __STD_C     1
 281 #else
 282 #if __cplusplus
 283 #define __STD_C     1
 284 #else
 285 #define __STD_C     0
 286 #endif /*__cplusplus*/
 287 #endif /*__STDC__*/
 288 #endif /*__STD_C*/
 289
 290 #ifndef Void_t
 291 #if __STD_C
 292 #define Void_t      void
 293 #else
 294 #define Void_t      char
 295 #endif
 296 #endif /*Void_t*/
 297
 298 #if __STD_C
 299 # include <stddef.h>   /* for size_t */
 300 # if defined(_LIBC) || defined(MALLOC_HOOKS)
 301 #  include <stdlib.h>  /* for getenv(), abort() */
 302 # endif
 303 #else
 304 # include <sys/types.h>
 305 #endif
 306
 307 /* Macros for handling mutexes and thread-specific data.  This is
 308    included early, because some thread-related header files (such as
 309    pthread.h) should be included before any others. */
 310 #include "thread-m.h"
 311
 312 #ifdef __cplusplus
 313 extern "C" {
 314 #endif
 315
 316 #include <stdio.h>    /* needed for malloc_stats */
 317
 318
 319 /*
 320   Compile-time options
 321 */
 322
 323
 324 /*
 325     Debugging:
 326
 327     Because freed chunks may be overwritten with link fields, this
 328     malloc will often die when freed memory is overwritten by user
 329     programs.  This can be very effective (albeit in an annoying way)
 330     in helping track down dangling pointers.
 331
 332     If you compile with -DMALLOC_DEBUG, a number of assertion checks are
 333     enabled that will catch more memory errors. You probably won't be
 334     able to make much sense of the actual assertion errors, but they
 335     should help you locate incorrectly overwritten memory.  The
 336     checking is fairly extensive, and will slow down execution
 337     noticeably. Calling malloc_stats or mallinfo with MALLOC_DEBUG set will
 338     attempt to check every non-mmapped allocated and free chunk in the
 339     course of computing the summaries. (By nature, mmapped regions
 340     cannot be checked very much automatically.)
 341
 342     Setting MALLOC_DEBUG may also be helpful if you are trying to modify
 343     this code. The assertions in the check routines spell out in more
 344     detail the assumptions and invariants underlying the algorithms.
 345
 346 */
 347
 348 #if MALLOC_DEBUG
 349 #include <assert.h>
 350 #else
 351 #define assert(x) ((void)0)
 352 #endif
 353
 354
 355 /*
 356   INTERNAL_SIZE_T is the word-size used for internal bookkeeping
 357   of chunk sizes. On a 64-bit machine, you can reduce malloc
 358   overhead by defining INTERNAL_SIZE_T to be a 32 bit `unsigned int'
 359   at the expense of not being able to handle requests greater than
 360   2^31. This limitation is hardly ever a concern; you are encouraged
 361   to set this. However, the default version is the same as size_t.
 362 */
 363
 364 #ifndef INTERNAL_SIZE_T
 365 #define INTERNAL_SIZE_T size_t
 366 #endif
 367
 368 /*
 369   REALLOC_ZERO_BYTES_FREES should be set if a call to
 370   realloc with zero bytes should be the same as a call to free.
 371   Some people think it should. Otherwise, since this malloc
 372   returns a unique pointer for malloc(0), so does realloc(p, 0).
 373 */
 374
 375
 376 /*   #define REALLOC_ZERO_BYTES_FREES */
 377
 378
 379 /*
 380   HAVE_MEMCPY should be defined if you are not otherwise using
 381   ANSI STD C, but still have memcpy and memset in your C library
 382   and want to use them in calloc and realloc. Otherwise simple
 383   macro versions are defined here.
 384
 385   USE_MEMCPY should be defined as 1 if you actually want to
 386   have memset and memcpy called. People report that the macro
 387   versions are often enough faster than libc versions on many
 388   systems that it is better to use them.
 389
 390 */
 391
 392 #define HAVE_MEMCPY 1
 393
 394 #ifndef USE_MEMCPY
 395 #ifdef HAVE_MEMCPY
 396 #define USE_MEMCPY 1
 397 #else
 398 #define USE_MEMCPY 0
 399 #endif
 400 #endif
 401
 402 #if (__STD_C || defined(HAVE_MEMCPY))
 403
 404 #if __STD_C
 405 void* memset(void*, int, size_t);
 406 void* memcpy(void*, const void*, size_t);
 407 #else
 408 Void_t* memset();
 409 Void_t* memcpy();
 410 #endif
 411 #endif
 412
 413 #if USE_MEMCPY
 414
 415 /* The following macros are only invoked with (2n+1)-multiples of
 416    INTERNAL_SIZE_T units, with a positive integer n. This is exploited
 417    for fast inline execution when n is small. */
 418
 419 #define MALLOC_ZERO(charp, nbytes)                                            \
 420 do {                                                                          \
 421   INTERNAL_SIZE_T mzsz = (nbytes);                                            \
 422   if(mzsz <= 9*sizeof(mzsz)) {                                                \
 423     INTERNAL_SIZE_T* mz = (INTERNAL_SIZE_T*) (charp);                         \
 424     if(mzsz >= 5*sizeof(mzsz)) {     *mz++ = 0;                               \
 425                                      *mz++ = 0;                               \
 426       if(mzsz >= 7*sizeof(mzsz)) {   *mz++ = 0;                               \
 427                                      *mz++ = 0;                               \
 428         if(mzsz >= 9*sizeof(mzsz)) { *mz++ = 0;                               \
 429                                      *mz++ = 0; }}}                           \
 430                                      *mz++ = 0;                               \
 431                                      *mz++ = 0;                               \
 432                                      *mz   = 0;                               \
 433   } else memset((charp), 0, mzsz);                                            \
 434 } while(0)
 435
 436 #define MALLOC_COPY(dest,src,nbytes)                                          \
 437 do {                                                                          \
 438   INTERNAL_SIZE_T mcsz = (nbytes);                                            \
 439   if(mcsz <= 9*sizeof(mcsz)) {                                                \
 440     INTERNAL_SIZE_T* mcsrc = (INTERNAL_SIZE_T*) (src);                        \
 441     INTERNAL_SIZE_T* mcdst = (INTERNAL_SIZE_T*) (dest);                       \
 442     if(mcsz >= 5*sizeof(mcsz)) {     *mcdst++ = *mcsrc++;                     \
 443                                      *mcdst++ = *mcsrc++;                     \
 444       if(mcsz >= 7*sizeof(mcsz)) {   *mcdst++ = *mcsrc++;                     \
 445                                      *mcdst++ = *mcsrc++;                     \
 446         if(mcsz >= 9*sizeof(mcsz)) { *mcdst++ = *mcsrc++;                     \
 447                                      *mcdst++ = *mcsrc++; }}}                 \
 448                                      *mcdst++ = *mcsrc++;                     \
 449                                      *mcdst++ = *mcsrc++;                     \
 450                                      *mcdst   = *mcsrc  ;                     \
 451   } else memcpy(dest, src, mcsz);                                             \
 452 } while(0)
 453
 454 #else /* !USE_MEMCPY */
 455
 456 /* Use Duff's device for good zeroing/copying performance. */
 457
 458 #define MALLOC_ZERO(charp, nbytes)                                            \
 459 do {                                                                          \
 460   INTERNAL_SIZE_T* mzp = (INTERNAL_SIZE_T*)(charp);                           \
 461   long mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T), mcn;                         \
 462   if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; }             \
 463   switch (mctmp) {                                                            \
 464     case 0: for(;;) { *mzp++ = 0;                                             \
 465     case 7:           *mzp++ = 0;                                             \
 466     case 6:           *mzp++ = 0;                                             \
 467     case 5:           *mzp++ = 0;                                             \
 468     case 4:           *mzp++ = 0;                                             \
 469     case 3:           *mzp++ = 0;                                             \
 470     case 2:           *mzp++ = 0;                                             \
 471     case 1:           *mzp++ = 0; if(mcn <= 0) break; mcn--; }                \
 472   }                                                                           \
 473 } while(0)
 474
 475 #define MALLOC_COPY(dest,src,nbytes)                                          \
 476 do {                                                                          \
 477   INTERNAL_SIZE_T* mcsrc = (INTERNAL_SIZE_T*) src;                            \
 478   INTERNAL_SIZE_T* mcdst = (INTERNAL_SIZE_T*) dest;                           \
 479   long mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T), mcn;                         \
 480   if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; }             \
 481   switch (mctmp) {                                                            \
 482     case 0: for(;;) { *mcdst++ = *mcsrc++;                                    \
 483     case 7:           *mcdst++ = *mcsrc++;                                    \
 484     case 6:           *mcdst++ = *mcsrc++;                                    \
 485     case 5:           *mcdst++ = *mcsrc++;                                    \
 486     case 4:           *mcdst++ = *mcsrc++;                                    \
 487     case 3:           *mcdst++ = *mcsrc++;                                    \
 488     case 2:           *mcdst++ = *mcsrc++;                                    \
 489     case 1:           *mcdst++ = *mcsrc++; if(mcn <= 0) break; mcn--; }       \
 490   }                                                                           \
 491 } while(0)
 492
 493 #endif
 494
 495
 496 /*
 497   Define HAVE_MMAP to optionally make malloc() use mmap() to
 498   allocate very large blocks.  These will be returned to the
 499   operating system immediately after a free().
 500 */
 501
 502 #ifndef HAVE_MMAP
 503 #define HAVE_MMAP 1
 504 #endif
 505
 506 /*
 507   Define HAVE_MREMAP to make realloc() use mremap() to re-allocate
 508   large blocks.  This is currently only possible on Linux with
 509   kernel versions newer than 1.3.77.
 510 */
 511
 512 #ifndef HAVE_MREMAP
 513 #define HAVE_MREMAP defined(__linux__)
 514 #endif
 515
 516 #if HAVE_MMAP
 517
 518 #include <unistd.h>
 519 #include <fcntl.h>
 520 #include <sys/mman.h>
 521
 522 #if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
 523 #define MAP_ANONYMOUS MAP_ANON
 524 #endif
 525
 526 #endif /* HAVE_MMAP */
 527
 528 /*
 529   Access to system page size. To the extent possible, this malloc
 530   manages memory from the system in page-size units.
 531
 532   The following mechanics for getpagesize were adapted from
 533   bsd/gnu getpagesize.h
 534 */
 535
 536 #ifndef LACKS_UNISTD_H
 537 #  include <unistd.h>
 538 #endif
 539
 540 #ifndef malloc_getpagesize
 541 #  ifdef _SC_PAGESIZE         /* some SVR4 systems omit an underscore */
 542 #    ifndef _SC_PAGE_SIZE
 543 #      define _SC_PAGE_SIZE _SC_PAGESIZE
 544 #    endif
 545 #  endif
 546 #  ifdef _SC_PAGE_SIZE
 547 #    define malloc_getpagesize sysconf(_SC_PAGE_SIZE)
 548 #  else
 549 #    if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE)
 550        extern size_t getpagesize();
 551 #      define malloc_getpagesize getpagesize()
 552 #    else
 553 #      include <sys/param.h>
 554 #      ifdef EXEC_PAGESIZE
 555 #        define malloc_getpagesize EXEC_PAGESIZE
 556 #      else
 557 #        ifdef NBPG
 558 #          ifndef CLSIZE
 559 #            define malloc_getpagesize NBPG
 560 #          else
 561 #            define malloc_getpagesize (NBPG * CLSIZE)
 562 #          endif
 563 #        else
 564 #          ifdef NBPC
 565 #            define malloc_getpagesize NBPC
 566 #          else
 567 #            ifdef PAGESIZE
 568 #              define malloc_getpagesize PAGESIZE
 569 #            else
 570 #              define malloc_getpagesize (4096) /* just guess */
 571 #            endif
 572 #          endif
 573 #        endif
 574 #      endif
 575 #    endif
 576 #  endif
 577 #endif
 578
 579
 580
 581 /*
 582
 583   This version of malloc supports the standard SVID/XPG mallinfo
 584   routine that returns a struct containing the same kind of
 585   information you can get from malloc_stats. It should work on
 586   any SVID/XPG compliant system that has a /usr/include/malloc.h
 587   defining struct mallinfo. (If you'd like to install such a thing
 588   yourself, cut out the preliminary declarations as described above
 589   and below and save them in a malloc.h file. But there's no
 590   compelling reason to bother to do this.)
 591
 592   The main declaration needed is the mallinfo struct that is returned
 593   (by-copy) by mallinfo().  The SVID/XPG malloinfo struct contains a
 594   bunch of fields, most of which are not even meaningful in this
 595   version of malloc. Some of these fields are are instead filled by
 596   mallinfo() with other numbers that might possibly be of interest.
 597
 598   HAVE_USR_INCLUDE_MALLOC_H should be set if you have a
 599   /usr/include/malloc.h file that includes a declaration of struct
 600   mallinfo.  If so, it is included; else an SVID2/XPG2 compliant
 601   version is declared below.  These must be precisely the same for
 602   mallinfo() to work.
 603
 604 */
 605
 606 /* #define HAVE_USR_INCLUDE_MALLOC_H */
 607
 608 #if HAVE_USR_INCLUDE_MALLOC_H
 609 # include "/usr/include/malloc.h"
 610 #else
 611 # ifdef _LIBC
 612 #  include "malloc.h"
 613 # else
 614 #  include "ptmalloc.h"
 615 # endif
 616 #endif
 617
 618
 619
 620 #ifndef DEFAULT_TRIM_THRESHOLD
 621 #define DEFAULT_TRIM_THRESHOLD (128 * 1024)
 622 #endif
 623
 624 /*
 625     M_TRIM_THRESHOLD is the maximum amount of unused top-most memory
 626       to keep before releasing via malloc_trim in free().
 627
 628       Automatic trimming is mainly useful in long-lived programs.
 629       Because trimming via sbrk can be slow on some systems, and can
 630       sometimes be wasteful (in cases where programs immediately
 631       afterward allocate more large chunks) the value should be high
 632       enough so that your overall system performance would improve by
 633       releasing.
 634
 635       The trim threshold and the mmap control parameters (see below)
 636       can be traded off with one another. Trimming and mmapping are
 637       two different ways of releasing unused memory back to the
 638       system. Between these two, it is often possible to keep
 639       system-level demands of a long-lived program down to a bare
 640       minimum. For example, in one test suite of sessions measuring
 641       the XF86 X server on Linux, using a trim threshold of 128K and a
 642       mmap threshold of 192K led to near-minimal long term resource
 643       consumption.
 644
 645       If you are using this malloc in a long-lived program, it should
 646       pay to experiment with these values.  As a rough guide, you
 647       might set to a value close to the average size of a process
 648       (program) running on your system.  Releasing this much memory
 649       would allow such a process to run in memory.  Generally, it's
 650       worth it to tune for trimming rather than memory mapping when a
 651       program undergoes phases where several large chunks are
 652       allocated and released in ways that can reuse each other's
 653       storage, perhaps mixed with phases where there are no such
 654       chunks at all.  And in well-behaved long-lived programs,
 655       controlling release of large blocks via trimming versus mapping
 656       is usually faster.
 657
 658       However, in most programs, these parameters serve mainly as
 659       protection against the system-level effects of carrying around
 660       massive amounts of unneeded memory. Since frequent calls to
 661       sbrk, mmap, and munmap otherwise degrade performance, the default
 662       parameters are set to relatively high values that serve only as
 663       safeguards.
 664
 665       The default trim value is high enough to cause trimming only in
 666       fairly extreme (by current memory consumption standards) cases.
 667       It must be greater than page size to have any useful effect.  To
 668       disable trimming completely, you can set to (unsigned long)(-1);
 669
 670
 671 */
 672
 673
 674 #ifndef DEFAULT_TOP_PAD
 675 #define DEFAULT_TOP_PAD        (0)
 676 #endif
 677
 678 /*
 679     M_TOP_PAD is the amount of extra `padding' space to allocate or
 680       retain whenever sbrk is called. It is used in two ways internally:
 681
 682       * When sbrk is called to extend the top of the arena to satisfy
 683         a new malloc request, this much padding is added to the sbrk
 684         request.
 685
 686       * When malloc_trim is called automatically from free(),
 687         it is used as the `pad' argument.
 688
 689       In both cases, the actual amount of padding is rounded
 690       so that the end of the arena is always a system page boundary.
 691
 692       The main reason for using padding is to avoid calling sbrk so
 693       often. Having even a small pad greatly reduces the likelihood
 694       that nearly every malloc request during program start-up (or
 695       after trimming) will invoke sbrk, which needlessly wastes
 696       time.
 697
 698       Automatic rounding-up to page-size units is normally sufficient
 699       to avoid measurable overhead, so the default is 0.  However, in
 700       systems where sbrk is relatively slow, it can pay to increase
 701       this value, at the expense of carrying around more memory than
 702       the program needs.
 703
 704 */
 705
 706
 707 #ifndef DEFAULT_MMAP_THRESHOLD
 708 #define DEFAULT_MMAP_THRESHOLD (128 * 1024)
 709 #endif
 710
 711 /*
 712
 713     M_MMAP_THRESHOLD is the request size threshold for using mmap()
 714       to service a request. Requests of at least this size that cannot
 715       be allocated using already-existing space will be serviced via mmap.
 716       (If enough normal freed space already exists it is used instead.)
 717
 718       Using mmap segregates relatively large chunks of memory so that
 719       they can be individually obtained and released from the host
 720       system. A request serviced through mmap is never reused by any
 721       other request (at least not directly; the system may just so
 722       happen to remap successive requests to the same locations).
 723
 724       Segregating space in this way has the benefit that mmapped space
 725       can ALWAYS be individually released back to the system, which
 726       helps keep the system level memory demands of a long-lived
 727       program low. Mapped memory can never become `locked' between
 728       other chunks, as can happen with normally allocated chunks, which
 729       menas that even trimming via malloc_trim would not release them.
 730
 731       However, it has the disadvantages that:
 732
 733          1. The space cannot be reclaimed, consolidated, and then
 734             used to service later requests, as happens with normal chunks.
 735          2. It can lead to more wastage because of mmap page alignment
 736             requirements
 737          3. It causes malloc performance to be more dependent on host
 738             system memory management support routines which may vary in
 739             implementation quality and may impose arbitrary
 740             limitations. Generally, servicing a request via normal
 741             malloc steps is faster than going through a system's mmap.
 742
 743       All together, these considerations should lead you to use mmap
 744       only for relatively large requests.
 745
 746
 747 */
 748
 749
 750
 751 #ifndef DEFAULT_MMAP_MAX
 752 #if HAVE_MMAP
 753 #define DEFAULT_MMAP_MAX       (1024)
 754 #else
 755 #define DEFAULT_MMAP_MAX       (0)
 756 #endif
 757 #endif
 758
 759 /*
 760     M_MMAP_MAX is the maximum number of requests to simultaneously
 761       service using mmap. This parameter exists because:
 762
 763          1. Some systems have a limited number of internal tables for
 764             use by mmap.
 765          2. In most systems, overreliance on mmap can degrade overall
 766             performance.
 767          3. If a program allocates many large regions, it is probably
 768             better off using normal sbrk-based allocation routines that
 769             can reclaim and reallocate normal heap memory. Using a
 770             small value allows transition into this mode after the
 771             first few allocations.
 772
 773       Setting to 0 disables all use of mmap.  If HAVE_MMAP is not set,
 774       the default value is 0, and attempts to set it to non-zero values
 775       in mallopt will fail.
 776 */
 777
 778
 779
 780 #ifndef DEFAULT_CHECK_ACTION
 781 #define DEFAULT_CHECK_ACTION 1
 782 #endif
 783
 784 /* What to do if the standard debugging hooks are in place and a
 785    corrupt pointer is detected: do nothing (0), print an error message
 786    (1), or call abort() (2). */
 787
 788
 789
 790 #define HEAP_MIN_SIZE (32*1024)
 791 #define HEAP_MAX_SIZE (1024*1024) /* must be a power of two */
 792
 793 /* HEAP_MIN_SIZE and HEAP_MAX_SIZE limit the size of mmap()ed heaps
 794       that are dynamically created for multi-threaded programs.  The
 795       maximum size must be a power of two, for fast determination of
 796       which heap belongs to a chunk.  It should be much larger than
 797       the mmap threshold, so that requests with a size just below that
 798       threshold can be fulfilled without creating too many heaps.
 799 */
 800
 801
 802
 803 #ifndef THREAD_STATS
 804 #define THREAD_STATS 0
 805 #endif
 806
 807 /* If THREAD_STATS is non-zero, some statistics on mutex locking are
 808    computed. */
 809
 810
 811 /*
 812
 813   Special defines for the Linux/GNU C library.
 814
 815 */
 816
 817
 818 #ifdef _LIBC
 819
 820 #if __STD_C
 821
 822 Void_t * __default_morecore (ptrdiff_t);
 823 Void_t *(*__morecore)(ptrdiff_t) = __default_morecore;
 824
 825 #else
 826
 827 Void_t * __default_morecore ();
 828 Void_t *(*__morecore)() = __default_morecore;
 829
 830 #endif
 831
 832 #define MORECORE (*__morecore)
 833 #define MORECORE_FAILURE 0
 834 #define MORECORE_CLEARS 1
 835 #define mmap    __mmap
 836 #define munmap  __munmap
 837 #define mremap  __mremap
 838 #define mprotect __mprotect
 839 #undef malloc_getpagesize
 840 #define malloc_getpagesize __getpagesize()
 841
 842 #else /* _LIBC */
 843
 844 #if __STD_C
 845 extern Void_t*     sbrk(ptrdiff_t);
 846 #else
 847 extern Void_t*     sbrk();
 848 #endif
 849
 850 #ifndef MORECORE
 851 #define MORECORE sbrk
 852 #endif
 853
 854 #ifndef MORECORE_FAILURE
 855 #define MORECORE_FAILURE -1
 856 #endif
 857
 858 #ifndef MORECORE_CLEARS
 859 #define MORECORE_CLEARS 1
 860 #endif
 861
 862 #endif /* _LIBC */
 863
 864 #ifdef _LIBC
 865
 866 #define cALLOc          __libc_calloc
 867 #define fREe            __libc_free
 868 #define mALLOc          __libc_malloc
 869 #define mEMALIGn        __libc_memalign
 870 #define rEALLOc         __libc_realloc
 871 #define vALLOc          __libc_valloc
 872 #define pvALLOc         __libc_pvalloc
 873 #define mALLINFo        __libc_mallinfo
 874 #define mALLOPt         __libc_mallopt
 875 #define mALLOC_STATs    __malloc_stats
 876 #define mALLOC_USABLE_SIZe __malloc_usable_size
 877 #define mALLOC_TRIm     __malloc_trim
 878 #define mALLOC_GET_STATe __malloc_get_state
 879 #define mALLOC_SET_STATe __malloc_set_state
 880
 881 #else
 882
 883 #define cALLOc          calloc
 884 #define fREe            free
 885 #define mALLOc          malloc
 886 #define mEMALIGn        memalign
 887 #define rEALLOc         realloc
 888 #define vALLOc          valloc
 889 #define pvALLOc         pvalloc
 890 #define mALLINFo        mallinfo
 891 #define mALLOPt         mallopt
 892 #define mALLOC_STATs    malloc_stats
 893 #define mALLOC_USABLE_SIZe malloc_usable_size
 894 #define mALLOC_TRIm     malloc_trim
 895 #define mALLOC_GET_STATe malloc_get_state
 896 #define mALLOC_SET_STATe malloc_set_state
 897
 898 #endif
 899
 900 /* Public routines */
 901
 902 #if __STD_C
 903
 904 #ifndef _LIBC
 905 void    ptmalloc_init(void);
 906 #endif
 907 Void_t* mALLOc(size_t);
 908 void    fREe(Void_t*);
 909 Void_t* rEALLOc(Void_t*, size_t);
 910 Void_t* mEMALIGn(size_t, size_t);
 911 Void_t* vALLOc(size_t);
 912 Void_t* pvALLOc(size_t);
 913 Void_t* cALLOc(size_t, size_t);
 914 void    cfree(Void_t*);
 915 int     mALLOC_TRIm(size_t);
 916 size_t  mALLOC_USABLE_SIZe(Void_t*);
 917 void    mALLOC_STATs(void);
 918 int     mALLOPt(int, int);
 919 struct mallinfo mALLINFo(void);
 920 Void_t* mALLOC_GET_STATe(void);
 921 int     mALLOC_SET_STATe(Void_t*);
 922
 923 #else /* !__STD_C */
 924
 925 #ifndef _LIBC
 926 void    ptmalloc_init();
 927 #endif
 928 Void_t* mALLOc();
 929 void    fREe();
 930 Void_t* rEALLOc();
 931 Void_t* mEMALIGn();
 932 Void_t* vALLOc();
 933 Void_t* pvALLOc();
 934 Void_t* cALLOc();
 935 void    cfree();
 936 int     mALLOC_TRIm();
 937 size_t  mALLOC_USABLE_SIZe();
 938 void    mALLOC_STATs();
 939 int     mALLOPt();
 940 struct mallinfo mALLINFo();
 941 Void_t* mALLOC_GET_STATe();
 942 int     mALLOC_SET_STATe();
 943
 944 #endif /* __STD_C */
 945
 946
 947 #ifdef __cplusplus
 948 };  /* end of extern "C" */
 949 #endif
 950
 951 #if !defined(NO_THREADS) && !HAVE_MMAP
 952 "Can't have threads support without mmap"
 953 #endif
 954
 955
 956 /*
 957   Type declarations
 958 */
 959
 960
 961 struct malloc_chunk
 962 {
 963   INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
 964   INTERNAL_SIZE_T size;      /* Size in bytes, including overhead. */
 965   struct malloc_chunk* fd;   /* double links -- used only if free. */
 966   struct malloc_chunk* bk;
 967 };
 968
 969 typedef struct malloc_chunk* mchunkptr;
 970
 971 /*
 972
 973    malloc_chunk details:
 974
 975     (The following includes lightly edited explanations by Colin Plumb.)
 976
 977     Chunks of memory are maintained using a `boundary tag' method as
 978     described in e.g., Knuth or Standish.  (See the paper by Paul
 979     Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a
 980     survey of such techniques.)  Sizes of free chunks are stored both
 981     in the front of each chunk and at the end.  This makes
 982     consolidating fragmented chunks into bigger chunks very fast.  The
 983     size fields also hold bits representing whether chunks are free or
 984     in use.
 985
 986     An allocated chunk looks like this:
 987
 988
 989     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 990             |             Size of previous chunk, if allocated            | |
 991             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 992             |             Size of chunk, in bytes                         |P|
 993       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 994             |             User data starts here...                          .
 995             .                                                               .
 996             .             (malloc_usable_space() bytes)                     .
 997             .                                                               |
 998 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 999             |             Size of chunk                                     |
1000             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1001
1002
1003     Where "chunk" is the front of the chunk for the purpose of most of
1004     the malloc code, but "mem" is the pointer that is returned to the
1005     user.  "Nextchunk" is the beginning of the next contiguous chunk.
1006
1007     Chunks always begin on even word boundaries, so the mem portion
1008     (which is returned to the user) is also on an even word boundary, and
1009     thus double-word aligned.
1010
1011     Free chunks are stored in circular doubly-linked lists, and look like this:
1012
1013     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1014             |             Size of previous chunk                            |
1015             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1016     `head:' |             Size of chunk, in bytes                         |P|
1017       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1018             |             Forward pointer to next chunk in list             |
1019             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1020             |             Back pointer to previous chunk in list            |
1021             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1022             |             Unused space (may be 0 bytes long)                .
1023             .                                                               .
1024             .                                                               |
1025 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1026     `foot:' |             Size of chunk, in bytes                           |
1027             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1028
1029     The P (PREV_INUSE) bit, stored in the unused low-order bit of the
1030     chunk size (which is always a multiple of two words), is an in-use
1031     bit for the *previous* chunk.  If that bit is *clear*, then the
1032     word before the current chunk size contains the previous chunk
1033     size, and can be used to find the front of the previous chunk.
1034     (The very first chunk allocated always has this bit set,
1035     preventing access to non-existent (or non-owned) memory.)
1036
1037     Note that the `foot' of the current chunk is actually represented
1038     as the prev_size of the NEXT chunk. (This makes it easier to
1039     deal with alignments etc).
1040
1041     The two exceptions to all this are
1042
1043      1. The special chunk `top', which doesn't bother using the
1044         trailing size field since there is no
1045         next contiguous chunk that would have to index off it. (After
1046         initialization, `top' is forced to always exist.  If it would
1047         become less than MINSIZE bytes long, it is replenished via
1048         malloc_extend_top.)
1049
1050      2. Chunks allocated via mmap, which have the second-lowest-order
1051         bit (IS_MMAPPED) set in their size fields.  Because they are
1052         never merged or traversed from any other chunk, they have no
1053         foot size or inuse information.
1054
1055     Available chunks are kept in any of several places (all declared below):
1056
1057     * `av': An array of chunks serving as bin headers for consolidated
1058        chunks. Each bin is doubly linked.  The bins are approximately
1059        proportionally (log) spaced.  There are a lot of these bins
1060        (128). This may look excessive, but works very well in
1061        practice.  All procedures maintain the invariant that no
1062        consolidated chunk physically borders another one. Chunks in
1063        bins are kept in size order, with ties going to the
1064        approximately least recently used chunk.
1065
1066        The chunks in each bin are maintained in decreasing sorted order by
1067        size.  This is irrelevant for the small bins, which all contain
1068        the same-sized chunks, but facilitates best-fit allocation for
1069        larger chunks. (These lists are just sequential. Keeping them in
1070        order almost never requires enough traversal to warrant using
1071        fancier ordered data structures.)  Chunks of the same size are
1072        linked with the most recently freed at the front, and allocations
1073        are taken from the back.  This results in LRU or FIFO allocation
1074        order, which tends to give each chunk an equal opportunity to be
1075        consolidated with adjacent freed chunks, resulting in larger free
1076        chunks and less fragmentation.
1077
1078     * `top': The top-most available chunk (i.e., the one bordering the
1079        end of available memory) is treated specially. It is never
1080        included in any bin, is used only if no other chunk is
1081        available, and is released back to the system if it is very
1082        large (see M_TRIM_THRESHOLD).
1083
1084     * `last_remainder': A bin holding only the remainder of the
1085        most recently split (non-top) chunk. This bin is checked
1086        before other non-fitting chunks, so as to provide better
1087        locality for runs of sequentially allocated chunks.
1088
1089     *  Implicitly, through the host system's memory mapping tables.
1090        If supported, requests greater than a threshold are usually
1091        serviced via calls to mmap, and then later released via munmap.
1092
1093 */
1094
1095 /*
1096    Bins
1097
1098     The bins are an array of pairs of pointers serving as the
1099     heads of (initially empty) doubly-linked lists of chunks, laid out
1100     in a way so that each pair can be treated as if it were in a
1101     malloc_chunk. (This way, the fd/bk offsets for linking bin heads
1102     and chunks are the same).
1103
1104     Bins for sizes < 512 bytes contain chunks of all the same size, spaced
1105     8 bytes apart. Larger bins are approximately logarithmically
1106     spaced. (See the table below.)
1107
1108     Bin layout:
1109
1110     64 bins of size       8
1111     32 bins of size      64
1112     16 bins of size     512
1113      8 bins of size    4096
1114      4 bins of size   32768
1115      2 bins of size  262144
1116      1 bin  of size what's left
1117
1118     There is actually a little bit of slop in the numbers in bin_index
1119     for the sake of speed. This makes no difference elsewhere.
1120
1121     The special chunks `top' and `last_remainder' get their own bins,
1122     (this is implemented via yet more trickery with the av array),
1123     although `top' is never properly linked to its bin since it is
1124     always handled specially.
1125
1126 */
1127
1128 #define NAV             128   /* number of bins */
1129
1130 typedef struct malloc_chunk* mbinptr;
1131
1132 /* An arena is a configuration of malloc_chunks together with an array
1133    of bins.  With multiple threads, it must be locked via a mutex
1134    before changing its data structures.  One or more `heaps' are
1135    associated with each arena, except for the main_arena, which is
1136    associated only with the `main heap', i.e.  the conventional free
1137    store obtained with calls to MORECORE() (usually sbrk).  The `av'
1138    array is never mentioned directly in the code, but instead used via
1139    bin access macros. */
1140
1141 typedef struct _arena {
1142   mbinptr av[2*NAV + 2];
1143   struct _arena *next;
1144   size_t size;
1145 #if THREAD_STATS
1146   long stat_lock_direct, stat_lock_loop, stat_lock_wait;
1147 #endif
1148   mutex_t mutex;
1149 } arena;
1150
1151
1152 /* A heap is a single contiguous memory region holding (coalesceable)
1153    malloc_chunks.  It is allocated with mmap() and always starts at an
1154    address aligned to HEAP_MAX_SIZE.  Not used unless compiling for
1155    multiple threads. */
1156
1157 typedef struct _heap_info {
1158   arena *ar_ptr; /* Arena for this heap. */
1159   struct _heap_info *prev; /* Previous heap. */
1160   size_t size;   /* Current size in bytes. */
1161   size_t pad;    /* Make sure the following data is properly aligned. */
1162 } heap_info;
1163
1164
1165 /*
1166   Static functions (forward declarations)
1167 */
1168
1169 #if __STD_C
1170
1171 static void      chunk_free(arena *ar_ptr, mchunkptr p);
1172 static mchunkptr chunk_alloc(arena *ar_ptr, INTERNAL_SIZE_T size);
1173 static mchunkptr chunk_realloc(arena *ar_ptr, mchunkptr oldp,
1174                                INTERNAL_SIZE_T oldsize, INTERNAL_SIZE_T nb);
1175 static mchunkptr chunk_align(arena *ar_ptr, INTERNAL_SIZE_T nb,
1176                              size_t alignment);
1177 static int       main_trim(size_t pad);
1178 #ifndef NO_THREADS
1179 static int       heap_trim(heap_info *heap, size_t pad);
1180 #endif
1181 #if defined(_LIBC) || defined(MALLOC_HOOKS)
1182 static Void_t*   malloc_check(size_t sz);
1183 static void      free_check(Void_t* mem);
1184 static Void_t*   realloc_check(Void_t* oldmem, size_t bytes);
1185 static Void_t*   memalign_check(size_t alignment, size_t bytes);
1186 static Void_t*   malloc_starter(size_t sz);
1187 static void      free_starter(Void_t* mem);
1188 #endif
1189
1190 #else
1191
1192 static void      chunk_free();
1193 static mchunkptr chunk_alloc();
1194 static mchunkptr chunk_realloc();
1195 static mchunkptr chunk_align();
1196 static int       main_trim();
1197 #ifndef NO_THREADS
1198 static int       heap_trim();
1199 #endif
1200 #if defined(_LIBC) || defined(MALLOC_HOOKS)
1201 static Void_t*   malloc_check();
1202 static void      free_check();
1203 static Void_t*   realloc_check();
1204 static Void_t*   memalign_check();
1205 static Void_t*   malloc_starter();
1206 static void      free_starter();
1207 #endif
1208
1209 #endif
1210
1211 \f
1212
1213 /* sizes, alignments */
1214
1215 #define SIZE_SZ                (sizeof(INTERNAL_SIZE_T))
1216 #define MALLOC_ALIGNMENT       (SIZE_SZ + SIZE_SZ)
1217 #define MALLOC_ALIGN_MASK      (MALLOC_ALIGNMENT - 1)
1218 #define MINSIZE                (sizeof(struct malloc_chunk))
1219
1220 /* conversion from malloc headers to user pointers, and back */
1221
1222 #define chunk2mem(p)   ((Void_t*)((char*)(p) + 2*SIZE_SZ))
1223 #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))
1224
1225 /* pad request bytes into a usable size */
1226
1227 #define request2size(req) \
1228  (((long)((req) + (SIZE_SZ + MALLOC_ALIGN_MASK)) < \
1229   (long)(MINSIZE + MALLOC_ALIGN_MASK)) ? MINSIZE : \
1230    (((req) + (SIZE_SZ + MALLOC_ALIGN_MASK)) & ~(MALLOC_ALIGN_MASK)))
1231
1232 /* Check if m has acceptable alignment */
1233
1234 #define aligned_OK(m)    (((unsigned long)((m)) & (MALLOC_ALIGN_MASK)) == 0)
1235
1236
1237 \f
1238
1239 /*
1240   Physical chunk operations
1241 */
1242
1243
1244 /* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
1245
1246 #define PREV_INUSE 0x1
1247
1248 /* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */
1249
1250 #define IS_MMAPPED 0x2
1251
1252 /* Bits to mask off when extracting size */
1253
1254 #define SIZE_BITS (PREV_INUSE|IS_MMAPPED)
1255
1256
1257 /* Ptr to next physical malloc_chunk. */
1258
1259 #define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->size & ~PREV_INUSE) ))
1260
1261 /* Ptr to previous physical malloc_chunk */
1262
1263 #define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_size) ))
1264
1265
1266 /* Treat space at ptr + offset as a chunk */
1267
1268 #define chunk_at_offset(p, s)  ((mchunkptr)(((char*)(p)) + (s)))
1269
1270
1271 \f
1272
1273 /*
1274   Dealing with use bits
1275 */
1276
1277 /* extract p's inuse bit */
1278
1279 #define inuse(p) \
1280  ((((mchunkptr)(((char*)(p))+((p)->size & ~PREV_INUSE)))->size) & PREV_INUSE)
1281
1282 /* extract inuse bit of previous chunk */
1283
1284 #define prev_inuse(p)  ((p)->size & PREV_INUSE)
1285
1286 /* check for mmap()'ed chunk */
1287
1288 #define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)
1289
1290 /* set/clear chunk as in use without otherwise disturbing */
1291
1292 #define set_inuse(p) \
1293  ((mchunkptr)(((char*)(p)) + ((p)->size & ~PREV_INUSE)))->size |= PREV_INUSE
1294
1295 #define clear_inuse(p) \
1296  ((mchunkptr)(((char*)(p)) + ((p)->size & ~PREV_INUSE)))->size &= ~(PREV_INUSE)
1297
1298 /* check/set/clear inuse bits in known places */
1299
1300 #define inuse_bit_at_offset(p, s)\
1301  (((mchunkptr)(((char*)(p)) + (s)))->size & PREV_INUSE)
1302
1303 #define set_inuse_bit_at_offset(p, s)\
1304  (((mchunkptr)(((char*)(p)) + (s)))->size |= PREV_INUSE)
1305
1306 #define clear_inuse_bit_at_offset(p, s)\
1307  (((mchunkptr)(((char*)(p)) + (s)))->size &= ~(PREV_INUSE))
1308
1309
1310 \f
1311
1312 /*
1313   Dealing with size fields
1314 */
1315
1316 /* Get size, ignoring use bits */
1317
1318 #define chunksize(p)          ((p)->size & ~(SIZE_BITS))
1319
1320 /* Set size at head, without disturbing its use bit */
1321
1322 #define set_head_size(p, s)   ((p)->size = (((p)->size & PREV_INUSE) | (s)))
1323
1324 /* Set size/use ignoring previous bits in header */
1325
1326 #define set_head(p, s)        ((p)->size = (s))
1327
1328 /* Set size at footer (only when chunk is not in use) */
1329
1330 #define set_foot(p, s)   (((mchunkptr)((char*)(p) + (s)))->prev_size = (s))
1331
1332
1333 \f
1334
1335
1336 /* access macros */
1337
1338 #define bin_at(a, i)   ((mbinptr)((char*)&(((a)->av)[2*(i) + 2]) - 2*SIZE_SZ))
1339 #define init_bin(a, i) ((a)->av[2*i+2] = (a)->av[2*i+3] = bin_at((a), i))
1340 #define next_bin(b)    ((mbinptr)((char*)(b) + 2 * sizeof(mbinptr)))
1341 #define prev_bin(b)    ((mbinptr)((char*)(b) - 2 * sizeof(mbinptr)))
1342
1343 /*
1344    The first 2 bins are never indexed. The corresponding av cells are instead
1345    used for bookkeeping. This is not to save space, but to simplify
1346    indexing, maintain locality, and avoid some initialization tests.
1347 */
1348
1349 #define binblocks(a)      (bin_at(a,0)->size)/* bitvector of nonempty blocks */
1350 #define top(a)            (bin_at(a,0)->fd)  /* The topmost chunk */
1351 #define last_remainder(a) (bin_at(a,1))      /* remainder from last split */
1352
1353 /*
1354    Because top initially points to its own bin with initial
1355    zero size, thus forcing extension on the first malloc request,
1356    we avoid having any special code in malloc to check whether
1357    it even exists yet. But we still need to in malloc_extend_top.
1358 */
1359
1360 #define initial_top(a)    ((mchunkptr)bin_at(a, 0))
1361
1362 \f
1363
1364 /* field-extraction macros */
1365
1366 #define first(b) ((b)->fd)
1367 #define last(b)  ((b)->bk)
1368
1369 /*
1370   Indexing into bins
1371 */
1372
1373 #define bin_index(sz)                                                          \
1374 (((((unsigned long)(sz)) >> 9) ==    0) ?       (((unsigned long)(sz)) >>  3): \
1375  ((((unsigned long)(sz)) >> 9) <=    4) ?  56 + (((unsigned long)(sz)) >>  6): \
1376  ((((unsigned long)(sz)) >> 9) <=   20) ?  91 + (((unsigned long)(sz)) >>  9): \
1377  ((((unsigned long)(sz)) >> 9) <=   84) ? 110 + (((unsigned long)(sz)) >> 12): \
1378  ((((unsigned long)(sz)) >> 9) <=  340) ? 119 + (((unsigned long)(sz)) >> 15): \
1379  ((((unsigned long)(sz)) >> 9) <= 1364) ? 124 + (((unsigned long)(sz)) >> 18): \
1380                                           126)
1381 /*
1382   bins for chunks < 512 are all spaced 8 bytes apart, and hold
1383   identically sized chunks. This is exploited in malloc.
1384 */
1385
1386 #define MAX_SMALLBIN         63
1387 #define MAX_SMALLBIN_SIZE   512
1388 #define SMALLBIN_WIDTH        8
1389
1390 #define smallbin_index(sz)  (((unsigned long)(sz)) >> 3)
1391
1392 /*
1393    Requests are `small' if both the corresponding and the next bin are small
1394 */
1395
1396 #define is_small_request(nb) ((nb) < MAX_SMALLBIN_SIZE - SMALLBIN_WIDTH)
1397
1398 \f
1399
1400 /*
1401     To help compensate for the large number of bins, a one-level index
1402     structure is used for bin-by-bin searching.  `binblocks' is a
1403     one-word bitvector recording whether groups of BINBLOCKWIDTH bins
1404     have any (possibly) non-empty bins, so they can be skipped over
1405     all at once during during traversals. The bits are NOT always
1406     cleared as soon as all bins in a block are empty, but instead only
1407     when all are noticed to be empty during traversal in malloc.
1408 */
1409
1410 #define BINBLOCKWIDTH     4   /* bins per block */
1411
1412 /* bin<->block macros */
1413
1414 #define idx2binblock(ix)      ((unsigned)1 << ((ix) / BINBLOCKWIDTH))
1415 #define mark_binblock(a, ii)  (binblocks(a) |= idx2binblock(ii))
1416 #define clear_binblock(a, ii) (binblocks(a) &= ~(idx2binblock(ii)))
1417
1418
1419 \f
1420
1421 /* Static bookkeeping data */
1422
1423 /* Helper macro to initialize bins */
1424 #define IAV(i) bin_at(&main_arena, i), bin_at(&main_arena, i)
1425
1426 static arena main_arena = {
1427     {
1428  0, 0,
1429  IAV(0),   IAV(1),   IAV(2),   IAV(3),   IAV(4),   IAV(5),   IAV(6),   IAV(7),
1430  IAV(8),   IAV(9),   IAV(10),  IAV(11),  IAV(12),  IAV(13),  IAV(14),  IAV(15),
1431  IAV(16),  IAV(17),  IAV(18),  IAV(19),  IAV(20),  IAV(21),  IAV(22),  IAV(23),
1432  IAV(24),  IAV(25),  IAV(26),  IAV(27),  IAV(28),  IAV(29),  IAV(30),  IAV(31),
1433  IAV(32),  IAV(33),  IAV(34),  IAV(35),  IAV(36),  IAV(37),  IAV(38),  IAV(39),
1434  IAV(40),  IAV(41),  IAV(42),  IAV(43),  IAV(44),  IAV(45),  IAV(46),  IAV(47),
1435  IAV(48),  IAV(49),  IAV(50),  IAV(51),  IAV(52),  IAV(53),  IAV(54),  IAV(55),
1436  IAV(56),  IAV(57),  IAV(58),  IAV(59),  IAV(60),  IAV(61),  IAV(62),  IAV(63),
1437  IAV(64),  IAV(65),  IAV(66),  IAV(67),  IAV(68),  IAV(69),  IAV(70),  IAV(71),
1438  IAV(72),  IAV(73),  IAV(74),  IAV(75),  IAV(76),  IAV(77),  IAV(78),  IAV(79),
1439  IAV(80),  IAV(81),  IAV(82),  IAV(83),  IAV(84),  IAV(85),  IAV(86),  IAV(87),
1440  IAV(88),  IAV(89),  IAV(90),  IAV(91),  IAV(92),  IAV(93),  IAV(94),  IAV(95),
1441  IAV(96),  IAV(97),  IAV(98),  IAV(99),  IAV(100), IAV(101), IAV(102), IAV(103),
1442  IAV(104), IAV(105), IAV(106), IAV(107), IAV(108), IAV(109), IAV(110), IAV(111),
1443  IAV(112), IAV(113), IAV(114), IAV(115), IAV(116), IAV(117), IAV(118), IAV(119),
1444  IAV(120), IAV(121), IAV(122), IAV(123), IAV(124), IAV(125), IAV(126), IAV(127)
1445     },
1446     &main_arena, /* next */
1447     0, /* size */
1448 #if THREAD_STATS
1449     0, 0, 0, /* stat_lock_direct, stat_lock_loop, stat_lock_wait */
1450 #endif
1451     MUTEX_INITIALIZER /* mutex */
1452 };
1453
1454 #undef IAV
1455
1456 /* Thread specific data */
1457
1458 #ifndef NO_THREADS
1459 static tsd_key_t arena_key;
1460 static mutex_t list_lock = MUTEX_INITIALIZER;
1461 #endif
1462
1463 #if THREAD_STATS
1464 static int stat_n_heaps = 0;
1465 #define THREAD_STAT(x) x
1466 #else
1467 #define THREAD_STAT(x) do ; while(0)
1468 #endif
1469
1470 /* variables holding tunable values */
1471
1472 static unsigned long trim_threshold   = DEFAULT_TRIM_THRESHOLD;
1473 static unsigned long top_pad          = DEFAULT_TOP_PAD;
1474 static unsigned int  n_mmaps_max      = DEFAULT_MMAP_MAX;
1475 static unsigned long mmap_threshold   = DEFAULT_MMAP_THRESHOLD;
1476 static int           check_action     = DEFAULT_CHECK_ACTION;
1477
1478 /* The first value returned from sbrk */
1479 static char* sbrk_base = (char*)(-1);
1480
1481 /* The maximum memory obtained from system via sbrk */
1482 static unsigned long max_sbrked_mem = 0;
1483
1484 /* The maximum via either sbrk or mmap (too difficult to track with threads) */
1485 #ifdef NO_THREADS
1486 static unsigned long max_total_mem = 0;
1487 #endif
1488
1489 /* The total memory obtained from system via sbrk */
1490 #define sbrked_mem (main_arena.size)
1491
1492 /* Tracking mmaps */
1493
1494 static unsigned int n_mmaps = 0;
1495 static unsigned int max_n_mmaps = 0;
1496 static unsigned long mmapped_mem = 0;
1497 static unsigned long max_mmapped_mem = 0;
1498
1499
1500 \f
1501 #ifndef _LIBC
1502 #define weak_variable
1503 #else
1504 /* In GNU libc we want the hook variables to be weak definitions to
1505    avoid a problem with Emacs.  */
1506 #define weak_variable weak_function
1507 #endif
1508
1509 /* Already initialized? */
1510 int __malloc_initialized = 0;
1511
1512
1513 /* Initialization routine. */
1514 #if defined(_LIBC)
1515 #if 0
1516 static void ptmalloc_init __MALLOC_P ((void)) __attribute__ ((constructor));
1517 #endif
1518
1519 static void
1520 ptmalloc_init __MALLOC_P((void))
1521 #else
1522 void
1523 ptmalloc_init __MALLOC_P((void))
1524 #endif
1525 {
1526 #if defined(_LIBC) || defined(MALLOC_HOOKS)
1527   __malloc_ptr_t (*save_malloc_hook) __MALLOC_P ((size_t __size));
1528   void (*save_free_hook) __MALLOC_P ((__malloc_ptr_t __ptr));
1529   const char* s;
1530 #endif
1531
1532   if(__malloc_initialized) return;
1533   __malloc_initialized = 1;
1534 #if defined(_LIBC) || defined(MALLOC_HOOKS)
1535   /* With some threads implementations, creating thread-specific data
1536      or initializing a mutex may call malloc() itself.  Provide a
1537      simple starter version (realloc() won't work). */
1538   save_malloc_hook = __malloc_hook;
1539   save_free_hook = __free_hook;
1540   __malloc_hook = malloc_starter;
1541   __free_hook = free_starter;
1542 #endif
1543 #if defined(_LIBC) && !defined (NO_THREADS)
1544   /* Initialize the pthreads interface. */
1545   if (__pthread_initialize != NULL)
1546     __pthread_initialize();
1547 #endif
1548 #ifndef NO_THREADS
1549   mutex_init(&main_arena.mutex);
1550   mutex_init(&list_lock);
1551   tsd_key_create(&arena_key, NULL);
1552   tsd_setspecific(arena_key, (Void_t *)&main_arena);
1553 #endif
1554 #if defined(_LIBC) || defined(MALLOC_HOOKS)
1555   if((s = getenv("MALLOC_TRIM_THRESHOLD_")))
1556     mALLOPt(M_TRIM_THRESHOLD, atoi(s));
1557   if((s = getenv("MALLOC_TOP_PAD_")))
1558     mALLOPt(M_TOP_PAD, atoi(s));
1559   if((s = getenv("MALLOC_MMAP_THRESHOLD_")))
1560     mALLOPt(M_MMAP_THRESHOLD, atoi(s));
1561   if((s = getenv("MALLOC_MMAP_MAX_")))
1562     mALLOPt(M_MMAP_MAX, atoi(s));
1563   s = getenv("MALLOC_CHECK_");
1564   __malloc_hook = save_malloc_hook;
1565   __free_hook = save_free_hook;
1566   if(s) {
1567     if(s[0]) mALLOPt(M_CHECK_ACTION, (int)(s[0] - '0'));
1568     __malloc_check_init();
1569   }
1570   if(__malloc_initialize_hook != NULL)
1571     (*__malloc_initialize_hook)();
1572 #endif
1573 }
1574
1575 #if defined(_LIBC) || defined(MALLOC_HOOKS)
1576
1577 /* Hooks for debugging versions.  The initial hooks just call the
1578    initialization routine, then do the normal work. */
1579
1580 static Void_t*
1581 #if __STD_C
1582 malloc_hook_ini(size_t sz)
1583 #else
1584 malloc_hook_ini(sz) size_t sz;
1585 #endif
1586 {
1587   __malloc_hook = NULL;
1588   __realloc_hook = NULL;
1589   __memalign_hook = NULL;
1590   ptmalloc_init();
1591   return mALLOc(sz);
1592 }
1593
1594 static Void_t*
1595 #if __STD_C
1596 realloc_hook_ini(Void_t* ptr, size_t sz)
1597 #else
1598 realloc_hook_ini(ptr, sz) Void_t* ptr; size_t sz;
1599 #endif
1600 {
1601   __malloc_hook = NULL;
1602   __realloc_hook = NULL;
1603   __memalign_hook = NULL;
1604   ptmalloc_init();
1605   return rEALLOc(ptr, sz);
1606 }
1607
1608 static Void_t*
1609 #if __STD_C
1610 memalign_hook_ini(size_t sz, size_t alignment)
1611 #else
1612 memalign_hook_ini(sz, alignment) size_t sz; size_t alignment;
1613 #endif
1614 {
1615   __malloc_hook = NULL;
1616   __realloc_hook = NULL;
1617   __memalign_hook = NULL;
1618   ptmalloc_init();
1619   return mEMALIGn(sz, alignment);
1620 }
1621
1622 void weak_variable (*__malloc_initialize_hook) __MALLOC_P ((void)) = NULL;
1623 void weak_variable (*__free_hook) __MALLOC_P ((__malloc_ptr_t __ptr)) = NULL;
1624 __malloc_ptr_t weak_variable (*__malloc_hook)
1625  __MALLOC_P ((size_t __size)) = malloc_hook_ini;
1626 __malloc_ptr_t weak_variable (*__realloc_hook)
1627  __MALLOC_P ((__malloc_ptr_t __ptr, size_t __size)) = realloc_hook_ini;
1628 __malloc_ptr_t weak_variable (*__memalign_hook)
1629  __MALLOC_P ((size_t __size, size_t __alignment)) = memalign_hook_ini;
1630 void weak_variable (*__after_morecore_hook) __MALLOC_P ((void)) = NULL;
1631
1632 /* Activate a standard set of debugging hooks. */
1633 void
1634 __malloc_check_init()
1635 {
1636   __malloc_hook = malloc_check;
1637   __free_hook = free_check;
1638   __realloc_hook = realloc_check;
1639   __memalign_hook = memalign_check;
1640   if(check_action == 1)
1641     fprintf(stderr, "malloc: using debugging hooks\n");
1642 }
1643
1644 #endif
1645
1646
1647 \f
1648
1649
1650 /* Routines dealing with mmap(). */
1651
1652 #if HAVE_MMAP
1653
1654 #ifndef MAP_ANONYMOUS
1655
1656 static int dev_zero_fd = -1; /* Cached file descriptor for /dev/zero. */
1657
1658 #define MMAP(size, prot) ((dev_zero_fd < 0) ? \
1659  (dev_zero_fd = open("/dev/zero", O_RDWR), \
1660   mmap(0, (size), (prot), MAP_PRIVATE, dev_zero_fd, 0)) : \
1661    mmap(0, (size), (prot), MAP_PRIVATE, dev_zero_fd, 0))
1662
1663 #else
1664
1665 #define MMAP(size, prot) \
1666  (mmap(0, (size), (prot), MAP_PRIVATE|MAP_ANONYMOUS, -1, 0))
1667
1668 #endif
1669
1670 #if __STD_C
1671 static mchunkptr mmap_chunk(size_t size)
1672 #else
1673 static mchunkptr mmap_chunk(size) size_t size;
1674 #endif
1675 {
1676   size_t page_mask = malloc_getpagesize - 1;
1677   mchunkptr p;
1678
1679   if(n_mmaps >= n_mmaps_max) return 0; /* too many regions */
1680
1681   /* For mmapped chunks, the overhead is one SIZE_SZ unit larger, because
1682    * there is no following chunk whose prev_size field could be used.
1683    */
1684   size = (size + SIZE_SZ + page_mask) & ~page_mask;
1685
1686   p = (mchunkptr)MMAP(size, PROT_READ|PROT_WRITE);
1687   if(p == (mchunkptr)-1) return 0;
1688
1689   n_mmaps++;
1690   if (n_mmaps > max_n_mmaps) max_n_mmaps = n_mmaps;
1691
1692   /* We demand that eight bytes into a page must be 8-byte aligned. */
1693   assert(aligned_OK(chunk2mem(p)));
1694
1695   /* The offset to the start of the mmapped region is stored
1696    * in the prev_size field of the chunk; normally it is zero,
1697    * but that can be changed in memalign().
1698    */
1699   p->prev_size = 0;
1700   set_head(p, size|IS_MMAPPED);
1701
1702   mmapped_mem += size;
1703   if ((unsigned long)mmapped_mem > (unsigned long)max_mmapped_mem)
1704     max_mmapped_mem = mmapped_mem;
1705 #ifdef NO_THREADS
1706   if ((unsigned long)(mmapped_mem + sbrked_mem) > (unsigned long)max_total_mem)
1707     max_total_mem = mmapped_mem + sbrked_mem;
1708 #endif
1709   return p;
1710 }
1711
1712 #if __STD_C
1713 static void munmap_chunk(mchunkptr p)
1714 #else
1715 static void munmap_chunk(p) mchunkptr p;
1716 #endif
1717 {
1718   INTERNAL_SIZE_T size = chunksize(p);
1719   int ret;
1720
1721   assert (chunk_is_mmapped(p));
1722   assert(! ((char*)p >= sbrk_base && (char*)p < sbrk_base + sbrked_mem));
1723   assert((n_mmaps > 0));
1724   assert(((p->prev_size + size) & (malloc_getpagesize-1)) == 0);
1725
1726   n_mmaps--;
1727   mmapped_mem -= (size + p->prev_size);
1728
1729   ret = munmap((char *)p - p->prev_size, size + p->prev_size);
1730
1731   /* munmap returns non-zero on failure */
1732   assert(ret == 0);
1733 }
1734
1735 #if HAVE_MREMAP
1736
1737 #if __STD_C
1738 static mchunkptr mremap_chunk(mchunkptr p, size_t new_size)
1739 #else
1740 static mchunkptr mremap_chunk(p, new_size) mchunkptr p; size_t new_size;
1741 #endif
1742 {
1743   size_t page_mask = malloc_getpagesize - 1;
1744   INTERNAL_SIZE_T offset = p->prev_size;
1745   INTERNAL_SIZE_T size = chunksize(p);
1746   char *cp;
1747
1748   assert (chunk_is_mmapped(p));
1749   assert(! ((char*)p >= sbrk_base && (char*)p < sbrk_base + sbrked_mem));
1750   assert((n_mmaps > 0));
1751   assert(((size + offset) & (malloc_getpagesize-1)) == 0);
1752
1753   /* Note the extra SIZE_SZ overhead as in mmap_chunk(). */
1754   new_size = (new_size + offset + SIZE_SZ + page_mask) & ~page_mask;
1755
1756   cp = (char *)mremap((char *)p - offset, size + offset, new_size,
1757                       MREMAP_MAYMOVE);
1758
1759   if (cp == (char *)-1) return 0;
1760
1761   p = (mchunkptr)(cp + offset);
1762
1763   assert(aligned_OK(chunk2mem(p)));
1764
1765   assert((p->prev_size == offset));
1766   set_head(p, (new_size - offset)|IS_MMAPPED);
1767
1768   mmapped_mem -= size + offset;
1769   mmapped_mem += new_size;
1770   if ((unsigned long)mmapped_mem > (unsigned long)max_mmapped_mem)
1771     max_mmapped_mem = mmapped_mem;
1772 #ifdef NO_THREADS
1773   if ((unsigned long)(mmapped_mem + sbrked_mem) > (unsigned long)max_total_mem)
1774     max_total_mem = mmapped_mem + sbrked_mem;
1775 #endif
1776   return p;
1777 }
1778
1779 #endif /* HAVE_MREMAP */
1780
1781 #endif /* HAVE_MMAP */
1782
1783 \f
1784
1785 /* Managing heaps and arenas (for concurrent threads) */
1786
1787 #ifndef NO_THREADS
1788
1789 /* Create a new heap.  size is automatically rounded up to a multiple
1790    of the page size. */
1791
1792 static heap_info *
1793 #if __STD_C
1794 new_heap(size_t size)
1795 #else
1796 new_heap(size) size_t size;
1797 #endif
1798 {
1799   size_t page_mask = malloc_getpagesize - 1;
1800   char *p1, *p2;
1801   unsigned long ul;
1802   heap_info *h;
1803
1804   if(size < HEAP_MIN_SIZE)
1805     size = HEAP_MIN_SIZE;
1806   size = (size + page_mask) & ~page_mask;
1807   if(size > HEAP_MAX_SIZE)
1808     return 0;
1809   p1 = (char *)MMAP(HEAP_MAX_SIZE<<1, PROT_NONE);
1810   if(p1 == (char *)-1)
1811     return 0;
1812   p2 = (char *)(((unsigned long)p1 + HEAP_MAX_SIZE) & ~(HEAP_MAX_SIZE-1));
1813   ul = p2 - p1;
1814   munmap(p1, ul);
1815   munmap(p2 + HEAP_MAX_SIZE, HEAP_MAX_SIZE - ul);
1816   if(mprotect(p2, size, PROT_READ|PROT_WRITE) != 0) {
1817     munmap(p2, HEAP_MAX_SIZE);
1818     return 0;
1819   }
1820   h = (heap_info *)p2;
1821   h->size = size;
1822   THREAD_STAT(stat_n_heaps++);
1823   return h;
1824 }
1825
1826 /* Grow or shrink a heap.  size is automatically rounded up to a
1827    multiple of the page size if it is positive. */
1828
1829 static int
1830 #if __STD_C
1831 grow_heap(heap_info *h, long diff)
1832 #else
1833 grow_heap(h, diff) heap_info *h; long diff;
1834 #endif
1835 {
1836   size_t page_mask = malloc_getpagesize - 1;
1837   long new_size;
1838
1839   if(diff >= 0) {
1840     diff = (diff + page_mask) & ~page_mask;
1841     new_size = (long)h->size + diff;
1842     if(new_size > HEAP_MAX_SIZE)
1843       return -1;
1844     if(mprotect((char *)h + h->size, diff, PROT_READ|PROT_WRITE) != 0)
1845       return -2;
1846   } else {
1847     new_size = (long)h->size + diff;
1848     if(new_size < (long)sizeof(*h))
1849       return -1;
1850     if(mprotect((char *)h + new_size, -diff, PROT_NONE) != 0)
1851       return -2;
1852   }
1853   h->size = new_size;
1854   return 0;
1855 }
1856
1857 /* Delete a heap. */
1858
1859 #define delete_heap(heap) munmap((char*)(heap), HEAP_MAX_SIZE)
1860
1861 /* arena_get() acquires an arena and locks the corresponding mutex.
1862    First, try the one last locked successfully by this thread.  (This
1863    is the common case and handled with a macro for speed.)  Then, loop
1864    once over the circularly linked list of arenas.  If no arena is
1865    readily available, create a new one. */
1866
1867 #define arena_get(ptr, size) do { \
1868   Void_t *vptr = NULL; \
1869   ptr = (arena *)tsd_getspecific(arena_key, vptr); \
1870   if(ptr && !mutex_trylock(&ptr->mutex)) { \
1871     THREAD_STAT(++(ptr->stat_lock_direct)); \
1872   } else \
1873     ptr = arena_get2(ptr, (size)); \
1874 } while(0)
1875
1876 static arena *
1877 #if __STD_C
1878 arena_get2(arena *a_tsd, size_t size)
1879 #else
1880 arena_get2(a_tsd, size) arena *a_tsd; size_t size;
1881 #endif
1882 {
1883   arena *a;
1884   heap_info *h;
1885   char *ptr;
1886   int i;
1887   unsigned long misalign;
1888
1889   if(!a_tsd)
1890     a = a_tsd = &main_arena;
1891   else {
1892     a = a_tsd->next;
1893     if(!a) {
1894       /* This can only happen while initializing the new arena. */
1895       (void)mutex_lock(&main_arena.mutex);
1896       THREAD_STAT(++(main_arena.stat_lock_wait));
1897       return &main_arena;
1898     }
1899   }
1900
1901   /* Check the global, circularly linked list for available arenas. */
1902   do {
1903     if(!mutex_trylock(&a->mutex)) {
1904       THREAD_STAT(++(a->stat_lock_loop));
1905       tsd_setspecific(arena_key, (Void_t *)a);
1906       return a;
1907     }
1908     a = a->next;
1909   } while(a != a_tsd);
1910
1911   /* Nothing immediately available, so generate a new arena. */
1912   h = new_heap(size + (sizeof(*h) + sizeof(*a) + MALLOC_ALIGNMENT));
1913   if(!h)
1914     return 0;
1915   a = h->ar_ptr = (arena *)(h+1);
1916   for(i=0; i<NAV; i++)
1917     init_bin(a, i);
1918   a->next = NULL;
1919   a->size = h->size;
1920   tsd_setspecific(arena_key, (Void_t *)a);
1921   mutex_init(&a->mutex);
1922   i = mutex_lock(&a->mutex); /* remember result */
1923
1924   /* Set up the top chunk, with proper alignment. */
1925   ptr = (char *)(a + 1);
1926   misalign = (unsigned long)chunk2mem(ptr) & MALLOC_ALIGN_MASK;
1927   if (misalign > 0)
1928     ptr += MALLOC_ALIGNMENT - misalign;
1929   top(a) = (mchunkptr)ptr;
1930   set_head(top(a), (((char*)h + h->size) - ptr) | PREV_INUSE);
1931
1932   /* Add the new arena to the list. */
1933   (void)mutex_lock(&list_lock);
1934   a->next = main_arena.next;
1935   main_arena.next = a;
1936   (void)mutex_unlock(&list_lock);
1937
1938   if(i) /* locking failed; keep arena for further attempts later */
1939     return 0;
1940
1941   THREAD_STAT(++(a->stat_lock_loop));
1942   return a;
1943 }
1944
1945 /* find the heap and corresponding arena for a given ptr */
1946
1947 #define heap_for_ptr(ptr) \
1948  ((heap_info *)((unsigned long)(ptr) & ~(HEAP_MAX_SIZE-1)))
1949 #define arena_for_ptr(ptr) \
1950  (((mchunkptr)(ptr) < top(&main_arena) && (char *)(ptr) >= sbrk_base) ? \
1951   &main_arena : heap_for_ptr(ptr)->ar_ptr)
1952
1953 #else /* defined(NO_THREADS) */
1954
1955 /* Without concurrent threads, there is only one arena. */
1956
1957 #define arena_get(ptr, sz) (ptr = &main_arena)
1958 #define arena_for_ptr(ptr) (&main_arena)
1959
1960 #endif /* !defined(NO_THREADS) */
1961
1962 \f
1963
1964 /*
1965   Debugging support
1966 */
1967
1968 #if MALLOC_DEBUG
1969
1970
1971 /*
1972   These routines make a number of assertions about the states
1973   of data structures that should be true at all times. If any
1974   are not true, it's very likely that a user program has somehow
1975   trashed memory. (It's also possible that there is a coding error
1976   in malloc. In which case, please report it!)
1977 */
1978
1979 #if __STD_C
1980 static void do_check_chunk(arena *ar_ptr, mchunkptr p)
1981 #else
1982 static void do_check_chunk(ar_ptr, p) arena *ar_ptr; mchunkptr p;
1983 #endif
1984 {
1985   INTERNAL_SIZE_T sz = p->size & ~PREV_INUSE;
1986
1987   /* No checkable chunk is mmapped */
1988   assert(!chunk_is_mmapped(p));
1989
1990 #ifndef NO_THREADS
1991   if(ar_ptr != &main_arena) {
1992     heap_info *heap = heap_for_ptr(p);
1993     assert(heap->ar_ptr == ar_ptr);
1994     assert((char *)p + sz <= (char *)heap + heap->size);
1995     return;
1996   }
1997 #endif
1998
1999   /* Check for legal address ... */
2000   assert((char*)p >= sbrk_base);
2001   if (p != top(ar_ptr))
2002     assert((char*)p + sz <= (char*)top(ar_ptr));
2003   else
2004     assert((char*)p + sz <= sbrk_base + sbrked_mem);
2005
2006 }
2007
2008
2009 #if __STD_C
2010 static void do_check_free_chunk(arena *ar_ptr, mchunkptr p)
2011 #else
2012 static void do_check_free_chunk(ar_ptr, p) arena *ar_ptr; mchunkptr p;
2013 #endif
2014 {
2015   INTERNAL_SIZE_T sz = p->size & ~PREV_INUSE;
2016   mchunkptr next = chunk_at_offset(p, sz);
2017
2018   do_check_chunk(ar_ptr, p);
2019
2020   /* Check whether it claims to be free ... */
2021   assert(!inuse(p));
2022
2023   /* Must have OK size and fields */
2024   assert((long)sz >= (long)MINSIZE);
2025   assert((sz & MALLOC_ALIGN_MASK) == 0);
2026   assert(aligned_OK(chunk2mem(p)));
2027   /* ... matching footer field */
2028   assert(next->prev_size == sz);
2029   /* ... and is fully consolidated */
2030   assert(prev_inuse(p));
2031   assert (next == top(ar_ptr) || inuse(next));
2032
2033   /* ... and has minimally sane links */
2034   assert(p->fd->bk == p);
2035   assert(p->bk->fd == p);
2036 }
2037
2038 #if __STD_C
2039 static void do_check_inuse_chunk(arena *ar_ptr, mchunkptr p)
2040 #else
2041 static void do_check_inuse_chunk(ar_ptr, p) arena *ar_ptr; mchunkptr p;
2042 #endif
2043 {
2044   mchunkptr next = next_chunk(p);
2045   do_check_chunk(ar_ptr, p);
2046
2047   /* Check whether it claims to be in use ... */
2048   assert(inuse(p));
2049
2050   /* ... whether its size is OK (it might be a fencepost) ... */
2051   assert(chunksize(p) >= MINSIZE || next->size == (0|PREV_INUSE));
2052
2053   /* ... and is surrounded by OK chunks.
2054     Since more things can be checked with free chunks than inuse ones,
2055     if an inuse chunk borders them and debug is on, it's worth doing them.
2056   */
2057   if (!prev_inuse(p))
2058   {
2059     mchunkptr prv = prev_chunk(p);
2060     assert(next_chunk(prv) == p);
2061     do_check_free_chunk(ar_ptr, prv);
2062   }
2063   if (next == top(ar_ptr))
2064   {
2065     assert(prev_inuse(next));
2066     assert(chunksize(next) >= MINSIZE);
2067   }
2068   else if (!inuse(next))
2069     do_check_free_chunk(ar_ptr, next);
2070
2071 }
2072
2073 #if __STD_C
2074 static void do_check_malloced_chunk(arena *ar_ptr,
2075                                     mchunkptr p, INTERNAL_SIZE_T s)
2076 #else
2077 static void do_check_malloced_chunk(ar_ptr, p, s)
2078 arena *ar_ptr; mchunkptr p; INTERNAL_SIZE_T s;
2079 #endif
2080 {
2081   INTERNAL_SIZE_T sz = p->size & ~PREV_INUSE;
2082   long room = sz - s;
2083
2084   do_check_inuse_chunk(ar_ptr, p);
2085
2086   /* Legal size ... */
2087   assert((long)sz >= (long)MINSIZE);
2088   assert((sz & MALLOC_ALIGN_MASK) == 0);
2089   assert(room >= 0);
2090   assert(room < (long)MINSIZE);
2091
2092   /* ... and alignment */
2093   assert(aligned_OK(chunk2mem(p)));
2094
2095
2096   /* ... and was allocated at front of an available chunk */
2097   assert(prev_inuse(p));
2098
2099 }
2100
2101
2102 #define check_free_chunk(A,P) do_check_free_chunk(A,P)
2103 #define check_inuse_chunk(A,P) do_check_inuse_chunk(A,P)
2104 #define check_chunk(A,P) do_check_chunk(A,P)
2105 #define check_malloced_chunk(A,P,N) do_check_malloced_chunk(A,P,N)
2106 #else
2107 #define check_free_chunk(A,P)
2108 #define check_inuse_chunk(A,P)
2109 #define check_chunk(A,P)
2110 #define check_malloced_chunk(A,P,N)
2111 #endif
2112
2113 \f
2114
2115 /*
2116   Macro-based internal utilities
2117 */
2118
2119
2120 /*
2121   Linking chunks in bin lists.
2122   Call these only with variables, not arbitrary expressions, as arguments.
2123 */
2124
2125 /*
2126   Place chunk p of size s in its bin, in size order,
2127   putting it ahead of others of same size.
2128 */
2129
2130
2131 #define frontlink(A, P, S, IDX, BK, FD)                                       \
2132 {                                                                             \
2133   if (S < MAX_SMALLBIN_SIZE)                                                  \
2134   {                                                                           \
2135     IDX = smallbin_index(S);                                                  \
2136     mark_binblock(A, IDX);                                                    \
2137     BK = bin_at(A, IDX);                                                      \
2138     FD = BK->fd;                                                              \
2139     P->bk = BK;                                                               \
2140     P->fd = FD;                                                               \
2141     FD->bk = BK->fd = P;                                                      \
2142   }                                                                           \
2143   else                                                                        \
2144   {                                                                           \
2145     IDX = bin_index(S);                                                       \
2146     BK = bin_at(A, IDX);                                                      \
2147     FD = BK->fd;                                                              \
2148     if (FD == BK) mark_binblock(A, IDX);                                      \
2149     else                                                                      \
2150     {                                                                         \
2151       while (FD != BK && S < chunksize(FD)) FD = FD->fd;                      \
2152       BK = FD->bk;                                                            \
2153     }                                                                         \
2154     P->bk = BK;                                                               \
2155     P->fd = FD;                                                               \
2156     FD->bk = BK->fd = P;                                                      \
2157   }                                                                           \
2158 }
2159
2160
2161 /* take a chunk off a list */
2162
2163 #define unlink(P, BK, FD)                                                     \
2164 {                                                                             \
2165   BK = P->bk;                                                                 \
2166   FD = P->fd;                                                                 \
2167   FD->bk = BK;                                                                \
2168   BK->fd = FD;                                                                \
2169 }                                                                             \
2170
2171 /* Place p as the last remainder */
2172
2173 #define link_last_remainder(A, P)                                             \
2174 {                                                                             \
2175   last_remainder(A)->fd = last_remainder(A)->bk = P;                          \
2176   P->fd = P->bk = last_remainder(A);                                          \
2177 }
2178
2179 /* Clear the last_remainder bin */
2180
2181 #define clear_last_remainder(A) \
2182   (last_remainder(A)->fd = last_remainder(A)->bk = last_remainder(A))
2183
2184
2185
2186 \f
2187
2188 /*
2189   Extend the top-most chunk by obtaining memory from system.
2190   Main interface to sbrk (but see also malloc_trim).
2191 */
2192
2193 #if __STD_C
2194 static void malloc_extend_top(arena *ar_ptr, INTERNAL_SIZE_T nb)
2195 #else
2196 static void malloc_extend_top(ar_ptr, nb) arena *ar_ptr; INTERNAL_SIZE_T nb;
2197 #endif
2198 {
2199   unsigned long pagesz   = malloc_getpagesize;
2200   mchunkptr old_top      = top(ar_ptr);        /* Record state of old top */
2201   INTERNAL_SIZE_T old_top_size = chunksize(old_top);
2202   INTERNAL_SIZE_T top_size;                    /* new size of top chunk */
2203
2204 #ifndef NO_THREADS
2205   if(ar_ptr == &main_arena) {
2206 #endif
2207
2208     char*     brk;                  /* return value from sbrk */
2209     INTERNAL_SIZE_T front_misalign; /* unusable bytes at front of sbrked space */
2210     INTERNAL_SIZE_T correction;     /* bytes for 2nd sbrk call */
2211     char*     new_brk;              /* return of 2nd sbrk call */
2212     char*     old_end = (char*)(chunk_at_offset(old_top, old_top_size));
2213
2214     /* Pad request with top_pad plus minimal overhead */
2215     INTERNAL_SIZE_T sbrk_size = nb + top_pad + MINSIZE;
2216
2217     /* If not the first time through, round to preserve page boundary */
2218     /* Otherwise, we need to correct to a page size below anyway. */
2219     /* (We also correct below if an intervening foreign sbrk call.) */
2220
2221     if (sbrk_base != (char*)(-1))
2222       sbrk_size = (sbrk_size + (pagesz - 1)) & ~(pagesz - 1);
2223
2224     brk = (char*)(MORECORE (sbrk_size));
2225
2226     /* Fail if sbrk failed or if a foreign sbrk call killed our space */
2227     if (brk == (char*)(MORECORE_FAILURE) ||
2228         (brk < old_end && old_top != initial_top(&main_arena)))
2229       return;
2230
2231     /* Call the `morecore' hook if necessary.  */
2232     if (__after_morecore_hook)
2233       (*__after_morecore_hook) ();
2234
2235     sbrked_mem += sbrk_size;
2236
2237     if (brk == old_end) { /* can just add bytes to current top */
2238       top_size = sbrk_size + old_top_size;
2239       set_head(old_top, top_size | PREV_INUSE);
2240       old_top = 0; /* don't free below */
2241     } else {
2242       if (sbrk_base == (char*)(-1)) /* First time through. Record base */
2243         sbrk_base = brk;
2244       else
2245         /* Someone else called sbrk().  Count those bytes as sbrked_mem. */
2246         sbrked_mem += brk - (char*)old_end;
2247
2248       /* Guarantee alignment of first new chunk made from this space */
2249       front_misalign = (unsigned long)chunk2mem(brk) & MALLOC_ALIGN_MASK;
2250       if (front_misalign > 0) {
2251         correction = (MALLOC_ALIGNMENT) - front_misalign;
2252         brk += correction;
2253       } else
2254         correction = 0;
2255
2256       /* Guarantee the next brk will be at a page boundary */
2257       correction += pagesz - ((unsigned long)(brk + sbrk_size) & (pagesz - 1));
2258
2259       /* Allocate correction */
2260       new_brk = (char*)(MORECORE (correction));
2261       if (new_brk == (char*)(MORECORE_FAILURE)) return;
2262
2263       /* Call the `morecore' hook if necessary.  */
2264       if (__after_morecore_hook)
2265         (*__after_morecore_hook) ();
2266
2267       sbrked_mem += correction;
2268
2269       top(&main_arena) = (mchunkptr)brk;
2270       top_size = new_brk - brk + correction;
2271       set_head(top(&main_arena), top_size | PREV_INUSE);
2272
2273       if (old_top == initial_top(&main_arena))
2274         old_top = 0; /* don't free below */
2275     }
2276
2277     if ((unsigned long)sbrked_mem > (unsigned long)max_sbrked_mem)
2278       max_sbrked_mem = sbrked_mem;
2279 #ifdef NO_THREADS
2280     if ((unsigned long)(mmapped_mem + sbrked_mem) >
2281         (unsigned long)max_total_mem)
2282       max_total_mem = mmapped_mem + sbrked_mem;
2283 #endif
2284
2285 #ifndef NO_THREADS
2286   } else { /* ar_ptr != &main_arena */
2287     heap_info *old_heap, *heap;
2288     size_t old_heap_size;
2289
2290     if(old_top_size < MINSIZE) /* this should never happen */
2291       return;
2292
2293     /* First try to extend the current heap. */
2294     if(MINSIZE + nb <= old_top_size)
2295       return;
2296     old_heap = heap_for_ptr(old_top);
2297     old_heap_size = old_heap->size;
2298     if(grow_heap(old_heap, MINSIZE + nb - old_top_size) == 0) {
2299       ar_ptr->size += old_heap->size - old_heap_size;
2300       top_size = ((char *)old_heap + old_heap->size) - (char *)old_top;
2301       set_head(old_top, top_size | PREV_INUSE);
2302       return;
2303     }
2304
2305     /* A new heap must be created. */
2306     heap = new_heap(nb + top_pad + (MINSIZE + sizeof(*heap)));
2307     if(!heap)
2308       return;
2309     heap->ar_ptr = ar_ptr;
2310     heap->prev = old_heap;
2311     ar_ptr->size += heap->size;
2312
2313     /* Set up the new top, so we can safely use chunk_free() below. */
2314     top(ar_ptr) = chunk_at_offset(heap, sizeof(*heap));
2315     top_size = heap->size - sizeof(*heap);
2316     set_head(top(ar_ptr), top_size | PREV_INUSE);
2317   }
2318 #endif /* !defined(NO_THREADS) */
2319
2320   /* We always land on a page boundary */
2321   assert(((unsigned long)((char*)top(ar_ptr) + top_size) & (pagesz-1)) == 0);
2322
2323   /* Setup fencepost and free the old top chunk. */
2324   if(old_top) {
2325     /* The fencepost takes at least MINSIZE bytes, because it might
2326        become the top chunk again later.  Note that a footer is set
2327        up, too, although the chunk is marked in use. */
2328     old_top_size -= MINSIZE;
2329     set_head(chunk_at_offset(old_top, old_top_size + 2*SIZE_SZ), 0|PREV_INUSE);
2330     if(old_top_size >= MINSIZE) {
2331       set_head(chunk_at_offset(old_top, old_top_size), (2*SIZE_SZ)|PREV_INUSE);
2332       set_foot(chunk_at_offset(old_top, old_top_size), (2*SIZE_SZ));
2333       set_head_size(old_top, old_top_size);
2334       chunk_free(ar_ptr, old_top);
2335     } else {
2336       set_head(old_top, (old_top_size + 2*SIZE_SZ)|PREV_INUSE);
2337       set_foot(old_top, (old_top_size + 2*SIZE_SZ));
2338     }
2339   }
2340 }
2341
2342
2343 \f
2344
2345 /* Main public routines */
2346
2347
2348 /*
2349   Malloc Algorithm:
2350
2351     The requested size is first converted into a usable form, `nb'.
2352     This currently means to add 4 bytes overhead plus possibly more to
2353     obtain 8-byte alignment and/or to obtain a size of at least
2354     MINSIZE (currently 16, 24, or 32 bytes), the smallest allocatable
2355     size.  (All fits are considered `exact' if they are within MINSIZE
2356     bytes.)
2357
2358     From there, the first successful of the following steps is taken:
2359
2360       1. The bin corresponding to the request size is scanned, and if
2361          a chunk of exactly the right size is found, it is taken.
2362
2363       2. The most recently remaindered chunk is used if it is big
2364          enough.  This is a form of (roving) first fit, used only in
2365          the absence of exact fits. Runs of consecutive requests use
2366          the remainder of the chunk used for the previous such request
2367          whenever possible. This limited use of a first-fit style
2368          allocation strategy tends to give contiguous chunks
2369          coextensive lifetimes, which improves locality and can reduce
2370          fragmentation in the long run.
2371
2372       3. Other bins are scanned in increasing size order, using a
2373          chunk big enough to fulfill the request, and splitting off
2374          any remainder.  This search is strictly by best-fit; i.e.,
2375          the smallest (with ties going to approximately the least
2376          recently used) chunk that fits is selected.
2377
2378       4. If large enough, the chunk bordering the end of memory
2379          (`top') is split off. (This use of `top' is in accord with
2380          the best-fit search rule.  In effect, `top' is treated as
2381          larger (and thus less well fitting) than any other available
2382          chunk since it can be extended to be as large as necessary
2383          (up to system limitations).
2384
2385       5. If the request size meets the mmap threshold and the
2386          system supports mmap, and there are few enough currently
2387          allocated mmapped regions, and a call to mmap succeeds,
2388          the request is allocated via direct memory mapping.
2389
2390       6. Otherwise, the top of memory is extended by
2391          obtaining more space from the system (normally using sbrk,
2392          but definable to anything else via the MORECORE macro).
2393          Memory is gathered from the system (in system page-sized
2394          units) in a way that allows chunks obtained across different
2395          sbrk calls to be consolidated, but does not require
2396          contiguous memory. Thus, it should be safe to intersperse
2397          mallocs with other sbrk calls.
2398
2399
2400       All allocations are made from the the `lowest' part of any found
2401       chunk. (The implementation invariant is that prev_inuse is
2402       always true of any allocated chunk; i.e., that each allocated
2403       chunk borders either a previously allocated and still in-use chunk,
2404       or the base of its memory arena.)
2405
2406 */
2407
2408 #if __STD_C
2409 Void_t* mALLOc(size_t bytes)
2410 #else
2411 Void_t* mALLOc(bytes) size_t bytes;
2412 #endif
2413 {
2414   arena *ar_ptr;
2415   INTERNAL_SIZE_T nb; /* padded request size */
2416   mchunkptr victim;
2417
2418 #if defined(_LIBC) || defined(MALLOC_HOOKS)
2419   if (__malloc_hook != NULL) {
2420     Void_t* result;
2421
2422     result = (*__malloc_hook)(bytes);
2423     return result;
2424   }
2425 #endif
2426
2427   nb = request2size(bytes);
2428   arena_get(ar_ptr, nb + top_pad);
2429   if(!ar_ptr)
2430     return 0;
2431   victim = chunk_alloc(ar_ptr, nb);
2432   (void)mutex_unlock(&ar_ptr->mutex);
2433   return victim ? chunk2mem(victim) : 0;
2434 }
2435
2436 static mchunkptr
2437 #if __STD_C
2438 chunk_alloc(arena *ar_ptr, INTERNAL_SIZE_T nb)
2439 #else
2440 chunk_alloc(ar_ptr, nb) arena *ar_ptr; INTERNAL_SIZE_T nb;
2441 #endif
2442 {
2443   mchunkptr victim;                  /* inspected/selected chunk */
2444   INTERNAL_SIZE_T victim_size;       /* its size */
2445   int       idx;                     /* index for bin traversal */
2446   mbinptr   bin;                     /* associated bin */
2447   mchunkptr remainder;               /* remainder from a split */
2448   long      remainder_size;          /* its size */
2449   int       remainder_index;         /* its bin index */
2450   unsigned long block;               /* block traverser bit */
2451   int       startidx;                /* first bin of a traversed block */
2452   mchunkptr fwd;                     /* misc temp for linking */
2453   mchunkptr bck;                     /* misc temp for linking */
2454   mbinptr q;                         /* misc temp */
2455
2456
2457   /* Check for exact match in a bin */
2458
2459   if (is_small_request(nb))  /* Faster version for small requests */
2460   {
2461     idx = smallbin_index(nb);
2462
2463     /* No traversal or size check necessary for small bins.  */
2464
2465     q = bin_at(ar_ptr, idx);
2466     victim = last(q);
2467
2468     /* Also scan the next one, since it would have a remainder < MINSIZE */
2469     if (victim == q)
2470     {
2471       q = next_bin(q);
2472       victim = last(q);
2473     }
2474     if (victim != q)
2475     {
2476       victim_size = chunksize(victim);
2477       unlink(victim, bck, fwd);
2478       set_inuse_bit_at_offset(victim, victim_size);
2479       check_malloced_chunk(ar_ptr, victim, nb);
2480       return victim;
2481     }
2482
2483     idx += 2; /* Set for bin scan below. We've already scanned 2 bins. */
2484
2485   }
2486   else
2487   {
2488     idx = bin_index(nb);
2489     bin = bin_at(ar_ptr, idx);
2490
2491     for (victim = last(bin); victim != bin; victim = victim->bk)
2492     {
2493       victim_size = chunksize(victim);
2494       remainder_size = victim_size - nb;
2495
2496       if (remainder_size >= (long)MINSIZE) /* too big */
2497       {
2498         --idx; /* adjust to rescan below after checking last remainder */
2499         break;
2500       }
2501
2502       else if (remainder_size >= 0) /* exact fit */
2503       {
2504         unlink(victim, bck, fwd);
2505         set_inuse_bit_at_offset(victim, victim_size);
2506         check_malloced_chunk(ar_ptr, victim, nb);
2507         return victim;
2508       }
2509     }
2510
2511     ++idx;
2512
2513   }
2514
2515   /* Try to use the last split-off remainder */
2516
2517   if ( (victim = last_remainder(ar_ptr)->fd) != last_remainder(ar_ptr))
2518   {
2519     victim_size = chunksize(victim);
2520     remainder_size = victim_size - nb;
2521
2522     if (remainder_size >= (long)MINSIZE) /* re-split */
2523     {
2524       remainder = chunk_at_offset(victim, nb);
2525       set_head(victim, nb | PREV_INUSE);
2526       link_last_remainder(ar_ptr, remainder);
2527       set_head(remainder, remainder_size | PREV_INUSE);
2528       set_foot(remainder, remainder_size);
2529       check_malloced_chunk(ar_ptr, victim, nb);
2530       return victim;
2531     }
2532
2533     clear_last_remainder(ar_ptr);
2534
2535     if (remainder_size >= 0)  /* exhaust */
2536     {
2537       set_inuse_bit_at_offset(victim, victim_size);
2538       check_malloced_chunk(ar_ptr, victim, nb);
2539       return victim;
2540     }
2541
2542     /* Else place in bin */
2543
2544     frontlink(ar_ptr, victim, victim_size, remainder_index, bck, fwd);
2545   }
2546
2547   /*
2548      If there are any possibly nonempty big-enough blocks,
2549      search for best fitting chunk by scanning bins in blockwidth units.
2550   */
2551
2552   if ( (block = idx2binblock(idx)) <= binblocks(ar_ptr))
2553   {
2554
2555     /* Get to the first marked block */
2556
2557     if ( (block & binblocks(ar_ptr)) == 0)
2558     {
2559       /* force to an even block boundary */
2560       idx = (idx & ~(BINBLOCKWIDTH - 1)) + BINBLOCKWIDTH;
2561       block <<= 1;
2562       while ((block & binblocks(ar_ptr)) == 0)
2563       {
2564         idx += BINBLOCKWIDTH;
2565         block <<= 1;
2566       }
2567     }
2568
2569     /* For each possibly nonempty block ... */
2570     for (;;)
2571     {
2572       startidx = idx;          /* (track incomplete blocks) */
2573       q = bin = bin_at(ar_ptr, idx);
2574
2575       /* For each bin in this block ... */
2576       do
2577       {
2578         /* Find and use first big enough chunk ... */
2579
2580         for (victim = last(bin); victim != bin; victim = victim->bk)
2581         {
2582           victim_size = chunksize(victim);
2583           remainder_size = victim_size - nb;
2584
2585           if (remainder_size >= (long)MINSIZE) /* split */
2586           {
2587             remainder = chunk_at_offset(victim, nb);
2588             set_head(victim, nb | PREV_INUSE);
2589             unlink(victim, bck, fwd);
2590             link_last_remainder(ar_ptr, remainder);
2591             set_head(remainder, remainder_size | PREV_INUSE);
2592             set_foot(remainder, remainder_size);
2593             check_malloced_chunk(ar_ptr, victim, nb);
2594             return victim;
2595           }
2596
2597           else if (remainder_size >= 0)  /* take */
2598           {
2599             set_inuse_bit_at_offset(victim, victim_size);
2600             unlink(victim, bck, fwd);
2601             check_malloced_chunk(ar_ptr, victim, nb);
2602             return victim;
2603           }
2604
2605         }
2606
2607        bin = next_bin(bin);
2608
2609       } while ((++idx & (BINBLOCKWIDTH - 1)) != 0);
2610
2611       /* Clear out the block bit. */
2612
2613       do   /* Possibly backtrack to try to clear a partial block */
2614       {
2615         if ((startidx & (BINBLOCKWIDTH - 1)) == 0)
2616         {
2617           binblocks(ar_ptr) &= ~block;
2618           break;
2619         }
2620         --startidx;
2621         q = prev_bin(q);
2622       } while (first(q) == q);
2623
2624       /* Get to the next possibly nonempty block */
2625
2626       if ( (block <<= 1) <= binblocks(ar_ptr) && (block != 0) )
2627       {
2628         while ((block & binblocks(ar_ptr)) == 0)
2629         {
2630           idx += BINBLOCKWIDTH;
2631           block <<= 1;
2632         }
2633       }
2634       else
2635         break;
2636     }
2637   }
2638
2639
2640   /* Try to use top chunk */
2641
2642   /* Require that there be a remainder, ensuring top always exists  */
2643   if ( (remainder_size = chunksize(top(ar_ptr)) - nb) < (long)MINSIZE)
2644   {
2645
2646 #if HAVE_MMAP
2647     /* If big and would otherwise need to extend, try to use mmap instead */
2648     if ((unsigned long)nb >= (unsigned long)mmap_threshold &&
2649         (victim = mmap_chunk(nb)) != 0)
2650       return victim;
2651 #endif
2652
2653     /* Try to extend */
2654     malloc_extend_top(ar_ptr, nb);
2655     if ((remainder_size = chunksize(top(ar_ptr)) - nb) < (long)MINSIZE)
2656       return 0; /* propagate failure */
2657   }
2658
2659   victim = top(ar_ptr);
2660   set_head(victim, nb | PREV_INUSE);
2661   top(ar_ptr) = chunk_at_offset(victim, nb);
2662   set_head(top(ar_ptr), remainder_size | PREV_INUSE);
2663   check_malloced_chunk(ar_ptr, victim, nb);
2664   return victim;
2665
2666 }
2667
2668
2669 \f
2670
2671 /*
2672
2673   free() algorithm :
2674
2675     cases:
2676
2677        1. free(0) has no effect.
2678
2679        2. If the chunk was allocated via mmap, it is released via munmap().
2680
2681        3. If a returned chunk borders the current high end of memory,
2682           it is consolidated into the top, and if the total unused
2683           topmost memory exceeds the trim threshold, malloc_trim is
2684           called.
2685
2686        4. Other chunks are consolidated as they arrive, and
2687           placed in corresponding bins. (This includes the case of
2688           consolidating with the current `last_remainder').
2689
2690 */
2691
2692
2693 #if __STD_C
2694 void fREe(Void_t* mem)
2695 #else
2696 void fREe(mem) Void_t* mem;
2697 #endif
2698 {
2699   arena *ar_ptr;
2700   mchunkptr p;                          /* chunk corresponding to mem */
2701
2702 #if defined(_LIBC) || defined(MALLOC_HOOKS)
2703   if (__free_hook != NULL) {
2704     (*__free_hook)(mem);
2705     return;
2706   }
2707 #endif
2708
2709   if (mem == 0)                              /* free(0) has no effect */
2710     return;
2711
2712   p = mem2chunk(mem);
2713
2714 #if HAVE_MMAP
2715   if (chunk_is_mmapped(p))                       /* release mmapped memory. */
2716   {
2717     munmap_chunk(p);
2718     return;
2719   }
2720 #endif
2721
2722   ar_ptr = arena_for_ptr(p);
2723 #if THREAD_STATS
2724   if(!mutex_trylock(&ar_ptr->mutex))
2725     ++(ar_ptr->stat_lock_direct);
2726   else {
2727     (void)mutex_lock(&ar_ptr->mutex);
2728     ++(ar_ptr->stat_lock_wait);
2729   }
2730 #else
2731   (void)mutex_lock(&ar_ptr->mutex);
2732 #endif
2733   chunk_free(ar_ptr, p);
2734   (void)mutex_unlock(&ar_ptr->mutex);
2735 }
2736
2737 static void
2738 #if __STD_C
2739 chunk_free(arena *ar_ptr, mchunkptr p)
2740 #else
2741 chunk_free(ar_ptr, p) arena *ar_ptr; mchunkptr p;
2742 #endif
2743 {
2744   INTERNAL_SIZE_T hd = p->size; /* its head field */
2745   INTERNAL_SIZE_T sz;  /* its size */
2746   int       idx;       /* its bin index */
2747   mchunkptr next;      /* next contiguous chunk */
2748   INTERNAL_SIZE_T nextsz; /* its size */
2749   INTERNAL_SIZE_T prevsz; /* size of previous contiguous chunk */
2750   mchunkptr bck;       /* misc temp for linking */
2751   mchunkptr fwd;       /* misc temp for linking */
2752   int       islr;      /* track whether merging with last_remainder */
2753
2754   check_inuse_chunk(ar_ptr, p);
2755
2756   sz = hd & ~PREV_INUSE;
2757   next = chunk_at_offset(p, sz);
2758   nextsz = chunksize(next);
2759
2760   if (next == top(ar_ptr))                         /* merge with top */
2761   {
2762     sz += nextsz;
2763
2764     if (!(hd & PREV_INUSE))                    /* consolidate backward */
2765     {
2766       prevsz = p->prev_size;
2767       p = chunk_at_offset(p, -prevsz);
2768       sz += prevsz;
2769       unlink(p, bck, fwd);
2770     }
2771
2772     set_head(p, sz | PREV_INUSE);
2773     top(ar_ptr) = p;
2774
2775 #ifndef NO_THREADS
2776     if(ar_ptr == &main_arena) {
2777 #endif
2778       if ((unsigned long)(sz) >= (unsigned long)trim_threshold)
2779         main_trim(top_pad);
2780 #ifndef NO_THREADS
2781     } else {
2782       heap_info *heap = heap_for_ptr(p);
2783
2784       assert(heap->ar_ptr == ar_ptr);
2785
2786       /* Try to get rid of completely empty heaps, if possible. */
2787       if((unsigned long)(sz) >= (unsigned long)trim_threshold ||
2788          p == chunk_at_offset(heap, sizeof(*heap)))
2789         heap_trim(heap, top_pad);
2790     }
2791 #endif
2792     return;
2793   }
2794
2795   set_head(next, nextsz);                    /* clear inuse bit */
2796
2797   islr = 0;
2798
2799   if (!(hd & PREV_INUSE))                    /* consolidate backward */
2800   {
2801     prevsz = p->prev_size;
2802     p = chunk_at_offset(p, -prevsz);
2803     sz += prevsz;
2804
2805     if (p->fd == last_remainder(ar_ptr))     /* keep as last_remainder */
2806       islr = 1;
2807     else
2808       unlink(p, bck, fwd);
2809   }
2810
2811   if (!(inuse_bit_at_offset(next, nextsz)))   /* consolidate forward */
2812   {
2813     sz += nextsz;
2814
2815     if (!islr && next->fd == last_remainder(ar_ptr))
2816                                               /* re-insert last_remainder */
2817     {
2818       islr = 1;
2819       link_last_remainder(ar_ptr, p);
2820     }
2821     else
2822       unlink(next, bck, fwd);
2823   }
2824
2825   set_head(p, sz | PREV_INUSE);
2826   set_foot(p, sz);
2827   if (!islr)
2828     frontlink(ar_ptr, p, sz, idx, bck, fwd);
2829 }
2830
2831
2832 \f
2833
2834
2835 /*
2836
2837   Realloc algorithm:
2838
2839     Chunks that were obtained via mmap cannot be extended or shrunk
2840     unless HAVE_MREMAP is defined, in which case mremap is used.
2841     Otherwise, if their reallocation is for additional space, they are
2842     copied.  If for less, they are just left alone.
2843
2844     Otherwise, if the reallocation is for additional space, and the
2845     chunk can be extended, it is, else a malloc-copy-free sequence is
2846     taken.  There are several different ways that a chunk could be
2847     extended. All are tried:
2848
2849        * Extending forward into following adjacent free chunk.
2850        * Shifting backwards, joining preceding adjacent space
2851        * Both shifting backwards and extending forward.
2852        * Extending into newly sbrked space
2853
2854     Unless the #define REALLOC_ZERO_BYTES_FREES is set, realloc with a
2855     size argument of zero (re)allocates a minimum-sized chunk.
2856
2857     If the reallocation is for less space, and the new request is for
2858     a `small' (<512 bytes) size, then the newly unused space is lopped
2859     off and freed.
2860
2861     The old unix realloc convention of allowing the last-free'd chunk
2862     to be used as an argument to realloc is no longer supported.
2863     I don't know of any programs still relying on this feature,
2864     and allowing it would also allow too many other incorrect
2865     usages of realloc to be sensible.
2866
2867
2868 */
2869
2870
2871 #if __STD_C
2872 Void_t* rEALLOc(Void_t* oldmem, size_t bytes)
2873 #else
2874 Void_t* rEALLOc(oldmem, bytes) Void_t* oldmem; size_t bytes;
2875 #endif
2876 {
2877   arena *ar_ptr;
2878   INTERNAL_SIZE_T    nb;      /* padded request size */
2879
2880   mchunkptr oldp;             /* chunk corresponding to oldmem */
2881   INTERNAL_SIZE_T    oldsize; /* its size */
2882
2883   mchunkptr newp;             /* chunk to return */
2884
2885 #if defined(_LIBC) || defined(MALLOC_HOOKS)
2886   if (__realloc_hook != NULL) {
2887     Void_t* result;
2888
2889     result = (*__realloc_hook)(oldmem, bytes);
2890     return result;
2891   }
2892 #endif
2893
2894 #ifdef REALLOC_ZERO_BYTES_FREES
2895   if (bytes == 0) { fREe(oldmem); return 0; }
2896 #endif
2897
2898   /* realloc of null is supposed to be same as malloc */
2899   if (oldmem == 0) return mALLOc(bytes);
2900
2901   oldp    = mem2chunk(oldmem);
2902   oldsize = chunksize(oldp);
2903
2904   nb = request2size(bytes);
2905
2906 #if HAVE_MMAP
2907   if (chunk_is_mmapped(oldp))
2908   {
2909     Void_t* newmem;
2910
2911 #if HAVE_MREMAP
2912     newp = mremap_chunk(oldp, nb);
2913     if(newp) return chunk2mem(newp);
2914 #endif
2915     /* Note the extra SIZE_SZ overhead. */
2916     if(oldsize - SIZE_SZ >= nb) return oldmem; /* do nothing */
2917     /* Must alloc, copy, free. */
2918     newmem = mALLOc(bytes);
2919     if (newmem == 0) return 0; /* propagate failure */
2920     MALLOC_COPY(newmem, oldmem, oldsize - 2*SIZE_SZ);
2921     munmap_chunk(oldp);
2922     return newmem;
2923   }
2924 #endif
2925
2926   ar_ptr = arena_for_ptr(oldp);
2927 #if THREAD_STATS
2928   if(!mutex_trylock(&ar_ptr->mutex))
2929     ++(ar_ptr->stat_lock_direct);
2930   else {
2931     (void)mutex_lock(&ar_ptr->mutex);
2932     ++(ar_ptr->stat_lock_wait);
2933   }
2934 #else
2935   (void)mutex_lock(&ar_ptr->mutex);
2936 #endif
2937
2938 #ifndef NO_THREADS
2939   /* As in malloc(), remember this arena for the next allocation. */
2940   tsd_setspecific(arena_key, (Void_t *)ar_ptr);
2941 #endif
2942
2943   newp = chunk_realloc(ar_ptr, oldp, oldsize, nb);
2944
2945   (void)mutex_unlock(&ar_ptr->mutex);
2946   return newp ? chunk2mem(newp) : NULL;
2947 }
2948
2949 static mchunkptr
2950 #if __STD_C
2951 chunk_realloc(arena* ar_ptr, mchunkptr oldp, INTERNAL_SIZE_T oldsize,
2952               INTERNAL_SIZE_T nb)
2953 #else
2954 chunk_realloc(ar_ptr, oldp, oldsize, nb)
2955 arena* ar_ptr; mchunkptr oldp; INTERNAL_SIZE_T oldsize, nb;
2956 #endif
2957 {
2958   mchunkptr newp = oldp;      /* chunk to return */
2959   INTERNAL_SIZE_T newsize = oldsize; /* its size */
2960
2961   mchunkptr next;             /* next contiguous chunk after oldp */
2962   INTERNAL_SIZE_T  nextsize;  /* its size */
2963
2964   mchunkptr prev;             /* previous contiguous chunk before oldp */
2965   INTERNAL_SIZE_T  prevsize;  /* its size */
2966
2967   mchunkptr remainder;        /* holds split off extra space from newp */
2968   INTERNAL_SIZE_T  remainder_size;   /* its size */
2969
2970   mchunkptr bck;              /* misc temp for linking */
2971   mchunkptr fwd;              /* misc temp for linking */
2972
2973   check_inuse_chunk(ar_ptr, oldp);
2974
2975   if ((long)(oldsize) < (long)(nb))
2976   {
2977
2978     /* Try expanding forward */
2979
2980     next = chunk_at_offset(oldp, oldsize);
2981     if (next == top(ar_ptr) || !inuse(next))
2982     {
2983       nextsize = chunksize(next);
2984
2985       /* Forward into top only if a remainder */
2986       if (next == top(ar_ptr))
2987       {
2988         if ((long)(nextsize + newsize) >= (long)(nb + MINSIZE))
2989         {
2990           newsize += nextsize;
2991           top(ar_ptr) = chunk_at_offset(oldp, nb);
2992           set_head(top(ar_ptr), (newsize - nb) | PREV_INUSE);
2993           set_head_size(oldp, nb);
2994           return oldp;
2995         }
2996       }
2997
2998       /* Forward into next chunk */
2999       else if (((long)(nextsize + newsize) >= (long)(nb)))
3000       {
3001         unlink(next, bck, fwd);
3002         newsize  += nextsize;
3003         goto split;
3004       }
3005     }
3006     else
3007     {
3008       next = 0;
3009       nextsize = 0;
3010     }
3011
3012     /* Try shifting backwards. */
3013
3014     if (!prev_inuse(oldp))
3015     {
3016       prev = prev_chunk(oldp);
3017       prevsize = chunksize(prev);
3018
3019       /* try forward + backward first to save a later consolidation */
3020
3021       if (next != 0)
3022       {
3023         /* into top */
3024         if (next == top(ar_ptr))
3025         {
3026           if ((long)(nextsize + prevsize + newsize) >= (long)(nb + MINSIZE))
3027           {
3028             unlink(prev, bck, fwd);
3029             newp = prev;
3030             newsize += prevsize + nextsize;
3031             MALLOC_COPY(chunk2mem(newp), chunk2mem(oldp), oldsize - SIZE_SZ);
3032             top(ar_ptr) = chunk_at_offset(newp, nb);
3033             set_head(top(ar_ptr), (newsize - nb) | PREV_INUSE);
3034             set_head_size(newp, nb);
3035             return newp;
3036           }
3037         }
3038
3039         /* into next chunk */
3040         else if (((long)(nextsize + prevsize + newsize) >= (long)(nb)))
3041         {
3042           unlink(next, bck, fwd);
3043           unlink(prev, bck, fwd);
3044           newp = prev;
3045           newsize += nextsize + prevsize;
3046           MALLOC_COPY(chunk2mem(newp), chunk2mem(oldp), oldsize - SIZE_SZ);
3047           goto split;
3048         }
3049       }
3050
3051       /* backward only */
3052       if (prev != 0 && (long)(prevsize + newsize) >= (long)nb)
3053       {
3054         unlink(prev, bck, fwd);
3055         newp = prev;
3056         newsize += prevsize;
3057         MALLOC_COPY(chunk2mem(newp), chunk2mem(oldp), oldsize - SIZE_SZ);
3058         goto split;
3059       }
3060     }
3061
3062     /* Must allocate */
3063
3064     newp = chunk_alloc (ar_ptr, nb);
3065
3066     if (newp == 0)  /* propagate failure */
3067       return 0;
3068
3069     /* Avoid copy if newp is next chunk after oldp. */
3070     /* (This can only happen when new chunk is sbrk'ed.) */
3071
3072     if ( newp == next_chunk(oldp))
3073     {
3074       newsize += chunksize(newp);
3075       newp = oldp;
3076       goto split;
3077     }
3078
3079     /* Otherwise copy, free, and exit */
3080     MALLOC_COPY(chunk2mem(newp), chunk2mem(oldp), oldsize - SIZE_SZ);
3081     chunk_free(ar_ptr, oldp);
3082     return newp;
3083   }
3084
3085
3086  split:  /* split off extra room in old or expanded chunk */
3087
3088   if (newsize - nb >= MINSIZE) /* split off remainder */
3089   {
3090     remainder = chunk_at_offset(newp, nb);
3091     remainder_size = newsize - nb;
3092     set_head_size(newp, nb);
3093     set_head(remainder, remainder_size | PREV_INUSE);
3094     set_inuse_bit_at_offset(remainder, remainder_size);
3095     chunk_free(ar_ptr, remainder);
3096   }
3097   else
3098   {
3099     set_head_size(newp, newsize);
3100     set_inuse_bit_at_offset(newp, newsize);
3101   }
3102
3103   check_inuse_chunk(ar_ptr, newp);
3104   return newp;
3105 }
3106
3107
3108 \f
3109
3110 /*
3111
3112   memalign algorithm:
3113
3114     memalign requests more than enough space from malloc, finds a spot
3115     within that chunk that meets the alignment request, and then
3116     possibly frees the leading and trailing space.
3117
3118     The alignment argument must be a power of two. This property is not
3119     checked by memalign, so misuse may result in random runtime errors.
3120
3121     8-byte alignment is guaranteed by normal malloc calls, so don't
3122     bother calling memalign with an argument of 8 or less.
3123
3124     Overreliance on memalign is a sure way to fragment space.
3125
3126 */
3127
3128
3129 #if __STD_C
3130 Void_t* mEMALIGn(size_t alignment, size_t bytes)
3131 #else
3132 Void_t* mEMALIGn(alignment, bytes) size_t alignment; size_t bytes;
3133 #endif
3134 {
3135   arena *ar_ptr;
3136   INTERNAL_SIZE_T    nb;      /* padded  request size */
3137   mchunkptr p;
3138
3139 #if defined(_LIBC) || defined(MALLOC_HOOKS)
3140   if (__memalign_hook != NULL) {
3141     Void_t* result;
3142
3143     result = (*__memalign_hook)(alignment, bytes);
3144     return result;
3145   }
3146 #endif
3147
3148   /* If need less alignment than we give anyway, just relay to malloc */
3149
3150   if (alignment <= MALLOC_ALIGNMENT) return mALLOc(bytes);
3151
3152   /* Otherwise, ensure that it is at least a minimum chunk size */
3153
3154   if (alignment <  MINSIZE) alignment = MINSIZE;
3155
3156   nb = request2size(bytes);
3157   arena_get(ar_ptr, nb + alignment + MINSIZE);
3158   if(!ar_ptr)
3159     return 0;
3160   p = chunk_align(ar_ptr, nb, alignment);
3161   (void)mutex_unlock(&ar_ptr->mutex);
3162   return p ? chunk2mem(p) : NULL;
3163 }
3164
3165 static mchunkptr
3166 #if __STD_C
3167 chunk_align(arena* ar_ptr, INTERNAL_SIZE_T nb, size_t alignment)
3168 #else
3169 chunk_align(ar_ptr, nb, alignment)
3170 arena* ar_ptr; INTERNAL_SIZE_T nb; size_t alignment;
3171 #endif
3172 {
3173   char*     m;                /* memory returned by malloc call */
3174   mchunkptr p;                /* corresponding chunk */
3175   char*     brk;              /* alignment point within p */
3176   mchunkptr newp;             /* chunk to return */
3177   INTERNAL_SIZE_T  newsize;   /* its size */
3178   INTERNAL_SIZE_T  leadsize;  /* leading space befor alignment point */
3179   mchunkptr remainder;        /* spare room at end to split off */
3180   long      remainder_size;   /* its size */
3181
3182   /* Call chunk_alloc with worst case padding to hit alignment. */
3183   p = chunk_alloc(ar_ptr, nb + alignment + MINSIZE);
3184   if (p == 0)
3185     return 0; /* propagate failure */
3186
3187   m = chunk2mem(p);
3188
3189   if ((((unsigned long)(m)) % alignment) == 0) /* aligned */
3190   {
3191 #if HAVE_MMAP
3192     if(chunk_is_mmapped(p)) {
3193       return p; /* nothing more to do */
3194     }
3195 #endif
3196   }
3197   else /* misaligned */
3198   {
3199     /*
3200       Find an aligned spot inside chunk.
3201       Since we need to give back leading space in a chunk of at
3202       least MINSIZE, if the first calculation places us at
3203       a spot with less than MINSIZE leader, we can move to the
3204       next aligned spot -- we've allocated enough total room so that
3205       this is always possible.
3206     */
3207
3208     brk = (char*)mem2chunk(((unsigned long)(m + alignment - 1)) & -alignment);
3209     if ((long)(brk - (char*)(p)) < (long)MINSIZE) brk += alignment;
3210
3211     newp = (mchunkptr)brk;
3212     leadsize = brk - (char*)(p);
3213     newsize = chunksize(p) - leadsize;
3214
3215 #if HAVE_MMAP
3216     if(chunk_is_mmapped(p))
3217     {
3218       newp->prev_size = p->prev_size + leadsize;
3219       set_head(newp, newsize|IS_MMAPPED);
3220       return newp;
3221     }
3222 #endif
3223
3224     /* give back leader, use the rest */
3225
3226     set_head(newp, newsize | PREV_INUSE);
3227     set_inuse_bit_at_offset(newp, newsize);
3228     set_head_size(p, leadsize);
3229     chunk_free(ar_ptr, p);
3230     p = newp;
3231
3232     assert (newsize>=nb && (((unsigned long)(chunk2mem(p))) % alignment) == 0);
3233   }
3234
3235   /* Also give back spare room at the end */
3236
3237   remainder_size = chunksize(p) - nb;
3238
3239   if (remainder_size >= (long)MINSIZE)
3240   {
3241     remainder = chunk_at_offset(p, nb);
3242     set_head(remainder, remainder_size | PREV_INUSE);
3243     set_head_size(p, nb);
3244     chunk_free(ar_ptr, remainder);
3245   }
3246
3247   check_inuse_chunk(ar_ptr, p);
3248   return p;
3249 }
3250
3251 \f
3252
3253
3254 /*
3255     valloc just invokes memalign with alignment argument equal
3256     to the page size of the system (or as near to this as can
3257     be figured out from all the includes/defines above.)
3258 */
3259
3260 #if __STD_C
3261 Void_t* vALLOc(size_t bytes)
3262 #else
3263 Void_t* vALLOc(bytes) size_t bytes;
3264 #endif
3265 {
3266   return mEMALIGn (malloc_getpagesize, bytes);
3267 }
3268
3269 /*
3270   pvalloc just invokes valloc for the nearest pagesize
3271   that will accommodate request
3272 */
3273
3274
3275 #if __STD_C
3276 Void_t* pvALLOc(size_t bytes)
3277 #else
3278 Void_t* pvALLOc(bytes) size_t bytes;
3279 #endif
3280 {
3281   size_t pagesize = malloc_getpagesize;
3282   return mEMALIGn (pagesize, (bytes + pagesize - 1) & ~(pagesize - 1));
3283 }
3284
3285 /*
3286
3287   calloc calls chunk_alloc, then zeroes out the allocated chunk.
3288
3289 */
3290
3291 #if __STD_C
3292 Void_t* cALLOc(size_t n, size_t elem_size)
3293 #else
3294 Void_t* cALLOc(n, elem_size) size_t n; size_t elem_size;
3295 #endif
3296 {
3297   arena *ar_ptr;
3298   mchunkptr p, oldtop;
3299   INTERNAL_SIZE_T sz, csz, oldtopsize;
3300   Void_t* mem;
3301
3302 #if defined(_LIBC) || defined(MALLOC_HOOKS)
3303   if (__malloc_hook != NULL) {
3304     sz = n * elem_size;
3305     mem = (*__malloc_hook)(sz);
3306     if(mem == 0)
3307       return 0;
3308 #ifdef HAVE_MEMCPY
3309     memset(mem, 0, sz);
3310 #else
3311     while(sz > 0) ((char*)mem)[--sz] = 0; /* rather inefficient */
3312 #endif
3313     return mem;
3314   }
3315 #endif
3316
3317   sz = request2size(n * elem_size);
3318   arena_get(ar_ptr, sz);
3319   if(!ar_ptr)
3320     return 0;
3321
3322   /* check if expand_top called, in which case don't need to clear */
3323 #if MORECORE_CLEARS
3324   oldtop = top(ar_ptr);
3325   oldtopsize = chunksize(top(ar_ptr));
3326 #endif
3327   p = chunk_alloc (ar_ptr, sz);
3328
3329   /* Only clearing follows, so we can unlock early. */
3330   (void)mutex_unlock(&ar_ptr->mutex);
3331
3332   if (p == 0)
3333     return 0;
3334   else
3335   {
3336     mem = chunk2mem(p);
3337
3338     /* Two optional cases in which clearing not necessary */
3339
3340 #if HAVE_MMAP
3341     if (chunk_is_mmapped(p)) return mem;
3342 #endif
3343
3344     csz = chunksize(p);
3345
3346 #if MORECORE_CLEARS
3347     if (p == oldtop && csz > oldtopsize)
3348     {
3349       /* clear only the bytes from non-freshly-sbrked memory */
3350       csz = oldtopsize;
3351     }
3352 #endif
3353
3354     MALLOC_ZERO(mem, csz - SIZE_SZ);
3355     return mem;
3356   }
3357 }
3358
3359 /*
3360
3361   cfree just calls free. It is needed/defined on some systems
3362   that pair it with calloc, presumably for odd historical reasons.
3363
3364 */
3365
3366 #if !defined(_LIBC)
3367 #if __STD_C
3368 void cfree(Void_t *mem)
3369 #else
3370 void cfree(mem) Void_t *mem;
3371 #endif
3372 {
3373   free(mem);
3374 }
3375 #endif
3376
3377 \f
3378
3379 /*
3380
3381     Malloc_trim gives memory back to the system (via negative
3382     arguments to sbrk) if there is unused memory at the `high' end of
3383     the malloc pool. You can call this after freeing large blocks of
3384     memory to potentially reduce the system-level memory requirements
3385     of a program. However, it cannot guarantee to reduce memory. Under
3386     some allocation patterns, some large free blocks of memory will be
3387     locked between two used chunks, so they cannot be given back to
3388     the system.
3389
3390     The `pad' argument to malloc_trim represents the amount of free
3391     trailing space to leave untrimmed. If this argument is zero,
3392     only the minimum amount of memory to maintain internal data
3393     structures will be left (one page or less). Non-zero arguments
3394     can be supplied to maintain enough trailing space to service
3395     future expected allocations without having to re-obtain memory
3396     from the system.
3397
3398     Malloc_trim returns 1 if it actually released any memory, else 0.
3399
3400 */
3401
3402 #if __STD_C
3403 int mALLOC_TRIm(size_t pad)
3404 #else
3405 int mALLOC_TRIm(pad) size_t pad;
3406 #endif
3407 {
3408   int res;
3409
3410   (void)mutex_lock(&main_arena.mutex);
3411   res = main_trim(pad);
3412   (void)mutex_unlock(&main_arena.mutex);
3413   return res;
3414 }
3415
3416 /* Trim the main arena. */
3417
3418 static int
3419 #if __STD_C
3420 main_trim(size_t pad)
3421 #else
3422 main_trim(pad) size_t pad;
3423 #endif
3424 {
3425   mchunkptr top_chunk;   /* The current top chunk */
3426   long  top_size;        /* Amount of top-most memory */
3427   long  extra;           /* Amount to release */
3428   char* current_brk;     /* address returned by pre-check sbrk call */
3429   char* new_brk;         /* address returned by negative sbrk call */
3430
3431   unsigned long pagesz = malloc_getpagesize;
3432
3433   top_chunk = top(&main_arena);
3434   top_size = chunksize(top_chunk);
3435   extra = ((top_size - pad - MINSIZE + (pagesz-1)) / pagesz - 1) * pagesz;
3436
3437   if (extra < (long)pagesz) /* Not enough memory to release */
3438     return 0;
3439
3440   /* Test to make sure no one else called sbrk */
3441   current_brk = (char*)(MORECORE (0));
3442   if (current_brk != (char*)(top_chunk) + top_size)
3443     return 0;     /* Apparently we don't own memory; must fail */
3444
3445   new_brk = (char*)(MORECORE (-extra));
3446
3447   /* Call the `morecore' hook if necessary.  */
3448   if (__after_morecore_hook)
3449     (*__after_morecore_hook) ();
3450
3451   if (new_brk == (char*)(MORECORE_FAILURE)) { /* sbrk failed? */
3452     /* Try to figure out what we have */
3453     current_brk = (char*)(MORECORE (0));
3454     top_size = current_brk - (char*)top_chunk;
3455     if (top_size >= (long)MINSIZE) /* if not, we are very very dead! */
3456     {
3457       sbrked_mem = current_brk - sbrk_base;
3458       set_head(top_chunk, top_size | PREV_INUSE);
3459     }
3460     check_chunk(&main_arena, top_chunk);
3461     return 0;
3462   }
3463   sbrked_mem -= extra;
3464
3465   /* Success. Adjust top accordingly. */
3466   set_head(top_chunk, (top_size - extra) | PREV_INUSE);
3467   check_chunk(&main_arena, top_chunk);
3468   return 1;
3469 }
3470
3471 #ifndef NO_THREADS
3472
3473 static int
3474 #if __STD_C
3475 heap_trim(heap_info *heap, size_t pad)
3476 #else
3477 heap_trim(heap, pad) heap_info *heap; size_t pad;
3478 #endif
3479 {
3480   unsigned long pagesz = malloc_getpagesize;
3481   arena *ar_ptr = heap->ar_ptr;
3482   mchunkptr top_chunk = top(ar_ptr), p, bck, fwd;
3483   heap_info *prev_heap;
3484   long new_size, top_size, extra;
3485
3486   /* Can this heap go away completely ? */
3487   while(top_chunk == chunk_at_offset(heap, sizeof(*heap))) {
3488     prev_heap = heap->prev;
3489     p = chunk_at_offset(prev_heap, prev_heap->size - (MINSIZE-2*SIZE_SZ));
3490     assert(p->size == (0|PREV_INUSE)); /* must be fencepost */
3491     p = prev_chunk(p);
3492     new_size = chunksize(p) + (MINSIZE-2*SIZE_SZ);
3493     assert(new_size>0 && new_size<(long)(2*MINSIZE));
3494     if(!prev_inuse(p))
3495       new_size += p->prev_size;
3496     assert(new_size>0 && new_size<HEAP_MAX_SIZE);
3497     if(new_size + (HEAP_MAX_SIZE - prev_heap->size) < pad + MINSIZE + pagesz)
3498       break;
3499     ar_ptr->size -= heap->size;
3500     delete_heap(heap);
3501     heap = prev_heap;
3502     if(!prev_inuse(p)) { /* consolidate backward */
3503       p = prev_chunk(p);
3504       unlink(p, bck, fwd);
3505     }
3506     assert(((unsigned long)((char*)p + new_size) & (pagesz-1)) == 0);
3507     assert( ((char*)p + new_size) == ((char*)heap + heap->size) );
3508     top(ar_ptr) = top_chunk = p;
3509     set_head(top_chunk, new_size | PREV_INUSE);
3510     check_chunk(ar_ptr, top_chunk);
3511   }
3512   top_size = chunksize(top_chunk);
3513   extra = ((top_size - pad - MINSIZE + (pagesz-1))/pagesz - 1) * pagesz;
3514   if(extra < (long)pagesz)
3515     return 0;
3516   /* Try to shrink. */
3517   if(grow_heap(heap, -extra) != 0)
3518     return 0;
3519   ar_ptr->size -= extra;
3520
3521   /* Success. Adjust top accordingly. */
3522   set_head(top_chunk, (top_size - extra) | PREV_INUSE);
3523   check_chunk(ar_ptr, top_chunk);
3524   return 1;
3525 }
3526
3527 #endif
3528
3529 \f
3530
3531 /*
3532   malloc_usable_size:
3533
3534     This routine tells you how many bytes you can actually use in an
3535     allocated chunk, which may be more than you requested (although
3536     often not). You can use this many bytes without worrying about
3537     overwriting other allocated objects. Not a particularly great
3538     programming practice, but still sometimes useful.
3539
3540 */
3541
3542 #if __STD_C
3543 size_t mALLOC_USABLE_SIZe(Void_t* mem)
3544 #else
3545 size_t mALLOC_USABLE_SIZe(mem) Void_t* mem;
3546 #endif
3547 {
3548   mchunkptr p;
3549
3550   if (mem == 0)
3551     return 0;
3552   else
3553   {
3554     p = mem2chunk(mem);
3555     if(!chunk_is_mmapped(p))
3556     {
3557       if (!inuse(p)) return 0;
3558       check_inuse_chunk(arena_for_ptr(mem), p);
3559       return chunksize(p) - SIZE_SZ;
3560     }
3561     return chunksize(p) - 2*SIZE_SZ;
3562   }
3563 }
3564
3565
3566 \f
3567
3568 /* Utility to update mallinfo for malloc_stats() and mallinfo() */
3569
3570 static void
3571 #if __STD_C
3572 malloc_update_mallinfo(arena *ar_ptr, struct mallinfo *mi)
3573 #else
3574 malloc_update_mallinfo(ar_ptr, mi) arena *ar_ptr; struct mallinfo *mi;
3575 #endif
3576 {
3577   int i, navail;
3578   mbinptr b;
3579   mchunkptr p;
3580 #if MALLOC_DEBUG
3581   mchunkptr q;
3582 #endif
3583   INTERNAL_SIZE_T avail;
3584
3585   (void)mutex_lock(&ar_ptr->mutex);
3586   avail = chunksize(top(ar_ptr));
3587   navail = ((long)(avail) >= (long)MINSIZE)? 1 : 0;
3588
3589   for (i = 1; i < NAV; ++i)
3590   {
3591     b = bin_at(ar_ptr, i);
3592     for (p = last(b); p != b; p = p->bk)
3593     {
3594 #if MALLOC_DEBUG
3595       check_free_chunk(ar_ptr, p);
3596       for (q = next_chunk(p);
3597            q != top(ar_ptr) && inuse(q) && (long)chunksize(q) > 0;
3598            q = next_chunk(q))
3599         check_inuse_chunk(ar_ptr, q);
3600 #endif
3601       avail += chunksize(p);
3602       navail++;
3603     }
3604   }
3605
3606   mi->arena = ar_ptr->size;
3607   mi->ordblks = navail;
3608   mi->uordblks = ar_ptr->size - avail;
3609   mi->fordblks = avail;
3610   mi->hblks = n_mmaps;
3611   mi->hblkhd = mmapped_mem;
3612   mi->keepcost = chunksize(top(ar_ptr));
3613
3614   (void)mutex_unlock(&ar_ptr->mutex);
3615 }
3616
3617 #if !defined(NO_THREADS) && MALLOC_DEBUG > 1
3618
3619 /* Print the complete contents of a single heap to stderr. */
3620
3621 static void
3622 #if __STD_C
3623 dump_heap(heap_info *heap)
3624 #else
3625 dump_heap(heap) heap_info *heap;
3626 #endif
3627 {
3628   char *ptr;
3629   mchunkptr p;
3630
3631   fprintf(stderr, "Heap %p, size %10lx:\n", heap, (long)heap->size);
3632   ptr = (heap->ar_ptr != (arena*)(heap+1)) ?
3633     (char*)(heap + 1) : (char*)(heap + 1) + sizeof(arena);
3634   p = (mchunkptr)(((unsigned long)ptr + MALLOC_ALIGN_MASK) &
3635                   ~MALLOC_ALIGN_MASK);
3636   for(;;) {
3637     fprintf(stderr, "chunk %p size %10lx", p, (long)p->size);
3638     if(p == top(heap->ar_ptr)) {
3639       fprintf(stderr, " (top)\n");
3640       break;
3641     } else if(p->size == (0|PREV_INUSE)) {
3642       fprintf(stderr, " (fence)\n");
3643       break;
3644     }
3645     fprintf(stderr, "\n");
3646     p = next_chunk(p);
3647   }
3648 }
3649
3650 #endif
3651
3652 \f
3653
3654 /*
3655
3656   malloc_stats:
3657
3658     For all arenas separately and in total, prints on stderr the
3659     amount of space obtained from the system, and the current number
3660     of bytes allocated via malloc (or realloc, etc) but not yet
3661     freed. (Note that this is the number of bytes allocated, not the
3662     number requested. It will be larger than the number requested
3663     because of alignment and bookkeeping overhead.)  When not compiled
3664     for multiple threads, the maximum amount of allocated memory
3665     (which may be more than current if malloc_trim and/or munmap got
3666     called) is also reported.  When using mmap(), prints the maximum
3667     number of simultaneous mmap regions used, too.
3668
3669 */
3670
3671 void mALLOC_STATs()
3672 {
3673   int i;
3674   arena *ar_ptr;
3675   struct mallinfo mi;
3676   unsigned int in_use_b = mmapped_mem, system_b = in_use_b;
3677 #if THREAD_STATS
3678   long stat_lock_direct = 0, stat_lock_loop = 0, stat_lock_wait = 0;
3679 #endif
3680
3681   for(i=0, ar_ptr = &main_arena;; i++) {
3682     malloc_update_mallinfo(ar_ptr, &mi);
3683     fprintf(stderr, "Arena %d:\n", i);
3684     fprintf(stderr, "system bytes     = %10u\n", (unsigned int)mi.arena);
3685     fprintf(stderr, "in use bytes     = %10u\n", (unsigned int)mi.uordblks);
3686     system_b += mi.arena;
3687     in_use_b += mi.uordblks;
3688 #if THREAD_STATS
3689     stat_lock_direct += ar_ptr->stat_lock_direct;
3690     stat_lock_loop += ar_ptr->stat_lock_loop;
3691     stat_lock_wait += ar_ptr->stat_lock_wait;
3692 #endif
3693 #if !defined(NO_THREADS) && MALLOC_DEBUG > 1
3694     if(ar_ptr != &main_arena) {
3695       (void)mutex_lock(&ar_ptr->mutex);
3696       heap_info *heap = heap_for_ptr(top(ar_ptr));
3697       while(heap) { dump_heap(heap); heap = heap->prev; }
3698       (void)mutex_unlock(&ar_ptr->mutex);
3699     }
3700 #endif
3701     ar_ptr = ar_ptr->next;
3702     if(ar_ptr == &main_arena) break;
3703   }
3704   fprintf(stderr, "Total (incl. mmap):\n");
3705   fprintf(stderr, "system bytes     = %10u\n", system_b);
3706   fprintf(stderr, "in use bytes     = %10u\n", in_use_b);
3707 #ifdef NO_THREADS
3708   fprintf(stderr, "max system bytes = %10u\n", (unsigned int)max_total_mem);
3709 #endif
3710 #if HAVE_MMAP
3711   fprintf(stderr, "max mmap regions = %10u\n", (unsigned int)max_n_mmaps);
3712 #endif
3713 #if THREAD_STATS
3714   fprintf(stderr, "heaps created    = %10d\n",  stat_n_heaps);
3715   fprintf(stderr, "locked directly  = %10ld\n", stat_lock_direct);
3716   fprintf(stderr, "locked in loop   = %10ld\n", stat_lock_loop);
3717   fprintf(stderr, "locked waiting   = %10ld\n", stat_lock_wait);
3718   fprintf(stderr, "locked total     = %10ld\n",
3719           stat_lock_direct + stat_lock_loop + stat_lock_wait);
3720 #endif
3721 }
3722
3723 /*
3724   mallinfo returns a copy of updated current mallinfo.
3725   The information reported is for the arena last used by the thread.
3726 */
3727
3728 struct mallinfo mALLINFo()
3729 {
3730   struct mallinfo mi;
3731   Void_t *vptr = NULL;
3732
3733 #ifndef NO_THREADS
3734   tsd_getspecific(arena_key, vptr);
3735 #endif
3736   malloc_update_mallinfo((vptr ? (arena*)vptr : &main_arena), &mi);
3737   return mi;
3738 }
3739
3740
3741 \f
3742
3743 /*
3744   mallopt:
3745
3746     mallopt is the general SVID/XPG interface to tunable parameters.
3747     The format is to provide a (parameter-number, parameter-value) pair.
3748     mallopt then sets the corresponding parameter to the argument
3749     value if it can (i.e., so long as the value is meaningful),
3750     and returns 1 if successful else 0.
3751
3752     See descriptions of tunable parameters above.
3753
3754 */
3755
3756 #if __STD_C
3757 int mALLOPt(int param_number, int value)
3758 #else
3759 int mALLOPt(param_number, value) int param_number; int value;
3760 #endif
3761 {
3762   switch(param_number)
3763   {
3764     case M_TRIM_THRESHOLD:
3765       trim_threshold = value; return 1;
3766     case M_TOP_PAD:
3767       top_pad = value; return 1;
3768     case M_MMAP_THRESHOLD:
3769 #ifndef NO_THREADS
3770       /* Forbid setting the threshold too high. */
3771       if((unsigned long)value > HEAP_MAX_SIZE/2) return 0;
3772 #endif
3773       mmap_threshold = value; return 1;
3774     case M_MMAP_MAX:
3775 #if HAVE_MMAP
3776       n_mmaps_max = value; return 1;
3777 #else
3778       if (value != 0) return 0; else  n_mmaps_max = value; return 1;
3779 #endif
3780     case M_CHECK_ACTION:
3781       check_action = value; return 1;
3782
3783     default:
3784       return 0;
3785   }
3786 }
3787
3788 \f
3789
3790 /* Get/set state: malloc_get_state() records the current state of all
3791    malloc variables (_except_ for the actual heap contents and `hook'
3792    function pointers) in a system dependent, opaque data structure.
3793    This data structure is dynamically allocated and can be free()d
3794    after use.  malloc_set_state() restores the state of all malloc
3795    variables to the previously obtained state.  This is especially
3796    useful when using this malloc as part of a shared library, and when
3797    the heap contents are saved/restored via some other method.  The
3798    primary example for this is GNU Emacs with its `dumping' procedure.
3799    `Hook' function pointers are never saved or restored by these
3800    functions. */
3801
3802 #define MALLOC_STATE_MAGIC   0x444c4541l
3803 #define MALLOC_STATE_VERSION (0*0x100l + 0l) /* major*0x100 + minor */
3804
3805 struct malloc_state {
3806   long          magic;
3807   long          version;
3808   mbinptr       av[NAV * 2 + 2];
3809   char*         sbrk_base;
3810   int           sbrked_mem_bytes;
3811   unsigned long trim_threshold;
3812   unsigned long top_pad;
3813   unsigned int  n_mmaps_max;
3814   unsigned long mmap_threshold;
3815   int           check_action;
3816   unsigned long max_sbrked_mem;
3817   unsigned long max_total_mem;
3818   unsigned int  n_mmaps;
3819   unsigned int  max_n_mmaps;
3820   unsigned long mmapped_mem;
3821   unsigned long max_mmapped_mem;
3822 };
3823
3824 Void_t*
3825 mALLOC_GET_STATe()
3826 {
3827   mchunkptr victim;
3828   struct malloc_state* ms;
3829   int i;
3830   mbinptr b;
3831
3832   ptmalloc_init();
3833   (void)mutex_lock(&main_arena.mutex);
3834   victim = chunk_alloc(&main_arena, request2size(sizeof(*ms)));
3835   if(!victim) {
3836     (void)mutex_unlock(&main_arena.mutex);
3837     return 0;
3838   }
3839   ms = (struct malloc_state*)chunk2mem(victim);
3840   ms->magic = MALLOC_STATE_MAGIC;
3841   ms->version = MALLOC_STATE_VERSION;
3842   ms->av[0] = main_arena.av[0];
3843   ms->av[1] = main_arena.av[1];
3844   for(i=0; i<NAV; i++) {
3845     b = bin_at(&main_arena, i);
3846     if(first(b) == b)
3847       ms->av[2*i+2] = ms->av[2*i+3] = 0; /* empty bin (or initial top) */
3848     else {
3849       ms->av[2*i+2] = first(b);
3850       ms->av[2*i+3] = last(b);
3851     }
3852   }
3853   ms->sbrk_base = sbrk_base;
3854   ms->sbrked_mem_bytes = sbrked_mem;
3855   ms->trim_threshold = trim_threshold;
3856   ms->top_pad = top_pad;
3857   ms->n_mmaps_max = n_mmaps_max;
3858   ms->mmap_threshold = mmap_threshold;
3859   ms->check_action = check_action;
3860   ms->max_sbrked_mem = max_sbrked_mem;
3861 #ifdef NO_THREADS
3862   ms->max_total_mem = max_total_mem;
3863 #else
3864   ms->max_total_mem = 0;
3865 #endif
3866   ms->n_mmaps = n_mmaps;
3867   ms->max_n_mmaps = max_n_mmaps;
3868   ms->mmapped_mem = mmapped_mem;
3869   ms->max_mmapped_mem = max_mmapped_mem;
3870   (void)mutex_unlock(&main_arena.mutex);
3871   return (Void_t*)ms;
3872 }
3873
3874 int
3875 #if __STD_C
3876 mALLOC_SET_STATe(Void_t* msptr)
3877 #else
3878 mALLOC_SET_STATe(msptr) Void_t* msptr;
3879 #endif
3880 {
3881   struct malloc_state* ms = (struct malloc_state*)msptr;
3882   int i;
3883   mbinptr b;
3884
3885   ptmalloc_init();
3886   if(ms->magic != MALLOC_STATE_MAGIC) return -1;
3887   /* Must fail if the major version is too high. */
3888   if((ms->version & ~0xffl) > (MALLOC_STATE_VERSION & ~0xffl)) return -2;
3889   (void)mutex_lock(&main_arena.mutex);
3890   main_arena.av[0] = ms->av[0];
3891   main_arena.av[1] = ms->av[1];
3892   for(i=0; i<NAV; i++) {
3893     b = bin_at(&main_arena, i);
3894     if(ms->av[2*i+2] == 0)
3895       first(b) = last(b) = b;
3896     else {
3897       first(b) = ms->av[2*i+2];
3898       last(b) = ms->av[2*i+3];
3899       if(i > 0) {
3900         /* Make sure the links to the `av'-bins in the heap are correct. */
3901         first(b)->bk = b;
3902         last(b)->fd = b;
3903       }
3904     }
3905   }
3906   sbrk_base = ms->sbrk_base;
3907   sbrked_mem = ms->sbrked_mem_bytes;
3908   trim_threshold = ms->trim_threshold;
3909   top_pad = ms->top_pad;
3910   n_mmaps_max = ms->n_mmaps_max;
3911   mmap_threshold = ms->mmap_threshold;
3912   check_action = ms->check_action;
3913   max_sbrked_mem = ms->max_sbrked_mem;
3914 #ifdef NO_THREADS
3915   max_total_mem = ms->max_total_mem;
3916 #endif
3917   n_mmaps = ms->n_mmaps;
3918   max_n_mmaps = ms->max_n_mmaps;
3919   mmapped_mem = ms->mmapped_mem;
3920   max_mmapped_mem = ms->max_mmapped_mem;
3921   /* add version-dependent code here */
3922   (void)mutex_unlock(&main_arena.mutex);
3923   return 0;
3924 }
3925
3926 \f
3927
3928 #if defined(_LIBC) || defined(MALLOC_HOOKS)
3929
3930 /* A simple, standard set of debugging hooks.  Overhead is `only' one
3931    byte per chunk; still this will catch most cases of double frees or
3932    overruns. */
3933
3934 #define MAGICBYTE(p) ( ( ((size_t)p >> 3) ^ ((size_t)p >> 11)) & 0xFF )
3935
3936 /* Convert a pointer to be free()d or realloc()ed to a valid chunk
3937    pointer.  If the provided pointer is not valid, return NULL.  The
3938    goal here is to avoid crashes, unlike in the MALLOC_DEBUG code. */
3939
3940 static mchunkptr
3941 #if __STD_C
3942 mem2chunk_check(Void_t* mem)
3943 #else
3944 mem2chunk_check(mem) Void_t* mem;
3945 #endif
3946 {
3947   mchunkptr p;
3948   INTERNAL_SIZE_T sz;
3949
3950   p = mem2chunk(mem);
3951   if(!aligned_OK(p)) return NULL;
3952   if( (char*)p>=sbrk_base && (char*)p<(sbrk_base+sbrked_mem) ) {
3953     /* Must be a chunk in conventional heap memory. */
3954     if(chunk_is_mmapped(p) ||
3955        ( (sz = chunksize(p)), ((char*)p + sz)>=(sbrk_base+sbrked_mem) ) ||
3956        sz<MINSIZE || sz&MALLOC_ALIGN_MASK || !inuse(p) ||
3957        ( !prev_inuse(p) && (p->prev_size&MALLOC_ALIGN_MASK ||
3958                             (long)prev_chunk(p)<(long)sbrk_base ||
3959                             next_chunk(prev_chunk(p))!=p) ))
3960       return NULL;
3961     if(*((unsigned char*)p + sz + (SIZE_SZ-1)) != MAGICBYTE(p))
3962       return NULL;
3963     *((unsigned char*)p + sz + (SIZE_SZ-1)) ^= 0xFF;
3964   } else {
3965     unsigned long offset, page_mask = malloc_getpagesize-1;
3966
3967     /* mmap()ed chunks have MALLOC_ALIGNMENT or higher power-of-two
3968        alignment relative to the beginning of a page.  Check this
3969        first. */
3970     offset = (unsigned long)mem & page_mask;
3971     if((offset!=MALLOC_ALIGNMENT && offset!=0 && offset!=0x10 &&
3972         offset!=0x20 && offset!=0x40 && offset!=0x80 && offset!=0x100 &&
3973         offset!=0x200 && offset!=0x400 && offset!=0x800 && offset!=0x1000 &&
3974         offset<0x2000) ||
3975        !chunk_is_mmapped(p) || (p->size & PREV_INUSE) ||
3976        ( (((unsigned long)p - p->prev_size) & page_mask) != 0 ) ||
3977        ( (sz = chunksize(p)), ((p->prev_size + sz) & page_mask) != 0 ) )
3978       return NULL;
3979     if(*((unsigned char*)p + sz - 1) != MAGICBYTE(p))
3980       return NULL;
3981     *((unsigned char*)p + sz - 1) ^= 0xFF;
3982   }
3983   return p;
3984 }
3985
3986 static Void_t*
3987 #if __STD_C
3988 malloc_check(size_t sz)
3989 #else
3990 malloc_check(sz) size_t sz;
3991 #endif
3992 {
3993   mchunkptr victim;
3994   INTERNAL_SIZE_T nb = request2size(sz + 1);
3995
3996   (void)mutex_lock(&main_arena.mutex);
3997   victim = chunk_alloc(&main_arena, nb);
3998   (void)mutex_unlock(&main_arena.mutex);
3999   if(!victim) return NULL;
4000   nb = chunksize(victim);
4001   if(chunk_is_mmapped(victim))
4002     --nb;
4003   else
4004     nb += SIZE_SZ - 1;
4005   *((unsigned char*)victim + nb) = MAGICBYTE(victim);
4006   return chunk2mem(victim);
4007 }
4008
4009 static void
4010 #if __STD_C
4011 free_check(Void_t* mem)
4012 #else
4013 free_check(mem) Void_t* mem;
4014 #endif
4015 {
4016   mchunkptr p;
4017
4018   if(!mem) return;
4019   (void)mutex_lock(&main_arena.mutex);
4020   p = mem2chunk_check(mem);
4021   if(!p) {
4022     (void)mutex_unlock(&main_arena.mutex);
4023     switch(check_action) {
4024     case 1:
4025       fprintf(stderr, "free(): invalid pointer %lx!\n", (long)(mem));
4026       break;
4027     case 2:
4028       abort();
4029     }
4030     return;
4031   }
4032 #if HAVE_MMAP
4033   if (chunk_is_mmapped(p)) {
4034     (void)mutex_unlock(&main_arena.mutex);
4035     munmap_chunk(p);
4036     return;
4037   }
4038 #endif
4039 #if 0 /* Erase freed memory. */
4040   memset(mem, 0, chunksize(p) - (SIZE_SZ+1));
4041 #endif
4042   chunk_free(&main_arena, p);
4043   (void)mutex_unlock(&main_arena.mutex);
4044 }
4045
4046 static Void_t*
4047 #if __STD_C
4048 realloc_check(Void_t* oldmem, size_t bytes)
4049 #else
4050 realloc_check(oldmem, bytes) Void_t* oldmem; size_t bytes;
4051 #endif
4052 {
4053   mchunkptr oldp, newp;
4054   INTERNAL_SIZE_T nb, oldsize;
4055
4056   if (oldmem == 0) return malloc_check(bytes);
4057   (void)mutex_lock(&main_arena.mutex);
4058   oldp = mem2chunk_check(oldmem);
4059   if(!oldp) {
4060     (void)mutex_unlock(&main_arena.mutex);
4061     switch(check_action) {
4062     case 1:
4063       fprintf(stderr, "realloc(): invalid pointer %lx!\n", (long)(oldmem));
4064       break;
4065     case 2:
4066       abort();
4067     }
4068     return malloc_check(bytes);
4069   }
4070   oldsize = chunksize(oldp);
4071
4072   nb = request2size(bytes+1);
4073
4074 #if HAVE_MMAP
4075   if (chunk_is_mmapped(oldp)) {
4076 #if HAVE_MREMAP
4077     newp = mremap_chunk(oldp, nb);
4078     if(!newp) {
4079 #endif
4080       /* Note the extra SIZE_SZ overhead. */
4081       if(oldsize - SIZE_SZ >= nb) newp = oldp; /* do nothing */
4082       else {
4083         /* Must alloc, copy, free. */
4084         newp = chunk_alloc(&main_arena, nb);
4085         if (newp) {
4086           MALLOC_COPY(chunk2mem(newp), oldmem, oldsize - 2*SIZE_SZ);
4087           munmap_chunk(oldp);
4088         }
4089       }
4090 #if HAVE_MREMAP
4091     }
4092 #endif
4093   } else {
4094 #endif /* HAVE_MMAP */
4095     newp = chunk_realloc(&main_arena, oldp, oldsize, nb);
4096 #if 0 /* Erase freed memory. */
4097     nb = chunksize(newp);
4098     if(oldp<newp || oldp>=chunk_at_offset(newp, nb)) {
4099       memset((char*)oldmem + 2*sizeof(mbinptr), 0,
4100              oldsize - (2*sizeof(mbinptr)+2*SIZE_SZ+1));
4101     } else if(nb > oldsize+SIZE_SZ) {
4102       memset((char*)chunk2mem(newp) + oldsize, 0, nb - (oldsize+SIZE_SZ));
4103     }
4104 #endif
4105 #if HAVE_MMAP
4106   }
4107 #endif
4108   (void)mutex_unlock(&main_arena.mutex);
4109
4110   if(!newp) return NULL;
4111   nb = chunksize(newp);
4112   if(chunk_is_mmapped(newp))
4113     --nb;
4114   else
4115     nb += SIZE_SZ - 1;
4116   *((unsigned char*)newp + nb) = MAGICBYTE(newp);
4117   return chunk2mem(newp);
4118 }
4119
4120 static Void_t*
4121 #if __STD_C
4122 memalign_check(size_t alignment, size_t bytes)
4123 #else
4124 memalign_check(alignment, bytes) size_t alignment; size_t bytes;
4125 #endif
4126 {
4127   INTERNAL_SIZE_T nb;
4128   mchunkptr p;
4129
4130   if (alignment <= MALLOC_ALIGNMENT) return malloc_check(bytes);
4131   if (alignment <  MINSIZE) alignment = MINSIZE;
4132
4133   nb = request2size(bytes+1);
4134   (void)mutex_lock(&main_arena.mutex);
4135   p = chunk_align(&main_arena, nb, alignment);
4136   (void)mutex_unlock(&main_arena.mutex);
4137   if(!p) return NULL;
4138   nb = chunksize(p);
4139   if(chunk_is_mmapped(p))
4140     --nb;
4141   else
4142     nb += SIZE_SZ - 1;
4143   *((unsigned char*)p + nb) = MAGICBYTE(p);
4144   return chunk2mem(p);
4145 }
4146
4147 /* The following hooks are used when the global initialization in
4148    ptmalloc_init() hasn't completed yet. */
4149
4150 static Void_t*
4151 #if __STD_C
4152 malloc_starter(size_t sz)
4153 #else
4154 malloc_starter(sz) size_t sz;
4155 #endif
4156 {
4157   mchunkptr victim = chunk_alloc(&main_arena, request2size(sz));
4158
4159   return victim ? chunk2mem(victim) : 0;
4160 }
4161
4162 static void
4163 #if __STD_C
4164 free_starter(Void_t* mem)
4165 #else
4166 free_starter(mem) Void_t* mem;
4167 #endif
4168 {
4169   mchunkptr p;
4170
4171   if(!mem) return;
4172   p = mem2chunk(mem);
4173 #if HAVE_MMAP
4174   if (chunk_is_mmapped(p)) {
4175     munmap_chunk(p);
4176     return;
4177   }
4178 #endif
4179   chunk_free(&main_arena, p);
4180 }
4181
4182 #endif /* defined(_LIBC) || defined(MALLOC_HOOKS) */
4183
4184 \f
4185
4186 #ifdef _LIBC
4187 weak_alias (__libc_calloc, __calloc) weak_alias (__libc_calloc, calloc)
4188 weak_alias (__libc_free, __cfree) weak_alias (__libc_free, cfree)
4189 weak_alias (__libc_free, __free) weak_alias (__libc_free, free)
4190 weak_alias (__libc_malloc, __malloc) weak_alias (__libc_malloc, malloc)
4191 weak_alias (__libc_memalign, __memalign) weak_alias (__libc_memalign, memalign)
4192 weak_alias (__libc_realloc, __realloc) weak_alias (__libc_realloc, realloc)
4193 weak_alias (__libc_valloc, __valloc) weak_alias (__libc_valloc, valloc)
4194 weak_alias (__libc_pvalloc, __pvalloc) weak_alias (__libc_pvalloc, pvalloc)
4195 weak_alias (__libc_mallinfo, __mallinfo) weak_alias (__libc_mallinfo, mallinfo)
4196 weak_alias (__libc_mallopt, __mallopt) weak_alias (__libc_mallopt, mallopt)
4197
4198 weak_alias (__malloc_stats, malloc_stats)
4199 weak_alias (__malloc_usable_size, malloc_usable_size)
4200 weak_alias (__malloc_trim, malloc_trim)
4201 weak_alias (__malloc_get_state, malloc_get_state)
4202 weak_alias (__malloc_set_state, malloc_set_state)
4203 #endif
4204
4205 /*
4206
4207 History:
4208
4209     V2.6.4-pt3 Thu Feb 20 1997 Wolfram Gloger (wmglo@dent.med.uni-muenchen.de)
4210       * Added malloc_get/set_state() (mainly for use in GNU emacs),
4211         using interface from Marcus Daniels
4212       * All parameters are now adjustable via environment variables
4213
4214     V2.6.4-pt2 Sat Dec 14 1996 Wolfram Gloger (wmglo@dent.med.uni-muenchen.de)
4215       * Added debugging hooks
4216       * Fixed possible deadlock in realloc() when out of memory
4217       * Don't pollute namespace in glibc: use __getpagesize, __mmap, etc.
4218
4219     V2.6.4-pt Wed Dec  4 1996 Wolfram Gloger (wmglo@dent.med.uni-muenchen.de)
4220       * Very minor updates from the released 2.6.4 version.
4221       * Trimmed include file down to exported data structures.
4222       * Changes from H.J. Lu for glibc-2.0.
4223
4224     V2.6.3i-pt Sep 16 1996  Wolfram Gloger (wmglo@dent.med.uni-muenchen.de)
4225       * Many changes for multiple threads
4226       * Introduced arenas and heaps
4227
4228     V2.6.3 Sun May 19 08:17:58 1996  Doug Lea  (dl at gee)
4229       * Added pvalloc, as recommended by H.J. Liu
4230       * Added 64bit pointer support mainly from Wolfram Gloger
4231       * Added anonymously donated WIN32 sbrk emulation
4232       * Malloc, calloc, getpagesize: add optimizations from Raymond Nijssen
4233       * malloc_extend_top: fix mask error that caused wastage after
4234         foreign sbrks
4235       * Add linux mremap support code from HJ Liu
4236
4237     V2.6.2 Tue Dec  5 06:52:55 1995  Doug Lea  (dl at gee)
4238       * Integrated most documentation with the code.
4239       * Add support for mmap, with help from
4240         Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
4241       * Use last_remainder in more cases.
4242       * Pack bins using idea from  colin@nyx10.cs.du.edu
4243       * Use ordered bins instead of best-fit threshold
4244       * Eliminate block-local decls to simplify tracing and debugging.
4245       * Support another case of realloc via move into top
4246       * Fix error occurring when initial sbrk_base not word-aligned.
4247       * Rely on page size for units instead of SBRK_UNIT to
4248         avoid surprises about sbrk alignment conventions.
4249       * Add mallinfo, mallopt. Thanks to Raymond Nijssen
4250         (raymond@es.ele.tue.nl) for the suggestion.
4251       * Add `pad' argument to malloc_trim and top_pad mallopt parameter.
4252       * More precautions for cases where other routines call sbrk,
4253         courtesy of Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
4254       * Added macros etc., allowing use in linux libc from
4255         H.J. Lu (hjl@gnu.ai.mit.edu)
4256       * Inverted this history list
4257
4258     V2.6.1 Sat Dec  2 14:10:57 1995  Doug Lea  (dl at gee)
4259       * Re-tuned and fixed to behave more nicely with V2.6.0 changes.
4260       * Removed all preallocation code since under current scheme
4261         the work required to undo bad preallocations exceeds
4262         the work saved in good cases for most test programs.
4263       * No longer use return list or unconsolidated bins since
4264         no scheme using them consistently outperforms those that don't
4265         given above changes.
4266       * Use best fit for very large chunks to prevent some worst-cases.
4267       * Added some support for debugging
4268
4269     V2.6.0 Sat Nov  4 07:05:23 1995  Doug Lea  (dl at gee)
4270       * Removed footers when chunks are in use. Thanks to
4271         Paul Wilson (wilson@cs.texas.edu) for the suggestion.
4272
4273     V2.5.4 Wed Nov  1 07:54:51 1995  Doug Lea  (dl at gee)
4274       * Added malloc_trim, with help from Wolfram Gloger
4275         (wmglo@Dent.MED.Uni-Muenchen.DE).
4276
4277     V2.5.3 Tue Apr 26 10:16:01 1994  Doug Lea  (dl at g)
4278
4279     V2.5.2 Tue Apr  5 16:20:40 1994  Doug Lea  (dl at g)
4280       * realloc: try to expand in both directions
4281       * malloc: swap order of clean-bin strategy;
4282       * realloc: only conditionally expand backwards
4283       * Try not to scavenge used bins
4284       * Use bin counts as a guide to preallocation
4285       * Occasionally bin return list chunks in first scan
4286       * Add a few optimizations from colin@nyx10.cs.du.edu
4287
4288     V2.5.1 Sat Aug 14 15:40:43 1993  Doug Lea  (dl at g)
4289       * faster bin computation & slightly different binning
4290       * merged all consolidations to one part of malloc proper
4291          (eliminating old malloc_find_space & malloc_clean_bin)
4292       * Scan 2 returns chunks (not just 1)
4293       * Propagate failure in realloc if malloc returns 0
4294       * Add stuff to allow compilation on non-ANSI compilers
4295           from kpv@research.att.com
4296
4297     V2.5 Sat Aug  7 07:41:59 1993  Doug Lea  (dl at g.oswego.edu)
4298       * removed potential for odd address access in prev_chunk
4299       * removed dependency on getpagesize.h
4300       * misc cosmetics and a bit more internal documentation
4301       * anticosmetics: mangled names in macros to evade debugger strangeness
4302       * tested on sparc, hp-700, dec-mips, rs6000
4303           with gcc & native cc (hp, dec only) allowing
4304           Detlefs & Zorn comparison study (in SIGPLAN Notices.)
4305
4306     Trial version Fri Aug 28 13:14:29 1992  Doug Lea  (dl at g.oswego.edu)
4307       * Based loosely on libg++-1.2X malloc. (It retains some of the overall
4308          structure of old version,  but most details differ.)
4309
4310 */