void*
mono_sgen_nursery_alloc (size_t size)
{
	Fragment *frag;
	DEBUG (4, fprintf (gc_debug_file, "Searching nursery for size: %zd\n", size));
	size = SGEN_ALIGN_UP (size);

	HEAVY_STAT (InterlockedIncrement (&stat_nursery_alloc_requests));

#ifdef NALLOC_DEBUG
	InterlockedIncrement (&alloc_count);
#endif

restart:
	for (frag = unmask (nursery_fragments); frag; frag = unmask (frag->next)) {
		HEAVY_STAT (InterlockedIncrement (&stat_alloc_iterations));

		if (size <= (frag->fragment_end - frag->fragment_next)) {
			void *p = alloc_from_fragment (frag, size);
			if (!p) {
				HEAVY_STAT (InterlockedIncrement (&stat_alloc_retries));
				goto restart;
			}
#ifdef NALLOC_DEBUG
			add_alloc_record (p, size, FIXED_ALLOC);
#endif
			return p;
		}
	}
	return NULL;
}

/*
 * size is already rounded up and we hold the GC lock.
 */
static void*
major_alloc_degraded (MonoVTable *vtable, size_t size)
{
	GCMemSection *section;
	void **p = NULL;
	g_assert (size <= SGEN_MAX_SMALL_OBJ_SIZE);
	HEAVY_STAT (++stat_objects_alloced_degraded);
	HEAVY_STAT (stat_bytes_alloced_degraded += size);
	for (section = section_list; section; section = section->block.next) {
		if ((section->end_data - section->next_data) >= size) {
			p = (void**)section->next_data;
			break;
		}
	}
	if (!p) {
		section = alloc_major_section ();
		section->is_to_space = FALSE;
		/* FIXME: handle OOM */
		p = (void**)section->next_data;
		sgen_register_major_sections_alloced (1);
	}
	section->next_data += size;
	DEBUG (3, fprintf (gc_debug_file, "Allocated (degraded) object %p, vtable: %p (%s), size: %zd in section %p\n", p, vtable, vtable->klass->name, size, section));
	*p = vtable;
	return p;
}

void*
sgen_fragment_allocator_par_alloc (SgenFragmentAllocator *allocator, size_t size)
{
	SgenFragment *frag;

#ifdef NALLOC_DEBUG
	InterlockedIncrement (&alloc_count);
#endif

restart:
	for (frag = (SgenFragment *)unmask (allocator->alloc_head); unmask (frag); frag = (SgenFragment *)unmask (frag->next)) {
		HEAVY_STAT (++stat_alloc_iterations);

		if (size <= (size_t)(frag->fragment_end - frag->fragment_next)) {
			void *p = par_alloc_from_fragment (allocator, frag, size);
			if (!p) {
				HEAVY_STAT (++stat_alloc_retries);
				goto restart;
			}
#ifdef NALLOC_DEBUG
			add_alloc_record (p, size, FIXED_ALLOC);
#endif
			return p;
		}
	}
	return NULL;
}

static void
major_copy_or_mark_object (void **ptr, SgenGrayQueue *queue)
{
	void *obj = *ptr;
	MSBlockInfo *block;

	HEAVY_STAT (++stat_copy_object_called_major);

	DEBUG (9, g_assert (obj));
	DEBUG (9, g_assert (current_collection_generation == GENERATION_OLD));

	if (ptr_in_nursery (obj)) {
		int word, bit;
		char *forwarded;

		if ((forwarded = SGEN_OBJECT_IS_FORWARDED (obj))) {
			*ptr = forwarded;
			return;
		}
		if (SGEN_OBJECT_IS_PINNED (obj))
			return;

		HEAVY_STAT (++stat_objects_copied_major);

		obj = copy_object_no_checks (obj, queue);
		*ptr = obj;

		/*
		 * FIXME: See comment for copy_object_no_checks().  If
		 * we have that, we can let the allocation function
		 * give us the block info, too, and we won't have to
		 * re-fetch it.
		 */
		block = MS_BLOCK_FOR_OBJ (obj);
		MS_CALC_MARK_BIT (word, bit, obj);
		DEBUG (9, g_assert (!MS_MARK_BIT (block, word, bit)));
		MS_SET_MARK_BIT (block, word, bit);
	} else {
#ifdef FIXED_HEAP
		if (MS_PTR_IN_SMALL_MAJOR_HEAP (obj))
#else
		mword objsize;

		objsize = SGEN_ALIGN_UP (mono_sgen_safe_object_get_size ((MonoObject*)obj));

		if (objsize <= SGEN_MAX_SMALL_OBJ_SIZE)
#endif
		{
			block = MS_BLOCK_FOR_OBJ (obj);
			MS_MARK_OBJECT_AND_ENQUEUE (obj, block, queue);
		} else {
			if (SGEN_OBJECT_IS_PINNED (obj))
				return;
			binary_protocol_pin (obj, (gpointer)SGEN_LOAD_VTABLE (obj), mono_sgen_safe_object_get_size ((MonoObject*)obj));
			SGEN_PIN_OBJECT (obj);
			/* FIXME: only enqueue if object has references */
			GRAY_OBJECT_ENQUEUE (queue, obj);
		}
	}
}

