malloc/malloc.c

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