2 * sgen-bridge.c: Simple generational GC.
4 * Copyright 2011 Novell, Inc (http://www.novell.com)
6 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
7 * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
9 * Permission is hereby granted to use or copy this program
10 * for any purpose, provided the above notices are retained on all copies.
11 * Permission to modify the code and to distribute modified code is granted,
12 * provided the above notices are retained, and a notice that the code was
13 * modified is included with the above copyright notice.
16 * Copyright 2001-2003 Ximian, Inc
17 * Copyright 2003-2010 Novell, Inc.
19 * Permission is hereby granted, free of charge, to any person obtaining
20 * a copy of this software and associated documentation files (the
21 * "Software"), to deal in the Software without restriction, including
22 * without limitation the rights to use, copy, modify, merge, publish,
23 * distribute, sublicense, and/or sell copies of the Software, and to
24 * permit persons to whom the Software is furnished to do so, subject to
25 * the following conditions:
27 * The above copyright notice and this permission notice shall be
28 * included in all copies or substantial portions of the Software.
30 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
44 #include "sgen-bridge.h"
53 #define DYN_ARRAY_REF(da,i) ((void*)((da)->data + (i) * (da)->elem_size))
54 #define DYN_ARRAY_PTR_REF(da,i) (((void**)(da)->data) [(i)])
55 #define DYN_ARRAY_INT_REF(da,i) (((int*)(da)->data) [(i)])
58 dyn_array_init (DynArray *da, int elem_size)
61 da->elem_size = elem_size;
67 dyn_array_ptr_init (DynArray *da)
69 dyn_array_init (da, sizeof (void*));
73 dyn_array_int_init (DynArray *da)
75 dyn_array_init (da, sizeof (int));
79 dyn_array_uninit (DynArray *da)
81 if (da->capacity <= 0)
84 mono_sgen_free_internal_dynamic (da->data, da->elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA);
89 dyn_array_ensure_capacity (DynArray *da, int capacity)
93 if (capacity <= da->capacity)
96 if (da->capacity == 0)
98 while (capacity > da->capacity)
101 new_data = mono_sgen_alloc_internal_dynamic (da->elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA);
102 memcpy (new_data, da->data, da->elem_size * da->size);
103 mono_sgen_free_internal_dynamic (da->data, da->elem_size * da->size, INTERNAL_MEM_BRIDGE_DATA);
108 dyn_array_add (DynArray *da)
112 dyn_array_ensure_capacity (da, da->size + 1);
114 p = DYN_ARRAY_REF (da, da->size);
120 dyn_array_ptr_add (DynArray *da, void *ptr)
122 void **p = dyn_array_add (da);
126 #define dyn_array_ptr_push dyn_array_ptr_add
129 dyn_array_ptr_pop (DynArray *da)
132 g_assert (da->size > 0);
133 p = DYN_ARRAY_PTR_REF (da, da->size - 1);
139 dyn_array_int_add (DynArray *da, int x)
141 int *p = dyn_array_add (da);
147 dyn_array_ptr_contains (DynArray *da, void *ptr)
150 for (i = 0; i < da->size; ++i)
151 if (DYN_ARRAY_PTR_REF (da, i) == ptr)
158 dyn_array_int_contains (DynArray *da, int x)
161 for (i = 0; i < da->size; ++i)
162 if (DYN_ARRAY_INT_REF (da, i) == x)
168 dyn_array_append (DynArray *dst, DynArray *src)
170 g_assert (dst->elem_size == src->elem_size);
172 dyn_array_ensure_capacity (dst, dst->size + src->size);
173 memcpy (DYN_ARRAY_REF (dst, dst->size), DYN_ARRAY_REF (src, 0), src->size * src->elem_size);
174 dst->size += src->size;
178 * FIXME: Optimizations:
180 * Don't allocate a scrs array for just one source. Most objects have
181 * just one source, so use the srcs pointer itself.
183 typedef struct _HashEntry {
194 struct _HashEntry *next;
197 typedef struct _SCC {
200 int num_bridge_entries;
201 DynArray xrefs; /* these are incoming, not outgoing */
204 static int num_hash_entries = 0;
205 static int hash_size = 0;
206 static HashEntry **hash_table = NULL;
208 static MonoGCBridgeCallbacks bridge_callbacks;
210 static int current_time;
213 mono_gc_register_bridge_callbacks (MonoGCBridgeCallbacks *callbacks)
215 bridge_callbacks = *callbacks;
219 mono_sgen_need_bridge_processing (void)
221 return bridge_callbacks.cross_references != NULL;
225 alloc_hash_table (int size)
228 table = mono_sgen_alloc_internal_dynamic (sizeof (HashEntry*) * size, INTERNAL_MEM_BRIDGE_DATA);
229 memset (table, 0, sizeof (HashEntry*) * size);
236 HashEntry **new_table;
237 int new_size = hash_size << 1;
240 new_table = alloc_hash_table (new_size);
241 for (i = 0; i < hash_size; ++i) {
242 HashEntry *entry = hash_table [i];
243 while (entry != NULL) {
244 HashEntry *next = entry->next;
245 int hash = ((mword)entry->obj >> 4) & (new_size - 1);
246 entry->next = new_table [hash];
247 new_table [hash] = entry;
252 mono_sgen_free_internal_dynamic (hash_table, sizeof (HashEntry*) * hash_size, INTERNAL_MEM_BRIDGE_DATA);
254 hash_table = new_table;
255 hash_size = new_size;
259 lookup_hash_entry (MonoObject *obj)
261 int hash = (mword)obj >> 4;
265 g_assert (hash_size == 0 && num_hash_entries == 0);
267 hash_table = alloc_hash_table (hash_size);
270 hash &= hash_size - 1;
271 for (entry = hash_table [hash]; entry != NULL; entry = entry->next) {
272 if (entry->obj == obj)
280 get_hash_entry (MonoObject *obj)
282 HashEntry *entry = lookup_hash_entry (obj);
288 entry = mono_sgen_alloc_internal_dynamic (sizeof (HashEntry), INTERNAL_MEM_BRIDGE_DATA);
289 memset (entry, 0, sizeof (HashEntry));
292 dyn_array_ptr_init (&entry->srcs);
293 entry->finishing_time = -1;
294 entry->scc_index = -1;
296 hash = ((mword)obj >> 4) & (hash_size - 1);
297 entry->next = hash_table [hash];
298 hash_table [hash] = entry;
302 if (num_hash_entries > hash_size >> 1)
309 add_source (HashEntry *entry, HashEntry *src)
311 dyn_array_ptr_add (&entry->srcs, src);
321 if (hash_table == NULL)
324 for (i = 0; i < hash_size; ++i) {
325 HashEntry *entry = hash_table [i];
326 while (entry != NULL) {
327 HashEntry *next = entry->next;
328 total_srcs += entry->srcs.size;
329 if (entry->srcs.size > max_srcs)
330 max_srcs = entry->srcs.size;
331 dyn_array_uninit (&entry->srcs);
332 mono_sgen_free_internal_dynamic (entry, sizeof (HashEntry), INTERNAL_MEM_BRIDGE_DATA);
337 mono_sgen_free_internal_dynamic (hash_table, sizeof (HashEntry*) * hash_size, INTERNAL_MEM_BRIDGE_DATA);
340 num_hash_entries = 0;
343 //g_print ("total srcs %d - max %d\n", total_srcs, max_srcs);
347 register_bridge_object (MonoObject *obj)
349 HashEntry *entry = get_hash_entry (obj);
350 g_assert (!entry->is_bridge);
351 entry->is_bridge = TRUE;
355 register_finishing_time (HashEntry *entry, int t)
357 g_assert (entry->finishing_time < 0);
358 entry->finishing_time = t;
362 object_is_live (MonoObject **objp)
364 MonoObject *obj = *objp;
365 MonoObject *fwd = SGEN_OBJECT_IS_FORWARDED (obj);
368 return lookup_hash_entry (fwd) == NULL;
370 if (!mono_sgen_object_is_live (obj))
372 return lookup_hash_entry (obj) == NULL;
375 static DynArray dfs_stack;
378 #define HANDLE_PTR(ptr,obj) do { \
379 MonoObject *dst = (MonoObject*)*(ptr); \
380 if (dst && !object_is_live (&dst)) { \
381 dyn_array_ptr_push (&dfs_stack, obj_entry); \
382 dyn_array_ptr_push (&dfs_stack, get_hash_entry (dst)); \
387 dfs1 (HashEntry *obj_entry, HashEntry *src)
389 g_assert (dfs_stack.size == 0);
391 dyn_array_ptr_push (&dfs_stack, src);
392 dyn_array_ptr_push (&dfs_stack, obj_entry);
398 obj_entry = dyn_array_ptr_pop (&dfs_stack);
400 src = dyn_array_ptr_pop (&dfs_stack);
402 obj = obj_entry->obj;
406 //g_print ("link %s -> %s\n", mono_sgen_safe_name (src->obj), mono_sgen_safe_name (obj));
407 add_source (obj_entry, src);
409 //g_print ("starting with %s\n", mono_sgen_safe_name (obj));
412 if (obj_entry->is_visited)
415 obj_entry->is_visited = TRUE;
417 dyn_array_ptr_push (&dfs_stack, obj_entry);
418 /* NULL marks that the next entry is to be finished */
419 dyn_array_ptr_push (&dfs_stack, NULL);
421 #include "sgen-scan-object.h"
423 obj_entry = dyn_array_ptr_pop (&dfs_stack);
425 //g_print ("finish %s\n", mono_sgen_safe_name (obj_entry->obj));
426 register_finishing_time (obj_entry, current_time++);
428 } while (dfs_stack.size > 0);
432 scc_add_xref (SCC *src, SCC *dst)
434 g_assert (src != dst);
435 g_assert (src->index != dst->index);
437 if (dyn_array_int_contains (&dst->xrefs, src->index))
439 if (src->num_bridge_entries) {
440 dyn_array_int_add (&dst->xrefs, src->index);
444 dyn_array_append (&dst->xrefs, &src->xrefs);
445 for (i = 0; i < dst->xrefs.size; ++i)
446 g_assert (DYN_ARRAY_INT_REF (&dst->xrefs, i) != dst->index);
451 scc_add_entry (SCC *scc, HashEntry *entry)
453 g_assert (entry->scc_index < 0);
454 entry->scc_index = scc->index;
455 if (entry->is_bridge)
456 ++scc->num_bridge_entries;
459 static DynArray sccs;
460 static SCC *current_scc;
463 dfs2 (HashEntry *entry)
467 g_assert (dfs_stack.size == 0);
469 dyn_array_ptr_push (&dfs_stack, entry);
472 entry = dyn_array_ptr_pop (&dfs_stack);
474 if (entry->scc_index >= 0) {
475 if (entry->scc_index != current_scc->index)
476 scc_add_xref (DYN_ARRAY_REF (&sccs, entry->scc_index), current_scc);
480 scc_add_entry (current_scc, entry);
482 for (i = 0; i < entry->srcs.size; ++i)
483 dyn_array_ptr_push (&dfs_stack, DYN_ARRAY_PTR_REF (&entry->srcs, i));
484 } while (dfs_stack.size > 0);
488 compare_hash_entries (const void *ep1, const void *ep2)
490 HashEntry *e1 = *(HashEntry**)ep1;
491 HashEntry *e2 = *(HashEntry**)ep2;
492 return e2->finishing_time - e1->finishing_time;
496 mono_sgen_bridge_processing (int num_objs, MonoObject **objs)
498 HashEntry **all_entries;
500 int num_sccs, num_xrefs;
501 int max_entries, max_xrefs;
503 MonoGCBridgeSCC **api_sccs;
504 MonoGCBridgeXRef *api_xrefs;
506 g_assert (mono_sgen_need_bridge_processing ());
508 //g_print ("%d finalized objects\n", num_objs);
510 /* remove objects that are not bridge objects */
512 for (i = 0; i < num_objs; ++i) {
513 MonoObject *obj = objs [i];
514 //g_assert (!mono_sgen_object_is_live (obj));
515 if (bridge_callbacks.is_bridge_object (obj)) {
516 register_bridge_object (obj);
522 //g_print ("%d bridge objects\n", num_objs);
526 dyn_array_ptr_init (&dfs_stack);
529 for (i = 0; i < num_objs; ++i)
530 dfs1 (get_hash_entry (objs [i]), NULL);
532 //g_print ("%d entries - hash size %d\n", num_hash_entries, hash_size);
534 /* alloc and fill array of all entries */
536 all_entries = mono_sgen_alloc_internal_dynamic (sizeof (HashEntry*) * num_hash_entries, INTERNAL_MEM_BRIDGE_DATA);
540 for (i = 0; i < hash_size; ++i) {
543 for (entry = hash_table [i]; entry != NULL; entry = entry->next) {
544 g_assert (entry->finishing_time >= 0);
545 all_entries [j++] = entry;
548 if (length > max_entries)
549 max_entries = length;
551 g_assert (j == num_hash_entries);
553 //g_print ("max hash bucket length %d\n", max_entries);
555 /* sort array according to decreasing finishing time */
557 qsort (all_entries, num_hash_entries, sizeof (HashEntry*), compare_hash_entries);
559 /* second DFS pass */
561 dyn_array_init (&sccs, sizeof (SCC));
562 for (i = 0; i < num_hash_entries; ++i) {
563 HashEntry *entry = all_entries [i];
564 if (entry->scc_index < 0) {
565 int index = sccs.size;
566 current_scc = dyn_array_add (&sccs);
567 current_scc->index = index;
568 current_scc->num_bridge_entries = 0;
569 current_scc->api_index = -1;
570 dyn_array_int_init (¤t_scc->xrefs);
576 //g_print ("%d sccs\n", sccs.size);
578 dyn_array_uninit (&dfs_stack);
580 /* init data for callback */
583 for (i = 0; i < sccs.size; ++i) {
584 SCC *scc = DYN_ARRAY_REF (&sccs, i);
585 g_assert (scc->index == i);
586 if (scc->num_bridge_entries)
590 api_sccs = mono_sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC*) * num_sccs, INTERNAL_MEM_BRIDGE_DATA);
593 for (i = 0; i < sccs.size; ++i) {
594 SCC *scc = DYN_ARRAY_REF (&sccs, i);
595 if (!scc->num_bridge_entries)
598 api_sccs [j] = mono_sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC) + sizeof (MonoObject*) * scc->num_bridge_entries, INTERNAL_MEM_BRIDGE_DATA);
599 api_sccs [j]->num_objs = scc->num_bridge_entries;
600 scc->num_bridge_entries = 0;
601 scc->api_index = j++;
603 num_xrefs += scc->xrefs.size;
606 for (i = 0; i < hash_size; ++i) {
608 for (entry = hash_table [i]; entry != NULL; entry = entry->next) {
610 if (!entry->is_bridge)
612 scc = DYN_ARRAY_REF (&sccs, entry->scc_index);
613 api_sccs [scc->api_index]->objs [scc->num_bridge_entries++] = entry->obj;
617 api_xrefs = mono_sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeXRef) * num_xrefs, INTERNAL_MEM_BRIDGE_DATA);
619 for (i = 0; i < sccs.size; ++i) {
621 SCC *scc = DYN_ARRAY_REF (&sccs, i);
622 if (!scc->num_bridge_entries)
624 for (k = 0; k < scc->xrefs.size; ++k) {
625 SCC *src_scc = DYN_ARRAY_REF (&sccs, DYN_ARRAY_INT_REF (&scc->xrefs, k));
626 if (!src_scc->num_bridge_entries)
628 api_xrefs [j].src_scc_index = src_scc->api_index;
629 api_xrefs [j].dst_scc_index = scc->api_index;
637 max_entries = max_xrefs = 0;
638 for (i = 0; i < sccs.size; ++i) {
639 SCC *scc = DYN_ARRAY_REF (&sccs, i);
640 if (scc->num_bridge_entries)
642 if (scc->num_bridge_entries > max_entries)
643 max_entries = scc->num_bridge_entries;
644 if (scc->xrefs.size > max_xrefs)
645 max_xrefs = scc->xrefs.size;
646 dyn_array_uninit (&scc->xrefs);
649 dyn_array_uninit (&sccs);
651 mono_sgen_free_internal_dynamic (all_entries, sizeof (HashEntry*) * num_hash_entries, INTERNAL_MEM_BRIDGE_DATA);
655 //g_print ("%d sccs containing bridges - %d max bridge objects - %d max xrefs\n", j, max_entries, max_xrefs);
659 bridge_callbacks.cross_references (num_sccs, api_sccs, num_xrefs, api_xrefs);
661 /* free callback data */
663 for (i = 0; i < num_sccs; ++i) {
664 mono_sgen_free_internal_dynamic (api_sccs [i],
665 sizeof (MonoGCBridgeSCC) + sizeof (MonoObject*) * api_sccs [i]->num_objs,
666 INTERNAL_MEM_BRIDGE_DATA);
668 mono_sgen_free_internal_dynamic (api_sccs, sizeof (MonoGCBridgeSCC*) * num_sccs, INTERNAL_MEM_BRIDGE_DATA);
670 mono_sgen_free_internal_dynamic (api_xrefs, sizeof (MonoGCBridgeXRef) * num_xrefs, INTERNAL_MEM_BRIDGE_DATA);
674 bridge_test_is_bridge_object (MonoObject *obj)
680 bridge_test_cross_reference (int num_sccs, MonoGCBridgeSCC **sccs, int num_xrefs, MonoGCBridgeXRef *xrefs)
683 for (i = 0; i < num_sccs; ++i) {
685 g_print ("--- SCC %d\n", i);
686 for (j = 0; j < sccs [i]->num_objs; ++j)
687 g_print (" %s\n", mono_sgen_safe_name (sccs [i]->objs [j]));
689 for (i = 0; i < num_xrefs; ++i) {
690 g_assert (xrefs [i].src_scc_index >= 0 && xrefs [i].src_scc_index < num_sccs);
691 g_assert (xrefs [i].dst_scc_index >= 0 && xrefs [i].dst_scc_index < num_sccs);
692 g_print ("%d -> %d\n", xrefs [i].src_scc_index, xrefs [i].dst_scc_index);
698 mono_sgen_register_test_bridge_callbacks (void)
700 MonoGCBridgeCallbacks callbacks;
701 callbacks.is_bridge_object = bridge_test_is_bridge_object;
702 callbacks.cross_references = bridge_test_cross_reference;
703 mono_gc_register_bridge_callbacks (&callbacks);