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