malloc/arena.c

   1 /* Malloc implementation for multiple threads without lock contention.
   2    Copyright (C) 2001,2002,2003,2004,2005,2006,2007,2009,2010
   3    Free Software Foundation, Inc.
   4    This file is part of the GNU C Library.
   5    Contributed by Wolfram Gloger <wg@malloc.de>, 2001.
   6
   7    The GNU C Library is free software; you can redistribute it and/or
   8    modify it under the terms of the GNU Lesser General Public License as
   9    published by the Free Software Foundation; either version 2.1 of the
  10    License, or (at your option) any later version.
  11
  12    The GNU C Library is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15    Lesser General Public License for more details.
  16
  17    You should have received a copy of the GNU Lesser General Public
  18    License along with the GNU C Library; see the file COPYING.LIB.  If not,
  19    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  20    Boston, MA 02111-1307, USA.  */
  21
  22 #include <stdbool.h>
  23
  24 /* Compile-time constants.  */
  25
  26 #define HEAP_MIN_SIZE (32*1024)
  27 #ifndef HEAP_MAX_SIZE
  28 # ifdef DEFAULT_MMAP_THRESHOLD_MAX
  29 #  define HEAP_MAX_SIZE (2 * DEFAULT_MMAP_THRESHOLD_MAX)
  30 # else
  31 #  define HEAP_MAX_SIZE (1024*1024) /* must be a power of two */
  32 # endif
  33 #endif
  34
  35 /* HEAP_MIN_SIZE and HEAP_MAX_SIZE limit the size of mmap()ed heaps
  36    that are dynamically created for multi-threaded programs.  The
  37    maximum size must be a power of two, for fast determination of
  38    which heap belongs to a chunk.  It should be much larger than the
  39    mmap threshold, so that requests with a size just below that
  40    threshold can be fulfilled without creating too many heaps.  */
  41
  42
  43 #ifndef THREAD_STATS
  44 #define THREAD_STATS 0
  45 #endif
  46
  47 /* If THREAD_STATS is non-zero, some statistics on mutex locking are
  48    computed.  */
  49
  50 /***************************************************************************/
  51
  52 #define top(ar_ptr) ((ar_ptr)->top)
  53
  54 /* A heap is a single contiguous memory region holding (coalesceable)
  55    malloc_chunks.  It is allocated with mmap() and always starts at an
  56    address aligned to HEAP_MAX_SIZE.  Not used unless compiling with
  57    USE_ARENAS. */
  58
  59 typedef struct _heap_info {
  60   mstate ar_ptr; /* Arena for this heap. */
  61   struct _heap_info *prev; /* Previous heap. */
  62   size_t size;   /* Current size in bytes. */
  63   size_t mprotect_size; /* Size in bytes that has been mprotected
  64                            PROT_READ|PROT_WRITE.  */
  65   /* Make sure the following data is properly aligned, particularly
  66      that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
  67      MALLOC_ALIGNMENT. */
  68   char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];
  69 } heap_info;
  70
  71 /* Get a compile-time error if the heap_info padding is not correct
  72    to make alignment work as expected in sYSMALLOc.  */
  73 extern int sanity_check_heap_info_alignment[(sizeof (heap_info)
  74                                              + 2 * SIZE_SZ) % MALLOC_ALIGNMENT
  75                                             ? -1 : 1];
  76
  77 /* Thread specific data */
  78
  79 static tsd_key_t arena_key;
  80 static mutex_t list_lock;
  81 #ifdef PER_THREAD
  82 static size_t narenas;
  83 static mstate free_list;
  84 #endif
  85
  86 #if THREAD_STATS
  87 static int stat_n_heaps;
  88 #define THREAD_STAT(x) x
  89 #else
  90 #define THREAD_STAT(x) do ; while(0)
  91 #endif
  92
  93 /* Mapped memory in non-main arenas (reliable only for NO_THREADS). */
  94 static unsigned long arena_mem;
  95
  96 /* Already initialized? */
  97 int __malloc_initialized = -1;
  98
  99 /**************************************************************************/
 100
 101 #if USE_ARENAS
 102
 103 /* arena_get() acquires an arena and locks the corresponding mutex.
 104    First, try the one last locked successfully by this thread.  (This
 105    is the common case and handled with a macro for speed.)  Then, loop
 106    once over the circularly linked list of arenas.  If no arena is
 107    readily available, create a new one.  In this latter case, `size'
 108    is just a hint as to how much memory will be required immediately
 109    in the new arena. */
 110
 111 #define arena_get(ptr, size) do { \
 112   arena_lookup(ptr); \
 113   arena_lock(ptr, size); \
 114 } while(0)
 115
 116 #define arena_lookup(ptr) do { \
 117   Void_t *vptr = NULL; \
 118   ptr = (mstate)tsd_getspecific(arena_key, vptr); \
 119 } while(0)
 120
 121 #ifdef PER_THREAD
 122 #define arena_lock(ptr, size) do { \
 123   if(ptr) \
 124     (void)mutex_lock(&ptr->mutex); \
 125   else \
 126     ptr = arena_get2(ptr, (size)); \
 127 } while(0)
 128 #else
 129 #define arena_lock(ptr, size) do { \
 130   if(ptr && !mutex_trylock(&ptr->mutex)) { \
 131     THREAD_STAT(++(ptr->stat_lock_direct)); \
 132   } else \
 133     ptr = arena_get2(ptr, (size)); \
 134 } while(0)
 135 #endif
 136
 137 /* find the heap and corresponding arena for a given ptr */
 138
 139 #define heap_for_ptr(ptr) \
 140  ((heap_info *)((unsigned long)(ptr) & ~(HEAP_MAX_SIZE-1)))
 141 #define arena_for_chunk(ptr) \
 142  (chunk_non_main_arena(ptr) ? heap_for_ptr(ptr)->ar_ptr : &main_arena)
 143
 144 #else /* !USE_ARENAS */
 145
 146 /* There is only one arena, main_arena. */
 147
 148 #if THREAD_STATS
 149 #define arena_get(ar_ptr, sz) do { \
 150   ar_ptr = &main_arena; \
 151   if(!mutex_trylock(&ar_ptr->mutex)) \
 152     ++(ar_ptr->stat_lock_direct); \
 153   else { \
 154     (void)mutex_lock(&ar_ptr->mutex); \
 155     ++(ar_ptr->stat_lock_wait); \
 156   } \
 157 } while(0)
 158 #else
 159 #define arena_get(ar_ptr, sz) do { \
 160   ar_ptr = &main_arena; \
 161   (void)mutex_lock(&ar_ptr->mutex); \
 162 } while(0)
 163 #endif
 164 #define arena_for_chunk(ptr) (&main_arena)
 165
 166 #endif /* USE_ARENAS */
 167
 168 /**************************************************************************/
 169
 170 #ifndef NO_THREADS
 171
 172 /* atfork support.  */
 173
 174 static __malloc_ptr_t (*save_malloc_hook) (size_t __size,
 175                                            __const __malloc_ptr_t);
 176 # if !defined _LIBC || (defined SHARED && !USE___THREAD)
 177 static __malloc_ptr_t (*save_memalign_hook) (size_t __align, size_t __size,
 178                                              __const __malloc_ptr_t);
 179 # endif
 180 static void           (*save_free_hook) (__malloc_ptr_t __ptr,
 181                                          __const __malloc_ptr_t);
 182 static Void_t*        save_arena;
 183
 184 #ifdef ATFORK_MEM
 185 ATFORK_MEM;
 186 #endif
 187
 188 /* Magic value for the thread-specific arena pointer when
 189    malloc_atfork() is in use.  */
 190
 191 #define ATFORK_ARENA_PTR ((Void_t*)-1)
 192
 193 /* The following hooks are used while the `atfork' handling mechanism
 194    is active. */
 195
 196 static Void_t*
 197 malloc_atfork(size_t sz, const Void_t *caller)
 198 {
 199   Void_t *vptr = NULL;
 200   Void_t *victim;
 201
 202   tsd_getspecific(arena_key, vptr);
 203   if(vptr == ATFORK_ARENA_PTR) {
 204     /* We are the only thread that may allocate at all.  */
 205     if(save_malloc_hook != malloc_check) {
 206       return _int_malloc(&main_arena, sz);
 207     } else {
 208       if(top_check()<0)
 209         return 0;
 210       victim = _int_malloc(&main_arena, sz+1);
 211       return mem2mem_check(victim, sz);
 212     }
 213   } else {
 214     /* Suspend the thread until the `atfork' handlers have completed.
 215        By that time, the hooks will have been reset as well, so that
 216        mALLOc() can be used again. */
 217     (void)mutex_lock(&list_lock);
 218     (void)mutex_unlock(&list_lock);
 219     return public_mALLOc(sz);
 220   }
 221 }
 222
 223 static void
 224 free_atfork(Void_t* mem, const Void_t *caller)
 225 {
 226   Void_t *vptr = NULL;
 227   mstate ar_ptr;
 228   mchunkptr p;                          /* chunk corresponding to mem */
 229
 230   if (mem == 0)                              /* free(0) has no effect */
 231     return;
 232
 233   p = mem2chunk(mem);         /* do not bother to replicate free_check here */
 234
 235 #if HAVE_MMAP
 236   if (chunk_is_mmapped(p))                       /* release mmapped memory. */
 237   {
 238     munmap_chunk(p);
 239     return;
 240   }
 241 #endif
 242
 243 #ifdef ATOMIC_FASTBINS
 244   ar_ptr = arena_for_chunk(p);
 245   tsd_getspecific(arena_key, vptr);
 246   _int_free(ar_ptr, p, vptr == ATFORK_ARENA_PTR);
 247 #else
 248   ar_ptr = arena_for_chunk(p);
 249   tsd_getspecific(arena_key, vptr);
 250   if(vptr != ATFORK_ARENA_PTR)
 251     (void)mutex_lock(&ar_ptr->mutex);
 252   _int_free(ar_ptr, p);
 253   if(vptr != ATFORK_ARENA_PTR)
 254     (void)mutex_unlock(&ar_ptr->mutex);
 255 #endif
 256 }
 257
 258
 259 /* Counter for number of times the list is locked by the same thread.  */
 260 static unsigned int atfork_recursive_cntr;
 261
 262 /* The following two functions are registered via thread_atfork() to
 263    make sure that the mutexes remain in a consistent state in the
 264    fork()ed version of a thread.  Also adapt the malloc and free hooks
 265    temporarily, because the `atfork' handler mechanism may use
 266    malloc/free internally (e.g. in LinuxThreads). */
 267
 268 static void
 269 ptmalloc_lock_all (void)
 270 {
 271   mstate ar_ptr;
 272
 273   if(__malloc_initialized < 1)
 274     return;
 275   if (mutex_trylock(&list_lock))
 276     {
 277       Void_t *my_arena;
 278       tsd_getspecific(arena_key, my_arena);
 279       if (my_arena == ATFORK_ARENA_PTR)
 280         /* This is the same thread which already locks the global list.
 281            Just bump the counter.  */
 282         goto out;
 283
 284       /* This thread has to wait its turn.  */
 285       (void)mutex_lock(&list_lock);
 286     }
 287   for(ar_ptr = &main_arena;;) {
 288     (void)mutex_lock(&ar_ptr->mutex);
 289     ar_ptr = ar_ptr->next;
 290     if(ar_ptr == &main_arena) break;
 291   }
 292   save_malloc_hook = __malloc_hook;
 293   save_free_hook = __free_hook;
 294   __malloc_hook = malloc_atfork;
 295   __free_hook = free_atfork;
 296   /* Only the current thread may perform malloc/free calls now. */
 297   tsd_getspecific(arena_key, save_arena);
 298   tsd_setspecific(arena_key, ATFORK_ARENA_PTR);
 299  out:
 300   ++atfork_recursive_cntr;
 301 }
 302
 303 static void
 304 ptmalloc_unlock_all (void)
 305 {
 306   mstate ar_ptr;
 307
 308   if(__malloc_initialized < 1)
 309     return;
 310   if (--atfork_recursive_cntr != 0)
 311     return;
 312   tsd_setspecific(arena_key, save_arena);
 313   __malloc_hook = save_malloc_hook;
 314   __free_hook = save_free_hook;
 315   for(ar_ptr = &main_arena;;) {
 316     (void)mutex_unlock(&ar_ptr->mutex);
 317     ar_ptr = ar_ptr->next;
 318     if(ar_ptr == &main_arena) break;
 319   }
 320   (void)mutex_unlock(&list_lock);
 321 }
 322
 323 #ifdef __linux__
 324
 325 /* In NPTL, unlocking a mutex in the child process after a
 326    fork() is currently unsafe, whereas re-initializing it is safe and
 327    does not leak resources.  Therefore, a special atfork handler is
 328    installed for the child. */
 329
 330 static void
 331 ptmalloc_unlock_all2 (void)
 332 {
 333   mstate ar_ptr;
 334
 335   if(__malloc_initialized < 1)
 336     return;
 337 #if defined _LIBC || defined MALLOC_HOOKS
 338   tsd_setspecific(arena_key, save_arena);
 339   __malloc_hook = save_malloc_hook;
 340   __free_hook = save_free_hook;
 341 #endif
 342 #ifdef PER_THREAD
 343   free_list = NULL;
 344 #endif
 345   for(ar_ptr = &main_arena;;) {
 346     mutex_init(&ar_ptr->mutex);
 347 #ifdef PER_THREAD
 348     if (ar_ptr != save_arena) {
 349       ar_ptr->next_free = free_list;
 350       free_list = ar_ptr;
 351     }
 352 #endif
 353     ar_ptr = ar_ptr->next;
 354     if(ar_ptr == &main_arena) break;
 355   }
 356   mutex_init(&list_lock);
 357   atfork_recursive_cntr = 0;
 358 }
 359
 360 #else
 361
 362 #define ptmalloc_unlock_all2 ptmalloc_unlock_all
 363
 364 #endif
 365
 366 #endif /* !defined NO_THREADS */
 367
 368 /* Initialization routine. */
 369 #ifdef _LIBC
 370 #include <string.h>
 371 extern char **_environ;
 372
 373 static char *
 374 internal_function
 375 next_env_entry (char ***position)
 376 {
 377   char **current = *position;
 378   char *result = NULL;
 379
 380   while (*current != NULL)
 381     {
 382       if (__builtin_expect ((*current)[0] == 'M', 0)
 383           && (*current)[1] == 'A'
 384           && (*current)[2] == 'L'
 385           && (*current)[3] == 'L'
 386           && (*current)[4] == 'O'
 387           && (*current)[5] == 'C'
 388           && (*current)[6] == '_')
 389         {
 390           result = &(*current)[7];
 391
 392           /* Save current position for next visit.  */
 393           *position = ++current;
 394
 395           break;
 396         }
 397
 398       ++current;
 399     }
 400
 401   return result;
 402 }
 403 #endif /* _LIBC */
 404
 405 /* Set up basic state so that _int_malloc et al can work.  */
 406 static void
 407 ptmalloc_init_minimal (void)
 408 {
 409 #if DEFAULT_TOP_PAD != 0
 410   mp_.top_pad        = DEFAULT_TOP_PAD;
 411 #endif
 412   mp_.n_mmaps_max    = DEFAULT_MMAP_MAX;
 413   mp_.mmap_threshold = DEFAULT_MMAP_THRESHOLD;
 414   mp_.trim_threshold = DEFAULT_TRIM_THRESHOLD;
 415   mp_.pagesize       = malloc_getpagesize;
 416 #ifdef PER_THREAD
 417 # define NARENAS_FROM_NCORES(n) ((n) * (sizeof(long) == 4 ? 2 : 8))
 418   mp_.arena_test     = NARENAS_FROM_NCORES (1);
 419   narenas = 1;
 420 #endif
 421 }
 422
 423
 424 #ifdef _LIBC
 425 # ifdef SHARED
 426 static void *
 427 __failing_morecore (ptrdiff_t d)
 428 {
 429   return (void *) MORECORE_FAILURE;
 430 }
 431
 432 extern struct dl_open_hook *_dl_open_hook;
 433 libc_hidden_proto (_dl_open_hook);
 434 # endif
 435
 436 # if defined SHARED && !USE___THREAD
 437 /* This is called by __pthread_initialize_minimal when it needs to use
 438    malloc to set up the TLS state.  We cannot do the full work of
 439    ptmalloc_init (below) until __pthread_initialize_minimal has finished,
 440    so it has to switch to using the special startup-time hooks while doing
 441    those allocations.  */
 442 void
 443 __libc_malloc_pthread_startup (bool first_time)
 444 {
 445   if (first_time)
 446     {
 447       ptmalloc_init_minimal ();
 448       save_malloc_hook = __malloc_hook;
 449       save_memalign_hook = __memalign_hook;
 450       save_free_hook = __free_hook;
 451       __malloc_hook = malloc_starter;
 452       __memalign_hook = memalign_starter;
 453       __free_hook = free_starter;
 454     }
 455   else
 456     {
 457       __malloc_hook = save_malloc_hook;
 458       __memalign_hook = save_memalign_hook;
 459       __free_hook = save_free_hook;
 460     }
 461 }
 462 # endif
 463 #endif
 464
 465 static void
 466 ptmalloc_init (void)
 467 {
 468 #if __STD_C
 469   const char* s;
 470 #else
 471   char* s;
 472 #endif
 473   int secure = 0;
 474
 475   if(__malloc_initialized >= 0) return;
 476   __malloc_initialized = 0;
 477
 478 #ifdef _LIBC
 479 # if defined SHARED && !USE___THREAD
 480   /* ptmalloc_init_minimal may already have been called via
 481      __libc_malloc_pthread_startup, above.  */
 482   if (mp_.pagesize == 0)
 483 # endif
 484 #endif
 485     ptmalloc_init_minimal();
 486
 487 #ifndef NO_THREADS
 488 # if defined _LIBC
 489   /* We know __pthread_initialize_minimal has already been called,
 490      and that is enough.  */
 491 #   define NO_STARTER
 492 # endif
 493 # ifndef NO_STARTER
 494   /* With some threads implementations, creating thread-specific data
 495      or initializing a mutex may call malloc() itself.  Provide a
 496      simple starter version (realloc() won't work). */
 497   save_malloc_hook = __malloc_hook;
 498   save_memalign_hook = __memalign_hook;
 499   save_free_hook = __free_hook;
 500   __malloc_hook = malloc_starter;
 501   __memalign_hook = memalign_starter;
 502   __free_hook = free_starter;
 503 #  ifdef _LIBC
 504   /* Initialize the pthreads interface. */
 505   if (__pthread_initialize != NULL)
 506     __pthread_initialize();
 507 #  endif /* !defined _LIBC */
 508 # endif /* !defined NO_STARTER */
 509 #endif /* !defined NO_THREADS */
 510   mutex_init(&main_arena.mutex);
 511   main_arena.next = &main_arena;
 512
 513 #if defined _LIBC && defined SHARED
 514   /* In case this libc copy is in a non-default namespace, never use brk.
 515      Likewise if dlopened from statically linked program.  */
 516   Dl_info di;
 517   struct link_map *l;
 518
 519   if (_dl_open_hook != NULL
 520       || (_dl_addr (ptmalloc_init, &di, &l, NULL) != 0
 521           && l->l_ns != LM_ID_BASE))
 522     __morecore = __failing_morecore;
 523 #endif
 524
 525   mutex_init(&list_lock);
 526   tsd_key_create(&arena_key, NULL);
 527   tsd_setspecific(arena_key, (Void_t *)&main_arena);
 528   thread_atfork(ptmalloc_lock_all, ptmalloc_unlock_all, ptmalloc_unlock_all2);
 529 #ifndef NO_THREADS
 530 # ifndef NO_STARTER
 531   __malloc_hook = save_malloc_hook;
 532   __memalign_hook = save_memalign_hook;
 533   __free_hook = save_free_hook;
 534 # else
 535 #  undef NO_STARTER
 536 # endif
 537 #endif
 538 #ifdef _LIBC
 539   secure = __libc_enable_secure;
 540   s = NULL;
 541   if (__builtin_expect (_environ != NULL, 1))
 542     {
 543       char **runp = _environ;
 544       char *envline;
 545
 546       while (__builtin_expect ((envline = next_env_entry (&runp)) != NULL,
 547                                0))
 548         {
 549           size_t len = strcspn (envline, "=");
 550
 551           if (envline[len] != '=')
 552             /* This is a "MALLOC_" variable at the end of the string
 553                without a '=' character.  Ignore it since otherwise we
 554                will access invalid memory below.  */
 555             continue;
 556
 557           switch (len)
 558             {
 559             case 6:
 560               if (memcmp (envline, "CHECK_", 6) == 0)
 561                 s = &envline[7];
 562               break;
 563             case 8:
 564               if (! secure)
 565                 {
 566                   if (memcmp (envline, "TOP_PAD_", 8) == 0)
 567                     mALLOPt(M_TOP_PAD, atoi(&envline[9]));
 568                   else if (memcmp (envline, "PERTURB_", 8) == 0)
 569                     mALLOPt(M_PERTURB, atoi(&envline[9]));
 570                 }
 571               break;
 572             case 9:
 573               if (! secure)
 574                 {
 575                   if (memcmp (envline, "MMAP_MAX_", 9) == 0)
 576                     mALLOPt(M_MMAP_MAX, atoi(&envline[10]));
 577 #ifdef PER_THREAD
 578                   else if (memcmp (envline, "ARENA_MAX", 9) == 0)
 579                     mALLOPt(M_ARENA_MAX, atoi(&envline[10]));
 580 #endif
 581                 }
 582               break;
 583 #ifdef PER_THREAD
 584             case 10:
 585               if (! secure)
 586                 {
 587                   if (memcmp (envline, "ARENA_TEST", 10) == 0)
 588                     mALLOPt(M_ARENA_TEST, atoi(&envline[11]));
 589                 }
 590               break;
 591 #endif
 592             case 15:
 593               if (! secure)
 594                 {
 595                   if (memcmp (envline, "TRIM_THRESHOLD_", 15) == 0)
 596                     mALLOPt(M_TRIM_THRESHOLD, atoi(&envline[16]));
 597                   else if (memcmp (envline, "MMAP_THRESHOLD_", 15) == 0)
 598                     mALLOPt(M_MMAP_THRESHOLD, atoi(&envline[16]));
 599                 }
 600               break;
 601             default:
 602               break;
 603             }
 604         }
 605     }
 606 #else
 607   if (! secure)
 608     {
 609       if((s = getenv("MALLOC_TRIM_THRESHOLD_")))
 610         mALLOPt(M_TRIM_THRESHOLD, atoi(s));
 611       if((s = getenv("MALLOC_TOP_PAD_")))
 612         mALLOPt(M_TOP_PAD, atoi(s));
 613       if((s = getenv("MALLOC_PERTURB_")))
 614         mALLOPt(M_PERTURB, atoi(s));
 615       if((s = getenv("MALLOC_MMAP_THRESHOLD_")))
 616         mALLOPt(M_MMAP_THRESHOLD, atoi(s));
 617       if((s = getenv("MALLOC_MMAP_MAX_")))
 618         mALLOPt(M_MMAP_MAX, atoi(s));
 619     }
 620   s = getenv("MALLOC_CHECK_");
 621 #endif
 622   if(s && s[0]) {
 623     mALLOPt(M_CHECK_ACTION, (int)(s[0] - '0'));
 624     if (check_action != 0)
 625       __malloc_check_init();
 626   }
 627   void (*hook) (void) = force_reg (__malloc_initialize_hook);
 628   if (hook != NULL)
 629     (*hook)();
 630   __malloc_initialized = 1;
 631 }
 632
 633 /* There are platforms (e.g. Hurd) with a link-time hook mechanism. */
 634 #ifdef thread_atfork_static
 635 thread_atfork_static(ptmalloc_lock_all, ptmalloc_unlock_all, \
 636                      ptmalloc_unlock_all2)
 637 #endif
 638
 639 \f
 640
 641 /* Managing heaps and arenas (for concurrent threads) */
 642
 643 #if USE_ARENAS
 644
 645 #if MALLOC_DEBUG > 1
 646
 647 /* Print the complete contents of a single heap to stderr. */
 648
 649 static void
 650 #if __STD_C
 651 dump_heap(heap_info *heap)
 652 #else
 653 dump_heap(heap) heap_info *heap;
 654 #endif
 655 {
 656   char *ptr;
 657   mchunkptr p;
 658
 659   fprintf(stderr, "Heap %p, size %10lx:\n", heap, (long)heap->size);
 660   ptr = (heap->ar_ptr != (mstate)(heap+1)) ?
 661     (char*)(heap + 1) : (char*)(heap + 1) + sizeof(struct malloc_state);
 662   p = (mchunkptr)(((unsigned long)ptr + MALLOC_ALIGN_MASK) &
 663                   ~MALLOC_ALIGN_MASK);
 664   for(;;) {
 665     fprintf(stderr, "chunk %p size %10lx", p, (long)p->size);
 666     if(p == top(heap->ar_ptr)) {
 667       fprintf(stderr, " (top)\n");
 668       break;
 669     } else if(p->size == (0|PREV_INUSE)) {
 670       fprintf(stderr, " (fence)\n");
 671       break;
 672     }
 673     fprintf(stderr, "\n");
 674     p = next_chunk(p);
 675   }
 676 }
 677
 678 #endif /* MALLOC_DEBUG > 1 */
 679
 680 /* If consecutive mmap (0, HEAP_MAX_SIZE << 1, ...) calls return decreasing
 681    addresses as opposed to increasing, new_heap would badly fragment the
 682    address space.  In that case remember the second HEAP_MAX_SIZE part
 683    aligned to HEAP_MAX_SIZE from last mmap (0, HEAP_MAX_SIZE << 1, ...)
 684    call (if it is already aligned) and try to reuse it next time.  We need
 685    no locking for it, as kernel ensures the atomicity for us - worst case
 686    we'll call mmap (addr, HEAP_MAX_SIZE, ...) for some value of addr in
 687    multiple threads, but only one will succeed.  */
 688 static char *aligned_heap_area;
 689
 690 /* Create a new heap.  size is automatically rounded up to a multiple
 691    of the page size. */
 692
 693 static heap_info *
 694 internal_function
 695 #if __STD_C
 696 new_heap(size_t size, size_t top_pad)
 697 #else
 698 new_heap(size, top_pad) size_t size, top_pad;
 699 #endif
 700 {
 701   size_t page_mask = malloc_getpagesize - 1;
 702   char *p1, *p2;
 703   unsigned long ul;
 704   heap_info *h;
 705
 706   if(size+top_pad < HEAP_MIN_SIZE)
 707     size = HEAP_MIN_SIZE;
 708   else if(size+top_pad <= HEAP_MAX_SIZE)
 709     size += top_pad;
 710   else if(size > HEAP_MAX_SIZE)
 711     return 0;
 712   else
 713     size = HEAP_MAX_SIZE;
 714   size = (size + page_mask) & ~page_mask;
 715
 716   /* A memory region aligned to a multiple of HEAP_MAX_SIZE is needed.
 717      No swap space needs to be reserved for the following large
 718      mapping (on Linux, this is the case for all non-writable mappings
 719      anyway). */
 720   p2 = MAP_FAILED;
 721   if(aligned_heap_area) {
 722     p2 = (char *)MMAP(aligned_heap_area, HEAP_MAX_SIZE, PROT_NONE,
 723                       MAP_PRIVATE|MAP_NORESERVE);
 724     aligned_heap_area = NULL;
 725     if (p2 != MAP_FAILED && ((unsigned long)p2 & (HEAP_MAX_SIZE-1))) {
 726       munmap(p2, HEAP_MAX_SIZE);
 727       p2 = MAP_FAILED;
 728     }
 729   }
 730   if(p2 == MAP_FAILED) {
 731     p1 = (char *)MMAP(0, HEAP_MAX_SIZE<<1, PROT_NONE,
 732                       MAP_PRIVATE|MAP_NORESERVE);
 733     if(p1 != MAP_FAILED) {
 734       p2 = (char *)(((unsigned long)p1 + (HEAP_MAX_SIZE-1))
 735                     & ~(HEAP_MAX_SIZE-1));
 736       ul = p2 - p1;
 737       if (ul)
 738         munmap(p1, ul);
 739       else
 740         aligned_heap_area = p2 + HEAP_MAX_SIZE;
 741       munmap(p2 + HEAP_MAX_SIZE, HEAP_MAX_SIZE - ul);
 742     } else {
 743       /* Try to take the chance that an allocation of only HEAP_MAX_SIZE
 744          is already aligned. */
 745       p2 = (char *)MMAP(0, HEAP_MAX_SIZE, PROT_NONE, MAP_PRIVATE|MAP_NORESERVE);
 746       if(p2 == MAP_FAILED)
 747         return 0;
 748       if((unsigned long)p2 & (HEAP_MAX_SIZE-1)) {
 749         munmap(p2, HEAP_MAX_SIZE);
 750         return 0;
 751       }
 752     }
 753   }
 754   if(mprotect(p2, size, PROT_READ|PROT_WRITE) != 0) {
 755     munmap(p2, HEAP_MAX_SIZE);
 756     return 0;
 757   }
 758   h = (heap_info *)p2;
 759   h->size = size;
 760   h->mprotect_size = size;
 761   THREAD_STAT(stat_n_heaps++);
 762   return h;
 763 }
 764
 765 /* Grow a heap.  size is automatically rounded up to a
 766    multiple of the page size. */
 767
 768 static int
 769 #if __STD_C
 770 grow_heap(heap_info *h, long diff)
 771 #else
 772 grow_heap(h, diff) heap_info *h; long diff;
 773 #endif
 774 {
 775   size_t page_mask = malloc_getpagesize - 1;
 776   long new_size;
 777
 778   diff = (diff + page_mask) & ~page_mask;
 779   new_size = (long)h->size + diff;
 780   if((unsigned long) new_size > (unsigned long) HEAP_MAX_SIZE)
 781     return -1;
 782   if((unsigned long) new_size > h->mprotect_size) {
 783     if (mprotect((char *)h + h->mprotect_size,
 784                  (unsigned long) new_size - h->mprotect_size,
 785                  PROT_READ|PROT_WRITE) != 0)
 786       return -2;
 787     h->mprotect_size = new_size;
 788   }
 789
 790   h->size = new_size;
 791   return 0;
 792 }
 793
 794 /* Shrink a heap.  */
 795
 796 static int
 797 #if __STD_C
 798 shrink_heap(heap_info *h, long diff)
 799 #else
 800 shrink_heap(h, diff) heap_info *h; long diff;
 801 #endif
 802 {
 803   long new_size;
 804
 805   new_size = (long)h->size - diff;
 806   if(new_size < (long)sizeof(*h))
 807     return -1;
 808   /* Try to re-map the extra heap space freshly to save memory, and
 809      make it inaccessible. */
 810 #ifdef _LIBC
 811   if (__builtin_expect (__libc_enable_secure, 0))
 812 #else
 813   if (1)
 814 #endif
 815     {
 816       if((char *)MMAP((char *)h + new_size, diff, PROT_NONE,
 817                       MAP_PRIVATE|MAP_FIXED) == (char *) MAP_FAILED)
 818         return -2;
 819       h->mprotect_size = new_size;
 820     }
 821 #ifdef _LIBC
 822   else
 823     madvise ((char *)h + new_size, diff, MADV_DONTNEED);
 824 #endif
 825   /*fprintf(stderr, "shrink %p %08lx\n", h, new_size);*/
 826
 827   h->size = new_size;
 828   return 0;
 829 }
 830
 831 /* Delete a heap. */
 832
 833 #define delete_heap(heap) \
 834   do {                                                          \
 835     if ((char *)(heap) + HEAP_MAX_SIZE == aligned_heap_area)    \
 836       aligned_heap_area = NULL;                                 \
 837     munmap((char*)(heap), HEAP_MAX_SIZE);                       \
 838   } while (0)
 839
 840 static int
 841 internal_function
 842 #if __STD_C
 843 heap_trim(heap_info *heap, size_t pad)
 844 #else
 845 heap_trim(heap, pad) heap_info *heap; size_t pad;
 846 #endif
 847 {
 848   mstate ar_ptr = heap->ar_ptr;
 849   unsigned long pagesz = mp_.pagesize;
 850   mchunkptr top_chunk = top(ar_ptr), p, bck, fwd;
 851   heap_info *prev_heap;
 852   long new_size, top_size, extra;
 853
 854   /* Can this heap go away completely? */
 855   while(top_chunk == chunk_at_offset(heap, sizeof(*heap))) {
 856     prev_heap = heap->prev;
 857     p = chunk_at_offset(prev_heap, prev_heap->size - (MINSIZE-2*SIZE_SZ));
 858     assert(p->size == (0|PREV_INUSE)); /* must be fencepost */
 859     p = prev_chunk(p);
 860     new_size = chunksize(p) + (MINSIZE-2*SIZE_SZ);
 861     assert(new_size>0 && new_size<(long)(2*MINSIZE));
 862     if(!prev_inuse(p))
 863       new_size += p->prev_size;
 864     assert(new_size>0 && new_size<HEAP_MAX_SIZE);
 865     if(new_size + (HEAP_MAX_SIZE - prev_heap->size) < pad + MINSIZE + pagesz)
 866       break;
 867     ar_ptr->system_mem -= heap->size;
 868     arena_mem -= heap->size;
 869     delete_heap(heap);
 870     heap = prev_heap;
 871     if(!prev_inuse(p)) { /* consolidate backward */
 872       p = prev_chunk(p);
 873       unlink(p, bck, fwd);
 874     }
 875     assert(((unsigned long)((char*)p + new_size) & (pagesz-1)) == 0);
 876     assert( ((char*)p + new_size) == ((char*)heap + heap->size) );
 877     top(ar_ptr) = top_chunk = p;
 878     set_head(top_chunk, new_size | PREV_INUSE);
 879     /*check_chunk(ar_ptr, top_chunk);*/
 880   }
 881   top_size = chunksize(top_chunk);
 882   extra = (top_size - pad - MINSIZE - 1) & ~(pagesz - 1);
 883   if(extra < (long)pagesz)
 884     return 0;
 885   /* Try to shrink. */
 886   if(shrink_heap(heap, extra) != 0)
 887     return 0;
 888   ar_ptr->system_mem -= extra;
 889   arena_mem -= extra;
 890
 891   /* Success. Adjust top accordingly. */
 892   set_head(top_chunk, (top_size - extra) | PREV_INUSE);
 893   /*check_chunk(ar_ptr, top_chunk);*/
 894   return 1;
 895 }
 896
 897 /* Create a new arena with initial size "size".  */
 898
 899 static mstate
 900 _int_new_arena(size_t size)
 901 {
 902   mstate a;
 903   heap_info *h;
 904   char *ptr;
 905   unsigned long misalign;
 906
 907   h = new_heap(size + (sizeof(*h) + sizeof(*a) + MALLOC_ALIGNMENT),
 908                mp_.top_pad);
 909   if(!h) {
 910     /* Maybe size is too large to fit in a single heap.  So, just try
 911        to create a minimally-sized arena and let _int_malloc() attempt
 912        to deal with the large request via mmap_chunk().  */
 913     h = new_heap(sizeof(*h) + sizeof(*a) + MALLOC_ALIGNMENT, mp_.top_pad);
 914     if(!h)
 915       return 0;
 916   }
 917   a = h->ar_ptr = (mstate)(h+1);
 918   malloc_init_state(a);
 919   /*a->next = NULL;*/
 920   a->system_mem = a->max_system_mem = h->size;
 921   arena_mem += h->size;
 922 #ifdef NO_THREADS
 923   if((unsigned long)(mp_.mmapped_mem + arena_mem + main_arena.system_mem) >
 924      mp_.max_total_mem)
 925     mp_.max_total_mem = mp_.mmapped_mem + arena_mem + main_arena.system_mem;
 926 #endif
 927
 928   /* Set up the top chunk, with proper alignment. */
 929   ptr = (char *)(a + 1);
 930   misalign = (unsigned long)chunk2mem(ptr) & MALLOC_ALIGN_MASK;
 931   if (misalign > 0)
 932     ptr += MALLOC_ALIGNMENT - misalign;
 933   top(a) = (mchunkptr)ptr;
 934   set_head(top(a), (((char*)h + h->size) - ptr) | PREV_INUSE);
 935
 936   tsd_setspecific(arena_key, (Void_t *)a);
 937   mutex_init(&a->mutex);
 938   (void)mutex_lock(&a->mutex);
 939
 940 #ifdef PER_THREAD
 941   (void)mutex_lock(&list_lock);
 942 #endif
 943
 944   /* Add the new arena to the global list.  */
 945   a->next = main_arena.next;
 946   atomic_write_barrier ();
 947   main_arena.next = a;
 948
 949 #ifdef PER_THREAD
 950   ++narenas;
 951
 952   (void)mutex_unlock(&list_lock);
 953 #endif
 954
 955   THREAD_STAT(++(a->stat_lock_loop));
 956
 957   return a;
 958 }
 959
 960
 961 #ifdef PER_THREAD
 962 static mstate
 963 get_free_list (void)
 964 {
 965   mstate result = free_list;
 966   if (result != NULL)
 967     {
 968       (void)mutex_lock(&list_lock);
 969       result = free_list;
 970       if (result != NULL)
 971         free_list = result->next_free;
 972       (void)mutex_unlock(&list_lock);
 973
 974       if (result != NULL)
 975         {
 976           (void)mutex_lock(&result->mutex);
 977           tsd_setspecific(arena_key, (Void_t *)result);
 978           THREAD_STAT(++(result->stat_lock_loop));
 979         }
 980     }
 981
 982   return result;
 983 }
 984
 985
 986 static mstate
 987 reused_arena (void)
 988 {
 989   if (narenas <= mp_.arena_test)
 990     return NULL;
 991
 992   static int narenas_limit;
 993   if (narenas_limit == 0)
 994     {
 995       if (mp_.arena_max != 0)
 996         narenas_limit = mp_.arena_max;
 997       else
 998         {
 999           int n  = __get_nprocs ();
1000
1001           if (n >= 1)
1002             narenas_limit = NARENAS_FROM_NCORES (n);
1003           else
1004             /* We have no information about the system.  Assume two
1005                cores.  */
1006             narenas_limit = NARENAS_FROM_NCORES (2);
1007         }
1008     }
1009
1010   if (narenas < narenas_limit)
1011     return NULL;
1012
1013   mstate result;
1014   static mstate next_to_use;
1015   if (next_to_use == NULL)
1016     next_to_use = &main_arena;
1017
1018   result = next_to_use;
1019   do
1020     {
1021       if (!mutex_trylock(&result->mutex))
1022         goto out;
1023
1024       result = result->next;
1025     }
1026   while (result != next_to_use);
1027
1028   /* No arena available.  Wait for the next in line.  */
1029   (void)mutex_lock(&result->mutex);
1030
1031  out:
1032   tsd_setspecific(arena_key, (Void_t *)result);
1033   THREAD_STAT(++(result->stat_lock_loop));
1034   next_to_use = result->next;
1035
1036   return result;
1037 }
1038 #endif
1039
1040 static mstate
1041 internal_function
1042 #if __STD_C
1043 arena_get2(mstate a_tsd, size_t size)
1044 #else
1045 arena_get2(a_tsd, size) mstate a_tsd; size_t size;
1046 #endif
1047 {
1048   mstate a;
1049
1050 #ifdef PER_THREAD
1051   if ((a = get_free_list ()) == NULL
1052       && (a = reused_arena ()) == NULL)
1053     /* Nothing immediately available, so generate a new arena.  */
1054     a = _int_new_arena(size);
1055 #else
1056   if(!a_tsd)
1057     a = a_tsd = &main_arena;
1058   else {
1059     a = a_tsd->next;
1060     if(!a) {
1061       /* This can only happen while initializing the new arena. */
1062       (void)mutex_lock(&main_arena.mutex);
1063       THREAD_STAT(++(main_arena.stat_lock_wait));
1064       return &main_arena;
1065     }
1066   }
1067
1068   /* Check the global, circularly linked list for available arenas. */
1069   bool retried = false;
1070  repeat:
1071   do {
1072     if(!mutex_trylock(&a->mutex)) {
1073       if (retried)
1074         (void)mutex_unlock(&list_lock);
1075       THREAD_STAT(++(a->stat_lock_loop));
1076       tsd_setspecific(arena_key, (Void_t *)a);
1077       return a;
1078     }
1079     a = a->next;
1080   } while(a != a_tsd);
1081
1082   /* If not even the list_lock can be obtained, try again.  This can
1083      happen during `atfork', or for example on systems where thread
1084      creation makes it temporarily impossible to obtain _any_
1085      locks. */
1086   if(!retried && mutex_trylock(&list_lock)) {
1087     /* We will block to not run in a busy loop.  */
1088     (void)mutex_lock(&list_lock);
1089
1090     /* Since we blocked there might be an arena available now.  */
1091     retried = true;
1092     a = a_tsd;
1093     goto repeat;
1094   }
1095
1096   /* Nothing immediately available, so generate a new arena.  */
1097   a = _int_new_arena(size);
1098   (void)mutex_unlock(&list_lock);
1099 #endif
1100
1101   return a;
1102 }
1103
1104 #ifdef PER_THREAD
1105 static void __attribute__ ((section ("__libc_thread_freeres_fn")))
1106 arena_thread_freeres (void)
1107 {
1108   Void_t *vptr = NULL;
1109   mstate a = tsd_getspecific(arena_key, vptr);
1110   tsd_setspecific(arena_key, NULL);
1111
1112   if (a != NULL)
1113     {
1114       (void)mutex_lock(&list_lock);
1115       a->next_free = free_list;
1116       free_list = a;
1117       (void)mutex_unlock(&list_lock);
1118     }
1119 }
1120 text_set_element (__libc_thread_subfreeres, arena_thread_freeres);
1121 #endif
1122
1123 #endif /* USE_ARENAS */
1124
1125 /*
1126  * Local variables:
1127  * c-basic-offset: 2
1128  * End:
1129  */