Update bitmap selection throttling to fully span active branches.

Replace the “bitmapCommitRange” parameter that was recently introduced
with two new parameters: “bitmapExcessiveBranchCount” and
“bitmapInactiveBranchAgeInDays”. If the count of branches does not
exceed “bitmapExcessiveBranchCount”, then the current algorithm is kept
for all branches.

If the branch count is excessive, then the commit time for the tip
commit for each branch is used to determine if a branch is “inactive”.
"Active" branches get full commit selection using the existing
algorithm. "Inactive" branches get fewer bitmaps near the branch tips.

Introduce a "contiguousCommitCount" parameter that always enforces that
the N most recent commits in a branch are selected for bitmaps. The
previous nextSelectionDistance() algorithm created anywhere from 1-100
contiguous bitmaps at branch tips.

For example, consider a branch with commits numbering 0-300, with 0
being the most recent commit. If the most recent 200 commits are not
merge commits and the 200th commit was the last one selected,
nextSelectionDistance() returned 100, causing commits 200-101 to be
ignored. Then a window of size 100 was evaluated, searching for merge
commits. Since no merge commits are found, the next commit (commit 0)
was selected, for a total of 1 commit in the topmost 100 commits.

If instead the 250th commit was selected, then by the same logic
commit 50 is selected. At that point nextSelectionDistance() switches to
selecting consecutive commits, so commits 0-50 in the topmost 100
commits are selected. The "contiguousCommitCount" parameter provides
more determinism by always selecting a constant number or topmost
commits.

Add an optimization to break out of the inner loop of selectCommits() if
all of the commits for the current branch have already been found.

When reusing bitmaps from an existing pack, remove unnecessary
populating and clearing of the writeBitmaps/PackBitmapIndexBuilder.

Add comments to PackWriterBitmapPreparer, rename methods and variables
for readability.

Add tests for bitmap selection with and without merge commits and with
excessive branch pruning triggered.

Note: I will follow up with an additional change that exposes the new
parameters through PackConfig.

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

2 files changed, 136 insertions, 62 deletions

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/GcBasicPackingTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/GcBasicPackingTest.java
index 4f6d249c5f..5a91e173bf 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/GcBasicPackingTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/GcBasicPackingTest.java
@@ -44,12 +44,15 @@
 package org.eclipse.jgit.internal.storage.file;
 
 import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
 
 import java.io.File;
 import java.io.IOException;
+import java.util.Arrays;
 import java.util.Collection;
 import java.util.Date;
 import java.util.Iterator;
+import java.util.List;
 
 import org.eclipse.jgit.junit.TestRepository.BranchBuilder;
 import org.eclipse.jgit.revwalk.RevCommit;
@@ -132,7 +135,8 @@ public class GcBasicPackingTest extends GcTestCase {
 	}
 
 	@Theory