/*
 * Tries to check if a given remset location was already added to the global remset.
 * It can
 *
 * A 2 entry, LRU cache of recently saw location remsets.
 *
 * It's hand-coded instead of done using loops to reduce the number of memory references on cache hit.
 *
 * Returns TRUE is the element was added..
 */
static gboolean
global_remset_location_was_not_added (gpointer ptr)
{

	gpointer first = global_remset_cache [0], second;
	if (first == ptr) {
		HEAVY_STAT (++stat_global_remsets_discarded);
		return FALSE;
	}

	second = global_remset_cache [1];

	if (second == ptr) {
		/*Move the second to the front*/
		global_remset_cache [0] = second;
		global_remset_cache [1] = first;

		HEAVY_STAT (++stat_global_remsets_discarded);
		return FALSE;
	}

	global_remset_cache [0] = second;
	global_remset_cache [1] = ptr;
	return TRUE;
}

static void
mono_sgen_ssb_wbarrier_generic_nostore (gpointer ptr)
{
	gpointer *buffer;
	int index;
	TLAB_ACCESS_INIT;

	LOCK_GC;

	buffer = STORE_REMSET_BUFFER;
	index = STORE_REMSET_BUFFER_INDEX;
	/* This simple optimization eliminates a sizable portion of
	   entries.  Comparing it to the last but one entry as well
	   doesn't eliminate significantly more entries. */
	if (buffer [index] == ptr) {
		UNLOCK_GC;
		return;
	}

	HEAVY_STAT (++stat_wbarrier_generic_store_remset);

	++index;
	if (index >= STORE_REMSET_BUFFER_SIZE) {
		evacuate_remset_buffer ();
		index = STORE_REMSET_BUFFER_INDEX;
		g_assert (index == 0);
		++index;
	}
	buffer [index] = ptr;
	STORE_REMSET_BUFFER_INDEX = index;

	UNLOCK_GC;
}

void
sgen_gray_object_enqueue (SgenGrayQueue *queue, GCObject *obj, SgenDescriptor desc)
{
	GrayQueueEntry entry = SGEN_GRAY_QUEUE_ENTRY (obj, desc);

	HEAVY_STAT (stat_gray_queue_enqueue_slow_path ++);

	SGEN_ASSERT (9, obj, "enqueueing a null object");
	//sgen_check_objref (obj);

#ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
	if (queue->enqueue_check_func)
		queue->enqueue_check_func (obj);
#endif

	if (G_UNLIKELY (!queue->first || queue->cursor == GRAY_LAST_CURSOR_POSITION (queue->first))) {
		if (queue->first) {
			/* Set the current section size back to default, might have been changed by sgen_gray_object_dequeue_section */
			queue->first->size = SGEN_GRAY_QUEUE_SECTION_SIZE;
		}

		sgen_gray_object_alloc_queue_section (queue);
	}
	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);
	*++queue->cursor = entry;

#ifdef SGEN_HEAVY_BINARY_PROTOCOL
	binary_protocol_gray_enqueue (queue, queue->cursor, obj);
#endif
}

