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