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_SECTION_SIZE (128 - 3)
  25 #define GRAY_QUEUE_LENGTH_LIMIT 64
  26
  27 /*
  28  * This is a stack now instead of a queue, so the most recently added items are removed
  29  * first, improving cache locality, and keeping the stack size manageable.
  30  */
  31 typedef struct _GrayQueueSection GrayQueueSection;
  32 struct _GrayQueueSection {
  33         int end;
  34         GrayQueueSection *next, *prev;
  35         char *objects [GRAY_QUEUE_SECTION_SIZE];
  36 };
  37
  38 static GrayQueueSection *gray_queue_start = NULL;
  39 static GrayQueueSection *gray_queue_end = NULL;
  40
  41 static int gray_queue_balance = 0;
  42 static int num_gray_queue_sections = 0;
  43
  44 static void
  45 gray_object_alloc_queue_section (void)
  46 {
  47         GrayQueueSection *section;
  48
  49         /* Use the previously allocated queue sections if possible */
  50         if (!gray_queue_end && gray_queue_start) {
  51                 gray_queue_end = gray_queue_start;
  52                 gray_queue_end->end = 0;
  53                 return;
  54         }
  55         if (gray_queue_end && gray_queue_end->next) {
  56                 gray_queue_end = gray_queue_end->next;
  57                 gray_queue_end->end = 0;
  58                 return;
  59         }
  60
  61         /* Allocate a new section */
  62         section = get_internal_mem (sizeof (GrayQueueSection), INTERNAL_MEM_GRAY_QUEUE);
  63         ++num_gray_queue_sections;
  64
  65         section->end = 0;
  66         section->next = NULL;
  67         section->prev = NULL;
  68
  69         /* Link it with the others */
  70         if (gray_queue_end) {
  71                 gray_queue_end->next = section;
  72                 section->prev = gray_queue_end;
  73         } else {
  74                 g_assert (!gray_queue_start);
  75                 gray_queue_start = section;
  76         }
  77         gray_queue_end = section;
  78 }
  79
  80 static void
  81 gray_object_free_queue_section (GrayQueueSection *section)
  82 {
  83         free_internal_mem (section, INTERNAL_MEM_GRAY_QUEUE);
  84         --num_gray_queue_sections;
  85 }
  86
  87 static inline gboolean
  88 gray_object_queue_is_empty (void)
  89 {
  90         return gray_queue_end == NULL;
  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 below.
  97  */
  98
  99 static inline void
 100 gray_object_enqueue (char *obj)
 101 {
 102         DEBUG (9, g_assert (obj));
 103         if (G_UNLIKELY (!gray_queue_end || gray_queue_end->end == GRAY_QUEUE_SECTION_SIZE))
 104                 gray_object_alloc_queue_section ();
 105         DEBUG (9, g_assert (gray_queue_end && gray_queue_end->end < GRAY_QUEUE_SECTION_SIZE));
 106         gray_queue_end->objects [gray_queue_end->end++] = obj;
 107
 108         DEBUG (9, ++gray_queue_balance);
 109 }
 110
 111 static inline char*
 112 gray_object_dequeue (void)
 113 {
 114         char *obj;
 115
 116         if (gray_object_queue_is_empty ())
 117                 return NULL;
 118
 119         DEBUG (9, g_assert (gray_queue_end->end));
 120
 121         obj = gray_queue_end->objects [--gray_queue_end->end];
 122
 123         if (G_UNLIKELY (gray_queue_end->end == 0))
 124                 gray_queue_end = gray_queue_end->prev;
 125
 126         DEBUG (9, --gray_queue_balance);
 127
 128         return obj;
 129 }
 130
 131 #if MAX_DEBUG_LEVEL >= 9
 132 #define GRAY_OBJECT_ENQUEUE gray_object_enqueue
 133 #define GRAY_OBJECT_DEQUEUE(o) ((o) = gray_object_dequeue ())
 134 #else
 135 #define GRAY_OBJECT_ENQUEUE(o) do {                                     \
 136                 if (G_UNLIKELY (!gray_queue_end || gray_queue_end->end == GRAY_QUEUE_SECTION_SIZE)) \
 137                         gray_object_alloc_queue_section ();             \
 138                 gray_queue_end->objects [gray_queue_end->end++] = (o);  \
 139         } while (0)
 140 #define GRAY_OBJECT_DEQUEUE(o) do {                                     \
 141                 if (!gray_queue_end) {                                  \
 142                         (o) = NULL;                                     \
 143                 } else {                                                \
 144                         (o) = gray_queue_end->objects [--gray_queue_end->end]; \
 145                         if (G_UNLIKELY (gray_queue_end->end == 0))      \
 146                                 gray_queue_end = gray_queue_end->prev;  \
 147                 }                                                       \
 148         } while (0)
 149 #endif
 150
 151 static void
 152 gray_object_queue_init (void)
 153 {
 154         GrayQueueSection *section, *next;
 155         int i;
 156
 157         g_assert (gray_object_queue_is_empty ());
 158         g_assert (sizeof (GrayQueueSection) < MAX_FREELIST_SIZE);
 159         DEBUG (9, g_assert (gray_queue_balance == 0));
 160
 161         /* Free the extra sections allocated during the last collection */
 162         i = 0;
 163         for (section = gray_queue_start; section && i < GRAY_QUEUE_LENGTH_LIMIT; section = section->next)
 164                 i ++;
 165         if (section) {
 166                 if (section->prev)
 167                         section->prev->next = NULL;
 168                 for (; section; section = next) {
 169                         next = section->next;
 170                         gray_object_free_queue_section (section);
 171                 }
 172         }
 173 }