void
sgen_gray_object_alloc_queue_section (SgenGrayQueue *queue)
{
	GrayQueueSection *section;

	HEAVY_STAT (stat_gray_queue_section_alloc ++);

	if (queue->alloc_prepare_func)
		queue->alloc_prepare_func (queue);

	if (queue->free_list) {
		/* Use the previously allocated queue sections if possible */
		section = queue->free_list;
		queue->free_list = section->next;
		STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_FREE_LIST, GRAY_QUEUE_SECTION_STATE_FLOATING);
	} else {
		/* Allocate a new section */
		section = (GrayQueueSection *)sgen_alloc_internal (INTERNAL_MEM_GRAY_QUEUE);
		STATE_SET (section, GRAY_QUEUE_SECTION_STATE_FLOATING);
	}

	section->size = SGEN_GRAY_QUEUE_SECTION_SIZE;

	STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_FLOATING, GRAY_QUEUE_SECTION_STATE_ENQUEUED);

	/* Link it with the others */
	section->next = queue->first;
	queue->first = section;
	queue->cursor = section->entries - 1;
}

GrayQueueEntry
sgen_gray_object_dequeue (SgenGrayQueue *queue)
{
	GrayQueueEntry entry;

	HEAVY_STAT (stat_gray_queue_dequeue_slow_path ++);

	if (sgen_gray_object_queue_is_empty (queue)) {
		entry.obj = NULL;
		return entry;
	}

	STATE_ASSERT (queue->first, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
	SGEN_ASSERT (9, queue->cursor >= GRAY_FIRST_CURSOR_POSITION (queue->first), "gray queue %p underflow", queue);

	entry = *queue->cursor--;

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

	if (G_UNLIKELY (queue->cursor < GRAY_FIRST_CURSOR_POSITION (queue->first))) {
		GrayQueueSection *section = queue->first;
		queue->first = section->next;
		section->next = queue->free_list;

		STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_ENQUEUED, GRAY_QUEUE_SECTION_STATE_FREE_LIST);

		queue->free_list = section;
		queue->cursor = queue->first ? queue->first->entries + queue->first->size - 1 : NULL;
	}

	return entry;
}

void
sgen_gray_object_enqueue (SgenGrayQueue *queue, GCObject *obj, SgenDescriptor desc, gboolean is_parallel)
{
	GrayQueueEntry entry = SGEN_GRAY_QUEUE_ENTRY (obj, desc);

	HEAVY_STAT (stat_gray_queue_enqueue_slow_path ++);

	SGEN_ASSERT (9, obj, "enqueueing a null object");
	//sgen_check_objref (obj);

#ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
	if (queue->enqueue_check_func)
		queue->enqueue_check_func (obj);
#endif

	if (G_UNLIKELY (!queue->first || queue->cursor == GRAY_LAST_CURSOR_POSITION (queue->first))) {
		if (queue->first) {
			/*
			 * We don't actively update the section size with each push/pop. For the first
			 * section we determine the size from the cursor position. For the reset of the
			 * sections we need to have the size set.
			 */
			queue->first->size = SGEN_GRAY_QUEUE_SECTION_SIZE;
		}

		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);
	*++queue->cursor = entry;

#ifdef SGEN_HEAVY_BINARY_PROTOCOL
	binary_protocol_gray_enqueue (queue, queue->cursor, obj);
#endif
}

/*
 * We found a fragment of free memory in the nursery: memzero it and if
 * it is big enough, add it to the list of fragments that can be used for
 * allocation.
 */
static void
add_nursery_frag (size_t frag_size, char* frag_start, char* frag_end)
{
	DEBUG (4, fprintf (gc_debug_file, "Found empty fragment: %p-%p, size: %zd\n", frag_start, frag_end, frag_size));
	binary_protocol_empty (frag_start, frag_size);
	/* Not worth dealing with smaller fragments: need to tune */
	if (frag_size >= SGEN_MAX_NURSERY_WASTE) {
		/* memsetting just the first chunk start is bound to provide better cache locality */
		if (mono_sgen_get_nursery_clear_policy () == CLEAR_AT_GC)
			memset (frag_start, 0, frag_size);

#ifdef NALLOC_DEBUG
		/* XXX convert this into a flight record entry
		printf ("\tfragment [%p %p] size %zd\n", frag_start, frag_end, frag_size);
		*/
#endif
		add_fragment (frag_start, frag_end);
		fragment_total += frag_size;
	} else {
		/* Clear unused fragments, pinning depends on this */
		/*TODO place an int[] here instead of the memset if size justify it*/
		memset (frag_start, 0, frag_size);
		HEAVY_STAT (InterlockedExchangeAdd (&stat_wasted_bytes_small_areas, frag_size));
	}
}

