git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH v6 08/11] commit-graph: implement generation data chunk

From
Abhishek Kumar via GitGitGadget <gitgitgadget@gmail.com>
Date
Jan 16, 2021, 18:11 UTC
Message-ID
<6d0696ae216156e820a8d19ebbae00039a0f3509.1610820679.git.gitgitgadget@gmail.com>
In-Reply-To
<pull.676.v6.git.1610820679.gitgitgadget@gmail.com>
From: Abhishek Kumar <abhishekkumar8222@gmail.com>

As discovered by Ævar, we cannot increment graph version to distinguish between generation numbers v1 and v2 [1]. Thus, one of pre-requistes before implementing generation number v2 was to distinguish between graph versions in a backwards compatible manner.

We are going to introduce a new chunk called Generation DATa chunk (or GDAT). GDAT will store corrected committer date offsets whereas CDAT will still store topological level.

Old Git does not understand GDAT chunk and would ignore it, reading topological levels from CDAT. New Git can parse GDAT and take advantage of newer generation numbers, falling back to topological levels when GDAT chunk is missing (as it would happen with a commit-graph written by old Git).

We introduce a test environment variable 'GIT_TEST_COMMIT_GRAPH_NO_GDAT' which forces commit-graph file to be written without generation data chunk to emulate a commit-graph file written by old Git.

To minimize the space required to store corrrected commit date, Git stores corrected commit date offsets into the commit-graph file, instea of corrected commit dates. This saves us 4 bytes per commit, decreasing the GDAT chunk size by half, but it's possible for the offset to overflow the 4-bytes allocated for storage. As such overflows are and should be exceedingly rare, we use the following overflow management scheme:

We introduce a new commit-graph chunk, Generation Data OVerflow ('GDOV') to store corrected commit dates for commits with offsets greater than GENERATION_NUMBER_V2_OFFSET_MAX.

If the offset is greater than GENERATION_NUMBER_V2_OFFSET_MAX, we set the MSB of the offset and the other bits store the position of corrected commit date in GDOV chunk, similar to how Extra Edge List is maintained.

We test the overflow-related code with the following repo history:
           F - N - U
          /         \
U - N - U            N
         \          /
	  N - F - N

Where the commits denoted by U have committer date of zero seconds since Unix epoch, the commits denoted by N have committer date of 1112354055 (default committer date for the test suite) seconds since Unix epoch and the commits denoted by F have committer date of (2 ^ 31 - 2) seconds since Unix epoch.

The largest offset observed is 2 ^ 31, just large enough to overflow.
[1]: https://lore.kernel.org/git/87a7gdspo4.fsf@evledraar.gmail.com/
Signed-off-by: Abhishek Kumar <abhishekkumar8222@gmail.com>
---
 commit-graph.c                | 114 ++++++++++++++++++++++++++++++----
 commit-graph.h                |   3 +
 commit.h                      |   1 +
 t/README                      |   3 +
 t/helper/test-read-graph.c    |   4 ++
 t/t4216-log-bloom.sh          |   4 +-
 t/t5318-commit-graph.sh       |  79 +++++++++++++++++++----
 t/t5324-split-commit-graph.sh |  12 ++--
 t/t6600-test-reach.sh         |   6 ++
 t/test-lib-functions.sh       |   6 ++
 10 files changed, 200 insertions(+), 32 deletions(-)
diff --git a/commit-graph.c b/commit-graph.c
index a899f429093..7365958d9d3 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -38,11 +38,13 @@ void git_test_write_commit_graph_or_die(void)
 #define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */
 #define GRAPH_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */
 #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
+#define GRAPH_CHUNKID_GENERATION_DATA 0x47444154 /* "GDAT" */
+#define GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW 0x47444f56 /* "GDOV" */
 #define GRAPH_CHUNKID_EXTRAEDGES 0x45444745 /* "EDGE" */
 #define GRAPH_CHUNKID_BLOOMINDEXES 0x42494458 /* "BIDX" */
 #define GRAPH_CHUNKID_BLOOMDATA 0x42444154 /* "BDAT" */
 #define GRAPH_CHUNKID_BASE 0x42415345 /* "BASE" */
-#define MAX_NUM_CHUNKS 7
+#define MAX_NUM_CHUNKS 9
 
 #define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16)
 
@@ -61,6 +63,8 @@ void git_test_write_commit_graph_or_die(void)
 #define GRAPH_MIN_SIZE (GRAPH_HEADER_SIZE + 4 * GRAPH_CHUNKLOOKUP_WIDTH \
 			+ GRAPH_FANOUT_SIZE + the_hash_algo->rawsz)
 
+#define CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW (1ULL << 31)
+
 /* Remember to update object flag allocation in object.h */
 #define REACHABLE       (1u<<15)
 
