[PATCH] negotiator/skipping.c: parse parents before queueing

[PATCH] negotiator/skipping.c: parse parents before queueing

[Taylor Blau]

From: Taylor Blau <ttaylorr@openai.com>

The skipping negotiator sorts its queue by commit date, but
`push_parent()` can add a parent before parsing it. Its date is still
zero, so old ref tips go ahead of it.

For example, suppose a topic branch is one commit ahead of master.
Skipping offers the topic tip and skips master's tip. Master's parent
then waits behind old ref tips. With enough old refs, negotiation can
end before we offer that recent common ancestor.

Parse each unseen parent before adding it to the queue, so the queue
uses its actual date. If parsing fails, leave the parent out of the
queue.

Signed-off-by: Taylor Blau <ttaylorr@openai.com>
---
 negotiator/skipping.c                |  5 ++++-
 t/t5552-skipping-fetch-negotiator.sh | 33 ++++++++++++++++++++++++++++
 2 files changed, 37 insertions(+), 1 deletion(-)

diff --git a/negotiator/skipping.c b/negotiator/skipping.c
index db90fa77b53..ed6e88b59b4 100644
--- a/negotiator/skipping.c
+++ b/negotiator/skipping.c
@@ -125,7 +125,7 @@ static void mark_common(struct data *data, struct commit *seen_commit)
  * entry has the correct flags and ttl.
  *
  * This function returns 1 if an entry was found or created, and 0 otherwise
- * (because the entry for this commit had already been popped).
+ * (because the commit could not be parsed or its entry had already been popped).
  */
 static int push_parent(struct data *data, struct entry *entry,
 		       struct commit *to_push)
@@ -151,6 +151,9 @@ static int push_parent(struct data *data, struct entry *entry,
 parent_found:
 		;
 	} else {
+		/* Parse the parent before using its date to order the queue. */
+		if (repo_parse_commit(the_repository, to_push))
+			return 0;
 		parent_entry = rev_list_push(data, to_push, 0);
 	}
 
diff --git a/t/t5552-skipping-fetch-negotiator.sh b/t/t5552-skipping-fetch-negotiator.sh
index 96e224168eb..7a0b9b32474 100755
--- a/t/t5552-skipping-fetch-negotiator.sh
+++ b/t/t5552-skipping-fetch-negotiator.sh
@@ -223,4 +223,37 @@ test_expect_success 'do not send "have" with ancestors of commits that server AC
 	have_sent b2.c1 b2.c0
 '
 
+test_expect_success 'recent ancestors are sent before old ref tips' '
+	rm -rf server client trace &&
+	git init server &&
+	test_tick=2000000000 &&
+	test_commit -C server --no-tag base &&
+	test_commit -C server --no-tag parent &&
+	test_commit -C server --no-tag main &&
+	git clone server client &&
+	test_commit -C server --no-tag to_fetch &&
+
+	git -C client checkout -b topic &&
+	test_commit -C client --no-tag topic &&
+
+	# These old tips have known dates, but the recent parent has no ref.
+	# Without parsing parents before queueing them, its date is zero and
+	# all of these tips are sent first, delaying it past the first batch.
+	for i in $(test_seq 32)
+	do
+		old=$(echo "old $i" |
+			GIT_AUTHOR_DATE="1000000000 +0000" \
+			GIT_COMMITTER_DATE="1000000000 +0000" \
+			git -C client commit-tree HEAD^{tree}) &&
+		git -C client update-ref refs/heads/old-$i "$old" || return 1
+	done &&
+
+	test_config -C client fetch.negotiationalgorithm skipping &&
+	trace_fetch client origin &&
+	git -C client rev-parse HEAD HEAD~2 >expect &&
+	sed -n "s/.*fetch> have //p" trace >haves &&
+	sed -n "1,2p" haves >actual &&
+	test_cmp expect actual
+'
+
 test_done

base-commit: c51408889c3b372814bc20b9431c3b74d0d268eb
-- 
2.56.0.187.gdc3dfa3647c

Re: [PATCH] negotiator/skipping.c: parse parents before queueing

[Patrick Steinhardt]

On Mon, Oct 19, 2026 at 03:17:07PM -0500, Taylor Blau wrote:
> diff --git a/negotiator/skipping.c b/negotiator/skipping.c
> index db90fa77b53..ed6e88b59b4 100644
> --- a/negotiator/skipping.c
> +++ b/negotiator/skipping.c
> @@ -151,6 +151,9 @@ static int push_parent(struct data *data, struct entry *entry,
>  parent_found:
>  		;
>  	} else {
> +		/* Parse the parent before using its date to order the queue. */
> +		if (repo_parse_commit(the_repository, to_push))
> +			return 0;
>  		parent_entry = rev_list_push(data, to_push, 0);
>  	}

Why do you parse the commit in `push_parent()` instead of parsing it in
`rev_list_push()`? The latter would also cover the other two callsites
that call it, and to me it's not clear why they wouldn't want to parse
the commits before adding it to the queue.

Doing so in `rev_list_push()` would also bring it in line with the
default negotiator.

There's also another call to `repo_parse_commit()` in `get_rev()`. Once
we start parsing the commit in `rev_list_push()` we could drop that call
as we'd know that every commit in the queue is parsed already.

