2 * sgen-fin-weak-hash.c: Finalizers and weak links.
5 * Paolo Molaro (lupus@ximian.com)
6 * Rodrigo Kumpera (kumpera@gmail.com)
8 * Copyright 2005-2011 Novell, Inc (http://www.novell.com)
9 * Copyright 2011 Xamarin Inc (http://www.xamarin.com)
10 * Copyright 2011 Xamarin, Inc.
11 * Copyright (C) 2012 Xamarin Inc
13 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
19 #include "mono/sgen/sgen-gc.h"
20 #include "mono/sgen/sgen-gray.h"
21 #include "mono/sgen/sgen-protocol.h"
22 #include "mono/sgen/sgen-pointer-queue.h"
23 #include "mono/sgen/sgen-client.h"
24 #include "mono/sgen/gc-internal-agnostic.h"
25 #include "mono/utils/mono-membar.h"
27 #define ptr_in_nursery sgen_ptr_in_nursery
29 typedef SgenGrayQueue GrayQueue;
31 static int no_finalize = 0;
34 * The finalizable hash has the object as the key, the
35 * disappearing_link hash, has the link address as key.
37 * Copyright 2011 Xamarin Inc.
40 #define TAG_MASK ((mword)0x1)
42 static inline GCObject*
43 tagged_object_get_object (GCObject *object)
45 return (GCObject*)(((mword)object) & ~TAG_MASK);
49 tagged_object_get_tag (GCObject *object)
51 return ((mword)object) & TAG_MASK;
54 static inline GCObject*
55 tagged_object_apply (void *object, int tag_bits)
57 return (GCObject*)((mword)object | (mword)tag_bits);
61 tagged_object_hash (GCObject *o)
63 return sgen_aligned_addr_hash (tagged_object_get_object (o));
67 tagged_object_equals (GCObject *a, GCObject *b)
69 return tagged_object_get_object (a) == tagged_object_get_object (b);
72 static SgenHashTable minor_finalizable_hash = SGEN_HASH_TABLE_INIT (INTERNAL_MEM_FIN_TABLE, INTERNAL_MEM_FINALIZE_ENTRY, 0, (GHashFunc)tagged_object_hash, (GEqualFunc)tagged_object_equals);
73 static SgenHashTable major_finalizable_hash = SGEN_HASH_TABLE_INIT (INTERNAL_MEM_FIN_TABLE, INTERNAL_MEM_FINALIZE_ENTRY, 0, (GHashFunc)tagged_object_hash, (GEqualFunc)tagged_object_equals);
76 get_finalize_entry_hash_table (int generation)
79 case GENERATION_NURSERY: return &minor_finalizable_hash;
80 case GENERATION_OLD: return &major_finalizable_hash;
81 default: g_assert_not_reached ();
85 #define BRIDGE_OBJECT_MARKED 0x1
87 /* LOCKING: requires that the GC lock is held */
89 sgen_mark_bridge_object (GCObject *obj)
91 SgenHashTable *hash_table = get_finalize_entry_hash_table (ptr_in_nursery (obj) ? GENERATION_NURSERY : GENERATION_OLD);
93 sgen_hash_table_set_key (hash_table, obj, tagged_object_apply (obj, BRIDGE_OBJECT_MARKED));
96 /* LOCKING: requires that the GC lock is held */
98 sgen_collect_bridge_objects (int generation, ScanCopyContext ctx)
100 CopyOrMarkObjectFunc copy_func = ctx.ops->copy_or_mark_object;
101 GrayQueue *queue = ctx.queue;
102 SgenHashTable *hash_table = get_finalize_entry_hash_table (generation);
104 gpointer dummy G_GNUC_UNUSED;
106 SgenPointerQueue moved_fin_objects;
108 sgen_pointer_queue_init (&moved_fin_objects, INTERNAL_MEM_TEMPORARY);
113 SGEN_HASH_TABLE_FOREACH (hash_table, GCObject *, object, gpointer, dummy) {
114 int tag = tagged_object_get_tag (object);
115 object = tagged_object_get_object (object);
117 /* Bridge code told us to ignore this one */
118 if (tag == BRIDGE_OBJECT_MARKED)
121 /* Object is a bridge object and major heap says it's dead */
122 if (major_collector.is_object_live (object))
125 /* Nursery says the object is dead. */
126 if (!sgen_gc_is_object_ready_for_finalization (object))
129 if (!sgen_client_bridge_is_bridge_object (object))
133 copy_func (©, queue);
135 sgen_client_bridge_register_finalized_object (copy);
137 if (hash_table == &minor_finalizable_hash && !ptr_in_nursery (copy)) {
138 /* remove from the list */
139 SGEN_HASH_TABLE_FOREACH_REMOVE (TRUE);
141 /* insert it into the major hash */
142 sgen_hash_table_replace (&major_finalizable_hash, tagged_object_apply (copy, tag), NULL, NULL);
144 SGEN_LOG (5, "Promoting finalization of object %p (%s) (was at %p) to major table", copy, sgen_client_vtable_get_name (SGEN_LOAD_VTABLE (copy)), object);
147 } else if (copy != object) {
149 SGEN_HASH_TABLE_FOREACH_REMOVE (TRUE);
151 /* register for reinsertion */
152 sgen_pointer_queue_add (&moved_fin_objects, tagged_object_apply (copy, tag));
154 SGEN_LOG (5, "Updating object for finalization: %p (%s) (was at %p)", copy, sgen_client_vtable_get_name (SGEN_LOAD_VTABLE (copy)), object);
158 } SGEN_HASH_TABLE_FOREACH_END;
160 while (!sgen_pointer_queue_is_empty (&moved_fin_objects)) {
161 sgen_hash_table_replace (hash_table, sgen_pointer_queue_pop (&moved_fin_objects), NULL, NULL);
164 sgen_pointer_queue_free (&moved_fin_objects);
168 /* LOCKING: requires that the GC lock is held */
170 sgen_finalize_in_range (int generation, ScanCopyContext ctx)
172 CopyOrMarkObjectFunc copy_func = ctx.ops->copy_or_mark_object;
173 GrayQueue *queue = ctx.queue;
174 SgenHashTable *hash_table = get_finalize_entry_hash_table (generation);
176 gpointer dummy G_GNUC_UNUSED;
177 SgenPointerQueue moved_fin_objects;
179 sgen_pointer_queue_init (&moved_fin_objects, INTERNAL_MEM_TEMPORARY);
183 SGEN_HASH_TABLE_FOREACH (hash_table, GCObject *, object, gpointer, dummy) {
184 int tag = tagged_object_get_tag (object);
185 object = tagged_object_get_object (object);
186 if (!major_collector.is_object_live (object)) {
187 gboolean is_fin_ready = sgen_gc_is_object_ready_for_finalization (object);
188 GCObject *copy = object;
189 copy_func (©, queue);
191 /* remove and put in fin_ready_list */
192 SGEN_HASH_TABLE_FOREACH_REMOVE (TRUE);
193 sgen_queue_finalization_entry (copy);
194 /* Make it survive */
195 SGEN_LOG (5, "Queueing object for finalization: %p (%s) (was at %p) (%d)", copy, sgen_client_vtable_get_name (SGEN_LOAD_VTABLE (copy)), object, sgen_hash_table_num_entries (hash_table));
198 if (hash_table == &minor_finalizable_hash && !ptr_in_nursery (copy)) {
199 /* remove from the list */
200 SGEN_HASH_TABLE_FOREACH_REMOVE (TRUE);
202 /* insert it into the major hash */
203 sgen_hash_table_replace (&major_finalizable_hash, tagged_object_apply (copy, tag), NULL, NULL);
205 SGEN_LOG (5, "Promoting finalization of object %p (%s) (was at %p) to major table", copy, sgen_client_vtable_get_name (SGEN_LOAD_VTABLE (copy)), object);
208 } else if (copy != object) {
210 SGEN_HASH_TABLE_FOREACH_REMOVE (TRUE);
212 /* register for reinsertion */
213 sgen_pointer_queue_add (&moved_fin_objects, tagged_object_apply (copy, tag));
215 SGEN_LOG (5, "Updating object for finalization: %p (%s) (was at %p)", copy, sgen_client_vtable_get_name (SGEN_LOAD_VTABLE (copy)), object);
221 } SGEN_HASH_TABLE_FOREACH_END;
223 while (!sgen_pointer_queue_is_empty (&moved_fin_objects)) {
224 sgen_hash_table_replace (hash_table, sgen_pointer_queue_pop (&moved_fin_objects), NULL, NULL);
227 sgen_pointer_queue_free (&moved_fin_objects);
230 /* LOCKING: requires that the GC lock is held */
232 register_for_finalization (GCObject *obj, void *user_data, int generation)
234 SgenHashTable *hash_table = get_finalize_entry_hash_table (generation);
240 if (sgen_hash_table_replace (hash_table, obj, NULL, NULL)) {
241 GCVTable vt = SGEN_LOAD_VTABLE_UNCHECKED (obj);
242 SGEN_LOG (5, "Added finalizer for object: %p (%s) (%d) to %s table", obj, sgen_client_vtable_get_name (vt), hash_table->num_entries, sgen_generation_name (generation));
245 if (sgen_hash_table_remove (hash_table, obj, NULL)) {
246 GCVTable vt = SGEN_LOAD_VTABLE_UNCHECKED (obj);
247 SGEN_LOG (5, "Removed finalizer for object: %p (%s) (%d)", obj, sgen_client_vtable_get_name (vt), hash_table->num_entries);
253 * We're using (mostly) non-locking staging queues for finalizers and weak links to speed
254 * up registering them. Otherwise we'd have to take the GC lock.
256 * The queues are arrays of `StageEntry`, plus a `next_entry` index. Threads add entries to
257 * the queue via `add_stage_entry()` in a linear fashion until it fills up, in which case
258 * `process_stage_entries()` is called to drain it. A garbage collection will also drain
259 * the queues via the same function. That implies that `add_stage_entry()`, since it
260 * doesn't take a lock, must be able to run concurrently with `process_stage_entries()`,
261 * though it doesn't have to make progress while the queue is drained. In fact, once it
262 * detects that the queue is being drained, it blocks until the draining is done.
264 * The protocol must guarantee that entries in the queue are causally ordered, otherwise two
265 * entries for the same location might get switched, resulting in the earlier one being
266 * committed and the later one ignored.
268 * `next_entry` is the index of the next entry to be filled, or `-1` if the queue is
269 * currently being drained. Each entry has a state:
271 * `STAGE_ENTRY_FREE`: The entry is free. Its data fields must be `NULL`.
273 * `STAGE_ENTRY_BUSY`: The entry is currently being filled in.
275 * `STAGE_ENTRY_USED`: The entry is completely filled in and must be processed in the next
278 * `STAGE_ENTRY_INVALID`: The entry was busy during queue draining and therefore
279 * invalidated. Entries that are `BUSY` can obviously not be processed during a drain, but
280 * we can't leave them in place because new entries might be inserted before them, including
281 * from the same thread, violating causality. An alternative would be not to reset
282 * `next_entry` to `0` after a drain, but to the index of the last `BUSY` entry plus one,
283 * but that can potentially waste the whole queue.
287 * | from | to | filler? | drainer? |
288 * +---------+---------+---------+----------+
289 * | FREE | BUSY | X | |
290 * | BUSY | FREE | X | |
291 * | BUSY | USED | X | |
292 * | BUSY | INVALID | | X |
293 * | USED | FREE | | X |
294 * | INVALID | FREE | X | |
296 * `next_entry` can be incremented either by the filler thread that set the corresponding
297 * entry to `BUSY`, or by another filler thread that's trying to get a `FREE` slot. If that
298 * other thread wasn't allowed to increment, it would block on the first filler thread.
300 * An entry's state, once it's set from `FREE` to `BUSY` by a filler thread, can only be
301 * changed by that same thread or by the drained. The drainer can only set a `BUSY` thread
302 * to `INVALID`, so it needs to be set to `FREE` again by the original filler thread.
305 #define STAGE_ENTRY_FREE 0
306 #define STAGE_ENTRY_BUSY 1
307 #define STAGE_ENTRY_USED 2
308 #define STAGE_ENTRY_INVALID 3
311 volatile gint32 state;
316 #define NUM_FIN_STAGE_ENTRIES 1024
318 static volatile gint32 next_fin_stage_entry = 0;
319 static StageEntry fin_stage_entries [NUM_FIN_STAGE_ENTRIES];
322 * This is used to lock the stage when processing is forced, i.e. when it's triggered by a
323 * garbage collection. In that case, the world is already stopped and there's only one
324 * thread operating on the queue.
327 lock_stage_for_processing (volatile gint32 *next_entry)
333 * When processing is triggered by an overflow, we don't want to take the GC lock
334 * immediately, and then set `next_index` to `-1`, because another thread might have drained
335 * the queue in the mean time. Instead, we make sure the overflow is still there, we
336 * atomically set `next_index`, and only once that happened do we take the GC lock.
339 try_lock_stage_for_processing (int num_entries, volatile gint32 *next_entry)
341 gint32 old = *next_entry;
342 if (old < num_entries)
344 return InterlockedCompareExchange (next_entry, -1, old) == old;
347 /* LOCKING: requires that the GC lock is held */
349 process_stage_entries (int num_entries, volatile gint32 *next_entry, StageEntry *entries, void (*process_func) (GCObject*, void*, int))
354 * This can happen if after setting `next_index` to `-1` in
355 * `try_lock_stage_for_processing()`, a GC was triggered, which then drained the
356 * queue and reset `next_entry`.
358 * We have the GC lock now, so if it's still `-1`, we can't be interrupted by a GC.
360 if (*next_entry != -1)
363 for (i = 0; i < num_entries; ++i) {
367 state = entries [i].state;
370 case STAGE_ENTRY_FREE:
371 case STAGE_ENTRY_INVALID:
373 case STAGE_ENTRY_BUSY:
374 /* BUSY -> INVALID */
376 * This must be done atomically, because the filler thread can set
377 * the entry to `USED`, in which case we must process it, so we must
378 * detect that eventuality.
380 if (InterlockedCompareExchange (&entries [i].state, STAGE_ENTRY_INVALID, STAGE_ENTRY_BUSY) != STAGE_ENTRY_BUSY)
383 case STAGE_ENTRY_USED:
386 SGEN_ASSERT (0, FALSE, "Invalid stage entry state");
392 process_func (entries [i].obj, entries [i].user_data, i);
394 entries [i].obj = NULL;
395 entries [i].user_data = NULL;
397 mono_memory_write_barrier ();
401 * This transition only happens here, so we don't have to do it atomically.
403 entries [i].state = STAGE_ENTRY_FREE;
406 mono_memory_write_barrier ();
411 #ifdef HEAVY_STATISTICS
412 static guint64 stat_overflow_abort = 0;
413 static guint64 stat_wait_for_processing = 0;
414 static guint64 stat_increment_other_thread = 0;
415 static guint64 stat_index_decremented = 0;
416 static guint64 stat_entry_invalidated = 0;
417 static guint64 stat_success = 0;
421 add_stage_entry (int num_entries, volatile gint32 *next_entry, StageEntry *entries, GCObject *obj, void *user_data)
423 gint32 index, new_next_entry, old_next_entry;
424 gint32 previous_state;
429 if (index >= num_entries) {
430 HEAVY_STAT (++stat_overflow_abort);
435 * Backed-off waiting is way more efficient than even using a
436 * dedicated lock for this.
438 while ((index = *next_entry) < 0) {
440 * This seems like a good value. Determined by timing
441 * sgen-weakref-stress.exe.
443 mono_thread_info_usleep (200);
444 HEAVY_STAT (++stat_wait_for_processing);
449 if (entries [index].state != STAGE_ENTRY_FREE ||
450 InterlockedCompareExchange (&entries [index].state, STAGE_ENTRY_BUSY, STAGE_ENTRY_FREE) != STAGE_ENTRY_FREE) {
452 * If we can't get the entry it must be because another thread got
453 * it first. We don't want to wait for that thread to increment
454 * `next_entry`, so we try to do it ourselves. Whether we succeed
455 * or not, we start over.
457 if (*next_entry == index) {
458 InterlockedCompareExchange (next_entry, index + 1, index);
459 //g_print ("tried increment for other thread\n");
460 HEAVY_STAT (++stat_increment_other_thread);
464 /* state is BUSY now */
465 mono_memory_write_barrier ();
467 * Incrementing `next_entry` must happen after setting the state to `BUSY`.
468 * If it were the other way around, it would be possible that after a filler
469 * incremented the index, other threads fill up the queue, the queue is
470 * drained, the original filler finally fills in the slot, but `next_entry`
471 * ends up at the start of the queue, and new entries are written in the
472 * queue in front of, not behind, the original filler's entry.
474 * We don't actually require that the CAS succeeds, but we do require that
475 * the value of `next_entry` is not lower than our index. Since the drainer
476 * sets it to `-1`, that also takes care of the case that the drainer is
479 old_next_entry = InterlockedCompareExchange (next_entry, index + 1, index);
480 if (old_next_entry < index) {
482 /* INVALID -> FREE */
484 * The state might still be `BUSY`, or the drainer could have set it
485 * to `INVALID`. In either case, there's no point in CASing. Set
486 * it to `FREE` and start over.
488 entries [index].state = STAGE_ENTRY_FREE;
489 HEAVY_STAT (++stat_index_decremented);
495 SGEN_ASSERT (0, index >= 0 && index < num_entries, "Invalid index");
497 entries [index].obj = obj;
498 entries [index].user_data = user_data;
500 mono_memory_write_barrier ();
502 new_next_entry = *next_entry;
503 mono_memory_read_barrier ();
506 * A `BUSY` entry will either still be `BUSY` or the drainer will have set it to
507 * `INVALID`. In the former case, we set it to `USED` and we're finished. In the
508 * latter case, we reset it to `FREE` and start over.
510 previous_state = InterlockedCompareExchange (&entries [index].state, STAGE_ENTRY_USED, STAGE_ENTRY_BUSY);
511 if (previous_state == STAGE_ENTRY_BUSY) {
512 SGEN_ASSERT (0, new_next_entry >= index || new_next_entry < 0, "Invalid next entry index - as long as we're busy, other thread can only increment or invalidate it");
513 HEAVY_STAT (++stat_success);
517 SGEN_ASSERT (0, previous_state == STAGE_ENTRY_INVALID, "Invalid state transition - other thread can only make busy state invalid");
518 entries [index].obj = NULL;
519 entries [index].user_data = NULL;
520 mono_memory_write_barrier ();
521 /* INVALID -> FREE */
522 entries [index].state = STAGE_ENTRY_FREE;
524 HEAVY_STAT (++stat_entry_invalidated);
529 /* LOCKING: requires that the GC lock is held */
531 process_fin_stage_entry (GCObject *obj, void *user_data, int index)
533 if (ptr_in_nursery (obj))
534 register_for_finalization (obj, user_data, GENERATION_NURSERY);
536 register_for_finalization (obj, user_data, GENERATION_OLD);
539 /* LOCKING: requires that the GC lock is held */
541 sgen_process_fin_stage_entries (void)
543 lock_stage_for_processing (&next_fin_stage_entry);
544 process_stage_entries (NUM_FIN_STAGE_ENTRIES, &next_fin_stage_entry, fin_stage_entries, process_fin_stage_entry);
548 sgen_object_register_for_finalization (GCObject *obj, void *user_data)
550 while (add_stage_entry (NUM_FIN_STAGE_ENTRIES, &next_fin_stage_entry, fin_stage_entries, obj, user_data) == -1) {
551 if (try_lock_stage_for_processing (NUM_FIN_STAGE_ENTRIES, &next_fin_stage_entry)) {
553 process_stage_entries (NUM_FIN_STAGE_ENTRIES, &next_fin_stage_entry, fin_stage_entries, process_fin_stage_entry);
559 /* LOCKING: requires that the GC lock is held */
561 finalizers_with_predicate (SgenObjectPredicateFunc predicate, void *user_data, GCObject **out_array, int out_size, SgenHashTable *hash_table)
564 gpointer dummy G_GNUC_UNUSED;
567 if (no_finalize || !out_size || !out_array)
570 SGEN_HASH_TABLE_FOREACH (hash_table, GCObject *, object, gpointer, dummy) {
571 object = tagged_object_get_object (object);
573 if (predicate (object, user_data)) {
574 /* remove and put in out_array */
575 SGEN_HASH_TABLE_FOREACH_REMOVE (TRUE);
576 out_array [count ++] = object;
577 SGEN_LOG (5, "Collecting object for finalization: %p (%s) (%d)", object, sgen_client_vtable_get_name (SGEN_LOAD_VTABLE (object)), sgen_hash_table_num_entries (hash_table));
578 if (count == out_size)
582 } SGEN_HASH_TABLE_FOREACH_END;
587 * sgen_gather_finalizers_if:
588 * @predicate: predicate function
589 * @user_data: predicate function data argument
590 * @out_array: output array
591 * @out_size: size of output array
593 * Store inside @out_array up to @out_size objects that match @predicate. Returns the number
594 * of stored items. Can be called repeteadly until it returns 0.
596 * The items are removed from the finalizer data structure, so the caller is supposed
599 * @out_array me be on the stack, or registered as a root, to allow the GC to know the
600 * objects are still alive.
603 sgen_gather_finalizers_if (SgenObjectPredicateFunc predicate, void *user_data, GCObject **out_array, int out_size)
608 sgen_process_fin_stage_entries ();
609 result = finalizers_with_predicate (predicate, user_data, (GCObject**)out_array, out_size, &minor_finalizable_hash);
610 if (result < out_size) {
611 result += finalizers_with_predicate (predicate, user_data, (GCObject**)out_array + result, out_size - result,
612 &major_finalizable_hash);
620 sgen_remove_finalizers_if (SgenObjectPredicateFunc predicate, void *user_data, int generation)
622 SgenHashTable *hash_table = get_finalize_entry_hash_table (generation);
624 gpointer dummy G_GNUC_UNUSED;
626 SGEN_HASH_TABLE_FOREACH (hash_table, GCObject *, object, gpointer, dummy) {
627 object = tagged_object_get_object (object);
629 if (predicate (object, user_data)) {
630 SGEN_HASH_TABLE_FOREACH_REMOVE (TRUE);
633 } SGEN_HASH_TABLE_FOREACH_END;
637 sgen_init_fin_weak_hash (void)
639 #ifdef HEAVY_STATISTICS
640 mono_counters_register ("FinWeak Successes", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_success);
641 mono_counters_register ("FinWeak Overflow aborts", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_overflow_abort);
642 mono_counters_register ("FinWeak Wait for processing", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_wait_for_processing);
643 mono_counters_register ("FinWeak Increment other thread", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_increment_other_thread);
644 mono_counters_register ("FinWeak Index decremented", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_index_decremented);
645 mono_counters_register ("FinWeak Entry invalidated", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_entry_invalidated);
649 #endif /* HAVE_SGEN_GC */