mono/sgen/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  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
   9  */
  10
  11 #include "config.h"
  12 #ifdef HAVE_SGEN_GC
  13
  14 #include <string.h>
  15
  16 #include "mono/sgen/sgen-gc.h"
  17 #include "mono/sgen/sgen-pinning.h"
  18 #include "mono/sgen/sgen-protocol.h"
  19 #include "mono/sgen/sgen-pointer-queue.h"
  20 #include "mono/sgen/sgen-client.h"
  21
  22 static SgenPointerQueue pin_queue;
  23 static size_t last_num_pinned = 0;
  24 /*
  25  * While we hold the pin_queue_mutex, all objects in pin_queue_objs will
  26  * stay pinned, which means they can't move, therefore they can be scanned.
  27  */
  28 static SgenPointerQueue pin_queue_objs;
  29 static MonoCoopMutex pin_queue_mutex;
  30
  31 #define PIN_HASH_SIZE 1024
  32 static void *pin_hash_filter [PIN_HASH_SIZE];
  33
  34 void
  35 sgen_pinning_init (void)
  36 {
  37         mono_coop_mutex_init (&pin_queue_mutex);
  38 }
  39
  40 void
  41 sgen_init_pinning (void)
  42 {
  43         mono_coop_mutex_lock (&pin_queue_mutex);
  44         memset (pin_hash_filter, 0, sizeof (pin_hash_filter));
  45         pin_queue.mem_type = INTERNAL_MEM_PIN_QUEUE;
  46         sgen_pointer_queue_clear (&pin_queue_objs);
  47 }
  48
  49 void
  50 sgen_finish_pinning (void)
  51 {
  52         last_num_pinned = pin_queue.next_slot;
  53         sgen_pointer_queue_clear (&pin_queue);
  54         mono_coop_mutex_unlock (&pin_queue_mutex);
  55 }
  56
  57 void
  58 sgen_pinning_register_pinned_in_nursery (GCObject *obj)
  59 {
  60         sgen_pointer_queue_add (&pin_queue_objs, obj);
  61 }
  62
  63 void
  64 sgen_scan_pin_queue_objects (ScanCopyContext ctx)
  65 {
  66         int i;
  67         ScanObjectFunc scan_func = ctx.ops->scan_object;
  68
  69         mono_coop_mutex_lock (&pin_queue_mutex);
  70         for (i = 0; i < pin_queue_objs.next_slot; ++i) {
  71                 GCObject *obj = (GCObject *)pin_queue_objs.data [i];
  72                 scan_func (obj, sgen_obj_get_descriptor_safe (obj), ctx.queue);
  73         }
  74         mono_coop_mutex_unlock (&pin_queue_mutex);
  75 }
  76
  77 void
  78 sgen_pin_stage_ptr (void *ptr)
  79 {
  80         /*very simple multiplicative hash function, tons better than simple and'ng */
  81         int hash_idx = ((mword)ptr * 1737350767) & (PIN_HASH_SIZE - 1);
  82         if (pin_hash_filter [hash_idx] == ptr)
  83                 return;
  84
  85         pin_hash_filter [hash_idx] = ptr;
  86
  87         sgen_pointer_queue_add (&pin_queue, ptr);
  88 }
  89
  90 gboolean
  91 sgen_find_optimized_pin_queue_area (void *start, void *end, size_t *first_out, size_t *last_out)
  92 {
  93         size_t first = sgen_pointer_queue_search (&pin_queue, start);
  94         size_t last = sgen_pointer_queue_search (&pin_queue, end);
  95         SGEN_ASSERT (0, last == pin_queue.next_slot || pin_queue.data [last] >= end, "Pin queue search gone awry");
  96         *first_out = first;
  97         *last_out = last;
  98         return first != last;
  99 }
 100
 101 void**
 102 sgen_pinning_get_entry (size_t index)
 103 {
 104         SGEN_ASSERT (0, index <= pin_queue.next_slot, "Pin queue entry out of range");
 105         return &pin_queue.data [index];
 106 }
 107
 108 void
 109 sgen_find_section_pin_queue_start_end (GCMemSection *section)
 110 {
 111         SGEN_LOG (6, "Pinning from section %p (%p-%p)", section, section->data, section->end_data);
 112
 113         sgen_find_optimized_pin_queue_area (section->data, section->end_data,
 114                         &section->pin_queue_first_entry, &section->pin_queue_last_entry);
 115
 116         SGEN_LOG (6, "Found %zd pinning addresses in section %p",
 117                         section->pin_queue_last_entry - section->pin_queue_first_entry, section);
 118 }
 119
 120 /*This will setup the given section for the while pin queue. */
 121 void
 122 sgen_pinning_setup_section (GCMemSection *section)
 123 {
 124         section->pin_queue_first_entry = 0;
 125         section->pin_queue_last_entry = pin_queue.next_slot;
 126 }
 127
 128 void
 129 sgen_pinning_trim_queue_to_section (GCMemSection *section)
 130 {
 131         SGEN_ASSERT (0, section->pin_queue_first_entry == 0, "Pin queue trimming assumes the whole pin queue is used by the nursery");
 132         pin_queue.next_slot = section->pin_queue_last_entry;
 133 }
 134
 135 /*
 136  * This is called when we've run out of memory during a major collection.
 137  *
 138  * After collecting potential pin entries and sorting the array, this is what it looks like:
 139  *
 140  * +--------------------+---------------------------------------------+--------------------+
 141  * | major heap entries |               nursery entries               | major heap entries |
 142  * +--------------------+---------------------------------------------+--------------------+
 143  *
 144  * Of course there might not be major heap entries before and/or after the nursery entries,
 145  * depending on where the major heap sections are in the address space, and whether there
 146  * were any potential pointers there.
 147  *
 148  * When we pin nursery objects, we compact the nursery part of the pin array, which leaves
 149  * discarded entries after the ones that actually pointed to nursery objects:
 150  *
 151  * +--------------------+-----------------+---------------------------+--------------------+
 152  * | major heap entries | nursery entries | discarded nursery entries | major heap entries |
 153  * +--------------------+-----------------+---------------------------+--------------------+
 154  *
 155  * When, due to being out of memory, we late pin more objects, the pin array looks like
 156  * this:
 157  *
 158  * +--------------------+-----------------+---------------------------+--------------------+--------------+
 159  * | major heap entries | nursery entries | discarded nursery entries | major heap entries | late entries |
 160  * +--------------------+-----------------+---------------------------+--------------------+--------------+
 161  *
 162  * This function gets rid of the discarded nursery entries by nulling them out.  Note that
 163  * we can late pin objects not only in the nursery but also in the major heap, which happens
 164  * when evacuation fails.
 165  */
 166 void
 167 sgen_pin_queue_clear_discarded_entries (GCMemSection *section, size_t max_pin_slot)
 168 {
 169         void **start = sgen_pinning_get_entry (section->pin_queue_last_entry);
 170         void **end = sgen_pinning_get_entry (max_pin_slot);
 171         void *addr;
 172
 173         for (; start < end; ++start) {
 174                 addr = *start;
 175                 if ((char*)addr < section->data || (char*)addr > section->end_data)
 176                         break;
 177                 *start = NULL;
 178         }
 179 }
 180
 181 /* reduce the info in the pin queue, removing duplicate pointers and sorting them */
 182 void
 183 sgen_optimize_pin_queue (void)
 184 {
 185         sgen_pointer_queue_sort_uniq (&pin_queue);
 186 }
 187
 188 size_t
 189 sgen_get_pinned_count (void)
 190 {
 191         return pin_queue.next_slot;
 192 }
 193
 194 void
 195 sgen_dump_pin_queue (void)
 196 {
 197         int i;
 198
 199         for (i = 0; i < last_num_pinned; ++i) {
 200                 GCObject *ptr = (GCObject *)pin_queue.data [i];
 201                 SGEN_LOG (3, "Bastard pinning obj %p (%s), size: %zd", ptr, sgen_client_vtable_get_name (SGEN_LOAD_VTABLE (ptr)), sgen_safe_object_get_size (ptr));
 202         }
 203 }
 204
 205 typedef struct _CementHashEntry CementHashEntry;
 206 struct _CementHashEntry {
 207         GCObject *obj;
 208         unsigned int count;
 209         gboolean forced; /* if it should stay cemented after the finishing pause */
 210 };
 211
 212 static CementHashEntry cement_hash [SGEN_CEMENT_HASH_SIZE];
 213
 214 static gboolean cement_enabled = TRUE;
 215
 216 void
 217 sgen_cement_init (gboolean enabled)
 218 {
 219         cement_enabled = enabled;
 220 }
 221
 222 void
 223 sgen_cement_reset (void)
 224 {
 225         int i;
 226         for (i = 0; i < SGEN_CEMENT_HASH_SIZE; i++) {
 227                 if (cement_hash [i].forced) {
 228                         cement_hash [i].forced = FALSE;
 229                 } else {
 230                         cement_hash [i].obj = NULL;
 231                         cement_hash [i].count = 0;
 232                 }
 233         }
 234         binary_protocol_cement_reset ();
 235 }
 236
 237
 238 /*
 239  * The pin_queue should be full and sorted, without entries from the cemented
 240  * objects. We traverse the cement hash and check if each object is pinned in
 241  * the pin_queue (the pin_queue contains entries between obj and obj+obj_len)
 242  */
 243 void
 244 sgen_cement_force_pinned (void)
 245 {
 246         int i;
 247
 248         if (!cement_enabled)
 249                 return;
 250
 251         for (i = 0; i < SGEN_CEMENT_HASH_SIZE; i++) {
 252                 GCObject *obj = cement_hash [i].obj;
 253                 size_t index;
 254                 if (!obj)
 255                         continue;
 256                 if (cement_hash [i].count < SGEN_CEMENT_THRESHOLD)
 257                         continue;
 258                 SGEN_ASSERT (0, !cement_hash [i].forced, "Why do we have a forced cemented object before forcing ?");
 259
 260                 /* Returns the index of the target or of the first element greater than it */
 261                 index = sgen_pointer_queue_search (&pin_queue, obj);
 262                 if (index == pin_queue.next_slot)
 263                         continue;
 264                 SGEN_ASSERT (0, pin_queue.data [index] >= (gpointer)obj, "Binary search should return a pointer greater than the search target");
 265                 if (pin_queue.data [index] < (gpointer)((char*)obj + sgen_safe_object_get_size (obj)))
 266                         cement_hash [i].forced = TRUE;
 267         }
 268 }
 269
 270 gboolean
 271 sgen_cement_is_forced (GCObject *obj)
 272 {
 273         guint hv = sgen_aligned_addr_hash (obj);
 274         int i = SGEN_CEMENT_HASH (hv);
 275
 276         SGEN_ASSERT (5, sgen_ptr_in_nursery (obj), "Looking up cementing for non-nursery objects makes no sense");
 277
 278         if (!cement_enabled)
 279                 return FALSE;
 280
 281         if (!cement_hash [i].obj)
 282                 return FALSE;
 283         if (cement_hash [i].obj != obj)
 284                 return FALSE;
 285
 286         return cement_hash [i].forced;
 287 }
 288
 289 gboolean
 290 sgen_cement_lookup (GCObject *obj)
 291 {
 292         guint hv = sgen_aligned_addr_hash (obj);
 293         int i = SGEN_CEMENT_HASH (hv);
 294
 295         SGEN_ASSERT (5, sgen_ptr_in_nursery (obj), "Looking up cementing for non-nursery objects makes no sense");
 296
 297         if (!cement_enabled)
 298                 return FALSE;
 299
 300         if (!cement_hash [i].obj)
 301                 return FALSE;
 302         if (cement_hash [i].obj != obj)
 303                 return FALSE;
 304
 305         return cement_hash [i].count >= SGEN_CEMENT_THRESHOLD;
 306 }
 307
 308 gboolean
 309 sgen_cement_lookup_or_register (GCObject *obj)
 310 {
 311         guint hv;
 312         int i;
 313         CementHashEntry *hash = cement_hash;
 314
 315         if (!cement_enabled)
 316                 return FALSE;
 317
 318         hv = sgen_aligned_addr_hash (obj);
 319         i = SGEN_CEMENT_HASH (hv);
 320
 321         SGEN_ASSERT (5, sgen_ptr_in_nursery (obj), "Can only cement pointers to nursery objects");
 322
 323         if (!hash [i].obj) {
 324                 SGEN_ASSERT (5, !hash [i].count, "Cementing hash inconsistent");
 325                 hash [i].obj = obj;
 326         } else if (hash [i].obj != obj) {
 327                 return FALSE;
 328         }
 329
 330         if (hash [i].count >= SGEN_CEMENT_THRESHOLD)
 331                 return TRUE;
 332
 333         ++hash [i].count;
 334         if (hash [i].count == SGEN_CEMENT_THRESHOLD) {
 335                 SGEN_ASSERT (9, sgen_get_current_collection_generation () >= 0, "We can only cement objects when we're in a collection pause.");
 336                 SGEN_ASSERT (9, SGEN_OBJECT_IS_PINNED (obj), "Can only cement pinned objects");
 337                 SGEN_CEMENT_OBJECT (obj);
 338
 339                 binary_protocol_cement (obj, (gpointer)SGEN_LOAD_VTABLE (obj),
 340                                 (int)sgen_safe_object_get_size (obj));
 341         }
 342
 343         return FALSE;
 344 }
 345
 346 static void
 347 pin_from_hash (CementHashEntry *hash, gboolean has_been_reset)
 348 {
 349         int i;
 350         for (i = 0; i < SGEN_CEMENT_HASH_SIZE; ++i) {
 351                 if (!hash [i].count)
 352                         continue;
 353
 354                 if (has_been_reset)
 355                         SGEN_ASSERT (5, hash [i].count >= SGEN_CEMENT_THRESHOLD, "Cementing hash inconsistent");
 356
 357                 sgen_pin_stage_ptr (hash [i].obj);
 358                 binary_protocol_cement_stage (hash [i].obj);
 359                 /* FIXME: do pin stats if enabled */
 360
 361                 SGEN_CEMENT_OBJECT (hash [i].obj);
 362         }
 363 }
 364
 365 void
 366 sgen_pin_cemented_objects (void)
 367 {
 368         pin_from_hash (cement_hash, TRUE);
 369 }
 370
 371 void
 372 sgen_cement_clear_below_threshold (void)
 373 {
 374         int i;
 375         for (i = 0; i < SGEN_CEMENT_HASH_SIZE; ++i) {
 376                 if (cement_hash [i].count < SGEN_CEMENT_THRESHOLD) {
 377                         cement_hash [i].obj = NULL;
 378                         cement_hash [i].count = 0;
 379                 }
 380         }
 381 }
 382
 383 #endif /* HAVE_SGEN_GC */