-/*
- * sgen-gray.c: Gray queue management.
+/**
+ * \file
+ * Gray queue management.
*
* Copyright 2001-2003 Ximian, Inc
* Copyright 2003-2010 Novell, Inc.
static GrayQueueSection *last_gray_queue_free_list;
void
-sgen_gray_object_alloc_queue_section (SgenGrayQueue *queue)
+sgen_gray_object_alloc_queue_section (SgenGrayQueue *queue, gboolean is_parallel)
{
GrayQueueSection *section;
queue->first = section;
queue->cursor = section->entries - 1;
- mono_memory_write_barrier ();
- /*
- * FIXME
- * we could probably optimize the code to only rely on the write barrier
- * for synchronization with the stealer thread. Additionally we could also
- * do a write barrier once every other gray queue change, and request
- * to have a minimum of sections before stealing, to keep consistency.
- */
- InterlockedIncrement (&queue->num_sections);
+ if (is_parallel) {
+ mono_memory_write_barrier ();
+ /*
+ * FIXME
+ * we could probably optimize the code to only rely on the write barrier
+ * for synchronization with the stealer thread. Additionally we could also
+ * do a write barrier once every other gray queue change, and request
+ * to have a minimum of sections before stealing, to keep consistency.
+ */
+ InterlockedIncrement (&queue->num_sections);
+ } else {
+ queue->num_sections++;
+ }
}
void
*/
void
-sgen_gray_object_enqueue (SgenGrayQueue *queue, GCObject *obj, SgenDescriptor desc)
+sgen_gray_object_enqueue (SgenGrayQueue *queue, GCObject *obj, SgenDescriptor desc, gboolean is_parallel)
{
GrayQueueEntry entry = SGEN_GRAY_QUEUE_ENTRY (obj, desc);
queue->first->size = SGEN_GRAY_QUEUE_SECTION_SIZE;
}
- sgen_gray_object_alloc_queue_section (queue);
+ sgen_gray_object_alloc_queue_section (queue, is_parallel);
}
STATE_ASSERT (queue->first, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
SGEN_ASSERT (9, queue->cursor <= GRAY_LAST_CURSOR_POSITION (queue->first), "gray queue %p overflow, first %p, cursor %p", queue, queue->first, queue->cursor);
#endif
}
+/*
+ * We attempt to spread the objects in the gray queue across a number
+ * of sections. If the queue has more sections, then it's already spread,
+ * if it doesn't have enough sections, then we allocate as many as we
+ * can.
+ */
+void
+sgen_gray_object_spread (SgenGrayQueue *queue, int num_sections)
+{
+ GrayQueueSection *section_start, *section_end;
+ int total_entries = 0, num_entries_per_section;
+ int num_sections_final;
+
+ if (queue->num_sections >= num_sections)
+ return;
+
+ if (!queue->first)
+ return;
+
+ /* Compute number of elements in the gray queue */
+ queue->first->size = queue->cursor - queue->first->entries + 1;
+ total_entries = queue->first->size;
+ for (section_start = queue->first->next; section_start != NULL; section_start = section_start->next) {
+ SGEN_ASSERT (0, section_start->size == SGEN_GRAY_QUEUE_SECTION_SIZE, "We expect all section aside from the first one to be full");
+ total_entries += section_start->size;
+ }
+
+ /* Compute how many sections we should have and elements per section */
+ num_sections_final = (total_entries > num_sections) ? num_sections : total_entries;
+ num_entries_per_section = total_entries / num_sections_final;
+
+ /* Allocate all needed sections */
+ while (queue->num_sections < num_sections_final)
+ sgen_gray_object_alloc_queue_section (queue, TRUE);
+
+ /* Spread out the elements in the sections. By design, sections at the end are fuller. */
+ section_start = queue->first;
+ section_end = queue->last;
+ while (section_start != section_end) {
+ /* We move entries from end to start, until they meet */
+ while (section_start->size < num_entries_per_section) {
+ GrayQueueEntry entry;
+ if (section_end->size <= num_entries_per_section) {
+ section_end = section_end->prev;
+ if (section_end == section_start)
+ break;
+ }
+ if (section_end->size <= num_entries_per_section)
+ break;
+
+ section_end->size--;
+ entry = section_end->entries [section_end->size];
+ section_start->entries [section_start->size] = entry;
+ section_start->size++;
+ }
+ section_start = section_start->next;
+ }
+
+ queue->cursor = queue->first->entries + queue->first->size - 1;
+ queue->num_sections = num_sections_final;
+}
+
GrayQueueEntry
-sgen_gray_object_dequeue (SgenGrayQueue *queue)
+sgen_gray_object_dequeue (SgenGrayQueue *queue, gboolean is_parallel)
{
GrayQueueEntry entry;
if (G_UNLIKELY (queue->cursor < GRAY_FIRST_CURSOR_POSITION (queue->first))) {
GrayQueueSection *section;
- gint32 old_num_sections;
+ gint32 old_num_sections = 0;
- old_num_sections = InterlockedDecrement (&queue->num_sections);
+ if (is_parallel)
+ old_num_sections = InterlockedDecrement (&queue->num_sections);
+ else
+ queue->num_sections--;
- if (old_num_sections <= 0) {
+ if (is_parallel && old_num_sections <= 0) {
mono_os_mutex_lock (&queue->steal_mutex);
}
queue->free_list = section;
queue->cursor = queue->first ? queue->first->entries + queue->first->size - 1 : NULL;
- if (old_num_sections <= 0) {
+ if (is_parallel && old_num_sections <= 0) {
mono_os_mutex_unlock (&queue->steal_mutex);
}
}
}
void
-sgen_gray_object_enqueue_section (SgenGrayQueue *queue, GrayQueueSection *section)
+sgen_gray_object_enqueue_section (SgenGrayQueue *queue, GrayQueueSection *section, gboolean is_parallel)
{
STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_FLOATING, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
queue->enqueue_check_func (section->entries [i].obj);
}
#endif
- mono_memory_write_barrier ();
- InterlockedIncrement (&queue->num_sections);
+ if (is_parallel) {
+ mono_memory_write_barrier ();
+ InterlockedIncrement (&queue->num_sections);
+ } else {
+ queue->num_sections++;
+ }
}
void