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
  29 static void** pin_queue;
  30 static size_t pin_queue_size = 0;
  31 static size_t next_pin_slot = 0;
  32 static size_t last_num_pinned = 0;
  33
  34 #define PIN_HASH_SIZE 1024
  35 static void *pin_hash_filter [PIN_HASH_SIZE];
  36
  37 void
  38 sgen_init_pinning (void)
  39 {
  40         memset (pin_hash_filter, 0, sizeof (pin_hash_filter));
  41 }
  42
  43 void
  44 sgen_finish_pinning (void)
  45 {
  46         last_num_pinned = next_pin_slot;
  47         next_pin_slot = 0;
  48 }
  49
  50 static void
  51 realloc_pin_queue (void)
  52 {
  53         size_t new_size = pin_queue_size? pin_queue_size + pin_queue_size/2: 1024;
  54         void **new_pin = sgen_alloc_internal_dynamic (sizeof (void*) * new_size, INTERNAL_MEM_PIN_QUEUE, TRUE);
  55         memcpy (new_pin, pin_queue, sizeof (void*) * next_pin_slot);
  56         sgen_free_internal_dynamic (pin_queue, sizeof (void*) * pin_queue_size, INTERNAL_MEM_PIN_QUEUE);
  57         pin_queue = new_pin;
  58         pin_queue_size = new_size;
  59         SGEN_LOG (4, "Reallocated pin queue to size: %zd", new_size);
  60 }
  61
  62 void
  63 sgen_pin_stage_ptr (void *ptr)
  64 {
  65         /*very simple multiplicative hash function, tons better than simple and'ng */
  66         int hash_idx = ((mword)ptr * 1737350767) & (PIN_HASH_SIZE - 1);
  67         if (pin_hash_filter [hash_idx] == ptr)
  68                 return;
  69
  70         pin_hash_filter [hash_idx] = ptr;
  71
  72         if (next_pin_slot >= pin_queue_size)
  73                 realloc_pin_queue ();
  74
  75         pin_queue [next_pin_slot++] = ptr;
  76 }
  77
  78 static size_t
  79 optimized_pin_queue_search (void *addr)
  80 {
  81         size_t first = 0, last = next_pin_slot;
  82         while (first < last) {
  83                 size_t middle = first + ((last - first) >> 1);
  84                 if (addr <= pin_queue [middle])
  85                         last = middle;
  86                 else
  87                         first = middle + 1;
  88         }
  89         g_assert (first == last);
  90         return first;
  91 }
  92
  93 void**
  94 sgen_find_optimized_pin_queue_area (void *start, void *end, size_t *num)
  95 {
  96         size_t first, last;
  97         first = optimized_pin_queue_search (start);
  98         last = optimized_pin_queue_search (end);
  99         *num = last - first;
 100         if (first == last)
 101                 return NULL;
 102         return pin_queue + first;
 103 }
 104
 105 void
 106 sgen_find_section_pin_queue_start_end (GCMemSection *section)
 107 {
 108         SGEN_LOG (6, "Pinning from section %p (%p-%p)", section, section->data, section->end_data);
 109         section->pin_queue_start = sgen_find_optimized_pin_queue_area (section->data, section->end_data, &section->pin_queue_num_entries);
 110         SGEN_LOG (6, "Found %zd pinning addresses in section %p", section->pin_queue_num_entries, section);
 111 }
 112
 113 /*This will setup the given section for the while pin queue. */
 114 void
 115 sgen_pinning_setup_section (GCMemSection *section)
 116 {
 117         section->pin_queue_start = pin_queue;
 118         section->pin_queue_num_entries = next_pin_slot;
 119 }
 120
 121 void
 122 sgen_pinning_trim_queue_to_section (GCMemSection *section)
 123 {
 124         next_pin_slot = section->pin_queue_num_entries;
 125 }
 126
 127 void
 128 sgen_pin_queue_clear_discarded_entries (GCMemSection *section, size_t max_pin_slot)
 129 {
 130         void **start = section->pin_queue_start + section->pin_queue_num_entries;
 131         void **end = pin_queue + max_pin_slot;
 132         void *addr;
 133
 134         if (!start)
 135                 return;
 136
 137         for (; start < end; ++start) {
 138                 addr = *start;
 139                 if ((char*)addr < section->data || (char*)addr > section->end_data)
 140                         break;
 141                 *start = NULL;
 142         }
 143 }
 144
 145 /* reduce the info in the pin queue, removing duplicate pointers and sorting them */
 146 void
 147 sgen_optimize_pin_queue (size_t start_slot)
 148 {
 149         void **start, **cur, **end;
 150         /* sort and uniq pin_queue: we just sort and we let the rest discard multiple values */
 151         /* it may be better to keep ranges of pinned memory instead of individually pinning objects */
 152         SGEN_LOG (5, "Sorting pin queue, size: %zd", next_pin_slot);
 153         if ((next_pin_slot - start_slot) > 1)
 154                 sgen_sort_addresses (pin_queue + start_slot, next_pin_slot - start_slot);
 155         start = cur = pin_queue + start_slot;
 156         end = pin_queue + next_pin_slot;
 157         while (cur < end) {
 158                 *start = *cur++;
 159                 while (*start == *cur && cur < end)
 160                         cur++;
 161                 start++;
 162         };
 163         next_pin_slot = start - pin_queue;
 164         SGEN_LOG (5, "Pin queue reduced to size: %zd", next_pin_slot);
 165 }
 166
 167 size_t
 168 sgen_get_pinned_count (void)
 169 {
 170         return next_pin_slot;
 171 }
 172
 173 void
 174 sgen_dump_pin_queue (void)
 175 {
 176         int i;
 177
 178         for (i = 0; i < last_num_pinned; ++i) {
 179                 SGEN_LOG (3, "Bastard pinning obj %p (%s), size: %zd", pin_queue [i], sgen_safe_name (pin_queue [i]), sgen_safe_object_get_size (pin_queue [i]));
 180         }
 181 }
 182
 183 typedef struct _CementHashEntry CementHashEntry;
 184 struct _CementHashEntry {
 185         char *obj;
 186         unsigned int count;
 187 };
 188
 189 static CementHashEntry cement_hash [SGEN_CEMENT_HASH_SIZE];
 190 static CementHashEntry cement_hash_concurrent [SGEN_CEMENT_HASH_SIZE];
 191
 192 static gboolean cement_enabled = TRUE;
 193 static gboolean cement_concurrent = FALSE;
 194
 195 void
 196 sgen_cement_init (gboolean enabled)
 197 {
 198         cement_enabled = enabled;
 199 }
 200
 201 void
 202 sgen_cement_reset (void)
 203 {
 204         SGEN_ASSERT (1, !cement_concurrent, "Concurrent cementing cannot simply be reset");
 205
 206         memset (cement_hash, 0, sizeof (cement_hash));
 207         binary_protocol_cement_reset ();
 208 }
 209
 210 /*
 211  * The reason we cannot simply reset cementing at the start of a
 212  * concurrent collection is that the nursery collections running
 213  * concurrently must keep pinning the cemented objects, because we
 214  * don't have the global remsets that point to them anymore - if the
 215  * nursery collector moved the cemented objects, we'd have invalid
 216  * pointers in the major heap.
 217  *
 218  * What we do instead is to reset cementing at the start of concurrent
 219  * collections in such a way that nursery collections happening during
 220  * the major collection still pin the formerly cemented objects.  We
 221  * have a shadow cementing table for that purpose.  The nursery
 222  * collections still work with the old cementing table, while the
 223  * major collector builds up a new cementing table, adding global
 224  * remsets whenever needed like usual.  When the major collector
 225  * finishes, the old cementing table is replaced by the new one.
 226  */
 227
 228 void
 229 sgen_cement_concurrent_start (void)
 230 {
 231         SGEN_ASSERT (1, !cement_concurrent, "Concurrent cementing has already been started");
 232         cement_concurrent = TRUE;
 233
 234         memset (cement_hash_concurrent, 0, sizeof (cement_hash));
 235 }
 236
 237 void
 238 sgen_cement_concurrent_finish (void)
 239 {
 240         SGEN_ASSERT (1, cement_concurrent, "Concurrent cementing hasn't been started");
 241         cement_concurrent = FALSE;
 242
 243         memcpy (cement_hash, cement_hash_concurrent, sizeof (cement_hash));
 244 }
 245
 246 gboolean
 247 sgen_cement_lookup (char *obj)
 248 {
 249         int i = mono_aligned_addr_hash (obj) % SGEN_CEMENT_HASH_SIZE;
 250
 251         SGEN_ASSERT (5, sgen_ptr_in_nursery (obj), "Looking up cementing for non-nursery objects makes no sense");
 252
 253         if (!cement_enabled)
 254                 return FALSE;
 255
 256         if (!cement_hash [i].obj)
 257                 return FALSE;
 258         if (cement_hash [i].obj != obj)
 259                 return FALSE;
 260
 261         return cement_hash [i].count >= SGEN_CEMENT_THRESHOLD;
 262 }
 263
 264 gboolean
 265 sgen_cement_lookup_or_register (char *obj)
 266 {
 267         int i;
 268         CementHashEntry *hash;
 269         gboolean concurrent_cementing = sgen_concurrent_collection_in_progress ();
 270
 271         if (!cement_enabled)
 272                 return FALSE;
 273
 274         if (concurrent_cementing)
 275                 SGEN_ASSERT (5, cement_concurrent, "Cementing wasn't inited with concurrent flag");
 276
 277         if (concurrent_cementing)
 278                 hash = cement_hash_concurrent;
 279         else
 280                 hash = cement_hash;
 281
 282         /*
 283          * We use modulus hashing, which is fine with constants as gcc
 284          * can optimize them to multiplication, but with variable
 285          * values it would be a bad idea given armv7 has no hardware
 286          * for division, making it 20x slower than a multiplication.
 287          *
 288          * This code path can be quite hot, depending on the workload,
 289          * so if we make the hash size user-adjustable we should
 290          * figure out something not involving division.
 291          */
 292         i = mono_aligned_addr_hash (obj) % SGEN_CEMENT_HASH_SIZE;
 293
 294         SGEN_ASSERT (5, sgen_ptr_in_nursery (obj), "Can only cement pointers to nursery objects");
 295
 296         if (!hash [i].obj) {
 297                 SGEN_ASSERT (5, !hash [i].count, "Cementing hash inconsistent");
 298                 hash [i].obj = obj;
 299         } else if (hash [i].obj != obj) {
 300                 return FALSE;
 301         }
 302
 303         if (hash [i].count >= SGEN_CEMENT_THRESHOLD)
 304                 return TRUE;
 305
 306         ++hash [i].count;
 307         if (hash [i].count == SGEN_CEMENT_THRESHOLD) {
 308                 if (G_UNLIKELY (MONO_GC_OBJ_CEMENTED_ENABLED())) {
 309                         MonoVTable *vt G_GNUC_UNUSED = (MonoVTable*)SGEN_LOAD_VTABLE (obj);
 310                         MONO_GC_OBJ_CEMENTED ((mword)obj, sgen_safe_object_get_size ((MonoObject*)obj),
 311                                         vt->klass->name_space, vt->klass->name);
 312                 }
 313                 binary_protocol_cement (obj, (gpointer)SGEN_LOAD_VTABLE (obj),
 314                                 (int)sgen_safe_object_get_size ((MonoObject*)obj));
 315         }
 316
 317         return FALSE;
 318 }
 319
 320 void
 321 sgen_cement_iterate (IterateObjectCallbackFunc callback, void *callback_data)
 322 {
 323         int i;
 324         for (i = 0; i < SGEN_CEMENT_HASH_SIZE; ++i) {
 325                 if (!cement_hash [i].count)
 326                         continue;
 327
 328                 SGEN_ASSERT (5, cement_hash [i].count >= SGEN_CEMENT_THRESHOLD, "Cementing hash inconsistent");
 329
 330                 callback (cement_hash [i].obj, 0, callback_data);
 331         }
 332 }
 333
 334 void
 335 sgen_cement_clear_below_threshold (void)
 336 {
 337         int i;
 338         for (i = 0; i < SGEN_CEMENT_HASH_SIZE; ++i) {
 339                 if (cement_hash [i].count < SGEN_CEMENT_THRESHOLD) {
 340                         cement_hash [i].obj = NULL;
 341                         cement_hash [i].count = 0;
 342                 }
 343         }
 344 }
 345
 346 #endif /* HAVE_SGEN_GC */