src/vppinfra/dlmalloc.c

   1 /*
   2   This is a version (aka dlmalloc) of malloc/free/realloc written by
   3   Doug Lea and released to the public domain, as explained at
   4   http://creativecommons.org/publicdomain/zero/1.0/ Send questions,
   5   comments, complaints, performance data, etc to dl@cs.oswego.edu
   6 */
   7
   8 #include <vppinfra/dlmalloc.h>
   9
  10 /*------------------------------ internal #includes ---------------------- */
  11
  12 #ifdef _MSC_VER
  13 #pragma warning( disable : 4146 ) /* no "unsigned" warnings */
  14 #endif /* _MSC_VER */
  15 #if !NO_MALLOC_STATS
  16 #include <stdio.h>       /* for printing in malloc_stats */
  17 #endif /* NO_MALLOC_STATS */
  18 #ifndef LACKS_ERRNO_H
  19 #include <errno.h>       /* for MALLOC_FAILURE_ACTION */
  20 #endif /* LACKS_ERRNO_H */
  21 #ifdef DEBUG
  22 #if DLM_ABORT_ON_ASSERT_FAILURE
  23 #undef assert
  24 #define assert(x) if(!(x)) DLM_ABORT
  25 #else /* DLM_ABORT_ON_ASSERT_FAILURE */
  26 #include <assert.h>
  27 #endif /* DLM_ABORT_ON_ASSERT_FAILURE */
  28 #else  /* DEBUG */
  29 #ifndef assert
  30 #define assert(x)
  31 #endif
  32 #define DEBUG 0
  33 #endif /* DEBUG */
  34 #if !defined(WIN32) && !defined(LACKS_TIME_H)
  35 #include <time.h>        /* for magic initialization */
  36 #endif /* WIN32 */
  37 #ifndef LACKS_STDLIB_H
  38 #include <stdlib.h>      /* for abort() */
  39 #endif /* LACKS_STDLIB_H */
  40 #ifndef LACKS_STRING_H
  41 #include <string.h>      /* for memset etc */
  42 #endif  /* LACKS_STRING_H */
  43 #if USE_BUILTIN_FFS
  44 #ifndef LACKS_STRINGS_H
  45 #include <strings.h>     /* for ffs */
  46 #endif /* LACKS_STRINGS_H */
  47 #endif /* USE_BUILTIN_FFS */
  48 #if HAVE_MMAP
  49 #ifndef LACKS_SYS_MMAN_H
  50 /* On some versions of linux, mremap decl in mman.h needs __USE_GNU set */
  51 #if (defined(linux) && !defined(__USE_GNU))
  52 #define __USE_GNU 1
  53 #include <sys/mman.h>    /* for mmap */
  54 #undef __USE_GNU
  55 #else
  56 #include <sys/mman.h>    /* for mmap */
  57 #endif /* linux */
  58 #endif /* LACKS_SYS_MMAN_H */
  59 #ifndef LACKS_FCNTL_H
  60 #include <fcntl.h>
  61 #endif /* LACKS_FCNTL_H */
  62 #endif /* HAVE_MMAP */
  63 #ifndef LACKS_UNISTD_H
  64 #include <unistd.h>     /* for sbrk, sysconf */
  65 #else /* LACKS_UNISTD_H */
  66 #if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)
  67 extern void*     sbrk(ptrdiff_t);
  68 #endif /* FreeBSD etc */
  69 #endif /* LACKS_UNISTD_H */
  70
  71 /* Declarations for locking */
  72 #if USE_LOCKS
  73 #ifndef WIN32
  74 #if defined (__SVR4) && defined (__sun)  /* solaris */
  75 #include <thread.h>
  76 #elif !defined(LACKS_SCHED_H)
  77 #include <sched.h>
  78 #endif /* solaris or LACKS_SCHED_H */
  79 #if (defined(USE_RECURSIVE_LOCKS) && USE_RECURSIVE_LOCKS != 0) || !USE_SPIN_LOCKS
  80 #include <pthread.h>
  81 #endif /* USE_RECURSIVE_LOCKS ... */
  82 #elif defined(_MSC_VER)
  83 #ifndef _M_AMD64
  84 /* These are already defined on AMD64 builds */
  85 #ifdef __cplusplus
  86 extern "C" {
  87 #endif /* __cplusplus */
  88 LONG __cdecl _InterlockedCompareExchange(LONG volatile *Dest, LONG Exchange, LONG Comp);
  89 LONG __cdecl _InterlockedExchange(LONG volatile *Target, LONG Value);
  90 #ifdef __cplusplus
  91 }
  92 #endif /* __cplusplus */
  93 #endif /* _M_AMD64 */
  94 #pragma intrinsic (_InterlockedCompareExchange)
  95 #pragma intrinsic (_InterlockedExchange)
  96 #define interlockedcompareexchange _InterlockedCompareExchange
  97 #define interlockedexchange _InterlockedExchange
  98 #elif defined(WIN32) && defined(__GNUC__)
  99 #define interlockedcompareexchange(a, b, c) __sync_val_compare_and_swap(a, c, b)
 100 #define interlockedexchange __sync_lock_test_and_set
 101 #endif /* Win32 */
 102 #else /* USE_LOCKS */
 103 #endif /* USE_LOCKS */
 104
 105 #ifndef LOCK_AT_FORK
 106 #define LOCK_AT_FORK 0
 107 #endif
 108
 109 /* Declarations for bit scanning on win32 */
 110 #if defined(_MSC_VER) && _MSC_VER>=1300
 111 #ifndef BitScanForward /* Try to avoid pulling in WinNT.h */
 112 #ifdef __cplusplus
 113 extern "C" {
 114 #endif /* __cplusplus */
 115 unsigned char _BitScanForward(unsigned long *index, unsigned long mask);
 116 unsigned char _BitScanReverse(unsigned long *index, unsigned long mask);
 117 #ifdef __cplusplus
 118 }
 119 #endif /* __cplusplus */
 120
 121 #define BitScanForward _BitScanForward
 122 #define BitScanReverse _BitScanReverse
 123 #pragma intrinsic(_BitScanForward)
 124 #pragma intrinsic(_BitScanReverse)
 125 #endif /* BitScanForward */
 126 #endif /* defined(_MSC_VER) && _MSC_VER>=1300 */
 127
 128 #ifndef WIN32
 129 #ifndef malloc_getpagesize
 130 #  ifdef _SC_PAGESIZE         /* some SVR4 systems omit an underscore */
 131 #    ifndef _SC_PAGE_SIZE
 132 #      define _SC_PAGE_SIZE _SC_PAGESIZE
 133 #    endif
 134 #  endif
 135 #  ifdef _SC_PAGE_SIZE
 136 #    define malloc_getpagesize sysconf(_SC_PAGE_SIZE)
 137 #  else
 138 #    if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE)
 139        extern size_t getpagesize();
 140 #      define malloc_getpagesize getpagesize()
 141 #    else
 142 #      ifdef WIN32 /* use supplied emulation of getpagesize */
 143 #        define malloc_getpagesize getpagesize()
 144 #      else
 145 #        ifndef LACKS_SYS_PARAM_H
 146 #          include <sys/param.h>
 147 #        endif
 148 #        ifdef EXEC_PAGESIZE
 149 #          define malloc_getpagesize EXEC_PAGESIZE
 150 #        else
 151 #          ifdef NBPG
 152 #            ifndef CLSIZE
 153 #              define malloc_getpagesize NBPG
 154 #            else
 155 #              define malloc_getpagesize (NBPG * CLSIZE)
 156 #            endif
 157 #          else
 158 #            ifdef NBPC
 159 #              define malloc_getpagesize NBPC
 160 #            else
 161 #              ifdef PAGESIZE
 162 #                define malloc_getpagesize PAGESIZE
 163 #              else /* just guess */
 164 #                define malloc_getpagesize ((size_t)4096U)
 165 #              endif
 166 #            endif
 167 #          endif
 168 #        endif
 169 #      endif
 170 #    endif
 171 #  endif
 172 #endif
 173 #endif
 174
 175 /* ------------------- size_t and alignment properties -------------------- */
 176
 177 /* The byte and bit size of a size_t */
 178 #define SIZE_T_SIZE         (sizeof(size_t))
 179 #define SIZE_T_BITSIZE      (sizeof(size_t) << 3)
 180
 181 /* Some constants coerced to size_t */
 182 /* Annoying but necessary to avoid errors on some platforms */
 183 #define SIZE_T_ZERO         ((size_t)0)
 184 #define SIZE_T_ONE          ((size_t)1)
 185 #define SIZE_T_TWO          ((size_t)2)
 186 #define SIZE_T_FOUR         ((size_t)4)
 187 #define TWO_SIZE_T_SIZES    (SIZE_T_SIZE<<1)
 188 #define FOUR_SIZE_T_SIZES   (SIZE_T_SIZE<<2)
 189 #define SIX_SIZE_T_SIZES    (FOUR_SIZE_T_SIZES+TWO_SIZE_T_SIZES)
 190 #define HALF_MAX_SIZE_T     (MAX_SIZE_T / 2U)
 191
 192 /* The bit mask value corresponding to MALLOC_ALIGNMENT */
 193 #define CHUNK_ALIGN_MASK    (MALLOC_ALIGNMENT - SIZE_T_ONE)
 194
 195 /* True if address a has acceptable alignment */
 196 #define is_aligned(A)       (((size_t)((A)) & (CHUNK_ALIGN_MASK)) == 0)
 197
 198 /* the number of bytes to offset an address to align it */
 199 #define align_offset(A)\
 200  ((((size_t)(A) & CHUNK_ALIGN_MASK) == 0)? 0 :\
 201   ((MALLOC_ALIGNMENT - ((size_t)(A) & CHUNK_ALIGN_MASK)) & CHUNK_ALIGN_MASK))
 202
 203 /* -------------------------- MMAP preliminaries ------------------------- */
 204
 205 /*
 206    If HAVE_MORECORE or HAVE_MMAP are false, we just define calls and
 207    checks to fail so compiler optimizer can delete code rather than
 208    using so many "#if"s.
 209 */
 210
 211
 212 /* MORECORE and MMAP must return MFAIL on failure */
 213 #define MFAIL                ((void*)(MAX_SIZE_T))
 214 #define CMFAIL               ((char*)(MFAIL)) /* defined for convenience */
 215
 216 #if HAVE_MMAP
 217
 218 #ifndef WIN32
 219 #define MUNMAP_DEFAULT(a, s)  munmap((a), (s))
 220 #define MMAP_PROT            (PROT_READ|PROT_WRITE)
 221 #if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
 222 #define MAP_ANONYMOUS        MAP_ANON
 223 #endif /* MAP_ANON */
 224 #ifdef MAP_ANONYMOUS
 225 #define MMAP_FLAGS           (MAP_PRIVATE|MAP_ANONYMOUS)
 226 #define MMAP_DEFAULT(s)       mmap(0, (s), MMAP_PROT, MMAP_FLAGS, -1, 0)
 227 #else /* MAP_ANONYMOUS */
 228 /*
 229    Nearly all versions of mmap support MAP_ANONYMOUS, so the following
 230    is unlikely to be needed, but is supplied just in case.
 231 */
 232 #define MMAP_FLAGS           (MAP_PRIVATE)
 233 static int dev_zero_fd = -1; /* Cached file descriptor for /dev/zero. */
 234 #define MMAP_DEFAULT(s) ((dev_zero_fd < 0) ? \
 235            (dev_zero_fd = open("/dev/zero", O_RDWR), \
 236             mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0)) : \
 237             mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0))
 238 #endif /* MAP_ANONYMOUS */
 239
 240 #define DIRECT_MMAP_DEFAULT(s) MMAP_DEFAULT(s)
 241
 242 #else /* WIN32 */
 243
 244 /* Win32 MMAP via VirtualAlloc */
 245 static FORCEINLINE void* win32mmap(size_t size) {
 246   void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT, PAGE_READWRITE);
 247   return (ptr != 0)? ptr: MFAIL;
 248 }
 249
 250 /* For direct MMAP, use MEM_TOP_DOWN to minimize interference */
 251 static FORCEINLINE void* win32direct_mmap(size_t size) {
 252   void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT|MEM_TOP_DOWN,
 253                            PAGE_READWRITE);
 254   return (ptr != 0)? ptr: MFAIL;
 255 }
 256
 257 /* This function supports releasing coalesed segments */
 258 static FORCEINLINE int win32munmap(void* ptr, size_t size) {
 259   MEMORY_BASIC_INFORMATION minfo;
 260   char* cptr = (char*)ptr;
 261   while (size) {
 262     if (VirtualQuery(cptr, &minfo, sizeof(minfo)) == 0)
 263       return -1;
 264     if (minfo.BaseAddress != cptr || minfo.AllocationBase != cptr ||
 265         minfo.State != MEM_COMMIT || minfo.RegionSize > size)
 266       return -1;
 267     if (VirtualFree(cptr, 0, MEM_RELEASE) == 0)
 268       return -1;
 269     cptr += minfo.RegionSize;
 270     size -= minfo.RegionSize;
 271   }
 272   return 0;
 273 }
 274
 275 #define MMAP_DEFAULT(s)             win32mmap(s)
 276 #define MUNMAP_DEFAULT(a, s)        win32munmap((a), (s))
 277 #define DIRECT_MMAP_DEFAULT(s)      win32direct_mmap(s)
 278 #endif /* WIN32 */
 279 #endif /* HAVE_MMAP */
 280
 281 #if HAVE_MREMAP
 282 #ifndef WIN32
 283 #define MREMAP_DEFAULT(addr, osz, nsz, mv) mremap((addr), (osz), (nsz), (mv))
 284 #endif /* WIN32 */
 285 #endif /* HAVE_MREMAP */
 286
 287 /**
 288  * Define CALL_MORECORE
 289  */
 290 #if HAVE_MORECORE
 291     #ifdef MORECORE
 292         #define CALL_MORECORE(S)    MORECORE(S)
 293     #else  /* MORECORE */
 294         #define CALL_MORECORE(S)    MORECORE_DEFAULT(S)
 295     #endif /* MORECORE */
 296 #else  /* HAVE_MORECORE */
 297     #define CALL_MORECORE(S)        MFAIL
 298 #endif /* HAVE_MORECORE */
 299
 300 /**
 301  * Define CALL_MMAP/CALL_MUNMAP/CALL_DIRECT_MMAP
 302  */
 303 #if HAVE_MMAP
 304     #define USE_MMAP_BIT            (SIZE_T_ONE)
 305
 306     #ifdef MMAP
 307         #define CALL_MMAP(s)        MMAP(s)
 308     #else /* MMAP */
 309         #define CALL_MMAP(s)        MMAP_DEFAULT(s)
 310     #endif /* MMAP */
 311     #ifdef MUNMAP
 312         #define CALL_MUNMAP(a, s)   MUNMAP((a), (s))
 313     #else /* MUNMAP */
 314         #define CALL_MUNMAP(a, s)   MUNMAP_DEFAULT((a), (s))
 315     #endif /* MUNMAP */
 316     #ifdef DIRECT_MMAP
 317         #define CALL_DIRECT_MMAP(s) DIRECT_MMAP(s)
 318     #else /* DIRECT_MMAP */
 319         #define CALL_DIRECT_MMAP(s) DIRECT_MMAP_DEFAULT(s)
 320     #endif /* DIRECT_MMAP */
 321 #else  /* HAVE_MMAP */
 322     #define USE_MMAP_BIT            (SIZE_T_ZERO)
 323
 324     #define MMAP(s)                 MFAIL
 325     #define MUNMAP(a, s)            (-1)
 326     #define DIRECT_MMAP(s)          MFAIL
 327     #define CALL_DIRECT_MMAP(s)     DIRECT_MMAP(s)
 328     #define CALL_MMAP(s)            MMAP(s)
 329     #define CALL_MUNMAP(a, s)       MUNMAP((a), (s))
 330 #endif /* HAVE_MMAP */
 331
 332 /**
 333  * Define CALL_MREMAP
 334  */
 335 #if HAVE_MMAP && HAVE_MREMAP
 336     #ifdef MREMAP
 337         #define CALL_MREMAP(addr, osz, nsz, mv) MREMAP((addr), (osz), (nsz), (mv))
 338     #else /* MREMAP */
 339         #define CALL_MREMAP(addr, osz, nsz, mv) MREMAP_DEFAULT((addr), (osz), (nsz), (mv))
 340     #endif /* MREMAP */
 341 #else  /* HAVE_MMAP && HAVE_MREMAP */
 342     #define CALL_MREMAP(addr, osz, nsz, mv)     MFAIL
 343 #endif /* HAVE_MMAP && HAVE_MREMAP */
 344
 345 /* mstate bit set if continguous morecore disabled or failed */
 346 #define USE_NONCONTIGUOUS_BIT (4U)
 347
 348 /* mstate bit set if no expansion allowed */
 349 #define USE_NOEXPAND_BIT (8U)
 350
 351 /* trace allocations if set */
 352 #define USE_TRACE_BIT (16U)
 353
 354 /* segment bit set in create_mspace_with_base */
 355 #define EXTERN_BIT            (8U)
 356
 357
 358 /* --------------------------- Lock preliminaries ------------------------ */
 359
 360 /*
 361   When locks are defined, there is one global lock, plus
 362   one per-mspace lock.
 363
 364   The global lock_ensures that mparams.magic and other unique
 365   mparams values are initialized only once. It also protects
 366   sequences of calls to MORECORE.  In many cases sys_alloc requires
 367   two calls, that should not be interleaved with calls by other
 368   threads.  This does not protect against direct calls to MORECORE
 369   by other threads not using this lock, so there is still code to
 370   cope the best we can on interference.
 371
 372   Per-mspace locks surround calls to malloc, free, etc.
 373   By default, locks are simple non-reentrant mutexes.
 374
 375   Because lock-protected regions generally have bounded times, it is
 376   OK to use the supplied simple spinlocks. Spinlocks are likely to
 377   improve performance for lightly contended applications, but worsen
 378   performance under heavy contention.
 379
 380   If USE_LOCKS is > 1, the definitions of lock routines here are
 381   bypassed, in which case you will need to define the type MLOCK_T,
 382   and at least INITIAL_LOCK, DESTROY_LOCK, ACQUIRE_LOCK, RELEASE_LOCK
 383   and TRY_LOCK.  You must also declare a
 384     static MLOCK_T malloc_global_mutex = { initialization values };.
 385
 386 */
 387
 388 #if !USE_LOCKS
 389 #define USE_LOCK_BIT               (0U)
 390 #define INITIAL_LOCK(l)            (0)
 391 #define DESTROY_LOCK(l)            (0)
 392 #define ACQUIRE_MALLOC_GLOBAL_LOCK()
 393 #define RELEASE_MALLOC_GLOBAL_LOCK()
 394
 395 #else
 396 #if USE_LOCKS > 1
 397 /* -----------------------  User-defined locks ------------------------ */
 398 /* Define your own lock implementation here */
 399 /* #define INITIAL_LOCK(lk)  ... */
 400 /* #define DESTROY_LOCK(lk)  ... */
 401 /* #define ACQUIRE_LOCK(lk)  ... */
 402 /* #define RELEASE_LOCK(lk)  ... */
 403 /* #define TRY_LOCK(lk) ... */
 404 /* static MLOCK_T malloc_global_mutex = ... */
 405
 406 #elif USE_SPIN_LOCKS
 407
 408 /* First, define CAS_LOCK and CLEAR_LOCK on ints */
 409 /* Note CAS_LOCK defined to return 0 on success */
 410
 411 #if defined(__GNUC__)&& (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 1))
 412 #define CAS_LOCK(sl)     __sync_lock_test_and_set(sl, 1)
 413 #define CLEAR_LOCK(sl)   __sync_lock_release(sl)
 414
 415 #elif (defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__)))
 416 /* Custom spin locks for older gcc on x86 */
 417 static FORCEINLINE int x86_cas_lock(int *sl) {
 418   int ret;
 419   int val = 1;
 420   int cmp = 0;
 421   __asm__ __volatile__  ("lock; cmpxchgl %1, %2"
 422                          : "=a" (ret)
 423                          : "r" (val), "m" (*(sl)), "0"(cmp)
 424                          : "memory", "cc");
 425   return ret;
 426 }
 427
 428 static FORCEINLINE void x86_clear_lock(int* sl) {
 429   assert(*sl != 0);
 430   int prev = 0;
 431   int ret;
 432   __asm__ __volatile__ ("lock; xchgl %0, %1"
 433                         : "=r" (ret)
 434                         : "m" (*(sl)), "0"(prev)
 435                         : "memory");
 436 }
 437
 438 #define CAS_LOCK(sl)     x86_cas_lock(sl)
 439 #define CLEAR_LOCK(sl)   x86_clear_lock(sl)
 440
 441 #else /* Win32 MSC */
 442 #define CAS_LOCK(sl)     interlockedexchange(sl, (LONG)1)
 443 #define CLEAR_LOCK(sl)   interlockedexchange (sl, (LONG)0)
 444
 445 #endif /* ... gcc spins locks ... */
 446
 447 /* How to yield for a spin lock */
 448 #define SPINS_PER_YIELD       63
 449 #if defined(_MSC_VER)
 450 #define SLEEP_EX_DURATION     50 /* delay for yield/sleep */
 451 #define SPIN_LOCK_YIELD  SleepEx(SLEEP_EX_DURATION, FALSE)
 452 #elif defined (__SVR4) && defined (__sun) /* solaris */
 453 #define SPIN_LOCK_YIELD   thr_yield();
 454 #elif !defined(LACKS_SCHED_H)
 455 #define SPIN_LOCK_YIELD   sched_yield();
 456 #else
 457 #define SPIN_LOCK_YIELD
 458 #endif /* ... yield ... */
 459
 460 #if !defined(USE_RECURSIVE_LOCKS) || USE_RECURSIVE_LOCKS == 0
 461 /* Plain spin locks use single word (embedded in malloc_states) */
 462 static int spin_acquire_lock(int *sl) {
 463   int spins = 0;
 464   while (*(volatile int *)sl != 0 || CAS_LOCK(sl)) {
 465     if ((++spins & SPINS_PER_YIELD) == 0) {
 466       SPIN_LOCK_YIELD;
 467     }
 468   }
 469   return 0;
 470 }
 471
 472 #define MLOCK_T               int
 473 #define TRY_LOCK(sl)          !CAS_LOCK(sl)
 474 #define RELEASE_LOCK(sl)      CLEAR_LOCK(sl)
 475 #define ACQUIRE_LOCK(sl)      (CAS_LOCK(sl)? spin_acquire_lock(sl) : 0)
 476 #define INITIAL_LOCK(sl)      (*sl = 0)
 477 #define DESTROY_LOCK(sl)      (0)
 478 static MLOCK_T malloc_global_mutex = 0;
 479
 480 #else /* USE_RECURSIVE_LOCKS */
 481 /* types for lock owners */
 482 #ifdef WIN32
 483 #define THREAD_ID_T           DWORD
 484 #define CURRENT_THREAD        GetCurrentThreadId()
 485 #define EQ_OWNER(X,Y)         ((X) == (Y))
 486 #else
 487 /*
 488   Note: the following assume that pthread_t is a type that can be
 489   initialized to (casted) zero. If this is not the case, you will need to
 490   somehow redefine these or not use spin locks.
 491 */
 492 #define THREAD_ID_T           pthread_t
 493 #define CURRENT_THREAD        pthread_self()
 494 #define EQ_OWNER(X,Y)         pthread_equal(X, Y)
 495 #endif
 496
 497 struct malloc_recursive_lock {
 498   int sl;
 499   unsigned int c;
 500   THREAD_ID_T threadid;
 501 };
 502
 503 #define MLOCK_T  struct malloc_recursive_lock
 504 static MLOCK_T malloc_global_mutex = { 0, 0, (THREAD_ID_T)0};
 505
 506 static FORCEINLINE void recursive_release_lock(MLOCK_T *lk) {
 507   assert(lk->sl != 0);
 508   if (--lk->c == 0) {
 509     CLEAR_LOCK(&lk->sl);
 510   }
 511 }
 512
 513 static FORCEINLINE int recursive_acquire_lock(MLOCK_T *lk) {
 514   THREAD_ID_T mythreadid = CURRENT_THREAD;
 515   int spins = 0;
 516   for (;;) {
 517     if (*((volatile int *)(&lk->sl)) == 0) {
 518       if (!CAS_LOCK(&lk->sl)) {
 519         lk->threadid = mythreadid;
 520         lk->c = 1;
 521         return 0;
 522       }
 523     }
 524     else if (EQ_OWNER(lk->threadid, mythreadid)) {
 525       ++lk->c;
 526       return 0;
 527     }
 528     if ((++spins & SPINS_PER_YIELD) == 0) {
 529       SPIN_LOCK_YIELD;
 530     }
 531   }
 532 }
 533
 534 static FORCEINLINE int recursive_try_lock(MLOCK_T *lk) {
 535   THREAD_ID_T mythreadid = CURRENT_THREAD;
 536   if (*((volatile int *)(&lk->sl)) == 0) {
 537     if (!CAS_LOCK(&lk->sl)) {
 538       lk->threadid = mythreadid;
 539       lk->c = 1;
 540       return 1;
 541     }
 542   }
 543   else if (EQ_OWNER(lk->threadid, mythreadid)) {
 544     ++lk->c;
 545     return 1;
 546   }
 547   return 0;
 548 }
 549
 550 #define RELEASE_LOCK(lk)      recursive_release_lock(lk)
 551 #define TRY_LOCK(lk)          recursive_try_lock(lk)
 552 #define ACQUIRE_LOCK(lk)      recursive_acquire_lock(lk)
 553 #define INITIAL_LOCK(lk)      ((lk)->threadid = (THREAD_ID_T)0, (lk)->sl = 0, (lk)->c = 0)
 554 #define DESTROY_LOCK(lk)      (0)
 555 #endif /* USE_RECURSIVE_LOCKS */
 556
 557 #elif defined(WIN32) /* Win32 critical sections */
 558 #define MLOCK_T               CRITICAL_SECTION
 559 #define ACQUIRE_LOCK(lk)      (EnterCriticalSection(lk), 0)
 560 #define RELEASE_LOCK(lk)      LeaveCriticalSection(lk)
 561 #define TRY_LOCK(lk)          TryEnterCriticalSection(lk)
 562 #define INITIAL_LOCK(lk)      (!InitializeCriticalSectionAndSpinCount((lk), 0x80000000|4000))
 563 #define DESTROY_LOCK(lk)      (DeleteCriticalSection(lk), 0)
 564 #define NEED_GLOBAL_LOCK_INIT
 565
 566 static MLOCK_T malloc_global_mutex;
 567 static volatile LONG malloc_global_mutex_status;
 568
 569 /* Use spin loop to initialize global lock */
 570 static void init_malloc_global_mutex() {
 571   for (;;) {
 572     long stat = malloc_global_mutex_status;
 573     if (stat > 0)
 574       return;
 575     /* transition to < 0 while initializing, then to > 0) */
 576     if (stat == 0 &&
 577         interlockedcompareexchange(&malloc_global_mutex_status, (LONG)-1, (LONG)0) == 0) {
 578       InitializeCriticalSection(&malloc_global_mutex);
 579       interlockedexchange(&malloc_global_mutex_status, (LONG)1);
 580       return;
 581     }
 582     SleepEx(0, FALSE);
 583   }
 584 }
 585
 586 #else /* pthreads-based locks */
 587 #define MLOCK_T               pthread_mutex_t
 588 #define ACQUIRE_LOCK(lk)      pthread_mutex_lock(lk)
 589 #define RELEASE_LOCK(lk)      pthread_mutex_unlock(lk)
 590 #define TRY_LOCK(lk)          (!pthread_mutex_trylock(lk))
 591 #define INITIAL_LOCK(lk)      pthread_init_lock(lk)
 592 #define DESTROY_LOCK(lk)      pthread_mutex_destroy(lk)
 593
 594 #if defined(USE_RECURSIVE_LOCKS) && USE_RECURSIVE_LOCKS != 0 && defined(linux) && !defined(PTHREAD_MUTEX_RECURSIVE)
 595 /* Cope with old-style linux recursive lock initialization by adding */
 596 /* skipped internal declaration from pthread.h */
 597 extern int pthread_mutexattr_setkind_np __P ((pthread_mutexattr_t *__attr,
 598                                               int __kind));
 599 #define PTHREAD_MUTEX_RECURSIVE PTHREAD_MUTEX_RECURSIVE_NP
 600 #define pthread_mutexattr_settype(x,y) pthread_mutexattr_setkind_np(x,y)
 601 #endif /* USE_RECURSIVE_LOCKS ... */
 602
 603 static MLOCK_T malloc_global_mutex = PTHREAD_MUTEX_INITIALIZER;
 604
 605 static int pthread_init_lock (MLOCK_T *lk) {
 606   pthread_mutexattr_t attr;
 607   if (pthread_mutexattr_init(&attr)) return 1;
 608 #if defined(USE_RECURSIVE_LOCKS) && USE_RECURSIVE_LOCKS != 0
 609   if (pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE)) return 1;
 610 #endif
 611   if (pthread_mutex_init(lk, &attr)) return 1;
 612   if (pthread_mutexattr_destroy(&attr)) return 1;
 613   return 0;
 614 }
 615
 616 #endif /* ... lock types ... */
 617
 618 /* Common code for all lock types */
 619 #define USE_LOCK_BIT               (2U)
 620
 621 #ifndef ACQUIRE_MALLOC_GLOBAL_LOCK
 622 #define ACQUIRE_MALLOC_GLOBAL_LOCK()  ACQUIRE_LOCK(&malloc_global_mutex);
 623 #endif
 624
 625 #ifndef RELEASE_MALLOC_GLOBAL_LOCK
 626 #define RELEASE_MALLOC_GLOBAL_LOCK()  RELEASE_LOCK(&malloc_global_mutex);
 627 #endif
 628
 629 #endif /* USE_LOCKS */
 630
 631 /* -----------------------  Chunk representations ------------------------ */
 632
 633 /*
 634   (The following includes lightly edited explanations by Colin Plumb.)
 635
 636   The malloc_chunk declaration below is misleading (but accurate and
 637   necessary).  It declares a "view" into memory allowing access to
 638   necessary fields at known offsets from a given base.
 639
 640   Chunks of memory are maintained using a `boundary tag' method as
 641   originally described by Knuth.  (See the paper by Paul Wilson
 642   ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a survey of such
 643   techniques.)  Sizes of free chunks are stored both in the front of
 644   each chunk and at the end.  This makes consolidating fragmented
 645   chunks into bigger chunks fast.  The head fields also hold bits
 646   representing whether chunks are free or in use.
 647
 648   Here are some pictures to make it clearer.  They are "exploded" to
 649   show that the state of a chunk can be thought of as extending from
 650   the high 31 bits of the head field of its header through the
 651   prev_foot and PINUSE_BIT bit of the following chunk header.
 652
 653   A chunk that's in use looks like:
 654
 655    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 656            | Size of previous chunk (if P = 0)                             |
 657            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 658          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
 659          | Size of this chunk                                         1| +-+
 660    mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 661          |                                                               |
 662          +-                                                             -+
 663          |                                                               |
 664          +-                                                             -+
 665          |                                                               :
 666          +-      size - sizeof(size_t) available payload bytes          -+
 667          :                                                               |
 668  chunk-> +-                                                             -+
 669          |                                                               |
 670          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 671        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1|
 672        | Size of next chunk (may or may not be in use)               | +-+
 673  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 674
 675     And if it's free, it looks like this:
 676
 677    chunk-> +-                                                             -+
 678            | User payload (must be in use, or we would have merged!)       |
 679            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 680          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
 681          | Size of this chunk                                         0| +-+
 682    mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 683          | Next pointer                                                  |
 684          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 685          | Prev pointer                                                  |
 686          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 687          |                                                               :
 688          +-      size - sizeof(struct chunk) unused bytes               -+
 689          :                                                               |
 690  chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 691          | Size of this chunk                                            |
 692          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 693        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0|
 694        | Size of next chunk (must be in use, or we would have merged)| +-+
 695  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 696        |                                                               :
 697        +- User payload                                                -+
 698        :                                                               |
 699        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 700                                                                      |0|
 701                                                                      +-+
 702   Note that since we always merge adjacent free chunks, the chunks
 703   adjacent to a free chunk must be in use.
 704
 705   Given a pointer to a chunk (which can be derived trivially from the
 706   payload pointer) we can, in O(1) time, find out whether the adjacent
 707   chunks are free, and if so, unlink them from the lists that they
 708   are on and merge them with the current chunk.
 709
 710   Chunks always begin on even word boundaries, so the mem portion
 711   (which is returned to the user) is also on an even word boundary, and
 712   thus at least double-word aligned.
 713
 714   The P (PINUSE_BIT) bit, stored in the unused low-order bit of the
 715   chunk size (which is always a multiple of two words), is an in-use
 716   bit for the *previous* chunk.  If that bit is *clear*, then the
 717   word before the current chunk size contains the previous chunk
 718   size, and can be used to find the front of the previous chunk.
 719   The very first chunk allocated always has this bit set, preventing
 720   access to non-existent (or non-owned) memory. If pinuse is set for
 721   any given chunk, then you CANNOT determine the size of the
 722   previous chunk, and might even get a memory addressing fault when
 723   trying to do so.
 724
 725   The C (CINUSE_BIT) bit, stored in the unused second-lowest bit of
 726   the chunk size redundantly records whether the current chunk is
 727   inuse (unless the chunk is mmapped). This redundancy enables usage
 728   checks within free and realloc, and reduces indirection when freeing
 729   and consolidating chunks.
 730
 731   Each freshly allocated chunk must have both cinuse and pinuse set.
 732   That is, each allocated chunk borders either a previously allocated
 733   and still in-use chunk, or the base of its memory arena. This is
 734   ensured by making all allocations from the `lowest' part of any
 735   found chunk.  Further, no free chunk physically borders another one,
 736   so each free chunk is known to be preceded and followed by either
 737   inuse chunks or the ends of memory.
 738
 739   Note that the `foot' of the current chunk is actually represented
 740   as the prev_foot of the NEXT chunk. This makes it easier to
 741   deal with alignments etc but can be very confusing when trying
 742   to extend or adapt this code.
 743
 744   The exceptions to all this are
 745
 746      1. The special chunk `top' is the top-most available chunk (i.e.,
 747         the one bordering the end of available memory). It is treated
 748         specially.  Top is never included in any bin, is used only if
 749         no other chunk is available, and is released back to the
 750         system if it is very large (see M_TRIM_THRESHOLD).  In effect,
 751         the top chunk is treated as larger (and thus less well
 752         fitting) than any other available chunk.  The top chunk
 753         doesn't update its trailing size field since there is no next
 754         contiguous chunk that would have to index off it. However,
 755         space is still allocated for it (TOP_FOOT_SIZE) to enable
 756         separation or merging when space is extended.
 757
 758      3. Chunks allocated via mmap, have both cinuse and pinuse bits
 759         cleared in their head fields.  Because they are allocated
 760         one-by-one, each must carry its own prev_foot field, which is
 761         also used to hold the offset this chunk has within its mmapped
 762         region, which is needed to preserve alignment. Each mmapped
 763         chunk is trailed by the first two fields of a fake next-chunk
 764         for sake of usage checks.
 765
 766 */
 767
 768 struct malloc_chunk {
 769   size_t               prev_foot;  /* Size of previous chunk (if free).  */
 770   size_t               head;       /* Size and inuse bits. */
 771   struct malloc_chunk* fd;         /* double links -- used only if free. */
 772   struct malloc_chunk* bk;
 773 };
 774
 775 typedef struct malloc_chunk  mchunk;
 776 typedef struct malloc_chunk* mchunkptr;
 777 typedef struct malloc_chunk* sbinptr;  /* The type of bins of chunks */
 778 typedef unsigned int bindex_t;         /* Described below */
 779 typedef unsigned int binmap_t;         /* Described below */
 780 typedef unsigned int flag_t;           /* The type of various bit flag sets */
 781
 782 /* ------------------- Chunks sizes and alignments ----------------------- */
 783
 784 #define MCHUNK_SIZE         (sizeof(mchunk))
 785
 786 #if FOOTERS
 787 #define CHUNK_OVERHEAD      (TWO_SIZE_T_SIZES)
 788 #else /* FOOTERS */
 789 #define CHUNK_OVERHEAD      (SIZE_T_SIZE)
 790 #endif /* FOOTERS */
 791
 792 /* MMapped chunks need a second word of overhead ... */
 793 #define MMAP_CHUNK_OVERHEAD (TWO_SIZE_T_SIZES)
 794 /* ... and additional padding for fake next-chunk at foot */
 795 #define MMAP_FOOT_PAD       (FOUR_SIZE_T_SIZES)
 796
 797 /* The smallest size we can malloc is an aligned minimal chunk */
 798 #define MIN_CHUNK_SIZE\
 799   ((MCHUNK_SIZE + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
 800
 801 /* conversion from malloc headers to user pointers, and back */
 802 #define chunk2mem(p)        ((void*)((char*)(p)       + TWO_SIZE_T_SIZES))
 803 #define mem2chunk(mem)      ((mchunkptr)((char*)(mem) - TWO_SIZE_T_SIZES))
 804 /* chunk associated with aligned address A */
 805 #define align_as_chunk(A)   (mchunkptr)((A) + align_offset(chunk2mem(A)))
 806
 807 /* Bounds on request (not chunk) sizes. */
 808 #define MAX_REQUEST         ((-MIN_CHUNK_SIZE) << 2)
 809 #define MIN_REQUEST         (MIN_CHUNK_SIZE - CHUNK_OVERHEAD - SIZE_T_ONE)
 810
 811 /* pad request bytes into a usable size */
 812 #define pad_request(req) \
 813    (((req) + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
 814
 815 /* pad request, checking for minimum (but not maximum) */
 816 #define request2size(req) \
 817   (((req) < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(req))
 818
 819
 820 /* ------------------ Operations on head and foot fields ----------------- */
 821
 822 /*
 823   The head field of a chunk is or'ed with PINUSE_BIT when previous
 824   adjacent chunk in use, and or'ed with CINUSE_BIT if this chunk is in
 825   use, unless mmapped, in which case both bits are cleared.
 826
 827   FLAG4_BIT is not used by this malloc, but might be useful in extensions.
 828 */
 829
 830 #define PINUSE_BIT          (SIZE_T_ONE)
 831 #define CINUSE_BIT          (SIZE_T_TWO)
 832 #define FLAG4_BIT           (SIZE_T_FOUR)
 833 #define INUSE_BITS          (PINUSE_BIT|CINUSE_BIT)
 834 #define FLAG_BITS           (PINUSE_BIT|CINUSE_BIT|FLAG4_BIT)
 835
 836 /* Head value for fenceposts */
 837 #define FENCEPOST_HEAD      (INUSE_BITS|SIZE_T_SIZE)
 838
 839 /* extraction of fields from head words */
 840 #define cinuse(p)           ((p)->head & CINUSE_BIT)
 841 #define pinuse(p)           ((p)->head & PINUSE_BIT)
 842 #define flag4inuse(p)       ((p)->head & FLAG4_BIT)
 843 #define is_inuse(p)         (((p)->head & INUSE_BITS) != PINUSE_BIT)
 844 #define is_mmapped(p)       (((p)->head & INUSE_BITS) == 0)
 845
 846 #define chunksize(p)        ((p)->head & ~(FLAG_BITS))
 847
 848 #define clear_pinuse(p)     ((p)->head &= ~PINUSE_BIT)
 849 #define set_flag4(p)        ((p)->head |= FLAG4_BIT)
 850 #define clear_flag4(p)      ((p)->head &= ~FLAG4_BIT)
 851
 852 /* Treat space at ptr +/- offset as a chunk */
 853 #define chunk_plus_offset(p, s)  ((mchunkptr)(((char*)(p)) + (s)))
 854 #define chunk_minus_offset(p, s) ((mchunkptr)(((char*)(p)) - (s)))
 855
 856 /* Ptr to next or previous physical malloc_chunk. */
 857 #define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->head & ~FLAG_BITS)))
 858 #define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_foot) ))
 859
 860 /* extract next chunk's pinuse bit */
 861 #define next_pinuse(p)  ((next_chunk(p)->head) & PINUSE_BIT)
 862
 863 /* Get/set size at footer */
 864 #define get_foot(p, s)  (((mchunkptr)((char*)(p) + (s)))->prev_foot)
 865 #define set_foot(p, s)  (((mchunkptr)((char*)(p) + (s)))->prev_foot = (s))
 866
 867 /* Set size, pinuse bit, and foot */
 868 #define set_size_and_pinuse_of_free_chunk(p, s)\
 869   ((p)->head = (s|PINUSE_BIT), set_foot(p, s))
 870
 871 /* Set size, pinuse bit, foot, and clear next pinuse */
 872 #define set_free_with_pinuse(p, s, n)\
 873   (clear_pinuse(n), set_size_and_pinuse_of_free_chunk(p, s))
 874
 875 /* Get the internal overhead associated with chunk p */
 876 #define overhead_for(p)\
 877  (is_mmapped(p)? MMAP_CHUNK_OVERHEAD : CHUNK_OVERHEAD)
 878
 879 /* Return true if malloced space is not necessarily cleared */
 880 #if MMAP_CLEARS
 881 #define calloc_must_clear(p) (!is_mmapped(p))
 882 #else /* MMAP_CLEARS */
 883 #define calloc_must_clear(p) (1)
 884 #endif /* MMAP_CLEARS */
 885
 886 /* ---------------------- Overlaid data structures ----------------------- */
 887
 888 /*
 889   When chunks are not in use, they are treated as nodes of either
 890   lists or trees.
 891
 892   "Small"  chunks are stored in circular doubly-linked lists, and look
 893   like this:
 894
 895     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 896             |             Size of previous chunk                            |
 897             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 898     `head:' |             Size of chunk, in bytes                         |P|
 899       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 900             |             Forward pointer to next chunk in list             |
 901             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 902             |             Back pointer to previous chunk in list            |
 903             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 904             |             Unused space (may be 0 bytes long)                .
 905             .                                                               .
 906             .                                                               |
 907 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 908     `foot:' |             Size of chunk, in bytes                           |
 909             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 910
 911   Larger chunks are kept in a form of bitwise digital trees (aka
 912   tries) keyed on chunksizes.  Because malloc_tree_chunks are only for
 913   free chunks greater than 256 bytes, their size doesn't impose any
 914   constraints on user chunk sizes.  Each node looks like:
 915
 916     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 917             |             Size of previous chunk                            |
 918             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 919     `head:' |             Size of chunk, in bytes                         |P|
 920       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 921             |             Forward pointer to next chunk of same size        |
 922             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 923             |             Back pointer to previous chunk of same size       |
 924             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 925             |             Pointer to left child (child[0])                  |
 926             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 927             |             Pointer to right child (child[1])                 |
 928             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 929             |             Pointer to parent                                 |
 930             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 931             |             bin index of this chunk                           |
 932             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 933             |             Unused space                                      .
 934             .                                                               |
 935 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 936     `foot:' |             Size of chunk, in bytes                           |
 937             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 938
 939   Each tree holding treenodes is a tree of unique chunk sizes.  Chunks
 940   of the same size are arranged in a circularly-linked list, with only
 941   the oldest chunk (the next to be used, in our FIFO ordering)
 942   actually in the tree.  (Tree members are distinguished by a non-null
 943   parent pointer.)  If a chunk with the same size an an existing node
 944   is inserted, it is linked off the existing node using pointers that
 945   work in the same way as fd/bk pointers of small chunks.
 946
 947   Each tree contains a power of 2 sized range of chunk sizes (the
 948   smallest is 0x100 <= x < 0x180), which is is divided in half at each
 949   tree level, with the chunks in the smaller half of the range (0x100
 950   <= x < 0x140 for the top nose) in the left subtree and the larger
 951   half (0x140 <= x < 0x180) in the right subtree.  This is, of course,
 952   done by inspecting individual bits.
 953
 954   Using these rules, each node's left subtree contains all smaller
 955   sizes than its right subtree.  However, the node at the root of each
 956   subtree has no particular ordering relationship to either.  (The
 957   dividing line between the subtree sizes is based on trie relation.)
 958   If we remove the last chunk of a given size from the interior of the
 959   tree, we need to replace it with a leaf node.  The tree ordering
 960   rules permit a node to be replaced by any leaf below it.
 961
 962   The smallest chunk in a tree (a common operation in a best-fit
 963   allocator) can be found by walking a path to the leftmost leaf in
 964   the tree.  Unlike a usual binary tree, where we follow left child
 965   pointers until we reach a null, here we follow the right child
 966   pointer any time the left one is null, until we reach a leaf with
 967   both child pointers null. The smallest chunk in the tree will be
 968   somewhere along that path.
 969
 970   The worst case number of steps to add, find, or remove a node is
 971   bounded by the number of bits differentiating chunks within
 972   bins. Under current bin calculations, this ranges from 6 up to 21
 973   (for 32 bit sizes) or up to 53 (for 64 bit sizes). The typical case
 974   is of course much better.
 975 */
 976
 977 struct malloc_tree_chunk {
 978   /* The first four fields must be compatible with malloc_chunk */
 979   size_t                    prev_foot;
 980   size_t                    head;
 981   struct malloc_tree_chunk* fd;
 982   struct malloc_tree_chunk* bk;
 983
 984   struct malloc_tree_chunk* child[2];
 985   struct malloc_tree_chunk* parent;
 986   bindex_t                  index;
 987 };
 988
 989 typedef struct malloc_tree_chunk  tchunk;
 990 typedef struct malloc_tree_chunk* tchunkptr;
 991 typedef struct malloc_tree_chunk* tbinptr; /* The type of bins of trees */
 992
 993 /* A little helper macro for trees */
 994 #define leftmost_child(t) ((t)->child[0] != 0? (t)->child[0] : (t)->child[1])
 995
 996 /* ----------------------------- Segments -------------------------------- */
 997
 998 /*
 999   Each malloc space may include non-contiguous segments, held in a
1000   list headed by an embedded malloc_segment record representing the
1001   top-most space. Segments also include flags holding properties of
1002   the space. Large chunks that are directly allocated by mmap are not
1003   included in this list. They are instead independently created and
1004   destroyed without otherwise keeping track of them.
1005
1006   Segment management mainly comes into play for spaces allocated by
1007   MMAP.  Any call to MMAP might or might not return memory that is
1008   adjacent to an existing segment.  MORECORE normally contiguously
1009   extends the current space, so this space is almost always adjacent,
1010   which is simpler and faster to deal with. (This is why MORECORE is
1011   used preferentially to MMAP when both are available -- see
1012   sys_alloc.)  When allocating using MMAP, we don't use any of the
1013   hinting mechanisms (inconsistently) supported in various
1014   implementations of unix mmap, or distinguish reserving from
1015   committing memory. Instead, we just ask for space, and exploit
1016   contiguity when we get it.  It is probably possible to do
1017   better than this on some systems, but no general scheme seems
1018   to be significantly better.
1019
1020   Management entails a simpler variant of the consolidation scheme
1021   used for chunks to reduce fragmentation -- new adjacent memory is
1022   normally prepended or appended to an existing segment. However,
1023   there are limitations compared to chunk consolidation that mostly
1024   reflect the fact that segment processing is relatively infrequent
1025   (occurring only when getting memory from system) and that we
1026   don't expect to have huge numbers of segments:
1027
1028   * Segments are not indexed, so traversal requires linear scans.  (It
1029     would be possible to index these, but is not worth the extra
1030     overhead and complexity for most programs on most platforms.)
1031   * New segments are only appended to old ones when holding top-most
1032     memory; if they cannot be prepended to others, they are held in
1033     different segments.
1034
1035   Except for the top-most segment of an mstate, each segment record
1036   is kept at the tail of its segment. Segments are added by pushing
1037   segment records onto the list headed by &mstate.seg for the
1038   containing mstate.
1039
1040   Segment flags control allocation/merge/deallocation policies:
1041   * If EXTERN_BIT set, then we did not allocate this segment,
1042     and so should not try to deallocate or merge with others.
1043     (This currently holds only for the initial segment passed
1044     into create_mspace_with_base.)
1045   * If USE_MMAP_BIT set, the segment may be merged with
1046     other surrounding mmapped segments and trimmed/de-allocated
1047     using munmap.
1048   * If neither bit is set, then the segment was obtained using
1049     MORECORE so can be merged with surrounding MORECORE'd segments
1050     and deallocated/trimmed using MORECORE with negative arguments.
1051 */
1052
1053 struct malloc_segment {
1054   char*        base;             /* base address */
1055   size_t       size;             /* allocated size */
1056   struct malloc_segment* next;   /* ptr to next segment */
1057   flag_t       sflags;           /* mmap and extern flag */
1058 };
1059
1060 #define is_mmapped_segment(S)  ((S)->sflags & USE_MMAP_BIT)
1061 #define is_extern_segment(S)   ((S)->sflags & EXTERN_BIT)
1062
1063 typedef struct malloc_segment  msegment;
1064 typedef struct malloc_segment* msegmentptr;
1065
1066 /* ---------------------------- malloc_state ----------------------------- */
1067
1068 /*
1069    A malloc_state holds all of the bookkeeping for a space.
1070    The main fields are:
1071
1072   Top
1073     The topmost chunk of the currently active segment. Its size is
1074     cached in topsize.  The actual size of topmost space is
1075     topsize+TOP_FOOT_SIZE, which includes space reserved for adding
1076     fenceposts and segment records if necessary when getting more
1077     space from the system.  The size at which to autotrim top is
1078     cached from mparams in trim_check, except that it is disabled if
1079     an autotrim fails.
1080
1081   Designated victim (dv)
1082     This is the preferred chunk for servicing small requests that
1083     don't have exact fits.  It is normally the chunk split off most
1084     recently to service another small request.  Its size is cached in
1085     dvsize. The link fields of this chunk are not maintained since it
1086     is not kept in a bin.
1087
1088   SmallBins
1089     An array of bin headers for free chunks.  These bins hold chunks
1090     with sizes less than MIN_LARGE_SIZE bytes. Each bin contains
1091     chunks of all the same size, spaced 8 bytes apart.  To simplify
1092     use in double-linked lists, each bin header acts as a malloc_chunk
1093     pointing to the real first node, if it exists (else pointing to
1094     itself).  This avoids special-casing for headers.  But to avoid
1095     waste, we allocate only the fd/bk pointers of bins, and then use
1096     repositioning tricks to treat these as the fields of a chunk.
1097
1098   TreeBins
1099     Treebins are pointers to the roots of trees holding a range of
1100     sizes. There are 2 equally spaced treebins for each power of two
1101     from TREE_SHIFT to TREE_SHIFT+16. The last bin holds anything
1102     larger.
1103
1104   Bin maps
1105     There is one bit map for small bins ("smallmap") and one for
1106     treebins ("treemap).  Each bin sets its bit when non-empty, and
1107     clears the bit when empty.  Bit operations are then used to avoid
1108     bin-by-bin searching -- nearly all "search" is done without ever
1109     looking at bins that won't be selected.  The bit maps
1110     conservatively use 32 bits per map word, even if on 64bit system.
1111     For a good description of some of the bit-based techniques used
1112     here, see Henry S. Warren Jr's book "Hacker's Delight" (and
1113     supplement at http://hackersdelight.org/). Many of these are
1114     intended to reduce the branchiness of paths through malloc etc, as
1115     well as to reduce the number of memory locations read or written.
1116
1117   Segments
1118     A list of segments headed by an embedded malloc_segment record
1119     representing the initial space.
1120
1121   Address check support
1122     The least_addr field is the least address ever obtained from
1123     MORECORE or MMAP. Attempted frees and reallocs of any address less
1124     than this are trapped (unless INSECURE is defined).
1125
1126   Magic tag
1127     A cross-check field that should always hold same value as mparams.magic.
1128
1129   Max allowed footprint
1130     The maximum allowed bytes to allocate from system (zero means no limit)
1131
1132   Flags
1133     Bits recording whether to use MMAP, locks, or contiguous MORECORE
1134
1135   Statistics
1136     Each space keeps track of current and maximum system memory
1137     obtained via MORECORE or MMAP.
1138
1139   Trim support
1140     Fields holding the amount of unused topmost memory that should trigger
1141     trimming, and a counter to force periodic scanning to release unused
1142     non-topmost segments.
1143
1144   Locking
1145     If USE_LOCKS is defined, the "mutex" lock is acquired and released
1146     around every public call using this mspace.
1147
1148   Extension support
1149     A void* pointer and a size_t field that can be used to help implement
1150     extensions to this malloc.
1151 */
1152
1153 /* Bin types, widths and sizes */
1154 #define NSMALLBINS        (32U)
1155 #define NTREEBINS         (32U)
1156 #define SMALLBIN_SHIFT    (3U)
1157 #define SMALLBIN_WIDTH    (SIZE_T_ONE << SMALLBIN_SHIFT)
1158 #define TREEBIN_SHIFT     (8U)
1159 #define MIN_LARGE_SIZE    (SIZE_T_ONE << TREEBIN_SHIFT)
1160 #define MAX_SMALL_SIZE    (MIN_LARGE_SIZE - SIZE_T_ONE)
1161 #define MAX_SMALL_REQUEST (MAX_SMALL_SIZE - CHUNK_ALIGN_MASK - CHUNK_OVERHEAD)
1162
1163 struct malloc_state {
1164   binmap_t   smallmap;
1165   binmap_t   treemap;
1166   size_t     dvsize;
1167   size_t     topsize;
1168   char*      least_addr;
1169   mchunkptr  dv;
1170   mchunkptr  top;
1171   size_t     trim_check;
1172   size_t     release_checks;
1173   size_t     magic;
1174   mchunkptr  smallbins[(NSMALLBINS+1)*2];
1175   tbinptr    treebins[NTREEBINS];
1176   size_t     footprint;
1177   size_t     max_footprint;
1178   size_t     footprint_limit; /* zero means no limit */
1179   flag_t     mflags;
1180 #if USE_LOCKS
1181   MLOCK_T    mutex;     /* locate lock among fields that rarely change */
1182 #endif /* USE_LOCKS */
1183   msegment   seg;
1184   void*      extp;      /* Unused but available for extensions */
1185   size_t     exts;
1186 };
1187
1188 typedef struct malloc_state*    mstate;
1189
1190 /* ------------- Global malloc_state and malloc_params ------------------- */
1191
1192 /*
1193   malloc_params holds global properties, including those that can be
1194   dynamically set using mallopt. There is a single instance, mparams,
1195   initialized in init_mparams. Note that the non-zeroness of "magic"
1196   also serves as an initialization flag.
1197 */
1198
1199 struct malloc_params {
1200   size_t magic;
1201   size_t page_size;
1202   size_t granularity;
1203   size_t mmap_threshold;
1204   size_t trim_threshold;
1205   flag_t default_mflags;
1206 };
1207
1208 static struct malloc_params mparams;
1209
1210 /* Ensure mparams initialized */
1211 #define ensure_initialization() (void)(mparams.magic != 0 || init_mparams())
1212
1213 #if !ONLY_MSPACES
1214
1215 /* The global malloc_state used for all non-"mspace" calls */
1216 static struct malloc_state _gm_;
1217 #define gm                 (&_gm_)
1218 #define is_global(M)       ((M) == &_gm_)
1219
1220 #endif /* !ONLY_MSPACES */
1221
1222 #define is_initialized(M)  ((M)->top != 0)
1223
1224 /* -------------------------- system alloc setup ------------------------- */
1225
1226 /* Operations on mflags */
1227
1228 #define use_lock(M)           ((M)->mflags &   USE_LOCK_BIT)
1229 #define enable_lock(M)        ((M)->mflags |=  USE_LOCK_BIT)
1230 #if USE_LOCKS
1231 #define disable_lock(M)       ((M)->mflags &= ~USE_LOCK_BIT)
1232 #else
1233 #define disable_lock(M)
1234 #endif
1235
1236 #define use_mmap(M)           ((M)->mflags &   USE_MMAP_BIT)
1237 #define enable_mmap(M)        ((M)->mflags |=  USE_MMAP_BIT)
1238 #if HAVE_MMAP
1239 #define disable_mmap(M)       ((M)->mflags &= ~USE_MMAP_BIT)
1240 #else
1241 #define disable_mmap(M)
1242 #endif
1243
1244 #define use_noncontiguous(M)  ((M)->mflags &   USE_NONCONTIGUOUS_BIT)
1245 #define disable_contiguous(M) ((M)->mflags |=  USE_NONCONTIGUOUS_BIT)
1246 #define use_noexpand(M) ((M)->mflags & USE_NOEXPAND_BIT)
1247 #define disable_expand(M) ((M)->mflags |= USE_NOEXPAND_BIT)
1248 #define use_trace(M) ((M)->mflags & USE_TRACE_BIT)
1249 #define enable_trace(M) ((M)->mflags |= USE_TRACE_BIT)
1250 #define disable_trace(M) ((M)->mflags |= USE_TRACE_BIT)
1251
1252 #define set_lock(M,L)\
1253  ((M)->mflags = (L)?\
1254   ((M)->mflags | USE_LOCK_BIT) :\
1255   ((M)->mflags & ~USE_LOCK_BIT))
1256
1257 /* page-align a size */
1258 #define page_align(S)\
1259  (((S) + (mparams.page_size - SIZE_T_ONE)) & ~(mparams.page_size - SIZE_T_ONE))
1260
1261 /* granularity-align a size */
1262 #define granularity_align(S)\
1263   (((S) + (mparams.granularity - SIZE_T_ONE))\
1264    & ~(mparams.granularity - SIZE_T_ONE))
1265
1266
1267 /* For mmap, use granularity alignment on windows, else page-align */
1268 #ifdef WIN32
1269 #define mmap_align(S) granularity_align(S)
1270 #else
1271 #define mmap_align(S) page_align(S)
1272 #endif
1273
1274 /* For sys_alloc, enough padding to ensure can malloc request on success */
1275 #define SYS_ALLOC_PADDING (TOP_FOOT_SIZE + MALLOC_ALIGNMENT)
1276
1277 #define is_page_aligned(S)\
1278    (((size_t)(S) & (mparams.page_size - SIZE_T_ONE)) == 0)
1279 #define is_granularity_aligned(S)\
1280    (((size_t)(S) & (mparams.granularity - SIZE_T_ONE)) == 0)
1281
1282 /*  True if segment S holds address A */
1283 #define segment_holds(S, A)\
1284   ((char*)(A) >= S->base && (char*)(A) < S->base + S->size)
1285
1286 /* Return segment holding given address */
1287 static msegmentptr segment_holding(mstate m, char* addr) {
1288   msegmentptr sp = &m->seg;
1289   for (;;) {
1290     if (addr >= sp->base && addr < sp->base + sp->size)
1291       return sp;
1292     if ((sp = sp->next) == 0)
1293       return 0;
1294   }
1295 }
1296
1297 /* Return true if segment contains a segment link */
1298 static int has_segment_link(mstate m, msegmentptr ss) {
1299   msegmentptr sp = &m->seg;
1300   for (;;) {
1301     if ((char*)sp >= ss->base && (char*)sp < ss->base + ss->size)
1302       return 1;
1303     if ((sp = sp->next) == 0)
1304       return 0;
1305   }
1306 }
1307
1308 #ifndef MORECORE_CANNOT_TRIM
1309 #define should_trim(M,s)  ((s) > (M)->trim_check)
1310 #else  /* MORECORE_CANNOT_TRIM */
1311 #define should_trim(M,s)  (0)
1312 #endif /* MORECORE_CANNOT_TRIM */
1313
1314 /*
1315   TOP_FOOT_SIZE is padding at the end of a segment, including space
1316   that may be needed to place segment records and fenceposts when new
1317   noncontiguous segments are added.
1318 */
1319 #define TOP_FOOT_SIZE\
1320   (align_offset(chunk2mem(0))+pad_request(sizeof(struct malloc_segment))+MIN_CHUNK_SIZE)
1321
1322
1323 /* -------------------------------  Hooks -------------------------------- */
1324
1325 /*
1326   PREACTION should be defined to return 0 on success, and nonzero on
1327   failure. If you are not using locking, you can redefine these to do
1328   anything you like.
1329 */
1330
1331 #if USE_LOCKS
1332 #define PREACTION(M)  ((use_lock(M))? ACQUIRE_LOCK(&(M)->mutex) : 0)
1333 #define POSTACTION(M) { if (use_lock(M)) RELEASE_LOCK(&(M)->mutex); }
1334 #else /* USE_LOCKS */
1335
1336 #ifndef PREACTION
1337 #define PREACTION(M) (0)
1338 #endif  /* PREACTION */
1339
1340 #ifndef POSTACTION
1341 #define POSTACTION(M)
1342 #endif  /* POSTACTION */
1343
1344 #endif /* USE_LOCKS */
1345
1346 /*
1347   CORRUPTION_ERROR_ACTION is triggered upon detected bad addresses.
1348   USAGE_ERROR_ACTION is triggered on detected bad frees and
1349   reallocs. The argument p is an address that might have triggered the
1350   fault. It is ignored by the two predefined actions, but might be
1351   useful in custom actions that try to help diagnose errors.
1352 */
1353
1354 #if PROCEED_ON_ERROR
1355
1356 /* A count of the number of corruption errors causing resets */
1357 int malloc_corruption_error_count;
1358
1359 /* default corruption action */
1360 static void reset_on_error(mstate m);
1361
1362 #define CORRUPTION_ERROR_ACTION(m)  reset_on_error(m)
1363 #define USAGE_ERROR_ACTION(m, p)
1364
1365 #else /* PROCEED_ON_ERROR */
1366
1367 #ifndef CORRUPTION_ERROR_ACTION
1368 #define CORRUPTION_ERROR_ACTION(m) DLM_ABORT
1369 #endif /* CORRUPTION_ERROR_ACTION */
1370
1371 #ifndef USAGE_ERROR_ACTION
1372 #define USAGE_ERROR_ACTION(m,p) DLM_ABORT
1373 #endif /* USAGE_ERROR_ACTION */
1374
1375 #endif /* PROCEED_ON_ERROR */
1376
1377
1378 /* -------------------------- Debugging setup ---------------------------- */
1379
1380 #if ! DEBUG
1381
1382 #define check_free_chunk(M,P)
1383 #define check_inuse_chunk(M,P)
1384 #define check_malloced_chunk(M,P,N)
1385 #define check_mmapped_chunk(M,P)
1386 #define check_malloc_state(M)
1387 #define check_top_chunk(M,P)
1388
1389 #else /* DEBUG */
1390 #define check_free_chunk(M,P)       do_check_free_chunk(M,P)
1391 #define check_inuse_chunk(M,P)      do_check_inuse_chunk(M,P)
1392 #define check_top_chunk(M,P)        do_check_top_chunk(M,P)
1393 #define check_malloced_chunk(M,P,N) do_check_malloced_chunk(M,P,N)
1394 #define check_mmapped_chunk(M,P)    do_check_mmapped_chunk(M,P)
1395 #define check_malloc_state(M)       do_check_malloc_state(M)
1396
1397 static void   do_check_any_chunk(mstate m, mchunkptr p);
1398 static void   do_check_top_chunk(mstate m, mchunkptr p);
1399 static void   do_check_mmapped_chunk(mstate m, mchunkptr p);
1400 static void   do_check_inuse_chunk(mstate m, mchunkptr p);
1401 static void   do_check_free_chunk(mstate m, mchunkptr p);
1402 static void   do_check_malloced_chunk(mstate m, void* mem, size_t s);
1403 static void   do_check_tree(mstate m, tchunkptr t);
1404 static void   do_check_treebin(mstate m, bindex_t i);
1405 static void   do_check_smallbin(mstate m, bindex_t i);
1406 static void   do_check_malloc_state(mstate m);
1407 static int    bin_find(mstate m, mchunkptr x);
1408 static size_t traverse_and_check(mstate m);
1409 #endif /* DEBUG */
1410
1411 /* ---------------------------- Indexing Bins ---------------------------- */
1412
1413 #define is_small(s)         (((s) >> SMALLBIN_SHIFT) < NSMALLBINS)
1414 #define small_index(s)      (bindex_t)((s)  >> SMALLBIN_SHIFT)
1415 #define small_index2size(i) ((i)  << SMALLBIN_SHIFT)
1416 #define MIN_SMALL_INDEX     (small_index(MIN_CHUNK_SIZE))
1417
1418 /* addressing by index. See above about smallbin repositioning */
1419 #define smallbin_at(M, i)   ((sbinptr)((char*)&((M)->smallbins[(i)<<1])))
1420 #define treebin_at(M,i)     (&((M)->treebins[i]))
1421
1422 /* assign tree index for size S to variable I. Use x86 asm if possible  */
1423 #if defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__))
1424 #define compute_tree_index(S, I)\
1425 {\
1426   unsigned int X = S >> TREEBIN_SHIFT;\
1427   if (X == 0)\
1428     I = 0;\
1429   else if (X > 0xFFFF)\
1430     I = NTREEBINS-1;\
1431   else {\
1432     unsigned int K = (unsigned) sizeof(X)*__CHAR_BIT__ - 1 - (unsigned) __builtin_clz(X); \
1433     I =  (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
1434   }\
1435 }
1436
1437 #elif defined (__INTEL_COMPILER)
1438 #define compute_tree_index(S, I)\
1439 {\
1440   size_t X = S >> TREEBIN_SHIFT;\
1441   if (X == 0)\
1442     I = 0;\
1443   else if (X > 0xFFFF)\
1444     I = NTREEBINS-1;\
1445   else {\
1446     unsigned int K = _bit_scan_reverse (X); \
1447     I =  (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
1448   }\
1449 }
1450
1451 #elif defined(_MSC_VER) && _MSC_VER>=1300
1452 #define compute_tree_index(S, I)\
1453 {\
1454   size_t X = S >> TREEBIN_SHIFT;\
1455   if (X == 0)\
1456     I = 0;\
1457   else if (X > 0xFFFF)\
1458     I = NTREEBINS-1;\
1459   else {\
1460     unsigned int K;\
1461     _BitScanReverse((DWORD *) &K, (DWORD) X);\
1462     I =  (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
1463   }\
1464 }
1465
1466 #else /* GNUC */
1467 #define compute_tree_index(S, I)\
1468 {\
1469   size_t X = S >> TREEBIN_SHIFT;\
1470   if (X == 0)\
1471     I = 0;\
1472   else if (X > 0xFFFF)\
1473     I = NTREEBINS-1;\
1474   else {\
1475     unsigned int Y = (unsigned int)X;\
1476     unsigned int N = ((Y - 0x100) >> 16) & 8;\
1477     unsigned int K = (((Y <<= N) - 0x1000) >> 16) & 4;\
1478     N += K;\
1479     N += K = (((Y <<= K) - 0x4000) >> 16) & 2;\
1480     K = 14 - N + ((Y <<= K) >> 15);\
1481     I = (K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1));\
1482   }\
1483 }
1484 #endif /* GNUC */
1485
1486 /* Bit representing maximum resolved size in a treebin at i */
1487 #define bit_for_tree_index(i) \
1488    (i == NTREEBINS-1)? (SIZE_T_BITSIZE-1) : (((i) >> 1) + TREEBIN_SHIFT - 2)
1489
1490 /* Shift placing maximum resolved bit in a treebin at i as sign bit */
1491 #define leftshift_for_tree_index(i) \
1492    ((i == NTREEBINS-1)? 0 : \
1493     ((SIZE_T_BITSIZE-SIZE_T_ONE) - (((i) >> 1) + TREEBIN_SHIFT - 2)))
1494
1495 /* The size of the smallest chunk held in bin with index i */
1496 #define minsize_for_tree_index(i) \
1497    ((SIZE_T_ONE << (((i) >> 1) + TREEBIN_SHIFT)) |  \
1498    (((size_t)((i) & SIZE_T_ONE)) << (((i) >> 1) + TREEBIN_SHIFT - 1)))
1499
1500
1501 /* ------------------------ Operations on bin maps ----------------------- */
1502
1503 /* bit corresponding to given index */
1504 #define idx2bit(i)              ((binmap_t)(1) << (i))
1505
1506 /* Mark/Clear bits with given index */
1507 #define mark_smallmap(M,i)      ((M)->smallmap |=  idx2bit(i))
1508 #define clear_smallmap(M,i)     ((M)->smallmap &= ~idx2bit(i))
1509 #define smallmap_is_marked(M,i) ((M)->smallmap &   idx2bit(i))
1510
1511 #define mark_treemap(M,i)       ((M)->treemap  |=  idx2bit(i))
1512 #define clear_treemap(M,i)      ((M)->treemap  &= ~idx2bit(i))
1513 #define treemap_is_marked(M,i)  ((M)->treemap  &   idx2bit(i))
1514
1515 /* isolate the least set bit of a bitmap */
1516 #define least_bit(x)         ((x) & -(x))
1517
1518 /* mask with all bits to left of least bit of x on */
1519 #define left_bits(x)         ((x<<1) | -(x<<1))
1520
1521 /* mask with all bits to left of or equal to least bit of x on */
1522 #define same_or_left_bits(x) ((x) | -(x))
1523
1524 /* index corresponding to given bit. Use x86 asm if possible */
1525
1526 #if defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__))
1527 #define compute_bit2idx(X, I)\
1528 {\
1529   unsigned int J;\
1530   J = __builtin_ctz(X); \
1531   I = (bindex_t)J;\
1532 }
1533
1534 #elif defined (__INTEL_COMPILER)
1535 #define compute_bit2idx(X, I)\
1536 {\
1537   unsigned int J;\
1538   J = _bit_scan_forward (X); \
1539   I = (bindex_t)J;\
1540 }
1541
1542 #elif defined(_MSC_VER) && _MSC_VER>=1300
1543 #define compute_bit2idx(X, I)\
1544 {\
1545   unsigned int J;\
1546   _BitScanForward((DWORD *) &J, X);\
1547   I = (bindex_t)J;\
1548 }
1549
1550 #elif USE_BUILTIN_FFS
1551 #define compute_bit2idx(X, I) I = ffs(X)-1
1552
1553 #else
1554 #define compute_bit2idx(X, I)\
1555 {\
1556   unsigned int Y = X - 1;\
1557   unsigned int K = Y >> (16-4) & 16;\
1558   unsigned int N = K;        Y >>= K;\
1559   N += K = Y >> (8-3) &  8;  Y >>= K;\
1560   N += K = Y >> (4-2) &  4;  Y >>= K;\
1561   N += K = Y >> (2-1) &  2;  Y >>= K;\
1562   N += K = Y >> (1-0) &  1;  Y >>= K;\
1563   I = (bindex_t)(N + Y);\
1564 }
1565 #endif /* GNUC */
1566
1567
1568 /* ----------------------- Runtime Check Support ------------------------- */
1569
1570 /*
1571   For security, the main invariant is that malloc/free/etc never
1572   writes to a static address other than malloc_state, unless static
1573   malloc_state itself has been corrupted, which cannot occur via
1574   malloc (because of these checks). In essence this means that we
1575   believe all pointers, sizes, maps etc held in malloc_state, but
1576   check all of those linked or offsetted from other embedded data
1577   structures.  These checks are interspersed with main code in a way
1578   that tends to minimize their run-time cost.
1579
1580   When FOOTERS is defined, in addition to range checking, we also
1581   verify footer fields of inuse chunks, which can be used guarantee
1582   that the mstate controlling malloc/free is intact.  This is a
1583   streamlined version of the approach described by William Robertson
1584   et al in "Run-time Detection of Heap-based Overflows" LISA'03
1585   http://www.usenix.org/events/lisa03/tech/robertson.html The footer
1586   of an inuse chunk holds the xor of its mstate and a random seed,
1587   that is checked upon calls to free() and realloc().  This is
1588   (probabalistically) unguessable from outside the program, but can be
1589   computed by any code successfully malloc'ing any chunk, so does not
1590   itself provide protection against code that has already broken
1591   security through some other means.  Unlike Robertson et al, we
1592   always dynamically check addresses of all offset chunks (previous,
1593   next, etc). This turns out to be cheaper than relying on hashes.
1594 */
1595
1596 #if !INSECURE
1597 /* Check if address a is at least as high as any from MORECORE or MMAP */
1598 #define ok_address(M, a) ((char*)(a) >= (M)->least_addr)
1599 /* Check if address of next chunk n is higher than base chunk p */
1600 #define ok_next(p, n)    ((char*)(p) < (char*)(n))
1601 /* Check if p has inuse status */
1602 #define ok_inuse(p)     is_inuse(p)
1603 /* Check if p has its pinuse bit on */
1604 #define ok_pinuse(p)     pinuse(p)
1605
1606 #else /* !INSECURE */
1607 #define ok_address(M, a) (1)
1608 #define ok_next(b, n)    (1)
1609 #define ok_inuse(p)      (1)
1610 #define ok_pinuse(p)     (1)
1611 #endif /* !INSECURE */
1612
1613 #if (FOOTERS && !INSECURE)
1614 /* Check if (alleged) mstate m has expected magic field */
1615 #define ok_magic(M)      ((M)->magic == mparams.magic)
1616 #else  /* (FOOTERS && !INSECURE) */
1617 #define ok_magic(M)      (1)
1618 #endif /* (FOOTERS && !INSECURE) */
1619
1620 /* In gcc, use __builtin_expect to minimize impact of checks */
1621 #if !INSECURE
1622 #if defined(__GNUC__) && __GNUC__ >= 3
1623 #define RTCHECK(e)  __builtin_expect(e, 1)
1624 #else /* GNUC */
1625 #define RTCHECK(e)  (e)
1626 #endif /* GNUC */
1627 #else /* !INSECURE */
1628 #define RTCHECK(e)  (1)
1629 #endif /* !INSECURE */
1630
1631 /* macros to set up inuse chunks with or without footers */
1632
1633 #if !FOOTERS
1634
1635 #define mark_inuse_foot(M,p,s)
1636
1637 /* Macros for setting head/foot of non-mmapped chunks */
1638
1639 /* Set cinuse bit and pinuse bit of next chunk */
1640 #define set_inuse(M,p,s)\
1641   ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
1642   ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
1643
1644 /* Set cinuse and pinuse of this chunk and pinuse of next chunk */
1645 #define set_inuse_and_pinuse(M,p,s)\
1646   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
1647   ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
1648
1649 /* Set size, cinuse and pinuse bit of this chunk */
1650 #define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
1651   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT))
1652
1653 #else /* FOOTERS */
1654
1655 /* Set foot of inuse chunk to be xor of mstate and seed */
1656 #define mark_inuse_foot(M,p,s)\
1657   (((mchunkptr)((char*)(p) + (s)))->prev_foot = ((size_t)(M) ^ mparams.magic))
1658
1659 #define get_mstate_for(p)\
1660   ((mstate)(((mchunkptr)((char*)(p) +\
1661     (chunksize(p))))->prev_foot ^ mparams.magic))
1662
1663 #define set_inuse(M,p,s)\
1664   ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
1665   (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT), \
1666   mark_inuse_foot(M,p,s))
1667
1668 #define set_inuse_and_pinuse(M,p,s)\
1669   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
1670   (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT),\
1671  mark_inuse_foot(M,p,s))
1672
1673 #define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
1674   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
1675   mark_inuse_foot(M, p, s))
1676
1677 #endif /* !FOOTERS */
1678
1679 /* ---------------------------- setting mparams -------------------------- */
1680
1681 #if LOCK_AT_FORK
1682 static void pre_fork(void)         { ACQUIRE_LOCK(&(gm)->mutex); }
1683 static void post_fork_parent(void) { RELEASE_LOCK(&(gm)->mutex); }
1684 static void post_fork_child(void)  { INITIAL_LOCK(&(gm)->mutex); }
1685 #endif /* LOCK_AT_FORK */
1686
1687 /* Initialize mparams */
1688 static int init_mparams(void) {
1689 #ifdef NEED_GLOBAL_LOCK_INIT
1690   if (malloc_global_mutex_status <= 0)
1691     init_malloc_global_mutex();
1692 #endif
1693
1694   ACQUIRE_MALLOC_GLOBAL_LOCK();
1695   if (mparams.magic == 0) {
1696     size_t magic;
1697     size_t psize;
1698     size_t gsize;
1699
1700 #ifndef WIN32
1701     psize = malloc_getpagesize;
1702     gsize = ((DEFAULT_GRANULARITY != 0)? DEFAULT_GRANULARITY : psize);
1703 #else /* WIN32 */
1704     {
1705       SYSTEM_INFO system_info;
1706       GetSystemInfo(&system_info);
1707       psize = system_info.dwPageSize;
1708       gsize = ((DEFAULT_GRANULARITY != 0)?
1709                DEFAULT_GRANULARITY : system_info.dwAllocationGranularity);
1710     }
1711 #endif /* WIN32 */
1712
1713     /* Sanity-check configuration:
1714        size_t must be unsigned and as wide as pointer type.
1715        ints must be at least 4 bytes.
1716        alignment must be at least 8.
1717        Alignment, min chunk size, and page size must all be powers of 2.
1718     */
1719     if ((sizeof(size_t) != sizeof(char*)) ||
1720         (MAX_SIZE_T < MIN_CHUNK_SIZE)  ||
1721         (sizeof(int) < 4)  ||
1722         (MALLOC_ALIGNMENT < (size_t)8U) ||
1723         ((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT-SIZE_T_ONE)) != 0) ||
1724         ((MCHUNK_SIZE      & (MCHUNK_SIZE-SIZE_T_ONE))      != 0) ||
1725         ((gsize            & (gsize-SIZE_T_ONE))            != 0) ||
1726         ((psize            & (psize-SIZE_T_ONE))            != 0))
1727       DLM_ABORT;
1728     mparams.granularity = gsize;
1729     mparams.page_size = psize;
1730     mparams.mmap_threshold = DEFAULT_MMAP_THRESHOLD;
1731     mparams.trim_threshold = DEFAULT_TRIM_THRESHOLD;
1732 #if MORECORE_CONTIGUOUS
1733     mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT;
1734 #else  /* MORECORE_CONTIGUOUS */
1735     mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT|USE_NONCONTIGUOUS_BIT;
1736 #endif /* MORECORE_CONTIGUOUS */
1737
1738 #if !ONLY_MSPACES
1739     /* Set up lock for main malloc area */
1740     gm->mflags = mparams.default_mflags;
1741     (void)INITIAL_LOCK(&gm->mutex);
1742 #endif
1743 #if LOCK_AT_FORK
1744     pthread_atfork(&pre_fork, &post_fork_parent, &post_fork_child);
1745 #endif
1746
1747     {
1748 #ifndef DLM_MAGIC_CONSTANT
1749 #if USE_DEV_RANDOM
1750       int fd;
1751       unsigned char buf[sizeof(size_t)];
1752       /* Try to use /dev/urandom, else fall back on using time */
1753       if ((fd = open("/dev/urandom", O_RDONLY)) >= 0 &&
1754           read(fd, buf, sizeof(buf)) == sizeof(buf)) {
1755         magic = *((size_t *) buf);
1756         close(fd);
1757       }
1758       else
1759 #endif /* USE_DEV_RANDOM */
1760 #ifdef WIN32
1761       magic = (size_t)(GetTickCount() ^ (size_t)0x55555555U);
1762 #elif defined(LACKS_TIME_H)
1763       magic = (size_t)&magic ^ (size_t)0x55555555U;
1764 #else
1765       magic = (size_t)(time(0) ^ (size_t)0x55555555U);
1766 #endif
1767       magic |= (size_t)8U;    /* ensure nonzero */
1768       magic &= ~(size_t)7U;   /* improve chances of fault for bad values */
1769 #else
1770       magic = DLM_MAGIC_CONSTANT;
1771 #endif
1772       /* Until memory modes commonly available, use volatile-write */
1773       (*(volatile size_t *)(&(mparams.magic))) = magic;
1774     }
1775   }
1776
1777   RELEASE_MALLOC_GLOBAL_LOCK();
1778   return 1;
1779 }
1780
1781 /* support for mallopt */
1782 static int change_mparam(int param_number, int value) {
1783   size_t val;
1784   ensure_initialization();
1785   val = (value == -1)? MAX_SIZE_T : (size_t)value;
1786   switch(param_number) {
1787   case M_TRIM_THRESHOLD:
1788     mparams.trim_threshold = val;
1789     return 1;
1790   case M_GRANULARITY:
1791     if (val >= mparams.page_size && ((val & (val-1)) == 0)) {
1792       mparams.granularity = val;
1793       return 1;
1794     }
1795     else
1796       return 0;
1797   case M_MMAP_THRESHOLD:
1798     mparams.mmap_threshold = val;
1799     return 1;
1800   default:
1801     return 0;
1802   }
1803 }
1804
1805 #if DEBUG
1806 /* ------------------------- Debugging Support --------------------------- */
1807
1808 /* Check properties of any chunk, whether free, inuse, mmapped etc  */
1809 static void do_check_any_chunk(mstate m, mchunkptr p) {
1810   assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
1811   assert(ok_address(m, p));
1812 }
1813
1814 /* Check properties of top chunk */
1815 static void do_check_top_chunk(mstate m, mchunkptr p) {
1816   msegmentptr sp = segment_holding(m, (char*)p);
1817   size_t  sz = p->head & ~INUSE_BITS; /* third-lowest bit can be set! */
1818   assert(sp != 0);
1819   assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
1820   assert(ok_address(m, p));
1821   assert(sz == m->topsize);
1822   assert(sz > 0);
1823   assert(sz == ((sp->base + sp->size) - (char*)p) - TOP_FOOT_SIZE);
1824   assert(pinuse(p));
1825   assert(!pinuse(chunk_plus_offset(p, sz)));
1826 }
1827
1828 /* Check properties of (inuse) mmapped chunks */
1829 static void do_check_mmapped_chunk(mstate m, mchunkptr p) {
1830   size_t  sz = chunksize(p);
1831   size_t len = (sz + (p->prev_foot) + MMAP_FOOT_PAD);
1832   assert(is_mmapped(p));
1833   assert(use_mmap(m));
1834   assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
1835   assert(ok_address(m, p));
1836   assert(!is_small(sz));
1837   assert((len & (mparams.page_size-SIZE_T_ONE)) == 0);
1838   assert(chunk_plus_offset(p, sz)->head == FENCEPOST_HEAD);
1839   assert(chunk_plus_offset(p, sz+SIZE_T_SIZE)->head == 0);
1840 }
1841
1842 /* Check properties of inuse chunks */
1843 static void do_check_inuse_chunk(mstate m, mchunkptr p) {
1844   do_check_any_chunk(m, p);
1845   assert(is_inuse(p));
1846   assert(next_pinuse(p));
1847   /* If not pinuse and not mmapped, previous chunk has OK offset */
1848   assert(is_mmapped(p) || pinuse(p) || next_chunk(prev_chunk(p)) == p);
1849   if (is_mmapped(p))
1850     do_check_mmapped_chunk(m, p);
1851 }
1852
1853 /* Check properties of free chunks */
1854 static void do_check_free_chunk(mstate m, mchunkptr p) {
1855   size_t sz = chunksize(p);
1856   mchunkptr next = chunk_plus_offset(p, sz);
1857   do_check_any_chunk(m, p);
1858   assert(!is_inuse(p));
1859   assert(!next_pinuse(p));
1860   assert (!is_mmapped(p));
1861   if (p != m->dv && p != m->top) {
1862     if (sz >= MIN_CHUNK_SIZE) {
1863       assert((sz & CHUNK_ALIGN_MASK) == 0);
1864       assert(is_aligned(chunk2mem(p)));
1865       assert(next->prev_foot == sz);
1866       assert(pinuse(p));
1867       assert (next == m->top || is_inuse(next));
1868       assert(p->fd->bk == p);
1869       assert(p->bk->fd == p);
1870     }
1871     else  /* markers are always of size SIZE_T_SIZE */
1872       assert(sz == SIZE_T_SIZE);
1873   }
1874 }
1875
1876 /* Check properties of malloced chunks at the point they are malloced */
1877 static void do_check_malloced_chunk(mstate m, void* mem, size_t s) {
1878   if (mem != 0) {
1879     mchunkptr p = mem2chunk(mem);
1880     size_t sz = p->head & ~INUSE_BITS;
1881     do_check_inuse_chunk(m, p);
1882     assert((sz & CHUNK_ALIGN_MASK) == 0);
1883     assert(sz >= MIN_CHUNK_SIZE);
1884     assert(sz >= s);
1885     /* unless mmapped, size is less than MIN_CHUNK_SIZE more than request */
1886     assert(is_mmapped(p) || sz < (s + MIN_CHUNK_SIZE));
1887   }
1888 }
1889
1890 /* Check a tree and its subtrees.  */
1891 static void do_check_tree(mstate m, tchunkptr t) {
1892   tchunkptr head = 0;
1893   tchunkptr u = t;
1894   bindex_t tindex = t->index;
1895   size_t tsize = chunksize(t);
1896   bindex_t idx;
1897   compute_tree_index(tsize, idx);
1898   assert(tindex == idx);
1899   assert(tsize >= MIN_LARGE_SIZE);
1900   assert(tsize >= minsize_for_tree_index(idx));
1901   assert((idx == NTREEBINS-1) || (tsize < minsize_for_tree_index((idx+1))));
1902
1903   do { /* traverse through chain of same-sized nodes */
1904     do_check_any_chunk(m, ((mchunkptr)u));
1905     assert(u->index == tindex);
1906     assert(chunksize(u) == tsize);
1907     assert(!is_inuse(u));
1908     assert(!next_pinuse(u));
1909     assert(u->fd->bk == u);
1910     assert(u->bk->fd == u);
1911     if (u->parent == 0) {
1912       assert(u->child[0] == 0);
1913       assert(u->child[1] == 0);
1914     }
1915     else {
1916       assert(head == 0); /* only one node on chain has parent */
1917       head = u;
1918       assert(u->parent != u);
1919       assert (u->parent->child[0] == u ||
1920               u->parent->child[1] == u ||
1921               *((tbinptr*)(u->parent)) == u);
1922       if (u->child[0] != 0) {
1923         assert(u->child[0]->parent == u);
1924         assert(u->child[0] != u);
1925         do_check_tree(m, u->child[0]);
1926       }
1927       if (u->child[1] != 0) {
1928         assert(u->child[1]->parent == u);
1929         assert(u->child[1] != u);
1930         do_check_tree(m, u->child[1]);
1931       }
1932       if (u->child[0] != 0 && u->child[1] != 0) {
1933         assert(chunksize(u->child[0]) < chunksize(u->child[1]));
1934       }
1935     }
1936     u = u->fd;
1937   } while (u != t);
1938   assert(head != 0);
1939 }
1940
1941 /*  Check all the chunks in a treebin.  */
1942 static void do_check_treebin(mstate m, bindex_t i) {
1943   tbinptr* tb = treebin_at(m, i);
1944   tchunkptr t = *tb;
1945   int empty = (m->treemap & (1U << i)) == 0;
1946   if (t == 0)
1947     assert(empty);
1948   if (!empty)
1949     do_check_tree(m, t);
1950 }
1951
1952 /*  Check all the chunks in a smallbin.  */
1953 static void do_check_smallbin(mstate m, bindex_t i) {
1954   sbinptr b = smallbin_at(m, i);
1955   mchunkptr p = b->bk;
1956   unsigned int empty = (m->smallmap & (1U << i)) == 0;
1957   if (p == b)
1958     assert(empty);
1959   if (!empty) {
1960     for (; p != b; p = p->bk) {
1961       size_t size = chunksize(p);
1962       mchunkptr q;
1963       /* each chunk claims to be free */
1964       do_check_free_chunk(m, p);
1965       /* chunk belongs in bin */
1966       assert(small_index(size) == i);
1967       assert(p->bk == b || chunksize(p->bk) == chunksize(p));
1968       /* chunk is followed by an inuse chunk */
1969       q = next_chunk(p);
1970       if (q->head != FENCEPOST_HEAD)
1971         do_check_inuse_chunk(m, q);
1972     }
1973   }
1974 }
1975
1976 /* Find x in a bin. Used in other check functions. */
1977 static int bin_find(mstate m, mchunkptr x) {
1978   size_t size = chunksize(x);
1979   if (is_small(size)) {
1980     bindex_t sidx = small_index(size);
1981     sbinptr b = smallbin_at(m, sidx);
1982     if (smallmap_is_marked(m, sidx)) {
1983       mchunkptr p = b;
1984       do {
1985         if (p == x)
1986           return 1;
1987       } while ((p = p->fd) != b);
1988     }
1989   }
1990   else {
1991     bindex_t tidx;
1992     compute_tree_index(size, tidx);
1993     if (treemap_is_marked(m, tidx)) {
1994       tchunkptr t = *treebin_at(m, tidx);
1995       size_t sizebits = size << leftshift_for_tree_index(tidx);
1996       while (t != 0 && chunksize(t) != size) {
1997         t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
1998         sizebits <<= 1;
1999       }
2000       if (t != 0) {
2001         tchunkptr u = t;
2002         do {
2003           if (u == (tchunkptr)x)
2004             return 1;
2005         } while ((u = u->fd) != t);
2006       }
2007     }
2008   }
2009   return 0;
2010 }
2011
2012 /* Traverse each chunk and check it; return total */
2013 static size_t traverse_and_check(mstate m) {
2014   size_t sum = 0;
2015   if (is_initialized(m)) {
2016     msegmentptr s = &m->seg;
2017     sum += m->topsize + TOP_FOOT_SIZE;
2018     while (s != 0) {
2019       mchunkptr q = align_as_chunk(s->base);
2020       mchunkptr lastq = 0;
2021       assert(pinuse(q));
2022       while (segment_holds(s, q) &&
2023              q != m->top && q->head != FENCEPOST_HEAD) {
2024         sum += chunksize(q);
2025         if (is_inuse(q)) {
2026           assert(!bin_find(m, q));
2027           do_check_inuse_chunk(m, q);
2028         }
2029         else {
2030           assert(q == m->dv || bin_find(m, q));
2031           assert(lastq == 0 || is_inuse(lastq)); /* Not 2 consecutive free */
2032           do_check_free_chunk(m, q);
2033         }
2034         lastq = q;
2035         q = next_chunk(q);
2036       }
2037       s = s->next;
2038     }
2039   }
2040   return sum;
2041 }
2042
2043
2044 /* Check all properties of malloc_state. */
2045 static void do_check_malloc_state(mstate m) {
2046   bindex_t i;
2047   size_t total;
2048   /* check bins */
2049   for (i = 0; i < NSMALLBINS; ++i)
2050     do_check_smallbin(m, i);
2051   for (i = 0; i < NTREEBINS; ++i)
2052     do_check_treebin(m, i);
2053
2054   if (m->dvsize != 0) { /* check dv chunk */
2055     do_check_any_chunk(m, m->dv);
2056     assert(m->dvsize == chunksize(m->dv));
2057     assert(m->dvsize >= MIN_CHUNK_SIZE);
2058     assert(bin_find(m, m->dv) == 0);
2059   }
2060
2061   if (m->top != 0) {   /* check top chunk */
2062     do_check_top_chunk(m, m->top);
2063     /*assert(m->topsize == chunksize(m->top)); redundant */
2064     assert(m->topsize > 0);
2065     assert(bin_find(m, m->top) == 0);
2066   }
2067
2068   total = traverse_and_check(m);
2069   assert(total <= m->footprint);
2070   assert(m->footprint <= m->max_footprint);
2071 }
2072 #endif /* DEBUG */
2073
2074 /* ----------------------------- statistics ------------------------------ */
2075
2076 #if !NO_MALLINFO
2077 static struct mallinfo internal_mallinfo(mstate m) {
2078   struct mallinfo nm = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
2079   ensure_initialization();
2080   if (!PREACTION(m)) {
2081     check_malloc_state(m);
2082     if (is_initialized(m)) {
2083       size_t nfree = SIZE_T_ONE; /* top always free */
2084       size_t mfree = m->topsize + TOP_FOOT_SIZE;
2085       size_t sum = mfree;
2086       msegmentptr s = &m->seg;
2087       while (s != 0) {
2088         mchunkptr q = align_as_chunk(s->base);
2089         while (segment_holds(s, q) &&
2090                q != m->top && q->head != FENCEPOST_HEAD) {
2091           size_t sz = chunksize(q);
2092           sum += sz;
2093           if (!is_inuse(q)) {
2094             mfree += sz;
2095             ++nfree;
2096           }
2097           q = next_chunk(q);
2098         }
2099         s = s->next;
2100       }
2101
2102       nm.arena    = sum;
2103       nm.ordblks  = nfree;
2104       nm.hblkhd   = m->footprint - sum;
2105       nm.usmblks  = m->max_footprint;
2106       nm.uordblks = m->footprint - mfree;
2107       nm.fordblks = mfree;
2108       nm.keepcost = m->topsize;
2109     }
2110
2111     POSTACTION(m);
2112   }
2113   return nm;
2114 }
2115 #endif /* !NO_MALLINFO */
2116
2117 #if !NO_MALLOC_STATS
2118 static void internal_malloc_stats(mstate m) {
2119   ensure_initialization();
2120   if (!PREACTION(m)) {
2121     size_t maxfp = 0;
2122     size_t fp = 0;
2123     size_t used = 0;
2124     check_malloc_state(m);
2125     if (is_initialized(m)) {
2126       msegmentptr s = &m->seg;
2127       maxfp = m->max_footprint;
2128       fp = m->footprint;
2129       used = fp - (m->topsize + TOP_FOOT_SIZE);
2130
2131       while (s != 0) {
2132         mchunkptr q = align_as_chunk(s->base);
2133         while (segment_holds(s, q) &&
2134                q != m->top && q->head != FENCEPOST_HEAD) {
2135           if (!is_inuse(q))
2136             used -= chunksize(q);
2137           q = next_chunk(q);
2138         }
2139         s = s->next;
2140       }
2141     }
2142     POSTACTION(m); /* drop lock */
2143     fprintf(stderr, "max system bytes = %10lu\n", (unsigned long)(maxfp));
2144     fprintf(stderr, "system bytes     = %10lu\n", (unsigned long)(fp));
2145     fprintf(stderr, "in use bytes     = %10lu\n", (unsigned long)(used));
2146   }
2147 }
2148 #endif /* NO_MALLOC_STATS */
2149
2150 /* ----------------------- Operations on smallbins ----------------------- */
2151
2152 /*
2153   Various forms of linking and unlinking are defined as macros.  Even
2154   the ones for trees, which are very long but have very short typical
2155   paths.  This is ugly but reduces reliance on inlining support of
2156   compilers.
2157 */
2158
2159 /* Link a free chunk into a smallbin  */
2160 #define insert_small_chunk(M, P, S) {\
2161   bindex_t I  = small_index(S);\
2162   mchunkptr B = smallbin_at(M, I);\
2163   mchunkptr F = B;\
2164   assert(S >= MIN_CHUNK_SIZE);\
2165   if (!smallmap_is_marked(M, I))\
2166     mark_smallmap(M, I);\
2167   else if (RTCHECK(ok_address(M, B->fd)))\
2168     F = B->fd;\
2169   else {\
2170     CORRUPTION_ERROR_ACTION(M);\
2171   }\
2172   B->fd = P;\
2173   F->bk = P;\
2174   P->fd = F;\
2175   P->bk = B;\
2176 }
2177
2178 /* Unlink a chunk from a smallbin  */
2179 #define unlink_small_chunk(M, P, S) {\
2180   mchunkptr F = P->fd;\
2181   mchunkptr B = P->bk;\
2182   bindex_t I = small_index(S);\
2183   assert(P != B);\
2184   assert(P != F);\
2185   assert(chunksize(P) == small_index2size(I));\
2186   if (RTCHECK(F == smallbin_at(M,I) || (ok_address(M, F) && F->bk == P))) { \
2187     if (B == F) {\
2188       clear_smallmap(M, I);\
2189     }\
2190     else if (RTCHECK(B == smallbin_at(M,I) ||\
2191                      (ok_address(M, B) && B->fd == P))) {\
2192       F->bk = B;\
2193       B->fd = F;\
2194     }\
2195     else {\
2196       CORRUPTION_ERROR_ACTION(M);\
2197     }\
2198   }\
2199   else {\
2200     CORRUPTION_ERROR_ACTION(M);\
2201   }\
2202 }
2203
2204 /* Unlink the first chunk from a smallbin */
2205 #define unlink_first_small_chunk(M, B, P, I) {\
2206   mchunkptr F = P->fd;\
2207   assert(P != B);\
2208   assert(P != F);\
2209   assert(chunksize(P) == small_index2size(I));\
2210   if (B == F) {\
2211     clear_smallmap(M, I);\
2212   }\
2213   else if (RTCHECK(ok_address(M, F) && F->bk == P)) {\
2214     F->bk = B;\
2215     B->fd = F;\
2216   }\
2217   else {\
2218     CORRUPTION_ERROR_ACTION(M);\
2219   }\
2220 }
2221
2222 /* Replace dv node, binning the old one */
2223 /* Used only when dvsize known to be small */
2224 #define replace_dv(M, P, S) {\
2225   size_t DVS = M->dvsize;\
2226   assert(is_small(DVS));\
2227   if (DVS != 0) {\
2228     mchunkptr DV = M->dv;\
2229     insert_small_chunk(M, DV, DVS);\
2230   }\
2231   M->dvsize = S;\
2232   M->dv = P;\
2233 }
2234
2235 /* ------------------------- Operations on trees ------------------------- */
2236
2237 /* Insert chunk into tree */
2238 #define insert_large_chunk(M, X, S) {\
2239   tbinptr* H;\
2240   bindex_t I;\
2241   compute_tree_index(S, I);\
2242   H = treebin_at(M, I);\
2243   X->index = I;\
2244   X->child[0] = X->child[1] = 0;\
2245   if (!treemap_is_marked(M, I)) {\
2246     mark_treemap(M, I);\
2247     *H = X;\
2248     X->parent = (tchunkptr)H;\
2249     X->fd = X->bk = X;\
2250   }\
2251   else {\
2252     tchunkptr T = *H;\
2253     size_t K = S << leftshift_for_tree_index(I);\
2254     for (;;) {\
2255       if (chunksize(T) != S) {\
2256         tchunkptr* C = &(T->child[(K >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1]);\
2257         K <<= 1;\
2258         if (*C != 0)\
2259           T = *C;\
2260         else if (RTCHECK(ok_address(M, C))) {\
2261           *C = X;\
2262           X->parent = T;\
2263           X->fd = X->bk = X;\
2264           break;\
2265         }\
2266         else {\
2267           CORRUPTION_ERROR_ACTION(M);\
2268           break;\
2269         }\
2270       }\
2271       else {\
2272         tchunkptr F = T->fd;\
2273         if (RTCHECK(ok_address(M, T) && ok_address(M, F))) {\
2274           T->fd = F->bk = X;\
2275           X->fd = F;\
2276           X->bk = T;\
2277           X->parent = 0;\
2278           break;\
2279         }\
2280         else {\
2281           CORRUPTION_ERROR_ACTION(M);\
2282           break;\
2283         }\
2284       }\
2285     }\
2286   }\
2287 }
2288
2289 /*
2290   Unlink steps:
2291
2292   1. If x is a chained node, unlink it from its same-sized fd/bk links
2293      and choose its bk node as its replacement.
2294   2. If x was the last node of its size, but not a leaf node, it must
2295      be replaced with a leaf node (not merely one with an open left or
2296      right), to make sure that lefts and rights of descendents
2297      correspond properly to bit masks.  We use the rightmost descendent
2298      of x.  We could use any other leaf, but this is easy to locate and
2299      tends to counteract removal of leftmosts elsewhere, and so keeps
2300      paths shorter than minimally guaranteed.  This doesn't loop much
2301      because on average a node in a tree is near the bottom.
2302   3. If x is the base of a chain (i.e., has parent links) relink
2303      x's parent and children to x's replacement (or null if none).
2304 */
2305
2306 #define unlink_large_chunk(M, X) {\
2307   tchunkptr XP = X->parent;\
2308   tchunkptr R;\
2309   if (X->bk != X) {\
2310     tchunkptr F = X->fd;\
2311     R = X->bk;\
2312     if (RTCHECK(ok_address(M, F) && F->bk == X && R->fd == X)) {\
2313       F->bk = R;\
2314       R->fd = F;\
2315     }\
2316     else {\
2317       CORRUPTION_ERROR_ACTION(M);\
2318     }\
2319   }\
2320   else {\
2321     tchunkptr* RP;\
2322     if (((R = *(RP = &(X->child[1]))) != 0) ||\
2323         ((R = *(RP = &(X->child[0]))) != 0)) {\
2324       tchunkptr* CP;\
2325       while ((*(CP = &(R->child[1])) != 0) ||\
2326              (*(CP = &(R->child[0])) != 0)) {\
2327         R = *(RP = CP);\
2328       }\
2329       if (RTCHECK(ok_address(M, RP)))\
2330         *RP = 0;\
2331       else {\
2332         CORRUPTION_ERROR_ACTION(M);\
2333       }\
2334     }\
2335   }\
2336   if (XP != 0) {\
2337     tbinptr* H = treebin_at(M, X->index);\
2338     if (X == *H) {\
2339       if ((*H = R) == 0) \
2340         clear_treemap(M, X->index);\
2341     }\
2342     else if (RTCHECK(ok_address(M, XP))) {\
2343       if (XP->child[0] == X) \
2344         XP->child[0] = R;\
2345       else \
2346         XP->child[1] = R;\
2347     }\
2348     else\
2349       CORRUPTION_ERROR_ACTION(M);\
2350     if (R != 0) {\
2351       if (RTCHECK(ok_address(M, R))) {\
2352         tchunkptr C0, C1;\
2353         R->parent = XP;\
2354         if ((C0 = X->child[0]) != 0) {\
2355           if (RTCHECK(ok_address(M, C0))) {\
2356             R->child[0] = C0;\
2357             C0->parent = R;\
2358           }\
2359           else\
2360             CORRUPTION_ERROR_ACTION(M);\
2361         }\
2362         if ((C1 = X->child[1]) != 0) {\
2363           if (RTCHECK(ok_address(M, C1))) {\
2364             R->child[1] = C1;\
2365             C1->parent = R;\
2366           }\
2367           else\
2368             CORRUPTION_ERROR_ACTION(M);\
2369         }\
2370       }\
2371       else\
2372         CORRUPTION_ERROR_ACTION(M);\
2373     }\
2374   }\
2375 }
2376
2377 /* Relays to large vs small bin operations */
2378
2379 #define insert_chunk(M, P, S)\
2380   if (is_small(S)) insert_small_chunk(M, P, S)\
2381   else { tchunkptr TP = (tchunkptr)(P); insert_large_chunk(M, TP, S); }
2382
2383 #define unlink_chunk(M, P, S)\
2384   if (is_small(S)) unlink_small_chunk(M, P, S)\
2385   else { tchunkptr TP = (tchunkptr)(P); unlink_large_chunk(M, TP); }
2386
2387
2388 /* Relays to internal calls to malloc/free from realloc, memalign etc */
2389
2390 #if ONLY_MSPACES
2391 #define internal_malloc(m, b) mspace_malloc(m, b)
2392 #define internal_free(m, mem) mspace_free(m,mem);
2393 #else /* ONLY_MSPACES */
2394 #if MSPACES
2395 #define internal_malloc(m, b)\
2396   ((m == gm)? dlmalloc(b) : mspace_malloc(m, b))
2397 #define internal_free(m, mem)\
2398    if (m == gm) dlfree(mem); else mspace_free(m,mem);
2399 #else /* MSPACES */
2400 #define internal_malloc(m, b) dlmalloc(b)
2401 #define internal_free(m, mem) dlfree(mem)
2402 #endif /* MSPACES */
2403 #endif /* ONLY_MSPACES */
2404
2405 /* -----------------------  Direct-mmapping chunks ----------------------- */
2406
2407 /*
2408   Directly mmapped chunks are set up with an offset to the start of
2409   the mmapped region stored in the prev_foot field of the chunk. This
2410   allows reconstruction of the required argument to MUNMAP when freed,
2411   and also allows adjustment of the returned chunk to meet alignment
2412   requirements (especially in memalign).
2413 */
2414
2415 /* Malloc using mmap */
2416 static void* mmap_alloc(mstate m, size_t nb) {
2417   size_t mmsize = mmap_align(nb + SIX_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
2418   if (m->footprint_limit != 0) {
2419     size_t fp = m->footprint + mmsize;
2420     if (fp <= m->footprint || fp > m->footprint_limit)
2421       return 0;
2422   }
2423   if (mmsize > nb) {     /* Check for wrap around 0 */
2424     char* mm = (char*)(CALL_DIRECT_MMAP(mmsize));
2425     if (mm != CMFAIL) {
2426       size_t offset = align_offset(chunk2mem(mm));
2427       size_t psize = mmsize - offset - MMAP_FOOT_PAD;
2428       mchunkptr p = (mchunkptr)(mm + offset);
2429       p->prev_foot = offset;
2430       p->head = psize;
2431       mark_inuse_foot(m, p, psize);
2432       chunk_plus_offset(p, psize)->head = FENCEPOST_HEAD;
2433       chunk_plus_offset(p, psize+SIZE_T_SIZE)->head = 0;
2434
2435       if (m->least_addr == 0 || mm < m->least_addr)
2436         m->least_addr = mm;
2437       if ((m->footprint += mmsize) > m->max_footprint)
2438         m->max_footprint = m->footprint;
2439       assert(is_aligned(chunk2mem(p)));
2440       check_mmapped_chunk(m, p);
2441       return chunk2mem(p);
2442     }
2443   }
2444   return 0;
2445 }
2446
2447 /* Realloc using mmap */
2448 static mchunkptr mmap_resize(mstate m, mchunkptr oldp, size_t nb, int flags) {
2449   size_t oldsize = chunksize(oldp);
2450   (void)flags; /* placate people compiling -Wunused */
2451   if (is_small(nb)) /* Can't shrink mmap regions below small size */
2452     return 0;
2453   /* Keep old chunk if big enough but not too big */
2454   if (oldsize >= nb + SIZE_T_SIZE &&
2455       (oldsize - nb) <= (mparams.granularity << 1))
2456     return oldp;
2457   else {
2458     size_t offset = oldp->prev_foot;
2459     size_t oldmmsize = oldsize + offset + MMAP_FOOT_PAD;
2460     size_t newmmsize = mmap_align(nb + SIX_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
2461     char* cp = (char*)CALL_MREMAP((char*)oldp - offset,
2462                                   oldmmsize, newmmsize, flags);
2463     if (cp != CMFAIL) {
2464       mchunkptr newp = (mchunkptr)(cp + offset);
2465       size_t psize = newmmsize - offset - MMAP_FOOT_PAD;
2466       newp->head = psize;
2467       mark_inuse_foot(m, newp, psize);
2468       chunk_plus_offset(newp, psize)->head = FENCEPOST_HEAD;
2469       chunk_plus_offset(newp, psize+SIZE_T_SIZE)->head = 0;
2470
2471       if (cp < m->least_addr)
2472         m->least_addr = cp;
2473       if ((m->footprint += newmmsize - oldmmsize) > m->max_footprint)
2474         m->max_footprint = m->footprint;
2475       check_mmapped_chunk(m, newp);
2476       return newp;
2477     }
2478   }
2479   return 0;
2480 }
2481
2482
2483 /* -------------------------- mspace management -------------------------- */
2484
2485 /* Initialize top chunk and its size */
2486 static void init_top(mstate m, mchunkptr p, size_t psize) {
2487   /* Ensure alignment */
2488   size_t offset = align_offset(chunk2mem(p));
2489   p = (mchunkptr)((char*)p + offset);
2490   psize -= offset;
2491
2492   m->top = p;
2493   m->topsize = psize;
2494   p->head = psize | PINUSE_BIT;
2495   /* set size of fake trailing chunk holding overhead space only once */
2496   chunk_plus_offset(p, psize)->head = TOP_FOOT_SIZE;
2497   m->trim_check = mparams.trim_threshold; /* reset on each update */
2498 }
2499
2500 /* Initialize bins for a new mstate that is otherwise zeroed out */
2501 static void init_bins(mstate m) {
2502   /* Establish circular links for smallbins */
2503   bindex_t i;
2504   for (i = 0; i < NSMALLBINS; ++i) {
2505     sbinptr bin = smallbin_at(m,i);
2506     bin->fd = bin->bk = bin;
2507   }
2508 }
2509
2510 #if PROCEED_ON_ERROR
2511
2512 /* default corruption action */
2513 static void reset_on_error(mstate m) {
2514   int i;
2515   ++malloc_corruption_error_count;
2516   /* Reinitialize fields to forget about all memory */
2517   m->smallmap = m->treemap = 0;
2518   m->dvsize = m->topsize = 0;
2519   m->seg.base = 0;
2520   m->seg.size = 0;
2521   m->seg.next = 0;
2522   m->top = m->dv = 0;
2523   for (i = 0; i < NTREEBINS; ++i)
2524     *treebin_at(m, i) = 0;
2525   init_bins(m);
2526 }
2527 #endif /* PROCEED_ON_ERROR */
2528
2529 /* Allocate chunk and prepend remainder with chunk in successor base. */
2530 static void* prepend_alloc(mstate m, char* newbase, char* oldbase,
2531                            size_t nb) {
2532   mchunkptr p = align_as_chunk(newbase);
2533   mchunkptr oldfirst = align_as_chunk(oldbase);
2534   size_t psize = (char*)oldfirst - (char*)p;
2535   mchunkptr q = chunk_plus_offset(p, nb);
2536   size_t qsize = psize - nb;
2537   set_size_and_pinuse_of_inuse_chunk(m, p, nb);
2538
2539   assert((char*)oldfirst > (char*)q);
2540   assert(pinuse(oldfirst));
2541   assert(qsize >= MIN_CHUNK_SIZE);
2542
2543   /* consolidate remainder with first chunk of old base */
2544   if (oldfirst == m->top) {
2545     size_t tsize = m->topsize += qsize;
2546     m->top = q;
2547     q->head = tsize | PINUSE_BIT;
2548     check_top_chunk(m, q);
2549   }
2550   else if (oldfirst == m->dv) {
2551     size_t dsize = m->dvsize += qsize;
2552     m->dv = q;
2553     set_size_and_pinuse_of_free_chunk(q, dsize);
2554   }
2555   else {
2556     if (!is_inuse(oldfirst)) {
2557       size_t nsize = chunksize(oldfirst);
2558       unlink_chunk(m, oldfirst, nsize);
2559       oldfirst = chunk_plus_offset(oldfirst, nsize);
2560       qsize += nsize;
2561     }
2562     set_free_with_pinuse(q, qsize, oldfirst);
2563     insert_chunk(m, q, qsize);
2564     check_free_chunk(m, q);
2565   }
2566
2567   check_malloced_chunk(m, chunk2mem(p), nb);
2568   return chunk2mem(p);
2569 }
2570
2571 /* Add a segment to hold a new noncontiguous region */
2572 static void add_segment(mstate m, char* tbase, size_t tsize, flag_t mmapped) {
2573   /* Determine locations and sizes of segment, fenceposts, old top */
2574   char* old_top = (char*)m->top;
2575   msegmentptr oldsp = segment_holding(m, old_top);
2576   char* old_end = oldsp->base + oldsp->size;
2577   size_t ssize = pad_request(sizeof(struct malloc_segment));
2578   char* rawsp = old_end - (ssize + FOUR_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
2579   size_t offset = align_offset(chunk2mem(rawsp));
2580   char* asp = rawsp + offset;
2581   char* csp = (asp < (old_top + MIN_CHUNK_SIZE))? old_top : asp;
2582   mchunkptr sp = (mchunkptr)csp;
2583   msegmentptr ss = (msegmentptr)(chunk2mem(sp));
2584   mchunkptr tnext = chunk_plus_offset(sp, ssize);
2585   mchunkptr p = tnext;
2586   int nfences = 0;
2587
2588   /* reset top to new space */
2589   init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE);
2590
2591   /* Set up segment record */
2592   assert(is_aligned(ss));
2593   set_size_and_pinuse_of_inuse_chunk(m, sp, ssize);
2594   *ss = m->seg; /* Push current record */
2595   m->seg.base = tbase;
2596   m->seg.size = tsize;
2597   m->seg.sflags = mmapped;
2598   m->seg.next = ss;
2599
2600   /* Insert trailing fenceposts */
2601   for (;;) {
2602     mchunkptr nextp = chunk_plus_offset(p, SIZE_T_SIZE);
2603     p->head = FENCEPOST_HEAD;
2604     ++nfences;
2605     if ((char*)(&(nextp->head)) < old_end)
2606       p = nextp;
2607     else
2608       break;
2609   }
2610   assert(nfences >= 2);
2611
2612   /* Insert the rest of old top into a bin as an ordinary free chunk */
2613   if (csp != old_top) {
2614     mchunkptr q = (mchunkptr)old_top;
2615     size_t psize = csp - old_top;
2616     mchunkptr tn = chunk_plus_offset(q, psize);
2617     set_free_with_pinuse(q, psize, tn);
2618     insert_chunk(m, q, psize);
2619   }
2620
2621   check_top_chunk(m, m->top);
2622 }
2623
2624 /* -------------------------- System allocation -------------------------- */
2625
2626 /* Get memory from system using MORECORE or MMAP */
2627 static void* sys_alloc(mstate m, size_t nb) {
2628   char* tbase = CMFAIL;
2629   size_t tsize = 0;
2630   flag_t mmap_flag = 0;
2631   size_t asize; /* allocation size */
2632
2633   ensure_initialization();
2634
2635   if (use_noexpand(m))
2636       return 0;
2637
2638   /* Directly map large chunks, but only if already initialized */
2639   if (use_mmap(m) && nb >= mparams.mmap_threshold && m->topsize != 0) {
2640     void* mem = mmap_alloc(m, nb);
2641     if (mem != 0)
2642       return mem;
2643   }
2644
2645   asize = granularity_align(nb + SYS_ALLOC_PADDING);
2646   if (asize <= nb)
2647     return 0; /* wraparound */
2648   if (m->footprint_limit != 0) {
2649     size_t fp = m->footprint + asize;
2650     if (fp <= m->footprint || fp > m->footprint_limit)
2651       return 0;
2652   }
2653
2654   /*
2655     Try getting memory in any of three ways (in most-preferred to
2656     least-preferred order):
2657     1. A call to MORECORE that can normally contiguously extend memory.
2658        (disabled if not MORECORE_CONTIGUOUS or not HAVE_MORECORE or
2659        or main space is mmapped or a previous contiguous call failed)
2660     2. A call to MMAP new space (disabled if not HAVE_MMAP).
2661        Note that under the default settings, if MORECORE is unable to
2662        fulfill a request, and HAVE_MMAP is true, then mmap is
2663        used as a noncontiguous system allocator. This is a useful backup
2664        strategy for systems with holes in address spaces -- in this case
2665        sbrk cannot contiguously expand the heap, but mmap may be able to
2666        find space.
2667     3. A call to MORECORE that cannot usually contiguously extend memory.
2668        (disabled if not HAVE_MORECORE)
2669
2670    In all cases, we need to request enough bytes from system to ensure
2671    we can malloc nb bytes upon success, so pad with enough space for
2672    top_foot, plus alignment-pad to make sure we don't lose bytes if
2673    not on boundary, and round this up to a granularity unit.
2674   */
2675
2676   if (MORECORE_CONTIGUOUS && !use_noncontiguous(m)) {
2677     char* br = CMFAIL;
2678     size_t ssize = asize; /* sbrk call size */
2679     msegmentptr ss = (m->top == 0)? 0 : segment_holding(m, (char*)m->top);
2680     ACQUIRE_MALLOC_GLOBAL_LOCK();
2681
2682     if (ss == 0) {  /* First time through or recovery */
2683       char* base = (char*)CALL_MORECORE(0);
2684       if (base != CMFAIL) {
2685         size_t fp;
2686         /* Adjust to end on a page boundary */
2687         if (!is_page_aligned(base))
2688           ssize += (page_align((size_t)base) - (size_t)base);
2689         fp = m->footprint + ssize; /* recheck limits */
2690         if (ssize > nb && ssize < HALF_MAX_SIZE_T &&
2691             (m->footprint_limit == 0 ||
2692              (fp > m->footprint && fp <= m->footprint_limit)) &&
2693             (br = (char*)(CALL_MORECORE(ssize))) == base) {
2694           tbase = base;
2695           tsize = ssize;
2696         }
2697       }
2698     }
2699     else {
2700       /* Subtract out existing available top space from MORECORE request. */
2701       ssize = granularity_align(nb - m->topsize + SYS_ALLOC_PADDING);
2702       /* Use mem here only if it did continuously extend old space */
2703       if (ssize < HALF_MAX_SIZE_T &&
2704           (br = (char*)(CALL_MORECORE(ssize))) == ss->base+ss->size) {
2705         tbase = br;
2706         tsize = ssize;
2707       }
2708     }
2709
2710     if (tbase == CMFAIL) {    /* Cope with partial failure */
2711       if (br != CMFAIL) {    /* Try to use/extend the space we did get */
2712         if (ssize < HALF_MAX_SIZE_T &&
2713             ssize < nb + SYS_ALLOC_PADDING) {
2714           size_t esize = granularity_align(nb + SYS_ALLOC_PADDING - ssize);
2715           if (esize < HALF_MAX_SIZE_T) {
2716             char* end = (char*)CALL_MORECORE(esize);
2717             if (end != CMFAIL)
2718               ssize += esize;
2719             else {            /* Can't use; try to release */
2720               (void) CALL_MORECORE(-ssize);
2721               br = CMFAIL;
2722             }
2723           }
2724         }
2725       }
2726       if (br != CMFAIL) {    /* Use the space we did get */
2727         tbase = br;
2728         tsize = ssize;
2729       }
2730       else
2731         disable_contiguous(m); /* Don't try contiguous path in the future */
2732     }
2733
2734     RELEASE_MALLOC_GLOBAL_LOCK();
2735   }
2736
2737   if (HAVE_MMAP && tbase == CMFAIL) {  /* Try MMAP */
2738     char* mp = (char*)(CALL_MMAP(asize));
2739     if (mp != CMFAIL) {
2740       tbase = mp;
2741       tsize = asize;
2742       mmap_flag = USE_MMAP_BIT;
2743     }
2744   }
2745
2746   if (HAVE_MORECORE && tbase == CMFAIL) { /* Try noncontiguous MORECORE */
2747     if (asize < HALF_MAX_SIZE_T) {
2748       char* br = CMFAIL;
2749       char* end = CMFAIL;
2750       ACQUIRE_MALLOC_GLOBAL_LOCK();
2751       br = (char*)(CALL_MORECORE(asize));
2752       end = (char*)(CALL_MORECORE(0));
2753       RELEASE_MALLOC_GLOBAL_LOCK();
2754       if (br != CMFAIL && end != CMFAIL && br < end) {
2755         size_t ssize = end - br;
2756         if (ssize > nb + TOP_FOOT_SIZE) {
2757           tbase = br;
2758           tsize = ssize;
2759         }
2760       }
2761     }
2762   }
2763
2764   if (tbase != CMFAIL) {
2765
2766     if ((m->footprint += tsize) > m->max_footprint)
2767       m->max_footprint = m->footprint;
2768
2769     if (!is_initialized(m)) { /* first-time initialization */
2770       if (m->least_addr == 0 || tbase < m->least_addr)
2771         m->least_addr = tbase;
2772       m->seg.base = tbase;
2773       m->seg.size = tsize;
2774       m->seg.sflags = mmap_flag;
2775       m->magic = mparams.magic;
2776       m->release_checks = MAX_RELEASE_CHECK_RATE;
2777       init_bins(m);
2778 #if !ONLY_MSPACES
2779       if (is_global(m))
2780         init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE);
2781       else
2782 #endif
2783       {
2784         /* Offset top by embedded malloc_state */
2785         mchunkptr mn = next_chunk(mem2chunk(m));
2786         init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) -TOP_FOOT_SIZE);
2787       }
2788     }
2789
2790     else {
2791       /* Try to merge with an existing segment */
2792       msegmentptr sp = &m->seg;
2793       /* Only consider most recent segment if traversal suppressed */
2794       while (sp != 0 && tbase != sp->base + sp->size)
2795         sp = (NO_SEGMENT_TRAVERSAL) ? 0 : sp->next;
2796       if (sp != 0 &&
2797           !is_extern_segment(sp) &&
2798           (sp->sflags & USE_MMAP_BIT) == mmap_flag &&
2799           segment_holds(sp, m->top)) { /* append */
2800         sp->size += tsize;
2801         init_top(m, m->top, m->topsize + tsize);
2802       }
2803       else {
2804         if (tbase < m->least_addr)
2805           m->least_addr = tbase;
2806         sp = &m->seg;
2807         while (sp != 0 && sp->base != tbase + tsize)
2808           sp = (NO_SEGMENT_TRAVERSAL) ? 0 : sp->next;
2809         if (sp != 0 &&
2810             !is_extern_segment(sp) &&
2811             (sp->sflags & USE_MMAP_BIT) == mmap_flag) {
2812           char* oldbase = sp->base;
2813           sp->base = tbase;
2814           sp->size += tsize;
2815           return prepend_alloc(m, tbase, oldbase, nb);
2816         }
2817         else
2818           add_segment(m, tbase, tsize, mmap_flag);
2819       }
2820     }
2821
2822     if (nb < m->topsize) { /* Allocate from new or extended top space */
2823       size_t rsize = m->topsize -= nb;
2824       mchunkptr p = m->top;
2825       mchunkptr r = m->top = chunk_plus_offset(p, nb);
2826       r->head = rsize | PINUSE_BIT;
2827       set_size_and_pinuse_of_inuse_chunk(m, p, nb);
2828       check_top_chunk(m, m->top);
2829       check_malloced_chunk(m, chunk2mem(p), nb);
2830       return chunk2mem(p);
2831     }
2832   }
2833
2834   MALLOC_FAILURE_ACTION;
2835   return 0;
2836 }
2837
2838 /* -----------------------  system deallocation -------------------------- */
2839
2840 /* Unmap and unlink any mmapped segments that don't contain used chunks */
2841 static size_t release_unused_segments(mstate m) {
2842   size_t released = 0;
2843   int nsegs = 0;
2844   msegmentptr pred = &m->seg;
2845   msegmentptr sp = pred->next;
2846   while (sp != 0) {
2847     char* base = sp->base;
2848     size_t size = sp->size;
2849     msegmentptr next = sp->next;
2850     ++nsegs;
2851     if (is_mmapped_segment(sp) && !is_extern_segment(sp)) {
2852       mchunkptr p = align_as_chunk(base);
2853       size_t psize = chunksize(p);
2854       /* Can unmap if first chunk holds entire segment and not pinned */
2855       if (!is_inuse(p) && (char*)p + psize >= base + size - TOP_FOOT_SIZE) {
2856         tchunkptr tp = (tchunkptr)p;
2857         assert(segment_holds(sp, (char*)sp));
2858         if (p == m->dv) {
2859           m->dv = 0;
2860           m->dvsize = 0;
2861         }
2862         else {
2863           unlink_large_chunk(m, tp);
2864         }
2865         if (CALL_MUNMAP(base, size) == 0) {
2866           released += size;
2867           m->footprint -= size;
2868           /* unlink obsoleted record */
2869           sp = pred;
2870           sp->next = next;
2871         }
2872         else { /* back out if cannot unmap */
2873           insert_large_chunk(m, tp, psize);
2874         }
2875       }
2876     }
2877     if (NO_SEGMENT_TRAVERSAL) /* scan only first segment */
2878       break;
2879     pred = sp;
2880     sp = next;
2881   }
2882   /* Reset check counter */
2883   m->release_checks = (((size_t) nsegs > (size_t) MAX_RELEASE_CHECK_RATE)?
2884                        (size_t) nsegs : (size_t) MAX_RELEASE_CHECK_RATE);
2885   return released;
2886 }
2887
2888 static int sys_trim(mstate m, size_t pad) {
2889   size_t released = 0;
2890   ensure_initialization();
2891   if (pad < MAX_REQUEST && is_initialized(m)) {
2892     pad += TOP_FOOT_SIZE; /* ensure enough room for segment overhead */
2893
2894     if (m->topsize > pad) {
2895       /* Shrink top space in granularity-size units, keeping at least one */
2896       size_t unit = mparams.granularity;
2897       size_t extra = ((m->topsize - pad + (unit - SIZE_T_ONE)) / unit -
2898                       SIZE_T_ONE) * unit;
2899       msegmentptr sp = segment_holding(m, (char*)m->top);
2900
2901       if (!is_extern_segment(sp)) {
2902         if (is_mmapped_segment(sp)) {
2903           if (HAVE_MMAP &&
2904               sp->size >= extra &&
2905               !has_segment_link(m, sp)) { /* can't shrink if pinned */
2906             size_t newsize = sp->size - extra;
2907             (void)newsize; /* placate people compiling -Wunused-variable */
2908             /* Prefer mremap, fall back to munmap */
2909             if ((CALL_MREMAP(sp->base, sp->size, newsize, 0) != MFAIL) ||
2910                 (CALL_MUNMAP(sp->base + newsize, extra) == 0)) {
2911               released = extra;
2912             }
2913           }
2914         }
2915         else if (HAVE_MORECORE) {
2916           if (extra >= HALF_MAX_SIZE_T) /* Avoid wrapping negative */
2917             extra = (HALF_MAX_SIZE_T) + SIZE_T_ONE - unit;
2918           ACQUIRE_MALLOC_GLOBAL_LOCK();
2919           {
2920             /* Make sure end of memory is where we last set it. */
2921             char* old_br = (char*)(CALL_MORECORE(0));
2922             if (old_br == sp->base + sp->size) {
2923               char* rel_br = (char*)(CALL_MORECORE(-extra));
2924               char* new_br = (char*)(CALL_MORECORE(0));
2925               if (rel_br != CMFAIL && new_br < old_br)
2926                 released = old_br - new_br;
2927             }
2928           }
2929           RELEASE_MALLOC_GLOBAL_LOCK();
2930         }
2931       }
2932
2933       if (released != 0) {
2934         sp->size -= released;
2935         m->footprint -= released;
2936         init_top(m, m->top, m->topsize - released);
2937         check_top_chunk(m, m->top);
2938       }
2939     }
2940
2941     /* Unmap any unused mmapped segments */
2942     if (HAVE_MMAP)
2943       released += release_unused_segments(m);
2944
2945     /* On failure, disable autotrim to avoid repeated failed future calls */
2946     if (released == 0 && m->topsize > m->trim_check)
2947       m->trim_check = MAX_SIZE_T;
2948   }
2949
2950   return (released != 0)? 1 : 0;
2951 }
2952
2953 /* Consolidate and bin a chunk. Differs from exported versions
2954    of free mainly in that the chunk need not be marked as inuse.
2955 */
2956 static void dispose_chunk(mstate m, mchunkptr p, size_t psize) {
2957   mchunkptr next = chunk_plus_offset(p, psize);
2958   if (!pinuse(p)) {
2959     mchunkptr prev;
2960     size_t prevsize = p->prev_foot;
2961     if (is_mmapped(p)) {
2962       psize += prevsize + MMAP_FOOT_PAD;
2963       if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)
2964         m->footprint -= psize;
2965       return;
2966     }
2967     prev = chunk_minus_offset(p, prevsize);
2968     psize += prevsize;
2969     p = prev;
2970     if (RTCHECK(ok_address(m, prev))) { /* consolidate backward */
2971       if (p != m->dv) {
2972         unlink_chunk(m, p, prevsize);
2973       }
2974       else if ((next->head & INUSE_BITS) == INUSE_BITS) {
2975         m->dvsize = psize;
2976         set_free_with_pinuse(p, psize, next);
2977         return;
2978       }
2979     }
2980     else {
2981       CORRUPTION_ERROR_ACTION(m);
2982       return;
2983     }
2984   }
2985   if (RTCHECK(ok_address(m, next))) {
2986     if (!cinuse(next)) {  /* consolidate forward */
2987       if (next == m->top) {
2988         size_t tsize = m->topsize += psize;
2989         m->top = p;
2990         p->head = tsize | PINUSE_BIT;
2991         if (p == m->dv) {
2992           m->dv = 0;
2993           m->dvsize = 0;
2994         }
2995         return;
2996       }
2997       else if (next == m->dv) {
2998         size_t dsize = m->dvsize += psize;
2999         m->dv = p;
3000         set_size_and_pinuse_of_free_chunk(p, dsize);
3001         return;
3002       }
3003       else {
3004         size_t nsize = chunksize(next);
3005         psize += nsize;
3006         unlink_chunk(m, next, nsize);
3007         set_size_and_pinuse_of_free_chunk(p, psize);
3008         if (p == m->dv) {
3009           m->dvsize = psize;
3010           return;
3011         }
3012       }
3013     }
3014     else {
3015       set_free_with_pinuse(p, psize, next);
3016     }
3017     insert_chunk(m, p, psize);
3018   }
3019   else {
3020     CORRUPTION_ERROR_ACTION(m);
3021   }
3022 }
3023
3024 /* ---------------------------- malloc --------------------------- */
3025
3026 /* allocate a large request from the best fitting chunk in a treebin */
3027 static void* tmalloc_large(mstate m, size_t nb) {
3028   tchunkptr v = 0;
3029   size_t rsize = -nb; /* Unsigned negation */
3030   tchunkptr t;
3031   bindex_t idx;
3032   compute_tree_index(nb, idx);
3033   if ((t = *treebin_at(m, idx)) != 0) {
3034     /* Traverse tree for this bin looking for node with size == nb */
3035     size_t sizebits = nb << leftshift_for_tree_index(idx);
3036     tchunkptr rst = 0;  /* The deepest untaken right subtree */
3037     for (;;) {
3038       tchunkptr rt;
3039       size_t trem = chunksize(t) - nb;
3040       if (trem < rsize) {
3041         v = t;
3042         if ((rsize = trem) == 0)
3043           break;
3044       }
3045       rt = t->child[1];
3046       t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
3047       if (rt != 0 && rt != t)
3048         rst = rt;
3049       if (t == 0) {
3050         t = rst; /* set t to least subtree holding sizes > nb */
3051         break;
3052       }
3053       sizebits <<= 1;
3054     }
3055   }
3056   if (t == 0 && v == 0) { /* set t to root of next non-empty treebin */
3057     binmap_t leftbits = left_bits(idx2bit(idx)) & m->treemap;
3058     if (leftbits != 0) {
3059       bindex_t i;
3060       binmap_t leastbit = least_bit(leftbits);
3061       compute_bit2idx(leastbit, i);
3062       t = *treebin_at(m, i);
3063     }
3064   }
3065
3066   while (t != 0) { /* find smallest of tree or subtree */
3067     size_t trem = chunksize(t) - nb;
3068     if (trem < rsize) {
3069       rsize = trem;
3070       v = t;
3071     }
3072     t = leftmost_child(t);
3073   }
3074
3075   /*  If dv is a better fit, return 0 so malloc will use it */
3076   if (v != 0 && rsize < (size_t)(m->dvsize - nb)) {
3077     if (RTCHECK(ok_address(m, v))) { /* split */
3078       mchunkptr r = chunk_plus_offset(v, nb);
3079       assert(chunksize(v) == rsize + nb);
3080       if (RTCHECK(ok_next(v, r))) {
3081         unlink_large_chunk(m, v);
3082         if (rsize < MIN_CHUNK_SIZE)
3083           set_inuse_and_pinuse(m, v, (rsize + nb));
3084         else {
3085           set_size_and_pinuse_of_inuse_chunk(m, v, nb);
3086           set_size_and_pinuse_of_free_chunk(r, rsize);
3087           insert_chunk(m, r, rsize);
3088         }
3089         return chunk2mem(v);
3090       }
3091     }
3092     CORRUPTION_ERROR_ACTION(m);
3093   }
3094   return 0;
3095 }
3096
3097 /* allocate a small request from the best fitting chunk in a treebin */
3098 static void* tmalloc_small(mstate m, size_t nb) {
3099   tchunkptr t, v;
3100   size_t rsize;
3101   bindex_t i;
3102   binmap_t leastbit = least_bit(m->treemap);
3103   compute_bit2idx(leastbit, i);
3104   v = t = *treebin_at(m, i);
3105   rsize = chunksize(t) - nb;
3106
3107   while ((t = leftmost_child(t)) != 0) {
3108     size_t trem = chunksize(t) - nb;
3109     if (trem < rsize) {
3110       rsize = trem;
3111       v = t;
3112     }
3113   }
3114
3115   if (RTCHECK(ok_address(m, v))) {
3116     mchunkptr r = chunk_plus_offset(v, nb);
3117     assert(chunksize(v) == rsize + nb);
3118     if (RTCHECK(ok_next(v, r))) {
3119       unlink_large_chunk(m, v);
3120       if (rsize < MIN_CHUNK_SIZE)
3121         set_inuse_and_pinuse(m, v, (rsize + nb));
3122       else {
3123         set_size_and_pinuse_of_inuse_chunk(m, v, nb);
3124         set_size_and_pinuse_of_free_chunk(r, rsize);
3125         replace_dv(m, r, rsize);
3126       }
3127       return chunk2mem(v);
3128     }
3129   }
3130
3131   CORRUPTION_ERROR_ACTION(m);
3132   return 0;
3133 }
3134
3135 #if !ONLY_MSPACES
3136
3137 void* dlmalloc(size_t bytes) {
3138   /*
3139      Basic algorithm:
3140      If a small request (< 256 bytes minus per-chunk overhead):
3141        1. If one exists, use a remainderless chunk in associated smallbin.
3142           (Remainderless means that there are too few excess bytes to
3143           represent as a chunk.)
3144        2. If it is big enough, use the dv chunk, which is normally the
3145           chunk adjacent to the one used for the most recent small request.
3146        3. If one exists, split the smallest available chunk in a bin,
3147           saving remainder in dv.
3148        4. If it is big enough, use the top chunk.
3149        5. If available, get memory from system and use it
3150      Otherwise, for a large request:
3151        1. Find the smallest available binned chunk that fits, and use it
3152           if it is better fitting than dv chunk, splitting if necessary.
3153        2. If better fitting than any binned chunk, use the dv chunk.
3154        3. If it is big enough, use the top chunk.
3155        4. If request size >= mmap threshold, try to directly mmap this chunk.
3156        5. If available, get memory from system and use it
3157
3158      The ugly goto's here ensure that postaction occurs along all paths.
3159   */
3160
3161 #if USE_LOCKS
3162   ensure_initialization(); /* initialize in sys_alloc if not using locks */
3163 #endif
3164
3165   if (!PREACTION(gm)) {
3166     void* mem;
3167     size_t nb;
3168     if (bytes <= MAX_SMALL_REQUEST) {
3169       bindex_t idx;
3170       binmap_t smallbits;
3171       nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes);
3172       idx = small_index(nb);
3173       smallbits = gm->smallmap >> idx;
3174
3175       if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */
3176         mchunkptr b, p;
3177         idx += ~smallbits & 1;       /* Uses next bin if idx empty */
3178         b = smallbin_at(gm, idx);
3179         p = b->fd;
3180         assert(chunksize(p) == small_index2size(idx));
3181         unlink_first_small_chunk(gm, b, p, idx);
3182         set_inuse_and_pinuse(gm, p, small_index2size(idx));
3183         mem = chunk2mem(p);
3184         check_malloced_chunk(gm, mem, nb);
3185         goto postaction;
3186       }
3187
3188       else if (nb > gm->dvsize) {
3189         if (smallbits != 0) { /* Use chunk in next nonempty smallbin */
3190           mchunkptr b, p, r;
3191           size_t rsize;
3192           bindex_t i;
3193           binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));
3194           binmap_t leastbit = least_bit(leftbits);
3195           compute_bit2idx(leastbit, i);
3196           b = smallbin_at(gm, i);
3197           p = b->fd;
3198           assert(chunksize(p) == small_index2size(i));
3199           unlink_first_small_chunk(gm, b, p, i);
3200           rsize = small_index2size(i) - nb;
3201           /* Fit here cannot be remainderless if 4byte sizes */
3202           if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE)
3203             set_inuse_and_pinuse(gm, p, small_index2size(i));
3204           else {
3205             set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
3206             r = chunk_plus_offset(p, nb);
3207             set_size_and_pinuse_of_free_chunk(r, rsize);
3208             replace_dv(gm, r, rsize);
3209           }
3210           mem = chunk2mem(p);
3211           check_malloced_chunk(gm, mem, nb);
3212           goto postaction;
3213         }
3214
3215         else if (gm->treemap != 0 && (mem = tmalloc_small(gm, nb)) != 0) {
3216           check_malloced_chunk(gm, mem, nb);
3217           goto postaction;
3218         }
3219       }
3220     }
3221     else if (bytes >= MAX_REQUEST)
3222       nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */
3223     else {
3224       nb = pad_request(bytes);
3225       if (gm->treemap != 0 && (mem = tmalloc_large(gm, nb)) != 0) {
3226         check_malloced_chunk(gm, mem, nb);
3227         goto postaction;
3228       }
3229     }
3230
3231     if (nb <= gm->dvsize) {
3232       size_t rsize = gm->dvsize - nb;
3233       mchunkptr p = gm->dv;
3234       if (rsize >= MIN_CHUNK_SIZE) { /* split dv */
3235         mchunkptr r = gm->dv = chunk_plus_offset(p, nb);
3236         gm->dvsize = rsize;
3237         set_size_and_pinuse_of_free_chunk(r, rsize);
3238         set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
3239       }
3240       else { /* exhaust dv */
3241         size_t dvs = gm->dvsize;
3242         gm->dvsize = 0;
3243         gm->dv = 0;
3244         set_inuse_and_pinuse(gm, p, dvs);
3245       }
3246       mem = chunk2mem(p);
3247       check_malloced_chunk(gm, mem, nb);
3248       goto postaction;
3249     }
3250
3251     else if (nb < gm->topsize) { /* Split top */
3252       size_t rsize = gm->topsize -= nb;
3253       mchunkptr p = gm->top;
3254       mchunkptr r = gm->top = chunk_plus_offset(p, nb);
3255       r->head = rsize | PINUSE_BIT;
3256       set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
3257       mem = chunk2mem(p);
3258       check_top_chunk(gm, gm->top);
3259       check_malloced_chunk(gm, mem, nb);
3260       goto postaction;
3261     }
3262
3263     mem = sys_alloc(gm, nb);
3264
3265   postaction:
3266     POSTACTION(gm);
3267     return mem;
3268   }
3269
3270   return 0;
3271 }
3272
3273 /* ---------------------------- free --------------------------- */
3274
3275 void dlfree(void* mem) {
3276   /*
3277      Consolidate freed chunks with preceeding or succeeding bordering
3278      free chunks, if they exist, and then place in a bin.  Intermixed
3279      with special cases for top, dv, mmapped chunks, and usage errors.
3280   */
3281
3282   if (mem != 0) {
3283     mchunkptr p  = mem2chunk(mem);
3284 #if FOOTERS
3285     mstate fm = get_mstate_for(p);
3286     if (!ok_magic(fm)) {
3287       USAGE_ERROR_ACTION(fm, p);
3288       return;
3289     }
3290 #else /* FOOTERS */
3291 #define fm gm
3292 #endif /* FOOTERS */
3293     if (!PREACTION(fm)) {
3294       check_inuse_chunk(fm, p);
3295       if (RTCHECK(ok_address(fm, p) && ok_inuse(p))) {
3296         size_t psize = chunksize(p);
3297         mchunkptr next = chunk_plus_offset(p, psize);
3298         if (!pinuse(p)) {
3299           size_t prevsize = p->prev_foot;
3300           if (is_mmapped(p)) {
3301             psize += prevsize + MMAP_FOOT_PAD;
3302             if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)
3303               fm->footprint -= psize;
3304             goto postaction;
3305           }
3306           else {
3307             mchunkptr prev = chunk_minus_offset(p, prevsize);
3308             psize += prevsize;
3309             p = prev;
3310             if (RTCHECK(ok_address(fm, prev))) { /* consolidate backward */
3311               if (p != fm->dv) {
3312                 unlink_chunk(fm, p, prevsize);
3313               }
3314               else if ((next->head & INUSE_BITS) == INUSE_BITS) {
3315                 fm->dvsize = psize;
3316                 set_free_with_pinuse(p, psize, next);
3317                 goto postaction;
3318               }
3319             }
3320             else
3321               goto erroraction;
3322           }
3323         }
3324
3325         if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) {
3326           if (!cinuse(next)) {  /* consolidate forward */
3327             if (next == fm->top) {
3328               size_t tsize = fm->topsize += psize;
3329               fm->top = p;
3330               p->head = tsize | PINUSE_BIT;
3331               if (p == fm->dv) {
3332                 fm->dv = 0;
3333                 fm->dvsize = 0;
3334               }
3335               if (should_trim(fm, tsize))
3336                 sys_trim(fm, 0);
3337               goto postaction;
3338             }
3339             else if (next == fm->dv) {
3340               size_t dsize = fm->dvsize += psize;
3341               fm->dv = p;
3342               set_size_and_pinuse_of_free_chunk(p, dsize);
3343               goto postaction;
3344             }
3345             else {
3346               size_t nsize = chunksize(next);
3347               psize += nsize;
3348               unlink_chunk(fm, next, nsize);
3349               set_size_and_pinuse_of_free_chunk(p, psize);
3350               if (p == fm->dv) {
3351                 fm->dvsize = psize;
3352                 goto postaction;
3353               }
3354             }
3355           }
3356           else
3357             set_free_with_pinuse(p, psize, next);
3358
3359           if (is_small(psize)) {
3360             insert_small_chunk(fm, p, psize);
3361             check_free_chunk(fm, p);
3362           }
3363           else {
3364             tchunkptr tp = (tchunkptr)p;
3365             insert_large_chunk(fm, tp, psize);
3366             check_free_chunk(fm, p);
3367             if (--fm->release_checks == 0)
3368               release_unused_segments(fm);
3369           }
3370           goto postaction;
3371         }
3372       }
3373     erroraction:
3374       USAGE_ERROR_ACTION(fm, p);
3375     postaction:
3376       POSTACTION(fm);
3377     }
3378   }
3379 #if !FOOTERS
3380 #undef fm
3381 #endif /* FOOTERS */
3382 }
3383
3384 void* dlcalloc(size_t n_elements, size_t elem_size) {
3385   void* mem;
3386   size_t req = 0;
3387   if (n_elements != 0) {
3388     req = n_elements * elem_size;
3389     if (((n_elements | elem_size) & ~(size_t)0xffff) &&
3390         (req / n_elements != elem_size))
3391       req = MAX_SIZE_T; /* force downstream failure on overflow */
3392   }
3393   mem = dlmalloc(req);
3394   if (mem != 0 && calloc_must_clear(mem2chunk(mem)))
3395     memset(mem, 0, req);
3396   return mem;
3397 }
3398
3399 #endif /* !ONLY_MSPACES */
3400
3401 /* ------------ Internal support for realloc, memalign, etc -------------- */
3402
3403 /* Try to realloc; only in-place unless can_move true */
3404 static mchunkptr try_realloc_chunk(mstate m, mchunkptr p, size_t nb,
3405                                    int can_move) {
3406   mchunkptr newp = 0;
3407   size_t oldsize = chunksize(p);
3408   mchunkptr next = chunk_plus_offset(p, oldsize);
3409   if (RTCHECK(ok_address(m, p) && ok_inuse(p) &&
3410               ok_next(p, next) && ok_pinuse(next))) {
3411     if (is_mmapped(p)) {
3412       newp = mmap_resize(m, p, nb, can_move);
3413     }
3414     else if (oldsize >= nb) {             /* already big enough */
3415       size_t rsize = oldsize - nb;
3416       if (rsize >= MIN_CHUNK_SIZE) {      /* split off remainder */
3417         mchunkptr r = chunk_plus_offset(p, nb);
3418         set_inuse(m, p, nb);
3419         set_inuse(m, r, rsize);
3420         dispose_chunk(m, r, rsize);
3421       }
3422       newp = p;
3423     }
3424     else if (next == m->top) {  /* extend into top */
3425       if (oldsize + m->topsize > nb) {
3426         size_t newsize = oldsize + m->topsize;
3427         size_t newtopsize = newsize - nb;
3428         mchunkptr newtop = chunk_plus_offset(p, nb);
3429         set_inuse(m, p, nb);
3430         newtop->head = newtopsize |PINUSE_BIT;
3431         m->top = newtop;
3432         m->topsize = newtopsize;
3433         newp = p;
3434       }
3435     }
3436     else if (next == m->dv) { /* extend into dv */
3437       size_t dvs = m->dvsize;
3438       if (oldsize + dvs >= nb) {
3439         size_t dsize = oldsize + dvs - nb;
3440         if (dsize >= MIN_CHUNK_SIZE) {
3441           mchunkptr r = chunk_plus_offset(p, nb);
3442           mchunkptr n = chunk_plus_offset(r, dsize);
3443           set_inuse(m, p, nb);
3444           set_size_and_pinuse_of_free_chunk(r, dsize);
3445           clear_pinuse(n);
3446           m->dvsize = dsize;
3447           m->dv = r;
3448         }
3449         else { /* exhaust dv */
3450           size_t newsize = oldsize + dvs;
3451           set_inuse(m, p, newsize);
3452           m->dvsize = 0;
3453           m->dv = 0;
3454         }
3455         newp = p;
3456       }
3457     }
3458     else if (!cinuse(next)) { /* extend into next free chunk */
3459       size_t nextsize = chunksize(next);
3460       if (oldsize + nextsize >= nb) {
3461         size_t rsize = oldsize + nextsize - nb;
3462         unlink_chunk(m, next, nextsize);
3463         if (rsize < MIN_CHUNK_SIZE) {
3464           size_t newsize = oldsize + nextsize;
3465           set_inuse(m, p, newsize);
3466         }
3467         else {
3468           mchunkptr r = chunk_plus_offset(p, nb);
3469           set_inuse(m, p, nb);
3470           set_inuse(m, r, rsize);
3471           dispose_chunk(m, r, rsize);
3472         }
3473         newp = p;
3474       }
3475     }
3476   }
3477   else {
3478     USAGE_ERROR_ACTION(m, chunk2mem(p));
3479   }
3480   return newp;
3481 }
3482
3483 static void* internal_memalign(mstate m, size_t alignment, size_t bytes) {
3484   void* mem = 0;
3485   if (alignment <  MIN_CHUNK_SIZE) /* must be at least a minimum chunk size */
3486     alignment = MIN_CHUNK_SIZE;
3487   if ((alignment & (alignment-SIZE_T_ONE)) != 0) {/* Ensure a power of 2 */
3488     size_t a = MALLOC_ALIGNMENT << 1;
3489     while (a < alignment) a <<= 1;
3490     alignment = a;
3491   }
3492   if (bytes >= MAX_REQUEST - alignment) {
3493     if (m != 0)  { /* Test isn't needed but avoids compiler warning */
3494       MALLOC_FAILURE_ACTION;
3495     }
3496   }
3497   else {
3498     size_t nb = request2size(bytes);
3499     size_t req = nb + alignment + MIN_CHUNK_SIZE - CHUNK_OVERHEAD;
3500     mem = internal_malloc(m, req);
3501     if (mem != 0) {
3502       mchunkptr p = mem2chunk(mem);
3503       if (PREACTION(m))
3504         return 0;
3505       if ((((size_t)(mem)) & (alignment - 1)) != 0) { /* misaligned */
3506         /*
3507           Find an aligned spot inside chunk.  Since we need to give
3508           back leading space in a chunk of at least MIN_CHUNK_SIZE, if
3509           the first calculation places us at a spot with less than
3510           MIN_CHUNK_SIZE leader, we can move to the next aligned spot.
3511           We've allocated enough total room so that this is always
3512           possible.
3513         */
3514         char* br = (char*)mem2chunk((size_t)(((size_t)((char*)mem + alignment -
3515                                                        SIZE_T_ONE)) &
3516                                              -alignment));
3517         char* pos = ((size_t)(br - (char*)(p)) >= MIN_CHUNK_SIZE)?
3518           br : br+alignment;
3519         mchunkptr newp = (mchunkptr)pos;
3520         size_t leadsize = pos - (char*)(p);
3521         size_t newsize = chunksize(p) - leadsize;
3522
3523         if (is_mmapped(p)) { /* For mmapped chunks, just adjust offset */
3524           newp->prev_foot = p->prev_foot + leadsize;
3525           newp->head = newsize;
3526         }
3527         else { /* Otherwise, give back leader, use the rest */
3528           set_inuse(m, newp, newsize);
3529           set_inuse(m, p, leadsize);
3530           dispose_chunk(m, p, leadsize);
3531         }
3532         p = newp;
3533       }
3534
3535       /* Give back spare room at the end */
3536       if (!is_mmapped(p)) {
3537         size_t size = chunksize(p);
3538         if (size > nb + MIN_CHUNK_SIZE) {
3539           size_t remainder_size = size - nb;
3540           mchunkptr remainder = chunk_plus_offset(p, nb);
3541           set_inuse(m, p, nb);
3542           set_inuse(m, remainder, remainder_size);
3543           dispose_chunk(m, remainder, remainder_size);
3544         }
3545       }
3546
3547       mem = chunk2mem(p);
3548       assert (chunksize(p) >= nb);
3549       assert(((size_t)mem & (alignment - 1)) == 0);
3550       check_inuse_chunk(m, p);
3551       POSTACTION(m);
3552     }
3553   }
3554   return mem;
3555 }
3556
3557 /*
3558   Common support for independent_X routines, handling
3559     all of the combinations that can result.
3560   The opts arg has:
3561     bit 0 set if all elements are same size (using sizes[0])
3562     bit 1 set if elements should be zeroed
3563 */
3564 static void** ialloc(mstate m,
3565                      size_t n_elements,
3566                      size_t* sizes,
3567                      int opts,
3568                      void* chunks[]) {
3569
3570   size_t    element_size;   /* chunksize of each element, if all same */
3571   size_t    contents_size;  /* total size of elements */
3572   size_t    array_size;     /* request size of pointer array */
3573   void*     mem;            /* malloced aggregate space */
3574   mchunkptr p;              /* corresponding chunk */
3575   size_t    remainder_size; /* remaining bytes while splitting */
3576   void**    marray;         /* either "chunks" or malloced ptr array */
3577   mchunkptr array_chunk;    /* chunk for malloced ptr array */
3578   flag_t    was_enabled;    /* to disable mmap */
3579   size_t    size;
3580   size_t    i;
3581
3582   ensure_initialization();
3583   /* compute array length, if needed */
3584   if (chunks != 0) {
3585     if (n_elements == 0)
3586       return chunks; /* nothing to do */
3587     marray = chunks;
3588     array_size = 0;
3589   }
3590   else {
3591     /* if empty req, must still return chunk representing empty array */
3592     if (n_elements == 0)
3593       return (void**)internal_malloc(m, 0);
3594     marray = 0;
3595     array_size = request2size(n_elements * (sizeof(void*)));
3596   }
3597
3598   /* compute total element size */
3599   if (opts & 0x1) { /* all-same-size */
3600     element_size = request2size(*sizes);
3601     contents_size = n_elements * element_size;
3602   }
3603   else { /* add up all the sizes */
3604     element_size = 0;
3605     contents_size = 0;
3606     for (i = 0; i != n_elements; ++i)
3607       contents_size += request2size(sizes[i]);
3608   }
3609
3610   size = contents_size + array_size;
3611
3612   /*
3613      Allocate the aggregate chunk.  First disable direct-mmapping so
3614      malloc won't use it, since we would not be able to later
3615      free/realloc space internal to a segregated mmap region.
3616   */
3617   was_enabled = use_mmap(m);
3618   disable_mmap(m);
3619   mem = internal_malloc(m, size - CHUNK_OVERHEAD);
3620   if (was_enabled)
3621     enable_mmap(m);
3622   if (mem == 0)
3623     return 0;
3624
3625   if (PREACTION(m)) return 0;
3626   p = mem2chunk(mem);
3627   remainder_size = chunksize(p);
3628
3629   assert(!is_mmapped(p));
3630
3631   if (opts & 0x2) {       /* optionally clear the elements */
3632     memset((size_t*)mem, 0, remainder_size - SIZE_T_SIZE - array_size);
3633   }
3634
3635   /* If not provided, allocate the pointer array as final part of chunk */
3636   if (marray == 0) {
3637     size_t  array_chunk_size;
3638     array_chunk = chunk_plus_offset(p, contents_size);
3639     array_chunk_size = remainder_size - contents_size;
3640     marray = (void**) (chunk2mem(array_chunk));
3641     set_size_and_pinuse_of_inuse_chunk(m, array_chunk, array_chunk_size);
3642     remainder_size = contents_size;
3643   }
3644
3645   /* split out elements */
3646   for (i = 0; ; ++i) {
3647     marray[i] = chunk2mem(p);
3648     if (i != n_elements-1) {
3649       if (element_size != 0)
3650         size = element_size;
3651       else
3652         size = request2size(sizes[i]);
3653       remainder_size -= size;
3654       set_size_and_pinuse_of_inuse_chunk(m, p, size);
3655       p = chunk_plus_offset(p, size);
3656     }
3657     else { /* the final element absorbs any overallocation slop */
3658       set_size_and_pinuse_of_inuse_chunk(m, p, remainder_size);
3659       break;
3660     }
3661   }
3662
3663 #if DEBUG
3664   if (marray != chunks) {
3665     /* final element must have exactly exhausted chunk */
3666     if (element_size != 0) {
3667       assert(remainder_size == element_size);
3668     }
3669     else {
3670       assert(remainder_size == request2size(sizes[i]));
3671     }
3672     check_inuse_chunk(m, mem2chunk(marray));
3673   }
3674   for (i = 0; i != n_elements; ++i)
3675     check_inuse_chunk(m, mem2chunk(marray[i]));
3676
3677 #endif /* DEBUG */
3678
3679   POSTACTION(m);
3680   return marray;
3681 }
3682
3683 /* Try to free all pointers in the given array.
3684    Note: this could be made faster, by delaying consolidation,
3685    at the price of disabling some user integrity checks, We
3686    still optimize some consolidations by combining adjacent
3687    chunks before freeing, which will occur often if allocated
3688    with ialloc or the array is sorted.
3689 */
3690 static size_t internal_bulk_free(mstate m, void* array[], size_t nelem) {
3691   size_t unfreed = 0;
3692   if (!PREACTION(m)) {
3693     void** a;
3694     void** fence = &(array[nelem]);
3695     for (a = array; a != fence; ++a) {
3696       void* mem = *a;
3697       if (mem != 0) {
3698         mchunkptr p = mem2chunk(mem);
3699         size_t psize = chunksize(p);
3700 #if FOOTERS
3701         if (get_mstate_for(p) != m) {
3702           ++unfreed;
3703           continue;
3704         }
3705 #endif
3706         check_inuse_chunk(m, p);
3707         *a = 0;
3708         if (RTCHECK(ok_address(m, p) && ok_inuse(p))) {
3709           void ** b = a + 1; /* try to merge with next chunk */
3710           mchunkptr next = next_chunk(p);
3711           if (b != fence && *b == chunk2mem(next)) {
3712             size_t newsize = chunksize(next) + psize;
3713             set_inuse(m, p, newsize);
3714             *b = chunk2mem(p);
3715           }
3716           else
3717             dispose_chunk(m, p, psize);
3718         }
3719         else {
3720           CORRUPTION_ERROR_ACTION(m);
3721           break;
3722         }
3723       }
3724     }
3725     if (should_trim(m, m->topsize))
3726       sys_trim(m, 0);
3727     POSTACTION(m);
3728   }
3729   return unfreed;
3730 }
3731
3732 /* Traversal */
3733 #if MALLOC_INSPECT_ALL
3734 static void internal_inspect_all(mstate m,
3735                                  void(*handler)(void *start,
3736                                                 void *end,
3737                                                 size_t used_bytes,
3738                                                 void* callback_arg),
3739                                  void* arg) {
3740   if (is_initialized(m)) {
3741     mchunkptr top = m->top;
3742     msegmentptr s;
3743     for (s = &m->seg; s != 0; s = s->next) {
3744       mchunkptr q = align_as_chunk(s->base);
3745       while (segment_holds(s, q) && q->head != FENCEPOST_HEAD) {
3746         mchunkptr next = next_chunk(q);
3747         size_t sz = chunksize(q);
3748         size_t used;
3749         void* start;
3750         if (is_inuse(q)) {
3751           used = sz - CHUNK_OVERHEAD; /* must not be mmapped */
3752           start = chunk2mem(q);
3753         }
3754         else {
3755           used = 0;
3756           if (is_small(sz)) {     /* offset by possible bookkeeping */
3757             start = (void*)((char*)q + sizeof(struct malloc_chunk));
3758           }
3759           else {
3760             start = (void*)((char*)q + sizeof(struct malloc_tree_chunk));
3761           }
3762         }
3763         if (start < (void*)next)  /* skip if all space is bookkeeping */
3764           handler(start, next, used, arg);
3765         if (q == top)
3766           break;
3767         q = next;
3768       }
3769     }
3770   }
3771 }
3772 #endif /* MALLOC_INSPECT_ALL */
3773
3774 /* ------------------ Exported realloc, memalign, etc -------------------- */
3775
3776 #if !ONLY_MSPACES
3777
3778 void* dlrealloc(void* oldmem, size_t bytes) {
3779   void* mem = 0;
3780   if (oldmem == 0) {
3781     mem = dlmalloc(bytes);
3782   }
3783   else if (bytes >= MAX_REQUEST) {
3784     MALLOC_FAILURE_ACTION;
3785   }
3786 #ifdef REALLOC_ZERO_BYTES_FREES
3787   else if (bytes == 0) {
3788     dlfree(oldmem);
3789   }
3790 #endif /* REALLOC_ZERO_BYTES_FREES */
3791   else {
3792     size_t nb = request2size(bytes);
3793     mchunkptr oldp = mem2chunk(oldmem);
3794 #if ! FOOTERS
3795     mstate m = gm;
3796 #else /* FOOTERS */
3797     mstate m = get_mstate_for(oldp);
3798     if (!ok_magic(m)) {
3799       USAGE_ERROR_ACTION(m, oldmem);
3800       return 0;
3801     }
3802 #endif /* FOOTERS */
3803     if (!PREACTION(m)) {
3804       mchunkptr newp = try_realloc_chunk(m, oldp, nb, 1);
3805       POSTACTION(m);
3806       if (newp != 0) {
3807         check_inuse_chunk(m, newp);
3808         mem = chunk2mem(newp);
3809       }
3810       else {
3811         mem = internal_malloc(m, bytes);
3812         if (mem != 0) {
3813           size_t oc = chunksize(oldp) - overhead_for(oldp);
3814           memcpy(mem, oldmem, (oc < bytes)? oc : bytes);
3815           internal_free(m, oldmem);
3816         }
3817       }
3818     }
3819   }
3820   return mem;
3821 }
3822
3823 void* dlrealloc_in_place(void* oldmem, size_t bytes) {
3824   void* mem = 0;
3825   if (oldmem != 0) {
3826     if (bytes >= MAX_REQUEST) {
3827       MALLOC_FAILURE_ACTION;
3828     }
3829     else {
3830       size_t nb = request2size(bytes);
3831       mchunkptr oldp = mem2chunk(oldmem);
3832 #if ! FOOTERS
3833       mstate m = gm;
3834 #else /* FOOTERS */
3835       mstate m = get_mstate_for(oldp);
3836       if (!ok_magic(m)) {
3837         USAGE_ERROR_ACTION(m, oldmem);
3838         return 0;
3839       }
3840 #endif /* FOOTERS */
3841       if (!PREACTION(m)) {
3842         mchunkptr newp = try_realloc_chunk(m, oldp, nb, 0);
3843         POSTACTION(m);
3844         if (newp == oldp) {
3845           check_inuse_chunk(m, newp);
3846           mem = oldmem;
3847         }
3848       }
3849     }
3850   }
3851   return mem;
3852 }
3853
3854 void* dlmemalign(size_t alignment, size_t bytes) {
3855   if (alignment <= MALLOC_ALIGNMENT) {
3856     return dlmalloc(bytes);
3857   }
3858   return internal_memalign(gm, alignment, bytes);
3859 }
3860
3861 int dlposix_memalign(void** pp, size_t alignment, size_t bytes) {
3862   void* mem = 0;
3863   if (alignment == MALLOC_ALIGNMENT)
3864     mem = dlmalloc(bytes);
3865   else {
3866     size_t d = alignment / sizeof(void*);
3867     size_t r = alignment % sizeof(void*);
3868     if (r != 0 || d == 0 || (d & (d-SIZE_T_ONE)) != 0)
3869       return EINVAL;
3870     else if (bytes <= MAX_REQUEST - alignment) {
3871       if (alignment <  MIN_CHUNK_SIZE)
3872         alignment = MIN_CHUNK_SIZE;
3873       mem = internal_memalign(gm, alignment, bytes);
3874     }
3875   }
3876   if (mem == 0)
3877     return ENOMEM;
3878   else {
3879     *pp = mem;
3880     return 0;
3881   }
3882 }
3883
3884 void* dlvalloc(size_t bytes) {
3885   size_t pagesz;
3886   ensure_initialization();
3887   pagesz = mparams.page_size;
3888   return dlmemalign(pagesz, bytes);
3889 }
3890
3891 void* dlpvalloc(size_t bytes) {
3892   size_t pagesz;
3893   ensure_initialization();
3894   pagesz = mparams.page_size;
3895   return dlmemalign(pagesz, (bytes + pagesz - SIZE_T_ONE) & ~(pagesz - SIZE_T_ONE));
3896 }
3897
3898 void** dlindependent_calloc(size_t n_elements, size_t elem_size,
3899                             void* chunks[]) {
3900   size_t sz = elem_size; /* serves as 1-element array */
3901   return ialloc(gm, n_elements, &sz, 3, chunks);
3902 }
3903
3904 void** dlindependent_comalloc(size_t n_elements, size_t sizes[],
3905                               void* chunks[]) {
3906   return ialloc(gm, n_elements, sizes, 0, chunks);
3907 }
3908
3909 size_t dlbulk_free(void* array[], size_t nelem) {
3910   return internal_bulk_free(gm, array, nelem);
3911 }
3912
3913 #if MALLOC_INSPECT_ALL
3914 void dlmalloc_inspect_all(void(*handler)(void *start,
3915                                          void *end,
3916                                          size_t used_bytes,
3917                                          void* callback_arg),
3918                           void* arg) {
3919   ensure_initialization();
3920   if (!PREACTION(gm)) {
3921     internal_inspect_all(gm, handler, arg);
3922     POSTACTION(gm);
3923   }
3924 }
3925 #endif /* MALLOC_INSPECT_ALL */
3926
3927 int dlmalloc_trim(size_t pad) {
3928   int result = 0;
3929   ensure_initialization();
3930   if (!PREACTION(gm)) {
3931     result = sys_trim(gm, pad);
3932     POSTACTION(gm);
3933   }
3934   return result;
3935 }
3936
3937 size_t dlmalloc_footprint(void) {
3938   return gm->footprint;
3939 }
3940
3941 size_t dlmalloc_max_footprint(void) {
3942   return gm->max_footprint;
3943 }
3944
3945 size_t dlmalloc_footprint_limit(void) {
3946   size_t maf = gm->footprint_limit;
3947   return maf == 0 ? MAX_SIZE_T : maf;
3948 }
3949
3950 size_t dlmalloc_set_footprint_limit(size_t bytes) {
3951   size_t result;  /* invert sense of 0 */
3952   if (bytes == 0)
3953     result = granularity_align(1); /* Use minimal size */
3954   if (bytes == MAX_SIZE_T)
3955     result = 0;                    /* disable */
3956   else
3957     result = granularity_align(bytes);
3958   return gm->footprint_limit = result;
3959 }
3960
3961 #if !NO_MALLINFO
3962 struct mallinfo dlmallinfo(void) {
3963   return internal_mallinfo(gm);
3964 }
3965 #endif /* NO_MALLINFO */
3966
3967 #if !NO_MALLOC_STATS
3968 void dlmalloc_stats() {
3969   internal_malloc_stats(gm);
3970 }
3971 #endif /* NO_MALLOC_STATS */
3972
3973 int dlmallopt(int param_number, int value) {
3974   return change_mparam(param_number, value);
3975 }
3976
3977 size_t dlmalloc_usable_size(void* mem) {
3978   if (mem != 0) {
3979     mchunkptr p = mem2chunk(mem);
3980     if (is_inuse(p))
3981       return chunksize(p) - overhead_for(p);
3982   }
3983   return 0;
3984 }
3985
3986 #endif /* !ONLY_MSPACES */
3987
3988 /* ----------------------------- user mspaces ---------------------------- */
3989
3990 #if MSPACES
3991
3992 static mstate init_user_mstate(char* tbase, size_t tsize) {
3993   size_t msize = pad_request(sizeof(struct malloc_state));
3994   mchunkptr mn;
3995   mchunkptr msp = align_as_chunk(tbase);
3996   mstate m = (mstate)(chunk2mem(msp));
3997   memset(m, 0, msize);
3998   (void)INITIAL_LOCK(&m->mutex);
3999   msp->head = (msize|INUSE_BITS);
4000   m->seg.base = m->least_addr = tbase;
4001   m->seg.size = m->footprint = m->max_footprint = tsize;
4002   m->magic = mparams.magic;
4003   m->release_checks = MAX_RELEASE_CHECK_RATE;
4004   m->mflags = mparams.default_mflags;
4005   m->extp = 0;
4006   m->exts = 0;
4007   disable_contiguous(m);
4008   init_bins(m);
4009   mn = next_chunk(mem2chunk(m));
4010   init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) - TOP_FOOT_SIZE);
4011   check_top_chunk(m, m->top);
4012   return m;
4013 }
4014
4015 mspace create_mspace(size_t capacity, int locked) {
4016   mstate m = 0;
4017   size_t msize;
4018   ensure_initialization();
4019   msize = pad_request(sizeof(struct malloc_state));
4020   if (capacity < (size_t) -(msize + TOP_FOOT_SIZE + mparams.page_size)) {
4021     size_t rs = ((capacity == 0)? mparams.granularity :
4022                  (capacity + TOP_FOOT_SIZE + msize));
4023     size_t tsize = granularity_align(rs);
4024     char* tbase = (char*)(CALL_MMAP(tsize));
4025     if (tbase != CMFAIL) {
4026       m = init_user_mstate(tbase, tsize);
4027       m->seg.sflags = USE_MMAP_BIT;
4028       set_lock(m, locked);
4029     }
4030   }
4031   return (mspace)m;
4032 }
4033
4034 mspace create_mspace_with_base(void* base, size_t capacity, int locked) {
4035   mstate m = 0;
4036   size_t msize;
4037   ensure_initialization();
4038   msize = pad_request(sizeof(struct malloc_state));
4039   if (capacity > msize + TOP_FOOT_SIZE &&
4040       capacity < (size_t) -(msize + TOP_FOOT_SIZE + mparams.page_size)) {
4041     m = init_user_mstate((char*)base, capacity);
4042     m->seg.sflags = EXTERN_BIT;
4043     set_lock(m, locked);
4044   }
4045   return (mspace)m;
4046 }
4047
4048 int mspace_track_large_chunks(mspace msp, int enable) {
4049   int ret = 0;
4050   mstate ms = (mstate)msp;
4051   if (!PREACTION(ms)) {
4052     if (!use_mmap(ms)) {
4053       ret = 1;
4054     }
4055     if (!enable) {
4056       enable_mmap(ms);
4057     } else {
4058       disable_mmap(ms);
4059     }
4060     POSTACTION(ms);
4061   }
4062   return ret;
4063 }
4064
4065 size_t destroy_mspace(mspace msp) {
4066   size_t freed = 0;
4067   mstate ms = (mstate)msp;
4068   if (ok_magic(ms)) {
4069     msegmentptr sp = &ms->seg;
4070     (void)DESTROY_LOCK(&ms->mutex); /* destroy before unmapped */
4071     while (sp != 0) {
4072       char* base = sp->base;
4073       size_t size = sp->size;
4074       flag_t flag = sp->sflags;
4075       (void)base; /* placate people compiling -Wunused-variable */
4076       sp = sp->next;
4077       if ((flag & USE_MMAP_BIT) && !(flag & EXTERN_BIT) &&
4078           CALL_MUNMAP(base, size) == 0)
4079         freed += size;
4080     }
4081   }
4082   else {
4083     USAGE_ERROR_ACTION(ms,ms);
4084   }
4085   return freed;
4086 }
4087
4088 void mspace_get_address_and_size (mspace msp, unsigned long long *addrp,
4089                                   unsigned long long *sizep)
4090 {
4091   mstate ms;
4092   msegment *this_seg;
4093
4094   ms = (mstate)msp;
4095   this_seg = &ms->seg;
4096
4097   *addrp = (unsigned long long) this_seg->base;
4098   *sizep = this_seg->size;
4099 }
4100
4101 int mspace_is_heap_object (mspace msp, void *p)
4102 {
4103   msegment *this_seg;
4104   char *pp, *base;
4105   mstate ms;
4106
4107   ms = (mstate)msp;
4108
4109   this_seg = &ms->seg;
4110   pp = (char *) p;
4111
4112   while (this_seg)
4113     {
4114       base = this_seg->base;
4115       if (pp >= base && pp < (base + this_seg->size))
4116         return 1;
4117       this_seg = this_seg->next;
4118     }
4119   return 0;
4120 }
4121
4122 void *mspace_least_addr (mspace msp)
4123 {
4124   mstate ms = (mstate) msp;
4125   return (void *) ms->least_addr;
4126 }
4127
4128 void mspace_disable_expand (mspace msp)
4129 {
4130   mstate ms = (mstate)msp;
4131
4132   disable_expand (ms);
4133 }
4134
4135 int mspace_enable_disable_trace (mspace msp, int enable)
4136 {
4137   mstate ms = (mstate)msp;
4138   int was_enabled = 0;
4139
4140   if (use_trace(ms))
4141     was_enabled = 1;
4142
4143   if (enable)
4144     enable_trace (ms);
4145   else
4146     disable_trace (ms);
4147
4148   return (was_enabled);
4149 }
4150
4151 void* mspace_get_aligned (mspace msp,
4152                           unsigned long long n_user_data_bytes,
4153                           unsigned long long align,
4154                           unsigned long long align_offset) {
4155   char *rv;
4156   unsigned long long searchp;
4157   unsigned *wwp;                /* "where's Waldo" pointer */
4158   mstate ms = (mstate)msp;
4159
4160   /*
4161    * Allocate space for the "Where's Waldo?" pointer
4162    * the base of the dlmalloc object
4163    */
4164   n_user_data_bytes += sizeof(unsigned);
4165
4166   /*
4167    * Alignment requests less than the size of an mmx vector are ignored
4168    */
4169   if (align < 16) {
4170     rv = mspace_malloc (msp, n_user_data_bytes);
4171     if (rv == 0)
4172         return rv;
4173
4174     if (use_trace(ms)) {
4175       mchunkptr p  = mem2chunk(rv);
4176       size_t psize = chunksize(p);
4177
4178       mheap_get_trace ((u64)rv + sizeof (unsigned), psize);
4179     }
4180
4181     wwp = (unsigned *)rv;
4182     *wwp = 0;
4183     rv += sizeof (unsigned);
4184
4185     return rv;
4186   }
4187
4188   /*
4189    * Alignment requests greater than 4K must be at offset zero,
4190    * and must be freed using mspace_free_no_offset - or never freed -
4191    * since the "Where's Waldo?" pointer would waste too much space.
4192    *
4193    * Waldo is the address of the chunk of memory returned by mspace_malloc,
4194    * which we need later to call mspace_free...
4195    */
4196   if (align > 4<<10 || align_offset == ~0ULL) {
4197     n_user_data_bytes -= sizeof(unsigned);
4198     assert(align_offset == 0);
4199     rv = internal_memalign(ms, (size_t)align, n_user_data_bytes);
4200
4201     /* Trace the allocation */
4202     if (rv && use_trace(ms)) {
4203       mchunkptr p  = mem2chunk(rv);
4204       size_t psize = chunksize(p);
4205       mheap_get_trace ((u64)rv, psize);
4206     }
4207     return rv;
4208   }
4209
4210   align = clib_max (align, MALLOC_ALIGNMENT);
4211   align = max_pow2 (align);
4212
4213   /* Correct align offset to be smaller than alignment. */
4214   align_offset &= (align - 1);
4215
4216   n_user_data_bytes += align;
4217   rv = mspace_malloc (msp, n_user_data_bytes);
4218
4219   if (rv == 0)
4220       return rv;
4221
4222   /* Honor the alignment request */
4223   searchp = (unsigned long long)(rv + sizeof (unsigned));
4224
4225 #if 0  /* this is the idea... */
4226   while ((searchp + align_offset) % align)
4227     searchp++;
4228 #endif
4229
4230   {
4231     unsigned long long where_now, delta;
4232
4233     where_now = (searchp + align_offset) % align;
4234     delta = align - where_now;
4235
4236     searchp += delta;
4237   }
4238
4239   wwp = (unsigned *)(searchp - sizeof(unsigned));
4240   *wwp = (searchp - (((unsigned long long) rv) + sizeof (*wwp)));
4241   assert (*wwp < align);
4242
4243   if (use_trace(ms)) {
4244     mchunkptr p  = mem2chunk(rv);
4245     size_t psize = chunksize(p);
4246     mheap_get_trace ((u64)rv, psize);
4247   }
4248   return (void *) searchp;
4249 }
4250
4251 void mspace_put (mspace msp, void *p_arg)
4252 {
4253   char *object_header;
4254   unsigned *wwp;
4255   mstate ms = (mstate)msp;
4256
4257   /* Find the object header delta */
4258   wwp = (unsigned *)p_arg;
4259   wwp --;
4260
4261   /* Recover the dlmalloc object pointer */
4262   object_header = (char *)wwp;
4263   object_header -= *wwp;
4264
4265   /* Tracing (if enabled) */
4266   if (use_trace(ms))
4267     {
4268       mchunkptr p  = mem2chunk(object_header);
4269       size_t psize = chunksize(p);
4270
4271       mheap_put_trace ((u64)p_arg, psize);
4272     }
4273
4274   /* And free it... */
4275   mspace_free (msp, object_header);
4276 }
4277
4278 void mspace_put_no_offset (mspace msp, void *p_arg)
4279 {
4280   mstate ms = (mstate)msp;
4281
4282   if (use_trace(ms))
4283     {
4284       mchunkptr p  = mem2chunk(p_arg);
4285       size_t psize = chunksize(p);
4286
4287       mheap_put_trace ((u64)p_arg, psize);
4288     }
4289   mspace_free (msp, p_arg);
4290 }
4291
4292 size_t mspace_usable_size_with_delta (const void *p)
4293 {
4294   size_t usable_size;
4295   char *object_header;
4296   unsigned *wwp;
4297
4298   /* Find the object header delta */
4299   wwp = (unsigned *)p;
4300   wwp --;
4301
4302   /* Recover the dlmalloc object pointer */
4303   object_header = (char *)wwp;
4304   object_header -= *wwp;
4305
4306   usable_size = mspace_usable_size (object_header);
4307   /* account for the offset and the size of the offset... */
4308   usable_size -= (*wwp + sizeof (*wwp));
4309   return usable_size;
4310 }
4311
4312 /*
4313   mspace versions of routines are near-clones of the global
4314   versions. This is not so nice but better than the alternatives.
4315 */
4316
4317 void* mspace_malloc(mspace msp, size_t bytes) {
4318   mstate ms = (mstate)msp;
4319   if (!ok_magic(ms)) {
4320     USAGE_ERROR_ACTION(ms,ms);
4321     return 0;
4322   }
4323   if (!PREACTION(ms)) {
4324     void* mem;
4325     size_t nb;
4326     if (bytes <= MAX_SMALL_REQUEST) {
4327       bindex_t idx;
4328       binmap_t smallbits;
4329       nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes);
4330       idx = small_index(nb);
4331       smallbits = ms->smallmap >> idx;
4332
4333       if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */
4334         mchunkptr b, p;
4335         idx += ~smallbits & 1;       /* Uses next bin if idx empty */
4336         b = smallbin_at(ms, idx);
4337         p = b->fd;
4338         assert(chunksize(p) == small_index2size(idx));
4339         unlink_first_small_chunk(ms, b, p, idx);
4340         set_inuse_and_pinuse(ms, p, small_index2size(idx));
4341         mem = chunk2mem(p);
4342         check_malloced_chunk(ms, mem, nb);
4343         goto postaction;
4344       }
4345
4346       else if (nb > ms->dvsize) {
4347         if (smallbits != 0) { /* Use chunk in next nonempty smallbin */
4348           mchunkptr b, p, r;
4349           size_t rsize;
4350           bindex_t i;
4351           binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));
4352           binmap_t leastbit = least_bit(leftbits);
4353           compute_bit2idx(leastbit, i);
4354           b = smallbin_at(ms, i);
4355           p = b->fd;
4356           assert(chunksize(p) == small_index2size(i));
4357           unlink_first_small_chunk(ms, b, p, i);
4358           rsize = small_index2size(i) - nb;
4359           /* Fit here cannot be remainderless if 4byte sizes */
4360           if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE)
4361             set_inuse_and_pinuse(ms, p, small_index2size(i));
4362           else {
4363             set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
4364             r = chunk_plus_offset(p, nb);
4365             set_size_and_pinuse_of_free_chunk(r, rsize);
4366             replace_dv(ms, r, rsize);
4367           }
4368           mem = chunk2mem(p);
4369           check_malloced_chunk(ms, mem, nb);
4370           goto postaction;
4371         }
4372
4373         else if (ms->treemap != 0 && (mem = tmalloc_small(ms, nb)) != 0) {
4374           check_malloced_chunk(ms, mem, nb);
4375           goto postaction;
4376         }
4377       }
4378     }
4379     else if (bytes >= MAX_REQUEST)
4380       nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */
4381     else {
4382       nb = pad_request(bytes);
4383       if (ms->treemap != 0 && (mem = tmalloc_large(ms, nb)) != 0) {
4384         check_malloced_chunk(ms, mem, nb);
4385         goto postaction;
4386       }
4387     }
4388
4389     if (nb <= ms->dvsize) {
4390       size_t rsize = ms->dvsize - nb;
4391       mchunkptr p = ms->dv;
4392       if (rsize >= MIN_CHUNK_SIZE) { /* split dv */
4393         mchunkptr r = ms->dv = chunk_plus_offset(p, nb);
4394         ms->dvsize = rsize;
4395         set_size_and_pinuse_of_free_chunk(r, rsize);
4396         set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
4397       }
4398       else { /* exhaust dv */
4399         size_t dvs = ms->dvsize;
4400         ms->dvsize = 0;
4401         ms->dv = 0;
4402         set_inuse_and_pinuse(ms, p, dvs);
4403       }
4404       mem = chunk2mem(p);
4405       check_malloced_chunk(ms, mem, nb);
4406       goto postaction;
4407     }
4408
4409     else if (nb < ms->topsize) { /* Split top */
4410       size_t rsize = ms->topsize -= nb;
4411       mchunkptr p = ms->top;
4412       mchunkptr r = ms->top = chunk_plus_offset(p, nb);
4413       r->head = rsize | PINUSE_BIT;
4414       set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
4415       mem = chunk2mem(p);
4416       check_top_chunk(ms, ms->top);
4417       check_malloced_chunk(ms, mem, nb);
4418       goto postaction;
4419     }
4420
4421     mem = sys_alloc(ms, nb);
4422
4423   postaction:
4424     POSTACTION(ms);
4425     return mem;
4426   }
4427
4428   return 0;
4429 }
4430
4431 void mspace_free(mspace msp, void* mem) {
4432   if (mem != 0) {
4433     mchunkptr p  = mem2chunk(mem);
4434 #if FOOTERS
4435     mstate fm = get_mstate_for(p);
4436     (void)msp; /* placate people compiling -Wunused */
4437 #else /* FOOTERS */
4438     mstate fm = (mstate)msp;
4439 #endif /* FOOTERS */
4440     if (!ok_magic(fm)) {
4441       USAGE_ERROR_ACTION(fm, p);
4442       return;
4443     }
4444     if (!PREACTION(fm)) {
4445       check_inuse_chunk(fm, p);
4446       if (RTCHECK(ok_address(fm, p) && ok_inuse(p))) {
4447         size_t psize = chunksize(p);
4448         mchunkptr next = chunk_plus_offset(p, psize);
4449         if (!pinuse(p)) {
4450           size_t prevsize = p->prev_foot;
4451           if (is_mmapped(p)) {
4452             psize += prevsize + MMAP_FOOT_PAD;
4453             if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)
4454               fm->footprint -= psize;
4455             goto postaction;
4456           }
4457           else {
4458             mchunkptr prev = chunk_minus_offset(p, prevsize);
4459             psize += prevsize;
4460             p = prev;
4461             if (RTCHECK(ok_address(fm, prev))) { /* consolidate backward */
4462               if (p != fm->dv) {
4463                 unlink_chunk(fm, p, prevsize);
4464               }
4465               else if ((next->head & INUSE_BITS) == INUSE_BITS) {
4466                 fm->dvsize = psize;
4467                 set_free_with_pinuse(p, psize, next);
4468                 goto postaction;
4469               }
4470             }
4471             else
4472               goto erroraction;
4473           }
4474         }
4475
4476         if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) {
4477           if (!cinuse(next)) {  /* consolidate forward */
4478             if (next == fm->top) {
4479               size_t tsize = fm->topsize += psize;
4480               fm->top = p;
4481               p->head = tsize | PINUSE_BIT;
4482               if (p == fm->dv) {
4483                 fm->dv = 0;
4484                 fm->dvsize = 0;
4485               }
4486               if (should_trim(fm, tsize))
4487                 sys_trim(fm, 0);
4488               goto postaction;
4489             }
4490             else if (next == fm->dv) {
4491               size_t dsize = fm->dvsize += psize;
4492               fm->dv = p;
4493               set_size_and_pinuse_of_free_chunk(p, dsize);
4494               goto postaction;
4495             }
4496             else {
4497               size_t nsize = chunksize(next);
4498               psize += nsize;
4499               unlink_chunk(fm, next, nsize);
4500               set_size_and_pinuse_of_free_chunk(p, psize);
4501               if (p == fm->dv) {
4502                 fm->dvsize = psize;
4503                 goto postaction;
4504               }
4505             }
4506           }
4507           else
4508             set_free_with_pinuse(p, psize, next);
4509
4510           if (is_small(psize)) {
4511             insert_small_chunk(fm, p, psize);
4512             check_free_chunk(fm, p);
4513           }
4514           else {
4515             tchunkptr tp = (tchunkptr)p;
4516             insert_large_chunk(fm, tp, psize);
4517             check_free_chunk(fm, p);
4518             if (--fm->release_checks == 0)
4519               release_unused_segments(fm);
4520           }
4521           goto postaction;
4522         }
4523       }
4524     erroraction:
4525       USAGE_ERROR_ACTION(fm, p);
4526     postaction:
4527       POSTACTION(fm);
4528     }
4529   }
4530 }
4531
4532 void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size) {
4533   void* mem;
4534   size_t req = 0;
4535   mstate ms = (mstate)msp;
4536   if (!ok_magic(ms)) {
4537     USAGE_ERROR_ACTION(ms,ms);
4538     return 0;
4539   }
4540   if (n_elements != 0) {
4541     req = n_elements * elem_size;
4542     if (((n_elements | elem_size) & ~(size_t)0xffff) &&
4543         (req / n_elements != elem_size))
4544       req = MAX_SIZE_T; /* force downstream failure on overflow */
4545   }
4546   mem = internal_malloc(ms, req);
4547   if (mem != 0 && calloc_must_clear(mem2chunk(mem)))
4548     memset(mem, 0, req);
4549   return mem;
4550 }
4551
4552 void* mspace_realloc(mspace msp, void* oldmem, size_t bytes) {
4553   void* mem = 0;
4554   if (oldmem == 0) {
4555     mem = mspace_malloc(msp, bytes);
4556   }
4557   else if (bytes >= MAX_REQUEST) {
4558     MALLOC_FAILURE_ACTION;
4559   }
4560 #ifdef REALLOC_ZERO_BYTES_FREES
4561   else if (bytes == 0) {
4562     mspace_free(msp, oldmem);
4563   }
4564 #endif /* REALLOC_ZERO_BYTES_FREES */
4565   else {
4566     size_t nb = request2size(bytes);
4567     mchunkptr oldp = mem2chunk(oldmem);
4568 #if ! FOOTERS
4569     mstate m = (mstate)msp;
4570 #else /* FOOTERS */
4571     mstate m = get_mstate_for(oldp);
4572     if (!ok_magic(m)) {
4573       USAGE_ERROR_ACTION(m, oldmem);
4574       return 0;
4575     }
4576 #endif /* FOOTERS */
4577     if (!PREACTION(m)) {
4578       mchunkptr newp = try_realloc_chunk(m, oldp, nb, 1);
4579       POSTACTION(m);
4580       if (newp != 0) {
4581         check_inuse_chunk(m, newp);
4582         mem = chunk2mem(newp);
4583       }
4584       else {
4585         mem = mspace_malloc(m, bytes);
4586         if (mem != 0) {
4587           size_t oc = chunksize(oldp) - overhead_for(oldp);
4588           memcpy(mem, oldmem, (oc < bytes)? oc : bytes);
4589           mspace_free(m, oldmem);
4590         }
4591       }
4592     }
4593   }
4594   return mem;
4595 }
4596
4597 void* mspace_realloc_in_place(mspace msp, void* oldmem, size_t bytes) {
4598   void* mem = 0;
4599   if (oldmem != 0) {
4600     if (bytes >= MAX_REQUEST) {
4601       MALLOC_FAILURE_ACTION;
4602     }
4603     else {
4604       size_t nb = request2size(bytes);
4605       mchunkptr oldp = mem2chunk(oldmem);
4606 #if ! FOOTERS
4607       mstate m = (mstate)msp;
4608 #else /* FOOTERS */
4609       mstate m = get_mstate_for(oldp);
4610       (void)msp; /* placate people compiling -Wunused */
4611       if (!ok_magic(m)) {
4612         USAGE_ERROR_ACTION(m, oldmem);
4613         return 0;
4614       }
4615 #endif /* FOOTERS */
4616       if (!PREACTION(m)) {
4617         mchunkptr newp = try_realloc_chunk(m, oldp, nb, 0);
4618         POSTACTION(m);
4619         if (newp == oldp) {
4620           check_inuse_chunk(m, newp);
4621           mem = oldmem;
4622         }
4623       }
4624     }
4625   }
4626   return mem;
4627 }
4628
4629 void* mspace_memalign(mspace msp, size_t alignment, size_t bytes) {
4630   mstate ms = (mstate)msp;
4631   if (!ok_magic(ms)) {
4632     USAGE_ERROR_ACTION(ms,ms);
4633     return 0;
4634   }
4635   if (alignment <= MALLOC_ALIGNMENT)
4636     return mspace_malloc(msp, bytes);
4637   return internal_memalign(ms, alignment, bytes);
4638 }
4639
4640 void** mspace_independent_calloc(mspace msp, size_t n_elements,
4641                                  size_t elem_size, void* chunks[]) {
4642   size_t sz = elem_size; /* serves as 1-element array */
4643   mstate ms = (mstate)msp;
4644   if (!ok_magic(ms)) {
4645     USAGE_ERROR_ACTION(ms,ms);
4646     return 0;
4647   }
4648   return ialloc(ms, n_elements, &sz, 3, chunks);
4649 }
4650
4651 void** mspace_independent_comalloc(mspace msp, size_t n_elements,
4652                                    size_t sizes[], void* chunks[]) {
4653   mstate ms = (mstate)msp;
4654   if (!ok_magic(ms)) {
4655     USAGE_ERROR_ACTION(ms,ms);
4656     return 0;
4657   }
4658   return ialloc(ms, n_elements, sizes, 0, chunks);
4659 }
4660
4661 size_t mspace_bulk_free(mspace msp, void* array[], size_t nelem) {
4662   return internal_bulk_free((mstate)msp, array, nelem);
4663 }
4664
4665 #if MALLOC_INSPECT_ALL
4666 void mspace_inspect_all(mspace msp,
4667                         void(*handler)(void *start,
4668                                        void *end,
4669                                        size_t used_bytes,
4670                                        void* callback_arg),
4671                         void* arg) {
4672   mstate ms = (mstate)msp;
4673   if (ok_magic(ms)) {
4674     if (!PREACTION(ms)) {
4675       internal_inspect_all(ms, handler, arg);
4676       POSTACTION(ms);
4677     }
4678   }
4679   else {
4680     USAGE_ERROR_ACTION(ms,ms);
4681   }
4682 }
4683 #endif /* MALLOC_INSPECT_ALL */
4684
4685 int mspace_trim(mspace msp, size_t pad) {
4686   int result = 0;
4687   mstate ms = (mstate)msp;
4688   if (ok_magic(ms)) {
4689     if (!PREACTION(ms)) {
4690       result = sys_trim(ms, pad);
4691       POSTACTION(ms);
4692     }
4693   }
4694   else {
4695     USAGE_ERROR_ACTION(ms,ms);
4696   }
4697   return result;
4698 }
4699
4700 #if !NO_MALLOC_STATS
4701 void mspace_malloc_stats(mspace msp) {
4702   mstate ms = (mstate)msp;
4703   if (ok_magic(ms)) {
4704     internal_malloc_stats(ms);
4705   }
4706   else {
4707     USAGE_ERROR_ACTION(ms,ms);
4708   }
4709 }
4710 #endif /* NO_MALLOC_STATS */
4711
4712 size_t mspace_footprint(mspace msp) {
4713   size_t result = 0;
4714   mstate ms = (mstate)msp;
4715   if (ok_magic(ms)) {
4716     result = ms->footprint;
4717   }
4718   else {
4719     USAGE_ERROR_ACTION(ms,ms);
4720   }
4721   return result;
4722 }
4723
4724 size_t mspace_max_footprint(mspace msp) {
4725   size_t result = 0;
4726   mstate ms = (mstate)msp;
4727   if (ok_magic(ms)) {
4728     result = ms->max_footprint;
4729   }
4730   else {
4731     USAGE_ERROR_ACTION(ms,ms);
4732   }
4733   return result;
4734 }
4735
4736 size_t mspace_footprint_limit(mspace msp) {
4737   size_t result = 0;
4738   mstate ms = (mstate)msp;
4739   if (ok_magic(ms)) {
4740     size_t maf = ms->footprint_limit;
4741     result = (maf == 0) ? MAX_SIZE_T : maf;
4742   }
4743   else {
4744     USAGE_ERROR_ACTION(ms,ms);
4745   }
4746   return result;
4747 }
4748
4749 size_t mspace_set_footprint_limit(mspace msp, size_t bytes) {
4750   size_t result = 0;
4751   mstate ms = (mstate)msp;
4752   if (ok_magic(ms)) {
4753     if (bytes == 0)
4754       result = granularity_align(1); /* Use minimal size */
4755     if (bytes == MAX_SIZE_T)
4756       result = 0;                    /* disable */
4757     else
4758       result = granularity_align(bytes);
4759     ms->footprint_limit = result;
4760   }
4761   else {
4762     USAGE_ERROR_ACTION(ms,ms);
4763   }
4764   return result;
4765 }
4766
4767 #if !NO_MALLINFO
4768 struct mallinfo mspace_mallinfo(mspace msp) {
4769   mstate ms = (mstate)msp;
4770   if (!ok_magic(ms)) {
4771     USAGE_ERROR_ACTION(ms,ms);
4772   }
4773   return internal_mallinfo(ms);
4774 }
4775 #endif /* NO_MALLINFO */
4776
4777 size_t mspace_usable_size(const void* mem) {
4778   if (mem != 0) {
4779     mchunkptr p = mem2chunk(mem);
4780     if (is_inuse(p))
4781       return chunksize(p) - overhead_for(p);
4782   }
4783   return 0;
4784 }
4785
4786 int mspace_mallopt(int param_number, int value) {
4787   return change_mparam(param_number, value);
4788 }
4789
4790 #endif /* MSPACES */
4791
4792
4793 /* -------------------- Alternative MORECORE functions ------------------- */
4794
4795 /*
4796   Guidelines for creating a custom version of MORECORE:
4797
4798   * For best performance, MORECORE should allocate in multiples of pagesize.
4799   * MORECORE may allocate more memory than requested. (Or even less,
4800       but this will usually result in a malloc failure.)
4801   * MORECORE must not allocate memory when given argument zero, but
4802       instead return one past the end address of memory from previous
4803       nonzero call.
4804   * For best performance, consecutive calls to MORECORE with positive
4805       arguments should return increasing addresses, indicating that
4806       space has been contiguously extended.
4807   * Even though consecutive calls to MORECORE need not return contiguous
4808       addresses, it must be OK for malloc'ed chunks to span multiple
4809       regions in those cases where they do happen to be contiguous.
4810   * MORECORE need not handle negative arguments -- it may instead
4811       just return MFAIL when given negative arguments.
4812       Negative arguments are always multiples of pagesize. MORECORE
4813       must not misinterpret negative args as large positive unsigned
4814       args. You can suppress all such calls from even occurring by defining
4815       MORECORE_CANNOT_TRIM,
4816
4817   As an example alternative MORECORE, here is a custom allocator
4818   kindly contributed for pre-OSX macOS.  It uses virtually but not
4819   necessarily physically contiguous non-paged memory (locked in,
4820   present and won't get swapped out).  You can use it by uncommenting
4821   this section, adding some #includes, and setting up the appropriate
4822   defines above:
4823
4824       #define MORECORE osMoreCore
4825
4826   There is also a shutdown routine that should somehow be called for
4827   cleanup upon program exit.
4828
4829   #define MAX_POOL_ENTRIES 100
4830   #define MINIMUM_MORECORE_SIZE  (64 * 1024U)
4831   static int next_os_pool;
4832   void *our_os_pools[MAX_POOL_ENTRIES];
4833
4834   void *osMoreCore(int size)
4835   {
4836     void *ptr = 0;
4837     static void *sbrk_top = 0;
4838
4839     if (size > 0)
4840     {
4841       if (size < MINIMUM_MORECORE_SIZE)
4842          size = MINIMUM_MORECORE_SIZE;
4843       if (CurrentExecutionLevel() == kTaskLevel)
4844          ptr = PoolAllocateResident(size + RM_PAGE_SIZE, 0);
4845       if (ptr == 0)
4846       {
4847         return (void *) MFAIL;
4848       }
4849       // save ptrs so they can be freed during cleanup
4850       our_os_pools[next_os_pool] = ptr;
4851       next_os_pool++;
4852       ptr = (void *) ((((size_t) ptr) + RM_PAGE_MASK) & ~RM_PAGE_MASK);
4853       sbrk_top = (char *) ptr + size;
4854       return ptr;
4855     }
4856     else if (size < 0)
4857     {
4858       // we don't currently support shrink behavior
4859       return (void *) MFAIL;
4860     }
4861     else
4862     {
4863       return sbrk_top;
4864     }
4865   }
4866
4867   // cleanup any allocated memory pools
4868   // called as last thing before shutting down driver
4869
4870   void osCleanupMem(void)
4871   {
4872     void **ptr;
4873
4874     for (ptr = our_os_pools; ptr < &our_os_pools[MAX_POOL_ENTRIES]; ptr++)
4875       if (*ptr)
4876       {
4877          PoolDeallocate(*ptr);
4878          *ptr = 0;
4879       }
4880   }
4881
4882 */
4883
4884
4885 /* -----------------------------------------------------------------------
4886 History:
4887     v2.8.6 Wed Aug 29 06:57:58 2012  Doug Lea
4888       * fix bad comparison in dlposix_memalign
4889       * don't reuse adjusted asize in sys_alloc
4890       * add LOCK_AT_FORK -- thanks to Kirill Artamonov for the suggestion
4891       * reduce compiler warnings -- thanks to all who reported/suggested these
4892
4893     v2.8.5 Sun May 22 10:26:02 2011  Doug Lea  (dl at gee)
4894       * Always perform unlink checks unless INSECURE
4895       * Add posix_memalign.
4896       * Improve realloc to expand in more cases; expose realloc_in_place.
4897         Thanks to Peter Buhr for the suggestion.
4898       * Add footprint_limit, inspect_all, bulk_free. Thanks
4899         to Barry Hayes and others for the suggestions.
4900       * Internal refactorings to avoid calls while holding locks
4901       * Use non-reentrant locks by default. Thanks to Roland McGrath
4902         for the suggestion.
4903       * Small fixes to mspace_destroy, reset_on_error.
4904       * Various configuration extensions/changes. Thanks
4905          to all who contributed these.
4906
4907     V2.8.4a Thu Apr 28 14:39:43 2011 (dl at gee.cs.oswego.edu)
4908       * Update Creative Commons URL
4909
4910     V2.8.4 Wed May 27 09:56:23 2009  Doug Lea  (dl at gee)
4911       * Use zeros instead of prev foot for is_mmapped
4912       * Add mspace_track_large_chunks; thanks to Jean Brouwers
4913       * Fix set_inuse in internal_realloc; thanks to Jean Brouwers
4914       * Fix insufficient sys_alloc padding when using 16byte alignment
4915       * Fix bad error check in mspace_footprint
4916       * Adaptations for ptmalloc; thanks to Wolfram Gloger.
4917       * Reentrant spin locks; thanks to Earl Chew and others
4918       * Win32 improvements; thanks to Niall Douglas and Earl Chew
4919       * Add NO_SEGMENT_TRAVERSAL and MAX_RELEASE_CHECK_RATE options
4920       * Extension hook in malloc_state
4921       * Various small adjustments to reduce warnings on some compilers
4922       * Various configuration extensions/changes for more platforms. Thanks
4923          to all who contributed these.
4924
4925     V2.8.3 Thu Sep 22 11:16:32 2005  Doug Lea  (dl at gee)
4926       * Add max_footprint functions
4927       * Ensure all appropriate literals are size_t
4928       * Fix conditional compilation problem for some #define settings
4929       * Avoid concatenating segments with the one provided
4930         in create_mspace_with_base
4931       * Rename some variables to avoid compiler shadowing warnings
4932       * Use explicit lock initialization.
4933       * Better handling of sbrk interference.
4934       * Simplify and fix segment insertion, trimming and mspace_destroy
4935       * Reinstate REALLOC_ZERO_BYTES_FREES option from 2.7.x
4936       * Thanks especially to Dennis Flanagan for help on these.
4937
4938     V2.8.2 Sun Jun 12 16:01:10 2005  Doug Lea  (dl at gee)
4939       * Fix memalign brace error.
4940
4941     V2.8.1 Wed Jun  8 16:11:46 2005  Doug Lea  (dl at gee)
4942       * Fix improper #endif nesting in C++
4943       * Add explicit casts needed for C++
4944
4945     V2.8.0 Mon May 30 14:09:02 2005  Doug Lea  (dl at gee)
4946       * Use trees for large bins
4947       * Support mspaces
4948       * Use segments to unify sbrk-based and mmap-based system allocation,
4949         removing need for emulation on most platforms without sbrk.
4950       * Default safety checks
4951       * Optional footer checks. Thanks to William Robertson for the idea.
4952       * Internal code refactoring
4953       * Incorporate suggestions and platform-specific changes.
4954         Thanks to Dennis Flanagan, Colin Plumb, Niall Douglas,
4955         Aaron Bachmann,  Emery Berger, and others.
4956       * Speed up non-fastbin processing enough to remove fastbins.
4957       * Remove useless cfree() to avoid conflicts with other apps.
4958       * Remove internal memcpy, memset. Compilers handle builtins better.
4959       * Remove some options that no one ever used and rename others.
4960
4961     V2.7.2 Sat Aug 17 09:07:30 2002  Doug Lea  (dl at gee)
4962       * Fix malloc_state bitmap array misdeclaration
4963
4964     V2.7.1 Thu Jul 25 10:58:03 2002  Doug Lea  (dl at gee)
4965       * Allow tuning of FIRST_SORTED_BIN_SIZE
4966       * Use PTR_UINT as type for all ptr->int casts. Thanks to John Belmonte.
4967       * Better detection and support for non-contiguousness of MORECORE.
4968         Thanks to Andreas Mueller, Conal Walsh, and Wolfram Gloger
4969       * Bypass most of malloc if no frees. Thanks To Emery Berger.
4970       * Fix freeing of old top non-contiguous chunk im sysmalloc.
4971       * Raised default trim and map thresholds to 256K.
4972       * Fix mmap-related #defines. Thanks to Lubos Lunak.
4973       * Fix copy macros; added LACKS_FCNTL_H. Thanks to Neal Walfield.
4974       * Branch-free bin calculation
4975       * Default trim and mmap thresholds now 256K.
4976
4977     V2.7.0 Sun Mar 11 14:14:06 2001  Doug Lea  (dl at gee)
4978       * Introduce independent_comalloc and independent_calloc.
4979         Thanks to Michael Pachos for motivation and help.
4980       * Make optional .h file available
4981       * Allow > 2GB requests on 32bit systems.
4982       * new WIN32 sbrk, mmap, munmap, lock code from <Walter@GeNeSys-e.de>.
4983         Thanks also to Andreas Mueller <a.mueller at paradatec.de>,
4984         and Anonymous.
4985       * Allow override of MALLOC_ALIGNMENT (Thanks to Ruud Waij for
4986         helping test this.)
4987       * memalign: check alignment arg
4988       * realloc: don't try to shift chunks backwards, since this
4989         leads to  more fragmentation in some programs and doesn't
4990         seem to help in any others.
4991       * Collect all cases in malloc requiring system memory into sysmalloc
4992       * Use mmap as backup to sbrk
4993       * Place all internal state in malloc_state
4994       * Introduce fastbins (although similar to 2.5.1)
4995       * Many minor tunings and cosmetic improvements
4996       * Introduce USE_PUBLIC_MALLOC_WRAPPERS, USE_MALLOC_LOCK
4997       * Introduce MALLOC_FAILURE_ACTION, MORECORE_CONTIGUOUS
4998         Thanks to Tony E. Bennett <tbennett@nvidia.com> and others.
4999       * Include errno.h to support default failure action.
5000
5001     V2.6.6 Sun Dec  5 07:42:19 1999  Doug Lea  (dl at gee)
5002       * return null for negative arguments
5003       * Added Several WIN32 cleanups from Martin C. Fong <mcfong at yahoo.com>
5004          * Add 'LACKS_SYS_PARAM_H' for those systems without 'sys/param.h'
5005           (e.g. WIN32 platforms)
5006          * Cleanup header file inclusion for WIN32 platforms
5007          * Cleanup code to avoid Microsoft Visual C++ compiler complaints
5008          * Add 'USE_DL_PREFIX' to quickly allow co-existence with existing
5009            memory allocation routines
5010          * Set 'malloc_getpagesize' for WIN32 platforms (needs more work)
5011          * Use 'assert' rather than 'ASSERT' in WIN32 code to conform to
5012            usage of 'assert' in non-WIN32 code
5013          * Improve WIN32 'sbrk()' emulation's 'findRegion()' routine to
5014            avoid infinite loop
5015       * Always call 'fREe()' rather than 'free()'
5016
5017     V2.6.5 Wed Jun 17 15:57:31 1998  Doug Lea  (dl at gee)
5018       * Fixed ordering problem with boundary-stamping
5019
5020     V2.6.3 Sun May 19 08:17:58 1996  Doug Lea  (dl at gee)
5021       * Added pvalloc, as recommended by H.J. Liu
5022       * Added 64bit pointer support mainly from Wolfram Gloger
5023       * Added anonymously donated WIN32 sbrk emulation
5024       * Malloc, calloc, getpagesize: add optimizations from Raymond Nijssen
5025       * malloc_extend_top: fix mask error that caused wastage after
5026         foreign sbrks
5027       * Add linux mremap support code from HJ Liu
5028
5029     V2.6.2 Tue Dec  5 06:52:55 1995  Doug Lea  (dl at gee)
5030       * Integrated most documentation with the code.
5031       * Add support for mmap, with help from
5032         Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
5033       * Use last_remainder in more cases.
5034       * Pack bins using idea from  colin@nyx10.cs.du.edu
5035       * Use ordered bins instead of best-fit threshhold
5036       * Eliminate block-local decls to simplify tracing and debugging.
5037       * Support another case of realloc via move into top
5038       * Fix error occuring when initial sbrk_base not word-aligned.
5039       * Rely on page size for units instead of SBRK_UNIT to
5040         avoid surprises about sbrk alignment conventions.
5041       * Add mallinfo, mallopt. Thanks to Raymond Nijssen
5042         (raymond@es.ele.tue.nl) for the suggestion.
5043       * Add `pad' argument to malloc_trim and top_pad mallopt parameter.
5044       * More precautions for cases where other routines call sbrk,
5045         courtesy of Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
5046       * Added macros etc., allowing use in linux libc from
5047         H.J. Lu (hjl@gnu.ai.mit.edu)
5048       * Inverted this history list
5049
5050     V2.6.1 Sat Dec  2 14:10:57 1995  Doug Lea  (dl at gee)
5051       * Re-tuned and fixed to behave more nicely with V2.6.0 changes.
5052       * Removed all preallocation code since under current scheme
5053         the work required to undo bad preallocations exceeds
5054         the work saved in good cases for most test programs.
5055       * No longer use return list or unconsolidated bins since
5056         no scheme using them consistently outperforms those that don't
5057         given above changes.
5058       * Use best fit for very large chunks to prevent some worst-cases.
5059       * Added some support for debugging
5060
5061     V2.6.0 Sat Nov  4 07:05:23 1995  Doug Lea  (dl at gee)
5062       * Removed footers when chunks are in use. Thanks to
5063         Paul Wilson (wilson@cs.texas.edu) for the suggestion.
5064
5065     V2.5.4 Wed Nov  1 07:54:51 1995  Doug Lea  (dl at gee)
5066       * Added malloc_trim, with help from Wolfram Gloger
5067         (wmglo@Dent.MED.Uni-Muenchen.DE).
5068
5069     V2.5.3 Tue Apr 26 10:16:01 1994  Doug Lea  (dl at g)
5070
5071     V2.5.2 Tue Apr  5 16:20:40 1994  Doug Lea  (dl at g)
5072       * realloc: try to expand in both directions
5073       * malloc: swap order of clean-bin strategy;
5074       * realloc: only conditionally expand backwards
5075       * Try not to scavenge used bins
5076       * Use bin counts as a guide to preallocation
5077       * Occasionally bin return list chunks in first scan
5078       * Add a few optimizations from colin@nyx10.cs.du.edu
5079
5080     V2.5.1 Sat Aug 14 15:40:43 1993  Doug Lea  (dl at g)
5081       * faster bin computation & slightly different binning
5082       * merged all consolidations to one part of malloc proper
5083          (eliminating old malloc_find_space & malloc_clean_bin)
5084       * Scan 2 returns chunks (not just 1)
5085       * Propagate failure in realloc if malloc returns 0
5086       * Add stuff to allow compilation on non-ANSI compilers
5087           from kpv@research.att.com
5088
5089     V2.5 Sat Aug  7 07:41:59 1993  Doug Lea  (dl at g.oswego.edu)
5090       * removed potential for odd address access in prev_chunk
5091       * removed dependency on getpagesize.h
5092       * misc cosmetics and a bit more internal documentation
5093       * anticosmetics: mangled names in macros to evade debugger strangeness
5094       * tested on sparc, hp-700, dec-mips, rs6000
5095           with gcc & native cc (hp, dec only) allowing
5096           Detlefs & Zorn comparison study (in SIGPLAN Notices.)
5097
5098     Trial version Fri Aug 28 13:14:29 1992  Doug Lea  (dl at g.oswego.edu)
5099       * Based loosely on libg++-1.2X malloc. (It retains some of the overall
5100          structure of old version,  but most details differ.)
5101
5102 */