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 /*
  88  * The following three functions are called in the inner loops of the collector, so they
  89  * need to be as fast as possible.
  90  */
  91
  92 static inline void
  93 gray_object_enqueue (char *obj)
  94 {
  95         g_assert (obj);
  96         if (G_UNLIKELY (!gray_queue_end || gray_queue_end->end == GRAY_QUEUE_SECTION_SIZE))
  97                 gray_object_alloc_queue_section ();
  98         g_assert (gray_queue_end && gray_queue_end->end < GRAY_QUEUE_SECTION_SIZE);
  99         gray_queue_end->objects [gray_queue_end->end++] = obj;
 100
 101         ++gray_queue_balance;
 102 }
 103
 104 static inline gboolean
 105 gray_object_queue_is_empty (void)
 106 {
 107         return gray_queue_end == NULL;
 108 }
 109
 110 static inline char*
 111 gray_object_dequeue (void)
 112 {
 113         char *obj;
 114
 115         if (gray_object_queue_is_empty ())
 116                 return NULL;
 117
 118         g_assert (gray_queue_end->end);
 119
 120         obj = gray_queue_end->objects [--gray_queue_end->end];
 121
 122         if (G_UNLIKELY (gray_queue_end->end == 0))
 123                 gray_queue_end = gray_queue_end->prev;
 124
 125         --gray_queue_balance;
 126
 127         return obj;
 128 }
 129
 130 static void
 131 gray_object_queue_init (void)
 132 {
 133         GrayQueueSection *section, *next;
 134         int i;
 135
 136         g_assert (gray_object_queue_is_empty ());
 137         g_assert (sizeof (GrayQueueSection) < MAX_FREELIST_SIZE);
 138         g_assert (gray_queue_balance == 0);
 139
 140         /* Free the extra sections allocated during the last collection */
 141         i = 0;
 142         for (section = gray_queue_start; section && i < GRAY_QUEUE_LENGTH_LIMIT; section = section->next)
 143                 i ++;
 144         if (section) {
 145                 if (section->prev)
 146                         section->prev->next = NULL;
 147                 for (; section; section = next) {
 148                         next = section->next;
 149                         gray_object_free_queue_section (section);
 150                 }
 151         }
 152 }