>From be9fe1f2fe9115f9cf116d923abd6ef882d14558 Mon Sep 17 00:00:00 2001
From: Paolo Bonzini <address@hidden>
Date: Wed, 27 Jul 2011 10:04:50 +0200
Subject: [PATCH] replace recursion with mark stack

libgst:
2011-07-04  Gwenael Casaccio  <address@hidden>
            Paolo Bonzini  <address@hidden>

	* libgst/oop.c: Use mark stack.
	* libgst/oop.h: Define mark stack data structures.
---
 libgst/ChangeLog |    6 +++
 libgst/oop.c     |   99 ++++++++++++++++++++++++++++++++++++------------------
 libgst/oop.h     |    7 ++++
 3 files changed, 79 insertions(+), 33 deletions(-)

diff --git a/libgst/ChangeLog b/libgst/ChangeLog
index 5436066..121fb5a 100644
--- a/libgst/ChangeLog
+++ b/libgst/ChangeLog
@@ -1,3 +1,9 @@
+2011-07-04  Gwenael Casaccio  <address@hidden>
+            Paolo Bonzini  <address@hidden>
+
+	* libgst/oop.c: Use mark stack.
+	* libgst/oop.h: Define mark stack data structures.
+
 2011-07-27  Paolo Bonzini  <address@hidden>
 
 	* libgst/oop.c: Clean up reset_incremental_gc.
diff --git a/libgst/oop.c b/libgst/oop.c
index e94b3e2..eea6565 100644
--- a/libgst/oop.c
+++ b/libgst/oop.c
@@ -348,6 +348,9 @@ _gst_init_mem (size_t eden, size_t survivor, size_t old,
       _gst_inc_init_registry ();
     }
 
+  _gst_mem.markQueue = (struct mark_queue *)
+    xcalloc (8 * K, sizeof (struct mark_queue));
+  _gst_mem.lastMarkQueue = &_gst_mem.markQueue[8 * K];
 }
 
 void _gst_update_object_memory_oop (OOP oop)
@@ -2185,50 +2188,70 @@ void
 _gst_mark_an_oop_internal (OOP oop)
 {
   OOP *curOOP, *atEndOOP;
+  struct mark_queue *markQueue = _gst_mem.markQueue;
+  struct mark_queue *lastMarkQueue = _gst_mem.lastMarkQueue;
+  struct mark_queue *currentMarkQueue = markQueue;
   goto markOne;
 
  markRange:
-  {			/* in the loop! */
-#if defined (GC_DEBUGGING)
-    gst_object obj = (gst_object) (curOOP - 1);	/* for debugging */
-#endif
-    for (;;)
+  {
+    OOP firstOOP = NULL;
+
+    /* The first unmarked OOP is used for tail recursion.  */
+    while (curOOP < atEndOOP)
+      {
+        oop = *curOOP++;
+        if (IS_OOP (oop) && !IS_OOP_MARKED (oop))
+          {
+            oop->flags |= F_REACHABLE;
+            firstOOP = oop;
+            break;
+          }
+      }
+
+    /* The second unmarked OOP is the first that is placed on the mark
+       queue.  TODO: split REACHABLE and VISITED flags.  An object is
+       marked REACHABLE here, and REACHABLE|VISITED in the markOne label.
+       At the end of GC, all REACHABLE objects are also VISITED.
+       The above loop should seek an object that is not VISITED so
+       that it can be marked.  For the loop below, however, REACHABLE
+       objects are known to be somewhere else on the mark stack, and can
+       be skipped.
+
+       Skipping objects after the first unmarked OOP is still useful,
+       because it keeps the stack size a bit lower in the relatively common
+       case of many integer or nil instance variables.  */
+    while (curOOP < atEndOOP)
       {
-        /* in a loop, do next iteration */
         oop = *curOOP;
-        PREFETCH_LOOP (curOOP, PREF_READ | PREF_NTA);
-        curOOP++;
-        if (IS_OOP (oop))
+
+        if (IS_OOP (oop) && !IS_OOP_MARKED (oop))
           {
-#if defined (GC_DEBUGGING)
-            if UNCOMMON (!IS_OOP_ADDR (oop))
+            if (currentMarkQueue == lastMarkQueue)
               {
-                printf
-                  ("Error! Invalid OOP %p was found inside %p!\n",
-                   oop, obj);
-                abort ();
+                const size_t size = lastMarkQueue - markQueue;
+
+                _gst_mem.markQueue = (struct mark_queue *)
+                  xrealloc (_gst_mem.markQueue, 2 * size * sizeof (struct mark_queue));
+                _gst_mem.lastMarkQueue = &_gst_mem.markQueue[2 * size];
+
+		markQueue = _gst_mem.markQueue;
+		lastMarkQueue = _gst_mem.lastMarkQueue;
+                currentMarkQueue = &_gst_mem.markQueue[size];
               }
-            else
-#endif
-              if (!IS_OOP_MARKED (oop))
-                {
-                  PREFETCH_START (oop->object, PREF_READ | PREF_NTA);
-
-                  /* On the last object in the set, reuse the
-                     current invocation. oop is valid, so we go to
-                     the single-object case */
-                  if UNCOMMON (curOOP == atEndOOP)
-                    goto markOne;
-
-                  _gst_mark_an_oop_internal (oop);
-                  continue;
-                }
+            currentMarkQueue->firstOOP = curOOP;
+            currentMarkQueue->endOOP = atEndOOP;
+	    currentMarkQueue++;
+            break;
           }
 
-        /* Place the check here so that the continue above skips it.  */
-        if UNCOMMON (curOOP == atEndOOP)
-          return;
+        curOOP++;
       }
+
+    if (!firstOOP)
+      goto pop;
+
+    TAIL_MARK_OOP (firstOOP);
   }
 
  markOne:
@@ -2290,6 +2313,16 @@ _gst_mark_an_oop_internal (OOP oop)
           TAIL_MARK_OOP (objClass);
       }
   }
+
+ pop:
+  {
+    if (currentMarkQueue > markQueue)
+      {
+        currentMarkQueue--;
+	TAIL_MARK_OOPRANGE (currentMarkQueue->firstOOP,
+			    currentMarkQueue->endOOP);
+      }
+  }
 }
 
 void
diff --git a/libgst/oop.h b/libgst/oop.h
index fa89dd0..c20dfc3 100644
--- a/libgst/oop.h
+++ b/libgst/oop.h
@@ -187,12 +187,19 @@ typedef struct cheney_scan_state {
   OOP current;			/* Currently scanned object */
 } cheney_scan_state;
 
+struct mark_queue
+{
+  OOP *firstOOP, *endOOP;
+};
+
 struct memory_space
 {
   heap_data *old, *fixed;
   struct new_space eden;
   struct surv_space surv[2], tenuring_queue;
 
+  struct mark_queue *markQueue, *lastMarkQueue;
+
   /* The current state of the copying collector's scan phase.  */
   struct cheney_scan_state scan;
 
-- 
1.7.6