@@ -394,6 +398,20 @@ struct commit_graph *parse_commit_graph(struct repository *r,
 				graph->chunk_commit_data = data + chunk_offset;
 			break;
 
+		case GRAPH_CHUNKID_GENERATION_DATA:
+			if (graph->chunk_generation_data)
+				chunk_repeated = 1;
+			else
+				graph->chunk_generation_data = data + chunk_offset;
+			break;
+
+		case GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW:
+			if (graph->chunk_generation_data_overflow)
+				chunk_repeated = 1;
+			else
+				graph->chunk_generation_data_overflow = data + chunk_offset;
+			break;
+
 		case GRAPH_CHUNKID_EXTRAEDGES:
 			if (graph->chunk_extra_edges)
 				chunk_repeated = 1;
@@ -754,8 +772,8 @@ static void fill_commit_graph_info(struct commit *item, struct commit_graph *g,
 {
 	const unsigned char *commit_data;
 	struct commit_graph_data *graph_data;
-	uint32_t lex_index;
-	uint64_t date_high, date_low;
+	uint32_t lex_index, offset_pos;
+	uint64_t date_high, date_low, offset;
 
 	while (pos < g->num_commits_in_base)
 		g = g->base_graph;
@@ -773,7 +791,19 @@ static void fill_commit_graph_info(struct commit *item, struct commit_graph *g,
 	date_low = get_be32(commit_data + g->hash_len + 12);
 	item->date = (timestamp_t)((date_high << 32) | date_low);
 
-	graph_data->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
+	if (g->chunk_generation_data) {
+		offset = (timestamp_t)get_be32(g->chunk_generation_data + sizeof(uint32_t) * lex_index);
+
+		if (offset & CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW) {
+			if (!g->chunk_generation_data_overflow)
+				die(_("commit-graph requires overflow generation data but has none"));
+
+			offset_pos = offset ^ CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW;
+			graph_data->generation = get_be64(g->chunk_generation_data_overflow + 8 * offset_pos);
+		} else
+			graph_data->generation = item->date + offset;
+	} else
+		graph_data->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
 
 	if (g->topo_levels)
 		*topo_level_slab_at(g->topo_levels, item) = get_be32(commit_data + g->hash_len + 8) >> 2;
@@ -945,6 +975,7 @@ struct write_commit_graph_context {
 	struct oid_array oids;
 	struct packed_commit_list commits;
 	int num_extra_edges;
+	int num_generation_data_overflows;
 	unsigned long approx_nr_objects;
 	struct progress *progress;
 	int progress_done;
@@ -963,7 +994,8 @@ struct write_commit_graph_context {
 		 report_progress:1,
 		 split:1,
 		 changed_paths:1,
-		 order_by_pack:1;
+		 order_by_pack:1,
+		 write_generation_data:1;
 
 	struct topo_level_slab *topo_levels;
 	const struct commit_graph_opts *opts;
@@ -1123,6 +1155,45 @@ static int write_graph_chunk_data(struct hashfile *f,
 	return 0;
 }
 
+static int write_graph_chunk_generation_data(struct hashfile *f,
+					      struct write_commit_graph_context *ctx)
+{
+	int i, num_generation_data_overflows = 0;
+
+	for (i = 0; i < ctx->commits.nr; i++) {
+		struct commit *c = ctx->commits.list[i];
+		timestamp_t offset = commit_graph_data_at(c)->generation - c->date;
+		display_progress(ctx->progress, ++ctx->progress_cnt);
+
+		if (offset > GENERATION_NUMBER_V2_OFFSET_MAX) {
+			offset = CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW | num_generation_data_overflows;
+			num_generation_data_overflows++;
+		}
+
+		hashwrite_be32(f, offset);
+	}
+
+	return 0;
+}
+
+static int write_graph_chunk_generation_data_overflow(struct hashfile *f,
+						       struct write_commit_graph_context *ctx)
+{
+	int i;
+	for (i = 0; i < ctx->commits.nr; i++) {
+		struct commit *c = ctx->commits.list[i];
+		timestamp_t offset = commit_graph_data_at(c)->generation - c->date;
+		display_progress(ctx->progress, ++ctx->progress_cnt);
+
+		if (offset > GENERATION_NUMBER_V2_OFFSET_MAX) {
+			hashwrite_be32(f, offset >> 32);
+			hashwrite_be32(f, (uint32_t) offset);
+		}
+	}
+
+	return 0;
+}
+
 static int write_graph_chunk_extra_edges(struct hashfile *f,
 					 struct write_commit_graph_context *ctx)
 {
@@ -1386,6 +1457,9 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
 				if (current->date && current->date > max_corrected_commit_date)
 					max_corrected_commit_date = current->date - 1;
 				commit_graph_data_at(current)->generation = max_corrected_commit_date + 1;
+
+				if (commit_graph_data_at(current)->generation - current->date > GENERATION_NUMBER_V2_OFFSET_MAX)
+					ctx->num_generation_data_overflows++;
 			}
 		}
 	}
@@ -1719,6 +1793,21 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)
 	chunks[2].id = GRAPH_CHUNKID_DATA;
 	chunks[2].size = (hashsz + 16) * ctx->commits.nr;
 	chunks[2].write_fn = write_graph_chunk_data;
+
+	if (git_env_bool(GIT_TEST_COMMIT_GRAPH_NO_GDAT, 0))
+		ctx->write_generation_data = 0;
+	if (ctx->write_generation_data) {
+		chunks[num_chunks].id = GRAPH_CHUNKID_GENERATION_DATA;
+		chunks[num_chunks].size = sizeof(uint32_t) * ctx->commits.nr;
+		chunks[num_chunks].write_fn = write_graph_chunk_generation_data;
+		num_chunks++;
+	}
+	if (ctx->num_generation_data_overflows) {
+		chunks[num_chunks].id = GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW;
+		chunks[num_chunks].size = sizeof(timestamp_t) * ctx->num_generation_data_overflows;
+		chunks[num_chunks].write_fn = write_graph_chunk_generation_data_overflow;
+		num_chunks++;
+	}
 	if (ctx->num_extra_edges) {
 		chunks[num_chunks].id = GRAPH_CHUNKID_EXTRAEDGES;
 		chunks[num_chunks].size = 4 * ctx->num_extra_edges;
@@ -2139,6 +2228,8 @@ int write_commit_graph(struct object_directory *odb,
 	ctx->split = flags & COMMIT_GRAPH_WRITE_SPLIT ? 1 : 0;
 	ctx->opts = opts;
 	ctx->total_bloom_filter_data_size = 0;
+	ctx->write_generation_data = 1;
+	ctx->num_generation_data_overflows = 0;
 
 	bloom_settings.bits_per_entry = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY",
 						      bloom_settings.bits_per_entry);
@@ -2445,16 +2536,17 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)
 			continue;
 
 		/*
-		 * If one of our parents has generation GENERATION_NUMBER_V1_MAX, then
-		 * our generation is also GENERATION_NUMBER_V1_MAX. Decrement to avoid
-		 * extra logic in the following condition.
+		 * If we are using topological level and one of our parents has
+		 * generation GENERATION_NUMBER_V1_MAX, then our generation is
+		 * also GENERATION_NUMBER_V1_MAX. Decrement to avoid extra logic
+		 * in the following condition.
 		 */
-		if (max_generation == GENERATION_NUMBER_V1_MAX)
+		if (!g->chunk_generation_data && max_generation == GENERATION_NUMBER_V1_MAX)
 			max_generation--;
 
 		generation = commit_graph_generation(graph_commit);
-		if (generation != max_generation + 1)
-			graph_report(_("commit-graph generation for commit %s is %"PRItime" != %"PRItime),
+		if (generation < max_generation + 1)
+			graph_report(_("commit-graph generation for commit %s is %"PRItime" < %"PRItime),
 				     oid_to_hex(&cur_oid),
 				     generation,
 				     max_generation + 1);
diff --git a/commit-graph.h b/commit-graph.h
index 2e9aa7824ee..19a02001fde 100644
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -6,6 +6,7 @@
 #include "oidset.h"
 
 #define GIT_TEST_COMMIT_GRAPH "GIT_TEST_COMMIT_GRAPH"
+#define GIT_TEST_COMMIT_GRAPH_NO_GDAT "GIT_TEST_COMMIT_GRAPH_NO_GDAT"
 #define GIT_TEST_COMMIT_GRAPH_DIE_ON_PARSE "GIT_TEST_COMMIT_GRAPH_DIE_ON_PARSE"
 #define GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS "GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS"
 
@@ -68,6 +69,8 @@ struct commit_graph {
 	const uint32_t *chunk_oid_fanout;
 	const unsigned char *chunk_oid_lookup;
 	const unsigned char *chunk_commit_data;
+	const unsigned char *chunk_generation_data;
+	const unsigned char *chunk_generation_data_overflow;
 	const unsigned char *chunk_extra_edges;
 	const unsigned char *chunk_base_graphs;
 	const unsigned char *chunk_bloom_indexes;
diff --git a/commit.h b/commit.h
index 742d96c41e8..eff94f3f7c2 100644
--- a/commit.h
+++ b/commit.h
@@ -14,6 +14,7 @@
 #define GENERATION_NUMBER_INFINITY ((1ULL << 63) - 1)
 #define GENERATION_NUMBER_V1_MAX 0x3FFFFFFF
 #define GENERATION_NUMBER_ZERO 0
+#define GENERATION_NUMBER_V2_OFFSET_MAX ((1ULL << 31) - 1)
 
 struct commit_list {
 	struct commit *item;
diff --git a/t/README b/t/README
index c730a707705..8a121487279 100644
--- a/t/README
+++ b/t/README
@@ -393,6 +393,9 @@ GIT_TEST_COMMIT_GRAPH=<boolean>, when true, forces the commit-graph to
 be written after every 'git commit' command, and overrides the
 'core.commitGraph' setting to true.
 
+GIT_TEST_COMMIT_GRAPH_NO_GDAT=<boolean>, when true, forces the
+commit-graph to be written without generation data chunk.
+
 GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=<boolean>, when true, forces
 commit-graph write to compute and write changed path Bloom filters for
 every 'git commit-graph write', as if the `--changed-paths` option was
diff --git a/t/helper/test-read-graph.c b/t/helper/test-read-graph.c
index 5f585a17256..75927b2c81d 100644
--- a/t/helper/test-read-graph.c
+++ b/t/helper/test-read-graph.c
@@ -33,6 +33,10 @@ int cmd__read_graph(int argc, const char **argv)
 		printf(" oid_lookup");
 	if (graph->chunk_commit_data)
 		printf(" commit_metadata");
+	if (graph->chunk_generation_data)
+		printf(" generation_data");
+	if (graph->chunk_generation_data_overflow)
+		printf(" generation_data_overflow");
 	if (graph->chunk_extra_edges)
 		printf(" extra_edges");
 	if (graph->chunk_bloom_indexes)
diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh
index d11040ce41c..dbde0161882 100755
--- a/t/t4216-log-bloom.sh
+++ b/t/t4216-log-bloom.sh
@@ -40,11 +40,11 @@ test_expect_success 'setup test - repo, commits, commit graph, log outputs' '
 '
 
 graph_read_expect () {
-	NUM_CHUNKS=5
+	NUM_CHUNKS=6
 	cat >expect <<- EOF
 	header: 43475048 1 $(test_oid oid_version) $NUM_CHUNKS 0
 	num_commits: $1
-	chunks: oid_fanout oid_lookup commit_metadata bloom_indexes bloom_data
+	chunks: oid_fanout oid_lookup commit_metadata generation_data bloom_indexes bloom_data
 	EOF
 	test-tool read-graph >actual &&
 	test_cmp expect actual
diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
index 2ed0c1544da..fa27df579a5 100755
--- a/t/t5318-commit-graph.sh
+++ b/t/t5318-commit-graph.sh
@@ -76,7 +76,7 @@ graph_git_behavior 'no graph' full commits/3 commits/1
 graph_read_expect() {
 	OPTIONAL=""
 	NUM_CHUNKS=3
-	if test ! -z $2
+	if test ! -z "$2"
 	then
 		OPTIONAL=" $2"
 		NUM_CHUNKS=$((3 + $(echo "$2" | wc -w)))
@@ -103,14 +103,14 @@ test_expect_success 'exit with correct error on bad input to --stdin-commits' '
 	# valid commit and tree OID
 	git rev-parse HEAD HEAD^{tree} >in &&
 	git commit-graph write --stdin-commits <in &&
-	graph_read_expect 3
+	graph_read_expect 3 generation_data
 '
 
 test_expect_success 'write graph' '
 	cd "$TRASH_DIRECTORY/full" &&
 	git commit-graph write &&
 	test_path_is_file $objdir/info/commit-graph &&
-	graph_read_expect "3"
+	graph_read_expect "3" generation_data
 '
 
 test_expect_success POSIXPERM 'write graph has correct permissions' '
@@ -219,7 +219,7 @@ test_expect_success 'write graph with merges' '
 	cd "$TRASH_DIRECTORY/full" &&
 	git commit-graph write &&
 	test_path_is_file $objdir/info/commit-graph &&
-	graph_read_expect "10" "extra_edges"
+	graph_read_expect "10" "generation_data extra_edges"
 '
 
 graph_git_behavior 'merge 1 vs 2' full merge/1 merge/2
@@ -254,7 +254,7 @@ test_expect_success 'write graph with new commit' '
 	cd "$TRASH_DIRECTORY/full" &&
 	git commit-graph write &&
 	test_path_is_file $objdir/info/commit-graph &&
-	graph_read_expect "11" "extra_edges"
+	graph_read_expect "11" "generation_data extra_edges"
 '
 
 graph_git_behavior 'full graph, commit 8 vs merge 1' full commits/8 merge/1
@@ -264,7 +264,7 @@ test_expect_success 'write graph with nothing new' '
 	cd "$TRASH_DIRECTORY/full" &&
 	git commit-graph write &&
 	test_path_is_file $objdir/info/commit-graph &&
-	graph_read_expect "11" "extra_edges"
+	graph_read_expect "11" "generation_data extra_edges"
 '
 
 graph_git_behavior 'cleared graph, commit 8 vs merge 1' full commits/8 merge/1
@@ -274,7 +274,7 @@ test_expect_success 'build graph from latest pack with closure' '
 	cd "$TRASH_DIRECTORY/full" &&
 	cat new-idx | git commit-graph write --stdin-packs &&
 	test_path_is_file $objdir/info/commit-graph &&
-	graph_read_expect "9" "extra_edges"
+	graph_read_expect "9" "generation_data extra_edges"
 '
 
 graph_git_behavior 'graph from pack, commit 8 vs merge 1' full commits/8 merge/1
@@ -287,7 +287,7 @@ test_expect_success 'build graph from commits with closure' '
 	git rev-parse merge/1 >>commits-in &&
 	cat commits-in | git commit-graph write --stdin-commits &&
 	test_path_is_file $objdir/info/commit-graph &&
-	graph_read_expect "6"
+	graph_read_expect "6" "generation_data"
 '
 
 graph_git_behavior 'graph from commits, commit 8 vs merge 1' full commits/8 merge/1
@@ -297,7 +297,7 @@ test_expect_success 'build graph from commits with append' '
 	cd "$TRASH_DIRECTORY/full" &&
 	git rev-parse merge/3 | git commit-graph write --stdin-commits --append &&
 	test_path_is_file $objdir/info/commit-graph &&
-	graph_read_expect "10" "extra_edges"
+	graph_read_expect "10" "generation_data extra_edges"
 '
 
 graph_git_behavior 'append graph, commit 8 vs merge 1' full commits/8 merge/1
@@ -307,7 +307,7 @@ test_expect_success 'build graph using --reachable' '
 	cd "$TRASH_DIRECTORY/full" &&
 	git commit-graph write --reachable &&
 	test_path_is_file $objdir/info/commit-graph &&
-	graph_read_expect "11" "extra_edges"
+	graph_read_expect "11" "generation_data extra_edges"
 '
 
 graph_git_behavior 'append graph, commit 8 vs merge 1' full commits/8 merge/1
@@ -328,7 +328,7 @@ test_expect_success 'write graph in bare repo' '
 	cd "$TRASH_DIRECTORY/bare" &&
 	git commit-graph write &&
 	test_path_is_file $baredir/info/commit-graph &&
-	graph_read_expect "11" "extra_edges"
+	graph_read_expect "11" "generation_data extra_edges"
 '
 
 graph_git_behavior 'bare repo with graph, commit 8 vs merge 1' bare commits/8 merge/1
@@ -454,8 +454,9 @@ test_expect_success 'warn on improper hash version' '
 
 test_expect_success 'git commit-graph verify' '
 	cd "$TRASH_DIRECTORY/full" &&
-	git rev-parse commits/8 | git commit-graph write --stdin-commits &&
-	git commit-graph verify >output
+	git rev-parse commits/8 | GIT_TEST_COMMIT_GRAPH_NO_GDAT=1 git commit-graph write --stdin-commits &&
+	git commit-graph verify >output &&
+	graph_read_expect 9 extra_edges
 '
 
 NUM_COMMITS=9
@@ -741,4 +742,56 @@ test_expect_success 'corrupt commit-graph write (missing tree)' '
 	)
 '
 
+# We test the overflow-related code with the following repo history:
+#
+#               4:F - 5:N - 6:U
+#              /                \
+# 1:U - 2:N - 3:U                M:N
+#              \                /
+#               7:N - 8:F - 9:N
+#
+# Here the commits denoted by U have committer date of zero seconds
+# since Unix epoch, the commits denoted by N have committer date
+# starting from 1112354055 seconds since Unix epoch (default committer
+# date for the test suite), and the commits denoted by F have committer
+# date of (2 ^ 31 - 2) seconds since Unix epoch.
+#
+# The largest offset observed is 2 ^ 31, just large enough to overflow.
+#
+
+test_expect_success 'set up and verify repo with generation data overflow chunk' '
+	objdir=".git/objects" &&
+	UNIX_EPOCH_ZERO="@0 +0000" &&
+	FUTURE_DATE="@2147483646 +0000" &&
+	test_oid_cache <<-EOF &&
+	oid_version sha1:1
+	oid_version sha256:2
+	EOF
+	cd "$TRASH_DIRECTORY" &&
+	mkdir repo &&
+	cd repo &&
+	git init &&
+	test_commit --date "$UNIX_EPOCH_ZERO" 1 &&
+	test_commit 2 &&
+	test_commit --date "$UNIX_EPOCH_ZERO" 3 &&
+	git commit-graph write --reachable &&
+	graph_read_expect 3 generation_data &&
+	test_commit --date "$FUTURE_DATE" 4 &&
+	test_commit 5 &&
+	test_commit --date "$UNIX_EPOCH_ZERO" 6 &&
+	git branch left &&
+	git reset --hard 3 &&
+	test_commit 7 &&
+	test_commit --date "$FUTURE_DATE" 8 &&
+	test_commit 9 &&
+	git branch right &&
+	git reset --hard 3 &&
+	test_merge M left right &&
+	git commit-graph write --reachable &&
+	graph_read_expect 10 "generation_data generation_data_overflow" &&
+	git commit-graph verify
+'
+
+graph_git_behavior 'generation data overflow chunk repo' repo left right
+
 test_done
diff --git a/t/t5324-split-commit-graph.sh b/t/t5324-split-commit-graph.sh
index 4d3842b83b9..587757b62d9 100755
--- a/t/t5324-split-commit-graph.sh
+++ b/t/t5324-split-commit-graph.sh
@@ -13,11 +13,11 @@ test_expect_success 'setup repo' '
 	infodir=".git/objects/info" &&
 	graphdir="$infodir/commit-graphs" &&
 	test_oid_cache <<-EOM
-	shallow sha1:1760
-	shallow sha256:2064
+	shallow sha1:2132
+	shallow sha256:2436
 
-	base sha1:1376
-	base sha256:1496
+	base sha1:1408
+	base sha256:1528
 
 	oid_version sha1:1
 	oid_version sha256:2
@@ -31,9 +31,9 @@ graph_read_expect() {
 		NUM_BASE=$2
 	fi
 	cat >expect <<- EOF
-	header: 43475048 1 $(test_oid oid_version) 3 $NUM_BASE
+	header: 43475048 1 $(test_oid oid_version) 4 $NUM_BASE
 	num_commits: $1
-	chunks: oid_fanout oid_lookup commit_metadata
+	chunks: oid_fanout oid_lookup commit_metadata generation_data
 	EOF
 	test-tool read-graph >output &&
 	test_cmp expect output
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index af10f0dc090..e2d33a8a4c4 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -55,6 +55,9 @@ test_expect_success 'setup' '
 	git show-ref -s commit-5-5 | git commit-graph write --stdin-commits &&
 	mv .git/objects/info/commit-graph commit-graph-half &&
 	chmod u+w commit-graph-half &&
+	GIT_TEST_COMMIT_GRAPH_NO_GDAT=1 git commit-graph write --reachable &&
+	mv .git/objects/info/commit-graph commit-graph-no-gdat &&
+	chmod u+w commit-graph-no-gdat &&
 	git config core.commitGraph true
 '
 
@@ -67,6 +70,9 @@ run_all_modes () {
 	test_cmp expect actual &&
 	cp commit-graph-half .git/objects/info/commit-graph &&
 	"$@" <input >actual &&
+	test_cmp expect actual &&
+	cp commit-graph-no-gdat .git/objects/info/commit-graph &&
+	"$@" <input >actual &&
 	test_cmp expect actual
 }
 
diff --git a/t/test-lib-functions.sh b/t/test-lib-functions.sh
index 999982fe4a9..3ad712c3acc 100644
--- a/t/test-lib-functions.sh
+++ b/t/test-lib-functions.sh
@@ -202,6 +202,12 @@ test_commit () {
 		--signoff)
 			signoff="$1"
 			;;
+		--date)
+			notick=yes
+			GIT_COMMITTER_DATE="$2"
+			GIT_AUTHOR_DATE="$2"
+			shift
+			;;
 		-C)
 			indir="$2"
 			shift
-- 
gitgitgadget
Previous: Abhishek Kumar via GitGitGadgetNext: Abhishek Kumar via GitGitGadget
Message 188 of 211 in “[GSoC] Implement Corrected Commit Date”
  1. 0/6 [GSoC] Implement Corrected Commit DateAbhishek Kumar via GitGitGadget, Jul 28, 2020
  2. 1/6 commit-graph: fix regression when computing bloom filterAbhishek Kumar via GitGitGadget, Jul 28, 2020
  3. Taylor BlauJul 28, 2020
  4. Abhishek KumarJul 30, 2020
  5. Jakub NarębskiAug 4, 2020
  6. Taylor BlauAug 4, 2020
  7. Jakub NarębskiAug 4, 2020
  8. Jakub NarębskiAug 4, 2020
  9. 2/6 revision: parse parent in indegree_walk_step()Abhishek Kumar via GitGitGadget, Jul 28, 2020
  10. Derrick StoleeJul 28, 2020
  11. Taylor BlauJul 28, 2020
  12. Jakub NarębskiAug 5, 2020
  13. 3/6 commit-graph: consolidate fill_commit_graph_infoAbhishek Kumar via GitGitGadget, Jul 28, 2020
  14. Derrick StoleeJul 28, 2020
  15. René ScharfeJul 28, 2020
  16. Derrick StoleeJul 28, 2020
  17. Taylor BlauJul 28, 2020
  18. Abhishek KumarJul 30, 2020
  19. 4/6 commit-graph: consolidate compare_commits_by_genAbhishek Kumar via GitGitGadget, Jul 28, 2020
  20. Taylor BlauJul 28, 2020
  21. 5/6 commit-graph: implement generation data chunkAbhishek Kumar via GitGitGadget, Jul 28, 2020
  22. Taylor BlauJul 28, 2020
  23. Abhishek KumarJul 30, 2020
  24. 6/6 commit-graph: implement corrected commit date offsetAbhishek Kumar via GitGitGadget, Jul 28, 2020
  25. Derrick StoleeJul 28, 2020
  26. Taylor BlauJul 28, 2020
  27. Abhishek KumarJul 30, 2020
  28. Taylor BlauJul 28, 2020
  29. Abhishek KumarJul 30, 2020
  30. Derrick StoleeJul 28, 2020
  31. 00/10 [GSoC] Implement Corrected Commit DateAbhishek Kumar via GitGitGadget, Aug 9, 2020
  32. 01/10 commit-graph: fix regression when computing bloom filterAbhishek Kumar via GitGitGadget, Aug 9, 2020
  33. 03/10 commit-graph: consolidate fill_commit_graph_infoAbhishek Kumar via GitGitGadget, Aug 9, 2020
  34. 02/10 revision: parse parent in indegree_walk_step()Abhishek Kumar via GitGitGadget, Aug 9, 2020
  35. 08/10 commit-graph: handle mixed generation commit chainsAbhishek Kumar via GitGitGadget, Aug 9, 2020
  36. Derrick StoleeAug 10, 2020
  37. Abhishek KumarAug 11, 2020
  38. Derrick StoleeAug 11, 2020
  39. 09/10 commit-reach: use corrected commit dates in paint_down_to_common()Abhishek Kumar via GitGitGadget, Aug 9, 2020
  40. 07/10 commit-graph: implement corrected commit dateAbhishek Kumar via GitGitGadget, Aug 9, 2020
  41. Derrick StoleeAug 10, 2020
  42. Abhishek KumarAug 14, 2020
  43. Derrick StoleeAug 14, 2020
  44. 06/10 commit-graph: return 64-bit generation numberAbhishek Kumar via GitGitGadget, Aug 9, 2020
  45. 10/10 doc: add corrected commit date infoAbhishek Kumar via GitGitGadget, Aug 9, 2020
  46. 04/10 commit-graph: consolidate compare_commits_by_genAbhishek Kumar via GitGitGadget, Aug 9, 2020
  47. 05/10 commit-graph: implement generation data chunkAbhishek Kumar via GitGitGadget, Aug 9, 2020
  48. Derrick StoleeAug 10, 2020
  49. Abhishek KumarAug 11, 2020
  50. Derrick StoleeAug 11, 2020
  51. Taylor BlauAug 11, 2020
  52. Derrick StoleeAug 10, 2020
  53. 00/11 [GSoC] Implement Corrected Commit DateAbhishek Kumar via GitGitGadget, Aug 15, 2020
  54. 01/11 commit-graph: fix regression when computing bloom filterAbhishek Kumar via GitGitGadget, Aug 15, 2020
  55. Jakub NarębskiAug 17, 2020
  56. 04/11 commit-graph: consolidate compare_commits_by_genAbhishek Kumar via GitGitGadget, Aug 15, 2020
  57. Derrick StoleeAug 17, 2020
  58. Jakub NarębskiAug 21, 2020
  59. 11/11 doc: add corrected commit date infoAbhishek Kumar via GitGitGadget, Aug 15, 2020
  60. Jakub NarębskiAug 22, 2020
  61. Abhishek KumarAug 27, 2020
  62. Jakub NarębskiAug 27, 2020
  63. Derrick StoleeAug 27, 2020
  64. Abhishek KumarSep 1, 2020
  65. 05/11 commit-graph: return 64-bit generation numberAbhishek Kumar via GitGitGadget, Aug 15, 2020
  66. Jakub NarębskiAug 21, 2020
  67. Abhishek KumarAug 25, 2020
  68. Jakub NarębskiAug 25, 2020
  69. Abhishek KumarSep 1, 2020
  70. Jakub NarębskiSep 3, 2020
  71. Abhishek KumarSep 5, 2020
  72. Jakub NarębskiSep 13, 2020
  73. Jakub NarębskiSep 28, 2020
  74. Abhishek KumarOct 5, 2020
  75. 10/11 commit-reach: use corrected commit dates in paint_down_to_common()Abhishek Kumar via GitGitGadget, Aug 15, 2020
  76. Jakub NarębskiAug 22, 2020
  77. Abhishek KumarSep 1, 2020
  78. Jakub NarębskiSep 3, 2020
  79. 09/11 commit-graph: use generation v2 only if entire chain doesAbhishek Kumar via GitGitGadget, Aug 15, 2020
  80. Jakub NarębskiAug 22, 2020
  81. Abhishek KumarAug 26, 2020
  82. Jakub NarębskiAug 26, 2020
  83. 08/11 commit-graph: implement generation data chunkAbhishek Kumar via GitGitGadget, Aug 15, 2020
  84. Jakub NarębskiAug 22, 2020
  85. 06/11 commit-graph: add a slab to store topological levelsAbhishek Kumar via GitGitGadget, Aug 15, 2020
  86. Jakub NarębskiAug 21, 2020
  87. Abhishek KumarAug 25, 2020
  88. Jakub NarębskiAug 25, 2020
  89. Jakub NarębskiAug 25, 2020
  90. Abhishek KumarSep 1, 2020
  91. Jakub NarębskiSep 3, 2020
  92. 03/11 commit-graph: consolidate fill_commit_graph_infoAbhishek Kumar via GitGitGadget, Aug 15, 2020
  93. Jakub NarębskiAug 19, 2020
  94. Abhishek KumarAug 21, 2020
  95. Jakub NarębskiAug 25, 2020
  96. Abhishek KumarSep 1, 2020
  97. 07/11 commit-graph: implement corrected commit dateAbhishek Kumar via GitGitGadget, Aug 15, 2020
  98. Jakub NarębskiAug 22, 2020
  99. Abhishek KumarAug 25, 2020
  100. Jakub NarębskiAug 25, 2020
  101. Abhishek KumarSep 1, 2020
  102. 02/11 revision: parse parent in indegree_walk_step()Abhishek Kumar via GitGitGadget, Aug 15, 2020
  103. Jakub NarębskiAug 18, 2020
  104. Jakub NarębskiAug 17, 2020
  105. Abhishek KumarAug 18, 2020
  106. Jakub NarębskiAug 23, 2020
  107. Abhishek KumarAug 24, 2020
  108. 00/10 [GSoC] Implement Corrected Commit DateAbhishek Kumar via GitGitGadget, Oct 7, 2020
  109. 02/10 revision: parse parent in indegree_walk_step()Abhishek Kumar via GitGitGadget, Oct 7, 2020
  110. Jakub NarębskiOct 24, 2020
  111. 01/10 commit-graph: fix regression when computing Bloom filtersAbhishek Kumar via GitGitGadget, Oct 7, 2020
  112. Jakub NarębskiOct 24, 2020
  113. Taylor BlauOct 25, 2020
  114. Abhishek KumarNov 3, 2020
  115. 03/10 commit-graph: consolidate fill_commit_graph_infoAbhishek Kumar via GitGitGadget, Oct 7, 2020
  116. Jakub NarębskiOct 25, 2020
  117. Abhishek KumarOct 27, 2020
  118. 05/10 commit-graph: add a slab to store topological levelsAbhishek Kumar via GitGitGadget, Oct 7, 2020
  119. Jakub NarębskiOct 25, 2020
  120. 04/10 commit-graph: return 64-bit generation numberAbhishek Kumar via GitGitGadget, Oct 7, 2020
  121. Jakub NarębskiOct 25, 2020
  122. Abhishek KumarNov 3, 2020
  123. 10/10 doc: add corrected commit date infoAbhishek Kumar via GitGitGadget, Oct 7, 2020
  124. Jakub NarębskiNov 4, 2020
  125. Abhishek KumarNov 21, 2020
  126. 09/10 commit-reach: use corrected commit dates in paint_down_to_common()Abhishek Kumar via GitGitGadget, Oct 7, 2020
  127. Jakub NarębskiNov 3, 2020
  128. Junio C HamanoNov 3, 2020
  129. Abhishek KumarNov 20, 2020
  130. 07/10 commit-graph: implement generation data chunkAbhishek Kumar via GitGitGadget, Oct 7, 2020
  131. Jakub NarębskiOct 30, 2020
  132. Abhishek KumarNov 6, 2020
  133. Jakub NarębskiNov 6, 2020
  134. 08/10 commit-graph: use generation v2 only if entire chain doesAbhishek Kumar via GitGitGadget, Oct 7, 2020
  135. Jakub NarębskiNov 1, 2020
  136. Abhishek KumarNov 12, 2020
  137. Jakub NarębskiNov 13, 2020
  138. 06/10 commit-graph: implement corrected commit dateAbhishek Kumar via GitGitGadget, Oct 7, 2020
  139. Jakub NarębskiOct 27, 2020
  140. Abhishek KumarNov 3, 2020
  141. Jakub NarębskiNov 4, 2020
  142. Philip OakleyNov 5, 2020
  143. Junio C HamanoNov 5, 2020
  144. Extending and updating gitglossary (was: Re: [PATCH v4 06/10] commit-graph: implement corrected commit date)Jakub Narębski, Nov 6, 2020
  145. Junio C HamanoNov 6, 2020
  146. Philip OakleyNov 8, 2020
  147. Jakub NarębskiNov 10, 2020
  148. Philip OakleyNov 10, 2020
  149. Jakub NarębskiNov 10, 2020
  150. Jakub NarębskiNov 4, 2020
  151. Abhishek KumarNov 22, 2020
  152. 00/11 [GSoC] Implement Corrected Commit DateAbhishek Kumar via GitGitGadget, Dec 28, 2020
  153. 01/11 commit-graph: fix regression when computing Bloom filtersAbhishek Kumar via GitGitGadget, Dec 28, 2020
  154. Derrick StoleeDec 30, 2020
  155. Abhishek KumarJan 8, 2021
  156. SZEDER GáborJan 5, 2021
  157. SZEDER GáborJan 5, 2021
  158. Abhishek KumarJan 8, 2021
  159. 02/11 revision: parse parent in indegree_walk_step()Abhishek Kumar via GitGitGadget, Dec 28, 2020
  160. 03/11 commit-graph: consolidate fill_commit_graph_infoAbhishek Kumar via GitGitGadget, Dec 28, 2020
  161. 04/11 t6600-test-reach: generalize *_three_modesAbhishek Kumar via GitGitGadget, Dec 28, 2020
  162. 05/11 commit-graph: add a slab to store topological levelsAbhishek Kumar via GitGitGadget, Dec 28, 2020
  163. 06/11 commit-graph: return 64-bit generation numberAbhishek Kumar via GitGitGadget, Dec 28, 2020
  164. 10/11 commit-reach: use corrected commit dates in paint_down_to_common()Abhishek Kumar via GitGitGadget, Dec 28, 2020
  165. 07/11 commit-graph: implement corrected commit dateAbhishek Kumar via GitGitGadget, Dec 28, 2020
  166. Derrick StoleeDec 30, 2020
  167. Abhishek KumarJan 10, 2021
  168. 11/11 doc: add corrected commit date infoAbhishek Kumar via GitGitGadget, Dec 28, 2020
  169. 08/11 commit-graph: implement generation data chunkAbhishek Kumar via GitGitGadget, Dec 28, 2020
  170. 09/11 commit-graph: use generation v2 only if entire chain doesAbhishek Kumar via GitGitGadget, Dec 28, 2020
  171. Derrick StoleeDec 30, 2020
  172. Abhishek KumarJan 10, 2021
  173. Derrick StoleeJan 11, 2021
  174. Derrick StoleeDec 30, 2020
  175. Abhishek KumarJan 10, 2021
  176. 00/11 [GSoC] Implement Corrected Commit DateAbhishek Kumar via GitGitGadget, Jan 16, 2021
  177. 02/11 revision: parse parent in indegree_walk_step()Abhishek Kumar via GitGitGadget, Jan 16, 2021
  178. 01/11 commit-graph: fix regression when computing Bloom filtersAbhishek Kumar via GitGitGadget, Jan 16, 2021
  179. 03/11 commit-graph: consolidate fill_commit_graph_infoAbhishek Kumar via GitGitGadget, Jan 16, 2021
  180. 04/11 t6600-test-reach: generalize *_three_modesAbhishek Kumar via GitGitGadget, Jan 16, 2021
  181. 07/11 commit-graph: implement corrected commit dateAbhishek Kumar via GitGitGadget, Jan 16, 2021
  182. 06/11 commit-graph: return 64-bit generation numberAbhishek Kumar via GitGitGadget, Jan 16, 2021
  183. 11/11 doc: add corrected commit date infoAbhishek Kumar via GitGitGadget, Jan 16, 2021
  184. SZEDER GáborJan 27, 2021
  185. Abhishek KumarJan 30, 2021
  186. Taylor BlauJan 31, 2021
  187. 05/11 commit-graph: add a slab to store topological levelsAbhishek Kumar via GitGitGadget, Jan 16, 2021
  188. 08/11 commit-graph: implement generation data chunkAbhishek Kumar via GitGitGadget, Jan 16, 2021
  189. 10/11 commit-reach: use corrected commit dates in paint_down_to_common()Abhishek Kumar via GitGitGadget, Jan 16, 2021
  190. 09/11 commit-graph: use generation v2 only if entire chain doesAbhishek Kumar via GitGitGadget, Jan 16, 2021
  191. Derrick StoleeJan 18, 2021
  192. Taylor BlauJan 18, 2021
  193. Abhishek KumarJan 23, 2021
  194. Junio C HamanoJan 19, 2021
  195. Abhishek KumarJan 23, 2021
  196. 00/11 [GSoC] Implement Corrected Commit DateAbhishek Kumar via GitGitGadget, Feb 1, 2021
  197. 01/11 commit-graph: fix regression when computing Bloom filtersAbhishek Kumar via GitGitGadget, Feb 1, 2021
  198. 02/11 revision: parse parent in indegree_walk_step()Abhishek Kumar via GitGitGadget, Feb 1, 2021
  199. 03/11 commit-graph: consolidate fill_commit_graph_infoAbhishek Kumar via GitGitGadget, Feb 1, 2021
  200. 04/11 t6600-test-reach: generalize *_three_modesAbhishek Kumar via GitGitGadget, Feb 1, 2021
  201. 05/11 commit-graph: add a slab to store topological levelsAbhishek Kumar via GitGitGadget, Feb 1, 2021
  202. 06/11 commit-graph: return 64-bit generation numberAbhishek Kumar via GitGitGadget, Feb 1, 2021
  203. 08/11 commit-graph: implement corrected commit dateAbhishek Kumar via GitGitGadget, Feb 1, 2021
  204. 10/11 commit-graph: use generation v2 only if entire chain doesAbhishek Kumar via GitGitGadget, Feb 1, 2021
  205. 09/11 commit-graph: implement generation data chunkAbhishek Kumar via GitGitGadget, Feb 1, 2021
  206. 07/11 commit-graph: document generation number v2Abhishek Kumar via GitGitGadget, Feb 1, 2021
  207. 11/11 commit-reach: use corrected commit dates in paint_down_to_common()Abhishek Kumar via GitGitGadget, Feb 1, 2021
  208. Derrick StoleeFeb 1, 2021
  209. Junio C HamanoFeb 1, 2021
  210. Taylor BlauAug 17, 2020
  211. Jakub NarębskiAug 17, 2020

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.