branches/cparm/i386/libsa/jemalloc.c - Chameleon Svn Source Tree - Chameleon open source boot loader project.

Root/branches/cparm/i386/libsa/jemalloc.c

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

Download this file