1#define JEMALLOC_CHUNK_C_ 2#include "jemalloc/internal/jemalloc_internal.h" 3 4/******************************************************************************/ 5/* Data. */ 6 7const char *opt_dss = DSS_DEFAULT; 8size_t opt_lg_chunk = LG_CHUNK_DEFAULT; 9 10/* Used exclusively for gdump triggering. */ 11static size_t curchunks; 12static size_t highchunks; 13 14rtree_t chunks_rtree; 15 16/* Various chunk-related settings. */ 17size_t chunksize; 18size_t chunksize_mask; /* (chunksize - 1). */ 19size_t chunk_npages; 20 21/******************************************************************************/ 22 23bool 24chunk_register(const void *chunk, const extent_node_t *node) 25{ 26 27 assert(extent_node_addr_get(node) == chunk); 28 29 if (rtree_set(&chunks_rtree, (uintptr_t)chunk, node)) 30 return (true); 31 if (config_prof && opt_prof) { 32 size_t size = extent_node_size_get(node); 33 size_t nadd = (size == 0) ? 1 : size / chunksize; 34 size_t cur = atomic_add_z(&curchunks, nadd); 35 size_t high = atomic_read_z(&highchunks); 36 while (cur > high && atomic_cas_z(&highchunks, high, cur)) { 37 /* 38 * Don't refresh cur, because it may have decreased 39 * since this thread lost the highchunks update race. 40 */ 41 high = atomic_read_z(&highchunks); 42 } 43 if (cur > high && prof_gdump_get_unlocked()) 44 prof_gdump(); 45 } 46 47 return (false); 48} 49 50void 51chunk_deregister(const void *chunk, const extent_node_t *node) 52{ 53 bool err; 54 55 err = rtree_set(&chunks_rtree, (uintptr_t)chunk, NULL); 56 assert(!err); 57 if (config_prof && opt_prof) { 58 size_t size = extent_node_size_get(node); 59 size_t nsub = (size == 0) ? 1 : size / chunksize; 60 assert(atomic_read_z(&curchunks) >= nsub); 61 atomic_sub_z(&curchunks, nsub); 62 } 63} 64 65/* 66 * Do first-best-fit chunk selection, i.e. select the lowest chunk that best 67 * fits. 68 */ 69static extent_node_t * 70chunk_first_best_fit(arena_t *arena, extent_tree_t *chunks_szad, 71 extent_tree_t *chunks_ad, size_t size) 72{ 73 extent_node_t key; 74 75 assert(size == CHUNK_CEILING(size)); 76 77 extent_node_init(&key, arena, NULL, size, false); 78 return (extent_tree_szad_nsearch(chunks_szad, &key)); 79} 80 81static void * 82chunk_recycle(arena_t *arena, extent_tree_t *chunks_szad, 83 extent_tree_t *chunks_ad, bool cache, void *new_addr, size_t size, 84 size_t alignment, bool *zero, bool dalloc_node) 85{ 86 void *ret; 87 extent_node_t *node; 88 size_t alloc_size, leadsize, trailsize; 89 bool zeroed; 90 91 assert(new_addr == NULL || alignment == chunksize); 92 assert(dalloc_node || new_addr != NULL); 93 94 alloc_size = CHUNK_CEILING(s2u(size + alignment - chunksize)); 95 /* Beware size_t wrap-around. */ 96 if (alloc_size < size) 97 return (NULL); 98 malloc_mutex_lock(&arena->chunks_mtx); 99 if (new_addr != NULL) { 100 extent_node_t key; 101 extent_node_init(&key, arena, new_addr, alloc_size, false); 102 node = extent_tree_ad_search(chunks_ad, &key); 103 } else { 104 node = chunk_first_best_fit(arena, chunks_szad, chunks_ad, 105 alloc_size); 106 } 107 if (node == NULL || (new_addr != NULL && extent_node_size_get(node) < 108 size)) { 109 malloc_mutex_unlock(&arena->chunks_mtx); 110 return (NULL); 111 } 112 leadsize = ALIGNMENT_CEILING((uintptr_t)extent_node_addr_get(node), 113 alignment) - (uintptr_t)extent_node_addr_get(node); 114 assert(new_addr == NULL || leadsize == 0); 115 assert(extent_node_size_get(node) >= leadsize + size); 116 trailsize = extent_node_size_get(node) - leadsize - size; 117 ret = (void *)((uintptr_t)extent_node_addr_get(node) + leadsize); 118 zeroed = extent_node_zeroed_get(node); 119 if (zeroed) 120 *zero = true; 121 /* Remove node from the tree. */ 122 extent_tree_szad_remove(chunks_szad, node); 123 extent_tree_ad_remove(chunks_ad, node); 124 arena_chunk_cache_maybe_remove(arena, node, cache); 125 if (leadsize != 0) { 126 /* Insert the leading space as a smaller chunk. */ 127 extent_node_size_set(node, leadsize); 128 extent_tree_szad_insert(chunks_szad, node); 129 extent_tree_ad_insert(chunks_ad, node); 130 arena_chunk_cache_maybe_insert(arena, node, cache); 131 node = NULL; 132 } 133 if (trailsize != 0) { 134 /* Insert the trailing space as a smaller chunk. */ 135 if (node == NULL) { 136 node = arena_node_alloc(arena); 137 if (node == NULL) { 138 malloc_mutex_unlock(&arena->chunks_mtx); 139 chunk_record(arena, chunks_szad, chunks_ad, 140 cache, ret, size, zeroed); 141 return (NULL); 142 } 143 } 144 extent_node_init(node, arena, (void *)((uintptr_t)(ret) + size), 145 trailsize, zeroed); 146 extent_tree_szad_insert(chunks_szad, node); 147 extent_tree_ad_insert(chunks_ad, node); 148 arena_chunk_cache_maybe_insert(arena, node, cache); 149 node = NULL; 150 } 151 malloc_mutex_unlock(&arena->chunks_mtx); 152 153 assert(dalloc_node || node != NULL); 154 if (dalloc_node && node != NULL) 155 arena_node_dalloc(arena, node); 156 if (*zero) { 157 if (!zeroed) 158 memset(ret, 0, size); 159 else if (config_debug) { 160 size_t i; 161 size_t *p = (size_t *)(uintptr_t)ret; 162 163 JEMALLOC_VALGRIND_MAKE_MEM_DEFINED(ret, size); 164 for (i = 0; i < size / sizeof(size_t); i++) 165 assert(p[i] == 0); 166 } 167 } 168 return (ret); 169} 170 171static void * 172chunk_alloc_core_dss(arena_t *arena, void *new_addr, size_t size, 173 size_t alignment, bool *zero) 174{ 175 void *ret; 176 177 if ((ret = chunk_recycle(arena, &arena->chunks_szad_dss, 178 &arena->chunks_ad_dss, false, new_addr, size, alignment, zero, 179 true)) != NULL) 180 return (ret); 181 ret = chunk_alloc_dss(arena, new_addr, size, alignment, zero); 182 return (ret); 183} 184 185/* 186 * If the caller specifies (!*zero), it is still possible to receive zeroed 187 * memory, in which case *zero is toggled to true. arena_chunk_alloc() takes 188 * advantage of this to avoid demanding zeroed chunks, but taking advantage of 189 * them if they are returned. 190 */ 191static void * 192chunk_alloc_core(arena_t *arena, void *new_addr, size_t size, size_t alignment, 193 bool *zero, dss_prec_t dss_prec) 194{ 195 void *ret; 196 197 assert(size != 0); 198 assert((size & chunksize_mask) == 0); 199 assert(alignment != 0); 200 assert((alignment & chunksize_mask) == 0); 201 202 /* "primary" dss. */ 203 if (have_dss && dss_prec == dss_prec_primary && (ret = 204 chunk_alloc_core_dss(arena, new_addr, size, alignment, zero)) != 205 NULL) 206 return (ret); 207 /* mmap. */ 208 if (!config_munmap && (ret = chunk_recycle(arena, 209 &arena->chunks_szad_mmap, &arena->chunks_ad_mmap, false, new_addr, 210 size, alignment, zero, true)) != NULL) 211 return (ret); 212 /* 213 * Requesting an address is not implemented for chunk_alloc_mmap(), so 214 * only call it if (new_addr == NULL). 215 */ 216 if (new_addr == NULL && (ret = chunk_alloc_mmap(size, alignment, zero)) 217 != NULL) 218 return (ret); 219 /* "secondary" dss. */ 220 if (have_dss && dss_prec == dss_prec_secondary && (ret = 221 chunk_alloc_core_dss(arena, new_addr, size, alignment, zero)) != 222 NULL) 223 return (ret); 224 225 /* All strategies for allocation failed. */ 226 return (NULL); 227} 228 229void * 230chunk_alloc_base(size_t size) 231{ 232 void *ret; 233 bool zero; 234 235 /* 236 * Directly call chunk_alloc_mmap() rather than chunk_alloc_core() 237 * because it's critical that chunk_alloc_base() return untouched 238 * demand-zeroed virtual memory. 239 */ 240 zero = true; 241 ret = chunk_alloc_mmap(size, chunksize, &zero); 242 if (ret == NULL) 243 return (NULL); 244 if (config_valgrind) 245 JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED(ret, size); 246 247 return (ret); 248} 249 250void * 251chunk_alloc_cache(arena_t *arena, void *new_addr, size_t size, size_t alignment, 252 bool *zero, bool dalloc_node) 253{ 254 255 assert(size != 0); 256 assert((size & chunksize_mask) == 0); 257 assert(alignment != 0); 258 assert((alignment & chunksize_mask) == 0); 259 260 return (chunk_recycle(arena, &arena->chunks_szad_cache, 261 &arena->chunks_ad_cache, true, new_addr, size, alignment, zero, 262 dalloc_node)); 263} 264 265static arena_t * 266chunk_arena_get(unsigned arena_ind) 267{ 268 arena_t *arena; 269 270 /* Dodge tsd for a0 in order to avoid bootstrapping issues. */ 271 arena = (arena_ind == 0) ? a0get() : arena_get(tsd_fetch(), arena_ind, 272 false, true); 273 /* 274 * The arena we're allocating on behalf of must have been initialized 275 * already. 276 */ 277 assert(arena != NULL); 278 return (arena); 279} 280 281static void * 282chunk_alloc_arena(arena_t *arena, void *new_addr, size_t size, size_t alignment, 283 bool *zero) 284{ 285 void *ret; 286 287 ret = chunk_alloc_core(arena, new_addr, size, alignment, zero, 288 arena->dss_prec); 289 if (ret == NULL) 290 return (NULL); 291 if (config_valgrind) 292 JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED(ret, size); 293 294 return (ret); 295} 296 297/* 298 * Default arena chunk allocation routine in the absence of user override. This 299 * function isn't actually used by jemalloc, but it does the right thing if the 300 * application passes calls through to it during chunk allocation. 301 */ 302void * 303chunk_alloc_default(void *new_addr, size_t size, size_t alignment, bool *zero, 304 unsigned arena_ind) 305{ 306 arena_t *arena; 307 308 arena = chunk_arena_get(arena_ind); 309 return (chunk_alloc_arena(arena, new_addr, size, alignment, zero)); 310} 311 312void * 313chunk_alloc_wrapper(arena_t *arena, chunk_alloc_t *chunk_alloc, void *new_addr, 314 size_t size, size_t alignment, bool *zero) 315{ 316 void *ret; 317 318 ret = chunk_alloc(new_addr, size, alignment, zero, arena->ind); 319 if (ret == NULL) 320 return (NULL); 321 if (config_valgrind && chunk_alloc != chunk_alloc_default) 322 JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED(ret, chunksize); 323 return (ret); 324} 325 326void 327chunk_record(arena_t *arena, extent_tree_t *chunks_szad, 328 extent_tree_t *chunks_ad, bool cache, void *chunk, size_t size, bool zeroed) 329{ 330 bool unzeroed; 331 extent_node_t *node, *prev; 332 extent_node_t key; 333 334 assert(!cache || !zeroed); 335 unzeroed = cache || !zeroed; 336 JEMALLOC_VALGRIND_MAKE_MEM_NOACCESS(chunk, size); 337 338 malloc_mutex_lock(&arena->chunks_mtx); 339 extent_node_init(&key, arena, (void *)((uintptr_t)chunk + size), 0, 340 false); 341 node = extent_tree_ad_nsearch(chunks_ad, &key); 342 /* Try to coalesce forward. */ 343 if (node != NULL && extent_node_addr_get(node) == 344 extent_node_addr_get(&key)) { 345 /* 346 * Coalesce chunk with the following address range. This does 347 * not change the position within chunks_ad, so only 348 * remove/insert from/into chunks_szad. 349 */ 350 extent_tree_szad_remove(chunks_szad, node); 351 arena_chunk_cache_maybe_remove(arena, node, cache); 352 extent_node_addr_set(node, chunk); 353 extent_node_size_set(node, size + extent_node_size_get(node)); 354 extent_node_zeroed_set(node, extent_node_zeroed_get(node) && 355 !unzeroed); 356 extent_tree_szad_insert(chunks_szad, node); 357 arena_chunk_cache_maybe_insert(arena, node, cache); 358 } else { 359 /* Coalescing forward failed, so insert a new node. */ 360 node = arena_node_alloc(arena); 361 if (node == NULL) { 362 /* 363 * Node allocation failed, which is an exceedingly 364 * unlikely failure. Leak chunk after making sure its 365 * pages have already been purged, so that this is only 366 * a virtual memory leak. 367 */ 368 if (cache) { 369 chunk_purge_wrapper(arena, arena->chunk_purge, 370 chunk, 0, size); 371 } 372 goto label_return; 373 } 374 extent_node_init(node, arena, chunk, size, !unzeroed); 375 extent_tree_ad_insert(chunks_ad, node); 376 extent_tree_szad_insert(chunks_szad, node); 377 arena_chunk_cache_maybe_insert(arena, node, cache); 378 } 379 380 /* Try to coalesce backward. */ 381 prev = extent_tree_ad_prev(chunks_ad, node); 382 if (prev != NULL && (void *)((uintptr_t)extent_node_addr_get(prev) + 383 extent_node_size_get(prev)) == chunk) { 384 /* 385 * Coalesce chunk with the previous address range. This does 386 * not change the position within chunks_ad, so only 387 * remove/insert node from/into chunks_szad. 388 */ 389 extent_tree_szad_remove(chunks_szad, prev); 390 extent_tree_ad_remove(chunks_ad, prev); 391 arena_chunk_cache_maybe_remove(arena, prev, cache); 392 extent_tree_szad_remove(chunks_szad, node); 393 arena_chunk_cache_maybe_remove(arena, node, cache); 394 extent_node_addr_set(node, extent_node_addr_get(prev)); 395 extent_node_size_set(node, extent_node_size_get(prev) + 396 extent_node_size_get(node)); 397 extent_node_zeroed_set(node, extent_node_zeroed_get(prev) && 398 extent_node_zeroed_get(node)); 399 extent_tree_szad_insert(chunks_szad, node); 400 arena_chunk_cache_maybe_insert(arena, node, cache); 401 402 arena_node_dalloc(arena, prev); 403 } 404 405label_return: 406 malloc_mutex_unlock(&arena->chunks_mtx); 407} 408 409void 410chunk_dalloc_cache(arena_t *arena, void *chunk, size_t size) 411{ 412 413 assert(chunk != NULL); 414 assert(CHUNK_ADDR2BASE(chunk) == chunk); 415 assert(size != 0); 416 assert((size & chunksize_mask) == 0); 417 418 chunk_record(arena, &arena->chunks_szad_cache, &arena->chunks_ad_cache, 419 true, chunk, size, false); 420 arena_maybe_purge(arena); 421} 422 423void 424chunk_dalloc_arena(arena_t *arena, void *chunk, size_t size, bool zeroed) 425{ 426 427 assert(chunk != NULL); 428 assert(CHUNK_ADDR2BASE(chunk) == chunk); 429 assert(size != 0); 430 assert((size & chunksize_mask) == 0); 431 432 if (have_dss && chunk_in_dss(chunk)) { 433 chunk_record(arena, &arena->chunks_szad_dss, 434 &arena->chunks_ad_dss, false, chunk, size, zeroed); 435 } else if (chunk_dalloc_mmap(chunk, size)) { 436 chunk_record(arena, &arena->chunks_szad_mmap, 437 &arena->chunks_ad_mmap, false, chunk, size, zeroed); 438 } 439} 440 441/* 442 * Default arena chunk deallocation routine in the absence of user override. 443 * This function isn't actually used by jemalloc, but it does the right thing if 444 * the application passes calls through to it during chunk deallocation. 445 */ 446bool 447chunk_dalloc_default(void *chunk, size_t size, unsigned arena_ind) 448{ 449 450 chunk_dalloc_arena(chunk_arena_get(arena_ind), chunk, size, false); 451 return (false); 452} 453 454void 455chunk_dalloc_wrapper(arena_t *arena, chunk_dalloc_t *chunk_dalloc, void *chunk, 456 size_t size) 457{ 458 459 chunk_dalloc(chunk, size, arena->ind); 460 if (config_valgrind && chunk_dalloc != chunk_dalloc_default) 461 JEMALLOC_VALGRIND_MAKE_MEM_NOACCESS(chunk, size); 462} 463 464bool 465chunk_purge_arena(arena_t *arena, void *chunk, size_t offset, size_t length) 466{ 467 468 assert(chunk != NULL); 469 assert(CHUNK_ADDR2BASE(chunk) == chunk); 470 assert((offset & PAGE_MASK) == 0); 471 assert(length != 0); 472 assert((length & PAGE_MASK) == 0); 473 474 return (pages_purge((void *)((uintptr_t)chunk + (uintptr_t)offset), 475 length)); 476} 477 478bool 479chunk_purge_default(void *chunk, size_t offset, size_t length, 480 unsigned arena_ind) 481{ 482 483 return (chunk_purge_arena(chunk_arena_get(arena_ind), chunk, offset, 484 length)); 485} 486 487bool 488chunk_purge_wrapper(arena_t *arena, chunk_purge_t *chunk_purge, void *chunk, 489 size_t offset, size_t length) 490{ 491 492 return (chunk_purge(chunk, offset, length, arena->ind)); 493} 494 495static rtree_node_elm_t * 496chunks_rtree_node_alloc(size_t nelms) 497{ 498 499 return ((rtree_node_elm_t *)base_alloc(nelms * 500 sizeof(rtree_node_elm_t))); 501} 502 503bool 504chunk_boot(void) 505{ 506 507 /* Set variables according to the value of opt_lg_chunk. */ 508 chunksize = (ZU(1) << opt_lg_chunk); 509 assert(chunksize >= PAGE); 510 chunksize_mask = chunksize - 1; 511 chunk_npages = (chunksize >> LG_PAGE); 512 513 if (have_dss && chunk_dss_boot()) 514 return (true); 515 if (rtree_new(&chunks_rtree, (ZU(1) << (LG_SIZEOF_PTR+3)) - 516 opt_lg_chunk, chunks_rtree_node_alloc, NULL)) 517 return (true); 518 519 return (false); 520} 521 522void 523chunk_prefork(void) 524{ 525 526 chunk_dss_prefork(); 527} 528 529void 530chunk_postfork_parent(void) 531{ 532 533 chunk_dss_postfork_parent(); 534} 535 536void 537chunk_postfork_child(void) 538{ 539 540 chunk_dss_postfork_child(); 541} 542