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

2 files changed, 146 insertions, 1 deletions

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/dfs/DfsBlockCacheTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/dfs/DfsBlockCacheTest.java
index 3dd4190c83..fef0563f48 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/dfs/DfsBlockCacheTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/dfs/DfsBlockCacheTest.java
@@ -284,12 +284,14 @@ public class DfsBlockCacheTest {
 			asyncRun(() -> pack.getBitmapIndex(reader));
 			asyncRun(() -> pack.getPackIndex(reader));
 			asyncRun(() -> pack.getBitmapIndex(reader));
+			asyncRun(() -> pack.getCommitGraph(reader));
 		}
 		waitForExecutorPoolTermination();
 
 		assertEquals(1, cache.getMissCount()[PackExt.BITMAP_INDEX.ordinal()]);
 		assertEquals(1, cache.getMissCount()[PackExt.INDEX.ordinal()]);
 		assertEquals(1, cache.getMissCount()[PackExt.REVERSE_INDEX.ordinal()]);
+		assertEquals(1, cache.getMissCount()[PackExt.COMMIT_GRAPH.ordinal()]);
 	}
 
 	@SuppressWarnings("resource")
@@ -313,12 +315,15 @@ public class DfsBlockCacheTest {
 			}
 			asyncRun(() -> pack1.getBitmapIndex(reader));
 			asyncRun(() -> pack2.getBitmapIndex(reader));
+			asyncRun(() -> pack1.getCommitGraph(reader));
+			asyncRun(() -> pack2.getCommitGraph(reader));
 		}
 
 		waitForExecutorPoolTermination();
 		assertEquals(2, cache.getMissCount()[PackExt.BITMAP_INDEX.ordinal()]);
 		assertEquals(2, cache.getMissCount()[PackExt.INDEX.ordinal()]);
 		assertEquals(2, cache.getMissCount()[PackExt.REVERSE_INDEX.ordinal()]);
+		assertEquals(2, cache.getMissCount()[PackExt.COMMIT_GRAPH.ordinal()]);
 	}
 
 	@SuppressWarnings("resource")
@@ -342,12 +347,15 @@ public class DfsBlockCacheTest {
 			}
 			asyncRun(() -> pack1.getBitmapIndex(reader));
 			asyncRun(() -> pack2.getBitmapIndex(reader));
+			asyncRun(() -> pack1.getCommitGraph(reader));
+			asyncRun(() -> pack2.getCommitGraph(reader));
 		}
 
 		waitForExecutorPoolTermination();
 		assertEquals(2, cache.getMissCount()[PackExt.BITMAP_INDEX.ordinal()]);
 		assertEquals(2, cache.getMissCount()[PackExt.INDEX.ordinal()]);
 		assertEquals(2, cache.getMissCount()[PackExt.REVERSE_INDEX.ordinal()]);
+		assertEquals(2, cache.getMissCount()[PackExt.COMMIT_GRAPH.ordinal()]);
 	}
 
 	@SuppressWarnings("resource")
@@ -372,7 +380,9 @@ public class DfsBlockCacheTest {
 			}
 			asyncRun(() -> pack1.getBitmapIndex(reader));
 			asyncRun(() -> pack1.getPackIndex(reader));
+			asyncRun(() -> pack1.getCommitGraph(reader));
 			asyncRun(() -> pack2.getBitmapIndex(reader));
+			asyncRun(() -> pack2.getCommitGraph(reader));
 		}
 		waitForExecutorPoolTermination();
 
@@ -380,6 +390,7 @@ public class DfsBlockCacheTest {
 		// Index is loaded once for each repo.
 		assertEquals(2, cache.getMissCount()[PackExt.INDEX.ordinal()]);
 		assertEquals(2, cache.getMissCount()[PackExt.REVERSE_INDEX.ordinal()]);
+		assertEquals(2, cache.getMissCount()[PackExt.COMMIT_GRAPH.ordinal()]);
 	}
 
 	@Test
