mono/metadata/sgen-gray.c

   1 /*
   2  * Copyright 2001-2003 Ximian, Inc
   3  * Copyright 2003-2010 Novell, Inc.
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining
   6  * a copy of this software and associated documentation files (the
   7  * "Software"), to deal in the Software without restriction, including
   8  * without limitation the rights to use, copy, modify, merge, publish,
   9  * distribute, sublicense, and/or sell copies of the Software, and to
  10  * permit persons to whom the Software is furnished to do so, subject to
  11  * the following conditions:
  12  *
  13  * The above copyright notice and this permission notice shall be
  14  * included in all copies or substantial portions of the Software.
  15  *
  16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  17  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  18  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  19  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  20  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  21  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  22  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  23  */
  24 #define GRAY_QUEUE_LENGTH_LIMIT 64
  25
  26 static GrayQueue gray_queue;
  27
  28 static void
  29 gray_object_alloc_queue_section (GrayQueue *queue)
  30 {
  31         GrayQueueSection *section;
  32
  33         if (queue->alloc_prepare_func)
  34                 queue->alloc_prepare_func (queue);
  35
  36         if (queue->free_list) {
  37                 /* Use the previously allocated queue sections if possible */
  38                 section = queue->free_list;
  39                 queue->free_list = section->next;
  40         } else {
  41                 /* Allocate a new section */
  42                 section = mono_sgen_alloc_internal_fixed (queue->allocator, INTERNAL_MEM_GRAY_QUEUE);
  43         }
  44
  45         section->end = 0;
  46
  47         /* Link it with the others */
  48         section->next = queue->first;
  49         queue->first = section;
  50 }
  51
  52 static void
  53 gray_object_free_queue_section (GrayQueueSection *section, SgenInternalAllocator *thread_allocator)
  54 {
  55         mono_sgen_free_internal_delayed (section, INTERNAL_MEM_GRAY_QUEUE, thread_allocator);
  56 }
  57
  58 static inline gboolean
  59 gray_object_queue_is_empty (GrayQueue *queue)
  60 {
  61         return queue->first == NULL;
  62 }
  63
  64 /*
  65  * The following two functions are called in the inner loops of the
  66  * collector, so they need to be as fast as possible.  We have macros
  67  * for them in sgen-gc.h.
  68  */
  69
  70 void
  71 mono_sgen_gray_object_enqueue (GrayQueue *queue, char *obj)
  72 {
  73         DEBUG (9, g_assert (obj));
  74         if (G_UNLIKELY (!queue->first || queue->first->end == SGEN_GRAY_QUEUE_SECTION_SIZE))
  75                 gray_object_alloc_queue_section (queue);
  76         DEBUG (9, g_assert (queue->first && queue->first->end < SGEN_GRAY_QUEUE_SECTION_SIZE));
  77         queue->first->objects [queue->first->end++] = obj;
  78
  79         DEBUG (9, ++queue->balance);
  80 }
  81
  82 char*
  83 mono_sgen_gray_object_dequeue (GrayQueue *queue)
  84 {
  85         char *obj;
  86
  87         if (gray_object_queue_is_empty (queue))
  88                 return NULL;
  89
  90         DEBUG (9, g_assert (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         DEBUG (9, --queue->balance);
 102
 103         return obj;
 104 }
 105
 106 static GrayQueueSection*
 107 gray_object_dequeue_section (GrayQueue *queue)
 108 {
 109         GrayQueueSection *section;
 110
 111         if (!queue->first)
 112                 return NULL;
 113
 114         section = queue->first;
 115         queue->first = section->next;
 116
 117         section->next = NULL;
 118
 119         return section;
 120 }
 121
 122 static void
 123 gray_object_enqueue_section (GrayQueue *queue, GrayQueueSection *section)
 124 {
 125         section->next = queue->first;
 126         queue->first = section;
 127 }
 128
 129 static void
 130 gray_object_queue_init (GrayQueue *queue, SgenInternalAllocator *allocator)
 131 {
 132         GrayQueueSection *section, *next;
 133         int i;
 134
 135         g_assert (gray_object_queue_is_empty (queue));
 136         DEBUG (9, g_assert (queue->balance == 0));
 137
 138         queue->allocator = allocator;
 139
 140         /* Free the extra sections allocated during the last collection */
 141         i = 0;
 142         for (section = queue->free_list; section && i < GRAY_QUEUE_LENGTH_LIMIT - 1; section = section->next)
 143                 i ++;
 144         if (!section)
 145                 return;
 146         while (section->next) {
 147                 next = section->next;
 148                 section->next = next->next;
 149                 gray_object_free_queue_section (next, allocator);
 150         }
 151 }
 152
 153 static void
 154 gray_object_queue_init_with_alloc_prepare (GrayQueue *queue, SgenInternalAllocator *allocator, GrayQueueAllocPrepareFunc func, void *data)
 155 {
 156         gray_object_queue_init (queue, allocator);
 157         queue->alloc_prepare_func = func;
 158         queue->alloc_prepare_data = data;
 159 }