-	public void testPackCommitsAndLooseOne(boolean aggressive) throws Exception {
+	public void testPackCommitsAndLooseOne(boolean aggressive)
+			throws Exception {
 		BranchBuilder bb = tr.branch("refs/heads/master");
 		RevCommit first = bb.commit().add("A", "A").add("B", "B").create();
 		bb.commit().add("A", "A2").add("B", "B2").create();
@@ -226,71 +230,139 @@ public class GcBasicPackingTest extends GcTestCase {
 	}
 
 	@Test
-	public void testCommitRangeForBitmaps() throws Exception {
-		BranchBuilder bb1 = tr.branch("refs/heads/master");
-		bb1.commit().message("A1").add("A1", "A1").create();
-		bb1.commit().message("B1").add("B1", "B1").create();
-		bb1.commit().message("C1").add("C1", "C1").create();
-		BranchBuilder bb2 = tr.branch("refs/heads/working");
-		bb2.commit().message("A2").add("A2", "A2").create();
-		bb2.commit().message("B2").add("B2", "B2").create();
-		bb2.commit().message("C2").add("C2", "C2").create();
-
-		// Consider all commits. Since history isn't deep all commits are
-		// selected.
-		configureGcRange(gc, -1);
-		gc.gc();
-		assertEquals(6, gc.getStatistics().numberOfBitmaps);
-
-		// Range==0 means don't examine commit history, create bitmaps only for
-		// branch tips, C1 & C2.
-		configureGcRange(gc, 0);
-		gc.gc();
-		assertEquals(2, gc.getStatistics().numberOfBitmaps);
-
-		// Consider only the most recent commit (C2, which is also a branch
-		// tip).
-		configureGcRange(gc, 1);
-		gc.gc();
-		assertEquals(2, gc.getStatistics().numberOfBitmaps);
-
-		// Consider only the two most recent commits, C2 & B2. C1 gets included
-		// too since it is a branch tip.
-		configureGcRange(gc, 2);
-		gc.gc();
-		assertEquals(3, gc.getStatistics().numberOfBitmaps);
-
-		// Consider C2 & B2 & A2. C1 gets included too since it is a branch tip.
-		configureGcRange(gc, 3);
-		gc.gc();
-		assertEquals(4, gc.getStatistics().numberOfBitmaps);
+	public void testBitmapSpansNoMerges() throws Exception {
+		/*
+		 * Commit counts -> expected bitmap counts for history without merges.
+		 * The top 100 contiguous commits should always have bitmaps, and the
+		 * "recent" bitmaps beyond that are spaced out every 100-200 commits.
+		 * (Starting at 100, the next 100 commits are searched for a merge
+		 * commit. Since one is not found, the spacing between commits is 200.
+		 */
+		int[][] bitmapCounts = { //
+				{ 1, 1 }, { 50, 50 }, { 99, 99 }, { 100, 100 }, { 101, 100 },
+				{ 200, 100 }, { 201, 100 }, { 299, 100 }, { 300, 101 },
+				{ 301, 101 }, { 401, 101 }, { 499, 101 }, { 500, 102 }, };
+		int currentCommits = 0;
+		BranchBuilder bb = tr.branch("refs/heads/main");
+
+		for (int[] counts : bitmapCounts) {
+			int nextCommitCount = counts[0];
+			int expectedBitmapCount = counts[1];
+			assertTrue(nextCommitCount > currentCommits); // programming error
+			for (int i = currentCommits; i < nextCommitCount; i++) {
+				String str = "A" + i;
+				bb.commit().message(str).add(str, str).create();
+			}
+			currentCommits = nextCommitCount;
+
+			gc.setExpireAgeMillis(0); // immediately delete old packs
+			gc.gc();
+			assertEquals(currentCommits * 3, // commit/tree/object
+					gc.getStatistics().numberOfPackedObjects);
+			assertEquals(currentCommits + " commits: ", expectedBitmapCount,
+					gc.getStatistics().numberOfBitmaps);
+		}
+	}
 
-		// Consider C2 & B2 & A2 & C1.
-		configureGcRange(gc, 4);
-		gc.gc();
-		assertEquals(4, gc.getStatistics().numberOfBitmaps);
+	@Test
+	public void testBitmapSpansWithMerges() throws Exception {
+		/*
+		 * Commits that are merged. Since 55 is in the oldest history it is
+		 * never considered. Searching goes from oldest to newest so 115 is the
+		 * first merge commit found. After that the range 116-216 is ignored so
+		 * 175 is never considered.
+		 */
+		List<Integer> merges = Arrays.asList(Integer.valueOf(55),
+				Integer.valueOf(115), Integer.valueOf(175),
+				Integer.valueOf(235));
+		/*
+		 * Commit counts -> expected bitmap counts for history with merges. The
+		 * top 100 contiguous commits should always have bitmaps, and the
+		 * "recent" bitmaps beyond that are spaced out every 100-200 commits.
+		 * Merges in the < 100 range have no effect and merges in the > 100
+		 * range will only be considered for commit counts > 200.
+		 */
+		int[][] bitmapCounts = { //
+				{ 1, 1 }, { 55, 55 }, { 56, 57 }, // +1 bitmap from branch A55
+				{ 99, 100 }, // still +1 branch @55
+				{ 100, 100 }, // 101 commits, only 100 newest
+				{ 116, 100 }, // @55 still in 100 newest bitmaps
+				{ 176, 101 }, // @55 branch tip is not in 100 newest
+				{ 213, 101 }, // 216 commits, @115&@175 in 100 newest
+				{ 214, 102 }, // @55 branch tip, merge @115, @177 in newest
+				{ 236, 102 }, // all 4 merge points in history
+				{ 273, 102 }, // 277 commits, @175&@235 in newest
+				{ 274, 103 }, // @55, @115, merge @175, @235 in newest
+				{ 334, 103 }, // @55,@115,@175, @235 in newest
+				{ 335, 104 }, // @55,@115,@175, merge @235
+				{ 435, 104 }, // @55,@115,@175,@235 tips
+				{ 436, 104 }, // force @236
+		};
+
+		int currentCommits = 0;
+		BranchBuilder bb = tr.branch("refs/heads/main");
+
+		for (int[] counts : bitmapCounts) {
+			int nextCommitCount = counts[0];
+			int expectedBitmapCount = counts[1];
+			assertTrue(nextCommitCount > currentCommits); // programming error
+			for (int i = currentCommits; i < nextCommitCount; i++) {
+				String str = "A" + i;
+				if (!merges.contains(Integer.valueOf(i))) {
+					bb.commit().message(str).add(str, str).create();
+				} else {
+					BranchBuilder bbN = tr.branch("refs/heads/A" + i);
+					bb.commit().message(str).add(str, str)
+							.parent(bbN.commit().create()).create();
+				}
+			}
+			currentCommits = nextCommitCount;
+
+			gc.setExpireAgeMillis(0); // immediately delete old packs
+			gc.gc();
+			assertEquals(currentCommits + " commits: ", expectedBitmapCount,
+					gc.getStatistics().numberOfBitmaps);
+		}
+	}
 
-		// Consider C2 & B2 & A2 & C1 & B1.
-		configureGcRange(gc, 5);
-		gc.gc();
-		assertEquals(5, gc.getStatistics().numberOfBitmaps);
+	@Test
+	public void testBitmapsForExcessiveBranches() throws Exception {
+		int oneDayInSeconds = 60 * 60 * 24;
+
+		// All of branch A is committed on day1
+		BranchBuilder bbA = tr.branch("refs/heads/A");
+		for (int i = 0; i < 1001; i++) {
+			String msg = "A" + i;
+			bbA.commit().message(msg).add(msg, msg).create();
+		}
+		// All of in branch B is committed on day91
+		tr.tick(oneDayInSeconds * 90);
+		BranchBuilder bbB = tr.branch("refs/heads/B");
+		for (int i = 0; i < 1001; i++) {
+			String msg = "B" + i;
+			bbB.commit().message(msg).add(msg, msg).create();
+		}
+		// Create 100 other branches with a single commit
+		for (int i = 0; i < 100; i++) {
+			BranchBuilder bb = tr.branch("refs/heads/N" + i);
+			String msg = "singlecommit" + i;
+			bb.commit().message(msg).add(msg, msg).create();
+		}
+		// now is day92
+		tr.tick(oneDayInSeconds);
 
-		// Consider all six commits.
-		configureGcRange(gc, 6);
-		gc.gc();
-		assertEquals(6, gc.getStatistics().numberOfBitmaps);
+		// Since there are no merges, commits in recent history are selected
+		// every 200 commits.
+		final int commitsForSparseBranch = 1 + (1001 / 200);
+		final int commitsForFullBranch = 100 + (901 / 200);
+		final int commitsForShallowBranches = 100;
 
-		// Input is out of range but should be capped to the total number of
-		// commits.
-		configureGcRange(gc, 1000);
+		// Excessive branch history pruning, one old branch.
 		gc.gc();
-		assertEquals(6, gc.getStatistics().numberOfBitmaps);
-	}
-
-	private void configureGcRange(GC myGc, int range) {
-		PackConfig pconfig = new PackConfig(repo);
-		pconfig.setBitmapCommitRange(range);
-		myGc.setPackConfig(pconfig);
+		assertEquals(
+				commitsForSparseBranch + commitsForFullBranch
+						+ commitsForShallowBranches,
+				gc.getStatistics().numberOfBitmaps);
 	}
 
 	private void configureGc(GC myGc, boolean aggressive) {
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/GcTestCase.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/GcTestCase.java
index a764f0fddd..5abf625489 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/GcTestCase.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/GcTestCase.java
@@ -52,6 +52,7 @@ import org.eclipse.jgit.junit.TestRepository;
 import org.eclipse.jgit.junit.TestRepository.CommitBuilder;
 import org.eclipse.jgit.lib.AnyObjectId;
 import org.eclipse.jgit.revwalk.RevCommit;
+import org.eclipse.jgit.revwalk.RevWalk;
 import org.junit.After;
 import org.junit.Before;
 
@@ -65,7 +66,8 @@ public abstract class GcTestCase extends LocalDiskRepositoryTestCase {
 	public void setUp() throws Exception {
 		super.setUp();
 		repo = createWorkRepository();
-		tr = new TestRepository<FileRepository>((repo));
+		tr = new TestRepository<FileRepository>(repo, new RevWalk(repo),
+				mockSystemReader);
 		gc = new GC(repo);
 	}