negotiator/skipping: skip commits during fetch

Introduce a new negotiation algorithm used during fetch that skips
commits in an effort to find common ancestors faster. The skips grow
similarly to the Fibonacci sequence as the commit walk proceeds further
away from the tips. The skips may cause unnecessary commits to be
included in the packfile, but the negotiation step typically ends more
quickly.

Usage of this algorithm is guarded behind the configuration flag
fetch.negotiationAlgorithm.

Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

1 files changed, 179 insertions, 0 deletions

diff --git a/t/t5552-skipping-fetch-negotiator.sh b/t/t5552-skipping-fetch-negotiator.sh
new file mode 100755
index 0000000000..0a8e0e42ed
--- /dev/null
+++ b/t/t5552-skipping-fetch-negotiator.sh
@@ -0,0 +1,179 @@
+#!/bin/sh
+
+test_description='test skipping fetch negotiator'
+. ./test-lib.sh
+
+have_sent () {
+	while test "$#" -ne 0
+	do
+		grep "fetch> have $(git -C client rev-parse $1)" trace
+		if test $? -ne 0
+		then
+			echo "No have $(git -C client rev-parse $1) ($1)"
+			return 1
+		fi
+		shift
+	done
+}
+
+have_not_sent () {
+	while test "$#" -ne 0
+	do
+		grep "fetch> have $(git -C client rev-parse $1)" trace
+		if test $? -eq 0
+		then
+			return 1
+		fi
+		shift
+	done
+}
+
+test_expect_success 'commits with no parents are sent regardless of skip distance' '
+	git init server &&
+	test_commit -C server to_fetch &&
+
+	git init client &&
+	for i in $(seq 7)
+	do
+		test_commit -C client c$i
+	done &&
+
+	# We send: "c7" (skip 1) "c5" (skip 2) "c2" (skip 4). After that, since
+	# "c1" has no parent, it is still sent as "have" even though it would
+	# normally be skipped.
+	test_config -C client fetch.negotiationalgorithm skipping &&
+	GIT_TRACE_PACKET="$(pwd)/trace" git -C client fetch "$(pwd)/server" &&
+	have_sent c7 c5 c2 c1 &&
+	have_not_sent c6 c4 c3
+'
+
+test_expect_success 'when two skips collide, favor the larger one' '
+	rm -rf server client trace &&
+	git init server &&
+	test_commit -C server to_fetch &&
+
+	git init client &&
+	for i in $(seq 11)
+	do
+		test_commit -C client c$i
+	done &&
+	git -C client checkout c5 &&
+	test_commit -C client c5side &&
+
+	# Before reaching c5, we send "c5side" (skip 1) and "c11" (skip 1) "c9"
+	# (skip 2) "c6" (skip 4). The larger skip (skip 4) takes precedence, so
+	# the next "have" sent will be "c1" (from "c6" skip 4) and not "c4"
+	# (from "c5side" skip 1).
+	test_config -C client fetch.negotiationalgorithm skipping &&
+	GIT_TRACE_PACKET="$(pwd)/trace" git -C client fetch "$(pwd)/server" &&
+	have_sent c5side c11 c9 c6 c1 &&
+	have_not_sent c10 c8 c7 c5 c4 c3 c2
+'
+
+test_expect_success 'use ref advertisement to filter out commits' '
+	rm -rf server client trace &&
+	git init server &&
+	test_commit -C server c1 &&
+	test_commit -C server c2 &&
+	test_commit -C server c3 &&
+	git -C server tag -d c1 c2 c3 &&
+
+	git clone server client &&
+	test_commit -C client c4 &&
+	test_commit -C client c5 &&
+	git -C client checkout c4^^ &&
+	test_commit -C client c2side &&
+
+	git -C server checkout --orphan anotherbranch &&
+	test_commit -C server to_fetch &&
+
+	# The server advertising "c3" (as "refs/heads/master") means that we do
+	# not need to send any ancestors of "c3", but we still need to send "c3"
+	# itself.
+	test_config -C client fetch.negotiationalgorithm skipping &&
+	GIT_TRACE_PACKET="$(pwd)/trace" git -C client fetch origin to_fetch &&
+	have_sent c5 c4^ c2side &&
+	have_not_sent c4 c4^^ c4^^^
+'
+
+test_expect_success 'handle clock skew' '
+	rm -rf server client trace &&
+	git init server &&
+	test_commit -C server to_fetch &&
+
+	git init client &&
+
+	# 2 regular commits
+	test_tick=2000000000 &&
+	test_commit -C client c1 &&
+	test_commit -C client c2 &&
+
+	# 4 old commits
+	test_tick=1000000000 &&
+	git -C client checkout c1 &&
+	test_commit -C client old1 &&
+	test_commit -C client old2 &&
+	test_commit -C client old3 &&
+	test_commit -C client old4 &&
+
+	# "c2" and "c1" are popped first, then "old4" to "old1". "old1" would
+	# normally be skipped, but is treated as a commit without a parent here
+	# and sent, because (due to clock skew) its only parent has already been
+	# popped off the priority queue.
+	test_config -C client fetch.negotiationalgorithm skipping &&
+	GIT_TRACE_PACKET="$(pwd)/trace" git -C client fetch "$(pwd)/server" &&
+	have_sent c2 c1 old4 old2 old1 &&
+	have_not_sent old3
+'
+
+test_expect_success 'do not send "have" with ancestors of commits that server ACKed' '
+	rm -rf server client trace &&
+	git init server &&
+	test_commit -C server to_fetch &&
+
+	git init client &&
+	for i in $(seq 8)
+	do
+		git -C client checkout --orphan b$i &&
+		test_commit -C client b$i.c0
+	done &&
+	for j in $(seq 19)
+	do
+		for i in $(seq 8)
+		do
+			git -C client checkout b$i &&
+			test_commit -C client b$i.c$j
+		done
+	done &&
+
+	# Copy this branch over to the server and add a commit on it so that it
+	# is reachable but not advertised.
+	git -C server fetch --no-tags "$(pwd)/client" b1:refs/heads/b1 &&
+	git -C server checkout b1 &&
+	test_commit -C server commit-on-b1 &&
+
+	test_config -C client fetch.negotiationalgorithm skipping &&
+	GIT_TRACE_PACKET="$(pwd)/trace" git -C client fetch "$(pwd)/server" to_fetch &&
+	grep "  fetch" trace &&
+
+	# fetch-pack sends 2 requests each containing 16 "have" lines before
+	# processing the first response. In these 2 requests, 4 commits from
+	# each branch are sent. Just check the first branch.
+	have_sent b1.c19 b1.c17 b1.c14 b1.c9 &&
+	have_not_sent b1.c18 b1.c16 b1.c15 b1.c13 b1.c12 b1.c11 b1.c10 &&
+
+	# While fetch-pack is processing the first response, it should read that
+	# the server ACKs b1.c19 and b1.c17.
+	grep "fetch< ACK $(git -C client rev-parse b1.c19) common" trace &&
+	grep "fetch< ACK $(git -C client rev-parse b1.c17) common" trace &&
+
+	# fetch-pack should thus not send any more commits in the b1 branch, but
+	# should still send the others (in this test, just check b2).
+	for i in $(seq 0 8)
+	do
+		have_not_sent b1.c$i
+	done &&
+	have_sent b2.c1 b2.c0
+'
+
+test_done