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/mono-compiler.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 long 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  *
  97  *   clang's ThreadSanitizer detects races of total_bytes_allocated and pool->d.allocated throughout the functions
  98  *     * mono_mempool_alloc
  99  *     * mono_mempool_new_size
 100  *     * mono_mempool_destroy
 101  *   while these races could lead to wrong values, total_bytes_allocated is just used for debugging / reporting and since
 102  *   the mempool.c functions are called quite often, a discussion led the the conclusion of ignoring these races:
 103  *   https://bugzilla.xamarin.com/show_bug.cgi?id=57936
 104  *
 105  * \param initial_size the amount of memory to initially reserve for the memory pool.
 106  * \returns a new memory pool with a specific initial memory reservation.
 107  */
 108 MONO_NO_SANITIZE_THREAD
 109 MonoMemPool *
 110 mono_mempool_new_size (int initial_size)
 111 {
 112         MonoMemPool *pool;
 113
 114 #ifdef INDIVIDUAL_ALLOCATIONS
 115         // In individual allocation mode, create initial block with zero storage space.
 116         initial_size = SIZEOF_MEM_POOL;
 117 #else
 118         if (initial_size < MONO_MEMPOOL_MINSIZE)
 119                 initial_size = MONO_MEMPOOL_MINSIZE;
 120 #endif
 121
 122         pool = (MonoMemPool *)g_malloc (initial_size);
 123
 124         pool->next = NULL;
 125         pool->pos = (guint8*)pool + SIZEOF_MEM_POOL; // Start after header
 126         pool->end = (guint8*)pool + initial_size;    // End at end of allocated space
 127         pool->d.allocated = pool->size = initial_size;
 128         total_bytes_allocated += initial_size;
 129         return pool;
 130 }
 131
 132 /**
 133  * mono_mempool_destroy:
 134  *
 135  *   clang's ThreadSanitizer detects races of total_bytes_allocated and pool->d.allocated throughout the functions
 136  *     * mono_mempool_alloc
 137  *     * mono_mempool_new_size
 138  *     * mono_mempool_destroy
 139  *   while these races could lead to wrong values, total_bytes_allocated is just used for debugging / reporting and since
 140  *   the mempool.c functions are called quite often, a discussion led the the conclusion of ignoring these races:
 141  *   https://bugzilla.xamarin.com/show_bug.cgi?id=57936
 142  *
 143  * \param pool the memory pool to destroy
 144  *
 145  * Free all memory associated with this pool.
 146  */
 147 MONO_NO_SANITIZE_THREAD
 148 void
 149 mono_mempool_destroy (MonoMemPool *pool)
 150 {
 151         MonoMemPool *p, *n;
 152
 153         total_bytes_allocated -= pool->d.allocated;
 154
 155         p = pool;
 156         while (p) {
 157                 n = p->next;
 158                 g_free (p);
 159                 p = n;
 160         }
 161 }
 162
 163 /**
 164  * mono_mempool_invalidate:
 165  * \param pool the memory pool to invalidate
 166  *
 167  * Fill the memory associated with this pool to 0x2a (42). Useful for debugging.
 168  */
 169 void
 170 mono_mempool_invalidate (MonoMemPool *pool)
 171 {
 172         MonoMemPool *p, *n;
 173
 174         p = pool;
 175         while (p) {
 176                 n = p->next;
 177                 memset (p, 42, p->size);
 178                 p = n;
 179         }
 180 }
 181
 182 /**
 183  * mono_mempool_stats:
 184  * \param pool the memory pool we need stats for
 185  *
 186  * Print a few stats about the mempool:
 187  * - Total memory allocated (malloced) by mem pool
 188  * - Number of chunks/blocks memory is allocated in
 189  * - How much memory is available to dispense before a new malloc must occur?
 190  */
 191 void
 192 mono_mempool_stats (MonoMemPool *pool)
 193 {
 194         MonoMemPool *p;
 195         int count = 0;
 196         guint32 still_free;
 197
 198         p = pool;
 199         while (p) {
 200                 p = p->next;
 201                 count++;
 202         }
 203         if (pool) {
 204                 still_free = pool->end - pool->pos;
 205                 g_print ("Mempool %p stats:\n", pool);
 206                 g_print ("Total mem allocated: %d\n", pool->d.allocated);
 207                 g_print ("Num chunks: %d\n", count);
 208                 g_print ("Free memory: %d\n", still_free);
 209         }
 210 }
 211
 212 #ifdef TRACE_ALLOCATIONS
 213 #include <execinfo.h>
 214 #include "metadata/appdomain.h"
 215 #include "metadata/metadata-internals.h"
 216
 217 static mono_mutex_t mempool_tracing_lock;
 218 #define BACKTRACE_DEPTH 7
 219 static void
 220 mono_backtrace (int size)
 221 {
 222         void *array[BACKTRACE_DEPTH];
 223         char **names;
 224         int i, symbols;
 225         static gboolean inited;
 226
 227         if (!inited) {
 228                 mono_os_mutex_init_recursive (&mempool_tracing_lock);
 229                 inited = TRUE;
 230         }
 231
 232         mono_os_mutex_lock (&mempool_tracing_lock);
 233         g_print ("Allocating %d bytes\n", size);
 234         MONO_ENTER_GC_SAFE;
 235         symbols = backtrace (array, BACKTRACE_DEPTH);
 236         names = backtrace_symbols (array, symbols);
 237         MONO_EXIT_GC_SAFE;
 238         for (i = 1; i < symbols; ++i) {
 239                 g_print ("\t%s\n", names [i]);
 240         }
 241         g_free (names);
 242         mono_os_mutex_unlock (&mempool_tracing_lock);
 243 }
 244
 245 #endif
 246
 247 /**
 248  * get_next_size:
 249  * @pool: the memory pool to use
 250  * @size: size of the memory entity we are trying to allocate
 251  *
 252  * A mempool is growing; give a recommended size for the next block.
 253  * Each block in a mempool should be about 150% bigger than the previous one,
 254  * or bigger if it is necessary to include the new entity.
 255  *
 256  * Returns: the recommended size.
 257  */
 258 static guint
 259 get_next_size (MonoMemPool *pool, int size)
 260 {
 261         int target = pool->next? pool->next->size: pool->size;
 262         size += SIZEOF_MEM_POOL;
 263         /* increase the size */
 264         target += target / 2;
 265         while (target < size) {
 266                 target += target / 2;
 267         }
 268         if (target > MONO_MEMPOOL_PAGESIZE && size <= MONO_MEMPOOL_PAGESIZE)
 269                 target = MONO_MEMPOOL_PAGESIZE;
 270         return target;
 271 }
 272
 273 /**
 274  * mono_mempool_alloc:
 275  *
 276  *   clang's ThreadSanitizer detects races of total_bytes_allocated and pool->d.allocated throughout the functions
 277  *     * mono_mempool_alloc
 278  *     * mono_mempool_new_size
 279  *     * mono_mempool_destroy
 280  *   while these races could lead to wrong values, total_bytes_allocated is just used for debugging / reporting and since
 281  *   the mempool.c functions are called quite often, a discussion led the the conclusion of ignoring these races:
 282  *   https://bugzilla.xamarin.com/show_bug.cgi?id=57936
 283  *
 284  * \param pool the memory pool to use
 285  * \param size size of the memory block
 286  *
 287  * Allocates a new block of memory in \p pool .
 288  *
 289  * \returns the address of a newly allocated memory block.
 290  */
 291 MONO_NO_SANITIZE_THREAD
 292 gpointer
 293 mono_mempool_alloc (MonoMemPool *pool, guint size)
 294 {
 295         gpointer rval = pool->pos; // Return value
 296
 297         // Normal case: Just bump up pos pointer and we are done
 298         size = ALIGN_SIZE (size);
 299         pool->pos = (guint8*)rval + size;
 300
 301 #ifdef TRACE_ALLOCATIONS
 302         if (pool == mono_get_corlib ()->mempool) {
 303                 mono_backtrace (size);
 304         }
 305 #endif
 306
 307         // If we have just overflowed the current block, we need to back up and try again.
 308         if (G_UNLIKELY (pool->pos >= pool->end)) {
 309                 pool->pos -= size;  // Back out
 310
 311                 // For large objects, allocate the object into its own block.
 312                 // (In individual allocation mode, the constant will be 0 and this path will always be taken)
 313                 if (size >= MONO_MEMPOOL_PREFER_INDIVIDUAL_ALLOCATION_SIZE) {
 314                         guint new_size = SIZEOF_MEM_POOL + size;
 315                         MonoMemPool *np = (MonoMemPool *)g_malloc (new_size);
 316
 317                         np->next = pool->next;
 318                         np->size = new_size;
 319                         pool->next = np;
 320                         pool->d.allocated += new_size;
 321                         total_bytes_allocated += new_size;
 322
 323                         rval = (guint8*)np + SIZEOF_MEM_POOL;
 324                 } else {
 325                         // 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)
 326                         guint new_size = get_next_size (pool, size);
 327                         MonoMemPool *np = (MonoMemPool *)g_malloc (new_size);
 328
 329                         np->next = pool->next;
 330                         np->size = new_size;
 331                         pool->next = np;
 332                         pool->pos = (guint8*)np + SIZEOF_MEM_POOL;
 333                         pool->end = (guint8*)np + new_size;
 334                         pool->d.allocated += new_size;
 335                         total_bytes_allocated += new_size;
 336
 337                         rval = pool->pos;
 338                         pool->pos += size;
 339                 }
 340         }
 341
 342         return rval;
 343 }
 344
 345 /**
 346  * mono_mempool_alloc0:
 347  *
 348  * same as \c mono_mempool_alloc, but fills memory with zero.
 349  */
 350 gpointer
 351 mono_mempool_alloc0 (MonoMemPool *pool, guint size)
 352 {
 353         gpointer rval;
 354
 355         // For the fast path, repeat the first few lines of mono_mempool_alloc
 356         size = ALIGN_SIZE (size);
 357         rval = pool->pos;
 358         pool->pos = (guint8*)rval + size;
 359
 360         // If that doesn't work fall back on mono_mempool_alloc to handle new chunk allocation
 361         if (G_UNLIKELY (pool->pos >= pool->end)) {
 362                 rval = mono_mempool_alloc (pool, size);
 363         }
 364 #ifdef TRACE_ALLOCATIONS
 365         else if (pool == mono_get_corlib ()->mempool) {
 366                 mono_backtrace (size);
 367         }
 368 #endif
 369
 370         memset (rval, 0, size);
 371         return rval;
 372 }
 373
 374 /**
 375  * mono_mempool_contains_addr:
 376  *
 377  * Determines whether \p addr is inside the memory used by the mempool.
 378  */
 379 gboolean
 380 mono_mempool_contains_addr (MonoMemPool *pool,
 381                                                         gpointer addr)
 382 {
 383         MonoMemPool *p = pool;
 384
 385         while (p) {
 386                 if (addr >= (gpointer)p && addr < (gpointer)((guint8*)p + p->size))
 387                         return TRUE;
 388                 p = p->next;
 389         }
 390
 391         return FALSE;
 392 }
 393
 394 /**
 395  * mono_mempool_strdup:
 396  *
 397  * Same as strdup, but allocates memory from the mempool.
 398  * Returns: a pointer to the newly allocated string data inside the mempool.
 399  */
 400 char*
 401 mono_mempool_strdup (MonoMemPool *pool,
 402                                          const char *s)
 403 {
 404         int l;
 405         char *res;
 406
 407         if (s == NULL)
 408                 return NULL;
 409
 410         l = strlen (s);
 411         res = (char *)mono_mempool_alloc (pool, l + 1);
 412         memcpy (res, s, l + 1);
 413
 414         return res;
 415 }
 416
 417 char*
 418 mono_mempool_strdup_vprintf (MonoMemPool *pool, const char *format, va_list args)
 419 {
 420         size_t buflen;
 421         char *buf;
 422         va_list args2;
 423         va_copy (args2, args);
 424         int len = vsnprintf (NULL, 0, format, args2);
 425         va_end (args2);
 426
 427         if (len >= 0 && (buf = (char*)mono_mempool_alloc (pool, (buflen = (size_t) (len + 1)))) != NULL) {
 428                 vsnprintf (buf, buflen, format, args);
 429         } else {
 430                 buf = NULL;
 431         }
 432         return buf;
 433 }
 434
 435 char*
 436 mono_mempool_strdup_printf (MonoMemPool *pool, const char *format, ...)
 437 {
 438         char *buf;
 439         va_list args;
 440         va_start (args, format);
 441         buf = mono_mempool_strdup_vprintf (pool, format, args);
 442         va_end (args);
 443         return buf;
 444 }
 445
 446 /**
 447  * mono_mempool_get_allocated:
 448  *
 449  * Return the amount of memory allocated for this mempool.
 450  */
 451 guint32
 452 mono_mempool_get_allocated (MonoMemPool *pool)
 453 {
 454         return pool->d.allocated;
 455 }
 456
 457 /**
 458  * mono_mempool_get_bytes_allocated:
 459  *
 460  * Return the number of bytes currently allocated for mempools.
 461  */
 462 long
 463 mono_mempool_get_bytes_allocated (void)
 464 {
 465         return total_bytes_allocated;
 466 }