malloc/arena.c

   1 /* Malloc implementation for multiple threads without lock contention.
   2    Copyright (C) 2001,2002,2003,2004,2005,2006,2007,2009,2010,2011,2012
   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.  */
  57
  58 typedef struct _heap_info {
  59   mstate ar_ptr; /* Arena for this heap. */
  60   struct _heap_info *prev; /* Previous heap. */
  61   size_t size;   /* Current size in bytes. */
  62   size_t mprotect_size; /* Size in bytes that has been mprotected
  63                            PROT_READ|PROT_WRITE.  */
  64   /* Make sure the following data is properly aligned, particularly
  65      that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
  66      MALLOC_ALIGNMENT. */
  67   char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];
  68 } heap_info;
  69
  70 /* Get a compile-time error if the heap_info padding is not correct
  71    to make alignment work as expected in sYSMALLOc.  */
  72 extern int sanity_check_heap_info_alignment[(sizeof (heap_info)
  73                                              + 2 * SIZE_SZ) % MALLOC_ALIGNMENT
  74                                             ? -1 : 1];
  75
  76 /* Thread specific data */
  77
  78 static tsd_key_t arena_key;
  79 static mutex_t list_lock = MUTEX_INITIALIZER;
  80 #ifdef PER_THREAD
  81 static size_t narenas = 1;
  82 static mstate free_list;
  83 #endif
  84
  85 #if THREAD_STATS
  86 static int stat_n_heaps;
  87 #define THREAD_STAT(x) x
  88 #else
  89 #define THREAD_STAT(x) do ; while(0)
  90 #endif
  91
  92 /* Mapped memory in non-main arenas (reliable only for NO_THREADS). */
  93 static unsigned long arena_mem;
  94
  95 /* Already initialized? */
  96 int __malloc_initialized = -1;
  97
  98 /**************************************************************************/
  99
 100
 101 /* arena_get() acquires an arena and locks the corresponding mutex.
 102    First, try the one last locked successfully by this thread.  (This
 103    is the common case and handled with a macro for speed.)  Then, loop
 104    once over the circularly linked list of arenas.  If no arena is
 105    readily available, create a new one.  In this latter case, `size'
 106    is just a hint as to how much memory will be required immediately
 107    in the new arena. */
 108
 109 #define arena_get(ptr, size) do { \
 110   arena_lookup(ptr); \
 111   arena_lock(ptr, size); \
 112 } while(0)
 113
 114 #define arena_lookup(ptr) do { \
 115   void *vptr = NULL; \
 116   ptr = (mstate)tsd_getspecific(arena_key, vptr); \
 117 } while(0)
 118
 119 #ifdef PER_THREAD
 120 # define arena_lock(ptr, size) do { \
 121   if(ptr) \
 122     (void)mutex_lock(&ptr->mutex); \
 123   else \
 124     ptr = arena_get2(ptr, (size)); \
 125 } while(0)
 126 #else
 127 # define arena_lock(ptr, size) do { \
 128   if(ptr && !mutex_trylock(&ptr->mutex)) { \
 129     THREAD_STAT(++(ptr->stat_lock_direct)); \
 130   } else \
 131     ptr = arena_get2(ptr, (size)); \
 132 } while(0)
 133 #endif
 134
 135 /* find the heap and corresponding arena for a given ptr */
 136
 137 #define heap_for_ptr(ptr) \
 138  ((heap_info *)((unsigned long)(ptr) & ~(HEAP_MAX_SIZE-1)))
 139 #define arena_for_chunk(ptr) \
 140  (chunk_non_main_arena(ptr) ? heap_for_ptr(ptr)->ar_ptr : &main_arena)
 141
 142
 143 /**************************************************************************/
 144
 145 /* atfork support.  */
 146
 147 static __malloc_ptr_t (*save_malloc_hook) (size_t __size,
 148                                            const __malloc_ptr_t);
 149 static void           (*save_free_hook) (__malloc_ptr_t __ptr,
 150                                          const __malloc_ptr_t);
 151 static void*        save_arena;
 152
 153 #ifdef ATFORK_MEM
 154 ATFORK_MEM;
 155 #endif
 156
 157 /* Magic value for the thread-specific arena pointer when
 158    malloc_atfork() is in use.  */
 159
 160 #define ATFORK_ARENA_PTR ((void*)-1)
 161
 162 /* The following hooks are used while the `atfork' handling mechanism
 163    is active. */
 164
 165 static void*
 166 malloc_atfork(size_t sz, const void *caller)
 167 {
 168   void *vptr = NULL;
 169   void *victim;
 170
 171   tsd_getspecific(arena_key, vptr);
 172   if(vptr == ATFORK_ARENA_PTR) {
 173     /* We are the only thread that may allocate at all.  */
 174     if(save_malloc_hook != malloc_check) {
 175       return _int_malloc(&main_arena, sz);
 176     } else {
 177       if(top_check()<0)
 178         return 0;
 179       victim = _int_malloc(&main_arena, sz+1);
 180       return mem2mem_check(victim, sz);
 181     }
 182   } else {
 183     /* Suspend the thread until the `atfork' handlers have completed.
 184        By that time, the hooks will have been reset as well, so that
 185        mALLOc() can be used again. */
 186     (void)mutex_lock(&list_lock);
 187     (void)mutex_unlock(&list_lock);
 188     return public_mALLOc(sz);
 189   }
 190 }
 191
 192 static void
 193 free_atfork(void* mem, const void *caller)
 194 {
 195   void *vptr = NULL;
 196   mstate ar_ptr;
 197   mchunkptr p;                          /* chunk corresponding to mem */
 198
 199   if (mem == 0)                              /* free(0) has no effect */
 200     return;
 201
 202   p = mem2chunk(mem);         /* do not bother to replicate free_check here */
 203
 204   if (chunk_is_mmapped(p))                       /* release mmapped memory. */
 205   {
 206     munmap_chunk(p);
 207     return;
 208   }
 209
 210   ar_ptr = arena_for_chunk(p);
 211   tsd_getspecific(arena_key, vptr);
 212   _int_free(ar_ptr, p, vptr == ATFORK_ARENA_PTR);
 213 }
 214
 215
 216 /* Counter for number of times the list is locked by the same thread.  */
 217 static unsigned int atfork_recursive_cntr;
 218
 219 /* The following two functions are registered via thread_atfork() to
 220    make sure that the mutexes remain in a consistent state in the
 221    fork()ed version of a thread.  Also adapt the malloc and free hooks
 222    temporarily, because the `atfork' handler mechanism may use
 223    malloc/free internally (e.g. in LinuxThreads). */
 224
 225 static void
 226 ptmalloc_lock_all (void)
 227 {
 228   mstate ar_ptr;
 229
 230   if(__malloc_initialized < 1)
 231     return;
 232   if (mutex_trylock(&list_lock))
 233     {
 234       void *my_arena;
 235       tsd_getspecific(arena_key, my_arena);
 236       if (my_arena == ATFORK_ARENA_PTR)
 237         /* This is the same thread which already locks the global list.
 238            Just bump the counter.  */
 239         goto out;
 240
 241       /* This thread has to wait its turn.  */
 242       (void)mutex_lock(&list_lock);
 243     }
 244   for(ar_ptr = &main_arena;;) {
 245     (void)mutex_lock(&ar_ptr->mutex);
 246     ar_ptr = ar_ptr->next;
 247     if(ar_ptr == &main_arena) break;
 248   }
 249   save_malloc_hook = __malloc_hook;
 250   save_free_hook = __free_hook;
 251   __malloc_hook = malloc_atfork;
 252   __free_hook = free_atfork;
 253   /* Only the current thread may perform malloc/free calls now. */
 254   tsd_getspecific(arena_key, save_arena);
 255   tsd_setspecific(arena_key, ATFORK_ARENA_PTR);
 256  out:
 257   ++atfork_recursive_cntr;
 258 }
 259
 260 static void
 261 ptmalloc_unlock_all (void)
 262 {
 263   mstate ar_ptr;
 264
 265   if(__malloc_initialized < 1)
 266     return;
 267   if (--atfork_recursive_cntr != 0)
 268     return;
 269   tsd_setspecific(arena_key, save_arena);
 270   __malloc_hook = save_malloc_hook;
 271   __free_hook = save_free_hook;
 272   for(ar_ptr = &main_arena;;) {
 273     (void)mutex_unlock(&ar_ptr->mutex);
 274     ar_ptr = ar_ptr->next;
 275     if(ar_ptr == &main_arena) break;
 276   }
 277   (void)mutex_unlock(&list_lock);
 278 }
 279
 280 #ifdef __linux__
 281
 282 /* In NPTL, unlocking a mutex in the child process after a
 283    fork() is currently unsafe, whereas re-initializing it is safe and
 284    does not leak resources.  Therefore, a special atfork handler is
 285    installed for the child. */
 286
 287 static void
 288 ptmalloc_unlock_all2 (void)
 289 {
 290   mstate ar_ptr;
 291
 292   if(__malloc_initialized < 1)
 293     return;
 294   tsd_setspecific(arena_key, save_arena);
 295   __malloc_hook = save_malloc_hook;
 296   __free_hook = save_free_hook;
 297 #ifdef PER_THREAD
 298   free_list = NULL;
 299 #endif
 300   for(ar_ptr = &main_arena;;) {
 301     mutex_init(&ar_ptr->mutex);
 302 #ifdef PER_THREAD
 303     if (ar_ptr != save_arena) {
 304       ar_ptr->next_free = free_list;
 305       free_list = ar_ptr;
 306     }
 307 #endif
 308     ar_ptr = ar_ptr->next;
 309     if(ar_ptr == &main_arena) break;
 310   }
 311   mutex_init(&list_lock);
 312   atfork_recursive_cntr = 0;
 313 }
 314
 315 #else
 316
 317 #define ptmalloc_unlock_all2 ptmalloc_unlock_all
 318
 319 #endif
 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                     mALLOPt(M_TOP_PAD, atoi(&envline[9]));
 417                   else if (memcmp (envline, "PERTURB_", 8) == 0)
 418                     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                     mALLOPt(M_MMAP_MAX, atoi(&envline[10]));
 426 #ifdef PER_THREAD
 427                   else if (memcmp (envline, "ARENA_MAX", 9) == 0)
 428                     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                     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                     mALLOPt(M_TRIM_THRESHOLD, atoi(&envline[16]));
 446                   else if (memcmp (envline, "MMAP_THRESHOLD_", 15) == 0)
 447                     mALLOPt(M_MMAP_THRESHOLD, atoi(&envline[16]));
 448                 }
 449               break;
 450             default:
 451               break;
 452             }
 453         }
 454     }
 455   if(s && s[0]) {
 456     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_PRIVATE|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,
 555                       MAP_PRIVATE|MAP_NORESERVE);
 556     if(p1 != MAP_FAILED) {
 557       p2 = (char *)(((unsigned long)p1 + (HEAP_MAX_SIZE-1))
 558                     & ~(HEAP_MAX_SIZE-1));
 559       ul = p2 - p1;
 560       if (ul)
 561         munmap(p1, ul);
 562       else
 563         aligned_heap_area = p2 + HEAP_MAX_SIZE;
 564       munmap(p2 + HEAP_MAX_SIZE, HEAP_MAX_SIZE - ul);
 565     } else {
 566       /* Try to take the chance that an allocation of only HEAP_MAX_SIZE
 567          is already aligned. */
 568       p2 = (char *)MMAP(0, HEAP_MAX_SIZE, PROT_NONE, MAP_PRIVATE|MAP_NORESERVE);
 569       if(p2 == MAP_FAILED)
 570         return 0;
 571       if((unsigned long)p2 & (HEAP_MAX_SIZE-1)) {
 572         munmap(p2, HEAP_MAX_SIZE);
 573         return 0;
 574       }
 575     }
 576   }
 577   if(mprotect(p2, size, PROT_READ|PROT_WRITE) != 0) {
 578     munmap(p2, HEAP_MAX_SIZE);
 579     return 0;
 580   }
 581   h = (heap_info *)p2;
 582   h->size = size;
 583   h->mprotect_size = size;
 584   THREAD_STAT(stat_n_heaps++);
 585   return h;
 586 }
 587
 588 /* Grow a heap.  size is automatically rounded up to a
 589    multiple of the page size. */
 590
 591 static int
 592 grow_heap(heap_info *h, long diff)
 593 {
 594   size_t page_mask = GLRO(dl_pagesize) - 1;
 595   long new_size;
 596
 597   diff = (diff + page_mask) & ~page_mask;
 598   new_size = (long)h->size + diff;
 599   if((unsigned long) new_size > (unsigned long) HEAP_MAX_SIZE)
 600     return -1;
 601   if((unsigned long) new_size > h->mprotect_size) {
 602     if (mprotect((char *)h + h->mprotect_size,
 603                  (unsigned long) new_size - h->mprotect_size,
 604                  PROT_READ|PROT_WRITE) != 0)
 605       return -2;
 606     h->mprotect_size = new_size;
 607   }
 608
 609   h->size = new_size;
 610   return 0;
 611 }
 612
 613 /* Shrink a heap.  */
 614
 615 static int
 616 shrink_heap(heap_info *h, long diff)
 617 {
 618   long new_size;
 619
 620   new_size = (long)h->size - diff;
 621   if(new_size < (long)sizeof(*h))
 622     return -1;
 623   /* Try to re-map the extra heap space freshly to save memory, and
 624      make it inaccessible. */
 625   if (__builtin_expect (__libc_enable_secure, 0))
 626     {
 627       if((char *)MMAP((char *)h + new_size, diff, PROT_NONE,
 628                       MAP_PRIVATE|MAP_FIXED) == (char *) MAP_FAILED)
 629         return -2;
 630       h->mprotect_size = new_size;
 631     }
 632   else
 633     madvise ((char *)h + new_size, diff, MADV_DONTNEED);
 634   /*fprintf(stderr, "shrink %p %08lx\n", h, new_size);*/
 635
 636   h->size = new_size;
 637   return 0;
 638 }
 639
 640 /* Delete a heap. */
 641
 642 #define delete_heap(heap) \
 643   do {                                                          \
 644     if ((char *)(heap) + HEAP_MAX_SIZE == aligned_heap_area)    \
 645       aligned_heap_area = NULL;                                 \
 646     munmap((char*)(heap), HEAP_MAX_SIZE);                       \
 647   } while (0)
 648
 649 static int
 650 internal_function
 651 heap_trim(heap_info *heap, size_t pad)
 652 {
 653   mstate ar_ptr = heap->ar_ptr;
 654   unsigned long pagesz = GLRO(dl_pagesize);
 655   mchunkptr top_chunk = top(ar_ptr), p, bck, fwd;
 656   heap_info *prev_heap;
 657   long new_size, top_size, extra;
 658
 659   /* Can this heap go away completely? */
 660   while(top_chunk == chunk_at_offset(heap, sizeof(*heap))) {
 661     prev_heap = heap->prev;
 662     p = chunk_at_offset(prev_heap, prev_heap->size - (MINSIZE-2*SIZE_SZ));
 663     assert(p->size == (0|PREV_INUSE)); /* must be fencepost */
 664     p = prev_chunk(p);
 665     new_size = chunksize(p) + (MINSIZE-2*SIZE_SZ);
 666     assert(new_size>0 && new_size<(long)(2*MINSIZE));
 667     if(!prev_inuse(p))
 668       new_size += p->prev_size;
 669     assert(new_size>0 && new_size<HEAP_MAX_SIZE);
 670     if(new_size + (HEAP_MAX_SIZE - prev_heap->size) < pad + MINSIZE + pagesz)
 671       break;
 672     ar_ptr->system_mem -= heap->size;
 673     arena_mem -= heap->size;
 674     delete_heap(heap);
 675     heap = prev_heap;
 676     if(!prev_inuse(p)) { /* consolidate backward */
 677       p = prev_chunk(p);
 678       unlink(p, bck, fwd);
 679     }
 680     assert(((unsigned long)((char*)p + new_size) & (pagesz-1)) == 0);
 681     assert( ((char*)p + new_size) == ((char*)heap + heap->size) );
 682     top(ar_ptr) = top_chunk = p;
 683     set_head(top_chunk, new_size | PREV_INUSE);
 684     /*check_chunk(ar_ptr, top_chunk);*/
 685   }
 686   top_size = chunksize(top_chunk);
 687   extra = (top_size - pad - MINSIZE - 1) & ~(pagesz - 1);
 688   if(extra < (long)pagesz)
 689     return 0;
 690   /* Try to shrink. */
 691   if(shrink_heap(heap, extra) != 0)
 692     return 0;
 693   ar_ptr->system_mem -= extra;
 694   arena_mem -= extra;
 695
 696   /* Success. Adjust top accordingly. */
 697   set_head(top_chunk, (top_size - extra) | PREV_INUSE);
 698   /*check_chunk(ar_ptr, top_chunk);*/
 699   return 1;
 700 }
 701
 702 /* Create a new arena with initial size "size".  */
 703
 704 static mstate
 705 _int_new_arena(size_t size)
 706 {
 707   mstate a;
 708   heap_info *h;
 709   char *ptr;
 710   unsigned long misalign;
 711
 712   h = new_heap(size + (sizeof(*h) + sizeof(*a) + MALLOC_ALIGNMENT),
 713                mp_.top_pad);
 714   if(!h) {
 715     /* Maybe size is too large to fit in a single heap.  So, just try
 716        to create a minimally-sized arena and let _int_malloc() attempt
 717        to deal with the large request via mmap_chunk().  */
 718     h = new_heap(sizeof(*h) + sizeof(*a) + MALLOC_ALIGNMENT, mp_.top_pad);
 719     if(!h)
 720       return 0;
 721   }
 722   a = h->ar_ptr = (mstate)(h+1);
 723   malloc_init_state(a);
 724   /*a->next = NULL;*/
 725   a->system_mem = a->max_system_mem = h->size;
 726   arena_mem += h->size;
 727
 728   /* Set up the top chunk, with proper alignment. */
 729   ptr = (char *)(a + 1);
 730   misalign = (unsigned long)chunk2mem(ptr) & MALLOC_ALIGN_MASK;
 731   if (misalign > 0)
 732     ptr += MALLOC_ALIGNMENT - misalign;
 733   top(a) = (mchunkptr)ptr;
 734   set_head(top(a), (((char*)h + h->size) - ptr) | PREV_INUSE);
 735
 736   tsd_setspecific(arena_key, (void *)a);
 737   mutex_init(&a->mutex);
 738   (void)mutex_lock(&a->mutex);
 739
 740 #ifdef PER_THREAD
 741   (void)mutex_lock(&list_lock);
 742 #endif
 743
 744   /* Add the new arena to the global list.  */
 745   a->next = main_arena.next;
 746   atomic_write_barrier ();
 747   main_arena.next = a;
 748
 749 #ifdef PER_THREAD
 750   (void)mutex_unlock(&list_lock);
 751 #endif
 752
 753   THREAD_STAT(++(a->stat_lock_loop));
 754
 755   return a;
 756 }
 757
 758
 759 #ifdef PER_THREAD
 760 static mstate
 761 get_free_list (void)
 762 {
 763   mstate result = free_list;
 764   if (result != NULL)
 765     {
 766       (void)mutex_lock(&list_lock);
 767       result = free_list;
 768       if (result != NULL)
 769         free_list = result->next_free;
 770       (void)mutex_unlock(&list_lock);
 771
 772       if (result != NULL)
 773         {
 774           (void)mutex_lock(&result->mutex);
 775           tsd_setspecific(arena_key, (void *)result);
 776           THREAD_STAT(++(result->stat_lock_loop));
 777         }
 778     }
 779
 780   return result;
 781 }
 782
 783
 784 static mstate
 785 reused_arena (void)
 786 {
 787   mstate result;
 788   static mstate next_to_use;
 789   if (next_to_use == NULL)
 790     next_to_use = &main_arena;
 791
 792   result = next_to_use;
 793   do
 794     {
 795       if (!mutex_trylock(&result->mutex))
 796         goto out;
 797
 798       result = result->next;
 799     }
 800   while (result != next_to_use);
 801
 802   /* No arena available.  Wait for the next in line.  */
 803   (void)mutex_lock(&result->mutex);
 804
 805  out:
 806   tsd_setspecific(arena_key, (void *)result);
 807   THREAD_STAT(++(result->stat_lock_loop));
 808   next_to_use = result->next;
 809
 810   return result;
 811 }
 812 #endif
 813
 814 static mstate
 815 internal_function
 816 arena_get2(mstate a_tsd, size_t size)
 817 {
 818   mstate a;
 819
 820 #ifdef PER_THREAD
 821   static size_t narenas_limit;
 822
 823   a = get_free_list ();
 824   if (a == NULL)
 825     {
 826       /* Nothing immediately available, so generate a new arena.  */
 827       if (narenas_limit == 0)
 828         {
 829           if (mp_.arena_max != 0)
 830             narenas_limit = mp_.arena_max;
 831           else
 832             {
 833               int n  = __get_nprocs ();
 834
 835               if (n >= 1)
 836                 narenas_limit = NARENAS_FROM_NCORES (n);
 837               else
 838                 /* We have no information about the system.  Assume two
 839                    cores.  */
 840                 narenas_limit = NARENAS_FROM_NCORES (2);
 841             }
 842         }
 843     repeat:;
 844       size_t n = narenas;
 845       if (__builtin_expect (n <= mp_.arena_test || n < narenas_limit, 0))
 846         {
 847           if (catomic_compare_and_exchange_bool_acq (&narenas, n + 1, n))
 848             goto repeat;
 849           a = _int_new_arena (size);
 850           if (__builtin_expect (a == NULL, 0))
 851             catomic_decrement (&narenas);
 852         }
 853       else
 854         a = reused_arena ();
 855     }
 856 #else
 857   if(!a_tsd)
 858     a = a_tsd = &main_arena;
 859   else {
 860     a = a_tsd->next;
 861     if(!a) {
 862       /* This can only happen while initializing the new arena. */
 863       (void)mutex_lock(&main_arena.mutex);
 864       THREAD_STAT(++(main_arena.stat_lock_wait));
 865       return &main_arena;
 866     }
 867   }
 868
 869   /* Check the global, circularly linked list for available arenas. */
 870   bool retried = false;
 871  repeat:
 872   do {
 873     if(!mutex_trylock(&a->mutex)) {
 874       if (retried)
 875         (void)mutex_unlock(&list_lock);
 876       THREAD_STAT(++(a->stat_lock_loop));
 877       tsd_setspecific(arena_key, (void *)a);
 878       return a;
 879     }
 880     a = a->next;
 881   } while(a != a_tsd);
 882
 883   /* If not even the list_lock can be obtained, try again.  This can
 884      happen during `atfork', or for example on systems where thread
 885      creation makes it temporarily impossible to obtain _any_
 886      locks. */
 887   if(!retried && mutex_trylock(&list_lock)) {
 888     /* We will block to not run in a busy loop.  */
 889     (void)mutex_lock(&list_lock);
 890
 891     /* Since we blocked there might be an arena available now.  */
 892     retried = true;
 893     a = a_tsd;
 894     goto repeat;
 895   }
 896
 897   /* Nothing immediately available, so generate a new arena.  */
 898   a = _int_new_arena(size);
 899   (void)mutex_unlock(&list_lock);
 900 #endif
 901
 902   return a;
 903 }
 904
 905 #ifdef PER_THREAD
 906 static void __attribute__ ((section ("__libc_thread_freeres_fn")))
 907 arena_thread_freeres (void)
 908 {
 909   void *vptr = NULL;
 910   mstate a = tsd_getspecific(arena_key, vptr);
 911   tsd_setspecific(arena_key, NULL);
 912
 913   if (a != NULL)
 914     {
 915       (void)mutex_lock(&list_lock);
 916       a->next_free = free_list;
 917       free_list = a;
 918       (void)mutex_unlock(&list_lock);
 919     }
 920 }
 921 text_set_element (__libc_thread_subfreeres, arena_thread_freeres);
 922 #endif
 923
 924 /*
 925  * Local variables:
 926  * c-basic-offset: 2
 927  * End:
 928  */