Merge pull request #43 from Unity-Technologies/unity-master-precise-array-scanning

Add vector marking helper routine. Refactor vector support to separat…

5 files changed, 280 insertions, 94 deletions

diff --git a/extra/gc.c b/extra/gc.c
index ec5b5249..9a394dca 100644
--- a/extra/gc.c
+++ b/extra/gc.c
@@ -64,6 +64,7 @@
 
 /* Unity specific includes */
 #include "../heapsections.c"
+#include "../vector_mlc.c"
 
 /* Most platform-specific files go here... */
 #include "../darwin_stop_world.c"
diff --git a/gcj_mlc.c b/gcj_mlc.c
index 0090d1b4..7e5f42e1 100644
--- a/gcj_mlc.c
+++ b/gcj_mlc.c
@@ -46,24 +46,13 @@
 #endif
 GC_bool GC_gcj_malloc_initialized = FALSE;
 
-#ifdef GC_ASSERTIONS
-  GC_INNER /* variable is also used in thread_local_alloc.c */
-#else
-  STATIC
-#endif
-GC_bool GC_gcj_vector_initialized = FALSE;
-
 int GC_gcj_kind = 0;    /* Object kind for objects with descriptors     */
                         /* in "vtable".                                 */
 int GC_gcj_debug_kind = 0;
                         /* The kind of objects that is always marked    */
                         /* with a mark proc call.                       */
 
-int GC_gcj_vector_kind = 0;    /* Object kind for objects with descriptors     */
-            /* in "vtable".                                 */
-
 GC_INNER ptr_t * GC_gcjobjfreelist = NULL;
-GC_INNER ptr_t * GC_gcjvecfreelist = NULL;
 
 STATIC struct GC_ms_entry * GC_gcj_fake_mark_proc(word * addr GC_ATTR_UNUSED,
                         struct GC_ms_entry *mark_stack_ptr,
@@ -132,36 +121,6 @@ GC_API void GC_CALL GC_init_gcj_malloc(int mp_index,
     UNLOCK();
 }
 
-/* Caller does not hold allocation lock. */
-GC_API void GC_CALL GC_init_gcj_vector (int mp_index,
-  void * /* really GC_mark_proc */mp)
-{
-  DCL_LOCK_STATE;
-
-  if (mp == 0)        /* In case GC_DS_PROC is unused.        */
-    ABORT ("GC_init_gcj_vector: bad index");
-
-  GC_init ();  /* In case it's not already done.       */
-  LOCK ();
-  if (GC_gcj_vector_initialized) {
-    UNLOCK ();
-    return;
-  }
-  GC_gcj_vector_initialized = TRUE;
-
-  GC_ASSERT (GC_mark_procs[mp_index] == (GC_mark_proc)0); /* unused */
-  GC_mark_procs[mp_index ] = (GC_mark_proc)(word)mp;
-  if ((unsigned)mp_index >= GC_n_mark_procs)
-    ABORT ("GC_init_gcj_vector: bad index");
-  GC_gcjvecfreelist = (ptr_t *)GC_new_free_list_inner ();
-  GC_gcj_vector_kind = GC_new_kind_inner ((void **)GC_gcjvecfreelist,
-    GC_MAKE_PROC (mp_index,
-      0),
-    FALSE, TRUE);
-
-  UNLOCK ();
-}
-
 #define GENERAL_MALLOC_INNER(lb,k) \
     GC_clear_stack(GC_generic_malloc_inner(lb, k))
 
@@ -239,53 +198,6 @@ static void maybe_finalize(void)
     return((void *) op);
 }
 
-#ifdef THREAD_LOCAL_ALLOC
-#error No THREAD_LOCAL_ALLOC support for GC_gcj_vector_malloc
-#else
-  GC_API GC_ATTR_MALLOC void * GC_CALL GC_gcj_vector_malloc (size_t lb,
-    void * ptr_to_struct_containing_descr)
-#endif
-  {
-    ptr_t op;
-    DCL_LOCK_STATE;
-
-    GC_DBG_COLLECT_AT_MALLOC (lb);
-    if (SMALL_OBJ (lb)) {
-      word lg;
-
-      LOCK ();
-      lg = GC_size_map[lb];
-      op = GC_gcjvecfreelist[lg];
-      if (EXPECT (0 == op, FALSE)) {
-        maybe_finalize ();
-        op = (ptr_t)GENERAL_MALLOC_INNER ((word)lb, GC_gcj_vector_kind);
-        if (0 == op) {
-          GC_oom_func oom_fn = GC_oom_fn;
-          UNLOCK ();
-          return((*oom_fn)(lb));
-        }
-      }
-      else {
-        GC_gcjvecfreelist[lg] = (ptr_t)obj_link (op);
-        GC_bytes_allocd += GRANULES_TO_BYTES ((word)lg);
-      }
-      GC_ASSERT (((void **)op)[1] == 0);
-    }
-    else {
-      LOCK ();
-      maybe_finalize ();
-      op = (ptr_t)GENERAL_MALLOC_INNER ((word)lb, GC_gcj_vector_kind);
-      if (0 == op) {
-        GC_oom_func oom_fn = GC_oom_fn;
-        UNLOCK ();
-        return((*oom_fn)(lb));
-      }
-    }
-    *(void **)op = ptr_to_struct_containing_descr;
-    UNLOCK ();
-    GC_dirty (op);
-    return((void *)op);
-  }
 #endif
 
 /* Similar to GC_gcj_malloc, but add debug info.  This is allocated     */
