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