1/*-
2 * Copyright (C) 2006 Jason Evans <jasone@FreeBSD.org>.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice(s), this list of conditions and the following disclaimer as
10 * the first lines of this file unmodified other than the possible
11 * addition of one or more copyright notices.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice(s), this list of conditions and the following disclaimer in
14 * the documentation and/or other materials provided with the
15 * distribution.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE
21 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
24 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
25 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
26 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
27 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 *
29 *******************************************************************************
30 *
31 * This allocator implementation is designed to provide scalable performance
32 * for multi-threaded programs on multi-processor systems. The following
33 * features are included for this purpose:
34 *
35 * + Multiple arenas are used if there are multiple CPUs, which reduces lock
36 * contention and cache sloshing.
37 *
38 * + Cache line sharing between arenas is avoided for internal data
39 * structures.
40 *
41 * + Memory is managed in chunks and runs (chunks can be split into runs using
42 * a binary buddy scheme), rather than as individual pages. This provides
43 * a constant-time mechanism for associating allocations with particular
44 * arenas.
45 *
46 * Allocation requests are rounded up to the nearest size class, and no record
47 * of the original request size is maintained. Allocations are broken into
48 * categories according to size class. Assuming runtime defaults, 4 kB pages
49 * and a 16 byte quantum, the size classes in each category are as follows:
50 *
51 * |====================================|
52 * | Category | Subcategory | Size |
53 * |====================================|
54 * | Small | Tiny | 2 |
55 * | | | 4 |
56 * | | | 8 |
57 * | |----------------+--------|
58 * | | Quantum-spaced | 16 |
59 * | | | 32 |
60 * | | | 48 |
61 * | | | ... |
62 * | | | 480 |
63 * | | | 496 |
64 * | | | 512 |
65 * | |----------------+--------|
66 * | | Sub-page | 1 kB |
67 * | | | 2 kB |
68 * |====================================|
69 * | Large | 4 kB |
70 * | | 8 kB |
71 * | | 16 kB |
72 * | | ... |
73 * | | 256 kB |
74 * | | 512 kB |
75 * | | 1 MB |
76 * |====================================|
77 * | Huge | 2 MB |
78 * | | 4 MB |
79 * | | 6 MB |
80 * | | ... |
81 * |====================================|
82 *
83 * A different mechanism is used for each category:
84 *
85 * Small : Each size class is segregated into its own set of runs. Each run
86 * maintains a bitmap of which regions are free/allocated.
87 *
88 * Large : Each allocation is backed by a dedicated run. Metadata are stored
89 * in the associated arena chunk header maps.
90 *
91 * Huge : Each allocation is backed by a dedicated contiguous set of chunks.
92 * Metadata are stored in a separate red-black tree.
93 *
94 *******************************************************************************
95 */
96
97/*
98 *******************************************************************************
99 *
100 * Ring macros.
101 *
102 *******************************************************************************
103 */
104
105/* Ring definitions. */
106#define qr(a_type) struct { \
107 a_type *qre_next; \
108 a_type *qre_prev; \
109}
110
111#define qr_initializer {NULL, NULL}
112
113/* Ring functions. */
114#define qr_new(a_qr, a_field) do { \
115 (a_qr)->a_field.qre_next = (a_qr); \
116 (a_qr)->a_field.qre_prev = (a_qr); \
117} while (0)
118
119#define qr_next(a_qr, a_field) ((a_qr)->a_field.qre_next)
120
121#define qr_prev(a_qr, a_field) ((a_qr)->a_field.qre_prev)
122
123#define qr_before_insert(a_qrelm, a_qr, a_field) do { \
124 (a_qr)->a_field.qre_prev = (a_qrelm)->a_field.qre_prev; \
125 (a_qr)->a_field.qre_next = (a_qrelm); \
126 (a_qr)->a_field.qre_prev->a_field.qre_next = (a_qr); \
127 (a_qrelm)->a_field.qre_prev = (a_qr); \
128} while (0)
129
130#define qr_after_insert(a_qrelm, a_qr, a_field) do { \
131 (a_qr)->a_field.qre_next = (a_qrelm)->a_field.qre_next; \
132 (a_qr)->a_field.qre_prev = (a_qrelm); \
133 (a_qr)->a_field.qre_next->a_field.qre_prev = (a_qr); \
134 (a_qrelm)->a_field.qre_next = (a_qr); \
135} while (0)
136
137#define qr_meld(a_qr_a, a_qr_b, a_type, a_field) do { \
138 a_type *t; \
139 (a_qr_a)->a_field.qre_prev->a_field.qre_next = (a_qr_b); \
140 (a_qr_b)->a_field.qre_prev->a_field.qre_next = (a_qr_a); \
141 t = (a_qr_a)->a_field.qre_prev; \
142 (a_qr_a)->a_field.qre_prev = (a_qr_b)->a_field.qre_prev; \
143 (a_qr_b)->a_field.qre_prev = t; \
144} while (0)
145
146/*
147 * qr_meld() and qr_split() are functionally equivalent, so there's no need to
148 * have two copies of the code.
149 */
150#define qr_split(a_qr_a, a_qr_b, a_type, a_field) \
151 qr_meld((a_qr_a), (a_qr_b), a_type, a_field)
152
153#define qr_remove(a_qr, a_field) do { \
154 (a_qr)->a_field.qre_prev->a_field.qre_next \
155 = (a_qr)->a_field.qre_next; \
156 (a_qr)->a_field.qre_next->a_field.qre_prev \
157 = (a_qr)->a_field.qre_prev; \
158 (a_qr)->a_field.qre_next = (a_qr); \
159 (a_qr)->a_field.qre_prev = (a_qr); \
160} while (0)
161
162#define qr_foreach(var, a_qr, a_field) \
163 for ((var) = (a_qr); \
164 (var) != NULL; \
165 (var) = (((var)->a_field.qre_next != (a_qr)) \
166 ? (var)->a_field.qre_next : NULL))
167
168#define qr_reverse_foreach(var, a_qr, a_field) \
169 for ((var) = ((a_qr) != NULL) ? qr_prev(a_qr, a_field) : NULL; \
170 (var) != NULL; \
171 (var) = (((var) != (a_qr)) \
172 ? (var)->a_field.qre_prev : NULL))
173
174/******************************************************************************/
175
176/*
177 * In order to disable various extra features that may have negative
178 * performance impacts, (assertions, expanded statistics), define
179 * NO_MALLOC_EXTRAS.
180 */
181/* #define NO_MALLOC_EXTRAS */
182
183#ifndef NO_MALLOC_EXTRAS
184# define MALLOC_DEBUG
185#endif
186
187#include <sys/cdefs.h>
188__FBSDID("$FreeBSD: head/lib/libc/stdlib/malloc.c 160761 2006-07-27 19:09:32Z jasone $");
189
190#include "libc_private.h"
191#ifdef MALLOC_DEBUG
192# define _LOCK_DEBUG
193#endif
194#include "spinlock.h"
195#include "namespace.h"
196#include <sys/mman.h>
197#include <sys/param.h>
198#include <sys/stddef.h>
199#include <sys/time.h>
200#include <sys/types.h>
201#include <sys/sysctl.h>
202#include <sys/tree.h>
203#include <sys/uio.h>
204#include <sys/ktrace.h> /* Must come after several other sys/ includes. */
205
206#include <machine/atomic.h>
207#include <machine/cpufunc.h>
208#include <machine/vmparam.h>
209
210#include <errno.h>
211#include <limits.h>
212#include <pthread.h>
213#include <sched.h>
214#include <stdarg.h>
215#include <stdbool.h>
216#include <stdio.h>
217#include <stdlib.h>
218#include <string.h>
219#include <strings.h>
220#include <unistd.h>
221
222#include "un-namespace.h"
223
224/*
225 * Calculate statistics that can be used to get an idea of how well caching is
226 * working.
227 */
228#ifndef NO_MALLOC_EXTRAS
229# define MALLOC_STATS
230#endif
231
232#ifndef MALLOC_DEBUG
233# ifndef NDEBUG
234# define NDEBUG
235# endif
236#endif
237#include <assert.h>
238
239#ifdef MALLOC_DEBUG
240 /* Disable inlining to make debugging easier. */
241# define inline
242#endif
243
244/* Size of stack-allocated buffer passed to strerror_r(). */
245#define STRERROR_BUF 64
246
247/* Minimum alignment of allocations is 2^QUANTUM_2POW_MIN bytes. */
248#ifdef __i386__
249# define QUANTUM_2POW_MIN 4
250# define SIZEOF_PTR 4
251# define USE_BRK
252#endif
253#ifdef __ia64__
254# define QUANTUM_2POW_MIN 4
255# define SIZEOF_PTR 8
256# define NO_TLS
257#endif
258#ifdef __alpha__
259# define QUANTUM_2POW_MIN 4
260# define SIZEOF_PTR 8
261# define NO_TLS
262#endif
263#ifdef __sparc64__
264# define QUANTUM_2POW_MIN 4
265# define SIZEOF_PTR 8
266# define NO_TLS
267#endif
268#ifdef __amd64__
269# define QUANTUM_2POW_MIN 4
270# define SIZEOF_PTR 8
271#endif
272#ifdef __arm__
273# define QUANTUM_2POW_MIN 3
274# define SIZEOF_PTR 4
275# define USE_BRK
276# define NO_TLS
277#endif
278#ifdef __powerpc__
279# define QUANTUM_2POW_MIN 4
280# define SIZEOF_PTR 4
281# define USE_BRK
282#endif
283
284/* sizeof(int) == (1 << SIZEOF_INT_2POW). */
285#ifndef SIZEOF_INT_2POW
286# define SIZEOF_INT_2POW 2
287#endif
288
289/* We can't use TLS in non-PIC programs, since TLS relies on loader magic. */
290#if (!defined(PIC) && !defined(NO_TLS))
291# define NO_TLS
292#endif
293
294/*
295 * Size and alignment of memory chunks that are allocated by the OS's virtual
296 * memory system.
297 *
298 * chunksize limits:
299 *
300 * 2^(pagesize_2pow - 1 + RUN_MIN_REGS_2POW) <= chunk_size <= 2^28
301 */
302#define CHUNK_2POW_DEFAULT 21
303#define CHUNK_2POW_MAX 28
304
305/*
306 * Maximum size of L1 cache line. This is used to avoid cache line aliasing,
307 * so over-estimates are okay (up to a point), but under-estimates will
308 * negatively affect performance.
309 */
310#define CACHELINE_2POW 6
311#define CACHELINE ((size_t)(1 << CACHELINE_2POW))
312
313/*
314 * Maximum size class that is a multiple of the quantum, but not (necessarily)
315 * a power of 2. Above this size, allocations are rounded up to the nearest
316 * power of 2.
317 */
318#define SMALL_MAX_2POW_DEFAULT 9
319#define SMALL_MAX_DEFAULT (1 << SMALL_MAX_2POW_DEFAULT)
320
321/*
322 * Minimum number of regions that must fit into a run that serves quantum-size
323 * bin allocations.
324 *
325 * Note that if this is set too low, space will be wasted if there are size
326 * classes that are small enough that RUN_MIN_REGS regions don't fill a page.
327 * If this is set too high, then the overhead of searching through the bitmap
328 * that tracks region usage will become excessive.
329 */
330#define RUN_MIN_REGS_2POW 10
331#define RUN_MIN_REGS (1 << RUN_MIN_REGS_2POW)
332
333/*
334 * Maximum number of pages for a run that is used for bin allocations.
335 *
336 * Note that if this is set too low, then fragmentation for the largest bin
337 * size classes will be high. If this is set too high, then even small
338 * programs will often have to allocate more than two chunks early on.
339 */
340#define RUN_MAX_PAGES_2POW 4
341#define RUN_MAX_PAGES (1 << RUN_MAX_PAGES_2POW)
342
343/******************************************************************************/
344
345/*
346 * Mutexes based on spinlocks. We can't use normal pthread mutexes, because
347 * they require malloc()ed memory.
348 */
349typedef struct {
350 spinlock_t lock;
351} malloc_mutex_t;
352
353/* Set to true once the allocator has been initialized. */
354static bool malloc_initialized = false;
355
356/* Used to avoid initialization races. */
357static malloc_mutex_t init_lock = {_SPINLOCK_INITIALIZER};
358
359/******************************************************************************/
360/*
361 * Statistics data structures.
362 */
363
364#ifdef MALLOC_STATS
365
366typedef struct malloc_bin_stats_s malloc_bin_stats_t;
367struct malloc_bin_stats_s {
368 /*
369 * Number of allocation requests that corresponded to the size of this
370 * bin.
371 */
372 uint64_t nrequests;
373
374 /* Total number of runs created for this bin's size class. */
375 uint64_t nruns;
376
377 /*
378 * Total number of run promotions/demotions for this bin's size class.
379 */
380 uint64_t npromote;
381 uint64_t ndemote;
382
383 /* High-water mark for this bin. */
384 unsigned long highruns;
385
386 /* Current number of runs in this bin. */
387 unsigned long curruns;
388};
389
390typedef struct arena_stats_s arena_stats_t;
391struct arena_stats_s {
392 /* Total byte count of allocated memory, not including overhead. */
393 size_t allocated;
394
395 /* Number of times each function was called. */
396 uint64_t nmalloc;
397 uint64_t ndalloc;
398 uint64_t nmadvise;
399
400 /* Number of large allocation requests. */
401 uint64_t large_nrequests;
402};
403
404typedef struct chunk_stats_s chunk_stats_t;
405struct chunk_stats_s {
406 /* Number of chunks that were allocated. */
407 uint64_t nchunks;
408
409 /* High-water mark for number of chunks allocated. */
410 unsigned long highchunks;
411
412 /*
413 * Current number of chunks allocated. This value isn't maintained for
414 * any other purpose, so keep track of it in order to be able to set
415 * highchunks.
416 */
417 unsigned long curchunks;
418};
419
420#endif /* #ifdef MALLOC_STATS */
421
422/******************************************************************************/
423/*
424 * Chunk data structures.
425 */
426
427/* Tree of chunks. */
428typedef struct chunk_node_s chunk_node_t;
429struct chunk_node_s {
430 /* Linkage for the chunk tree. */
431 RB_ENTRY(chunk_node_s) link;
432
433 /*
434 * Pointer to the chunk that this tree node is responsible for. In some
435 * (but certainly not all) cases, this data structure is placed at the
436 * beginning of the corresponding chunk, so this field may point to this
437 * node.
438 */
439 void *chunk;
440
441 /* Total chunk size. */
442 size_t size;
443};
444typedef struct chunk_tree_s chunk_tree_t;
445RB_HEAD(chunk_tree_s, chunk_node_s);
446
447/******************************************************************************/
448/*
449 * Arena data structures.
450 */
451
452typedef struct arena_s arena_t;
453typedef struct arena_bin_s arena_bin_t;
454
455typedef struct arena_chunk_map_s arena_chunk_map_t;
456struct arena_chunk_map_s {
457 bool free:1;
458 bool large:1;
459 unsigned npages:15; /* Limiting factor for CHUNK_2POW_MAX. */
460 unsigned pos:15;
461};
462
463/* Arena chunk header. */
464typedef struct arena_chunk_s arena_chunk_t;
465struct arena_chunk_s {
466 /* Arena that owns the chunk. */
467 arena_t *arena;
468
469 /* Linkage for the arena's chunk tree. */
470 RB_ENTRY(arena_chunk_s) link;
471
472 /*
473 * Number of pages in use. This is maintained in order to make
474 * detection of empty chunks fast.
475 */
476 uint32_t pages_used;
477
478 /*
479 * Array of counters that keeps track of how many free runs of each
480 * size are available in this chunk. This table is sized at compile
481 * time, which is wasteful. However, due to unrelated rounding, this
482 * doesn't actually waste any otherwise useful space.
483 *
484 * index == 2^n pages
485 *
486 * index | npages
487 * ------+-------
488 * 0 | 1
489 * 1 | 2
490 * 2 | 4
491 * 3 | 8
492 * :
493 */
494 uint32_t nfree_runs[CHUNK_2POW_MAX/* - PAGE_SHIFT */];
495
496 /* Map of pages within chunk that keeps track of free/large/small. */
497 arena_chunk_map_t map[1]; /* Dynamically sized. */
498};
499typedef struct arena_chunk_tree_s arena_chunk_tree_t;
500RB_HEAD(arena_chunk_tree_s, arena_chunk_s);
501
502typedef struct arena_run_s arena_run_t;
503struct arena_run_s {
504 /* Linkage for run rings. */
505 qr(arena_run_t) link;
506
507#ifdef MALLOC_DEBUG
508 uint32_t magic;
509# define ARENA_RUN_MAGIC 0x384adf93
510#endif
511
512 /* Bin this run is associated with. */
513 arena_bin_t *bin;
514
515 /* Bitmask of in-use regions (0: in use, 1: free). */
516#define REGS_MASK_NELMS \
517 (1 << (RUN_MIN_REGS_2POW - SIZEOF_INT_2POW - 2))
518 unsigned regs_mask[REGS_MASK_NELMS];
519
520 /* Index of first element that might have a free region. */
521 unsigned regs_minelm;
522
523 /* Number of free regions in run. */
524 unsigned nfree;
525
526 /*
527 * Current quartile for this run, one of: {RUN_QINIT, RUN_Q0, RUN_25,
528 * RUN_Q50, RUN_Q75, RUN_Q100}.
529 */
530#define RUN_QINIT 0
531#define RUN_Q0 1
532#define RUN_Q25 2
533#define RUN_Q50 3
534#define RUN_Q75 4
535#define RUN_Q100 5
536 unsigned quartile;
537
538 /*
539 * Limits on the number of free regions for the fullness quartile this
540 * run is currently in. If nfree goes outside these limits, the run
541 * is moved to a different fullness quartile.
542 */
543 unsigned free_max;
544 unsigned free_min;
545};
546
547/* Used for run ring headers, where the run isn't actually used. */
548typedef struct arena_run_link_s arena_run_link_t;
549struct arena_run_link_s {
550 /* Linkage for run rings. */
551 qr(arena_run_t) link;
552};
553
554struct arena_bin_s {
555 /*
556 * Current run being used to service allocations of this bin's size
557 * class.
558 */
559 arena_run_t *runcur;
560
561 /*
562 * Links into rings of runs, of various fullnesses (names indicate
563 * approximate lower bounds). A new run conceptually starts off in
564 * runsinit, and it isn't inserted into the runs0 ring until it
565 * reaches 25% full (hysteresis mechanism). For the run to be moved
566 * again, it must become either empty or 50% full. Thus, each ring
567 * contains runs that are within 50% above the advertised fullness for
568 * the ring. This provides a low-overhead mechanism for segregating
569 * runs into approximate fullness classes.
570 *
571 * Conceptually, there is a runs100 that contains completely full runs.
572 * Since we don't need to search for these runs though, no runs100 ring
573 * is actually maintained.
574 *
575 * These rings are useful when looking for an existing run to use when
576 * runcur is no longer usable. We look for usable runs in the
577 * following order:
578 *
579 * 1) runs50
580 * 2) runs25
581 * 3) runs0
582 * 4) runs75
583 *
584 * runs75 isn't a good place to look, because it contains runs that may
585 * be nearly completely full. Still, we look there as a last resort in
586 * order to avoid allocating a new run if at all possible.
587 */
588 /* arena_run_link_t runsinit; 0% <= fullness < 25% */
589 arena_run_link_t runs0; /* 0% < fullness < 50% */
590 arena_run_link_t runs25; /* 25% < fullness < 75% */
591 arena_run_link_t runs50; /* 50% < fullness < 100% */
592 arena_run_link_t runs75; /* 75% < fullness < 100% */
593 /* arena_run_link_t runs100; fullness == 100% */
594
595 /* Size of regions in a run for this bin's size class. */
596 size_t reg_size;
597
598 /* Total size of a run for this bin's size class. */
599 size_t run_size;
600
601 /* Total number of regions in a run for this bin's size class. */
602 uint32_t nregs;
603
604 /* Offset of first region in a run for this bin's size class. */
605 uint32_t reg0_offset;
606
607#ifdef MALLOC_STATS
608 /* Bin statistics. */
609 malloc_bin_stats_t stats;
610#endif
611};
612
613struct arena_s {
614#ifdef MALLOC_DEBUG
615 uint32_t magic;
616# define ARENA_MAGIC 0x947d3d24
617#endif
618
619 /* All operations on this arena require that mtx be locked. */
620 malloc_mutex_t mtx;
621
622#ifdef MALLOC_STATS
623 arena_stats_t stats;
624#endif
625
626 /*
627 * Tree of chunks this arena manages.
628 */
629 arena_chunk_tree_t chunks;
630
631 /*
632 * bins is used to store rings of free regions of the following sizes,
633 * assuming a 16-byte quantum, 4kB pagesize, and default MALLOC_OPTIONS.
634 *
635 * bins[i] | size |
636 * --------+------+
637 * 0 | 2 |
638 * 1 | 4 |
639 * 2 | 8 |
640 * --------+------+
641 * 3 | 16 |
642 * 4 | 32 |
643 * 5 | 48 |
644 * 6 | 64 |
645 * : :
646 * : :
647 * 33 | 496 |
648 * 34 | 512 |
649 * --------+------+
650 * 35 | 1024 |
651 * 36 | 2048 |
652 * --------+------+
653 */
654 arena_bin_t bins[1]; /* Dynamically sized. */
655};
656
657/******************************************************************************/
658/*
659 * Data.
660 */
661
662/* Number of CPUs. */
663static unsigned ncpus;
664
665/* VM page size. */
666static unsigned pagesize;
667static unsigned pagesize_2pow;
668
669/* Various bin-related settings. */
670static size_t bin_maxclass; /* Max size class for bins. */
671static unsigned ntbins; /* Number of (2^n)-spaced tiny bins. */
672static unsigned nqbins; /* Number of quantum-spaced bins. */
673static unsigned nsbins; /* Number of (2^n)-spaced sub-page bins. */
674static size_t small_min;
675static size_t small_max;
676static unsigned tiny_min_2pow;
677
678/* Various quantum-related settings. */
679static size_t quantum;
680static size_t quantum_mask; /* (quantum - 1). */
681
682/* Various chunk-related settings. */
683static size_t chunk_size;
684static size_t chunk_size_mask; /* (chunk_size - 1). */
685static size_t arena_maxclass; /* Max size class for arenas. */
686static unsigned arena_chunk_maplen;
687
688/********/
689/*
690 * Chunks.
691 */
692
693/* Protects chunk-related data structures. */
694static malloc_mutex_t chunks_mtx;
695
696/* Tree of chunks that are stand-alone huge allocations. */
697static chunk_tree_t huge;
698
699#ifdef USE_BRK
700/*
701 * Try to use brk for chunk-size allocations, due to address space constraints.
702 */
703/* Result of first sbrk(0) call. */
704static void *brk_base;
705/* Current end of brk, or ((void *)-1) if brk is exhausted. */
706static void *brk_prev;
707/* Current upper limit on brk addresses. */
708static void *brk_max;
709#endif
710
711#ifdef MALLOC_STATS
712/*
713 * Byte counters for allocated/total space used by the chunks in the huge
714 * allocations tree.
715 */
716static uint64_t huge_nmalloc;
717static uint64_t huge_ndalloc;
718static size_t huge_allocated;
719#endif
720
721/*
722 * Tree of chunks that were previously allocated. This is used when allocating
723 * chunks, in an attempt to re-use address space.
724 */
725static chunk_tree_t old_chunks;
726
727/****************************/
728/*
729 * base (internal allocation).
730 */
731
732/*
733 * Current chunk that is being used for internal memory allocations. This
734 * chunk is carved up in cacheline-size quanta, so that there is no chance of
735 * false cache line sharing.
736 */
737static void *base_chunk;
738static void *base_next_addr;
739static void *base_past_addr; /* Addr immediately past base_chunk. */
740static chunk_node_t *base_chunk_nodes; /* LIFO cache of chunk nodes. */
741static malloc_mutex_t base_mtx;
742#ifdef MALLOC_STATS
743static uint64_t base_total;
744#endif
745
746/********/
747/*
748 * Arenas.
749 */
750
751/*
752 * Arenas that are used to service external requests. Not all elements of the
753 * arenas array are necessarily used; arenas are created lazily as needed.
754 */
755static arena_t **arenas;
756static unsigned narenas;
757#ifndef NO_TLS
758static unsigned next_arena;
759#endif
760static malloc_mutex_t arenas_mtx; /* Protects arenas initialization. */
761
762#ifndef NO_TLS
763/*
764 * Map of pthread_self() --> arenas[???], used for selecting an arena to use
765 * for allocations.
766 */
767static __thread arena_t *arenas_map;
768#endif
769
770#ifdef MALLOC_STATS
771/* Chunk statistics. */
772static chunk_stats_t stats_chunks;
773#endif
774
775/*******************************/
776/*
777 * Runtime configuration options.
778 */
779const char *_malloc_options;
780
781#ifndef NO_MALLOC_EXTRAS
782static bool opt_abort = true;
783static bool opt_junk = true;
784#else
785static bool opt_abort = false;
786static bool opt_junk = false;
787#endif
788static bool opt_hint = false;
789static bool opt_print_stats = false;
790static size_t opt_quantum_2pow = QUANTUM_2POW_MIN;
791static size_t opt_small_max_2pow = SMALL_MAX_2POW_DEFAULT;
792static size_t opt_chunk_2pow = CHUNK_2POW_DEFAULT;
793static bool opt_utrace = false;
794static bool opt_sysv = false;
795static bool opt_xmalloc = false;
796static bool opt_zero = false;
797static int32_t opt_narenas_lshift = 0;
798
799typedef struct {
800 void *p;
801 size_t s;
802 void *r;
803} malloc_utrace_t;
804
805#define UTRACE(a, b, c) \
806 if (opt_utrace) { \
807 malloc_utrace_t ut = {a, b, c}; \
808 utrace(&ut, sizeof(ut)); \
809 }
810
811/******************************************************************************/
812/*
813 * Begin function prototypes for non-inline static functions.
814 */
815
816static void malloc_mutex_init(malloc_mutex_t *a_mutex);
817static void wrtmessage(const char *p1, const char *p2, const char *p3,
818 const char *p4);
819static void malloc_printf(const char *format, ...);
820static void *base_alloc(size_t size);
821static chunk_node_t *base_chunk_node_alloc(void);
822static void base_chunk_node_dealloc(chunk_node_t *node);
823#ifdef MALLOC_STATS
824static void stats_print(arena_t *arena);
825#endif
826static void *pages_map(void *addr, size_t size);
827static void pages_unmap(void *addr, size_t size);
828static void *chunk_alloc(size_t size);
829static void chunk_dealloc(void *chunk, size_t size);
830#ifndef NO_TLS
831static arena_t *choose_arena_hard(void);
832#endif
833static void arena_run_split(arena_t *arena, arena_run_t *run, bool large,
834 size_t size);
835static arena_chunk_t *arena_chunk_alloc(arena_t *arena);
836static void arena_chunk_dealloc(arena_chunk_t *chunk);
837static void arena_bin_run_promote(arena_t *arena, arena_bin_t *bin,
838 arena_run_t *run);
839static void arena_bin_run_demote(arena_t *arena, arena_bin_t *bin,
840 arena_run_t *run);
841static arena_run_t *arena_run_alloc(arena_t *arena, bool large, size_t size);
842static void arena_run_dalloc(arena_t *arena, arena_run_t *run, size_t size);
843static arena_run_t *arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin);
844static void *arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin);
845static void *arena_malloc(arena_t *arena, size_t size);
846static size_t arena_salloc(const void *ptr);
847static void *arena_ralloc(void *ptr, size_t size, size_t oldsize);
848static void arena_dalloc(arena_t *arena, arena_chunk_t *chunk, void *ptr);
849static bool arena_new(arena_t *arena);
850static arena_t *arenas_extend(unsigned ind);
851static void *huge_malloc(size_t size);
852static void *huge_ralloc(void *ptr, size_t size, size_t oldsize);
853static void huge_dalloc(void *ptr);
854static void *imalloc(size_t size);
855static void *ipalloc(size_t alignment, size_t size);
856static void *icalloc(size_t size);
857static size_t isalloc(const void *ptr);
858static void *iralloc(void *ptr, size_t size);
859static void idalloc(void *ptr);
860static void malloc_print_stats(void);
861static bool malloc_init_hard(void);
862
863/*
864 * End function prototypes.
865 */
866/******************************************************************************/
867/*
868 * Begin mutex.
869 */
870
871static void
872malloc_mutex_init(malloc_mutex_t *a_mutex)
873{
874 static const spinlock_t lock = _SPINLOCK_INITIALIZER;
875
876 a_mutex->lock = lock;
877}
878
879static inline void
880malloc_mutex_lock(malloc_mutex_t *a_mutex)
881{
882
883 if (__isthreaded)
884 _SPINLOCK(&a_mutex->lock);
885}
886
887static inline void
888malloc_mutex_unlock(malloc_mutex_t *a_mutex)
889{
890
891 if (__isthreaded)
892 _SPINUNLOCK(&a_mutex->lock);
893}
894
895/*
896 * End mutex.
897 */
898/******************************************************************************/
899/*
900 * Begin Utility functions/macros.
901 */
902
903/* Return the chunk address for allocation address a. */
904#define CHUNK_ADDR2BASE(a) \
905 ((void *)((uintptr_t)(a) & ~chunk_size_mask))
906
907/* Return the chunk offset of address a. */
908#define CHUNK_ADDR2OFFSET(a) \
909 ((size_t)((uintptr_t)(a) & chunk_size_mask))
910
911/* Return the smallest chunk multiple that is >= s. */
912#define CHUNK_CEILING(s) \
913 (((s) + chunk_size_mask) & ~chunk_size_mask)
914
915/* Return the smallest cacheline multiple that is >= s. */
916#define CACHELINE_CEILING(s) \
917 (((s) + (CACHELINE - 1)) & ~(CACHELINE - 1))
918
919/* Return the smallest quantum multiple that is >= a. */
920#define QUANTUM_CEILING(a) \
921 (((a) + quantum_mask) & ~quantum_mask)
922
923/* Compute the smallest power of 2 that is >= x. */
924static inline size_t
925pow2_ceil(size_t x)
926{
927
928 x--;
929 x |= x >> 1;
930 x |= x >> 2;
931 x |= x >> 4;
932 x |= x >> 8;
933 x |= x >> 16;
934#if (SIZEOF_PTR == 8)
935 x |= x >> 32;
936#endif
937 x++;
938 return (x);
939}
940
941static void
942wrtmessage(const char *p1, const char *p2, const char *p3, const char *p4)
943{
944
945 _write(STDERR_FILENO, p1, strlen(p1));
946 _write(STDERR_FILENO, p2, strlen(p2));
947 _write(STDERR_FILENO, p3, strlen(p3));
948 _write(STDERR_FILENO, p4, strlen(p4));
949}
950
951void (*_malloc_message)(const char *p1, const char *p2, const char *p3,
952 const char *p4) = wrtmessage;
953
954/*
955 * Print to stderr in such a way as to (hopefully) avoid memory allocation.
956 */
957static void
958malloc_printf(const char *format, ...)
959{
960 char buf[4096];
961 va_list ap;
962
963 va_start(ap, format);
964 vsnprintf(buf, sizeof(buf), format, ap);
965 va_end(ap);
966 _malloc_message(buf, "", "", "");
967}
968
969/******************************************************************************/
970
971static void *
972base_alloc(size_t size)
973{
974 void *ret;
975 size_t csize;
976
977 /* Round size up to nearest multiple of the cacheline size. */
978 csize = CACHELINE_CEILING(size);
979
980 malloc_mutex_lock(&base_mtx);
981
982 /* Make sure there's enough space for the allocation. */
983 if ((uintptr_t)base_next_addr + csize > (uintptr_t)base_past_addr) {
984 void *tchunk;
985
986 assert(csize <= chunk_size);
987
988 tchunk = chunk_alloc(chunk_size);
989 if (tchunk == NULL) {
990 ret = NULL;
991 goto RETURN;
992 }
993 base_chunk = tchunk;
994 base_next_addr = (void *)base_chunk;
995 base_past_addr = (void *)((uintptr_t)base_chunk + chunk_size);
996#ifdef MALLOC_STATS
997 base_total += chunk_size;
998#endif
999 }
1000
1001 /* Allocate. */
1002 ret = base_next_addr;
1003 base_next_addr = (void *)((uintptr_t)base_next_addr + csize);
1004
1005RETURN:
1006 malloc_mutex_unlock(&base_mtx);
1007 return (ret);
1008}
1009
1010static chunk_node_t *
1011base_chunk_node_alloc(void)
1012{
1013 chunk_node_t *ret;
1014
1015 malloc_mutex_lock(&base_mtx);
1016 if (base_chunk_nodes != NULL) {
1017 ret = base_chunk_nodes;
1018 base_chunk_nodes = *(chunk_node_t **)ret;
1019 malloc_mutex_unlock(&base_mtx);
1020 } else {
1021 malloc_mutex_unlock(&base_mtx);
1022 ret = (chunk_node_t *)base_alloc(sizeof(chunk_node_t));
1023 }
1024
1025 return (ret);
1026}
1027
1028static void
1029base_chunk_node_dealloc(chunk_node_t *node)
1030{
1031
1032 malloc_mutex_lock(&base_mtx);
1033 *(chunk_node_t **)node = base_chunk_nodes;
1034 base_chunk_nodes = node;
1035 malloc_mutex_unlock(&base_mtx);
1036}
1037
1038/******************************************************************************/
1039
1040#ifdef MALLOC_STATS
1041static void
1042stats_print(arena_t *arena)
1043{
1044 unsigned i;
1045 int gap_start;
1046
1047 malloc_printf("allocated: %zu\n", arena->stats.allocated);
1048
1049 malloc_printf("calls:\n");
1050 malloc_printf(" %12s %12s %12s\n", "nmalloc","ndalloc", "nmadvise");
1051 malloc_printf(" %12llu %12llu %12llu\n",
1052 arena->stats.nmalloc, arena->stats.ndalloc, arena->stats.nmadvise);
1053
1054 malloc_printf("large requests: %llu\n", arena->stats.large_nrequests);
1055
1056 malloc_printf("bins:\n");
1057 malloc_printf("%13s %1s %4s %5s %6s %9s %5s %6s %7s %6s %6s\n",
1058 "bin", "", "size", "nregs", "run_sz", "nrequests", "nruns",
1059 "hiruns", "curruns", "npromo", "ndemo");
1060 for (i = 0, gap_start = -1; i < ntbins + nqbins + nsbins; i++) {
1061 if (arena->bins[i].stats.nrequests == 0) {
1062 if (gap_start == -1)
1063 gap_start = i;
1064 } else {
1065 if (gap_start != -1) {
1066 if (i > gap_start + 1) {
1067 /* Gap of more than one size class. */
1068 malloc_printf("[%u..%u]\n",
1069 gap_start, i - 1);
1070 } else {
1071 /* Gap of one size class. */
1072 malloc_printf("[%u]\n", gap_start);
1073 }
1074 gap_start = -1;
1075 }
1076 malloc_printf(
1077 "%13u %1s %4u %5u %6u %9llu %5llu"
1078 " %6lu %7lu %6llu %6llu\n",
1079 i,
1080 i < ntbins ? "T" : i < ntbins + nqbins ? "Q" : "S",
1081 arena->bins[i].reg_size,
1082 arena->bins[i].nregs,
1083 arena->bins[i].run_size,
1084 arena->bins[i].stats.nrequests,
1085 arena->bins[i].stats.nruns,
1086 arena->bins[i].stats.highruns,
1087 arena->bins[i].stats.curruns,
1088 arena->bins[i].stats.npromote,
1089 arena->bins[i].stats.ndemote);
1090 }
1091 }
1092 if (gap_start != -1) {
1093 if (i > gap_start + 1) {
1094 /* Gap of more than one size class. */
1095 malloc_printf("[%u..%u]\n", gap_start, i - 1);
1096 } else {
1097 /* Gap of one size class. */
1098 malloc_printf("[%u]\n", gap_start);
1099 }
1100 }
1101}
1102#endif
1103
1104/*
1105 * End Utility functions/macros.
1106 */
1107/******************************************************************************/
1108/*
1109 * Begin chunk management functions.
1110 */
1111
1112static inline int
1113chunk_comp(chunk_node_t *a, chunk_node_t *b)
1114{
1115
1116 assert(a != NULL);
1117 assert(b != NULL);
1118
1119 if ((uintptr_t)a->chunk < (uintptr_t)b->chunk)
1120 return (-1);
1121 else if (a->chunk == b->chunk)
1122 return (0);
1123 else
1124 return (1);
1125}
1126
1127/* Generate red-black tree code for chunks. */
1128RB_GENERATE_STATIC(chunk_tree_s, chunk_node_s, link, chunk_comp);
1129
1130static void *
1131pages_map(void *addr, size_t size)
1132{
1133 void *ret;
1134
1135 /*
1136 * We don't use MAP_FIXED here, because it can cause the *replacement*
1137 * of existing mappings, and we only want to create new mappings.
1138 */
1139 ret = mmap(addr, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON,
1140 -1, 0);
1141 assert(ret != NULL);
1142
1143 if (ret == MAP_FAILED)
1144 ret = NULL;
1145 else if (addr != NULL && ret != addr) {
1146 /*
1147 * We succeeded in mapping memory, but not in the right place.
1148 */
1149 if (munmap(ret, size) == -1) {
1150 char buf[STRERROR_BUF];
1151
1152 strerror_r(errno, buf, sizeof(buf));
1153 malloc_printf("%s: (malloc) Error in munmap(): %s\n",
1154 _getprogname(), buf);
1155 if (opt_abort)
1156 abort();
1157 }
1158 ret = NULL;
1159 }
1160
1161 assert(ret == NULL || (addr == NULL && ret != addr)
1162 || (addr != NULL && ret == addr));
1163 return (ret);
1164}
1165
1166static void
1167pages_unmap(void *addr, size_t size)
1168{
1169
1170 if (munmap(addr, size) == -1) {
1171 char buf[STRERROR_BUF];
1172
1173 strerror_r(errno, buf, sizeof(buf));
1174 malloc_printf("%s: (malloc) Error in munmap(): %s\n",
1175 _getprogname(), buf);
1176 if (opt_abort)
1177 abort();
1178 }
1179}
1180
1181static void *
1182chunk_alloc(size_t size)
1183{
1184 void *ret, *chunk;
1185 chunk_node_t *tchunk, *delchunk;
1186
1187 assert(size != 0);
1188 assert(size % chunk_size == 0);
1189
1190 malloc_mutex_lock(&chunks_mtx);
1191
1192 if (size == chunk_size) {
1193 /*
1194 * Check for address ranges that were previously chunks and try
1195 * to use them.
1196 */
1197
1198 tchunk = RB_MIN(chunk_tree_s, &old_chunks);
1199 while (tchunk != NULL) {
1200 /* Found an address range. Try to recycle it. */
1201
1202 chunk = tchunk->chunk;
1203 delchunk = tchunk;
1204 tchunk = RB_NEXT(chunk_tree_s, &old_chunks, delchunk);
1205
1206 /* Remove delchunk from the tree. */
1207 RB_REMOVE(chunk_tree_s, &old_chunks, delchunk);
1208 base_chunk_node_dealloc(delchunk);
1209
1210#ifdef USE_BRK
1211 if ((uintptr_t)chunk >= (uintptr_t)brk_base
1212 && (uintptr_t)chunk < (uintptr_t)brk_max) {
1213 /* Re-use a previously freed brk chunk. */
1214 ret = chunk;
1215 goto RETURN;
1216 }
1217#endif
1218 if ((ret = pages_map(chunk, size)) != NULL) {
1219 /* Success. */
1220 goto RETURN;
1221 }
1222 }
1223 }
1224
1225#ifdef USE_BRK
1226 /*
1227 * Try to create allocations in brk, in order to make full use of
1228 * limited address space.
1229 */
1230 if (brk_prev != (void *)-1) {
1231 void *brk_cur;
1232 intptr_t incr;
1233
1234 /*
1235 * The loop is necessary to recover from races with other
1236 * threads that are using brk for something other than malloc.
1237 */
1238 do {
1239 /* Get the current end of brk. */
1240 brk_cur = sbrk(0);
1241
1242 /*
1243 * Calculate how much padding is necessary to
1244 * chunk-align the end of brk.
1245 */
1246 incr = (intptr_t)size
1247 - (intptr_t)CHUNK_ADDR2OFFSET(brk_cur);
1248 if (incr == size) {
1249 ret = brk_cur;
1250 } else {
1251 ret = (void *)(intptr_t)brk_cur + incr;
1252 incr += size;
1253 }
1254
1255 brk_prev = sbrk(incr);
1256 if (brk_prev == brk_cur) {
1257 /* Success. */
1258 brk_max = (void *)(intptr_t)ret + size;
1259 goto RETURN;
1260 }
1261 } while (brk_prev != (void *)-1);
1262 }
1263#endif
1264
1265 /*
1266 * Try to over-allocate, but allow the OS to place the allocation
1267 * anywhere. Beware of size_t wrap-around.
1268 */
1269 if (size + chunk_size > size) {
1270 if ((ret = pages_map(NULL, size + chunk_size)) != NULL) {
1271 size_t offset = CHUNK_ADDR2OFFSET(ret);
1272
1273 /*
1274 * Success. Clean up unneeded leading/trailing space.
1275 */
1276 if (offset != 0) {
1277 /* Leading space. */
1278 pages_unmap(ret, chunk_size - offset);
1279
1280 ret = (void *)((uintptr_t)ret + (chunk_size -
1281 offset));
1282
1283 /* Trailing space. */
1284 pages_unmap((void *)((uintptr_t)ret + size),
1285 offset);
1286 } else {
1287 /* Trailing space only. */
1288 pages_unmap((void *)((uintptr_t)ret + size),
1289 chunk_size);
1290 }
1291 goto RETURN;
1292 }
1293 }
1294
1295 /* All strategies for allocation failed. */
1296 ret = NULL;
1297RETURN:
1298#ifdef MALLOC_STATS
1299 if (ret != NULL) {
1300 stats_chunks.nchunks += (size / chunk_size);
1301 stats_chunks.curchunks += (size / chunk_size);
1302 }
1303 if (stats_chunks.curchunks > stats_chunks.highchunks)
1304 stats_chunks.highchunks = stats_chunks.curchunks;
1305#endif
1306 malloc_mutex_unlock(&chunks_mtx);
1307
1308 assert(CHUNK_ADDR2BASE(ret) == ret);
1309 return (ret);
1310}
1311
1312static void
1313chunk_dealloc(void *chunk, size_t size)
1314{
1315 size_t offset;
1316 chunk_node_t key;
1317 chunk_node_t *node;
1318
1319 assert(chunk != NULL);
1320 assert(CHUNK_ADDR2BASE(chunk) == chunk);
1321 assert(size != 0);
1322 assert(size % chunk_size == 0);
1323
1324 malloc_mutex_lock(&chunks_mtx);
1325
1326#ifdef USE_BRK
1327 if ((uintptr_t)chunk >= (uintptr_t)brk_base
1328 && (uintptr_t)chunk < (uintptr_t)brk_max) {
1329 void *brk_cur;
1330
1331 /* Get the current end of brk. */
1332 brk_cur = sbrk(0);
1333
1334 /*
1335 * Try to shrink the data segment if this chunk is at the end
1336 * of the data segment. The sbrk() call here is subject to a
1337 * race condition with threads that use brk(2) or sbrk(2)
1338 * directly, but the alternative would be to leak memory for
1339 * the sake of poorly designed multi-threaded programs.
1340 */
1341 if (brk_cur == brk_max
1342 && (void *)(uintptr_t)chunk + size == brk_max
1343 && sbrk(-(intptr_t)size) == brk_max) {
1344 if (brk_prev == brk_max) {
1345 /* Success. */
1346 brk_prev = (void *)(intptr_t)brk_max
1347 - (intptr_t)size;
1348 brk_max = brk_prev;
1349 }
1350 goto RETURN;
1351 } else
1352 madvise(chunk, size, MADV_FREE);
1353 } else
1354#endif
1355 pages_unmap(chunk, size);
1356
1357 /*
1358 * Iteratively create records of each chunk-sized memory region that
1359 * 'chunk' is comprised of, so that the address range can be recycled
1360 * if memory usage increases later on.
1361 */
1362 for (offset = 0; offset < size; offset += chunk_size) {
1363 /*
1364 * It is possible for chunk to overlap existing entries in
1365 * old_chunks if it is a huge allocation, so take care to not
1366 * leak tree nodes.
1367 */
1368 key.chunk = (void *)((uintptr_t)chunk + (uintptr_t)offset);
1369 if (RB_FIND(chunk_tree_s, &old_chunks, &key) == NULL) {
1370 node = base_chunk_node_alloc();
1371 if (node == NULL)
1372 break;
1373
1374 node->chunk = key.chunk;
1375 node->size = chunk_size;
1376 RB_INSERT(chunk_tree_s, &old_chunks, node);
1377 }
1378 }
1379
1380#ifdef USE_BRK
1381RETURN:
1382#endif
1383#ifdef MALLOC_STATS
1384 stats_chunks.curchunks -= (size / chunk_size);
1385#endif
1386 malloc_mutex_unlock(&chunks_mtx);
1387}
1388
1389/*
1390 * End chunk management functions.
1391 */
1392/******************************************************************************/
1393/*
1394 * Begin arena.
1395 */
1396
1397/*
1398 * Choose an arena based on a per-thread value (fast-path code, calls slow-path
1399 * code if necessary.
1400 */
1401static inline arena_t *
1402choose_arena(void)
1403{
1404 arena_t *ret;
1405
1406 /*
1407 * We can only use TLS if this is a PIC library, since for the static
1408 * library version, libc's malloc is used by TLS allocation, which
1409 * introduces a bootstrapping issue.
1410 */
1411#ifndef NO_TLS
1412 if (__isthreaded == false) {
1413 /*
1414 * Avoid the overhead of TLS for single-threaded operation. If the
1415 * app switches to threaded mode, the initial thread may end up
1416 * being assigned to some other arena, but this one-time switch
1417 * shouldn't cause significant issues.
1418 * */
1419 return (arenas[0]);
1420 }
1421
1422 ret = arenas_map;
1423 if (ret == NULL)
1424 ret = choose_arena_hard();
1425#else
1426 if (__isthreaded) {
1427 unsigned long ind;
1428
1429 /*
1430 * Hash _pthread_self() to one of the arenas. There is a prime
1431 * number of arenas, so this has a reasonable chance of
1432 * working. Even so, the hashing can be easily thwarted by
1433 * inconvenient _pthread_self() values. Without specific
1434 * knowledge of how _pthread_self() calculates values, we can't
1435 * easily do much better than this.
1436 */
1437 ind = (unsigned long) _pthread_self() % narenas;
1438
1439 /*
1440 * Optimistially assume that arenas[ind] has been initialized.
1441 * At worst, we find out that some other thread has already
1442 * done so, after acquiring the lock in preparation. Note that
1443 * this lazy locking also has the effect of lazily forcing
1444 * cache coherency; without the lock acquisition, there's no
1445 * guarantee that modification of arenas[ind] by another thread
1446 * would be seen on this CPU for an arbitrary amount of time.
1447 *
1448 * In general, this approach to modifying a synchronized value
1449 * isn't a good idea, but in this case we only ever modify the
1450 * value once, so things work out well.
1451 */
1452 ret = arenas[ind];
1453 if (ret == NULL) {
1454 /*
1455 * Avoid races with another thread that may have already
1456 * initialized arenas[ind].
1457 */
1458 malloc_mutex_lock(&arenas_mtx);
1459 if (arenas[ind] == NULL)
1460 ret = arenas_extend((unsigned)ind);
1461 else
1462 ret = arenas[ind];
1463 malloc_mutex_unlock(&arenas_mtx);
1464 }
1465 } else
1466 ret = arenas[0];
1467#endif
1468
1469 assert(ret != NULL);
1470 return (ret);
1471}
1472
1473#ifndef NO_TLS
1474/*
1475 * Choose an arena based on a per-thread value (slow-path code only, called
1476 * only by choose_arena()).
1477 */
1478static arena_t *
1479choose_arena_hard(void)
1480{
1481 arena_t *ret;
1482
1483 assert(__isthreaded);
1484
1485 /* Assign one of the arenas to this thread, in a round-robin fashion. */
1486 malloc_mutex_lock(&arenas_mtx);
1487 ret = arenas[next_arena];
1488 if (ret == NULL)
1489 ret = arenas_extend(next_arena);
1490 if (ret == NULL) {
1491 /*
1492 * Make sure that this function never returns NULL, so that
1493 * choose_arena() doesn't have to check for a NULL return
1494 * value.
1495 */
1496 ret = arenas[0];
1497 }
1498 next_arena = (next_arena + 1) % narenas;
1499 malloc_mutex_unlock(&arenas_mtx);
1500 arenas_map = ret;
1501
1502 return (ret);
1503}
1504#endif
1505
1506static inline int
1507arena_chunk_comp(arena_chunk_t *a, arena_chunk_t *b)
1508{
1509
1510 assert(a != NULL);
1511 assert(b != NULL);
1512
1513 if ((uintptr_t)a < (uintptr_t)b)
1514 return (-1);
1515 else if (a == b)
1516 return (0);
1517 else
1518 return (1);
1519}
1520
1521/* Generate red-black tree code for arena chunks. */
1522RB_GENERATE_STATIC(arena_chunk_tree_s, arena_chunk_s, link, arena_chunk_comp);
1523
1524static inline void *
1525arena_run_reg_alloc(arena_run_t *run, arena_bin_t *bin)
1526{
1527 void *ret;
1528 unsigned i, mask, bit, regind;
1529
1530 assert(run->magic == ARENA_RUN_MAGIC);
1531
1532 for (i = run->regs_minelm; i < REGS_MASK_NELMS; i++) {
1533 mask = run->regs_mask[i];
1534 if (mask != 0) {
1535 /* Usable allocation found. */
1536 bit = ffs(mask) - 1;
1537
1538 regind = ((i << (SIZEOF_INT_2POW + 3)) + bit);
1539 ret = (void *)&((char *)run)[bin->reg0_offset
1540 + (bin->reg_size * regind)];
1541
1542 /* Clear bit. */
1543 mask ^= (1 << bit);
1544 run->regs_mask[i] = mask;
1545
1546 return (ret);
1547 } else {
1548 /*
1549 * Make a note that nothing before this element
1550 * contains a free region.
1551 */
1552 run->regs_minelm = i + 1;
1553 }
1554 }
1555 /* Not reached. */
1556 assert(0);
1557 return (NULL);
1558}
1559
1560static inline void
1561arena_run_reg_dalloc(arena_run_t *run, arena_bin_t *bin, void *ptr, size_t size)
1562{
1563 /*
1564 * To divide by a number D that is not a power of two we multiply
1565 * by (2^21 / D) and then right shift by 21 positions.
1566 *
1567 * X / D
1568 *
1569 * becomes
1570 *
1571 * (size_invs[(D >> QUANTUM_2POW_MIN) - 3] * D) >> SIZE_INV_SHIFT
1572 */
1573#define SIZE_INV_SHIFT 21
1574#define SIZE_INV(s) (((1 << SIZE_INV_SHIFT) / (s << QUANTUM_2POW_MIN)) + 1)
1575 static const unsigned size_invs[] = {
1576 SIZE_INV(3),
1577 SIZE_INV(4), SIZE_INV(5), SIZE_INV(6), SIZE_INV(7),
1578 SIZE_INV(8), SIZE_INV(9), SIZE_INV(10), SIZE_INV(11),
1579 SIZE_INV(12),SIZE_INV(13), SIZE_INV(14), SIZE_INV(15),
1580 SIZE_INV(16),SIZE_INV(17), SIZE_INV(18), SIZE_INV(19),
1581 SIZE_INV(20),SIZE_INV(21), SIZE_INV(22), SIZE_INV(23),
1582 SIZE_INV(24),SIZE_INV(25), SIZE_INV(26), SIZE_INV(27),
1583 SIZE_INV(28),SIZE_INV(29), SIZE_INV(30), SIZE_INV(31)
1584#if (QUANTUM_2POW_MIN < 4)
1585 ,
1586 SIZE_INV(32), SIZE_INV(33), SIZE_INV(34), SIZE_INV(35),
1587 SIZE_INV(36), SIZE_INV(37), SIZE_INV(38), SIZE_INV(39),
1588 SIZE_INV(40), SIZE_INV(41), SIZE_INV(42), SIZE_INV(43),
1589 SIZE_INV(44), SIZE_INV(45), SIZE_INV(46), SIZE_INV(47),
1590 SIZE_INV(48), SIZE_INV(49), SIZE_INV(50), SIZE_INV(51),
1591 SIZE_INV(52), SIZE_INV(53), SIZE_INV(54), SIZE_INV(55),
1592 SIZE_INV(56), SIZE_INV(57), SIZE_INV(58), SIZE_INV(59),
1593 SIZE_INV(60), SIZE_INV(61), SIZE_INV(62), SIZE_INV(63)
1594#endif
1595 };
1596 unsigned diff, regind, elm, bit;
1597
1598 assert(run->magic == ARENA_RUN_MAGIC);
1599 assert(((sizeof(size_invs)) / sizeof(unsigned)) + 3
1600 >= (SMALL_MAX_DEFAULT >> QUANTUM_2POW_MIN));
1601
1602 /*
1603 * Avoid doing division with a variable divisor if possible. Using
1604 * actual division here can reduce allocator throughput by over 20%!
1605 */
1606 diff = (unsigned)((uintptr_t)ptr - (uintptr_t)run - bin->reg0_offset);
1607 if ((size & (size - 1)) == 0) {
1608 /*
1609 * log2_table allows fast division of a power of two in the
1610 * [1..128] range.
1611 *
1612 * (x / divisor) becomes (x >> log2_table[divisor - 1]).
1613 */
1614 static const unsigned char log2_table[] = {
1615 0, 1, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 4,
1616 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5,
1617 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1618 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6,
1619 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1620 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1621 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1622 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7
1623 };
1624
1625 if (size <= 128)
1626 regind = (diff >> log2_table[size - 1]);
1627 else if (size <= 32768)
1628 regind = diff >> (8 + log2_table[(size >> 8) - 1]);
1629 else {
1630 /*
1631 * The page size is too large for us to use the lookup
1632 * table. Use real division.
1633 */
1634 regind = diff / size;
1635 }
1636 } else if (size <= ((sizeof(size_invs) / sizeof(unsigned))
1637 << QUANTUM_2POW_MIN) + 2) {
1638 regind = size_invs[(size >> QUANTUM_2POW_MIN) - 3] * diff;
1639 regind >>= SIZE_INV_SHIFT;
1640 } else {
1641 /*
1642 * size_invs isn't large enough to handle this size class, so
1643 * calculate regind using actual division. This only happens
1644 * if the user increases small_max via the 'S' runtime
1645 * configuration option.
1646 */
1647 regind = diff / size;
1648 };
1649 assert(regind == diff / size);
1650 assert(regind < bin->nregs);
1651
1652 elm = regind >> (SIZEOF_INT_2POW + 3);
1653 if (elm < run->regs_minelm)
1654 run->regs_minelm = elm;
1655 bit = regind - (elm << (SIZEOF_INT_2POW + 3));
1656 assert((run->regs_mask[elm] & (1 << bit)) == 0);
1657 run->regs_mask[elm] |= (1 << bit);
1658#undef SIZE_INV
1659#undef SIZE_INV_SHIFT
1660}
1661
1662static void
1663arena_run_split(arena_t *arena, arena_run_t *run, bool large, size_t size)
1664{
1665 arena_chunk_t *chunk;
1666 unsigned run_ind, map_offset, total_pages, need_pages;
1667 unsigned i, log2_run_pages, run_pages;
1668
1669 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
1670 run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk)
1671 >> pagesize_2pow);
1672 assert(chunk->map[run_ind].free);
1673 total_pages = chunk->map[run_ind].npages;
1674 need_pages = (size >> pagesize_2pow);
1675
1676 assert(chunk->map[run_ind].free);
1677 assert(chunk->map[run_ind].large == false);
1678 assert(chunk->map[run_ind].npages == total_pages);
1679
1680 /* Split enough pages from the front of run to fit allocation size. */
1681 map_offset = run_ind;
1682 for (i = 0; i < need_pages; i++) {
1683 chunk->map[map_offset + i].free = false;
1684 chunk->map[map_offset + i].large = large;
1685 chunk->map[map_offset + i].npages = need_pages;
1686 chunk->map[map_offset + i].pos = i;
1687 }
1688
1689 /* Update map for trailing pages. */
1690 map_offset += need_pages;
1691 while (map_offset < run_ind + total_pages) {
1692 log2_run_pages = ffs(map_offset) - 1;
1693 run_pages = (1 << log2_run_pages);
1694
1695 chunk->map[map_offset].free = true;
1696 chunk->map[map_offset].large = false;
1697 chunk->map[map_offset].npages = run_pages;
1698
1699 chunk->nfree_runs[log2_run_pages]++;
1700
1701 map_offset += run_pages;
1702 }
1703
1704 chunk->pages_used += (size >> pagesize_2pow);
1705}
1706
1707static arena_chunk_t *
1708arena_chunk_alloc(arena_t *arena)
1709{
1710 arena_chunk_t *chunk;
1711 unsigned i, j, header_npages, pow2_header_npages, map_offset;
1712 unsigned log2_run_pages, run_pages;
1713 size_t header_size;
1714
1715 chunk = (arena_chunk_t *)chunk_alloc(chunk_size);
1716 if (chunk == NULL)
1717 return (NULL);
1718
1719 chunk->arena = arena;
1720
1721 RB_INSERT(arena_chunk_tree_s, &arena->chunks, chunk);
1722
1723 /*
1724 * Claim that no pages are in use, since the header is merely overhead.
1725 */
1726 chunk->pages_used = 0;
1727
1728 memset(&chunk->nfree_runs, 0, sizeof(chunk->nfree_runs));
1729
1730 header_size = (size_t)((uintptr_t)&chunk->map[arena_chunk_maplen]
1731 - (uintptr_t)chunk);
1732 if (header_size % pagesize != 0) {
1733 /* Round up to the nearest page boundary. */
1734 header_size += pagesize - (header_size % pagesize);
1735 }
1736
1737 header_npages = header_size >> pagesize_2pow;
1738 pow2_header_npages = pow2_ceil(header_npages);
1739
1740 /*
1741 * Iteratively mark runs as in use, until we've spoken for the entire
1742 * header.
1743 */
1744 map_offset = 0;
1745 for (i = 0; header_npages > 0; i++) {
1746 if ((pow2_header_npages >> i) <= header_npages) {
1747 for (j = 0; j < (pow2_header_npages >> i); j++) {
1748 chunk->map[map_offset + j].free = false;
1749 chunk->map[map_offset + j].large = false;
1750 chunk->map[map_offset + j].npages =
1751 (pow2_header_npages >> i);
1752 chunk->map[map_offset + j].pos = j;
1753 }
1754 header_npages -= (pow2_header_npages >> i);
1755 map_offset += (pow2_header_npages >> i);
1756 }
1757 }
1758
1759 /*
1760 * Finish initializing map. The chunk header takes up some space at
1761 * the beginning of the chunk, which we just took care of by
1762 * "allocating" the leading pages.
1763 */
1764 while (map_offset < (chunk_size >> pagesize_2pow)) {
1765 log2_run_pages = ffs(map_offset) - 1;
1766 run_pages = (1 << log2_run_pages);
1767
1768 chunk->map[map_offset].free = true;
1769 chunk->map[map_offset].large = false;
1770 chunk->map[map_offset].npages = run_pages;
1771
1772 chunk->nfree_runs[log2_run_pages]++;
1773
1774 map_offset += run_pages;
1775 }
1776
1777 return (chunk);
1778}
1779
1780static void
1781arena_chunk_dealloc(arena_chunk_t *chunk)
1782{
1783
1784 RB_REMOVE(arena_chunk_tree_s, &chunk->arena->chunks, chunk);
1785
1786 chunk_dealloc((void *)chunk, chunk_size);
1787}
1788
1789static void
1790arena_bin_run_promote(arena_t *arena, arena_bin_t *bin, arena_run_t *run)
1791{
1792
1793 assert(bin == run->bin);
1794
1795 /* Promote. */
1796 assert(run->free_min > run->nfree);
1797 assert(run->quartile < RUN_Q100);
1798 run->quartile++;
1799#ifdef MALLOC_STATS
1800 bin->stats.npromote++;
1801#endif
1802
1803 /* Re-file run. */
1804 switch (run->quartile) {
1805 case RUN_QINIT:
1806 assert(0);
1807 break;
1808 case RUN_Q0:
1809 qr_before_insert((arena_run_t *)&bin->runs0, run, link);
1810 run->free_max = bin->nregs - 1;
1811 run->free_min = (bin->nregs >> 1) + 1;
1812 assert(run->nfree <= run->free_max);
1813 assert(run->nfree >= run->free_min);
1814 break;
1815 case RUN_Q25:
1816 qr_remove(run, link);
1817 qr_before_insert((arena_run_t *)&bin->runs25, run,
1818 link);
1819 run->free_max = ((bin->nregs >> 2) * 3) - 1;
1820 run->free_min = (bin->nregs >> 2) + 1;
1821 assert(run->nfree <= run->free_max);
1822 assert(run->nfree >= run->free_min);
1823 break;
1824 case RUN_Q50:
1825 qr_remove(run, link);
1826 qr_before_insert((arena_run_t *)&bin->runs50, run,
1827 link);
1828 run->free_max = (bin->nregs >> 1) - 1;
1829 run->free_min = 1;
1830 assert(run->nfree <= run->free_max);
1831 assert(run->nfree >= run->free_min);
1832 break;
1833 case RUN_Q75:
1834 /*
1835 * Skip RUN_Q75 during promotion from RUN_Q50.
1836 * Separate handling of RUN_Q75 and RUN_Q100 allows us
1837 * to keep completely full runs in RUN_Q100, thus
1838 * guaranteeing that runs in RUN_Q75 are only mostly
1839 * full. This provides a method for avoiding a linear
1840 * search for non-full runs, which avoids some
1841 * pathological edge cases.
1842 */
1843 run->quartile++;
1844 /* Fall through. */
1845 case RUN_Q100:
1846 qr_remove(run, link);
1847 assert(bin->runcur == run);
1848 bin->runcur = NULL;
1849 run->free_max = 0;
1850 run->free_min = 0;
1851 assert(run->nfree <= run->free_max);
1852 assert(run->nfree >= run->free_min);
1853 break;
1854 default:
1855 assert(0);
1856 break;
1857 }
1858}
1859
1860static void
1861arena_bin_run_demote(arena_t *arena, arena_bin_t *bin, arena_run_t *run)
1862{
1863
1864 assert(bin == run->bin);
1865
1866 /* Demote. */
1867 assert(run->free_max < run->nfree);
1868 assert(run->quartile > RUN_QINIT);
1869 run->quartile--;
1870#ifdef MALLOC_STATS
1871 bin->stats.ndemote++;
1872#endif
1873
1874 /* Re-file run. */
1875 switch (run->quartile) {
1876 case RUN_QINIT:
1877 qr_remove(run, link);
1878#ifdef MALLOC_STATS
1879 bin->stats.curruns--;
1880#endif
1881 if (bin->runcur == run)
1882 bin->runcur = NULL;
1883#ifdef MALLOC_DEBUG
1884 run->magic = 0;
1885#endif
1886 arena_run_dalloc(arena, run, bin->run_size);
1887 break;
1888 case RUN_Q0:
1889 qr_remove(run, link);
1890 qr_before_insert((arena_run_t *)&bin->runs0, run, link);
1891 run->free_max = bin->nregs - 1;
1892 run->free_min = (bin->nregs >> 1) + 1;
1893 assert(run->nfree <= run->free_max);
1894 assert(run->nfree >= run->free_min);
1895 break;
1896 case RUN_Q25:
1897 qr_remove(run, link);
1898 qr_before_insert((arena_run_t *)&bin->runs25, run,
1899 link);
1900 run->free_max = ((bin->nregs >> 2) * 3) - 1;
1901 run->free_min = (bin->nregs >> 2) + 1;
1902 assert(run->nfree <= run->free_max);
1903 assert(run->nfree >= run->free_min);
1904 break;
1905 case RUN_Q50:
1906 qr_remove(run, link);
1907 qr_before_insert((arena_run_t *)&bin->runs50, run,
1908 link);
1909 run->free_max = (bin->nregs >> 1) - 1;
1910 run->free_min = 1;
1911 assert(run->nfree <= run->free_max);
1912 assert(run->nfree >= run->free_min);
1913 break;
1914 case RUN_Q75:
1915 qr_before_insert((arena_run_t *)&bin->runs75, run,
1916 link);
1917 run->free_max = (bin->nregs >> 2) - 1;
1918 run->free_min = 1;
1919 assert(run->nfree <= run->free_max);
1920 assert(run->nfree >= run->free_min);
1921 break;
1922 case RUN_Q100:
1923 default:
1924 assert(0);
1925 break;
1926 }
1927}
1928
1929static arena_run_t *
1930arena_run_alloc(arena_t *arena, bool large, size_t size)
1931{
1932 arena_run_t *run;
1933 unsigned min_ind, i, j;
1934 arena_chunk_t *chunk;
1935#ifndef NDEBUG
1936 int rep = 0;
1937#endif
1938
1939 assert(size <= arena_maxclass);
1940
1941AGAIN:
1942#ifndef NDEBUG
1943 rep++;
1944 assert(rep <= 2);
1945#endif
1946
1947 /*
1948 * Search through arena's chunks in address order for a run that is
1949 * large enough. Look for a precise fit, but do not pass up a chunk
1950 * that has a run which is large enough to split.
1951 */
1952 min_ind = ffs(size >> pagesize_2pow) - 1;
1953 RB_FOREACH(chunk, arena_chunk_tree_s, &arena->chunks) {
1954 for (i = min_ind;
1955 i < (opt_chunk_2pow - pagesize_2pow);
1956 i++) {
1957 if (chunk->nfree_runs[i] > 0) {
1958 arena_chunk_map_t *map = chunk->map;
1959
1960 /* Scan chunk's map for free run. */
1961 for (j = 0;
1962 j < arena_chunk_maplen;
1963 j += map[j].npages) {
1964 if (map[j].free
1965 && map[j].npages == (1 << i))
1966 {/*<----------------------------*/
1967 run = (arena_run_t *)&((char *)chunk)[j
1968 << pagesize_2pow];
1969
1970 assert(chunk->nfree_runs[i] > 0);
1971 chunk->nfree_runs[i]--;
1972
1973 /* Update page map. */
1974 arena_run_split(arena, run, large, size);
1975
1976 return (run);
1977 }/*---------------------------->*/
1978 }
1979 /* Not reached. */
1980 assert(0);
1981 }
1982 }
1983 }
1984
1985 /* No usable runs. Allocate a new chunk, then try again. */
1986 if (arena_chunk_alloc(arena) == NULL)
1987 return (NULL);
1988 goto AGAIN;
1989}
1990
1991static void
1992arena_run_dalloc(arena_t *arena, arena_run_t *run, size_t size)
1993{
1994 arena_chunk_t *chunk;
1995 unsigned run_ind, buddy_ind, base_run_ind, run_pages, log2_run_pages;
1996
1997 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
1998 run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk)
1999 >> pagesize_2pow);
2000 run_pages = (size >> pagesize_2pow);
2001 log2_run_pages = ffs(run_pages) - 1;
2002 assert(run_pages > 0);
2003
2004 /* Subtract pages from count of pages used in chunk. */
2005 chunk->pages_used -= run_pages;
2006
2007 /* Mark run as deallocated. */
2008 chunk->map[run_ind].free = true;
2009 chunk->map[run_ind].large = false;
2010 chunk->map[run_ind].npages = run_pages;
2011
2012 /*
2013 * Tell the kernel that we don't need the data in this run, but only if
2014 * requested via runtime configuration.
2015 */
2016 if (opt_hint) {
2017 madvise(run, size, MADV_FREE);
2018#ifdef MALLOC_STATS
2019 arena->stats.nmadvise += (size >> pagesize_2pow);
2020#endif
2021 }
2022
2023 /*
2024 * Iteratively coalesce with buddies. Conceptually, the buddy scheme
2025 * induces a tree on the set of pages. If we know the number of pages
2026 * in the subtree rooted at the current node, we can quickly determine
2027 * whether a run is the left or right buddy, and then calculate the
2028 * buddy's index.
2029 */
2030 for (;
2031 (run_pages = (1 << log2_run_pages)) < arena_chunk_maplen;
2032 log2_run_pages++) {
2033 if (((run_ind >> log2_run_pages) & 1) == 0) {
2034 /* Current run precedes its buddy. */
2035 buddy_ind = run_ind + run_pages;
2036 base_run_ind = run_ind;
2037 } else {
2038 /* Current run follows its buddy. */
2039 buddy_ind = run_ind - run_pages;
2040 base_run_ind = buddy_ind;
2041 }
2042
2043 if (chunk->map[buddy_ind].free == false
2044 || chunk->map[buddy_ind].npages != run_pages)
2045 break;
2046
2047 assert(chunk->nfree_runs[log2_run_pages] > 0);
2048 chunk->nfree_runs[log2_run_pages]--;
2049
2050 /* Coalesce. */
2051 chunk->map[base_run_ind].npages = (run_pages << 1);
2052
2053 /* Update run_ind to be the beginning of the coalesced run. */
2054 run_ind = base_run_ind;
2055 }
2056
2057 chunk->nfree_runs[log2_run_pages]++;
2058
2059 /* Free pages, to the extent possible. */
2060 if (chunk->pages_used == 0) {
2061 /* This chunk is completely unused now, so deallocate it. */
2062 arena_chunk_dealloc(chunk);
2063 }
2064}
2065
2066static arena_run_t *
2067arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin)
2068{
2069 arena_run_t *run;
2070 unsigned i, remainder;
2071
2072 /* Look for a usable run. */
2073 if ((run = qr_next((arena_run_t *)&bin->runs50, link))
2074 != (arena_run_t *)&bin->runs50
2075 || (run = qr_next((arena_run_t *)&bin->runs25, link))
2076 != (arena_run_t *)&bin->runs25
2077 || (run = qr_next((arena_run_t *)&bin->runs0, link))
2078 != (arena_run_t *)&bin->runs0
2079 || (run = qr_next((arena_run_t *)&bin->runs75, link))
2080 != (arena_run_t *)&bin->runs75) {
2081 /* run is guaranteed to have available space. */
2082 qr_remove(run, link);
2083 return (run);
2084 }
2085 /* No existing runs have any space available. */
2086
2087 /* Allocate a new run. */
2088 run = arena_run_alloc(arena, false, bin->run_size);
2089 if (run == NULL)
2090 return (NULL);
2091
2092 /* Initialize run internals. */
2093 qr_new(run, link);
2094 run->bin = bin;
2095
2096 for (i = 0; i < (bin->nregs >> (SIZEOF_INT_2POW + 3)); i++)
2097 run->regs_mask[i] = UINT_MAX;
2098 remainder = bin->nregs % (1 << (SIZEOF_INT_2POW + 3));
2099 if (remainder != 0) {
2100 run->regs_mask[i] = (UINT_MAX >> ((1 << (SIZEOF_INT_2POW + 3))
2101 - remainder));
2102 i++;
2103 }
2104 for (; i < REGS_MASK_NELMS; i++)
2105 run->regs_mask[i] = 0;
2106
2107 run->regs_minelm = 0;
2108
2109 run->nfree = bin->nregs;
2110 run->quartile = RUN_QINIT;
2111 run->free_max = bin->nregs;
2112 run->free_min = ((bin->nregs >> 2) * 3) + 1;
2113#ifdef MALLOC_DEBUG
2114 run->magic = ARENA_RUN_MAGIC;
2115#endif
2116
2117#ifdef MALLOC_STATS
2118 bin->stats.nruns++;
2119 bin->stats.curruns++;
2120 if (bin->stats.curruns > bin->stats.highruns)
2121 bin->stats.highruns = bin->stats.curruns;
2122#endif
2123 return (run);
2124}
2125
2126/* bin->runcur must have space available before this function is called. */
2127static inline void *
2128arena_bin_malloc_easy(arena_t *arena, arena_bin_t *bin, arena_run_t *run)
2129{
2130 void *ret;
2131
2132 assert(run->magic == ARENA_RUN_MAGIC);
2133 assert(run->nfree > 0);
2134
2135 ret = arena_run_reg_alloc(run, bin);
2136 assert(ret != NULL);
2137 run->nfree--;
2138 if (run->nfree < run->free_min) {
2139 /* Promote run to higher fullness quartile. */
2140 arena_bin_run_promote(arena, bin, run);
2141 }
2142
2143 return (ret);
2144}
2145
2146/* Re-fill bin->runcur, then call arena_bin_malloc_easy(). */
2147static void *
2148arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin)
2149{
2150
2151 assert(bin->runcur == NULL || bin->runcur->quartile == RUN_Q100);
2152
2153 bin->runcur = arena_bin_nonfull_run_get(arena, bin);
2154 if (bin->runcur == NULL)
2155 return (NULL);
2156 assert(bin->runcur->magic == ARENA_RUN_MAGIC);
2157 assert(bin->runcur->nfree > 0);
2158
2159 return (arena_bin_malloc_easy(arena, bin, bin->runcur));
2160}
2161
2162static void *
2163arena_malloc(arena_t *arena, size_t size)
2164{
2165 void *ret;
2166
2167 assert(arena != NULL);
2168 assert(arena->magic == ARENA_MAGIC);
2169 assert(size != 0);
2170 assert(QUANTUM_CEILING(size) <= arena_maxclass);
2171
2172 if (size <= bin_maxclass) {
2173 arena_bin_t *bin;
2174 arena_run_t *run;
2175
2176 /* Small allocation. */
2177
2178 if (size < small_min) {
2179 /* Tiny. */
2180 size = pow2_ceil(size);
2181 bin = &arena->bins[ffs(size >> (tiny_min_2pow + 1))];
2182#if (!defined(NDEBUG) || defined(MALLOC_STATS))
2183 /*
2184 * Bin calculation is always correct, but we may need
2185 * to fix size for the purposes of assertions and/or
2186 * stats accuracy.
2187 */
2188 if (size < (1 << tiny_min_2pow))
2189 size = (1 << tiny_min_2pow);
2190#endif
2191 } else if (size <= small_max) {
2192 /* Quantum-spaced. */
2193 size = QUANTUM_CEILING(size);
2194 bin = &arena->bins[ntbins + (size >> opt_quantum_2pow)
2195 - 1];
2196 } else {
2197 /* Sub-page. */
2198 size = pow2_ceil(size);
2199 bin = &arena->bins[ntbins + nqbins
2200 + (ffs(size >> opt_small_max_2pow) - 2)];
2201 }
2202 assert(size == bin->reg_size);
2203
2204 malloc_mutex_lock(&arena->mtx);
2205 if ((run = bin->runcur) != NULL)
2206 ret = arena_bin_malloc_easy(arena, bin, run);
2207 else
2208 ret = arena_bin_malloc_hard(arena, bin);
2209
2210#ifdef MALLOC_STATS
2211 bin->stats.nrequests++;
2212#endif
2213 } else {
2214 /* Medium allocation. */
2215 size = pow2_ceil(size);
2216 malloc_mutex_lock(&arena->mtx);
2217 ret = (void *)arena_run_alloc(arena, true, size);
2218#ifdef MALLOC_STATS
2219 arena->stats.large_nrequests++;
2220#endif
2221 }
2222
2223#ifdef MALLOC_STATS
2224 arena->stats.nmalloc++;
2225 if (ret != NULL)
2226 arena->stats.allocated += size;
2227#endif
2228
2229 malloc_mutex_unlock(&arena->mtx);
2230
2231 if (opt_junk && ret != NULL)
2232 memset(ret, 0xa5, size);
2233 else if (opt_zero && ret != NULL)
2234 memset(ret, 0, size);
2235 return (ret);
2236}
2237
2238/* Return the size of the allocation pointed to by ptr. */
2239static size_t
2240arena_salloc(const void *ptr)
2241{
2242 size_t ret;
2243 arena_chunk_t *chunk;
2244 uint32_t pageind;
2245 arena_chunk_map_t mapelm;
2246
2247 assert(ptr != NULL);
2248 assert(CHUNK_ADDR2BASE(ptr) != ptr);
2249
2250 /*
2251 * No arena data structures that we query here can change in a way that
2252 * affects this function, so we don't need to lock.
2253 */
2254 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
2255 pageind = (((uintptr_t)ptr - (uintptr_t)chunk) >> pagesize_2pow);
2256 mapelm = chunk->map[pageind];
2257 assert(mapelm.free == false);
2258 if (mapelm.large == false) {
2259 arena_run_t *run;
2260
2261 pageind -= mapelm.pos;
2262
2263 run = (arena_run_t *)&((char *)chunk)[pageind << pagesize_2pow];
2264 assert(run->magic == ARENA_RUN_MAGIC);
2265 ret = run->bin->reg_size;
2266 } else
2267 ret = mapelm.npages << pagesize_2pow;
2268
2269 return (ret);
2270}
2271
2272static void *
2273arena_ralloc(void *ptr, size_t size, size_t oldsize)
2274{
2275 void *ret;
2276
2277 /* Avoid moving the allocation if the size class would not change. */
2278 if (size < small_min) {
2279 if (oldsize < small_min &&
2280 ffs(pow2_ceil(size) >> (tiny_min_2pow + 1))
2281 == ffs(pow2_ceil(oldsize) >> (tiny_min_2pow + 1)))
2282 goto IN_PLACE;
2283 } else if (size <= small_max) {
2284 if (oldsize >= small_min && oldsize <= small_max &&
2285 (QUANTUM_CEILING(size) >> opt_quantum_2pow)
2286 == (QUANTUM_CEILING(oldsize) >> opt_quantum_2pow))
2287 goto IN_PLACE;
2288 } else {
2289 if (oldsize > small_max && pow2_ceil(size) == oldsize)
2290 goto IN_PLACE;
2291 }
2292
2293 /*
2294 * If we get here, then size and oldsize are different enough that we
2295 * need to use a different size class. In that case, fall back to
2296 * allocating new space and copying.
2297 */
2298 ret = arena_malloc(choose_arena(), size);
2299 if (ret == NULL)
2300 return (NULL);
2301
2302 if (size < oldsize)
2303 memcpy(ret, ptr, size);
2304 else
2305 memcpy(ret, ptr, oldsize);
2306 idalloc(ptr);
2307 return (ret);
2308IN_PLACE:
2309 if (opt_junk && size < oldsize)
2310 memset(&((char *)ptr)[size], 0x5a, oldsize - size);
2311 else if (opt_zero && size > oldsize)
2312 memset(&((char *)ptr)[size], 0, size - oldsize);
2313 return (ptr);
2314}
2315
2316static void
2317arena_dalloc(arena_t *arena, arena_chunk_t *chunk, void *ptr)
2318{
2319 unsigned pageind;
2320 arena_chunk_map_t mapelm;
2321 size_t size;
2322
2323 assert(arena != NULL);
2324 assert(arena->magic == ARENA_MAGIC);
2325 assert(chunk->arena == arena);
2326 assert(ptr != NULL);
2327 assert(CHUNK_ADDR2BASE(ptr) != ptr);
2328
2329 pageind = (((uintptr_t)ptr - (uintptr_t)chunk) >> pagesize_2pow);
2330 mapelm = chunk->map[pageind];
2331 assert(mapelm.free == false);
2332 if (mapelm.large == false) {
2333 arena_run_t *run;
2334 arena_bin_t *bin;
2335
2336 /* Small allocation. */
2337
2338 pageind -= mapelm.pos;
2339
2340 run = (arena_run_t *)&((char *)chunk)[pageind << pagesize_2pow];
2341 assert(run->magic == ARENA_RUN_MAGIC);
2342 bin = run->bin;
2343 size = bin->reg_size;
2344
2345 if (opt_junk)
2346 memset(ptr, 0x5a, size);
2347
2348 malloc_mutex_lock(&arena->mtx);
2349 arena_run_reg_dalloc(run, bin, ptr, size);
2350 run->nfree++;
2351 if (run->nfree > run->free_max) {
2352 /* Demote run to lower fullness quartile. */
2353 arena_bin_run_demote(arena, bin, run);
2354 }
2355 } else {
2356 /* Medium allocation. */
2357
2358 size = mapelm.npages << pagesize_2pow;
2359 assert((((uintptr_t)ptr) & (size - 1)) == 0);
2360
2361 if (opt_junk)
2362 memset(ptr, 0x5a, size);
2363
2364 malloc_mutex_lock(&arena->mtx);
2365 arena_run_dalloc(arena, (arena_run_t *)ptr, size);
2366 }
2367
2368#ifdef MALLOC_STATS
2369 arena->stats.allocated -= size;
2370#endif
2371
2372 malloc_mutex_unlock(&arena->mtx);
2373}
2374
2375static bool
2376arena_new(arena_t *arena)
2377{
2378 unsigned i;
2379 arena_bin_t *bin;
2380 size_t pow2_size, run_size;
2381
2382 malloc_mutex_init(&arena->mtx);
2383
2384#ifdef MALLOC_STATS
2385 memset(&arena->stats, 0, sizeof(arena_stats_t));
2386#endif
2387
2388 /* Initialize chunks. */
2389 RB_INIT(&arena->chunks);
2390
2391 /* Initialize bins. */
2392
2393 /* (2^n)-spaced tiny bins. */
2394 for (i = 0; i < ntbins; i++) {
2395 bin = &arena->bins[i];
2396 bin->runcur = NULL;
2397 qr_new((arena_run_t *)&bin->runs0, link);
2398 qr_new((arena_run_t *)&bin->runs25, link);
2399 qr_new((arena_run_t *)&bin->runs50, link);
2400 qr_new((arena_run_t *)&bin->runs75, link);
2401
2402 bin->reg_size = (1 << (tiny_min_2pow + i));
2403
2404 /*
2405 * Calculate how large of a run to allocate. Make sure that at
2406 * least RUN_MIN_REGS regions fit in the run.
2407 */
2408 run_size = bin->reg_size << RUN_MIN_REGS_2POW;
2409 if (run_size < pagesize)
2410 run_size = pagesize;
2411 if (run_size > (pagesize << RUN_MAX_PAGES_2POW))
2412 run_size = (pagesize << RUN_MAX_PAGES_2POW);
2413 if (run_size > arena_maxclass)
2414 run_size = arena_maxclass;
2415 bin->run_size = run_size;
2416
2417 assert(run_size >= sizeof(arena_run_t));
2418 bin->nregs = (run_size - sizeof(arena_run_t)) / bin->reg_size;
2419 if (bin->nregs > (REGS_MASK_NELMS << (SIZEOF_INT_2POW + 3))) {
2420 /* Take care not to overflow regs_mask. */
2421 bin->nregs = REGS_MASK_NELMS << (SIZEOF_INT_2POW + 3);
2422 }
2423 bin->reg0_offset = run_size - (bin->nregs * bin->reg_size);
2424
2425#ifdef MALLOC_STATS
2426 memset(&bin->stats, 0, sizeof(malloc_bin_stats_t));
2427#endif
2428 }
2429
2430 /* Quantum-spaced bins. */
2431 for (; i < ntbins + nqbins; i++) {
2432 bin = &arena->bins[i];
2433 bin->runcur = NULL;
2434 qr_new((arena_run_t *)&bin->runs0, link);
2435 qr_new((arena_run_t *)&bin->runs25, link);
2436 qr_new((arena_run_t *)&bin->runs50, link);
2437 qr_new((arena_run_t *)&bin->runs75, link);
2438
2439 bin->reg_size = quantum * (i - ntbins + 1);
2440
2441 /*
2442 * Calculate how large of a run to allocate. Make sure that at
2443 * least RUN_MIN_REGS regions fit in the run.
2444 */
2445 pow2_size = pow2_ceil(quantum * (i - ntbins + 1));
2446 run_size = (pow2_size << RUN_MIN_REGS_2POW);
2447 if (run_size < pagesize)
2448 run_size = pagesize;
2449 if (run_size > (pagesize << RUN_MAX_PAGES_2POW))
2450 run_size = (pagesize << RUN_MAX_PAGES_2POW);
2451 if (run_size > arena_maxclass)
2452 run_size = arena_maxclass;
2453 bin->run_size = run_size;
2454
2455 bin->nregs = (run_size - sizeof(arena_run_t)) / bin->reg_size;
2456 assert(bin->nregs <= REGS_MASK_NELMS << (SIZEOF_INT_2POW + 3));
2457 bin->reg0_offset = run_size - (bin->nregs * bin->reg_size);
2458
2459#ifdef MALLOC_STATS
2460 memset(&bin->stats, 0, sizeof(malloc_bin_stats_t));
2461#endif
2462 }
2463
2464 /* (2^n)-spaced sub-page bins. */
2465 for (; i < ntbins + nqbins + nsbins; i++) {
2466 bin = &arena->bins[i];
2467 bin->runcur = NULL;
2468 qr_new((arena_run_t *)&bin->runs0, link);
2469 qr_new((arena_run_t *)&bin->runs25, link);
2470 qr_new((arena_run_t *)&bin->runs50, link);
2471 qr_new((arena_run_t *)&bin->runs75, link);
2472
2473 bin->reg_size = (small_max << (i - (ntbins + nqbins) + 1));
2474
2475 /*
2476 * Calculate how large of a run to allocate. Make sure that at
2477 * least RUN_MIN_REGS regions fit in the run.
2478 */
2479 run_size = bin->reg_size << RUN_MIN_REGS_2POW;
2480 if (run_size < pagesize)
2481 run_size = pagesize;
2482 if (run_size > (pagesize << RUN_MAX_PAGES_2POW))
2483 run_size = (pagesize << RUN_MAX_PAGES_2POW);
2484 if (run_size > arena_maxclass)
2485 run_size = arena_maxclass;
2486 bin->run_size = run_size;
2487
2488 bin->nregs = (run_size - sizeof(arena_run_t)) / bin->reg_size;
2489 assert(bin->nregs <= REGS_MASK_NELMS << (SIZEOF_INT_2POW + 3));
2490 bin->reg0_offset = run_size - (bin->nregs * bin->reg_size);
2491
2492#ifdef MALLOC_STATS
2493 memset(&bin->stats, 0, sizeof(malloc_bin_stats_t));
2494#endif
2495 }
2496
2497#ifdef MALLOC_DEBUG
2498 arena->magic = ARENA_MAGIC;
2499#endif
2500
2501 return (false);
2502}
2503
2504/* Create a new arena and insert it into the arenas array at index ind. */
2505static arena_t *
2506arenas_extend(unsigned ind)
2507{
2508 arena_t *ret;
2509
2510 /* Allocate enough space for trailing bins. */
2511 ret = (arena_t *)base_alloc(sizeof(arena_t)
2512 + (sizeof(arena_bin_t) * (ntbins + nqbins + nsbins - 1)));
2513 if (ret != NULL && arena_new(ret) == false) {
2514 arenas[ind] = ret;
2515 return (ret);
2516 }
2517 /* Only reached if there is an OOM error. */
2518
2519 /*
2520 * OOM here is quite inconvenient to propagate, since dealing with it
2521 * would require a check for failure in the fast path. Instead, punt
2522 * by using arenas[0]. In practice, this is an extremely unlikely
2523 * failure.
2524 */
2525 malloc_printf("%s: (malloc) Error initializing arena\n",
2526 _getprogname());
2527 if (opt_abort)
2528 abort();
2529
2530 return (arenas[0]);
2531}
2532
2533/*
2534 * End arena.
2535 */
2536/******************************************************************************/
2537/*
2538 * Begin general internal functions.
2539 */
2540
2541static void *
2542huge_malloc(size_t size)
2543{
2544 void *ret;
2545 size_t csize;
2546 chunk_node_t *node;
2547
2548 /* Allocate one or more contiguous chunks for this request. */
2549
2550 csize = CHUNK_CEILING(size);
2551 if (csize == 0) {
2552 /* size is large enough to cause size_t wrap-around. */
2553 return (NULL);
2554 }
2555
2556 /* Allocate a chunk node with which to track the chunk. */
2557 node = base_chunk_node_alloc();
2558 if (node == NULL)
2559 return (NULL);
2560
2561 ret = chunk_alloc(csize);
2562 if (ret == NULL) {
2563 base_chunk_node_dealloc(node);
2564 return (NULL);
2565 }
2566
2567 /* Insert node into huge. */
2568 node->chunk = ret;
2569 node->size = csize;
2570
2571 malloc_mutex_lock(&chunks_mtx);
2572 RB_INSERT(chunk_tree_s, &huge, node);
2573#ifdef MALLOC_STATS
2574 huge_nmalloc++;
2575 huge_allocated += csize;
2576#endif
2577 malloc_mutex_unlock(&chunks_mtx);
2578
2579 if (opt_junk && ret != NULL)
2580 memset(ret, 0xa5, csize);
2581 else if (opt_zero && ret != NULL)
2582 memset(ret, 0, csize);
2583
2584 return (ret);
2585}
2586
2587static void *
2588huge_ralloc(void *ptr, size_t size, size_t oldsize)
2589{
2590 void *ret;
2591
2592 /* Avoid moving the allocation if the size class would not change. */
2593 if (oldsize > arena_maxclass &&
2594 CHUNK_CEILING(size) == CHUNK_CEILING(oldsize))
2595 return (ptr);
2596
2597 /*
2598 * If we get here, then size and oldsize are different enough that we
2599 * need to use a different size class. In that case, fall back to
2600 * allocating new space and copying.
2601 */
2602 ret = huge_malloc(size);
2603 if (ret == NULL)
2604 return (NULL);
2605
2606 if (CHUNK_ADDR2BASE(ptr) == ptr) {
2607 /* The old allocation is a chunk. */
2608 if (size < oldsize)
2609 memcpy(ret, ptr, size);
2610 else
2611 memcpy(ret, ptr, oldsize);
2612 } else {
2613 /* The old allocation is a region. */
2614 assert(oldsize < size);
2615 memcpy(ret, ptr, oldsize);
2616 }
2617 idalloc(ptr);
2618 return (ret);
2619}
2620
2621static void
2622huge_dalloc(void *ptr)
2623{
2624 chunk_node_t key;
2625 chunk_node_t *node;
2626
2627 malloc_mutex_lock(&chunks_mtx);
2628
2629 /* Extract from tree of huge allocations. */
2630 key.chunk = ptr;
2631 node = RB_FIND(chunk_tree_s, &huge, &key);
2632 assert(node != NULL);
2633 assert(node->chunk == ptr);
2634 RB_REMOVE(chunk_tree_s, &huge, node);
2635
2636#ifdef MALLOC_STATS
2637 /* Update counters. */
2638 huge_ndalloc++;
2639 huge_allocated -= node->size;
2640#endif
2641
2642 malloc_mutex_unlock(&chunks_mtx);
2643
2644 /* Unmap chunk. */
2645#ifdef USE_BRK
2646 if (opt_junk)
2647 memset(node->chunk, 0x5a, node->size);
2648#endif
2649 chunk_dealloc(node->chunk, node->size);
2650
2651 base_chunk_node_dealloc(node);
2652}
2653
2654static void *
2655imalloc(size_t size)
2656{
2657 void *ret;
2658
2659 assert(size != 0);
2660
2661 if (size <= arena_maxclass)
2662 ret = arena_malloc(choose_arena(), size);
2663 else
2664 ret = huge_malloc(size);
2665
2666 return (ret);
2667}
2668
2669static void *
2670ipalloc(size_t alignment, size_t size)
2671{
2672 void *ret;
2673 size_t alloc_size;
2674
2675 /*
2676 * Take advantage of the fact that for each size class, every object is
2677 * aligned at the smallest power of two that is non-zero in the base
2678 * two representation of the size. For example:
2679 *
2680 * Size | Base 2 | Minimum alignment
2681 * -----+----------+------------------
2682 * 96 | 1100000 | 32
2683 * 144 | 10100000 | 32
2684 * 192 | 11000000 | 64
2685 *
2686 * Depending on runtime settings, it is possible that arena_malloc()
2687 * will further round up to a power of two, but that never causes
2688 * correctness issues.
2689 */
2690 alloc_size = (size + (alignment - 1)) & (-alignment);
2691 if (alloc_size < size) {
2692 /* size_t overflow. */
2693 return (NULL);
2694 }
2695
2696 if (alloc_size <= arena_maxclass)
2697 ret = arena_malloc(choose_arena(), alloc_size);
2698 else {
2699 if (alignment <= chunk_size)
2700 ret = huge_malloc(size);
2701 else {
2702 size_t chunksize, offset;
2703 chunk_node_t *node;
2704
2705 /*
2706 * This allocation requires alignment that is even
2707 * larger than chunk alignment. This means that
2708 * huge_malloc() isn't good enough.
2709 *
2710 * Allocate almost twice as many chunks as are demanded
2711 * by the size or alignment, in order to assure the
2712 * alignment can be achieved, then unmap leading and
2713 * trailing chunks.
2714 */
2715
2716 chunksize = CHUNK_CEILING(size);
2717
2718 if (size >= alignment)
2719 alloc_size = chunksize + alignment - chunk_size;
2720 else
2721 alloc_size = (alignment << 1) - chunk_size;
2722
2723 /*
2724 * Allocate a chunk node with which to track the chunk.
2725 */
2726 node = base_chunk_node_alloc();
2727 if (node == NULL)
2728 return (NULL);
2729
2730 ret = chunk_alloc(alloc_size);
2731 if (ret == NULL) {
2732 base_chunk_node_dealloc(node);
2733 return (NULL);
2734 }
2735
2736 offset = (uintptr_t)ret & (alignment - 1);
2737 assert(offset % chunk_size == 0);
2738 assert(offset < alloc_size);
2739 if (offset == 0) {
2740 /* Trim trailing space. */
2741 chunk_dealloc((void *)((uintptr_t)ret
2742 + chunksize), alloc_size - chunksize);
2743 } else {
2744 size_t trailsize;
2745
2746 /* Trim leading space. */
2747 chunk_dealloc(ret, alignment - offset);
2748
2749 ret = (void *)((uintptr_t)ret + (alignment
2750 - offset));
2751
2752 trailsize = alloc_size - (alignment - offset)
2753 - chunksize;
2754 if (trailsize != 0) {
2755 /* Trim trailing space. */
2756 assert(trailsize < alloc_size);
2757 chunk_dealloc((void *)((uintptr_t)ret
2758 + chunksize), trailsize);
2759 }
2760 }
2761
2762 /* Insert node into huge. */
2763 node->chunk = ret;
2764 node->size = chunksize;
2765
2766 malloc_mutex_lock(&chunks_mtx);
2767 RB_INSERT(chunk_tree_s, &huge, node);
2768#ifdef MALLOC_STATS
2769 huge_allocated += size;
2770#endif
2771 malloc_mutex_unlock(&chunks_mtx);
2772
2773 if (opt_junk)
2774 memset(ret, 0xa5, chunksize);
2775 else if (opt_zero)
2776 memset(ret, 0, chunksize);
2777 }
2778 }
2779
2780 assert(((uintptr_t)ret & (alignment - 1)) == 0);
2781 return (ret);
2782}
2783
2784static void *
2785icalloc(size_t size)
2786{
2787 void *ret;
2788
2789 if (size <= arena_maxclass) {
2790 ret = arena_malloc(choose_arena(), size);
2791 if (ret == NULL)
2792 return (NULL);
2793 memset(ret, 0, size);
2794 } else {
2795 /*
2796 * The virtual memory system provides zero-filled pages, so
2797 * there is no need to do so manually, unless opt_junk is
2798 * enabled, in which case huge_malloc() fills huge allocations
2799 * with junk.
2800 */
2801 ret = huge_malloc(size);
2802 if (ret == NULL)
2803 return (NULL);
2804
2805 if (opt_junk)
2806 memset(ret, 0, size);
2807#ifdef USE_BRK
2808 else if ((uintptr_t)ret >= (uintptr_t)brk_base
2809 && (uintptr_t)ret < (uintptr_t)brk_max) {
2810 /*
2811 * This may be a re-used brk chunk. Therefore, zero
2812 * the memory.
2813 */
2814 memset(ret, 0, size);
2815 }
2816#endif
2817 }
2818
2819 return (ret);
2820}
2821
2822static size_t
2823isalloc(const void *ptr)
2824{
2825 size_t ret;
2826 arena_chunk_t *chunk;
2827
2828 assert(ptr != NULL);
2829
2830 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
2831 if (chunk != ptr) {
2832 /* Region. */
2833 assert(chunk->arena->magic == ARENA_MAGIC);
2834
2835 ret = arena_salloc(ptr);
2836 } else {
2837 chunk_node_t *node, key;
2838
2839 /* Chunk (huge allocation). */
2840
2841 malloc_mutex_lock(&chunks_mtx);
2842
2843 /* Extract from tree of huge allocations. */
2844 key.chunk = (void *)ptr;
2845 node = RB_FIND(chunk_tree_s, &huge, &key);
2846 assert(node != NULL);
2847
2848 ret = node->size;
2849
2850 malloc_mutex_unlock(&chunks_mtx);
2851 }
2852
2853 return (ret);
2854}
2855
2856static void *
2857iralloc(void *ptr, size_t size)
2858{
2859 void *ret;
2860 size_t oldsize;
2861
2862 assert(ptr != NULL);
2863 assert(size != 0);
2864
2865 oldsize = isalloc(ptr);
2866
2867 if (size <= arena_maxclass)
2868 ret = arena_ralloc(ptr, size, oldsize);
2869 else
2870 ret = huge_ralloc(ptr, size, oldsize);
2871
2872 return (ret);
2873}
2874
2875static void
2876idalloc(void *ptr)
2877{
2878 arena_chunk_t *chunk;
2879
2880 assert(ptr != NULL);
2881
2882 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
2883 if (chunk != ptr) {
2884 /* Region. */
2885#ifdef MALLOC_STATS
2886 malloc_mutex_lock(&chunk->arena->mtx);
2887 chunk->arena->stats.ndalloc++;
2888 malloc_mutex_unlock(&chunk->arena->mtx);
2889#endif
2890 arena_dalloc(chunk->arena, chunk, ptr);
2891 } else
2892 huge_dalloc(ptr);
2893}
2894
2895static void
2896malloc_print_stats(void)
2897{
2898
2899 if (opt_print_stats) {
2900 malloc_printf("___ Begin malloc statistics ___\n");
2901 malloc_printf("Number of CPUs: %u\n", ncpus);
2902 malloc_printf("Number of arenas: %u\n", narenas);
2903 malloc_printf("Chunk size: %zu (2^%zu)\n", chunk_size,
2904 opt_chunk_2pow);
2905 malloc_printf("Quantum size: %zu (2^%zu)\n", quantum,
2906 opt_quantum_2pow);
2907 malloc_printf("Max small size: %zu\n", small_max);
2908 malloc_printf("Pointer size: %u\n", sizeof(void *));
2909 malloc_printf("Assertions %s\n",
2910#ifdef NDEBUG
2911 "disabled"
2912#else
2913 "enabled"
2914#endif
2915 );
2916
2917#ifdef MALLOC_STATS
2918
2919 {
2920 size_t allocated, total;
2921 unsigned i;
2922 arena_t *arena;
2923
2924 /* Calculate and print allocated/total stats. */
2925
2926 /* arenas. */
2927 for (i = 0, allocated = 0; i < narenas; i++) {
2928 if (arenas[i] != NULL) {
2929 malloc_mutex_lock(&arenas[i]->mtx);
2930 allocated += arenas[i]->stats.allocated;
2931 malloc_mutex_unlock(&arenas[i]->mtx);
2932 }
2933 }
2934
2935 /* huge. */
2936 malloc_mutex_lock(&chunks_mtx);
2937 allocated += huge_allocated;
2938 total = stats_chunks.curchunks * chunk_size;
2939 malloc_mutex_unlock(&chunks_mtx);
2940
2941 malloc_printf("Allocated: %zu, space used: %zu\n",
2942 allocated, total);
2943
2944 /* Print chunk stats. */
2945 {
2946 chunk_stats_t chunks_stats;
2947
2948 malloc_mutex_lock(&chunks_mtx);
2949 chunks_stats = stats_chunks;
2950 malloc_mutex_unlock(&chunks_mtx);
2951
2952 malloc_printf("\nchunks:\n");
2953 malloc_printf(" %13s%13s%13s\n", "nchunks",
2954 "highchunks", "curchunks");
2955 malloc_printf(" %13llu%13lu%13lu\n",
2956 chunks_stats.nchunks,
2957 chunks_stats.highchunks,
2958 chunks_stats.curchunks);
2959 }
2960
2961 /* Print chunk stats. */
2962 malloc_printf("\nhuge:\n");
2963 malloc_printf("%12s %12s %12s\n",
2964 "nmalloc", "ndalloc", "allocated");
2965 malloc_printf("%12llu %12llu %12zu\n",
2966 huge_nmalloc, huge_ndalloc, huge_allocated);
2967
2968 /* Print stats for each arena. */
2969 for (i = 0; i < narenas; i++) {
2970 arena = arenas[i];
2971 if (arena != NULL) {
2972 malloc_printf(
2973 "\narenas[%u] statistics:\n", i);
2974 malloc_mutex_lock(&arena->mtx);
2975 stats_print(arena);
2976 malloc_mutex_unlock(&arena->mtx);
2977 }
2978 }
2979 }
2980#endif /* #ifdef MALLOC_STATS */
2981 malloc_printf("--- End malloc statistics ---\n");
2982 }
2983}
2984
2985/*
2986 * FreeBSD's pthreads implementation calls malloc(3), so the malloc
2987 * implementation has to take pains to avoid infinite recursion during
2988 * initialization.
2989 */
2990static inline bool
2991malloc_init(void)
2992{
2993
2994 if (malloc_initialized == false)
2995 return (malloc_init_hard());
2996
2997 return (false);
2998}
2999
3000static bool
3001malloc_init_hard(void)
3002{
3003 unsigned i, j;
3004 int linklen;
3005 char buf[PATH_MAX + 1];
3006 const char *opts;
3007
3008 malloc_mutex_lock(&init_lock);
3009 if (malloc_initialized) {
3010 /*
3011 * Another thread initialized the allocator before this one
3012 * acquired init_lock.
3013 */
3014 malloc_mutex_unlock(&init_lock);
3015 return (false);
3016 }
3017
3018 /* Get number of CPUs. */
3019 {
3020 int mib[2];
3021 size_t len;
3022
3023 mib[0] = CTL_HW;
3024 mib[1] = HW_NCPU;
3025 len = sizeof(ncpus);
3026 if (sysctl(mib, 2, &ncpus, &len, (void *) 0, 0) == -1) {
3027 /* Error. */
3028 ncpus = 1;
3029 }
3030 }
3031
3032 /* Get page size. */
3033 {
3034 long result;
3035
3036 result = sysconf(_SC_PAGESIZE);
3037 assert(result != -1);
3038 pagesize = (unsigned) result;
3039
3040 /*
3041 * We assume that pagesize is a power of 2 when calculating
3042 * pagesize_2pow.
3043 */
3044 assert(((result - 1) & result) == 0);
3045 pagesize_2pow = ffs(result) - 1;
3046 }
3047
3048 for (i = 0; i < 3; i++) {
3049 /* Get runtime configuration. */
3050 switch (i) {
3051 case 0:
3052 if ((linklen = readlink("/etc/malloc.conf", buf,
3053 sizeof(buf) - 1)) != -1) {
3054 /*
3055 * Use the contents of the "/etc/malloc.conf"
3056 * symbolic link's name.
3057 */
3058 buf[linklen] = '\0';
3059 opts = buf;
3060 } else {
3061 /* No configuration specified. */
3062 buf[0] = '\0';
3063 opts = buf;
3064 }
3065 break;
3066 case 1:
3067 if (issetugid() == 0 && (opts =
3068 getenv("MALLOC_OPTIONS")) != NULL) {
3069 /*
3070 * Do nothing; opts is already initialized to
3071 * the value of the MALLOC_OPTIONS environment
3072 * variable.
3073 */
3074 } else {
3075 /* No configuration specified. */
3076 buf[0] = '\0';
3077 opts = buf;
3078 }
3079 break;
3080 case 2:
3081 if (_malloc_options != NULL) {
3082 /*
3083 * Use options that were compiled into the program.
3084 */
3085 opts = _malloc_options;
3086 } else {
3087 /* No configuration specified. */
3088 buf[0] = '\0';
3089 opts = buf;
3090 }
3091 break;
3092 default:
3093 /* NOTREACHED */
3094 assert(false);
3095 }
3096
3097 for (j = 0; opts[j] != '\0'; j++) {
3098 switch (opts[j]) {
3099 case 'a':
3100 opt_abort = false;
3101 break;
3102 case 'A':
3103 opt_abort = true;
3104 break;
3105 case 'h':
3106 opt_hint = false;
3107 break;
3108 case 'H':
3109 opt_hint = true;
3110 break;
3111 case 'j':
3112 opt_junk = false;
3113 break;
3114 case 'J':
3115 opt_junk = true;
3116 break;
3117 case 'k':
3118 /*
3119 * Run fullness quartile limits don't have
3120 * enough resolution if there are too few
3121 * regions for the largest bin size classes.
3122 */
3123 if (opt_chunk_2pow > pagesize_2pow + 4)
3124 opt_chunk_2pow--;
3125 break;
3126 case 'K':
3127 if (opt_chunk_2pow < CHUNK_2POW_MAX)
3128 opt_chunk_2pow++;
3129 break;
3130 case 'n':
3131 opt_narenas_lshift--;
3132 break;
3133 case 'N':
3134 opt_narenas_lshift++;
3135 break;
3136 case 'p':
3137 opt_print_stats = false;
3138 break;
3139 case 'P':
3140 opt_print_stats = true;
3141 break;
3142 case 'q':
3143 if (opt_quantum_2pow > QUANTUM_2POW_MIN)
3144 opt_quantum_2pow--;
3145 break;
3146 case 'Q':
3147 if (opt_quantum_2pow < pagesize_2pow - 1)
3148 opt_quantum_2pow++;
3149 break;
3150 case 's':
3151 if (opt_small_max_2pow > QUANTUM_2POW_MIN)
3152 opt_small_max_2pow--;
3153 break;
3154 case 'S':
3155 if (opt_small_max_2pow < pagesize_2pow - 1)
3156 opt_small_max_2pow++;
3157 break;
3158 case 'u':
3159 opt_utrace = false;
3160 break;
3161 case 'U':
3162 opt_utrace = true;
3163 break;
3164 case 'v':
3165 opt_sysv = false;
3166 break;
3167 case 'V':
3168 opt_sysv = true;
3169 break;
3170 case 'x':
3171 opt_xmalloc = false;
3172 break;
3173 case 'X':
3174 opt_xmalloc = true;
3175 break;
3176 case 'z':
3177 opt_zero = false;
3178 break;
3179 case 'Z':
3180 opt_zero = true;
3181 break;
3182 default:
3183 malloc_printf("%s: (malloc) Unsupported"
3184 " character in malloc options: '%c'\n",
3185 _getprogname(), opts[j]);
3186 }
3187 }
3188 }
3189
3190 /* Take care to call atexit() only once. */
3191 if (opt_print_stats) {
3192 /* Print statistics at exit. */
3193 atexit(malloc_print_stats);
3194 }
3195
3196 /* Set variables according to the value of opt_small_max_2pow. */
3197 if (opt_small_max_2pow < opt_quantum_2pow)
3198 opt_small_max_2pow = opt_quantum_2pow;
3199 small_max = (1 << opt_small_max_2pow);
3200
3201 /* Set bin-related variables. */
3202 bin_maxclass = (pagesize >> 1);
3203 if (pagesize_2pow > RUN_MIN_REGS_2POW + 1)
3204 tiny_min_2pow = pagesize_2pow - (RUN_MIN_REGS_2POW + 1);
3205 else
3206 tiny_min_2pow = 1;
3207 assert(opt_quantum_2pow >= tiny_min_2pow);
3208 ntbins = opt_quantum_2pow - tiny_min_2pow;
3209 assert(ntbins <= opt_quantum_2pow);
3210 nqbins = (small_max >> opt_quantum_2pow);
3211 nsbins = pagesize_2pow - opt_small_max_2pow - 1;
3212
3213 /* Set variables according to the value of opt_quantum_2pow. */
3214 quantum = (1 << opt_quantum_2pow);
3215 quantum_mask = quantum - 1;
3216 if (ntbins > 0)
3217 small_min = (quantum >> 1) + 1;
3218 else
3219 small_min = 1;
3220 assert(small_min <= quantum);
3221
3222 /* Set variables according to the value of opt_chunk_2pow. */
3223 chunk_size = (1 << opt_chunk_2pow);
3224 chunk_size_mask = chunk_size - 1;
3225 arena_chunk_maplen = (1 << (opt_chunk_2pow - pagesize_2pow));
3226 arena_maxclass = (chunk_size >> 1);
3227
3228 UTRACE(0, 0, 0);
3229
3230#ifdef MALLOC_STATS
3231 memset(&stats_chunks, 0, sizeof(chunk_stats_t));
3232#endif
3233
3234 /* Various sanity checks that regard configuration. */
3235 assert(quantum >= sizeof(void *));
3236 assert(quantum <= pagesize);
3237 assert(chunk_size >= pagesize);
3238 assert(quantum * 4 <= chunk_size);
3239
3240 /* Initialize chunks data. */
3241 malloc_mutex_init(&chunks_mtx);
3242 RB_INIT(&huge);
3243#ifdef USE_BRK
3244 brk_base = sbrk(0);
3245 brk_prev = brk_base;
3246 brk_max = brk_base;
3247#endif
3248#ifdef MALLOC_STATS
3249 huge_nmalloc = 0;
3250 huge_ndalloc = 0;
3251 huge_allocated = 0;
3252#endif
3253 RB_INIT(&old_chunks);
3254
3255 /* Initialize base allocation data structures. */
3256#ifdef MALLOC_STATS
3257 base_total = 0;
3258#endif
3259#ifdef USE_BRK
3260 /*
3261 * Do special brk allocation here, since the base chunk doesn't really
3262 * need to be chunk-aligned.
3263 */
3264 {
3265 void *brk_cur;
3266 intptr_t incr;
3267
3268 do {
3269 /* Get the current end of brk. */
3270 brk_cur = sbrk(0);
3271
3272 /*
3273 * Calculate how much padding is necessary to
3274 * chunk-align the end of brk. Don't worry about
3275 * brk_cur not being chunk-aligned though.
3276 */
3277 incr = (intptr_t)chunk_size
3278 - (intptr_t)CHUNK_ADDR2OFFSET(brk_cur);
3279
3280 brk_prev = sbrk(incr);
3281 if (brk_prev == brk_cur) {
3282 /* Success. */
3283 break;
3284 }
3285 } while (brk_prev != (void *)-1);
3286
3287 base_chunk = brk_cur;
3288 base_next_addr = base_chunk;
3289 base_past_addr = (void *)((uintptr_t)base_chunk + incr);
3290#ifdef MALLOC_STATS
3291 base_total += incr;
3292 stats_chunks.nchunks = 1;
3293 stats_chunks.curchunks = 1;
3294 stats_chunks.highchunks = 1;
3295#endif
3296 }
3297#else
3298 /*
3299 * The first base chunk will be allocated when needed by base_alloc().
3300 */
3301 base_chunk = NULL;
3302 base_next_addr = NULL;
3303 base_past_addr = NULL;
3304#endif
3305 base_chunk_nodes = NULL;
3306 malloc_mutex_init(&base_mtx);
3307
3308 if (ncpus > 1) {
3309 /*
3310 * For SMP systems, create four times as many arenas as there
3311 * are CPUs by default.
3312 */
3313 opt_narenas_lshift += 2;
3314 }
3315
3316 /* Determine how many arenas to use. */
3317 narenas = ncpus;
3318 if (opt_narenas_lshift > 0) {
3319 if ((narenas << opt_narenas_lshift) > narenas)
3320 narenas <<= opt_narenas_lshift;
3321 /*
3322 * Make sure not to exceed the limits of what base_malloc()
3323 * can handle.
3324 */
3325 if (narenas * sizeof(arena_t *) > chunk_size)
3326 narenas = chunk_size / sizeof(arena_t *);
3327 } else if (opt_narenas_lshift < 0) {
3328 if ((narenas << opt_narenas_lshift) < narenas)
3329 narenas <<= opt_narenas_lshift;
3330 /* Make sure there is at least one arena. */
3331 if (narenas == 0)
3332 narenas = 1;
3333 }
3334
3335#ifdef NO_TLS
3336 if (narenas > 1) {
3337 static const unsigned primes[] = {1, 3, 5, 7, 11, 13, 17, 19,
3338 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
3339 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149,
3340 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211,
3341 223, 227, 229, 233, 239, 241, 251, 257, 263};
3342 unsigned i, nprimes, parenas;
3343
3344 /*
3345 * Pick a prime number of hash arenas that is more than narenas
3346 * so that direct hashing of pthread_self() pointers tends to
3347 * spread allocations evenly among the arenas.
3348 */
3349 assert((narenas & 1) == 0); /* narenas must be even. */
3350 nprimes = (sizeof(primes) >> SIZEOF_INT_2POW);
3351 parenas = primes[nprimes - 1]; /* In case not enough primes. */
3352 for (i = 1; i < nprimes; i++) {
3353 if (primes[i] > narenas) {
3354 parenas = primes[i];
3355 break;
3356 }
3357 }
3358 narenas = parenas;
3359 }
3360#endif
3361
3362#ifndef NO_TLS
3363 next_arena = 0;
3364#endif
3365
3366 /* Allocate and initialize arenas. */
3367 arenas = (arena_t **)base_alloc(sizeof(arena_t *) * narenas);
3368 if (arenas == NULL) {
3369 malloc_mutex_unlock(&init_lock);
3370 return (true);
3371 }
3372 /*
3373 * Zero the array. In practice, this should always be pre-zeroed,
3374 * since it was just mmap()ed, but let's be sure.
3375 */
3376 memset(arenas, 0, sizeof(arena_t *) * narenas);
3377
3378 /*
3379 * Initialize one arena here. The rest are lazily created in
3380 * arena_choose_hard().
3381 */
3382 arenas_extend(0);
3383 if (arenas[0] == NULL) {
3384 malloc_mutex_unlock(&init_lock);
3385 return (true);
3386 }
3387
3388 malloc_mutex_init(&arenas_mtx);
3389
3390 malloc_initialized = true;
3391 malloc_mutex_unlock(&init_lock);
3392 return (false);
3393}
3394
3395/*
3396 * End general internal functions.
3397 */
3398/******************************************************************************/
3399/*
3400 * Begin malloc(3)-compatible functions.
3401 */
3402
3403void *
3404malloc(size_t size)
3405{
3406 void *ret;
3407
3408 if (malloc_init()) {
3409 ret = NULL;
3410 goto RETURN;
3411 }
3412
3413 if (size == 0) {
3414 if (opt_sysv == false)
3415 size = 1;
3416 else {
3417 ret = NULL;
3418 goto RETURN;
3419 }
3420 }
3421
3422 ret = imalloc(size);
3423
3424RETURN:
3425 if (ret == NULL) {
3426 if (opt_xmalloc) {
3427 malloc_printf("%s: (malloc) Error in malloc(%zu):"
3428 " out of memory\n", _getprogname(), size);
3429 abort();
3430 }
3431 errno = ENOMEM;
3432 }
3433
3434 UTRACE(0, size, ret);
3435 return (ret);
3436}
3437
3438int
3439posix_memalign(void **memptr, size_t alignment, size_t size)
3440{
3441 int ret;
3442 void *result;
3443
3444 if (malloc_init())
3445 result = NULL;
3446 else {
3447 /* Make sure that alignment is a large enough power of 2. */
3448 if (((alignment - 1) & alignment) != 0
3449 || alignment < sizeof(void *)) {
3450 if (opt_xmalloc) {
3451 malloc_printf("%s: (malloc) Error in"
3452 " posix_memalign(%zu, %zu):"
3453 " invalid alignment\n",
3454 _getprogname(), alignment, size);
3455 abort();
3456 }
3457 result = NULL;
3458 ret = EINVAL;
3459 goto RETURN;
3460 }
3461
3462 result = ipalloc(alignment, size);
3463 }
3464
3465 if (result == NULL) {
3466 if (opt_xmalloc) {
3467 malloc_printf("%s: (malloc) Error in"
3468 " posix_memalign(%zu, %zu): out of memory\n",
3469 _getprogname(), alignment, size);
3470 abort();
3471 }
3472 ret = ENOMEM;
3473 goto RETURN;
3474 }
3475
3476 *memptr = result;
3477 ret = 0;
3478
3479RETURN:
3480 UTRACE(0, size, result);
3481 return (ret);
3482}
3483
3484void *
3485calloc(size_t num, size_t size)
3486{
3487 void *ret;
3488 size_t num_size;
3489
3490 if (malloc_init()) {
3491 ret = NULL;
3492 goto RETURN;
3493 }
3494
3495 num_size = num * size;
3496 if (num_size == 0) {
3497 if (opt_sysv == false)
3498 num_size = 1;
3499 else {
3500 ret = NULL;
3501 goto RETURN;
3502 }
3503 /*
3504 * Try to avoid division here. We know that it isn't possible to
3505 * overflow during multiplication if neither operand uses any of the
3506 * most significant half of the bits in a size_t.
3507 */
3508 } else if (((num | size) & (SIZE_T_MAX << (sizeof(size_t) << 2)))
3509 && (num_size / size != num)) {
3510 /* size_t overflow. */
3511 ret = NULL;
3512 goto RETURN;
3513 }
3514
3515 ret = icalloc(num_size);
3516
3517RETURN:
3518 if (ret == NULL) {
3519 if (opt_xmalloc) {
3520 malloc_printf("%s: (malloc) Error in"
3521 " calloc(%zu, %zu): out of memory\n",
3522 _getprogname(), num, size);
3523 abort();
3524 }
3525 errno = ENOMEM;
3526 }
3527
3528 UTRACE(0, num_size, ret);
3529 return (ret);
3530}
3531
3532void *
3533realloc(void *ptr, size_t size)
3534{
3535 void *ret;
3536
3537 if (size == 0) {
3538 if (opt_sysv == false)
3539 size = 1;
3540 else {
3541 if (ptr != NULL)
3542 idalloc(ptr);
3543 ret = NULL;
3544 goto RETURN;
3545 }
3546 }
3547
3548 if (ptr != NULL) {
3549 assert(malloc_initialized);
3550
3551 ret = iralloc(ptr, size);
3552
3553 if (ret == NULL) {
3554 if (opt_xmalloc) {
3555 malloc_printf("%s: (malloc) Error in"
3556 " realloc(%p, %zu): out of memory\n",
3557 _getprogname(), ptr, size);
3558 abort();
3559 }
3560 errno = ENOMEM;
3561 }
3562 } else {
3563 if (malloc_init())
3564 ret = NULL;
3565 else
3566 ret = imalloc(size);
3567
3568 if (ret == NULL) {
3569 if (opt_xmalloc) {
3570 malloc_printf("%s: (malloc) Error in"
3571 " realloc(%p, %zu): out of memory\n",
3572 _getprogname(), ptr, size);
3573 abort();
3574 }
3575 errno = ENOMEM;
3576 }
3577 }
3578
3579RETURN:
3580 UTRACE(ptr, size, ret);
3581 return (ret);
3582}
3583
3584void
3585free(void *ptr)
3586{
3587
3588 UTRACE(ptr, 0, 0);
3589 if (ptr != NULL) {
3590 assert(malloc_initialized);
3591
3592 idalloc(ptr);
3593 }
3594}
3595
3596/*
3597 * End malloc(3)-compatible functions.
3598 */
3599/******************************************************************************/
3600/*
3601 * Begin non-standard functions.
3602 */
3603
3604size_t
3605malloc_usable_size(const void *ptr)
3606{
3607
3608 assert(ptr != NULL);
3609
3610 return (isalloc(ptr));
3611}
3612
3613/*
3614 * End non-standard functions.
3615 */
3616/******************************************************************************/
3617/*
3618 * Begin library-private functions, used by threading libraries for protection
3619 * of malloc during fork(). These functions are only called if the program is
3620 * running in threaded mode, so there is no need to check whether the program
3621 * is threaded here.
3622 */
3623
3624void
3625_malloc_prefork(void)
3626{
3627 unsigned i;
3628
3629 /* Acquire all mutexes in a safe order. */
3630
3631 malloc_mutex_lock(&arenas_mtx);
3632 for (i = 0; i < narenas; i++) {
3633 if (arenas[i] != NULL)
3634 malloc_mutex_lock(&arenas[i]->mtx);
3635 }
3636 malloc_mutex_unlock(&arenas_mtx);
3637
3638 malloc_mutex_lock(&base_mtx);
3639
3640 malloc_mutex_lock(&chunks_mtx);
3641}
3642
3643void
3644_malloc_postfork(void)
3645{
3646 unsigned i;
3647
3648 /* Release all mutexes, now that fork() has completed. */
3649
3650 malloc_mutex_unlock(&chunks_mtx);
3651
3652 malloc_mutex_unlock(&base_mtx);
3653
3654 malloc_mutex_lock(&arenas_mtx);
3655 for (i = 0; i < narenas; i++) {
3656 if (arenas[i] != NULL)
3657 malloc_mutex_unlock(&arenas[i]->mtx);
3658 }
3659 malloc_mutex_unlock(&arenas_mtx);
3660}
3661
3662/*
3663 * End library-private functions.
3664 */
3665/******************************************************************************/