chunk.c revision 242844
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 /* Remove node from the tree. */ 82 extent_tree_szad_remove(chunks_szad, node); 83 extent_tree_ad_remove(chunks_ad, node); 84 if (leadsize != 0) { 85 /* Insert the leading space as a smaller chunk. */ 86 node->size = leadsize; 87 extent_tree_szad_insert(chunks_szad, node); 88 extent_tree_ad_insert(chunks_ad, node); 89 node = NULL; 90 } 91 if (trailsize != 0) { 92 /* Insert the trailing space as a smaller chunk. */ 93 if (node == NULL) { 94 /* 95 * An additional node is required, but 96 * base_node_alloc() can cause a new base chunk to be 97 * allocated. Drop chunks_mtx in order to avoid 98 * deadlock, and if node allocation fails, deallocate 99 * the result before returning an error. 100 */ 101 malloc_mutex_unlock(&chunks_mtx); 102 node = base_node_alloc(); 103 if (node == NULL) { 104 chunk_dealloc(ret, size, true); 105 return (NULL); 106 } 107 malloc_mutex_lock(&chunks_mtx); 108 } 109 node->addr = (void *)((uintptr_t)(ret) + size); 110 node->size = trailsize; 111 extent_tree_szad_insert(chunks_szad, node); 112 extent_tree_ad_insert(chunks_ad, node); 113 node = NULL; 114 } 115 malloc_mutex_unlock(&chunks_mtx); 116 117 zeroed = false; 118 if (node != NULL) { 119 if (node->zeroed) { 120 zeroed = true; 121 *zero = true; 122 } 123 base_node_dealloc(node); 124 } 125 if (zeroed == false && *zero) { 126 VALGRIND_MAKE_MEM_UNDEFINED(ret, size); 127 memset(ret, 0, size); 128 } 129 return (ret); 130} 131 132/* 133 * If the caller specifies (*zero == false), it is still possible to receive 134 * zeroed memory, in which case *zero is toggled to true. arena_chunk_alloc() 135 * takes advantage of this to avoid demanding zeroed chunks, but taking 136 * advantage of them if they are returned. 137 */ 138void * 139chunk_alloc(size_t size, size_t alignment, bool base, bool *zero, 140 dss_prec_t dss_prec) 141{ 142 void *ret; 143 144 assert(size != 0); 145 assert((size & chunksize_mask) == 0); 146 assert(alignment != 0); 147 assert((alignment & chunksize_mask) == 0); 148 149 /* "primary" dss. */ 150 if (config_dss && dss_prec == dss_prec_primary) { 151 if ((ret = chunk_recycle(&chunks_szad_dss, &chunks_ad_dss, size, 152 alignment, base, zero)) != NULL) 153 goto label_return; 154 if ((ret = chunk_alloc_dss(size, alignment, zero)) != NULL) 155 goto label_return; 156 } 157 /* mmap. */ 158 if ((ret = chunk_recycle(&chunks_szad_mmap, &chunks_ad_mmap, size, 159 alignment, base, zero)) != NULL) 160 goto label_return; 161 if ((ret = chunk_alloc_mmap(size, alignment, zero)) != NULL) 162 goto label_return; 163 /* "secondary" dss. */ 164 if (config_dss && dss_prec == dss_prec_secondary) { 165 if ((ret = chunk_recycle(&chunks_szad_dss, &chunks_ad_dss, size, 166 alignment, base, zero)) != NULL) 167 goto label_return; 168 if ((ret = chunk_alloc_dss(size, alignment, zero)) != NULL) 169 goto label_return; 170 } 171 172 /* All strategies for allocation failed. */ 173 ret = NULL; 174label_return: 175 if (config_ivsalloc && base == false && ret != NULL) { 176 if (rtree_set(chunks_rtree, (uintptr_t)ret, ret)) { 177 chunk_dealloc(ret, size, true); 178 return (NULL); 179 } 180 } 181 if ((config_stats || config_prof) && ret != NULL) { 182 bool gdump; 183 malloc_mutex_lock(&chunks_mtx); 184 if (config_stats) 185 stats_chunks.nchunks += (size / chunksize); 186 stats_chunks.curchunks += (size / chunksize); 187 if (stats_chunks.curchunks > stats_chunks.highchunks) { 188 stats_chunks.highchunks = stats_chunks.curchunks; 189 if (config_prof) 190 gdump = true; 191 } else if (config_prof) 192 gdump = false; 193 malloc_mutex_unlock(&chunks_mtx); 194 if (config_prof && opt_prof && opt_prof_gdump && gdump) 195 prof_gdump(); 196 } 197 if (config_debug && *zero && ret != NULL) { 198 size_t i; 199 size_t *p = (size_t *)(uintptr_t)ret; 200 201 VALGRIND_MAKE_MEM_DEFINED(ret, size); 202 for (i = 0; i < size / sizeof(size_t); i++) 203 assert(p[i] == 0); 204 } 205 assert(CHUNK_ADDR2BASE(ret) == ret); 206 return (ret); 207} 208 209static void 210chunk_record(extent_tree_t *chunks_szad, extent_tree_t *chunks_ad, void *chunk, 211 size_t size) 212{ 213 bool unzeroed; 214 extent_node_t *xnode, *node, *prev, key; 215 216 unzeroed = pages_purge(chunk, size); 217 218 /* 219 * Allocate a node before acquiring chunks_mtx even though it might not 220 * be needed, because base_node_alloc() may cause a new base chunk to 221 * be allocated, which could cause deadlock if chunks_mtx were already 222 * held. 223 */ 224 xnode = base_node_alloc(); 225 226 malloc_mutex_lock(&chunks_mtx); 227 key.addr = (void *)((uintptr_t)chunk + size); 228 node = extent_tree_ad_nsearch(chunks_ad, &key); 229 /* Try to coalesce forward. */ 230 if (node != NULL && node->addr == key.addr) { 231 /* 232 * Coalesce chunk with the following address range. This does 233 * not change the position within chunks_ad, so only 234 * remove/insert from/into chunks_szad. 235 */ 236 extent_tree_szad_remove(chunks_szad, node); 237 node->addr = chunk; 238 node->size += size; 239 node->zeroed = (node->zeroed && (unzeroed == false)); 240 extent_tree_szad_insert(chunks_szad, node); 241 if (xnode != NULL) 242 base_node_dealloc(xnode); 243 } else { 244 /* Coalescing forward failed, so insert a new node. */ 245 if (xnode == NULL) { 246 /* 247 * base_node_alloc() failed, which is an exceedingly 248 * unlikely failure. Leak chunk; its pages have 249 * already been purged, so this is only a virtual 250 * memory leak. 251 */ 252 malloc_mutex_unlock(&chunks_mtx); 253 return; 254 } 255 node = xnode; 256 node->addr = chunk; 257 node->size = size; 258 node->zeroed = (unzeroed == false); 259 extent_tree_ad_insert(chunks_ad, node); 260 extent_tree_szad_insert(chunks_szad, node); 261 } 262 263 /* Try to coalesce backward. */ 264 prev = extent_tree_ad_prev(chunks_ad, node); 265 if (prev != NULL && (void *)((uintptr_t)prev->addr + prev->size) == 266 chunk) { 267 /* 268 * Coalesce chunk with the previous address range. This does 269 * not change the position within chunks_ad, so only 270 * remove/insert node from/into chunks_szad. 271 */ 272 extent_tree_szad_remove(chunks_szad, prev); 273 extent_tree_ad_remove(chunks_ad, prev); 274 275 extent_tree_szad_remove(chunks_szad, node); 276 node->addr = prev->addr; 277 node->size += prev->size; 278 node->zeroed = (node->zeroed && prev->zeroed); 279 extent_tree_szad_insert(chunks_szad, node); 280 281 base_node_dealloc(prev); 282 } 283 malloc_mutex_unlock(&chunks_mtx); 284} 285 286void 287chunk_unmap(void *chunk, size_t size) 288{ 289 assert(chunk != NULL); 290 assert(CHUNK_ADDR2BASE(chunk) == chunk); 291 assert(size != 0); 292 assert((size & chunksize_mask) == 0); 293 294 if (config_dss && chunk_in_dss(chunk)) 295 chunk_record(&chunks_szad_dss, &chunks_ad_dss, chunk, size); 296 else if (chunk_dealloc_mmap(chunk, size)) 297 chunk_record(&chunks_szad_mmap, &chunks_ad_mmap, chunk, size); 298} 299 300void 301chunk_dealloc(void *chunk, size_t size, bool unmap) 302{ 303 304 assert(chunk != NULL); 305 assert(CHUNK_ADDR2BASE(chunk) == chunk); 306 assert(size != 0); 307 assert((size & chunksize_mask) == 0); 308 309 if (config_ivsalloc) 310 rtree_set(chunks_rtree, (uintptr_t)chunk, NULL); 311 if (config_stats || config_prof) { 312 malloc_mutex_lock(&chunks_mtx); 313 assert(stats_chunks.curchunks >= (size / chunksize)); 314 stats_chunks.curchunks -= (size / chunksize); 315 malloc_mutex_unlock(&chunks_mtx); 316 } 317 318 if (unmap) 319 chunk_unmap(chunk, size); 320} 321 322bool 323chunk_boot(void) 324{ 325 326 /* Set variables according to the value of opt_lg_chunk. */ 327 chunksize = (ZU(1) << opt_lg_chunk); 328 assert(chunksize >= PAGE); 329 chunksize_mask = chunksize - 1; 330 chunk_npages = (chunksize >> LG_PAGE); 331 332 if (config_stats || config_prof) { 333 if (malloc_mutex_init(&chunks_mtx)) 334 return (true); 335 memset(&stats_chunks, 0, sizeof(chunk_stats_t)); 336 } 337 if (config_dss && chunk_dss_boot()) 338 return (true); 339 extent_tree_szad_new(&chunks_szad_mmap); 340 extent_tree_ad_new(&chunks_ad_mmap); 341 extent_tree_szad_new(&chunks_szad_dss); 342 extent_tree_ad_new(&chunks_ad_dss); 343 if (config_ivsalloc) { 344 chunks_rtree = rtree_new((ZU(1) << (LG_SIZEOF_PTR+3)) - 345 opt_lg_chunk); 346 if (chunks_rtree == NULL) 347 return (true); 348 } 349 350 return (false); 351} 352 353void 354chunk_prefork(void) 355{ 356 357 malloc_mutex_lock(&chunks_mtx); 358 if (config_ivsalloc) 359 rtree_prefork(chunks_rtree); 360 chunk_dss_prefork(); 361} 362 363void 364chunk_postfork_parent(void) 365{ 366 367 chunk_dss_postfork_parent(); 368 if (config_ivsalloc) 369 rtree_postfork_parent(chunks_rtree); 370 malloc_mutex_postfork_parent(&chunks_mtx); 371} 372 373void 374chunk_postfork_child(void) 375{ 376 377 chunk_dss_postfork_child(); 378 if (config_ivsalloc) 379 rtree_postfork_child(chunks_rtree); 380 malloc_mutex_postfork_child(&chunks_mtx); 381} 382