Re: [PATCH v3 1/2] negotiator/default: avoid stack overflow
- From
Junio C Hamano <gitster@pobox.com>
- Date
- Apr 26, 2023, 17:14 UTC
- Message-ID
- <xmqqedo6tvkj.fsf@gitster.g>
- In-Reply-To
- <0e69d70805e6da684e6e17642a1cf0d59a03dfc0.1682513384.git.hanxin.hx@bytedance.com>
Han Xin <hanxin.hx@bytedance.com> writes:
Show 27 quoted lines
> mark_common() in negotiator/default.c may overflow the stack due to
> recursive function calls. Avoid this by instead recursing using a
> heap-allocated data structure.
>
> This is the same case as 4654134976f (negotiator/skipping: avoid
> stack overflow, 2022-10-25)
>
> Reported-by: Xin Xing <xingxin.xx@bytedance.com>
> Signed-off-by: Han Xin <hanxin.hx@bytedance.com>
> ---
> negotiator/default.c | 39 +++++++++++++++++++++++++++++----------
> 1 file changed, 29 insertions(+), 10 deletions(-)
>
> diff --git a/negotiator/default.c b/negotiator/default.c
> index f4b78eb47d..635cdd6483 100644
> --- a/negotiator/default.c
> +++ b/negotiator/default.c
> @@ -55,30 +55,49 @@ static int clear_marks(const char *refname, const struct object_id *oid,
> static void mark_common(struct negotiation_state *ns, struct commit *commit,
> int ancestors_only, int dont_parse)
> {
> - if (commit != NULL && !(commit->object.flags & COMMON)) {
> - struct object *o = (struct object *)commit;
> + struct prio_queue queue = { NULL };
> +
> + if (!commit || (commit->object.flags & COMMON))
> + return;The original naive recursive marker had a large if block guarded by the opposite condition around the whole thing, which amounts to the same as this early return. Good.
> + prio_queue_put(&queue, commit);
And the code now uses on-stack priority queue here, and bootstraps the machinery by placing the first element here. OK.
Show 5 quoted lines
> + if (!ancestors_only) {
> + commit->object.flags |= COMMON;
>
> - if (!ancestors_only)
> - o->flags |= COMMON;These two are equivalent, which is good.
> + if ((commit->object.flags & SEEN) && !(commit->object.flags & POPPED)) > + ns->non_common_revs--;
Hmph, this is a bit unexpected to duplicate the non_common_revs counting logic here. In the original, this piece of code was there just after we decided to continue digging into the parents, and even if this patch changes the mechanism with which "digging into the parents" from recursion to priority queue, it is not obvious why we can keep doing the decrementing for the current commit we are looking at, instead of doing that for parents of the commit like this patch does. In other words, it is not clear why it needs to be changed while going from recursive to iterative.
Is it because ancestors_only is not usable inside the loop in the iterative version? That is, if ancestors_only is not set, we do paint the initial commit as COMMON just as the parents we discover in the loop, but when ancestors_only is set, we need to skip painting the initial commit as COMMON, so the patch moves that logic?
It may solve the issue of special casing the initial commit, but it feels backwards in that the resulting loop becomes harder to understand by making it necessary to process the initial commit outside the loop only halfway.
It may make it easier to understand if we had another local variable, "struct commit *skip_commit", that is NULL by default but is set to the initial commit when ancestors_only is set, and do the painting with COMMON and counting of non_common_revs all inside the loop for the current commit that is being processed (instead of the parents the loop discovered). I dunno. It would avoid duplicating the logic and implements the "ancestors_only, do not paint or count the initial commit" in a more readable and straight-forward way, no?
Thanks.
Show 41 quoted lines
> + }
> + while ((commit = prio_queue_get(&queue))) {
> + struct object *o = (struct object *)commit;
>
> if (!(o->flags & SEEN))
> rev_list_push(ns, commit, SEEN);
> else {
> struct commit_list *parents;
>
> - if (!ancestors_only && !(o->flags & POPPED))
> - ns->non_common_revs--;
> if (!o->parsed && !dont_parse)
> if (repo_parse_commit(the_repository, commit))
> - return;
> + continue;
>
> for (parents = commit->parents;
> parents;
> - parents = parents->next)
> - mark_common(ns, parents->item, 0,
> - dont_parse);
> + parents = parents->next) {
> + struct commit *p = parents->item;
> +
> + if (p->object.flags & COMMON)
> + continue;
> +
> + p->object.flags |= COMMON;
> +
> + if ((p->object.flags & SEEN) && !(p->object.flags & POPPED))
> + ns->non_common_revs--;
> +
> + prio_queue_put(&queue, parents->item);
> + }
> }
> }
> +
> + clear_prio_queue(&queue);
> }
>
> /*