mono/sgen/sgen-internal.c

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