> diff --git a/t/t5552-skipping-fetch-negotiator.sh b/t/t5552-skipping-fetch-negotiator.sh
> index 96e224168eb..7a0b9b32474 100755
> --- a/t/t5552-skipping-fetch-negotiator.sh
> +++ b/t/t5552-skipping-fetch-negotiator.sh
> @@ -223,4 +223,37 @@ test_expect_success 'do not send "have" with ancestors of commits that server AC
>  	have_sent b2.c1 b2.c0
>  '
>  
> +test_expect_success 'recent ancestors are sent before old ref tips' '
> +	rm -rf server client trace &&
> +	git init server &&
> +	test_tick=2000000000 &&
> +	test_commit -C server --no-tag base &&
> +	test_commit -C server --no-tag parent &&
> +	test_commit -C server --no-tag main &&
> +	git clone server client &&
> +	test_commit -C server --no-tag to_fetch &&
> +
> +	git -C client checkout -b topic &&
> +	test_commit -C client --no-tag topic &&
> +
> +	# These old tips have known dates, but the recent parent has no ref.
> +	# Without parsing parents before queueing them, its date is zero and
> +	# all of these tips are sent first, delaying it past the first batch.
> +	for i in $(test_seq 32)
> +	do
> +		old=$(echo "old $i" |
> +			GIT_AUTHOR_DATE="1000000000 +0000" \
> +			GIT_COMMITTER_DATE="1000000000 +0000" \
> +			git -C client commit-tree HEAD^{tree}) &&
> +		git -C client update-ref refs/heads/old-$i "$old" || return 1
> +	done &&
> +
> +	test_config -C client fetch.negotiationalgorithm skipping &&
> +	trace_fetch client origin &&
> +	git -C client rev-parse HEAD HEAD~2 >expect &&
> +	sed -n "s/.*fetch> have //p" trace >haves &&
> +	sed -n "1,2p" haves >actual &&

Nit: `head -n2 haves >actual`

Thanks!

Patrick

Re: [PATCH] negotiator/skipping.c: parse parents before queueing

[Junio C Hamano]

Patrick Steinhardt <ps@pks.im> writes:

> On Mon, Oct 19, 2026 at 03:17:07PM -0500, Taylor Blau wrote:
>> diff --git a/negotiator/skipping.c b/negotiator/skipping.c
>> index db90fa77b53..ed6e88b59b4 100644
>> --- a/negotiator/skipping.c
>> +++ b/negotiator/skipping.c
>> @@ -151,6 +151,9 @@ static int push_parent(struct data *data, struct entry *entry,
>>  parent_found:
>>  		;
>>  	} else {
>> +		/* Parse the parent before using its date to order the queue. */
>> +		if (repo_parse_commit(the_repository, to_push))
>> +			return 0;
>>  		parent_entry = rev_list_push(data, to_push, 0);
>>  	}
>
> Why do you parse the commit in `push_parent()` instead of parsing it in
> `rev_list_push()`? The latter would also cover the other two callsites
> that call it, and to me it's not clear why they wouldn't want to parse
> the commits before adding it to the queue.
>
> Doing so in `rev_list_push()` would also bring it in line with the
> default negotiator.
>
> There's also another call to `repo_parse_commit()` in `get_rev()`. Once
> we start parsing the commit in `rev_list_push()` we could drop that call
> as we'd know that every commit in the queue is parsed already.

Thanks for noticing this.

Re: [PATCH] negotiator/skipping.c: parse parents before queueing

[Taylor Blau]

On Wed, Oct 21, 2026 at 08:49:27AM +0200, Patrick Steinhardt wrote:
> On Mon, Oct 19, 2026 at 03:17:07PM -0500, Taylor Blau wrote:
> > diff --git a/negotiator/skipping.c b/negotiator/skipping.c
> > index db90fa77b53..ed6e88b59b4 100644
> > --- a/negotiator/skipping.c
> > +++ b/negotiator/skipping.c
> > @@ -151,6 +151,9 @@ static int push_parent(struct data *data, struct entry *entry,
> >  parent_found:
> >  		;
> >  	} else {
> > +		/* Parse the parent before using its date to order the queue. */
> > +		if (repo_parse_commit(the_repository, to_push))
> > +			return 0;
> >  		parent_entry = rev_list_push(data, to_push, 0);
> >  	}
>
> Why do you parse the commit in `push_parent()` instead of parsing it in
> `rev_list_push()`? The latter would also cover the other two callsites
> that call it, and to me it's not clear why they wouldn't want to parse
> the commits before adding it to the queue.
>
> Doing so in `rev_list_push()` would also bring it in line with the
> default negotiator.

I originally wrote it this way because the skipping negotiator's version
of `rev_list_push()` returns a pointer to an 'entry' struct, whereas the
default negotiator's simply returns void. But the only caller that needs
to learn to handle a NULL return value from that function is simply
`push_parent()` itself, since the other two callers already disregard
the return value.

I agree that performing the parse in `rev_list_push()` makes more sense
from both an ergonomic and consistency perspective, so I have moved it
there for the next round.

> There's also another call to `repo_parse_commit()` in `get_rev()`. Once
> we start parsing the commit in `rev_list_push()` we could drop that call
> as we'd know that every commit in the queue is parsed already.

That makes sense. The commit struct comes from the queue, and we know
that the queue always has fully-parsed commits, so there is no need to
re-parse it (even though the second and subsequent calls are noops).
I've removed it.

> > +	sed -n "s/.*fetch> have //p" trace >haves &&
> > +	sed -n "1,2p" haves >actual &&
>
> Nit: `head -n2 haves >actual`

Thanks, I realized when responding here that we don't even need the
'haves' intermediate file, so we can replace this and the above line
with:

    sed -n "s/.*fetch> have //p" trace | head -n 2 >actual &&

Thanks for reviewing!

Thanks,
Taylor

[PATCH v2] negotiator/skipping.c: parse parents before queueing

[Taylor Blau]

From: Taylor Blau <ttaylorr@openai.com>

The skipping negotiator sorts its queue by commit date, but callers
which push commits onto that queue, such as `push_parent()`, can add a
parent before parsing it. When an unparsed commit enters the queue, its
date is still zero, so old ref tips may sort ahead of it.

For example, suppose a topic branch is one commit ahead of master.
Skipping offers the topic tip and skips master's tip. Master's parent
then waits behind old ref tips. With enough old refs, negotiation can
end before we offer that recent common ancestor.

