mono/sgen/sgen-gray.c

   1 /*
   2  * sgen-gray.c: Gray queue management.
   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 #include "config.h"
  11 #ifdef HAVE_SGEN_GC
  12
  13 #include "mono/sgen/sgen-gc.h"
  14 #include "mono/sgen/sgen-protocol.h"
  15
  16 #ifdef HEAVY_STATISTICS
  17 guint64 stat_gray_queue_section_alloc;
  18 guint64 stat_gray_queue_section_free;
  19 guint64 stat_gray_queue_enqueue_fast_path;
  20 guint64 stat_gray_queue_dequeue_fast_path;
  21 guint64 stat_gray_queue_enqueue_slow_path;
  22 guint64 stat_gray_queue_dequeue_slow_path;
  23 #endif
  24
  25 #define GRAY_QUEUE_LENGTH_LIMIT 64
  26
  27 #ifdef SGEN_CHECK_GRAY_OBJECT_SECTIONS
  28 #define STATE_TRANSITION(s,o,n) do {                                    \
  29                 int __old = (o);                                        \
  30                 if (InterlockedCompareExchange ((volatile int*)&(s)->state, (n), __old) != __old) \
  31                         g_assert_not_reached ();                        \
  32         } while (0)
  33 #define STATE_SET(s,v)          (s)->state = (v)
  34 #define STATE_ASSERT(s,v)       g_assert ((s)->state == (v))
  35 #else
  36 #define STATE_TRANSITION(s,o,n)
  37 #define STATE_SET(s,v)
  38 #define STATE_ASSERT(s,v)
  39 #endif
  40
  41 /*
  42  * Whenever we dispose a gray queue, we save its free list.  Then, in the next collection,
  43  * we reuse that free list for the new gray queue.
  44  */
  45 static GrayQueueSection *last_gray_queue_free_list;
  46
  47 void
  48 sgen_gray_object_alloc_queue_section (SgenGrayQueue *queue)
  49 {
  50         GrayQueueSection *section;
  51
  52         if (queue->free_list) {
  53                 /* Use the previously allocated queue sections if possible */
  54                 section = queue->free_list;
  55                 queue->free_list = section->next;
  56                 STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_FREE_LIST, GRAY_QUEUE_SECTION_STATE_FLOATING);
  57         } else {
  58                 HEAVY_STAT (stat_gray_queue_section_alloc ++);
  59
  60                 /* Allocate a new section */
  61                 section = (GrayQueueSection *)sgen_alloc_internal (INTERNAL_MEM_GRAY_QUEUE);
  62                 STATE_SET (section, GRAY_QUEUE_SECTION_STATE_FLOATING);
  63         }
  64
  65         /* Section is empty */
  66         section->size = 0;
  67
  68         STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_FLOATING, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
  69
  70         /* Link it with the others */
  71         section->next = queue->first;
  72         section->prev = NULL;
  73         if (queue->first)
  74                 queue->first->prev = section;
  75         else
  76                 queue->last = section;
  77         queue->first = section;
  78         queue->cursor = section->entries - 1;
  79
  80         mono_memory_write_barrier ();
  81         /*
  82          * FIXME
  83          * we could probably optimize the code to only rely on the write barrier
  84          * for synchronization with the stealer thread. Additionally we could also
  85          * do a write barrier once every other gray queue change, and request
  86          * to have a minimum of sections before stealing, to keep consistency.
  87          */
  88         InterlockedIncrement (&queue->num_sections);
  89 }
  90
  91 void
  92 sgen_gray_object_free_queue_section (GrayQueueSection *section)
  93 {
  94         HEAVY_STAT (stat_gray_queue_section_free ++);
  95
  96         STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_FLOATING, GRAY_QUEUE_SECTION_STATE_FREED);
  97         sgen_free_internal (section, INTERNAL_MEM_GRAY_QUEUE);
  98 }
  99
 100 /*
 101  * The following two functions are called in the inner loops of the
 102  * collector, so they need to be as fast as possible.  We have macros
 103  * for them in sgen-gc.h.
 104  */
 105
 106 void
 107 sgen_gray_object_enqueue (SgenGrayQueue *queue, GCObject *obj, SgenDescriptor desc)
 108 {
 109         GrayQueueEntry entry = SGEN_GRAY_QUEUE_ENTRY (obj, desc);
 110
 111         HEAVY_STAT (stat_gray_queue_enqueue_slow_path ++);
 112
 113         SGEN_ASSERT (9, obj, "enqueueing a null object");
 114         //sgen_check_objref (obj);
 115
 116 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
 117         if (queue->enqueue_check_func)
 118                 queue->enqueue_check_func (obj);
 119 #endif
 120
 121         if (G_UNLIKELY (!queue->first || queue->cursor == GRAY_LAST_CURSOR_POSITION (queue->first))) {
 122                 if (queue->first) {
 123                         /*
 124                          * We don't actively update the section size with each push/pop. For the first
 125                          * section we determine the size from the cursor position. For the reset of the
 126                          * sections we need to have the size set.
 127                          */
 128                         queue->first->size = SGEN_GRAY_QUEUE_SECTION_SIZE;
 129                 }
 130
 131                 sgen_gray_object_alloc_queue_section (queue);
 132         }
 133         STATE_ASSERT (queue->first, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
 134         SGEN_ASSERT (9, queue->cursor <= GRAY_LAST_CURSOR_POSITION (queue->first), "gray queue %p overflow, first %p, cursor %p", queue, queue->first, queue->cursor);
 135         *++queue->cursor = entry;
 136
 137 #ifdef SGEN_HEAVY_BINARY_PROTOCOL
 138         binary_protocol_gray_enqueue (queue, queue->cursor, obj);
 139 #endif
 140 }
 141
 142 GrayQueueEntry
 143 sgen_gray_object_dequeue (SgenGrayQueue *queue)
 144 {
 145         GrayQueueEntry entry;
 146
 147         HEAVY_STAT (stat_gray_queue_dequeue_slow_path ++);
 148
 149         if (sgen_gray_object_queue_is_empty (queue)) {
 150                 entry.obj = NULL;
 151                 return entry;
 152         }
 153
 154         STATE_ASSERT (queue->first, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
 155         SGEN_ASSERT (9, queue->cursor >= GRAY_FIRST_CURSOR_POSITION (queue->first), "gray queue %p underflow", queue);
 156
 157         entry = *queue->cursor--;
 158
 159 #ifdef SGEN_HEAVY_BINARY_PROTOCOL
 160         binary_protocol_gray_dequeue (queue, queue->cursor + 1, entry.obj);
 161 #endif
 162
 163         if (G_UNLIKELY (queue->cursor < GRAY_FIRST_CURSOR_POSITION (queue->first))) {
 164                 GrayQueueSection *section;
 165                 gint32 old_num_sections;
 166
 167                 old_num_sections = InterlockedDecrement (&queue->num_sections);
 168
 169                 if (old_num_sections <= 0) {
 170                         mono_os_mutex_lock (&queue->steal_mutex);
 171                 }
 172
 173                 section = queue->first;
 174                 queue->first = section->next;
 175                 if (queue->first) {
 176                         queue->first->prev = NULL;
 177                 } else {
 178                         queue->last = NULL;
 179                         SGEN_ASSERT (0, !old_num_sections, "Why do we have an inconsistent number of sections ?");
 180                 }
 181                 section->next = queue->free_list;
 182
 183                 STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_ENQUEUED, GRAY_QUEUE_SECTION_STATE_FREE_LIST);
 184
 185                 queue->free_list = section;
 186                 queue->cursor = queue->first ? queue->first->entries + queue->first->size - 1 : NULL;
 187
 188                 if (old_num_sections <= 0) {
 189                         mono_os_mutex_unlock (&queue->steal_mutex);
 190                 }
 191         }
 192
 193         return entry;
 194 }
 195
 196 GrayQueueSection*
 197 sgen_gray_object_dequeue_section (SgenGrayQueue *queue)
 198 {
 199         GrayQueueSection *section;
 200
 201         if (!queue->first)
 202                 return NULL;
 203
 204         /* We never steal from this queue */
 205         queue->num_sections--;
 206
 207         section = queue->first;
 208         queue->first = section->next;
 209         if (queue->first)
 210                 queue->first->prev = NULL;
 211         else
 212                 queue->last = NULL;
 213
 214         section->next = NULL;
 215         section->size = queue->cursor - section->entries + 1;
 216
 217         queue->cursor = queue->first ? queue->first->entries + queue->first->size - 1 : NULL;
 218
 219         STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_ENQUEUED, GRAY_QUEUE_SECTION_STATE_FLOATING);
 220
 221         return section;
 222 }
 223
 224 GrayQueueSection*
 225 sgen_gray_object_steal_section (SgenGrayQueue *queue)
 226 {
 227         gint32 sections_remaining;
 228         GrayQueueSection *section = NULL;
 229
 230         /*
 231          * With each push/pop into the queue we increment the number of sections.
 232          * There is only one thread accessing the top (the owner) and potentially
 233          * multiple workers trying to steal sections from the bottom, so we need
 234          * to lock. A num sections decrement from the owner means that the first
 235          * section is reserved, while a decrement by the stealer means that the
 236          * last section is reserved. If after we decrement the num sections, we
 237          * have at least one more section present, it means we can't race with
 238          * the other thread. If this is not the case the steal end abandons the
 239          * pop, setting back the num_sections, while the owner end will take a
 240          * lock to make sure we are not racing with the stealer (since the stealer
 241          * might have popped an entry and be in the process of updating the entry
 242          * that the owner is trying to pop.
 243          */
 244
 245         if (queue->num_sections <= 1)
 246                 return NULL;
 247
 248         /* Give up if there is contention on the last section */
 249         if (mono_os_mutex_trylock (&queue->steal_mutex) != 0)
 250                 return NULL;
 251
 252         sections_remaining = InterlockedDecrement (&queue->num_sections);
 253         if (sections_remaining <= 0) {
 254                 /* The section that we tried to steal might be the head of the queue. */
 255                 InterlockedIncrement (&queue->num_sections);
 256         } else {
 257                 /* We have reserved for us the tail section of the queue */
 258                 section = queue->last;
 259                 SGEN_ASSERT (0, section, "Why we don't have any sections to steal?");
 260                 SGEN_ASSERT (0, !section->next, "Why aren't we stealing the tail?");
 261                 queue->last = section->prev;
 262                 section->prev = NULL;
 263                 SGEN_ASSERT (0, queue->last, "Why are we stealing the last section?");
 264                 queue->last->next = NULL;
 265
 266                 STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_ENQUEUED, GRAY_QUEUE_SECTION_STATE_FLOATING);
 267         }
 268
 269         mono_os_mutex_unlock (&queue->steal_mutex);
 270         return section;
 271 }
 272
 273 void
 274 sgen_gray_object_enqueue_section (SgenGrayQueue *queue, GrayQueueSection *section)
 275 {
 276         STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_FLOATING, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
 277
 278         if (queue->first)
 279                 queue->first->size = queue->cursor - queue->first->entries + 1;
 280
 281         section->next = queue->first;
 282         section->prev = NULL;
 283         if (queue->first)
 284                 queue->first->prev = section;
 285         else
 286                 queue->last = section;
 287         queue->first = section;
 288         queue->cursor = queue->first->entries + queue->first->size - 1;
 289 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
 290         if (queue->enqueue_check_func) {
 291                 int i;
 292                 for (i = 0; i < section->size; ++i)
 293                         queue->enqueue_check_func (section->entries [i].obj);
 294         }
 295 #endif
 296         mono_memory_write_barrier ();
 297         InterlockedIncrement (&queue->num_sections);
 298 }
 299
 300 void
 301 sgen_gray_object_queue_trim_free_list (SgenGrayQueue *queue)
 302 {
 303         GrayQueueSection *section, *next;
 304         int i = 0;
 305         for (section = queue->free_list; section && i < GRAY_QUEUE_LENGTH_LIMIT - 1; section = section->next) {
 306                 STATE_ASSERT (section, GRAY_QUEUE_SECTION_STATE_FREE_LIST);
 307                 i ++;
 308         }
 309         if (!section)
 310                 return;
 311         while (section->next) {
 312                 next = section->next;
 313                 section->next = next->next;
 314                 STATE_TRANSITION (next, GRAY_QUEUE_SECTION_STATE_FREE_LIST, GRAY_QUEUE_SECTION_STATE_FLOATING);
 315                 sgen_gray_object_free_queue_section (next);
 316         }
 317 }
 318
 319 void
 320 sgen_gray_object_queue_init (SgenGrayQueue *queue, GrayQueueEnqueueCheckFunc enqueue_check_func, gboolean reuse_free_list)
 321 {
 322         memset (queue, 0, sizeof (SgenGrayQueue));
 323
 324 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
 325         queue->enqueue_check_func = enqueue_check_func;
 326 #endif
 327
 328         mono_os_mutex_init (&queue->steal_mutex);
 329
 330         if (reuse_free_list) {
 331                 queue->free_list = last_gray_queue_free_list;
 332                 last_gray_queue_free_list = NULL;
 333         }
 334 }
 335
 336 void
 337 sgen_gray_object_queue_dispose (SgenGrayQueue *queue)
 338 {
 339         SGEN_ASSERT (0, sgen_gray_object_queue_is_empty (queue), "Why are we disposing a gray queue that's not empty?");
 340
 341         /* Free the extra sections allocated during the last collection */
 342         sgen_gray_object_queue_trim_free_list (queue);
 343
 344         SGEN_ASSERT (0, !last_gray_queue_free_list, "Are we disposing two gray queues after another?");
 345         last_gray_queue_free_list = queue->free_list;
 346
 347         /* just to make sure */
 348         memset (queue, 0, sizeof (SgenGrayQueue));
 349 }
 350
 351 void
 352 sgen_gray_object_queue_deinit (SgenGrayQueue *queue)
 353 {
 354         g_assert (!queue->first);
 355         while (queue->free_list) {
 356                 GrayQueueSection *next = queue->free_list->next;
 357                 STATE_TRANSITION (queue->free_list, GRAY_QUEUE_SECTION_STATE_FREE_LIST, GRAY_QUEUE_SECTION_STATE_FLOATING);
 358                 sgen_gray_object_free_queue_section (queue->free_list);
 359                 queue->free_list = next;
 360         }
 361 }
 362
 363 static void
 364 lock_section_queue (SgenSectionGrayQueue *queue)
 365 {
 366         if (!queue->locked)
 367                 return;
 368
 369         mono_os_mutex_lock (&queue->lock);
 370 }
 371
 372 static void
 373 unlock_section_queue (SgenSectionGrayQueue *queue)
 374 {
 375         if (!queue->locked)
 376                 return;
 377
 378         mono_os_mutex_unlock (&queue->lock);
 379 }
 380
 381 void
 382 sgen_section_gray_queue_init (SgenSectionGrayQueue *queue, gboolean locked, GrayQueueEnqueueCheckFunc enqueue_check_func)
 383 {
 384         g_assert (sgen_section_gray_queue_is_empty (queue));
 385
 386         queue->locked = locked;
 387         if (locked) {
 388                 mono_os_mutex_init_recursive (&queue->lock);
 389         }
 390
 391 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
 392         queue->enqueue_check_func = enqueue_check_func;
 393 #endif
 394 }
 395
 396 gboolean
 397 sgen_section_gray_queue_is_empty (SgenSectionGrayQueue *queue)
 398 {
 399         return !queue->first;
 400 }
 401
 402 GrayQueueSection*
 403 sgen_section_gray_queue_dequeue (SgenSectionGrayQueue *queue)
 404 {
 405         GrayQueueSection *section;
 406
 407         lock_section_queue (queue);
 408
 409         if (queue->first) {
 410                 section = queue->first;
 411                 queue->first = section->next;
 412
 413                 STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_ENQUEUED, GRAY_QUEUE_SECTION_STATE_FLOATING);
 414
 415                 section->next = NULL;
 416         } else {
 417                 section = NULL;
 418         }
 419
 420         unlock_section_queue (queue);
 421
 422         return section;
 423 }
 424
 425 void
 426 sgen_section_gray_queue_enqueue (SgenSectionGrayQueue *queue, GrayQueueSection *section)
 427 {
 428         STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_FLOATING, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
 429
 430         lock_section_queue (queue);
 431
 432         section->next = queue->first;
 433         queue->first = section;
 434 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
 435         if (queue->enqueue_check_func) {
 436                 int i;
 437                 for (i = 0; i < section->size; ++i)
 438                         queue->enqueue_check_func (section->entries [i].obj);
 439         }
 440 #endif
 441
 442         unlock_section_queue (queue);
 443 }
 444
 445 void
 446 sgen_init_gray_queues (void)
 447 {
 448 #ifdef HEAVY_STATISTICS
 449         mono_counters_register ("Gray Queue alloc section", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_gray_queue_section_alloc);
 450         mono_counters_register ("Gray Queue free section", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_gray_queue_section_free);
 451         mono_counters_register ("Gray Queue enqueue fast path", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_gray_queue_enqueue_fast_path);
 452         mono_counters_register ("Gray Queue dequeue fast path", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_gray_queue_dequeue_fast_path);
 453         mono_counters_register ("Gray Queue enqueue slow path", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_gray_queue_enqueue_slow_path);
 454         mono_counters_register ("Gray Queue dequeue slow path", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_gray_queue_dequeue_slow_path);
 455 #endif
 456 }
 457 #endif