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