Parse each unseen parent before adding it to the queue, so the queue
uses its actual date. If parsing fails, leave the parent out of the
queue.

Since the sole caller of `prio_queue_put()` ensures that commits are
fully parsed before pushing them onto the queue, we can avoid a noop
call to `repo_parse_commit()` within `get_rev()`.

Note that unlike the default negotiator, the skipping negotiator's
version of `rev_list_push()` returns a pointer to an 'entry' struct. As
a consequence, callers must be prepared to handle a NULL return value.
The caller in `push_parent()` gains a NULL-ness check, and the remaining
two callers continue to ignore the return value from `rev_list_push()`.

Signed-off-by: Taylor Blau <ttaylorr@openai.com>
---
 negotiator/skipping.c                |  8 +++++--
 t/t5552-skipping-fetch-negotiator.sh | 32 ++++++++++++++++++++++++++++
 2 files changed, 38 insertions(+), 2 deletions(-)

diff --git a/negotiator/skipping.c b/negotiator/skipping.c
index db90fa77b53..0ae5f28d353 100644
--- a/negotiator/skipping.c
+++ b/negotiator/skipping.c
@@ -66,6 +66,9 @@ static struct entry *rev_list_push(struct data *data, struct commit *commit, int
 	struct entry *entry;
 	commit->object.flags |= mark | SEEN;
 
+	if (repo_parse_commit(the_repository, commit))
+		return NULL;
+
 	CALLOC_ARRAY(entry, 1);
 	entry->commit = commit;
 	prio_queue_put(&data->rev_list, entry);
@@ -125,7 +128,7 @@ static void mark_common(struct data *data, struct commit *seen_commit)
  * entry has the correct flags and ttl.
  *
  * This function returns 1 if an entry was found or created, and 0 otherwise
- * (because the entry for this commit had already been popped).
+ * (because the commit could not be parsed or its entry had already been popped).
  */
 static int push_parent(struct data *data, struct entry *entry,
 		       struct commit *to_push)
@@ -152,6 +155,8 @@ static int push_parent(struct data *data, struct entry *entry,
 		;
 	} else {
 		parent_entry = rev_list_push(data, to_push, 0);
+		if (!parent_entry)
+			return 0;
 	}
 
 	if (entry->commit->object.flags & (COMMON | ADVERTISED)) {
@@ -194,7 +199,6 @@ static const struct object_id *get_rev(struct data *data)
 		if (!(commit->object.flags & COMMON) && !entry->ttl)
 			to_send = commit;
 
-		repo_parse_commit(the_repository, commit);
 		for (p = commit->parents; p; p = p->next)
 			parent_pushed |= push_parent(data, entry, p->item);
 
diff --git a/t/t5552-skipping-fetch-negotiator.sh b/t/t5552-skipping-fetch-negotiator.sh
index 96e224168eb..7479424ca94 100755
--- a/t/t5552-skipping-fetch-negotiator.sh
+++ b/t/t5552-skipping-fetch-negotiator.sh
@@ -223,4 +223,36 @@ test_expect_success 'do not send "have" with ancestors of commits that server AC
 	have_sent b2.c1 b2.c0
 '
 
+test_expect_success 'recent ancestors are sent before old ref tips' '
+	rm -rf server client trace &&
+	git init server &&
+	test_tick=2000000000 &&
+	test_commit -C server --no-tag base &&
+	test_commit -C server --no-tag parent &&
+	test_commit -C server --no-tag main &&
+	git clone server client &&
+	test_commit -C server --no-tag to_fetch &&
+
+	git -C client checkout -b topic &&
+	test_commit -C client --no-tag topic &&
+
+	# These old tips have known dates, but the recent parent has no ref.
+	# Without parsing parents before queueing them, its date is zero and
+	# all of these tips are sent first, delaying it past the first batch.
+	for i in $(test_seq 32)
+	do
+		old=$(echo "old $i" |
+			GIT_AUTHOR_DATE="1000000000 +0000" \
+			GIT_COMMITTER_DATE="1000000000 +0000" \
+			git -C client commit-tree HEAD^{tree}) &&
+		git -C client update-ref refs/heads/old-$i "$old" || return 1
+	done &&
+
+	test_config -C client fetch.negotiationalgorithm skipping &&
+	trace_fetch client origin &&
+	git -C client rev-parse HEAD HEAD~2 >expect &&
+	sed -n "s/.*fetch> have //p" trace | head -n 2 >actual &&
+	test_cmp expect actual
+'
+
 test_done

Range-diff against v1:
1:  cfb16d16d8c ! 1:  9e9ae442333 negotiator/skipping.c: parse parents before queueing
    @@ Metadata
      ## Commit message ##
         negotiator/skipping.c: parse parents before queueing
     
    -    The skipping negotiator sorts its queue by commit date, but
    -    `push_parent()` can add a parent before parsing it. Its date is still
    -    zero, so old ref tips go ahead of it.
    +    The skipping negotiator sorts its queue by commit date, but callers
    +    which push commits onto that queue, such as `push_parent()`, can add a
    +    parent before parsing it. When an unparsed commit enters the queue, its
    +    date is still zero, so old ref tips may sort ahead of it.
     
         For example, suppose a topic branch is one commit ahead of master.
         Skipping offers the topic tip and skips master's tip. Master's parent
    @@ Commit message
         uses its actual date. If parsing fails, leave the parent out of the
         queue.
     
    +    Since the sole caller of `prio_queue_put()` ensures that commits are
    +    fully parsed before pushing them onto the queue, we can avoid a noop
    +    call to `repo_parse_commit()` within `get_rev()`.
    +
    +    Note that unlike the default negotiator, the skipping negotiator's
    +    version of `rev_list_push()` returns a pointer to an 'entry' struct. As
    +    a consequence, callers must be prepared to handle a NULL return value.
    +    The caller in `push_parent()` gains a NULL-ness check, and the remaining
    +    two callers continue to ignore the return value from `rev_list_push()`.
    +
         Signed-off-by: Taylor Blau <ttaylorr@openai.com>
    -    Signed-off-by: Taylor Blau <me@ttaylorr.com>
     
      ## negotiator/skipping.c ##
    +@@ negotiator/skipping.c: static struct entry *rev_list_push(struct data *data, struct commit *commit, int
    + 	struct entry *entry;
    + 	commit->object.flags |= mark | SEEN;
    + 
    ++	if (repo_parse_commit(the_repository, commit))
    ++		return NULL;
    ++
    + 	CALLOC_ARRAY(entry, 1);
    + 	entry->commit = commit;
    + 	prio_queue_put(&data->rev_list, entry);
     @@ negotiator/skipping.c: static void mark_common(struct data *data, struct commit *seen_commit)
       * entry has the correct flags and ttl.
       *
    @@ negotiator/skipping.c: static void mark_common(struct data *data, struct commit
      static int push_parent(struct data *data, struct entry *entry,
      		       struct commit *to_push)
     @@ negotiator/skipping.c: static int push_parent(struct data *data, struct entry *entry,
    - parent_found:
      		;
      	} else {
    -+		/* Parse the parent before using its date to order the queue. */
    -+		if (repo_parse_commit(the_repository, to_push))
    -+			return 0;
      		parent_entry = rev_list_push(data, to_push, 0);
    ++		if (!parent_entry)
    ++			return 0;
      	}
      
    + 	if (entry->commit->object.flags & (COMMON | ADVERTISED)) {
    +@@ negotiator/skipping.c: static const struct object_id *get_rev(struct data *data)
    + 		if (!(commit->object.flags & COMMON) && !entry->ttl)
    + 			to_send = commit;
    + 
    +-		repo_parse_commit(the_repository, commit);
    + 		for (p = commit->parents; p; p = p->next)
    + 			parent_pushed |= push_parent(data, entry, p->item);
    + 
     
      ## t/t5552-skipping-fetch-negotiator.sh ##
     @@ t/t5552-skipping-fetch-negotiator.sh: test_expect_success 'do not send "have" with ancestors of commits that server AC
    @@ t/t5552-skipping-fetch-negotiator.sh: test_expect_success 'do not send "have" wi
     +	test_config -C client fetch.negotiationalgorithm skipping &&
     +	trace_fetch client origin &&
     +	git -C client rev-parse HEAD HEAD~2 >expect &&
    -+	sed -n "s/.*fetch> have //p" trace >haves &&
    -+	sed -n "1,2p" haves >actual &&
    ++	sed -n "s/.*fetch> have //p" trace | head -n 2 >actual &&
     +	test_cmp expect actual
     +'
     +

base-commit: c51408889c3b372814bc20b9431c3b74d0d268eb
-- 
2.56.0.187.g9e9ae442333

Re: [PATCH] negotiator/skipping.c: parse parents before queueing

[Junio C Hamano]

Taylor Blau <ttaylorr@openai.com> writes:

> Thanks, I realized when responding here that we don't even need the
> 'haves' intermediate file, so we can replace this and the above line
> with:
>
>     sed -n "s/.*fetch> have //p" trace | head -n 2 >actual &&

Looks good enough.  Thanks.

I wondered if we can avoid pipes, but the best I could come up with
was this:

    sed -n '/.*fetch> have /{s///p;x;/./q;H;}' trace >actual

which is not exactly readable.  Even folks on process/fork starved
platforms would not appreciate it X-<.

Re: [PATCH v2] negotiator/skipping.c: parse parents before queueing

[Junio C Hamano]

Taylor Blau <ttaylorr@openai.com> writes:

> From: Taylor Blau <ttaylorr@openai.com>
>
> The skipping negotiator sorts its queue by commit date, but callers
> which push commits onto that queue, such as `push_parent()`, can add a
> parent before parsing it. When an unparsed commit enters the queue, its
> date is still zero, so old ref tips may sort ahead of it.
>
> For example, suppose a topic branch is one commit ahead of master.
> Skipping offers the topic tip and skips master's tip. Master's parent
> then waits behind old ref tips. With enough old refs, negotiation can
> end before we offer that recent common ancestor.
>
> Parse each unseen parent before adding it to the queue, so the queue
> uses its actual date. If parsing fails, leave the parent out of the
> queue.
>
> Since the sole caller of `prio_queue_put()` ensures that commits are
> fully parsed before pushing them onto the queue, we can avoid a noop
> call to `repo_parse_commit()` within `get_rev()`.
>
> Note that unlike the default negotiator, the skipping negotiator's
> version of `rev_list_push()` returns a pointer to an 'entry' struct. As
> a consequence, callers must be prepared to handle a NULL return value.
> The caller in `push_parent()` gains a NULL-ness check, and the remaining
> two callers continue to ignore the return value from `rev_list_push()`.
>
> Signed-off-by: Taylor Blau <ttaylorr@openai.com>
> ---
>  negotiator/skipping.c                |  8 +++++--
>  t/t5552-skipping-fetch-negotiator.sh | 32 ++++++++++++++++++++++++++++
>  2 files changed, 38 insertions(+), 2 deletions(-)
>
> diff --git a/negotiator/skipping.c b/negotiator/skipping.c
> index db90fa77b53..0ae5f28d353 100644
> --- a/negotiator/skipping.c
> +++ b/negotiator/skipping.c
> @@ -66,6 +66,9 @@ static struct entry *rev_list_push(struct data *data, struct commit *commit, int
>  	struct entry *entry;
>  	commit->object.flags |= mark | SEEN;
>  
> +	if (repo_parse_commit(the_repository, commit))
> +		return NULL;
> +
>  	CALLOC_ARRAY(entry, 1);
>  	entry->commit = commit;
>  	prio_queue_put(&data->rev_list, entry);
> @@ -125,7 +128,7 @@ static void mark_common(struct data *data, struct commit *seen_commit)
>   * entry has the correct flags and ttl.
>   *
>   * This function returns 1 if an entry was found or created, and 0 otherwise
> - * (because the entry for this commit had already been popped).
> + * (because the commit could not be parsed or its entry had already been popped).
>   */
>  static int push_parent(struct data *data, struct entry *entry,
>  		       struct commit *to_push)
> @@ -152,6 +155,8 @@ static int push_parent(struct data *data, struct entry *entry,
>  		;
>  	} else {
>  		parent_entry = rev_list_push(data, to_push, 0);
> +		if (!parent_entry)
> +			return 0;
>  	}
>  
>  	if (entry->commit->object.flags & (COMMON | ADVERTISED)) {
> @@ -194,7 +199,6 @@ static const struct object_id *get_rev(struct data *data)
>  		if (!(commit->object.flags & COMMON) && !entry->ttl)
>  			to_send = commit;
>  
> -		repo_parse_commit(the_repository, commit);
>  		for (p = commit->parents; p; p = p->next)
>  			parent_pushed |= push_parent(data, entry, p->item);

Moving the parsing to rev_list_push() means that when a commit
cannot be parsed, it is marked as 'SEEN' and NULL is returned.  The
caller, push_parent(), notices this NULL return and naturally
returns without pushing the parent.  However, when the same
unparsable commit is encountered again (perhaps as a parent of
another commit), push_parent() sees that it is already 'SEEN' and
looks for it in the priority queue.  It will fail to find it and
trigger BUG("missing parent in priority queue").

Perhaps rev_list_push() should mark the commit as 'SEEN' only after
repo_parse_commit() succeeds?

While this issue only arises with a corrupt repository or when a
promisor remote goes offline, a failure to parse should not trigger
a BUG(), which should be reserved for programming errors.

Thanks.

Re: [PATCH v2] negotiator/skipping.c: parse parents before queueing

[Taylor Blau]

On Thu, Oct 22, 2026 at 03:34:25PM -0700, Junio C Hamano wrote:
> Perhaps rev_list_push() should mark the commit as 'SEEN' only after
> repo_parse_commit() succeeds?

I considered this but ultimately decided against it, since the default
negotiator does:

    static void rev_list_push(struct negotiation_state *ns,
                              struct commit *commit, int mark)
    {
        if (!(commit->object.flags & mark)) {
            commit->object.flags |= mark;

            if (repo_parse_commit(the_repository, commit))
                return;

    /* ... */

There are various callers of rev_list_push() in the default negotiator,
but all include SEEN in the provided 'mark'.

Thanks,
Taylor

Re: [PATCH] negotiator/skipping.c: parse parents before queueing

[Taylor Blau]

On Thu, Oct 22, 2026 at 02:46:44PM -0700, Junio C Hamano wrote:
> I wondered if we can avoid pipes, but the best I could come up with
> was this:
>
>     sed -n '/.*fetch> have /{s///p;x;/./q;H;}' trace >actual

Yeah, I wondered something similar, but figured that writing it out
would be fairly inscrutable. Seems like it was ;-).

Thanks,
Taylor

Re: [PATCH v2] negotiator/skipping.c: parse parents before queueing

[Junio C Hamano]

Taylor Blau <ttaylorr@openai.com> writes:

> On Thu, Oct 22, 2026 at 03:34:25PM -0700, Junio C Hamano wrote:
>> Perhaps rev_list_push() should mark the commit as 'SEEN' only after
>> repo_parse_commit() succeeds?
>
> I considered this but ultimately decided against it, since the default
> negotiator does:
> ...
> There are various callers of rev_list_push() in the default negotiator,
> but all include SEEN in the provided 'mark'.

It is understandable that we do not want to widen the scope of the
patch by adding a preparatory "fix the existing ones" step, but I do
not think "the existing ones make the same mistake" is particularly
a good excuse to add new one.  Would a hybrid approach to (1) avoid
copying a mistake to new code and (2) document near the new code and/or
in the log message that the difference is deliberate and fixing existing
ones are #leftoverbits and not addressed in this commit?

Re: [PATCH v2] negotiator/skipping.c: parse parents before queueing

[Taylor Blau]

On Fri, Oct 23, 2026 at 07:30:58AM -0700, Junio C Hamano wrote:
> Taylor Blau <ttaylorr@openai.com> writes:
>
> > On Thu, Oct 22, 2026 at 03:34:25PM -0700, Junio C Hamano wrote:
> >> Perhaps rev_list_push() should mark the commit as 'SEEN' only after
> >> repo_parse_commit() succeeds?
> >
> > I considered this but ultimately decided against it, since the default
> > negotiator does:
> > ...
> > There are various callers of rev_list_push() in the default negotiator,
> > but all include SEEN in the provided 'mark'.
>
> It is understandable that we do not want to widen the scope of the
> patch by adding a preparatory "fix the existing ones" step, but I do
> not think "the existing ones make the same mistake" is particularly
> a good excuse to add new one.

I think that's fair. For what it's worth, when writing it my thought
process was "let's be as consistent as possible with the most
battle-tested negotiator" as opposed to "this is broken, let's repeat
the breakage elsewhere".

But looking at it more closely, I think you're right that there is a bug
here in the default negotiator. So...

> Would a hybrid approach to (1) avoid copying a mistake to new code and
> (2) document near the new code and/or in the log message that the
> difference is deliberate and fixing existing ones are #leftoverbits
> and not addressed in this commit?

I think a hybrid approach is fine, though I am happy to fix the default
negotiator alongside this series. I have a patch for it locally, but I'm
happy to send either depending on your preference.

Thanks,
Taylor

Re: [PATCH v2] negotiator/skipping.c: parse parents before queueing

[Junio C Hamano]

Taylor Blau <ttaylorr@openai.com> writes:

> But looking at it more closely, I think you're right that there is a bug
> here in the default negotiator. So...
>
>> Would a hybrid approach to (1) avoid copying a mistake to new code and
>> (2) document near the new code and/or in the log message that the
>> difference is deliberate and fixing existing ones are #leftoverbits
>> and not addressed in this commit?
>
> I think a hybrid approach is fine, though I am happy to fix the default
> negotiator alongside this series. I have a patch for it locally, but I'm
> happy to send either depending on your preference.

If you have a clear grasp of the existing bug and the fix is
straightforward, let's do the fix as part of this series.

Thanks.

[PATCH v3 0/2] negotiator: parse commits before queueing

[Taylor Blau]

This is a reroll of my patches to fix a pair of bugs in the default and
skipping negotiators.

This version fixes the SEEN bookkeeping issue Junio pointed out in v2,
and adds a separate fix for the same mistake in the default negotiator.

The original problem is that the skipping negotiator can queue unparsed
parents with a date of zero. Old ref tips then sort ahead of recent
ancestors, so negotiation can end before we offer a recent common
ancestor. As in v2, the fix parses commits in rev_list_push(), where
their dates are needed to order the queue, and removes the later parse
from get_rev().

But v2 set SEEN before attempting that parse. If parsing failed, another
child sharing the missing parent would look for a queue entry that did
not exist and trigger BUG("missing parent in priority queue"). Both
rev_list_push() implementations set SEEN only after parsing succeeds:

  - The first patch fixes the existing bug in the default negotiator.
    Marking a missing ancestor SEEN can cause mark_common() to decrement
    non_common_revs for a commit that was never queued, ending
    negotiation while other commits remain.

  - The second patch is an updated version of the previous round which
    applies the same fix to the skipping negotiator. Relative to the
    earlier round, it also adds a test where two tips share a missing
    parent and fetching retrieves that parent without hitting the BUG().

Thanks to Junio and Patrick for their review. The range-diff against v2
is below.

Thanks in advance for your review!

Taylor Blau (2):
  negotiator/default.c: mark commits seen only after parsing
  negotiator/skipping.c: parse parents before queueing

 negotiator/default.c                 |  3 +-
 negotiator/skipping.c                |  9 +++-
 t/t5552-skipping-fetch-negotiator.sh | 63 ++++++++++++++++++++++++++++
 t/t5702-protocol-v2.sh               | 31 ++++++++++++++
 4 files changed, 102 insertions(+), 4 deletions(-)

Range-diff against v2:
-:  ----------- > 1:  5a6af916635 negotiator/default.c: mark commits seen only after parsing
1:  c1674625a65 ! 2:  7365a2ab180 negotiator/skipping.c: parse parents before queueing
    @@ Commit message
         then waits behind old ref tips. With enough old refs, negotiation can
         end before we offer that recent common ancestor.
     
    -    Parse each unseen parent before adding it to the queue, so the queue
    -    uses its actual date. If parsing fails, leave the parent out of the
    -    queue.
    +    Parse commits in rev_list_push() before adding them to the queue, so
    +    the queue uses their actual dates. If parsing fails, leave the commit
    +    out of the queue. Move the parsing from get_rev() to the insertion
    +    point, where the date is needed to order the queue.
     
    -    Since the sole caller of `prio_queue_put()` ensures that commits are
    -    fully parsed before pushing them onto the queue, we can avoid a noop
    -    call to `repo_parse_commit()` within `get_rev()`.
    +    Set SEEN only after parsing succeeds, following the default negotiator
    +    after the preceding fix. push_parent() assumes that a commit marked
    +    SEEN but not POPPED has an entry in the queue. Marking an unparseable
    +    parent SEEN would violate that assumption and trigger a BUG() if another
    +    child tried to push the same parent.
     
    -    Note that unlike the default negotiator, the skipping negotiator's
    -    version of `rev_list_push()` returns a pointer to an 'entry' struct. As
    -    a consequence, callers must be prepared to handle a NULL return value.
    -    The caller in `push_parent()` gains a NULL-ness check, and the remaining
    -    two callers continue to ignore the return value from `rev_list_push()`.
    +    Unlike the default negotiator, the skipping negotiator's version of
    +    rev_list_push() returns a pointer to an entry struct. Check for NULL in
    +    push_parent() before using that entry. The other two callers continue
    +    to ignore the return value.
    +
    +    Add tests for the ordering of recent ancestors relative to old ref tips
    +    and for two tips sharing a missing parent. In the latter case, fetching
    +    from a server that has the parent should retrieve it without triggering
    +    the missing-entry BUG().
     
         Signed-off-by: Taylor Blau <ttaylorr@openai.com>
     
      ## negotiator/skipping.c ##
    -@@ negotiator/skipping.c: static struct entry *rev_list_push(struct data *data, struct commit *commit, int
    +@@ negotiator/skipping.c: static int compare(const void *a_, const void *b_, void *data UNUSED)
    + static struct entry *rev_list_push(struct data *data, struct commit *commit, int mark)
    + {
      	struct entry *entry;
    - 	commit->object.flags |= mark | SEEN;
    - 
    ++
     +	if (repo_parse_commit(the_repository, commit))
     +		return NULL;
     +
    + 	commit->object.flags |= mark | SEEN;
    + 
      	CALLOC_ARRAY(entry, 1);
    - 	entry->commit = commit;
    - 	prio_queue_put(&data->rev_list, entry);
     @@ negotiator/skipping.c: static void mark_common(struct data *data, struct commit *seen_commit)
       * entry has the correct flags and ttl.
       *
    @@ t/t5552-skipping-fetch-negotiator.sh: test_expect_success 'do not send "have" wi
     +	sed -n "s/.*fetch> have //p" trace | head -n 2 >actual &&
     +	test_cmp expect actual
     +'
    ++
    ++test_expect_success 'missing parent shared by two tips is not treated as queued' '
    ++	rm -rf server client trace &&
    ++	git init server &&
    ++	test_commit -C server base &&
    ++	parent=$(git -C server rev-parse HEAD) &&
    ++	test_commit -C server to_fetch &&
    ++
    ++	git init client &&
    ++	tree=$(git -C client mktree </dev/null) &&
    ++	# Write the tips directly, bypassing the parent lookup in commit-tree.
    ++	# Both tips name a parent that only the server has.
    ++	for i in 1 2
    ++	do
    ++		cat >commit <<-EOF_COMMIT &&
    ++		tree $tree
    ++		parent $parent
    ++		author A U Thor <author@example.com> 1000000000 +0000
    ++		committer C O Mitter <committer@example.com> 1000000000 +0000
    ++
    ++		tip $i
    ++		EOF_COMMIT
    ++		tip=$(git -C client hash-object -w -t commit --stdin <commit) &&
    ++		git -C client update-ref refs/heads/tip-$i "$tip" || return 1
    ++	done &&
    ++
    ++	test_config -C client fetch.negotiationalgorithm skipping &&
    ++	trace_fetch client "$(pwd)/server" \
    ++		--negotiation-tip=tip-1 --negotiation-tip=tip-2 &&
    ++	git -C client cat-file -e "$parent"
    ++'
     +
      test_done

base-commit: c51408889c3b372814bc20b9431c3b74d0d268eb
-- 
2.56.0.187.g9e9ae442333

[PATCH v3 1/2] negotiator/default.c: mark commits seen only after parsing

[Taylor Blau]

rev_list_push() sets SEEN before parsing a commit, but leaves the commit
out of the queue if parsing fails. This makes SEEN describe an attempted
insertion rather than a commit that was actually queued.

mark_common() relies on SEEN and POPPED to decide whether a newly common
commit contributes to non_common_revs. If a missing parent is marked SEEN
and later reached while acknowledging one of its children, mark_common()
subtracts it even though rev_list_push() never incremented the counter.
This can stop negotiation while other non-common commits remain queued.

Set the requested flags only after parsing succeeds. Successful
insertions are unchanged, and a failed parse no longer marks the commit
as queued. This also lets the skipping negotiator follow the same order
when it starts parsing commits in rev_list_push().

Add a negotiation-only fetch test that fills the first batch with commits
above a missing parent, leaving an older, unrelated tip queued. The ACK
for the first branch must not stop negotiation before the second tip is
sent and acknowledged. Before this fix, the second tip is omitted and
the negotiation-only fetch fails.

Signed-off-by: Taylor Blau <ttaylorr@openai.com>
---
 negotiator/default.c   |  3 +--
 t/t5702-protocol-v2.sh | 31 +++++++++++++++++++++++++++++++
 2 files changed, 32 insertions(+), 2 deletions(-)

diff --git a/negotiator/default.c b/negotiator/default.c
index 19cdf3808cf..32cba7ed8d9 100644
--- a/negotiator/default.c
+++ b/negotiator/default.c
@@ -26,11 +26,10 @@ static void rev_list_push(struct negotiation_state *ns,
 			  struct commit *commit, int mark)
 {
 	if (!(commit->object.flags & mark)) {
-		commit->object.flags |= mark;
-
 		if (repo_parse_commit(the_repository, commit))
 			return;
 
+		commit->object.flags |= mark;
 		prio_queue_put(&ns->rev_list, commit);
 
 		if (!(commit->object.flags & COMMON))
diff --git a/t/t5702-protocol-v2.sh b/t/t5702-protocol-v2.sh
index 7e69ba7f843..b1768cbdbc5 100755
--- a/t/t5702-protocol-v2.sh
+++ b/t/t5702-protocol-v2.sh
@@ -912,6 +912,37 @@ test_expect_success 'file:// --negotiate-only' '
 	test_grep "$COMMON" out
 '
 
+test_expect_success 'negotiate-only continues after ACK with a missing ancestor' '
+	rm -rf server client &&
+	git init server &&
+	test_commit -C server --no-tag b &&
+	git -C server branch b &&
+	git -C server checkout --orphan a &&
+	test_commit -C server --no-tag missing &&
+	missing=$(git -C server rev-parse HEAD) &&
+
+	# Fill the first batch with this branch, leaving b for the next one.
+	for i in $(test_seq 16)
+	do
+		test_commit -C server --no-tag a$i || return 1
+	done &&
+	git clone --no-hardlinks server client &&
+	# Force a parse failure in the client. Keep the parent on the
+	# server so it can acknowledge the branch normally.
+	rm "client/.git/objects/$(test_oid_to_path "$missing")" &&
+
+	# ACKing a must not count the missing ancestor as a queued commit
+	# and stop negotiation before sending b.
+	git -c protocol.version=2 -c core.commitGraph=false \
+		-c fetch.negotiationAlgorithm=consecutive -C client fetch \
+		--negotiate-only --negotiation-tip=a --negotiation-tip=origin/b \
+		origin >out &&
+	git -C client rev-parse a origin/b >tips &&
+	sort tips >expect &&
+	sort out >actual &&
+	test_cmp expect actual
+'
+
 test_expect_success 'file:// --negotiate-only with protocol v0' '
 	SERVER="server" &&
 	URI="file://$(pwd)/server" &&
-- 
2.56.0.187.g9e9ae442333

[PATCH v3 2/2] negotiator/skipping.c: parse parents before queueing

[Taylor Blau]

The skipping negotiator sorts its queue by commit date, but callers
which push commits onto that queue, such as `push_parent()`, can add a
parent before parsing it. When an unparsed commit enters the queue, its
date is still zero, so old ref tips may sort ahead of it.

For example, suppose a topic branch is one commit ahead of master.
Skipping offers the topic tip and skips master's tip. Master's parent
then waits behind old ref tips. With enough old refs, negotiation can
end before we offer that recent common ancestor.

Parse commits in rev_list_push() before adding them to the queue, so
the queue uses their actual dates. If parsing fails, leave the commit
out of the queue. Move the parsing from get_rev() to the insertion
point, where the date is needed to order the queue.

Set SEEN only after parsing succeeds, following the default negotiator
after the preceding fix. push_parent() assumes that a commit marked
SEEN but not POPPED has an entry in the queue. Marking an unparseable
parent SEEN would violate that assumption and trigger a BUG() if another
child tried to push the same parent.

Unlike the default negotiator, the skipping negotiator's version of
rev_list_push() returns a pointer to an entry struct. Check for NULL in
push_parent() before using that entry. The other two callers continue
to ignore the return value.

Add tests for the ordering of recent ancestors relative to old ref tips
and for two tips sharing a missing parent. In the latter case, fetching
from a server that has the parent should retrieve it without triggering
the missing-entry BUG().

Signed-off-by: Taylor Blau <ttaylorr@openai.com>
---
 negotiator/skipping.c                |  9 +++-
 t/t5552-skipping-fetch-negotiator.sh | 63 ++++++++++++++++++++++++++++
 2 files changed, 70 insertions(+), 2 deletions(-)

diff --git a/negotiator/skipping.c b/negotiator/skipping.c
index db90fa77b53..a7c7b8d9e94 100644
--- a/negotiator/skipping.c
+++ b/negotiator/skipping.c
@@ -64,6 +64,10 @@ static int compare(const void *a_, const void *b_, void *data UNUSED)
 static struct entry *rev_list_push(struct data *data, struct commit *commit, int mark)
 {
 	struct entry *entry;
+
+	if (repo_parse_commit(the_repository, commit))
+		return NULL;
+
 	commit->object.flags |= mark | SEEN;
 
 	CALLOC_ARRAY(entry, 1);
@@ -125,7 +129,7 @@ static void mark_common(struct data *data, struct commit *seen_commit)
  * entry has the correct flags and ttl.
  *
  * This function returns 1 if an entry was found or created, and 0 otherwise
- * (because the entry for this commit had already been popped).
+ * (because the commit could not be parsed or its entry had already been popped).
  */
 static int push_parent(struct data *data, struct entry *entry,
 		       struct commit *to_push)
@@ -152,6 +156,8 @@ static int push_parent(struct data *data, struct entry *entry,
 		;
 	} else {
 		parent_entry = rev_list_push(data, to_push, 0);
+		if (!parent_entry)
+			return 0;
 	}
 
 	if (entry->commit->object.flags & (COMMON | ADVERTISED)) {
@@ -194,7 +200,6 @@ static const struct object_id *get_rev(struct data *data)
 		if (!(commit->object.flags & COMMON) && !entry->ttl)
 			to_send = commit;
 
-		repo_parse_commit(the_repository, commit);
 		for (p = commit->parents; p; p = p->next)
 			parent_pushed |= push_parent(data, entry, p->item);
 
diff --git a/t/t5552-skipping-fetch-negotiator.sh b/t/t5552-skipping-fetch-negotiator.sh
index 96e224168eb..0efd2f2ac49 100755
--- a/t/t5552-skipping-fetch-negotiator.sh
+++ b/t/t5552-skipping-fetch-negotiator.sh
@@ -223,4 +223,67 @@ test_expect_success 'do not send "have" with ancestors of commits that server AC
 	have_sent b2.c1 b2.c0
 '
 
+test_expect_success 'recent ancestors are sent before old ref tips' '
+	rm -rf server client trace &&
+	git init server &&
+	test_tick=2000000000 &&
+	test_commit -C server --no-tag base &&
+	test_commit -C server --no-tag parent &&
+	test_commit -C server --no-tag main &&
+	git clone server client &&
+	test_commit -C server --no-tag to_fetch &&
+
+	git -C client checkout -b topic &&
+	test_commit -C client --no-tag topic &&
+
+	# These old tips have known dates, but the recent parent has no ref.
+	# Without parsing parents before queueing them, its date is zero and
+	# all of these tips are sent first, delaying it past the first batch.
+	for i in $(test_seq 32)
+	do
+		old=$(echo "old $i" |
+			GIT_AUTHOR_DATE="1000000000 +0000" \
+			GIT_COMMITTER_DATE="1000000000 +0000" \
+			git -C client commit-tree HEAD^{tree}) &&
+		git -C client update-ref refs/heads/old-$i "$old" || return 1
+	done &&
+
+	test_config -C client fetch.negotiationalgorithm skipping &&
+	trace_fetch client origin &&
+	git -C client rev-parse HEAD HEAD~2 >expect &&
+	sed -n "s/.*fetch> have //p" trace | head -n 2 >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'missing parent shared by two tips is not treated as queued' '
+	rm -rf server client trace &&
+	git init server &&
+	test_commit -C server base &&
+	parent=$(git -C server rev-parse HEAD) &&
+	test_commit -C server to_fetch &&
+
+	git init client &&
+	tree=$(git -C client mktree </dev/null) &&
+	# Write the tips directly, bypassing the parent lookup in commit-tree.
+	# Both tips name a parent that only the server has.
+	for i in 1 2
+	do
+		cat >commit <<-EOF_COMMIT &&
+		tree $tree
+		parent $parent
+		author A U Thor <author@example.com> 1000000000 +0000
+		committer C O Mitter <committer@example.com> 1000000000 +0000
+
+		tip $i
+		EOF_COMMIT
+		tip=$(git -C client hash-object -w -t commit --stdin <commit) &&
+		git -C client update-ref refs/heads/tip-$i "$tip" || return 1
+	done &&
+
+	test_config -C client fetch.negotiationalgorithm skipping &&
+	trace_fetch client "$(pwd)/server" \
+		--negotiation-tip=tip-1 --negotiation-tip=tip-2 &&
+	git -C client cat-file -e "$parent"
+'
+
 test_done
-- 
2.56.0.187.g9e9ae442333