deps/jemalloc/src/chunk_dss.c

   1 #define JEMALLOC_CHUNK_DSS_C_
   2 #include "jemalloc/internal/jemalloc_internal.h"
   3 #ifdef JEMALLOC_DSS
   4 /******************************************************************************/
   5 /* Data. */
   6
   7 malloc_mutex_t  dss_mtx;
   8
   9 /* Base address of the DSS. */
  10 static void     *dss_base;
  11 /* Current end of the DSS, or ((void *)-1) if the DSS is exhausted. */
  12 static void     *dss_prev;
  13 /* Current upper limit on DSS addresses. */
  14 static void     *dss_max;
  15
  16 /*
  17  * Trees of chunks that were previously allocated (trees differ only in node
  18  * ordering).  These are used when allocating chunks, in an attempt to re-use
  19  * address space.  Depending on function, different tree orderings are needed,
  20  * which is why there are two trees with the same contents.
  21  */
  22 static extent_tree_t    dss_chunks_szad;
  23 static extent_tree_t    dss_chunks_ad;
  24
  25 /******************************************************************************/
  26 /* Function prototypes for non-inline static functions. */
  27
  28 static void     *chunk_recycle_dss(size_t size, bool *zero);
  29 static extent_node_t *chunk_dealloc_dss_record(void *chunk, size_t size);
  30
  31 /******************************************************************************/
  32
  33 static void *
  34 chunk_recycle_dss(size_t size, bool *zero)
  35 {
  36         extent_node_t *node, key;
  37
  38         key.addr = NULL;
  39         key.size = size;
  40         malloc_mutex_lock(&dss_mtx);
  41         node = extent_tree_szad_nsearch(&dss_chunks_szad, &key);
  42         if (node != NULL) {
  43                 void *ret = node->addr;
  44
  45                 /* Remove node from the tree. */
  46                 extent_tree_szad_remove(&dss_chunks_szad, node);
  47                 if (node->size == size) {
  48                         extent_tree_ad_remove(&dss_chunks_ad, node);
  49                         base_node_dealloc(node);
  50                 } else {
  51                         /*
  52                          * Insert the remainder of node's address range as a
  53                          * smaller chunk.  Its position within dss_chunks_ad
  54                          * does not change.
  55                          */
  56                         assert(node->size > size);
  57                         node->addr = (void *)((uintptr_t)node->addr + size);
  58                         node->size -= size;
  59                         extent_tree_szad_insert(&dss_chunks_szad, node);
  60                 }
  61                 malloc_mutex_unlock(&dss_mtx);
  62
  63                 if (*zero)
  64                         memset(ret, 0, size);
  65                 return (ret);
  66         }
  67         malloc_mutex_unlock(&dss_mtx);
  68
  69         return (NULL);
  70 }
  71
  72 void *
  73 chunk_alloc_dss(size_t size, bool *zero)
  74 {
  75         void *ret;
  76
  77         ret = chunk_recycle_dss(size, zero);
  78         if (ret != NULL)
  79                 return (ret);
  80
  81         /*
  82          * sbrk() uses a signed increment argument, so take care not to
  83          * interpret a huge allocation request as a negative increment.
  84          */
  85         if ((intptr_t)size < 0)
  86                 return (NULL);
  87
  88         malloc_mutex_lock(&dss_mtx);
  89         if (dss_prev != (void *)-1) {
  90                 intptr_t incr;
  91
  92                 /*
  93                  * The loop is necessary to recover from races with other
  94                  * threads that are using the DSS for something other than
  95                  * malloc.
  96                  */
  97                 do {
  98                         /* Get the current end of the DSS. */
  99                         dss_max = sbrk(0);
 100
 101                         /*
 102                          * Calculate how much padding is necessary to
 103                          * chunk-align the end of the DSS.
 104                          */
 105                         incr = (intptr_t)size
 106                             - (intptr_t)CHUNK_ADDR2OFFSET(dss_max);
 107                         if (incr == (intptr_t)size)
 108                                 ret = dss_max;
 109                         else {
 110                                 ret = (void *)((intptr_t)dss_max + incr);
 111                                 incr += size;
 112                         }
 113
 114                         dss_prev = sbrk(incr);
 115                         if (dss_prev == dss_max) {
 116                                 /* Success. */
 117                                 dss_max = (void *)((intptr_t)dss_prev + incr);
 118                                 malloc_mutex_unlock(&dss_mtx);
 119                                 *zero = true;
 120                                 return (ret);
 121                         }
 122                 } while (dss_prev != (void *)-1);
 123         }
 124         malloc_mutex_unlock(&dss_mtx);
 125
 126         return (NULL);
 127 }
 128
 129 static extent_node_t *
 130 chunk_dealloc_dss_record(void *chunk, size_t size)
 131 {
 132         extent_node_t *xnode, *node, *prev, key;
 133
 134         xnode = NULL;
 135         while (true) {
 136                 key.addr = (void *)((uintptr_t)chunk + size);
 137                 node = extent_tree_ad_nsearch(&dss_chunks_ad, &key);
 138                 /* Try to coalesce forward. */
 139                 if (node != NULL && node->addr == key.addr) {
 140                         /*
 141                          * Coalesce chunk with the following address range.
 142                          * This does not change the position within
 143                          * dss_chunks_ad, so only remove/insert from/into
 144                          * dss_chunks_szad.
 145                          */
 146                         extent_tree_szad_remove(&dss_chunks_szad, node);
 147                         node->addr = chunk;
 148                         node->size += size;
 149                         extent_tree_szad_insert(&dss_chunks_szad, node);
 150                         break;
 151                 } else if (xnode == NULL) {
 152                         /*
 153                          * It is possible that base_node_alloc() will cause a
 154                          * new base chunk to be allocated, so take care not to
 155                          * deadlock on dss_mtx, and recover if another thread
 156                          * deallocates an adjacent chunk while this one is busy
 157                          * allocating xnode.
 158                          */
 159                         malloc_mutex_unlock(&dss_mtx);
 160                         xnode = base_node_alloc();
 161                         malloc_mutex_lock(&dss_mtx);
 162                         if (xnode == NULL)
 163                                 return (NULL);
 164                 } else {
 165                         /* Coalescing forward failed, so insert a new node. */
 166                         node = xnode;
 167                         xnode = NULL;
 168                         node->addr = chunk;
 169                         node->size = size;
 170                         extent_tree_ad_insert(&dss_chunks_ad, node);
 171                         extent_tree_szad_insert(&dss_chunks_szad, node);
 172                         break;
 173                 }
 174         }
 175         /* Discard xnode if it ended up unused do to a race. */
 176         if (xnode != NULL)
 177                 base_node_dealloc(xnode);
 178
 179         /* Try to coalesce backward. */
 180         prev = extent_tree_ad_prev(&dss_chunks_ad, node);
 181         if (prev != NULL && (void *)((uintptr_t)prev->addr + prev->size) ==
 182             chunk) {
 183                 /*
 184                  * Coalesce chunk with the previous address range.  This does
 185                  * not change the position within dss_chunks_ad, so only
 186                  * remove/insert node from/into dss_chunks_szad.
 187                  */
 188                 extent_tree_szad_remove(&dss_chunks_szad, prev);
 189                 extent_tree_ad_remove(&dss_chunks_ad, prev);
 190
 191                 extent_tree_szad_remove(&dss_chunks_szad, node);
 192                 node->addr = prev->addr;
 193                 node->size += prev->size;
 194                 extent_tree_szad_insert(&dss_chunks_szad, node);
 195
 196                 base_node_dealloc(prev);
 197         }
 198
 199         return (node);
 200 }
 201
 202 bool
 203 chunk_in_dss(void *chunk)
 204 {
 205         bool ret;
 206
 207         malloc_mutex_lock(&dss_mtx);
 208         if ((uintptr_t)chunk >= (uintptr_t)dss_base
 209             && (uintptr_t)chunk < (uintptr_t)dss_max)
 210                 ret = true;
 211         else
 212                 ret = false;
 213         malloc_mutex_unlock(&dss_mtx);
 214
 215         return (ret);
 216 }
 217
 218 bool
 219 chunk_dealloc_dss(void *chunk, size_t size)
 220 {
 221         bool ret;
 222
 223         malloc_mutex_lock(&dss_mtx);
 224         if ((uintptr_t)chunk >= (uintptr_t)dss_base
 225             && (uintptr_t)chunk < (uintptr_t)dss_max) {
 226                 extent_node_t *node;
 227
 228                 /* Try to coalesce with other unused chunks. */
 229                 node = chunk_dealloc_dss_record(chunk, size);
 230                 if (node != NULL) {
 231                         chunk = node->addr;
 232                         size = node->size;
 233                 }
 234
 235                 /* Get the current end of the DSS. */
 236                 dss_max = sbrk(0);
 237
 238                 /*
 239                  * Try to shrink the DSS if this chunk is at the end of the
 240                  * DSS.  The sbrk() call here is subject to a race condition
 241                  * with threads that use brk(2) or sbrk(2) directly, but the
 242                  * alternative would be to leak memory for the sake of poorly
 243                  * designed multi-threaded programs.
 244                  */
 245                 if ((void *)((uintptr_t)chunk + size) == dss_max
 246                     && (dss_prev = sbrk(-(intptr_t)size)) == dss_max) {
 247                         /* Success. */
 248                         dss_max = (void *)((intptr_t)dss_prev - (intptr_t)size);
 249
 250                         if (node != NULL) {
 251                                 extent_tree_szad_remove(&dss_chunks_szad, node);
 252                                 extent_tree_ad_remove(&dss_chunks_ad, node);
 253                                 base_node_dealloc(node);
 254                         }
 255                 } else
 256                         madvise(chunk, size, MADV_DONTNEED);
 257
 258                 ret = false;
 259                 goto RETURN;
 260         }
 261
 262         ret = true;
 263 RETURN:
 264         malloc_mutex_unlock(&dss_mtx);
 265         return (ret);
 266 }
 267
 268 bool
 269 chunk_dss_boot(void)
 270 {
 271
 272         if (malloc_mutex_init(&dss_mtx))
 273                 return (true);
 274         dss_base = sbrk(0);
 275         dss_prev = dss_base;
 276         dss_max = dss_base;
 277         extent_tree_szad_new(&dss_chunks_szad);
 278         extent_tree_ad_new(&dss_chunks_ad);
 279
 280         return (false);
 281 }
 282
 283 /******************************************************************************/
 284 #endif /* JEMALLOC_DSS */