| 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 | /******************************************************************************/ |
