Fixed bug #77345 (Stack Overflow caused by circular reference in garbage collection)

4 files changed, 333 insertions, 90 deletions

diff --git a/NEWS b/NEWS
index 28e5ea09cc..c395f12847 100644
--- a/NEWS
+++ b/NEWS
@@ -6,7 +6,8 @@ PHP                                                                        NEWS
   . Fixed bug #77660 (Segmentation fault on break 2147483648). (Laruence)
   . Fixed bug #77652 (Anonymous classes can lose their interface information).
     (Nikita)
-
+  . Fixed bug #77345 (Stack Overflow caused by circular reference in garbage
+    collection). (Alexandru Patranescu, Nikita, Dmitry)
 - Apache2Handler:
   . Fixed bug #77648 (BOM in sapi/apache2handler/php_functions.c). (cmb)
 
diff --git a/Zend/tests/bug77345_gc_1.phpt b/Zend/tests/bug77345_gc_1.phpt
new file mode 100644
index 0000000000..eabb94ce7d
--- /dev/null
+++ b/Zend/tests/bug77345_gc_1.phpt
@@ -0,0 +1,42 @@
+--TEST--
+Bug #77345 (Segmentation faults stack overflow in cyclic garbage collector) (Bug #77427)
+--INI--
+zend.enable_gc = 1
+--FILE--
+<?php
+
+class Node
+{
+    /** @var Node */
+    public $previous;
+    /** @var Node */
+    public $next;
+}
+
+var_dump(gc_enabled());
+var_dump('start');
+
+$firstNode = new Node();
+$firstNode->previous = $firstNode;
+$firstNode->next = $firstNode;
+
+$circularDoublyLinkedList = $firstNode;
+
+for ($i = 0; $i < 200000; $i++) {
+    $currentNode = $circularDoublyLinkedList;
+    $nextNode = $circularDoublyLinkedList->next;
+
+    $newNode = new Node();
+
+    $newNode->previous = $currentNode;
+    $currentNode->next = $newNode;
+    $newNode->next = $nextNode;
+    $nextNode->previous = $newNode;
+
+    $circularDoublyLinkedList = $nextNode;
+}
+var_dump('end');
+--EXPECT--
+bool(true)
+string(5) "start"
+string(3) "end"
\ No newline at end of file
diff --git a/Zend/tests/bug77345_gc_2.phpt b/Zend/tests/bug77345_gc_2.phpt
new file mode 100644
index 0000000000..9d39b6b969
--- /dev/null
+++ b/Zend/tests/bug77345_gc_2.phpt
@@ -0,0 +1,48 @@
+--TEST--
+Bug #77345 (Segmentation faults stack overflow in cyclic garbage collector) (Bug #77427)
+--INI--
+zend.enable_gc = 1
+--FILE--
+<?php
+
+class Node
+{
+    /** @var Node */
+    public $previous;
+    /** @var Node */
+    public $next;
+}
+
+var_dump(gc_enabled());
+var_dump('start');
+
+function xxx() {
+    $firstNode = new Node();
+    $firstNode->previous = $firstNode;
+    $firstNode->next = $firstNode;
+
+    $circularDoublyLinkedList = $firstNode;
+
+    for ($i = 0; $i < 300000; $i++) {
+        $currentNode = $circularDoublyLinkedList;
+        $nextNode = $circularDoublyLinkedList->next;
+
+        $newNode = new Node();
+
+        $newNode->previous = $currentNode;
+        $currentNode->next = $newNode;
+        $newNode->next = $nextNode;
+        $nextNode->previous = $newNode;
+
+        $circularDoublyLinkedList = $nextNode;
+    }
+}
+
+xxx();
+gc_collect_cycles();
+
+var_dump('end');
+--EXPECT--
+bool(true)
+string(5) "start"
+string(3) "end"
\ No newline at end of file
diff --git a/Zend/zend_gc.c b/Zend/zend_gc.c
index 833ca5f66f..5486452581 100644
--- a/Zend/zend_gc.c
+++ b/Zend/zend_gc.c
@@ -48,7 +48,7 @@
  * gc_scan_roots will be called, and each root will be called with
  * gc_scan(root->ref)
  *
