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

[Taylor Blau <ttaylorr@openai.com>]

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