DfsPackFile/DfsGC: Write commit graphs and expose in pack

JGit knows how to read/write commit graphs but the DFS stack is not
using it yet.

The DFS garbage collector generates a commit-graph with commits
reachable from any ref. The pack is stored as extra stream in the GC
pack. DfsPackFile mimicks how other indices are loaded storing the
reference in DFS cache.

Signed-off-by: Xing Huang <xingkhuang@google.com>
Change-Id: I3f94997377986d21a56b300d8358dd27be37f5de

5 files changed, 136 insertions, 0 deletions

diff --git a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/storage/dfs/DfsText.properties b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/storage/dfs/DfsText.properties
index 2c4bd06a33..d9d43dc71f 100644
--- a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/storage/dfs/DfsText.properties
+++ b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/storage/dfs/DfsText.properties
@@ -1,4 +1,5 @@
 cannotReadIndex=Cannot read index {0}
+cannotReadCommitGraph=Cannot read commit graph {0}
 shortReadOfBlock=Short read of block at {0} in pack {1}; expected {2} bytes, received only {3}
 shortReadOfIndex=Short read of index {0}
 willNotStoreEmptyPack=Cannot store empty pack
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsGarbageCollector.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsGarbageCollector.java
index 26d5b5b176..66bcf73987 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsGarbageCollector.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsGarbageCollector.java
@@ -18,6 +18,7 @@ import static org.eclipse.jgit.internal.storage.dfs.DfsObjDatabase.PackSource.RE
 import static org.eclipse.jgit.internal.storage.dfs.DfsObjDatabase.PackSource.UNREACHABLE_GARBAGE;
 import static org.eclipse.jgit.internal.storage.dfs.DfsPackCompactor.configureReftable;
 import static org.eclipse.jgit.internal.storage.pack.PackExt.BITMAP_INDEX;
+import static org.eclipse.jgit.internal.storage.pack.PackExt.COMMIT_GRAPH;
 import static org.eclipse.jgit.internal.storage.pack.PackExt.INDEX;
 import static org.eclipse.jgit.internal.storage.pack.PackExt.PACK;
 import static org.eclipse.jgit.internal.storage.pack.PackExt.REFTABLE;
@@ -34,8 +35,11 @@ import java.util.HashSet;
 import java.util.List;
 import java.util.Set;
 import java.util.concurrent.TimeUnit;
+import java.util.stream.Collectors;
 
 import org.eclipse.jgit.internal.JGitText;
+import org.eclipse.jgit.internal.storage.commitgraph.CommitGraphWriter;
+import org.eclipse.jgit.internal.storage.commitgraph.GraphCommits;
 import org.eclipse.jgit.internal.storage.dfs.DfsObjDatabase.PackSource;
 import org.eclipse.jgit.internal.storage.file.PackIndex;
 import org.eclipse.jgit.internal.storage.file.PackReverseIndex;