- * gc_scan checkes the colors of possible members.
+ * gc_scan checks the colors of possible members.
  *
  * If the node is marked as grey and the refcount > 0
  *    gc_scan_black will be called on that node to scan it's subgraph.
@@ -245,6 +245,73 @@ static zend_gc_globals gc_globals;
 # define GC_TRACE(str)
 #endif
 
+
+#define GC_STACK_SEGMENT_SIZE (((4096 - ZEND_MM_OVERHEAD) / sizeof(void*)) - 2)
+
+typedef struct _gc_stack gc_stack;
+
+struct _gc_stack {
+	gc_stack        *prev;
+	gc_stack        *next;
+	zend_refcounted *data[GC_STACK_SEGMENT_SIZE];
+};
+
+#define GC_STACK_DCL(init) \
+	gc_stack *_stack = init; \
+	size_t    _top = 0;
+
+#define GC_STACK_PUSH(ref) \
+	gc_stack_push(&_stack, &_top, ref);
+
+#define GC_STACK_POP() \
+	gc_stack_pop(&_stack, &_top)
+
+static zend_never_inline gc_stack* gc_stack_next(gc_stack *stack)
+{
+	if (UNEXPECTED(!stack->next)) {
+		gc_stack *segment = emalloc(sizeof(gc_stack));
+		segment->prev = stack;
+		segment->next = NULL;
+		stack->next = segment;
+	}
+	return stack->next;
+}
+
+static zend_always_inline void gc_stack_push(gc_stack **stack, size_t *top, zend_refcounted *ref)
+{
+	if (UNEXPECTED(*top == GC_STACK_SEGMENT_SIZE)) {
+		(*stack) = gc_stack_next(*stack);
+		(*top) = 0;
+	}
+	(*stack)->data[(*top)++] = ref;
+}
+
+static zend_always_inline zend_refcounted* gc_stack_pop(gc_stack **stack, size_t *top)
+{
+	if (UNEXPECTED((*top) == 0)) {
+		if (!(*stack)->prev) {
+			return NULL;
+		} else {
+			(*stack) = (*stack)->prev;
+			(*top) = GC_STACK_SEGMENT_SIZE - 1;
+			return (*stack)->data[GC_STACK_SEGMENT_SIZE - 1];
+		}
+	} else {
+		return (*stack)->data[--(*top)];
+	}
+}
+
+static void gc_stack_free(gc_stack *stack)
+{
+	gc_stack *p = stack->next;
+
+	while (p) {
+		stack = p->next;
+		efree(p);
+		p = stack;
+	}
+}
+
 static zend_always_inline uint32_t gc_compress(uint32_t idx)
 {
 	return idx % GC_MAX_UNCOMPRESSED;
@@ -606,16 +673,14 @@ ZEND_API void ZEND_FASTCALL gc_remove_from_buffer(zend_refcounted *ref)
 	gc_remove_from_roots(root);
 }
 
-static void gc_scan_black(zend_refcounted *ref)
+static void gc_scan_black(zend_refcounted *ref, gc_stack *stack)
 {
-	HashTable *ht;
+	HashTable *ht = NULL;
 	Bucket *p, *end;
 	zval *zv;
+	GC_STACK_DCL(stack);
 
 tail_call:
-	ht = NULL;
-	GC_REF_SET_BLACK(ref);
-
 	if (GC_TYPE(ref) == IS_OBJECT) {
 		zend_object_get_gc_t get_gc;
 		zend_object *obj = (zend_object*)ref;
@@ -630,9 +695,9 @@ tail_call:
 			ht = get_gc(&tmp, &zv, &n);
 			end = zv + n;
 			if (EXPECTED(!ht)) {
-				if (!n) return;
+				if (!n) goto next;
 				while (!Z_REFCOUNTED_P(--end)) {
-					if (zv == end) return;
+					if (zv == end) goto next;
 				}
 			}
 			while (zv != end) {
@@ -640,7 +705,8 @@ tail_call:
 					ref = Z_COUNTED_P(zv);
 					GC_ADDREF(ref);
 					if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
-						gc_scan_black(ref);
+						GC_REF_SET_BLACK(ref);
+						GC_STACK_PUSH(ref);
 					}
 				}
 				zv++;
@@ -649,33 +715,35 @@ tail_call:
 				ref = Z_COUNTED_P(zv);
 				GC_ADDREF(ref);
 				if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
+					GC_REF_SET_BLACK(ref);
 					goto tail_call;
 				}