diff --git a/include/gc_gcj.h b/include/gc_gcj.h
index deca0fee..476db221 100644
--- a/include/gc_gcj.h
+++ b/include/gc_gcj.h
@@ -68,8 +68,6 @@
 /* (GC_GCJ_RESERVED_MARK_PROC_INDEX in gc_mark.h) is an obvious choice. */
 GC_API void GC_CALL GC_init_gcj_malloc(int /* mp_index */,
                                 void * /* really mark_proc */ /* mp */);
-GC_API void GC_CALL GC_init_gcj_vector (int /* mp_index */,
-	void * /* really mark_proc */ /* mp */);
 
 /* Allocate an object, clear it, and store the pointer to the   */
 /* type structure (vtable in gcj).                              */
@@ -91,10 +89,6 @@ GC_API GC_ATTR_MALLOC GC_ATTR_ALLOC_SIZE(1) void * GC_CALL
         GC_gcj_malloc_ignore_off_page(size_t /* lb */,
                                 void * /* ptr_to_struct_containing_descr */);
 
-GC_API GC_ATTR_MALLOC void * GC_CALL
-        GC_gcj_vector_malloc(size_t /* lb */,
-                      void * /* ptr_to_struct_containing_descr */);
-
 /* The kind numbers of normal and debug gcj objects.            */
 /* Useful only for debug support, we hope.                      */
 GC_API int GC_gcj_kind;
