Redis 2.6.5

[redis.git] / deps / jemalloc / src / chunk.c

diff --git a/deps/jemalloc/src/chunk.c b/deps/jemalloc/src/chunk.c
index 301519e8042fb350448d882753490a790a32aaf3..6bc245447977362591c88c5c0d1bd77eef3e907e 100644 (file)
--- a/deps/jemalloc/src/chunk.c
+++ b/deps/jemalloc/src/chunk.c
@@ -5,18 +5,20 @@
 /* Data. */
 
 size_t opt_lg_chunk = LG_CHUNK_DEFAULT;
 /* Data. */
 
 size_t opt_lg_chunk = LG_CHUNK_DEFAULT;

-#ifdef JEMALLOC_SWAP
-bool   opt_overcommit = true;
-#endif

 
 

-#if (defined(JEMALLOC_STATS) || defined(JEMALLOC_PROF))

 malloc_mutex_t chunks_mtx;
 chunk_stats_t  stats_chunks;
 malloc_mutex_t chunks_mtx;
 chunk_stats_t  stats_chunks;

-#endif

 
 

-#ifdef JEMALLOC_IVSALLOC
+/*
+ * Trees of chunks that were previously allocated (trees differ only in node
+ * ordering).  These are used when allocating chunks, in an attempt to re-use
+ * address space.  Depending on function, different tree orderings are needed,
+ * which is why there are two trees with the same contents.
+ */
+static extent_tree_t   chunks_szad;
+static extent_tree_t   chunks_ad;
+

 rtree_t                *chunks_rtree;
 rtree_t                *chunks_rtree;

-#endif

 
 /* Various chunk-related settings. */
 size_t         chunksize;
 
 /* Various chunk-related settings. */
 size_t         chunksize;


@@ -26,6 +28,98 @@ size_t               map_bias;
 size_t         arena_maxclass; /* Max size class for arenas. */
 
 /******************************************************************************/
 size_t         arena_maxclass; /* Max size class for arenas. */
 
 /******************************************************************************/

+/* Function prototypes for non-inline static functions. */
+
+static void    *chunk_recycle(size_t size, size_t alignment, bool base,
+    bool *zero);
+static void    chunk_record(void *chunk, size_t size);
+
+/******************************************************************************/
+
+static void *
+chunk_recycle(size_t size, size_t alignment, bool base, bool *zero)
+{
+       void *ret;
+       extent_node_t *node;
+       extent_node_t key;
+       size_t alloc_size, leadsize, trailsize;
+
+       if (base) {
+               /*
+                * This function may need to call base_node_{,de}alloc(), but
+                * the current chunk allocation request is on behalf of the
+                * base allocator.  Avoid deadlock (and if that weren't an
+                * issue, potential for infinite recursion) by returning NULL.
+                */
+               return (NULL);
+       }
+
+       alloc_size = size + alignment - chunksize;
+       /* Beware size_t wrap-around. */
+       if (alloc_size < size)
+               return (NULL);
+       key.addr = NULL;
+       key.size = alloc_size;
+       malloc_mutex_lock(&chunks_mtx);
+       node = extent_tree_szad_nsearch(&chunks_szad, &key);
+       if (node == NULL) {
+               malloc_mutex_unlock(&chunks_mtx);
+               return (NULL);
+       }
+       leadsize = ALIGNMENT_CEILING((uintptr_t)node->addr, alignment) -
+           (uintptr_t)node->addr;
+       assert(node->size >= leadsize + size);
+       trailsize = node->size - leadsize - size;
+       ret = (void *)((uintptr_t)node->addr + leadsize);
+       /* Remove node from the tree. */
+       extent_tree_szad_remove(&chunks_szad, node);
+       extent_tree_ad_remove(&chunks_ad, node);
+       if (leadsize != 0) {
+               /* Insert the leading space as a smaller chunk. */
+               node->size = leadsize;
+               extent_tree_szad_insert(&chunks_szad, node);
+               extent_tree_ad_insert(&chunks_ad, node);
+               node = NULL;
+       }
+       if (trailsize != 0) {
+               /* Insert the trailing space as a smaller chunk. */
+               if (node == NULL) {
+                       /*
+                        * An additional node is required, but
+                        * base_node_alloc() can cause a new base chunk to be
+                        * allocated.  Drop chunks_mtx in order to avoid
+                        * deadlock, and if node allocation fails, deallocate
+                        * the result before returning an error.
+                        */
+                       malloc_mutex_unlock(&chunks_mtx);
+                       node = base_node_alloc();
+                       if (node == NULL) {
+                               chunk_dealloc(ret, size, true);
+                               return (NULL);
+                       }
+                       malloc_mutex_lock(&chunks_mtx);
+               }
+               node->addr = (void *)((uintptr_t)(ret) + size);
+               node->size = trailsize;
+               extent_tree_szad_insert(&chunks_szad, node);
+               extent_tree_ad_insert(&chunks_ad, node);
+               node = NULL;
+       }
+       malloc_mutex_unlock(&chunks_mtx);
+
+       if (node != NULL)
+               base_node_dealloc(node);
+#ifdef JEMALLOC_PURGE_MADVISE_DONTNEED
+       /* Pages are zeroed as a side effect of pages_purge(). */
+       *zero = true;
+#else
+       if (*zero) {
+               VALGRIND_MAKE_MEM_UNDEFINED(ret, size);
+               memset(ret, 0, size);
+       }
+#endif
+       return (ret);
+}

 
 /*
  * If the caller specifies (*zero == false), it is still possible to receive
 
 /*
  * If the caller specifies (*zero == false), it is still possible to receive


@@ -34,81 +128,140 @@ size_t            arena_maxclass; /* Max size class for arenas. */
  * advantage of them if they are returned.
  */
 void *
  * advantage of them if they are returned.
  */
 void *