-				return;
+				goto next;
 			}
 		} else {
-			return;
+			goto next;
 		}
 	} else if (GC_TYPE(ref) == IS_ARRAY) {
 		if ((zend_array*)ref != &EG(symbol_table)) {
 			ht = (zend_array*)ref;
 		} else {
-			return;
+			goto next;
 		}
 	} else if (GC_TYPE(ref) == IS_REFERENCE) {
 		if (Z_REFCOUNTED(((zend_reference*)ref)->val)) {
 			ref = Z_COUNTED(((zend_reference*)ref)->val);
 			GC_ADDREF(ref);
 			if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
+				GC_REF_SET_BLACK(ref);
 				goto tail_call;
 			}
 		}
-		return;
+		goto next;
 	} else {
-		return;
+		goto next;
 	}
 
-	if (!ht->nNumUsed) return;
+	if (!ht->nNumUsed) goto next;
 	p = ht->arData;
 	end = p + ht->nNumUsed;
 	while (1) {
@@ -687,7 +755,7 @@ tail_call:
 		if (Z_REFCOUNTED_P(zv)) {
 			break;
 		}
-		if (p == end) return;
+		if (p == end) goto next;
 	}
 	while (p != end) {
 		zv = &p->val;
@@ -698,7 +766,8 @@ tail_call:
 			ref = Z_COUNTED_P(zv);
 			GC_ADDREF(ref);
 			if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
-				gc_scan_black(ref);
+				GC_REF_SET_BLACK(ref);
+				GC_STACK_PUSH(ref);
 			}
 		}
 		p++;
@@ -710,28 +779,33 @@ tail_call:
 	ref = Z_COUNTED_P(zv);
 	GC_ADDREF(ref);
 	if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
+		GC_REF_SET_BLACK(ref);
+		goto tail_call;
+	}
+
+next:
+	ref = GC_STACK_POP();
+	if (ref) {
 		goto tail_call;
 	}
 }
 
