mono/metadata/sgen-gray.c

   1 #define GRAY_QUEUE_SECTION_SIZE (128 - 3)
   2 #define GRAY_QUEUE_LENGTH_LIMIT 64
   3
   4 /*
   5  * This is a stack now instead of a queue, so the most recently added items are removed
   6  * first, improving cache locality, and keeping the stack size manageable.
   7  */
   8 typedef struct _GrayQueueSection GrayQueueSection;
   9 struct _GrayQueueSection {
  10         int end;
  11         GrayQueueSection *next, *prev;
  12         char *objects [GRAY_QUEUE_SECTION_SIZE];
  13 };
  14
  15 static GrayQueueSection *gray_queue_start = NULL;
  16 static GrayQueueSection *gray_queue_end = NULL;
  17
  18 static int gray_queue_balance = 0;
  19 static int num_gray_queue_sections = 0;
  20
  21 static void
  22 gray_object_alloc_queue_section (void)
  23 {
  24         GrayQueueSection *section;
  25
  26         /* Use the previously allocated queue sections if possible */
  27         if (!gray_queue_end && gray_queue_start) {
  28                 gray_queue_end = gray_queue_start;
  29                 gray_queue_end->end = 0;
  30                 return;
  31         }
  32         if (gray_queue_end && gray_queue_end->next) {
  33                 gray_queue_end = gray_queue_end->next;
  34                 gray_queue_end->end = 0;
  35                 return;
  36         }
  37
  38         /* Allocate a new section */
  39         section = get_internal_mem (sizeof (GrayQueueSection), INTERNAL_MEM_GRAY_QUEUE);
  40         ++num_gray_queue_sections;
  41
  42         section->end = 0;
  43         section->next = NULL;
  44         section->prev = NULL;
  45
  46         /* Link it with the others */
  47         if (gray_queue_end) {
  48                 gray_queue_end->next = section;
  49                 section->prev = gray_queue_end;
  50         } else {
  51                 g_assert (!gray_queue_start);
  52                 gray_queue_start = section;
  53         }
  54         gray_queue_end = section;
  55 }
  56
  57 static void
  58 gray_object_free_queue_section (GrayQueueSection *section)
  59 {
  60         free_internal_mem (section, INTERNAL_MEM_GRAY_QUEUE);
  61         --num_gray_queue_sections;
  62 }
  63
  64 /*
  65  * The following three functions are called in the inner loops of the collector, so they
  66  * need to be as fast as possible.
  67  */
  68
  69 static inline void
  70 gray_object_enqueue (char *obj)
  71 {
  72         g_assert (obj);
  73         if (G_UNLIKELY (!gray_queue_end || gray_queue_end->end == GRAY_QUEUE_SECTION_SIZE))
  74                 gray_object_alloc_queue_section ();
  75         g_assert (gray_queue_end && gray_queue_end->end < GRAY_QUEUE_SECTION_SIZE);
  76         gray_queue_end->objects [gray_queue_end->end++] = obj;
  77
  78         ++gray_queue_balance;
  79 }
  80
  81 static inline gboolean
  82 gray_object_queue_is_empty (void)
  83 {
  84         return gray_queue_end == NULL;
  85 }
  86
  87 static inline char*
  88 gray_object_dequeue (void)
  89 {
  90         char *obj;
  91
  92         if (gray_object_queue_is_empty ())
  93                 return NULL;
  94
  95         g_assert (gray_queue_end->end);
  96
  97         obj = gray_queue_end->objects [--gray_queue_end->end];
  98
  99         if (G_UNLIKELY (gray_queue_end->end == 0))
 100                 gray_queue_end = gray_queue_end->prev;
 101
 102         --gray_queue_balance;
 103
 104         return obj;
 105 }
 106
 107 static void
 108 gray_object_queue_init (void)
 109 {
 110         GrayQueueSection *section, *next;
 111         int i;
 112
 113         g_assert (gray_object_queue_is_empty ());
 114         g_assert (sizeof (GrayQueueSection) < MAX_FREELIST_SIZE);
 115         g_assert (gray_queue_balance == 0);
 116
 117         /* Free the extra sections allocated during the last collection */
 118         i = 0;
 119         for (section = gray_queue_start; section && i < GRAY_QUEUE_LENGTH_LIMIT; section = section->next)
 120                 i ++;
 121         if (section) {
 122                 if (section->prev)
 123                         section->prev->next = NULL;
 124                 for (; section; section = next) {
 125                         next = section->next;
 126                         gray_object_free_queue_section (section);
 127                 }
 128         }
 129 }