[6/7] commit-graph: parse file format v2

Commit Message

Derrick Stolee Feb. 24, 2022, 8:38 p.m. UTC

From: Derrick Stolee <[e-mail]>

The commit-graph file format v2 alters how it stores the corrected
commit date offsets within the Commit Data chunk instead of a separate
chunk. The idea is to significantly reduce the amount of data loaded
from disk while parsing the commit-graph.

We need to alter the error message when we see a file format version
outside of our range now that multiple are possible. This has a
non-functional side-effect of altering a use of GRAPH_VERSION within
write_commit_graph().

By storing the file format version in 'struct commit_graph', we can
alter the parsing code to depend on that version value. This involves
changing where we look for the corrected commit date offset, but also
which constants we use for jumping into the Generation Data Overflow
chunk. The Commit Data chunk only has 30 bits available for the offset
while the Generation Data chunk has 32 bits. This only makes a
meaningful difference in very malformed repositories.

Also, we need to be careful about how we enable using corrected commit
dates and generation numbers to rely upon the read_generation_data value
instead of a non-zero value in the Commit Date chunk. In
generation_numbers_enabled(), the first_generation variable is
attemptint to look for the first topological level stored to see that it
is nonzero. However, for a v2 commit-graph, this value is actually
likely to be zero because the corrected commit date offset is probably
zero.

Signed-off-by: Derrick Stolee <[e-mail]>
---
 commit-graph.c          | 43 +++++++++++++++++++++++++++++------------
 commit-graph.h          |  6 ++++++
 t/t5318-commit-graph.sh |  2 +-
 3 files changed, 38 insertions(+), 13 deletions(-)

Comments

Junio C Hamano Feb. 24, 2022, 11:01 p.m. UTC | #1

"Derrick Stolee via GitGitGadget" <[e-mail]> writes:

> From: Derrick Stolee <[e-mail]>
>
> The commit-graph file format v2 alters how it stores the corrected
> commit date offsets within the Commit Data chunk instead of a separate
> chunk. The idea is to significantly reduce the amount of data loaded
> from disk while parsing the commit-graph.
>
> We need to alter the error message when we see a file format version
> outside of our range now that multiple are possible. This has a
> non-functional side-effect of altering a use of GRAPH_VERSION within
> write_commit_graph().
>
> By storing the file format version in 'struct commit_graph', we can
> alter the parsing code to depend on that version value. This involves
> changing where we look for the corrected commit date offset, but also
> which constants we use for jumping into the Generation Data Overflow
> chunk. The Commit Data chunk only has 30 bits available for the offset
> while the Generation Data chunk has 32 bits. This only makes a
> meaningful difference in very malformed repositories.
>
> Also, we need to be careful about how we enable using corrected commit
> dates and generation numbers to rely upon the read_generation_data value
> instead of a non-zero value in the Commit Date chunk. In
> generation_numbers_enabled(), the first_generation variable is
> attemptint to look for the first topological level stored to see that it
> is nonzero. However, for a v2 commit-graph, this value is actually
> likely to be zero because the corrected commit date offset is probably
> zero.

I see references to OVERFLOW_V3 that comes after OVERFLOW, but there
is no OVERFLOW_V2.  Intended, or should it be V2 to match the "file
format v2" of "generation number v2"?  It is getting awkward to have
two different version scheme ("gen v2" means corrected committer
timestamp, whose on-disk representation is different between "file
v1" and "file v2", and this OVERFLOW vs OVERFLOW_V3 is about the
difference between "file v1" and "file v2" if I am following the
series correctly).

Derrick Stolee Feb. 25, 2022, 1:54 p.m. UTC | #2

