/**
 * \file
 * Gray queue management.
 *
 * Copyright 2011 Xamarin Inc (http://www.xamarin.com)
 * Copyright (C) 2012 Xamarin Inc
 *
 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
 */
#ifndef __MONO_SGEN_GRAY_H__
#define __MONO_SGEN_GRAY_H__

#include "mono/sgen/sgen-protocol.h"

/*
 * This gray queue has to be as optimized as possible, because it is in the core of
 * the mark/copy phase of the garbage collector. The memory access has then to be as
 * cache friendly as possible. That's why we use a cursor based implementation.
 * 
 * This simply consist in maintaining a pointer to the current element in the
 * queue. In addition to using this cursor, we use a simple linked list of arrays,
 * called sections, so that we have the cache friendliness of arrays without having
 * the cost of memory reallocation of a dynaic array, not the cost of memory
 * indirection of a linked list.
 * 
 * This implementation also allows the dequeuing of a whole section at a time. This is
 * for example used in the parallel GC because it would be too costly to take one element 
 * at a time. This imply the main constraint that, because we don't carry the cursor
 * with the section, we still have to store the index of the last element. This is done 
 * through the 'size' field on the section, which default value is it's maximum value
 * SGEN_GRAY_QUEUE_SECTION_SIZE. This field is updated in multiple cases :
 *  - section allocation : default value
 *  - object push : default value if we fill the current queue first
 *  - section dequeue : position of the cursor in the dequeued section
 *  - section enqueue : position of the cursor in the previously first section in the queue
 * 
 * The previous implementation was an index based access where we would store the index
 * of the last element in the section. This was less efficient because we would have
 * to make 1 memory access for the index value, 1 for the base address of the objects
 * array and another 1 for the actual value in the array.
 */

/* SGEN_GRAY_QUEUE_HEADER_SIZE is number of machine words */
#ifdef SGEN_CHECK_GRAY_OBJECT_SECTIONS
#define SGEN_GRAY_QUEUE_HEADER_SIZE	5
#else
#define SGEN_GRAY_QUEUE_HEADER_SIZE	3
#endif

#define SGEN_GRAY_QUEUE_SECTION_SIZE	(512 - SGEN_GRAY_QUEUE_HEADER_SIZE)

#ifdef SGEN_CHECK_GRAY_OBJECT_SECTIONS
typedef enum {
	GRAY_QUEUE_SECTION_STATE_FLOATING,
	GRAY_QUEUE_SECTION_STATE_ENQUEUED,
 	GRAY_QUEUE_SECTION_STATE_FREE_LIST,
 	GRAY_QUEUE_SECTION_STATE_FREED
} GrayQueueSectionState;
#endif

typedef struct _GrayQueueEntry GrayQueueEntry;
struct _GrayQueueEntry {
	GCObject *obj;
	SgenDescriptor desc;
};

#define SGEN_GRAY_QUEUE_ENTRY(obj,desc)	{ (obj), (desc) }

#define GRAY_OBJECT_ENQUEUE_SERIAL(queue, obj, desc) (GRAY_OBJECT_ENQUEUE (queue, obj, desc, FALSE))
#define GRAY_OBJECT_ENQUEUE_PARALLEL(queue, obj, desc) (GRAY_OBJECT_ENQUEUE (queue, obj, desc, TRUE))
#define GRAY_OBJECT_DEQUEUE_SERIAL(queue, obj, desc) (GRAY_OBJECT_DEQUEUE (queue, obj, desc, FALSE))
#define GRAY_OBJECT_DEQUEUE_PARALLEL(queue, obj, desc) (GRAY_OBJECT_DEQUEUE (queue, obj, desc, TRUE))

/*
 * This is a stack now instead of a queue, so the most recently added items are removed
 * first, improving cache locality, and keeping the stack size manageable.
 */
typedef struct _GrayQueueSection GrayQueueSection;
struct _GrayQueueSection {
#ifdef SGEN_CHECK_GRAY_OBJECT_SECTIONS
	/*
	 * The dummy is here so that the state doesn't get overwritten
	 * by the internal allocator once the section is freed.
	 */
	int dummy;
	GrayQueueSectionState state;
#endif
	int size;
	GrayQueueSection *next, *prev;
	GrayQueueEntry entries [SGEN_GRAY_QUEUE_SECTION_SIZE];
};

typedef struct _SgenGrayQueue SgenGrayQueue;

typedef void (*GrayQueueAllocPrepareFunc) (SgenGrayQueue*);
typedef void (*GrayQueueEnqueueCheckFunc) (GCObject*);

struct _SgenGrayQueue {
	GrayQueueEntry *cursor;
	GrayQueueSection *first, *last;
	GrayQueueSection *free_list;
	mono_mutex_t steal_mutex;
	gint32 num_sections;
#ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
	GrayQueueEnqueueCheckFunc enqueue_check_func;
#endif
};

typedef struct _SgenSectionGrayQueue SgenSectionGrayQueue;

