mono/metadata/sgen-gray.h

   1 /*
   2  * sgen-gray.h: Gray queue management.
   3  *
   4  * Copyright 2011 Xamarin Inc (http://www.xamarin.com)
   5  * Copyright (C) 2012 Xamarin Inc
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Library General Public
   9  * License 2.0 as published by the Free Software Foundation;
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Library General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Library General Public
  17  * License 2.0 along with this library; if not, write to the Free
  18  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19  */
  20 #ifndef __MONO_SGEN_GRAY_H__
  21 #define __MONO_SGEN_GRAY_H__
  22
  23 /*
  24  * This gray queue has to be as optimized as possible, because it is in the core of
  25  * the mark/copy phase of the garbage collector. The memory access has then to be as
  26  * cache friendly as possible. That's why we use a cursor based implementation.
  27  *
  28  * This simply consist in maintaining a pointer to the current element in the
  29  * queue. In addition to using this cursor, we use a simple linked list of arrays,
  30  * called sections, so that we have the cache friendliness of arrays without having
  31  * the cost of memory reallocation of a dynaic array, not the cost of memory
  32  * indirection of a linked list.
  33  *
  34  * This implementation also allows the dequeuing of a whole section at a time. This is
  35  * for example used in the parallel GC because it would be too costly to take one element
  36  * at a time. This imply the main constraint that, because we don't carry the cursor
  37  * with the section, we still have to store the index of the last element. This is done
  38  * through the 'size' field on the section, which default value is it's maximum value
  39  * SGEN_GRAY_QUEUE_SECTION_SIZE. This field is updated in multiple cases :
  40  *  - section allocation : default value
  41  *  - object push : default value if we fill the current queue first
  42  *  - section dequeue : position of the cursor in the dequeued section
  43  *  - section enqueue : position of the cursor in the previously first section in the queue
  44  *
  45  * The previous implementation was an index based access where we would store the index
  46  * of the last element in the section. This was less efficient because we would have
  47  * to make 1 memory access for the index value, 1 for the base address of the objects
  48  * array and another 1 for the actual value in the array.
  49  */
  50
  51 /* SGEN_GRAY_QUEUE_HEADER_SIZE is number of machine words */
  52 #ifdef SGEN_CHECK_GRAY_OBJECT_SECTIONS
  53 #define SGEN_GRAY_QUEUE_HEADER_SIZE     4
  54 #else
  55 #define SGEN_GRAY_QUEUE_HEADER_SIZE     2
  56 #endif
  57
  58 #define SGEN_GRAY_QUEUE_SECTION_SIZE    (128 - SGEN_GRAY_QUEUE_HEADER_SIZE)
  59
  60 #ifdef SGEN_CHECK_GRAY_OBJECT_SECTIONS
  61 typedef enum {
  62         GRAY_QUEUE_SECTION_STATE_FLOATING,
  63         GRAY_QUEUE_SECTION_STATE_ENQUEUED,
  64         GRAY_QUEUE_SECTION_STATE_FREE_LIST,
  65         GRAY_QUEUE_SECTION_STATE_FREED
  66 } GrayQueueSectionState;
  67 #endif
  68
  69 typedef struct _GrayQueueEntry GrayQueueEntry;
  70 struct _GrayQueueEntry {
  71         char *obj;
  72         mword desc;
  73 };
  74
  75 /*
  76  * This is a stack now instead of a queue, so the most recently added items are removed
  77  * first, improving cache locality, and keeping the stack size manageable.
  78  */
  79 typedef struct _GrayQueueSection GrayQueueSection;
  80 struct _GrayQueueSection {
  81 #ifdef SGEN_CHECK_GRAY_OBJECT_SECTIONS
  82         /*
  83          * The dummy is here so that the state doesn't get overwritten
  84          * by the internal allocator once the section is freed.
  85          */
  86         int dummy;
  87         GrayQueueSectionState state;
  88 #endif
  89         int size;
  90         GrayQueueSection *next;
  91         GrayQueueEntry entries [SGEN_GRAY_QUEUE_SECTION_SIZE];
  92 };
  93
  94 typedef struct _SgenGrayQueue SgenGrayQueue;
  95
  96 typedef void (*GrayQueueAllocPrepareFunc) (SgenGrayQueue*);
  97 typedef void (*GrayQueueEnqueueCheckFunc) (char*);
  98
  99 struct _SgenGrayQueue {
 100         GrayQueueEntry *cursor;
 101         GrayQueueSection *first;
 102         GrayQueueSection *free_list;
 103         GrayQueueAllocPrepareFunc alloc_prepare_func;
 104 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
 105         GrayQueueEnqueueCheckFunc enqueue_check_func;
 106 #endif
 107         void *alloc_prepare_data;
 108 };
 109
 110 typedef struct _SgenSectionGrayQueue SgenSectionGrayQueue;
 111
 112 struct _SgenSectionGrayQueue {
 113         GrayQueueSection *first;
 114         gboolean locked;
 115         mono_mutex_t lock;
 116 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
 117         GrayQueueEnqueueCheckFunc enqueue_check_func;
 118 #endif
 119 };
 120
 121 #define GRAY_LAST_CURSOR_POSITION(s) ((s)->entries + SGEN_GRAY_QUEUE_SECTION_SIZE - 1)
 122 #define GRAY_FIRST_CURSOR_POSITION(s) ((s)->entries)
 123
 124 #ifdef HEAVY_STATISTICS
 125 extern unsigned long long stat_gray_queue_section_alloc;
 126 extern unsigned long long stat_gray_queue_section_free;
 127 extern unsigned long long stat_gray_queue_enqueue_fast_path;
 128 extern unsigned long long stat_gray_queue_dequeue_fast_path;
 129 extern unsigned long long stat_gray_queue_enqueue_slow_path;
 130 extern unsigned long long stat_gray_queue_dequeue_slow_path;
 131 #endif
 132
 133 void sgen_init_gray_queues (void) MONO_INTERNAL;
 134
 135 void sgen_gray_object_enqueue (SgenGrayQueue *queue, char *obj, mword desc) MONO_INTERNAL;
 136 GrayQueueEntry sgen_gray_object_dequeue (SgenGrayQueue *queue) MONO_INTERNAL;
 137 GrayQueueSection* sgen_gray_object_dequeue_section (SgenGrayQueue *queue) MONO_INTERNAL;
 138 void sgen_gray_object_enqueue_section (SgenGrayQueue *queue, GrayQueueSection *section) MONO_INTERNAL;
 139 void sgen_gray_object_queue_trim_free_list (SgenGrayQueue *queue) MONO_INTERNAL;
 140 void sgen_gray_object_queue_init (SgenGrayQueue *queue, GrayQueueEnqueueCheckFunc enqueue_check_func) MONO_INTERNAL;
 141 void sgen_gray_object_queue_init_invalid (SgenGrayQueue *queue) MONO_INTERNAL;
 142 void sgen_gray_object_queue_init_with_alloc_prepare (SgenGrayQueue *queue, GrayQueueEnqueueCheckFunc enqueue_check_func,
 143                 GrayQueueAllocPrepareFunc func, void *data) MONO_INTERNAL;
 144 void sgen_gray_object_queue_deinit (SgenGrayQueue *queue) MONO_INTERNAL;
 145 void sgen_gray_object_queue_disable_alloc_prepare (SgenGrayQueue *queue) MONO_INTERNAL;
 146 void sgen_gray_object_alloc_queue_section (SgenGrayQueue *queue) MONO_INTERNAL;
 147 void sgen_gray_object_free_queue_section (GrayQueueSection *section) MONO_INTERNAL;
 148
 149 void sgen_section_gray_queue_init (SgenSectionGrayQueue *queue, gboolean locked,
 150                 GrayQueueEnqueueCheckFunc enqueue_check_func) MONO_INTERNAL;
 151 gboolean sgen_section_gray_queue_is_empty (SgenSectionGrayQueue *queue) MONO_INTERNAL;
 152 GrayQueueSection* sgen_section_gray_queue_dequeue (SgenSectionGrayQueue *queue) MONO_INTERNAL;
 153 void sgen_section_gray_queue_enqueue (SgenSectionGrayQueue *queue, GrayQueueSection *section) MONO_INTERNAL;
 154
 155 static inline gboolean
 156 sgen_gray_object_queue_is_empty (SgenGrayQueue *queue)
 157 {
 158         return queue->first == NULL;
 159 }
 160
 161 static inline MONO_ALWAYS_INLINE void
 162 GRAY_OBJECT_ENQUEUE (SgenGrayQueue *queue, char* obj, mword desc)
 163 {
 164 #if SGEN_MAX_DEBUG_LEVEL >= 9
 165         sgen_gray_object_enqueue (queue, obj, desc);
 166 #else
 167         if (G_UNLIKELY (!queue->first || queue->cursor == GRAY_LAST_CURSOR_POSITION (queue->first))) {
 168                 sgen_gray_object_enqueue (queue, obj, desc);
 169         } else {
 170                 GrayQueueEntry entry = { obj, desc };
 171
 172                 HEAVY_STAT (stat_gray_queue_enqueue_fast_path ++);
 173
 174                 *++queue->cursor = entry;
 175 #ifdef SGEN_HEAVY_BINARY_PROTOCOL
 176                 binary_protocol_gray_enqueue (queue, queue->cursor, obj);
 177 #endif
 178         }
 179 #endif
 180 }
 181
 182 static inline MONO_ALWAYS_INLINE void
 183 GRAY_OBJECT_DEQUEUE (SgenGrayQueue *queue, char** obj, mword *desc)
 184 {
 185         GrayQueueEntry entry;
 186 #if SGEN_MAX_DEBUG_LEVEL >= 9
 187         entry = sgen_gray_object_enqueue (queue);
 188         *obj = entry.obj;
 189         *desc = entry.desc;
 190 #else
 191         if (!queue->first) {
 192                 HEAVY_STAT (stat_gray_queue_dequeue_fast_path ++);
 193
 194                 *obj = NULL;
 195 #ifdef SGEN_HEAVY_BINARY_PROTOCOL
 196                 binary_protocol_gray_dequeue (queue, queue->cursor, *obj);
 197 #endif
 198         } else if (G_UNLIKELY (queue->cursor == GRAY_FIRST_CURSOR_POSITION (queue->first))) {
 199                 entry = sgen_gray_object_dequeue (queue);
 200                 *obj = entry.obj;
 201                 *desc = entry.desc;
 202         } else {
 203                 HEAVY_STAT (stat_gray_queue_dequeue_fast_path ++);
 204
 205                 entry = *queue->cursor--;
 206                 *obj = entry.obj;
 207                 *desc = entry.desc;
 208 #ifdef SGEN_HEAVY_BINARY_PROTOCOL
 209                 binary_protocol_gray_dequeue (queue, queue->cursor + 1, *obj);
 210 #endif
 211         }
 212 #endif
 213 }
 214
 215 #endif