-static void gc_mark_grey(zend_refcounted *ref)
+static void gc_mark_grey(zend_refcounted *ref, gc_stack *stack)
 {
-    HashTable *ht;
+	HashTable *ht = NULL;
 	Bucket *p, *end;
 	zval *zv;
+	GC_STACK_DCL(stack);
 
-tail_call:
-	if (!GC_REF_CHECK_COLOR(ref, GC_GREY)) {
-		ht = NULL;
+	do {
 		GC_BENCH_INC(zval_marked_grey);
-		GC_REF_SET_COLOR(ref, GC_GREY);
 
 		if (GC_TYPE(ref) == IS_OBJECT) {
 			zend_object_get_gc_t get_gc;
 			zend_object *obj = (zend_object*)ref;
 
 			if (EXPECTED(!(OBJ_FLAGS(ref) & IS_OBJ_FREE_CALLED) &&
-		                 (get_gc = obj->handlers->get_gc) != NULL)) {
+						 (get_gc = obj->handlers->get_gc) != NULL)) {
 				int n;
 				zval *zv, *end;
 				zval tmp;
@@ -740,31 +814,38 @@ tail_call:
 				ht = get_gc(&tmp, &zv, &n);
 				end = zv + n;
 				if (EXPECTED(!ht)) {
-					if (!n) return;
+					if (!n) goto next;
 					while (!Z_REFCOUNTED_P(--end)) {
-						if (zv == end) return;
+						if (zv == end) goto next;
 					}
 				}
 				while (zv != end) {
 					if (Z_REFCOUNTED_P(zv)) {
 						ref = Z_COUNTED_P(zv);
 						GC_DELREF(ref);
-						gc_mark_grey(ref);
+						if (!GC_REF_CHECK_COLOR(ref, GC_GREY)) {
+							GC_REF_SET_COLOR(ref, GC_GREY);
+							GC_STACK_PUSH(ref);
+						}
 					}
 					zv++;
 				}
 				if (EXPECTED(!ht)) {
 					ref = Z_COUNTED_P(zv);
 					GC_DELREF(ref);
-					goto tail_call;
+					if (!GC_REF_CHECK_COLOR(ref, GC_GREY)) {
+						GC_REF_SET_COLOR(ref, GC_GREY);
+						continue;
+					}
+					goto next;
 				}
 			} else {
-				return;
+				goto next;
 			}
 		} else if (GC_TYPE(ref) == IS_ARRAY) {
 			if (((zend_array*)ref) == &EG(symbol_table)) {
 				GC_REF_SET_BLACK(ref);
-				return;
+				goto next;
 			} else {
 				ht = (zend_array*)ref;
 			}
@@ -772,14 +853,17 @@ tail_call:
 			if (Z_REFCOUNTED(((zend_reference*)ref)->val)) {
 				ref = Z_COUNTED(((zend_reference*)ref)->val);
 				GC_DELREF(ref);
-				goto tail_call;
+				if (!GC_REF_CHECK_COLOR(ref, GC_GREY)) {
+					GC_REF_SET_COLOR(ref, GC_GREY);
+					continue;
+				}
 			}
-			return;
+			goto next;
 		} else {
-			return;
+			goto next;
 		}
 
-		if (!ht->nNumUsed) return;
+		if (!ht->nNumUsed) goto next;
 		p = ht->arData;
 		end = p + ht->nNumUsed;
 		while (1) {
@@ -791,7 +875,7 @@ tail_call:
 			if (Z_REFCOUNTED_P(zv)) {
 				break;
 			}
-			if (p == end) return;
+			if (p == end) goto next;
 		}
 		while (p != end) {
 			zv = &p->val;
@@ -801,7 +885,10 @@ tail_call:
 			if (Z_REFCOUNTED_P(zv)) {
 				ref = Z_COUNTED_P(zv);
 				GC_DELREF(ref);
-				gc_mark_grey(ref);
+				if (!GC_REF_CHECK_COLOR(ref, GC_GREY)) {
+					GC_REF_SET_COLOR(ref, GC_GREY);
+					GC_STACK_PUSH(ref);
+				}
 			}
 			p++;
 		}
@@ -811,8 +898,14 @@ tail_call:
 		}
 		ref = Z_COUNTED_P(zv);
 		GC_DELREF(ref);
-		goto tail_call;
-	}
+		if (!GC_REF_CHECK_COLOR(ref, GC_GREY)) {
+			GC_REF_SET_COLOR(ref, GC_GREY);
+			continue;
+		}
+
+next:
+		ref = GC_STACK_POP();
+	} while (ref);
 }
 
 /* Two-Finger compaction algorithm */
@@ -852,7 +945,7 @@ static void gc_compact(void)
 	}
 }
 
-static void gc_mark_roots(void)
+static void gc_mark_roots(gc_stack *stack)
 {
 	gc_root_buffer *current, *last;
 
@@ -863,31 +956,41 @@ static void gc_mark_roots(void)
 	while (current != last) {
 		if (GC_IS_ROOT(current->ref)) {
 			if (GC_REF_CHECK_COLOR(current->ref, GC_PURPLE)) {
-				gc_mark_grey(current->ref);
+				GC_REF_SET_COLOR(current->ref, GC_GREY);
+				gc_mark_grey(current->ref, stack);
 			}
 		}
 		current++;
 	}
 }
 
