mono/sgen/sgen-fin-weak-hash.c

   1 /*
   2  * sgen-fin-weak-hash.c: Finalizers and weak links.
   3  *
   4  * Author:
   5  *      Paolo Molaro (lupus@ximian.com)
   6  *  Rodrigo Kumpera (kumpera@gmail.com)
   7  *
   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
  12  *
  13  * This library is free software; you can redistribute it and/or
  14  * modify it under the terms of the GNU Library General Public
  15  * License 2.0 as published by the Free Software Foundation;
  16  *
  17  * This library is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  20  * Library General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Library General Public
  23  * License 2.0 along with this library; if not, write to the Free
  24  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  25  */
  26
  27 #include "config.h"
  28 #ifdef HAVE_SGEN_GC
  29
  30 #include "mono/sgen/sgen-gc.h"
  31 #include "mono/sgen/sgen-gray.h"
  32 #include "mono/sgen/sgen-protocol.h"
  33 #include "mono/sgen/sgen-pointer-queue.h"
  34 #include "mono/sgen/sgen-client.h"
  35 #include "mono/sgen/gc-internal-agnostic.h"
  36 #include "mono/utils/mono-membar.h"
  37
  38 #define ptr_in_nursery sgen_ptr_in_nursery
  39
  40 typedef SgenGrayQueue GrayQueue;
  41
  42 static int no_finalize = 0;
  43
  44 /*
  45  * The finalizable hash has the object as the key, the
  46  * disappearing_link hash, has the link address as key.
  47  *
  48  * Copyright 2011 Xamarin Inc.
  49  */
  50
  51 #define TAG_MASK ((mword)0x1)
  52
  53 static inline GCObject*
  54 tagged_object_get_object (GCObject *object)
  55 {
  56         return (GCObject*)(((mword)object) & ~TAG_MASK);
  57 }
  58
  59 static inline int
  60 tagged_object_get_tag (GCObject *object)
  61 {
  62         return ((mword)object) & TAG_MASK;
  63 }
  64
  65 static inline GCObject*
  66 tagged_object_apply (void *object, int tag_bits)
  67 {
  68        return (GCObject*)((mword)object | (mword)tag_bits);
  69 }
  70
  71 static int
  72 tagged_object_hash (GCObject *o)
  73 {
  74         return sgen_aligned_addr_hash (tagged_object_get_object (o));
  75 }
  76
  77 static gboolean
  78 tagged_object_equals (GCObject *a, GCObject *b)
  79 {
  80         return tagged_object_get_object (a) == tagged_object_get_object (b);
  81 }
  82
  83 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);
  84 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);
  85
  86 static SgenHashTable*
  87 get_finalize_entry_hash_table (int generation)
  88 {
  89         switch (generation) {
  90         case GENERATION_NURSERY: return &minor_finalizable_hash;
  91         case GENERATION_OLD: return &major_finalizable_hash;
  92         default: g_assert_not_reached ();
  93         }
  94 }
  95
  96 #define BRIDGE_OBJECT_MARKED 0x1
  97
  98 /* LOCKING: requires that the GC lock is held */
  99 void
 100 sgen_mark_bridge_object (GCObject *obj)
 101 {
 102         SgenHashTable *hash_table = get_finalize_entry_hash_table (ptr_in_nursery (obj) ? GENERATION_NURSERY : GENERATION_OLD);
 103
 104         sgen_hash_table_set_key (hash_table, obj, tagged_object_apply (obj, BRIDGE_OBJECT_MARKED));
 105 }
 106
 107 /* LOCKING: requires that the GC lock is held */
 108 void
 109 sgen_collect_bridge_objects (int generation, ScanCopyContext ctx)
 110 {
 111         CopyOrMarkObjectFunc copy_func = ctx.ops->copy_or_mark_object;
 112         GrayQueue *queue = ctx.queue;
 113         SgenHashTable *hash_table = get_finalize_entry_hash_table (generation);
 114         GCObject *object;
 115         gpointer dummy G_GNUC_UNUSED;
 116         GCObject *copy;
 117         SgenPointerQueue moved_fin_objects;
 118
 119         sgen_pointer_queue_init (&moved_fin_objects, INTERNAL_MEM_TEMPORARY);
 120
 121         if (no_finalize)
 122                 return;
 123
 124         SGEN_HASH_TABLE_FOREACH (hash_table, object, dummy) {
 125                 int tag = tagged_object_get_tag (object);
 126                 object = tagged_object_get_object (object);
 127
 128                 /* Bridge code told us to ignore this one */
 129                 if (tag == BRIDGE_OBJECT_MARKED)
 130                         continue;
 131
 132                 /* Object is a bridge object and major heap says it's dead  */
 133                 if (major_collector.is_object_live (object))
 134                         continue;
 135
 136                 /* Nursery says the object is dead. */
 137                 if (!sgen_gc_is_object_ready_for_finalization (object))
 138                         continue;
 139
 140                 if (!sgen_client_bridge_is_bridge_object (object))
 141                         continue;
 142
 143                 copy = object;
 144                 copy_func (&copy, queue);
 145
 146                 sgen_client_bridge_register_finalized_object (copy);
 147
 148                 if (hash_table == &minor_finalizable_hash && !ptr_in_nursery (copy)) {
 149                         /* remove from the list */
 150                         SGEN_HASH_TABLE_FOREACH_REMOVE (TRUE);
 151
 152                         /* insert it into the major hash */
 153                         sgen_hash_table_replace (&major_finalizable_hash, tagged_object_apply (copy, tag), NULL, NULL);
 154
 155                         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);
 156
 157                         continue;
 158                 } else if (copy != object) {
 159                         /* update pointer */
 160                         SGEN_HASH_TABLE_FOREACH_REMOVE (TRUE);
 161
 162                         /* register for reinsertion */
 163                         sgen_pointer_queue_add (&moved_fin_objects, tagged_object_apply (copy, tag));
 164
 165                         SGEN_LOG (5, "Updating object for finalization: %p (%s) (was at %p)", copy, sgen_client_vtable_get_name (SGEN_LOAD_VTABLE (copy)), object);
 166
 167                         continue;
 168                 }
 169         } SGEN_HASH_TABLE_FOREACH_END;
 170
 171         while (!sgen_pointer_queue_is_empty (&moved_fin_objects)) {
 172                 sgen_hash_table_replace (hash_table, sgen_pointer_queue_pop (&moved_fin_objects), NULL, NULL);
 173         }
 174
 175         sgen_pointer_queue_free (&moved_fin_objects);
 176 }
 177
 178
 179 /* LOCKING: requires that the GC lock is held */
 180 void
 181 sgen_finalize_in_range (int generation, ScanCopyContext ctx)
 182 {
 183         CopyOrMarkObjectFunc copy_func = ctx.ops->copy_or_mark_object;
 184         GrayQueue *queue = ctx.queue;
 185         SgenHashTable *hash_table = get_finalize_entry_hash_table (generation);
 186         GCObject *object;
 187         gpointer dummy G_GNUC_UNUSED;
 188         SgenPointerQueue moved_fin_objects;
 189
 190         sgen_pointer_queue_init (&moved_fin_objects, INTERNAL_MEM_TEMPORARY);
 191
 192         if (no_finalize)
 193                 return;
 194         SGEN_HASH_TABLE_FOREACH (hash_table, object, dummy) {
 195                 int tag = tagged_object_get_tag (object);
 196                 object = tagged_object_get_object (object);
 197                 if (!major_collector.is_object_live (object)) {
 198                         gboolean is_fin_ready = sgen_gc_is_object_ready_for_finalization (object);
 199                         GCObject *copy = object;
 200                         copy_func (&copy, queue);
 201                         if (is_fin_ready) {
 202                                 /* remove and put in fin_ready_list */
 203                                 SGEN_HASH_TABLE_FOREACH_REMOVE (TRUE);
 204                                 sgen_queue_finalization_entry (copy);
 205                                 /* Make it survive */
 206                                 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));
 207                                 continue;
 208                         } else {
 209                                 if (hash_table == &minor_finalizable_hash && !ptr_in_nursery (copy)) {
 210                                         /* remove from the list */
 211                                         SGEN_HASH_TABLE_FOREACH_REMOVE (TRUE);
 212
 213                                         /* insert it into the major hash */
 214                                         sgen_hash_table_replace (&major_finalizable_hash, tagged_object_apply (copy, tag), NULL, NULL);
 215
 216                                         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);
 217
 218                                         continue;
 219                                 } else if (copy != object) {
 220                                         /* update pointer */
 221                                         SGEN_HASH_TABLE_FOREACH_REMOVE (TRUE);
 222
 223                                         /* register for reinsertion */
 224                                         sgen_pointer_queue_add (&moved_fin_objects, tagged_object_apply (copy, tag));
 225
 226                                         SGEN_LOG (5, "Updating object for finalization: %p (%s) (was at %p)", copy, sgen_client_vtable_get_name (SGEN_LOAD_VTABLE (copy)), object);
 227
 228                                         continue;
 229                                 }
 230                         }
 231                 }
 232         } SGEN_HASH_TABLE_FOREACH_END;
 233
 234         while (!sgen_pointer_queue_is_empty (&moved_fin_objects)) {
 235                 sgen_hash_table_replace (hash_table, sgen_pointer_queue_pop (&moved_fin_objects), NULL, NULL);
 236         }
 237
 238         sgen_pointer_queue_free (&moved_fin_objects);
 239 }
 240
 241 /* LOCKING: requires that the GC lock is held */
 242 static void
 243 register_for_finalization (GCObject *obj, void *user_data, int generation)
 244 {
 245         SgenHashTable *hash_table = get_finalize_entry_hash_table (generation);
 246
 247         if (no_finalize)
 248                 return;
 249
 250         if (user_data) {
 251                 if (sgen_hash_table_replace (hash_table, obj, NULL, NULL)) {
 252                         GCVTable vt = SGEN_LOAD_VTABLE_UNCHECKED (obj);
 253                         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));
 254                 }
 255         } else {
 256                 if (sgen_hash_table_remove (hash_table, obj, NULL)) {
 257                         GCVTable vt = SGEN_LOAD_VTABLE_UNCHECKED (obj);
 258                         SGEN_LOG (5, "Removed finalizer for object: %p (%s) (%d)", obj, sgen_client_vtable_get_name (vt), hash_table->num_entries);
 259                 }
 260         }
 261 }
 262
 263 /*
 264  * We're using (mostly) non-locking staging queues for finalizers and weak links to speed
 265  * up registering them.  Otherwise we'd have to take the GC lock.
 266  *
 267  * The queues are arrays of `StageEntry`, plus a `next_entry` index.  Threads add entries to
 268  * the queue via `add_stage_entry()` in a linear fashion until it fills up, in which case
 269  * `process_stage_entries()` is called to drain it.  A garbage collection will also drain
 270  * the queues via the same function.  That implies that `add_stage_entry()`, since it
 271  * doesn't take a lock, must be able to run concurrently with `process_stage_entries()`,
 272  * though it doesn't have to make progress while the queue is drained.  In fact, once it
 273  * detects that the queue is being drained, it blocks until the draining is done.
 274  *
 275  * The protocol must guarantee that entries in the queue are causally ordered, otherwise two
 276  * entries for the same location might get switched, resulting in the earlier one being
 277  * committed and the later one ignored.
 278  *
 279  * `next_entry` is the index of the next entry to be filled, or `-1` if the queue is
 280  * currently being drained.  Each entry has a state:
 281  *
 282  * `STAGE_ENTRY_FREE`: The entry is free.  Its data fields must be `NULL`.
 283  *
 284  * `STAGE_ENTRY_BUSY`: The entry is currently being filled in.
 285  *
 286  * `STAGE_ENTRY_USED`: The entry is completely filled in and must be processed in the next
 287  * draining round.
 288  *
 289  * `STAGE_ENTRY_INVALID`: The entry was busy during queue draining and therefore
 290  * invalidated.  Entries that are `BUSY` can obviously not be processed during a drain, but
 291  * we can't leave them in place because new entries might be inserted before them, including
 292  * from the same thread, violating causality.  An alternative would be not to reset
 293  * `next_entry` to `0` after a drain, but to the index of the last `BUSY` entry plus one,
 294  * but that can potentially waste the whole queue.
 295  *
 296  * State transitions:
 297  *
 298  * | from    | to      | filler? | drainer? |
 299  * +---------+---------+---------+----------+
 300  * | FREE    | BUSY    | X       |          |
 301  * | BUSY    | FREE    | X       |          |
 302  * | BUSY    | USED    | X       |          |
 303  * | BUSY    | INVALID |         | X        |
 304  * | USED    | FREE    |         | X        |
 305  * | INVALID | FREE    | X       |          |
 306  *
 307  * `next_entry` can be incremented either by the filler thread that set the corresponding
 308  * entry to `BUSY`, or by another filler thread that's trying to get a `FREE` slot.  If that
 309  * other thread wasn't allowed to increment, it would block on the first filler thread.
 310  *
 311  * An entry's state, once it's set from `FREE` to `BUSY` by a filler thread, can only be
 312  * changed by that same thread or by the drained.  The drainer can only set a `BUSY` thread
 313  * to `INVALID`, so it needs to be set to `FREE` again by the original filler thread.
 314  */
 315
 316 #define STAGE_ENTRY_FREE        0
 317 #define STAGE_ENTRY_BUSY        1
 318 #define STAGE_ENTRY_USED        2
 319 #define STAGE_ENTRY_INVALID     3
 320
 321 typedef struct {
 322         volatile gint32 state;
 323         GCObject *obj;
 324         void *user_data;
 325 } StageEntry;
 326
 327 #define NUM_FIN_STAGE_ENTRIES   1024
 328
 329 static volatile gint32 next_fin_stage_entry = 0;
 330 static StageEntry fin_stage_entries [NUM_FIN_STAGE_ENTRIES];
 331
 332 /*
 333  * This is used to lock the stage when processing is forced, i.e. when it's triggered by a
 334  * garbage collection.  In that case, the world is already stopped and there's only one
 335  * thread operating on the queue.
 336  */
 337 static void
 338 lock_stage_for_processing (volatile gint32 *next_entry)
 339 {
 340         *next_entry = -1;
 341 }
 342
 343 /*
 344  * When processing is triggered by an overflow, we don't want to take the GC lock
 345  * immediately, and then set `next_index` to `-1`, because another thread might have drained
 346  * the queue in the mean time.  Instead, we make sure the overflow is still there, we
 347  * atomically set `next_index`, and only once that happened do we take the GC lock.
 348  */
 349 static gboolean
 350 try_lock_stage_for_processing (int num_entries, volatile gint32 *next_entry)
 351 {
 352         gint32 old = *next_entry;
 353         if (old < num_entries)
 354                 return FALSE;
 355         return InterlockedCompareExchange (next_entry, -1, old) == old;
 356 }
 357
 358 /* LOCKING: requires that the GC lock is held */
 359 static void
 360 process_stage_entries (int num_entries, volatile gint32 *next_entry, StageEntry *entries, void (*process_func) (GCObject*, void*, int))
 361 {
 362         int i;
 363
 364         /*
 365          * This can happen if after setting `next_index` to `-1` in
 366          * `try_lock_stage_for_processing()`, a GC was triggered, which then drained the
 367          * queue and reset `next_entry`.
 368          *
 369          * We have the GC lock now, so if it's still `-1`, we can't be interrupted by a GC.
 370          */
 371         if (*next_entry != -1)
 372                 return;
 373
 374         for (i = 0; i < num_entries; ++i) {
 375                 gint32 state;
 376
 377         retry:
 378                 state = entries [i].state;
 379
 380                 switch (state) {
 381                 case STAGE_ENTRY_FREE:
 382                 case STAGE_ENTRY_INVALID:
 383                         continue;
 384                 case STAGE_ENTRY_BUSY:
 385                         /* BUSY -> INVALID */
 386                         /*
 387                          * This must be done atomically, because the filler thread can set
 388                          * the entry to `USED`, in which case we must process it, so we must
 389                          * detect that eventuality.
 390                          */
 391                         if (InterlockedCompareExchange (&entries [i].state, STAGE_ENTRY_INVALID, STAGE_ENTRY_BUSY) != STAGE_ENTRY_BUSY)
 392                                 goto retry;
 393                         continue;
 394                 case STAGE_ENTRY_USED:
 395                         break;
 396                 default:
 397                         SGEN_ASSERT (0, FALSE, "Invalid stage entry state");
 398                         break;
 399                 }
 400
 401                 /* state is USED */
 402
 403                 process_func (entries [i].obj, entries [i].user_data, i);
 404
 405                 entries [i].obj = NULL;
 406                 entries [i].user_data = NULL;
 407
 408                 mono_memory_write_barrier ();
 409
 410                 /* USED -> FREE */
 411                 /*
 412                  * This transition only happens here, so we don't have to do it atomically.
 413                  */
 414                 entries [i].state = STAGE_ENTRY_FREE;
 415         }
 416
 417         mono_memory_write_barrier ();
 418
 419         *next_entry = 0;
 420 }
 421
 422 #ifdef HEAVY_STATISTICS
 423 static guint64 stat_overflow_abort = 0;
 424 static guint64 stat_wait_for_processing = 0;
 425 static guint64 stat_increment_other_thread = 0;
 426 static guint64 stat_index_decremented = 0;
 427 static guint64 stat_entry_invalidated = 0;
 428 static guint64 stat_success = 0;
 429 #endif
 430
 431 static int
 432 add_stage_entry (int num_entries, volatile gint32 *next_entry, StageEntry *entries, GCObject *obj, void *user_data)
 433 {
 434         gint32 index, new_next_entry, old_next_entry;
 435         gint32 previous_state;
 436
 437  retry:
 438         for (;;) {
 439                 index = *next_entry;
 440                 if (index >= num_entries) {
 441                         HEAVY_STAT (++stat_overflow_abort);
 442                         return -1;
 443                 }
 444                 if (index < 0) {
 445                         /*
 446                          * Backed-off waiting is way more efficient than even using a
 447                          * dedicated lock for this.
 448                          */
 449                         while ((index = *next_entry) < 0) {
 450                                 /*
 451                                  * This seems like a good value.  Determined by timing
 452                                  * sgen-weakref-stress.exe.
 453                                  */
 454                                 g_usleep (200);
 455                                 HEAVY_STAT (++stat_wait_for_processing);
 456                         }
 457                         continue;
 458                 }
 459                 /* FREE -> BUSY */
 460                 if (entries [index].state != STAGE_ENTRY_FREE ||
 461                                 InterlockedCompareExchange (&entries [index].state, STAGE_ENTRY_BUSY, STAGE_ENTRY_FREE) != STAGE_ENTRY_FREE) {
 462                         /*
 463                          * If we can't get the entry it must be because another thread got
 464                          * it first.  We don't want to wait for that thread to increment
 465                          * `next_entry`, so we try to do it ourselves.  Whether we succeed
 466                          * or not, we start over.
 467                          */
 468                         if (*next_entry == index) {
 469                                 InterlockedCompareExchange (next_entry, index + 1, index);
 470                                 //g_print ("tried increment for other thread\n");
 471                                 HEAVY_STAT (++stat_increment_other_thread);
 472                         }
 473                         continue;
 474                 }
 475                 /* state is BUSY now */
 476                 mono_memory_write_barrier ();
 477                 /*
 478                  * Incrementing `next_entry` must happen after setting the state to `BUSY`.
 479                  * If it were the other way around, it would be possible that after a filler
 480                  * incremented the index, other threads fill up the queue, the queue is
 481                  * drained, the original filler finally fills in the slot, but `next_entry`
 482                  * ends up at the start of the queue, and new entries are written in the
 483                  * queue in front of, not behind, the original filler's entry.
 484                  *
 485                  * We don't actually require that the CAS succeeds, but we do require that
 486                  * the value of `next_entry` is not lower than our index.  Since the drainer
 487                  * sets it to `-1`, that also takes care of the case that the drainer is
 488                  * currently running.
 489                  */
 490                 old_next_entry = InterlockedCompareExchange (next_entry, index + 1, index);
 491                 if (old_next_entry < index) {
 492                         /* BUSY -> FREE */
 493                         /* INVALID -> FREE */
 494                         /*
 495                          * The state might still be `BUSY`, or the drainer could have set it
 496                          * to `INVALID`.  In either case, there's no point in CASing.  Set
 497                          * it to `FREE` and start over.
 498                          */
 499                         entries [index].state = STAGE_ENTRY_FREE;
 500                         HEAVY_STAT (++stat_index_decremented);
 501                         continue;
 502                 }
 503                 break;
 504         }
 505
 506         SGEN_ASSERT (0, index >= 0 && index < num_entries, "Invalid index");
 507
 508         entries [index].obj = obj;
 509         entries [index].user_data = user_data;
 510
 511         mono_memory_write_barrier ();
 512
 513         new_next_entry = *next_entry;
 514         mono_memory_read_barrier ();
 515         /* BUSY -> USED */
 516         /*
 517          * A `BUSY` entry will either still be `BUSY` or the drainer will have set it to
 518          * `INVALID`.  In the former case, we set it to `USED` and we're finished.  In the
 519          * latter case, we reset it to `FREE` and start over.
 520          */
 521         previous_state = InterlockedCompareExchange (&entries [index].state, STAGE_ENTRY_USED, STAGE_ENTRY_BUSY);
 522         if (previous_state == STAGE_ENTRY_BUSY) {
 523                 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");
 524                 HEAVY_STAT (++stat_success);
 525                 return index;
 526         }
 527
 528         SGEN_ASSERT (0, previous_state == STAGE_ENTRY_INVALID, "Invalid state transition - other thread can only make busy state invalid");
 529         entries [index].obj = NULL;
 530         entries [index].user_data = NULL;
 531         mono_memory_write_barrier ();
 532         /* INVALID -> FREE */
 533         entries [index].state = STAGE_ENTRY_FREE;
 534
 535         HEAVY_STAT (++stat_entry_invalidated);
 536
 537         goto retry;
 538 }
 539
 540 /* LOCKING: requires that the GC lock is held */
 541 static void
 542 process_fin_stage_entry (GCObject *obj, void *user_data, int index)
 543 {
 544         if (ptr_in_nursery (obj))
 545                 register_for_finalization (obj, user_data, GENERATION_NURSERY);
 546         else
 547                 register_for_finalization (obj, user_data, GENERATION_OLD);
 548 }
 549
 550 /* LOCKING: requires that the GC lock is held */
 551 void
 552 sgen_process_fin_stage_entries (void)
 553 {
 554         lock_stage_for_processing (&next_fin_stage_entry);
 555         process_stage_entries (NUM_FIN_STAGE_ENTRIES, &next_fin_stage_entry, fin_stage_entries, process_fin_stage_entry);
 556 }
 557
 558 void
 559 sgen_object_register_for_finalization (GCObject *obj, void *user_data)
 560 {
 561         while (add_stage_entry (NUM_FIN_STAGE_ENTRIES, &next_fin_stage_entry, fin_stage_entries, obj, user_data) == -1) {
 562                 if (try_lock_stage_for_processing (NUM_FIN_STAGE_ENTRIES, &next_fin_stage_entry)) {
 563                         LOCK_GC;
 564                         process_stage_entries (NUM_FIN_STAGE_ENTRIES, &next_fin_stage_entry, fin_stage_entries, process_fin_stage_entry);
 565                         UNLOCK_GC;
 566                 }
 567         }
 568 }
 569
 570 /* LOCKING: requires that the GC lock is held */
 571 static int
 572 finalizers_with_predicate (SgenObjectPredicateFunc predicate, void *user_data, GCObject **out_array, int out_size, SgenHashTable *hash_table)
 573 {
 574         GCObject *object;
 575         gpointer dummy G_GNUC_UNUSED;
 576         int count;
 577
 578         if (no_finalize || !out_size || !out_array)
 579                 return 0;
 580         count = 0;
 581         SGEN_HASH_TABLE_FOREACH (hash_table, object, dummy) {
 582                 object = tagged_object_get_object (object);
 583
 584                 if (predicate (object, user_data)) {
 585                         /* remove and put in out_array */
 586                         SGEN_HASH_TABLE_FOREACH_REMOVE (TRUE);
 587                         out_array [count ++] = object;
 588                         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));
 589                         if (count == out_size)
 590                                 return count;
 591                         continue;
 592                 }
 593         } SGEN_HASH_TABLE_FOREACH_END;
 594         return count;
 595 }
 596
 597 /**
 598  * sgen_gather_finalizers_if:
 599  * @predicate: predicate function
 600  * @user_data: predicate function data argument
 601  * @out_array: output array
 602  * @out_size: size of output array
 603  *
 604  * Store inside @out_array up to @out_size objects that match @predicate. Returns the number
 605  * of stored items. Can be called repeteadly until it returns 0.
 606  *
 607  * The items are removed from the finalizer data structure, so the caller is supposed
 608  * to finalize them.
 609  *
 610  * @out_array me be on the stack, or registered as a root, to allow the GC to know the
 611  * objects are still alive.
 612  */
 613 int
 614 sgen_gather_finalizers_if (SgenObjectPredicateFunc predicate, void *user_data, GCObject **out_array, int out_size)
 615 {
 616         int result;
 617
 618         LOCK_GC;
 619         sgen_process_fin_stage_entries ();
 620         result = finalizers_with_predicate (predicate, user_data, (GCObject**)out_array, out_size, &minor_finalizable_hash);
 621         if (result < out_size) {
 622                 result += finalizers_with_predicate (predicate, user_data, (GCObject**)out_array + result, out_size - result,
 623                         &major_finalizable_hash);
 624         }
 625         UNLOCK_GC;
 626
 627         return result;
 628 }
 629
 630 void
 631 sgen_remove_finalizers_if (SgenObjectPredicateFunc predicate, void *user_data, int generation)
 632 {
 633         SgenHashTable *hash_table = get_finalize_entry_hash_table (generation);
 634         GCObject *object;
 635         gpointer dummy G_GNUC_UNUSED;
 636
 637         SGEN_HASH_TABLE_FOREACH (hash_table, object, dummy) {
 638                 object = tagged_object_get_object (object);
 639
 640                 if (predicate (object, user_data)) {
 641                         SGEN_HASH_TABLE_FOREACH_REMOVE (TRUE);
 642                         continue;
 643                 }
 644         } SGEN_HASH_TABLE_FOREACH_END;
 645 }
 646
 647 /* GC Handles */
 648
 649 #ifdef HEAVY_STATISTICS
 650 static volatile guint64 stat_gc_handles_allocated = 0;
 651 static volatile guint64 stat_gc_handles_max_allocated = 0;
 652 #endif
 653
 654 #define BUCKETS (32 - MONO_GC_HANDLE_TYPE_SHIFT)
 655 #define MIN_BUCKET_BITS (5)
 656 #define MIN_BUCKET_SIZE (1 << MIN_BUCKET_BITS)
 657
 658 /*
 659  * A table of GC handle data, implementing a simple lock-free bitmap allocator.
 660  *
 661  * 'entries' is an array of pointers to buckets of increasing size. The first
 662  * bucket has size 'MIN_BUCKET_SIZE', and each bucket is twice the size of the
 663  * previous, i.e.:
 664  *
 665  *           |-------|-- MIN_BUCKET_SIZE
 666  *    [0] -> xxxxxxxx
 667  *    [1] -> xxxxxxxxxxxxxxxx
 668  *    [2] -> xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
 669  *    ...
 670  *
 671  * The size of the spine, 'BUCKETS', is chosen so that the maximum number of
 672  * entries is no less than the maximum index value of a GC handle.
 673  *
 674  * Each entry in a bucket is a pointer with two tag bits: if
 675  * 'GC_HANDLE_OCCUPIED' returns true for a slot, then the slot is occupied; if
 676  * so, then 'GC_HANDLE_VALID' gives whether the entry refers to a valid (1) or
 677  * NULL (0) object reference. If the reference is valid, then the pointer is an
 678  * object pointer. If the reference is NULL, and 'GC_HANDLE_TYPE_IS_WEAK' is
 679  * true for 'type', then the pointer is a metadata pointer--this allows us to
 680  * retrieve the domain ID of an expired weak reference in Mono.
 681  *
 682  * Finally, 'slot_hint' denotes the position of the last allocation, so that the
 683  * whole array needn't be searched on every allocation.
 684  */
 685
 686 typedef struct {
 687         volatile gpointer *volatile entries [BUCKETS];
 688         volatile guint32 capacity;
 689         volatile guint32 slot_hint;
 690         guint8 type;
 691 } HandleData;
 692
 693 static inline guint
 694 bucket_size (guint index)
 695 {
 696         return 1 << (index + MIN_BUCKET_BITS);
 697 }
 698
 699 /* Computes floor(log2(index + MIN_BUCKET_SIZE)) - 1, giving the index
 700  * of the bucket containing a slot.
 701  */
 702 static inline guint
 703 index_bucket (guint index)
 704 {
 705 #ifdef __GNUC__
 706         return CHAR_BIT * sizeof (index) - __builtin_clz (index + MIN_BUCKET_SIZE) - 1 - MIN_BUCKET_BITS;
 707 #else
 708         guint count = 0;
 709         index += MIN_BUCKET_SIZE;
 710         while (index) {
 711                 ++count;
 712                 index >>= 1;
 713         }
 714         return count - 1 - MIN_BUCKET_BITS;
 715 #endif
 716 }
 717
 718 static inline void
 719 bucketize (guint index, guint *bucket, guint *offset)
 720 {
 721         *bucket = index_bucket (index);
 722         *offset = index - bucket_size (*bucket) + MIN_BUCKET_SIZE;
 723 }
 724
 725 static inline gboolean
 726 try_set_slot (volatile gpointer *slot, GCObject *obj, gpointer old, GCHandleType type)
 727 {
 728         if (obj)
 729                 return InterlockedCompareExchangePointer (slot, MONO_GC_HANDLE_OBJECT_POINTER (obj, GC_HANDLE_TYPE_IS_WEAK (type)), old) == old;
 730         return InterlockedCompareExchangePointer (slot, MONO_GC_HANDLE_METADATA_POINTER (sgen_client_default_metadata (), GC_HANDLE_TYPE_IS_WEAK (type)), old) == old;
 731 }
 732
 733 /* Try to claim a slot by setting its occupied bit. */
 734 static inline gboolean
 735 try_occupy_slot (HandleData *handles, guint bucket, guint offset, GCObject *obj, gboolean track)
 736 {
 737         volatile gpointer *link_addr = &(handles->entries [bucket] [offset]);
 738         if (MONO_GC_HANDLE_OCCUPIED (*link_addr))
 739                 return FALSE;
 740         return try_set_slot (link_addr, obj, NULL, handles->type);
 741 }
 742
 743 #define EMPTY_HANDLE_DATA(type) { { NULL }, 0, 0, (type) }
 744
 745 /* weak and weak-track arrays will be allocated in malloc memory
 746  */
 747 static HandleData gc_handles [] = {
 748         EMPTY_HANDLE_DATA (HANDLE_WEAK),
 749         EMPTY_HANDLE_DATA (HANDLE_WEAK_TRACK),
 750         EMPTY_HANDLE_DATA (HANDLE_NORMAL),
 751         EMPTY_HANDLE_DATA (HANDLE_PINNED)
 752 };
 753
 754 static HandleData *
 755 gc_handles_for_type (GCHandleType type)
 756 {
 757         g_assert (type < HANDLE_TYPE_MAX);
 758         return &gc_handles [type];
 759 }
 760
 761 /* This assumes that the world is stopped. */
 762 void
 763 sgen_mark_normal_gc_handles (void *addr, SgenUserMarkFunc mark_func, void *gc_data)
 764 {
 765         HandleData *handles = gc_handles_for_type (HANDLE_NORMAL);
 766         size_t bucket, offset;
 767         const guint max_bucket = index_bucket (handles->capacity);
 768         for (bucket = 0; bucket < max_bucket; ++bucket) {
 769                 volatile gpointer *entries = handles->entries [bucket];
 770                 for (offset = 0; offset < bucket_size (bucket); ++offset) {
 771                         volatile gpointer *entry = &entries [offset];
 772                         gpointer hidden = *entry;
 773                         gpointer revealed = MONO_GC_REVEAL_POINTER (hidden, FALSE);
 774                         if (!MONO_GC_HANDLE_IS_OBJECT_POINTER (hidden))
 775                                 continue;
 776                         mark_func ((MonoObject **)&revealed, gc_data);
 777                         g_assert (revealed);
 778                         *entry = MONO_GC_HANDLE_OBJECT_POINTER (revealed, FALSE);
 779                 }
 780         }
 781 }
 782
 783 static guint
 784 handle_data_find_unset (HandleData *handles, guint32 begin, guint32 end)
 785 {
 786         guint index;
 787         gint delta = begin < end ? +1 : -1;
 788         for (index = begin; index < end; index += delta) {
 789                 guint bucket, offset;
 790                 volatile gpointer *entries;
 791                 bucketize (index, &bucket, &offset);
 792                 entries = handles->entries [bucket];
 793                 g_assert (entries);
 794                 if (!MONO_GC_HANDLE_OCCUPIED (entries [offset]))
 795                         return index;
 796         }
 797         return -1;
 798 }
 799
 800 /* Adds a bucket if necessary and possible. */
 801 static void
 802 handle_data_grow (HandleData *handles, guint32 old_capacity)
 803 {
 804         const guint new_bucket = index_bucket (old_capacity);
 805         const guint32 growth = bucket_size (new_bucket);
 806         const guint32 new_capacity = old_capacity + growth;
 807         gpointer *entries;
 808         const size_t new_bucket_size = sizeof (**handles->entries) * growth;
 809         if (handles->capacity >= new_capacity)
 810                 return;
 811         entries = g_malloc0 (new_bucket_size);
 812         if (handles->type == HANDLE_PINNED)
 813                 sgen_register_root ((char *)entries, new_bucket_size, SGEN_DESCRIPTOR_NULL, ROOT_TYPE_PINNED, MONO_ROOT_SOURCE_GC_HANDLE, "pinned gc handles");
 814         if (InterlockedCompareExchangePointer ((volatile gpointer *)&handles->entries [new_bucket], entries, NULL) == NULL) {
 815                 if (InterlockedCompareExchange ((volatile gint32 *)&handles->capacity, new_capacity, old_capacity) != old_capacity)
 816                         g_assert_not_reached ();
 817                 handles->slot_hint = old_capacity;
 818                 mono_memory_write_barrier ();
 819                 return;
 820         }
 821         /* Someone beat us to the allocation. */
 822         if (handles->type == HANDLE_PINNED)
 823                 sgen_deregister_root ((char *)entries);
 824         g_free (entries);
 825 }
 826
 827 static guint32
 828 alloc_handle (HandleData *handles, GCObject *obj, gboolean track)
 829 {
 830         guint index;
 831         guint32 res;
 832         guint bucket, offset;
 833         guint32 capacity;
 834         guint32 slot_hint;
 835         if (!handles->capacity)
 836                 handle_data_grow (handles, 0);
 837 retry:
 838         capacity = handles->capacity;
 839         slot_hint = handles->slot_hint;
 840         index = handle_data_find_unset (handles, slot_hint, capacity);
 841         if (index == -1)
 842                 index = handle_data_find_unset (handles, 0, slot_hint);
 843         if (index == -1) {
 844                 handle_data_grow (handles, capacity);
 845                 goto retry;
 846         }
 847         handles->slot_hint = index;
 848         bucketize (index, &bucket, &offset);
 849         if (!try_occupy_slot (handles, bucket, offset, obj, track))
 850                 goto retry;
 851 #ifdef HEAVY_STATISTICS
 852         InterlockedIncrement64 ((volatile gint64 *)&stat_gc_handles_allocated);
 853         if (stat_gc_handles_allocated > stat_gc_handles_max_allocated)
 854                 stat_gc_handles_max_allocated = stat_gc_handles_allocated;
 855 #endif
 856         if (obj && MONO_GC_HANDLE_TYPE_IS_WEAK (handles->type))
 857                 binary_protocol_dislink_add ((gpointer)&handles->entries [bucket] [offset], obj, track);
 858         /* Ensure that a GC handle cannot be given to another thread without the slot having been set. */
 859         mono_memory_write_barrier ();
 860         res = MONO_GC_HANDLE (index, handles->type);
 861         sgen_client_gchandle_created (handles->type, obj, res);
 862         return res;
 863 }
 864
 865 static gboolean
 866 object_older_than (GCObject *object, int generation)
 867 {
 868         return generation == GENERATION_NURSERY && !sgen_ptr_in_nursery (object);
 869 }
 870
 871 /*
 872  * Maps a function over all GC handles.
 873  * This assumes that the world is stopped!
 874  */
 875 void
 876 sgen_gchandle_iterate (GCHandleType handle_type, int max_generation, gpointer callback(gpointer, GCHandleType, int, gpointer), gpointer user)
 877 {
 878         HandleData *handle_data = gc_handles_for_type (handle_type);
 879         size_t bucket, offset;
 880         guint max_bucket = index_bucket (handle_data->capacity);
 881         /* If a new bucket has been allocated, but the capacity has not yet been
 882          * increased, nothing can yet have been allocated in the bucket because the
 883          * world is stopped, so we shouldn't miss any handles during iteration.
 884          */
 885         for (bucket = 0; bucket < max_bucket; ++bucket) {
 886                 volatile gpointer *entries = handle_data->entries [bucket];
 887                 for (offset = 0; offset < bucket_size (bucket); ++offset) {
 888                         gpointer hidden = entries [offset];
 889                         gpointer result;
 890                         /* Table must contain no garbage pointers. */
 891                         gboolean occupied = MONO_GC_HANDLE_OCCUPIED (hidden);
 892                         g_assert (hidden ? occupied : !occupied);
 893                         if (!occupied) // || !MONO_GC_HANDLE_VALID (hidden))
 894                                 continue;
 895                         result = callback (hidden, handle_type, max_generation, user);
 896                         if (result) {
 897                                 SGEN_ASSERT (0, MONO_GC_HANDLE_OCCUPIED (result), "Why did the callback return an unoccupied entry?");
 898                                 // FIXME: add the dislink_update protocol call here
 899                         } else {
 900                                 // FIXME: enable this for weak links
 901                                 //binary_protocol_dislink_remove ((gpointer)&handles->entries [bucket] [offset], handles->type == HANDLE_WEAK_TRACK);
 902                                 HEAVY_STAT (InterlockedDecrement64 ((volatile gint64 *)&stat_gc_handles_allocated));
 903                         }
 904                         entries [offset] = result;
 905                 }
 906         }
 907 }
 908
 909 /**
 910  * mono_gchandle_new:
 911  * @obj: managed object to get a handle for
 912  * @pinned: whether the object should be pinned
 913  *
 914  * This returns a handle that wraps the object, this is used to keep a
 915  * reference to a managed object from the unmanaged world and preventing the
 916  * object from being disposed.
 917  *
 918  * If @pinned is false the address of the object can not be obtained, if it is
 919  * true the address of the object can be obtained.  This will also pin the
 920  * object so it will not be possible by a moving garbage collector to move the
 921  * object.
 922  *
 923  * Returns: a handle that can be used to access the object from
 924  * unmanaged code.
 925  */
 926 guint32
 927 mono_gchandle_new (GCObject *obj, gboolean pinned)
 928 {
 929         return alloc_handle (gc_handles_for_type (pinned ? HANDLE_PINNED : HANDLE_NORMAL), obj, FALSE);
 930 }
 931
 932 /**
 933  * mono_gchandle_new_weakref:
 934  * @obj: managed object to get a handle for
 935  * @pinned: whether the object should be pinned
 936  *
 937  * This returns a weak handle that wraps the object, this is used to
 938  * keep a reference to a managed object from the unmanaged world.
 939  * Unlike the mono_gchandle_new the object can be reclaimed by the
 940  * garbage collector.  In this case the value of the GCHandle will be
 941  * set to zero.
 942  *
 943  * If @pinned is false the address of the object can not be obtained, if it is
 944  * true the address of the object can be obtained.  This will also pin the
 945  * object so it will not be possible by a moving garbage collector to move the
 946  * object.
 947  *
 948  * Returns: a handle that can be used to access the object from
 949  * unmanaged code.
 950  */
 951 guint32
 952 mono_gchandle_new_weakref (GCObject *obj, gboolean track_resurrection)
 953 {
 954         return alloc_handle (gc_handles_for_type (track_resurrection ? HANDLE_WEAK_TRACK : HANDLE_WEAK), obj, track_resurrection);
 955 }
 956
 957 static GCObject *
 958 link_get (volatile gpointer *link_addr, gboolean is_weak)
 959 {
 960         void *volatile *link_addr_volatile;
 961         void *ptr;
 962         GCObject *obj;
 963 retry:
 964         link_addr_volatile = link_addr;
 965         ptr = (void*)*link_addr_volatile;
 966         /*
 967          * At this point we have a hidden pointer.  If the GC runs
 968          * here, it will not recognize the hidden pointer as a
 969          * reference, and if the object behind it is not referenced
 970          * elsewhere, it will be freed.  Once the world is restarted
 971          * we reveal the pointer, giving us a pointer to a freed
 972          * object.  To make sure we don't return it, we load the
 973          * hidden pointer again.  If it's still the same, we can be
 974          * sure the object reference is valid.
 975          */
 976         if (ptr && MONO_GC_HANDLE_IS_OBJECT_POINTER (ptr))
 977                 obj = (GCObject *)MONO_GC_REVEAL_POINTER (ptr, is_weak);
 978         else
 979                 return NULL;
 980
 981         /* Note [dummy use]:
 982          *
 983          * If a GC happens here, obj needs to be on the stack or in a
 984          * register, so we need to prevent this from being reordered
 985          * wrt the check.
 986          */
 987         mono_gc_dummy_use (obj);
 988         mono_memory_barrier ();
 989
 990         if (is_weak)
 991                 sgen_client_ensure_weak_gchandles_accessible ();
 992
 993         if ((void*)*link_addr_volatile != ptr)
 994                 goto retry;
 995
 996         return obj;
 997 }
 998
 999 /**
1000  * mono_gchandle_get_target:
1001  * @gchandle: a GCHandle's handle.
1002  *
1003  * The handle was previously created by calling mono_gchandle_new or
1004  * mono_gchandle_new_weakref.
1005  *
1006  * Returns a pointer to the MonoObject represented by the handle or
1007  * NULL for a collected object if using a weakref handle.
1008  */
1009 GCObject*
1010 mono_gchandle_get_target (guint32 gchandle)
1011 {
1012         guint index = MONO_GC_HANDLE_SLOT (gchandle);
1013         guint type = MONO_GC_HANDLE_TYPE (gchandle);
1014         HandleData *handles = gc_handles_for_type (type);
1015         guint bucket, offset;
1016         g_assert (index < handles->capacity);
1017         bucketize (index, &bucket, &offset);
1018         return link_get (&handles->entries [bucket] [offset], MONO_GC_HANDLE_TYPE_IS_WEAK (type));
1019 }
1020
1021 void
1022 sgen_gchandle_set_target (guint32 gchandle, GCObject *obj)
1023 {
1024         guint index = MONO_GC_HANDLE_SLOT (gchandle);
1025         guint type = MONO_GC_HANDLE_TYPE (gchandle);
1026         HandleData *handles = gc_handles_for_type (type);
1027         gboolean track = handles->type == HANDLE_WEAK_TRACK;
1028         guint bucket, offset;
1029         gpointer slot;
1030
1031         g_assert (index < handles->capacity);
1032         bucketize (index, &bucket, &offset);
1033
1034 retry:
1035         slot = handles->entries [bucket] [offset];
1036         g_assert (MONO_GC_HANDLE_OCCUPIED (slot));
1037         if (!try_set_slot (&handles->entries [bucket] [offset], obj, slot, MONO_GC_HANDLE_TYPE_IS_WEAK (handles->type)))
1038                 goto retry;
1039         if (MONO_GC_HANDLE_IS_OBJECT_POINTER (slot))
1040                 binary_protocol_dislink_remove ((gpointer)&handles->entries [bucket] [offset], track);
1041         if (obj)
1042                 binary_protocol_dislink_add ((gpointer)&handles->entries [bucket] [offset], obj, track);
1043 }
1044
1045 static gpointer
1046 mono_gchandle_slot_metadata (volatile gpointer *slot_addr, gboolean is_weak)
1047 {
1048         gpointer slot;
1049         gpointer metadata;
1050 retry:
1051         slot = *slot_addr;
1052         if (!MONO_GC_HANDLE_OCCUPIED (slot))
1053                 return NULL;
1054         if (MONO_GC_HANDLE_IS_OBJECT_POINTER (slot)) {
1055                 GCObject *obj = MONO_GC_REVEAL_POINTER (slot, is_weak);
1056                 /* See note [dummy use]. */
1057                 mono_gc_dummy_use (obj);
1058                 /*
1059                  * FIXME: The compiler could technically not carry a reference to obj around
1060                  * at this point and recompute it later, in which case we would still use
1061                  * it.
1062                  */
1063                 if (*slot_addr != slot)
1064                         goto retry;
1065                 return sgen_client_metadata_for_object (obj);
1066         }
1067         metadata = MONO_GC_REVEAL_POINTER (slot, is_weak);
1068         /* See note [dummy use]. */
1069         mono_gc_dummy_use (metadata);
1070         if (*slot_addr != slot)
1071                 goto retry;
1072         return metadata;
1073 }
1074
1075 gpointer
1076 sgen_gchandle_get_metadata (guint32 gchandle)
1077 {
1078         guint index = MONO_GC_HANDLE_SLOT (gchandle);
1079         guint type = MONO_GC_HANDLE_TYPE (gchandle);
1080         HandleData *handles = gc_handles_for_type (type);
1081         guint bucket, offset;
1082         if (index >= handles->capacity)
1083                 return NULL;
1084         bucketize (index, &bucket, &offset);
1085         return mono_gchandle_slot_metadata (&handles->entries [bucket] [offset], MONO_GC_HANDLE_TYPE_IS_WEAK (type));
1086 }
1087
1088 /**
1089  * mono_gchandle_free:
1090  * @gchandle: a GCHandle's handle.
1091  *
1092  * Frees the @gchandle handle.  If there are no outstanding
1093  * references, the garbage collector can reclaim the memory of the
1094  * object wrapped.
1095  */
1096 void
1097 mono_gchandle_free (guint32 gchandle)
1098 {
1099         guint index = MONO_GC_HANDLE_SLOT (gchandle);
1100         guint type = MONO_GC_HANDLE_TYPE (gchandle);
1101         HandleData *handles = gc_handles_for_type (type);
1102         guint bucket, offset;
1103         bucketize (index, &bucket, &offset);
1104         if (index < handles->capacity && MONO_GC_HANDLE_OCCUPIED (handles->entries [bucket] [offset])) {
1105                 if (MONO_GC_HANDLE_TYPE_IS_WEAK (handles->type))
1106                         binary_protocol_dislink_remove ((gpointer)&handles->entries [bucket] [offset], handles->type == HANDLE_WEAK_TRACK);
1107                 handles->entries [bucket] [offset] = NULL;
1108                 HEAVY_STAT (InterlockedDecrement64 ((volatile gint64 *)&stat_gc_handles_allocated));
1109         } else {
1110                 /* print a warning? */
1111         }
1112         sgen_client_gchandle_destroyed (handles->type, gchandle);
1113 }
1114
1115 /*
1116  * Returns whether to remove the link from its hash.
1117  */
1118 static gpointer
1119 null_link_if_necessary (gpointer hidden, GCHandleType handle_type, int max_generation, gpointer user)
1120 {
1121         const gboolean is_weak = GC_HANDLE_TYPE_IS_WEAK (handle_type);
1122         ScanCopyContext *ctx = (ScanCopyContext *)user;
1123         GCObject *obj;
1124         GCObject *copy;
1125
1126         if (!MONO_GC_HANDLE_VALID (hidden))
1127                 return hidden;
1128
1129         obj = MONO_GC_REVEAL_POINTER (hidden, MONO_GC_HANDLE_TYPE_IS_WEAK (handle_type));
1130         SGEN_ASSERT (0, obj, "Why is the hidden pointer NULL?");
1131
1132         if (object_older_than (obj, max_generation))
1133                 return hidden;
1134
1135         if (major_collector.is_object_live (obj))
1136                 return hidden;
1137
1138         /* Clear link if object is ready for finalization. This check may be redundant wrt is_object_live(). */
1139         if (sgen_gc_is_object_ready_for_finalization (obj))
1140                 return MONO_GC_HANDLE_METADATA_POINTER (sgen_client_metadata_for_object (obj), is_weak);
1141
1142         ctx->ops->copy_or_mark_object (&copy, ctx->queue);
1143         g_assert (copy);
1144         /* binary_protocol_dislink_update (hidden_entry, copy, handle_type == HANDLE_WEAK_TRACK); */
1145
1146         copy = obj;
1147         ctx->ops->copy_or_mark_object (&copy, ctx->queue);
1148         SGEN_ASSERT (0, copy, "Why couldn't we copy the object?");
1149         /* Update link if object was moved. */
1150         return MONO_GC_HANDLE_OBJECT_POINTER (copy, is_weak);
1151 }
1152
1153 /* LOCKING: requires that the GC lock is held */
1154 void
1155 sgen_null_link_in_range (int generation, ScanCopyContext ctx, gboolean track)
1156 {
1157         sgen_gchandle_iterate (track ? HANDLE_WEAK_TRACK : HANDLE_WEAK, generation, null_link_if_necessary, &ctx);
1158 }
1159
1160 typedef struct {
1161         SgenObjectPredicateFunc predicate;
1162         gpointer data;
1163 } WeakLinkAlivePredicateClosure;
1164
1165 static gpointer
1166 null_link_if (gpointer hidden, GCHandleType handle_type, int max_generation, gpointer user)
1167 {
1168         /* Strictly speaking, function pointers are not guaranteed to have the same size as data pointers. */
1169         WeakLinkAlivePredicateClosure *closure = (WeakLinkAlivePredicateClosure *)user;
1170         GCObject *obj;
1171
1172         if (!MONO_GC_HANDLE_VALID (hidden))
1173                 return hidden;
1174
1175         obj = MONO_GC_REVEAL_POINTER (hidden, MONO_GC_HANDLE_TYPE_IS_WEAK (handle_type));
1176         SGEN_ASSERT (0, obj, "Why is the hidden pointer NULL?");
1177
1178         if (object_older_than (obj, max_generation))
1179                 return hidden;
1180
1181         if (closure->predicate (obj, closure->data))
1182                 return NULL;
1183
1184         return hidden;
1185 }
1186
1187 /* LOCKING: requires that the GC lock is held */
1188 void
1189 sgen_null_links_if (SgenObjectPredicateFunc predicate, void *data, int generation, gboolean track)
1190 {
1191         WeakLinkAlivePredicateClosure closure = { predicate, data };
1192         sgen_gchandle_iterate (track ? HANDLE_WEAK_TRACK : HANDLE_WEAK, generation, null_link_if, &closure);
1193 }
1194
1195 void
1196 sgen_init_fin_weak_hash (void)
1197 {
1198 #ifdef HEAVY_STATISTICS
1199         mono_counters_register ("FinWeak Successes", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_success);
1200         mono_counters_register ("FinWeak Overflow aborts", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_overflow_abort);
1201         mono_counters_register ("FinWeak Wait for processing", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_wait_for_processing);
1202         mono_counters_register ("FinWeak Increment other thread", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_increment_other_thread);
1203         mono_counters_register ("FinWeak Index decremented", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_index_decremented);
1204         mono_counters_register ("FinWeak Entry invalidated", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_entry_invalidated);
1205
1206         mono_counters_register ("GC handles allocated", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_gc_handles_allocated);
1207         mono_counters_register ("max GC handles allocated", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_gc_handles_max_allocated);
1208 #endif
1209 }
1210
1211 #endif /* HAVE_SGEN_GC */