2 * sgen-internal.c: Internal lock-free memory allocator.
4 * Copyright (C) 2012 Xamarin Inc
6 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
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"
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 };
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 };
35 #define NUM_ALLOCATORS (sizeof (allocator_sizes) / sizeof (int))
37 static int allocator_block_sizes [NUM_ALLOCATORS];
39 static MonoLockFreeAllocSizeClass size_classes [NUM_ALLOCATORS];
40 static MonoLockFreeAllocator allocators [NUM_ALLOCATORS];
42 #ifdef HEAVY_STATISTICS
43 static int allocator_sizes_stats [NUM_ALLOCATORS];
47 block_size (size_t slot_size)
49 static int pagesize = -1;
54 pagesize = mono_pagesize ();
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))
60 return LOCK_FREE_ALLOC_SB_MAX_SIZE;
64 * Find the allocator index for memory chunks that can contain @size
68 index_for_size (size_t size)
71 /* do a binary search or lookup table later. */
72 for (slot = 0; slot < NUM_ALLOCATORS; ++slot) {
73 if (allocator_sizes [slot] >= size)
76 g_assert_not_reached ();
81 * Allocator indexes for the fixed INTERNAL_MEM_XXX types. -1 if that
84 static int fixed_type_allocator_indexes [INTERNAL_MEM_MAX];
87 sgen_register_fixed_internal_mem_type (int type, size_t size)
91 g_assert (type >= 0 && type < INTERNAL_MEM_MAX);
92 g_assert (size <= allocator_sizes [NUM_ALLOCATORS - 1]);
94 slot = index_for_size (size);
97 if (fixed_type_allocator_indexes [type] == -1)
98 fixed_type_allocator_indexes [type] = slot;
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);
106 description_for_type (int 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";
147 const char *description = sgen_client_description_for_internal_mem_type (type);
148 SGEN_ASSERT (0, description, "Unknown internal mem type");
155 sgen_alloc_internal_dynamic (size_t size, int type, gboolean assert_on_failure)
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);
163 sgen_assert_memory_alloc (NULL, size, description_for_type (type));
165 index = index_for_size (size);
167 #ifdef HEAVY_STATISTICS
168 ++ allocator_sizes_stats [index];
171 p = mono_lock_free_alloc (&allocators [index]);
173 sgen_assert_memory_alloc (NULL, size, description_for_type (type));
180 sgen_free_internal_dynamic (void *addr, size_t size, int type)
185 if (size > allocator_sizes [NUM_ALLOCATORS - 1])
186 sgen_free_os_memory (addr, size, SGEN_ALLOC_INTERNAL, MONO_MEM_ACCOUNT_SGEN_INTERNAL);
188 mono_lock_free_free (addr, block_size (size));
192 sgen_alloc_internal (int type)
197 index = fixed_type_allocator_indexes [type];
198 g_assert (index >= 0 && index < NUM_ALLOCATORS);
200 #ifdef HEAVY_STATISTICS
201 ++ allocator_sizes_stats [index];
204 size = allocator_sizes [index];
206 p = mono_lock_free_alloc (&allocators [index]);
213 sgen_free_internal (void *addr, int type)
220 index = fixed_type_allocator_indexes [type];
221 g_assert (index >= 0 && index < NUM_ALLOCATORS);
223 mono_lock_free_free (addr, allocator_block_sizes [index]);
227 sgen_dump_internal_mem_usage (FILE *heap_dump_file)
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]);
242 sgen_report_internal_mem_usage (void)
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]);
253 sgen_init_internal_allocator (void)
257 for (i = 0; i < INTERNAL_MEM_MAX; ++i)
258 fixed_type_allocator_indexes [i] = -1;
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);
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;
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
273 g_assert (allocator_sizes [index_for_size (max_size)] == max_size);