/*
 * We found a fragment of free memory in the nursery: memzero it and if
 * it is big enough, add it to the list of fragments that can be used for
 * allocation.
 */
static void
add_nursery_frag (SgenFragmentAllocator *allocator, size_t frag_size, char* frag_start, char* frag_end)
{
	SGEN_LOG (4, "Found empty fragment: %p-%p, size: %zd", frag_start, frag_end, frag_size);
	binary_protocol_empty (frag_start, frag_size);
	/* Not worth dealing with smaller fragments: need to tune */
	if (frag_size >= SGEN_MAX_NURSERY_WASTE) {
		/* memsetting just the first chunk start is bound to provide better cache locality */
		if (sgen_get_nursery_clear_policy () == CLEAR_AT_GC)
			memset (frag_start, 0, frag_size);
		else if (sgen_get_nursery_clear_policy () == CLEAR_AT_TLAB_CREATION_DEBUG)
			memset (frag_start, 0xff, frag_size);

#ifdef NALLOC_DEBUG
		/* XXX convert this into a flight record entry
		printf ("\tfragment [%p %p] size %zd\n", frag_start, frag_end, frag_size);
		*/
#endif
		sgen_fragment_allocator_add (allocator, frag_start, frag_end);
		fragment_total += frag_size;
	} else {
		/* Clear unused fragments, pinning depends on this */
		sgen_clear_range (frag_start, frag_end);
		HEAVY_STAT (stat_wasted_bytes_small_areas += frag_size);
	}
}

void*
sgen_fragment_allocator_serial_alloc (SgenFragmentAllocator *allocator, size_t size)
{
	SgenFragment *frag;
	SgenFragment **previous;
#ifdef NALLOC_DEBUG
	InterlockedIncrement (&alloc_count);
#endif

	previous = &allocator->alloc_head;

	for (frag = *previous; frag; frag = *previous) {
		char *p = (char *)serial_alloc_from_fragment (previous, frag, size);

		HEAVY_STAT (++stat_alloc_iterations);

		if (p) {
#ifdef NALLOC_DEBUG
			add_alloc_record (p, size, FIXED_ALLOC);
#endif
			return p;
		}
		previous = &frag->next;
	}
	return NULL;
}

void
sgen_gray_object_free_queue_section (GrayQueueSection *section)
{
	HEAVY_STAT (stat_gray_queue_section_free ++);

	STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_FLOATING, GRAY_QUEUE_SECTION_STATE_FREED);
	sgen_free_internal (section, INTERNAL_MEM_GRAY_QUEUE);
}

void*
sgen_nursery_alloc_range (size_t desired_size, size_t minimum_size, size_t *out_alloc_size)
{
	SGEN_LOG (4, "Searching for byte range desired size: %zd minimum size %zd", desired_size, minimum_size);

	HEAVY_STAT (++stat_nursery_alloc_range_requests);

	return sgen_fragment_allocator_par_range_alloc (&mutator_allocator, desired_size, minimum_size, out_alloc_size);
}

GrayQueueEntry
sgen_gray_object_dequeue (SgenGrayQueue *queue, gboolean is_parallel)
{
	GrayQueueEntry entry;

	HEAVY_STAT (stat_gray_queue_dequeue_slow_path ++);

	if (sgen_gray_object_queue_is_empty (queue)) {
		entry.obj = NULL;
		return entry;
	}

	STATE_ASSERT (queue->first, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
	SGEN_ASSERT (9, queue->cursor >= GRAY_FIRST_CURSOR_POSITION (queue->first), "gray queue %p underflow", queue);

	entry = *queue->cursor--;

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

	if (G_UNLIKELY (queue->cursor < GRAY_FIRST_CURSOR_POSITION (queue->first))) {
		GrayQueueSection *section;
		gint32 old_num_sections = 0;

		if (is_parallel)
			old_num_sections = mono_atomic_dec_i32 (&queue->num_sections);
		else
			queue->num_sections--;

		if (is_parallel && old_num_sections <= 0) {
			mono_os_mutex_lock (&queue->steal_mutex);
		}

		section = queue->first;
		queue->first = section->next;
		if (queue->first) {
			queue->first->prev = NULL;
		} else {
			queue->last = NULL;
			SGEN_ASSERT (0, !old_num_sections, "Why do we have an inconsistent number of sections ?");
		}
		section->next = queue->free_list;

		STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_ENQUEUED, GRAY_QUEUE_SECTION_STATE_FREE_LIST);

		queue->free_list = section;
		queue->cursor = queue->first ? queue->first->entries + queue->first->size - 1 : NULL;

		if (is_parallel && old_num_sections <= 0) {
			mono_os_mutex_unlock (&queue->steal_mutex);
		}
	}

	return entry;
}

