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