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;
  35         char *objects [GRAY_QUEUE_SECTION_SIZE];
  36 };
  37
  38 struct _GrayQueue {
  39         GrayQueueSection *first;
  40         GrayQueueSection *free_list;
  41         int balance;
  42 };
  43
  44 static GrayQueue gray_queue;
  45
  46 static void
  47 gray_object_alloc_queue_section (GrayQueue *queue)
  48 {
  49         GrayQueueSection *section;
  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         } else {
  56                 /* Allocate a new section */
  57                 section = mono_sgen_alloc_internal (INTERNAL_MEM_GRAY_QUEUE);
  58         }
  59
  60         section->end = 0;
  61
  62         /* Link it with the others */
  63         section->next = queue->first;
  64         queue->first = section;
  65 }
  66
  67 static void
  68 gray_object_free_queue_section (GrayQueueSection *section)
  69 {
  70         mono_sgen_free_internal (section, INTERNAL_MEM_GRAY_QUEUE);
  71 }
  72
  73 static inline gboolean
  74 gray_object_queue_is_empty (GrayQueue *queue)
  75 {
  76         return queue->first == NULL;
  77 }
  78
  79 /*
  80  * The following two functions are called in the inner loops of the
  81  * collector, so they need to be as fast as possible.  We have macros
  82  * for them below.
  83  */
  84
  85 static inline void
  86 gray_object_enqueue (GrayQueue *queue, char *obj)
  87 {
  88         DEBUG (9, g_assert (obj));
  89         if (G_UNLIKELY (!queue->first || queue->first->end == GRAY_QUEUE_SECTION_SIZE))
  90                 gray_object_alloc_queue_section (queue);
  91         DEBUG (9, g_assert (queue->first && queue->first->end < GRAY_QUEUE_SECTION_SIZE));
  92         queue->first->objects [queue->first->end++] = obj;
  93
  94         DEBUG (9, ++queue->balance);
  95 }
  96
  97 static inline char*
  98 gray_object_dequeue (GrayQueue *queue)
  99 {
 100         char *obj;
 101
 102         if (gray_object_queue_is_empty (queue))
 103                 return NULL;
 104
 105         DEBUG (9, g_assert (queue->first->end));
 106
 107         obj = queue->first->objects [--queue->first->end];
 108
 109         if (G_UNLIKELY (queue->first->end == 0)) {
 110                 GrayQueueSection *section = queue->first;
 111                 queue->first = section->next;
 112                 section->next = queue->free_list;
 113                 queue->free_list = section;
 114         }
 115
 116         DEBUG (9, --queue->balance);
 117
 118         return obj;
 119 }
 120
 121 #if MAX_DEBUG_LEVEL >= 9
 122 #define GRAY_OBJECT_ENQUEUE gray_object_enqueue
 123 #define GRAY_OBJECT_DEQUEUE(queue,o) ((o) = gray_object_dequeue ((queue)))
 124 #else
 125 #define GRAY_OBJECT_ENQUEUE(queue,o) do {                               \
 126                 if (G_UNLIKELY (!(queue)->first || (queue)->first->end == GRAY_QUEUE_SECTION_SIZE)) \
 127                         gray_object_alloc_queue_section ((queue));      \
 128                 (queue)->first->objects [(queue)->first->end++] = (o);  \
 129         } while (0)
 130 #define GRAY_OBJECT_DEQUEUE(queue,o) do {                               \
 131                 if (!(queue)->first)                                    \
 132                         (o) = NULL;                                     \
 133                 else if (G_UNLIKELY ((queue)->first->end == 1))         \
 134                         (o) = gray_object_dequeue ((queue));            \
 135                 else                                                    \
 136                         (o) = (queue)->first->objects [--(queue)->first->end]; \
 137         } while (0)
 138 #endif
 139
 140 static void
 141 gray_object_queue_init (GrayQueue *queue)
 142 {
 143         GrayQueueSection *section, *next;
 144         int i;
 145
 146         g_assert (gray_object_queue_is_empty (queue));
 147         DEBUG (9, g_assert (queue->balance == 0));
 148
 149         /* Free the extra sections allocated during the last collection */
 150         i = 0;
 151         for (section = queue->free_list; section && i < GRAY_QUEUE_LENGTH_LIMIT - 1; section = section->next)
 152                 i ++;
 153         if (!section)
 154                 return;
 155         while (section->next) {
 156                 next = section->next;
 157                 section->next = next->next;
 158                 gray_object_free_queue_section (next);
 159         }
 160 }