/*
+ * sgen-gray.c: Gray queue management.
+ *
* Copyright 2001-2003 Ximian, Inc
* Copyright 2003-2010 Novell, Inc.
- *
- * Permission is hereby granted, free of charge, to any person obtaining
- * a copy of this software and associated documentation files (the
- * "Software"), to deal in the Software without restriction, including
- * without limitation the rights to use, copy, modify, merge, publish,
- * distribute, sublicense, and/or sell copies of the Software, and to
- * permit persons to whom the Software is furnished to do so, subject to
- * the following conditions:
- *
- * The above copyright notice and this permission notice shall be
- * included in all copies or substantial portions of the Software.
- *
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
- * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
- * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
- * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
- * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
- * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
- * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ * Copyright (C) 2012 Xamarin Inc
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License 2.0 as published by the Free Software Foundation;
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License 2.0 along with this library; if not, write to the Free
+ * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
-#define GRAY_QUEUE_SECTION_SIZE (128 - 3)
-#define GRAY_QUEUE_LENGTH_LIMIT 64
+#include "config.h"
+#ifdef HAVE_SGEN_GC
-/*
- * 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 {
- int end;
- GrayQueueSection *next, *prev;
- char *objects [GRAY_QUEUE_SECTION_SIZE];
-};
+#include "metadata/sgen-gc.h"
+#include "utils/mono-counters.h"
+#include "sgen-protocol.h"
-static GrayQueueSection *gray_queue_start = NULL;
-static GrayQueueSection *gray_queue_end = NULL;
+#define GRAY_QUEUE_LENGTH_LIMIT 64
-static int gray_queue_balance = 0;
-static int num_gray_queue_sections = 0;
+#ifdef SGEN_CHECK_GRAY_OBJECT_SECTIONS
+#define STATE_TRANSITION(s,o,n) do { \
+ int __old = (o); \
+ if (InterlockedCompareExchange ((volatile int*)&(s)->state, (n), __old) != __old) \
+ g_assert_not_reached (); \
+ } while (0)
+#define STATE_SET(s,v) (s)->state = (v)
+#define STATE_ASSERT(s,v) g_assert ((s)->state == (v))
+#else
+#define STATE_TRANSITION(s,o,n)
+#define STATE_SET(s,v)
+#define STATE_ASSERT(s,v)
+#endif
-static void
-gray_object_alloc_queue_section (void)
+void
+sgen_gray_object_alloc_queue_section (SgenGrayQueue *queue)
{
GrayQueueSection *section;
- /* Use the previously allocated queue sections if possible */
- if (!gray_queue_end && gray_queue_start) {
- gray_queue_end = gray_queue_start;
- gray_queue_end->end = 0;
- return;
- }
- if (gray_queue_end && gray_queue_end->next) {
- gray_queue_end = gray_queue_end->next;
- gray_queue_end->end = 0;
- return;
+ HEAVY_STAT (gc_stats.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 = sgen_alloc_internal (INTERNAL_MEM_GRAY_QUEUE);
+ STATE_SET (section, GRAY_QUEUE_SECTION_STATE_FLOATING);
}
- /* Allocate a new section */
- section = get_internal_mem (sizeof (GrayQueueSection), INTERNAL_MEM_GRAY_QUEUE);
- ++num_gray_queue_sections;
+ section->size = SGEN_GRAY_QUEUE_SECTION_SIZE;
- section->end = 0;
- section->next = NULL;
- section->prev = NULL;
+ STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_FLOATING, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
/* Link it with the others */
- if (gray_queue_end) {
- gray_queue_end->next = section;
- section->prev = gray_queue_end;
- } else {
- g_assert (!gray_queue_start);
- gray_queue_start = section;
- }
- gray_queue_end = section;
+ section->next = queue->first;
+ queue->first = section;
+ queue->cursor = (char**)section->objects - 1;
}
-static void
-gray_object_free_queue_section (GrayQueueSection *section)
+void
+sgen_gray_object_free_queue_section (GrayQueueSection *section)
{
- free_internal_mem (section, INTERNAL_MEM_GRAY_QUEUE);
- --num_gray_queue_sections;
-}
+ HEAVY_STAT (gc_stats.gray_queue_section_free ++);
-static inline gboolean
-gray_object_queue_is_empty (void)
-{
- return gray_queue_end == NULL;
+ STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_FLOATING, GRAY_QUEUE_SECTION_STATE_FREED);
+ sgen_free_internal (section, INTERNAL_MEM_GRAY_QUEUE);
}
/*
* The following two functions are called in the inner loops of the
* collector, so they need to be as fast as possible. We have macros
- * for them below.
+ * for them in sgen-gc.h.
*/
-static inline void
-gray_object_enqueue (char *obj)
+void
+sgen_gray_object_enqueue (SgenGrayQueue *queue, char *obj)
{
- DEBUG (9, g_assert (obj));
- if (G_UNLIKELY (!gray_queue_end || gray_queue_end->end == GRAY_QUEUE_SECTION_SIZE))
- gray_object_alloc_queue_section ();
- DEBUG (9, g_assert (gray_queue_end && gray_queue_end->end < GRAY_QUEUE_SECTION_SIZE));
- gray_queue_end->objects [gray_queue_end->end++] = obj;
+ HEAVY_STAT (gc_stats.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
- DEBUG (9, ++gray_queue_balance);
+ 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 = obj;
+
+#ifdef SGEN_HEAVY_BINARY_PROTOCOL
+ binary_protocol_gray_enqueue (queue, queue->cursor, obj);
+#endif
}
-static inline char*
-gray_object_dequeue (void)
+char*
+sgen_gray_object_dequeue (SgenGrayQueue *queue)
{
char *obj;
- if (gray_object_queue_is_empty ())
+ HEAVY_STAT (gc_stats.gray_queue_dequeue_slow_path ++);
+
+ if (sgen_gray_object_queue_is_empty (queue))
return NULL;
- DEBUG (9, g_assert (gray_queue_end->end));
+ STATE_ASSERT (queue->first, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
+ SGEN_ASSERT (9, queue->cursor >= (char**)queue->first->objects, "gray queue %p underflow, first %p, cursor %d", queue, queue->first, queue->cursor);
+
+ obj = *queue->cursor--;
- obj = gray_queue_end->objects [--gray_queue_end->end];
+#ifdef SGEN_HEAVY_BINARY_PROTOCOL
+ binary_protocol_gray_dequeue (queue, queue->cursor + 1, obj);
+#endif
+
+ if (G_UNLIKELY (queue->cursor == (char**)queue->first->objects - 1)) {
+ GrayQueueSection *section = queue->first;
+ queue->first = section->next;
+ section->next = queue->free_list;
- if (G_UNLIKELY (gray_queue_end->end == 0))
- gray_queue_end = gray_queue_end->prev;
+ STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_ENQUEUED, GRAY_QUEUE_SECTION_STATE_FREE_LIST);
- DEBUG (9, --gray_queue_balance);
+ queue->free_list = section;
+ queue->cursor = queue->first ? (char**)queue->first->objects + queue->first->size - 1 : NULL;
+ }
return obj;
}
-#if MAX_DEBUG_LEVEL >= 9
-#define GRAY_OBJECT_ENQUEUE gray_object_enqueue
-#define GRAY_OBJECT_DEQUEUE(o) ((o) = gray_object_dequeue ())
-#else
-#define GRAY_OBJECT_ENQUEUE(o) do { \
- if (G_UNLIKELY (!gray_queue_end || gray_queue_end->end == GRAY_QUEUE_SECTION_SIZE)) \
- gray_object_alloc_queue_section (); \
- gray_queue_end->objects [gray_queue_end->end++] = (o); \
- } while (0)
-#define GRAY_OBJECT_DEQUEUE(o) do { \
- if (!gray_queue_end) { \
- (o) = NULL; \
- } else { \
- (o) = gray_queue_end->objects [--gray_queue_end->end]; \
- if (G_UNLIKELY (gray_queue_end->end == 0)) \
- gray_queue_end = gray_queue_end->prev; \
- } \
- } while (0)
+GrayQueueSection*
+sgen_gray_object_dequeue_section (SgenGrayQueue *queue)
+{
+ GrayQueueSection *section;
+
+ if (!queue->first)
+ return NULL;
+
+ section = queue->first;
+ queue->first = section->next;
+
+ section->next = NULL;
+ section->size = queue->cursor - (char**)section->objects + 1;
+
+ queue->cursor = queue->first ? (char**)queue->first->objects + queue->first->size - 1 : NULL;
+
+ STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_ENQUEUED, GRAY_QUEUE_SECTION_STATE_FLOATING);
+
+ return section;
+}
+
+void
+sgen_gray_object_enqueue_section (SgenGrayQueue *queue, GrayQueueSection *section)
+{
+ STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_FLOATING, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
+
+ if (queue->first)
+ queue->first->size = queue->cursor - (char**)queue->first->objects + 1;
+
+ section->next = queue->first;
+ queue->first = section;
+ queue->cursor = (char**)queue->first->objects + queue->first->size - 1;
+#ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
+ if (queue->enqueue_check_func) {
+ int i;
+ for (i = 0; i < section->size; ++i)
+ queue->enqueue_check_func (section->objects [i]);
+ }
#endif
+}
-static void
-gray_object_queue_init (void)
+void
+sgen_gray_object_queue_init (SgenGrayQueue *queue, GrayQueueEnqueueCheckFunc enqueue_check_func)
{
GrayQueueSection *section, *next;
int i;
- g_assert (gray_object_queue_is_empty ());
- g_assert (sizeof (GrayQueueSection) < MAX_FREELIST_SIZE);
- DEBUG (9, g_assert (gray_queue_balance == 0));
+ g_assert (sgen_gray_object_queue_is_empty (queue));
+
+ queue->alloc_prepare_func = NULL;
+ queue->alloc_prepare_data = NULL;
+#ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
+ queue->enqueue_check_func = enqueue_check_func;
+#endif
/* Free the extra sections allocated during the last collection */
i = 0;
- for (section = gray_queue_start; section && i < GRAY_QUEUE_LENGTH_LIMIT; section = section->next)
+ for (section = queue->free_list; section && i < GRAY_QUEUE_LENGTH_LIMIT - 1; section = section->next) {
+ STATE_ASSERT (section, GRAY_QUEUE_SECTION_STATE_FREE_LIST);
i ++;
- if (section) {
- if (section->prev)
- section->prev->next = NULL;
- for (; section; section = next) {
- next = section->next;
- gray_object_free_queue_section (section);
- }
}
+ if (!section)
+ return;
+ while (section->next) {
+ next = section->next;
+ section->next = next->next;
+ STATE_TRANSITION (next, GRAY_QUEUE_SECTION_STATE_FREE_LIST, GRAY_QUEUE_SECTION_STATE_FLOATING);
+ sgen_gray_object_free_queue_section (next);
+ }
+}
+
+static void
+invalid_prepare_func (SgenGrayQueue *queue)
+{
+ g_assert_not_reached ();
+}
+
+void
+sgen_gray_object_queue_init_invalid (SgenGrayQueue *queue)
+{
+ sgen_gray_object_queue_init (queue, FALSE);
+ queue->alloc_prepare_func = invalid_prepare_func;
+ queue->alloc_prepare_data = NULL;
+}
+
+void
+sgen_gray_object_queue_init_with_alloc_prepare (SgenGrayQueue *queue, GrayQueueEnqueueCheckFunc enqueue_check_func,
+ GrayQueueAllocPrepareFunc alloc_prepare_func, void *data)
+{
+ sgen_gray_object_queue_init (queue, enqueue_check_func);
+ queue->alloc_prepare_func = alloc_prepare_func;
+ queue->alloc_prepare_data = data;
+}
+
+void
+sgen_gray_object_queue_deinit (SgenGrayQueue *queue)
+{
+ g_assert (!queue->first);
+ while (queue->free_list) {
+ GrayQueueSection *next = queue->free_list->next;
+ STATE_TRANSITION (queue->free_list, GRAY_QUEUE_SECTION_STATE_FREE_LIST, GRAY_QUEUE_SECTION_STATE_FLOATING);
+ sgen_gray_object_free_queue_section (queue->free_list);
+ queue->free_list = next;
+ }
+}
+
+void
+sgen_gray_object_queue_disable_alloc_prepare (SgenGrayQueue *queue)
+{
+ queue->alloc_prepare_func = NULL;
+ queue->alloc_prepare_data = NULL;
+}
+
+static void
+lock_section_queue (SgenSectionGrayQueue *queue)
+{
+ if (!queue->locked)
+ return;
+
+ mono_mutex_lock (&queue->lock);
+}
+
+static void
+unlock_section_queue (SgenSectionGrayQueue *queue)
+{
+ if (!queue->locked)
+ return;
+
+ mono_mutex_unlock (&queue->lock);
+}
+
+void
+sgen_section_gray_queue_init (SgenSectionGrayQueue *queue, gboolean locked, GrayQueueEnqueueCheckFunc enqueue_check_func)
+{
+ g_assert (sgen_section_gray_queue_is_empty (queue));
+
+ queue->locked = locked;
+ if (locked) {
+ mono_mutex_init_recursive (&queue->lock);
+ }
+
+#ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
+ queue->enqueue_check_func = enqueue_check_func;
+#endif
+}
+
+gboolean
+sgen_section_gray_queue_is_empty (SgenSectionGrayQueue *queue)
+{
+ return !queue->first;
+}
+
+GrayQueueSection*
+sgen_section_gray_queue_dequeue (SgenSectionGrayQueue *queue)
+{
+ GrayQueueSection *section;
+
+ lock_section_queue (queue);
+
+ if (queue->first) {
+ section = queue->first;
+ queue->first = section->next;
+
+ STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_ENQUEUED, GRAY_QUEUE_SECTION_STATE_FLOATING);
+
+ section->next = NULL;
+ } else {
+ section = NULL;
+ }
+
+ unlock_section_queue (queue);
+
+ return section;
}
+
+void
+sgen_section_gray_queue_enqueue (SgenSectionGrayQueue *queue, GrayQueueSection *section)
+{
+ STATE_TRANSITION (section, GRAY_QUEUE_SECTION_STATE_FLOATING, GRAY_QUEUE_SECTION_STATE_ENQUEUED);
+
+ lock_section_queue (queue);
+
+ section->next = queue->first;
+ queue->first = section;
+#ifdef SGEN_CHECK_GRAY_OBJECT_ENQUEUE
+ if (queue->enqueue_check_func) {
+ int i;
+ for (i = 0; i < section->size; ++i)
+ queue->enqueue_check_func (section->objects [i]);
+ }
+#endif
+
+ unlock_section_queue (queue);
+}
+
+#endif
projects / mono.git / blobdiff