mono/metadata/mempool.c

   1 /**
   2  * \file
   3  * efficient memory allocation
   4  *
   5  * MonoMemPool is for fast allocation of memory. We free
   6  * all memory when the pool is destroyed.
   7  *
   8  * Author:
   9  *   Dietmar Maurer (dietmar@ximian.com)
  10  *
  11  * Copyright 2001-2003 Ximian, Inc (http://www.ximian.com)
  12  * Copyright 2004-2009 Novell, Inc (http://www.novell.com)
  13  * Copyright 2011 Xamarin Inc. (http://www.xamarin.com)
  14  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
  15  */
  16
  17 #include <config.h>
  18 #include <glib.h>
  19 #include <string.h>
  20
  21 #include "mempool.h"
  22 #include "mempool-internals.h"
  23 #include "utils/unlocked.h"
  24
  25 /*
  26  * MonoMemPool is for fast allocation of memory. We free
  27  * all memory when the pool is destroyed.
  28  */
  29
  30 #define MEM_ALIGN 8
  31 #define ALIGN_SIZE(s)   (((s) + MEM_ALIGN - 1) & ~(MEM_ALIGN - 1))
  32
  33 // Size of memory at start of mempool reserved for header
  34 #define SIZEOF_MEM_POOL (ALIGN_SIZE (sizeof (MonoMemPool)))
  35
  36 #if MONO_SMALL_CONFIG
  37 #define MONO_MEMPOOL_PAGESIZE 4096
  38 #define MONO_MEMPOOL_MINSIZE 256
  39 #else
  40 #define MONO_MEMPOOL_PAGESIZE 8192
  41 #define MONO_MEMPOOL_MINSIZE 512
  42 #endif
  43
  44 // The --with-malloc-mempools debug-build flag causes mempools to be allocated in single-element blocks, so tools like Valgrind can run better.
  45 #if USE_MALLOC_FOR_MEMPOOLS
  46 #define INDIVIDUAL_ALLOCATIONS
  47 #define MONO_MEMPOOL_PREFER_INDIVIDUAL_ALLOCATION_SIZE 0
  48 #else
  49 #define MONO_MEMPOOL_PREFER_INDIVIDUAL_ALLOCATION_SIZE MONO_MEMPOOL_PAGESIZE
  50 #endif
  51
  52 #ifndef G_LIKELY
  53 #define G_LIKELY(a) (a)
  54 #define G_UNLIKELY(a) (a)
  55 #endif
  56
  57 // A mempool is a linked list of memory blocks, each of which begins with this header structure.
  58 // The initial block in the linked list is special, and tracks additional information.
  59 struct _MonoMemPool {
  60         // Next block after this one in linked list
  61         MonoMemPool *next;
  62
  63         // Size of this memory block only
  64         guint32 size;
  65
  66         // Used in "initial block" only: Beginning of current free space in mempool (may be in some block other than the first one)
  67         guint8 *pos;
  68
  69         // Used in "initial block" only: End of current free space in mempool (ie, the first byte following the end of usable space)
  70         guint8 *end;
  71
  72         union {
  73                 // Unused: Imposing floating point memory rules on _MonoMemPool's final field ensures proper alignment of whole header struct
  74                 double pad;
  75
  76                 // Used in "initial block" only: Number of bytes so far allocated (whether used or not) in the whole mempool
  77                 guint32 allocated;
  78         } d;
  79 };
  80
  81 static gint64 total_bytes_allocated = 0;
  82
  83 /**
  84  * mono_mempool_new:
  85  *
  86  * Returns: a new memory pool.
  87  */
  88 MonoMemPool *
  89 mono_mempool_new (void)
  90 {
  91         return mono_mempool_new_size (MONO_MEMPOOL_PAGESIZE);
  92 }
  93
  94 /**
  95  * mono_mempool_new_size:
  96  * \param initial_size the amount of memory to initially reserve for the memory pool.
  97  * \returns a new memory pool with a specific initial memory reservation.
  98  */
  99 MonoMemPool *
 100 mono_mempool_new_size (int initial_size)
 101 {
 102         MonoMemPool *pool;
 103
 104 #ifdef INDIVIDUAL_ALLOCATIONS
 105         // In individual allocation mode, create initial block with zero storage space.
 106         initial_size = SIZEOF_MEM_POOL;
 107 #else
 108         if (initial_size < MONO_MEMPOOL_MINSIZE)
 109                 initial_size = MONO_MEMPOOL_MINSIZE;
 110 #endif
 111
 112         pool = (MonoMemPool *)g_malloc (initial_size);
 113
 114         pool->next = NULL;
 115         pool->pos = (guint8*)pool + SIZEOF_MEM_POOL; // Start after header
 116         pool->end = (guint8*)pool + initial_size;    // End at end of allocated space
 117         pool->d.allocated = pool->size = initial_size;
 118         UnlockedAdd64 (&total_bytes_allocated, initial_size);
 119         return pool;
 120 }
 121
 122 /**
 123  * mono_mempool_destroy:
 124  * \param pool the memory pool to destroy
 125  *
 126  * Free all memory associated with this pool.
 127  */
 128 void
 129 mono_mempool_destroy (MonoMemPool *pool)
 130 {
 131         MonoMemPool *p, *n;
 132
 133         UnlockedSubtract64 (&total_bytes_allocated, pool->d.allocated);
 134
 135         p = pool;
 136         while (p) {
 137                 n = p->next;
 138                 g_free (p);
 139                 p = n;
 140         }
 141 }
 142
 143 /**
 144  * mono_mempool_invalidate:
 145  * \param pool the memory pool to invalidate
 146  *
 147  * Fill the memory associated with this pool to 0x2a (42). Useful for debugging.
 148  */
 149 void
 150 mono_mempool_invalidate (MonoMemPool *pool)
 151 {
 152         MonoMemPool *p, *n;
 153
 154         p = pool;
 155         while (p) {
 156                 n = p->next;
 157                 memset (p, 42, p->size);
 158                 p = n;
 159         }
 160 }
 161
 162 /**
 163  * mono_mempool_stats:
 164  * \param pool the memory pool we need stats for
 165  *
 166  * Print a few stats about the mempool:
 167  * - Total memory allocated (malloced) by mem pool
 168  * - Number of chunks/blocks memory is allocated in
 169  * - How much memory is available to dispense before a new malloc must occur?
 170  */
 171 void
 172 mono_mempool_stats (MonoMemPool *pool)
 173 {
 174         MonoMemPool *p;
 175         int count = 0;
 176         guint32 still_free;
 177
 178         p = pool;
 179         while (p) {
 180                 p = p->next;
 181                 count++;
 182         }
 183         if (pool) {
 184                 still_free = pool->end - pool->pos;
 185                 g_print ("Mempool %p stats:\n", pool);
 186                 g_print ("Total mem allocated: %d\n", pool->d.allocated);
 187                 g_print ("Num chunks: %d\n", count);
 188                 g_print ("Free memory: %d\n", still_free);
 189         }
 190 }
 191
 192 #ifdef TRACE_ALLOCATIONS
 193 #include <execinfo.h>
 194 #include "metadata/appdomain.h"
 195 #include "metadata/metadata-internals.h"
 196
 197 static mono_mutex_t mempool_tracing_lock;
 198 #define BACKTRACE_DEPTH 7
 199 static void
 200 mono_backtrace (int size)
 201 {
 202         void *array[BACKTRACE_DEPTH];
 203         char **names;
 204         int i, symbols;
 205         static gboolean inited;
 206
 207         if (!inited) {
 208                 mono_os_mutex_init_recursive (&mempool_tracing_lock);
 209                 inited = TRUE;
 210         }
 211
 212         mono_os_mutex_lock (&mempool_tracing_lock);
 213         g_print ("Allocating %d bytes\n", size);
 214         MONO_ENTER_GC_SAFE;
 215         symbols = backtrace (array, BACKTRACE_DEPTH);
 216         names = backtrace_symbols (array, symbols);
 217         MONO_EXIT_GC_SAFE;
 218         for (i = 1; i < symbols; ++i) {
 219                 g_print ("\t%s\n", names [i]);
 220         }
 221         g_free (names);
 222         mono_os_mutex_unlock (&mempool_tracing_lock);
 223 }
 224
 225 #endif
 226
 227 /**
 228  * get_next_size:
 229  * @pool: the memory pool to use
 230  * @size: size of the memory entity we are trying to allocate
 231  *
 232  * A mempool is growing; give a recommended size for the next block.
 233  * Each block in a mempool should be about 150% bigger than the previous one,
 234  * or bigger if it is necessary to include the new entity.
 235  *
 236  * Returns: the recommended size.
 237  */
 238 static guint
 239 get_next_size (MonoMemPool *pool, int size)
 240 {
 241         int target = pool->next? pool->next->size: pool->size;
 242         size += SIZEOF_MEM_POOL;
 243         /* increase the size */
 244         target += target / 2;
 245         while (target < size) {
 246                 target += target / 2;
 247         }
 248         if (target > MONO_MEMPOOL_PAGESIZE && size <= MONO_MEMPOOL_PAGESIZE)
 249                 target = MONO_MEMPOOL_PAGESIZE;
 250         return target;
 251 }
 252
 253 /**
 254  * mono_mempool_alloc:
 255  * \param pool the memory pool to use
 256  * \param size size of the memory block
 257  *
 258  * Allocates a new block of memory in \p pool .
 259  *
 260  * \returns the address of a newly allocated memory block.
 261  */
 262 gpointer
 263 mono_mempool_alloc (MonoMemPool *pool, guint size)
 264 {
 265         gpointer rval = pool->pos; // Return value
 266
 267         // Normal case: Just bump up pos pointer and we are done
 268         size = ALIGN_SIZE (size);
 269         pool->pos = (guint8*)rval + size;
 270
 271 #ifdef TRACE_ALLOCATIONS
 272         if (pool == mono_get_corlib ()->mempool) {
 273                 mono_backtrace (size);
 274         }
 275 #endif
 276
 277         // If we have just overflowed the current block, we need to back up and try again.
 278         if (G_UNLIKELY (pool->pos >= pool->end)) {
 279                 pool->pos -= size;  // Back out
 280
 281                 // For large objects, allocate the object into its own block.
 282                 // (In individual allocation mode, the constant will be 0 and this path will always be taken)
 283                 if (size >= MONO_MEMPOOL_PREFER_INDIVIDUAL_ALLOCATION_SIZE) {
 284                         guint new_size = SIZEOF_MEM_POOL + size;
 285                         MonoMemPool *np = (MonoMemPool *)g_malloc (new_size);
 286
 287                         np->next = pool->next;
 288                         np->size = new_size;
 289                         pool->next = np;
 290                         pool->d.allocated += new_size;
 291                         UnlockedAdd64 (&total_bytes_allocated, new_size);
 292
 293                         rval = (guint8*)np + SIZEOF_MEM_POOL;
 294                 } else {
 295                         // Notice: any unused memory at the end of the old head becomes simply abandoned in this case until the mempool is freed (see Bugzilla #35136)
 296                         guint new_size = get_next_size (pool, size);
 297                         MonoMemPool *np = (MonoMemPool *)g_malloc (new_size);
 298
 299                         np->next = pool->next;
 300                         np->size = new_size;
 301                         pool->next = np;
 302                         pool->pos = (guint8*)np + SIZEOF_MEM_POOL;
 303                         pool->end = (guint8*)np + new_size;
 304                         pool->d.allocated += new_size;
 305                         UnlockedAdd64 (&total_bytes_allocated, new_size);
 306
 307                         rval = pool->pos;
 308                         pool->pos += size;
 309                 }
 310         }
 311
 312         return rval;
 313 }
 314
 315 /**
 316  * mono_mempool_alloc0:
 317  *
 318  * same as \c mono_mempool_alloc, but fills memory with zero.
 319  */
 320 gpointer
 321 mono_mempool_alloc0 (MonoMemPool *pool, guint size)
 322 {
 323         gpointer rval;
 324
 325         // For the fast path, repeat the first few lines of mono_mempool_alloc
 326         size = ALIGN_SIZE (size);
 327         rval = pool->pos;
 328         pool->pos = (guint8*)rval + size;
 329
 330         // If that doesn't work fall back on mono_mempool_alloc to handle new chunk allocation
 331         if (G_UNLIKELY (pool->pos >= pool->end)) {
 332                 rval = mono_mempool_alloc (pool, size);
 333         }
 334 #ifdef TRACE_ALLOCATIONS
 335         else if (pool == mono_get_corlib ()->mempool) {
 336                 mono_backtrace (size);
 337         }
 338 #endif
 339
 340         memset (rval, 0, size);
 341         return rval;
 342 }
 343
 344 /**
 345  * mono_mempool_contains_addr:
 346  *
 347  * Determines whether \p addr is inside the memory used by the mempool.
 348  */
 349 gboolean
 350 mono_mempool_contains_addr (MonoMemPool *pool,
 351                                                         gpointer addr)
 352 {
 353         MonoMemPool *p = pool;
 354
 355         while (p) {
 356                 if (addr >= (gpointer)p && addr < (gpointer)((guint8*)p + p->size))
 357                         return TRUE;
 358                 p = p->next;
 359         }
 360
 361         return FALSE;
 362 }
 363
 364 /**
 365  * mono_mempool_strdup:
 366  *
 367  * Same as strdup, but allocates memory from the mempool.
 368  * Returns: a pointer to the newly allocated string data inside the mempool.
 369  */
 370 char*
 371 mono_mempool_strdup (MonoMemPool *pool,
 372                                          const char *s)
 373 {
 374         int l;
 375         char *res;
 376
 377         if (s == NULL)
 378                 return NULL;
 379
 380         l = strlen (s);
 381         res = (char *)mono_mempool_alloc (pool, l + 1);
 382         memcpy (res, s, l + 1);
 383
 384         return res;
 385 }
 386
 387 char*
 388 mono_mempool_strdup_vprintf (MonoMemPool *pool, const char *format, va_list args)
 389 {
 390         size_t buflen;
 391         char *buf;
 392         va_list args2;
 393         va_copy (args2, args);
 394         int len = vsnprintf (NULL, 0, format, args2);
 395         va_end (args2);
 396
 397         if (len >= 0 && (buf = (char*)mono_mempool_alloc (pool, (buflen = (size_t) (len + 1)))) != NULL) {
 398                 vsnprintf (buf, buflen, format, args);
 399         } else {
 400                 buf = NULL;
 401         }
 402         return buf;
 403 }
 404
 405 char*
 406 mono_mempool_strdup_printf (MonoMemPool *pool, const char *format, ...)
 407 {
 408         char *buf;
 409         va_list args;
 410         va_start (args, format);
 411         buf = mono_mempool_strdup_vprintf (pool, format, args);
 412         va_end (args);
 413         return buf;
 414 }
 415
 416 /**
 417  * mono_mempool_get_allocated:
 418  *
 419  * Return the amount of memory allocated for this mempool.
 420  */
 421 guint32
 422 mono_mempool_get_allocated (MonoMemPool *pool)
 423 {
 424         return pool->d.allocated;
 425 }
 426
 427 /**
 428  * mono_mempool_get_bytes_allocated:
 429  *
 430  * Return the number of bytes currently allocated for mempools.
 431  */
 432 long
 433 mono_mempool_get_bytes_allocated (void)
 434 {
 435         return UnlockedRead64 (&total_bytes_allocated);
 436 }