malloc/arena.c

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