PackWriterBitmapPreparer: Set limit on excessive branch count

If there are too many branches then the bitmap
indexing selects only the tip commits of the least active
branches to reduce the amount of bitmaps to load on request.
This can still be a problem if the number of inactive branches
rival or exceed the total number of commits selected
for the active branches.

Limit the number of branches that receive only-tip bitmaps.
This reduces the memory pressure of loading all the bitmaps,
and allows us to model the size of the bitmap index without
considering the number of branches.

Bitmaps are generated for branches in order of most recent commit,
and follow these rules:

* The first {@code DEFAULT_BITMAP_EXCESSIVE_BRANCH_COUNT} most active
  branches have full bitmap coverage.
* The {@code DEFAULT_BITMAP_EXCESSIVE_BRANCH_COUNT} to {@code
  DEFAULT_BITMAP_EXCESSIVE_BRANCH_TIP_COUNT} most active branches have
  only the tip commit covered.
* The remaining branches have no bitmap coverage.

To prevent effecting existing repositories, the default value is set
at Integer.MAX_VALUE.

Change-Id: I7cc53c898cdc04953b95669be0b069543e10c6f8

3 files changed, 88 insertions, 5 deletions

diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriterBitmapPreparer.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriterBitmapPreparer.java
index 8b5cea7af6..0c67b45344 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriterBitmapPreparer.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriterBitmapPreparer.java
@@ -28,16 +28,16 @@ import org.eclipse.jgit.errors.MissingObjectException;
 import org.eclipse.jgit.internal.JGitText;
 import org.eclipse.jgit.internal.revwalk.AddUnseenToBitmapFilter;
 import org.eclipse.jgit.internal.storage.file.BitmapIndexImpl;
-import org.eclipse.jgit.internal.storage.file.BitmapIndexImpl.CompressedBitmap;
 import org.eclipse.jgit.internal.storage.file.PackBitmapIndex;
 import org.eclipse.jgit.internal.storage.file.PackBitmapIndexBuilder;
 import org.eclipse.jgit.internal.storage.file.PackBitmapIndexRemapper;
+import org.eclipse.jgit.internal.storage.file.BitmapIndexImpl.CompressedBitmap;
 import org.eclipse.jgit.lib.AnyObjectId;
-import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder;
 import org.eclipse.jgit.lib.Constants;
 import org.eclipse.jgit.lib.ObjectId;
 import org.eclipse.jgit.lib.ObjectReader;
 import org.eclipse.jgit.lib.ProgressMonitor;
+import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder;
 import org.eclipse.jgit.revwalk.BitmapWalker;
 import org.eclipse.jgit.revwalk.ObjectWalk;
 import org.eclipse.jgit.revwalk.RevCommit;
