mono/metadata/mempool.c

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