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