@@ -396,12 +407,14 @@ public class DfsBlockCacheTest {
 			asyncRun(() -> pack.getBitmapIndex(reader));
 			asyncRun(() -> pack.getPackIndex(reader));
 			asyncRun(() -> pack.getBitmapIndex(reader));
+			asyncRun(() -> pack.getCommitGraph(reader));
 		}
 		waitForExecutorPoolTermination();
 
 		assertEquals(1, cache.getMissCount()[PackExt.BITMAP_INDEX.ordinal()]);
 		assertEquals(1, cache.getMissCount()[PackExt.INDEX.ordinal()]);
 		assertEquals(1, cache.getMissCount()[PackExt.REVERSE_INDEX.ordinal()]);
+		assertEquals(1, cache.getMissCount()[PackExt.COMMIT_GRAPH.ordinal()]);
 	}
 
 	@Test
@@ -420,12 +433,14 @@ public class DfsBlockCacheTest {
 			asyncRun(() -> pack.getBitmapIndex(reader));
 			asyncRun(() -> pack.getPackIndex(reader));
 			asyncRun(() -> pack.getBitmapIndex(reader));
+			asyncRun(() -> pack.getCommitGraph(reader));
 		}
 		waitForExecutorPoolTermination();
 
 		assertEquals(1, cache.getMissCount()[PackExt.BITMAP_INDEX.ordinal()]);
 		assertEquals(1, cache.getMissCount()[PackExt.INDEX.ordinal()]);
 		assertEquals(1, cache.getMissCount()[PackExt.REVERSE_INDEX.ordinal()]);
+		assertEquals(1, cache.getMissCount()[PackExt.COMMIT_GRAPH.ordinal()]);
 	}
 
 	private void resetCache() {
@@ -450,7 +465,7 @@ public class DfsBlockCacheTest {
 			repository.branch("/refs/ref2" + repoName).commit()
 					.add("blob2", "blob2" + repoName).parent(commit).create();
 		}
-		new DfsGarbageCollector(repo).pack(null);
+		new DfsGarbageCollector(repo).setWriteCommitGraph(true).pack(null);
 		return repo;
 	}
 
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/dfs/DfsGarbageCollectorTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/dfs/DfsGarbageCollectorTest.java
index f235b2eaa4..ab998951f3 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/dfs/DfsGarbageCollectorTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/dfs/DfsGarbageCollectorTest.java
@@ -18,6 +18,7 @@ import java.io.IOException;
 import java.util.Collections;
 import java.util.concurrent.TimeUnit;
 
+import org.eclipse.jgit.internal.storage.commitgraph.CommitGraph;
 import org.eclipse.jgit.internal.storage.dfs.DfsObjDatabase.PackSource;
 import org.eclipse.jgit.internal.storage.reftable.RefCursor;
 import org.eclipse.jgit.internal.storage.reftable.ReftableConfig;
@@ -976,10 +977,139 @@ public class DfsGarbageCollectorTest {
 		assertNull(refdb.exactRef(NEXT));
 	}
 