-static void gc_scan(zend_refcounted *ref)
+static void gc_scan(zend_refcounted *ref, gc_stack *stack)
 {
-    HashTable *ht;
+	HashTable *ht = NULL;
 	Bucket *p, *end;
 	zval *zv;
+	GC_STACK_DCL(stack);
 
 tail_call:
-	if (GC_REF_CHECK_COLOR(ref, GC_GREY)) {
+	if (GC_REF_CHECK_COLOR(ref, GC_WHITE)) {
 		if (GC_REFCOUNT(ref) > 0) {
-			gc_scan_black(ref);
+			if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
+				GC_REF_SET_BLACK(ref);
+				if (UNEXPECTED(!_stack->next)) {
+					gc_stack_next(_stack);
+				}
+				/* Split stack and reuse the tail */
+				_stack->next->prev = NULL;
+				gc_scan_black(ref, _stack->next);
+				_stack->next->prev = _stack;
+			}
 		} else {
-			GC_REF_SET_COLOR(ref, GC_WHITE);
 			if (GC_TYPE(ref) == IS_OBJECT) {
 				zend_object_get_gc_t get_gc;
 				zend_object *obj = (zend_object*)ref;
 
 				if (EXPECTED(!(OBJ_FLAGS(ref) & IS_OBJ_FREE_CALLED) &&
-				             (get_gc = obj->handlers->get_gc) != NULL)) {
+							 (get_gc = obj->handlers->get_gc) != NULL)) {
 					int n;
 					zval *zv, *end;
 					zval tmp;
@@ -896,43 +999,53 @@ tail_call:
 					ht = get_gc(&tmp, &zv, &n);
 					end = zv + n;
 					if (EXPECTED(!ht)) {
-						if (!n) return;
+						if (!n) goto next;
 						while (!Z_REFCOUNTED_P(--end)) {
-							if (zv == end) return;
+							if (zv == end) goto next;
 						}
 					}
 					while (zv != end) {
 						if (Z_REFCOUNTED_P(zv)) {
 							ref = Z_COUNTED_P(zv);
-							gc_scan(ref);
+							if (GC_REF_CHECK_COLOR(ref, GC_GREY)) {
+								GC_REF_SET_COLOR(ref, GC_WHITE);
+								GC_STACK_PUSH(ref);
+							}
 						}
 						zv++;
 					}
 					if (EXPECTED(!ht)) {
 						ref = Z_COUNTED_P(zv);
-						goto tail_call;
+						if (GC_REF_CHECK_COLOR(ref, GC_GREY)) {
+							GC_REF_SET_COLOR(ref, GC_WHITE);
+							goto tail_call;
+						}
+						goto next;
 					}
 				} else {
-					return;
+					goto next;
 				}
 			} else if (GC_TYPE(ref) == IS_ARRAY) {
 				if ((zend_array*)ref == &EG(symbol_table)) {
 					GC_REF_SET_BLACK(ref);
-					return;
+					goto next;
 				} else {
 					ht = (zend_array*)ref;
 				}
 			} else if (GC_TYPE(ref) == IS_REFERENCE) {
 				if (Z_REFCOUNTED(((zend_reference*)ref)->val)) {
 					ref = Z_COUNTED(((zend_reference*)ref)->val);
-					goto tail_call;
+					if (GC_REF_CHECK_COLOR(ref, GC_GREY)) {
+						GC_REF_SET_COLOR(ref, GC_WHITE);
+						goto tail_call;
+					}
 				}
-				return;
+				goto next;
 			} else {
-				return;
+				goto next;
 			}
 
-			if (!ht->nNumUsed) return;
+			if (!ht->nNumUsed) goto next;
 			p = ht->arData;
 			end = p + ht->nNumUsed;
 			while (1) {
@@ -944,7 +1057,7 @@ tail_call:
 				if (Z_REFCOUNTED_P(zv)) {
 					break;
 				}
-				if (p == end) return;
+				if (p == end) goto next;
 			}
 			while (p != end) {
 				zv = &p->val;
@@ -953,7 +1066,10 @@ tail_call:
 				}
 				if (Z_REFCOUNTED_P(zv)) {
 					ref = Z_COUNTED_P(zv);
-					gc_scan(ref);
+					if (GC_REF_CHECK_COLOR(ref, GC_GREY)) {
+						GC_REF_SET_COLOR(ref, GC_WHITE);
+						GC_STACK_PUSH(ref);
+					}
 				}
 				p++;
 			}
@@ -962,19 +1078,31 @@ tail_call:
 				zv = Z_INDIRECT_P(zv);
 			}
 			ref = Z_COUNTED_P(zv);