-chunk_alloc(size_t size, bool base, bool *zero)
+chunk_alloc(size_t size, size_t alignment, bool base, bool *zero)

 {
        void *ret;
 
        assert(size != 0);
        assert((size & chunksize_mask) == 0);
 {
        void *ret;
 
        assert(size != 0);
        assert((size & chunksize_mask) == 0);

+       assert(alignment != 0);
+       assert((alignment & chunksize_mask) == 0);

 
 

-#ifdef JEMALLOC_SWAP
-       if (swap_enabled) {
-               ret = chunk_alloc_swap(size, zero);
-               if (ret != NULL)
-                       goto RETURN;
-       }
+       ret = chunk_recycle(size, alignment, base, zero);
+       if (ret != NULL)
+               goto label_return;

 
 

-       if (swap_enabled == false || opt_overcommit) {
-#endif
-#ifdef JEMALLOC_DSS
-               ret = chunk_alloc_dss(size, zero);
+       ret = chunk_alloc_mmap(size, alignment, zero);
+       if (ret != NULL)
+               goto label_return;
+
+       if (config_dss) {
+               ret = chunk_alloc_dss(size, alignment, zero);

                if (ret != NULL)
                if (ret != NULL)

-                       goto RETURN;
-#endif
-               ret = chunk_alloc_mmap(size);
-               if (ret != NULL) {
-                       *zero = true;
-                       goto RETURN;
-               }
-#ifdef JEMALLOC_SWAP
+                       goto label_return;

        }
        }

-#endif

 
        /* All strategies for allocation failed. */
        ret = NULL;
 
        /* All strategies for allocation failed. */
        ret = NULL;

-RETURN:
-#ifdef JEMALLOC_IVSALLOC
-       if (base == false && ret != NULL) {
+label_return:
+       if (config_ivsalloc && base == false && ret != NULL) {

                if (rtree_set(chunks_rtree, (uintptr_t)ret, ret)) {
                if (rtree_set(chunks_rtree, (uintptr_t)ret, ret)) {

-                       chunk_dealloc(ret, size);
+                       chunk_dealloc(ret, size, true);

                        return (NULL);
                }
        }
                        return (NULL);
                }
        }

-#endif
-#if (defined(JEMALLOC_STATS) || defined(JEMALLOC_PROF))
-       if (ret != NULL) {
-#  ifdef JEMALLOC_PROF
+       if ((config_stats || config_prof) && ret != NULL) {

                bool gdump;
                bool gdump;

-#  endif

                malloc_mutex_lock(&chunks_mtx);
                malloc_mutex_lock(&chunks_mtx);

-#  ifdef JEMALLOC_STATS
-               stats_chunks.nchunks += (size / chunksize);
-#  endif
+               if (config_stats)
+                       stats_chunks.nchunks += (size / chunksize);

                stats_chunks.curchunks += (size / chunksize);
                if (stats_chunks.curchunks > stats_chunks.highchunks) {
                        stats_chunks.highchunks = stats_chunks.curchunks;
                stats_chunks.curchunks += (size / chunksize);
                if (stats_chunks.curchunks > stats_chunks.highchunks) {
                        stats_chunks.highchunks = stats_chunks.curchunks;

-#  ifdef JEMALLOC_PROF
-                       gdump = true;
-#  endif
-               }
-#  ifdef JEMALLOC_PROF
-               else
+                       if (config_prof)
+                               gdump = true;
+               } else if (config_prof)

                        gdump = false;
                        gdump = false;

-#  endif

                malloc_mutex_unlock(&chunks_mtx);
                malloc_mutex_unlock(&chunks_mtx);

-#  ifdef JEMALLOC_PROF
-               if (opt_prof && opt_prof_gdump && gdump)
+               if (config_prof && opt_prof && opt_prof_gdump && gdump)

                        prof_gdump();
                        prof_gdump();

-#  endif

        }
        }

-#endif
+       if (config_debug && *zero && ret != NULL) {
+               size_t i;
+               size_t *p = (size_t *)(uintptr_t)ret;

 
 

+               VALGRIND_MAKE_MEM_DEFINED(ret, size);
+               for (i = 0; i < size / sizeof(size_t); i++)
+                       assert(p[i] == 0);
+       }

        assert(CHUNK_ADDR2BASE(ret) == ret);
        return (ret);
 }
 
        assert(CHUNK_ADDR2BASE(ret) == ret);
        return (ret);
 }
 

