ReceivePack: adding IterativeConnectivityChecker

Introduce an IterativeConnectivityChecker which runs a connectivity
check with a filtered set of references, and falls back to using the
full set of advertised references.

It uses references during first check attempt:
- References that are ancestors of an incoming commits (e.g., pushing
a commit onto an existing branch or pushing a new branch based on
another branch)
- Additional list of references we know client can be interested in
(e.g. list of open changes for Gerrit)

We tested it inside Google and it improves connectivity for certain
topologies. For example connectivity counts for
chromium.googlesource.com/chromium/src:

percentile_50: 1923 (was: 22777)
percentile_90: 23272 (was: 353003)
percentile_99: 345522 (was: 353435)

This saved ~2 seconds on every push to this repository.

Signed-off-by: Demetr Starshov <dstarshov@google.com>
Change-Id: I6543c2e10ed04622ca795b195665133e690d3b10

2 files changed, 259 insertions, 0 deletions

diff --git a/org.eclipse.jgit.test/META-INF/MANIFEST.MF b/org.eclipse.jgit.test/META-INF/MANIFEST.MF
index 6bd06e11b6..eda4505264 100644
--- a/org.eclipse.jgit.test/META-INF/MANIFEST.MF
+++ b/org.eclipse.jgit.test/META-INF/MANIFEST.MF
@@ -42,6 +42,7 @@ Import-Package: com.googlecode.javaewah;version="[1.1.6,2.0.0)",
  org.eclipse.jgit.internal.storage.pack;version="[5.8.0,5.9.0)",
  org.eclipse.jgit.internal.storage.reftable;version="[5.8.0,5.9.0)",
  org.eclipse.jgit.internal.storage.reftree;version="[5.8.0,5.9.0)",
