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