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