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