mono/metadata/sgen-internal.c

   1 /*
   2  * sgen-internal.c: Internal lock-free memory allocator.
   3  *
   4  * Copyright (C) 2012 Xamarin Inc
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Library General Public
   8  * License 2.0 as published by the Free Software Foundation;
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Library General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Library General Public
  16  * License 2.0 along with this library; if not, write to the Free
  17  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18  */
  19
  20 #include "config.h"
  21
  22 #ifdef HAVE_SGEN_GC
  23
  24 #include "utils/mono-counters.h"
  25 #include "metadata/sgen-gc.h"
  26 #include "utils/mono-mmap.h"
  27 #include "utils/lock-free-alloc.h"
  28 #include "metadata/sgen-memory-governor.h"
  29
  30 /* keep each size a multiple of ALLOC_ALIGN */
  31 #if SIZEOF_VOID_P == 4
  32 static const int allocator_sizes [] = {
  33            8,   16,   24,   32,   40,   48,   64,   80,
  34           96,  128,  160,  192,  224,  248,  296,  320,
  35          384,  448,  504,  528,  584,  680,  816, 1088,
  36         1360, 2044, 2336, 2728, 3272, 4092, 5456, 8188 };
  37 #else
  38 static const int allocator_sizes [] = {
  39            8,   16,   24,   32,   40,   48,   64,   80,
  40           96,  128,  160,  192,  224,  248,  320,  328,
  41          384,  448,  528,  584,  680,  816, 1016, 1088,
  42         1360, 2040, 2336, 2728, 3272, 4088, 5456, 8184 };
  43 #endif
  44
  45 #define NUM_ALLOCATORS  (sizeof (allocator_sizes) / sizeof (int))
  46
  47 static int allocator_block_sizes [NUM_ALLOCATORS];
  48
  49 static MonoLockFreeAllocSizeClass size_classes [NUM_ALLOCATORS];
  50 static MonoLockFreeAllocator allocators [NUM_ALLOCATORS];
  51
  52 #ifdef HEAVY_STATISTICS
  53 static int allocator_sizes_stats [NUM_ALLOCATORS];
  54 #endif
  55
  56 static size_t
  57 block_size (size_t slot_size)
  58 {
  59         static int pagesize = -1;
  60
  61         int size;
  62
  63         if (pagesize == -1)
  64                 pagesize = mono_pagesize ();
  65
  66         for (size = pagesize; size < LOCK_FREE_ALLOC_SB_MAX_SIZE; size <<= 1) {
  67                 if (slot_size * 2 <= LOCK_FREE_ALLOC_SB_USABLE_SIZE (size))
  68                         return size;
  69         }
  70         return LOCK_FREE_ALLOC_SB_MAX_SIZE;
  71 }
  72
  73 /*
  74  * Find the allocator index for memory chunks that can contain @size
  75  * objects.
  76  */
  77 static int
  78 index_for_size (size_t size)
  79 {
  80         int slot;
  81         /* do a binary search or lookup table later. */
  82         for (slot = 0; slot < NUM_ALLOCATORS; ++slot) {
  83                 if (allocator_sizes [slot] >= size)
  84                         return slot;
  85         }
  86         g_assert_not_reached ();
  87         return -1;
  88 }
  89
  90 /*
  91  * Allocator indexes for the fixed INTERNAL_MEM_XXX types.  -1 if that
  92  * type is dynamic.
  93  */
  94 static int fixed_type_allocator_indexes [INTERNAL_MEM_MAX];
  95
  96 void
  97 sgen_register_fixed_internal_mem_type (int type, size_t size)
  98 {
  99         int slot;
 100
 101         g_assert (type >= 0 && type < INTERNAL_MEM_MAX);
 102         g_assert (size <= allocator_sizes [NUM_ALLOCATORS - 1]);
 103
 104         slot = index_for_size (size);
 105         g_assert (slot >= 0);
 106
 107         if (fixed_type_allocator_indexes [type] == -1)
 108                 fixed_type_allocator_indexes [type] = slot;
 109         else
 110                 g_assert (fixed_type_allocator_indexes [type] == slot);
 111 }
 112
 113 static const char*
 114 description_for_type (int type)
 115 {
 116         switch (type) {
 117         case INTERNAL_MEM_PIN_QUEUE: return "pin-queue";
 118         case INTERNAL_MEM_FRAGMENT: return "fragment";
 119         case INTERNAL_MEM_SECTION: return "section";
 120         case INTERNAL_MEM_SCAN_STARTS: return "scan-starts";
 121         case INTERNAL_MEM_FIN_TABLE: return "fin-table";
 122         case INTERNAL_MEM_FINALIZE_ENTRY: return "finalize-entry";
 123         case INTERNAL_MEM_FINALIZE_READY_ENTRY: return "finalize-ready-entry";
 124         case INTERNAL_MEM_DISLINK_TABLE: return "dislink-table";
 125         case INTERNAL_MEM_DISLINK: return "dislink";
 126         case INTERNAL_MEM_ROOTS_TABLE: return "roots-table";
 127         case INTERNAL_MEM_ROOT_RECORD: return "root-record";
 128         case INTERNAL_MEM_STATISTICS: return "statistics";
 129         case INTERNAL_MEM_STAT_PINNED_CLASS: return "pinned-class";
 130         case INTERNAL_MEM_STAT_REMSET_CLASS: return "remset-class";
 131         case INTERNAL_MEM_GRAY_QUEUE: return "gray-queue";
 132         case INTERNAL_MEM_MS_TABLES: return "marksweep-tables";
 133         case INTERNAL_MEM_MS_BLOCK_INFO: return "marksweep-block-info";
 134         case INTERNAL_MEM_MS_BLOCK_INFO_SORT: return "marksweep-block-info-sort";
 135         case INTERNAL_MEM_EPHEMERON_LINK: return "ephemeron-link";
 136         case INTERNAL_MEM_WORKER_DATA: return "worker-data";
 137         case INTERNAL_MEM_WORKER_JOB_DATA: return "worker-job-data";
 138         case INTERNAL_MEM_BRIDGE_DATA: return "bridge-data";
 139         case INTERNAL_MEM_OLD_BRIDGE_HASH_TABLE: return "old-bridge-hash-table";
 140         case INTERNAL_MEM_OLD_BRIDGE_HASH_TABLE_ENTRY: return "old-bridge-hash-table-entry";
 141         case INTERNAL_MEM_BRIDGE_HASH_TABLE: return "bridge-hash-table";
 142         case INTERNAL_MEM_BRIDGE_HASH_TABLE_ENTRY: return "bridge-hash-table-entry";
 143         case INTERNAL_MEM_TARJAN_BRIDGE_HASH_TABLE: return "tarjan-bridge-hash-table";
 144         case INTERNAL_MEM_TARJAN_BRIDGE_HASH_TABLE_ENTRY: return "tarjan-bridge-hash-table-entry";
 145         case INTERNAL_MEM_TARJAN_OBJ_BUCKET: return "tarjan-bridge-object-buckets";
 146         case INTERNAL_MEM_BRIDGE_ALIVE_HASH_TABLE: return "bridge-alive-hash-table";
 147         case INTERNAL_MEM_BRIDGE_ALIVE_HASH_TABLE_ENTRY: return "bridge-alive-hash-table-entry";
 148         case INTERNAL_MEM_BRIDGE_DEBUG: return "bridge-debug";
 149         case INTERNAL_MEM_JOB_QUEUE_ENTRY: return "job-queue-entry";
 150         case INTERNAL_MEM_TOGGLEREF_DATA: return "toggleref-data";
 151         case INTERNAL_MEM_CARDTABLE_MOD_UNION: return "cardtable-mod-union";
 152         case INTERNAL_MEM_BINARY_PROTOCOL: return "binary-protocol";
 153         case INTERNAL_MEM_TEMPORARY: return "temporary";
 154         default:
 155                 g_assert_not_reached ();
 156         }
 157 }
 158
 159 void*
 160 sgen_alloc_internal_dynamic (size_t size, int type, gboolean assert_on_failure)
 161 {
 162         int index;
 163         void *p;
 164
 165         if (size > allocator_sizes [NUM_ALLOCATORS - 1]) {
 166                 p = sgen_alloc_os_memory (size, SGEN_ALLOC_INTERNAL | SGEN_ALLOC_ACTIVATE, NULL);
 167                 if (!p)
 168                         sgen_assert_memory_alloc (NULL, size, description_for_type (type));
 169         } else {
 170                 index = index_for_size (size);
 171
 172 #ifdef HEAVY_STATISTICS
 173                 ++ allocator_sizes_stats [index];
 174 #endif
 175
 176                 p = mono_lock_free_alloc (&allocators [index]);
 177                 if (!p)
 178                         sgen_assert_memory_alloc (NULL, size, description_for_type (type));
 179                 memset (p, 0, size);
 180         }
 181
 182         MONO_GC_INTERNAL_ALLOC ((mword)p, size, type);
 183         return p;
 184 }
 185
 186 void
 187 sgen_free_internal_dynamic (void *addr, size_t size, int type)
 188 {
 189         if (!addr)
 190                 return;
 191
 192         if (size > allocator_sizes [NUM_ALLOCATORS - 1])
 193                 sgen_free_os_memory (addr, size, SGEN_ALLOC_INTERNAL);
 194         else
 195                 mono_lock_free_free (addr, block_size (size));
 196
 197         MONO_GC_INTERNAL_DEALLOC ((mword)addr, size, type);
 198 }
 199
 200 void*
 201 sgen_alloc_internal (int type)
 202 {
 203         int index, size;
 204         void *p;
 205
 206         index = fixed_type_allocator_indexes [type];
 207         g_assert (index >= 0 && index < NUM_ALLOCATORS);
 208
 209 #ifdef HEAVY_STATISTICS
 210         ++ allocator_sizes_stats [index];
 211 #endif
 212
 213         size = allocator_sizes [index];
 214
 215         p = mono_lock_free_alloc (&allocators [index]);
 216         memset (p, 0, size);
 217
 218         MONO_GC_INTERNAL_ALLOC ((mword)p, size, type);
 219
 220         return p;
 221 }
 222
 223 void
 224 sgen_free_internal (void *addr, int type)
 225 {
 226         int index;
 227
 228         if (!addr)
 229                 return;
 230
 231         index = fixed_type_allocator_indexes [type];
 232         g_assert (index >= 0 && index < NUM_ALLOCATORS);
 233
 234         mono_lock_free_free (addr, allocator_block_sizes [index]);
 235
 236         if (MONO_GC_INTERNAL_DEALLOC_ENABLED ()) {
 237                 int size G_GNUC_UNUSED = allocator_sizes [index];
 238                 MONO_GC_INTERNAL_DEALLOC ((mword)addr, size, type);
 239         }
 240 }
 241
 242 void
 243 sgen_dump_internal_mem_usage (FILE *heap_dump_file)
 244 {
 245         /*
 246         int i;
 247
 248         fprintf (heap_dump_file, "<other-mem-usage type=\"large-internal\" size=\"%lld\"/>\n", large_internal_bytes_alloced);
 249         fprintf (heap_dump_file, "<other-mem-usage type=\"pinned-chunks\" size=\"%lld\"/>\n", pinned_chunk_bytes_alloced);
 250         for (i = 0; i < INTERNAL_MEM_MAX; ++i) {
 251                 fprintf (heap_dump_file, "<other-mem-usage type=\"%s\" size=\"%ld\"/>\n",
 252                                 description_for_type (i), unmanaged_allocator.small_internal_mem_bytes [i]);
 253         }
 254         */
 255 }
 256
 257 void
 258 sgen_report_internal_mem_usage (void)
 259 {
 260         int i G_GNUC_UNUSED;
 261 #ifdef HEAVY_STATISTICS
 262         printf ("size -> # allocations\n");
 263         for (i = 0; i < NUM_ALLOCATORS; ++i)
 264                 printf ("%d -> %d\n", allocator_sizes [i], allocator_sizes_stats [i]);
 265 #endif
 266 }
 267
 268 void
 269 sgen_init_internal_allocator (void)
 270 {
 271         int i, size;
 272
 273         for (i = 0; i < INTERNAL_MEM_MAX; ++i)
 274                 fixed_type_allocator_indexes [i] = -1;
 275
 276         for (i = 0; i < NUM_ALLOCATORS; ++i) {
 277                 allocator_block_sizes [i] = block_size (allocator_sizes [i]);
 278                 mono_lock_free_allocator_init_size_class (&size_classes [i], allocator_sizes [i], allocator_block_sizes [i]);
 279                 mono_lock_free_allocator_init_allocator (&allocators [i], &size_classes [i]);
 280         }
 281
 282         for (size = mono_pagesize (); size <= LOCK_FREE_ALLOC_SB_MAX_SIZE; size <<= 1) {
 283                 int max_size = LOCK_FREE_ALLOC_SB_USABLE_SIZE (size) / 2;
 284                 /*
 285                  * we assert that allocator_sizes contains the biggest possible object size
 286                  * per block (4K => 4080 / 2 = 2040, 8k => 8176 / 2 = 4088, 16k => 16368 / 2 = 8184 on 64bits),
 287                  * so that we do not get different block sizes for sizes that should go to the same one
 288                  */
 289                 g_assert (allocator_sizes [index_for_size (max_size)] == max_size);
 290         }
 291 }
 292
 293 #endif