+	@Test
+	public void produceCommitGraphAllRefsIncludedFromDisk() throws Exception {
+		String tag = "refs/tags/tag1";
+		String head = "refs/heads/head1";
+		String nonHead = "refs/something/nonHead";
+
+		RevCommit rootCommitTagged = git.branch(tag).commit().message("0")
+				.noParents().create();
+		RevCommit headTip = git.branch(head).commit().message("1")
+				.parent(rootCommitTagged).create();
+		RevCommit nonHeadTip = git.branch(nonHead).commit().message("2")
+				.parent(rootCommitTagged).create();
+
+		gcWithCommitGraph();
+
+		assertEquals(2, odb.getPacks().length);
+		DfsPackFile gcPack = odb.getPacks()[0];
+		assertEquals(GC, gcPack.getPackDescription().getPackSource());
+
+		DfsReader reader = odb.newReader();
+		CommitGraph cg = gcPack.getCommitGraph(reader);
+		assertNotNull(cg);
+
+		assertTrue("all commits in commit graph", cg.getCommitCnt() == 3);
+		// GC packed
+		assertTrue("tag referenced commit is in graph",
+				cg.findGraphPosition(rootCommitTagged) != -1);
+		assertTrue("head referenced commit is in graph",
+				cg.findGraphPosition(headTip) != -1);
+		// GC_REST packed
+		assertTrue("nonHead referenced commit is in graph",
+				cg.findGraphPosition(nonHeadTip) != -1);
+	}
+
+	@Test
+	public void produceCommitGraphAllRefsIncludedFromCache() throws Exception {
+		String tag = "refs/tags/tag1";
+		String head = "refs/heads/head1";
+		String nonHead = "refs/something/nonHead";
+
+		RevCommit rootCommitTagged = git.branch(tag).commit().message("0")
+				.noParents().create();
+		RevCommit headTip = git.branch(head).commit().message("1")
+				.parent(rootCommitTagged).create();
+		RevCommit nonHeadTip = git.branch(nonHead).commit().message("2")
+				.parent(rootCommitTagged).create();
+
+		gcWithCommitGraph();
+
+		assertEquals(2, odb.getPacks().length);
+		DfsPackFile gcPack = odb.getPacks()[0];
+		assertEquals(GC, gcPack.getPackDescription().getPackSource());
+
+		DfsReader reader = odb.newReader();
+		gcPack.getCommitGraph(reader);
+		// Invoke cache hit
+		CommitGraph cachedCG = gcPack.getCommitGraph(reader);
+		assertNotNull(cachedCG);
+		assertTrue("commit graph have been read from disk once",
+				reader.stats.readCommitGraph == 1);
+		assertTrue("commit graph read contains content",
+				reader.stats.readCommitGraphBytes > 0);
+		assertTrue("commit graph read time is recorded",
+				reader.stats.readCommitGraphMicros > 0);
+
+		assertTrue("all commits in commit graph", cachedCG.getCommitCnt() == 3);
+		// GC packed
+		assertTrue("tag referenced commit is in graph",
+				cachedCG.findGraphPosition(rootCommitTagged) != -1);
+		assertTrue("head referenced commit is in graph",
+				cachedCG.findGraphPosition(headTip) != -1);
+		// GC_REST packed
+		assertTrue("nonHead referenced commit is in graph",
+				cachedCG.findGraphPosition(nonHeadTip) != -1);
+	}
+
+	@Test
+	public void noCommitGraphWithoutGcPack() throws Exception {
+		String nonHead = "refs/something/nonHead";
+		RevCommit nonHeadCommit = git.branch(nonHead).commit()
+				.message("nonhead").noParents().create();
+		commit().message("unreachable").parent(nonHeadCommit).create();
+
+		gcWithCommitGraph();
+
+		assertEquals(2, odb.getPacks().length);
+		for (DfsPackFile pack : odb.getPacks()) {
+			assertNull(pack.getCommitGraph(odb.newReader()));
+		}
+	}
+
+	@Test
+	public void commitGraphWithoutGCrestPack() throws Exception {
+		String head = "refs/heads/head1";
+		RevCommit headCommit = git.branch(head).commit().message("head")
+				.noParents().create();
+		RevCommit unreachableCommit = commit().message("unreachable")
+				.parent(headCommit).create();
+
+		gcWithCommitGraph();
+
+		assertEquals(2, odb.getPacks().length);
+		for (DfsPackFile pack : odb.getPacks()) {
+			DfsPackDescription d = pack.getPackDescription();
+			if (d.getPackSource() == GC) {
+				CommitGraph cg = pack.getCommitGraph(odb.newReader());
+				assertNotNull(cg);
+				assertTrue("commit graph only contains 1 commit",
+						cg.getCommitCnt() == 1);
+				assertTrue("head exists in commit graph",
+						cg.findGraphPosition(headCommit) != -1);
+				assertTrue("unreachable commit does not exist in commit graph",
+						cg.findGraphPosition(unreachableCommit) == -1);
+			} else if (d.getPackSource() == UNREACHABLE_GARBAGE) {
+				CommitGraph cg = pack.getCommitGraph(odb.newReader());
+				assertNull(cg);
+			} else {
+				fail("unexpected " + d.getPackSource());
+				break;
+			}
+		}
+	}
+
 	private TestRepository<InMemoryRepository>.CommitBuilder commit() {
 		return git.commit();
 	}
 
+	private void gcWithCommitGraph() throws IOException {
+		DfsGarbageCollector gc = new DfsGarbageCollector(repo);
+		gc.setWriteCommitGraph(true);
+		run(gc);
+	}
+
 	private void gcNoTtl() throws IOException {
 		DfsGarbageCollector gc = new DfsGarbageCollector(repo);
 		gc.setGarbageTtl(0, TimeUnit.MILLISECONDS); // disable TTL