diff --git a/include/gc_vector.h b/include/gc_vector.h
new file mode 100644
index 00000000..e0a6cb44
--- /dev/null
+++ b/include/gc_vector.h
@@ -0,0 +1,65 @@
+/*
+ * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
+ * Copyright (c) 1991-1995 by Xerox Corporation.  All rights reserved.
+ * Copyright 1996-1999 by Silicon Graphics.  All rights reserved.
+ * Copyright 1999 by Hewlett-Packard Company.  All rights reserved.
+ *
+ * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
+ * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
+ *
+ * Permission is hereby granted to use or copy this program
+ * for any purpose,  provided the above notices are retained on all copies.
+ * Permission to modify the code and to distribute modified code is granted,
+ * provided the above notices are retained, and a notice that the code was
+ * modified is included with the above copyright notice.
+ */
+
+/* This file assumes the collector has been compiled with GC_GCJ_SUPPORT. */
+
+/*
+ * We allocate objects whose first word contains a pointer to a struct
+ * describing the object type.  This struct contains a garbage collector mark
+ * descriptor at offset MARK_DESCR_OFFSET.  Alternatively, the objects
+ * may be marked by the mark procedure passed to GC_init_gcj_malloc.
+ */
+
+#ifndef GC_VECTOR_H
+#define GC_VECTOR_H
+
+        /* Gcj keeps GC descriptor as second word of vtable.    This    */
+        /* probably needs to be adjusted for other clients.             */
+        /* We currently assume that this offset is such that:           */
+        /*      - all objects of this kind are large enough to have     */
+        /*        a value at that offset, and                           */
+        /*      - it is not zero.                                       */
+        /* These assumptions allow objects on the free list to be       */
+        /* marked normally.                                             */
+
+#ifndef GC_H
+# include "gc.h"
+#endif
+
+# include "gc_typed.h"
+
+#ifdef __cplusplus
+  extern "C" {
+#endif
+
+GC_API void GC_CALL GC_init_gcj_vector (int /* mp_index */,
+  void * /* really mark_proc */ /* mp */);
+
+GC_API GC_ATTR_MALLOC void * GC_CALL GC_gcj_vector_malloc(size_t /* lb */,
+  void * /* ptr_to_struct_containing_descr */);
+
+GC_API struct GC_ms_entry *GC_CALL
+GC_gcj_vector_mark_proc (struct GC_ms_entry *mark_stack_ptr,
+  GC_descr element_desc,
+  GC_word*start,
+  GC_word*end,
+  int words_per_element);
+
+#ifdef __cplusplus
+  } /* extern "C" */
+#endif
+
+#endif /* GC_VECTOR_H */
diff --git a/vector_mlc.c b/vector_mlc.c
new file mode 100644
index 00000000..0aab55d2
--- /dev/null
+++ b/vector_mlc.c
@@ -0,0 +1,214 @@
+/*
+ * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
+ * Copyright (c) 1999-2004 Hewlett-Packard Development Company, L.P.
+ *
+ * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
+ * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
+ *
+ * Permission is hereby granted to use or copy this program
+ * for any purpose,  provided the above notices are retained on all copies.
+ * Permission to modify the code and to distribute modified code is granted,
+ * provided the above notices are retained, and a notice that the code was
+ * modified is included with the above copyright notice.
+ *
+ */
+
+#include "private/gc_pmark.h"  /* includes gc_priv.h */
+
+#ifdef GC_GCJ_SUPPORT
+
+/*
+ * This is an allocator interface tuned for gcj (the GNU static
+ * java compiler).
+ *
+ * Each allocated object has a pointer in its first word to a vtable,
+ * which for our purposes is simply a structure describing the type of
+ * the object.
+ * This descriptor structure contains a GC marking descriptor at offset
+ * MARK_DESCR_OFFSET.
+ *
+ * It is hoped that this interface may also be useful for other systems,
+ * possibly with some tuning of the constants.  But the immediate goal
+ * is to get better gcj performance.
+ *
+ * We assume:
+ *  1) Counting on explicit initialization of this interface is OK;
+ *  2) FASTLOCK is not a significant win.
+ */
+
+#include "gc_vector.h"
+#include "private/dbg_mlc.h"
+#include "gc_typed.h"
+
+#ifdef GC_ASSERTIONS
+  GC_INNER /* variable is also used in thread_local_alloc.c */
+#else
+  STATIC
+#endif
+GC_bool GC_gcj_vector_initialized = FALSE;
+
+int GC_gcj_vector_kind = 0;    /* Object kind for objects with descriptors     */
+            /* in "vtable".                                 */
+
+int GC_gcj_vector_mp_index = 0;
+
+GC_INNER ptr_t * GC_gcjvecfreelist = NULL;
+
+/* Caller does not hold allocation lock. */
+GC_API void GC_CALL GC_init_gcj_vector (int mp_index,
+  void * /* really GC_mark_proc */mp)
+{
+  DCL_LOCK_STATE;
+
+  if (mp == 0)        /* In case GC_DS_PROC is unused.        */
+    ABORT ("GC_init_gcj_vector: bad index");
+
+  GC_init ();  /* In case it's not already done.       */
+  LOCK ();
+  if (GC_gcj_vector_initialized) {
+    UNLOCK ();
+    return;
+  }
+  GC_gcj_vector_initialized = TRUE;
+  GC_gcj_vector_mp_index = mp_index;
+  GC_ASSERT (GC_mark_procs[mp_index] == (GC_mark_proc)0); /* unused */
+  GC_mark_procs[mp_index ] = (GC_mark_proc)(word)mp;
+  if ((unsigned)mp_index >= GC_n_mark_procs)
+    ABORT ("GC_init_gcj_vector: bad index");
+  GC_gcjvecfreelist = (ptr_t *)GC_new_free_list_inner ();
+  GC_gcj_vector_kind = GC_new_kind_inner ((void **)GC_gcjvecfreelist,
+    GC_MAKE_PROC (mp_index,
+      0),
+    FALSE, TRUE);
+
+  UNLOCK ();
+}
+
+#define GENERAL_MALLOC_INNER(lb,k) \
+    GC_clear_stack(GC_generic_malloc_inner(lb, k))
+
+#define GENERAL_MALLOC_INNER_IOP(lb,k) \
+    GC_clear_stack(GC_generic_malloc_inner_ignore_off_page(lb, k))
+
+#if !IL2CPP_ENABLE_WRITE_BARRIER_VALIDATION
+#ifdef THREAD_LOCAL_ALLOC
+#error No THREAD_LOCAL_ALLOC support for GC_gcj_vector_malloc
+#else
+  GC_API GC_ATTR_MALLOC void * GC_CALL GC_gcj_vector_malloc (size_t lb,
+    void * ptr_to_struct_containing_descr)
+#endif
+  {
+    ptr_t op;
+    DCL_LOCK_STATE;
+
+    GC_DBG_COLLECT_AT_MALLOC (lb);
+    if (SMALL_OBJ (lb)) {
+      word lg;
+
+      LOCK ();
+      lg = GC_size_map[lb];
+      op = GC_gcjvecfreelist[lg];
+      if (EXPECT (0 == op, FALSE)) {
+        maybe_finalize ();
+        op = (ptr_t)GENERAL_MALLOC_INNER ((word)lb, GC_gcj_vector_kind);
+        if (0 == op) {
+          GC_oom_func oom_fn = GC_oom_fn;
+          UNLOCK ();
+          return((*oom_fn)(lb));
+        }
+      }
+      else {
+        GC_gcjvecfreelist[lg] = (ptr_t)obj_link (op);
+        GC_bytes_allocd += GRANULES_TO_BYTES ((word)lg);
+      }
+      GC_ASSERT (((void **)op)[1] == 0);
+    }
+    else {
+      LOCK ();
+      maybe_finalize ();
+      op = (ptr_t)GENERAL_MALLOC_INNER ((word)lb, GC_gcj_vector_kind);
+      if (0 == op) {
+        GC_oom_func oom_fn = GC_oom_fn;
+        UNLOCK ();
+        return((*oom_fn)(lb));
+      }
+    }
+    *(void **)op = ptr_to_struct_containing_descr;
+    UNLOCK ();
+    GC_dirty (op);
+    return((void *)op);
+  }
+#define ELEMENT_CHUNK_SIZE 256
+
+GC_API mse * GC_CALL
+  GC_gcj_vector_mark_proc (mse *mark_stack_ptr, GC_descr element_desc, word *start, word *end, int words_per_element)
+{
+	/* create new descriptor that is shifted two bits to account 
+	* for lack of object header. Descriptors for value types include
+	* the object header for boxed values */
+
+	/* remove tags */
+	GC_descr element_desc_shifted = element_desc & ~(GC_DS_TAGS);
+	/* shift actual bits */
+	element_desc_shifted = element_desc_shifted << 2;
+	/* shifted and unmasked desc to use for bulk processing */
+	GC_descr element_desc_shifted_unmasked = element_desc_shifted;
+	/* add back tag to indicate descriptor is a bitmap */
+	element_desc_shifted |= GC_DS_BITMAP;
+
+	/* attempt to bulk process multiple elements with single descriptor */
+	size_t elements_per_desc = (CPP_WORDSZ - GC_DS_TAG_BITS) / words_per_element;
+
+	size_t remaining_elements = (end - start) / words_per_element;
+	size_t bulk_count = remaining_elements / elements_per_desc;
+	size_t remainder_count = remaining_elements % elements_per_desc;
+
+	word *current = start;
+
+  size_t i;
+
+	// bulk
+	if (bulk_count) {
+		size_t bulk_stride = elements_per_desc * words_per_element;
+
+		if (bulk_count > ELEMENT_CHUNK_SIZE) {
+			bulk_count = ELEMENT_CHUNK_SIZE;
+			/* clear remainder as we have more bulk to process next time */
+			remainder_count = 0;
+
+			/* only process chunk number of items */
+			end = start + bulk_count * bulk_stride;
+
+			mark_stack_ptr++;
+			mark_stack_ptr->mse_descr.w = GC_MAKE_PROC (GC_gcj_vector_mp_index, 1 /* continue processing */);
+			mark_stack_ptr->mse_start = (ptr_t)end;
+		}
+
+		GC_descr bulk_desc = 0;
+		for (i = 0; i < elements_per_desc; ++i) {
+			bulk_desc |= element_desc_shifted_unmasked >> (i * words_per_element);
+		}
+		bulk_desc |= GC_DS_BITMAP;
+
+		for (i = 0; i < bulk_count; ++i, current += bulk_stride) {
+			mark_stack_ptr++;
+
+			mark_stack_ptr->mse_start = (ptr_t) (current);
+			mark_stack_ptr->mse_descr.w = bulk_desc;
+		}
+	}
+
+	size_t remainder_stride = words_per_element;
+	// remainder
+	for (i = 0; i < remainder_count; ++i, current += remainder_stride) {
+		mark_stack_ptr++;
+
+		mark_stack_ptr->mse_start = (ptr_t) (current);
+		mark_stack_ptr->mse_descr.w = element_desc_shifted;
+	}
+
+	return (mark_stack_ptr);
+}
+#endif
+
+#endif  /* GC_GCJ_SUPPORT */