struct _SgenSectionGrayQueue {
	GrayQueueSection *first;
	gboolean locked;
	mono_mutex_t lock;
#ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
	GrayQueueEnqueueCheckFunc enqueue_check_func;
#endif
};

#define GRAY_LAST_CURSOR_POSITION(s) ((s)->entries + SGEN_GRAY_QUEUE_SECTION_SIZE - 1)
#define GRAY_FIRST_CURSOR_POSITION(s) ((s)->entries)

#ifdef HEAVY_STATISTICS
extern guint64 stat_gray_queue_section_alloc;
extern guint64 stat_gray_queue_section_free;
extern guint64 stat_gray_queue_enqueue_fast_path;
extern guint64 stat_gray_queue_dequeue_fast_path;
extern guint64 stat_gray_queue_enqueue_slow_path;
extern guint64 stat_gray_queue_dequeue_slow_path;
#endif

void sgen_init_gray_queues (void);

void sgen_gray_object_enqueue (SgenGrayQueue *queue, GCObject *obj, SgenDescriptor desc, gboolean is_parallel);
GrayQueueEntry sgen_gray_object_dequeue (SgenGrayQueue *queue, gboolean is_parallel);
GrayQueueSection* sgen_gray_object_dequeue_section (SgenGrayQueue *queue);
GrayQueueSection* sgen_gray_object_steal_section (SgenGrayQueue *queue);
void sgen_gray_object_spread (SgenGrayQueue *queue, int num_sections);
void sgen_gray_object_enqueue_section (SgenGrayQueue *queue, GrayQueueSection *section, gboolean is_parallel);
void sgen_gray_object_queue_trim_free_list (SgenGrayQueue *queue);
void sgen_gray_object_queue_init (SgenGrayQueue *queue, GrayQueueEnqueueCheckFunc enqueue_check_func, gboolean reuse_free_list);
void sgen_gray_object_queue_dispose (SgenGrayQueue *queue);
void sgen_gray_object_queue_deinit (SgenGrayQueue *queue);
void sgen_gray_object_alloc_queue_section (SgenGrayQueue *queue, gboolean is_parallel);
void sgen_gray_object_free_queue_section (GrayQueueSection *section);

void sgen_section_gray_queue_init (SgenSectionGrayQueue *queue, gboolean locked,
		GrayQueueEnqueueCheckFunc enqueue_check_func);
gboolean sgen_section_gray_queue_is_empty (SgenSectionGrayQueue *queue);
GrayQueueSection* sgen_section_gray_queue_dequeue (SgenSectionGrayQueue *queue);
void sgen_section_gray_queue_enqueue (SgenSectionGrayQueue *queue, GrayQueueSection *section);

gboolean sgen_gray_object_fill_prefetch (SgenGrayQueue *queue);

static inline gboolean
sgen_gray_object_queue_is_empty (SgenGrayQueue *queue)
{
	return queue->first == NULL;
}

static inline MONO_ALWAYS_INLINE void
GRAY_OBJECT_ENQUEUE (SgenGrayQueue *queue, GCObject *obj, SgenDescriptor desc, gboolean is_parallel)
{
#if SGEN_MAX_DEBUG_LEVEL >= 9
	sgen_gray_object_enqueue (queue, obj, desc, is_parallel);
#else
	if (G_UNLIKELY (!queue->first || queue->cursor == GRAY_LAST_CURSOR_POSITION (queue->first))) {
		sgen_gray_object_enqueue (queue, obj, desc, is_parallel);
	} else {
		GrayQueueEntry entry = SGEN_GRAY_QUEUE_ENTRY (obj, desc);

		HEAVY_STAT (stat_gray_queue_enqueue_fast_path ++);

		*++queue->cursor = entry;
#ifdef SGEN_HEAVY_BINARY_PROTOCOL
		binary_protocol_gray_enqueue (queue, queue->cursor, obj);
#endif
	}
#endif
}

static inline MONO_ALWAYS_INLINE void
GRAY_OBJECT_DEQUEUE (SgenGrayQueue *queue, GCObject** obj, SgenDescriptor *desc, gboolean is_parallel)
{
	GrayQueueEntry entry;
#if SGEN_MAX_DEBUG_LEVEL >= 9
	entry = sgen_gray_object_dequeue (queue, is_parallel);
	*obj = entry.obj;
	*desc = entry.desc;
#else
	if (!queue->first) {
		HEAVY_STAT (stat_gray_queue_dequeue_fast_path ++);

		*obj = NULL;
	} else if (G_UNLIKELY (queue->cursor == GRAY_FIRST_CURSOR_POSITION (queue->first))) {
		entry = sgen_gray_object_dequeue (queue, is_parallel);
		*obj = entry.obj;
		*desc = entry.desc;
	} else {
		HEAVY_STAT (stat_gray_queue_dequeue_fast_path ++);

		entry = *queue->cursor--;
		*obj = entry.obj;
		*desc = entry.desc;
#ifdef SGEN_HEAVY_BINARY_PROTOCOL
		binary_protocol_gray_dequeue (queue, queue->cursor + 1, *obj);
#endif
	}
#endif
}

#endif