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->size = SGEN_GRAY_QUEUE_SECTION_SIZE;
  66
  67         STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_FLOATING, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
  68
  69         /* Link it with the others */
  70         section->next = queue->first;
  71         queue->first = section;
  72         queue->cursor = section->entries - 1;
  73 }
  74
  75 void
  76 sgen_gray_object_free_queue_section (GrayQueueSection *section)
  77 {
  78         HEAVY_STAT (stat_gray_queue_section_free ++);
  79
  80         STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_FLOATING, GRAY_QUEUE_SECTION_STATE_FREED);
  81         sgen_free_internal (section, INTERNAL_MEM_GRAY_QUEUE);
  82 }
  83
  84 /*
  85  * The following two functions are called in the inner loops of the
  86  * collector, so they need to be as fast as possible.  We have macros
  87  * for them in sgen-gc.h.
  88  */
  89
  90 void
  91 sgen_gray_object_enqueue (SgenGrayQueue *queue, GCObject *obj, SgenDescriptor desc)
  92 {
  93         GrayQueueEntry entry = SGEN_GRAY_QUEUE_ENTRY (obj, desc);
  94
  95         HEAVY_STAT (stat_gray_queue_enqueue_slow_path ++);
  96
  97         SGEN_ASSERT (9, obj, "enqueueing a null object");
  98         //sgen_check_objref (obj);
  99
 100 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
 101         if (queue->enqueue_check_func)
 102                 queue->enqueue_check_func (obj);
 103 #endif
 104
 105         if (G_UNLIKELY (!queue->first || queue->cursor == GRAY_LAST_CURSOR_POSITION (queue->first))) {
 106                 if (queue->first) {
 107                         /* Set the current section size back to default, might have been changed by sgen_gray_object_dequeue_section */
 108                         queue->first->size = SGEN_GRAY_QUEUE_SECTION_SIZE;
 109                 }
 110
 111                 sgen_gray_object_alloc_queue_section (queue);
 112         }
 113         STATE_ASSERT (queue->first, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
 114         SGEN_ASSERT (9, queue->cursor <= GRAY_LAST_CURSOR_POSITION (queue->first), "gray queue %p overflow, first %p, cursor %p", queue, queue->first, queue->cursor);
 115         *++queue->cursor = entry;
 116
 117 #ifdef SGEN_HEAVY_BINARY_PROTOCOL
 118         binary_protocol_gray_enqueue (queue, queue->cursor, obj);
 119 #endif
 120 }
 121
 122 GrayQueueEntry
 123 sgen_gray_object_dequeue (SgenGrayQueue *queue)
 124 {
 125         GrayQueueEntry entry;
 126
 127         HEAVY_STAT (stat_gray_queue_dequeue_slow_path ++);
 128
 129         if (sgen_gray_object_queue_is_empty (queue)) {
 130                 entry.obj = NULL;
 131                 return entry;
 132         }
 133
 134         STATE_ASSERT (queue->first, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
 135         SGEN_ASSERT (9, queue->cursor >= GRAY_FIRST_CURSOR_POSITION (queue->first), "gray queue %p underflow", queue);
 136
 137         entry = *queue->cursor--;
 138
 139 #ifdef SGEN_HEAVY_BINARY_PROTOCOL
 140         binary_protocol_gray_dequeue (queue, queue->cursor + 1, entry.obj);
 141 #endif
 142
 143         if (G_UNLIKELY (queue->cursor < GRAY_FIRST_CURSOR_POSITION (queue->first))) {
 144                 GrayQueueSection *section = queue->first;
 145                 queue->first = section->next;
 146                 section->next = queue->free_list;
 147
 148                 STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_ENQUEUED, GRAY_QUEUE_SECTION_STATE_FREE_LIST);
 149
 150                 queue->free_list = section;
 151                 queue->cursor = queue->first ? queue->first->entries + queue->first->size - 1 : NULL;
 152         }
 153
 154         return entry;
 155 }
 156
 157 GrayQueueSection*
 158 sgen_gray_object_dequeue_section (SgenGrayQueue *queue)
 159 {
 160         GrayQueueSection *section;
 161
 162         if (!queue->first)
 163                 return NULL;
 164
 165         section = queue->first;
 166         queue->first = section->next;
 167
 168         section->next = NULL;
 169         section->size = queue->cursor - section->entries + 1;
 170
 171         queue->cursor = queue->first ? queue->first->entries + queue->first->size - 1 : NULL;
 172
 173         STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_ENQUEUED, GRAY_QUEUE_SECTION_STATE_FLOATING);
 174
 175         return section;
 176 }
 177
 178 void
 179 sgen_gray_object_enqueue_section (SgenGrayQueue *queue, GrayQueueSection *section)
 180 {
 181         STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_FLOATING, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
 182
 183         if (queue->first)
 184                 queue->first->size = queue->cursor - queue->first->entries + 1;
 185
 186         section->next = queue->first;
 187         queue->first = section;
 188         queue->cursor = queue->first->entries + queue->first->size - 1;
 189 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
 190         if (queue->enqueue_check_func) {
 191                 int i;
 192                 for (i = 0; i < section->size; ++i)
 193                         queue->enqueue_check_func (section->entries [i].obj);
 194         }
 195 #endif
 196 }
 197
 198 void
 199 sgen_gray_object_queue_trim_free_list (SgenGrayQueue *queue)
 200 {
 201         GrayQueueSection *section, *next;
 202         int i = 0;
 203         for (section = queue->free_list; section && i < GRAY_QUEUE_LENGTH_LIMIT - 1; section = section->next) {
 204                 STATE_ASSERT (section, GRAY_QUEUE_SECTION_STATE_FREE_LIST);
 205                 i ++;
 206         }
 207         if (!section)
 208                 return;
 209         while (section->next) {
 210                 next = section->next;
 211                 section->next = next->next;
 212                 STATE_TRANSITION (next, GRAY_QUEUE_SECTION_STATE_FREE_LIST, GRAY_QUEUE_SECTION_STATE_FLOATING);
 213                 sgen_gray_object_free_queue_section (next);
 214         }
 215 }
 216
 217 void
 218 sgen_gray_object_queue_init (SgenGrayQueue *queue, GrayQueueEnqueueCheckFunc enqueue_check_func, gboolean reuse_free_list)
 219 {
 220         memset (queue, 0, sizeof (SgenGrayQueue));
 221
 222 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
 223         queue->enqueue_check_func = enqueue_check_func;
 224 #endif
 225
 226         if (reuse_free_list) {
 227                 queue->free_list = last_gray_queue_free_list;
 228                 last_gray_queue_free_list = NULL;
 229         }
 230 }
 231
 232 void
 233 sgen_gray_object_queue_dispose (SgenGrayQueue *queue)
 234 {
 235         SGEN_ASSERT (0, sgen_gray_object_queue_is_empty (queue), "Why are we disposing a gray queue that's not empty?");
 236
 237         /* Free the extra sections allocated during the last collection */
 238         sgen_gray_object_queue_trim_free_list (queue);
 239
 240         SGEN_ASSERT (0, !last_gray_queue_free_list, "Are we disposing two gray queues after another?");
 241         last_gray_queue_free_list = queue->free_list;
 242
 243         /* just to make sure */
 244         memset (queue, 0, sizeof (SgenGrayQueue));
 245 }
 246
 247 void
 248 sgen_gray_object_queue_deinit (SgenGrayQueue *queue)
 249 {
 250         g_assert (!queue->first);
 251         while (queue->free_list) {
 252                 GrayQueueSection *next = queue->free_list->next;
 253                 STATE_TRANSITION (queue->free_list, GRAY_QUEUE_SECTION_STATE_FREE_LIST, GRAY_QUEUE_SECTION_STATE_FLOATING);
 254                 sgen_gray_object_free_queue_section (queue->free_list);
 255                 queue->free_list = next;
 256         }
 257 }
 258
 259 static void
 260 lock_section_queue (SgenSectionGrayQueue *queue)
 261 {
 262         if (!queue->locked)
 263                 return;
 264
 265         mono_os_mutex_lock (&queue->lock);
 266 }
 267
 268 static void
 269 unlock_section_queue (SgenSectionGrayQueue *queue)
 270 {
 271         if (!queue->locked)
 272                 return;
 273
 274         mono_os_mutex_unlock (&queue->lock);
 275 }
 276
 277 void
 278 sgen_section_gray_queue_init (SgenSectionGrayQueue *queue, gboolean locked, GrayQueueEnqueueCheckFunc enqueue_check_func)
 279 {
 280         g_assert (sgen_section_gray_queue_is_empty (queue));
 281
 282         queue->locked = locked;
 283         if (locked) {
 284                 mono_os_mutex_init_recursive (&queue->lock);
 285         }
 286
 287 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
 288         queue->enqueue_check_func = enqueue_check_func;
 289 #endif
 290 }
 291
 292 gboolean
 293 sgen_section_gray_queue_is_empty (SgenSectionGrayQueue *queue)
 294 {
 295         return !queue->first;
 296 }
 297
 298 GrayQueueSection*
 299 sgen_section_gray_queue_dequeue (SgenSectionGrayQueue *queue)
 300 {
 301         GrayQueueSection *section;
 302
 303         lock_section_queue (queue);
 304
 305         if (queue->first) {
 306                 section = queue->first;
 307                 queue->first = section->next;
 308
 309                 STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_ENQUEUED, GRAY_QUEUE_SECTION_STATE_FLOATING);
 310
 311                 section->next = NULL;
 312         } else {
 313                 section = NULL;
 314         }
 315
 316         unlock_section_queue (queue);
 317
 318         return section;
 319 }
 320
 321 void
 322 sgen_section_gray_queue_enqueue (SgenSectionGrayQueue *queue, GrayQueueSection *section)
 323 {
 324         STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_FLOATING, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
 325
 326         lock_section_queue (queue);
 327
 328         section->next = queue->first;
 329         queue->first = section;
 330 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
 331         if (queue->enqueue_check_func) {
 332                 int i;
 333                 for (i = 0; i < section->size; ++i)
 334                         queue->enqueue_check_func (section->entries [i].obj);
 335         }
 336 #endif
 337
 338         unlock_section_queue (queue);
 339 }
 340
 341 void
 342 sgen_init_gray_queues (void)
 343 {
 344 #ifdef HEAVY_STATISTICS
 345         mono_counters_register ("Gray Queue alloc section", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_gray_queue_section_alloc);
 346         mono_counters_register ("Gray Queue free section", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_gray_queue_section_free);
 347         mono_counters_register ("Gray Queue enqueue fast path", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_gray_queue_enqueue_fast_path);
 348         mono_counters_register ("Gray Queue dequeue fast path", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_gray_queue_dequeue_fast_path);
 349         mono_counters_register ("Gray Queue enqueue slow path", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_gray_queue_enqueue_slow_path);
 350         mono_counters_register ("Gray Queue dequeue slow path", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_gray_queue_dequeue_slow_path);
 351 #endif
 352 }
 353 #endif