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