+ org.eclipse.jgit.internal.transport.connectivity;version="[5.8.0,5.9.0)",
  org.eclipse.jgit.internal.transport.http;version="[5.8.0,5.9.0)",
  org.eclipse.jgit.internal.transport.parser;version="[5.8.0,5.9.0)",
  org.eclipse.jgit.junit;version="[5.8.0,5.9.0)",
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/transport/connectivity/IterativeConnectivityCheckerTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/transport/connectivity/IterativeConnectivityCheckerTest.java
new file mode 100644
index 0000000000..e75dd22591
--- /dev/null
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/transport/connectivity/IterativeConnectivityCheckerTest.java
@@ -0,0 +1,258 @@
+/*
+ * Copyright (c) 2019, Google LLC  and others
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Distribution License v. 1.0 which is available at
+ * http://www.eclipse.org/org/documents/edl-v10.php.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+
+package org.eclipse.jgit.internal.transport.connectivity;
+
+import static org.mockito.Mockito.doThrow;
+import static org.mockito.Mockito.verify;
+
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Set;
+
+import org.eclipse.jgit.errors.MissingObjectException;
+import org.eclipse.jgit.internal.storage.dfs.DfsRepositoryDescription;
+import org.eclipse.jgit.internal.storage.dfs.InMemoryRepository;
+import org.eclipse.jgit.junit.TestRepository;
+import org.eclipse.jgit.lib.Constants;
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.ProgressMonitor;
+import org.eclipse.jgit.revwalk.RevCommit;
+import org.eclipse.jgit.transport.PackParser;
+import org.eclipse.jgit.transport.ReceiveCommand;
+import org.eclipse.jgit.transport.ConnectivityChecker;
+import org.eclipse.jgit.transport.ConnectivityChecker.ConnectivityCheckInfo;
+import org.junit.Before;
+import org.junit.Rule;
+import org.junit.Test;
+import org.mockito.Mock;
+import org.mockito.junit.MockitoJUnit;
+import org.mockito.junit.MockitoRule;
+
+public class IterativeConnectivityCheckerTest {
+	@Rule
+	public MockitoRule rule = MockitoJUnit.rule();
+
+	private ObjectId branchHeadObjectId;
+
+	private ObjectId openRewiewObjectId;
+
+	private ObjectId newCommitObjectId;
+	private ObjectId otherHaveObjectId = ObjectId
+			.fromString("DEADBEEFDEADBEEFDEADBEEFDEADBEEFDEADBEEF");
+
+	private Set<ObjectId> advertisedHaves;
+
+	@Mock
+	private ConnectivityChecker connectivityCheckerDelegate;
+
+	@Mock
+	private ProgressMonitor pm;
+
+	@Mock
+	private PackParser parser;
+
+	private RevCommit branchHeadCommitObject;
+	private RevCommit openReviewCommitObject;
+	private RevCommit newCommitObject;
+
+	private ConnectivityCheckInfo connectivityCheckInfo;
+	private IterativeConnectivityChecker connectivityChecker;
+
+	private TestRepository tr;
+
+	@Before
+	public void setUp() throws Exception {
+		tr = new TestRepository<>(
+				new InMemoryRepository(new DfsRepositoryDescription("test")));
+		connectivityChecker = new IterativeConnectivityChecker(
+				connectivityCheckerDelegate);
+		connectivityCheckInfo = new ConnectivityCheckInfo();
+		connectivityCheckInfo.setParser(parser);
+		connectivityCheckInfo.setRepository(tr.getRepository());
+		connectivityCheckInfo.setWalk(tr.getRevWalk());
+
+		branchHeadCommitObject = tr.commit().create();
+		branchHeadObjectId = branchHeadCommitObject.getId();
+
+		openReviewCommitObject = tr.commit().create();
+		openRewiewObjectId = openReviewCommitObject.getId();
+
+		advertisedHaves = wrap(branchHeadObjectId, openRewiewObjectId,
+				otherHaveObjectId);
+	}
+
+	@Test
+	public void testSuccessfulNewBranchBasedOnOld() throws Exception {
+		createNewCommit(branchHeadCommitObject);
+		connectivityCheckInfo.setCommands(
+				Collections.singletonList(createNewBrachCommand()));
+
+		connectivityChecker.checkConnectivity(connectivityCheckInfo,
+				advertisedHaves, pm);
+
+		verify(connectivityCheckerDelegate).checkConnectivity(
+				connectivityCheckInfo,
+				wrap(branchHeadObjectId /* as direct parent */),
+				pm);
+	}
+
+	@Test
+	public void testSuccessfulNewBranchBasedOnOldWithTip() throws Exception {
+		createNewCommit(branchHeadCommitObject);
+		connectivityCheckInfo.setCommands(
+				Collections.singletonList(createNewBrachCommand()));
+
+		connectivityChecker.setForcedHaves(wrap(openRewiewObjectId));
+
+		connectivityChecker.checkConnectivity(connectivityCheckInfo,
+				advertisedHaves, pm);
+
+		verify(connectivityCheckerDelegate).checkConnectivity(
+				connectivityCheckInfo,
+				wrap(branchHeadObjectId /* as direct parent */,
+						openRewiewObjectId),
+				pm);
+	}
+
+	@Test
+	public void testSuccessfulNewBranchMerge() throws Exception {
+		createNewCommit(branchHeadCommitObject, openReviewCommitObject);
+		connectivityCheckInfo.setCommands(
+				Collections.singletonList(createNewBrachCommand()));
+
+		connectivityChecker.checkConnectivity(connectivityCheckInfo,
+				advertisedHaves, pm);
+
+		verify(connectivityCheckerDelegate).checkConnectivity(
+				connectivityCheckInfo,
+				wrap(branchHeadObjectId /* as direct parent */,
+						openRewiewObjectId),
+				pm);
+	}
+
+	@Test
+	public void testSuccessfulNewBranchBasedOnNewWithTip() throws Exception {
+		createNewCommit();
+		connectivityCheckInfo.setCommands(
+				Collections.singletonList(createNewBrachCommand()));
+
+		connectivityChecker.setForcedHaves(wrap(openRewiewObjectId));
+
+		connectivityChecker.checkConnectivity(connectivityCheckInfo,
+				advertisedHaves, pm);
+
+		verify(connectivityCheckerDelegate).checkConnectivity(
+				connectivityCheckInfo, wrap(openRewiewObjectId), pm);
+	}
+
+	@Test
+	public void testSuccessfulPushOldBranch() throws Exception {
+		createNewCommit(branchHeadCommitObject);
+		connectivityCheckInfo.setCommands(
+				Collections.singletonList(pushOldBranchCommand()));
+
+		connectivityChecker.checkConnectivity(connectivityCheckInfo,
+				advertisedHaves, pm);
+
+		verify(connectivityCheckerDelegate).checkConnectivity(
+				connectivityCheckInfo, wrap(branchHeadObjectId /* as direct parent */),
+				pm);
+	}
+
+	@Test
+	public void testSuccessfulPushOldBranchMergeCommit() throws Exception {
+		createNewCommit(branchHeadCommitObject, openReviewCommitObject);
+		connectivityCheckInfo.setCommands(
+				Collections.singletonList(pushOldBranchCommand()));
+
+		connectivityChecker.checkConnectivity(connectivityCheckInfo,
+				advertisedHaves, pm);
+
+		verify(connectivityCheckerDelegate).checkConnectivity(
+				connectivityCheckInfo,
+				wrap(branchHeadObjectId /* as direct parent */,
+						openRewiewObjectId),
+				pm);
+	}
+
+
+	@Test
+	public void testNoChecksIfCantFindSubset() throws Exception {
+		createNewCommit();
+		connectivityCheckInfo.setCommands(
+				Collections.singletonList(createNewBrachCommand()));
+
+		connectivityChecker.checkConnectivity(connectivityCheckInfo,
+				advertisedHaves, pm);
+
+		verify(connectivityCheckerDelegate)
+				.checkConnectivity(connectivityCheckInfo, advertisedHaves, pm);
+	}
+
+	@Test
+	public void testReiterateInCaseNotSuccessful() throws Exception {
+		createNewCommit(branchHeadCommitObject);
+		connectivityCheckInfo.setCommands(
+				Collections.singletonList(createNewBrachCommand()));
+
+		doThrow(new MissingObjectException(branchHeadCommitObject,
+				Constants.OBJ_COMMIT)).when(connectivityCheckerDelegate)
+						.checkConnectivity(connectivityCheckInfo,
+								wrap(branchHeadObjectId /* as direct parent */), pm);
+
+		connectivityChecker.checkConnectivity(connectivityCheckInfo,
+				advertisedHaves, pm);
+
+		verify(connectivityCheckerDelegate)
+				.checkConnectivity(connectivityCheckInfo, advertisedHaves, pm);
+	}
+
+	@Test
+	public void testDependOnGrandparent() throws Exception {
+		RevCommit grandparent = tr.commit(new RevCommit[] {});
+		RevCommit parent = tr.commit(grandparent);
+		createNewCommit(parent);
+
+		branchHeadCommitObject = tr.commit(grandparent);
+		branchHeadObjectId = branchHeadCommitObject.getId();
+		tr.getRevWalk().dispose();
+
+		connectivityCheckInfo.setCommands(
+				Collections.singletonList(createNewBrachCommand()));
+
+		connectivityChecker.checkConnectivity(connectivityCheckInfo,
+				advertisedHaves, pm);
+
+		verify(connectivityCheckerDelegate)
+				.checkConnectivity(connectivityCheckInfo, advertisedHaves, pm);
+	}
+
+	private static Set<ObjectId> wrap(ObjectId... objectIds) {
+		return new HashSet<>(Arrays.asList(objectIds));
+	}
+
+	private ReceiveCommand createNewBrachCommand() {
+		return new ReceiveCommand(ObjectId.zeroId(), newCommitObjectId,
+				"totally/a/new/branch");
+	}
+
+	private ReceiveCommand pushOldBranchCommand() {
+		return new ReceiveCommand(branchHeadObjectId, newCommitObjectId,
+				"push/to/an/old/branch");
+	}
+
+	private void createNewCommit(RevCommit... parents) throws Exception {
+		newCommitObject = tr.commit(parents);
+		newCommitObjectId = newCommitObject.getId();
+	}
+
+}