• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /* -*- Mode: C; tab-width: 8; c-basic-offset: 8 -*- */
2 /* vim:set softtabstop=8 shiftwidth=8: */
3 /*-
4  * Copyright (C) 2006-2008 Jason Evans <jasone@FreeBSD.org>.
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  * 1. Redistributions of source code must retain the above copyright
11  *    notice(s), this list of conditions and the following disclaimer as
12  *    the first lines of this file unmodified other than the possible
13  *    addition of one or more copyright notices.
14  * 2. Redistributions in binary form must reproduce the above copyright
15  *    notice(s), this list of conditions and the following disclaimer in
16  *    the documentation and/or other materials provided with the
17  *    distribution.
18  *
19  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY
20  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE
23  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
26  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
27  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
28  * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
29  * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30  *
31  *******************************************************************************
32  *
33  * This allocator implementation is designed to provide scalable performance
34  * for multi-threaded programs on multi-processor systems.  The following
35  * features are included for this purpose:
36  *
37  *   + Multiple arenas are used if there are multiple CPUs, which reduces lock
38  *     contention and cache sloshing.
39  *
40  *   + Cache line sharing between arenas is avoided for internal data
41  *     structures.
42  *
43  *   + Memory is managed in chunks and runs (chunks can be split into runs),
44  *     rather than as individual pages.  This provides a constant-time
45  *     mechanism for associating allocations with particular arenas.
46  *
47  * Allocation requests are rounded up to the nearest size class, and no record
48  * of the original request size is maintained.  Allocations are broken into
49  * categories according to size class.  Assuming runtime defaults, 4 kB pages
50  * and a 16 byte quantum on a 32-bit system, the size classes in each category
51  * are as follows:
52  *
53  *   |=====================================|
54  *   | Category | Subcategory    |    Size |
55  *   |=====================================|
56  *   | Small    | Tiny           |       2 |
57  *   |          |                |       4 |
58  *   |          |                |       8 |
59  *   |          |----------------+---------|
60  *   |          | Quantum-spaced |      16 |
61  *   |          |                |      32 |
62  *   |          |                |      48 |
63  *   |          |                |     ... |
64  *   |          |                |     480 |
65  *   |          |                |     496 |
66  *   |          |                |     512 |
67  *   |          |----------------+---------|
68  *   |          | Sub-page       |    1 kB |
69  *   |          |                |    2 kB |
70  *   |=====================================|
71  *   | Large                     |    4 kB |
72  *   |                           |    8 kB |
73  *   |                           |   12 kB |
74  *   |                           |     ... |
75  *   |                           | 1012 kB |
76  *   |                           | 1016 kB |
77  *   |                           | 1020 kB |
78  *   |=====================================|
79  *   | Huge                      |    1 MB |
80  *   |                           |    2 MB |
81  *   |                           |    3 MB |
82  *   |                           |     ... |
83  *   |=====================================|
84  *
85  * A different mechanism is used for each category:
86  *
87  *   Small : Each size class is segregated into its own set of runs.  Each run
88  *           maintains a bitmap of which regions are free/allocated.
89  *
90  *   Large : Each allocation is backed by a dedicated run.  Metadata are stored
91  *           in the associated arena chunk header maps.
92  *
93  *   Huge : Each allocation is backed by a dedicated contiguous set of chunks.
94  *          Metadata are stored in a separate red-black tree.
95  *
96  *******************************************************************************
97  */
98 
99 /*
100  * NOTE(mbelshe): Added these defines to fit within chromium build system.
101  */
102 #define MOZ_MEMORY_WINDOWS
103 #define MOZ_MEMORY
104 #define DONT_OVERRIDE_LIBC
105 
106 /*
107  * MALLOC_PRODUCTION disables assertions and statistics gathering.  It also
108  * defaults the A and J runtime options to off.  These settings are appropriate
109  * for production systems.
110  */
111 #ifndef MOZ_MEMORY_DEBUG
112 #  define	MALLOC_PRODUCTION
113 #endif
114 
115 /*
116  * Use only one arena by default.  Mozilla does not currently make extensive
117  * use of concurrent allocation, so the increased fragmentation associated with
118  * multiple arenas is not warranted.
119  */
120 #define	MOZ_MEMORY_NARENAS_DEFAULT_ONE
121 
122 /*
123  * MALLOC_STATS enables statistics calculation, and is required for
124  * jemalloc_stats().
125  */
126 #define MALLOC_STATS
127 
128 #ifndef MALLOC_PRODUCTION
129    /*
130     * MALLOC_DEBUG enables assertions and other sanity checks, and disables
131     * inline functions.
132     */
133 #  define MALLOC_DEBUG
134 
135    /* Memory filling (junk/zero). */
136 #  define MALLOC_FILL
137 
138    /* Allocation tracing. */
139 #  ifndef MOZ_MEMORY_WINDOWS
140 #    define MALLOC_UTRACE
141 #  endif
142 
143    /* Support optional abort() on OOM. */
144 #  define MALLOC_XMALLOC
145 
146    /* Support SYSV semantics. */
147 #  define MALLOC_SYSV
148 #endif
149 
150 /*
151  * MALLOC_VALIDATE causes malloc_usable_size() to perform some pointer
152  * validation.  There are many possible errors that validation does not even
153  * attempt to detect.
154  */
155 #define MALLOC_VALIDATE
156 
157 /* Embed no-op macros that support memory allocation tracking via valgrind. */
158 #ifdef MOZ_VALGRIND
159 #  define MALLOC_VALGRIND
160 #endif
161 #ifdef MALLOC_VALGRIND
162 #  include <valgrind/valgrind.h>
163 #else
164 #  define VALGRIND_MALLOCLIKE_BLOCK(addr, sizeB, rzB, is_zeroed)
165 #  define VALGRIND_FREELIKE_BLOCK(addr, rzB)
166 #endif
167 
168 /*
169  * MALLOC_BALANCE enables monitoring of arena lock contention and dynamically
170  * re-balances arena load if exponentially averaged contention exceeds a
171  * certain threshold.
172  */
173 /* #define	MALLOC_BALANCE */
174 
175 #if (!defined(MOZ_MEMORY_WINDOWS) && !defined(MOZ_MEMORY_DARWIN))
176    /*
177     * MALLOC_PAGEFILE causes all mmap()ed memory to be backed by temporary
178     * files, so that if a chunk is mapped, it is guaranteed to be swappable.
179     * This avoids asynchronous OOM failures that are due to VM over-commit.
180     *
181     * XXX OS X over-commits, so we should probably use mmap() instead of
182     * vm_allocate(), so that MALLOC_PAGEFILE works.
183     */
184 #define MALLOC_PAGEFILE
185 #endif
186 
187 #ifdef MALLOC_PAGEFILE
188 /* Write size when initializing a page file. */
189 #  define MALLOC_PAGEFILE_WRITE_SIZE 512
190 #endif
191 
192 #ifdef MOZ_MEMORY_LINUX
193 #define	_GNU_SOURCE /* For mremap(2). */
194 #define	issetugid() 0
195 #if 0 /* Enable in order to test decommit code on Linux. */
196 #  define MALLOC_DECOMMIT
197 #endif
198 #endif
199 
200 #ifndef MOZ_MEMORY_WINCE
201 #include <sys/types.h>
202 
203 #include <errno.h>
204 #include <stdlib.h>
205 #endif
206 #include <limits.h>
207 #include <stdarg.h>
208 #include <stdio.h>
209 #include <string.h>
210 
211 #ifdef MOZ_MEMORY_WINDOWS
212 #ifndef MOZ_MEMORY_WINCE
213 //#include <cruntime.h>
214 //#include <internal.h>
215 #include <io.h>
216 #else
217 #include <cmnintrin.h>
218 #include <crtdefs.h>
219 #define SIZE_MAX UINT_MAX
220 #endif
221 #include <windows.h>
222 
223 #pragma warning( disable: 4267 4996 4146 )
224 
225 #define	false FALSE
226 #define	true TRUE
227 #define	inline __inline
228 #define	SIZE_T_MAX SIZE_MAX
229 #define	STDERR_FILENO 2
230 #define	PATH_MAX MAX_PATH
231 #define	vsnprintf _vsnprintf
232 
233 #ifndef NO_TLS
234 static unsigned long tlsIndex = 0xffffffff;
235 #endif
236 
237 #define	__thread
238 #ifdef MOZ_MEMORY_WINCE
239 #define	_pthread_self() GetCurrentThreadId()
240 #else
241 #define	_pthread_self() __threadid()
242 #endif
243 #define	issetugid() 0
244 
245 #ifndef MOZ_MEMORY_WINCE
246 /* use MSVC intrinsics */
247 #pragma intrinsic(_BitScanForward)
248 static __forceinline int
ffs(int x)249 ffs(int x)
250 {
251 	unsigned long i;
252 
253 	if (_BitScanForward(&i, x) != 0)
254 		return (i + 1);
255 
256 	return (0);
257 }
258 
259 /* Implement getenv without using malloc */
260 static char mozillaMallocOptionsBuf[64];
261 
262 #define	getenv xgetenv
263 static char *
getenv(const char * name)264 getenv(const char *name)
265 {
266 
267 	if (GetEnvironmentVariableA(name, (LPSTR)&mozillaMallocOptionsBuf,
268 		    sizeof(mozillaMallocOptionsBuf)) > 0)
269 		return (mozillaMallocOptionsBuf);
270 
271 	return (NULL);
272 }
273 
274 #else /* WIN CE */
275 
276 #define ENOMEM          12
277 #define EINVAL          22
278 
279 static __forceinline int
ffs(int x)280 ffs(int x)
281 {
282 
283 	return 32 - _CountLeadingZeros((-x) & x);
284 }
285 #endif
286 
287 typedef unsigned char uint8_t;
288 typedef unsigned uint32_t;
289 typedef unsigned long long uint64_t;
290 typedef unsigned long long uintmax_t;
291 typedef long ssize_t;
292 
293 #define	MALLOC_DECOMMIT
294 #endif
295 
296 #ifndef MOZ_MEMORY_WINDOWS
297 #ifndef MOZ_MEMORY_SOLARIS
298 #include <sys/cdefs.h>
299 #endif
300 #ifndef __DECONST
301 #  define __DECONST(type, var)	((type)(uintptr_t)(const void *)(var))
302 #endif
303 #ifndef MOZ_MEMORY
304 __FBSDID("$FreeBSD: head/lib/libc/stdlib/malloc.c 180599 2008-07-18 19:35:44Z jasone $");
305 #include "libc_private.h"
306 #ifdef MALLOC_DEBUG
307 #  define _LOCK_DEBUG
308 #endif
309 #include "spinlock.h"
310 #include "namespace.h"
311 #endif
312 #include <sys/mman.h>
313 #ifndef MADV_FREE
314 #  define MADV_FREE	MADV_DONTNEED
315 #endif
316 #ifndef MAP_NOSYNC
317 #  define MAP_NOSYNC	0
318 #endif
319 #include <sys/param.h>
320 #ifndef MOZ_MEMORY
321 #include <sys/stddef.h>
322 #endif
323 #include <sys/time.h>
324 #include <sys/types.h>
325 #ifndef MOZ_MEMORY_SOLARIS
326 #include <sys/sysctl.h>
327 #endif
328 #include <sys/uio.h>
329 #ifndef MOZ_MEMORY
330 #include <sys/ktrace.h> /* Must come after several other sys/ includes. */
331 
332 #include <machine/atomic.h>
333 #include <machine/cpufunc.h>
334 #include <machine/vmparam.h>
335 #endif
336 
337 #include <errno.h>
338 #include <limits.h>
339 #ifndef SIZE_T_MAX
340 #  define SIZE_T_MAX	SIZE_MAX
341 #endif
342 #include <pthread.h>
343 #ifdef MOZ_MEMORY_DARWIN
344 #define _pthread_self pthread_self
345 #define _pthread_mutex_init pthread_mutex_init
346 #define _pthread_mutex_trylock pthread_mutex_trylock
347 #define _pthread_mutex_lock pthread_mutex_lock
348 #define _pthread_mutex_unlock pthread_mutex_unlock
349 #endif
350 #include <sched.h>
351 #include <stdarg.h>
352 #include <stdbool.h>
353 #include <stdio.h>
354 #include <stdint.h>
355 #include <stdlib.h>
356 #include <string.h>
357 #ifndef MOZ_MEMORY_DARWIN
358 #include <strings.h>
359 #endif
360 #include <unistd.h>
361 
362 #ifdef MOZ_MEMORY_DARWIN
363 #include <libkern/OSAtomic.h>
364 #include <mach/mach_error.h>
365 #include <mach/mach_init.h>
366 #include <mach/vm_map.h>
367 #include <malloc/malloc.h>
368 #endif
369 
370 #ifndef MOZ_MEMORY
371 #include "un-namespace.h"
372 #endif
373 
374 #endif
375 
376 #include "jemalloc.h"
377 
378 #undef bool
379 #define bool jemalloc_bool
380 
381 #ifdef MOZ_MEMORY_DARWIN
382 static const bool __isthreaded = true;
383 #endif
384 
385 #if defined(MOZ_MEMORY_SOLARIS) && defined(MAP_ALIGN) && !defined(JEMALLOC_NEVER_USES_MAP_ALIGN)
386 #define JEMALLOC_USES_MAP_ALIGN	 /* Required on Solaris 10. Might improve performance elsewhere. */
387 #endif
388 
389 #if defined(MOZ_MEMORY_WINCE) && !defined(MOZ_MEMORY_WINCE6)
390 #define JEMALLOC_USES_MAP_ALIGN	 /* Required for Windows CE < 6 */
391 #endif
392 
393 #define __DECONST(type, var) ((type)(uintptr_t)(const void *)(var))
394 
395 #include "qr.h"
396 #include "ql.h"
397 #ifdef MOZ_MEMORY_WINDOWS
398    /* MSVC++ does not support C99 variable-length arrays. */
399 #  define RB_NO_C99_VARARRAYS
400 #endif
401 #include "rb.h"
402 
403 #ifdef MALLOC_DEBUG
404    /* Disable inlining to make debugging easier. */
405 #ifdef inline
406 #undef inline
407 #endif
408 
409 #  define inline
410 #endif
411 
412 /* Size of stack-allocated buffer passed to strerror_r(). */
413 #define	STRERROR_BUF		64
414 
415 /* Minimum alignment of allocations is 2^QUANTUM_2POW_MIN bytes. */
416 #  define QUANTUM_2POW_MIN      4
417 #ifdef MOZ_MEMORY_SIZEOF_PTR_2POW
418 #  define SIZEOF_PTR_2POW		MOZ_MEMORY_SIZEOF_PTR_2POW
419 #else
420 #  define SIZEOF_PTR_2POW       2
421 #endif
422 #define PIC
423 #ifndef MOZ_MEMORY_DARWIN
424 static const bool __isthreaded = true;
425 #else
426 #  define NO_TLS
427 #endif
428 #if 0
429 #ifdef __i386__
430 #  define QUANTUM_2POW_MIN	4
431 #  define SIZEOF_PTR_2POW	2
432 #  define CPU_SPINWAIT		__asm__ volatile("pause")
433 #endif
434 #ifdef __ia64__
435 #  define QUANTUM_2POW_MIN	4
436 #  define SIZEOF_PTR_2POW	3
437 #endif
438 #ifdef __alpha__
439 #  define QUANTUM_2POW_MIN	4
440 #  define SIZEOF_PTR_2POW	3
441 #  define NO_TLS
442 #endif
443 #ifdef __sparc64__
444 #  define QUANTUM_2POW_MIN	4
445 #  define SIZEOF_PTR_2POW	3
446 #  define NO_TLS
447 #endif
448 #ifdef __amd64__
449 #  define QUANTUM_2POW_MIN	4
450 #  define SIZEOF_PTR_2POW	3
451 #  define CPU_SPINWAIT		__asm__ volatile("pause")
452 #endif
453 #ifdef __arm__
454 #  define QUANTUM_2POW_MIN	3
455 #  define SIZEOF_PTR_2POW	2
456 #  define NO_TLS
457 #endif
458 #ifdef __mips__
459 #  define QUANTUM_2POW_MIN	3
460 #  define SIZEOF_PTR_2POW	2
461 #  define NO_TLS
462 #endif
463 #ifdef __powerpc__
464 #  define QUANTUM_2POW_MIN	4
465 #  define SIZEOF_PTR_2POW	2
466 #endif
467 #endif
468 
469 #define	SIZEOF_PTR		(1U << SIZEOF_PTR_2POW)
470 
471 /* sizeof(int) == (1U << SIZEOF_INT_2POW). */
472 #ifndef SIZEOF_INT_2POW
473 #  define SIZEOF_INT_2POW	2
474 #endif
475 
476 /* We can't use TLS in non-PIC programs, since TLS relies on loader magic. */
477 #if (!defined(PIC) && !defined(NO_TLS))
478 #  define NO_TLS
479 #endif
480 
481 #ifdef NO_TLS
482    /* MALLOC_BALANCE requires TLS. */
483 #  ifdef MALLOC_BALANCE
484 #    undef MALLOC_BALANCE
485 #  endif
486 #endif
487 
488 /*
489  * Size and alignment of memory chunks that are allocated by the OS's virtual
490  * memory system.
491  */
492 #if defined(MOZ_MEMORY_WINCE) && !defined(MOZ_MEMORY_WINCE6)
493 #define	CHUNK_2POW_DEFAULT	21
494 #else
495 #define	CHUNK_2POW_DEFAULT	20
496 #endif
497 /* Maximum number of dirty pages per arena. */
498 #define	DIRTY_MAX_DEFAULT	(1U << 10)
499 
500 /* Default reserve chunks. */
501 #define	RESERVE_MIN_2POW_DEFAULT	1
502 /*
503  * Default range (in chunks) between reserve_min and reserve_max, in addition
504  * to the mandatory one chunk per arena.
505  */
506 #ifdef MALLOC_PAGEFILE
507 #  define RESERVE_RANGE_2POW_DEFAULT	5
508 #else
509 #  define RESERVE_RANGE_2POW_DEFAULT	0
510 #endif
511 
512 /*
513  * Maximum size of L1 cache line.  This is used to avoid cache line aliasing,
514  * so over-estimates are okay (up to a point), but under-estimates will
515  * negatively affect performance.
516  */
517 #define	CACHELINE_2POW		6
518 #define	CACHELINE		((size_t)(1U << CACHELINE_2POW))
519 
520 /* Smallest size class to support. */
521 #define	TINY_MIN_2POW		1
522 
523 /*
524  * Maximum size class that is a multiple of the quantum, but not (necessarily)
525  * a power of 2.  Above this size, allocations are rounded up to the nearest
526  * power of 2.
527  */
528 #define	SMALL_MAX_2POW_DEFAULT	9
529 #define	SMALL_MAX_DEFAULT	(1U << SMALL_MAX_2POW_DEFAULT)
530 
531 /*
532  * RUN_MAX_OVRHD indicates maximum desired run header overhead.  Runs are sized
533  * as small as possible such that this setting is still honored, without
534  * violating other constraints.  The goal is to make runs as small as possible
535  * without exceeding a per run external fragmentation threshold.
536  *
537  * We use binary fixed point math for overhead computations, where the binary
538  * point is implicitly RUN_BFP bits to the left.
539  *
540  * Note that it is possible to set RUN_MAX_OVRHD low enough that it cannot be
541  * honored for some/all object sizes, since there is one bit of header overhead
542  * per object (plus a constant).  This constraint is relaxed (ignored) for runs
543  * that are so small that the per-region overhead is greater than:
544  *
545  *   (RUN_MAX_OVRHD / (reg_size << (3+RUN_BFP))
546  */
547 #define	RUN_BFP			12
548 /*                                    \/   Implicit binary fixed point. */
549 #define	RUN_MAX_OVRHD		0x0000003dU
550 #define	RUN_MAX_OVRHD_RELAX	0x00001800U
551 
552 /* Put a cap on small object run size.  This overrides RUN_MAX_OVRHD. */
553 #define	RUN_MAX_SMALL_2POW	15
554 #define	RUN_MAX_SMALL		(1U << RUN_MAX_SMALL_2POW)
555 
556 /*
557  * Hyper-threaded CPUs may need a special instruction inside spin loops in
558  * order to yield to another virtual CPU.  If no such instruction is defined
559  * above, make CPU_SPINWAIT a no-op.
560  */
561 #ifndef CPU_SPINWAIT
562 #  define CPU_SPINWAIT
563 #endif
564 
565 /*
566  * Adaptive spinning must eventually switch to blocking, in order to avoid the
567  * potential for priority inversion deadlock.  Backing off past a certain point
568  * can actually waste time.
569  */
570 #define	SPIN_LIMIT_2POW		11
571 
572 /*
573  * Conversion from spinning to blocking is expensive; we use (1U <<
574  * BLOCK_COST_2POW) to estimate how many more times costly blocking is than
575  * worst-case spinning.
576  */
577 #define	BLOCK_COST_2POW		4
578 
579 #ifdef MALLOC_BALANCE
580    /*
581     * We use an exponential moving average to track recent lock contention,
582     * where the size of the history window is N, and alpha=2/(N+1).
583     *
584     * Due to integer math rounding, very small values here can cause
585     * substantial degradation in accuracy, thus making the moving average decay
586     * faster than it would with precise calculation.
587     */
588 #  define BALANCE_ALPHA_INV_2POW	9
589 
590    /*
591     * Threshold value for the exponential moving contention average at which to
592     * re-assign a thread.
593     */
594 #  define BALANCE_THRESHOLD_DEFAULT	(1U << (SPIN_LIMIT_2POW-4))
595 #endif
596 
597 /******************************************************************************/
598 
599 /*
600  * Mutexes based on spinlocks.  We can't use normal pthread spinlocks in all
601  * places, because they require malloc()ed memory, which causes bootstrapping
602  * issues in some cases.
603  */
604 #if defined(MOZ_MEMORY_WINDOWS)
605 #define malloc_mutex_t CRITICAL_SECTION
606 #define malloc_spinlock_t CRITICAL_SECTION
607 #elif defined(MOZ_MEMORY_DARWIN)
608 typedef struct {
609 	OSSpinLock	lock;
610 } malloc_mutex_t;
611 typedef struct {
612 	OSSpinLock	lock;
613 } malloc_spinlock_t;
614 #elif defined(MOZ_MEMORY)
615 typedef pthread_mutex_t malloc_mutex_t;
616 typedef pthread_mutex_t malloc_spinlock_t;
617 #else
618 /* XXX these should #ifdef these for freebsd (and linux?) only */
619 typedef struct {
620 	spinlock_t	lock;
621 } malloc_mutex_t;
622 typedef malloc_spinlock_t malloc_mutex_t;
623 #endif
624 
625 /* Set to true once the allocator has been initialized. */
626 static bool malloc_initialized = false;
627 
628 #if defined(MOZ_MEMORY_WINDOWS)
629 /* No init lock for Windows. */
630 #elif defined(MOZ_MEMORY_DARWIN)
631 static malloc_mutex_t init_lock = {OS_SPINLOCK_INIT};
632 #elif defined(MOZ_MEMORY_LINUX)
633 static malloc_mutex_t init_lock = PTHREAD_ADAPTIVE_MUTEX_INITIALIZER_NP;
634 #elif defined(MOZ_MEMORY)
635 static malloc_mutex_t init_lock = PTHREAD_MUTEX_INITIALIZER;
636 #else
637 static malloc_mutex_t init_lock = {_SPINLOCK_INITIALIZER};
638 #endif
639 
640 /******************************************************************************/
641 /*
642  * Statistics data structures.
643  */
644 
645 #ifdef MALLOC_STATS
646 
647 typedef struct malloc_bin_stats_s malloc_bin_stats_t;
648 struct malloc_bin_stats_s {
649 	/*
650 	 * Number of allocation requests that corresponded to the size of this
651 	 * bin.
652 	 */
653 	uint64_t	nrequests;
654 
655 	/* Total number of runs created for this bin's size class. */
656 	uint64_t	nruns;
657 
658 	/*
659 	 * Total number of runs reused by extracting them from the runs tree for
660 	 * this bin's size class.
661 	 */
662 	uint64_t	reruns;
663 
664 	/* High-water mark for this bin. */
665 	unsigned long	highruns;
666 
667 	/* Current number of runs in this bin. */
668 	unsigned long	curruns;
669 };
670 
671 typedef struct arena_stats_s arena_stats_t;
672 struct arena_stats_s {
673 	/* Number of bytes currently mapped. */
674 	size_t		mapped;
675 
676 	/*
677 	 * Total number of purge sweeps, total number of madvise calls made,
678 	 * and total pages purged in order to keep dirty unused memory under
679 	 * control.
680 	 */
681 	uint64_t	npurge;
682 	uint64_t	nmadvise;
683 	uint64_t	purged;
684 #ifdef MALLOC_DECOMMIT
685 	/*
686 	 * Total number of decommit/commit operations, and total number of
687 	 * pages decommitted.
688 	 */
689 	uint64_t	ndecommit;
690 	uint64_t	ncommit;
691 	uint64_t	decommitted;
692 #endif
693 
694 	/* Per-size-category statistics. */
695 	size_t		allocated_small;
696 	uint64_t	nmalloc_small;
697 	uint64_t	ndalloc_small;
698 
699 	size_t		allocated_large;
700 	uint64_t	nmalloc_large;
701 	uint64_t	ndalloc_large;
702 
703 #ifdef MALLOC_BALANCE
704 	/* Number of times this arena reassigned a thread due to contention. */
705 	uint64_t	nbalance;
706 #endif
707 };
708 
709 typedef struct chunk_stats_s chunk_stats_t;
710 struct chunk_stats_s {
711 	/* Number of chunks that were allocated. */
712 	uint64_t	nchunks;
713 
714 	/* High-water mark for number of chunks allocated. */
715 	unsigned long	highchunks;
716 
717 	/*
718 	 * Current number of chunks allocated.  This value isn't maintained for
719 	 * any other purpose, so keep track of it in order to be able to set
720 	 * highchunks.
721 	 */
722 	unsigned long	curchunks;
723 };
724 
725 #endif /* #ifdef MALLOC_STATS */
726 
727 /******************************************************************************/
728 /*
729  * Extent data structures.
730  */
731 
732 /* Tree of extents. */
733 typedef struct extent_node_s extent_node_t;
734 struct extent_node_s {
735 	/* Linkage for the size/address-ordered tree. */
736 	rb_node(extent_node_t) link_szad;
737 
738 	/* Linkage for the address-ordered tree. */
739 	rb_node(extent_node_t) link_ad;
740 
741 	/* Pointer to the extent that this tree node is responsible for. */
742 	void	*addr;
743 
744 	/* Total region size. */
745 	size_t	size;
746 };
747 typedef rb_tree(extent_node_t) extent_tree_t;
748 
749 /******************************************************************************/
750 /*
751  * Radix tree data structures.
752  */
753 
754 #ifdef MALLOC_VALIDATE
755    /*
756     * Size of each radix tree node (must be a power of 2).  This impacts tree
757     * depth.
758     */
759 #  if (SIZEOF_PTR == 4)
760 #    define MALLOC_RTREE_NODESIZE (1U << 14)
761 #  else
762 #    define MALLOC_RTREE_NODESIZE CACHELINE
763 #  endif
764 
765 typedef struct malloc_rtree_s malloc_rtree_t;
766 struct malloc_rtree_s {
767 	malloc_spinlock_t	lock;
768 	void			**root;
769 	unsigned		height;
770 	unsigned		level2bits[1]; /* Dynamically sized. */
771 };
772 #endif
773 
774 /******************************************************************************/
775 /*
776  * Reserve data structures.
777  */
778 
779 /* Callback registration. */
780 typedef struct reserve_reg_s reserve_reg_t;
781 struct reserve_reg_s {
782 	/* Linkage for list of all registered callbacks. */
783 	ql_elm(reserve_reg_t)	link;
784 
785 	/* Callback function pointer. */
786 	reserve_cb_t		*cb;
787 
788 	/* Opaque application data pointer. */
789 	void			*ctx;
790 
791 	/*
792 	 * Sequence number of condition notification most recently sent to this
793 	 * callback.
794 	 */
795 	uint64_t		seq;
796 };
797 
798 /******************************************************************************/
799 /*
800  * Arena data structures.
801  */
802 
803 typedef struct arena_s arena_t;
804 typedef struct arena_bin_s arena_bin_t;
805 
806 /* Each element of the chunk map corresponds to one page within the chunk. */
807 typedef struct arena_chunk_map_s arena_chunk_map_t;
808 struct arena_chunk_map_s {
809 	/*
810 	 * Linkage for run trees.  There are two disjoint uses:
811 	 *
812 	 * 1) arena_t's runs_avail tree.
813 	 * 2) arena_run_t conceptually uses this linkage for in-use non-full
814 	 *    runs, rather than directly embedding linkage.
815 	 */
816 	rb_node(arena_chunk_map_t)	link;
817 
818 	/*
819 	 * Run address (or size) and various flags are stored together.  The bit
820 	 * layout looks like (assuming 32-bit system):
821 	 *
822 	 *   ???????? ???????? ????---- --ckdzla
823 	 *
824 	 * ? : Unallocated: Run address for first/last pages, unset for internal
825 	 *                  pages.
826 	 *     Small: Run address.
827 	 *     Large: Run size for first page, unset for trailing pages.
828 	 * - : Unused.
829 	 * c : decommitted?
830 	 * k : key?
831 	 * d : dirty?
832 	 * z : zeroed?
833 	 * l : large?
834 	 * a : allocated?
835 	 *
836 	 * Following are example bit patterns for the three types of runs.
837 	 *
838 	 * r : run address
839 	 * s : run size
840 	 * x : don't care
841 	 * - : 0
842 	 * [cdzla] : bit set
843 	 *
844 	 *   Unallocated:
845 	 *     ssssssss ssssssss ssss---- --c-----
846 	 *     xxxxxxxx xxxxxxxx xxxx---- ----d---
847 	 *     ssssssss ssssssss ssss---- -----z--
848 	 *
849 	 *   Small:
850 	 *     rrrrrrrr rrrrrrrr rrrr---- -------a
851 	 *     rrrrrrrr rrrrrrrr rrrr---- -------a
852 	 *     rrrrrrrr rrrrrrrr rrrr---- -------a
853 	 *
854 	 *   Large:
855 	 *     ssssssss ssssssss ssss---- ------la
856 	 *     -------- -------- -------- ------la
857 	 *     -------- -------- -------- ------la
858 	 */
859 	size_t				bits;
860 #ifdef MALLOC_DECOMMIT
861 #define	CHUNK_MAP_DECOMMITTED	((size_t)0x20U)
862 #endif
863 #define	CHUNK_MAP_KEY		((size_t)0x10U)
864 #define	CHUNK_MAP_DIRTY		((size_t)0x08U)
865 #define	CHUNK_MAP_ZEROED	((size_t)0x04U)
866 #define	CHUNK_MAP_LARGE		((size_t)0x02U)
867 #define	CHUNK_MAP_ALLOCATED	((size_t)0x01U)
868 };
869 typedef rb_tree(arena_chunk_map_t) arena_avail_tree_t;
870 typedef rb_tree(arena_chunk_map_t) arena_run_tree_t;
871 
872 /* Arena chunk header. */
873 typedef struct arena_chunk_s arena_chunk_t;
874 struct arena_chunk_s {
875 	/* Arena that owns the chunk. */
876 	arena_t		*arena;
877 
878 	/* Linkage for the arena's chunks_dirty tree. */
879 	rb_node(arena_chunk_t) link_dirty;
880 
881 	/* Number of dirty pages. */
882 	size_t		ndirty;
883 
884 	/* Map of pages within chunk that keeps track of free/large/small. */
885 	arena_chunk_map_t map[1]; /* Dynamically sized. */
886 };
887 typedef rb_tree(arena_chunk_t) arena_chunk_tree_t;
888 
889 typedef struct arena_run_s arena_run_t;
890 struct arena_run_s {
891 #ifdef MALLOC_DEBUG
892 	uint32_t	magic;
893 #  define ARENA_RUN_MAGIC 0x384adf93
894 #endif
895 
896 	/* Bin this run is associated with. */
897 	arena_bin_t	*bin;
898 
899 	/* Index of first element that might have a free region. */
900 	unsigned	regs_minelm;
901 
902 	/* Number of free regions in run. */
903 	unsigned	nfree;
904 
905 	/* Bitmask of in-use regions (0: in use, 1: free). */
906 	unsigned	regs_mask[1]; /* Dynamically sized. */
907 };
908 
909 struct arena_bin_s {
910 	/*
911 	 * Current run being used to service allocations of this bin's size
912 	 * class.
913 	 */
914 	arena_run_t	*runcur;
915 
916 	/*
917 	 * Tree of non-full runs.  This tree is used when looking for an
918 	 * existing run when runcur is no longer usable.  We choose the
919 	 * non-full run that is lowest in memory; this policy tends to keep
920 	 * objects packed well, and it can also help reduce the number of
921 	 * almost-empty chunks.
922 	 */
923 	arena_run_tree_t runs;
924 
925 	/* Size of regions in a run for this bin's size class. */
926 	size_t		reg_size;
927 
928 	/* Total size of a run for this bin's size class. */
929 	size_t		run_size;
930 
931 	/* Total number of regions in a run for this bin's size class. */
932 	uint32_t	nregs;
933 
934 	/* Number of elements in a run's regs_mask for this bin's size class. */
935 	uint32_t	regs_mask_nelms;
936 
937 	/* Offset of first region in a run for this bin's size class. */
938 	uint32_t	reg0_offset;
939 
940 #ifdef MALLOC_STATS
941 	/* Bin statistics. */
942 	malloc_bin_stats_t stats;
943 #endif
944 };
945 
946 struct arena_s {
947 #ifdef MALLOC_DEBUG
948 	uint32_t		magic;
949 #  define ARENA_MAGIC 0x947d3d24
950 #endif
951 
952 	/* All operations on this arena require that lock be locked. */
953 #ifdef MOZ_MEMORY
954 	malloc_spinlock_t	lock;
955 #else
956 	pthread_mutex_t		lock;
957 #endif
958 
959 #ifdef MALLOC_STATS
960 	arena_stats_t		stats;
961 #endif
962 
963 	/*
964 	 * Chunk allocation sequence number, used to detect races with other
965 	 * threads during chunk allocation, and then discard unnecessary chunks.
966 	 */
967 	uint64_t		chunk_seq;
968 
969 	/* Tree of dirty-page-containing chunks this arena manages. */
970 	arena_chunk_tree_t	chunks_dirty;
971 
972 	/*
973 	 * In order to avoid rapid chunk allocation/deallocation when an arena
974 	 * oscillates right on the cusp of needing a new chunk, cache the most
975 	 * recently freed chunk.  The spare is left in the arena's chunk trees
976 	 * until it is deleted.
977 	 *
978 	 * There is one spare chunk per arena, rather than one spare total, in
979 	 * order to avoid interactions between multiple threads that could make
980 	 * a single spare inadequate.
981 	 */
982 	arena_chunk_t		*spare;
983 
984 	/*
985 	 * Current count of pages within unused runs that are potentially
986 	 * dirty, and for which madvise(... MADV_FREE) has not been called.  By
987 	 * tracking this, we can institute a limit on how much dirty unused
988 	 * memory is mapped for each arena.
989 	 */
990 	size_t			ndirty;
991 
992 	/*
993 	 * Size/address-ordered tree of this arena's available runs.  This tree
994 	 * is used for first-best-fit run allocation.
995 	 */
996 	arena_avail_tree_t	runs_avail;
997 
998 #ifdef MALLOC_BALANCE
999 	/*
1000 	 * The arena load balancing machinery needs to keep track of how much
1001 	 * lock contention there is.  This value is exponentially averaged.
1002 	 */
1003 	uint32_t		contention;
1004 #endif
1005 
1006 	/*
1007 	 * bins is used to store rings of free regions of the following sizes,
1008 	 * assuming a 16-byte quantum, 4kB pagesize, and default MALLOC_OPTIONS.
1009 	 *
1010 	 *   bins[i] | size |
1011 	 *   --------+------+
1012 	 *        0  |    2 |
1013 	 *        1  |    4 |
1014 	 *        2  |    8 |
1015 	 *   --------+------+
1016 	 *        3  |   16 |
1017 	 *        4  |   32 |
1018 	 *        5  |   48 |
1019 	 *        6  |   64 |
1020 	 *           :      :
1021 	 *           :      :
1022 	 *       33  |  496 |
1023 	 *       34  |  512 |
1024 	 *   --------+------+
1025 	 *       35  | 1024 |
1026 	 *       36  | 2048 |
1027 	 *   --------+------+
1028 	 */
1029 	arena_bin_t		bins[1]; /* Dynamically sized. */
1030 };
1031 
1032 /******************************************************************************/
1033 /*
1034  * Data.
1035  */
1036 
1037 /* Number of CPUs. */
1038 static unsigned		ncpus;
1039 
1040 /* VM page size. */
1041 static size_t		pagesize;
1042 static size_t		pagesize_mask;
1043 static size_t		pagesize_2pow;
1044 
1045 /* Various bin-related settings. */
1046 static size_t		bin_maxclass; /* Max size class for bins. */
1047 static unsigned		ntbins; /* Number of (2^n)-spaced tiny bins. */
1048 static unsigned		nqbins; /* Number of quantum-spaced bins. */
1049 static unsigned		nsbins; /* Number of (2^n)-spaced sub-page bins. */
1050 static size_t		small_min;
1051 static size_t		small_max;
1052 
1053 /* Various quantum-related settings. */
1054 static size_t		quantum;
1055 static size_t		quantum_mask; /* (quantum - 1). */
1056 
1057 /* Various chunk-related settings. */
1058 static size_t		chunksize;
1059 static size_t		chunksize_mask; /* (chunksize - 1). */
1060 static size_t		chunk_npages;
1061 static size_t		arena_chunk_header_npages;
1062 static size_t		arena_maxclass; /* Max size class for arenas. */
1063 
1064 /********/
1065 /*
1066  * Chunks.
1067  */
1068 
1069 #ifdef MALLOC_VALIDATE
1070 static malloc_rtree_t *chunk_rtree;
1071 #endif
1072 
1073 /* Protects chunk-related data structures. */
1074 static malloc_mutex_t	huge_mtx;
1075 
1076 /* Tree of chunks that are stand-alone huge allocations. */
1077 static extent_tree_t	huge;
1078 
1079 #ifdef MALLOC_STATS
1080 /* Huge allocation statistics. */
1081 static uint64_t		huge_nmalloc;
1082 static uint64_t		huge_ndalloc;
1083 static size_t		huge_allocated;
1084 #endif
1085 
1086 /****************/
1087 /*
1088  * Memory reserve.
1089  */
1090 
1091 #ifdef MALLOC_PAGEFILE
1092 static char		pagefile_templ[PATH_MAX];
1093 #endif
1094 
1095 /* Protects reserve-related data structures. */
1096 static malloc_mutex_t	reserve_mtx;
1097 
1098 /*
1099  * Bounds on acceptable reserve size, and current reserve size.  Reserve
1100  * depletion may cause (reserve_cur < reserve_min).
1101  */
1102 static size_t		reserve_min;
1103 static size_t		reserve_cur;
1104 static size_t		reserve_max;
1105 
1106 /* List of registered callbacks. */
1107 static ql_head(reserve_reg_t) reserve_regs;
1108 
1109 /*
1110  * Condition notification sequence number, used to determine whether all
1111  * registered callbacks have been notified of the most current condition.
1112  */
1113 static uint64_t		reserve_seq;
1114 
1115 /*
1116  * Trees of chunks currently in the memory reserve.  Depending on function,
1117  * different tree orderings are needed, which is why there are two trees with
1118  * the same contents.
1119  */
1120 static extent_tree_t	reserve_chunks_szad;
1121 static extent_tree_t	reserve_chunks_ad;
1122 
1123 /****************************/
1124 /*
1125  * base (internal allocation).
1126  */
1127 
1128 /*
1129  * Current pages that are being used for internal memory allocations.  These
1130  * pages are carved up in cacheline-size quanta, so that there is no chance of
1131  * false cache line sharing.
1132  */
1133 static void		*base_pages;
1134 static void		*base_next_addr;
1135 #ifdef MALLOC_DECOMMIT
1136 static void		*base_next_decommitted;
1137 #endif
1138 static void		*base_past_addr; /* Addr immediately past base_pages. */
1139 static extent_node_t	*base_nodes;
1140 static reserve_reg_t	*base_reserve_regs;
1141 static malloc_mutex_t	base_mtx;
1142 #ifdef MALLOC_STATS
1143 static size_t		base_mapped;
1144 #endif
1145 
1146 /********/
1147 /*
1148  * Arenas.
1149  */
1150 
1151 /*
1152  * Arenas that are used to service external requests.  Not all elements of the
1153  * arenas array are necessarily used; arenas are created lazily as needed.
1154  */
1155 static arena_t		**arenas;
1156 static unsigned		narenas;
1157 static unsigned		narenas_2pow;
1158 #ifndef NO_TLS
1159 #  ifdef MALLOC_BALANCE
1160 static unsigned		narenas_2pow;
1161 #  else
1162 static unsigned		next_arena;
1163 #  endif
1164 #endif
1165 #ifdef MOZ_MEMORY
1166 static malloc_spinlock_t arenas_lock; /* Protects arenas initialization. */
1167 #else
1168 static pthread_mutex_t arenas_lock; /* Protects arenas initialization. */
1169 #endif
1170 
1171 #ifndef NO_TLS
1172 /*
1173  * Map of pthread_self() --> arenas[???], used for selecting an arena to use
1174  * for allocations.
1175  */
1176 #ifndef MOZ_MEMORY_WINDOWS
1177 static __thread arena_t	*arenas_map;
1178 #endif
1179 #endif
1180 
1181 #ifdef MALLOC_STATS
1182 /* Chunk statistics. */
1183 static chunk_stats_t	stats_chunks;
1184 #endif
1185 
1186 /*******************************/
1187 /*
1188  * Runtime configuration options.
1189  */
1190 const char	*_malloc_options;
1191 
1192 #ifndef MALLOC_PRODUCTION
1193 static bool	opt_abort = true;
1194 #ifdef MALLOC_FILL
1195 static bool	opt_junk = true;
1196 #endif
1197 #else
1198 static bool	opt_abort = false;
1199 #ifdef MALLOC_FILL
1200 static bool	opt_junk = false;
1201 #endif
1202 #endif
1203 static size_t	opt_dirty_max = DIRTY_MAX_DEFAULT;
1204 #ifdef MALLOC_BALANCE
1205 static uint64_t	opt_balance_threshold = BALANCE_THRESHOLD_DEFAULT;
1206 #endif
1207 static bool	opt_print_stats = false;
1208 static size_t	opt_quantum_2pow = QUANTUM_2POW_MIN;
1209 static size_t	opt_small_max_2pow = SMALL_MAX_2POW_DEFAULT;
1210 static size_t	opt_chunk_2pow = CHUNK_2POW_DEFAULT;
1211 static int	opt_reserve_min_lshift = 0;
1212 static int	opt_reserve_range_lshift = 0;
1213 #ifdef MALLOC_PAGEFILE
1214 static bool	opt_pagefile = false;
1215 #endif
1216 #ifdef MALLOC_UTRACE
1217 static bool	opt_utrace = false;
1218 #endif
1219 #ifdef MALLOC_SYSV
1220 static bool	opt_sysv = false;
1221 #endif
1222 #ifdef MALLOC_XMALLOC
1223 static bool	opt_xmalloc = false;
1224 #endif
1225 #ifdef MALLOC_FILL
1226 static bool	opt_zero = false;
1227 #endif
1228 static int	opt_narenas_lshift = 0;
1229 
1230 #ifdef MALLOC_UTRACE
1231 typedef struct {
1232 	void	*p;
1233 	size_t	s;
1234 	void	*r;
1235 } malloc_utrace_t;
1236 
1237 #define	UTRACE(a, b, c)							\
1238 	if (opt_utrace) {						\
1239 		malloc_utrace_t ut;					\
1240 		ut.p = (a);						\
1241 		ut.s = (b);						\
1242 		ut.r = (c);						\
1243 		utrace(&ut, sizeof(ut));				\
1244 	}
1245 #else
1246 #define	UTRACE(a, b, c)
1247 #endif
1248 
1249 /******************************************************************************/
1250 /*
1251  * Begin function prototypes for non-inline static functions.
1252  */
1253 
1254 static char	*umax2s(uintmax_t x, char *s);
1255 static bool	malloc_mutex_init(malloc_mutex_t *mutex);
1256 static bool	malloc_spin_init(malloc_spinlock_t *lock);
1257 static void	wrtmessage(const char *p1, const char *p2, const char *p3,
1258 		const char *p4);
1259 #ifdef MALLOC_STATS
1260 #ifdef MOZ_MEMORY_DARWIN
1261 /* Avoid namespace collision with OS X's malloc APIs. */
1262 #define malloc_printf moz_malloc_printf
1263 #endif
1264 static void	malloc_printf(const char *format, ...);
1265 #endif
1266 static bool	base_pages_alloc_mmap(size_t minsize);
1267 static bool	base_pages_alloc(size_t minsize);
1268 static void	*base_alloc(size_t size);
1269 static void	*base_calloc(size_t number, size_t size);
1270 static extent_node_t *base_node_alloc(void);
1271 static void	base_node_dealloc(extent_node_t *node);
1272 static reserve_reg_t *base_reserve_reg_alloc(void);
1273 static void	base_reserve_reg_dealloc(reserve_reg_t *reg);
1274 #ifdef MALLOC_STATS
1275 static void	stats_print(arena_t *arena);
1276 #endif
1277 static void	*pages_map(void *addr, size_t size, int pfd);
1278 static void	pages_unmap(void *addr, size_t size);
1279 static void	*chunk_alloc_mmap(size_t size, bool pagefile);
1280 #ifdef MALLOC_PAGEFILE
1281 static int	pagefile_init(size_t size);
1282 static void	pagefile_close(int pfd);
1283 #endif
1284 static void	*chunk_recycle_reserve(size_t size, bool zero);
1285 static void	*chunk_alloc(size_t size, bool zero, bool pagefile);
1286 static extent_node_t *chunk_dealloc_reserve(void *chunk, size_t size);
1287 static void	chunk_dealloc_mmap(void *chunk, size_t size);
1288 static void	chunk_dealloc(void *chunk, size_t size);
1289 #ifndef NO_TLS
1290 static arena_t	*choose_arena_hard(void);
1291 #endif
1292 static void	arena_run_split(arena_t *arena, arena_run_t *run, size_t size,
1293     bool large, bool zero);
1294 static void arena_chunk_init(arena_t *arena, arena_chunk_t *chunk);
1295 static void	arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk);
1296 static arena_run_t *arena_run_alloc(arena_t *arena, arena_bin_t *bin,
1297     size_t size, bool large, bool zero);
1298 static void	arena_purge(arena_t *arena);
1299 static void	arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty);
1300 static void	arena_run_trim_head(arena_t *arena, arena_chunk_t *chunk,
1301     arena_run_t *run, size_t oldsize, size_t newsize);
1302 static void	arena_run_trim_tail(arena_t *arena, arena_chunk_t *chunk,
1303     arena_run_t *run, size_t oldsize, size_t newsize, bool dirty);
1304 static arena_run_t *arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin);
1305 static void *arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin);
1306 static size_t arena_bin_run_size_calc(arena_bin_t *bin, size_t min_run_size);
1307 #ifdef MALLOC_BALANCE
1308 static void	arena_lock_balance_hard(arena_t *arena);
1309 #endif
1310 static void	*arena_malloc_large(arena_t *arena, size_t size, bool zero);
1311 static void	*arena_palloc(arena_t *arena, size_t alignment, size_t size,
1312     size_t alloc_size);
1313 static size_t	arena_salloc(const void *ptr);
1314 static void	arena_dalloc_large(arena_t *arena, arena_chunk_t *chunk,
1315     void *ptr);
1316 static void	arena_ralloc_large_shrink(arena_t *arena, arena_chunk_t *chunk,
1317     void *ptr, size_t size, size_t oldsize);
1318 static bool	arena_ralloc_large_grow(arena_t *arena, arena_chunk_t *chunk,
1319     void *ptr, size_t size, size_t oldsize);
1320 static bool	arena_ralloc_large(void *ptr, size_t size, size_t oldsize);
1321 static void	*arena_ralloc(void *ptr, size_t size, size_t oldsize);
1322 static bool	arena_new(arena_t *arena);
1323 static arena_t	*arenas_extend(unsigned ind);
1324 static void	*huge_malloc(size_t size, bool zero);
1325 static void	*huge_palloc(size_t alignment, size_t size);
1326 static void	*huge_ralloc(void *ptr, size_t size, size_t oldsize);
1327 static void	huge_dalloc(void *ptr);
1328 static void	malloc_print_stats(void);
1329 #ifndef MOZ_MEMORY_WINDOWS
1330 static
1331 #endif
1332 bool		malloc_init_hard(void);
1333 static void	reserve_shrink(void);
1334 static uint64_t	reserve_notify(reserve_cnd_t cnd, size_t size, uint64_t seq);
1335 static uint64_t	reserve_crit(size_t size, const char *fname, uint64_t seq);
1336 static void	reserve_fail(size_t size, const char *fname);
1337 
1338 void		_malloc_prefork(void);
1339 void		_malloc_postfork(void);
1340 
1341 /*
1342  * End function prototypes.
1343  */
1344 /******************************************************************************/
1345 
1346 /*
1347  * umax2s() provides minimal integer printing functionality, which is
1348  * especially useful for situations where allocation in vsnprintf() calls would
1349  * potentially cause deadlock.
1350  */
1351 #define	UMAX2S_BUFSIZE	21
1352 static char *
umax2s(uintmax_t x,char * s)1353 umax2s(uintmax_t x, char *s)
1354 {
1355 	unsigned i;
1356 
1357 	i = UMAX2S_BUFSIZE - 1;
1358 	s[i] = '\0';
1359 	do {
1360 		i--;
1361 		s[i] = "0123456789"[x % 10];
1362 		x /= 10;
1363 	} while (x > 0);
1364 
1365 	return (&s[i]);
1366 }
1367 
1368 static void
wrtmessage(const char * p1,const char * p2,const char * p3,const char * p4)1369 wrtmessage(const char *p1, const char *p2, const char *p3, const char *p4)
1370 {
1371 #ifdef MOZ_MEMORY_WINCE
1372        wchar_t buf[1024];
1373 #define WRT_PRINT(s) \
1374        MultiByteToWideChar(CP_ACP, 0, s, -1, buf, 1024); \
1375        OutputDebugStringW(buf)
1376 
1377        WRT_PRINT(p1);
1378        WRT_PRINT(p2);
1379        WRT_PRINT(p3);
1380        WRT_PRINT(p4);
1381 #else
1382 #if defined(MOZ_MEMORY) && !defined(MOZ_MEMORY_WINDOWS)
1383 #define	_write	write
1384 #endif
1385 	_write(STDERR_FILENO, p1, (unsigned int) strlen(p1));
1386 	_write(STDERR_FILENO, p2, (unsigned int) strlen(p2));
1387 	_write(STDERR_FILENO, p3, (unsigned int) strlen(p3));
1388 	_write(STDERR_FILENO, p4, (unsigned int) strlen(p4));
1389 #endif
1390 
1391 }
1392 
1393 #define _malloc_message malloc_message
1394 
1395 void	(*_malloc_message)(const char *p1, const char *p2, const char *p3,
1396 	    const char *p4) = wrtmessage;
1397 
1398 #ifdef MALLOC_DEBUG
1399 #  define assert(e) do {						\
1400 	if (!(e)) {							\
1401 		char line_buf[UMAX2S_BUFSIZE];				\
1402 		_malloc_message(__FILE__, ":", umax2s(__LINE__,		\
1403 		    line_buf), ": Failed assertion: ");			\
1404 		_malloc_message("\"", #e, "\"\n", "");			\
1405 		abort();						\
1406 	}								\
1407 } while (0)
1408 #else
1409 #define assert(e)
1410 #endif
1411 
1412 /******************************************************************************/
1413 /*
1414  * Begin mutex.  We can't use normal pthread mutexes in all places, because
1415  * they require malloc()ed memory, which causes bootstrapping issues in some
1416  * cases.
1417  */
1418 
1419 static bool
malloc_mutex_init(malloc_mutex_t * mutex)1420 malloc_mutex_init(malloc_mutex_t *mutex)
1421 {
1422 #if defined(MOZ_MEMORY_WINCE)
1423 	InitializeCriticalSection(mutex);
1424 #elif defined(MOZ_MEMORY_WINDOWS)
1425   // XXXMB
1426 	//if (__isthreaded)
1427 	//	if (! __crtInitCritSecAndSpinCount(mutex, _CRT_SPINCOUNT))
1428 	//		return (true);
1429   if (!InitializeCriticalSectionAndSpinCount(mutex, 4000))
1430     return true;
1431 #elif defined(MOZ_MEMORY_DARWIN)
1432 	mutex->lock = OS_SPINLOCK_INIT;
1433 #elif defined(MOZ_MEMORY_LINUX)
1434 	pthread_mutexattr_t attr;
1435 	if (pthread_mutexattr_init(&attr) != 0)
1436 		return (true);
1437 	pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_ADAPTIVE_NP);
1438 	if (pthread_mutex_init(mutex, &attr) != 0) {
1439 		pthread_mutexattr_destroy(&attr);
1440 		return (true);
1441 	}
1442 	pthread_mutexattr_destroy(&attr);
1443 #elif defined(MOZ_MEMORY)
1444 	if (pthread_mutex_init(mutex, NULL) != 0)
1445 		return (true);
1446 #else
1447 	static const spinlock_t lock = _SPINLOCK_INITIALIZER;
1448 
1449 	mutex->lock = lock;
1450 #endif
1451 	return (false);
1452 }
1453 
1454 static inline void
malloc_mutex_lock(malloc_mutex_t * mutex)1455 malloc_mutex_lock(malloc_mutex_t *mutex)
1456 {
1457 
1458 #if defined(MOZ_MEMORY_WINDOWS)
1459 	EnterCriticalSection(mutex);
1460 #elif defined(MOZ_MEMORY_DARWIN)
1461 	OSSpinLockLock(&mutex->lock);
1462 #elif defined(MOZ_MEMORY)
1463 	pthread_mutex_lock(mutex);
1464 #else
1465 	if (__isthreaded)
1466 		_SPINLOCK(&mutex->lock);
1467 #endif
1468 }
1469 
1470 static inline void
malloc_mutex_unlock(malloc_mutex_t * mutex)1471 malloc_mutex_unlock(malloc_mutex_t *mutex)
1472 {
1473 
1474 #if defined(MOZ_MEMORY_WINDOWS)
1475 	LeaveCriticalSection(mutex);
1476 #elif defined(MOZ_MEMORY_DARWIN)
1477 	OSSpinLockUnlock(&mutex->lock);
1478 #elif defined(MOZ_MEMORY)
1479 	pthread_mutex_unlock(mutex);
1480 #else
1481 	if (__isthreaded)
1482 		_SPINUNLOCK(&mutex->lock);
1483 #endif
1484 }
1485 
1486 static bool
malloc_spin_init(malloc_spinlock_t * lock)1487 malloc_spin_init(malloc_spinlock_t *lock)
1488 {
1489 #if defined(MOZ_MEMORY_WINCE)
1490 	InitializeCriticalSection(lock);
1491 #elif defined(MOZ_MEMORY_WINDOWS)
1492   // XXXMB
1493 	//if (__isthreaded)
1494 	//	if (! __crtInitCritSecAndSpinCount(lock, _CRT_SPINCOUNT))
1495 	//		return (true);
1496 #elif defined(MOZ_MEMORY_DARWIN)
1497 	lock->lock = OS_SPINLOCK_INIT;
1498 #elif defined(MOZ_MEMORY_LINUX)
1499 	pthread_mutexattr_t attr;
1500 	if (pthread_mutexattr_init(&attr) != 0)
1501 		return (true);
1502 	pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_ADAPTIVE_NP);
1503 	if (pthread_mutex_init(lock, &attr) != 0) {
1504 		pthread_mutexattr_destroy(&attr);
1505 		return (true);
1506 	}
1507 	pthread_mutexattr_destroy(&attr);
1508 #elif defined(MOZ_MEMORY)
1509 	if (pthread_mutex_init(lock, NULL) != 0)
1510 		return (true);
1511 #else
1512 	lock->lock = _SPINLOCK_INITIALIZER;
1513 #endif
1514 	return (false);
1515 }
1516 
1517 static inline void
malloc_spin_lock(malloc_spinlock_t * lock)1518 malloc_spin_lock(malloc_spinlock_t *lock)
1519 {
1520 
1521 #if defined(MOZ_MEMORY_WINDOWS)
1522 	EnterCriticalSection(lock);
1523 #elif defined(MOZ_MEMORY_DARWIN)
1524 	OSSpinLockLock(&lock->lock);
1525 #elif defined(MOZ_MEMORY)
1526 	pthread_mutex_lock(lock);
1527 #else
1528 	if (__isthreaded)
1529 		_SPINLOCK(&lock->lock);
1530 #endif
1531 }
1532 
1533 static inline void
malloc_spin_unlock(malloc_spinlock_t * lock)1534 malloc_spin_unlock(malloc_spinlock_t *lock)
1535 {
1536 #if defined(MOZ_MEMORY_WINDOWS)
1537 	LeaveCriticalSection(lock);
1538 #elif defined(MOZ_MEMORY_DARWIN)
1539 	OSSpinLockUnlock(&lock->lock);
1540 #elif defined(MOZ_MEMORY)
1541 	pthread_mutex_unlock(lock);
1542 #else
1543 	if (__isthreaded)
1544 		_SPINUNLOCK(&lock->lock);
1545 #endif
1546 }
1547 
1548 /*
1549  * End mutex.
1550  */
1551 /******************************************************************************/
1552 /*
1553  * Begin spin lock.  Spin locks here are actually adaptive mutexes that block
1554  * after a period of spinning, because unbounded spinning would allow for
1555  * priority inversion.
1556  */
1557 
1558 #if defined(MOZ_MEMORY) && !defined(MOZ_MEMORY_DARWIN)
1559 #  define	malloc_spin_init	malloc_mutex_init
1560 #  define	malloc_spin_lock	malloc_mutex_lock
1561 #  define	malloc_spin_unlock	malloc_mutex_unlock
1562 #endif
1563 
1564 #ifndef MOZ_MEMORY
1565 /*
1566  * We use an unpublished interface to initialize pthread mutexes with an
1567  * allocation callback, in order to avoid infinite recursion.
1568  */
1569 int	_pthread_mutex_init_calloc_cb(pthread_mutex_t *mutex,
1570     void *(calloc_cb)(size_t, size_t));
1571 
1572 __weak_reference(_pthread_mutex_init_calloc_cb_stub,
1573     _pthread_mutex_init_calloc_cb);
1574 
1575 int
_pthread_mutex_init_calloc_cb_stub(pthread_mutex_t * mutex,void * (calloc_cb)(size_t,size_t))1576 _pthread_mutex_init_calloc_cb_stub(pthread_mutex_t *mutex,
1577     void *(calloc_cb)(size_t, size_t))
1578 {
1579 
1580 	return (0);
1581 }
1582 
1583 static bool
malloc_spin_init(pthread_mutex_t * lock)1584 malloc_spin_init(pthread_mutex_t *lock)
1585 {
1586 
1587 	if (_pthread_mutex_init_calloc_cb(lock, base_calloc) != 0)
1588 		return (true);
1589 
1590 	return (false);
1591 }
1592 
1593 static inline unsigned
malloc_spin_lock(pthread_mutex_t * lock)1594 malloc_spin_lock(pthread_mutex_t *lock)
1595 {
1596 	unsigned ret = 0;
1597 
1598 	if (__isthreaded) {
1599 		if (_pthread_mutex_trylock(lock) != 0) {
1600 			unsigned i;
1601 			volatile unsigned j;
1602 
1603 			/* Exponentially back off. */
1604 			for (i = 1; i <= SPIN_LIMIT_2POW; i++) {
1605 				for (j = 0; j < (1U << i); j++)
1606 					ret++;
1607 
1608 				CPU_SPINWAIT;
1609 				if (_pthread_mutex_trylock(lock) == 0)
1610 					return (ret);
1611 			}
1612 
1613 			/*
1614 			 * Spinning failed.  Block until the lock becomes
1615 			 * available, in order to avoid indefinite priority
1616 			 * inversion.
1617 			 */
1618 			_pthread_mutex_lock(lock);
1619 			assert((ret << BLOCK_COST_2POW) != 0);
1620 			return (ret << BLOCK_COST_2POW);
1621 		}
1622 	}
1623 
1624 	return (ret);
1625 }
1626 
1627 static inline void
malloc_spin_unlock(pthread_mutex_t * lock)1628 malloc_spin_unlock(pthread_mutex_t *lock)
1629 {
1630 
1631 	if (__isthreaded)
1632 		_pthread_mutex_unlock(lock);
1633 }
1634 #endif
1635 
1636 /*
1637  * End spin lock.
1638  */
1639 /******************************************************************************/
1640 /*
1641  * Begin Utility functions/macros.
1642  */
1643 
1644 /* Return the chunk address for allocation address a. */
1645 #define	CHUNK_ADDR2BASE(a)						\
1646 	((void *)((uintptr_t)(a) & ~chunksize_mask))
1647 
1648 /* Return the chunk offset of address a. */
1649 #define	CHUNK_ADDR2OFFSET(a)						\
1650 	((size_t)((uintptr_t)(a) & chunksize_mask))
1651 
1652 /* Return the smallest chunk multiple that is >= s. */
1653 #define	CHUNK_CEILING(s)						\
1654 	(((s) + chunksize_mask) & ~chunksize_mask)
1655 
1656 /* Return the smallest cacheline multiple that is >= s. */
1657 #define	CACHELINE_CEILING(s)						\
1658 	(((s) + (CACHELINE - 1)) & ~(CACHELINE - 1))
1659 
1660 /* Return the smallest quantum multiple that is >= a. */
1661 #define	QUANTUM_CEILING(a)						\
1662 	(((a) + quantum_mask) & ~quantum_mask)
1663 
1664 /* Return the smallest pagesize multiple that is >= s. */
1665 #define	PAGE_CEILING(s)							\
1666 	(((s) + pagesize_mask) & ~pagesize_mask)
1667 
1668 /* Compute the smallest power of 2 that is >= x. */
1669 static inline size_t
pow2_ceil(size_t x)1670 pow2_ceil(size_t x)
1671 {
1672 
1673 	x--;
1674 	x |= x >> 1;
1675 	x |= x >> 2;
1676 	x |= x >> 4;
1677 	x |= x >> 8;
1678 	x |= x >> 16;
1679 #if (SIZEOF_PTR == 8)
1680 	x |= x >> 32;
1681 #endif
1682 	x++;
1683 	return (x);
1684 }
1685 
1686 #ifdef MALLOC_BALANCE
1687 /*
1688  * Use a simple linear congruential pseudo-random number generator:
1689  *
1690  *   prn(y) = (a*x + c) % m
1691  *
1692  * where the following constants ensure maximal period:
1693  *
1694  *   a == Odd number (relatively prime to 2^n), and (a-1) is a multiple of 4.
1695  *   c == Odd number (relatively prime to 2^n).
1696  *   m == 2^32
1697  *
1698  * See Knuth's TAOCP 3rd Ed., Vol. 2, pg. 17 for details on these constraints.
1699  *
1700  * This choice of m has the disadvantage that the quality of the bits is
1701  * proportional to bit position.  For example. the lowest bit has a cycle of 2,
1702  * the next has a cycle of 4, etc.  For this reason, we prefer to use the upper
1703  * bits.
1704  */
1705 #  define PRN_DEFINE(suffix, var, a, c)					\
1706 static inline void							\
1707 sprn_##suffix(uint32_t seed)						\
1708 {									\
1709 	var = seed;							\
1710 }									\
1711 									\
1712 static inline uint32_t							\
1713 prn_##suffix(uint32_t lg_range)						\
1714 {									\
1715 	uint32_t ret, x;						\
1716 									\
1717 	assert(lg_range > 0);						\
1718 	assert(lg_range <= 32);						\
1719 									\
1720 	x = (var * (a)) + (c);						\
1721 	var = x;							\
1722 	ret = x >> (32 - lg_range);					\
1723 									\
1724 	return (ret);							\
1725 }
1726 #  define SPRN(suffix, seed)	sprn_##suffix(seed)
1727 #  define PRN(suffix, lg_range)	prn_##suffix(lg_range)
1728 #endif
1729 
1730 #ifdef MALLOC_BALANCE
1731 /* Define the PRNG used for arena assignment. */
1732 static __thread uint32_t balance_x;
1733 PRN_DEFINE(balance, balance_x, 1297, 1301)
1734 #endif
1735 
1736 #ifdef MALLOC_UTRACE
1737 static int
utrace(const void * addr,size_t len)1738 utrace(const void *addr, size_t len)
1739 {
1740 	malloc_utrace_t *ut = (malloc_utrace_t *)addr;
1741 
1742 	assert(len == sizeof(malloc_utrace_t));
1743 
1744 	if (ut->p == NULL && ut->s == 0 && ut->r == NULL)
1745 		malloc_printf("%d x USER malloc_init()\n", getpid());
1746 	else if (ut->p == NULL && ut->r != NULL) {
1747 		malloc_printf("%d x USER %p = malloc(%zu)\n", getpid(), ut->r,
1748 		    ut->s);
1749 	} else if (ut->p != NULL && ut->r != NULL) {
1750 		malloc_printf("%d x USER %p = realloc(%p, %zu)\n", getpid(),
1751 		    ut->r, ut->p, ut->s);
1752 	} else
1753 		malloc_printf("%d x USER free(%p)\n", getpid(), ut->p);
1754 
1755 	return (0);
1756 }
1757 #endif
1758 
1759 static inline const char *
_getprogname(void)1760 _getprogname(void)
1761 {
1762 
1763 	return ("<jemalloc>");
1764 }
1765 
1766 #ifdef MALLOC_STATS
1767 /*
1768  * Print to stderr in such a way as to (hopefully) avoid memory allocation.
1769  */
1770 static void
malloc_printf(const char * format,...)1771 malloc_printf(const char *format, ...)
1772 {
1773 #ifndef WINCE
1774 	char buf[4096];
1775 	va_list ap;
1776 
1777 	va_start(ap, format);
1778 	vsnprintf(buf, sizeof(buf), format, ap);
1779 	va_end(ap);
1780 	_malloc_message(buf, "", "", "");
1781 #endif
1782 }
1783 #endif
1784 
1785 /******************************************************************************/
1786 
1787 #ifdef MALLOC_DECOMMIT
1788 static inline void
pages_decommit(void * addr,size_t size)1789 pages_decommit(void *addr, size_t size)
1790 {
1791 
1792 #ifdef MOZ_MEMORY_WINDOWS
1793 	VirtualFree(addr, size, MEM_DECOMMIT);
1794 #else
1795 	if (mmap(addr, size, PROT_NONE, MAP_FIXED | MAP_PRIVATE | MAP_ANON, -1,
1796 	    0) == MAP_FAILED)
1797 		abort();
1798 #endif
1799 }
1800 
1801 static inline void
pages_commit(void * addr,size_t size)1802 pages_commit(void *addr, size_t size)
1803 {
1804 
1805 #  ifdef MOZ_MEMORY_WINDOWS
1806 	VirtualAlloc(addr, size, MEM_COMMIT, PAGE_READWRITE);
1807 #  else
1808 	if (mmap(addr, size, PROT_READ | PROT_WRITE, MAP_FIXED | MAP_PRIVATE |
1809 	    MAP_ANON, -1, 0) == MAP_FAILED)
1810 		abort();
1811 #  endif
1812 }
1813 #endif
1814 
1815 static bool
base_pages_alloc_mmap(size_t minsize)1816 base_pages_alloc_mmap(size_t minsize)
1817 {
1818 	bool ret;
1819 	size_t csize;
1820 #ifdef MALLOC_DECOMMIT
1821 	size_t pminsize;
1822 #endif
1823 	int pfd;
1824 
1825 	assert(minsize != 0);
1826 	csize = CHUNK_CEILING(minsize);
1827 #ifdef MALLOC_PAGEFILE
1828 	if (opt_pagefile) {
1829 		pfd = pagefile_init(csize);
1830 		if (pfd == -1)
1831 			return (true);
1832 	} else
1833 #endif
1834 		pfd = -1;
1835 	base_pages = pages_map(NULL, csize, pfd);
1836 	if (base_pages == NULL) {
1837 		ret = true;
1838 		goto RETURN;
1839 	}
1840 	base_next_addr = base_pages;
1841 	base_past_addr = (void *)((uintptr_t)base_pages + csize);
1842 #ifdef MALLOC_DECOMMIT
1843 	/*
1844 	 * Leave enough pages for minsize committed, since otherwise they would
1845 	 * have to be immediately recommitted.
1846 	 */
1847 	pminsize = PAGE_CEILING(minsize);
1848 	base_next_decommitted = (void *)((uintptr_t)base_pages + pminsize);
1849 	if (pminsize < csize)
1850 		pages_decommit(base_next_decommitted, csize - pminsize);
1851 #endif
1852 #ifdef MALLOC_STATS
1853 	base_mapped += csize;
1854 #endif
1855 
1856 	ret = false;
1857 RETURN:
1858 #ifdef MALLOC_PAGEFILE
1859 	if (pfd != -1)
1860 		pagefile_close(pfd);
1861 #endif
1862 	return (false);
1863 }
1864 
1865 static bool
base_pages_alloc(size_t minsize)1866 base_pages_alloc(size_t minsize)
1867 {
1868 
1869 	if (base_pages_alloc_mmap(minsize) == false)
1870 		return (false);
1871 
1872 	return (true);
1873 }
1874 
1875 static void *
base_alloc(size_t size)1876 base_alloc(size_t size)
1877 {
1878 	void *ret;
1879 	size_t csize;
1880 
1881 	/* Round size up to nearest multiple of the cacheline size. */
1882 	csize = CACHELINE_CEILING(size);
1883 
1884 	malloc_mutex_lock(&base_mtx);
1885 	/* Make sure there's enough space for the allocation. */
1886 	if ((uintptr_t)base_next_addr + csize > (uintptr_t)base_past_addr) {
1887 		if (base_pages_alloc(csize)) {
1888 			malloc_mutex_unlock(&base_mtx);
1889 			return (NULL);
1890 		}
1891 	}
1892 	/* Allocate. */
1893 	ret = base_next_addr;
1894 	base_next_addr = (void *)((uintptr_t)base_next_addr + csize);
1895 #ifdef MALLOC_DECOMMIT
1896 	/* Make sure enough pages are committed for the new allocation. */
1897 	if ((uintptr_t)base_next_addr > (uintptr_t)base_next_decommitted) {
1898 		void *pbase_next_addr =
1899 		    (void *)(PAGE_CEILING((uintptr_t)base_next_addr));
1900 
1901 		pages_commit(base_next_decommitted, (uintptr_t)pbase_next_addr -
1902 		    (uintptr_t)base_next_decommitted);
1903 		base_next_decommitted = pbase_next_addr;
1904 	}
1905 #endif
1906 	malloc_mutex_unlock(&base_mtx);
1907 	VALGRIND_MALLOCLIKE_BLOCK(ret, size, 0, false);
1908 
1909 	return (ret);
1910 }
1911 
1912 static void *
base_calloc(size_t number,size_t size)1913 base_calloc(size_t number, size_t size)
1914 {
1915 	void *ret;
1916 
1917 	ret = base_alloc(number * size);
1918 #ifdef MALLOC_VALGRIND
1919 	if (ret != NULL) {
1920 		VALGRIND_FREELIKE_BLOCK(ret, 0);
1921 		VALGRIND_MALLOCLIKE_BLOCK(ret, size, 0, true);
1922 	}
1923 #endif
1924 	memset(ret, 0, number * size);
1925 
1926 	return (ret);
1927 }
1928 
1929 static extent_node_t *
base_node_alloc(void)1930 base_node_alloc(void)
1931 {
1932 	extent_node_t *ret;
1933 
1934 	malloc_mutex_lock(&base_mtx);
1935 	if (base_nodes != NULL) {
1936 		ret = base_nodes;
1937 		base_nodes = *(extent_node_t **)ret;
1938 		VALGRIND_FREELIKE_BLOCK(ret, 0);
1939 		VALGRIND_MALLOCLIKE_BLOCK(ret, sizeof(extent_node_t), 0, false);
1940 		malloc_mutex_unlock(&base_mtx);
1941 	} else {
1942 		malloc_mutex_unlock(&base_mtx);
1943 		ret = (extent_node_t *)base_alloc(sizeof(extent_node_t));
1944 	}
1945 
1946 	return (ret);
1947 }
1948 
1949 static void
base_node_dealloc(extent_node_t * node)1950 base_node_dealloc(extent_node_t *node)
1951 {
1952 
1953 	malloc_mutex_lock(&base_mtx);
1954 	VALGRIND_FREELIKE_BLOCK(node, 0);
1955 	VALGRIND_MALLOCLIKE_BLOCK(node, sizeof(extent_node_t *), 0, false);
1956 	*(extent_node_t **)node = base_nodes;
1957 	base_nodes = node;
1958 	malloc_mutex_unlock(&base_mtx);
1959 }
1960 
1961 static reserve_reg_t *
base_reserve_reg_alloc(void)1962 base_reserve_reg_alloc(void)
1963 {
1964 	reserve_reg_t *ret;
1965 
1966 	malloc_mutex_lock(&base_mtx);
1967 	if (base_reserve_regs != NULL) {
1968 		ret = base_reserve_regs;
1969 		base_reserve_regs = *(reserve_reg_t **)ret;
1970 		VALGRIND_FREELIKE_BLOCK(ret, 0);
1971 		VALGRIND_MALLOCLIKE_BLOCK(ret, sizeof(reserve_reg_t), 0, false);
1972 		malloc_mutex_unlock(&base_mtx);
1973 	} else {
1974 		malloc_mutex_unlock(&base_mtx);
1975 		ret = (reserve_reg_t *)base_alloc(sizeof(reserve_reg_t));
1976 	}
1977 
1978 	return (ret);
1979 }
1980 
1981 static void
base_reserve_reg_dealloc(reserve_reg_t * reg)1982 base_reserve_reg_dealloc(reserve_reg_t *reg)
1983 {
1984 
1985 	malloc_mutex_lock(&base_mtx);
1986 	VALGRIND_FREELIKE_BLOCK(reg, 0);
1987 	VALGRIND_MALLOCLIKE_BLOCK(reg, sizeof(reserve_reg_t *), 0, false);
1988 	*(reserve_reg_t **)reg = base_reserve_regs;
1989 	base_reserve_regs = reg;
1990 	malloc_mutex_unlock(&base_mtx);
1991 }
1992 
1993 /******************************************************************************/
1994 
1995 #ifdef MALLOC_STATS
1996 static void
stats_print(arena_t * arena)1997 stats_print(arena_t *arena)
1998 {
1999 	unsigned i, gap_start;
2000 
2001 #ifdef MOZ_MEMORY_WINDOWS
2002 	malloc_printf("dirty: %Iu page%s dirty, %I64u sweep%s,"
2003 	    " %I64u madvise%s, %I64u page%s purged\n",
2004 	    arena->ndirty, arena->ndirty == 1 ? "" : "s",
2005 	    arena->stats.npurge, arena->stats.npurge == 1 ? "" : "s",
2006 	    arena->stats.nmadvise, arena->stats.nmadvise == 1 ? "" : "s",
2007 	    arena->stats.purged, arena->stats.purged == 1 ? "" : "s");
2008 #  ifdef MALLOC_DECOMMIT
2009 	malloc_printf("decommit: %I64u decommit%s, %I64u commit%s,"
2010 	    " %I64u page%s decommitted\n",
2011 	    arena->stats.ndecommit, (arena->stats.ndecommit == 1) ? "" : "s",
2012 	    arena->stats.ncommit, (arena->stats.ncommit == 1) ? "" : "s",
2013 	    arena->stats.decommitted,
2014 	    (arena->stats.decommitted == 1) ? "" : "s");
2015 #  endif
2016 
2017 	malloc_printf("            allocated      nmalloc      ndalloc\n");
2018 	malloc_printf("small:   %12Iu %12I64u %12I64u\n",
2019 	    arena->stats.allocated_small, arena->stats.nmalloc_small,
2020 	    arena->stats.ndalloc_small);
2021 	malloc_printf("large:   %12Iu %12I64u %12I64u\n",
2022 	    arena->stats.allocated_large, arena->stats.nmalloc_large,
2023 	    arena->stats.ndalloc_large);
2024 	malloc_printf("total:   %12Iu %12I64u %12I64u\n",
2025 	    arena->stats.allocated_small + arena->stats.allocated_large,
2026 	    arena->stats.nmalloc_small + arena->stats.nmalloc_large,
2027 	    arena->stats.ndalloc_small + arena->stats.ndalloc_large);
2028 	malloc_printf("mapped:  %12Iu\n", arena->stats.mapped);
2029 #else
2030 	malloc_printf("dirty: %zu page%s dirty, %llu sweep%s,"
2031 	    " %llu madvise%s, %llu page%s purged\n",
2032 	    arena->ndirty, arena->ndirty == 1 ? "" : "s",
2033 	    arena->stats.npurge, arena->stats.npurge == 1 ? "" : "s",
2034 	    arena->stats.nmadvise, arena->stats.nmadvise == 1 ? "" : "s",
2035 	    arena->stats.purged, arena->stats.purged == 1 ? "" : "s");
2036 #  ifdef MALLOC_DECOMMIT
2037 	malloc_printf("decommit: %llu decommit%s, %llu commit%s,"
2038 	    " %llu page%s decommitted\n",
2039 	    arena->stats.ndecommit, (arena->stats.ndecommit == 1) ? "" : "s",
2040 	    arena->stats.ncommit, (arena->stats.ncommit == 1) ? "" : "s",
2041 	    arena->stats.decommitted,
2042 	    (arena->stats.decommitted == 1) ? "" : "s");
2043 #  endif
2044 
2045 	malloc_printf("            allocated      nmalloc      ndalloc\n");
2046 	malloc_printf("small:   %12zu %12llu %12llu\n",
2047 	    arena->stats.allocated_small, arena->stats.nmalloc_small,
2048 	    arena->stats.ndalloc_small);
2049 	malloc_printf("large:   %12zu %12llu %12llu\n",
2050 	    arena->stats.allocated_large, arena->stats.nmalloc_large,
2051 	    arena->stats.ndalloc_large);
2052 	malloc_printf("total:   %12zu %12llu %12llu\n",
2053 	    arena->stats.allocated_small + arena->stats.allocated_large,
2054 	    arena->stats.nmalloc_small + arena->stats.nmalloc_large,
2055 	    arena->stats.ndalloc_small + arena->stats.ndalloc_large);
2056 	malloc_printf("mapped:  %12zu\n", arena->stats.mapped);
2057 #endif
2058 	malloc_printf("bins:     bin   size regs pgs  requests   newruns"
2059 	    "    reruns maxruns curruns\n");
2060 	for (i = 0, gap_start = UINT_MAX; i < ntbins + nqbins + nsbins; i++) {
2061 		if (arena->bins[i].stats.nrequests == 0) {
2062 			if (gap_start == UINT_MAX)
2063 				gap_start = i;
2064 		} else {
2065 			if (gap_start != UINT_MAX) {
2066 				if (i > gap_start + 1) {
2067 					/* Gap of more than one size class. */
2068 					malloc_printf("[%u..%u]\n",
2069 					    gap_start, i - 1);
2070 				} else {
2071 					/* Gap of one size class. */
2072 					malloc_printf("[%u]\n", gap_start);
2073 				}
2074 				gap_start = UINT_MAX;
2075 			}
2076 			malloc_printf(
2077 #if defined(MOZ_MEMORY_WINDOWS)
2078 			    "%13u %1s %4u %4u %3u %9I64u %9I64u"
2079 			    " %9I64u %7u %7u\n",
2080 #else
2081 			    "%13u %1s %4u %4u %3u %9llu %9llu"
2082 			    " %9llu %7lu %7lu\n",
2083 #endif
2084 			    i,
2085 			    i < ntbins ? "T" : i < ntbins + nqbins ? "Q" : "S",
2086 			    arena->bins[i].reg_size,
2087 			    arena->bins[i].nregs,
2088 			    arena->bins[i].run_size >> pagesize_2pow,
2089 			    arena->bins[i].stats.nrequests,
2090 			    arena->bins[i].stats.nruns,
2091 			    arena->bins[i].stats.reruns,
2092 			    arena->bins[i].stats.highruns,
2093 			    arena->bins[i].stats.curruns);
2094 		}
2095 	}
2096 	if (gap_start != UINT_MAX) {
2097 		if (i > gap_start + 1) {
2098 			/* Gap of more than one size class. */
2099 			malloc_printf("[%u..%u]\n", gap_start, i - 1);
2100 		} else {
2101 			/* Gap of one size class. */
2102 			malloc_printf("[%u]\n", gap_start);
2103 		}
2104 	}
2105 }
2106 #endif
2107 
2108 /*
2109  * End Utility functions/macros.
2110  */
2111 /******************************************************************************/
2112 /*
2113  * Begin extent tree code.
2114  */
2115 
2116 static inline int
extent_szad_comp(extent_node_t * a,extent_node_t * b)2117 extent_szad_comp(extent_node_t *a, extent_node_t *b)
2118 {
2119 	int ret;
2120 	size_t a_size = a->size;
2121 	size_t b_size = b->size;
2122 
2123 	ret = (a_size > b_size) - (a_size < b_size);
2124 	if (ret == 0) {
2125 		uintptr_t a_addr = (uintptr_t)a->addr;
2126 		uintptr_t b_addr = (uintptr_t)b->addr;
2127 
2128 		ret = (a_addr > b_addr) - (a_addr < b_addr);
2129 	}
2130 
2131 	return (ret);
2132 }
2133 
2134 /* Wrap red-black tree macros in functions. */
rb_wrap(static,extent_tree_szad_,extent_tree_t,extent_node_t,link_szad,extent_szad_comp)2135 rb_wrap(static, extent_tree_szad_, extent_tree_t, extent_node_t,
2136     link_szad, extent_szad_comp)
2137 
2138 static inline int
2139 extent_ad_comp(extent_node_t *a, extent_node_t *b)
2140 {
2141 	uintptr_t a_addr = (uintptr_t)a->addr;
2142 	uintptr_t b_addr = (uintptr_t)b->addr;
2143 
2144 	return ((a_addr > b_addr) - (a_addr < b_addr));
2145 }
2146 
2147 /* Wrap red-black tree macros in functions. */
rb_wrap(static,extent_tree_ad_,extent_tree_t,extent_node_t,link_ad,extent_ad_comp)2148 rb_wrap(static, extent_tree_ad_, extent_tree_t, extent_node_t, link_ad,
2149     extent_ad_comp)
2150 
2151 /*
2152  * End extent tree code.
2153  */
2154 /******************************************************************************/
2155 /*
2156  * Begin chunk management functions.
2157  */
2158 
2159 #ifdef MOZ_MEMORY_WINDOWS
2160 #ifdef MOZ_MEMORY_WINCE
2161 #define ALIGN_ADDR2OFFSET(al, ad) \
2162 	((uintptr_t)ad & (al - 1))
2163 static void *
2164 pages_map_align(size_t size, int pfd, size_t alignment)
2165 {
2166 
2167 	void *ret;
2168 	int offset;
2169 	if (size % alignment)
2170 		size += (alignment - (size % alignment));
2171 	assert(size >= alignment);
2172 	ret = pages_map(NULL, size, pfd);
2173 	offset = ALIGN_ADDR2OFFSET(alignment, ret);
2174 	if (offset) {
2175 		/* try to over allocate by the ammount we're offset */
2176 		void *tmp;
2177 		pages_unmap(ret, size);
2178 		tmp = VirtualAlloc(NULL, size + alignment - offset,
2179 					 MEM_RESERVE, PAGE_NOACCESS);
2180 		if (offset == ALIGN_ADDR2OFFSET(alignment, tmp))
2181 			ret = VirtualAlloc((void*)((intptr_t)tmp + alignment
2182 						   - offset), size, MEM_COMMIT,
2183 					   PAGE_READWRITE);
2184 		else
2185 			VirtualFree(tmp, 0, MEM_RELEASE);
2186 		offset = ALIGN_ADDR2OFFSET(alignment, ret);
2187 
2188 
2189 		if (offset) {
2190 			/* over allocate to ensure we have an aligned region */
2191 			ret = VirtualAlloc(NULL, size + alignment, MEM_RESERVE,
2192 					   PAGE_NOACCESS);
2193 			offset = ALIGN_ADDR2OFFSET(alignment, ret);
2194 			ret = VirtualAlloc((void*)((intptr_t)ret +
2195 						   alignment - offset),
2196 					   size, MEM_COMMIT, PAGE_READWRITE);
2197 		}
2198 	}
2199 	return (ret);
2200 }
2201 #endif
2202 
2203 static void *
pages_map(void * addr,size_t size,int pfd)2204 pages_map(void *addr, size_t size, int pfd)
2205 {
2206 	void *ret = NULL;
2207 #if defined(MOZ_MEMORY_WINCE) && !defined(MOZ_MEMORY_WINCE6)
2208 	void *va_ret;
2209 	assert(addr == NULL);
2210 	va_ret = VirtualAlloc(addr, size, MEM_RESERVE, PAGE_NOACCESS);
2211 	if (va_ret)
2212 		ret = VirtualAlloc(va_ret, size, MEM_COMMIT, PAGE_READWRITE);
2213 	assert(va_ret == ret);
2214 #else
2215 	ret = VirtualAlloc(addr, size, MEM_COMMIT | MEM_RESERVE,
2216 	    PAGE_READWRITE);
2217 #endif
2218 	return (ret);
2219 }
2220 
2221 static void
pages_unmap(void * addr,size_t size)2222 pages_unmap(void *addr, size_t size)
2223 {
2224 	if (VirtualFree(addr, 0, MEM_RELEASE) == 0) {
2225 #if defined(MOZ_MEMORY_WINCE) && !defined(MOZ_MEMORY_WINCE6)
2226 		if (GetLastError() == ERROR_INVALID_PARAMETER) {
2227 			MEMORY_BASIC_INFORMATION info;
2228 			VirtualQuery(addr, &info, sizeof(info));
2229 			if (VirtualFree(info.AllocationBase, 0, MEM_RELEASE))
2230 				return;
2231 		}
2232 #endif
2233 		_malloc_message(_getprogname(),
2234 		    ": (malloc) Error in VirtualFree()\n", "", "");
2235 		if (opt_abort)
2236 			abort();
2237 	}
2238 }
2239 #elif (defined(MOZ_MEMORY_DARWIN))
2240 static void *
2241 pages_map(void *addr, size_t size, int pfd)
2242 {
2243 	void *ret;
2244 	kern_return_t err;
2245 	int flags;
2246 
2247 	if (addr != NULL) {
2248 		ret = addr;
2249 		flags = 0;
2250 	} else
2251 		flags = VM_FLAGS_ANYWHERE;
2252 
2253 	err = vm_allocate((vm_map_t)mach_task_self(), (vm_address_t *)&ret,
2254 	    (vm_size_t)size, flags);
2255 	if (err != KERN_SUCCESS)
2256 		ret = NULL;
2257 
2258 	assert(ret == NULL || (addr == NULL && ret != addr)
2259 	    || (addr != NULL && ret == addr));
2260 	return (ret);
2261 }
2262 
2263 static void
2264 pages_unmap(void *addr, size_t size)
2265 {
2266 	kern_return_t err;
2267 
2268 	err = vm_deallocate((vm_map_t)mach_task_self(), (vm_address_t)addr,
2269 	    (vm_size_t)size);
2270 	if (err != KERN_SUCCESS) {
2271 		malloc_message(_getprogname(),
2272 		    ": (malloc) Error in vm_deallocate(): ",
2273 		    mach_error_string(err), "\n");
2274 		if (opt_abort)
2275 			abort();
2276 	}
2277 }
2278 
2279 #define	VM_COPY_MIN (pagesize << 5)
2280 static inline void
2281 pages_copy(void *dest, const void *src, size_t n)
2282 {
2283 
2284 	assert((void *)((uintptr_t)dest & ~pagesize_mask) == dest);
2285 	assert(n >= VM_COPY_MIN);
2286 	assert((void *)((uintptr_t)src & ~pagesize_mask) == src);
2287 
2288 	vm_copy(mach_task_self(), (vm_address_t)src, (vm_size_t)n,
2289 	    (vm_address_t)dest);
2290 }
2291 #else /* MOZ_MEMORY_DARWIN */
2292 #ifdef JEMALLOC_USES_MAP_ALIGN
2293 static void *
2294 pages_map_align(size_t size, int pfd, size_t alignment)
2295 {
2296 	void *ret;
2297 
2298 	/*
2299 	 * We don't use MAP_FIXED here, because it can cause the *replacement*
2300 	 * of existing mappings, and we only want to create new mappings.
2301 	 */
2302 #ifdef MALLOC_PAGEFILE
2303 	if (pfd != -1) {
2304 		ret = mmap((void *)alignment, size, PROT_READ | PROT_WRITE, MAP_PRIVATE |
2305 		    MAP_NOSYNC | MAP_ALIGN, pfd, 0);
2306 	} else
2307 #endif
2308 	       {
2309 		ret = mmap((void *)alignment, size, PROT_READ | PROT_WRITE, MAP_PRIVATE |
2310 		    MAP_NOSYNC | MAP_ALIGN | MAP_ANON, -1, 0);
2311 	}
2312 	assert(ret != NULL);
2313 
2314 	if (ret == MAP_FAILED)
2315 		ret = NULL;
2316 	return (ret);
2317 }
2318 #endif
2319 
2320 static void *
2321 pages_map(void *addr, size_t size, int pfd)
2322 {
2323 	void *ret;
2324 
2325 	/*
2326 	 * We don't use MAP_FIXED here, because it can cause the *replacement*
2327 	 * of existing mappings, and we only want to create new mappings.
2328 	 */
2329 #ifdef MALLOC_PAGEFILE
2330 	if (pfd != -1) {
2331 		ret = mmap(addr, size, PROT_READ | PROT_WRITE, MAP_PRIVATE |
2332 		    MAP_NOSYNC, pfd, 0);
2333 	} else
2334 #endif
2335 	       {
2336 		ret = mmap(addr, size, PROT_READ | PROT_WRITE, MAP_PRIVATE |
2337 		    MAP_ANON, -1, 0);
2338 	}
2339 	assert(ret != NULL);
2340 
2341 	if (ret == MAP_FAILED)
2342 		ret = NULL;
2343 	else if (addr != NULL && ret != addr) {
2344 		/*
2345 		 * We succeeded in mapping memory, but not in the right place.
2346 		 */
2347 		if (munmap(ret, size) == -1) {
2348 			char buf[STRERROR_BUF];
2349 
2350 			strerror_r(errno, buf, sizeof(buf));
2351 			_malloc_message(_getprogname(),
2352 			    ": (malloc) Error in munmap(): ", buf, "\n");
2353 			if (opt_abort)
2354 				abort();
2355 		}
2356 		ret = NULL;
2357 	}
2358 
2359 	assert(ret == NULL || (addr == NULL && ret != addr)
2360 	    || (addr != NULL && ret == addr));
2361 	return (ret);
2362 }
2363 
2364 static void
2365 pages_unmap(void *addr, size_t size)
2366 {
2367 
2368 	if (munmap(addr, size) == -1) {
2369 		char buf[STRERROR_BUF];
2370 
2371 		strerror_r(errno, buf, sizeof(buf));
2372 		_malloc_message(_getprogname(),
2373 		    ": (malloc) Error in munmap(): ", buf, "\n");
2374 		if (opt_abort)
2375 			abort();
2376 	}
2377 }
2378 #endif
2379 
2380 #ifdef MALLOC_VALIDATE
2381 static inline malloc_rtree_t *
malloc_rtree_new(unsigned bits)2382 malloc_rtree_new(unsigned bits)
2383 {
2384 	malloc_rtree_t *ret;
2385 	unsigned bits_per_level, height, i;
2386 
2387 	bits_per_level = ffs(pow2_ceil((MALLOC_RTREE_NODESIZE /
2388 	    sizeof(void *)))) - 1;
2389 	height = bits / bits_per_level;
2390 	if (height * bits_per_level != bits)
2391 		height++;
2392 	assert(height * bits_per_level >= bits);
2393 
2394 	ret = (malloc_rtree_t*)base_calloc(1, sizeof(malloc_rtree_t) + (sizeof(unsigned) *
2395 	    (height - 1)));
2396 	if (ret == NULL)
2397 		return (NULL);
2398 
2399 	malloc_spin_init(&ret->lock);
2400 	ret->height = height;
2401 	if (bits_per_level * height > bits)
2402 		ret->level2bits[0] = bits % bits_per_level;
2403 	else
2404 		ret->level2bits[0] = bits_per_level;
2405 	for (i = 1; i < height; i++)
2406 		ret->level2bits[i] = bits_per_level;
2407 
2408 	ret->root = (void**)base_calloc(1, sizeof(void *) << ret->level2bits[0]);
2409 	if (ret->root == NULL) {
2410 		/*
2411 		 * We leak the rtree here, since there's no generic base
2412 		 * deallocation.
2413 		 */
2414 		return (NULL);
2415 	}
2416 
2417 	return (ret);
2418 }
2419 
2420 /* The least significant bits of the key are ignored. */
2421 static inline void *
malloc_rtree_get(malloc_rtree_t * rtree,uintptr_t key)2422 malloc_rtree_get(malloc_rtree_t *rtree, uintptr_t key)
2423 {
2424 	void *ret;
2425 	uintptr_t subkey;
2426 	unsigned i, lshift, height, bits;
2427 	void **node, **child;
2428 
2429 	malloc_spin_lock(&rtree->lock);
2430 	for (i = lshift = 0, height = rtree->height, node = rtree->root;
2431 	    i < height - 1;
2432 	    i++, lshift += bits, node = child) {
2433 		bits = rtree->level2bits[i];
2434 		subkey = (key << lshift) >> ((SIZEOF_PTR << 3) - bits);
2435 		child = (void**)node[subkey];
2436 		if (child == NULL) {
2437 			malloc_spin_unlock(&rtree->lock);
2438 			return (NULL);
2439 		}
2440 	}
2441 
2442 	/* node is a leaf, so it contains values rather than node pointers. */
2443 	bits = rtree->level2bits[i];
2444 	subkey = (key << lshift) >> ((SIZEOF_PTR << 3) - bits);
2445 	ret = node[subkey];
2446 	malloc_spin_unlock(&rtree->lock);
2447 
2448 	return (ret);
2449 }
2450 
2451 static inline bool
malloc_rtree_set(malloc_rtree_t * rtree,uintptr_t key,void * val)2452 malloc_rtree_set(malloc_rtree_t *rtree, uintptr_t key, void *val)
2453 {
2454 	uintptr_t subkey;
2455 	unsigned i, lshift, height, bits;
2456 	void **node, **child;
2457 
2458 	malloc_spin_lock(&rtree->lock);
2459 	for (i = lshift = 0, height = rtree->height, node = rtree->root;
2460 	    i < height - 1;
2461 	    i++, lshift += bits, node = child) {
2462 		bits = rtree->level2bits[i];
2463 		subkey = (key << lshift) >> ((SIZEOF_PTR << 3) - bits);
2464 		child = (void**)node[subkey];
2465 		if (child == NULL) {
2466 			child = (void**)base_calloc(1, sizeof(void *) <<
2467 			    rtree->level2bits[i+1]);
2468 			if (child == NULL) {
2469 				malloc_spin_unlock(&rtree->lock);
2470 				return (true);
2471 			}
2472 			node[subkey] = child;
2473 		}
2474 	}
2475 
2476 	/* node is a leaf, so it contains values rather than node pointers. */
2477 	bits = rtree->level2bits[i];
2478 	subkey = (key << lshift) >> ((SIZEOF_PTR << 3) - bits);
2479 	node[subkey] = val;
2480 	malloc_spin_unlock(&rtree->lock);
2481 
2482 	return (false);
2483 }
2484 #endif
2485 
2486 static void *
chunk_alloc_mmap(size_t size,bool pagefile)2487 chunk_alloc_mmap(size_t size, bool pagefile)
2488 {
2489 	void *ret;
2490 #ifndef JEMALLOC_USES_MAP_ALIGN
2491 	size_t offset;
2492 #endif
2493 	int pfd;
2494 
2495 #ifdef MALLOC_PAGEFILE
2496 	if (opt_pagefile && pagefile) {
2497 		pfd = pagefile_init(size);
2498 		if (pfd == -1)
2499 			return (NULL);
2500 	} else
2501 #endif
2502 		pfd = -1;
2503 
2504 	/*
2505 	 * Windows requires that there be a 1:1 mapping between VM
2506 	 * allocation/deallocation operations.  Therefore, take care here to
2507 	 * acquire the final result via one mapping operation.  This means
2508 	 * unmapping any preliminary result that is not correctly aligned.
2509 	 *
2510 	 * The MALLOC_PAGEFILE code also benefits from this mapping algorithm,
2511 	 * since it reduces the number of page files.
2512 	 */
2513 
2514 #ifdef JEMALLOC_USES_MAP_ALIGN
2515 	ret = pages_map_align(size, pfd, chunksize);
2516 #else
2517 	ret = pages_map(NULL, size, pfd);
2518 	if (ret == NULL)
2519 		goto RETURN;
2520 
2521 	offset = CHUNK_ADDR2OFFSET(ret);
2522 	if (offset != 0) {
2523 		/* Deallocate, then try to allocate at (ret + size - offset). */
2524 		pages_unmap(ret, size);
2525 		ret = pages_map((void *)((uintptr_t)ret + size - offset), size,
2526 		    pfd);
2527 		while (ret == NULL) {
2528 			/*
2529 			 * Over-allocate in order to map a memory region that
2530 			 * is definitely large enough.
2531 			 */
2532 			ret = pages_map(NULL, size + chunksize, -1);
2533 			if (ret == NULL)
2534 				goto RETURN;
2535 			/*
2536 			 * Deallocate, then allocate the correct size, within
2537 			 * the over-sized mapping.
2538 			 */
2539 			offset = CHUNK_ADDR2OFFSET(ret);
2540 			pages_unmap(ret, size + chunksize);
2541 			if (offset == 0)
2542 				ret = pages_map(ret, size, pfd);
2543 			else {
2544 				ret = pages_map((void *)((uintptr_t)ret +
2545 				    chunksize - offset), size, pfd);
2546 			}
2547 			/*
2548 			 * Failure here indicates a race with another thread, so
2549 			 * try again.
2550 			 */
2551 		}
2552 	}
2553 RETURN:
2554 #endif
2555 #ifdef MALLOC_PAGEFILE
2556 	if (pfd != -1)
2557 		pagefile_close(pfd);
2558 #endif
2559 #ifdef MALLOC_STATS
2560 	if (ret != NULL)
2561 		stats_chunks.nchunks += (size / chunksize);
2562 #endif
2563 	return (ret);
2564 }
2565 
2566 #ifdef MALLOC_PAGEFILE
2567 static int
pagefile_init(size_t size)2568 pagefile_init(size_t size)
2569 {
2570 	int ret;
2571 	size_t i;
2572 	char pagefile_path[PATH_MAX];
2573 	char zbuf[MALLOC_PAGEFILE_WRITE_SIZE];
2574 
2575 	/*
2576 	 * Create a temporary file, then immediately unlink it so that it will
2577 	 * not persist.
2578 	 */
2579 	strcpy(pagefile_path, pagefile_templ);
2580 	ret = mkstemp(pagefile_path);
2581 	if (ret == -1)
2582 		return (ret);
2583 	if (unlink(pagefile_path)) {
2584 		char buf[STRERROR_BUF];
2585 
2586 		strerror_r(errno, buf, sizeof(buf));
2587 		_malloc_message(_getprogname(), ": (malloc) Error in unlink(\"",
2588 		    pagefile_path, "\"):");
2589 		_malloc_message(buf, "\n", "", "");
2590 		if (opt_abort)
2591 			abort();
2592 	}
2593 
2594 	/*
2595 	 * Write sequential zeroes to the file in order to assure that disk
2596 	 * space is committed, with minimal fragmentation.  It would be
2597 	 * sufficient to write one zero per disk block, but that potentially
2598 	 * results in more system calls, for no real gain.
2599 	 */
2600 	memset(zbuf, 0, sizeof(zbuf));
2601 	for (i = 0; i < size; i += sizeof(zbuf)) {
2602 		if (write(ret, zbuf, sizeof(zbuf)) != sizeof(zbuf)) {
2603 			if (errno != ENOSPC) {
2604 				char buf[STRERROR_BUF];
2605 
2606 				strerror_r(errno, buf, sizeof(buf));
2607 				_malloc_message(_getprogname(),
2608 				    ": (malloc) Error in write(): ", buf, "\n");
2609 				if (opt_abort)
2610 					abort();
2611 			}
2612 			pagefile_close(ret);
2613 			return (-1);
2614 		}
2615 	}
2616 
2617 	return (ret);
2618 }
2619 
2620 static void
pagefile_close(int pfd)2621 pagefile_close(int pfd)
2622 {
2623 
2624 	if (close(pfd)) {
2625 		char buf[STRERROR_BUF];
2626 
2627 		strerror_r(errno, buf, sizeof(buf));
2628 		_malloc_message(_getprogname(),
2629 		    ": (malloc) Error in close(): ", buf, "\n");
2630 		if (opt_abort)
2631 			abort();
2632 	}
2633 }
2634 #endif
2635 
2636 static void *
chunk_recycle_reserve(size_t size,bool zero)2637 chunk_recycle_reserve(size_t size, bool zero)
2638 {
2639 	extent_node_t *node, key;
2640 
2641 #ifdef MALLOC_DECOMMIT
2642 	if (size != chunksize)
2643 		return (NULL);
2644 #endif
2645 
2646 	key.addr = NULL;
2647 	key.size = size;
2648 	malloc_mutex_lock(&reserve_mtx);
2649 	node = extent_tree_szad_nsearch(&reserve_chunks_szad, &key);
2650 	if (node != NULL) {
2651 		void *ret = node->addr;
2652 
2653 		/* Remove node from the tree. */
2654 		extent_tree_szad_remove(&reserve_chunks_szad, node);
2655 #ifndef MALLOC_DECOMMIT
2656 		if (node->size == size) {
2657 #else
2658 			assert(node->size == size);
2659 #endif
2660 			extent_tree_ad_remove(&reserve_chunks_ad, node);
2661 			base_node_dealloc(node);
2662 #ifndef MALLOC_DECOMMIT
2663 		} else {
2664 			/*
2665 			 * Insert the remainder of node's address range as a
2666 			 * smaller chunk.  Its position within reserve_chunks_ad
2667 			 * does not change.
2668 			 */
2669 			assert(node->size > size);
2670 			node->addr = (void *)((uintptr_t)node->addr + size);
2671 			node->size -= size;
2672 			extent_tree_szad_insert(&reserve_chunks_szad, node);
2673 		}
2674 #endif
2675 		reserve_cur -= size;
2676 		/*
2677 		 * Try to replenish the reserve if this allocation depleted it.
2678 		 */
2679 #ifndef MALLOC_DECOMMIT
2680 		if (reserve_cur < reserve_min) {
2681 			size_t diff = reserve_min - reserve_cur;
2682 #else
2683 		while (reserve_cur < reserve_min) {
2684 #  define diff chunksize
2685 #endif
2686 			void *chunk;
2687 
2688 			malloc_mutex_unlock(&reserve_mtx);
2689 			chunk = chunk_alloc_mmap(diff, true);
2690 			malloc_mutex_lock(&reserve_mtx);
2691 			if (chunk == NULL) {
2692 				uint64_t seq = 0;
2693 
2694 				do {
2695 					seq = reserve_notify(RESERVE_CND_LOW,
2696 					    size, seq);
2697 					if (seq == 0)
2698 						goto MALLOC_OUT;
2699 				} while (reserve_cur < reserve_min);
2700 			} else {
2701 				extent_node_t *node;
2702 
2703 				node = chunk_dealloc_reserve(chunk, diff);
2704 				if (node == NULL) {
2705 					uint64_t seq = 0;
2706 
2707 					pages_unmap(chunk, diff);
2708 					do {
2709 						seq = reserve_notify(
2710 						    RESERVE_CND_LOW, size, seq);
2711 						if (seq == 0)
2712 							goto MALLOC_OUT;
2713 					} while (reserve_cur < reserve_min);
2714 				}
2715 			}
2716 		}
2717 MALLOC_OUT:
2718 		malloc_mutex_unlock(&reserve_mtx);
2719 
2720 #ifdef MALLOC_DECOMMIT
2721 		pages_commit(ret, size);
2722 #  undef diff
2723 #else
2724 		if (zero)
2725 			memset(ret, 0, size);
2726 #endif
2727 		return (ret);
2728 	}
2729 	malloc_mutex_unlock(&reserve_mtx);
2730 
2731 	return (NULL);
2732 }
2733 
2734 static void *
2735 chunk_alloc(size_t size, bool zero, bool pagefile)
2736 {
2737 	void *ret;
2738 
2739 	assert(size != 0);
2740 	assert((size & chunksize_mask) == 0);
2741 
2742 	ret = chunk_recycle_reserve(size, zero);
2743 	if (ret != NULL)
2744 		goto RETURN;
2745 
2746 	ret = chunk_alloc_mmap(size, pagefile);
2747 	if (ret != NULL) {
2748 		goto RETURN;
2749 	}
2750 
2751 	/* All strategies for allocation failed. */
2752 	ret = NULL;
2753 RETURN:
2754 #ifdef MALLOC_STATS
2755 	if (ret != NULL)
2756 		stats_chunks.curchunks += (size / chunksize);
2757 	if (stats_chunks.curchunks > stats_chunks.highchunks)
2758 		stats_chunks.highchunks = stats_chunks.curchunks;
2759 #endif
2760 
2761 #ifdef MALLOC_VALIDATE
2762 	if (ret != NULL) {
2763 		if (malloc_rtree_set(chunk_rtree, (uintptr_t)ret, ret)) {
2764 			chunk_dealloc(ret, size);
2765 			return (NULL);
2766 		}
2767 	}
2768 #endif
2769 
2770 	assert(CHUNK_ADDR2BASE(ret) == ret);
2771 	return (ret);
2772 }
2773 
2774 static extent_node_t *
2775 chunk_dealloc_reserve(void *chunk, size_t size)
2776 {
2777 	extent_node_t *node;
2778 
2779 #ifdef MALLOC_DECOMMIT
2780 	if (size != chunksize)
2781 		return (NULL);
2782 #else
2783 	extent_node_t *prev, key;
2784 
2785 	key.addr = (void *)((uintptr_t)chunk + size);
2786 	node = extent_tree_ad_nsearch(&reserve_chunks_ad, &key);
2787 	/* Try to coalesce forward. */
2788 	if (node != NULL && node->addr == key.addr) {
2789 		/*
2790 		 * Coalesce chunk with the following address range.  This does
2791 		 * not change the position within reserve_chunks_ad, so only
2792 		 * remove/insert from/into reserve_chunks_szad.
2793 		 */
2794 		extent_tree_szad_remove(&reserve_chunks_szad, node);
2795 		node->addr = chunk;
2796 		node->size += size;
2797 		extent_tree_szad_insert(&reserve_chunks_szad, node);
2798 	} else {
2799 #endif
2800 		/* Coalescing forward failed, so insert a new node. */
2801 		node = base_node_alloc();
2802 		if (node == NULL)
2803 			return (NULL);
2804 		node->addr = chunk;
2805 		node->size = size;
2806 		extent_tree_ad_insert(&reserve_chunks_ad, node);
2807 		extent_tree_szad_insert(&reserve_chunks_szad, node);
2808 #ifndef MALLOC_DECOMMIT
2809 	}
2810 
2811 	/* Try to coalesce backward. */
2812 	prev = extent_tree_ad_prev(&reserve_chunks_ad, node);
2813 	if (prev != NULL && (void *)((uintptr_t)prev->addr + prev->size) ==
2814 	    chunk) {
2815 		/*
2816 		 * Coalesce chunk with the previous address range.  This does
2817 		 * not change the position within reserve_chunks_ad, so only
2818 		 * remove/insert node from/into reserve_chunks_szad.
2819 		 */
2820 		extent_tree_szad_remove(&reserve_chunks_szad, prev);
2821 		extent_tree_ad_remove(&reserve_chunks_ad, prev);
2822 
2823 		extent_tree_szad_remove(&reserve_chunks_szad, node);
2824 		node->addr = prev->addr;
2825 		node->size += prev->size;
2826 		extent_tree_szad_insert(&reserve_chunks_szad, node);
2827 
2828 		base_node_dealloc(prev);
2829 	}
2830 #endif
2831 
2832 #ifdef MALLOC_DECOMMIT
2833 	pages_decommit(chunk, size);
2834 #else
2835 	madvise(chunk, size, MADV_FREE);
2836 #endif
2837 
2838 	reserve_cur += size;
2839 	if (reserve_cur > reserve_max)
2840 		reserve_shrink();
2841 
2842 	return (node);
2843 }
2844 
2845 static void
2846 chunk_dealloc_mmap(void *chunk, size_t size)
2847 {
2848 
2849 	pages_unmap(chunk, size);
2850 }
2851 
2852 static void
2853 chunk_dealloc(void *chunk, size_t size)
2854 {
2855 	extent_node_t *node;
2856 
2857 	assert(chunk != NULL);
2858 	assert(CHUNK_ADDR2BASE(chunk) == chunk);
2859 	assert(size != 0);
2860 	assert((size & chunksize_mask) == 0);
2861 
2862 #ifdef MALLOC_STATS
2863 	stats_chunks.curchunks -= (size / chunksize);
2864 #endif
2865 #ifdef MALLOC_VALIDATE
2866 	malloc_rtree_set(chunk_rtree, (uintptr_t)chunk, NULL);
2867 #endif
2868 
2869 	/* Try to merge chunk into the reserve. */
2870 	malloc_mutex_lock(&reserve_mtx);
2871 	node = chunk_dealloc_reserve(chunk, size);
2872 	malloc_mutex_unlock(&reserve_mtx);
2873 	if (node == NULL)
2874 		chunk_dealloc_mmap(chunk, size);
2875 }
2876 
2877 /*
2878  * End chunk management functions.
2879  */
2880 /******************************************************************************/
2881 /*
2882  * Begin arena.
2883  */
2884 
2885 /*
2886  * Choose an arena based on a per-thread value (fast-path code, calls slow-path
2887  * code if necessary).
2888  */
2889 static inline arena_t *
2890 choose_arena(void)
2891 {
2892 	arena_t *ret;
2893 
2894 	/*
2895 	 * We can only use TLS if this is a PIC library, since for the static
2896 	 * library version, libc's malloc is used by TLS allocation, which
2897 	 * introduces a bootstrapping issue.
2898 	 */
2899 #ifndef NO_TLS
2900 	if (__isthreaded == false) {
2901 	    /* Avoid the overhead of TLS for single-threaded operation. */
2902 	    return (arenas[0]);
2903 	}
2904 
2905 #  ifdef MOZ_MEMORY_WINDOWS
2906 	ret = (arena_t*)TlsGetValue(tlsIndex);
2907 #  else
2908 	ret = arenas_map;
2909 #  endif
2910 
2911 	if (ret == NULL) {
2912 		ret = choose_arena_hard();
2913 		assert(ret != NULL);
2914 	}
2915 #else
2916 	if (__isthreaded && narenas > 1) {
2917 		unsigned long ind;
2918 
2919 		/*
2920 		 * Hash _pthread_self() to one of the arenas.  There is a prime
2921 		 * number of arenas, so this has a reasonable chance of
2922 		 * working.  Even so, the hashing can be easily thwarted by
2923 		 * inconvenient _pthread_self() values.  Without specific
2924 		 * knowledge of how _pthread_self() calculates values, we can't
2925 		 * easily do much better than this.
2926 		 */
2927 		ind = (unsigned long) _pthread_self() % narenas;
2928 
2929 		/*
2930 		 * Optimistially assume that arenas[ind] has been initialized.
2931 		 * At worst, we find out that some other thread has already
2932 		 * done so, after acquiring the lock in preparation.  Note that
2933 		 * this lazy locking also has the effect of lazily forcing
2934 		 * cache coherency; without the lock acquisition, there's no
2935 		 * guarantee that modification of arenas[ind] by another thread
2936 		 * would be seen on this CPU for an arbitrary amount of time.
2937 		 *
2938 		 * In general, this approach to modifying a synchronized value
2939 		 * isn't a good idea, but in this case we only ever modify the
2940 		 * value once, so things work out well.
2941 		 */
2942 		ret = arenas[ind];
2943 		if (ret == NULL) {
2944 			/*
2945 			 * Avoid races with another thread that may have already
2946 			 * initialized arenas[ind].
2947 			 */
2948 			malloc_spin_lock(&arenas_lock);
2949 			if (arenas[ind] == NULL)
2950 				ret = arenas_extend((unsigned)ind);
2951 			else
2952 				ret = arenas[ind];
2953 			malloc_spin_unlock(&arenas_lock);
2954 		}
2955 	} else
2956 		ret = arenas[0];
2957 #endif
2958 
2959 	assert(ret != NULL);
2960 	return (ret);
2961 }
2962 
2963 #ifndef NO_TLS
2964 /*
2965  * Choose an arena based on a per-thread value (slow-path code only, called
2966  * only by choose_arena()).
2967  */
2968 static arena_t *
2969 choose_arena_hard(void)
2970 {
2971 	arena_t *ret;
2972 
2973 	assert(__isthreaded);
2974 
2975 #ifdef MALLOC_BALANCE
2976 	/* Seed the PRNG used for arena load balancing. */
2977 	SPRN(balance, (uint32_t)(uintptr_t)(_pthread_self()));
2978 #endif
2979 
2980 	if (narenas > 1) {
2981 #ifdef MALLOC_BALANCE
2982 		unsigned ind;
2983 
2984 		ind = PRN(balance, narenas_2pow);
2985 		if ((ret = arenas[ind]) == NULL) {
2986 			malloc_spin_lock(&arenas_lock);
2987 			if ((ret = arenas[ind]) == NULL)
2988 				ret = arenas_extend(ind);
2989 			malloc_spin_unlock(&arenas_lock);
2990 		}
2991 #else
2992 		malloc_spin_lock(&arenas_lock);
2993 		if ((ret = arenas[next_arena]) == NULL)
2994 			ret = arenas_extend(next_arena);
2995 		next_arena = (next_arena + 1) % narenas;
2996 		malloc_spin_unlock(&arenas_lock);
2997 #endif
2998 	} else
2999 		ret = arenas[0];
3000 
3001 #ifdef MOZ_MEMORY_WINDOWS
3002 	TlsSetValue(tlsIndex, ret);
3003 #else
3004 	arenas_map = ret;
3005 #endif
3006 
3007 	return (ret);
3008 }
3009 #endif
3010 
3011 static inline int
3012 arena_chunk_comp(arena_chunk_t *a, arena_chunk_t *b)
3013 {
3014 	uintptr_t a_chunk = (uintptr_t)a;
3015 	uintptr_t b_chunk = (uintptr_t)b;
3016 
3017 	assert(a != NULL);
3018 	assert(b != NULL);
3019 
3020 	return ((a_chunk > b_chunk) - (a_chunk < b_chunk));
3021 }
3022 
3023 /* Wrap red-black tree macros in functions. */
3024 rb_wrap(static, arena_chunk_tree_dirty_, arena_chunk_tree_t,
3025     arena_chunk_t, link_dirty, arena_chunk_comp)
3026 
3027 static inline int
3028 arena_run_comp(arena_chunk_map_t *a, arena_chunk_map_t *b)
3029 {
3030 	uintptr_t a_mapelm = (uintptr_t)a;
3031 	uintptr_t b_mapelm = (uintptr_t)b;
3032 
3033 	assert(a != NULL);
3034 	assert(b != NULL);
3035 
3036 	return ((a_mapelm > b_mapelm) - (a_mapelm < b_mapelm));
3037 }
3038 
3039 /* Wrap red-black tree macros in functions. */
3040 rb_wrap(static, arena_run_tree_, arena_run_tree_t, arena_chunk_map_t, link,
3041     arena_run_comp)
3042 
3043 static inline int
3044 arena_avail_comp(arena_chunk_map_t *a, arena_chunk_map_t *b)
3045 {
3046 	int ret;
3047 	size_t a_size = a->bits & ~pagesize_mask;
3048 	size_t b_size = b->bits & ~pagesize_mask;
3049 
3050 	ret = (a_size > b_size) - (a_size < b_size);
3051 	if (ret == 0) {
3052 		uintptr_t a_mapelm, b_mapelm;
3053 
3054 		if ((a->bits & CHUNK_MAP_KEY) == 0)
3055 			a_mapelm = (uintptr_t)a;
3056 		else {
3057 			/*
3058 			 * Treat keys as though they are lower than anything
3059 			 * else.
3060 			 */
3061 			a_mapelm = 0;
3062 		}
3063 		b_mapelm = (uintptr_t)b;
3064 
3065 		ret = (a_mapelm > b_mapelm) - (a_mapelm < b_mapelm);
3066 	}
3067 
3068 	return (ret);
3069 }
3070 
3071 /* Wrap red-black tree macros in functions. */
3072 rb_wrap(static, arena_avail_tree_, arena_avail_tree_t, arena_chunk_map_t, link,
3073     arena_avail_comp)
3074 
3075 static inline void *
3076 arena_run_reg_alloc(arena_run_t *run, arena_bin_t *bin)
3077 {
3078 	void *ret;
3079 	unsigned i, mask, bit, regind;
3080 
3081 	assert(run->magic == ARENA_RUN_MAGIC);
3082 	assert(run->regs_minelm < bin->regs_mask_nelms);
3083 
3084 	/*
3085 	 * Move the first check outside the loop, so that run->regs_minelm can
3086 	 * be updated unconditionally, without the possibility of updating it
3087 	 * multiple times.
3088 	 */
3089 	i = run->regs_minelm;
3090 	mask = run->regs_mask[i];
3091 	if (mask != 0) {
3092 		/* Usable allocation found. */
3093 		bit = ffs((int)mask) - 1;
3094 
3095 		regind = ((i << (SIZEOF_INT_2POW + 3)) + bit);
3096 		assert(regind < bin->nregs);
3097 		ret = (void *)(((uintptr_t)run) + bin->reg0_offset
3098 		    + (bin->reg_size * regind));
3099 
3100 		/* Clear bit. */
3101 		mask ^= (1U << bit);
3102 		run->regs_mask[i] = mask;
3103 
3104 		return (ret);
3105 	}
3106 
3107 	for (i++; i < bin->regs_mask_nelms; i++) {
3108 		mask = run->regs_mask[i];
3109 		if (mask != 0) {
3110 			/* Usable allocation found. */
3111 			bit = ffs((int)mask) - 1;
3112 
3113 			regind = ((i << (SIZEOF_INT_2POW + 3)) + bit);
3114 			assert(regind < bin->nregs);
3115 			ret = (void *)(((uintptr_t)run) + bin->reg0_offset
3116 			    + (bin->reg_size * regind));
3117 
3118 			/* Clear bit. */
3119 			mask ^= (1U << bit);
3120 			run->regs_mask[i] = mask;
3121 
3122 			/*
3123 			 * Make a note that nothing before this element
3124 			 * contains a free region.
3125 			 */
3126 			run->regs_minelm = i; /* Low payoff: + (mask == 0); */
3127 
3128 			return (ret);
3129 		}
3130 	}
3131 	/* Not reached. */
3132 	assert(0);
3133 	return (NULL);
3134 }
3135 
3136 static inline void
3137 arena_run_reg_dalloc(arena_run_t *run, arena_bin_t *bin, void *ptr, size_t size)
3138 {
3139 	/*
3140 	 * To divide by a number D that is not a power of two we multiply
3141 	 * by (2^21 / D) and then right shift by 21 positions.
3142 	 *
3143 	 *   X / D
3144 	 *
3145 	 * becomes
3146 	 *
3147 	 *   (X * size_invs[(D >> QUANTUM_2POW_MIN) - 3]) >> SIZE_INV_SHIFT
3148 	 */
3149 #define	SIZE_INV_SHIFT 21
3150 #define	SIZE_INV(s) (((1U << SIZE_INV_SHIFT) / (s << QUANTUM_2POW_MIN)) + 1)
3151 	static const unsigned size_invs[] = {
3152 	    SIZE_INV(3),
3153 	    SIZE_INV(4), SIZE_INV(5), SIZE_INV(6), SIZE_INV(7),
3154 	    SIZE_INV(8), SIZE_INV(9), SIZE_INV(10), SIZE_INV(11),
3155 	    SIZE_INV(12),SIZE_INV(13), SIZE_INV(14), SIZE_INV(15),
3156 	    SIZE_INV(16),SIZE_INV(17), SIZE_INV(18), SIZE_INV(19),
3157 	    SIZE_INV(20),SIZE_INV(21), SIZE_INV(22), SIZE_INV(23),
3158 	    SIZE_INV(24),SIZE_INV(25), SIZE_INV(26), SIZE_INV(27),
3159 	    SIZE_INV(28),SIZE_INV(29), SIZE_INV(30), SIZE_INV(31)
3160 #if (QUANTUM_2POW_MIN < 4)
3161 	    ,
3162 	    SIZE_INV(32), SIZE_INV(33), SIZE_INV(34), SIZE_INV(35),
3163 	    SIZE_INV(36), SIZE_INV(37), SIZE_INV(38), SIZE_INV(39),
3164 	    SIZE_INV(40), SIZE_INV(41), SIZE_INV(42), SIZE_INV(43),
3165 	    SIZE_INV(44), SIZE_INV(45), SIZE_INV(46), SIZE_INV(47),
3166 	    SIZE_INV(48), SIZE_INV(49), SIZE_INV(50), SIZE_INV(51),
3167 	    SIZE_INV(52), SIZE_INV(53), SIZE_INV(54), SIZE_INV(55),
3168 	    SIZE_INV(56), SIZE_INV(57), SIZE_INV(58), SIZE_INV(59),
3169 	    SIZE_INV(60), SIZE_INV(61), SIZE_INV(62), SIZE_INV(63)
3170 #endif
3171 	};
3172 	unsigned diff, regind, elm, bit;
3173 
3174 	assert(run->magic == ARENA_RUN_MAGIC);
3175 	assert(((sizeof(size_invs)) / sizeof(unsigned)) + 3
3176 	    >= (SMALL_MAX_DEFAULT >> QUANTUM_2POW_MIN));
3177 
3178 	/*
3179 	 * Avoid doing division with a variable divisor if possible.  Using
3180 	 * actual division here can reduce allocator throughput by over 20%!
3181 	 */
3182 	diff = (unsigned)((uintptr_t)ptr - (uintptr_t)run - bin->reg0_offset);
3183 	if ((size & (size - 1)) == 0) {
3184 		/*
3185 		 * log2_table allows fast division of a power of two in the
3186 		 * [1..128] range.
3187 		 *
3188 		 * (x / divisor) becomes (x >> log2_table[divisor - 1]).
3189 		 */
3190 		static const unsigned char log2_table[] = {
3191 		    0, 1, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 4,
3192 		    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5,
3193 		    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
3194 		    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6,
3195 		    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
3196 		    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
3197 		    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
3198 		    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7
3199 		};
3200 
3201 		if (size <= 128)
3202 			regind = (diff >> log2_table[size - 1]);
3203 		else if (size <= 32768)
3204 			regind = diff >> (8 + log2_table[(size >> 8) - 1]);
3205 		else {
3206 			/*
3207 			 * The run size is too large for us to use the lookup
3208 			 * table.  Use real division.
3209 			 */
3210 			regind = diff / size;
3211 		}
3212 	} else if (size <= ((sizeof(size_invs) / sizeof(unsigned))
3213 	    << QUANTUM_2POW_MIN) + 2) {
3214 		regind = size_invs[(size >> QUANTUM_2POW_MIN) - 3] * diff;
3215 		regind >>= SIZE_INV_SHIFT;
3216 	} else {
3217 		/*
3218 		 * size_invs isn't large enough to handle this size class, so
3219 		 * calculate regind using actual division.  This only happens
3220 		 * if the user increases small_max via the 'S' runtime
3221 		 * configuration option.
3222 		 */
3223 		regind = diff / size;
3224 	};
3225 	assert(diff == regind * size);
3226 	assert(regind < bin->nregs);
3227 
3228 	elm = regind >> (SIZEOF_INT_2POW + 3);
3229 	if (elm < run->regs_minelm)
3230 		run->regs_minelm = elm;
3231 	bit = regind - (elm << (SIZEOF_INT_2POW + 3));
3232 	assert((run->regs_mask[elm] & (1U << bit)) == 0);
3233 	run->regs_mask[elm] |= (1U << bit);
3234 #undef SIZE_INV
3235 #undef SIZE_INV_SHIFT
3236 }
3237 
3238 static void
3239 arena_run_split(arena_t *arena, arena_run_t *run, size_t size, bool large,
3240     bool zero)
3241 {
3242 	arena_chunk_t *chunk;
3243 	size_t old_ndirty, run_ind, total_pages, need_pages, rem_pages, i;
3244 
3245 	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
3246 	old_ndirty = chunk->ndirty;
3247 	run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk)
3248 	    >> pagesize_2pow);
3249 	total_pages = (chunk->map[run_ind].bits & ~pagesize_mask) >>
3250 	    pagesize_2pow;
3251 	need_pages = (size >> pagesize_2pow);
3252 	assert(need_pages > 0);
3253 	assert(need_pages <= total_pages);
3254 	rem_pages = total_pages - need_pages;
3255 
3256 	arena_avail_tree_remove(&arena->runs_avail, &chunk->map[run_ind]);
3257 
3258 	/* Keep track of trailing unused pages for later use. */
3259 	if (rem_pages > 0) {
3260 		chunk->map[run_ind+need_pages].bits = (rem_pages <<
3261 		    pagesize_2pow) | (chunk->map[run_ind+need_pages].bits &
3262 		    pagesize_mask);
3263 		chunk->map[run_ind+total_pages-1].bits = (rem_pages <<
3264 		    pagesize_2pow) | (chunk->map[run_ind+total_pages-1].bits &
3265 		    pagesize_mask);
3266 		arena_avail_tree_insert(&arena->runs_avail,
3267 		    &chunk->map[run_ind+need_pages]);
3268 	}
3269 
3270 	for (i = 0; i < need_pages; i++) {
3271 #ifdef MALLOC_DECOMMIT
3272 		/*
3273 		 * Commit decommitted pages if necessary.  If a decommitted
3274 		 * page is encountered, commit all needed adjacent decommitted
3275 		 * pages in one operation, in order to reduce system call
3276 		 * overhead.
3277 		 */
3278 		if (chunk->map[run_ind + i].bits & CHUNK_MAP_DECOMMITTED) {
3279 			size_t j;
3280 
3281 			/*
3282 			 * Advance i+j to just past the index of the last page
3283 			 * to commit.  Clear CHUNK_MAP_DECOMMITTED along the
3284 			 * way.
3285 			 */
3286 			for (j = 0; i + j < need_pages && (chunk->map[run_ind +
3287 			    i + j].bits & CHUNK_MAP_DECOMMITTED); j++) {
3288 				chunk->map[run_ind + i + j].bits ^=
3289 				    CHUNK_MAP_DECOMMITTED;
3290 			}
3291 
3292 			pages_commit((void *)((uintptr_t)chunk + ((run_ind + i)
3293 			    << pagesize_2pow)), (j << pagesize_2pow));
3294 #  ifdef MALLOC_STATS
3295 			arena->stats.ncommit++;
3296 #  endif
3297 		} else /* No need to zero since commit zeros. */
3298 #endif
3299 
3300 		/* Zero if necessary. */
3301 		if (zero) {
3302 			if ((chunk->map[run_ind + i].bits & CHUNK_MAP_ZEROED)
3303 			    == 0) {
3304 				VALGRIND_MALLOCLIKE_BLOCK((void *)((uintptr_t)
3305 				    chunk + ((run_ind + i) << pagesize_2pow)),
3306 				    pagesize, 0, false);
3307 				memset((void *)((uintptr_t)chunk + ((run_ind
3308 				    + i) << pagesize_2pow)), 0, pagesize);
3309 				VALGRIND_FREELIKE_BLOCK((void *)((uintptr_t)
3310 				    chunk + ((run_ind + i) << pagesize_2pow)),
3311 				    0);
3312 				/* CHUNK_MAP_ZEROED is cleared below. */
3313 			}
3314 		}
3315 
3316 		/* Update dirty page accounting. */
3317 		if (chunk->map[run_ind + i].bits & CHUNK_MAP_DIRTY) {
3318 			chunk->ndirty--;
3319 			arena->ndirty--;
3320 			/* CHUNK_MAP_DIRTY is cleared below. */
3321 		}
3322 
3323 		/* Initialize the chunk map. */
3324 		if (large) {
3325 			chunk->map[run_ind + i].bits = CHUNK_MAP_LARGE
3326 			    | CHUNK_MAP_ALLOCATED;
3327 		} else {
3328 			chunk->map[run_ind + i].bits = (size_t)run
3329 			    | CHUNK_MAP_ALLOCATED;
3330 		}
3331 	}
3332 
3333 	/*
3334 	 * Set the run size only in the first element for large runs.  This is
3335 	 * primarily a debugging aid, since the lack of size info for trailing
3336 	 * pages only matters if the application tries to operate on an
3337 	 * interior pointer.
3338 	 */
3339 	if (large)
3340 		chunk->map[run_ind].bits |= size;
3341 
3342 	if (chunk->ndirty == 0 && old_ndirty > 0)
3343 		arena_chunk_tree_dirty_remove(&arena->chunks_dirty, chunk);
3344 }
3345 
3346 static void
3347 arena_chunk_init(arena_t *arena, arena_chunk_t *chunk)
3348 {
3349 	arena_run_t *run;
3350 	size_t i;
3351 
3352 	VALGRIND_MALLOCLIKE_BLOCK(chunk, (arena_chunk_header_npages <<
3353 	    pagesize_2pow), 0, false);
3354 #ifdef MALLOC_STATS
3355 	arena->stats.mapped += chunksize;
3356 #endif
3357 
3358 	chunk->arena = arena;
3359 
3360 	/*
3361 	 * Claim that no pages are in use, since the header is merely overhead.
3362 	 */
3363 	chunk->ndirty = 0;
3364 
3365 	/* Initialize the map to contain one maximal free untouched run. */
3366 	run = (arena_run_t *)((uintptr_t)chunk + (arena_chunk_header_npages <<
3367 	    pagesize_2pow));
3368 	for (i = 0; i < arena_chunk_header_npages; i++)
3369 		chunk->map[i].bits = 0;
3370 	chunk->map[i].bits = arena_maxclass
3371 #ifdef MALLOC_DECOMMIT
3372 	    | CHUNK_MAP_DECOMMITTED
3373 #endif
3374 	    | CHUNK_MAP_ZEROED;
3375 	for (i++; i < chunk_npages-1; i++) {
3376 		chunk->map[i].bits =
3377 #ifdef MALLOC_DECOMMIT
3378 		    CHUNK_MAP_DECOMMITTED |
3379 #endif
3380 		    CHUNK_MAP_ZEROED;
3381 	}
3382 	chunk->map[chunk_npages-1].bits = arena_maxclass
3383 #ifdef MALLOC_DECOMMIT
3384 	    | CHUNK_MAP_DECOMMITTED
3385 #endif
3386 	    | CHUNK_MAP_ZEROED;
3387 
3388 #ifdef MALLOC_DECOMMIT
3389 	/*
3390 	 * Start out decommitted, in order to force a closer correspondence
3391 	 * between dirty pages and committed untouched pages.
3392 	 */
3393 	pages_decommit(run, arena_maxclass);
3394 #  ifdef MALLOC_STATS
3395 	arena->stats.ndecommit++;
3396 	arena->stats.decommitted += (chunk_npages - arena_chunk_header_npages);
3397 #  endif
3398 #endif
3399 
3400 	/* Insert the run into the runs_avail tree. */
3401 	arena_avail_tree_insert(&arena->runs_avail,
3402 	    &chunk->map[arena_chunk_header_npages]);
3403 }
3404 
3405 static void
3406 arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk)
3407 {
3408 
3409 	if (arena->spare != NULL) {
3410 		if (arena->spare->ndirty > 0) {
3411 			arena_chunk_tree_dirty_remove(
3412 			    &chunk->arena->chunks_dirty, arena->spare);
3413 			arena->ndirty -= arena->spare->ndirty;
3414 		}
3415 		VALGRIND_FREELIKE_BLOCK(arena->spare, 0);
3416 		chunk_dealloc((void *)arena->spare, chunksize);
3417 #ifdef MALLOC_STATS
3418 		arena->stats.mapped -= chunksize;
3419 #endif
3420 	}
3421 
3422 	/*
3423 	 * Remove run from runs_avail, regardless of whether this chunk
3424 	 * will be cached, so that the arena does not use it.  Dirty page
3425 	 * flushing only uses the chunks_dirty tree, so leaving this chunk in
3426 	 * the chunks_* trees is sufficient for that purpose.
3427 	 */
3428 	arena_avail_tree_remove(&arena->runs_avail,
3429 	    &chunk->map[arena_chunk_header_npages]);
3430 
3431 	arena->spare = chunk;
3432 }
3433 
3434 static arena_run_t *
3435 arena_run_alloc(arena_t *arena, arena_bin_t *bin, size_t size, bool large,
3436     bool zero)
3437 {
3438 	arena_chunk_t *chunk;
3439 	arena_run_t *run;
3440 	arena_chunk_map_t *mapelm, key;
3441 
3442 	assert(size <= arena_maxclass);
3443 	assert((size & pagesize_mask) == 0);
3444 
3445 	chunk = NULL;
3446 	while (true) {
3447 		/* Search the arena's chunks for the lowest best fit. */
3448 		key.bits = size | CHUNK_MAP_KEY;
3449 		mapelm = arena_avail_tree_nsearch(&arena->runs_avail, &key);
3450 		if (mapelm != NULL) {
3451 			arena_chunk_t *run_chunk = (arena_chunk_t*)CHUNK_ADDR2BASE(mapelm);
3452 			size_t pageind = ((uintptr_t)mapelm -
3453 			    (uintptr_t)run_chunk->map) /
3454 			    sizeof(arena_chunk_map_t);
3455 
3456 			if (chunk != NULL)
3457 				chunk_dealloc(chunk, chunksize);
3458 			run = (arena_run_t *)((uintptr_t)run_chunk + (pageind
3459 			    << pagesize_2pow));
3460 			arena_run_split(arena, run, size, large, zero);
3461 			return (run);
3462 		}
3463 
3464 		if (arena->spare != NULL) {
3465 			/* Use the spare. */
3466 			chunk = arena->spare;
3467 			arena->spare = NULL;
3468 			run = (arena_run_t *)((uintptr_t)chunk +
3469 			    (arena_chunk_header_npages << pagesize_2pow));
3470 			/* Insert the run into the runs_avail tree. */
3471 			arena_avail_tree_insert(&arena->runs_avail,
3472 			    &chunk->map[arena_chunk_header_npages]);
3473 			arena_run_split(arena, run, size, large, zero);
3474 			return (run);
3475 		}
3476 
3477 		/*
3478 		 * No usable runs.  Create a new chunk from which to allocate
3479 		 * the run.
3480 		 */
3481 		if (chunk == NULL) {
3482 			uint64_t chunk_seq;
3483 
3484 			/*
3485 			 * Record the chunk allocation sequence number in order
3486 			 * to detect races.
3487 			 */
3488 			arena->chunk_seq++;
3489 			chunk_seq = arena->chunk_seq;
3490 
3491 			/*
3492 			 * Drop the arena lock while allocating a chunk, since
3493 			 * reserve notifications may cause recursive
3494 			 * allocation.  Dropping the lock here opens an
3495 			 * allocataion race, but we recover.
3496 			 */
3497 			malloc_mutex_unlock(&arena->lock);
3498 			chunk = (arena_chunk_t *)chunk_alloc(chunksize, true,
3499 			    true);
3500 			malloc_mutex_lock(&arena->lock);
3501 
3502 			/*
3503 			 * Check whether a race allowed a usable run to appear.
3504 			 */
3505 			if (bin != NULL && (run = bin->runcur) != NULL &&
3506 			    run->nfree > 0) {
3507 				if (chunk != NULL)
3508 					chunk_dealloc(chunk, chunksize);
3509 				return (run);
3510 			}
3511 
3512 			/*
3513 			 * If this thread raced with another such that multiple
3514 			 * chunks were allocated, make sure that there is still
3515 			 * inadequate space before using this chunk.
3516 			 */
3517 			if (chunk_seq != arena->chunk_seq)
3518 				continue;
3519 
3520 			/*
3521 			 * Check for an error *after* checking for a race,
3522 			 * since a race could also cause a transient OOM
3523 			 * condition.
3524 			 */
3525 			if (chunk == NULL)
3526 				return (NULL);
3527 		}
3528 
3529 		arena_chunk_init(arena, chunk);
3530 		run = (arena_run_t *)((uintptr_t)chunk +
3531 		    (arena_chunk_header_npages << pagesize_2pow));
3532 		/* Update page map. */
3533 		arena_run_split(arena, run, size, large, zero);
3534 		return (run);
3535 	}
3536 }
3537 
3538 static void
3539 arena_purge(arena_t *arena)
3540 {
3541 	arena_chunk_t *chunk;
3542 	size_t i, npages;
3543 #ifdef MALLOC_DEBUG
3544 	size_t ndirty = 0;
3545 	rb_foreach_begin(arena_chunk_t, link_dirty, &arena->chunks_dirty,
3546 	    chunk) {
3547 		ndirty += chunk->ndirty;
3548 	} rb_foreach_end(arena_chunk_t, link_dirty, &arena->chunks_dirty, chunk)
3549 	assert(ndirty == arena->ndirty);
3550 #endif
3551 	assert(arena->ndirty > opt_dirty_max);
3552 
3553 #ifdef MALLOC_STATS
3554 	arena->stats.npurge++;
3555 #endif
3556 
3557 	/*
3558 	 * Iterate downward through chunks until enough dirty memory has been
3559 	 * purged.  Terminate as soon as possible in order to minimize the
3560 	 * number of system calls, even if a chunk has only been partially
3561 	 * purged.
3562 	 */
3563 	while (arena->ndirty > (opt_dirty_max >> 1)) {
3564 		chunk = arena_chunk_tree_dirty_last(&arena->chunks_dirty);
3565 		assert(chunk != NULL);
3566 
3567 		for (i = chunk_npages - 1; chunk->ndirty > 0; i--) {
3568 			assert(i >= arena_chunk_header_npages);
3569 
3570 			if (chunk->map[i].bits & CHUNK_MAP_DIRTY) {
3571 #ifdef MALLOC_DECOMMIT
3572 				assert((chunk->map[i].bits &
3573 				    CHUNK_MAP_DECOMMITTED) == 0);
3574 #endif
3575 				chunk->map[i].bits ^=
3576 #ifdef MALLOC_DECOMMIT
3577 				    CHUNK_MAP_DECOMMITTED |
3578 #endif
3579 				    CHUNK_MAP_DIRTY;
3580 				/* Find adjacent dirty run(s). */
3581 				for (npages = 1; i > arena_chunk_header_npages
3582 				    && (chunk->map[i - 1].bits &
3583 				    CHUNK_MAP_DIRTY); npages++) {
3584 					i--;
3585 #ifdef MALLOC_DECOMMIT
3586 					assert((chunk->map[i].bits &
3587 					    CHUNK_MAP_DECOMMITTED) == 0);
3588 #endif
3589 					chunk->map[i].bits ^=
3590 #ifdef MALLOC_DECOMMIT
3591 					    CHUNK_MAP_DECOMMITTED |
3592 #endif
3593 					    CHUNK_MAP_DIRTY;
3594 				}
3595 				chunk->ndirty -= npages;
3596 				arena->ndirty -= npages;
3597 
3598 #ifdef MALLOC_DECOMMIT
3599 				pages_decommit((void *)((uintptr_t)
3600 				    chunk + (i << pagesize_2pow)),
3601 				    (npages << pagesize_2pow));
3602 #  ifdef MALLOC_STATS
3603 				arena->stats.ndecommit++;
3604 				arena->stats.decommitted += npages;
3605 #  endif
3606 #else
3607 				madvise((void *)((uintptr_t)chunk + (i <<
3608 				    pagesize_2pow)), (npages << pagesize_2pow),
3609 				    MADV_FREE);
3610 #endif
3611 #ifdef MALLOC_STATS
3612 				arena->stats.nmadvise++;
3613 				arena->stats.purged += npages;
3614 #endif
3615 				if (arena->ndirty <= (opt_dirty_max >> 1))
3616 					break;
3617 			}
3618 		}
3619 
3620 		if (chunk->ndirty == 0) {
3621 			arena_chunk_tree_dirty_remove(&arena->chunks_dirty,
3622 			    chunk);
3623 		}
3624 	}
3625 }
3626 
3627 static void
3628 arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty)
3629 {
3630 	arena_chunk_t *chunk;
3631 	size_t size, run_ind, run_pages;
3632 
3633 	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
3634 	run_ind = (size_t)(((uintptr_t)run - (uintptr_t)chunk)
3635 	    >> pagesize_2pow);
3636 	assert(run_ind >= arena_chunk_header_npages);
3637 	assert(run_ind < chunk_npages);
3638 	if ((chunk->map[run_ind].bits & CHUNK_MAP_LARGE) != 0)
3639 		size = chunk->map[run_ind].bits & ~pagesize_mask;
3640 	else
3641 		size = run->bin->run_size;
3642 	run_pages = (size >> pagesize_2pow);
3643 
3644 	/* Mark pages as unallocated in the chunk map. */
3645 	if (dirty) {
3646 		size_t i;
3647 
3648 		for (i = 0; i < run_pages; i++) {
3649 			assert((chunk->map[run_ind + i].bits & CHUNK_MAP_DIRTY)
3650 			    == 0);
3651 			chunk->map[run_ind + i].bits = CHUNK_MAP_DIRTY;
3652 		}
3653 
3654 		if (chunk->ndirty == 0) {
3655 			arena_chunk_tree_dirty_insert(&arena->chunks_dirty,
3656 			    chunk);
3657 		}
3658 		chunk->ndirty += run_pages;
3659 		arena->ndirty += run_pages;
3660 	} else {
3661 		size_t i;
3662 
3663 		for (i = 0; i < run_pages; i++) {
3664 			chunk->map[run_ind + i].bits &= ~(CHUNK_MAP_LARGE |
3665 			    CHUNK_MAP_ALLOCATED);
3666 		}
3667 	}
3668 	chunk->map[run_ind].bits = size | (chunk->map[run_ind].bits &
3669 	    pagesize_mask);
3670 	chunk->map[run_ind+run_pages-1].bits = size |
3671 	    (chunk->map[run_ind+run_pages-1].bits & pagesize_mask);
3672 
3673 	/* Try to coalesce forward. */
3674 	if (run_ind + run_pages < chunk_npages &&
3675 	    (chunk->map[run_ind+run_pages].bits & CHUNK_MAP_ALLOCATED) == 0) {
3676 		size_t nrun_size = chunk->map[run_ind+run_pages].bits &
3677 		    ~pagesize_mask;
3678 
3679 		/*
3680 		 * Remove successor from runs_avail; the coalesced run is
3681 		 * inserted later.
3682 		 */
3683 		arena_avail_tree_remove(&arena->runs_avail,
3684 		    &chunk->map[run_ind+run_pages]);
3685 
3686 		size += nrun_size;
3687 		run_pages = size >> pagesize_2pow;
3688 
3689 		assert((chunk->map[run_ind+run_pages-1].bits & ~pagesize_mask)
3690 		    == nrun_size);
3691 		chunk->map[run_ind].bits = size | (chunk->map[run_ind].bits &
3692 		    pagesize_mask);
3693 		chunk->map[run_ind+run_pages-1].bits = size |
3694 		    (chunk->map[run_ind+run_pages-1].bits & pagesize_mask);
3695 	}
3696 
3697 	/* Try to coalesce backward. */
3698 	if (run_ind > arena_chunk_header_npages && (chunk->map[run_ind-1].bits &
3699 	    CHUNK_MAP_ALLOCATED) == 0) {
3700 		size_t prun_size = chunk->map[run_ind-1].bits & ~pagesize_mask;
3701 
3702 		run_ind -= prun_size >> pagesize_2pow;
3703 
3704 		/*
3705 		 * Remove predecessor from runs_avail; the coalesced run is
3706 		 * inserted later.
3707 		 */
3708 		arena_avail_tree_remove(&arena->runs_avail,
3709 		    &chunk->map[run_ind]);
3710 
3711 		size += prun_size;
3712 		run_pages = size >> pagesize_2pow;
3713 
3714 		assert((chunk->map[run_ind].bits & ~pagesize_mask) ==
3715 		    prun_size);
3716 		chunk->map[run_ind].bits = size | (chunk->map[run_ind].bits &
3717 		    pagesize_mask);
3718 		chunk->map[run_ind+run_pages-1].bits = size |
3719 		    (chunk->map[run_ind+run_pages-1].bits & pagesize_mask);
3720 	}
3721 
3722 	/* Insert into runs_avail, now that coalescing is complete. */
3723 	arena_avail_tree_insert(&arena->runs_avail, &chunk->map[run_ind]);
3724 
3725 	/* Deallocate chunk if it is now completely unused. */
3726 	if ((chunk->map[arena_chunk_header_npages].bits & (~pagesize_mask |
3727 	    CHUNK_MAP_ALLOCATED)) == arena_maxclass)
3728 		arena_chunk_dealloc(arena, chunk);
3729 
3730 	/* Enforce opt_dirty_max. */
3731 	if (arena->ndirty > opt_dirty_max)
3732 		arena_purge(arena);
3733 }
3734 
3735 static void
3736 arena_run_trim_head(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run,
3737     size_t oldsize, size_t newsize)
3738 {
3739 	size_t pageind = ((uintptr_t)run - (uintptr_t)chunk) >> pagesize_2pow;
3740 	size_t head_npages = (oldsize - newsize) >> pagesize_2pow;
3741 
3742 	assert(oldsize > newsize);
3743 
3744 	/*
3745 	 * Update the chunk map so that arena_run_dalloc() can treat the
3746 	 * leading run as separately allocated.
3747 	 */
3748 	chunk->map[pageind].bits = (oldsize - newsize) | CHUNK_MAP_LARGE |
3749 	    CHUNK_MAP_ALLOCATED;
3750 	chunk->map[pageind+head_npages].bits = newsize | CHUNK_MAP_LARGE |
3751 	    CHUNK_MAP_ALLOCATED;
3752 
3753 	arena_run_dalloc(arena, run, false);
3754 }
3755 
3756 static void
3757 arena_run_trim_tail(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run,
3758     size_t oldsize, size_t newsize, bool dirty)
3759 {
3760 	size_t pageind = ((uintptr_t)run - (uintptr_t)chunk) >> pagesize_2pow;
3761 	size_t npages = newsize >> pagesize_2pow;
3762 
3763 	assert(oldsize > newsize);
3764 
3765 	/*
3766 	 * Update the chunk map so that arena_run_dalloc() can treat the
3767 	 * trailing run as separately allocated.
3768 	 */
3769 	chunk->map[pageind].bits = newsize | CHUNK_MAP_LARGE |
3770 	    CHUNK_MAP_ALLOCATED;
3771 	chunk->map[pageind+npages].bits = (oldsize - newsize) | CHUNK_MAP_LARGE
3772 	    | CHUNK_MAP_ALLOCATED;
3773 
3774 	arena_run_dalloc(arena, (arena_run_t *)((uintptr_t)run + newsize),
3775 	    dirty);
3776 }
3777 
3778 static arena_run_t *
3779 arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin)
3780 {
3781 	arena_chunk_map_t *mapelm;
3782 	arena_run_t *run;
3783 	unsigned i, remainder;
3784 
3785 	/* Look for a usable run. */
3786 	mapelm = arena_run_tree_first(&bin->runs);
3787 	if (mapelm != NULL) {
3788 		/* run is guaranteed to have available space. */
3789 		arena_run_tree_remove(&bin->runs, mapelm);
3790 		run = (arena_run_t *)(mapelm->bits & ~pagesize_mask);
3791 #ifdef MALLOC_STATS
3792 		bin->stats.reruns++;
3793 #endif
3794 		return (run);
3795 	}
3796 	/* No existing runs have any space available. */
3797 
3798 	/* Allocate a new run. */
3799 	run = arena_run_alloc(arena, bin, bin->run_size, false, false);
3800 	if (run == NULL)
3801 		return (NULL);
3802 	/*
3803 	 * Don't initialize if a race in arena_run_alloc() allowed an existing
3804 	 * run to become usable.
3805 	 */
3806 	if (run == bin->runcur)
3807 		return (run);
3808 
3809 	VALGRIND_MALLOCLIKE_BLOCK(run, sizeof(arena_run_t) + (sizeof(unsigned) *
3810 	    (bin->regs_mask_nelms - 1)), 0, false);
3811 
3812 	/* Initialize run internals. */
3813 	run->bin = bin;
3814 
3815 	for (i = 0; i < bin->regs_mask_nelms - 1; i++)
3816 		run->regs_mask[i] = UINT_MAX;
3817 	remainder = bin->nregs & ((1U << (SIZEOF_INT_2POW + 3)) - 1);
3818 	if (remainder == 0)
3819 		run->regs_mask[i] = UINT_MAX;
3820 	else {
3821 		/* The last element has spare bits that need to be unset. */
3822 		run->regs_mask[i] = (UINT_MAX >> ((1U << (SIZEOF_INT_2POW + 3))
3823 		    - remainder));
3824 	}
3825 
3826 	run->regs_minelm = 0;
3827 
3828 	run->nfree = bin->nregs;
3829 #ifdef MALLOC_DEBUG
3830 	run->magic = ARENA_RUN_MAGIC;
3831 #endif
3832 
3833 #ifdef MALLOC_STATS
3834 	bin->stats.nruns++;
3835 	bin->stats.curruns++;
3836 	if (bin->stats.curruns > bin->stats.highruns)
3837 		bin->stats.highruns = bin->stats.curruns;
3838 #endif
3839 	return (run);
3840 }
3841 
3842 /* bin->runcur must have space available before this function is called. */
3843 static inline void *
3844 arena_bin_malloc_easy(arena_t *arena, arena_bin_t *bin, arena_run_t *run)
3845 {
3846 	void *ret;
3847 
3848 	assert(run->magic == ARENA_RUN_MAGIC);
3849 	assert(run->nfree > 0);
3850 
3851 	ret = arena_run_reg_alloc(run, bin);
3852 	assert(ret != NULL);
3853 	run->nfree--;
3854 
3855 	return (ret);
3856 }
3857 
3858 /* Re-fill bin->runcur, then call arena_bin_malloc_easy(). */
3859 static void *
3860 arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin)
3861 {
3862 
3863 	bin->runcur = arena_bin_nonfull_run_get(arena, bin);
3864 	if (bin->runcur == NULL)
3865 		return (NULL);
3866 	assert(bin->runcur->magic == ARENA_RUN_MAGIC);
3867 	assert(bin->runcur->nfree > 0);
3868 
3869 	return (arena_bin_malloc_easy(arena, bin, bin->runcur));
3870 }
3871 
3872 /*
3873  * Calculate bin->run_size such that it meets the following constraints:
3874  *
3875  *   *) bin->run_size >= min_run_size
3876  *   *) bin->run_size <= arena_maxclass
3877  *   *) bin->run_size <= RUN_MAX_SMALL
3878  *   *) run header overhead <= RUN_MAX_OVRHD (or header overhead relaxed).
3879  *
3880  * bin->nregs, bin->regs_mask_nelms, and bin->reg0_offset are
3881  * also calculated here, since these settings are all interdependent.
3882  */
3883 static size_t
3884 arena_bin_run_size_calc(arena_bin_t *bin, size_t min_run_size)
3885 {
3886 	size_t try_run_size, good_run_size;
3887 	unsigned good_nregs, good_mask_nelms, good_reg0_offset;
3888 	unsigned try_nregs, try_mask_nelms, try_reg0_offset;
3889 
3890 	assert(min_run_size >= pagesize);
3891 	assert(min_run_size <= arena_maxclass);
3892 	assert(min_run_size <= RUN_MAX_SMALL);
3893 
3894 	/*
3895 	 * Calculate known-valid settings before entering the run_size
3896 	 * expansion loop, so that the first part of the loop always copies
3897 	 * valid settings.
3898 	 *
3899 	 * The do..while loop iteratively reduces the number of regions until
3900 	 * the run header and the regions no longer overlap.  A closed formula
3901 	 * would be quite messy, since there is an interdependency between the
3902 	 * header's mask length and the number of regions.
3903 	 */
3904 	try_run_size = min_run_size;
3905 	try_nregs = ((try_run_size - sizeof(arena_run_t)) / bin->reg_size)
3906 	    + 1; /* Counter-act try_nregs-- in loop. */
3907 	do {
3908 		try_nregs--;
3909 		try_mask_nelms = (try_nregs >> (SIZEOF_INT_2POW + 3)) +
3910 		    ((try_nregs & ((1U << (SIZEOF_INT_2POW + 3)) - 1)) ? 1 : 0);
3911 		try_reg0_offset = try_run_size - (try_nregs * bin->reg_size);
3912 	} while (sizeof(arena_run_t) + (sizeof(unsigned) * (try_mask_nelms - 1))
3913 	    > try_reg0_offset);
3914 
3915 	/* run_size expansion loop. */
3916 	do {
3917 		/*
3918 		 * Copy valid settings before trying more aggressive settings.
3919 		 */
3920 		good_run_size = try_run_size;
3921 		good_nregs = try_nregs;
3922 		good_mask_nelms = try_mask_nelms;
3923 		good_reg0_offset = try_reg0_offset;
3924 
3925 		/* Try more aggressive settings. */
3926 		try_run_size += pagesize;
3927 		try_nregs = ((try_run_size - sizeof(arena_run_t)) /
3928 		    bin->reg_size) + 1; /* Counter-act try_nregs-- in loop. */
3929 		do {
3930 			try_nregs--;
3931 			try_mask_nelms = (try_nregs >> (SIZEOF_INT_2POW + 3)) +
3932 			    ((try_nregs & ((1U << (SIZEOF_INT_2POW + 3)) - 1)) ?
3933 			    1 : 0);
3934 			try_reg0_offset = try_run_size - (try_nregs *
3935 			    bin->reg_size);
3936 		} while (sizeof(arena_run_t) + (sizeof(unsigned) *
3937 		    (try_mask_nelms - 1)) > try_reg0_offset);
3938 	} while (try_run_size <= arena_maxclass && try_run_size <= RUN_MAX_SMALL
3939 	    && RUN_MAX_OVRHD * (bin->reg_size << 3) > RUN_MAX_OVRHD_RELAX
3940 	    && (try_reg0_offset << RUN_BFP) > RUN_MAX_OVRHD * try_run_size);
3941 
3942 	assert(sizeof(arena_run_t) + (sizeof(unsigned) * (good_mask_nelms - 1))
3943 	    <= good_reg0_offset);
3944 	assert((good_mask_nelms << (SIZEOF_INT_2POW + 3)) >= good_nregs);
3945 
3946 	/* Copy final settings. */
3947 	bin->run_size = good_run_size;
3948 	bin->nregs = good_nregs;
3949 	bin->regs_mask_nelms = good_mask_nelms;
3950 	bin->reg0_offset = good_reg0_offset;
3951 
3952 	return (good_run_size);
3953 }
3954 
3955 #ifdef MALLOC_BALANCE
3956 static inline void
3957 arena_lock_balance(arena_t *arena)
3958 {
3959 	unsigned contention;
3960 
3961 	contention = malloc_spin_lock(&arena->lock);
3962 	if (narenas > 1) {
3963 		/*
3964 		 * Calculate the exponentially averaged contention for this
3965 		 * arena.  Due to integer math always rounding down, this value
3966 		 * decays somewhat faster then normal.
3967 		 */
3968 		arena->contention = (((uint64_t)arena->contention
3969 		    * (uint64_t)((1U << BALANCE_ALPHA_INV_2POW)-1))
3970 		    + (uint64_t)contention) >> BALANCE_ALPHA_INV_2POW;
3971 		if (arena->contention >= opt_balance_threshold)
3972 			arena_lock_balance_hard(arena);
3973 	}
3974 }
3975 
3976 static void
3977 arena_lock_balance_hard(arena_t *arena)
3978 {
3979 	uint32_t ind;
3980 
3981 	arena->contention = 0;
3982 #ifdef MALLOC_STATS
3983 	arena->stats.nbalance++;
3984 #endif
3985 	ind = PRN(balance, narenas_2pow);
3986 	if (arenas[ind] != NULL) {
3987 #ifdef MOZ_MEMORY_WINDOWS
3988 		TlsSetValue(tlsIndex, arenas[ind]);
3989 #else
3990 		arenas_map = arenas[ind];
3991 #endif
3992 	} else {
3993 		malloc_spin_lock(&arenas_lock);
3994 		if (arenas[ind] != NULL) {
3995 #ifdef MOZ_MEMORY_WINDOWS
3996 			TlsSetValue(tlsIndex, arenas[ind]);
3997 #else
3998 			arenas_map = arenas[ind];
3999 #endif
4000 		} else {
4001 #ifdef MOZ_MEMORY_WINDOWS
4002 			TlsSetValue(tlsIndex, arenas_extend(ind));
4003 #else
4004 			arenas_map = arenas_extend(ind);
4005 #endif
4006 		}
4007 		malloc_spin_unlock(&arenas_lock);
4008 	}
4009 }
4010 #endif
4011 
4012 static inline void *
4013 arena_malloc_small(arena_t *arena, size_t size, bool zero)
4014 {
4015 	void *ret;
4016 	arena_bin_t *bin;
4017 	arena_run_t *run;
4018 
4019 	if (size < small_min) {
4020 		/* Tiny. */
4021 		size = pow2_ceil(size);
4022 		bin = &arena->bins[ffs((int)(size >> (TINY_MIN_2POW +
4023 		    1)))];
4024 #if (!defined(NDEBUG) || defined(MALLOC_STATS))
4025 		/*
4026 		 * Bin calculation is always correct, but we may need
4027 		 * to fix size for the purposes of assertions and/or
4028 		 * stats accuracy.
4029 		 */
4030 		if (size < (1U << TINY_MIN_2POW))
4031 			size = (1U << TINY_MIN_2POW);
4032 #endif
4033 	} else if (size <= small_max) {
4034 		/* Quantum-spaced. */
4035 		size = QUANTUM_CEILING(size);
4036 		bin = &arena->bins[ntbins + (size >> opt_quantum_2pow)
4037 		    - 1];
4038 	} else {
4039 		/* Sub-page. */
4040 		size = pow2_ceil(size);
4041 		bin = &arena->bins[ntbins + nqbins
4042 		    + (ffs((int)(size >> opt_small_max_2pow)) - 2)];
4043 	}
4044 	assert(size == bin->reg_size);
4045 
4046 #ifdef MALLOC_BALANCE
4047 	arena_lock_balance(arena);
4048 #else
4049 	malloc_spin_lock(&arena->lock);
4050 #endif
4051 	if ((run = bin->runcur) != NULL && run->nfree > 0)
4052 		ret = arena_bin_malloc_easy(arena, bin, run);
4053 	else
4054 		ret = arena_bin_malloc_hard(arena, bin);
4055 
4056 	if (ret == NULL) {
4057 		malloc_spin_unlock(&arena->lock);
4058 		return (NULL);
4059 	}
4060 
4061 #ifdef MALLOC_STATS
4062 	bin->stats.nrequests++;
4063 	arena->stats.nmalloc_small++;
4064 	arena->stats.allocated_small += size;
4065 #endif
4066 	malloc_spin_unlock(&arena->lock);
4067 
4068 	VALGRIND_MALLOCLIKE_BLOCK(ret, size, 0, zero);
4069 	if (zero == false) {
4070 #ifdef MALLOC_FILL
4071 		if (opt_junk)
4072 			memset(ret, 0xa5, size);
4073 		else if (opt_zero)
4074 			memset(ret, 0, size);
4075 #endif
4076 	} else
4077 		memset(ret, 0, size);
4078 
4079 	return (ret);
4080 }
4081 
4082 static void *
4083 arena_malloc_large(arena_t *arena, size_t size, bool zero)
4084 {
4085 	void *ret;
4086 
4087 	/* Large allocation. */
4088 	size = PAGE_CEILING(size);
4089 #ifdef MALLOC_BALANCE
4090 	arena_lock_balance(arena);
4091 #else
4092 	malloc_spin_lock(&arena->lock);
4093 #endif
4094 	ret = (void *)arena_run_alloc(arena, NULL, size, true, zero);
4095 	if (ret == NULL) {
4096 		malloc_spin_unlock(&arena->lock);
4097 		return (NULL);
4098 	}
4099 #ifdef MALLOC_STATS
4100 	arena->stats.nmalloc_large++;
4101 	arena->stats.allocated_large += size;
4102 #endif
4103 	malloc_spin_unlock(&arena->lock);
4104 
4105 	VALGRIND_MALLOCLIKE_BLOCK(ret, size, 0, zero);
4106 	if (zero == false) {
4107 #ifdef MALLOC_FILL
4108 		if (opt_junk)
4109 			memset(ret, 0xa5, size);
4110 		else if (opt_zero)
4111 			memset(ret, 0, size);
4112 #endif
4113 	}
4114 
4115 	return (ret);
4116 }
4117 
4118 static inline void *
4119 arena_malloc(arena_t *arena, size_t size, bool zero)
4120 {
4121 
4122 	assert(arena != NULL);
4123 	assert(arena->magic == ARENA_MAGIC);
4124 	assert(size != 0);
4125 	assert(QUANTUM_CEILING(size) <= arena_maxclass);
4126 
4127 	if (size <= bin_maxclass) {
4128 		return (arena_malloc_small(arena, size, zero));
4129 	} else
4130 		return (arena_malloc_large(arena, size, zero));
4131 }
4132 
4133 static inline void *
4134 imalloc(size_t size)
4135 {
4136 
4137 	assert(size != 0);
4138 
4139 	if (size <= arena_maxclass)
4140 		return (arena_malloc(choose_arena(), size, false));
4141 	else
4142 		return (huge_malloc(size, false));
4143 }
4144 
4145 static inline void *
4146 icalloc(size_t size)
4147 {
4148 
4149 	if (size <= arena_maxclass)
4150 		return (arena_malloc(choose_arena(), size, true));
4151 	else
4152 		return (huge_malloc(size, true));
4153 }
4154 
4155 /* Only handles large allocations that require more than page alignment. */
4156 static void *
4157 arena_palloc(arena_t *arena, size_t alignment, size_t size, size_t alloc_size)
4158 {
4159 	void *ret;
4160 	size_t offset;
4161 	arena_chunk_t *chunk;
4162 
4163 	assert((size & pagesize_mask) == 0);
4164 	assert((alignment & pagesize_mask) == 0);
4165 
4166 #ifdef MALLOC_BALANCE
4167 	arena_lock_balance(arena);
4168 #else
4169 	malloc_spin_lock(&arena->lock);
4170 #endif
4171 	ret = (void *)arena_run_alloc(arena, NULL, alloc_size, true, false);
4172 	if (ret == NULL) {
4173 		malloc_spin_unlock(&arena->lock);
4174 		return (NULL);
4175 	}
4176 
4177 	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ret);
4178 
4179 	offset = (uintptr_t)ret & (alignment - 1);
4180 	assert((offset & pagesize_mask) == 0);
4181 	assert(offset < alloc_size);
4182 	if (offset == 0)
4183 		arena_run_trim_tail(arena, chunk, (arena_run_t*)ret, alloc_size, size, false);
4184 	else {
4185 		size_t leadsize, trailsize;
4186 
4187 		leadsize = alignment - offset;
4188 		if (leadsize > 0) {
4189 			arena_run_trim_head(arena, chunk, (arena_run_t*)ret, alloc_size,
4190 			    alloc_size - leadsize);
4191 			ret = (void *)((uintptr_t)ret + leadsize);
4192 		}
4193 
4194 		trailsize = alloc_size - leadsize - size;
4195 		if (trailsize != 0) {
4196 			/* Trim trailing space. */
4197 			assert(trailsize < alloc_size);
4198 			arena_run_trim_tail(arena, chunk, (arena_run_t*)ret, size + trailsize,
4199 			    size, false);
4200 		}
4201 	}
4202 
4203 #ifdef MALLOC_STATS
4204 	arena->stats.nmalloc_large++;
4205 	arena->stats.allocated_large += size;
4206 #endif
4207 	malloc_spin_unlock(&arena->lock);
4208 
4209 	VALGRIND_MALLOCLIKE_BLOCK(ret, size, 0, false);
4210 #ifdef MALLOC_FILL
4211 	if (opt_junk)
4212 		memset(ret, 0xa5, size);
4213 	else if (opt_zero)
4214 		memset(ret, 0, size);
4215 #endif
4216 	return (ret);
4217 }
4218 
4219 static inline void *
4220 ipalloc(size_t alignment, size_t size)
4221 {
4222 	void *ret;
4223 	size_t ceil_size;
4224 
4225 	/*
4226 	 * Round size up to the nearest multiple of alignment.
4227 	 *
4228 	 * This done, we can take advantage of the fact that for each small
4229 	 * size class, every object is aligned at the smallest power of two
4230 	 * that is non-zero in the base two representation of the size.  For
4231 	 * example:
4232 	 *
4233 	 *   Size |   Base 2 | Minimum alignment
4234 	 *   -----+----------+------------------
4235 	 *     96 |  1100000 |  32
4236 	 *    144 | 10100000 |  32
4237 	 *    192 | 11000000 |  64
4238 	 *
4239 	 * Depending on runtime settings, it is possible that arena_malloc()
4240 	 * will further round up to a power of two, but that never causes
4241 	 * correctness issues.
4242 	 */
4243 	ceil_size = (size + (alignment - 1)) & (-alignment);
4244 	/*
4245 	 * (ceil_size < size) protects against the combination of maximal
4246 	 * alignment and size greater than maximal alignment.
4247 	 */
4248 	if (ceil_size < size) {
4249 		/* size_t overflow. */
4250 		return (NULL);
4251 	}
4252 
4253 	if (ceil_size <= pagesize || (alignment <= pagesize
4254 	    && ceil_size <= arena_maxclass))
4255 		ret = arena_malloc(choose_arena(), ceil_size, false);
4256 	else {
4257 		size_t run_size;
4258 
4259 		/*
4260 		 * We can't achieve sub-page alignment, so round up alignment
4261 		 * permanently; it makes later calculations simpler.
4262 		 */
4263 		alignment = PAGE_CEILING(alignment);
4264 		ceil_size = PAGE_CEILING(size);
4265 		/*
4266 		 * (ceil_size < size) protects against very large sizes within
4267 		 * pagesize of SIZE_T_MAX.
4268 		 *
4269 		 * (ceil_size + alignment < ceil_size) protects against the
4270 		 * combination of maximal alignment and ceil_size large enough
4271 		 * to cause overflow.  This is similar to the first overflow
4272 		 * check above, but it needs to be repeated due to the new
4273 		 * ceil_size value, which may now be *equal* to maximal
4274 		 * alignment, whereas before we only detected overflow if the
4275 		 * original size was *greater* than maximal alignment.
4276 		 */
4277 		if (ceil_size < size || ceil_size + alignment < ceil_size) {
4278 			/* size_t overflow. */
4279 			return (NULL);
4280 		}
4281 
4282 		/*
4283 		 * Calculate the size of the over-size run that arena_palloc()
4284 		 * would need to allocate in order to guarantee the alignment.
4285 		 */
4286 		if (ceil_size >= alignment)
4287 			run_size = ceil_size + alignment - pagesize;
4288 		else {
4289 			/*
4290 			 * It is possible that (alignment << 1) will cause
4291 			 * overflow, but it doesn't matter because we also
4292 			 * subtract pagesize, which in the case of overflow
4293 			 * leaves us with a very large run_size.  That causes
4294 			 * the first conditional below to fail, which means
4295 			 * that the bogus run_size value never gets used for
4296 			 * anything important.
4297 			 */
4298 			run_size = (alignment << 1) - pagesize;
4299 		}
4300 
4301 		if (run_size <= arena_maxclass) {
4302 			ret = arena_palloc(choose_arena(), alignment, ceil_size,
4303 			    run_size);
4304 		} else if (alignment <= chunksize)
4305 			ret = huge_malloc(ceil_size, false);
4306 		else
4307 			ret = huge_palloc(alignment, ceil_size);
4308 	}
4309 
4310 	assert(((uintptr_t)ret & (alignment - 1)) == 0);
4311 	return (ret);
4312 }
4313 
4314 /* Return the size of the allocation pointed to by ptr. */
4315 static size_t
4316 arena_salloc(const void *ptr)
4317 {
4318 	size_t ret;
4319 	arena_chunk_t *chunk;
4320 	size_t pageind, mapbits;
4321 
4322 	assert(ptr != NULL);
4323 	assert(CHUNK_ADDR2BASE(ptr) != ptr);
4324 
4325 	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
4326 	pageind = (((uintptr_t)ptr - (uintptr_t)chunk) >> pagesize_2pow);
4327 	mapbits = chunk->map[pageind].bits;
4328 	assert((mapbits & CHUNK_MAP_ALLOCATED) != 0);
4329 	if ((mapbits & CHUNK_MAP_LARGE) == 0) {
4330 		arena_run_t *run = (arena_run_t *)(mapbits & ~pagesize_mask);
4331 		assert(run->magic == ARENA_RUN_MAGIC);
4332 		ret = run->bin->reg_size;
4333 	} else {
4334 		ret = mapbits & ~pagesize_mask;
4335 		assert(ret != 0);
4336 	}
4337 
4338 	return (ret);
4339 }
4340 
4341 #if (defined(MALLOC_VALIDATE) || defined(MOZ_MEMORY_DARWIN))
4342 /*
4343  * Validate ptr before assuming that it points to an allocation.  Currently,
4344  * the following validation is performed:
4345  *
4346  * + Check that ptr is not NULL.
4347  *
4348  * + Check that ptr lies within a mapped chunk.
4349  */
4350 static inline size_t
4351 isalloc_validate(const void *ptr)
4352 {
4353 	arena_chunk_t *chunk;
4354 
4355 	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
4356 	if (chunk == NULL)
4357 		return (0);
4358 
4359 	if (malloc_rtree_get(chunk_rtree, (uintptr_t)chunk) == NULL)
4360 		return (0);
4361 
4362 	if (chunk != ptr) {
4363 		assert(chunk->arena->magic == ARENA_MAGIC);
4364 		return (arena_salloc(ptr));
4365 	} else {
4366 		size_t ret;
4367 		extent_node_t *node;
4368 		extent_node_t key;
4369 
4370 		/* Chunk. */
4371 		key.addr = (void *)chunk;
4372 		malloc_mutex_lock(&huge_mtx);
4373 		node = extent_tree_ad_search(&huge, &key);
4374 		if (node != NULL)
4375 			ret = node->size;
4376 		else
4377 			ret = 0;
4378 		malloc_mutex_unlock(&huge_mtx);
4379 		return (ret);
4380 	}
4381 }
4382 #endif
4383 
4384 static inline size_t
4385 isalloc(const void *ptr)
4386 {
4387 	size_t ret;
4388 	arena_chunk_t *chunk;
4389 
4390 	assert(ptr != NULL);
4391 
4392 	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
4393 	if (chunk != ptr) {
4394 		/* Region. */
4395 		assert(chunk->arena->magic == ARENA_MAGIC);
4396 
4397 		ret = arena_salloc(ptr);
4398 	} else {
4399 		extent_node_t *node, key;
4400 
4401 		/* Chunk (huge allocation). */
4402 
4403 		malloc_mutex_lock(&huge_mtx);
4404 
4405 		/* Extract from tree of huge allocations. */
4406 		key.addr = __DECONST(void *, ptr);
4407 		node = extent_tree_ad_search(&huge, &key);
4408 		assert(node != NULL);
4409 
4410 		ret = node->size;
4411 
4412 		malloc_mutex_unlock(&huge_mtx);
4413 	}
4414 
4415 	return (ret);
4416 }
4417 
4418 static inline void
4419 arena_dalloc_small(arena_t *arena, arena_chunk_t *chunk, void *ptr,
4420     arena_chunk_map_t *mapelm)
4421 {
4422 	arena_run_t *run;
4423 	arena_bin_t *bin;
4424 	size_t size;
4425 
4426 	run = (arena_run_t *)(mapelm->bits & ~pagesize_mask);
4427 	assert(run->magic == ARENA_RUN_MAGIC);
4428 	bin = run->bin;
4429 	size = bin->reg_size;
4430 
4431 #ifdef MALLOC_FILL
4432 	if (opt_junk)
4433 		memset(ptr, 0x5a, size);
4434 #endif
4435 
4436 	arena_run_reg_dalloc(run, bin, ptr, size);
4437 	run->nfree++;
4438 
4439 	if (run->nfree == bin->nregs) {
4440 		/* Deallocate run. */
4441 		if (run == bin->runcur)
4442 			bin->runcur = NULL;
4443 		else if (bin->nregs != 1) {
4444 			size_t run_pageind = (((uintptr_t)run -
4445 			    (uintptr_t)chunk)) >> pagesize_2pow;
4446 			arena_chunk_map_t *run_mapelm =
4447 			    &chunk->map[run_pageind];
4448 			/*
4449 			 * This block's conditional is necessary because if the
4450 			 * run only contains one region, then it never gets
4451 			 * inserted into the non-full runs tree.
4452 			 */
4453 			assert(arena_run_tree_search(&bin->runs, run_mapelm) ==
4454 			    run_mapelm);
4455 			arena_run_tree_remove(&bin->runs, run_mapelm);
4456 		}
4457 #ifdef MALLOC_DEBUG
4458 		run->magic = 0;
4459 #endif
4460 		VALGRIND_FREELIKE_BLOCK(run, 0);
4461 		arena_run_dalloc(arena, run, true);
4462 #ifdef MALLOC_STATS
4463 		bin->stats.curruns--;
4464 #endif
4465 	} else if (run->nfree == 1 && run != bin->runcur) {
4466 		/*
4467 		 * Make sure that bin->runcur always refers to the lowest
4468 		 * non-full run, if one exists.
4469 		 */
4470 		if (bin->runcur == NULL)
4471 			bin->runcur = run;
4472 		else if ((uintptr_t)run < (uintptr_t)bin->runcur) {
4473 			/* Switch runcur. */
4474 			if (bin->runcur->nfree > 0) {
4475 				arena_chunk_t *runcur_chunk =
4476 				    (arena_chunk_t*)CHUNK_ADDR2BASE(bin->runcur);
4477 				size_t runcur_pageind =
4478 				    (((uintptr_t)bin->runcur -
4479 				    (uintptr_t)runcur_chunk)) >> pagesize_2pow;
4480 				arena_chunk_map_t *runcur_mapelm =
4481 				    &runcur_chunk->map[runcur_pageind];
4482 
4483 				/* Insert runcur. */
4484 				assert(arena_run_tree_search(&bin->runs,
4485 				    runcur_mapelm) == NULL);
4486 				arena_run_tree_insert(&bin->runs,
4487 				    runcur_mapelm);
4488 			}
4489 			bin->runcur = run;
4490 		} else {
4491 			size_t run_pageind = (((uintptr_t)run -
4492 			    (uintptr_t)chunk)) >> pagesize_2pow;
4493 			arena_chunk_map_t *run_mapelm =
4494 			    &chunk->map[run_pageind];
4495 
4496 			assert(arena_run_tree_search(&bin->runs, run_mapelm) ==
4497 			    NULL);
4498 			arena_run_tree_insert(&bin->runs, run_mapelm);
4499 		}
4500 	}
4501 #ifdef MALLOC_STATS
4502 	arena->stats.allocated_small -= size;
4503 	arena->stats.ndalloc_small++;
4504 #endif
4505 }
4506 
4507 static void
4508 arena_dalloc_large(arena_t *arena, arena_chunk_t *chunk, void *ptr)
4509 {
4510 	/* Large allocation. */
4511 	malloc_spin_lock(&arena->lock);
4512 
4513 #ifdef MALLOC_FILL
4514 #ifndef MALLOC_STATS
4515 	if (opt_junk)
4516 #endif
4517 #endif
4518 	{
4519 		size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >>
4520 		    pagesize_2pow;
4521 		size_t size = chunk->map[pageind].bits & ~pagesize_mask;
4522 
4523 #ifdef MALLOC_FILL
4524 #ifdef MALLOC_STATS
4525 		if (opt_junk)
4526 #endif
4527 			memset(ptr, 0x5a, size);
4528 #endif
4529 #ifdef MALLOC_STATS
4530 		arena->stats.allocated_large -= size;
4531 #endif
4532 	}
4533 #ifdef MALLOC_STATS
4534 	arena->stats.ndalloc_large++;
4535 #endif
4536 
4537 	arena_run_dalloc(arena, (arena_run_t *)ptr, true);
4538 	malloc_spin_unlock(&arena->lock);
4539 }
4540 
4541 static inline void
4542 arena_dalloc(arena_t *arena, arena_chunk_t *chunk, void *ptr)
4543 {
4544 	size_t pageind;
4545 	arena_chunk_map_t *mapelm;
4546 
4547 	assert(arena != NULL);
4548 	assert(arena->magic == ARENA_MAGIC);
4549 	assert(chunk->arena == arena);
4550 	assert(ptr != NULL);
4551 	assert(CHUNK_ADDR2BASE(ptr) != ptr);
4552 
4553 	pageind = (((uintptr_t)ptr - (uintptr_t)chunk) >> pagesize_2pow);
4554 	mapelm = &chunk->map[pageind];
4555 	assert((mapelm->bits & CHUNK_MAP_ALLOCATED) != 0);
4556 	if ((mapelm->bits & CHUNK_MAP_LARGE) == 0) {
4557 		/* Small allocation. */
4558 		malloc_spin_lock(&arena->lock);
4559 		arena_dalloc_small(arena, chunk, ptr, mapelm);
4560 		malloc_spin_unlock(&arena->lock);
4561 	} else
4562 		arena_dalloc_large(arena, chunk, ptr);
4563 	VALGRIND_FREELIKE_BLOCK(ptr, 0);
4564 }
4565 
4566 static inline void
4567 idalloc(void *ptr)
4568 {
4569 	arena_chunk_t *chunk;
4570 
4571 	assert(ptr != NULL);
4572 
4573 	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
4574 	if (chunk != ptr)
4575 		arena_dalloc(chunk->arena, chunk, ptr);
4576 	else
4577 		huge_dalloc(ptr);
4578 }
4579 
4580 static void
4581 arena_ralloc_large_shrink(arena_t *arena, arena_chunk_t *chunk, void *ptr,
4582     size_t size, size_t oldsize)
4583 {
4584 
4585 	assert(size < oldsize);
4586 
4587 	/*
4588 	 * Shrink the run, and make trailing pages available for other
4589 	 * allocations.
4590 	 */
4591 #ifdef MALLOC_BALANCE
4592 	arena_lock_balance(arena);
4593 #else
4594 	malloc_spin_lock(&arena->lock);
4595 #endif
4596 	arena_run_trim_tail(arena, chunk, (arena_run_t *)ptr, oldsize, size,
4597 	    true);
4598 #ifdef MALLOC_STATS
4599 	arena->stats.allocated_large -= oldsize - size;
4600 #endif
4601 	malloc_spin_unlock(&arena->lock);
4602 }
4603 
4604 static bool
4605 arena_ralloc_large_grow(arena_t *arena, arena_chunk_t *chunk, void *ptr,
4606     size_t size, size_t oldsize)
4607 {
4608 	size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> pagesize_2pow;
4609 	size_t npages = oldsize >> pagesize_2pow;
4610 
4611 	assert(oldsize == (chunk->map[pageind].bits & ~pagesize_mask));
4612 
4613 	/* Try to extend the run. */
4614 	assert(size > oldsize);
4615 #ifdef MALLOC_BALANCE
4616 	arena_lock_balance(arena);
4617 #else
4618 	malloc_spin_lock(&arena->lock);
4619 #endif
4620 	if (pageind + npages < chunk_npages && (chunk->map[pageind+npages].bits
4621 	    & CHUNK_MAP_ALLOCATED) == 0 && (chunk->map[pageind+npages].bits &
4622 	    ~pagesize_mask) >= size - oldsize) {
4623 		/*
4624 		 * The next run is available and sufficiently large.  Split the
4625 		 * following run, then merge the first part with the existing
4626 		 * allocation.
4627 		 */
4628 		arena_run_split(arena, (arena_run_t *)((uintptr_t)chunk +
4629 		    ((pageind+npages) << pagesize_2pow)), size - oldsize, true,
4630 		    false);
4631 
4632 		chunk->map[pageind].bits = size | CHUNK_MAP_LARGE |
4633 		    CHUNK_MAP_ALLOCATED;
4634 		chunk->map[pageind+npages].bits = CHUNK_MAP_LARGE |
4635 		    CHUNK_MAP_ALLOCATED;
4636 
4637 #ifdef MALLOC_STATS
4638 		arena->stats.allocated_large += size - oldsize;
4639 #endif
4640 		malloc_spin_unlock(&arena->lock);
4641 		return (false);
4642 	}
4643 	malloc_spin_unlock(&arena->lock);
4644 
4645 	return (true);
4646 }
4647 
4648 /*
4649  * Try to resize a large allocation, in order to avoid copying.  This will
4650  * always fail if growing an object, and the following run is already in use.
4651  */
4652 static bool
4653 arena_ralloc_large(void *ptr, size_t size, size_t oldsize)
4654 {
4655 	size_t psize;
4656 
4657 	psize = PAGE_CEILING(size);
4658 	if (psize == oldsize) {
4659 		/* Same size class. */
4660 #ifdef MALLOC_FILL
4661 		if (opt_junk && size < oldsize) {
4662 			memset((void *)((uintptr_t)ptr + size), 0x5a, oldsize -
4663 			    size);
4664 		}
4665 #endif
4666 		return (false);
4667 	} else {
4668 		arena_chunk_t *chunk;
4669 		arena_t *arena;
4670 
4671 		chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
4672 		arena = chunk->arena;
4673 		assert(arena->magic == ARENA_MAGIC);
4674 
4675 		if (psize < oldsize) {
4676 #ifdef MALLOC_FILL
4677 			/* Fill before shrinking in order avoid a race. */
4678 			if (opt_junk) {
4679 				memset((void *)((uintptr_t)ptr + size), 0x5a,
4680 				    oldsize - size);
4681 			}
4682 #endif
4683 			arena_ralloc_large_shrink(arena, chunk, ptr, psize,
4684 			    oldsize);
4685 			return (false);
4686 		} else {
4687 			bool ret = arena_ralloc_large_grow(arena, chunk, ptr,
4688 			    psize, oldsize);
4689 #ifdef MALLOC_FILL
4690 			if (ret == false && opt_zero) {
4691 				memset((void *)((uintptr_t)ptr + oldsize), 0,
4692 				    size - oldsize);
4693 			}
4694 #endif
4695 			return (ret);
4696 		}
4697 	}
4698 }
4699 
4700 static void *
4701 arena_ralloc(void *ptr, size_t size, size_t oldsize)
4702 {
4703 	void *ret;
4704 	size_t copysize;
4705 
4706 	/* Try to avoid moving the allocation. */
4707 	if (size < small_min) {
4708 		if (oldsize < small_min &&
4709 		    ffs((int)(pow2_ceil(size) >> (TINY_MIN_2POW + 1)))
4710 		    == ffs((int)(pow2_ceil(oldsize) >> (TINY_MIN_2POW + 1))))
4711 			goto IN_PLACE; /* Same size class. */
4712 	} else if (size <= small_max) {
4713 		if (oldsize >= small_min && oldsize <= small_max &&
4714 		    (QUANTUM_CEILING(size) >> opt_quantum_2pow)
4715 		    == (QUANTUM_CEILING(oldsize) >> opt_quantum_2pow))
4716 			goto IN_PLACE; /* Same size class. */
4717 	} else if (size <= bin_maxclass) {
4718 		if (oldsize > small_max && oldsize <= bin_maxclass &&
4719 		    pow2_ceil(size) == pow2_ceil(oldsize))
4720 			goto IN_PLACE; /* Same size class. */
4721 	} else if (oldsize > bin_maxclass && oldsize <= arena_maxclass) {
4722 		assert(size > bin_maxclass);
4723 		if (arena_ralloc_large(ptr, size, oldsize) == false)
4724 			return (ptr);
4725 	}
4726 
4727 	/*
4728 	 * If we get here, then size and oldsize are different enough that we
4729 	 * need to move the object.  In that case, fall back to allocating new
4730 	 * space and copying.
4731 	 */
4732 	ret = arena_malloc(choose_arena(), size, false);
4733 	if (ret == NULL)
4734 		return (NULL);
4735 
4736 	/* Junk/zero-filling were already done by arena_malloc(). */
4737 	copysize = (size < oldsize) ? size : oldsize;
4738 #ifdef VM_COPY_MIN
4739 	if (copysize >= VM_COPY_MIN)
4740 		pages_copy(ret, ptr, copysize);
4741 	else
4742 #endif
4743 		memcpy(ret, ptr, copysize);
4744 	idalloc(ptr);
4745 	return (ret);
4746 IN_PLACE:
4747 #ifdef MALLOC_FILL
4748 	if (opt_junk && size < oldsize)
4749 		memset((void *)((uintptr_t)ptr + size), 0x5a, oldsize - size);
4750 	else if (opt_zero && size > oldsize)
4751 		memset((void *)((uintptr_t)ptr + oldsize), 0, size - oldsize);
4752 #endif
4753 	return (ptr);
4754 }
4755 
4756 static inline void *
4757 iralloc(void *ptr, size_t size)
4758 {
4759 	size_t oldsize;
4760 
4761 	assert(ptr != NULL);
4762 	assert(size != 0);
4763 
4764 	oldsize = isalloc(ptr);
4765 
4766 #ifndef MALLOC_VALGRIND
4767 	if (size <= arena_maxclass)
4768 		return (arena_ralloc(ptr, size, oldsize));
4769 	else
4770 		return (huge_ralloc(ptr, size, oldsize));
4771 #else
4772 	/*
4773 	 * Valgrind does not provide a public interface for modifying an
4774 	 * existing allocation, so use malloc/memcpy/free instead.
4775 	 */
4776 	{
4777 		void *ret = imalloc(size);
4778 		if (ret != NULL) {
4779 			if (oldsize < size)
4780 			    memcpy(ret, ptr, oldsize);
4781 			else
4782 			    memcpy(ret, ptr, size);
4783 			idalloc(ptr);
4784 		}
4785 		return (ret);
4786 	}
4787 #endif
4788 }
4789 
4790 static bool
4791 arena_new(arena_t *arena)
4792 {
4793 	unsigned i;
4794 	arena_bin_t *bin;
4795 	size_t pow2_size, prev_run_size;
4796 
4797 	if (malloc_spin_init(&arena->lock))
4798 		return (true);
4799 
4800 #ifdef MALLOC_STATS
4801 	memset(&arena->stats, 0, sizeof(arena_stats_t));
4802 #endif
4803 
4804 	arena->chunk_seq = 0;
4805 
4806 	/* Initialize chunks. */
4807 	arena_chunk_tree_dirty_new(&arena->chunks_dirty);
4808 	arena->spare = NULL;
4809 
4810 	arena->ndirty = 0;
4811 
4812 	arena_avail_tree_new(&arena->runs_avail);
4813 
4814 #ifdef MALLOC_BALANCE
4815 	arena->contention = 0;
4816 #endif
4817 
4818 	/* Initialize bins. */
4819 	prev_run_size = pagesize;
4820 
4821 	/* (2^n)-spaced tiny bins. */
4822 	for (i = 0; i < ntbins; i++) {
4823 		bin = &arena->bins[i];
4824 		bin->runcur = NULL;
4825 		arena_run_tree_new(&bin->runs);
4826 
4827 		bin->reg_size = ((size_t)1 << (TINY_MIN_2POW + i));
4828 
4829 		prev_run_size = arena_bin_run_size_calc(bin, prev_run_size);
4830 
4831 #ifdef MALLOC_STATS
4832 		memset(&bin->stats, 0, sizeof(malloc_bin_stats_t));
4833 #endif
4834 	}
4835 
4836 	/* Quantum-spaced bins. */
4837 	for (; i < ntbins + nqbins; i++) {
4838 		bin = &arena->bins[i];
4839 		bin->runcur = NULL;
4840 		arena_run_tree_new(&bin->runs);
4841 
4842 		bin->reg_size = quantum * (i - ntbins + 1);
4843 
4844 		pow2_size = pow2_ceil(quantum * (i - ntbins + 1));
4845 		prev_run_size = arena_bin_run_size_calc(bin, prev_run_size);
4846 
4847 #ifdef MALLOC_STATS
4848 		memset(&bin->stats, 0, sizeof(malloc_bin_stats_t));
4849 #endif
4850 	}
4851 
4852 	/* (2^n)-spaced sub-page bins. */
4853 	for (; i < ntbins + nqbins + nsbins; i++) {
4854 		bin = &arena->bins[i];
4855 		bin->runcur = NULL;
4856 		arena_run_tree_new(&bin->runs);
4857 
4858 		bin->reg_size = (small_max << (i - (ntbins + nqbins) + 1));
4859 
4860 		prev_run_size = arena_bin_run_size_calc(bin, prev_run_size);
4861 
4862 #ifdef MALLOC_STATS
4863 		memset(&bin->stats, 0, sizeof(malloc_bin_stats_t));
4864 #endif
4865 	}
4866 
4867 #ifdef MALLOC_DEBUG
4868 	arena->magic = ARENA_MAGIC;
4869 #endif
4870 
4871 	return (false);
4872 }
4873 
4874 /* Create a new arena and insert it into the arenas array at index ind. */
4875 static arena_t *
4876 arenas_extend(unsigned ind)
4877 {
4878 	arena_t *ret;
4879 
4880 	/* Allocate enough space for trailing bins. */
4881 	ret = (arena_t *)base_alloc(sizeof(arena_t)
4882 	    + (sizeof(arena_bin_t) * (ntbins + nqbins + nsbins - 1)));
4883 	if (ret != NULL && arena_new(ret) == false) {
4884 		arenas[ind] = ret;
4885 		return (ret);
4886 	}
4887 	/* Only reached if there is an OOM error. */
4888 
4889 	/*
4890 	 * OOM here is quite inconvenient to propagate, since dealing with it
4891 	 * would require a check for failure in the fast path.  Instead, punt
4892 	 * by using arenas[0].  In practice, this is an extremely unlikely
4893 	 * failure.
4894 	 */
4895 	_malloc_message(_getprogname(),
4896 	    ": (malloc) Error initializing arena\n", "", "");
4897 	if (opt_abort)
4898 		abort();
4899 
4900 	return (arenas[0]);
4901 }
4902 
4903 /*
4904  * End arena.
4905  */
4906 /******************************************************************************/
4907 /*
4908  * Begin general internal functions.
4909  */
4910 
4911 static void *
4912 huge_malloc(size_t size, bool zero)
4913 {
4914 	void *ret;
4915 	size_t csize;
4916 #ifdef MALLOC_DECOMMIT
4917 	size_t psize;
4918 #endif
4919 	extent_node_t *node;
4920 
4921 	/* Allocate one or more contiguous chunks for this request. */
4922 
4923 	csize = CHUNK_CEILING(size);
4924 	if (csize == 0) {
4925 		/* size is large enough to cause size_t wrap-around. */
4926 		return (NULL);
4927 	}
4928 
4929 	/* Allocate an extent node with which to track the chunk. */
4930 	node = base_node_alloc();
4931 	if (node == NULL)
4932 		return (NULL);
4933 
4934 	ret = chunk_alloc(csize, zero, true);
4935 	if (ret == NULL) {
4936 		base_node_dealloc(node);
4937 		return (NULL);
4938 	}
4939 
4940 	/* Insert node into huge. */
4941 	node->addr = ret;
4942 #ifdef MALLOC_DECOMMIT
4943 	psize = PAGE_CEILING(size);
4944 	node->size = psize;
4945 #else
4946 	node->size = csize;
4947 #endif
4948 
4949 	malloc_mutex_lock(&huge_mtx);
4950 	extent_tree_ad_insert(&huge, node);
4951 #ifdef MALLOC_STATS
4952 	huge_nmalloc++;
4953 #  ifdef MALLOC_DECOMMIT
4954 	huge_allocated += psize;
4955 #  else
4956 	huge_allocated += csize;
4957 #  endif
4958 #endif
4959 	malloc_mutex_unlock(&huge_mtx);
4960 
4961 #ifdef MALLOC_DECOMMIT
4962 	if (csize - psize > 0)
4963 		pages_decommit((void *)((uintptr_t)ret + psize), csize - psize);
4964 #endif
4965 
4966 #ifdef MALLOC_DECOMMIT
4967 	VALGRIND_MALLOCLIKE_BLOCK(ret, psize, 0, zero);
4968 #else
4969 	VALGRIND_MALLOCLIKE_BLOCK(ret, csize, 0, zero);
4970 #endif
4971 
4972 #ifdef MALLOC_FILL
4973 	if (zero == false) {
4974 		if (opt_junk)
4975 #  ifdef MALLOC_DECOMMIT
4976 			memset(ret, 0xa5, psize);
4977 #  else
4978 			memset(ret, 0xa5, csize);
4979 #  endif
4980 		else if (opt_zero)
4981 #  ifdef MALLOC_DECOMMIT
4982 			memset(ret, 0, psize);
4983 #  else
4984 			memset(ret, 0, csize);
4985 #  endif
4986 	}
4987 #endif
4988 
4989 	return (ret);
4990 }
4991 
4992 /* Only handles large allocations that require more than chunk alignment. */
4993 static void *
4994 huge_palloc(size_t alignment, size_t size)
4995 {
4996 	void *ret;
4997 	size_t alloc_size, chunk_size, offset;
4998 #ifdef MALLOC_DECOMMIT
4999 	size_t psize;
5000 #endif
5001 	extent_node_t *node;
5002 	int pfd;
5003 
5004 	/*
5005 	 * This allocation requires alignment that is even larger than chunk
5006 	 * alignment.  This means that huge_malloc() isn't good enough.
5007 	 *
5008 	 * Allocate almost twice as many chunks as are demanded by the size or
5009 	 * alignment, in order to assure the alignment can be achieved, then
5010 	 * unmap leading and trailing chunks.
5011 	 */
5012 	assert(alignment >= chunksize);
5013 
5014 	chunk_size = CHUNK_CEILING(size);
5015 
5016 	if (size >= alignment)
5017 		alloc_size = chunk_size + alignment - chunksize;
5018 	else
5019 		alloc_size = (alignment << 1) - chunksize;
5020 
5021 	/* Allocate an extent node with which to track the chunk. */
5022 	node = base_node_alloc();
5023 	if (node == NULL)
5024 		return (NULL);
5025 
5026 	/*
5027 	 * Windows requires that there be a 1:1 mapping between VM
5028 	 * allocation/deallocation operations.  Therefore, take care here to
5029 	 * acquire the final result via one mapping operation.
5030 	 *
5031 	 * The MALLOC_PAGEFILE code also benefits from this mapping algorithm,
5032 	 * since it reduces the number of page files.
5033 	 */
5034 #ifdef MALLOC_PAGEFILE
5035 	if (opt_pagefile) {
5036 		pfd = pagefile_init(size);
5037 		if (pfd == -1)
5038 			return (NULL);
5039 	} else
5040 #endif
5041 		pfd = -1;
5042 #ifdef JEMALLOC_USES_MAP_ALIGN
5043 		ret = pages_map_align(chunk_size, pfd, alignment);
5044 #else
5045 	do {
5046 		void *over;
5047 
5048 		over = chunk_alloc(alloc_size, false, false);
5049 		if (over == NULL) {
5050 			base_node_dealloc(node);
5051 			ret = NULL;
5052 			goto RETURN;
5053 		}
5054 
5055 		offset = (uintptr_t)over & (alignment - 1);
5056 		assert((offset & chunksize_mask) == 0);
5057 		assert(offset < alloc_size);
5058 		ret = (void *)((uintptr_t)over + offset);
5059 		chunk_dealloc(over, alloc_size);
5060 		ret = pages_map(ret, chunk_size, pfd);
5061 		/*
5062 		 * Failure here indicates a race with another thread, so try
5063 		 * again.
5064 		 */
5065 	} while (ret == NULL);
5066 #endif
5067 	/* Insert node into huge. */
5068 	node->addr = ret;
5069 #ifdef MALLOC_DECOMMIT
5070 	psize = PAGE_CEILING(size);
5071 	node->size = psize;
5072 #else
5073 	node->size = chunk_size;
5074 #endif
5075 
5076 	malloc_mutex_lock(&huge_mtx);
5077 	extent_tree_ad_insert(&huge, node);
5078 #ifdef MALLOC_STATS
5079 	huge_nmalloc++;
5080 #  ifdef MALLOC_DECOMMIT
5081 	huge_allocated += psize;
5082 #  else
5083 	huge_allocated += chunk_size;
5084 #  endif
5085 #endif
5086 	malloc_mutex_unlock(&huge_mtx);
5087 
5088 #ifdef MALLOC_DECOMMIT
5089 	if (chunk_size - psize > 0) {
5090 		pages_decommit((void *)((uintptr_t)ret + psize),
5091 		    chunk_size - psize);
5092 	}
5093 #endif
5094 
5095 #ifdef MALLOC_DECOMMIT
5096 	VALGRIND_MALLOCLIKE_BLOCK(ret, psize, 0, false);
5097 #else
5098 	VALGRIND_MALLOCLIKE_BLOCK(ret, chunk_size, 0, false);
5099 #endif
5100 
5101 #ifdef MALLOC_FILL
5102 	if (opt_junk)
5103 #  ifdef MALLOC_DECOMMIT
5104 		memset(ret, 0xa5, psize);
5105 #  else
5106 		memset(ret, 0xa5, chunk_size);
5107 #  endif
5108 	else if (opt_zero)
5109 #  ifdef MALLOC_DECOMMIT
5110 		memset(ret, 0, psize);
5111 #  else
5112 		memset(ret, 0, chunk_size);
5113 #  endif
5114 #endif
5115 
5116 RETURN:
5117 #ifdef MALLOC_PAGEFILE
5118 	if (pfd != -1)
5119 		pagefile_close(pfd);
5120 #endif
5121 	return (ret);
5122 }
5123 
5124 static void *
5125 huge_ralloc(void *ptr, size_t size, size_t oldsize)
5126 {
5127 	void *ret;
5128 	size_t copysize;
5129 
5130 	/* Avoid moving the allocation if the size class would not change. */
5131 
5132 	if (oldsize > arena_maxclass &&
5133 	    CHUNK_CEILING(size) == CHUNK_CEILING(oldsize)) {
5134 #ifdef MALLOC_DECOMMIT
5135 		size_t psize = PAGE_CEILING(size);
5136 #endif
5137 #ifdef MALLOC_FILL
5138 		if (opt_junk && size < oldsize) {
5139 			memset((void *)((uintptr_t)ptr + size), 0x5a, oldsize
5140 			    - size);
5141 		}
5142 #endif
5143 #ifdef MALLOC_DECOMMIT
5144 		if (psize < oldsize) {
5145 			extent_node_t *node, key;
5146 
5147 			pages_decommit((void *)((uintptr_t)ptr + psize),
5148 			    oldsize - psize);
5149 
5150 			/* Update recorded size. */
5151 			malloc_mutex_lock(&huge_mtx);
5152 			key.addr = __DECONST(void *, ptr);
5153 			node = extent_tree_ad_search(&huge, &key);
5154 			assert(node != NULL);
5155 			assert(node->size == oldsize);
5156 #  ifdef MALLOC_STATS
5157 			huge_allocated -= oldsize - psize;
5158 #  endif
5159 			node->size = psize;
5160 			malloc_mutex_unlock(&huge_mtx);
5161 		} else if (psize > oldsize) {
5162 			extent_node_t *node, key;
5163 
5164 			pages_commit((void *)((uintptr_t)ptr + oldsize),
5165 			    psize - oldsize);
5166 
5167 			/* Update recorded size. */
5168 			malloc_mutex_lock(&huge_mtx);
5169 			key.addr = __DECONST(void *, ptr);
5170 			node = extent_tree_ad_search(&huge, &key);
5171 			assert(node != NULL);
5172 			assert(node->size == oldsize);
5173 #  ifdef MALLOC_STATS
5174 			huge_allocated += psize - oldsize;
5175 #  endif
5176 			node->size = psize;
5177 			malloc_mutex_unlock(&huge_mtx);
5178 		}
5179 #endif
5180 #ifdef MALLOC_FILL
5181 		if (opt_zero && size > oldsize) {
5182 			memset((void *)((uintptr_t)ptr + oldsize), 0, size
5183 			    - oldsize);
5184 		}
5185 #endif
5186 		return (ptr);
5187 	}
5188 
5189 	/*
5190 	 * If we get here, then size and oldsize are different enough that we
5191 	 * need to use a different size class.  In that case, fall back to
5192 	 * allocating new space and copying.
5193 	 */
5194 	ret = huge_malloc(size, false);
5195 	if (ret == NULL)
5196 		return (NULL);
5197 
5198 	copysize = (size < oldsize) ? size : oldsize;
5199 #ifdef VM_COPY_MIN
5200 	if (copysize >= VM_COPY_MIN)
5201 		pages_copy(ret, ptr, copysize);
5202 	else
5203 #endif
5204 		memcpy(ret, ptr, copysize);
5205 	idalloc(ptr);
5206 	return (ret);
5207 }
5208 
5209 static void
5210 huge_dalloc(void *ptr)
5211 {
5212 	extent_node_t *node, key;
5213 
5214 	malloc_mutex_lock(&huge_mtx);
5215 
5216 	/* Extract from tree of huge allocations. */
5217 	key.addr = ptr;
5218 	node = extent_tree_ad_search(&huge, &key);
5219 	assert(node != NULL);
5220 	assert(node->addr == ptr);
5221 	extent_tree_ad_remove(&huge, node);
5222 
5223 #ifdef MALLOC_STATS
5224 	huge_ndalloc++;
5225 	huge_allocated -= node->size;
5226 #endif
5227 
5228 	malloc_mutex_unlock(&huge_mtx);
5229 
5230 	/* Unmap chunk. */
5231 #ifdef MALLOC_FILL
5232 	if (opt_junk)
5233 		memset(node->addr, 0x5a, node->size);
5234 #endif
5235 #ifdef MALLOC_DECOMMIT
5236 	chunk_dealloc(node->addr, CHUNK_CEILING(node->size));
5237 #else
5238 	chunk_dealloc(node->addr, node->size);
5239 #endif
5240 	VALGRIND_FREELIKE_BLOCK(node->addr, 0);
5241 
5242 	base_node_dealloc(node);
5243 }
5244 
5245 #ifdef MOZ_MEMORY_BSD
5246 static inline unsigned
5247 malloc_ncpus(void)
5248 {
5249 	unsigned ret;
5250 	int mib[2];
5251 	size_t len;
5252 
5253 	mib[0] = CTL_HW;
5254 	mib[1] = HW_NCPU;
5255 	len = sizeof(ret);
5256 	if (sysctl(mib, 2, &ret, &len, (void *) 0, 0) == -1) {
5257 		/* Error. */
5258 		return (1);
5259 	}
5260 
5261 	return (ret);
5262 }
5263 #elif (defined(MOZ_MEMORY_LINUX))
5264 #include <fcntl.h>
5265 
5266 static inline unsigned
5267 malloc_ncpus(void)
5268 {
5269 	unsigned ret;
5270 	int fd, nread, column;
5271 	char buf[1024];
5272 	static const char matchstr[] = "processor\t:";
5273 	int i;
5274 
5275 	/*
5276 	 * sysconf(3) would be the preferred method for determining the number
5277 	 * of CPUs, but it uses malloc internally, which causes untennable
5278 	 * recursion during malloc initialization.
5279 	 */
5280 	fd = open("/proc/cpuinfo", O_RDONLY);
5281 	if (fd == -1)
5282 		return (1); /* Error. */
5283 	/*
5284 	 * Count the number of occurrences of matchstr at the beginnings of
5285 	 * lines.  This treats hyperthreaded CPUs as multiple processors.
5286 	 */
5287 	column = 0;
5288 	ret = 0;
5289 	while (true) {
5290 		nread = read(fd, &buf, sizeof(buf));
5291 		if (nread <= 0)
5292 			break; /* EOF or error. */
5293 		for (i = 0;i < nread;i++) {
5294 			char c = buf[i];
5295 			if (c == '\n')
5296 				column = 0;
5297 			else if (column != -1) {
5298 				if (c == matchstr[column]) {
5299 					column++;
5300 					if (column == sizeof(matchstr) - 1) {
5301 						column = -1;
5302 						ret++;
5303 					}
5304 				} else
5305 					column = -1;
5306 			}
5307 		}
5308 	}
5309 
5310 	if (ret == 0)
5311 		ret = 1; /* Something went wrong in the parser. */
5312 	close(fd);
5313 
5314 	return (ret);
5315 }
5316 #elif (defined(MOZ_MEMORY_DARWIN))
5317 #include <mach/mach_init.h>
5318 #include <mach/mach_host.h>
5319 
5320 static inline unsigned
5321 malloc_ncpus(void)
5322 {
5323 	kern_return_t error;
5324 	natural_t n;
5325 	processor_info_array_t pinfo;
5326 	mach_msg_type_number_t pinfocnt;
5327 
5328 	error = host_processor_info(mach_host_self(), PROCESSOR_BASIC_INFO,
5329 				    &n, &pinfo, &pinfocnt);
5330 	if (error != KERN_SUCCESS)
5331 		return (1); /* Error. */
5332 	else
5333 		return (n);
5334 }
5335 #elif (defined(MOZ_MEMORY_SOLARIS))
5336 
5337 static inline unsigned
5338 malloc_ncpus(void)
5339 {
5340 	return sysconf(_SC_NPROCESSORS_ONLN);
5341 }
5342 #else
5343 static inline unsigned
5344 malloc_ncpus(void)
5345 {
5346 
5347 	/*
5348 	 * We lack a way to determine the number of CPUs on this platform, so
5349 	 * assume 1 CPU.
5350 	 */
5351 	return (1);
5352 }
5353 #endif
5354 
5355 static void
5356 malloc_print_stats(void)
5357 {
5358 
5359 	if (opt_print_stats) {
5360 		char s[UMAX2S_BUFSIZE];
5361 		_malloc_message("___ Begin malloc statistics ___\n", "", "",
5362 		    "");
5363 		_malloc_message("Assertions ",
5364 #ifdef NDEBUG
5365 		    "disabled",
5366 #else
5367 		    "enabled",
5368 #endif
5369 		    "\n", "");
5370 		_malloc_message("Boolean MALLOC_OPTIONS: ",
5371 		    opt_abort ? "A" : "a", "", "");
5372 #ifdef MALLOC_FILL
5373 		_malloc_message(opt_junk ? "J" : "j", "", "", "");
5374 #endif
5375 #ifdef MALLOC_PAGEFILE
5376 		_malloc_message(opt_pagefile ? "o" : "O", "", "", "");
5377 #endif
5378 		_malloc_message("P", "", "", "");
5379 #ifdef MALLOC_UTRACE
5380 		_malloc_message(opt_utrace ? "U" : "u", "", "", "");
5381 #endif
5382 #ifdef MALLOC_SYSV
5383 		_malloc_message(opt_sysv ? "V" : "v", "", "", "");
5384 #endif
5385 #ifdef MALLOC_XMALLOC
5386 		_malloc_message(opt_xmalloc ? "X" : "x", "", "", "");
5387 #endif
5388 #ifdef MALLOC_FILL
5389 		_malloc_message(opt_zero ? "Z" : "z", "", "", "");
5390 #endif
5391 		_malloc_message("\n", "", "", "");
5392 
5393 		_malloc_message("CPUs: ", umax2s(ncpus, s), "\n", "");
5394 		_malloc_message("Max arenas: ", umax2s(narenas, s), "\n", "");
5395 #ifdef MALLOC_BALANCE
5396 		_malloc_message("Arena balance threshold: ",
5397 		    umax2s(opt_balance_threshold, s), "\n", "");
5398 #endif
5399 		_malloc_message("Pointer size: ", umax2s(sizeof(void *), s),
5400 		    "\n", "");
5401 		_malloc_message("Quantum size: ", umax2s(quantum, s), "\n", "");
5402 		_malloc_message("Max small size: ", umax2s(small_max, s), "\n",
5403 		    "");
5404 		_malloc_message("Max dirty pages per arena: ",
5405 		    umax2s(opt_dirty_max, s), "\n", "");
5406 
5407 		_malloc_message("Chunk size: ", umax2s(chunksize, s), "", "");
5408 		_malloc_message(" (2^", umax2s(opt_chunk_2pow, s), ")\n", "");
5409 
5410 #ifdef MALLOC_STATS
5411 		{
5412 			size_t allocated, mapped;
5413 #ifdef MALLOC_BALANCE
5414 			uint64_t nbalance = 0;
5415 #endif
5416 			unsigned i;
5417 			arena_t *arena;
5418 
5419 			/* Calculate and print allocated/mapped stats. */
5420 
5421 			/* arenas. */
5422 			for (i = 0, allocated = 0; i < narenas; i++) {
5423 				if (arenas[i] != NULL) {
5424 					malloc_spin_lock(&arenas[i]->lock);
5425 					allocated +=
5426 					    arenas[i]->stats.allocated_small;
5427 					allocated +=
5428 					    arenas[i]->stats.allocated_large;
5429 #ifdef MALLOC_BALANCE
5430 					nbalance += arenas[i]->stats.nbalance;
5431 #endif
5432 					malloc_spin_unlock(&arenas[i]->lock);
5433 				}
5434 			}
5435 
5436 			/* huge/base. */
5437 			malloc_mutex_lock(&huge_mtx);
5438 			allocated += huge_allocated;
5439 			mapped = stats_chunks.curchunks * chunksize;
5440 			malloc_mutex_unlock(&huge_mtx);
5441 
5442 			malloc_mutex_lock(&base_mtx);
5443 			mapped += base_mapped;
5444 			malloc_mutex_unlock(&base_mtx);
5445 
5446 #ifdef MOZ_MEMORY_WINDOWS
5447 			malloc_printf("Allocated: %lu, mapped: %lu\n",
5448 			    allocated, mapped);
5449 #else
5450 			malloc_printf("Allocated: %zu, mapped: %zu\n",
5451 			    allocated, mapped);
5452 #endif
5453 
5454 			malloc_mutex_lock(&reserve_mtx);
5455 			malloc_printf("Reserve:    min          "
5456 			    "cur          max\n");
5457 #ifdef MOZ_MEMORY_WINDOWS
5458 			malloc_printf("   %12lu %12lu %12lu\n",
5459 			    CHUNK_CEILING(reserve_min) >> opt_chunk_2pow,
5460 			    reserve_cur >> opt_chunk_2pow,
5461 			    reserve_max >> opt_chunk_2pow);
5462 #else
5463 			malloc_printf("   %12zu %12zu %12zu\n",
5464 			    CHUNK_CEILING(reserve_min) >> opt_chunk_2pow,
5465 			    reserve_cur >> opt_chunk_2pow,
5466 			    reserve_max >> opt_chunk_2pow);
5467 #endif
5468 			malloc_mutex_unlock(&reserve_mtx);
5469 
5470 #ifdef MALLOC_BALANCE
5471 			malloc_printf("Arena balance reassignments: %llu\n",
5472 			    nbalance);
5473 #endif
5474 
5475 			/* Print chunk stats. */
5476 			{
5477 				chunk_stats_t chunks_stats;
5478 
5479 				malloc_mutex_lock(&huge_mtx);
5480 				chunks_stats = stats_chunks;
5481 				malloc_mutex_unlock(&huge_mtx);
5482 
5483 				malloc_printf("chunks: nchunks   "
5484 				    "highchunks    curchunks\n");
5485 				malloc_printf("  %13llu%13lu%13lu\n",
5486 				    chunks_stats.nchunks,
5487 				    chunks_stats.highchunks,
5488 				    chunks_stats.curchunks);
5489 			}
5490 
5491 			/* Print chunk stats. */
5492 			malloc_printf(
5493 			    "huge: nmalloc      ndalloc    allocated\n");
5494 #ifdef MOZ_MEMORY_WINDOWS
5495 			malloc_printf(" %12llu %12llu %12lu\n",
5496 			    huge_nmalloc, huge_ndalloc, huge_allocated);
5497 #else
5498 			malloc_printf(" %12llu %12llu %12zu\n",
5499 			    huge_nmalloc, huge_ndalloc, huge_allocated);
5500 #endif
5501 			/* Print stats for each arena. */
5502 			for (i = 0; i < narenas; i++) {
5503 				arena = arenas[i];
5504 				if (arena != NULL) {
5505 					malloc_printf(
5506 					    "\narenas[%u]:\n", i);
5507 					malloc_spin_lock(&arena->lock);
5508 					stats_print(arena);
5509 					malloc_spin_unlock(&arena->lock);
5510 				}
5511 			}
5512 		}
5513 #endif /* #ifdef MALLOC_STATS */
5514 		_malloc_message("--- End malloc statistics ---\n", "", "", "");
5515 	}
5516 }
5517 
5518 /*
5519  * FreeBSD's pthreads implementation calls malloc(3), so the malloc
5520  * implementation has to take pains to avoid infinite recursion during
5521  * initialization.
5522  */
5523 #if (defined(MOZ_MEMORY_WINDOWS) || defined(MOZ_MEMORY_DARWIN)) && !defined(MOZ_MEMORY_WINCE)
5524 #define	malloc_init() false
5525 #else
5526 static inline bool
5527 malloc_init(void)
5528 {
5529 
5530 	if (malloc_initialized == false)
5531 		return (malloc_init_hard());
5532 
5533 	return (false);
5534 }
5535 #endif
5536 
5537 #if !defined(MOZ_MEMORY_WINDOWS) || defined(MOZ_MEMORY_WINCE)
5538 static
5539 #endif
5540 bool
5541 je_malloc_init_hard(void)
5542 {
5543 	unsigned i;
5544 	char buf[PATH_MAX + 1];
5545 	const char *opts;
5546 	long result;
5547 #ifndef MOZ_MEMORY_WINDOWS
5548 	int linklen;
5549 #endif
5550 
5551 #ifndef MOZ_MEMORY_WINDOWS
5552 	malloc_mutex_lock(&init_lock);
5553 #endif
5554 
5555 	if (malloc_initialized) {
5556 		/*
5557 		 * Another thread initialized the allocator before this one
5558 		 * acquired init_lock.
5559 		 */
5560 #ifndef MOZ_MEMORY_WINDOWS
5561 		malloc_mutex_unlock(&init_lock);
5562 #endif
5563 		return (false);
5564 	}
5565 
5566 #ifdef MOZ_MEMORY_WINDOWS
5567 	/* get a thread local storage index */
5568 	tlsIndex = TlsAlloc();
5569 #endif
5570 
5571 	/* Get page size and number of CPUs */
5572 #ifdef MOZ_MEMORY_WINDOWS
5573 	{
5574 		SYSTEM_INFO info;
5575 
5576 		GetSystemInfo(&info);
5577 		result = info.dwPageSize;
5578 
5579 		pagesize = (unsigned) result;
5580 
5581 		ncpus = info.dwNumberOfProcessors;
5582 	}
5583 #else
5584 	ncpus = malloc_ncpus();
5585 
5586 	result = sysconf(_SC_PAGESIZE);
5587 	assert(result != -1);
5588 
5589 	pagesize = (unsigned) result;
5590 #endif
5591 
5592 	/*
5593 	 * We assume that pagesize is a power of 2 when calculating
5594 	 * pagesize_mask and pagesize_2pow.
5595 	 */
5596 	assert(((result - 1) & result) == 0);
5597 	pagesize_mask = result - 1;
5598 	pagesize_2pow = ffs((int)result) - 1;
5599 
5600 #ifdef MALLOC_PAGEFILE
5601 	/*
5602 	 * Determine where to create page files.  It is insufficient to
5603 	 * unconditionally use P_tmpdir (typically "/tmp"), since for some
5604 	 * operating systems /tmp is a separate filesystem that is rather small.
5605 	 * Therefore prefer, in order, the following locations:
5606 	 *
5607 	 * 1) MALLOC_TMPDIR
5608 	 * 2) TMPDIR
5609 	 * 3) P_tmpdir
5610 	 */
5611 	{
5612 		char *s;
5613 		size_t slen;
5614 		static const char suffix[] = "/jemalloc.XXXXXX";
5615 
5616 		if ((s = getenv("MALLOC_TMPDIR")) == NULL && (s =
5617 		    getenv("TMPDIR")) == NULL)
5618 			s = P_tmpdir;
5619 		slen = strlen(s);
5620 		if (slen + sizeof(suffix) > sizeof(pagefile_templ)) {
5621 			_malloc_message(_getprogname(),
5622 			    ": (malloc) Page file path too long\n",
5623 			    "", "");
5624 			abort();
5625 		}
5626 		memcpy(pagefile_templ, s, slen);
5627 		memcpy(&pagefile_templ[slen], suffix, sizeof(suffix));
5628 	}
5629 #endif
5630 
5631 	for (i = 0; i < 3; i++) {
5632 		unsigned j;
5633 
5634 		/* Get runtime configuration. */
5635 		switch (i) {
5636 		case 0:
5637 #ifndef MOZ_MEMORY_WINDOWS
5638 			if ((linklen = readlink("/etc/malloc.conf", buf,
5639 						sizeof(buf) - 1)) != -1) {
5640 				/*
5641 				 * Use the contents of the "/etc/malloc.conf"
5642 				 * symbolic link's name.
5643 				 */
5644 				buf[linklen] = '\0';
5645 				opts = buf;
5646 			} else
5647 #endif
5648 			{
5649 				/* No configuration specified. */
5650 				buf[0] = '\0';
5651 				opts = buf;
5652 			}
5653 			break;
5654 		case 1:
5655 			if (issetugid() == 0 && (opts =
5656 			    getenv("MALLOC_OPTIONS")) != NULL) {
5657 				/*
5658 				 * Do nothing; opts is already initialized to
5659 				 * the value of the MALLOC_OPTIONS environment
5660 				 * variable.
5661 				 */
5662 			} else {
5663 				/* No configuration specified. */
5664 				buf[0] = '\0';
5665 				opts = buf;
5666 			}
5667 			break;
5668 		case 2:
5669 			if (_malloc_options != NULL) {
5670 				/*
5671 				 * Use options that were compiled into the
5672 				 * program.
5673 				 */
5674 				opts = _malloc_options;
5675 			} else {
5676 				/* No configuration specified. */
5677 				buf[0] = '\0';
5678 				opts = buf;
5679 			}
5680 			break;
5681 		default:
5682 			/* NOTREACHED */
5683 			buf[0] = '\0';
5684 			opts = buf;
5685 			assert(false);
5686 		}
5687 
5688 		for (j = 0; opts[j] != '\0'; j++) {
5689 			unsigned k, nreps;
5690 			bool nseen;
5691 
5692 			/* Parse repetition count, if any. */
5693 			for (nreps = 0, nseen = false;; j++, nseen = true) {
5694 				switch (opts[j]) {
5695 					case '0': case '1': case '2': case '3':
5696 					case '4': case '5': case '6': case '7':
5697 					case '8': case '9':
5698 						nreps *= 10;
5699 						nreps += opts[j] - '0';
5700 						break;
5701 					default:
5702 						goto MALLOC_OUT;
5703 				}
5704 			}
5705 MALLOC_OUT:
5706 			if (nseen == false)
5707 				nreps = 1;
5708 
5709 			for (k = 0; k < nreps; k++) {
5710 				switch (opts[j]) {
5711 				case 'a':
5712 					opt_abort = false;
5713 					break;
5714 				case 'A':
5715 					opt_abort = true;
5716 					break;
5717 				case 'b':
5718 #ifdef MALLOC_BALANCE
5719 					opt_balance_threshold >>= 1;
5720 #endif
5721 					break;
5722 				case 'B':
5723 #ifdef MALLOC_BALANCE
5724 					if (opt_balance_threshold == 0)
5725 						opt_balance_threshold = 1;
5726 					else if ((opt_balance_threshold << 1)
5727 					    > opt_balance_threshold)
5728 						opt_balance_threshold <<= 1;
5729 #endif
5730 					break;
5731 				case 'f':
5732 					opt_dirty_max >>= 1;
5733 					break;
5734 				case 'F':
5735 					if (opt_dirty_max == 0)
5736 						opt_dirty_max = 1;
5737 					else if ((opt_dirty_max << 1) != 0)
5738 						opt_dirty_max <<= 1;
5739 					break;
5740 				case 'g':
5741 					opt_reserve_range_lshift--;
5742 					break;
5743 				case 'G':
5744 					opt_reserve_range_lshift++;
5745 					break;
5746 #ifdef MALLOC_FILL
5747 				case 'j':
5748 					opt_junk = false;
5749 					break;
5750 				case 'J':
5751 					opt_junk = true;
5752 					break;
5753 #endif
5754 				case 'k':
5755 					/*
5756 					 * Chunks always require at least one
5757 					 * header page, so chunks can never be
5758 					 * smaller than two pages.
5759 					 */
5760 					if (opt_chunk_2pow > pagesize_2pow + 1)
5761 						opt_chunk_2pow--;
5762 					break;
5763 				case 'K':
5764 					if (opt_chunk_2pow + 1 <
5765 					    (sizeof(size_t) << 3))
5766 						opt_chunk_2pow++;
5767 					break;
5768 				case 'n':
5769 					opt_narenas_lshift--;
5770 					break;
5771 				case 'N':
5772 					opt_narenas_lshift++;
5773 					break;
5774 #ifdef MALLOC_PAGEFILE
5775 				case 'o':
5776 					/* Do not over-commit. */
5777 					opt_pagefile = true;
5778 					break;
5779 				case 'O':
5780 					/* Allow over-commit. */
5781 					opt_pagefile = false;
5782 					break;
5783 #endif
5784 				case 'p':
5785 					opt_print_stats = false;
5786 					break;
5787 				case 'P':
5788 					opt_print_stats = true;
5789 					break;
5790 				case 'q':
5791 					if (opt_quantum_2pow > QUANTUM_2POW_MIN)
5792 						opt_quantum_2pow--;
5793 					break;
5794 				case 'Q':
5795 					if (opt_quantum_2pow < pagesize_2pow -
5796 					    1)
5797 						opt_quantum_2pow++;
5798 					break;
5799 				case 'r':
5800 					opt_reserve_min_lshift--;
5801 					break;
5802 				case 'R':
5803 					opt_reserve_min_lshift++;
5804 					break;
5805 				case 's':
5806 					if (opt_small_max_2pow >
5807 					    QUANTUM_2POW_MIN)
5808 						opt_small_max_2pow--;
5809 					break;
5810 				case 'S':
5811 					if (opt_small_max_2pow < pagesize_2pow
5812 					    - 1)
5813 						opt_small_max_2pow++;
5814 					break;
5815 #ifdef MALLOC_UTRACE
5816 				case 'u':
5817 					opt_utrace = false;
5818 					break;
5819 				case 'U':
5820 					opt_utrace = true;
5821 					break;
5822 #endif
5823 #ifdef MALLOC_SYSV
5824 				case 'v':
5825 					opt_sysv = false;
5826 					break;
5827 				case 'V':
5828 					opt_sysv = true;
5829 					break;
5830 #endif
5831 #ifdef MALLOC_XMALLOC
5832 				case 'x':
5833 					opt_xmalloc = false;
5834 					break;
5835 				case 'X':
5836 					opt_xmalloc = true;
5837 					break;
5838 #endif
5839 #ifdef MALLOC_FILL
5840 				case 'z':
5841 					opt_zero = false;
5842 					break;
5843 				case 'Z':
5844 					opt_zero = true;
5845 					break;
5846 #endif
5847 				default: {
5848 					char cbuf[2];
5849 
5850 					cbuf[0] = opts[j];
5851 					cbuf[1] = '\0';
5852 					_malloc_message(_getprogname(),
5853 					    ": (malloc) Unsupported character "
5854 					    "in malloc options: '", cbuf,
5855 					    "'\n");
5856 				}
5857 				}
5858 			}
5859 		}
5860 	}
5861 
5862 	/* Take care to call atexit() only once. */
5863 	if (opt_print_stats) {
5864 #ifndef MOZ_MEMORY_WINDOWS
5865 		/* Print statistics at exit. */
5866 		atexit(malloc_print_stats);
5867 #endif
5868 	}
5869 
5870 #if (!defined(MOZ_MEMORY_WINDOWS) && !defined(MOZ_MEMORY_DARWIN))
5871 	/* Prevent potential deadlock on malloc locks after fork. */
5872 	pthread_atfork(_malloc_prefork, _malloc_postfork, _malloc_postfork);
5873 #endif
5874 
5875 	/* Set variables according to the value of opt_small_max_2pow. */
5876 	if (opt_small_max_2pow < opt_quantum_2pow)
5877 		opt_small_max_2pow = opt_quantum_2pow;
5878 	small_max = ((size_t)1 << opt_small_max_2pow);
5879 
5880 	/* Set bin-related variables. */
5881 	bin_maxclass = (pagesize >> 1);
5882 	assert(opt_quantum_2pow >= TINY_MIN_2POW);
5883 	ntbins = opt_quantum_2pow - TINY_MIN_2POW;
5884 	assert(ntbins <= opt_quantum_2pow);
5885 	nqbins = (small_max >> opt_quantum_2pow);
5886 	nsbins = pagesize_2pow - opt_small_max_2pow - 1;
5887 
5888 	/* Set variables according to the value of opt_quantum_2pow. */
5889 	quantum = ((size_t)1 << opt_quantum_2pow);
5890 	quantum_mask = quantum - 1;
5891 	if (ntbins > 0)
5892 		small_min = (quantum >> 1) + 1;
5893 	else
5894 		small_min = 1;
5895 	assert(small_min <= quantum);
5896 
5897 	/* Set variables according to the value of opt_chunk_2pow. */
5898 	chunksize = ((size_t)1 << opt_chunk_2pow);
5899 	chunksize_mask = chunksize - 1;
5900 	chunk_npages = (chunksize >> pagesize_2pow);
5901 	{
5902 		size_t header_size;
5903 
5904 		/*
5905 		 * Compute the header size such that it is large
5906 		 * enough to contain the page map and enough nodes for the
5907 		 * worst case: one node per non-header page plus one extra for
5908 		 * situations where we briefly have one more node allocated
5909 		 * than we will need.
5910 		 */
5911 		header_size = sizeof(arena_chunk_t) +
5912 		    (sizeof(arena_chunk_map_t) * (chunk_npages - 1));
5913 		arena_chunk_header_npages = (header_size >> pagesize_2pow) +
5914 		    ((header_size & pagesize_mask) != 0);
5915 	}
5916 	arena_maxclass = chunksize - (arena_chunk_header_npages <<
5917 	    pagesize_2pow);
5918 
5919 #ifdef JEMALLOC_USES_MAP_ALIGN
5920 	/*
5921 	 * When using MAP_ALIGN, the alignment parameter must be a power of two
5922 	 * multiple of the system pagesize, or mmap will fail.
5923 	 */
5924 	assert((chunksize % pagesize) == 0);
5925 	assert((1 << (ffs(chunksize / pagesize) - 1)) == (chunksize/pagesize));
5926 #endif
5927 
5928 	UTRACE(0, 0, 0);
5929 
5930 #ifdef MALLOC_STATS
5931 	memset(&stats_chunks, 0, sizeof(chunk_stats_t));
5932 #endif
5933 
5934 	/* Various sanity checks that regard configuration. */
5935 	assert(quantum >= sizeof(void *));
5936 	assert(quantum <= pagesize);
5937 	assert(chunksize >= pagesize);
5938 	assert(quantum * 4 <= chunksize);
5939 
5940 	/* Initialize chunks data. */
5941 	malloc_mutex_init(&huge_mtx);
5942 	extent_tree_ad_new(&huge);
5943 #ifdef MALLOC_STATS
5944 	huge_nmalloc = 0;
5945 	huge_ndalloc = 0;
5946 	huge_allocated = 0;
5947 #endif
5948 
5949 	/* Initialize base allocation data structures. */
5950 #ifdef MALLOC_STATS
5951 	base_mapped = 0;
5952 #endif
5953 	base_nodes = NULL;
5954 	base_reserve_regs = NULL;
5955 	malloc_mutex_init(&base_mtx);
5956 
5957 #ifdef MOZ_MEMORY_NARENAS_DEFAULT_ONE
5958 	narenas = 1;
5959 #else
5960 	if (ncpus > 1) {
5961 		/*
5962 		 * For SMP systems, create four times as many arenas as there
5963 		 * are CPUs by default.
5964 		 */
5965 		opt_narenas_lshift += 2;
5966 	}
5967 
5968 	/* Determine how many arenas to use. */
5969 	narenas = ncpus;
5970 #endif
5971 	if (opt_narenas_lshift > 0) {
5972 		if ((narenas << opt_narenas_lshift) > narenas)
5973 			narenas <<= opt_narenas_lshift;
5974 		/*
5975 		 * Make sure not to exceed the limits of what base_alloc() can
5976 		 * handle.
5977 		 */
5978 		if (narenas * sizeof(arena_t *) > chunksize)
5979 			narenas = chunksize / sizeof(arena_t *);
5980 	} else if (opt_narenas_lshift < 0) {
5981 		if ((narenas >> -opt_narenas_lshift) < narenas)
5982 			narenas >>= -opt_narenas_lshift;
5983 		/* Make sure there is at least one arena. */
5984 		if (narenas == 0)
5985 			narenas = 1;
5986 	}
5987 #ifdef MALLOC_BALANCE
5988 	assert(narenas != 0);
5989 	for (narenas_2pow = 0;
5990 	     (narenas >> (narenas_2pow + 1)) != 0;
5991 	     narenas_2pow++);
5992 #endif
5993 
5994 #ifdef NO_TLS
5995 	if (narenas > 1) {
5996 		static const unsigned primes[] = {1, 3, 5, 7, 11, 13, 17, 19,
5997 		    23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
5998 		    89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149,
5999 		    151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211,
6000 		    223, 227, 229, 233, 239, 241, 251, 257, 263};
6001 		unsigned nprimes, parenas;
6002 
6003 		/*
6004 		 * Pick a prime number of hash arenas that is more than narenas
6005 		 * so that direct hashing of pthread_self() pointers tends to
6006 		 * spread allocations evenly among the arenas.
6007 		 */
6008 		assert((narenas & 1) == 0); /* narenas must be even. */
6009 		nprimes = (sizeof(primes) >> SIZEOF_INT_2POW);
6010 		parenas = primes[nprimes - 1]; /* In case not enough primes. */
6011 		for (i = 1; i < nprimes; i++) {
6012 			if (primes[i] > narenas) {
6013 				parenas = primes[i];
6014 				break;
6015 			}
6016 		}
6017 		narenas = parenas;
6018 	}
6019 #endif
6020 
6021 #ifndef NO_TLS
6022 #  ifndef MALLOC_BALANCE
6023 	next_arena = 0;
6024 #  endif
6025 #endif
6026 
6027 	/* Allocate and initialize arenas. */
6028 	arenas = (arena_t **)base_alloc(sizeof(arena_t *) * narenas);
6029 	if (arenas == NULL) {
6030 #ifndef MOZ_MEMORY_WINDOWS
6031 		malloc_mutex_unlock(&init_lock);
6032 #endif
6033 		return (true);
6034 	}
6035 	/*
6036 	 * Zero the array.  In practice, this should always be pre-zeroed,
6037 	 * since it was just mmap()ed, but let's be sure.
6038 	 */
6039 	memset(arenas, 0, sizeof(arena_t *) * narenas);
6040 
6041 	/*
6042 	 * Initialize one arena here.  The rest are lazily created in
6043 	 * choose_arena_hard().
6044 	 */
6045 	arenas_extend(0);
6046 	if (arenas[0] == NULL) {
6047 #ifndef MOZ_MEMORY_WINDOWS
6048 		malloc_mutex_unlock(&init_lock);
6049 #endif
6050 		return (true);
6051 	}
6052 #ifndef NO_TLS
6053 	/*
6054 	 * Assign the initial arena to the initial thread, in order to avoid
6055 	 * spurious creation of an extra arena if the application switches to
6056 	 * threaded mode.
6057 	 */
6058 #ifdef MOZ_MEMORY_WINDOWS
6059 	TlsSetValue(tlsIndex, arenas[0]);
6060 #else
6061 	arenas_map = arenas[0];
6062 #endif
6063 #endif
6064 
6065 	/*
6066 	 * Seed here for the initial thread, since choose_arena_hard() is only
6067 	 * called for other threads.  The seed value doesn't really matter.
6068 	 */
6069 #ifdef MALLOC_BALANCE
6070 	SPRN(balance, 42);
6071 #endif
6072 
6073 	malloc_spin_init(&arenas_lock);
6074 
6075 #ifdef MALLOC_VALIDATE
6076 	chunk_rtree = malloc_rtree_new((SIZEOF_PTR << 3) - opt_chunk_2pow);
6077 	if (chunk_rtree == NULL)
6078 		return (true);
6079 #endif
6080 
6081 	/*
6082 	 * Configure and initialize the memory reserve.  This needs to happen
6083 	 * late during initialization, since chunks are allocated.
6084 	 */
6085 	malloc_mutex_init(&reserve_mtx);
6086 	reserve_min = 0;
6087 	reserve_cur = 0;
6088 	reserve_max = 0;
6089 	if (RESERVE_RANGE_2POW_DEFAULT + opt_reserve_range_lshift >= 0) {
6090 		reserve_max += chunksize << (RESERVE_RANGE_2POW_DEFAULT +
6091 		    opt_reserve_range_lshift);
6092 	}
6093 	ql_new(&reserve_regs);
6094 	reserve_seq = 0;
6095 	extent_tree_szad_new(&reserve_chunks_szad);
6096 	extent_tree_ad_new(&reserve_chunks_ad);
6097 	if (RESERVE_MIN_2POW_DEFAULT + opt_reserve_min_lshift >= 0) {
6098 		reserve_min_set(chunksize << (RESERVE_MIN_2POW_DEFAULT +
6099 		    opt_reserve_min_lshift));
6100 	}
6101 
6102 	malloc_initialized = true;
6103 #ifndef MOZ_MEMORY_WINDOWS
6104 	malloc_mutex_unlock(&init_lock);
6105 #endif
6106 	return (false);
6107 }
6108 
6109 /* XXX Why not just expose malloc_print_stats()? */
6110 #ifdef MOZ_MEMORY_WINDOWS
6111 void
6112 malloc_shutdown()
6113 {
6114 
6115 	malloc_print_stats();
6116 }
6117 #endif
6118 
6119 /*
6120  * End general internal functions.
6121  */
6122 /******************************************************************************/
6123 /*
6124  * Begin malloc(3)-compatible functions.
6125  */
6126 
6127 /*
6128  * Inline the standard malloc functions if they are being subsumed by Darwin's
6129  * zone infrastructure.
6130  */
6131 #ifdef MOZ_MEMORY_DARWIN
6132 #  define ZONE_INLINE	inline
6133 #else
6134 #  define ZONE_INLINE
6135 #endif
6136 
6137 /* Mangle standard interfaces on Darwin and Windows CE,
6138    in order to avoid linking problems. */
6139 #ifdef MOZ_MEMORY_DARWIN
6140 #define DONT_OVERRIDE_LIBC
6141 #endif
6142 
6143 #if defined(DONT_OVERRIDE_LIBC)
6144 #define	malloc(a)	je_malloc(a)
6145 #define	valloc(a)	je_valloc(a)
6146 #define	calloc(a, b)	je_calloc(a, b)
6147 #define	realloc(a, b)	je_realloc(a, b)
6148 #define	free(a)		je_free(a)
6149 #define _msize(p) je_msize(p)
6150 #define _recalloc(p, n, s) je_recalloc(p, n, s)
6151 #define memalign(a, s) je_memalign(a, s)
6152 #endif
6153 
6154 ZONE_INLINE
6155 void *
6156 malloc(size_t size)
6157 {
6158 	void *ret;
6159 
6160 	if (malloc_init()) {
6161 		ret = NULL;
6162 		goto RETURN;
6163 	}
6164 
6165 	if (size == 0) {
6166 #ifdef MALLOC_SYSV
6167 		if (opt_sysv == false)
6168 #endif
6169 			size = 1;
6170 #ifdef MALLOC_SYSV
6171 		else {
6172 			ret = NULL;
6173 			goto RETURN;
6174 		}
6175 #endif
6176 	}
6177 
6178 	ret = imalloc(size);
6179 
6180 RETURN:
6181 	if (ret == NULL) {
6182 #ifdef MALLOC_XMALLOC
6183 		if (opt_xmalloc) {
6184 			_malloc_message(_getprogname(),
6185 			    ": (malloc) Error in malloc(): out of memory\n", "",
6186 			    "");
6187 			abort();
6188 		}
6189 #endif
6190 		errno = ENOMEM;
6191 	}
6192 
6193 	UTRACE(0, size, ret);
6194 	return (ret);
6195 }
6196 
6197 #ifdef MOZ_MEMORY_SOLARIS
6198 #  ifdef __SUNPRO_C
6199 void *
6200 memalign(size_t alignment, size_t size);
6201 #pragma no_inline(memalign)
6202 #  elif (defined(__GNU_C__))
6203 __attribute__((noinline))
6204 #  endif
6205 #else
6206 inline
6207 #endif
6208 void *
6209 memalign(size_t alignment, size_t size)
6210 {
6211 	void *ret;
6212 
6213 	assert(((alignment - 1) & alignment) == 0 && alignment >=
6214 	    sizeof(void *));
6215 
6216 	if (malloc_init()) {
6217 		ret = NULL;
6218 		goto RETURN;
6219 	}
6220 
6221 	ret = ipalloc(alignment, size);
6222 
6223 RETURN:
6224 #ifdef MALLOC_XMALLOC
6225 	if (opt_xmalloc && ret == NULL) {
6226 		_malloc_message(_getprogname(),
6227 		": (malloc) Error in memalign(): out of memory\n", "", "");
6228 		abort();
6229 	}
6230 #endif
6231 	UTRACE(0, size, ret);
6232 	return (ret);
6233 }
6234 
6235 ZONE_INLINE
6236 int
6237 posix_memalign(void **memptr, size_t alignment, size_t size)
6238 {
6239 	void *result;
6240 
6241 	/* Make sure that alignment is a large enough power of 2. */
6242 	if (((alignment - 1) & alignment) != 0 || alignment < sizeof(void *)) {
6243 #ifdef MALLOC_XMALLOC
6244 		if (opt_xmalloc) {
6245 			_malloc_message(_getprogname(),
6246 			    ": (malloc) Error in posix_memalign(): "
6247 			    "invalid alignment\n", "", "");
6248 			abort();
6249 		}
6250 #endif
6251 		return (EINVAL);
6252 	}
6253 
6254 #ifdef MOZ_MEMORY_DARWIN
6255 	result = moz_memalign(alignment, size);
6256 #else
6257 	result = memalign(alignment, size);
6258 #endif
6259 	if (result == NULL)
6260 		return (ENOMEM);
6261 
6262 	*memptr = result;
6263 	return (0);
6264 }
6265 
6266 ZONE_INLINE
6267 void *
6268 valloc(size_t size)
6269 {
6270 #ifdef MOZ_MEMORY_DARWIN
6271 	return (moz_memalign(pagesize, size));
6272 #else
6273 	return (memalign(pagesize, size));
6274 #endif
6275 }
6276 
6277 ZONE_INLINE
6278 void *
6279 calloc(size_t num, size_t size)
6280 {
6281 	void *ret;
6282 	size_t num_size;
6283 
6284 	if (malloc_init()) {
6285 		num_size = 0;
6286 		ret = NULL;
6287 		goto RETURN;
6288 	}
6289 
6290 	num_size = num * size;
6291 	if (num_size == 0) {
6292 #ifdef MALLOC_SYSV
6293 		if ((opt_sysv == false) && ((num == 0) || (size == 0)))
6294 #endif
6295 			num_size = 1;
6296 #ifdef MALLOC_SYSV
6297 		else {
6298 			ret = NULL;
6299 			goto RETURN;
6300 		}
6301 #endif
6302 	/*
6303 	 * Try to avoid division here.  We know that it isn't possible to
6304 	 * overflow during multiplication if neither operand uses any of the
6305 	 * most significant half of the bits in a size_t.
6306 	 */
6307 	} else if (((num | size) & (SIZE_T_MAX << (sizeof(size_t) << 2)))
6308 	    && (num_size / size != num)) {
6309 		/* size_t overflow. */
6310 		ret = NULL;
6311 		goto RETURN;
6312 	}
6313 
6314 	ret = icalloc(num_size);
6315 
6316 RETURN:
6317 	if (ret == NULL) {
6318 #ifdef MALLOC_XMALLOC
6319 		if (opt_xmalloc) {
6320 			_malloc_message(_getprogname(),
6321 			    ": (malloc) Error in calloc(): out of memory\n", "",
6322 			    "");
6323 			abort();
6324 		}
6325 #endif
6326 		errno = ENOMEM;
6327 	}
6328 
6329 	UTRACE(0, num_size, ret);
6330 	return (ret);
6331 }
6332 
6333 ZONE_INLINE
6334 void *
6335 realloc(void *ptr, size_t size)
6336 {
6337 	void *ret;
6338 
6339 	if (size == 0) {
6340 #ifdef MALLOC_SYSV
6341 		if (opt_sysv == false)
6342 #endif
6343 			size = 1;
6344 #ifdef MALLOC_SYSV
6345 		else {
6346 			if (ptr != NULL)
6347 				idalloc(ptr);
6348 			ret = NULL;
6349 			goto RETURN;
6350 		}
6351 #endif
6352 	}
6353 
6354 	if (ptr != NULL) {
6355 		assert(malloc_initialized);
6356 
6357 		ret = iralloc(ptr, size);
6358 
6359 		if (ret == NULL) {
6360 #ifdef MALLOC_XMALLOC
6361 			if (opt_xmalloc) {
6362 				_malloc_message(_getprogname(),
6363 				    ": (malloc) Error in realloc(): out of "
6364 				    "memory\n", "", "");
6365 				abort();
6366 			}
6367 #endif
6368 			errno = ENOMEM;
6369 		}
6370 	} else {
6371 		if (malloc_init())
6372 			ret = NULL;
6373 		else
6374 			ret = imalloc(size);
6375 
6376 		if (ret == NULL) {
6377 #ifdef MALLOC_XMALLOC
6378 			if (opt_xmalloc) {
6379 				_malloc_message(_getprogname(),
6380 				    ": (malloc) Error in realloc(): out of "
6381 				    "memory\n", "", "");
6382 				abort();
6383 			}
6384 #endif
6385 			errno = ENOMEM;
6386 		}
6387 	}
6388 
6389 #ifdef MALLOC_SYSV
6390 RETURN:
6391 #endif
6392 	UTRACE(ptr, size, ret);
6393 	return (ret);
6394 }
6395 
6396 ZONE_INLINE
6397 void
6398 free(void *ptr)
6399 {
6400 
6401 	UTRACE(ptr, 0, 0);
6402 	if (ptr != NULL) {
6403 		assert(malloc_initialized);
6404 
6405 		idalloc(ptr);
6406 	}
6407 }
6408 
6409 /*
6410  * End malloc(3)-compatible functions.
6411  */
6412 /******************************************************************************/
6413 /*
6414  * Begin non-standard functions.
6415  */
6416 
6417 size_t
6418 malloc_usable_size(const void *ptr)
6419 {
6420 
6421 #ifdef MALLOC_VALIDATE
6422 	return (isalloc_validate(ptr));
6423 #else
6424 	assert(ptr != NULL);
6425 
6426 	return (isalloc(ptr));
6427 #endif
6428 }
6429 
6430 void
6431 jemalloc_stats(jemalloc_stats_t *stats)
6432 {
6433 	size_t i;
6434 
6435 	assert(stats != NULL);
6436 
6437 	/*
6438 	 * Gather runtime settings.
6439 	 */
6440 	stats->opt_abort = opt_abort;
6441 	stats->opt_junk =
6442 #ifdef MALLOC_FILL
6443 	    opt_junk ? true :
6444 #endif
6445 	    false;
6446 	stats->opt_utrace =
6447 #ifdef MALLOC_UTRACE
6448 	    opt_utrace ? true :
6449 #endif
6450 	    false;
6451 	stats->opt_sysv =
6452 #ifdef MALLOC_SYSV
6453 	    opt_sysv ? true :
6454 #endif
6455 	    false;
6456 	stats->opt_xmalloc =
6457 #ifdef MALLOC_XMALLOC
6458 	    opt_xmalloc ? true :
6459 #endif
6460 	    false;
6461 	stats->opt_zero =
6462 #ifdef MALLOC_FILL
6463 	    opt_zero ? true :
6464 #endif
6465 	    false;
6466 	stats->narenas = narenas;
6467 	stats->balance_threshold =
6468 #ifdef MALLOC_BALANCE
6469 	    opt_balance_threshold
6470 #else
6471 	    SIZE_T_MAX
6472 #endif
6473 	    ;
6474 	stats->quantum = quantum;
6475 	stats->small_max = small_max;
6476 	stats->large_max = arena_maxclass;
6477 	stats->chunksize = chunksize;
6478 	stats->dirty_max = opt_dirty_max;
6479 
6480 	malloc_mutex_lock(&reserve_mtx);
6481 	stats->reserve_min = reserve_min;
6482 	stats->reserve_max = reserve_max;
6483 	stats->reserve_cur = reserve_cur;
6484 	malloc_mutex_unlock(&reserve_mtx);
6485 
6486 	/*
6487 	 * Gather current memory usage statistics.
6488 	 */
6489 	stats->mapped = 0;
6490 	stats->committed = 0;
6491 	stats->allocated = 0;
6492 	stats->dirty = 0;
6493 
6494 	/* Get huge mapped/allocated. */
6495 	malloc_mutex_lock(&huge_mtx);
6496 	stats->mapped += stats_chunks.curchunks * chunksize;
6497 #ifdef MALLOC_DECOMMIT
6498 	stats->committed += huge_allocated;
6499 #endif
6500 	stats->allocated += huge_allocated;
6501 	malloc_mutex_unlock(&huge_mtx);
6502 
6503 	/* Get base mapped. */
6504 	malloc_mutex_lock(&base_mtx);
6505 	stats->mapped += base_mapped;
6506 #ifdef MALLOC_DECOMMIT
6507 	stats->committed += base_mapped;
6508 #endif
6509 	malloc_mutex_unlock(&base_mtx);
6510 
6511 	/* Iterate over arenas and their chunks. */
6512 	for (i = 0; i < narenas; i++) {
6513 		arena_t *arena = arenas[i];
6514 		if (arena != NULL) {
6515 			arena_chunk_t *chunk;
6516 
6517 			malloc_spin_lock(&arena->lock);
6518 			stats->allocated += arena->stats.allocated_small;
6519 			stats->allocated += arena->stats.allocated_large;
6520 #ifdef MALLOC_DECOMMIT
6521 			rb_foreach_begin(arena_chunk_t, link_dirty,
6522 			    &arena->chunks_dirty, chunk) {
6523 				size_t j;
6524 
6525 				for (j = 0; j < chunk_npages; j++) {
6526 					if ((chunk->map[j].bits &
6527 					    CHUNK_MAP_DECOMMITTED) == 0)
6528 						stats->committed += pagesize;
6529 				}
6530 			} rb_foreach_end(arena_chunk_t, link_dirty,
6531 			    &arena->chunks_dirty, chunk)
6532 #endif
6533 			stats->dirty += (arena->ndirty << pagesize_2pow);
6534 			malloc_spin_unlock(&arena->lock);
6535 		}
6536 	}
6537 
6538 #ifndef MALLOC_DECOMMIT
6539 	stats->committed = stats->mapped;
6540 #endif
6541 }
6542 
6543 void *
6544 xmalloc(size_t size)
6545 {
6546 	void *ret;
6547 
6548 	if (malloc_init())
6549 		reserve_fail(size, "xmalloc");
6550 
6551 	if (size == 0) {
6552 #ifdef MALLOC_SYSV
6553 		if (opt_sysv == false)
6554 #endif
6555 			size = 1;
6556 #ifdef MALLOC_SYSV
6557 		else {
6558 			_malloc_message(_getprogname(),
6559 			    ": (malloc) Error in xmalloc(): ",
6560 			    "invalid size 0", "\n");
6561 			abort();
6562 		}
6563 #endif
6564 	}
6565 
6566 	ret = imalloc(size);
6567 	if (ret == NULL) {
6568 		uint64_t seq = 0;
6569 
6570 		do {
6571 			seq = reserve_crit(size, "xmalloc", seq);
6572 			ret = imalloc(size);
6573 		} while (ret == NULL);
6574 	}
6575 
6576 	UTRACE(0, size, ret);
6577 	return (ret);
6578 }
6579 
6580 void *
6581 xcalloc(size_t num, size_t size)
6582 {
6583 	void *ret;
6584 	size_t num_size;
6585 
6586 	num_size = num * size;
6587 	if (malloc_init())
6588 		reserve_fail(num_size, "xcalloc");
6589 
6590 	if (num_size == 0) {
6591 #ifdef MALLOC_SYSV
6592 		if ((opt_sysv == false) && ((num == 0) || (size == 0)))
6593 #endif
6594 			num_size = 1;
6595 #ifdef MALLOC_SYSV
6596 		else {
6597 			_malloc_message(_getprogname(),
6598 			    ": (malloc) Error in xcalloc(): ",
6599 			    "invalid size 0", "\n");
6600 			abort();
6601 		}
6602 #endif
6603 	/*
6604 	 * Try to avoid division here.  We know that it isn't possible to
6605 	 * overflow during multiplication if neither operand uses any of the
6606 	 * most significant half of the bits in a size_t.
6607 	 */
6608 	} else if (((num | size) & (SIZE_T_MAX << (sizeof(size_t) << 2)))
6609 	    && (num_size / size != num)) {
6610 		/* size_t overflow. */
6611 		_malloc_message(_getprogname(),
6612 		    ": (malloc) Error in xcalloc(): ",
6613 		    "size overflow", "\n");
6614 		abort();
6615 	}
6616 
6617 	ret = icalloc(num_size);
6618 	if (ret == NULL) {
6619 		uint64_t seq = 0;
6620 
6621 		do {
6622 			seq = reserve_crit(num_size, "xcalloc", seq);
6623 			ret = icalloc(num_size);
6624 		} while (ret == NULL);
6625 	}
6626 
6627 	UTRACE(0, num_size, ret);
6628 	return (ret);
6629 }
6630 
6631 void *
6632 xrealloc(void *ptr, size_t size)
6633 {
6634 	void *ret;
6635 
6636 	if (size == 0) {
6637 #ifdef MALLOC_SYSV
6638 		if (opt_sysv == false)
6639 #endif
6640 			size = 1;
6641 #ifdef MALLOC_SYSV
6642 		else {
6643 			if (ptr != NULL)
6644 				idalloc(ptr);
6645 			_malloc_message(_getprogname(),
6646 			    ": (malloc) Error in xrealloc(): ",
6647 			    "invalid size 0", "\n");
6648 			abort();
6649 		}
6650 #endif
6651 	}
6652 
6653 	if (ptr != NULL) {
6654 		assert(malloc_initialized);
6655 
6656 		ret = iralloc(ptr, size);
6657 		if (ret == NULL) {
6658 			uint64_t seq = 0;
6659 
6660 			do {
6661 				seq = reserve_crit(size, "xrealloc", seq);
6662 				ret = iralloc(ptr, size);
6663 			} while (ret == NULL);
6664 		}
6665 	} else {
6666 		if (malloc_init())
6667 			reserve_fail(size, "xrealloc");
6668 
6669 		ret = imalloc(size);
6670 		if (ret == NULL) {
6671 			uint64_t seq = 0;
6672 
6673 			do {
6674 				seq = reserve_crit(size, "xrealloc", seq);
6675 				ret = imalloc(size);
6676 			} while (ret == NULL);
6677 		}
6678 	}
6679 
6680 	UTRACE(ptr, size, ret);
6681 	return (ret);
6682 }
6683 
6684 void *
6685 xmemalign(size_t alignment, size_t size)
6686 {
6687 	void *ret;
6688 
6689 	assert(((alignment - 1) & alignment) == 0 && alignment >=
6690 	    sizeof(void *));
6691 
6692 	if (malloc_init())
6693 		reserve_fail(size, "xmemalign");
6694 
6695 	ret = ipalloc(alignment, size);
6696 	if (ret == NULL) {
6697 		uint64_t seq = 0;
6698 
6699 		do {
6700 			seq = reserve_crit(size, "xmemalign", seq);
6701 			ret = ipalloc(alignment, size);
6702 		} while (ret == NULL);
6703 	}
6704 
6705 	UTRACE(0, size, ret);
6706 	return (ret);
6707 }
6708 
6709 static void
6710 reserve_shrink(void)
6711 {
6712 	extent_node_t *node;
6713 
6714 	assert(reserve_cur > reserve_max);
6715 #ifdef MALLOC_DEBUG
6716 	{
6717 		extent_node_t *node;
6718 		size_t reserve_size;
6719 
6720 		reserve_size = 0;
6721 		rb_foreach_begin(extent_node_t, link_szad, &reserve_chunks_szad,
6722 		    node) {
6723 			reserve_size += node->size;
6724 		} rb_foreach_end(extent_node_t, link_szad, &reserve_chunks_szad,
6725 		    node)
6726 		assert(reserve_size == reserve_cur);
6727 
6728 		reserve_size = 0;
6729 		rb_foreach_begin(extent_node_t, link_ad, &reserve_chunks_ad,
6730 		    node) {
6731 			reserve_size += node->size;
6732 		} rb_foreach_end(extent_node_t, link_ad, &reserve_chunks_ad,
6733 		    node)
6734 		assert(reserve_size == reserve_cur);
6735 	}
6736 #endif
6737 
6738 	/* Discard chunks until the the reserve is below the size limit. */
6739 	rb_foreach_reverse_begin(extent_node_t, link_ad, &reserve_chunks_ad,
6740 	    node) {
6741 #ifndef MALLOC_DECOMMIT
6742 		if (node->size <= reserve_cur - reserve_max) {
6743 #endif
6744 			extent_node_t *tnode = extent_tree_ad_prev(
6745 			    &reserve_chunks_ad, node);
6746 
6747 #ifdef MALLOC_DECOMMIT
6748 			assert(node->size <= reserve_cur - reserve_max);
6749 #endif
6750 
6751 			/* Discard the entire [multi-]chunk. */
6752 			extent_tree_szad_remove(&reserve_chunks_szad, node);
6753 			extent_tree_ad_remove(&reserve_chunks_ad, node);
6754 			reserve_cur -= node->size;
6755 			pages_unmap(node->addr, node->size);
6756 #ifdef MALLOC_STATS
6757 			stats_chunks.curchunks -= (node->size / chunksize);
6758 #endif
6759 			base_node_dealloc(node);
6760 			if (reserve_cur == reserve_max)
6761 				break;
6762 
6763 			rb_foreach_reverse_prev(extent_node_t, link_ad,
6764 			    extent_ad_comp, &reserve_chunks_ad, tnode);
6765 #ifndef MALLOC_DECOMMIT
6766 		} else {
6767 			/* Discard the end of the multi-chunk. */
6768 			extent_tree_szad_remove(&reserve_chunks_szad, node);
6769 			node->size -= reserve_cur - reserve_max;
6770 			extent_tree_szad_insert(&reserve_chunks_szad, node);
6771 			pages_unmap((void *)((uintptr_t)node->addr +
6772 			    node->size), reserve_cur - reserve_max);
6773 #ifdef MALLOC_STATS
6774 			stats_chunks.curchunks -= ((reserve_cur - reserve_max) /
6775 			    chunksize);
6776 #endif
6777 			reserve_cur = reserve_max;
6778 			break;
6779 		}
6780 #endif
6781 		assert(reserve_cur > reserve_max);
6782 	} rb_foreach_reverse_end(extent_node_t, link_ad, &reserve_chunks_ad,
6783 	    node)
6784 }
6785 
6786 /* Send a condition notification. */
6787 static uint64_t
6788 reserve_notify(reserve_cnd_t cnd, size_t size, uint64_t seq)
6789 {
6790 	reserve_reg_t *reg;
6791 
6792 	/* seq is used to keep track of distinct condition-causing events. */
6793 	if (seq == 0) {
6794 		/* Allocate new sequence number. */
6795 		reserve_seq++;
6796 		seq = reserve_seq;
6797 	}
6798 
6799 	/*
6800 	 * Advance to the next callback registration and send a notification,
6801 	 * unless one has already been sent for this condition-causing event.
6802 	 */
6803 	reg = ql_first(&reserve_regs);
6804 	if (reg == NULL)
6805 		return (0);
6806 	ql_first(&reserve_regs) = ql_next(&reserve_regs, reg, link);
6807 	if (reg->seq == seq)
6808 		return (0);
6809 	reg->seq = seq;
6810 	malloc_mutex_unlock(&reserve_mtx);
6811 	reg->cb(reg->ctx, cnd, size);
6812 	malloc_mutex_lock(&reserve_mtx);
6813 
6814 	return (seq);
6815 }
6816 
6817 /* Allocation failure due to OOM.  Try to free some memory via callbacks. */
6818 static uint64_t
6819 reserve_crit(size_t size, const char *fname, uint64_t seq)
6820 {
6821 
6822 	/*
6823 	 * Send one condition notification.  Iteration is handled by the
6824 	 * caller of this function.
6825 	 */
6826 	malloc_mutex_lock(&reserve_mtx);
6827 	seq = reserve_notify(RESERVE_CND_CRIT, size, seq);
6828 	malloc_mutex_unlock(&reserve_mtx);
6829 
6830 	/* If no notification could be sent, then no further recourse exists. */
6831 	if (seq == 0)
6832 		reserve_fail(size, fname);
6833 
6834 	return (seq);
6835 }
6836 
6837 /* Permanent allocation failure due to OOM. */
6838 static void
6839 reserve_fail(size_t size, const char *fname)
6840 {
6841 	uint64_t seq = 0;
6842 
6843 	/* Send fail notifications. */
6844 	malloc_mutex_lock(&reserve_mtx);
6845 	do {
6846 		seq = reserve_notify(RESERVE_CND_FAIL, size, seq);
6847 	} while (seq != 0);
6848 	malloc_mutex_unlock(&reserve_mtx);
6849 
6850 	/* Terminate the application. */
6851 	_malloc_message(_getprogname(),
6852 	    ": (malloc) Error in ", fname, "(): out of memory\n");
6853 	abort();
6854 }
6855 
6856 bool
6857 reserve_cb_register(reserve_cb_t *cb, void *ctx)
6858 {
6859 	reserve_reg_t *reg = base_reserve_reg_alloc();
6860 	if (reg == NULL)
6861 		return (true);
6862 
6863 	ql_elm_new(reg, link);
6864 	reg->cb = cb;
6865 	reg->ctx = ctx;
6866 	reg->seq = 0;
6867 
6868 	malloc_mutex_lock(&reserve_mtx);
6869 	ql_head_insert(&reserve_regs, reg, link);
6870 	malloc_mutex_unlock(&reserve_mtx);
6871 
6872 	return (false);
6873 }
6874 
6875 bool
6876 reserve_cb_unregister(reserve_cb_t *cb, void *ctx)
6877 {
6878 	reserve_reg_t *reg = NULL;
6879 
6880 	malloc_mutex_lock(&reserve_mtx);
6881 	ql_foreach(reg, &reserve_regs, link) {
6882 		if (reg->cb == cb && reg->ctx == ctx) {
6883 			ql_remove(&reserve_regs, reg, link);
6884 			break;
6885 		}
6886 	}
6887 	malloc_mutex_unlock(&reserve_mtx);
6888 
6889 	if (reg != NULL)
6890 		base_reserve_reg_dealloc(reg);
6891 		return (false);
6892 	return (true);
6893 }
6894 
6895 size_t
6896 reserve_cur_get(void)
6897 {
6898 	size_t ret;
6899 
6900 	malloc_mutex_lock(&reserve_mtx);
6901 	ret = reserve_cur;
6902 	malloc_mutex_unlock(&reserve_mtx);
6903 
6904 	return (ret);
6905 }
6906 
6907 size_t
6908 reserve_min_get(void)
6909 {
6910 	size_t ret;
6911 
6912 	malloc_mutex_lock(&reserve_mtx);
6913 	ret = reserve_min;
6914 	malloc_mutex_unlock(&reserve_mtx);
6915 
6916 	return (ret);
6917 }
6918 
6919 bool
6920 reserve_min_set(size_t min)
6921 {
6922 
6923 	min = CHUNK_CEILING(min);
6924 
6925 	malloc_mutex_lock(&reserve_mtx);
6926 	/* Keep |reserve_max - reserve_min| the same. */
6927 	if (min < reserve_min) {
6928 		reserve_max -= reserve_min - min;
6929 		reserve_min = min;
6930 	} else {
6931 		/* Protect against wrap-around. */
6932 		if (reserve_max + min - reserve_min < reserve_max) {
6933 			reserve_min = SIZE_T_MAX - (reserve_max - reserve_min)
6934 			    - chunksize + 1;
6935 			reserve_max = SIZE_T_MAX - chunksize + 1;
6936 		} else {
6937 			reserve_max += min - reserve_min;
6938 			reserve_min = min;
6939 		}
6940 	}
6941 
6942 	/* Resize the reserve if necessary. */
6943 	if (reserve_cur < reserve_min) {
6944 		size_t size = reserve_min - reserve_cur;
6945 
6946 		/* Force the reserve to grow by allocating/deallocating. */
6947 		malloc_mutex_unlock(&reserve_mtx);
6948 #ifdef MALLOC_DECOMMIT
6949 		{
6950 			void **chunks;
6951 			size_t i, n;
6952 
6953 			n = size >> opt_chunk_2pow;
6954 			chunks = (void**)imalloc(n * sizeof(void *));
6955 			if (chunks == NULL)
6956 				return (true);
6957 			for (i = 0; i < n; i++) {
6958 				chunks[i] = huge_malloc(chunksize, false);
6959 				if (chunks[i] == NULL) {
6960 					size_t j;
6961 
6962 					for (j = 0; j < i; j++) {
6963 						huge_dalloc(chunks[j]);
6964 					}
6965 					idalloc(chunks);
6966 					return (true);
6967 				}
6968 			}
6969 			for (i = 0; i < n; i++)
6970 				huge_dalloc(chunks[i]);
6971 			idalloc(chunks);
6972 		}
6973 #else
6974 		{
6975 			void *x = huge_malloc(size, false);
6976 			if (x == NULL) {
6977 				return (true);
6978 			}
6979 			huge_dalloc(x);
6980 		}
6981 #endif
6982 	} else if (reserve_cur > reserve_max) {
6983 		reserve_shrink();
6984 		malloc_mutex_unlock(&reserve_mtx);
6985 	} else
6986 		malloc_mutex_unlock(&reserve_mtx);
6987 
6988 	return (false);
6989 }
6990 
6991 #ifdef MOZ_MEMORY_WINDOWS
6992 void*
6993 _recalloc(void *ptr, size_t count, size_t size)
6994 {
6995 	size_t oldsize = (ptr != NULL) ? isalloc(ptr) : 0;
6996 	size_t newsize = count * size;
6997 
6998 	/*
6999 	 * In order for all trailing bytes to be zeroed, the caller needs to
7000 	 * use calloc(), followed by recalloc().  However, the current calloc()
7001 	 * implementation only zeros the bytes requested, so if recalloc() is
7002 	 * to work 100% correctly, calloc() will need to change to zero
7003 	 * trailing bytes.
7004 	 */
7005 
7006 	ptr = realloc(ptr, newsize);
7007 	if (ptr != NULL && oldsize < newsize) {
7008 		memset((void *)((uintptr_t)ptr + oldsize), 0, newsize -
7009 		    oldsize);
7010 	}
7011 
7012 	return ptr;
7013 }
7014 
7015 /*
7016  * This impl of _expand doesn't ever actually expand or shrink blocks: it
7017  * simply replies that you may continue using a shrunk block.
7018  */
7019 void*
7020 _expand(void *ptr, size_t newsize)
7021 {
7022 	if (isalloc(ptr) >= newsize)
7023 		return ptr;
7024 
7025 	return NULL;
7026 }
7027 
7028 size_t
7029 _msize(const void *ptr)
7030 {
7031 	return malloc_usable_size(ptr);
7032 }
7033 #endif
7034 
7035 /*
7036  * End non-standard functions.
7037  */
7038 /******************************************************************************/
7039 /*
7040  * Begin library-private functions, used by threading libraries for protection
7041  * of malloc during fork().  These functions are only called if the program is
7042  * running in threaded mode, so there is no need to check whether the program
7043  * is threaded here.
7044  */
7045 
7046 void
7047 _malloc_prefork(void)
7048 {
7049 	unsigned i;
7050 
7051 	/* Acquire all mutexes in a safe order. */
7052 
7053 	malloc_spin_lock(&arenas_lock);
7054 	for (i = 0; i < narenas; i++) {
7055 		if (arenas[i] != NULL)
7056 			malloc_spin_lock(&arenas[i]->lock);
7057 	}
7058 	malloc_spin_unlock(&arenas_lock);
7059 
7060 	malloc_mutex_lock(&base_mtx);
7061 
7062 	malloc_mutex_lock(&huge_mtx);
7063 }
7064 
7065 void
7066 _malloc_postfork(void)
7067 {
7068 	unsigned i;
7069 
7070 	/* Release all mutexes, now that fork() has completed. */
7071 
7072 	malloc_mutex_unlock(&huge_mtx);
7073 
7074 	malloc_mutex_unlock(&base_mtx);
7075 
7076 	malloc_spin_lock(&arenas_lock);
7077 	for (i = 0; i < narenas; i++) {
7078 		if (arenas[i] != NULL)
7079 			malloc_spin_unlock(&arenas[i]->lock);
7080 	}
7081 	malloc_spin_unlock(&arenas_lock);
7082 }
7083 
7084 /*
7085  * End library-private functions.
7086  */
7087 /******************************************************************************/
7088 
7089 #ifdef HAVE_LIBDL
7090 #  include <dlfcn.h>
7091 #endif
7092 
7093 #ifdef MOZ_MEMORY_DARWIN
7094 static malloc_zone_t zone;
7095 static struct malloc_introspection_t zone_introspect;
7096 
7097 static size_t
7098 zone_size(malloc_zone_t *zone, void *ptr)
7099 {
7100 
7101 	/*
7102 	 * There appear to be places within Darwin (such as setenv(3)) that
7103 	 * cause calls to this function with pointers that *no* zone owns.  If
7104 	 * we knew that all pointers were owned by *some* zone, we could split
7105 	 * our zone into two parts, and use one as the default allocator and
7106 	 * the other as the default deallocator/reallocator.  Since that will
7107 	 * not work in practice, we must check all pointers to assure that they
7108 	 * reside within a mapped chunk before determining size.
7109 	 */
7110 	return (isalloc_validate(ptr));
7111 }
7112 
7113 static void *
7114 zone_malloc(malloc_zone_t *zone, size_t size)
7115 {
7116 
7117 	return (malloc(size));
7118 }
7119 
7120 static void *
7121 zone_calloc(malloc_zone_t *zone, size_t num, size_t size)
7122 {
7123 
7124 	return (calloc(num, size));
7125 }
7126 
7127 static void *
7128 zone_valloc(malloc_zone_t *zone, size_t size)
7129 {
7130 	void *ret = NULL; /* Assignment avoids useless compiler warning. */
7131 
7132 	posix_memalign(&ret, pagesize, size);
7133 
7134 	return (ret);
7135 }
7136 
7137 static void
7138 zone_free(malloc_zone_t *zone, void *ptr)
7139 {
7140 
7141 	free(ptr);
7142 }
7143 
7144 static void *
7145 zone_realloc(malloc_zone_t *zone, void *ptr, size_t size)
7146 {
7147 
7148 	return (realloc(ptr, size));
7149 }
7150 
7151 static void *
7152 zone_destroy(malloc_zone_t *zone)
7153 {
7154 
7155 	/* This function should never be called. */
7156 	assert(false);
7157 	return (NULL);
7158 }
7159 
7160 static size_t
7161 zone_good_size(malloc_zone_t *zone, size_t size)
7162 {
7163 	size_t ret;
7164 	void *p;
7165 
7166 	/*
7167 	 * Actually create an object of the appropriate size, then find out
7168 	 * how large it could have been without moving up to the next size
7169 	 * class.
7170 	 */
7171 	p = malloc(size);
7172 	if (p != NULL) {
7173 		ret = isalloc(p);
7174 		free(p);
7175 	} else
7176 		ret = size;
7177 
7178 	return (ret);
7179 }
7180 
7181 static void
7182 zone_force_lock(malloc_zone_t *zone)
7183 {
7184 
7185 	_malloc_prefork();
7186 }
7187 
7188 static void
7189 zone_force_unlock(malloc_zone_t *zone)
7190 {
7191 
7192 	_malloc_postfork();
7193 }
7194 
7195 static malloc_zone_t *
7196 create_zone(void)
7197 {
7198 
7199 	assert(malloc_initialized);
7200 
7201 	zone.size = (void *)zone_size;
7202 	zone.malloc = (void *)zone_malloc;
7203 	zone.calloc = (void *)zone_calloc;
7204 	zone.valloc = (void *)zone_valloc;
7205 	zone.free = (void *)zone_free;
7206 	zone.realloc = (void *)zone_realloc;
7207 	zone.destroy = (void *)zone_destroy;
7208 	zone.zone_name = "jemalloc_zone";
7209 	zone.batch_malloc = NULL;
7210 	zone.batch_free = NULL;
7211 	zone.introspect = &zone_introspect;
7212 
7213 	zone_introspect.enumerator = NULL;
7214 	zone_introspect.good_size = (void *)zone_good_size;
7215 	zone_introspect.check = NULL;
7216 	zone_introspect.print = NULL;
7217 	zone_introspect.log = NULL;
7218 	zone_introspect.force_lock = (void *)zone_force_lock;
7219 	zone_introspect.force_unlock = (void *)zone_force_unlock;
7220 	zone_introspect.statistics = NULL;
7221 
7222 	return (&zone);
7223 }
7224 
7225 __attribute__((constructor))
7226 void
7227 jemalloc_darwin_init(void)
7228 {
7229 	extern unsigned malloc_num_zones;
7230 	extern malloc_zone_t **malloc_zones;
7231 
7232 	if (malloc_init_hard())
7233 		abort();
7234 
7235 	/*
7236 	 * The following code is *not* thread-safe, so it's critical that
7237 	 * initialization be manually triggered.
7238 	 */
7239 
7240 	/* Register the custom zones. */
7241 	malloc_zone_register(create_zone());
7242 	assert(malloc_zones[malloc_num_zones - 1] == &zone);
7243 
7244 	/*
7245 	 * Shift malloc_zones around so that zone is first, which makes it the
7246 	 * default zone.
7247 	 */
7248 	assert(malloc_num_zones > 1);
7249 	memmove(&malloc_zones[1], &malloc_zones[0],
7250 		sizeof(malloc_zone_t *) * (malloc_num_zones - 1));
7251 	malloc_zones[0] = &zone;
7252 }
7253 
7254 #elif defined(__GLIBC__) && !defined(__UCLIBC__)
7255 /*
7256  * glibc provides the RTLD_DEEPBIND flag for dlopen which can make it possible
7257  * to inconsistently reference libc's malloc(3)-compatible functions
7258  * (bug 493541).
7259  *
7260  * These definitions interpose hooks in glibc.  The functions are actually
7261  * passed an extra argument for the caller return address, which will be
7262  * ignored.
7263  */
7264 void (*__free_hook)(void *ptr) = free;
7265 void *(*__malloc_hook)(size_t size) = malloc;
7266 void *(*__realloc_hook)(void *ptr, size_t size) = realloc;
7267 void *(*__memalign_hook)(size_t alignment, size_t size) = memalign;
7268 
7269 #elif defined(RTLD_DEEPBIND)
7270 /*
7271  * XXX On systems that support RTLD_GROUP or DF_1_GROUP, do their
7272  * implementations permit similar inconsistencies?  Should STV_SINGLETON
7273  * visibility be used for interposition where available?
7274  */
7275 #  error "Interposing malloc is unsafe on this system without libc malloc hooks."
7276 #endif
7277 
7278