mono/sgen/sgen-gray.h

   1 /**
   2  * \file
   3  * Gray queue management.
   4  *
   5  * Copyright 2011 Xamarin Inc (http://www.xamarin.com)
   6  * Copyright (C) 2012 Xamarin Inc
   7  *
   8  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
   9  */
  10 #ifndef __MONO_SGEN_GRAY_H__
  11 #define __MONO_SGEN_GRAY_H__
  12
  13 #include "mono/sgen/sgen-protocol.h"
  14
  15 /*
  16  * This gray queue has to be as optimized as possible, because it is in the core of
  17  * the mark/copy phase of the garbage collector. The memory access has then to be as
  18  * cache friendly as possible. That's why we use a cursor based implementation.
  19  *
  20  * This simply consist in maintaining a pointer to the current element in the
  21  * queue. In addition to using this cursor, we use a simple linked list of arrays,
  22  * called sections, so that we have the cache friendliness of arrays without having
  23  * the cost of memory reallocation of a dynaic array, not the cost of memory
  24  * indirection of a linked list.
  25  *
  26  * This implementation also allows the dequeuing of a whole section at a time. This is
  27  * for example used in the parallel GC because it would be too costly to take one element
  28  * at a time. This imply the main constraint that, because we don't carry the cursor
  29  * with the section, we still have to store the index of the last element. This is done
  30  * through the 'size' field on the section, which default value is it's maximum value
  31  * SGEN_GRAY_QUEUE_SECTION_SIZE. This field is updated in multiple cases :
  32  *  - section allocation : default value
  33  *  - object push : default value if we fill the current queue first
  34  *  - section dequeue : position of the cursor in the dequeued section
  35  *  - section enqueue : position of the cursor in the previously first section in the queue
  36  *
  37  * The previous implementation was an index based access where we would store the index
  38  * of the last element in the section. This was less efficient because we would have
  39  * to make 1 memory access for the index value, 1 for the base address of the objects
  40  * array and another 1 for the actual value in the array.
  41  */
  42
  43 /* SGEN_GRAY_QUEUE_HEADER_SIZE is number of machine words */
  44 #ifdef SGEN_CHECK_GRAY_OBJECT_SECTIONS
  45 #define SGEN_GRAY_QUEUE_HEADER_SIZE     5
  46 #else
  47 #define SGEN_GRAY_QUEUE_HEADER_SIZE     3
  48 #endif
  49
  50 #define SGEN_GRAY_QUEUE_SECTION_SIZE    (512 - SGEN_GRAY_QUEUE_HEADER_SIZE)
  51
  52 #ifdef SGEN_CHECK_GRAY_OBJECT_SECTIONS
  53 typedef enum {
  54         GRAY_QUEUE_SECTION_STATE_FLOATING,
  55         GRAY_QUEUE_SECTION_STATE_ENQUEUED,
  56         GRAY_QUEUE_SECTION_STATE_FREE_LIST,
  57         GRAY_QUEUE_SECTION_STATE_FREED
  58 } GrayQueueSectionState;
  59 #endif
  60
  61 typedef struct _GrayQueueEntry GrayQueueEntry;
  62 struct _GrayQueueEntry {
  63         GCObject *obj;
  64         SgenDescriptor desc;
  65 };
  66
  67 #define SGEN_GRAY_QUEUE_ENTRY(obj,desc) { (obj), (desc) }
  68
  69 #define GRAY_OBJECT_ENQUEUE_SERIAL(queue, obj, desc) (GRAY_OBJECT_ENQUEUE (queue, obj, desc, FALSE))
  70 #define GRAY_OBJECT_ENQUEUE_PARALLEL(queue, obj, desc) (GRAY_OBJECT_ENQUEUE (queue, obj, desc, TRUE))
  71 #define GRAY_OBJECT_DEQUEUE_SERIAL(queue, obj, desc) (GRAY_OBJECT_DEQUEUE (queue, obj, desc, FALSE))
  72 #define GRAY_OBJECT_DEQUEUE_PARALLEL(queue, obj, desc) (GRAY_OBJECT_DEQUEUE (queue, obj, desc, TRUE))
  73
  74 /*
  75  * This is a stack now instead of a queue, so the most recently added items are removed
  76  * first, improving cache locality, and keeping the stack size manageable.
  77  */
  78 typedef struct _GrayQueueSection GrayQueueSection;
  79 struct _GrayQueueSection {
  80 #ifdef SGEN_CHECK_GRAY_OBJECT_SECTIONS
  81         /*
  82          * The dummy is here so that the state doesn't get overwritten
  83          * by the internal allocator once the section is freed.
  84          */
  85         int dummy;
  86         GrayQueueSectionState state;
  87 #endif
  88         int size;
  89         GrayQueueSection *next, *prev;
  90         GrayQueueEntry entries [SGEN_GRAY_QUEUE_SECTION_SIZE];
  91 };
  92
  93 typedef struct _SgenGrayQueue SgenGrayQueue;
  94
  95 typedef void (*GrayQueueAllocPrepareFunc) (SgenGrayQueue*);
  96 typedef void (*GrayQueueEnqueueCheckFunc) (GCObject*);
  97
  98 struct _SgenGrayQueue {
  99         GrayQueueEntry *cursor;
 100         GrayQueueSection *first, *last;
 101         GrayQueueSection *free_list;
 102         mono_mutex_t steal_mutex;
 103         gint32 num_sections;
 104 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
 105         GrayQueueEnqueueCheckFunc enqueue_check_func;
 106 #endif
 107 };
 108
 109 typedef struct _SgenSectionGrayQueue SgenSectionGrayQueue;
 110
 111 struct _SgenSectionGrayQueue {
 112         GrayQueueSection *first;
 113         gboolean locked;
 114         mono_mutex_t lock;
 115 #ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
 116         GrayQueueEnqueueCheckFunc enqueue_check_func;
 117 #endif
 118 };
 119
 120 #define GRAY_LAST_CURSOR_POSITION(s) ((s)->entries + SGEN_GRAY_QUEUE_SECTION_SIZE - 1)
 121 #define GRAY_FIRST_CURSOR_POSITION(s) ((s)->entries)
 122
 123 #ifdef HEAVY_STATISTICS
 124 extern guint64 stat_gray_queue_section_alloc;
 125 extern guint64 stat_gray_queue_section_free;
 126 extern guint64 stat_gray_queue_enqueue_fast_path;
 127 extern guint64 stat_gray_queue_dequeue_fast_path;
 128 extern guint64 stat_gray_queue_enqueue_slow_path;
 129 extern guint64 stat_gray_queue_dequeue_slow_path;
 130 #endif
 131
 132 void sgen_init_gray_queues (void);
 133
 134 void sgen_gray_object_enqueue (SgenGrayQueue *queue, GCObject *obj, SgenDescriptor desc, gboolean is_parallel);
 135 GrayQueueEntry sgen_gray_object_dequeue (SgenGrayQueue *queue, gboolean is_parallel);
 136 GrayQueueSection* sgen_gray_object_dequeue_section (SgenGrayQueue *queue);
 137 GrayQueueSection* sgen_gray_object_steal_section (SgenGrayQueue *queue);
 138 void sgen_gray_object_spread (SgenGrayQueue *queue, int num_sections);
 139 void sgen_gray_object_enqueue_section (SgenGrayQueue *queue, GrayQueueSection *section, gboolean is_parallel);
 140 void sgen_gray_object_queue_trim_free_list (SgenGrayQueue *queue);
 141 void sgen_gray_object_queue_init (SgenGrayQueue *queue, GrayQueueEnqueueCheckFunc enqueue_check_func, gboolean reuse_free_list);
 142 void sgen_gray_object_queue_dispose (SgenGrayQueue *queue);
 143 void sgen_gray_object_queue_deinit (SgenGrayQueue *queue);
 144 void sgen_gray_object_alloc_queue_section (SgenGrayQueue *queue, gboolean is_parallel);
 145 void sgen_gray_object_free_queue_section (GrayQueueSection *section);
 146
 147 void sgen_section_gray_queue_init (SgenSectionGrayQueue *queue, gboolean locked,
 148                 GrayQueueEnqueueCheckFunc enqueue_check_func);
 149 gboolean sgen_section_gray_queue_is_empty (SgenSectionGrayQueue *queue);
 150 GrayQueueSection* sgen_section_gray_queue_dequeue (SgenSectionGrayQueue *queue);
 151 void sgen_section_gray_queue_enqueue (SgenSectionGrayQueue *queue, GrayQueueSection *section);
 152
 153 gboolean sgen_gray_object_fill_prefetch (SgenGrayQueue *queue);
 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, GCObject *obj, SgenDescriptor desc, gboolean is_parallel)
 163 {
 164 #if SGEN_MAX_DEBUG_LEVEL >= 9
 165         sgen_gray_object_enqueue (queue, obj, desc, is_parallel);
 166 #else
 167         if (G_UNLIKELY (!queue->first || queue->cursor == GRAY_LAST_CURSOR_POSITION (queue->first))) {
 168                 sgen_gray_object_enqueue (queue, obj, desc, is_parallel);
 169         } else {
 170                 GrayQueueEntry entry = SGEN_GRAY_QUEUE_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                 sgen_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, GCObject** obj, SgenDescriptor *desc, gboolean is_parallel)
 184 {
 185         GrayQueueEntry entry;
 186 #if SGEN_MAX_DEBUG_LEVEL >= 9
 187         entry = sgen_gray_object_dequeue (queue, is_parallel);
 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         } else if (G_UNLIKELY (queue->cursor == GRAY_FIRST_CURSOR_POSITION (queue->first))) {
 196                 entry = sgen_gray_object_dequeue (queue, is_parallel);
 197                 *obj = entry.obj;
 198                 *desc = entry.desc;
 199         } else {
 200                 HEAVY_STAT (stat_gray_queue_dequeue_fast_path ++);
 201
 202                 entry = *queue->cursor--;
 203                 *obj = entry.obj;
 204                 *desc = entry.desc;
 205 #ifdef SGEN_HEAVY_BINARY_PROTOCOL
 206                 sgen_binary_protocol_gray_dequeue (queue, queue->cursor + 1, *obj);
 207 #endif
 208         }
 209 #endif
 210 }
 211
 212 #endif