{"thread":{"id":"58692","subject":"[PATCH] negotiator/skipping: avoid stack overflow","startedAt":"2022-10-25T23:29:42Z","lastAt":"2022-10-25T23:52:13Z","messageCount":2,"participants":["Jonathan Tan","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"465742","messageId":"20221025232934.1504445-1-jonathantanmy@google.com","threadId":"58692","inReplyTo":null,"subject":"[PATCH] negotiator/skipping: avoid stack overflow","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2022-10-25T23:29:34Z","receivedAt":"2022-10-25T23:29:42Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"mark_common() in negotiator/skipping.c may overflow the stack due to\nrecursive function calls. Avoid this by instead recursing using a\nheap-allocated data structure.\n\nSigned-off-by: Jonathan Tan <jonathantanmy@google.com>\n---\nThis was observed at $DAYJOB.\n\nTo reviewers, you can check the diff with:\n  git show --color-moved-ws=allow-indentation-change --color-moved\nto more clearly show which lines are new and which lines have only\nchanged indentation.\n---\n negotiator/skipping.c | 29 +++++++++++++++++------------\n 1 file changed, 17 insertions(+), 12 deletions(-)\n\ndiff --git a/negotiator/skipping.c b/negotiator/skipping.c\nindex c4398f5ae1..0f5ac48e87 100644\n--- a/negotiator/skipping.c\n+++ b/negotiator/skipping.c\n@@ -86,21 +86,26 @@ static int clear_marks(const char *refname, const struct object_id *oid,\n /*\n  * Mark this SEEN commit and all its SEEN ancestors as COMMON.\n  */\n-static void mark_common(struct data *data, struct commit *c)\n+static void mark_common(struct data *data, struct commit *seen_commit)\n {\n-\tstruct commit_list *p;\n+\tstruct prio_queue queue = { NULL };\n+\tstruct commit *c;\n \n-\tif (c->object.flags & COMMON)\n-\t\treturn;\n-\tc->object.flags |= COMMON;\n-\tif (!(c->object.flags & POPPED))\n-\t\tdata->non_common_revs--;\n+\tprio_queue_put(&queue, seen_commit);\n+\twhile ((c = prio_queue_get(&queue))) {\n+\t\tstruct commit_list *p;\n+\t\tif (c->object.flags & COMMON)\n+\t\t\treturn;\n+\t\tc->object.flags |= COMMON;\n+\t\tif (!(c->object.flags & POPPED))\n+\t\t\tdata->non_common_revs--;\n \n-\tif (!c->object.parsed)\n-\t\treturn;\n-\tfor (p = c->parents; p; p = p->next) {\n-\t\tif (p->item->object.flags & SEEN)\n-\t\t\tmark_common(data, p->item);\n+\t\tif (!c->object.parsed)\n+\t\t\treturn;\n+\t\tfor (p = c->parents; p; p = p->next) {\n+\t\t\tif (p->item->object.flags & SEEN)\n+\t\t\t\tprio_queue_put(&queue, p->item);\n+\t\t}\n \t}\n }\n \n-- \n2.38.0.135.g90850a2211-goog\n\n"},{"id":"465746","messageId":"xmqqilk7mpg8.fsf@gitster.g","threadId":"58692","inReplyTo":"20221025232934.1504445-1-jonathantanmy@google.com","subject":"Re: [PATCH] negotiator/skipping: avoid stack overflow","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-10-25T23:52:07Z","receivedAt":"2022-10-25T23:52:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan <jonathantanmy@google.com> writes:\n\n> mark_common() in negotiator/skipping.c may overflow the stack due to\n> recursive function calls. Avoid this by instead recursing using a\n> heap-allocated data structure.\n\nVery straight-forward.  I think we've done quite a many of these in\nvarious places by now ;-)\n\n"}]}