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