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