039d70ff184811ece5a9d699068d381b67570ba9
[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 /* $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 static mstate
790 internal_function
791 #if __STD_C
792 arena_get2(mstate a_tsd, size_t size)
793 #else
794 arena_get2(a_tsd, size) mstate a_tsd; size_t size;
795 #endif
796 {
797   mstate a;
798
799   if(!a_tsd)
800     a = a_tsd = &main_arena;
801   else {
802     a = a_tsd->next;
803     if(!a) {
804       /* This can only happen while initializing the new arena. */
805       (void)mutex_lock(&main_arena.mutex);
806       THREAD_STAT(++(main_arena.stat_lock_wait));
807       return &main_arena;
808     }
809   }
810
811   /* Check the global, circularly linked list for available arenas. */
812   bool retried = false;
813  repeat:
814   do {
815     if(!mutex_trylock(&a->mutex)) {
816       if (retried)
817         (void)mutex_unlock(&list_lock);
818       THREAD_STAT(++(a->stat_lock_loop));
819       tsd_setspecific(arena_key, (Void_t *)a);
820       return a;
821     }
822     a = a->next;
823   } while(a != a_tsd);
824
825   /* If not even the list_lock can be obtained, try again.  This can
826      happen during `atfork', or for example on systems where thread
827      creation makes it temporarily impossible to obtain _any_
828      locks. */
829   if(!retried && mutex_trylock(&list_lock)) {
830     /* We will block to not run in a busy loop.  */
831     (void)mutex_lock(&list_lock);
832
833     /* Since we blocked there might be an arena available now.  */
834     retried = true;
835     a = a_tsd;
836     goto repeat;
837   }
838
839   /* Nothing immediately available, so generate a new arena.  */
840   a = _int_new_arena(size);
841   if(a)
842     {
843       tsd_setspecific(arena_key, (Void_t *)a);
844       mutex_init(&a->mutex);
845       mutex_lock(&a->mutex); /* remember result */
846
847       /* Add the new arena to the global list.  */
848       a->next = main_arena.next;
849       atomic_write_barrier ();
850       main_arena.next = a;
851
852       THREAD_STAT(++(a->stat_lock_loop));
853     }
854   (void)mutex_unlock(&list_lock);
855
856   return a;
857 }
858
859 /* Create a new arena with initial size "size".  */
860
861 mstate
862 _int_new_arena(size_t size)
863 {
864   mstate a;
865   heap_info *h;
866   char *ptr;
867   unsigned long misalign;
868
869   h = new_heap(size + (sizeof(*h) + sizeof(*a) + MALLOC_ALIGNMENT),
870                mp_.top_pad);
871   if(!h) {
872     /* Maybe size is too large to fit in a single heap.  So, just try
873        to create a minimally-sized arena and let _int_malloc() attempt
874        to deal with the large request via mmap_chunk().  */
875     h = new_heap(sizeof(*h) + sizeof(*a) + MALLOC_ALIGNMENT, mp_.top_pad);
876     if(!h)
877       return 0;
878   }
879   a = h->ar_ptr = (mstate)(h+1);
880   malloc_init_state(a);
881   /*a->next = NULL;*/
882   a->system_mem = a->max_system_mem = h->size;
883   arena_mem += h->size;
884 #ifdef NO_THREADS
885   if((unsigned long)(mp_.mmapped_mem + arena_mem + main_arena.system_mem) >
886      mp_.max_total_mem)
887     mp_.max_total_mem = mp_.mmapped_mem + arena_mem + main_arena.system_mem;
888 #endif
889
890   /* Set up the top chunk, with proper alignment. */
891   ptr = (char *)(a + 1);
892   misalign = (unsigned long)chunk2mem(ptr) & MALLOC_ALIGN_MASK;
893   if (misalign > 0)
894     ptr += MALLOC_ALIGNMENT - misalign;
895   top(a) = (mchunkptr)ptr;
896   set_head(top(a), (((char*)h + h->size) - ptr) | PREV_INUSE);
897
898   return a;
899 }
900
901 #endif /* USE_ARENAS */
902
903 /*
904  * Local variables:
905  * c-basic-offset: 2
906  * End:
907  */