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