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
  27 #define GRAY_QUEUE_LENGTH_LIMIT 64
  28
  29 #ifdef SGEN_CHECK_GRAY_OBJECT_SECTIONS
  30 #define STATE_TRANSITION(s,o,n) do {                                    \
  31                 int __old = (o);                                        \
  32                 if (InterlockedCompareExchange ((volatile int*)&(s)->state, (n), __old) != __old) \
  33                         g_assert_not_reached ();                        \
  34         } while (0)
  35 #define STATE_SET(s,v)          (s)->state = (v)
  36 #define STATE_ASSERT(s,v)       g_assert ((s)->state == (v))
  37 #else
  38 #define STATE_TRANSITION(s,o,n)
  39 #define STATE_SET(s,v)
  40 #define STATE_ASSERT(s,v)
  41 #endif
  42
  43 void
  44 sgen_gray_object_alloc_queue_section (SgenGrayQueue *queue)
  45 {
  46         GrayQueueSection *section;
  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 = sgen_alloc_internal (INTERNAL_MEM_GRAY_QUEUE);
  59                 STATE_SET (section, GRAY_QUEUE_SECTION_STATE_FLOATING);
  60         }
  61
  62         section->end = 0;
  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 }
  70
  71 void
  72 sgen_gray_object_free_queue_section (GrayQueueSection *section)
  73 {
  74         STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_FLOATING, GRAY_QUEUE_SECTION_STATE_FREED);
  75         sgen_free_internal (section, INTERNAL_MEM_GRAY_QUEUE);
  76 }
  77
  78 /*
  79  * The following two functions are called in the inner loops of the
  80  * collector, so they need to be as fast as possible.  We have macros
  81  * for them in sgen-gc.h.
  82  */
  83
  84 void
  85 sgen_gray_object_enqueue (SgenGrayQueue *queue, char *obj)
  86 {
  87         SGEN_ASSERT (9, obj, "enqueueing a null object");
  88         //sgen_check_objref (obj);
  89
  90 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
  91         if (queue->enqueue_check_func)
  92                 queue->enqueue_check_func (obj);
  93 #endif
  94
  95         if (G_UNLIKELY (!queue->first || queue->first->end == SGEN_GRAY_QUEUE_SECTION_SIZE))
  96                 sgen_gray_object_alloc_queue_section (queue);
  97         STATE_ASSERT (queue->first, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
  98         SGEN_ASSERT (9, queue->first->end < SGEN_GRAY_QUEUE_SECTION_SIZE, "gray queue %p overflow, first %p, end %d", queue, queue->first, queue->first->end);
  99         queue->first->objects [queue->first->end++] = obj;
 100 }
 101
 102 char*
 103 sgen_gray_object_dequeue (SgenGrayQueue *queue)
 104 {
 105         char *obj;
 106
 107         if (sgen_gray_object_queue_is_empty (queue))
 108                 return NULL;
 109
 110         STATE_ASSERT (queue->first, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
 111         SGEN_ASSERT (9, queue->first->end, "gray queue %p underflow, first %p, end %d", queue, queue->first, queue->first->end);
 112
 113         obj = queue->first->objects [--queue->first->end];
 114
 115         if (G_UNLIKELY (queue->first->end == 0)) {
 116                 GrayQueueSection *section = queue->first;
 117                 queue->first = section->next;
 118                 section->next = queue->free_list;
 119
 120                 STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_ENQUEUED, GRAY_QUEUE_SECTION_STATE_FREE_LIST);
 121
 122                 queue->free_list = section;
 123         }
 124
 125         return obj;
 126 }
 127
 128 GrayQueueSection*
 129 sgen_gray_object_dequeue_section (SgenGrayQueue *queue)
 130 {
 131         GrayQueueSection *section;
 132
 133         if (!queue->first)
 134                 return NULL;
 135
 136         section = queue->first;
 137         queue->first = section->next;
 138
 139         section->next = NULL;
 140
 141         STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_ENQUEUED, GRAY_QUEUE_SECTION_STATE_FLOATING);
 142
 143         return section;
 144 }
 145
 146 void
 147 sgen_gray_object_enqueue_section (SgenGrayQueue *queue, GrayQueueSection *section)
 148 {
 149         STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_FLOATING, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
 150
 151         section->next = queue->first;
 152         queue->first = section;
 153 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
 154         if (queue->enqueue_check_func) {
 155                 int i;
 156                 for (i = 0; i < section->end; ++i)
 157                         queue->enqueue_check_func (section->objects [i]);
 158         }
 159 #endif
 160 }
 161
 162 void
 163 sgen_gray_object_queue_init (SgenGrayQueue *queue, GrayQueueEnqueueCheckFunc enqueue_check_func)
 164 {
 165         GrayQueueSection *section, *next;
 166         int i;
 167
 168         g_assert (sgen_gray_object_queue_is_empty (queue));
 169
 170         queue->alloc_prepare_func = NULL;
 171         queue->alloc_prepare_data = NULL;
 172 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
 173         queue->enqueue_check_func = enqueue_check_func;
 174 #endif
 175
 176         /* Free the extra sections allocated during the last collection */
 177         i = 0;
 178         for (section = queue->free_list; section && i < GRAY_QUEUE_LENGTH_LIMIT - 1; section = section->next) {
 179                 STATE_ASSERT (section, GRAY_QUEUE_SECTION_STATE_FREE_LIST);
 180                 i ++;
 181         }
 182         if (!section)
 183                 return;
 184         while (section->next) {
 185                 next = section->next;
 186                 section->next = next->next;
 187                 STATE_TRANSITION (next, GRAY_QUEUE_SECTION_STATE_FREE_LIST, GRAY_QUEUE_SECTION_STATE_FLOATING);
 188                 sgen_gray_object_free_queue_section (next);
 189         }
 190 }
 191
 192 static void
 193 invalid_prepare_func (SgenGrayQueue *queue)
 194 {
 195         g_assert_not_reached ();
 196 }
 197
 198 void
 199 sgen_gray_object_queue_init_invalid (SgenGrayQueue *queue)
 200 {
 201         sgen_gray_object_queue_init (queue, FALSE);
 202         queue->alloc_prepare_func = invalid_prepare_func;
 203         queue->alloc_prepare_data = NULL;
 204 }
 205
 206 void
 207 sgen_gray_object_queue_init_with_alloc_prepare (SgenGrayQueue *queue, GrayQueueEnqueueCheckFunc enqueue_check_func,
 208                 GrayQueueAllocPrepareFunc alloc_prepare_func, void *data)
 209 {
 210         sgen_gray_object_queue_init (queue, enqueue_check_func);
 211         queue->alloc_prepare_func = alloc_prepare_func;
 212         queue->alloc_prepare_data = data;
 213 }
 214
 215 void
 216 sgen_gray_object_queue_deinit (SgenGrayQueue *queue)
 217 {
 218         g_assert (!queue->first);
 219         while (queue->free_list) {
 220                 GrayQueueSection *next = queue->free_list->next;
 221                 STATE_TRANSITION (queue->free_list, GRAY_QUEUE_SECTION_STATE_FREE_LIST, GRAY_QUEUE_SECTION_STATE_FLOATING);
 222                 sgen_gray_object_free_queue_section (queue->free_list);
 223                 queue->free_list = next;
 224         }
 225 }
 226
 227 void
 228 sgen_gray_object_queue_disable_alloc_prepare (SgenGrayQueue *queue)
 229 {
 230         queue->alloc_prepare_func = NULL;
 231         queue->alloc_prepare_data = NULL;
 232 }
 233
 234 static void
 235 lock_section_queue (SgenSectionGrayQueue *queue)
 236 {
 237         if (!queue->locked)
 238                 return;
 239
 240         mono_mutex_lock (&queue->lock);
 241 }
 242
 243 static void
 244 unlock_section_queue (SgenSectionGrayQueue *queue)
 245 {
 246         if (!queue->locked)
 247                 return;
 248
 249         mono_mutex_unlock (&queue->lock);
 250 }
 251
 252 void
 253 sgen_section_gray_queue_init (SgenSectionGrayQueue *queue, gboolean locked, GrayQueueEnqueueCheckFunc enqueue_check_func)
 254 {
 255         g_assert (sgen_section_gray_queue_is_empty (queue));
 256
 257         queue->locked = locked;
 258         if (locked) {
 259                 mono_mutex_init_recursive (&queue->lock);
 260         }
 261
 262 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
 263         queue->enqueue_check_func = enqueue_check_func;
 264 #endif
 265 }
 266
 267 gboolean
 268 sgen_section_gray_queue_is_empty (SgenSectionGrayQueue *queue)
 269 {
 270         return !queue->first;
 271 }
 272
 273 GrayQueueSection*
 274 sgen_section_gray_queue_dequeue (SgenSectionGrayQueue *queue)
 275 {
 276         GrayQueueSection *section;
 277
 278         lock_section_queue (queue);
 279
 280         if (queue->first) {
 281                 section = queue->first;
 282                 queue->first = section->next;
 283
 284                 STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_ENQUEUED, GRAY_QUEUE_SECTION_STATE_FLOATING);
 285
 286                 section->next = NULL;
 287         } else {
 288                 section = NULL;
 289         }
 290
 291         unlock_section_queue (queue);
 292
 293         return section;
 294 }
 295
 296 void
 297 sgen_section_gray_queue_enqueue (SgenSectionGrayQueue *queue, GrayQueueSection *section)
 298 {
 299         STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_FLOATING, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
 300
 301         lock_section_queue (queue);
 302
 303         section->next = queue->first;
 304         queue->first = section;
 305 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
 306         if (queue->enqueue_check_func) {
 307                 int i;
 308                 for (i = 0; i < section->end; ++i)
 309                         queue->enqueue_check_func (section->objects [i]);
 310         }
 311 #endif
 312
 313         unlock_section_queue (queue);
 314 }
 315
 316 #endif