Add a minimum negotiation feature for fetch

Android an Chrome have several repos with >300k refs. We sometimes see
negotiations of >100k rounds. This change provides a "minimal negotiation"
feature on the client side that limits how many "have" lines the client
sends. The client extracts the current SHA-1 values for the refs in its
wants set, and terminates negotiation early when all of those values have
been sent as haves. If a new branch is being fetched then that set will
be empty and the client will terminate after current default minimum
of two rounds.

This feature is gated behind a "fetch.useminimalnegotiation" configuration
flag, which defaults to false.

Change-Id: Ib12b095cac76a59da6e8f72773c4129e3b32ff2b
Signed-off-by: Terry Parker <tparker@google.com>

1 files changed, 82 insertions, 3 deletions

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/transport/TestProtocolTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/transport/TestProtocolTest.java
index b926e482f6..86c92bb528 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/transport/TestProtocolTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/transport/TestProtocolTest.java
@@ -60,6 +60,9 @@ import org.eclipse.jgit.internal.storage.dfs.InMemoryRepository;
 import org.eclipse.jgit.junit.TestRepository;
 import org.eclipse.jgit.lib.ObjectId;
 import org.eclipse.jgit.lib.Repository;
+import org.eclipse.jgit.revwalk.RevCommit;
+import org.eclipse.jgit.storage.pack.PackStatistics;
+import org.eclipse.jgit.transport.BasePackFetchConnection.FetchConfig;
 import org.eclipse.jgit.transport.resolver.ReceivePackFactory;
 import org.eclipse.jgit.transport.resolver.ServiceNotAuthorizedException;
 import org.eclipse.jgit.transport.resolver.UploadPackFactory;
@@ -70,6 +73,11 @@ import org.junit.Test;
 public class TestProtocolTest {
 	private static final RefSpec HEADS = new RefSpec("+refs/heads/*:refs/heads/*");
 
+	private static final RefSpec MASTER = new RefSpec(
+			"+refs/heads/master:refs/heads/master");
+
+	private static final int HAVES_PER_ROUND = 32;
+
 	private static class User {
 		private final String name;
 
@@ -81,7 +89,14 @@ public class TestProtocolTest {
 	private static class DefaultUpload implements UploadPackFactory<User> {
 		@Override
 		public UploadPack create(User req, Repository db) {
-			return new UploadPack(db);
+			UploadPack up = new UploadPack(db);
+			up.setPostUploadHook(new PostUploadHook() {
+				@Override
+				public void onPostUpload(PackStatistics stats) {
+					havesCount = stats.getHaves();
+				}
+			});
+			return up;
 		}
 	}
 
@@ -92,6 +107,8 @@ public class TestProtocolTest {
 		}
 	}
 
+	private static long havesCount;
+
 	private List<TransportProtocol> protos;
 	private TestRepository<InMemoryRepository> local;
 	private TestRepository<InMemoryRepository> remote;
@@ -147,6 +164,68 @@ public class TestProtocolTest {
 	}
 
 	@Test
+	public void testFullNegotiation() throws Exception {
+		TestProtocol<User> proto = registerDefault();
+		URIish uri = proto.register(new User("user"), remote.getRepository());
+
+		// Enough local branches to cause 10 rounds of negotiation,
+		// and a unique remote master branch commit with a later timestamp.
+		for (int i = 0; i < 10 * HAVES_PER_ROUND; i++) {
+			local.branch("local-branch-" + i).commit().create();
+		}
+		remote.tick(11 * HAVES_PER_ROUND);
+		RevCommit master = remote.branch("master").commit()
+				.add("readme.txt", "unique commit").create();
+
+		try (Git git = new Git(local.getRepository())) {
+			assertNull(local.getRepository().exactRef("refs/heads/master"));
+			git.fetch().setRemote(uri.toString()).setRefSpecs(MASTER).call();
+			assertEquals(master, local.getRepository()
+					.exactRef("refs/heads/master").getObjectId());
+			assertEquals(10 * HAVES_PER_ROUND, havesCount);
+		}
+	}
+
+	@Test
+	public void testMinimalNegotiation() throws Exception {
+		TestProtocol<User> proto = registerDefault();
+		URIish uri = proto.register(new User("user"), remote.getRepository());
+
+		// Enough local branches to cause 10 rounds of negotiation,
+		// and a unique remote master branch commit with a later timestamp.
+		for (int i = 0; i < 10 * HAVES_PER_ROUND; i++) {
+			local.branch("local-branch-" + i).commit().create();
+		}
+		remote.tick(11 * HAVES_PER_ROUND);
+		RevCommit master = remote.branch("master").commit()
+				.add("readme.txt", "unique commit").create();
+
+		TestProtocol.setFetchConfig(new FetchConfig(true, true));
+		try (Git git = new Git(local.getRepository())) {
+			assertNull(local.getRepository().exactRef("refs/heads/master"));
+			git.fetch().setRemote(uri.toString()).setRefSpecs(MASTER).call();
+			assertEquals(master, local.getRepository()
+					.exactRef("refs/heads/master").getObjectId());
+			assertTrue(havesCount <= 2 * HAVES_PER_ROUND);
+
+			// Update the remote master and add local branches for 5 more rounds
+			// of negotiation, where the local branch commits have newer
+			// timestamps. Negotiation should send 5 rounds for those newer
+			// branches before getting to the round that sends its stale version
+			// of master.
+			master = remote.branch("master").commit().parent(master).create();
+			local.tick(2 * HAVES_PER_ROUND);
+			for (int i = 0; i < 5 * HAVES_PER_ROUND; i++) {
+				local.branch("local-" + i).commit().create();
+			}
+			git.fetch().setRemote(uri.toString()).setRefSpecs(MASTER).call();
+			assertEquals(master, local.getRepository()
+					.exactRef("refs/heads/master").getObjectId());
+			assertEquals(6 * HAVES_PER_ROUND, havesCount);
+		}
+	}
+
+	@Test
 	public void testUploadPackFactory() throws Exception {
 		ObjectId master = remote.branch("master").commit().create();
 
@@ -171,7 +250,7 @@ public class TestProtocolTest {
 			try {
 				git.fetch()
 						.setRemote(user1Uri.toString())
-						.setRefSpecs(HEADS)
+						.setRefSpecs(MASTER)
 						.call();
 			} catch (InvalidRemoteException expected) {
 				// Expected.
@@ -181,7 +260,7 @@ public class TestProtocolTest {
 
 			git.fetch()
 					.setRemote(user2Uri.toString())
-					.setRefSpecs(HEADS)
+					.setRefSpecs(MASTER)
 					.call();
 			assertEquals(1, rejected.get());
 			assertEquals(master,