CommitGraph: implement commit-graph writer

Teach JGit to write a commit-graph formatted file by walking commit
graph from specified commit objects.

See: https://git-scm.com/docs/commit-graph-format/2.21.0

Bug: 574368
Change-Id: I34f9f28f8729080c275f86215ebf30b2d05af41d
Signed-off-by: kylezhao <kylezhao@tencent.com>

9 files changed, 800 insertions, 0 deletions

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphWriterTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphWriterTest.java
new file mode 100644
index 0000000000..6c5e5e5605
--- /dev/null
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphWriterTest.java
@@ -0,0 +1,113 @@
+/*
+ * Copyright (C) 2021, Tencent.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Distribution License v. 1.0 which is available at
+ * https://www.eclipse.org/org/documents/edl-v10.php.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+
+package org.eclipse.jgit.internal.storage.commitgraph;
+
+import static org.junit.Assert.assertArrayEquals;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+import java.io.ByteArrayOutputStream;
+import java.util.Collections;
+import java.util.Set;
+
+import org.eclipse.jgit.internal.storage.file.FileRepository;
+import org.eclipse.jgit.junit.RepositoryTestCase;
+import org.eclipse.jgit.junit.TestRepository;
+import org.eclipse.jgit.lib.NullProgressMonitor;
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.revwalk.RevCommit;
+import org.eclipse.jgit.revwalk.RevWalk;
+import org.eclipse.jgit.util.NB;
+import org.junit.Before;
+import org.junit.Test;
+
+public class CommitGraphWriterTest extends RepositoryTestCase {
+
+	private TestRepository<FileRepository> tr;
+
+	private ByteArrayOutputStream os;
+
+	private CommitGraphWriter writer;
+
+	private RevWalk walk;
+
+	@Override
+	@Before
+	public void setUp() throws Exception {
+		super.setUp();
+		os = new ByteArrayOutputStream();
+		tr = new TestRepository<>(db, new RevWalk(db), mockSystemReader);
+		walk = new RevWalk(db);
+	}
+
+	@Test
+	public void testWriteInEmptyRepo() throws Exception {
+		NullProgressMonitor m = NullProgressMonitor.INSTANCE;
+		writer = new CommitGraphWriter(
+				GraphCommits.fromWalk(m, Collections.emptySet(), walk));
+		writer.write(m, os);
+		assertEquals(0, os.size());
+	}
+
+	@Test
+	public void testWriterWithExtraEdgeList() throws Exception {
+		RevCommit root = commit();
+		RevCommit a = commit(root);
+		RevCommit b = commit(root);
+		RevCommit c = commit(root);
+		RevCommit tip = commit(a, b, c);
+
+		Set<ObjectId> wants = Collections.singleton(tip);
+		NullProgressMonitor m = NullProgressMonitor.INSTANCE;
+		GraphCommits graphCommits = GraphCommits.fromWalk(m, wants, walk);
+		writer = new CommitGraphWriter(graphCommits);
+		writer.write(m, os);
+
+		assertEquals(5, graphCommits.size());
+		byte[] data = os.toByteArray();
+		assertTrue(data.length > 0);
+		byte[] headers = new byte[8];
+		System.arraycopy(data, 0, headers, 0, 8);
+		assertArrayEquals(new byte[] {'C', 'G', 'P', 'H', 1, 1, 4, 0}, headers);
+		assertEquals(CommitGraphConstants.CHUNK_ID_OID_FANOUT, NB.decodeInt32(data, 8));
+		assertEquals(CommitGraphConstants.CHUNK_ID_OID_LOOKUP, NB.decodeInt32(data, 20));
+		assertEquals(CommitGraphConstants.CHUNK_ID_COMMIT_DATA, NB.decodeInt32(data, 32));
+		assertEquals(CommitGraphConstants.CHUNK_ID_EXTRA_EDGE_LIST, NB.decodeInt32(data, 44));
+	}
+
+	@Test
+	public void testWriterWithoutExtraEdgeList() throws Exception {
+		RevCommit root = commit();
+		RevCommit a = commit(root);
+		RevCommit b = commit(root);
+		RevCommit tip = commit(a, b);
+
+		Set<ObjectId> wants = Collections.singleton(tip);
+		NullProgressMonitor m = NullProgressMonitor.INSTANCE;
+		GraphCommits graphCommits = GraphCommits.fromWalk(m, wants, walk);
+		writer = new CommitGraphWriter(graphCommits);
+		writer.write(m, os);
+
+		assertEquals(4, graphCommits.size());
+		byte[] data = os.toByteArray();
+		assertTrue(data.length > 0);
+		byte[] headers = new byte[8];
+		System.arraycopy(data, 0, headers, 0, 8);
+		assertArrayEquals(new byte[] {'C', 'G', 'P', 'H', 1, 1, 3, 0}, headers);
+		assertEquals(CommitGraphConstants.CHUNK_ID_OID_FANOUT, NB.decodeInt32(data, 8));
+		assertEquals(CommitGraphConstants.CHUNK_ID_OID_LOOKUP, NB.decodeInt32(data, 20));
+		assertEquals(CommitGraphConstants.CHUNK_ID_COMMIT_DATA, NB.decodeInt32(data, 32));
+	}
+
+	RevCommit commit(RevCommit... parents) throws Exception {
+		return tr.commit(parents);
+	}
+}
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/commitgraph/GraphCommitsTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/commitgraph/GraphCommitsTest.java
new file mode 100644
index 0000000000..fc05febed7
--- /dev/null
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/commitgraph/GraphCommitsTest.java
@@ -0,0 +1,119 @@
+/*
+ * Copyright (C) 2021, Tencent.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Distribution License v. 1.0 which is available at
+ * https://www.eclipse.org/org/documents/edl-v10.php.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+
+package org.eclipse.jgit.internal.storage.commitgraph;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertThrows;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
+
+import org.eclipse.jgit.errors.MissingObjectException;
+import org.eclipse.jgit.internal.storage.file.FileRepository;
+import org.eclipse.jgit.junit.RepositoryTestCase;
+import org.eclipse.jgit.junit.TestRepository;
+import org.eclipse.jgit.lib.NullProgressMonitor;
+import org.eclipse.jgit.revwalk.RevCommit;
+import org.eclipse.jgit.revwalk.RevWalk;
+import org.junit.Before;
+import org.junit.Test;
+
+public class GraphCommitsTest extends RepositoryTestCase {
+
+	private TestRepository<FileRepository> tr;
+
+	@Override
+	@Before
+	public void setUp() throws Exception {
+		super.setUp();
+		tr = new TestRepository<>(db, new RevWalk(db), mockSystemReader);
+	}
+
+	@Test
+	public void testEmptyRepo() throws Exception {
+		try (RevWalk rw = new RevWalk(db)) {
+			GraphCommits commits = GraphCommits.fromWalk(
+					NullProgressMonitor.INSTANCE, Collections.emptySet(), rw);
+			assertEquals(0, commits.size());
+			assertEquals(0, commits.getExtraEdgeCnt());
+			assertFalse(commits.iterator().hasNext());
+		}
+	}
+
+	@Test
+	public void testRepoWithoutExtraEdges() throws Exception {
+		try (RevWalk rw = new RevWalk(db)) {
+			RevCommit root = commit();
+			RevCommit a = commit(root);
+			RevCommit b = commit(root);
+			RevCommit tip = commit(a, b);
+			GraphCommits commits = GraphCommits.fromWalk(
+					NullProgressMonitor.INSTANCE, Collections.singleton(tip),
+					rw);
+			assertEquals(4, commits.size());
+			assertEquals(0, commits.getExtraEdgeCnt());
+			verifyOrderOfLookup(List.of(root, a, b, tip), commits);
+		}
+	}
+
+	@Test
+	public void testRepoWithExtraEdges() throws Exception {
+		try (RevWalk rw = new RevWalk(db)) {
+			RevCommit root = commit();
+			RevCommit a = commit(root);
+			RevCommit b = commit(root);
+			RevCommit c = commit(root);
+			RevCommit tip = commit(a, b, c);
+			GraphCommits commits = GraphCommits.fromWalk(
+					NullProgressMonitor.INSTANCE, Collections.singleton(tip),
+					rw);
+			assertEquals(5, commits.size());
+			assertEquals(2, commits.getExtraEdgeCnt());
+			verifyOrderOfLookup(List.of(root, a, b, c, tip), commits);
+		}
+	}
+
+	@Test
+	public void testCommitNotInLookup() throws Exception {
+		try (RevWalk rw = new RevWalk(db)) {
+			RevCommit a = commit();
+			RevCommit b = commit(a);
+			GraphCommits commits = GraphCommits.fromWalk(
+					NullProgressMonitor.INSTANCE, Collections.singleton(a), rw);
+			assertEquals(1, commits.size());
+			assertEquals(0, commits.getExtraEdgeCnt());
+			Iterator<RevCommit> iterator = commits.iterator();
+			assertEquals(a, iterator.next());
+			assertFalse(iterator.hasNext());
+			assertThrows(MissingObjectException.class,
+					() -> commits.getOidPosition(b));
+		}
+	}
+
+	private void verifyOrderOfLookup(List<RevCommit> commits,
+			GraphCommits graphCommits) {
+		commits = new ArrayList<>(commits);
+		Collections.sort(commits);
+		Iterator<RevCommit> expected = commits.iterator();
+		Iterator<RevCommit> actual = graphCommits.iterator();
+		while (expected.hasNext()) {
+			assertEquals(expected.next(), actual.next());
+		}
+		assertFalse(actual.hasNext());
+	}
+
+	RevCommit commit(RevCommit... parents) throws Exception {
+		return tr.commit(parents);
+	}
+}
diff --git a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
index 93269d5d62..9b9e6d5a2c 100644
--- a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
+++ b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
@@ -143,11 +143,13 @@ collisionOn=Collision on {0}
 commandClosedStderrButDidntExit=Command {0} closed stderr stream but didn''t exit within timeout {1} seconds
 commandRejectedByHook=Rejected by "{0}" hook.\n{1}
 commandWasCalledInTheWrongState=Command {0} was called in the wrong state
+commitGraphWritingCancelled=commit-graph writing was canceled
 commitMessageNotSpecified=commit message not specified
 commitOnRepoWithoutHEADCurrentlyNotSupported=Commit on repo without HEAD currently not supported
 commitAmendOnInitialNotPossible=Amending is not possible on initial commit.
 commitsHaveAlreadyBeenMarkedAsStart=Commits have already been marked as walk starts.
 compressingObjects=Compressing objects
+computingCommitGeneration=Computing commit-graph generation numbers
 configSubsectionContainsNewline=config subsection name contains newline
 configSubsectionContainsNullByte=config subsection name contains byte 0x00
 configValueContainsNullByte=config value contains byte 0x00
@@ -328,6 +330,7 @@ fileModeNotSetForPath=FileMode not set for path {0}
 filterExecutionFailed=Execution of filter command ''{0}'' on file ''{1}'' failed
 filterExecutionFailedRc=Execution of filter command ''{0}'' on file ''{1}'' failed with return code ''{2}'', message on stderr: ''{3}''
 filterRequiresCapability=filter requires server to advertise that capability
+findingCommitsForCommitGraph=Finding commits for commit-graph
 findingGarbage=Finding garbage
 flagIsDisposed={0} is disposed.
 flagNotFromThis={0} not from this.
@@ -839,6 +842,7 @@ writerAlreadyInitialized=Writer already initialized
 writeTimedOut=Write timed out after {0} ms
 writingNotPermitted=Writing not permitted
 writingNotSupported=Writing {0} not supported.
+writingOutCommitGraph=Writing out commit-graph in {0} passes
 writingObjects=Writing objects
 wrongDecompressedLength=wrong decompressed length
 wrongRepositoryState=Wrong Repository State: {0}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
index d89d689c9e..7e741e09ee 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
@@ -171,11 +171,13 @@ public class JGitText extends TranslationBundle {
 	/***/ public String commandClosedStderrButDidntExit;
 	/***/ public String commandRejectedByHook;
 	/***/ public String commandWasCalledInTheWrongState;
