mono/metadata/sgen-pinning.c

   1 /*
   2  * sgen-pinning.c: The pin queue.
   3  *
   4  * Copyright 2001-2003 Ximian, Inc
   5  * Copyright 2003-2010 Novell, Inc.
   6  * Copyright (C) 2012 Xamarin Inc
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Library General Public
  10  * License 2.0 as published by the Free Software Foundation;
  11  *
  12  * This library is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Library General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Library General Public
  18  * License 2.0 along with this library; if not, write to the Free
  19  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  20  */
  21
  22 #include "config.h"
  23 #ifdef HAVE_SGEN_GC
  24
  25 #include "metadata/sgen-gc.h"
  26 #include "metadata/sgen-pinning.h"
  27 #include "metadata/sgen-protocol.h"
  28 #include "metadata/sgen-pointer-queue.h"
  29
  30 static SgenPointerQueue pin_queue;
  31 static size_t last_num_pinned = 0;
  32
  33 #define PIN_HASH_SIZE 1024
  34 static void *pin_hash_filter [PIN_HASH_SIZE];
  35
  36 void
  37 sgen_init_pinning (void)
  38 {
  39         memset (pin_hash_filter, 0, sizeof (pin_hash_filter));
  40 }
  41
  42 void
  43 sgen_finish_pinning (void)
  44 {
  45         last_num_pinned = pin_queue.next_slot;
  46         sgen_pointer_queue_clear (&pin_queue);
  47 }
  48
  49 void
  50 sgen_pin_stage_ptr (void *ptr)
  51 {
  52         /*very simple multiplicative hash function, tons better than simple and'ng */
  53         int hash_idx = ((mword)ptr * 1737350767) & (PIN_HASH_SIZE - 1);
  54         if (pin_hash_filter [hash_idx] == ptr)
  55                 return;
  56
  57         pin_hash_filter [hash_idx] = ptr;
  58
  59         sgen_pointer_queue_add (&pin_queue, ptr);
  60 }
  61
  62 gboolean
  63 sgen_find_optimized_pin_queue_area (void *start, void *end, size_t *first_out, size_t *last_out)
  64 {
  65         size_t first = sgen_pointer_queue_search (&pin_queue, start);
  66         size_t last = sgen_pointer_queue_search (&pin_queue, end);
  67         SGEN_ASSERT (0, last == pin_queue.next_slot || pin_queue.data [last] >= end, "Pin queue search gone awry");
  68         *first_out = first;
  69         *last_out = last;
  70         return first != last;
  71 }
  72
  73 void**
  74 sgen_pinning_get_entry (size_t index)
  75 {
  76         SGEN_ASSERT (0, index <= pin_queue.next_slot, "Pin queue entry out of range");
  77         return &pin_queue.data [index];
  78 }
  79
  80 void
  81 sgen_find_section_pin_queue_start_end (GCMemSection *section)
  82 {
  83         SGEN_LOG (6, "Pinning from section %p (%p-%p)", section, section->data, section->end_data);
  84
  85         sgen_find_optimized_pin_queue_area (section->data, section->end_data,
  86                         &section->pin_queue_first_entry, &section->pin_queue_last_entry);
  87
  88         SGEN_LOG (6, "Found %zd pinning addresses in section %p",
  89                         section->pin_queue_last_entry - section->pin_queue_first_entry, section);
  90 }
  91
  92 /*This will setup the given section for the while pin queue. */
  93 void
  94 sgen_pinning_setup_section (GCMemSection *section)
  95 {
  96         section->pin_queue_first_entry = 0;
  97         section->pin_queue_last_entry = pin_queue.next_slot;
  98 }
  99
 100 void
 101 sgen_pinning_trim_queue_to_section (GCMemSection *section)
 102 {
 103         SGEN_ASSERT (0, section->pin_queue_first_entry == 0, "Pin queue trimming assumes the whole pin queue is used by the nursery");
 104         pin_queue.next_slot = section->pin_queue_last_entry;
 105 }
 106
 107 /*
 108  * This is called when we've run out of memory during a major collection.
 109  *
 110  * After collecting potential pin entries and sorting the array, this is what it looks like:
 111  *
 112  * +--------------------+---------------------------------------------+--------------------+
 113  * | major heap entries |               nursery entries               | major heap entries |
 114  * +--------------------+---------------------------------------------+--------------------+
 115  *
 116  * Of course there might not be major heap entries before and/or after the nursery entries,
 117  * depending on where the major heap sections are in the address space, and whether there
 118  * were any potential pointers there.
 119  *
 120  * When we pin nursery objects, we compact the nursery part of the pin array, which leaves
 121  * discarded entries after the ones that actually pointed to nursery objects:
 122  *
 123  * +--------------------+-----------------+---------------------------+--------------------+
 124  * | major heap entries | nursery entries | discarded nursery entries | major heap entries |
 125  * +--------------------+-----------------+---------------------------+--------------------+
 126  *
 127  * When, due to being out of memory, we late pin more objects, the pin array looks like
 128  * this:
 129  *
 130  * +--------------------+-----------------+---------------------------+--------------------+--------------+
 131  * | major heap entries | nursery entries | discarded nursery entries | major heap entries | late entries |
 132  * +--------------------+-----------------+---------------------------+--------------------+--------------+
 133  *
 134  * This function gets rid of the discarded nursery entries by nulling them out.  Note that
 135  * we can late pin objects not only in the nursery but also in the major heap, which happens
 136  * when evacuation fails.
 137  */
 138 void
 139 sgen_pin_queue_clear_discarded_entries (GCMemSection *section, size_t max_pin_slot)
 140 {
 141         void **start = sgen_pinning_get_entry (section->pin_queue_last_entry);
 142         void **end = sgen_pinning_get_entry (max_pin_slot);
 143         void *addr;
 144
 145         for (; start < end; ++start) {
 146                 addr = *start;
 147                 if ((char*)addr < section->data || (char*)addr > section->end_data)
 148                         break;
 149                 *start = NULL;
 150         }
 151 }
 152
 153 /* reduce the info in the pin queue, removing duplicate pointers and sorting them */
 154 void
 155 sgen_optimize_pin_queue (void)
 156 {
 157         sgen_pointer_queue_sort_uniq (&pin_queue);
 158 }
 159
 160 size_t
 161 sgen_get_pinned_count (void)
 162 {
 163         return pin_queue.next_slot;
 164 }
 165
 166 void
 167 sgen_dump_pin_queue (void)
 168 {
 169         int i;
 170
 171         for (i = 0; i < last_num_pinned; ++i) {
 172                 void *ptr = pin_queue.data [i];
 173                 SGEN_LOG (3, "Bastard pinning obj %p (%s), size: %zd", ptr, sgen_safe_name (ptr), sgen_safe_object_get_size (ptr));
 174         }
 175 }
 176
 177 typedef struct _CementHashEntry CementHashEntry;
 178 struct _CementHashEntry {
 179         char *obj;
 180         unsigned int count;
 181 };
 182
 183 static CementHashEntry cement_hash [SGEN_CEMENT_HASH_SIZE];
 184 static CementHashEntry cement_hash_concurrent [SGEN_CEMENT_HASH_SIZE];
 185
 186 static gboolean cement_enabled = TRUE;
 187 static gboolean cement_concurrent = FALSE;
 188
 189 void
 190 sgen_cement_init (gboolean enabled)
 191 {
 192         cement_enabled = enabled;
 193 }
 194
 195 void
 196 sgen_cement_reset (void)
 197 {
 198         SGEN_ASSERT (1, !cement_concurrent, "Concurrent cementing cannot simply be reset");
 199
 200         memset (cement_hash, 0, sizeof (cement_hash));
 201         binary_protocol_cement_reset ();
 202 }
 203
 204 /*
 205  * The reason we cannot simply reset cementing at the start of a
 206  * concurrent collection is that the nursery collections running
 207  * concurrently must keep pinning the cemented objects, because we
 208  * don't have the global remsets that point to them anymore - if the
 209  * nursery collector moved the cemented objects, we'd have invalid
 210  * pointers in the major heap.
 211  *
 212  * What we do instead is to reset cementing at the start of concurrent
 213  * collections in such a way that nursery collections happening during
 214  * the major collection still pin the formerly cemented objects.  We
 215  * have a shadow cementing table for that purpose.  The nursery
 216  * collections still work with the old cementing table, while the
 217  * major collector builds up a new cementing table, adding global
 218  * remsets whenever needed like usual.  When the major collector
 219  * finishes, the old cementing table is replaced by the new one.
 220  */
 221
 222 void
 223 sgen_cement_concurrent_start (void)
 224 {
 225         SGEN_ASSERT (1, !cement_concurrent, "Concurrent cementing has already been started");
 226         cement_concurrent = TRUE;
 227
 228         memset (cement_hash_concurrent, 0, sizeof (cement_hash));
 229 }
 230
 231 void
 232 sgen_cement_concurrent_finish (void)
 233 {
 234         SGEN_ASSERT (1, cement_concurrent, "Concurrent cementing hasn't been started");
 235         cement_concurrent = FALSE;
 236
 237         memcpy (cement_hash, cement_hash_concurrent, sizeof (cement_hash));
 238 }
 239
 240 gboolean
 241 sgen_cement_lookup (char *obj)
 242 {
 243         guint hv = mono_aligned_addr_hash (obj);
 244         int i = SGEN_CEMENT_HASH (hv);
 245
 246         SGEN_ASSERT (5, sgen_ptr_in_nursery (obj), "Looking up cementing for non-nursery objects makes no sense");
 247
 248         if (!cement_enabled)
 249                 return FALSE;
 250
 251         if (!cement_hash [i].obj)
 252                 return FALSE;
 253         if (cement_hash [i].obj != obj)
 254                 return FALSE;
 255
 256         return cement_hash [i].count >= SGEN_CEMENT_THRESHOLD;
 257 }
 258
 259 gboolean
 260 sgen_cement_lookup_or_register (char *obj)
 261 {
 262         guint hv;
 263         int i;
 264         CementHashEntry *hash;
 265         gboolean concurrent_cementing = sgen_concurrent_collection_in_progress ();
 266
 267         if (!cement_enabled)
 268                 return FALSE;
 269
 270         if (concurrent_cementing)
 271                 SGEN_ASSERT (5, cement_concurrent, "Cementing wasn't inited with concurrent flag");
 272
 273         if (concurrent_cementing)
 274                 hash = cement_hash_concurrent;
 275         else
 276                 hash = cement_hash;
 277
 278         hv = mono_aligned_addr_hash (obj);
 279         i = SGEN_CEMENT_HASH (hv);
 280
 281         SGEN_ASSERT (5, sgen_ptr_in_nursery (obj), "Can only cement pointers to nursery objects");
 282
 283         if (!hash [i].obj) {
 284                 SGEN_ASSERT (5, !hash [i].count, "Cementing hash inconsistent");
 285                 hash [i].obj = obj;
 286         } else if (hash [i].obj != obj) {
 287                 return FALSE;
 288         }
 289
 290         if (hash [i].count >= SGEN_CEMENT_THRESHOLD)
 291                 return TRUE;
 292
 293         ++hash [i].count;
 294         if (hash [i].count == SGEN_CEMENT_THRESHOLD) {
 295                 if (G_UNLIKELY (MONO_GC_OBJ_CEMENTED_ENABLED())) {
 296                         MonoVTable *vt G_GNUC_UNUSED = (MonoVTable*)SGEN_LOAD_VTABLE (obj);
 297                         MONO_GC_OBJ_CEMENTED ((mword)obj, sgen_safe_object_get_size ((MonoObject*)obj),
 298                                         vt->klass->name_space, vt->klass->name);
 299                 }
 300                 binary_protocol_cement (obj, (gpointer)SGEN_LOAD_VTABLE (obj),
 301                                 (int)sgen_safe_object_get_size ((MonoObject*)obj));
 302         }
 303
 304         return FALSE;
 305 }
 306
 307 void
 308 sgen_pin_cemented_objects (void)
 309 {
 310         int i;
 311         for (i = 0; i < SGEN_CEMENT_HASH_SIZE; ++i) {
 312                 if (!cement_hash [i].count)
 313                         continue;
 314
 315                 SGEN_ASSERT (5, cement_hash [i].count >= SGEN_CEMENT_THRESHOLD, "Cementing hash inconsistent");
 316
 317                 sgen_pin_stage_ptr (cement_hash [i].obj);
 318                 /* FIXME: do pin stats if enabled */
 319         }
 320 }
 321
 322 void
 323 sgen_cement_clear_below_threshold (void)
 324 {
 325         int i;
 326         for (i = 0; i < SGEN_CEMENT_HASH_SIZE; ++i) {
 327                 if (cement_hash [i].count < SGEN_CEMENT_THRESHOLD) {
 328                         cement_hash [i].obj = NULL;
 329                         cement_hash [i].count = 0;
 330                 }
 331         }
 332 }
 333
 334 #endif /* HAVE_SGEN_GC */