git.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Jonathan Tan <jonathantanmy@google.com>
To: git@vger.kernel.org
Cc: Jonathan Tan <jonathantanmy@google.com>
Subject: [PATCH] negotiator/skipping: avoid stack overflow
Date: Tue, 25 Oct 2022 16:29:34 -0700	[thread overview]
Message-ID: <20221025232934.1504445-1-jonathantanmy@google.com> (raw)

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 <jonathantanmy@google.com>
---
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(-)

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);
+		}
 	}
 }
 
-- 
2.38.0.135.g90850a2211-goog


             reply	other threads:[~2022-10-25 23:29 UTC|newest]

Thread overview: 2+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-10-25 23:29 Jonathan Tan [this message]
2022-10-25 23:52 ` [PATCH] negotiator/skipping: avoid stack overflow Junio C Hamano

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20221025232934.1504445-1-jonathantanmy@google.com \
    --to=jonathantanmy@google.com \
    --cc=git@vger.kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).