On 2/24/2022 6:01 PM, Junio C Hamano wrote:
> "Derrick Stolee via GitGitGadget" <[e-mail]> writes:
> 
>> From: Derrick Stolee <[e-mail]>
>>
>> The commit-graph file format v2 alters how it stores the corrected
>> commit date offsets within the Commit Data chunk instead of a separate
>> chunk. The idea is to significantly reduce the amount of data loaded
>> from disk while parsing the commit-graph.
>>
>> We need to alter the error message when we see a file format version
>> outside of our range now that multiple are possible. This has a
>> non-functional side-effect of altering a use of GRAPH_VERSION within
>> write_commit_graph().
>>
>> By storing the file format version in 'struct commit_graph', we can
>> alter the parsing code to depend on that version value. This involves
>> changing where we look for the corrected commit date offset, but also
>> which constants we use for jumping into the Generation Data Overflow
>> chunk. The Commit Data chunk only has 30 bits available for the offset
>> while the Generation Data chunk has 32 bits. This only makes a
>> meaningful difference in very malformed repositories.
>>
>> Also, we need to be careful about how we enable using corrected commit
>> dates and generation numbers to rely upon the read_generation_data value
>> instead of a non-zero value in the Commit Date chunk. In
>> generation_numbers_enabled(), the first_generation variable is
>> attemptint to look for the first topological level stored to see that it
>> is nonzero. However, for a v2 commit-graph, this value is actually
>> likely to be zero because the corrected commit date offset is probably
>> zero.
> 
> I see references to OVERFLOW_V3 that comes after OVERFLOW, but there
> is no OVERFLOW_V2.  Intended, or should it be V2 to match the "file
> format v2" of "generation number v2"?  It is getting awkward to have
> two different version scheme ("gen v2" means corrected committer
> timestamp, whose on-disk representation is different between "file
> v1" and "file v2", and this OVERFLOW vs OVERFLOW_V3 is about the
> difference between "file v1" and "file v2" if I am following the
> series correctly).

You're right that it would be clearer to rename OVERFLOW to
OVERFLOW_V2. I'll add that to my next version when these patches
appear on their own.

Thanks,
-Stolee

Patch

diff --git a/commit-graph.c b/commit-graph.c
index b86a6a634fe..366fc4d6e41 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -49,7 +49,9 @@  void git_test_write_commit_graph_or_die(void)
 #define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16)
 
 #define GRAPH_VERSION_1 0x1
-#define GRAPH_VERSION GRAPH_VERSION_1
+#define GRAPH_VERSION_2 0x2
+#define GRAPH_VERSION_MIN GRAPH_VERSION_1
+#define GRAPH_VERSION_MAX GRAPH_VERSION_2
 
 #define GRAPH_EXTRA_EDGES_NEEDED 0x80000000
 #define GRAPH_EDGE_LAST_MASK 0x7fffffff
@@ -63,6 +65,7 @@  void git_test_write_commit_graph_or_die(void)
 			+ GRAPH_FANOUT_SIZE + the_hash_algo->rawsz)
 
 #define CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW (1ULL << 31)
+#define CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW_V3 (1ULL << 29)
 
 /* Remember to update object flag allocation in object.h */
 #define REACHABLE       (1u<<15)
@@ -358,9 +361,10 @@  struct commit_graph *parse_commit_graph(struct repository *r,
 	}
 
 	graph_version = *(unsigned char*)(data + 4);