@@ -77,6 +77,7 @@ class PackWriterBitmapPreparer {
 	private final int recentCommitSpan;
 	private final int distantCommitSpan;
 	private final int excessiveBranchCount;
+	private final int excessiveBranchTipCount;
 	private final long inactiveBranchTimestamp;
 
 	PackWriterBitmapPreparer(ObjectReader reader,
@@ -96,6 +97,8 @@ class PackWriterBitmapPreparer {
 		this.recentCommitSpan = config.getBitmapRecentCommitSpan();
 		this.distantCommitSpan = config.getBitmapDistantCommitSpan();
 		this.excessiveBranchCount = config.getBitmapExcessiveBranchCount();
+		this.excessiveBranchTipCount = Math.max(excessiveBranchCount,
+				config.getBitmapExcessiveBranchTipCount());
 		long now = SystemReader.getInstance().getCurrentTime();
 		long ageInSeconds = (long) config.getBitmapInactiveBranchAgeInDays()
 				* DAY_IN_SECONDS;
@@ -163,11 +166,14 @@ class PackWriterBitmapPreparer {
 			rw2.setRetainBody(false);
 			rw2.setRevFilter(new NotInBitmapFilter(seen));
 
+			int maxBranches = Math.min(excessiveBranchTipCount,
+					selectionHelper.newWantsByNewest.size());
 			// For each branch, do a revwalk to enumerate its commits. Exclude
 			// both reused commits and any commits seen in a previous branch.
 			// Then iterate through all new commits from oldest to newest,
 			// selecting well-spaced commits in this branch.
-			for (RevCommit rc : selectionHelper.newWantsByNewest) {
+			for (RevCommit rc : selectionHelper.newWantsByNewest.subList(0,
+					maxBranches)) {
 				BitmapBuilder tipBitmap = commitBitmapIndex.newBitmapBuilder();
 				rw2.markStart((RevCommit) rw2.peel(rw2.parseAny(rc)));
 				RevCommit rc2;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/ConfigConstants.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ConfigConstants.java
index c7b4e45697..76b4d7195e 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/ConfigConstants.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ConfigConstants.java
@@ -751,6 +751,13 @@ public final class ConfigConstants {
 	public static final String CONFIG_KEY_BITMAP_EXCESSIVE_BRANCH_COUNT = "bitmapexcessivebranchcount";
 
 	/**
+	 * The "pack.bitmapExcessiveBranchTipCount" key
+	 *
+	 * @since 6.9
+	 */
+	public static final String CONFIG_KEY_BITMAP_EXCESSIVE_BRANCH_TIP_COUNT = "bitmapexcessivebranchtipcount";
+
+	/**
 	 * The "pack.bitmapExcludedRefsPrefixes" key
 	 * @since 5.13.2
 	 */
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackConfig.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackConfig.java
index d524524612..8373d6809a 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackConfig.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackConfig.java
@@ -16,6 +16,7 @@ import static org.eclipse.jgit.lib.ConfigConstants.CONFIG_KEY_BIGFILE_THRESHOLD;
 import static org.eclipse.jgit.lib.ConfigConstants.CONFIG_KEY_BITMAP_CONTIGUOUS_COMMIT_COUNT;
 import static org.eclipse.jgit.lib.ConfigConstants.CONFIG_KEY_BITMAP_DISTANT_COMMIT_SPAN;
 import static org.eclipse.jgit.lib.ConfigConstants.CONFIG_KEY_BITMAP_EXCESSIVE_BRANCH_COUNT;
+import static org.eclipse.jgit.lib.ConfigConstants.CONFIG_KEY_BITMAP_EXCESSIVE_BRANCH_TIP_COUNT;
 import static org.eclipse.jgit.lib.ConfigConstants.CONFIG_KEY_BITMAP_EXCLUDED_REFS_PREFIXES;
 import static org.eclipse.jgit.lib.ConfigConstants.CONFIG_KEY_BITMAP_INACTIVE_BRANCH_AGE_INDAYS;
 import static org.eclipse.jgit.lib.ConfigConstants.CONFIG_KEY_BITMAP_RECENT_COMMIT_COUNT;
@@ -240,6 +241,17 @@ public class PackConfig {
 	public static final int DEFAULT_BITMAP_EXCESSIVE_BRANCH_COUNT = 100;
 
 	/**
+	 * Default maxium count of branches to create tip bitmaps for. If the number
+	 * of branches exceeds this, then tip bitmaps will only be created for the
+	 * most recently active branches. Branches exceeding this count will receive
+	 * 0 bitmaps: {@value #DEFAULT_BITMAP_EXCESSIVE_BRANCH_TIP_COUNT}
+	 *
+	 * @see #setBitmapExcessiveBranchTipCount(int)
+	 * @since 6.9
+	 */
+	public static final int DEFAULT_BITMAP_EXCESSIVE_BRANCH_TIP_COUNT = Integer.MAX_VALUE;
+
+	/**
 	 * Default age at which a branch is considered inactive. Age is taken as the
 	 * number of days ago that the most recent commit was made to a branch. Only
 	 * affects bitmap processing if bitmaps are enabled and the
@@ -330,6 +342,8 @@ public class PackConfig {
 
 	private int bitmapExcessiveBranchCount = DEFAULT_BITMAP_EXCESSIVE_BRANCH_COUNT;
 
+	private int bitmapExcessiveBranchTipCount = DEFAULT_BITMAP_EXCESSIVE_BRANCH_TIP_COUNT;
+
 	private int bitmapInactiveBranchAgeInDays = DEFAULT_BITMAP_INACTIVE_BRANCH_AGE_IN_DAYS;
 
 	private String[] bitmapExcludedRefsPrefixes = DEFAULT_BITMAP_EXCLUDED_REFS_PREFIXES;
@@ -1190,7 +1204,8 @@ public class PackConfig {
 	 * a repository exceeds this number and bitmaps are enabled, "inactive"
 	 * branches will have fewer bitmaps than "active" branches.
 	 *
-	 * Default setting: {@value #DEFAULT_BITMAP_EXCESSIVE_BRANCH_COUNT}
+	 * Default setting: {@value #DEFAULT_BITMAP_EXCESSIVE_BRANCH_COUNT}. See
+	 * also {@link #getBitmapExcessiveBranchTipCount}.
 	 *
 	 * @return the count of branches deemed "excessive"
 	 * @since 4.2
@@ -1204,7 +1219,8 @@ public class PackConfig {
 	 * a repository exceeds this number and bitmaps are enabled, "inactive"
 	 * branches will have fewer bitmaps than "active" branches.
 	 *
-	 * Default setting: {@value #DEFAULT_BITMAP_EXCESSIVE_BRANCH_COUNT}
+	 * Default setting: {@value #DEFAULT_BITMAP_EXCESSIVE_BRANCH_COUNT}. See
+	 * also {@link #setBitmapExcessiveBranchTipCount(int)}.
 	 *
 	 * @param count
 	 *            the count of branches deemed "excessive"
@@ -1215,6 +1231,57 @@ public class PackConfig {
 	}
 
 	/**
+	 * Get the count of branches deemed "excessive". If the count of branches in
+	 * a repository exceeds this number and bitmaps are enabled, branches
+	 * exceeding this count will have no bitmaps selected. Branches are indexed
+	 * most recent first.
+	 *
+	 * <li>The first {@code DEFAULT_BITMAP_EXCESSIVE_BRANCH_COUNT} most active
+	 * branches have full bitmap coverage.
+	 * <li>The {@code DEFAULT_BITMAP_EXCESSIVE_BRANCH_COUNT} to {@code
+	 * 	  DEFAULT_BITMAP_EXCESSIVE_BRANCH_TIP_COUNT} most active branches have
+	 * only the tip commit covered.
+	 * <li>The remaining branches have no bitmap coverage.
+	 *
+	 * If {@link #getBitmapExcessiveBranchCount()} is greater, then that value
+	 * will override this value.
+	 *
+	 * Default setting: {@value #DEFAULT_BITMAP_EXCESSIVE_BRANCH_TIP_COUNT}
+	 *
+	 * @return the count of branch tips deemed "excessive"
+	 * @since 6.9
+	 */
+	public int getBitmapExcessiveBranchTipCount() {
+		return bitmapExcessiveBranchTipCount;
+	}
+
+	/**
+	 * Get the count of branches deemed "excessive". If the count of branches in
+	 * a repository exceeds this number and bitmaps are enabled, branches
+	 * exceeding this count will have no bitmaps selected. Branches are indexed
+	 * most recent first.
+	 *
+	 * <li>The first {@code DEFAULT_BITMAP_EXCESSIVE_BRANCH_COUNT} most active
+	 * branches have full bitmap coverage.
+	 * <li>The {@code DEFAULT_BITMAP_EXCESSIVE_BRANCH_COUNT} to {@code
+	 * 	  DEFAULT_BITMAP_EXCESSIVE_BRANCH_TIP_COUNT} most active branches have
+	 * only the tip commit covered.
+	 * <li>The remaining branches have no bitmap coverage.
+	 *
+	 * If {@link #getBitmapExcessiveBranchCount()} is greater, then that value
+	 * will override this value.
+	 *
+	 * Default setting: {@value #DEFAULT_BITMAP_EXCESSIVE_BRANCH_TIP_COUNT}
+	 *
+	 * @param count
+	 *            the count of branch tips deemed "excessive"
+	 * @since 6.9
+	 */
+	public void setBitmapExcessiveBranchTipCount(int count) {
+		bitmapExcessiveBranchTipCount = count;
+	}
+
+	/**
 	 * Get the age in days that marks a branch as "inactive".
 	 *
 	 * Default setting: {@value #DEFAULT_BITMAP_INACTIVE_BRANCH_AGE_IN_DAYS}
@@ -1390,6 +1457,9 @@ public class PackConfig {
 		setBitmapExcessiveBranchCount(rc.getInt(CONFIG_PACK_SECTION,
 				CONFIG_KEY_BITMAP_EXCESSIVE_BRANCH_COUNT,
 				getBitmapExcessiveBranchCount()));
+		setBitmapExcessiveBranchTipCount(rc.getInt(CONFIG_PACK_SECTION,
+				CONFIG_KEY_BITMAP_EXCESSIVE_BRANCH_TIP_COUNT,
+				getBitmapExcessiveBranchTipCount()));
 		setBitmapInactiveBranchAgeInDays(rc.getInt(CONFIG_PACK_SECTION,
 				CONFIG_KEY_BITMAP_INACTIVE_BRANCH_AGE_INDAYS,
 				getBitmapInactiveBranchAgeInDays()));