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