2 * sgen-internal.c: Internal lock-free memory allocator.
4 * Copyright (C) 2012 Xamarin Inc
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;
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.
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.
26 #include "mono/sgen/sgen-gc.h"
27 #include "mono/utils/lock-free-alloc.h"
28 #include "mono/sgen/sgen-memory-governor.h"
29 #include "mono/sgen/sgen-client.h"
31 /* keep each size a multiple of ALLOC_ALIGN */
32 #if SIZEOF_VOID_P == 4
33 static const int allocator_sizes
[] = {
34 8, 16, 24, 32, 40, 48, 64, 80,
35 96, 128, 160, 192, 224, 248, 296, 320,
36 384, 448, 504, 528, 584, 680, 816, 1088,
37 1360, 2044, 2336, 2728, 3272, 4092, 5456, 8188 };
39 static const int allocator_sizes
[] = {
40 8, 16, 24, 32, 40, 48, 64, 80,
41 96, 128, 160, 192, 224, 248, 320, 328,
42 384, 448, 528, 584, 680, 816, 1016, 1088,
43 1360, 2040, 2336, 2728, 3272, 4088, 5456, 8184 };
46 #define NUM_ALLOCATORS (sizeof (allocator_sizes) / sizeof (int))
48 static int allocator_block_sizes
[NUM_ALLOCATORS
];
50 static MonoLockFreeAllocSizeClass size_classes
[NUM_ALLOCATORS
];
51 static MonoLockFreeAllocator allocators
[NUM_ALLOCATORS
];
53 #ifdef HEAVY_STATISTICS
54 static int allocator_sizes_stats
[NUM_ALLOCATORS
];
58 block_size (size_t slot_size
)
60 static int pagesize
= -1;
65 pagesize
= mono_pagesize ();
67 for (size
= pagesize
; size
< LOCK_FREE_ALLOC_SB_MAX_SIZE
; size
<<= 1) {
68 if (slot_size
* 2 <= LOCK_FREE_ALLOC_SB_USABLE_SIZE (size
))
71 return LOCK_FREE_ALLOC_SB_MAX_SIZE
;
75 * Find the allocator index for memory chunks that can contain @size
79 index_for_size (size_t size
)
82 /* do a binary search or lookup table later. */
83 for (slot
= 0; slot
< NUM_ALLOCATORS
; ++slot
) {
84 if (allocator_sizes
[slot
] >= size
)
87 g_assert_not_reached ();
92 * Allocator indexes for the fixed INTERNAL_MEM_XXX types. -1 if that
95 static int fixed_type_allocator_indexes
[INTERNAL_MEM_MAX
];
98 sgen_register_fixed_internal_mem_type (int type
, size_t size
)
102 g_assert (type
>= 0 && type
< INTERNAL_MEM_MAX
);
103 g_assert (size
<= allocator_sizes
[NUM_ALLOCATORS
- 1]);
105 slot
= index_for_size (size
);
106 g_assert (slot
>= 0);
108 if (fixed_type_allocator_indexes
[type
] == -1)
109 fixed_type_allocator_indexes
[type
] = slot
;
111 g_assert (fixed_type_allocator_indexes
[type
] == slot
);
115 description_for_type (int type
)
118 case INTERNAL_MEM_PIN_QUEUE
: return "pin-queue";
119 case INTERNAL_MEM_FRAGMENT
: return "fragment";
120 case INTERNAL_MEM_SECTION
: return "section";
121 case INTERNAL_MEM_SCAN_STARTS
: return "scan-starts";
122 case INTERNAL_MEM_FIN_TABLE
: return "fin-table";
123 case INTERNAL_MEM_FINALIZE_ENTRY
: return "finalize-entry";
124 case INTERNAL_MEM_FINALIZE_READY
: return "finalize-ready";
125 case INTERNAL_MEM_DISLINK_TABLE
: return "dislink-table";
126 case INTERNAL_MEM_DISLINK
: return "dislink";
127 case INTERNAL_MEM_ROOTS_TABLE
: return "roots-table";
128 case INTERNAL_MEM_ROOT_RECORD
: return "root-record";
129 case INTERNAL_MEM_STATISTICS
: return "statistics";
130 case INTERNAL_MEM_STAT_PINNED_CLASS
: return "pinned-class";
131 case INTERNAL_MEM_STAT_REMSET_CLASS
: return "remset-class";
132 case INTERNAL_MEM_GRAY_QUEUE
: return "gray-queue";
133 case INTERNAL_MEM_MS_TABLES
: return "marksweep-tables";
134 case INTERNAL_MEM_MS_BLOCK_INFO
: return "marksweep-block-info";
135 case INTERNAL_MEM_MS_BLOCK_INFO_SORT
: return "marksweep-block-info-sort";
136 case INTERNAL_MEM_WORKER_DATA
: return "worker-data";
137 case INTERNAL_MEM_THREAD_POOL_JOB
: return "thread-pool-job";
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_TOGGLEREF_DATA
: return "toggleref-data";
150 case INTERNAL_MEM_CARDTABLE_MOD_UNION
: return "cardtable-mod-union";
151 case INTERNAL_MEM_BINARY_PROTOCOL
: return "binary-protocol";
152 case INTERNAL_MEM_TEMPORARY
: return "temporary";
154 const char *description
= sgen_client_description_for_internal_mem_type (type
);
155 SGEN_ASSERT (0, description
, "Unknown internal mem type");
162 sgen_alloc_internal_dynamic (size_t size
, int type
, gboolean assert_on_failure
)
167 if (size
> allocator_sizes
[NUM_ALLOCATORS
- 1]) {
168 p
= sgen_alloc_os_memory (size
, SGEN_ALLOC_INTERNAL
| SGEN_ALLOC_ACTIVATE
, NULL
);
170 sgen_assert_memory_alloc (NULL
, size
, description_for_type (type
));
172 index
= index_for_size (size
);
174 #ifdef HEAVY_STATISTICS
175 ++ allocator_sizes_stats
[index
];
178 p
= mono_lock_free_alloc (&allocators
[index
]);
180 sgen_assert_memory_alloc (NULL
, size
, description_for_type (type
));
187 sgen_free_internal_dynamic (void *addr
, size_t size
, int type
)
192 if (size
> allocator_sizes
[NUM_ALLOCATORS
- 1])
193 sgen_free_os_memory (addr
, size
, SGEN_ALLOC_INTERNAL
);
195 mono_lock_free_free (addr
, block_size (size
));
199 sgen_alloc_internal (int type
)
204 index
= fixed_type_allocator_indexes
[type
];
205 g_assert (index
>= 0 && index
< NUM_ALLOCATORS
);
207 #ifdef HEAVY_STATISTICS
208 ++ allocator_sizes_stats
[index
];
211 size
= allocator_sizes
[index
];
213 p
= mono_lock_free_alloc (&allocators
[index
]);
220 sgen_free_internal (void *addr
, int type
)
227 index
= fixed_type_allocator_indexes
[type
];
228 g_assert (index
>= 0 && index
< NUM_ALLOCATORS
);
230 mono_lock_free_free (addr
, allocator_block_sizes
[index
]);
234 sgen_dump_internal_mem_usage (FILE *heap_dump_file
)
239 fprintf (heap_dump_file, "<other-mem-usage type=\"large-internal\" size=\"%lld\"/>\n", large_internal_bytes_alloced);
240 fprintf (heap_dump_file, "<other-mem-usage type=\"pinned-chunks\" size=\"%lld\"/>\n", pinned_chunk_bytes_alloced);
241 for (i = 0; i < INTERNAL_MEM_MAX; ++i) {
242 fprintf (heap_dump_file, "<other-mem-usage type=\"%s\" size=\"%ld\"/>\n",
243 description_for_type (i), unmanaged_allocator.small_internal_mem_bytes [i]);
249 sgen_report_internal_mem_usage (void)
252 #ifdef HEAVY_STATISTICS
253 printf ("size -> # allocations\n");
254 for (i
= 0; i
< NUM_ALLOCATORS
; ++i
)
255 printf ("%d -> %d\n", allocator_sizes
[i
], allocator_sizes_stats
[i
]);
260 sgen_init_internal_allocator (void)
264 for (i
= 0; i
< INTERNAL_MEM_MAX
; ++i
)
265 fixed_type_allocator_indexes
[i
] = -1;
267 for (i
= 0; i
< NUM_ALLOCATORS
; ++i
) {
268 allocator_block_sizes
[i
] = block_size (allocator_sizes
[i
]);
269 mono_lock_free_allocator_init_size_class (&size_classes
[i
], allocator_sizes
[i
], allocator_block_sizes
[i
]);
270 mono_lock_free_allocator_init_allocator (&allocators
[i
], &size_classes
[i
]);
273 for (size
= mono_pagesize (); size
<= LOCK_FREE_ALLOC_SB_MAX_SIZE
; size
<<= 1) {
274 int max_size
= LOCK_FREE_ALLOC_SB_USABLE_SIZE (size
) / 2;
276 * we assert that allocator_sizes contains the biggest possible object size
277 * per block (4K => 4080 / 2 = 2040, 8k => 8176 / 2 = 4088, 16k => 16368 / 2 = 8184 on 64bits),
278 * so that we do not get different block sizes for sizes that should go to the same one
280 g_assert (allocator_sizes
[index_for_size (max_size
)] == max_size
);