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