(grow_heap): When growing bail even if new_size is negative.
[kopensolaris-gnu/glibc.git] / 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 USE_TLS || (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 && defined USE_TLS && !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 && defined USE_TLS && !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 && defined USE_TLS
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  */