@@ -75,6 +79,7 @@ public class DfsGarbageCollector {
 	private PackConfig packConfig;
 	private ReftableConfig reftableConfig;
 	private boolean convertToReftable = true;
+	private boolean writeCommitGraph;
 	private boolean includeDeletes;
 	private long reftableInitialMinUpdateIndex = 1;
 	private long reftableInitialMaxUpdateIndex = 1;
@@ -279,6 +284,20 @@ public class DfsGarbageCollector {
 	}
 
 	/**
+	 * Toggle commit graph generation.
+	 * <p>
+	 * False by default.
+	 *
+	 * @param enable
+	 *            Allow/Disallow commit graph generation.
+	 * @return {@code this}
+	 */
+	public DfsGarbageCollector setWriteCommitGraph(boolean enable) {
+		writeCommitGraph = enable;
+		return this;
+	}
+
+	/**
 	 * Create a single new pack file containing all of the live objects.
 	 * <p>
 	 * This method safely decides which packs can be expired after the new pack
@@ -642,6 +661,10 @@ public class DfsGarbageCollector {
 			writeReftable(pack);
 		}
 
+		if (source == GC) {
+			writeCommitGraph(pack, pm);
+		}
+
 		try (DfsOutputStream out = objdb.writeFile(pack, PACK)) {
 			pw.writePack(pm, pm, out);
 			pack.addFileExt(PACK);
@@ -724,4 +747,25 @@ public class DfsGarbageCollector {
 			pack.setReftableStats(writer.getStats());
 		}
 	}
+
+	private void writeCommitGraph(DfsPackDescription pack, ProgressMonitor pm)
+			throws IOException {
+		if (!writeCommitGraph || !objdb.getShallowCommits().isEmpty()) {
+			return;
+		}
+
+		Set<ObjectId> allTips = refsBefore.stream().map(Ref::getObjectId)
+				.collect(Collectors.toUnmodifiableSet());
+
+		try (DfsOutputStream out = objdb.writeFile(pack, COMMIT_GRAPH);
+				RevWalk pool = new RevWalk(ctx)) {
+			GraphCommits gcs = GraphCommits.fromWalk(pm, allTips, pool);
+			CountingOutputStream cnt = new CountingOutputStream(out);
+			CommitGraphWriter writer = new CommitGraphWriter(gcs);
+			writer.write(pm, cnt);
+			pack.addFileExt(COMMIT_GRAPH);
+			pack.setFileSize(COMMIT_GRAPH, cnt.getCount());
+			pack.setBlockSize(COMMIT_GRAPH, out.blockSize());
+		}
+	}
 }
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 15511fed30..411777c7ad 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
@@ -14,6 +14,7 @@ package org.eclipse.jgit.internal.storage.dfs;
 
 import static org.eclipse.jgit.internal.storage.dfs.DfsObjDatabase.PackSource.UNREACHABLE_GARBAGE;
 import static org.eclipse.jgit.internal.storage.pack.PackExt.BITMAP_INDEX;
+import static org.eclipse.jgit.internal.storage.pack.PackExt.COMMIT_GRAPH;
 import static org.eclipse.jgit.internal.storage.pack.PackExt.INDEX;
 import static org.eclipse.jgit.internal.storage.pack.PackExt.PACK;
 import static org.eclipse.jgit.internal.storage.pack.PackExt.REVERSE_INDEX;
@@ -37,6 +38,8 @@ import org.eclipse.jgit.errors.MissingObjectException;
 import org.eclipse.jgit.errors.PackInvalidException;
 import org.eclipse.jgit.errors.StoredObjectRepresentationNotAvailableException;
 import org.eclipse.jgit.internal.JGitText;
+import org.eclipse.jgit.internal.storage.commitgraph.CommitGraph;
+import org.eclipse.jgit.internal.storage.commitgraph.CommitGraphLoader;
 import org.eclipse.jgit.internal.storage.file.PackBitmapIndex;
 import org.eclipse.jgit.internal.storage.file.PackIndex;
 import org.eclipse.jgit.internal.storage.file.PackReverseIndex;
@@ -69,6 +72,9 @@ public final class DfsPackFile extends BlockBasedFile {
 	/** Index of compressed bitmap mapping entire object graph. */
 	private volatile PackBitmapIndex bitmapIndex;
 
+	/** Index of compressed commit graph mapping entire object graph. */
+	private volatile CommitGraph commitGraph;
+
 	/**
 	 * Objects we have tried to read, and discovered to be corrupt.
 	 * <p>
@@ -215,6 +221,43 @@ public final class DfsPackFile extends BlockBasedFile {
 		return bitmapIndex;
 	}
 
+	/**
+	 * Get the Commit Graph for this PackFile.
+	 *
+	 * @param ctx
+	 *            reader context to support reading from the backing store if
+	 *            the index is not already loaded in memory.
+	 * @return {@link org.eclipse.jgit.internal.storage.commitgraph.CommitGraph},
+	 *         null if pack doesn't have it.
+	 * @throws java.io.IOException
+	 *             the Commit Graph is not available, or is corrupt.
+	 */
+	public CommitGraph getCommitGraph(DfsReader ctx) throws IOException {
+		if (invalid || isGarbage() || !desc.hasFileExt(COMMIT_GRAPH)) {
+			return null;
+		}
+
+		if (commitGraph != null) {
+			return commitGraph;
+		}
+
+		DfsStreamKey commitGraphKey = desc.getStreamKey(COMMIT_GRAPH);
+		AtomicBoolean cacheHit = new AtomicBoolean(true);
+		DfsBlockCache.Ref<CommitGraph> cgref = cache
+				.getOrLoadRef(commitGraphKey, REF_POSITION, () -> {
+					cacheHit.set(false);
+					return loadCommitGraph(ctx, commitGraphKey);
+				});
+		if (cacheHit.get()) {
+			ctx.stats.commitGraphCacheHit++;
+		}
+		CommitGraph cg = cgref.get();
+		if (commitGraph == null && cg != null) {
+			commitGraph = cg;
+		}
+		return commitGraph;
+	}
+
 	PackReverseIndex getReverseIdx(DfsReader ctx) throws IOException {
 		if (reverseIndex != null) {
 			return reverseIndex;
@@ -1081,4 +1124,37 @@ public final class DfsPackFile extends BlockBasedFile {
 					desc.getFileName(BITMAP_INDEX)), e);
 		}
 	}
