source: lib/libjemalloc/malloc.c @ 93a495

Revision 93a495, 138.4 KB checked in by Tollef Fog Heen <tfheen@…>, 6 years ago (diff)

Import jemalloc

git-svn-id:  http://www.varnish-cache.org/svn/trunk/varnish-cache@3215 d4fa192b-c00b-0410-8231-f00ffab90ce4

  • Property mode set to 100644
Line 
1/*-
2 * Copyright (C) 2006-2008 Jason Evans <jasone@FreeBSD.org>.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 *    notice(s), this list of conditions and the following disclaimer as
10 *    the first lines of this file unmodified other than the possible
11 *    addition of one or more copyright notices.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 *    notice(s), this list of conditions and the following disclaimer in
14 *    the documentation and/or other materials provided with the
15 *    distribution.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE
21 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
24 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
25 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
26 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
27 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 *
29 *******************************************************************************
30 *
31 * This allocator implementation is designed to provide scalable performance
32 * for multi-threaded programs on multi-processor systems.  The following
33 * features are included for this purpose:
34 *
35 *   + Multiple arenas are used if there are multiple CPUs, which reduces lock
36 *     contention and cache sloshing.
37 *
38 *   + Thread-specific caching is used if there are multiple threads, which
39 *     reduces the amount of locking.
40 *
41 *   + Cache line sharing between arenas is avoided for internal data
42 *     structures.
43 *
44 *   + Memory is managed in chunks and runs (chunks can be split into runs),
45 *     rather than as individual pages.  This provides a constant-time
46 *     mechanism for associating allocations with particular arenas.
47 *
48 * Allocation requests are rounded up to the nearest size class, and no record
49 * of the original request size is maintained.  Allocations are broken into
50 * categories according to size class.  Assuming runtime defaults, 4 kB pages
51 * and a 16 byte quantum on a 32-bit system, the size classes in each category
52 * are as follows:
53 *
54 *   |=======================================|
55 *   | Category | Subcategory      |    Size |
56 *   |=======================================|
57 *   | Small    | Tiny             |       2 |
58 *   |          |                  |       4 |
59 *   |          |                  |       8 |
60 *   |          |------------------+---------|
61 *   |          | Quantum-spaced   |      16 |
62 *   |          |                  |      32 |
63 *   |          |                  |      48 |
64 *   |          |                  |     ... |
65 *   |          |                  |      96 |
66 *   |          |                  |     112 |
67 *   |          |                  |     128 |
68 *   |          |------------------+---------|
69 *   |          | Cacheline-spaced |     192 |
70 *   |          |                  |     256 |
71 *   |          |                  |     320 |
72 *   |          |                  |     384 |
73 *   |          |                  |     448 |
74 *   |          |                  |     512 |
75 *   |          |------------------+---------|
76 *   |          | Sub-page         |     760 |
77 *   |          |                  |    1024 |
78 *   |          |                  |    1280 |
79 *   |          |                  |     ... |
80 *   |          |                  |    3328 |
81 *   |          |                  |    3584 |
82 *   |          |                  |    3840 |
83 *   |=======================================|
84 *   | Large                       |    4 kB |
85 *   |                             |    8 kB |
86 *   |                             |   12 kB |
87 *   |                             |     ... |
88 *   |                             | 1012 kB |
89 *   |                             | 1016 kB |
90 *   |                             | 1020 kB |
91 *   |=======================================|
92 *   | Huge                        |    1 MB |
93 *   |                             |    2 MB |
94 *   |                             |    3 MB |
95 *   |                             |     ... |
96 *   |=======================================|
97 *
98 * A different mechanism is used for each category:
99 *
100 *   Small : Each size class is segregated into its own set of runs.  Each run
101 *           maintains a bitmap of which regions are free/allocated.
102 *
103 *   Large : Each allocation is backed by a dedicated run.  Metadata are stored
104 *           in the associated arena chunk header maps.
105 *
106 *   Huge : Each allocation is backed by a dedicated contiguous set of chunks.
107 *          Metadata are stored in a separate red-black tree.
108 *
109 *******************************************************************************
110 */
111
112/*
113 * MALLOC_PRODUCTION disables assertions and statistics gathering.  It also
114 * defaults the A and J runtime options to off.  These settings are appropriate
115 * for production systems.
116 */
117/* #define      MALLOC_PRODUCTION */
118
119#ifndef MALLOC_PRODUCTION
120   /*
121    * MALLOC_DEBUG enables assertions and other sanity checks, and disables
122    * inline functions.
123    */
124#  define MALLOC_DEBUG
125
126   /* MALLOC_STATS enables statistics calculation. */
127#  define MALLOC_STATS
128#endif
129
130/*
131 * MALLOC_TINY enables support for tiny objects, which are smaller than one
132 * quantum.
133 */
134#define MALLOC_TINY
135
136/*
137 * MALLOC_MAG enables a magazine-based thread-specific caching layer for small
138 * objects.  This makes it possible to allocate/deallocate objects without any
139 * locking when the cache is in the steady state.
140 */
141#define MALLOC_MAG
142
143/*
144 * MALLOC_BALANCE enables monitoring of arena lock contention and dynamically
145 * re-balances arena load if exponentially averaged contention exceeds a
146 * certain threshold.
147 */
148#define MALLOC_BALANCE
149
150/*
151 * MALLOC_DSS enables use of sbrk(2) to allocate chunks from the data storage
152 * segment (DSS).  In an ideal world, this functionality would be completely
153 * unnecessary, but we are burdened by history and the lack of resource limits
154 * for anonymous mapped memory.
155 */
156#define MALLOC_DSS
157
158#include <sys/cdefs.h>
159__FBSDID("$FreeBSD: head/lib/libc/stdlib/malloc.c 182225 2008-08-27 02:00:53Z jasone $");
160
161#include "libc_private.h"
162#ifdef MALLOC_DEBUG
163#  define _LOCK_DEBUG
164#endif
165#include "spinlock.h"
166#include "namespace.h"
167#include <sys/mman.h>
168#include <sys/param.h>
169#include <sys/stddef.h>
170#include <sys/time.h>
171#include <sys/types.h>
172#include <sys/sysctl.h>
173#include <sys/uio.h>
174#include <sys/ktrace.h> /* Must come after several other sys/ includes. */
175
176#include <machine/cpufunc.h>
177#include <machine/vmparam.h>
178
179#include <errno.h>
180#include <limits.h>
181#include <pthread.h>
182#include <sched.h>
183#include <stdarg.h>
184#include <stdbool.h>
185#include <stdio.h>
186#include <stdint.h>
187#include <stdlib.h>
188#include <string.h>
189#include <strings.h>
190#include <unistd.h>
191
192#include "un-namespace.h"
193
194#ifdef MALLOC_DEBUG
195#  ifdef NDEBUG
196#    undef NDEBUG
197#  endif
198#else
199#  ifndef NDEBUG
200#    define NDEBUG
201#  endif
202#endif
203#include <assert.h>
204
205#include "rb.h"
206
207#ifdef MALLOC_DEBUG
208   /* Disable inlining to make debugging easier. */
209#  define inline
210#endif
211
212/* Size of stack-allocated buffer passed to strerror_r(). */
213#define STRERROR_BUF            64
214
215/*
216 * The const_size2bin table is sized according to PAGESIZE_2POW, but for
217 * correctness reasons, we never assume that
218 * (pagesize == (1U << * PAGESIZE_2POW)).
219 *
220 * Minimum alignment of allocations is 2^QUANTUM_2POW bytes.
221 */
222#ifdef __i386__
223#  define PAGESIZE_2POW         12
224#  define QUANTUM_2POW          4
225#  define SIZEOF_PTR_2POW       2
226#  define CPU_SPINWAIT          __asm__ volatile("pause")
227#endif
228#ifdef __ia64__
229#  define PAGESIZE_2POW         12
230#  define QUANTUM_2POW          4
231#  define SIZEOF_PTR_2POW       3
232#endif
233#ifdef __alpha__
234#  define PAGESIZE_2POW         13
235#  define QUANTUM_2POW          4
236#  define SIZEOF_PTR_2POW       3
237#  define NO_TLS
238#endif
239#ifdef __sparc64__
240#  define PAGESIZE_2POW         13
241#  define QUANTUM_2POW          4
242#  define SIZEOF_PTR_2POW       3
243#  define NO_TLS
244#endif
245#ifdef __amd64__
246#  define PAGESIZE_2POW         12
247#  define QUANTUM_2POW          4
248#  define SIZEOF_PTR_2POW       3
249#  define CPU_SPINWAIT          __asm__ volatile("pause")
250#endif
251#ifdef __arm__
252#  define PAGESIZE_2POW         12
253#  define QUANTUM_2POW          3
254#  define SIZEOF_PTR_2POW       2
255#  define NO_TLS
256#endif
257#ifdef __mips__
258#  define PAGESIZE_2POW         12
259#  define QUANTUM_2POW          3
260#  define SIZEOF_PTR_2POW       2
261#  define NO_TLS
262#endif
263#ifdef __powerpc__
264#  define PAGESIZE_2POW         12
265#  define QUANTUM_2POW          4
266#  define SIZEOF_PTR_2POW       2
267#endif
268
269#define QUANTUM                 ((size_t)(1U << QUANTUM_2POW))
270#define QUANTUM_MASK            (QUANTUM - 1)
271
272#define SIZEOF_PTR              (1U << SIZEOF_PTR_2POW)
273
274/* sizeof(int) == (1U << SIZEOF_INT_2POW). */
275#ifndef SIZEOF_INT_2POW
276#  define SIZEOF_INT_2POW       2
277#endif
278
279/* We can't use TLS in non-PIC programs, since TLS relies on loader magic. */
280#if (!defined(PIC) && !defined(NO_TLS))
281#  define NO_TLS
282#endif
283
284#ifdef NO_TLS
285   /* MALLOC_MAG requires TLS. */
286#  ifdef MALLOC_MAG
287#    undef MALLOC_MAG
288#  endif
289   /* MALLOC_BALANCE requires TLS. */
290#  ifdef MALLOC_BALANCE
291#    undef MALLOC_BALANCE
292#  endif
293#endif
294
295/*
296 * Size and alignment of memory chunks that are allocated by the OS's virtual
297 * memory system.
298 */
299#define CHUNK_2POW_DEFAULT      20
300
301/* Maximum number of dirty pages per arena. */
302#define DIRTY_MAX_DEFAULT       (1U << 9)
303
304/*
305 * Maximum size of L1 cache line.  This is used to avoid cache line aliasing.
306 * In addition, this controls the spacing of cacheline-spaced size classes.
307 */
308#define CACHELINE_2POW          6
309#define CACHELINE               ((size_t)(1U << CACHELINE_2POW))
310#define CACHELINE_MASK          (CACHELINE - 1)
311
312/*
313 * Subpages are an artificially designated partitioning of pages.  Their only
314 * purpose is to support subpage-spaced size classes.
315 *
316 * There must be at least 4 subpages per page, due to the way size classes are
317 * handled.
318 */
319#define SUBPAGE_2POW            8
320#define SUBPAGE                 ((size_t)(1U << SUBPAGE_2POW))
321#define SUBPAGE_MASK            (SUBPAGE - 1)
322
323#ifdef MALLOC_TINY
324   /* Smallest size class to support. */
325#  define TINY_MIN_2POW         1
326#endif
327
328/*
329 * Maximum size class that is a multiple of the quantum, but not (necessarily)
330 * a power of 2.  Above this size, allocations are rounded up to the nearest
331 * power of 2.
332 */
333#define QSPACE_MAX_2POW_DEFAULT 7
334
335/*
336 * Maximum size class that is a multiple of the cacheline, but not (necessarily)
337 * a power of 2.  Above this size, allocations are rounded up to the nearest
338 * power of 2.
339 */
340#define CSPACE_MAX_2POW_DEFAULT 9
341
342/*
343 * RUN_MAX_OVRHD indicates maximum desired run header overhead.  Runs are sized
344 * as small as possible such that this setting is still honored, without
345 * violating other constraints.  The goal is to make runs as small as possible
346 * without exceeding a per run external fragmentation threshold.
347 *
348 * We use binary fixed point math for overhead computations, where the binary
349 * point is implicitly RUN_BFP bits to the left.
350 *
351 * Note that it is possible to set RUN_MAX_OVRHD low enough that it cannot be
352 * honored for some/all object sizes, since there is one bit of header overhead
353 * per object (plus a constant).  This constraint is relaxed (ignored) for runs
354 * that are so small that the per-region overhead is greater than:
355 *
356 *   (RUN_MAX_OVRHD / (reg_size << (3+RUN_BFP))
357 */
358#define RUN_BFP                 12
359/*                                    \/   Implicit binary fixed point. */
360#define RUN_MAX_OVRHD           0x0000003dU
361#define RUN_MAX_OVRHD_RELAX     0x00001800U
362
363/* Put a cap on small object run size.  This overrides RUN_MAX_OVRHD. */
364#define RUN_MAX_SMALL   (12 * pagesize)
365
366/*
367 * Hyper-threaded CPUs may need a special instruction inside spin loops in
368 * order to yield to another virtual CPU.  If no such instruction is defined
369 * above, make CPU_SPINWAIT a no-op.
370 */
371#ifndef CPU_SPINWAIT
372#  define CPU_SPINWAIT
373#endif
374
375/*
376 * Adaptive spinning must eventually switch to blocking, in order to avoid the
377 * potential for priority inversion deadlock.  Backing off past a certain point
378 * can actually waste time.
379 */
380#define SPIN_LIMIT_2POW         11
381
382/*
383 * Conversion from spinning to blocking is expensive; we use (1U <<
384 * BLOCK_COST_2POW) to estimate how many more times costly blocking is than
385 * worst-case spinning.
386 */
387#define BLOCK_COST_2POW         4
388
389#ifdef MALLOC_MAG
390   /*
391    * Default magazine size, in bytes.  max_rounds is calculated to make
392    * optimal use of the space, leaving just enough room for the magazine
393    * header.
394    */
395#  define MAG_SIZE_2POW_DEFAULT 9
396#endif
397
398#ifdef MALLOC_BALANCE
399   /*
400    * We use an exponential moving average to track recent lock contention,
401    * where the size of the history window is N, and alpha=2/(N+1).
402    *
403    * Due to integer math rounding, very small values here can cause
404    * substantial degradation in accuracy, thus making the moving average decay
405    * faster than it would with precise calculation.
406    */
407#  define BALANCE_ALPHA_INV_2POW        9
408
409   /*
410    * Threshold value for the exponential moving contention average at which to
411    * re-assign a thread.
412    */
413#  define BALANCE_THRESHOLD_DEFAULT     (1U << (SPIN_LIMIT_2POW-4))
414#endif
415
416/******************************************************************************/
417
418/*
419 * Mutexes based on spinlocks.  We can't use normal pthread spinlocks in all
420 * places, because they require malloc()ed memory, which causes bootstrapping
421 * issues in some cases.
422 */
423typedef struct {
424        spinlock_t      lock;
425} malloc_mutex_t;
426
427/* Set to true once the allocator has been initialized. */
428static bool malloc_initialized = false;
429
430/* Used to avoid initialization races. */
431static malloc_mutex_t init_lock = {_SPINLOCK_INITIALIZER};
432
433/******************************************************************************/
434/*
435 * Statistics data structures.
436 */
437
438#ifdef MALLOC_STATS
439
440typedef struct malloc_bin_stats_s malloc_bin_stats_t;
441struct malloc_bin_stats_s {
442        /*
443         * Number of allocation requests that corresponded to the size of this
444         * bin.
445         */
446        uint64_t        nrequests;
447
448#ifdef MALLOC_MAG
449        /* Number of magazine reloads from this bin. */
450        uint64_t        nmags;
451#endif
452
453        /* Total number of runs created for this bin's size class. */
454        uint64_t        nruns;
455
456        /*
457         * Total number of runs reused by extracting them from the runs tree for
458         * this bin's size class.
459         */
460        uint64_t        reruns;
461
462        /* High-water mark for this bin. */
463        unsigned long   highruns;
464
465        /* Current number of runs in this bin. */
466        unsigned long   curruns;
467};
468
469typedef struct arena_stats_s arena_stats_t;
470struct arena_stats_s {
471        /* Number of bytes currently mapped. */
472        size_t          mapped;
473
474        /*
475         * Total number of purge sweeps, total number of madvise calls made,
476         * and total pages purged in order to keep dirty unused memory under
477         * control.
478         */
479        uint64_t        npurge;
480        uint64_t        nmadvise;
481        uint64_t        purged;
482
483        /* Per-size-category statistics. */
484        size_t          allocated_small;
485        uint64_t        nmalloc_small;
486        uint64_t        ndalloc_small;
487
488        size_t          allocated_large;
489        uint64_t        nmalloc_large;
490        uint64_t        ndalloc_large;
491
492#ifdef MALLOC_BALANCE
493        /* Number of times this arena reassigned a thread due to contention. */
494        uint64_t        nbalance;
495#endif
496};
497
498typedef struct chunk_stats_s chunk_stats_t;
499struct chunk_stats_s {
500        /* Number of chunks that were allocated. */
501        uint64_t        nchunks;
502
503        /* High-water mark for number of chunks allocated. */
504        unsigned long   highchunks;
505
506        /*
507         * Current number of chunks allocated.  This value isn't maintained for
508         * any other purpose, so keep track of it in order to be able to set
509         * highchunks.
510         */
511        unsigned long   curchunks;
512};
513
514#endif /* #ifdef MALLOC_STATS */
515
516/******************************************************************************/
517/*
518 * Extent data structures.
519 */
520
521/* Tree of extents. */
522typedef struct extent_node_s extent_node_t;
523struct extent_node_s {
524#ifdef MALLOC_DSS
525        /* Linkage for the size/address-ordered tree. */
526        rb_node(extent_node_t) link_szad;
527#endif
528
529        /* Linkage for the address-ordered tree. */
530        rb_node(extent_node_t) link_ad;
531
532        /* Pointer to the extent that this tree node is responsible for. */
533        void    *addr;
534
535        /* Total region size. */
536        size_t  size;
537};
538typedef rb_tree(extent_node_t) extent_tree_t;
539
540/******************************************************************************/
541/*
542 * Arena data structures.
543 */
544
545typedef struct arena_s arena_t;
546typedef struct arena_bin_s arena_bin_t;
547
548/* Each element of the chunk map corresponds to one page within the chunk. */
549typedef struct arena_chunk_map_s arena_chunk_map_t;
550struct arena_chunk_map_s {
551        /*
552         * Linkage for run trees.  There are two disjoint uses:
553         *
554         * 1) arena_t's runs_avail tree.
555         * 2) arena_run_t conceptually uses this linkage for in-use non-full
556         *    runs, rather than directly embedding linkage.
557         */
558        rb_node(arena_chunk_map_t)      link;
559
560        /*
561         * Run address (or size) and various flags are stored together.  The bit
562         * layout looks like (assuming 32-bit system):
563         *
564         *   ???????? ???????? ????---- ---kdzla
565         *
566         * ? : Unallocated: Run address for first/last pages, unset for internal
567         *                  pages.
568         *     Small: Run address.
569         *     Large: Run size for first page, unset for trailing pages.
570         * - : Unused.
571         * k : key?
572         * d : dirty?
573         * z : zeroed?
574         * l : large?
575         * a : allocated?
576         *
577         * Following are example bit patterns for the three types of runs.
578         *
579         * r : run address
580         * s : run size
581         * x : don't care
582         * - : 0
583         * [dzla] : bit set
584         *
585         *   Unallocated:
586         *     ssssssss ssssssss ssss---- --------
587         *     xxxxxxxx xxxxxxxx xxxx---- ----d---
588         *     ssssssss ssssssss ssss---- -----z--
589         *
590         *   Small:
591         *     rrrrrrrr rrrrrrrr rrrr---- -------a
592         *     rrrrrrrr rrrrrrrr rrrr---- -------a
593         *     rrrrrrrr rrrrrrrr rrrr---- -------a
594         *
595         *   Large:
596         *     ssssssss ssssssss ssss---- ------la
597         *     -------- -------- -------- ------la
598         *     -------- -------- -------- ------la
599         */
600        size_t                          bits;
601#define CHUNK_MAP_KEY           ((size_t)0x10U)
602#define CHUNK_MAP_DIRTY         ((size_t)0x08U)
603#define CHUNK_MAP_ZEROED        ((size_t)0x04U)
604#define CHUNK_MAP_LARGE         ((size_t)0x02U)
605#define CHUNK_MAP_ALLOCATED     ((size_t)0x01U)
606};
607typedef rb_tree(arena_chunk_map_t) arena_avail_tree_t;
608typedef rb_tree(arena_chunk_map_t) arena_run_tree_t;
609
610/* Arena chunk header. */
611typedef struct arena_chunk_s arena_chunk_t;
612struct arena_chunk_s {
613        /* Arena that owns the chunk. */
614        arena_t         *arena;
615
616        /* Linkage for the arena's chunks_dirty tree. */
617        rb_node(arena_chunk_t) link_dirty;
618
619        /* Number of dirty pages. */
620        size_t          ndirty;
621
622        /* Map of pages within chunk that keeps track of free/large/small. */
623        arena_chunk_map_t map[1]; /* Dynamically sized. */
624};
625typedef rb_tree(arena_chunk_t) arena_chunk_tree_t;
626
627typedef struct arena_run_s arena_run_t;
628struct arena_run_s {
629#ifdef MALLOC_DEBUG
630        uint32_t        magic;
631#  define ARENA_RUN_MAGIC 0x384adf93
632#endif
633
634        /* Bin this run is associated with. */
635        arena_bin_t     *bin;
636
637        /* Index of first element that might have a free region. */
638        unsigned        regs_minelm;
639
640        /* Number of free regions in run. */
641        unsigned        nfree;
642
643        /* Bitmask of in-use regions (0: in use, 1: free). */
644        unsigned        regs_mask[1]; /* Dynamically sized. */
645};
646
647struct arena_bin_s {
648        /*
649         * Current run being used to service allocations of this bin's size
650         * class.
651         */
652        arena_run_t     *runcur;
653
654        /*
655         * Tree of non-full runs.  This tree is used when looking for an
656         * existing run when runcur is no longer usable.  We choose the
657         * non-full run that is lowest in memory; this policy tends to keep
658         * objects packed well, and it can also help reduce the number of
659         * almost-empty chunks.
660         */
661        arena_run_tree_t runs;
662
663        /* Size of regions in a run for this bin's size class. */
664        size_t          reg_size;
665
666        /* Total size of a run for this bin's size class. */
667        size_t          run_size;
668
669        /* Total number of regions in a run for this bin's size class. */
670        uint32_t        nregs;
671
672        /* Number of elements in a run's regs_mask for this bin's size class. */
673        uint32_t        regs_mask_nelms;
674
675        /* Offset of first region in a run for this bin's size class. */
676        uint32_t        reg0_offset;
677
678#ifdef MALLOC_STATS
679        /* Bin statistics. */
680        malloc_bin_stats_t stats;
681#endif
682};
683
684struct arena_s {
685#ifdef MALLOC_DEBUG
686        uint32_t                magic;
687#  define ARENA_MAGIC 0x947d3d24
688#endif
689
690        /* All operations on this arena require that lock be locked. */
691        pthread_mutex_t         lock;
692
693#ifdef MALLOC_STATS
694        arena_stats_t           stats;
695#endif
696
697        /* Tree of dirty-page-containing chunks this arena manages. */
698        arena_chunk_tree_t      chunks_dirty;
699
700        /*
701         * In order to avoid rapid chunk allocation/deallocation when an arena
702         * oscillates right on the cusp of needing a new chunk, cache the most
703         * recently freed chunk.  The spare is left in the arena's chunk trees
704         * until it is deleted.
705         *
706         * There is one spare chunk per arena, rather than one spare total, in
707         * order to avoid interactions between multiple threads that could make
708         * a single spare inadequate.
709         */
710        arena_chunk_t           *spare;
711
712        /*
713         * Current count of pages within unused runs that are potentially
714         * dirty, and for which madvise(... MADV_FREE) has not been called.  By
715         * tracking this, we can institute a limit on how much dirty unused
716         * memory is mapped for each arena.
717         */
718        size_t                  ndirty;
719
720        /*
721         * Size/address-ordered tree of this arena's available runs.  This tree
722         * is used for first-best-fit run allocation.
723         */
724        arena_avail_tree_t      runs_avail;
725
726#ifdef MALLOC_BALANCE
727        /*
728         * The arena load balancing machinery needs to keep track of how much
729         * lock contention there is.  This value is exponentially averaged.
730         */
731        uint32_t                contention;
732#endif
733
734        /*
735         * bins is used to store rings of free regions of the following sizes,
736         * assuming a 16-byte quantum, 4kB pagesize, and default MALLOC_OPTIONS.
737         *
738         *   bins[i] | size |
739         *   --------+------+
740         *        0  |    2 |
741         *        1  |    4 |
742         *        2  |    8 |
743         *   --------+------+
744         *        3  |   16 |
745         *        4  |   32 |
746         *        5  |   48 |
747         *        6  |   64 |
748         *           :      :
749         *           :      :
750         *       33  |  496 |
751         *       34  |  512 |
752         *   --------+------+
753         *       35  | 1024 |
754         *       36  | 2048 |
755         *   --------+------+
756         */
757        arena_bin_t             bins[1]; /* Dynamically sized. */
758};
759
760/******************************************************************************/
761/*
762 * Magazine data structures.
763 */
764
765#ifdef MALLOC_MAG
766typedef struct mag_s mag_t;
767struct mag_s {
768        size_t          binind; /* Index of associated bin. */
769        size_t          nrounds;
770        void            *rounds[1]; /* Dynamically sized. */
771};
772
773/*
774 * Magazines are lazily allocated, but once created, they remain until the
775 * associated mag_rack is destroyed.
776 */
777typedef struct bin_mags_s bin_mags_t;
778struct bin_mags_s {
779        mag_t   *curmag;
780        mag_t   *sparemag;
781};
782
783typedef struct mag_rack_s mag_rack_t;
784struct mag_rack_s {
785        bin_mags_t      bin_mags[1]; /* Dynamically sized. */
786};
787#endif
788
789/******************************************************************************/
790/*
791 * Data.
792 */
793
794/* Number of CPUs. */
795static unsigned         ncpus;
796
797/* VM page size. */
798static size_t           pagesize;
799static size_t           pagesize_mask;
800static size_t           pagesize_2pow;
801
802/* Various bin-related settings. */
803#ifdef MALLOC_TINY              /* Number of (2^n)-spaced tiny bins. */
804#  define               ntbins  ((unsigned)(QUANTUM_2POW - TINY_MIN_2POW))
805#else
806#  define               ntbins  0
807#endif
808static unsigned         nqbins; /* Number of quantum-spaced bins. */
809static unsigned         ncbins; /* Number of cacheline-spaced bins. */
810static unsigned         nsbins; /* Number of subpage-spaced bins. */
811static unsigned         nbins;
812#ifdef MALLOC_TINY
813#  define               tspace_max      ((size_t)(QUANTUM >> 1))
814#endif
815#define                 qspace_min      QUANTUM
816static size_t           qspace_max;
817static size_t           cspace_min;
818static size_t           cspace_max;
819static size_t           sspace_min;
820static size_t           sspace_max;
821#define                 bin_maxclass    sspace_max
822
823static uint8_t const    *size2bin;
824/*
825 * const_size2bin is a static constant lookup table that in the common case can
826 * be used as-is for size2bin.  For dynamically linked programs, this avoids
827 * a page of memory overhead per process.
828 */
829#define S2B_1(i)        i,
830#define S2B_2(i)        S2B_1(i) S2B_1(i)
831#define S2B_4(i)        S2B_2(i) S2B_2(i)
832#define S2B_8(i)        S2B_4(i) S2B_4(i)
833#define S2B_16(i)       S2B_8(i) S2B_8(i)
834#define S2B_32(i)       S2B_16(i) S2B_16(i)
835#define S2B_64(i)       S2B_32(i) S2B_32(i)
836#define S2B_128(i)      S2B_64(i) S2B_64(i)
837#define S2B_256(i)      S2B_128(i) S2B_128(i)
838static const uint8_t    const_size2bin[(1U << PAGESIZE_2POW) - 255] = {
839        S2B_1(0xffU)            /*    0 */
840#if (QUANTUM_2POW == 4)
841/* 64-bit system ************************/
842#  ifdef MALLOC_TINY
843        S2B_2(0)                /*    2 */
844        S2B_2(1)                /*    4 */
845        S2B_4(2)                /*    8 */
846        S2B_8(3)                /*   16 */
847#    define S2B_QMIN 3
848#  else
849        S2B_16(0)               /*   16 */
850#    define S2B_QMIN 0
851#  endif
852        S2B_16(S2B_QMIN + 1)    /*   32 */
853        S2B_16(S2B_QMIN + 2)    /*   48 */
854        S2B_16(S2B_QMIN + 3)    /*   64 */
855        S2B_16(S2B_QMIN + 4)    /*   80 */
856        S2B_16(S2B_QMIN + 5)    /*   96 */
857        S2B_16(S2B_QMIN + 6)    /*  112 */
858        S2B_16(S2B_QMIN + 7)    /*  128 */
859#  define S2B_CMIN (S2B_QMIN + 8)
860#else
861/* 32-bit system ************************/
862#  ifdef MALLOC_TINY
863        S2B_2(0)                /*    2 */
864        S2B_2(1)                /*    4 */
865        S2B_4(2)                /*    8 */
866#    define S2B_QMIN 2
867#  else
868        S2B_8(0)                /*    8 */
869#    define S2B_QMIN 0
870#  endif
871        S2B_8(S2B_QMIN + 1)     /*   16 */
872        S2B_8(S2B_QMIN + 2)     /*   24 */
873        S2B_8(S2B_QMIN + 3)     /*   32 */
874        S2B_8(S2B_QMIN + 4)     /*   40 */
875        S2B_8(S2B_QMIN + 5)     /*   48 */
876        S2B_8(S2B_QMIN + 6)     /*   56 */
877        S2B_8(S2B_QMIN + 7)     /*   64 */
878        S2B_8(S2B_QMIN + 8)     /*   72 */
879        S2B_8(S2B_QMIN + 9)     /*   80 */
880        S2B_8(S2B_QMIN + 10)    /*   88 */
881        S2B_8(S2B_QMIN + 11)    /*   96 */
882        S2B_8(S2B_QMIN + 12)    /*  104 */
883        S2B_8(S2B_QMIN + 13)    /*  112 */
884        S2B_8(S2B_QMIN + 14)    /*  120 */
885        S2B_8(S2B_QMIN + 15)    /*  128 */
886#  define S2B_CMIN (S2B_QMIN + 16)
887#endif
888/****************************************/
889        S2B_64(S2B_CMIN + 0)    /*  192 */
890        S2B_64(S2B_CMIN + 1)    /*  256 */
891        S2B_64(S2B_CMIN + 2)    /*  320 */
892        S2B_64(S2B_CMIN + 3)    /*  384 */
893        S2B_64(S2B_CMIN + 4)    /*  448 */
894        S2B_64(S2B_CMIN + 5)    /*  512 */
895#  define S2B_SMIN (S2B_CMIN + 6)
896        S2B_256(S2B_SMIN + 0)   /*  768 */
897        S2B_256(S2B_SMIN + 1)   /* 1024 */
898        S2B_256(S2B_SMIN + 2)   /* 1280 */
899        S2B_256(S2B_SMIN + 3)   /* 1536 */
900        S2B_256(S2B_SMIN + 4)   /* 1792 */
901        S2B_256(S2B_SMIN + 5)   /* 2048 */
902        S2B_256(S2B_SMIN + 6)   /* 2304 */
903        S2B_256(S2B_SMIN + 7)   /* 2560 */
904        S2B_256(S2B_SMIN + 8)   /* 2816 */
905        S2B_256(S2B_SMIN + 9)   /* 3072 */
906        S2B_256(S2B_SMIN + 10)  /* 3328 */
907        S2B_256(S2B_SMIN + 11)  /* 3584 */
908        S2B_256(S2B_SMIN + 12)  /* 3840 */
909#if (PAGESIZE_2POW == 13)
910        S2B_256(S2B_SMIN + 13)  /* 4096 */
911        S2B_256(S2B_SMIN + 14)  /* 4352 */
912        S2B_256(S2B_SMIN + 15)  /* 4608 */
913        S2B_256(S2B_SMIN + 16)  /* 4864 */
914        S2B_256(S2B_SMIN + 17)  /* 5120 */
915        S2B_256(S2B_SMIN + 18)  /* 5376 */
916        S2B_256(S2B_SMIN + 19)  /* 5632 */
917        S2B_256(S2B_SMIN + 20)  /* 5888 */
918        S2B_256(S2B_SMIN + 21)  /* 6144 */
919        S2B_256(S2B_SMIN + 22)  /* 6400 */
920        S2B_256(S2B_SMIN + 23)  /* 6656 */
921        S2B_256(S2B_SMIN + 24)  /* 6912 */
922        S2B_256(S2B_SMIN + 25)  /* 7168 */
923        S2B_256(S2B_SMIN + 26)  /* 7424 */
924        S2B_256(S2B_SMIN + 27)  /* 7680 */
925        S2B_256(S2B_SMIN + 28)  /* 7936 */
926#endif
927};
928#undef S2B_1
929#undef S2B_2
930#undef S2B_4
931#undef S2B_8
932#undef S2B_16
933#undef S2B_32
934#undef S2B_64
935#undef S2B_128
936#undef S2B_256
937#undef S2B_QMIN
938#undef S2B_CMIN
939#undef S2B_SMIN
940
941#ifdef MALLOC_MAG
942static size_t           max_rounds;
943#endif
944
945/* Various chunk-related settings. */
946static size_t           chunksize;
947static size_t           chunksize_mask; /* (chunksize - 1). */
948static size_t           chunk_npages;
949static size_t           arena_chunk_header_npages;
950static size_t           arena_maxclass; /* Max size class for arenas. */
951
952/********/
953/*
954 * Chunks.
955 */
956
957/* Protects chunk-related data structures. */
958static malloc_mutex_t   huge_mtx;
959
960/* Tree of chunks that are stand-alone huge allocations. */
961static extent_tree_t    huge;
962
963#ifdef MALLOC_DSS
964/*
965 * Protects sbrk() calls.  This avoids malloc races among threads, though it
966 * does not protect against races with threads that call sbrk() directly.
967 */
968static malloc_mutex_t   dss_mtx;
969/* Base address of the DSS. */
970static void             *dss_base;
971/* Current end of the DSS, or ((void *)-1) if the DSS is exhausted. */
972static void             *dss_prev;
973/* Current upper limit on DSS addresses. */
974static void             *dss_max;
975
976/*
977 * Trees of chunks that were previously allocated (trees differ only in node
978 * ordering).  These are used when allocating chunks, in an attempt to re-use
979 * address space.  Depending on function, different tree orderings are needed,
980 * which is why there are two trees with the same contents.
981 */
982static extent_tree_t    dss_chunks_szad;
983static extent_tree_t    dss_chunks_ad;
984#endif
985
986#ifdef MALLOC_STATS
987/* Huge allocation statistics. */
988static uint64_t         huge_nmalloc;
989static uint64_t         huge_ndalloc;
990static size_t           huge_allocated;
991#endif
992
993/****************************/
994/*
995 * base (internal allocation).
996 */
997
998/*
999 * Current pages that are being used for internal memory allocations.  These
1000 * pages are carved up in cacheline-size quanta, so that there is no chance of
1001 * false cache line sharing.
1002 */
1003static void             *base_pages;
1004static void             *base_next_addr;
1005static void             *base_past_addr; /* Addr immediately past base_pages. */
1006static extent_node_t    *base_nodes;
1007static malloc_mutex_t   base_mtx;
1008#ifdef MALLOC_STATS
1009static size_t           base_mapped;
1010#endif
1011
1012/********/
1013/*
1014 * Arenas.
1015 */
1016
1017/*
1018 * Arenas that are used to service external requests.  Not all elements of the
1019 * arenas array are necessarily used; arenas are created lazily as needed.
1020 */
1021static arena_t          **arenas;
1022static unsigned         narenas;
1023#ifndef NO_TLS
1024#  ifdef MALLOC_BALANCE
1025static unsigned         narenas_2pow;
1026#  else
1027static unsigned         next_arena;
1028#  endif
1029#endif
1030static pthread_mutex_t  arenas_lock; /* Protects arenas initialization. */
1031
1032#ifndef NO_TLS
1033/*
1034 * Map of pthread_self() --> arenas[???], used for selecting an arena to use
1035 * for allocations.
1036 */
1037static __thread arena_t *arenas_map;
1038#endif
1039
1040#ifdef MALLOC_MAG
1041/*
1042 * Map of thread-specific magazine racks, used for thread-specific object
1043 * caching.
1044 */
1045static __thread mag_rack_t      *mag_rack;
1046#endif
1047
1048#ifdef MALLOC_STATS
1049/* Chunk statistics. */
1050static chunk_stats_t    stats_chunks;
1051#endif
1052
1053/*******************************/
1054/*
1055 * Runtime configuration options.
1056 */
1057const char      *_malloc_options;
1058
1059#ifndef MALLOC_PRODUCTION
1060static bool     opt_abort = true;
1061static bool     opt_junk = true;
1062#else
1063static bool     opt_abort = false;
1064static bool     opt_junk = false;
1065#endif
1066#ifdef MALLOC_DSS
1067static bool     opt_dss = true;
1068static bool     opt_mmap = true;
1069#endif
1070#ifdef MALLOC_MAG
1071static bool     opt_mag = true;
1072static size_t   opt_mag_size_2pow = MAG_SIZE_2POW_DEFAULT;
1073#endif
1074static size_t   opt_dirty_max = DIRTY_MAX_DEFAULT;
1075#ifdef MALLOC_BALANCE
1076static uint64_t opt_balance_threshold = BALANCE_THRESHOLD_DEFAULT;
1077#endif
1078static bool     opt_print_stats = false;
1079static size_t   opt_qspace_max_2pow = QSPACE_MAX_2POW_DEFAULT;
1080static size_t   opt_cspace_max_2pow = CSPACE_MAX_2POW_DEFAULT;
1081static size_t   opt_chunk_2pow = CHUNK_2POW_DEFAULT;
1082static bool     opt_utrace = false;
1083static bool     opt_sysv = false;
1084static bool     opt_xmalloc = false;
1085static bool     opt_zero = false;
1086static int      opt_narenas_lshift = 0;
1087
1088typedef struct {
1089        void    *p;
1090        size_t  s;
1091        void    *r;
1092} malloc_utrace_t;
1093
1094#define UTRACE(a, b, c)                                                 \
1095        if (opt_utrace) {                                               \
1096                malloc_utrace_t ut;                                     \
1097                ut.p = (a);                                             \
1098                ut.s = (b);                                             \
1099                ut.r = (c);                                             \
1100                utrace(&ut, sizeof(ut));                                \
1101        }
1102
1103/******************************************************************************/
1104/*
1105 * Begin function prototypes for non-inline static functions.
1106 */
1107
1108static void     malloc_mutex_init(malloc_mutex_t *mutex);
1109static bool     malloc_spin_init(pthread_mutex_t *lock);
1110static void     wrtmessage(const char *p1, const char *p2, const char *p3,
1111                const char *p4);
1112#ifdef MALLOC_STATS
1113static void     malloc_printf(const char *format, ...);
1114#endif
1115static char     *umax2s(uintmax_t x, char *s);
1116#ifdef MALLOC_DSS
1117static bool     base_pages_alloc_dss(size_t minsize);
1118#endif
1119static bool     base_pages_alloc_mmap(size_t minsize);
1120static bool     base_pages_alloc(size_t minsize);
1121static void     *base_alloc(size_t size);
1122static void     *base_calloc(size_t number, size_t size);
1123static extent_node_t *base_node_alloc(void);
1124static void     base_node_dealloc(extent_node_t *node);
1125#ifdef MALLOC_STATS
1126static void     stats_print(arena_t *arena);
1127#endif
1128static void     *pages_map(void *addr, size_t size);
1129static void     pages_unmap(void *addr, size_t size);
1130#ifdef MALLOC_DSS
1131static void     *chunk_alloc_dss(size_t size);
1132static void     *chunk_recycle_dss(size_t size, bool zero);
1133#endif
1134static void     *chunk_alloc_mmap(size_t size);
1135static void     *chunk_alloc(size_t size, bool zero);
1136#ifdef MALLOC_DSS
1137static extent_node_t *chunk_dealloc_dss_record(void *chunk, size_t size);
1138static bool     chunk_dealloc_dss(void *chunk, size_t size);
1139#endif
1140static void     chunk_dealloc_mmap(void *chunk, size_t size);
1141static void     chunk_dealloc(void *chunk, size_t size);
1142#ifndef NO_TLS
1143static arena_t  *choose_arena_hard(void);
1144#endif
1145static void     arena_run_split(arena_t *arena, arena_run_t *run, size_t size,
1146    bool large, bool zero);
1147static arena_chunk_t *arena_chunk_alloc(arena_t *arena);
1148static void     arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk);
1149static arena_run_t *arena_run_alloc(arena_t *arena, size_t size, bool large,
1150    bool zero);
1151static void     arena_purge(arena_t *arena);
1152static void     arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty);
1153static void     arena_run_trim_head(arena_t *arena, arena_chunk_t *chunk,
1154    arena_run_t *run, size_t oldsize, size_t newsize);
1155static void     arena_run_trim_tail(arena_t *arena, arena_chunk_t *chunk,
1156    arena_run_t *run, size_t oldsize, size_t newsize, bool dirty);
1157static arena_run_t *arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin);
1158static void     *arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin);
1159static size_t   arena_bin_run_size_calc(arena_bin_t *bin, size_t min_run_size);
1160#ifdef MALLOC_BALANCE
1161static void     arena_lock_balance_hard(arena_t *arena);
1162#endif
1163#ifdef MALLOC_MAG
1164static void     mag_load(mag_t *mag);
1165#endif
1166static void     *arena_malloc_large(arena_t *arena, size_t size, bool zero);
1167static void     *arena_palloc(arena_t *arena, size_t alignment, size_t size,
1168    size_t alloc_size);
1169static size_t   arena_salloc(const void *ptr);
1170#ifdef MALLOC_MAG
1171static void     mag_unload(mag_t *mag);
1172#endif
1173static void     arena_dalloc_large(arena_t *arena, arena_chunk_t *chunk,
1174    void *ptr);
1175static void     arena_ralloc_large_shrink(arena_t *arena, arena_chunk_t *chunk,
1176    void *ptr, size_t size, size_t oldsize);
1177static bool     arena_ralloc_large_grow(arena_t *arena, arena_chunk_t *chunk,
1178    void *ptr, size_t size, size_t oldsize);
1179static bool     arena_ralloc_large(void *ptr, size_t size, size_t oldsize);
1180static void     *arena_ralloc(void *ptr, size_t size, size_t oldsize);
1181static bool     arena_new(arena_t *arena);
1182static arena_t  *arenas_extend(unsigned ind);
1183#ifdef MALLOC_MAG
1184static mag_t    *mag_create(arena_t *arena, size_t binind);
1185static void     mag_destroy(mag_t *mag);
1186static mag_rack_t *mag_rack_create(arena_t *arena);
1187static void     mag_rack_destroy(mag_rack_t *rack);
1188#endif
1189static void     *huge_malloc(size_t size, bool zero);
1190static void     *huge_palloc(size_t alignment, size_t size);
1191static void     *huge_ralloc(void *ptr, size_t size, size_t oldsize);
1192static void     huge_dalloc(void *ptr);
1193static void     malloc_print_stats(void);
1194#ifdef MALLOC_DEBUG
1195static void     size2bin_validate(void);
1196#endif
1197static bool     size2bin_init(void);
1198static bool     size2bin_init_hard(void);
1199static bool     malloc_init_hard(void);
1200
1201/*
1202 * End function prototypes.
1203 */
1204/******************************************************************************/
1205/*
1206 * Begin mutex.  We can't use normal pthread mutexes in all places, because
1207 * they require malloc()ed memory, which causes bootstrapping issues in some
1208 * cases.
1209 */
1210
1211static void
1212malloc_mutex_init(malloc_mutex_t *mutex)
1213{
1214        static const spinlock_t lock = _SPINLOCK_INITIALIZER;
1215
1216        mutex->lock = lock;
1217}
1218
1219static inline void
1220malloc_mutex_lock(malloc_mutex_t *mutex)
1221{
1222
1223        if (__isthreaded)
1224                _SPINLOCK(&mutex->lock);
1225}
1226
1227static inline void
1228malloc_mutex_unlock(malloc_mutex_t *mutex)
1229{
1230
1231        if (__isthreaded)
1232                _SPINUNLOCK(&mutex->lock);
1233}
1234
1235/*
1236 * End mutex.
1237 */
1238/******************************************************************************/
1239/*
1240 * Begin spin lock.  Spin locks here are actually adaptive mutexes that block
1241 * after a period of spinning, because unbounded spinning would allow for
1242 * priority inversion.
1243 */
1244
1245/*
1246 * We use an unpublished interface to initialize pthread mutexes with an
1247 * allocation callback, in order to avoid infinite recursion.
1248 */
1249int     _pthread_mutex_init_calloc_cb(pthread_mutex_t *mutex,
1250    void *(calloc_cb)(size_t, size_t));
1251
1252__weak_reference(_pthread_mutex_init_calloc_cb_stub,
1253    _pthread_mutex_init_calloc_cb);
1254
1255int
1256_pthread_mutex_init_calloc_cb_stub(pthread_mutex_t *mutex,
1257    void *(calloc_cb)(size_t, size_t))
1258{
1259
1260        return (0);
1261}
1262
1263static bool
1264malloc_spin_init(pthread_mutex_t *lock)
1265{
1266
1267        if (_pthread_mutex_init_calloc_cb(lock, base_calloc) != 0)
1268                return (true);
1269
1270        return (false);
1271}
1272
1273static inline unsigned
1274malloc_spin_lock(pthread_mutex_t *lock)
1275{
1276        unsigned ret = 0;
1277
1278        if (__isthreaded) {
1279                if (_pthread_mutex_trylock(lock) != 0) {
1280                        unsigned i;
1281                        volatile unsigned j;
1282
1283                        /* Exponentially back off. */
1284                        for (i = 1; i <= SPIN_LIMIT_2POW; i++) {
1285                                for (j = 0; j < (1U << i); j++) {
1286                                        ret++;
1287                                        CPU_SPINWAIT;
1288                                }
1289
1290                                if (_pthread_mutex_trylock(lock) == 0)
1291                                        return (ret);
1292                        }
1293
1294                        /*
1295                         * Spinning failed.  Block until the lock becomes
1296                         * available, in order to avoid indefinite priority
1297                         * inversion.
1298                         */
1299                        _pthread_mutex_lock(lock);
1300                        assert((ret << BLOCK_COST_2POW) != 0);
1301                        return (ret << BLOCK_COST_2POW);
1302                }
1303        }
1304
1305        return (ret);
1306}
1307
1308static inline void
1309malloc_spin_unlock(pthread_mutex_t *lock)
1310{
1311
1312        if (__isthreaded)
1313                _pthread_mutex_unlock(lock);
1314}
1315
1316/*
1317 * End spin lock.
1318 */
1319/******************************************************************************/
1320/*
1321 * Begin Utility functions/macros.
1322 */
1323
1324/* Return the chunk address for allocation address a. */
1325#define CHUNK_ADDR2BASE(a)                                              \
1326        ((void *)((uintptr_t)(a) & ~chunksize_mask))
1327
1328/* Return the chunk offset of address a. */
1329#define CHUNK_ADDR2OFFSET(a)                                            \
1330        ((size_t)((uintptr_t)(a) & chunksize_mask))
1331
1332/* Return the smallest chunk multiple that is >= s. */
1333#define CHUNK_CEILING(s)                                                \
1334        (((s) + chunksize_mask) & ~chunksize_mask)
1335
1336/* Return the smallest quantum multiple that is >= a. */
1337#define QUANTUM_CEILING(a)                                              \
1338        (((a) + QUANTUM_MASK) & ~QUANTUM_MASK)
1339
1340/* Return the smallest cacheline multiple that is >= s. */
1341#define CACHELINE_CEILING(s)                                            \
1342        (((s) + CACHELINE_MASK) & ~CACHELINE_MASK)
1343
1344/* Return the smallest subpage multiple that is >= s. */
1345#define SUBPAGE_CEILING(s)                                              \
1346        (((s) + SUBPAGE_MASK) & ~SUBPAGE_MASK)
1347
1348/* Return the smallest pagesize multiple that is >= s. */
1349#define PAGE_CEILING(s)                                                 \
1350        (((s) + pagesize_mask) & ~pagesize_mask)
1351
1352#ifdef MALLOC_TINY
1353/* Compute the smallest power of 2 that is >= x. */
1354static inline size_t
1355pow2_ceil(size_t x)
1356{
1357
1358        x--;
1359        x |= x >> 1;
1360        x |= x >> 2;
1361        x |= x >> 4;
1362        x |= x >> 8;
1363        x |= x >> 16;
1364#if (SIZEOF_PTR == 8)
1365        x |= x >> 32;
1366#endif
1367        x++;
1368        return (x);
1369}
1370#endif
1371
1372#ifdef MALLOC_BALANCE
1373/*
1374 * Use a simple linear congruential pseudo-random number generator:
1375 *
1376 *   prn(y) = (a*x + c) % m
1377 *
1378 * where the following constants ensure maximal period:
1379 *
1380 *   a == Odd number (relatively prime to 2^n), and (a-1) is a multiple of 4.
1381 *   c == Odd number (relatively prime to 2^n).
1382 *   m == 2^32
1383 *
1384 * See Knuth's TAOCP 3rd Ed., Vol. 2, pg. 17 for details on these constraints.
1385 *
1386 * This choice of m has the disadvantage that the quality of the bits is
1387 * proportional to bit position.  For example. the lowest bit has a cycle of 2,
1388 * the next has a cycle of 4, etc.  For this reason, we prefer to use the upper
1389 * bits.
1390 */
1391#  define PRN_DEFINE(suffix, var, a, c)                                 \
1392static inline void                                                      \
1393sprn_##suffix(uint32_t seed)                                            \
1394{                                                                       \
1395        var = seed;                                                     \
1396}                                                                       \
1397                                                                        \
1398static inline uint32_t                                                  \
1399prn_##suffix(uint32_t lg_range)                                         \
1400{                                                                       \
1401        uint32_t ret, x;                                                \
1402                                                                        \
1403        assert(lg_range > 0);                                           \
1404        assert(lg_range <= 32);                                         \
1405                                                                        \
1406        x = (var * (a)) + (c);                                          \
1407        var = x;                                                        \
1408        ret = x >> (32 - lg_range);                                     \
1409                                                                        \
1410        return (ret);                                                   \
1411}
1412#  define SPRN(suffix, seed)    sprn_##suffix(seed)
1413#  define PRN(suffix, lg_range) prn_##suffix(lg_range)
1414#endif
1415
1416#ifdef MALLOC_BALANCE
1417/* Define the PRNG used for arena assignment. */
1418static __thread uint32_t balance_x;
1419PRN_DEFINE(balance, balance_x, 1297, 1301)
1420#endif
1421
1422static void
1423wrtmessage(const char *p1, const char *p2, const char *p3, const char *p4)
1424{
1425
1426        _write(STDERR_FILENO, p1, strlen(p1));
1427        _write(STDERR_FILENO, p2, strlen(p2));
1428        _write(STDERR_FILENO, p3, strlen(p3));
1429        _write(STDERR_FILENO, p4, strlen(p4));
1430}
1431
1432void    (*_malloc_message)(const char *p1, const char *p2, const char *p3,
1433            const char *p4) = wrtmessage;
1434
1435#ifdef MALLOC_STATS
1436/*
1437 * Print to stderr in such a way as to (hopefully) avoid memory allocation.
1438 */
1439static void
1440malloc_printf(const char *format, ...)
1441{
1442        char buf[4096];
1443        va_list ap;
1444
1445        va_start(ap, format);
1446        vsnprintf(buf, sizeof(buf), format, ap);
1447        va_end(ap);
1448        _malloc_message(buf, "", "", "");
1449}
1450#endif
1451
1452/*
1453 * We don't want to depend on vsnprintf() for production builds, since that can
1454 * cause unnecessary bloat for static binaries.  umax2s() provides minimal
1455 * integer printing functionality, so that malloc_printf() use can be limited to
1456 * MALLOC_STATS code.
1457 */
1458#define UMAX2S_BUFSIZE  21
1459static char *
1460umax2s(uintmax_t x, char *s)
1461{
1462        unsigned i;
1463
1464        /* Make sure UMAX2S_BUFSIZE is large enough. */
1465        assert(sizeof(uintmax_t) <= 8);
1466
1467        i = UMAX2S_BUFSIZE - 1;
1468        s[i] = '\0';
1469        do {
1470                i--;
1471                s[i] = "0123456789"[x % 10];
1472                x /= 10;
1473        } while (x > 0);
1474
1475        return (&s[i]);
1476}
1477
1478/******************************************************************************/
1479
1480#ifdef MALLOC_DSS
1481static bool
1482base_pages_alloc_dss(size_t minsize)
1483{
1484
1485        /*
1486         * Do special DSS allocation here, since base allocations don't need to
1487         * be chunk-aligned.
1488         */
1489        malloc_mutex_lock(&dss_mtx);
1490        if (dss_prev != (void *)-1) {
1491                intptr_t incr;
1492                size_t csize = CHUNK_CEILING(minsize);
1493
1494                do {
1495                        /* Get the current end of the DSS. */
1496                        dss_max = sbrk(0);
1497
1498                        /*
1499                         * Calculate how much padding is necessary to
1500                         * chunk-align the end of the DSS.  Don't worry about
1501                         * dss_max not being chunk-aligned though.
1502                         */
1503                        incr = (intptr_t)chunksize
1504                            - (intptr_t)CHUNK_ADDR2OFFSET(dss_max);
1505                        assert(incr >= 0);
1506                        if ((size_t)incr < minsize)
1507                                incr += csize;
1508
1509                        dss_prev = sbrk(incr);
1510                        if (dss_prev == dss_max) {
1511                                /* Success. */
1512                                dss_max = (void *)((intptr_t)dss_prev + incr);
1513                                base_pages = dss_prev;
1514                                base_next_addr = base_pages;
1515                                base_past_addr = dss_max;
1516#ifdef MALLOC_STATS
1517                                base_mapped += incr;
1518#endif
1519                                malloc_mutex_unlock(&dss_mtx);
1520                                return (false);
1521                        }
1522                } while (dss_prev != (void *)-1);
1523        }
1524        malloc_mutex_unlock(&dss_mtx);
1525
1526        return (true);
1527}
1528#endif
1529
1530static bool
1531base_pages_alloc_mmap(size_t minsize)
1532{
1533        size_t csize;
1534
1535        assert(minsize != 0);
1536        csize = PAGE_CEILING(minsize);
1537        base_pages = pages_map(NULL, csize);
1538        if (base_pages == NULL)
1539                return (true);
1540        base_next_addr = base_pages;
1541        base_past_addr = (void *)((uintptr_t)base_pages + csize);
1542#ifdef MALLOC_STATS
1543        base_mapped += csize;
1544#endif
1545
1546        return (false);
1547}
1548
1549static bool
1550base_pages_alloc(size_t minsize)
1551{
1552
1553#ifdef MALLOC_DSS
1554        if (opt_dss) {
1555                if (base_pages_alloc_dss(minsize) == false)
1556                        return (false);
1557        }
1558
1559        if (opt_mmap && minsize != 0)
1560#endif
1561        {
1562                if (base_pages_alloc_mmap(minsize) == false)
1563                        return (false);
1564        }
1565
1566        return (true);
1567}
1568
1569static void *
1570base_alloc(size_t size)
1571{
1572        void *ret;
1573        size_t csize;
1574
1575        /* Round size up to nearest multiple of the cacheline size. */
1576        csize = CACHELINE_CEILING(size);
1577
1578        malloc_mutex_lock(&base_mtx);
1579        /* Make sure there's enough space for the allocation. */
1580        if ((uintptr_t)base_next_addr + csize > (uintptr_t)base_past_addr) {
1581                if (base_pages_alloc(csize)) {
1582                        malloc_mutex_unlock(&base_mtx);
1583                        return (NULL);
1584                }
1585        }
1586        /* Allocate. */
1587        ret = base_next_addr;
1588        base_next_addr = (void *)((uintptr_t)base_next_addr + csize);
1589        malloc_mutex_unlock(&base_mtx);
1590
1591        return (ret);
1592}
1593
1594static void *
1595base_calloc(size_t number, size_t size)
1596{
1597        void *ret;
1598
1599        ret = base_alloc(number * size);
1600        memset(ret, 0, number * size);
1601
1602        return (ret);
1603}
1604
1605static extent_node_t *
1606base_node_alloc(void)
1607{
1608        extent_node_t *ret;
1609
1610        malloc_mutex_lock(&base_mtx);
1611        if (base_nodes != NULL) {
1612                ret = base_nodes;
1613                base_nodes = *(extent_node_t **)ret;
1614                malloc_mutex_unlock(&base_mtx);
1615        } else {
1616                malloc_mutex_unlock(&base_mtx);
1617                ret = (extent_node_t *)base_alloc(sizeof(extent_node_t));
1618        }
1619
1620        return (ret);
1621}
1622
1623static void
1624base_node_dealloc(extent_node_t *node)
1625{
1626
1627        malloc_mutex_lock(&base_mtx);
1628        *(extent_node_t **)node = base_nodes;
1629        base_nodes = node;
1630        malloc_mutex_unlock(&base_mtx);
1631}
1632
1633/******************************************************************************/
1634
1635#ifdef MALLOC_STATS
1636static void
1637stats_print(arena_t *arena)
1638{
1639        unsigned i, gap_start;
1640
1641        malloc_printf("dirty: %zu page%s dirty, %llu sweep%s,"
1642            " %llu madvise%s, %llu page%s purged\n",
1643            arena->ndirty, arena->ndirty == 1 ? "" : "s",
1644            arena->stats.npurge, arena->stats.npurge == 1 ? "" : "s",
1645            arena->stats.nmadvise, arena->stats.nmadvise == 1 ? "" : "s",
1646            arena->stats.purged, arena->stats.purged == 1 ? "" : "s");
1647
1648        malloc_printf("            allocated      nmalloc      ndalloc\n");
1649        malloc_printf("small:   %12zu %12llu %12llu\n",
1650            arena->stats.allocated_small, arena->stats.nmalloc_small,
1651            arena->stats.ndalloc_small);
1652        malloc_printf("large:   %12zu %12llu %12llu\n",
1653            arena->stats.allocated_large, arena->stats.nmalloc_large,
1654            arena->stats.ndalloc_large);
1655        malloc_printf("total:   %12zu %12llu %12llu\n",
1656            arena->stats.allocated_small + arena->stats.allocated_large,
1657            arena->stats.nmalloc_small + arena->stats.nmalloc_large,
1658            arena->stats.ndalloc_small + arena->stats.ndalloc_large);
1659        malloc_printf("mapped:  %12zu\n", arena->stats.mapped);
1660
1661#ifdef MALLOC_MAG
1662        if (__isthreaded && opt_mag) {
1663                malloc_printf("bins:     bin   size regs pgs      mags   "
1664                    "newruns    reruns maxruns curruns\n");
1665        } else {
1666#endif
1667                malloc_printf("bins:     bin   size regs pgs  requests   "
1668                    "newruns    reruns maxruns curruns\n");
1669#ifdef MALLOC_MAG
1670        }
1671#endif
1672        for (i = 0, gap_start = UINT_MAX; i < nbins; i++) {
1673                if (arena->bins[i].stats.nruns == 0) {
1674                        if (gap_start == UINT_MAX)
1675                                gap_start = i;
1676                } else {
1677                        if (gap_start != UINT_MAX) {
1678                                if (i > gap_start + 1) {
1679                                        /* Gap of more than one size class. */
1680                                        malloc_printf("[%u..%u]\n",
1681                                            gap_start, i - 1);
1682                                } else {
1683                                        /* Gap of one size class. */
1684                                        malloc_printf("[%u]\n", gap_start);
1685                                }
1686                                gap_start = UINT_MAX;
1687                        }
1688                        malloc_printf(
1689                            "%13u %1s %4u %4u %3u %9llu %9llu"
1690                            " %9llu %7lu %7lu\n",
1691                            i,
1692                            i < ntbins ? "T" : i < ntbins + nqbins ? "Q" :
1693                            i < ntbins + nqbins + ncbins ? "C" : "S",
1694                            arena->bins[i].reg_size,
1695                            arena->bins[i].nregs,
1696                            arena->bins[i].run_size >> pagesize_2pow,
1697#ifdef MALLOC_MAG
1698                            (__isthreaded && opt_mag) ?
1699                            arena->bins[i].stats.nmags :
1700#endif
1701                            arena->bins[i].stats.nrequests,
1702                            arena->bins[i].stats.nruns,
1703                            arena->bins[i].stats.reruns,
1704                            arena->bins[i].stats.highruns,
1705                            arena->bins[i].stats.curruns);
1706                }
1707        }
1708        if (gap_start != UINT_MAX) {
1709                if (i > gap_start + 1) {
1710                        /* Gap of more than one size class. */
1711                        malloc_printf("[%u..%u]\n", gap_start, i - 1);
1712                } else {
1713                        /* Gap of one size class. */
1714                        malloc_printf("[%u]\n", gap_start);
1715                }
1716        }
1717}
1718#endif
1719
1720/*
1721 * End Utility functions/macros.
1722 */
1723/******************************************************************************/
1724/*
1725 * Begin extent tree code.
1726 */
1727
1728#ifdef MALLOC_DSS
1729static inline int
1730extent_szad_comp(extent_node_t *a, extent_node_t *b)
1731{
1732        int ret;
1733        size_t a_size = a->size;
1734        size_t b_size = b->size;
1735
1736        ret = (a_size > b_size) - (a_size < b_size);
1737        if (ret == 0) {
1738                uintptr_t a_addr = (uintptr_t)a->addr;
1739                uintptr_t b_addr = (uintptr_t)b->addr;
1740
1741                ret = (a_addr > b_addr) - (a_addr < b_addr);
1742        }
1743
1744        return (ret);
1745}
1746
1747/* Wrap red-black tree macros in functions. */
1748rb_wrap(__unused static, extent_tree_szad_, extent_tree_t, extent_node_t,
1749    link_szad, extent_szad_comp)
1750#endif
1751
1752static inline int
1753extent_ad_comp(extent_node_t *a, extent_node_t *b)
1754{
1755        uintptr_t a_addr = (uintptr_t)a->addr;
1756        uintptr_t b_addr = (uintptr_t)b->addr;
1757
1758        return ((a_addr > b_addr) - (a_addr < b_addr));
1759}
1760
1761/* Wrap red-black tree macros in functions. */
1762rb_wrap(__unused static, extent_tree_ad_, extent_tree_t, extent_node_t, link_ad,
1763    extent_ad_comp)
1764
1765/*
1766 * End extent tree code.
1767 */
1768/******************************************************************************/
1769/*
1770 * Begin chunk management functions.
1771 */
1772
1773static void *
1774pages_map(void *addr, size_t size)
1775{
1776        void *ret;
1777
1778        /*
1779         * We don't use MAP_FIXED here, because it can cause the *replacement*
1780         * of existing mappings, and we only want to create new mappings.
1781         */
1782        ret = mmap(addr, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON,
1783            -1, 0);
1784        assert(ret != NULL);
1785
1786        if (ret == MAP_FAILED)
1787                ret = NULL;
1788        else if (addr != NULL && ret != addr) {
1789                /*
1790                 * We succeeded in mapping memory, but not in the right place.
1791                 */
1792                if (munmap(ret, size) == -1) {
1793                        char buf[STRERROR_BUF];
1794
1795                        strerror_r(errno, buf, sizeof(buf));
1796                        _malloc_message(_getprogname(),
1797                            ": (malloc) Error in munmap(): ", buf, "\n");
1798                        if (opt_abort)
1799                                abort();
1800                }
1801                ret = NULL;
1802        }
1803
1804        assert(ret == NULL || (addr == NULL && ret != addr)
1805            || (addr != NULL && ret == addr));
1806        return (ret);
1807}
1808
1809static void
1810pages_unmap(void *addr, size_t size)
1811{
1812
1813        if (munmap(addr, size) == -1) {
1814                char buf[STRERROR_BUF];
1815
1816                strerror_r(errno, buf, sizeof(buf));
1817                _malloc_message(_getprogname(),
1818                    ": (malloc) Error in munmap(): ", buf, "\n");
1819                if (opt_abort)
1820                        abort();
1821        }
1822}
1823
1824#ifdef MALLOC_DSS
1825static void *
1826chunk_alloc_dss(size_t size)
1827{
1828
1829        /*
1830         * sbrk() uses a signed increment argument, so take care not to
1831         * interpret a huge allocation request as a negative increment.
1832         */
1833        if ((intptr_t)size < 0)
1834                return (NULL);
1835
1836        malloc_mutex_lock(&dss_mtx);
1837        if (dss_prev != (void *)-1) {
1838                intptr_t incr;
1839
1840                /*
1841                 * The loop is necessary to recover from races with other
1842                 * threads that are using the DSS for something other than
1843                 * malloc.
1844                 */
1845                do {
1846                        void *ret;
1847
1848                        /* Get the current end of the DSS. */
1849                        dss_max = sbrk(0);
1850
1851                        /*
1852                         * Calculate how much padding is necessary to
1853                         * chunk-align the end of the DSS.
1854                         */
1855                        incr = (intptr_t)size
1856                            - (intptr_t)CHUNK_ADDR2OFFSET(dss_max);
1857                        if (incr == (intptr_t)size)
1858                                ret = dss_max;
1859                        else {
1860                                ret = (void *)((intptr_t)dss_max + incr);
1861                                incr += size;
1862                        }
1863
1864                        dss_prev = sbrk(incr);
1865                        if (dss_prev == dss_max) {
1866                                /* Success. */
1867                                dss_max = (void *)((intptr_t)dss_prev + incr);
1868                                malloc_mutex_unlock(&dss_mtx);
1869                                return (ret);
1870                        }
1871                } while (dss_prev != (void *)-1);
1872        }
1873        malloc_mutex_unlock(&dss_mtx);
1874
1875        return (NULL);
1876}
1877
1878static void *
1879chunk_recycle_dss(size_t size, bool zero)
1880{
1881        extent_node_t *node, key;
1882
1883        key.addr = NULL;
1884        key.size = size;
1885        malloc_mutex_lock(&dss_mtx);
1886        node = extent_tree_szad_nsearch(&dss_chunks_szad, &key);
1887        if (node != NULL) {
1888                void *ret = node->addr;
1889
1890                /* Remove node from the tree. */
1891                extent_tree_szad_remove(&dss_chunks_szad, node);
1892                if (node->size == size) {
1893                        extent_tree_ad_remove(&dss_chunks_ad, node);
1894                        base_node_dealloc(node);
1895                } else {
1896                        /*
1897                         * Insert the remainder of node's address range as a
1898                         * smaller chunk.  Its position within dss_chunks_ad
1899                         * does not change.
1900                         */
1901                        assert(node->size > size);
1902                        node->addr = (void *)((uintptr_t)node->addr + size);
1903                        node->size -= size;
1904                        extent_tree_szad_insert(&dss_chunks_szad, node);
1905                }
1906                malloc_mutex_unlock(&dss_mtx);
1907
1908                if (zero)
1909                        memset(ret, 0, size);
1910                return (ret);
1911        }
1912        malloc_mutex_unlock(&dss_mtx);
1913
1914        return (NULL);
1915}
1916#endif
1917
1918static void *
1919chunk_alloc_mmap(size_t size)
1920{
1921        void *ret;
1922        size_t offset;
1923
1924        /*
1925         * Ideally, there would be a way to specify alignment to mmap() (like
1926         * NetBSD has), but in the absence of such a feature, we have to work
1927         * hard to efficiently create aligned mappings.  The reliable, but
1928         * expensive method is to create a mapping that is over-sized, then
1929         * trim the excess.  However, that always results in at least one call
1930         * to pages_unmap().
1931         *
1932         * A more optimistic approach is to try mapping precisely the right
1933         * amount, then try to append another mapping if alignment is off.  In
1934         * practice, this works out well as long as the application is not
1935         * interleaving mappings via direct mmap() calls.  If we do run into a
1936         * situation where there is an interleaved mapping and we are unable to
1937         * extend an unaligned mapping, our best option is to momentarily
1938         * revert to the reliable-but-expensive method.  This will tend to
1939         * leave a gap in the memory map that is too small to cause later
1940         * problems for the optimistic method.
1941         */
1942
1943        ret = pages_map(NULL, size);
1944        if (ret == NULL)
1945                return (NULL);
1946
1947        offset = CHUNK_ADDR2OFFSET(ret);
1948        if (offset != 0) {
1949                /* Try to extend chunk boundary. */
1950                if (pages_map((void *)((uintptr_t)ret + size),
1951                    chunksize - offset) == NULL) {
1952                        /*
1953                         * Extension failed.  Clean up, then revert to the
1954                         * reliable-but-expensive method.
1955                         */
1956                        pages_unmap(ret, size);
1957
1958                        /* Beware size_t wrap-around. */
1959                        if (size + chunksize <= size)
1960                                return NULL;
1961
1962                        ret = pages_map(NULL, size + chunksize);
1963                        if (ret == NULL)
1964                                return (NULL);
1965
1966                        /* Clean up unneeded leading/trailing space. */
1967                        offset = CHUNK_ADDR2OFFSET(ret);
1968                        if (offset != 0) {
1969                                /* Leading space. */
1970                                pages_unmap(ret, chunksize - offset);
1971
1972                                ret = (void *)((uintptr_t)ret +
1973                                    (chunksize - offset));
1974
1975                                /* Trailing space. */
1976                                pages_unmap((void *)((uintptr_t)ret + size),
1977                                    offset);
1978                        } else {
1979                                /* Trailing space only. */
1980                                pages_unmap((void *)((uintptr_t)ret + size),
1981                                    chunksize);
1982                        }
1983                } else {
1984                        /* Clean up unneeded leading space. */
1985                        pages_unmap(ret, chunksize - offset);
1986                        ret = (void *)((uintptr_t)ret + (chunksize - offset));
1987                }
1988        }
1989
1990        return (ret);
1991}
1992
1993static void *
1994chunk_alloc(size_t size, bool zero)
1995{
1996        void *ret;
1997
1998        assert(size != 0);
1999        assert((size & chunksize_mask) == 0);
2000
2001#ifdef MALLOC_DSS
2002        if (opt_dss) {
2003                ret = chunk_recycle_dss(size, zero);
2004                if (ret != NULL) {
2005                        goto RETURN;
2006                }
2007
2008                ret = chunk_alloc_dss(size);
2009                if (ret != NULL)
2010                        goto RETURN;
2011        }
2012
2013        if (opt_mmap)
2014#endif
2015        {
2016                ret = chunk_alloc_mmap(size);
2017                if (ret != NULL)
2018                        goto RETURN;
2019        }
2020
2021        /* All strategies for allocation failed. */
2022        ret = NULL;
2023RETURN:
2024#ifdef MALLOC_STATS
2025        if (ret != NULL) {
2026                stats_chunks.nchunks += (size / chunksize);
2027                stats_chunks.curchunks += (size / chunksize);
2028        }
2029        if (stats_chunks.curchunks > stats_chunks.highchunks)
2030                stats_chunks.highchunks = stats_chunks.curchunks;
2031#endif
2032
2033        assert(CHUNK_ADDR2BASE(ret) == ret);
2034        return (ret);
2035}
2036
2037#ifdef MALLOC_DSS
2038static extent_node_t *
2039chunk_dealloc_dss_record(void *chunk, size_t size)
2040{
2041        extent_node_t *node, *prev, key;
2042
2043        key.addr = (void *)((uintptr_t)chunk + size);
2044        node = extent_tree_ad_nsearch(&dss_chunks_ad, &key);
2045        /* Try to coalesce forward. */
2046        if (node != NULL && node->addr == key.addr) {
2047                /*
2048                 * Coalesce chunk with the following address range.  This does
2049                 * not change the position within dss_chunks_ad, so only
2050                 * remove/insert from/into dss_chunks_szad.
2051                 */
2052                extent_tree_szad_remove(&dss_chunks_szad, node);
2053                node->addr = chunk;
2054                node->size += size;
2055                extent_tree_szad_insert(&dss_chunks_szad, node);
2056        } else {
2057                /*
2058                 * Coalescing forward failed, so insert a new node.  Drop
2059                 * dss_mtx during node allocation, since it is possible that a
2060                 * new base chunk will be allocated.
2061                 */
2062                malloc_mutex_unlock(&dss_mtx);
2063                node = base_node_alloc();
2064                malloc_mutex_lock(&dss_mtx);
2065                if (node == NULL)
2066                        return (NULL);
2067                node->addr = chunk;
2068                node->size = size;
2069                extent_tree_ad_insert(&dss_chunks_ad, node);
2070                extent_tree_szad_insert(&dss_chunks_szad, node);
2071        }
2072
2073        /* Try to coalesce backward. */
2074        prev = extent_tree_ad_prev(&dss_chunks_ad, node);
2075        if (prev != NULL && (void *)((uintptr_t)prev->addr + prev->size) ==
2076            chunk) {
2077                /*
2078                 * Coalesce chunk with the previous address range.  This does
2079                 * not change the position within dss_chunks_ad, so only
2080                 * remove/insert node from/into dss_chunks_szad.
2081                 */
2082                extent_tree_szad_remove(&dss_chunks_szad, prev);
2083                extent_tree_ad_remove(&dss_chunks_ad, prev);
2084
2085                extent_tree_szad_remove(&dss_chunks_szad, node);
2086                node->addr = prev->addr;
2087                node->size += prev->size;
2088                extent_tree_szad_insert(&dss_chunks_szad, node);
2089
2090                base_node_dealloc(prev);
2091        }
2092
2093        return (node);
2094}
2095
2096static bool
2097chunk_dealloc_dss(void *chunk, size_t size)
2098{
2099
2100        malloc_mutex_lock(&dss_mtx);
2101        if ((uintptr_t)chunk >= (uintptr_t)dss_base
2102            && (uintptr_t)chunk < (uintptr_t)dss_max) {
2103                extent_node_t *node;
2104
2105                /* Try to coalesce with other unused chunks. */
2106                node = chunk_dealloc_dss_record(chunk, size);
2107                if (node != NULL) {
2108                        chunk = node->addr;
2109                        size = node->size;
2110                }
2111
2112                /* Get the current end of the DSS. */
2113                dss_max = sbrk(0);
2114
2115                /*
2116                 * Try to shrink the DSS if this chunk is at the end of the
2117                 * DSS.  The sbrk() call here is subject to a race condition
2118                 * with threads that use brk(2) or sbrk(2) directly, but the
2119                 * alternative would be to leak memory for the sake of poorly
2120                 * designed multi-threaded programs.
2121                 */
2122                if ((void *)((uintptr_t)chunk + size) == dss_max
2123                    && (dss_prev = sbrk(-(intptr_t)size)) == dss_max) {
2124                        /* Success. */
2125                        dss_max = (void *)((intptr_t)dss_prev - (intptr_t)size);
2126
2127                        if (node != NULL) {
2128                                extent_tree_szad_remove(&dss_chunks_szad, node);
2129                                extent_tree_ad_remove(&dss_chunks_ad, node);
2130                                base_node_dealloc(node);
2131                        }
2132                        malloc_mutex_unlock(&dss_mtx);
2133                } else {
2134                        malloc_mutex_unlock(&dss_mtx);
2135                        madvise(chunk, size, MADV_FREE);
2136                }
2137
2138                return (false);
2139        }
2140        malloc_mutex_unlock(&dss_mtx);
2141
2142        return (true);
2143}
2144#endif
2145
2146static void
2147chunk_dealloc_mmap(void *chunk, size_t size)
2148{
2149
2150        pages_unmap(chunk, size);
2151}
2152
2153static void
2154chunk_dealloc(void *chunk, size_t size)
2155{
2156
2157        assert(chunk != NULL);
2158        assert(CHUNK_ADDR2BASE(chunk) == chunk);
2159        assert(size != 0);
2160        assert((size & chunksize_mask) == 0);
2161
2162#ifdef MALLOC_STATS
2163        stats_chunks.curchunks -= (size / chunksize);
2164#endif
2165
2166#ifdef MALLOC_DSS
2167        if (opt_dss) {
2168                if (chunk_dealloc_dss(chunk, size) == false)
2169                        return;
2170        }
2171
2172        if (opt_mmap)
2173#endif
2174                chunk_dealloc_mmap(chunk, size);
2175}
2176
2177/*
2178 * End chunk management functions.
2179 */
2180/******************************************************************************/
2181/*
2182 * Begin arena.
2183 */
2184
2185/*
2186 * Choose an arena based on a per-thread value (fast-path code, calls slow-path
2187 * code if necessary).
2188 */
2189static inline arena_t *
2190choose_arena(void)
2191{
2192        arena_t *ret;
2193
2194        /*
2195         * We can only use TLS if this is a PIC library, since for the static
2196         * library version, libc's malloc is used by TLS allocation, which
2197         * introduces a bootstrapping issue.
2198         */
2199#ifndef NO_TLS
2200        if (__isthreaded == false) {
2201            /* Avoid the overhead of TLS for single-threaded operation. */
2202            return (arenas[0]);
2203        }
2204
2205        ret = arenas_map;
2206        if (ret == NULL) {
2207                ret = choose_arena_hard();
2208                assert(ret != NULL);
2209        }
2210#else
2211        if (__isthreaded && narenas > 1) {
2212                unsigned long ind;
2213
2214                /*
2215                 * Hash _pthread_self() to one of the arenas.  There is a prime
2216                 * number of arenas, so this has a reasonable chance of
2217                 * working.  Even so, the hashing can be easily thwarted by
2218                 * inconvenient _pthread_self() values.  Without specific
2219                 * knowledge of how _pthread_self() calculates values, we can't
2220                 * easily do much better than this.
2221                 */
2222                ind = (unsigned long) _pthread_self() % narenas;
2223
2224                /*
2225                 * Optimistially assume that arenas[ind] has been initialized.
2226                 * At worst, we find out that some other thread has already
2227                 * done so, after acquiring the lock in preparation.  Note that
2228                 * this lazy locking also has the effect of lazily forcing
2229                 * cache coherency; without the lock acquisition, there's no
2230                 * guarantee that modification of arenas[ind] by another thread
2231                 * would be seen on this CPU for an arbitrary amount of time.
2232                 *
2233                 * In general, this approach to modifying a synchronized value
2234                 * isn't a good idea, but in this case we only ever modify the
2235                 * value once, so things work out well.
2236                 */
2237                ret = arenas[ind];
2238                if (ret == NULL) {
2239                        /*
2240                         * Avoid races with another thread that may have already
2241                         * initialized arenas[ind].
2242                         */
2243                        malloc_spin_lock(&arenas_lock);
2244                        if (arenas[ind] == NULL)
2245                                ret = arenas_extend((unsigned)ind);
2246                        else
2247                                ret = arenas[ind];
2248                        malloc_spin_unlock(&arenas_lock);
2249                }
2250        } else
2251                ret = arenas[0];
2252#endif
2253
2254        assert(ret != NULL);
2255        return (ret);
2256}
2257
2258#ifndef NO_TLS
2259/*
2260 * Choose an arena based on a per-thread value (slow-path code only, called
2261 * only by choose_arena()).
2262 */
2263static arena_t *
2264choose_arena_hard(void)
2265{
2266        arena_t *ret;
2267
2268        assert(__isthreaded);
2269
2270#ifdef MALLOC_BALANCE
2271        /* Seed the PRNG used for arena load balancing. */
2272        SPRN(balance, (uint32_t)(uintptr_t)(_pthread_self()));
2273#endif
2274
2275        if (narenas > 1) {
2276#ifdef MALLOC_BALANCE
2277                unsigned ind;
2278
2279                ind = PRN(balance, narenas_2pow);
2280                if ((ret = arenas[ind]) == NULL) {
2281                        malloc_spin_lock(&arenas_lock);
2282                        if ((ret = arenas[ind]) == NULL)
2283                                ret = arenas_extend(ind);
2284                        malloc_spin_unlock(&arenas_lock);
2285                }
2286#else
2287                malloc_spin_lock(&arenas_lock);
2288                if ((ret = arenas[next_arena]) == NULL)
2289                        ret = arenas_extend(next_arena);
2290                next_arena = (next_arena + 1) % narenas;
2291                malloc_spin_unlock(&arenas_lock);
2292#endif
2293        } else
2294                ret = arenas[0];
2295
2296        arenas_map = ret;
2297
2298        return (ret);
2299}
2300#endif
2301
2302static inline int
2303arena_chunk_comp(arena_chunk_t *a, arena_chunk_t *b)
2304{
2305        uintptr_t a_chunk = (uintptr_t)a;
2306        uintptr_t b_chunk = (uintptr_t)b;
2307
2308        assert(a != NULL);
2309        assert(b != NULL);
2310
2311        return ((a_chunk > b_chunk) - (a_chunk < b_chunk));
2312}
2313
2314/* Wrap red-black tree macros in functions. */
2315rb_wrap(__unused static, arena_chunk_tree_dirty_, arena_chunk_tree_t,
2316    arena_chunk_t, link_dirty, arena_chunk_comp)
2317
2318static inline int
2319arena_run_comp(arena_chunk_map_t *a, arena_chunk_map_t *b)
2320{
2321        uintptr_t a_mapelm = (uintptr_t)a;
2322        uintptr_t b_mapelm = (uintptr_t)b;
2323
2324        assert(a != NULL);
2325        assert(b != NULL);
2326
2327        return ((a_mapelm > b_mapelm) - (a_mapelm < b_mapelm));
2328}
2329
2330/* Wrap red-black tree macros in functions. */
2331rb_wrap(__unused static, arena_run_tree_, arena_run_tree_t, arena_chunk_map_t,
2332    link, arena_run_comp)
2333
2334static inline int
2335arena_avail_comp(arena_chunk_map_t *a, arena_chunk_map_t *b)
2336{
2337        int ret;
2338        size_t a_size = a->bits & ~pagesize_mask;
2339        size_t b_size = b->bits & ~pagesize_mask;
2340
2341        ret = (a_size > b_size) - (a_size < b_size);
2342        if (ret == 0) {
2343                uintptr_t a_mapelm, b_mapelm;
2344
2345                if ((a->bits & CHUNK_MAP_KEY) == 0)
2346                        a_mapelm = (uintptr_t)a;
2347                else {
2348                        /*
2349                         * Treat keys as though they are lower than anything
2350                         * else.
2351                         */
2352                        a_mapelm = 0;
2353                }
2354                b_mapelm = (uintptr_t)b;
2355
2356                ret = (a_mapelm > b_mapelm) - (a_mapelm < b_mapelm);
2357        }
2358
2359        return (ret);
2360}
2361
2362/* Wrap red-black tree macros in functions. */
2363rb_wrap(__unused static, arena_avail_tree_, arena_avail_tree_t,
2364    arena_chunk_map_t, link, arena_avail_comp)
2365
2366static inline void *
2367arena_run_reg_alloc(arena_run_t *run, arena_bin_t *bin)
2368{
2369        void *ret;
2370        unsigned i, mask, bit, regind;
2371
2372        assert(run->magic == ARENA_RUN_MAGIC);
2373        assert(run->regs_minelm < bin->regs_mask_nelms);
2374
2375        /*
2376         * Move the first check outside the loop, so that run->regs_minelm can
2377         * be updated unconditionally, without the possibility of updating it
2378         * multiple times.
2379         */
2380        i = run->regs_minelm;
2381        mask = run->regs_mask[i];
2382        if (mask != 0) {
2383                /* Usable allocation found. */
2384                bit = ffs((int)mask) - 1;
2385
2386                regind = ((i << (SIZEOF_INT_2POW + 3)) + bit);
2387                assert(regind < bin->nregs);
2388                ret = (void *)(((uintptr_t)run) + bin->reg0_offset
2389                    + (bin->reg_size * regind));
2390
2391                /* Clear bit. */
2392                mask ^= (1U << bit);
2393                run->regs_mask[i] = mask;
2394
2395                return (ret);
2396        }
2397
2398        for (i++; i < bin->regs_mask_nelms; i++) {
2399                mask = run->regs_mask[i];
2400                if (mask != 0) {
2401                        /* Usable allocation found. */
2402                        bit = ffs((int)mask) - 1;
2403
2404                        regind = ((i << (SIZEOF_INT_2POW + 3)) + bit);
2405                        assert(regind < bin->nregs);
2406                        ret = (void *)(((uintptr_t)run) + bin->reg0_offset
2407                            + (bin->reg_size * regind));
2408
2409                        /* Clear bit. */
2410                        mask ^= (1U << bit);
2411                        run->regs_mask[i] = mask;
2412
2413                        /*
2414                         * Make a note that nothing before this element
2415                         * contains a free region.
2416                         */
2417                        run->regs_minelm = i; /* Low payoff: + (mask == 0); */
2418
2419                        return (ret);
2420                }
2421        }
2422        /* Not reached. */
2423        assert(0);
2424        return (NULL);
2425}
2426
2427static inline void
2428arena_run_reg_dalloc(arena_run_t *run, arena_bin_t *bin, void *ptr, size_t size)
2429{
2430        unsigned diff, regind, elm, bit;
2431
2432        assert(run->magic == ARENA_RUN_MAGIC);
2433
2434        /*
2435         * Avoid doing division with a variable divisor if possible.  Using
2436         * actual division here can reduce allocator throughput by over 20%!
2437         */
2438        diff = (unsigned)((uintptr_t)ptr - (uintptr_t)run - bin->reg0_offset);
2439        if ((size & (size - 1)) == 0) {
2440                /*
2441                 * log2_table allows fast division of a power of two in the
2442                 * [1..128] range.
2443                 *
2444                 * (x / divisor) becomes (x >> log2_table[divisor - 1]).
2445                 */
2446                static const unsigned char log2_table[] = {
2447                    0, 1, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 4,
2448                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5,
2449                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2450                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6,
2451                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2452                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2453                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2454                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7
2455                };
2456
2457                if (size <= 128)
2458                        regind = (diff >> log2_table[size - 1]);
2459                else if (size <= 32768)
2460                        regind = diff >> (8 + log2_table[(size >> 8) - 1]);
2461                else
2462                        regind = diff / size;
2463        } else if (size < qspace_max) {
2464                /*
2465                 * To divide by a number D that is not a power of two we
2466                 * multiply by (2^21 / D) and then right shift by 21 positions.
2467                 *
2468                 *   X / D
2469                 *
2470                 * becomes
2471                 *
2472                 *   (X * qsize_invs[(D >> QUANTUM_2POW) - 3])
2473                 *       >> SIZE_INV_SHIFT
2474                 *
2475                 * We can omit the first three elements, because we never
2476                 * divide by 0, and QUANTUM and 2*QUANTUM are both powers of
2477                 * two, which are handled above.
2478                 */
2479#define SIZE_INV_SHIFT 21
2480#define QSIZE_INV(s) (((1U << SIZE_INV_SHIFT) / (s << QUANTUM_2POW)) + 1)
2481                static const unsigned qsize_invs[] = {
2482                    QSIZE_INV(3),
2483                    QSIZE_INV(4), QSIZE_INV(5), QSIZE_INV(6), QSIZE_INV(7)
2484#if (QUANTUM_2POW < 4)
2485                    ,
2486                    QSIZE_INV(8), QSIZE_INV(9), QSIZE_INV(10), QSIZE_INV(11),
2487                    QSIZE_INV(12),QSIZE_INV(13), QSIZE_INV(14), QSIZE_INV(15)
2488#endif
2489                };
2490                assert(QUANTUM * (((sizeof(qsize_invs)) / sizeof(unsigned)) + 3)
2491                    >= (1U << QSPACE_MAX_2POW_DEFAULT));
2492
2493                if (size <= (((sizeof(qsize_invs) / sizeof(unsigned)) + 2) <<
2494                    QUANTUM_2POW)) {
2495                        regind = qsize_invs[(size >> QUANTUM_2POW) - 3] * diff;
2496                        regind >>= SIZE_INV_SHIFT;
2497                } else
2498                        regind = diff / size;
2499#undef QSIZE_INV
2500        } else if (size < cspace_max) {
2501#define CSIZE_INV(s) (((1U << SIZE_INV_SHIFT) / (s << CACHELINE_2POW)) + 1)
2502                static const unsigned csize_invs[] = {
2503                    CSIZE_INV(3),
2504                    CSIZE_INV(4), CSIZE_INV(5), CSIZE_INV(6), CSIZE_INV(7)
2505                };
2506                assert(CACHELINE * (((sizeof(csize_invs)) / sizeof(unsigned)) +
2507                    3) >= (1U << CSPACE_MAX_2POW_DEFAULT));
2508
2509                if (size <= (((sizeof(csize_invs) / sizeof(unsigned)) + 2) <<
2510                    CACHELINE_2POW)) {
2511                        regind = csize_invs[(size >> CACHELINE_2POW) - 3] *
2512                            diff;
2513                        regind >>= SIZE_INV_SHIFT;
2514                } else
2515                        regind = diff / size;
2516#undef CSIZE_INV
2517        } else {
2518#define SSIZE_INV(s) (((1U << SIZE_INV_SHIFT) / (s << SUBPAGE_2POW)) + 1)
2519                static const unsigned ssize_invs[] = {
2520                    SSIZE_INV(3),
2521                    SSIZE_INV(4), SSIZE_INV(5), SSIZE_INV(6), SSIZE_INV(7),
2522                    SSIZE_INV(8), SSIZE_INV(9), SSIZE_INV(10), SSIZE_INV(11),
2523                    SSIZE_INV(12), SSIZE_INV(13), SSIZE_INV(14), SSIZE_INV(15)
2524#if (PAGESIZE_2POW == 13)
2525                    ,
2526                    SSIZE_INV(16), SSIZE_INV(17), SSIZE_INV(18), SSIZE_INV(19),
2527                    SSIZE_INV(20), SSIZE_INV(21), SSIZE_INV(22), SSIZE_INV(23),
2528                    SSIZE_INV(24), SSIZE_INV(25), SSIZE_INV(26), SSIZE_INV(27),
2529                    SSIZE_INV(28), SSIZE_INV(29), SSIZE_INV(29), SSIZE_INV(30)
2530#endif
2531                };
2532                assert(SUBPAGE * (((sizeof(ssize_invs)) / sizeof(unsigned)) + 3)
2533                    >= (1U << PAGESIZE_2POW));
2534
2535                if (size < (((sizeof(ssize_invs) / sizeof(unsigned)) + 2) <<
2536                    SUBPAGE_2POW)) {
2537                        regind = ssize_invs[(size >> SUBPAGE_2POW) - 3] * diff;
2538                        regind >>= SIZE_INV_SHIFT;
2539                } else
2540                        regind = diff / size;
2541#undef SSIZE_INV
2542        }
2543#undef SIZE_INV_SHIFT
2544        assert(diff == regind * size);
2545        assert(regind < bin->nregs);
2546
2547        elm = regind >> (SIZEOF_INT_2POW + 3);
2548        if (elm < run->regs_minelm)
2549                run->regs_minelm = elm;
2550        bit = regind - (elm << (SIZEOF_INT_2POW + 3));
2551        assert((run->regs_mask[elm] & (1U << bit)) == 0);
2552        run->regs_mask[elm] |= (1U << bit);
2553}
2554
2555static void
2556arena_run_split(arena_t *arena, arena_run_t *run, size_t size, bool large,
2557    bool zero)
2558{
2559        arena_chunk_t *chunk;
2560        size_t old_ndirty, run_ind, total_pages, need_pages, rem_pages, i;
2561
2562        chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
2563        old_ndirty = chunk->ndirty;
2564        run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk)
2565            >> pagesize_2pow);
2566        total_pages = (chunk->map[run_ind].bits & ~pagesize_mask) >>
2567            pagesize_2pow;
2568        need_pages = (size >> pagesize_2pow);
2569        assert(need_pages > 0);
2570        assert(need_pages <= total_pages);
2571        rem_pages = total_pages - need_pages;
2572
2573        arena_avail_tree_remove(&arena->runs_avail, &chunk->map[run_ind]);
2574
2575        /* Keep track of trailing unused pages for later use. */
2576        if (rem_pages > 0) {
2577                chunk->map[run_ind+need_pages].bits = (rem_pages <<
2578                    pagesize_2pow) | (chunk->map[run_ind+need_pages].bits &
2579                    pagesize_mask);
2580                chunk->map[run_ind+total_pages-1].bits = (rem_pages <<
2581                    pagesize_2pow) | (chunk->map[run_ind+total_pages-1].bits &
2582                    pagesize_mask);
2583                arena_avail_tree_insert(&arena->runs_avail,
2584                    &chunk->map[run_ind+need_pages]);
2585        }
2586
2587        for (i = 0; i < need_pages; i++) {
2588                /* Zero if necessary. */
2589                if (zero) {
2590                        if ((chunk->map[run_ind + i].bits & CHUNK_MAP_ZEROED)
2591                            == 0) {
2592                                memset((void *)((uintptr_t)chunk + ((run_ind
2593                                    + i) << pagesize_2pow)), 0, pagesize);
2594                                /* CHUNK_MAP_ZEROED is cleared below. */
2595                        }
2596                }
2597
2598                /* Update dirty page accounting. */
2599                if (chunk->map[run_ind + i].bits & CHUNK_MAP_DIRTY) {
2600                        chunk->ndirty--;
2601                        arena->ndirty--;
2602                        /* CHUNK_MAP_DIRTY is cleared below. */
2603                }
2604
2605                /* Initialize the chunk map. */
2606                if (large) {
2607                        chunk->map[run_ind + i].bits = CHUNK_MAP_LARGE
2608                            | CHUNK_MAP_ALLOCATED;
2609                } else {
2610                        chunk->map[run_ind + i].bits = (size_t)run
2611                            | CHUNK_MAP_ALLOCATED;
2612                }
2613        }
2614
2615        /*
2616         * Set the run size only in the first element for large runs.  This is
2617         * primarily a debugging aid, since the lack of size info for trailing
2618         * pages only matters if the application tries to operate on an
2619         * interior pointer.
2620         */
2621        if (large)
2622                chunk->map[run_ind].bits |= size;
2623
2624        if (chunk->ndirty == 0 && old_ndirty > 0)
2625                arena_chunk_tree_dirty_remove(&arena->chunks_dirty, chunk);
2626}
2627
2628static arena_chunk_t *
2629arena_chunk_alloc(arena_t *arena)
2630{
2631        arena_chunk_t *chunk;
2632        size_t i;
2633
2634        if (arena->spare != NULL) {
2635                chunk = arena->spare;
2636                arena->spare = NULL;
2637        } else {
2638                chunk = (arena_chunk_t *)chunk_alloc(chunksize, true);
2639                if (chunk == NULL)
2640                        return (NULL);
2641#ifdef MALLOC_STATS
2642                arena->stats.mapped += chunksize;
2643#endif
2644
2645                chunk->arena = arena;
2646
2647                /*
2648                 * Claim that no pages are in use, since the header is merely
2649                 * overhead.
2650                 */
2651                chunk->ndirty = 0;
2652
2653                /*
2654                 * Initialize the map to contain one maximal free untouched run.
2655                 */
2656                for (i = 0; i < arena_chunk_header_npages; i++)
2657                        chunk->map[i].bits = 0;
2658                chunk->map[i].bits = arena_maxclass | CHUNK_MAP_ZEROED;
2659                for (i++; i < chunk_npages-1; i++) {
2660                        chunk->map[i].bits = CHUNK_MAP_ZEROED;
2661                }
2662                chunk->map[chunk_npages-1].bits = arena_maxclass |
2663                    CHUNK_MAP_ZEROED;
2664        }
2665
2666        /* Insert the run into the runs_avail tree. */
2667        arena_avail_tree_insert(&arena->runs_avail,
2668            &chunk->map[arena_chunk_header_npages]);
2669
2670        return (chunk);
2671}
2672
2673static void
2674arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk)
2675{
2676
2677        if (arena->spare != NULL) {
2678                if (arena->spare->ndirty > 0) {
2679                        arena_chunk_tree_dirty_remove(
2680                            &chunk->arena->chunks_dirty, arena->spare);
2681                        arena->ndirty -= arena->spare->ndirty;
2682                }
2683                chunk_dealloc((void *)arena->spare, chunksize);
2684#ifdef MALLOC_STATS
2685                arena->stats.mapped -= chunksize;
2686#endif
2687        }
2688
2689        /*
2690         * Remove run from runs_avail, regardless of whether this chunk
2691         * will be cached, so that the arena does not use it.  Dirty page
2692         * flushing only uses the chunks_dirty tree, so leaving this chunk in
2693         * the chunks_* trees is sufficient for that purpose.
2694         */
2695        arena_avail_tree_remove(&arena->runs_avail,
2696            &chunk->map[arena_chunk_header_npages]);
2697
2698        arena->spare = chunk;
2699}
2700
2701static arena_run_t *
2702arena_run_alloc(arena_t *arena, size_t size, bool large, bool zero)
2703{
2704        arena_chunk_t *chunk;
2705        arena_run_t *run;
2706        arena_chunk_map_t *mapelm, key;
2707
2708        assert(size <= arena_maxclass);
2709        assert((size & pagesize_mask) == 0);
2710
2711        /* Search the arena's chunks for the lowest best fit. */
2712        key.bits = size | CHUNK_MAP_KEY;
2713        mapelm = arena_avail_tree_nsearch(&arena->runs_avail, &key);
2714        if (mapelm != NULL) {
2715                arena_chunk_t *run_chunk = CHUNK_ADDR2BASE(mapelm);
2716                size_t pageind = ((uintptr_t)mapelm - (uintptr_t)run_chunk->map)
2717                    / sizeof(arena_chunk_map_t);
2718
2719                run = (arena_run_t *)((uintptr_t)run_chunk + (pageind
2720                    << pagesize_2pow));
2721                arena_run_split(arena, run, size, large, zero);
2722                return (run);
2723        }
2724
2725        /*
2726         * No usable runs.  Create a new chunk from which to allocate the run.
2727         */
2728        chunk = arena_chunk_alloc(arena);
2729        if (chunk == NULL)
2730                return (NULL);
2731        run = (arena_run_t *)((uintptr_t)chunk + (arena_chunk_header_npages <<
2732            pagesize_2pow));
2733        /* Update page map. */
2734        arena_run_split(arena, run, size, large, zero);
2735        return (run);
2736}
2737
2738static void
2739arena_purge(arena_t *arena)
2740{
2741        arena_chunk_t *chunk;
2742        size_t i, npages;
2743#ifdef MALLOC_DEBUG
2744        size_t ndirty = 0;
2745
2746        rb_foreach_begin(arena_chunk_t, link_dirty, &arena->chunks_dirty,
2747            chunk) {
2748                ndirty += chunk->ndirty;
2749        } rb_foreach_end(arena_chunk_t, link_dirty, &arena->chunks_dirty, chunk)
2750        assert(ndirty == arena->ndirty);
2751#endif
2752        assert(arena->ndirty > opt_dirty_max);
2753
2754#ifdef MALLOC_STATS
2755        arena->stats.npurge++;
2756#endif
2757
2758        /*
2759         * Iterate downward through chunks until enough dirty memory has been
2760         * purged.  Terminate as soon as possible in order to minimize the
2761         * number of system calls, even if a chunk has only been partially
2762         * purged.
2763         */
2764        while (arena->ndirty > (opt_dirty_max >> 1)) {
2765                chunk = arena_chunk_tree_dirty_last(&arena->chunks_dirty);
2766                assert(chunk != NULL);
2767
2768                for (i = chunk_npages - 1; chunk->ndirty > 0; i--) {
2769                        assert(i >= arena_chunk_header_npages);
2770
2771                        if (chunk->map[i].bits & CHUNK_MAP_DIRTY) {
2772                                chunk->map[i].bits ^= CHUNK_MAP_DIRTY;
2773                                /* Find adjacent dirty run(s). */
2774                                for (npages = 1; i > arena_chunk_header_npages
2775                                    && (chunk->map[i - 1].bits &
2776                                    CHUNK_MAP_DIRTY); npages++) {
2777                                        i--;
2778                                        chunk->map[i].bits ^= CHUNK_MAP_DIRTY;
2779                                }
2780                                chunk->ndirty -= npages;
2781                                arena->ndirty -= npages;
2782
2783                                madvise((void *)((uintptr_t)chunk + (i <<
2784                                    pagesize_2pow)), (npages << pagesize_2pow),
2785                                    MADV_FREE);
2786#ifdef MALLOC_STATS
2787                                arena->stats.nmadvise++;
2788                                arena->stats.purged += npages;
2789#endif
2790                                if (arena->ndirty <= (opt_dirty_max >> 1))
2791                                        break;
2792                        }
2793                }
2794
2795                if (chunk->ndirty == 0) {
2796                        arena_chunk_tree_dirty_remove(&arena->chunks_dirty,
2797                            chunk);
2798                }
2799        }
2800}
2801
2802static void
2803arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty)
2804{
2805        arena_chunk_t *chunk;
2806        size_t size, run_ind, run_pages;
2807
2808        chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
2809        run_ind = (size_t)(((uintptr_t)run - (uintptr_t)chunk)
2810            >> pagesize_2pow);
2811        assert(run_ind >= arena_chunk_header_npages);
2812        assert(run_ind < chunk_npages);
2813        if ((chunk->map[run_ind].bits & CHUNK_MAP_LARGE) != 0)
2814                size = chunk->map[run_ind].bits & ~pagesize_mask;
2815        else
2816                size = run->bin->run_size;
2817        run_pages = (size >> pagesize_2pow);
2818
2819        /* Mark pages as unallocated in the chunk map. */
2820        if (dirty) {
2821                size_t i;
2822
2823                for (i = 0; i < run_pages; i++) {
2824                        assert((chunk->map[run_ind + i].bits & CHUNK_MAP_DIRTY)
2825                            == 0);
2826                        chunk->map[run_ind + i].bits = CHUNK_MAP_DIRTY;
2827                }
2828
2829                if (chunk->ndirty == 0) {
2830                        arena_chunk_tree_dirty_insert(&arena->chunks_dirty,
2831                            chunk);
2832                }
2833                chunk->ndirty += run_pages;
2834                arena->ndirty += run_pages;
2835        } else {
2836                size_t i;
2837
2838                for (i = 0; i < run_pages; i++) {
2839                        chunk->map[run_ind + i].bits &= ~(CHUNK_MAP_LARGE |
2840                            CHUNK_MAP_ALLOCATED);
2841                }
2842        }
2843        chunk->map[run_ind].bits = size | (chunk->map[run_ind].bits &
2844            pagesize_mask);
2845        chunk->map[run_ind+run_pages-1].bits = size |
2846            (chunk->map[run_ind+run_pages-1].bits & pagesize_mask);
2847
2848        /* Try to coalesce forward. */
2849        if (run_ind + run_pages < chunk_npages &&
2850            (chunk->map[run_ind+run_pages].bits & CHUNK_MAP_ALLOCATED) == 0) {
2851                size_t nrun_size = chunk->map[run_ind+run_pages].bits &
2852                    ~pagesize_mask;
2853
2854                /*
2855                 * Remove successor from runs_avail; the coalesced run is
2856                 * inserted later.
2857                 */
2858                arena_avail_tree_remove(&arena->runs_avail,
2859                    &chunk->map[run_ind+run_pages]);
2860
2861                size += nrun_size;
2862                run_pages = size >> pagesize_2pow;
2863
2864                assert((chunk->map[run_ind+run_pages-1].bits & ~pagesize_mask)
2865                    == nrun_size);
2866                chunk->map[run_ind].bits = size | (chunk->map[run_ind].bits &
2867                    pagesize_mask);
2868                chunk->map[run_ind+run_pages-1].bits = size |
2869                    (chunk->map[run_ind+run_pages-1].bits & pagesize_mask);
2870        }
2871
2872        /* Try to coalesce backward. */
2873        if (run_ind > arena_chunk_header_npages && (chunk->map[run_ind-1].bits &
2874            CHUNK_MAP_ALLOCATED) == 0) {
2875                size_t prun_size = chunk->map[run_ind-1].bits & ~pagesize_mask;
2876
2877                run_ind -= prun_size >> pagesize_2pow;
2878
2879                /*
2880                 * Remove predecessor from runs_avail; the coalesced run is
2881                 * inserted later.
2882                 */
2883                arena_avail_tree_remove(&arena->runs_avail,
2884                    &chunk->map[run_ind]);
2885
2886                size += prun_size;
2887                run_pages = size >> pagesize_2pow;
2888
2889                assert((chunk->map[run_ind].bits & ~pagesize_mask) ==
2890                    prun_size);
2891                chunk->map[run_ind].bits = size | (chunk->map[run_ind].bits &
2892                    pagesize_mask);
2893                chunk->map[run_ind+run_pages-1].bits = size |
2894                    (chunk->map[run_ind+run_pages-1].bits & pagesize_mask);
2895        }
2896
2897        /* Insert into runs_avail, now that coalescing is complete. */
2898        arena_avail_tree_insert(&arena->runs_avail, &chunk->map[run_ind]);
2899
2900        /* Deallocate chunk if it is now completely unused. */
2901        if ((chunk->map[arena_chunk_header_npages].bits & (~pagesize_mask |
2902            CHUNK_MAP_ALLOCATED)) == arena_maxclass)
2903                arena_chunk_dealloc(arena, chunk);
2904
2905        /* Enforce opt_dirty_max. */
2906        if (arena->ndirty > opt_dirty_max)
2907                arena_purge(arena);
2908}
2909
2910static void
2911arena_run_trim_head(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run,
2912    size_t oldsize, size_t newsize)
2913{
2914        size_t pageind = ((uintptr_t)run - (uintptr_t)chunk) >> pagesize_2pow;
2915        size_t head_npages = (oldsize - newsize) >> pagesize_2pow;
2916
2917        assert(oldsize > newsize);
2918
2919        /*
2920         * Update the chunk map so that arena_run_dalloc() can treat the
2921         * leading run as separately allocated.
2922         */
2923        chunk->map[pageind].bits = (oldsize - newsize) | CHUNK_MAP_LARGE |
2924            CHUNK_MAP_ALLOCATED;
2925        chunk->map[pageind+head_npages].bits = newsize | CHUNK_MAP_LARGE |
2926            CHUNK_MAP_ALLOCATED;
2927
2928        arena_run_dalloc(arena, run, false);
2929}
2930
2931static void
2932arena_run_trim_tail(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run,
2933    size_t oldsize, size_t newsize, bool dirty)
2934{
2935        size_t pageind = ((uintptr_t)run - (uintptr_t)chunk) >> pagesize_2pow;
2936        size_t npages = newsize >> pagesize_2pow;
2937
2938        assert(oldsize > newsize);
2939
2940        /*
2941         * Update the chunk map so that arena_run_dalloc() can treat the
2942         * trailing run as separately allocated.
2943         */
2944        chunk->map[pageind].bits = newsize | CHUNK_MAP_LARGE |
2945            CHUNK_MAP_ALLOCATED;
2946        chunk->map[pageind+npages].bits = (oldsize - newsize) | CHUNK_MAP_LARGE
2947            | CHUNK_MAP_ALLOCATED;
2948
2949        arena_run_dalloc(arena, (arena_run_t *)((uintptr_t)run + newsize),
2950            dirty);
2951}
2952
2953static arena_run_t *
2954arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin)
2955{
2956        arena_chunk_map_t *mapelm;
2957        arena_run_t *run;
2958        unsigned i, remainder;
2959
2960        /* Look for a usable run. */
2961        mapelm = arena_run_tree_first(&bin->runs);
2962        if (mapelm != NULL) {
2963                /* run is guaranteed to have available space. */
2964                arena_run_tree_remove(&bin->runs, mapelm);
2965                run = (arena_run_t *)(mapelm->bits & ~pagesize_mask);
2966#ifdef MALLOC_STATS
2967                bin->stats.reruns++;
2968#endif
2969                return (run);
2970        }
2971        /* No existing runs have any space available. */
2972
2973        /* Allocate a new run. */
2974        run = arena_run_alloc(arena, bin->run_size, false, false);
2975        if (run == NULL)
2976                return (NULL);
2977
2978        /* Initialize run internals. */
2979        run->bin = bin;
2980
2981        for (i = 0; i < bin->regs_mask_nelms - 1; i++)
2982                run->regs_mask[i] = UINT_MAX;
2983        remainder = bin->nregs & ((1U << (SIZEOF_INT_2POW + 3)) - 1);
2984        if (remainder == 0)
2985                run->regs_mask[i] = UINT_MAX;
2986        else {
2987                /* The last element has spare bits that need to be unset. */
2988                run->regs_mask[i] = (UINT_MAX >> ((1U << (SIZEOF_INT_2POW + 3))
2989                    - remainder));
2990        }
2991
2992        run->regs_minelm = 0;
2993
2994        run->nfree = bin->nregs;
2995#ifdef MALLOC_DEBUG
2996        run->magic = ARENA_RUN_MAGIC;
2997#endif
2998
2999#ifdef MALLOC_STATS
3000        bin->stats.nruns++;
3001        bin->stats.curruns++;
3002        if (bin->stats.curruns > bin->stats.highruns)
3003                bin->stats.highruns = bin->stats.curruns;
3004#endif
3005        return (run);
3006}
3007
3008/* bin->runcur must have space available before this function is called. */
3009static inline void *
3010arena_bin_malloc_easy(arena_t *arena, arena_bin_t *bin, arena_run_t *run)
3011{
3012        void *ret;
3013
3014        assert(run->magic == ARENA_RUN_MAGIC);
3015        assert(run->nfree > 0);
3016
3017        ret = arena_run_reg_alloc(run, bin);
3018        assert(ret != NULL);
3019        run->nfree--;
3020
3021        return (ret);
3022}
3023
3024/* Re-fill bin->runcur, then call arena_bin_malloc_easy(). */
3025static void *
3026arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin)
3027{
3028
3029        bin->runcur = arena_bin_nonfull_run_get(arena, bin);
3030        if (bin->runcur == NULL)
3031                return (NULL);
3032        assert(bin->runcur->magic == ARENA_RUN_MAGIC);
3033        assert(bin->runcur->nfree > 0);
3034
3035        return (arena_bin_malloc_easy(arena, bin, bin->runcur));
3036}
3037
3038/*
3039 * Calculate bin->run_size such that it meets the following constraints:
3040 *
3041 *   *) bin->run_size >= min_run_size
3042 *   *) bin->run_size <= arena_maxclass
3043 *   *) bin->run_size <= RUN_MAX_SMALL
3044 *   *) run header overhead <= RUN_MAX_OVRHD (or header overhead relaxed).
3045 *
3046 * bin->nregs, bin->regs_mask_nelms, and bin->reg0_offset are
3047 * also calculated here, since these settings are all interdependent.
3048 */
3049static size_t
3050arena_bin_run_size_calc(arena_bin_t *bin, size_t min_run_size)
3051{
3052        size_t try_run_size, good_run_size;
3053        unsigned good_nregs, good_mask_nelms, good_reg0_offset;
3054        unsigned try_nregs, try_mask_nelms, try_reg0_offset;
3055
3056        assert(min_run_size >= pagesize);
3057        assert(min_run_size <= arena_maxclass);
3058        assert(min_run_size <= RUN_MAX_SMALL);
3059
3060        /*
3061         * Calculate known-valid settings before entering the run_size
3062         * expansion loop, so that the first part of the loop always copies
3063         * valid settings.
3064         *
3065         * The do..while loop iteratively reduces the number of regions until
3066         * the run header and the regions no longer overlap.  A closed formula
3067         * would be quite messy, since there is an interdependency between the
3068         * header's mask length and the number of regions.
3069         */
3070        try_run_size = min_run_size;
3071        try_nregs = ((try_run_size - sizeof(arena_run_t)) / bin->reg_size)
3072            + 1; /* Counter-act try_nregs-- in loop. */
3073        do {
3074                try_nregs--;
3075                try_mask_nelms = (try_nregs >> (SIZEOF_INT_2POW + 3)) +
3076                    ((try_nregs & ((1U << (SIZEOF_INT_2POW + 3)) - 1)) ? 1 : 0);
3077                try_reg0_offset = try_run_size - (try_nregs * bin->reg_size);
3078        } while (sizeof(arena_run_t) + (sizeof(unsigned) * (try_mask_nelms - 1))
3079            > try_reg0_offset);
3080
3081        /* run_size expansion loop. */
3082        do {
3083                /*
3084                 * Copy valid settings before trying more aggressive settings.
3085                 */
3086                good_run_size = try_run_size;
3087                good_nregs = try_nregs;
3088                good_mask_nelms = try_mask_nelms;
3089                good_reg0_offset = try_reg0_offset;
3090
3091                /* Try more aggressive settings. */
3092                try_run_size += pagesize;
3093                try_nregs = ((try_run_size - sizeof(arena_run_t)) /
3094                    bin->reg_size) + 1; /* Counter-act try_nregs-- in loop. */
3095                do {
3096                        try_nregs--;
3097                        try_mask_nelms = (try_nregs >> (SIZEOF_INT_2POW + 3)) +
3098                            ((try_nregs & ((1U << (SIZEOF_INT_2POW + 3)) - 1)) ?
3099                            1 : 0);
3100                        try_reg0_offset = try_run_size - (try_nregs *
3101                            bin->reg_size);
3102                } while (sizeof(arena_run_t) + (sizeof(unsigned) *
3103                    (try_mask_nelms - 1)) > try_reg0_offset);
3104        } while (try_run_size <= arena_maxclass && try_run_size <= RUN_MAX_SMALL
3105            && RUN_MAX_OVRHD * (bin->reg_size << 3) > RUN_MAX_OVRHD_RELAX
3106            && (try_reg0_offset << RUN_BFP) > RUN_MAX_OVRHD * try_run_size);
3107
3108        assert(sizeof(arena_run_t) + (sizeof(unsigned) * (good_mask_nelms - 1))
3109            <= good_reg0_offset);
3110        assert((good_mask_nelms << (SIZEOF_INT_2POW + 3)) >= good_nregs);
3111
3112        /* Copy final settings. */
3113        bin->run_size = good_run_size;
3114        bin->nregs = good_nregs;
3115        bin->regs_mask_nelms = good_mask_nelms;
3116        bin->reg0_offset = good_reg0_offset;
3117
3118        return (good_run_size);
3119}
3120
3121#ifdef MALLOC_BALANCE
3122static inline void
3123arena_lock_balance(arena_t *arena)
3124{
3125        unsigned contention;
3126
3127        contention = malloc_spin_lock(&arena->lock);
3128        if (narenas > 1) {
3129                /*
3130                 * Calculate the exponentially averaged contention for this
3131                 * arena.  Due to integer math always rounding down, this value
3132                 * decays somewhat faster than normal.
3133                 */
3134                arena->contention = (((uint64_t)arena->contention
3135                    * (uint64_t)((1U << BALANCE_ALPHA_INV_2POW)-1))
3136                    + (uint64_t)contention) >> BALANCE_ALPHA_INV_2POW;
3137                if (arena->contention >= opt_balance_threshold)
3138                        arena_lock_balance_hard(arena);
3139        }
3140}
3141
3142static void
3143arena_lock_balance_hard(arena_t *arena)
3144{
3145        uint32_t ind;
3146
3147        arena->contention = 0;
3148#ifdef MALLOC_STATS
3149        arena->stats.nbalance++;
3150#endif
3151        ind = PRN(balance, narenas_2pow);
3152        if (arenas[ind] != NULL)
3153                arenas_map = arenas[ind];
3154        else {
3155                malloc_spin_lock(&arenas_lock);
3156                if (arenas[ind] != NULL)
3157                        arenas_map = arenas[ind];
3158                else
3159                        arenas_map = arenas_extend(ind);
3160                malloc_spin_unlock(&arenas_lock);
3161        }
3162}
3163#endif
3164
3165#ifdef MALLOC_MAG
3166static inline void *
3167mag_alloc(mag_t *mag)
3168{
3169
3170        if (mag->nrounds == 0)
3171                return (NULL);
3172        mag->nrounds--;
3173
3174        return (mag->rounds[mag->nrounds]);
3175}
3176
3177static void
3178mag_load(mag_t *mag)
3179{
3180        arena_t *arena;
3181        arena_bin_t *bin;
3182        arena_run_t *run;
3183        void *round;
3184        size_t i;
3185
3186        arena = choose_arena();
3187        bin = &arena->bins[mag->binind];
3188#ifdef MALLOC_BALANCE
3189        arena_lock_balance(arena);
3190#else
3191        malloc_spin_lock(&arena->lock);
3192#endif
3193        for (i = mag->nrounds; i < max_rounds; i++) {
3194                if ((run = bin->runcur) != NULL && run->nfree > 0)
3195                        round = arena_bin_malloc_easy(arena, bin, run);
3196                else
3197                        round = arena_bin_malloc_hard(arena, bin);
3198                if (round == NULL)
3199                        break;
3200                mag->rounds[i] = round;
3201        }
3202#ifdef MALLOC_STATS
3203        bin->stats.nmags++;
3204        arena->stats.nmalloc_small += (i - mag->nrounds);
3205        arena->stats.allocated_small += (i - mag->nrounds) * bin->reg_size;
3206#endif
3207        malloc_spin_unlock(&arena->lock);
3208        mag->nrounds = i;
3209}
3210
3211static inline void *
3212mag_rack_alloc(mag_rack_t *rack, size_t size, bool zero)
3213{
3214        void *ret;
3215        bin_mags_t *bin_mags;
3216        mag_t *mag;
3217        size_t binind;
3218
3219        binind = size2bin[size];
3220        assert(binind < nbins);
3221        bin_mags = &rack->bin_mags[binind];
3222
3223        mag = bin_mags->curmag;
3224        if (mag == NULL) {
3225                /* Create an initial magazine for this size class. */
3226                assert(bin_mags->sparemag == NULL);
3227                mag = mag_create(choose_arena(), binind);
3228                if (mag == NULL)
3229                        return (NULL);
3230                bin_mags->curmag = mag;
3231                mag_load(mag);
3232        }
3233
3234        ret = mag_alloc(mag);
3235        if (ret == NULL) {
3236                if (bin_mags->sparemag != NULL) {
3237                        if (bin_mags->sparemag->nrounds > 0) {
3238                                /* Swap magazines. */
3239                                bin_mags->curmag = bin_mags->sparemag;
3240                                bin_mags->sparemag = mag;
3241                                mag = bin_mags->curmag;
3242                        } else {
3243                                /* Reload the current magazine. */
3244                                mag_load(mag);
3245                        }
3246                } else {
3247                        /* Create a second magazine. */
3248                        mag = mag_create(choose_arena(), binind);
3249                        if (mag == NULL)
3250                                return (NULL);
3251                        mag_load(mag);
3252                        bin_mags->sparemag = bin_mags->curmag;
3253                        bin_mags->curmag = mag;
3254                }
3255                ret = mag_alloc(mag);
3256                if (ret == NULL)
3257                        return (NULL);
3258        }
3259
3260        if (zero == false) {
3261                if (opt_junk)
3262                        memset(ret, 0xa5, size);
3263                else if (opt_zero)
3264                        memset(ret, 0, size);
3265        } else
3266                memset(ret, 0, size);
3267
3268        return (ret);
3269}
3270#endif
3271
3272static inline void *
3273arena_malloc_small(arena_t *arena, size_t size, bool zero)
3274{
3275        void *ret;
3276        arena_bin_t *bin;
3277        arena_run_t *run;
3278        size_t binind;
3279
3280        binind = size2bin[size];
3281        assert(binind < nbins);
3282        bin = &arena->bins[binind];
3283        size = bin->reg_size;
3284
3285#ifdef MALLOC_BALANCE
3286        arena_lock_balance(arena);
3287#else
3288        malloc_spin_lock(&arena->lock);
3289#endif
3290        if ((run = bin->runcur) != NULL && run->nfree > 0)
3291                ret = arena_bin_malloc_easy(arena, bin, run);
3292        else
3293                ret = arena_bin_malloc_hard(arena, bin);
3294
3295        if (ret == NULL) {
3296                malloc_spin_unlock(&arena->lock);
3297                return (NULL);
3298        }
3299
3300#ifdef MALLOC_STATS
3301        bin->stats.nrequests++;
3302        arena->stats.nmalloc_small++;
3303        arena->stats.allocated_small += size;
3304#endif
3305        malloc_spin_unlock(&arena->lock);
3306
3307        if (zero == false) {
3308                if (opt_junk)
3309                        memset(ret, 0xa5, size);
3310                else if (opt_zero)
3311                        memset(ret, 0, size);
3312        } else
3313                memset(ret, 0, size);
3314
3315        return (ret);
3316}
3317
3318static void *
3319arena_malloc_large(arena_t *arena, size_t size, bool zero)
3320{
3321        void *ret;
3322
3323        /* Large allocation. */
3324        size = PAGE_CEILING(size);
3325#ifdef MALLOC_BALANCE
3326        arena_lock_balance(arena);
3327#else
3328        malloc_spin_lock(&arena->lock);
3329#endif
3330        ret = (void *)arena_run_alloc(arena, size, true, zero);
3331        if (ret == NULL) {
3332                malloc_spin_unlock(&arena->lock);
3333                return (NULL);
3334        }
3335#ifdef MALLOC_STATS
3336        arena->stats.nmalloc_large++;
3337        arena->stats.allocated_large += size;
3338#endif
3339        malloc_spin_unlock(&arena->lock);
3340
3341        if (zero == false) {
3342                if (opt_junk)
3343                        memset(ret, 0xa5, size);
3344                else if (opt_zero)
3345                        memset(ret, 0, size);
3346        }
3347
3348        return (ret);
3349}
3350
3351static inline void *
3352arena_malloc(arena_t *arena, size_t size, bool zero)
3353{
3354
3355        assert(arena != NULL);
3356        assert(arena->magic == ARENA_MAGIC);
3357        assert(size != 0);
3358        assert(QUANTUM_CEILING(size) <= arena_maxclass);
3359
3360        if (size <= bin_maxclass) {
3361#ifdef MALLOC_MAG
3362                if (__isthreaded && opt_mag) {
3363                        mag_rack_t *rack = mag_rack;
3364                        if (rack == NULL) {
3365                                rack = mag_rack_create(arena);
3366                                if (rack == NULL)
3367                                        return (NULL);
3368                                mag_rack = rack;
3369                        }
3370                        return (mag_rack_alloc(rack, size, zero));
3371                } else
3372#endif
3373                        return (arena_malloc_small(arena, size, zero));
3374        } else
3375                return (arena_malloc_large(arena, size, zero));
3376}
3377
3378static inline void *
3379imalloc(size_t size)
3380{
3381
3382        assert(size != 0);
3383
3384        if (size <= arena_maxclass)
3385                return (arena_malloc(choose_arena(), size, false));
3386        else
3387                return (huge_malloc(size, false));
3388}
3389
3390static inline void *
3391icalloc(size_t size)
3392{
3393
3394        if (size <= arena_maxclass)
3395                return (arena_malloc(choose_arena(), size, true));
3396        else
3397                return (huge_malloc(size, true));
3398}
3399
3400/* Only handles large allocations that require more than page alignment. */
3401static void *
3402arena_palloc(arena_t *arena, size_t alignment, size_t size, size_t alloc_size)
3403{
3404        void *ret;
3405        size_t offset;
3406        arena_chunk_t *chunk;
3407
3408        assert((size & pagesize_mask) == 0);
3409        assert((alignment & pagesize_mask) == 0);
3410
3411#ifdef MALLOC_BALANCE
3412        arena_lock_balance(arena);
3413#else
3414        malloc_spin_lock(&arena->lock);
3415#endif
3416        ret = (void *)arena_run_alloc(arena, alloc_size, true, false);
3417        if (ret == NULL) {
3418                malloc_spin_unlock(&arena->lock);
3419                return (NULL);
3420        }
3421
3422        chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ret);
3423
3424        offset = (uintptr_t)ret & (alignment - 1);
3425        assert((offset & pagesize_mask) == 0);
3426        assert(offset < alloc_size);
3427        if (offset == 0)
3428                arena_run_trim_tail(arena, chunk, ret, alloc_size, size, false);
3429        else {
3430                size_t leadsize, trailsize;
3431
3432                leadsize = alignment - offset;
3433                if (leadsize > 0) {
3434                        arena_run_trim_head(arena, chunk, ret, alloc_size,
3435                            alloc_size - leadsize);
3436                        ret = (void *)((uintptr_t)ret + leadsize);
3437                }
3438
3439                trailsize = alloc_size - leadsize - size;
3440                if (trailsize != 0) {
3441                        /* Trim trailing space. */
3442                        assert(trailsize < alloc_size);
3443                        arena_run_trim_tail(arena, chunk, ret, size + trailsize,
3444                            size, false);
3445                }
3446        }
3447
3448#ifdef MALLOC_STATS
3449        arena->stats.nmalloc_large++;
3450        arena->stats.allocated_large += size;
3451#endif
3452        malloc_spin_unlock(&arena->lock);
3453
3454        if (opt_junk)
3455                memset(ret, 0xa5, size);
3456        else if (opt_zero)
3457                memset(ret, 0, size);
3458        return (ret);
3459}
3460
3461static inline void *
3462ipalloc(size_t alignment, size_t size)
3463{
3464        void *ret;
3465        size_t ceil_size;
3466
3467        /*
3468         * Round size up to the nearest multiple of alignment.
3469         *
3470         * This done, we can take advantage of the fact that for each small
3471         * size class, every object is aligned at the smallest power of two
3472         * that is non-zero in the base two representation of the size.  For
3473         * example:
3474         *
3475         *   Size |   Base 2 | Minimum alignment
3476         *   -----+----------+------------------
3477         *     96 |  1100000 |  32
3478         *    144 | 10100000 |  32
3479         *    192 | 11000000 |  64
3480         *
3481         * Depending on runtime settings, it is possible that arena_malloc()
3482         * will further round up to a power of two, but that never causes
3483         * correctness issues.
3484         */
3485        ceil_size = (size + (alignment - 1)) & (-alignment);
3486        /*
3487         * (ceil_size < size) protects against the combination of maximal
3488         * alignment and size greater than maximal alignment.
3489         */
3490        if (ceil_size < size) {
3491                /* size_t overflow. */
3492                return (NULL);
3493        }
3494
3495        if (ceil_size <= pagesize || (alignment <= pagesize
3496            && ceil_size <= arena_maxclass))
3497                ret = arena_malloc(choose_arena(), ceil_size, false);
3498        else {
3499                size_t run_size;
3500
3501                /*
3502                 * We can't achieve subpage alignment, so round up alignment
3503                 * permanently; it makes later calculations simpler.
3504                 */
3505                alignment = PAGE_CEILING(alignment);
3506                ceil_size = PAGE_CEILING(size);
3507                /*
3508                 * (ceil_size < size) protects against very large sizes within
3509                 * pagesize of SIZE_T_MAX.
3510                 *
3511                 * (ceil_size + alignment < ceil_size) protects against the
3512                 * combination of maximal alignment and ceil_size large enough
3513                 * to cause overflow.  This is similar to the first overflow
3514                 * check above, but it needs to be repeated due to the new
3515                 * ceil_size value, which may now be *equal* to maximal
3516                 * alignment, whereas before we only detected overflow if the
3517                 * original size was *greater* than maximal alignment.
3518                 */
3519                if (ceil_size < size || ceil_size + alignment < ceil_size) {
3520                        /* size_t overflow. */
3521                        return (NULL);
3522                }
3523
3524                /*
3525                 * Calculate the size of the over-size run that arena_palloc()
3526                 * would need to allocate in order to guarantee the alignment.
3527                 */
3528                if (ceil_size >= alignment)
3529                        run_size = ceil_size + alignment - pagesize;
3530                else {
3531                        /*
3532                         * It is possible that (alignment << 1) will cause
3533                         * overflow, but it doesn't matter because we also
3534                         * subtract pagesize, which in the case of overflow
3535                         * leaves us with a very large run_size.  That causes
3536                         * the first conditional below to fail, which means
3537                         * that the bogus run_size value never gets used for
3538                         * anything important.
3539                         */
3540                        run_size = (alignment << 1) - pagesize;
3541                }
3542
3543                if (run_size <= arena_maxclass) {
3544                        ret = arena_palloc(choose_arena(), alignment, ceil_size,
3545                            run_size);
3546                } else if (alignment <= chunksize)
3547                        ret = huge_malloc(ceil_size, false);
3548                else
3549                        ret = huge_palloc(alignment, ceil_size);
3550        }
3551
3552        assert(((uintptr_t)ret & (alignment - 1)) == 0);
3553        return (ret);
3554}
3555
3556/* Return the size of the allocation pointed to by ptr. */
3557static size_t
3558arena_salloc(const void *ptr)
3559{
3560        size_t ret;
3561        arena_chunk_t *chunk;
3562        size_t pageind, mapbits;
3563
3564        assert(ptr != NULL);
3565        assert(CHUNK_ADDR2BASE(ptr) != ptr);
3566
3567        chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
3568        pageind = (((uintptr_t)ptr - (uintptr_t)chunk) >> pagesize_2pow);
3569        mapbits = chunk->map[pageind].bits;
3570        assert((mapbits & CHUNK_MAP_ALLOCATED) != 0);
3571        if ((mapbits & CHUNK_MAP_LARGE) == 0) {
3572                arena_run_t *run = (arena_run_t *)(mapbits & ~pagesize_mask);
3573                assert(run->magic == ARENA_RUN_MAGIC);
3574                ret = run->bin->reg_size;
3575        } else {
3576                ret = mapbits & ~pagesize_mask;
3577                assert(ret != 0);
3578        }
3579
3580        return (ret);
3581}
3582
3583static inline size_t
3584isalloc(const void *ptr)
3585{
3586        size_t ret;
3587        arena_chunk_t *chunk;
3588
3589        assert(ptr != NULL);
3590
3591        chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
3592        if (chunk != ptr) {
3593                /* Region. */
3594                assert(chunk->arena->magic == ARENA_MAGIC);
3595
3596                ret = arena_salloc(ptr);
3597        } else {
3598                extent_node_t *node, key;
3599
3600                /* Chunk (huge allocation). */
3601
3602                malloc_mutex_lock(&huge_mtx);
3603
3604                /* Extract from tree of huge allocations. */
3605                key.addr = __DECONST(void *, ptr);
3606                node = extent_tree_ad_search(&huge, &key);
3607                assert(node != NULL);
3608
3609                ret = node->size;
3610
3611                malloc_mutex_unlock(&huge_mtx);
3612        }
3613
3614        return (ret);
3615}
3616
3617static inline void
3618arena_dalloc_small(arena_t *arena, arena_chunk_t *chunk, void *ptr,
3619    arena_chunk_map_t *mapelm)
3620{
3621        arena_run_t *run;
3622        arena_bin_t *bin;
3623        size_t size;
3624
3625        run = (arena_run_t *)(mapelm->bits & ~pagesize_mask);
3626        assert(run->magic == ARENA_RUN_MAGIC);
3627        bin = run->bin;
3628        size = bin->reg_size;
3629
3630        if (opt_junk)
3631                memset(ptr, 0x5a, size);
3632
3633        arena_run_reg_dalloc(run, bin, ptr, size);
3634        run->nfree++;
3635
3636        if (run->nfree == bin->nregs) {
3637                /* Deallocate run. */
3638                if (run == bin->runcur)
3639                        bin->runcur = NULL;
3640                else if (bin->nregs != 1) {
3641                        size_t run_pageind = (((uintptr_t)run -
3642                            (uintptr_t)chunk)) >> pagesize_2pow;
3643                        arena_chunk_map_t *run_mapelm =
3644                            &chunk->map[run_pageind];
3645                        /*
3646                         * This block's conditional is necessary because if the
3647                         * run only contains one region, then it never gets
3648                         * inserted into the non-full runs tree.
3649                         */
3650                        arena_run_tree_remove(&bin->runs, run_mapelm);
3651                }
3652#ifdef MALLOC_DEBUG
3653                run->magic = 0;
3654#endif
3655                arena_run_dalloc(arena, run, true);
3656#ifdef MALLOC_STATS
3657                bin->stats.curruns--;
3658#endif
3659        } else if (run->nfree == 1 && run != bin->runcur) {
3660                /*
3661                 * Make sure that bin->runcur always refers to the lowest
3662                 * non-full run, if one exists.
3663                 */
3664                if (bin->runcur == NULL)
3665                        bin->runcur = run;
3666                else if ((uintptr_t)run < (uintptr_t)bin->runcur) {
3667                        /* Switch runcur. */
3668                        if (bin->runcur->nfree > 0) {
3669                                arena_chunk_t *runcur_chunk =
3670                                    CHUNK_ADDR2BASE(bin->runcur);
3671                                size_t runcur_pageind =
3672                                    (((uintptr_t)bin->runcur -
3673                                    (uintptr_t)runcur_chunk)) >> pagesize_2pow;
3674                                arena_chunk_map_t *runcur_mapelm =
3675                                    &runcur_chunk->map[runcur_pageind];
3676
3677                                /* Insert runcur. */
3678                                arena_run_tree_insert(&bin->runs,
3679                                    runcur_mapelm);
3680                        }
3681                        bin->runcur = run;
3682                } else {
3683                        size_t run_pageind = (((uintptr_t)run -
3684                            (uintptr_t)chunk)) >> pagesize_2pow;
3685                        arena_chunk_map_t *run_mapelm =
3686                            &chunk->map[run_pageind];
3687
3688                        assert(arena_run_tree_search(&bin->runs, run_mapelm) ==
3689                            NULL);
3690                        arena_run_tree_insert(&bin->runs, run_mapelm);
3691                }
3692        }
3693#ifdef MALLOC_STATS
3694        arena->stats.allocated_small -= size;
3695        arena->stats.ndalloc_small++;
3696#endif
3697}
3698
3699#ifdef MALLOC_MAG
3700static void
3701mag_unload(mag_t *mag)
3702{
3703        arena_chunk_t *chunk;
3704        arena_t *arena;
3705        void *round;
3706        size_t i, ndeferred, nrounds;
3707
3708        for (ndeferred = mag->nrounds; ndeferred > 0;) {
3709                nrounds = ndeferred;
3710                /* Lock the arena associated with the first round. */
3711                chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(mag->rounds[0]);
3712                arena = chunk->arena;
3713#ifdef MALLOC_BALANCE
3714                arena_lock_balance(arena);
3715#else
3716                malloc_spin_lock(&arena->lock);
3717#endif
3718                /* Deallocate every round that belongs to the locked arena. */
3719                for (i = ndeferred = 0; i < nrounds; i++) {
3720                        round = mag->rounds[i];
3721                        chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(round);
3722                        if (chunk->arena == arena) {
3723                                size_t pageind = (((uintptr_t)round -
3724                                    (uintptr_t)chunk) >> pagesize_2pow);
3725                                arena_chunk_map_t *mapelm =
3726                                    &chunk->map[pageind];
3727                                arena_dalloc_small(arena, chunk, round, mapelm);
3728                        } else {
3729                                /*
3730                                 * This round was allocated via a different
3731                                 * arena than the one that is currently locked.
3732                                 * Stash the round, so that it can be handled
3733                                 * in a future pass.
3734                                 */
3735                                mag->rounds[ndeferred] = round;
3736                                ndeferred++;
3737                        }
3738                }
3739                malloc_spin_unlock(&arena->lock);
3740        }
3741
3742        mag->nrounds = 0;
3743}
3744
3745static inline void
3746mag_rack_dalloc(mag_rack_t *rack, void *ptr)
3747{
3748        arena_t *arena;
3749        arena_chunk_t *chunk;
3750        arena_run_t *run;
3751        arena_bin_t *bin;
3752        bin_mags_t *bin_mags;
3753        mag_t *mag;
3754        size_t pageind, binind;
3755        arena_chunk_map_t *mapelm;
3756
3757        chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
3758        arena = chunk->arena;
3759        pageind = (((uintptr_t)ptr - (uintptr_t)chunk) >> pagesize_2pow);
3760        mapelm = &chunk->map[pageind];
3761        run = (arena_run_t *)(mapelm->bits & ~pagesize_mask);
3762        assert(run->magic == ARENA_RUN_MAGIC);
3763        bin = run->bin;
3764        binind = ((uintptr_t)bin - (uintptr_t)&arena->bins) /
3765            sizeof(arena_bin_t);
3766        assert(binind < nbins);
3767
3768        if (opt_junk)
3769                memset(ptr, 0x5a, arena->bins[binind].reg_size);
3770
3771        bin_mags = &rack->bin_mags[binind];
3772        mag = bin_mags->curmag;
3773        if (mag == NULL) {
3774                /* Create an initial magazine for this size class. */
3775                assert(bin_mags->sparemag == NULL);
3776                mag = mag_create(choose_arena(), binind);
3777                if (mag == NULL) {
3778                        malloc_spin_lock(&arena->lock);
3779                        arena_dalloc_small(arena, chunk, ptr, mapelm);
3780                        malloc_spin_unlock(&arena->lock);
3781                        return;
3782                }
3783                bin_mags->curmag = mag;
3784        }
3785
3786        if (mag->nrounds == max_rounds) {
3787                if (bin_mags->sparemag != NULL) {
3788                        if (bin_mags->sparemag->nrounds < max_rounds) {
3789                                /* Swap magazines. */
3790                                bin_mags->curmag = bin_mags->sparemag;
3791                                bin_mags->sparemag = mag;
3792                                mag = bin_mags->curmag;
3793                        } else {
3794                                /* Unload the current magazine. */
3795                                mag_unload(mag);
3796                        }
3797                } else {
3798                        /* Create a second magazine. */
3799                        mag = mag_create(choose_arena(), binind);
3800                        if (mag == NULL) {
3801                                mag = rack->bin_mags[binind].curmag;
3802                                mag_unload(mag);
3803                        } else {
3804                                bin_mags->sparemag = bin_mags->curmag;
3805                                bin_mags->curmag = mag;
3806                        }
3807                }
3808                assert(mag->nrounds < max_rounds);
3809        }
3810        mag->rounds[mag->nrounds] = ptr;
3811        mag->nrounds++;
3812}
3813#endif
3814
3815static void
3816arena_dalloc_large(arena_t *arena, arena_chunk_t *chunk, void *ptr)
3817{
3818        /* Large allocation. */
3819        malloc_spin_lock(&arena->lock);
3820
3821#ifndef MALLOC_STATS
3822        if (opt_junk)
3823#endif
3824        {
3825                size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >>
3826                    pagesize_2pow;
3827                size_t size = chunk->map[pageind].bits & ~pagesize_mask;
3828
3829#ifdef MALLOC_STATS
3830                if (opt_junk)
3831#endif
3832                        memset(ptr, 0x5a, size);
3833#ifdef MALLOC_STATS
3834                arena->stats.allocated_large -= size;
3835#endif
3836        }
3837#ifdef MALLOC_STATS
3838        arena->stats.ndalloc_large++;
3839#endif
3840
3841        arena_run_dalloc(arena, (arena_run_t *)ptr, true);
3842        malloc_spin_unlock(&arena->lock);
3843}
3844
3845static inline void
3846arena_dalloc(arena_t *arena, arena_chunk_t *chunk, void *ptr)
3847{
3848        size_t pageind;
3849        arena_chunk_map_t *mapelm;
3850
3851        assert(arena != NULL);
3852        assert(arena->magic == ARENA_MAGIC);
3853        assert(chunk->arena == arena);
3854        assert(ptr != NULL);
3855        assert(CHUNK_ADDR2BASE(ptr) != ptr);
3856
3857        pageind = (((uintptr_t)ptr - (uintptr_t)chunk) >> pagesize_2pow);
3858        mapelm = &chunk->map[pageind];
3859        assert((mapelm->bits & CHUNK_MAP_ALLOCATED) != 0);
3860        if ((mapelm->bits & CHUNK_MAP_LARGE) == 0) {
3861                /* Small allocation. */
3862#ifdef MALLOC_MAG
3863                if (__isthreaded && opt_mag) {
3864                        mag_rack_t *rack = mag_rack;
3865                        if (rack == NULL) {
3866                                rack = mag_rack_create(arena);
3867                                if (rack == NULL) {
3868                                        malloc_spin_lock(&arena->lock);
3869                                        arena_dalloc_small(arena, chunk, ptr,
3870                                            mapelm);
3871                                        malloc_spin_unlock(&arena->lock);
3872                                }
3873                                mag_rack = rack;
3874                        }
3875                        mag_rack_dalloc(rack, ptr);
3876                } else {
3877#endif
3878                        malloc_spin_lock(&arena->lock);
3879                        arena_dalloc_small(arena, chunk, ptr, mapelm);
3880                        malloc_spin_unlock(&arena->lock);
3881#ifdef MALLOC_MAG
3882                }
3883#endif
3884        } else
3885                arena_dalloc_large(arena, chunk, ptr);
3886}
3887
3888static inline void
3889idalloc(void *ptr)
3890{
3891        arena_chunk_t *chunk;
3892
3893        assert(ptr != NULL);
3894
3895        chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
3896        if (chunk != ptr)
3897                arena_dalloc(chunk->arena, chunk, ptr);
3898        else
3899                huge_dalloc(ptr);
3900}
3901
3902static void
3903arena_ralloc_large_shrink(arena_t *arena, arena_chunk_t *chunk, void *ptr,
3904    size_t size, size_t oldsize)
3905{
3906
3907        assert(size < oldsize);
3908
3909        /*
3910         * Shrink the run, and make trailing pages available for other
3911         * allocations.
3912         */
3913#ifdef MALLOC_BALANCE
3914        arena_lock_balance(arena);
3915#else
3916        malloc_spin_lock(&arena->lock);
3917#endif
3918        arena_run_trim_tail(arena, chunk, (arena_run_t *)ptr, oldsize, size,
3919            true);
3920#ifdef MALLOC_STATS
3921        arena->stats.allocated_large -= oldsize - size;
3922#endif
3923        malloc_spin_unlock(&arena->lock);
3924}
3925
3926static bool
3927arena_ralloc_large_grow(arena_t *arena, arena_chunk_t *chunk, void *ptr,
3928    size_t size, size_t oldsize)
3929{
3930        size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> pagesize_2pow;
3931        size_t npages = oldsize >> pagesize_2pow;
3932
3933        assert(oldsize == (chunk->map[pageind].bits & ~pagesize_mask));
3934
3935        /* Try to extend the run. */
3936        assert(size > oldsize);
3937#ifdef MALLOC_BALANCE
3938        arena_lock_balance(arena);
3939#else
3940        malloc_spin_lock(&arena->lock);
3941#endif
3942        if (pageind + npages < chunk_npages && (chunk->map[pageind+npages].bits
3943            & CHUNK_MAP_ALLOCATED) == 0 && (chunk->map[pageind+npages].bits &
3944            ~pagesize_mask) >= size - oldsize) {
3945                /*
3946                 * The next run is available and sufficiently large.  Split the
3947                 * following run, then merge the first part with the existing
3948                 * allocation.
3949                 */
3950                arena_run_split(arena, (arena_run_t *)((uintptr_t)chunk +
3951                    ((pageind+npages) << pagesize_2pow)), size - oldsize, true,
3952                    false);
3953
3954                chunk->map[pageind].bits = size | CHUNK_MAP_LARGE |
3955                    CHUNK_MAP_ALLOCATED;
3956                chunk->map[pageind+npages].bits = CHUNK_MAP_LARGE |
3957                    CHUNK_MAP_ALLOCATED;
3958
3959#ifdef MALLOC_STATS
3960                arena->stats.allocated_large += size - oldsize;
3961#endif
3962                malloc_spin_unlock(&arena->lock);
3963                return (false);
3964        }
3965        malloc_spin_unlock(&arena->lock);
3966
3967        return (true);
3968}
3969
3970/*
3971 * Try to resize a large allocation, in order to avoid copying.  This will
3972 * always fail if growing an object, and the following run is already in use.
3973 */
3974static bool
3975arena_ralloc_large(void *ptr, size_t size, size_t oldsize)
3976{
3977        size_t psize;
3978
3979        psize = PAGE_CEILING(size);
3980        if (psize == oldsize) {
3981                /* Same size class. */
3982                if (opt_junk && size < oldsize) {
3983                        memset((void *)((uintptr_t)ptr + size), 0x5a, oldsize -
3984                            size);
3985                }
3986                return (false);
3987        } else {
3988                arena_chunk_t *chunk;
3989                arena_t *arena;
3990
3991                chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
3992                arena = chunk->arena;
3993                assert(arena->magic == ARENA_MAGIC);
3994
3995                if (psize < oldsize) {
3996                        /* Fill before shrinking in order avoid a race. */
3997                        if (opt_junk) {
3998                                memset((void *)((uintptr_t)ptr + size), 0x5a,
3999                                    oldsize - size);
4000                        }
4001                        arena_ralloc_large_shrink(arena, chunk, ptr, psize,
4002                            oldsize);
4003                        return (false);
4004                } else {
4005                        bool ret = arena_ralloc_large_grow(arena, chunk, ptr,
4006                            psize, oldsize);
4007                        if (ret == false && opt_zero) {
4008                                memset((void *)((uintptr_t)ptr + oldsize), 0,
4009                                    size - oldsize);
4010                        }
4011                        return (ret);
4012                }
4013        }
4014}
4015
4016static void *
4017arena_ralloc(void *ptr, size_t size, size_t oldsize)
4018{
4019        void *ret;
4020        size_t copysize;
4021
4022        /* Try to avoid moving the allocation. */
4023        if (size <= bin_maxclass) {
4024                if (oldsize <= bin_maxclass && size2bin[size] ==
4025                    size2bin[oldsize])
4026                        goto IN_PLACE;
4027        } else {
4028                if (oldsize > bin_maxclass && oldsize <= arena_maxclass) {
4029                        assert(size > bin_maxclass);
4030                        if (arena_ralloc_large(ptr, size, oldsize) == false)
4031                                return (ptr);
4032                }
4033        }
4034
4035        /*
4036         * If we get here, then size and oldsize are different enough that we
4037         * need to move the object.  In that case, fall back to allocating new
4038         * space and copying.
4039         */
4040        ret = arena_malloc(choose_arena(), size, false);
4041        if (ret == NULL)
4042                return (NULL);
4043
4044        /* Junk/zero-filling were already done by arena_malloc(). */
4045        copysize = (size < oldsize) ? size : oldsize;
4046        memcpy(ret, ptr, copysize);
4047        idalloc(ptr);
4048        return (ret);
4049IN_PLACE:
4050        if (opt_junk && size < oldsize)
4051                memset((void *)((uintptr_t)ptr + size), 0x5a, oldsize - size);
4052        else if (opt_zero && size > oldsize)
4053                memset((void *)((uintptr_t)ptr + oldsize), 0, size - oldsize);
4054        return (ptr);
4055}
4056
4057static inline void *
4058iralloc(void *ptr, size_t size)
4059{
4060        size_t oldsize;
4061
4062        assert(ptr != NULL);
4063        assert(size != 0);
4064
4065        oldsize = isalloc(ptr);
4066
4067        if (size <= arena_maxclass)
4068                return (arena_ralloc(ptr, size, oldsize));
4069        else
4070                return (huge_ralloc(ptr, size, oldsize));
4071}
4072
4073static bool
4074arena_new(arena_t *arena)
4075{
4076        unsigned i;
4077        arena_bin_t *bin;
4078        size_t prev_run_size;
4079
4080        if (malloc_spin_init(&arena->lock))
4081                return (true);
4082
4083#ifdef MALLOC_STATS
4084        memset(&arena->stats, 0, sizeof(arena_stats_t));
4085#endif
4086
4087        /* Initialize chunks. */
4088        arena_chunk_tree_dirty_new(&arena->chunks_dirty);
4089        arena->spare = NULL;
4090
4091        arena->ndirty = 0;
4092
4093        arena_avail_tree_new(&arena->runs_avail);
4094
4095#ifdef MALLOC_BALANCE
4096        arena->contention = 0;
4097#endif
4098
4099        /* Initialize bins. */
4100        prev_run_size = pagesize;
4101
4102        i = 0;
4103#ifdef MALLOC_TINY
4104        /* (2^n)-spaced tiny bins. */
4105        for (; i < ntbins; i++) {
4106                bin = &arena->bins[i];
4107                bin->runcur = NULL;
4108                arena_run_tree_new(&bin->runs);
4109
4110                bin->reg_size = (1U << (TINY_MIN_2POW + i));
4111
4112                prev_run_size = arena_bin_run_size_calc(bin, prev_run_size);
4113
4114#ifdef MALLOC_STATS
4115                memset(&bin->stats, 0, sizeof(malloc_bin_stats_t));
4116#endif
4117        }
4118#endif
4119
4120        /* Quantum-spaced bins. */
4121        for (; i < ntbins + nqbins; i++) {
4122                bin = &arena->bins[i];
4123                bin->runcur = NULL;
4124                arena_run_tree_new(&bin->runs);
4125
4126                bin->reg_size = (i - ntbins + 1) << QUANTUM_2POW;
4127
4128                prev_run_size = arena_bin_run_size_calc(bin, prev_run_size);
4129
4130#ifdef MALLOC_STATS
4131                memset(&bin->stats, 0, sizeof(malloc_bin_stats_t));
4132#endif
4133        }
4134
4135        /* Cacheline-spaced bins. */
4136        for (; i < ntbins + nqbins + ncbins; i++) {
4137                bin = &arena->bins[i];
4138                bin->runcur = NULL;
4139                arena_run_tree_new(&bin->runs);
4140
4141                bin->reg_size = cspace_min + ((i - (ntbins + nqbins)) <<
4142                    CACHELINE_2POW);
4143
4144                prev_run_size = arena_bin_run_size_calc(bin, prev_run_size);
4145
4146#ifdef MALLOC_STATS
4147                memset(&bin->stats, 0, sizeof(malloc_bin_stats_t));
4148#endif
4149        }
4150
4151        /* Subpage-spaced bins. */
4152        for (; i < nbins; i++) {
4153                bin = &arena->bins[i];
4154                bin->runcur = NULL;
4155                arena_run_tree_new(&bin->runs);
4156
4157                bin->reg_size = sspace_min + ((i - (ntbins + nqbins + ncbins))
4158                    << SUBPAGE_2POW);
4159
4160                prev_run_size = arena_bin_run_size_calc(bin, prev_run_size);
4161
4162#ifdef MALLOC_STATS
4163                memset(&bin->stats, 0, sizeof(malloc_bin_stats_t));
4164#endif
4165        }
4166
4167#ifdef MALLOC_DEBUG
4168        arena->magic = ARENA_MAGIC;
4169#endif
4170
4171        return (false);
4172}
4173
4174/* Create a new arena and insert it into the arenas array at index ind. */
4175static arena_t *
4176arenas_extend(unsigned ind)
4177{
4178        arena_t *ret;
4179
4180        /* Allocate enough space for trailing bins. */
4181        ret = (arena_t *)base_alloc(sizeof(arena_t)
4182            + (sizeof(arena_bin_t) * (nbins - 1)));
4183        if (ret != NULL && arena_new(ret) == false) {
4184                arenas[ind] = ret;
4185                return (ret);
4186        }
4187        /* Only reached if there is an OOM error. */
4188
4189        /*
4190         * OOM here is quite inconvenient to propagate, since dealing with it
4191         * would require a check for failure in the fast path.  Instead, punt
4192         * by using arenas[0].  In practice, this is an extremely unlikely
4193         * failure.
4194         */
4195        _malloc_message(_getprogname(),
4196            ": (malloc) Error initializing arena\n", "", "");
4197        if (opt_abort)
4198                abort();
4199
4200        return (arenas[0]);
4201}
4202
4203#ifdef MALLOC_MAG
4204static mag_t *
4205mag_create(arena_t *arena, size_t binind)
4206{
4207        mag_t *ret;
4208
4209        if (sizeof(mag_t) + (sizeof(void *) * (max_rounds - 1)) <=
4210            bin_maxclass) {
4211                ret = arena_malloc_small(arena, sizeof(mag_t) + (sizeof(void *)
4212                    * (max_rounds - 1)), false);
4213        } else {
4214                ret = imalloc(sizeof(mag_t) + (sizeof(void *) * (max_rounds -
4215                    1)));
4216        }
4217        if (ret == NULL)
4218                return (NULL);
4219        ret->binind = binind;
4220        ret->nrounds = 0;
4221
4222        return (ret);
4223}
4224
4225static void
4226mag_destroy(mag_t *mag)
4227{
4228        arena_t *arena;
4229        arena_chunk_t *chunk;
4230        size_t pageind;
4231        arena_chunk_map_t *mapelm;
4232
4233        chunk = CHUNK_ADDR2BASE(mag);
4234        arena = chunk->arena;
4235        pageind = (((uintptr_t)mag - (uintptr_t)chunk) >> pagesize_2pow);
4236        mapelm = &chunk->map[pageind];
4237
4238        assert(mag->nrounds == 0);
4239        if (sizeof(mag_t) + (sizeof(void *) * (max_rounds - 1)) <=
4240            bin_maxclass) {
4241                malloc_spin_lock(&arena->lock);
4242                arena_dalloc_small(arena, chunk, mag, mapelm);
4243                malloc_spin_unlock(&arena->lock);
4244        } else
4245                idalloc(mag);
4246}
4247
4248static mag_rack_t *
4249mag_rack_create(arena_t *arena)
4250{
4251
4252        assert(sizeof(mag_rack_t) + (sizeof(bin_mags_t *) * (nbins - 1)) <=
4253            bin_maxclass);
4254        return (arena_malloc_small(arena, sizeof(mag_rack_t) +
4255            (sizeof(bin_mags_t) * (nbins - 1)), true));
4256}
4257
4258static void
4259mag_rack_destroy(mag_rack_t *rack)
4260{
4261        arena_t *arena;
4262        arena_chunk_t *chunk;
4263        bin_mags_t *bin_mags;
4264        size_t i, pageind;
4265        arena_chunk_map_t *mapelm;
4266
4267        for (i = 0; i < nbins; i++) {
4268                bin_mags = &rack->bin_mags[i];
4269                if (bin_mags->curmag != NULL) {
4270                        assert(bin_mags->curmag->binind == i);
4271                        mag_unload(bin_mags->curmag);
4272                        mag_destroy(bin_mags->curmag);
4273                }
4274                if (bin_mags->sparemag != NULL) {
4275                        assert(bin_mags->sparemag->binind == i);
4276                        mag_unload(bin_mags->sparemag);
4277                        mag_destroy(bin_mags->sparemag);
4278                }
4279        }
4280
4281        chunk = CHUNK_ADDR2BASE(rack);
4282        arena = chunk->arena;
4283        pageind = (((uintptr_t)rack - (uintptr_t)chunk) >> pagesize_2pow);
4284        mapelm = &chunk->map[pageind];
4285
4286        malloc_spin_lock(&arena->lock);
4287        arena_dalloc_small(arena, chunk, rack, mapelm);
4288        malloc_spin_unlock(&arena->lock);
4289}
4290#endif
4291
4292/*
4293 * End arena.
4294 */
4295/******************************************************************************/
4296/*
4297 * Begin general internal functions.
4298 */
4299
4300static void *
4301huge_malloc(size_t size, bool zero)
4302{
4303        void *ret;
4304        size_t csize;
4305        extent_node_t *node;
4306
4307        /* Allocate one or more contiguous chunks for this request. */
4308
4309        csize = CHUNK_CEILING(size);
4310        if (csize == 0) {
4311                /* size is large enough to cause size_t wrap-around. */
4312                return (NULL);
4313        }
4314
4315        /* Allocate an extent node with which to track the chunk. */
4316        node = base_node_alloc();
4317        if (node == NULL)
4318                return (NULL);
4319
4320        ret = chunk_alloc(csize, zero);
4321        if (ret == NULL) {
4322                base_node_dealloc(node);
4323                return (NULL);
4324        }
4325
4326        /* Insert node into huge. */
4327        node->addr = ret;
4328        node->size = csize;
4329
4330        malloc_mutex_lock(&huge_mtx);
4331        extent_tree_ad_insert(&huge, node);
4332#ifdef MALLOC_STATS
4333        huge_nmalloc++;
4334        huge_allocated += csize;
4335#endif
4336        malloc_mutex_unlock(&huge_mtx);
4337
4338        if (zero == false) {
4339                if (opt_junk)
4340                        memset(ret, 0xa5, csize);
4341                else if (opt_zero)
4342                        memset(ret, 0, csize);
4343        }
4344
4345        return (ret);
4346}
4347
4348/* Only handles large allocations that require more than chunk alignment. */
4349static void *
4350huge_palloc(size_t alignment, size_t size)
4351{
4352        void *ret;
4353        size_t alloc_size, chunk_size, offset;
4354        extent_node_t *node;
4355
4356        /*
4357         * This allocation requires alignment that is even larger than chunk
4358         * alignment.  This means that huge_malloc() isn't good enough.
4359         *
4360         * Allocate almost twice as many chunks as are demanded by the size or
4361         * alignment, in order to assure the alignment can be achieved, then
4362         * unmap leading and trailing chunks.
4363         */
4364        assert(alignment >= chunksize);
4365
4366        chunk_size = CHUNK_CEILING(size);
4367
4368        if (size >= alignment)
4369                alloc_size = chunk_size + alignment - chunksize;
4370        else
4371                alloc_size = (alignment << 1) - chunksize;
4372
4373        /* Allocate an extent node with which to track the chunk. */
4374        node = base_node_alloc();
4375        if (node == NULL)
4376                return (NULL);
4377
4378        ret = chunk_alloc(alloc_size, false);
4379        if (ret == NULL) {
4380                base_node_dealloc(node);
4381                return (NULL);
4382        }
4383
4384        offset = (uintptr_t)ret & (alignment - 1);
4385        assert((offset & chunksize_mask) == 0);
4386        assert(offset < alloc_size);
4387        if (offset == 0) {
4388                /* Trim trailing space. */
4389                chunk_dealloc((void *)((uintptr_t)ret + chunk_size), alloc_size
4390                    - chunk_size);
4391        } else {
4392                size_t trailsize;
4393
4394                /* Trim leading space. */
4395                chunk_dealloc(ret, alignment - offset);
4396
4397                ret = (void *)((uintptr_t)ret + (alignment - offset));
4398
4399                trailsize = alloc_size - (alignment - offset) - chunk_size;
4400                if (trailsize != 0) {
4401                    /* Trim trailing space. */
4402                    assert(trailsize < alloc_size);
4403                    chunk_dealloc((void *)((uintptr_t)ret + chunk_size),
4404                        trailsize);
4405                }
4406        }
4407
4408        /* Insert node into huge. */
4409        node->addr = ret;
4410        node->size = chunk_size;
4411
4412        malloc_mutex_lock(&huge_mtx);
4413        extent_tree_ad_insert(&huge, node);
4414#ifdef MALLOC_STATS
4415        huge_nmalloc++;
4416        huge_allocated += chunk_size;
4417#endif
4418        malloc_mutex_unlock(&huge_mtx);
4419
4420        if (opt_junk)
4421                memset(ret, 0xa5, chunk_size);
4422        else if (opt_zero)
4423                memset(ret, 0, chunk_size);
4424
4425        return (ret);
4426}
4427
4428static void *
4429huge_ralloc(void *ptr, size_t size, size_t oldsize)
4430{
4431        void *ret;
4432        size_t copysize;
4433
4434        /* Avoid moving the allocation if the size class would not change. */
4435        if (oldsize > arena_maxclass &&
4436            CHUNK_CEILING(size) == CHUNK_CEILING(oldsize)) {
4437                if (opt_junk && size < oldsize) {
4438                        memset((void *)((uintptr_t)ptr + size), 0x5a, oldsize
4439                            - size);
4440                } else if (opt_zero && size > oldsize) {
4441                        memset((void *)((uintptr_t)ptr + oldsize), 0, size
4442                            - oldsize);
4443                }
4444                return (ptr);
4445        }
4446
4447        /*
4448         * If we get here, then size and oldsize are different enough that we
4449         * need to use a different size class.  In that case, fall back to
4450         * allocating new space and copying.
4451         */
4452        ret = huge_malloc(size, false);
4453        if (ret == NULL)
4454                return (NULL);
4455
4456        copysize = (size < oldsize) ? size : oldsize;
4457        memcpy(ret, ptr, copysize);
4458        idalloc(ptr);
4459        return (ret);
4460}
4461
4462static void
4463huge_dalloc(void *ptr)
4464{
4465        extent_node_t *node, key;
4466
4467        malloc_mutex_lock(&huge_mtx);
4468
4469        /* Extract from tree of huge allocations. */
4470        key.addr = ptr;
4471        node = extent_tree_ad_search(&huge, &key);
4472        assert(node != NULL);
4473        assert(node->addr == ptr);
4474        extent_tree_ad_remove(&huge, node);
4475
4476#ifdef MALLOC_STATS
4477        huge_ndalloc++;
4478        huge_allocated -= node->size;
4479#endif
4480
4481        malloc_mutex_unlock(&huge_mtx);
4482
4483        /* Unmap chunk. */
4484#ifdef MALLOC_DSS
4485        if (opt_dss && opt_junk)
4486                memset(node->addr, 0x5a, node->size);
4487#endif
4488        chunk_dealloc(node->addr, node->size);
4489
4490        base_node_dealloc(node);
4491}
4492
4493static void
4494malloc_print_stats(void)
4495{
4496
4497        if (opt_print_stats) {
4498                char s[UMAX2S_BUFSIZE];
4499                _malloc_message("___ Begin malloc statistics ___\n", "", "",
4500                    "");
4501                _malloc_message("Assertions ",
4502#ifdef NDEBUG
4503                    "disabled",
4504#else
4505                    "enabled",
4506#endif
4507                    "\n", "");
4508                _malloc_message("Boolean MALLOC_OPTIONS: ",
4509                    opt_abort ? "A" : "a", "", "");
4510#ifdef MALLOC_DSS
4511                _malloc_message(opt_dss ? "D" : "d", "", "", "");
4512#endif
4513#ifdef MALLOC_MAG
4514                _malloc_message(opt_mag ? "G" : "g", "", "", "");
4515#endif
4516                _malloc_message(opt_junk ? "J" : "j", "", "", "");
4517#ifdef MALLOC_DSS
4518                _malloc_message(opt_mmap ? "M" : "m", "", "", "");
4519#endif
4520                _malloc_message(opt_utrace ? "PU" : "Pu",
4521                    opt_sysv ? "V" : "v",
4522                    opt_xmalloc ? "X" : "x",
4523                    opt_zero ? "Z\n" : "z\n");
4524
4525                _malloc_message("CPUs: ", umax2s(ncpus, s), "\n", "");
4526                _malloc_message("Max arenas: ", umax2s(narenas, s), "\n", "");
4527#ifdef MALLOC_BALANCE
4528                _malloc_message("Arena balance threshold: ",
4529                    umax2s(opt_balance_threshold, s), "\n", "");
4530#endif
4531                _malloc_message("Pointer size: ", umax2s(sizeof(void *), s),
4532                    "\n", "");
4533                _malloc_message("Quantum size: ", umax2s(QUANTUM, s), "\n", "");
4534                _malloc_message("Cacheline size (assumed): ", umax2s(CACHELINE,
4535                    s), "\n", "");
4536#ifdef MALLOC_TINY
4537                _malloc_message("Tiny 2^n-spaced sizes: [", umax2s((1U <<
4538                    TINY_MIN_2POW), s), "..", "");
4539                _malloc_message(umax2s((qspace_min >> 1), s), "]\n", "", "");
4540#endif
4541                _malloc_message("Quantum-spaced sizes: [", umax2s(qspace_min,
4542                    s), "..", "");
4543                _malloc_message(umax2s(qspace_max, s), "]\n", "", "");
4544                _malloc_message("Cacheline-spaced sizes: [", umax2s(cspace_min,
4545                    s), "..", "");
4546                _malloc_message(umax2s(cspace_max, s), "]\n", "", "");
4547                _malloc_message("Subpage-spaced sizes: [", umax2s(sspace_min,
4548                    s), "..", "");
4549                _malloc_message(umax2s(sspace_max, s), "]\n", "", "");
4550#ifdef MALLOC_MAG
4551                _malloc_message("Rounds per magazine: ", umax2s(max_rounds, s),
4552                    "\n", "");
4553#endif
4554                _malloc_message("Max dirty pages per arena: ",
4555                    umax2s(opt_dirty_max, s), "\n", "");
4556
4557                _malloc_message("Chunk size: ", umax2s(chunksize, s), "", "");
4558                _malloc_message(" (2^", umax2s(opt_chunk_2pow, s), ")\n", "");
4559
4560#ifdef MALLOC_STATS
4561                {
4562                        size_t allocated, mapped;
4563#ifdef MALLOC_BALANCE
4564                        uint64_t nbalance = 0;
4565#endif
4566                        unsigned i;
4567                        arena_t *arena;
4568
4569                        /* Calculate and print allocated/mapped stats. */
4570
4571                        /* arenas. */
4572                        for (i = 0, allocated = 0; i < narenas; i++) {
4573                                if (arenas[i] != NULL) {
4574                                        malloc_spin_lock(&arenas[i]->lock);
4575                                        allocated +=
4576                                            arenas[i]->stats.allocated_small;
4577                                        allocated +=
4578                                            arenas[i]->stats.allocated_large;
4579#ifdef MALLOC_BALANCE
4580                                        nbalance += arenas[i]->stats.nbalance;
4581#endif
4582                                        malloc_spin_unlock(&arenas[i]->lock);
4583                                }
4584                        }
4585
4586                        /* huge/base. */
4587                        malloc_mutex_lock(&huge_mtx);
4588                        allocated += huge_allocated;
4589                        mapped = stats_chunks.curchunks * chunksize;
4590                        malloc_mutex_unlock(&huge_mtx);
4591
4592                        malloc_mutex_lock(&base_mtx);
4593                        mapped += base_mapped;
4594                        malloc_mutex_unlock(&base_mtx);
4595
4596                        malloc_printf("Allocated: %zu, mapped: %zu\n",
4597                            allocated, mapped);
4598
4599#ifdef MALLOC_BALANCE
4600                        malloc_printf("Arena balance reassignments: %llu\n",
4601                            nbalance);
4602#endif
4603
4604                        /* Print chunk stats. */
4605                        {
4606                                chunk_stats_t chunks_stats;
4607
4608                                malloc_mutex_lock(&huge_mtx);
4609                                chunks_stats = stats_chunks;
4610                                malloc_mutex_unlock(&huge_mtx);
4611
4612                                malloc_printf("chunks: nchunks   "
4613                                    "highchunks    curchunks\n");
4614                                malloc_printf("  %13llu%13lu%13lu\n",
4615                                    chunks_stats.nchunks,
4616                                    chunks_stats.highchunks,
4617                                    chunks_stats.curchunks);
4618                        }
4619
4620                        /* Print chunk stats. */
4621                        malloc_printf(
4622                            "huge: nmalloc      ndalloc    allocated\n");
4623                        malloc_printf(" %12llu %12llu %12zu\n",
4624                            huge_nmalloc, huge_ndalloc, huge_allocated);
4625
4626                        /* Print stats for each arena. */
4627                        for (i = 0; i < narenas; i++) {
4628                                arena = arenas[i];
4629                                if (arena != NULL) {
4630                                        malloc_printf(
4631                                            "\narenas[%u]:\n", i);
4632                                        malloc_spin_lock(&arena->lock);
4633                                        stats_print(arena);
4634                                        malloc_spin_unlock(&arena->lock);
4635                                }
4636                        }
4637                }
4638#endif /* #ifdef MALLOC_STATS */
4639                _malloc_message("--- End malloc statistics ---\n", "", "", "");
4640        }
4641}
4642
4643#ifdef MALLOC_DEBUG
4644static void
4645size2bin_validate(void)
4646{
4647        size_t i, size, binind;
4648
4649        assert(size2bin[0] == 0xffU);
4650        i = 1;
4651#  ifdef MALLOC_TINY
4652        /* Tiny. */
4653        for (; i < (1U << TINY_MIN_2POW); i++) {
4654                size = pow2_ceil(1U << TINY_MIN_2POW);
4655                binind = ffs((int)(size >> (TINY_MIN_2POW + 1)));
4656                assert(size2bin[i] == binind);
4657        }
4658        for (; i < qspace_min; i++) {
4659                size = pow2_ceil(i);
4660                binind = ffs((int)(size >> (TINY_MIN_2POW + 1)));
4661                assert(size2bin[i] == binind);
4662        }
4663#  endif
4664        /* Quantum-spaced. */
4665        for (; i <= qspace_max; i++) {
4666                size = QUANTUM_CEILING(i);
4667                binind = ntbins + (size >> QUANTUM_2POW) - 1;
4668                assert(size2bin[i] == binind);
4669        }
4670        /* Cacheline-spaced. */
4671        for (; i <= cspace_max; i++) {
4672                size = CACHELINE_CEILING(i);
4673                binind = ntbins + nqbins + ((size - cspace_min) >>
4674                    CACHELINE_2POW);
4675                assert(size2bin[i] == binind);
4676        }
4677        /* Sub-page. */
4678        for (; i <= sspace_max; i++) {
4679                size = SUBPAGE_CEILING(i);
4680                binind = ntbins + nqbins + ncbins + ((size - sspace_min)
4681                    >> SUBPAGE_2POW);
4682                assert(size2bin[i] == binind);
4683        }
4684}
4685#endif
4686
4687static bool
4688size2bin_init(void)
4689{
4690
4691        if (opt_qspace_max_2pow != QSPACE_MAX_2POW_DEFAULT
4692            || opt_cspace_max_2pow != CSPACE_MAX_2POW_DEFAULT)
4693                return (size2bin_init_hard());
4694
4695        size2bin = const_size2bin;
4696#ifdef MALLOC_DEBUG
4697        assert(sizeof(const_size2bin) == bin_maxclass + 1);
4698        size2bin_validate();
4699#endif
4700        return (false);
4701}
4702
4703static bool
4704size2bin_init_hard(void)
4705{
4706        size_t i, size, binind;
4707        uint8_t *custom_size2bin;
4708
4709        assert(opt_qspace_max_2pow != QSPACE_MAX_2POW_DEFAULT
4710            || opt_cspace_max_2pow != CSPACE_MAX_2POW_DEFAULT);
4711
4712        custom_size2bin = (uint8_t *)base_alloc(bin_maxclass + 1);
4713        if (custom_size2bin == NULL)
4714                return (true);
4715
4716        custom_size2bin[0] = 0xffU;
4717        i = 1;
4718#ifdef MALLOC_TINY
4719        /* Tiny. */
4720        for (; i < (1U << TINY_MIN_2POW); i++) {
4721                size = pow2_ceil(1U << TINY_MIN_2POW);
4722                binind = ffs((int)(size >> (TINY_MIN_2POW + 1)));
4723                custom_size2bin[i] = binind;
4724        }
4725        for (; i < qspace_min; i++) {
4726                size = pow2_ceil(i);
4727                binind = ffs((int)(size >> (TINY_MIN_2POW + 1)));
4728                custom_size2bin[i] = binind;
4729        }
4730#endif
4731        /* Quantum-spaced. */
4732        for (; i <= qspace_max; i++) {
4733                size = QUANTUM_CEILING(i);
4734                binind = ntbins + (size >> QUANTUM_2POW) - 1;
4735                custom_size2bin[i] = binind;
4736        }
4737        /* Cacheline-spaced. */
4738        for (; i <= cspace_max; i++) {
4739                size = CACHELINE_CEILING(i);
4740                binind = ntbins + nqbins + ((size - cspace_min) >>
4741                    CACHELINE_2POW);
4742                custom_size2bin[i] = binind;
4743        }
4744        /* Sub-page. */
4745        for (; i <= sspace_max; i++) {
4746                size = SUBPAGE_CEILING(i);
4747                binind = ntbins + nqbins + ncbins + ((size - sspace_min) >>
4748                    SUBPAGE_2POW);
4749                custom_size2bin[i] = binind;
4750        }
4751
4752        size2bin = custom_size2bin;
4753#ifdef MALLOC_DEBUG
4754        size2bin_validate();
4755#endif
4756        return (false);
4757}
4758
4759/*
4760 * FreeBSD's pthreads implementation calls malloc(3), so the malloc
4761 * implementation has to take pains to avoid infinite recursion during
4762 * initialization.
4763 */
4764static inline bool
4765malloc_init(void)
4766{
4767
4768        if (malloc_initialized == false)
4769                return (malloc_init_hard());
4770
4771        return (false);
4772}
4773
4774static bool
4775malloc_init_hard(void)
4776{
4777        unsigned i;
4778        int linklen;
4779        char buf[PATH_MAX + 1];
4780        const char *opts;
4781
4782        malloc_mutex_lock(&init_lock);
4783        if (malloc_initialized) {
4784                /*
4785                 * Another thread initialized the allocator before this one
4786                 * acquired init_lock.
4787                 */
4788                malloc_mutex_unlock(&init_lock);
4789                return (false);
4790        }
4791
4792        /* Get number of CPUs. */
4793        {
4794                int mib[2];
4795                size_t len;
4796
4797                mib[0] = CTL_HW;
4798                mib[1] = HW_NCPU;
4799                len = sizeof(ncpus);
4800                if (sysctl(mib, 2, &ncpus, &len, (void *) 0, 0) == -1) {
4801                        /* Error. */
4802                        ncpus = 1;
4803                }
4804        }
4805
4806        /* Get page size. */
4807        {
4808                long result;
4809
4810                result = sysconf(_SC_PAGESIZE);
4811                assert(result != -1);
4812                pagesize = (unsigned)result;
4813
4814                /*
4815                 * We assume that pagesize is a power of 2 when calculating
4816                 * pagesize_mask and pagesize_2pow.
4817                 */
4818                assert(((result - 1) & result) == 0);
4819                pagesize_mask = result - 1;
4820                pagesize_2pow = ffs((int)result) - 1;
4821        }
4822
4823        for (i = 0; i < 3; i++) {
4824                unsigned j;
4825
4826                /* Get runtime configuration. */
4827                switch (i) {
4828                case 0:
4829                        if ((linklen = readlink("/etc/malloc.conf", buf,
4830                                                sizeof(buf) - 1)) != -1) {
4831                                /*
4832                                 * Use the contents of the "/etc/malloc.conf"
4833                                 * symbolic link's name.
4834                                 */
4835                                buf[linklen] = '\0';
4836                                opts = buf;
4837                        } else {
4838                                /* No configuration specified. */
4839                                buf[0] = '\0';
4840                                opts = buf;
4841                        }
4842                        break;
4843                case 1:
4844                        if (issetugid() == 0 && (opts =
4845                            getenv("MALLOC_OPTIONS")) != NULL) {
4846                                /*
4847                                 * Do nothing; opts is already initialized to
4848                                 * the value of the MALLOC_OPTIONS environment
4849                                 * variable.
4850                                 */
4851                        } else {
4852                                /* No configuration specified. */
4853                                buf[0] = '\0';
4854                                opts = buf;
4855                        }
4856                        break;
4857                case 2:
4858                        if (_malloc_options != NULL) {
4859                                /*
4860                                 * Use options that were compiled into the
4861                                 * program.
4862                                 */
4863                                opts = _malloc_options;
4864                        } else {
4865                                /* No configuration specified. */
4866                                buf[0] = '\0';
4867                                opts = buf;
4868                        }
4869                        break;
4870                default:
4871                        /* NOTREACHED */
4872                        assert(false);
4873                }
4874
4875                for (j = 0; opts[j] != '\0'; j++) {
4876                        unsigned k, nreps;
4877                        bool nseen;
4878
4879                        /* Parse repetition count, if any. */
4880                        for (nreps = 0, nseen = false;; j++, nseen = true) {
4881                                switch (opts[j]) {
4882                                        case '0': case '1': case '2': case '3':
4883                                        case '4': case '5': case '6': case '7':
4884                                        case '8': case '9':
4885                                                nreps *= 10;
4886                                                nreps += opts[j] - '0';
4887                                                break;
4888                                        default:
4889                                                goto MALLOC_OUT;
4890                                }
4891                        }
4892MALLOC_OUT:
4893                        if (nseen == false)
4894                                nreps = 1;
4895
4896                        for (k = 0; k < nreps; k++) {
4897                                switch (opts[j]) {
4898                                case 'a':
4899                                        opt_abort = false;
4900                                        break;
4901                                case 'A':
4902                                        opt_abort = true;
4903                                        break;
4904                                case 'b':
4905#ifdef MALLOC_BALANCE
4906                                        opt_balance_threshold >>= 1;
4907#endif
4908                                        break;
4909                                case 'B':
4910#ifdef MALLOC_BALANCE
4911                                        if (opt_balance_threshold == 0)
4912                                                opt_balance_threshold = 1;
4913                                        else if ((opt_balance_threshold << 1)
4914                                            > opt_balance_threshold)
4915                                                opt_balance_threshold <<= 1;
4916#endif
4917                                        break;
4918                                case 'c':
4919                                        if (opt_cspace_max_2pow - 1 >
4920                                            opt_qspace_max_2pow &&
4921                                            opt_cspace_max_2pow >
4922                                            CACHELINE_2POW)
4923                                                opt_cspace_max_2pow--;
4924                                        break;
4925                                case 'C':
4926                                        if (opt_cspace_max_2pow < pagesize_2pow
4927                                            - 1)
4928                                                opt_cspace_max_2pow++;
4929                                        break;
4930                                case 'd':
4931#ifdef MALLOC_DSS
4932                                        opt_dss = false;
4933#endif
4934                                        break;
4935                                case 'D':
4936#ifdef MALLOC_DSS
4937                                        opt_dss = true;
4938#endif
4939                                        break;
4940                                case 'f':
4941                                        opt_dirty_max >>= 1;
4942                                        break;
4943                                case 'F':
4944                                        if (opt_dirty_max == 0)
4945                                                opt_dirty_max = 1;
4946                                        else if ((opt_dirty_max << 1) != 0)
4947                                                opt_dirty_max <<= 1;
4948                                        break;
4949#ifdef MALLOC_MAG
4950                                case 'g':
4951                                        opt_mag = false;
4952                                        break;
4953                                case 'G':
4954                                        opt_mag = true;
4955                                        break;
4956#endif
4957                                case 'j':
4958                                        opt_junk = false;
4959                                        break;
4960                                case 'J':
4961                                        opt_junk = true;
4962                                        break;
4963                                case 'k':
4964                                        /*
4965                                         * Chunks always require at least one
4966                                         * header page, so chunks can never be
4967                                         * smaller than two pages.
4968                                         */
4969                                        if (opt_chunk_2pow > pagesize_2pow + 1)
4970                                                opt_chunk_2pow--;
4971                                        break;
4972                                case 'K':
4973                                        if (opt_chunk_2pow + 1 <
4974                                            (sizeof(size_t) << 3))
4975                                                opt_chunk_2pow++;
4976                                        break;
4977                                case 'm':
4978#ifdef MALLOC_DSS
4979                                        opt_mmap = false;
4980#endif
4981                                        break;
4982                                case 'M':
4983#ifdef MALLOC_DSS
4984                                        opt_mmap = true;
4985#endif
4986                                        break;
4987                                case 'n':
4988                                        opt_narenas_lshift--;
4989                                        break;
4990                                case 'N':
4991                                        opt_narenas_lshift++;
4992                                        break;
4993                                case 'p':
4994                                        opt_print_stats = false;
4995                                        break;
4996                                case 'P':
4997                                        opt_print_stats = true;
4998                                        break;
4999                                case 'q':
5000                                        if (opt_qspace_max_2pow > QUANTUM_2POW)
5001                                                opt_qspace_max_2pow--;
5002                                        break;
5003                                case 'Q':
5004                                        if (opt_qspace_max_2pow + 1 <
5005                                            opt_cspace_max_2pow)
5006                                                opt_qspace_max_2pow++;
5007                                        break;
5008#ifdef MALLOC_MAG
5009                                case 'R':
5010                                        if (opt_mag_size_2pow + 1 < (8U <<
5011                                            SIZEOF_PTR_2POW))
5012                                                opt_mag_size_2pow++;
5013                                        break;
5014                                case 'r':
5015                                        /*
5016                                         * Make sure there's always at least
5017                                         * one round per magazine.
5018                                         */
5019                                        if ((1U << (opt_mag_size_2pow-1)) >=
5020                                            sizeof(mag_t))
5021                                                opt_mag_size_2pow--;
5022                                        break;
5023#endif
5024                                case 'u':
5025                                        opt_utrace = false;
5026                                        break;
5027                                case 'U':
5028                                        opt_utrace = true;
5029                                        break;
5030                                case 'v':
5031                                        opt_sysv = false;
5032                                        break;
5033                                case 'V':
5034                                        opt_sysv = true;
5035                                        break;
5036                                case 'x':
5037                                        opt_xmalloc = false;
5038                                        break;
5039                                case 'X':
5040                                        opt_xmalloc = true;
5041                                        break;
5042                                case 'z':
5043                                        opt_zero = false;
5044                                        break;
5045                                case 'Z':
5046                                        opt_zero = true;
5047                                        break;
5048                                default: {
5049                                        char cbuf[2];
5050
5051                                        cbuf[0] = opts[j];
5052                                        cbuf[1] = '\0';
5053                                        _malloc_message(_getprogname(),
5054                                            ": (malloc) Unsupported character "
5055                                            "in malloc options: '", cbuf,
5056                                            "'\n");
5057                                }
5058                                }
5059                        }
5060                }
5061        }
5062
5063#ifdef MALLOC_DSS
5064        /* Make sure that there is some method for acquiring memory. */
5065        if (opt_dss == false && opt_mmap == false)
5066                opt_mmap = true;
5067#endif
5068
5069        /* Take care to call atexit() only once. */
5070        if (opt_print_stats) {
5071                /* Print statistics at exit. */
5072                atexit(malloc_print_stats);
5073        }
5074
5075#ifdef MALLOC_MAG
5076        /*
5077         * Calculate the actual number of rounds per magazine, taking into
5078         * account header overhead.
5079         */
5080        max_rounds = (1LLU << (opt_mag_size_2pow - SIZEOF_PTR_2POW)) -
5081            (sizeof(mag_t) >> SIZEOF_PTR_2POW) + 1;
5082#endif
5083
5084        /* Set variables according to the value of opt_[qc]space_max_2pow. */
5085        qspace_max = (1U << opt_qspace_max_2pow);
5086        cspace_min = CACHELINE_CEILING(qspace_max);
5087        if (cspace_min == qspace_max)
5088                cspace_min += CACHELINE;
5089        cspace_max = (1U << opt_cspace_max_2pow);
5090        sspace_min = SUBPAGE_CEILING(cspace_max);
5091        if (sspace_min == cspace_max)
5092                sspace_min += SUBPAGE;
5093        assert(sspace_min < pagesize);
5094        sspace_max = pagesize - SUBPAGE;
5095
5096#ifdef MALLOC_TINY
5097        assert(QUANTUM_2POW >= TINY_MIN_2POW);
5098#endif
5099        assert(ntbins <= QUANTUM_2POW);
5100        nqbins = qspace_max >> QUANTUM_2POW;
5101        ncbins = ((cspace_max - cspace_min) >> CACHELINE_2POW) + 1;
5102        nsbins = ((sspace_max - sspace_min) >> SUBPAGE_2POW) + 1;
5103        nbins = ntbins + nqbins + ncbins + nsbins;
5104
5105        if (size2bin_init()) {
5106                malloc_mutex_unlock(&init_lock);
5107                return (true);
5108        }
5109
5110        /* Set variables according to the value of opt_chunk_2pow. */
5111        chunksize = (1LU << opt_chunk_2pow);
5112        chunksize_mask = chunksize - 1;
5113        chunk_npages = (chunksize >> pagesize_2pow);
5114        {
5115                size_t header_size;
5116
5117                /*
5118                 * Compute the header size such that it is large enough to
5119                 * contain the page map.
5120                 */
5121                header_size = sizeof(arena_chunk_t) +
5122                    (sizeof(arena_chunk_map_t) * (chunk_npages - 1));
5123                arena_chunk_header_npages = (header_size >> pagesize_2pow) +
5124                    ((header_size & pagesize_mask) != 0);
5125        }
5126        arena_maxclass = chunksize - (arena_chunk_header_npages <<
5127            pagesize_2pow);
5128
5129        UTRACE(0, 0, 0);
5130
5131#ifdef MALLOC_STATS
5132        memset(&stats_chunks, 0, sizeof(chunk_stats_t));
5133#endif
5134
5135        /* Various sanity checks that regard configuration. */
5136        assert(chunksize >= pagesize);
5137
5138        /* Initialize chunks data. */
5139        malloc_mutex_init(&huge_mtx);
5140        extent_tree_ad_new(&huge);
5141#ifdef MALLOC_DSS
5142        malloc_mutex_init(&dss_mtx);
5143        dss_base = sbrk(0);
5144        dss_prev = dss_base;
5145        dss_max = dss_base;
5146        extent_tree_szad_new(&dss_chunks_szad);
5147        extent_tree_ad_new(&dss_chunks_ad);
5148#endif
5149#ifdef MALLOC_STATS
5150        huge_nmalloc = 0;
5151        huge_ndalloc = 0;
5152        huge_allocated = 0;
5153#endif
5154
5155        /* Initialize base allocation data structures. */
5156#ifdef MALLOC_STATS
5157        base_mapped = 0;
5158#endif
5159#ifdef MALLOC_DSS
5160        /*
5161         * Allocate a base chunk here, since it doesn't actually have to be
5162         * chunk-aligned.  Doing this before allocating any other chunks allows
5163         * the use of space that would otherwise be wasted.
5164         */
5165        if (opt_dss)
5166                base_pages_alloc(0);
5167#endif
5168        base_nodes = NULL;
5169        malloc_mutex_init(&base_mtx);
5170
5171        if (ncpus > 1) {
5172                /*
5173                 * For SMP systems, create twice as many arenas as there are
5174                 * CPUs by default.
5175                 */
5176                opt_narenas_lshift++;
5177        }
5178
5179        /* Determine how many arenas to use. */
5180        narenas = ncpus;
5181        if (opt_narenas_lshift > 0) {
5182                if ((narenas << opt_narenas_lshift) > narenas)
5183                        narenas <<= opt_narenas_lshift;
5184                /*
5185                 * Make sure not to exceed the limits of what base_alloc() can
5186                 * handle.
5187                 */
5188                if (narenas * sizeof(arena_t *) > chunksize)
5189                        narenas = chunksize / sizeof(arena_t *);
5190        } else if (opt_narenas_lshift < 0) {
5191                if ((narenas >> -opt_narenas_lshift) < narenas)
5192                        narenas >>= -opt_narenas_lshift;
5193                /* Make sure there is at least one arena. */
5194                if (narenas == 0)
5195                        narenas = 1;
5196        }
5197#ifdef MALLOC_BALANCE
5198        assert(narenas != 0);
5199        for (narenas_2pow = 0;
5200             (narenas >> (narenas_2pow + 1)) != 0;
5201             narenas_2pow++);
5202#endif
5203
5204#ifdef NO_TLS
5205        if (narenas > 1) {
5206                static const unsigned primes[] = {1, 3, 5, 7, 11, 13, 17, 19,
5207                    23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
5208                    89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149,
5209                    151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211,
5210                    223, 227, 229, 233, 239, 241, 251, 257, 263};
5211                unsigned nprimes, parenas;
5212
5213                /*
5214                 * Pick a prime number of hash arenas that is more than narenas
5215                 * so that direct hashing of pthread_self() pointers tends to
5216                 * spread allocations evenly among the arenas.
5217                 */
5218                assert((narenas & 1) == 0); /* narenas must be even. */
5219                nprimes = (sizeof(primes) >> SIZEOF_INT_2POW);
5220                parenas = primes[nprimes - 1]; /* In case not enough primes. */
5221                for (i = 1; i < nprimes; i++) {
5222                        if (primes[i] > narenas) {
5223                                parenas = primes[i];
5224                                break;
5225                        }
5226                }
5227                narenas = parenas;
5228        }
5229#endif
5230
5231#ifndef NO_TLS
5232#  ifndef MALLOC_BALANCE
5233        next_arena = 0;
5234#  endif
5235#endif
5236
5237        /* Allocate and initialize arenas. */
5238        arenas = (arena_t **)base_alloc(sizeof(arena_t *) * narenas);
5239        if (arenas == NULL) {
5240                malloc_mutex_unlock(&init_lock);
5241                return (true);
5242        }
5243        /*
5244         * Zero the array.  In practice, this should always be pre-zeroed,
5245         * since it was just mmap()ed, but let's be sure.
5246         */
5247        memset(arenas, 0, sizeof(arena_t *) * narenas);
5248
5249        /*
5250         * Initialize one arena here.  The rest are lazily created in
5251         * choose_arena_hard().
5252         */
5253        arenas_extend(0);
5254        if (arenas[0] == NULL) {
5255                malloc_mutex_unlock(&init_lock);
5256                return (true);
5257        }
5258#ifndef NO_TLS
5259        /*
5260         * Assign the initial arena to the initial thread, in order to avoid
5261         * spurious creation of an extra arena if the application switches to
5262         * threaded mode.
5263         */
5264        arenas_map = arenas[0];
5265#endif
5266        /*
5267         * Seed here for the initial thread, since choose_arena_hard() is only
5268         * called for other threads.  The seed value doesn't really matter.
5269         */
5270#ifdef MALLOC_BALANCE
5271        SPRN(balance, 42);
5272#endif
5273
5274        malloc_spin_init(&arenas_lock);
5275
5276        malloc_initialized = true;
5277        malloc_mutex_unlock(&init_lock);
5278        return (false);
5279}
5280
5281/*
5282 * End general internal functions.
5283 */
5284/******************************************************************************/
5285/*
5286 * Begin malloc(3)-compatible functions.
5287 */
5288
5289void *
5290malloc(size_t size)
5291{
5292        void *ret;
5293
5294        if (malloc_init()) {
5295                ret = NULL;
5296                goto RETURN;
5297        }
5298
5299        if (size == 0) {
5300                if (opt_sysv == false)
5301                        size = 1;
5302                else {
5303                        ret = NULL;
5304                        goto RETURN;
5305                }
5306        }
5307
5308        ret = imalloc(size);
5309
5310RETURN:
5311        if (ret == NULL) {
5312                if (opt_xmalloc) {
5313                        _malloc_message(_getprogname(),
5314                            ": (malloc) Error in malloc(): out of memory\n", "",
5315                            "");
5316                        abort();
5317                }
5318                errno = ENOMEM;
5319        }
5320
5321        UTRACE(0, size, ret);
5322        return (ret);
5323}
5324
5325int
5326posix_memalign(void **memptr, size_t alignment, size_t size)
5327{
5328        int ret;
5329        void *result;
5330
5331        if (malloc_init())
5332                result = NULL;
5333        else {
5334                /* Make sure that alignment is a large enough power of 2. */
5335                if (((alignment - 1) & alignment) != 0
5336                    || alignment < sizeof(void *)) {
5337                        if (opt_xmalloc) {
5338                                _malloc_message(_getprogname(),
5339                                    ": (malloc) Error in posix_memalign(): "
5340                                    "invalid alignment\n", "", "");
5341                                abort();
5342                        }
5343                        result = NULL;
5344                        ret = EINVAL;
5345                        goto RETURN;
5346                }
5347
5348                result = ipalloc(alignment, size);
5349        }
5350
5351        if (result == NULL) {
5352                if (opt_xmalloc) {
5353                        _malloc_message(_getprogname(),
5354                        ": (malloc) Error in posix_memalign(): out of memory\n",
5355                        "", "");
5356                        abort();
5357                }
5358                ret = ENOMEM;
5359                goto RETURN;
5360        }
5361
5362        *memptr = result;
5363        ret = 0;
5364
5365RETURN:
5366        UTRACE(0, size, result);
5367        return (ret);
5368}
5369
5370void *
5371calloc(size_t num, size_t size)
5372{
5373        void *ret;
5374        size_t num_size;
5375
5376        if (malloc_init()) {
5377                num_size = 0;
5378                ret = NULL;
5379                goto RETURN;
5380        }
5381
5382        num_size = num * size;
5383        if (num_size == 0) {
5384                if ((opt_sysv == false) && ((num == 0) || (size == 0)))
5385                        num_size = 1;
5386                else {
5387                        ret = NULL;
5388                        goto RETURN;
5389                }
5390        /*
5391         * Try to avoid division here.  We know that it isn't possible to
5392         * overflow during multiplication if neither operand uses any of the
5393         * most significant half of the bits in a size_t.
5394         */
5395        } else if (((num | size) & (SIZE_T_MAX << (sizeof(size_t) << 2)))
5396            && (num_size / size != num)) {
5397                /* size_t overflow. */
5398                ret = NULL;
5399                goto RETURN;
5400        }
5401
5402        ret = icalloc(num_size);
5403
5404RETURN:
5405        if (ret == NULL) {
5406                if (opt_xmalloc) {
5407                        _malloc_message(_getprogname(),
5408                            ": (malloc) Error in calloc(): out of memory\n", "",
5409                            "");
5410                        abort();
5411                }
5412                errno = ENOMEM;
5413        }
5414
5415        UTRACE(0, num_size, ret);
5416        return (ret);
5417}
5418
5419void *
5420realloc(void *ptr, size_t size)
5421{
5422        void *ret;
5423
5424        if (size == 0) {
5425                if (opt_sysv == false)
5426                        size = 1;
5427                else {
5428                        if (ptr != NULL)
5429                                idalloc(ptr);
5430                        ret = NULL;
5431                        goto RETURN;
5432                }
5433        }
5434
5435        if (ptr != NULL) {
5436                assert(malloc_initialized);
5437
5438                ret = iralloc(ptr, size);
5439
5440                if (ret == NULL) {
5441                        if (opt_xmalloc) {
5442                                _malloc_message(_getprogname(),
5443                                    ": (malloc) Error in realloc(): out of "
5444                                    "memory\n", "", "");
5445                                abort();
5446                        }
5447                        errno = ENOMEM;
5448                }
5449        } else {
5450                if (malloc_init())
5451                        ret = NULL;
5452                else
5453                        ret = imalloc(size);
5454
5455                if (ret == NULL) {
5456                        if (opt_xmalloc) {
5457                                _malloc_message(_getprogname(),
5458                                    ": (malloc) Error in realloc(): out of "
5459                                    "memory\n", "", "");
5460                                abort();
5461                        }
5462                        errno = ENOMEM;
5463                }
5464        }
5465
5466RETURN:
5467        UTRACE(ptr, size, ret);
5468        return (ret);
5469}
5470
5471void
5472free(void *ptr)
5473{
5474
5475        UTRACE(ptr, 0, 0);
5476        if (ptr != NULL) {
5477                assert(malloc_initialized);
5478
5479                idalloc(ptr);
5480        }
5481}
5482
5483/*
5484 * End malloc(3)-compatible functions.
5485 */
5486/******************************************************************************/
5487/*
5488 * Begin non-standard functions.
5489 */
5490
5491size_t
5492malloc_usable_size(const void *ptr)
5493{
5494
5495        assert(ptr != NULL);
5496
5497        return (isalloc(ptr));
5498}
5499
5500/*
5501 * End non-standard functions.
5502 */
5503/******************************************************************************/
5504/*
5505 * Begin library-private functions.
5506 */
5507
5508/******************************************************************************/
5509/*
5510 * Begin thread cache.
5511 */
5512
5513/*
5514 * We provide an unpublished interface in order to receive notifications from
5515 * the pthreads library whenever a thread exits.  This allows us to clean up
5516 * thread caches.
5517 */
5518void
5519_malloc_thread_cleanup(void)
5520{
5521
5522#ifdef MALLOC_MAG
5523        if (mag_rack != NULL) {
5524                assert(mag_rack != (void *)-1);
5525                mag_rack_destroy(mag_rack);
5526#ifdef MALLOC_DEBUG
5527                mag_rack = (void *)-1;
5528#endif
5529        }
5530#endif
5531}
5532
5533/*
5534 * The following functions are used by threading libraries for protection of
5535 * malloc during fork().  These functions are only called if the program is
5536 * running in threaded mode, so there is no need to check whether the program
5537 * is threaded here.
5538 */
5539
5540void
5541_malloc_prefork(void)
5542{
5543        unsigned i;
5544
5545        /* Acquire all mutexes in a safe order. */
5546
5547        malloc_spin_lock(&arenas_lock);
5548        for (i = 0; i < narenas; i++) {
5549                if (arenas[i] != NULL)
5550                        malloc_spin_lock(&arenas[i]->lock);
5551        }
5552        malloc_spin_unlock(&arenas_lock);
5553
5554        malloc_mutex_lock(&base_mtx);
5555
5556        malloc_mutex_lock(&huge_mtx);
5557
5558#ifdef MALLOC_DSS
5559        malloc_mutex_lock(&dss_mtx);
5560#endif
5561}
5562
5563void
5564_malloc_postfork(void)
5565{
5566        unsigned i;
5567
5568        /* Release all mutexes, now that fork() has completed. */
5569
5570#ifdef MALLOC_DSS
5571        malloc_mutex_unlock(&dss_mtx);
5572#endif
5573
5574        malloc_mutex_unlock(&huge_mtx);
5575
5576        malloc_mutex_unlock(&base_mtx);
5577
5578        malloc_spin_lock(&arenas_lock);
5579        for (i = 0; i < narenas; i++) {
5580                if (arenas[i] != NULL)
5581                        malloc_spin_unlock(&arenas[i]->lock);
5582        }
5583        malloc_spin_unlock(&arenas_lock);
5584}
5585
5586/*
5587 * End library-private functions.
5588 */
5589/******************************************************************************/
Note: See TracBrowser for help on using the repository browser.