negotiator/skipping: avoid stack overflow

Commit Message

Jonathan Tan Oct. 25, 2022, 11:29 p.m. UTC

mark_common() in negotiator/skipping.c may overflow the stack due to
recursive function calls. Avoid this by instead recursing using a
heap-allocated data structure.

Signed-off-by: Jonathan Tan <[e-mail]>
---
This was observed at $DAYJOB.

To reviewers, you can check the diff with:
  git show --color-moved-ws=allow-indentation-change --color-moved
to more clearly show which lines are new and which lines have only
changed indentation.
---
 negotiator/skipping.c | 29 +++++++++++++++++------------
 1 file changed, 17 insertions(+), 12 deletions(-)

Comments

Junio C Hamano Oct. 25, 2022, 11:52 p.m. UTC | #1

Jonathan Tan <[e-mail]> writes:

> mark_common() in negotiator/skipping.c may overflow the stack due to
> recursive function calls. Avoid this by instead recursing using a
> heap-allocated data structure.

Very straight-forward.  I think we've done quite a many of these in
various places by now ;-)

Patch

diff --git a/negotiator/skipping.c b/negotiator/skipping.c
index c4398f5ae1..0f5ac48e87 100644
--- a/negotiator/skipping.c
+++ b/negotiator/skipping.c
@@ -86,21 +86,26 @@  static int clear_marks(const char *refname, const struct object_id *oid,
 /*
  * Mark this SEEN commit and all its SEEN ancestors as COMMON.
  */
-static void mark_common(struct data *data, struct commit *c)
+static void mark_common(struct data *data, struct commit *seen_commit)
 {
-	struct commit_list *p;
+	struct prio_queue queue = { NULL };
+	struct commit *c;
 
-	if (c->object.flags & COMMON)
-		return;
-	c->object.flags |= COMMON;
-	if (!(c->object.flags & POPPED))
-		data->non_common_revs--;
+	prio_queue_put(&queue, seen_commit);
+	while ((c = prio_queue_get(&queue))) {
+		struct commit_list *p;
+		if (c->object.flags & COMMON)
+			return;
+		c->object.flags |= COMMON;
+		if (!(c->object.flags & POPPED))
+			data->non_common_revs--;
 
-	if (!c->object.parsed)
-		return;
-	for (p = c->parents; p; p = p->next) {
-		if (p->item->object.flags & SEEN)
-			mark_common(data, p->item);
+		if (!c->object.parsed)
+			return;
+		for (p = c->parents; p; p = p->next) {
+			if (p->item->object.flags & SEEN)
+				prio_queue_put(&queue, p->item);
+		}
 	}
 }