Han Xin <hanxin.hx@xxxxxxxxxxxxx> writes:
> 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@xxxxxxxxxxxxx>
> Signed-off-by: Han Xin <hanxin.hx@xxxxxxxxxxxxx>
> ---
> 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.
> + 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.
> + }
> + 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);
> }
>
> /*
