1/* Malloc implementation for multiple threads without lock contention.
2 Copyright (C) 2001-2018 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
18 not, see <http://www.gnu.org/licenses/>. */
19
20#include <stdbool.h>
21
22#if HAVE_TUNABLES
23# define TUNABLE_NAMESPACE malloc
24#endif
25#include <elf/dl-tunables.h>
26
27/* Compile-time constants. */
28
29#define HEAP_MIN_SIZE (32 * 1024)
30#ifndef HEAP_MAX_SIZE
31# ifdef DEFAULT_MMAP_THRESHOLD_MAX
32# define HEAP_MAX_SIZE (2 * DEFAULT_MMAP_THRESHOLD_MAX)
33# else
34# define HEAP_MAX_SIZE (1024 * 1024) /* must be a power of two */
35# endif
36#endif
37
38/* HEAP_MIN_SIZE and HEAP_MAX_SIZE limit the size of mmap()ed heaps
39 that are dynamically created for multi-threaded programs. The
40 maximum size must be a power of two, for fast determination of
41 which heap belongs to a chunk. It should be much larger than the
42 mmap threshold, so that requests with a size just below that
43 threshold can be fulfilled without creating too many heaps. */
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. */
52
53typedef struct _heap_info
54{
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 mprotect_size; /* Size in bytes that has been mprotected
59 PROT_READ|PROT_WRITE. */
60 /* Make sure the following data is properly aligned, particularly
61 that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
62 MALLOC_ALIGNMENT. */
63 char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];
64} heap_info;
65
66/* Get a compile-time error if the heap_info padding is not correct
67 to make alignment work as expected in sYSMALLOc. */
68extern int sanity_check_heap_info_alignment[(sizeof (heap_info)
69 + 2 * SIZE_SZ) % MALLOC_ALIGNMENT
70 ? -1 : 1];
71
72/* Thread specific data. */
73
74static __thread mstate thread_arena attribute_tls_model_ie;
75
76/* Arena free list. free_list_lock synchronizes access to the
77 free_list variable below, and the next_free and attached_threads
78 members of struct malloc_state objects. No other locks must be
79 acquired after free_list_lock has been acquired. */
80
81__libc_lock_define_initialized (static, free_list_lock);
82static size_t narenas = 1;
83static mstate free_list;
84
85/* list_lock prevents concurrent writes to the next member of struct
86 malloc_state objects.
87
88 Read access to the next member is supposed to synchronize with the
89 atomic_write_barrier and the write to the next member in
90 _int_new_arena. This suffers from data races; see the FIXME
91 comments in _int_new_arena and reused_arena.
92
93 list_lock also prevents concurrent forks. At the time list_lock is
94 acquired, no arena lock must have been acquired, but it is
95 permitted to acquire arena locks subsequently, while list_lock is
96 acquired. */
97__libc_lock_define_initialized (static, list_lock);
98
99/* Already initialized? */
100int __malloc_initialized = -1;
101
102/**************************************************************************/
103
104
105/* arena_get() acquires an arena and locks the corresponding mutex.
106 First, try the one last locked successfully by this thread. (This
107 is the common case and handled with a macro for speed.) Then, loop
108 once over the circularly linked list of arenas. If no arena is
109 readily available, create a new one. In this latter case, `size'
110 is just a hint as to how much memory will be required immediately
111 in the new arena. */
112
113#define arena_get(ptr, size) do { \
114 ptr = thread_arena; \
115 arena_lock (ptr, size); \
116 } while (0)
117
118#define arena_lock(ptr, size) do { \
119 if (ptr) \
120 __libc_lock_lock (ptr->mutex); \
121 else \
122 ptr = arena_get2 ((size), NULL); \
123 } while (0)
124
125/* find the heap and corresponding arena for a given ptr */
126
127#define heap_for_ptr(ptr) \
128 ((heap_info *) ((unsigned long) (ptr) & ~(HEAP_MAX_SIZE - 1)))
129#define arena_for_chunk(ptr) \
130 (chunk_main_arena (ptr) ? &main_arena : heap_for_ptr (ptr)->ar_ptr)
131
132
133/**************************************************************************/
134
135/* atfork support. */
136
137/* The following three functions are called around fork from a
138 multi-threaded process. We do not use the general fork handler
139 mechanism to make sure that our handlers are the last ones being
140 called, so that other fork handlers can use the malloc
141 subsystem. */
142
143void
144__malloc_fork_lock_parent (void)
145{
146 if (__malloc_initialized < 1)
147 return;
148
149 /* We do not acquire free_list_lock here because we completely
150 reconstruct free_list in __malloc_fork_unlock_child. */
151
152 __libc_lock_lock (list_lock);
153
154 for (mstate ar_ptr = &main_arena;; )
155 {
156 __libc_lock_lock (ar_ptr->mutex);
157 ar_ptr = ar_ptr->next;
158 if (ar_ptr == &main_arena)
159 break;
160 }
161}
162
163void
164__malloc_fork_unlock_parent (void)
165{
166 if (__malloc_initialized < 1)
167 return;
168
169 for (mstate ar_ptr = &main_arena;; )
170 {
171 __libc_lock_unlock (ar_ptr->mutex);
172 ar_ptr = ar_ptr->next;
173 if (ar_ptr == &main_arena)
174 break;
175 }
176 __libc_lock_unlock (list_lock);
177}
178
179void
180__malloc_fork_unlock_child (void)
181{
182 if (__malloc_initialized < 1)
183 return;
184
185 /* Push all arenas to the free list, except thread_arena, which is
186 attached to the current thread. */
187 __libc_lock_init (free_list_lock);
188 if (thread_arena != NULL)
189 thread_arena->attached_threads = 1;
190 free_list = NULL;
191 for (mstate ar_ptr = &main_arena;; )
192 {
193 __libc_lock_init (ar_ptr->mutex);
194 if (ar_ptr != thread_arena)
195 {
196 /* This arena is no longer attached to any thread. */
197 ar_ptr->attached_threads = 0;
198 ar_ptr->next_free = free_list;
199 free_list = ar_ptr;
200 }
201 ar_ptr = ar_ptr->next;
202 if (ar_ptr == &main_arena)
203 break;
204 }
205
206 __libc_lock_init (list_lock);
207}
208
209#if HAVE_TUNABLES
210static inline int do_set_mallopt_check (int32_t value);
211void
212TUNABLE_CALLBACK (set_mallopt_check) (tunable_val_t *valp)
213{
214 int32_t value = (int32_t) valp->numval;
215 if (value != 0)
216 __malloc_check_init ();
217}
218
219# define TUNABLE_CALLBACK_FNDECL(__name, __type) \
220static inline int do_ ## __name (__type value); \
221void \
222TUNABLE_CALLBACK (__name) (tunable_val_t *valp) \
223{ \
224 __type value = (__type) (valp)->numval; \
225 do_ ## __name (value); \
226}
227
228TUNABLE_CALLBACK_FNDECL (set_mmap_threshold, size_t)
229TUNABLE_CALLBACK_FNDECL (set_mmaps_max, int32_t)
230TUNABLE_CALLBACK_FNDECL (set_top_pad, size_t)
231TUNABLE_CALLBACK_FNDECL (set_perturb_byte, int32_t)
232TUNABLE_CALLBACK_FNDECL (set_trim_threshold, size_t)
233TUNABLE_CALLBACK_FNDECL (set_arena_max, size_t)
234TUNABLE_CALLBACK_FNDECL (set_arena_test, size_t)
235#if USE_TCACHE
236TUNABLE_CALLBACK_FNDECL (set_tcache_max, size_t)
237TUNABLE_CALLBACK_FNDECL (set_tcache_count, size_t)
238TUNABLE_CALLBACK_FNDECL (set_tcache_unsorted_limit, size_t)
239#endif
240TUNABLE_CALLBACK_FNDECL (set_mxfast, size_t)
241#else
242/* Initialization routine. */
243#include <string.h>
244extern char **_environ;
245
246static char *
247next_env_entry (char ***position)
248{
249 char **current = *position;
250 char *result = NULL;
251
252 while (*current != NULL)
253 {
254 if (__builtin_expect ((*current)[0] == 'M', 0)
255 && (*current)[1] == 'A'
256 && (*current)[2] == 'L'
257 && (*current)[3] == 'L'
258 && (*current)[4] == 'O'
259 && (*current)[5] == 'C'
260 && (*current)[6] == '_')
261 {
262 result = &(*current)[7];
263
264 /* Save current position for next visit. */
265 *position = ++current;
266
267 break;
268 }
269
270 ++current;
271 }
272
273 return result;
274}
275#endif
276
277
278#ifdef SHARED
279static void *
280__failing_morecore (ptrdiff_t d)
281{
282 return (void *) MORECORE_FAILURE;
283}
284
285extern struct dl_open_hook *_dl_open_hook;
286libc_hidden_proto (_dl_open_hook);
287#endif
288
289static void
290ptmalloc_init (void)
291{
292 if (__malloc_initialized >= 0)
293 return;
294
295 __malloc_initialized = 0;
296
297#ifdef SHARED
298 /* In case this libc copy is in a non-default namespace, never use brk.
299 Likewise if dlopened from statically linked program. */
300 Dl_info di;
301 struct link_map *l;
302
303 if (_dl_open_hook != NULL
304 || (_dl_addr (ptmalloc_init, &di, &l, NULL) != 0
305 && l->l_ns != LM_ID_BASE))
306 __morecore = __failing_morecore;
307#endif
308
309 thread_arena = &main_arena;
310
311 malloc_init_state (&main_arena);
312
313#if HAVE_TUNABLES
314 TUNABLE_GET (check, int32_t, TUNABLE_CALLBACK (set_mallopt_check));
315 TUNABLE_GET (top_pad, size_t, TUNABLE_CALLBACK (set_top_pad));
316 TUNABLE_GET (perturb, int32_t, TUNABLE_CALLBACK (set_perturb_byte));
317 TUNABLE_GET (mmap_threshold, size_t, TUNABLE_CALLBACK (set_mmap_threshold));
318 TUNABLE_GET (trim_threshold, size_t, TUNABLE_CALLBACK (set_trim_threshold));
319 TUNABLE_GET (mmap_max, int32_t, TUNABLE_CALLBACK (set_mmaps_max));
320 TUNABLE_GET (arena_max, size_t, TUNABLE_CALLBACK (set_arena_max));
321 TUNABLE_GET (arena_test, size_t, TUNABLE_CALLBACK (set_arena_test));
322# if USE_TCACHE
323 TUNABLE_GET (tcache_max, size_t, TUNABLE_CALLBACK (set_tcache_max));
324 TUNABLE_GET (tcache_count, size_t, TUNABLE_CALLBACK (set_tcache_count));
325 TUNABLE_GET (tcache_unsorted_limit, size_t,
326 TUNABLE_CALLBACK (set_tcache_unsorted_limit));
327# endif
328 TUNABLE_GET (mxfast, size_t, TUNABLE_CALLBACK (set_mxfast));
329#else
330 const char *s = NULL;
331 if (__glibc_likely (_environ != NULL))
332 {
333 char **runp = _environ;
334 char *envline;
335
336 while (__builtin_expect ((envline = next_env_entry (&runp)) != NULL,
337 0))
338 {
339 size_t len = strcspn (envline, "=");
340
341 if (envline[len] != '=')
342 /* This is a "MALLOC_" variable at the end of the string
343 without a '=' character. Ignore it since otherwise we
344 will access invalid memory below. */
345 continue;
346
347 switch (len)
348 {
349 case 6:
350 if (memcmp (envline, "CHECK_", 6) == 0)
351 s = &envline[7];
352 break;
353 case 8:
354 if (!__builtin_expect (__libc_enable_secure, 0))
355 {
356 if (memcmp (envline, "TOP_PAD_", 8) == 0)
357 __libc_mallopt (M_TOP_PAD, atoi (&envline[9]));
358 else if (memcmp (envline, "PERTURB_", 8) == 0)
359 __libc_mallopt (M_PERTURB, atoi (&envline[9]));
360 }
361 break;
362 case 9:
363 if (!__builtin_expect (__libc_enable_secure, 0))
364 {
365 if (memcmp (envline, "MMAP_MAX_", 9) == 0)
366 __libc_mallopt (M_MMAP_MAX, atoi (&envline[10]));
367 else if (memcmp (envline, "ARENA_MAX", 9) == 0)
368 __libc_mallopt (M_ARENA_MAX, atoi (&envline[10]));
369 }
370 break;
371 case 10:
372 if (!__builtin_expect (__libc_enable_secure, 0))
373 {
374 if (memcmp (envline, "ARENA_TEST", 10) == 0)
375 __libc_mallopt (M_ARENA_TEST, atoi (&envline[11]));
376 }
377 break;
378 case 15:
379 if (!__builtin_expect (__libc_enable_secure, 0))
380 {
381 if (memcmp (envline, "TRIM_THRESHOLD_", 15) == 0)
382 __libc_mallopt (M_TRIM_THRESHOLD, atoi (&envline[16]));
383 else if (memcmp (envline, "MMAP_THRESHOLD_", 15) == 0)
384 __libc_mallopt (M_MMAP_THRESHOLD, atoi (&envline[16]));
385 }
386 break;
387 default:
388 break;
389 }
390 }
391 }
392 if (s && s[0] != '\0' && s[0] != '0')
393 __malloc_check_init ();
394#endif
395
396#if HAVE_MALLOC_INIT_HOOK
397 void (*hook) (void) = atomic_forced_read (__malloc_initialize_hook);
398 if (hook != NULL)
399 (*hook)();
400#endif
401 __malloc_initialized = 1;
402}
403
404/* Managing heaps and arenas (for concurrent threads) */
405
406#if MALLOC_DEBUG > 1
407
408/* Print the complete contents of a single heap to stderr. */
409
410static void
411dump_heap (heap_info *heap)
412{
413 char *ptr;
414 mchunkptr p;
415
416 fprintf (stderr, "Heap %p, size %10lx:\n", heap, (long) heap->size);
417 ptr = (heap->ar_ptr != (mstate) (heap + 1)) ?
418 (char *) (heap + 1) : (char *) (heap + 1) + sizeof (struct malloc_state);
419 p = (mchunkptr) (((unsigned long) ptr + MALLOC_ALIGN_MASK) &
420 ~MALLOC_ALIGN_MASK);
421 for (;; )
422 {
423 fprintf (stderr, "chunk %p size %10lx", p, (long) p->size);
424 if (p == top (heap->ar_ptr))
425 {
426 fprintf (stderr, " (top)\n");
427 break;
428 }
429 else if (p->size == (0 | PREV_INUSE))
430 {
431 fprintf (stderr, " (fence)\n");
432 break;
433 }
434 fprintf (stderr, "\n");
435 p = next_chunk (p);
436 }
437}
438#endif /* MALLOC_DEBUG > 1 */
439
440/* If consecutive mmap (0, HEAP_MAX_SIZE << 1, ...) calls return decreasing
441 addresses as opposed to increasing, new_heap would badly fragment the
442 address space. In that case remember the second HEAP_MAX_SIZE part
443 aligned to HEAP_MAX_SIZE from last mmap (0, HEAP_MAX_SIZE << 1, ...)
444 call (if it is already aligned) and try to reuse it next time. We need
445 no locking for it, as kernel ensures the atomicity for us - worst case
446 we'll call mmap (addr, HEAP_MAX_SIZE, ...) for some value of addr in
447 multiple threads, but only one will succeed. */
448static char *aligned_heap_area;
449
450/* Create a new heap. size is automatically rounded up to a multiple
451 of the page size. */
452
453static heap_info *
454new_heap (size_t size, size_t top_pad)
455{
456 size_t pagesize = GLRO (dl_pagesize);
457 char *p1, *p2;
458 unsigned long ul;
459 heap_info *h;
460
461 if (size + top_pad < HEAP_MIN_SIZE)
462 size = HEAP_MIN_SIZE;
463 else if (size + top_pad <= HEAP_MAX_SIZE)
464 size += top_pad;
465 else if (size > HEAP_MAX_SIZE)
466 return 0;
467 else
468 size = HEAP_MAX_SIZE;
469 size = ALIGN_UP (size, pagesize);
470
471 /* A memory region aligned to a multiple of HEAP_MAX_SIZE is needed.
472 No swap space needs to be reserved for the following large
473 mapping (on Linux, this is the case for all non-writable mappings
474 anyway). */
475 p2 = MAP_FAILED;
476 if (aligned_heap_area)
477 {
478 p2 = (char *) MMAP (aligned_heap_area, HEAP_MAX_SIZE, PROT_NONE,
479 MAP_NORESERVE);
480 aligned_heap_area = NULL;
481 if (p2 != MAP_FAILED && ((unsigned long) p2 & (HEAP_MAX_SIZE - 1)))
482 {
483 __munmap (p2, HEAP_MAX_SIZE);
484 p2 = MAP_FAILED;
485 }
486 }
487 if (p2 == MAP_FAILED)
488 {
489 p1 = (char *) MMAP (0, HEAP_MAX_SIZE << 1, PROT_NONE, MAP_NORESERVE);
490 if (p1 != MAP_FAILED)
491 {
492 p2 = (char *) (((unsigned long) p1 + (HEAP_MAX_SIZE - 1))
493 & ~(HEAP_MAX_SIZE - 1));
494 ul = p2 - p1;
495 if (ul)
496 __munmap (p1, ul);
497 else
498 aligned_heap_area = p2 + HEAP_MAX_SIZE;
499 __munmap (p2 + HEAP_MAX_SIZE, HEAP_MAX_SIZE - ul);
500 }
501 else
502 {
503 /* Try to take the chance that an allocation of only HEAP_MAX_SIZE
504 is already aligned. */
505 p2 = (char *) MMAP (0, HEAP_MAX_SIZE, PROT_NONE, MAP_NORESERVE);
506 if (p2 == MAP_FAILED)
507 return 0;
508
509 if ((unsigned long) p2 & (HEAP_MAX_SIZE - 1))
510 {
511 __munmap (p2, HEAP_MAX_SIZE);
512 return 0;
513 }
514 }
515 }
516 if (__mprotect (p2, size, PROT_READ | PROT_WRITE) != 0)
517 {
518 __munmap (p2, HEAP_MAX_SIZE);
519 return 0;
520 }
521 h = (heap_info *) p2;
522 h->size = size;
523 h->mprotect_size = size;
524 LIBC_PROBE (memory_heap_new, 2, h, h->size);
525 return h;
526}
527
528/* Grow a heap. size is automatically rounded up to a
529 multiple of the page size. */
530
531static int
532grow_heap (heap_info *h, long diff)
533{
534 size_t pagesize = GLRO (dl_pagesize);
535 long new_size;
536
537 diff = ALIGN_UP (diff, pagesize);
538 new_size = (long) h->size + diff;
539 if ((unsigned long) new_size > (unsigned long) HEAP_MAX_SIZE)
540 return -1;
541
542 if ((unsigned long) new_size > h->mprotect_size)
543 {
544 if (__mprotect ((char *) h + h->mprotect_size,
545 (unsigned long) new_size - h->mprotect_size,
546 PROT_READ | PROT_WRITE) != 0)
547 return -2;
548
549 h->mprotect_size = new_size;
550 }
551
552 h->size = new_size;
553 LIBC_PROBE (memory_heap_more, 2, h, h->size);
554 return 0;
555}
556
557/* Shrink a heap. */
558
559static int
560shrink_heap (heap_info *h, long diff)
561{
562 long new_size;
563
564 new_size = (long) h->size - diff;
565 if (new_size < (long) sizeof (*h))
566 return -1;
567
568 /* Try to re-map the extra heap space freshly to save memory, and make it
569 inaccessible. See malloc-sysdep.h to know when this is true. */
570 if (__glibc_unlikely (check_may_shrink_heap ()))
571 {
572 if ((char *) MMAP ((char *) h + new_size, diff, PROT_NONE,
573 MAP_FIXED) == (char *) MAP_FAILED)
574 return -2;
575
576 h->mprotect_size = new_size;
577 }
578 else
579 __madvise ((char *) h + new_size, diff, MADV_DONTNEED);
580 /*fprintf(stderr, "shrink %p %08lx\n", h, new_size);*/
581
582 h->size = new_size;
583 LIBC_PROBE (memory_heap_less, 2, h, h->size);
584 return 0;
585}
586
587/* Delete a heap. */
588
589#define delete_heap(heap) \
590 do { \
591 if ((char *) (heap) + HEAP_MAX_SIZE == aligned_heap_area) \
592 aligned_heap_area = NULL; \
593 __munmap ((char *) (heap), HEAP_MAX_SIZE); \
594 } while (0)
595
596static int
597heap_trim (heap_info *heap, size_t pad)
598{
599 mstate ar_ptr = heap->ar_ptr;
600 unsigned long pagesz = GLRO (dl_pagesize);
601 mchunkptr top_chunk = top (ar_ptr), p, bck, fwd;
602 heap_info *prev_heap;
603 long new_size, top_size, top_area, extra, prev_size, misalign;
604
605 /* Can this heap go away completely? */
606 while (top_chunk == chunk_at_offset (heap, sizeof (*heap)))
607 {
608 prev_heap = heap->prev;
609 prev_size = prev_heap->size - (MINSIZE - 2 * SIZE_SZ);
610 p = chunk_at_offset (prev_heap, prev_size);
611 /* fencepost must be properly aligned. */
612 misalign = ((long) p) & MALLOC_ALIGN_MASK;
613 p = chunk_at_offset (prev_heap, prev_size - misalign);
614 assert (chunksize_nomask (p) == (0 | PREV_INUSE)); /* must be fencepost */
615 p = prev_chunk (p);
616 new_size = chunksize (p) + (MINSIZE - 2 * SIZE_SZ) + misalign;
617 assert (new_size > 0 && new_size < (long) (2 * MINSIZE));
618 if (!prev_inuse (p))
619 new_size += prev_size (p);
620 assert (new_size > 0 && new_size < HEAP_MAX_SIZE);
621 if (new_size + (HEAP_MAX_SIZE - prev_heap->size) < pad + MINSIZE + pagesz)
622 break;
623 ar_ptr->system_mem -= heap->size;
624 LIBC_PROBE (memory_heap_free, 2, heap, heap->size);
625 delete_heap (heap);
626 heap = prev_heap;
627 if (!prev_inuse (p)) /* consolidate backward */
628 {
629 p = prev_chunk (p);
630 unlink (ar_ptr, p, bck, fwd);
631 }
632 assert (((unsigned long) ((char *) p + new_size) & (pagesz - 1)) == 0);
633 assert (((char *) p + new_size) == ((char *) heap + heap->size));
634 top (ar_ptr) = top_chunk = p;
635 set_head (top_chunk, new_size | PREV_INUSE);
636 /*check_chunk(ar_ptr, top_chunk);*/
637 }
638
639 /* Uses similar logic for per-thread arenas as the main arena with systrim
640 and _int_free by preserving the top pad and rounding down to the nearest
641 page. */
642 top_size = chunksize (top_chunk);
643 if ((unsigned long)(top_size) <
644 (unsigned long)(mp_.trim_threshold))
645 return 0;
646
647 top_area = top_size - MINSIZE - 1;
648 if (top_area < 0 || (size_t) top_area <= pad)
649 return 0;
650
651 /* Release in pagesize units and round down to the nearest page. */
652 extra = ALIGN_DOWN(top_area - pad, pagesz);
653 if (extra == 0)
654 return 0;
655
656 /* Try to shrink. */
657 if (shrink_heap (heap, extra) != 0)
658 return 0;
659
660 ar_ptr->system_mem -= extra;
661
662 /* Success. Adjust top accordingly. */
663 set_head (top_chunk, (top_size - extra) | PREV_INUSE);
664 /*check_chunk(ar_ptr, top_chunk);*/
665 return 1;
666}
667
668/* Create a new arena with initial size "size". */
669
670/* If REPLACED_ARENA is not NULL, detach it from this thread. Must be
671 called while free_list_lock is held. */
672static void
673detach_arena (mstate replaced_arena)
674{
675 if (replaced_arena != NULL)
676 {
677 assert (replaced_arena->attached_threads > 0);
678 /* The current implementation only detaches from main_arena in
679 case of allocation failure. This means that it is likely not
680 beneficial to put the arena on free_list even if the
681 reference count reaches zero. */
682 --replaced_arena->attached_threads;
683 }
684}
685
686static mstate
687_int_new_arena (size_t size)
688{
689 mstate a;
690 heap_info *h;
691 char *ptr;
692 unsigned long misalign;
693
694 h = new_heap (size + (sizeof (*h) + sizeof (*a) + MALLOC_ALIGNMENT),
695 mp_.top_pad);
696 if (!h)
697 {
698 /* Maybe size is too large to fit in a single heap. So, just try
699 to create a minimally-sized arena and let _int_malloc() attempt
700 to deal with the large request via mmap_chunk(). */
701 h = new_heap (sizeof (*h) + sizeof (*a) + MALLOC_ALIGNMENT, mp_.top_pad);
702 if (!h)
703 return 0;
704 }
705 a = h->ar_ptr = (mstate) (h + 1);
706 malloc_init_state (a);
707 a->attached_threads = 1;
708 /*a->next = NULL;*/
709 a->system_mem = a->max_system_mem = h->size;
710
711 /* Set up the top chunk, with proper alignment. */
712 ptr = (char *) (a + 1);
713 misalign = (unsigned long) chunk2mem (ptr) & MALLOC_ALIGN_MASK;
714 if (misalign > 0)
715 ptr += MALLOC_ALIGNMENT - misalign;
716 top (a) = (mchunkptr) ptr;
717 set_head (top (a), (((char *) h + h->size) - ptr) | PREV_INUSE);
718
719 LIBC_PROBE (memory_arena_new, 2, a, size);
720 mstate replaced_arena = thread_arena;
721 thread_arena = a;
722 __libc_lock_init (a->mutex);
723
724 __libc_lock_lock (list_lock);
725
726 /* Add the new arena to the global list. */
727 a->next = main_arena.next;
728 /* FIXME: The barrier is an attempt to synchronize with read access
729 in reused_arena, which does not acquire list_lock while
730 traversing the list. */
731 atomic_write_barrier ();
732 main_arena.next = a;
733
734 __libc_lock_unlock (list_lock);
735
736 __libc_lock_lock (free_list_lock);
737 detach_arena (replaced_arena);
738 __libc_lock_unlock (free_list_lock);
739
740 /* Lock this arena. NB: Another thread may have been attached to
741 this arena because the arena is now accessible from the
742 main_arena.next list and could have been picked by reused_arena.
743 This can only happen for the last arena created (before the arena
744 limit is reached). At this point, some arena has to be attached
745 to two threads. We could acquire the arena lock before list_lock
746 to make it less likely that reused_arena picks this new arena,
747 but this could result in a deadlock with
748 __malloc_fork_lock_parent. */
749
750 __libc_lock_lock (a->mutex);
751
752 return a;
753}
754
755
756/* Remove an arena from free_list. */
757static mstate
758get_free_list (void)
759{
760 mstate replaced_arena = thread_arena;
761 mstate result = free_list;
762 if (result != NULL)
763 {
764 __libc_lock_lock (free_list_lock);
765 result = free_list;
766 if (result != NULL)
767 {
768 free_list = result->next_free;
769
770 /* The arena will be attached to this thread. */
771 assert (result->attached_threads == 0);
772 result->attached_threads = 1;
773
774 detach_arena (replaced_arena);
775 }
776 __libc_lock_unlock (free_list_lock);
777
778 if (result != NULL)
779 {
780 LIBC_PROBE (memory_arena_reuse_free_list, 1, result);
781 __libc_lock_lock (result->mutex);
782 thread_arena = result;
783 }
784 }
785
786 return result;
787}
788
789/* Remove the arena from the free list (if it is present).
790 free_list_lock must have been acquired by the caller. */
791static void
792remove_from_free_list (mstate arena)
793{
794 mstate *previous = &free_list;
795 for (mstate p = free_list; p != NULL; p = p->next_free)
796 {
797 assert (p->attached_threads == 0);
798 if (p == arena)
799 {
800 /* Remove the requested arena from the list. */
801 *previous = p->next_free;
802 break;
803 }
804 else
805 previous = &p->next_free;
806 }
807}
808
809/* Lock and return an arena that can be reused for memory allocation.
810 Avoid AVOID_ARENA as we have already failed to allocate memory in
811 it and it is currently locked. */
812static mstate
813reused_arena (mstate avoid_arena)
814{
815 mstate result;
816 /* FIXME: Access to next_to_use suffers from data races. */
817 static mstate next_to_use;
818 if (next_to_use == NULL)
819 next_to_use = &main_arena;
820
821 /* Iterate over all arenas (including those linked from
822 free_list). */
823 result = next_to_use;
824 do
825 {
826 if (!__libc_lock_trylock (result->mutex))
827 goto out;
828
829 /* FIXME: This is a data race, see _int_new_arena. */
830 result = result->next;
831 }
832 while (result != next_to_use);
833
834 /* Avoid AVOID_ARENA as we have already failed to allocate memory
835 in that arena and it is currently locked. */
836 if (result == avoid_arena)
837 result = result->next;
838
839 /* No arena available without contention. Wait for the next in line. */
840 LIBC_PROBE (memory_arena_reuse_wait, 3, &result->mutex, result, avoid_arena);
841 __libc_lock_lock (result->mutex);
842
843out:
844 /* Attach the arena to the current thread. */
845 {
846 /* Update the arena thread attachment counters. */
847 mstate replaced_arena = thread_arena;
848 __libc_lock_lock (free_list_lock);
849 detach_arena (replaced_arena);
850
851 /* We may have picked up an arena on the free list. We need to
852 preserve the invariant that no arena on the free list has a
853 positive attached_threads counter (otherwise,
854 arena_thread_freeres cannot use the counter to determine if the
855 arena needs to be put on the free list). We unconditionally
856 remove the selected arena from the free list. The caller of
857 reused_arena checked the free list and observed it to be empty,
858 so the list is very short. */
859 remove_from_free_list (result);
860
861 ++result->attached_threads;
862
863 __libc_lock_unlock (free_list_lock);
864 }
865
866 LIBC_PROBE (memory_arena_reuse, 2, result, avoid_arena);
867 thread_arena = result;
868 next_to_use = result->next;
869
870 return result;
871}
872
873static mstate
874arena_get2 (size_t size, mstate avoid_arena)
875{
876 mstate a;
877
878 static size_t narenas_limit;
879
880 a = get_free_list ();
881 if (a == NULL)
882 {
883 /* Nothing immediately available, so generate a new arena. */
884 if (narenas_limit == 0)
885 {
886 if (mp_.arena_max != 0)
887 narenas_limit = mp_.arena_max;
888 else if (narenas > mp_.arena_test)
889 {
890 int n = __get_nprocs ();
891
892 if (n >= 1)
893 narenas_limit = NARENAS_FROM_NCORES (n);
894 else
895 /* We have no information about the system. Assume two
896 cores. */
897 narenas_limit = NARENAS_FROM_NCORES (2);
898 }
899 }
900 repeat:;
901 size_t n = narenas;
902 /* NB: the following depends on the fact that (size_t)0 - 1 is a
903 very large number and that the underflow is OK. If arena_max
904 is set the value of arena_test is irrelevant. If arena_test
905 is set but narenas is not yet larger or equal to arena_test
906 narenas_limit is 0. There is no possibility for narenas to
907 be too big for the test to always fail since there is not
908 enough address space to create that many arenas. */
909 if (__glibc_unlikely (n <= narenas_limit - 1))
910 {
911 if (catomic_compare_and_exchange_bool_acq (&narenas, n + 1, n))
912 goto repeat;
913 a = _int_new_arena (size);
914 if (__glibc_unlikely (a == NULL))
915 catomic_decrement (&narenas);
916 }
917 else
918 a = reused_arena (avoid_arena);
919 }
920 return a;
921}
922
923/* If we don't have the main arena, then maybe the failure is due to running
924 out of mmapped areas, so we can try allocating on the main arena.
925 Otherwise, it is likely that sbrk() has failed and there is still a chance
926 to mmap(), so try one of the other arenas. */
927static mstate
928arena_get_retry (mstate ar_ptr, size_t bytes)
929{
930 LIBC_PROBE (memory_arena_retry, 2, bytes, ar_ptr);
931 if (ar_ptr != &main_arena)
932 {
933 __libc_lock_unlock (ar_ptr->mutex);
934 ar_ptr = &main_arena;
935 __libc_lock_lock (ar_ptr->mutex);
936 }
937 else
938 {
939 __libc_lock_unlock (ar_ptr->mutex);
940 ar_ptr = arena_get2 (bytes, ar_ptr);
941 }
942
943 return ar_ptr;
944}
945
946void
947__malloc_arena_thread_freeres (void)
948{
949 /* Shut down the thread cache first. This could deallocate data for
950 the thread arena, so do this before we put the arena on the free
951 list. */
952 tcache_thread_shutdown ();
953
954 mstate a = thread_arena;
955 thread_arena = NULL;
956
957 if (a != NULL)
958 {
959 __libc_lock_lock (free_list_lock);
960 /* If this was the last attached thread for this arena, put the
961 arena on the free list. */
962 assert (a->attached_threads > 0);
963 if (--a->attached_threads == 0)
964 {
965 a->next_free = free_list;
966 free_list = a;
967 }
968 __libc_lock_unlock (free_list_lock);
969 }
970}
971
972/*
973 * Local variables:
974 * c-basic-offset: 2
975 * End:
976 */
977