malloc/arena.c

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