+	/***/ public String commitGraphWritingCancelled;
 	/***/ public String commitMessageNotSpecified;
 	/***/ public String commitOnRepoWithoutHEADCurrentlyNotSupported;
 	/***/ public String commitAmendOnInitialNotPossible;
 	/***/ public String commitsHaveAlreadyBeenMarkedAsStart;
 	/***/ public String compressingObjects;
+	/***/ public String computingCommitGeneration;
 	/***/ public String configSubsectionContainsNewline;
 	/***/ public String configSubsectionContainsNullByte;
 	/***/ public String configValueContainsNullByte;
@@ -356,6 +358,7 @@ public class JGitText extends TranslationBundle {
 	/***/ public String filterExecutionFailed;
 	/***/ public String filterExecutionFailedRc;
 	/***/ public String filterRequiresCapability;
+	/***/ public String findingCommitsForCommitGraph;
 	/***/ public String findingGarbage;
 	/***/ public String flagIsDisposed;
 	/***/ public String flagNotFromThis;
@@ -867,6 +870,7 @@ public class JGitText extends TranslationBundle {
 	/***/ public String writeTimedOut;
 	/***/ public String writingNotPermitted;
 	/***/ public String writingNotSupported;
+	/***/ public String writingOutCommitGraph;
 	/***/ public String writingObjects;
 	/***/ public String wrongDecompressedLength;
 	/***/ public String wrongRepositoryState;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphConstants.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphConstants.java
new file mode 100644
index 0000000000..a074833fa5
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphConstants.java
@@ -0,0 +1,55 @@
+/*
+ * Copyright (C) 2021, Tencent.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Distribution License v. 1.0 which is available at
+ * https://www.eclipse.org/org/documents/edl-v10.php.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+
+package org.eclipse.jgit.internal.storage.commitgraph;
+
+/**
+ * Constants relating to commit-graph.
+ */
+class CommitGraphConstants {
+
+	static final int COMMIT_GRAPH_MAGIC = 0x43475048; /* "CGPH" */
+
+	static final int CHUNK_ID_OID_FANOUT = 0x4f494446; /* "OIDF" */
+
+	static final int CHUNK_ID_OID_LOOKUP = 0x4f49444c; /* "OIDL" */
+
+	static final int CHUNK_ID_COMMIT_DATA = 0x43444154; /* "CDAT" */
+
+	static final int CHUNK_ID_EXTRA_EDGE_LIST = 0x45444745; /* "EDGE" */
+
+	/**
+	 * First 4 bytes describe the chunk id. Value 0 is a terminating label.
+	 * Other 8 bytes provide the byte-offset in current file for chunk to start.
+	 */
+	static final int CHUNK_LOOKUP_WIDTH = 12;
+
+	/**
+	 * First 8 bytes are for the positions of the first two parents of the ith
+	 * commit. The next 8 bytes store the generation number of the commit and
+	 * the commit time in seconds since EPOCH.
+	 */
+	static final int COMMIT_DATA_WIDTH = 16;
+
+	/** Mask to make the last edgeValue into position */
+	static final int GRAPH_EDGE_LAST_MASK = 0x7fffffff;
+
+	/** EdgeValue & GRAPH_LAST_EDGE != 0 means it is the last edgeValue */
+	static final int GRAPH_LAST_EDGE = 0x80000000;
+
+	/** EdgeValue == GRAPH_NO_PARENT means it has no parents */
+	static final int GRAPH_NO_PARENT = 0x70000000;
+
+	/**
+	 * EdgeValue & GRAPH_EXTRA_EDGES_NEEDED != 0 means its other parents are in
+	 * Chunk Extra Edge List
+	 */
+	static final int GRAPH_EXTRA_EDGES_NEEDED = 0x80000000;
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphWriter.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphWriter.java
new file mode 100644
index 0000000000..49a73dbd04
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphWriter.java
@@ -0,0 +1,335 @@
+/*
+ * Copyright (C) 2021, Tencent.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Distribution License v. 1.0 which is available at
+ * https://www.eclipse.org/org/documents/edl-v10.php.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+
+package org.eclipse.jgit.internal.storage.commitgraph;
+
+import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.CHUNK_ID_COMMIT_DATA;
+import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.CHUNK_ID_EXTRA_EDGE_LIST;
+import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.CHUNK_ID_OID_FANOUT;
+import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.CHUNK_ID_OID_LOOKUP;
+import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.CHUNK_LOOKUP_WIDTH;
+import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.COMMIT_DATA_WIDTH;
+import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.COMMIT_GRAPH_MAGIC;
+import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.GRAPH_EXTRA_EDGES_NEEDED;
+import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.GRAPH_LAST_EDGE;
+import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.GRAPH_NO_PARENT;
+import static org.eclipse.jgit.lib.Constants.COMMIT_GENERATION_NOT_COMPUTED;
+import static org.eclipse.jgit.lib.Constants.COMMIT_GENERATION_UNKNOWN;
+import static org.eclipse.jgit.lib.Constants.OBJECT_ID_LENGTH;
+
+import java.io.IOException;
+import java.io.InterruptedIOException;
+import java.io.OutputStream;
+import java.text.MessageFormat;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Stack;
+
+import org.eclipse.jgit.annotations.NonNull;
+import org.eclipse.jgit.errors.MissingObjectException;
+import org.eclipse.jgit.internal.JGitText;
+import org.eclipse.jgit.internal.storage.io.CancellableDigestOutputStream;
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.ProgressMonitor;
+import org.eclipse.jgit.revwalk.RevCommit;
+import org.eclipse.jgit.util.NB;
+
+/**
+ * Writes a commit-graph formatted file.
+ */
+public class CommitGraphWriter {
+
+	private static final int COMMIT_GRAPH_VERSION_GENERATED = 1;
+
+	private static final int OID_HASH_VERSION = 1;
+
+	private static final int GRAPH_FANOUT_SIZE = 4 * 256;
+
+	private static final int GENERATION_NUMBER_MAX = 0x3FFFFFFF;
+
+	private final int hashsz;
+
+	private final GraphCommits graphCommits;
+
+	/**
+	 * Create commit-graph writer for these commits.
+	 *
+	 * @param graphCommits
+	 *            the commits which will be writen to the commit-graph.
+	 */
+	public CommitGraphWriter(@NonNull GraphCommits graphCommits) {
+		this.graphCommits = graphCommits;
+		this.hashsz = OBJECT_ID_LENGTH;
+	}
+
+	/**
+	 * Write commit-graph to the supplied stream.
+	 *
+	 * @param monitor
+	 *            progress monitor to report the number of items written.
+	 * @param commitGraphStream
+	 *            output stream of commit-graph data. The stream should be
+	 *            buffered by the caller. The caller is responsible for closing
+	 *            the stream.
+	 * @throws IOException
+	 */
+	public void write(@NonNull ProgressMonitor monitor,
+			@NonNull OutputStream commitGraphStream) throws IOException {
+		if (graphCommits.size() == 0) {
+			return;
+		}
+
+		List<ChunkHeader> chunks = createChunks();
+		long writeCount = 256 + 2 * graphCommits.size()
+				+ graphCommits.getExtraEdgeCnt();
+		monitor.beginTask(
+				MessageFormat.format(JGitText.get().writingOutCommitGraph,
+						Integer.valueOf(chunks.size())),
+				(int) writeCount);
+
+		try (CancellableDigestOutputStream out = new CancellableDigestOutputStream(
+				monitor, commitGraphStream)) {
+			writeHeader(out, chunks.size());
+			writeChunkLookup(out, chunks);
+			writeChunks(monitor, out, chunks);
+			writeCheckSum(out);
+		} catch (InterruptedIOException e) {
+			throw new IOException(JGitText.get().commitGraphWritingCancelled);
+		} finally {
+			monitor.endTask();
+		}
+	}
+
+	private List<ChunkHeader> createChunks() {
+		List<ChunkHeader> chunks = new ArrayList<>();
+		chunks.add(new ChunkHeader(CHUNK_ID_OID_FANOUT, GRAPH_FANOUT_SIZE));
+		chunks.add(new ChunkHeader(CHUNK_ID_OID_LOOKUP,
+				hashsz * graphCommits.size()));
+		chunks.add(new ChunkHeader(CHUNK_ID_COMMIT_DATA,
+				(hashsz + 16) * graphCommits.size()));
+		if (graphCommits.getExtraEdgeCnt() > 0) {
+			chunks.add(new ChunkHeader(CHUNK_ID_EXTRA_EDGE_LIST,
+					graphCommits.getExtraEdgeCnt() * 4));
+		}
+		return chunks;
+	}
+
+	private void writeHeader(CancellableDigestOutputStream out, int numChunks)
+			throws IOException {
+		byte[] headerBuffer = new byte[8];
+		NB.encodeInt32(headerBuffer, 0, COMMIT_GRAPH_MAGIC);
+		byte[] buff = { (byte) COMMIT_GRAPH_VERSION_GENERATED,
+				(byte) OID_HASH_VERSION, (byte) numChunks, (byte) 0 };
+		System.arraycopy(buff, 0, headerBuffer, 4, 4);
+		out.write(headerBuffer, 0, 8);
+		out.flush();
+	}
+
+	private void writeChunkLookup(CancellableDigestOutputStream out,
+			List<ChunkHeader> chunks) throws IOException {
+		int numChunks = chunks.size();
+		long chunkOffset = 8 + (numChunks + 1) * CHUNK_LOOKUP_WIDTH;
+		byte[] buffer = new byte[CHUNK_LOOKUP_WIDTH];
+		for (ChunkHeader chunk : chunks) {
+			NB.encodeInt32(buffer, 0, chunk.id);
+			NB.encodeInt64(buffer, 4, chunkOffset);
+			out.write(buffer);
+			chunkOffset += chunk.size;
+		}
+		NB.encodeInt32(buffer, 0, 0);
+		NB.encodeInt64(buffer, 4, chunkOffset);
+		out.write(buffer);
+	}
+
+	private void writeChunks(ProgressMonitor monitor,
+			CancellableDigestOutputStream out, List<ChunkHeader> chunks)
+			throws IOException {
+		for (ChunkHeader chunk : chunks) {
+			int chunkId = chunk.id;
+
+			switch (chunkId) {
+			case CHUNK_ID_OID_FANOUT:
+				writeFanoutTable(out);
+				break;
+			case CHUNK_ID_OID_LOOKUP:
+				writeOidLookUp(out);
+				break;
+			case CHUNK_ID_COMMIT_DATA:
+				writeCommitData(monitor, out);
+				break;
+			case CHUNK_ID_EXTRA_EDGE_LIST:
+				writeExtraEdges(out);
+				break;
+			}
+		}
+	}
+
+	private void writeCheckSum(CancellableDigestOutputStream out)
+			throws IOException {
+		out.write(out.getDigest());
+		out.flush();
+	}
+
+	private void writeFanoutTable(CancellableDigestOutputStream out)
+			throws IOException {
+		byte[] tmp = new byte[4];
+		int[] fanout = new int[256];
+		for (RevCommit c : graphCommits) {
+			fanout[c.getFirstByte() & 0xff]++;
+		}
+		for (int i = 1; i < fanout.length; i++) {
+			fanout[i] += fanout[i - 1];
+		}
+		for (int n : fanout) {
+			NB.encodeInt32(tmp, 0, n);
+			out.write(tmp, 0, 4);
+			out.getWriteMonitor().update(1);
+		}
+	}
+
+	private void writeOidLookUp(CancellableDigestOutputStream out)
+			throws IOException {
+		byte[] tmp = new byte[4 + hashsz];
+
+		for (RevCommit c : graphCommits) {
+			c.copyRawTo(tmp, 0);
+			out.write(tmp, 0, hashsz);
+			out.getWriteMonitor().update(1);
+		}
+	}
+
+	private void writeCommitData(ProgressMonitor monitor,
+			CancellableDigestOutputStream out) throws IOException {
+		int[] generations = computeGenerationNumbers(monitor);
+		int num = 0;
+		byte[] tmp = new byte[hashsz + COMMIT_DATA_WIDTH];
+		int i = 0;
+		for (RevCommit commit : graphCommits) {
+			int edgeValue;
+			int[] packedDate = new int[2];
+
+			ObjectId treeId = commit.getTree();
+			treeId.copyRawTo(tmp, 0);
+
+			RevCommit[] parents = commit.getParents();
+			if (parents.length == 0) {
+				edgeValue = GRAPH_NO_PARENT;
+			} else {
+				RevCommit parent = parents[0];
+				edgeValue = graphCommits.getOidPosition(parent);
+			}
+			NB.encodeInt32(tmp, hashsz, edgeValue);
+			if (parents.length == 1) {
+				edgeValue = GRAPH_NO_PARENT;
+			} else if (parents.length == 2) {
+				RevCommit parent = parents[1];
+				edgeValue = graphCommits.getOidPosition(parent);
+			} else if (parents.length > 2) {
+				edgeValue = GRAPH_EXTRA_EDGES_NEEDED | num;
+				num += parents.length - 1;
+			}
+
+			NB.encodeInt32(tmp, hashsz + 4, edgeValue);
+
+			packedDate[0] = 0; // commitTime is an int in JGit now
+			packedDate[0] |= generations[i] << 2;
+			packedDate[1] = commit.getCommitTime();
+			NB.encodeInt32(tmp, hashsz + 8, packedDate[0]);
+			NB.encodeInt32(tmp, hashsz + 12, packedDate[1]);
+
+			out.write(tmp);
+			out.getWriteMonitor().update(1);
+			i++;
+		}
+	}
+
+	private int[] computeGenerationNumbers(ProgressMonitor monitor)
+			throws MissingObjectException {
+		int[] generations = new int[graphCommits.size()];
+		monitor.beginTask(JGitText.get().computingCommitGeneration,
+				graphCommits.size());
+		for (RevCommit cmit : graphCommits) {
+			monitor.update(1);
+			int generation = generations[graphCommits.getOidPosition(cmit)];
+			if (generation != COMMIT_GENERATION_NOT_COMPUTED
+					&& generation != COMMIT_GENERATION_UNKNOWN) {
+				continue;
+			}
+
+			Stack<RevCommit> commitStack = new Stack<>();
+			commitStack.push(cmit);
+
+			while (!commitStack.empty()) {
+				int maxGeneration = 0;
+				boolean allParentComputed = true;
+				RevCommit current = commitStack.peek();
+				RevCommit parent;
+
+				for (int i = 0; i < current.getParentCount(); i++) {
+					parent = current.getParent(i);
+					generation = generations[graphCommits
+							.getOidPosition(parent)];
+					if (generation == COMMIT_GENERATION_NOT_COMPUTED
+							|| generation == COMMIT_GENERATION_UNKNOWN) {
+						allParentComputed = false;
+						commitStack.push(parent);
+						break;
+					} else if (generation > maxGeneration) {
+						maxGeneration = generation;
+					}
+				}
+
+				if (allParentComputed) {
+					RevCommit commit = commitStack.pop();
+					generation = maxGeneration + 1;
+					if (generation > GENERATION_NUMBER_MAX) {
+						generation = GENERATION_NUMBER_MAX;
+					}
+					generations[graphCommits
+							.getOidPosition(commit)] = generation;
+				}
+			}
+		}
+		monitor.endTask();
+		return generations;
+	}
+
+	private void writeExtraEdges(CancellableDigestOutputStream out)
+			throws IOException {
+		byte[] tmp = new byte[4];
+		for (RevCommit commit : graphCommits) {
+			RevCommit[] parents = commit.getParents();
+			if (parents.length > 2) {
+				int edgeValue;
+				for (int n = 1; n < parents.length; n++) {
+					RevCommit parent = parents[n];
+					edgeValue = graphCommits.getOidPosition(parent);
+					if (n == parents.length - 1) {
+						edgeValue |= GRAPH_LAST_EDGE;
+					}
+					NB.encodeInt32(tmp, 0, edgeValue);
+					out.write(tmp);
+					out.getWriteMonitor().update(1);
+				}
+			}
+		}
+	}
+
+	private static class ChunkHeader {
+		final int id;
+
+		final long size;
+
+		public ChunkHeader(int id, long size) {
+			this.id = id;
+			this.size = size;
+		}
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/GraphCommits.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/GraphCommits.java
new file mode 100644
index 0000000000..e278434dee
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/GraphCommits.java
@@ -0,0 +1,147 @@
+/*
+ * Copyright (C) 2021, Tencent.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Distribution License v. 1.0 which is available at
+ * https://www.eclipse.org/org/documents/edl-v10.php.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+
+package org.eclipse.jgit.internal.storage.commitgraph;
+
+import java.io.IOException;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Set;
+
+import org.eclipse.jgit.annotations.NonNull;
+import org.eclipse.jgit.errors.MissingObjectException;
+import org.eclipse.jgit.internal.JGitText;
+import org.eclipse.jgit.lib.AnyObjectId;
+import org.eclipse.jgit.lib.Constants;
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.ObjectIdOwnerMap;
+import org.eclipse.jgit.lib.ProgressMonitor;
+import org.eclipse.jgit.revwalk.RevCommit;
+import org.eclipse.jgit.revwalk.RevObject;
+import org.eclipse.jgit.revwalk.RevSort;
+import org.eclipse.jgit.revwalk.RevWalk;
+import org.eclipse.jgit.util.BlockList;
+
+/**
+ * The commits which are used by the commit-graph writer to:
+ * <ul>
+ * <li>List commits in SHA1 order.</li>
+ * <li>Get the position of a specific SHA1 in the list.</li>
+ * </ul>
+ */
+public class GraphCommits implements Iterable<RevCommit> {
+
+	/**
+	 * Prepare and create the commits for
+	 * {@link org.eclipse.jgit.internal.storage.commitgraph.CommitGraphWriter}
+	 * from the RevWalk.
+	 *
+	 * @param pm
+	 *            progress monitor.
+	 * @param wants
+	 *            the list of wanted objects, writer walks commits starting at
+	 *            these. Must not be {@code null}.
+	 * @param walk
+	 *            the RevWalk to use. Must not be {@code null}.
+	 * @return the commits' collection which are used by the commit-graph
+	 *         writer. Never null.
+	 * @throws IOException
+	 */
+	public static GraphCommits fromWalk(ProgressMonitor pm,
+			@NonNull Set<? extends ObjectId> wants, @NonNull RevWalk walk)
+			throws IOException {
+		walk.reset();
+		walk.sort(RevSort.NONE);
+		walk.setRetainBody(false);
+		for (ObjectId id : wants) {
+			RevObject o = walk.parseAny(id);
+			if (o instanceof RevCommit) {
+				walk.markStart((RevCommit) o);
+			}
+		}
+		List<RevCommit> commits = new BlockList<>();
+		RevCommit c;
+		pm.beginTask(JGitText.get().findingCommitsForCommitGraph,
+				ProgressMonitor.UNKNOWN);
+		while ((c = walk.next()) != null) {
+			pm.update(1);
+			commits.add(c);
+		}
+		pm.endTask();
+		return new GraphCommits(commits);
+	}
+
+	private final List<RevCommit> sortedCommits;
+
+	private final ObjectIdOwnerMap<CommitWithPosition> commitPosMap;
+
+	private final int extraEdgeCnt;
+
+	/**
+	 * Initialize the GraphCommits.
+	 *
+	 * @param commits
+	 *            list of commits with their headers already parsed.
+	 */
+	private GraphCommits(List<RevCommit> commits) {
+		Collections.sort(commits); // sorted by name
+		sortedCommits = commits;
+		commitPosMap = new ObjectIdOwnerMap<>();
+		int cnt = 0;
+		for (int i = 0; i < commits.size(); i++) {
+			RevCommit c = sortedCommits.get(i);
+			if (c.getParentCount() > 2) {
+				cnt += c.getParentCount() - 1;
+			}
+			commitPosMap.add(new CommitWithPosition(c, i));
+		}
+		this.extraEdgeCnt = cnt;
+	}
+
+	int getOidPosition(RevCommit c) throws MissingObjectException {
+		CommitWithPosition commitWithPosition = commitPosMap.get(c);
+		if (commitWithPosition == null) {
+			throw new MissingObjectException(c, Constants.OBJ_COMMIT);
+		}
+		return commitWithPosition.position;
+	}
+
+	RevCommit getCommit(int oidPos) {
+		if (oidPos < 0 || oidPos >= sortedCommits.size()) {
+			return null;
+		}
+		return sortedCommits.get(oidPos);
+	}
+
+	int getExtraEdgeCnt() {
+		return extraEdgeCnt;
+	}
+
+	int size() {
+		return sortedCommits.size();
+	}
+
+	/** {@inheritDoc} */
+	@Override
+	public Iterator<RevCommit> iterator() {
+		return sortedCommits.iterator();
+	}
+
+	private static class CommitWithPosition extends ObjectIdOwnerMap.Entry {
+
+		final int position;
+
+		CommitWithPosition(AnyObjectId id, int position) {
+			super(id);
+			this.position = position;
+		}
+	}
+}
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 47a572b83a..203533d3a8 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/ConfigConstants.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ConfigConstants.java
@@ -886,4 +886,10 @@ public final class ConfigConstants {
 	 */
 	public static final String CONFIG_KEY_ABBREV = "abbrev";
 
+	/**
+	 * The "writeCommitGraph" key
+	 *
+	 * @since 6.5
+	 */
+	public static final String CONFIG_KEY_WRITE_COMMIT_GRAPH = "writeCommitGraph";
 }
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/Constants.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/Constants.java
index 30a0074195..c166abe128 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/Constants.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/Constants.java
@@ -754,6 +754,23 @@ public final class Constants {
 	 */
 	public static final int INFINITE_DEPTH = 0x7fffffff;
 
+	/**
+	 * We use ({@value}) as generation number for commits not in the
+	 * commit-graph file.
+	 *
+	 * @since 6.5
+	 */
+	public static int COMMIT_GENERATION_UNKNOWN = Integer.MAX_VALUE;
+
+	/**
+	 * If a commit-graph file was written by a version of Git that did not
+	 * compute generation numbers, then those commits will have generation
+	 * number represented by ({@value}).
+	 *
+	 * @since 6.5
+	 */
+	public static int COMMIT_GENERATION_NOT_COMPUTED = 0;
+
 	private Constants() {
 		// Hide the default constructor
 	}