+
+	private DfsBlockCache.Ref<CommitGraph> loadCommitGraph(DfsReader ctx,
+			DfsStreamKey cgkey) throws IOException {
+		ctx.stats.readCommitGraph++;
+		long start = System.nanoTime();
+		try (ReadableChannel rc = ctx.db.openFile(desc, COMMIT_GRAPH)) {
+			long size;
+			CommitGraph cg;
+			try {
+				InputStream in = Channels.newInputStream(rc);
+				int wantSize = 8192;
+				int bs = rc.blockSize();
+				if (0 < bs && bs < wantSize) {
+					bs = (wantSize / bs) * bs;
+				} else if (bs <= 0) {
+					bs = wantSize;
+				}
+				in = new BufferedInputStream(in, bs);
+				cg = CommitGraphLoader.read(in);
+			} finally {
+				size = rc.position();
+				ctx.stats.readCommitGraphBytes += size;
+				ctx.stats.readCommitGraphMicros += elapsedMicros(start);
+			}
+			commitGraph = cg;
+			return new DfsBlockCache.Ref<>(cgkey, REF_POSITION, size, cg);
+		} catch (IOException e) {
+			throw new IOException(
+					MessageFormat.format(DfsText.get().cannotReadCommitGraph,
+							desc.getFileName(COMMIT_GRAPH)),
+					e);
+		}
+	}
 }
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsReader.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsReader.java
index d043b05fb9..8d8a766b0f 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsReader.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsReader.java
@@ -23,6 +23,7 @@ import java.util.HashSet;
 import java.util.Iterator;
 import java.util.LinkedList;
 import java.util.List;
+import java.util.Optional;
 import java.util.Set;
 import java.util.zip.DataFormatException;
 import java.util.zip.Inflater;
@@ -31,6 +32,7 @@ import org.eclipse.jgit.errors.IncorrectObjectTypeException;
 import org.eclipse.jgit.errors.MissingObjectException;
 import org.eclipse.jgit.errors.StoredObjectRepresentationNotAvailableException;
 import org.eclipse.jgit.internal.JGitText;
+import org.eclipse.jgit.internal.storage.commitgraph.CommitGraph;
 import org.eclipse.jgit.internal.storage.dfs.DfsObjDatabase.PackList;
 import org.eclipse.jgit.internal.storage.file.BitmapIndexImpl;
 import org.eclipse.jgit.internal.storage.file.PackBitmapIndex;
@@ -123,6 +125,18 @@ public class DfsReader extends ObjectReader implements ObjectReuseAsIs {
 
 	/** {@inheritDoc} */
 	@Override
+	public Optional<CommitGraph> getCommitGraph() throws IOException {
+		for (DfsPackFile pack : db.getPacks()) {
+			CommitGraph cg = pack.getCommitGraph(this);
+			if (cg != null) {
+				return Optional.of(cg);
+			}
+		}
+		return Optional.empty();
+	}
+
+	/** {@inheritDoc} */
+	@Override
 	public Collection<CachedPack> getCachedPacksAndUpdate(
 		BitmapBuilder needBitmap) throws IOException {
 		for (DfsPackFile pack : db.getPacks()) {
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsText.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsText.java
index df565e568d..f36ec06d3f 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsText.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsText.java
@@ -28,6 +28,7 @@ public class DfsText extends TranslationBundle {
 
 	// @formatter:off
 	/***/ public String cannotReadIndex;
+	/***/ public String cannotReadCommitGraph;
 	/***/ public String shortReadOfBlock;
 	/***/ public String shortReadOfIndex;
 	/***/ public String willNotStoreEmptyPack;