contrib/jemalloc/src/chunk.c

   1 #define JEMALLOC_CHUNK_C_
   2 #include "jemalloc/internal/jemalloc_internal.h"
   3
   4 /******************************************************************************/
   5 /* Data. */
   6
   7 const char      *opt_dss = DSS_DEFAULT;
   8 size_t          opt_lg_chunk = LG_CHUNK_DEFAULT;
   9
  10 malloc_mutex_t  chunks_mtx;
  11 chunk_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  */
  19 static extent_tree_t    chunks_szad_mmap;
  20 static extent_tree_t    chunks_ad_mmap;
  21 static extent_tree_t    chunks_szad_dss;
  22 static extent_tree_t    chunks_ad_dss;
  23
  24 rtree_t         *chunks_rtree;
  25
  26 /* Various chunk-related settings. */
  27 size_t          chunksize;
  28 size_t          chunksize_mask; /* (chunksize - 1). */
  29 size_t          chunk_npages;
  30 size_t          map_bias;
  31 size_t          arena_maxclass; /* Max size class for arenas. */
  32
  33 /******************************************************************************/
  34 /* Function prototypes for non-inline static functions. */
  35
  36 static 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);
  39 static void     chunk_record(extent_tree_t *chunks_szad,
  40     extent_tree_t *chunks_ad, void *chunk, size_t size);
  41
  42 /******************************************************************************/
  43
  44 static void *
  45 chunk_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  */
 144 void *
 145 chunk_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;
 180 label_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
 212 static void
 213 chunk_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
 288 label_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
 300 void
 301 chunk_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
 314 void
 315 chunk_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
 336 bool
 337 chunk_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
 367 void
 368 chunk_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
 377 void
 378 chunk_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
 387 void
 388 chunk_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 }