3 files changed, 72 insertions, 19 deletions

diff --git a/src/interp/interp.cc b/src/interp/interp.cc
index b4f8403e..0dcd0ff1 100644
--- a/src/interp/interp.cc
+++ b/src/interp/interp.cc
@@ -246,8 +246,11 @@ void Store::DeleteRoot(RootList::Index index) {
 
 void Store::Collect() {
   size_t object_count = objects_.size();
-  marks_.resize(object_count);
-  std::fill(marks_.begin(), marks_.end(), false);
+
+  assert(gc_context_.call_depth == 0);
+
+  gc_context_.marks.resize(object_count);
+  std::fill(gc_context_.marks.begin(), gc_context_.marks.end(), false);
 
   // First mark all roots.
   for (RootList::Index i = 0; i < roots_.size(); ++i) {
@@ -260,31 +263,44 @@ void Store::Collect() {
     thread->Mark();
   }
 
-  // TODO: better GC algo.
-  // Loop through all newly marked objects and mark their referents.
-  std::vector<bool> all_marked(object_count, false);
-  bool new_marked;
-  do {
-    new_marked = false;
-    for (size_t i = 0; i < object_count; ++i) {
-      if (!all_marked[i] && marks_[i]) {
-        all_marked[i] = true;
-        objects_.Get(i)->Mark(*this);
-        new_marked = true;
-      }
-    }
-  } while (new_marked);
+  // This vector is often empty since the default maximum
+  // recursion is usually enough to mark all objects.
+  while (WABT_UNLIKELY(!gc_context_.untraced_objects.empty())) {
+    size_t index = gc_context_.untraced_objects.back();
+
+    assert(gc_context_.marks[index]);
+    assert(gc_context_.call_depth == 0);
+
+    gc_context_.untraced_objects.pop_back();
+    objects_.Get(index)->Mark(*this);
+  }
+
+  assert(gc_context_.call_depth == 0);
 
   // Delete all unmarked objects.
   for (size_t i = 0; i < object_count; ++i) {
-    if (objects_.IsUsed(i) && !all_marked[i]) {
+    if (objects_.IsUsed(i) && !gc_context_.marks[i]) {
       objects_.Delete(i);
     }
   }
 }
 
 void Store::Mark(Ref ref) {
-  marks_[ref.index] = true;
+  size_t index = ref.index;
+
+  if (gc_context_.marks[index])
+    return;
+
+  gc_context_.marks[index] = true;
+
+  if (WABT_UNLIKELY(gc_context_.call_depth >= max_call_depth)) {
+    gc_context_.untraced_objects.push_back(index);
+    return;
+  }
+
+  gc_context_.call_depth++;
+  objects_.Get(index)->Mark(*this);
+  gc_context_.call_depth--;
 }
 
 void Store::Mark(const RefVec& refs) {
diff --git a/src/interp/interp.h b/src/interp/interp.h
index a3fee5f4..9a12f575 100644
--- a/src/interp/interp.h
+++ b/src/interp/interp.h
@@ -481,12 +481,20 @@ class Store {
   template <typename T>
   friend class RefPtr;
 
+  struct GCContext {
+    int call_depth = 0;
+    std::vector<bool> marks;
+    std::vector<size_t> untraced_objects;
+  };
+
+  static const int max_call_depth = 10;
+
   Features features_;
+  GCContext gc_context_;
   // This set contains the currently active Thread objects.
   std::set<Thread*> threads_;
   ObjectList objects_;
   RootList roots_;
-  std::vector<bool> marks_;
 };
 
 template <typename T>
diff --git a/src/test-interp.cc b/src/test-interp.cc
index 93a524c6..e3de004b 100644
--- a/src/test-interp.cc
+++ b/src/test-interp.cc
@@ -689,6 +689,35 @@ TEST_F(InterpGCTest, Collect_InstanceExport) {
   EXPECT_EQ(after_new - 1, store_.object_count());
 }
 
+TEST_F(InterpGCTest, Collect_DeepRecursion) {
+  const size_t table_count = 65;
+
+  TableType tt = TableType{ValueType::ExternRef, Limits{1}};
+
+  // Create a chain of tables, where each contains
+  // a single reference to the next table.
+
+  Table::Ptr prev_table = Table::New(store_, tt);
+
+  for (size_t i = 1; i < table_count; i++) {
+    Table::Ptr new_table = Table::New(store_, tt);
+
+    new_table->Set(store_, 0, prev_table->self());
+
+    prev_table.reset();
+    prev_table = std::move(new_table);
+  }
+
+  store_.Collect();
+  EXPECT_EQ(table_count + 1, store_.object_count());
+
+  // Remove the last root, now all should be removed.
+  prev_table.reset();
+
+  store_.Collect();
+  EXPECT_EQ(1u, store_.object_count());
+}
+
 // TODO: Test for Thread keeping references alive as locals/params/stack values.
 // This requires better tracking of references than currently exists in the
 // interpreter. (see TODOs in Select/LocalGet/GlobalGet)