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