malloc/arena.c

   1 /* Malloc implementation for multiple threads without lock contention.
   2    Copyright (C) 2001, 2002, 2003, 2004, 2005 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 not,
  18    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19    Boston, MA 02111-1307, USA.  */
  20
  21 /* $Id$ */
  22
  23 #include <stdbool.h>
  24
  25 /* Compile-time constants.  */
  26
  27 #define HEAP_MIN_SIZE (32*1024)
  28 #ifndef HEAP_MAX_SIZE
  29 #define HEAP_MAX_SIZE (1024*1024) /* must be a power of two */
  30 #endif
  31
  32 /* HEAP_MIN_SIZE and HEAP_MAX_SIZE limit the size of mmap()ed heaps
  33    that are dynamically created for multi-threaded programs.  The
  34    maximum size must be a power of two, for fast determination of
  35    which heap belongs to a chunk.  It should be much larger than the
  36    mmap threshold, so that requests with a size just below that
  37    threshold can be fulfilled without creating too many heaps.  */
  38
  39
  40 #ifndef THREAD_STATS
  41 #define THREAD_STATS 0
  42 #endif
  43
  44 /* If THREAD_STATS is non-zero, some statistics on mutex locking are
  45    computed.  */
  46
  47 /***************************************************************************/
  48
  49 #define top(ar_ptr) ((ar_ptr)->top)
  50
  51 /* A heap is a single contiguous memory region holding (coalesceable)
  52    malloc_chunks.  It is allocated with mmap() and always starts at an
  53    address aligned to HEAP_MAX_SIZE.  Not used unless compiling with
  54    USE_ARENAS. */
  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 pad;    /* Make sure the following data is properly aligned. */
  61 } heap_info;
  62
  63 /* Thread specific data */
  64
  65 static tsd_key_t arena_key;
  66 static mutex_t list_lock;
  67
  68 #if THREAD_STATS
  69 static int stat_n_heaps;
  70 #define THREAD_STAT(x) x
  71 #else
  72 #define THREAD_STAT(x) do ; while(0)
  73 #endif
  74
  75 /* Mapped memory in non-main arenas (reliable only for NO_THREADS). */
  76 static unsigned long arena_mem;
  77
  78 /* Already initialized? */
  79 int __malloc_initialized = -1;
  80
  81 /**************************************************************************/
  82
  83 #if USE_ARENAS
  84
  85 /* arena_get() acquires an arena and locks the corresponding mutex.
  86    First, try the one last locked successfully by this thread.  (This
  87    is the common case and handled with a macro for speed.)  Then, loop
  88    once over the circularly linked list of arenas.  If no arena is
  89    readily available, create a new one.  In this latter case, `size'
  90    is just a hint as to how much memory will be required immediately
  91    in the new arena. */
  92
  93 #define arena_get(ptr, size) do { \
  94   Void_t *vptr = NULL; \
  95   ptr = (mstate)tsd_getspecific(arena_key, vptr); \
  96   if(ptr && !mutex_trylock(&ptr->mutex)) { \
  97     THREAD_STAT(++(ptr->stat_lock_direct)); \
  98   } else \
  99     ptr = arena_get2(ptr, (size)); \
 100 } while(0)
 101
 102 /* find the heap and corresponding arena for a given ptr */
 103
 104 #define heap_for_ptr(ptr) \
 105  ((heap_info *)((unsigned long)(ptr) & ~(HEAP_MAX_SIZE-1)))
 106 #define arena_for_chunk(ptr) \
 107  (chunk_non_main_arena(ptr) ? heap_for_ptr(ptr)->ar_ptr : &main_arena)
 108
 109 #else /* !USE_ARENAS */
 110
 111 /* There is only one arena, main_arena. */
 112
 113 #if THREAD_STATS
 114 #define arena_get(ar_ptr, sz) do { \
 115   ar_ptr = &main_arena; \
 116   if(!mutex_trylock(&ar_ptr->mutex)) \
 117     ++(ar_ptr->stat_lock_direct); \
 118   else { \
 119     (void)mutex_lock(&ar_ptr->mutex); \
 120     ++(ar_ptr->stat_lock_wait); \
 121   } \
 122 } while(0)
 123 #else
 124 #define arena_get(ar_ptr, sz) do { \
 125   ar_ptr = &main_arena; \
 126   (void)mutex_lock(&ar_ptr->mutex); \
 127 } while(0)
 128 #endif
 129 #define arena_for_chunk(ptr) (&main_arena)
 130
 131 #endif /* USE_ARENAS */
 132
 133 /**************************************************************************/
 134
 135 #ifndef NO_THREADS
 136
 137 /* atfork support.  */
 138
 139 static __malloc_ptr_t (*save_malloc_hook) (size_t __size,
 140                                            __const __malloc_ptr_t);
 141 # if !defined _LIBC || !defined USE_TLS || (defined SHARED && !USE___THREAD)
 142 static __malloc_ptr_t (*save_memalign_hook) (size_t __align, size_t __size,
 143                                              __const __malloc_ptr_t);
 144 # endif
 145 static void           (*save_free_hook) (__malloc_ptr_t __ptr,
 146                                          __const __malloc_ptr_t);
 147 static Void_t*        save_arena;
 148
 149 /* Magic value for the thread-specific arena pointer when
 150    malloc_atfork() is in use.  */
 151
 152 #define ATFORK_ARENA_PTR ((Void_t*)-1)
 153
 154 /* The following hooks are used while the `atfork' handling mechanism
 155    is active. */
 156
 157 static Void_t*
 158 malloc_atfork(size_t sz, const Void_t *caller)
 159 {
 160   Void_t *vptr = NULL;
 161   Void_t *victim;
 162
 163   tsd_getspecific(arena_key, vptr);
 164   if(vptr == ATFORK_ARENA_PTR) {
 165     /* We are the only thread that may allocate at all.  */
 166     if(save_malloc_hook != malloc_check) {
 167       return _int_malloc(&main_arena, sz);
 168     } else {
 169       if(top_check()<0)
 170         return 0;
 171       victim = _int_malloc(&main_arena, sz+1);
 172       return mem2mem_check(victim, sz);
 173     }
 174   } else {
 175     /* Suspend the thread until the `atfork' handlers have completed.
 176        By that time, the hooks will have been reset as well, so that
 177        mALLOc() can be used again. */
 178     (void)mutex_lock(&list_lock);
 179     (void)mutex_unlock(&list_lock);
 180     return public_mALLOc(sz);
 181   }
 182 }
 183
 184 static void
 185 free_atfork(Void_t* mem, const Void_t *caller)
 186 {
 187   Void_t *vptr = NULL;
 188   mstate ar_ptr;
 189   mchunkptr p;                          /* chunk corresponding to mem */
 190
 191   if (mem == 0)                              /* free(0) has no effect */
 192     return;
 193
 194   p = mem2chunk(mem);         /* do not bother to replicate free_check here */
 195
 196 #if HAVE_MMAP
 197   if (chunk_is_mmapped(p))                       /* release mmapped memory. */
 198   {
 199     munmap_chunk(p);
 200     return;
 201   }
 202 #endif
 203
 204   ar_ptr = arena_for_chunk(p);
 205   tsd_getspecific(arena_key, vptr);
 206   if(vptr != ATFORK_ARENA_PTR)
 207     (void)mutex_lock(&ar_ptr->mutex);
 208   _int_free(ar_ptr, mem);
 209   if(vptr != ATFORK_ARENA_PTR)
 210     (void)mutex_unlock(&ar_ptr->mutex);
 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_t *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 #if defined _LIBC || defined MALLOC_HOOKS
 293   tsd_setspecific(arena_key, save_arena);
 294   __malloc_hook = save_malloc_hook;
 295   __free_hook = save_free_hook;
 296 #endif
 297   for(ar_ptr = &main_arena;;) {
 298     mutex_init(&ar_ptr->mutex);
 299     ar_ptr = ar_ptr->next;
 300     if(ar_ptr == &main_arena) break;
 301   }
 302   mutex_init(&list_lock);
 303   atfork_recursive_cntr = 0;
 304 }
 305
 306 #else
 307
 308 #define ptmalloc_unlock_all2 ptmalloc_unlock_all
 309
 310 #endif
 311
 312 #endif /* !defined NO_THREADS */
 313
 314 /* Initialization routine. */
 315 #ifdef _LIBC
 316 #include <string.h>
 317 extern char **_environ;
 318
 319 static char *
 320 internal_function
 321 next_env_entry (char ***position)
 322 {
 323   char **current = *position;
 324   char *result = NULL;
 325
 326   while (*current != NULL)
 327     {
 328       if (__builtin_expect ((*current)[0] == 'M', 0)
 329           && (*current)[1] == 'A'
 330           && (*current)[2] == 'L'
 331           && (*current)[3] == 'L'
 332           && (*current)[4] == 'O'
 333           && (*current)[5] == 'C'
 334           && (*current)[6] == '_')
 335         {
 336           result = &(*current)[7];
 337
 338           /* Save current position for next visit.  */
 339           *position = ++current;
 340
 341           break;
 342         }
 343
 344       ++current;
 345     }
 346
 347   return result;
 348 }
 349 #endif /* _LIBC */
 350
 351 /* Set up basic state so that _int_malloc et al can work.  */
 352 static void
 353 ptmalloc_init_minimal (void)
 354 {
 355 #if DEFAULT_TOP_PAD != 0
 356   mp_.top_pad        = DEFAULT_TOP_PAD;
 357 #endif
 358   mp_.n_mmaps_max    = DEFAULT_MMAP_MAX;
 359   mp_.mmap_threshold = DEFAULT_MMAP_THRESHOLD;
 360   mp_.trim_threshold = DEFAULT_TRIM_THRESHOLD;
 361   mp_.pagesize       = malloc_getpagesize;
 362 }
 363
 364
 365 #ifdef _LIBC
 366 # ifdef SHARED
 367 static void *
 368 __failing_morecore (ptrdiff_t d)
 369 {
 370   return (void *) MORECORE_FAILURE;
 371 }
 372
 373 extern struct dl_open_hook *_dl_open_hook;
 374 libc_hidden_proto (_dl_open_hook);
 375 # endif
 376
 377 # if defined SHARED && defined USE_TLS && !USE___THREAD
 378 /* This is called by __pthread_initialize_minimal when it needs to use
 379    malloc to set up the TLS state.  We cannot do the full work of
 380    ptmalloc_init (below) until __pthread_initialize_minimal has finished,
 381    so it has to switch to using the special startup-time hooks while doing
 382    those allocations.  */
 383 void
 384 __libc_malloc_pthread_startup (bool first_time)
 385 {
 386   if (first_time)
 387     {
 388       ptmalloc_init_minimal ();
 389       save_malloc_hook = __malloc_hook;
 390       save_memalign_hook = __memalign_hook;
 391       save_free_hook = __free_hook;
 392       __malloc_hook = malloc_starter;
 393       __memalign_hook = memalign_starter;
 394       __free_hook = free_starter;
 395     }
 396   else
 397     {
 398       __malloc_hook = save_malloc_hook;
 399       __memalign_hook = save_memalign_hook;
 400       __free_hook = save_free_hook;
 401     }
 402 }
 403 # endif
 404 #endif
 405
 406 static void
 407 ptmalloc_init (void)
 408 {
 409 #if __STD_C
 410   const char* s;
 411 #else
 412   char* s;
 413 #endif
 414   int secure = 0;
 415
 416   if(__malloc_initialized >= 0) return;
 417   __malloc_initialized = 0;
 418
 419 #ifdef _LIBC
 420 # if defined SHARED && defined USE_TLS && !USE___THREAD
 421   /* ptmalloc_init_minimal may already have been called via
 422      __libc_malloc_pthread_startup, above.  */
 423   if (mp_.pagesize == 0)
 424 # endif
 425 #endif
 426     ptmalloc_init_minimal();
 427
 428 #ifndef NO_THREADS
 429 # if defined _LIBC && defined USE_TLS
 430   /* We know __pthread_initialize_minimal has already been called,
 431      and that is enough.  */
 432 #   define NO_STARTER
 433 # endif
 434 # ifndef NO_STARTER
 435   /* With some threads implementations, creating thread-specific data
 436      or initializing a mutex may call malloc() itself.  Provide a
 437      simple starter version (realloc() won't work). */
 438   save_malloc_hook = __malloc_hook;
 439   save_memalign_hook = __memalign_hook;
 440   save_free_hook = __free_hook;
 441   __malloc_hook = malloc_starter;
 442   __memalign_hook = memalign_starter;
 443   __free_hook = free_starter;
 444 #  ifdef _LIBC
 445   /* Initialize the pthreads interface. */
 446   if (__pthread_initialize != NULL)
 447     __pthread_initialize();
 448 #  endif /* !defined _LIBC */
 449 # endif /* !defined NO_STARTER */
 450 #endif /* !defined NO_THREADS */
 451   mutex_init(&main_arena.mutex);
 452   main_arena.next = &main_arena;
 453
 454 #if defined _LIBC && defined SHARED
 455   /* In case this libc copy is in a non-default namespace, never use brk.
 456      Likewise if dlopened from statically linked program.  */
 457   Dl_info di;
 458   struct link_map *l;
 459
 460   if (_dl_open_hook != NULL
 461       || (_dl_addr (ptmalloc_init, &di, &l, NULL) != 0
 462           && l->l_ns != LM_ID_BASE))
 463     __morecore = __failing_morecore;
 464 #endif
 465
 466   mutex_init(&list_lock);
 467   tsd_key_create(&arena_key, NULL);
 468   tsd_setspecific(arena_key, (Void_t *)&main_arena);
 469   thread_atfork(ptmalloc_lock_all, ptmalloc_unlock_all, ptmalloc_unlock_all2);
 470 #ifndef NO_THREADS
 471 # ifndef NO_STARTER
 472   __malloc_hook = save_malloc_hook;
 473   __memalign_hook = save_memalign_hook;
 474   __free_hook = save_free_hook;
 475 # else
 476 #  undef NO_STARTER
 477 # endif
 478 #endif
 479 #ifdef _LIBC
 480   secure = __libc_enable_secure;
 481   s = NULL;
 482   if (__builtin_expect (_environ != NULL, 1))
 483     {
 484       char **runp = _environ;
 485       char *envline;
 486
 487       while (__builtin_expect ((envline = next_env_entry (&runp)) != NULL,
 488                                0))
 489         {
 490           size_t len = strcspn (envline, "=");
 491
 492           if (envline[len] != '=')
 493             /* This is a "MALLOC_" variable at the end of the string
 494                without a '=' character.  Ignore it since otherwise we
 495                will access invalid memory below.  */
 496             continue;
 497
 498           switch (len)
 499             {
 500             case 6:
 501               if (memcmp (envline, "CHECK_", 6) == 0)
 502                 s = &envline[7];
 503               break;
 504             case 8:
 505               if (! secure)
 506                 {
 507                   if (memcmp (envline, "TOP_PAD_", 8) == 0)
 508                     mALLOPt(M_TOP_PAD, atoi(&envline[9]));
 509                   else if (memcmp (envline, "PERTURB_", 8) == 0)
 510                     mALLOPt(M_PERTURB, atoi(&envline[9]));
 511                 }
 512               break;
 513             case 9:
 514               if (! secure && memcmp (envline, "MMAP_MAX_", 9) == 0)
 515                 mALLOPt(M_MMAP_MAX, atoi(&envline[10]));
 516               break;
 517             case 15:
 518               if (! secure)
 519                 {
 520                   if (memcmp (envline, "TRIM_THRESHOLD_", 15) == 0)
 521                     mALLOPt(M_TRIM_THRESHOLD, atoi(&envline[16]));
 522                   else if (memcmp (envline, "MMAP_THRESHOLD_", 15) == 0)
 523                     mALLOPt(M_MMAP_THRESHOLD, atoi(&envline[16]));
 524                 }
 525               break;
 526             default:
 527               break;
 528             }
 529         }
 530     }
 531 #else
 532   if (! secure)
 533     {
 534       if((s = getenv("MALLOC_TRIM_THRESHOLD_")))
 535         mALLOPt(M_TRIM_THRESHOLD, atoi(s));
 536       if((s = getenv("MALLOC_TOP_PAD_")))
 537         mALLOPt(M_TOP_PAD, atoi(s));
 538       if((s = getenv("MALLOC_PERTURB_")))
 539         mALLOPt(M_PERTURB, atoi(s));
 540       if((s = getenv("MALLOC_MMAP_THRESHOLD_")))
 541         mALLOPt(M_MMAP_THRESHOLD, atoi(s));
 542       if((s = getenv("MALLOC_MMAP_MAX_")))
 543         mALLOPt(M_MMAP_MAX, atoi(s));
 544     }
 545   s = getenv("MALLOC_CHECK_");
 546 #endif
 547   if(s) {
 548     if(s[0]) mALLOPt(M_CHECK_ACTION, (int)(s[0] - '0'));
 549     if (check_action != 0)
 550       __malloc_check_init();
 551   }
 552   if(__malloc_initialize_hook != NULL)
 553     (*__malloc_initialize_hook)();
 554   __malloc_initialized = 1;
 555 }
 556
 557 /* There are platforms (e.g. Hurd) with a link-time hook mechanism. */
 558 #ifdef thread_atfork_static
 559 thread_atfork_static(ptmalloc_lock_all, ptmalloc_unlock_all, \
 560                      ptmalloc_unlock_all2)
 561 #endif
 562
 563 \f
 564
 565 /* Managing heaps and arenas (for concurrent threads) */
 566
 567 #if USE_ARENAS
 568
 569 #if MALLOC_DEBUG > 1
 570
 571 /* Print the complete contents of a single heap to stderr. */
 572
 573 static void
 574 #if __STD_C
 575 dump_heap(heap_info *heap)
 576 #else
 577 dump_heap(heap) heap_info *heap;
 578 #endif
 579 {
 580   char *ptr;
 581   mchunkptr p;
 582
 583   fprintf(stderr, "Heap %p, size %10lx:\n", heap, (long)heap->size);
 584   ptr = (heap->ar_ptr != (mstate)(heap+1)) ?
 585     (char*)(heap + 1) : (char*)(heap + 1) + sizeof(struct malloc_state);
 586   p = (mchunkptr)(((unsigned long)ptr + MALLOC_ALIGN_MASK) &
 587                   ~MALLOC_ALIGN_MASK);
 588   for(;;) {
 589     fprintf(stderr, "chunk %p size %10lx", p, (long)p->size);
 590     if(p == top(heap->ar_ptr)) {
 591       fprintf(stderr, " (top)\n");
 592       break;
 593     } else if(p->size == (0|PREV_INUSE)) {
 594       fprintf(stderr, " (fence)\n");
 595       break;
 596     }
 597     fprintf(stderr, "\n");
 598     p = next_chunk(p);
 599   }
 600 }
 601
 602 #endif /* MALLOC_DEBUG > 1 */
 603
 604 /* If consecutive mmap (0, HEAP_MAX_SIZE << 1, ...) calls return decreasing
 605    addresses as opposed to increasing, new_heap would badly fragment the
 606    address space.  In that case remember the second HEAP_MAX_SIZE part
 607    aligned to HEAP_MAX_SIZE from last mmap (0, HEAP_MAX_SIZE << 1, ...)
 608    call (if it is already aligned) and try to reuse it next time.  We need
 609    no locking for it, as kernel ensures the atomicity for us - worst case
 610    we'll call mmap (addr, HEAP_MAX_SIZE, ...) for some value of addr in
 611    multiple threads, but only one will succeed.  */
 612 static char *aligned_heap_area;
 613
 614 /* Create a new heap.  size is automatically rounded up to a multiple
 615    of the page size. */
 616
 617 static heap_info *
 618 internal_function
 619 #if __STD_C
 620 new_heap(size_t size, size_t top_pad)
 621 #else
 622 new_heap(size, top_pad) size_t size, top_pad;
 623 #endif
 624 {
 625   size_t page_mask = malloc_getpagesize - 1;
 626   char *p1, *p2;
 627   unsigned long ul;
 628   heap_info *h;
 629
 630   if(size+top_pad < HEAP_MIN_SIZE)
 631     size = HEAP_MIN_SIZE;
 632   else if(size+top_pad <= HEAP_MAX_SIZE)
 633     size += top_pad;
 634   else if(size > HEAP_MAX_SIZE)
 635     return 0;
 636   else
 637     size = HEAP_MAX_SIZE;
 638   size = (size + page_mask) & ~page_mask;
 639
 640   /* A memory region aligned to a multiple of HEAP_MAX_SIZE is needed.
 641      No swap space needs to be reserved for the following large
 642      mapping (on Linux, this is the case for all non-writable mappings
 643      anyway). */
 644   p2 = MAP_FAILED;
 645   if(aligned_heap_area) {
 646     p2 = (char *)MMAP(aligned_heap_area, HEAP_MAX_SIZE, PROT_NONE,
 647                       MAP_PRIVATE|MAP_NORESERVE);
 648     aligned_heap_area = NULL;
 649     if (p2 != MAP_FAILED && ((unsigned long)p2 & (HEAP_MAX_SIZE-1))) {
 650       munmap(p2, HEAP_MAX_SIZE);
 651       p2 = MAP_FAILED;
 652     }
 653   }
 654   if(p2 == MAP_FAILED) {
 655     p1 = (char *)MMAP(0, HEAP_MAX_SIZE<<1, PROT_NONE,
 656                       MAP_PRIVATE|MAP_NORESERVE);
 657     if(p1 != MAP_FAILED) {
 658       p2 = (char *)(((unsigned long)p1 + (HEAP_MAX_SIZE-1))
 659                     & ~(HEAP_MAX_SIZE-1));
 660       ul = p2 - p1;
 661       if (ul)
 662         munmap(p1, ul);
 663       else
 664         aligned_heap_area = p2 + HEAP_MAX_SIZE;
 665       munmap(p2 + HEAP_MAX_SIZE, HEAP_MAX_SIZE - ul);
 666     } else {
 667       /* Try to take the chance that an allocation of only HEAP_MAX_SIZE
 668          is already aligned. */
 669       p2 = (char *)MMAP(0, HEAP_MAX_SIZE, PROT_NONE, MAP_PRIVATE|MAP_NORESERVE);
 670       if(p2 == MAP_FAILED)
 671         return 0;
 672       if((unsigned long)p2 & (HEAP_MAX_SIZE-1)) {
 673         munmap(p2, HEAP_MAX_SIZE);
 674         return 0;
 675       }
 676     }
 677   }
 678   if(mprotect(p2, size, PROT_READ|PROT_WRITE) != 0) {
 679     munmap(p2, HEAP_MAX_SIZE);
 680     return 0;
 681   }
 682   h = (heap_info *)p2;
 683   h->size = size;
 684   THREAD_STAT(stat_n_heaps++);
 685   return h;
 686 }
 687
 688 /* Grow or shrink a heap.  size is automatically rounded up to a
 689    multiple of the page size if it is positive. */
 690
 691 static int
 692 #if __STD_C
 693 grow_heap(heap_info *h, long diff)
 694 #else
 695 grow_heap(h, diff) heap_info *h; long diff;
 696 #endif
 697 {
 698   size_t page_mask = malloc_getpagesize - 1;
 699   long new_size;
 700
 701   if(diff >= 0) {
 702     diff = (diff + page_mask) & ~page_mask;
 703     new_size = (long)h->size + diff;
 704     if(new_size > HEAP_MAX_SIZE)
 705       return -1;
 706     if(mprotect((char *)h + h->size, diff, PROT_READ|PROT_WRITE) != 0)
 707       return -2;
 708   } else {
 709     new_size = (long)h->size + diff;
 710     if(new_size < (long)sizeof(*h))
 711       return -1;
 712     /* Try to re-map the extra heap space freshly to save memory, and
 713        make it inaccessible. */
 714     if((char *)MMAP((char *)h + new_size, -diff, PROT_NONE,
 715                     MAP_PRIVATE|MAP_FIXED) == (char *) MAP_FAILED)
 716       return -2;
 717     /*fprintf(stderr, "shrink %p %08lx\n", h, new_size);*/
 718   }
 719   h->size = new_size;
 720   return 0;
 721 }
 722
 723 /* Delete a heap. */
 724
 725 #define delete_heap(heap) \
 726   do {                                                          \
 727     if ((char *)(heap) + HEAP_MAX_SIZE == aligned_heap_area)    \
 728       aligned_heap_area = NULL;                                 \
 729     munmap((char*)(heap), HEAP_MAX_SIZE);                       \
 730   } while (0)
 731
 732 static int
 733 internal_function
 734 #if __STD_C
 735 heap_trim(heap_info *heap, size_t pad)
 736 #else
 737 heap_trim(heap, pad) heap_info *heap; size_t pad;
 738 #endif
 739 {
 740   mstate ar_ptr = heap->ar_ptr;
 741   unsigned long pagesz = mp_.pagesize;
 742   mchunkptr top_chunk = top(ar_ptr), p, bck, fwd;
 743   heap_info *prev_heap;
 744   long new_size, top_size, extra;
 745
 746   /* Can this heap go away completely? */
 747   while(top_chunk == chunk_at_offset(heap, sizeof(*heap))) {
 748     prev_heap = heap->prev;
 749     p = chunk_at_offset(prev_heap, prev_heap->size - (MINSIZE-2*SIZE_SZ));
 750     assert(p->size == (0|PREV_INUSE)); /* must be fencepost */
 751     p = prev_chunk(p);
 752     new_size = chunksize(p) + (MINSIZE-2*SIZE_SZ);
 753     assert(new_size>0 && new_size<(long)(2*MINSIZE));
 754     if(!prev_inuse(p))
 755       new_size += p->prev_size;
 756     assert(new_size>0 && new_size<HEAP_MAX_SIZE);
 757     if(new_size + (HEAP_MAX_SIZE - prev_heap->size) < pad + MINSIZE + pagesz)
 758       break;
 759     ar_ptr->system_mem -= heap->size;
 760     arena_mem -= heap->size;
 761     delete_heap(heap);
 762     heap = prev_heap;
 763     if(!prev_inuse(p)) { /* consolidate backward */
 764       p = prev_chunk(p);
 765       unlink(p, bck, fwd);
 766     }
 767     assert(((unsigned long)((char*)p + new_size) & (pagesz-1)) == 0);
 768     assert( ((char*)p + new_size) == ((char*)heap + heap->size) );
 769     top(ar_ptr) = top_chunk = p;
 770     set_head(top_chunk, new_size | PREV_INUSE);
 771     /*check_chunk(ar_ptr, top_chunk);*/
 772   }
 773   top_size = chunksize(top_chunk);
 774   extra = ((top_size - pad - MINSIZE + (pagesz-1))/pagesz - 1) * pagesz;
 775   if(extra < (long)pagesz)
 776     return 0;
 777   /* Try to shrink. */
 778   if(grow_heap(heap, -extra) != 0)
 779     return 0;
 780   ar_ptr->system_mem -= extra;
 781   arena_mem -= extra;
 782
 783   /* Success. Adjust top accordingly. */
 784   set_head(top_chunk, (top_size - extra) | PREV_INUSE);
 785   /*check_chunk(ar_ptr, top_chunk);*/
 786   return 1;
 787 }
 788
 789 /* Create a new arena with initial size "size".  */
 790
 791 static mstate
 792 _int_new_arena(size_t size)
 793 {
 794   mstate a;
 795   heap_info *h;
 796   char *ptr;
 797   unsigned long misalign;
 798
 799   h = new_heap(size + (sizeof(*h) + sizeof(*a) + MALLOC_ALIGNMENT),
 800                mp_.top_pad);
 801   if(!h) {
 802     /* Maybe size is too large to fit in a single heap.  So, just try
 803        to create a minimally-sized arena and let _int_malloc() attempt
 804        to deal with the large request via mmap_chunk().  */
 805     h = new_heap(sizeof(*h) + sizeof(*a) + MALLOC_ALIGNMENT, mp_.top_pad);
 806     if(!h)
 807       return 0;
 808   }
 809   a = h->ar_ptr = (mstate)(h+1);
 810   malloc_init_state(a);
 811   /*a->next = NULL;*/
 812   a->system_mem = a->max_system_mem = h->size;
 813   arena_mem += h->size;
 814 #ifdef NO_THREADS
 815   if((unsigned long)(mp_.mmapped_mem + arena_mem + main_arena.system_mem) >
 816      mp_.max_total_mem)
 817     mp_.max_total_mem = mp_.mmapped_mem + arena_mem + main_arena.system_mem;
 818 #endif
 819
 820   /* Set up the top chunk, with proper alignment. */
 821   ptr = (char *)(a + 1);
 822   misalign = (unsigned long)chunk2mem(ptr) & MALLOC_ALIGN_MASK;
 823   if (misalign > 0)
 824     ptr += MALLOC_ALIGNMENT - misalign;
 825   top(a) = (mchunkptr)ptr;
 826   set_head(top(a), (((char*)h + h->size) - ptr) | PREV_INUSE);
 827
 828   return a;
 829 }
 830
 831 static mstate
 832 internal_function
 833 #if __STD_C
 834 arena_get2(mstate a_tsd, size_t size)
 835 #else
 836 arena_get2(a_tsd, size) mstate a_tsd; size_t size;
 837 #endif
 838 {
 839   mstate a;
 840
 841   if(!a_tsd)
 842     a = a_tsd = &main_arena;
 843   else {
 844     a = a_tsd->next;
 845     if(!a) {
 846       /* This can only happen while initializing the new arena. */
 847       (void)mutex_lock(&main_arena.mutex);
 848       THREAD_STAT(++(main_arena.stat_lock_wait));
 849       return &main_arena;
 850     }
 851   }
 852
 853   /* Check the global, circularly linked list for available arenas. */
 854   bool retried = false;
 855  repeat:
 856   do {
 857     if(!mutex_trylock(&a->mutex)) {
 858       if (retried)
 859         (void)mutex_unlock(&list_lock);
 860       THREAD_STAT(++(a->stat_lock_loop));
 861       tsd_setspecific(arena_key, (Void_t *)a);
 862       return a;
 863     }
 864     a = a->next;
 865   } while(a != a_tsd);
 866
 867   /* If not even the list_lock can be obtained, try again.  This can
 868      happen during `atfork', or for example on systems where thread
 869      creation makes it temporarily impossible to obtain _any_
 870      locks. */
 871   if(!retried && mutex_trylock(&list_lock)) {
 872     /* We will block to not run in a busy loop.  */
 873     (void)mutex_lock(&list_lock);
 874
 875     /* Since we blocked there might be an arena available now.  */
 876     retried = true;
 877     a = a_tsd;
 878     goto repeat;
 879   }
 880
 881   /* Nothing immediately available, so generate a new arena.  */
 882   a = _int_new_arena(size);
 883   if(a)
 884     {
 885       tsd_setspecific(arena_key, (Void_t *)a);
 886       mutex_init(&a->mutex);
 887       mutex_lock(&a->mutex); /* remember result */
 888
 889       /* Add the new arena to the global list.  */
 890       a->next = main_arena.next;
 891       atomic_write_barrier ();
 892       main_arena.next = a;
 893
 894       THREAD_STAT(++(a->stat_lock_loop));
 895     }
 896   (void)mutex_unlock(&list_lock);
 897
 898   return a;
 899 }
 900
 901 #endif /* USE_ARENAS */
 902
 903 /*
 904  * Local variables:
 905  * c-basic-offset: 2
 906  * End:
 907  */