-			goto tail_call;
+			if (GC_REF_CHECK_COLOR(ref, GC_GREY)) {
+				GC_REF_SET_COLOR(ref, GC_WHITE);
+				goto tail_call;
+			}
 		}
 	}
+
+next:
+	ref = GC_STACK_POP();
+	if (ref) {
+		goto tail_call;
+	}
 }
 
-static void gc_scan_roots(void)
+static void gc_scan_roots(gc_stack *stack)
 {
 	gc_root_buffer *current = GC_IDX2PTR(GC_FIRST_ROOT);
 	gc_root_buffer *last = GC_IDX2PTR(GC_G(first_unused));
 
 	while (current != last) {
 		if (GC_IS_ROOT(current->ref)) {
-			gc_scan(current->ref);
+			if (GC_REF_CHECK_COLOR(current->ref, GC_GREY)) {
+				GC_REF_SET_COLOR(current->ref, GC_WHITE);
+				gc_scan(current->ref, stack);
+			}
 		}
 		current++;
 	}
@@ -1005,18 +1133,15 @@ static void gc_add_garbage(zend_refcounted *ref)
 	GC_G(num_roots)++;
 }
 
-static int gc_collect_white(zend_refcounted *ref, uint32_t *flags)
+static int gc_collect_white(zend_refcounted *ref, uint32_t *flags, gc_stack *stack)
 {
 	int count = 0;
-	HashTable *ht;
+	HashTable *ht = NULL;
 	Bucket *p, *end;
 	zval *zv;
+	GC_STACK_DCL(stack);
 
-tail_call:
-	if (GC_REF_CHECK_COLOR(ref, GC_WHITE)) {
-		ht = NULL;
-		GC_REF_SET_BLACK(ref);
-
+	do {
 		/* don't count references for compatibility ??? */
 		if (GC_TYPE(ref) != IS_REFERENCE) {
 			count++;
@@ -1027,7 +1152,7 @@ tail_call:
 			zend_object *obj = (zend_object*)ref;
 
 			if (EXPECTED(!(OBJ_FLAGS(ref) & IS_OBJ_FREE_CALLED) &&
-			             (get_gc = obj->handlers->get_gc) != NULL)) {
+						 (get_gc = obj->handlers->get_gc) != NULL)) {
 				int n;
 				zval *zv, *end;
 				zval tmp;
@@ -1037,28 +1162,31 @@ tail_call:
 					gc_add_garbage(ref);
 				}
 				if (obj->handlers->dtor_obj &&
-				    ((obj->handlers->dtor_obj != zend_objects_destroy_object) ||
-				     (obj->ce->destructor != NULL))) {
+					((obj->handlers->dtor_obj != zend_objects_destroy_object) ||
+					 (obj->ce->destructor != NULL))) {
 					*flags |= GC_HAS_DESTRUCTORS;
 				}
 				ZVAL_OBJ(&tmp, obj);
 				ht = get_gc(&tmp, &zv, &n);
 				end = zv + n;
 				if (EXPECTED(!ht)) {
-					if (!n) return count;
+					if (!n) goto next;
 					while (!Z_REFCOUNTED_P(--end)) {
 						/* count non-refcounted for compatibility ??? */
 						if (Z_TYPE_P(zv) != IS_UNDEF) {
 							count++;
 						}
-						if (zv == end) return count;
+						if (zv == end) goto next;
 					}
 				}
 				while (zv != end) {
 					if (Z_REFCOUNTED_P(zv)) {
 						ref = Z_COUNTED_P(zv);
 						GC_ADDREF(ref);
-						count += gc_collect_white(ref, flags);
+						if (GC_REF_CHECK_COLOR(ref, GC_WHITE)) {
+							GC_REF_SET_BLACK(ref);
+							GC_STACK_PUSH(ref);
+						}
 					/* count non-refcounted for compatibility ??? */
 					} else if (Z_TYPE_P(zv) != IS_UNDEF) {
 						count++;
@@ -1068,10 +1196,14 @@ tail_call:
 				if (EXPECTED(!ht)) {
 					ref = Z_COUNTED_P(zv);
 					GC_ADDREF(ref);
-					goto tail_call;
+					if (GC_REF_CHECK_COLOR(ref, GC_WHITE)) {
+						GC_REF_SET_BLACK(ref);
+						continue;
+					}
+					goto next;
 				}
 			} else {
-				return count;
+				goto next;
 			}
 		} else if (GC_TYPE(ref) == IS_ARRAY) {
 			/* optimization: color is GC_BLACK (0) */
@@ -1083,14 +1215,17 @@ tail_call:
 			if (Z_REFCOUNTED(((zend_reference*)ref)->val)) {
 				ref = Z_COUNTED(((zend_reference*)ref)->val);
 				GC_ADDREF(ref);
-				goto tail_call;
+				if (GC_REF_CHECK_COLOR(ref, GC_WHITE)) {
+					GC_REF_SET_BLACK(ref);
+					continue;
+				}
 			}
-			return count;
+			goto next;
 		} else {
-			return count;
+			goto next;
 		}
 
-		if (!ht->nNumUsed) return count;
+		if (!ht->nNumUsed) goto next;
 		p = ht->arData;
 		end = p + ht->nNumUsed;
 		while (1) {
@@ -1106,7 +1241,7 @@ tail_call:
 			if (Z_TYPE_P(zv) != IS_UNDEF) {
 				count++;
 			}
-			if (p == end) return count;
+			if (p == end) goto next;
 		}
 		while (p != end) {
 			zv = &p->val;
@@ -1116,7 +1251,10 @@ tail_call:
 			if (Z_REFCOUNTED_P(zv)) {
 				ref = Z_COUNTED_P(zv);
 				GC_ADDREF(ref);
-				count += gc_collect_white(ref, flags);
+				if (GC_REF_CHECK_COLOR(ref, GC_WHITE)) {
+					GC_REF_SET_BLACK(ref);
+					GC_STACK_PUSH(ref);
+				}
 				/* count non-refcounted for compatibility ??? */
 			} else if (Z_TYPE_P(zv) != IS_UNDEF) {
 				count++;
@@ -1129,12 +1267,19 @@ tail_call:
 		}
 		ref = Z_COUNTED_P(zv);
 		GC_ADDREF(ref);
-		goto tail_call;
-	}
+		if (GC_REF_CHECK_COLOR(ref, GC_WHITE)) {
+			GC_REF_SET_BLACK(ref);
+			continue;
+		}
+
+next:
+		ref = GC_STACK_POP();
+	} while (ref);
+
 	return count;
 }
 
-static int gc_collect_roots(uint32_t *flags)
+static int gc_collect_roots(uint32_t *flags, gc_stack *stack)
 {
 	uint32_t idx, end;
 	zend_refcounted *ref;
@@ -1165,7 +1310,8 @@ static int gc_collect_roots(uint32_t *flags)
 		ZEND_ASSERT(GC_IS_ROOT(ref));
 		current->ref = GC_MAKE_GARBAGE(ref);
 		if (GC_REF_CHECK_COLOR(ref, GC_WHITE)) {
-			count += gc_collect_white(ref, flags);
+			GC_REF_SET_BLACK(ref);
+			count += gc_collect_white(ref, flags, stack);
 		}
 		idx++;
 	}
@@ -1280,6 +1426,10 @@ ZEND_API int zend_gc_collect_cycles(void)
 		zend_refcounted *p;
 		uint32_t gc_flags = 0;
 		uint32_t idx, end;
+		gc_stack stack;
+
+		stack.prev = NULL;
+		stack.next = NULL;
 
 		if (GC_G(gc_active)) {
 			return 0;
@@ -1290,12 +1440,14 @@ ZEND_API int zend_gc_collect_cycles(void)
 		GC_G(gc_active) = 1;
 
 		GC_TRACE("Marking roots");
-		gc_mark_roots();
+		gc_mark_roots(&stack);
 		GC_TRACE("Scanning roots");
-		gc_scan_roots();
+		gc_scan_roots(&stack);
 
 		GC_TRACE("Collecting roots");
-		count = gc_collect_roots(&gc_flags);
+		count = gc_collect_roots(&gc_flags, &stack);
+
+		gc_stack_free(&stack);
 
 		if (!GC_G(num_roots)) {
 			/* nothing to free */