void*
sgen_nursery_alloc (size_t size)
{
	SGEN_ASSERT (1, size >= sizeof (MonoObject) && size <= SGEN_MAX_SMALL_OBJ_SIZE, "Invalid nursery object size");

	SGEN_LOG (4, "Searching nursery for size: %zd", size);
	size = SGEN_ALIGN_UP (size);

	HEAVY_STAT (InterlockedIncrement (&stat_nursery_alloc_requests));

	return sgen_fragment_allocator_par_alloc (&mutator_allocator, size);
}

void*
sgen_nursery_alloc (size_t size)
{
	SGEN_ASSERT (1, size >= (SGEN_CLIENT_MINIMUM_OBJECT_SIZE + CANARY_SIZE) && size <= (SGEN_MAX_SMALL_OBJ_SIZE + CANARY_SIZE), "Invalid nursery object size");

	SGEN_LOG (4, "Searching nursery for size: %zd", size);
	size = SGEN_ALIGN_UP (size);

	HEAVY_STAT (++stat_nursery_alloc_requests);

	return sgen_fragment_allocator_par_alloc (&mutator_allocator, size);
}

void*
sgen_fragment_allocator_serial_range_alloc (SgenFragmentAllocator *allocator, size_t desired_size, size_t minimum_size, size_t *out_alloc_size)
{
	SgenFragment *frag, **previous, *min_frag = NULL, **prev_min_frag = NULL;
	size_t current_minimum = minimum_size;

#ifdef NALLOC_DEBUG
	InterlockedIncrement (&alloc_count);
#endif

	previous = &allocator->alloc_head;

	for (frag = *previous; frag; frag = *previous) {
		size_t frag_size = frag->fragment_end - frag->fragment_next;

		HEAVY_STAT (++stat_alloc_range_iterations);

		if (desired_size <= frag_size) {
			void *p;
			*out_alloc_size = desired_size;

			p = serial_alloc_from_fragment (previous, frag, desired_size);
#ifdef NALLOC_DEBUG
			add_alloc_record (p, desired_size, RANGE_ALLOC);
#endif
			return p;
		}
		if (current_minimum <= frag_size) {
			min_frag = frag;
			prev_min_frag = previous;
			current_minimum = frag_size;
		}
		previous = &frag->next;
	}

	if (min_frag) {
		void *p;
		size_t frag_size = min_frag->fragment_end - min_frag->fragment_next;
		*out_alloc_size = frag_size;

		p = serial_alloc_from_fragment (prev_min_frag, min_frag, frag_size);

#ifdef NALLOC_DEBUG
		add_alloc_record (p, frag_size, RANGE_ALLOC);
#endif
		return p;
	}

	return NULL;
}

void
sgen_gray_object_alloc_queue_section (SgenGrayQueue *queue, gboolean is_parallel)
{
	GrayQueueSection *section;

	if (queue->free_list) {
		/* Use the previously allocated queue sections if possible */
		section = queue->free_list;
		queue->free_list = section->next;
		STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_FREE_LIST, GRAY_QUEUE_SECTION_STATE_FLOATING);
	} else {
		HEAVY_STAT (stat_gray_queue_section_alloc ++);

		/* Allocate a new section */
		section = (GrayQueueSection *)sgen_alloc_internal (INTERNAL_MEM_GRAY_QUEUE);
		STATE_SET (section, GRAY_QUEUE_SECTION_STATE_FLOATING);
	}

	/* Section is empty */
	section->size = 0;

	STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_FLOATING, GRAY_QUEUE_SECTION_STATE_ENQUEUED);

	/* Link it with the others */
	section->next = queue->first;
	section->prev = NULL;
	if (queue->first)
		queue->first->prev = section;
	else
		queue->last = section;
	queue->first = section;
	queue->cursor = section->entries - 1;

	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.
		 */
		mono_atomic_inc_i32 (&queue->num_sections);
	} else {
		queue->num_sections++;
	}
}