+static void
+chunk_record(void *chunk, size_t size)
+{
+       extent_node_t *xnode, *node, *prev, key;
+
+       pages_purge(chunk, size);
+
+       /*
+        * Allocate a node before acquiring chunks_mtx even though it might not
+        * be needed, because base_node_alloc() may cause a new base chunk to
+        * be allocated, which could cause deadlock if chunks_mtx were already
+        * held.
+        */
+       xnode = base_node_alloc();
+
+       malloc_mutex_lock(&chunks_mtx);
+       key.addr = (void *)((uintptr_t)chunk + size);
+       node = extent_tree_ad_nsearch(&chunks_ad, &key);
+       /* Try to coalesce forward. */
+       if (node != NULL && node->addr == key.addr) {
+               /*
+                * Coalesce chunk with the following address range.  This does
+                * not change the position within chunks_ad, so only
+                * remove/insert from/into chunks_szad.
+                */
+               extent_tree_szad_remove(&chunks_szad, node);
+               node->addr = chunk;
+               node->size += size;
+               extent_tree_szad_insert(&chunks_szad, node);
+               if (xnode != NULL)
+                       base_node_dealloc(xnode);
+       } else {
+               /* Coalescing forward failed, so insert a new node. */
+               if (xnode == NULL) {
+                       /*
+                        * base_node_alloc() failed, which is an exceedingly
+                        * unlikely failure.  Leak chunk; its pages have
+                        * already been purged, so this is only a virtual
+                        * memory leak.
+                        */
+                       malloc_mutex_unlock(&chunks_mtx);
+                       return;
+               }
+               node = xnode;
+               node->addr = chunk;
+               node->size = size;
+               extent_tree_ad_insert(&chunks_ad, node);
+               extent_tree_szad_insert(&chunks_szad, node);
+       }
+
+       /* Try to coalesce backward. */
+       prev = extent_tree_ad_prev(&chunks_ad, node);
+       if (prev != NULL && (void *)((uintptr_t)prev->addr + prev->size) ==
+           chunk) {
+               /*
+                * Coalesce chunk with the previous address range.  This does
+                * not change the position within chunks_ad, so only
+                * remove/insert node from/into chunks_szad.
+                */
+               extent_tree_szad_remove(&chunks_szad, prev);
+               extent_tree_ad_remove(&chunks_ad, prev);
+
+               extent_tree_szad_remove(&chunks_szad, node);
+               node->addr = prev->addr;
+               node->size += prev->size;
+               extent_tree_szad_insert(&chunks_szad, node);
+
+               base_node_dealloc(prev);
+       }
+       malloc_mutex_unlock(&chunks_mtx);
+}
+

 void
 void

