Re: [PATCH v2 1/2] negotiator/default: avoid stack overflow

[Derrick Stolee <derrickstolee@github.com>]

On 4/26/2023 12:05 AM, Han Xin wrote:
> 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 [1].
> 
> 1. 4654134976f (negotiator/skipping: avoid stack overflow, 2022-10-25)

We would typically write this inline, such as:

  This is the same case as 4654134976f (negotiator/skipping: avoid
  stack overflow, 2022-10-25)

> -	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;
> +
> +	prio_queue_put(&queue, commit);
> +	if (!ancestors_only) {
> +		commit->object.flags |= COMMON;
>  
> -		if (!ancestors_only)
> -			o->flags |= COMMON;
> +		if ((commit->object.flags & SEEN) && !(commit->object.flags & POPPED))
> +			ns->non_common_revs--;
> +	}
> +	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);

Thanks for this version. It looks like an identical set of actions
in the commit walk, but the change from DFS to priority queue is
a welcome change.

-Stolee