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 10malloc_mutex_t chunks_mtx; 11chunk_stats_t stats_chunks; 12 13/* 14 * Trees of chunks that were previously allocated (trees differ only in node 15 * ordering). These are used when allocating chunks, in an attempt to re-use 16 * address space. Depending on function, different tree orderings are needed, 17 * which is why there are two trees with the same contents. 18 */ 19static extent_tree_t chunks_szad_mmap; 20static extent_tree_t chunks_ad_mmap; 21static extent_tree_t chunks_szad_dss; 22static extent_tree_t chunks_ad_dss; 23 24rtree_t *chunks_rtree; 25 26/* Various chunk-related settings. */ 27size_t chunksize; 28size_t chunksize_mask; /* (chunksize - 1). */ 29size_t chunk_npages; 30size_t map_bias; 31size_t arena_maxclass; /* Max size class for arenas. */ 32 33/******************************************************************************/ 34/* Function prototypes for non-inline static functions. */ 35 36static void *chunk_recycle(extent_tree_t *chunks_szad, 37 extent_tree_t *chunks_ad, size_t size, size_t alignment, bool base, 38 bool *zero); 39static void chunk_record(extent_tree_t *chunks_szad, 40 extent_tree_t *chunks_ad, void *chunk, size_t size); 41 42/******************************************************************************/ 43 44static void * 45chunk_recycle(extent_tree_t *chunks_szad, extent_tree_t *chunks_ad, size_t size, 46 size_t alignment, bool base, bool *zero) 47{ 48 void *ret; 49 extent_node_t *node; 50 extent_node_t key; 51 size_t alloc_size, leadsize, trailsize; 52 bool zeroed; 53 54 if (base) { 55 /* 56 * This function may need to call base_node_{,de}alloc(), but 57 * the current chunk allocation request is on behalf of the 58 * base allocator. Avoid deadlock (and if that weren't an 59 * issue, potential for infinite recursion) by returning NULL. 60 */ 61 return (NULL); 62 } 63 64 alloc_size = size + alignment - chunksize; 65 /* Beware size_t wrap-around. */ 66 if (alloc_size < size) 67 return (NULL); 68 key.addr = NULL; 69 key.size = alloc_size; 70 malloc_mutex_lock(&chunks_mtx); 71 node = extent_tree_szad_nsearch(chunks_szad, &key); 72 if (node == NULL) { 73 malloc_mutex_unlock(&chunks_mtx); 74 return (NULL); 75 } 76 leadsize = ALIGNMENT_CEILING((uintptr_t)node->addr, alignment) - 77 (uintptr_t)node->addr; 78 assert(node->size >= leadsize + size); 79 trailsize = node->size - leadsize - size; 80 ret = (void *)((uintptr_t)node->addr + leadsize); 81 zeroed = node->zeroed; 82 if (zeroed) 83 *zero = true; 84 /* Remove node from the tree. */ 85 extent_tree_szad_remove(chunks_szad, node); 86 extent_tree_ad_remove(chunks_ad, node); 87 if (leadsize != 0) { 88 /* Insert the leading space as a smaller chunk. */ 89 node->size = leadsize; 90 extent_tree_szad_insert(chunks_szad, node); 91 extent_tree_ad_insert(chunks_ad, node); 92 node = NULL; 93 } 94 if (trailsize != 0) { 95 /* Insert the trailing space as a smaller chunk. */ 96 if (node == NULL) { 97 /* 98 * An additional node is required, but 99 * base_node_alloc() can cause a new base chunk to be 100 * allocated. Drop chunks_mtx in order to avoid 101 * deadlock, and if node allocation fails, deallocate 102 * the result before returning an error. 103 */ 104 malloc_mutex_unlock(&chunks_mtx); 105 node = base_node_alloc(); 106 if (node == NULL) { 107 chunk_dealloc(ret, size, true); 108 return (NULL); 109 } 110 malloc_mutex_lock(&chunks_mtx); 111 } 112 node->addr = (void *)((uintptr_t)(ret) + size); 113 node->size = trailsize; 114 node->zeroed = zeroed; 115 extent_tree_szad_insert(chunks_szad, node); 116 extent_tree_ad_insert(chunks_ad, node); 117 node = NULL; 118 } 119 malloc_mutex_unlock(&chunks_mtx); 120 121 if (node != NULL) 122 base_node_dealloc(node); 123 if (*zero) { 124 if (zeroed == false) 125 memset(ret, 0, size); 126 else if (config_debug) { 127 size_t i; 128 size_t *p = (size_t *)(uintptr_t)ret; 129 130 VALGRIND_MAKE_MEM_DEFINED(ret, size); 131 for (i = 0; i < size / sizeof(size_t); i++) 132 assert(p[i] == 0); 133 } 134 } 135 return (ret); 136} 137 138/* 139 * If the caller specifies (*zero == false), it is still possible to receive 140 * zeroed memory, in which case *zero is toggled to true. arena_chunk_alloc() 141 * takes advantage of this to avoid demanding zeroed chunks, but taking 142 * advantage of them if they are returned. 143 */ 144void * 145chunk_alloc(size_t size, size_t alignment, bool base, bool *zero, 146 dss_prec_t dss_prec) 147{ 148 void *ret; 149 150 assert(size != 0); 151 assert((size & chunksize_mask) == 0); 152 assert(alignment != 0); 153 assert((alignment & chunksize_mask) == 0); 154 155 /* "primary" dss. */ 156 if (config_dss && dss_prec == dss_prec_primary) { 157 if ((ret = chunk_recycle(&chunks_szad_dss, &chunks_ad_dss, size, 158 alignment, base, zero)) != NULL) 159 goto label_return; 160 if ((ret = chunk_alloc_dss(size, alignment, zero)) != NULL) 161 goto label_return; 162 } 163 /* mmap. */ 164 if ((ret = chunk_recycle(&chunks_szad_mmap, &chunks_ad_mmap, size, 165 alignment, base, zero)) != NULL) 166 goto label_return; 167 if ((ret = chunk_alloc_mmap(size, alignment, zero)) != NULL) 168 goto label_return; 169 /* "secondary" dss. */ 170 if (config_dss && dss_prec == dss_prec_secondary) { 171 if ((ret = chunk_recycle(&chunks_szad_dss, &chunks_ad_dss, size, 172 alignment, base, zero)) != NULL) 173 goto label_return; 174 if ((ret = chunk_alloc_dss(size, alignment, zero)) != NULL) 175 goto label_return; 176 } 177 178 /* All strategies for allocation failed. */ 179 ret = NULL; 180label_return: 181 if (ret != NULL) { 182 if (config_ivsalloc && base == false) { 183 if (rtree_set(chunks_rtree, (uintptr_t)ret, ret)) { 184 chunk_dealloc(ret, size, true); 185 return (NULL); 186 } 187 } 188 if (config_stats || config_prof) { 189 bool gdump; 190 malloc_mutex_lock(&chunks_mtx); 191 if (config_stats) 192 stats_chunks.nchunks += (size / chunksize); 193 stats_chunks.curchunks += (size / chunksize); 194 if (stats_chunks.curchunks > stats_chunks.highchunks) { 195 stats_chunks.highchunks = 196 stats_chunks.curchunks; 197 if (config_prof) 198 gdump = true; 199 } else if (config_prof) 200 gdump = false; 201 malloc_mutex_unlock(&chunks_mtx); 202 if (config_prof && opt_prof && opt_prof_gdump && gdump) 203 prof_gdump(); 204 } 205 if (config_valgrind) 206 VALGRIND_MAKE_MEM_UNDEFINED(ret, size); 207 } 208 assert(CHUNK_ADDR2BASE(ret) == ret); 209 return (ret); 210} 211 212static void 213chunk_record(extent_tree_t *chunks_szad, extent_tree_t *chunks_ad, void *chunk, 214 size_t size) 215{ 216 bool unzeroed; 217 extent_node_t *xnode, *node, *prev, *xprev, key; 218 219 unzeroed = pages_purge(chunk, size); 220 VALGRIND_MAKE_MEM_NOACCESS(chunk, size); 221 222 /* 223 * Allocate a node before acquiring chunks_mtx even though it might not 224 * be needed, because base_node_alloc() may cause a new base chunk to 225 * be allocated, which could cause deadlock if chunks_mtx were already 226 * held. 227 */ 228 xnode = base_node_alloc(); 229 /* Use xprev to implement conditional deferred deallocation of prev. */ 230 xprev = NULL; 231 232 malloc_mutex_lock(&chunks_mtx); 233 key.addr = (void *)((uintptr_t)chunk + size); 234 node = extent_tree_ad_nsearch(chunks_ad, &key); 235 /* Try to coalesce forward. */ 236 if (node != NULL && node->addr == key.addr) { 237 /* 238 * Coalesce chunk with the following address range. This does 239 * not change the position within chunks_ad, so only 240 * remove/insert from/into chunks_szad. 241 */ 242 extent_tree_szad_remove(chunks_szad, node); 243 node->addr = chunk; 244 node->size += size; 245 node->zeroed = (node->zeroed && (unzeroed == false)); 246 extent_tree_szad_insert(chunks_szad, node); 247 } else { 248 /* Coalescing forward failed, so insert a new node. */ 249 if (xnode == NULL) { 250 /* 251 * base_node_alloc() failed, which is an exceedingly 252 * unlikely failure. Leak chunk; its pages have 253 * already been purged, so this is only a virtual 254 * memory leak. 255 */ 256 goto label_return; 257 } 258 node = xnode; 259 xnode = NULL; /* Prevent deallocation below. */ 260 node->addr = chunk; 261 node->size = size; 262 node->zeroed = (unzeroed == false); 263 extent_tree_ad_insert(chunks_ad, node); 264 extent_tree_szad_insert(chunks_szad, node); 265 } 266 267 /* Try to coalesce backward. */ 268 prev = extent_tree_ad_prev(chunks_ad, node); 269 if (prev != NULL && (void *)((uintptr_t)prev->addr + prev->size) == 270 chunk) { 271 /* 272 * Coalesce chunk with the previous address range. This does 273 * not change the position within chunks_ad, so only 274 * remove/insert node from/into chunks_szad. 275 */ 276 extent_tree_szad_remove(chunks_szad, prev); 277 extent_tree_ad_remove(chunks_ad, prev); 278 279 extent_tree_szad_remove(chunks_szad, node); 280 node->addr = prev->addr; 281 node->size += prev->size; 282 node->zeroed = (node->zeroed && prev->zeroed); 283 extent_tree_szad_insert(chunks_szad, node); 284 285 xprev = prev; 286 } 287 288label_return: 289 malloc_mutex_unlock(&chunks_mtx); 290 /* 291 * Deallocate xnode and/or xprev after unlocking chunks_mtx in order to 292 * avoid potential deadlock. 293 */ 294 if (xnode != NULL) 295 base_node_dealloc(xnode); 296 if (xprev != NULL) 297 base_node_dealloc(prev); 298} 299 300void 301chunk_unmap(void *chunk, size_t size) 302{ 303 assert(chunk != NULL); 304 assert(CHUNK_ADDR2BASE(chunk) == chunk); 305 assert(size != 0); 306 assert((size & chunksize_mask) == 0); 307 308 if (config_dss && chunk_in_dss(chunk)) 309 chunk_record(&chunks_szad_dss, &chunks_ad_dss, chunk, size); 310 else if (chunk_dealloc_mmap(chunk, size)) 311 chunk_record(&chunks_szad_mmap, &chunks_ad_mmap, chunk, size); 312} 313 314void 315chunk_dealloc(void *chunk, size_t size, bool unmap) 316{ 317 318 assert(chunk != NULL); 319 assert(CHUNK_ADDR2BASE(chunk) == chunk); 320 assert(size != 0); 321 assert((size & chunksize_mask) == 0); 322 323 if (config_ivsalloc) 324 rtree_set(chunks_rtree, (uintptr_t)chunk, NULL); 325 if (config_stats || config_prof) { 326 malloc_mutex_lock(&chunks_mtx); 327 assert(stats_chunks.curchunks >= (size / chunksize)); 328 stats_chunks.curchunks -= (size / chunksize); 329 malloc_mutex_unlock(&chunks_mtx); 330 } 331 332 if (unmap) 333 chunk_unmap(chunk, size); 334} 335 336bool 337chunk_boot(void) 338{ 339 340 /* Set variables according to the value of opt_lg_chunk. */ 341 chunksize = (ZU(1) << opt_lg_chunk); 342 assert(chunksize >= PAGE); 343 chunksize_mask = chunksize - 1; 344 chunk_npages = (chunksize >> LG_PAGE); 345 346 if (config_stats || config_prof) { 347 if (malloc_mutex_init(&chunks_mtx)) 348 return (true); 349 memset(&stats_chunks, 0, sizeof(chunk_stats_t)); 350 } 351 if (config_dss && chunk_dss_boot()) 352 return (true); 353 extent_tree_szad_new(&chunks_szad_mmap); 354 extent_tree_ad_new(&chunks_ad_mmap); 355 extent_tree_szad_new(&chunks_szad_dss); 356 extent_tree_ad_new(&chunks_ad_dss); 357 if (config_ivsalloc) { 358 chunks_rtree = rtree_new((ZU(1) << (LG_SIZEOF_PTR+3)) - 359 opt_lg_chunk); 360 if (chunks_rtree == NULL) 361 return (true); 362 } 363 364 return (false); 365} 366 367void 368chunk_prefork(void) 369{ 370 371 malloc_mutex_lock(&chunks_mtx); 372 if (config_ivsalloc) 373 rtree_prefork(chunks_rtree); 374 chunk_dss_prefork(); 375} 376 377void 378chunk_postfork_parent(void) 379{ 380 381 chunk_dss_postfork_parent(); 382 if (config_ivsalloc) 383 rtree_postfork_parent(chunks_rtree); 384 malloc_mutex_postfork_parent(&chunks_mtx); 385} 386 387void 388chunk_postfork_child(void) 389{ 390 391 chunk_dss_postfork_child(); 392 if (config_ivsalloc) 393 rtree_postfork_child(chunks_rtree); 394 malloc_mutex_postfork_child(&chunks_mtx); 395} 396