-chunk_dealloc(void *chunk, size_t size)
+chunk_dealloc(void *chunk, size_t size, bool unmap)

 {
 
        assert(chunk != NULL);
 {
 
        assert(chunk != NULL);


@@ -116,24 +269,19 @@ chunk_dealloc(void *chunk, size_t size)
        assert(size != 0);
        assert((size & chunksize_mask) == 0);
 
        assert(size != 0);
        assert((size & chunksize_mask) == 0);
 

-#ifdef JEMALLOC_IVSALLOC
-       rtree_set(chunks_rtree, (uintptr_t)chunk, NULL);
-#endif
-#if (defined(JEMALLOC_STATS) || defined(JEMALLOC_PROF))
-       malloc_mutex_lock(&chunks_mtx);
-       stats_chunks.curchunks -= (size / chunksize);
-       malloc_mutex_unlock(&chunks_mtx);
-#endif
+       if (config_ivsalloc)
+               rtree_set(chunks_rtree, (uintptr_t)chunk, NULL);
+       if (config_stats || config_prof) {
+               malloc_mutex_lock(&chunks_mtx);
+               stats_chunks.curchunks -= (size / chunksize);
+               malloc_mutex_unlock(&chunks_mtx);
+       }

 
 

-#ifdef JEMALLOC_SWAP
-       if (swap_enabled && chunk_dealloc_swap(chunk, size) == false)
-               return;
-#endif
-#ifdef JEMALLOC_DSS
-       if (chunk_dealloc_dss(chunk, size) == false)
-               return;
-#endif
-       chunk_dealloc_mmap(chunk, size);
+       if (unmap) {
+               if ((config_dss && chunk_in_dss(chunk)) ||
+                   chunk_dealloc_mmap(chunk, size))
+                       chunk_record(chunk, size);
+       }

 }
 
 bool
 }
 
 bool


@@ -142,30 +290,25 @@ chunk_boot(void)
 
        /* Set variables according to the value of opt_lg_chunk. */
        chunksize = (ZU(1) << opt_lg_chunk);
 
        /* Set variables according to the value of opt_lg_chunk. */
        chunksize = (ZU(1) << opt_lg_chunk);

-       assert(chunksize >= PAGE_SIZE);
+       assert(chunksize >= PAGE);

        chunksize_mask = chunksize - 1;
        chunksize_mask = chunksize - 1;

-       chunk_npages = (chunksize >> PAGE_SHIFT);
+       chunk_npages = (chunksize >> LG_PAGE);

 
 

-#if (defined(JEMALLOC_STATS) || defined(JEMALLOC_PROF))
-       if (malloc_mutex_init(&chunks_mtx))
-               return (true);
-       memset(&stats_chunks, 0, sizeof(chunk_stats_t));
-#endif
-#ifdef JEMALLOC_SWAP
-       if (chunk_swap_boot())
-               return (true);
-#endif
-       if (chunk_mmap_boot())
-               return (true);
-#ifdef JEMALLOC_DSS
-       if (chunk_dss_boot())
-               return (true);
-#endif
-#ifdef JEMALLOC_IVSALLOC
-       chunks_rtree = rtree_new((ZU(1) << (LG_SIZEOF_PTR+3)) - opt_lg_chunk);
-       if (chunks_rtree == NULL)
+       if (config_stats || config_prof) {
+               if (malloc_mutex_init(&chunks_mtx))
+                       return (true);
+               memset(&stats_chunks, 0, sizeof(chunk_stats_t));
+       }
+       if (config_dss && chunk_dss_boot())

                return (true);
                return (true);

-#endif
+       extent_tree_szad_new(&chunks_szad);
+       extent_tree_ad_new(&chunks_ad);
+       if (config_ivsalloc) {
+               chunks_rtree = rtree_new((ZU(1) << (LG_SIZEOF_PTR+3)) -
+                   opt_lg_chunk);
+               if (chunks_rtree == NULL)
+                       return (true);
+       }

 
        return (false);
 }
 
        return (false);
 }