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 #define GRAY_QUEUE_LENGTH_LIMIT 64
  29
  30 #ifdef SGEN_CHECK_GRAY_OBJECT_SECTIONS
  31 #define STATE_TRANSITION(s,o,n) do {                                    \
  32                 int __old = (o);                                        \
  33                 if (InterlockedCompareExchange ((volatile int*)&(s)->state, (n), __old) != __old) \
  34                         g_assert_not_reached ();                        \
  35         } while (0)
  36 #define STATE_SET(s,v)          (s)->state = (v)
  37 #define STATE_ASSERT(s,v)       g_assert ((s)->state == (v))
  38 #else
  39 #define STATE_TRANSITION(s,o,n)
  40 #define STATE_SET(s,v)
  41 #define STATE_ASSERT(s,v)
  42 #endif
  43
  44 void
  45 sgen_gray_object_alloc_queue_section (SgenGrayQueue *queue)
  46 {
  47         GrayQueueSection *section;
  48
  49         HEAVY_STAT (gc_stats.gray_queue_section_alloc ++);
  50
  51         if (queue->alloc_prepare_func)
  52                 queue->alloc_prepare_func (queue);
  53
  54         if (queue->free_list) {
  55                 /* Use the previously allocated queue sections if possible */
  56                 section = queue->free_list;
  57                 queue->free_list = section->next;
  58                 STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_FREE_LIST, GRAY_QUEUE_SECTION_STATE_FLOATING);
  59         } else {
  60                 /* Allocate a new section */
  61                 section = 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 = (char**)section->objects - 1;
  73 }
  74
  75 void
  76 sgen_gray_object_free_queue_section (GrayQueueSection *section)
  77 {
  78         HEAVY_STAT (gc_stats.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, char *obj)
  92 {
  93         HEAVY_STAT (gc_stats.gray_queue_enqueue_slow_path ++);
  94
  95         SGEN_ASSERT (9, obj, "enqueueing a null object");
  96         //sgen_check_objref (obj);
  97
  98 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
  99         if (queue->enqueue_check_func)
 100                 queue->enqueue_check_func (obj);
 101 #endif
 102
 103         if (G_UNLIKELY (!queue->first || queue->cursor == GRAY_LAST_CURSOR_POSITION (queue->first))) {
 104                 if (queue->first) {
 105                         /* Set the current section size back to default, might have been changed by sgen_gray_object_dequeue_section */
 106                         queue->first->size = SGEN_GRAY_QUEUE_SECTION_SIZE;
 107                 }
 108
 109                 sgen_gray_object_alloc_queue_section (queue);
 110         }
 111         STATE_ASSERT (queue->first, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
 112         SGEN_ASSERT (9, queue->cursor <= GRAY_LAST_CURSOR_POSITION (queue->first), "gray queue %p overflow, first %p, cursor %p", queue, queue->first, queue->cursor);
 113         *++queue->cursor = obj;
 114
 115 #ifdef SGEN_HEAVY_BINARY_PROTOCOL
 116         binary_protocol_gray_enqueue (queue, queue->cursor, obj);
 117 #endif
 118 }
 119
 120 char*
 121 sgen_gray_object_dequeue (SgenGrayQueue *queue)
 122 {
 123         char *obj;
 124
 125         HEAVY_STAT (gc_stats.gray_queue_dequeue_slow_path ++);
 126
 127         if (sgen_gray_object_queue_is_empty (queue))
 128                 return NULL;
 129
 130         STATE_ASSERT (queue->first, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
 131         SGEN_ASSERT (9, queue->cursor >= (char**)queue->first->objects, "gray queue %p underflow, first %p, cursor %d", queue, queue->first, queue->cursor);
 132
 133         obj = *queue->cursor--;
 134
 135 #ifdef SGEN_HEAVY_BINARY_PROTOCOL
 136         binary_protocol_gray_dequeue (queue, queue->cursor + 1, obj);
 137 #endif
 138
 139         if (G_UNLIKELY (queue->cursor == (char**)queue->first->objects - 1)) {
 140                 GrayQueueSection *section = queue->first;
 141                 queue->first = section->next;
 142                 section->next = queue->free_list;
 143
 144                 STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_ENQUEUED, GRAY_QUEUE_SECTION_STATE_FREE_LIST);
 145
 146                 queue->free_list = section;
 147                 queue->cursor = queue->first ? (char**)queue->first->objects + queue->first->size - 1 : NULL;
 148         }
 149
 150         return obj;
 151 }
 152
 153 GrayQueueSection*
 154 sgen_gray_object_dequeue_section (SgenGrayQueue *queue)
 155 {
 156         GrayQueueSection *section;
 157
 158         if (!queue->first)
 159                 return NULL;
 160
 161         section = queue->first;
 162         queue->first = section->next;
 163
 164         section->next = NULL;
 165         section->size = queue->cursor - (char**)section->objects + 1;
 166
 167         queue->cursor = queue->first ? (char**)queue->first->objects + queue->first->size - 1 : NULL;
 168
 169         STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_ENQUEUED, GRAY_QUEUE_SECTION_STATE_FLOATING);
 170
 171         return section;
 172 }
 173
 174 void
 175 sgen_gray_object_enqueue_section (SgenGrayQueue *queue, GrayQueueSection *section)
 176 {
 177         STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_FLOATING, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
 178
 179         if (queue->first)
 180                 queue->first->size = queue->cursor - (char**)queue->first->objects + 1;
 181
 182         section->next = queue->first;
 183         queue->first = section;
 184         queue->cursor = (char**)queue->first->objects + queue->first->size - 1;
 185 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
 186         if (queue->enqueue_check_func) {
 187                 int i;
 188                 for (i = 0; i < section->size; ++i)
 189                         queue->enqueue_check_func (section->objects [i]);
 190         }
 191 #endif
 192 }
 193
 194 void
 195 sgen_gray_object_queue_init (SgenGrayQueue *queue, GrayQueueEnqueueCheckFunc enqueue_check_func)
 196 {
 197         GrayQueueSection *section, *next;
 198         int i;
 199
 200         g_assert (sgen_gray_object_queue_is_empty (queue));
 201
 202         queue->alloc_prepare_func = NULL;
 203         queue->alloc_prepare_data = NULL;
 204 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
 205         queue->enqueue_check_func = enqueue_check_func;
 206 #endif
 207
 208         /* Free the extra sections allocated during the last collection */
 209         i = 0;
 210         for (section = queue->free_list; section && i < GRAY_QUEUE_LENGTH_LIMIT - 1; section = section->next) {
 211                 STATE_ASSERT (section, GRAY_QUEUE_SECTION_STATE_FREE_LIST);
 212                 i ++;
 213         }
 214         if (!section)
 215                 return;
 216         while (section->next) {
 217                 next = section->next;
 218                 section->next = next->next;
 219                 STATE_TRANSITION (next, GRAY_QUEUE_SECTION_STATE_FREE_LIST, GRAY_QUEUE_SECTION_STATE_FLOATING);
 220                 sgen_gray_object_free_queue_section (next);
 221         }
 222 }
 223
 224 static void
 225 invalid_prepare_func (SgenGrayQueue *queue)
 226 {
 227         g_assert_not_reached ();
 228 }
 229
 230 void
 231 sgen_gray_object_queue_init_invalid (SgenGrayQueue *queue)
 232 {
 233         sgen_gray_object_queue_init (queue, FALSE);
 234         queue->alloc_prepare_func = invalid_prepare_func;
 235         queue->alloc_prepare_data = NULL;
 236 }
 237
 238 void
 239 sgen_gray_object_queue_init_with_alloc_prepare (SgenGrayQueue *queue, GrayQueueEnqueueCheckFunc enqueue_check_func,
 240                 GrayQueueAllocPrepareFunc alloc_prepare_func, void *data)
 241 {
 242         sgen_gray_object_queue_init (queue, enqueue_check_func);
 243         queue->alloc_prepare_func = alloc_prepare_func;
 244         queue->alloc_prepare_data = data;
 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 void
 260 sgen_gray_object_queue_disable_alloc_prepare (SgenGrayQueue *queue)
 261 {
 262         queue->alloc_prepare_func = NULL;
 263         queue->alloc_prepare_data = NULL;
 264 }
 265
 266 static void
 267 lock_section_queue (SgenSectionGrayQueue *queue)
 268 {
 269         if (!queue->locked)
 270                 return;
 271
 272         mono_mutex_lock (&queue->lock);
 273 }
 274
 275 static void
 276 unlock_section_queue (SgenSectionGrayQueue *queue)
 277 {
 278         if (!queue->locked)
 279                 return;
 280
 281         mono_mutex_unlock (&queue->lock);
 282 }
 283
 284 void
 285 sgen_section_gray_queue_init (SgenSectionGrayQueue *queue, gboolean locked, GrayQueueEnqueueCheckFunc enqueue_check_func)
 286 {
 287         g_assert (sgen_section_gray_queue_is_empty (queue));
 288
 289         queue->locked = locked;
 290         if (locked) {
 291                 mono_mutex_init_recursive (&queue->lock);
 292         }
 293
 294 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
 295         queue->enqueue_check_func = enqueue_check_func;
 296 #endif
 297 }
 298
 299 gboolean
 300 sgen_section_gray_queue_is_empty (SgenSectionGrayQueue *queue)
 301 {
 302         return !queue->first;
 303 }
 304
 305 GrayQueueSection*
 306 sgen_section_gray_queue_dequeue (SgenSectionGrayQueue *queue)
 307 {
 308         GrayQueueSection *section;
 309
 310         lock_section_queue (queue);
 311
 312         if (queue->first) {
 313                 section = queue->first;
 314                 queue->first = section->next;
 315
 316                 STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_ENQUEUED, GRAY_QUEUE_SECTION_STATE_FLOATING);
 317
 318                 section->next = NULL;
 319         } else {
 320                 section = NULL;
 321         }
 322
 323         unlock_section_queue (queue);
 324
 325         return section;
 326 }
 327
 328 void
 329 sgen_section_gray_queue_enqueue (SgenSectionGrayQueue *queue, GrayQueueSection *section)
 330 {
 331         STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_FLOATING, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
 332
 333         lock_section_queue (queue);
 334
 335         section->next = queue->first;
 336         queue->first = section;
 337 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
 338         if (queue->enqueue_check_func) {
 339                 int i;
 340                 for (i = 0; i < section->size; ++i)
 341                         queue->enqueue_check_func (section->objects [i]);
 342         }
 343 #endif
 344
 345         unlock_section_queue (queue);
 346 }
 347
 348 #endif