-	if (graph_version != GRAPH_VERSION) {
-		error(_("commit-graph version %X does not match version %X"),
-		      graph_version, GRAPH_VERSION);
+	if (graph_version < GRAPH_VERSION_MIN ||
+	    graph_version > GRAPH_VERSION_MAX) {
+		error(_("commit-graph version %X is not understood"),
+		      graph_version);
 		return NULL;
 	}
 
@@ -375,6 +379,7 @@  struct commit_graph *parse_commit_graph(struct repository *r,
 
 	graph = alloc_commit_graph();
 
+	graph->version = graph_version;
 	graph->hash_len = the_hash_algo->rawsz;
 	graph->num_chunks = *(unsigned char*)(data + 6);
 	graph->data = graph_map;
@@ -402,13 +407,17 @@  struct commit_graph *parse_commit_graph(struct repository *r,
 	pair_chunk(cf, GRAPH_CHUNKID_EXTRAEDGES, &graph->chunk_extra_edges);
 	pair_chunk(cf, GRAPH_CHUNKID_BASE, &graph->chunk_base_graphs);
 
-	if (get_configured_generation_version(r) >= 2) {
-		pair_chunk(cf, GRAPH_CHUNKID_GENERATION_DATA,
-			&graph->chunk_generation_data);
+	if (graph_version >= GRAPH_VERSION_2 ||
+	    get_configured_generation_version(r) >= 2) {
+		/* Skip this chunk if GRAPH_VERSION_2 or higher. */
+		if (graph_version == GRAPH_VERSION_1)
+			pair_chunk(cf, GRAPH_CHUNKID_GENERATION_DATA,
+				   &graph->chunk_generation_data);
 		pair_chunk(cf, GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW,
 			&graph->chunk_generation_data_overflow);
 
-		if (graph->chunk_generation_data)
+		if (graph_version >= GRAPH_VERSION_2 ||
+		    graph->chunk_generation_data)
 			graph->read_generation_data = 1;
 	}
 
@@ -683,6 +692,9 @@  int generation_numbers_enabled(struct repository *r)
 	if (!g->num_commits)
 		return 0;
 
+	if (g->version >= GRAPH_VERSION_2)
+		return g->read_generation_data;
+
 	first_generation = get_be32(g->chunk_commit_data +
 				    g->hash_len + 8) >> 2;
 
@@ -799,13 +811,20 @@  static void fill_commit_graph_info(struct commit *item, struct commit_graph *g,
 	item->date = (timestamp_t)((date_high << 32) | date_low);
 
 	if (g->read_generation_data) {
-		offset = (timestamp_t)get_be32(g->chunk_generation_data + sizeof(uint32_t) * lex_index);
+		timestamp_t overflow_bit;
+		if (g->version == GRAPH_VERSION_2) {
+			offset = (timestamp_t)(get_be32(commit_data + g->hash_len + 8) >> 2);
+			overflow_bit = CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW_V3;
+		} else {
+			offset = (timestamp_t)get_be32(g->chunk_generation_data + sizeof(uint32_t) * lex_index);
+			overflow_bit = CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW;
+		}
 
-		if (offset & CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW) {
+		if (offset & overflow_bit) {
 			if (!g->chunk_generation_data_overflow)
 				die(_("commit-graph requires overflow generation data but has none"));
 
-			offset_pos = offset ^ CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW;
+			offset_pos = offset ^ overflow_bit;
 			graph_data->generation = item->date + get_be64(g->chunk_generation_data_overflow + 8 * offset_pos);
 		} else
 			graph_data->generation = item->date + offset;
@@ -1917,7 +1936,7 @@  static int write_commit_graph_file(struct write_commit_graph_context *ctx)
 
 	hashwrite_be32(f, GRAPH_SIGNATURE);
 
-	hashwrite_u8(f, GRAPH_VERSION);
+	hashwrite_u8(f, GRAPH_VERSION_1);
 	hashwrite_u8(f, oid_version());
 	hashwrite_u8(f, get_num_chunks(cf));
 	hashwrite_u8(f, ctx->num_commit_graphs_after - 1);
diff --git a/commit-graph.h b/commit-graph.h
index 04a94e18302..b379b8eae25 100644
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -63,6 +63,12 @@  struct commit_graph {
 	const unsigned char *data;
 	size_t data_len;
 
+	/**
+	 * The 'version' byte mirrors the file format version. This is
+	 * necessary to consider when parsing commits.
+	 */
+	unsigned version;
+
 	unsigned char hash_len;
 	unsigned char num_chunks;
 	uint32_t num_commits;
diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
index 5e4b0216fa6..a14a13e5f7b 100755
--- a/t/t5318-commit-graph.sh
+++ b/t/t5318-commit-graph.sh
@@ -605,7 +605,7 @@  test_expect_success 'detect bad signature' '
 '
 
 test_expect_success 'detect bad version' '
-	corrupt_graph_and_verify $GRAPH_BYTE_VERSION "\02" \
+	corrupt_graph_and_verify $GRAPH_BYTE_VERSION "\03" \
 		"graph version"
 '