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