PackBitmapIndex/StoredBitmap: Expose size and counts

PackBitmapIndex holds a collection of StoredBitmaps. StoredBitmaps can
be either base bitmaps (ready) or an XOR over another bitmap. XOR
bitmaps are replaced with a resolved version on demand. Bitmaps
can use a significant amount of memory but we don't have detailed
visibility about it.

Add methods to PackBitmapIndex to know how many xor/bases we have and
their sizes.

Change-Id: I57aa80a1f07ddf9223eb34cfda85aab85529ea9c

5 files changed, 295 insertions, 1 deletions

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/BasePackBitmapIndexTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/BasePackBitmapIndexTest.java
new file mode 100644
index 0000000000..f47c385ab9
--- /dev/null
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/BasePackBitmapIndexTest.java
@@ -0,0 +1,137 @@
+/*
+ * Copyright (c) 2023, 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.storage.file;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+import org.eclipse.jgit.internal.storage.file.BasePackBitmapIndex.StoredBitmap;
+import org.eclipse.jgit.lib.AnyObjectId;
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.ObjectIdOwnerMap;
+import org.junit.Before;
+import org.junit.Test;
+
+import com.googlecode.javaewah.EWAHCompressedBitmap;
+
+public class BasePackBitmapIndexTest {
+
+	private ObjectId baseOid;
+
+	private StoredBitmap baseBitmap;
+
+	private ObjectId xorOid;
+
+	private StoredBitmap xorBitmap;
+
+	private ObjectIdOwnerMap<StoredBitmap> bitmaps;
+
+	@Before
+	public void setUp() {
+		baseOid = ObjectId
+				.fromString("c46f36f2bfc96d6d6f75bd71ee33625293aee690");
+		baseBitmap = newBaseStoredBitmap(baseOid, bitmapOf(100));
+		xorOid = ObjectId
+				.fromString("52c18ae15f8fa3787f920e68791367dae2e1af2d");
+		xorBitmap = newXorStoredBitmap(xorOid, bitmapOf(200, 300), baseBitmap);
+		bitmaps = new ObjectIdOwnerMap<>();
+		bitmaps.add(baseBitmap);
+		bitmaps.add(xorBitmap);
+	}
+
+	@Test
+	public void testBitmapCounts() {
+		TestPackBitmapIndex index = new TestPackBitmapIndex(bitmaps);
+
+		assertEquals(1, index.getBaseBitmapCount());
+		assertEquals(1, index.getXorBitmapCount());
+		assertEquals(2, index.getBitmapCount());
+	}
+
+	@Test
+	public void testBitmapCounts_xorResolved() {
+		TestPackBitmapIndex index = new TestPackBitmapIndex(bitmaps);
+		index.getBitmap(xorOid);
+
+		assertEquals(2, index.getBaseBitmapCount());
+		assertEquals(0, index.getXorBitmapCount());
+		assertEquals(2, index.getBitmapCount());
+	}
+
+	@Test
+	public void testBitmapSizes() {
+		TestPackBitmapIndex index = new TestPackBitmapIndex(bitmaps);
+
+		assertEquals(baseBitmap.getCurrentSizeInBytes(),
+				index.getBaseBitmapSizeInBytes());
+		assertEquals(xorBitmap.getCurrentSizeInBytes(),
+				index.getXorBitmapSizeInBytes());
+	}
+
+	@Test
+	public void testBitmapSizes_xorResolved() {
+		TestPackBitmapIndex index = new TestPackBitmapIndex(bitmaps);
+		index.getBitmap(xorOid);
+
+		assertTrue(baseBitmap.getCurrentSizeInBytes() < index
+				.getBaseBitmapSizeInBytes());
+		assertEquals(0, index.getXorBitmapSizeInBytes());
+	}
+
+	private static final StoredBitmap newBaseStoredBitmap(ObjectId oid,
+			EWAHCompressedBitmap base) {
+		return new StoredBitmap(oid, base, null, 0);
+	}
+
+	private static StoredBitmap newXorStoredBitmap(ObjectId oid,
+			EWAHCompressedBitmap xorMask, StoredBitmap base) {
+		return new StoredBitmap(oid, xorMask, base, 0);
+	}
+
+	private static final EWAHCompressedBitmap bitmapOf(int... bits) {
+		EWAHCompressedBitmap b = new EWAHCompressedBitmap();
+		for (int bit : bits)
+			b.set(bit);
+		return b;
+	}
+
+	private static class TestPackBitmapIndex extends BasePackBitmapIndex {
+		TestPackBitmapIndex(ObjectIdOwnerMap<StoredBitmap> bitmaps) {
+			super(bitmaps);
+		}
+
+		@Override
+		public int findPosition(AnyObjectId objectId) {
+			throw new IllegalStateException();
+		}
+
+		@Override
+		public ObjectId getObject(int position)
+				throws IllegalArgumentException {
+			throw new IllegalStateException();
+		}
+
+		@Override
+		public EWAHCompressedBitmap ofObjectType(EWAHCompressedBitmap bitmap,
+				int type) {
+			throw new IllegalStateException();
+		}
+
+		@Override
+		public int getObjectCount() {
+			throw new IllegalStateException();
+		}
+
+		@Override
+		public int getBitmapCount() {
+			return getBitmaps().size();
+		}
+	}
+}
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/StoredBitmapTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/StoredBitmapTest.java
index f5c7c67c5d..684ee52b4a 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/StoredBitmapTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/StoredBitmapTest.java
@@ -11,6 +11,8 @@
 package org.eclipse.jgit.internal.storage.file;
 
 import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
 
 import org.eclipse.jgit.internal.storage.file.BasePackBitmapIndex.StoredBitmap;
 import org.eclipse.jgit.lib.ObjectId;
@@ -44,6 +46,33 @@ public class StoredBitmapTest {
 		assertEquals(bitmapOf(50, 90), sb.getBitmap());
 	}
 
+	@Test
+	public void testGetSizeWithoutXor() {
+		EWAHCompressedBitmap base = bitmapOf(100);
+		StoredBitmap sb = newStoredBitmap(base);
+		assertEquals(base.sizeInBytes(), sb.getCurrentSizeInBytes());
+		sb.getBitmap();
+		assertEquals(base.sizeInBytes(), sb.getCurrentSizeInBytes());
+	}
+
+	@Test
+	public void testGetSizeWithOneXor() {
+		EWAHCompressedBitmap base = bitmapOf(100, 101);
+		EWAHCompressedBitmap xor = bitmapOf(100);
+		StoredBitmap sb = newStoredBitmap(base, xor);
+		assertEquals(xor.sizeInBytes(), sb.getCurrentSizeInBytes());
+	}
+
+	@Test
+	public void testIsBase() {
+		EWAHCompressedBitmap one = bitmapOf(100, 101);
+		EWAHCompressedBitmap two = bitmapOf(100);
+		StoredBitmap baseBitmap = newStoredBitmap(one);
+		StoredBitmap xoredBitmap = newStoredBitmap(one, two);
+		assertTrue(baseBitmap.isBase());
+		assertFalse(xoredBitmap.isBase());
+	}
+
 	private static final StoredBitmap newStoredBitmap(
 			EWAHCompressedBitmap... bitmaps) {
 		StoredBitmap sb = null;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/BasePackBitmapIndex.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/BasePackBitmapIndex.java
index 906faded81..c2b3926309 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/BasePackBitmapIndex.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/BasePackBitmapIndex.java
@@ -35,6 +35,50 @@ abstract class BasePackBitmapIndex extends PackBitmapIndex {
 		return bitmaps;
 	}
 
+	@Override
+	public int getBaseBitmapCount() {
+		int bases = 0;
+		for (StoredBitmap sb : getBitmaps()) {
+			if (sb.isBase()) {
+				bases += 1;
+			}
+		}
+		return bases;
+	}
+
+	@Override
+	public long getBaseBitmapSizeInBytes() {
+		long baseSize = 0;
+		for (StoredBitmap sb : getBitmaps()) {
+			if (sb.isBase()) {
+				baseSize += sb.getCurrentSizeInBytes();
+			}
+		}
+		return baseSize;
+	}
+
+	@Override
+	public int getXorBitmapCount() {
+		int xored = 0;
+		for (StoredBitmap sb : getBitmaps()) {
+			if (!sb.isBase()) {
+				xored += 1;
+			}
+		}
+		return xored;
+	}
+
+	@Override
+	public long getXorBitmapSizeInBytes() {
+		long xorSize = 0;
+		for (StoredBitmap sb : getBitmaps()) {
+			if (!sb.isBase()) {
+				xorSize += sb.getCurrentSizeInBytes();
+			}
+		}
+		return xorSize;
+	}
+
 	/**
 	 * Data representation of the bitmap entry restored from a pack index. The
 	 * commit of the bitmap is the map key.
@@ -74,8 +118,9 @@ abstract class BasePackBitmapIndex extends PackBitmapIndex {
 		EWAHCompressedBitmap getBitmapWithoutCaching() {
 			// Fast path to immediately return the expanded result.
 			Object r = bitmapContainer;
-			if (r instanceof EWAHCompressedBitmap)
+			if (r instanceof EWAHCompressedBitmap) {
 				return (EWAHCompressedBitmap) r;
+			}
 
 			// Expand the bitmap but not cache the result.
 			XorCompressedBitmap xb = (XorCompressedBitmap) r;
@@ -100,10 +145,38 @@ abstract class BasePackBitmapIndex extends PackBitmapIndex {
 		int getFlags() {
 			return flags;
 		}
+
+		/**
+		 * This bitmap is (currently) a base or a XOR mask
+		 *
+		 * @return true if this bitmap is a base (a ready map).
+		 */
+		boolean isBase() {
+			return bitmapContainer instanceof EWAHCompressedBitmap;
+		}
+
+		/**
+		 * Size in bytes of this bitmap in its current representation
+		 *
+		 * If this is a XOR'ed bitmap, size is different before/after
+		 * {@link #getBitmap()}. Before is the byte size of the xor mask,
+		 * afterwards is the size of the "ready" bitmap
+		 *
+		 * @return size in bytes of the bitmap in its current representation
+		 */
+		long getCurrentSizeInBytes() {
+			Object r = bitmapContainer;
+			if (r instanceof EWAHCompressedBitmap) {
+				return ((EWAHCompressedBitmap) r).sizeInBytes();
+			}
+			XorCompressedBitmap xor = ((XorCompressedBitmap) r);
+			return xor.bitmap.sizeInBytes();
+		}
 	}
 
 	private static final class XorCompressedBitmap {
 		final EWAHCompressedBitmap bitmap;
+
 		final StoredBitmap xorBitmap;
 
 		XorCompressedBitmap(EWAHCompressedBitmap b, StoredBitmap xb) {
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackBitmapIndex.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackBitmapIndex.java
index 2334bd4851..def4f3dc11 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackBitmapIndex.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackBitmapIndex.java
@@ -196,6 +196,41 @@ public abstract class PackBitmapIndex {
 	public abstract int getBitmapCount();
 
 	/**
+	 * Returns the number of bitmaps in this bitmap index ready to use, not
+	 * XOR'ed against other entries.
+	 *
+	 * @return the number of bitmaps in this bitmap index ready to use.
+	 */
+	public abstract int getBaseBitmapCount();
+
+	/**
+	 * Current size in bytes of all base bitmaps in the index.
+	 *
+	 * Resolving xors for bitmaps can affect this size.
+	 *
+	 * @return Current size (in bytes) of all base bitmaps in this index.
+	 */
+	public abstract long getBaseBitmapSizeInBytes();
+
+	/**
+	 * Returns the number of bitmaps in this bitmap index XOR'ed against other
+	 * entries.
+	 *
+	 * @return the number of bitmaps in this bitmap index represented as XOR
+	 *         masks.
+	 */
+	public abstract int getXorBitmapCount();
+
+	/**
+	 * Current size in bytes of all XOR'ed bitmaps in the index.
+	 *
+	 * Resolving xors for bitmaps can affect this size.
+	 *
+	 * @return Current size (in bytes) of all xor bitmaps in this index.
+	 */
+	public abstract long getXorBitmapSizeInBytes();
+
+	/**
 	 * Supplier that propagates IOException.
 	 *
 	 * @param <T>
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackBitmapIndexRemapper.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackBitmapIndexRemapper.java
index 91c3683501..bb7cfd0464 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackBitmapIndexRemapper.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackBitmapIndexRemapper.java
@@ -95,6 +95,26 @@ public class PackBitmapIndexRemapper extends PackBitmapIndex
 	}
 
 	@Override
+	public int getBaseBitmapCount() {
+		return newPackIndex.getBaseBitmapCount();
+	}
+
+	@Override
+	public long getBaseBitmapSizeInBytes() {
+		return newPackIndex.getBaseBitmapSizeInBytes();
+	}
+
+	@Override
+	public int getXorBitmapCount() {
+		return newPackIndex.getXorBitmapCount();
+	}
+
+	@Override
+	public long getXorBitmapSizeInBytes() {
+		return newPackIndex.getXorBitmapSizeInBytes();
+	}
+
+	@Override
 	public EWAHCompressedBitmap ofObjectType(
 			EWAHCompressedBitmap bitmap, int type) {
 		return newPackIndex.ofObjectType(bitmap, type);