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