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