DFS block cache: Refactor to enable parallel index loading

With this change bitmap index creation is not blocked on index and
reverse index full initialization in DfsPackFile. Now bitmap index and index could be
read from storage in parallel in separate threads.

Update PackBitmapIndexV1 constructor to get packIndex and reverseIndex
suppliers instead of actual objects. Inner class IdxPositionBitmap was added to initialize pack objects after bitmap
index is fully read from storage. Update DfsPackFile and PackBitmapIndex
accordingly.

Signed-off-by: Alina Djamankulova <adjama@google.com>
Change-Id: Iea59ab58501b2acbbf9263412982ec9c6898a7ee

3 files changed, 144 insertions, 40 deletions

diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsPackFile.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsPackFile.java
index 96ca690c1c..81b8d69939 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsPackFile.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsPackFile.java
@@ -58,12 +58,8 @@ public final class DfsPackFile extends BlockBasedFile {
 	private static final int REC_SIZE = Constants.OBJECT_ID_LENGTH + 8;
 	private static final long REF_POSITION = 0;
 
-	/**
-	 * Lock for initialization of {@link #index} and {@link #corruptObjects}.
-	 * <p>
-	 * This lock ensures only one thread can perform the initialization work.
-	 */
-	private final Object initLock = new Object();
+	/** Lock for initialization of {@link #index} and {@link #reverseIndex}. */
+	private final Object indexLock = new Object();
 
 	/** Index mapping {@link ObjectId} to position within the pack stream. */
 	private volatile PackIndex index;
@@ -71,9 +67,15 @@ public final class DfsPackFile extends BlockBasedFile {
 	/** Reverse version of {@link #index} mapping position to {@link ObjectId}. */
 	private volatile PackReverseIndex reverseIndex;
 
+	/** Lock for initialization of {@link #bitmapIndex}. */
+	private final Object bitmapIndexLock = new Object();
+
 	/** Index of compressed bitmap mapping entire object graph. */
 	private volatile PackBitmapIndex bitmapIndex;
 
+	/** Lock for {@link #corruptObjects}. */
+	private final Object corruptObjectsLock = new Object();
+
 	/**
 	 * Objects we have tried to read, and discovered to be corrupt.
 	 * <p>
@@ -155,7 +157,7 @@ public final class DfsPackFile extends BlockBasedFile {
 		Repository.getGlobalListenerList()
 				.dispatch(new BeforeDfsPackIndexLoadedEvent(this));
 
-		synchronized (initLock) {
+		synchronized (indexLock) {
 			if (index != null) {
 				return index;
 			}
@@ -183,7 +185,17 @@ public final class DfsPackFile extends BlockBasedFile {
 		return desc.getPackSource() == UNREACHABLE_GARBAGE;
 	}
 
-	PackBitmapIndex getBitmapIndex(DfsReader ctx) throws IOException {
+	/**
+	 * Get the BitmapIndex for this PackFile.
+	 *
+	 * @param ctx
+	 *            reader context to support reading from the backing store if
+	 *            the index is not already loaded in memory.
+	 * @return the BitmapIndex.
+	 * @throws java.io.IOException
+	 *             the bitmap index is not available, or is corrupt.
+	 */
+	public PackBitmapIndex getBitmapIndex(DfsReader ctx) throws IOException {
 		if (invalid || isGarbage() || !desc.hasFileExt(BITMAP_INDEX)) {
 			return null;
 		}
@@ -192,18 +204,16 @@ public final class DfsPackFile extends BlockBasedFile {
 			return bitmapIndex;
 		}
 
-		synchronized (initLock) {
+		synchronized (bitmapIndexLock) {
 			if (bitmapIndex != null) {
 				return bitmapIndex;
 			}
 
-			PackIndex idx = idx(ctx);
-			PackReverseIndex revidx = getReverseIdx(ctx);
 			DfsStreamKey bitmapKey = desc.getStreamKey(BITMAP_INDEX);
 			DfsBlockCache.Ref<PackBitmapIndex> idxref = cache.getOrLoadRef(
 					bitmapKey,
 					REF_POSITION,
-					() -> loadBitmapIndex(ctx, bitmapKey, idx, revidx));
+					() -> loadBitmapIndex(ctx, bitmapKey));
 			PackBitmapIndex bmidx = idxref.get();
 			if (bitmapIndex == null && bmidx != null) {
 				bitmapIndex = bmidx;
@@ -217,7 +227,7 @@ public final class DfsPackFile extends BlockBasedFile {
 			return reverseIndex;
 		}
 
-		synchronized (initLock) {
+		synchronized (indexLock) {
 			if (reverseIndex != null) {
 				return reverseIndex;
 			}
@@ -981,7 +991,7 @@ public final class DfsPackFile extends BlockBasedFile {
 	private void setCorrupt(long offset) {
 		LongList list = corruptObjects;
 		if (list == null) {
-			synchronized (initLock) {
+			synchronized (corruptObjectsLock) {
 				list = corruptObjects;
 				if (list == null) {
 					list = new LongList();
@@ -1041,11 +1051,8 @@ public final class DfsPackFile extends BlockBasedFile {
 				revidx);
 	}
 
-	private DfsBlockCache.Ref<PackBitmapIndex> loadBitmapIndex(
-			DfsReader ctx,
-			DfsStreamKey bitmapKey,
-			PackIndex idx,
-			PackReverseIndex revidx) throws IOException {
+	private DfsBlockCache.Ref<PackBitmapIndex> loadBitmapIndex(DfsReader ctx,
+			DfsStreamKey bitmapKey) throws IOException {
 		ctx.stats.readBitmap++;
 		long start = System.nanoTime();
 		try (ReadableChannel rc = ctx.db.openFile(desc, BITMAP_INDEX)) {
@@ -1061,7 +1068,8 @@ public final class DfsPackFile extends BlockBasedFile {
 					bs = wantSize;
 				}
 				in = new BufferedInputStream(in, bs);
-				bmidx = PackBitmapIndex.read(in, idx, revidx);
+				bmidx = PackBitmapIndex.read(in, () -> idx(ctx),
+						() -> getReverseIdx(ctx));
 			} finally {
 				size = rc.position();
 				ctx.stats.readIdxBytes += size;
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 beb51dc2eb..b7439f9c5b 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
@@ -97,7 +97,37 @@ public abstract class PackBitmapIndex {
 	public static PackBitmapIndex read(
 			InputStream fd, PackIndex packIndex, PackReverseIndex reverseIndex)
 			throws IOException {
-		return new PackBitmapIndexV1(fd, packIndex, reverseIndex);
+		return new PackBitmapIndexV1(fd, () -> packIndex, () -> reverseIndex);
+	}
+
+	/**
+	 * Read an existing pack bitmap index file from a buffered stream.
+	 * <p>
+	 * The format of the file will be automatically detected and a proper access
+	 * implementation for that format will be constructed and returned to the
+	 * caller. The file may or may not be held open by the returned instance.
+	 *
+	 * @param fd
+	 *            stream to read the bitmap index file from. The stream must be
+	 *            buffered as some small IOs are performed against the stream.
+	 *            The caller is responsible for closing the stream.
+	 * @param packIndexSupplier
+	 *            the supplier for pack index for the corresponding pack file.
+	 * @param reverseIndexSupplier
+	 *            the supplier for pack reverse index for the corresponding pack
+	 *            file.
+	 * @return a copy of the index in-memory.
+	 * @throws java.io.IOException
+	 *             the stream cannot be read.
+	 * @throws CorruptObjectException
+	 *             the stream does not contain a valid pack bitmap index.
+	 */
+	public static PackBitmapIndex read(InputStream fd,
+			SupplierWithIOException<PackIndex> packIndexSupplier,
+			SupplierWithIOException<PackReverseIndex> reverseIndexSupplier)
+			throws IOException {
+		return new PackBitmapIndexV1(fd, packIndexSupplier,
+				reverseIndexSupplier);
 	}
 
 	/** Footer checksum applied on the bottom of the pack file. */
@@ -161,4 +191,19 @@ public abstract class PackBitmapIndex {
 	 * @return the number of bitmaps in this bitmap index.
 	 */
 	public abstract int getBitmapCount();
+
+	/**
+	 * Supplier that propagates IOException.
+	 *
+	 * @param <T>
+	 *            the return type which is expected from {@link #get()}
+	 */
+	@FunctionalInterface
+	public interface SupplierWithIOException<T> {
+		/**
+		 * @return result
+		 * @throws IOException
+		 */
+		T get() throws IOException;
+	}
 }
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackBitmapIndexV1.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackBitmapIndexV1.java
index b7d241f3f8..c7864f4e70 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackBitmapIndexV1.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackBitmapIndexV1.java
@@ -14,8 +14,11 @@ import java.io.DataInput;
 import java.io.IOException;
 import java.io.InputStream;
 import java.text.MessageFormat;
+import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.List;
 
+import org.eclipse.jgit.annotations.Nullable;
 import org.eclipse.jgit.internal.JGitText;
 import org.eclipse.jgit.lib.AnyObjectId;
 import org.eclipse.jgit.lib.Constants;
@@ -46,11 +49,13 @@ class PackBitmapIndexV1 extends BasePackBitmapIndex {
 
 	private final ObjectIdOwnerMap<StoredBitmap> bitmaps;
 
-	PackBitmapIndexV1(final InputStream fd, PackIndex packIndex,
-			PackReverseIndex reverseIndex) throws IOException {
+	PackBitmapIndexV1(final InputStream fd,
+			SupplierWithIOException<PackIndex> packIndexSupplier,
+			SupplierWithIOException<PackReverseIndex> reverseIndexSupplier)
+			throws IOException {
+		// An entry is object id, xor offset, flag byte, and a length encoded
+		// bitmap. The object id is an int32 of the nth position sorted by name.
 		super(new ObjectIdOwnerMap<StoredBitmap>());
-		this.packIndex = packIndex;
-		this.reverseIndex = reverseIndex;
 		this.bitmaps = getBitmaps();
 
 		final byte[] scratch = new byte[32];
@@ -97,10 +102,10 @@ class PackBitmapIndexV1 extends BasePackBitmapIndex {
 		this.blobs = readBitmap(dataInput);
 		this.tags = readBitmap(dataInput);
 
-		// An entry is object id, xor offset, flag byte, and a length encoded
-		// bitmap. The object id is an int32 of the nth position sorted by name.
+		// Read full bitmap from storage first.
+		List<IdxPositionBitmap> idxPositionBitmapList = new ArrayList<>();
 		// The xor offset is a single byte offset back in the list of entries.
-		StoredBitmap[] recentBitmaps = new StoredBitmap[MAX_XOR_OFFSET];
+		IdxPositionBitmap[] recentBitmaps = new IdxPositionBitmap[MAX_XOR_OFFSET];
 		for (int i = 0; i < (int) numEntries; i++) {
 			IO.readFully(fd, scratch, 0, 6);
 			int nthObjectId = NB.decodeInt32(scratch, 0);
@@ -108,38 +113,58 @@ class PackBitmapIndexV1 extends BasePackBitmapIndex {
 			int flags = scratch[5];
 			EWAHCompressedBitmap bitmap = readBitmap(dataInput);
 
-			if (nthObjectId < 0)
+			if (nthObjectId < 0) {
 				throw new IOException(MessageFormat.format(
 						JGitText.get().invalidId, String.valueOf(nthObjectId)));
-			if (xorOffset < 0)
+			}
+			if (xorOffset < 0) {
 				throw new IOException(MessageFormat.format(
 						JGitText.get().invalidId, String.valueOf(xorOffset)));
-			if (xorOffset > MAX_XOR_OFFSET)
+			}
+			if (xorOffset > MAX_XOR_OFFSET) {
 				throw new IOException(MessageFormat.format(
 						JGitText.get().expectedLessThanGot,
 						String.valueOf(MAX_XOR_OFFSET),
 						String.valueOf(xorOffset)));
-			if (xorOffset > i)
+			}
+			if (xorOffset > i) {
 				throw new IOException(MessageFormat.format(
 						JGitText.get().expectedLessThanGot, String.valueOf(i),
 						String.valueOf(xorOffset)));
-
-			ObjectId objectId = packIndex.getObjectId(nthObjectId);
-			StoredBitmap xorBitmap = null;
+			}
+			IdxPositionBitmap xorIdxPositionBitmap = null;
 			if (xorOffset > 0) {
 				int index = (i - xorOffset);
-				xorBitmap = recentBitmaps[index % recentBitmaps.length];
-				if (xorBitmap == null)
+				xorIdxPositionBitmap = recentBitmaps[index
+						% recentBitmaps.length];
+				if (xorIdxPositionBitmap == null) {
 					throw new IOException(MessageFormat.format(
 							JGitText.get().invalidId,
 							String.valueOf(xorOffset)));
+				}
 			}
+			IdxPositionBitmap idxPositionBitmap = new IdxPositionBitmap(
+					nthObjectId, xorIdxPositionBitmap, bitmap, flags);
+			idxPositionBitmapList.add(idxPositionBitmap);
+			recentBitmaps[i % recentBitmaps.length] = idxPositionBitmap;
+		}
 
-			StoredBitmap sb = new StoredBitmap(
-					objectId, bitmap, xorBitmap, flags);
+		this.packIndex = packIndexSupplier.get();
+		for (int i = 0; i < idxPositionBitmapList.size(); ++i) {
+			IdxPositionBitmap idxPositionBitmap = idxPositionBitmapList.get(i);
+			ObjectId objectId = packIndex
+					.getObjectId(idxPositionBitmap.nthObjectId);
+			StoredBitmap sb = new StoredBitmap(objectId,
+					idxPositionBitmap.bitmap,
+					idxPositionBitmap.getXorStoredBitmap(),
+					idxPositionBitmap.flags);
+			// Save the StoredBitmap for a possible future XorStoredBitmap
+			// reference.
+			idxPositionBitmap.sb = sb;
 			bitmaps.add(sb);
-			recentBitmaps[i % recentBitmaps.length] = sb;
 		}
+
+		this.reverseIndex = reverseIndexSupplier.get();
 	}
 
 	/** {@inheritDoc} */
@@ -214,4 +239,30 @@ class PackBitmapIndexV1 extends BasePackBitmapIndex {
 		bitmap.deserialize(dataInput);
 		return bitmap;
 	}
+
+	/**
+	 * Temporary holder of object position in pack index and other metadata for
+	 * {@code StoredBitmap}.
+	 */
+	private static final class IdxPositionBitmap {
+		int nthObjectId;
+		IdxPositionBitmap xorIdxPositionBitmap;
+		EWAHCompressedBitmap bitmap;
+		int flags;
+		StoredBitmap sb;
+
+		IdxPositionBitmap(int nthObjectId, @Nullable
+		IdxPositionBitmap xorIdxPositionBitmap, EWAHCompressedBitmap bitmap,
+				int flags) {
+			this.nthObjectId = nthObjectId;
+			this.xorIdxPositionBitmap = xorIdxPositionBitmap;
+			this.bitmap = bitmap;
+			this.flags = flags;
+		}
+
+		StoredBitmap getXorStoredBitmap() {
+			return xorIdxPositionBitmap == null ? null
+					: xorIdxPositionBitmap.sb;
+		}
+	}
 }